src/vppinfra/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/hash.h>
  17 #include <vppinfra/pool.h>
  18 #include <vppinfra/timing_wheel.h>
  19
  20 void
  21 timing_wheel_init (timing_wheel_t * w, u64 current_cpu_time,
  22                    f64 cpu_clocks_per_second)
  23 {
  24   if (w->max_sched_time <= w->min_sched_time)
  25     {
  26       w->min_sched_time = 1e-6;
  27       w->max_sched_time = 1e-3;
  28     }
  29
  30   w->cpu_clocks_per_second = cpu_clocks_per_second;
  31   w->log2_clocks_per_bin =
  32     max_log2 (w->cpu_clocks_per_second * w->min_sched_time);
  33   w->log2_bins_per_wheel =
  34     max_log2 (w->cpu_clocks_per_second * w->max_sched_time);
  35   w->log2_bins_per_wheel -= w->log2_clocks_per_bin;
  36   w->log2_clocks_per_wheel = w->log2_bins_per_wheel + w->log2_clocks_per_bin;
  37   w->bins_per_wheel = 1 << w->log2_bins_per_wheel;
  38   w->bins_per_wheel_mask = w->bins_per_wheel - 1;
  39
  40   w->current_time_index = current_cpu_time >> w->log2_clocks_per_bin;
  41
  42   if (w->n_wheel_elt_time_bits <= 0 ||
  43       w->n_wheel_elt_time_bits >= STRUCT_BITS_OF (timing_wheel_elt_t,
  44                                                   cpu_time_relative_to_base))
  45     w->n_wheel_elt_time_bits =
  46       STRUCT_BITS_OF (timing_wheel_elt_t, cpu_time_relative_to_base) - 1;
  47
  48   w->cpu_time_base = current_cpu_time;
  49   w->time_index_next_cpu_time_base_update
  50     =
  51     w->current_time_index +
  52     ((u64) 1 << (w->n_wheel_elt_time_bits - w->log2_clocks_per_bin));
  53 }
  54
  55 always_inline uword
  56 get_level_and_relative_time (timing_wheel_t * w, u64 cpu_time,
  57                              uword * rtime_result)
  58 {
  59   u64 dt, rtime;
  60   uword level_index;
  61
  62   dt = (cpu_time >> w->log2_clocks_per_bin);
  63
  64   /* Time should always move forward. */
  65   ASSERT (dt >= w->current_time_index);
  66
  67   dt -= w->current_time_index;
  68
  69   /* Find level and offset within level.  Level i has bins of size 2^((i+1)*M) */
  70   rtime = dt;
  71   for (level_index = 0; (rtime >> w->log2_bins_per_wheel) != 0; level_index++)
  72     rtime = (rtime >> w->log2_bins_per_wheel) - 1;
  73
  74   /* Return offset within level and level index. */
  75   ASSERT (rtime < w->bins_per_wheel);
  76   *rtime_result = rtime;
  77   return level_index;
  78 }
  79
  80 always_inline uword
  81 time_index_to_wheel_index (timing_wheel_t * w, uword level_index, u64 ti)
  82 {
  83   return (ti >> (level_index * w->log2_bins_per_wheel)) &
  84     w->bins_per_wheel_mask;
  85 }
  86
  87 /* Find current time on this level. */
  88 always_inline uword
  89 current_time_wheel_index (timing_wheel_t * w, uword level_index)
  90 {
  91   return time_index_to_wheel_index (w, level_index, w->current_time_index);
  92 }
  93
  94 /* Circular wheel indexing. */
  95 always_inline uword
  96 wheel_add (timing_wheel_t * w, word x)
  97 {
  98   return x & w->bins_per_wheel_mask;
  99 }
 100
 101 always_inline uword
 102 rtime_to_wheel_index (timing_wheel_t * w, uword level_index, uword rtime)
 103 {
 104   uword t = current_time_wheel_index (w, level_index);
 105   return wheel_add (w, t + rtime);
 106 }
 107
 108 static clib_error_t *
 109 validate_level (timing_wheel_t * w, uword level_index, uword * n_elts)
 110 {
 111   timing_wheel_level_t *level;
 112   timing_wheel_elt_t *e;
 113   uword wi;
 114   clib_error_t *error = 0;
 115
 116 #define _(x)                                    \
 117   do {                                          \
 118     error = CLIB_ERROR_ASSERT (x);              \
 119     ASSERT (! error);                           \
 120     if (error) return error;                    \
 121   } while (0)
 122
 123   level = vec_elt_at_index (w->levels, level_index);
 124   for (wi = 0; wi < vec_len (level->elts); wi++)
 125     {
 126       /* Validate occupancy bitmap. */
 127       _(clib_bitmap_get_no_check (level->occupancy_bitmap, wi) ==
 128         (vec_len (level->elts[wi]) > 0));
 129
 130       *n_elts += vec_len (level->elts[wi]);
 131
 132       vec_foreach (e, level->elts[wi])
 133       {
 134         /* Validate time bin and level. */
 135         u64 e_time;
 136         uword e_ti, e_li, e_wi;
 137
 138         e_time = e->cpu_time_relative_to_base + w->cpu_time_base;
 139         e_li = get_level_and_relative_time (w, e_time, &e_ti);
 140         e_wi = rtime_to_wheel_index (w, level_index, e_ti);
 141
 142         if (e_li == level_index - 1)
 143           /* If this element was scheduled on the previous level
 144              it must be wrapped. */
 145           _(e_ti + current_time_wheel_index (w, level_index - 1)
 146             >= w->bins_per_wheel);
 147         else
 148           {
 149             _(e_li == level_index);
 150             if (e_li == 0)
 151               _(e_wi == wi);
 152             else
 153               _(e_wi == wi || e_wi + 1 == wi || e_wi - 1 == wi);
 154           }
 155       }
 156     }
 157
 158 #undef _
 159
 160   return error;
 161 }
 162
 163 void
 164 timing_wheel_validate (timing_wheel_t * w)
 165 {
 166   uword l;
 167   clib_error_t *error = 0;
 168   uword n_elts;
 169
 170   if (!w->validate)
 171     return;
 172
 173   n_elts = pool_elts (w->overflow_pool);
 174   for (l = 0; l < vec_len (w->levels); l++)
 175     {
 176       error = validate_level (w, l, &n_elts);
 177       if (error)
 178         clib_error_report (error);
 179     }
 180 }
 181
 182 always_inline void
 183 free_elt_vector (timing_wheel_t * w, timing_wheel_elt_t * ev)
 184 {
 185   /* Poison free elements so we never use them by mistake. */
 186   if (CLIB_DEBUG > 0)
 187     clib_memset (ev, ~0, vec_len (ev) * sizeof (ev[0]));
 188   vec_set_len (ev, 0);
 189   vec_add1 (w->free_elt_vectors, ev);
 190 }
 191
 192 static timing_wheel_elt_t *
 193 insert_helper (timing_wheel_t * w, uword level_index, uword rtime)
 194 {
 195   timing_wheel_level_t *level;
 196   timing_wheel_elt_t *e;
 197   uword wheel_index;
 198
 199   /* Circular buffer. */
 200   vec_validate (w->levels, level_index);
 201   level = vec_elt_at_index (w->levels, level_index);
 202
 203   if (PREDICT_FALSE (!level->elts))
 204     {
 205       uword max = w->bins_per_wheel - 1;
 206       clib_bitmap_validate (level->occupancy_bitmap, max);
 207       vec_validate (level->elts, max);
 208     }
 209
 210   wheel_index = rtime_to_wheel_index (w, level_index, rtime);
 211
 212   level->occupancy_bitmap =
 213     clib_bitmap_ori (level->occupancy_bitmap, wheel_index);
 214
 215   /* Allocate an elt vector from free list if there is one. */
 216   if (!level->elts[wheel_index] && vec_len (w->free_elt_vectors))
 217     level->elts[wheel_index] = vec_pop (w->free_elt_vectors);
 218
 219   /* Add element to vector for this time bin. */
 220   vec_add2 (level->elts[wheel_index], e, 1);
 221
 222   return e;
 223 }
 224
 225 /* Insert user data on wheel at given CPU time stamp. */
 226 static void
 227 timing_wheel_insert_helper (timing_wheel_t * w, u64 insert_cpu_time,
 228                             u32 user_data)
 229 {
 230   timing_wheel_elt_t *e;
 231   u64 dt;
 232   uword rtime, level_index;
 233
 234   level_index = get_level_and_relative_time (w, insert_cpu_time, &rtime);
 235
 236   dt = insert_cpu_time - w->cpu_time_base;
 237   if (PREDICT_TRUE (0 == (dt >> BITS (e->cpu_time_relative_to_base))))
 238     {
 239       e = insert_helper (w, level_index, rtime);
 240       e->user_data = user_data;
 241       e->cpu_time_relative_to_base = dt;
 242       if (insert_cpu_time < w->cached_min_cpu_time_on_wheel)
 243         w->cached_min_cpu_time_on_wheel = insert_cpu_time;
 244     }
 245   else
 246     {
 247       /* Time too far in the future: add to overflow vector. */
 248       timing_wheel_overflow_elt_t *oe;
 249       pool_get (w->overflow_pool, oe);
 250       oe->user_data = user_data;
 251       oe->cpu_time = insert_cpu_time;
 252     }
 253 }
 254
 255 always_inline uword
 256 elt_is_deleted (timing_wheel_t * w, u32 user_data)
 257 {
 258   return (hash_elts (w->deleted_user_data_hash) > 0
 259           && hash_get (w->deleted_user_data_hash, user_data));
 260 }
 261
 262 static timing_wheel_elt_t *
 263 delete_user_data (timing_wheel_elt_t * elts, u32 user_data)
 264 {
 265   uword found_match;
 266   timing_wheel_elt_t *e, *new_elts;
 267
 268   /* Quickly scan to see if there are any elements to delete
 269      in this bucket. */
 270   found_match = 0;
 271   vec_foreach (e, elts)
 272   {
 273     found_match = e->user_data == user_data;
 274     if (found_match)
 275       break;
 276   }
 277   if (!found_match)
 278     return elts;
 279
 280   /* Re-scan to build vector of new elts with matching user_data deleted. */
 281   new_elts = 0;
 282   vec_foreach (e, elts)
 283   {
 284     if (e->user_data != user_data)
 285       vec_add1 (new_elts, e[0]);
 286   }
 287
 288   vec_free (elts);
 289   return new_elts;
 290 }
 291
 292 /* Insert user data on wheel at given CPU time stamp. */
 293 void
 294 timing_wheel_insert (timing_wheel_t * w, u64 insert_cpu_time, u32 user_data)
 295 {
 296   /* Remove previously deleted elements. */
 297   if (elt_is_deleted (w, user_data))
 298     {
 299       timing_wheel_level_t *l;
 300       uword wi;
 301
 302       /* Delete elts with given user data so that stale events don't expire. */
 303       vec_foreach (l, w->levels)
 304       {
 305           clib_bitmap_foreach (wi, l->occupancy_bitmap)  {
 306             l->elts[wi] = delete_user_data (l->elts[wi], user_data);
 307             if (vec_len (l->elts[wi]) == 0)
 308               l->occupancy_bitmap = clib_bitmap_andnoti (l->occupancy_bitmap, wi);
 309           }
 310       }
 311
 312       {
 313         timing_wheel_overflow_elt_t *oe;
 314         pool_foreach (oe, w->overflow_pool)  {
 315           if (oe->user_data == user_data)
 316             pool_put (w->overflow_pool, oe);
 317         }
 318       }
 319
 320       hash_unset (w->deleted_user_data_hash, user_data);
 321     }
 322
 323   timing_wheel_insert_helper (w, insert_cpu_time, user_data);
 324 }
 325
 326 void
 327 timing_wheel_delete (timing_wheel_t * w, u32 user_data)
 328 {
 329   if (!w->deleted_user_data_hash)
 330     w->deleted_user_data_hash =
 331       hash_create ( /* capacity */ 0, /* value bytes */ 0);
 332
 333   hash_set1 (w->deleted_user_data_hash, user_data);
 334 }
 335
 336 /* Returns time of next expiring element. */
 337 u64
 338 timing_wheel_next_expiring_elt_time (timing_wheel_t * w)
 339 {
 340   timing_wheel_level_t *l;
 341   timing_wheel_elt_t *e;
 342   uword li, wi, wi0;
 343   u32 min_dt;
 344   u64 min_t;
 345   uword wrapped = 0;
 346
 347   min_dt = ~0;
 348   min_t = ~0ULL;
 349   vec_foreach (l, w->levels)
 350   {
 351     if (!l->occupancy_bitmap)
 352       continue;
 353
 354     li = l - w->levels;
 355     wi0 = wi = current_time_wheel_index (w, li);
 356     wrapped = 0;
 357     while (1)
 358       {
 359         if (clib_bitmap_get_no_check (l->occupancy_bitmap, wi))
 360           {
 361             vec_foreach (e, l->elts[wi])
 362               min_dt = clib_min (min_dt, e->cpu_time_relative_to_base);
 363
 364             if (wrapped && li + 1 < vec_len (w->levels))
 365               {
 366                 uword wi1 = current_time_wheel_index (w, li + 1);
 367                 if (l[1].occupancy_bitmap
 368                     && clib_bitmap_get_no_check (l[1].occupancy_bitmap, wi1))
 369                   {
 370                     vec_foreach (e, l[1].elts[wi1])
 371                     {
 372                       min_dt =
 373                         clib_min (min_dt, e->cpu_time_relative_to_base);
 374                     }
 375                   }
 376               }
 377
 378             min_t = w->cpu_time_base + min_dt;
 379             goto done;
 380           }
 381
 382         wi = wheel_add (w, wi + 1);
 383         if (wi == wi0)
 384           break;
 385
 386         wrapped = wi != wi + 1;
 387       }
 388   }
 389
 390   {
 391     timing_wheel_overflow_elt_t *oe;
 392
 393     if (min_dt != ~0)
 394       min_t = w->cpu_time_base + min_dt;
 395
 396     pool_foreach (oe, w->overflow_pool)
 397                    { min_t = clib_min (min_t, oe->cpu_time); }
 398
 399   done:
 400     return min_t;
 401   }
 402 }
 403
 404 static inline void
 405 insert_elt (timing_wheel_t * w, timing_wheel_elt_t * e)
 406 {
 407   u64 t = w->cpu_time_base + e->cpu_time_relative_to_base;
 408   timing_wheel_insert_helper (w, t, e->user_data);
 409 }
 410
 411 always_inline u64
 412 elt_cpu_time (timing_wheel_t * w, timing_wheel_elt_t * e)
 413 {
 414   return w->cpu_time_base + e->cpu_time_relative_to_base;
 415 }
 416
 417 always_inline void
 418 validate_expired_elt (timing_wheel_t * w, timing_wheel_elt_t * e,
 419                       u64 current_cpu_time)
 420 {
 421   if (CLIB_DEBUG > 0)
 422     {
 423       u64 e_time = elt_cpu_time (w, e);
 424
 425       /* Verify that element is actually expired. */
 426       ASSERT ((e_time >> w->log2_clocks_per_bin)
 427               <= (current_cpu_time >> w->log2_clocks_per_bin));
 428     }
 429 }
 430
 431 static u32 *
 432 expire_bin (timing_wheel_t * w,
 433             uword level_index,
 434             uword wheel_index, u64 advance_cpu_time, u32 * expired_user_data)
 435 {
 436   timing_wheel_level_t *level = vec_elt_at_index (w->levels, level_index);
 437   timing_wheel_elt_t *e;
 438   u32 *x;
 439   uword i, j, e_len;
 440
 441   e = vec_elt (level->elts, wheel_index);
 442   e_len = vec_len (e);
 443
 444   vec_add2 (expired_user_data, x, e_len);
 445   for (i = j = 0; i < e_len; i++)
 446     {
 447       validate_expired_elt (w, &e[i], advance_cpu_time);
 448       x[j] = e[i].user_data;
 449
 450       /* Only advance if elt is not to be deleted. */
 451       j += !elt_is_deleted (w, e[i].user_data);
 452     }
 453
 454   /* Adjust for deleted elts. */
 455   if (j < e_len)
 456     vec_dec_len (expired_user_data, e_len - j);
 457
 458   free_elt_vector (w, e);
 459
 460   level->elts[wheel_index] = 0;
 461   clib_bitmap_set_no_check (level->occupancy_bitmap, wheel_index, 0);
 462
 463   return expired_user_data;
 464 }
 465
 466 /* Called rarely. 32 bit times should only overflow every 4 seconds or so on a fast machine. */
 467 static u32 *
 468 advance_cpu_time_base (timing_wheel_t * w, u32 * expired_user_data)
 469 {
 470   timing_wheel_level_t *l;
 471   timing_wheel_elt_t *e;
 472   u64 delta;
 473
 474   w->stats.cpu_time_base_advances++;
 475   delta = ((u64) 1 << w->n_wheel_elt_time_bits);
 476   w->cpu_time_base += delta;
 477   w->time_index_next_cpu_time_base_update += delta >> w->log2_clocks_per_bin;
 478
 479   vec_foreach (l, w->levels)
 480   {
 481     uword wi;
 482       clib_bitmap_foreach (wi, l->occupancy_bitmap)  {
 483         vec_foreach (e, l->elts[wi])
 484           {
 485             /* This should always be true since otherwise we would have already expired
 486                this element. Note that in the second half of this function we need
 487                to take care not to place the expired elements ourselves. */
 488             ASSERT (e->cpu_time_relative_to_base >= delta);
 489             e->cpu_time_relative_to_base -= delta;
 490           }
 491       }
 492   }
 493
 494   /* See which overflow elements fit now. */
 495   {
 496     timing_wheel_overflow_elt_t *oe;
 497     pool_foreach (oe, w->overflow_pool)  {
 498       /* It fits now into 32 bits. */
 499       if (0 == ((oe->cpu_time - w->cpu_time_base) >> BITS (e->cpu_time_relative_to_base)))
 500         {
 501           u64 ti = oe->cpu_time >> w->log2_clocks_per_bin;
 502           if (ti <= w->current_time_index)
 503             {
 504               /* This can happen when timing wheel is not advanced for a long time
 505                  (for example when at a gdb breakpoint for a while). */
 506               /* Note: the ti == w->current_time_index means it is also an expired timer */
 507               if (! elt_is_deleted (w, oe->user_data))
 508                 vec_add1 (expired_user_data, oe->user_data);
 509             }
 510           else
 511             timing_wheel_insert_helper (w, oe->cpu_time, oe->user_data);
 512           pool_put (w->overflow_pool, oe);
 513         }
 514     }
 515   }
 516   return expired_user_data;
 517 }
 518
 519 static u32 *
 520 refill_level (timing_wheel_t * w,
 521               uword level_index,
 522               u64 advance_cpu_time,
 523               uword from_wheel_index,
 524               uword to_wheel_index, u32 * expired_user_data)
 525 {
 526   timing_wheel_level_t *level;
 527   timing_wheel_elt_t *to_insert = w->unexpired_elts_pending_insert;
 528   u64 advance_time_index = advance_cpu_time >> w->log2_clocks_per_bin;
 529
 530   vec_validate (w->stats.refills, level_index);
 531   w->stats.refills[level_index] += 1;
 532
 533   if (level_index + 1 >= vec_len (w->levels))
 534     goto done;
 535
 536   level = vec_elt_at_index (w->levels, level_index + 1);
 537   if (!level->occupancy_bitmap)
 538     goto done;
 539
 540   while (1)
 541     {
 542       timing_wheel_elt_t *e, *es;
 543
 544       if (clib_bitmap_get_no_check
 545           (level->occupancy_bitmap, from_wheel_index))
 546         {
 547           es = level->elts[from_wheel_index];
 548           level->elts[from_wheel_index] = 0;
 549           clib_bitmap_set_no_check (level->occupancy_bitmap, from_wheel_index,
 550                                     0);
 551
 552           vec_foreach (e, es)
 553           {
 554             u64 e_time = elt_cpu_time (w, e);
 555             u64 ti = e_time >> w->log2_clocks_per_bin;
 556             if (ti <= advance_time_index)
 557               {
 558                 validate_expired_elt (w, e, advance_cpu_time);
 559                 if (!elt_is_deleted (w, e->user_data))
 560                   vec_add1 (expired_user_data, e->user_data);
 561               }
 562             else
 563               vec_add1 (to_insert, e[0]);
 564           }
 565           free_elt_vector (w, es);
 566         }
 567
 568       if (from_wheel_index == to_wheel_index)
 569         break;
 570
 571       from_wheel_index = wheel_add (w, from_wheel_index + 1);
 572     }
 573
 574   timing_wheel_validate (w);
 575 done:
 576   w->unexpired_elts_pending_insert = to_insert;
 577   return expired_user_data;
 578 }
 579
 580 /* Advance wheel and return any expired user data in vector. */
 581 u32 *
 582 timing_wheel_advance (timing_wheel_t * w, u64 advance_cpu_time,
 583                       u32 * expired_user_data,
 584                       u64 * next_expiring_element_cpu_time)
 585 {
 586   timing_wheel_level_t *level;
 587   uword level_index, advance_rtime, advance_level_index, advance_wheel_index;
 588   uword n_expired_user_data_before;
 589   u64 current_time_index, advance_time_index;
 590
 591   n_expired_user_data_before = vec_len (expired_user_data);
 592
 593   /* Re-fill lower levels when time wraps. */
 594   current_time_index = w->current_time_index;
 595   advance_time_index = advance_cpu_time >> w->log2_clocks_per_bin;
 596
 597   {
 598     u64 current_ti, advance_ti;
 599
 600     current_ti = current_time_index >> w->log2_bins_per_wheel;
 601     advance_ti = advance_time_index >> w->log2_bins_per_wheel;
 602
 603     if (PREDICT_FALSE (current_ti != advance_ti))
 604       {
 605         if (w->unexpired_elts_pending_insert)
 606           vec_set_len (w->unexpired_elts_pending_insert, 0);
 607
 608         level_index = 0;
 609         while (current_ti != advance_ti)
 610           {
 611             uword c, a;
 612             c = current_ti & (w->bins_per_wheel - 1);
 613             a = advance_ti & (w->bins_per_wheel - 1);
 614             if (c != a)
 615               expired_user_data = refill_level (w,
 616                                                 level_index,
 617                                                 advance_cpu_time,
 618                                                 c, a, expired_user_data);
 619             current_ti >>= w->log2_bins_per_wheel;
 620             advance_ti >>= w->log2_bins_per_wheel;
 621             level_index++;
 622           }
 623       }
 624   }
 625
 626   advance_level_index =
 627     get_level_and_relative_time (w, advance_cpu_time, &advance_rtime);
 628   advance_wheel_index =
 629     rtime_to_wheel_index (w, advance_level_index, advance_rtime);
 630
 631   /* Empty all occupied bins for entire levels that we advance past. */
 632   for (level_index = 0; level_index < advance_level_index; level_index++)
 633     {
 634       uword wi;
 635
 636       if (level_index >= vec_len (w->levels))
 637         break;
 638
 639       level = vec_elt_at_index (w->levels, level_index);
 640       clib_bitmap_foreach (wi, level->occupancy_bitmap)  {
 641         expired_user_data = expire_bin (w, level_index, wi, advance_cpu_time,
 642                                         expired_user_data);
 643       }
 644     }
 645
 646   if (PREDICT_TRUE (level_index < vec_len (w->levels)))
 647     {
 648       uword wi;
 649       level = vec_elt_at_index (w->levels, level_index);
 650       wi = current_time_wheel_index (w, level_index);
 651       if (level->occupancy_bitmap)
 652         while (1)
 653           {
 654             if (clib_bitmap_get_no_check (level->occupancy_bitmap, wi))
 655               expired_user_data =
 656                 expire_bin (w, advance_level_index, wi, advance_cpu_time,
 657                             expired_user_data);
 658
 659             /* When we jump out, we have already just expired the bin,
 660                corresponding to advance_wheel_index */
 661             if (wi == advance_wheel_index)
 662               break;
 663
 664             wi = wheel_add (w, wi + 1);
 665           }
 666     }
 667
 668   /* Advance current time index. */
 669   w->current_time_index = advance_time_index;
 670
 671   if (vec_len (w->unexpired_elts_pending_insert) > 0)
 672     {
 673       timing_wheel_elt_t *e;
 674       vec_foreach (e, w->unexpired_elts_pending_insert) insert_elt (w, e);
 675       vec_set_len (w->unexpired_elts_pending_insert, 0);
 676     }
 677
 678   /* Don't advance until necessary. */
 679   /* However, if the timing_wheel_advance() hasn't been called for some time,
 680      the while() loop will ensure multiple calls to advance_cpu_time_base()
 681      in a row until the w->cpu_time_base is fresh enough. */
 682   while (PREDICT_FALSE
 683          (advance_time_index >= w->time_index_next_cpu_time_base_update))
 684     expired_user_data = advance_cpu_time_base (w, expired_user_data);
 685
 686   if (next_expiring_element_cpu_time)
 687     {
 688       u64 min_t;
 689
 690       /* Anything expired?  If so we need to recompute next expiring elt time. */
 691       if (vec_len (expired_user_data) == n_expired_user_data_before
 692           && w->cached_min_cpu_time_on_wheel != 0ULL)
 693         min_t = w->cached_min_cpu_time_on_wheel;
 694       else
 695         {
 696           min_t = timing_wheel_next_expiring_elt_time (w);
 697           w->cached_min_cpu_time_on_wheel = min_t;
 698         }
 699
 700       *next_expiring_element_cpu_time = min_t;
 701     }
 702
 703   return expired_user_data;
 704 }
 705
 706 u8 *
 707 format_timing_wheel (u8 * s, va_list * va)
 708 {
 709   timing_wheel_t *w = va_arg (*va, timing_wheel_t *);
 710   int verbose = va_arg (*va, int);
 711   u32 indent = format_get_indent (s);
 712
 713   s = format (s, "level 0: %.4e - %.4e secs, 2^%d - 2^%d clocks",
 714               (f64) (1 << w->log2_clocks_per_bin) / w->cpu_clocks_per_second,
 715               (f64) (1 << w->log2_clocks_per_wheel) /
 716               w->cpu_clocks_per_second, w->log2_clocks_per_bin,
 717               w->log2_clocks_per_wheel);
 718
 719   if (verbose)
 720     {
 721       int l;
 722
 723       s = format (s, "\n%Utime base advances %Ld, every %.4e secs",
 724                   format_white_space, indent + 2,
 725                   w->stats.cpu_time_base_advances,
 726                   (f64) ((u64) 1 << w->n_wheel_elt_time_bits) /
 727                   w->cpu_clocks_per_second);
 728
 729       for (l = 0; l < vec_len (w->levels); l++)
 730         s = format (s, "\n%Ulevel %d: refills %Ld",
 731                     format_white_space, indent + 2,
 732                     l,
 733                     l <
 734                     vec_len (w->stats.refills) ? w->stats.
 735                     refills[l] : (u64) 0);
 736     }
 737
 738   return s;
 739 }
 740
 741 /*
 742  * fd.io coding-style-patch-verification: ON
 743  *
 744  * Local Variables:
 745  * eval: (c-set-style "gnu")
 746  * End:
 747  */