FD.io VPP  v21.06-3-gbb25fbf28
Vector Packet Processing
timing_wheel.c
Go to the documentation of this file.
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;
39 
40  w->current_time_index = current_cpu_time >> w->log2_clocks_per_bin;
41 
42  if (w->n_wheel_elt_time_bits <= 0 ||
44  cpu_time_relative_to_base))
46  STRUCT_BITS_OF (timing_wheel_elt_t, cpu_time_relative_to_base) - 1;
47 
48  w->cpu_time_base = current_cpu_time;
50  =
53 }
54 
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 
82 {
83  return (ti >> (level_index * w->log2_bins_per_wheel)) &
85 }
86 
87 /* Find current time on this level. */
90 {
91  return time_index_to_wheel_index (w, level_index, w->current_time_index);
92 }
93 
94 /* Circular wheel indexing. */
97 {
98  return x & w->bins_per_wheel_mask;
99 }
100 
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;
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. */
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
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)
179  }
180 }
181 
182 always_inline void
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_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;
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;
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
228  u32 user_data)
229 {
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;
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. */
249  pool_get (w->overflow_pool, oe);
250  oe->user_data = user_data;
251  oe->cpu_time = insert_cpu_time;
252  }
253 }
254 
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 *
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  {
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  /* *INDENT-OFF* */
307  l->elts[wi] = delete_user_data (l->elts[wi], user_data);
308  if (vec_len (l->elts[wi]) == 0)
309  l->occupancy_bitmap = clib_bitmap_andnoti (l->occupancy_bitmap, wi);
310  }
311  /* *INDENT-ON* */
312  }
313 
314  {
316  /* *INDENT-OFF* */
317  pool_foreach (oe, w->overflow_pool) {
318  if (oe->user_data == user_data)
319  pool_put (w->overflow_pool, oe);
320  }
321  /* *INDENT-ON* */
322  }
323 
324  hash_unset (w->deleted_user_data_hash, user_data);
325  }
326 
327  timing_wheel_insert_helper (w, insert_cpu_time, user_data);
328 }
329 
330 void
332 {
333  if (!w->deleted_user_data_hash)
335  hash_create ( /* capacity */ 0, /* value bytes */ 0);
336 
337  hash_set1 (w->deleted_user_data_hash, user_data);
338 }
339 
340 /* Returns time of next expiring element. */
341 u64
343 {
346  uword li, wi, wi0;
347  u32 min_dt;
348  u64 min_t;
349  uword wrapped = 0;
350 
351  min_dt = ~0;
352  min_t = ~0ULL;
353  vec_foreach (l, w->levels)
354  {
355  if (!l->occupancy_bitmap)
356  continue;
357 
358  li = l - w->levels;
359  wi0 = wi = current_time_wheel_index (w, li);
360  wrapped = 0;
361  while (1)
362  {
364  {
365  vec_foreach (e, l->elts[wi])
366  min_dt = clib_min (min_dt, e->cpu_time_relative_to_base);
367 
368  if (wrapped && li + 1 < vec_len (w->levels))
369  {
370  uword wi1 = current_time_wheel_index (w, li + 1);
371  if (l[1].occupancy_bitmap
372  && clib_bitmap_get_no_check (l[1].occupancy_bitmap, wi1))
373  {
374  vec_foreach (e, l[1].elts[wi1])
375  {
376  min_dt =
377  clib_min (min_dt, e->cpu_time_relative_to_base);
378  }
379  }
380  }
381 
382  min_t = w->cpu_time_base + min_dt;
383  goto done;
384  }
385 
386  wi = wheel_add (w, wi + 1);
387  if (wi == wi0)
388  break;
389 
390  wrapped = wi != wi + 1;
391  }
392  }
393 
394  {
396 
397  if (min_dt != ~0)
398  min_t = w->cpu_time_base + min_dt;
399 
400  /* *INDENT-OFF* */
401  pool_foreach (oe, w->overflow_pool)
402  { min_t = clib_min (min_t, oe->cpu_time); }
403  /* *INDENT-ON* */
404 
405  done:
406  return min_t;
407  }
408 }
409 
410 static inline void
412 {
415 }
416 
419 {
421 }
422 
423 always_inline void
425  u64 current_cpu_time)
426 {
427  if (CLIB_DEBUG > 0)
428  {
429  u64 e_time = elt_cpu_time (w, e);
430 
431  /* Verify that element is actually expired. */
432  ASSERT ((e_time >> w->log2_clocks_per_bin)
433  <= (current_cpu_time >> w->log2_clocks_per_bin));
434  }
435 }
436 
437 static u32 *
439  uword level_index,
440  uword wheel_index, u64 advance_cpu_time, u32 * expired_user_data)
441 {
442  timing_wheel_level_t *level = vec_elt_at_index (w->levels, level_index);
444  u32 *x;
445  uword i, j, e_len;
446 
447  e = vec_elt (level->elts, wheel_index);
448  e_len = vec_len (e);
449 
450  vec_add2 (expired_user_data, x, e_len);
451  for (i = j = 0; i < e_len; i++)
452  {
453  validate_expired_elt (w, &e[i], advance_cpu_time);
454  x[j] = e[i].user_data;
455 
456  /* Only advance if elt is not to be deleted. */
457  j += !elt_is_deleted (w, e[i].user_data);
458  }
459 
460  /* Adjust for deleted elts. */
461  if (j < e_len)
462  _vec_len (expired_user_data) -= e_len - j;
463 
464  free_elt_vector (w, e);
465 
466  level->elts[wheel_index] = 0;
467  clib_bitmap_set_no_check (level->occupancy_bitmap, wheel_index, 0);
468 
469  return expired_user_data;
470 }
471 
472 /* Called rarely. 32 bit times should only overflow every 4 seconds or so on a fast machine. */
473 static u32 *
474 advance_cpu_time_base (timing_wheel_t * w, u32 * expired_user_data)
475 {
478  u64 delta;
479 
481  delta = ((u64) 1 << w->n_wheel_elt_time_bits);
482  w->cpu_time_base += delta;
484 
485  vec_foreach (l, w->levels)
486  {
487  uword wi;
488  /* *INDENT-OFF* */
490  vec_foreach (e, l->elts[wi])
491  {
492  /* This should always be true since otherwise we would have already expired
493  this element. Note that in the second half of this function we need
494  to take care not to place the expired elements ourselves. */
495  ASSERT (e->cpu_time_relative_to_base >= delta);
496  e->cpu_time_relative_to_base -= delta;
497  }
498  }
499  /* *INDENT-ON* */
500  }
501 
502  /* See which overflow elements fit now. */
503  {
505  /* *INDENT-OFF* */
506  pool_foreach (oe, w->overflow_pool) {
507  /* It fits now into 32 bits. */
508  if (0 == ((oe->cpu_time - w->cpu_time_base) >> BITS (e->cpu_time_relative_to_base)))
509  {
510  u64 ti = oe->cpu_time >> w->log2_clocks_per_bin;
511  if (ti <= w->current_time_index)
512  {
513  /* This can happen when timing wheel is not advanced for a long time
514  (for example when at a gdb breakpoint for a while). */
515  /* Note: the ti == w->current_time_index means it is also an expired timer */
516  if (! elt_is_deleted (w, oe->user_data))
517  vec_add1 (expired_user_data, oe->user_data);
518  }
519  else
521  pool_put (w->overflow_pool, oe);
522  }
523  }
524  /* *INDENT-ON* */
525  }
526  return expired_user_data;
527 }
528 
529 static u32 *
531  uword level_index,
532  u64 advance_cpu_time,
533  uword from_wheel_index,
534  uword to_wheel_index, u32 * expired_user_data)
535 {
536  timing_wheel_level_t *level;
538  u64 advance_time_index = advance_cpu_time >> w->log2_clocks_per_bin;
539 
540  vec_validate (w->stats.refills, level_index);
541  w->stats.refills[level_index] += 1;
542 
543  if (level_index + 1 >= vec_len (w->levels))
544  goto done;
545 
546  level = vec_elt_at_index (w->levels, level_index + 1);
547  if (!level->occupancy_bitmap)
548  goto done;
549 
550  while (1)
551  {
552  timing_wheel_elt_t *e, *es;
553 
555  (level->occupancy_bitmap, from_wheel_index))
556  {
557  es = level->elts[from_wheel_index];
558  level->elts[from_wheel_index] = 0;
559  clib_bitmap_set_no_check (level->occupancy_bitmap, from_wheel_index,
560  0);
561 
562  vec_foreach (e, es)
563  {
564  u64 e_time = elt_cpu_time (w, e);
565  u64 ti = e_time >> w->log2_clocks_per_bin;
566  if (ti <= advance_time_index)
567  {
568  validate_expired_elt (w, e, advance_cpu_time);
569  if (!elt_is_deleted (w, e->user_data))
570  vec_add1 (expired_user_data, e->user_data);
571  }
572  else
573  vec_add1 (to_insert, e[0]);
574  }
575  free_elt_vector (w, es);
576  }
577 
578  if (from_wheel_index == to_wheel_index)
579  break;
580 
581  from_wheel_index = wheel_add (w, from_wheel_index + 1);
582  }
583 
585 done:
586  w->unexpired_elts_pending_insert = to_insert;
587  return expired_user_data;
588 }
589 
590 /* Advance wheel and return any expired user data in vector. */
591 u32 *
592 timing_wheel_advance (timing_wheel_t * w, u64 advance_cpu_time,
593  u32 * expired_user_data,
594  u64 * next_expiring_element_cpu_time)
595 {
596  timing_wheel_level_t *level;
597  uword level_index, advance_rtime, advance_level_index, advance_wheel_index;
598  uword n_expired_user_data_before;
599  u64 current_time_index, advance_time_index;
600 
601  n_expired_user_data_before = vec_len (expired_user_data);
602 
603  /* Re-fill lower levels when time wraps. */
604  current_time_index = w->current_time_index;
605  advance_time_index = advance_cpu_time >> w->log2_clocks_per_bin;
606 
607  {
608  u64 current_ti, advance_ti;
609 
610  current_ti = current_time_index >> w->log2_bins_per_wheel;
611  advance_ti = advance_time_index >> w->log2_bins_per_wheel;
612 
613  if (PREDICT_FALSE (current_ti != advance_ti))
614  {
616  _vec_len (w->unexpired_elts_pending_insert) = 0;
617 
618  level_index = 0;
619  while (current_ti != advance_ti)
620  {
621  uword c, a;
622  c = current_ti & (w->bins_per_wheel - 1);
623  a = advance_ti & (w->bins_per_wheel - 1);
624  if (c != a)
625  expired_user_data = refill_level (w,
626  level_index,
627  advance_cpu_time,
628  c, a, expired_user_data);
629  current_ti >>= w->log2_bins_per_wheel;
630  advance_ti >>= w->log2_bins_per_wheel;
631  level_index++;
632  }
633  }
634  }
635 
636  advance_level_index =
637  get_level_and_relative_time (w, advance_cpu_time, &advance_rtime);
638  advance_wheel_index =
639  rtime_to_wheel_index (w, advance_level_index, advance_rtime);
640 
641  /* Empty all occupied bins for entire levels that we advance past. */
642  for (level_index = 0; level_index < advance_level_index; level_index++)
643  {
644  uword wi;
645 
646  if (level_index >= vec_len (w->levels))
647  break;
648 
649  level = vec_elt_at_index (w->levels, level_index);
650  /* *INDENT-OFF* */
652  expired_user_data = expire_bin (w, level_index, wi, advance_cpu_time,
653  expired_user_data);
654  }
655  /* *INDENT-ON* */
656  }
657 
658  if (PREDICT_TRUE (level_index < vec_len (w->levels)))
659  {
660  uword wi;
661  level = vec_elt_at_index (w->levels, level_index);
662  wi = current_time_wheel_index (w, level_index);
663  if (level->occupancy_bitmap)
664  while (1)
665  {
667  expired_user_data =
668  expire_bin (w, advance_level_index, wi, advance_cpu_time,
669  expired_user_data);
670 
671  /* When we jump out, we have already just expired the bin,
672  corresponding to advance_wheel_index */
673  if (wi == advance_wheel_index)
674  break;
675 
676  wi = wheel_add (w, wi + 1);
677  }
678  }
679 
680  /* Advance current time index. */
681  w->current_time_index = advance_time_index;
682 
684  {
687  _vec_len (w->unexpired_elts_pending_insert) = 0;
688  }
689 
690  /* Don't advance until necessary. */
691  /* However, if the timing_wheel_advance() hasn't been called for some time,
692  the while() loop will ensure multiple calls to advance_cpu_time_base()
693  in a row until the w->cpu_time_base is fresh enough. */
694  while (PREDICT_FALSE
695  (advance_time_index >= w->time_index_next_cpu_time_base_update))
696  expired_user_data = advance_cpu_time_base (w, expired_user_data);
697 
698  if (next_expiring_element_cpu_time)
699  {
700  u64 min_t;
701 
702  /* Anything expired? If so we need to recompute next expiring elt time. */
703  if (vec_len (expired_user_data) == n_expired_user_data_before
704  && w->cached_min_cpu_time_on_wheel != 0ULL)
705  min_t = w->cached_min_cpu_time_on_wheel;
706  else
707  {
709  w->cached_min_cpu_time_on_wheel = min_t;
710  }
711 
712  *next_expiring_element_cpu_time = min_t;
713  }
714 
715  return expired_user_data;
716 }
717 
718 u8 *
719 format_timing_wheel (u8 * s, va_list * va)
720 {
721  timing_wheel_t *w = va_arg (*va, timing_wheel_t *);
722  int verbose = va_arg (*va, int);
723  u32 indent = format_get_indent (s);
724 
725  s = format (s, "level 0: %.4e - %.4e secs, 2^%d - 2^%d clocks",
727  (f64) (1 << w->log2_clocks_per_wheel) /
730 
731  if (verbose)
732  {
733  int l;
734 
735  s = format (s, "\n%Utime base advances %Ld, every %.4e secs",
736  format_white_space, indent + 2,
738  (f64) ((u64) 1 << w->n_wheel_elt_time_bits) /
740 
741  for (l = 0; l < vec_len (w->levels); l++)
742  s = format (s, "\n%Ulevel %d: refills %Ld",
743  format_white_space, indent + 2,
744  l,
745  l <
746  vec_len (w->stats.refills) ? w->stats.
747  refills[l] : (u64) 0);
748  }
749 
750  return s;
751 }
752 
753 /*
754  * fd.io coding-style-patch-verification: ON
755  *
756  * Local Variables:
757  * eval: (c-set-style "gnu")
758  * End:
759  */
timing_wheel_t::bins_per_wheel
u32 bins_per_wheel
Definition: timing_wheel.h:78
timing_wheel_validate
void timing_wheel_validate(timing_wheel_t *w)
Definition: timing_wheel.c:164
timing_wheel_t::overflow_pool
timing_wheel_overflow_elt_t * overflow_pool
Definition: timing_wheel.h:85
timing_wheel_t::log2_bins_per_wheel
u8 log2_bins_per_wheel
Definition: timing_wheel.h:68
timing_wheel_overflow_elt_t::user_data
u32 user_data
Definition: timing_wheel.h:38
elt_is_deleted
static uword elt_is_deleted(timing_wheel_t *w, u32 user_data)
Definition: timing_wheel.c:256
validate_level
static clib_error_t * validate_level(timing_wheel_t *w, uword level_index, uword *n_elts)
Definition: timing_wheel.c:109
timing_wheel_t::current_time_index
u64 current_time_index
Definition: timing_wheel.h:100
bitmap.h
insert_helper
static timing_wheel_elt_t * insert_helper(timing_wheel_t *w, uword level_index, uword rtime)
Definition: timing_wheel.c:193
timing_wheel_level_t::occupancy_bitmap
uword * occupancy_bitmap
Definition: timing_wheel.h:46
timing_wheel_next_expiring_elt_time
u64 timing_wheel_next_expiring_elt_time(timing_wheel_t *w)
Definition: timing_wheel.c:342
timing_wheel_t::stats
timing_wheel_stats_t stats
Definition: timing_wheel.h:117
timing_wheel.h
wheel_add
static uword wheel_add(timing_wheel_t *w, word x)
Definition: timing_wheel.c:96
timing_wheel_t::cpu_clocks_per_second
f64 cpu_clocks_per_second
Definition: timing_wheel.h:115
pool_put
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:305
timing_wheel_elt_t::cpu_time_relative_to_base
u32 cpu_time_relative_to_base
Definition: timing_wheel.h:25
timing_wheel_t::max_sched_time
f64 max_sched_time
Definition: timing_wheel.h:115
timing_wheel_overflow_elt_t::cpu_time
u64 cpu_time
Definition: timing_wheel.h:35
clib_error_report
#define clib_error_report(e)
Definition: error.h:113
hash_create
#define hash_create(elts, value_bytes)
Definition: hash.h:695
timing_wheel_level_t
Definition: timing_wheel.h:43
timing_wheel_insert
void timing_wheel_insert(timing_wheel_t *w, u64 insert_cpu_time, u32 user_data)
Definition: timing_wheel.c:294
error
Definition: cJSON.c:88
free_elt_vector
static void free_elt_vector(timing_wheel_t *w, timing_wheel_elt_t *ev)
Definition: timing_wheel.c:183
validate_expired_elt
static void validate_expired_elt(timing_wheel_t *w, timing_wheel_elt_t *e, u64 current_cpu_time)
Definition: timing_wheel.c:424
delete_user_data
static timing_wheel_elt_t * delete_user_data(timing_wheel_elt_t *elts, u32 user_data)
Definition: timing_wheel.c:263
max_log2
static uword max_log2(uword x)
Definition: clib.h:223
vec_elt
#define vec_elt(v, i)
Get vector value at index i.
Definition: vec_bootstrap.h:210
timing_wheel_t::log2_clocks_per_bin
u8 log2_clocks_per_bin
Definition: timing_wheel.h:65
format_timing_wheel
u8 * format_timing_wheel(u8 *s, va_list *va)
Definition: timing_wheel.c:719
expire_bin
static u32 * expire_bin(timing_wheel_t *w, uword level_index, uword wheel_index, u64 advance_cpu_time, u32 *expired_user_data)
Definition: timing_wheel.c:438
timing_wheel_elt_t
Definition: timing_wheel.h:20
timing_wheel_insert_helper
static void timing_wheel_insert_helper(timing_wheel_t *w, u64 insert_cpu_time, u32 user_data)
Definition: timing_wheel.c:227
ti
u32 ti
Definition: interface_output.c:405
pool_foreach
#define pool_foreach(VAR, POOL)
Iterate through pool.
Definition: pool.h:534
timing_wheel_stats_t::refills
u64 * refills
Definition: timing_wheel.h:55
timing_wheel_t::free_elt_vectors
timing_wheel_elt_t ** free_elt_vectors
Definition: timing_wheel.h:88
vec_len
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
Definition: vec_bootstrap.h:142
rtime_to_wheel_index
static uword rtime_to_wheel_index(timing_wheel_t *w, uword level_index, uword rtime)
Definition: timing_wheel.c:102
vec_add2
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:644
vec_add1
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:606
timing_wheel_t::min_sched_time
f64 min_sched_time
Definition: timing_wheel.h:115
timing_wheel_t
Definition: timing_wheel.h:61
vec_elt_at_index
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
Definition: vec_bootstrap.h:203
advance_cpu_time_base
static u32 * advance_cpu_time_base(timing_wheel_t *w, u32 *expired_user_data)
Definition: timing_wheel.c:474
PREDICT_FALSE
#define PREDICT_FALSE(x)
Definition: clib.h:124
BITS
#define BITS(x)
Definition: clib.h:69
timing_wheel_delete
void timing_wheel_delete(timing_wheel_t *w, u32 user_data)
Definition: timing_wheel.c:331
c
svmdb_client_t * c
Definition: vpp_get_metrics.c:48
uword
u64 uword
Definition: types.h:112
hash_get
#define hash_get(h, key)
Definition: hash.h:249
pool.h
Fixed length block allocator. Pools are built from clib vectors and bitmaps. Use pools when repeatedl...
timing_wheel_t::cpu_time_base
u64 cpu_time_base
Definition: timing_wheel.h:105
timing_wheel_elt_t::user_data
u32 user_data
Definition: timing_wheel.h:28
timing_wheel_level_t::elts
timing_wheel_elt_t ** elts
Definition: timing_wheel.h:49
i
sll srl srl sll sra u16x4 i
Definition: vector_sse42.h:261
f64
double f64
Definition: types.h:142
pool_get
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:255
vec_validate
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment)
Definition: vec.h:523
elt_cpu_time
static u64 elt_cpu_time(timing_wheel_t *w, timing_wheel_elt_t *e)
Definition: timing_wheel.c:418
clib_min
#define clib_min(x, y)
Definition: clib.h:342
vec_pop
#define vec_pop(V)
Returns last element of a vector and decrements its length.
Definition: vec.h:705
timing_wheel_advance
u32 * timing_wheel_advance(timing_wheel_t *w, u64 advance_cpu_time, u32 *expired_user_data, u64 *next_expiring_element_cpu_time)
Definition: timing_wheel.c:592
timing_wheel_t::levels
timing_wheel_level_t * levels
Definition: timing_wheel.h:83
get_level_and_relative_time
static uword get_level_and_relative_time(timing_wheel_t *w, u64 cpu_time, uword *rtime_result)
Definition: timing_wheel.c:56
timing_wheel_t::validate
u32 validate
Definition: timing_wheel.h:96
clib_bitmap_get_no_check
static uword clib_bitmap_get_no_check(uword *ai, uword i)
Gets the ith bit value from a bitmap Does not sanity-check the bit position.
Definition: bitmap.h:212
hash_elts
static uword hash_elts(void *v)
Definition: hash.h:118
clib_bitmap_validate
#define clib_bitmap_validate(v, n_bits)
Definition: bitmap.h:115
current_time_wheel_index
static uword current_time_wheel_index(timing_wheel_t *w, uword level_index)
Definition: timing_wheel.c:89
vec_free
#define vec_free(V)
Free vector's memory (no header).
Definition: vec.h:395
always_inline
#define always_inline
Definition: rdma_mlx5dv.h:23
u64
unsigned long u64
Definition: types.h:89
format
description fragment has unexpected format
Definition: map.api:433
ASSERT
#define ASSERT(truth)
Definition: error_bootstrap.h:69
format_get_indent
static u32 format_get_indent(u8 *s)
Definition: format.h:72
u32
unsigned int u32
Definition: types.h:88
timing_wheel_t::n_wheel_elt_time_bits
u8 n_wheel_elt_time_bits
Definition: timing_wheel.h:75
timing_wheel_overflow_elt_t
Definition: timing_wheel.h:32
vec_foreach
#define vec_foreach(var, vec)
Vector iterator.
Definition: vec_bootstrap.h:213
pool_elts
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:127
STRUCT_BITS_OF
#define STRUCT_BITS_OF(t, f)
Definition: clib.h:76
timing_wheel_t::bins_per_wheel_mask
u32 bins_per_wheel_mask
Definition: timing_wheel.h:81
hash_unset
#define hash_unset(h, key)
Definition: hash.h:261
clib_memset
clib_memset(h->entries, 0, sizeof(h->entries[0]) *entries)
timing_wheel_t::deleted_user_data_hash
uword * deleted_user_data_hash
Definition: timing_wheel.h:93
hash.h
u8
unsigned char u8
Definition: types.h:56
clib_error_t
Definition: clib_error.h:21
a
a
Definition: bitmap.h:544
timing_wheel_t::unexpired_elts_pending_insert
timing_wheel_elt_t * unexpired_elts_pending_insert
Definition: timing_wheel.h:90
word
i64 word
Definition: types.h:111
insert_elt
static void insert_elt(timing_wheel_t *w, timing_wheel_elt_t *e)
Definition: timing_wheel.c:411
time_index_to_wheel_index
static uword time_index_to_wheel_index(timing_wheel_t *w, uword level_index, u64 ti)
Definition: timing_wheel.c:81
timing_wheel_t::time_index_next_cpu_time_base_update
u64 time_index_next_cpu_time_base_update
Definition: timing_wheel.h:110
clib_bitmap_foreach
#define clib_bitmap_foreach(i, ai)
Macro to iterate across set bits in a bitmap.
Definition: bitmap.h:361
clib_bitmap_set_no_check
static uword clib_bitmap_set_no_check(uword *a, uword i, uword new_value)
Sets the ith bit of a bitmap to new_value.
Definition: bitmap.h:141
refill_level
static u32 * refill_level(timing_wheel_t *w, uword level_index, u64 advance_cpu_time, uword from_wheel_index, uword to_wheel_index, u32 *expired_user_data)
Definition: timing_wheel.c:530
hash_set1
#define hash_set1(h, key)
Definition: hash.h:258
PREDICT_TRUE
#define PREDICT_TRUE(x)
Definition: clib.h:125
timing_wheel_t::log2_clocks_per_wheel
u8 log2_clocks_per_wheel
Definition: timing_wheel.h:71
timing_wheel_init
void timing_wheel_init(timing_wheel_t *w, u64 current_cpu_time, f64 cpu_clocks_per_second)
Definition: timing_wheel.c:21
format_white_space
u8 * format_white_space(u8 *s, va_list *va)
Definition: std-formats.c:129
timing_wheel_t::cached_min_cpu_time_on_wheel
u64 cached_min_cpu_time_on_wheel
Definition: timing_wheel.h:113
timing_wheel_stats_t::cpu_time_base_advances
u64 cpu_time_base_advances
Definition: timing_wheel.h:58