Add fixed-size, preallocated pool support

Simply call pool_init_fixed(...) before using the pool. Note that
fixed, preallocated pools live in individually-mmap'ed address
segments, except for the free element bitmap. A large fixed pool can
exceed 4gb.

Fix tcp buffer allocator leak, remove broken assert

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

12 files changed, 431 insertions, 38 deletions

diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h
index d0be028cba9..173168fe98e 100644
--- a/src/vppinfra/bihash_24_8.h
+++ b/src/vppinfra/bihash_24_8.h
@@ -18,7 +18,7 @@
 
 #define BIHASH_TYPE _24_8
 #define BIHASH_KVP_PER_PAGE 4
-#define BIHASH_KVP_CACHE_SIZE 3
+#define BIHASH_KVP_CACHE_SIZE 0
 
 #ifndef __included_bihash_24_8_h__
 #define __included_bihash_24_8_h__
diff --git a/src/vppinfra/pool.c b/src/vppinfra/pool.c
new file mode 100644
index 00000000000..ed83b41afef
--- /dev/null
+++ b/src/vppinfra/pool.c
@@ -0,0 +1,131 @@
+/*
+ * Copyright (c) 2017 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.
+ */
+/*
+  Copyright (c) 2001, 2002, 2003, 2004 Eliot Dresselhaus
+
+  Permission is hereby granted, free of charge, to any person obtaining
+  a copy of this software and associated documentation files (the
+  "Software"), to deal in the Software without restriction, including
+  without limitation the rights to use, copy, modify, merge, publish,
+  distribute, sublicense, and/or sell copies of the Software, and to
+  permit persons to whom the Software is furnished to do so, subject to
+  the following conditions:
+
+  The above copyright notice and this permission notice shall be
+  included in all copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+
+#include <vppinfra/pool.h>
+
+void
+_pool_init_fixed (void **pool_ptr, u32 elt_size, u32 max_elts)
+{
+  u8 *mmap_base;
+  u64 vector_size;
+  u64 free_index_size;
+  u64 total_size;
+  u64 page_size;
+  pool_header_t *fh;
+  vec_header_t *vh;
+  u8 *v;
+  u32 *fi;
+  u32 i;
+  u32 set_bits;
+
+  ASSERT (elt_size);
+  ASSERT (max_elts);
+
+  vector_size = pool_aligned_header_bytes + vec_header_bytes (0)
+    + (u64) elt_size *max_elts;
+
+  free_index_size = vec_header_bytes (0) + sizeof (u32) * max_elts;
+
+  /* Round up to a cache line boundary */
+  vector_size = (vector_size + CLIB_CACHE_LINE_BYTES - 1)
+    & ~(CLIB_CACHE_LINE_BYTES - 1);
+
+  free_index_size = (free_index_size + CLIB_CACHE_LINE_BYTES - 1)
+    & ~(CLIB_CACHE_LINE_BYTES - 1);
+
+  total_size = vector_size + free_index_size;
+
+  /* Round up to an even number of pages */
+  page_size = clib_mem_get_page_size ();
+  total_size = (total_size + page_size - 1) & ~(page_size - 1);
+
+  /* mmap demand zero memory */
+
+  mmap_base = mmap (0, total_size, PROT_READ | PROT_WRITE,
+		    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
+
+  if (mmap_base == MAP_FAILED)
+    {
+      clib_unix_warning ("mmap");
+      *pool_ptr = 0;
+    }
+
+  /* First comes the pool header */
+  fh = (pool_header_t *) mmap_base;
+  /* Find the user vector pointer */
+  v = (u8 *) (mmap_base + pool_aligned_header_bytes);
+  /* Finally, the vector header */
+  vh = _vec_find (v);
+
+  fh->free_bitmap = 0;		/* No free elts (yet) */
+  fh->max_elts = max_elts;
+  fh->mmap_base = mmap_base;
+  fh->mmap_size = total_size;
+
+  vh->len = max_elts;
+
+  /* Build the free-index vector */
+  vh = (vec_header_t *) (v + vector_size);
+  vh->len = max_elts;
+  fi = (u32 *) (vh + 1);
+
+  fh->free_indices = fi;
+
+  /* Set the entire free bitmap */
+  clib_bitmap_alloc (fh->free_bitmap, max_elts);
+  memset (fh->free_bitmap, 0xff, vec_len (fh->free_bitmap) * sizeof (uword));
+
+  /* Clear any extraneous set bits */
+  set_bits = vec_len (fh->free_bitmap) * BITS (uword);
+
+  for (i = max_elts; i < set_bits; i++)
+    fh->free_bitmap = clib_bitmap_set (fh->free_bitmap, i, 0);
+
+  /* Create the initial free vector */
+  for (i = 0; i < max_elts; i++)
+    fi[i] = (max_elts - 1) - i;
+
+  *pool_ptr = v;
+}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vppinfra/pool.h b/src/vppinfra/pool.h
index 56536b77963..62d5b54ec07 100644
--- a/src/vppinfra/pool.h
+++ b/src/vppinfra/pool.h
@@ -56,6 +56,16 @@ typedef struct
 
   /** Vector of free indices.  One element for each set bit in bitmap. */
   u32 *free_indices;
