Improve fifo allocator performance

- add option to preallocate fifos in a segment
- track active fifos with doubly linked list instead of vector
- update udp redirect test code to read fifo pointers from API call
  instead of digging them up from fifo segment header
- input-node based active-open session generator

Change-Id: I804b81e99d95f8690d17e12660c6645995e28a9a
Signed-off-by: Dave Barach <dave@barachs.net>
Signed-off-by: Florin Coras <fcoras@cisco.com>
Signed-off-by: Dave Barach <dbarach@cisco.com>

4 files changed, 168 insertions, 36 deletions

diff --git a/src/svm/svm_fifo.h b/src/svm/svm_fifo.h
index 693691639ba..9cb93ff414d 100644
--- a/src/svm/svm_fifo.h
+++ b/src/svm/svm_fifo.h
@@ -38,7 +38,7 @@ format_function_t format_ooo_list;
 
 #define OOO_SEGMENT_INVALID_INDEX ((u32)~0)
 
-typedef struct
+typedef struct _svm_fifo
 {
   volatile u32 cursize;		/**< current fifo size */
   u32 nitems;
@@ -62,7 +62,8 @@ typedef struct
   ooo_segment_t *ooo_segments;	/**< Pool of ooo segments */
   u32 ooos_list_head;		/**< Head of out-of-order linked-list */
   u32 ooos_newest;		/**< Last segment to have been updated */
-
+  struct _svm_fifo *next;	/**< next in freelist/active chain */
+  struct _svm_fifo *prev;	/**< prev in active chain */
     CLIB_CACHE_LINE_ALIGN_MARK (data);
 } svm_fifo_t;
 
diff --git a/src/svm/svm_fifo_segment.c b/src/svm/svm_fifo_segment.c
index 281fae27997..eef2168c477 100644
--- a/src/svm/svm_fifo_segment.c
+++ b/src/svm/svm_fifo_segment.c
@@ -17,6 +17,71 @@
 
 svm_fifo_segment_main_t svm_fifo_segment_main;
 
+static void
+preallocate_fifo_pairs (svm_fifo_segment_header_t * fsh,
+			svm_fifo_segment_create_args_t * a)
+{
+  u32 rx_fifo_size, tx_fifo_size;
+  svm_fifo_t *f;
+  u8 *rx_fifo_space, *tx_fifo_space;
+  int i;
+
+  /* Parameter check */
+  if (a->rx_fifo_size == 0 || a->tx_fifo_size == 0
+      || a->preallocated_fifo_pairs == 0)
+    return;
+
+  /* Calculate space requirements */
+  rx_fifo_size = (sizeof (*f) + a->rx_fifo_size) * a->preallocated_fifo_pairs;
+  tx_fifo_size = (sizeof (*f) + a->tx_fifo_size) * a->preallocated_fifo_pairs;
+
+  /* Allocate rx fifo space. May fail. */
+  rx_fifo_space = clib_mem_alloc_aligned_at_offset
+    (rx_fifo_size, CLIB_CACHE_LINE_BYTES, 0 /* align_offset */ ,
+     0 /* os_out_of_memory */ );
+
+  /* Same for TX */
+  tx_fifo_space = clib_mem_alloc_aligned_at_offset
+    (tx_fifo_size, CLIB_CACHE_LINE_BYTES, 0 /* align_offset */ ,
+     0 /* os_out_of_memory */ );
+
+  /* Make sure it worked. Clean up if it didn't... */
+  if (rx_fifo_space == 0 || tx_fifo_space == 0)
+    {
+      if (rx_fifo_space)
+	clib_mem_free (rx_fifo_space);
+      else
+	clib_warning ("rx fifo preallocation failure: size %d npairs %d",
+		      a->rx_fifo_size, a->preallocated_fifo_pairs);
+
+      if (tx_fifo_space)
+	clib_mem_free (tx_fifo_space);
+      else
+	clib_warning ("tx fifo preallocation failure: size %d nfifos %d",
+		      a->tx_fifo_size, a->preallocated_fifo_pairs);
+      return;
+    }
+
+  /* Carve rx fifo space */
+  f = (svm_fifo_t *) rx_fifo_space;
+  for (i = 0; i < a->preallocated_fifo_pairs; i++)
+    {
+      f->next = fsh->free_fifos[FIFO_SEGMENT_RX_FREELIST];
+      fsh->free_fifos[FIFO_SEGMENT_RX_FREELIST] = f;
+      rx_fifo_space += sizeof (*f) + a->rx_fifo_size;
+      f = (svm_fifo_t *) rx_fifo_space;
+    }
+  /* Carve tx fifo space */
+  f = (svm_fifo_t *) tx_fifo_space;
+  for (i = 0; i < a->preallocated_fifo_pairs; i++)
+    {
+      f->next = fsh->free_fifos[FIFO_SEGMENT_TX_FREELIST];
+      fsh->free_fifos[FIFO_SEGMENT_TX_FREELIST] = f;
+      tx_fifo_space += sizeof (*f) + a->tx_fifo_size;
+      f = (svm_fifo_t *) tx_fifo_space;
+    }
+}
+
 /** (master) create an svm fifo segment */
 int
 svm_fifo_segment_create (svm_fifo_segment_create_args_t * a)
