src/ext/timeouts/timeout.h

   1 /* ==========================================================================
   2  * timeout.h - 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 #ifndef TIMEOUT_H
  27 #define TIMEOUT_H
  28
  29 #include <stdbool.h>    /* bool */
  30 #include <stdio.h>      /* FILE */
  31
  32 #include <inttypes.h>   /* PRIu64 PRIx64 PRIX64 uint64_t */
  33
  34 #include "ext/tor_queue.h"  /* TAILQ(3) */
  35
  36
  37 /*
  38  * V E R S I O N  I N T E R F A C E S
  39  *
  40  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  41
  42 #if !defined TIMEOUT_PUBLIC
  43 #define TIMEOUT_PUBLIC
  44 #endif
  45
  46 #define TIMEOUT_VERSION TIMEOUT_V_REL
  47 #define TIMEOUT_VENDOR  "william@25thandClement.com"
  48
  49 #define TIMEOUT_V_REL 0x20160226
  50 #define TIMEOUT_V_ABI 0x20160224
  51 #define TIMEOUT_V_API 0x20160226
  52
  53 TIMEOUT_PUBLIC int timeout_version(void);
  54
  55 TIMEOUT_PUBLIC const char *timeout_vendor(void);
  56
  57 TIMEOUT_PUBLIC int timeout_v_rel(void);
  58
  59 TIMEOUT_PUBLIC int timeout_v_abi(void);
  60
  61 TIMEOUT_PUBLIC int timeout_v_api(void);
  62
  63
  64 /*
  65  * I N T E G E R  T Y P E  I N T E R F A C E S
  66  *
  67  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  68
  69 #define TIMEOUT_C(n) UINT64_C(n)
  70 #define TIMEOUT_PRIu PRIu64
  71 #define TIMEOUT_PRIx PRIx64
  72 #define TIMEOUT_PRIX PRIX64
  73
  74 #define TIMEOUT_mHZ TIMEOUT_C(1000)
  75 #define TIMEOUT_uHZ TIMEOUT_C(1000000)
  76 #define TIMEOUT_nHZ TIMEOUT_C(1000000000)
  77
  78 typedef uint64_t timeout_t;
  79
  80 #define timeout_error_t int /* for documentation purposes */
  81
  82
  83 /*
  84  * C A L L B A C K  I N T E R F A C E
  85  *
  86  * Callback function parameters unspecified to make embedding into existing
  87  * applications easier.
  88  *
  89  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
  90
  91 #ifndef TIMEOUT_CB_OVERRIDE
  92 struct timeout_cb_t {
  93         void (*fn)(void);
  94         void *arg;
  95 }; /* struct timeout_cb_t */
  96 #endif
  97
  98 /*
  99  * T I M E O U T  I N T E R F A C E S
 100  *
 101  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 102
 103 #ifndef TIMEOUT_DISABLE_INTERVALS
 104 #define TIMEOUT_INT 0x01 /* interval (repeating) timeout */
 105 #endif
 106 #define TIMEOUT_ABS 0x02 /* treat timeout values as absolute */
 107
 108 #define TIMEOUT_INITIALIZER(flags) { (flags) }
 109
 110 #define timeout_setcb(to, fn, arg) do { \
 111         (to)->callback.fn = (fn);       \
 112         (to)->callback.arg = (arg);     \
 113 } while (0)
 114
 115 struct timeout {
 116         int flags;
 117
 118         timeout_t expires;
 119         /* absolute expiration time */
 120
 121         struct timeout_list *pending;
 122         /* timeout list if pending on wheel or expiry queue */
 123
 124         TOR_TAILQ_ENTRY(timeout) tqe;
 125         /* entry member for struct timeout_list lists */
 126
 127 #ifndef TIMEOUT_DISABLE_CALLBACKS
 128         struct timeout_cb_t callback;
 129         /* optional callback information */
 130 #endif
 131
 132 #ifndef TIMEOUT_DISABLE_INTERVALS
 133         timeout_t interval;
 134         /* timeout interval if periodic */
 135 #endif
 136
 137 #ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS
 138         struct timeouts *timeouts;
 139         /* timeouts collection if member of */
 140 #endif
 141 }; /* struct timeout */
 142
 143
 144 TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *, int);
 145 /* initialize timeout structure (same as TIMEOUT_INITIALIZER) */
 146
 147 #ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS
 148 TIMEOUT_PUBLIC bool timeout_pending(struct timeout *);
 149 /* true if on timing wheel, false otherwise */
 150
 151 TIMEOUT_PUBLIC bool timeout_expired(struct timeout *);
 152 /* true if on expired queue, false otherwise */
 153
 154 TIMEOUT_PUBLIC void timeout_del(struct timeout *);
 155 /* remove timeout from any timing wheel (okay if not member of any) */
 156 #endif
 157
 158 /*
 159  * T I M I N G  W H E E L  I N T E R F A C E S
 160  *
 161  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 162
 163 struct timeouts;
 164
 165 TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t, timeout_error_t *);
 166 /* open a new timing wheel, setting optional HZ (for float conversions) */
 167
 168 TIMEOUT_PUBLIC void timeouts_close(struct timeouts *);
 169 /* destroy timing wheel */
 170
 171 TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *);
 172 /* return HZ setting (for float conversions) */
 173
 174 TIMEOUT_PUBLIC void timeouts_update(struct timeouts *, timeout_t);
 175 /* update timing wheel with current absolute time */
 176
 177 TIMEOUT_PUBLIC void timeouts_step(struct timeouts *, timeout_t);
 178 /* step timing wheel by relative time */
 179
 180 TIMEOUT_PUBLIC timeout_t timeouts_get_curtime(struct timeouts *);
 181 /* Return the current tick. */
 182
 183 TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *);
 184 /* return interval to next required update */
 185
 186 TIMEOUT_PUBLIC void timeouts_add(struct timeouts *, struct timeout *, timeout_t);
 187 /* add timeout to timing wheel */
 188
 189 TIMEOUT_PUBLIC void timeouts_del(struct timeouts *, struct timeout *);
 190 /* remove timeout from any timing wheel or expired queue (okay if on neither) */
 191
 192 TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *);
 193 /* return any expired timeout (caller should loop until NULL-return) */
 194
 195 TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *);
 196 /* return true if any timeouts pending on timing wheel */
 197
 198 TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *);
 199 /* return true if any timeouts on expired queue */
 200
 201 TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *, FILE *);
 202 /* return true if invariants hold. describes failures to optional file handle. */
 203
 204 #define TIMEOUTS_PENDING 0x10
 205 #define TIMEOUTS_EXPIRED 0x20
 206 #define TIMEOUTS_ALL     (TIMEOUTS_PENDING|TIMEOUTS_EXPIRED)
 207 #define TIMEOUTS_CLEAR   0x40
 208
 209 #define TIMEOUTS_IT_INITIALIZER(flags) { (flags), 0, 0, 0, 0 }
 210
 211 #define TIMEOUTS_IT_INIT(cur, _flags) do {                              \
 212         (cur)->flags = (_flags);                                        \
 213         (cur)->pc = 0;                                                  \
 214 } while (0)
 215
 216 struct timeouts_it {
 217         int flags;
 218         unsigned pc, i, j;
 219         struct timeout *to;
 220 }; /* struct timeouts_it */
 221
 222 TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *, struct timeouts_it *);
 223 /* return next timeout in pending wheel or expired queue. caller can delete
 224  * the returned timeout, but should not otherwise manipulate the timing
 225  * wheel. in particular, caller SHOULD NOT delete any other timeout as that
 226  * could invalidate cursor state and trigger a use-after-free.
 227  */
 228
 229 #define TIMEOUTS_FOREACH(var, T, flags)                                 \
 230         struct timeouts_it _it = TIMEOUTS_IT_INITIALIZER((flags));      \
 231         while (((var) = timeouts_next((T), &_it)))
 232
 233
 234 /*
 235  * B O N U S  W H E E L  I N T E R F A C E S
 236  *
 237  * I usually use floating point timeouts in all my code, but it's cleaner to
 238  * separate it to keep the core algorithmic code simple.
 239  *
 240  * Using macros instead of static inline routines where <math.h> routines
 241  * might be used to keep -lm linking optional.
 242  *
 243  * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 244
 245 #include <math.h> /* ceil(3) */
 246
 247 #define timeouts_f2i(T, f) \
 248         ((timeout_t)ceil((f) * timeouts_hz((T)))) /* prefer late expiration over early */
 249
 250 #define timeouts_i2f(T, i) \
 251         ((double)(i) / timeouts_hz((T)))
 252
 253 #define timeouts_addf(T, to, timeout) \
 254         timeouts_add((T), (to), timeouts_f2i((T), (timeout)))
 255
 256 #endif /* TIMEOUT_H */