summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/bihash_template.h
diff options
context:
space:
mode:
authorDave Barach <dave@barachs.net>2016-12-12 15:37:29 -0500
committerDamjan Marion <dmarion.lists@gmail.com>2017-01-02 17:37:00 +0000
commit5e6b9580f202188cbe158368bdbe35c3f39973d7 (patch)
treef4584fc2f989f9cad62a5de9ec33d894033a59a8 /src/vppinfra/bihash_template.h
parent77fabdbcee0123fbdf77060a63515058c1529e66 (diff)
Handle execessive hash collisions, VPP-555
Change-Id: I55dad7b5cfb3d38c22b1105f7d2d61e7449410ea Signed-off-by: Dave Barach <dave@barachs.net>
Diffstat (limited to 'src/vppinfra/bihash_template.h')
-rw-r--r--src/vppinfra/bihash_template.h31
1 files changed, 19 insertions, 12 deletions
diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h
index f70190c63a5..a0a7844cd32 100644
--- a/src/vppinfra/bihash_template.h
+++ b/src/vppinfra/bihash_template.h
@@ -61,7 +61,8 @@ typedef struct
struct
{
u32 offset;
- u8 pad[3];
+ u8 linear_search;
+ u8 pad[2];
u8 log2_pages;
};
u64 as_u64;
@@ -80,6 +81,7 @@ typedef struct
u32 nbuckets;
u32 log2_nbuckets;
+ u32 linear_buckets;
u8 *name;
BVT (clib_bihash_value) ** freelists;
@@ -132,10 +134,9 @@ static inline int BV (clib_bihash_search_inline)
{
u64 hash;
u32 bucket_index;
- uword value_index;
BVT (clib_bihash_value) * v;
clib_bihash_bucket_t *b;
- int i;
+ int i, limit;
hash = BV (clib_bihash_hash) (kvp);
@@ -148,10 +149,14 @@ static inline int BV (clib_bihash_search_inline)
hash >>= h->log2_nbuckets;
v = BV (clib_bihash_get_value) (h, b->offset);
- value_index = hash & ((1 << b->log2_pages) - 1);
- v += value_index;
- for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
+ /* If the bucket has unresolvable collisions, use linear search */
+ limit = BIHASH_KVP_PER_PAGE;
+ v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
+ if (PREDICT_FALSE (b->linear_search))
+ limit <<= b->log2_pages;
+
+ for (i = 0; i < limit; i++)
{
if (BV (clib_bihash_key_compare) (v->kvp[i].key, kvp->key))
{
@@ -168,10 +173,9 @@ static inline int BV (clib_bihash_search_inline_2)
{
u64 hash;
u32 bucket_index;
- uword value_index;
BVT (clib_bihash_value) * v;
clib_bihash_bucket_t *b;
- int i;
+ int i, limit;
ASSERT (valuep);
@@ -184,12 +188,15 @@ static inline int BV (clib_bihash_search_inline_2)
return -1;
hash >>= h->log2_nbuckets;
-
v = BV (clib_bihash_get_value) (h, b->offset);
- value_index = hash & ((1 << b->log2_pages) - 1);
- v += value_index;
- for (i = 0; i < BIHASH_KVP_PER_PAGE; i++)
+ /* If the bucket has unresolvable collisions, use linear search */
+ limit = BIHASH_KVP_PER_PAGE;
+ v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0;
+ if (PREDICT_FALSE (b->linear_search))
+ limit <<= b->log2_pages;
+
+ for (i = 0; i < limit; i++)
{
if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key))
{