Tor 0.4.9.0-alpha-dev
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
53TIMEOUT_PUBLIC int timeout_version(void);
54
55TIMEOUT_PUBLIC const char *timeout_vendor(void);
56
57TIMEOUT_PUBLIC int timeout_v_rel(void);
58
59TIMEOUT_PUBLIC int timeout_v_abi(void);
60
61TIMEOUT_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
78typedef 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
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
115struct 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
144TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *, int);
145/* initialize timeout structure (same as TIMEOUT_INITIALIZER) */
146
147#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS
148TIMEOUT_PUBLIC bool timeout_pending(struct timeout *);
149/* true if on timing wheel, false otherwise */
150
151TIMEOUT_PUBLIC bool timeout_expired(struct timeout *);
152/* true if on expired queue, false otherwise */
153
154TIMEOUT_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
163struct timeouts;
164
165TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t, timeout_error_t *);
166/* open a new timing wheel, setting optional HZ (for float conversions) */
167
168TIMEOUT_PUBLIC void timeouts_close(struct timeouts *);
169/* destroy timing wheel */
170
171TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *);
172/* return HZ setting (for float conversions) */
173
174TIMEOUT_PUBLIC void timeouts_update(struct timeouts *, timeout_t);
175/* update timing wheel with current absolute time */
176
177TIMEOUT_PUBLIC void timeouts_step(struct timeouts *, timeout_t);
178/* step timing wheel by relative time */
179
180TIMEOUT_PUBLIC timeout_t timeouts_get_curtime(struct timeouts *);
181/* Return the current tick. */
182
183TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *);
184/* return interval to next required update */
185
186TIMEOUT_PUBLIC void timeouts_add(struct timeouts *, struct timeout *, timeout_t);
187/* add timeout to timing wheel */
188
189TIMEOUT_PUBLIC void timeouts_del(struct timeouts *, struct timeout *);
190/* remove timeout from any timing wheel or expired queue (okay if on neither) */
191
192TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *);
193/* return any expired timeout (caller should loop until NULL-return) */
194
195TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *);
196/* return true if any timeouts pending on timing wheel */
197
198TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *);
199/* return true if any timeouts on expired queue */
200
201TIMEOUT_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
217 int flags;
218 unsigned pc, i, j;
219 struct timeout *to;
220}; /* struct timeouts_it */
221
222TIMEOUT_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 */