From mboxrd@z Thu Jan 1 00:00:00 1970 From: Pablo de Lara Subject: [PATCH 5/6] hash: add new functionality to store data in hash table Date: Fri, 5 Jun 2015 15:33:23 +0100 Message-ID: <1433514804-7075-6-git-send-email-pablo.de.lara.guarch@intel.com> References: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> To: dev@dpdk.org Return-path: Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id E58215A54 for ; Fri, 5 Jun 2015 16:33:28 +0200 (CEST) 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 t55EXOcL003763 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 t55EXOHY007145 for ; Fri, 5 Jun 2015 15:33:24 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t55EXOYk007140 for dev@dpdk.org; Fri, 5 Jun 2015 15:33:24 +0100 In-Reply-To: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Usually hash tables not only store keys, but also data associated to them. In order to maintain the existing API, the key index will still be returned when looking up/deleting an entry, but user will be able to store/look up data associated to a key. Signed-off-by: Pablo de Lara --- lib/librte_hash/rte_hash.c | 284 ++++++++++++++++++++++++----------- lib/librte_hash/rte_hash.h | 180 ++++++++++++++++++++++ lib/librte_hash/rte_hash_version.map | 8 + 3 files changed, 385 insertions(+), 87 deletions(-) diff --git a/lib/librte_hash/rte_hash.c b/lib/librte_hash/rte_hash.c index 0b7f543..c1be7b0 100644 --- a/lib/librte_hash/rte_hash.c +++ b/lib/librte_hash/rte_hash.c @@ -177,7 +177,7 @@ rte_hash_create(const struct rte_hash_parameters *params) /* Total memory required for hash context */ mem_size = hash_struct_size + tbl_size; - key_entry_size = params->key_len; + key_entry_size = sizeof(struct rte_hash_key) + params->key_len; rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK); @@ -335,7 +335,7 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, uint32_t key_i /* idx = 0 if primary, 1 if secondary */ unsigned idx; static unsigned number_pushes; - void *k, *keys = h->key_store; + struct rte_hash_key *k, *keys = h->key_store; unsigned i, j; uint64_t hash_stored; @@ -358,8 +358,8 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, uint32_t key_i * 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)) { + k = (struct rte_hash_key *) ((char *)keys + key_idx * h->key_entry_size); + if (!memcmp(k->key, original_key, h->key_len)) { rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)key_idx)); number_pushes = 0; /* @@ -381,10 +381,11 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, uint32_t key_i */ idx = !(bkt->signatures[i] & (h->sig_secondary)); key_idx_stored = bkt->key_idx[i]; - k = (char *)keys + key_idx_stored * h->key_entry_size; + k = (struct rte_hash_key *) ((char *)keys + + key_idx_stored * h->key_entry_size); if (idx == 0) - hash_stored = rte_hash_hash(h, k); + hash_stored = rte_hash_hash(h, k->key); else hash_stored = rte_hash_secondary_hash(bkt->signatures[i]); @@ -430,7 +431,7 @@ rte_hash_rehash(struct rte_hash *h, rte_hash_function hash_func, uint32_t tbl_size, mem_size, bucket_size, hash_struct_size; uint64_t hash; struct rte_hash_bucket *bkt; - void *k; + struct rte_hash_key *k; struct rte_hash *sec_h; uint32_t bucket_idx; int32_t ret; @@ -458,16 +459,16 @@ rte_hash_rehash(struct rte_hash *h, rte_hash_function hash_func, for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) { /* Check if entry in bucket is not empty */ if (h->buckets[i].signatures[j] != NULL_SIGNATURE) { - k = (char *)h->key_store + - h->buckets[i].key_idx[j] * h->key_entry_size; + k = (struct rte_hash_key *) ((char *)h->key_store + + h->buckets[i].key_idx[j] * h->key_entry_size); /* Get new hash (with new initial value) */ - hash = rte_hash_hash(sec_h, k); + hash = rte_hash_hash(sec_h, k->key); bucket_idx = hash & sec_h->bucket_bitmask; hash |= sec_h->sig_msb; bkt = &sec_h->buckets[bucket_idx]; /* Add entry on secondary hash table */ ret = run_cuckoo(sec_h, bkt, h->buckets[i].key_idx[j], - hash, hash, k); + hash, hash, k->key); if (ret == -EAGAIN) goto exit; num_entries++; @@ -489,12 +490,12 @@ exit: static inline int32_t __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, - hash_sig_t sig) + hash_sig_t sig, uintptr_t data) { uint64_t hash0, bucket_idx0, hash1, bucket_idx1; unsigned i; struct rte_hash_bucket *bkt0, *bkt1; - void *k, *keys = h->key_store; + struct rte_hash_key *k, *keys = h->key_store; void *slot_id; hash0 = sig; @@ -515,28 +516,39 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, /* 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) + k = (struct rte_hash_key *) ((char *)keys + + bkt0->key_idx[i] * h->key_entry_size); + if (memcmp(key, k->key, h->key_len) == 0) { + /* Update data */ + k->idata = data; 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) + k = (struct rte_hash_key *) ((char *)keys + + bkt1->key_idx[i] * h->key_entry_size); + if (memcmp(key, k->key, h->key_len) == 0) { + /* Update data */ + k->idata = data; return bkt1->key_idx[i]; + } } } - k = (char *)keys + bkt0->key_idx[i] * h->key_entry_size; + k = (struct rte_hash_key *) ((char *)keys + + bkt0->key_idx[i] * h->key_entry_size); if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) return -ENOSPC; - /* Copy key*/ - k = (char *)keys + (uintptr_t)slot_id * h->key_entry_size; - memcpy(k, key, h->key_len); + /* Copy key and data */ + k = (struct rte_hash_key *)((char *)keys + + (uintptr_t)slot_id * h->key_entry_size); + memcpy(k->key, key, h->key_len); + k->idata = data; /* Run cuckoo algorithm */ return run_cuckoo(h, bkt0, (uint32_t)((uintptr_t) slot_id), hash0, hash0, key); @@ -547,24 +559,39 @@ rte_hash_add_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_add_key_with_hash(h, key, sig); + return __rte_hash_add_key_with_hash(h, key, sig, 0); } int32_t rte_hash_add_key(const struct rte_hash *h, const void *key) { RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key)); + return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), 0); +} + +int32_t +rte_hash_add_key_with_hash_data(const struct rte_hash *h, + const void *key, hash_sig_t sig, uintptr_t data) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_add_key_with_hash(h, key, sig, data); +} + +int32_t +rte_hash_add_key_data(const struct rte_hash *h, const void *key, uintptr_t data) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data); } static inline int32_t __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, - hash_sig_t sig) + hash_sig_t sig, uintptr_t *data) { uint64_t hash, bucket_idx; unsigned i; struct rte_hash_bucket *bkt; - void *k, *keys = h->key_store; + struct rte_hash_key *k, *keys = h->key_store; hash = sig; bucket_idx = hash & h->bucket_bitmask; @@ -575,9 +602,13 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, /* 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) + k = (struct rte_hash_key *) ((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (memcmp(key, k->key, h->key_len) == 0) { + if (data != NULL) + *data = k->idata; return bkt->key_idx[i]; + } } } @@ -594,9 +625,13 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, /* 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) + k = (struct rte_hash_key *) ((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (memcmp(key, k->key, h->key_len) == 0) { + if (data != NULL) + *data = k->idata; return bkt->key_idx[i]; + } } } @@ -604,28 +639,43 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, } int32_t +rte_hash_lookup_with_hash_data(const struct rte_hash *h, + const void *key, hash_sig_t sig, uintptr_t *data) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_lookup_with_hash(h, key, sig, data); +} + +int32_t +rte_hash_lookup_data(const struct rte_hash *h, const void *key, uintptr_t *data) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_lookup_with_hash(h, key, rte_hash_hash(h, key), data); +} + +int32_t 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_lookup_with_hash(h, key, sig); + return __rte_hash_lookup_with_hash(h, key, sig, NULL); } int32_t rte_hash_lookup(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_lookup_with_hash(h, key, rte_hash_hash(h, key), NULL); } static inline int32_t __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, - hash_sig_t sig) + hash_sig_t sig, uintptr_t *data) { uint64_t hash, bucket_idx; unsigned i; struct rte_hash_bucket *bkt; - void *k, *keys = h->key_store; + struct rte_hash_key *k, *keys = h->key_store; hash = sig; bucket_idx = hash & h->bucket_bitmask; @@ -636,8 +686,11 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* 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) { + k = (struct rte_hash_key *) ((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (memcmp(key, k->key, h->key_len) == 0) { + if (data != NULL) + data[i] = k->idata; bkt->signatures[i] = NULL_SIGNATURE; rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)bkt->key_idx[i])); @@ -657,8 +710,11 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* 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) { + k = (struct rte_hash_key *) ((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (memcmp(key, k->key, h->key_len) == 0) { + if (data != NULL) + data[i] = k->idata; bkt->signatures[i] = NULL_SIGNATURE; rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)bkt->key_idx[i])); @@ -671,18 +727,33 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, } int32_t +rte_hash_del_key_with_hash_data(const struct rte_hash *h, + const void *key, hash_sig_t sig, uintptr_t *data) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_del_key_with_hash(h, key, sig, data); +} + +int32_t +rte_hash_del_key_data(const struct rte_hash *h, const void *key, uintptr_t *data) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key), data); +} + +int32_t 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_del_key_with_hash(h, key, sig); + return __rte_hash_del_key_with_hash(h, key, sig, NULL); } int32_t rte_hash_del_key(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_del_key_with_hash(h, key, rte_hash_hash(h, key), NULL); } /* Lookup bulk stage 0: Calculate next primary/secondary hash value (from new key) */ @@ -748,10 +819,10 @@ 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, + const struct rte_hash_key **key_slot, int32_t *positions, uint64_t *extra_hits_mask, - const void *keys, const struct rte_hash *h) + const struct rte_hash_key *keys, const struct rte_hash *h) { unsigned primary_hash_matches, secondary_hash_matches, key_idx, i; unsigned total_hash_matches; @@ -775,7 +846,8 @@ lookup_stage2(unsigned idx, uint64_t primary_hash, uint64_t secondary_hash, 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; + *key_slot = (const struct rte_hash_key *)((const char *)keys + + key_idx * h->key_entry_size); rte_prefetch0(*key_slot); positions[idx] = key_idx; @@ -787,15 +859,20 @@ lookup_stage2(unsigned idx, uint64_t primary_hash, uint64_t secondary_hash, } -/* Lookup bulk stage 3: Check if key matches, update hit mask */ +/* + * Lookup bulk stage 3: Check if key matches, update hit mask + * and store data in values[] + */ 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) +lookup_stage3(unsigned idx, const struct rte_hash_key *key_slot, + uintptr_t values[], 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 (values != NULL) + values[idx] = key_slot->idata; + hit = !memcmp(key_slot->key, keys[idx], h->key_len); if (unlikely(hit == 0)) positions[idx] = -ENOENT; *hits = (uint64_t)(hit) << idx; @@ -803,21 +880,21 @@ lookup_stage3(unsigned idx, const void *key_slot, static inline int __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, - uint32_t num_keys, int32_t *positions) { + uint32_t num_keys, int32_t *positions, uintptr_t data[]) { 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; + const struct rte_hash_key *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; + const struct rte_hash_key *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; @@ -830,6 +907,7 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, 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, @@ -912,8 +990,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, 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); + lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h); } k_slot30 = k_slot20, k_slot31 = k_slot21; @@ -942,8 +1020,8 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, 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); + lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h); k_slot30 = k_slot20, k_slot31 = k_slot21; idx30 = idx20, idx31 = idx21; @@ -963,14 +1041,14 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, 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); + lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, data, 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); + lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h); /* handle extra_hits_mask */ next_mask |= extra_hits_mask; @@ -982,7 +1060,11 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, /* run a single search for each remaining item */ do { idx = __builtin_ctzl(next_mask); - positions[idx] = rte_hash_lookup(h, keys[idx]); + if (data != NULL) + positions[idx] = rte_hash_lookup_data(h, keys[idx], + &data[idx]); + else + positions[idx] = rte_hash_lookup(h, keys[idx]); next_mask &= ~(1llu << idx); } while (next_mask); } @@ -993,21 +1075,21 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, static inline int __rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, const hash_sig_t *hash_vals, uint32_t num_keys, - int32_t *positions) + int32_t *positions, uintptr_t data[]) { 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; + const struct rte_hash_key *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; + const struct rte_hash_key *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; @@ -1020,10 +1102,10 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, else lookup_mask = (1 << num_keys) - 1; - lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00, - &secondary_hash00, hash_vals, h); - lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01, - &secondary_hash01, hash_vals, h); + lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00, &secondary_hash00, + hash_vals, h); + lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01, &secondary_hash01, + hash_vals, h); primary_hash10 = primary_hash00; primary_hash11 = primary_hash01; @@ -1031,10 +1113,10 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, secondary_hash11 = secondary_hash01; idx10 = idx00, idx11 = idx01; - lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00, - &secondary_hash00, hash_vals, h); - lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01, - &secondary_hash01, hash_vals, h); + lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00, &secondary_hash00, + hash_vals, h); + lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01, &secondary_hash01, + hash_vals, h); lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, &secondary_bkt10, h); lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11, @@ -1055,10 +1137,10 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, secondary_hash11 = secondary_hash01; idx10 = idx00, idx11 = idx01; - lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00, - &secondary_hash00, hash_vals, h); - lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01, - &secondary_hash01, hash_vals, h); + lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00, &secondary_hash00, + hash_vals, h); + lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01, &secondary_hash01, + hash_vals, h); lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, &secondary_bkt10, h); lookup_stage1(primary_hash11, secondary_hash11, &primary_bkt11, @@ -1089,9 +1171,9 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, idx10 = idx00, idx11 = idx01; lookup_stage0_with_hash(&idx00, &lookup_mask, &primary_hash00, - &secondary_hash00, hash_vals, h); + &secondary_hash00, hash_vals, h); lookup_stage0_with_hash(&idx01, &lookup_mask, &primary_hash01, - &secondary_hash01, hash_vals, h); + &secondary_hash01, hash_vals, h); lookup_stage1(primary_hash10, secondary_hash10, &primary_bkt10, &secondary_bkt10, h); lookup_stage1(primary_hash11, secondary_hash11, @@ -1102,8 +1184,8 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, 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); + lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h); } k_slot30 = k_slot20, k_slot31 = k_slot21; @@ -1133,8 +1215,8 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, 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); + lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h); k_slot30 = k_slot20, k_slot31 = k_slot21; idx30 = idx20, idx31 = idx21; @@ -1154,14 +1236,14 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, 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); + lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, data, 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); + lookup_stage3(idx30, k_slot30, data, keys, positions, &hits, h); + lookup_stage3(idx31, k_slot31, data, keys, positions, &hits, h); /* handle extra_hits_mask */ next_mask |= extra_hits_mask; @@ -1173,7 +1255,11 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, /* run a single search for each remaining item */ do { idx = __builtin_ctzl(next_mask); - positions[idx] = rte_hash_lookup_with_hash(h, keys[idx], + if (data != NULL) + positions[idx] = rte_hash_lookup_with_hash_data(h, keys[idx], + hash_vals[idx], &data[idx]); + else + positions[idx] = rte_hash_lookup_with_hash(h, keys[idx], hash_vals[idx]); next_mask &= ~(1llu << idx); } while (next_mask); @@ -1183,6 +1269,17 @@ __rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, } int +rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys, + uint32_t num_keys, int32_t *positions, uintptr_t data[]) +{ + 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, data); +} + +int rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, uint32_t num_keys, int32_t *positions) { @@ -1190,7 +1287,20 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || (positions == NULL)), -EINVAL); - return __rte_hash_lookup_bulk(h, keys, num_keys, positions); + return __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL); +} + +int +rte_hash_lookup_bulk_with_hash_data(const struct rte_hash *h, const void **keys, + const hash_sig_t *hash_vals, uint32_t num_keys, + int32_t *positions, uintptr_t data[]) +{ + 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_with_hash(h, keys, hash_vals, num_keys, + positions, data); } int @@ -1203,5 +1313,5 @@ rte_hash_lookup_bulk_with_hash(const struct rte_hash *h, const void **keys, (positions == NULL)), -EINVAL); return __rte_hash_lookup_bulk_with_hash(h, keys, hash_vals, num_keys, - positions); + positions, NULL); } diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index c92d935..d832b09 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -119,6 +119,15 @@ struct rte_hash { to the key table*/ }; +struct rte_hash_key { + union { + uintptr_t idata; + void *pdata; + }; + /* Variable key size */ + char key[] __attribute__((aligned(KEY_ALIGNMENT))); +}; + /** Bucket structure */ struct rte_hash_bucket { uint64_t signatures[RTE_HASH_BUCKET_ENTRIES]; @@ -194,6 +203,47 @@ void rte_hash_reset(struct rte_hash *h); /** + * Add a pair key/data to an existing hash table. This operation is not multi-thread safe + * and should only be called from one thread. + * + * @param h + * Hash table to add the key to. + * @param key + * Key to add to the hash table. + * @param data + * Data 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. + * - 0 if key was added successfully + */ +int32_t +rte_hash_add_key_data(const struct rte_hash *h, const void *key, uintptr_t data); + +/** + * Add a pair key/data to an existing hash table. This operation is not multi-thread safe + * and should only be called from one thread. + * + * @param h + * Hash table to add the key to. + * @param key + * Key to add to the hash table. + * @param sig + * Hash value to add to the hash table. + * @param data + * Data 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. + * - 0 if key was added successfully + */ +int32_t +rte_hash_add_key_with_hash_data(const struct rte_hash *h, const void *key, + hash_sig_t sig, uintptr_t data); + +/** * Add a key to an existing hash table. This operation is not multi-thread safe * and should only be called from one thread. * @@ -237,6 +287,45 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t * Hash table to remove the key from. * @param key * Key to remove from the hash table. + * @param data + * Pointer to data returned from the hash table. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOENT if the key is not found. + * - 0 if key was deleted successfully + */ +int32_t +rte_hash_del_key_data(const struct rte_hash *h, const void *key, uintptr_t *data); + +/** + * Remove a key from an existing hash table. This operation is not multi-thread + * safe and should only be called from one thread. + * + * @param h + * Hash table to remove the key from. + * @param key + * Key to remove from the hash table. + * @param sig + * Hash value to remove from the hash table. + * @param data + * Pointer to data returned from the hash table. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOENT if the key is not found. + * - 0 if key was deleted successfully + */ +int32_t +rte_hash_del_key_with_hash_data(const struct rte_hash *h, const void *key, + hash_sig_t sig, uintptr_t *data); + +/** + * Remove a key from an existing hash table. This operation is not multi-thread + * safe and should only be called from one thread. + * + * @param h + * Hash table to remove the key from. + * @param key + * Key to remove from the hash table. * @return * - -EINVAL if the parameters are invalid. * - -ENOENT if the key is not found. @@ -263,6 +352,44 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); int32_t 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. + * + * @param h + * Hash table to look in. + * @param key + * Key to find. + * @param data + * Data to return. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOENT if the key is not found. + * - 0 if key was found successfully + */ +int32_t +rte_hash_lookup_data(const struct rte_hash *h, const void *key, uintptr_t *data); + +/** + * Find a key in the hash table. This operation is multi-thread safe. + * + * @param h + * Hash table to look in. + * @param key + * Key to find. + * @param sig + * Hash value to find. + * @param data + * Pointer to data returned from the hash table. + * @return + * - -EINVAL if the parameters are invalid. + * - -ENOENT if the key is not found. + * - 0 if key was found successfully + */ +int32_t +rte_hash_lookup_with_hash_data(const struct rte_hash *h, const void *key, + hash_sig_t sig, uintptr_t *data); + /** * Find a key in the hash table. This operation is multi-thread safe. * @@ -296,7 +423,33 @@ int32_t 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 +#define rte_hash_lookup_multi_data rte_hash_lookup_bulk_data #define rte_hash_lookup_multi_with_hash rte_hash_lookup_bulk_with_hash +#define rte_hash_lookup_multi_with_hash_data rte_hash_lookup_bulk_with_hash_data +/** + * 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. + * @param data + * Output containing array of data returned from all the successful lookups. + * @return + * -EINVAL if there's an error, otherwise 0. + */ +int +rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys, + uint32_t num_keys, int32_t *positions, uintptr_t data[]); + /** * Find multiple keys in the hash table. This operation is multi-thread safe. * @@ -336,6 +489,33 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, * 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 data + * Output containing array of data returned from all the successful lookups. + * @return + * -EINVAL if there's an error, otherwise 0. + */ +int +rte_hash_lookup_bulk_with_hash_data(const struct rte_hash *h, const void **keys, + const hash_sig_t *hash_vals, uint32_t num_keys, + int32_t *positions, uintptr_t data[]); + +/** + * 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 hash_vals + * A pointer to a list of pre-calculated hash values. + * @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. */ diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index 0a78756..1b06e37 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -21,7 +21,15 @@ DPDK_2.0 { DPDK_2.1 { global: + rte_hash_add_key_data; + rte_hash_add_key_with_hash_data; + rte_hash_del_key_data; + rte_hash_del_key_with_hash_data; + rte_hash_lookup_bulk_data; rte_hash_lookup_bulk_with_hash; + rte_hash_lookup_bulk_with_hash_data; + rte_hash_lookup_data; + rte_hash_lookup_with_hash_data; rte_hash_rehash; rte_hash_reset; -- 2.4.2