From 7cd468a3d7dee7d6c92f69a0bb7061ae208ec727 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Mon, 19 Dec 2016 23:05:39 +0100 Subject: Reorganize source tree to use single autotools instance Change-Id: I7b51f88292e057c6443b12224486f2d0c9f8ae23 Signed-off-by: Damjan Marion --- src/vppinfra/bihash_template.c | 455 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 455 insertions(+) create mode 100644 src/vppinfra/bihash_template.c (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c new file mode 100644 index 00000000..4b0b4257 --- /dev/null +++ b/src/vppinfra/bihash_template.c @@ -0,0 +1,455 @@ +/* + * Copyright (c) 2015 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** @cond DOCUMENTATION_IS_IN_BIHASH_DOC_H */ + +void BV (clib_bihash_init) + (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size) +{ + void *oldheap; + + nbuckets = 1 << (max_log2 (nbuckets)); + + h->name = (u8 *) name; + h->nbuckets = nbuckets; + h->log2_nbuckets = max_log2 (nbuckets); + + h->mheap = mheap_alloc (0 /* use VM */ , memory_size); + + oldheap = clib_mem_set_heap (h->mheap); + vec_validate_aligned (h->buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES); + h->writer_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES, + CLIB_CACHE_LINE_BYTES); + + clib_mem_set_heap (oldheap); +} + +void BV (clib_bihash_free) (BVT (clib_bihash) * h) +{ + mheap_free (h->mheap); + memset (h, 0, sizeof (*h)); +} + +static +BVT (clib_bihash_value) * +BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages) +{ + BVT (clib_bihash_value) * rv = 0; + void *oldheap; + + ASSERT (h->writer_lock[0]); + if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0) + { + 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); + clib_mem_set_heap (oldheap); + goto initialize; + } + rv = h->freelists[log2_pages]; + h->freelists[log2_pages] = rv->next_free; + +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]; + h->freelists[log2_pages] = v; +} + +static inline void +BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b) +{ + BVT (clib_bihash_value) * v; + clib_bihash_bucket_t working_bucket __attribute__ ((aligned (8))); + void *oldheap; + BVT (clib_bihash_value) * working_copy; + u32 cpu_number = os_get_cpu_number (); + + if (cpu_number >= vec_len (h->working_copies)) + { + oldheap = clib_mem_set_heap (h->mheap); + vec_validate (h->working_copies, cpu_number); + clib_mem_set_heap (oldheap); + } + + /* + * working_copies are per-cpu so that near-simultaneous + * updates from multiple threads will not result in sporadic, spurious + * lookup failures. + */ + working_copy = h->working_copies[cpu_number]; + + h->saved_bucket.as_u64 = b->as_u64; + oldheap = clib_mem_set_heap (h->mheap); + + if ((1 << b->log2_pages) > vec_len (working_copy)) + { + vec_validate_aligned (working_copy, (1 << b->log2_pages) - 1, + sizeof (u64)); + h->working_copies[cpu_number] = working_copy; + } + + _vec_len (working_copy) = 1 << b->log2_pages; + clib_mem_set_heap (oldheap); + + v = BV (clib_bihash_get_value) (h, b->offset); + + clib_memcpy (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 (); + b->as_u64 = working_bucket.as_u64; + h->working_copies[cpu_number] = 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) * new_values, *v, *new_v; + int i, j, k; + + new_values = BV (value_alloc) (h, new_log2_pages); + + v = old_values; + for (i = 0; i < vec_len (old_values); i++) + { + u64 new_hash; + + for (j = 0; j < BIHASH_KVP_PER_PAGE; j++) + { + if (BV (clib_bihash_is_free) (&(v->kvp[j])) == 0) + { + new_hash = BV (clib_bihash_hash) (&(v->kvp[j])); + new_hash >>= h->log2_nbuckets; + new_hash &= (1 << new_log2_pages) - 1; + + new_v = &new_values[new_hash]; + + for (k = 0; k < BIHASH_KVP_PER_PAGE; k++) + { + if (BV (clib_bihash_is_free) (&(new_v->kvp[k]))) + { + clib_memcpy (&(new_v->kvp[k]), &(v->kvp[j]), + sizeof (new_v->kvp[k])); + goto doublebreak; + } + } + /* Crap. Tell caller to try again */ + BV (value_free) (h, new_values); + return 0; + } + doublebreak: + ; + } + v++; + } + return new_values; +} + +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_value) * v, *new_v, *save_new_v, *working_copy; + u32 value_index; + int rv = 0; + int i; + u64 hash, new_hash; + u32 new_log2_pages; + u32 cpu_number = os_get_cpu_number (); + + hash = BV (clib_bihash_hash) (add_v); + + bucket_index = hash & (h->nbuckets - 1); + b = &h->buckets[bucket_index]; + + hash >>= h->log2_nbuckets; + + while (__sync_lock_test_and_set (h->writer_lock, 1)) + ; + + /* First elt in the bucket? */ + if (b->offset == 0) + { + if (is_add == 0) + { + rv = -1; + goto unlock; + } + + 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); + + b->as_u64 = tmp_b.as_u64; + goto unlock; + } + + BV (make_working_copy) (h, b); + + v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset); + value_index = hash & ((1 << h->saved_bucket.log2_pages) - 1); + v += value_index; + + if (is_add) + { + /* + * For obvious (in hindsight) reasons, see if we're supposed to + * replace an existing key, then look for an empty slot. + */ + for (i = 0; i < BIHASH_KVP_PER_PAGE; i++) + { + if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key))) + { + clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v)); + CLIB_MEMORY_BARRIER (); + /* Restore the previous (k,v) pairs */ + b->as_u64 = h->saved_bucket.as_u64; + goto unlock; + } + } + for (i = 0; i < BIHASH_KVP_PER_PAGE; i++) + { + if (BV (clib_bihash_is_free) (&(v->kvp[i]))) + { + clib_memcpy (&(v->kvp[i]), add_v, sizeof (*add_v)); + CLIB_MEMORY_BARRIER (); + b->as_u64 = h->saved_bucket.as_u64; + goto unlock; + } + } + /* no room at the inn... split case... */ + } + else + { + for (i = 0; i < BIHASH_KVP_PER_PAGE; i++) + { + if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key))) + { + memset (&(v->kvp[i]), 0xff, sizeof (*(add_v))); + CLIB_MEMORY_BARRIER (); + b->as_u64 = h->saved_bucket.as_u64; + goto unlock; + } + } + rv = -3; + b->as_u64 = h->saved_bucket.as_u64; + goto unlock; + } + + new_log2_pages = h->saved_bucket.log2_pages + 1; + +expand_again: + working_copy = h->working_copies[cpu_number]; + new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages); + if (new_v == 0) + { + new_log2_pages++; + goto expand_again; + } + + /* Try to add the new entry */ + save_new_v = new_v; + new_hash = BV (clib_bihash_hash) (add_v); + new_hash >>= h->log2_nbuckets; + new_hash &= (1 << min_log2 (vec_len (new_v))) - 1; + new_v += new_hash; + + for (i = 0; i < BIHASH_KVP_PER_PAGE; i++) + { + if (BV (clib_bihash_is_free) (&(new_v->kvp[i]))) + { + clib_memcpy (&(new_v->kvp[i]), add_v, sizeof (*add_v)); + goto expand_ok; + } + } + /* Crap. Try again */ + new_log2_pages++; + BV (value_free) (h, save_new_v); + goto expand_again; + +expand_ok: + tmp_b.log2_pages = min_log2 (vec_len (save_new_v)); + tmp_b.offset = BV (clib_bihash_get_offset) (h, save_new_v); + 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); + +unlock: + CLIB_MEMORY_BARRIER (); + h->writer_lock[0] = 0; + return rv; +} + +int BV (clib_bihash_search) + (const BVT (clib_bihash) * h, + BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep) +{ + u64 hash; + u32 bucket_index; + uword value_index; + BVT (clib_bihash_value) * v; + clib_bihash_bucket_t *b; + int i; + + ASSERT (valuep); + + hash = BV (clib_bihash_hash) (search_key); + + bucket_index = hash & (h->nbuckets - 1); + b = &h->buckets[bucket_index]; + + if (b->offset == 0) + 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 (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key)) + { + *valuep = v->kvp[i]; + return 0; + } + } + return -1; +} + +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_value) * v; + int i, j, k; + u64 active_elements = 0; + + s = format (s, "Hash table %s\n", h->name ? h->name : (u8 *) "(unnamed)"); + + for (i = 0; i < h->nbuckets; i++) + { + b = &h->buckets[i]; + if (b->offset == 0) + { + if (verbose > 1) + s = format (s, "[%d]: empty\n", i); + continue; + } + + if (verbose) + { + s = format (s, "[%d]: heap offset %d, len %d\n", i, + b->offset, (1 << b->log2_pages)); + } + + v = BV (clib_bihash_get_value) (h, b->offset); + for (j = 0; j < (1 << b->log2_pages); j++) + { + for (k = 0; k < BIHASH_KVP_PER_PAGE; k++) + { + if (BV (clib_bihash_is_free) (&v->kvp[k])) + { + if (verbose > 1) + s = format (s, " %d: empty\n", + j * BIHASH_KVP_PER_PAGE + k); + continue; + } + if (verbose) + { + s = format (s, " %d: %U\n", + j * BIHASH_KVP_PER_PAGE + k, + BV (format_bihash_kvp), &(v->kvp[k])); + } + active_elements++; + } + v++; + } + } + + s = format (s, " %lld active elements\n", active_elements); + s = format (s, " %d free lists\n", vec_len (h->freelists)); + + return s; +} + +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_value) * v; + void (*fp) (BVT (clib_bihash_kv) *, void *) = callback; + + for (i = 0; i < h->nbuckets; i++) + { + b = &h->buckets[i]; + if (b->offset == 0) + continue; + + v = BV (clib_bihash_get_value) (h, b->offset); + for (j = 0; j < (1 << b->log2_pages); j++) + { + for (k = 0; k < BIHASH_KVP_PER_PAGE; k++) + { + if (BV (clib_bihash_is_free) (&v->kvp[k])) + continue; + + (*fp) (&v->kvp[k], arg); + } + v++; + } + } +} + +/** @endcond */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ -- cgit 1.2.3-korg From 5e6b9580f202188cbe158368bdbe35c3f39973d7 Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Mon, 12 Dec 2016 15:37:29 -0500 Subject: Handle execessive hash collisions, VPP-555 Change-Id: I55dad7b5cfb3d38c22b1105f7d2d61e7449410ea Signed-off-by: Dave Barach --- src/vppinfra/bihash_8_8.h | 1 + src/vppinfra/bihash_template.c | 166 ++++++++++++++++++++++++++---------- src/vppinfra/bihash_template.h | 31 ++++--- src/vppinfra/test_bihash_template.c | 32 ++----- 4 files changed, 146 insertions(+), 84 deletions(-) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/vppinfra/bihash_8_8.h b/src/vppinfra/bihash_8_8.h index a0d6df2e..d70da596 100644 --- a/src/vppinfra/bihash_8_8.h +++ b/src/vppinfra/bihash_8_8.h @@ -53,6 +53,7 @@ clib_bihash_is_free_8_8 (clib_bihash_kv_8_8_t * v) static inline u64 clib_bihash_hash_8_8 (clib_bihash_kv_8_8_t * v) { + /* Note: to torture-test linear scan, make this fn return a constant */ #if __SSE4_2__ return _mm_crc32_u64 (0, v->key); #else diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 4b0b4257..7c817a20 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -141,43 +141,83 @@ BV (split_and_rehash) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * old_values, u32 new_log2_pages) { - BVT (clib_bihash_value) * new_values, *v, *new_v; - int i, j, k; + BVT (clib_bihash_value) * new_values, *new_v; + int i, j, length; new_values = BV (value_alloc) (h, new_log2_pages); + length = vec_len (old_values) * BIHASH_KVP_PER_PAGE; - v = old_values; - for (i = 0; i < vec_len (old_values); i++) + for (i = 0; i < length; i++) { u64 new_hash; + /* Entry not in use? Forget it */ + if (BV (clib_bihash_is_free) (&(old_values->kvp[i]))) + continue; + + /* rehash the item onto its new home-page */ + new_hash = BV (clib_bihash_hash) (&(old_values->kvp[i])); + new_hash >>= h->log2_nbuckets; + new_hash &= (1 << new_log2_pages) - 1; + new_v = &new_values[new_hash]; + + /* Across the new home-page */ for (j = 0; j < BIHASH_KVP_PER_PAGE; j++) { - if (BV (clib_bihash_is_free) (&(v->kvp[j])) == 0) + /* Empty slot */ + if (BV (clib_bihash_is_free) (&(new_v->kvp[j]))) { - new_hash = BV (clib_bihash_hash) (&(v->kvp[j])); - new_hash >>= h->log2_nbuckets; - new_hash &= (1 << new_log2_pages) - 1; + clib_memcpy (&(new_v->kvp[j]), &(old_values->kvp[i]), + sizeof (new_v->kvp[j])); + goto doublebreak; + } + } + /* Crap. Tell caller to try again */ + BV (value_free) (h, new_values); + return 0; + doublebreak:; + } + return new_values; +} - new_v = &new_values[new_hash]; +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) * new_values; + int i, j, new_length; - for (k = 0; k < BIHASH_KVP_PER_PAGE; k++) - { - if (BV (clib_bihash_is_free) (&(new_v->kvp[k]))) - { - clib_memcpy (&(new_v->kvp[k]), &(v->kvp[j]), - sizeof (new_v->kvp[k])); - goto doublebreak; - } - } - /* Crap. Tell caller to try again */ - BV (value_free) (h, new_values); - return 0; + new_values = BV (value_alloc) (h, new_log2_pages); + new_length = (1 << new_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++) + { + /* Find a free slot in the new linear scan bucket */ + for (; j < new_length; j++) + { + /* Old value in use? Forget it. */ + if (BV (clib_bihash_is_free) (&(old_values->kvp[i]))) + goto doublebreak; + + /* New value should never be in use */ + if (BV (clib_bihash_is_free) (&(new_values->kvp[j]))) + { + /* Copy the old value and move along */ + clib_memcpy (&(new_values->kvp[j]), &(old_values->kvp[i]), + sizeof (new_values->kvp[j])); + j++; + goto doublebreak; } - doublebreak: - ; + /* This should never happen... */ + clib_warning ("BUG: linear rehash failed!"); + BV (value_free) (h, new_values); + return 0; } - v++; + doublebreak:; } return new_values; } @@ -188,12 +228,13 @@ int BV (clib_bihash_add_del) u32 bucket_index; clib_bihash_bucket_t *b, tmp_b; BVT (clib_bihash_value) * v, *new_v, *save_new_v, *working_copy; - u32 value_index; int rv = 0; - int i; + int i, limit; u64 hash, new_hash; u32 new_log2_pages; u32 cpu_number = os_get_cpu_number (); + int mark_bucket_linear; + int resplit_once; hash = BV (clib_bihash_hash) (add_v); @@ -226,8 +267,11 @@ int BV (clib_bihash_add_del) BV (make_working_copy) (h, b); v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset); - value_index = hash & ((1 << h->saved_bucket.log2_pages) - 1); - v += value_index; + + limit = BIHASH_KVP_PER_PAGE; + v += (b->linear_search == 0) ? hash & ((1 << b->log2_pages) - 1) : 0; + if (b->linear_search) + limit <<= b->log2_pages; if (is_add) { @@ -235,7 +279,7 @@ int BV (clib_bihash_add_del) * For obvious (in hindsight) reasons, see if we're supposed to * replace an existing key, then look for an empty slot. */ - for (i = 0; i < BIHASH_KVP_PER_PAGE; i++) + for (i = 0; i < limit; i++) { if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key))) { @@ -246,7 +290,7 @@ int BV (clib_bihash_add_del) goto unlock; } } - for (i = 0; i < BIHASH_KVP_PER_PAGE; i++) + for (i = 0; i < limit; i++) { if (BV (clib_bihash_is_free) (&(v->kvp[i]))) { @@ -260,7 +304,7 @@ int BV (clib_bihash_add_del) } else { - for (i = 0; i < BIHASH_KVP_PER_PAGE; i++) + for (i = 0; i < limit; i++) { if (!memcmp (&(v->kvp[i]), &add_v->key, sizeof (add_v->key))) { @@ -276,24 +320,41 @@ int BV (clib_bihash_add_del) } new_log2_pages = h->saved_bucket.log2_pages + 1; + mark_bucket_linear = 0; -expand_again: working_copy = h->working_copies[cpu_number]; + resplit_once = 0; + new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages); if (new_v == 0) { + try_resplit: + resplit_once = 1; new_log2_pages++; - goto expand_again; + /* Try re-splitting. If that fails, fall back to linear search */ + new_v = BV (split_and_rehash) (h, working_copy, 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); + mark_bucket_linear = 1; + } } /* Try to add the new entry */ save_new_v = new_v; new_hash = BV (clib_bihash_hash) (add_v); + limit = BIHASH_KVP_PER_PAGE; + if (mark_bucket_linear) + limit <<= new_log2_pages; new_hash >>= h->log2_nbuckets; - new_hash &= (1 << min_log2 (vec_len (new_v))) - 1; - new_v += new_hash; + new_hash &= (1 << new_log2_pages) - 1; + new_v += mark_bucket_linear ? 0 : new_hash; - for (i = 0; i < BIHASH_KVP_PER_PAGE; i++) + for (i = 0; i < limit; i++) { if (BV (clib_bihash_is_free) (&(new_v->kvp[i]))) { @@ -302,13 +363,24 @@ expand_again: } } /* Crap. Try again */ - new_log2_pages++; BV (value_free) (h, save_new_v); - goto expand_again; + /* + * If we've already doubled the size of the bucket once, + * fall back to linear search now. + */ + if (resplit_once) + goto mark_linear; + else + goto try_resplit; expand_ok: - tmp_b.log2_pages = min_log2 (vec_len (save_new_v)); + /* Keep track of the number of linear-scan buckets */ + if (tmp_b.linear_search ^ mark_bucket_linear) + h->linear_buckets += (mark_bucket_linear == 1) ? 1 : -1; + + 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); @@ -326,10 +398,9 @@ int BV (clib_bihash_search) { 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); @@ -344,10 +415,12 @@ int BV (clib_bihash_search) hash >>= h->log2_nbuckets; v = BV (clib_bihash_get_value) (h, b->offset); - value_index = hash & ((1 << b->log2_pages) - 1); - v += value_index; + 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 < BIHASH_KVP_PER_PAGE; i++) + for (i = 0; i < limit; i++) { if (BV (clib_bihash_key_compare) (v->kvp[i].key, search_key->key)) { @@ -381,8 +454,8 @@ u8 *BV (format_bihash) (u8 * s, va_list * args) if (verbose) { - s = format (s, "[%d]: heap offset %d, len %d\n", i, - b->offset, (1 << b->log2_pages)); + s = format (s, "[%d]: heap offset %d, len %d, linear %d\n", i, + b->offset, (1 << b->log2_pages), b->linear_search); } v = BV (clib_bihash_get_value) (h, b->offset); @@ -411,6 +484,7 @@ 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); return s; } diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index f70190c6..a0a7844c 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)) { diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c index c505bd83..ef03f565 100644 --- a/src/vppinfra/test_bihash_template.c +++ b/src/vppinfra/test_bihash_template.c @@ -111,37 +111,17 @@ test_bihash (test_main_t * tm) for (j = 0; j < tm->search_iter; j++) { - u64 hash1 = clib_xxhash (tm->keys[0]); - for (i = 0; i < tm->nitems; i++) { - if (i < (tm->nitems - 3)) - { - clib_bihash_bucket_t *b; - BVT (clib_bihash_value) * v; - u64 hash2 = clib_xxhash (tm->keys[i + 3]); - u32 bucket_index = hash2 & (h->nbuckets - 1); - b = &h->buckets[bucket_index]; - CLIB_PREFETCH (b, CLIB_CACHE_LINE_BYTES, LOAD); - - bucket_index = hash1 & (h->nbuckets - 1); - b = &h->buckets[bucket_index]; - v = BV (clib_bihash_get_value) (h, b->offset); - hash1 >>= h->log2_nbuckets; - hash1 = hash1 & ((1 << b->log2_pages) - 1); - v += hash1; - CLIB_PREFETCH (v, CLIB_CACHE_LINE_BYTES, LOAD); - - hash1 = hash2; - } - kv.key = tm->keys[i]; if (BV (clib_bihash_search) (h, &kv, &kv) < 0) - clib_warning ("search for key %lld failed unexpectedly\n", - tm->keys[i]); + if (BV (clib_bihash_search) (h, &kv, &kv) < 0) + clib_warning ("[%d] search for key %lld failed unexpectedly\n", + i, tm->keys[i]); if (kv.value != (u64) (i + 1)) - clib_warning ("search for key %lld returned %lld, not %lld\n", - tm->keys, kv.value, (u64) (i + 1)); + clib_warning + ("[%d] search for key %lld returned %lld, not %lld\n", i, + tm->keys, kv.value, (u64) (i + 1)); } } -- cgit 1.2.3-korg From 8f544964a3df144a441b136c2a01427eca731eea Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Wed, 18 Jan 2017 10:23:22 -0500 Subject: Fix coverity warnings, VPP-608 Change-Id: Ib0144ba3a9a09971d3946c932e8fed6d5c1ad278 Signed-off-by: Dave Barach --- src/plugins/snat/in2out.c | 8 ++++++-- src/plugins/snat/out2in.c | 8 ++++++-- src/vnet/devices/virtio/vhost-user.c | 8 ++++++-- src/vnet/unix/tapcli.c | 5 +++-- src/vpp/api/api_main.c | 10 +++++----- src/vppinfra/bihash_template.c | 11 ++++++----- 6 files changed, 32 insertions(+), 18 deletions(-) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/plugins/snat/in2out.c b/src/plugins/snat/in2out.c index 76a6a12c..ba752cf0 100644 --- a/src/plugins/snat/in2out.c +++ b/src/plugins/snat/in2out.c @@ -1232,8 +1232,12 @@ snat_in2out_worker_handoff_fn (vlib_main_t * vm, if (clib_bihash_search_8_8 (&sm->worker_by_in, &kv0, &value0)) { /* No, assign next available worker (RR) */ - next_worker_index = sm->first_worker_index + - sm->workers[sm->next_worker++ % vec_len (sm->workers)]; + next_worker_index = sm->first_worker_index; + if (vec_len (sm->workers)) + { + next_worker_index += + sm->workers[sm->next_worker++ % _vec_len (sm->workers)]; + } /* add non-traslated packets worker lookup */ kv0.value = next_worker_index; diff --git a/src/plugins/snat/out2in.c b/src/plugins/snat/out2in.c index f1329733..855e9efb 100644 --- a/src/plugins/snat/out2in.c +++ b/src/plugins/snat/out2in.c @@ -901,8 +901,12 @@ snat_out2in_worker_handoff_fn (vlib_main_t * vm, if (clib_bihash_search_8_8 (&sm->worker_by_out, &kv0, &value0)) { /* No, assign next available worker (RR) */ - next_worker_index = sm->first_worker_index + - sm->workers[sm->next_worker++ % vec_len (sm->workers)]; + next_worker_index = sm->first_worker_index; + if (vec_len (sm->workers)) + { + next_worker_index += + sm->workers[sm->next_worker++ % _vec_len (sm->workers)]; + } } else { diff --git a/src/vnet/devices/virtio/vhost-user.c b/src/vnet/devices/virtio/vhost-user.c index 9a7c1dc0..ac142867 100644 --- a/src/vnet/devices/virtio/vhost-user.c +++ b/src/vnet/devices/virtio/vhost-user.c @@ -2326,12 +2326,16 @@ vhost_user_process (vlib_main_t * vm, sizeof (sun.sun_path) - 1); /* Avoid hanging VPP if the other end does not accept */ - fcntl(sockfd, F_SETFL, O_NONBLOCK); + if (fcntl(sockfd, F_SETFL, O_NONBLOCK) < 0) + clib_unix_warning ("fcntl"); + if (connect (sockfd, (struct sockaddr *) &sun, sizeof (struct sockaddr_un)) == 0) { /* Set the socket to blocking as it was before */ - fcntl(sockfd, F_SETFL, 0); + if (fcntl(sockfd, F_SETFL, 0) < 0) + clib_unix_warning ("fcntl2"); + vui->sock_errno = 0; template.file_descriptor = sockfd; template.private_data = diff --git a/src/vnet/unix/tapcli.c b/src/vnet/unix/tapcli.c index 2d3082cb..e9dbf729 100644 --- a/src/vnet/unix/tapcli.c +++ b/src/vnet/unix/tapcli.c @@ -899,8 +899,9 @@ int vnet_tap_connect (vlib_main_t * vm, vnet_tap_connect_args_t *ap) /* ip4: mask defaults to /24 */ u32 mask = clib_host_to_net_u32 (0xFFFFFF00); + memset(&sin, 0, sizeof(sin)); sin.sin_family = AF_INET; - sin.sin_port = 0; + /* sin.sin_port = 0; */ sin.sin_addr.s_addr = ap->ip4_address->as_u32; memcpy (&ifr.ifr_ifru.ifru_addr, &sin, sizeof (sin)); @@ -1294,7 +1295,7 @@ tap_connect_command_fn (vlib_main_t * vm, unformat_input_t * input, vlib_cli_command_t * cmd) { - u8 * intfc_name; + u8 * intfc_name = 0; unformat_input_t _line_input, *line_input = &_line_input; vnet_tap_connect_args_t _a, *ap= &_a; tapcli_main_t * tm = &tapcli_main; diff --git a/src/vpp/api/api_main.c b/src/vpp/api/api_main.c index db532061..fd6998f4 100644 --- a/src/vpp/api/api_main.c +++ b/src/vpp/api/api_main.c @@ -139,11 +139,11 @@ api_command_fn (vlib_main_t * vm, "%s error: %U\n", cmdp, format_api_error, vam, rv); - if (vam->regenerate_interface_table) - { - vam->regenerate_interface_table = 0; - api_sw_interface_dump (vam); - } + } + if (vam->regenerate_interface_table) + { + vam->regenerate_interface_table = 0; + api_sw_interface_dump (vam); } unformat_free (vam->input); return 0; diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 7c817a20..d8b97b5f 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -199,7 +199,7 @@ BV (split_and_rehash_linear) /* Find a free slot in the new linear scan bucket */ for (; j < new_length; j++) { - /* Old value in use? Forget it. */ + /* Old value not in use? Forget it. */ if (BV (clib_bihash_is_free) (&(old_values->kvp[i]))) goto doublebreak; @@ -212,11 +212,12 @@ BV (split_and_rehash_linear) j++; goto doublebreak; } - /* This should never happen... */ - clib_warning ("BUG: linear rehash failed!"); - BV (value_free) (h, new_values); - return 0; } + /* This should never happen... */ + clib_warning ("BUG: linear rehash failed!"); + BV (value_free) (h, new_values); + return 0; + doublebreak:; } return new_values; -- cgit 1.2.3-korg From f55f9b851f59264d737d92c6277a87588c565d24 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Wed, 10 May 2017 21:06:28 +0200 Subject: completelly deprecate os_get_cpu_number, replace new occurences Change-Id: I82c663bc0866c6c68ba354104b0bb059387f4b9d Signed-off-by: Damjan Marion --- src/plugins/flowperpkt/l2_node.c | 20 ++++++++++---------- src/plugins/flowperpkt/node.c | 20 ++++++++++---------- src/plugins/snat/in2out.c | 2 +- src/plugins/snat/out2in.c | 2 +- src/vlib/main.h | 2 +- src/vlib/threads.c | 12 ++---------- src/vlib/threads.h | 3 +-- src/vlib/unix/main.c | 2 +- src/vlibmemory/memory_vlib.c | 2 +- src/vnet/dpo/interface_dpo.c | 8 ++++---- src/vnet/lisp-gpe/lisp_gpe_adjacency.c | 2 +- src/vppinfra/bihash_template.c | 16 ++++++++-------- src/vppinfra/lock.h | 6 +++--- src/vppinfra/mem.h | 6 +++--- src/vppinfra/mhash.c | 2 +- src/vppinfra/mhash.h | 2 +- src/vppinfra/mheap.c | 4 ++-- src/vppinfra/os.h | 20 ++++++++++++++++++-- src/vppinfra/smp.c | 2 +- src/vppinfra/unix-misc.c | 19 +++++++------------ 20 files changed, 77 insertions(+), 75 deletions(-) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/plugins/flowperpkt/l2_node.c b/src/plugins/flowperpkt/l2_node.c index fdaf81d1..db80e990 100644 --- a/src/plugins/flowperpkt/l2_node.c +++ b/src/plugins/flowperpkt/l2_node.c @@ -102,7 +102,7 @@ add_to_flow_record_l2 (vlib_main_t * vm, u8 * src_mac, u8 * dst_mac, u16 ethertype, u64 timestamp, u16 length, int do_flush) { - u32 my_cpu_number = vm->thread_index; + u32 my_thread_index = vm->thread_index; flow_report_main_t *frm = &flow_report_main; ip4_header_t *ip; udp_header_t *udp; @@ -116,7 +116,7 @@ add_to_flow_record_l2 (vlib_main_t * vm, vlib_buffer_free_list_t *fl; /* Find or allocate a buffer */ - b0 = fm->l2_buffers_per_worker[my_cpu_number]; + b0 = fm->l2_buffers_per_worker[my_thread_index]; /* Need to allocate a buffer? */ if (PREDICT_FALSE (b0 == 0)) @@ -130,7 +130,7 @@ add_to_flow_record_l2 (vlib_main_t * vm, return; /* Initialize the buffer */ - b0 = fm->l2_buffers_per_worker[my_cpu_number] = + b0 = fm->l2_buffers_per_worker[my_thread_index] = vlib_get_buffer (vm, bi0); fl = vlib_buffer_get_free_list (vm, VLIB_BUFFER_DEFAULT_FREE_LIST_INDEX); @@ -142,16 +142,16 @@ add_to_flow_record_l2 (vlib_main_t * vm, { /* use the current buffer */ bi0 = vlib_get_buffer_index (vm, b0); - offset = fm->l2_next_record_offset_per_worker[my_cpu_number]; + offset = fm->l2_next_record_offset_per_worker[my_thread_index]; } /* Find or allocate a frame */ - f = fm->l2_frames_per_worker[my_cpu_number]; + f = fm->l2_frames_per_worker[my_thread_index]; if (PREDICT_FALSE (f == 0)) { u32 *to_next; f = vlib_get_frame_to_node (vm, ip4_lookup_node.index); - fm->l2_frames_per_worker[my_cpu_number] = f; + fm->l2_frames_per_worker[my_thread_index] = f; /* Enqueue the buffer */ to_next = vlib_frame_vector_args (f); @@ -299,13 +299,13 @@ add_to_flow_record_l2 (vlib_main_t * vm, } vlib_put_frame_to_node (vm, ip4_lookup_node.index, - fm->l2_frames_per_worker[my_cpu_number]); - fm->l2_frames_per_worker[my_cpu_number] = 0; - fm->l2_buffers_per_worker[my_cpu_number] = 0; + fm->l2_frames_per_worker[my_thread_index]); + fm->l2_frames_per_worker[my_thread_index] = 0; + fm->l2_buffers_per_worker[my_thread_index] = 0; offset = 0; } - fm->l2_next_record_offset_per_worker[my_cpu_number] = offset; + fm->l2_next_record_offset_per_worker[my_thread_index] = offset; } void diff --git a/src/plugins/flowperpkt/node.c b/src/plugins/flowperpkt/node.c index 0277682d..9bac4166 100644 --- a/src/plugins/flowperpkt/node.c +++ b/src/plugins/flowperpkt/node.c @@ -101,7 +101,7 @@ add_to_flow_record_ipv4 (vlib_main_t * vm, u32 src_address, u32 dst_address, u8 tos, u64 timestamp, u16 length, int do_flush) { - u32 my_cpu_number = vm->thread_index; + u32 my_thread_index = vm->thread_index; flow_report_main_t *frm = &flow_report_main; ip4_header_t *ip; udp_header_t *udp; @@ -115,7 +115,7 @@ add_to_flow_record_ipv4 (vlib_main_t * vm, vlib_buffer_free_list_t *fl; /* Find or allocate a buffer */ - b0 = fm->ipv4_buffers_per_worker[my_cpu_number]; + b0 = fm->ipv4_buffers_per_worker[my_thread_index]; /* Need to allocate a buffer? */ if (PREDICT_FALSE (b0 == 0)) @@ -129,7 +129,7 @@ add_to_flow_record_ipv4 (vlib_main_t * vm, return; /* Initialize the buffer */ - b0 = fm->ipv4_buffers_per_worker[my_cpu_number] = + b0 = fm->ipv4_buffers_per_worker[my_thread_index] = vlib_get_buffer (vm, bi0); fl = vlib_buffer_get_free_list (vm, VLIB_BUFFER_DEFAULT_FREE_LIST_INDEX); @@ -141,16 +141,16 @@ add_to_flow_record_ipv4 (vlib_main_t * vm, { /* use the current buffer */ bi0 = vlib_get_buffer_index (vm, b0); - offset = fm->ipv4_next_record_offset_per_worker[my_cpu_number]; + offset = fm->ipv4_next_record_offset_per_worker[my_thread_index]; } /* Find or allocate a frame */ - f = fm->ipv4_frames_per_worker[my_cpu_number]; + f = fm->ipv4_frames_per_worker[my_thread_index]; if (PREDICT_FALSE (f == 0)) { u32 *to_next; f = vlib_get_frame_to_node (vm, ip4_lookup_node.index); - fm->ipv4_frames_per_worker[my_cpu_number] = f; + fm->ipv4_frames_per_worker[my_thread_index] = f; /* Enqueue the buffer */ to_next = vlib_frame_vector_args (f); @@ -300,13 +300,13 @@ add_to_flow_record_ipv4 (vlib_main_t * vm, } vlib_put_frame_to_node (vm, ip4_lookup_node.index, - fm->ipv4_frames_per_worker[my_cpu_number]); - fm->ipv4_frames_per_worker[my_cpu_number] = 0; - fm->ipv4_buffers_per_worker[my_cpu_number] = 0; + fm->ipv4_frames_per_worker[my_thread_index]); + fm->ipv4_frames_per_worker[my_thread_index] = 0; + fm->ipv4_buffers_per_worker[my_thread_index] = 0; offset = 0; } - fm->ipv4_next_record_offset_per_worker[my_cpu_number] = offset; + fm->ipv4_next_record_offset_per_worker[my_thread_index] = offset; } void diff --git a/src/plugins/snat/in2out.c b/src/plugins/snat/in2out.c index f7d29c69..bc86a7a4 100644 --- a/src/plugins/snat/in2out.c +++ b/src/plugins/snat/in2out.c @@ -1514,7 +1514,7 @@ snat_det_in2out_node_fn (vlib_main_t * vm, u32 pkts_processed = 0; snat_main_t * sm = &snat_main; u32 now = (u32) vlib_time_now (vm); - u32 thread_index = os_get_cpu_number (); + u32 thread_index = vlib_get_thread_index (); from = vlib_frame_vector_args (frame); n_left_from = frame->n_vectors; diff --git a/src/plugins/snat/out2in.c b/src/plugins/snat/out2in.c index 3d7b106a..824406ab 100644 --- a/src/plugins/snat/out2in.c +++ b/src/plugins/snat/out2in.c @@ -1168,7 +1168,7 @@ snat_det_out2in_node_fn (vlib_main_t * vm, snat_out2in_next_t next_index; u32 pkts_processed = 0; snat_main_t * sm = &snat_main; - u32 thread_index = os_get_cpu_number (); + u32 thread_index = vlib_get_thread_index (); from = vlib_frame_vector_args (frame); n_left_from = frame->n_vectors; diff --git a/src/vlib/main.h b/src/vlib/main.h index 329bf073..0e8026d1 100644 --- a/src/vlib/main.h +++ b/src/vlib/main.h @@ -320,7 +320,7 @@ always_inline void vlib_set_queue_signal_callback /* Main routine. */ int vlib_main (vlib_main_t * vm, unformat_input_t * input); -/* Thread stacks, for os_get_cpu_number */ +/* Thread stacks, for os_get_thread_index */ extern u8 **vlib_thread_stacks; /* Number of thread stacks that the application needs */ diff --git a/src/vlib/threads.c b/src/vlib/threads.c index 9ccfd3a2..b7bc9e26 100644 --- a/src/vlib/threads.c +++ b/src/vlib/threads.c @@ -35,16 +35,8 @@ vl (void *p) vlib_worker_thread_t *vlib_worker_threads; vlib_thread_main_t vlib_thread_main; -__thread uword vlib_thread_index = 0; - -uword -os_get_cpu_number (void) -{ - return vlib_thread_index; -} - uword -os_get_ncpus (void) +os_get_nthreads (void) { u32 len; @@ -467,7 +459,7 @@ vlib_worker_thread_bootstrap_fn (void *arg) w->lwp = syscall (SYS_gettid); w->thread_id = pthread_self (); - vlib_thread_index = w - vlib_worker_threads; + __os_thread_index = w - vlib_worker_threads; rv = (void *) clib_calljmp ((uword (*)(uword)) w->thread_function, diff --git a/src/vlib/threads.h b/src/vlib/threads.h index 101d3d4a..17d35a24 100644 --- a/src/vlib/threads.h +++ b/src/vlib/threads.h @@ -181,11 +181,10 @@ u32 vlib_frame_queue_main_init (u32 node_index, u32 frame_queue_nelts); void vlib_worker_thread_barrier_sync (vlib_main_t * vm); void vlib_worker_thread_barrier_release (vlib_main_t * vm); -extern __thread uword vlib_thread_index; static_always_inline uword vlib_get_thread_index (void) { - return vlib_thread_index; + return __os_thread_index; } always_inline void diff --git a/src/vlib/unix/main.c b/src/vlib/unix/main.c index db5ddd64..103576db 100644 --- a/src/vlib/unix/main.c +++ b/src/vlib/unix/main.c @@ -565,7 +565,7 @@ vlib_unix_main (int argc, char *argv[]) vlib_thread_stack_init (0); - vlib_thread_index = 0; + __os_thread_index = 0; i = clib_calljmp (thread0, (uword) vm, (void *) (vlib_thread_stacks[0] + diff --git a/src/vlibmemory/memory_vlib.c b/src/vlibmemory/memory_vlib.c index acba8b3f..e5d88732 100644 --- a/src/vlibmemory/memory_vlib.c +++ b/src/vlibmemory/memory_vlib.c @@ -1333,7 +1333,7 @@ vl_api_rpc_call_main_thread (void *fp, u8 * data, u32 data_length) unix_shared_memory_queue_t *q; /* Main thread: call the function directly */ - if (os_get_cpu_number () == 0) + if (vlib_get_thread_index () == 0) { vlib_main_t *vm = vlib_get_main (); void (*call_fp) (void *); diff --git a/src/vnet/dpo/interface_dpo.c b/src/vnet/dpo/interface_dpo.c index 50ca756f..8d700c23 100644 --- a/src/vnet/dpo/interface_dpo.c +++ b/src/vnet/dpo/interface_dpo.c @@ -231,7 +231,7 @@ interface_dpo_inline (vlib_main_t * vm, vlib_frame_t * from_frame) { u32 n_left_from, next_index, * from, * to_next; - u32 cpu_index = os_get_cpu_number(); + u32 thread_index = vlib_get_thread_index (); vnet_interface_main_t *im; im = &vnet_get_main ()->interface_main; @@ -274,13 +274,13 @@ interface_dpo_inline (vlib_main_t * vm, vlib_increment_combined_counter (im->combined_sw_if_counters + VNET_INTERFACE_COUNTER_RX, - cpu_index, + thread_index, ido0->ido_sw_if_index, 1, vlib_buffer_length_in_chain (vm, b0)); vlib_increment_combined_counter (im->combined_sw_if_counters + VNET_INTERFACE_COUNTER_RX, - cpu_index, + thread_index, ido1->ido_sw_if_index, 1, vlib_buffer_length_in_chain (vm, b1)); @@ -331,7 +331,7 @@ interface_dpo_inline (vlib_main_t * vm, /* Bump the interface's RX coutners */ vlib_increment_combined_counter (im->combined_sw_if_counters + VNET_INTERFACE_COUNTER_RX, - cpu_index, + thread_index, ido0->ido_sw_if_index, 1, vlib_buffer_length_in_chain (vm, b0)); diff --git a/src/vnet/lisp-gpe/lisp_gpe_adjacency.c b/src/vnet/lisp-gpe/lisp_gpe_adjacency.c index d5f3a28a..7db1c9bb 100644 --- a/src/vnet/lisp-gpe/lisp_gpe_adjacency.c +++ b/src/vnet/lisp-gpe/lisp_gpe_adjacency.c @@ -302,7 +302,7 @@ lisp_gpe_increment_stats_counters (lisp_cp_main_t * lcm, ip_adjacency_t * adj, /* compute payload length starting after GPE */ u32 bytes = b->current_length - (lisp_data - b->data - b->current_data); - vlib_increment_combined_counter (&lgm->counters, os_get_cpu_number (), + vlib_increment_combined_counter (&lgm->counters, vlib_get_thread_index (), p[0], 1, bytes); } diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index d8b97b5f..51fadeb8 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -96,12 +96,12 @@ 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 (); - 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); clib_mem_set_heap (oldheap); } @@ -110,7 +110,7 @@ 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]; h->saved_bucket.as_u64 = b->as_u64; oldheap = clib_mem_set_heap (h->mheap); @@ -119,7 +119,7 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b) { vec_validate_aligned (working_copy, (1 << b->log2_pages) - 1, sizeof (u64)); - h->working_copies[cpu_number] = working_copy; + h->working_copies[thread_index] = working_copy; } _vec_len (working_copy) = 1 << b->log2_pages; @@ -132,7 +132,7 @@ 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 @@ -233,7 +233,7 @@ int BV (clib_bihash_add_del) int i, limit; u64 hash, new_hash; u32 new_log2_pages; - u32 cpu_number = os_get_cpu_number (); + u32 thread_index = os_get_thread_index (); int mark_bucket_linear; int resplit_once; @@ -323,7 +323,7 @@ int BV (clib_bihash_add_del) new_log2_pages = h->saved_bucket.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); diff --git a/src/vppinfra/lock.h b/src/vppinfra/lock.h index c60ff414..0cd2b4fe 100644 --- a/src/vppinfra/lock.h +++ b/src/vppinfra/lock.h @@ -24,7 +24,7 @@ typedef struct u32 lock; #if CLIB_DEBUG > 0 pid_t pid; - uword cpu_index; + uword thread_index; void *frame_address; #endif } *clib_spinlock_t; @@ -57,7 +57,7 @@ clib_spinlock_lock (clib_spinlock_t * p) #if CLIB_DEBUG > 0 (*p)->frame_address = __builtin_frame_address (0); (*p)->pid = getpid (); - (*p)->cpu_index = os_get_cpu_number (); + (*p)->thread_index = os_get_thread_index (); #endif } @@ -75,7 +75,7 @@ clib_spinlock_unlock (clib_spinlock_t * p) #if CLIB_DEBUG > 0 (*p)->frame_address = 0; (*p)->pid = 0; - (*p)->cpu_index = 0; + (*p)->thread_index = 0; #endif } diff --git a/src/vppinfra/mem.h b/src/vppinfra/mem.h index 1260eab2..63c5ac16 100644 --- a/src/vppinfra/mem.h +++ b/src/vppinfra/mem.h @@ -54,14 +54,14 @@ extern void *clib_per_cpu_mheaps[CLIB_MAX_MHEAPS]; always_inline void * clib_mem_get_per_cpu_heap (void) { - int cpu = os_get_cpu_number (); + int cpu = os_get_thread_index (); return clib_per_cpu_mheaps[cpu]; } always_inline void * clib_mem_set_per_cpu_heap (u8 * new_heap) { - int cpu = os_get_cpu_number (); + int cpu = os_get_thread_index (); void *old = clib_per_cpu_mheaps[cpu]; clib_per_cpu_mheaps[cpu] = new_heap; return old; @@ -83,7 +83,7 @@ clib_mem_alloc_aligned_at_offset (uword size, uword align, uword align_offset, align_offset = align; } - cpu = os_get_cpu_number (); + cpu = os_get_thread_index (); heap = clib_per_cpu_mheaps[cpu]; heap = mheap_get_aligned (heap, size, align, align_offset, &offset); clib_per_cpu_mheaps[cpu] = heap; diff --git a/src/vppinfra/mhash.c b/src/vppinfra/mhash.c index c917e164..00b67c49 100644 --- a/src/vppinfra/mhash.c +++ b/src/vppinfra/mhash.c @@ -226,7 +226,7 @@ static uword mhash_set_tmp_key (mhash_t * h, const void *key) { u8 *key_tmp; - int my_cpu = os_get_cpu_number (); + int my_cpu = os_get_thread_index (); vec_validate (h->key_tmps, my_cpu); key_tmp = h->key_tmps[my_cpu]; diff --git a/src/vppinfra/mhash.h b/src/vppinfra/mhash.h index 102adf4e..7eb19183 100644 --- a/src/vppinfra/mhash.h +++ b/src/vppinfra/mhash.h @@ -93,7 +93,7 @@ mhash_key_to_mem (mhash_t * h, uword key) { u8 *key_tmp; - int my_cpu = os_get_cpu_number (); + int my_cpu = os_get_thread_index (); vec_validate (h->key_tmps, my_cpu); key_tmp = h->key_tmps[my_cpu]; return key_tmp; diff --git a/src/vppinfra/mheap.c b/src/vppinfra/mheap.c index 192732db..d4010ceb 100644 --- a/src/vppinfra/mheap.c +++ b/src/vppinfra/mheap.c @@ -56,7 +56,7 @@ mheap_maybe_lock (void *v) mheap_t *h = mheap_header (v); if (v && (h->flags & MHEAP_FLAG_THREAD_SAFE)) { - u32 my_cpu = os_get_cpu_number (); + u32 my_cpu = os_get_thread_index (); if (h->owner_cpu == my_cpu) { h->recursion_count++; @@ -77,7 +77,7 @@ mheap_maybe_unlock (void *v) mheap_t *h = mheap_header (v); if (v && h->flags & MHEAP_FLAG_THREAD_SAFE) { - ASSERT (os_get_cpu_number () == h->owner_cpu); + ASSERT (os_get_thread_index () == h->owner_cpu); if (--h->recursion_count == 0) { h->owner_cpu = ~0; diff --git a/src/vppinfra/os.h b/src/vppinfra/os.h index a5c74f8c..33300716 100644 --- a/src/vppinfra/os.h +++ b/src/vppinfra/os.h @@ -56,8 +56,24 @@ void os_out_of_memory (void); /* Estimate, measure or divine CPU timestamp clock frequency. */ f64 os_cpu_clock_frequency (void); -uword os_get_cpu_number (void); -uword os_get_ncpus (void); +extern __thread uword __os_thread_index; + +static_always_inline uword +os_get_thread_index (void) +{ + return __os_thread_index; +} + +static_always_inline uword +os_get_cpu_number (void) __attribute__ ((deprecated)); + +static_always_inline uword +os_get_cpu_number (void) +{ + return __os_thread_index; +} + +uword os_get_nthreads (void); #include diff --git a/src/vppinfra/smp.c b/src/vppinfra/smp.c index 8ac19960..f603283e 100644 --- a/src/vppinfra/smp.c +++ b/src/vppinfra/smp.c @@ -53,7 +53,7 @@ allocate_per_cpu_mheap (uword cpu) void *heap; uword vm_size, stack_size, mheap_flags; - ASSERT (os_get_cpu_number () == cpu); + ASSERT (os_get_thread_index () == cpu); vm_size = (uword) 1 << m->log2_n_per_cpu_vm_bytes; stack_size = (uword) 1 << m->log2_n_per_cpu_stack_bytes; diff --git a/src/vppinfra/unix-misc.c b/src/vppinfra/unix-misc.c index 2928369d..361015b4 100644 --- a/src/vppinfra/unix-misc.c +++ b/src/vppinfra/unix-misc.c @@ -45,6 +45,8 @@ #include #include /* for sprintf */ +__thread uword __os_thread_index = 0; + clib_error_t * unix_file_n_bytes (char *file, uword * result) { @@ -188,14 +190,14 @@ void os_puts (u8 * string, uword string_length, uword is_error) void os_puts (u8 * string, uword string_length, uword is_error) { - int cpu = os_get_cpu_number (); - int ncpus = os_get_ncpus (); + int cpu = os_get_thread_index (); + int nthreads = os_get_nthreads (); char buf[64]; int fd = is_error ? 2 : 1; struct iovec iovs[2]; int n_iovs = 0; - if (ncpus > 1) + if (nthreads > 1) { snprintf (buf, sizeof (buf), "%d: ", cpu); @@ -219,16 +221,9 @@ os_out_of_memory (void) os_panic (); } -uword os_get_cpu_number (void) __attribute__ ((weak)); -uword -os_get_cpu_number (void) -{ - return 0; -} - -uword os_get_ncpus (void) __attribute__ ((weak)); +uword os_get_nthreads (void) __attribute__ ((weak)); uword -os_get_ncpus (void) +os_get_nthreads (void) { return 1; } -- cgit 1.2.3-korg From ba7ddfe9b77771c47f99df5475e6e92b8d80816e Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Wed, 17 May 2017 20:20:50 -0400 Subject: VPP-847: improve bihash template memory allocator performance Particularly in the DCLIB_VEC64=1 case, using vectors vs. raw clib_mem_alloc'ed memory causes abysmal memory allocator performance. Change-Id: I07a4dec0cd69ca357445385e2671cdf23c59b95d Signed-off-by: Dave Barach --- src/vppinfra/bihash_template.c | 70 +++++++++++++++++++++++-------------- src/vppinfra/bihash_template.h | 1 + src/vppinfra/mheap.c | 28 ++++++--------- src/vppinfra/mheap_bootstrap.h | 24 ++++++------- src/vppinfra/test_bihash_template.c | 45 +++++++++++++++++++++++- 5 files changed, 111 insertions(+), 57 deletions(-) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 51fadeb8..7e4216bd 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]; @@ -97,11 +94,14 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b) void *oldheap; BVT (clib_bihash_value) * working_copy; u32 thread_index = os_get_thread_index (); + int log2_working_copy_length; if (thread_index >= vec_len (h->working_copies)) { oldheap = clib_mem_set_heap (h->mheap); vec_validate (h->working_copies, thread_index); + vec_validate (h->working_copy_lengths, thread_index); + h->working_copy_lengths[thread_index] = -1; clib_mem_set_heap (oldheap); } @@ -111,18 +111,23 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b) * lookup failures. */ 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)); + 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); @@ -139,15 +144,16 @@ 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 +179,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 +191,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 +224,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,7 +241,7 @@ int BV (clib_bihash_add_del) int rv = 0; int i, limit; u64 hash, new_hash; - u32 new_log2_pages; + u32 new_log2_pages, old_log2_pages; u32 thread_index = os_get_thread_index (); int mark_bucket_linear; int resplit_once; @@ -257,6 +266,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 +330,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[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 +377,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 +397,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 (); diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index a0a7844c..4ea14ff0 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -77,6 +77,7 @@ typedef struct volatile u32 *writer_lock; BVT (clib_bihash_value) ** working_copies; + int *working_copy_lengths; clib_bihash_bucket_t saved_bucket; u32 nbuckets; diff --git a/src/vppinfra/mheap.c b/src/vppinfra/mheap.c index d4010ceb..5bbbc65f 100644 --- a/src/vppinfra/mheap.c +++ b/src/vppinfra/mheap.c @@ -549,23 +549,17 @@ mheap_get_search_free_list (void *v, non_empty_bin_mask &= ~pow2_mask (bin % BITS (uword)); /* Search each occupied free bin which is large enough. */ - foreach_set_bit (bi, non_empty_bin_mask, ( - { - uword r = - mheap_get_search_free_bin (v, - bi - + - i - * - BITS - (uword), - n_user_bytes_arg, - align, - align_offset); - if (r != - MHEAP_GROUNDED) return - r;} - )); + /* *INDENT-OFF* */ + foreach_set_bit (bi, non_empty_bin_mask, + ({ + uword r = + mheap_get_search_free_bin (v, bi + i * BITS (uword), + n_user_bytes_arg, + align, + align_offset); + if (r != MHEAP_GROUNDED) return r; + })); + /* *INDENT-ON* */ } return MHEAP_GROUNDED; diff --git a/src/vppinfra/mheap_bootstrap.h b/src/vppinfra/mheap_bootstrap.h index 4b21051b..38f0ac84 100644 --- a/src/vppinfra/mheap_bootstrap.h +++ b/src/vppinfra/mheap_bootstrap.h @@ -160,11 +160,23 @@ typedef struct uword *trace_index_by_offset; } mheap_trace_main_t; +/* Without vector instructions don't bother with small object cache. */ +#ifdef CLIB_HAVE_VEC128 +#define MHEAP_HAVE_SMALL_OBJECT_CACHE 1 +#else +#define MHEAP_HAVE_SMALL_OBJECT_CACHE 0 +#endif + /* Small object bin i is for objects with user_size > sizeof (mheap_elt_t) + sizeof (mheap_elt_t) * (i - 1) user_size <= sizeof (mheap_elt_t) + sizeof (mheap_size_t) * i. */ +#if MHEAP_HAVE_SMALL_OBJECT_CACHE > 0 #define MHEAP_LOG2_N_SMALL_OBJECT_BINS 8 #define MHEAP_N_SMALL_OBJECT_BINS (1 << MHEAP_LOG2_N_SMALL_OBJECT_BINS) +#else +#define MHEAP_LOG2_N_SMALL_OBJECT_BINS 0 +#define MHEAP_N_SMALL_OBJECT_BINS 0 +#endif #define MHEAP_N_BINS \ (MHEAP_N_SMALL_OBJECT_BINS \ @@ -188,18 +200,6 @@ typedef struct u64 n_clocks_get, n_clocks_put; } mheap_stats_t; -/* Without vector instructions don't bother with small object cache. */ -#ifdef CLIB_HAVE_VEC128 -#define MHEAP_HAVE_SMALL_OBJECT_CACHE 1 -#else -#define MHEAP_HAVE_SMALL_OBJECT_CACHE 0 -#endif - -#if CLIB_VEC64 > 0 -#undef MHEAP_HAVE_SMALL_OBJECT_CACHE -#define MHEAP_HAVE_SMALL_OBJECT_CACHE 0 -#endif - /* For objects with align == 4 and align_offset == 0 (e.g. vector strings). */ typedef struct { diff --git a/src/vppinfra/test_bihash_template.c b/src/vppinfra/test_bihash_template.c index ef03f565..1e262430 100644 --- a/src/vppinfra/test_bihash_template.c +++ b/src/vppinfra/test_bihash_template.c @@ -47,6 +47,43 @@ vl (void *v) return vec_len (v); } +static clib_error_t * +test_bihash_vec64 (test_main_t * tm) +{ + u32 user_buckets = 1228800; + u32 user_memory_size = 209715200; + BVT (clib_bihash_kv) kv; + int i, j; + f64 before; + f64 *cum_times = 0; + BVT (clib_bihash) * h; + + h = &tm->hash; + + BV (clib_bihash_init) (h, "test", user_buckets, user_memory_size); + + before = clib_time_now (&tm->clib_time); + + for (j = 0; j < 10; j++) + { + for (i = 1; i <= j * 1000 + 1; i++) + { + kv.key = i; + kv.value = 1; + + BV (clib_bihash_add_del) (h, &kv, 1 /* is_add */ ); + } + + vec_add1 (cum_times, clib_time_now (&tm->clib_time) - before); + } + + for (j = 0; j < vec_len (cum_times); j++) + fformat (stdout, "Cum time for %d: %.4f (us)\n", (j + 1) * 1000, + cum_times[j] * 1e6); + + return 0; +} + static clib_error_t * test_bihash (test_main_t * tm) { @@ -204,6 +241,7 @@ test_bihash_main (test_main_t * tm) { unformat_input_t *i = tm->input; clib_error_t *error; + int test_vec64 = 0; while (unformat_check_input (i) != UNFORMAT_END_OF_INPUT) { @@ -222,6 +260,8 @@ test_bihash_main (test_main_t * tm) ; else if (unformat (i, "search %d", &tm->search_iter)) ; + else if (unformat (i, "vec64")) + test_vec64 = 1; else if (unformat (i, "verbose")) tm->verbose = 1; else @@ -229,7 +269,10 @@ test_bihash_main (test_main_t * tm) format_unformat_error, i); } - error = test_bihash (tm); + if (test_vec64) + error = test_bihash_vec64 (tm); + else + error = test_bihash (tm); return error; } -- cgit 1.2.3-korg From 871cdec1b5fe5e0b0ccd70cf2e6fbedad0902c9f Mon Sep 17 00:00:00 2001 From: Steve Shin Date: Fri, 2 Jun 2017 10:09:02 -0700 Subject: Fix mac_age process crash in multi-threaded environment VPP crash is observed when MAC aging is enabled with multi-threaded mode. If a thread other-than-zero expands the working_copies vector, working_copy_lengths should be initialized with vec_validate_init_empty(..., -1) to fill -1 across lower-numbered working_copy_lengths vector element. Change-Id: I60959fc6511306b33acae323df9c6898fc6c50ce Signed-off-by: Steve Shin --- src/vppinfra/bihash_template.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 7e4216bd..7117f994 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -100,8 +100,7 @@ BV (make_working_copy) (BVT (clib_bihash) * h, clib_bihash_bucket_t * b) { oldheap = clib_mem_set_heap (h->mheap); vec_validate (h->working_copies, thread_index); - vec_validate (h->working_copy_lengths, thread_index); - h->working_copy_lengths[thread_index] = -1; + vec_validate_init_empty (h->working_copy_lengths, thread_index, ~0); clib_mem_set_heap (oldheap); } -- cgit 1.2.3-korg From 47366b19fb7f65dba1a7c731ee765b1216f47e33 Mon Sep 17 00:00:00 2001 From: Marco Varlese Date: Mon, 5 Jun 2017 17:59:24 +0200 Subject: More GCC-7 errors The Wmaybe-uninitialized is the new error included with Wall. This patch addresses the warning and fixes it. Change-Id: I8fdf9ff2d236c46b717024a14874fbbbad8af303 Signed-off-by: Marco Varlese --- src/plugins/snat/out2in.c | 2 ++ src/vppinfra/bihash_template.c | 2 ++ 2 files changed, 4 insertions(+) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/plugins/snat/out2in.c b/src/plugins/snat/out2in.c index 824406ab..e8ddcf1c 100644 --- a/src/plugins/snat/out2in.c +++ b/src/plugins/snat/out2in.c @@ -308,6 +308,8 @@ u32 icmp_match_out2in_slow(snat_main_t *sm, vlib_node_runtime_t *node, sw_if_index0 = vnet_buffer(b0)->sw_if_index[VLIB_RX]; rx_fib_index0 = ip4_fib_table_get_index_for_sw_if_index (sw_if_index0); + key0.protocol = 0; + err = icmp_get_key (ip0, &key0); if (err != -1) { diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 7117f994..004e8a9a 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -252,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)) ; -- cgit 1.2.3-korg From 908a5ea6e247b4a15f0ec7e8ee8ebff799abdc4f Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Fri, 14 Jul 2017 12:42:21 -0400 Subject: 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 --- src/vnet/fib/ip6_fib.c | 4 +- src/vnet/fib/ip6_fib.h | 2 +- src/vnet/l2/l2_fib.c | 8 +- src/vppinfra.am | 2 + src/vppinfra/bihash_16_8.h | 3 + src/vppinfra/bihash_24_8.h | 3 + src/vppinfra/bihash_48_8.h | 3 + src/vppinfra/bihash_8_8.h | 3 + src/vppinfra/bihash_template.c | 78 ++++++++++++-- src/vppinfra/bihash_template.h | 206 ++++++++++++++++++++++++++++++++---- src/vppinfra/test_bihash_template.c | 61 +++++++++-- 11 files changed, 329 insertions(+), 44 deletions(-) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/vnet/fib/ip6_fib.c b/src/vnet/fib/ip6_fib.c index 527f9114..8fde6f9f 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 9789da4f..aad8305c 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 4ed16987..7e59b098 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 785445a6..533bacd6 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 6b1b563e..361665be 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 db77daa4..d0be028c 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 48079e0a..107bcace 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 68049351..f81002d6 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 004e8a9a..e3a5759d 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 4ea14ff0..feb6fb68 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 1e262430..589c815d 100644 --- a/src/vppinfra/test_bihash_template.c +++ b/src/vppinfra/test_bihash_template.c @@ -236,12 +236,45 @@ test_bihash (test_main_t * tm) return 0; } +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; } -- cgit 1.2.3-korg From 858c06fac65e7ad05dc6e739a51e8d87a544e0fe Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Fri, 21 Jul 2017 10:44:27 -0400 Subject: Atomic bucket lock Change-Id: I84908b9ad30d7555024e98b69ed37b111f31c27a Signed-off-by: Dave Barach --- src/vppinfra/bihash_template.c | 27 ++++++++-------- src/vppinfra/bihash_template.h | 72 ++++++++++++++++++++++++++---------------- 2 files changed, 58 insertions(+), 41 deletions(-) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index e3a5759d..b5eb379a 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -135,8 +135,9 @@ BV (make_working_copy) (BVT (clib_bihash) * h, BVT (clib_bihash_bucket) * b) clib_mem_set_heap (oldheap); - /* Turn off the cache */ - BV (clib_bihash_cache_enable_disable) (b, 0); + /* Lock the bucket... */ + while (BV (clib_bihash_lock_bucket) (b) == 0) + ; v = BV (clib_bihash_get_value) (h, b->offset); @@ -416,7 +417,7 @@ expand_ok: unlock: BV (clib_bihash_reset_cache) (b); - BV (clib_bihash_cache_enable_disable) (b, 1 /* enable */ ); + BV (clib_bihash_unlock_bucket) (b); CLIB_MEMORY_BARRIER (); h->writer_lock[0] = 0; return rv; @@ -444,7 +445,7 @@ int BV (clib_bihash_search) return -1; /* Check the cache, if currently enabled */ - if (PREDICT_TRUE (b->cache_lru & (1 << 15))) + if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0)) { limit = BIHASH_KVP_CACHE_SIZE; kvp = b->cache; @@ -475,16 +476,16 @@ int BV (clib_bihash_search) *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); + if (BV (clib_bihash_lock_bucket) (b)) + { + 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++; + /* Reenable the cache */ + BV (clib_bihash_unlock_bucket) (b); + h->cache_misses++; + } return 0; } } diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index feb6fb68..3d9c59cb 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -182,13 +182,29 @@ static inline void BV (clib_bihash_reset_cache) (BVT (clib_bihash_bucket) * b) b->cache_lru = initial_lru_value; } -static inline void BV (clib_bihash_cache_enable_disable) - (BVT (clib_bihash_bucket) * b, u8 enable) +static inline int BV (clib_bihash_lock_bucket) (BVT (clib_bihash_bucket) * b) { BVT (clib_bihash_bucket) tmp_b; + u64 rv; + + tmp_b.as_u64 = 0; + tmp_b.cache_lru = 1 << 15; + + rv = __sync_fetch_and_or (&b->as_u64, tmp_b.as_u64); + tmp_b.as_u64 = rv; + /* Was already locked? */ + if (tmp_b.cache_lru & (1 << 15)) + return 0; + return 1; +} + +static inline void BV (clib_bihash_unlock_bucket) + (BVT (clib_bihash_bucket) * b) +{ + BVT (clib_bihash_bucket) tmp_b; + tmp_b.as_u64 = b->as_u64; - tmp_b.cache_lru &= 0x7FFF; - tmp_b.cache_lru |= enable << 15; + tmp_b.cache_lru &= ~(1 << 15); b->as_u64 = tmp_b.as_u64; } @@ -249,8 +265,8 @@ 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))) + /* Check the cache, if not currently locked */ + if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0)) { limit = BIHASH_KVP_CACHE_SIZE; kvp = b->cache; @@ -282,17 +298,17 @@ static inline int BV (clib_bihash_search_inline) 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); + /* Try to lock the bucket */ + if (BV (clib_bihash_lock_bucket) (b)) + { + 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++; + /* Unlock the bucket */ + BV (clib_bihash_unlock_bucket) (b); + h->cache_misses++; + } return 0; } } @@ -320,8 +336,8 @@ 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))) + /* Check the cache, if currently unlocked */ + if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0)) { limit = BIHASH_KVP_CACHE_SIZE; kvp = b->cache; @@ -352,17 +368,17 @@ static inline int BV (clib_bihash_search_inline_2) 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); + /* Try to lock the bucket */ + if (BV (clib_bihash_lock_bucket) (b)) + { + 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++; + /* Reenable the cache */ + BV (clib_bihash_unlock_bucket) (b); + h->cache_misses++; + } return 0; } } -- cgit 1.2.3-korg From c8ef08ac63231120900ca08608a61625db28f096 Mon Sep 17 00:00:00 2001 From: Dave Barach Date: Thu, 31 Aug 2017 05:58:22 -0400 Subject: Fix BIHASH_KVP_CACHE_SIZE == 0 case Setting the bucket-level LRU cache size to zero removes the bucket-level LRU cache code. Change-Id: Idf2e63d0d508675e957366515863766f79a3479c Signed-off-by: Dave Barach --- src/vppinfra/bihash_8_8.h | 2 +- src/vppinfra/bihash_template.c | 14 +++++++++++++- src/vppinfra/bihash_template.h | 25 +++++++++++++++++++++++-- 3 files changed, 37 insertions(+), 4 deletions(-) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/vppinfra/bihash_8_8.h b/src/vppinfra/bihash_8_8.h index f81002d6..2deb64ef 100644 --- a/src/vppinfra/bihash_8_8.h +++ b/src/vppinfra/bihash_8_8.h @@ -18,7 +18,7 @@ #define BIHASH_TYPE _8_8 #define BIHASH_KVP_PER_PAGE 4 -#define BIHASH_KVP_CACHE_SIZE 5 +#define BIHASH_KVP_CACHE_SIZE 0 #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 b5eb379a..704d1659 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -430,7 +430,9 @@ int BV (clib_bihash_search) u64 hash; u32 bucket_index; BVT (clib_bihash_value) * v; +#if BIHASH_KVP_CACHE_SIZE > 0 BVT (clib_bihash_kv) * kvp; +#endif BVT (clib_bihash_bucket) * b; int i, limit; @@ -444,6 +446,7 @@ int BV (clib_bihash_search) if (b->offset == 0) return -1; +#if BIHASH_KVP_CACHE_SIZE > 0 /* Check the cache, if currently enabled */ if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0)) { @@ -459,6 +462,7 @@ int BV (clib_bihash_search) } } } +#endif hash >>= h->log2_nbuckets; @@ -472,9 +476,10 @@ 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]; +#if BIHASH_KVP_CACHE_SIZE > 0 + u8 cache_slot; /* Shut off the cache */ if (BV (clib_bihash_lock_bucket) (b)) { @@ -486,6 +491,7 @@ int BV (clib_bihash_search) BV (clib_bihash_unlock_bucket) (b); h->cache_misses++; } +#endif return 0; } } @@ -494,6 +500,7 @@ int BV (clib_bihash_search) u8 *BV (format_bihash_lru) (u8 * s, va_list * args) { +#if BIHASH_KVP_SIZE > 0 int i; BVT (clib_bihash_bucket) * b = va_arg (*args, BVT (clib_bihash_bucket) *); u16 cache_lru = b->cache_lru; @@ -502,13 +509,18 @@ u8 *BV (format_bihash_lru) (u8 * s, va_list * args) for (i = 0; i < BIHASH_KVP_CACHE_SIZE; i++) s = format (s, "[%d] ", ((cache_lru >> (3 * i)) & 7)); +#else + return format (s, "cache not configured"); +#endif return (s); } void BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b, u8 slot) { +#if BIHASH_KVP_SIZE > 0 BV (clib_bihash_update_lru) (b, slot); +#endif } u8 *BV (format_bihash) (u8 * s, va_list * args) diff --git a/src/vppinfra/bihash_template.h b/src/vppinfra/bihash_template.h index 3d9c59cb..ea1b6f7b 100644 --- a/src/vppinfra/bihash_template.h +++ b/src/vppinfra/bihash_template.h @@ -65,7 +65,9 @@ typedef struct }; u64 as_u64; }; +#if BIHASH_KVP_CACHE_SIZE > 0 BVT (clib_bihash_kv) cache[BIHASH_KVP_CACHE_SIZE]; +#endif } BVT (clib_bihash_bucket); typedef struct @@ -155,11 +157,16 @@ BV (clib_bihash_update_lru_not_inline) (BVT (clib_bihash_bucket) * b, static inline u8 BV (clib_bihash_get_lru) (BVT (clib_bihash_bucket) * b) { +#if BIHASH_KVP_CACHE_SIZE > 0 return (b->cache_lru >> (3 * (BIHASH_KVP_CACHE_SIZE - 1))) & 7; +#else + return 0; +#endif } static inline void BV (clib_bihash_reset_cache) (BVT (clib_bihash_bucket) * b) { +#if BIHASH_KVP_CACHE_SIZE > 0 u16 initial_lru_value; memset (b->cache, 0xff, sizeof (b->cache)); @@ -180,6 +187,7 @@ static inline void BV (clib_bihash_reset_cache) (BVT (clib_bihash_bucket) * b) initial_lru_value = (0 << 12) | (1 << 9) | (2 << 6) | (3 << 3) | (4 << 0); b->cache_lru = initial_lru_value; +#endif } static inline int BV (clib_bihash_lock_bucket) (BVT (clib_bihash_bucket) * b) @@ -254,7 +262,9 @@ static inline int BV (clib_bihash_search_inline) u32 bucket_index; BVT (clib_bihash_value) * v; BVT (clib_bihash_bucket) * b; +#if BIHASH_KVP_CACHE_SIZE > 0 BVT (clib_bihash_kv) * kvp; +#endif int i, limit; hash = BV (clib_bihash_hash) (key_result); @@ -265,6 +275,7 @@ static inline int BV (clib_bihash_search_inline) if (b->offset == 0) return -1; +#if BIHASH_KVP_CACHE_SIZE > 0 /* Check the cache, if not currently locked */ if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0)) { @@ -280,6 +291,7 @@ static inline int BV (clib_bihash_search_inline) } } } +#endif hash >>= h->log2_nbuckets; @@ -295,9 +307,10 @@ static inline int BV (clib_bihash_search_inline) { if (BV (clib_bihash_key_compare) (v->kvp[i].key, key_result->key)) { - u8 cache_slot; *key_result = v->kvp[i]; +#if BIHASH_KVP_CACHE_SIZE > 0 + u8 cache_slot; /* Try to lock the bucket */ if (BV (clib_bihash_lock_bucket) (b)) { @@ -309,6 +322,7 @@ static inline int BV (clib_bihash_search_inline) BV (clib_bihash_unlock_bucket) (b); h->cache_misses++; } +#endif return 0; } } @@ -323,7 +337,9 @@ static inline int BV (clib_bihash_search_inline_2) u32 bucket_index; BVT (clib_bihash_value) * v; BVT (clib_bihash_bucket) * b; +#if BIHASH_KVP_CACHE_SIZE > 0 BVT (clib_bihash_kv) * kvp; +#endif int i, limit; ASSERT (valuep); @@ -337,6 +353,7 @@ static inline int BV (clib_bihash_search_inline_2) return -1; /* Check the cache, if currently unlocked */ +#if BIHASH_KVP_CACHE_SIZE > 0 if (PREDICT_TRUE ((b->cache_lru & (1 << 15)) == 0)) { limit = BIHASH_KVP_CACHE_SIZE; @@ -351,6 +368,7 @@ static inline int BV (clib_bihash_search_inline_2) } } } +#endif hash >>= h->log2_nbuckets; v = BV (clib_bihash_get_value) (h, b->offset); @@ -365,9 +383,11 @@ 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]; +#if BIHASH_KVP_CACHE_SIZE > 0 + u8 cache_slot; + /* Try to lock the bucket */ if (BV (clib_bihash_lock_bucket) (b)) { @@ -379,6 +399,7 @@ static inline int BV (clib_bihash_search_inline_2) BV (clib_bihash_unlock_bucket) (b); h->cache_misses++; } +#endif return 0; } } -- cgit 1.2.3-korg From 2951d901a5b6ac48b0203b2da9e35ea419b9b4d6 Mon Sep 17 00:00:00 2001 From: Chris Luke Date: Tue, 5 Sep 2017 11:59:55 -0400 Subject: Fixes for issues raised by Coverity (VPP-972) Change-Id: I4b1f27b95d67d48b7a13750ff8754c344ed7afa7 Signed-off-by: Chris Luke --- src/plugins/memif/memif_test.c | 4 ++-- src/vnet/mpls/mpls_api.c | 3 --- src/vppinfra/bihash_template.c | 3 ++- 3 files changed, 4 insertions(+), 6 deletions(-) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/plugins/memif/memif_test.c b/src/plugins/memif/memif_test.c index cbef4dfa..a7c23daa 100644 --- a/src/plugins/memif/memif_test.c +++ b/src/plugins/memif/memif_test.c @@ -186,10 +186,10 @@ api_memif_create (vat_main_t * vam) strncpy ((char *) mp->socket_filename, (char *) socket_filename, 127); vec_free (socket_filename); } - if (socket_filename != 0) + if (secret != 0) { strncpy ((char *) mp->secret, (char *) secret, 16); - vec_free (socket_filename); + vec_free (secret); } memcpy (mp->hw_addr, hw_addr, 6); mp->rx_queues = rx_queues; diff --git a/src/vnet/mpls/mpls_api.c b/src/vnet/mpls/mpls_api.c index 2af6af8f..a44b1a25 100644 --- a/src/vnet/mpls/mpls_api.c +++ b/src/vnet/mpls/mpls_api.c @@ -68,9 +68,6 @@ vl_api_mpls_table_add_del_t_handler (vl_api_mpls_table_add_del_t * mp) vnm = vnet_get_main (); vnm->api_errno = 0; - - rv = (rv == 0) ? vnm->api_errno : rv; - REPLY_MACRO (VL_API_MPLS_TABLE_ADD_DEL_REPLY); } diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 704d1659..2a5a5cd2 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -509,10 +509,11 @@ u8 *BV (format_bihash_lru) (u8 * s, va_list * args) for (i = 0; i < BIHASH_KVP_CACHE_SIZE; i++) s = format (s, "[%d] ", ((cache_lru >> (3 * i)) & 7)); + + return (s); #else return format (s, "cache not configured"); #endif - return (s); } void -- cgit 1.2.3-korg From ace9fc92ca9521c9a20dd3306b76c678052856b9 Mon Sep 17 00:00:00 2001 From: JingLiuZTE Date: Wed, 8 Nov 2017 15:35:01 +0800 Subject: lock init writer_lock must be inited before used. Change-Id: Ib258aa09b3bccc4de6edba0eb75a7eec20f1a61f Signed-off-by: JingLiuZTE (cherry picked from commit 4c9f2a805038a2d4f663b05a3d08ac4ee1eec3da) --- src/vppinfra/bihash_template.c | 1 + 1 file changed, 1 insertion(+) (limited to 'src/vppinfra/bihash_template.c') diff --git a/src/vppinfra/bihash_template.c b/src/vppinfra/bihash_template.c index 2a5a5cd2..56c410b5 100644 --- a/src/vppinfra/bihash_template.c +++ b/src/vppinfra/bihash_template.c @@ -35,6 +35,7 @@ void BV (clib_bihash_init) vec_validate_aligned (h->buckets, nbuckets - 1, CLIB_CACHE_LINE_BYTES); h->writer_lock = clib_mem_alloc_aligned (CLIB_CACHE_LINE_BYTES, CLIB_CACHE_LINE_BYTES); + h->writer_lock[0] = 0; for (i = 0; i < nbuckets; i++) BV (clib_bihash_reset_cache) (h->buckets + i); -- cgit 1.2.3-korg