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