svm: support addition of chunks to fifos

Change-Id: Ia56cad89b85b7a99ab4bfb85318a45a71381fb53
Signed-off-by: Florin Coras <fcoras@cisco.com>

4 files changed, 221 insertions, 14 deletions

diff --git a/src/plugins/unittest/tcp_test.c b/src/plugins/unittest/tcp_test.c
index f7bcad3e67e..7a81469307d 100644
--- a/src/plugins/unittest/tcp_test.c
+++ b/src/plugins/unittest/tcp_test.c
@@ -1393,8 +1393,8 @@ tcp_test_fifo5 (vlib_main_t * vm, unformat_input_t * input)
 	verbose = 1;
       else
 	{
-	  clib_error_t *e = clib_error_return
-	    (0, "unknown input `%U'", format_unformat_error, input);
+	  clib_error_t *e = clib_error_return (0, "unknown input `%U'",
+					       format_unformat_error, input);
 	  clib_error_report (e);
 	  return -1;
 	}
@@ -1507,6 +1507,131 @@ tcp_test_fifo5 (vlib_main_t * vm, unformat_input_t * input)
   return 0;
 }
 
+static int
+tcp_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input)
+{
+  int __clib_unused verbose, fifo_size = 201, start_offset = 100, i;
+  svm_fifo_chunk_t *c, *next, *prev;
+  svm_fifo_t *f;
+  u8 *buf = 0;
+
+  while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
+    {
+      if (unformat (input, "verbose"))
+	verbose = 1;
+      else
+	{
+	  vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
+			   input);
+	  return -1;
+	}
+    }
+
+  f = fifo_prepare (fifo_size);
+  svm_fifo_init_pointers (f, start_offset);
+
+  /*
+   * Add with fifo not wrapped
+   */
+  c = clib_mem_alloc (sizeof (svm_fifo_chunk_t) + 100);
+  c->length = 100;
+  c->start_byte = ~0;
+  c->next = 0;
+
+  svm_fifo_add_chunk (f, c);
+
+  TCP_TEST (f->size == fifo_size + 100, "size expected %u is %u",
+	    fifo_size + 100, f->size);
+  TCP_TEST (c->start_byte == fifo_size, "start byte expected %u is %u",
+	    fifo_size, c->start_byte);
+
+  /*
+   *  Add with fifo wrapped
+   */
+
+  f->tail = f->head + f->nitems;
+  c = clib_mem_alloc (sizeof (svm_fifo_chunk_t) + 100);
+  c->length = 100;
+  c->start_byte = ~0;
+  c->next = 0;
+
+  svm_fifo_add_chunk (f, c);
+
+  TCP_TEST (f->end_chunk != c, "tail chunk should not be updated");
+  TCP_TEST (f->size == fifo_size + 100, "size expected %u is %u",
+	    fifo_size + 100, f->size);
+  TCP_TEST (c->start_byte == ~0, "start byte expected %u is %u", ~0,
+	    c->start_byte);
+
+  /*
+   * Unwrap fifo
+   */
+  vec_validate (buf, 200);
+  svm_fifo_dequeue_nowait (f, 201, buf);
+
+  TCP_TEST (f->end_chunk == c, "tail chunk should be updated");
+  TCP_TEST (f->size == fifo_size + 200, "size expected %u is %u",
+	    fifo_size + 200, f->size);
+  TCP_TEST (c->start_byte == fifo_size + 100, "start byte expected %u is "
+	    "%u", fifo_size + 100, c->start_byte);
+
+  /*
+   * Add N chunks
+   */
+
+  f->head = f->nitems - 100;
+  f->tail = f->head + f->nitems;
+
+  prev = 0;
+  for (i = 0; i < 5; i++)
+    {
+      c = clib_mem_alloc (sizeof (svm_fifo_chunk_t) + 100);
+      c->length = 100;
+      c->start_byte = ~0;
+      c->next = prev;
+      prev = c;
+    }
+
+  svm_fifo_add_chunk (f, c);
+  TCP_TEST (f->size == fifo_size + 200, "size expected %u is %u",
+	    fifo_size + 200, f->size);
+
+  prev = 0;
+  for (i = 0; i < 5; i++)
+    {
+      c = clib_mem_alloc (sizeof (svm_fifo_chunk_t) + 100);
+      c->length = 100;
+      c->start_byte = ~0;
+      c->next = prev;
+      prev = c;
+    }
+
+  svm_fifo_add_chunk (f, c);
+  TCP_TEST (f->size == fifo_size + 200, "size expected %u is %u",
+	    fifo_size + 200, f->size);
+
+  svm_fifo_dequeue_nowait (f, 201, buf);
+
+  TCP_TEST (f->size == fifo_size + 200 + 10 * 100, "size expected %u is %u",
+	    fifo_size + 200 + 10 * 100, f->size);
+
+  /*
+   * Cleanup
+   */
+  c = f->start_chunk->next;
+  while (c && c != f->start_chunk)
+    {
+      next = c->next;
+      clib_mem_free (c);
+      c = next;
+    }
+
+  svm_fifo_free (f);
+
+  vec_free (buf);
+  return 0;
+}
+
 /* *INDENT-OFF* */
 svm_fifo_trace_elem_t fifo_trace[] = {};
 /* *INDENT-ON* */
