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
nxt_timers_init(nxt_timers_t * timers,nxt_uint_t mchanges)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
nxt_timer_rbtree_compare(nxt_rbtree_node_t * node1,nxt_rbtree_node_t * node2)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
nxt_timer_add(nxt_event_engine_t * engine,nxt_timer_t * timer,nxt_msec_t timeout)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
nxt_timer_delete(nxt_event_engine_t * engine,nxt_timer_t * timer)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
nxt_timer_change(nxt_event_engine_t * engine,nxt_timer_t * timer,nxt_timer_operation_t change,nxt_msec_t time)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
nxt_timer_changes_commit(nxt_event_engine_t * engine)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
nxt_timer_find(nxt_event_engine_t * engine)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
nxt_timer_expire(nxt_event_engine_t * engine,nxt_msec_t now)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
nxt_timer_handler(nxt_task_t * task,void * obj,void * data)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