[dpdk-dev] hash: fix incorrect eviction counter
Checks
Commit Message
When adding a new entry in a hash table, there is
a maximum number of evictions that can be
performed. When the counter of these evictions reaches
this maximum, the entry cannot be added, as it is considered
that the algorithm has encountered an infinite loop.
The problem with the current implementation, is that this
counter was declared as a static variable.
If there are multiple threads adding entries in the same table
or in different tables, they should access different counters,
one per core and per table.
Therefore, an array of counter has been added to the
hash table structure.
Fixes: 243e93a5046f ("hash: fix unlimited cuckoo path")
Cc: stable@dpdk.org
Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
lib/librte_hash/rte_cuckoo_hash.c | 27 ++++++++++++++++++---------
lib/librte_hash/rte_cuckoo_hash.h | 4 ++++
2 files changed, 22 insertions(+), 9 deletions(-)
Comments
On Thu, Sep 21, 2017 at 01:46:46PM +0100, Pablo de Lara wrote:
> When adding a new entry in a hash table, there is
> a maximum number of evictions that can be
> performed. When the counter of these evictions reaches
> this maximum, the entry cannot be added, as it is considered
> that the algorithm has encountered an infinite loop.
>
> The problem with the current implementation, is that this
> counter was declared as a static variable.
> If there are multiple threads adding entries in the same table
> or in different tables, they should access different counters,
> one per core and per table.
>
> Therefore, an array of counter has been added to the
> hash table structure.
>
> Fixes: 243e93a5046f ("hash: fix unlimited cuckoo path")
> Cc: stable@dpdk.org
>
> Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
> ---
Since you appear to be passing this counter through the different
function calls as parameter, and it gets reset to zero at the start, do
you even need an array. Can you not just have a non-static local
variable in the function?
/Bruce
> -----Original Message-----
> From: Richardson, Bruce
> Sent: Friday, September 22, 2017 9:36 AM
> To: De Lara Guarch, Pablo <pablo.de.lara.guarch@intel.com>
> Cc: dev@dpdk.org; stable@dpdk.org
> Subject: Re: [PATCH] hash: fix incorrect eviction counter
>
> On Thu, Sep 21, 2017 at 01:46:46PM +0100, Pablo de Lara wrote:
> > When adding a new entry in a hash table, there is a maximum number of
> > evictions that can be performed. When the counter of these evictions
> > reaches this maximum, the entry cannot be added, as it is considered
> > that the algorithm has encountered an infinite loop.
> >
> > The problem with the current implementation, is that this counter was
> > declared as a static variable.
> > If there are multiple threads adding entries in the same table or in
> > different tables, they should access different counters, one per core
> > and per table.
> >
> > Therefore, an array of counter has been added to the hash table
> > structure.
> >
> > Fixes: 243e93a5046f ("hash: fix unlimited cuckoo path")
> > Cc: stable@dpdk.org
> >
> > Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
> > ---
> Since you appear to be passing this counter through the different function
> calls as parameter, and it gets reset to zero at the start, do you even need
> an array. Can you not just have a non-static local variable in the function?
>
> /Bruce
Right, I clearly overthought here... Will send a v2 with your much simpler approach.
Thanks!
Pablo
@@ -121,6 +121,7 @@ rte_hash_create(const struct rte_hash_parameters *params)
char hash_name[RTE_HASH_NAMESIZE];
void *k = NULL;
void *buckets = NULL;
+ uint32_t *nr_cuckoo_pushes = NULL;
char ring_name[RTE_RING_NAMESIZE];
unsigned num_key_slots;
unsigned hw_trans_mem_support = 0;
@@ -313,6 +314,14 @@ rte_hash_create(const struct rte_hash_parameters *params)
for (i = 1; i < params->entries + 1; i++)
rte_ring_sp_enqueue(r, (void *)((uintptr_t) i));
+ nr_cuckoo_pushes = rte_zmalloc_socket(NULL,
+ sizeof(uint32_t) * RTE_MAX_LCORE,
+ 0, params->socket_id);
+ if (nr_cuckoo_pushes == NULL) {
+ RTE_LOG(ERR, HASH, "memory allocation failed\n");
+ goto err_unlock;
+ }
+ h->nr_cuckoo_pushes = nr_cuckoo_pushes;
te->data = (void *) h;
TAILQ_INSERT_TAIL(hash_list, te, next);
rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
@@ -326,6 +335,7 @@ rte_hash_create(const struct rte_hash_parameters *params)
rte_free(h);
rte_free(buckets);
rte_free(k);
+ rte_free(nr_cuckoo_pushes);
return NULL;
}
@@ -417,9 +427,9 @@ rte_hash_reset(struct rte_hash *h)
/* Search for an entry that can be pushed to its alternative location */
static inline int
-make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
+make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt,
+ uint32_t *nr_pushes)
{
- static unsigned int nr_pushes;
unsigned i, j;
int ret;
uint32_t next_bucket_idx;
@@ -456,15 +466,14 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
break;
/* All entries have been pushed, so entry cannot be added */
- if (i == RTE_HASH_BUCKET_ENTRIES || nr_pushes > RTE_HASH_MAX_PUSHES)
+ if (i == RTE_HASH_BUCKET_ENTRIES || ++(*nr_pushes) > RTE_HASH_MAX_PUSHES)
return -ENOSPC;
/* Set flag to indicate that this entry is going to be pushed */
bkt->flag[i] = 1;
- nr_pushes++;
/* Need room in alternative bucket to insert the pushed entry */
- ret = make_space_bucket(h, next_bkt[i]);
+ ret = make_space_bucket(h, next_bkt[i], nr_pushes);
/*
* After recursive function.
* Clear flags and insert the pushed entry
@@ -472,7 +481,7 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt)
* or return error
*/
bkt->flag[i] = 0;
- nr_pushes = 0;
+ *nr_pushes = 0;
if (ret >= 0) {
next_bkt[i]->sig_alt[ret] = bkt->sig_current[i];
next_bkt[i]->sig_current[ret] = bkt->sig_alt[i];
@@ -513,8 +522,9 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
uint32_t new_idx;
int ret;
unsigned n_slots;
- unsigned lcore_id;
+ unsigned int lcore_id = rte_lcore_id();
struct lcore_cache *cached_free_slots = NULL;
+ uint32_t *nr_pushes = &(h->nr_cuckoo_pushes[lcore_id]);
if (h->add_key == ADD_KEY_MULTIWRITER)
rte_spinlock_lock(h->multiwriter_lock);
@@ -530,7 +540,6 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
/* Get a new slot for storing the new key */
if (h->hw_trans_mem_support) {
- lcore_id = rte_lcore_id();
cached_free_slots = &h->local_free_slots[lcore_id];
/* Try to get a free slot from the local cache */
if (cached_free_slots->len == 0) {
@@ -648,7 +657,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
* if successful or return error and
* store the new slot back in the ring
*/
- ret = make_space_bucket(h, prim_bkt);
+ ret = make_space_bucket(h, prim_bkt, nr_pushes);
if (ret >= 0) {
prim_bkt->sig_current[ret] = sig;
prim_bkt->sig_alt[ret] = alt_hash;
@@ -219,6 +219,10 @@ struct rte_hash {
/**< Table with buckets storing all the hash values and key indexes
* to the key table.
*/
+ uint32_t *nr_cuckoo_pushes;
+ /**< Pointer to number of entries that have been evicted
+ * when adding a new entry, per lcore.
+ */
} __rte_cache_aligned;
struct queue_node {