Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 21 | timing_wheel_init (timing_wheel_t * w, u64 current_cpu_time, |
| 22 | f64 cpu_clocks_per_second) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 31 | w->log2_clocks_per_bin = |
| 32 | max_log2 (w->cpu_clocks_per_second * w->min_sched_time); |
| 33 | w->log2_bins_per_wheel = |
| 34 | max_log2 (w->cpu_clocks_per_second * w->max_sched_time); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 35 | w->log2_bins_per_wheel -= w->log2_clocks_per_bin; |
| 36 | w->log2_clocks_per_wheel = w->log2_bins_per_wheel + w->log2_clocks_per_bin; |
| 37 | w->bins_per_wheel = 1 << w->log2_bins_per_wheel; |
| 38 | w->bins_per_wheel_mask = w->bins_per_wheel - 1; |
| 39 | |
| 40 | w->current_time_index = current_cpu_time >> w->log2_clocks_per_bin; |
| 41 | |
| 42 | if (w->n_wheel_elt_time_bits <= 0 || |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 43 | w->n_wheel_elt_time_bits >= STRUCT_BITS_OF (timing_wheel_elt_t, |
| 44 | cpu_time_relative_to_base)) |
| 45 | w->n_wheel_elt_time_bits = |
| 46 | STRUCT_BITS_OF (timing_wheel_elt_t, cpu_time_relative_to_base) - 1; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 47 | |
| 48 | w->cpu_time_base = current_cpu_time; |
| 49 | w->time_index_next_cpu_time_base_update |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 50 | = |
| 51 | w->current_time_index + |
| 52 | ((u64) 1 << (w->n_wheel_elt_time_bits - w->log2_clocks_per_bin)); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 53 | } |
| 54 | |
| 55 | always_inline uword |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 56 | get_level_and_relative_time (timing_wheel_t * w, u64 cpu_time, |
| 57 | uword * rtime_result) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 58 | { |
| 59 | u64 dt, rtime; |
| 60 | uword level_index; |
| 61 | |
| 62 | dt = (cpu_time >> w->log2_clocks_per_bin); |
| 63 | |
| 64 | /* Time should always move forward. */ |
| 65 | ASSERT (dt >= w->current_time_index); |
| 66 | |
| 67 | dt -= w->current_time_index; |
| 68 | |
| 69 | /* Find level and offset within level. Level i has bins of size 2^((i+1)*M) */ |
| 70 | rtime = dt; |
| 71 | for (level_index = 0; (rtime >> w->log2_bins_per_wheel) != 0; level_index++) |
| 72 | rtime = (rtime >> w->log2_bins_per_wheel) - 1; |
| 73 | |
| 74 | /* Return offset within level and level index. */ |
| 75 | ASSERT (rtime < w->bins_per_wheel); |
| 76 | *rtime_result = rtime; |
| 77 | return level_index; |
| 78 | } |
| 79 | |
| 80 | always_inline uword |
| 81 | time_index_to_wheel_index (timing_wheel_t * w, uword level_index, u64 ti) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 82 | { |
| 83 | return (ti >> (level_index * w->log2_bins_per_wheel)) & |
| 84 | w->bins_per_wheel_mask; |
| 85 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 86 | |
| 87 | /* Find current time on this level. */ |
| 88 | always_inline uword |
| 89 | current_time_wheel_index (timing_wheel_t * w, uword level_index) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 90 | { |
| 91 | return time_index_to_wheel_index (w, level_index, w->current_time_index); |
| 92 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 93 | |
| 94 | /* Circular wheel indexing. */ |
| 95 | always_inline uword |
| 96 | wheel_add (timing_wheel_t * w, word x) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 97 | { |
| 98 | return x & w->bins_per_wheel_mask; |
| 99 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 100 | |
| 101 | always_inline uword |
| 102 | rtime_to_wheel_index (timing_wheel_t * w, uword level_index, uword rtime) |
| 103 | { |
| 104 | uword t = current_time_wheel_index (w, level_index); |
| 105 | return wheel_add (w, t + rtime); |
| 106 | } |
| 107 | |
| 108 | static clib_error_t * |
| 109 | validate_level (timing_wheel_t * w, uword level_index, uword * n_elts) |
| 110 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 111 | timing_wheel_level_t *level; |
| 112 | timing_wheel_elt_t *e; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 113 | uword wi; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 114 | clib_error_t *error = 0; |
| 115 | |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 127 | _(clib_bitmap_get_no_check (level->occupancy_bitmap, wi) == |
| 128 | (vec_len (level->elts[wi]) > 0)); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 129 | |
| 130 | *n_elts += vec_len (level->elts[wi]); |
| 131 | |
| 132 | vec_foreach (e, level->elts[wi]) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 133 | { |
| 134 | /* Validate time bin and level. */ |
| 135 | u64 e_time; |
| 136 | uword e_ti, e_li, e_wi; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 137 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 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); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 141 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 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 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 156 | } |
| 157 | |
| 158 | #undef _ |
| 159 | |
| 160 | return error; |
| 161 | } |
| 162 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 163 | void |
| 164 | timing_wheel_validate (timing_wheel_t * w) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 165 | { |
| 166 | uword l; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 167 | clib_error_t *error = 0; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 168 | uword n_elts; |
| 169 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 170 | if (!w->validate) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 171 | return; |
| 172 | |
| 173 | n_elts = pool_elts (w->overflow_pool); |
| 174 | for (l = 0; l < vec_len (w->levels); l++) |
| 175 | { |
| 176 | error = validate_level (w, l, &n_elts); |
| 177 | if (error) |
| 178 | clib_error_report (error); |
| 179 | } |
| 180 | } |
| 181 | |
| 182 | always_inline void |
| 183 | free_elt_vector (timing_wheel_t * w, timing_wheel_elt_t * ev) |
| 184 | { |
| 185 | /* Poison free elements so we never use them by mistake. */ |
| 186 | if (CLIB_DEBUG > 0) |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame] | 187 | clib_memset (ev, ~0, vec_len (ev) * sizeof (ev[0])); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 188 | _vec_len (ev) = 0; |
| 189 | vec_add1 (w->free_elt_vectors, ev); |
| 190 | } |
| 191 | |
| 192 | static timing_wheel_elt_t * |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 193 | insert_helper (timing_wheel_t * w, uword level_index, uword rtime) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 194 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 195 | timing_wheel_level_t *level; |
| 196 | timing_wheel_elt_t *e; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 203 | if (PREDICT_FALSE (!level->elts)) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 204 | { |
| 205 | uword max = w->bins_per_wheel - 1; |
| 206 | clib_bitmap_validate (level->occupancy_bitmap, max); |
| 207 | vec_validate (level->elts, max); |
| 208 | } |
| 209 | |
| 210 | wheel_index = rtime_to_wheel_index (w, level_index, rtime); |
| 211 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 212 | level->occupancy_bitmap = |
| 213 | clib_bitmap_ori (level->occupancy_bitmap, wheel_index); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 214 | |
| 215 | /* Allocate an elt vector from free list if there is one. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 216 | if (!level->elts[wheel_index] && vec_len (w->free_elt_vectors)) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 226 | static void |
| 227 | timing_wheel_insert_helper (timing_wheel_t * w, u64 insert_cpu_time, |
| 228 | u32 user_data) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 229 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 230 | timing_wheel_elt_t *e; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 231 | u64 dt; |
| 232 | uword rtime, level_index; |
| 233 | |
| 234 | level_index = get_level_and_relative_time (w, insert_cpu_time, &rtime); |
| 235 | |
| 236 | dt = insert_cpu_time - w->cpu_time_base; |
| 237 | if (PREDICT_TRUE (0 == (dt >> BITS (e->cpu_time_relative_to_base)))) |
| 238 | { |
| 239 | e = insert_helper (w, level_index, rtime); |
| 240 | e->user_data = user_data; |
| 241 | e->cpu_time_relative_to_base = dt; |
Andrew Yourtchenko | fa5231d | 2017-02-01 14:08:21 +0000 | [diff] [blame] | 242 | if (insert_cpu_time < w->cached_min_cpu_time_on_wheel) |
| 243 | w->cached_min_cpu_time_on_wheel = insert_cpu_time; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 244 | } |
| 245 | else |
| 246 | { |
| 247 | /* Time too far in the future: add to overflow vector. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 248 | timing_wheel_overflow_elt_t *oe; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 249 | pool_get (w->overflow_pool, oe); |
| 250 | oe->user_data = user_data; |
| 251 | oe->cpu_time = insert_cpu_time; |
| 252 | } |
| 253 | } |
| 254 | |
| 255 | always_inline uword |
| 256 | elt_is_deleted (timing_wheel_t * w, u32 user_data) |
| 257 | { |
| 258 | return (hash_elts (w->deleted_user_data_hash) > 0 |
| 259 | && hash_get (w->deleted_user_data_hash, user_data)); |
| 260 | } |
| 261 | |
| 262 | static timing_wheel_elt_t * |
| 263 | delete_user_data (timing_wheel_elt_t * elts, u32 user_data) |
| 264 | { |
| 265 | uword found_match; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 266 | timing_wheel_elt_t *e, *new_elts; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 272 | { |
| 273 | found_match = e->user_data == user_data; |
| 274 | if (found_match) |
| 275 | break; |
| 276 | } |
| 277 | if (!found_match) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 283 | { |
| 284 | if (e->user_data != user_data) |
| 285 | vec_add1 (new_elts, e[0]); |
| 286 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 287 | |
| 288 | vec_free (elts); |
| 289 | return new_elts; |
| 290 | } |
| 291 | |
| 292 | /* Insert user data on wheel at given CPU time stamp. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 293 | void |
| 294 | timing_wheel_insert (timing_wheel_t * w, u64 insert_cpu_time, u32 user_data) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 295 | { |
| 296 | /* Remove previously deleted elements. */ |
| 297 | if (elt_is_deleted (w, user_data)) |
| 298 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 299 | timing_wheel_level_t *l; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 300 | uword wi; |
| 301 | |
| 302 | /* Delete elts with given user data so that stale events don't expire. */ |
| 303 | vec_foreach (l, w->levels) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 304 | { |
| 305 | /* *INDENT-OFF* */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 306 | 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 Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 311 | /* *INDENT-ON* */ |
| 312 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 313 | |
| 314 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 315 | timing_wheel_overflow_elt_t *oe; |
| 316 | /* *INDENT-OFF* */ |
Damjan Marion | b2c31b6 | 2020-12-13 21:47:40 +0100 | [diff] [blame^] | 317 | pool_foreach (oe, w->overflow_pool) { |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 318 | if (oe->user_data == user_data) |
| 319 | pool_put (w->overflow_pool, oe); |
Damjan Marion | b2c31b6 | 2020-12-13 21:47:40 +0100 | [diff] [blame^] | 320 | } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 321 | /* *INDENT-ON* */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 330 | void |
| 331 | timing_wheel_delete (timing_wheel_t * w, u32 user_data) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 332 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 333 | if (!w->deleted_user_data_hash) |
| 334 | w->deleted_user_data_hash = |
| 335 | hash_create ( /* capacity */ 0, /* value bytes */ 0); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 336 | |
| 337 | hash_set1 (w->deleted_user_data_hash, user_data); |
| 338 | } |
| 339 | |
| 340 | /* Returns time of next expiring element. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 341 | u64 |
| 342 | timing_wheel_next_expiring_elt_time (timing_wheel_t * w) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 343 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 344 | timing_wheel_level_t *l; |
| 345 | timing_wheel_elt_t *e; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 354 | { |
| 355 | if (!l->occupancy_bitmap) |
| 356 | continue; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 357 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 358 | 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 Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 367 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 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]) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 375 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 376 | min_dt = |
| 377 | clib_min (min_dt, e->cpu_time_relative_to_base); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 378 | } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 379 | } |
| 380 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 381 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 382 | min_t = w->cpu_time_base + min_dt; |
| 383 | goto done; |
| 384 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 385 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 386 | wi = wheel_add (w, wi + 1); |
| 387 | if (wi == wi0) |
| 388 | break; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 389 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 390 | wrapped = wi != wi + 1; |
| 391 | } |
| 392 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 393 | |
| 394 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 395 | timing_wheel_overflow_elt_t *oe; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 396 | |
| 397 | if (min_dt != ~0) |
| 398 | min_t = w->cpu_time_base + min_dt; |
| 399 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 400 | /* *INDENT-OFF* */ |
Damjan Marion | b2c31b6 | 2020-12-13 21:47:40 +0100 | [diff] [blame^] | 401 | pool_foreach (oe, w->overflow_pool) |
| 402 | { min_t = clib_min (min_t, oe->cpu_time); } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 403 | /* *INDENT-ON* */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 404 | |
| 405 | done: |
| 406 | return min_t; |
| 407 | } |
| 408 | } |
| 409 | |
| 410 | static inline void |
| 411 | insert_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 | |
| 417 | always_inline u64 |
| 418 | elt_cpu_time (timing_wheel_t * w, timing_wheel_elt_t * e) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 419 | { |
| 420 | return w->cpu_time_base + e->cpu_time_relative_to_base; |
| 421 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 422 | |
| 423 | always_inline void |
| 424 | 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 | 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 * |
| 438 | expire_bin (timing_wheel_t * w, |
| 439 | uword level_index, |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 440 | uword wheel_index, u64 advance_cpu_time, u32 * expired_user_data) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 441 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 442 | timing_wheel_level_t *level = vec_elt_at_index (w->levels, level_index); |
| 443 | timing_wheel_elt_t *e; |
| 444 | u32 *x; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 457 | j += !elt_is_deleted (w, e[i].user_data); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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. */ |
Klement Sekera | e5af88c | 2016-11-11 05:58:10 +0100 | [diff] [blame] | 473 | static u32 * |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 474 | advance_cpu_time_base (timing_wheel_t * w, u32 * expired_user_data) |
| 475 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 476 | timing_wheel_level_t *l; |
| 477 | timing_wheel_elt_t *e; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 478 | 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 Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 486 | { |
| 487 | uword wi; |
| 488 | /* *INDENT-OFF* */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 489 | 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 Yourtchenko | fa5231d | 2017-02-01 14:08:21 +0000 | [diff] [blame] | 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. */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 495 | ASSERT (e->cpu_time_relative_to_base >= delta); |
| 496 | e->cpu_time_relative_to_base -= delta; |
| 497 | } |
| 498 | })); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 499 | /* *INDENT-ON* */ |
| 500 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 501 | |
| 502 | /* See which overflow elements fit now. */ |
| 503 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 504 | timing_wheel_overflow_elt_t *oe; |
| 505 | /* *INDENT-OFF* */ |
Damjan Marion | b2c31b6 | 2020-12-13 21:47:40 +0100 | [diff] [blame^] | 506 | pool_foreach (oe, w->overflow_pool) { |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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; |
Andrew Yourtchenko | fa5231d | 2017-02-01 14:08:21 +0000 | [diff] [blame] | 511 | if (ti <= w->current_time_index) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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). */ |
Andrew Yourtchenko | fa5231d | 2017-02-01 14:08:21 +0000 | [diff] [blame] | 515 | /* Note: the ti == w->current_time_index means it is also an expired timer */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 516 | 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 Marion | b2c31b6 | 2020-12-13 21:47:40 +0100 | [diff] [blame^] | 523 | } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 524 | /* *INDENT-ON* */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 525 | } |
Klement Sekera | e5af88c | 2016-11-11 05:58:10 +0100 | [diff] [blame] | 526 | return expired_user_data; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 527 | } |
| 528 | |
| 529 | static u32 * |
| 530 | refill_level (timing_wheel_t * w, |
| 531 | uword level_index, |
| 532 | u64 advance_cpu_time, |
| 533 | uword from_wheel_index, |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 534 | uword to_wheel_index, u32 * expired_user_data) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 535 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 536 | timing_wheel_level_t *level; |
| 537 | timing_wheel_elt_t *to_insert = w->unexpired_elts_pending_insert; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 547 | if (!level->occupancy_bitmap) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 548 | goto done; |
| 549 | |
| 550 | while (1) |
| 551 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 552 | timing_wheel_elt_t *e, *es; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 553 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 554 | if (clib_bitmap_get_no_check |
| 555 | (level->occupancy_bitmap, from_wheel_index)) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 556 | { |
| 557 | es = level->elts[from_wheel_index]; |
| 558 | level->elts[from_wheel_index] = 0; |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 559 | clib_bitmap_set_no_check (level->occupancy_bitmap, from_wheel_index, |
| 560 | 0); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 561 | |
| 562 | vec_foreach (e, es) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 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 | } |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 | |
| 584 | timing_wheel_validate (w); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 585 | done: |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 * |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 592 | timing_wheel_advance (timing_wheel_t * w, u64 advance_cpu_time, |
| 593 | u32 * expired_user_data, |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 594 | u64 * next_expiring_element_cpu_time) |
| 595 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 596 | timing_wheel_level_t *level; |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 | { |
| 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 Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 628 | c, a, expired_user_data); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 629 | current_ti >>= w->log2_bins_per_wheel; |
| 630 | advance_ti >>= w->log2_bins_per_wheel; |
| 631 | level_index++; |
| 632 | } |
| 633 | } |
| 634 | } |
| 635 | |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 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); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 650 | /* *INDENT-OFF* */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 651 | 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 Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 655 | /* *INDENT-ON* */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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); |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 662 | wi = current_time_wheel_index (w, level_index); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 663 | if (level->occupancy_bitmap) |
| 664 | while (1) |
| 665 | { |
| 666 | if (clib_bitmap_get_no_check (level->occupancy_bitmap, wi)) |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 667 | expired_user_data = |
| 668 | expire_bin (w, advance_level_index, wi, advance_cpu_time, |
| 669 | expired_user_data); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 670 | |
Andrew Yourtchenko | fa5231d | 2017-02-01 14:08:21 +0000 | [diff] [blame] | 671 | /* When we jump out, we have already just expired the bin, |
| 672 | corresponding to advance_wheel_index */ |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 | |
| 683 | if (vec_len (w->unexpired_elts_pending_insert) > 0) |
| 684 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 685 | timing_wheel_elt_t *e; |
| 686 | vec_foreach (e, w->unexpired_elts_pending_insert) insert_elt (w, e); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 687 | _vec_len (w->unexpired_elts_pending_insert) = 0; |
| 688 | } |
| 689 | |
| 690 | /* Don't advance until necessary. */ |
Andrew Yourtchenko | fa5231d | 2017-02-01 14:08:21 +0000 | [diff] [blame] | 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. */ |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 694 | while (PREDICT_FALSE |
| 695 | (advance_time_index >= w->time_index_next_cpu_time_base_update)) |
Klement Sekera | e5af88c | 2016-11-11 05:58:10 +0100 | [diff] [blame] | 696 | expired_user_data = advance_cpu_time_base (w, expired_user_data); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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 | { |
| 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 Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 718 | u8 * |
| 719 | format_timing_wheel (u8 * s, va_list * va) |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 720 | { |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 721 | timing_wheel_t *w = va_arg (*va, timing_wheel_t *); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 722 | int verbose = va_arg (*va, int); |
Christophe Fontaine | d3c008d | 2017-10-02 18:10:54 +0200 | [diff] [blame] | 723 | u32 indent = format_get_indent (s); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 724 | |
| 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 Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 727 | (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 Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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, |
| 737 | w->stats.cpu_time_base_advances, |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 738 | (f64) ((u64) 1 << w->n_wheel_elt_time_bits) / |
| 739 | w->cpu_clocks_per_second); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 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, |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 744 | l, |
| 745 | l < |
| 746 | vec_len (w->stats.refills) ? w->stats. |
| 747 | refills[l] : (u64) 0); |
Ed Warnicke | cb9cada | 2015-12-08 15:45:58 -0700 | [diff] [blame] | 748 | } |
| 749 | |
| 750 | return s; |
| 751 | } |
Dave Barach | c379999 | 2016-08-15 11:12:27 -0400 | [diff] [blame] | 752 | |
| 753 | /* |
| 754 | * fd.io coding-style-patch-verification: ON |
| 755 | * |
| 756 | * Local Variables: |
| 757 | * eval: (c-set-style "gnu") |
| 758 | * End: |
| 759 | */ |