vppinfra: bihash improvements

Template instances can allocate BIHASH_KVP_PER_PAGE data records
tangent to the bucket, to remove a dependent read / prefetch.

Template instances can ask for immediate memory allocation, to avoid
several branches in the lookup path.

Clean up l2 fib, gpb plugin codes: use clib_bihash_get_bucket(...)

Use hugepages for bihash allocation arenas

Type: improvement

Signed-off-by: Dave Barach <dave@barachs.net>
Signed-off-by: Damjan Marion <damarion@cisco.com>
Change-Id: I92fc11bc58e48d84e2d61f44580916dd1c56361c

diff --git a/src/plugins/gbp/gbp_endpoint.c b/src/plugins/gbp/gbp_endpoint.c
index 9ef0890..e1a810c 100644 (file)
--- a/src/plugins/gbp/gbp_endpoint.c
+++ b/src/plugins/gbp/gbp_endpoint.c
@@ -1398,8 +1398,8 @@ gbp_endpoint_scan_l2 (vlib_main_t * vm)
          last_start = vlib_time_now (vm);
        }
 
-      b = &gte_table->buckets[i];
-      if (b->offset == 0)
+      b = clib_bihash_get_bucket_16_8 (gte_table, i);
+      if (clib_bihash_bucket_is_empty_16_8 (b))
        continue;
       v = clib_bihash_get_value_16_8 (gte_table, b->offset);
 
@@ -1416,7 +1416,7 @@ gbp_endpoint_scan_l2 (vlib_main_t * vm)
               * Note: we may have just freed the bucket's backing
               * storage, so check right here...
               */
-             if (b->offset == 0)
+             if (clib_bihash_bucket_is_empty_16_8 (b))
                goto doublebreak;
            }
          v++;
@@ -1453,8 +1453,8 @@ gbp_endpoint_scan_l3 (vlib_main_t * vm)
          last_start = vlib_time_now (vm);
        }
 
-      b = &gte_table->buckets[i];
-      if (b->offset == 0)
+      b = clib_bihash_get_bucket_24_8 (gte_table, i);
+      if (clib_bihash_bucket_is_empty_24_8 (b))
        continue;
       v = clib_bihash_get_value_24_8 (gte_table, b->offset);
 
@@ -1471,7 +1471,7 @@ gbp_endpoint_scan_l3 (vlib_main_t * vm)
               * Note: we may have just freed the bucket's backing
               * storage, so check right here...
               */
-             if (b->offset == 0)
+             if (clib_bihash_bucket_is_empty_24_8 (b))
                goto doublebreak;
            }
          v++;

diff --git a/src/vnet/l2/l2_fib.c b/src/vnet/l2/l2_fib.c
index 160e4e6..983e021 100644 (file)
--- a/src/vnet/l2/l2_fib.c
+++ b/src/vnet/l2/l2_fib.c
@@ -1028,10 +1028,11 @@ l2fib_scan (vlib_main_t * vm, f64 start_time, u8 event_only)
 
       if (i < (h->nbuckets - 3))
        {
-         BVT (clib_bihash_bucket) * b = &h->buckets[i + 3];
+         BVT (clib_bihash_bucket) * b =
+           BV (clib_bihash_get_bucket) (h, i + 3);
          CLIB_PREFETCH (b, CLIB_CACHE_LINE_BYTES, LOAD);
-         b = &h->buckets[i + 1];
-         if (b->offset)
+         b = BV (clib_bihash_get_bucket) (h, i + 1);
+         if (!BV (clib_bihash_bucket_is_empty) (b))
            {
              BVT (clib_bihash_value) * v =
                BV (clib_bihash_get_value) (h, b->offset);
@@ -1039,8 +1040,8 @@ l2fib_scan (vlib_main_t * vm, f64 start_time, u8 event_only)
            }
        }
 
-      BVT (clib_bihash_bucket) * b = &h->buckets[i];
-      if (b->offset == 0)
+      BVT (clib_bihash_bucket) * b = BV (clib_bihash_get_bucket) (h, i);
+      if (BV (clib_bihash_bucket_is_empty) (b))
        continue;
       BVT (clib_bihash_value) * v = BV (clib_bihash_get_value) (h, b->offset);
       for (j = 0; j < (1 << b->log2_pages); j++)
