xref: /unit/src/nxt_timer.c (revision 959:159b672b12ce)
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
nxt_timers_init(nxt_timers_t * timers,nxt_uint_t mchanges)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
nxt_timer_rbtree_compare(nxt_rbtree_node_t * node1,nxt_rbtree_node_t * node2)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
nxt_timer_add(nxt_event_engine_t * engine,nxt_timer_t * timer,nxt_msec_t timeout)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±%d %M:%M",
79               timer->time, timer->bias, timeout, time);
80 
81     timer->enabled = 1;
82 
83     if (nxt_timer_is_in_tree(timer)) {
84 
85         diff = nxt_msec_diff(time, timer->time);
86         /*
87          * Use the previous timer if difference between it and the
88          * new timer is within bias: this decreases number of rbtree
89          * operations for fast connections.
90          */
91         if (nxt_abs(diff) <= timer->bias) {
92             nxt_debug(timer->task, "timer previous: %M±%d",
93                       time, timer->bias);
94 
95             nxt_timer_change(engine, timer, NXT_TIMER_NOPE, 0);
96             return;
97         }
98     }
99 
100     nxt_timer_change(engine, timer, NXT_TIMER_ADD, time);
101 }
102 
103 
104 nxt_bool_t
nxt_timer_delete(nxt_event_engine_t * engine,nxt_timer_t * timer)105 nxt_timer_delete(nxt_event_engine_t *engine, nxt_timer_t *timer)
106 {
107     nxt_debug(timer->task, "timer delete: %M±%d",
108               timer->time, timer->bias);
109 
110     timer->enabled = 0;
111 
112     if (nxt_timer_is_in_tree(timer)) {
113 
114         nxt_timer_change(engine, timer, NXT_TIMER_DELETE, 0);
115 
116         return 1;
117     }
118 
119     nxt_timer_change(engine, timer, NXT_TIMER_NOPE, 0);
120 
121     return (timer->queued || timer->change != NXT_TIMER_NO_CHANGE);
122 }
123 
124 
125 static void
nxt_timer_change(nxt_event_engine_t * engine,nxt_timer_t * timer,nxt_timer_operation_t change,nxt_msec_t time)126 nxt_timer_change(nxt_event_engine_t *engine, nxt_timer_t *timer,
127     nxt_timer_operation_t change, nxt_msec_t time)
128 {
129     nxt_timers_t        *timers;
130     nxt_timer_change_t  *ch;
131 
132     timers = &engine->timers;
133 
134     if (timer->change == NXT_TIMER_NO_CHANGE) {
135 
136         if (change == NXT_TIMER_NOPE) {
137             return;
138         }
139 
140         if (timers->nchanges >= timers->mchanges) {
141             nxt_timer_changes_commit(engine);
142         }
143 
144         timers->nchanges++;
145         timer->change = timers->nchanges;
146     }
147 
148     nxt_debug(timer->task, "timer change: %M±%d:%d",
149               time, timer->bias, change);
150 
151     ch = &timers->changes[timer->change - 1];
152 
153     ch->change = change;
154     ch->time = time;
155     ch->timer = timer;
156 }
157 
158 
159 static void
nxt_timer_changes_commit(nxt_event_engine_t * engine)160 nxt_timer_changes_commit(nxt_event_engine_t *engine)
161 {
162     nxt_timer_t         *timer;
163     nxt_timers_t        *timers;
164     nxt_timer_change_t  *ch, *end, *add, *add_end;
165 
166     timers = &engine->timers;
167 
168     nxt_debug(&engine->task, "timers changes: %ui", timers->nchanges);
169 
170     ch = timers->changes;
171     end = ch + timers->nchanges;
172 
173     add = ch;
174     add_end = add;
175 
176     while (ch < end) {
177         timer = ch->timer;
178 
179         switch (ch->change) {
180 
181         case NXT_TIMER_NOPE:
182             break;
183 
184         case NXT_TIMER_ADD:
185 
186             timer->time = ch->time;
187 
188             add_end->timer = timer;
189             add_end++;
190 
191             if (!nxt_timer_is_in_tree(timer)) {
192                 break;
193             }
194 
195             /* Fall through. */
196 
197         case NXT_TIMER_DELETE:
198             nxt_debug(timer->task, "timer rbtree delete: %M±%d",
199                       timer->time, timer->bias);
200 
201             nxt_rbtree_delete(&timers->tree, &timer->node);
202             nxt_timer_in_tree_clear(timer);
203 
204             break;
205         }
206 
207         timer->change = NXT_TIMER_NO_CHANGE;
208 
209         ch++;
210     }
211 
212     while (add < add_end) {
213         timer = add->timer;
214 
215         nxt_debug(timer->task, "timer rbtree insert: %M±%d",
216                   timer->time, timer->bias);
217 
218         nxt_rbtree_insert(&timers->tree, &timer->node);
219         nxt_timer_in_tree_set(timer);
220 
221         add++;
222     }
223 
224     timers->nchanges = 0;
225 }
226 
227 
228 nxt_msec_t
nxt_timer_find(nxt_event_engine_t * engine)229 nxt_timer_find(nxt_event_engine_t *engine)
230 {
231     int32_t            delta;
232     nxt_msec_t         time;
233     nxt_timer_t        *timer;
234     nxt_timers_t       *timers;
235     nxt_rbtree_t       *tree;
236     nxt_rbtree_node_t  *node, *next;
237 
238     timers = &engine->timers;
239 
240     if (timers->nchanges != 0) {
241         nxt_timer_changes_commit(engine);
242     }
243 
244     tree = &timers->tree;
245 
246     for (node = nxt_rbtree_min(tree);
247          nxt_rbtree_is_there_successor(tree, node);
248          node = next)
249     {
250         next = nxt_rbtree_node_successor(tree, node);
251 
252         timer = (nxt_timer_t *) node;
253 
254         /*
255          * Disabled timers are not deleted here since the minimum active
256          * timer may be larger than a disabled timer, but event poll may
257          * return much earlier and the disabled timer can be reactivated.
258          */
259 
260         if (timer->enabled) {
261             time = timer->time;
262             timers->minimum = time - timer->bias;
263 
264             nxt_debug(timer->task, "timer found minimum: %M±%d:%M",
265                       time, timer->bias, timers->now);
266 
267             delta = nxt_msec_diff(time, timers->now);
268 
269             return (nxt_msec_t) nxt_max(delta, 0);
270         }
271     }
272 
273     /* Set minimum time one day ahead. */
274     timers->minimum = timers->now + 24 * 60 * 60 * 1000;
275 
276     return NXT_INFINITE_MSEC;
277 }
278 
279 
280 void
nxt_timer_expire(nxt_event_engine_t * engine,nxt_msec_t now)281 nxt_timer_expire(nxt_event_engine_t *engine, nxt_msec_t now)
282 {
283     nxt_timer_t        *timer;
284     nxt_timers_t       *timers;
285     nxt_rbtree_t       *tree;
286     nxt_rbtree_node_t  *node, *next;
287 
288     timers = &engine->timers;
289     timers->now = now;
290 
291     nxt_debug(&engine->task, "timer expire minimum: %M:%M",
292               timers->minimum, now);
293 
294                    /* timers->minimum > now */
295     if (nxt_msec_diff(timers->minimum , now) > 0) {
296         return;
297     }
298 
299     tree = &timers->tree;
300 
301     for (node = nxt_rbtree_min(tree);
302          nxt_rbtree_is_there_successor(tree, node);
303          node = next)
304     {
305         timer = (nxt_timer_t *) node;
306 
307                        /* timer->time > now + timer->bias */
308         if (nxt_msec_diff(timer->time , now) > (int32_t) timer->bias) {
309             return;
310         }
311 
312         next = nxt_rbtree_node_successor(tree, node);
313 
314         nxt_debug(timer->task, "timer expire delete: %M±%d",
315                   timer->time, timer->bias);
316 
317         nxt_rbtree_delete(tree, &timer->node);
318         nxt_timer_in_tree_clear(timer);
319 
320         if (timer->enabled) {
321             timer->queued = 1;
322 
323             nxt_work_queue_add(timer->work_queue, nxt_timer_handler,
324                                timer->task, timer, NULL);
325         }
326     }
327 }
328 
329 
330 static void
nxt_timer_handler(nxt_task_t * task,void * obj,void * data)331 nxt_timer_handler(nxt_task_t *task, void *obj, void *data)
332 {
333     nxt_timer_t  *timer;
334 
335     timer = obj;
336 
337     timer->queued = 0;
338 
339     if (timer->enabled && timer->change == NXT_TIMER_NO_CHANGE) {
340         timer->enabled = 0;
341 
342         timer->handler(task, timer, NULL);
343     }
344 }
345