DPDK patches and discussions
 help / color / mirror / Atom feed
From: "Wang, Yipeng1" <yipeng1.wang@intel.com>
To: Qiaobin Fu <qiaobinf@bu.edu>,
	"Richardson, Bruce" <bruce.richardson@intel.com>,
	"De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com>
Cc: "dev@dpdk.org" <dev@dpdk.org>,
	"doucette@bu.edu" <doucette@bu.edu>,
	"Wiles, Keith" <keith.wiles@intel.com>,
	"Gobriel, Sameh" <sameh.gobriel@intel.com>,
	"Tai, Charlie" <charlie.tai@intel.com>,
	"stephen@networkplumber.org" <stephen@networkplumber.org>,
	"nd@arm.com" <nd@arm.com>,
	"honnappa.nagarahalli@arm.com" <honnappa.nagarahalli@arm.com>,
	"michel@digirati.com.br" <michel@digirati.com.br>
Subject: Re: [dpdk-dev] [PATCH v4 2/2] hash table: add an iterator over conflicting entries
Date: Wed, 10 Oct 2018 02:54:57 +0000
Message-ID: <D2C4A16CA39F7F4E8E384D204491D7A6614EE385@FMSMSX151.amr.corp.intel.com> (raw)
In-Reply-To: <20181009192907.85650-2-qiaobinf@bu.edu>

Hi, Qiaobin,

