FD.io VPP  v21.10.1-2-g0a485f517
Vector Packet Processing
tw_timer_template.h
Go to the documentation of this file.
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>
22 #include <vppinfra/bitmap.h>
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 
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 
118 typedef struct
119 {
120  /** next, previous pool indices */
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;
133 #endif
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 
147  /** user timer 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 */
162 typedef enum
163 {
164  /** Fast timer ring ID */
166  /** Slow timer ring ID */
168  /** Glacier ring ID */
171 #endif /* __defined_tw_timer_wheel_slot__ */
172 
173 typedef CLIB_PACKED (struct
174  {
175  u8 timer_id;
176  u32 pool_index;
177  u32 handle;
178  }) TWT (trace);
179 
180 typedef struct
181 {
182  /** Timer pool */
183  TWT (tw_timer) * timers;
184 
185  /** Next time the wheel should run */
187 
188  /** Last time the wheel ran */
190 
191  /** Timer ticks per second */
193 
194  /** Timer interval, also needed to avoid fp divide in speed path */
196 
197  /** current tick */
199 
200  /** current wheel indices */
201  u32 current_index[TW_TIMER_WHEELS];
202 
203  /** wheel arrays */
205 
206 #if TW_OVERFLOW_VECTOR > 0
207  tw_timer_wheel_slot_t overflow;
208 #endif
209 
210 #if TW_FAST_WHEEL_BITMAP > 0
211  /** Fast wheel slot occupancy bitmap */
212  uword *fast_slot_bitmap;
213 #endif
214 
215  /** expired timer callback, receives a vector of handles */
216  void (*expired_timer_callback) (u32 * expired_timer_handles);
217 
218  /** vectors of expired timers */
220 
221  /** maximum expirations */
223 
224  /** current trace index */
225 #if TW_START_STOP_TRACE_SIZE > 0
226  /* Start/stop/expire tracing */
227  u32 trace_index;
228  u32 trace_wrapped;
229  TWT (trace) traces[TW_START_STOP_TRACE_SIZE];
230 #endif
231 
232 } TWT (tw_timer_wheel);
233 
234 u32 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw,
235  u32 pool_index, u32 timer_id, u64 interval);
236 
237 void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle);
238 int TW (tw_timer_handle_is_free) (TWT (tw_timer_wheel) * tw, u32 handle);
239 void TW (tw_timer_update) (TWT (tw_timer_wheel) * tw, u32 handle,
240  u64 interval);
241 
242 void TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw,
244  f64 timer_interval, u32 max_expirations);
245 
246 void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw);
247 
248 u32 *TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now);
249 u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now,
250  u32 * vec);
251 #if TW_FAST_WHEEL_BITMAP
252 u32 TW (tw_timer_first_expires_in_ticks) (TWT (tw_timer_wheel) * tw);
253 #endif
254 
255 #if TW_START_STOP_TRACE_SIZE > 0
256 void TW (tw_search_trace) (TWT (tw_timer_wheel) * tw, u32 handle);
257 void TW (tw_timer_trace) (TWT (tw_timer_wheel) * tw, u32 timer_id,
258  u32 pool_index, u32 handle);
259 #endif
260 
261 /*
262  * fd.io coding-style-patch-verification: ON
263  *
264  * Local Variables:
265  * eval: (c-set-style "gnu")
266  * End:
267  */
TWT::next_run_time
f64 next_run_time
Next time the wheel should run.
Definition: tw_timer_template.h:186
CLIB_PACKED
typedef CLIB_PACKED(struct { u8 timer_id;u32 pool_index;u32 handle;}) TWT(trace)
trace
static vlib_cli_command_t trace
(constructor) VLIB_CLI_COMMAND (trace)
Definition: vlib_api_cli.c:870
TWT::prev
u32 prev
Definition: tw_timer_template.h:122
TWT::current_tick
u64 current_tick
current tick
Definition: tw_timer_template.h:198
bitmap.h
clib.h
tw_timer_expire_timers
u32 *TW() tw_timer_expire_timers(TWT(tw_timer_wheel) *tw, f64 now)
Definition: tw_timer_template.c:814
tw_timer_stop
void TW() tw_timer_stop(TWT(tw_timer_wheel) *tw, u32 handle)
Stop a tw timer.
Definition: tw_timer_template.c:352
tw_timer_start
u32 TW() tw_timer_start(TWT(tw_timer_wheel) *tw, u32 pool_index, u32 timer_id, u64 interval)
Start a Tw Timer.
Definition: tw_timer_template.c:296
tw_timer_wheel_slot_t::head_index
u32 head_index
Listhead of timers which expire in this interval.
Definition: tw_timer_template.h:160
u16
unsigned short u16
Definition: types.h:57
TWT::expired_timer_handles
u32 * expired_timer_handles
vectors of expired timers
Definition: tw_timer_template.h:219
TWT::last_run_time
f64 last_run_time
Last time the wheel ran.
Definition: tw_timer_template.h:189
TWT::ticks_per_second
f64 ticks_per_second
Timer ticks per second.
Definition: tw_timer_template.h:192
tw_timer_wheel_slot_t
Definition: tw_timer_template.h:157
uword
u64 uword
Definition: types.h:112
tw_timer_update
void TW() tw_timer_update(TWT(tw_timer_wheel) *tw, u32 handle, u64 interval)
Update a tw timer.
Definition: tw_timer_template.c:392
tw_timer_handle_is_free
int TW() tw_timer_handle_is_free(TWT(tw_timer_wheel) *tw, u32 handle)
Definition: tw_timer_template.c:380
pool.h
Fixed length block allocator. Pools are built from clib vectors and bitmaps. Use pools when repeatedl...
TW_SLOTS_PER_RING
#define TW_SLOTS_PER_RING
Definition: tcp_types.h:464
f64
double f64
Definition: types.h:142
expired_timer_callback
static void expired_timer_callback(u32 *expired_timers)
Definition: wireguard_timer.c:281
TWT
#define TWT(a)
Definition: tw_timer_template.h:27
tw_ring_index_t
tw_ring_index_t
Definition: tw_timer_template.h:162
interval
u16 interval
Definition: vrrp.api:34
u64
unsigned long u64
Definition: types.h:89
TW_TIMER_RING_FAST
@ TW_TIMER_RING_FAST
Fast timer ring ID.
Definition: tw_timer_template.h:165
TWT::next
u32 next
next, previous pool indices
Definition: tw_timer_template.h:121
u32
unsigned int u32
Definition: types.h:88
TW_TIMER_RING_GLACIER
@ TW_TIMER_RING_GLACIER
Glacier ring ID.
Definition: tw_timer_template.h:169
tw_timer_expire_timers_vec
u32 *TW() tw_timer_expire_timers_vec(TWT(tw_timer_wheel) *tw, f64 now, u32 *vec)
Definition: tw_timer_template.c:820
TWT::user_handle
u32 user_handle
user timer handle
Definition: tw_timer_template.h:148
now
f64 now
Definition: nat44_ei_out2in.c:710
TWT::max_expirations
u32 max_expirations
maximum expirations
Definition: tw_timer_template.h:222
TW_TIMER_WHEELS
#define TW_TIMER_WHEELS
Definition: tcp_types.h:463
u8
unsigned char u8
Definition: types.h:56
pad
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
TW_TIMER_RING_SLOW
@ TW_TIMER_RING_SLOW
Slow timer ring ID.
Definition: tw_timer_template.h:167
TW
#define TW(a)
Definition: tw_timer_template.h:31
tw_timer_wheel_free
void TW() tw_timer_wheel_free(TWT(tw_timer_wheel) *tw)
Free a tw timer wheel template instance.
Definition: tw_timer_template.c:454
TWT
Definition: tw_timer_template.h:118
tw_timer_wheel_init
void TW() tw_timer_wheel_init(TWT(tw_timer_wheel) *tw, void *expired_timer_callback, f64 timer_interval, u32 max_expirations)
Initialize a tw timer wheel template instance.
Definition: tw_timer_template.c:408
TWT::timer_interval
f64 timer_interval
Timer interval, also needed to avoid fp divide in speed path.
Definition: tw_timer_template.h:195