FD.io VPP  v18.10-32-g1161dda
Vector Packet Processing
timer.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 /*
16  Copyright (c) 2001, 2002, 2003 Eliot Dresselhaus
17 
18  Permission is hereby granted, free of charge, to any person obtaining
19  a copy of this software and associated documentation files (the
20  "Software"), to deal in the Software without restriction, including
21  without limitation the rights to use, copy, modify, merge, publish,
22  distribute, sublicense, and/or sell copies of the Software, and to
23  permit persons to whom the Software is furnished to do so, subject to
24  the following conditions:
25 
26  The above copyright notice and this permission notice shall be
27  included in all copies or substantial portions of the Software.
28 
29  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 */
37 
38 #include <math.h>
39 #include <stdlib.h>
40 #include <string.h>
41 #include <sys/param.h>
42 
43 #include <vppinfra/vec.h>
44 #include <vppinfra/smp.h>
45 #include <vppinfra/time.h>
46 #include <vppinfra/timer.h>
47 #include <vppinfra/error.h>
48 
49 #ifndef HZ
50 #define HZ 1000
51 #endif
52 
53 typedef struct
54 {
59 
60 /* Vector of currently unexpired timers. */
62 
63 /* Convert time from 64bit floating format to struct timeval. */
64 always_inline void
65 f64_to_tv (f64 t, struct timeval *tv)
66 {
67  tv->tv_sec = t;
68  tv->tv_usec = 1e6 * (t - tv->tv_sec);
69  while (tv->tv_usec >= 1000000)
70  {
71  tv->tv_usec -= 1000000;
72  tv->tv_sec += 1;
73  }
74 }
75 
76 /* Sort timers so that timer soonest to expire is at end. */
77 static int
78 timer_compare (const void *_a, const void *_b)
79 {
80  const timer_callback_t *a = _a;
81  const timer_callback_t *b = _b;
82  f64 dt = b->time - a->time;
83  return dt < 0 ? -1 : (dt > 0 ? +1 : 0);
84 }
85 
86 static inline void
88 {
89  qsort (timers, vec_len (timers), sizeof (timers[0]), timer_compare);
90 }
91 
92 #define TIMER_SIGNAL SIGALRM
93 
94 /* Don't bother set timer if time different is less than this value. */
95 /* We would like to initialize this to 0.75 / (f64) HZ,
96  * but HZ may not be a compile-time constant on some systems,
97  * so instead we do the initialization before first use.
98  */
100 
101 /* Interrupt handler. Call functions for all expired timers.
102  Set time for next timer interrupt. */
103 static void
104 timer_interrupt (int signum)
105 {
106  f64 now = unix_time_now ();
107  f64 dt;
108  timer_callback_t *t;
109 
110  while (1)
111  {
112  if (vec_len (timers) <= 0)
113  return;
114 
115  /* Consider last (earliest) timer in reverse sorted
116  vector of pending timers. */
117  t = vec_end (timers) - 1;
118 
119  ASSERT (now >= 0 && isfinite (now));
120 
121  /* Time difference between when timer goes off and now. */
122  dt = t->time - now;
123 
124  /* If timer is within threshold of going off
125  call user's callback. */
126  if (dt <= time_resolution && isfinite (dt))
127  {
128  _vec_len (timers) -= 1;
129  (*t->func) (t->arg, -dt);
130  }
131  else
132  {
133  /* Set timer for to go off in future. */
134  struct itimerval itv;
135  memset (&itv, 0, sizeof (itv));
136  f64_to_tv (dt, &itv.it_value);
137  if (setitimer (ITIMER_REAL, &itv, 0) < 0)
138  clib_unix_error ("sititmer");
139  return;
140  }
141  }
142 }
143 
144 void
145 timer_block (sigset_t * save)
146 {
147  sigset_t block_timer;
148 
149  memset (&block_timer, 0, sizeof (block_timer));
150  sigaddset (&block_timer, TIMER_SIGNAL);
151  sigprocmask (SIG_BLOCK, &block_timer, save);
152 }
153 
154 void
155 timer_unblock (sigset_t * save)
156 {
157  sigprocmask (SIG_SETMASK, save, 0);
158 }
159 
160 /* Arrange for function to be called some time,
161  roughly equal to dt seconds, in the future. */
162 void
163 timer_call (timer_func_t * func, any arg, f64 dt)
164 {
165  timer_callback_t *t;
166  sigset_t save;
167 
168  /* Install signal handler on first call. */
169  static word signal_installed = 0;
170 
171  if (!signal_installed)
172  {
173  struct sigaction sa;
174 
175  /* Initialize time_resolution before first call to timer_interrupt */
176  time_resolution = 0.75 / (f64) HZ;
177 
178  memset (&sa, 0, sizeof (sa));
179  sa.sa_handler = timer_interrupt;
180 
181  if (sigaction (TIMER_SIGNAL, &sa, 0) < 0)
182  clib_panic ("sigaction");
183 
184  signal_installed = 1;
185  }
186 
187  timer_block (&save);
188 
189  /* Add new timer. */
190  vec_add2 (timers, t, 1);
191 
192  t->time = unix_time_now () + dt;
193  t->func = func;
194  t->arg = arg;
195 
196  {
197  word reset_timer = vec_len (timers) == 1;
198 
199  if (_vec_len (timers) > 1)
200  {
201  reset_timer += t->time < (t - 1)->time;
202  sort_timers (timers);
203  }
204 
205  if (reset_timer)
207  }
208 
209  timer_unblock (&save);
210 }
211 
212 #ifdef TEST
213 
214 #include <vppinfra/random.h>
215 
216 /* Compute average delay of function calls to foo.
217  If this is a small number over a lot of iterations we know
218  the code is working. */
219 
220 static f64 ave_delay = 0;
221 static word ave_delay_count = 0;
222 
224 update (f64 delay)
225 {
226  ave_delay += delay;
227  ave_delay_count += 1;
228 }
229 
230 typedef struct
231 {
232  f64 time_requested, time_called;
233 } foo_t;
234 
235 static f64 foo_base_time = 0;
236 static foo_t *foos = 0;
237 
238 void
239 foo (any arg, f64 delay)
240 {
241  foos[arg].time_called = unix_time_now () - foo_base_time;
242  update (delay);
243 }
244 
245 typedef struct
246 {
247  word count;
248  word limit;
249 } bar_t;
250 
251 void
252 bar (any arg, f64 delay)
253 {
254  bar_t *b = (bar_t *) arg;
255 
256  fformat (stdout, "bar %d delay %g\n", b->count++, delay);
257 
258  update (delay);
259  if (b->count < b->limit)
260  timer_call (bar, arg, random_f64 ());
261 }
262 
263 int
264 main (int argc, char *argv[])
265 {
266  word i, n = atoi (argv[1]);
267  word run_foo = argc > 2;
268 bar_t b = { limit:10 };
269 
270  if (run_foo)
271  {
272  f64 time_limit;
273 
274  time_limit = atof (argv[2]);
275 
276  vec_resize (foos, n);
277  for (i = 0; i < n; i++)
278  {
279  foos[i].time_requested = time_limit * random_f64 ();
280  foos[i].time_called = 1e100;
281  }
282 
283  foo_base_time = unix_time_now ();
284  for (i = 0; i < n; i++)
285  timer_call (foo, i, foos[i].time_requested);
286  }
287  else
288  timer_call (bar, (any) & b, random_f64 ());
289 
290  while (vec_len (timers) > 0)
291  os_sched_yield ();
292 
293  if (vec_len (foos) > 0)
294  {
295  f64 min = 1e100, max = -min;
296  f64 ave = 0, rms = 0;
297 
298  for (i = 0; i < n; i++)
299  {
300  f64 dt = foos[i].time_requested - foos[i].time_called;
301  if (dt < min)
302  min = dt;
303  if (dt > max)
304  max = dt;
305  ave += dt;
306  rms += dt * dt;
307  }
308  ave /= n;
309  rms = sqrt (rms / n - ave * ave);
310  fformat (stdout, "error min %g max %g ave %g +- %g\n", min, max, ave,
311  rms);
312  }
313 
314  fformat (stdout, "%d function calls, ave. timer delay %g secs\n",
315  ave_delay_count, ave_delay / ave_delay_count);
316 
317  return 0;
318 }
319 #endif
320 
321 /*
322  * fd.io coding-style-patch-verification: ON
323  *
324  * Local Variables:
325  * eval: (c-set-style "gnu")
326  * End:
327  */
static void os_sched_yield(void)
Definition: smp.h:62
a
Definition: bitmap.h:538
void timer_unblock(sigset_t *save)
Definition: timer.c:155
word any
Definition: types.h:139
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:562
int i
#define clib_unix_error(format, args...)
Definition: error.h:65
double f64
Definition: types.h:142
static f64 time_resolution
Definition: timer.c:99
memset(h->entries, 0, sizeof(h->entries[0])*entries)
i64 word
Definition: types.h:111
#define always_inline
Definition: clib.h:94
static timer_callback_t * timers
Definition: timer.c:61
static f64 unix_time_now(void)
Definition: time.h:238
#define vec_resize(V, N)
Resize a vector (no header, unspecified alignment) Add N elements to end of given vector V...
Definition: vec.h:240
#define vec_end(v)
End (last data address) of vector.
void timer_call(timer_func_t *func, any arg, f64 dt)
Definition: timer.c:163
static int timer_compare(const void *_a, const void *_b)
Definition: timer.c:78
#define TIMER_SIGNAL
Definition: timer.c:92
word fformat(FILE *f, char *fmt,...)
Definition: format.c:453
static void timer_interrupt(int signum)
Definition: timer.c:104
static f64 sqrt(f64 x)
Definition: math.h:44
#define ASSERT(truth)
static void f64_to_tv(f64 t, struct timeval *tv)
Definition: timer.c:65
static f64 random_f64(u32 *seed)
Generate f64 random number in the interval [0,1].
Definition: random.h:145
size_t count
Definition: vapi.c:46
void( timer_func_t)(any arg, f64 delay)
Definition: timer.h:29
void timer_block(sigset_t *save)
Definition: timer.c:145
int main(int argc, char **argv)
Definition: persist.c:215
void qsort(void *base, uword n, uword size, int(*compar)(const void *, const void *))
Definition: qsort.c:56
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
Linear Congruential Random Number Generator.
#define clib_panic(format, args...)
Definition: error.h:72
timer_func_t * func
Definition: timer.c:56
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".
static void sort_timers(timer_callback_t *timers)
Definition: timer.c:87