diff options
Diffstat (limited to 'hicn-plugin/src/hashtb.c')
| -rwxr-xr-x | hicn-plugin/src/hashtb.c | 1008 |
1 files changed, 1008 insertions, 0 deletions
diff --git a/hicn-plugin/src/hashtb.c b/hicn-plugin/src/hashtb.c new file mode 100755 index 000000000..332da350d --- /dev/null +++ b/hicn-plugin/src/hashtb.c @@ -0,0 +1,1008 @@ +/* + * Copyright (c) 2017-2019 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. + */ + +#include <stdlib.h> +#include <errno.h> +#include <assert.h> +#include <inttypes.h> + +#include <vlib/vlib.h> +#include <vppinfra/pool.h> + +#include "pcs.h" +#include "hashtb.h" +#include "parser.h" +#include "error.h" + +/* return dvd/dvr, rounded up (intended for integer values) */ +#define CEIL(dvd, dvr) \ + ({ \ + __typeof__ (dvd) _dvd = (dvd); \ + __typeof__ (dvr) _dvr = (dvr); \ + (_dvd + _dvr - 1)/_dvr; \ + }) + +#ifndef ALIGN8 +#define ALIGN8(p) (((p) + 0x7) & ~(0x7)) +#endif + +#ifndef ALIGNPTR8 +#define ALIGNPTR8(p) ((void *)(((u8 * )(p) + 0x7) & ~(0x7))) +#endif + +#ifndef ALIGN64 +#define ALIGN64(p) (((p) + 0x3f) & ~(0x3f)) +#endif + +#ifndef TRUE +#define TRUE 1 +#endif + +#ifndef FALSE +#define FALSE 0 +#endif + + +/* + * Offset to aligned start of additional data (PIT/CS, FIB) embedded in each + * node. + */ +u32 ht_node_data_offset_aligned; + +/* Some support for posix vs vpp mem management */ +#define MEM_ALLOC(x) clib_mem_alloc_aligned((x), 8) +#define MEM_FREE(p) clib_mem_free((p)) + +/* + * Internal utilities + */ + +/* Allocate an overflow bucket */ +static hicn_hash_bucket_t * +alloc_overflow_bucket (hicn_hashtb_h h) +{ + hicn_hash_bucket_t *newbkt = NULL; + + if (h->ht_overflow_buckets_used < h->ht_overflow_bucket_count) + { + pool_get_aligned (h->ht_overflow_buckets, newbkt, 8); + + if (newbkt) + { + h->ht_overflow_buckets_used++; + } + } + return (newbkt); +} + +/* Free an overflow bucket; clear caller's pointer */ +static void +free_overflow_bucket (hicn_hashtb_h h, hicn_hash_bucket_t ** pb) +{ + hicn_hash_bucket_t *bkt = *pb; + + ASSERT (h->ht_overflow_buckets_used > 0); + + pool_put (h->ht_overflow_buckets, bkt); + h->ht_overflow_buckets_used--; + *pb = NULL; +} + +/* + * Init, allocate a new hashtable + */ +int +hicn_hashtb_alloc (hicn_hashtb_h * ph, u32 max_elems, size_t app_data_size) +{ + int ret = HICN_ERROR_NONE; + hicn_hashtb_h h = NULL; + u32 count; + u32 total_buckets; + size_t sz; + hicn_hash_node_t *nodep; + hicn_hash_bucket_t *bucket; + + if (ph == NULL) + { + ret = HICN_ERROR_HASHTB_INVAL; + goto done; + } + if (max_elems < HICN_HASHTB_MIN_ENTRIES || + max_elems > HICN_HASHTB_MAX_ENTRIES) + { + goto done; + } + /* Allocate and init main hashtable struct */ + h = MEM_ALLOC (sizeof (hicn_hashtb_t)); + if (h == NULL) + { + ret = HICN_ERROR_HASHTB_NOMEM; + goto done; + } + memset (h, 0, sizeof (hicn_hashtb_t)); + + /* Compute main table bucket (row) count and size, and allocate */ + + /* Consider the last entry as used for containing the overflow bucket */ + total_buckets = CEIL (max_elems, HICN_HASHTB_BUCKET_ENTRIES - 1); + count = ALIGN8 (CEIL (total_buckets, HICN_HASHTB_FILL_FACTOR)); + + h->ht_bucket_count = count; + + /* We _really_ expect to have buckets aligned on cache lines ... */ + sz = sizeof (hicn_hash_bucket_t); + assert (sz == ALIGN64 (sz)); + + h->ht_buckets = MEM_ALLOC (count * sz); + if (h->ht_buckets == NULL) + { + ret = HICN_ERROR_HASHTB_NOMEM; + goto done; + } + memset (h->ht_buckets, 0, count * sz); + + /* + * First time through, compute offset to aligned extra data start in + * each node struct it's crucial that both the node struct (that the + * base hashtable uses) and the extra data area (that's also probably + * a struct) are aligned. + */ + if (ht_node_data_offset_aligned == 0) + { + count = STRUCT_OFFSET_OF (hicn_hash_node_t, hn_data); + ht_node_data_offset_aligned = ALIGN8 (count); + } + //check app struct fits into space provided(HICN_HASH_NODE_APP_DATA_SIZE) + u32 ht_node_data_size; + ht_node_data_size = sizeof (hicn_hash_node_t) - ht_node_data_offset_aligned; + if (app_data_size > ht_node_data_size) + { + clib_error + ("hicn hashtable: fatal error: requested app data size(%u) > hashtb node's configured bytes available(%u), sizeof(hicn_shared_t)=%u, sizeof(hicn_pit_entry_t)=%u, sizeof(hicn_cs_entry_t)=%u", + app_data_size, ht_node_data_size, sizeof (hicn_pcs_shared_t), + sizeof (hicn_pit_entry_t), sizeof (hicn_cs_entry_t)); + } + /* + * Compute entry node count and size, allocate Allocate/'Hide' the + * zero-th node so can use zero as an 'empty' value + */ + pool_alloc_aligned (h->ht_nodes, max_elems, 8); + if (h->ht_nodes == NULL) + { + ret = HICN_ERROR_HASHTB_NOMEM; + goto done; + } + pool_get_aligned (h->ht_nodes, nodep, 8); + //alloc node 0 + nodep = nodep; /* Silence 'not used' warning */ + + h->ht_node_count = max_elems; + h->ht_nodes_used = 1; + + /* + * Compute overflow bucket count and size, allocate + */ + //count = ALIGN8(CEIL(max_elems, HICN_HASHTB_OVERFLOW_FRACTION)); + count = ALIGN8 (total_buckets - h->ht_bucket_count); + + pool_alloc_aligned (h->ht_overflow_buckets, count, 8); + if (h->ht_overflow_buckets == NULL) + { + ret = HICN_ERROR_HASHTB_NOMEM; + goto done; + } + /* 'Hide' the zero-th node so we can use zero as an 'empty' value */ + pool_get_aligned (h->ht_overflow_buckets, bucket, 8); + bucket = bucket; /* Silence 'not used' warning */ + + h->ht_overflow_bucket_count = count; + h->ht_overflow_buckets_used = 1; + +done: + + if (h) + { + if ((ret == HICN_ERROR_NONE) && ph) + { + *ph = h; + } + else + { + hicn_hashtb_free (&h); + } + } + return (ret); +} + +/* + * Free, de-allocate a hashtable + */ +int +hicn_hashtb_free (hicn_hashtb_h * ph) +{ + int ret = 0; + + if (ph) + { + if ((*ph)->ht_nodes) + { + pool_free ((*ph)->ht_nodes); + (*ph)->ht_nodes = 0; + } + if ((*ph)->ht_overflow_buckets) + { + pool_free ((*ph)->ht_overflow_buckets); + (*ph)->ht_overflow_buckets = 0; + } + if ((*ph)->ht_buckets) + { + MEM_FREE ((*ph)->ht_buckets); + (*ph)->ht_buckets = 0; + } + MEM_FREE (*ph); + + *ph = NULL; + } + return (ret); +} + + + +/* + * Basic api to lookup a specific hash+key tuple. This does the entire lookup + * operation, retrieving node structs and comparing keys, so it's not + * optimized for prefetching or high performance. + * + * Returns zero and mails back a node on success, errno otherwise. + */ +int +hicn_hashtb_lookup_node (hicn_hashtb_h h, const u8 * key, + u32 keylen, u64 hashval, u8 is_data, + u32 * node_id, u8 * dpo_ctx_id, u8 * vft_id, + u8 * is_cs, u8 * hash_entry_id, u32 * bucket_id, + u8 * bucket_is_overflow) +{ + return (hicn_hashtb_lookup_node_ex + (h, key, keylen, hashval, is_data, FALSE /* deleted nodes */ , + node_id, + dpo_ctx_id, vft_id, is_cs, hash_entry_id, bucket_id, + bucket_is_overflow)); +} + +/* + * Extended api to lookup a specific hash+key tuple. The implementation + * allows the caller to locate nodes that are marked for deletion, which is + * part of some hashtable applications, such as the FIB. + * + * This does the entire lookup operation, retrieving node structs and comparing + * keys, so it's not optimized for prefetching or high performance. + * + * Returns zero and mails back a node on success, errno otherwise. + */ +int +hicn_hashtb_lookup_node_ex (hicn_hashtb_h h, const u8 * key, + u32 keylen, u64 hashval, u8 is_data, + int include_deleted_p, u32 * node_id, + u8 * dpo_ctx_id, u8 * vft_id, u8 * is_cs, + u8 * hash_entry_id, u32 * bucket_id, + u8 * bucket_is_overflow) +{ + int i, ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND; + int found_p = FALSE; + u32 bidx; + hicn_hash_bucket_t *bucket; + u32 current_bucket_id = ~0; + + /* + * Use some bits of the low half of the hash to locate a row/bucket + * in the table + */ + current_bucket_id = bidx = (hashval & (h->ht_bucket_count - 1)); + + bucket = h->ht_buckets + bidx; + + *bucket_is_overflow = 0; + /* Check the entries in the bucket for matching hash value */ + +loop_buckets: + + for (i = 0; i < HICN_HASHTB_BUCKET_ENTRIES && !found_p; i++) + { + /* + * If an entry is marked for deletion, ignore it unless the + * caller explicitly wants these nodes. + */ + if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED) + { + if (!include_deleted_p) + { + continue; + } + } + if (bucket->hb_entries[i].he_msb64 == hashval) + { + /* + * Found a candidate - must retrieve the actual node + * and check the key. + */ + *node_id = bucket->hb_entries[i].he_node; + *dpo_ctx_id = bucket->hb_entries[i].dpo_ctx_id; + *vft_id = bucket->hb_entries[i].vft_id; + *is_cs = + bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_CS_ENTRY; + *hash_entry_id = i; + *bucket_id = current_bucket_id; + /* + * If we are doing lookup for a data, do not take a + * lock in case of a hit with a CS entry + */ + if (!(is_data && *is_cs)) + { + bucket->hb_entries[i].locks++; + } + found_p = TRUE; + ret = HICN_ERROR_NONE; + goto done; + } + } + + /* + * Be prepared to continue to an overflow bucket if necessary. We + * only expect the last entry in a bucket to refer to an overflow + * bucket... + */ + i = HICN_HASHTB_BUCKET_ENTRIES - 1; + if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW) + { + current_bucket_id = bucket->hb_entries[i].he_node; + bucket = pool_elt_at_index (h->ht_overflow_buckets, + bucket->hb_entries[i].he_node); + *bucket_is_overflow = 1; + goto loop_buckets; + } +done: + + return (ret); +} + +/** + * This function allows to split the hash verification from the comparison of + * the entire key. Useful to exploit prefertching. + * return 1 if equals, 0 otherwise + */ +int +hicn_node_compare (const u8 * key, u32 keylen, hicn_hash_node_t * node) +{ + + int ret = 0; + + if (key && keylen == node->hn_keysize) + { + ret = (memcmp (key, node->hn_key.ks.key, keylen) == 0); + } + return ret; +} + +/* + * Utility to init a new entry in a hashtable bucket/row. We use this to add + * new a node+hash, and to clear out an entry during removal. + */ +void +hicn_hashtb_init_entry (hicn_hash_entry_t * entry, u32 nodeidx, + u64 hashval, u32 locks) +{ + entry->he_msb64 = hashval; + entry->he_node = nodeidx; + + /* Clear out some other fields in the entry */ + entry->he_flags = 0; + entry->locks = locks; +} + +/* + * Insert a node into the hashtable. We expect the caller has a) computed the + * hash value to use, b) initialized the node with the hash and key info, and + * c) filled in its app-specific data portion of the node. + */ + +int +hicn_hashtb_insert (hicn_hashtb_h h, hicn_hash_node_t * node, + hicn_hash_entry_t ** hash_entry, u64 hash, + u32 * node_id, + u8 * dpo_ctx_id, u8 * vft_id, u8 * is_cs, + u8 * hash_entry_id, u32 * bucket_id, + u8 * bucket_is_overflow) +{ + int i, ret = HICN_ERROR_HASHTB_INVAL; + u32 bidx; + hicn_hash_bucket_t *bucket, *newbkt; + int use_seven; + u32 current_bucket_id = ~0; + int is_overflow = 0; + + *hash_entry = NULL; + + if (h == NULL) + { + goto done; + } + /* + * Use some bits of the low half of the hash to locate a row/bucket + * in the table + */ + current_bucket_id = bidx = (hash & (h->ht_bucket_count - 1)); + + bucket = h->ht_buckets + bidx; + + use_seven = (h->ht_flags & HICN_HASHTB_FLAG_USE_SEVEN); + + /* Locate a free entry slot in the bucket */ + +loop_buckets: + + for (i = 0; i < HICN_HASHTB_BUCKET_ENTRIES; i++) + { + + /* + * If an entry is marked for deletion, ignore it + */ + if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED) + { + continue; + } + /* + * Be sure that we are not inserting the same entry twice + */ + if (bucket->hb_entries[i].he_msb64 == hash) + { + /* + * We hit an existing pit entry. increase lock. + */ + + *node_id = bucket->hb_entries[i].he_node; + *dpo_ctx_id = bucket->hb_entries[i].dpo_ctx_id; + *vft_id = bucket->hb_entries[i].vft_id; + *is_cs = + bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_CS_ENTRY; + *hash_entry_id = i; + *bucket_id = current_bucket_id; + *hash_entry = &(bucket->hb_entries[i]); + /* + * If we are doing lookup for a data, do not take a + * lock in case of a hit with a CS entry + */ + bucket->hb_entries[i].locks++; + *bucket_is_overflow = is_overflow; + ret = HICN_ERROR_HASHTB_EXIST; + goto done; + } + if ((bucket->hb_entries[i].he_msb64 == 0LL) && + (bucket->hb_entries[i].he_node == 0)) + { + /* Found a candidate -- fill it in */ + + /* + * Special case if the application asked not to use + * the last entry in each bucket. + */ + if ((i != (HICN_HASHTB_BUCKET_ENTRIES - 1)) || use_seven) + { + hicn_hashtb_init_entry (&(bucket->hb_entries[i]), + NODE_IDX_FROM_NODE (node, h), hash, 0); + + *hash_entry = &(bucket->hb_entries[i]); + + node->bucket_id = current_bucket_id; + node->entry_idx = i; + if (is_overflow) + node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET; + + ret = HICN_ERROR_NONE; + goto done; + } + } + } + /* + * Be prepared to continue to an overflow bucket if necessary, or to + * add a new overflow bucket. We only expect the last entry in a + * bucket to refer to an overflow bucket... + */ + i = HICN_HASHTB_BUCKET_ENTRIES - 1; + if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW) + { + /* Existing overflow bucket - re-start the search loop */ + current_bucket_id = bucket->hb_entries[i].he_node; + bucket = pool_elt_at_index (h->ht_overflow_buckets, current_bucket_id); + is_overflow = 1; + goto loop_buckets; + + } + else + { + /* + * Overflow - reached the end of a bucket without finding a + * free entry slot. Need to allocate an overflow bucket, and + * connect it to this bucket. + */ + newbkt = alloc_overflow_bucket (h); + if (newbkt == NULL) + { + ret = HICN_ERROR_HASHTB_NOMEM; + goto done; + } + /* + * We're touching some more bytes than we absolutely have to + * here, but ... that seems ok. + */ + memset (newbkt, 0, sizeof (hicn_hash_bucket_t)); + + if (use_seven) + { + /* + * Copy existing entry into new bucket - we really + * expect these to be properly aligned so they can be + * treated as int. + */ + memcpy (&(newbkt->hb_entries[0]), + &(bucket->hb_entries[i]), sizeof (hicn_hash_entry_t)); + + /* Update bucket id and entry_idx on the hash node */ + hicn_hash_node_t *node = + pool_elt_at_index (h->ht_nodes, newbkt->hb_entries[0].he_node); + node->bucket_id = (newbkt - h->ht_overflow_buckets); + node->entry_idx = 0; + node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET; + + } + /* + * Connect original bucket to the index of the new overflow + * bucket + */ + bucket->hb_entries[i].he_flags |= HICN_HASH_ENTRY_FLAG_OVERFLOW; + bucket->hb_entries[i].he_node = (newbkt - h->ht_overflow_buckets); + + /* Add new entry to new overflow bucket */ + bucket = newbkt; + + /* + * Use entry [1] in the new bucket _if_ we just copied into + * entry [zero] above. + */ + if (use_seven) + { + + hicn_hashtb_init_entry (&(bucket->hb_entries[1]), + NODE_IDX_FROM_NODE (node, h), hash, 0); + *hash_entry = &(bucket->hb_entries[1]); + + node->bucket_id = (newbkt - h->ht_overflow_buckets); + node->entry_idx = 1; + node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET; + } + else + { + + hicn_hashtb_init_entry (&(bucket->hb_entries[0]), + NODE_IDX_FROM_NODE (node, h), hash, 0); + *hash_entry = &(bucket->hb_entries[0]); + node->bucket_id = (newbkt - h->ht_overflow_buckets); + node->entry_idx = 0; + node->hn_flags |= HICN_HASH_NODE_OVERFLOW_BUCKET; + } + } + + /* And we're done with the overflow bucket */ + ret = HICN_ERROR_NONE; + +done: + + return (ret); +} + +/* + * Delete a node from a hashtable using the node itself, and delete/free the + * node. Caller's pointer is cleared on success. + */ +void +hicn_hashtb_delete (hicn_hashtb_h h, hicn_hash_node_t ** pnode, u64 hashval) +{ + + hicn_hashtb_remove_node (h, *pnode, hashval); + hicn_hashtb_free_node (h, *pnode); + *pnode = NULL; + +} + +/* + * Delete an entry from a hashtable using the node itself. If the node was + * stored in an overflow bucket, and the bucket is empty after freeing the + * node, the bucket is freed as well. + */ +void +hicn_hashtb_remove_node (hicn_hashtb_h h, hicn_hash_node_t * node, + u64 hashval) +{ + int i, count; + u32 bidx, overflow_p; + hicn_hash_bucket_t *bucket, *parent; + + if ((h == NULL) || (node == NULL)) + { + goto done; + } + if (node->hn_flags & HICN_HASH_NODE_OVERFLOW_BUCKET) + bucket = pool_elt_at_index (h->ht_overflow_buckets, node->bucket_id); + else + { + /* + * Use some bits of the low half of the hash to locate a + * row/bucket in the table + */ + bidx = (hashval & (h->ht_bucket_count - 1)); + ASSERT (bidx == node->bucket_id); + bucket = h->ht_buckets + node->bucket_id; + } + + overflow_p = node->hn_flags & HICN_HASH_NODE_OVERFLOW_BUCKET; + + /* Clear out the entry. */ + hicn_hashtb_init_entry (&(bucket->hb_entries[node->entry_idx]), 0, 0LL, 0); + + if (!overflow_p) + { + /* + * And we're done, in the easy case where we didn't change an + * overflow bucket + */ + goto done; + } + /* + * The special case: if this is the last remaining entry in an + * overflow bucket, liberate the bucket. That in turn has a special + * case if this bucket is in the middle of a chain of overflow + * buckets. + * + * Note that we're not trying aggressively (yet) to condense buckets at + * every possible opportunity. + */ + + /* + * Reset this flag; we'll set it again if this bucket links to + * another + */ + overflow_p = FALSE; + + for (i = 0, count = 0; i < HICN_HASHTB_BUCKET_ENTRIES; i++) + { + if (bucket->hb_entries[i].he_node != 0) + { + count++; + } + if (i == (HICN_HASHTB_BUCKET_ENTRIES - 1) && + (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW)) + { + count--; /* Doesn't count as a 'real' entry */ + overflow_p = TRUE; + } + } + + if (count > 0) + { + /* Still a (real) entry in the row */ + goto done; + } + /* + * Need to locate the predecessor of 'bucket': start at the beginning + * of the chain of buckets and move forward + */ + bidx = (hashval & (h->ht_bucket_count - 1)); + + for (parent = h->ht_buckets + bidx; parent != NULL;) + { + + if ((parent->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_flags & + HICN_HASH_ENTRY_FLAG_OVERFLOW) == 0) + { + parent = NULL; + break; + } + bidx = parent->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_node; + + if (pool_elt_at_index (h->ht_overflow_buckets, bidx) == bucket) + { + /* + * Found the predecessor of 'bucket'. If 'bucket' has + * a successor, connect 'parent' to it, and take + * 'bucket out of the middle. + */ + if (overflow_p) + { + parent->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_node = + bucket->hb_entries[(HICN_HASHTB_BUCKET_ENTRIES - 1)].he_node; + } + else + { + /* + * Just clear the predecessor entry pointing + * at 'bucket' + */ + hicn_hashtb_init_entry (&parent->hb_entries + [(HICN_HASHTB_BUCKET_ENTRIES - 1)], 0, + 0LL, 0); + } + + break; + } + /* + * After the first iteration, 'parent' will be an overflow + * bucket too + */ + parent = pool_elt_at_index (h->ht_overflow_buckets, bidx); + } + + /* We really expect to have found the predecessor */ + ASSERT (parent != NULL); + + /* And now, finally, we can put 'bucket' back on the free list */ + free_overflow_bucket (h, &bucket); + +done: + return; +} + +/* + * Prepare a hashtable node, supplying the key, and computed hash info. + */ +void +hicn_hashtb_init_node (hicn_hashtb_h h, hicn_hash_node_t * node, + const u8 * key, u32 keylen) +{ + assert (h != NULL); + assert (node != NULL); + assert (keylen <= HICN_PARAM_HICN_NAME_LEN_MAX); + + /* Init the node struct */ + node->hn_flags = HICN_HASH_NODE_FLAGS_DEFAULT; + node->hn_keysize = 0; + node->hn_keysize = keylen; + memcpy (node->hn_key.ks.key, key, keylen); + node->bucket_id = ~0; + node->entry_idx = ~0; +} + +/* + * Release a hashtable node back to the free list when an entry is cleared + */ +void +hicn_hashtb_free_node (hicn_hashtb_h h, hicn_hash_node_t * node) +{ + ASSERT (h->ht_nodes_used > 0); + + /* Return 'node' to the free list */ + pool_put (h->ht_nodes, node); + h->ht_nodes_used--; + +} + +/* + * Walk a hashtable, iterating through the nodes, keeping context in 'ctx'. + */ +int +hicn_hashtb_next_node (hicn_hashtb_h h, hicn_hash_node_t ** pnode, u64 * ctx) +{ + int i, j, ret = HICN_ERROR_HASHTB_INVAL; + u32 bidx, entry; + hicn_hash_bucket_t *bucket; + + if ((h == NULL) || (pnode == NULL) || (ctx == NULL)) + { + goto done; + } + /* Special-case for new iteration */ + if (*ctx == HICN_HASH_WALK_CTX_INITIAL) + { + bidx = 0; + bucket = &h->ht_buckets[0]; + entry = 0; + j = 0; + i = 0; + goto search_table; + } + /* Convert context to bucket and entry indices */ + bidx = *ctx & 0xffffffffLL; + entry = *ctx >> 32; + + if (bidx >= h->ht_bucket_count) + { + ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND; + goto done; + } + bucket = h->ht_buckets + bidx; + + /* Init total index into entries (includes fixed bucket and overflow) */ + j = 0; + +skip_processed_bucket_chunks: + /* + * Figure out where to resume the search for the next entry in the + * table, by trying to find the last entry returned, from the cookie. + * Loop walks one (regular or overflow) bucket chunk, label is used + * for walking chain of chunks. Note that if there was a deletion or + * an addition that created an overflow, iterator can skip entries or + * return duplicate entries, for entries that are present from before + * the walk starts until after it ends. + */ + + for (i = 0; i < HICN_HASHTB_BUCKET_ENTRIES; i++, j++) + { + if (j > entry) + { + /* + * Start search for next here, use existing 'bucket' + * and 'i' + */ + break; + } + /* + * If an entry is marked for deletion, ignore it + */ + if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED) + { + continue; + } + /* + * Be prepared to continue to an overflow bucket if + * necessary. (We only expect the last entry in a bucket to + * refer to an overflow bucket...) + */ + if (i == (HICN_HASHTB_BUCKET_ENTRIES - 1)) + { + if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW) + { + bucket = pool_elt_at_index (h->ht_overflow_buckets, + bucket->hb_entries[i].he_node); + + /* Increment overall entry counter 'j' */ + j++; + + goto skip_processed_bucket_chunks; + } + /* + * end of row (end of fixed bucket plus any + * overflows) + */ + i = 0; + j = 0; + + bidx++; + + /* Special case - we're at the end */ + if (bidx >= h->ht_bucket_count) + { + ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND; + goto done; + } + bucket = h->ht_buckets + bidx; + break; + } + } + +search_table: + + /* + * Now we're searching through the table for the next entry that's + * set + */ + + for (; i < HICN_HASHTB_BUCKET_ENTRIES; i++, j++) + { + /* + * If an entry is marked for deletion, ignore it + */ + if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_DELETED) + { + continue; + } + /* Is this entry set? */ + if (bucket->hb_entries[i].he_node != 0) + { + + /* Retrieve the node struct */ + *pnode = pool_elt_at_index (h->ht_nodes, + bucket->hb_entries[i].he_node); + + /* + * Set 'entry' as we exit, so we can update the + * cookie + */ + entry = j; + ret = HICN_ERROR_NONE; + break; + } + /* + * Be prepared to continue to an overflow bucket if + * necessary. (We only expect the last entry in a bucket to + * refer to an overflow bucket...) + */ + if (i == (HICN_HASHTB_BUCKET_ENTRIES - 1)) + { + if (bucket->hb_entries[i].he_flags & HICN_HASH_ENTRY_FLAG_OVERFLOW) + { + bucket = pool_elt_at_index (h->ht_overflow_buckets, + bucket->hb_entries[i].he_node); + /* + * Reset per-bucket index 'i', here (not done + * in iterator) + */ + i = 0; + /* Increment overall entry counter 'j' */ + j++; + + goto search_table; + } + else + { + /* + * Move to next bucket, resetting per-bucket + * and overall entry indexes + */ + i = 0; + j = 0; + + bidx++; + + /* Special case - we're at the end */ + if (bidx >= h->ht_bucket_count) + { + ret = HICN_ERROR_HASHTB_HASH_NOT_FOUND; + goto done; + } + bucket = h->ht_buckets + bidx; + goto search_table; + } + } + } + +done: + + if (ret == HICN_ERROR_NONE) + { + /* Update context */ + *ctx = bidx; + *ctx |= ((u64) entry << 32); + } + return (ret); +} + +int +hicn_hashtb_key_to_buf (u8 ** vec_res, hicn_hashtb_h h, + const hicn_hash_node_t * node) +{ + int ret = HICN_ERROR_NONE; + u8 *vec = *vec_res; + + if (node->hn_keysize <= HICN_HASH_KEY_BYTES) + { + vec_add (vec, node->hn_key.ks.key, node->hn_keysize); + } + *vec_res = vec; + return (ret); +} + +/* + * fd.io coding-style-patch-verification: ON + * + * Local Variables: eval: (c-set-style "gnu") End: + */ |