+
+  /* The following fields are set for fixed-size, preallocated pools */
+
+  /** Maximum size of the pool, in elements */
+  u32 max_elts;
+
+  /** mmap segment info: base + length */
+  u8 *mmap_base;
+  u64 mmap_size;
+
 } pool_header_t;
 
 /** Align pool header so that pointers are naturally aligned. */
@@ -69,6 +79,15 @@ pool_header (void *v)
   return vec_aligned_header (v, sizeof (pool_header_t), sizeof (void *));
 }
 
+extern void _pool_init_fixed (void **, u32, u32);
+extern void fpool_free (void *);
+
+/** initialize a fixed-size, preallocated pool */
+#define pool_init_fixed(pool,max_elts)                  \
+{                                                       \
+  _pool_init_fixed((void **)&(pool),sizeof(pool[0]),max_elts);  \
+}
+
 /** Validate a pool */
 always_inline void
 pool_validate (void *v)
@@ -98,7 +117,7 @@ pool_header_validate_index (void *v, uword index)
 do {								\
   uword __pool_validate_index = (i);				\
   vec_validate_ha ((v), __pool_validate_index,			\
-		   pool_aligned_header_bytes, /* align */ 0);		\
+		   pool_aligned_header_bytes, /* align */ 0);   \
   pool_header_validate_index ((v), __pool_validate_index);	\
 } while (0)
 
@@ -166,34 +185,40 @@ pool_free_elts (void *v)
 
    First search free list.  If nothing is free extend vector of objects.
 */
