Re: [dpdk-dev] [PATCH v4 2/4] hash: add extendable bucket feature

[Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>]

> >> +	while (last_bkt->next) {
> >> +		prev_bkt = last_bkt;
> >> +		last_bkt = last_bkt->next;
> >> +	}
> >Minor: We are trying to find the last bucket here, along with its previous.
> May be we can modify 'rte_hash_get_last_bkt' instead?
> >
> [Wang, Yipeng] Then there will be one more store in each iteration for the
> regular find_last. I was having an individual function for this but since it is
> only used here I removed that. If you think it is necessary or you may reuse it
> somewhere else for LF, I can add it back.
I am fine with the existing code.

> >> +
> >> +	for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
> >> +		if (last_bkt->key_idx[i] != EMPTY_SLOT)
> >> +			break;
> >> +	}
> >> +	/* found empty bucket and recycle */
> >> +	if (i == RTE_HASH_BUCKET_ENTRIES) {
> >> +		prev_bkt->next = last_bkt->next = NULL;
> >> +		uint32_t index = last_bkt - h->buckets_ext + 1;
> >> +		rte_ring_sp_enqueue(h->free_ext_bkts, (void
> >> *)(uintptr_t)index);
> >In the lock-less algorithm, the bucket cannot be freed immediately. I
> >looked at couple of solutions. The bucket needs to be stored internally and
> should be associated with the key-store index (or position). I am thinking that I
> will add a field to 'struct rte_hash_key'
> >to store the bucket pointer or index.
> [Wang, Yipeng] Even if the bucket is recycled immediately, what's the worst
> could happen? Even if there are readers currently iterating the deleted Bucket,
> it is still fine right? It is a miss anyway.
Good question. Logically, freeing the bucket is similar to freeing memory. I think the worst that can happen is, readers will continue looking up a bucket (and any additional linked buckets), that they do not have to. But, I do not see any illegal memory accesses. I will have a better answer once I get code this.

> >
> >From the code, my understanding is that we will free only the last
> >bucket. We will never free the middle bucket, please correct me if I am
> wrong. This will keep it simple for the lock-free algorithm.
> [Wang, Yipeng] It is correct.
> >
> >I could work through these issues. So, I do not see any issues for lock-free
> algorithm (as of now :) ).
> >
> >> +
> >> +	/* Out of bounds of all buckets (both main table and ext table */
> >Typo: missing ')'
> >
> [Wang, Yipeng] Yeah thanks!
> 
Apologies :)