@@ -1599,6 +1724,10 @@ tcp_test_fifo (vlib_main_t * vm, unformat_input_t * input)
       res = tcp_test_fifo5 (vm, input);
       if (res)
 	return res;
+
+      res = tcp_test_fifo_grow (vm, input);
+      if (res)
+	return res;
     }
   else
     {
@@ -1626,6 +1755,10 @@ tcp_test_fifo (vlib_main_t * vm, unformat_input_t * input)
 	{
 	  res = tcp_test_fifo_replay (vm, input);
 	}
+      else if (unformat (input, "grow"))
+	{
+	  res = tcp_test_fifo_grow (vm, input);
+	}
     }
 
   return res;
diff --git a/src/svm/svm_fifo.c b/src/svm/svm_fifo.c
index de1997452d5..41cd752914a 100644
--- a/src/svm/svm_fifo.c
+++ b/src/svm/svm_fifo.c
@@ -216,11 +216,10 @@ svm_fifo_init (svm_fifo_t * f, u32 size)
   f->ct_session_index = SVM_FIFO_INVALID_SESSION_INDEX;
   f->segment_index = SVM_FIFO_INVALID_INDEX;
   f->refcnt = 1;
-  f->head_chunk = &f->default_chunk;
-  f->tail_chunk = &f->default_chunk;
-  f->default_chunk.next = &f->default_chunk;
   f->default_chunk.start_byte = 0;
   f->default_chunk.length = f->size;
+  f->default_chunk.next = f->start_chunk = &f->default_chunk;
+  f->end_chunk = f->head_chunk = f->tail_chunk = f->start_chunk;
 }
 
 /** create an svm fifo, in the current heap. Fails vs blow up the process */
