blob: a6c476b2cfa77e094299403ea9ee9b1d605f54aa [file] [log] [blame]
Ed Warnickecb9cada2015-12-08 15:45:58 -07001/*
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
20void
Dave Barachc3799992016-08-15 11:12:27 -040021timing_wheel_init (timing_wheel_t * w, u64 current_cpu_time,
22 f64 cpu_clocks_per_second)
Ed Warnickecb9cada2015-12-08 15:45:58 -070023{
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;
Dave Barachc3799992016-08-15 11:12:27 -040031 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);
Ed Warnickecb9cada2015-12-08 15:45:58 -070035 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 ||
Dave Barachc3799992016-08-15 11:12:27 -040043 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;
Ed Warnickecb9cada2015-12-08 15:45:58 -070047
48 w->cpu_time_base = current_cpu_time;
49 w->time_index_next_cpu_time_base_update
Dave Barachc3799992016-08-15 11:12:27 -040050 =
51 w->current_time_index +
52 ((u64) 1 << (w->n_wheel_elt_time_bits - w->log2_clocks_per_bin));
Ed Warnickecb9cada2015-12-08 15:45:58 -070053}
54
55always_inline uword
Dave Barachc3799992016-08-15 11:12:27 -040056get_level_and_relative_time (timing_wheel_t * w, u64 cpu_time,
57 uword * rtime_result)
Ed Warnickecb9cada2015-12-08 15:45:58 -070058{
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
80always_inline uword
81time_index_to_wheel_index (timing_wheel_t * w, uword level_index, u64 ti)
Dave Barachc3799992016-08-15 11:12:27 -040082{
83 return (ti >> (level_index * w->log2_bins_per_wheel)) &
84 w->bins_per_wheel_mask;
85}
Ed Warnickecb9cada2015-12-08 15:45:58 -070086
87/* Find current time on this level. */
88always_inline uword
89current_time_wheel_index (timing_wheel_t * w, uword level_index)
Dave Barachc3799992016-08-15 11:12:27 -040090{
91 return time_index_to_wheel_index (w, level_index, w->current_time_index);
92}
Ed Warnickecb9cada2015-12-08 15:45:58 -070093
94/* Circular wheel indexing. */
95always_inline uword
96wheel_add (timing_wheel_t * w, word x)
Dave Barachc3799992016-08-15 11:12:27 -040097{
98 return x & w->bins_per_wheel_mask;
99}
Ed Warnickecb9cada2015-12-08 15:45:58 -0700100
101always_inline uword
102rtime_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
108static clib_error_t *
109validate_level (timing_wheel_t * w, uword level_index, uword * n_elts)
110{
Dave Barachc3799992016-08-15 11:12:27 -0400111 timing_wheel_level_t *level;
112 timing_wheel_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700113 uword wi;
Dave Barachc3799992016-08-15 11:12:27 -0400114 clib_error_t *error = 0;
115
Ed Warnickecb9cada2015-12-08 15:45:58 -0700116#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. */
Dave Barachc3799992016-08-15 11:12:27 -0400127 _(clib_bitmap_get_no_check (level->occupancy_bitmap, wi) ==
128 (vec_len (level->elts[wi]) > 0));
Ed Warnickecb9cada2015-12-08 15:45:58 -0700129
130 *n_elts += vec_len (level->elts[wi]);
131
132 vec_foreach (e, level->elts[wi])
Dave Barachc3799992016-08-15 11:12:27 -0400133 {
134 /* Validate time bin and level. */
135 u64 e_time;
136 uword e_ti, e_li, e_wi;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700137
Dave Barachc3799992016-08-15 11:12:27 -0400138 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);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700141
Dave Barachc3799992016-08-15 11:12:27 -0400142 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 }
Ed Warnickecb9cada2015-12-08 15:45:58 -0700156 }
157
158#undef _
159
160 return error;
161}
162
Dave Barachc3799992016-08-15 11:12:27 -0400163void
164timing_wheel_validate (timing_wheel_t * w)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700165{
166 uword l;
Dave Barachc3799992016-08-15 11:12:27 -0400167 clib_error_t *error = 0;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700168 uword n_elts;
169
Dave Barachc3799992016-08-15 11:12:27 -0400170 if (!w->validate)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700171 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
182always_inline void
183free_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)
Dave Barachb7b92992018-10-17 10:38:51 -0400187 clib_memset (ev, ~0, vec_len (ev) * sizeof (ev[0]));
Ed Warnickecb9cada2015-12-08 15:45:58 -0700188 _vec_len (ev) = 0;
189 vec_add1 (w->free_elt_vectors, ev);
190}
191
192static timing_wheel_elt_t *
Dave Barachc3799992016-08-15 11:12:27 -0400193insert_helper (timing_wheel_t * w, uword level_index, uword rtime)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700194{
Dave Barachc3799992016-08-15 11:12:27 -0400195 timing_wheel_level_t *level;
196 timing_wheel_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700197 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
Dave Barachc3799992016-08-15 11:12:27 -0400203 if (PREDICT_FALSE (!level->elts))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700204 {
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
Dave Barachc3799992016-08-15 11:12:27 -0400212 level->occupancy_bitmap =
213 clib_bitmap_ori (level->occupancy_bitmap, wheel_index);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700214
215 /* Allocate an elt vector from free list if there is one. */
Dave Barachc3799992016-08-15 11:12:27 -0400216 if (!level->elts[wheel_index] && vec_len (w->free_elt_vectors))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700217 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. */
Dave Barachc3799992016-08-15 11:12:27 -0400226static void
227timing_wheel_insert_helper (timing_wheel_t * w, u64 insert_cpu_time,
228 u32 user_data)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700229{
Dave Barachc3799992016-08-15 11:12:27 -0400230 timing_wheel_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700231 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;
Andrew Yourtchenkofa5231d2017-02-01 14:08:21 +0000242 if (insert_cpu_time < w->cached_min_cpu_time_on_wheel)
243 w->cached_min_cpu_time_on_wheel = insert_cpu_time;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700244 }
245 else
246 {
247 /* Time too far in the future: add to overflow vector. */
Dave Barachc3799992016-08-15 11:12:27 -0400248 timing_wheel_overflow_elt_t *oe;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700249 pool_get (w->overflow_pool, oe);
250 oe->user_data = user_data;
251 oe->cpu_time = insert_cpu_time;
252 }
253}
254
255always_inline uword
256elt_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
262static timing_wheel_elt_t *
263delete_user_data (timing_wheel_elt_t * elts, u32 user_data)
264{
265 uword found_match;
Dave Barachc3799992016-08-15 11:12:27 -0400266 timing_wheel_elt_t *e, *new_elts;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700267
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)
Dave Barachc3799992016-08-15 11:12:27 -0400272 {
273 found_match = e->user_data == user_data;
274 if (found_match)
275 break;
276 }
277 if (!found_match)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700278 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)
Dave Barachc3799992016-08-15 11:12:27 -0400283 {
284 if (e->user_data != user_data)
285 vec_add1 (new_elts, e[0]);
286 }
Ed Warnickecb9cada2015-12-08 15:45:58 -0700287
288 vec_free (elts);
289 return new_elts;
290}
291
292/* Insert user data on wheel at given CPU time stamp. */
Dave Barachc3799992016-08-15 11:12:27 -0400293void
294timing_wheel_insert (timing_wheel_t * w, u64 insert_cpu_time, u32 user_data)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700295{
296 /* Remove previously deleted elements. */
297 if (elt_is_deleted (w, user_data))
298 {
Dave Barachc3799992016-08-15 11:12:27 -0400299 timing_wheel_level_t *l;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700300 uword wi;
301
302 /* Delete elts with given user data so that stale events don't expire. */
303 vec_foreach (l, w->levels)
Dave Barachc3799992016-08-15 11:12:27 -0400304 {
305 /* *INDENT-OFF* */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700306 clib_bitmap_foreach (wi, l->occupancy_bitmap, ({
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 }));
Dave Barachc3799992016-08-15 11:12:27 -0400311 /* *INDENT-ON* */
312 }
Ed Warnickecb9cada2015-12-08 15:45:58 -0700313
314 {
Dave Barachc3799992016-08-15 11:12:27 -0400315 timing_wheel_overflow_elt_t *oe;
316 /* *INDENT-OFF* */
Damjan Marionb2c31b62020-12-13 21:47:40 +0100317 pool_foreach (oe, w->overflow_pool) {
Ed Warnickecb9cada2015-12-08 15:45:58 -0700318 if (oe->user_data == user_data)
319 pool_put (w->overflow_pool, oe);
Damjan Marionb2c31b62020-12-13 21:47:40 +0100320 }
Dave Barachc3799992016-08-15 11:12:27 -0400321 /* *INDENT-ON* */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700322 }
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
Dave Barachc3799992016-08-15 11:12:27 -0400330void
331timing_wheel_delete (timing_wheel_t * w, u32 user_data)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700332{
Dave Barachc3799992016-08-15 11:12:27 -0400333 if (!w->deleted_user_data_hash)
334 w->deleted_user_data_hash =
335 hash_create ( /* capacity */ 0, /* value bytes */ 0);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700336
337 hash_set1 (w->deleted_user_data_hash, user_data);
338}
339
340/* Returns time of next expiring element. */
Dave Barachc3799992016-08-15 11:12:27 -0400341u64
342timing_wheel_next_expiring_elt_time (timing_wheel_t * w)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700343{
Dave Barachc3799992016-08-15 11:12:27 -0400344 timing_wheel_level_t *l;
345 timing_wheel_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700346 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)
Dave Barachc3799992016-08-15 11:12:27 -0400354 {
355 if (!l->occupancy_bitmap)
356 continue;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700357
Dave Barachc3799992016-08-15 11:12:27 -0400358 li = l - w->levels;
359 wi0 = wi = current_time_wheel_index (w, li);
360 wrapped = 0;
361 while (1)
362 {
363 if (clib_bitmap_get_no_check (l->occupancy_bitmap, wi))
364 {
365 vec_foreach (e, l->elts[wi])
366 min_dt = clib_min (min_dt, e->cpu_time_relative_to_base);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700367
Dave Barachc3799992016-08-15 11:12:27 -0400368 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])
Ed Warnickecb9cada2015-12-08 15:45:58 -0700375 {
Dave Barachc3799992016-08-15 11:12:27 -0400376 min_dt =
377 clib_min (min_dt, e->cpu_time_relative_to_base);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700378 }
Dave Barachc3799992016-08-15 11:12:27 -0400379 }
380 }
Ed Warnickecb9cada2015-12-08 15:45:58 -0700381
Dave Barachc3799992016-08-15 11:12:27 -0400382 min_t = w->cpu_time_base + min_dt;
383 goto done;
384 }
Ed Warnickecb9cada2015-12-08 15:45:58 -0700385
Dave Barachc3799992016-08-15 11:12:27 -0400386 wi = wheel_add (w, wi + 1);
387 if (wi == wi0)
388 break;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700389
Dave Barachc3799992016-08-15 11:12:27 -0400390 wrapped = wi != wi + 1;
391 }
392 }
Ed Warnickecb9cada2015-12-08 15:45:58 -0700393
394 {
Dave Barachc3799992016-08-15 11:12:27 -0400395 timing_wheel_overflow_elt_t *oe;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700396
397 if (min_dt != ~0)
398 min_t = w->cpu_time_base + min_dt;
399
Dave Barachc3799992016-08-15 11:12:27 -0400400 /* *INDENT-OFF* */
Damjan Marionb2c31b62020-12-13 21:47:40 +0100401 pool_foreach (oe, w->overflow_pool)
402 { min_t = clib_min (min_t, oe->cpu_time); }
Dave Barachc3799992016-08-15 11:12:27 -0400403 /* *INDENT-ON* */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700404
405 done:
406 return min_t;
407 }
408}
409
410static inline void
411insert_elt (timing_wheel_t * w, timing_wheel_elt_t * e)
412{
413 u64 t = w->cpu_time_base + e->cpu_time_relative_to_base;
414 timing_wheel_insert_helper (w, t, e->user_data);
415}
416
417always_inline u64
418elt_cpu_time (timing_wheel_t * w, timing_wheel_elt_t * e)
Dave Barachc3799992016-08-15 11:12:27 -0400419{
420 return w->cpu_time_base + e->cpu_time_relative_to_base;
421}
Ed Warnickecb9cada2015-12-08 15:45:58 -0700422
423always_inline void
424validate_expired_elt (timing_wheel_t * w, timing_wheel_elt_t * e,
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
437static u32 *
438expire_bin (timing_wheel_t * w,
439 uword level_index,
Dave Barachc3799992016-08-15 11:12:27 -0400440 uword wheel_index, u64 advance_cpu_time, u32 * expired_user_data)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700441{
Dave Barachc3799992016-08-15 11:12:27 -0400442 timing_wheel_level_t *level = vec_elt_at_index (w->levels, level_index);
443 timing_wheel_elt_t *e;
444 u32 *x;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700445 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. */
Dave Barachc3799992016-08-15 11:12:27 -0400457 j += !elt_is_deleted (w, e[i].user_data);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700458 }
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. */
Klement Sekerae5af88c2016-11-11 05:58:10 +0100473static u32 *
Ed Warnickecb9cada2015-12-08 15:45:58 -0700474advance_cpu_time_base (timing_wheel_t * w, u32 * expired_user_data)
475{
Dave Barachc3799992016-08-15 11:12:27 -0400476 timing_wheel_level_t *l;
477 timing_wheel_elt_t *e;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700478 u64 delta;
479
480 w->stats.cpu_time_base_advances++;
481 delta = ((u64) 1 << w->n_wheel_elt_time_bits);
482 w->cpu_time_base += delta;
483 w->time_index_next_cpu_time_base_update += delta >> w->log2_clocks_per_bin;
484
485 vec_foreach (l, w->levels)
Dave Barachc3799992016-08-15 11:12:27 -0400486 {
487 uword wi;
488 /* *INDENT-OFF* */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700489 clib_bitmap_foreach (wi, l->occupancy_bitmap, ({
490 vec_foreach (e, l->elts[wi])
491 {
492 /* This should always be true since otherwise we would have already expired
Andrew Yourtchenkofa5231d2017-02-01 14:08:21 +0000493 this element. Note that in the second half of this function we need
494 to take care not to place the expired elements ourselves. */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700495 ASSERT (e->cpu_time_relative_to_base >= delta);
496 e->cpu_time_relative_to_base -= delta;
497 }
498 }));
Dave Barachc3799992016-08-15 11:12:27 -0400499 /* *INDENT-ON* */
500 }
Ed Warnickecb9cada2015-12-08 15:45:58 -0700501
502 /* See which overflow elements fit now. */
503 {
Dave Barachc3799992016-08-15 11:12:27 -0400504 timing_wheel_overflow_elt_t *oe;
505 /* *INDENT-OFF* */
Damjan Marionb2c31b62020-12-13 21:47:40 +0100506 pool_foreach (oe, w->overflow_pool) {
Ed Warnickecb9cada2015-12-08 15:45:58 -0700507 /* 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;
Andrew Yourtchenkofa5231d2017-02-01 14:08:21 +0000511 if (ti <= w->current_time_index)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700512 {
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). */
Andrew Yourtchenkofa5231d2017-02-01 14:08:21 +0000515 /* Note: the ti == w->current_time_index means it is also an expired timer */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700516 if (! elt_is_deleted (w, oe->user_data))
517 vec_add1 (expired_user_data, oe->user_data);
518 }
519 else
520 timing_wheel_insert_helper (w, oe->cpu_time, oe->user_data);
521 pool_put (w->overflow_pool, oe);
522 }
Damjan Marionb2c31b62020-12-13 21:47:40 +0100523 }
Dave Barachc3799992016-08-15 11:12:27 -0400524 /* *INDENT-ON* */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700525 }
Klement Sekerae5af88c2016-11-11 05:58:10 +0100526 return expired_user_data;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700527}
528
529static u32 *
530refill_level (timing_wheel_t * w,
531 uword level_index,
532 u64 advance_cpu_time,
533 uword from_wheel_index,
Dave Barachc3799992016-08-15 11:12:27 -0400534 uword to_wheel_index, u32 * expired_user_data)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700535{
Dave Barachc3799992016-08-15 11:12:27 -0400536 timing_wheel_level_t *level;
537 timing_wheel_elt_t *to_insert = w->unexpired_elts_pending_insert;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700538 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);
Dave Barachc3799992016-08-15 11:12:27 -0400547 if (!level->occupancy_bitmap)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700548 goto done;
549
550 while (1)
551 {
Dave Barachc3799992016-08-15 11:12:27 -0400552 timing_wheel_elt_t *e, *es;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700553
Dave Barachc3799992016-08-15 11:12:27 -0400554 if (clib_bitmap_get_no_check
555 (level->occupancy_bitmap, from_wheel_index))
Ed Warnickecb9cada2015-12-08 15:45:58 -0700556 {
557 es = level->elts[from_wheel_index];
558 level->elts[from_wheel_index] = 0;
Dave Barachc3799992016-08-15 11:12:27 -0400559 clib_bitmap_set_no_check (level->occupancy_bitmap, from_wheel_index,
560 0);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700561
562 vec_foreach (e, es)
Dave Barachc3799992016-08-15 11:12:27 -0400563 {
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 }
Ed Warnickecb9cada2015-12-08 15:45:58 -0700575 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
584 timing_wheel_validate (w);
Dave Barachc3799992016-08-15 11:12:27 -0400585done:
Ed Warnickecb9cada2015-12-08 15:45:58 -0700586 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. */
591u32 *
Dave Barachc3799992016-08-15 11:12:27 -0400592timing_wheel_advance (timing_wheel_t * w, u64 advance_cpu_time,
593 u32 * expired_user_data,
Ed Warnickecb9cada2015-12-08 15:45:58 -0700594 u64 * next_expiring_element_cpu_time)
595{
Dave Barachc3799992016-08-15 11:12:27 -0400596 timing_wheel_level_t *level;
Ed Warnickecb9cada2015-12-08 15:45:58 -0700597 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 {
615 if (w->unexpired_elts_pending_insert)
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,
Dave Barachc3799992016-08-15 11:12:27 -0400628 c, a, expired_user_data);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700629 current_ti >>= w->log2_bins_per_wheel;
630 advance_ti >>= w->log2_bins_per_wheel;
631 level_index++;
632 }
633 }
634 }
635
Dave Barachc3799992016-08-15 11:12:27 -0400636 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);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700640
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);
Dave Barachc3799992016-08-15 11:12:27 -0400650 /* *INDENT-OFF* */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700651 clib_bitmap_foreach (wi, level->occupancy_bitmap, ({
652 expired_user_data = expire_bin (w, level_index, wi, advance_cpu_time,
653 expired_user_data);
654 }));
Dave Barachc3799992016-08-15 11:12:27 -0400655 /* *INDENT-ON* */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700656 }
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);
Dave Barachc3799992016-08-15 11:12:27 -0400662 wi = current_time_wheel_index (w, level_index);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700663 if (level->occupancy_bitmap)
664 while (1)
665 {
666 if (clib_bitmap_get_no_check (level->occupancy_bitmap, wi))
Dave Barachc3799992016-08-15 11:12:27 -0400667 expired_user_data =
668 expire_bin (w, advance_level_index, wi, advance_cpu_time,
669 expired_user_data);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700670
Andrew Yourtchenkofa5231d2017-02-01 14:08:21 +0000671 /* When we jump out, we have already just expired the bin,
672 corresponding to advance_wheel_index */
Ed Warnickecb9cada2015-12-08 15:45:58 -0700673 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
683 if (vec_len (w->unexpired_elts_pending_insert) > 0)
684 {
Dave Barachc3799992016-08-15 11:12:27 -0400685 timing_wheel_elt_t *e;
686 vec_foreach (e, w->unexpired_elts_pending_insert) insert_elt (w, e);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700687 _vec_len (w->unexpired_elts_pending_insert) = 0;
688 }
689
690 /* Don't advance until necessary. */
Andrew Yourtchenkofa5231d2017-02-01 14:08:21 +0000691 /* 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. */
Dave Barachc3799992016-08-15 11:12:27 -0400694 while (PREDICT_FALSE
695 (advance_time_index >= w->time_index_next_cpu_time_base_update))
Klement Sekerae5af88c2016-11-11 05:58:10 +0100696 expired_user_data = advance_cpu_time_base (w, expired_user_data);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700697
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 {
708 min_t = timing_wheel_next_expiring_elt_time (w);
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
Dave Barachc3799992016-08-15 11:12:27 -0400718u8 *
719format_timing_wheel (u8 * s, va_list * va)
Ed Warnickecb9cada2015-12-08 15:45:58 -0700720{
Dave Barachc3799992016-08-15 11:12:27 -0400721 timing_wheel_t *w = va_arg (*va, timing_wheel_t *);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700722 int verbose = va_arg (*va, int);
Christophe Fontained3c008d2017-10-02 18:10:54 +0200723 u32 indent = format_get_indent (s);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700724
725 s = format (s, "level 0: %.4e - %.4e secs, 2^%d - 2^%d clocks",
726 (f64) (1 << w->log2_clocks_per_bin) / w->cpu_clocks_per_second,
Dave Barachc3799992016-08-15 11:12:27 -0400727 (f64) (1 << w->log2_clocks_per_wheel) /
728 w->cpu_clocks_per_second, w->log2_clocks_per_bin,
729 w->log2_clocks_per_wheel);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700730
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,
737 w->stats.cpu_time_base_advances,
Dave Barachc3799992016-08-15 11:12:27 -0400738 (f64) ((u64) 1 << w->n_wheel_elt_time_bits) /
739 w->cpu_clocks_per_second);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700740
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,
Dave Barachc3799992016-08-15 11:12:27 -0400744 l,
745 l <
746 vec_len (w->stats.refills) ? w->stats.
747 refills[l] : (u64) 0);
Ed Warnickecb9cada2015-12-08 15:45:58 -0700748 }
749
750 return s;
751}
Dave Barachc3799992016-08-15 11:12:27 -0400752
753/*
754 * fd.io coding-style-patch-verification: ON
755 *
756 * Local Variables:
757 * eval: (c-set-style "gnu")
758 * End:
759 */