From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 11349C324 for ; Fri, 5 Jun 2015 16:33:28 +0200 (CEST) Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga102.fm.intel.com with ESMTP; 05 Jun 2015 07:33:26 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,559,1427785200"; d="scan'208";a="737735428" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by fmsmga002.fm.intel.com with ESMTP; 05 Jun 2015 07:33:26 -0700 Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com [10.237.217.46]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id t55EXOtr003756 for ; Fri, 5 Jun 2015 15:33:24 +0100 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t55EXOKj007123 for ; Fri, 5 Jun 2015 15:33:24 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t55EXOp9007119 for dev@dpdk.org; Fri, 5 Jun 2015 15:33:24 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Fri, 5 Jun 2015 15:33:20 +0100 Message-Id: <1433514804-7075-3-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH 2/6] hash: replace existing hash library with cuckoo hash implementation X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 05 Jun 2015 14:33:30 -0000 This patch replaces the existing hash library with another approach, using the Cuckoo Hash method to resolve collisions (open addressing), which pushes items from a full bucket when a new entry tries to be added in it, storing the evicted entry in an alternative location, using a secondary hash function. This gives the user the ability to store more entries when a bucket is full, in comparison with the previous implementation. Therefore, the unit test has been updated, as some scenarios have changed (such as the previous removed restriction). Also note that the API has not been changed, although new fields have been added in the rte_hash structure. The main change when creating a new table is that the number of entries per bucket is fixed now, so its parameter is ignored now (still there to maintain the same parameters structure). As a last note, the maximum burst size in lookup_burst function hash been increased to 64, to improve performance. Signed-off-by: Pablo de Lara --- app/test/test_hash.c | 86 +---- lib/librte_hash/rte_hash.c | 797 ++++++++++++++++++++++++++++++++++----------- lib/librte_hash/rte_hash.h | 157 +++++---- 3 files changed, 721 insertions(+), 319 deletions(-) diff --git a/app/test/test_hash.c b/app/test/test_hash.c index 1da27c5..4ef99ee 100644 --- a/app/test/test_hash.c +++ b/app/test/test_hash.c @@ -169,7 +169,6 @@ static struct flow_key keys[5] = { { /* Parameters used for hash table in unit test functions. Name set later. */ static struct rte_hash_parameters ut_params = { .entries = 64, - .bucket_entries = 4, .key_len = sizeof(struct flow_key), /* 13 */ .hash_func = rte_jhash, .hash_func_init_val = 0, @@ -527,21 +526,18 @@ static int test_five_keys(void) /* * Add keys to the same bucket until bucket full. * - add 5 keys to the same bucket (hash created with 4 keys per bucket): - * first 4 successful, 5th unsuccessful - * - lookup the 5 keys: 4 hits, 1 miss - * - add the 5 keys again: 4 OK, one error as bucket is full - * - lookup the 5 keys: 4 hits (updated data), 1 miss - * - delete the 5 keys: 5 OK (even if the 5th is not in the table) + * first 4 successful, 5th successful, pushing existing item in bucket + * - lookup the 5 keys: 5 hits + * - add the 5 keys again: 5 OK + * - lookup the 5 keys: 5 hits (updated data) + * - delete the 5 keys: 5 OK * - lookup the 5 keys: 5 misses - * - add the 5th key: OK - * - lookup the 5th key: hit */ static int test_full_bucket(void) { struct rte_hash_parameters params_pseudo_hash = { .name = "test4", .entries = 64, - .bucket_entries = 4, .key_len = sizeof(struct flow_key), /* 13 */ .hash_func = pseudo_hash, .hash_func_init_val = 0, @@ -555,7 +551,7 @@ static int test_full_bucket(void) handle = rte_hash_create(¶ms_pseudo_hash); RETURN_IF_ERROR(handle == NULL, "hash creation failed"); - /* Fill bucket*/ + /* Fill bucket */ for (i = 0; i < 4; i++) { pos[i] = rte_hash_add_key(handle, &keys[i]); print_key_info("Add", &keys[i], pos[i]); @@ -563,47 +559,36 @@ static int test_full_bucket(void) "failed to add key (pos[%u]=%d)", i, pos[i]); expected_pos[i] = pos[i]; } - /* This shouldn't work because the bucket is full */ + /* This should work and will push one of the items in the bucket because it is full */ pos[4] = rte_hash_add_key(handle, &keys[4]); print_key_info("Add", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != -ENOSPC, - "fail: added key to full bucket (pos[4]=%d)", pos[4]); + RETURN_IF_ERROR(pos[4] < 0, + "failed to add key (pos[4]=%d)", pos[4]); + expected_pos[5] = pos[5]; /* Lookup */ - for (i = 0; i < 4; i++) { + for (i = 0; i < 5; i++) { pos[i] = rte_hash_lookup(handle, &keys[i]); print_key_info("Lkp", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to find key (pos[%u]=%d)", i, pos[i]); } - pos[4] = rte_hash_lookup(handle, &keys[4]); - print_key_info("Lkp", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != -ENOENT, - "fail: found non-existent key (pos[4]=%d)", pos[4]); /* Add - update */ - for (i = 0; i < 4; i++) { + for (i = 0; i < 5; i++) { pos[i] = rte_hash_add_key(handle, &keys[i]); print_key_info("Add", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to add key (pos[%u]=%d)", i, pos[i]); } - pos[4] = rte_hash_add_key(handle, &keys[4]); - print_key_info("Add", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != -ENOSPC, - "fail: added key to full bucket (pos[4]=%d)", pos[4]); /* Lookup */ - for (i = 0; i < 4; i++) { + for (i = 0; i < 5; i++) { pos[i] = rte_hash_lookup(handle, &keys[i]); print_key_info("Lkp", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to find key (pos[%u]=%d)", i, pos[i]); } - pos[4] = rte_hash_lookup(handle, &keys[4]); - print_key_info("Lkp", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != -ENOENT, - "fail: found non-existent key (pos[4]=%d)", pos[4]); /* Delete 1 key, check other keys are still found */ pos[1] = rte_hash_del_key(handle, &keys[1]); @@ -623,35 +608,21 @@ static int test_full_bucket(void) RETURN_IF_ERROR(pos[1] < 0, "failed to add key (pos[1]=%d)", pos[1]); /* Delete */ - for (i = 0; i < 4; i++) { + for (i = 0; i < 5; i++) { pos[i] = rte_hash_del_key(handle, &keys[i]); print_key_info("Del", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != expected_pos[i], "failed to delete key (pos[%u]=%d)", i, pos[i]); } - pos[4] = rte_hash_del_key(handle, &keys[4]); - print_key_info("Del", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != -ENOENT, - "fail: deleted non-existent key (pos[4]=%d)", pos[4]); /* Lookup */ - for (i = 0; i < 4; i++) { + for (i = 0; i < 5; i++) { pos[i] = rte_hash_lookup(handle, &keys[i]); print_key_info("Lkp", &keys[i], pos[i]); RETURN_IF_ERROR(pos[i] != -ENOENT, "fail: found non-existent key (pos[%u]=%d)", i, pos[i]); } - /* Add and lookup the 5th key */ - pos[4] = rte_hash_add_key(handle, &keys[4]); - print_key_info("Add", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] < 0, "failed to add key (pos[4]=%d)", pos[4]); - expected_pos[4] = pos[4]; - pos[4] = rte_hash_lookup(handle, &keys[4]); - print_key_info("Lkp", &keys[4], pos[4]); - RETURN_IF_ERROR(pos[4] != expected_pos[4], - "failed to find key (pos[4]=%d)", pos[4]); - rte_hash_free(handle); /* Cover the NULL case. */ @@ -1017,18 +988,8 @@ static int test_hash_creation_with_bad_parameters(void) } memcpy(¶ms, &ut_params, sizeof(params)); - params.name = "creation_with_bad_parameters_1"; - params.bucket_entries = RTE_HASH_BUCKET_ENTRIES_MAX + 1; - handle = rte_hash_create(¶ms); - if (handle != NULL) { - rte_hash_free(handle); - printf("Impossible creating hash sucessfully with bucket_entries in parameter exceeded\n"); - return -1; - } - - memcpy(¶ms, &ut_params, sizeof(params)); params.name = "creation_with_bad_parameters_2"; - params.entries = params.bucket_entries - 1; + params.entries = RTE_HASH_BUCKET_ENTRIES - 1; handle = rte_hash_create(¶ms); if (handle != NULL) { rte_hash_free(handle); @@ -1048,16 +1009,6 @@ static int test_hash_creation_with_bad_parameters(void) memcpy(¶ms, &ut_params, sizeof(params)); params.name = "creation_with_bad_parameters_4"; - params.bucket_entries = params.bucket_entries - 1; - handle = rte_hash_create(¶ms); - if (handle != NULL) { - rte_hash_free(handle); - printf("Impossible creating hash sucessfully if bucket_entries in parameter is not power of 2\n"); - return -1; - } - - memcpy(¶ms, &ut_params, sizeof(params)); - params.name = "creation_with_bad_parameters_5"; params.key_len = 0; handle = rte_hash_create(¶ms); if (handle != NULL) { @@ -1067,7 +1018,7 @@ static int test_hash_creation_with_bad_parameters(void) } memcpy(¶ms, &ut_params, sizeof(params)); - params.name = "creation_with_bad_parameters_6"; + params.name = "creation_with_bad_parameters_5"; params.key_len = RTE_HASH_KEY_LENGTH_MAX + 1; handle = rte_hash_create(¶ms); if (handle != NULL) { @@ -1077,7 +1028,7 @@ static int test_hash_creation_with_bad_parameters(void) } memcpy(¶ms, &ut_params, sizeof(params)); - params.name = "creation_with_bad_parameters_7"; + params.name = "creation_with_bad_parameters_6"; params.socket_id = RTE_MAX_NUMA_NODES + 1; handle = rte_hash_create(¶ms); if (handle != NULL) { @@ -1158,7 +1109,6 @@ static uint8_t key[16] = {0x00, 0x01, 0x02, 0x03, static struct rte_hash_parameters hash_params_ex = { .name = NULL, .entries = 64, - .bucket_entries = 4, .key_len = 0, .hash_func = NULL, .hash_func_init_val = 0, diff --git a/lib/librte_hash/rte_hash.c b/lib/librte_hash/rte_hash.c index 9245716..cbfe17e 100644 --- a/lib/librte_hash/rte_hash.c +++ b/lib/librte_hash/rte_hash.c @@ -1,7 +1,7 @@ /*- * BSD LICENSE * - * Copyright(c) 2010-2014 Intel Corporation. All rights reserved. + * Copyright(c) 2010-2015 Intel Corporation. All rights reserved. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -83,64 +83,12 @@ EAL_REGISTER_TAILQ(rte_hash_tailq) #define DEFAULT_HASH_FUNC rte_jhash #endif -/* Signature bucket size is a multiple of this value */ -#define SIG_BUCKET_ALIGNMENT 16 - -/* Stoered key size is a multiple of this value */ -#define KEY_ALIGNMENT 16 +/* Bucket size is a multiple of this value */ +#define BUCKET_ALIGNMENT 16 /* The high bit is always set in real signatures */ #define NULL_SIGNATURE 0 -/* Returns a pointer to the first signature in specified bucket. */ -static inline hash_sig_t * -get_sig_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index) -{ - return (hash_sig_t *) - &(h->sig_tbl[bucket_index * h->sig_tbl_bucket_size]); -} - -/* Returns a pointer to the first key in specified bucket. */ -static inline uint8_t * -get_key_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index) -{ - return (uint8_t *) &(h->key_tbl[bucket_index * h->bucket_entries * - h->key_tbl_key_size]); -} - -/* Returns a pointer to a key at a specific position in a specified bucket. */ -static inline void * -get_key_from_bucket(const struct rte_hash *h, uint8_t *bkt, uint32_t pos) -{ - return (void *) &bkt[pos * h->key_tbl_key_size]; -} - -/* Does integer division with rounding-up of result. */ -static inline uint32_t -div_roundup(uint32_t numerator, uint32_t denominator) -{ - return (numerator + denominator - 1) / denominator; -} - -/* Increases a size (if needed) to a multiple of alignment. */ -static inline uint32_t -align_size(uint32_t val, uint32_t alignment) -{ - return alignment * div_roundup(val, alignment); -} - -/* Returns the index into the bucket of the first occurrence of a signature. */ -static inline int -find_first(uint32_t sig, const uint32_t *sig_bucket, uint32_t num_sigs) -{ - uint32_t i; - for (i = 0; i < num_sigs; i++) { - if (sig == sig_bucket[i]) - return i; - } - return -1; -} - struct rte_hash * rte_hash_find_existing(const char *name) { @@ -165,25 +113,49 @@ rte_hash_find_existing(const char *name) return h; } +/* Does integer division with rounding-up of result. */ +static inline uint32_t +div_roundup(uint32_t numerator, uint32_t denominator) +{ + return (numerator + denominator - 1) / denominator; +} + +/* Increases a size (if needed) to a multiple of alignment. */ +static inline uint32_t +align_size(uint32_t val, uint32_t alignment) +{ + return alignment * div_roundup(val, alignment); +} + struct rte_hash * rte_hash_create(const struct rte_hash_parameters *params) { struct rte_hash *h = NULL; struct rte_tailq_entry *te; - uint32_t num_buckets, sig_bucket_size, key_size, - hash_tbl_size, sig_tbl_size, key_tbl_size, mem_size; + uint32_t num_buckets, bucket_size, + tbl_size, mem_size, hash_struct_size; char hash_name[RTE_HASH_NAMESIZE]; struct rte_hash_list *hash_list; + void *k = NULL; + struct rte_ring *r = NULL; + char ring_name[RTE_RING_NAMESIZE]; + unsigned key_entry_size; + const unsigned anyalignment = 0; + unsigned i; + void *ptr; hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); + if (params == NULL) { + RTE_LOG(ERR, HASH, "rte_hash_create has no parameters\n"); + return NULL; + } + /* Check for valid parameters */ - if ((params == NULL) || - (params->entries > RTE_HASH_ENTRIES_MAX) || - (params->bucket_entries > RTE_HASH_BUCKET_ENTRIES_MAX) || - (params->entries < params->bucket_entries) || + if ((params->entries > RTE_HASH_ENTRIES_MAX) || + (params->entries < RTE_HASH_BUCKET_ENTRIES) || !rte_is_power_of_2(params->entries) || - !rte_is_power_of_2(params->bucket_entries) || + !rte_is_power_of_2(RTE_HASH_BUCKET_ENTRIES) || (params->key_len == 0) || (params->key_len > RTE_HASH_KEY_LENGTH_MAX)) { rte_errno = EINVAL; @@ -194,19 +166,18 @@ rte_hash_create(const struct rte_hash_parameters *params) snprintf(hash_name, sizeof(hash_name), "HT_%s", params->name); /* Calculate hash dimensions */ - num_buckets = params->entries / params->bucket_entries; - sig_bucket_size = align_size(params->bucket_entries * - sizeof(hash_sig_t), SIG_BUCKET_ALIGNMENT); - key_size = align_size(params->key_len, KEY_ALIGNMENT); + num_buckets = params->entries / RTE_HASH_BUCKET_ENTRIES; + + bucket_size = align_size(sizeof(struct rte_hash_bucket), BUCKET_ALIGNMENT); - hash_tbl_size = align_size(sizeof(struct rte_hash), RTE_CACHE_LINE_SIZE); - sig_tbl_size = align_size(num_buckets * sig_bucket_size, + hash_struct_size = align_size(sizeof(struct rte_hash), RTE_CACHE_LINE_SIZE); + tbl_size = align_size(num_buckets * bucket_size, RTE_CACHE_LINE_SIZE); - key_tbl_size = align_size(num_buckets * key_size * - params->bucket_entries, RTE_CACHE_LINE_SIZE); /* Total memory required for hash context */ - mem_size = hash_tbl_size + sig_tbl_size + key_tbl_size; + mem_size = hash_struct_size + tbl_size; + + key_entry_size = params->key_len; rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); @@ -216,6 +187,7 @@ rte_hash_create(const struct rte_hash_parameters *params) if (strncmp(params->name, h->name, RTE_HASH_NAMESIZE) == 0) break; } + rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); if (te != NULL) goto exit; @@ -226,36 +198,73 @@ rte_hash_create(const struct rte_hash_parameters *params) } h = (struct rte_hash *)rte_zmalloc_socket(hash_name, mem_size, - RTE_CACHE_LINE_SIZE, params->socket_id); + RTE_CACHE_LINE_SIZE, params->socket_id); + if (h == NULL) { RTE_LOG(ERR, HASH, "memory allocation failed\n"); rte_free(te); goto exit; } + k = rte_zmalloc_socket(NULL, key_entry_size * (params->entries + 1), + anyalignment, params->socket_id); + + if (k == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + h = NULL; + rte_free(te); + rte_free(h); + goto exit; + } + + snprintf(ring_name, sizeof(ring_name), "HT_%s", params->name); + r = rte_ring_lookup(ring_name); + if (r != NULL) { + /* clear the free ring */ + while (rte_ring_dequeue(r, &ptr) == 0) + rte_pause(); + } else + r = rte_ring_create(ring_name, rte_align32pow2(params->entries), + params->socket_id, 0); + if (r == NULL) { + RTE_LOG(ERR, HASH, "memory allocation failed\n"); + rte_free(te); + rte_free(h); + h = NULL; + rte_free(k); + goto exit; + } + /* Setup hash context */ snprintf(h->name, sizeof(h->name), "%s", params->name); h->entries = params->entries; - h->bucket_entries = params->bucket_entries; + h->bucket_entries = RTE_HASH_BUCKET_ENTRIES; h->key_len = params->key_len; + h->key_entry_size = key_entry_size; h->hash_func_init_val = params->hash_func_init_val; + h->socket_id = params->socket_id; + h->num_buckets = num_buckets; h->bucket_bitmask = h->num_buckets - 1; - h->sig_msb = 1 << (sizeof(hash_sig_t) * 8 - 1); - h->sig_tbl = (uint8_t *)h + hash_tbl_size; - h->sig_tbl_bucket_size = sig_bucket_size; - h->key_tbl = h->sig_tbl + sig_tbl_size; - h->key_tbl_key_size = key_size; + h->buckets = (struct rte_hash_bucket *)((uint8_t *)h + hash_struct_size); h->hash_func = (params->hash_func == NULL) ? DEFAULT_HASH_FUNC : params->hash_func; + h->sig_msb = 1ULL << (sizeof(uint64_t) * 8 - 1); + h->sig_secondary = 1ULL << (sizeof(uint64_t) * 8 - 2); + + h->key_store = k; + h->free_slots = r; te->data = (void *) h; - TAILQ_INSERT_TAIL(hash_list, te, next); + /* populate the free slots ring. Entry zero is reserved for key misses */ + for (i = 1; i < params->entries + 1; i++) + rte_ring_sp_enqueue(r, (void *)((uintptr_t) i)); -exit: + rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); + TAILQ_INSERT_TAIL(hash_list, te, next); rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); - +exit: return h; } @@ -287,49 +296,164 @@ rte_hash_free(struct rte_hash *h) rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK); + rte_free(h->key_store); rte_free(h); rte_free(te); } static inline int32_t -__rte_hash_add_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) +run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, uint32_t key_idx, + uint64_t hash, uint64_t original_hash, const void *original_key) { - hash_sig_t *sig_bucket; - uint8_t *key_bucket; - uint32_t bucket_index, i; - int32_t pos; - - /* Get the hash signature and bucket index */ - sig |= h->sig_msb; - bucket_index = sig & h->bucket_bitmask; - sig_bucket = get_sig_tbl_bucket(h, bucket_index); - key_bucket = get_key_tbl_bucket(h, bucket_index); - - /* Check if key is already present in the hash */ - for (i = 0; i < h->bucket_entries; i++) { - if ((sig == sig_bucket[i]) && - likely(memcmp(key, get_key_from_bucket(h, key_bucket, i), - h->key_len) == 0)) { - return bucket_index * h->bucket_entries + i; + /* idx = 0 if primary, 1 if secondary */ + unsigned idx; + static unsigned number_pushes; + void *k, *keys = h->key_store; + unsigned i, j; + + uint64_t hash_stored; + uint32_t key_idx_stored; + uint32_t bucket_stored_idx; + struct rte_hash_bucket *bkt_stored; + + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + /* Check if slot is available */ + if (likely(bkt->signatures[i] == NULL_SIGNATURE)) { + bkt->signatures[i] = hash; + bkt->key_idx[i] = key_idx; + number_pushes = 0; + return bkt->key_idx[i]; + } + } + + /* + * If number of pushes has exceeded a certain limit, it + * is very likely that it has entered in a loop, need rehasing + */ + if (++number_pushes > 1 && hash == original_hash) { + k = (char *)keys + key_idx * h->key_entry_size; + if (!memcmp(k, original_key, h->key_len)) { + rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)key_idx)); + number_pushes = 0; + /* + * Indicates to the user that key could not be added, + * so he can rehash and add it again or decide not to. + */ + return -EAGAIN; } } - /* Check if any free slot within the bucket to add the new key */ - pos = find_first(NULL_SIGNATURE, sig_bucket, h->bucket_entries); + /* + * Push existing item (search for bucket with space in alternative locations) + * to its alternative location + */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + /* + * Check if item was stored in its primary/secondary location, + * to get the hash in the alternative location + */ + idx = !(bkt->signatures[i] & (h->sig_secondary)); + key_idx_stored = bkt->key_idx[i]; + k = (char *)keys + key_idx_stored * h->key_entry_size; + + if (idx == 0) + hash_stored = rte_hash_hash(h, k); + else + hash_stored = rte_hash_secondary_hash(bkt->signatures[i]); + + bucket_stored_idx = hash_stored & h->bucket_bitmask; + bkt_stored = &h->buckets[bucket_stored_idx]; + hash_stored |= h->sig_msb; + + if (idx != 0) + hash_stored |= h->sig_secondary; + + for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) { + if (bkt_stored->signatures[j] == NULL_SIGNATURE) + break; + } + + if (j != RTE_HASH_BUCKET_ENTRIES) + break; + } + + /* Push existing item (if all alternative buckets are full, pick the last one) */ + if (i == RTE_HASH_BUCKET_ENTRIES) + i -= 1; + + bkt->signatures[i] = hash; + bkt->key_idx[i] = key_idx; + + /* There is an empty slot in the alternative bucket */ + if (j != RTE_HASH_BUCKET_ENTRIES) { + bkt_stored->signatures[j] = hash_stored; + bkt_stored->key_idx[j] = key_idx_stored; + + number_pushes = 0; + return bkt_stored->key_idx[j]; + } else + return run_cuckoo(h, bkt_stored, key_idx_stored, hash_stored, + original_hash, original_key); +} + +static inline int32_t +__rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, + hash_sig_t sig) +{ + uint64_t hash0, bucket_idx0, hash1, bucket_idx1; + unsigned i; + struct rte_hash_bucket *bkt0, *bkt1; + void *k, *keys = h->key_store; + void *slot_id; + + hash0 = sig; + bucket_idx0 = hash0 & h->bucket_bitmask; + hash0 |= h->sig_msb; + + bkt0 = &h->buckets[bucket_idx0]; - if (unlikely(pos < 0)) + hash1 = rte_hash_secondary_hash(hash0); + + bucket_idx1 = hash1 & h->bucket_bitmask; + hash1 |= h->sig_msb; + /* Secondary location, add an extra 1 in the second MSB */ + hash1 |= h->sig_secondary; + + bkt1 = &h->buckets[bucket_idx1]; + + /* Check if key is already inserted in primary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt0->signatures[i] == hash0) { + k = (char *)keys + bkt0->key_idx[i] * h->key_entry_size; + if (memcmp(key, k, h->key_len) == 0) + return bkt0->key_idx[i]; + } + } + + /* Check if key is already inserted in secondary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt1->signatures[i] == hash1) { + k = (char *)keys + bkt1->key_idx[i] * h->key_entry_size; + if (memcmp(key, k, h->key_len) == 0) + return bkt1->key_idx[i]; + } + } + + k = (char *)keys + bkt0->key_idx[i] * h->key_entry_size; + if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) return -ENOSPC; - /* Add the new key to the bucket */ - sig_bucket[pos] = sig; - rte_memcpy(get_key_from_bucket(h, key_bucket, pos), key, h->key_len); - return bucket_index * h->bucket_entries + pos; + /* Copy key*/ + k = (char *)keys + (uintptr_t)slot_id * h->key_entry_size; + memcpy(k, key, h->key_len); + + /* Run cuckoo algorithm */ + return run_cuckoo(h, bkt0, (uint32_t)((uintptr_t) slot_id), hash0, hash0, key); } int32_t rte_hash_add_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) + const void *key, hash_sig_t sig) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); return __rte_hash_add_key_with_hash(h, key, sig); @@ -343,26 +467,45 @@ rte_hash_add_key(const struct rte_hash *h, const void *key) } static inline int32_t -__rte_hash_del_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) +__rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, + hash_sig_t sig) { - hash_sig_t *sig_bucket; - uint8_t *key_bucket; - uint32_t bucket_index, i; - - /* Get the hash signature and bucket index */ - sig = sig | h->sig_msb; - bucket_index = sig & h->bucket_bitmask; - sig_bucket = get_sig_tbl_bucket(h, bucket_index); - key_bucket = get_key_tbl_bucket(h, bucket_index); - - /* Check if key is already present in the hash */ - for (i = 0; i < h->bucket_entries; i++) { - if ((sig == sig_bucket[i]) && - likely(memcmp(key, get_key_from_bucket(h, key_bucket, i), - h->key_len) == 0)) { - sig_bucket[i] = NULL_SIGNATURE; - return bucket_index * h->bucket_entries + i; + uint64_t hash, bucket_idx; + unsigned i; + struct rte_hash_bucket *bkt; + void *k, *keys = h->key_store; + + hash = sig; + bucket_idx = hash & h->bucket_bitmask; + hash |= h->sig_msb; + + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in primary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt->signatures[i] == hash) { + k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; + if (memcmp(key, k, h->key_len) == 0) + return bkt->key_idx[i]; + } + } + + /* Calculate secondary hash */ + hash = rte_hash_secondary_hash(hash); + + bucket_idx = hash & h->bucket_bitmask; + hash |= h->sig_msb; + /* Secondary location, add an extra 1 in the second MSB */ + hash |= h->sig_secondary; + + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in secondary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt->signatures[i] == hash) { + k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; + if (memcmp(key, k, h->key_len) == 0) + return bkt->key_idx[i]; } } @@ -370,40 +513,66 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, } int32_t -rte_hash_del_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) +rte_hash_lookup_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_del_key_with_hash(h, key, sig); + return __rte_hash_lookup_with_hash(h, key, sig); } int32_t -rte_hash_del_key(const struct rte_hash *h, const void *key) +rte_hash_lookup(const struct rte_hash *h, const void *key) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key)); + return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key)); } static inline int32_t -__rte_hash_lookup_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig) +__rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, + hash_sig_t sig) { - hash_sig_t *sig_bucket; - uint8_t *key_bucket; - uint32_t bucket_index, i; - - /* Get the hash signature and bucket index */ - sig |= h->sig_msb; - bucket_index = sig & h->bucket_bitmask; - sig_bucket = get_sig_tbl_bucket(h, bucket_index); - key_bucket = get_key_tbl_bucket(h, bucket_index); - - /* Check if key is already present in the hash */ - for (i = 0; i < h->bucket_entries; i++) { - if ((sig == sig_bucket[i]) && - likely(memcmp(key, get_key_from_bucket(h, key_bucket, i), - h->key_len) == 0)) { - return bucket_index * h->bucket_entries + i; + uint64_t hash, bucket_idx; + unsigned i; + struct rte_hash_bucket *bkt; + void *k, *keys = h->key_store; + + hash = sig; + bucket_idx = hash & h->bucket_bitmask; + hash |= h->sig_msb; + + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in primary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt->signatures[i] == hash) { + k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; + if (memcmp(key, k, h->key_len) == 0) { + bkt->signatures[i] = NULL_SIGNATURE; + rte_ring_sp_enqueue(h->free_slots, + (void *)((uintptr_t)bkt->key_idx[i])); + return bkt->key_idx[i]; + } + } + } + + hash = rte_hash_secondary_hash(hash); + bucket_idx = hash & h->bucket_bitmask; + hash |= h->sig_msb; + /* Secondary location, add an extra 1 in the second MSB */ + hash |= h->sig_secondary; + + bkt = &h->buckets[bucket_idx]; + + /* Check if key is in secondary location */ + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + if (bkt->signatures[i] == hash) { + k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; + if (memcmp(key, k, h->key_len) == 0) { + bkt->signatures[i] = NULL_SIGNATURE; + rte_ring_sp_enqueue(h->free_slots, + (void *)((uintptr_t)bkt->key_idx[i])); + return bkt->key_idx[i]; + } } } @@ -411,61 +580,313 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, } int32_t -rte_hash_lookup_with_hash(const struct rte_hash *h, +rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_lookup_with_hash(h, key, sig); + return __rte_hash_del_key_with_hash(h, key, sig); } int32_t -rte_hash_lookup(const struct rte_hash *h, const void *key) +rte_hash_del_key(const struct rte_hash *h, const void *key) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key)); + return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key)); } -int -rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, - uint32_t num_keys, int32_t *positions) +/* Lookup bulk stage 0: Calculate next primary/secondary hash value (from new key) */ +static inline void +lookup_stage0(unsigned *idx, uint64_t *lookup_mask, + uint64_t *primary_hash, uint64_t *secondary_hash, + const void * const *keys, const struct rte_hash *h) { - uint32_t i, j, bucket_index; - hash_sig_t sigs[RTE_HASH_LOOKUP_BULK_MAX]; + *idx = __builtin_ctzl(*lookup_mask); + if (*lookup_mask == 0) + *idx = 0; - RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || - (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || - (positions == NULL)), -EINVAL); + *primary_hash = rte_hash_hash(h, keys[*idx]); + *secondary_hash = rte_hash_secondary_hash(*primary_hash); - /* Get the hash signature and bucket index */ - for (i = 0; i < num_keys; i++) { - sigs[i] = h->hash_func(keys[i], h->key_len, - h->hash_func_init_val) | h->sig_msb; - bucket_index = sigs[i] & h->bucket_bitmask; + *primary_hash |= h->sig_msb; + + *secondary_hash |= h->sig_msb; + *secondary_hash |= h->sig_secondary; + + *lookup_mask &= ~(1llu << *idx); +} + + +/* Lookup bulk stage 1: Prefetch primary/secondary buckets */ +static inline void +lookup_stage1(uint64_t primary_hash, uint64_t secondary_hash, + const struct rte_hash_bucket **primary_bkt, + const struct rte_hash_bucket **secondary_bkt, + const struct rte_hash *h) +{ + *primary_bkt = &h->buckets[primary_hash & h->bucket_bitmask]; + *secondary_bkt = &h->buckets[secondary_hash & h->bucket_bitmask]; + + rte_prefetch0(*primary_bkt); + rte_prefetch0(*secondary_bkt); +} - /* Pre-fetch relevant buckets */ - rte_prefetch1((void *) get_sig_tbl_bucket(h, bucket_index)); - rte_prefetch1((void *) get_key_tbl_bucket(h, bucket_index)); +/* + * Lookup bulk stage 2: Search for match hashes in primary/secondary locations + * and prefetch first key slot + */ +static inline void +lookup_stage2(unsigned idx, uint64_t primary_hash, uint64_t secondary_hash, + const struct rte_hash_bucket *primary_bkt, + const struct rte_hash_bucket *secondary_bkt, + const void **key_slot, + int32_t *positions, + uint64_t *extra_hits_mask, + const void *keys, const struct rte_hash *h) +{ + unsigned primary_hash_matches, secondary_hash_matches, key_idx, i; + unsigned total_hash_matches; + + total_hash_matches = 1 << (RTE_HASH_BUCKET_ENTRIES * 2); + primary_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES; + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + primary_hash_matches |= ((primary_hash == primary_bkt->signatures[i]) << i); + total_hash_matches |= ((primary_hash == primary_bkt->signatures[i]) << i); } - /* Check if key is already present in the hash */ - for (i = 0; i < num_keys; i++) { - bucket_index = sigs[i] & h->bucket_bitmask; - hash_sig_t *sig_bucket = get_sig_tbl_bucket(h, bucket_index); - uint8_t *key_bucket = get_key_tbl_bucket(h, bucket_index); - - positions[i] = -ENOENT; - - for (j = 0; j < h->bucket_entries; j++) { - if ((sigs[i] == sig_bucket[j]) && - likely(memcmp(keys[i], - get_key_from_bucket(h, key_bucket, j), - h->key_len) == 0)) { - positions[i] = bucket_index * - h->bucket_entries + j; - break; - } - } + key_idx = primary_bkt->key_idx[__builtin_ctzl(primary_hash_matches)]; + + secondary_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES; + for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { + secondary_hash_matches |= ((secondary_hash == secondary_bkt->signatures[i]) << i); + total_hash_matches |= ((secondary_hash == secondary_bkt->signatures[i]) + << (i + RTE_HASH_BUCKET_ENTRIES)); + } + + if (key_idx == 0) + key_idx = secondary_bkt->key_idx[__builtin_ctzl(secondary_hash_matches)]; + + *key_slot = (const char *)keys + key_idx * h->key_entry_size; + + rte_prefetch0(*key_slot); + positions[idx] = key_idx; + + *extra_hits_mask |= (uint64_t)(__builtin_popcount(primary_hash_matches) > 2) << idx; + *extra_hits_mask |= (uint64_t)(__builtin_popcount(secondary_hash_matches) > 2) << idx; + *extra_hits_mask |= (uint64_t)(__builtin_popcount(total_hash_matches) > 2) << idx; + +} + + +/* Lookup bulk stage 3: Check if key matches, update hit mask */ +static inline void +lookup_stage3(unsigned idx, const void *key_slot, + const void * const *keys, int32_t *positions, + uint64_t *hits, const struct rte_hash *h) +{ + unsigned hit; + + hit = !memcmp(key_slot, keys[idx], h->key_len); + if (unlikely(hit == 0)) + positions[idx] = -ENOENT; + *hits = (uint64_t)(hit) << idx; +} + +static inline int +__rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, + uint32_t num_keys, int32_t *positions) { + + uint64_t hits = 0; + uint64_t next_mask = 0; + uint64_t extra_hits_mask = 0; + uint64_t lookup_mask; + unsigned idx; + const void *key_store = h->key_store; + + unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31; + const struct rte_hash_bucket *primary_bkt10, *primary_bkt11; + const struct rte_hash_bucket *secondary_bkt10, *secondary_bkt11; + const struct rte_hash_bucket *primary_bkt20, *primary_bkt21; + const struct rte_hash_bucket *secondary_bkt20, *secondary_bkt21; + const void *k_slot20, *k_slot21, *k_slot30, *k_slot31; + uint64_t primary_hash00, primary_hash01; + uint64_t secondary_hash00, secondary_hash01; + uint64_t primary_hash10, primary_hash11; + uint64_t secondary_hash10, secondary_hash11; + uint64_t primary_hash20, primary_hash21; + uint64_t secondary_hash20, secondary_hash21; + + if (num_keys == RTE_HASH_LOOKUP_BULK_MAX) + lookup_mask = 0xffffffffffffffff; + else + lookup_mask = (1 << num_keys) - 1; + + lookup_stage0(&idx00, &lookup_mask, &primary_hash00, + &secondary_hash00, keys, h); + lookup_stage0(&idx01, &lookup_mask, &primary_hash01, + &secondary_hash01, keys, h); + + primary_hash10 = primary_hash00; + primary_hash11 = primary_hash01; + secondary_hash10 = secondary_hash00; + secondary_hash11 = secondary_hash01; + idx10 = idx00, idx11 = idx01; + + lookup_stage0(&idx00, &lookup_mask, &primary_hash00, + &secondary_hash00, keys, h); + lookup_stage0(&idx01, &lookup_mask, &primary_hash01, + &secondary_hash01, keys, h); + lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, + &secondary_bkt10, h); + lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11, + &secondary_bkt11, h); + + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + primary_hash10 = primary_hash00; + primary_hash11 = primary_hash01; + secondary_hash10 = secondary_hash00; + secondary_hash11 = secondary_hash01; + idx10 = idx00, idx11 = idx01; + + lookup_stage0(&idx00, &lookup_mask, &primary_hash00, + &secondary_hash00, keys, h); + lookup_stage0(&idx01, &lookup_mask, &primary_hash01, + &secondary_hash01, keys, h); + lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, + &secondary_bkt10, h); + lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11, + &secondary_bkt11, h); + lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20, + secondary_bkt20, &k_slot20, positions, &extra_hits_mask, + key_store, h); + lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21, + secondary_bkt21, &k_slot21, positions, &extra_hits_mask, + key_store, h); + + while (lookup_mask) { + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + primary_hash10 = primary_hash00; + primary_hash11 = primary_hash01; + secondary_hash10 = secondary_hash00; + secondary_hash11 = secondary_hash01; + idx10 = idx00, idx11 = idx01; + + lookup_stage0(&idx00, &lookup_mask, &primary_hash00, + &secondary_hash00, keys, h); + lookup_stage0(&idx01, &lookup_mask, &primary_hash01, + &secondary_hash01, keys, h); + lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, + &secondary_bkt10, h); + lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11, + &secondary_bkt11, h); + lookup_stage2(idx20, primary_hash20, secondary_hash20, + primary_bkt20, secondary_bkt20, &k_slot20, positions, + &extra_hits_mask, key_store, h); + lookup_stage2(idx21, primary_hash21, secondary_hash21, + primary_bkt21, secondary_bkt21, &k_slot21, positions, + &extra_hits_mask, key_store, h); + lookup_stage3(idx30, k_slot30, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, &hits, h); + } + + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + primary_hash10 = primary_hash00; + primary_hash11 = primary_hash01; + secondary_hash10 = secondary_hash00; + secondary_hash11 = secondary_hash01; + idx10 = idx00, idx11 = idx01; + lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, + &secondary_bkt10, h); + lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11, + &secondary_bkt11, h); + lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20, + secondary_bkt20, &k_slot20, positions, &extra_hits_mask, + key_store, h); + lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21, + secondary_bkt21, &k_slot21, positions, &extra_hits_mask, + key_store, h); + lookup_stage3(idx30, k_slot30, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, &hits, h); + + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + primary_bkt20 = primary_bkt10; + primary_bkt21 = primary_bkt11; + secondary_bkt20 = secondary_bkt10; + secondary_bkt21 = secondary_bkt11; + primary_hash20 = primary_hash10; + primary_hash21 = primary_hash11; + secondary_hash20 = secondary_hash10; + secondary_hash21 = secondary_hash11; + idx20 = idx10, idx21 = idx11; + + lookup_stage2(idx20, primary_hash20, secondary_hash20, primary_bkt20, + secondary_bkt20, &k_slot20, positions, &extra_hits_mask, + key_store, h); + lookup_stage2(idx21, primary_hash21, secondary_hash21, primary_bkt21, + secondary_bkt21, &k_slot21, positions, &extra_hits_mask, + key_store, h); + lookup_stage3(idx30, k_slot30, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, &hits, h); + + k_slot30 = k_slot20, k_slot31 = k_slot21; + idx30 = idx20, idx31 = idx21; + + lookup_stage3(idx30, k_slot30, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, positions, &hits, h); + + /* handle extra_hits_mask */ + next_mask |= extra_hits_mask; + + /* ignore any items we have already found */ + next_mask &= ~hits; + + if (unlikely(next_mask)) { + /* run a single search for each remaining item */ + do { + idx = __builtin_ctzl(next_mask); + positions[idx] = rte_hash_lookup(h, keys[idx]); + next_mask &= ~(1llu << idx); + } while (next_mask); } return 0; } + +int +rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, + uint32_t num_keys, int32_t *positions) +{ + RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || + (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || + (positions == NULL)), -EINVAL); + + return __rte_hash_lookup_bulk(h, keys, num_keys, positions); +} diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index 821a9d4..4088ac4 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -1,7 +1,7 @@ /*- * BSD LICENSE * - * Copyright(c) 2010-2014 Intel Corporation. All rights reserved. + * Copyright(c) 2010-2015 Intel Corporation. All rights reserved. * All rights reserved. * * Redistribution and use in source and binary forms, with or without @@ -42,27 +42,36 @@ #include #include +#include #ifdef __cplusplus extern "C" { #endif /** Maximum size of hash table that can be created. */ -#define RTE_HASH_ENTRIES_MAX (1 << 26) +#define RTE_HASH_ENTRIES_MAX (1 << 30) -/** Maximum bucket size that can be created. */ -#define RTE_HASH_BUCKET_ENTRIES_MAX 16 +/** Number of items per bucket. */ +#define RTE_HASH_BUCKET_ENTRIES 4 /** Maximum length of key that can be used. */ #define RTE_HASH_KEY_LENGTH_MAX 64 -/** Max number of keys that can be searched for using rte_hash_lookup_multi. */ -#define RTE_HASH_LOOKUP_BULK_MAX 16 -#define RTE_HASH_LOOKUP_MULTI_MAX RTE_HASH_LOOKUP_BULK_MAX - -/** Max number of characters in hash name.*/ +/** Maximum number of characters in hash name.*/ #define RTE_HASH_NAMESIZE 32 +/** Bits that will be right shifted when calculating a secondary hash. */ +#define RTE_HASH_ALT_BITS_SHIFT 12 + +/** Bits that will be XORed to obtained a secondary hash. */ +#define RTE_HASH_ALT_BITS_XOR_MASK 0x5bd1e995 + +/** Maximum number of keys that can be searched for using rte_hash_lookup_bulk. */ +#define RTE_HASH_LOOKUP_BULK_MAX 64 + +/* Stored key size is a multiple of this value */ +#define KEY_ALIGNMENT 16 + /** Signature of key that is stored internally. */ typedef uint32_t hash_sig_t; @@ -77,9 +86,9 @@ typedef uint32_t (*rte_hash_function)(const void *key, uint32_t key_len, struct rte_hash_parameters { const char *name; /**< Name of the hash. */ uint32_t entries; /**< Total hash table entries. */ - uint32_t bucket_entries; /**< Bucket entries. */ - uint32_t key_len; /**< Length of hash key. */ - rte_hash_function hash_func; /**< Function used to calculate hash. */ + uint32_t bucket_entries; /**< Bucket entries. */ + uint16_t key_len; /**< Length of hash key. */ + rte_hash_function hash_func; /**< Primary Hash function used to calculate hash. */ uint32_t hash_func_init_val; /**< Init value used by hash_func. */ int socket_id; /**< NUMA Socket ID for memory. */ }; @@ -88,24 +97,35 @@ struct rte_hash_parameters { struct rte_hash { char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */ uint32_t entries; /**< Total table entries. */ - uint32_t bucket_entries; /**< Bucket entries. */ - uint32_t key_len; /**< Length of hash key. */ + uint32_t bucket_entries; /**< Bucket entries. */ + uint16_t key_len; /**< Length of hash key. */ rte_hash_function hash_func; /**< Function used to calculate hash. */ uint32_t hash_func_init_val; /**< Init value used by hash_func. */ uint32_t num_buckets; /**< Number of buckets in table. */ uint32_t bucket_bitmask; /**< Bitmask for getting bucket index from hash signature. */ - hash_sig_t sig_msb; /**< MSB is always set in valid signatures. */ - uint8_t *sig_tbl; /**< Flat array of hash signature buckets. */ - uint32_t sig_tbl_bucket_size; /**< Signature buckets may be padded for - alignment reasons, and this is the - bucket size used by sig_tbl. */ - uint8_t *key_tbl; /**< Flat array of key value buckets. */ - uint32_t key_tbl_key_size; /**< Keys may be padded for alignment - reasons, and this is the key size - used by key_tbl. */ + uint16_t key_entry_size; /**< Size of each key entry. */ + int socket_id; /**< NUMA Socket ID for memory. */ + uint64_t sig_msb; /**< MSB is always set in valid signatures. */ + uint64_t sig_secondary; /**< Second MSB is set when hash is calculated + from secondary hash function. */ + + struct rte_ring *free_slots; /**< Ring that stores all indexes + of the free slots in the key table */ + void *key_store; /**< Table storing all keys and data */ + + struct rte_hash_bucket *buckets; /**< Table with buckets storing all the + hash values and key indexes + to the key table*/ }; +/** Bucket structure */ +struct rte_hash_bucket { + uint64_t signatures[RTE_HASH_BUCKET_ENTRIES]; + uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES]; +} __rte_cache_aligned; + + /** * Create a new hash table. * @@ -126,7 +146,6 @@ struct rte_hash { struct rte_hash * rte_hash_create(const struct rte_hash_parameters *params); - /** * Find an existing hash table object and return a pointer to it. * @@ -158,9 +177,9 @@ rte_hash_free(struct rte_hash *h); * Key to add to the hash table. * @return * - -EINVAL if the parameters are invalid. + * - -EAGAIN if key could not be added (table needs rehash) * - -ENOSPC if there is no space in the hash for this key. - * - A positive value that can be used by the caller as an offset into an - * array of user data. This value is unique for this key. + * - 0 if key was added successfully */ int32_t rte_hash_add_key(const struct rte_hash *h, const void *key); @@ -177,13 +196,12 @@ rte_hash_add_key(const struct rte_hash *h, const void *key); * Hash value to add to the hash table. * @return * - -EINVAL if the parameters are invalid. + * - -EAGAIN if key could not be added (table needs rehash) * - -ENOSPC if there is no space in the hash for this key. - * - A positive value that can be used by the caller as an offset into an - * array of user data. This value is unique for this key. + * - 0 if key was added successfully */ int32_t -rte_hash_add_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig); +rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); /** * Remove a key from an existing hash table. This operation is not multi-thread @@ -196,9 +214,7 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, * @return * - -EINVAL if the parameters are invalid. * - -ENOENT if the key is not found. - * - A positive value that can be used by the caller as an offset into an - * array of user data. This value is unique for this key, and is the same - * value that was returned when the key was added. + * - 0 if key was deleted successfully */ int32_t rte_hash_del_key(const struct rte_hash *h, const void *key); @@ -216,14 +232,10 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); * @return * - -EINVAL if the parameters are invalid. * - -ENOENT if the key is not found. - * - A positive value that can be used by the caller as an offset into an - * array of user data. This value is unique for this key, and is the same - * value that was returned when the key was added. + * - 0 if key was deleted successfully */ int32_t -rte_hash_del_key_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig); - +rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); /** * Find a key in the hash table. This operation is multi-thread safe. @@ -235,9 +247,7 @@ rte_hash_del_key_with_hash(const struct rte_hash *h, * @return * - -EINVAL if the parameters are invalid. * - -ENOENT if the key is not found. - * - A positive value that can be used by the caller as an offset into an - * array of user data. This value is unique for this key, and is the same - * value that was returned when the key was added. + * - 0 if key was found successfully */ int32_t rte_hash_lookup(const struct rte_hash *h, const void *key); @@ -254,14 +264,40 @@ rte_hash_lookup(const struct rte_hash *h, const void *key); * @return * - -EINVAL if the parameters are invalid. * - -ENOENT if the key is not found. - * - A positive value that can be used by the caller as an offset into an - * array of user data. This value is unique for this key, and is the same - * value that was returned when the key was added. + * - 0 if key was found successfully */ int32_t -rte_hash_lookup_with_hash(const struct rte_hash *h, - const void *key, hash_sig_t sig); +rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig); +#define rte_hash_lookup_multi rte_hash_lookup_bulk +/** + * Find multiple keys in the hash table. This operation is multi-thread safe. + * + * @param h + * Hash table to look in. + * @param keys + * A pointer to a list of keys to look for. + * @param num_keys + * How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX). + * @param positions + * Output containing a list of values, corresponding to the list of keys that + * can be used by the caller as an offset into an array of user data. These + * values are unique for each key, and are the same values that were returned + * when each key was added. If a key in the list was not found, then -ENOENT + * will be the value. + * @return + * -EINVAL if there's an error, otherwise number of hits. + */ +int +rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, + uint32_t num_keys, int32_t *positions); + +static inline hash_sig_t +hash_alt(const uint32_t primary_hash) { + uint32_t tag = primary_hash >> RTE_HASH_ALT_BITS_SHIFT; + + return (primary_hash ^ ((tag + 1) * RTE_HASH_ALT_BITS_XOR_MASK)); +} /** * Calc a hash value by key. This operation is not multi-process safe. @@ -280,28 +316,23 @@ rte_hash_hash(const struct rte_hash *h, const void *key) return h->hash_func(key, h->key_len, h->hash_func_init_val); } -#define rte_hash_lookup_multi rte_hash_lookup_bulk /** - * Find multiple keys in the hash table. This operation is multi-thread safe. + * Calc the secondary hash value by key. This operation is not multi-process safe. * * @param h * Hash table to look in. - * @param keys - * A pointer to a list of keys to look for. - * @param num_keys - * How many keys are in the keys list (less than RTE_HASH_LOOKUP_BULK_MAX). - * @param positions - * Output containing a list of values, corresponding to the list of keys that - * can be used by the caller as an offset into an array of user data. These - * values are unique for each key, and are the same values that were returned - * when each key was added. If a key in the list was not found, then -ENOENT - * will be the value. + * @param key + * Key to find. * @return - * -EINVAL if there's an error, otherwise 0. + * - hash value */ -int -rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, - uint32_t num_keys, int32_t *positions); +static inline hash_sig_t +rte_hash_secondary_hash(const uint32_t primary_hash) +{ + /* calc hash result by key */ + return hash_alt(primary_hash); +} + #ifdef __cplusplus } #endif -- 2.4.2