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