@@ -140,6 +140,7 @@ rte_hash_create(const struct rte_hash_parameters *params)
unsigned int ext_table_support = 0;
unsigned int readwrite_concur_support = 0;
unsigned int writer_takes_lock = 0;
+ unsigned int no_free_on_del = 0;
rte_hash_function default_hash_func = (rte_hash_function)rte_jhash;
@@ -176,6 +177,9 @@ rte_hash_create(const struct rte_hash_parameters *params)
if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_EXT_TABLE)
ext_table_support = 1;
+ if (params->extra_flag & RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL)
+ no_free_on_del = 1;
+
/* Store all keys and leave the first entry as a dummy entry for lookup_bulk */
if (use_local_cache)
/*
@@ -359,6 +363,7 @@ rte_hash_create(const struct rte_hash_parameters *params)
h->readwrite_concur_support = readwrite_concur_support;
h->ext_table_support = ext_table_support;
h->writer_takes_lock = writer_takes_lock;
+ h->no_free_on_del = no_free_on_del;
#if defined(RTE_ARCH_X86)
if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_SSE2))
@@ -1121,7 +1126,6 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i)
unsigned lcore_id, n_slots;
struct lcore_cache *cached_free_slots;
- bkt->sig_current[i] = NULL_SIGNATURE;
if (h->use_local_cache) {
lcore_id = rte_lcore_id();
cached_free_slots = &h->local_free_slots[lcore_id];
@@ -1183,7 +1187,12 @@ search_and_remove(const struct rte_hash *h, const void *key,
k = (struct rte_hash_key *) ((char *)keys +
bkt->key_idx[i] * h->key_entry_size);
if (rte_hash_cmp_eq(key, k->key, h) == 0) {
- remove_entry(h, bkt, i);
+ bkt->sig_current[i] = NULL_SIGNATURE;
+ /* Free the key store index if
+ * no_free_on_del is disabled.
+ */
+ if (!h->no_free_on_del)
+ remove_entry(h, bkt, i);
/* Return index where key is stored,
* subtracting the first dummy index
@@ -1301,6 +1310,43 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
return 0;
}
+int __rte_experimental
+rte_hash_free_key_with_position(const struct rte_hash *h,
+ const int32_t position)
+{
+ RETURN_IF_TRUE(((h == NULL) || (position == EMPTY_SLOT)), -EINVAL);
+
+ unsigned int lcore_id, n_slots;
+ struct lcore_cache *cached_free_slots;
+ const int32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
+
+ /* Out of bounds */
+ if (position >= total_entries)
+ return -EINVAL;
+
+ if (h->use_local_cache) {
+ lcore_id = rte_lcore_id();
+ cached_free_slots = &h->local_free_slots[lcore_id];
+ /* Cache full, need to free it. */
+ if (cached_free_slots->len == LCORE_CACHE_SIZE) {
+ /* Need to enqueue the free slots in global ring. */
+ n_slots = rte_ring_mp_enqueue_burst(h->free_slots,
+ cached_free_slots->objs,
+ LCORE_CACHE_SIZE, NULL);
+ cached_free_slots->len -= n_slots;
+ }
+ /* Put index of new free slot in cache. */
+ cached_free_slots->objs[cached_free_slots->len] =
+ (void *)((uintptr_t)position);
+ cached_free_slots->len++;
+ } else {
+ rte_ring_sp_enqueue(h->free_slots,
+ (void *)((uintptr_t)position));
+ }
+
+ return 0;
+}
+
static inline void
compare_signatures(uint32_t *prim_hash_matches, uint32_t *sec_hash_matches,
const struct rte_hash_bucket *prim_bkt,
@@ -168,6 +168,12 @@ struct rte_hash {
uint8_t readwrite_concur_support;
/**< If read-write concurrency support is enabled */
uint8_t ext_table_support; /**< Enable extendable bucket table */
+ uint8_t no_free_on_del;
+ /**< If key index should be freed on calling rte_hash_del_xxx APIs.
+ * If this is set, rte_hash_free_key_with_position must be called to
+ * free the key index associated with the deleted entry.
+ * This flag is enabled by default.
+ */
uint8_t writer_takes_lock;
/**< Indicates if the writer threads need to take lock */
rte_hash_function hash_func; /**< Function used to calculate hash. */
@@ -14,6 +14,8 @@
#include <stdint.h>
#include <stddef.h>
+#include <rte_compat.h>
+
#ifdef __cplusplus
extern "C" {
#endif
@@ -40,6 +42,11 @@ extern "C" {
/** Flag to indicate the extendabe bucket table feature should be used */
#define RTE_HASH_EXTRA_FLAGS_EXT_TABLE 0x08
+/** Flag to disable freeing of key index on hash delete.
+ * Refer to rte_hash_del_xxx APIs for more details.
+ */
+#define RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL 0x10
+
/**
* The type of hash value of a key.
* It should be a value of at least 32bit with fully random pattern.
@@ -236,6 +243,10 @@ rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t
* and should only be called from one thread by default.
* Thread safety can be enabled by setting flag during
* table creation.
+ * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is enabled,
+ * the key index returned by rte_hash_add_key_xxx APIs will not be
+ * freed by this API. rte_hash_free_key_with_position API must be called
+ * additionally to free the index associated with the key.
*
* @param h
* Hash table to remove the key from.
@@ -257,6 +268,10 @@ rte_hash_del_key(const struct rte_hash *h, const void *key);
* and should only be called from one thread by default.
* Thread safety can be enabled by setting flag during
* table creation.
+ * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is enabled,
+ * the key index returned by rte_hash_add_key_xxx APIs will not be
+ * freed by this API. rte_hash_free_key_with_position API must be called
+ * additionally to free the index associated with the key.
*
* @param h
* Hash table to remove the key from.
@@ -296,6 +311,31 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
void **key);
/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Free a hash key in the hash table given the position
+ * of the key. This operation is not multi-thread safe and should
+ * only be called from one thread by default. Thread safety
+ * can be enabled by setting flag during table creation.
+ * If RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL is enabled,
+ * this API must be called, with the key index returned by rte_hash_add_key_xxx
+ * APIs, after the key is deleted using rte_hash_del_key_xxx APIs.
+ * This API does not validate if the key is already freed.
+ *
+ * @param h
+ * Hash table to free the key from.
+ * @param position
+ * Position returned when the key was deleted.
+ * @return
+ * - 0 if freed successfully
+ * - -EINVAL if the parameters are invalid.
+ */
+int __rte_experimental
+rte_hash_free_key_with_position(const struct rte_hash *h,
+ const int32_t position);
+
+/**
* Find a key-value pair in the hash table.
* This operation is multi-thread safe with regarding to other lookup threads.
* Read-write concurrency can be enabled by setting flag during
@@ -260,6 +260,13 @@ static void run_hash_func_tests(void)
* - lookup (hit)
* - delete
* - lookup (miss)
+ *
+ * Repeat the test case when 'free on delete' is disabled.
+ * - add
+ * - lookup (hit)
+ * - delete
+ * - lookup (miss)
+ * - free
*/
static int test_add_delete(void)
{
@@ -295,10 +302,12 @@ static int test_add_delete(void)
/* repeat test with precomputed hash functions */
hash_sig_t hash_value;
- int pos1, expectedPos1;
+ int pos1, expectedPos1, delPos1;
+ ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL;
handle = rte_hash_create(&ut_params);
RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+ ut_params.extra_flag = 0;
hash_value = rte_hash_hash(handle, &keys[0]);
pos1 = rte_hash_add_key_with_hash(handle, &keys[0], hash_value);
@@ -315,12 +324,18 @@ static int test_add_delete(void)
print_key_info("Del", &keys[0], pos1);
RETURN_IF_ERROR(pos1 != expectedPos1,
"failed to delete key (pos1=%d)", pos1);
+ delPos1 = 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);
+ pos1 = rte_hash_free_key_with_position(handle, delPos1);
+ print_key_info("Free", &keys[0], delPos1);
+ RETURN_IF_ERROR(pos1 != 0,
+ "failed to free key (pos1=%d)", delPos1);
+
rte_hash_free(handle);
return 0;
@@ -391,6 +406,84 @@ static int test_add_update_delete(void)
}
/*
+ * Sequence of operations for a single key with 'disable free on del' set:
+ * - delete: miss
+ * - add
+ * - lookup: hit
+ * - add: update
+ * - lookup: hit (updated data)
+ * - delete: hit
+ * - delete: miss
+ * - lookup: miss
+ * - free: hit
+ * - lookup: miss
+ */
+static int test_add_update_delete_free(void)
+{
+ struct rte_hash *handle;
+ int pos0, expectedPos0, delPos0, result;
+
+ ut_params.name = "test2";
+ ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL;
+ handle = rte_hash_create(&ut_params);
+ RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+ ut_params.extra_flag = 0;
+
+ pos0 = rte_hash_del_key(handle, &keys[0]);
+ print_key_info("Del", &keys[0], pos0);
+ RETURN_IF_ERROR(pos0 != -ENOENT,
+ "fail: found non-existent key (pos0=%d)", pos0);
+
+ pos0 = rte_hash_add_key(handle, &keys[0]);
+ print_key_info("Add", &keys[0], pos0);
+ RETURN_IF_ERROR(pos0 < 0, "failed to add key (pos0=%d)", pos0);
+ expectedPos0 = pos0;
+
+ pos0 = rte_hash_lookup(handle, &keys[0]);
+ print_key_info("Lkp", &keys[0], pos0);
+ RETURN_IF_ERROR(pos0 != expectedPos0,
+ "failed to find key (pos0=%d)", pos0);
+
+ pos0 = rte_hash_add_key(handle, &keys[0]);
+ print_key_info("Add", &keys[0], pos0);
+ RETURN_IF_ERROR(pos0 != expectedPos0,
+ "failed to re-add key (pos0=%d)", pos0);
+
+ pos0 = rte_hash_lookup(handle, &keys[0]);
+ print_key_info("Lkp", &keys[0], pos0);
+ RETURN_IF_ERROR(pos0 != expectedPos0,
+ "failed to find key (pos0=%d)", pos0);
+
+ delPos0 = rte_hash_del_key(handle, &keys[0]);
+ print_key_info("Del", &keys[0], delPos0);
+ RETURN_IF_ERROR(delPos0 != expectedPos0,
+ "failed to delete key (pos0=%d)", delPos0);
+
+ pos0 = rte_hash_del_key(handle, &keys[0]);
+ print_key_info("Del", &keys[0], pos0);
+ RETURN_IF_ERROR(pos0 != -ENOENT,
+ "fail: deleted already deleted key (pos0=%d)", pos0);
+
+ pos0 = rte_hash_lookup(handle, &keys[0]);
+ print_key_info("Lkp", &keys[0], pos0);
+ RETURN_IF_ERROR(pos0 != -ENOENT,
+ "fail: found key after deleting! (pos0=%d)", pos0);
+
+ result = rte_hash_free_key_with_position(handle, delPos0);
+ print_key_info("Free", &keys[0], delPos0);
+ RETURN_IF_ERROR(result != 0,
+ "failed to free key (pos1=%d)", delPos0);
+
+ pos0 = rte_hash_lookup(handle, &keys[0]);
+ print_key_info("Lkp", &keys[0], pos0);
+ RETURN_IF_ERROR(pos0 != -ENOENT,
+ "fail: found key after deleting! (pos0=%d)", pos0);
+
+ rte_hash_free(handle);
+ return 0;
+}
+
+/*
* Sequence of operations for retrieving a key with its position
*
* - create table
@@ -399,11 +492,20 @@ static int test_add_update_delete(void)
* - delete key
* - try to get the deleted key: miss
*
+ * Repeat the test case when 'free on delete' is disabled.
+ * - create table
+ * - add key
+ * - get the key with its position: hit
+ * - delete key
+ * - try to get the deleted key: hit
+ * - free key
+ * - try to get the deleted key: miss
+ *
*/
static int test_hash_get_key_with_position(void)
{
struct rte_hash *handle = NULL;
- int pos, expectedPos, result;
+ int pos, expectedPos, delPos, result;
void *key;
ut_params.name = "hash_get_key_w_pos";
@@ -427,6 +529,38 @@ static int test_hash_get_key_with_position(void)
RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
rte_hash_free(handle);
+
+ ut_params.name = "hash_get_key_w_pos";
+ ut_params.extra_flag = RTE_HASH_EXTRA_FLAGS_NO_FREE_ON_DEL;
+ handle = rte_hash_create(&ut_params);
+ RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+ ut_params.extra_flag = 0;
+
+ pos = rte_hash_add_key(handle, &keys[0]);
+ print_key_info("Add", &keys[0], pos);
+ RETURN_IF_ERROR(pos < 0, "failed to add key (pos0=%d)", pos);
+ expectedPos = pos;
+
+ result = rte_hash_get_key_with_position(handle, pos, &key);
+ RETURN_IF_ERROR(result != 0, "error retrieving a key");
+
+ delPos = rte_hash_del_key(handle, &keys[0]);
+ print_key_info("Del", &keys[0], delPos);
+ RETURN_IF_ERROR(delPos != expectedPos,
+ "failed to delete key (pos0=%d)", delPos);
+
+ result = rte_hash_get_key_with_position(handle, delPos, &key);
+ RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
+
+ result = rte_hash_free_key_with_position(handle, delPos);
+ print_key_info("Free", &keys[0], delPos);
+ RETURN_IF_ERROR(result != 0,
+ "failed to free key (pos1=%d)", delPos);
+
+ result = rte_hash_get_key_with_position(handle, delPos, &key);
+ RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
+
+ rte_hash_free(handle);
return 0;
}
@@ -1609,6 +1743,8 @@ test_hash(void)
return -1;
if (test_add_update_delete() < 0)
return -1;
+ if (test_add_update_delete_free() < 0)
+ return -1;
if (test_five_keys() < 0)
return -1;
if (test_full_bucket() < 0)