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