xref: /unit/src/nxt_timer.c (revision 959)
16Sigor@sysoev.ru 
26Sigor@sysoev.ru /*
36Sigor@sysoev.ru  * Copyright (C) Igor Sysoev
46Sigor@sysoev.ru  * Copyright (C) NGINX, Inc.
56Sigor@sysoev.ru  */
66Sigor@sysoev.ru 
76Sigor@sysoev.ru #include <nxt_main.h>
86Sigor@sysoev.ru 
96Sigor@sysoev.ru 
106Sigor@sysoev.ru /*
117Sigor@sysoev.ru  * Timer operations are batched in the changes array to improve instruction
127Sigor@sysoev.ru  * and data cache locality of rbtree operations.
136Sigor@sysoev.ru  *
147Sigor@sysoev.ru  * nxt_timer_add() adds or modify a timer.
156Sigor@sysoev.ru  *
167Sigor@sysoev.ru  * nxt_timer_disable() disables a timer.
176Sigor@sysoev.ru  *
187Sigor@sysoev.ru  * nxt_timer_delete() deletes a timer.  It returns 1 if there are pending
197Sigor@sysoev.ru  * changes in the changes array or 0 otherwise.
206Sigor@sysoev.ru  */
216Sigor@sysoev.ru 
226Sigor@sysoev.ru static intptr_t nxt_timer_rbtree_compare(nxt_rbtree_node_t *node1,
236Sigor@sysoev.ru     nxt_rbtree_node_t *node2);
247Sigor@sysoev.ru static void nxt_timer_change(nxt_event_engine_t *engine, nxt_timer_t *timer,
257Sigor@sysoev.ru     nxt_timer_operation_t change, nxt_msec_t time);
267Sigor@sysoev.ru static void nxt_timer_changes_commit(nxt_event_engine_t *engine);
277Sigor@sysoev.ru static void nxt_timer_handler(nxt_task_t *task, void *obj, void *data);
286Sigor@sysoev.ru 
296Sigor@sysoev.ru 
306Sigor@sysoev.ru nxt_int_t
316Sigor@sysoev.ru nxt_timers_init(nxt_timers_t *timers, nxt_uint_t mchanges)
326Sigor@sysoev.ru {
336Sigor@sysoev.ru     nxt_rbtree_init(&timers->tree, nxt_timer_rbtree_compare);
346Sigor@sysoev.ru 
35809Svbart@nginx.com     if (mchanges > NXT_TIMER_MAX_CHANGES) {
36809Svbart@nginx.com         mchanges = NXT_TIMER_MAX_CHANGES;
37809Svbart@nginx.com     }
38809Svbart@nginx.com 
396Sigor@sysoev.ru     timers->mchanges = mchanges;
406Sigor@sysoev.ru 
416Sigor@sysoev.ru     timers->changes = nxt_malloc(sizeof(nxt_timer_change_t) * mchanges);
426Sigor@sysoev.ru 
436Sigor@sysoev.ru     if (nxt_fast_path(timers->changes != NULL)) {
446Sigor@sysoev.ru         return NXT_OK;
456Sigor@sysoev.ru     }
466Sigor@sysoev.ru 
476Sigor@sysoev.ru     return NXT_ERROR;
486Sigor@sysoev.ru }
496Sigor@sysoev.ru 
506Sigor@sysoev.ru 
516Sigor@sysoev.ru static intptr_t
526Sigor@sysoev.ru nxt_timer_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2)
536Sigor@sysoev.ru {
546Sigor@sysoev.ru     nxt_timer_t  *timer1, *timer2;
556Sigor@sysoev.ru 
566Sigor@sysoev.ru     timer1 = (nxt_timer_t *) node1;
576Sigor@sysoev.ru     timer2 = (nxt_timer_t *) node2;
586Sigor@sysoev.ru 
596Sigor@sysoev.ru     /*
606Sigor@sysoev.ru      * Timer values are distributed in small range, usually several minutes
616Sigor@sysoev.ru      * and overflow every 49 days if nxt_msec_t is stored in 32 bits.
626Sigor@sysoev.ru      * This signed comparison takes into account that overflow.
636Sigor@sysoev.ru      */
646Sigor@sysoev.ru                       /* timer1->time < timer2->time */
657Sigor@sysoev.ru     return nxt_msec_diff(timer1->time , timer2->time);
666Sigor@sysoev.ru }
676Sigor@sysoev.ru 
686Sigor@sysoev.ru 
696Sigor@sysoev.ru void
706Sigor@sysoev.ru nxt_timer_add(nxt_event_engine_t *engine, nxt_timer_t *timer,
716Sigor@sysoev.ru     nxt_msec_t timeout)
726Sigor@sysoev.ru {
736Sigor@sysoev.ru     int32_t   diff;
746Sigor@sysoev.ru     uint32_t  time;
756Sigor@sysoev.ru 
766Sigor@sysoev.ru     time = engine->timers.now + timeout;
776Sigor@sysoev.ru 
78811Svbart@nginx.com     nxt_debug(timer->task, "timer add: %M±%d %M:%M",
79811Svbart@nginx.com               timer->time, timer->bias, timeout, time);
806Sigor@sysoev.ru 
81809Svbart@nginx.com     timer->enabled = 1;
82809Svbart@nginx.com 
83809Svbart@nginx.com     if (nxt_timer_is_in_tree(timer)) {
846Sigor@sysoev.ru 
85809Svbart@nginx.com         diff = nxt_msec_diff(time, timer->time);
86809Svbart@nginx.com         /*
87809Svbart@nginx.com          * Use the previous timer if difference between it and the
88811Svbart@nginx.com          * new timer is within bias: this decreases number of rbtree
89811Svbart@nginx.com          * operations for fast connections.
90809Svbart@nginx.com          */
91811Svbart@nginx.com         if (nxt_abs(diff) <= timer->bias) {
92811Svbart@nginx.com             nxt_debug(timer->task, "timer previous: %M±%d",
93811Svbart@nginx.com                       time, timer->bias);
946Sigor@sysoev.ru 
95809Svbart@nginx.com             nxt_timer_change(engine, timer, NXT_TIMER_NOPE, 0);
96809Svbart@nginx.com             return;
977Sigor@sysoev.ru         }
987Sigor@sysoev.ru     }
996Sigor@sysoev.ru 
1007Sigor@sysoev.ru     nxt_timer_change(engine, timer, NXT_TIMER_ADD, time);
1017Sigor@sysoev.ru }
1027Sigor@sysoev.ru 
1036Sigor@sysoev.ru 
1047Sigor@sysoev.ru nxt_bool_t
1057Sigor@sysoev.ru nxt_timer_delete(nxt_event_engine_t *engine, nxt_timer_t *timer)
1067Sigor@sysoev.ru {
107811Svbart@nginx.com     nxt_debug(timer->task, "timer delete: %M±%d",
108811Svbart@nginx.com               timer->time, timer->bias);
1097Sigor@sysoev.ru 
110809Svbart@nginx.com     timer->enabled = 0;
111809Svbart@nginx.com 
112809Svbart@nginx.com     if (nxt_timer_is_in_tree(timer)) {
1137Sigor@sysoev.ru 
1147Sigor@sysoev.ru         nxt_timer_change(engine, timer, NXT_TIMER_DELETE, 0);
1157Sigor@sysoev.ru 
1167Sigor@sysoev.ru         return 1;
1176Sigor@sysoev.ru     }
1186Sigor@sysoev.ru 
119809Svbart@nginx.com     nxt_timer_change(engine, timer, NXT_TIMER_NOPE, 0);
1207Sigor@sysoev.ru 
121809Svbart@nginx.com     return (timer->queued || timer->change != NXT_TIMER_NO_CHANGE);
1226Sigor@sysoev.ru }
1236Sigor@sysoev.ru 
1246Sigor@sysoev.ru 
1256Sigor@sysoev.ru static void
1267Sigor@sysoev.ru nxt_timer_change(nxt_event_engine_t *engine, nxt_timer_t *timer,
1277Sigor@sysoev.ru     nxt_timer_operation_t change, nxt_msec_t time)
1286Sigor@sysoev.ru {
1297Sigor@sysoev.ru     nxt_timers_t        *timers;
1306Sigor@sysoev.ru     nxt_timer_change_t  *ch;
1316Sigor@sysoev.ru 
1327Sigor@sysoev.ru     timers = &engine->timers;
1337Sigor@sysoev.ru 
134809Svbart@nginx.com     if (timer->change == NXT_TIMER_NO_CHANGE) {
135809Svbart@nginx.com 
136809Svbart@nginx.com         if (change == NXT_TIMER_NOPE) {
137809Svbart@nginx.com             return;
138809Svbart@nginx.com         }
139809Svbart@nginx.com 
140809Svbart@nginx.com         if (timers->nchanges >= timers->mchanges) {
141809Svbart@nginx.com             nxt_timer_changes_commit(engine);
142809Svbart@nginx.com         }
143809Svbart@nginx.com 
144809Svbart@nginx.com         timers->nchanges++;
145809Svbart@nginx.com         timer->change = timers->nchanges;
1466Sigor@sysoev.ru     }
1476Sigor@sysoev.ru 
148811Svbart@nginx.com     nxt_debug(timer->task, "timer change: %M±%d:%d",
149811Svbart@nginx.com               time, timer->bias, change);
1507Sigor@sysoev.ru 
151809Svbart@nginx.com     ch = &timers->changes[timer->change - 1];
1527Sigor@sysoev.ru 
1537Sigor@sysoev.ru     ch->change = change;
1546Sigor@sysoev.ru     ch->time = time;
1556Sigor@sysoev.ru     ch->timer = timer;
1566Sigor@sysoev.ru }
1576Sigor@sysoev.ru 
1586Sigor@sysoev.ru 
1597Sigor@sysoev.ru static void
1607Sigor@sysoev.ru nxt_timer_changes_commit(nxt_event_engine_t *engine)
1616Sigor@sysoev.ru {
162*959Svbart@nginx.com     nxt_timer_t         *timer;
1637Sigor@sysoev.ru     nxt_timers_t        *timers;
164*959Svbart@nginx.com     nxt_timer_change_t  *ch, *end, *add, *add_end;
1656Sigor@sysoev.ru 
1667Sigor@sysoev.ru     timers = &engine->timers;
1677Sigor@sysoev.ru 
1687Sigor@sysoev.ru     nxt_debug(&engine->task, "timers changes: %ui", timers->nchanges);
1696Sigor@sysoev.ru 
1706Sigor@sysoev.ru     ch = timers->changes;
1716Sigor@sysoev.ru     end = ch + timers->nchanges;
1726Sigor@sysoev.ru 
173*959Svbart@nginx.com     add = ch;
174810Svbart@nginx.com     add_end = add;
175810Svbart@nginx.com 
1766Sigor@sysoev.ru     while (ch < end) {
1776Sigor@sysoev.ru         timer = ch->timer;
1786Sigor@sysoev.ru 
1797Sigor@sysoev.ru         switch (ch->change) {
1806Sigor@sysoev.ru 
181809Svbart@nginx.com         case NXT_TIMER_NOPE:
182809Svbart@nginx.com             break;
183809Svbart@nginx.com 
1847Sigor@sysoev.ru         case NXT_TIMER_ADD:
1856Sigor@sysoev.ru 
1867Sigor@sysoev.ru             timer->time = ch->time;
1877Sigor@sysoev.ru 
188*959Svbart@nginx.com             add_end->timer = timer;
189*959Svbart@nginx.com             add_end++;
1906Sigor@sysoev.ru 
191810Svbart@nginx.com             if (!nxt_timer_is_in_tree(timer)) {
192810Svbart@nginx.com                 break;
193810Svbart@nginx.com             }
1947Sigor@sysoev.ru 
195810Svbart@nginx.com             /* Fall through. */
1967Sigor@sysoev.ru 
1977Sigor@sysoev.ru         case NXT_TIMER_DELETE:
198811Svbart@nginx.com             nxt_debug(timer->task, "timer rbtree delete: %M±%d",
199811Svbart@nginx.com                       timer->time, timer->bias);
2007Sigor@sysoev.ru 
201809Svbart@nginx.com             nxt_rbtree_delete(&timers->tree, &timer->node);
202809Svbart@nginx.com             nxt_timer_in_tree_clear(timer);
2037Sigor@sysoev.ru 
2047Sigor@sysoev.ru             break;
2056Sigor@sysoev.ru         }
2066Sigor@sysoev.ru 
207809Svbart@nginx.com         timer->change = NXT_TIMER_NO_CHANGE;
2087Sigor@sysoev.ru 
2096Sigor@sysoev.ru         ch++;
2106Sigor@sysoev.ru     }
2116Sigor@sysoev.ru 
212810Svbart@nginx.com     while (add < add_end) {
213*959Svbart@nginx.com         timer = add->timer;
214810Svbart@nginx.com 
215811Svbart@nginx.com         nxt_debug(timer->task, "timer rbtree insert: %M±%d",
216811Svbart@nginx.com                   timer->time, timer->bias);
217810Svbart@nginx.com 
218810Svbart@nginx.com         nxt_rbtree_insert(&timers->tree, &timer->node);
219810Svbart@nginx.com         nxt_timer_in_tree_set(timer);
220810Svbart@nginx.com 
221810Svbart@nginx.com         add++;
222810Svbart@nginx.com     }
223810Svbart@nginx.com 
2246Sigor@sysoev.ru     timers->nchanges = 0;
2256Sigor@sysoev.ru }
2266Sigor@sysoev.ru 
2276Sigor@sysoev.ru 
2286Sigor@sysoev.ru nxt_msec_t
2296Sigor@sysoev.ru nxt_timer_find(nxt_event_engine_t *engine)
2306Sigor@sysoev.ru {
231590Sigor@sysoev.ru     int32_t            delta;
232590Sigor@sysoev.ru     nxt_msec_t         time;
2336Sigor@sysoev.ru     nxt_timer_t        *timer;
2347Sigor@sysoev.ru     nxt_timers_t       *timers;
2357Sigor@sysoev.ru     nxt_rbtree_t       *tree;
2366Sigor@sysoev.ru     nxt_rbtree_node_t  *node, *next;
2376Sigor@sysoev.ru 
2387Sigor@sysoev.ru     timers = &engine->timers;
2397Sigor@sysoev.ru 
2407Sigor@sysoev.ru     if (timers->nchanges != 0) {
2417Sigor@sysoev.ru         nxt_timer_changes_commit(engine);
2426Sigor@sysoev.ru     }
2436Sigor@sysoev.ru 
2447Sigor@sysoev.ru     tree = &timers->tree;
2457Sigor@sysoev.ru 
2467Sigor@sysoev.ru     for (node = nxt_rbtree_min(tree);
2477Sigor@sysoev.ru          nxt_rbtree_is_there_successor(tree, node);
2486Sigor@sysoev.ru          node = next)
2496Sigor@sysoev.ru     {
2507Sigor@sysoev.ru         next = nxt_rbtree_node_successor(tree, node);
2516Sigor@sysoev.ru 
2526Sigor@sysoev.ru         timer = (nxt_timer_t *) node;
2536Sigor@sysoev.ru 
2547Sigor@sysoev.ru         /*
2557Sigor@sysoev.ru          * Disabled timers are not deleted here since the minimum active
2567Sigor@sysoev.ru          * timer may be larger than a disabled timer, but event poll may
2577Sigor@sysoev.ru          * return much earlier and the disabled timer can be reactivated.
2587Sigor@sysoev.ru          */
2596Sigor@sysoev.ru 
260809Svbart@nginx.com         if (timer->enabled) {
2617Sigor@sysoev.ru             time = timer->time;
262811Svbart@nginx.com             timers->minimum = time - timer->bias;
2636Sigor@sysoev.ru 
264811Svbart@nginx.com             nxt_debug(timer->task, "timer found minimum: %M±%d:%M",
265811Svbart@nginx.com                       time, timer->bias, timers->now);
2667Sigor@sysoev.ru 
267590Sigor@sysoev.ru             delta = nxt_msec_diff(time, timers->now);
2686Sigor@sysoev.ru 
269590Sigor@sysoev.ru             return (nxt_msec_t) nxt_max(delta, 0);
2706Sigor@sysoev.ru         }
2717Sigor@sysoev.ru     }
2726Sigor@sysoev.ru 
2737Sigor@sysoev.ru     /* Set minimum time one day ahead. */
2747Sigor@sysoev.ru     timers->minimum = timers->now + 24 * 60 * 60 * 1000;
2756Sigor@sysoev.ru 
2766Sigor@sysoev.ru     return NXT_INFINITE_MSEC;
2776Sigor@sysoev.ru }
2786Sigor@sysoev.ru 
2796Sigor@sysoev.ru 
2806Sigor@sysoev.ru void
2817Sigor@sysoev.ru nxt_timer_expire(nxt_event_engine_t *engine, nxt_msec_t now)
2826Sigor@sysoev.ru {
2836Sigor@sysoev.ru     nxt_timer_t        *timer;
2847Sigor@sysoev.ru     nxt_timers_t       *timers;
2856Sigor@sysoev.ru     nxt_rbtree_t       *tree;
2866Sigor@sysoev.ru     nxt_rbtree_node_t  *node, *next;
2876Sigor@sysoev.ru 
2887Sigor@sysoev.ru     timers = &engine->timers;
2897Sigor@sysoev.ru     timers->now = now;
2907Sigor@sysoev.ru 
2917Sigor@sysoev.ru     nxt_debug(&engine->task, "timer expire minimum: %M:%M",
2927Sigor@sysoev.ru               timers->minimum, now);
2937Sigor@sysoev.ru 
2947Sigor@sysoev.ru                    /* timers->minimum > now */
2957Sigor@sysoev.ru     if (nxt_msec_diff(timers->minimum , now) > 0) {
2967Sigor@sysoev.ru         return;
2977Sigor@sysoev.ru     }
2987Sigor@sysoev.ru 
2997Sigor@sysoev.ru     tree = &timers->tree;
3006Sigor@sysoev.ru 
3016Sigor@sysoev.ru     for (node = nxt_rbtree_min(tree);
3026Sigor@sysoev.ru          nxt_rbtree_is_there_successor(tree, node);
3036Sigor@sysoev.ru          node = next)
3046Sigor@sysoev.ru     {
3056Sigor@sysoev.ru         timer = (nxt_timer_t *) node;
3066Sigor@sysoev.ru 
307811Svbart@nginx.com                        /* timer->time > now + timer->bias */
308811Svbart@nginx.com         if (nxt_msec_diff(timer->time , now) > (int32_t) timer->bias) {
3096Sigor@sysoev.ru             return;
3106Sigor@sysoev.ru         }
3116Sigor@sysoev.ru 
3126Sigor@sysoev.ru         next = nxt_rbtree_node_successor(tree, node);
3136Sigor@sysoev.ru 
314811Svbart@nginx.com         nxt_debug(timer->task, "timer expire delete: %M±%d",
315811Svbart@nginx.com                   timer->time, timer->bias);
3166Sigor@sysoev.ru 
3176Sigor@sysoev.ru         nxt_rbtree_delete(tree, &timer->node);
3186Sigor@sysoev.ru         nxt_timer_in_tree_clear(timer);
3196Sigor@sysoev.ru 
320809Svbart@nginx.com         if (timer->enabled) {
321809Svbart@nginx.com             timer->queued = 1;
3226Sigor@sysoev.ru 
3237Sigor@sysoev.ru             nxt_work_queue_add(timer->work_queue, nxt_timer_handler,
3247Sigor@sysoev.ru                                timer->task, timer, NULL);
3256Sigor@sysoev.ru         }
3266Sigor@sysoev.ru     }
3276Sigor@sysoev.ru }
3287Sigor@sysoev.ru 
3297Sigor@sysoev.ru 
3307Sigor@sysoev.ru static void
3317Sigor@sysoev.ru nxt_timer_handler(nxt_task_t *task, void *obj, void *data)
3327Sigor@sysoev.ru {
3337Sigor@sysoev.ru     nxt_timer_t  *timer;
3347Sigor@sysoev.ru 
3357Sigor@sysoev.ru     timer = obj;
3367Sigor@sysoev.ru 
337809Svbart@nginx.com     timer->queued = 0;
338809Svbart@nginx.com 
339809Svbart@nginx.com     if (timer->enabled && timer->change == NXT_TIMER_NO_CHANGE) {
340809Svbart@nginx.com         timer->enabled = 0;
3417Sigor@sysoev.ru 
3427Sigor@sysoev.ru         timer->handler(task, timer, NULL);
3437Sigor@sysoev.ru     }
3447Sigor@sysoev.ru }
345