@@ -1146,7 +1147,7 @@ l2fib_scan (vlib_main_t * vm, f64 start_time, u8 event_only)
               * Note: we may have just freed the bucket's backing
               * storage, so check right here...
               */
-             if (b->offset == 0)
+             if (BV (clib_bihash_bucket_is_empty) (b))
                goto doublebreak;
            }
          v++;

diff --git a/src/vppinfra/bihash_16_8.h b/src/vppinfra/bihash_16_8.h
index b6b0766..1815a52 100644 (file)
--- a/src/vppinfra/bihash_16_8.h
+++ b/src/vppinfra/bihash_16_8.h
@@ -16,9 +16,15 @@
 #undef BIHASH_KVP_PER_PAGE
 #undef BIHASH_32_64_SVM
 #undef BIHASH_ENABLE_STATS
+#undef BIHASH_KVP_AT_BUCKET_LEVEL
+#undef BIHASH_LAZY_INSTANTIATE
+#undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
 
 #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
 
 #ifndef __included_bihash_16_8_h__
 #define __included_bihash_16_8_h__

diff --git a/src/vppinfra/bihash_16_8_32.h b/src/vppinfra/bihash_16_8_32.h
index e66954f..9453f88 100644 (file)
--- a/src/vppinfra/bihash_16_8_32.h
+++ b/src/vppinfra/bihash_16_8_32.h
@@ -16,10 +16,15 @@
 #undef BIHASH_KVP_PER_PAGE
 #undef BIHASH_32_64_SVM
 #undef BIHASH_ENABLE_STATS
-
+#undef BIHASH_KVP_AT_BUCKET_LEVEL
+#undef BIHASH_LAZY_INSTANTIATE
+#undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
 
 #define BIHASH_TYPE _16_8_32
 #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_32_64_SVM 1
 

diff --git a/src/vppinfra/bihash_24_8.h b/src/vppinfra/bihash_24_8.h
index 463521d..33199bf 100644 (file)
--- a/src/vppinfra/bihash_24_8.h
+++ b/src/vppinfra/bihash_24_8.h
@@ -16,9 +16,15 @@
 #undef BIHASH_KVP_PER_PAGE
 #undef BIHASH_32_64_SVM
 #undef BIHASH_ENABLE_STATS
+#undef BIHASH_KVP_AT_BUCKET_LEVEL
+#undef BIHASH_LAZY_INSTANTIATE
+#undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
 
 #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
 
 #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 b50e5eb..9cd2371 100644 (file)
--- a/src/vppinfra/bihash_40_8.h
+++ b/src/vppinfra/bihash_40_8.h
@@ -17,9 +17,15 @@
 #undef BIHASH_KVP_PER_PAGE
 #undef BIHASH_32_64_SVM
 #undef BIHASH_ENABLE_STATS
+#undef BIHASH_KVP_AT_BUCKET_LEVEL
+#undef BIHASH_LAZY_INSTANTIATE
+#undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
 
 #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
 
 #ifndef __included_bihash_40_8_h__
 #define __included_bihash_40_8_h__

diff --git a/src/vppinfra/bihash_48_8.h b/src/vppinfra/bihash_48_8.h
index 2a6381f..54fd709 100644 (file)
--- a/src/vppinfra/bihash_48_8.h
+++ b/src/vppinfra/bihash_48_8.h
@@ -17,9 +17,15 @@
 #undef BIHASH_KVP_PER_PAGE
 #undef BIHASH_32_64_SVM
 #undef BIHASH_ENABLE_STATS
+#undef BIHASH_KVP_AT_BUCKET_LEVEL
+#undef BIHASH_LAZY_INSTANTIATE
+#undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
 
 #define BIHASH_TYPE _48_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
 
 #ifndef __included_bihash_48_8_h__
 #define __included_bihash_48_8_h__

