From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id AB5F1C3FE for ; Fri, 10 Jul 2015 19:24:37 +0200 (CEST) Received: from orsmga001.jf.intel.com ([10.7.209.18]) by orsmga102.jf.intel.com with ESMTP; 10 Jul 2015 10:24:38 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.15,448,1432623600"; d="scan'208";a="726563811" Received: from pdelarag-mobl.ger.corp.intel.com ([10.237.208.60]) by orsmga001.jf.intel.com with SMTP; 10 Jul 2015 10:24:35 -0700 Received: by (sSMTP sendmail emulation); Fri, 10 Jul 2015 18:24:34 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Fri, 10 Jul 2015 18:24:20 +0100 Message-Id: <1436549064-5200-4-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 2.4.5 In-Reply-To: <1436549064-5200-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> <1436549064-5200-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH v4 3/7] 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, 10 Jul 2015 17:24:39 -0000 Usually hash tables not only store keys, but also data associated to them. In order to maintain the existing API, the old functions will still return the index where the key was stored. The new functions will return the data associated to that key. In the case of the lookup_bulk function, it will return also the number of entries found and a bitmask of which entries were found. Unit tests have been updated to use these new functions. As a final point, a flag has been added in rte_hash_parameters to indicate if there are new parameters for future versions, so there is no need to maintain multiple versions of the existing functions in the future. Signed-off-by: Pablo de Lara --- app/test/test_hash_perf.c | 254 +++++++++++++++++++++++++---------- lib/librte_hash/rte_cuckoo_hash.c | 193 ++++++++++++++++++++------ lib/librte_hash/rte_hash.h | 108 ++++++++++++++- lib/librte_hash/rte_hash_version.map | 6 + 4 files changed, 441 insertions(+), 120 deletions(-) diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c index b01b040..7a6dbf7 100644 --- a/app/test/test_hash_perf.c +++ b/app/test/test_hash_perf.c @@ -55,6 +55,7 @@ #define NUM_KEYSIZES 10 #define NUM_SHUFFLES 10 #define BURST_SIZE 16 +#define DATA_MULTIPLIER 13 /* Used for storing data */ enum operations { ADD = 0, @@ -83,7 +84,7 @@ struct rte_hash *h[NUM_KEYSIZES]; uint8_t slot_taken[MAX_ENTRIES]; /* Array to store number of cycles per operation */ -uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2]; +uint64_t cycles[NUM_KEYSIZES][NUM_OPERATIONS][2][2]; /* Array to store all input keys */ uint8_t keys[KEYS_TO_ADD][MAX_KEYSIZE]; @@ -106,11 +107,16 @@ static struct rte_hash_parameters ut_params = { }; static int -create_table(unsigned table_index) +create_table(unsigned with_data, unsigned table_index) { char name[RTE_HASH_NAMESIZE]; - sprintf(name, "test_hash%d", hashtest_key_lens[table_index]); + if (with_data) + /* Table will store 8-byte data */ + sprintf(name, "test_hash%d_data", hashtest_key_lens[table_index]); + else + sprintf(name, "test_hash%d", hashtest_key_lens[table_index]); + ut_params.name = name; ut_params.key_len = hashtest_key_lens[table_index]; ut_params.socket_id = rte_socket_id(); @@ -234,6 +240,7 @@ get_input_keys(unsigned with_pushes, unsigned table_index) else { /* Store the returned position and mark slot as taken */ slot_taken[ret] = 1; + positions[i] = ret; buckets[bucket_idx]++; success = 1; i++; @@ -249,54 +256,116 @@ get_input_keys(unsigned with_pushes, unsigned table_index) } static int -timed_adds(unsigned with_hash, unsigned table_index) +timed_adds(unsigned with_hash, unsigned with_data, unsigned table_index) { unsigned i; const uint64_t start_tsc = rte_rdtsc(); + uintptr_t data; int32_t ret; for (i = 0; i < KEYS_TO_ADD; i++) { - if (with_hash) + data = (uint64_t) signatures[i] * DATA_MULTIPLIER; + if (with_hash && with_data) { + ret = rte_hash_add_key_with_hash_data(h[table_index], + (const void *) keys[i], + signatures[i], data); + if (ret < 0) { + printf("Failed to add key number %u\n", ret); + return -1; + } + } else if (with_hash && !with_data) { ret = rte_hash_add_key_with_hash(h[table_index], (const void *) keys[i], signatures[i]); - else + if (ret >= 0) + positions[i] = ret; + else { + printf("Failed to add key number %u\n", ret); + return -1; + } + } else if (!with_hash && with_data) { + ret = rte_hash_add_key_data(h[table_index], + (const void *) keys[i], + data); + if (ret < 0) { + printf("Failed to add key number %u\n", ret); + return -1; + } + } else { ret = rte_hash_add_key(h[table_index], keys[i]); - - if (ret >= 0) - positions[i] = ret; - else { - printf("Failed to add key number %u\n", ret); - return -1; + if (ret >= 0) + positions[i] = ret; + else { + printf("Failed to add key number %u\n", ret); + return -1; + } } } const uint64_t end_tsc = rte_rdtsc(); const uint64_t time_taken = end_tsc - start_tsc; - cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD; + cycles[table_index][ADD][with_hash][with_data] = time_taken/KEYS_TO_ADD; + return 0; } static int -timed_lookups(unsigned with_hash, unsigned table_index) +timed_lookups(unsigned with_hash, unsigned with_data, unsigned table_index) { unsigned i, j; const uint64_t start_tsc = rte_rdtsc(); + uintptr_t ret_data; + uintptr_t expected_data; int32_t ret; for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { for (j = 0; j < KEYS_TO_ADD; j++) { - if (with_hash) + if (with_hash && with_data) { + ret = rte_hash_lookup_with_hash_data(h[table_index], + (const void *) keys[j], + signatures[j], &ret_data); + if (ret < 0) { + printf("Key number %u was not found\n", j); + return -1; + } + expected_data = (uint64_t) signatures[j] * DATA_MULTIPLIER; + if (ret_data != expected_data) { + printf("Data returned for key number %u is %"PRIx64"," + " but should be %"PRIx64"\n", j, ret_data, + expected_data); + return -1; + } + } else if (with_hash && !with_data) { ret = rte_hash_lookup_with_hash(h[table_index], (const void *) keys[j], signatures[j]); - else + if (ret < 0 || ret != positions[j]) { + printf("Key looked up in %d, should be in %d\n", + ret, positions[j]); + return -1; + } + } else if (!with_hash && with_data) { + ret = rte_hash_lookup_data(h[table_index], + (const void *) keys[j], &ret_data); + if (ret < 0) { + printf("Key number %u was not found\n", j); + return -1; + } + expected_data = (uint64_t) signatures[j] * DATA_MULTIPLIER; + if (ret_data != expected_data) { + printf("Data returned for key number %u is %"PRIx64"," + " but should be %"PRIx64"\n", j, ret_data, + expected_data); + return -1; + } + } else { ret = rte_hash_lookup(h[table_index], keys[j]); - if (ret < 0 || ret != positions[j]) { - printf("Key looked up in %d, should be in %d\n", - ret, positions[j]); - return -1; + if (ret < 0 || ret != positions[j]) { + printf("Key looked up in %d, should be in %d\n", + ret, positions[j]); + return -1; + } } } } @@ -304,34 +373,66 @@ timed_lookups(unsigned with_hash, unsigned table_index) const uint64_t end_tsc = rte_rdtsc(); const uint64_t time_taken = end_tsc - start_tsc; - cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS; + cycles[table_index][LOOKUP][with_hash][with_data] = time_taken/NUM_LOOKUPS; return 0; } static int -timed_lookups_multi(unsigned table_index) +timed_lookups_multi(unsigned with_data, unsigned table_index) { unsigned i, j, k; int32_t positions_burst[BURST_SIZE]; const void *keys_burst[BURST_SIZE]; + uintptr_t expected_data[BURST_SIZE]; + uintptr_t ret_data[BURST_SIZE]; + uint64_t hit_mask; + int ret; + const uint64_t start_tsc = rte_rdtsc(); for (i = 0; i < NUM_LOOKUPS/KEYS_TO_ADD; i++) { for (j = 0; j < KEYS_TO_ADD/BURST_SIZE; j++) { for (k = 0; k < BURST_SIZE; k++) keys_burst[k] = keys[j * BURST_SIZE + k]; - - rte_hash_lookup_bulk(h[table_index], + if (with_data) { + ret = rte_hash_lookup_bulk_data(h[table_index], + (const void **) keys_burst, + BURST_SIZE, + &hit_mask, + ret_data); + if (ret != BURST_SIZE) { + printf("Expect to find %u keys," + " but found %d\n", BURST_SIZE, ret); + return -1; + } + for (k = 0; k < BURST_SIZE; k++) { + if ((hit_mask & (1ULL << k)) == 0) { + printf("Key number %u not found\n", + j * BURST_SIZE + k); + return -1; + } + expected_data[k] = (uint64_t)signatures[j * BURST_SIZE + k] + * DATA_MULTIPLIER; + if (ret_data[k] != expected_data[k]) { + printf("Data returned for key number %u is %"PRIx64"," + " but should be %"PRIx64"\n", j * BURST_SIZE + k, + ret_data[k], expected_data[k]); + return -1; + } + } + } else { + rte_hash_lookup_bulk(h[table_index], (const void **) keys_burst, BURST_SIZE, positions_burst); - for (k = 0; k < BURST_SIZE; k++) { - if (positions_burst[k] != positions[j * BURST_SIZE + k]) { - printf("Key looked up in %d, should be in %d\n", - positions_burst[k], - positions[j * BURST_SIZE + k]); - return -1; + for (k = 0; k < BURST_SIZE; k++) { + if (positions_burst[k] != positions[j * BURST_SIZE + k]) { + printf("Key looked up in %d, should be in %d\n", + positions_burst[k], + positions[j * BURST_SIZE + k]); + return -1; + } } } } @@ -340,19 +441,20 @@ timed_lookups_multi(unsigned table_index) const uint64_t end_tsc = rte_rdtsc(); const uint64_t time_taken = end_tsc - start_tsc; - cycles[table_index][LOOKUP_MULTI][0] = time_taken/NUM_LOOKUPS; + cycles[table_index][LOOKUP_MULTI][0][with_data] = time_taken/NUM_LOOKUPS; return 0; } static int -timed_deletes(unsigned with_hash, unsigned table_index) +timed_deletes(unsigned with_hash, unsigned with_data, unsigned table_index) { unsigned i; const uint64_t start_tsc = rte_rdtsc(); int32_t ret; for (i = 0; i < KEYS_TO_ADD; i++) { + /* There are no delete functions with data, so just call two functions */ if (with_hash) ret = rte_hash_del_key_with_hash(h[table_index], (const void *) keys[i], @@ -371,7 +473,7 @@ timed_deletes(unsigned with_hash, unsigned table_index) const uint64_t end_tsc = rte_rdtsc(); const uint64_t time_taken = end_tsc - start_tsc; - cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD; + cycles[table_index][DELETE][with_hash][with_data] = time_taken/KEYS_TO_ADD; return 0; } @@ -391,62 +493,67 @@ reset_table(unsigned table_index) static int run_all_tbl_perf_tests(unsigned with_pushes) { - unsigned i, j, with_hash; + unsigned i, j, with_data, with_hash; printf("Measuring performance, please wait"); fflush(stdout); - for (i = 0; i < NUM_KEYSIZES; i++) { - if (create_table(i) < 0) - return -1; - if (get_input_keys(with_pushes, i) < 0) - return -1; - for (with_hash = 0; with_hash <= 1; with_hash++) { - if (timed_adds(with_hash, i) < 0) + for (with_data = 0; with_data <= 1; with_data++) { + for (i = 0; i < NUM_KEYSIZES; i++) { + if (create_table(with_data, i) < 0) return -1; - for (j = 0; j < NUM_SHUFFLES; j++) - shuffle_input_keys(i); - - if (timed_lookups(with_hash, i) < 0) + if (get_input_keys(with_pushes, i) < 0) return -1; + for (with_hash = 0; with_hash <= 1; with_hash++) { + if (timed_adds(with_hash, with_data, i) < 0) + return -1; - if (timed_lookups_multi(i) < 0) - return -1; + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); - if (timed_deletes(with_hash, i) < 0) - return -1; + if (timed_lookups(with_hash, with_data, i) < 0) + return -1; - reset_table(i); + if (timed_lookups_multi(with_data, i) < 0) + return -1; - /* Print a dot to show progress on operations */ - printf("."); - fflush(stdout); - } + if (timed_deletes(with_hash, with_data, i) < 0) + return -1; - free_table(i); + /* Print a dot to show progress on operations */ + printf("."); + fflush(stdout); + + reset_table(i); + } + free_table(i); + } } + printf("\nResults (in CPU cycles/operation)\n"); - printf("---------------------------------\n"); - printf("\nWithout pre-computed hash values\n"); - printf("\n%-18s%-18s%-18s%-18s%-18s\n", - "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); - for (i = 0; i < NUM_KEYSIZES; i++) { - printf("%-18d", hashtest_key_lens[i]); - for (j = 0; j < NUM_OPERATIONS; j++) - printf("%-18"PRIu64, cycles[i][j][0]); - printf("\n"); - } - printf("\nWith pre-computed hash values\n"); - printf("\n%-18s%-18s%-18s%-18s%-18s\n", + printf("-----------------------------------\n"); + for (with_data = 0; with_data <= 1; with_data++) { + if (with_data) + printf("\n Operations with 8-byte data\n"); + else + printf("\n Operations without data\n"); + for (with_hash = 0; with_hash <= 1; with_hash++) { + if (with_hash) + printf("\nWith pre-computed hash values\n"); + else + printf("\nWithout pre-computed hash values\n"); + + printf("\n%-18s%-18s%-18s%-18s%-18s\n", "Keysize", "Add", "Lookup", "Lookup_bulk", "Delete"); - for (i = 0; i < NUM_KEYSIZES; i++) { - printf("%-18d", hashtest_key_lens[i]); - for (j = 0; j < NUM_OPERATIONS; j++) - printf("%-18"PRIu64, cycles[i][j][1]); - printf("\n"); + for (i = 0; i < NUM_KEYSIZES; i++) { + printf("%-18d", hashtest_key_lens[i]); + for (j = 0; j < NUM_OPERATIONS; j++) + printf("%-18"PRIu64, cycles[i][j][with_hash][with_data]); + printf("\n"); + } + } } - return 0; } @@ -546,7 +653,6 @@ test_hash_perf(void) if (run_all_tbl_perf_tests(with_pushes) < 0) return -1; } - if (fbk_hash_perf_test() < 0) return -1; diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 15c5da5..cd91a7d 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -56,6 +56,7 @@ #include #include #include +#include #include "rte_hash.h" @@ -90,6 +91,8 @@ EAL_REGISTER_TAILQ(rte_hash_tailq) #define NULL_SIGNATURE 0 +#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); static int rte_hash_k32_cmp_eq(const void *key1, const void *key2, size_t key_len); @@ -132,6 +135,16 @@ struct rte_hash_signatures { }; }; +/* Structure that stores key-value pair */ +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 { struct rte_hash_signatures signatures[RTE_HASH_BUCKET_ENTRIES]; @@ -227,7 +240,8 @@ rte_hash_create(const struct rte_hash_parameters *params) goto err; } - const uint32_t key_entry_size = params->key_len; + const uint32_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); @@ -461,13 +475,13 @@ make_space_bucket(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 alt_hash; uint32_t prim_bucket_idx, sec_bucket_idx; unsigned i; struct rte_hash_bucket *prim_bkt, *sec_bkt; - void *new_k, *k, *keys = h->key_store; + struct rte_hash_key *new_k, *k, *keys = h->key_store; void *slot_id; uint32_t new_idx; int ret; @@ -492,9 +506,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 (prim_bkt->signatures[i].current == sig && prim_bkt->signatures[i].alt == alt_hash) { - k = (char *)keys + prim_bkt->key_idx[i] * h->key_entry_size; - if (h->rte_hash_cmp_eq(key, k, h->key_len) == 0) { + k = (struct rte_hash_key *) ((char *)keys + + prim_bkt->key_idx[i] * h->key_entry_size); + if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) { 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 @@ -508,9 +525,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 (sec_bkt->signatures[i].alt == sig && sec_bkt->signatures[i].current == alt_hash) { - k = (char *)keys + sec_bkt->key_idx[i] * h->key_entry_size; - if (h->rte_hash_cmp_eq(key, k, h->key_len) == 0) { + k = (struct rte_hash_key *) ((char *)keys + + sec_bkt->key_idx[i] * h->key_entry_size); + if (h->rte_hash_cmp_eq(key, k->key, h->key_len) == 0) { 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 @@ -521,7 +541,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, } /* Copy key */ - rte_memcpy(new_k, key, h->key_len); + rte_memcpy(new_k->key, key, h->key_len); + new_k->idata = data; /* Insert new entry is there is room in the primary bucket */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { @@ -561,25 +582,52 @@ 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, NULL); } 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), NULL); +} + +int +rte_hash_add_key_with_hash_data(const struct rte_hash *h, + const void *key, hash_sig_t sig, uintptr_t data) +{ + int ret; + + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + ret = __rte_hash_add_key_with_hash(h, key, sig, data); + if (ret >= 0) + return 0; + else + return ret; } +int +rte_hash_add_key_data(const struct rte_hash *h, const void *key, uintptr_t data) +{ + int ret; + + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + + ret = __rte_hash_add_key_with_hash(h, key, rte_hash_hash(h, key), data); + if (ret >= 0) + return 0; + else + return ret; +} 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]; @@ -588,13 +636,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) == 0) + 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) == 0) { + if (data != NULL) + *data = k->idata; /* * Return index where key is stored, * substracting the first dummy index */ return (bkt->key_idx[i] - 1); + } } } @@ -607,13 +659,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) == 0) + 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) == 0) { + if (data != NULL) + *data = k->idata; /* * Return index where key is stored, * substracting the first dummy index */ return (bkt->key_idx[i] - 1); + } } } @@ -625,14 +681,29 @@ 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); +} + +int +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); +} + +int +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); } static inline int32_t @@ -643,7 +714,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, 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]; @@ -652,8 +723,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) == 0) { + 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) == 0) { bkt->signatures[i].sig = NULL_SIGNATURE; rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)bkt->key_idx[i])); @@ -675,8 +747,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) == 0) { + 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) == 0) { bkt->signatures[i].sig = NULL_SIGNATURE; rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t)bkt->key_idx[i])); @@ -750,7 +823,7 @@ 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, + const struct rte_hash_key **key_slot, int32_t *positions, uint64_t *extra_hits_mask, const void *keys, const struct rte_hash *h) { @@ -770,7 +843,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); /* @@ -784,26 +858,31 @@ 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 return data */ static inline void -lookup_stage3(unsigned idx, const void *key_slot, const void * const *keys, - uint64_t *hits, const struct rte_hash *h) +lookup_stage3(unsigned idx, const struct rte_hash_key *key_slot, const void * const *keys, + uintptr_t data[], uint64_t *hits, const struct rte_hash *h) { unsigned hit; - hit = !h->rte_hash_cmp_eq(key_slot, keys[idx], h->key_len); + hit = !h->rte_hash_cmp_eq(key_slot->key, keys[idx], h->key_len); + if (data != NULL) + data[idx] = key_slot->idata; + *hits |= (uint64_t)(hit) << idx; } static inline void __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, + uint64_t *hit_mask, uintptr_t data[]) { uint64_t hits = 0; uint64_t extra_hits_mask = 0; uint64_t lookup_mask, miss_mask; unsigned idx; const void *key_store = h->key_store; + int ret; hash_sig_t hash_vals[RTE_HASH_LOOKUP_BULK_MAX]; unsigned idx00, idx01, idx10, idx11, idx20, idx21, idx30, idx31; @@ -811,7 +890,7 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, 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_hash10, primary_hash11; hash_sig_t secondary_hash10, secondary_hash11; hash_sig_t primary_hash20, primary_hash21; @@ -882,8 +961,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, &hits, h); - lookup_stage3(idx31, k_slot31, keys, &hits, h); + lookup_stage3(idx30, k_slot30, keys, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, &hits, h); } k_slot30 = k_slot20, k_slot31 = k_slot21; @@ -909,8 +988,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, &hits, h); - lookup_stage3(idx31, k_slot31, keys, &hits, h); + lookup_stage3(idx30, k_slot30, keys, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, &hits, h); k_slot30 = k_slot20, k_slot31 = k_slot21; idx30 = idx20, idx31 = idx21; @@ -930,14 +1009,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, &hits, h); - lookup_stage3(idx31, k_slot31, keys, &hits, h); + lookup_stage3(idx30, k_slot30, keys, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, &hits, h); k_slot30 = k_slot20, k_slot31 = k_slot21; idx30 = idx20, idx31 = idx21; - lookup_stage3(idx30, k_slot30, keys, &hits, h); - lookup_stage3(idx31, k_slot31, keys, &hits, h); + lookup_stage3(idx30, k_slot30, keys, data, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, &hits, h); /* ignore any items we have already found */ extra_hits_mask &= ~hits; @@ -946,11 +1025,18 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, /* run a single search for each remaining item */ do { idx = __builtin_ctzl(extra_hits_mask); - positions[idx] = rte_hash_lookup_with_hash(h, keys[idx], - hash_vals[idx]); + if (data != NULL) { + ret = rte_hash_lookup_with_hash_data(h, + keys[idx], hash_vals[idx], &data[idx]); + if (ret >= 0) + hits |= 1ULL << idx; + } else { + positions[idx] = rte_hash_lookup_with_hash(h, + keys[idx], hash_vals[idx]); + if (positions[idx] >= 0) + hits |= 1llu << idx; + } extra_hits_mask &= ~(1llu << idx); - if (positions[idx] >= 0) - hits |= 1llu << idx; } while (extra_hits_mask); } @@ -962,6 +1048,9 @@ __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, miss_mask &= ~(1llu << idx); } while (miss_mask); } + + if (hit_mask != NULL) + *hit_mask = hits; } int @@ -972,10 +1061,26 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || (positions == NULL)), -EINVAL); - __rte_hash_lookup_bulk(h, keys, num_keys, positions); + __rte_hash_lookup_bulk(h, keys, num_keys, positions, NULL, NULL); return 0; } +int +rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys, + uint32_t num_keys, uint64_t *hit_mask, uintptr_t data[]) +{ + RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || + (num_keys > RTE_HASH_LOOKUP_BULK_MAX), + (hit_mask == NULL)), -EINVAL); + + int32_t positions[num_keys]; + + __rte_hash_lookup_bulk(h, keys, num_keys, positions, hit_mask, data); + + /* Return number of hits */ + return __builtin_popcountl(*hit_mask); +} + /* Functions to compare multiple of 16 byte keys (up to 128 bytes) */ static int rte_hash_k16_cmp_eq(const void *key1, const void *key2, size_t key_len __rte_unused) diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index 8bbc9f0..15f8b2f 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -80,12 +80,12 @@ struct rte_hash_parameters { rte_hash_function hash_func; /**< Primary Hash function used to calculate hash. */ uint32_t hash_func_init_val; /**< Init value used by hash_func. */ int socket_id; /**< NUMA Socket ID for memory. */ + uint8_t extra_flag; /**< Indicate if additional parameters are present. */ }; /** @internal A hash table structure. */ struct rte_hash; - /** * Create a new hash table. * @@ -136,6 +136,48 @@ 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 + * - 0 if added successfully + * - -EINVAL if the parameters are invalid. + * - -ENOSPC if there is no space in the hash for this key. + */ +int +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 + * - 0 if added successfully + * - -EINVAL if the parameters are invalid. + * - -ENOSPC if there is no space in the hash 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. * @@ -212,6 +254,47 @@ 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 + * Output with pointer to data returned from the hash table. + * @return + * 0 if successful lookup + * - EINVAL if the parameters are invalid. + * - ENOENT if the key is not found. + */ +int +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 + * Output with pointer to data returned from the hash table. + * @return + * 0 if successful lookup + * - EINVAL if the parameters are invalid. + * - ENOENT if the key is not found. + */ +int +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. @@ -266,6 +349,28 @@ 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 +/** + * 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 hit_mask + * Output containing a bitmask with all successful lookups. + * @param data + * Output containing array of data returned from all the successful lookups. + * @return + * -EINVAL if there's an error, otherwise number of successful lookups. + */ +int +rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys, + uint32_t num_keys, uint64_t *hit_mask, uintptr_t data[]); + /** * Find multiple keys in the hash table. * This operation is multi-thread safe. @@ -288,7 +393,6 @@ rte_hash_hash(const struct rte_hash *h, const void *key); int rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, uint32_t num_keys, int32_t *positions); - #ifdef __cplusplus } #endif diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map index d5f5af5..a97eac1 100644 --- a/lib/librte_hash/rte_hash_version.map +++ b/lib/librte_hash/rte_hash_version.map @@ -22,6 +22,12 @@ DPDK_2.0 { DPDK_2.1 { global: + rte_hash_add_key_data; + rte_hash_add_key_with_hash_data; + rte_hash_create; + rte_hash_lookup_bulk_data; + rte_hash_lookup_data; + rte_hash_lookup_with_hash_data; rte_hash_reset; local: *; -- 2.4.2