From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga01.intel.com (mga01.intel.com [192.55.52.88]) by dpdk.org (Postfix) with ESMTP id A236AC714 for ; Fri, 26 Jun 2015 00:08:33 +0200 (CEST) Received: from orsmga002.jf.intel.com ([10.7.209.21]) by fmsmga101.fm.intel.com with ESMTP; 25 Jun 2015 15:08:32 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,680,1427785200"; d="scan'208";a="753354893" Received: from msvmon001.ims.intel.com ([10.125.148.15]) by orsmga002.jf.intel.com with ESMTP; 25 Jun 2015 15:08:32 -0700 Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com [10.237.217.46]) by msvmon001.ims.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id t5PM8TvX028744; Fri, 26 Jun 2015 01:08:29 +0300 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t5PM5K1u007103; Thu, 25 Jun 2015 23:05:20 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t5PM5KdV007099; Thu, 25 Jun 2015 23:05:20 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Thu, 25 Jun 2015 23:05:16 +0100 Message-Id: <1435269919-7007-9-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1435269919-7007-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> <1435269919-7007-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH v2 08/11] 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: Thu, 25 Jun 2015 22:08:35 -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 adding/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_cuckoo_hash.c | 231 +++++++++++++++++++++++++---------- lib/librte_hash/rte_hash.h | 144 +++++++++++++++++++++- lib/librte_hash/rte_hash_version.map | 6 + 3 files changed, 314 insertions(+), 67 deletions(-) diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 8e5b9a6..37e72ab 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -84,6 +84,8 @@ EAL_REGISTER_TAILQ(rte_hash_tailq) #endif #define NULL_SIGNATURE 0 +/* Stored key size is a multiple of this value */ +#define KEY_ALIGNMENT 16 typedef int (*rte_hash_cmp_eq_t)(const void *key1, const void *key2, size_t key_len); static int rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t key_len); @@ -133,6 +135,15 @@ struct rte_hash_bucket { uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES + 1]; } __rte_cache_aligned; +struct rte_hash_key { + union { + uintptr_t idata; + void *pdata; + }; + /* Variable key size */ + char key[] __attribute__((aligned(KEY_ALIGNMENT))); +}; + struct rte_hash * rte_hash_find_existing(const char *name) { @@ -200,7 +211,7 @@ rte_hash_create(const struct rte_hash_parameters *params) /* Total memory required for hash context */ const uint32_t mem_size = sizeof(struct rte_hash) + num_buckets * sizeof(struct rte_hash_bucket); - const uint8_t key_entry_size = params->key_len; + const uint8_t key_entry_size = sizeof(struct rte_hash_key) + params->key_len; /* Store all keys and leave the first entry as a dummy entry for lookup_bulk */ const uint64_t key_tbl_size = key_entry_size * (params->entries + 1); @@ -396,7 +407,7 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, const void *original_key) { static unsigned number_pushes; - void *k, *keys = h->key_store; + struct rte_hash_key *k, *keys = h->key_store; unsigned i, j; hash_sig_t current_hash_stored, alt_hash_stored; @@ -421,8 +432,8 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, * we just entered in a loop and key cannot be added */ if (++number_pushes > 1 && current_hash == original_hash) { - k = (char *)keys + key_idx * h->key_entry_size; - if (!h->rte_hash_cmp_eq(k, original_key, h->key_len)) { + k = (struct rte_hash_key *) ((char *)keys + key_idx * h->key_entry_size); + if (!h->rte_hash_cmp_eq(k->key, original_key, h->key_len)) { rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)key_idx)); number_pushes = 0; @@ -436,6 +447,9 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { key_idx_stored = bkt->key_idx[i]; + k = (struct rte_hash_key *) ((char *)keys + + key_idx_stored * h->key_entry_size); + current_hash_stored = bkt->signatures[i].current; alt_hash_stored = bkt->signatures[i].alt; @@ -479,20 +493,21 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, 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) { hash_sig_t hash0, hash1; uint32_t bucket_idx0, bucket_idx1; unsigned i; struct rte_hash_bucket *bkt0, *bkt1; - void *new_k, *k, *keys = h->key_store; + struct rte_hash_key *new_k, *k, *keys = h->key_store; void *slot_id; int ret; /* Get a new slot for storing the new key */ if (rte_ring_sc_dequeue(h->free_slots, &slot_id) != 0) return -ENOSPC; - new_k = (char *)keys + (uintptr_t)slot_id * h->key_entry_size; + new_k = (struct rte_hash_key *) ((char *)keys + + (uintptr_t)slot_id * h->key_entry_size); rte_prefetch0(new_k); hash0 = sig; @@ -508,9 +523,12 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt0->signatures[i].current == hash0 && bkt0->signatures[i].alt == hash1) { - k = (char *)keys + bkt0->key_idx[i] * h->key_entry_size; - if (!h->rte_hash_cmp_eq(key, k, h->key_len)) { + k = (struct rte_hash_key *) ((char *)keys + + bkt0->key_idx[i] * h->key_entry_size); + if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) { rte_ring_sp_enqueue(h->free_slots, &slot_id); + /* Update data */ + k->idata = data; /* * Return index where key is stored, * substracting the first dummy index @@ -524,9 +542,12 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt1->signatures[i].alt == hash0 && bkt1->signatures[i].current == hash1) { - k = (char *)keys + bkt1->key_idx[i] * h->key_entry_size; - if (!h->rte_hash_cmp_eq(key, k, h->key_len)) { + k = (struct rte_hash_key *) ((char *)keys + + bkt1->key_idx[i] * h->key_entry_size); + if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) { rte_ring_sp_enqueue(h->free_slots, &slot_id); + /* Update data */ + k->idata = data; /* * Return index where key is stored, * substracting the first dummy index @@ -536,8 +557,9 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, } } - /* Copy key */ - rte_memcpy(new_k, key, h->key_len); + /* Copy key and data */ + rte_memcpy(new_k->key, key, h->key_len); + new_k->idata = data; /* * Run cuckoo algorithm @@ -568,25 +590,40 @@ 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) { uint32_t bucket_idx; hash_sig_t alt_hash; unsigned i; struct rte_hash_bucket *bkt; - void *k, *keys = h->key_store; + struct rte_hash_key *k, *keys = h->key_store; bucket_idx = sig & h->bucket_bitmask; bkt = &h->buckets[bucket_idx]; @@ -595,13 +632,17 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt->signatures[i].current == sig && bkt->signatures[i].sig != NULL_SIGNATURE) { - k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; - if (!h->rte_hash_cmp_eq(key, k, h->key_len)) + k = (struct rte_hash_key *) ((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) { + if (data != NULL) + *data = k->idata; /* * Return index where key is stored, * substracting the first dummy index */ return (bkt->key_idx[i] - 1); + } } } @@ -614,13 +655,17 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt->signatures[i].current == alt_hash && bkt->signatures[i].alt == sig) { - k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; - if (!h->rte_hash_cmp_eq(key, k, h->key_len)) + k = (struct rte_hash_key *) ((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) { + if (data != NULL) + *data = k->idata; /* * Return index where key is stored, * substracting the first dummy index */ return (bkt->key_idx[i] - 1); + } } } @@ -628,29 +673,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) +__rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig) { uint32_t bucket_idx; hash_sig_t alt_hash; unsigned i; struct rte_hash_bucket *bkt; - void *k, *keys = h->key_store; + struct rte_hash_key *k, *keys = h->key_store; bucket_idx = sig & h->bucket_bitmask; bkt = &h->buckets[bucket_idx]; @@ -659,8 +718,9 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt->signatures[i].current == sig && bkt->signatures[i].sig != NULL_SIGNATURE) { - k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; - if (!h->rte_hash_cmp_eq(key, k, h->key_len)) { + k = (struct rte_hash_key *) ((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) { bkt->signatures[i].sig = NULL_SIGNATURE; rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)bkt->key_idx[i])); @@ -682,8 +742,9 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt->signatures[i].current == alt_hash && bkt->signatures[i].sig != NULL_SIGNATURE) { - k = (char *)keys + bkt->key_idx[i] * h->key_entry_size; - if (!h->rte_hash_cmp_eq(key, k, h->key_len)) { + k = (struct rte_hash_key *) ((char *)keys + + bkt->key_idx[i] * h->key_entry_size); + if (!h->rte_hash_cmp_eq(key, k->key, h->key_len)) { bkt->signatures[i].sig = NULL_SIGNATURE; rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)bkt->key_idx[i])); @@ -768,9 +829,9 @@ static inline void lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash, const struct rte_hash_bucket *prim_bkt, const struct rte_hash_bucket *sec_bkt, - const void **key_slot, int32_t *positions, - uint64_t *extra_hits_mask, const void *keys, - const struct rte_hash *h) + const struct rte_hash_key **key_slot, + int32_t *positions, uint64_t *extra_hits_mask, + const void *keys, const struct rte_hash *h) { unsigned prim_hash_matches, sec_hash_matches, key_idx, i; unsigned total_hash_matches; @@ -788,8 +849,8 @@ lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash, total_hash_matches = (prim_hash_matches | (sec_hash_matches << (RTE_HASH_BUCKET_ENTRIES + 1))); - *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); /* * Return index where key is stored, @@ -804,15 +865,20 @@ lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_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 = !h->rte_hash_cmp_eq(key_slot, keys[idx], h->key_len); + if (values != NULL) + values[idx] = key_slot->idata; + hit = !h->rte_hash_cmp_eq(key_slot->key, keys[idx], h->key_len); if (unlikely(hit == 0)) positions[idx] = -ENOENT; *hits = (uint64_t)(hit) << idx; @@ -820,21 +886,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; hash_sig_t primary_hash00, primary_hash01; hash_sig_t secondary_hash00, secondary_hash01; hash_sig_t primary_hash10, primary_hash11; @@ -847,6 +913,7 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, else lookup_mask = (1ULL << num_keys) - 1; + lookup_stage0(&idx00, &lookup_mask, &primary_hash00, &secondary_hash00, keys, h); lookup_stage0(&idx01, &lookup_mask, &primary_hash01, @@ -929,8 +996,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; @@ -959,8 +1026,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; @@ -980,14 +1047,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; @@ -999,7 +1066,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); } @@ -1010,21 +1081,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; hash_sig_t primary_hash00, primary_hash01; hash_sig_t secondary_hash00, secondary_hash01; hash_sig_t primary_hash10, primary_hash11; @@ -1119,8 +1190,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; @@ -1150,8 +1221,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; @@ -1171,14 +1242,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; @@ -1190,7 +1261,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); @@ -1200,6 +1275,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) { @@ -1207,7 +1293,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 @@ -1220,7 +1319,7 @@ 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); } /* Functions to compare multiple of 16 byte keys (up to 128 bytes) */ diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index fa327c2..940e5db 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -89,7 +89,6 @@ struct rte_hash_parameters { /** @internal A hash table structure. */ struct rte_hash; - /** * Create a new hash table. * @@ -140,6 +139,50 @@ void rte_hash_reset(struct rte_hash *h); /** + * Add a key-value pair 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. + * - -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. + */ +int32_t +rte_hash_add_key_data(const struct rte_hash *h, const void *key, uintptr_t data); + +/** + * Add a key-value pair with a pre-computed hash value + * 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 + * Precomputed hash value for 'key' + * @param data + * Data to add to the hash table. + * @return + * - -EINVAL if the parameters are invalid. + * - -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. + */ +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. * @@ -216,6 +259,51 @@ 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-value pair 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. + * - 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. + */ +int32_t +rte_hash_lookup_data(const struct rte_hash *h, const void *key, uintptr_t *data); + +/** + * Find a key-value pair with a pre-computed hash value + * to an existing hash table. + * This operation is multi-thread safe. + * + * @param h + * Hash table to look in. + * @param key + * Key to find. + * @param sig + * Precomputed hash value for 'key' + * @param data + * Pointer to data returned from the hash table. + * @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. + */ +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. @@ -270,7 +358,34 @@ hash_sig_t rte_hash_hash(const struct rte_hash *h, const void *key); #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. @@ -303,6 +418,33 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, * @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 for 'keys'. + * @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_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). diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index f011054..3a4e1a3 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -21,7 +21,13 @@ DPDK_2.0 { DPDK_2.1 { global: + rte_hash_add_key_data; + rte_hash_add_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_reset; local: *; -- 2.4.2