FD.io VPP  v17.01-9-ge7dcee4
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)
178  clib_error_report (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  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  }
243  else
244  {
245  /* Time too far in the future: add to overflow vector. */
247  pool_get (w->overflow_pool, oe);
248  oe->user_data = user_data;
249  oe->cpu_time = insert_cpu_time;
250  }
251 }
252 
255 {
256  return (hash_elts (w->deleted_user_data_hash) > 0
257  && hash_get (w->deleted_user_data_hash, user_data));
258 }
259 
260 static timing_wheel_elt_t *
262 {
263  uword found_match;
264  timing_wheel_elt_t *e, *new_elts;
265 
266  /* Quickly scan to see if there are any elements to delete
267  in this bucket. */
268  found_match = 0;
269  vec_foreach (e, elts)
270  {
271  found_match = e->user_data == user_data;
272  if (found_match)
273  break;
274  }
275  if (!found_match)
276  return elts;
277 
278  /* Re-scan to build vector of new elts with matching user_data deleted. */
279  new_elts = 0;
280  vec_foreach (e, elts)
281  {
282  if (e->user_data != user_data)
283  vec_add1 (new_elts, e[0]);
284  }
285 
286  vec_free (elts);
287  return new_elts;
288 }
289 
290 /* Insert user data on wheel at given CPU time stamp. */
291 void
292 timing_wheel_insert (timing_wheel_t * w, u64 insert_cpu_time, u32 user_data)
293 {
294  /* Remove previously deleted elements. */
295  if (elt_is_deleted (w, user_data))
296  {
298  uword wi;
299 
300  /* Delete elts with given user data so that stale events don't expire. */
301  vec_foreach (l, w->levels)
302  {
303  /* *INDENT-OFF* */
305  l->elts[wi] = delete_user_data (l->elts[wi], user_data);
306  if (vec_len (l->elts[wi]) == 0)
307  l->occupancy_bitmap = clib_bitmap_andnoti (l->occupancy_bitmap, wi);
308  }));
309  /* *INDENT-ON* */
310  }
311 
312  {
314  /* *INDENT-OFF* */
315  pool_foreach (oe, w->overflow_pool, ({
316  if (oe->user_data == user_data)
317  pool_put (w->overflow_pool, oe);
318  }));
319  /* *INDENT-ON* */
320  }
321 
322  hash_unset (w->deleted_user_data_hash, user_data);
323  }
324 
325  timing_wheel_insert_helper (w, insert_cpu_time, user_data);
326 }
327 
328 void
330 {
331  if (!w->deleted_user_data_hash)
333  hash_create ( /* capacity */ 0, /* value bytes */ 0);
334 
335  hash_set1 (w->deleted_user_data_hash, user_data);
336 }
337 
338 /* Returns time of next expiring element. */
339 u64
341 {
344  uword li, wi, wi0;
345  u32 min_dt;
346  u64 min_t;
347  uword wrapped = 0;
348 
349  min_dt = ~0;
350  min_t = ~0ULL;
351  vec_foreach (l, w->levels)
352  {
353  if (!l->occupancy_bitmap)
354  continue;
355 
356  li = l - w->levels;
357  wi0 = wi = current_time_wheel_index (w, li);
358  wrapped = 0;
359  while (1)
360  {
362  {
363  vec_foreach (e, l->elts[wi])
364  min_dt = clib_min (min_dt, e->cpu_time_relative_to_base);
365 
366  if (wrapped && li + 1 < vec_len (w->levels))
367  {
368  uword wi1 = current_time_wheel_index (w, li + 1);
369  if (l[1].occupancy_bitmap
370  && clib_bitmap_get_no_check (l[1].occupancy_bitmap, wi1))
371  {
372  vec_foreach (e, l[1].elts[wi1])
373  {
374  min_dt =
375  clib_min (min_dt, e->cpu_time_relative_to_base);
376  }
377  }
378  }
379 
380  min_t = w->cpu_time_base + min_dt;
381  goto done;
382  }
383 
384  wi = wheel_add (w, wi + 1);
385  if (wi == wi0)
386  break;
387 
388  wrapped = wi != wi + 1;
389  }
390  }
391 
392  {
394 
395  if (min_dt != ~0)
396  min_t = w->cpu_time_base + min_dt;
397 
398  /* *INDENT-OFF* */
399  pool_foreach (oe, w->overflow_pool,
400  ({ min_t = clib_min (min_t, oe->cpu_time); }));
401  /* *INDENT-ON* */
402 
403  done:
404  return min_t;
405  }
406 }
407 
408 static inline void
410 {
413 }
414 
417 {
419 }
420 
421 always_inline void
423  u64 current_cpu_time)
424 {
425  if (CLIB_DEBUG > 0)
426  {
427  u64 e_time = elt_cpu_time (w, e);
428 
429  /* Verify that element is actually expired. */
430  ASSERT ((e_time >> w->log2_clocks_per_bin)
431  <= (current_cpu_time >> w->log2_clocks_per_bin));
432  }
433 }
434 
435 static u32 *
437  uword level_index,
438  uword wheel_index, u64 advance_cpu_time, u32 * expired_user_data)
439 {
440  timing_wheel_level_t *level = vec_elt_at_index (w->levels, level_index);
442  u32 *x;
443  uword i, j, e_len;
444 
445  e = vec_elt (level->elts, wheel_index);
446  e_len = vec_len (e);
447 
448  vec_add2 (expired_user_data, x, e_len);
449  for (i = j = 0; i < e_len; i++)
450  {
451  validate_expired_elt (w, &e[i], advance_cpu_time);
452  x[j] = e[i].user_data;
453 
454  /* Only advance if elt is not to be deleted. */
455  j += !elt_is_deleted (w, e[i].user_data);
456  }
457 
458  /* Adjust for deleted elts. */
459  if (j < e_len)
460  _vec_len (expired_user_data) -= e_len - j;
461 
462  free_elt_vector (w, e);
463 
464  level->elts[wheel_index] = 0;
465  clib_bitmap_set_no_check (level->occupancy_bitmap, wheel_index, 0);
466 
467  return expired_user_data;
468 }
469 
470 /* Called rarely. 32 bit times should only overflow every 4 seconds or so on a fast machine. */
471 static u32 *
472 advance_cpu_time_base (timing_wheel_t * w, u32 * expired_user_data)
473 {
476  u64 delta;
477 
479  delta = ((u64) 1 << w->n_wheel_elt_time_bits);
480  w->cpu_time_base += delta;
482 
483  vec_foreach (l, w->levels)
484  {
485  uword wi;
486  /* *INDENT-OFF* */
488  vec_foreach (e, l->elts[wi])
489  {
490  /* This should always be true since otherwise we would have already expired
491  this element. */
492  ASSERT (e->cpu_time_relative_to_base >= delta);
493  e->cpu_time_relative_to_base -= delta;
494  }
495  }));
496  /* *INDENT-ON* */
497  }
498 
499  /* See which overflow elements fit now. */
500  {
502  /* *INDENT-OFF* */
503  pool_foreach (oe, w->overflow_pool, ({
504  /* It fits now into 32 bits. */
505  if (0 == ((oe->cpu_time - w->cpu_time_base) >> BITS (e->cpu_time_relative_to_base)))
506  {
507  u64 ti = oe->cpu_time >> w->log2_clocks_per_bin;
508  if (ti < w->current_time_index)
509  {
510  /* This can happen when timing wheel is not advanced for a long time
511  (for example when at a gdb breakpoint for a while). */
512  if (! elt_is_deleted (w, oe->user_data))
513  vec_add1 (expired_user_data, oe->user_data);
514  }
515  else
516  timing_wheel_insert_helper (w, oe->cpu_time, oe->user_data);
517  pool_put (w->overflow_pool, oe);
518  }
519  }));
520  /* *INDENT-ON* */
521  }
522  return expired_user_data;
523 }
524 
525 static u32 *
527  uword level_index,
528  u64 advance_cpu_time,
529  uword from_wheel_index,
530  uword to_wheel_index, u32 * expired_user_data)
531 {
532  timing_wheel_level_t *level;
534  u64 advance_time_index = advance_cpu_time >> w->log2_clocks_per_bin;
535 
536  vec_validate (w->stats.refills, level_index);
537  w->stats.refills[level_index] += 1;
538 
539  if (level_index + 1 >= vec_len (w->levels))
540  goto done;
541 
542  level = vec_elt_at_index (w->levels, level_index + 1);
543  if (!level->occupancy_bitmap)
544  goto done;
545 
546  while (1)
547  {
548  timing_wheel_elt_t *e, *es;
549 
551  (level->occupancy_bitmap, from_wheel_index))
552  {
553  es = level->elts[from_wheel_index];
554  level->elts[from_wheel_index] = 0;
555  clib_bitmap_set_no_check (level->occupancy_bitmap, from_wheel_index,
556  0);
557 
558  vec_foreach (e, es)
559  {
560  u64 e_time = elt_cpu_time (w, e);
561  u64 ti = e_time >> w->log2_clocks_per_bin;
562  if (ti <= advance_time_index)
563  {
564  validate_expired_elt (w, e, advance_cpu_time);
565  if (!elt_is_deleted (w, e->user_data))
566  vec_add1 (expired_user_data, e->user_data);
567  }
568  else
569  vec_add1 (to_insert, e[0]);
570  }
571  free_elt_vector (w, es);
572  }
573 
574  if (from_wheel_index == to_wheel_index)
575  break;
576 
577  from_wheel_index = wheel_add (w, from_wheel_index + 1);
578  }
579 
581 done:
582  w->unexpired_elts_pending_insert = to_insert;
583  return expired_user_data;
584 }
585 
586 /* Advance wheel and return any expired user data in vector. */
587 u32 *
588 timing_wheel_advance (timing_wheel_t * w, u64 advance_cpu_time,
589  u32 * expired_user_data,
590  u64 * next_expiring_element_cpu_time)
591 {
592  timing_wheel_level_t *level;
593  uword level_index, advance_rtime, advance_level_index, advance_wheel_index;
594  uword n_expired_user_data_before;
595  u64 current_time_index, advance_time_index;
596 
597  n_expired_user_data_before = vec_len (expired_user_data);
598 
599  /* Re-fill lower levels when time wraps. */
600  current_time_index = w->current_time_index;
601  advance_time_index = advance_cpu_time >> w->log2_clocks_per_bin;
602 
603  {
604  u64 current_ti, advance_ti;
605 
606  current_ti = current_time_index >> w->log2_bins_per_wheel;
607  advance_ti = advance_time_index >> w->log2_bins_per_wheel;
608 
609  if (PREDICT_FALSE (current_ti != advance_ti))
610  {
612  _vec_len (w->unexpired_elts_pending_insert) = 0;
613 
614  level_index = 0;
615  while (current_ti != advance_ti)
616  {
617  uword c, a;
618  c = current_ti & (w->bins_per_wheel - 1);
619  a = advance_ti & (w->bins_per_wheel - 1);
620  if (c != a)
621  expired_user_data = refill_level (w,
622  level_index,
623  advance_cpu_time,
624  c, a, expired_user_data);
625  current_ti >>= w->log2_bins_per_wheel;
626  advance_ti >>= w->log2_bins_per_wheel;
627  level_index++;
628  }
629  }
630  }
631 
632  advance_level_index =
633  get_level_and_relative_time (w, advance_cpu_time, &advance_rtime);
634  advance_wheel_index =
635  rtime_to_wheel_index (w, advance_level_index, advance_rtime);
636 
637  /* Empty all occupied bins for entire levels that we advance past. */
638  for (level_index = 0; level_index < advance_level_index; level_index++)
639  {
640  uword wi;
641 
642  if (level_index >= vec_len (w->levels))
643  break;
644 
645  level = vec_elt_at_index (w->levels, level_index);
646  /* *INDENT-OFF* */
647  clib_bitmap_foreach (wi, level->occupancy_bitmap, ({
648  expired_user_data = expire_bin (w, level_index, wi, advance_cpu_time,
649  expired_user_data);
650  }));
651  /* *INDENT-ON* */
652  }
653 
654  if (PREDICT_TRUE (level_index < vec_len (w->levels)))
655  {
656  uword wi;
657  level = vec_elt_at_index (w->levels, level_index);
658  wi = current_time_wheel_index (w, level_index);
659  if (level->occupancy_bitmap)
660  while (1)
661  {
663  expired_user_data =
664  expire_bin (w, advance_level_index, wi, advance_cpu_time,
665  expired_user_data);
666 
667  if (wi == advance_wheel_index)
668  break;
669 
670  wi = wheel_add (w, wi + 1);
671  }
672  }
673 
674  /* Advance current time index. */
675  w->current_time_index = advance_time_index;
676 
678  {
681  _vec_len (w->unexpired_elts_pending_insert) = 0;
682  }
683 
684  /* Don't advance until necessary. */
685  while (PREDICT_FALSE
686  (advance_time_index >= w->time_index_next_cpu_time_base_update))
687  expired_user_data = advance_cpu_time_base (w, expired_user_data);
688 
689  if (next_expiring_element_cpu_time)
690  {
691  u64 min_t;
692 
693  /* Anything expired? If so we need to recompute next expiring elt time. */
694  if (vec_len (expired_user_data) == n_expired_user_data_before
695  && w->cached_min_cpu_time_on_wheel != 0ULL)
696  min_t = w->cached_min_cpu_time_on_wheel;
697  else
698  {
700  w->cached_min_cpu_time_on_wheel = min_t;
701  }
702 
703  *next_expiring_element_cpu_time = min_t;
704  }
705 
706  return expired_user_data;
707 }
708 
709 u8 *
710 format_timing_wheel (u8 * s, va_list * va)
711 {
712  timing_wheel_t *w = va_arg (*va, timing_wheel_t *);
713  int verbose = va_arg (*va, int);
714  uword indent = format_get_indent (s);
715 
716  s = format (s, "level 0: %.4e - %.4e secs, 2^%d - 2^%d clocks",
718  (f64) (1 << w->log2_clocks_per_wheel) /
721 
722  if (verbose)
723  {
724  int l;
725 
726  s = format (s, "\n%Utime base advances %Ld, every %.4e secs",
727  format_white_space, indent + 2,
729  (f64) ((u64) 1 << w->n_wheel_elt_time_bits) /
731 
732  for (l = 0; l < vec_len (w->levels); l++)
733  s = format (s, "\n%Ulevel %d: refills %Ld",
734  format_white_space, indent + 2,
735  l,
736  l <
737  vec_len (w->stats.refills) ? w->stats.
738  refills[l] : (u64) 0);
739  }
740 
741  return s;
742 }
743 
744 /*
745  * fd.io coding-style-patch-verification: ON
746  *
747  * Local Variables:
748  * eval: (c-set-style "gnu")
749  * End:
750  */
#define vec_validate(V, I)
Make sure vector is long enough for given index (no header, unspecified alignment) ...
Definition: vec.h:396
timing_wheel_overflow_elt_t * overflow_pool
Definition: timing_wheel.h:85
void timing_wheel_validate(timing_wheel_t *w)
Definition: timing_wheel.c:164
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
#define clib_min(x, y)
Definition: clib.h:326
#define hash_unset(h, key)
Definition: hash.h:260
a
Definition: bitmap.h:516
#define PREDICT_TRUE(x)
Definition: clib.h:98
#define STRUCT_BITS_OF(t, f)
Definition: clib.h:65
void timing_wheel_init(timing_wheel_t *w, u64 current_cpu_time, f64 cpu_clocks_per_second)
Definition: timing_wheel.c:21
Fixed length block allocator.
u64 timing_wheel_next_expiring_elt_time(timing_wheel_t *w)
Definition: timing_wheel.c:340
u64 cached_min_cpu_time_on_wheel
Definition: timing_wheel.h:113
#define vec_add1(V, E)
Add 1 element to end of vector (unspecified alignment).
Definition: vec.h:482
#define vec_add2(V, P, N)
Add N elements to end of vector V, return pointer to new elements in P.
Definition: vec.h:521
#define clib_error_report(e)
Definition: error.h:125
void timing_wheel_insert(timing_wheel_t *w, u64 insert_cpu_time, u32 user_data)
Definition: timing_wheel.c:292
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:200
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
#define vec_pop(V)
Returns last element of a vector and decrements its length.
Definition: vec.h:576
static uword wheel_add(timing_wheel_t *w, word x)
Definition: timing_wheel.c:96
static timing_wheel_elt_t * delete_user_data(timing_wheel_elt_t *elts, u32 user_data)
Definition: timing_wheel.c:261
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
static void free_elt_vector(timing_wheel_t *w, timing_wheel_elt_t *ev)
Definition: timing_wheel.c:183
#define clib_bitmap_validate(v, n_bits)
Definition: bitmap.h:115
static timing_wheel_elt_t * insert_helper(timing_wheel_t *w, uword level_index, uword rtime)
Definition: timing_wheel.c:193
#define pool_foreach(VAR, POOL, BODY)
Iterate through pool.
Definition: pool.h:348
#define always_inline
Definition: clib.h:84
u8 * format_white_space(u8 *s, va_list *va)
Definition: std-formats.c:113
timing_wheel_stats_t stats
Definition: timing_wheel.h:117
#define vec_elt_at_index(v, i)
Get vector value at index i checking that i is in bounds.
f64 cpu_clocks_per_second
Definition: timing_wheel.h:115
unsigned long u64
Definition: types.h:89
static u32 * advance_cpu_time_base(timing_wheel_t *w, u32 *expired_user_data)
Definition: timing_wheel.c:472
static void validate_expired_elt(timing_wheel_t *w, timing_wheel_elt_t *e, u64 current_cpu_time)
Definition: timing_wheel.c:422
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:436
#define hash_get(h, key)
Definition: hash.h:248
#define clib_bitmap_foreach(i, ai, body)
Macro to iterate across set bits in a bitmap.
Definition: bitmap.h:361
static uword format_get_indent(u8 *s)
Definition: format.h:72
timing_wheel_elt_t ** free_elt_vectors
Definition: timing_wheel.h:88
u8 * format_timing_wheel(u8 *s, va_list *va)
Definition: timing_wheel.c:710
#define PREDICT_FALSE(x)
Definition: clib.h:97
static uword current_time_wheel_index(timing_wheel_t *w, uword level_index)
Definition: timing_wheel.c:89
static u64 elt_cpu_time(timing_wheel_t *w, timing_wheel_elt_t *e)
Definition: timing_wheel.c:416
static void timing_wheel_insert_helper(timing_wheel_t *w, u64 insert_cpu_time, u32 user_data)
Definition: timing_wheel.c:227
static uword rtime_to_wheel_index(timing_wheel_t *w, uword level_index, uword rtime)
Definition: timing_wheel.c:102
svmdb_client_t * c
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:300
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:588
void timing_wheel_delete(timing_wheel_t *w, u32 user_data)
Definition: timing_wheel.c:329
timing_wheel_elt_t ** elts
Definition: timing_wheel.h:49
#define hash_set1(h, key)
Definition: hash.h:257
timing_wheel_elt_t * unexpired_elts_pending_insert
Definition: timing_wheel.h:90
#define hash_create(elts, value_bytes)
Definition: hash.h:658
uword * deleted_user_data_hash
Definition: timing_wheel.h:93
static uword hash_elts(void *v)
Definition: hash.h:117
#define ASSERT(truth)
unsigned int u32
Definition: types.h:88
u64 time_index_next_cpu_time_base_update
Definition: timing_wheel.h:110
Bitmaps built as vectors of machine words.
static uword get_level_and_relative_time(timing_wheel_t *w, u64 cpu_time, uword *rtime_result)
Definition: timing_wheel.c:56
timing_wheel_level_t * levels
Definition: timing_wheel.h:83
u64 uword
Definition: types.h:112
#define vec_elt(v, i)
Get vector value at index i.
i64 word
Definition: types.h:111
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
double f64
Definition: types.h:142
unsigned char u8
Definition: types.h:56
static uword max_log2(uword x)
Definition: clib.h:222
u8 n_wheel_elt_time_bits
Definition: timing_wheel.h:75
u32 bins_per_wheel_mask
Definition: timing_wheel.h:81
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:526
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:418
#define vec_foreach(var, vec)
Vector iterator.
static uword time_index_to_wheel_index(timing_wheel_t *w, uword level_index, u64 ti)
Definition: timing_wheel.c:81
static void insert_elt(timing_wheel_t *w, timing_wheel_elt_t *e)
Definition: timing_wheel.c:409
static uword elt_is_deleted(timing_wheel_t *w, u32 user_data)
Definition: timing_wheel.c:254
u8 log2_clocks_per_wheel
Definition: timing_wheel.h:71
#define BITS(x)
Definition: clib.h:58
static clib_error_t * validate_level(timing_wheel_t *w, uword level_index, uword *n_elts)
Definition: timing_wheel.c:109
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:109