From 801ec2a080d9414b3fab80906333bdb94b5d4043 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Tue, 21 Apr 2020 19:42:30 +0200 Subject: [PATCH] vppinfra: improve bihash add/del performance Measured improvement is from 439 to 167 clocks for add operation in 16_8 case... Type: improvement Change-Id: I975ff46ff30b983a3ec80a5cde25ccb68d7fa03b Signed-off-by: Damjan Marion --- src/vppinfra/bihash_template.c | 46 +++++++++++++++++++++++++----------------- src/vppinfra/bihash_template.h | 16 ++++++++------- 2 files changed, 36 insertions(+), 26 deletions(-) diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 89bfc8b6b56..7269959f4a6 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -106,7 +106,7 @@ static void BV (clib_bihash_instantiate) (BVT (clib_bihash) * h) sizeof (BVT (clib_bihash_kv)))); } } - CLIB_MEMORY_BARRIER (); + CLIB_MEMORY_STORE_BARRIER (); h->instantiated = 1; } @@ -433,7 +433,7 @@ BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b) clib_memcpy_fast (working_copy, v, sizeof (*v) * (1 << b->log2_pages)); working_bucket.as_u64 = b->as_u64; working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy); - CLIB_MEMORY_BARRIER (); + CLIB_MEMORY_STORE_BARRIER (); b->as_u64 = working_bucket.as_u64; h->working_copies[thread_index] = working_copy; } @@ -534,14 +534,14 @@ BV (split_and_rehash_linear) return new_values; } -static inline int BV (clib_bihash_add_del_inline) - (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add, +static_always_inline int BV (clib_bihash_add_del_inline_with_hash) + (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, u64 hash, int is_add, int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg) { BVT (clib_bihash_bucket) * b, tmp_b; BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy; int i, limit; - u64 hash, new_hash; + u64 new_hash; u32 new_log2_pages, old_log2_pages; u32 thread_index = os_get_thread_index (); int mark_bucket_linear; @@ -562,8 +562,6 @@ static inline int BV (clib_bihash_add_del_inline) BV (clib_bihash_alloc_unlock) (h); } - hash = BV (clib_bihash_hash) (add_v); - b = BV (clib_bihash_get_bucket) (h, hash); hash >>= h->log2_nbuckets; @@ -587,7 +585,7 @@ static inline int BV (clib_bihash_add_del_inline) tmp_b.as_u64 = 0; /* clears bucket lock */ tmp_b.offset = BV (clib_bihash_get_offset) (h, v); tmp_b.refcnt = 1; - CLIB_MEMORY_BARRIER (); + CLIB_MEMORY_STORE_BARRIER (); b->as_u64 = tmp_b.as_u64; /* unlocks the bucket */ BV (clib_bihash_increment_stat) (h, BIHASH_STAT_alloc_add, 1); @@ -599,9 +597,10 @@ static inline int BV (clib_bihash_add_del_inline) limit = BIHASH_KVP_PER_PAGE; v = BV (clib_bihash_get_value) (h, b->offset); - v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0; if (b->linear_search) limit <<= b->log2_pages; + else + v += hash & ((1 << b->log2_pages) - 1); if (is_add) { @@ -627,8 +626,8 @@ static inline int BV (clib_bihash_add_del_inline) return (-2); } - CLIB_MEMORY_BARRIER (); /* Add a delay */ - clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v)); + clib_memcpy_fast (&(v->kvp[i].value), + &add_v->value, sizeof (add_v->value)); BV (clib_bihash_unlock_bucket) (b); BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1); return (0); @@ -647,7 +646,7 @@ static inline int BV (clib_bihash_add_del_inline) */ clib_memcpy_fast (&(v->kvp[i].value), &add_v->value, sizeof (add_v->value)); - CLIB_MEMORY_BARRIER (); /* Make sure the value has settled */ + CLIB_MEMORY_STORE_BARRIER (); /* Make sure the value has settled */ clib_memcpy_fast (&(v->kvp[i]), &add_v->key, sizeof (add_v->key)); b->refcnt++; @@ -664,8 +663,8 @@ static inline int BV (clib_bihash_add_del_inline) { if (is_stale_cb (&(v->kvp[i]), arg)) { - CLIB_MEMORY_BARRIER (); clib_memcpy_fast (&(v->kvp[i]), add_v, sizeof (*add_v)); + CLIB_MEMORY_STORE_BARRIER (); BV (clib_bihash_unlock_bucket) (b); BV (clib_bihash_increment_stat) (h, BIHASH_STAT_replace, 1); return (0); @@ -681,7 +680,7 @@ static inline int BV (clib_bihash_add_del_inline) /* Found the key? Kill it... */ if (BV (clib_bihash_key_compare) (v->kvp[i].key, add_v->key)) { - clib_memset (&(v->kvp[i]), 0xff, sizeof (*(add_v))); + clib_memset_u8 (&(v->kvp[i]), 0xff, sizeof (*(add_v))); /* Is the bucket empty? */ if (PREDICT_TRUE (b->refcnt > 1)) { @@ -696,14 +695,15 @@ static inline int BV (clib_bihash_add_del_inline) b->linear_search = 0; b->log2_pages = 0; /* Clean up the bucket-level kvp array */ - clib_memset - ((b + 1), 0xff, - BIHASH_KVP_PER_PAGE * sizeof (BVT (clib_bihash_kv))); + clib_memset_u8 ((b + 1), 0xff, BIHASH_KVP_PER_PAGE * + sizeof (BVT (clib_bihash_kv))); + CLIB_MEMORY_STORE_BARRIER (); BV (clib_bihash_unlock_bucket) (b); BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1); goto free_backing_store; } + CLIB_MEMORY_STORE_BARRIER (); BV (clib_bihash_unlock_bucket) (b); BV (clib_bihash_increment_stat) (h, BIHASH_STAT_del, 1); return (0); @@ -712,7 +712,6 @@ static inline int BV (clib_bihash_add_del_inline) { /* Save old bucket value, need log2_pages to free it */ tmp_b.as_u64 = b->as_u64; - CLIB_MEMORY_BARRIER (); /* Kill and unlock the bucket */ b->as_u64 = 0; @@ -818,7 +817,7 @@ expand_ok: tmp_b.refcnt = h->saved_bucket.refcnt + 1; ASSERT (tmp_b.refcnt > 0); tmp_b.lock = 0; - CLIB_MEMORY_BARRIER (); + CLIB_MEMORY_STORE_BARRIER (); b->as_u64 = tmp_b.as_u64; #if BIHASH_KVP_AT_BUCKET_LEVEL @@ -839,6 +838,15 @@ expand_ok: return (0); } +static_always_inline int BV (clib_bihash_add_del_inline) + (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add, + int (*is_stale_cb) (BVT (clib_bihash_kv) *, void *), void *arg) +{ + u64 hash = BV (clib_bihash_hash) (add_v); + return BV (clib_bihash_add_del_inline_with_hash) (h, add_v, hash, is_add, + is_stale_cb, arg); +} + int BV (clib_bihash_add_del) (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * add_v, int is_add) { diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index 13a348fbcf4..b8e0a239013 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -262,23 +262,25 @@ static inline void BV (clib_bihash_lock_bucket) (BVT (clib_bihash_bucket) * b) { BVT (clib_bihash_bucket) unlocked_bucket, locked_bucket; - do + locked_bucket.as_u64 = unlocked_bucket.as_u64 = b->as_u64; + unlocked_bucket.lock = 0; + locked_bucket.lock = 1; + + while (__atomic_compare_exchange_n (&b->as_u64, &unlocked_bucket.as_u64, + locked_bucket.as_u64, 1 /* weak */ , + __ATOMIC_ACQUIRE, + __ATOMIC_ACQUIRE) == 0) { + CLIB_PAUSE (); locked_bucket.as_u64 = unlocked_bucket.as_u64 = b->as_u64; unlocked_bucket.lock = 0; locked_bucket.lock = 1; - CLIB_PAUSE (); } - while (__atomic_compare_exchange_n (&b->as_u64, &unlocked_bucket.as_u64, - locked_bucket.as_u64, 1 /* weak */ , - __ATOMIC_ACQUIRE, - __ATOMIC_ACQUIRE) == 0); } static inline void BV (clib_bihash_unlock_bucket) (BVT (clib_bihash_bucket) * b) { - CLIB_MEMORY_BARRIER (); b->lock = 0; } -- 2.16.6