@@ -59,9 +124,7 @@ svm_fifo_segment_create (svm_fifo_segment_create_args_t * a)
   s->h = fsh;
   fsh->segment_name = format (0, "%s%c", a->segment_name, 0);
 
-  /* Avoid vec_add1(...) failure when adding a fifo, etc. */
-  vec_validate (fsh->fifos, 64);
-  _vec_len (fsh->fifos) = 0;
+  preallocate_fifo_pairs (fsh, a);
 
   ssvm_pop_heap (oldheap);
 
@@ -103,6 +166,8 @@ svm_fifo_segment_create_process_private (svm_fifo_segment_create_args_t * a)
   s->h = fsh;
   fsh->segment_name = format (0, "%s%c", a->segment_name, 0);
 
+  preallocate_fifo_pairs (fsh, a);
+
   sh->ready = 1;
   a->new_segment_index = s - sm->segments;
   return (0);
@@ -154,7 +219,8 @@ svm_fifo_segment_delete (svm_fifo_segment_private_t * s)
 
 svm_fifo_t *
 svm_fifo_segment_alloc_fifo (svm_fifo_segment_private_t * s,
-			     u32 data_size_in_bytes)
+			     u32 data_size_in_bytes,
+			     svm_fifo_segment_freelist_t list_index)
 {
   ssvm_shared_header_t *sh;
   svm_fifo_segment_header_t *fsh;
@@ -167,6 +233,29 @@ svm_fifo_segment_alloc_fifo (svm_fifo_segment_private_t * s,
   ssvm_lock (sh, 1, 0);
   oldheap = ssvm_push_heap (sh);
 
+  switch (list_index)
+    {
+    case FIFO_SEGMENT_RX_FREELIST:
+    case FIFO_SEGMENT_TX_FREELIST:
+      f = fsh->free_fifos[list_index];
+      if (f)
+	{
+	  fsh->free_fifos[list_index] = f->next;
+	  /* (re)initialize the fifo, as in svm_fifo_create */
+	  memset (f, 0, sizeof (*f));
+	  f->nitems = data_size_in_bytes;
+	  f->ooos_list_head = OOO_SEGMENT_INVALID_INDEX;
+	  goto found;
+	}
+      /* FALLTHROUGH */
+    case FIFO_SEGMENT_FREELIST_NONE:
+      break;
+
+    default:
+      clib_warning ("ignore bogus freelist %d", list_index);
+      break;
+    }
+
   /* Note: this can fail, in which case: create another segment */
   f = svm_fifo_create (data_size_in_bytes);
   if (PREDICT_FALSE (f == 0))
@@ -176,37 +265,62 @@ svm_fifo_segment_alloc_fifo (svm_fifo_segment_private_t * s,
       return (0);
     }
 
-  vec_add1 (fsh->fifos, f);
+found:
+  /* If rx_freelist add to active fifos list. When cleaning up segment,
+   * we need a list of active sessions that should be disconnected. Since
+   * both rx and tx fifos keep pointers to the session, it's enough to track
+   * only one. */
+  if (list_index == FIFO_SEGMENT_RX_FREELIST)
+    {
+      if (fsh->fifos)
+	{
+	  fsh->fifos->prev = f;
+	  f->next = fsh->fifos;
+	}
+      fsh->fifos = f;
+    }
+
   ssvm_pop_heap (oldheap);
   ssvm_unlock (sh);
   return (f);
 }
 
 void
-svm_fifo_segment_free_fifo (svm_fifo_segment_private_t * s, svm_fifo_t * f)
+svm_fifo_segment_free_fifo (svm_fifo_segment_private_t * s, svm_fifo_t * f,
+			    svm_fifo_segment_freelist_t list_index)
 {
   ssvm_shared_header_t *sh;
   svm_fifo_segment_header_t *fsh;
   void *oldheap;
-  int i;
 
   sh = s->ssvm.sh;
   fsh = (svm_fifo_segment_header_t *) sh->opaque[0];
 
   ssvm_lock (sh, 1, 0);
   oldheap = ssvm_push_heap (sh);
-  for (i = 0; i < vec_len (fsh->fifos); i++)
+
+  switch (list_index)
     {
-      if (fsh->fifos[i] == f)
-	{
-	  vec_delete (fsh->fifos, 1, i);
-	  goto found;
-	}
+    case FIFO_SEGMENT_RX_FREELIST:
+      /* Remove from active list */
+      if (f->prev)
+	f->prev->next = f->next;
+      if (f->next)
+	f->next->prev = f->prev;
+      /* FALLTHROUGH */
+    case FIFO_SEGMENT_TX_FREELIST:
+      /* Add to free list */
+      f->next = fsh->free_fifos[list_index];
+      fsh->free_fifos[list_index] = f;
+      /* FALLTHROUGH */
+    case FIFO_SEGMENT_FREELIST_NONE:
+      break;
+
+    default:
+      clib_warning ("ignore bogus freelist %d", list_index);
+      break;
     }
-  clib_warning ("fifo 0x%llx not found in fifo table...", f);
 
-found:
-  clib_mem_free (f);
   ssvm_pop_heap (oldheap);
   ssvm_unlock (sh);
 }
diff --git a/src/svm/svm_fifo_segment.h b/src/svm/svm_fifo_segment.h
index 4218013a9e4..31e14db50f6 100644
--- a/src/svm/svm_fifo_segment.h
+++ b/src/svm/svm_fifo_segment.h
@@ -19,10 +19,19 @@
 #include <svm/ssvm.h>
 #include <vppinfra/lock.h>
 
+typedef enum
+{
+  FIFO_SEGMENT_FREELIST_NONE = -1,
+  FIFO_SEGMENT_RX_FREELIST = 0,
+  FIFO_SEGMENT_TX_FREELIST,
+  FIFO_SEGMENT_N_FREELISTS
+} svm_fifo_segment_freelist_t;
+
 typedef struct
 {
-  volatile svm_fifo_t **fifos;
-  u8 *segment_name;
+  svm_fifo_t *fifos;		/**< Linked list of active RX fifos */
+  u8 *segment_name;		/**< Segment name */
+  svm_fifo_t *free_fifos[FIFO_SEGMENT_N_FREELISTS];	/**< Free lists */
 } svm_fifo_segment_header_t;
 
 typedef struct
@@ -49,6 +58,9 @@ typedef struct
   char *segment_name;
   u32 segment_size;
   u32 new_segment_index;
+  u32 rx_fifo_size;
+  u32 tx_fifo_size;
+  u32 preallocated_fifo_pairs;
 } svm_fifo_segment_create_args_t;
 
 static inline svm_fifo_segment_private_t *
