buffer chain linearization

Rewrite vlib_buffer_chain_linearize function so that it works as intended.
Linearize buffer chains coming out of reassembly to work around some
dpdk-tx issues. Note that this is not a complete workaround
as a sufficiently large packet will still cause the resulting chain to
be too long.

Drop features from reassembly code which relies on knowing which and how
many buffers were freed during linearization, buffer counts and tracing
capabilities for these cases.

Change-Id: Ic65de53ecb5c78cd96b178033f6a576ab4060ed1
Signed-off-by: Klement Sekera <ksekera@cisco.com>

2 files changed, 125 insertions, 106 deletions

diff --git a/src/vlib/buffer_funcs.h b/src/vlib/buffer_funcs.h
index b561a91c394..0b15a23e8a9 100644
--- a/src/vlib/buffer_funcs.h
+++ b/src/vlib/buffer_funcs.h
@@ -42,6 +42,10 @@
 
 #include <vppinfra/hash.h>
 #include <vppinfra/fifo.h>
+#include <vlib/buffer.h>
+#include <vlib/physmem_funcs.h>
+#include <vlib/main.h>
+#include <vlib/node.h>
 
 /** \file
     vlib buffer access methods.
@@ -1130,131 +1134,141 @@ vlib_validate_buffer_set_in_use (vlib_buffer_t * b, u32 expected)
 #endif
 }
 
-/** minimum data size of first buffer in a buffer chain */
-#define VLIB_BUFFER_CHAIN_MIN_FIRST_DATA_SIZE (256)
+always_inline u32
+vlib_buffer_space_left_at_end (vlib_main_t * vm, vlib_buffer_t * b)
+{
+  return b->data + VLIB_BUFFER_DATA_SIZE -
+    ((u8 *) vlib_buffer_get_current (b) + b->current_length);
+}
 
-/**
- * @brief compress buffer chain in a way where the first buffer is at least
- * VLIB_BUFFER_CHAIN_MIN_FIRST_DATA_SIZE long
- *
- * @param[in] vm - vlib_main
- * @param[in,out] first - first buffer in chain
- * @param[in,out] discard_vector - vector of buffer indexes which were removed
- * from the chain
- */
-always_inline void
-vlib_buffer_chain_compress (vlib_main_t * vm,
-			    vlib_buffer_t * first, u32 ** discard_vector)
+always_inline u32
+vlib_buffer_chain_linearize (vlib_main_t * vm, vlib_buffer_t * b)
 {
-  if (first->current_length >= VLIB_BUFFER_CHAIN_MIN_FIRST_DATA_SIZE ||
-      !(first->flags & VLIB_BUFFER_NEXT_PRESENT))
+  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;
+
+  if (PREDICT_TRUE ((b->flags & VLIB_BUFFER_NEXT_PRESENT) == 0))
+    return 1;
+
+  data_size = VLIB_BUFFER_DATA_SIZE;
+
+  dst_left = vlib_buffer_space_left_at_end (vm, b);
+
+  while (b->flags & VLIB_BUFFER_NEXT_PRESENT)
     {
-      /* this is already big enough or not a chain */
-      return;
+      b = vlib_get_buffer (vm, b->next_buffer);
+      if (b->n_add_refs > 0)
+	is_cloned = 1;
+      bytes_left += b->current_length;
+      n_buffers++;
     }
-  /* probe free list to find allocated buffer size to avoid overfill */
-  vlib_buffer_free_list_index_t index;
-  vlib_buffer_free_list_t *free_list =
-    vlib_buffer_get_buffer_free_list (vm, first, &index);
-
-  u32 want_first_size = clib_min (VLIB_BUFFER_CHAIN_MIN_FIRST_DATA_SIZE,
-				  free_list->n_data_bytes -
-				  first->current_data);
-  do
+
+  /* if buffer is cloned, create completely new chain - unless everything fits
+   * into one buffer */
+  if (is_cloned && bytes_left >= dst_left)
     {
-      vlib_buffer_t *second = vlib_get_buffer (vm, first->next_buffer);
-      u32 need = want_first_size - first->current_length;
-      u32 amount_to_copy = clib_min (need, second->current_length);
-      clib_memcpy_fast (((u8 *) vlib_buffer_get_current (first)) +
-			first->current_length,
-			vlib_buffer_get_current (second), amount_to_copy);
-      first->current_length += amount_to_copy;
-      second->current_data += amount_to_copy;
-      second->current_length -= amount_to_copy;
-      if (first->flags & VLIB_BUFFER_TOTAL_LENGTH_VALID)
-	{
-	  first->total_length_not_including_first_buffer -= amount_to_copy;
-	}
-      if (!second->current_length)
+      u32 len = 0;
+      u32 space_needed = bytes_left - dst_left;
+      u32 tail;
+
+      if (vlib_buffer_alloc (vm, &tail, 1) == 0)
+	return 0;
+
+      ++n_buffers;
+      len += data_size;
+      b = vlib_get_buffer (vm, tail);
+
+      while (len < space_needed)
 	{
-	  vec_add1 (*discard_vector, first->next_buffer);
-	  if (second->flags & VLIB_BUFFER_NEXT_PRESENT)
+	  u32 bi;
+	  if (vlib_buffer_alloc (vm, &bi, 1) == 0)
 	    {
-	      first->next_buffer = second->next_buffer;
+	      vlib_buffer_free_one (vm, tail);
+	      return 0;
 	    }
-	  else
-	    {
-	      first->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
-	    }
-	  second->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
+	  b->flags = VLIB_BUFFER_NEXT_PRESENT;
+	  b->next_buffer = bi;
+	  b = vlib_get_buffer (vm, bi);
+	  len += data_size;
+	  n_buffers++;
 	}
+      sb = vlib_get_buffer (vm, first->next_buffer);
+      to_free = first->next_buffer;
+      first->next_buffer = tail;
     }
-  while ((first->current_length < want_first_size) &&
-	 (first->flags & VLIB_BUFFER_NEXT_PRESENT));
-}
+  else
+    sb = vlib_get_buffer (vm, first->next_buffer);
 
