DPDK patches and discussions
 help / color / mirror / Atom feed
From: Qiaobin Fu <qiaobinf@bu.edu>
To: Bruce Richardson <bruce.richardson@intel.com>,
	Pablo de Lara <pablo.de.lara.guarch@intel.com>
Cc: dev@dpdk.org, michel@digirati.com.br, doucette@bu.edu,
	Qiaobin Fu <qiaobinf@bu.edu>
Subject: [dpdk-dev] [PATCH] hash table: add a bucket iterator function
Date: Sat, 28 Jul 2018 13:48:51 -0400
Message-ID: <20180728174851.46422-1-qiaobinf@bu.edu> (raw)

Function rte_hash_bucket_iterate() enables callers to
incrementally iterate over the hash table bucket by bucket,
so that it can avoid creating hiccups and thrashing the cache
of the processor.

This patch mainly deals with cases in which
the hash table is full and one needs to decide if the incoming
entry is more valuable than the entries already in the hash table.

Signed-off-by: Qiaobin Fu <qiaobinf@bu.edu>
Reviewed-by: Cody Doucette <doucette@bu.edu>
Reviewed-by: Michel Machado <michel@digirati.com.br>
---
 lib/librte_hash/rte_cuckoo_hash.c    | 60 +++++++++++++++++++++++++
 lib/librte_hash/rte_hash.h           | 66 ++++++++++++++++++++++++++++
 lib/librte_hash/rte_hash_version.map |  4 ++
 3 files changed, 130 insertions(+)

diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index a07543a29..2b90f3593 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -1160,3 +1160,63 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32
 
 	return position - 1;
 }
+
+int
+rte_hash_get_num_buckets(struct rte_hash *h)
+{
+	RETURN_IF_TRUE((h == NULL), -EINVAL);
+	return h->num_buckets;
+}
+
+uint32_t
+rte_hash_get_primary_bucket(const struct rte_hash *h, hash_sig_t sig)
+{
+	return sig & h->bucket_bitmask;
+}
+
+uint32_t
+rte_hash_get_secondary_bucket(const struct rte_hash *h, hash_sig_t sig)
+{
+	return rte_hash_secondary_hash(sig) & h->bucket_bitmask;
+}
+
+int32_t
+rte_hash_bucket_iterate(const struct rte_hash *h,
+	const void **key, void **data, uint32_t *bidx, uint32_t *next)
+{
+	uint32_t position;
+	struct rte_hash_key *next_key;
+
+	RETURN_IF_TRUE(((h == NULL) || (key == NULL) || (data == NULL) ||
+		(bidx == NULL) || (next == NULL)), -EINVAL);
+
+	/* Out of bounds. */
+	if (*bidx >= h->num_buckets || *next >= RTE_HASH_BUCKET_ENTRIES)
+		goto next_bucket;
+
+	/* If current position is empty, go to the next one. */
+	while (h->buckets[*bidx].key_idx[*next] == EMPTY_SLOT) {
+		(*next)++;
+		/* End of bucket. */
+		if (*next >= RTE_HASH_BUCKET_ENTRIES)
+			goto next_bucket;
+	}
+
+	/* Get position of entry in key table. */
+	position = h->buckets[*bidx].key_idx[*next];
+	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;
+
+	/* Increment iterator. */
+	(*next)++;
+
+	return position - 1;
+
+next_bucket:
+	*bidx = (*bidx + 1) >= h->num_buckets ? 0 : *bidx + 1;
+	*next = 0;
+	return -ENOENT;
+}
diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
index f71ca9fbf..329bf42d6 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -94,6 +94,17 @@ rte_hash_create(const struct rte_hash_parameters *params);
  */
 void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func);
 
