aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/vnet/fib/ip6_fib.c4
-rw-r--r--src/vnet/fib/ip6_fib.h2
-rw-r--r--src/vnet/l2/l2_fib.c8
-rw-r--r--src/vppinfra.am2
-rw-r--r--src/vppinfra/bihash_16_8.h3
-rw-r--r--src/vppinfra/bihash_24_8.h3
-rw-r--r--src/vppinfra/bihash_48_8.h3
-rw-r--r--src/vppinfra/bihash_8_8.h3
-rw-r--r--src/vppinfra/bihash_template.c78
-rw-r--r--src/vppinfra/bihash_template.h206
-rw-r--r--src/vppinfra/test_bihash_template.c61
11 files changed, 329 insertions, 44 deletions
diff --git a/src/vnet/fib/ip6_fib.c b/src/vnet/fib/ip6_fib.c
index 527f91146a0..8fde6f9f46e 100644
--- a/src/vnet/fib/ip6_fib.c
+++ b/src/vnet/fib/ip6_fib.c
@@ -200,7 +200,7 @@ ip6_fib_table_lookup (u32 fib_index,
const ip6_address_t *addr,
u32 len)
{
- const ip6_fib_table_instance_t *table;
+ ip6_fib_table_instance_t *table;
BVT(clib_bihash_kv) kv, value;
int i, n_p, rv;
u64 fib;
@@ -246,7 +246,7 @@ ip6_fib_table_lookup_exact_match (u32 fib_index,
const ip6_address_t *addr,
u32 len)
{
- const ip6_fib_table_instance_t *table;
+ ip6_fib_table_instance_t *table;
BVT(clib_bihash_kv) kv, value;
ip6_address_t *mask;
u64 fib;
diff --git a/src/vnet/fib/ip6_fib.h b/src/vnet/fib/ip6_fib.h
index 9789da4fa97..aad8305c990 100644
--- a/src/vnet/fib/ip6_fib.h
+++ b/src/vnet/fib/ip6_fib.h
@@ -68,7 +68,7 @@ ip6_fib_table_fwding_lookup (ip6_main_t * im,
u32 fib_index,
const ip6_address_t * dst)
{
- const ip6_fib_table_instance_t *table;
+ ip6_fib_table_instance_t *table;
int i, len;
int rv;
BVT(clib_bihash_kv) kv, value;
diff --git a/src/vnet/l2/l2_fib.c b/src/vnet/l2/l2_fib.c
index 4ed16987404..7e59b09848a 100644
--- a/src/vnet/l2/l2_fib.c
+++ b/src/vnet/l2/l2_fib.c
@@ -66,7 +66,7 @@ l2fib_table_dump (u32 bd_index, l2fib_entry_key_t ** l2fe_key,
{
l2fib_main_t *msm = &l2fib_main;
BVT (clib_bihash) * h = &msm->mac_table;
- clib_bihash_bucket_t *b;
+ BVT (clib_bihash_bucket) * b;
BVT (clib_bihash_value) * v;
l2fib_entry_key_t key;
l2fib_entry_result_t result;
@@ -108,7 +108,7 @@ show_l2fib (vlib_main_t * vm,
l2fib_main_t *msm = &l2fib_main;
l2_bridge_domain_t *bd_config;
BVT (clib_bihash) * h = &msm->mac_table;
- clib_bihash_bucket_t *b;
+ BVT (clib_bihash_bucket) * b;
BVT (clib_bihash_value) * v;
l2fib_entry_key_t key;
l2fib_entry_result_t result;
@@ -961,7 +961,7 @@ l2fib_mac_age_scanner_process (vlib_main_t * vm, vlib_node_runtime_t * rt,
if (i < (h->nbuckets - 3))
{
- clib_bihash_bucket_t *b = &h->buckets[i + 3];
+ BVT (clib_bihash_bucket) * b = &h->buckets[i + 3];
CLIB_PREFETCH (b, CLIB_CACHE_LINE_BYTES, LOAD);
b = &h->buckets[i + 1];
if (b->offset)
@@ -972,7 +972,7 @@ l2fib_mac_age_scanner_process (vlib_main_t * vm, vlib_node_runtime_t * rt,
}
}
- clib_bihash_bucket_t *b = &h->buckets[i];
+ BVT (clib_bihash_bucket) * b = &h->buckets[i];
if (b->offset == 0)
continue;
BVT (clib_bihash_value) * v =
diff --git a/src/vppinfra.am b/src/vppinfra.am
index 785445a6d98..533bacd6f63 100644
--- a/src/vppinfra.am
+++ b/src/vppinfra.am
@@ -42,6 +42,8 @@ TESTS += test_bihash_template \
test_zvec
endif
+TESTS += test_bihash_template
+
noinst_PROGRAMS = $(TESTS)
check_PROGRAMS = $(TESTS)
diff --git a/src/vppinfra/bihash_16_8.h b/src/vppinfra/bihash_16_8.h
index 6b1b563e25b..361665bee4b 100644
--- a/src/vppinfra/bihash_16_8.h
+++ b/src/vppinfra/bihash_16_8.h
@@ -13,9 +13,12 @@
* limitations under the License.
*/
#undef BIHASH_TYPE
+#undef BIHASH_KVP_CACHE_SIZE
+#undef BIHASH_KVP_PER_PAGE
#define BIHASH_TYPE _16_8
#define BIHASH_KVP_PER_PAGE 4
+#define BIHASH_KVP_CACHE_SIZE 5
#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 db77daa4e2c..d0be028cba9 100644
--- a/src/vppinfra/bihash_24_8.h
+++ b/src/vppinfra/bihash_24_8.h
@@ -13,9 +13,12 @@
* limitations under the License.
*/
#undef BIHASH_TYPE
+#undef BIHASH_KVP_CACHE_SIZE
+#undef BIHASH_KVP_PER_PAGE
#define BIHASH_TYPE _24_8
#define BIHASH_KVP_PER_PAGE 4
+#define BIHASH_KVP_CACHE_SIZE 3
#ifndef __included_bihash_24_8_h__
#define __included_bihash_24_8_h__
diff --git a/src/vppinfra/bihash_48_8.h b/src/vppinfra/bihash_48_8.h
index 48079e0a1cf..107bcace3ce 100644
--- a/src/vppinfra/bihash_48_8.h
+++ b/src/vppinfra/bihash_48_8.h
@@ -14,9 +14,12 @@
*/
#undef BIHASH_TYPE
+#undef BIHASH_KVP_CACHE_SIZE
+#undef BIHASH_KVP_PER_PAGE
#define BIHASH_TYPE _48_8
#define BIHASH_KVP_PER_PAGE 4
+#define BIHASH_KVP_CACHE_SIZE 2
#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 68049351eea..f81002d6589 100644
--- a/src/vppinfra/bihash_8_8.h
+++ b/src/vppinfra/bihash_8_8.h
@@ -13,9 +13,12 @@
* limitations under the License.
*/
#undef BIHASH_TYPE
+#undef BIHASH_KVP_CACHE_SIZE
+#undef BIHASH_KVP_PER_PAGE
#define BIHASH_TYPE _8_8
#define BIHASH_KVP_PER_PAGE 4
+#define BIHASH_KVP_CACHE_SIZE 5
#ifndef __included_bihash_8_8_h__
#define __included_bihash_8_8_h__
diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c
index 004e8a9a558..e3a5759d766 100644
--- a/src/vppinfra/bihash_template.c
+++ b/src/vppinfra/bihash_template.c
@@ -19,12 +19,15 @@ void BV (clib_bihash_init)
(BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size)
{
void *oldheap;
+ int i;
nbuckets = 1 << (max_log2 (nbuckets));
h->name = (u8 *) name;
h->nbuckets = nbuckets;
h->log2_nbuckets = max_log2 (nbuckets);
+ h->cache_hits = 0;
+ h->cache_misses = 0;
h->mheap = mheap_alloc (0 /* use VM */ , memory_size);
@@ -33,6 +36,9 @@ void BV (clib_bihash_init)
h->writer_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES,
CLIB_CACHE_LINE_BYTES);
+ for (i = 0; i < nbuckets; i++)
+ BV (clib_bihash_reset_cache) (h->buckets + i);
+
clib_mem_set_heap (oldheap);
}
@@ -87,10 +93,10 @@ BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v,
}
static inline void
-BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b)
+BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b)
{
BVT (clib_bihash_value) * v;
- clib_bihash_bucket_t working_bucket __attribute__ ((aligned (8)));
+ BVT (clib_bihash_bucket) working_bucket __attribute__ ((aligned (8)));
void *oldheap;
BVT (clib_bihash_value) * working_copy;
u32 thread_index = os_get_thread_index ();
@@ -129,6 +135,9 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b)
clib_mem_set_heap (oldheap);
+ /* Turn off the cache */
+ BV (clib_bihash_cache_enable_disable) (b, 0);
+
v = BV (clib_bihash_get_value) (h, b->offset);
clib_memcpy (working_copy, v, sizeof (*v) * (1 << b->log2_pages));
@@ -235,7 +244,7 @@ int BV (clib_bihash_add_del)
(BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add)
{
u32 bucket_index;
- clib_bihash_bucket_t *b, tmp_b;
+ BVT (clib_bihash_bucket) * b, tmp_b;
BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy;
int rv = 0;
int i, limit;
@@ -276,6 +285,7 @@ int BV (clib_bihash_add_del)
goto unlock;
}
+ /* Note: this leaves the cache disabled */
BV (make_working_copy) (h, b);
v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset);
@@ -405,19 +415,22 @@ expand_ok:
BV (value_free) (h, v, old_log2_pages);
unlock:
+ BV (clib_bihash_reset_cache) (b);
+ BV (clib_bihash_cache_enable_disable) (b, 1 /* enable */ );
CLIB_MEMORY_BARRIER ();
h->writer_lock[0] = 0;
return rv;
}
int BV (clib_bihash_search)
- (const BVT (clib_bihash) * h,
+ (BVT (clib_bihash) * h,
BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
{
u64 hash;
u32 bucket_index;
BVT (clib_bihash_value) * v;
- clib_bihash_bucket_t *b;
+ BVT (clib_bihash_kv) * kvp;
+ BVT (clib_bihash_bucket) * b;
int i, limit;
ASSERT (valuep);
@@ -430,6 +443,22 @@ int BV (clib_bihash_search)
if (b->offset == 0)
return -1;
+ /* Check the cache, if currently enabled */
+ if (PREDICT_TRUE (b->cache_lru & (1 << 15)))
+ {
+ limit = BIHASH_KVP_CACHE_SIZE;
+ kvp = b->cache;
+ for (i = 0; i < limit; i++)
+ {
+ if (BV (clib_bihash_key_compare) (kvp[i].key, search_key->key))
+ {
+ *valuep = kvp[i];
+ h->cache_hits++;
+ return 0;
+ }
+ }
+ }
+
hash >>= h->log2_nbuckets;
v = BV (clib_bihash_get_value) (h, b->offset);
@@ -442,18 +471,50 @@ int BV (clib_bihash_search)
{
if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
{
+ 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);
+
+ /* Reenable the cache */
+ BV (clib_bihash_cache_enable_disable) (b, 1);
+ h->cache_misses++;
return 0;
}
}
return -1;
}
+u8 *BV (format_bihash_lru) (u8 * s, va_list * args)
+{
+ int i;
+ BVT (clib_bihash_bucket) * b = va_arg (*args, BVT (clib_bihash_bucket) *);
+ u16 cache_lru = b->cache_lru;
+
+ s = format (s, "cache %s, order ", cache_lru & (1 << 15) ? "on" : "off");
+
+ for (i = 0; i < BIHASH_KVP_CACHE_SIZE; i++)
+ s = format (s, "[%d] ", ((cache_lru >> (3 * i)) & 7));
+ return (s);
+}
+
+void
+BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b, u8 slot)
+{
+ BV (clib_bihash_update_lru) (b, slot);
+}
+
u8 *BV (format_bihash) (u8 * s, va_list * args)
{
BVT (clib_bihash) * h = va_arg (*args, BVT (clib_bihash) *);
int verbose = va_arg (*args, int);
- clib_bihash_bucket_t *b;
+ BVT (clib_bihash_bucket) * b;
BVT (clib_bihash_value) * v;
int i, j, k;
u64 active_elements = 0;
@@ -503,7 +564,8 @@ u8 *BV (format_bihash) (u8 * s, va_list * args)
s = format (s, " %lld active elements\n", active_elements);
s = format (s, " %d free lists\n", vec_len (h->freelists));
s = format (s, " %d linear search buckets\n", h->linear_buckets);
-
+ s = format (s, " %lld cache hits, %lld cache misses\n",
+ h->cache_hits, h->cache_misses);
return s;
}
@@ -511,7 +573,7 @@ void BV (clib_bihash_foreach_key_value_pair)
(BVT (clib_bihash) * h, void *callback, void *arg)
{
int i, j, k;
- clib_bihash_bucket_t *b;
+ BVT (clib_bihash_bucket) * b;
BVT (clib_bihash_value) * v;
void (*fp) (BVT (clib_bihash_kv) *, void *) = callback;
diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index 4ea14ff0267..feb6fb68797 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -48,12 +48,10 @@ typedef struct BV (clib_bihash_value)
};
} BVT (clib_bihash_value);
-/*
- * This is shared across all uses of the template, so it needs
- * a "personal" #include recursion block
- */
-#ifndef __defined_clib_bihash_bucket_t__
-#define __defined_clib_bihash_bucket_t__
+#if BIHASH_KVP_CACHE_SIZE > 5
+#error Requested KVP cache LRU data exceeds 16 bits
+#endif
+
typedef struct
{
union
@@ -62,36 +60,139 @@ typedef struct
{
u32 offset;
u8 linear_search;
- u8 pad[2];
u8 log2_pages;
+ u16 cache_lru;
};
u64 as_u64;
};
-} clib_bihash_bucket_t;
-#endif /* __defined_clib_bihash_bucket_t__ */
+ BVT (clib_bihash_kv) cache[BIHASH_KVP_CACHE_SIZE];
+} BVT (clib_bihash_bucket);
typedef struct
{
BVT (clib_bihash_value) * values;
- clib_bihash_bucket_t *buckets;
+ BVT (clib_bihash_bucket) * buckets;
volatile u32 *writer_lock;
BVT (clib_bihash_value) ** working_copies;
int *working_copy_lengths;
- clib_bihash_bucket_t saved_bucket;
+ BVT (clib_bihash_bucket) saved_bucket;
u32 nbuckets;
u32 log2_nbuckets;
u32 linear_buckets;
u8 *name;
+ u64 cache_hits;
+ u64 cache_misses;
+
BVT (clib_bihash_value) ** freelists;
void *mheap;
} BVT (clib_bihash);
-static inline void *BV (clib_bihash_get_value) (const BVT (clib_bihash) * h,
+static inline void
+BV (clib_bihash_update_lru) (BVT (clib_bihash_bucket) * b, u8 slot)
+{
+ u16 value, tmp, mask;
+ u8 found_lru_pos;
+ u16 save_hi;
+
+ if (BIHASH_KVP_CACHE_SIZE < 2)
+ return;
+
+ ASSERT (slot < BIHASH_KVP_CACHE_SIZE);
+
+ /* First, find the slot in cache_lru */
+ mask = slot;
+ if (BIHASH_KVP_CACHE_SIZE > 1)
+ mask |= slot << 3;
+ if (BIHASH_KVP_CACHE_SIZE > 2)
+ mask |= slot << 6;
+ if (BIHASH_KVP_CACHE_SIZE > 3)
+ mask |= slot << 9;
+ if (BIHASH_KVP_CACHE_SIZE > 4)
+ mask |= slot << 12;
+
+ value = b->cache_lru;
+ tmp = value ^ mask;
+
+ /* Already the most-recently used? */
+ if ((tmp & 7) == 0)
+ return;
+
+ found_lru_pos = ((tmp & (7 << 3)) == 0) ? 1 : 0;
+ if (BIHASH_KVP_CACHE_SIZE > 2)
+ found_lru_pos = ((tmp & (7 << 6)) == 0) ? 2 : found_lru_pos;
+ if (BIHASH_KVP_CACHE_SIZE > 3)
+ found_lru_pos = ((tmp & (7 << 9)) == 0) ? 3 : found_lru_pos;
+ if (BIHASH_KVP_CACHE_SIZE > 4)
+ found_lru_pos = ((tmp & (7 << 12)) == 0) ? 4 : found_lru_pos;
+
+ ASSERT (found_lru_pos);
+
+ /* create a mask to kill bits in or above slot */
+ mask = 0xFFFF << found_lru_pos;
+ mask <<= found_lru_pos;
+ mask <<= found_lru_pos;
+ mask ^= 0xFFFF;
+ tmp = value & mask;
+
+ /* Save bits above slot */
+ mask ^= 0xFFFF;
+ mask <<= 3;
+ save_hi = value & mask;
+
+ value = save_hi | (tmp << 3) | slot;
+
+ b->cache_lru = value;
+}
+
+void
+BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b,
+ u8 slot);
+
+static inline u8 BV (clib_bihash_get_lru) (BVT (clib_bihash_bucket) * b)
+{
+ return (b->cache_lru >> (3 * (BIHASH_KVP_CACHE_SIZE - 1))) & 7;
+}
+
+static inline void BV (clib_bihash_reset_cache) (BVT (clib_bihash_bucket) * b)
+{
+ u16 initial_lru_value;
+
+ memset (b->cache, 0xff, sizeof (b->cache));
+
+ /*
+ * We'll want the cache to be loaded from slot 0 -> slot N, so
+ * the initial LRU order is reverse index order.
+ */
+ if (BIHASH_KVP_CACHE_SIZE == 1)
+ initial_lru_value = 0;
+ else if (BIHASH_KVP_CACHE_SIZE == 2)
+ initial_lru_value = (0 << 3) | (1 << 0);
+ else if (BIHASH_KVP_CACHE_SIZE == 3)
+ initial_lru_value = (0 << 6) | (1 << 3) | (2 << 0);
+ else if (BIHASH_KVP_CACHE_SIZE == 4)
+ initial_lru_value = (0 << 9) | (1 << 6) | (2 << 3) | (3 << 0);
+ else if (BIHASH_KVP_CACHE_SIZE == 5)
+ initial_lru_value = (0 << 12) | (1 << 9) | (2 << 6) | (3 << 3) | (4 << 0);
+
+ b->cache_lru = initial_lru_value;
+}
+
+static inline void BV (clib_bihash_cache_enable_disable)
+ (BVT (clib_bihash_bucket) * b, u8 enable)
+{
+ BVT (clib_bihash_bucket) tmp_b;
+ tmp_b.as_u64 = b->as_u64;
+ tmp_b.cache_lru &= 0x7FFF;
+ tmp_b.cache_lru |= enable << 15;
+ b->as_u64 = tmp_b.as_u64;
+}
+
+static inline void *BV (clib_bihash_get_value) (BVT (clib_bihash) * h,
uword offset)
{
u8 *hp = h->mheap;
@@ -100,7 +201,7 @@ static inline void *BV (clib_bihash_get_value) (const BVT (clib_bihash) * h,
return (void *) vp;
}
-static inline uword BV (clib_bihash_get_offset) (const BVT (clib_bihash) * h,
+static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h,
void *v)
{
u8 *hp, *vp;
@@ -119,7 +220,7 @@ void BV (clib_bihash_free) (BVT (clib_bihash) * h);
int BV (clib_bihash_add_del) (BVT (clib_bihash) * h,
BVT (clib_bihash_kv) * add_v, int is_add);
-int BV (clib_bihash_search) (const BVT (clib_bihash) * h,
+int BV (clib_bihash_search) (BVT (clib_bihash) * h,
BVT (clib_bihash_kv) * search_v,
BVT (clib_bihash_kv) * return_v);
@@ -128,18 +229,19 @@ void BV (clib_bihash_foreach_key_value_pair) (BVT (clib_bihash) * h,
format_function_t BV (format_bihash);
format_function_t BV (format_bihash_kvp);
-
+format_function_t BV (format_bihash_lru);
static inline int BV (clib_bihash_search_inline)
- (const BVT (clib_bihash) * h, BVT (clib_bihash_kv) * kvp)
+ (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * key_result)
{
u64 hash;
u32 bucket_index;
BVT (clib_bihash_value) * v;
- clib_bihash_bucket_t *b;
+ BVT (clib_bihash_bucket) * b;
+ BVT (clib_bihash_kv) * kvp;
int i, limit;
- hash = BV (clib_bihash_hash) (kvp);
+ hash = BV (clib_bihash_hash) (key_result);
bucket_index = hash & (h->nbuckets - 1);
b = &h->buckets[bucket_index];
@@ -147,6 +249,22 @@ 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)))
+ {
+ limit = BIHASH_KVP_CACHE_SIZE;
+ kvp = b->cache;
+ for (i = 0; i < limit; i++)
+ {
+ if (BV (clib_bihash_key_compare) (kvp[i].key, key_result->key))
+ {
+ *key_result = kvp[i];
+ h->cache_hits++;
+ return 0;
+ }
+ }
+ }
+
hash >>= h->log2_nbuckets;
v = BV (clib_bihash_get_value) (h, b->offset);
@@ -159,9 +277,22 @@ static inline int BV (clib_bihash_search_inline)
for (i = 0; i < limit; i++)
{
- if (BV (clib_bihash_key_compare) (v->kvp[i].key, kvp->key))
+ if (BV (clib_bihash_key_compare) (v->kvp[i].key, key_result->key))
{
- *kvp = v->kvp[i];
+ 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);
+
+ /* Reenable the cache */
+ BV (clib_bihash_cache_enable_disable) (b, 1);
+ h->cache_misses++;
return 0;
}
}
@@ -169,13 +300,14 @@ static inline int BV (clib_bihash_search_inline)
}
static inline int BV (clib_bihash_search_inline_2)
- (const BVT (clib_bihash) * h,
+ (BVT (clib_bihash) * h,
BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
{
u64 hash;
u32 bucket_index;
BVT (clib_bihash_value) * v;
- clib_bihash_bucket_t *b;
+ BVT (clib_bihash_bucket) * b;
+ BVT (clib_bihash_kv) * kvp;
int i, limit;
ASSERT (valuep);
@@ -188,6 +320,22 @@ 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)))
+ {
+ limit = BIHASH_KVP_CACHE_SIZE;
+ kvp = b->cache;
+ for (i = 0; i < limit; i++)
+ {
+ if (BV (clib_bihash_key_compare) (kvp[i].key, search_key->key))
+ {
+ *valuep = kvp[i];
+ h->cache_hits++;
+ return 0;
+ }
+ }
+ }
+
hash >>= h->log2_nbuckets;
v = BV (clib_bihash_get_value) (h, b->offset);
@@ -201,14 +349,26 @@ static inline int BV (clib_bihash_search_inline_2)
{
if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
{
+ 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);
+
+ /* Reenable the cache */
+ BV (clib_bihash_cache_enable_disable) (b, 1);
+ h->cache_misses++;
return 0;
}
}
return -1;
}
-
#endif /* __included_bihash_template_h__ */
/** @endcond */
diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c
index 1e262430803..589c815dff1 100644
--- a/src/vppinfra/test_bihash_template.c
+++ b/src/vppinfra/test_bihash_template.c
@@ -237,11 +237,44 @@ test_bihash (test_main_t * tm)
}
clib_error_t *
+test_bihash_cache (test_main_t * tm)
+{
+ u32 lru;
+ BVT (clib_bihash_bucket) _b, *b = &_b;
+
+ BV (clib_bihash_reset_cache) (b);
+
+ fformat (stdout, "Initial LRU config: %U\n", BV (format_bihash_lru), b);
+
+ BV (clib_bihash_update_lru_not_inline) (b, 3);
+
+ fformat (stdout, "use slot 3, LRU config: %U\n", BV (format_bihash_lru), b);
+
+ BV (clib_bihash_update_lru) (b, 1);
+
+ fformat (stdout, "use slot 1 LRU config: %U\n", BV (format_bihash_lru), b);
+
+ lru = BV (clib_bihash_get_lru) (b);
+
+ fformat (stdout, "least-recently-used is %d\n", lru);
+
+ BV (clib_bihash_update_lru) (b, 4);
+
+ fformat (stdout, "use slot 4 LRU config: %U\n", BV (format_bihash_lru), b);
+
+ lru = BV (clib_bihash_get_lru) (b);
+
+ fformat (stdout, "least-recently-used is %d\n", lru);
+
+ return 0;
+}
+
+clib_error_t *
test_bihash_main (test_main_t * tm)
{
unformat_input_t *i = tm->input;
clib_error_t *error;
- int test_vec64 = 0;
+ int which = 0;
while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT)
{
@@ -261,7 +294,10 @@ test_bihash_main (test_main_t * tm)
else if (unformat (i, "search %d", &tm->search_iter))
;
else if (unformat (i, "vec64"))
- test_vec64 = 1;
+ which = 1;
+ else if (unformat (i, "cache"))
+ which = 2;
+
else if (unformat (i, "verbose"))
tm->verbose = 1;
else
@@ -269,10 +305,23 @@ test_bihash_main (test_main_t * tm)
format_unformat_error, i);
}
- if (test_vec64)
- error = test_bihash_vec64 (tm);
- else
- error = test_bihash (tm);
+ switch (which)
+ {
+ case 0:
+ error = test_bihash (tm);
+ break;
+
+ case 1:
+ error = test_bihash_vec64 (tm);
+ break;
+
+ case 2:
+ error = test_bihash_cache (tm);
+ break;
+
+ default:
+ return clib_error_return (0, "no such test?");
+ }
return error;
}