diff options
Diffstat (limited to 'vppinfra/vppinfra/bihash_template.c')
-rw-r--r-- | vppinfra/vppinfra/bihash_template.c | 487 |
1 files changed, 242 insertions, 245 deletions
diff --git a/vppinfra/vppinfra/bihash_template.c b/vppinfra/vppinfra/bihash_template.c index 0ee92c07570..a8d095c9758 100644 --- a/vppinfra/vppinfra/bihash_template.c +++ b/vppinfra/vppinfra/bihash_template.c @@ -15,92 +15,88 @@ /** @if DOCUMENTATION_IS_IN_BIHASH_DOC_H */ -void BV(clib_bihash_init) - (BVT(clib_bihash) * h, char * name, u32 nbuckets, - uword memory_size) +void BV (clib_bihash_init) + (BVT (clib_bihash) * h, char *name, u32 nbuckets, uword memory_size) { - void * oldheap; + void *oldheap; nbuckets = 1 << (max_log2 (nbuckets)); - h->name = (u8 *)name; + h->name = (u8 *) name; h->nbuckets = nbuckets; h->log2_nbuckets = max_log2 (nbuckets); - h->mheap = mheap_alloc (0 /* use VM */, memory_size); + 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); + 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) +void BV (clib_bihash_free) (BVT (clib_bihash) * h) { - mheap_free (h->mheap); - memset (h, 0, sizeof (*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) +static +BVT (clib_bihash_value) * +BV (value_alloc) (BVT (clib_bihash) * h, u32 log2_pages) { - BVT(clib_bihash_value) * rv = 0; - void * oldheap; + 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) + ASSERT (h->writer_lock[0]); + if (log2_pages >= vec_len (h->freelists) || h->freelists[log2_pages] == 0) { - oldheap = clib_mem_set_heap (h->mheap); + 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; + 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<<log2_pages) with vec_len(rv). - * No clue. - */ - memset (rv, 0xff, sizeof (*rv) * (1<<log2_pages)); - return rv; + 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<<log2_pages) with vec_len(rv). + * No clue. + */ + memset (rv, 0xff, sizeof (*rv) * (1 << log2_pages)); + return rv; } static void -BV(value_free) - (BVT(clib_bihash) * h, - BVT(clib_bihash_value) * v) +BV (value_free) (BVT (clib_bihash) * h, BVT (clib_bihash_value) * v) { - u32 log2_pages; + u32 log2_pages; - ASSERT (h->writer_lock[0]); - - log2_pages = min_log2(vec_len(v)); + ASSERT (h->writer_lock[0]); - ASSERT(vec_len (h->freelists) > log2_pages); + log2_pages = min_log2 (vec_len (v)); - v->next_free = h->freelists[log2_pages]; - h->freelists[log2_pages] = 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) +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(); + 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)) { @@ -109,173 +105,171 @@ BV(make_working_copy) 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. + * 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)) + if ((1 << b->log2_pages) > vec_len (working_copy)) { - vec_validate_aligned (working_copy, (1<<b->log2_pages)-1, - sizeof (u64)); + 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; + _vec_len (working_copy) = 1 << b->log2_pages; clib_mem_set_heap (oldheap); - v = BV(clib_bihash_get_value) (h, b->offset); + v = BV (clib_bihash_get_value) (h, b->offset); - clib_memcpy (working_copy, v, sizeof (*v)*(1<<b->log2_pages)); + 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(); + 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) +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; + BVT (clib_bihash_value) * new_values, *v, *new_v; int i, j, k; - new_values = BV(value_alloc) (h, new_log2_pages); + 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: - ; - } + { + 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) +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; + 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); + u32 cpu_number = os_get_cpu_number (); - bucket_index = hash & (h->nbuckets-1); + 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; - } + { + rv = -1; + goto unlock; + } - v = BV(value_alloc) (h, 0); - *v->kvp = * add_v; + 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); + 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); + 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 = 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; - } - } + { + 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; - } - } + { + 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; - } - } + { + 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; @@ -283,9 +277,9 @@ int BV(clib_bihash_add_del) new_log2_pages = h->saved_bucket.log2_pages + 1; - expand_again: +expand_again: working_copy = h->working_copies[cpu_number]; - new_v = BV(split_and_rehash) (h, working_copy, new_log2_pages); + new_v = BV (split_and_rehash) (h, working_copy, new_log2_pages); if (new_v == 0) { new_log2_pages++; @@ -294,55 +288,54 @@ int BV(clib_bihash_add_del) /* Try to add the new entry */ save_new_v = new_v; - new_hash = BV(clib_bihash_hash) (add_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_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; - } + 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); + BV (value_free) (h, save_new_v); goto expand_again; - expand_ok: +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(); + 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); + v = BV (clib_bihash_get_value) (h, h->saved_bucket.offset); + BV (value_free) (h, v); - unlock: - CLIB_MEMORY_BARRIER(); +unlock: + CLIB_MEMORY_BARRIER (); h->writer_lock[0] = 0; return rv; } -int BV(clib_bihash_search) - (BVT(clib_bihash) * h, - BVT(clib_bihash_kv) *search_key, - BVT(clib_bihash_kv) *valuep) +int BV (clib_bihash_search) + (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; + BVT (clib_bihash_value) * v; + clib_bihash_bucket_t *b; int i; - ASSERT(valuep); + ASSERT (valuep); - hash = BV(clib_bihash_hash) (search_key); + hash = BV (clib_bihash_hash) (search_key); - bucket_index = hash & (h->nbuckets-1); + bucket_index = hash & (h->nbuckets - 1); b = &h->buckets[bucket_index]; if (b->offset == 0) @@ -350,72 +343,70 @@ 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 = 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; - } + 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) +u8 *BV (format_bihash) (u8 * s, va_list * args) { - BVT(clib_bihash) * h - = va_arg (*args, BVT(clib_bihash) *); + 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; + 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]; + b = &h->buckets[i]; if (b->offset == 0) - { - if (verbose > 1) - s = format (s, "[%d]: empty\n", i); - continue; - } + { + 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, "[%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); @@ -424,35 +415,41 @@ u8 * BV(format_bihash) (u8 * s, va_list * args) return s; } -void BV(clib_bihash_foreach_key_value_pair) - (BVT(clib_bihash) * h, - void *callback, - void *arg) +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; - + 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]; + 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++; - } + 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++; + } } } /** @endif */ + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: + * eval: (c-set-style "gnu") + * End: + */ |