1 files changed, 353 insertions, 52 deletions

diff --git a/src/vppinfra/tw_timer_template.c b/src/vppinfra/tw_timer_template.c
index e3f44500..a0c407ae 100644
--- a/src/vppinfra/tw_timer_template.c
+++ b/src/vppinfra/tw_timer_template.c
@@ -18,16 +18,19 @@
  *
  *
  */
-
 static inline u32
 TW (make_internal_timer_handle) (u32 pool_index, u32 timer_id)
 {
   u32 handle;
 
   ASSERT (timer_id < TW_TIMERS_PER_OBJECT);
+#if LOG2_TW_TIMERS_PER_OBJECT > 0
   ASSERT (pool_index < (1 << (32 - LOG2_TW_TIMERS_PER_OBJECT)));
 
   handle = (timer_id << (32 - LOG2_TW_TIMERS_PER_OBJECT)) | (pool_index);
+#else
+  handle = pool_index;
+#endif
   return handle;
 }
 
@@ -79,17 +82,23 @@ timer_remove (TWT (tw_timer) * pool, u32 index)
  * @param tw_timer_wheel_t * tw timer wheel object pointer
  * @param u32 pool_index user pool index, presumably for a tw session
  * @param u32 timer_id app-specific timer ID. 4 bits.
- * @param u32 interval timer interval in ticks
+ * @param u64 interval timer interval in ticks
  * @returns handle needed to cancel the timer
  */
 u32
 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id,
-		     u32 interval)
+		     u64 interval)
 {
 #if TW_TIMER_WHEELS > 1
   u16 slow_ring_offset;
   u32 carry;
 #endif
+#if TW_TIMER_WHEELS > 2
+  u16 glacier_ring_offset;
+#endif
+#if TW_OVERFLOW_VECTOR > 0
+  u64 interval_plus_time_to_wrap, triple_wrap_mask;
+#endif
   u16 fast_ring_offset;
   tw_timer_wheel_slot_t *ts;
   TWT (tw_timer) * t;
@@ -97,31 +106,89 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id,
   ASSERT (interval);
 
   pool_get (tw->timers, t);
-  t->next = t->prev = ~0;
-#if TW_TIMER_WHEELS > 1
-  t->fast_ring_offset = ~0;
-#endif
+  memset (t, 0xff, sizeof (*t));
+
   t->user_handle = TW (make_internal_timer_handle) (pool_index, timer_id);
 
+  /* Factor interval into 1..3 wheel offsets */
+#if TW_TIMER_WHEELS > 2
+#if TW_OVERFLOW_VECTOR > 0
+  /*
+   * This is tricky. Put a timer onto the overflow
+   * vector if the interval PLUS the time
+   * until the next triple-wrap exceeds one full revolution
+   * of all three wheels.
+   */
+  triple_wrap_mask = (1 << (3 * TW_RING_SHIFT)) - 1;
+  interval_plus_time_to_wrap =
+    interval + (tw->current_tick & triple_wrap_mask);
+  if ((interval_plus_time_to_wrap >= 1 << (3 * TW_RING_SHIFT)))
+    {
+      t->expiration_time = tw->current_tick + interval;
+      ts = &tw->overflow;
+      timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+      return t - tw->timers;
+    }
+#endif
+
+  glacier_ring_offset = interval >> (2 * TW_RING_SHIFT);
+  ASSERT (glacier_ring_offset < TW_SLOTS_PER_RING);
+  interval -= (glacier_ring_offset << (2 * TW_RING_SHIFT));
+#endif
+#if TW_TIMER_WHEELS > 1
+  slow_ring_offset = interval >> TW_RING_SHIFT;
+  ASSERT (slow_ring_offset < TW_SLOTS_PER_RING);
+  interval -= (slow_ring_offset << TW_RING_SHIFT);
+#endif
   fast_ring_offset = interval & TW_RING_MASK;
-  fast_ring_offset += tw->current_index[TW_TIMER_RING_FAST];
+
+  /*
+   * Account for the current wheel positions(s)
+   * This is made slightly complicated by the fact that the current
+   * index vector will contain (TW_SLOTS_PER_RING, ...) when
+   * the actual position is (0, ...)
+   */
+
+  fast_ring_offset += tw->current_index[TW_TIMER_RING_FAST] & TW_RING_MASK;
+
 #if TW_TIMER_WHEELS > 1
   carry = fast_ring_offset >= TW_SLOTS_PER_RING ? 1 : 0;
   fast_ring_offset %= TW_SLOTS_PER_RING;
-  slow_ring_offset = (interval >> TW_RING_SHIFT) + carry;
+  slow_ring_offset += (tw->current_index[TW_TIMER_RING_SLOW] & TW_RING_MASK)
+    + carry;
+  carry = slow_ring_offset >= TW_SLOTS_PER_RING ? 1 : 0;
+  slow_ring_offset %= TW_SLOTS_PER_RING;
+#endif
 
-  /* Timer duration exceeds ~7 hrs? Oops */
-  ASSERT (slow_ring_offset < TW_SLOTS_PER_RING);
+#if TW_TIMER_WHEELS > 2
+  glacier_ring_offset +=
+    (tw->current_index[TW_TIMER_RING_GLACIER] & TW_RING_MASK) + carry;
+  glacier_ring_offset %= TW_SLOTS_PER_RING;
+#endif
 
-  /* Timer expires more than 51.2 seconds from now? */
-  if (slow_ring_offset)
+#if TW_TIMER_WHEELS > 2
+  if (glacier_ring_offset !=
+      (tw->current_index[TW_TIMER_RING_GLACIER] & TW_RING_MASK))
     {
-      slow_ring_offset += tw->current_index[TW_TIMER_RING_SLOW];
-      slow_ring_offset %= TW_SLOTS_PER_RING;
+      /* We'll need slow and fast ring offsets later */
+      t->slow_ring_offset = slow_ring_offset;
+      t->fast_ring_offset = fast_ring_offset;
 
-      /* We'll want the fast ring offset later... */
+      ts = &tw->w[TW_TIMER_RING_GLACIER][glacier_ring_offset];
+
+      timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+
+      return t - tw->timers;
+    }
+#endif
+
+#if TW_TIMER_WHEELS > 1
+  /* Timer expires more than 51.2 seconds from now? */
+  if (slow_ring_offset !=
+      (tw->current_index[TW_TIMER_RING_SLOW] & TW_RING_MASK))
+    {
+      /* We'll need the fast ring offset later... */
       t->fast_ring_offset = fast_ring_offset;
-      ASSERT (t->fast_ring_offset < TW_SLOTS_PER_RING);
 
       ts = &tw->w[TW_TIMER_RING_SLOW][slow_ring_offset];
 
@@ -131,7 +198,6 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id,
     }
 #else
   fast_ring_offset %= TW_SLOTS_PER_RING;
-  ASSERT (interval < TW_SLOTS_PER_RING);
 #endif
 
   /* Timer expires less than one fast-ring revolution from now */
@@ -141,6 +207,41 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id,
   return t - tw->timers;
 }
 
