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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
15 #ifndef included_clib_timing_wheel_h
16 #define included_clib_timing_wheel_h
18 #include <vppinfra/format.h>
21 /* Time of this element in units cpu clock ticks relative to time
22 base. 32 bits should be large enough for serveral kilo-seconds
23 to elapse before we have to re-set time base. */
24 u32 cpu_time_relative_to_base;
26 /* User data to store in this bin. */
30 /* Overflow wheel elements where time does not fit into 32 bits. */
32 /* Absolute time of this element. */
35 /* User data to store in this bin. */
39 } timing_wheel_overflow_elt_t;
42 /* 2^M bits: 1 means vector is non-zero else zero. */
43 uword * occupancy_bitmap;
45 /* 2^M element table of element vectors, one for each time bin. */
46 timing_wheel_elt_t ** elts;
47 } timing_wheel_level_t;
50 /* Vector of refill counts per level. */
53 /* Number of times cpu time base was rescaled. */
54 u64 cpu_time_base_advances;
55 } timing_wheel_stats_t;
58 /* Each bin is a power of two clock ticks (N)
59 chosen so that 2^N >= min_sched_time. */
60 u8 log2_clocks_per_bin;
62 /* Wheels are 2^M bins where 2^(N+M) >= max_sched_time. */
63 u8 log2_bins_per_wheel;
66 u8 log2_clocks_per_wheel;
68 /* Number of bits to use in cpu_time_relative_to_base field
69 of timing_wheel_elt_t. */
70 u8 n_wheel_elt_time_bits;
76 u32 bins_per_wheel_mask;
78 timing_wheel_level_t * levels;
80 timing_wheel_overflow_elt_t * overflow_pool;
82 /* Free list of element vector so we can recycle old allocated vectors. */
83 timing_wheel_elt_t ** free_elt_vectors;
85 timing_wheel_elt_t * unexpired_elts_pending_insert;
87 /* Hash table of user data values which have been deleted but not yet re-inserted. */
88 uword * deleted_user_data_hash;
90 /* Enable validation for debugging. */
93 /* Time index. Measures time in units of 2^N clock ticks from
95 u64 current_time_index;
97 /* All times are 32 bit numbers relative to cpu_time_base.
98 So, roughly every 2^(32 + N) clocks we'll need to subtract from
99 all timing_wheel_elt_t times to make sure they never overflow. */
102 /* When current_time_index is >= this we update cpu_time_base
103 to avoid overflowing 32 bit cpu_time_relative_to_base
104 in timing_wheel_elt_t. */
105 u64 time_index_next_cpu_time_base_update;
107 /* Cached earliest element on wheel; 0 if not valid. */
108 u64 cached_min_cpu_time_on_wheel;
110 f64 min_sched_time, max_sched_time, cpu_clocks_per_second;
112 timing_wheel_stats_t stats;
115 /* Initialization function. */
116 void timing_wheel_init (timing_wheel_t * w,
117 u64 current_cpu_time, f64 cpu_clocks_per_second);
119 /* Insert user data on wheel at given CPU time stamp. */
120 void timing_wheel_insert (timing_wheel_t * w, u64 insert_cpu_time, u32 user_data);
122 /* Delete user data from wheel (until it is again inserted). */
123 void timing_wheel_delete (timing_wheel_t * w, u32 user_data);
125 /* Advance wheel and return any expired user data in vector. If non-zero
126 min_next_expiring_element_cpu_time will return a cpu time stamp
127 before which there are guaranteed to be no elements in the current wheel. */
128 u32 * timing_wheel_advance (timing_wheel_t * w, u64 advance_cpu_time, u32 * expired_user_data,
129 u64 * min_next_expiring_element_cpu_time);
131 /* Returns absolute time in clock cycles of next expiring element. */
132 u64 timing_wheel_next_expiring_elt_time (timing_wheel_t * w);
134 /* Format a timing wheel. */
135 format_function_t format_timing_wheel;
137 /* Testing function to validate wheel. */
138 void timing_wheel_validate (timing_wheel_t * w);
140 #endif /* included_clib_timing_wheel_h */