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 to improve instruction and data 12 * cache locality of rbtree operations. 13 * 14 * nxt_timer_add() adds a timer to the changes array to add or to 15 * modify the timer. The changes are processed by nxt_timer_find(). 16 * 17 * nxt_timer_disable() disables a timer. The disabled timer may 18 * however present in rbtree for a long time and may be eventually removed 19 * by nxt_timer_find() or nxt_timer_expire(). 20 * 21 * nxt_timer_delete() removes a timer at once from both the rbtree and 22 * the changes array and should be used only if the timer memory must be freed. 23 */ 24 25 static intptr_t nxt_timer_rbtree_compare(nxt_rbtree_node_t *node1, 26 nxt_rbtree_node_t *node2); 27 static void nxt_timer_change(nxt_timers_t *timers, nxt_timer_t *timer, 28 nxt_msec_t time); 29 static void nxt_commit_timer_changes(nxt_timers_t *timers); 30 static void nxt_timer_drop_changes(nxt_timers_t *timers, nxt_timer_t *timer); 31 32 33 nxt_int_t 34 nxt_timers_init(nxt_timers_t *timers, nxt_uint_t mchanges) 35 { 36 nxt_rbtree_init(&timers->tree, nxt_timer_rbtree_compare); 37 38 timers->mchanges = mchanges; 39 40 timers->changes = nxt_malloc(sizeof(nxt_timer_change_t) * mchanges); 41 42 if (nxt_fast_path(timers->changes != NULL)) { 43 return NXT_OK; 44 } 45 46 return NXT_ERROR; 47 } 48 49 50 static intptr_t 51 nxt_timer_rbtree_compare(nxt_rbtree_node_t *node1, nxt_rbtree_node_t *node2) 52 { 53 nxt_timer_t *timer1, *timer2; 54 55 timer1 = (nxt_timer_t *) node1; 56 timer2 = (nxt_timer_t *) node2; 57 58 /* 59 * Timer values are distributed in small range, usually several minutes 60 * and overflow every 49 days if nxt_msec_t is stored in 32 bits. 61 * This signed comparison takes into account that overflow. 62 */ 63 /* timer1->time < timer2->time */ 64 return nxt_msec_diff(timer1->time, timer2->time); 65 } 66 67 68 void 69 nxt_timer_add(nxt_event_engine_t *engine, nxt_timer_t *timer, 70 nxt_msec_t timeout) 71 { 72 int32_t diff; 73 uint32_t time; 74 75 time = engine->timers.now + timeout; 76 77 if (nxt_timer_is_in_tree(timer)) { 78 79 diff = nxt_msec_diff(time, timer->time); 80 81 /* 82 * Use the previous timer if difference between it and the 83 * new timer is less than required precision milliseconds: 84 * this decreases rbtree operations for fast connections. 85 */ 86 87 if (nxt_abs(diff) < timer->precision) { 88 nxt_log_debug(timer->log, "timer previous: %D: %d:%M", 89 timer->ident, timer->state, time); 90 91 if (timer->state == NXT_TIMER_DISABLED) { 92 timer->state = NXT_TIMER_ACTIVE; 93 } 94 95 return; 96 } 97 98 nxt_log_debug(timer->log, "timer change: %D: %d:%M", 99 timer->ident, timer->state, timer->time); 100 101 } else { 102 /* 103 * The timer's time is updated here just to log a correct 104 * value by debug logging in nxt_timer_disable(). 105 * It could be updated only in nxt_commit_timer_changes() 106 * just before nxt_rbtree_insert(). 107 */ 108 timer->time = time; 109 110 nxt_log_debug(timer->log, "timer add: %D: %M:%M", 111 timer->ident, timeout, time); 112 } 113 114 nxt_timer_change(&engine->timers, timer, time); 115 } 116 117 118 static void 119 nxt_timer_change(nxt_timers_t *timers, nxt_timer_t *timer, nxt_msec_t time) 120 { 121 nxt_timer_change_t *ch; 122 123 if (timers->nchanges >= timers->mchanges) { 124 nxt_commit_timer_changes(timers); 125 } 126 127 timer->state = NXT_TIMER_ACTIVE; 128 129 ch = &timers->changes[timers->nchanges]; 130 ch->time = time; 131 ch->timer = timer; 132 timers->nchanges++; 133 } 134 135 136 #if (NXT_DEBUG) 137 138 void 139 nxt_timer_disable(nxt_timer_t *timer) 140 { 141 nxt_debug(timer->task, "timer disable: %D: %d:%M", 142 timer->ident, timer->state, timer->time); 143 144 timer->state = NXT_TIMER_DISABLED; 145 } 146 147 #endif 148 149 150 void 151 nxt_timer_delete(nxt_event_engine_t *engine, nxt_timer_t *timer) 152 { 153 if (nxt_timer_is_in_tree(timer)) { 154 nxt_log_debug(timer->log, "timer delete: %D: %d:%M", 155 timer->ident, timer->state, timer->time); 156 157 nxt_rbtree_delete(&engine->timers.tree, &timer->node); 158 nxt_timer_in_tree_clear(timer); 159 timer->state = NXT_TIMER_DISABLED; 160 } 161 162 nxt_timer_drop_changes(&engine->timers, timer); 163 } 164 165 166 static void 167 nxt_timer_drop_changes(nxt_timers_t *timers, nxt_timer_t *timer) 168 { 169 nxt_timer_change_t *dst, *src, *end; 170 171 dst = timers->changes; 172 end = dst + timers->nchanges; 173 174 for (src = dst; src < end; src++) { 175 176 if (src->timer == timer) { 177 continue; 178 } 179 180 if (dst != src) { 181 *dst = *src; 182 } 183 184 dst++; 185 } 186 187 timers->nchanges -= end - dst; 188 } 189 190 191 static void 192 nxt_commit_timer_changes(nxt_timers_t *timers) 193 { 194 nxt_timer_t *timer; 195 nxt_timer_change_t *ch, *end; 196 197 nxt_thread_log_debug("timers changes: %ui", timers->nchanges); 198 199 ch = timers->changes; 200 end = ch + timers->nchanges; 201 202 while (ch < end) { 203 timer = ch->timer; 204 205 if (timer->state != NXT_TIMER_DISABLED) { 206 207 if (nxt_timer_is_in_tree(timer)) { 208 nxt_log_debug(timer->log, "timer delete: %D: %d:%M", 209 timer->ident, timer->state, timer->time); 210 211 nxt_rbtree_delete(&timers->tree, &timer->node); 212 213 timer->time = ch->time; 214 } 215 216 nxt_log_debug(timer->log, "timer add: %D: %M", 217 timer->ident, timer->time); 218 219 nxt_rbtree_insert(&timers->tree, &timer->node); 220 nxt_timer_in_tree_set(timer); 221 } 222 223 ch++; 224 } 225 226 timers->nchanges = 0; 227 } 228 229 230 nxt_msec_t 231 nxt_timer_find(nxt_event_engine_t *engine) 232 { 233 int32_t time; 234 nxt_timer_t *timer; 235 nxt_rbtree_node_t *node, *next; 236 237 if (engine->timers.nchanges != 0) { 238 nxt_commit_timer_changes(&engine->timers); 239 } 240 241 for (node = nxt_rbtree_min(&engine->timers.tree); 242 nxt_rbtree_is_there_successor(&engine->timers.tree, node); 243 node = next) 244 { 245 next = nxt_rbtree_node_successor(&engine->timers.tree, node); 246 247 timer = (nxt_timer_t *) node; 248 249 if (timer->state != NXT_TIMER_DISABLED) { 250 251 if (timer->state == NXT_TIMER_BLOCKED) { 252 nxt_log_debug(timer->log, "timer blocked: %D: %M", 253 timer->ident, timer->time); 254 continue; 255 } 256 257 time = nxt_msec_diff(timer->time, engine->timers.now); 258 259 return (nxt_msec_t) nxt_max(time, 0); 260 } 261 262 /* Delete disabled timer. */ 263 264 nxt_log_debug(timer->log, "timer delete: %D: 0:%M", 265 timer->ident, timer->time); 266 267 nxt_rbtree_delete(&engine->timers.tree, &timer->node); 268 nxt_timer_in_tree_clear(timer); 269 } 270 271 return NXT_INFINITE_MSEC; 272 } 273 274 275 void 276 nxt_timer_expire(nxt_thread_t *thr, nxt_msec_t now) 277 { 278 nxt_timer_t *timer; 279 nxt_rbtree_t *tree; 280 nxt_rbtree_node_t *node, *next; 281 282 thr->engine->timers.now = now; 283 tree = &thr->engine->timers.tree; 284 285 for (node = nxt_rbtree_min(tree); 286 nxt_rbtree_is_there_successor(tree, node); 287 node = next) 288 { 289 timer = (nxt_timer_t *) node; 290 291 /* timer->time > now */ 292 if (nxt_msec_diff(timer->time, now) > 0) { 293 return; 294 } 295 296 next = nxt_rbtree_node_successor(tree, node); 297 298 if (timer->state == NXT_TIMER_BLOCKED) { 299 nxt_log_debug(timer->log, "timer blocked: %D: %M", 300 timer->ident, timer->time); 301 continue; 302 } 303 304 nxt_log_debug(timer->log, "timer delete: %D: %d:%M", 305 timer->ident, timer->state, timer->time); 306 307 nxt_rbtree_delete(tree, &timer->node); 308 nxt_timer_in_tree_clear(timer); 309 310 if (timer->state != NXT_TIMER_DISABLED) { 311 timer->state = NXT_TIMER_DISABLED; 312 313 nxt_work_queue_add(timer->work_queue, timer->handler, timer->task, 314 timer, NULL); 315 } 316 } 317 } 318