[dpdk-dev] [PATCH v4 1/4] hash: fix race condition in iterate

Honnappa Nagarahalli Honnappa.Nagarahalli at arm.com
Tue Oct 2 06:26:59 CEST 2018


> 
> >-----Original Message-----
> >From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli at arm.com]
> >> @@ -1317,16 +1317,19 @@ rte_hash_iterate(const struct rte_hash *h,
> >> const void **key, void **data, uint32
> >>  	bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
> >>  	idx = *next % RTE_HASH_BUCKET_ENTRIES;
> >>
> >> +	__hash_rw_reader_lock(h);
> >This does not work well with the lock-less changes I am making.  We
> >should leave the lock in its original position. Instead change the while loop as
> follows:
> >
> >while ((position = h->buckets[bucket_idx].key_idx[idx]) == EMPTY_SLOT)
> >
> >>  	/* If current position is empty, go to the next one */
> >>  	while (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) {
> >>  		(*next)++;
> >>  		/* End of table */
> >> -		if (*next == total_entries)
> >> +		if (*next == total_entries) {
> >> +			__hash_rw_reader_unlock(h);
> >>  			return -ENOENT;
> >> +		}
> >>  		bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES;
> >>  		idx = *next % RTE_HASH_BUCKET_ENTRIES;
> >>  	}
> >> -	__hash_rw_reader_lock(h);
> >> +
> >>  	/* Get position of entry in key table */
> >>  	position = h->buckets[bucket_idx].key_idx[idx];
> >If we change the while loop as I suggested as above, we can remove this line.
> >
> >>  	next_key = (struct rte_hash_key *) ((char *)h->key_store +
> 
> [Wang, Yipeng] Sorry that I did not realize you already have it in your patch
> set and I agree.
> Do you want to export it as a bug fix in your patch set? I will remove my
> change.
Sure, I will make a separate commit for this.

> 
> For the lock free, do we need to protect it with version counter? Imagine the
> following corner case:
> While the iterator read the key and data, there is a writer deleted, removed,
> and recycled the key-data pair, and write a new key and data into it. While the
> writer are writing, will the reader reads out wrong key/data, or mismatched
> key/data?
> 
In the lock-free algorithm, the key-data is not 'freed' until the readers have completed all their references to the 'deleted' key-data. Hence, the writers will not be able to allocate the same key store index till the readers have stopped referring to the 'deleted' key-data.
I re-checked my ladder diagrams [1] and I could not find any issues.

[1] https://dpdkuserspace2018.sched.com/event/G44w/lock-free-read-write-concurrency-in-rtehash (PPT)


More information about the dev mailing list