X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvppinfra%2Fbihash_template.c;h=2b378427ce8c79e325d64ae700a0fff4e8e153f6;hb=a690fdbfe179e0ea65818c03b52535bf9210efd0;hp=698053867a494fade138e4cf31fbef9716c206e4;hpb=178cf493d009995b28fdf220f04c98860ff79a9b;p=vpp.git

diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c
index 698053867a4..2b378427ce8 100644
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -26,23 +26,42 @@ static inline void *BV (alloc_aligned) (BVT (clib_bihash) * h, uword nbytes)
   rv = alloc_arena_next (h);
   alloc_arena_next (h) += nbytes;
 
-  if (rv >= alloc_arena_size (h))
+  if (alloc_arena_next (h) > alloc_arena_size (h))
     os_out_of_memory ();
 
   return (void *) (uword) (rv + alloc_arena (h));
 }
 
-
-void BV (clib_bihash_init)
-  (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
+static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h)
 {
   uword bucket_size;
 
-  nbuckets = 1 << (max_log2 (nbuckets));
+  alloc_arena (h) = (uword) clib_mem_vm_alloc (h->memory_size);
+  alloc_arena_next (h) = 0;
+  alloc_arena_size (h) = h->memory_size;
 
-  h->name = (u8 *) name;
-  h->nbuckets = nbuckets;
-  h->log2_nbuckets = max_log2 (nbuckets);
+  bucket_size = h->nbuckets * sizeof (h->buckets[0]);
+  h->buckets = BV (alloc_aligned) (h, bucket_size);
+  CLIB_MEMORY_BARRIER ();
+  h->instantiated = 1;
+}
+
+void BV (clib_bihash_init2) (BVT (clib_bihash_init2_args) * a)
+{
+  int i;
+  void *oldheap;
+  BVT (clib_bihash) * h = a->h;
+
+  a->nbuckets = 1 << (max_log2 (a->nbuckets));
+
+  h->name = (u8 *) a->name;
+  h->nbuckets = a->nbuckets;
+  h->log2_nbuckets = max_log2 (a->nbuckets);
+  h->memory_size = a->memory_size;
+  h->instantiated = 0;
+  h->fmt_fn = a->fmt_fn;
+
+  alloc_arena (h) = 0;
 
   /*
    * Make sure the requested size is rational. The max table
@@ -50,19 +69,48 @@ void BV (clib_bihash_init)
    * If someone starts complaining that's not enough, we can shift
    * the offset by CLIB_LOG2_CACHE_LINE_BYTES...
    */
-  ASSERT (memory_size < (1ULL << BIHASH_BUCKET_OFFSET_BITS));
+  ASSERT (h->memory_size < (1ULL << BIHASH_BUCKET_OFFSET_BITS));
 
-  alloc_arena (h) = (uword) clib_mem_vm_alloc (memory_size);
-  alloc_arena_next (h) = 0;
-  alloc_arena_size (h) = memory_size;
+  /* Add this hash table to the list */
+  if (a->dont_add_to_all_bihash_list == 0)
+    {
+      for (i = 0; i < vec_len (clib_all_bihashes); i++)
+	if (clib_all_bihashes[i] == h)
+	  goto do_lock;
+      oldheap = clib_all_bihash_set_heap ();
+      vec_add1 (clib_all_bihashes, (void *) h);
+      clib_mem_set_heap (oldheap);
+    }
 
-  bucket_size = nbuckets * sizeof (h->buckets[0]);
-  h->buckets = BV (alloc_aligned) (h, bucket_size);
+do_lock:
+  if (h->alloc_lock)
+    clib_mem_free ((void *) h->alloc_lock);
 
-  h->alloc_lock = BV (alloc_aligned) (h, CLIB_CACHE_LINE_BYTES);
+  /*
+   * Set up the lock now, so we can use it to make the first add
+   * thread-safe
+   */
+  h->alloc_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES,
+					  CLIB_CACHE_LINE_BYTES);
   h->alloc_lock[0] = 0;
 
-  h->fmt_fn = NULL;
+  if (a->instantiate_immediately)
+    BV (clib_bihash_instantiate) (h);
+}
+
+void BV (clib_bihash_init)
+  (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
+{
+  BVT (clib_bihash_init2_args) _a, *a = &_a;
+
+  memset (a, 0, sizeof (*a));
+
+  a->h = h;
+  a->name = name;
+  a->nbuckets = nbuckets;
+  a->memory_size = memory_size;
+
+  BV (clib_bihash_init2) (a);
 }
 
 #if BIHASH_32_64_SVM
@@ -131,12 +179,12 @@ void BV (clib_bihash_master_init_svm)
 			sizeof (vec_header_t) +
 			BIHASH_FREELIST_LENGTH * sizeof (u64));
   freelist_vh->len = BIHASH_FREELIST_LENGTH;
