Wheel-timer infra

Change-Id: I5499dd6b768425a56936afae50bd578620c83d30
Signed-off-by: Dave Barach <dave@barachs.net>

1 files changed, 199 insertions, 0 deletions

diff --git a/src/vppinfra/tw_timer_template.h b/src/vppinfra/tw_timer_template.h
new file mode 100644
index 00000000000..cf15ab8a667
--- /dev/null
+++ b/src/vppinfra/tw_timer_template.h
@@ -0,0 +1,199 @@
+/*
+ * Copyright (c) 2016 Cisco and/or its affiliates.
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef TW_SUFFIX
+#error do not include tw_timer_template.h directly
+#endif
+
+#include <vppinfra/clib.h>
+#include <vppinfra/pool.h>
+
+#ifndef _twt
+#define _twt(a,b) a##b##_t
+#define __twt(a,b) _twt(a,b)
+#define TWT(a) __twt(a,TW_SUFFIX)
+
+#define _tw(a,b) a##b
+#define __tw(a,b) _tw(a,b)
+#define TW(a) __tw(a,TW_SUFFIX)
+#endif
+
+/** @file
+    @brief TW timer template header file, do not compile directly
+
+Instantiation of tw_timer_template.h generates named structures to
+implement specific timer wheel geometries. Choices include: number of
+timer wheels (currently, 1 or 2), number of slots per ring (a power of
+two), and the number of timers per "object handle".
+
+Internally, user object/timer handles are 32-bit integers, so if one
+selects 16 timers/object (4 bits), the resulting timer wheel handle is
+limited to 2**28 objects.
+
+Here are the specific settings required to generate a single 2048 slot
+wheel which supports 2 timers per object:
+
+    #define TW_TIMER_WHEELS 1
+    #define TW_SLOTS_PER_RING 2048
+    #define TW_RING_SHIFT 11
+    #define TW_RING_MASK (TW_SLOTS_PER_RING -1)
+    #define TW_TIMERS_PER_OBJECT 2
+    #define LOG2_TW_TIMERS_PER_OBJECT 1
+    #define TW_SUFFIX _2t_1w_2048sl
+
+See tw_timer_2t_1w_2048sl.h for a complete
+example.
+
+tw_timer_template.h is not intended to be #included directly. Client
+codes can include multiple timer geometry header files, although
+extreme caution would required to use the TW and TWT macros in such a
+case.
+
+API usage example:
+
+Initialize a two-timer, single 2048-slot wheel w/ a 1-second
+timer granularity:
+
+    tw_timer_wheel_init_2t_1w_2048sl (&tm->single_wheel,
+                                     expired_timer_single_callback,
+				      1.0 / * timer interval * / );
+
+Start a timer:
+
+    handle = tw_timer_start_2t_1w_2048sl (&tm->single_wheel, elt_index,
+                                          [0 | 1] / * timer id * / ,
+                                          expiration_time_in_u32_ticks);
+
+Stop a timer:
+
+    tw_timer_stop_2t_1w_2048sl (&tm->single_wheel, handle);
+
+Expired timer callback:
+
+    static void
+    expired_timer_single_callback (u32 * expired_timers)
+    {
+    	int i;
+        u32 pool_index, timer_id;
+        tw_timer_test_elt_t *e;
+        tw_timer_test_main_t *tm = &tw_timer_test_main;
+
+        for (i = 0; i < vec_len (expired_timers);
+            {
+            pool_index = expired_timers[i] & 0x7FFFFFFF;
+            timer_id = expired_timers[i] >> 31;
+
+            ASSERT (timer_id == 1);
+
+            e = pool_elt_at_index (tm->test_elts, pool_index);
+
+            if (e->expected_to_expire != tm->single_wheel.current_tick)
+              {
+              	fformat (stdout, "[%d] expired at %d not %d\n",
+                         e - tm->test_elts, tm->single_wheel.current_tick,
+                         e->expected_to_expire);
+              }
+         pool_put (tm->test_elts, e);
+         }
+     }
+ */
+
+typedef struct
+{
+  /** next, previous pool indices */
+  u32 next;
+  u32 prev;
+#if TW_TIMER_WHEELS > 0
+  /** fast ring offset, only valid in the slow ring */
+  u16 fast_ring_offset;
+  u16 pad;
+#endif
+  /** user timer handle */
+  u32 user_handle;
+} TWT (tw_timer);
+
+/*
+ * These structures ar used by all geometries,
+ * so they need a private #include block...
+ */
+#ifndef __defined_tw_timer_wheel_slot__
+#define __defined_tw_timer_wheel_slot__
+typedef struct
+{
+  /** Listhead of timers which expire in this interval */
+  u32 head_index;
+} tw_timer_wheel_slot_t;
+typedef enum
+{
+  /** Fast timer ring ID */
+  TW_TIMER_RING_FAST,
+  /** Slow timer ring ID */
+  TW_TIMER_RING_SLOW,
+} tw_ring_index_t;
+#endif /* __defined_tw_timer_wheel_slot__ */
+
+typedef struct
+{
+  /** Timer pool */
+  TWT (tw_timer) * timers;
+
+  /** Next time the wheel should run */
+  f64 next_run_time;
+
+  /** Last time the wheel ran */
+  f64 last_run_time;
+
+  /** Timer ticks per second */
+  f64 ticks_per_second;
+
+  /** Timer interval, also needed to avoid fp divide in speed path */
+  f64 timer_interval;
+
+  /** current tick */
+  u32 current_tick;
+
+  /** current wheel indices */
+  u32 current_index[TW_TIMER_WHEELS];
+
+  /** wheel arrays */
+  tw_timer_wheel_slot_t w[TW_TIMER_WHEELS][TW_SLOTS_PER_RING];
+
+  /** expired timer callback, receives a vector of handles */
+  void (*expired_timer_callback) (u32 * expired_timer_handles);
+
+  /** vector of expired timers */
+  u32 *expired_timer_handles;
+} TWT (tw_timer_wheel);
+
+u32 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw,
+			 u32 pool_index, u32 timer_id, u32 interval);
+
+void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle);
+
+void TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw,
+			       void *expired_timer_callback,
+			       f64 timer_interval);
+
+void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw);
+
+void TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now);
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */