FD.io VPP  v21.06-3-gbb25fbf28
Vector Packet Processing
timing_wheel.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 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 #ifndef included_clib_timing_wheel_h
16 #define included_clib_timing_wheel_h
17 
18 #include <vppinfra/format.h>
19 
20 typedef struct
21 {
22  /* Time of this element in units cpu clock ticks relative to time
23  base. 32 bits should be large enough for several kilo-seconds
24  to elapse before we have to re-set time base. */
26 
27  /* User data to store in this bin. */
30 
31 /* Overflow wheel elements where time does not fit into 32 bits. */
32 typedef struct
33 {
34  /* Absolute time of this element. */
36 
37  /* User data to store in this bin. */
39 
42 
43 typedef struct
44 {
45  /* 2^M bits: 1 means vector is non-zero else zero. */
47 
48  /* 2^M element table of element vectors, one for each time bin. */
51 
52 typedef struct
53 {
54  /* Vector of refill counts per level. */
56 
57  /* Number of times cpu time base was rescaled. */
60 
61 typedef struct
62 {
63  /* Each bin is a power of two clock ticks (N)
64  chosen so that 2^N >= min_sched_time. */
66 
67  /* Wheels are 2^M bins where 2^(N+M) >= max_sched_time. */
69 
70  /* N + M. */
72 
73  /* Number of bits to use in cpu_time_relative_to_base field
74  of timing_wheel_elt_t. */
76 
77  /* 2^M. */
79 
80  /* 2^M - 1. */
82 
84 
86 
87  /* Free list of element vector so we can recycle old allocated vectors. */
89 
91 
92  /* Hash table of user data values which have been deleted but not yet re-inserted. */
94 
95  /* Enable validation for debugging. */
97 
98  /* Time index. Measures time in units of 2^N clock ticks from
99  when wheel starts. */
101 
102  /* All times are 32 bit numbers relative to cpu_time_base.
103  So, roughly every 2^(32 + N) clocks we'll need to subtract from
104  all timing_wheel_elt_t times to make sure they never overflow. */
106 
107  /* When current_time_index is >= this we update cpu_time_base
108  to avoid overflowing 32 bit cpu_time_relative_to_base
109  in timing_wheel_elt_t. */
111 
112  /* Cached earliest element on wheel; 0 if not valid. */
114 
115  f64 min_sched_time, max_sched_time, cpu_clocks_per_second;
116 
119 
120 /* Initialization function. */
122  u64 current_cpu_time, f64 cpu_clocks_per_second);
123 
124 /* Insert user data on wheel at given CPU time stamp. */
125 void timing_wheel_insert (timing_wheel_t * w, u64 insert_cpu_time,
126  u32 user_data);
127 
128 /* Delete user data from wheel (until it is again inserted). */
129 void timing_wheel_delete (timing_wheel_t * w, u32 user_data);
130 
131 /* Advance wheel and return any expired user data in vector. If non-zero
132  min_next_expiring_element_cpu_time will return a cpu time stamp
133  before which there are guaranteed to be no elements in the current wheel. */
134 u32 *timing_wheel_advance (timing_wheel_t * w, u64 advance_cpu_time,
135  u32 * expired_user_data,
136  u64 * min_next_expiring_element_cpu_time);
137 
138 /* Returns absolute time in clock cycles of next expiring element. */
140 
141 /* Format a timing wheel. */
143 
144 /* Testing function to validate wheel. */
146 
147 #endif /* included_clib_timing_wheel_h */
148 
149 /*
150  * fd.io coding-style-patch-verification: ON
151  *
152  * Local Variables:
153  * eval: (c-set-style "gnu")
154  * End:
155  */
timing_wheel_advance
u32 * timing_wheel_advance(timing_wheel_t *w, u64 advance_cpu_time, u32 *expired_user_data, u64 *min_next_expiring_element_cpu_time)
Definition: timing_wheel.c:592
timing_wheel_delete
void timing_wheel_delete(timing_wheel_t *w, u32 user_data)
Definition: timing_wheel.c:331
timing_wheel_t::bins_per_wheel
u32 bins_per_wheel
Definition: timing_wheel.h:78
timing_wheel_t::overflow_pool
timing_wheel_overflow_elt_t * overflow_pool
Definition: timing_wheel.h:85
timing_wheel_t::log2_bins_per_wheel
u8 log2_bins_per_wheel
Definition: timing_wheel.h:68
timing_wheel_overflow_elt_t::user_data
u32 user_data
Definition: timing_wheel.h:38
timing_wheel_t::current_time_index
u64 current_time_index
Definition: timing_wheel.h:100
timing_wheel_level_t::occupancy_bitmap
uword * occupancy_bitmap
Definition: timing_wheel.h:46
timing_wheel_t::stats
timing_wheel_stats_t stats
Definition: timing_wheel.h:117
timing_wheel_elt_t::cpu_time_relative_to_base
u32 cpu_time_relative_to_base
Definition: timing_wheel.h:25
timing_wheel_overflow_elt_t::cpu_time
u64 cpu_time
Definition: timing_wheel.h:35
timing_wheel_level_t
Definition: timing_wheel.h:43
timing_wheel_t::log2_clocks_per_bin
u8 log2_clocks_per_bin
Definition: timing_wheel.h:65
timing_wheel_elt_t
Definition: timing_wheel.h:20
timing_wheel_stats_t::refills
u64 * refills
Definition: timing_wheel.h:55
timing_wheel_t::free_elt_vectors
timing_wheel_elt_t ** free_elt_vectors
Definition: timing_wheel.h:88
timing_wheel_t::min_sched_time
f64 min_sched_time
Definition: timing_wheel.h:115
format_timing_wheel
format_function_t format_timing_wheel
Definition: timing_wheel.h:142
timing_wheel_t
Definition: timing_wheel.h:61
timing_wheel_next_expiring_elt_time
u64 timing_wheel_next_expiring_elt_time(timing_wheel_t *w)
Definition: timing_wheel.c:342
uword
u64 uword
Definition: types.h:112
timing_wheel_validate
void timing_wheel_validate(timing_wheel_t *w)
Definition: timing_wheel.c:164
timing_wheel_t::cpu_time_base
u64 cpu_time_base
Definition: timing_wheel.h:105
timing_wheel_elt_t::user_data
u32 user_data
Definition: timing_wheel.h:28
timing_wheel_level_t::elts
timing_wheel_elt_t ** elts
Definition: timing_wheel.h:49
f64
double f64
Definition: types.h:142
timing_wheel_insert
void timing_wheel_insert(timing_wheel_t *w, u64 insert_cpu_time, u32 user_data)
Definition: timing_wheel.c:294
format.h
timing_wheel_init
void timing_wheel_init(timing_wheel_t *w, u64 current_cpu_time, f64 cpu_clocks_per_second)
Definition: timing_wheel.c:21
timing_wheel_t::levels
timing_wheel_level_t * levels
Definition: timing_wheel.h:83
timing_wheel_t::validate
u32 validate
Definition: timing_wheel.h:96
format_function_t
u8 *() format_function_t(u8 *s, va_list *args)
Definition: format.h:48
u64
unsigned long u64
Definition: types.h:89
timing_wheel_stats_t
Definition: timing_wheel.h:52
u32
unsigned int u32
Definition: types.h:88
timing_wheel_t::n_wheel_elt_time_bits
u8 n_wheel_elt_time_bits
Definition: timing_wheel.h:75
timing_wheel_overflow_elt_t
Definition: timing_wheel.h:32
timing_wheel_t::bins_per_wheel_mask
u32 bins_per_wheel_mask
Definition: timing_wheel.h:81
timing_wheel_t::deleted_user_data_hash
uword * deleted_user_data_hash
Definition: timing_wheel.h:93
u8
unsigned char u8
Definition: types.h:56
timing_wheel_t::unexpired_elts_pending_insert
timing_wheel_elt_t * unexpired_elts_pending_insert
Definition: timing_wheel.h:90
timing_wheel_t::time_index_next_cpu_time_base_update
u64 time_index_next_cpu_time_base_update
Definition: timing_wheel.h:110
timing_wheel_t::log2_clocks_per_wheel
u8 log2_clocks_per_wheel
Definition: timing_wheel.h:71
timing_wheel_overflow_elt_t::pad
u32 pad
Definition: timing_wheel.h:40
timing_wheel_t::cached_min_cpu_time_on_wheel
u64 cached_min_cpu_time_on_wheel
Definition: timing_wheel.h:113
timing_wheel_stats_t::cpu_time_base_advances
u64 cpu_time_base_advances
Definition: timing_wheel.h:58