vppinfra: use heap to store bihash data

Type: improvement
Change-Id: Ifb0fa114414aa2fdc244f964612ca3ac3e29b5e1
Signed-off-by: Damjan Marion <damarion@cisco.com>

7 files changed, 196 insertions, 25 deletions

diff --git a/src/vppinfra/bihash_16_8.h b/src/vppinfra/bihash_16_8.h
index 1815a526ce6..6b116bcf3e4 100644
--- a/src/vppinfra/bihash_16_8.h
+++ b/src/vppinfra/bihash_16_8.h
@@ -19,12 +19,14 @@
 #undef BIHASH_KVP_AT_BUCKET_LEVEL
 #undef BIHASH_LAZY_INSTANTIATE
 #undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
+#undef BIHASH_USE_HEAP
 
 #define BIHASH_TYPE _16_8
 #define BIHASH_KVP_PER_PAGE 4
 #define BIHASH_KVP_AT_BUCKET_LEVEL 1
 #define BIHASH_LAZY_INSTANTIATE 0
 #define BIHASH_BUCKET_PREFETCH_CACHE_LINES 2
+#define BIHASH_USE_HEAP 1
 
 #ifndef __included_bihash_16_8_h__
 #define __included_bihash_16_8_h__
diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h
index 33199bfcef4..2d667ad9aa3 100644
--- a/src/vppinfra/bihash_24_8.h
+++ b/src/vppinfra/bihash_24_8.h
@@ -19,12 +19,14 @@
 #undef BIHASH_KVP_AT_BUCKET_LEVEL
 #undef BIHASH_LAZY_INSTANTIATE
 #undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
+#undef BIHASH_USE_HEAP
 
 #define BIHASH_TYPE _24_8
 #define BIHASH_KVP_PER_PAGE 4
 #define BIHASH_KVP_AT_BUCKET_LEVEL 0
 #define BIHASH_LAZY_INSTANTIATE 1
 #define BIHASH_BUCKET_PREFETCH_CACHE_LINES 1
+#define BIHASH_USE_HEAP 1
 
 #ifndef __included_bihash_24_8_h__
 #define __included_bihash_24_8_h__
diff --git a/src/vppinfra/bihash_40_8.h b/src/vppinfra/bihash_40_8.h
index 9cd2371afa7..1fb344fdeeb 100644
--- a/src/vppinfra/bihash_40_8.h
+++ b/src/vppinfra/bihash_40_8.h
@@ -20,12 +20,14 @@
 #undef BIHASH_KVP_AT_BUCKET_LEVEL
 #undef BIHASH_LAZY_INSTANTIATE
 #undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
+#undef BIHASH_USE_HEAP
 
 #define BIHASH_TYPE _40_8
 #define BIHASH_KVP_PER_PAGE 4
 #define BIHASH_KVP_AT_BUCKET_LEVEL 0
 #define BIHASH_LAZY_INSTANTIATE 1
 #define BIHASH_BUCKET_PREFETCH_CACHE_LINES 1
+#define BIHASH_USE_HEAP 1
 
 #ifndef __included_bihash_40_8_h__
 #define __included_bihash_40_8_h__
diff --git a/src/vppinfra/bihash_8_8.h b/src/vppinfra/bihash_8_8.h
index 234890752a5..2fdd2ed7aef 100644
--- a/src/vppinfra/bihash_8_8.h
+++ b/src/vppinfra/bihash_8_8.h
@@ -19,12 +19,14 @@
 #undef BIHASH_KVP_AT_BUCKET_LEVEL
 #undef BIHASH_LAZY_INSTANTIATE
 #undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
+#undef BIHASH_USE_HEAP
 
 #define BIHASH_TYPE _8_8
 #define BIHASH_KVP_PER_PAGE 7
 #define BIHASH_KVP_AT_BUCKET_LEVEL 1
 #define BIHASH_LAZY_INSTANTIATE 0
 #define BIHASH_BUCKET_PREFETCH_CACHE_LINES 2
+#define BIHASH_USE_HEAP 1
 
 #ifndef __included_bihash_8_8_h__
 #define __included_bihash_8_8_h__
diff --git a/src/vppinfra/bihash_8_8_stats.h b/src/vppinfra/bihash_8_8_stats.h
index 5aceb1bdc81..2237a0d624f 100644
--- a/src/vppinfra/bihash_8_8_stats.h
+++ b/src/vppinfra/bihash_8_8_stats.h
@@ -19,6 +19,7 @@
 #undef BIHASH_KVP_AT_BUCKET_LEVEL
 #undef BIHASH_LAZY_INSTANTIATE
 #undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
+#undef BIHASH_USE_HEAP
 
 #define BIHASH_TYPE _8_8_stats
 #define BIHASH_KVP_PER_PAGE 4
