FD.io VPP  v17.07.01-10-g3be13f0
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 
23 #ifndef _twt
24 #define _twt(a,b) a##b##_t
25 #define __twt(a,b) _twt(a,b)
26 #define TWT(a) __twt(a,TW_SUFFIX)
27 
28 #define _tw(a,b) a##b
29 #define __tw(a,b) _tw(a,b)
30 #define TW(a) __tw(a,TW_SUFFIX)
31 #endif
32 
33 /** @file
34  @brief TW timer template header file, do not compile directly
35 
36 Instantiation of tw_timer_template.h generates named structures to
37 implement specific timer wheel geometries. Choices include: number of
38 timer wheels (currently, 1 or 2), number of slots per ring (a power of
39 two), and the number of timers per "object handle".
40 
41 Internally, user object/timer handles are 32-bit integers, so if one
42 selects 16 timers/object (4 bits), the resulting timer wheel handle is
43 limited to 2**28 objects.
44 
45 Here are the specific settings required to generate a single 2048 slot
46 wheel which supports 2 timers per object:
47 
48  #define TW_TIMER_WHEELS 1
49  #define TW_SLOTS_PER_RING 2048
50  #define TW_RING_SHIFT 11
51  #define TW_RING_MASK (TW_SLOTS_PER_RING -1)
52  #define TW_TIMERS_PER_OBJECT 2
53  #define LOG2_TW_TIMERS_PER_OBJECT 1
54  #define TW_SUFFIX _2t_1w_2048sl
55 
56 See tw_timer_2t_1w_2048sl.h for a complete
57 example.
58 
59 tw_timer_template.h is not intended to be #included directly. Client
60 codes can include multiple timer geometry header files, although
61 extreme caution would required to use the TW and TWT macros in such a
62 case.
63 
64 API usage example:
65 
66 Initialize a two-timer, single 2048-slot wheel w/ a 1-second
67 timer granularity:
68 
69  tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
70  expired_timer_single_callback,
71  1.0 / * timer interval * / );
72 
73 Start a timer:
74 
75  handle = tw_timer_start_2t_1w_2048sl (&tm->single_wheel, elt_index,
76  [0 | 1] / * timer id * / ,
77  expiration_time_in_u32_ticks);
78 
79 Stop a timer:
80 
81  tw_timer_stop_2t_1w_2048sl (&tm->single_wheel, handle);
82 
83 Expired timer callback:
84 
85  static void
86  expired_timer_single_callback (u32 * expired_timers)
87  {
88  int i;
89  u32 pool_index, timer_id;
90  tw_timer_test_elt_t *e;
91  tw_timer_test_main_t *tm = &tw_timer_test_main;
92 
93  for (i = 0; i < vec_len (expired_timers);
94  {
95  pool_index = expired_timers[i] & 0x7FFFFFFF;
96  timer_id = expired_timers[i] >> 31;
97 
98  ASSERT (timer_id == 1);
99 
100  e = pool_elt_at_index (tm->test_elts, pool_index);
101 
102  if (e->expected_to_expire != tm->single_wheel.current_tick)
103  {
104  fformat (stdout, "[%d] expired at %d not %d\n",
105  e - tm->test_elts, tm->single_wheel.current_tick,
106  e->expected_to_expire);
107  }
108  pool_put (tm->test_elts, e);
109  }
110  }
111  */
112 
113 #if (TW_TIMER_WHEELS != 1 && TW_TIMER_WHEELS != 2 && TW_TIMER_WHEELS != 3)
114 #error TW_TIMER_WHEELS must be 1, 2 or 3
115 #endif
116 
117 typedef struct
118 {
119  /** next, previous pool indices */
122 
123  union
124  {
125  struct
126  {
127 #if (TW_TIMER_WHEELS == 3)
128  /** fast ring offset, only valid in the slow ring */
129  u16 fast_ring_offset;
130  /** slow ring offset, only valid in the glacier ring */
131  u16 slow_ring_offset;
132 #endif
133 #if (TW_TIMER_WHEELS == 2)
134  /** fast ring offset, only valid in the slow ring */
135  u16 fast_ring_offset;
136  /** slow ring offset, only valid in the glacier ring */
137  u16 pad;
138 #endif
139  };
140 
141 #if (TW_OVERFLOW_VECTOR > 0)
142  u64 expiration_time;
143 #endif
144  };
145 
146  /** user timer handle */
148 } TWT (tw_timer);
149 
150 /*
151  * These structures ar used by all geometries,
152  * so they need a private #include block...
153  */
154 #ifndef __defined_tw_timer_wheel_slot__
155 #define __defined_tw_timer_wheel_slot__
156 typedef struct
157 {
158  /** Listhead of timers which expire in this interval */
161 typedef enum
162 {
163  /** Fast timer ring ID */
165  /** Slow timer ring ID */
167  /** Glacier ring ID */
170 #endif /* __defined_tw_timer_wheel_slot__ */
171 
172 typedef struct
173 {
174  /** Timer pool */
175  TWT (tw_timer) * timers;
176 
177  /** Next time the wheel should run */
179 
180  /** Last time the wheel ran */
182 
183  /** Timer ticks per second */
185 
186  /** Timer interval, also needed to avoid fp divide in speed path */
188 
189  /** current tick */
191 
192  /** first expiration time */
194 
195  /** current wheel indices */
196  u32 current_index[TW_TIMER_WHEELS];
197 
198  /** wheel arrays */
200 
201 #if TW_OVERFLOW_VECTOR > 0
202  tw_timer_wheel_slot_t overflow;
203 #endif
204 
205  /** expired timer callback, receives a vector of handles */
206  void (*expired_timer_callback) (u32 * expired_timer_handles);
207 
208  /** vector of expired timers */
210 
211  /** maximum expirations */
213 } TWT (tw_timer_wheel);
214 
215 u32 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw,
216  u32 pool_index, u32 timer_id, u64 interval);
217 
218 void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle);
219 
220 void TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw,
221  void *expired_timer_callback,
222  f64 timer_interval, u32 max_expirations);
223 
224 void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw);
225 
226 u32 *TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now);
227 u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now,
228  u32 * vec);
229 
230 /*
231  * fd.io coding-style-patch-verification: ON
232  *
233  * Local Variables:
234  * eval: (c-set-style "gnu")
235  * End:
236  */
void TW() tw_timer_wheel_free(TWT(tw_timer_wheel)*tw)
Free a tw timer wheel template instance.
u64 current_tick
current tick
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)
Fixed length block allocator.
#define TW_TIMER_WHEELS
u32 max_expirations
maximum expirations
f64 timer_interval
Timer interval, also needed to avoid fp divide in speed path.
u64 first_expires_tick
first expiration time
static timer_callback_t * timers
Definition: timer.c:56
unsigned long u64
Definition: types.h:89
#define TW_SLOTS_PER_RING
#define TWT(a)
tw_ring_index_t
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.
unsigned int u32
Definition: types.h:88
u32 * expired_timer_handles
vector of expired timers
f64 ticks_per_second
Timer ticks per second.
u32 *TW() tw_timer_expire_timers(TWT(tw_timer_wheel)*tw, f64 now)
unsigned short u16
Definition: types.h:57
double f64
Definition: types.h:142
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.