src/vppinfra/timer.c

   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 {
  55   f64 time;
  56   timer_func_t *func;
  57   any arg;
  58 } timer_callback_t;
  59
  60 /* Vector of currently unexpired timers. */
  61 static timer_callback_t *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
  87 sort_timers (timer_callback_t * timers)
  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  */
  99 static f64 time_resolution;
 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)
 206       timer_interrupt (TIMER_SIGNAL);
 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
 223 always_inline
 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  */