@@ -1120,43 +1120,140 @@ rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
return __builtin_popcountl(*hit_mask);
}
+/* istate stands for internal state. */
+struct rte_hash_iterator_istate {
+ const struct rte_hash *h;
+ uint32_t next;
+ uint32_t total_entries;
+};
+
+int32_t
+rte_hash_iterator_init(const struct rte_hash *h,
+ struct rte_hash_iterator_state *state)
+{
+ struct rte_hash_iterator_istate *__state;
+
+ RETURN_IF_TRUE(((h == NULL) || (state == NULL)), -EINVAL);
+
+ __state = (struct rte_hash_iterator_istate *)state;
+ __state->h = h;
+ __state->next = 0;
+ __state->total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
+
+ return 0;
+}
+
int32_t
-rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next)
+rte_hash_iterate(
+ struct rte_hash_iterator_state *state, const void **key, void **data)
{
+ struct rte_hash_iterator_istate *__state;
uint32_t bucket_idx, idx, position;
struct rte_hash_key *next_key;
- RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
+ RETURN_IF_TRUE(((state == NULL) || (key == NULL) ||
+ (data == NULL)), -EINVAL);
+
+ __state = (struct rte_hash_iterator_istate *)state;
- const uint32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
/* Out of bounds */
- if (*next >= total_entries)
+ if (__state->next >= __state->total_entries)
return -ENOENT;
/* Calculate bucket and index of current iterator */
- bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
- idx = *next % RTE_HASH_BUCKET_ENTRIES;
+ bucket_idx = __state->next / RTE_HASH_BUCKET_ENTRIES;
+ idx = __state->next % RTE_HASH_BUCKET_ENTRIES;
/* If current position is empty, go to the next one */
- while (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) {
- (*next)++;
+ while (__state->h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) {
+ __state->next++;
/* End of table */
- if (*next == total_entries)
+ if (__state->next == __state->total_entries)
return -ENOENT;
- bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
- idx = *next % RTE_HASH_BUCKET_ENTRIES;
+ bucket_idx = __state->next / RTE_HASH_BUCKET_ENTRIES;
+ idx = __state->next % RTE_HASH_BUCKET_ENTRIES;
}
/* Get position of entry in key table */
- position = h->buckets[bucket_idx].key_idx[idx];
- next_key = (struct rte_hash_key *) ((char *)h->key_store +
- position * h->key_entry_size);
+ position = __state->h->buckets[bucket_idx].key_idx[idx];
+ next_key = (struct rte_hash_key *) ((char *)__state->h->key_store +
+ position * __state->h->key_entry_size);
/* Return key and data */
*key = next_key->key;
*data = next_key->pdata;
/* Increment iterator */
- (*next)++;
+ __state->next++;
return position - 1;
}
+
+struct rte_hash_iterator_conflict_entries_istate {
+ const struct rte_hash *h;
+ uint32_t vnext;
+ uint32_t primary_bidx;
+ uint32_t secondary_bidx;
+};
+
+int32_t __rte_experimental
+rte_hash_iterator_conflict_entries_init_with_hash(const struct rte_hash *h,
+ hash_sig_t sig, struct rte_hash_iterator_state *state)
+{
+ struct rte_hash_iterator_conflict_entries_istate *__state;
+
+ RETURN_IF_TRUE(((h == NULL) || (state == NULL)), -EINVAL);
+
+ __state = (struct rte_hash_iterator_conflict_entries_istate *)state;
+ __state->h = h;
+ __state->vnext = 0;
+
+ /* Get the primary bucket index given the precomputed hash value. */
+ __state->primary_bidx = sig & h->bucket_bitmask;
+ /* Get the secondary bucket index given the precomputed hash value. */
+ __state->secondary_bidx =
+ rte_hash_secondary_hash(sig) & h->bucket_bitmask;
+
+ return 0;
+}
+
+int32_t __rte_experimental
+rte_hash_iterate_conflict_entries(
+ struct rte_hash_iterator_state *state, const void **key, void **data)
+{
+ struct rte_hash_iterator_conflict_entries_istate *__state;
+
+ RETURN_IF_TRUE(((state == NULL) || (key == NULL) ||
+ (data == NULL)), -EINVAL);
+
+ __state = (struct rte_hash_iterator_conflict_entries_istate *)state;
+
+ while (__state->vnext < RTE_HASH_BUCKET_ENTRIES * 2) {
+ uint32_t bidx = __state->vnext < RTE_HASH_BUCKET_ENTRIES ?
+ __state->primary_bidx : __state->secondary_bidx;
+ uint32_t next = __state->vnext & (RTE_HASH_BUCKET_ENTRIES - 1);
+ uint32_t position = __state->h->buckets[bidx].key_idx[next];
+ struct rte_hash_key *next_key;
+
+ /* Increment iterator. */
+ __state->vnext++;
+
+ /*
+ * The test below is unlikely because this iterator is meant
+ * to be used after a failed insert.
+ * */
+ if (unlikely(position == EMPTY_SLOT))
+ continue;
+
+ /* Get the entry in key table. */
+ next_key = (struct rte_hash_key *) (
+ (char *)__state->h->key_store +
+ position * __state->h->key_entry_size);
+ /* Return key and data. */
+ *key = next_key->key;
+ *data = next_key->pdata;
+
+ return position - 1;
+ }
+
+ return -ENOENT;
+}
@@ -14,6 +14,8 @@
#include <stdint.h>
#include <stddef.h>
+#include <rte_compat.h>
+
#ifdef __cplusplus
extern "C" {
#endif
@@ -61,6 +63,11 @@ struct rte_hash_parameters {
/** @internal A hash table structure. */
struct rte_hash;
+/** @internal A hash table iterator state structure. */
+struct rte_hash_iterator_state {
+ uint8_t space[64];
+} __rte_cache_aligned;
+
/**
* Create a new hash table.
*
@@ -399,26 +406,76 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
uint32_t num_keys, int32_t *positions);
/**
- * Iterate through the hash table, returning key-value pairs.
+ * Initialize the iterator over the hash table.
*
* @param h
- * Hash table to iterate
+ * Hash table to iterate.
+ * @param state
+ * Pointer to the iterator state.
+ * @return
+ * - 0 if successful.
+ * - -EINVAL if the parameters are invalid.
+ */
+int32_t
+rte_hash_iterator_init(const struct rte_hash *h,
+ struct rte_hash_iterator_state *state);
+
+/**
+ * Iterate through the hash table, returning key-value pairs.
+ *
+ * @param state
+ * Pointer to the iterator state.
* @param key
* Output containing the key where current iterator
* was pointing at
* @param data
* Output containing the data associated with key.
* Returns NULL if data was not stored.
- * @param next
- * Pointer to iterator. Should be 0 to start iterating the hash table.
- * Iterator is incremented after each call of this function.
* @return
* Position where key was stored, if successful.
* - -EINVAL if the parameters are invalid.
* - -ENOENT if end of the hash table.
*/
int32_t
-rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next);
+rte_hash_iterate(
+ struct rte_hash_iterator_state *state, const void **key, void **data);
+
+/**
+ * Initialize the iterator over entries that conflict with a given hash.
+ *
+ * @param h
+ * Hash table to iterate.
+ * @param sig
+ * Precomputed hash value with which the returning entries conflict.
+ * @param state
+ * Pointer to the iterator state.
+ * @return
+ * - 0 if successful.
+ * - -EINVAL if the parameters are invalid.
+ */
+int32_t __rte_experimental
+rte_hash_iterator_conflict_entries_init_with_hash(const struct rte_hash *h,
+ hash_sig_t sig, struct rte_hash_iterator_state *state);
+
+/**
+ * Iterate over entries that conflict with a given hash.
+ *
+ * @param state
+ * Pointer to the iterator state.
+ * @param key
+ * Output containing the key at where the iterator is currently pointing.
+ * @param data
+ * Output containing the data associated with key.
+ * Returns NULL if data was not stored.
+ * @return
+ * Position where key was stored, if successful.
+ * - -EINVAL if the parameters are invalid.
+ * - -ENOENT if there is no more conflicting entries.
+ */
+int32_t __rte_experimental
+rte_hash_iterate_conflict_entries(
+ struct rte_hash_iterator_state *state, const void **key, void **data);
+
#ifdef __cplusplus
}
#endif
@@ -24,6 +24,7 @@ DPDK_2.1 {
rte_hash_add_key_data;
rte_hash_add_key_with_hash_data;
+ rte_hash_iterator_init;
rte_hash_iterate;
rte_hash_lookup_bulk_data;
rte_hash_lookup_data;
@@ -45,3 +46,10 @@ DPDK_16.07 {
rte_hash_get_key_with_position;
} DPDK_2.2;
+
+EXPERIMENTAL {
+ global:
+
+ rte_hash_iterator_conflict_entries_init_with_hash;
+ rte_hash_iterate_conflict_entries;
+};
@@ -1158,8 +1158,8 @@ static int test_hash_iteration(void)
void *next_data;
void *data[NUM_ENTRIES];
unsigned added_keys;
- uint32_t iter = 0;
int ret = 0;
+ struct rte_hash_iterator_state state;
ut_params.entries = NUM_ENTRIES;
ut_params.name = "test_hash_iteration";
@@ -1168,6 +1168,9 @@ static int test_hash_iteration(void)
handle = rte_hash_create(&ut_params);
RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+ RETURN_IF_ERROR(rte_hash_iterator_init(handle, &state) != 0,
+ "initialization of the hash iterator failed");
+
/* Add random entries until key cannot be added */
for (added_keys = 0; added_keys < NUM_ENTRIES; added_keys++) {
data[added_keys] = (void *) ((uintptr_t) rte_rand());
@@ -1179,7 +1182,7 @@ static int test_hash_iteration(void)
}
/* Iterate through the hash table */
- while (rte_hash_iterate(handle, &next_key, &next_data, &iter) >= 0) {
+ while (rte_hash_iterate(&state, &next_key, &next_data) >= 0) {
/* Search for the key in the list of keys added */
for (i = 0; i < NUM_ENTRIES; i++) {
if (memcmp(next_key, keys[i], ut_params.key_len) == 0) {
@@ -112,17 +112,21 @@ test_hash_multiwriter(void)
const void *next_key;
void *next_data;
- uint32_t iter = 0;
uint32_t duplicated_keys = 0;
uint32_t lost_keys = 0;
+ struct rte_hash_iterator_state state;
+
snprintf(name, 32, "test%u", calledCount++);
hash_params.name = name;
handle = rte_hash_create(&hash_params);
RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+ RETURN_IF_ERROR(rte_hash_iterator_init(handle, &state) != 0,
+ "initialization of the hash iterator failed");
+
tbl_multiwriter_test_params.h = handle;
tbl_multiwriter_test_params.nb_tsx_insertion =
nb_total_tsx_insertion / rte_lcore_count();
@@ -163,7 +167,7 @@ test_hash_multiwriter(void)
NULL, CALL_MASTER);
rte_eal_mp_wait_lcore();
- while (rte_hash_iterate(handle, &next_key, &next_data, &iter) >= 0) {
+ while (rte_hash_iterate(&state, &next_key, &next_data) >= 0) {
/* Search for the key in the list of keys added .*/
i = *(const uint32_t *)next_key;
tbl_multiwriter_test_params.found[i]++;