@@ -61,13 +73,13 @@ svm_fifo_get_segment (u32 segment_index)
 static inline u8
 svm_fifo_segment_has_fifos (svm_fifo_segment_private_t * fifo_segment)
 {
-  return vec_len ((svm_fifo_t **) fifo_segment->h->fifos) != 0;
+  return fifo_segment->h->fifos != 0;
 }
 
-static inline svm_fifo_t **
-svm_fifo_segment_get_fifos (svm_fifo_segment_private_t * fifo_segment)
+static inline svm_fifo_t *
+svm_fifo_segment_get_fifo_list (svm_fifo_segment_private_t * fifo_segment)
 {
-  return (svm_fifo_t **) fifo_segment->h->fifos;
+  return fifo_segment->h->fifos;
 }
 
 #define foreach_ssvm_fifo_segment_api_error             \
@@ -87,9 +99,11 @@ int svm_fifo_segment_attach (svm_fifo_segment_create_args_t * a);
 void svm_fifo_segment_delete (svm_fifo_segment_private_t * s);
 
 svm_fifo_t *svm_fifo_segment_alloc_fifo (svm_fifo_segment_private_t * s,
-					 u32 data_size_in_bytes);
+					 u32 data_size_in_bytes,
+					 svm_fifo_segment_freelist_t index);
 void svm_fifo_segment_free_fifo (svm_fifo_segment_private_t * s,
-				 svm_fifo_t * f);
+				 svm_fifo_t * f,
+				 svm_fifo_segment_freelist_t index);
 void svm_fifo_segment_init (u64 baseva, u32 timeout_in_seconds);
 u32 svm_fifo_segment_index (svm_fifo_segment_private_t * s);
 
