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 */ 257