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