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
