X-Git-Url: https://gerrit.fd.io/r/gitweb?a=blobdiff_plain;ds=sidebyside;f=src%2Fvppinfra%2Fbihash_template.c;h=004e8a9a55873b548f063b98f319c81e92074967;hb=7968e6cad5fac28568162945e2e57556740013fd;hp=d8b97b5f3d08b8319eaf12f2cf4ed426b7d6747e;hpb=8f544964a3df144a441b136c2a01427eca731eea;p=vpp.git diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index d8b97b5f3d0..004e8a9a558 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -55,7 +55,8 @@ BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages) oldheap = clib_mem_set_heap (h->mheap); vec_validate (h->freelists, log2_pages); - vec_validate_aligned (rv, (1 << log2_pages) - 1, CLIB_CACHE_LINE_BYTES); + rv = clib_mem_alloc_aligned ((sizeof (*rv) * (1 << log2_pages)), + CLIB_CACHE_LINE_BYTES); clib_mem_set_heap (oldheap); goto initialize; } @@ -64,7 +65,6 @@ BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages) initialize: ASSERT (rv); - ASSERT (vec_len (rv) == (1 << log2_pages)); /* * Latest gcc complains that the length arg is zero * if we replace (1<writer_lock[0]); - log2_pages = min_log2 (vec_len (v)); - ASSERT (vec_len (h->freelists) > log2_pages); v->next_free = h->freelists[log2_pages]; @@ -96,12 +93,14 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b) clib_bihash_bucket_t working_bucket __attribute__ ((aligned (8))); void *oldheap; BVT (clib_bihash_value) * working_copy; - u32 cpu_number = os_get_cpu_number (); + u32 thread_index = os_get_thread_index (); + int log2_working_copy_length; - if (cpu_number >= vec_len (h->working_copies)) + if (thread_index >= vec_len (h->working_copies)) { oldheap = clib_mem_set_heap (h->mheap); - vec_validate (h->working_copies, cpu_number); + vec_validate (h->working_copies, thread_index); + vec_validate_init_empty (h->working_copy_lengths, thread_index, ~0); clib_mem_set_heap (oldheap); } @@ -110,19 +109,24 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b) * updates from multiple threads will not result in sporadic, spurious * lookup failures. */ - working_copy = h->working_copies[cpu_number]; + working_copy = h->working_copies[thread_index]; + log2_working_copy_length = h->working_copy_lengths[thread_index]; h->saved_bucket.as_u64 = b->as_u64; oldheap = clib_mem_set_heap (h->mheap); - if ((1 << b->log2_pages) > vec_len (working_copy)) + if (b->log2_pages > log2_working_copy_length) { - vec_validate_aligned (working_copy, (1 << b->log2_pages) - 1, - sizeof (u64)); - h->working_copies[cpu_number] = working_copy; + if (working_copy) + clib_mem_free (working_copy); + + working_copy = clib_mem_alloc_aligned + (sizeof (working_copy[0]) * (1 << b->log2_pages), + CLIB_CACHE_LINE_BYTES); + h->working_copy_lengths[thread_index] = b->log2_pages; + h->working_copies[thread_index] = working_copy; } - _vec_len (working_copy) = 1 << b->log2_pages; clib_mem_set_heap (oldheap); v = BV (clib_bihash_get_value) (h, b->offset); @@ -132,22 +136,23 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b) working_bucket.offset = BV (clib_bihash_get_offset) (h, working_copy); CLIB_MEMORY_BARRIER (); b->as_u64 = working_bucket.as_u64; - h->working_copies[cpu_number] = working_copy; + h->working_copies[thread_index] = working_copy; } static BVT (clib_bihash_value) * BV (split_and_rehash) (BVT (clib_bihash) * h, - BVT (clib_bihash_value) * old_values, u32 new_log2_pages) + BVT (clib_bihash_value) * old_values, u32 old_log2_pages, + u32 new_log2_pages) { BVT (clib_bihash_value) * new_values, *new_v; - int i, j, length; + int i, j, length_in_kvs; new_values = BV (value_alloc) (h, new_log2_pages); - length = vec_len (old_values) * BIHASH_KVP_PER_PAGE; + length_in_kvs = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE; - for (i = 0; i < length; i++) + for (i = 0; i < length_in_kvs; i++) { u64 new_hash; @@ -173,10 +178,11 @@ BV (split_and_rehash) } } /* Crap. Tell caller to try again */ - BV (value_free) (h, new_values); + BV (value_free) (h, new_values, new_log2_pages); return 0; doublebreak:; } + return new_values; } @@ -184,17 +190,19 @@ static BVT (clib_bihash_value) * BV (split_and_rehash_linear) (BVT (clib_bihash) * h, - BVT (clib_bihash_value) * old_values, u32 new_log2_pages) + BVT (clib_bihash_value) * old_values, u32 old_log2_pages, + u32 new_log2_pages) { BVT (clib_bihash_value) * new_values; - int i, j, new_length; + int i, j, new_length, old_length; new_values = BV (value_alloc) (h, new_log2_pages); new_length = (1 << new_log2_pages) * BIHASH_KVP_PER_PAGE; + old_length = (1 << old_log2_pages) * BIHASH_KVP_PER_PAGE; j = 0; /* Across the old value array */ - for (i = 0; i < vec_len (old_values) * BIHASH_KVP_PER_PAGE; i++) + for (i = 0; i < old_length; i++) { /* Find a free slot in the new linear scan bucket */ for (; j < new_length; j++) @@ -215,7 +223,7 @@ BV (split_and_rehash_linear) } /* This should never happen... */ clib_warning ("BUG: linear rehash failed!"); - BV (value_free) (h, new_values); + BV (value_free) (h, new_values, new_log2_pages); return 0; doublebreak:; @@ -232,8 +240,8 @@ int BV (clib_bihash_add_del) int rv = 0; int i, limit; u64 hash, new_hash; - u32 new_log2_pages; - u32 cpu_number = os_get_cpu_number (); + u32 new_log2_pages, old_log2_pages; + u32 thread_index = os_get_thread_index (); int mark_bucket_linear; int resplit_once; @@ -244,6 +252,8 @@ int BV (clib_bihash_add_del) hash >>= h->log2_nbuckets; + tmp_b.linear_search = 0; + while (__sync_lock_test_and_set (h->writer_lock, 1)) ; @@ -257,6 +267,7 @@ int BV (clib_bihash_add_del) } v = BV (value_alloc) (h, 0); + *v->kvp = *add_v; tmp_b.as_u64 = 0; tmp_b.offset = BV (clib_bihash_get_offset) (h, v); @@ -320,27 +331,31 @@ int BV (clib_bihash_add_del) goto unlock; } - new_log2_pages = h->saved_bucket.log2_pages + 1; + old_log2_pages = h->saved_bucket.log2_pages; + new_log2_pages = old_log2_pages + 1; mark_bucket_linear = 0; - working_copy = h->working_copies[cpu_number]; + working_copy = h->working_copies[thread_index]; resplit_once = 0; - new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages); + new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages, + new_log2_pages); if (new_v == 0) { try_resplit: resplit_once = 1; new_log2_pages++; /* Try re-splitting. If that fails, fall back to linear search */ - new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages); + new_v = BV (split_and_rehash) (h, working_copy, old_log2_pages, + new_log2_pages); if (new_v == 0) { mark_linear: new_log2_pages--; /* pinned collisions, use linear search */ new_v = - BV (split_and_rehash_linear) (h, working_copy, new_log2_pages); + BV (split_and_rehash_linear) (h, working_copy, old_log2_pages, + new_log2_pages); mark_bucket_linear = 1; } } @@ -363,8 +378,9 @@ int BV (clib_bihash_add_del) goto expand_ok; } } + /* Crap. Try again */ - BV (value_free) (h, save_new_v); + BV (value_free) (h, save_new_v, new_log2_pages); /* * If we've already doubled the size of the bucket once, * fall back to linear search now. @@ -382,10 +398,11 @@ expand_ok: tmp_b.log2_pages = new_log2_pages; tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v); tmp_b.linear_search = mark_bucket_linear; + CLIB_MEMORY_BARRIER (); b->as_u64 = tmp_b.as_u64; v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset); - BV (value_free) (h, v); + BV (value_free) (h, v, old_log2_pages); unlock: CLIB_MEMORY_BARRIER ();