@@ -650,6 +649,7 @@ CLIB_MARCH_FN (svm_fifo_dequeue_nowait, int, svm_fifo_t * f, u32 len,
     return -2;			/* nothing in the fifo */
 
   to_copy = len = clib_min (cursize, len);
+  ASSERT (cursize >= to_copy);
 
   c = f->head_chunk;
   head_idx = head % f->size;
@@ -673,7 +673,9 @@ CLIB_MARCH_FN (svm_fifo_dequeue_nowait, int, svm_fifo_t * f, u32 len,
     }
   head += len;
 
-  ASSERT (cursize >= to_copy);
+  if (PREDICT_FALSE (f->flags & SVM_FIFO_F_SIZE_UPDATE))
+    svm_fifo_try_size_update (f, head);
+
   /* store-rel: consumer owned index (paired with load-acq in producer) */
   clib_atomic_store_rel_n (&f->head, head);
 
diff --git a/src/svm/svm_fifo.h b/src/svm/svm_fifo.h
index f311576f5af..39f052fb9fd 100644
--- a/src/svm/svm_fifo.h
+++ b/src/svm/svm_fifo.h
@@ -46,7 +46,7 @@ format_function_t format_ooo_list;
 #define SVM_FIFO_INVALID_INDEX		((u32)~0)
 #define SVM_FIFO_MAX_EVT_SUBSCRIBERS	8
 
-enum
+enum svm_fifo_tx_ntf_
 {
   SVM_FIFO_NO_TX_NOTIF = 0,
   SVM_FIFO_WANT_TX_NOTIF = 1,
@@ -68,13 +68,20 @@ typedef struct svm_fifo_chunk_
   u8 data[0];
 } svm_fifo_chunk_t;
 
+typedef enum svm_fifo_flag_
+{
+  SVM_FIFO_F_SIZE_UPDATE = 1 << 0,
+} svm_fifo_flag_t;
+
 typedef struct _svm_fifo
 {
   CLIB_CACHE_LINE_ALIGN_MARK (shared_first);
   u32 size;			/**< size of the fifo */
   u32 nitems;			/**< usable size(size-1) */
-  struct _svm_fifo *next;	/**< next in freelist/active chain */
-  struct _svm_fifo *prev;	/**< prev in active chain */
+  u8 flags;			/**< fifo flags */
+  svm_fifo_chunk_t *start_chunk;/**< first chunk in fifo chunk list */
+  svm_fifo_chunk_t *end_chunk;	/**< end chunk in fifo chunk list */
+  svm_fifo_chunk_t *new_chunks;	/**< chunks yet to be added to list */
 
     CLIB_CACHE_LINE_ALIGN_MARK (shared_second);
   volatile u32 has_event;	/**< non-zero if deq event exists */
@@ -88,16 +95,18 @@ typedef struct _svm_fifo
   u32 ct_session_index;		/**< Local session index for vpp */
   u32 freelist_index;		/**< aka log2(allocated_size) - const. */
   i8 refcnt;			/**< reference count  */
+  struct _svm_fifo *next;	/**< next in freelist/active chain */
+  struct _svm_fifo *prev;	/**< prev in active chain */
 
     CLIB_CACHE_LINE_ALIGN_MARK (consumer);
   u32 head;
-  svm_fifo_chunk_t *head_chunk;
+  svm_fifo_chunk_t *head_chunk;	/**< tracks chunk where head lands */
   volatile u32 want_tx_ntf;	/**< producer wants nudge */
   volatile u32 has_tx_ntf;
 
     CLIB_CACHE_LINE_ALIGN_MARK (producer);
   u32 tail;
-  svm_fifo_chunk_t *tail_chunk;
+  svm_fifo_chunk_t *tail_chunk;	/**< tracks chunk where tail lands */
 
   ooo_segment_t *ooo_segments;	/**< Pool of ooo segments */
   u32 ooos_list_head;		/**< Head of out-of-order linked-list */
@@ -511,6 +520,70 @@ ooo_segment_next (svm_fifo_t * f, ooo_segment_t * s)
   return pool_elt_at_index (f->ooo_segments, s->next);
 }
 
+static inline u8
+svm_fifo_is_wrapped (svm_fifo_t * f)
+{
+  u32 head, tail;
+  f_load_head_tail_all_acq (f, &head, &tail);
+  return head % f->size > tail % f->size;
+}
+
+static inline void
+svm_fifo_size_update (svm_fifo_t * f, svm_fifo_chunk_t * c)
+{
+  svm_fifo_chunk_t *prev;
+  u32 add_bytes = 0;
+
+  prev = f->end_chunk;
+  while (c)
+    {
+      c->start_byte = prev->start_byte + prev->length;
+      add_bytes += c->length;
+      prev->next = c;
+      prev = c;
+      c = c->next;
+    }
+  f->end_chunk = prev;
+  prev->next = f->start_chunk;
+  f->size += add_bytes;
+  f->nitems = f->size - 1;
+  f->new_chunks = 0;
+}
+
+static inline void
+svm_fifo_add_chunk (svm_fifo_t * f, svm_fifo_chunk_t * c)
+{
+  if (svm_fifo_is_wrapped (f))
+    {
+      if (f->new_chunks)
+	{
+	  svm_fifo_chunk_t *prev;
+
+	  prev = f->new_chunks;
+	  while (prev->next)
+	    prev = prev->next;
+	  prev->next = c;
+	}
+      else
+	{
+	  f->new_chunks = c;
+	}
+      f->flags |= SVM_FIFO_F_SIZE_UPDATE;
+      return;
+    }
+
+  svm_fifo_size_update (f, c);
+}
+
+static inline void
+svm_fifo_try_size_update (svm_fifo_t * f, u32 new_head)
+{
+  if (new_head % f->size > f->tail % f->size)
+    return;
+
+  svm_fifo_size_update (f, f->new_chunks);
+  f->flags &= ~SVM_FIFO_F_SIZE_UPDATE;
+}
 #endif /* __included_ssvm_fifo_h__ */
 
 /*
diff --git a/src/svm/svm_fifo_segment.c b/src/svm/svm_fifo_segment.c
index 90bf593f74c..f5fe60a280d 100644
--- a/src/svm/svm_fifo_segment.c
+++ b/src/svm/svm_fifo_segment.c
@@ -23,11 +23,10 @@ fifo_init_for_segment (svm_fifo_segment_header_t * fsh, u8 * fifo_space,
 
   f = (svm_fifo_t *) fifo_space;
   f->freelist_index = freelist_index;
-  f->default_chunk.next = &f->default_chunk;
   f->default_chunk.start_byte = 0;
   f->default_chunk.length = size;
-  f->head_chunk = &f->default_chunk;
-  f->tail_chunk = &f->default_chunk;
+  f->default_chunk.next = f->start_chunk = &f->default_chunk;
+  f->end_chunk = f->head_chunk = f->tail_chunk = f->start_chunk;
   f->next = fsh->free_fifos[freelist_index];
   fsh->free_fifos[freelist_index] = f;
 }