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 | */ |
| 21 | |
| 22 | static inline u32 |
| 23 | TW (make_internal_timer_handle) (u32 pool_index, u32 timer_id) |
| 24 | { |
| 25 | u32 handle; |
| 26 | |
| 27 | ASSERT (timer_id < TW_TIMERS_PER_OBJECT); |
| 28 | ASSERT (pool_index < (1 << (32 - LOG2_TW_TIMERS_PER_OBJECT))); |
| 29 | |
| 30 | handle = (timer_id << (32 - LOG2_TW_TIMERS_PER_OBJECT)) | (pool_index); |
| 31 | return handle; |
| 32 | } |
| 33 | |
| 34 | static inline void |
| 35 | timer_addhead (TWT (tw_timer) * pool, u32 head_index, u32 new_index) |
| 36 | { |
| 37 | TWT (tw_timer) * head = pool_elt_at_index (pool, head_index); |
| 38 | TWT (tw_timer) * old_first; |
| 39 | u32 old_first_index; |
| 40 | TWT (tw_timer) * new; |
| 41 | |
| 42 | new = pool_elt_at_index (pool, new_index); |
| 43 | |
| 44 | if (PREDICT_FALSE (head->next == head_index)) |
| 45 | { |
| 46 | head->next = head->prev = new_index; |
| 47 | new->next = new->prev = head_index; |
| 48 | return; |
| 49 | } |
| 50 | |
| 51 | old_first_index = head->next; |
| 52 | old_first = pool_elt_at_index (pool, old_first_index); |
| 53 | |
| 54 | new->next = old_first_index; |
| 55 | new->prev = old_first->prev; |
| 56 | old_first->prev = new_index; |
| 57 | head->next = new_index; |
| 58 | } |
| 59 | |
| 60 | static inline void |
| 61 | timer_remove (TWT (tw_timer) * pool, u32 index) |
| 62 | { |
| 63 | TWT (tw_timer) * elt = pool_elt_at_index (pool, index); |
| 64 | TWT (tw_timer) * next_elt, *prev_elt; |
| 65 | |
| 66 | ASSERT (elt->user_handle != ~0); |
| 67 | |
| 68 | next_elt = pool_elt_at_index (pool, elt->next); |
| 69 | prev_elt = pool_elt_at_index (pool, elt->prev); |
| 70 | |
| 71 | next_elt->prev = elt->prev; |
| 72 | prev_elt->next = elt->next; |
| 73 | |
| 74 | elt->prev = elt->next = ~0; |
| 75 | } |
| 76 | |
| 77 | /** |
| 78 | * @brief Start a Tw Timer |
| 79 | * @param tw_timer_wheel_t * tw timer wheel object pointer |
| 80 | * @param u32 pool_index user pool index, presumably for a tw session |
| 81 | * @param u32 timer_id app-specific timer ID. 4 bits. |
| 82 | * @param u32 interval timer interval in ticks |
| 83 | * @returns handle needed to cancel the timer |
| 84 | */ |
| 85 | u32 |
| 86 | TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id, |
| 87 | u32 interval) |
| 88 | { |
| 89 | #if TW_TIMER_WHEELS > 1 |
| 90 | u16 slow_ring_offset; |
| 91 | u32 carry; |
| 92 | #endif |
| 93 | u16 fast_ring_offset; |
| 94 | tw_timer_wheel_slot_t *ts; |
| 95 | TWT (tw_timer) * t; |
| 96 | |
| 97 | ASSERT (interval); |
| 98 | |
| 99 | pool_get (tw->timers, t); |
| 100 | t->next = t->prev = ~0; |
| 101 | #if TW_TIMER_WHEELS > 1 |
| 102 | t->fast_ring_offset = ~0; |
| 103 | #endif |
| 104 | t->user_handle = TW (make_internal_timer_handle) (pool_index, timer_id); |
| 105 | |
| 106 | fast_ring_offset = interval & TW_RING_MASK; |
| 107 | fast_ring_offset += tw->current_index[TW_TIMER_RING_FAST]; |
| 108 | #if TW_TIMER_WHEELS > 1 |
| 109 | carry = fast_ring_offset >= TW_SLOTS_PER_RING ? 1 : 0; |
| 110 | fast_ring_offset %= TW_SLOTS_PER_RING; |
| 111 | slow_ring_offset = (interval >> TW_RING_SHIFT) + carry; |
| 112 | |
| 113 | /* Timer duration exceeds ~7 hrs? Oops */ |
| 114 | ASSERT (slow_ring_offset < TW_SLOTS_PER_RING); |
| 115 | |
| 116 | /* Timer expires more than 51.2 seconds from now? */ |
| 117 | if (slow_ring_offset) |
| 118 | { |
| 119 | slow_ring_offset += tw->current_index[TW_TIMER_RING_SLOW]; |
| 120 | slow_ring_offset %= TW_SLOTS_PER_RING; |
| 121 | |
| 122 | /* We'll want the fast ring offset later... */ |
| 123 | t->fast_ring_offset = fast_ring_offset; |
| 124 | ASSERT (t->fast_ring_offset < TW_SLOTS_PER_RING); |
| 125 | |
| 126 | ts = &tw->w[TW_TIMER_RING_SLOW][slow_ring_offset]; |
| 127 | |
| 128 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
| 129 | |
| 130 | return t - tw->timers; |
| 131 | } |
| 132 | #else |
| 133 | fast_ring_offset %= TW_SLOTS_PER_RING; |
| 134 | ASSERT (interval < TW_SLOTS_PER_RING); |
| 135 | #endif |
| 136 | |
| 137 | /* Timer expires less than one fast-ring revolution from now */ |
| 138 | ts = &tw->w[TW_TIMER_RING_FAST][fast_ring_offset]; |
| 139 | |
| 140 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
| 141 | return t - tw->timers; |
| 142 | } |
| 143 | |
| 144 | /** |
| 145 | * @brief Stop a tw timer |
| 146 | * @param tw_timer_wheel_t * tw timer wheel object pointer |
| 147 | * @param u32 pool_index user pool index, passed for consistency checking only |
| 148 | * @param u32 timer_id 4 bit timer ID, passed for consistency checking only |
| 149 | * @param u32 handle timer cancellation returned by tw_timer_start |
| 150 | */ |
| 151 | |
| 152 | void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle) |
| 153 | { |
| 154 | TWT (tw_timer) * t; |
| 155 | |
| 156 | t = pool_elt_at_index (tw->timers, handle); |
| 157 | |
| 158 | /* in case of idiotic handle (e.g. passing a listhead index) */ |
| 159 | ASSERT (t->user_handle != ~0); |
| 160 | |
| 161 | timer_remove (tw->timers, handle); |
| 162 | |
| 163 | pool_put_index (tw->timers, handle); |
| 164 | } |
| 165 | |
| 166 | /** |
| 167 | * @brief Initialize a tw timer wheel template instance |
| 168 | * @param tw_timer_wheel_t * tw timer wheel object pointer |
| 169 | * @param void * expired_timer_callback. Passed a u32 * vector of |
| 170 | * expired timer handles. |
| 171 | * @param f64 timer_interval_in_seconds |
| 172 | */ |
| 173 | void |
| 174 | TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw, |
| 175 | void *expired_timer_callback, |
| 176 | f64 timer_interval_in_seconds) |
| 177 | { |
| 178 | int ring, slot; |
| 179 | tw_timer_wheel_slot_t *ts; |
| 180 | TWT (tw_timer) * t; |
| 181 | memset (tw, 0, sizeof (*tw)); |
| 182 | tw->expired_timer_callback = expired_timer_callback; |
| 183 | if (timer_interval_in_seconds == 0.0) |
| 184 | { |
| 185 | clib_warning ("timer interval is zero"); |
| 186 | abort (); |
| 187 | } |
| 188 | tw->timer_interval = timer_interval_in_seconds; |
| 189 | tw->ticks_per_second = 1.0 / timer_interval_in_seconds; |
| 190 | |
| 191 | for (ring = 0; ring < TW_TIMER_WHEELS; ring++) |
| 192 | { |
| 193 | for (slot = 0; slot < TW_SLOTS_PER_RING; slot++) |
| 194 | { |
| 195 | ts = &tw->w[ring][slot]; |
| 196 | pool_get (tw->timers, t); |
| 197 | memset (t, 0xff, sizeof (*t)); |
| 198 | t->next = t->prev = t - tw->timers; |
| 199 | ts->head_index = t - tw->timers; |
| 200 | } |
| 201 | } |
| 202 | } |
| 203 | |
| 204 | /** |
| 205 | * @brief Free a tw timer wheel template instance |
| 206 | * @param tw_timer_wheel_t * tw timer wheel object pointer |
| 207 | */ |
| 208 | void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw) |
| 209 | { |
| 210 | int i, j; |
| 211 | tw_timer_wheel_slot_t *ts; |
| 212 | TWT (tw_timer) * head, *t; |
| 213 | u32 next_index; |
| 214 | |
| 215 | for (i = 0; i < TW_TIMER_WHEELS; i++) |
| 216 | { |
| 217 | for (j = 0; j < TW_SLOTS_PER_RING; j++) |
| 218 | { |
| 219 | ts = &tw->w[i][j]; |
| 220 | head = pool_elt_at_index (tw->timers, ts->head_index); |
| 221 | next_index = head->next; |
| 222 | |
| 223 | while (next_index != ts->head_index) |
| 224 | { |
| 225 | t = pool_elt_at_index (tw->timers, next_index); |
| 226 | next_index = t->next; |
| 227 | pool_put (tw->timers, t); |
| 228 | } |
| 229 | pool_put (tw->timers, head); |
| 230 | } |
| 231 | } |
| 232 | memset (tw, 0, sizeof (*tw)); |
| 233 | } |
| 234 | |
| 235 | /** |
| 236 | * @brief Advance a tw timer wheel. Calls the expired timer callback |
| 237 | * as needed. This routine should be called once every timer_interval seconds |
| 238 | * @param tw_timer_wheel_t * tw timer wheel template instance pointer |
| 239 | * @param f64 now the current time, e.g. from vlib_time_now(vm) |
| 240 | */ |
| 241 | void TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now) |
| 242 | { |
| 243 | u32 nticks, i; |
| 244 | tw_timer_wheel_slot_t *ts; |
| 245 | TWT (tw_timer) * t, *head; |
| 246 | u32 fast_wheel_index; |
| 247 | u32 next_index; |
| 248 | #if TW_TIMER_WHEELS > 1 |
| 249 | u32 slow_wheel_index; |
| 250 | #endif |
| 251 | |
| 252 | /* Shouldn't happen */ |
| 253 | if (PREDICT_FALSE (now < tw->next_run_time)) |
| 254 | return; |
| 255 | |
| 256 | /* Number of ticks which have occurred */ |
| 257 | nticks = tw->ticks_per_second * (now - tw->last_run_time); |
| 258 | if (nticks == 0) |
| 259 | return; |
| 260 | |
| 261 | /* Remember when we ran, compute next runtime */ |
| 262 | tw->next_run_time = (now + tw->timer_interval); |
| 263 | tw->last_run_time = now; |
| 264 | |
| 265 | for (i = 0; i < nticks; i++) |
| 266 | { |
| 267 | fast_wheel_index = tw->current_index[TW_TIMER_RING_FAST]; |
| 268 | |
| 269 | /* |
| 270 | * If we've been around the fast ring once, |
| 271 | * process one slot in the slow ring before we handle |
| 272 | * the fast ring. |
| 273 | */ |
| 274 | if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING)) |
| 275 | { |
| 276 | fast_wheel_index = tw->current_index[TW_TIMER_RING_FAST] = 0; |
| 277 | |
| 278 | #if TW_TIMER_WHEELS > 1 |
| 279 | tw->current_index[TW_TIMER_RING_SLOW]++; |
| 280 | tw->current_index[TW_TIMER_RING_SLOW] %= TW_SLOTS_PER_RING; |
| 281 | slow_wheel_index = tw->current_index[TW_TIMER_RING_SLOW]; |
| 282 | |
| 283 | ts = &tw->w[TW_TIMER_RING_SLOW][slow_wheel_index]; |
| 284 | |
| 285 | head = pool_elt_at_index (tw->timers, ts->head_index); |
| 286 | next_index = head->next; |
| 287 | |
| 288 | /* Make slot empty */ |
| 289 | head->next = head->prev = ts->head_index; |
| 290 | |
| 291 | /* traverse slot, deal timers into fast ring */ |
| 292 | while (next_index != head - tw->timers) |
| 293 | { |
| 294 | t = pool_elt_at_index (tw->timers, next_index); |
| 295 | next_index = t->next; |
| 296 | |
| 297 | /* Remove from slow ring slot (hammer) */ |
| 298 | t->next = t->prev = ~0; |
| 299 | ASSERT (t->fast_ring_offset < TW_SLOTS_PER_RING); |
| 300 | /* Add to fast ring */ |
| 301 | ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset]; |
| 302 | timer_addhead (tw->timers, ts->head_index, t - tw->timers); |
| 303 | } |
| 304 | #endif |
| 305 | } |
| 306 | |
| 307 | /* Handle the fast ring */ |
| 308 | vec_reset_length (tw->expired_timer_handles); |
| 309 | |
| 310 | ts = &tw->w[TW_TIMER_RING_FAST][fast_wheel_index]; |
| 311 | |
| 312 | head = pool_elt_at_index (tw->timers, ts->head_index); |
| 313 | next_index = head->next; |
| 314 | |
| 315 | /* Make slot empty */ |
| 316 | head->next = head->prev = ts->head_index; |
| 317 | |
| 318 | /* Construct vector of expired timer handles to give the user */ |
| 319 | while (next_index != ts->head_index) |
| 320 | { |
| 321 | t = pool_elt_at_index (tw->timers, next_index); |
| 322 | next_index = t->next; |
| 323 | vec_add1 (tw->expired_timer_handles, t->user_handle); |
| 324 | pool_put (tw->timers, t); |
| 325 | } |
| 326 | |
| 327 | /* If any timers expired, tell the user */ |
| 328 | if (vec_len (tw->expired_timer_handles)) |
| 329 | tw->expired_timer_callback (tw->expired_timer_handles); |
| 330 | tw->current_index[TW_TIMER_RING_FAST]++; |
| 331 | tw->current_tick++; |
| 332 | } |
| 333 | } |
| 334 | |
| 335 | /* |
| 336 | * fd.io coding-style-patch-verification: ON |
| 337 | * |
| 338 | * Local Variables: |
| 339 | * eval: (c-set-style "gnu") |
| 340 | * End: |
| 341 | */ |