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

["Wang, Yipeng1" <yipeng1.wang@intel.com>]

>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com]
>> +
>> +	for (i = RTE_HASH_BUCKET_ENTRIES - 1; i >= 0; i--) {
>> +		if (last_bkt->key_idx[i] != EMPTY_SLOT) {
>> +			cur_bkt->key_idx[pos] = last_bkt->key_idx[i];
>> +			cur_bkt->sig_current[pos] = last_bkt->sig_current[i];
>> +			cur_bkt->sig_alt[pos] = last_bkt->sig_alt[i];
>> +			last_bkt->sig_current[i] = NULL_SIGNATURE;
>> +			last_bkt->sig_alt[i] = NULL_SIGNATURE;
>> +			last_bkt->key_idx[i] = EMPTY_SLOT;
>> +			return;
>In lock-free algorithm, this will require the global counter increment.
>
[Wang, Yipeng] I agree. Similar to your protect for cuckoo displacement, protecting the copy part.
>> +	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.
>> +
>> +	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. 
>
>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!