+#if TW_TIMER_SCAN_FOR_HANDLE > 0
+int TW (scan_for_handle) (TWT (tw_timer_wheel) * tw, u32 handle)
+{
+  int i, j;
+  tw_timer_wheel_slot_t *ts;
+  TWT (tw_timer) * t, *head;
+  u32 next_index;
+  int rv = 0;
+
+  for (i = 0; i < TW_TIMER_WHEELS; i++)
+    {
+      for (j = 0; j < TW_SLOTS_PER_RING; j++)
+	{
+	  ts = &tw->w[i][j];
+	  head = pool_elt_at_index (tw->timers, ts->head_index);
+	  next_index = head->next;
+
+	  while (next_index != ts->head_index)
+	    {
+	      t = pool_elt_at_index (tw->timers, next_index);
+	      if (next_index == handle)
+		{
+		  clib_warning ("handle %d found in ring %d slot %d",
+				handle, i, j);
+		  clib_warning ("user handle 0x%x", t->user_handle);
+		  rv = 1;
+		}
+	      next_index = t->next;
+	    }
+	}
+    }
+  return rv;
+}
+#endif /* TW_TIMER_SCAN_FOR_HANDLE */
+
 /**
  * @brief Stop a tw timer
  * @param tw_timer_wheel_t * tw timer wheel object pointer
@@ -164,7 +265,7 @@ void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle)
  * @brief Initialize a tw timer wheel template instance
  * @param tw_timer_wheel_t * tw timer wheel object pointer
  * @param void * expired_timer_callback. Passed a u32 * vector of
- *   expired timer handles.
+ *   expired timer handles. The callback is optional.
  * @param f64 timer_interval_in_seconds
  */
 void
