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 | #ifndef TW_SUFFIX |
| 17 | #error do not include tw_timer_template.h directly |
| 18 | #endif |
| 19 | |
| 20 | #include <vppinfra/clib.h> |
| 21 | #include <vppinfra/pool.h> |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 22 | #include <vppinfra/bitmap.h> |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 23 | |
| 24 | #ifndef _twt |
| 25 | #define _twt(a,b) a##b##_t |
| 26 | #define __twt(a,b) _twt(a,b) |
| 27 | #define TWT(a) __twt(a,TW_SUFFIX) |
| 28 | |
| 29 | #define _tw(a,b) a##b |
| 30 | #define __tw(a,b) _tw(a,b) |
| 31 | #define TW(a) __tw(a,TW_SUFFIX) |
| 32 | #endif |
| 33 | |
| 34 | /** @file |
| 35 | @brief TW timer template header file, do not compile directly |
| 36 | |
| 37 | Instantiation of tw_timer_template.h generates named structures to |
| 38 | implement specific timer wheel geometries. Choices include: number of |
| 39 | timer wheels (currently, 1 or 2), number of slots per ring (a power of |
| 40 | two), and the number of timers per "object handle". |
| 41 | |
| 42 | Internally, user object/timer handles are 32-bit integers, so if one |
| 43 | selects 16 timers/object (4 bits), the resulting timer wheel handle is |
| 44 | limited to 2**28 objects. |
| 45 | |
| 46 | Here are the specific settings required to generate a single 2048 slot |
| 47 | wheel which supports 2 timers per object: |
| 48 | |
| 49 | #define TW_TIMER_WHEELS 1 |
| 50 | #define TW_SLOTS_PER_RING 2048 |
| 51 | #define TW_RING_SHIFT 11 |
| 52 | #define TW_RING_MASK (TW_SLOTS_PER_RING -1) |
| 53 | #define TW_TIMERS_PER_OBJECT 2 |
| 54 | #define LOG2_TW_TIMERS_PER_OBJECT 1 |
| 55 | #define TW_SUFFIX _2t_1w_2048sl |
| 56 | |
| 57 | See tw_timer_2t_1w_2048sl.h for a complete |
| 58 | example. |
| 59 | |
| 60 | tw_timer_template.h is not intended to be #included directly. Client |
| 61 | codes can include multiple timer geometry header files, although |
| 62 | extreme caution would required to use the TW and TWT macros in such a |
| 63 | case. |
| 64 | |
| 65 | API usage example: |
| 66 | |
| 67 | Initialize a two-timer, single 2048-slot wheel w/ a 1-second |
| 68 | timer granularity: |
| 69 | |
| 70 | tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel, |
| 71 | expired_timer_single_callback, |
| 72 | 1.0 / * timer interval * / ); |
| 73 | |
| 74 | Start a timer: |
| 75 | |
| 76 | handle = tw_timer_start_2t_1w_2048sl (&tm->single_wheel, elt_index, |
| 77 | [0 | 1] / * timer id * / , |
| 78 | expiration_time_in_u32_ticks); |
| 79 | |
| 80 | Stop a timer: |
| 81 | |
| 82 | tw_timer_stop_2t_1w_2048sl (&tm->single_wheel, handle); |
| 83 | |
| 84 | Expired timer callback: |
| 85 | |
| 86 | static void |
| 87 | expired_timer_single_callback (u32 * expired_timers) |
| 88 | { |
| 89 | int i; |
| 90 | u32 pool_index, timer_id; |
| 91 | tw_timer_test_elt_t *e; |
| 92 | tw_timer_test_main_t *tm = &tw_timer_test_main; |
| 93 | |
| 94 | for (i = 0; i < vec_len (expired_timers); |
| 95 | { |
| 96 | pool_index = expired_timers[i] & 0x7FFFFFFF; |
| 97 | timer_id = expired_timers[i] >> 31; |
| 98 | |
| 99 | ASSERT (timer_id == 1); |
| 100 | |
| 101 | e = pool_elt_at_index (tm->test_elts, pool_index); |
| 102 | |
| 103 | if (e->expected_to_expire != tm->single_wheel.current_tick) |
| 104 | { |
| 105 | fformat (stdout, "[%d] expired at %d not %d\n", |
| 106 | e - tm->test_elts, tm->single_wheel.current_tick, |
| 107 | e->expected_to_expire); |
| 108 | } |
| 109 | pool_put (tm->test_elts, e); |
| 110 | } |
| 111 | } |
| 112 | */ |
| 113 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 114 | #if (TW_TIMER_WHEELS != 1 && TW_TIMER_WHEELS != 2 && TW_TIMER_WHEELS != 3) |
| 115 | #error TW_TIMER_WHEELS must be 1, 2 or 3 |
| 116 | #endif |
| 117 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 118 | typedef struct |
| 119 | { |
| 120 | /** next, previous pool indices */ |
| 121 | u32 next; |
| 122 | u32 prev; |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 123 | |
| 124 | union |
| 125 | { |
| 126 | struct |
| 127 | { |
| 128 | #if (TW_TIMER_WHEELS == 3) |
| 129 | /** fast ring offset, only valid in the slow ring */ |
| 130 | u16 fast_ring_offset; |
| 131 | /** slow ring offset, only valid in the glacier ring */ |
| 132 | u16 slow_ring_offset; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 133 | #endif |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 134 | #if (TW_TIMER_WHEELS == 2) |
| 135 | /** fast ring offset, only valid in the slow ring */ |
| 136 | u16 fast_ring_offset; |
| 137 | /** slow ring offset, only valid in the glacier ring */ |
| 138 | u16 pad; |
| 139 | #endif |
| 140 | }; |
| 141 | |
| 142 | #if (TW_OVERFLOW_VECTOR > 0) |
| 143 | u64 expiration_time; |
| 144 | #endif |
| 145 | }; |
| 146 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 147 | /** user timer handle */ |
| 148 | u32 user_handle; |
| 149 | } TWT (tw_timer); |
| 150 | |
| 151 | /* |
| 152 | * These structures ar used by all geometries, |
| 153 | * so they need a private #include block... |
| 154 | */ |
| 155 | #ifndef __defined_tw_timer_wheel_slot__ |
| 156 | #define __defined_tw_timer_wheel_slot__ |
| 157 | typedef struct |
| 158 | { |
| 159 | /** Listhead of timers which expire in this interval */ |
| 160 | u32 head_index; |
| 161 | } tw_timer_wheel_slot_t; |
| 162 | typedef enum |
| 163 | { |
| 164 | /** Fast timer ring ID */ |
| 165 | TW_TIMER_RING_FAST, |
| 166 | /** Slow timer ring ID */ |
| 167 | TW_TIMER_RING_SLOW, |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 168 | /** Glacier ring ID */ |
| 169 | TW_TIMER_RING_GLACIER, |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 170 | } tw_ring_index_t; |
| 171 | #endif /* __defined_tw_timer_wheel_slot__ */ |
| 172 | |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 173 | typedef CLIB_PACKED (struct |
| 174 | { |
| 175 | u8 timer_id; |
| 176 | u32 pool_index; |
| 177 | u32 handle; |
| 178 | }) TWT (trace); |
| 179 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 180 | typedef struct |
| 181 | { |
| 182 | /** Timer pool */ |
| 183 | TWT (tw_timer) * timers; |
| 184 | |
| 185 | /** Next time the wheel should run */ |
| 186 | f64 next_run_time; |
| 187 | |
| 188 | /** Last time the wheel ran */ |
| 189 | f64 last_run_time; |
| 190 | |
| 191 | /** Timer ticks per second */ |
| 192 | f64 ticks_per_second; |
| 193 | |
| 194 | /** Timer interval, also needed to avoid fp divide in speed path */ |
| 195 | f64 timer_interval; |
| 196 | |
| 197 | /** current tick */ |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 198 | u64 current_tick; |
| 199 | |
| 200 | /** first expiration time */ |
| 201 | u64 first_expires_tick; |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 202 | |
| 203 | /** current wheel indices */ |
| 204 | u32 current_index[TW_TIMER_WHEELS]; |
| 205 | |
| 206 | /** wheel arrays */ |
| 207 | tw_timer_wheel_slot_t w[TW_TIMER_WHEELS][TW_SLOTS_PER_RING]; |
| 208 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 209 | #if TW_OVERFLOW_VECTOR > 0 |
| 210 | tw_timer_wheel_slot_t overflow; |
| 211 | #endif |
| 212 | |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 213 | #if TW_FAST_WHEEL_BITMAP > 0 |
| 214 | /** Fast wheel slot occupancy bitmap */ |
| 215 | uword *fast_slot_bitmap; |
| 216 | #endif |
| 217 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 218 | /** expired timer callback, receives a vector of handles */ |
| 219 | void (*expired_timer_callback) (u32 * expired_timer_handles); |
| 220 | |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 221 | /** vectors of expired timers */ |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 222 | u32 *expired_timer_handles; |
Gabriel Ganne | 83ed1f4 | 2017-02-15 16:55:30 +0100 | [diff] [blame] | 223 | |
| 224 | /** maximum expirations */ |
| 225 | u32 max_expirations; |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 226 | |
| 227 | /** current trace index */ |
| 228 | #if TW_START_STOP_TRACE_SIZE > 0 |
| 229 | /* Start/stop/expire tracing */ |
| 230 | u32 trace_index; |
| 231 | u32 trace_wrapped; |
| 232 | TWT (trace) traces[TW_START_STOP_TRACE_SIZE]; |
| 233 | #endif |
| 234 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 235 | } TWT (tw_timer_wheel); |
| 236 | |
| 237 | u32 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 238 | u32 pool_index, u32 timer_id, u64 interval); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 239 | |
| 240 | void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle); |
Florin Coras | 40f9246 | 2018-08-01 16:25:45 -0700 | [diff] [blame^] | 241 | int TW (tw_timer_handle_is_free) (TWT (tw_timer_wheel) * tw, u32 handle); |
Florin Coras | adb5bd5 | 2018-06-22 15:29:38 -0700 | [diff] [blame] | 242 | void TW (tw_timer_update) (TWT (tw_timer_wheel) * tw, u32 handle, |
| 243 | u64 interval); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 244 | |
| 245 | void TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw, |
| 246 | void *expired_timer_callback, |
Gabriel Ganne | 83ed1f4 | 2017-02-15 16:55:30 +0100 | [diff] [blame] | 247 | f64 timer_interval, u32 max_expirations); |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 248 | |
| 249 | void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw); |
| 250 | |
Dave Barach | 4af9ba1 | 2017-06-07 15:18:23 -0400 | [diff] [blame] | 251 | u32 *TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now); |
| 252 | u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now, |
| 253 | u32 * vec); |
Dave Barach | 5c20a01 | 2017-06-13 08:48:31 -0400 | [diff] [blame] | 254 | #if TW_FAST_WHEEL_BITMAP |
| 255 | u32 TW (tw_timer_first_expires_in_ticks) (TWT (tw_timer_wheel) * tw); |
| 256 | #endif |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 257 | |
Dave Barach | b7f1faa | 2017-08-29 11:43:37 -0400 | [diff] [blame] | 258 | #if TW_START_STOP_TRACE_SIZE > 0 |
| 259 | void TW (tw_search_trace) (TWT (tw_timer_wheel) * tw, u32 handle); |
| 260 | void TW (tw_timer_trace) (TWT (tw_timer_wheel) * tw, u32 timer_id, |
| 261 | u32 pool_index, u32 handle); |
| 262 | #endif |
| 263 | |
Dave Barach | 8e8f98c | 2017-02-03 11:58:53 -0500 | [diff] [blame] | 264 | /* |
| 265 | * fd.io coding-style-patch-verification: ON |
| 266 | * |
| 267 | * Local Variables: |
| 268 | * eval: (c-set-style "gnu") |
| 269 | * End: |
| 270 | */ |