Atomic bucket lock

Change-Id: I84908b9ad30d7555024e98b69ed37b111f31c27a
Signed-off-by: Dave Barach <dbarach@cisco.com>

2 files changed, 58 insertions, 41 deletions

diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c
index e3a5759d766..b5eb379a0f5 100644
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -135,8 +135,9 @@ BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b)
 
   clib_mem_set_heap (oldheap);
 
-  /* Turn off the cache */
-  BV (clib_bihash_cache_enable_disable) (b, 0);
+  /* Lock the bucket... */
+  while (BV (clib_bihash_lock_bucket) (b) == 0)
+    ;
 
   v = BV (clib_bihash_get_value) (h, b->offset);
 
@@ -416,7 +417,7 @@ expand_ok:
 
 unlock:
   BV (clib_bihash_reset_cache) (b);
-  BV (clib_bihash_cache_enable_disable) (b, 1 /* enable */ );
+  BV (clib_bihash_unlock_bucket) (b);
   CLIB_MEMORY_BARRIER ();
   h->writer_lock[0] = 0;
   return rv;
@@ -444,7 +445,7 @@ int BV (clib_bihash_search)
     return -1;
 
   /* Check the cache, if currently enabled */
-  if (PREDICT_TRUE (b->cache_lru & (1 << 15)))
+  if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0))
     {
       limit = BIHASH_KVP_CACHE_SIZE;
       kvp = b->cache;
@@ -475,16 +476,16 @@ int BV (clib_bihash_search)
 	  *valuep = v->kvp[i];
 
 	  /* Shut off the cache */
-	  BV (clib_bihash_cache_enable_disable) (b, 0);
-	  CLIB_MEMORY_BARRIER ();
-
-	  cache_slot = BV (clib_bihash_get_lru) (b);
-	  b->cache[cache_slot] = v->kvp[i];
-	  BV (clib_bihash_update_lru) (b, cache_slot);
+	  if (BV (clib_bihash_lock_bucket) (b))
+	    {
+	      cache_slot = BV (clib_bihash_get_lru) (b);
+	      b->cache[cache_slot] = v->kvp[i];
+	      BV (clib_bihash_update_lru) (b, cache_slot);
 
-	  /* Reenable the cache */
-	  BV (clib_bihash_cache_enable_disable) (b, 1);
-	  h->cache_misses++;
+	      /* Reenable the cache */
+	      BV (clib_bihash_unlock_bucket) (b);
+	      h->cache_misses++;
+	    }
 	  return 0;
 	}
     }
diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index feb6fb68797..3d9c59cb933 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -182,13 +182,29 @@ static inline void BV (clib_bihash_reset_cache) (BVT (clib_bihash_bucket) * b)
   b->cache_lru = initial_lru_value;
 }
 
-static inline void BV (clib_bihash_cache_enable_disable)
-  (BVT (clib_bihash_bucket) * b, u8 enable)
+static inline int BV (clib_bihash_lock_bucket) (BVT (clib_bihash_bucket) * b)
 {
   BVT (clib_bihash_bucket) tmp_b;
+  u64 rv;
+
+  tmp_b.as_u64 = 0;
+  tmp_b.cache_lru = 1 << 15;
+
+  rv = __sync_fetch_and_or (&b->as_u64, tmp_b.as_u64);
+  tmp_b.as_u64 = rv;
+  /* Was already locked? */
+  if (tmp_b.cache_lru & (1 << 15))
+    return 0;
+  return 1;
+}
+
+static inline void BV (clib_bihash_unlock_bucket)
+  (BVT (clib_bihash_bucket) * b)
+{
+  BVT (clib_bihash_bucket) tmp_b;
+
   tmp_b.as_u64 = b->as_u64;
-  tmp_b.cache_lru &= 0x7FFF;
-  tmp_b.cache_lru |= enable << 15;
+  tmp_b.cache_lru &= ~(1 << 15);
   b->as_u64 = tmp_b.as_u64;
 }
 
@@ -249,8 +265,8 @@ static inline int BV (clib_bihash_search_inline)
   if (b->offset == 0)
     return -1;
 
-  /* Check the cache, if currently enabled */
-  if (PREDICT_TRUE (b->cache_lru & (1 << 15)))
+  /* Check the cache, if not currently locked */
+  if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0))
     {
       limit = BIHASH_KVP_CACHE_SIZE;
       kvp = b->cache;
@@ -282,17 +298,17 @@ static inline int BV (clib_bihash_search_inline)
 	  u8 cache_slot;
 	  *key_result = v->kvp[i];
 
-	  /* Shut off the cache */
-	  BV (clib_bihash_cache_enable_disable) (b, 0);
-	  CLIB_MEMORY_BARRIER ();
-
-	  cache_slot = BV (clib_bihash_get_lru) (b);
-	  b->cache[cache_slot] = v->kvp[i];
-	  BV (clib_bihash_update_lru) (b, cache_slot);
+	  /* Try to lock the bucket */
+	  if (BV (clib_bihash_lock_bucket) (b))
+	    {
+	      cache_slot = BV (clib_bihash_get_lru) (b);
+	      b->cache[cache_slot] = v->kvp[i];
+	      BV (clib_bihash_update_lru) (b, cache_slot);
 
-	  /* Reenable the cache */
-	  BV (clib_bihash_cache_enable_disable) (b, 1);
-	  h->cache_misses++;
+	      /* Unlock the bucket */
+	      BV (clib_bihash_unlock_bucket) (b);
+	      h->cache_misses++;
+	    }
 	  return 0;
 	}
     }
@@ -320,8 +336,8 @@ static inline int BV (clib_bihash_search_inline_2)
   if (b->offset == 0)
     return -1;
 
-  /* Check the cache, if currently enabled */
-  if (PREDICT_TRUE (b->cache_lru & (1 << 15)))
+  /* Check the cache, if currently unlocked */
+  if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0))
     {
       limit = BIHASH_KVP_CACHE_SIZE;
       kvp = b->cache;
@@ -352,17 +368,17 @@ static inline int BV (clib_bihash_search_inline_2)
 	  u8 cache_slot;
 	  *valuep = v->kvp[i];
 
-	  /* Shut off the cache */
-	  BV (clib_bihash_cache_enable_disable) (b, 0);
-	  CLIB_MEMORY_BARRIER ();
-
-	  cache_slot = BV (clib_bihash_get_lru) (b);
-	  b->cache[cache_slot] = v->kvp[i];
-	  BV (clib_bihash_update_lru) (b, cache_slot);
+	  /* Try to lock the bucket */
+	  if (BV (clib_bihash_lock_bucket) (b))
+	    {
+	      cache_slot = BV (clib_bihash_get_lru) (b);
+	      b->cache[cache_slot] = v->kvp[i];
+	      BV (clib_bihash_update_lru) (b, cache_slot);
 
-	  /* Reenable the cache */
-	  BV (clib_bihash_cache_enable_disable) (b, 1);
-	  h->cache_misses++;
+	      /* Reenable the cache */
+	      BV (clib_bihash_unlock_bucket) (b);
+	      h->cache_misses++;
+	    }
 	  return 0;
 	}
     }