src/vppinfra/tw_timer_template.h

   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 */
 121   u32 next;
 122   u32 prev;
 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 */
 148   u32 user_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 */
 160   u32 head_index;
 161 } tw_timer_wheel_slot_t;
 162 typedef enum
 163 {
 164   /** Fast timer ring ID */
 165   TW_TIMER_RING_FAST,
 166   /** Slow timer ring ID */
 167   TW_TIMER_RING_SLOW,
 168   /** Glacier ring ID */
 169   TW_TIMER_RING_GLACIER,
 170 } tw_ring_index_t;
 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 */
 186   f64 next_run_time;
 187
 188   /** Last time the wheel ran */
 189   f64 last_run_time;
 190
 191   /** Timer ticks per second */
 192   f64 ticks_per_second;
 193
 194   /** Timer interval, also needed to avoid fp divide in speed path */
 195   f64 timer_interval;
 196
 197   /** current tick */
 198   u64 current_tick;
 199
 200   /** first expiration time */
 201   u64 first_expires_tick;
 202
 203   /** current wheel indices */
 204   u32 current_index[TW_TIMER_WHEELS];
 205
 206   /** wheel arrays */
 207   tw_timer_wheel_slot_t w[TW_TIMER_WHEELS][TW_SLOTS_PER_RING];
 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 */
 222   u32 *expired_timer_handles;
 223
 224   /** maximum expirations */
 225   u32 max_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
 242 void TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw,
 243                                void *expired_timer_callback,
 244                                f64 timer_interval, u32 max_expirations);
 245
 246 void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw);
 247
 248 u32 *TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now);
 249 u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now,
 250                                       u32 * vec);
 251 #if TW_FAST_WHEEL_BITMAP
 252 u32 TW (tw_timer_first_expires_in_ticks) (TWT (tw_timer_wheel) * tw);
 253 #endif
 254
 255 #if TW_START_STOP_TRACE_SIZE > 0
 256 void TW (tw_search_trace) (TWT (tw_timer_wheel) * tw, u32 handle);
 257 void TW (tw_timer_trace) (TWT (tw_timer_wheel) * tw, u32 timer_id,
 258                           u32 pool_index, u32 handle);
 259 #endif
 260
 261 /*
 262  * fd.io coding-style-patch-verification: ON
 263  *
 264  * Local Variables:
 265  * eval: (c-set-style "gnu")
 266  * End:
 267  */