-#define pool_get_aligned(P,E,A)						\
-do {									\
-  pool_header_t * _pool_var (p) = pool_header (P);			\
-  uword _pool_var (l);							\
-									\
-  _pool_var (l) = 0;							\
-  if (P)								\
-    _pool_var (l) = vec_len (_pool_var (p)->free_indices);		\
-									\
-  if (_pool_var (l) > 0)						\
-    {									\
-      /* Return free element from free list. */				\
+#define pool_get_aligned(P,E,A)                                         \
+do {                                                                    \
+  pool_header_t * _pool_var (p) = pool_header (P);                      \
+  uword _pool_var (l);                                                  \
+                                                                        \
+  _pool_var (l) = 0;                                                    \
+  if (P)                                                                \
+    _pool_var (l) = vec_len (_pool_var (p)->free_indices);              \
+                                                                        \
+  if (_pool_var (l) > 0)                                                \
+    {                                                                   \
+      /* Return free element from free list. */                         \
       uword _pool_var (i) = _pool_var (p)->free_indices[_pool_var (l) - 1]; \
-      (E) = (P) + _pool_var (i);					\
-      _pool_var (p)->free_bitmap =					\
+      (E) = (P) + _pool_var (i);                                        \
+      _pool_var (p)->free_bitmap =                                      \
 	clib_bitmap_andnoti (_pool_var (p)->free_bitmap, _pool_var (i)); \
-      _vec_len (_pool_var (p)->free_indices) = _pool_var (l) - 1;	\
-    }									\
-  else									\
-    {									\
-      /* Nothing on free list, make a new element and return it. */	\
-      P = _vec_resize (P,						\
-		       /* length_increment */ 1,			\
+      _vec_len (_pool_var (p)->free_indices) = _pool_var (l) - 1;       \
+    }                                                                   \
+  else                                                                  \
+    {                                                                   \
+      /* fixed-size, preallocated pools cannot expand */                \
+      if ((P) && _pool_var(p)->max_elts)                                \
+        {                                                               \
+          clib_warning ("can't expand fixed-size pool");                \
+          os_out_of_memory();                                           \
+        }                                                               \
+      /* Nothing on free list, make a new element and return it. */     \
+      P = _vec_resize (P,                                               \
+		       /* length_increment */ 1,                        \
 		       /* new size */ (vec_len (P) + 1) * sizeof (P[0]), \
-		       pool_aligned_header_bytes,				\
-		       /* align */ (A));				\
-      E = vec_end (P) - 1;						\
-    }									\
+		       pool_aligned_header_bytes,                       \
+		       /* align */ (A));                                \
+      E = vec_end (P) - 1;                                              \
+    }                                                                   \
 } while (0)
 
 /** Allocate an object E from a pool P (unspecified alignment). */
@@ -207,7 +232,11 @@ do {                                                                    \
                                                                         \
   _pool_var (l) = 0;                                                    \
   if (P)                                                                \
+    {                                                                   \
+    if (_pool_var (p)->max_elts)                                        \
+      return 0;                                                         \
     _pool_var (l) = vec_len (_pool_var (p)->free_indices);              \
+    }                                                                   \
                                                                         \
   /* Free elements, certainly won't expand */                           \
   if (_pool_var (l) > 0)                                                \
@@ -248,7 +277,16 @@ do {									\
   /* Add element to free bitmap and to free list. */			\
   _pool_var (p)->free_bitmap =						\
     clib_bitmap_ori (_pool_var (p)->free_bitmap, _pool_var (l));	\
-  vec_add1 (_pool_var (p)->free_indices, _pool_var (l));		\
+  /* Preallocated pool? */                                              \
+  if (_pool_var (p)->max_elts)                                          \
+    {                                                                   \
+      ASSERT(_pool_var(l) < _pool_var (p)->max_elts);                   \
+      _pool_var(p)->free_indices[_vec_len(_pool_var(p)->free_indices)] = \
+                                 _pool_var(l);                          \
+      _vec_len(_pool_var(p)->free_indices) += 1;                        \
+    }                                                                   \
+  else                                                                  \
+    vec_add1 (_pool_var (p)->free_indices, _pool_var (l));		\
 } while (0)
 
 /** Free pool element with given index. */
@@ -262,6 +300,17 @@ do {						\
 #define pool_alloc_aligned(P,N,A)					\
 do {									\
   pool_header_t * _p;							\
+                                                                        \
+  if ((P))                                                              \
+    {                                                                   \
+      _p = pool_header (P);                                             \
+      if (_p->max_elts)                                                 \
+        {                                                               \
+           clib_warning ("Can't expand fixed-size pool");		\
+           os_out_of_memory();                                          \
+        }                                                               \
+    }                                                                   \
+                                                                        \
   (P) = _vec_resize ((P), 0, (vec_len (P) + (N)) * sizeof (P[0]),	\
 		     pool_aligned_header_bytes,				\
 		     (A));						\
@@ -281,8 +330,20 @@ _pool_free (void *v)
   if (!v)
     return v;
   clib_bitmap_free (p->free_bitmap);
-  vec_free (p->free_indices);
-  vec_free_h (v, pool_aligned_header_bytes);
+
+  if (p->max_elts)
+    {
+      int rv;
+
+      rv = munmap (p->mmap_base, p->mmap_size);
+      if (rv)
+	clib_unix_warning ("munmap");
+    }
+  else
+    {
+      vec_free (p->free_indices);
+      vec_free_h (v, pool_aligned_header_bytes);
+    }
   return 0;
 }
 
diff --git a/src/vppinfra/test_fpool.c b/src/vppinfra/test_fpool.c
new file mode 100644
index 00000000000..e2d67f16907
--- /dev/null
+++ b/src/vppinfra/test_fpool.c
@@ -0,0 +1,69 @@
+/*
+ * Copyright (c) 2017 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.
+*/
+
+#include <vppinfra/pool.h>
+
+/* can be a very large size */
+#define NELTS 1024
+
+int
+main (int argc, char *argv[])
+{
+  u32 *junk = 0;
+  int i;
+  u32 *tp = 0;
+  u32 *indices = 0;
+
+  clib_mem_init (0, 3ULL << 30);
+
+  vec_validate (indices, NELTS - 1);
+  _vec_len (indices) = 0;
+
+  pool_init_fixed (tp, NELTS);
+
+  for (i = 0; i < NELTS; i++)
+    {
+      pool_get (tp, junk);
+      vec_add1 (indices, junk - tp);
+      *junk = i;
+    }
+
+  for (i = 0; i < NELTS; i++)
+    {
+      junk = pool_elt_at_index (tp, indices[i]);
+      ASSERT (*junk == i);
+    }
+
+  fformat (stdout, "%d pool elts before deletes\n", pool_elts (tp));
+
+  pool_put_index (tp, indices[12]);
+  pool_put_index (tp, indices[43]);
+
+  fformat (stdout, "%d pool elts after deletes\n", pool_elts (tp));
+
+  pool_validate (tp);
+
+  pool_free (tp);
+  return 0;
+}
+
+/*
+ * fd.io coding-style-patch-verification: ON
+ *
+ * Local Variables:
+ * eval: (c-set-style "gnu")
+ * End:
+ */
diff --git a/src/vppinfra/tw_timer_16t_1w_2048sl.h b/src/vppinfra/tw_timer_16t_1w_2048sl.h
index 66cf7d37b68..761646b3838 100644
--- a/src/vppinfra/tw_timer_16t_1w_2048sl.h
+++ b/src/vppinfra/tw_timer_16t_1w_2048sl.h
@@ -27,6 +27,7 @@
 #undef TW_OVERFLOW_VECTOR
 #undef TW_FAST_WHEEL_BITMAP
 #undef TW_TIMER_ALLOW_DUPLICATE_STOP
+#undef TW_START_STOP_TRACE_SIZE
 
 #define TW_TIMER_WHEELS 1
 #define TW_SLOTS_PER_RING 2048
diff --git a/src/vppinfra/tw_timer_16t_2w_512sl.h b/src/vppinfra/tw_timer_16t_2w_512sl.h
index 00587b8eeda..029f529d2e3 100644
--- a/src/vppinfra/tw_timer_16t_2w_512sl.h
+++ b/src/vppinfra/tw_timer_16t_2w_512sl.h
@@ -27,6 +27,7 @@
 #undef TW_OVERFLOW_VECTOR
 #undef TW_FAST_WHEEL_BITMAP
 #undef TW_TIMER_ALLOW_DUPLICATE_STOP
+#undef TW_START_STOP_TRACE_SIZE
 
 #define TW_TIMER_WHEELS 2
 #define TW_SLOTS_PER_RING 512
@@ -36,7 +37,7 @@
 #define LOG2_TW_TIMERS_PER_OBJECT 4
 #define TW_SUFFIX _16t_2w_512sl
 #define TW_FAST_WHEEL_BITMAP 0
-#define TW_TIMER_ALLOW_DUPLICATE_STOP 0
+#define TW_TIMER_ALLOW_DUPLICATE_STOP 1
 
 #include <vppinfra/tw_timer_template.h>
 
diff --git a/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h b/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h
index e5e4cc19a90..0b455e029e7 100644
--- a/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h
+++ b/src/vppinfra/tw_timer_1t_3w_1024sl_ov.h
@@ -27,6 +27,7 @@
 #undef TW_OVERFLOW_VECTOR
 #undef TW_FAST_WHEEL_BITMAP
 #undef TW_TIMER_ALLOW_DUPLICATE_STOP
+#undef TW_START_STOP_TRACE_SIZE
 
 #define TW_TIMER_WHEELS 3
 #define TW_SLOTS_PER_RING 1024
diff --git a/src/vppinfra/tw_timer_2t_1w_2048sl.h b/src/vppinfra/tw_timer_2t_1w_2048sl.h
index 98b548b39d4..6ae86688b9b 100644
--- a/src/vppinfra/tw_timer_2t_1w_2048sl.h
+++ b/src/vppinfra/tw_timer_2t_1w_2048sl.h
@@ -27,6 +27,7 @@
 #undef TW_OVERFLOW_VECTOR
 #undef TW_FAST_WHEEL_BITMAP
 #undef TW_TIMER_ALLOW_DUPLICATE_STOP
+#undef TW_START_STOP_TRACE_SIZE
 
 #define TW_TIMER_WHEELS 1
 #define TW_SLOTS_PER_RING 2048
diff --git a/src/vppinfra/tw_timer_4t_3w_256sl.h b/src/vppinfra/tw_timer_4t_3w_256sl.h
index 07203de8742..16c41bcd5a5 100644
--- a/src/vppinfra/tw_timer_4t_3w_256sl.h
+++ b/src/vppinfra/tw_timer_4t_3w_256sl.h
@@ -27,6 +27,7 @@
 #undef TW_OVERFLOW_VECTOR
 #undef TW_FAST_WHEEL_BITMAP
 #undef TW_TIMER_ALLOW_DUPLICATE_STOP
+#undef TW_START_STOP_TRACE_SIZE
 
 #define TW_TIMER_WHEELS 3
 #define TW_SLOTS_PER_RING 256
diff --git a/src/vppinfra/tw_timer_4t_3w_4sl_ov.h b/src/vppinfra/tw_timer_4t_3w_4sl_ov.h
index 20a01d05e7d..845ffeacb5f 100644
--- a/src/vppinfra/tw_timer_4t_3w_4sl_ov.h
+++ b/src/vppinfra/tw_timer_4t_3w_4sl_ov.h
@@ -27,6 +27,7 @@
 #undef TW_OVERFLOW_VECTOR
 #undef TW_FAST_WHEEL_BITMAP
 #undef TW_TIMER_ALLOW_DUPLICATE_STOP
+#undef TW_START_STOP_TRACE_SIZE
 
 #define TW_TIMER_WHEELS 3
 #define TW_SLOTS_PER_RING 4
diff --git a/src/vppinfra/tw_timer_template.c b/src/vppinfra/tw_timer_template.c
index c0a9685aa82..aba00142051 100644
--- a/src/vppinfra/tw_timer_template.c
+++ b/src/vppinfra/tw_timer_template.c
@@ -18,6 +18,87 @@
  *
  *
  */
+#if TW_START_STOP_TRACE_SIZE > 0
+
+void TW (tw_timer_trace) (TWT (tw_timer_wheel) * tw, u32 timer_id,
+			  u32 pool_index, u32 handle)
+{
+  TWT (trace) * t = &tw->traces[tw->trace_index];
+
+  t->timer_id = timer_id;
+  t->pool_index = pool_index;
+  t->handle = handle;
+
+  tw->trace_index++;
+  if (tw->trace_index == TW_START_STOP_TRACE_SIZE)
+    {
+      tw->trace_index = 0;
+      tw->trace_wrapped++;
+    }
+}
+
+void TW (tw_search_trace) (TWT (tw_timer_wheel) * tw, u32 handle)
+{
+  u32 i, start_pos;
+  TWT (trace) * t;
+  char *s = "bogus!";
+
+  /* reverse search for the supplied handle */
+
+  start_pos = tw->trace_index;
+  if (start_pos == 0)
+    start_pos = TW_START_STOP_TRACE_SIZE - 1;
+  else
+    start_pos--;
+
+  for (i = start_pos; i > 0; i--)
+    {
+      t = &tw->traces[i];
+      if (t->handle == handle)
+	{
+	  switch (t->timer_id)
+	    {
+	    case 0xFF:
+	      s = "stopped";
+	      break;
+	    case 0xFE:
+	      s = "expired";
+	      break;
+	    default:
+	      s = "started";
+	      break;
+	    }
+	  fformat (stderr, "handle 0x%x (%d) %s at trace %d\n",
+		   handle, handle, s, i);
+	}
+    }
+  if (tw->trace_wrapped > 0)
+    {
+      for (i = TW_START_STOP_TRACE_SIZE; i >= tw->trace_index; i--)
+	{
+	  t = &tw->traces[i];
+	  if (t->handle == handle)
+	    {
+	      switch (t->timer_id)
+		{
+		case 0xFF:
+		  s = "stopped";
+		  break;
+		case 0xFE:
+		  s = "expired";
+		  break;
+		default:
+		  s = "started";
+		  break;
+		}
+	      fformat (stderr, "handle 0x%x (%d) %s at trace %d\n",
+		       handle, handle, s, i);
+	    }
+	}
+    }
+}
+#endif /* TW_START_STOP_TRACE_SIZE > 0 */
+
 static inline u32
 TW (make_internal_timer_handle) (u32 pool_index, u32 timer_id)
 {
@@ -127,6 +208,9 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id,
       t->expiration_time = tw->current_tick + interval;
       ts = &tw->overflow;
       timer_addhead (tw->timers, ts->head_index, t - tw->timers);
+#if TW_START_STOP_TRACE_SIZE > 0
+      TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers);
+#endif
       return t - tw->timers;
     }
 #endif
@@ -177,7 +261,9 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id,
       ts = &tw->w[TW_TIMER_RING_GLACIER][glacier_ring_offset];
 
       timer_addhead (tw->timers, ts->head_index, t - tw->timers);
-
+#if TW_START_STOP_TRACE_SIZE > 0
+      TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers);
+#endif
       return t - tw->timers;
     }
 #endif
