svm: fix multi-chunk fifo alloc and add more tests

Type: fix

- make sure that chunks and the rbtree are initialized if fifo segment
allocates multiple chunks for the fifo.
- ensure head/tail chunks are updated on all enqueue/dequeue events,
including when dropping data.
- more unit tests

Also fixes dequeue drop updates of head chunk.

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

diff --git a/src/plugins/unittest/svm_fifo_test.c b/src/plugins/unittest/svm_fifo_test.c
index bf633b7..6f8873d 100644 (file)
--- a/src/plugins/unittest/svm_fifo_test.c
+++ b/src/plugins/unittest/svm_fifo_test.c
@@ -1225,6 +1225,7 @@ sfifo_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input)
              fifo_size + 100, f->size);
   SFIFO_TEST (c->start_byte == fifo_size, "start byte expected %u is %u",
              fifo_size, c->start_byte);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /*
    *  Add with fifo wrapped
@@ -1243,6 +1244,7 @@ sfifo_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input)
              fifo_size + 100, f->size);
   SFIFO_TEST (c->start_byte == fifo_size + 100, "start byte expected %u is "
              " %u", fifo_size + 100, c->start_byte);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /*
    * Unwrap fifo
@@ -1255,6 +1257,7 @@ sfifo_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input)
              fifo_size + 200, f->size);
   SFIFO_TEST (c->start_byte == fifo_size + 100, "start byte expected %u is "
              "%u", fifo_size + 100, c->start_byte);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /*
    * Add N chunks
@@ -1296,6 +1299,7 @@ sfifo_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input)
              fifo_size + 200 + 10 * 100, f->size);
   SFIFO_TEST (f->tail == old_tail, "new tail expected %u is %u", old_tail,
              f->tail);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /*
    * Enqueue/dequeue tests
@@ -1351,6 +1355,7 @@ sfifo_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input)
     vlib_cli_output (vm, "[%d] dequeued %u expected %u", j, data_buf[j],
                     test_data[j]);
   SFIFO_TEST ((rv == 0), "dequeued compared to original returned %d", rv);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /*
    * Simple enqueue/deq and data validation (2)
@@ -1377,6 +1382,42 @@ sfifo_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input)
     vlib_cli_output (vm, "[%d] dequeued %u expected %u", j, data_buf[j],
                     test_data[j]);
   SFIFO_TEST ((rv == 0), "dequeued compared to original returned %d", rv);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
+
+  /*
+   * Simple enqueue and drop
+   */
+  for (i = 0; i <= n_enqs; i++)
+    {
+      rv = svm_fifo_enqueue (f, enq_bytes, test_data + i * enq_bytes);
+      if (rv < 0)
+       SFIFO_TEST (0, "failed to enqueue");
+    }
+
+  rv = svm_fifo_dequeue_drop (f, test_n_bytes / 2);
+  SFIFO_TEST (rv == test_n_bytes / 2, "drop should be equal");
+  SFIFO_TEST (svm_fifo_is_sane (f), "head chunk should be valid");
+  rv = svm_fifo_dequeue_drop (f, test_n_bytes / 2);
+  SFIFO_TEST (rv == test_n_bytes / 2, "drop should be equal");
+  SFIFO_TEST (svm_fifo_is_sane (f), "head chunk should be valid");
+  SFIFO_TEST (svm_fifo_max_dequeue (f) == 0, "should be empty");
+
+  /*
+   * Simple enqueue and drop all
+   */
+
+  /* Enqueue just enough data to make sure fifo is not full */
+  for (i = 0; i <= n_enqs / 2; i++)
+    {
+      rv = svm_fifo_enqueue (f, enq_bytes, test_data + i * enq_bytes);
+      if (rv < 0)
+       SFIFO_TEST (0, "failed to enqueue");
+    }
+
+  /* check drop all as well */
+  svm_fifo_dequeue_drop_all (f);
+  SFIFO_TEST (svm_fifo_is_sane (f), "head chunk should be valid");
+  SFIFO_TEST (svm_fifo_max_dequeue (f) == 0, "should be empty");
 
   /*
    * OOO enqueues/dequeues and data validation (1)
@@ -1408,6 +1449,7 @@ sfifo_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input)
     vlib_cli_output (vm, "[%d] dequeued %u expected %u", j, data_buf[j],
                     test_data[j]);
   SFIFO_TEST ((rv == 0), "dequeued compared to original returned %d", rv);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /*
    * OOO enqueues/dequeues and data validation (2)
@@ -1427,8 +1469,10 @@ sfifo_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input)
          goto cleanup;
        }
     }
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   svm_fifo_enqueue (f, enq_bytes, &test_data[0]);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   memset (data_buf, 0, vec_len (data_buf));
   for (i = 0; i <= n_deqs; i++)
@@ -1440,6 +1484,7 @@ sfifo_test_fifo_grow (vlib_main_t * vm, unformat_input_t * input)
     vlib_cli_output (vm, "[%d] dequeued %u expected %u", j, data_buf[j],
                     test_data[j]);
   SFIFO_TEST ((rv == 0), "dequeued compared to original returned %d", rv);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /*
    * Cleanup
@@ -1554,6 +1599,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (f->size == 12 * chunk_size + 1, "size expected %u is %u",
              12 * chunk_size + 1, f->size);
   SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Check enqueue space to force size reduction */
   (void) svm_fifo_max_enqueue (f);
