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 {
  50   f64 time;
  51   timer_func_t *func;
  52   any arg;
  53 } timer_callback_t;
  54
  55 /* Vector of currently unexpired timers. */
  56 static timer_callback_t *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
  82 sort_timers (timer_callback_t * timers)
  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  */
  94 static f64 time_resolution;
  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)
 201       timer_interrupt (TIMER_SIGNAL);
 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
 218 always_inline
 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  */