@@ -185,6 +286,9 @@ TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw,
     }
   tw->timer_interval = timer_interval_in_seconds;
   tw->ticks_per_second = 1.0 / timer_interval_in_seconds;
+  tw->first_expires_tick = ~0ULL;
+  vec_validate (tw->expired_timer_handles, 0);
+  _vec_len (tw->expired_timer_handles) = 0;
 
   for (ring = 0; ring < TW_TIMER_WHEELS; ring++)
     {
@@ -197,6 +301,14 @@ TW (tw_timer_wheel_init) (TWT (tw_timer_wheel) * tw,
 	  ts->head_index = t - tw->timers;
 	}
     }
+
+#if TW_OVERFLOW_VECTOR > 0
+  ts = &tw->overflow;
+  pool_get (tw->timers, t);
+  memset (t, 0xff, sizeof (*t));
+  t->next = t->prev = t - tw->timers;
+  ts->head_index = t - tw->timers;
+#endif
 }
 
 /**
@@ -227,6 +339,21 @@ void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw)
 	  pool_put (tw->timers, head);
 	}
     }
+
+#if TW_OVERFLOW_VECVOR > 0
+  ts = &tw->overflow;
+  head = pool_elt_at_index (tw->timers, ts->head_index);
+  next_index = head->next;
+
+  while (next_index != ts->head_index)
+    {
+      t = pool_elt_at_index (tw->timers, next_index);
+      next_index = t->next;
+      pool_put (tw->timers, t);
+    }
+  pool_put (tw->timers, head);
+#endif
+
   memset (tw, 0, sizeof (*tw));
 }
 
@@ -235,50 +362,185 @@ void TW (tw_timer_wheel_free) (TWT (tw_timer_wheel) * tw)
  * as needed. This routine should be called once every timer_interval seconds
  * @param tw_timer_wheel_t * tw timer wheel template instance pointer
  * @param f64 now the current time, e.g. from vlib_time_now(vm)
+ * @returns u32 * vector of expired user handles
  */