+/**
+ * Get the number of buckets in the hash table.
+ * @param h
+ *   Hash table for which the function queries.
+ * @return
+ *   The number of buckets in the hash table h.
+ *    - EINVAL - invalid parameter passed to function
+ */
+int
+rte_hash_get_num_buckets(struct rte_hash *h);
+
 /**
  * Find an existing hash table object and return a pointer to it.
  *
@@ -261,6 +272,34 @@ int
 rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
 			       void **key);
 
+/**
+ * Get the primary bucket index given the precomputed hash value.
+ * This operation is multi-thread safe.
+ *
+ * @param h
+ *   Hash table to get the key from.
+ * @param sig
+ *   Precomputed hash value.
+ * @return
+ *   The primary bucket index.
+ */
+uint32_t
+rte_hash_get_primary_bucket(const struct rte_hash *h, hash_sig_t sig);
+
+/**
+ * Get the secondary bucket index given the precomputed hash value.
+ * This operation is multi-thread safe.
+ *
+ * @param h
+ *   Hash table to get the key from.
+ * @param sig
+ *   Precomputed hash value.
+ * @return
+ *   The primary bucket index.
+ */
+uint32_t
+rte_hash_get_secondary_bucket(const struct rte_hash *h, hash_sig_t sig);
+
 /**
  * Find a key-value pair in the hash table.
  * This operation is multi-thread safe.
@@ -419,6 +458,33 @@ rte_hash_lookup_bulk(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);
+
+/**
+ * Iterate through the buckets in hash table, returning key-value pairs.
+ *
+ * @param h
+ *   Hash table to iterate
+ * @param key
+ *   Output containing the key where current iterator
+ *   was pointing at
+ * @param data
+ *   Output containing the data associated with key.
+ *   Returns NULL if data was not stored.
+ * @param bidx
+ *   Pointer to the current bucket index. Should be 0 to start
+ *   iterating the hash table. Iterator is incremented after
+ *   RTE_HASH_BUCKET_ENTRIES calls of this function.
+ * @param next
+ *   Pointer to iterator. Should be 0 to start iterating the bucket.
+ *   Iterator is incremented after each call of this function.
+ * @return
+ *   Position where key was stored, if successful.
+ *   - -EINVAL if the parameters are invalid.
+ *   - -ENOENT if end of the bucket.
+ */
+int32_t
+rte_hash_bucket_iterate(const struct rte_hash *h,
+	const void **key, void **data, uint32_t *bidx, uint32_t *next);
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map
index 52a2576f9..7d48f32c9 100644
--- a/lib/librte_hash/rte_hash_version.map
+++ b/lib/librte_hash/rte_hash_version.map
@@ -15,6 +15,10 @@ DPDK_2.0 {
 	rte_hash_lookup;
 	rte_hash_lookup_bulk;
 	rte_hash_lookup_with_hash;
+	rte_hash_get_num_buckets;
+	rte_hash_get_primary_bucket;
+	rte_hash_get_secondary_bucket;
+	rte_hash_bucket_iterate;
 
 	local: *;
 };
-- 
2.17.1

             reply	other threads:[~2018-07-28 17:50 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-07-28 17:48 Qiaobin Fu [this message]
2018-07-29 13:17 ` Wiles, Keith
     [not found]   ` <D2C4A16CA39F7F4E8E384D204491D7A66148250A@ORSMSX105.amr.corp.intel.com>
2018-07-31  6:09     ` Fu, Qiaobin
2018-07-31 14:57       ` Wiles, Keith
2018-07-31 15:32         ` Michel Machado
2018-08-01  1:40           ` Wang, Yipeng1
2018-08-01 12:57             ` Michel Machado
2018-08-03 15:24               ` Stephen Hemminger
2018-08-07 13:24                 ` Michel Machado
  -- strict thread matches above, loose matches on Subject: below --
2018-07-15 17:15 Qiaobin Fu

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=20180728174851.46422-1-qiaobinf@bu.edu \
    --to=qiaobinf@bu.edu \
    --cc=bruce.richardson@intel.com \
    --cc=dev@dpdk.org \
    --cc=doucette@bu.edu \
    --cc=michel@digirati.com.br \
    --cc=pablo.de.lara.guarch@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

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