diff --git a/src/svm/test_svm_fifo1.c b/src/svm/test_svm_fifo1.c
index 398dd6d7c38..63b4a9b7ba5 100644
--- a/src/svm/test_svm_fifo1.c
+++ b/src/svm/test_svm_fifo1.c
@@ -30,6 +30,9 @@ hello_world (int verbose)
 
   a->segment_name = "fifo-test1";
   a->segment_size = 256 << 10;
+  a->rx_fifo_size = 4096;
+  a->tx_fifo_size = 4096;
+  a->preallocated_fifo_pairs = 4;
 
   rv = svm_fifo_segment_create (a);
 
@@ -38,7 +41,7 @@ hello_world (int verbose)
 
   sp = svm_fifo_get_segment (a->new_segment_index);
 
-  f = svm_fifo_segment_alloc_fifo (sp, 4096);
+  f = svm_fifo_segment_alloc_fifo (sp, 4096, FIFO_SEGMENT_RX_FREELIST);
 
   if (f == 0)
     return clib_error_return (0, "svm_fifo_segment_alloc_fifo failed");
@@ -63,7 +66,7 @@ hello_world (int verbose)
   else
     error = clib_error_return (0, "data test FAIL!");
 
-  svm_fifo_segment_free_fifo (sp, f);
+  svm_fifo_segment_free_fifo (sp, f, FIFO_SEGMENT_RX_FREELIST);
 
   return error;
 }
@@ -91,7 +94,7 @@ master (int verbose)
 
   sp = svm_fifo_get_segment (a->new_segment_index);
 
-  f = svm_fifo_segment_alloc_fifo (sp, 4096);
+  f = svm_fifo_segment_alloc_fifo (sp, 4096, FIFO_SEGMENT_RX_FREELIST);
 
   if (f == 0)
     return clib_error_return (0, "svm_fifo_segment_alloc_fifo failed");
@@ -129,7 +132,7 @@ mempig (int verbose)
 
   for (i = 0; i < 1000; i++)
     {
-      f = svm_fifo_segment_alloc_fifo (sp, 4096);
+      f = svm_fifo_segment_alloc_fifo (sp, 4096, FIFO_SEGMENT_RX_FREELIST);
       if (f == 0)
 	break;
       vec_add1 (flist, f);
@@ -139,14 +142,14 @@ mempig (int verbose)
   for (i = 0; i < vec_len (flist); i++)
     {
       f = flist[i];
-      svm_fifo_segment_free_fifo (sp, f);
+      svm_fifo_segment_free_fifo (sp, f, FIFO_SEGMENT_RX_FREELIST);
     }
 
   _vec_len (flist) = 0;
 
   for (i = 0; i < 1000; i++)
     {
-      f = svm_fifo_segment_alloc_fifo (sp, 4096);
+      f = svm_fifo_segment_alloc_fifo (sp, 4096, FIFO_SEGMENT_RX_FREELIST);
       if (f == 0)
 	break;
       vec_add1 (flist, f);
@@ -156,7 +159,7 @@ mempig (int verbose)
   for (i = 0; i < vec_len (flist); i++)
     {
       f = flist[i];
-      svm_fifo_segment_free_fifo (sp, f);
+      svm_fifo_segment_free_fifo (sp, f, FIFO_SEGMENT_RX_FREELIST);
     }
 
   return 0;
@@ -185,7 +188,7 @@ offset (int verbose)
 
   sp = svm_fifo_get_segment (a->new_segment_index);
 
-  f = svm_fifo_segment_alloc_fifo (sp, 200 << 10);
+  f = svm_fifo_segment_alloc_fifo (sp, 200 << 10, FIFO_SEGMENT_RX_FREELIST);
 
   if (f == 0)
     return clib_error_return (0, "svm_fifo_segment_alloc_fifo failed");
@@ -226,9 +229,9 @@ slave (int verbose)
 {
   svm_fifo_segment_create_args_t _a, *a = &_a;
   svm_fifo_segment_private_t *sp;
-  svm_fifo_segment_header_t *fsh;
   svm_fifo_t *f;
   ssvm_shared_header_t *sh;
+  svm_fifo_segment_header_t *fsh;
   int rv;
   u8 *test_data;
   u8 *retrieved_data = 0;
@@ -248,7 +251,7 @@ slave (int verbose)
   fsh = (svm_fifo_segment_header_t *) sh->opaque[0];
 
   /* might wanna wait.. */
-  f = (svm_fifo_t *) fsh->fifos[0];
+  f = fsh->fifos;
 
   /* Lazy bastards united */
   test_data = format (0, "Hello world%c", 0);