diff --git a/src/vppinfra/bihash_8_8.h b/src/vppinfra/bihash_8_8.h
index a4a18a1..2348907 100644 (file)
--- a/src/vppinfra/bihash_8_8.h
+++ b/src/vppinfra/bihash_8_8.h
@@ -16,9 +16,15 @@
 #undef BIHASH_KVP_PER_PAGE
 #undef BIHASH_32_64_SVM
 #undef BIHASH_ENABLE_STATS
+#undef BIHASH_KVP_AT_BUCKET_LEVEL
+#undef BIHASH_LAZY_INSTANTIATE
+#undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
 
 #define BIHASH_TYPE _8_8
-#define BIHASH_KVP_PER_PAGE 4
+#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
 
 #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 a6c947a..5aceb1b 100644 (file)
--- a/src/vppinfra/bihash_8_8_stats.h
+++ b/src/vppinfra/bihash_8_8_stats.h
@@ -16,10 +16,16 @@
 #undef BIHASH_KVP_PER_PAGE
 #undef BIHASH_32_64_SVM
 #undef BIHASH_ENABLE_STATS
+#undef BIHASH_KVP_AT_BUCKET_LEVEL
+#undef BIHASH_LAZY_INSTANTIATE
+#undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
 
 #define BIHASH_TYPE _8_8_stats
 #define BIHASH_KVP_PER_PAGE 4
 #define BIHASH_ENABLE_STATS 1
+#define BIHASH_KVP_AT_BUCKET_LEVEL 0
+#define BIHASH_LAZY_INSTANTIATE 1
+#define BIHASH_BUCKET_PREFETCH_CACHE_LINES 1
 
 #ifndef __included_bihash_8_8_stats_h__
 #define __included_bihash_8_8__stats_h__

diff --git a/src/vppinfra/bihash_doc.h b/src/vppinfra/bihash_doc.h
index da8c832..b4b6a4a 100644 (file)
--- a/src/vppinfra/bihash_doc.h
+++ b/src/vppinfra/bihash_doc.h
@@ -81,6 +81,7 @@ typedef struct
   uword alloc_arena;                 /**< memory allocation arena  */
   uword alloc_arena_next;            /**< first available mem chunk */
   uword alloc_arena_size;            /**< size of the arena */
+  uword alloc_arena_mapped;          /**< size of mapped memory in the arena */
 } clib_bihash_t;
 
 /** Get pointer to value page given its clib mheap offset */

diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c
index 471251d..89bfc8b 100644 (file)
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -15,6 +15,10 @@
 
 /** @cond DOCUMENTATION_IS_IN_BIHASH_DOC_H */
 
+#ifndef MAP_HUGE_SHIFT
+#define MAP_HUGE_SHIFT 26
+#endif
+
 static inline void *BV (alloc_aligned) (BVT (clib_bihash) * h, uword nbytes)
 {
   uword rv;
@@ -29,6 +33,35 @@ static inline void *BV (alloc_aligned) (BVT (clib_bihash) * h, uword nbytes)
   if (alloc_arena_next (h) > alloc_arena_size (h))
     os_out_of_memory ();
 
+  if (alloc_arena_next (h) > alloc_arena_mapped (h))
+    {
+      void *base, *rv;
+      uword alloc = alloc_arena_next (h) - alloc_arena_mapped (h);
+      int mmap_flags = MAP_FIXED | MAP_PRIVATE | MAP_ANONYMOUS;
+      int mmap_flags_huge = (mmap_flags | MAP_HUGETLB |
+                            BIHASH_LOG2_HUGEPAGE_SIZE << MAP_HUGE_SHIFT);
+
+      /* new allocation is 25% of existing one */
+      if (alloc_arena_mapped (h) >> 2 > alloc)
+       alloc = alloc_arena_mapped (h) >> 2;
+
+      /* round allocation to page size */
+      alloc = round_pow2 (alloc, 1 << BIHASH_LOG2_HUGEPAGE_SIZE);
+
+      base = (void *) (uword) (alloc_arena (h) + alloc_arena_mapped (h));
+
+      rv = mmap (base, alloc, PROT_READ | PROT_WRITE, mmap_flags_huge, -1, 0);
+
+      /* fallback - maybe we are still able to allocate normal pages */
+      if (rv == MAP_FAILED)
+       rv = mmap (base, alloc, PROT_READ | PROT_WRITE, mmap_flags, -1, 0);
+
+      if (rv == MAP_FAILED)
+       os_out_of_memory ();
+
+      alloc_arena_mapped (h) += alloc;
+    }
+
   return (void *) (uword) (rv + alloc_arena (h));
 }
 
