FD.io VPP  v17.07-30-g839fa73
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/time.h>
45 #include <vppinfra/timer.h>
46 #include <vppinfra/error.h>
47 
48 typedef struct
49 {
54 
55 /* Vector of currently unexpired timers. */
57 
58 /* Convert time from 64bit floating format to struct timeval. */
59 always_inline void
60 f64_to_tv (f64 t, struct timeval *tv)
61 {
62  tv->tv_sec = t;
63  tv->tv_usec = 1e6 * (t - tv->tv_sec);
64  while (tv->tv_usec >= 1000000)
65  {
66  tv->tv_usec -= 1000000;
67  tv->tv_sec += 1;
68  }
69 }
70 
71 /* Sort timers so that timer soonest to expire is at end. */
72 static int
73 timer_compare (const void *_a, const void *_b)
74 {
75  const timer_callback_t *a = _a;
76  const timer_callback_t *b = _b;
77  f64 dt = b->time - a->time;
78  return dt < 0 ? -1 : (dt > 0 ? +1 : 0);
79 }
80 
81 static inline void
83 {
84  qsort (timers, vec_len (timers), sizeof (timers[0]), timer_compare);
85 }
86 
87 #define TIMER_SIGNAL SIGALRM
88 
89 /* Don't bother set timer if time different is less than this value. */
90 /* We would like to initialize this to 0.75 / (f64) HZ,
91  * but HZ may not be a compile-time constant on some systems,
92  * so instead we do the initialization before first use.
93  */
95 
96 /* Interrupt handler. Call functions for all expired timers.
97  Set time for next timer interrupt. */
98 static void
99 timer_interrupt (int signum)
100 {
101  f64 now = unix_time_now ();
102  f64 dt;
103  timer_callback_t *t;
104 
105  while (1)
106  {
107  if (vec_len (timers) <= 0)
108  return;
109 
110  /* Consider last (earliest) timer in reverse sorted
111  vector of pending timers. */
112  t = vec_end (timers) - 1;
113 
114  ASSERT (now >= 0 && finite (now));
115 
116  /* Time difference between when timer goes off and now. */
117  dt = t->time - now;
118 
119  /* If timer is within threshold of going off
120  call user's callback. */
121  if (dt <= time_resolution && finite (dt))
122  {
123  _vec_len (timers) -= 1;
124  (*t->func) (t->arg, -dt);
125  }
126  else
127  {
128  /* Set timer for to go off in future. */
129  struct itimerval itv;
130  memset (&itv, 0, sizeof (itv));
131  f64_to_tv (dt, &itv.it_value);
132  if (setitimer (ITIMER_REAL, &itv, 0) < 0)
133  clib_unix_error ("sititmer");
134  return;
135  }
136  }
137 }
138 
139 void
140 timer_block (sigset_t * save)
141 {
142  sigset_t block_timer;
143 
144  memset (&block_timer, 0, sizeof (block_timer));
145  sigaddset (&block_timer, TIMER_SIGNAL);
146  sigprocmask (SIG_BLOCK, &block_timer, save);
147 }
148 
149 void
150 timer_unblock (sigset_t * save)
151 {
152  sigprocmask (SIG_SETMASK, save, 0);
153 }
154 
155 /* Arrange for function to be called some time,
156  roughly equal to dt seconds, in the future. */
157 void
158 timer_call (timer_func_t * func, any arg, f64 dt)
159 {
160  timer_callback_t *t;
161  sigset_t save;
162 
163  /* Install signal handler on first call. */
164  static word signal_installed = 0;
165 
166  if (!signal_installed)
167  {
168  struct sigaction sa;
169 
170  /* Initialize time_resolution before first call to timer_interrupt */
171  time_resolution = 0.75 / (f64) HZ;
172 
173  memset (&sa, 0, sizeof (sa));
174  sa.sa_handler = timer_interrupt;
175 
176  if (sigaction (TIMER_SIGNAL, &sa, 0) < 0)
177  clib_panic ("sigaction");
178 
179  signal_installed = 1;
180  }
181 
182  timer_block (&save);
183 
184  /* Add new timer. */
185  vec_add2 (timers, t, 1);
186 
187  t->time = unix_time_now () + dt;
188  t->func = func;
189  t->arg = arg;
190 
191  {
192  word reset_timer = vec_len (timers) == 1;
193 
194  if (_vec_len (timers) > 1)
195  {
196  reset_timer += t->time < (t - 1)->time;
197  sort_timers (timers);
198  }
199 
200  if (reset_timer)
202  }
203 
204  timer_unblock (&save);
205 }
206 
207 #ifdef TEST
208 
209 #include <vppinfra/random.h>
210 
211 /* Compute average delay of function calls to foo.
212  If this is a small number over a lot of iterations we know
213  the code is working. */
214 
215 static f64 ave_delay = 0;
216 static word ave_delay_count = 0;
217 
219 update (f64 delay)
220 {
221  ave_delay += delay;
222  ave_delay_count += 1;
223 }
224 
225 typedef struct
226 {
227  f64 time_requested, time_called;
228 } foo_t;
229 
230 static f64 foo_base_time = 0;
231 static foo_t *foos = 0;
232 
233 void
234 foo (any arg, f64 delay)
235 {
236  foos[arg].time_called = unix_time_now () - foo_base_time;
237  update (delay);
238 }
239 
240 typedef struct
241 {
242  word count;
243  word limit;
244 } bar_t;
245 
246 void
247 bar (any arg, f64 delay)
248 {
249  bar_t *b = (bar_t *) arg;
250 
251  fformat (stdout, "bar %d delay %g\n", b->count++, delay);
252 
253  update (delay);
254  if (b->count < b->limit)
255  timer_call (bar, arg, random_f64 ());
256 }
257 
258 int
259 main (int argc, char *argv[])
260 {
261  word i, n = atoi (argv[1]);
262  word run_foo = argc > 2;
263 bar_t b = { limit:10 };
264 
265  if (run_foo)
266  {
267  f64 time_limit;
268 
269  time_limit = atof (argv[2]);
270 
271  vec_resize (foos, n);
272  for (i = 0; i < n; i++)
273  {
274  foos[i].time_requested = time_limit * random_f64 ();
275  foos[i].time_called = 1e100;
276  }
277 
278  foo_base_time = unix_time_now ();
279  for (i = 0; i < n; i++)
280  timer_call (foo, i, foos[i].time_requested);
281  }
282  else
283  timer_call (bar, (any) & b, random_f64 ());
284 
285  while (vec_len (timers) > 0)
286  sched_yield ();
287 
288  if (vec_len (foos) > 0)
289  {
290  f64 min = 1e100, max = -min;
291  f64 ave = 0, rms = 0;
292 
293  for (i = 0; i < n; i++)
294  {
295  f64 dt = foos[i].time_requested - foos[i].time_called;
296  if (dt < min)
297  min = dt;
298  if (dt > max)
299  max = dt;
300  ave += dt;
301  rms += dt * dt;
302  }
303  ave /= n;
304  rms = sqrt (rms / n - ave * ave);
305  fformat (stdout, "error min %g max %g ave %g +- %g\n", min, max, ave,
306  rms);
307  }
308 
309  fformat (stdout, "%d function calls, ave. timer delay %g secs\n",
310  ave_delay_count, ave_delay / ave_delay_count);
311 
312  return 0;
313 }
314 #endif
315 
316 /*
317  * fd.io coding-style-patch-verification: ON
318  *
319  * Local Variables:
320  * eval: (c-set-style "gnu")
321  * End:
322  */
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:337
a
Definition: bitmap.h:516
void timer_unblock(sigset_t *save)
Definition: timer.c:150
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:561
#define clib_unix_error(format, args...)
Definition: error.h:65
static f64 time_resolution
Definition: timer.c:94
#define always_inline
Definition: clib.h:84
static timer_callback_t * timers
Definition: timer.c:56
static f64 unix_time_now(void)
Definition: time.h:227
#define vec_resize(V, N)
Resize a vector (no header, unspecified alignment) Add N elements to end of given vector V...
Definition: vec.h:241
#define vec_end(v)
End (last data address) of vector.
void timer_call(timer_func_t *func, any arg, f64 dt)
Definition: timer.c:158
static int timer_compare(const void *_a, const void *_b)
Definition: timer.c:73
#define TIMER_SIGNAL
Definition: timer.c:87
word any
Definition: types.h:139
word fformat(FILE *f, char *fmt,...)
Definition: format.c:453
static void timer_interrupt(int signum)
Definition: timer.c:99
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:60
static f64 random_f64(u32 *seed)
Generate f64 random number in the interval [0,1].
Definition: random.h:145
void( timer_func_t)(any arg, f64 delay)
Definition: timer.h:29
void timer_block(sigset_t *save)
Definition: timer.c:140
int main(int argc, char **argv)
Definition: persist.c:215
i64 word
Definition: types.h:111
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)
double f64
Definition: types.h:142
Linear Congruential Random Number Generator.
#define clib_panic(format, args...)
Definition: error.h:72
timer_func_t * func
Definition: timer.c:51
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".
static void sort_timers(timer_callback_t *timers)
Definition: timer.c:82