-/**
- * @brief linearize buffer chain - the first buffer is filled, if needed,
- * buffers are allocated and filled, returns free space in last buffer or
- * negative on failure
- *
- * @param[in] vm - vlib_main
- * @param[in,out] first - first buffer in chain
- */
-always_inline int
-vlib_buffer_chain_linearize (vlib_main_t * vm, vlib_buffer_t * first)
-{
-  vlib_buffer_t *b = first;
-  vlib_buffer_free_list_t *fl =
-    vlib_buffer_get_free_list (vm, vlib_buffer_get_free_list_index (b));
-  u32 buf_len = fl->n_data_bytes;
-  // free buffer chain starting from the second buffer
-  int free_count = (b->flags & VLIB_BUFFER_NEXT_PRESENT) != 0;
-  u32 chain_to_free = b->next_buffer;
-
-  u32 len = vlib_buffer_length_in_chain (vm, b);
-  u32 free_len = buf_len - b->current_data - b->current_length;
-  int alloc_len = clib_max (len - free_len, 0);	//use the free len in the first buffer
-  int n_buffers = (alloc_len + buf_len - 1) / buf_len;
-  u32 new_buffers[n_buffers];
+  src_left = sb->current_length;
+  sp = vlib_buffer_get_current (sb);
+  dp = vlib_buffer_get_tail (db);
 
-  u32 n_alloc = vlib_buffer_alloc (vm, new_buffers, n_buffers);
-  if (n_alloc != n_buffers)
+  while (bytes_left)
     {
-      vlib_buffer_free_no_next (vm, new_buffers, n_alloc);
-      return -1;
+      u16 bytes_to_copy;
+
+      if (dst_left == 0)
+	{
+	  if (db != first)
+	    db->current_data = 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;
+	  dp = db->data;
+	}
+
+      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);
+	}
+
+      bytes_to_copy = clib_min (dst_left, src_left);
+
+      if (dp != sp)
+	{
+	  if (sb == db)
+	    bytes_to_copy = clib_min (bytes_to_copy, sp - dp);
+
+	  clib_memcpy_fast (dp, sp, bytes_to_copy);
+	}
+
+      src_left -= bytes_to_copy;
+      dst_left -= bytes_to_copy;
+      dp += bytes_to_copy;
+      sp += bytes_to_copy;
+      bytes_left -= bytes_to_copy;
     }
+  if (db != first)
+    db->current_data = 0;
+  db->current_length = dp - (u8 *) vlib_buffer_get_current (db);
 
-  vlib_buffer_t *s = b;
-  while (s->flags & VLIB_BUFFER_NEXT_PRESENT)
+  if (is_cloned && to_free)
+    vlib_buffer_free_one (vm, to_free);
+  else
     {
-      s = vlib_get_buffer (vm, s->next_buffer);
-      int d_free_len = buf_len - b->current_data - b->current_length;
-      ASSERT (d_free_len >= 0);
-      // chain buf and split write
-      u32 copy_len = clib_min (d_free_len, s->current_length);
-      u8 *d = vlib_buffer_put_uninit (b, copy_len);
-      clib_memcpy (d, vlib_buffer_get_current (s), copy_len);
-      int rest = s->current_length - copy_len;
-      if (rest > 0)
+      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)
 	{
-	  //prev buf is full
-	  ASSERT (vlib_buffer_get_tail (b) == b->data + buf_len);
-	  ASSERT (n_buffers > 0);
-	  b = vlib_buffer_chain_buffer (vm, b, new_buffers[--n_buffers]);
-	  //make full use of the new buffers
-	  b->current_data = 0;
-	  d = vlib_buffer_put_uninit (b, rest);
-	  clib_memcpy (d, vlib_buffer_get_current (s) + copy_len, rest);
+	  b = vlib_get_buffer (vm, b->next_buffer);
+	  ++n_buffers;
 	}
     }
-  vlib_buffer_free (vm, &chain_to_free, free_count);
-  b->flags &= ~VLIB_BUFFER_TOTAL_LENGTH_VALID;
-  if (b == first)		/* no buffers addeed */
-    b->flags &= ~VLIB_BUFFER_NEXT_PRESENT;
-  ASSERT (len == vlib_buffer_length_in_chain (vm, first));
-  ASSERT (n_buffers == 0);
-  return buf_len - b->current_data - b->current_length;
+
+  first->flags &= ~VLIB_BUFFER_TOTAL_LENGTH_VALID;
+
+  return n_buffers;
 }
 
 #endif /* included_vlib_buffer_funcs_h */
diff --git a/src/vlib/physmem_funcs.h b/src/vlib/physmem_funcs.h
index 18daeebabd9..d93bae8fbe5 100644
--- a/src/vlib/physmem_funcs.h
+++ b/src/vlib/physmem_funcs.h
@@ -40,6 +40,11 @@
 #ifndef included_vlib_physmem_funcs_h
 #define included_vlib_physmem_funcs_h
 
+#include <vppinfra/clib.h>
+#include <vppinfra/clib_error.h>
+#include <vlib/physmem.h>
+#include <vlib/main.h>
+
 clib_error_t *vlib_physmem_init (vlib_main_t * vm);
 clib_error_t *vlib_physmem_shared_map_create (vlib_main_t * vm, char *name,
 					      uword size, u32 log2_page_sz,