-  freelist_vh->dlmalloc_header_offset = 0xDEADBEEF;
   h->sh->freelists_as_u64 =
     (u64) BV (clib_bihash_get_offset) (h, freelist_vh->vector_data);
   h->freelists = (void *) (freelist_vh->vector_data);
 
   h->fmt_fn = NULL;
+  h->instantiated = 1;
 }
 
 void BV (clib_bihash_slave_init_svm)
@@ -195,7 +243,14 @@ void BV (clib_bihash_set_kvp_format_fn) (BVT (clib_bihash) * h,
 
 void BV (clib_bihash_free) (BVT (clib_bihash) * h)
 {
+  int i;
+
+  if (PREDICT_FALSE (h->instantiated == 0))
+    goto never_initialized;
+
+  h->instantiated = 0;
   vec_free (h->working_copies);
+  vec_free (h->working_copy_lengths);
 #if BIHASH_32_64_SVM == 0
   vec_free (h->freelists);
 #else
@@ -203,7 +258,18 @@ void BV (clib_bihash_free) (BVT (clib_bihash) * h)
     (void) close (h->memfd);
 #endif
   clib_mem_vm_free ((void *) (uword) (alloc_arena (h)), alloc_arena_size (h));
+never_initialized:
   clib_memset (h, 0, sizeof (*h));
+  for (i = 0; i < vec_len (clib_all_bihashes); i++)
+    {
+      if ((void *) h == clib_all_bihashes[i])
+	{
+	  vec_delete (clib_all_bihashes, 1, i);
+	  return;
+	}
+    }
+  clib_warning ("Couldn't find hash table %llx on clib_all_bihashes...",
+		(u64) (uword) h);
 }
 
 static
@@ -291,6 +357,9 @@ BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b)
 	(h, sizeof (working_copy[0]) * (1 << b->log2_pages));
       h->working_copy_lengths[thread_index] = b->log2_pages;
       h->working_copies[thread_index] = working_copy;
+
+      BV (clib_bihash_increment_stat) (h, BIHASH_STAT_working_copy_lost,
+				       1ULL << b->log2_pages);
     }
 
   v = BV (clib_bihash_get_value) (h, b->offset);
@@ -413,6 +482,21 @@ static inline int BV (clib_bihash_add_del_inline)
   int mark_bucket_linear;
   int resplit_once;
 
+  /*
+   * Create the table (is_add=1,2), or flunk the request now (is_add=0)
+   * Use the alloc_lock to protect the instantiate operation.
+   */
+  if (PREDICT_FALSE (h->instantiated == 0))
+    {
+      if (is_add == 0)
+	return (-1);
+
+      BV (clib_bihash_alloc_lock) (h);
+      if (h->instantiated == 0)
+	BV (clib_bihash_instantiate) (h);
+      BV (clib_bihash_alloc_unlock) (h);
+    }
+
   hash = BV (clib_bihash_hash) (add_v);
 
   bucket_index = hash & (h->nbuckets - 1);
@@ -441,8 +525,9 @@ static inline int BV (clib_bihash_add_del_inline)
       tmp_b.refcnt = 1;
       CLIB_MEMORY_BARRIER ();
 
-      b->as_u64 = tmp_b.as_u64;
-      BV (clib_bihash_unlock_bucket) (b);
+      b->as_u64 = tmp_b.as_u64;	/* unlocks the bucket */
+      BV (clib_bihash_increment_stat) (h, BIHASH_STAT_alloc_add, 1);
+
       return (0);
     }
 
@@ -469,11 +554,19 @@ static inline int BV (clib_bihash_add_del_inline)
        */
       for (i = 0; i < limit; i++)
 	{
-	  if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
+	  if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
 	    {
+	      /* Add but do not overwrite? */
+	      if (is_add == 2)
+		{
+		  BV (clib_bihash_unlock_bucket) (b);
+		  return (-2);
+		}
+
 	      CLIB_MEMORY_BARRIER ();	/* Add a delay */
 	      clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
 	      BV (clib_bihash_unlock_bucket) (b);
+	      BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1);
 	      return (0);
 	    }
 	}
@@ -496,6 +589,7 @@ static inline int BV (clib_bihash_add_del_inline)
 	      b->refcnt++;
 	      ASSERT (b->refcnt > 0);
 	      BV (clib_bihash_unlock_bucket) (b);
+	      BV (clib_bihash_increment_stat) (h, BIHASH_STAT_add, 1);
 	      return (0);
 	    }
 	}
