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