@@ -36,12 +69,43 @@ static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h)
 {
   uword bucket_size;
 
-  alloc_arena (h) = (uword) clib_mem_vm_alloc (h->memory_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;
 
   bucket_size = h->nbuckets * sizeof (h->buckets[0]);
+
+  if (BIHASH_KVP_AT_BUCKET_LEVEL)
+    bucket_size +=
+      h->nbuckets * BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv));
+
   h->buckets = BV (alloc_aligned) (h, bucket_size);
+
+  if (BIHASH_KVP_AT_BUCKET_LEVEL)
+    {
+      int i;
+      BVT (clib_bihash_bucket) * b;
+
+      b = h->buckets;
+
+      for (i = 0; i < h->nbuckets; i++)
+       {
+         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)));
+
+         /* Compute next bucket start address */
+         b = (void *) (((uword) b) + sizeof (*b) +
+                       (BIHASH_KVP_PER_PAGE *
+                        sizeof (BVT (clib_bihash_kv))));
+       }
+    }
   CLIB_MEMORY_BARRIER ();
   h->instantiated = 1;
 }
@@ -94,7 +158,9 @@ do_lock:
                                          CLIB_CACHE_LINE_BYTES);
   h->alloc_lock[0] = 0;
 
+#if BIHASH_LAZY_INSTANTIATE
   if (a->instantiate_immediately)
+#endif
     BV (clib_bihash_instantiate) (h);
 }
 
@@ -505,7 +571,7 @@ static inline int BV (clib_bihash_add_del_inline)
   BV (clib_bihash_lock_bucket) (b);
 
   /* First elt in the bucket? */
-  if (BV (clib_bihash_bucket_is_empty) (b))
+  if (BIHASH_KVP_AT_BUCKET_LEVEL == 0 && BV (clib_bihash_bucket_is_empty) (b))
     {
       if (is_add == 0)
        {
@@ -620,6 +686,24 @@ static inline int BV (clib_bihash_add_del_inline)
              if (PREDICT_TRUE (b->refcnt > 1))
                {
                  b->refcnt--;
+                 /* Switch back to the bucket-level kvp array? */
+                 if (BIHASH_KVP_AT_BUCKET_LEVEL && b->refcnt == 1
+                     && b->log2_pages > 0)
+                   {
+                     tmp_b.as_u64 = b->as_u64;
+                     b->offset = BV (clib_bihash_get_offset)
+                       (h, (void *) (b + 1));
+                     b->linear_search = 0;
+                     b->log2_pages = 0;
+                     /* Clean up the bucket-level kvp array */
+                     clib_memset
+                       ((b + 1), 0xff,
+                        BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv)));
+                     BV (clib_bihash_unlock_bucket) (b);
+                     BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1);
+                     goto free_backing_store;
+                   }
+
                  BV (clib_bihash_unlock_bucket) (b);
                  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1);
                  return (0);
@@ -633,6 +717,7 @@ static inline int BV (clib_bihash_add_del_inline)
                  /* Kill and unlock the bucket */
                  b->as_u64 = 0;
 
+               free_backing_store:
                  /* And free the backing storage */
                  BV (clib_bihash_alloc_lock) (h);
                  /* Note: v currently points into the middle of the bucket */
@@ -726,14 +811,30 @@ expand_ok:
   tmp_b.log2_pages = new_log2_pages;
   tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v);
   tmp_b.linear_search = mark_bucket_linear;
-  tmp_b.refcnt = h->saved_bucket.refcnt + 1;
+#if BIHASH_KVP_AT_BUCKET_LEVEL
+  /* Compensate for permanent refcount bump at the bucket level */
+  if (new_log2_pages > 0)
+#endif
+    tmp_b.refcnt = h->saved_bucket.refcnt + 1;
   ASSERT (tmp_b.refcnt > 0);
   tmp_b.lock = 0;
   CLIB_MEMORY_BARRIER ();
   b->as_u64 = tmp_b.as_u64;
