X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;f=src%2Fvppinfra%2Fcuckoo_template.c;h=8cd2a2be2b5f7a2b30bbd53cc8b436e33bc4b4e8;hb=aad1ee149403994194cf37cef4530b042ba7df3a;hp=595bd1ca3bcb029b981e108e9be8441e0fcefa7c;hpb=819d5fdb39526386ee8fe4a8729f960e84443cbd;p=vpp.git

diff --git a/src/vppinfra/cuckoo_template.c b/src/vppinfra/cuckoo_template.c
index 595bd1ca3bc..8cd2a2be2b5 100644
--- a/src/vppinfra/cuckoo_template.c
+++ b/src/vppinfra/cuckoo_template.c
@@ -21,7 +21,6 @@
  */
 
 #include <vppinfra/vec.h>
-#include <vppinfra/cuckoo_template.h>
 
 int CV (clib_cuckoo_search) (CVT (clib_cuckoo) * h,
 			     CVT (clib_cuckoo_kv) * search_v,
@@ -100,8 +99,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
   CVT (clib_cuckoo_bucket) * bucket;
   uword bucket_idx = 0;
   /* *INDENT-OFF* */
-  clib_cuckoo_foreach_bucket (bucket, h)
-  {
+  clib_cuckoo_foreach_bucket (bucket, h, {
     int i = 0;
     int used = 0;
     clib_cuckoo_bucket_foreach_idx (i)
@@ -110,8 +108,8 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
       if (!CV (clib_cuckoo_kv_is_free) (elt))
         {
           u64 hash = CV (clib_cuckoo_hash) (elt);
-          clib_cuckoo_lookup_info_t lookup = CV (clib_cuckoo_calc_lookup) (
-              CV (clib_cuckoo_get_snapshot) (h), hash);
+          clib_cuckoo_lookup_info_t lookup =
+              CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
           CVT (clib_cuckoo_kv) kv = *elt;
           int rv = CV (clib_cuckoo_search) (h, &kv, &kv);
           if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
@@ -121,7 +119,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
                                bucket->reduced_hashes[i]);
               CLIB_CUCKOO_DBG ("%U", CV (format_cuckoo), h, 1);
             }
-          ASSERT (aux.bucket1 == bucket_idx || aux.bucket2 == bucket_idx);
+          ASSERT (lookup.bucket1 == bucket_idx || lookup.bucket2 == bucket_idx);
           ASSERT (CLIB_CUCKOO_ERROR_SUCCESS == rv);
           ++used;
         }
@@ -129,7 +127,7 @@ static void CV (clib_cuckoo_deep_self_check) (CVT (clib_cuckoo) * h)
     clib_cuckoo_bucket_aux_t aux = bucket->aux;
     ASSERT (used == clib_cuckoo_bucket_aux_get_use_count (aux));
     ++bucket_idx;
-  }
+  });
   /* *INDENT-ON* */
   // CLIB_CUCKOO_DBG ("Deep self check passed: %U", CV (format_cuckoo), h);
 }
@@ -169,7 +167,7 @@ void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
 			    void *garbage_ctx)
 {
   uword log2_nbuckets = max_log2 (nbuckets);
-  nbuckets = 1 << (log2_nbuckets);
+  nbuckets = 1ULL << (log2_nbuckets);
   CLIB_CUCKOO_DBG ("New cuckoo, adjusted nbuckets %wu", nbuckets);
   CVT (clib_cuckoo_bucket) * buckets = NULL;
   vec_validate_aligned (buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES);
@@ -180,7 +178,7 @@ void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
   CVT (clib_cuckoo_bucket) * bucket;
   /* *INDENT-OFF* */
   clib_cuckoo_foreach_bucket (
-      bucket, h, { memset (bucket->elts, 0xff, sizeof (bucket->elts)); });
+      bucket, h, { clib_memset (bucket->elts, 0xff, sizeof (bucket->elts)); });
   /* *INDENT-ON* */
   h->name = name;
   h->garbage_callback = garbage_callback;