-u32 TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now)
+static inline
+  u32 * TW (tw_timer_expire_timers_internal) (TWT (tw_timer_wheel) * tw,
+					      f64 now,
+					      u32 * callback_vector_arg)
 {
   u32 nticks, i;
   tw_timer_wheel_slot_t *ts;
   TWT (tw_timer) * t, *head;
+  u32 *callback_vector;
   u32 fast_wheel_index;
   u32 next_index;
-  u32 nexpirations, total_nexpirations;
-#if TW_TIMER_WHEELS > 1
-  u32 slow_wheel_index;
-#endif
+  u32 slow_wheel_index __attribute__ ((unused));
+  u32 glacier_wheel_index __attribute__ ((unused));
 
   /* Shouldn't happen */
   if (PREDICT_FALSE (now < tw->next_run_time))
-    return 0;
+    return callback_vector_arg;
 
   /* Number of ticks which have occurred */
   nticks = tw->ticks_per_second * (now - tw->last_run_time);
   if (nticks == 0)
-    return 0;
+    return callback_vector_arg;
 
   /* Remember when we ran, compute next runtime */
   tw->next_run_time = (now + tw->timer_interval);
 
-  total_nexpirations = 0;
+  if (callback_vector_arg == 0)
+    {
+      _vec_len (tw->expired_timer_handles) = 0;
+      callback_vector = tw->expired_timer_handles;
+    }
+  else
+    callback_vector = callback_vector_arg;
+
   for (i = 0; i < nticks; i++)
     {
       fast_wheel_index = tw->current_index[TW_TIMER_RING_FAST];
+      if (TW_TIMER_WHEELS > 1)
+	slow_wheel_index = tw->current_index[TW_TIMER_RING_SLOW];
+      if (TW_TIMER_WHEELS > 2)
+	glacier_wheel_index = tw->current_index[TW_TIMER_RING_GLACIER];
+
+#if TW_OVERFLOW_VECTOR > 0
+      /* Triple odometer-click? Process the overflow vector... */
+      if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING
+			 && slow_wheel_index == TW_SLOTS_PER_RING
+			 && glacier_wheel_index == TW_SLOTS_PER_RING))
+	{
+	  u64 interval;
+	  u32 new_glacier_ring_offset, new_slow_ring_offset;
+	  u32 new_fast_ring_offset;
 
+	  ts = &tw->overflow;
+	  head = pool_elt_at_index (tw->timers, ts->head_index);
+	  next_index = head->next;
+
+	  /* Make slot empty */
+	  head->next = head->prev = ts->head_index;
+
+	  /* traverse slot, place timers wherever they go */
+	  while (next_index != head - tw->timers)
+	    {
+	      t = pool_elt_at_index (tw->timers, next_index);
+	      next_index = t->next;
+
+	      /* Remove from the overflow vector (hammer) */
+	      t->next = t->prev = ~0;
+
+	      ASSERT (t->expiration_time >= tw->current_tick);
+
+	      interval = t->expiration_time - tw->current_tick;
+
+	      /* Right back onto the overflow vector? */
+	      if (interval >= (1 << (3 * TW_RING_SHIFT)))
+		{
+		  ts = &tw->overflow;
+		  timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+		  continue;
+		}
+	      /* Compute ring offsets */
+	      new_glacier_ring_offset = interval >> (2 * TW_RING_SHIFT);
+
+	      interval -= (new_glacier_ring_offset << (2 * TW_RING_SHIFT));
+
+	      /* Note: the wheels are at (0,0,0), no add-with-carry needed */
+	      new_slow_ring_offset = interval >> TW_RING_SHIFT;
+	      interval -= (new_slow_ring_offset << TW_RING_SHIFT);
+	      new_fast_ring_offset = interval & TW_RING_MASK;
+	      t->slow_ring_offset = new_slow_ring_offset;
+	      t->fast_ring_offset = new_fast_ring_offset;
+
+	      /* Timer expires Right Now */
+	      if (PREDICT_FALSE (t->slow_ring_offset == 0 &&
+				 t->fast_ring_offset == 0 &&
+				 new_glacier_ring_offset == 0))
+		{
+		  vec_add1 (callback_vector, t->user_handle);
+		  pool_put (tw->timers, t);
+		}
+	      /* Timer moves to the glacier ring */
+	      else if (new_glacier_ring_offset)
+		{
+		  ts = &tw->w[TW_TIMER_RING_GLACIER][new_glacier_ring_offset];
+		  timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+		}
+	      /* Timer moves to the slow ring */
+	      else if (t->slow_ring_offset)
+		{
+		  /* Add to slow ring */
+		  ts = &tw->w[TW_TIMER_RING_SLOW][t->slow_ring_offset];
+		  timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+		}
+	      /* Timer timer moves to the fast ring */
+	      else
+		{
+		  ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset];
+		  timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+		}
+	    }
+	}
+#endif
+
+#if TW_TIMER_WHEELS > 2
       /*
-       * If we've been around the fast ring once,
-       * process one slot in the slow ring before we handle
-       * the fast ring.
+       * Double odometer-click? Process one slot in the glacier ring...
        */
-      if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING))
+      if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING
+			 && slow_wheel_index == TW_SLOTS_PER_RING))
 	{
-	  fast_wheel_index = tw->current_index[TW_TIMER_RING_FAST] = 0;
+	  glacier_wheel_index %= TW_SLOTS_PER_RING;
+	  ts = &tw->w[TW_TIMER_RING_GLACIER][glacier_wheel_index];
 
-#if TW_TIMER_WHEELS > 1
-	  tw->current_index[TW_TIMER_RING_SLOW]++;
-	  tw->current_index[TW_TIMER_RING_SLOW] %= TW_SLOTS_PER_RING;
-	  slow_wheel_index = tw->current_index[TW_TIMER_RING_SLOW];
+	  head = pool_elt_at_index (tw->timers, ts->head_index);
+	  next_index = head->next;
+
+	  /* Make slot empty */
+	  head->next = head->prev = ts->head_index;
+
+	  /* traverse slot, deal timers into slow ring */
+	  while (next_index != head - tw->timers)
+	    {
+	      t = pool_elt_at_index (tw->timers, next_index);
+	      next_index = t->next;
+
+	      /* Remove from glacier ring slot (hammer) */
+	      t->next = t->prev = ~0;
+
+	      /* Timer expires Right Now */
+	      if (PREDICT_FALSE (t->slow_ring_offset == 0 &&
+				 t->fast_ring_offset == 0))
+		{
+		  vec_add1 (callback_vector, t->user_handle);
+		  pool_put (tw->timers, t);
+		}
+	      /* Timer expires during slow-wheel tick 0 */
+	      else if (PREDICT_FALSE (t->slow_ring_offset == 0))
+		{
+		  ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset];
+		  timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+		}
+	      else		/* typical case */
+		{
+		  /* Add to slow ring */
+		  ts = &tw->w[TW_TIMER_RING_SLOW][t->slow_ring_offset];
+		  timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+		}
+	    }
+	}
+#endif
 
