xref: /unit/src/nxt_timer.c (revision 810:5d0edd35c4ce)
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