From 1a9f648be2911b8890c03a8be25842587f3fa885 Mon Sep 17 00:00:00 2001 From: Intel Date: Mon, 3 Jun 2013 00:00:00 +0000 Subject: [PATCH] hash: fix for multi-process apps Signed-off-by: Intel --- app/test/test_hash.c | 48 +++++++++++++++--- app/test/test_hash_perf.c | 14 +++--- lib/librte_hash/rte_fbk_hash.h | 85 +++++++++++++++++++++++++++----- lib/librte_hash/rte_hash.c | 80 ++++++++++++++++++++++-------- lib/librte_hash/rte_hash.h | 89 ++++++++++++++++++++++++++++++++-- 5 files changed, 268 insertions(+), 48 deletions(-) diff --git a/app/test/test_hash.c b/app/test/test_hash.c index 5437e05b36..7e7d031c54 100644 --- a/app/test/test_hash.c +++ b/app/test/test_hash.c @@ -50,6 +50,11 @@ #include #include #include +#include + +#include "test.h" + +#ifdef RTE_LIBRTE_HASH #include #include @@ -58,11 +63,6 @@ #ifdef RTE_MACHINE_CPUFLAG_SSE4_2 #include #endif -#include - -#include "test.h" - -#ifdef RTE_LIBRTE_HASH /******************************************************************************* * Hash function performance test configuration section. Each performance test @@ -242,6 +242,7 @@ static void run_hash_func_tests(void) static int test_add_delete(void) { struct rte_hash *handle; + /* test with standard add/lookup/delete functions */ int pos0, expectedPos0; ut_params.name = "test1"; @@ -269,6 +270,37 @@ static int test_add_delete(void) "fail: found key after deleting! (pos0=%d)", pos0); rte_hash_free(handle); + + /* repeat test with precomputed hash functions */ + hash_sig_t hash_value; + int pos1, expectedPos1; + + handle = rte_hash_create(&ut_params); + RETURN_IF_ERROR(handle == NULL, "hash creation failed"); + + hash_value = rte_hash_hash(handle, &keys[0]); + pos1 = rte_hash_add_key_with_hash(handle, &keys[0], hash_value); + print_key_info("Add", &keys[0], pos1); + RETURN_IF_ERROR(pos1 < 0, "failed to add key (pos1=%d)", pos1); + expectedPos1 = pos1; + + pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value); + print_key_info("Lkp", &keys[0], pos1); + RETURN_IF_ERROR(pos1 != expectedPos1, + "failed to find key (pos1=%d)", pos1); + + pos1 = rte_hash_del_key_with_hash(handle, &keys[0], hash_value); + print_key_info("Del", &keys[0], pos1); + RETURN_IF_ERROR(pos1 != expectedPos1, + "failed to delete key (pos1=%d)", pos1); + + pos1 = rte_hash_lookup_with_hash(handle, &keys[0], hash_value); + print_key_info("Lkp", &keys[0], pos1); + RETURN_IF_ERROR(pos1 != -ENOENT, + "fail: found key after deleting! (pos1=%d)", pos1); + + rte_hash_free(handle); + return 0; } @@ -707,6 +739,8 @@ fbk_hash_unit_test(void) double used_entries; /* Try creating hashes with invalid parameters */ + printf("# Testing hash creation with invalid parameters " + "- expert error msgs\n"); handle = rte_fbk_hash_create(&invalid_params_1); RETURN_IF_ERROR_FBK(handle != NULL, "fbk hash creation should have failed"); @@ -1334,7 +1368,7 @@ int test_hash(void) return 0; } -#else +#else /* RTE_LIBRTE_HASH */ int test_hash(void) @@ -1343,4 +1377,4 @@ test_hash(void) return 0; } -#endif +#endif /* RTE_LIBRTE_HASH */ diff --git a/app/test/test_hash_perf.c b/app/test/test_hash_perf.c index 8a0feb302b..bfd05a7fce 100644 --- a/app/test/test_hash_perf.c +++ b/app/test/test_hash_perf.c @@ -51,6 +51,11 @@ #include #include #include +#include + +#include "test.h" + +#ifdef RTE_LIBRTE_HASH #include #include @@ -59,11 +64,6 @@ #ifdef RTE_MACHINE_CPUFLAG_SSE4_2 #include #endif -#include - -#include "test.h" - -#ifdef RTE_LIBRTE_HASH /* Types of hash table performance test that can be performed */ enum hash_test_t { @@ -773,7 +773,7 @@ int test_hash_perf(void) return -1; return 0; } -#else +#else /* RTE_LIBRTE_HASH */ int test_hash_perf(void) @@ -782,4 +782,4 @@ test_hash_perf(void) return 0; } -#endif +#endif /* RTE_LIBRTE_HASH */ diff --git a/lib/librte_hash/rte_fbk_hash.h b/lib/librte_hash/rte_fbk_hash.h index 93160b2584..6cd048e7e9 100644 --- a/lib/librte_hash/rte_fbk_hash.h +++ b/lib/librte_hash/rte_fbk_hash.h @@ -139,9 +139,9 @@ rte_fbk_hash_get_bucket(const struct rte_fbk_hash_table *ht, uint32_t key) ht->bucket_shift; } - /** - * Add a key to an existing hash table. This operation is not multi-thread safe + * Add a key to an existing hash table with bucket id. + * This operation is not multi-thread safe * and should only be called from one thread. * * @param ht @@ -150,12 +150,14 @@ rte_fbk_hash_get_bucket(const struct rte_fbk_hash_table *ht, uint32_t key) * Key to add to the hash table. * @param value * Value to associate with key. + * @param bucket + * Bucket to associate with key. * @return * 0 if ok, or negative value on error. */ static inline int -rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, - uint32_t key, uint16_t value) +rte_fbk_hash_add_key_with_bucket(struct rte_fbk_hash_table *ht, + uint32_t key, uint16_t value, uint32_t bucket) { /* * The writing of a new value to the hash table is done as a single @@ -166,7 +168,6 @@ rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, const uint64_t new_entry = ((uint64_t)(key) << 32) | ((uint64_t)(value) << 16) | 1; /* 1 = is_entry bit. */ - const uint32_t bucket = rte_fbk_hash_get_bucket(ht, key); uint32_t i; for (i = 0; i < ht->entries_per_bucket; i++) { @@ -187,20 +188,44 @@ rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, } /** - * Remove a key from an existing hash table. This operation is not multi-thread + * Add a key to an existing hash table. This operation is not multi-thread safe + * and should only be called from one thread. + * + * @param ht + * Hash table to add the key to. + * @param key + * Key to add to the hash table. + * @param value + * Value to associate with key. + * @return + * 0 if ok, or negative value on error. + */ +static inline int +rte_fbk_hash_add_key(struct rte_fbk_hash_table *ht, + uint32_t key, uint16_t value) +{ + return rte_fbk_hash_add_key_with_bucket(ht, + key, value, rte_fbk_hash_get_bucket(ht, key)); +} + +/** + * Remove a key with a given bucket id from an existing hash table. + * This operation is not multi-thread * safe and should only be called from one thread. * * @param ht * Hash table to remove the key from. * @param key * Key to remove from the hash table. + * @param bucket + * Bucket id associate with key. * @return * 0 if ok, or negative value on error. */ static inline int -rte_fbk_hash_delete_key(struct rte_fbk_hash_table *ht, uint32_t key) +rte_fbk_hash_delete_key_with_bucket(struct rte_fbk_hash_table *ht, + uint32_t key, uint32_t bucket) { - const uint32_t bucket = rte_fbk_hash_get_bucket(ht, key); uint32_t last_entry = ht->entries_per_bucket - 1; uint32_t i, j; @@ -230,19 +255,40 @@ rte_fbk_hash_delete_key(struct rte_fbk_hash_table *ht, uint32_t key) } /** - * Find a key in the hash table. This operation is multi-thread safe. + * Remove a key from an existing hash table. This operation is not multi-thread + * safe and should only be called from one thread. + * + * @param ht + * Hash table to remove the key from. + * @param key + * Key to remove from the hash table. + * @return + * 0 if ok, or negative value on error. + */ +static inline int +rte_fbk_hash_delete_key(struct rte_fbk_hash_table *ht, uint32_t key) +{ + return rte_fbk_hash_delete_key_with_bucket(ht, + key, rte_fbk_hash_get_bucket(ht, key)); +} + +/** + * Find a key in the hash table with a given bucketid. + * This operation is multi-thread safe. * * @param ht * Hash table to look in. * @param key * Key to find. + * @param bucket + * Bucket associate to the key. * @return * The value that was associated with the key, or negative value on error. */ static inline int -rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key) +rte_fbk_hash_lookup_with_bucket(const struct rte_fbk_hash_table *ht, + uint32_t key, uint32_t bucket) { - const uint32_t bucket = rte_fbk_hash_get_bucket(ht, key); union rte_fbk_hash_entry current_entry; uint32_t i; @@ -259,6 +305,23 @@ rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key) return -ENOENT; /* Key didn't exist. */ } +/** + * Find a key in the hash table. This operation is multi-thread safe. + * + * @param ht + * Hash table to look in. + * @param key + * Key to find. + * @return + * The value that was associated with the key, or negative value on error. + */ +static inline int +rte_fbk_hash_lookup(const struct rte_fbk_hash_table *ht, uint32_t key) +{ + return rte_fbk_hash_lookup_with_bucket(ht, + key, rte_fbk_hash_get_bucket(ht, key)); +} + /** * Delete all entries in a hash table. This operation is not multi-thread * safe and should only be called from one thread. diff --git a/lib/librte_hash/rte_hash.c b/lib/librte_hash/rte_hash.c index d8d2dfde9f..5ff8d69e21 100644 --- a/lib/librte_hash/rte_hash.c +++ b/lib/librte_hash/rte_hash.c @@ -261,18 +261,17 @@ rte_hash_free(struct rte_hash *h) rte_free(h); } -int32_t -rte_hash_add_key(const struct rte_hash *h, const void *key) +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, *sig_bucket; + hash_sig_t *sig_bucket; uint8_t *key_bucket; uint32_t bucket_index, i; int32_t pos; - RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); - /* Get the hash signature and bucket index */ - sig = h->hash_func(key, h->key_len, h->hash_func_init_val) | h->sig_msb; + sig |= h->sig_msb; bucket_index = sig & h->bucket_bitmask; sig_bucket = get_sig_tbl_bucket(h, bucket_index); key_bucket = get_key_tbl_bucket(h, bucket_index); @@ -299,16 +298,30 @@ rte_hash_add_key(const struct rte_hash *h, const void *key) } int32_t -rte_hash_del_key(const struct rte_hash *h, const void *key) +rte_hash_add_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) { - hash_sig_t sig, *sig_bucket; - uint8_t *key_bucket; - uint32_t bucket_index, i; + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_add_key_with_hash(h, key, sig); +} +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)); +} + +static inline int32_t +__rte_hash_del_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + hash_sig_t *sig_bucket; + uint8_t *key_bucket; + uint32_t bucket_index, i; /* Get the hash signature and bucket index */ - sig = h->hash_func(key, h->key_len, h->hash_func_init_val) | h->sig_msb; + sig = sig | h->sig_msb; bucket_index = sig & h->bucket_bitmask; sig_bucket = get_sig_tbl_bucket(h, bucket_index); key_bucket = get_key_tbl_bucket(h, bucket_index); @@ -327,16 +340,30 @@ rte_hash_del_key(const struct rte_hash *h, const void *key) } int32_t -rte_hash_lookup(const struct rte_hash *h, const void *key) +rte_hash_del_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) { - hash_sig_t sig, *sig_bucket; - uint8_t *key_bucket; - uint32_t bucket_index, i; + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_del_key_with_hash(h, key, sig); +} +int32_t +rte_hash_del_key(const struct rte_hash *h, const void *key) +{ RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key)); +} + +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_bucket; + uint8_t *key_bucket; + uint32_t bucket_index, i; /* Get the hash signature and bucket index */ - sig = h->hash_func(key, h->key_len, h->hash_func_init_val) | h->sig_msb; + sig |= h->sig_msb; bucket_index = sig & h->bucket_bitmask; sig_bucket = get_sig_tbl_bucket(h, bucket_index); key_bucket = get_key_tbl_bucket(h, bucket_index); @@ -353,15 +380,30 @@ rte_hash_lookup(const struct rte_hash *h, const void *key) return -ENOENT; } +int32_t +rte_hash_lookup_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig) +{ + RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); + return __rte_hash_lookup_with_hash(h, key, sig); +} + +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)); +} + int -rte_hash_lookup_multi(const struct rte_hash *h, const void **keys, +rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, uint32_t num_keys, int32_t *positions) { uint32_t i, j, bucket_index; - hash_sig_t sigs[RTE_HASH_LOOKUP_MULTI_MAX]; + hash_sig_t sigs[RTE_HASH_LOOKUP_BULK_MAX]; RETURN_IF_TRUE(((h == NULL) || (keys == NULL) || (num_keys == 0) || - (num_keys > RTE_HASH_LOOKUP_MULTI_MAX) || + (num_keys > RTE_HASH_LOOKUP_BULK_MAX) || (positions == NULL)), -EINVAL); /* Get the hash signature and bucket index */ diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index de500f5ed7..bf39d33089 100644 --- a/lib/librte_hash/rte_hash.h +++ b/lib/librte_hash/rte_hash.h @@ -58,7 +58,8 @@ extern "C" { #define RTE_HASH_KEY_LENGTH_MAX 64 /** Max number of keys that can be searched for using rte_hash_lookup_multi. */ -#define RTE_HASH_LOOKUP_MULTI_MAX 16 +#define RTE_HASH_LOOKUP_BULK_MAX 16 +#define RTE_HASH_LOOKUP_MULTI_MAX RTE_HASH_LOOKUP_BULK_MAX /** Max number of characters in hash name.*/ #define RTE_HASH_NAMESIZE 32 @@ -168,6 +169,26 @@ rte_hash_free(struct rte_hash *h); int32_t rte_hash_add_key(const struct rte_hash *h, const void *key); +/** + * Add a key 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 + * Hash value 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(const struct rte_hash *h, + const void *key, hash_sig_t sig); + /** * Remove a key from an existing hash table. This operation is not multi-thread * safe and should only be called from one thread. @@ -186,6 +207,28 @@ rte_hash_add_key(const struct rte_hash *h, const void *key); int32_t rte_hash_del_key(const struct rte_hash *h, const void *key); +/** + * Remove a key from an existing hash table. This operation is not multi-thread + * safe and should only be called from one thread. + * + * @param h + * Hash table to remove the key from. + * @param key + * Key to remove from the hash table. + * @param sig + * Hash value to remove 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_del_key_with_hash(const struct rte_hash *h, + const void *key, hash_sig_t sig); + + /** * Find a key in the hash table. This operation is multi-thread safe. * @@ -203,6 +246,45 @@ rte_hash_del_key(const struct rte_hash *h, const void *key); int32_t rte_hash_lookup(const struct rte_hash *h, const void *key); +/** + * Find a key in the hash table. This operation is multi-thread safe. + * + * @param h + * Hash table to look in. + * @param key + * Key to find. + * @param sig + * Hash value to find. + * @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(const struct rte_hash *h, + const void *key, hash_sig_t sig); + + +/** + * Calc a hash value by key. This operation is not multi-process safe. + * + * @param h + * Hash table to look in. + * @param key + * Key to find. + * @return + * - hash value + */ +static inline hash_sig_t +rte_hash_hash(const struct rte_hash *h, const void *key) +{ + /* calc hash result by key */ + return h->hash_func(key, h->key_len, h->hash_func_init_val); +} + +#define rte_hash_lookup_multi rte_hash_lookup_bulk /** * Find multiple keys in the hash table. This operation is multi-thread safe. * @@ -211,7 +293,7 @@ rte_hash_lookup(const struct rte_hash *h, const void *key); * @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_MULTI_MAX). + * 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 @@ -222,9 +304,8 @@ rte_hash_lookup(const struct rte_hash *h, const void *key); * -EINVAL if there's an error, otherwise 0. */ int -rte_hash_lookup_multi(const struct rte_hash *h, const void **keys, +rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys, uint32_t num_keys, int32_t *positions); - #ifdef __cplusplus } #endif -- 2.20.1