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