[dpdk-dev] [PATCH v3 08/11] hash: add new functionality to store data in hash table
Pablo de Lara
pablo.de.lara.guarch at intel.com
Mon Jun 29 00:25:27 CEST 2015
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 <pablo.de.lara.guarch at intel.com>
---
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
More information about the dev
mailing list