TAS
TCP Acceleration as an OS Service
timeout.c
1 /*
2  * Copyright 2019 University of Washington, Max Planck Institute for
3  * Software Systems, and The University of Texas at Austin
4  *
5  * Permission is hereby granted, free of charge, to any person obtaining
6  * a copy of this software and associated documentation files (the
7  * "Software"), to deal in the Software without restriction, including
8  * without limitation the rights to use, copy, modify, merge, publish,
9  * distribute, sublicense, and/or sell copies of the Software, and to
10  * permit persons to whom the Software is furnished to do so, subject to
11  * the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be
14  * included in all copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
20  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
21  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
22  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23  */
24 
25 #include <inttypes.h>
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <time.h>
30 #include <unistd.h>
31 
32 #include <utils.h>
33 #include <utils_timeout.h>
34 
37 #define TIMEOUT_BITS 28
38 
39 #define TIMEOUT_MASK ((1 << TIMEOUT_BITS) - 1)
40 
42 #define MAX_TIMEOUTS 64
43 
45 static uint64_t tsc_per_us = 0;
46 
48 static inline void move_due_timeouts(struct timeout_manager *mgr,
49  uint32_t cur_ts);
51 static inline int timeout_due(struct timeout *to, uint32_t ts);
52 
54 static inline uint32_t timestamp_us_long(void);
56 static inline uint32_t timestamp_us(void);
58 static inline int32_t rel_time(uint32_t cur, struct timeout *to);
60 static inline void calibrate_tsc(void);
61 
63  void (*handler)(struct timeout *, uint8_t, void *), void *handler_opaque)
64 {
65  calibrate_tsc();
66  memset(mgr, 0, sizeof(*mgr));
67  mgr->handler = handler;
68  mgr->handler_opaque = handler_opaque;
69  return 0;
70 }
71 
72 uint32_t util_timeout_time_us(void)
73 {
74  if (tsc_per_us == 0)
75  calibrate_tsc();
76  return timestamp_us_long();
77 }
78 
80 {
81  util_timeout_poll_ts(mgr, timestamp_us());
82 }
83 
84 void util_timeout_poll_ts(struct timeout_manager *mgr, uint32_t cur_ts)
85 {
86  unsigned num = 0;
87  struct timeout *to;
88 
89  cur_ts &= TIMEOUT_MASK;
90 
91  /* check for potential due timeouts in #timeouts */
92  move_due_timeouts(mgr, cur_ts);
93 
94  /* process due queue */
95  while ((to = mgr->due_first) != NULL && num < MAX_TIMEOUTS) {
96  mgr->due_first = to->next;
97  if (mgr->due_first != NULL) {
98  mgr->due_first->prev = NULL;
99  } else {
100  mgr->due_last = NULL;
101  }
102 
103  mgr->handler(to, to->timeout_type >> TIMEOUT_BITS, mgr->handler_opaque);
104 
105  num++;
106  }
107 
108 }
109 
110 void util_timeout_arm(struct timeout_manager *mgr, struct timeout *to,
111  uint32_t us, uint8_t type)
112 {
113  util_timeout_arm_ts(mgr, to, us, type, timestamp_us());
114 }
115 
116 void util_timeout_arm_ts(struct timeout_manager *mgr, struct timeout *to,
117  uint32_t us, uint8_t type, uint32_t cur_ts)
118 {
119  struct timeout *tp, *tn;
120 
121  cur_ts &= TIMEOUT_MASK;
122 
123  /* make sure #us is not out of range */
124  if (us >= (1 << (TIMEOUT_BITS - 1))) {
125  fprintf(stderr, "timeout_arm: specified timeout is out of range (needs to "
126  "be < %u, but got %u)\n", (1 << (TIMEOUT_BITS - 1)), us);
127  abort();
128  }
129 
130  /* step 1: move all due timeouts to due queue */
131  move_due_timeouts(mgr, cur_ts);
132 
133  /* step 2: find predecessor and successor in list */
134  for (tp = mgr->timeouts_last; tp != NULL && rel_time(cur_ts, tp) > us;
135  tp = tp->prev);
136  tn = (tp != NULL ? tp->next : mgr->timeouts_first);
137 
138  /* step 3: insert */
139  to->timeout_type = ((uint32_t) type) << TIMEOUT_BITS;
140  to->timeout_type |= (cur_ts + us) & TIMEOUT_MASK;
141  to->next = tn;
142  to->prev = tp;
143  if (tp == NULL) {
144  mgr->timeouts_first = to;
145  } else {
146  tp->next = to;
147  }
148  if (tn == NULL) {
149  mgr->timeouts_last = to;
150  } else {
151  tn->prev = to;
152  }
153 }
154 
155 void util_timeout_disarm(struct timeout_manager *mgr, struct timeout *to)
156 {
157  struct timeout *prev, *next;
158 
159  prev = to->prev;
160  next = to->next;
161  if (prev == NULL) {
162  if (mgr->timeouts_first == to) {
163  mgr->timeouts_first = next;
164  } else if (mgr->due_first == to) {
165  mgr->due_first = next;
166  } else {
167  fprintf(stderr, "timeout_disarm: timeout neither in timeouts_first nor "
168  "due_first\n");
169  abort();
170  }
171  } else {
172  prev->next = next;
173  }
174 
175  if (next == NULL) {
176  if (mgr->timeouts_last == to) {
177  mgr->timeouts_last = prev;
178  } else if (mgr->due_last == to) {
179  mgr->due_last = prev;
180  } else {
181  fprintf(stderr, "timeout_disarm: timeout neither in timeouts_last nor "
182  "due_last\n");
183  abort();
184  }
185  } else {
186  next->prev = prev;
187  }
188 }
189 
190 uint32_t util_timeout_next(struct timeout_manager *mgr, uint32_t cur_ts)
191 {
192  if(mgr->due_first != NULL) {
193  // We have timeouts due immediately
194  return 0;
195  }
196 
197  if(mgr->timeouts_first == NULL) {
198  // Nothing due
199  return -1U;
200  }
201 
202  cur_ts &= TIMEOUT_MASK;
203  int32_t next = rel_time(cur_ts, mgr->timeouts_first);
204  return (next < 0 ? 0 : next);
205 }
206 
207 static inline void move_due_timeouts(struct timeout_manager *mgr, uint32_t cur_ts)
208 {
209  struct timeout *to, *next;
210 
211  while ((to = mgr->timeouts_first) != NULL &&
212  timeout_due(mgr->timeouts_first, cur_ts))
213  {
214  /* remove from timeouts list */
215  mgr->timeouts_first = next = to->next;
216  if (next != NULL) {
217  next->prev = NULL;
218  } else {
219  mgr->timeouts_last = NULL;
220  }
221 
222  /* add to due list */
223  to->next = NULL;
224  to->prev = mgr->due_last;
225  if (mgr->due_last == NULL) {
226  mgr->due_first = to;
227  } else {
228  mgr->due_last->next = to;
229  }
230  mgr->due_last = to;
231  }
232 }
233 
234 static inline int timeout_due(struct timeout *to, uint32_t ts)
235 {
236  return rel_time(ts, to) <= 0;
237 }
238 
239 static inline uint32_t timestamp_us_long(void)
240 {
241  return util_rdtsc() / tsc_per_us;
242 }
243 
244 static inline uint32_t timestamp_us(void)
245 {
246  return timestamp_us_long() & TIMEOUT_MASK;
247 }
248 
249 static inline int32_t rel_time(uint32_t cur_ts, struct timeout *to)
250 {
251  const uint32_t middle = (1 << (TIMEOUT_BITS - 1));
252  uint32_t to_ts = to->timeout_type & TIMEOUT_MASK;
253  uint32_t start, end;
254 
255  if (cur_ts < middle) {
256  /* negative interval is split in half */
257  start = (cur_ts - middle) & TIMEOUT_MASK;
258  end = (1 << TIMEOUT_BITS);
259  if (start <= to_ts && to_ts < end) {
260  /* in first half of negative interval, smallest timestamps */
261  return to_ts - start - middle;
262  } else {
263  /* in second half or in positive interval */
264  return to_ts - cur_ts;
265  }
266  } else if (cur_ts == middle) {
267  /* intervals not split */
268  return to_ts - cur_ts;
269  } else {
270  /* higher interval is split */
271  start = 0;
272  end = ((cur_ts + middle) & TIMEOUT_MASK) + 1;
273  if (start <= cur_ts && to_ts < end) {
274  /* in second half of positive interval, largest timestamps */
275  return to_ts + ((1 << TIMEOUT_BITS) - cur_ts);
276  } else {
277  /* in negative interval or first half of positive interval */
278  return to_ts - cur_ts;
279  }
280  }
281 }
282 
284 static inline void calibrate_tsc(void)
285 {
286  struct timespec ts_before, ts_after;
287  uint64_t tsc;
288  double freq;
289 
290  if (tsc_per_us != 0)
291  return;
292 
293  if (clock_gettime(CLOCK_MONOTONIC_RAW, &ts_before) != 0) {
294  fprintf(stderr, "calibrate_tsc: clock_gettime(CLOCK_MONOTONIC_RAW) "
295  "failed\n");
296  abort();
297  }
298 
299  tsc = util_rdtsc();
300  usleep(10000);
301  tsc = util_rdtsc() - tsc;
302 
303  if (clock_gettime(CLOCK_MONOTONIC_RAW, &ts_after) != 0) {
304  fprintf(stderr, "calibrate_tsc: clock_gettime(CLOCK_MONOTONIC_RAW) "
305  "failed\n");
306  abort();
307  }
308 
309  freq = ((ts_after.tv_sec * 1000000UL) + (ts_after.tv_nsec / 1000)) -
310  ((ts_before.tv_sec * 1000000UL) + (ts_before.tv_nsec / 1000));
311  tsc_per_us = tsc / freq;
312 }
struct timeout * timeouts_first
Definition: utils_timeout.h:55
uint32_t timeout_type
Time and type. Type is stored in the 4 most significant bits, and the time in the 28 least significan...
Definition: utils_timeout.h:43
uint32_t util_timeout_time_us(void)
Definition: timeout.c:72
struct timeout * timeouts_last
Definition: utils_timeout.h:57
struct timeout * due_last
Definition: utils_timeout.h:61
struct timeout * due_first
Definition: utils_timeout.h:59
int util_timeout_init(struct timeout_manager *mgr, void(*handler)(struct timeout *, uint8_t, void *), void *handler_opaque)
Definition: timeout.c:62
void util_timeout_poll(struct timeout_manager *mgr)
Definition: timeout.c:79
void(* handler)(struct timeout *, uint8_t, void *)
Definition: utils_timeout.h:64
struct timeout * next
Definition: utils_timeout.h:46
void util_timeout_disarm(struct timeout_manager *mgr, struct timeout *to)
Definition: timeout.c:155
void util_timeout_poll_ts(struct timeout_manager *mgr, uint32_t cur_ts)
Definition: timeout.c:84
void util_timeout_arm_ts(struct timeout_manager *mgr, struct timeout *to, uint32_t us, uint8_t type, uint32_t cur_ts)
Definition: timeout.c:116
void * handler_opaque
Definition: utils_timeout.h:66
void util_timeout_arm(struct timeout_manager *mgr, struct timeout *to, uint32_t us, uint8_t type)
Definition: timeout.c:110
struct timeout * prev
Definition: utils_timeout.h:48