Line data Source code
1 : /* ==========================================================================
2 : * timeout.c - Tickless hierarchical timing wheel.
3 : * --------------------------------------------------------------------------
4 : * Copyright (c) 2013, 2014 William Ahern
5 : *
6 : * Permission is hereby granted, free of charge, to any person obtaining a
7 : * copy of this software and associated documentation files (the
8 : * "Software"), to deal in the Software without restriction, including
9 : * without limitation the rights to use, copy, modify, merge, publish,
10 : * distribute, sublicense, and/or sell copies of the Software, and to permit
11 : * persons to whom the Software is furnished to do so, subject to the
12 : * following conditions:
13 : *
14 : * The above copyright notice and this permission notice shall be included
15 : * in all copies or substantial portions of the Software.
16 : *
17 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 : * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
20 : * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
21 : * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
22 : * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
23 : * USE OR OTHER DEALINGS IN THE SOFTWARE.
24 : * ==========================================================================
25 : */
26 :
27 : #include <assert.h>
28 :
29 : #include <limits.h> /* CHAR_BIT */
30 :
31 : #include <stddef.h> /* NULL */
32 : #include <stdlib.h> /* malloc(3) free(3) */
33 :
34 : #include <inttypes.h> /* UINT64_C uint64_t */
35 :
36 : #include <string.h> /* memset(3) */
37 :
38 : #include <errno.h> /* errno */
39 :
40 : #include "lwan-private.h"
41 :
42 : #include "list.h"
43 :
44 : #include "timeout.h"
45 :
46 : /*
47 : * A N C I L L A R Y R O U T I N E S
48 : *
49 : * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
50 :
51 : #define abstime_t timeout_t /* for documentation purposes */
52 : #define reltime_t timeout_t /* "" */
53 :
54 : /*
55 : * B I T M A N I P U L A T I O N R O U T I N E S
56 : *
57 : * The macros and routines below implement wheel parameterization. The
58 : * inputs are:
59 : *
60 : * WHEEL_BIT - The number of value bits mapped in each wheel. The
61 : * lowest-order WHEEL_BIT bits index the lowest-order (highest
62 : * resolution) wheel, the next group of WHEEL_BIT bits the
63 : * higher wheel, etc.
64 : *
65 : * WHEEL_NUM - The number of wheels. WHEEL_BIT * WHEEL_NUM = the number of
66 : * value bits used by all the wheels. For the default of 6 and
67 : * 4, only the low 24 bits are processed. Any timeout value
68 : * larger than this will cycle through again.
69 : *
70 : * The implementation uses bit fields to remember which slot in each wheel
71 : * is populated, and to generate masks of expiring slots according to the
72 : * current update interval (i.e. the "tickless" aspect). The slots to
73 : * process in a wheel are (populated-set & interval-mask).
74 : *
75 : * WHEEL_BIT cannot be larger than 6 bits because 2^6 -> 64 is the largest
76 : * number of slots which can be tracked in a uint64_t integer bit field.
77 : * WHEEL_BIT cannot be smaller than 3 bits because of our rotr and rotl
78 : * routines, which only operate on all the value bits in an integer, and
79 : * there's no integer smaller than uint8_t.
80 : *
81 : * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
82 :
83 : #define WHEEL_BIT 6
84 : #define WHEEL_NUM 4
85 :
86 : #define WHEEL_LEN (1U << WHEEL_BIT)
87 : #define WHEEL_MAX (WHEEL_LEN - 1)
88 : #define WHEEL_MASK (WHEEL_LEN - 1)
89 : #define TIMEOUT_MAX ((TIMEOUT_C(1) << (WHEEL_BIT * WHEEL_NUM)) - 1)
90 :
91 : /* On GCC and clang and some others, we can use __builtin functions. They
92 : * are not defined for n==0, but these are never called with n==0. */
93 :
94 : #define ctz64(n) __builtin_ctzll(n)
95 : #define clz64(n) __builtin_clzll(n)
96 : #if LONG_BITS == 32
97 : #define ctz32(n) __builtin_ctzl(n)
98 : #define clz32(n) __builtin_clzl(n)
99 : #else
100 : #define ctz32(n) __builtin_ctz(n)
101 : #define clz32(n) __builtin_clz(n)
102 : #endif
103 :
104 : #define ctz(n) ctz64(n)
105 : #define clz(n) clz64(n)
106 : #define fls(n) ((int)(64 - clz64(n)))
107 :
108 : #define WHEEL_C(n) UINT64_C(n)
109 : #define WHEEL_PRIu PRIu64
110 : #define WHEEL_PRIx PRIx64
111 :
112 : typedef uint64_t wheel_t;
113 :
114 : /* See "Safe, Efficient, and Portable Rotate in C/C++" by John Regehr
115 : * http://blog.regehr.org/archives/1063
116 : * These should be recognized by the backend C compiler and turned into a rol
117 : */
118 :
119 : #define WHEEL_T_BITS ((CHAR_BIT) * sizeof(wheel_t))
120 :
121 1384 : static inline wheel_t rotl(const wheel_t v, uint32_t n)
122 : {
123 1384 : assert(n < WHEEL_T_BITS);
124 1384 : return (v << n) | (v >> (-n & (WHEEL_T_BITS - 1)));
125 : }
126 :
127 1234 : static inline wheel_t rotr(const wheel_t v, uint32_t n)
128 : {
129 1234 : assert(n < WHEEL_T_BITS);
130 1234 : return (v >> n) | (v << (-n & (WHEEL_T_BITS - 1)));
131 : }
132 :
133 : #undef WHEEL_T_BITS
134 :
135 : /*
136 : * T I M E R R O U T I N E S
137 : *
138 : * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
139 :
140 : struct timeouts {
141 : struct list_head wheel[WHEEL_NUM][WHEEL_LEN];
142 : struct list_head expired;
143 :
144 : wheel_t pending[WHEEL_NUM];
145 :
146 : timeout_t curtime;
147 : };
148 :
149 184 : static struct timeouts *timeouts_init(struct timeouts *T)
150 : {
151 : unsigned i, j;
152 :
153 920 : for (i = 0; i < N_ELEMENTS(T->wheel); i++) {
154 47840 : for (j = 0; j < N_ELEMENTS(T->wheel[i]); j++) {
155 47104 : list_head_init(&T->wheel[i][j]);
156 : }
157 : }
158 :
159 184 : list_head_init(&T->expired);
160 :
161 920 : for (i = 0; i < N_ELEMENTS(T->pending); i++) {
162 736 : T->pending[i] = 0;
163 : }
164 :
165 184 : T->curtime = 0;
166 :
167 184 : return T;
168 : }
169 :
170 184 : struct timeouts *timeouts_open(timeout_error_t *error)
171 : {
172 : struct timeouts *T;
173 :
174 184 : if ((T = lwan_aligned_alloc(sizeof *T, 64)))
175 184 : return timeouts_init(T);
176 :
177 0 : *error = errno;
178 :
179 0 : return NULL;
180 : }
181 :
182 0 : void timeouts_close(struct timeouts *T)
183 : {
184 0 : free(T);
185 0 : }
186 :
187 257 : void timeouts_del(struct timeouts *T, struct timeout *to)
188 : {
189 257 : if (to->pending) {
190 139 : list_del_from(to->pending, &to->tqe);
191 :
192 139 : if (to->pending != &T->expired && list_empty(to->pending)) {
193 139 : ptrdiff_t index = to->pending - &T->wheel[0][0];
194 139 : ptrdiff_t wheel = index / WHEEL_LEN;
195 139 : ptrdiff_t slot = index % WHEEL_LEN;
196 :
197 139 : T->pending[wheel] &= ~(WHEEL_C(1) << slot);
198 : }
199 :
200 139 : to->pending = NULL;
201 : }
202 257 : }
203 :
204 247 : static inline reltime_t timeout_rem(struct timeouts *T, struct timeout *to)
205 : {
206 247 : return to->expires - T->curtime;
207 : }
208 :
209 247 : static inline int timeout_wheel(timeout_t timeout)
210 : {
211 : /* must be called with timeout != 0, so fls input is nonzero */
212 247 : return (fls(LWAN_MIN(timeout, TIMEOUT_MAX)) - 1) / WHEEL_BIT;
213 : }
214 :
215 247 : static inline int timeout_slot(int wheel, timeout_t expires)
216 : {
217 247 : return (int)(WHEEL_MASK & ((expires >> (wheel * WHEEL_BIT)) - !!wheel));
218 : }
219 :
220 : static void
221 254 : timeouts_sched(struct timeouts *T, struct timeout *to, timeout_t expires)
222 : {
223 : timeout_t rem;
224 : int wheel, slot;
225 :
226 254 : timeouts_del(T, to);
227 :
228 254 : to->expires = expires;
229 :
230 254 : if (expires > T->curtime) {
231 247 : rem = timeout_rem(T, to);
232 :
233 : /* rem is nonzero since:
234 : * rem == timeout_rem(T,to),
235 : * == to->expires - T->curtime
236 : * and above we have expires > T->curtime.
237 : */
238 247 : wheel = timeout_wheel(rem);
239 247 : slot = timeout_slot(wheel, to->expires);
240 :
241 247 : to->pending = &T->wheel[wheel][slot];
242 :
243 247 : T->pending[wheel] |= WHEEL_C(1) << slot;
244 : } else {
245 7 : to->pending = &T->expired;
246 : }
247 :
248 254 : list_add_tail(to->pending, &to->tqe);
249 254 : }
250 :
251 241 : void timeouts_add(struct timeouts *T, struct timeout *to, timeout_t timeout)
252 : {
253 241 : if (to->flags & TIMEOUT_ABS)
254 0 : timeouts_sched(T, to, timeout);
255 : else
256 241 : timeouts_sched(T, to, T->curtime + timeout);
257 241 : }
258 :
259 829 : void timeouts_update(struct timeouts *T, abstime_t curtime)
260 : {
261 829 : timeout_t elapsed = curtime - T->curtime;
262 : struct list_head todo;
263 : int wheel;
264 :
265 829 : list_head_init(&todo);
266 :
267 : /*
268 : * There's no avoiding looping over every wheel. It's best to keep
269 : * WHEEL_NUM smallish.
270 : */
271 1722 : for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
272 : wheel_t pending;
273 :
274 : /*
275 : * Calculate the slots expiring in this wheel
276 : *
277 : * If the elapsed time is greater than the maximum period of
278 : * the wheel, mark every position as expiring.
279 : *
280 : * Otherwise, to determine the expired slots fill in all the
281 : * bits between the last slot processed and the current
282 : * slot, inclusive of the last slot. We'll bitwise-AND this
283 : * with our pending set below.
284 : *
285 : * If a wheel rolls over, force a tick of the next higher
286 : * wheel.
287 : */
288 1538 : if ((elapsed >> (wheel * WHEEL_BIT)) > WHEEL_MAX) {
289 846 : pending = (wheel_t)~WHEEL_C(0);
290 : } else {
291 692 : const timeout_t wheel_mask = (timeout_t)WHEEL_MASK;
292 692 : wheel_t _elapsed = WHEEL_MASK & (elapsed >> (wheel * WHEEL_BIT));
293 : unsigned int oslot, nslot;
294 :
295 : /*
296 : * TODO: It's likely that at least one of the
297 : * following three bit fill operations is redundant
298 : * or can be replaced with a simpler operation.
299 : */
300 692 : oslot = (unsigned int)(wheel_mask &
301 692 : (T->curtime >> (wheel * WHEEL_BIT)));
302 692 : pending = rotl(((UINT64_C(1) << _elapsed) - 1), oslot);
303 :
304 692 : nslot =
305 692 : (unsigned int)(wheel_mask & (curtime >> (wheel * WHEEL_BIT)));
306 692 : pending |= rotr(rotl(((WHEEL_C(1) << _elapsed) - 1), nslot),
307 : (unsigned int)_elapsed);
308 692 : pending |= WHEEL_C(1) << nslot;
309 : }
310 :
311 1551 : while (pending & T->pending[wheel]) {
312 : /* ctz input cannot be zero: loop condition. */
313 13 : int slot = ctz(pending & T->pending[wheel]);
314 :
315 13 : list_append_list(&todo, &T->wheel[wheel][slot]);
316 13 : list_head_init(&T->wheel[wheel][slot]);
317 :
318 13 : T->pending[wheel] &= ~(UINT64_C(1) << slot);
319 : }
320 :
321 1538 : if (!(0x1 & pending))
322 645 : break; /* break if we didn't wrap around end of wheel */
323 :
324 : /* if we're continuing, the next wheel must tick at least once */
325 893 : elapsed = LWAN_MAX(elapsed, (WHEEL_LEN << (wheel * WHEEL_BIT)));
326 : }
327 :
328 829 : T->curtime = curtime;
329 :
330 : struct timeout *to, *next;
331 842 : list_for_each_safe (&todo, to, next, tqe) {
332 13 : list_del_from(&todo, &to->tqe);
333 13 : to->pending = NULL;
334 :
335 13 : timeouts_sched(T, to, to->expires);
336 : }
337 :
338 829 : return;
339 : }
340 :
341 : /*
342 : * Calculate the interval before needing to process any timeouts pending on
343 : * any wheel.
344 : *
345 : * (This is separated from the public API routine so we can evaluate our
346 : * wheel invariant assertions irrespective of the expired queue.)
347 : *
348 : * This might return a timeout value sooner than any installed timeout if
349 : * only higher-order wheels have timeouts pending. We can only know when to
350 : * process a wheel, not precisely when a timeout is scheduled. Our timeout
351 : * accuracy could be off by 2^(N*M)-1 units where N is the wheel number and
352 : * M is WHEEL_BIT. Only timeouts which have fallen through to wheel 0 can be
353 : * known exactly.
354 : *
355 : * We should never return a timeout larger than the lowest actual timeout.
356 : */
357 824 : static timeout_t timeouts_int(struct timeouts *T)
358 : {
359 824 : const timeout_t wheel_mask = (timeout_t)WHEEL_MASK;
360 824 : timeout_t timeout = ~TIMEOUT_C(0), _timeout;
361 : timeout_t relmask;
362 : unsigned int slot;
363 : int wheel;
364 :
365 824 : relmask = 0;
366 :
367 4120 : for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
368 3296 : if (T->pending[wheel]) {
369 542 : slot = (unsigned int)(wheel_mask & (T->curtime >> (wheel * WHEEL_BIT)));
370 :
371 : /* ctz input cannot be zero: T->pending[wheel] is
372 : * nonzero, so rotr() is nonzero. */
373 542 : _timeout = (timeout_t)(ctz(rotr(T->pending[wheel], slot)) + !!wheel)
374 542 : << (wheel * WHEEL_BIT);
375 : /* +1 to higher order wheels as those timeouts are one rotation in
376 : * the future (otherwise they'd be on a lower wheel or expired) */
377 :
378 542 : _timeout -= relmask & T->curtime;
379 : /* reduce by how much lower wheels have progressed */
380 :
381 542 : timeout = LWAN_MIN(_timeout, timeout);
382 : }
383 :
384 3296 : relmask <<= WHEEL_BIT;
385 3296 : relmask |= WHEEL_MASK;
386 : }
387 :
388 824 : return timeout;
389 : }
390 :
391 : /*
392 : * Calculate the interval our caller can wait before needing to process
393 : * events.
394 : */
395 831 : timeout_t timeouts_timeout(struct timeouts *T)
396 : {
397 831 : if (!list_empty(&T->expired))
398 7 : return 0;
399 :
400 824 : return timeouts_int(T);
401 : }
402 :
403 14 : struct timeout *timeouts_get(struct timeouts *T)
404 : {
405 14 : struct timeout *to = list_top(&T->expired, struct timeout, tqe);
406 :
407 14 : if (!to)
408 7 : return NULL;
409 :
410 7 : list_del_from(&T->expired, &to->tqe);
411 7 : to->pending = NULL;
412 :
413 7 : return to;
414 : }
|