FD.io VPP  v18.07-rc0-415-g6c78436
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  /** first expiration time */
202 
203  /** current wheel indices */
204  u32 current_index[TW_TIMER_WHEELS];
205 
206  /** wheel arrays */
208 
209 #if TW_OVERFLOW_VECTOR > 0
210  tw_timer_wheel_slot_t overflow;
211 #endif
212 
213 #if TW_FAST_WHEEL_BITMAP > 0
214  /** Fast wheel slot occupancy bitmap */
215  uword *fast_slot_bitmap;
216 #endif
217 
218  /** expired timer callback, receives a vector of handles */
219  void (*expired_timer_callback) (u32 * expired_timer_handles);
220 
221  /** vectors of expired timers */
223 
224  /** maximum expirations */
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 
235 } TWT (tw_timer_wheel);
236 
237 u32 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw,
238  u32 pool_index, u32 timer_id, u64 interval);
239 
240 void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle);
241 void TW (tw_timer_update) (TWT (tw_timer_wheel) * tw, u32 handle,
242  u64 interval);
243 
244 void TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw,
245  void *expired_timer_callback,
246  f64 timer_interval, u32 max_expirations);
247 
248 void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw);
249 
250 u32 *TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now);
251 u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now,
252  u32 * vec);
253 #if TW_FAST_WHEEL_BITMAP
254 u32 TW (tw_timer_first_expires_in_ticks) (TWT (tw_timer_wheel) * tw);
255 #endif
256 
257 #if TW_START_STOP_TRACE_SIZE > 0
258 void TW (tw_search_trace) (TWT (tw_timer_wheel) * tw, u32 handle);
259 void TW (tw_timer_trace) (TWT (tw_timer_wheel) * tw, u32 timer_id,
260  u32 pool_index, u32 handle);
261 #endif
262 
263 /*
264  * fd.io coding-style-patch-verification: ON
265  *
266  * Local Variables:
267  * eval: (c-set-style "gnu")
268  * End:
269  */
void TW() tw_timer_wheel_free(TWT(tw_timer_wheel)*tw)
Free a tw timer wheel template instance.
u64 current_tick
current tick
static vlib_cli_command_t trace
(constructor) VLIB_CLI_COMMAND (trace)
Definition: vlib_api_cli.c:862
u8 pad[3]
log2 (size of the packing page block)
Definition: bihash_doc.h:61
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.
u32 *TW() tw_timer_expire_timers_vec(TWT(tw_timer_wheel)*tw, f64 now, u32 *vec)
unsigned long u64
Definition: types.h:89
Fixed length block allocator.
typedef CLIB_PACKED(struct{u8 timer_id;u32 pool_index;u32 handle;}) TWT(trace)
#define TW_TIMER_WHEELS
u32 max_expirations
maximum expirations
f64 timer_interval
Timer interval, also needed to avoid fp divide in speed path.
unsigned char u8
Definition: types.h:56
double f64
Definition: types.h:142
u64 first_expires_tick
first expiration time
static timer_callback_t * timers
Definition: timer.c:57
unsigned int u32
Definition: types.h:88
unsigned short u16
Definition: types.h:57
#define TW_SLOTS_PER_RING
#define TWT(a)
tw_ring_index_t
void TW() tw_timer_update(TWT(tw_timer_wheel)*tw, u32 handle, u64 interval)
Update a tw timer.
u32 TW() tw_timer_start(TWT(tw_timer_wheel)*tw, u32 pool_index, u32 timer_id, u64 interval)
Start a Tw Timer.
void TW() tw_timer_stop(TWT(tw_timer_wheel)*tw, u32 handle)
Stop a tw timer.
f64 next_run_time
Next time the wheel should run.
u32 next
next, previous pool indices
Fast timer ring ID.
u32 * expired_timer_handles
vectors of expired timers
Bitmaps built as vectors of machine words.
f64 ticks_per_second
Timer ticks per second.
u32 *TW() tw_timer_expire_timers(TWT(tw_timer_wheel)*tw, f64 now)
u64 uword
Definition: types.h:112
f64 last_run_time
Last time the wheel ran.
u32 user_handle
user timer handle
#define TW(a)
u32 head_index
Listhead of timers which expire in this interval.
Slow timer ring ID.