src/vppinfra/timing_wheel.h

   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. */
  25   u32 cpu_time_relative_to_base;
  26
  27   /* User data to store in this bin. */
  28   u32 user_data;
  29 } timing_wheel_elt_t;
  30
  31 /* Overflow wheel elements where time does not fit into 32 bits. */
  32 typedef struct
  33 {
  34   /* Absolute time of this element. */
  35   u64 cpu_time;
  36
  37   /* User data to store in this bin. */
  38   u32 user_data;
  39
  40   u32 pad;
  41 } timing_wheel_overflow_elt_t;
  42
  43 typedef struct
  44 {
  45   /* 2^M bits: 1 means vector is non-zero else zero. */
  46   uword *occupancy_bitmap;
  47
  48   /* 2^M element table of element vectors, one for each time bin. */
  49   timing_wheel_elt_t **elts;
  50 } timing_wheel_level_t;
  51
  52 typedef struct
  53 {
  54   /* Vector of refill counts per level. */
  55   u64 *refills;
  56
  57   /* Number of times cpu time base was rescaled. */
  58   u64 cpu_time_base_advances;
  59 } timing_wheel_stats_t;
  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. */
  65   u8 log2_clocks_per_bin;
  66
  67   /* Wheels are 2^M bins where 2^(N+M) >= max_sched_time. */
  68   u8 log2_bins_per_wheel;
  69
  70   /* N + M. */
  71   u8 log2_clocks_per_wheel;
  72
  73   /* Number of bits to use in cpu_time_relative_to_base field
  74      of timing_wheel_elt_t. */
  75   u8 n_wheel_elt_time_bits;
  76
  77   /* 2^M. */
  78   u32 bins_per_wheel;
  79
  80   /* 2^M - 1. */
  81   u32 bins_per_wheel_mask;
  82
  83   timing_wheel_level_t *levels;
  84
  85   timing_wheel_overflow_elt_t *overflow_pool;
  86
  87   /* Free list of element vector so we can recycle old allocated vectors. */
  88   timing_wheel_elt_t **free_elt_vectors;
  89
  90   timing_wheel_elt_t *unexpired_elts_pending_insert;
  91
  92   /* Hash table of user data values which have been deleted but not yet re-inserted. */
  93   uword *deleted_user_data_hash;
  94
  95   /* Enable validation for debugging. */
  96   u32 validate;
  97
  98   /* Time index.  Measures time in units of 2^N clock ticks from
  99      when wheel starts. */
 100   u64 current_time_index;
 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. */
 105   u64 cpu_time_base;
 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. */
 110   u64 time_index_next_cpu_time_base_update;
 111
 112   /* Cached earliest element on wheel; 0 if not valid. */
 113   u64 cached_min_cpu_time_on_wheel;
 114
 115   f64 min_sched_time, max_sched_time, cpu_clocks_per_second;
 116
 117   timing_wheel_stats_t stats;
 118 } timing_wheel_t;
 119
 120 /* Initialization function. */
 121 void timing_wheel_init (timing_wheel_t * w,
 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. */
 139 u64 timing_wheel_next_expiring_elt_time (timing_wheel_t * w);
 140
 141 /* Format a timing wheel. */
 142 format_function_t format_timing_wheel;
 143
 144 /* Testing function to validate wheel. */
 145 void timing_wheel_validate (timing_wheel_t * w);
 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  */