1 /*
2 * C eventloop example.
3 *
4 * Timer management is similar to eventloop.js but implemented in C.
5 * In particular, timer insertion is an O(n) operation; in a real world
6 * eventloop based on a heap insertion would be O(log N).
7 */
8
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <string.h>
12 #include <stdint.h>
13 #include <sys/time.h>
14 #include <poll.h>
15
16 #include "duktape.h"
17
18 #define MAX_TIMERS 4096 /* this is quite excessive for embedded use, but good for testing */
19 #define MIN_DELAY 1.0
20 #define MIN_WAIT 1.0
21 #define MAX_WAIT 60000.0
22 #define MAX_EXPIRYS 10
23
24 #define MAX_FDS 256
25
26 typedef struct {
27 int64_t id; /* numeric ID (returned from e.g. setTimeout); zero if unused */
28 double target; /* next target time */
29 double delay; /* delay/interval */
30 int oneshot; /* oneshot=1 (setTimeout), repeated=0 (setInterval) */
31 int removed; /* timer has been requested for removal */
32
33 /* The callback associated with the timer is held in the "global stash",
34 * in <stash>.eventTimers[String(id)]. The references must be deleted
35 * when a timer struct is deleted.
36 */
37 } ev_timer;
38
39 /* Active timers. Dense list, terminates to end of list or first unused timer.
40 * The list is sorted by 'target', with lowest 'target' (earliest expiry) last
41 * in the list. When a timer's callback is being called, the timer is moved
42 * to 'timer_expiring' as it needs special handling should the user callback
43 * delete that particular timer.
44 */
45 static ev_timer timer_list[MAX_TIMERS];
46 static ev_timer timer_expiring;
47 static int timer_count; /* last timer at timer_count - 1 */
48 static int64_t timer_next_id = 1;
49
50 /* Socket poll state. */
51 static struct pollfd poll_list[MAX_FDS];
52 static int poll_count = 0;
53
54 /* Misc */
55 static int exit_requested = 0;
56
57 /* Get Javascript compatible 'now' timestamp (millisecs since 1970). */
get_now(void)58 static double get_now(void) {
59 struct timeval tv;
60 int rc;
61
62 rc = gettimeofday(&tv, NULL);
63 if (rc != 0) {
64 /* Should never happen, so return whatever. */
65 return 0.0;
66 }
67 return ((double) tv.tv_sec) * 1000.0 + ((double) tv.tv_usec) / 1000.0;
68 }
69
find_nearest_timer(void)70 static ev_timer *find_nearest_timer(void) {
71 /* Last timer expires first (list is always kept sorted). */
72 if (timer_count <= 0) {
73 return NULL;
74 }
75 return timer_list + timer_count - 1;
76 }
77
78 /* Bubble last timer on timer list backwards until it has been moved to
79 * its proper sorted position (based on 'target' time).
80 */
bubble_last_timer(void)81 static void bubble_last_timer(void) {
82 int i;
83 int n = timer_count;
84 ev_timer *t;
85 ev_timer tmp;
86
87 for (i = n - 1; i > 0; i--) {
88 /* Timer to bubble is at index i, timer to compare to is
89 * at i-1 (both guaranteed to exist).
90 */
91 t = timer_list + i;
92 if (t->target <= (t-1)->target) {
93 /* 't' expires earlier than (or same time as) 't-1', so we're done. */
94 break;
95 } else {
96 /* 't' expires later than 't-1', so swap them and repeat. */
97 memcpy((void *) &tmp, (void *) (t - 1), sizeof(ev_timer));
98 memcpy((void *) (t - 1), (void *) t, sizeof(ev_timer));
99 memcpy((void *) t, (void *) &tmp, sizeof(ev_timer));
100 }
101 }
102 }
103
expire_timers(duk_context * ctx)104 static void expire_timers(duk_context *ctx) {
105 ev_timer *t;
106 int sanity = MAX_EXPIRYS;
107 double now;
108 int rc;
109
110 /* Because a user callback can mutate the timer list (by adding or deleting
111 * a timer), we expire one timer and then rescan from the end again. There
112 * is a sanity limit on how many times we do this per expiry round.
113 */
114
115 duk_push_global_stash(ctx);
116 duk_get_prop_string(ctx, -1, "eventTimers");
117
118 /* [ ... stash eventTimers ] */
119
120 now = get_now();
121 while (sanity-- > 0) {
122 /*
123 * If exit has been requested, exit without running further
124 * callbacks.
125 */
126
127 if (exit_requested) {
128 #if 0
129 fprintf(stderr, "exit requested, exiting timer expiry loop\n");
130 fflush(stderr);
131 #endif
132 break;
133 }
134
135 /*
136 * Expired timer(s) still exist?
137 */
138
139 if (timer_count <= 0) {
140 break;
141 }
142 t = timer_list + timer_count - 1;
143 if (t->target > now) {
144 break;
145 }
146
147 /*
148 * Move the timer to 'expiring' for the duration of the callback.
149 * Mark a one-shot timer deleted, compute a new target for an interval.
150 */
151
152 memcpy((void *) &timer_expiring, (void *) t, sizeof(ev_timer));
153 memset((void *) t, 0, sizeof(ev_timer));
154 timer_count--;
155 t = &timer_expiring;
156
157 if (t->oneshot) {
158 t->removed = 1;
159 } else {
160 t->target = now + t->delay; /* XXX: or t->target + t->delay? */
161 }
162
163 /*
164 * Call timer callback. The callback can operate on the timer list:
165 * add new timers, remove timers. The callback can even remove the
166 * expired timer whose callback we're calling. However, because the
167 * timer being expired has been moved to 'timer_expiring', we don't
168 * need to worry about the timer's offset changing on the timer list.
169 */
170
171 #if 0
172 fprintf(stderr, "calling user callback for timer id %d\n", (int) t->id);
173 fflush(stderr);
174 #endif
175
176 duk_push_number(ctx, (double) t->id);
177 duk_get_prop(ctx, -2); /* -> [ ... stash eventTimers func ] */
178 rc = duk_pcall(ctx, 0 /*nargs*/); /* -> [ ... stash eventTimers retval ] */
179 if (rc != 0) {
180 #if 0
181 fprintf(stderr, "timer callback failed for timer %d: %s\n", (int) t->id, duk_to_string(ctx, -1));
182 fflush(stderr);
183 #endif
184 }
185 duk_pop(ctx); /* ignore errors for now -> [ ... stash eventTimers ] */
186
187 if (t->removed) {
188 /* One-shot timer (always removed) or removed by user callback. */
189 #if 0
190 fprintf(stderr, "deleting callback state for timer %d\n", (int) t->id);
191 fflush(stderr);
192 #endif
193 duk_push_number(ctx, (double) t->id);
194 duk_del_prop(ctx, -2);
195 } else {
196 /* Interval timer, not removed by user callback. Queue back to
197 * timer list and bubble to its final sorted position.
198 */
199 #if 0
200 fprintf(stderr, "queueing timer %d back into active list\n", (int) t->id);
201 fflush(stderr);
202 #endif
203 if (timer_count >= MAX_TIMERS) {
204 duk_error(ctx, DUK_ERR_RANGE_ERROR, "out of timer slots");
205 }
206 memcpy((void *) (timer_list + timer_count), (void *) t, sizeof(ev_timer));
207 timer_count++;
208 bubble_last_timer();
209 }
210 }
211
212 memset((void *) &timer_expiring, 0, sizeof(ev_timer));
213
214 duk_pop_2(ctx); /* -> [ ... ] */
215 }
216
compact_poll_list(void)217 static void compact_poll_list(void) {
218 int i, j, n;
219
220 /* i = input index
221 * j = output index (initially same as i)
222 */
223
224 n = poll_count;
225 for (i = 0, j = 0; i < n; i++) {
226 struct pollfd *pfd = poll_list + i;
227 if (pfd->fd == 0) {
228 /* keep output index the same */
229 #if 0
230 fprintf(stderr, "remove pollfd (index %d): fd=%d, events=%d, revents=%d\n",
231 i, pfd->fd, pfd->events, pfd->revents),
232 fflush(stderr);
233 #endif
234
235 continue;
236 }
237 #if 0
238 fprintf(stderr, "keep pollfd (index %d -> %d): fd=%d, events=%d, revents=%d\n",
239 i, j, pfd->fd, pfd->events, pfd->revents),
240 fflush(stderr);
241 #endif
242 if (i != j) {
243 /* copy only if indices have diverged */
244 memcpy((void *) (poll_list + j), (void *) (poll_list + i), sizeof(struct pollfd));
245 }
246 j++;
247 }
248
249 if (j < poll_count) {
250 /* zeroize unused entries for sanity */
251 memset((void *) (poll_list + j), 0, (poll_count - j) * sizeof(struct pollfd));
252 }
253
254 poll_count = j;
255 }
256
eventloop_run(duk_context * ctx)257 int eventloop_run(duk_context *ctx) {
258 ev_timer *t;
259 double now;
260 double diff;
261 int timeout;
262 int rc;
263 int i, n;
264 int idx_eventloop;
265 int idx_fd_handler;
266
267 /* The Ecmascript poll handler is passed through EventLoop.fdPollHandler
268 * which c_eventloop.js sets before we come here.
269 */
270 duk_push_global_object(ctx);
271 duk_get_prop_string(ctx, -1, "EventLoop");
272 duk_get_prop_string(ctx, -1, "fdPollHandler"); /* -> [ global EventLoop fdPollHandler ] */
273 idx_fd_handler = duk_get_top_index(ctx);
274 idx_eventloop = idx_fd_handler - 1;
275
276 for (;;) {
277 /*
278 * Expire timers.
279 */
280
281 expire_timers(ctx);
282
283 /*
284 * If exit requested, bail out as fast as possible.
285 */
286
287 if (exit_requested) {
288 #if 0
289 fprintf(stderr, "exit requested, exiting event loop\n");
290 fflush(stderr);
291 #endif
292 break;
293 }
294
295 /*
296 * Compact poll list by removing pollfds with fd == 0.
297 */
298
299 compact_poll_list();
300
301 /*
302 * Determine poll() timeout (as close to poll() as possible as
303 * the wait is relative).
304 */
305
306 now = get_now();
307 t = find_nearest_timer();
308 if (t) {
309 diff = t->target - now;
310 if (diff < MIN_WAIT) {
311 diff = MIN_WAIT;
312 } else if (diff > MAX_WAIT) {
313 diff = MAX_WAIT;
314 }
315 timeout = (int) diff; /* clamping ensures that fits */
316 } else {
317 if (poll_count == 0) {
318 #if 0
319 fprintf(stderr, "no timers and no sockets to poll, exiting\n");
320 fflush(stderr);
321 #endif
322 break;
323 }
324 timeout = (int) MAX_WAIT;
325 }
326
327 /*
328 * Poll for activity or timeout.
329 */
330
331 #if 0
332 fprintf(stderr, "going to poll, timeout %d ms, pollfd count %d\n", timeout, poll_count);
333 fflush(stderr);
334 #endif
335
336 rc = poll(poll_list, poll_count, timeout);
337 #if 0
338 fprintf(stderr, "poll rc: %d\n", rc);
339 fflush(stderr);
340 #endif
341 if (rc < 0) {
342 /* error */
343 } else if (rc == 0) {
344 /* timeout */
345 } else {
346 /* 'rc' fds active */
347 }
348
349 /*
350 * Check socket activity, handle all sockets. Handling is offloaded to
351 * Ecmascript code (fd + revents).
352 *
353 * If FDs are removed from the poll list while we're processing callbacks,
354 * the entries are simply marked unused (fd set to 0) without actually
355 * removing them from the poll list. This ensures indices are not
356 * disturbed. The poll list is compacted before next poll().
357 */
358
359 n = (rc == 0 ? 0 : poll_count); /* if timeout, no need to check pollfd */
360 for (i = 0; i < n; i++) {
361 struct pollfd *pfd = poll_list + i;
362
363 if (pfd->fd == 0) {
364 /* deleted, perhaps by previous callback */
365 continue;
366 }
367
368 if (pfd->revents) {
369 #if 0
370 fprintf(stderr, "fd %d has revents: %d\n", (int) pfd->fd, (int) pfd->revents);
371 fflush(stderr);
372 #endif
373 duk_dup(ctx, idx_fd_handler);
374 duk_dup(ctx, idx_eventloop);
375 duk_push_int(ctx, pfd->fd);
376 duk_push_int(ctx, pfd->revents);
377 rc = duk_pcall_method(ctx, 2 /*nargs*/);
378 if (rc) {
379 #if 0
380 fprintf(stderr, "fd callback failed for fd %d: %s\n", (int) pfd->fd, duk_to_string(ctx, -1));
381 fflush(stderr);
382 #endif
383 }
384 duk_pop(ctx);
385
386 pfd->revents = 0;
387 }
388
389 }
390 }
391
392 duk_pop_n(ctx, 3);
393
394 return 0;
395 }
396
create_timer(duk_context * ctx)397 static int create_timer(duk_context *ctx) {
398 double delay;
399 int oneshot;
400 int idx;
401 int64_t timer_id;
402 double now;
403 ev_timer *t;
404
405 now = get_now();
406
407 /* indexes:
408 * 0 = function (callback)
409 * 1 = delay
410 * 2 = boolean: oneshot
411 */
412
413 delay = duk_require_number(ctx, 1);
414 if (delay < MIN_DELAY) {
415 delay = MIN_DELAY;
416 }
417 oneshot = duk_require_boolean(ctx, 2);
418
419 if (timer_count >= MAX_TIMERS) {
420 duk_error(ctx, DUK_ERR_RANGE_ERROR, "out of timer slots");
421 }
422 idx = timer_count++;
423 timer_id = timer_next_id++;
424 t = timer_list + idx;
425
426 memset((void *) t, 0, sizeof(ev_timer));
427 t->id = timer_id;
428 t->target = now + delay;
429 t->delay = delay;
430 t->oneshot = oneshot;
431 t->removed = 0;
432
433 /* Timer is now at the last position; use swaps to "bubble" it to its
434 * correct sorted position.
435 */
436
437 bubble_last_timer();
438
439 /* Finally, register the callback to the global stash 'eventTimers' object. */
440
441 duk_push_global_stash(ctx);
442 duk_get_prop_string(ctx, -1, "eventTimers"); /* -> [ func delay oneshot stash eventTimers ] */
443 duk_push_number(ctx, (double) timer_id);
444 duk_dup(ctx, 0);
445 duk_put_prop(ctx, -3); /* eventTimers[timer_id] = callback */
446
447 /* Return timer id. */
448
449 duk_push_number(ctx, (double) timer_id);
450 #if 0
451 fprintf(stderr, "created timer id: %d\n", (int) timer_id);
452 fflush(stderr);
453 #endif
454 return 1;
455 }
456
delete_timer(duk_context * ctx)457 static int delete_timer(duk_context *ctx) {
458 int i, n;
459 int64_t timer_id;
460 ev_timer *t;
461 int found = 0;
462
463 /* indexes:
464 * 0 = timer id
465 */
466
467 timer_id = (int64_t) duk_require_number(ctx, 0);
468
469 /*
470 * Unlike insertion, deletion needs a full scan of the timer list
471 * and an expensive remove. If no match is found, nothing is deleted.
472 * Caller gets a boolean return code indicating match.
473 *
474 * When a timer is being expired and its user callback is running,
475 * the timer has been moved to 'timer_expiring' and its deletion
476 * needs special handling: just mark it to-be-deleted and let the
477 * expiry code remove it.
478 */
479
480 t = &timer_expiring;
481 if (t->id == timer_id) {
482 t->removed = 1;
483 duk_push_true(ctx);
484 #if 0
485 fprintf(stderr, "deleted expiring timer id: %d\n", (int) timer_id);
486 fflush(stderr);
487 #endif
488 return 1;
489 }
490
491 n = timer_count;
492 for (i = 0; i < n; i++) {
493 t = timer_list + i;
494 if (t->id == timer_id) {
495 found = 1;
496
497 /* Shift elements downwards to keep the timer list dense
498 * (no need if last element).
499 */
500 if (i < timer_count - 1) {
501 memmove((void *) t, (void *) (t + 1), (timer_count - i - 1) * sizeof(ev_timer));
502 }
503
504 /* Zero last element for clarity. */
505 memset((void *) (timer_list + n - 1), 0, sizeof(ev_timer));
506
507 /* Update timer_count. */
508 timer_count--;
509
510 /* The C state is now up-to-date, but we still need to delete
511 * the timer callback state from the global 'stash'.
512 */
513
514 duk_push_global_stash(ctx);
515 duk_get_prop_string(ctx, -1, "eventTimers"); /* -> [ timer_id stash eventTimers ] */
516 duk_push_number(ctx, (double) timer_id);
517 duk_del_prop(ctx, -2); /* delete eventTimers[timer_id] */
518
519 #if 0
520 fprintf(stderr, "deleted timer id: %d\n", (int) timer_id);
521 fflush(stderr);
522 #endif
523 break;
524 }
525 }
526
527 #if 0
528 if (!found) {
529 fprintf(stderr, "trying to delete timer id %d, but not found; ignoring\n", (int) timer_id);
530 fflush(stderr);
531 }
532 #endif
533
534 duk_push_boolean(ctx, found);
535 return 1;
536 }
537
listen_fd(duk_context * ctx)538 static int listen_fd(duk_context *ctx) {
539 int fd = duk_require_int(ctx, 0);
540 int events = duk_require_int(ctx, 1);
541 int i, n;
542 struct pollfd *pfd;
543
544 #if 0
545 fprintf(stderr, "listen_fd: fd=%d, events=%d\n", fd, events);
546 fflush(stderr);
547 #endif
548 /* events == 0 means stop listening to the FD */
549
550 n = poll_count;
551 for (i = 0; i < n; i++) {
552 pfd = poll_list + i;
553 if (pfd->fd == fd) {
554 #if 0
555 fprintf(stderr, "listen_fd: fd found at index %d\n", i);
556 fflush(stderr);
557 #endif
558 if (events == 0) {
559 /* mark to-be-deleted, cleaned up by next poll */
560 pfd->fd = 0;
561 } else {
562 pfd->events = events;
563 }
564 return 0;
565 }
566 }
567
568 /* not found, append to list */
569 #if 0
570 fprintf(stderr, "listen_fd: fd not found on list, add new entry\n");
571 fflush(stderr);
572 #endif
573
574 if (poll_count >= MAX_FDS) {
575 duk_error(ctx, DUK_ERR_ERROR, "out of fd slots");
576 }
577
578 pfd = poll_list + poll_count;
579 pfd->fd = fd;
580 pfd->events = events;
581 pfd->revents = 0;
582 poll_count++;
583
584 return 0;
585 }
586
request_exit(duk_context * ctx)587 static int request_exit(duk_context *ctx) {
588 (void) ctx;
589 exit_requested = 1;
590 return 0;
591 }
592
593 static duk_function_list_entry eventloop_funcs[] = {
594 { "createTimer", create_timer, 3 },
595 { "deleteTimer", delete_timer, 1 },
596 { "listenFd", listen_fd, 2 },
597 { "requestExit", request_exit, 0 },
598 { NULL, NULL, 0 }
599 };
600
eventloop_register(duk_context * ctx)601 void eventloop_register(duk_context *ctx) {
602 memset((void *) timer_list, 0, MAX_TIMERS * sizeof(ev_timer));
603 memset((void *) &timer_expiring, 0, sizeof(ev_timer));
604 memset((void *) poll_list, 0, MAX_FDS * sizeof(struct pollfd));
605
606 /* Set global 'EventLoop'. */
607 duk_push_global_object(ctx);
608 duk_push_object(ctx);
609 duk_put_function_list(ctx, -1, eventloop_funcs);
610 duk_put_prop_string(ctx, -2, "EventLoop");
611 duk_pop(ctx);
612
613 /* Initialize global stash 'eventTimers'. */
614 duk_push_global_stash(ctx);
615 duk_push_object(ctx);
616 duk_put_prop_string(ctx, -2, "eventTimers");
617 duk_pop(ctx);
618 }
619