-  /* free the old bucket */
-  v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
-  BV (value_free) (h, v, h->saved_bucket.log2_pages);
+
+#if BIHASH_KVP_AT_BUCKET_LEVEL
+  if (h->saved_bucket.log2_pages > 0)
+    {
+#endif
+
+      /* free the old bucket, except at the bucket level if so configured */
+      v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
+      BV (value_free) (h, v, h->saved_bucket.log2_pages);
+
+#if BIHASH_KVP_AT_BUCKET_LEVEL
+    }
+#endif
+
+
   BV (clib_bihash_alloc_unlock) (h);
   return (0);
 }
@@ -762,8 +863,10 @@ int BV (clib_bihash_search)
 
   ASSERT (valuep);
 
+#if BIHASH_LAZY_INSTANTIATE
   if (PREDICT_FALSE (alloc_arena (h) == 0))
     return -1;
+#endif
 
   hash = BV (clib_bihash_hash) (search_key);
 
@@ -812,12 +915,14 @@ u8 *BV (format_bihash) (u8 * s, va_list * args)
 
   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 
+#if BIHASH_LAZY_INSTANTIATE
   if (PREDICT_FALSE (alloc_arena (h) == 0))
     return format (s, "[empty, uninitialized]");
+#endif
 
   for (i = 0; i < h->nbuckets; i++)
     {
-      b = &h->buckets[i];
+      b = BV (clib_bihash_get_bucket) (h, i);
       if (BV (clib_bihash_bucket_is_empty) (b))
        {
          if (verbose > 1)
@@ -832,8 +937,9 @@ u8 *BV (format_bihash) (u8 * s, va_list * args)
 
       if (verbose)
        {
-         s = format (s, "[%d]: heap offset %lld, len %d, linear %d\n", i,
-                     b->offset, (1 << b->log2_pages), b->linear_search);
+         s = format
+           (s, "[%d]: heap offset %lld, len %d, refcnt %d, linear %d\n", i,
+            b->offset, (1 << b->log2_pages), b->refcnt, b->linear_search);
        }
 
       v = BV (clib_bihash_get_value) (h, b->offset);
@@ -909,12 +1015,15 @@ void BV (clib_bihash_foreach_key_value_pair)
   BVT (clib_bihash_bucket) * b;
   BVT (clib_bihash_value) * v;
 
+
+#if BIHASH_LAZY_INSTANTIATE
   if (PREDICT_FALSE (alloc_arena (h) == 0))
     return;
+#endif
 
   for (i = 0; i < h->nbuckets; i++)
     {
-      b = &h->buckets[i];
+      b = BV (clib_bihash_get_bucket) (h, i);
       if (BV (clib_bihash_bucket_is_empty) (b))
        continue;
 

diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index 6abe7a3..13a348f 100644 (file)
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -44,6 +44,11 @@
 #define BIHASH_FREELIST_LENGTH 17
 #endif
 
+/* default is 2MB, use 30 for 1GB */
+#ifndef BIHASH_LOG2_HUGEPAGE_SIZE
+#define BIHASH_LOG2_HUGEPAGE_SIZE 21
+#endif
+
 #define _bv(a,b) a##b
 #define __bv(a,b) _bv(a,b)
 #define BV(a) __bv(a,BIHASH_TYPE)
@@ -103,6 +108,7 @@ typedef CLIB_PACKED (struct {
    */
   u64 alloc_arena_next;        /* Next offset from alloc_arena to allocate, definitely NOT a constant */
   u64 alloc_arena_size;        /* Size of the arena */
+  u64 alloc_arena_mapped;      /* Size of the mapped memory in the arena */
   /* Two SVM pointers stored as 8-byte integers */
   u64 alloc_lock_as_u64;
   u64 buckets_as_u64;
@@ -111,7 +117,7 @@ typedef CLIB_PACKED (struct {
   u32 nbuckets;        /* Number of buckets */
   /* Set when header valid */
   volatile u32 ready;
-  u64 pad[2];
+  u64 pad[1];
 }) BVT (clib_bihash_shared_header);
 /* *INDENT-ON* */
 
@@ -175,19 +181,23 @@ extern void **clib_all_bihashes;
 #if BIHASH_32_64_SVM
 #undef alloc_arena_next
 #undef alloc_arena_size
+#undef alloc_arena_mapped
 #undef alloc_arena
 #undef CLIB_BIHASH_READY_MAGIC
 #define alloc_arena_next(h) (((h)->sh)->alloc_arena_next)
 #define alloc_arena_size(h) (((h)->sh)->alloc_arena_size)
+#define alloc_arena_mapped(h) (((h)->sh)->alloc_arena_mapped)
 #define alloc_arena(h) ((h)->alloc_arena)
 #define CLIB_BIHASH_READY_MAGIC 0xFEEDFACE
 #else
 #undef alloc_arena_next
 #undef alloc_arena_size
+#undef alloc_arena_mapped
 #undef alloc_arena
 #undef CLIB_BIHASH_READY_MAGIC
 #define alloc_arena_next(h) ((h)->sh.alloc_arena_next)
 #define alloc_arena_size(h) ((h)->sh.alloc_arena_size)
+#define alloc_arena_mapped(h) ((h)->sh.alloc_arena_mapped)
 #define alloc_arena(h) ((h)->alloc_arena)
 #define CLIB_BIHASH_READY_MAGIC 0
 #endif
@@ -285,7 +295,10 @@ static inline int BV (clib_bihash_bucket_is_empty)
   (BVT (clib_bihash_bucket) * b)
 {
   /* Note: applied to locked buckets, test offset */
-  return b->offset == 0;
+  if (BIHASH_KVP_AT_BUCKET_LEVEL == 0)
+    return b->offset == 0;
+  else
+    return (b->log2_pages == 0 && b->refcnt == 1);
 }
 
 static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h,
@@ -345,19 +358,34 @@ format_function_t BV (format_bihash);
 format_function_t BV (format_bihash_kvp);
 format_function_t BV (format_bihash_lru);
 
+static inline
+BVT (clib_bihash_bucket) *
+BV (clib_bihash_get_bucket) (BVT (clib_bihash) * h, u64 hash)
+{
+#if BIHASH_KVP_AT_BUCKET_LEVEL
+  uword offset;
+  offset = (hash & (h->nbuckets - 1));
+  offset = offset * (sizeof (BVT (clib_bihash_bucket))
+                    + (BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv))));
+  return ((BVT (clib_bihash_bucket) *) (((u8 *) h->buckets) + offset));
+#endif
+
+  return h->buckets + (hash & (h->nbuckets - 1));
+}
+
 static inline int BV (clib_bihash_search_inline_with_hash)
   (BVT (clib_bihash) * h, u64 hash, BVT (clib_bihash_kv) * key_result)
 {
-  u32 bucket_index;
   BVT (clib_bihash_value) * v;
   BVT (clib_bihash_bucket) * b;
   int i, limit;
 
+#if BIHASH_LAZY_INSTANTIATE
   if (PREDICT_FALSE (alloc_arena (h) == 0))
     return -1;
+#endif
 
-  bucket_index = hash & (h->nbuckets - 1);
-  b = &h->buckets[bucket_index];
+  b = BV (clib_bihash_get_bucket) (h, hash);
 
   if (PREDICT_FALSE (BV (clib_bihash_bucket_is_empty) (b)))
     return -1;
@@ -400,17 +428,12 @@ static inline int BV (clib_bihash_search_inline)
   return BV (clib_bihash_search_inline_with_hash) (h, hash, key_result);
 }
 
-static inline
-BVT (clib_bihash_bucket) *
-BV (clib_bihash_get_bucket) (BVT (clib_bihash) * h, u64 hash)
-{
-  return h->buckets + (hash & (h->nbuckets - 1));
-}
-
 static inline void BV (clib_bihash_prefetch_bucket)
   (BVT (clib_bihash) * h, u64 hash)
 {
-  clib_prefetch_load (BV (clib_bihash_get_bucket) (h, hash));
+  CLIB_PREFETCH (BV (clib_bihash_get_bucket) (h, hash),
+                BIHASH_BUCKET_PREFETCH_CACHE_LINES * CLIB_CACHE_LINE_BYTES,
+                LOAD);
 }
 
 static inline void BV (clib_bihash_prefetch_data)
@@ -419,8 +442,10 @@ static inline void BV (clib_bihash_prefetch_data)
   BVT (clib_bihash_value) * v;
   BVT (clib_bihash_bucket) * b;
 
+#if BIHASH_LAZY_INSTANTIATE
   if (PREDICT_FALSE (alloc_arena (h) == 0))
     return;
+#endif
 
   b = BV (clib_bihash_get_bucket) (h, hash);
 
@@ -445,8 +470,10 @@ static inline int BV (clib_bihash_search_inline_2_with_hash)
 
   ASSERT (valuep);
 
+#if BIHASH_LAZY_INSTANTIATE
   if (PREDICT_FALSE (alloc_arena (h) == 0))
     return -1;
+#endif
 
   b = BV (clib_bihash_get_bucket) (h, hash);
 

diff --git a/src/vppinfra/bihash_vec8_8.h b/src/vppinfra/bihash_vec8_8.h
index f50234e..15c6d8c 100644 (file)
--- a/src/vppinfra/bihash_vec8_8.h
+++ b/src/vppinfra/bihash_vec8_8.h
@@ -16,9 +16,15 @@
 #undef BIHASH_KVP_PER_PAGE
 #undef BIHASH_32_64_SVM
 #undef BIHASH_ENABLE_STATS
+#undef BIHASH_KVP_AT_BUCKET_LEVEL
+#undef BIHASH_LAZY_INSTANTIATE
+#undef BIHASH_BUCKET_PREFETCH_CACHE_LINES
 
 #define BIHASH_TYPE _vec8_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
 
 #ifndef __included_bihash_vec8_8_h__
 #define __included_bihash_vec8_8_h__

diff --git a/src/vppinfra/linux/mem.c b/src/vppinfra/linux/mem.c
index 3b7294f..d86402a 100644 (file)
--- a/src/vppinfra/linux/mem.c
+++ b/src/vppinfra/linux/mem.c
@@ -344,6 +344,38 @@ clib_mem_vm_ext_free (clib_mem_vm_alloc_t * a)
     }
 }
 
+uword
+clib_mem_vm_reserve (uword start, uword size, u32 log2_page_sz)
+{
+  uword off, pagesize = 1 << log2_page_sz;
+  int mmap_flags = MAP_PRIVATE | MAP_ANONYMOUS;
+  u8 *p;
+
+  if (start)
+    mmap_flags |= MAP_FIXED;
+
+  size = round_pow2 (size, pagesize);
+
+  p = uword_to_pointer (start, void *);
+  p = mmap (p, size + pagesize, PROT_NONE, mmap_flags, -1, 0);
+
+  if (p == MAP_FAILED)
+    return ~0;
+
+  off = round_pow2 ((uword) p, pagesize) - (uword) p;
+
+  /* trim start and end of reservation to be page aligned */
+  if (off)
+    {
+      munmap (p, off);
+      p += off;
+    }
+
+  munmap (p + size, pagesize - off);
+
+  return (uword) p;
+}
+
 u64 *
 clib_mem_vm_get_paddr (void *mem, int log2_page_size, int n_pages)
 {

diff --git a/src/vppinfra/mem.h b/src/vppinfra/mem.h
index 4fedd10..f254601 100644 (file)
--- a/src/vppinfra/mem.h
+++ b/src/vppinfra/mem.h
@@ -411,6 +411,7 @@ void clib_mem_vm_ext_free (clib_mem_vm_alloc_t * a);
 u64 clib_mem_get_fd_page_size (int fd);
 uword clib_mem_get_default_hugepage_size (void);
 int clib_mem_get_fd_log2_page_size (int fd);
+uword clib_mem_vm_reserve (uword start, uword size, u32 log2_page_sz);
 u64 *clib_mem_vm_get_paddr (void *mem, int log2_page_size, int n_pages);
 
 typedef struct

diff --git a/src/vppinfra/pmalloc.c b/src/vppinfra/pmalloc.c
index cca8039..e0f3f3a 100644 (file)
--- a/src/vppinfra/pmalloc.c
+++ b/src/vppinfra/pmalloc.c
@@ -63,9 +63,8 @@ pmalloc_validate_numa_node (u32 * numa_node)
 int
 clib_pmalloc_init (clib_pmalloc_main_t * pm, uword base_addr, uword size)
 {
-  uword off, pagesize;
+  uword base, pagesize;
   u64 *pt = 0;
-  int mmap_flags;
 
   ASSERT (pm->error == 0);
 
@@ -84,32 +83,16 @@ clib_pmalloc_init (clib_pmalloc_main_t * pm, uword base_addr, uword size)
 
   pm->max_pages = size >> pm->def_log2_page_sz;
 
-  /* reserve VA space for future growth */
-  mmap_flags = MAP_PRIVATE | MAP_ANONYMOUS;
+  base = clib_mem_vm_reserve (base_addr, size, pm->def_log2_page_sz);
 
-  if (base_addr)
-    mmap_flags |= MAP_FIXED;
-
-  pm->base = mmap (uword_to_pointer (base_addr, void *), size + pagesize,
-                  PROT_NONE, mmap_flags, -1, 0);
-
-  if (pm->base == MAP_FAILED)
+  if (base == ~0)
     {
-      pm->error = clib_error_return_unix (0, "failed to reserve %u pages");
+      pm->error = clib_error_return (0, "failed to reserve %u pages",
+                                    pm->max_pages);
       return -1;
     }
 
-  off = round_pow2 (pointer_to_uword (pm->base), pagesize) -
-    pointer_to_uword (pm->base);
-
-  /* trim start and end of reservation to be page aligned */
-  if (off)
-    {
-      munmap (pm->base, off);
-      pm->base += off;
-    }
-
-  munmap (pm->base + ((uword) pm->max_pages * pagesize), pagesize - off);
+  pm->base = uword_to_pointer (base, void *);
   return 0;
 }
 

diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c
index c1a4469..86039d8 100644 (file)
--- a/src/vppinfra/test_bihash_template.c
+++ b/src/vppinfra/test_bihash_template.c
@@ -337,6 +337,16 @@ test_bihash (test_main_t * tm)
        {
          for (i = 0; i < tm->nitems; i++)
            {
+             /* Prefetch buckets 8 iterations ahead */
+             if (1 && (i < (tm->nitems - 8)))
+               {
+                 BVT (clib_bihash_kv) pref_kv;
+                 u64 pref_hash;
+                 pref_kv.key = tm->keys[i + 8];
+                 pref_hash = BV (clib_bihash_hash) (&pref_kv);
+                 BV (clib_bihash_prefetch_bucket) (h, pref_hash);
+               }
+
              kv.key = tm->keys[i];
              if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
                if (BV (clib_bihash_search) (h, &kv, &kv) < 0)
@@ -356,8 +366,10 @@ test_bihash (test_main_t * tm)
          total_searches = (uword) tm->search_iter * (uword) tm->nitems;
 
          if (delta > 0)
-           fformat (stdout, "%.f searches per second\n",
-                    ((f64) total_searches) / delta);
+           fformat (stdout,
+                    "%.f searches per second, %.2f nsec per search\n",
+                    ((f64) total_searches) / delta,
+                    1e9 * (delta / ((f64) total_searches)));
 
          fformat (stdout, "%lld searches in %.6f seconds\n", total_searches,
                   delta);
@@ -409,6 +421,16 @@ test_bihash (test_main_t * tm)
            {
              for (j = 0; j < tm->nitems; j++)
                {
+                 /* Prefetch buckets 8 iterations ahead */
+                 if (1 && (j < (tm->nitems - 8)))
+                   {
+                     BVT (clib_bihash_kv) pref_kv;
+                     u64 pref_hash;
+                     pref_kv.key = tm->keys[j + 8];
+                     pref_hash = BV (clib_bihash_hash) (&pref_kv);
+                     BV (clib_bihash_prefetch_bucket) (h, pref_hash);
+                   }
+
                  kv.key = tm->keys[j];
                  rv = BV (clib_bihash_search) (h, &kv, &kv);
                  if (j <= i && rv >= 0)