xref: /unit/src/nxt_timer.c (revision 6:6b3ce47b7663)
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