@@ -193,7 +279,9 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id,
       ts = &tw->w[TW_TIMER_RING_SLOW][slow_ring_offset];
 
       timer_addhead (tw->timers, ts->head_index, t - tw->timers);
-
+#if TW_START_STOP_TRACE_SIZE > 0
+      TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers);
+#endif
       return t - tw->timers;
     }
 #else
@@ -209,6 +297,9 @@ TW (tw_timer_start) (TWT (tw_timer_wheel) * tw, u32 pool_index, u32 timer_id,
   tw->fast_slot_bitmap = clib_bitmap_set (tw->fast_slot_bitmap,
 					  fast_ring_offset, 1);
 #endif
+#if TW_START_STOP_TRACE_SIZE > 0
+  TW (tw_timer_trace) (tw, timer_id, pool_index, t - tw->timers);
+#endif
   return t - tw->timers;
 }
 
@@ -265,6 +356,9 @@ void TW (tw_timer_stop) (TWT (tw_timer_wheel) * tw, u32 handle)
   if (pool_is_free_index (tw->timers, handle))
     return;
 #endif
+#if TW_START_STOP_TRACE_SIZE > 0
+  TW (tw_timer_trace) (tw, ~0, ~0, handle);
+#endif
 
   t = pool_elt_at_index (tw->timers, handle);
 