@@ -26,6 +27,7 @@
 #define BIHASH_KVP_AT_BUCKET_LEVEL 0
 #define BIHASH_LAZY_INSTANTIATE 1
 #define BIHASH_BUCKET_PREFETCH_CACHE_LINES 1
+#define BIHASH_USE_HEAP 1
 
 #ifndef __included_bihash_8_8_stats_h__
 #define __included_bihash_8_8__stats_h__
diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c
index aac66cbf53b..e408d157da7 100644
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -19,13 +19,77 @@
 #define MAP_HUGE_SHIFT 26
 #endif
 
+#ifndef BIIHASH_MIN_ALLOC_LOG2_PAGES
+#define BIIHASH_MIN_ALLOC_LOG2_PAGES 10
+#endif
+
 static inline void *BV (alloc_aligned) (BVT (clib_bihash) * h, uword nbytes)
 {
   uword rv;
 
   /* Round to an even number of cache lines */
-  nbytes += CLIB_CACHE_LINE_BYTES - 1;
-  nbytes &= ~(CLIB_CACHE_LINE_BYTES - 1);
+  nbytes = round_pow2 (nbytes, CLIB_CACHE_LINE_BYTES);
+
+  if (BIHASH_USE_HEAP)
+    {
+      void *rv, *oldheap;
+      uword page_sz = sizeof (BVT (clib_bihash_value));
+      uword chunk_sz = round_pow2 (page_sz << BIIHASH_MIN_ALLOC_LOG2_PAGES,
+				   CLIB_CACHE_LINE_BYTES);
+
+      BVT (clib_bihash_alloc_chunk) * chunk = h->chunks;
+
+      /* if there is enough space in the currenrt chunk */
+      if (chunk && chunk->bytes_left >= nbytes)
+	{
+	  rv = chunk->next_alloc;
+	  chunk->bytes_left -= nbytes;
+	  chunk->next_alloc += nbytes;
+	  return rv;
+	}
+
+      /* requested allocation is bigger than chunk size */
+      if (nbytes >= chunk_sz)
+	{
+	  oldheap = clib_mem_set_heap (h->heap);
+	  chunk = clib_mem_alloc_aligned (nbytes + sizeof (*chunk),
+					  CLIB_CACHE_LINE_BYTES);
+	  clib_mem_set_heap (oldheap);
+	  clib_memset_u8 (chunk, 0, sizeof (*chunk));
+	  chunk->size = nbytes;
+	  rv = (u8 *) (chunk + 1);
+	  if (h->chunks)
+	    {
+	      /* take 2nd place in the list */
+	      chunk->next = h->chunks->next;
+	      chunk->prev = h->chunks;
+	      h->chunks->next = chunk;
+	      if (chunk->next)
+		chunk->next->prev = chunk;
+	    }
+	  else
+	    h->chunks = chunk;
+
+	  return rv;
+	}
+
+      oldheap = clib_mem_set_heap (h->heap);
+      chunk = clib_mem_alloc_aligned (chunk_sz + sizeof (*chunk),
+				      CLIB_CACHE_LINE_BYTES);
+      clib_mem_set_heap (oldheap);
+      chunk->size = chunk_sz;
+      chunk->bytes_left = chunk_sz;
+      chunk->next_alloc = (u8 *) (chunk + 1);
+      chunk->next = h->chunks;
+      chunk->prev = 0;
+      if (chunk->next)
+	chunk->next->prev = chunk;
+      h->chunks = chunk;
+      rv = chunk->next_alloc;
+      chunk->bytes_left -= nbytes;
+      chunk->next_alloc += nbytes;
+      return rv;
+    }
 
   rv = alloc_arena_next (h);
   alloc_arena_next (h) += nbytes;
@@ -69,13 +133,22 @@ static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h)
 {
   uword bucket_size;
 
-  alloc_arena (h) = clib_mem_vm_reserve (0, h->memory_size,
-					 BIHASH_LOG2_HUGEPAGE_SIZE);
-  if (alloc_arena (h) == ~0)
-    os_out_of_memory ();
-  alloc_arena_next (h) = 0;
-  alloc_arena_size (h) = h->memory_size;
-  alloc_arena_mapped (h) = 0;
+  if (BIHASH_USE_HEAP)
+    {
+      h->heap = clib_mem_get_heap ();
+      h->chunks = 0;
+      alloc_arena (h) = (uword) clib_mem_get_heap_base (h->heap);
+    }
+  else
+    {
+      alloc_arena (h) = clib_mem_vm_reserve (0, h->memory_size,
+					     BIHASH_LOG2_HUGEPAGE_SIZE);
+      if (alloc_arena (h) == ~0)
+	os_out_of_memory ();
+      alloc_arena_next (h) = 0;
+      alloc_arena_size (h) = h->memory_size;
+      alloc_arena_mapped (h) = 0;
+    }
 
   bucket_size = h->nbuckets * sizeof (h->buckets[0]);
 
@@ -84,6 +157,7 @@ static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h)
       h->nbuckets * BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv));
 
   h->buckets = BV (alloc_aligned) (h, bucket_size);