+#if TW_TIMER_WHEELS > 1
+      /*
+       * Single odometer-click? Process a slot in the slow ring,
+       */
+      if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING))
+	{
+	  slow_wheel_index %= TW_SLOTS_PER_RING;
 	  ts = &tw->w[TW_TIMER_RING_SLOW][slow_wheel_index];
 
 	  head = pool_elt_at_index (tw->timers, ts->head_index);
@@ -293,19 +555,27 @@ u32 TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now)
 	      t = pool_elt_at_index (tw->timers, next_index);
 	      next_index = t->next;
 
-	      /* Remove from slow ring slot (hammer) */
+	      /* Remove from sloe ring slot (hammer) */
 	      t->next = t->prev = ~0;
-	      ASSERT (t->fast_ring_offset < TW_SLOTS_PER_RING);
-	      /* Add to fast ring */
-	      ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset];
-	      timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+
+	      /* Timer expires Right Now */
+	      if (PREDICT_FALSE (t->fast_ring_offset == 0))
+		{
+		  vec_add1 (callback_vector, t->user_handle);
+		  pool_put (tw->timers, t);
+		}
+	      else		/* typical case */
+		{
+		  /* Add to fast ring */
+		  ts = &tw->w[TW_TIMER_RING_FAST][t->fast_ring_offset];
+		  timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+		}
 	    }
-#endif
 	}
+#endif
 
       /* Handle the fast ring */
-      vec_reset_length (tw->expired_timer_handles);
-
+      fast_wheel_index %= TW_SLOTS_PER_RING;
       ts = &tw->w[TW_TIMER_RING_FAST][fast_wheel_index];
 
       head = pool_elt_at_index (tw->timers, ts->head_index);
@@ -319,26 +589,57 @@ u32 TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now)
 	{
 	  t = pool_elt_at_index (tw->timers, next_index);
 	  next_index = t->next;
-	  vec_add1 (tw->expired_timer_handles, t->user_handle);
+	  vec_add1 (callback_vector, t->user_handle);
 	  pool_put (tw->timers, t);
 	}
 
       /* If any timers expired, tell the user */
-      nexpirations = vec_len (tw->expired_timer_handles);
-      if (nexpirations)
+      if (callback_vector_arg == 0 && vec_len (callback_vector))
 	{
-	  tw->expired_timer_callback (tw->expired_timer_handles);
-	  total_nexpirations += nexpirations;
+	  /* The callback is optional. We return the u32 * handle vector */
+	  if (tw->expired_timer_callback)
+	    {
+	      tw->expired_timer_callback (callback_vector);
+	      _vec_len (callback_vector) = 0;
+	    }
+	  tw->expired_timer_handles = callback_vector;
 	}
-      tw->current_index[TW_TIMER_RING_FAST]++;
       tw->current_tick++;
+      fast_wheel_index++;
+      tw->current_index[TW_TIMER_RING_FAST] = fast_wheel_index;
+
+#if TW_TIMER_WHEELS > 1
+      if (PREDICT_FALSE (fast_wheel_index == TW_SLOTS_PER_RING))
+	slow_wheel_index++;
+      tw->current_index[TW_TIMER_RING_SLOW] = slow_wheel_index;
+#endif
+
+#if TW_TIMER_WHEELS > 2
+      if (PREDICT_FALSE (slow_wheel_index == TW_SLOTS_PER_RING))
+	glacier_wheel_index++;
+      tw->current_index[TW_TIMER_RING_GLACIER] = glacier_wheel_index;
+#endif
 
-      if (total_nexpirations >= tw->max_expirations)
+      if (vec_len (callback_vector) >= tw->max_expirations)
 	break;
     }
 
+  if (callback_vector_arg == 0)
+    tw->expired_timer_handles = callback_vector;
+
   tw->last_run_time += i * tw->timer_interval;
-  return total_nexpirations;
+  return callback_vector;
+}
+
+u32 *TW (tw_timer_expire_timers) (TWT (tw_timer_wheel) * tw, f64 now)
+{
+  return TW (tw_timer_expire_timers_internal) (tw, now, 0 /* no vector */ );
+}
+
+u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now,
+				      u32 * vec)
+{
+  return TW (tw_timer_expire_timers_internal) (tw, now, vec);
 }
 
 /*