LCOV - code coverage report
Current view: top level - lib - timeout.c (source / functions) Hit Total Coverage
Test: coverage.info.cleaned Lines: 104 110 94.5 %
Date: 2023-04-18 16:19:03 Functions: 14 15 93.3 %

          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             : }

Generated by: LCOV version 1.15-2-gb9d6727