src/vppinfra/test_timing_wheel.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 #include <vppinfra/bitmap.h>
  16 #include <vppinfra/error.h>
  17 #include <vppinfra/format.h>
  18 #include <vppinfra/pool.h>
  19 #include <vppinfra/random.h>
  20 #include <vppinfra/time.h>
  21 #include <vppinfra/timing_wheel.h>
  22 #include <vppinfra/zvec.h>
  23
  24 #include <vppinfra/math.h>
  25
  26 #if __GNUC__ < 4
  27 #define SQRT(a) a
  28 #else
  29 #define SQRT(a) sqrt(a)
  30 #endif
  31
  32 typedef struct
  33 {
  34   uword n_iter;
  35
  36   u32 n_events;
  37   u32 seed;
  38   u32 verbose;
  39
  40   /* Time is "synthetic" e.g. not taken from CPU timer. */
  41   u32 synthetic_time;
  42
  43   clib_time_t time;
  44   timing_wheel_t timing_wheel;
  45
  46   u64 *events;
  47
  48   f64 max_time;
  49   f64 wait_time;
  50
  51   f64 total_iterate_time;
  52   f64 time_iterate_start;
  53
  54   f64 time_per_status_update;
  55   f64 time_next_status_update;
  56 } test_timing_wheel_main_t;
  57
  58 typedef struct
  59 {
  60   f64 dt;
  61   f64 fraction;
  62   u64 count;
  63 } test_timing_wheel_tmp_t;
  64
  65 static void
  66 set_event (test_timing_wheel_main_t * tm, uword i)
  67 {
  68   timing_wheel_t *w = &tm->timing_wheel;
  69   u64 cpu_time;
  70
  71   cpu_time = w->current_time_index << w->log2_clocks_per_bin;
  72   if (tm->synthetic_time)
  73     cpu_time += random_u32 (&tm->seed) % tm->n_iter;
  74   else
  75     cpu_time +=
  76       random_f64 (&tm->seed) * tm->max_time * tm->time.clocks_per_second;
  77
  78   timing_wheel_insert (w, cpu_time, i);
  79   timing_wheel_validate (w);
  80   tm->events[i] = cpu_time;
  81 }
  82
  83 static int
  84 test_timing_wheel_tmp_cmp (void *a1, void *a2)
  85 {
  86   test_timing_wheel_tmp_t *f1 = a1;
  87   test_timing_wheel_tmp_t *f2 = a2;
  88
  89   return f1->dt < f2->dt ? -1 : (f1->dt > f2->dt ? +1 : 0);
  90 }
  91
  92 clib_error_t *
  93 test_timing_wheel_main (unformat_input_t * input)
  94 {
  95   clib_error_t *error = 0;
  96   test_timing_wheel_main_t _tm, *tm = &_tm;
  97   timing_wheel_t *w = &tm->timing_wheel;
  98   uword iter, i;
  99
 100   memset (tm, 0, sizeof (tm[0]));
 101   tm->n_iter = 10;
 102   tm->time_per_status_update = 0;
 103   tm->n_events = 100;
 104   tm->seed = 1;
 105   tm->synthetic_time = 1;
 106   tm->max_time = 1;
 107   tm->wait_time = 1e-3;
 108
 109   w->validate = 0;
 110   w->n_wheel_elt_time_bits = 32;
 111
 112   while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
 113     {
 114       if (unformat (input, "iter %wd", &tm->n_iter))
 115         ;
 116       else if (unformat (input, "events %d", &tm->n_events))
 117         ;
 118       else
 119         if (unformat (input, "elt-time-bits %d", &w->n_wheel_elt_time_bits))
 120         ;
 121       else if (unformat (input, "seed %d", &tm->seed))
 122         ;
 123       else if (unformat (input, "verbose"))
 124         tm->verbose = 1;
 125       else if (unformat (input, "validate"))
 126         w->validate = 1;
 127
 128       else if (unformat (input, "real-time"))
 129         tm->synthetic_time = 0;
 130       else if (unformat (input, "synthetic-time"))
 131         tm->synthetic_time = 1;
 132       else if (unformat (input, "max-time %f", &tm->max_time))
 133         ;
 134       else if (unformat (input, "wait-time %f", &tm->wait_time))
 135         ;
 136       else if (unformat (input, "iter-time %f", &tm->total_iterate_time))
 137         ;
 138       else if (unformat (input, "print %f", &tm->time_per_status_update))
 139         ;
 140
 141       else
 142         {
 143           error = clib_error_create ("unknown input `%U'\n",
 144                                      format_unformat_error, input);
 145           goto done;
 146         }
 147     }
 148
 149   if (!tm->seed)
 150     tm->seed = random_default_seed ();
 151
 152   clib_time_init (&tm->time);
 153
 154   if (tm->synthetic_time)
 155     {
 156       w->min_sched_time = tm->time.seconds_per_clock;
 157       w->max_sched_time = w->min_sched_time * 256;
 158       timing_wheel_init (w, 0, tm->time.clocks_per_second);
 159     }
 160   else
 161     {
 162       timing_wheel_init (w, clib_cpu_time_now (), tm->time.clocks_per_second);
 163     }
 164
 165   clib_warning ("iter %wd, events %d, seed %u, %U",
 166                 tm->n_iter, tm->n_events, tm->seed,
 167                 format_timing_wheel, &tm->timing_wheel, /* verbose */ 0);
 168
 169   /* Make some events. */
 170   vec_resize (tm->events, tm->n_events);
 171   for (i = 0; i < vec_len (tm->events); i++)
 172     set_event (tm, i);
 173
 174   {
 175     u32 *expired = 0;
 176     f64 ave_error = 0;
 177     f64 rms_error = 0;
 178     f64 max_error = 0, min_error = 1e30;
 179     u32 *error_hist = 0;
 180     uword n_expired = 0;
 181     uword *expired_bitmap[2] = { 0 };
 182     uword n_events_in_wheel = vec_len (tm->events);
 183
 184     vec_resize (expired, 32);
 185     vec_resize (error_hist, 1024);
 186
 187     tm->time_iterate_start = clib_time_now (&tm->time);
 188     tm->time_next_status_update =
 189       tm->time_iterate_start + tm->time_per_status_update;
 190
 191     if (tm->total_iterate_time != 0)
 192       tm->n_iter = ~0;
 193
 194     for (iter = 0; iter < tm->n_iter || n_events_in_wheel > 0; iter++)
 195       {
 196         u64 cpu_time, min_next_time[2];
 197
 198         if (tm->synthetic_time)
 199           cpu_time = iter << w->log2_clocks_per_bin;
 200         else
 201           cpu_time = clib_cpu_time_now ();
 202
 203         _vec_len (expired) = 0;
 204         expired =
 205           timing_wheel_advance (w, cpu_time, expired, &min_next_time[0]);
 206         timing_wheel_validate (w);
 207
 208         /* Update bitmap of expired events. */
 209         if (w->validate)
 210           {
 211             for (i = 0; i < vec_len (tm->events); i++)
 212               {
 213                 uword is_expired;
 214
 215                 is_expired =
 216                   (cpu_time >> w->log2_clocks_per_bin) >=
 217                   (tm->events[i] >> w->log2_clocks_per_bin);
 218                 expired_bitmap[0] =
 219                   clib_bitmap_set (expired_bitmap[0], i, is_expired);
 220
 221                 /* Validate min next time. */
 222                 if (is_expired)
 223                   ASSERT (min_next_time[0] > tm->events[i]);
 224                 else
 225                   ASSERT (min_next_time[0] <= tm->events[i]);
 226               }
 227           }
 228
 229         n_expired += vec_len (expired);
 230         for (i = 0; i < vec_len (expired); i++)
 231           {
 232             word j, idt;
 233             i64 dt_cpu;
 234             f64 fdt_cpu;
 235
 236             j = expired[i];
 237             expired_bitmap[1] = clib_bitmap_ori (expired_bitmap[1], j);
 238
 239             dt_cpu = cpu_time - tm->events[j];
 240
 241             /* Event must be scheduled in correct bin. */
 242             if (tm->synthetic_time)
 243               ASSERT (dt_cpu >= 0 && dt_cpu <= (1 << w->log2_clocks_per_bin));
 244
 245             fdt_cpu = dt_cpu * tm->time.seconds_per_clock;
 246
 247             ave_error += fdt_cpu;
 248             rms_error += fdt_cpu * fdt_cpu;
 249
 250             if (fdt_cpu > max_error)
 251               max_error = fdt_cpu;
 252             if (fdt_cpu < min_error)
 253               min_error = fdt_cpu;
 254
 255             idt =
 256               (cpu_time >> w->log2_clocks_per_bin) -
 257               (tm->events[j] >> w->log2_clocks_per_bin);
 258             idt = zvec_signed_to_unsigned (idt);
 259             vec_validate (error_hist, idt);
 260             error_hist[idt] += 1;
 261           }
 262
 263         if (w->validate)
 264           for (i = 0; i < vec_len (tm->events); i++)
 265             {
 266               int is_expired = clib_bitmap_get (expired_bitmap[0], i);
 267               int is_expired_w = clib_bitmap_get (expired_bitmap[1], i);
 268               ASSERT (is_expired == is_expired_w);
 269             }
 270
 271         min_next_time[1] = ~0;
 272         for (i = 0; i < vec_len (tm->events); i++)
 273           {
 274             if (!clib_bitmap_get (expired_bitmap[1], i))
 275               min_next_time[1] = clib_min (min_next_time[1], tm->events[i]);
 276           }
 277         if (min_next_time[0] != min_next_time[1])
 278           clib_error ("min next time wrong 0x%Lx != 0x%Lx", min_next_time[0],
 279                       min_next_time[1]);
 280
 281         if (tm->time_per_status_update != 0
 282             && clib_time_now (&tm->time) >= tm->time_next_status_update)
 283           {
 284             f64 ave = 0, rms = 0;
 285
 286             tm->time_next_status_update += tm->time_per_status_update;
 287             if (n_expired > 0)
 288               {
 289                 ave = ave_error / n_expired;
 290                 rms = SQRT (rms_error / n_expired - ave * ave);
 291               }
 292
 293             clib_warning
 294               ("%12wd iter done %10wd expired; ave. error %.4e +- %.4e, range %.4e %.4e",
 295                iter, n_expired, ave, rms, min_error, max_error);
 296           }
 297
 298         if (tm->total_iterate_time != 0
 299             && (clib_time_now (&tm->time) - tm->time_iterate_start
 300                 >= tm->total_iterate_time))
 301           tm->n_iter = iter;
 302
 303         /* Add new events to wheel to replace expired ones. */
 304         n_events_in_wheel -= vec_len (expired);
 305         if (iter < tm->n_iter)
 306           {
 307             for (i = 0; i < vec_len (expired); i++)
 308               {
 309                 uword j = expired[i];
 310                 set_event (tm, j);
 311                 expired_bitmap[1] =
 312                   clib_bitmap_andnoti (expired_bitmap[1], j);
 313               }
 314             n_events_in_wheel += vec_len (expired);
 315           }
 316       }
 317
 318     ave_error /= n_expired;
 319     rms_error = SQRT (rms_error / n_expired - ave_error * ave_error);
 320
 321     clib_warning
 322       ("%wd iter done %wd expired; ave. error %.4e +- %.4e, range %.4e %.4e",
 323        1 + iter, n_expired, ave_error, rms_error, min_error, max_error);
 324
 325     {
 326       test_timing_wheel_tmp_t *fs, *f;
 327       f64 total_fraction;
 328
 329       fs = 0;
 330       for (i = 0; i < vec_len (error_hist); i++)
 331         {
 332           if (error_hist[i] == 0)
 333             continue;
 334           vec_add2 (fs, f, 1);
 335           f->dt =
 336             (((i64) zvec_unsigned_to_signed (i) << w->log2_clocks_per_bin) *
 337              tm->time.seconds_per_clock);
 338           f->fraction = (f64) error_hist[i] / (f64) n_expired;
 339           f->count = error_hist[i];
 340         }
 341
 342       vec_sort_with_function (fs, test_timing_wheel_tmp_cmp);
 343
 344       total_fraction = 0;
 345       vec_foreach (f, fs)
 346       {
 347         total_fraction += f->fraction;
 348         if (f == fs)
 349           fformat (stdout, "%=12s %=16s %=16s %s\n", "Error max", "Fraction",
 350                    "Total", "Count");
 351         fformat (stdout, "%12.4e %16.4f%% %16.4f%% %Ld\n", f->dt,
 352                  f->fraction * 100, total_fraction * 100, f->count);
 353       }
 354     }
 355
 356     clib_warning ("%U", format_timing_wheel, w, /* verbose */ 1);
 357   }
 358
 359 done:
 360   return error;
 361 }
 362
 363 #ifdef CLIB_UNIX
 364 int
 365 main (int argc, char *argv[])
 366 {
 367   unformat_input_t i;
 368   clib_error_t *error;
 369
 370   clib_mem_init (0, 64ULL << 20);
 371
 372   unformat_init_command_line (&i, argv);
 373   error = test_timing_wheel_main (&i);
 374   unformat_free (&i);
 375   if (error)
 376     {
 377       clib_error_report (error);
 378       return 1;
 379     }
 380   else
 381     return 0;
 382 }
 383 #endif /* CLIB_UNIX */
 384
 385 /*
 386  * fd.io coding-style-patch-verification: ON
 387  *
 388  * Local Variables:
 389  * eval: (c-set-style "gnu")
 390  * End:
 391  */