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