1 2 /* 3 * Copyright (C) Igor Sysoev 4 * Copyright (C) NGINX, Inc. 5 */ 6 7 #include <nxt_main.h> 8 9 10 /* 11 * Timer operations are batched in the changes array to improve instruction 12 * and data cache locality of rbtree operations. 13 * 14 * nxt_timer_add() adds or modify a timer. 15 * 16 * nxt_timer_disable() disables a timer. 17 * 18 * nxt_timer_delete() deletes a timer. It returns 1 if there are pending 19 * changes in the changes array or 0 otherwise. 20 */ 21 22 static intptr_t nxt_timer_rbtree_compare(nxt_rbtree_node_t *node1, 23 nxt_rbtree_node_t *node2); 24 static void nxt_timer_change(nxt_event_engine_t *engine, nxt_timer_t *timer, 25 nxt_timer_operation_t change, nxt_msec_t time); 26 static void nxt_timer_changes_commit(nxt_event_engine_t *engine); 27 static void nxt_timer_handler(nxt_task_t *task, void *obj, void *data); 28 29 30 nxt_int_t 31 nxt_timers_init(nxt_timers_t *timers, nxt_uint_t mchanges) 32 { 33 nxt_rbtree_init(&timers->tree, nxt_timer_rbtree_compare); 34 35 if (mchanges > NXT_TIMER_MAX_CHANGES) { 36 mchanges = NXT_TIMER_MAX_CHANGES; 37 } 38 39 timers->mchanges = mchanges; 40 41 timers->changes = nxt_malloc(sizeof(nxt_timer_change_t) * mchanges); 42 43 if (nxt_fast_path(timers->changes != NULL)) { 44 return NXT_OK; 45 } 46 47 return NXT_ERROR; 48 } 49 50 51 static intptr_t 52 nxt_timer_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2) 53 { 54 nxt_timer_t *timer1, *timer2; 55 56 timer1 = (nxt_timer_t *) node1; 57 timer2 = (nxt_timer_t *) node2; 58 59 /* 60 * Timer values are distributed in small range, usually several minutes 61 * and overflow every 49 days if nxt_msec_t is stored in 32 bits. 62 * This signed comparison takes into account that overflow. 63 */ 64 /* timer1->time < timer2->time */ 65 return nxt_msec_diff(timer1->time , timer2->time); 66 } 67 68 69 void 70 nxt_timer_add(nxt_event_engine_t *engine, nxt_timer_t *timer, 71 nxt_msec_t timeout) 72 { 73 int32_t diff; 74 uint32_t time; 75 76 time = engine->timers.now + timeout; 77 78 nxt_debug(timer->task, "timer add: %M %M:%M", timer->time, timeout, time); 79 80 timer->enabled = 1; 81 82 if (nxt_timer_is_in_tree(timer)) { 83 84 diff = nxt_msec_diff(time, timer->time); 85 /* 86 * Use the previous timer if difference between it and the 87 * new timer is less than required precision milliseconds: this 88 * decreases number of rbtree operations for fast connections. 89 */ 90 if (nxt_abs(diff) < timer->precision) { 91 nxt_debug(timer->task, "timer previous: %M", time); 92 93 nxt_timer_change(engine, timer, NXT_TIMER_NOPE, 0); 94 return; 95 } 96 } 97 98 nxt_timer_change(engine, timer, NXT_TIMER_ADD, time); 99 } 100 101 102 nxt_bool_t 103 nxt_timer_delete(nxt_event_engine_t *engine, nxt_timer_t *timer) 104 { 105 nxt_debug(timer->task, "timer delete: %M", timer->time); 106 107 timer->enabled = 0; 108 109 if (nxt_timer_is_in_tree(timer)) { 110 111 nxt_timer_change(engine, timer, NXT_TIMER_DELETE, 0); 112 113 return 1; 114 } 115 116 nxt_timer_change(engine, timer, NXT_TIMER_NOPE, 0); 117 118 return (timer->queued || timer->change != NXT_TIMER_NO_CHANGE); 119 } 120 121 122 static void 123 nxt_timer_change(nxt_event_engine_t *engine, nxt_timer_t *timer, 124 nxt_timer_operation_t change, nxt_msec_t time) 125 { 126 nxt_timers_t *timers; 127 nxt_timer_change_t *ch; 128 129 timers = &engine->timers; 130 131 if (timer->change == NXT_TIMER_NO_CHANGE) { 132 133 if (change == NXT_TIMER_NOPE) { 134 return; 135 } 136 137 if (timers->nchanges >= timers->mchanges) { 138 nxt_timer_changes_commit(engine); 139 } 140 141 timers->nchanges++; 142 timer->change = timers->nchanges; 143 } 144 145 nxt_debug(timer->task, "timer change: %M:%d", time, change); 146 147 ch = &timers->changes[timer->change - 1]; 148 149 ch->change = change; 150 ch->time = time; 151 ch->timer = timer; 152 } 153 154 155 static void 156 nxt_timer_changes_commit(nxt_event_engine_t *engine) 157 { 158 nxt_timer_t *timer, **add, **add_end; 159 nxt_timers_t *timers; 160 nxt_timer_change_t *ch, *end; 161 162 timers = &engine->timers; 163 164 nxt_debug(&engine->task, "timers changes: %ui", timers->nchanges); 165 166 ch = timers->changes; 167 end = ch + timers->nchanges; 168 169 add = (nxt_timer_t **) ch; 170 add_end = add; 171 172 while (ch < end) { 173 timer = ch->timer; 174 175 switch (ch->change) { 176 177 case NXT_TIMER_NOPE: 178 break; 179 180 case NXT_TIMER_ADD: 181 182 timer->time = ch->time; 183 184 *add_end++ = timer; 185 186 if (!nxt_timer_is_in_tree(timer)) { 187 break; 188 } 189 190 /* Fall through. */ 191 192 case NXT_TIMER_DELETE: 193 nxt_debug(timer->task, "timer rbtree delete: %M", timer->time); 194 195 nxt_rbtree_delete(&timers->tree, &timer->node); 196 nxt_timer_in_tree_clear(timer); 197 198 break; 199 } 200 201 timer->change = NXT_TIMER_NO_CHANGE; 202 203 ch++; 204 } 205 206 while (add < add_end) { 207 timer = *add; 208 209 nxt_debug(timer->task, "timer rbtree insert: %M", timer->time); 210 211 nxt_rbtree_insert(&timers->tree, &timer->node); 212 nxt_timer_in_tree_set(timer); 213 214 add++; 215 } 216 217 timers->nchanges = 0; 218 } 219 220 221 nxt_msec_t 222 nxt_timer_find(nxt_event_engine_t *engine) 223 { 224 int32_t delta; 225 nxt_msec_t time; 226 nxt_timer_t *timer; 227 nxt_timers_t *timers; 228 nxt_rbtree_t *tree; 229 nxt_rbtree_node_t *node, *next; 230 231 timers = &engine->timers; 232 233 if (timers->nchanges != 0) { 234 nxt_timer_changes_commit(engine); 235 } 236 237 tree = &timers->tree; 238 239 for (node = nxt_rbtree_min(tree); 240 nxt_rbtree_is_there_successor(tree, node); 241 node = next) 242 { 243 next = nxt_rbtree_node_successor(tree, node); 244 245 timer = (nxt_timer_t *) node; 246 247 /* 248 * Disabled timers are not deleted here since the minimum active 249 * timer may be larger than a disabled timer, but event poll may 250 * return much earlier and the disabled timer can be reactivated. 251 */ 252 253 if (timer->enabled) { 254 time = timer->time; 255 timers->minimum = time; 256 257 nxt_debug(timer->task, "timer found minimum: %M:%M", 258 time, timers->now); 259 260 delta = nxt_msec_diff(time, timers->now); 261 262 return (nxt_msec_t) nxt_max(delta, 0); 263 } 264 } 265 266 /* Set minimum time one day ahead. */ 267 timers->minimum = timers->now + 24 * 60 * 60 * 1000; 268 269 return NXT_INFINITE_MSEC; 270 } 271 272 273 void 274 nxt_timer_expire(nxt_event_engine_t *engine, nxt_msec_t now) 275 { 276 nxt_timer_t *timer; 277 nxt_timers_t *timers; 278 nxt_rbtree_t *tree; 279 nxt_rbtree_node_t *node, *next; 280 281 timers = &engine->timers; 282 timers->now = now; 283 284 nxt_debug(&engine->task, "timer expire minimum: %M:%M", 285 timers->minimum, now); 286 287 /* timers->minimum > now */ 288 if (nxt_msec_diff(timers->minimum , now) > 0) { 289 return; 290 } 291 292 tree = &timers->tree; 293 294 for (node = nxt_rbtree_min(tree); 295 nxt_rbtree_is_there_successor(tree, node); 296 node = next) 297 { 298 timer = (nxt_timer_t *) node; 299 300 /* timer->time > now */ 301 if (nxt_msec_diff(timer->time , now) > 0) { 302 return; 303 } 304 305 next = nxt_rbtree_node_successor(tree, node); 306 307 nxt_debug(timer->task, "timer expire delete: %M", timer->time); 308 309 nxt_rbtree_delete(tree, &timer->node); 310 nxt_timer_in_tree_clear(timer); 311 312 if (timer->enabled) { 313 timer->queued = 1; 314 315 nxt_work_queue_add(timer->work_queue, nxt_timer_handler, 316 timer->task, timer, NULL); 317 } 318 } 319 } 320 321 322 static void 323 nxt_timer_handler(nxt_task_t *task, void *obj, void *data) 324 { 325 nxt_timer_t *timer; 326 327 timer = obj; 328 329 timer->queued = 0; 330 331 if (timer->enabled && timer->change == NXT_TIMER_NO_CHANGE) { 332 timer->enabled = 0; 333 334 timer->handler(task, timer, NULL); 335 } 336 } 337