+  clib_memset_u8 (h->buckets, 0, bucket_size);
 
   if (BIHASH_KVP_AT_BUCKET_LEVEL)
     {
@@ -97,8 +171,8 @@ static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h)
 	  b->offset = BV (clib_bihash_get_offset) (h, (void *) (b + 1));
 	  b->refcnt = 1;
 	  /* Mark all elements free */
-	  clib_memset ((b + 1), 0xff,
-		       BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv)));
+	  clib_memset_u8 ((b + 1), 0xff, BIHASH_KVP_PER_PAGE *
+			  sizeof (BVT (clib_bihash_kv)));
 
 	  /* Compute next bucket start address */
 	  b = (void *) (((uword) b) + sizeof (*b) +
@@ -121,7 +195,7 @@ void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a)
   h->name = (u8 *) a->name;
   h->nbuckets = a->nbuckets;
   h->log2_nbuckets = max_log2 (a->nbuckets);
-  h->memory_size = a->memory_size;
+  h->memory_size = BIHASH_USE_HEAP ? 0 : a->memory_size;
   h->instantiated = 0;
   h->fmt_fn = a->fmt_fn;
 
@@ -133,7 +207,8 @@ void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a)
    * If someone starts complaining that's not enough, we can shift
    * the offset by CLIB_LOG2_CACHE_LINE_BYTES...
    */
-  ASSERT (h->memory_size < (1ULL << BIHASH_BUCKET_OFFSET_BITS));
+  if (BIHASH_USE_HEAP)
+    ASSERT (h->memory_size < (1ULL << BIHASH_BUCKET_OFFSET_BITS));
 
   /* Add this hash table to the list */
   if (a->dont_add_to_all_bihash_list == 0)
@@ -192,6 +267,8 @@ void BV (clib_bihash_initiator_init_svm)
   vec_header_t *freelist_vh;
   int fd;
 
+  ASSERT (BIHASH_USE_HEAP == 0);
+
   ASSERT (memory_size < (1ULL << 32));
   /* Set up for memfd sharing */
   if ((fd = memfd_create (name, MFD_ALLOW_SEALING)) == -1)
@@ -233,6 +310,7 @@ void BV (clib_bihash_initiator_init_svm)
 
   bucket_size = nbuckets * sizeof (h->buckets[0]);
   h->buckets = BV (alloc_aligned) (h, bucket_size);
+  clib_memset_u8 (h->buckets, 0, bucket_size);
   h->sh->buckets_as_u64 = (u64) BV (clib_bihash_get_offset) (h, h->buckets);
 
   h->alloc_lock = BV (alloc_aligned) (h, CLIB_CACHE_LINE_BYTES);
@@ -260,6 +338,8 @@ void BV (clib_bihash_responder_init_svm)
   u64 memory_size;
   BVT (clib_bihash_shared_header) * sh;
 
+  ASSERT (BIHASH_USE_HEAP == 0);
+
   /* Trial mapping, to learn the segment size */
   mmap_addr = mmap (0, 4096, PROT_READ, MAP_SHARED, fd, 0 /* offset */ );
   if (mmap_addr == MAP_FAILED)
@@ -315,6 +395,22 @@ void BV (clib_bihash_free) (BVT (clib_bihash) * h)
     goto never_initialized;
 
   h->instantiated = 0;
+
+  if (BIHASH_USE_HEAP)
+    {
+      BVT (clib_bihash_alloc_chunk) * next, *chunk;
+      void *oldheap = clib_mem_set_heap (h->heap);
+
+      chunk = h->chunks;
+      while (chunk)
+	{
+	  next = chunk->next;
+	  clib_mem_free (chunk);
+	  chunk = next;
+	}
+      clib_mem_set_heap (oldheap);
+    }
+
   vec_free (h->working_copies);
   vec_free (h->working_copy_lengths);
 #if BIHASH_32_64_SVM == 0
@@ -323,9 +419,11 @@ void BV (clib_bihash_free) (BVT (clib_bihash) * h)
   if (h->memfd > 0)
     (void) close (h->memfd);
 #endif
-  clib_mem_vm_free ((void *) (uword) (alloc_arena (h)), alloc_arena_size (h));
+  if (BIHASH_USE_HEAP == 0)
+    clib_mem_vm_free ((void *) (uword) (alloc_arena (h)),
+		      alloc_arena_size (h));
 never_initialized:
-  clib_memset (h, 0, sizeof (*h));
+  clib_memset_u8 (h, 0, sizeof (*h));
   for (i = 0; i < vec_len (clib_all_bihashes); i++)
     {
       if ((void *) h == clib_all_bihashes[i])
@@ -366,7 +464,7 @@ initialize:
    * if we replace (1<<log2_pages) with vec_len(rv).
    * No clue.
    */
-  clib_memset (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
+  clib_memset_u8 (rv, 0xff, sizeof (*rv) * (1 << log2_pages));
   return rv;
 }
 
@@ -378,8 +476,30 @@ BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
 
   ASSERT (vec_len (h->freelists) > log2_pages);
 
+  if (BIHASH_USE_HEAP && log2_pages >= BIIHASH_MIN_ALLOC_LOG2_PAGES)
+    {
+      /* allocations bigger or equal to chunk size always contain single
+       * alloc and they can be given back to heap */
+      void *oldheap;
+      BVT (clib_bihash_alloc_chunk) * c;
+      c = (BVT (clib_bihash_alloc_chunk) *) v - 1;
+
+      if (c->prev)
+	c->prev->next = c->next;
+      else
+	h->chunks = c->next;
+
+      if (c->next)
+	c->next->prev = c->prev;
+
+      oldheap = clib_mem_set_heap (h->heap);
+      clib_mem_free (c);
+      clib_mem_set_heap (oldheap);
+      return;
+    }
+
   if (CLIB_DEBUG > 0)
-    clib_memset (v, 0xFE, sizeof (*v) * (1 << log2_pages));
+    clib_memset_u8 (v, 0xFE, sizeof (*v) * (1 << log2_pages));
 
   v->next_free_as_u64 = (u64) h->freelists[log2_pages];
   h->freelists[log2_pages] = (u64) BV (clib_bihash_get_offset) (h, v);
@@ -888,7 +1008,6 @@ u8 *BV (format_bihash) (u8 * s, va_list * args)
   u64 active_elements = 0;
   u64 active_buckets = 0;
   u64 linear_buckets = 0;
-  u64 used_bytes;
 
   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 
@@ -974,13 +1093,34 @@ u8 *BV (format_bihash) (u8 * s, va_list * args)
     }
 
   s = format (s, "    %lld linear search buckets\n", linear_buckets);
-  used_bytes = alloc_arena_next (h);
-  s = format (s,
-	      "    arena: base %llx, next %llx\n"
-	      "           used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
-	      alloc_arena (h), alloc_arena_next (h),
-	      used_bytes, used_bytes >> 20,
-	      alloc_arena_size (h), alloc_arena_size (h) >> 20);
+  if (BIHASH_USE_HEAP)
+    {
+      BVT (clib_bihash_alloc_chunk) * c = h->chunks;
+      uword bytes_left = 0, total_size = 0, n_chunks = 0;
+
+      while (c)
+	{
+	  bytes_left += c->bytes_left;
+	  total_size += c->size;
+	  n_chunks += 1;
+	  c = c->next;
+	}
+      s = format (s,
+		  "    heap: %u chunks allocated\n"
+		  "          used %UB, scrap %UB\n", n_chunks,
+		  format_memory_size, total_size,
+		  format_memory_size, bytes_left);
+    }
+  else
+    {
+      u64 used_bytes = alloc_arena_next (h);
+      s = format (s,
+		  "    arena: base %llx, next %llx\n"
+		  "           used %lld b (%lld Mbytes) of %lld b (%lld Mbytes)\n",
+		  alloc_arena (h), alloc_arena_next (h),
+		  used_bytes, used_bytes >> 20,
+		  alloc_arena_size (h), alloc_arena_size (h) >> 20);
+    }
   return s;
 }
 
diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index d6aa3c9f6ef..a6990ff5999 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -124,6 +124,25 @@ typedef CLIB_PACKED (struct {
 STATIC_ASSERT_SIZEOF (BVT (clib_bihash_shared_header), 8 * sizeof (u64));
 
 typedef
+BVS (clib_bihash_alloc_chunk)
+{
+  CLIB_CACHE_LINE_ALIGN_MARK (cacheline0);
+
+  /* chunk size */
+  uword size;
+
+  /* pointer to the next allocation */
+  u8 *next_alloc;
+
+  /* number of bytes left in this chunk */
+  uword bytes_left;
+
+  /* doubly linked list of heap allocated chunks */
+  BVS (clib_bihash_alloc_chunk) * prev, *next;
+
+} BVT (clib_bihash_alloc_chunk);
+
+typedef
 BVS (clib_bihash)
 {
   BVT (clib_bihash_bucket) * buckets;
@@ -137,6 +156,8 @@ BVS (clib_bihash)
   u32 log2_nbuckets;
   u64 memory_size;
   u8 *name;
+  void *heap;
+  BVT (clib_bihash_alloc_chunk) * chunks;
 
   u64 *freelists;