summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/bihash_template.c
diff options
context:
space:
mode:
authorDave Barach <dave@barachs.net>2017-07-14 12:42:21 -0400
committerJohn Lo <loj@cisco.com>2017-07-19 23:25:43 +0000
commit908a5ea6e247b4a15f0ec7e8ee8ebff799abdc4f (patch)
tree8fa18f75cce531e266535dd4bbddd24f0cc15c9a /src/vppinfra/bihash_template.c
parentc4423229e2ed51084fb277570bfde097abaf7c97 (diff)
Add a bihash prefetchable bucket-level cache
According to Maciek, the easiest way to leverage the csit "performance trend" job is to actually merge the patch once verified. Manual testing indicates that the patch improves l2 path performance. Other use-cases are TBD. It's possible that we'll need to back out the patch depending on what happens. Change-Id: Ic0a0363de35ef9be953ad7709c57c3936b73fd5a Signed-off-by: Dave Barach <dave@barachs.net>
Diffstat (limited to 'src/vppinfra/bihash_template.c')
-rw-r--r--src/vppinfra/bihash_template.c78
1 files changed, 70 insertions, 8 deletions
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;