@@ -189,7 +187,7 @@ void CV (clib_cuckoo_init) (CVT (clib_cuckoo) * h, const char *name,
 
 void CV (clib_cuckoo_free) (CVT (clib_cuckoo) * h)
 {
-  memset (h, 0, sizeof (*h));
+  clib_memset (h, 0, sizeof (*h));
 }
 
 static clib_cuckoo_bucket_aux_t
@@ -227,7 +225,7 @@ static clib_cuckoo_path_t *CV (clib_cuckoo_path_get) (CVT (clib_cuckoo) * h)
 {
   clib_cuckoo_path_t *path;
   pool_get (h->paths, path);
-  memset (path, 0, sizeof (*path));
+  clib_memset (path, 0, sizeof (*path));
 #if CLIB_CUCKOO_DEBUG_PATH_DETAIL
   CLIB_CUCKOO_DBG ("Get path @%lu", (long unsigned) (path - h->paths));
 #endif
@@ -531,10 +529,10 @@ static void CV (clib_cuckoo_bucket_tidy) (CVT (clib_cuckoo_bucket) * b)
 static void CV (clib_cuckoo_free_locked_elt) (CVT (clib_cuckoo_kv) * elt)
 {
   /*
-   * FIXME - improve performance by getting rid of this memset - make all
+   * FIXME - improve performance by getting rid of this clib_memset - make all
    * functions in this file not rely on clib_cuckoo_kv_is_free but instead
    * take use_count into account */
-  memset (elt, 0xff, sizeof (*elt));
+  clib_memset (elt, 0xff, sizeof (*elt));
 }
 
 static void CV (clib_cuckoo_free_elt_in_bucket) (CVT (clib_cuckoo_bucket) * b,
@@ -736,7 +734,7 @@ static void CV (clib_cuckoo_rehash) (CVT (clib_cuckoo) * h)
   CVT (clib_cuckoo_bucket) * bucket;
   for (bucket = new + old_nbuckets; bucket < vec_end (new); ++bucket)
     {
-      memset (bucket->elts, 0xff, sizeof (bucket->elts));
+      clib_memset (bucket->elts, 0xff, sizeof (bucket->elts));
     }
   /*
    * this for loop manipulates the new (unseen) memory, so no locks
@@ -820,14 +818,15 @@ static int CV (clib_cuckoo_bucket_search_internal) (CVT (clib_cuckoo) * h,
 }
 
 int CV (clib_cuckoo_add_del) (CVT (clib_cuckoo) * h,
-			      CVT (clib_cuckoo_kv) * kvp, int is_add)
+			      CVT (clib_cuckoo_kv) * kvp, int is_add,
+			      int dont_overwrite)
 {
   CLIB_CUCKOO_DBG ("%s %U", is_add ? "Add" : "Del", CV (format_cuckoo_kvp),
 		   kvp);
   clib_cuckoo_lookup_info_t lookup;
   u64 hash = CV (clib_cuckoo_hash) (kvp);
-  clib_spinlock_lock (&h->writer_lock);
   u8 reduced_hash = clib_cuckoo_reduce_hash (hash);
+  clib_spinlock_lock (&h->writer_lock);
 restart:
   lookup = CV (clib_cuckoo_calc_lookup) (h->buckets, hash);
   CVT (clib_cuckoo_bucket) * b =
@@ -846,19 +845,30 @@ restart:
     {
       if (is_add)
 	{
-	  /* prevent readers reading this bucket while we switch the values */
-	  clib_cuckoo_bucket_aux_t aux =
-	    CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
-	  clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
-	  CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
-			   found, b->reduced_hashes[found - b->elts]);
-	  CV (clib_cuckoo_bucket_unlock) (b, aux);
+	  if (dont_overwrite)
+	    {
+	      CLIB_CUCKOO_DBG ("Refused replacing existing %U",
+			       CV (format_cuckoo_elt), found,
+			       b->reduced_hashes[found - b->elts]);
+	      rv = CLIB_CUCKOO_ERROR_AGAIN;
+	    }
+	  else
+	    {
+	      /* prevent readers reading this bucket while we switch the values */
+	      clib_cuckoo_bucket_aux_t aux =
+		CV (clib_cuckoo_bucket_version_bump_and_lock) (b);
+	      clib_memcpy (&found->value, &kvp->value, sizeof (found->value));
+	      CLIB_CUCKOO_DBG ("Replaced existing %U", CV (format_cuckoo_elt),
+			       found, b->reduced_hashes[found - b->elts]);
+	      CV (clib_cuckoo_bucket_unlock) (b, aux);
+	      rv = CLIB_CUCKOO_ERROR_SUCCESS;
+	    }
 	}
       else
 	{
 	  CV (clib_cuckoo_free_elt_in_bucket) (b, found);
+	  rv = CLIB_CUCKOO_ERROR_SUCCESS;
 	}
-      rv = CLIB_CUCKOO_ERROR_SUCCESS;
       CLIB_CUCKOO_DEEP_SELF_CHECK (h);
       goto unlock;
     }
@@ -876,9 +886,12 @@ restart:
   CLIB_CUCKOO_DEEP_SELF_CHECK (h);
   if (CLIB_CUCKOO_ERROR_SUCCESS != rv)
     {
-    CLIB_CUCKOO_DBG ("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U", aux.bucket1, aux.bucket2, CV (format_cuckoo_bucket), CV (clib_cuckoo_bucindent: Standaindent: Standard input: 903: Error: Unmatched 'else' rd input: 865: Error:Unmatched 'else' ket_at_index) (h, aux.bucket1),
-		       CV (format_cuckoo_bucket),
-		       CV (clib_cuckoo_bucket_at_index) (h, aux.bucket2));
+      CLIB_CUCKOO_DBG
+	("Fast insert failed, bucket 1: %wu, bucket 2: %wu\n%U%U",
+	 lookup.bucket1, lookup.bucket2, CV (format_cuckoo_bucket),
+	 CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket1),
+	 CV (format_cuckoo_bucket),
+	 CV (clib_cuckoo_bucket_at_index) (h, lookup.bucket2));
       /* slow path */
       rv = CV (clib_cuckoo_add_slow) (h, kvp, &lookup, reduced_hash);
       CLIB_CUCKOO_DEEP_SELF_CHECK (h);