@@ -302,6 +396,7 @@ 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;
 
@@ -476,6 +571,9 @@ static inline
 				 new_glacier_ring_offset == 0))
 		{
 		  vec_add1 (callback_vector, t->user_handle);
+#if TW_START_STOP_TRACE_SIZE > 0
+		  TW (tw_timer_trace) (tw, 0xfe, ~0, t - tw->timers);
+#endif
 		  pool_put (tw->timers, t);
 		}
 	      /* Timer moves to the glacier ring */
@@ -536,6 +634,9 @@ static inline
 				 t->fast_ring_offset == 0))
 		{
 		  vec_add1 (callback_vector, t->user_handle);
+#if TW_START_STOP_TRACE_SIZE > 0
+		  TW (tw_timer_trace) (tw, 0xfe, ~0, t - tw->timers);
+#endif
 		  pool_put (tw->timers, t);
 		}
 	      /* Timer expires during slow-wheel tick 0 */
@@ -587,6 +688,9 @@ static inline
 	      if (PREDICT_FALSE (t->fast_ring_offset == 0))
 		{
 		  vec_add1 (callback_vector, t->user_handle);
+#if TW_START_STOP_TRACE_SIZE > 0
+		  TW (tw_timer_trace) (tw, 0xfe, ~0, t - tw->timers);
+#endif
 		  pool_put (tw->timers, t);
 		}
 	      else		/* typical case */
