2 files changed, 376 insertions, 131 deletions

diff --git a/src/plugins/unittest/test_buffer.c b/src/plugins/unittest/test_buffer.c
index 18938d888bb..584ce589012 100644
--- a/src/plugins/unittest/test_buffer.c
+++ b/src/plugins/unittest/test_buffer.c
@@ -16,48 +16,237 @@
 #include <vlib/vlib.h>
 #include <vlib/buffer_funcs.h>
 
-#define TEST_I(_cond, _comment, _args...)			\
-({								\
-  int _evald = (_cond);						\
-  if (!(_evald)) {						\
-    fformat(stderr, "FAIL:%d: " _comment "\n",			\
-	    __LINE__, ##_args);					\
-  } else {							\
-    fformat(stderr, "PASS:%d: " _comment "\n",			\
-	    __LINE__, ##_args);					\
-  }								\
-  _evald;							\
-})
-
-#define TEST(_cond, _comment, _args...)			\
-{								\
-    if (!TEST_I(_cond, _comment, ##_args)) {		\
-	return 1;                                               \
-    }								\
+#define TEST_I(_cond, _comment, _args...)                                     \
+  ({                                                                          \
+    int _evald = (0 == (_cond));                                              \
+    if (_evald)                                                               \
+      {                                                                       \
+	fformat (stderr, "FAIL:%d: " _comment "\n", __LINE__, ##_args);       \
+      }                                                                       \
+    else                                                                      \
+      {                                                                       \
+	fformat (stderr, "PASS:%d: " _comment "\n", __LINE__, ##_args);       \
+      }                                                                       \
+    _evald;                                                                   \
+  })
+
+#define TEST(_cond, _comment, _args...)                                       \
+  {                                                                           \
+    if (TEST_I (_cond, _comment, ##_args))                                    \
+      {                                                                       \
+	goto err;                                                             \
+      }                                                                       \
+  }
+
+typedef struct
+{
+  i16 current_data;
+  u16 current_length;
+  u8 ref_count;
+} chained_buffer_template_t;
+
+static int
+build_chain (vlib_main_t *vm, const chained_buffer_template_t *tmpl, u32 n,
+	     clib_random_buffer_t *randbuf, u8 **rand, vlib_buffer_t **b_,
+	     u32 *bi_)
+{
+  vlib_buffer_t *bufs[2 * VLIB_BUFFER_LINEARIZE_MAX], **b = bufs;
+  u32 bis[2 * VLIB_BUFFER_LINEARIZE_MAX + 1], *bi = bis;
+  u32 n_alloc;
+
+  if (rand)
+    vec_reset_length (*rand);
+
+  ASSERT (n <= ARRAY_LEN (bufs));
+  n_alloc = vlib_buffer_alloc (vm, bi, n);
+  if (n_alloc != n)
+    {
+      vlib_buffer_free (vm, bi, n_alloc);
+      return 0;
+    }
+
+  vlib_get_buffers (vm, bis, bufs, n);
+
+  while (n > 0)
+    {
+      b[0]->next_buffer = bi[1];
+      b[0]->flags |= VLIB_BUFFER_NEXT_PRESENT;
+      b[0]->current_data = tmpl->current_data;
+      b[0]->current_length = tmpl->current_length;
+      b[0]->ref_count = 0xff == tmpl->ref_count ? 1 : tmpl->ref_count;
+
+      if (rand)
+	{
+	  const u16 len = b[0]->current_length;
+	  if (len)
+	    {
+	      vec_add (*rand, clib_random_buffer_get_data (randbuf, len), len);
+	      void *dst = vlib_buffer_get_current (b[0]);
+	      const void *src =
+		vec_elt_at_index (*rand, vec_len (*rand) - len);
+	      clib_memcpy_fast (dst, src, len);
+	    }
+	}
+
+      b++;
+      bi++;
+      tmpl++;
+      n--;
+    }
+
+  b[-1]->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
+
+  *b_ = bufs[0];
+  *bi_ = bis[0];
+  return 1;
+}
+
+static int
+check_chain (vlib_main_t *vm, vlib_buffer_t *b, const u8 *rand)
+{
+  int len_chain = vlib_buffer_length_in_chain (vm, b);
+  int len;
+
+  /* check for data corruption */
+  if (clib_memcmp (vlib_buffer_get_current (b), vec_elt_at_index (rand, 0),
+		   b->current_length))
+    return 0;
+  len = b->current_length;
+  while (b->flags & VLIB_BUFFER_NEXT_PRESENT)
+    {
+      b = vlib_get_buffer (vm, b->next_buffer);
+      if (clib_memcmp (vlib_buffer_get_current (b),
+		       vec_elt_at_index (rand, len), b->current_length))
+	return 0;
+      len += b->current_length;
+    }
+
+  /* check for data truncation */
+  if (len != vec_len (rand))
+    return 0;
+
+  /* check total length update is correct */
+  if (len != len_chain)
+    return 0;
+
+  return 1;
+}
+
+static int
+test_chain (vlib_main_t *vm, const chained_buffer_template_t *tmpl,
+	    const u32 n, const int clone_off, clib_random_buffer_t *randbuf,
+	    u8 **rand)
+{
+  vlib_buffer_t *b;
+  u32 bi[2];
+  int ret = 0;
+
+  if (!build_chain (vm, tmpl, n, randbuf, rand, &b, bi))
+    goto err0;
+
+  if (clone_off)
+    {
+      if (2 != vlib_buffer_clone (vm, bi[0], bi, 2, clone_off))
+	goto err1;
+      b = vlib_get_buffer (vm, bi[0]);
+    }
+
+  if (!(ret = vlib_buffer_chain_linearize (vm, b)))
+    goto err2;
+
+  if (!check_chain (vm, b, *rand))
+    {
+      ret = 0;
+      goto err2;
+    }
+
+err2:
+  if (clone_off)
+    vlib_buffer_free_one (vm, bi[1]);
+err1:
+  vlib_buffer_free_one (vm, bi[0]);
+err0:
+  return ret;
 }
 
-/* test function for a specific case where current_data is negative, verify
- * that there is no crash */
 static int
-linearize_negative_current_data (vlib_main_t * vm)
+linearize_test (vlib_main_t *vm)
 {
-  u32 bi[32];
-  TEST (ARRAY_LEN (bi) == vlib_buffer_alloc (vm, bi, ARRAY_LEN (bi)),
-	"buff alloc");
+  chained_buffer_template_t tmpl[VLIB_BUFFER_LINEARIZE_MAX];
+  clib_random_buffer_t randbuf;
   u32 data_size = vlib_buffer_get_default_data_size (vm);
-  u32 i;
-  for (i = 0; i < ARRAY_LEN (bi) - 1; ++i)
+  u8 *rand = 0;
+  int ret = 0;
+  int i;
+
+  clib_random_buffer_init (&randbuf, 0);
+
+  clib_memset (tmpl, 0xff, sizeof (tmpl));
+  for (i = 0; i < 2; i++)
     {
-      vlib_buffer_t *b = vlib_get_buffer (vm, bi[i]);
-      b->next_buffer = bi[i + 1];
-      b->flags |= VLIB_BUFFER_NEXT_PRESENT;
-      b->current_data = -14;
-      b->current_length = 14 + data_size;
+      tmpl[i].current_data = -14;
+      tmpl[i].current_length = 14 + data_size;
     }
+  TEST (2 == test_chain (vm, tmpl, 2, 0, &randbuf, &rand),
+	"linearize chain with negative current data");
 
-  (void) vlib_buffer_chain_linearize (vm, vlib_get_buffer (vm, bi[0]));
+  clib_memset (tmpl, 0xff, sizeof (tmpl));
+  tmpl[0].current_data = 12;
+  tmpl[0].current_length = data_size - 12;
+  tmpl[1].current_data = 0;
+  tmpl[1].current_length = 0;
+  TEST (1 == test_chain (vm, tmpl, 2, 0, &randbuf, &rand),
+	"linearize chain with empty next");
 
-  return 0;
+  clib_memset (tmpl, 0xff, sizeof (tmpl));
+  tmpl[0].current_data = 0;
+  tmpl[0].current_length = data_size - 17;
+  tmpl[1].current_data = -5;
+  tmpl[1].current_length = 3;
+  tmpl[2].current_data = 17;
+  tmpl[2].current_length = 9;
+  tmpl[3].current_data = 3;
+  tmpl[3].current_length = 5;
+  TEST (1 == test_chain (vm, tmpl, 4, 0, &randbuf, &rand),
+	"linearize chain into a single buffer");
+
+  clib_memset (tmpl, 0xff, sizeof (tmpl));
+  tmpl[0].current_data = 0;
+  tmpl[0].current_length = data_size - 2;
+  tmpl[1].current_data = -VLIB_BUFFER_PRE_DATA_SIZE;
+  tmpl[1].current_length = 20;
+  tmpl[2].current_data = data_size - 10;
+  tmpl[2].current_length = 10;
+  tmpl[3].current_data = 0;
+  tmpl[3].current_length = data_size;
+  TEST (2 == test_chain (vm, tmpl, 4, data_size - 1, &randbuf, &rand),
+	"linearize cloned chain");
+
+  clib_memset (tmpl, 0xff, sizeof (tmpl));
+  for (i = 0; i < 100; i++)
+    {
+      u8 *r = clib_random_buffer_get_data (&randbuf, 1);
+      int n = clib_max (r[0] % ARRAY_LEN (tmpl), 1);
+      int j;
+      for (j = 0; j < n; j++)
+	{
+	  r = clib_random_buffer_get_data (&randbuf, 3);
+	  i16 current_data = (i16) r[0] - VLIB_BUFFER_PRE_DATA_SIZE;
+	  u16 current_length = *(u16 *) (r + 1) % (data_size - current_data);
+	  tmpl[j].current_data = current_data;
+	  tmpl[j].current_length = current_length;
+	}
+      r = clib_random_buffer_get_data (&randbuf, 1);
+      TEST (
+	test_chain (vm, tmpl, n, r[0] > 250 ? r[0] % 128 : 0, &randbuf, &rand),
+	"linearize random chain %d", i);
+    }
+
+  ret = 1;
+err:
+  clib_random_buffer_free (&randbuf);
+  vec_free (rand);
+  return ret;
 }
 
 static clib_error_t *
@@ -65,12 +254,12 @@ test_linearize_fn (vlib_main_t * vm, unformat_input_t * input,
 		   vlib_cli_command_t * cmd)
 {
 
-  if (linearize_negative_current_data (vm))
+  if (!linearize_test (vm))
     {
-      return clib_error_return (0, "linearize_negative_current_data failed");
+      return clib_error_return (0, "linearize test failed");
     }
 
-  return (NULL);
+  return 0;
 }
 
 /* *INDENT-OFF* */
@@ -82,6 +271,53 @@ VLIB_CLI_COMMAND (test_linearize_command, static) =
 };
 /* *INDENT-ON* */
 
+static clib_error_t *
+test_linearize_speed_fn (vlib_main_t *vm, unformat_input_t *input,
+			 vlib_cli_command_t *cmd)
+{
+  /* typical 9000-bytes TCP jumbo frames */
+  const chained_buffer_template_t tmpl[5] = { { 14, 2034, 1 },
+					      { 0, 2048, 1 },
+					      { 0, 2048, 1 },
+					      { 0, 2048, 1 },
+					      { 0, 808, 1 } };
+  int i, j;
+
+  for (i = 0; i < 10; i++)
+    {
+      u64 tot = 0;
+      for (j = 0; j < 100000; j++)
+	{
+	  vlib_buffer_t *b;
+	  u32 bi;
+
+	  if (!build_chain (vm, tmpl, 5, 0, 0, &b, &bi))
+	    return clib_error_create ("build_chain() failed");
+
+	  CLIB_COMPILER_BARRIER ();
+	  u64 start = clib_cpu_time_now ();
+	  CLIB_COMPILER_BARRIER ();
+
+	  vlib_buffer_chain_linearize (vm, b);
+
+	  CLIB_COMPILER_BARRIER ();
+	  tot += clib_cpu_time_now () - start;
+	  CLIB_COMPILER_BARRIER ();
+
+	  vlib_buffer_free_one (vm, bi);
+	}
+      vlib_cli_output (vm, "%.03f ticks/call", (f64) tot / j);
+    }
+
+  return 0;
+}
+
+VLIB_CLI_COMMAND (test_linearize_speed_command, static) = {
+  .path = "test chained-buffer-linearization speed",
+  .short_help = "test chained-buffer-linearization speed",
+  .function = test_linearize_speed_fn,
+};
+
 /*
  * fd.io coding-style-patch-verification: ON
  *
diff --git a/src/vlib/buffer_funcs.h b/src/vlib/buffer_funcs.h
index 8b8a3911776..89a765ee0d3 100644
--- a/src/vlib/buffer_funcs.h
+++ b/src/vlib/buffer_funcs.h
@@ -1468,139 +1468,148 @@ vlib_buffer_space_left_at_end (vlib_main_t * vm, vlib_buffer_t * b)
     ((u8 *) vlib_buffer_get_current (b) + b->current_length);
 }
 
+#define VLIB_BUFFER_LINEARIZE_MAX 64
+
 always_inline u32
 vlib_buffer_chain_linearize (vlib_main_t * vm, vlib_buffer_t * b)
 {
-  vlib_buffer_t *db = b, *sb, *first = b;
-  int is_cloned = 0;
-  u32 bytes_left = 0, data_size;
-  u16 src_left, dst_left, n_buffers = 1;
-  u8 *dp, *sp;
-  u32 to_free = 0;
+  vlib_buffer_t *dst_b;
+  u32 n_buffers = 1, to_free = 0;
+  u16 rem_len, dst_len, data_size, src_len = 0;
+  u8 *dst, *src = 0;
 
   if (PREDICT_TRUE ((b->flags & VLIB_BUFFER_NEXT_PRESENT) == 0))
     return 1;
 
+  ASSERT (1 == b->ref_count);
+  if (PREDICT_FALSE (1 != b->ref_count))
+    return 0;
+
   data_size = vlib_buffer_get_default_data_size (vm);
+  rem_len = vlib_buffer_length_in_chain (vm, b) - b->current_length;
 
-  dst_left = vlib_buffer_space_left_at_end (vm, b);
+  dst_b = b;
+  dst = vlib_buffer_get_tail (dst_b);
+  dst_len = vlib_buffer_space_left_at_end (vm, dst_b);
 
-  while (b->flags & VLIB_BUFFER_NEXT_PRESENT)
-    {
-      b = vlib_get_buffer (vm, b->next_buffer);
-      if (b->ref_count > 1)
-	is_cloned = 1;
-      bytes_left += b->current_length;
-      n_buffers++;
-    }
+  b->total_length_not_including_first_buffer -= dst_len;
 
-  /* if buffer is cloned, create completely new chain - unless everything fits
-   * into one buffer */
-  if (is_cloned && bytes_left >= dst_left)
+  while (rem_len > 0)
     {
-      u32 len = 0;
-      u32 space_needed = bytes_left - dst_left;
-      u32 tail;
-
-      if (vlib_buffer_alloc (vm, &tail, 1) == 0)
-	return 0;
+      u16 copy_len;
 
-      ++n_buffers;
-      len += data_size;
-      b = vlib_get_buffer (vm, tail);
-
-      while (len < space_needed)
+      while (0 == src_len)
 	{
-	  u32 bi;
-	  if (vlib_buffer_alloc (vm, &bi, 1) == 0)
-	    {
-	      vlib_buffer_free_one (vm, tail);
-	      return 0;
-	    }
-	  b->flags = VLIB_BUFFER_NEXT_PRESENT;
-	  b->next_buffer = bi;
-	  b = vlib_get_buffer (vm, bi);
-	  len += data_size;
-	  n_buffers++;
+	  ASSERT (b->flags & VLIB_BUFFER_NEXT_PRESENT);
+	  if (PREDICT_FALSE (!(b->flags & VLIB_BUFFER_NEXT_PRESENT)))
+	    break; /* malformed chained buffer */
+
+	  b = vlib_get_buffer (vm, b->next_buffer);
+	  src = vlib_buffer_get_current (b);
+	  src_len = b->current_length;
 	}
-      sb = vlib_get_buffer (vm, first->next_buffer);
-      to_free = first->next_buffer;
-      first->next_buffer = tail;
-    }
-  else
-    sb = vlib_get_buffer (vm, first->next_buffer);
 
-  src_left = sb->current_length;
-  sp = vlib_buffer_get_current (sb);
-  dp = vlib_buffer_get_tail (db);
+      if (0 == dst_len)
+	{
+	  ASSERT (dst_b->flags & VLIB_BUFFER_NEXT_PRESENT);
+	  if (PREDICT_FALSE (!(dst_b->flags & VLIB_BUFFER_NEXT_PRESENT)))
+	    break; /* malformed chained buffer */
 
-  while (bytes_left)
-    {
-      u16 bytes_to_copy;
+	  vlib_buffer_t *next_dst_b = vlib_get_buffer (vm, dst_b->next_buffer);
 
-      if (dst_left == 0)
-	{
-	  db->current_length = dp - (u8 *) vlib_buffer_get_current (db);
-	  ASSERT (db->flags & VLIB_BUFFER_NEXT_PRESENT);
-	  db = vlib_get_buffer (vm, db->next_buffer);
-	  dst_left = data_size;
-	  if (db->current_data > 0)
+	  if (PREDICT_TRUE (1 == next_dst_b->ref_count))
 	    {
-	      db->current_data = 0;
+	      /* normal case: buffer is not cloned, just use it */
+	      dst_b = next_dst_b;
 	    }
 	  else
 	    {
-	      dst_left += -db->current_data;
+	      /* cloned buffer, build a new dest chain from there */
+	      vlib_buffer_t *bufs[VLIB_BUFFER_LINEARIZE_MAX];
+	      u32 bis[VLIB_BUFFER_LINEARIZE_MAX + 1];
+	      const int n = (rem_len + data_size - 1) / data_size;
+	      int n_alloc;
+	      int i;
+
+	      ASSERT (n <= VLIB_BUFFER_LINEARIZE_MAX);
+	      if (PREDICT_FALSE (n > VLIB_BUFFER_LINEARIZE_MAX))
+		return 0;
+
+	      n_alloc = vlib_buffer_alloc (vm, bis, n);
+	      if (PREDICT_FALSE (n_alloc != n))
+		{
+		  vlib_buffer_free (vm, bis, n_alloc);
+		  return 0;
+		}
+
+	      vlib_get_buffers (vm, bis, bufs, n);
+
+	      for (i = 0; i < n - 1; i++)
+		{
+		  bufs[i]->flags |= VLIB_BUFFER_NEXT_PRESENT;
+		  bufs[i]->next_buffer = bis[i + 1];
+		}
+
+	      to_free = dst_b->next_buffer;
+	      dst_b->next_buffer = bis[0];
+	      dst_b = bufs[0];
 	    }
-	  dp = vlib_buffer_get_current (db);
-	}
 
-      while (src_left == 0)
-	{
-	  ASSERT (sb->flags & VLIB_BUFFER_NEXT_PRESENT);
-	  sb = vlib_get_buffer (vm, sb->next_buffer);
-	  src_left = sb->current_length;
-	  sp = vlib_buffer_get_current (sb);
+	  n_buffers++;
+
+	  dst_b->current_data = clib_min (0, dst_b->current_data);
+	  dst_b->current_length = 0;
+
+	  dst = dst_b->data + dst_b->current_data;
+	  dst_len = data_size - dst_b->current_data;
 	}
 
-      bytes_to_copy = clib_min (dst_left, src_left);
+      copy_len = clib_min (src_len, dst_len);
 
-      if (dp != sp)
+      if (PREDICT_TRUE (src == dst))
 	{
-	  if (sb == db)
-	    bytes_to_copy = clib_min (bytes_to_copy, sp - dp);
-
-	  clib_memcpy_fast (dp, sp, bytes_to_copy);
+	  /* nothing to do */
+	}
+      else if (src + copy_len > dst && dst + copy_len > src)
+	{
+	  /* src and dst overlap */
+	  ASSERT (b == dst_b);
+	  memmove (dst, src, copy_len);
+	}
+      else
+	{
+	  clib_memcpy_fast (dst, src, copy_len);
 	}
 
-      src_left -= bytes_to_copy;
-      dst_left -= bytes_to_copy;
-      dp += bytes_to_copy;
-      sp += bytes_to_copy;
-      bytes_left -= bytes_to_copy;
+      dst_b->current_length += copy_len;
+
+      dst += copy_len;
+      src += copy_len;
+      dst_len -= copy_len;
+      src_len -= copy_len;
+      rem_len -= copy_len;
     }
-  if (db != first)
-    db->current_data = 0;
-  db->current_length = dp - (u8 *) vlib_buffer_get_current (db);
 
-  if (is_cloned && to_free)
+  /* in case of a malformed chain buffer, we'll exit early from the loop. */
+  ASSERT (0 == rem_len);
+  b->total_length_not_including_first_buffer -= rem_len;
+
+  if (to_free)
     vlib_buffer_free_one (vm, to_free);
-  else
+
+  if (dst_b->flags & VLIB_BUFFER_NEXT_PRESENT)
     {
-      if (db->flags & VLIB_BUFFER_NEXT_PRESENT)
-	vlib_buffer_free_one (vm, db->next_buffer);
-      db->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
-      b = first;
-      n_buffers = 1;
-      while (b->flags & VLIB_BUFFER_NEXT_PRESENT)
+      /* the resulting chain is smaller than the original, cut it there */
+      dst_b->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
+      vlib_buffer_free_one (vm, dst_b->next_buffer);
+      if (1 == n_buffers)
 	{
-	  b = vlib_get_buffer (vm, b->next_buffer);
-	  ++n_buffers;
+	  /* no longer a chained buffer */
+	  dst_b->flags &= ~VLIB_BUFFER_TOTAL_LENGTH_VALID;
+	  dst_b->total_length_not_including_first_buffer = 0;
 	}
     }
 
-  first->flags &= ~VLIB_BUFFER_TOTAL_LENGTH_VALID;
-
   return n_buffers;
 }