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 E58215A54 for ; Fri, 5 Jun 2015 16:33:28 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) 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="503280434" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by FMSMGA003.fm.intel.com with ESMTP; 05 Jun 2015 07:33:25 -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 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 From: Pablo de Lara To: dev@dpdk.org Date: Fri, 5 Jun 2015 15:33:23 +0100 Message-Id: <1433514804-7075-6-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 5/6] hash: add new functionality to store data in hash table 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 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