@@ -1564,6 +1610,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
              " be set");
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_SHRINK), "shrink flag should not be"
              " set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   collected = c = svm_fifo_collect_chunks (f);
   rv = chunk_list_len (c);
@@ -1572,6 +1619,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (rv == 11, "expected %u chunks got %u", 11, rv);
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /*
    * Fifo wrap and multiple chunks used
@@ -1600,6 +1648,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (f->size == 11 * chunk_size + 1, "size expected %u is %u",
              11 * chunk_size + 1, f->size);
   SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Check enqueue space to try size reduction. Should not work */
   rv = svm_fifo_max_enqueue (f);
@@ -1610,6 +1659,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Dequeue byte-by-byte up to last byte on last chunk */
   deq_bytes = f->size - f->size / 2 - 1;
@@ -1620,6 +1670,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
       if (rv < 0)
        SFIFO_TEST (0, "dequeue returned");
     }
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   rv = svm_fifo_max_enqueue (f);
 
@@ -1635,6 +1686,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Dequeue one more such that head goes beyond last chunk */
   rv = svm_fifo_dequeue (f, 1, &data_buf[deq_bytes]);
@@ -1651,6 +1703,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
              " set");
   SFIFO_TEST (f->flags & SVM_FIFO_F_COLLECT_CHUNKS, "collect flag should"
              " be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Dequeue the rest of the data */
   deq_bytes += 1;
@@ -1681,6 +1734,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (rv == 8, "expected %u chunks got %u", 8, rv);
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /*
    * OOO segment on chunk that should be removed
@@ -1700,6 +1754,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   rv = svm_fifo_max_enqueue (f);
   SFIFO_TEST (rv == vec_len (test_data) - 200, "free space expected %u is %u",
              vec_len (test_data) - 200, rv);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Ask to reduce size */
   rv = svm_fifo_reduce_size (f, 3.5 * chunk_size, 0);
@@ -1708,6 +1763,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (f->size == 11 * chunk_size + 1, "size expected %u is %u",
              11 * chunk_size + 1, f->size);
   SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Try to force size reduction but it should fail */
   rv = svm_fifo_max_enqueue (f);
@@ -1719,6 +1775,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Dequeue the in order data. This should shrink nitems */
   rv = svm_fifo_dequeue (f, 200, data_buf);
@@ -1735,11 +1792,13 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Enqueue the missing 50 bytes. Fifo will become full */
   rv = svm_fifo_enqueue (f, 50, &test_data[200]);
   SFIFO_TEST (rv == vec_len (test_data) - 200, "free space expected %u is %u",
              vec_len (test_data) - 200, rv);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   rv = svm_fifo_max_enqueue (f);
 
@@ -1749,6 +1808,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
 
   /* Dequeue a chunk and check nitems shrink but fifo still full */
@@ -1764,6 +1824,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Dequeue enough to unwrap the fifo */
   deq_bytes = f->size - f->size / 2 - 300;
@@ -1781,6 +1842,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
              " set");
   SFIFO_TEST (f->flags & SVM_FIFO_F_COLLECT_CHUNKS, "collect flag should"
              " be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Dequeue the rest */
   svm_fifo_dequeue (f, test_n_bytes / 2, &data_buf[300 + deq_bytes]);
@@ -1797,13 +1859,16 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (rv == 8, "expected %u chunks got %u", 8, rv);
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   chunk_list_splice (collected, c);
 
   /*
-   * Remove all chunks possible
+   * Remove all chunks possible (1)
+   *
+   * Tail and head are in first chunk that is not removed
    */
-  svm_fifo_init_pointers (f, 601, 601);
+  svm_fifo_init_pointers (f, 600, 600);
   rv = svm_fifo_reduce_size (f, 8 * chunk_size, 1);
   SFIFO_TEST (rv == 7 * chunk_size, "actual len expected %u is %u",
              7 * chunk_size, rv);
@@ -1814,10 +1879,12 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
   SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   rv = svm_fifo_max_enqueue (f);
   SFIFO_TEST (rv == chunk_size, "free space expected %u is %u", chunk_size,
              rv);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /* Force head/tail to move to first chunk */
   svm_fifo_enqueue (f, 1, test_data);
@@ -1832,6 +1899,57 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
              " set");
   SFIFO_TEST (f->flags & SVM_FIFO_F_COLLECT_CHUNKS, "collect flag should"
              " be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
+
+  c = svm_fifo_collect_chunks (f);
+  rv = chunk_list_len (c);
+  SFIFO_TEST (rv == 7, "expected %u chunks got %u", 7, rv);
+  SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
+             " not be set");
+  SFIFO_TEST (!(f->flags & SVM_FIFO_F_MULTI_CHUNK), "multi-chunk flag should"
+             " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
+
+  /* re-add chunks for next test */
+  svm_fifo_add_chunk (f, c);
+
+  /*
+   * Remove all chunks possible (2)
+   *
+   * Tail and head are in the first chunk that should eventually be removed
+   */
+  svm_fifo_init_pointers (f, 601, 601);
+  rv = svm_fifo_reduce_size (f, 8 * chunk_size, 1);
+  SFIFO_TEST (rv == 7 * chunk_size, "actual len expected %u is %u",
+             7 * chunk_size, rv);
+  SFIFO_TEST (f->size == 7 * chunk_size + 1, "size expected %u is %u",
+             7 * chunk_size + 1, f->size);
+  SFIFO_TEST (f->nitems == 1 * chunk_size, "nitems expected %u is %u",
+             1 * chunk_size, f->nitems);
+  SFIFO_TEST (f->flags & SVM_FIFO_F_SHRINK, "shrink flag should be set");
+  SFIFO_TEST (!(f->flags & SVM_FIFO_F_COLLECT_CHUNKS), "collect flag should"
+             " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
+
+  rv = svm_fifo_max_enqueue (f);
+  SFIFO_TEST (rv == chunk_size, "free space expected %u is %u", chunk_size,
+             rv);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
+
+  /* Force head/tail to move to first chunk */
+  svm_fifo_enqueue (f, chunk_size, test_data);
+  svm_fifo_dequeue (f, chunk_size, data_buf);
+  rv = svm_fifo_max_enqueue (f);
+
+  SFIFO_TEST (rv == chunk_size, "free space expected %u is %u", chunk_size,
+             rv);
+  SFIFO_TEST (f->size == chunk_size + 1, "size expected %u is %u",
+             chunk_size + 1, f->size);
+  SFIFO_TEST (!(f->flags & SVM_FIFO_F_SHRINK), "shrink flag should not be"
+             " set");
+  SFIFO_TEST (f->flags & SVM_FIFO_F_COLLECT_CHUNKS, "collect flag should"
+             " be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   c = svm_fifo_collect_chunks (f);
   rv = chunk_list_len (c);
@@ -1840,6 +1958,7 @@ sfifo_test_fifo_shrink (vlib_main_t * vm, unformat_input_t * input)
              " not be set");
   SFIFO_TEST (!(f->flags & SVM_FIFO_F_MULTI_CHUNK), "multi-chunk flag should"
              " not be set");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   chunk_list_splice (collected, c);
 
@@ -1982,6 +2101,7 @@ sfifo_test_fifo_segment_fifo_grow (int verbose)
   fifo_segment_grow_fifo (fs, f, fifo_size);
   SFIFO_TEST (f->size == 2 * fifo_size, "fifo size should be %u is %u",
              2 * fifo_size, f->size);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   n_chunks = fifo_segment_num_free_chunks (fs, fifo_size);
   SFIFO_TEST (n_chunks == n_batch - 2, "free 2^10B chunks "
@@ -2063,6 +2183,7 @@ sfifo_test_fifo_segment_fifo_grow (int verbose)
 
   SFIFO_TEST (n_free_chunk_bytes - 16 * fifo_size == rv, "free chunk bytes "
              "expected %u is %u", n_free_chunk_bytes - 16 * fifo_size, rv);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   fifo_segment_free_fifo (fs, f);
   rv = fifo_segment_fl_chunk_bytes (fs);
@@ -2081,6 +2202,8 @@ sfifo_test_fifo_segment_fifo_grow (int verbose)
              32 * fifo_size);
 
   f = fifo_segment_alloc_fifo (fs, 17 * fifo_size, FIFO_SEGMENT_RX_FIFO);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
+
   rv = fifo_segment_fl_chunk_bytes (fs);
 
   /* Make sure that the non-power of two chunk freed above is correctly
@@ -2100,6 +2223,7 @@ sfifo_test_fifo_segment_fifo_grow (int verbose)
    */
   f = fifo_segment_alloc_fifo (fs, n_free_chunk_bytes, FIFO_SEGMENT_RX_FIFO);
   SFIFO_TEST (f != 0, "allocation should work");
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   fifo_segment_free_fifo (fs, f);
 
@@ -2388,7 +2512,7 @@ sfifo_test_fifo_segment_prealloc (int verbose)
   u32 max_pairs, pairs_req, free_space, pair_mem;
   svm_fifo_t *f, *old;
   fifo_segment_t *fs;
-  int rv;
+  int rv, alloc;
 
   clib_memset (a, 0, sizeof (*a));
 
@@ -2438,26 +2562,39 @@ sfifo_test_fifo_segment_prealloc (int verbose)
   SFIFO_TEST (rv == 0, "prealloc chunks expected %u is %u", 0, rv);
   rv = fifo_segment_fl_chunk_bytes (fs);
   SFIFO_TEST (rv == 0, "chunk free space expected %u is %u", 0, rv);
+  SFIFO_TEST (svm_fifo_is_sane (f), "fifo should be sane");
 
   /*
    * Multiple preallocs that consume the remaining space
    */
+  fifo_segment_update_free_bytes (fs);
+  free_space = fifo_segment_free_bytes (fs);
   pair_mem = 2 * (4096 + sizeof (*f) + sizeof (svm_fifo_chunk_t));
-  max_pairs = pairs_req = free_space / pair_mem - 1;
+  max_pairs = pairs_req = (free_space / pair_mem) - 1;
   fifo_segment_preallocate_fifo_pairs (fs, 4096, 4096, &pairs_req);
-  SFIFO_TEST (pairs_req == 0, "prealloc pairs should work");
+  SFIFO_TEST (pairs_req == 0, "prealloc pairs should work req %u", max_pairs);
   rv = fifo_segment_num_free_chunks (fs, 4096);
   SFIFO_TEST (rv == max_pairs * 2, "prealloc chunks expected %u is %u",
              max_pairs * 2, rv);
 
-  rv = fifo_segment_prealloc_fifo_chunks (fs, 4096, 2);
-  SFIFO_TEST (rv == 0, "chunk prealloc should work");
+  fifo_segment_update_free_bytes (fs);
+  rv = fifo_segment_free_bytes (fs);
+  SFIFO_TEST (rv < 2 * pair_mem, "free bytes %u less than %u", rv,
+             2 * pair_mem);
+
+  /* Preallocate as many more chunks as possible. Heap is almost full
+   * so we may not use all the free space*/
+  alloc = 0;
+  while (!fifo_segment_prealloc_fifo_chunks (fs, 4096, 1))
+    alloc++;
+  SFIFO_TEST (alloc, "chunk prealloc should work %u", alloc);
   rv = fifo_segment_num_free_chunks (fs, 4096);
-  SFIFO_TEST (rv == (max_pairs + 1) * 2, "prealloc chunks expected %u is %u",
-             (max_pairs + 1) * 2, rv);
+  SFIFO_TEST (rv == max_pairs * 2 + alloc, "prealloc chunks expected %u "
+             "is %u", max_pairs * 2 + alloc, rv);
 
-  free_space = fifo_segment_free_bytes (fs);
-  SFIFO_TEST (rv < 8192, "free bytes expected less than %u is %u", 8192, rv);
+  rv = fifo_segment_free_bytes (fs);
+  SFIFO_TEST (rv < pair_mem, "free bytes expected less than %u is %u",
+             pair_mem, rv);
 
   /*
    * Test negative prealloc cases

diff --git a/src/svm/fifo_segment.c b/src/svm/fifo_segment.c
index d47c853..eeb2746 100644 (file)
--- a/src/svm/fifo_segment.c
+++ b/src/svm/fifo_segment.c
@@ -394,6 +394,14 @@ fifo_segment_alloc_fifo (fifo_segment_t * fs, u32 data_bytes,
   /* (re)initialize the fifo, as in svm_fifo_create */
   svm_fifo_init (f, data_bytes);
 
+  /* Initialize chunks and rbtree for multi-chunk fifos */
+  if (f->start_chunk->next != f->start_chunk)
+    {
+      void *oldheap = ssvm_push_heap (fs->ssvm.sh);
+      svm_fifo_init_chunks (f);
+      ssvm_pop_heap (oldheap);
+    }
+
   /* If rx fifo type 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
@@ -613,12 +621,16 @@ fifo_segment_preallocate_fifo_pairs (fifo_segment_t * fs,
   /* Calculate space requirements */
   pair_size = 2 * hdrs + rx_rounded_data_size + tx_rounded_data_size;
   space_available = fs_free_space (fs);
-  pairs_to_alloc = clib_min (space_available / pair_size, *n_fifo_pairs);
+  pairs_to_alloc = space_available / pair_size;
+  pairs_to_alloc = clib_min (pairs_to_alloc, *n_fifo_pairs);
+
+  if (!pairs_to_alloc)
+    return;
 
   if (fs_try_alloc_fifo_batch (fs, rx_fl_index, pairs_to_alloc))
-    clib_warning ("rx prealloc failed");
+    clib_warning ("rx prealloc failed: pairs %u", pairs_to_alloc);
   if (fs_try_alloc_fifo_batch (fs, tx_fl_index, pairs_to_alloc))
-    clib_warning ("tx prealloc failed");
+    clib_warning ("tx prealloc failed: pairs %u", pairs_to_alloc);
 
   /* Account for the pairs allocated */
   *n_fifo_pairs -= pairs_to_alloc;

diff --git a/src/svm/svm_fifo.c b/src/svm/svm_fifo.c
index 3d53829..56f53a3 100644 (file)
--- a/src/svm/svm_fifo.c
+++ b/src/svm/svm_fifo.c
@@ -404,6 +404,31 @@ svm_fifo_init (svm_fifo_t * f, u32 size)
   f->head_chunk = f->tail_chunk = f->ooo_enq = f->ooo_deq = f->start_chunk;
 }
 
+void
+svm_fifo_init_chunks (svm_fifo_t * f)
+{
+  svm_fifo_chunk_t *c, *prev;
+
+  if (f->start_chunk->next == f->start_chunk)
+    return;
+
+  f->flags |= SVM_FIFO_F_MULTI_CHUNK;
+  rb_tree_init (&f->chunk_lookup);
+  rb_tree_add2 (&f->chunk_lookup, 0, pointer_to_uword (f->start_chunk));
+
+  f->start_chunk->start_byte = 0;
+  prev = f->start_chunk;
+  c = prev->next;
+
+  while (c != f->start_chunk)
+    {
+      c->start_byte = prev->start_byte + prev->length;
+      rb_tree_add2 (&f->chunk_lookup, c->start_byte, pointer_to_uword (c));
+      prev = c;
+      c = c->next;
+    }
+}
+
 /**
  * Creates a fifo in the current heap. Fails vs blow up the process
  */
@@ -559,6 +584,7 @@ svm_fifo_add_chunk (svm_fifo_t * f, svm_fifo_chunk_t * c)
    * that this is called with the heap where the rbtree's pool is pushed. */
   if (!(f->flags & SVM_FIFO_F_MULTI_CHUNK))
     {
+      ASSERT (f->start_chunk->next == f->start_chunk);
       rb_tree_init (&f->chunk_lookup);
       rb_tree_add2 (&f->chunk_lookup, 0, pointer_to_uword (f->start_chunk));
       f->flags |= SVM_FIFO_F_MULTI_CHUNK;
@@ -626,7 +652,7 @@ svm_fifo_collect_chunks (svm_fifo_t * f)
 void
 svm_fifo_try_shrink (svm_fifo_t * f, u32 head, u32 tail)
 {
-  u32 len_to_shrink = 0, tail_pos, len;
+  u32 len_to_shrink = 0, tail_pos, len, last_pos;
   svm_fifo_chunk_t *cur, *prev, *next, *start;
 
   tail_pos = tail;
@@ -649,13 +675,24 @@ svm_fifo_try_shrink (svm_fifo_t * f, u32 head, u32 tail)
    * - not wrapped
    * - last used byte less than start of last chunk
    */
-  if (tail_pos >= head && tail_pos <= f->end_chunk->start_byte)
+  if (tail_pos >= head && tail_pos < f->end_chunk->start_byte)
     {
       /* Lookup the last position not to be removed. Since size still needs
-       * to be nitems + 1, nitems must fall within the usable space */
-      tail_pos = tail_pos > 0 ? tail_pos - 1 : tail_pos;
-      prev = svm_fifo_find_chunk (f, clib_max (f->nitems, tail_pos));
+       * to be nitems + 1, nitems must fall within the usable space. Also,
+       * first segment is not removable, so tail_pos can be 0. */
+      last_pos = tail_pos > 0 ? tail_pos - 1 : tail_pos;
+      prev = svm_fifo_find_chunk (f, clib_max (f->nitems, last_pos));
       next = prev->next;
+      /* If tail_pos is first position in next, skip the chunk, otherwise,
+       * we must update the tail and, if fifo size is 0, even the head.
+       * We should not invalidate the tail for the caller and must not change
+       * consumer owned variables from code that's typically called by the
+       * producer */
+      if (next->start_byte == tail_pos)
+       {
+         prev = next;
+         next = next->next;
+       }
       while (next != f->start_chunk)
        {
          cur = next;
@@ -790,7 +827,11 @@ svm_fifo_enqueue (svm_fifo_t * f, u32 len, const u8 * src)
 
   /* collect out-of-order segments */
   if (PREDICT_FALSE (f->ooos_list_head != OOO_SEGMENT_INVALID_INDEX))
-    len += ooo_segment_try_collect (f, len, &tail);
+    {
+      len += ooo_segment_try_collect (f, len, &tail);
+      if (!svm_fifo_chunk_includes_pos (f->tail_chunk, tail))
+       f->tail_chunk = svm_fifo_find_chunk (f, tail);
+    }
 
   /* store-rel: producer owned index (paired with load-acq in consumer) */
   clib_atomic_store_rel_n (&f->tail, tail);
@@ -847,6 +888,10 @@ svm_fifo_enqueue_nocopy (svm_fifo_t * f, u32 len)
   /* load-relaxed: producer owned index */
   tail = f->tail;
   tail = (tail + len) % f->size;
+
+  if (!svm_fifo_chunk_includes_pos (f->tail_chunk, tail))
+    f->tail_chunk = svm_fifo_find_chunk (f, tail);
+
   /* store-rel: producer owned index (paired with load-acq in consumer) */
   clib_atomic_store_rel_n (&f->tail, tail);
 }
@@ -919,6 +964,9 @@ svm_fifo_dequeue_drop (svm_fifo_t * f, u32 len)
   /* move head */
   head = (head + total_drop_bytes) % f->size;
 
+  if (!svm_fifo_chunk_includes_pos (f->head_chunk, head))
+    f->head_chunk = svm_fifo_find_chunk (f, head);
+
   /* store-rel: consumer owned index (paired with load-acq in producer) */
   clib_atomic_store_rel_n (&f->head, head);
 
@@ -930,6 +978,10 @@ svm_fifo_dequeue_drop_all (svm_fifo_t * f)
 {
   /* consumer foreign index */
   u32 tail = clib_atomic_load_acq_n (&f->tail);
+
+  if (!svm_fifo_chunk_includes_pos (f->head_chunk, tail))
+    f->head_chunk = svm_fifo_find_chunk (f, tail);
+
   /* store-rel: consumer owned index (paired with load-acq in producer) */
   clib_atomic_store_rel_n (&f->head, tail);
 }
@@ -1055,6 +1107,45 @@ svm_fifo_del_subscriber (svm_fifo_t * f, u8 subscriber)
     }
 }
 
+u8
+svm_fifo_is_sane (svm_fifo_t * f)
+{
+  if (f->size - 1 != f->nitems && !(f->flags & SVM_FIFO_F_SHRINK))
+    return 0;
+  if (!svm_fifo_chunk_includes_pos (f->head_chunk, f->head))
+    return 0;
+  if (!svm_fifo_chunk_includes_pos (f->tail_chunk, f->tail))
+    return 0;
+
+  if (f->start_chunk->next != f->start_chunk)
+    {
+      svm_fifo_chunk_t *c, *prev = 0, *tmp;
+      u32 size = 0;
+
+      if (!(f->flags & SVM_FIFO_F_MULTI_CHUNK))
+       return 0;
+
+      c = f->start_chunk;
+      do
+       {
+         tmp = svm_fifo_find_chunk (f, c->start_byte);
+         if (tmp != c)
+           return 0;
+         if (prev && (prev->start_byte + prev->length != c->start_byte))
+           return 0;
+         size += c->length;
+         prev = c;
+         c = c->next;
+       }
+      while (c != f->start_chunk);
+
+      if (size != f->size)
+       return 0;
+    }
+
+  return 1;
+}
+
 u8 *
 format_ooo_segment (u8 * s, va_list * args)
 {

diff --git a/src/svm/svm_fifo.h b/src/svm/svm_fifo.h
index 9b23d7e..d5dfc9c 100644 (file)
--- a/src/svm/svm_fifo.h
+++ b/src/svm/svm_fifo.h
@@ -252,9 +252,16 @@ svm_fifo_t *svm_fifo_create (u32 size);
 /**
  * Initialize fifo
  *
+ * @param f            fifo
  * @param size         size for fifo
  */
 void svm_fifo_init (svm_fifo_t * f, u32 size);
+/**
+ * Initialize fifo chunks and rbtree
+ *
+ * @param f            fifo
+ */
+void svm_fifo_init_chunks (svm_fifo_t * f);
 /**
  * Allocate a fifo chunk on heap
  *
@@ -456,13 +463,20 @@ void svm_fifo_del_subscriber (svm_fifo_t * f, u8 subscriber);
  * @return     number of out of order segments
  */
 u32 svm_fifo_n_ooo_segments (svm_fifo_t * f);
-/*
+/**
  * First out-of-order segment for fifo
  *
  * @param f    fifo
  * @return     first out-of-order segment for fifo
  */
 ooo_segment_t *svm_fifo_first_ooo_segment (svm_fifo_t * f);
+/**
+ * Check if fifo is sane. Debug only.
+ *
+ * @param f    fifo
+ * @return     1 if sane, 0 otherwise
+ */
+u8 svm_fifo_is_sane (svm_fifo_t * f);
 format_function_t format_svm_fifo;
 
 /**