@@ -620,6 +724,9 @@ static inline
 	  t = pool_elt_at_index (tw->timers, next_index);
 	  next_index = t->next;
 	  vec_add1 (callback_vector, t->user_handle);
+#if TW_START_STOP_TRACE_SIZE > 0
+	  TW (tw_timer_trace) (tw, 0xfe, ~0, t - tw->timers);
+#endif
 	  pool_put (tw->timers, t);
 	}
 
@@ -628,10 +735,7 @@ static inline
 	{
 	  /* 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_callback (callback_vector);
 	  tw->expired_timer_handles = callback_vector;
 	}
 
diff --git a/src/vppinfra/tw_timer_template.h b/src/vppinfra/tw_timer_template.h
index 0404e3f4715..0217644df6e 100644
--- a/src/vppinfra/tw_timer_template.h
+++ b/src/vppinfra/tw_timer_template.h
@@ -170,6 +170,13 @@ typedef enum
 } tw_ring_index_t;
 #endif /* __defined_tw_timer_wheel_slot__ */
 
+typedef CLIB_PACKED (struct
+		     {
+		     u8 timer_id;
+		     u32 pool_index;
+		     u32 handle;
+		     }) TWT (trace);
+
 typedef struct
 {
   /** Timer pool */
@@ -211,11 +218,20 @@ typedef struct
   /** expired timer callback, receives a vector of handles */
   void (*expired_timer_callback) (u32 * expired_timer_handles);
 
-  /** vector of expired timers */
+  /** vectors of expired timers */
   u32 *expired_timer_handles;
 
   /** maximum expirations */
   u32 max_expirations;
+
+  /** current trace index */
+#if TW_START_STOP_TRACE_SIZE > 0
+  /* Start/stop/expire tracing */
+  u32 trace_index;
+  u32 trace_wrapped;
+    TWT (trace) traces[TW_START_STOP_TRACE_SIZE];
+#endif
+
 } TWT (tw_timer_wheel);
 
 u32 TW (tw_timer_start) (TWT (tw_timer_wheel) * tw,
@@ -236,6 +252,12 @@ u32 *TW (tw_timer_expire_timers_vec) (TWT (tw_timer_wheel) * tw, f64 now,
 u32 TW (tw_timer_first_expires_in_ticks) (TWT (tw_timer_wheel) * tw);
 #endif
 
+#if TW_START_STOP_TRACE_SIZE > 0
+void TW (tw_search_trace) (TWT (tw_timer_wheel) * tw, u32 handle);
+void TW (tw_timer_trace) (TWT (tw_timer_wheel) * tw, u32 timer_id,
+			  u32 pool_index, u32 handle);
+#endif
+
 /*
  * fd.io coding-style-patch-verification: ON
  *