[dpdk-dev] [PATCH v2 5/7] hash: add extendable bucket feature

[Wang, Yipeng1]

>-----Original Message-----
>From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli at arm.com]
>>
>> Extendable bucket table composes of buckets that can be linked list to current
>> main table. When extendable bucket is enabled, the table utilization can
>> always acheive 100%.
>IMO, referring to this as 'table utilization' indicates an efficiency about memory utilization. Please consider changing this to indicate
>that all of the configured number of entries will be accommodated?
>
[Wang, Yipeng] Improved in V4, please check! Thanks!

>> +snprintf(ext_ring_name, sizeof(ext_ring_name), "HT_EXT_%s",
>> +params-
>> >name);
>Can be inside the if statement below.
[Wang, Yipeng] Done in V3, Thanks!
>
>> +/* Populate ext bkt ring. We reserve 0 similar to the
>> + * key-data slot, just in case in future we want to
>> + * use bucket index for the linked list and 0 means NULL
>> + * for next bucket
>> + */
>> +for (i = 1; i <= num_buckets; i++)
>Since, the bucket index 0 is reserved, should be 'i < num_buckets'
[Wang, Yipeng]  So the bucket array is from 0 to num_buckets - 1, and the index
Is from 1 to num_buckets. So I guess reserving 0 means reserving the index 0 but
not reduce the usable bucket count.
So I guess we still need to enqueue index of 1 to num_buckets into the free
Bucket ring for use?
>
>>  rte_free(h->key_store);
>>  rte_free(h->buckets);
>Add rte_free(h->buckets_ext);
[Wang, Yipeng] Done in V3, thanks!
>
>> +for (i = 1; i < h->num_buckets + 1; i++)
>Index 0 is reserved as per the comments. Condition should be 'i < h->num_buckets'.
[Wang, Yipeng] Similar to previous one, I guess we still need the number of num_buckets index
To be inserted in the ring.
>
>> +bkt_id = (uint32_t)((uintptr_t)ext_bkt_id) - 1;
>If index 0 is reserved, -1 is not required.
>
[Wang, Yipeng] Similar to previous one, bkt_id is the subscript to the array so it ranges from 0 to num_bucket - 1.
While the index is ranged from 1 to num_bucket. So I guess every time we got a bucket index we need to -1
To get the bucket array subscript. 
>> +if (tobe_removed_bkt) {
>> +uint32_t index = tobe_removed_bkt - h->buckets_ext + 1;
>No need to increase the index by 1 if entry 0 is reserved.
>
[Wang, Yipeng] Similar to previous one.
>> @@ -1308,10 +1519,13 @@ rte_hash_iterate(const struct rte_hash *h, const
>> void **key, void **data, uint32
>>
>>  RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
>>
>> -const uint32_t total_entries = h->num_buckets *
>> RTE_HASH_BUCKET_ENTRIES;
>> +const uint32_t total_entries_main = h->num_buckets *
>> +
>> RTE_HASH_BUCKET_ENTRIES;
>> +const uint32_t total_entries = total_entries_main << 1;
>> +
>>  /* Out of bounds */
>Minor: update the comment to reflect the new code.
[Wang, Yipeng] Done in V4, thanks!
>
>> @@ -1341,4 +1555,32 @@ rte_hash_iterate(const struct rte_hash *h, const
>> void **key, void **data, uint32
>>  (*next)++;
>>
>>  return position - 1;
>> +
>> +extend_table:
>> +/* Out of bounds */
>> +if (*next >= total_entries || !h->ext_table_support)
>> +return -ENOENT;
>> +
>> +bucket_idx = (*next - total_entries_main) /
>> RTE_HASH_BUCKET_ENTRIES;
>> +idx = (*next - total_entries_main) % RTE_HASH_BUCKET_ENTRIES;
>> +
>> +while (h->buckets_ext[bucket_idx].key_idx[idx] == EMPTY_SLOT) {
>> +(*next)++;
>> +if (*next == total_entries)
>> +return -ENOENT;
>> +bucket_idx = (*next - total_entries_main) /
>> +RTE_HASH_BUCKET_ENTRIES;
>> +idx = (*next - total_entries_main) %
>> RTE_HASH_BUCKET_ENTRIES;
>> +}
>> +/* Get position of entry in key table */
>> +position = h->buckets_ext[bucket_idx].key_idx[idx];
>There is a possibility that 'position' is not the same value read in the while loop. It presents a problem if 'position' becomes
>EMPTY_SLOT. 'position' should be read as part of the while loop. Since it is 32b value, it should be atomic on most platforms. This issue
>applies to existing code as well.
>
[Wang, Yipeng] I agree. I add a new bug fix commit to fix this in V4. Basically I just extend the current critical region to cover
The while loop. Please check if that works. Thanks.

>__hash_rw_reader_lock(h) required
>> +next_key = (struct rte_hash_key *) ((char *)h->key_store +
>> +position * h->key_entry_size);
>> +/* Return key and data */
>> +*key = next_key->key;
>> +*data = next_key->pdata;
>> +
>__hash_rw_reader_unlock(h) required
[Wang, Yipeng] Agree, done in V4.  Thanks!
>