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 3CF43C502 for ; Mon, 29 Jun 2015 00:25:34 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga102.fm.intel.com with ESMTP; 28 Jun 2015 15:25:32 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,695,1427785200"; d="scan'208";a="515624876" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by FMSMGA003.fm.intel.com with ESMTP; 28 Jun 2015 15:25:32 -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 t5SMPUEF030629; Sun, 28 Jun 2015 23:25:30 +0100 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t5SMPUEQ010223; Sun, 28 Jun 2015 23:25:30 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t5SMPUNl010219; Sun, 28 Jun 2015 23:25:30 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Sun, 28 Jun 2015 23:25:27 +0100 Message-Id: <1435530330-10132-9-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1435269919-7007-1-git-send-email-pablo.de.lara.guarch@intel.com> <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH v3 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: Sun, 28 Jun 2015 22:25:34 -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. Unit tests have been updated to use these new functions. Signed-off-by: Pablo de Lara --- app/test/Makefile | 1 + app/test/test_hash_perf.c | 246 ++++++++++++++++++++--------------- lib/librte_hash/rte_cuckoo_hash.c | 167 +++++++++++++++++++----- lib/librte_hash/rte_hash.h | 145 ++++++++++++++++++++- lib/librte_hash/rte_hash_version.map | 6 + 5 files changed, 424 insertions(+), 141 deletions(-) diff --git a/app/test/Makefile b/app/test/Makefile index 2e2758c..5481ca1 100644 --- a/app/test/Makefile +++ b/app/test/Makefile @@ -83,6 +83,7 @@ SRCS-y += test_memcpy_perf.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_perf.c +SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_cuckoo_hash_perf.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_functions.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_scaling.c diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c index 6e8b255..2fcb9a6 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, @@ -75,7 +76,7 @@ struct rte_hash *h[NUM_KEYSIZES]; /* Array that stores if a slot is full */ 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]; /* Array to store the precomputed hash for 'keys' */ @@ -92,11 +93,19 @@ 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) { + sprintf(name, "test_hash%d_data", hashtest_key_lens[table_index]); + /* Table will store 8-byte data */ + ut_params.data_len = sizeof(uint64_t); + } else { + sprintf(name, "test_hash%d", hashtest_key_lens[table_index]); + ut_params.data_len = 0; + } + ut_params.name = name; ut_params.key_len = hashtest_key_lens[table_index]; ut_params.socket_id = rte_socket_id(); @@ -228,15 +237,25 @@ get_input_keys(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(); + uint64_t data; for (i = 0; i < KEYS_TO_ADD; i++) { - if (with_hash) + data = signatures[i] * DATA_MULTIPLIER; + if (with_hash && with_data) + rte_hash_add_key_with_hash_data(h[table_index], + (const void *) keys[i], + signatures[i], &data); + else if (with_hash && !with_data) rte_hash_add_key_with_hash(h[table_index], (const void *) keys[i], signatures[i]); + else if (!with_hash && with_data) + rte_hash_add_key_data(h[table_index], + (const void *) keys[i], + &data); else rte_hash_add_key(h[table_index], keys[i]); } @@ -245,29 +264,38 @@ timed_adds(unsigned with_hash, unsigned table_index) { const uint64_t time_taken = end_tsc - start_tsc; const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); - cycles[table_index][ADD][with_hash] = time_taken/KEYS_TO_ADD; + cycles[table_index][ADD][with_hash][with_data] = time_taken/KEYS_TO_ADD; printf("\n%"PRIu64" adds in %f seconds\n", (uint64_t)KEYS_TO_ADD, seconds_taken); printf("Average %"PRIu64" tsc ticks per add\n", - cycles[table_index][ADD][with_hash]); + cycles[table_index][ADD][with_hash][with_data]); printf("Average %"PRIu64" adds per second\n", (KEYS_TO_ADD * rte_get_tsc_hz())/time_taken); 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(); + uint64_t ret_data; 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) + rte_hash_lookup_with_hash_data(h[table_index], + (const void *) keys[j], + signatures[j], &ret_data); + else if (with_hash && !with_data) rte_hash_lookup_with_hash(h[table_index], (const void *) keys[j], signatures[j]); + else if (!with_hash && with_data) + rte_hash_lookup_data(h[table_index], + (const void *) keys[j], + &ret_data); else rte_hash_lookup(h[table_index], keys[j]); } @@ -277,23 +305,29 @@ timed_lookups(unsigned with_hash, unsigned table_index) const uint64_t time_taken = end_tsc - start_tsc; const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); - cycles[table_index][LOOKUP][with_hash] = time_taken/NUM_LOOKUPS; + cycles[table_index][LOOKUP][with_hash][with_data] = time_taken/NUM_LOOKUPS; printf("%"PRIu64" lookups in %f seconds\n", (uint64_t) NUM_LOOKUPS, seconds_taken); printf("Average %"PRIu64" tsc ticks per lookup\n", - cycles[table_index][LOOKUP][with_hash]); + cycles[table_index][LOOKUP][with_hash][with_data]); printf("Average %"PRIu64" lookups per second\n", (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken); return 0; } static int -timed_lookups_multi(unsigned with_hash, unsigned table_index) +timed_lookups_multi(unsigned with_hash, unsigned with_data, unsigned table_index) { unsigned i, j, k; int32_t positions_burst[BURST_SIZE]; const void *keys_burst[BURST_SIZE]; + uint64_t ret_data[BURST_SIZE]; + void *data_ptrs[BURST_SIZE]; + + for (i = 0; i < BURST_SIZE; i++) + data_ptrs[i] = &ret_data[i]; + const uint64_t start_tsc = rte_rdtsc(); hash_sig_t *hash_array; @@ -301,18 +335,32 @@ timed_lookups_multi(unsigned with_hash, unsigned table_index) 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]; - if (with_hash) { + if (with_hash && with_data) { + hash_array = &signatures[j * BURST_SIZE]; + rte_hash_lookup_bulk_with_hash_data(h[table_index], + (const void **) keys_burst, + (const hash_sig_t *) hash_array, + BURST_SIZE, + positions_burst, + data_ptrs); + } else if (with_hash && !with_data) { hash_array = &signatures[j * BURST_SIZE]; rte_hash_lookup_bulk_with_hash(h[table_index], - (const void **) keys_burst, - (const hash_sig_t *) hash_array, - BURST_SIZE, - positions_burst); - } else + (const void **) keys_burst, + (const hash_sig_t *) hash_array, + BURST_SIZE, + positions_burst); + } else if (!with_hash && with_data) + rte_hash_lookup_bulk_data(h[table_index], + (const void **) keys_burst, + BURST_SIZE, + positions_burst, + data_ptrs); + else rte_hash_lookup_bulk(h[table_index], - (const void **) keys_burst, - BURST_SIZE, - positions_burst); + (const void **) keys_burst, + BURST_SIZE, + positions_burst); } } @@ -320,24 +368,25 @@ timed_lookups_multi(unsigned with_hash, unsigned table_index) const uint64_t time_taken = end_tsc - start_tsc; const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); - cycles[table_index][LOOKUP_MULTI][with_hash] = time_taken/NUM_LOOKUPS; + cycles[table_index][LOOKUP_MULTI][with_hash][with_data] = time_taken/NUM_LOOKUPS; printf("%"PRIu64" lookups in %f seconds\n", (uint64_t)NUM_LOOKUPS, seconds_taken); printf("Average %"PRIu64" tsc ticks per lookup\n", - cycles[table_index][LOOKUP_MULTI][with_hash]); + cycles[table_index][LOOKUP_MULTI][with_hash][with_data]); printf("Average %"PRIu64" lookups per second\n", (NUM_LOOKUPS * rte_get_tsc_hz())/time_taken); 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(); for (i = 0; i < KEYS_TO_ADD; i++) { + /* There are no delete functions with data, so just call two functions */ if (with_hash) rte_hash_del_key_with_hash(h[table_index], (const void *) keys[i], @@ -351,12 +400,12 @@ timed_deletes(unsigned with_hash, unsigned table_index) const uint64_t time_taken = end_tsc - start_tsc; const float seconds_taken = (float)time_taken/rte_get_tsc_hz(); - cycles[table_index][DELETE][with_hash] = time_taken/KEYS_TO_ADD; + cycles[table_index][DELETE][with_hash][with_data] = time_taken/KEYS_TO_ADD; printf("\n%"PRIu64" deletions in %f seconds\n", (uint64_t) KEYS_TO_ADD, seconds_taken); printf("Average %"PRIu64" tsc ticks per deletion\n", - cycles[table_index][DELETE][with_hash]); + cycles[table_index][DELETE][with_hash][with_data]); printf("Average %"PRIu64" deletions per second\n", (KEYS_TO_ADD * rte_get_tsc_hz())/time_taken); return 0; @@ -377,93 +426,80 @@ reset_table(unsigned table_index) static int run_all_tbl_perf_tests(void) { - unsigned i, j; - - for (i = 0; i < NUM_KEYSIZES; i++) { - if (create_table(i) < 0) - return -1; - - if (get_input_keys(i) < 0) - return -1; - - printf("\n------ KEY SIZE = %u ----------\n\n", - hashtest_key_lens[i]); - printf("\n ----- WITH PRECOMPUTED HASH VALUES -----\n\n"); - - printf("\nTimed additions\n"); - printf("------------------\n"); - if (timed_adds(1, i) < 0) - return -1; - - for (j = 0; j < NUM_SHUFFLES; j++) - shuffle_input_keys(i); - - printf("\nTimed lookups\n"); - printf("------------------\n"); - if (timed_lookups(1, i) < 0) - return -1; - - printf("\nTimed lookups multi\n"); - printf("------------------\n"); - if (timed_lookups_multi(1, i) < 0) - return -1; + unsigned i, j, with_data, with_hash; - printf("\nTimed deletions\n"); - printf("------------------\n"); - if (timed_deletes(1, i) < 0) - return -1; - - reset_table(i); - - printf("\n ----- WITH JUST KEYS -----\n\n"); - - printf("\nTimed additions\n"); - printf("------------------\n"); - if (timed_adds(0, i) < 0) - return -1; - - for (j = 0; j < NUM_SHUFFLES; j++) - shuffle_input_keys(i); - - printf("\nTimed lookups\n"); - printf("------------------\n"); - if (timed_lookups(0, i) < 0) - return -1; - - printf("\nTimed lookups multi\n"); - printf("------------------\n"); - if (timed_lookups_multi(0, i) < 0) - return -1; - - printf("\nTimed deletions\n"); - printf("------------------\n"); - if (timed_deletes(0, i) < 0) - return -1; + 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 (i = 0; i < NUM_KEYSIZES; i++) { + printf("\n--------- KEY SIZE = %u ---------\n\n", + hashtest_key_lens[i]); + if (create_table(with_data, i) < 0) + return -1; + + if (get_input_keys(i) < 0) + return -1; + for (with_hash = 0; with_hash <= 1; with_hash++) { + if (with_hash) + printf("\n--- WITH PRECOMPUTED HASH VALUES ---\n\n"); + else + printf("\n--- WITH JUST KEYS ---\n\n"); + + printf("\nTimed additions\n"); + printf("------------------\n"); + if (timed_adds(with_hash, with_data, i) < 0) + return -1; + + for (j = 0; j < NUM_SHUFFLES; j++) + shuffle_input_keys(i); + + printf("\nTimed lookups\n"); + printf("------------------\n"); + if (timed_lookups(with_hash, with_data, i) < 0) + return -1; + + printf("\nTimed lookups multi\n"); + printf("------------------\n"); + if (timed_lookups_multi(with_hash, with_data, i) < 0) + return -1; + + printf("\nTimed deletions\n"); + printf("------------------\n"); + if (timed_deletes(with_hash, with_data, i) < 0) + return -1; + + reset_table(i); + } - free_table(i); + free_table(i); + } } printf("\nResults (in CPU cycles/operation)\n"); printf("-----------------------------------\n"); - printf("\nWith precomputed hash\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"); - } - printf("\nWith just keys\n"); - printf("\n%-18s%-18s%-18s%-18s%-18s\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 precomputed hash\n"); + else + printf("\nWith just keys\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"); + 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; } diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index 44f87fb..ad8ac9b 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -84,7 +84,9 @@ EAL_REGISTER_TAILQ(rte_hash_tailq) #define DEFAULT_HASH_FUNC rte_jhash #endif -#define NULL_SIGNATURE 0 +#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); @@ -101,6 +103,7 @@ struct rte_hash { char name[RTE_HASH_NAMESIZE]; /**< Name of the hash. */ uint32_t entries; /**< Total table entries. */ uint16_t key_len; /**< Length of hash key. */ + uint16_t data_len; /**< Length of data. */ rte_hash_function hash_func; /**< Function used to calculate hash. */ rte_hash_cmp_eq_t rte_hash_cmp_eq; /**< Function used to compare keys. */ uint32_t hash_func_init_val; /**< Init value used by hash_func. */ @@ -170,6 +173,7 @@ rte_hash_create(const struct rte_hash_parameters *params) void *ptr, *k = NULL; char ring_name[RTE_RING_NAMESIZE]; unsigned i; + uint32_t key_entry_size; hash_list = RTE_TAILQ_CAST(rte_hash_tailq.head, rte_hash_list); @@ -202,7 +206,12 @@ 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 uint32_t key_entry_size = params->key_len; + /* If key size is multiple of KEY_ALIGNMENT, need to align for fast comparison */ + if ((params->key_len % KEY_ALIGNMENT) == 0) + key_entry_size = RTE_ALIGN(params->key_len + params->data_len, KEY_ALIGNMENT); + else + key_entry_size = params->key_len + params->data_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); @@ -277,6 +286,7 @@ rte_hash_create(const struct rte_hash_parameters *params) snprintf(h->name, sizeof(h->name), "%s", params->name); h->entries = params->entries; h->key_len = params->key_len; + h->data_len = params->data_len; h->key_entry_size = key_entry_size; h->hash_func_init_val = params->hash_func_init_val; @@ -481,14 +491,14 @@ 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, const void *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; - void *slot_id; + void *slot_id, *data_entry; int ret; /* Get a new slot for storing the new key */ @@ -512,6 +522,11 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, 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)) { + if (data != NULL) { + data_entry = (char *) k + h->key_len; + /* Update data */ + rte_memcpy(data_entry, data, h->data_len); + } rte_ring_sp_enqueue(h->free_slots, &slot_id); /* * Return index where key is stored, @@ -528,6 +543,11 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, 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)) { + if (data != NULL) { + data_entry = (char *) k + h->key_len; + /* Update data */ + rte_memcpy(data_entry, data, h->data_len); + } rte_ring_sp_enqueue(h->free_slots, &slot_id); /* * Return index where key is stored, @@ -540,6 +560,11 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, /* Copy key */ rte_memcpy(new_k, key, h->key_len); + if (data != NULL) { + data_entry = (char *) new_k + h->key_len; + /* Copy data */ + rte_memcpy(data_entry, data, h->data_len); + } /* * Run cuckoo algorithm @@ -570,19 +595,33 @@ 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); } +int32_t +rte_hash_add_key_with_hash_data(const struct rte_hash *h, + const void *key, hash_sig_t sig, const void *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, const void *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, void *data) { uint32_t bucket_idx; hash_sig_t alt_hash; @@ -598,12 +637,19 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, 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)) + if (!h->rte_hash_cmp_eq(key, k, h->key_len)) { + if (data != NULL) { + const void *data_entry = (char *) k + h->key_len; + /* Return data */ + rte_memcpy(data, data_entry, h->data_len); + } + /* * Return index where key is stored, * substracting the first dummy index */ return (bkt->key_idx[i] - 1); + } } } @@ -617,12 +663,18 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, 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)) + if (!h->rte_hash_cmp_eq(key, k, h->key_len)) { + if (data != NULL) { + const void *data_entry = (char *) k + h->key_len; + /* Return data */ + rte_memcpy(data, data_entry, h->data_len); + } /* * Return index where key is stored, * substracting the first dummy index */ return (bkt->key_idx[i] - 1); + } } } @@ -634,16 +686,30 @@ 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); +} + +int32_t +rte_hash_lookup_with_hash_data(const struct rte_hash *h, + const void *key, hash_sig_t sig, void *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, void *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 __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig) @@ -806,23 +872,30 @@ 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, int32_t *positions, +lookup_stage3(unsigned idx, const void *key_slot, const void * const *keys, + void * const *data, 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 (unlikely(hit == 0)) + if (unlikely(hit == 0)) { positions[idx] = -ENOENT; + return; + } + if (data != NULL) { + const void *data_entry = (const char *) key_slot + h->key_len; + + rte_memcpy(data[idx], data_entry, h->data_len); + } *hits = (uint64_t)(hit) << idx; } static inline int __rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, - uint32_t num_keys, int32_t *positions) { + uint32_t num_keys, int32_t *positions, void **data) { uint64_t hits = 0; uint64_t next_mask = 0; @@ -931,8 +1004,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, keys, data, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, positions, &hits, h); } k_slot30 = k_slot20, k_slot31 = k_slot21; @@ -961,8 +1034,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, keys, data, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, positions, &hits, h); k_slot30 = k_slot20, k_slot31 = k_slot21; idx30 = idx20, idx31 = idx21; @@ -982,14 +1055,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, keys, data, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, 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, keys, data, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, positions, &hits, h); /* handle extra_hits_mask */ next_mask |= extra_hits_mask; @@ -1012,7 +1085,7 @@ __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, void **data) { uint64_t hits = 0; uint64_t next_mask = 0; @@ -1121,8 +1194,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, keys, data, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, positions, &hits, h); } k_slot30 = k_slot20, k_slot31 = k_slot21; @@ -1152,8 +1225,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, keys, data, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, positions, &hits, h); k_slot30 = k_slot20, k_slot31 = k_slot21; idx30 = idx20, idx31 = idx21; @@ -1173,14 +1246,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, keys, data, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, 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, keys, data, positions, &hits, h); + lookup_stage3(idx31, k_slot31, keys, data, positions, &hits, h); /* handle extra_hits_mask */ next_mask |= extra_hits_mask; @@ -1209,7 +1282,7 @@ 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 @@ -1222,7 +1295,31 @@ 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); +} + +int +rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys, + uint32_t num_keys, int32_t *positions, void **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_with_hash_data(const struct rte_hash *h, const void **keys, + const hash_sig_t *hash_vals, uint32_t num_keys, + int32_t *positions, void **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); } /* 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..e917fea 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -84,12 +84,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. */ + uint32_t data_len; /**< Length of data. */ }; /** @internal A hash table structure. */ struct rte_hash; - /** * Create a new hash table. * @@ -140,6 +140,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, const void *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, const void *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 +260,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, void *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, void *data); + /** * Find a key in the hash table. * This operation is multi-thread safe. @@ -270,7 +359,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, void **data); + /** * Find multiple keys in the hash table. * This operation is multi-thread safe. @@ -303,6 +419,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, void **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