Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (c) 2016 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 | |
| 16 | /** @file |
| 17 | * @brief TW timer implementation TEMPLATE ONLY, do not compile directly |
| 18 | * |
| 19 | * |
| 20 | */ |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 21 | #if TW_START_STOP_TRACE_SIZE > 0 |
| 22 | |
| 23 | void TW (tw_timer_trace) (TWT (tw_timer_wheel) * tw, u32 timer_id, |
| 24 | u32 pool_index, u32 handle) |
| 25 | { |
| 26 | TWT (trace) * t = &tw->traces[tw->trace_index]; |
| 27 | |
| 28 | t->timer_id = timer_id; |
| 29 | t->pool_index = pool_index; |
| 30 | t->handle = handle; |
| 31 | |
| 32 | tw->trace_index++; |
| 33 | if (tw->trace_index == TW_START_STOP_TRACE_SIZE) |
| 34 | { |
| 35 | tw->trace_index = 0; |
| 36 | tw->trace_wrapped++; |
| 37 | } |
| 38 | } |
| 39 | |
| 40 | void TW (tw_search_trace) (TWT (tw_timer_wheel) * tw, u32 handle) |
| 41 | { |
| 42 | u32 i, start_pos; |
| 43 | TWT (trace) * t; |
| 44 | char *s = "bogus!"; |
| 45 | |
| 46 | /* reverse search for the supplied handle */ |
| 47 | |
| 48 | start_pos = tw->trace_index; |
| 49 | if (start_pos == 0) |
| 50 | start_pos = TW_START_STOP_TRACE_SIZE - 1; |
| 51 | else |
| 52 | start_pos--; |
| 53 | |
| 54 | for (i = start_pos; i > 0; i--) |
| 55 | { |
| 56 | t = &tw->traces[i]; |
| 57 | if (t->handle == handle) |
| 58 | { |
| 59 | switch (t->timer_id) |
| 60 | { |
| 61 | case 0xFF: |
| 62 | s = "stopped"; |
| 63 | break; |
| 64 | case 0xFE: |
| 65 | s = "expired"; |
| 66 | break; |
| 67 | default: |
| 68 | s = "started"; |
| 69 | break; |
| 70 | } |
| 71 | fformat (stderr, "handle 0x%x (%d) %s at trace %d\n", |
| 72 | handle, handle, s, i); |
| 73 | } |
| 74 | } |
| 75 | if (tw->trace_wrapped > 0) |
| 76 | { |
| 77 | for (i = TW_START_STOP_TRACE_SIZE; i >= tw->trace_index; i--) |
| 78 | { |
| 79 | t = &tw->traces[i]; |
| 80 | if (t->handle == handle) |
| 81 | { |
| 82 | switch (t->timer_id) |
| 83 | { |
| 84 | case 0xFF: |
| 85 | s = "stopped"; |
| 86 | break; |
| 87 | case 0xFE: |
| 88 | s = "expired"; |
| 89 | break; |
| 90 | default: |
| 91 | s = "started"; |
| 92 | break; |
| 93 | } |
| 94 | fformat (stderr, "handle 0x%x (%d) %s at trace %d\n", |
| 95 | handle, handle, s, i); |
| 96 | } |
| 97 | } |
| 98 | } |
| 99 | } |
| 100 | #endif /* TW_START_STOP_TRACE_SIZE > 0 */ |
| 101 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 102 | static inline u32 |
| 103 | TW (make_internal_timer_handle) (u32 pool_index, u32 timer_id) |
| 104 | { |
| 105 | u32 handle; |
| 106 | |
| 107 | ASSERT (timer_id < TW_TIMERS_PER_OBJECT); |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 108 | #if LOG2_TW_TIMERS_PER_OBJECT > 0 |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 109 | ASSERT (pool_index < (1 << (32 - LOG2_TW_TIMERS_PER_OBJECT))); |
| 110 | |
| 111 | handle = (timer_id << (32 - LOG2_TW_TIMERS_PER_OBJECT)) | (pool_index); |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 112 | #else |
| 113 | handle = pool_index; |
| 114 | #endif |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 115 | return handle; |
| 116 | } |
| 117 | |
| 118 | static inline void |
| 119 | timer_addhead (TWT (tw_timer) * pool, u32 head_index, u32 new_index) |
| 120 | { |
| 121 | TWT (tw_timer) * head = pool_elt_at_index (pool, head_index); |
| 122 | TWT (tw_timer) * old_first; |
| 123 | u32 old_first_index; |
| 124 | TWT (tw_timer) * new; |
| 125 | |
| 126 | new = pool_elt_at_index (pool, new_index); |
| 127 | |
| 128 | if (PREDICT_FALSE (head->next == head_index)) |
| 129 | { |
| 130 | head->next = head->prev = new_index; |
| 131 | new->next = new->prev = head_index; |
| 132 | return; |
| 133 | } |
| 134 | |
| 135 | old_first_index = head->next; |
| 136 | old_first = pool_elt_at_index (pool, old_first_index); |
| 137 | |
| 138 | new->next = old_first_index; |
| 139 | new->prev = old_first->prev; |
| 140 | old_first->prev = new_index; |
| 141 | head->next = new_index; |
| 142 | } |
| 143 | |
| 144 | static inline void |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 145 | timer_remove (TWT (tw_timer) * pool, TWT (tw_timer) * elt) |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 146 | { |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 147 | TWT (tw_timer) * next_elt, *prev_elt; |
| 148 | |
| 149 | ASSERT (elt->user_handle != ~0); |
| 150 | |
| 151 | next_elt = pool_elt_at_index (pool, elt->next); |
| 152 | prev_elt = pool_elt_at_index (pool, elt->prev); |
| 153 | |
| 154 | next_elt->prev = elt->prev; |
| 155 | prev_elt->next = elt->next; |
| 156 | |
| 157 | elt->prev = elt->next = ~0; |
| 158 | } |
| 159 | |
Florin Coras | 208daa1 | 2018-07-02 01:30:51 -0700 | [diff] [blame] | 160 | static inline void |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 161 | timer_add (TWT (tw_timer_wheel) * tw, TWT (tw_timer) * t, u64 interval) |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 162 | { |
| 163 | #if TW_TIMER_WHEELS > 1 |
| 164 | u16 slow_ring_offset; |
| 165 | u32 carry; |
| 166 | #endif |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 167 | #if TW_TIMER_WHEELS > 2 |
| 168 | u16 glacier_ring_offset; |
| 169 | #endif |
| 170 | #if TW_OVERFLOW_VECTOR > 0 |
| 171 | u64 interval_plus_time_to_wrap, triple_wrap_mask; |
| 172 | #endif |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 173 | u16 fast_ring_offset; |
| 174 | tw_timer_wheel_slot_t *ts; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 175 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 176 | /* Factor interval into 1..3 wheel offsets */ |
| 177 | #if TW_TIMER_WHEELS > 2 |
| 178 | #if TW_OVERFLOW_VECTOR > 0 |
| 179 | /* |
| 180 | * This is tricky. Put a timer onto the overflow |
| 181 | * vector if the interval PLUS the time |
| 182 | * until the next triple-wrap exceeds one full revolution |
| 183 | * of all three wheels. |
| 184 | */ |
| 185 | triple_wrap_mask = (1 << (3 * TW_RING_SHIFT)) - 1; |
| 186 | interval_plus_time_to_wrap = |
| 187 | interval + (tw->current_tick & triple_wrap_mask); |
| 188 | if ((interval_plus_time_to_wrap >= 1 << (3 * TW_RING_SHIFT))) |
| 189 | { |
| 190 | t->expiration_time = tw->current_tick + interval; |
| 191 | ts = &tw->overflow; |
| 192 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 193 | #if TW_START_STOP_TRACE_SIZE > 0 |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 194 | TW (tw_timer_trace) (tw, timer_id, user_id, t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 195 | #endif |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 196 | return; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 197 | } |
| 198 | #endif |
| 199 | |
| 200 | glacier_ring_offset = interval >> (2 * TW_RING_SHIFT); |
Dave Barach | 28b70af | 2017-06-13 17:04:28 -0400 | [diff] [blame] | 201 | ASSERT ((u64) glacier_ring_offset < TW_SLOTS_PER_RING); |
| 202 | interval -= (((u64) glacier_ring_offset) << (2 * TW_RING_SHIFT)); |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 203 | #endif |
| 204 | #if TW_TIMER_WHEELS > 1 |
| 205 | slow_ring_offset = interval >> TW_RING_SHIFT; |
Dave Barach | 28b70af | 2017-06-13 17:04:28 -0400 | [diff] [blame] | 206 | ASSERT ((u64) slow_ring_offset < TW_SLOTS_PER_RING); |
| 207 | interval -= (((u64) slow_ring_offset) << TW_RING_SHIFT); |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 208 | #endif |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 209 | fast_ring_offset = interval & TW_RING_MASK; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 210 | |
| 211 | /* |
| 212 | * Account for the current wheel positions(s) |
| 213 | * This is made slightly complicated by the fact that the current |
| 214 | * index vector will contain (TW_SLOTS_PER_RING, ...) when |
| 215 | * the actual position is (0, ...) |
| 216 | */ |
| 217 | |
| 218 | fast_ring_offset += tw->current_index[TW_TIMER_RING_FAST] & TW_RING_MASK; |
| 219 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 220 | #if TW_TIMER_WHEELS > 1 |
| 221 | carry = fast_ring_offset >= TW_SLOTS_PER_RING ? 1 : 0; |
| 222 | fast_ring_offset %= TW_SLOTS_PER_RING; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 223 | slow_ring_offset += (tw->current_index[TW_TIMER_RING_SLOW] & TW_RING_MASK) |
| 224 | + carry; |
| 225 | carry = slow_ring_offset >= TW_SLOTS_PER_RING ? 1 : 0; |
| 226 | slow_ring_offset %= TW_SLOTS_PER_RING; |
| 227 | #endif |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 228 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 229 | #if TW_TIMER_WHEELS > 2 |
| 230 | glacier_ring_offset += |
| 231 | (tw->current_index[TW_TIMER_RING_GLACIER] & TW_RING_MASK) + carry; |
| 232 | glacier_ring_offset %= TW_SLOTS_PER_RING; |
| 233 | #endif |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 234 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 235 | #if TW_TIMER_WHEELS > 2 |
| 236 | if (glacier_ring_offset != |
| 237 | (tw->current_index[TW_TIMER_RING_GLACIER] & TW_RING_MASK)) |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 238 | { |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 239 | /* We'll need slow and fast ring offsets later */ |
| 240 | t->slow_ring_offset = slow_ring_offset; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 241 | t->fast_ring_offset = fast_ring_offset; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 242 | |
| 243 | ts = &tw->w[TW_TIMER_RING_GLACIER][glacier_ring_offset]; |
| 244 | |
| 245 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 246 | #if TW_START_STOP_TRACE_SIZE > 0 |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 247 | TW (tw_timer_trace) (tw, timer_id, user_id, t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 248 | #endif |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 249 | return; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 250 | } |
| 251 | #endif |
| 252 | |
| 253 | #if TW_TIMER_WHEELS > 1 |
| 254 | /* Timer expires more than 51.2 seconds from now? */ |
| 255 | if (slow_ring_offset != |
| 256 | (tw->current_index[TW_TIMER_RING_SLOW] & TW_RING_MASK)) |
| 257 | { |
| 258 | /* We'll need the fast ring offset later... */ |
| 259 | t->fast_ring_offset = fast_ring_offset; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 260 | |
| 261 | ts = &tw->w[TW_TIMER_RING_SLOW][slow_ring_offset]; |
| 262 | |
| 263 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 264 | #if TW_START_STOP_TRACE_SIZE > 0 |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 265 | TW (tw_timer_trace) (tw, timer_id, user_id, t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 266 | #endif |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 267 | return; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 268 | } |
| 269 | #else |
| 270 | fast_ring_offset %= TW_SLOTS_PER_RING; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 271 | #endif |
| 272 | |
| 273 | /* Timer expires less than one fast-ring revolution from now */ |
| 274 | ts = &tw->w[TW_TIMER_RING_FAST][fast_ring_offset]; |
| 275 | |
| 276 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 277 | |
| 278 | #if TW_FAST_WHEEL_BITMAP |
| 279 | tw->fast_slot_bitmap = clib_bitmap_set (tw->fast_slot_bitmap, |
| 280 | fast_ring_offset, 1); |
| 281 | #endif |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 282 | #if TW_START_STOP_TRACE_SIZE > 0 |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 283 | TW (tw_timer_trace) (tw, timer_id, user_id, t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 284 | #endif |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 285 | } |
| 286 | |
| 287 | /** |
| 288 | * @brief Start a Tw Timer |
| 289 | * @param tw_timer_wheel_t * tw timer wheel object pointer |
| 290 | * @param u32 user_id user defined timer id, presumably for a tw session |
| 291 | * @param u32 timer_id app-specific timer ID. 4 bits. |
| 292 | * @param u64 interval timer interval in ticks |
| 293 | * @returns handle needed to cancel the timer |
| 294 | */ |
| 295 | u32 |
| 296 | TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 user_id, u32 timer_id, |
| 297 | u64 interval) |
| 298 | { |
| 299 | TWT (tw_timer) * t; |
| 300 | |
| 301 | ASSERT (interval); |
| 302 | |
| 303 | pool_get (tw->timers, t); |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame] | 304 | clib_memset (t, 0xff, sizeof (*t)); |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 305 | |
| 306 | t->user_handle = TW (make_internal_timer_handle) (user_id, timer_id); |
| 307 | |
| 308 | timer_add (tw, t, interval); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 309 | return t - tw->timers; |
| 310 | } |
| 311 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 312 | #if TW_TIMER_SCAN_FOR_HANDLE > 0 |
| 313 | int TW (scan_for_handle) (TWT (tw_timer_wheel) * tw, u32 handle) |
| 314 | { |
| 315 | int i, j; |
| 316 | tw_timer_wheel_slot_t *ts; |
| 317 | TWT (tw_timer) * t, *head; |
| 318 | u32 next_index; |
| 319 | int rv = 0; |
| 320 | |
| 321 | for (i = 0; i < TW_TIMER_WHEELS; i++) |
| 322 | { |
| 323 | for (j = 0; j < TW_SLOTS_PER_RING; j++) |
| 324 | { |
| 325 | ts = &tw->w[i][j]; |
| 326 | head = pool_elt_at_index (tw->timers, ts->head_index); |
| 327 | next_index = head->next; |
| 328 | |
| 329 | while (next_index != ts->head_index) |
| 330 | { |
| 331 | t = pool_elt_at_index (tw->timers, next_index); |
| 332 | if (next_index == handle) |
| 333 | { |
| 334 | clib_warning ("handle %d found in ring %d slot %d", |
| 335 | handle, i, j); |
| 336 | clib_warning ("user handle 0x%x", t->user_handle); |
| 337 | rv = 1; |
| 338 | } |
| 339 | next_index = t->next; |
| 340 | } |
| 341 | } |
| 342 | } |
| 343 | return rv; |
| 344 | } |
| 345 | #endif /* TW_TIMER_SCAN_FOR_HANDLE */ |
| 346 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 347 | /** |
| 348 | * @brief Stop a tw timer |
| 349 | * @param tw_timer_wheel_t * tw timer wheel object pointer |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 350 | * @param u32 handle timer cancellation returned by tw_timer_start |
| 351 | */ |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 352 | void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle) |
| 353 | { |
| 354 | TWT (tw_timer) * t; |
| 355 | |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 356 | #if TW_TIMER_ALLOW_DUPLICATE_STOP |
| 357 | /* |
| 358 | * A vlib process may have its timer expire, and receive |
| 359 | * an event before the expiration is processed. |
| 360 | * That results in a duplicate tw_timer_stop. |
| 361 | */ |
| 362 | if (pool_is_free_index (tw->timers, handle)) |
| 363 | return; |
| 364 | #endif |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 365 | #if TW_START_STOP_TRACE_SIZE > 0 |
| 366 | TW (tw_timer_trace) (tw, ~0, ~0, handle); |
| 367 | #endif |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 368 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 369 | t = pool_elt_at_index (tw->timers, handle); |
| 370 | |
| 371 | /* in case of idiotic handle (e.g. passing a listhead index) */ |
| 372 | ASSERT (t->user_handle != ~0); |
| 373 | |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 374 | timer_remove (tw->timers, t); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 375 | |
| 376 | pool_put_index (tw->timers, handle); |
| 377 | } |
| 378 | |
Florin Coras | 40f9246 | 2018-08-01 16:25:45 -0700 | [diff] [blame] | 379 | int TW (tw_timer_handle_is_free) (TWT (tw_timer_wheel) * tw, u32 handle) |
| 380 | { |
| 381 | return pool_is_free_index (tw->timers, handle); |
| 382 | } |
| 383 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 384 | /** |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 385 | * @brief Update a tw timer |
| 386 | * @param tw_timer_wheel_t * tw timer wheel object pointer |
| 387 | * @param u32 handle timer returned by tw_timer_start |
| 388 | * @param u32 interval timer interval in ticks |
| 389 | */ |
| 390 | void TW (tw_timer_update) (TWT (tw_timer_wheel) * tw, u32 handle, |
| 391 | u64 interval) |
| 392 | { |
| 393 | TWT (tw_timer) * t; |
| 394 | t = pool_elt_at_index (tw->timers, handle); |
| 395 | timer_remove (tw->timers, t); |
| 396 | timer_add (tw, t, interval); |
| 397 | } |
| 398 | |
| 399 | /** |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 400 | * @brief Initialize a tw timer wheel template instance |
| 401 | * @param tw_timer_wheel_t * tw timer wheel object pointer |
| 402 | * @param void * expired_timer_callback. Passed a u32 * vector of |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 403 | * expired timer handles. The callback is optional. |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 404 | * @param f64 timer_interval_in_seconds |
| 405 | */ |
| 406 | void |
| 407 | TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw, |
| 408 | void *expired_timer_callback, |
Gabriel Ganne | 83ed1f4 | 2017-02-15 16:55:30 +0100 | [diff] [blame] | 409 | f64 timer_interval_in_seconds, u32 max_expirations) |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 410 | { |
| 411 | int ring, slot; |
| 412 | tw_timer_wheel_slot_t *ts; |
| 413 | TWT (tw_timer) * t; |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame] | 414 | clib_memset (tw, 0, sizeof (*tw)); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 415 | tw->expired_timer_callback = expired_timer_callback; |
Gabriel Ganne | 83ed1f4 | 2017-02-15 16:55:30 +0100 | [diff] [blame] | 416 | tw->max_expirations = max_expirations; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 417 | if (timer_interval_in_seconds == 0.0) |
| 418 | { |
| 419 | clib_warning ("timer interval is zero"); |
| 420 | abort (); |
| 421 | } |
| 422 | tw->timer_interval = timer_interval_in_seconds; |
| 423 | tw->ticks_per_second = 1.0 / timer_interval_in_seconds; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 424 | tw->first_expires_tick = ~0ULL; |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 425 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 426 | vec_validate (tw->expired_timer_handles, 0); |
| 427 | _vec_len (tw->expired_timer_handles) = 0; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 428 | |
| 429 | for (ring = 0; ring < TW_TIMER_WHEELS; ring++) |
| 430 | { |
| 431 | for (slot = 0; slot < TW_SLOTS_PER_RING; slot++) |
| 432 | { |
| 433 | ts = &tw->w[ring][slot]; |
| 434 | pool_get (tw->timers, t); |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame] | 435 | clib_memset (t, 0xff, sizeof (*t)); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 436 | t->next = t->prev = t - tw->timers; |
| 437 | ts->head_index = t - tw->timers; |
| 438 | } |
| 439 | } |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 440 | |
| 441 | #if TW_OVERFLOW_VECTOR > 0 |
| 442 | ts = &tw->overflow; |
| 443 | pool_get (tw->timers, t); |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame] | 444 | clib_memset (t, 0xff, sizeof (*t)); |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 445 | t->next = t->prev = t - tw->timers; |
| 446 | ts->head_index = t - tw->timers; |
| 447 | #endif |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 448 | } |
| 449 | |
| 450 | /** |
| 451 | * @brief Free a tw timer wheel template instance |
| 452 | * @param tw_timer_wheel_t * tw timer wheel object pointer |
| 453 | */ |
| 454 | void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw) |
| 455 | { |
| 456 | int i, j; |
| 457 | tw_timer_wheel_slot_t *ts; |
| 458 | TWT (tw_timer) * head, *t; |
| 459 | u32 next_index; |
| 460 | |
| 461 | for (i = 0; i < TW_TIMER_WHEELS; i++) |
| 462 | { |
| 463 | for (j = 0; j < TW_SLOTS_PER_RING; j++) |
| 464 | { |
| 465 | ts = &tw->w[i][j]; |
| 466 | head = pool_elt_at_index (tw->timers, ts->head_index); |
| 467 | next_index = head->next; |
| 468 | |
| 469 | while (next_index != ts->head_index) |
| 470 | { |
| 471 | t = pool_elt_at_index (tw->timers, next_index); |
| 472 | next_index = t->next; |
| 473 | pool_put (tw->timers, t); |
| 474 | } |
| 475 | pool_put (tw->timers, head); |
| 476 | } |
| 477 | } |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 478 | |
Dave Barach | 0f96673 | 2020-02-03 11:57:41 -0500 | [diff] [blame^] | 479 | #if TW_OVERFLOW_VECTOR > 0 |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 480 | ts = &tw->overflow; |
| 481 | head = pool_elt_at_index (tw->timers, ts->head_index); |
| 482 | next_index = head->next; |
| 483 | |
| 484 | while (next_index != ts->head_index) |
| 485 | { |
| 486 | t = pool_elt_at_index (tw->timers, next_index); |
| 487 | next_index = t->next; |
| 488 | pool_put (tw->timers, t); |
| 489 | } |
| 490 | pool_put (tw->timers, head); |
| 491 | #endif |
| 492 | |
Dave Barach | b7b9299 | 2018-10-17 10:38:51 -0400 | [diff] [blame] | 493 | clib_memset (tw, 0, sizeof (*tw)); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 494 | } |
| 495 | |
| 496 | /** |
| 497 | * @brief Advance a tw timer wheel. Calls the expired timer callback |
| 498 | * as needed. This routine should be called once every timer_interval seconds |
| 499 | * @param tw_timer_wheel_t * tw timer wheel template instance pointer |
| 500 | * @param f64 now the current time, e.g. from vlib_time_now(vm) |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 501 | * @returns u32 * vector of expired user handles |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 502 | */ |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 503 | static inline |
| 504 | u32 * TW (tw_timer_expire_timers_internal) (TWT (tw_timer_wheel) * tw, |
| 505 | f64 now, |
| 506 | u32 * callback_vector_arg) |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 507 | { |
| 508 | u32 nticks, i; |
| 509 | tw_timer_wheel_slot_t *ts; |
| 510 | TWT (tw_timer) * t, *head; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 511 | u32 *callback_vector; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 512 | u32 fast_wheel_index; |
| 513 | u32 next_index; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 514 | u32 slow_wheel_index __attribute__ ((unused)); |
| 515 | u32 glacier_wheel_index __attribute__ ((unused)); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 516 | |
| 517 | /* Shouldn't happen */ |
| 518 | if (PREDICT_FALSE (now < tw->next_run_time)) |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 519 | return callback_vector_arg; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 520 | |
| 521 | /* Number of ticks which have occurred */ |
| 522 | nticks = tw->ticks_per_second * (now - tw->last_run_time); |
| 523 | if (nticks == 0) |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 524 | return callback_vector_arg; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 525 | |
| 526 | /* Remember when we ran, compute next runtime */ |
| 527 | tw->next_run_time = (now + tw->timer_interval); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 528 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 529 | if (callback_vector_arg == 0) |
| 530 | { |
| 531 | _vec_len (tw->expired_timer_handles) = 0; |
| 532 | callback_vector = tw->expired_timer_handles; |
| 533 | } |
| 534 | else |
| 535 | callback_vector = callback_vector_arg; |
| 536 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 537 | for (i = 0; i < nticks; i++) |
| 538 | { |
| 539 | fast_wheel_index = tw->current_index[TW_TIMER_RING_FAST]; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 540 | if (TW_TIMER_WHEELS > 1) |
| 541 | slow_wheel_index = tw->current_index[TW_TIMER_RING_SLOW]; |
| 542 | if (TW_TIMER_WHEELS > 2) |
| 543 | glacier_wheel_index = tw->current_index[TW_TIMER_RING_GLACIER]; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 544 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 545 | #if TW_OVERFLOW_VECTOR > 0 |
| 546 | /* Triple odometer-click? Process the overflow vector... */ |
| 547 | if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING |
| 548 | && slow_wheel_index == TW_SLOTS_PER_RING |
| 549 | && glacier_wheel_index == TW_SLOTS_PER_RING)) |
| 550 | { |
| 551 | u64 interval; |
| 552 | u32 new_glacier_ring_offset, new_slow_ring_offset; |
| 553 | u32 new_fast_ring_offset; |
| 554 | |
| 555 | ts = &tw->overflow; |
| 556 | head = pool_elt_at_index (tw->timers, ts->head_index); |
| 557 | next_index = head->next; |
| 558 | |
| 559 | /* Make slot empty */ |
| 560 | head->next = head->prev = ts->head_index; |
| 561 | |
| 562 | /* traverse slot, place timers wherever they go */ |
| 563 | while (next_index != head - tw->timers) |
| 564 | { |
| 565 | t = pool_elt_at_index (tw->timers, next_index); |
| 566 | next_index = t->next; |
| 567 | |
| 568 | /* Remove from the overflow vector (hammer) */ |
| 569 | t->next = t->prev = ~0; |
| 570 | |
| 571 | ASSERT (t->expiration_time >= tw->current_tick); |
| 572 | |
| 573 | interval = t->expiration_time - tw->current_tick; |
| 574 | |
| 575 | /* Right back onto the overflow vector? */ |
| 576 | if (interval >= (1 << (3 * TW_RING_SHIFT))) |
| 577 | { |
| 578 | ts = &tw->overflow; |
| 579 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
| 580 | continue; |
| 581 | } |
| 582 | /* Compute ring offsets */ |
| 583 | new_glacier_ring_offset = interval >> (2 * TW_RING_SHIFT); |
| 584 | |
| 585 | interval -= (new_glacier_ring_offset << (2 * TW_RING_SHIFT)); |
| 586 | |
| 587 | /* Note: the wheels are at (0,0,0), no add-with-carry needed */ |
| 588 | new_slow_ring_offset = interval >> TW_RING_SHIFT; |
| 589 | interval -= (new_slow_ring_offset << TW_RING_SHIFT); |
| 590 | new_fast_ring_offset = interval & TW_RING_MASK; |
| 591 | t->slow_ring_offset = new_slow_ring_offset; |
| 592 | t->fast_ring_offset = new_fast_ring_offset; |
| 593 | |
| 594 | /* Timer expires Right Now */ |
| 595 | if (PREDICT_FALSE (t->slow_ring_offset == 0 && |
| 596 | t->fast_ring_offset == 0 && |
| 597 | new_glacier_ring_offset == 0)) |
| 598 | { |
| 599 | vec_add1 (callback_vector, t->user_handle); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 600 | #if TW_START_STOP_TRACE_SIZE > 0 |
Florin Coras | 4eeeaaf | 2017-09-05 14:03:37 -0400 | [diff] [blame] | 601 | TW (tw_timer_trace) (tw, 0xfe, t->user_handle, |
| 602 | t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 603 | #endif |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 604 | pool_put (tw->timers, t); |
| 605 | } |
| 606 | /* Timer moves to the glacier ring */ |
| 607 | else if (new_glacier_ring_offset) |
| 608 | { |
| 609 | ts = &tw->w[TW_TIMER_RING_GLACIER][new_glacier_ring_offset]; |
| 610 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
| 611 | } |
| 612 | /* Timer moves to the slow ring */ |
| 613 | else if (t->slow_ring_offset) |
| 614 | { |
| 615 | /* Add to slow ring */ |
| 616 | ts = &tw->w[TW_TIMER_RING_SLOW][t->slow_ring_offset]; |
| 617 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
| 618 | } |
| 619 | /* Timer timer moves to the fast ring */ |
| 620 | else |
| 621 | { |
| 622 | ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset]; |
| 623 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 624 | #if TW_FAST_WHEEL_BITMAP |
| 625 | tw->fast_slot_bitmap = |
| 626 | clib_bitmap_set (tw->fast_slot_bitmap, |
| 627 | t->fast_ring_offset, 1); |
| 628 | #endif |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 629 | } |
| 630 | } |
| 631 | } |
| 632 | #endif |
| 633 | |
| 634 | #if TW_TIMER_WHEELS > 2 |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 635 | /* |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 636 | * Double odometer-click? Process one slot in the glacier ring... |
| 637 | */ |
| 638 | if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING |
| 639 | && slow_wheel_index == TW_SLOTS_PER_RING)) |
| 640 | { |
| 641 | glacier_wheel_index %= TW_SLOTS_PER_RING; |
| 642 | ts = &tw->w[TW_TIMER_RING_GLACIER][glacier_wheel_index]; |
| 643 | |
| 644 | head = pool_elt_at_index (tw->timers, ts->head_index); |
| 645 | next_index = head->next; |
| 646 | |
| 647 | /* Make slot empty */ |
| 648 | head->next = head->prev = ts->head_index; |
| 649 | |
| 650 | /* traverse slot, deal timers into slow ring */ |
| 651 | while (next_index != head - tw->timers) |
| 652 | { |
| 653 | t = pool_elt_at_index (tw->timers, next_index); |
| 654 | next_index = t->next; |
| 655 | |
| 656 | /* Remove from glacier ring slot (hammer) */ |
| 657 | t->next = t->prev = ~0; |
| 658 | |
| 659 | /* Timer expires Right Now */ |
| 660 | if (PREDICT_FALSE (t->slow_ring_offset == 0 && |
| 661 | t->fast_ring_offset == 0)) |
| 662 | { |
| 663 | vec_add1 (callback_vector, t->user_handle); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 664 | #if TW_START_STOP_TRACE_SIZE > 0 |
Florin Coras | 4eeeaaf | 2017-09-05 14:03:37 -0400 | [diff] [blame] | 665 | TW (tw_timer_trace) (tw, 0xfe, t->user_handle, |
| 666 | t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 667 | #endif |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 668 | pool_put (tw->timers, t); |
| 669 | } |
| 670 | /* Timer expires during slow-wheel tick 0 */ |
| 671 | else if (PREDICT_FALSE (t->slow_ring_offset == 0)) |
| 672 | { |
| 673 | ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset]; |
| 674 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 675 | #if TW_FAST_WHEEL_BITMAP |
| 676 | tw->fast_slot_bitmap = |
| 677 | clib_bitmap_set (tw->fast_slot_bitmap, |
| 678 | t->fast_ring_offset, 1); |
| 679 | #endif |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 680 | } |
| 681 | else /* typical case */ |
| 682 | { |
| 683 | /* Add to slow ring */ |
| 684 | ts = &tw->w[TW_TIMER_RING_SLOW][t->slow_ring_offset]; |
| 685 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
| 686 | } |
| 687 | } |
| 688 | } |
| 689 | #endif |
| 690 | |
| 691 | #if TW_TIMER_WHEELS > 1 |
| 692 | /* |
| 693 | * Single odometer-click? Process a slot in the slow ring, |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 694 | */ |
| 695 | if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING)) |
| 696 | { |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 697 | slow_wheel_index %= TW_SLOTS_PER_RING; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 698 | ts = &tw->w[TW_TIMER_RING_SLOW][slow_wheel_index]; |
| 699 | |
| 700 | head = pool_elt_at_index (tw->timers, ts->head_index); |
| 701 | next_index = head->next; |
| 702 | |
| 703 | /* Make slot empty */ |
| 704 | head->next = head->prev = ts->head_index; |
| 705 | |
| 706 | /* traverse slot, deal timers into fast ring */ |
| 707 | while (next_index != head - tw->timers) |
| 708 | { |
| 709 | t = pool_elt_at_index (tw->timers, next_index); |
| 710 | next_index = t->next; |
| 711 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 712 | /* Remove from sloe ring slot (hammer) */ |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 713 | t->next = t->prev = ~0; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 714 | |
| 715 | /* Timer expires Right Now */ |
| 716 | if (PREDICT_FALSE (t->fast_ring_offset == 0)) |
| 717 | { |
| 718 | vec_add1 (callback_vector, t->user_handle); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 719 | #if TW_START_STOP_TRACE_SIZE > 0 |
Florin Coras | 4eeeaaf | 2017-09-05 14:03:37 -0400 | [diff] [blame] | 720 | TW (tw_timer_trace) (tw, 0xfe, t->user_handle, |
| 721 | t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 722 | #endif |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 723 | pool_put (tw->timers, t); |
| 724 | } |
| 725 | else /* typical case */ |
| 726 | { |
| 727 | /* Add to fast ring */ |
| 728 | ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset]; |
| 729 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 730 | #if TW_FAST_WHEEL_BITMAP |
| 731 | tw->fast_slot_bitmap = |
| 732 | clib_bitmap_set (tw->fast_slot_bitmap, |
| 733 | t->fast_ring_offset, 1); |
| 734 | #endif |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 735 | } |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 736 | } |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 737 | } |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 738 | #endif |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 739 | |
| 740 | /* Handle the fast ring */ |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 741 | fast_wheel_index %= TW_SLOTS_PER_RING; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 742 | ts = &tw->w[TW_TIMER_RING_FAST][fast_wheel_index]; |
| 743 | |
| 744 | head = pool_elt_at_index (tw->timers, ts->head_index); |
| 745 | next_index = head->next; |
| 746 | |
| 747 | /* Make slot empty */ |
| 748 | head->next = head->prev = ts->head_index; |
| 749 | |
| 750 | /* Construct vector of expired timer handles to give the user */ |
| 751 | while (next_index != ts->head_index) |
| 752 | { |
| 753 | t = pool_elt_at_index (tw->timers, next_index); |
| 754 | next_index = t->next; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 755 | vec_add1 (callback_vector, t->user_handle); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 756 | #if TW_START_STOP_TRACE_SIZE > 0 |
Florin Coras | 4eeeaaf | 2017-09-05 14:03:37 -0400 | [diff] [blame] | 757 | TW (tw_timer_trace) (tw, 0xfe, t->user_handle, t - tw->timers); |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 758 | #endif |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 759 | pool_put (tw->timers, t); |
| 760 | } |
| 761 | |
| 762 | /* If any timers expired, tell the user */ |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 763 | if (callback_vector_arg == 0 && vec_len (callback_vector)) |
Gabriel Ganne | 581b072 | 2017-02-13 10:27:15 +0100 | [diff] [blame] | 764 | { |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 765 | /* The callback is optional. We return the u32 * handle vector */ |
| 766 | if (tw->expired_timer_callback) |
Dave Barach | ad09933 | 2018-02-20 08:34:48 -0500 | [diff] [blame] | 767 | { |
| 768 | tw->expired_timer_callback (callback_vector); |
| 769 | vec_reset_length (callback_vector); |
| 770 | } |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 771 | tw->expired_timer_handles = callback_vector; |
Gabriel Ganne | 581b072 | 2017-02-13 10:27:15 +0100 | [diff] [blame] | 772 | } |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 773 | |
| 774 | #if TW_FAST_WHEEL_BITMAP |
| 775 | tw->fast_slot_bitmap = clib_bitmap_set (tw->fast_slot_bitmap, |
| 776 | fast_wheel_index, 0); |
| 777 | #endif |
| 778 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 779 | tw->current_tick++; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 780 | fast_wheel_index++; |
| 781 | tw->current_index[TW_TIMER_RING_FAST] = fast_wheel_index; |
Gabriel Ganne | 83ed1f4 | 2017-02-15 16:55:30 +0100 | [diff] [blame] | 782 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 783 | #if TW_TIMER_WHEELS > 1 |
| 784 | if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING)) |
| 785 | slow_wheel_index++; |
| 786 | tw->current_index[TW_TIMER_RING_SLOW] = slow_wheel_index; |
| 787 | #endif |
| 788 | |
| 789 | #if TW_TIMER_WHEELS > 2 |
| 790 | if (PREDICT_FALSE (slow_wheel_index == TW_SLOTS_PER_RING)) |
| 791 | glacier_wheel_index++; |
| 792 | tw->current_index[TW_TIMER_RING_GLACIER] = glacier_wheel_index; |
| 793 | #endif |
| 794 | |
| 795 | if (vec_len (callback_vector) >= tw->max_expirations) |
Gabriel Ganne | 83ed1f4 | 2017-02-15 16:55:30 +0100 | [diff] [blame] | 796 | break; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 797 | } |
Gabriel Ganne | 581b072 | 2017-02-13 10:27:15 +0100 | [diff] [blame] | 798 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 799 | if (callback_vector_arg == 0) |
| 800 | tw->expired_timer_handles = callback_vector; |
| 801 | |
Florin Coras | 954898f | 2017-02-21 19:26:51 -0800 | [diff] [blame] | 802 | tw->last_run_time += i * tw->timer_interval; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 803 | return callback_vector; |
| 804 | } |
| 805 | |
| 806 | u32 *TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now) |
| 807 | { |
| 808 | return TW (tw_timer_expire_timers_internal) (tw, now, 0 /* no vector */ ); |
| 809 | } |
| 810 | |
| 811 | u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now, |
| 812 | u32 * vec) |
| 813 | { |
| 814 | return TW (tw_timer_expire_timers_internal) (tw, now, vec); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 815 | } |
| 816 | |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 817 | #if TW_FAST_WHEEL_BITMAP |
| 818 | /** Returns an approximation to the first timer expiration in |
| 819 | * timer-ticks from "now". To avoid wasting an unjustifiable |
| 820 | * amount of time on the problem, we maintain an approximate fast-wheel slot |
| 821 | * occupancy bitmap. We don't worry about clearing fast wheel bits |
| 822 | * when timers are removed from fast wheel slots. |
| 823 | */ |
| 824 | |
| 825 | u32 TW (tw_timer_first_expires_in_ticks) (TWT (tw_timer_wheel) * tw) |
| 826 | { |
| 827 | u32 first_expiring_index, fast_ring_index; |
| 828 | i32 delta; |
| 829 | |
Andreas Schultz | 217c62a | 2019-06-25 15:29:06 +0200 | [diff] [blame] | 830 | #if TW_TIMER_WHEELS > 1 |
| 831 | fast_ring_index = tw->current_index[TW_TIMER_RING_FAST]; |
| 832 | if (fast_ring_index == TW_SLOTS_PER_RING) |
| 833 | return 1; |
| 834 | |
| 835 | first_expiring_index = clib_bitmap_next_set (tw->fast_slot_bitmap, |
| 836 | fast_ring_index); |
| 837 | if (first_expiring_index == ~0) |
| 838 | first_expiring_index = TW_SLOTS_PER_RING; |
| 839 | |
| 840 | #else |
| 841 | |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 842 | if (clib_bitmap_is_zero (tw->fast_slot_bitmap)) |
| 843 | return TW_SLOTS_PER_RING; |
| 844 | |
| 845 | fast_ring_index = tw->current_index[TW_TIMER_RING_FAST]; |
| 846 | if (fast_ring_index == TW_SLOTS_PER_RING) |
| 847 | fast_ring_index = 0; |
| 848 | |
| 849 | first_expiring_index = clib_bitmap_next_set (tw->fast_slot_bitmap, |
| 850 | fast_ring_index); |
| 851 | if (first_expiring_index == ~0 && fast_ring_index != 0) |
| 852 | first_expiring_index = clib_bitmap_first_set (tw->fast_slot_bitmap); |
Andreas Schultz | 217c62a | 2019-06-25 15:29:06 +0200 | [diff] [blame] | 853 | #endif |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 854 | |
| 855 | ASSERT (first_expiring_index != ~0); |
| 856 | |
| 857 | delta = (i32) first_expiring_index - (i32) fast_ring_index; |
| 858 | if (delta < 0) |
| 859 | delta += TW_SLOTS_PER_RING; |
| 860 | |
| 861 | ASSERT (delta >= 0); |
| 862 | |
| 863 | return (u32) delta; |
| 864 | } |
| 865 | |
| 866 | #endif |
| 867 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 868 | /* |
| 869 | * fd.io coding-style-patch-verification: ON |
| 870 | * |
| 871 | * Local Variables: |
| 872 | * eval: (c-set-style "gnu") |
| 873 | * End: |
| 874 | */ |