From: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>
To: "Wang, Yipeng1" <yipeng1.wang@intel.com>,
"Richardson, Bruce" <bruce.richardson@intel.com>
Cc: "dev@dpdk.org" <dev@dpdk.org>,
"michel@digirati.com.br" <michel@digirati.com.br>,
"Gobriel, Sameh" <sameh.gobriel@intel.com>,
Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>,
nd <nd@arm.com>
Subject: Re: [dpdk-dev] [PATCH v2 5/7] hash: add extendable bucket feature
Date: Mon, 1 Oct 2018 20:56:37 +0000 [thread overview]
Message-ID: <AM6PR08MB36720F3D2B09D1D2150F49A898EF0@AM6PR08MB3672.eurprd08.prod.outlook.com> (raw)
In-Reply-To: <D2C4A16CA39F7F4E8E384D204491D7A6614E9767@FMSMSX151.amr.corp.intel.com>
> >-----Original Message-----
> >From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@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?
I understand it now. I mis-read the 'similar to the key-data slot' comment. I see that the changes are correct.
Minor comment, I am not particular: I think it makes sense to change it to the same logic followed for key-data slot. i.e. allocate an extra bucket.
> >
> >> 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++)
Minor comment:
If we are not changing the logic, I suggest we change the for loop as follows (like it is done earlier)
for (i = 1; i <= h->num_buckets; 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!
> >
next prev parent reply other threads:[~2018-10-01 20:56 UTC|newest]
Thread overview: 107+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-09-06 17:09 [dpdk-dev] [PATCH v1 0/5] hash: add extendable bucket and partial-key hashing Yipeng Wang
2018-09-06 17:09 ` [dpdk-dev] [PATCH v1 1/5] test: fix bucket size in hash table perf test Yipeng Wang
2018-09-06 17:09 ` [dpdk-dev] [PATCH v1 2/5] test: more accurate hash table perf test output Yipeng Wang
2018-09-06 17:09 ` [dpdk-dev] [PATCH v1 3/5] hash: add extendable bucket feature Yipeng Wang
2018-09-06 17:09 ` [dpdk-dev] [PATCH v1 4/5] test: implement extendable bucket hash test Yipeng Wang
2018-09-06 17:09 ` [dpdk-dev] [PATCH v1 5/5] hash: use partial-key hashing Yipeng Wang
2018-09-21 17:17 ` [dpdk-dev] [PATCH v2 0/7] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-09-21 17:17 ` [dpdk-dev] [PATCH v2 1/7] test/hash: fix bucket size in hash perf test Yipeng Wang
2018-09-26 10:04 ` Bruce Richardson
2018-09-27 3:39 ` Wang, Yipeng1
2018-09-27 4:23 ` Honnappa Nagarahalli
2018-09-29 0:31 ` Wang, Yipeng1
2018-09-21 17:17 ` [dpdk-dev] [PATCH v2 2/7] test/hash: more accurate hash perf test output Yipeng Wang
2018-09-26 10:07 ` Bruce Richardson
2018-09-21 17:17 ` [dpdk-dev] [PATCH v2 3/7] test/hash: fix rw test with non-consecutive cores Yipeng Wang
2018-09-26 11:02 ` Bruce Richardson
2018-09-27 3:40 ` Wang, Yipeng1
2018-09-26 11:13 ` Bruce Richardson
2018-09-21 17:17 ` [dpdk-dev] [PATCH v2 4/7] hash: fix unnecessary code Yipeng Wang
2018-09-26 12:55 ` Bruce Richardson
2018-09-21 17:17 ` [dpdk-dev] [PATCH v2 5/7] hash: add extendable bucket feature Yipeng Wang
2018-09-27 4:23 ` Honnappa Nagarahalli
2018-09-27 11:15 ` Bruce Richardson
2018-09-27 11:27 ` Ananyev, Konstantin
2018-09-27 12:27 ` Bruce Richardson
2018-09-27 12:33 ` Ananyev, Konstantin
2018-09-27 19:21 ` Honnappa Nagarahalli
2018-09-28 17:35 ` Wang, Yipeng1
2018-09-29 21:09 ` Honnappa Nagarahalli
2018-09-29 1:10 ` Wang, Yipeng1
2018-10-01 20:56 ` Honnappa Nagarahalli [this message]
2018-10-02 1:56 ` Wang, Yipeng1
2018-09-21 17:17 ` [dpdk-dev] [PATCH v2 6/7] test/hash: implement extendable bucket hash test Yipeng Wang
2018-09-27 4:24 ` Honnappa Nagarahalli
2018-09-29 0:50 ` Wang, Yipeng1
2018-09-21 17:17 ` [dpdk-dev] [PATCH v2 7/7] hash: use partial-key hashing Yipeng Wang
2018-09-27 4:24 ` Honnappa Nagarahalli
2018-09-29 0:55 ` Wang, Yipeng1
2018-09-26 12:57 ` [dpdk-dev] [PATCH v2 0/7] hash: add extendable bucket and partial key hashing Bruce Richardson
2018-09-27 3:41 ` Wang, Yipeng1
2018-09-27 4:23 ` Honnappa Nagarahalli
2018-09-29 0:46 ` Wang, Yipeng1
2018-09-26 12:54 ` [dpdk-dev] [PATCH v3 0/5] hash: fix multiple issues Yipeng Wang
2018-09-26 12:54 ` [dpdk-dev] [PATCH v3 1/5] test/hash: fix bucket size in hash perf test Yipeng Wang
2018-09-27 11:17 ` Bruce Richardson
2018-09-26 12:54 ` [dpdk-dev] [PATCH v3 2/5] test/hash: more accurate hash perf test output Yipeng Wang
2018-09-26 12:54 ` [dpdk-dev] [PATCH v3 3/5] test/hash: fix rw test with non-consecutive cores Yipeng Wang
2018-09-27 11:18 ` Bruce Richardson
2018-09-26 12:54 ` [dpdk-dev] [PATCH v3 4/5] test/hash: fix missing file in meson build file Yipeng Wang
2018-09-27 11:22 ` Bruce Richardson
2018-09-26 12:54 ` [dpdk-dev] [PATCH v3 5/5] hash: fix unused define Yipeng Wang
2018-09-28 14:11 ` [dpdk-dev] [PATCH v4 0/5] hash: fix multiple issues Yipeng Wang
2018-09-28 14:11 ` [dpdk-dev] [PATCH v4 1/5] test/hash: fix bucket size in hash perf test Yipeng Wang
2018-10-01 20:28 ` Honnappa Nagarahalli
2018-09-28 14:11 ` [dpdk-dev] [PATCH v4 2/5] test/hash: more accurate hash perf test output Yipeng Wang
2018-09-28 14:11 ` [dpdk-dev] [PATCH v4 3/5] test/hash: fix rw test with non-consecutive cores Yipeng Wang
2018-09-28 14:11 ` [dpdk-dev] [PATCH v4 4/5] test/hash: fix missing file in meson build file Yipeng Wang
2018-09-28 14:11 ` [dpdk-dev] [PATCH v4 5/5] hash: fix unused define Yipeng Wang
2018-10-25 22:04 ` [dpdk-dev] [PATCH v4 0/5] hash: fix multiple issues Thomas Monjalon
2018-09-26 20:26 ` [dpdk-dev] [PATCH v3 0/3] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-09-26 20:26 ` [dpdk-dev] [PATCH v3 1/3] hash: add extendable bucket feature Yipeng Wang
2018-09-26 20:26 ` [dpdk-dev] [PATCH v3 2/3] test/hash: implement extendable bucket hash test Yipeng Wang
2018-09-26 20:26 ` [dpdk-dev] [PATCH v3 3/3] hash: use partial-key hashing Yipeng Wang
2018-09-28 17:23 ` [dpdk-dev] [PATCH v4 0/4] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-09-28 17:23 ` [dpdk-dev] [PATCH v4 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-01 20:23 ` Honnappa Nagarahalli
2018-10-02 0:17 ` Wang, Yipeng1
2018-10-02 4:26 ` Honnappa Nagarahalli
2018-10-02 23:53 ` Wang, Yipeng1
2018-09-28 17:23 ` [dpdk-dev] [PATCH v4 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-02 3:58 ` Honnappa Nagarahalli
2018-10-02 23:39 ` Wang, Yipeng1
2018-10-03 4:37 ` Honnappa Nagarahalli
2018-10-03 15:08 ` Stephen Hemminger
2018-10-03 15:08 ` Stephen Hemminger
2018-10-03 16:53 ` Wang, Yipeng1
2018-10-03 17:59 ` Honnappa Nagarahalli
2018-10-04 1:22 ` Wang, Yipeng1
2018-09-28 17:23 ` [dpdk-dev] [PATCH v4 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-01 19:53 ` Honnappa Nagarahalli
2018-09-28 17:23 ` [dpdk-dev] [PATCH v4 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-01 20:09 ` Honnappa Nagarahalli
2018-10-03 19:05 ` [dpdk-dev] [PATCH v4 0/4] hash: add extendable bucket and partial key hashing Dharmik Thakkar
2018-10-01 18:34 ` [dpdk-dev] [PATCH v5 " Yipeng Wang
2018-10-01 18:34 ` [dpdk-dev] [PATCH v5 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-02 17:26 ` Honnappa Nagarahalli
2018-10-01 18:35 ` [dpdk-dev] [PATCH v5 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-01 18:35 ` [dpdk-dev] [PATCH v5 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-01 18:35 ` [dpdk-dev] [PATCH v5 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-02 20:52 ` Dharmik Thakkar
2018-10-03 0:43 ` Wang, Yipeng1
2018-10-03 19:10 ` [dpdk-dev] [PATCH v5 0/4] hash: add extendable bucket and partial key hashing Dharmik Thakkar
2018-10-04 0:36 ` Wang, Yipeng1
2018-10-04 16:35 ` [dpdk-dev] [PATCH v6 " Yipeng Wang
2018-10-04 16:35 ` [dpdk-dev] [PATCH v6 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-04 16:35 ` [dpdk-dev] [PATCH v6 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-04 16:35 ` [dpdk-dev] [PATCH v6 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-04 16:35 ` [dpdk-dev] [PATCH v6 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-10 21:27 ` [dpdk-dev] [PATCH v7 0/4] hash: add extendable bucket and partial key hashing Yipeng Wang
2018-10-10 21:27 ` [dpdk-dev] [PATCH v7 1/4] hash: fix race condition in iterate Yipeng Wang
2018-10-10 21:27 ` [dpdk-dev] [PATCH v7 2/4] hash: add extendable bucket feature Yipeng Wang
2018-10-10 21:27 ` [dpdk-dev] [PATCH v7 3/4] test/hash: implement extendable bucket hash test Yipeng Wang
2018-10-10 21:27 ` [dpdk-dev] [PATCH v7 4/4] hash: use partial-key hashing Yipeng Wang
2018-10-16 18:47 ` [dpdk-dev] [PATCH] doc: update release note for hash library Yipeng Wang
2018-10-17 20:09 ` Honnappa Nagarahalli
2018-10-25 18:45 ` Wang, Yipeng1
2018-10-25 23:07 ` Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=AM6PR08MB36720F3D2B09D1D2150F49A898EF0@AM6PR08MB3672.eurprd08.prod.outlook.com \
--to=honnappa.nagarahalli@arm.com \
--cc=bruce.richardson@intel.com \
--cc=dev@dpdk.org \
--cc=michel@digirati.com.br \
--cc=nd@arm.com \
--cc=sameh.gobriel@intel.com \
--cc=yipeng1.wang@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).