@@ -509,6 +603,7 @@ static inline int BV (clib_bihash_add_del_inline)
 		  CLIB_MEMORY_BARRIER ();
 		  clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v));
 		  BV (clib_bihash_unlock_bucket) (b);
+		  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1);
 		  return (0);
 		}
 	    }
@@ -520,7 +615,7 @@ static inline int BV (clib_bihash_add_del_inline)
       for (i = 0; i < limit; i++)
 	{
 	  /* Found the key? Kill it... */
-	  if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)))
+	  if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key))
 	    {
 	      clib_memset (&(v->kvp[i]), 0xff, sizeof (*(add_v)));
 	      /* Is the bucket empty? */
@@ -528,6 +623,7 @@ static inline int BV (clib_bihash_add_del_inline)
 		{
 		  b->refcnt--;
 		  BV (clib_bihash_unlock_bucket) (b);
+		  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1);
 		  return (0);
 		}
 	      else		/* yes, free it */
@@ -545,6 +641,8 @@ static inline int BV (clib_bihash_add_del_inline)
 		  v = BV (clib_bihash_get_value) (h, tmp_b.offset);
 		  BV (value_free) (h, v, tmp_b.log2_pages);
 		  BV (clib_bihash_alloc_unlock) (h);
+		  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del_free,
+						   1);
 		  return (0);
 		}
 	    }
@@ -563,9 +661,12 @@ static inline int BV (clib_bihash_add_del_inline)
   old_log2_pages = h->saved_bucket.log2_pages;
   new_log2_pages = old_log2_pages + 1;
   mark_bucket_linear = 0;
+  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_split_add, 1);
+  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, old_log2_pages);
 
   working_copy = h->working_copies[thread_index];
   resplit_once = 0;
+  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits, 1);
 
   new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages,
 				 new_log2_pages);
@@ -586,7 +687,11 @@ static inline int BV (clib_bihash_add_del_inline)
 	    BV (split_and_rehash_linear) (h, working_copy, old_log2_pages,
 					  new_log2_pages);
 	  mark_bucket_linear = 1;
+	  BV (clib_bihash_increment_stat) (h, BIHASH_STAT_linear, 1);
 	}
+      BV (clib_bihash_increment_stat) (h, BIHASH_STAT_resplit, 1);
+      BV (clib_bihash_increment_stat) (h, BIHASH_STAT_splits,
+				       old_log2_pages + 1);
     }
 
   /* Try to add the new entry */
@@ -660,6 +765,9 @@ int BV (clib_bihash_search)
 
   ASSERT (valuep);
 
+  if (PREDICT_FALSE (alloc_arena (h) == 0))
+    return -1;
+
   hash = BV (clib_bihash_hash) (search_key);
 
   bucket_index = hash & (h->nbuckets - 1);
@@ -708,6 +816,9 @@ u8 *BV (format_bihash) (u8 * s, va_list * args)
 
   s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)");
 
+  if (PREDICT_FALSE (alloc_arena (h) == 0))
+    return format (s, "[empty, uninitialized]");
+
   for (i = 0; i < h->nbuckets; i++)
     {
       b = &h->buckets[i];
@@ -747,7 +858,7 @@ u8 *BV (format_bihash) (u8 * s, va_list * args)
 		    {
 		      s = format (s, "    %d: %U\n",
 				  j * BIHASH_KVP_PER_PAGE + k,
-				  h->fmt_fn, &(v->kvp[k]));
+				  h->fmt_fn, &(v->kvp[k]), verbose);
 		    }
 		  else
 		    {
@@ -795,12 +906,15 @@ u8 *BV (format_bihash) (u8 * s, va_list * args)
 }
 
 void BV (clib_bihash_foreach_key_value_pair)
-  (BVT (clib_bihash) * h, void *callback, void *arg)
+  (BVT (clib_bihash) * h,
+   BV (clib_bihash_foreach_key_value_pair_cb) cb, void *arg)
 {
   int i, j, k;
   BVT (clib_bihash_bucket) * b;
   BVT (clib_bihash_value) * v;
-  void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
+
+  if (PREDICT_FALSE (alloc_arena (h) == 0))
+    return;
 
   for (i = 0; i < h->nbuckets; i++)
     {
@@ -816,7 +930,8 @@ void BV (clib_bihash_foreach_key_value_pair)
 	      if (BV (clib_bihash_is_free) (&v->kvp[k]))
 		continue;
 
-	      (*fp) (&v->kvp[k], arg);
+	      if (BIHASH_WALK_STOP == cb (&v->kvp[k], arg))
+		return;
 	      /*
 	       * In case the callback deletes the last entry in the bucket...
 	       */