Could you try to rebase on this patch set? (http://patchwork.dpdk.org/cover/46106/) 

I checked your patch and I think there won't be many functional issues merging our patches. Let's coordinate to make sure the final merge is easier. 

Other comments inlined:

>-----Original Message-----
>From: Qiaobin Fu [mailto:qiaobinf@bu.edu]
>diff --git a/MAINTAINERS b/MAINTAINERS
>index 9fd258fad..e8c81656f 100644
>--- a/MAINTAINERS
>+++ b/MAINTAINERS
>@@ -1055,7 +1055,7 @@ F: test/test/test_efd*
> F: examples/server_node_efd/
> F: doc/guides/sample_app_ug/server_node_efd.rst
>
>-Hashes
>+Hashes - EXPERIMENTAL
[Wang, Yipeng] I don’t think we need to mark the whole library to be experimental, do we?

> M: Bruce Richardson <bruce.richardson@intel.com>
> M: Pablo de Lara <pablo.de.lara.guarch@intel.com>
> F: lib/librte_hash/
>diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
>index a3e76684d..439251a7f 100644
>--- a/lib/librte_hash/rte_cuckoo_hash.c
>+++ b/lib/librte_hash/rte_cuckoo_hash.c
>@@ -1301,7 +1301,10 @@ rte_hash_lookup_bulk_data(const struct rte_hash *h, const void **keys,
> }
>
> int32_t
>-rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next)
>+rte_hash_iterate_v1808(const struct rte_hash *h,
>+	const void **key,
>+	void **data,
>+	uint32_t *next)
> {
> 	uint32_t bucket_idx, idx, position;
> 	struct rte_hash_key *next_key;
>@@ -1344,3 +1347,132 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32
>
> 	return position - 1;
> }
>+VERSION_SYMBOL(rte_hash_iterate, _v1808, 18.08);
>+
>+int32_t
>+rte_hash_iterate_v1811(const struct rte_hash *h,
[Wang, Yipeng]With the ext table patch set, this function considers the ext bucket as well. For a rebase,
You just need to add that part of code.
>+	const void **key,
>+	void **data,
>+	struct rte_hash_iterator_state *state)
>+{
>+	struct rte_hash_iterator_priv *it;
>+	uint32_t bucket_idx, idx, position;
>+	struct rte_hash_key *next_key;
>+
>+	RETURN_IF_TRUE(((h == NULL) || (key == NULL) ||
>+		(data == NULL) || (state == NULL)), -EINVAL);
>+
>+	RTE_BUILD_BUG_ON(sizeof(struct rte_hash_iterator_priv) >
>+		sizeof(struct rte_hash_iterator_state));
>+
>+	it = (struct rte_hash_iterator_priv *)state;
>+	if (it->next == 0)
>+		it->total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
>+
>+	/* Out of bounds */
>+	if (it->next >= it->total_entries)
>+		return -ENOENT;
>+
>+	/* Calculate bucket and index of current iterator */
>+	bucket_idx = it->next / RTE_HASH_BUCKET_ENTRIES;
>+	idx = it->next % RTE_HASH_BUCKET_ENTRIES;
>+
>+	__hash_rw_reader_lock(h);
>+	/* If current position is empty, go to the next one */
>+	while (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) {
>+		it->next++;
>+		/* End of table */
>+		if (it->next == it->total_entries) {
>+			__hash_rw_reader_unlock(h);
>+			return -ENOENT;
>+		}
>+		bucket_idx = it->next / RTE_HASH_BUCKET_ENTRIES;
>+		idx = it->next % RTE_HASH_BUCKET_ENTRIES;
>+	}
>+	/* Get position of entry in key table */
>+	position = h->buckets[bucket_idx].key_idx[idx];
>+	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);
>+
>+	/* Increment iterator */
>+	it->next++;
>+
>+	return position - 1;
>+}
>+MAP_STATIC_SYMBOL(int32_t rte_hash_iterate(const struct rte_hash *h,
>+	const void **key, void **data, struct rte_hash_iterator_state *state),
>+	rte_hash_iterate_v1811);
>+
>+int32_t __rte_experimental
>+rte_hash_iterate_conflict_entries_with_hash(struct rte_hash *h,
>+	const void **key,
>+	void **data,
>+	hash_sig_t sig,
>+	struct rte_hash_iterator_state *state)
[Wang, Yipeng] With the ext bucket feature, the conflict entries can include the entries in the
Linked list. You can keep the current behavior for simplicity or iterate the linked list
as well if the extendable bucket is turned on.  For iterating the linked list, the vnext
can grow larger than RTE_HASH_BUCKET_ENTRIES. It depends on you but if not
Iterate the linked list, please indicate it in the API comment.
>+{
>+	struct rte_hash_iterator_conflict_entries_priv *it;
>+
>+	RETURN_IF_TRUE(((h == NULL) || (key == NULL) ||
>+		(data == NULL) || (state == NULL)), -EINVAL);
>+
>+	RTE_BUILD_BUG_ON(sizeof(
>+		struct rte_hash_iterator_conflict_entries_priv) >
>+		sizeof(struct rte_hash_iterator_state));
>+
>+	it = (struct rte_hash_iterator_conflict_entries_priv *)state;
>+	if (it->vnext == 0) {
>+		/*
>+		 * Get the primary bucket index given
>+		 * the precomputed hash value.
>+		 */
>+		it->primary_bidx = sig & h->bucket_bitmask;
>+		/*
>+		 * Get the secondary bucket index given
>+		 * the precomputed hash value.
>+		 */
>+		it->secondary_bidx =
>+			rte_hash_secondary_hash(sig) & h->bucket_bitmask;
>+	}
>+
>+	while (it->vnext < RTE_HASH_BUCKET_ENTRIES * 2) {
>+		uint32_t bidx = it->vnext < RTE_HASH_BUCKET_ENTRIES ?
>+			it->primary_bidx : it->secondary_bidx;
>+		uint32_t next = it->vnext & (RTE_HASH_BUCKET_ENTRIES - 1);
>+		uint32_t position;
>+		struct rte_hash_key *next_key;
>+
>+		RTE_BUILD_BUG_ON(!RTE_IS_POWER_OF_2(RTE_HASH_BUCKET_ENTRIES));
[Wang, Yipeng] I think we already checked this in rte_cuckoo_hash.h

>+		__hash_rw_reader_lock(h);
>+		position = h->buckets[bidx].key_idx[next];
>+
>+		/* Increment iterator. */
>+		it->vnext++;
>+
>+		/*
>+		 * The test below is unlikely because this iterator is meant
>+		 * to be used after a failed insert.
>+		 */
>+		if (unlikely(position == EMPTY_SLOT)) {
>+			__hash_rw_reader_unlock(h);
 [Wang, Yipeng] Should you just lock the outer while loop so that if there are many empty entries, the lock function won't
be called multiple times? It is more coarse grained but saves the cost of lock.


  reply	other threads:[~2018-10-10  2:55 UTC|newest]

Thread overview: 21+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-08-31 16:51 [dpdk-dev] [PATCH v3] " Qiaobin Fu
2018-08-31 22:53 ` Gaëtan Rivet
2018-09-04 18:46   ` Michel Machado
2018-09-02 22:05 ` Honnappa Nagarahalli
2018-09-04 19:36   ` Michel Machado
2018-09-05 22:13     ` Honnappa Nagarahalli
2018-09-06 14:28       ` Michel Machado
2018-09-12 20:37         ` Honnappa Nagarahalli
2018-09-20 19:50           ` Michel Machado
2018-09-04 18:55 ` Wang, Yipeng1
2018-09-04 19:07   ` Michel Machado
2018-09-04 19:51     ` Wang, Yipeng1
2018-09-04 20:26       ` Michel Machado
2018-09-04 20:57         ` Wang, Yipeng1
2018-09-05 17:52           ` Michel Machado
2018-09-05 20:27             ` Wang, Yipeng1
2018-09-06 13:34               ` Michel Machado
2018-10-09 19:29 ` [dpdk-dev] [PATCH v4 1/2] hash table: fix a bug in rte_hash_iterate() Qiaobin Fu
2018-10-09 19:29   ` [dpdk-dev] [PATCH v4 2/2] hash table: add an iterator over conflicting entries Qiaobin Fu
2018-10-10  2:54     ` Wang, Yipeng1 [this message]
2018-10-10  1:55   ` [dpdk-dev] [PATCH v4 1/2] hash table: fix a bug in rte_hash_iterate() Wang, Yipeng1

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=D2C4A16CA39F7F4E8E384D204491D7A6614EE385@FMSMSX151.amr.corp.intel.com \
    --to=yipeng1.wang@intel.com \
    --cc=bruce.richardson@intel.com \
    --cc=charlie.tai@intel.com \
    --cc=dev@dpdk.org \
    --cc=doucette@bu.edu \
    --cc=honnappa.nagarahalli@arm.com \
    --cc=keith.wiles@intel.com \
    --cc=michel@digirati.com.br \
    --cc=nd@arm.com \
    --cc=pablo.de.lara.guarch@intel.com \
    --cc=qiaobinf@bu.edu \
    --cc=sameh.gobriel@intel.com \
    --cc=stephen@networkplumber.org \
    /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

DPDK patches and discussions

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://inbox.dpdk.org/dev/0 dev/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 dev dev/ https://inbox.dpdk.org/dev \
		dev@dpdk.org
	public-inbox-index dev

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://inbox.dpdk.org/inbox.dpdk.dev


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git