rhashtable: Move hash_rnd into bucket_table

rhashtable: Move hash_rnd into bucket_table

[Herbert Xu]

Currently hash_rnd is a parameter that users can set.  However,
no existing users set this parameter.  It is also something that
people are unlikely to want to set directly since it's just a
random number.
    
In preparation for allowing the reseeding/rehashing of rhashtable,
this patch moves hash_rnd into bucket_table so that it's now an
internal state rather than a parameter.
    
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index a2562ed..6d7e840 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -55,6 +55,7 @@ struct rhash_head {
 struct bucket_table {
 	size_t				size;
 	unsigned int			locks_mask;
+	u32				hash_rnd;
 	spinlock_t			*locks;
 	struct rhash_head __rcu		*buckets[];
 };
@@ -70,7 +71,6 @@ struct rhashtable;
  * @key_len: Length of key
  * @key_offset: Offset of key in struct to be hashed
  * @head_offset: Offset of rhash_head in struct to be hashed
- * @hash_rnd: Seed to use while hashing
  * @max_shift: Maximum number of shifts while expanding
  * @min_shift: Minimum number of shifts while shrinking
  * @nulls_base: Base value to generate nulls marker
@@ -89,7 +89,6 @@ struct rhashtable_params {
 	size_t			key_len;
 	size_t			key_offset;
 	size_t			head_offset;
-	u32			hash_rnd;
 	size_t			max_shift;
 	size_t			min_shift;
 	u32			nulls_base;
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 84a78e3..71c6aa1 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -81,13 +81,14 @@ static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
 
 static u32 obj_raw_hashfn(const struct rhashtable *ht, const void *ptr)
 {
+	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 	u32 hash;
 
 	if (unlikely(!ht->p.key_len))
-		hash = ht->p.obj_hashfn(ptr, ht->p.hash_rnd);
+		hash = ht->p.obj_hashfn(ptr, tbl->hash_rnd);
 	else
 		hash = ht->p.hashfn(ptr + ht->p.key_offset, ht->p.key_len,
-				    ht->p.hash_rnd);
+				    tbl->hash_rnd);
 
 	return hash >> HASH_RESERVED_SPACE;
 }
@@ -97,7 +98,7 @@ static u32 key_hashfn(struct rhashtable *ht, const void *key, u32 len)
 	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 	u32 hash;
 
-	hash = ht->p.hashfn(key, len, ht->p.hash_rnd);
+	hash = ht->p.hashfn(key, len, tbl->hash_rnd);
 	hash >>= HASH_RESERVED_SPACE;
 
 	return rht_bucket_index(tbl, hash);
@@ -894,14 +895,13 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 	if (tbl == NULL)
 		return -ENOMEM;
 
+	get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
+
 	atomic_set(&ht->nelems, 0);
 	atomic_set(&ht->shift, ilog2(tbl->size));
 	RCU_INIT_POINTER(ht->tbl, tbl);
 	RCU_INIT_POINTER(ht->future_tbl, tbl);
 
-	if (!ht->p.hash_rnd)
-		get_random_bytes(&ht->p.hash_rnd, sizeof(ht->p.hash_rnd));
-
 	if (ht->p.grow_decision || ht->p.shrink_decision)
 		INIT_WORK(&ht->run_work, rht_deferred_worker);
 
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[RFC] rhashtable: rhashtable_rehash

[Herbert Xu]

Here is a totally untested patch that illustrates what I want to
do with rehash.

Note that this depends on the hash rnd patch I just sent.

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 4c3da1f..ebd5e44 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -79,9 +79,9 @@ static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
 	return hash & (tbl->size - 1);
 }
 
-static u32 obj_raw_hashfn(const struct rhashtable *ht, const void *ptr)
+static u32 obj_raw_hashfn(const struct rhashtable *ht,
+			  struct bucket_table *tbl, const void *ptr)
 {
-	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 	u32 hash;
 
 	if (unlikely(!ht->p.key_len))
@@ -93,9 +93,9 @@ static u32 obj_raw_hashfn(const struct rhashtable *ht, const void *ptr)
 	return hash >> HASH_RESERVED_SPACE;
 }
 
-static u32 key_hashfn(struct rhashtable *ht, const void *key, u32 len)
+static u32 key_hashfn(struct rhashtable *ht, struct bucket_table *tbl,
+		      const void *key, u32 len)
 {
-	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 	u32 hash;
 
 	hash = ht->p.hashfn(key, len, tbl->hash_rnd);
@@ -295,6 +295,89 @@ static void link_old_to_new(struct bucket_table *new_tbl,
 	spin_unlock_bh(new_bucket_lock);
 }
 
+static void rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash)
+{
+	struct *old_tbl = rht_dereference(ht->tbl, ht);
+	struct *new_tbl = rht_dereference(ht->future_tbl, ht);
+	struct rhash_head *head, *next, *entry;
+	struct rhash_head __rcu **pprev;
+	spinlock_t *new_bucket_lock;
+	unsigned int new_hash;
+
+	pprev = &old_tbl->buckets[old_hash];
+	rht_for_each(entry, old_tbl, old_hash) {
+		next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
+
+		if (rht_is_a_nulls(next))
+			break;
+
+		pprev = &entry->next;
+	}
+
+	new_hash = head_hashfn(ht, new_tbl, entry);
+
+	new_bucket_lock = bucket_lock(new_tbl, new_hash);
+
+	spin_lock(new_bucket_lock);
+	head = rht_dereference_bucket(new_tbl->buckets[new_hash],
+				      new_tbl, new_hash);
+
+	if (rht_is_a_nulls(head))
+		INIT_RHT_NULLS_HEAD(entry->next, ht, hash);
+	else
+		RCU_INIT_POINTER(entry->next, head);
+
+	rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
+	spin_unlock(new_bucket_lock);
+
+	rcu_assign_pointer(*pprev, next);
+}
+
+static void rhashtable_rehash_chain(struct rhashtable *ht,
+				    unsigned int old_hash)
+{
+	struct *old_tbl = rht_dereference(ht->tbl, ht);
+	spinlock_t *old_bucket_lock;
+
+	old_bucket_lock = bucket_lock(old_tbl, old_hash);
+
+	spin_lock_bh(old_bucket_lock);
+	while (!rht_is_a_nulls(rht_dereference_bucket(
+		old_tbl->buckets[old_hash], old_tbl, old_hash)))
+		rhashtable_rehash_one(ht, old_hash);
+	spin_unlock_bh(old_bucket_lock);
+}
+
+static void rhashtable_rehash(struct rhashtable *ht,
+			      struct bucket_table *new_tbl)
+{
+	struct *old_tbl = rht_dereference(ht->tbl, ht);
+
+	get_random_bytes(&new_tbl->hash_rnd, sizeof(new_tbl->hash_rnd));
+
+	/* Make insertions go into the new, empty table right away. Deletions
+	 * and lookups will be attempted in both tables until we synchronize.
+	 * The synchronize_rcu() guarantees for the new table to be picked up
+	 * so no new additions go into the old table while we relink.
+	 */
+	rcu_assign_pointer(ht->future_tbl, new_tbl);
+	synchronize_rcu();
+
+	for (old_hash = 0; i < old_tbl->size; old_hash++)
+		rhashtable_rehash_chain(ht, old_hash);
+
+	/* Publish the new table pointer. */
+	rcu_assign_pointer(ht->tbl, new_tbl);
+
+	/* Wait for readers. All new readers will see the new
+	 * table, and thus no references to the old table will
+	 * remain.
+	 */
+	synchronize_rcu();
+
+	bucket_table_free(old_tbl);
+}
+
 /**
  * rhashtable_expand - Expand hash table while allowing concurrent lookups
  * @ht:		the hash table to expand
@@ -327,72 +410,8 @@ int rhashtable_expand(struct rhashtable *ht)
 
 	atomic_inc(&ht->shift);
 
-	/* Make insertions go into the new, empty table right away. Deletions
-	 * and lookups will be attempted in both tables until we synchronize.
-	 * The synchronize_rcu() guarantees for the new table to be picked up
-	 * so no new additions go into the old table while we relink.
-	 */
-	rcu_assign_pointer(ht->future_tbl, new_tbl);
-	synchronize_rcu();
-
-	/* For each new bucket, search the corresponding old bucket for the
-	 * first entry that hashes to the new bucket, and link the end of
-	 * newly formed bucket chain (containing entries added to future
-	 * table) to that entry. Since all the entries which will end up in
-	 * the new bucket appear in the same old bucket, this constructs an
-	 * entirely valid new hash table, but with multiple buckets
-	 * "zipped" together into a single imprecise chain.
-	 */
-	for (new_hash = 0; new_hash < new_tbl->size; new_hash++) {
-		old_hash = rht_bucket_index(old_tbl, new_hash);
-		old_bucket_lock = bucket_lock(old_tbl, old_hash);
-
-		spin_lock_bh(old_bucket_lock);
-		rht_for_each(he, old_tbl, old_hash) {
-			if (head_hashfn(ht, new_tbl, he) == new_hash) {
-				link_old_to_new(new_tbl, new_hash, he);
-				break;
-			}
-		}
-		spin_unlock_bh(old_bucket_lock);
-	}
-
-	/* Publish the new table pointer. Lookups may now traverse
-	 * the new table, but they will not benefit from any
-	 * additional efficiency until later steps unzip the buckets.
-	 */
-	rcu_assign_pointer(ht->tbl, new_tbl);
-
-	/* Unzip interleaved hash chains */
-	while (!complete && !ht->being_destroyed) {
-		/* Wait for readers. All new readers will see the new
-		 * table, and thus no references to the old table will
-		 * remain.
-		 */
-		synchronize_rcu();
-
-		/* For each bucket in the old table (each of which
-		 * contains items from multiple buckets of the new
-		 * table): ...
-		 */
-		complete = true;
-		for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
-			struct rhash_head *head;
-
-			old_bucket_lock = bucket_lock(old_tbl, old_hash);
-			spin_lock_bh(old_bucket_lock);
-
-			hashtable_chain_unzip(ht, new_tbl, old_tbl, old_hash);
-			head = rht_dereference_bucket(old_tbl->buckets[old_hash],
-						      old_tbl, old_hash);
-			if (!rht_is_a_nulls(head))
-				complete = false;
-
-			spin_unlock_bh(old_bucket_lock);
-		}
-	}
+	rhashtable_rehash(ht, new_tbl);
 
-	bucket_table_free(old_tbl);
 	return 0;
 }
 EXPORT_SYMBOL_GPL(rhashtable_expand);
@@ -425,57 +444,7 @@ int rhashtable_shrink(struct rhashtable *ht)
 	if (new_tbl == NULL)
 		return -ENOMEM;
 
-	rcu_assign_pointer(ht->future_tbl, new_tbl);
-	synchronize_rcu();
-
-	/* Link the first entry in the old bucket to the end of the
-	 * bucket in the new table. As entries are concurrently being
-	 * added to the new table, lock down the new bucket. As we
-	 * always divide the size in half when shrinking, each bucket
-	 * in the new table maps to exactly two buckets in the old
-	 * table.
-	 *
-	 * As removals can occur concurrently on the old table, we need
-	 * to lock down both matching buckets in the old table.
-	 */
-	for (new_hash = 0; new_hash < new_tbl->size; new_hash++) {
-		old_bucket_lock1 = bucket_lock(tbl, new_hash);
-		old_bucket_lock2 = bucket_lock(tbl, new_hash + new_tbl->size);
-		new_bucket_lock = bucket_lock(new_tbl, new_hash);
-
-		spin_lock_bh(old_bucket_lock1);
-
-		/* Depending on the lock per buckets mapping, the bucket in
-		 * the lower and upper region may map to the same lock.
-		 */
-		if (old_bucket_lock1 != old_bucket_lock2) {
-			spin_lock_bh_nested(old_bucket_lock2, RHT_LOCK_NESTED);
-			spin_lock_bh_nested(new_bucket_lock, RHT_LOCK_NESTED2);
-		} else {
-			spin_lock_bh_nested(new_bucket_lock, RHT_LOCK_NESTED);
-		}
-
-		rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
-				   tbl->buckets[new_hash]);
-		rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
-				   tbl->buckets[new_hash + new_tbl->size]);
-
-		spin_unlock_bh(new_bucket_lock);
-		if (old_bucket_lock1 != old_bucket_lock2)
-			spin_unlock_bh(old_bucket_lock2);
-		spin_unlock_bh(old_bucket_lock1);
-	}
-
-	/* Publish the new, valid hash table */
-	rcu_assign_pointer(ht->tbl, new_tbl);
-	atomic_dec(&ht->shift);
-
-	/* Wait for readers. No new readers will have references to the
-	 * old hash table.
-	 */
-	synchronize_rcu();
-
-	bucket_table_free(tbl);
+	rhashtable_rehash(ht, new_tbl);
 
 	return 0;
 }

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: rhashtable: Move hash_rnd into bucket_table

[Thomas Graf]

On 01/31/15 at 09:21pm, Herbert Xu wrote:
> Currently hash_rnd is a parameter that users can set.  However,
> no existing users set this parameter.  It is also something that
> people are unlikely to want to set directly since it's just a
> random number.
>     
> In preparation for allowing the reseeding/rehashing of rhashtable,
> this patch moves hash_rnd into bucket_table so that it's now an
> internal state rather than a parameter.
>     
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

For net-next

Acked-by: Thomas Graf <tgraf@suug.ch>

Re: [RFC] rhashtable: rhashtable_rehash

[Thomas Graf]

On 01/31/15 at 09:23pm, Herbert Xu wrote:
> +	new_hash = head_hashfn(ht, new_tbl, entry);
> +
> +	new_bucket_lock = bucket_lock(new_tbl, new_hash);
> +
> +	spin_lock(new_bucket_lock);

I realize this is WIP and not fully worked out yet, therefore just a
thought:

Unless you change this fundamentally then locking just the new bucket
lock based on the new hash is not sufficient when you rehash while growing
as the old bucket will contain entries which will get distributed across
2 buckets in the new table and if we change the seed it will map to
even more buckets. I assume you have an idea how to handle that.

Let me know if any of the patches proposed in "rhashtable fixes" don't
conflict with your intended changes and I will resubmit those separately.

Re: rhashtable: Move hash_rnd into bucket_table

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Sat, 31 Jan 2015 21:21:50 +1100

> Currently hash_rnd is a parameter that users can set.  However,
> no existing users set this parameter.  It is also something that
> people are unlikely to want to set directly since it's just a
> random number.
>     
> In preparation for allowing the reseeding/rehashing of rhashtable,
> this patch moves hash_rnd into bucket_table so that it's now an
> internal state rather than a parameter.
>     
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Also applied to net-next, thanks a lot.

Re: rhashtable: Move hash_rnd into bucket_table

[David Miller]

From: David Miller <davem@davemloft.net>
Date: Mon, 02 Feb 2015 19:19:56 -0800 (PST)

> From: Herbert Xu <herbert@gondor.apana.org.au>
> Date: Sat, 31 Jan 2015 21:21:50 +1100
> 
>> Currently hash_rnd is a parameter that users can set.  However,
>> no existing users set this parameter.  It is also something that
>> people are unlikely to want to set directly since it's just a
>> random number.
>>     
>> In preparation for allowing the reseeding/rehashing of rhashtable,
>> this patch moves hash_rnd into bucket_table so that it's now an
>> internal state rather than a parameter.
>>     
>> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
> 
> Also applied to net-next, thanks a lot.

Actually this and the netfilter change break the build.

I'm reverting all of these rhashtable changes, please fix this stuff
up.

Firstly, the hash_rnd change results in this:

lib/rhashtable.c: In function ‘obj_raw_hashfn’:
lib/rhashtable.c:84:9: warning: passing argument 1 of ‘lockdep_rht_mutex_is_held’ discards ‘const’ qualifier from pointer target type [enabled by default]
lib/rhashtable.c:57:5: note: expected ‘struct rhashtable *’ but argument is of type ‘const struct rhashtable *’

Next, the netfilter change results in:

ERROR: "rhashtable_walk_start" [net/netfilter/nft_hash.ko] undefined!

Re: rhashtable: Move hash_rnd into bucket_table

[Herbert Xu]

On Mon, Feb 02, 2015 at 07:26:34PM -0800, David Miller wrote:
>
> Firstly, the hash_rnd change results in this:
> 
> lib/rhashtable.c: In function ‘obj_raw_hashfn’:
> lib/rhashtable.c:84:9: warning: passing argument 1 of ‘lockdep_rht_mutex_is_held’ discards ‘const’ qualifier from pointer target type [enabled by default]
> lib/rhashtable.c:57:5: note: expected ‘struct rhashtable *’ but argument is of type ‘const struct rhashtable *’

Pleas drop the hash_rnd patch since that's only needed by my
rehash work which is not yet complete.  Although I thought it
built correctly on its own since I've always had it in my test
tree but obviously I missed something.

> Next, the netfilter change results in:
> 
> ERROR: "rhashtable_walk_start" [net/netfilter/nft_hash.ko] undefined!

Oops, I missed an export on that symbol.  I'll fix it up and
repost.

Thanks,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[PATCH 0/4] rhashtable: Add iterators and use them

[Herbert Xu]

On Wed, Feb 04, 2015 at 07:17:50AM +1100, Herbert Xu wrote:
> 
> > ERROR: "rhashtable_walk_start" [net/netfilter/nft_hash.ko] undefined!
> 
> Oops, I missed an export on that symbol.  I'll fix it up and
> repost.

OK here is the repost without the hash_rnd patch.

The first patch fixes a potential crash with nft_hash destroying
the table during a shrinking process.  While the next patch adds
rhashtable iterators to replace current manual walks used by
netlink and netfilter.  The final two patches make use of these
iterators in netlink and netfilter.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[PATCH 1/4] rhashtable: Fix potential crash on destroy in rhashtable_shrink

[Herbert Xu]

The current being_destroyed check in rhashtable_expand is not
enough since if we start a shrinking process after freeing all
elements in the table that's also going to crash.

This patch adds a being_destroyed check to the deferred worker
thread so that we bail out as soon as we take the lock.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---

 lib/rhashtable.c |    4 ++++
 1 file changed, 4 insertions(+)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index c41e210..904b419 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -487,6 +487,9 @@ static void rht_deferred_worker(struct work_struct *work)
 
 	ht = container_of(work, struct rhashtable, run_work);
 	mutex_lock(&ht->mutex);
+	if (ht->being_destroyed)
+		goto unlock;
+
 	tbl = rht_dereference(ht->tbl, ht);
 
 	if (ht->p.grow_decision && ht->p.grow_decision(ht, tbl->size))
@@ -494,6 +497,7 @@ static void rht_deferred_worker(struct work_struct *work)
 	else if (ht->p.shrink_decision && ht->p.shrink_decision(ht, tbl->size))
 		rhashtable_shrink(ht);
 
+unlock:
 	mutex_unlock(&ht->mutex);
 }
 

[PATCH 2/4] rhashtable: Introduce rhashtable_walk_*

[Herbert Xu]

Some existing rhashtable users get too intimate with it by walking
the buckets directly.  This prevents us from easily changing the
internals of rhashtable.

This patch adds the helpers rhashtable_walk_init/exit/start/next/stop
which will replace these custom walkers.

They are meant to be usable for both procfs seq_file walks as well
as walking by a netlink dump.  The iterator structure should fit
inside a netlink dump cb structure, with at least one element to
spare.
  
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---

 include/linux/rhashtable.h |   35 +++++++++
 lib/rhashtable.c           |  163 +++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 198 insertions(+)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index e033784..5885127 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -18,6 +18,7 @@
 #ifndef _LINUX_RHASHTABLE_H
 #define _LINUX_RHASHTABLE_H
 
+#include <linux/compiler.h>
 #include <linux/list_nulls.h>
 #include <linux/workqueue.h>
 #include <linux/mutex.h>
@@ -111,6 +112,7 @@ struct rhashtable_params {
  * @p: Configuration parameters
  * @run_work: Deferred worker to expand/shrink asynchronously
  * @mutex: Mutex to protect current/future table swapping
+ * @walkers: List of active walkers
  * @being_destroyed: True if table is set up for destruction
  */
 struct rhashtable {
@@ -121,9 +123,36 @@ struct rhashtable {
 	struct rhashtable_params	p;
 	struct work_struct		run_work;
 	struct mutex                    mutex;
+	struct list_head		walkers;
 	bool                            being_destroyed;
 };
 
+/**
+ * struct rhashtable_walker - Hash table walker
+ * @list: List entry on list of walkers
+ * @resize: Resize event occured
+ */
+struct rhashtable_walker {
+	struct list_head list;
+	bool resize;
+};
+
+/**
+ * struct rhashtable_iter - Hash table iterator, fits into netlink cb
+ * @ht: Table to iterate through
+ * @p: Current pointer
+ * @walker: Associated rhashtable walker
+ * @slot: Current slot
+ * @skip: Number of entries to skip in slot
+ */
+struct rhashtable_iter {
+	struct rhashtable *ht;
+	struct rhash_head *p;
+	struct rhashtable_walker *walker;
+	unsigned int slot;
+	unsigned int skip;
+};
+
 static inline unsigned long rht_marker(const struct rhashtable *ht, u32 hash)
 {
 	return NULLS_MARKER(ht->p.nulls_base + hash);
@@ -179,6 +208,12 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
 				      bool (*compare)(void *, void *),
 				      void *arg);
 
+int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter);
+void rhashtable_walk_exit(struct rhashtable_iter *iter);
+int rhashtable_walk_start(struct rhashtable_iter *iter) __acquires(RCU);
+void *rhashtable_walk_next(struct rhashtable_iter *iter);
+void rhashtable_walk_stop(struct rhashtable_iter *iter) __releases(RCU);
+
 void rhashtable_destroy(struct rhashtable *ht);
 
 #define rht_dereference(p, ht) \
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 904b419..0579191 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -484,6 +484,7 @@ static void rht_deferred_worker(struct work_struct *work)
 {
 	struct rhashtable *ht;
 	struct bucket_table *tbl;
+	struct rhashtable_walker *walker;
 
 	ht = container_of(work, struct rhashtable, run_work);
 	mutex_lock(&ht->mutex);
@@ -492,6 +493,9 @@ static void rht_deferred_worker(struct work_struct *work)
 
 	tbl = rht_dereference(ht->tbl, ht);
 
+	list_for_each_entry(walker, &ht->walkers, list)
+		walker->resize = true;
+
 	if (ht->p.grow_decision && ht->p.grow_decision(ht, tbl->size))
 		rhashtable_expand(ht);
 	else if (ht->p.shrink_decision && ht->p.shrink_decision(ht, tbl->size))
@@ -822,6 +826,164 @@ exit:
 }
 EXPORT_SYMBOL_GPL(rhashtable_lookup_compare_insert);
 
+/**
+ * rhashtable_walk_init - Initialise an iterator
+ * @ht:		Table to walk over
+ * @iter:	Hash table Iterator
+ *
+ * This function prepares a hash table walk.
+ *
+ * Note that if you restart a walk after rhashtable_walk_stop you
+ * may see the same object twice.  Also, you may miss objects if
+ * there are removals in between rhashtable_walk_stop and the next
+ * call to rhashtable_walk_start.
+ *
+ * For a completely stable walk you should construct your own data
+ * structure outside the hash table.
+ *
+ * This function may sleep so you must not call it from interrupt
+ * context or with spin locks held.
+ *
+ * You must call rhashtable_walk_exit if this function returns
+ * successfully.
+ */
+int rhashtable_walk_init(struct rhashtable *ht, struct rhashtable_iter *iter)
+{
+	iter->ht = ht;
+	iter->p = NULL;
+	iter->slot = 0;
+	iter->skip = 0;
+
+	iter->walker = kmalloc(sizeof(*iter->walker), GFP_KERNEL);
+	if (!iter->walker)
+		return -ENOMEM;
+
+	mutex_lock(&ht->mutex);
+	list_add(&iter->walker->list, &ht->walkers);
+	mutex_unlock(&ht->mutex);
+
+	return 0;
+}
+EXPORT_SYMBOL_GPL(rhashtable_walk_init);
+
+/**
+ * rhashtable_walk_exit - Free an iterator
+ * @iter:	Hash table Iterator
+ *
+ * This function frees resources allocated by rhashtable_walk_init.
+ */
+void rhashtable_walk_exit(struct rhashtable_iter *iter)
+{
+	mutex_lock(&iter->ht->mutex);
+	list_del(&iter->walker->list);
+	mutex_unlock(&iter->ht->mutex);
+	kfree(iter->walker);
+}
+EXPORT_SYMBOL_GPL(rhashtable_walk_exit);
+
+/**
+ * rhashtable_walk_start - Start a hash table walk
+ * @iter:	Hash table iterator
+ *
+ * Start a hash table walk.  Note that we take the RCU lock in all
+ * cases including when we return an error.  So you must always call
+ * rhashtable_walk_stop to clean up.
+ *
+ * Returns zero if successful.
+ *
+ * Returns -EAGAIN if resize event occured.  Note that the iterator
+ * will rewind back to the beginning and you may use it immediately
+ * by calling rhashtable_walk_next.
+ */
+int rhashtable_walk_start(struct rhashtable_iter *iter)
+{
+	rcu_read_lock();
+
+	if (iter->walker->resize) {
+		iter->slot = 0;
+		iter->skip = 0;
+		iter->walker->resize = false;
+		return -EAGAIN;
+	}
+
+	return 0;
+}
+EXPORT_SYMBOL_GPL(rhashtable_walk_start);
+
+/**
+ * rhashtable_walk_next - Return the next object and advance the iterator
+ * @iter:	Hash table iterator
+ *
+ * Note that you must call rhashtable_walk_stop when you are finished
+ * with the walk.
+ *
+ * Returns the next object or NULL when the end of the table is reached.
+ *
+ * Returns -EAGAIN if resize event occured.  Note that the iterator
+ * will rewind back to the beginning and you may continue to use it.
+ */
+void *rhashtable_walk_next(struct rhashtable_iter *iter)
+{
+	const struct bucket_table *tbl;
+	struct rhashtable *ht = iter->ht;
+	struct rhash_head *p = iter->p;
+	void *obj = NULL;
+
+	tbl = rht_dereference_rcu(ht->tbl, ht);
+
+	if (p) {
+		p = rht_dereference_bucket_rcu(p->next, tbl, iter->slot);
+		goto next;
+	}
+
+	for (; iter->slot < tbl->size; iter->slot++) {
+		int skip = iter->skip;
+
+		rht_for_each_rcu(p, tbl, iter->slot) {
+			if (!skip)
+				break;
+			skip--;
+		}
+
+next:
+		if (!rht_is_a_nulls(p)) {
+			iter->skip++;
+			iter->p = p;
+			obj = rht_obj(ht, p);
+			goto out;
+		}
+
+		iter->skip = 0;
+	}
+
+	iter->p = NULL;
+
+out:
+	if (iter->walker->resize) {
+		iter->p = NULL;
+		iter->slot = 0;
+		iter->skip = 0;
+		iter->walker->resize = false;
+		return ERR_PTR(-EAGAIN);
+	}
+
+	return obj;
+}
+EXPORT_SYMBOL_GPL(rhashtable_walk_next);
+
+/**
+ * rhashtable_walk_stop - Finish a hash table walk
+ * @iter:	Hash table iterator
+ *
+ * Finish a hash table walk.
+ */
+void rhashtable_walk_stop(struct rhashtable_iter *iter)
+{
+	rcu_read_unlock();
+	iter->p = NULL;
+}
+EXPORT_SYMBOL_GPL(rhashtable_walk_stop);
+
 static size_t rounded_hashtable_size(struct rhashtable_params *params)
 {
 	return max(roundup_pow_of_two(params->nelem_hint * 4 / 3),
@@ -894,6 +1056,7 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 	memset(ht, 0, sizeof(*ht));
 	mutex_init(&ht->mutex);
 	memcpy(&ht->p, params, sizeof(*params));
+	INIT_LIST_HEAD(&ht->walkers);
 
 	if (params->locks_mul)
 		ht->p.locks_mul = roundup_pow_of_two(params->locks_mul);

[PATCH 3/4] netlink: Use rhashtable walk iterator

[Herbert Xu]

This patch gets rid of the manual rhashtable walk in netlink
which touches rhashtable internals that should not be exposed.
It does so by using the rhashtable iterator primitives.

In fact the existing code was very buggy.  Some sockets weren't
shown at all while others were shown more than once.
 
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---

 net/netlink/af_netlink.c |  130 +++++++++++++++++++++++------------------------
 1 file changed, 64 insertions(+), 66 deletions(-)

diff --git a/net/netlink/af_netlink.c b/net/netlink/af_netlink.c
index a36777b..1558548 100644
--- a/net/netlink/af_netlink.c
+++ b/net/netlink/af_netlink.c
@@ -2886,99 +2886,97 @@ EXPORT_SYMBOL(nlmsg_notify);
 #ifdef CONFIG_PROC_FS
 struct nl_seq_iter {
 	struct seq_net_private p;
+	struct rhashtable_iter hti;
 	int link;
-	int hash_idx;
 };
 
-static struct sock *netlink_seq_socket_idx(struct seq_file *seq, loff_t pos)
+static int netlink_walk_start(struct nl_seq_iter *iter)
 {
-	struct nl_seq_iter *iter = seq->private;
-	int i, j;
-	struct netlink_sock *nlk;
-	struct sock *s;
-	loff_t off = 0;
-
-	for (i = 0; i < MAX_LINKS; i++) {
-		struct rhashtable *ht = &nl_table[i].hash;
-		const struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
-
-		for (j = 0; j < tbl->size; j++) {
-			struct rhash_head *node;
-
-			rht_for_each_entry_rcu(nlk, node, tbl, j, node) {
-				s = (struct sock *)nlk;
+	int err;
 
-				if (sock_net(s) != seq_file_net(seq))
-					continue;
-				if (off == pos) {
-					iter->link = i;
-					iter->hash_idx = j;
-					return s;
-				}
-				++off;
-			}
-		}
+	err = rhashtable_walk_init(&nl_table[iter->link].hash, &iter->hti);
+	if (err) {
+		iter->link = MAX_LINKS;
+		return err;
 	}
-	return NULL;
+
+	err = rhashtable_walk_start(&iter->hti);
+	return err == -EAGAIN ? 0 : err;
 }
 
-static void *netlink_seq_start(struct seq_file *seq, loff_t *pos)
-	__acquires(RCU)
+static void netlink_walk_stop(struct nl_seq_iter *iter)
 {
-	rcu_read_lock();
-	return *pos ? netlink_seq_socket_idx(seq, *pos - 1) : SEQ_START_TOKEN;
+	rhashtable_walk_stop(&iter->hti);
+	rhashtable_walk_exit(&iter->hti);
 }
 
-static void *netlink_seq_next(struct seq_file *seq, void *v, loff_t *pos)
+static void *__netlink_seq_next(struct seq_file *seq)
 {
-	struct rhashtable *ht;
-	const struct bucket_table *tbl;
-	struct rhash_head *node;
+	struct nl_seq_iter *iter = seq->private;
 	struct netlink_sock *nlk;
-	struct nl_seq_iter *iter;
-	struct net *net;
-	int i, j;
 
-	++*pos;
+	do {
+		for (;;) {
+			int err;
 
-	if (v == SEQ_START_TOKEN)
-		return netlink_seq_socket_idx(seq, 0);
+			nlk = rhashtable_walk_next(&iter->hti);
 
-	net = seq_file_net(seq);
-	iter = seq->private;
-	nlk = v;
+			if (IS_ERR(nlk)) {
+				if (PTR_ERR(nlk) == -EAGAIN)
+					continue;
 
-	i = iter->link;
-	ht = &nl_table[i].hash;
-	tbl = rht_dereference_rcu(ht->tbl, ht);
-	rht_for_each_entry_rcu_continue(nlk, node, nlk->node.next, tbl, iter->hash_idx, node)
-		if (net_eq(sock_net((struct sock *)nlk), net))
-			return nlk;
+				return nlk;
+			}
 
-	j = iter->hash_idx + 1;
+			if (nlk)
+				break;
 
-	do {
+			netlink_walk_stop(iter);
+			if (++iter->link >= MAX_LINKS)
+				return NULL;
 
-		for (; j < tbl->size; j++) {
-			rht_for_each_entry_rcu(nlk, node, tbl, j, node) {
-				if (net_eq(sock_net((struct sock *)nlk), net)) {
-					iter->link = i;
-					iter->hash_idx = j;
-					return nlk;
-				}
-			}
+			err = netlink_walk_start(iter);
+			if (err)
+				return ERR_PTR(err);
 		}
+	} while (sock_net(&nlk->sk) != seq_file_net(seq));
 
-		j = 0;
-	} while (++i < MAX_LINKS);
+	return nlk;
+}
 
-	return NULL;
+static void *netlink_seq_start(struct seq_file *seq, loff_t *posp)
+{
+	struct nl_seq_iter *iter = seq->private;
+	void *obj = SEQ_START_TOKEN;
+	loff_t pos;
+	int err;
+
+	iter->link = 0;
+
+	err = netlink_walk_start(iter);
+	if (err)
+		return ERR_PTR(err);
+
+	for (pos = *posp; pos && obj && !IS_ERR(obj); pos--)
+		obj = __netlink_seq_next(seq);
+
+	return obj;
+}
+
+static void *netlink_seq_next(struct seq_file *seq, void *v, loff_t *pos)
+{
+	++*pos;
+	return __netlink_seq_next(seq);
 }
 
 static void netlink_seq_stop(struct seq_file *seq, void *v)
-	__releases(RCU)
 {
-	rcu_read_unlock();
+	struct nl_seq_iter *iter = seq->private;
+
+	if (iter->link >= MAX_LINKS)
+		return;
+
+	netlink_walk_stop(iter);
 }
 
 

[PATCH 4/4] netfilter: Use rhashtable walk iterator

[Herbert Xu]

This patch gets rid of the manual rhashtable walk in nft_hash
which touches rhashtable internals that should not be exposed.
It does so by using the rhashtable iterator primitives.

Note that I'm leaving nft_hash_destroy alone since it's only
invoked on shutdown and it shouldn't be affected by changes
to rhashtable internals (or at least not what I'm planning to
change).
 
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---

 net/netfilter/nft_hash.c |   53 +++++++++++++++++++++++++++++++----------------
 1 file changed, 36 insertions(+), 17 deletions(-)

diff --git a/net/netfilter/nft_hash.c b/net/netfilter/nft_hash.c
index 75887d7..61e6c40 100644
--- a/net/netfilter/nft_hash.c
+++ b/net/netfilter/nft_hash.c
@@ -130,31 +130,50 @@ static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set,
 			  struct nft_set_iter *iter)
 {
 	struct rhashtable *priv = nft_set_priv(set);
-	const struct bucket_table *tbl;
 	const struct nft_hash_elem *he;
+	struct rhashtable_iter hti;
 	struct nft_set_elem elem;
-	unsigned int i;
+	int err;
 
-	tbl = rht_dereference_rcu(priv->tbl, priv);
-	for (i = 0; i < tbl->size; i++) {
-		struct rhash_head *pos;
+	err = rhashtable_walk_init(priv, &hti);
+	iter->err = err;
+	if (err)
+		return;
+
+	err = rhashtable_walk_start(&hti);
+	if (err && err != -EAGAIN) {
+		iter->err = err;
+		goto out;
+	}
 
-		rht_for_each_entry_rcu(he, pos, tbl, i, node) {
-			if (iter->count < iter->skip)
-				goto cont;
+	while ((he = rhashtable_walk_next(&hti))) {
+		if (IS_ERR(he)) {
+			err = PTR_ERR(he);
+			if (err != -EAGAIN) {
+				iter->err = err;
+				goto out;
+			}
+		}
+
+		if (iter->count < iter->skip)
+			goto cont;
+
+		memcpy(&elem.key, &he->key, sizeof(elem.key));
+		if (set->flags & NFT_SET_MAP)
+			memcpy(&elem.data, he->data, sizeof(elem.data));
+		elem.flags = 0;
 
-			memcpy(&elem.key, &he->key, sizeof(elem.key));
-			if (set->flags & NFT_SET_MAP)
-				memcpy(&elem.data, he->data, sizeof(elem.data));
-			elem.flags = 0;
+		iter->err = iter->fn(ctx, set, iter, &elem);
+		if (iter->err < 0)
+			goto out;
 
-			iter->err = iter->fn(ctx, set, iter, &elem);
-			if (iter->err < 0)
-				return;
 cont:
-			iter->count++;
-		}
+		iter->count++;
 	}
+
+out:
+	rhashtable_walk_stop(&hti);
+	rhashtable_walk_exit(&hti);
 }
 
 static unsigned int nft_hash_privsize(const struct nlattr * const nla[])

Re: [PATCH 3/4] netlink: Use rhashtable walk iterator

[Thomas Graf]

On 02/04/15 at 07:33am, Herbert Xu wrote:
> This patch gets rid of the manual rhashtable walk in netlink
> which touches rhashtable internals that should not be exposed.
> It does so by using the rhashtable iterator primitives.
> 
> In fact the existing code was very buggy.  Some sockets weren't
> shown at all while others were shown more than once.
>  
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

I tested these patches. Only thing I found are these sparse
warnings:

net/netlink/af_netlink.c:2893:12: warning: context imbalance in 'netlink_walk_start' - different lock contexts for basic block
net/netlink/af_netlink.c:2907:13: warning: context imbalance in 'netlink_walk_stop' - unexpected unlock

Re: [PATCH 0/4] rhashtable: Add iterators and use them

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Wed, 4 Feb 2015 07:32:13 +1100

> On Wed, Feb 04, 2015 at 07:17:50AM +1100, Herbert Xu wrote:
>> 
>> > ERROR: "rhashtable_walk_start" [net/netfilter/nft_hash.ko] undefined!
>> 
>> Oops, I missed an export on that symbol.  I'll fix it up and
>> repost.
> 
> OK here is the repost without the hash_rnd patch.
> 
> The first patch fixes a potential crash with nft_hash destroying
> the table during a shrinking process.  While the next patch adds
> rhashtable iterators to replace current manual walks used by
> netlink and netfilter.  The final two patches make use of these
> iterators in netlink and netfilter.

Series applied to net-next.

Please address the sparse locking warnings reported against patch #3, it's
probably just some missing acquire/release annotations.

rhashtable: Move hash_rnd into bucket_table

[Herbert Xu]

Currently hash_rnd is a parameter that users can set.  However,
no existing users set this parameter.  It is also something that
people are unlikely to want to set directly since it's just a
random number.

In preparation for allowing the reseeding/rehashing of rhashtable,
this patch moves hash_rnd into bucket_table so that it's now an
internal state rather than a parameter.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index d438eeb..5ef8ea5 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -49,12 +49,14 @@ struct rhash_head {
 /**
  * struct bucket_table - Table of hash buckets
  * @size: Number of hash buckets
+ * @hash_rnd: Random seed to fold into hash
  * @locks_mask: Mask to apply before accessing locks[]
  * @locks: Array of spinlocks protecting individual buckets
  * @buckets: size * hash buckets
  */
 struct bucket_table {
 	size_t			size;
+	u32			hash_rnd;
 	unsigned int		locks_mask;
 	spinlock_t		*locks;
 
@@ -72,7 +74,6 @@ struct rhashtable;
  * @key_len: Length of key
  * @key_offset: Offset of key in struct to be hashed
  * @head_offset: Offset of rhash_head in struct to be hashed
- * @hash_rnd: Seed to use while hashing
  * @max_shift: Maximum number of shifts while expanding
  * @min_shift: Minimum number of shifts while shrinking
  * @nulls_base: Base value to generate nulls marker
@@ -85,7 +86,6 @@ struct rhashtable_params {
 	size_t			key_len;
 	size_t			key_offset;
 	size_t			head_offset;
-	u32			hash_rnd;
 	size_t			max_shift;
 	size_t			min_shift;
 	u32			nulls_base;
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index b5344ef..4ce267f 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -66,25 +66,28 @@ static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
 	return hash & (tbl->size - 1);
 }
 
-static u32 obj_raw_hashfn(const struct rhashtable *ht, const void *ptr)
+static u32 obj_raw_hashfn(struct rhashtable *ht, const void *ptr)
 {
+	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 	u32 hash;
 
 	if (unlikely(!ht->p.key_len))
-		hash = ht->p.obj_hashfn(ptr, ht->p.hash_rnd);
+		hash = ht->p.obj_hashfn(ptr, tbl->hash_rnd);
 	else
 		hash = ht->p.hashfn(ptr + ht->p.key_offset, ht->p.key_len,
-				    ht->p.hash_rnd);
+				    tbl->hash_rnd);
 
 	return hash >> HASH_RESERVED_SPACE;
 }
 
 static u32 key_hashfn(struct rhashtable *ht, const void *key, u32 len)
 {
-	return ht->p.hashfn(key, len, ht->p.hash_rnd) >> HASH_RESERVED_SPACE;
+	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
+
+	return ht->p.hashfn(key, len, tbl->hash_rnd) >> HASH_RESERVED_SPACE;
 }
 
-static u32 head_hashfn(const struct rhashtable *ht,
+static u32 head_hashfn(struct rhashtable *ht,
 		       const struct bucket_table *tbl,
 		       const struct rhash_head *he)
 {
@@ -92,7 +95,7 @@ static u32 head_hashfn(const struct rhashtable *ht,
 }
 
 #ifdef CONFIG_PROVE_LOCKING
-static void debug_dump_buckets(const struct rhashtable *ht,
+static void debug_dump_buckets(struct rhashtable *ht,
 			       const struct bucket_table *tbl)
 {
 	struct rhash_head *he;
@@ -1099,14 +1102,13 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 	if (tbl == NULL)
 		return -ENOMEM;
 
+	get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
+
 	atomic_set(&ht->nelems, 0);
 	atomic_set(&ht->shift, ilog2(tbl->size));
 	RCU_INIT_POINTER(ht->tbl, tbl);
 	RCU_INIT_POINTER(ht->future_tbl, tbl);
 
-	if (!ht->p.hash_rnd)
-		get_random_bytes(&ht->p.hash_rnd, sizeof(ht->p.hash_rnd));
-
 	INIT_WORK(&ht->run_work, rht_deferred_worker);
 
 	return 0;
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [RFC] rhashtable: rhashtable_rehash

[Herbert Xu]

Just going through old emails so this may no longer be relevant.

On Mon, Feb 02, 2015 at 11:16:47AM +0000, Thomas Graf wrote:
> On 01/31/15 at 09:23pm, Herbert Xu wrote:
> > +	new_hash = head_hashfn(ht, new_tbl, entry);
> > +
> > +	new_bucket_lock = bucket_lock(new_tbl, new_hash);
> > +
> > +	spin_lock(new_bucket_lock);
> 
> I realize this is WIP and not fully worked out yet, therefore just a
> thought:
> 
> Unless you change this fundamentally then locking just the new bucket
> lock based on the new hash is not sufficient when you rehash while growing
> as the old bucket will contain entries which will get distributed across
> 2 buckets in the new table and if we change the seed it will map to
> even more buckets. I assume you have an idea how to handle that.

This doesn't matter because we're doing the resize one entry at
a time.  IOW we're moving one entry from the old table to the
new table.  The lock is only needed to avoid parallel additions
to the same bucket in the new table.

Removals will need to scan the old table followed by the new table
just like lookups so they don't care.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: rhashtable: Move hash_rnd into bucket_table

[Daniel Borkmann]

On 03/09/2015 10:58 AM, Herbert Xu wrote:
> Currently hash_rnd is a parameter that users can set.  However,
> no existing users set this parameter.  It is also something that
> people are unlikely to want to set directly since it's just a
> random number.

I believe the original purpose was to have reproduceability, but
yeah, there are no users of it currently.

> In preparation for allowing the reseeding/rehashing of rhashtable,
> this patch moves hash_rnd into bucket_table so that it's now an
> internal state rather than a parameter.
>
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
>
> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
> index d438eeb..5ef8ea5 100644
> --- a/include/linux/rhashtable.h
> +++ b/include/linux/rhashtable.h
> @@ -49,12 +49,14 @@ struct rhash_head {
>   /**
>    * struct bucket_table - Table of hash buckets
>    * @size: Number of hash buckets
> + * @hash_rnd: Random seed to fold into hash
>    * @locks_mask: Mask to apply before accessing locks[]
>    * @locks: Array of spinlocks protecting individual buckets
>    * @buckets: size * hash buckets
>    */
>   struct bucket_table {
>   	size_t			size;
> +	u32			hash_rnd;
>   	unsigned int		locks_mask;
>   	spinlock_t		*locks;
>
> @@ -72,7 +74,6 @@ struct rhashtable;
>    * @key_len: Length of key
>    * @key_offset: Offset of key in struct to be hashed
>    * @head_offset: Offset of rhash_head in struct to be hashed
> - * @hash_rnd: Seed to use while hashing
>    * @max_shift: Maximum number of shifts while expanding
>    * @min_shift: Minimum number of shifts while shrinking
>    * @nulls_base: Base value to generate nulls marker
> @@ -85,7 +86,6 @@ struct rhashtable_params {
>   	size_t			key_len;
>   	size_t			key_offset;
>   	size_t			head_offset;
> -	u32			hash_rnd;
>   	size_t			max_shift;
>   	size_t			min_shift;
>   	u32			nulls_base;
> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index b5344ef..4ce267f 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -66,25 +66,28 @@ static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
>   	return hash & (tbl->size - 1);
>   }
>
> -static u32 obj_raw_hashfn(const struct rhashtable *ht, const void *ptr)
> +static u32 obj_raw_hashfn(struct rhashtable *ht, const void *ptr)
>   {
> +	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);

const

>   	u32 hash;
>
>   	if (unlikely(!ht->p.key_len))
> -		hash = ht->p.obj_hashfn(ptr, ht->p.hash_rnd);
> +		hash = ht->p.obj_hashfn(ptr, tbl->hash_rnd);
>   	else
>   		hash = ht->p.hashfn(ptr + ht->p.key_offset, ht->p.key_len,
> -				    ht->p.hash_rnd);
> +				    tbl->hash_rnd);
>
>   	return hash >> HASH_RESERVED_SPACE;
>   }
>
>   static u32 key_hashfn(struct rhashtable *ht, const void *key, u32 len)
>   {
> -	return ht->p.hashfn(key, len, ht->p.hash_rnd) >> HASH_RESERVED_SPACE;
> +	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
> +

const

> +	return ht->p.hashfn(key, len, tbl->hash_rnd) >> HASH_RESERVED_SPACE;
>   }
>
> -static u32 head_hashfn(const struct rhashtable *ht,
> +static u32 head_hashfn(struct rhashtable *ht,
>   		       const struct bucket_table *tbl,
>   		       const struct rhash_head *he)
>   {
> @@ -92,7 +95,7 @@ static u32 head_hashfn(const struct rhashtable *ht,
>   }
>
>   #ifdef CONFIG_PROVE_LOCKING
> -static void debug_dump_buckets(const struct rhashtable *ht,
> +static void debug_dump_buckets(struct rhashtable *ht,
>   			       const struct bucket_table *tbl)
>   {
>   	struct rhash_head *he;
> @@ -1099,14 +1102,13 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
>   	if (tbl == NULL)
>   		return -ENOMEM;
>
> +	get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
> +

Have you tested this patch? ;-)

If I see this correctly, the first time you shrink or expand, your hash_rnd
from then onwards will constantly be 0.

You need to copy over the above old hash_rnd to the new one from the newly
allocated tbl. So, bucket_table_alloc() needs a change as well. Of course,
with rehashing, the get_random_bytes() would directly move there.

>   	atomic_set(&ht->nelems, 0);
>   	atomic_set(&ht->shift, ilog2(tbl->size));
>   	RCU_INIT_POINTER(ht->tbl, tbl);
>   	RCU_INIT_POINTER(ht->future_tbl, tbl);
>
> -	if (!ht->p.hash_rnd)
> -		get_random_bytes(&ht->p.hash_rnd, sizeof(ht->p.hash_rnd));
> -
>   	INIT_WORK(&ht->run_work, rht_deferred_worker);
>
>   	return 0;
>

Re: rhashtable: Move hash_rnd into bucket_table

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Mon, 9 Mar 2015 20:58:33 +1100

> Currently hash_rnd is a parameter that users can set.  However,
> no existing users set this parameter.  It is also something that
> people are unlikely to want to set directly since it's just a
> random number.
> 
> In preparation for allowing the reseeding/rehashing of rhashtable,
> this patch moves hash_rnd into bucket_table so that it's now an
> internal state rather than a parameter.
> 
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Thomas is right, you're going to have to move the hash_rnd initialization
to where we allocate the bucket tables, otherwise the first shrink/expand
will set it to zero.

Re: rhashtable: Move hash_rnd into bucket_table

[David Miller]

From: David Miller <davem@redhat.com>
Date: Mon, 09 Mar 2015 15:51:37 -0400 (EDT)

> From: Herbert Xu <herbert@gondor.apana.org.au>
> Date: Mon, 9 Mar 2015 20:58:33 +1100
> 
>> Currently hash_rnd is a parameter that users can set.  However,
>> no existing users set this parameter.  It is also something that
>> people are unlikely to want to set directly since it's just a
>> random number.
>> 
>> In preparation for allowing the reseeding/rehashing of rhashtable,
>> this patch moves hash_rnd into bucket_table so that it's now an
>> internal state rather than a parameter.
>> 
>> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
> 
> Thomas is right, you're going to have to move the hash_rnd initialization
> to where we allocate the bucket tables, otherwise the first shrink/expand
> will set it to zero.

My bad, Daniel pointed this out, not Thomas.

Sorry about that.

Re: rhashtable: Move hash_rnd into bucket_table

[Herbert Xu]

On Mon, Mar 09, 2015 at 05:26:52PM +0100, Daniel Borkmann wrote:
> 
> I believe the original purpose was to have reproduceability, but
> yeah, there are no users of it currently.

If anyone ever needed that we could always provide a way to set
the random value, through a rehash.
 
> Have you tested this patch? ;-)

Clearly not :)

> If I see this correctly, the first time you shrink or expand, your hash_rnd
> from then onwards will constantly be 0.
> 
> You need to copy over the above old hash_rnd to the new one from the newly
> allocated tbl. So, bucket_table_alloc() needs a change as well. Of course,
> with rehashing, the get_random_bytes() would directly move there.

Yes it should copy them.  I've fixed in my tree now and it actually
works!

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[PATCH 0/2] rhashtable: Arbitrary rehashing

[Herbert Xu]

Hi Dave:

These two patches implement arbitrary rehashing in rhashtable.  The
idea is based on the hashtable in net/bridge/br_multicast.c plus
the suggestion by Josh Triplett to avoid using two linked lists.

I have tested it using netlink but obviously more testing especially
using netfilter would be welcome.

After this I would like to explore the idea of allowing multiple
rehashes in parallel.  This would allow us to not have to rehash
synchronously when the table gets too big and the previous rehash
hasn't finished.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[PATCH 1/2] rhashtable: Move hash_rnd into bucket_table

[Herbert Xu]

Currently hash_rnd is a parameter that users can set.  However,
no existing users set this parameter.  It is also something that
people are unlikely to want to set directly since it's just a
random number.

In preparation for allowing the reseeding/rehashing of rhashtable,
this patch moves hash_rnd into bucket_table so that it's now an
internal state rather than a parameter.

Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
---

 include/linux/rhashtable.h |    4 ++--
 lib/rhashtable.c           |   24 +++++++++++++++---------
 2 files changed, 17 insertions(+), 11 deletions(-)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index d438eeb..5ef8ea5 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -49,12 +49,14 @@ struct rhash_head {
 /**
  * struct bucket_table - Table of hash buckets
  * @size: Number of hash buckets
+ * @hash_rnd: Random seed to fold into hash
  * @locks_mask: Mask to apply before accessing locks[]
  * @locks: Array of spinlocks protecting individual buckets
  * @buckets: size * hash buckets
  */
 struct bucket_table {
 	size_t			size;
+	u32			hash_rnd;
 	unsigned int		locks_mask;
 	spinlock_t		*locks;
 
@@ -72,7 +74,6 @@ struct rhashtable;
  * @key_len: Length of key
  * @key_offset: Offset of key in struct to be hashed
  * @head_offset: Offset of rhash_head in struct to be hashed
- * @hash_rnd: Seed to use while hashing
  * @max_shift: Maximum number of shifts while expanding
  * @min_shift: Minimum number of shifts while shrinking
  * @nulls_base: Base value to generate nulls marker
@@ -85,7 +86,6 @@ struct rhashtable_params {
 	size_t			key_len;
 	size_t			key_offset;
 	size_t			head_offset;
-	u32			hash_rnd;
 	size_t			max_shift;
 	size_t			min_shift;
 	u32			nulls_base;
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index b5344ef..ba15dce 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -66,25 +66,28 @@ static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
 	return hash & (tbl->size - 1);
 }
 
-static u32 obj_raw_hashfn(const struct rhashtable *ht, const void *ptr)
+static u32 obj_raw_hashfn(struct rhashtable *ht, const void *ptr)
 {
+	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 	u32 hash;
 
 	if (unlikely(!ht->p.key_len))
-		hash = ht->p.obj_hashfn(ptr, ht->p.hash_rnd);
+		hash = ht->p.obj_hashfn(ptr, tbl->hash_rnd);
 	else
 		hash = ht->p.hashfn(ptr + ht->p.key_offset, ht->p.key_len,
-				    ht->p.hash_rnd);
+				    tbl->hash_rnd);
 
 	return hash >> HASH_RESERVED_SPACE;
 }
 
 static u32 key_hashfn(struct rhashtable *ht, const void *key, u32 len)
 {
-	return ht->p.hashfn(key, len, ht->p.hash_rnd) >> HASH_RESERVED_SPACE;
+	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
+
+	return ht->p.hashfn(key, len, tbl->hash_rnd) >> HASH_RESERVED_SPACE;
 }
 
-static u32 head_hashfn(const struct rhashtable *ht,
+static u32 head_hashfn(struct rhashtable *ht,
 		       const struct bucket_table *tbl,
 		       const struct rhash_head *he)
 {
@@ -92,7 +95,7 @@ static u32 head_hashfn(const struct rhashtable *ht,
 }
 
 #ifdef CONFIG_PROVE_LOCKING
-static void debug_dump_buckets(const struct rhashtable *ht,
+static void debug_dump_buckets(struct rhashtable *ht,
 			       const struct bucket_table *tbl)
 {
 	struct rhash_head *he;
@@ -385,6 +388,8 @@ int rhashtable_expand(struct rhashtable *ht)
 	if (new_tbl == NULL)
 		return -ENOMEM;
 
+	new_tbl->hash_rnd = old_tbl->hash_rnd;
+
 	atomic_inc(&ht->shift);
 
 	/* Make insertions go into the new, empty table right away. Deletions
@@ -476,6 +481,8 @@ int rhashtable_shrink(struct rhashtable *ht)
 	if (new_tbl == NULL)
 		return -ENOMEM;
 
+	new_tbl->hash_rnd = tbl->hash_rnd;
+
 	rcu_assign_pointer(ht->future_tbl, new_tbl);
 	synchronize_rcu();
 
@@ -1099,14 +1106,13 @@ int rhashtable_init(struct rhashtable *ht, struct rhashtable_params *params)
 	if (tbl == NULL)
 		return -ENOMEM;
 
+	get_random_bytes(&tbl->hash_rnd, sizeof(tbl->hash_rnd));
+
 	atomic_set(&ht->nelems, 0);
 	atomic_set(&ht->shift, ilog2(tbl->size));
 	RCU_INIT_POINTER(ht->tbl, tbl);
 	RCU_INIT_POINTER(ht->future_tbl, tbl);
 
-	if (!ht->p.hash_rnd)
-		get_random_bytes(&ht->p.hash_rnd, sizeof(ht->p.hash_rnd));
-
 	INIT_WORK(&ht->run_work, rht_deferred_worker);
 
 	return 0;

[PATCH 2/2] rhashtable: Add arbitrary rehash function

[Herbert Xu]

This patch adds a rehash function that supports the use of any
hash function for the new table.  This is needed to support changing
the random seed value during the lifetime of the hash table.

However for now the random seed value is still constant and the
rehash function is simply used to replace the existing expand/shrink
functions.

Signed-off-by: Herbert Xu <herbert.xu@redhat.com>
---

 lib/rhashtable.c |  445 ++++++++++++++++++++-----------------------------------
 1 file changed, 162 insertions(+), 283 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index ba15dce..639b04f 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -66,9 +66,9 @@ static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
 	return hash & (tbl->size - 1);
 }
 
-static u32 obj_raw_hashfn(struct rhashtable *ht, const void *ptr)
+static u32 obj_raw_hashfn(struct rhashtable *ht,
+			  const struct bucket_table *tbl, const void *ptr)
 {
-	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 	u32 hash;
 
 	if (unlikely(!ht->p.key_len))
@@ -80,10 +80,9 @@ static u32 obj_raw_hashfn(struct rhashtable *ht, const void *ptr)
 	return hash >> HASH_RESERVED_SPACE;
 }
 
-static u32 key_hashfn(struct rhashtable *ht, const void *key, u32 len)
+static u32 key_hashfn(struct rhashtable *ht, const struct bucket_table *tbl,
+		      const void *key, u32 len)
 {
-	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
-
 	return ht->p.hashfn(key, len, tbl->hash_rnd) >> HASH_RESERVED_SPACE;
 }
 
@@ -91,7 +90,7 @@ static u32 head_hashfn(struct rhashtable *ht,
 		       const struct bucket_table *tbl,
 		       const struct rhash_head *he)
 {
-	return rht_bucket_index(tbl, obj_raw_hashfn(ht, rht_obj(ht, he)));
+	return rht_bucket_index(tbl, obj_raw_hashfn(ht, tbl, rht_obj(ht, he)));
 }
 
 #ifdef CONFIG_PROVE_LOCKING
@@ -165,18 +164,6 @@ EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
 #endif
 
 
-static struct rhash_head __rcu **bucket_tail(struct bucket_table *tbl, u32 n)
-{
-	struct rhash_head __rcu **pprev;
-
-	for (pprev = &tbl->buckets[n];
-	     !rht_is_a_nulls(rht_dereference_bucket(*pprev, tbl, n));
-	     pprev = &rht_dereference_bucket(*pprev, tbl, n)->next)
-		;
-
-	return pprev;
-}
-
 static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl)
 {
 	unsigned int i, size;
@@ -270,101 +257,99 @@ static bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size)
 	       (atomic_read(&ht->shift) > ht->p.min_shift);
 }
 
-static void lock_buckets(struct bucket_table *new_tbl,
-			 struct bucket_table *old_tbl, unsigned int hash)
-	__acquires(old_bucket_lock)
+static int rhashtable_rehash_one(struct rhashtable *ht, unsigned old_hash)
 {
-	spin_lock_bh(bucket_lock(old_tbl, hash));
-	if (new_tbl != old_tbl)
-		spin_lock_bh_nested(bucket_lock(new_tbl, hash),
-				    RHT_LOCK_NESTED);
-}
+	struct bucket_table *new_tbl = rht_dereference(ht->future_tbl, ht);
+	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
+	struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];
+	int err = -ENOENT;
+	struct rhash_head *head, *next, *entry;
+	spinlock_t *new_bucket_lock;
+	unsigned new_hash;
 
-static void unlock_buckets(struct bucket_table *new_tbl,
-			   struct bucket_table *old_tbl, unsigned int hash)
-	__releases(old_bucket_lock)
-{
-	if (new_tbl != old_tbl)
-		spin_unlock_bh(bucket_lock(new_tbl, hash));
-	spin_unlock_bh(bucket_lock(old_tbl, hash));
-}
+	rht_for_each(entry, old_tbl, old_hash) {
+		err = 0;
+		next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
 
-/**
- * Unlink entries on bucket which hash to different bucket.
- *
- * Returns true if no more work needs to be performed on the bucket.
- */
-static bool hashtable_chain_unzip(struct rhashtable *ht,
-				  const struct bucket_table *new_tbl,
-				  struct bucket_table *old_tbl,
-				  size_t old_hash)
-{
-	struct rhash_head *he, *p, *next;
-	unsigned int new_hash, new_hash2;
+		if (rht_is_a_nulls(next))
+			break;
 
-	ASSERT_BUCKET_LOCK(ht, old_tbl, old_hash);
+		pprev = &entry->next;
+	}
 
-	/* Old bucket empty, no work needed. */
-	p = rht_dereference_bucket(old_tbl->buckets[old_hash], old_tbl,
-				   old_hash);
-	if (rht_is_a_nulls(p))
-		return false;
+	if (err)
+		goto out;
 
-	new_hash = head_hashfn(ht, new_tbl, p);
-	ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
+	new_hash = head_hashfn(ht, new_tbl, entry);
 
-	/* Advance the old bucket pointer one or more times until it
-	 * reaches a node that doesn't hash to the same bucket as the
-	 * previous node p. Call the previous node p;
-	 */
-	rht_for_each_continue(he, p->next, old_tbl, old_hash) {
-		new_hash2 = head_hashfn(ht, new_tbl, he);
-		ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash2);
+	new_bucket_lock = bucket_lock(new_tbl, new_hash);
 
-		if (new_hash != new_hash2)
-			break;
-		p = he;
-	}
-	rcu_assign_pointer(old_tbl->buckets[old_hash], p->next);
+	spin_lock(new_bucket_lock);
+	head = rht_dereference_bucket(new_tbl->buckets[new_hash],
+				      new_tbl, new_hash);
 
-	/* Find the subsequent node which does hash to the same
-	 * bucket as node P, or NULL if no such node exists.
-	 */
-	INIT_RHT_NULLS_HEAD(next, ht, old_hash);
-	if (!rht_is_a_nulls(he)) {
-		rht_for_each_continue(he, he->next, old_tbl, old_hash) {
-			if (head_hashfn(ht, new_tbl, he) == new_hash) {
-				next = he;
-				break;
-			}
-		}
-	}
+	if (rht_is_a_nulls(head))
+		INIT_RHT_NULLS_HEAD(entry->next, ht, new_hash);
+	else
+		RCU_INIT_POINTER(entry->next, head);
 
-	/* Set p's next pointer to that subsequent node pointer,
-	 * bypassing the nodes which do not hash to p's bucket
-	 */
-	rcu_assign_pointer(p->next, next);
+	rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
+	spin_unlock(new_bucket_lock);
+
+	rcu_assign_pointer(*pprev, next);
+
+out:
+	return err;
+}
+
+static void rhashtable_rehash_chain(struct rhashtable *ht, unsigned old_hash)
+{
+	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
+	spinlock_t *old_bucket_lock;
 
-	p = rht_dereference_bucket(old_tbl->buckets[old_hash], old_tbl,
-				   old_hash);
+	old_bucket_lock = bucket_lock(old_tbl, old_hash);
 
-	return !rht_is_a_nulls(p);
+	spin_lock_bh(old_bucket_lock);
+	while (!rhashtable_rehash_one(ht, old_hash))
+		;
+	spin_unlock_bh(old_bucket_lock);
 }
 
-static void link_old_to_new(struct rhashtable *ht, struct bucket_table *new_tbl,
-			    unsigned int new_hash, struct rhash_head *entry)
+static void rhashtable_rehash(struct rhashtable *ht,
+			      struct bucket_table *new_tbl)
 {
-	ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
+	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
+	unsigned old_hash;
+
+	get_random_bytes(&new_tbl->hash_rnd, sizeof(new_tbl->hash_rnd));
+
+	/* Make insertions go into the new, empty table right away. Deletions
+	 * and lookups will be attempted in both tables until we synchronize.
+	 * The synchronize_rcu() guarantees for the new table to be picked up
+	 * so no new additions go into the old table while we relink.
+	 */
+	rcu_assign_pointer(ht->future_tbl, new_tbl);
+
+	for (old_hash = 0; old_hash < old_tbl->size; old_hash++)
+		rhashtable_rehash_chain(ht, old_hash);
+
+	/* Publish the new table pointer. */
+	rcu_assign_pointer(ht->tbl, new_tbl);
+
+	/* Wait for readers. All new readers will see the new
+	 * table, and thus no references to the old table will
+	 * remain.
+	 */
+	synchronize_rcu();
 
-	rcu_assign_pointer(*bucket_tail(new_tbl, new_hash), entry);
+	bucket_table_free(old_tbl);
 }
 
 /**
  * rhashtable_expand - Expand hash table while allowing concurrent lookups
  * @ht:		the hash table to expand
  *
- * A secondary bucket array is allocated and the hash entries are migrated
- * while keeping them on both lists until the end of the RCU grace period.
+ * A secondary bucket array is allocated and the hash entries are migrated.
  *
  * This function may only be called in a context where it is safe to call
  * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
@@ -378,9 +363,6 @@ static void link_old_to_new(struct rhashtable *ht, struct bucket_table *new_tbl,
 int rhashtable_expand(struct rhashtable *ht)
 {
 	struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
-	struct rhash_head *he;
-	unsigned int new_hash, old_hash;
-	bool complete = false;
 
 	ASSERT_RHT_MUTEX(ht);
 
@@ -392,64 +374,8 @@ int rhashtable_expand(struct rhashtable *ht)
 
 	atomic_inc(&ht->shift);
 
-	/* Make insertions go into the new, empty table right away. Deletions
-	 * and lookups will be attempted in both tables until we synchronize.
-	 * The synchronize_rcu() guarantees for the new table to be picked up
-	 * so no new additions go into the old table while we relink.
-	 */
-	rcu_assign_pointer(ht->future_tbl, new_tbl);
-	synchronize_rcu();
-
-	/* For each new bucket, search the corresponding old bucket for the
-	 * first entry that hashes to the new bucket, and link the end of
-	 * newly formed bucket chain (containing entries added to future
-	 * table) to that entry. Since all the entries which will end up in
-	 * the new bucket appear in the same old bucket, this constructs an
-	 * entirely valid new hash table, but with multiple buckets
-	 * "zipped" together into a single imprecise chain.
-	 */
-	for (new_hash = 0; new_hash < new_tbl->size; new_hash++) {
-		old_hash = rht_bucket_index(old_tbl, new_hash);
-		lock_buckets(new_tbl, old_tbl, new_hash);
-		rht_for_each(he, old_tbl, old_hash) {
-			if (head_hashfn(ht, new_tbl, he) == new_hash) {
-				link_old_to_new(ht, new_tbl, new_hash, he);
-				break;
-			}
-		}
-		unlock_buckets(new_tbl, old_tbl, new_hash);
-		cond_resched();
-	}
-
-	/* Unzip interleaved hash chains */
-	while (!complete && !ht->being_destroyed) {
-		/* Wait for readers. All new readers will see the new
-		 * table, and thus no references to the old table will
-		 * remain.
-		 */
-		synchronize_rcu();
-
-		/* For each bucket in the old table (each of which
-		 * contains items from multiple buckets of the new
-		 * table): ...
-		 */
-		complete = true;
-		for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
-			lock_buckets(new_tbl, old_tbl, old_hash);
-
-			if (hashtable_chain_unzip(ht, new_tbl, old_tbl,
-						  old_hash))
-				complete = false;
-
-			unlock_buckets(new_tbl, old_tbl, old_hash);
-			cond_resched();
-		}
-	}
-
-	rcu_assign_pointer(ht->tbl, new_tbl);
-	synchronize_rcu();
+	rhashtable_rehash(ht, new_tbl);
 
-	bucket_table_free(old_tbl);
 	return 0;
 }
 EXPORT_SYMBOL_GPL(rhashtable_expand);
@@ -473,7 +399,6 @@ EXPORT_SYMBOL_GPL(rhashtable_expand);
 int rhashtable_shrink(struct rhashtable *ht)
 {
 	struct bucket_table *new_tbl, *tbl = rht_dereference(ht->tbl, ht);
-	unsigned int new_hash;
 
 	ASSERT_RHT_MUTEX(ht);
 
@@ -483,39 +408,9 @@ int rhashtable_shrink(struct rhashtable *ht)
 
 	new_tbl->hash_rnd = tbl->hash_rnd;
 
-	rcu_assign_pointer(ht->future_tbl, new_tbl);
-	synchronize_rcu();
-
-	/* Link the first entry in the old bucket to the end of the
-	 * bucket in the new table. As entries are concurrently being
-	 * added to the new table, lock down the new bucket. As we
-	 * always divide the size in half when shrinking, each bucket
-	 * in the new table maps to exactly two buckets in the old
-	 * table.
-	 */
-	for (new_hash = 0; new_hash < new_tbl->size; new_hash++) {
-		lock_buckets(new_tbl, tbl, new_hash);
-
-		rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
-				   tbl->buckets[new_hash]);
-		ASSERT_BUCKET_LOCK(ht, tbl, new_hash + new_tbl->size);
-		rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
-				   tbl->buckets[new_hash + new_tbl->size]);
-
-		unlock_buckets(new_tbl, tbl, new_hash);
-		cond_resched();
-	}
-
-	/* Publish the new, valid hash table */
-	rcu_assign_pointer(ht->tbl, new_tbl);
 	atomic_dec(&ht->shift);
 
-	/* Wait for readers. No new readers will have references to the
-	 * old hash table.
-	 */
-	synchronize_rcu();
-
-	bucket_table_free(tbl);
+	rhashtable_rehash(ht, new_tbl);
 
 	return 0;
 }
@@ -545,18 +440,46 @@ unlock:
 	mutex_unlock(&ht->mutex);
 }
 
-static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
-				struct bucket_table *tbl,
-				const struct bucket_table *old_tbl, u32 hash)
+bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
+			 bool (*compare)(void *, void *), void *arg)
 {
-	bool no_resize_running = tbl == old_tbl;
+	struct bucket_table *tbl, *old_tbl;
 	struct rhash_head *head;
+	bool no_resize_running;
+	spinlock_t *lock;
+	unsigned hash;
+	bool success = true;
+
+	rcu_read_lock();
+
+	tbl = rht_dereference_rcu(ht->future_tbl, ht);
+
+	for (;;) {
+		hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+
+		lock = bucket_lock(tbl, hash);
+		spin_lock_bh(lock);
+
+		old_tbl = tbl;
+		tbl = rht_dereference_rcu(ht->future_tbl, ht);
+		if (tbl == old_tbl)
+			break;
+
+		spin_unlock_bh(lock);
+	}
+
+	if (compare &&
+	    rhashtable_lookup_compare(ht, rht_obj(ht, obj) + ht->p.key_offset,
+				      compare, arg)) {
+		success = false;
+		goto exit;
+	}
+
+	no_resize_running = tbl == rht_dereference_rcu(ht->tbl, ht);
 
 	hash = rht_bucket_index(tbl, hash);
 	head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
 
-	ASSERT_BUCKET_LOCK(ht, tbl, hash);
-
 	if (rht_is_a_nulls(head))
 		INIT_RHT_NULLS_HEAD(obj->next, ht, hash);
 	else
@@ -567,6 +490,13 @@ static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 	atomic_inc(&ht->nelems);
 	if (no_resize_running && rht_grow_above_75(ht, tbl->size))
 		schedule_work(&ht->run_work);
+
+exit:
+	spin_unlock_bh(lock);
+
+	rcu_read_unlock();
+
+	return success;
 }
 
 /**
@@ -586,22 +516,41 @@ static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
  */
 void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
 {
-	struct bucket_table *tbl, *old_tbl;
+	__rhashtable_insert(ht, obj, NULL, NULL);
+}
+EXPORT_SYMBOL_GPL(rhashtable_insert);
+
+bool __rhashtable_remove(struct rhashtable *ht, struct bucket_table *tbl,
+			 struct rhash_head *obj)
+{
+	struct rhash_head __rcu **pprev;
+	struct rhash_head *he;
+	spinlock_t * lock;
 	unsigned hash;
+	bool ret = false;
 
-	rcu_read_lock();
+	hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+	lock = bucket_lock(tbl, hash);
+	hash = rht_bucket_index(tbl, hash);
 
-	tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
+	spin_lock_bh(lock);
+
+	pprev = &tbl->buckets[hash];
+	rht_for_each(he, tbl, hash) {
+		if (he != obj) {
+			pprev = &he->next;
+			continue;
+		}
 
-	lock_buckets(tbl, old_tbl, hash);
-	__rhashtable_insert(ht, obj, tbl, old_tbl, hash);
-	unlock_buckets(tbl, old_tbl, hash);
+		rcu_assign_pointer(*pprev, obj->next);
+		ret = true;
+		break;
+	}
 
-	rcu_read_unlock();
+	spin_unlock_bh(lock);
+
+	return ret;
 }
-EXPORT_SYMBOL_GPL(rhashtable_insert);
 
 /**
  * rhashtable_remove - remove object from hash table
@@ -620,68 +569,22 @@ EXPORT_SYMBOL_GPL(rhashtable_insert);
  */
 bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
 {
-	struct bucket_table *tbl, *new_tbl, *old_tbl;
-	struct rhash_head __rcu **pprev;
-	struct rhash_head *he, *he2;
-	unsigned int hash, new_hash;
-	bool ret = false;
+	struct bucket_table *tbl, *old_tbl;
+	bool ret;
 
 	rcu_read_lock();
 	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	tbl = new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
-
-	lock_buckets(new_tbl, old_tbl, new_hash);
-restart:
-	hash = rht_bucket_index(tbl, new_hash);
-	pprev = &tbl->buckets[hash];
-	rht_for_each(he, tbl, hash) {
-		if (he != obj) {
-			pprev = &he->next;
-			continue;
-		}
-
-		ASSERT_BUCKET_LOCK(ht, tbl, hash);
-
-		if (old_tbl->size > new_tbl->size && tbl == old_tbl &&
-		    !rht_is_a_nulls(obj->next) &&
-		    head_hashfn(ht, tbl, obj->next) != hash) {
-			rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash));
-		} else if (unlikely(old_tbl->size < new_tbl->size && tbl == new_tbl)) {
-			rht_for_each_continue(he2, obj->next, tbl, hash) {
-				if (head_hashfn(ht, tbl, he2) == hash) {
-					rcu_assign_pointer(*pprev, he2);
-					goto found;
-				}
-			}
-
-			rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash));
-		} else {
-			rcu_assign_pointer(*pprev, obj->next);
-		}
-
-found:
-		ret = true;
-		break;
-	}
-
-	/* The entry may be linked in either 'tbl', 'future_tbl', or both.
-	 * 'future_tbl' only exists for a short period of time during
-	 * resizing. Thus traversing both is fine and the added cost is
-	 * very rare.
-	 */
-	if (tbl != old_tbl) {
-		tbl = old_tbl;
-		goto restart;
-	}
+	tbl = rht_dereference_rcu(ht->future_tbl, ht);
 
-	unlock_buckets(new_tbl, old_tbl, new_hash);
+	ret = __rhashtable_remove(ht, old_tbl, obj);
+	if (!ret && old_tbl != tbl)
+		ret = __rhashtable_remove(ht, tbl, obj);
 
 	if (ret) {
-		bool no_resize_running = new_tbl == old_tbl;
+		bool no_resize_running = tbl == old_tbl;
 
 		atomic_dec(&ht->nelems);
-		if (no_resize_running && rht_shrink_below_30(ht, new_tbl->size))
+		if (no_resize_running && rht_shrink_below_30(ht, tbl->size))
 			schedule_work(&ht->run_work);
 	}
 
@@ -753,9 +656,8 @@ void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
 
 	rcu_read_lock();
 
-	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	hash = key_hashfn(ht, key, ht->p.key_len);
+	tbl = rht_dereference_rcu(ht->tbl, ht);
+	hash = key_hashfn(ht, tbl, key, ht->p.key_len);
 restart:
 	rht_for_each_rcu(he, tbl, rht_bucket_index(tbl, hash)) {
 		if (!compare(rht_obj(ht, he), arg))
@@ -764,10 +666,10 @@ restart:
 		return rht_obj(ht, he);
 	}
 
-	if (unlikely(tbl != old_tbl)) {
-		tbl = old_tbl;
+	old_tbl = tbl;
+	tbl = rht_dereference_rcu(ht->future_tbl, ht);
+	if (unlikely(tbl != old_tbl))
 		goto restart;
-	}
 	rcu_read_unlock();
 
 	return NULL;
@@ -833,32 +735,9 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
 				      bool (*compare)(void *, void *),
 				      void *arg)
 {
-	struct bucket_table *new_tbl, *old_tbl;
-	u32 new_hash;
-	bool success = true;
-
 	BUG_ON(!ht->p.key_len);
 
-	rcu_read_lock();
-	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
-
-	lock_buckets(new_tbl, old_tbl, new_hash);
-
-	if (rhashtable_lookup_compare(ht, rht_obj(ht, obj) + ht->p.key_offset,
-				      compare, arg)) {
-		success = false;
-		goto exit;
-	}
-
-	__rhashtable_insert(ht, obj, new_tbl, old_tbl, new_hash);
-
-exit:
-	unlock_buckets(new_tbl, old_tbl, new_hash);
-	rcu_read_unlock();
-
-	return success;
+	return __rhashtable_insert(ht, obj, compare, arg);
 }
 EXPORT_SYMBOL_GPL(rhashtable_lookup_compare_insert);
 

Re: [PATCH 0/2] rhashtable: Arbitrary rehashing

[Josh Triplett]

On Tue, Mar 10, 2015 at 09:26:31AM +1100, Herbert Xu wrote:
> Hi Dave:
> 
> These two patches implement arbitrary rehashing in rhashtable.  The
> idea is based on the hashtable in net/bridge/br_multicast.c plus
> the suggestion by Josh Triplett to avoid using two linked lists.

Awesome.

> I have tested it using netlink but obviously more testing especially
> using netfilter would be welcome.
> 
> After this I would like to explore the idea of allowing multiple
> rehashes in parallel.  This would allow us to not have to rehash
> synchronously when the table gets too big and the previous rehash
> hasn't finished.

Aieee.

- Josh Triplett

Re: [PATCH 1/2] rhashtable: Move hash_rnd into bucket_table

[Thomas Graf]

On 03/10/15 at 09:27am, Herbert Xu wrote:
> Currently hash_rnd is a parameter that users can set.  However,
> no existing users set this parameter.  It is also something that
> people are unlikely to want to set directly since it's just a
> random number.
> 
> In preparation for allowing the reseeding/rehashing of rhashtable,
> this patch moves hash_rnd into bucket_table so that it's now an
> internal state rather than a parameter.
> 
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

I assume you are targeting net-next?

Acked-by: Thomas Graf <tgraf@suug.ch>

Re: [PATCH 2/2] rhashtable: Add arbitrary rehash function

[Thomas Graf]

On 03/10/15 at 09:27am, Herbert Xu wrote:
> This patch adds a rehash function that supports the use of any
> hash function for the new table.  This is needed to support changing
> the random seed value during the lifetime of the hash table.
> 
> However for now the random seed value is still constant and the
> rehash function is simply used to replace the existing expand/shrink
> functions.
> 
> Signed-off-by: Herbert Xu <herbert.xu@redhat.com>

> +static int rhashtable_rehash_one(struct rhashtable *ht, unsigned old_hash)
> +	struct bucket_table *new_tbl = rht_dereference(ht->future_tbl, ht);
> +	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
> +	struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];

[...]

I absolutely love the simplification this brings. Looks great. I now
also understand what you meant with entry for entry rehashing.

> +static void rhashtable_rehash(struct rhashtable *ht,
> +			      struct bucket_table *new_tbl)
>  {
> -	ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
> +	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
> +	unsigned old_hash;
> +
> +	get_random_bytes(&new_tbl->hash_rnd, sizeof(new_tbl->hash_rnd));
> +
> +	/* Make insertions go into the new, empty table right away. Deletions
> +	 * and lookups will be attempted in both tables until we synchronize.
> +	 * The synchronize_rcu() guarantees for the new table to be picked up
> +	 * so no new additions go into the old table while we relink.
> +	 */
> +	rcu_assign_pointer(ht->future_tbl, new_tbl);

I think you need an rcu_synchronize() here. rhashtable_remove() must
be guaranteed to either see tbl != old_tbl and thus consider both
tables or the rehashing must be guaranteed to not start for an already
started removal. 

> -static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
> -				struct bucket_table *tbl,
> -				const struct bucket_table *old_tbl, u32 hash)
> +bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
> +			 bool (*compare)(void *, void *), void *arg)

Why make this non-static? We already have rhashtable_lookup_compare_insert()
exported.

> +bool __rhashtable_remove(struct rhashtable *ht, struct bucket_table *tbl,
> +			 struct rhash_head *obj)

Same here.

Re: [PATCH 0/2] rhashtable: Arbitrary rehashing

[Thomas Graf]

On 03/10/15 at 09:26am, Herbert Xu wrote:
> After this I would like to explore the idea of allowing multiple
> rehashes in parallel.  This would allow us to not have to rehash
> synchronously when the table gets too big and the previous rehash
> hasn't finished.

Another interesting idea was to allow growing faster than 2x. It
actually became easier with this generic rehashing code because
the number of bucket locks can grow quicker than 2x again.

Re: [PATCH 1/2] rhashtable: Move hash_rnd into bucket_table

[Herbert Xu]

On Tue, Mar 10, 2015 at 05:20:02PM +0000, Thomas Graf wrote:
> On 03/10/15 at 09:27am, Herbert Xu wrote:
> > Currently hash_rnd is a parameter that users can set.  However,
> > no existing users set this parameter.  It is also something that
> > people are unlikely to want to set directly since it's just a
> > random number.
> > 
> > In preparation for allowing the reseeding/rehashing of rhashtable,
> > this patch moves hash_rnd into bucket_table so that it's now an
> > internal state rather than a parameter.
> > 
> > Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>
> 
> I assume you are targeting net-next?

Yes.

Thanks,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH 2/2] rhashtable: Add arbitrary rehash function

[Herbert Xu]

On Tue, Mar 10, 2015 at 06:17:20PM +0000, Thomas Graf wrote:
> 
> > +static void rhashtable_rehash(struct rhashtable *ht,
> > +			      struct bucket_table *new_tbl)
> >  {
> > -	ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
> > +	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
> > +	unsigned old_hash;
> > +
> > +	get_random_bytes(&new_tbl->hash_rnd, sizeof(new_tbl->hash_rnd));
> > +
> > +	/* Make insertions go into the new, empty table right away. Deletions
> > +	 * and lookups will be attempted in both tables until we synchronize.
> > +	 * The synchronize_rcu() guarantees for the new table to be picked up
> > +	 * so no new additions go into the old table while we relink.
> > +	 */
> > +	rcu_assign_pointer(ht->future_tbl, new_tbl);
> 
> I think you need an rcu_synchronize() here. rhashtable_remove() must
> be guaranteed to either see tbl != old_tbl and thus consider both
> tables or the rehashing must be guaranteed to not start for an already
> started removal. 

You are right that there is a bug with respect to removal here.
But we don't need a complete synchronize.  I just need to move
the future_tbl read in rhashtable_remove so that it occurs after
__rhashtable_remove.

Because __rhashtable_remove would have already taken a spinlock
in the old table, this means that if future_tbl is not yet visible,
then the rehashing thread has yet to process that bucket (since it
takes every single bucket lock while processing) so the entry must
be visible there (if it exists).

BTW there is also a similar bug in rhashtable_lookup_compare_insert
which I will fix in the next update.

> > -static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
> > -				struct bucket_table *tbl,
> > -				const struct bucket_table *old_tbl, u32 hash)
> > +bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
> > +			 bool (*compare)(void *, void *), void *arg)
> 
> Why make this non-static? We already have rhashtable_lookup_compare_insert()
> exported.

Good catch.  Cut-n-paste error.

Thanks,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[PATCH v2] rhashtable: Add arbitrary rehash function

[Herbert Xu]

This patch adds a rehash function that supports the use of any
hash function for the new table.  This is needed to support changing
the random seed value during the lifetime of the hash table.

However for now the random seed value is still constant and the
rehash function is simply used to replace the existing expand/shrink
functions.

Signed-off-by: Herbert Xu <herbert.xu@redhat.com>

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index ba15dce..9bc3fc4b 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -66,9 +66,9 @@ static u32 rht_bucket_index(const struct bucket_table *tbl, u32 hash)
 	return hash & (tbl->size - 1);
 }
 
-static u32 obj_raw_hashfn(struct rhashtable *ht, const void *ptr)
+static u32 obj_raw_hashfn(struct rhashtable *ht,
+			  const struct bucket_table *tbl, const void *ptr)
 {
-	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
 	u32 hash;
 
 	if (unlikely(!ht->p.key_len))
@@ -80,10 +80,9 @@ static u32 obj_raw_hashfn(struct rhashtable *ht, const void *ptr)
 	return hash >> HASH_RESERVED_SPACE;
 }
 
-static u32 key_hashfn(struct rhashtable *ht, const void *key, u32 len)
+static u32 key_hashfn(struct rhashtable *ht, const struct bucket_table *tbl,
+		      const void *key, u32 len)
 {
-	struct bucket_table *tbl = rht_dereference_rcu(ht->tbl, ht);
-
 	return ht->p.hashfn(key, len, tbl->hash_rnd) >> HASH_RESERVED_SPACE;
 }
 
@@ -91,7 +90,7 @@ static u32 head_hashfn(struct rhashtable *ht,
 		       const struct bucket_table *tbl,
 		       const struct rhash_head *he)
 {
-	return rht_bucket_index(tbl, obj_raw_hashfn(ht, rht_obj(ht, he)));
+	return rht_bucket_index(tbl, obj_raw_hashfn(ht, tbl, rht_obj(ht, he)));
 }
 
 #ifdef CONFIG_PROVE_LOCKING
@@ -165,18 +164,6 @@ EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
 #endif
 
 
-static struct rhash_head __rcu **bucket_tail(struct bucket_table *tbl, u32 n)
-{
-	struct rhash_head __rcu **pprev;
-
-	for (pprev = &tbl->buckets[n];
-	     !rht_is_a_nulls(rht_dereference_bucket(*pprev, tbl, n));
-	     pprev = &rht_dereference_bucket(*pprev, tbl, n)->next)
-		;
-
-	return pprev;
-}
-
 static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl)
 {
 	unsigned int i, size;
@@ -270,101 +257,99 @@ static bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size)
 	       (atomic_read(&ht->shift) > ht->p.min_shift);
 }
 
-static void lock_buckets(struct bucket_table *new_tbl,
-			 struct bucket_table *old_tbl, unsigned int hash)
-	__acquires(old_bucket_lock)
+static int rhashtable_rehash_one(struct rhashtable *ht, unsigned old_hash)
 {
-	spin_lock_bh(bucket_lock(old_tbl, hash));
-	if (new_tbl != old_tbl)
-		spin_lock_bh_nested(bucket_lock(new_tbl, hash),
-				    RHT_LOCK_NESTED);
-}
+	struct bucket_table *new_tbl = rht_dereference(ht->future_tbl, ht);
+	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
+	struct rhash_head __rcu **pprev = &old_tbl->buckets[old_hash];
+	int err = -ENOENT;
+	struct rhash_head *head, *next, *entry;
+	spinlock_t *new_bucket_lock;
+	unsigned new_hash;
+
+	rht_for_each(entry, old_tbl, old_hash) {
+		err = 0;
+		next = rht_dereference_bucket(entry->next, old_tbl, old_hash);
+
+		if (rht_is_a_nulls(next))
+			break;
 
-static void unlock_buckets(struct bucket_table *new_tbl,
-			   struct bucket_table *old_tbl, unsigned int hash)
-	__releases(old_bucket_lock)
-{
-	if (new_tbl != old_tbl)
-		spin_unlock_bh(bucket_lock(new_tbl, hash));
-	spin_unlock_bh(bucket_lock(old_tbl, hash));
-}
+		pprev = &entry->next;
+	}
 
-/**
- * Unlink entries on bucket which hash to different bucket.
- *
- * Returns true if no more work needs to be performed on the bucket.
- */
-static bool hashtable_chain_unzip(struct rhashtable *ht,
-				  const struct bucket_table *new_tbl,
-				  struct bucket_table *old_tbl,
-				  size_t old_hash)
-{
-	struct rhash_head *he, *p, *next;
-	unsigned int new_hash, new_hash2;
+	if (err)
+		goto out;
 
-	ASSERT_BUCKET_LOCK(ht, old_tbl, old_hash);
+	new_hash = head_hashfn(ht, new_tbl, entry);
 
-	/* Old bucket empty, no work needed. */
-	p = rht_dereference_bucket(old_tbl->buckets[old_hash], old_tbl,
-				   old_hash);
-	if (rht_is_a_nulls(p))
-		return false;
+	new_bucket_lock = bucket_lock(new_tbl, new_hash);
 
-	new_hash = head_hashfn(ht, new_tbl, p);
-	ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
+	spin_lock(new_bucket_lock);
+	head = rht_dereference_bucket(new_tbl->buckets[new_hash],
+				      new_tbl, new_hash);
 
-	/* Advance the old bucket pointer one or more times until it
-	 * reaches a node that doesn't hash to the same bucket as the
-	 * previous node p. Call the previous node p;
-	 */
-	rht_for_each_continue(he, p->next, old_tbl, old_hash) {
-		new_hash2 = head_hashfn(ht, new_tbl, he);
-		ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash2);
+	if (rht_is_a_nulls(head))
+		INIT_RHT_NULLS_HEAD(entry->next, ht, new_hash);
+	else
+		RCU_INIT_POINTER(entry->next, head);
 
-		if (new_hash != new_hash2)
-			break;
-		p = he;
-	}
-	rcu_assign_pointer(old_tbl->buckets[old_hash], p->next);
+	rcu_assign_pointer(new_tbl->buckets[new_hash], entry);
+	spin_unlock(new_bucket_lock);
 
-	/* Find the subsequent node which does hash to the same
-	 * bucket as node P, or NULL if no such node exists.
-	 */
-	INIT_RHT_NULLS_HEAD(next, ht, old_hash);
-	if (!rht_is_a_nulls(he)) {
-		rht_for_each_continue(he, he->next, old_tbl, old_hash) {
-			if (head_hashfn(ht, new_tbl, he) == new_hash) {
-				next = he;
-				break;
-			}
-		}
-	}
+	rcu_assign_pointer(*pprev, next);
 
-	/* Set p's next pointer to that subsequent node pointer,
-	 * bypassing the nodes which do not hash to p's bucket
-	 */
-	rcu_assign_pointer(p->next, next);
+out:
+	return err;
+}
+
+static void rhashtable_rehash_chain(struct rhashtable *ht, unsigned old_hash)
+{
+	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
+	spinlock_t *old_bucket_lock;
 
-	p = rht_dereference_bucket(old_tbl->buckets[old_hash], old_tbl,
-				   old_hash);
+	old_bucket_lock = bucket_lock(old_tbl, old_hash);
 
-	return !rht_is_a_nulls(p);
+	spin_lock_bh(old_bucket_lock);
+	while (!rhashtable_rehash_one(ht, old_hash))
+		;
+	spin_unlock_bh(old_bucket_lock);
 }
 
-static void link_old_to_new(struct rhashtable *ht, struct bucket_table *new_tbl,
-			    unsigned int new_hash, struct rhash_head *entry)
+static void rhashtable_rehash(struct rhashtable *ht,
+			      struct bucket_table *new_tbl)
 {
-	ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
+	struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht);
+	unsigned old_hash;
+
+	get_random_bytes(&new_tbl->hash_rnd, sizeof(new_tbl->hash_rnd));
 
-	rcu_assign_pointer(*bucket_tail(new_tbl, new_hash), entry);
+	/* Make insertions go into the new, empty table right away. Deletions
+	 * and lookups will be attempted in both tables until we synchronize.
+	 * The synchronize_rcu() guarantees for the new table to be picked up
+	 * so no new additions go into the old table while we relink.
+	 */
+	rcu_assign_pointer(ht->future_tbl, new_tbl);
+
+	for (old_hash = 0; old_hash < old_tbl->size; old_hash++)
+		rhashtable_rehash_chain(ht, old_hash);
+
+	/* Publish the new table pointer. */
+	rcu_assign_pointer(ht->tbl, new_tbl);
+
+	/* Wait for readers. All new readers will see the new
+	 * table, and thus no references to the old table will
+	 * remain.
+	 */
+	synchronize_rcu();
+
+	bucket_table_free(old_tbl);
 }
 
 /**
  * rhashtable_expand - Expand hash table while allowing concurrent lookups
  * @ht:		the hash table to expand
  *
- * A secondary bucket array is allocated and the hash entries are migrated
- * while keeping them on both lists until the end of the RCU grace period.
+ * A secondary bucket array is allocated and the hash entries are migrated.
  *
  * This function may only be called in a context where it is safe to call
  * synchronize_rcu(), e.g. not within a rcu_read_lock() section.
@@ -378,9 +363,6 @@ static void link_old_to_new(struct rhashtable *ht, struct bucket_table *new_tbl,
 int rhashtable_expand(struct rhashtable *ht)
 {
 	struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
-	struct rhash_head *he;
-	unsigned int new_hash, old_hash;
-	bool complete = false;
 
 	ASSERT_RHT_MUTEX(ht);
 
@@ -392,64 +374,8 @@ int rhashtable_expand(struct rhashtable *ht)
 
 	atomic_inc(&ht->shift);
 
-	/* Make insertions go into the new, empty table right away. Deletions
-	 * and lookups will be attempted in both tables until we synchronize.
-	 * The synchronize_rcu() guarantees for the new table to be picked up
-	 * so no new additions go into the old table while we relink.
-	 */
-	rcu_assign_pointer(ht->future_tbl, new_tbl);
-	synchronize_rcu();
+	rhashtable_rehash(ht, new_tbl);
 
-	/* For each new bucket, search the corresponding old bucket for the
-	 * first entry that hashes to the new bucket, and link the end of
-	 * newly formed bucket chain (containing entries added to future
-	 * table) to that entry. Since all the entries which will end up in
-	 * the new bucket appear in the same old bucket, this constructs an
-	 * entirely valid new hash table, but with multiple buckets
-	 * "zipped" together into a single imprecise chain.
-	 */
-	for (new_hash = 0; new_hash < new_tbl->size; new_hash++) {
-		old_hash = rht_bucket_index(old_tbl, new_hash);
-		lock_buckets(new_tbl, old_tbl, new_hash);
-		rht_for_each(he, old_tbl, old_hash) {
-			if (head_hashfn(ht, new_tbl, he) == new_hash) {
-				link_old_to_new(ht, new_tbl, new_hash, he);
-				break;
-			}
-		}
-		unlock_buckets(new_tbl, old_tbl, new_hash);
-		cond_resched();
-	}
-
-	/* Unzip interleaved hash chains */
-	while (!complete && !ht->being_destroyed) {
-		/* Wait for readers. All new readers will see the new
-		 * table, and thus no references to the old table will
-		 * remain.
-		 */
-		synchronize_rcu();
-
-		/* For each bucket in the old table (each of which
-		 * contains items from multiple buckets of the new
-		 * table): ...
-		 */
-		complete = true;
-		for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
-			lock_buckets(new_tbl, old_tbl, old_hash);
-
-			if (hashtable_chain_unzip(ht, new_tbl, old_tbl,
-						  old_hash))
-				complete = false;
-
-			unlock_buckets(new_tbl, old_tbl, old_hash);
-			cond_resched();
-		}
-	}
-
-	rcu_assign_pointer(ht->tbl, new_tbl);
-	synchronize_rcu();
-
-	bucket_table_free(old_tbl);
 	return 0;
 }
 EXPORT_SYMBOL_GPL(rhashtable_expand);
@@ -473,7 +399,6 @@ EXPORT_SYMBOL_GPL(rhashtable_expand);
 int rhashtable_shrink(struct rhashtable *ht)
 {
 	struct bucket_table *new_tbl, *tbl = rht_dereference(ht->tbl, ht);
-	unsigned int new_hash;
 
 	ASSERT_RHT_MUTEX(ht);
 
@@ -483,39 +408,9 @@ int rhashtable_shrink(struct rhashtable *ht)
 
 	new_tbl->hash_rnd = tbl->hash_rnd;
 
-	rcu_assign_pointer(ht->future_tbl, new_tbl);
-	synchronize_rcu();
-
-	/* Link the first entry in the old bucket to the end of the
-	 * bucket in the new table. As entries are concurrently being
-	 * added to the new table, lock down the new bucket. As we
-	 * always divide the size in half when shrinking, each bucket
-	 * in the new table maps to exactly two buckets in the old
-	 * table.
-	 */
-	for (new_hash = 0; new_hash < new_tbl->size; new_hash++) {
-		lock_buckets(new_tbl, tbl, new_hash);
-
-		rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
-				   tbl->buckets[new_hash]);
-		ASSERT_BUCKET_LOCK(ht, tbl, new_hash + new_tbl->size);
-		rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
-				   tbl->buckets[new_hash + new_tbl->size]);
-
-		unlock_buckets(new_tbl, tbl, new_hash);
-		cond_resched();
-	}
-
-	/* Publish the new, valid hash table */
-	rcu_assign_pointer(ht->tbl, new_tbl);
 	atomic_dec(&ht->shift);
 
-	/* Wait for readers. No new readers will have references to the
-	 * old hash table.
-	 */
-	synchronize_rcu();
-
-	bucket_table_free(tbl);
+	rhashtable_rehash(ht, new_tbl);
 
 	return 0;
 }
@@ -545,18 +440,46 @@ unlock:
 	mutex_unlock(&ht->mutex);
 }
 
-static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
-				struct bucket_table *tbl,
-				const struct bucket_table *old_tbl, u32 hash)
+static bool __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
+				bool (*compare)(void *, void *), void *arg)
 {
-	bool no_resize_running = tbl == old_tbl;
+	struct bucket_table *tbl, *old_tbl;
 	struct rhash_head *head;
+	bool no_resize_running;
+	unsigned hash;
+	bool success = true;
+
+	rcu_read_lock();
+
+	old_tbl = rht_dereference_rcu(ht->tbl, ht);
+	hash = obj_raw_hashfn(ht, old_tbl, rht_obj(ht, obj));
+
+	spin_lock_bh(bucket_lock(old_tbl, hash));
+
+	/* Because we have already taken the bucket lock in old_tbl,
+	 * if we find that future_tbl is not yet visible then that
+	 * guarantees all other insertions of the same entry will
+	 * also grab the bucket lock in old_tbl because until the
+	 * rehash completes ht->tbl won't be changed.
+	 */
+	tbl = rht_dereference_rcu(ht->future_tbl, ht);
+	if (tbl != old_tbl) {
+		hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+		spin_lock(bucket_lock(tbl, hash));
+	}
+
+	if (compare &&
+	    rhashtable_lookup_compare(ht, rht_obj(ht, obj) + ht->p.key_offset,
+				      compare, arg)) {
+		success = false;
+		goto exit;
+	}
+
+	no_resize_running = tbl == old_tbl;
 
 	hash = rht_bucket_index(tbl, hash);
 	head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
 
-	ASSERT_BUCKET_LOCK(ht, tbl, hash);
-
 	if (rht_is_a_nulls(head))
 		INIT_RHT_NULLS_HEAD(obj->next, ht, hash);
 	else
@@ -567,6 +490,19 @@ static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 	atomic_inc(&ht->nelems);
 	if (no_resize_running && rht_grow_above_75(ht, tbl->size))
 		schedule_work(&ht->run_work);
+
+exit:
+	if (tbl != old_tbl) {
+		hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+		spin_unlock(bucket_lock(tbl, hash));
+	}
+
+	hash = obj_raw_hashfn(ht, old_tbl, rht_obj(ht, obj));
+	spin_unlock_bh(bucket_lock(old_tbl, hash));
+
+	rcu_read_unlock();
+
+	return success;
 }
 
 /**
@@ -586,22 +522,42 @@ static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
  */
 void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
 {
-	struct bucket_table *tbl, *old_tbl;
+	__rhashtable_insert(ht, obj, NULL, NULL);
+}
+EXPORT_SYMBOL_GPL(rhashtable_insert);
+
+static bool __rhashtable_remove(struct rhashtable *ht,
+				struct bucket_table *tbl,
+				struct rhash_head *obj)
+{
+	struct rhash_head __rcu **pprev;
+	struct rhash_head *he;
+	spinlock_t * lock;
 	unsigned hash;
+	bool ret = false;
 
-	rcu_read_lock();
+	hash = obj_raw_hashfn(ht, tbl, rht_obj(ht, obj));
+	lock = bucket_lock(tbl, hash);
+	hash = rht_bucket_index(tbl, hash);
 
-	tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
+	spin_lock_bh(lock);
 
-	lock_buckets(tbl, old_tbl, hash);
-	__rhashtable_insert(ht, obj, tbl, old_tbl, hash);
-	unlock_buckets(tbl, old_tbl, hash);
+	pprev = &tbl->buckets[hash];
+	rht_for_each(he, tbl, hash) {
+		if (he != obj) {
+			pprev = &he->next;
+			continue;
+		}
 
-	rcu_read_unlock();
+		rcu_assign_pointer(*pprev, obj->next);
+		ret = true;
+		break;
+	}
+
+	spin_unlock_bh(lock);
+
+	return ret;
 }
-EXPORT_SYMBOL_GPL(rhashtable_insert);
 
 /**
  * rhashtable_remove - remove object from hash table
@@ -620,68 +576,28 @@ EXPORT_SYMBOL_GPL(rhashtable_insert);
  */
 bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
 {
-	struct bucket_table *tbl, *new_tbl, *old_tbl;
-	struct rhash_head __rcu **pprev;
-	struct rhash_head *he, *he2;
-	unsigned int hash, new_hash;
-	bool ret = false;
+	struct bucket_table *tbl, *old_tbl;
+	bool ret;
 
 	rcu_read_lock();
-	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	tbl = new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
 
-	lock_buckets(new_tbl, old_tbl, new_hash);
-restart:
-	hash = rht_bucket_index(tbl, new_hash);
-	pprev = &tbl->buckets[hash];
-	rht_for_each(he, tbl, hash) {
-		if (he != obj) {
-			pprev = &he->next;
-			continue;
-		}
-
-		ASSERT_BUCKET_LOCK(ht, tbl, hash);
-
-		if (old_tbl->size > new_tbl->size && tbl == old_tbl &&
-		    !rht_is_a_nulls(obj->next) &&
-		    head_hashfn(ht, tbl, obj->next) != hash) {
-			rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash));
-		} else if (unlikely(old_tbl->size < new_tbl->size && tbl == new_tbl)) {
-			rht_for_each_continue(he2, obj->next, tbl, hash) {
-				if (head_hashfn(ht, tbl, he2) == hash) {
-					rcu_assign_pointer(*pprev, he2);
-					goto found;
-				}
-			}
-
-			rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash));
-		} else {
-			rcu_assign_pointer(*pprev, obj->next);
-		}
-
-found:
-		ret = true;
-		break;
-	}
+	old_tbl = rht_dereference_rcu(ht->tbl, ht);
+	ret = __rhashtable_remove(ht, old_tbl, obj);
 
-	/* The entry may be linked in either 'tbl', 'future_tbl', or both.
-	 * 'future_tbl' only exists for a short period of time during
-	 * resizing. Thus traversing both is fine and the added cost is
-	 * very rare.
+	/* Because we have already taken (and released) the bucket
+	 * lock in old_tbl, if we find that future_tbl is not yet
+	 * visible then that guarantees the entry to still be in
+	 * old_tbl if it exists.
 	 */
-	if (tbl != old_tbl) {
-		tbl = old_tbl;
-		goto restart;
-	}
-
-	unlock_buckets(new_tbl, old_tbl, new_hash);
+	tbl = rht_dereference_rcu(ht->future_tbl, ht);
+	if (!ret && old_tbl != tbl)
+		ret = __rhashtable_remove(ht, tbl, obj);
 
 	if (ret) {
-		bool no_resize_running = new_tbl == old_tbl;
+		bool no_resize_running = tbl == old_tbl;
 
 		atomic_dec(&ht->nelems);
-		if (no_resize_running && rht_shrink_below_30(ht, new_tbl->size))
+		if (no_resize_running && rht_shrink_below_30(ht, tbl->size))
 			schedule_work(&ht->run_work);
 	}
 
@@ -753,9 +669,8 @@ void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
 
 	rcu_read_lock();
 
-	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	hash = key_hashfn(ht, key, ht->p.key_len);
+	tbl = rht_dereference_rcu(ht->tbl, ht);
+	hash = key_hashfn(ht, tbl, key, ht->p.key_len);
 restart:
 	rht_for_each_rcu(he, tbl, rht_bucket_index(tbl, hash)) {
 		if (!compare(rht_obj(ht, he), arg))
@@ -764,10 +679,10 @@ restart:
 		return rht_obj(ht, he);
 	}
 
-	if (unlikely(tbl != old_tbl)) {
-		tbl = old_tbl;
+	old_tbl = tbl;
+	tbl = rht_dereference_rcu(ht->future_tbl, ht);
+	if (unlikely(tbl != old_tbl))
 		goto restart;
-	}
 	rcu_read_unlock();
 
 	return NULL;
@@ -833,32 +748,9 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
 				      bool (*compare)(void *, void *),
 				      void *arg)
 {
-	struct bucket_table *new_tbl, *old_tbl;
-	u32 new_hash;
-	bool success = true;
-
 	BUG_ON(!ht->p.key_len);
 
-	rcu_read_lock();
-	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
-
-	lock_buckets(new_tbl, old_tbl, new_hash);
-
-	if (rhashtable_lookup_compare(ht, rht_obj(ht, obj) + ht->p.key_offset,
-				      compare, arg)) {
-		success = false;
-		goto exit;
-	}
-
-	__rhashtable_insert(ht, obj, new_tbl, old_tbl, new_hash);
-
-exit:
-	unlock_buckets(new_tbl, old_tbl, new_hash);
-	rcu_read_unlock();
-
-	return success;
+	return __rhashtable_insert(ht, obj, compare, arg);
 }
 EXPORT_SYMBOL_GPL(rhashtable_lookup_compare_insert);
 
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH v2] rhashtable: Add arbitrary rehash function

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Wed, 11 Mar 2015 09:43:48 +1100

> This patch adds a rehash function that supports the use of any
> hash function for the new table.  This is needed to support changing
> the random seed value during the lifetime of the hash table.
> 
> However for now the random seed value is still constant and the
> rehash function is simply used to replace the existing expand/shrink
> functions.
> 
> Signed-off-by: Herbert Xu <herbert.xu@redhat.com>

I applied both patches, but for this one I had to tack on
a removal of ASSERT_BUCKET_LOCK(), debug_dump_table(), and
debug_dump_buckets() as they are no longer used.

Please watch the compiler warning output when making changes,
thanks.

Re: [PATCH v2] rhashtable: Add arbitrary rehash function

[Herbert Xu]

On Wed, Mar 11, 2015 at 04:37:28PM -0400, David Miller wrote:
>
> I applied both patches, but for this one I had to tack on
> a removal of ASSERT_BUCKET_LOCK(), debug_dump_table(), and
> debug_dump_buckets() as they are no longer used.

Sorry, I didn't have PROVE_LOCKING on so I didn't see these
warnings.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH 0/2] rhashtable: Arbitrary rehashing

[Thomas Graf]

[-- Attachment #1: Type: text/plain, Size: 581 bytes --]

On 03/10/15 at 09:26am, Herbert Xu wrote:
> I have tested it using netlink but obviously more testing especially
> using netfilter would be welcome.

I ran the attached bind_netlink test written by Ying Xue and it
currently crashes with:

[  108.693908] BUG: unable to handle kernel paging request at fffffffffffffe68

I'm running bind_netlink like this:

while true; do
    ./bind_netlink 9000 324234324&
    ./bind_netlink 9000 888448422&
    ./bind_netlink 9000 324
done

I tested with the synchronize_rcu() fix on top as well and that
didn't help so it must be something else.

[-- Attachment #2: bind_netlink.c --]
[-- Type: text/plain, Size: 1043 bytes --]

#include <sys/types.h>
#include <sys/socket.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>
#include <netinet/in.h>
#include <linux/netlink.h>

void diep(char *err)
{
	perror(err);
	exit(1);
}

int main(int argc, char *argv[])
{
	int i;
	int *fds;
	int num_ports;
	struct sockaddr_nl local;

	srand(strtoul(argv[2], NULL, 0));

	if (argc < 2) {
		fprintf(stderr, "Usage: %s <PORTS>\n", argv[0]);
		exit(1);
	}

	num_ports = atoi(argv[optind]);

	printf("Create %u ports\n", num_ports);

	fds = malloc(sizeof(int) * num_ports);
	for (i = 1; i <= num_ports; i++) {
		if (!(fds[i] = socket(PF_NETLINK, SOCK_RAW, 0)))
			diep("socket");

		memset(&local, 0, sizeof(local));
		local.nl_family = AF_NETLINK;
		local.nl_pid = rand();
		local.nl_groups = 0;
		if(bind(fds[i], (struct sockaddr *)&local, sizeof(local)) != 0){
			diep("socket");
		}
		
		if (!(i % 1000))
			printf("Created %u ports\n", i);

	}
	printf("Ports successfully created, terminating\n");

	return 0;
}

Re: [PATCH 0/2] rhashtable: Arbitrary rehashing

[Herbert Xu]

On Thu, Mar 12, 2015 at 04:46:35PM +0000, Thomas Graf wrote:
> On 03/10/15 at 09:26am, Herbert Xu wrote:
> > I have tested it using netlink but obviously more testing especially
> > using netfilter would be welcome.
> 
> I ran the attached bind_netlink test written by Ying Xue and it
> currently crashes with:
> 
> [  108.693908] BUG: unable to handle kernel paging request at fffffffffffffe68

Oops, thanks for testing and finding this bug.

This patch should cure it.

---8<---
rhashtable: Fix read-side crash during rehash
    
This patch fixes a typo rhashtable_lookup_compare where we fail
to recompute the hash when looking up the new table.  This causes
elements to be missed and potentially a crash during a resize.

Reported-by: Thomas Graf <tgraf@suug.ch>
Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 9666efec..f8c5063 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -614,8 +614,8 @@ void *rhashtable_lookup_compare(struct rhashtable *ht, const void *key,
 	rcu_read_lock();
 
 	tbl = rht_dereference_rcu(ht->tbl, ht);
-	hash = key_hashfn(ht, tbl, key);
 restart:
+	hash = key_hashfn(ht, tbl, key);
 	rht_for_each_rcu(he, tbl, hash) {
 		if (!compare(rht_obj(ht, he), arg))
 			continue;

-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH 0/2] rhashtable: Arbitrary rehashing

[David Miller]

From: Herbert Xu <herbert@gondor.apana.org.au>
Date: Fri, 13 Mar 2015 12:54:10 +1100

> rhashtable: Fix read-side crash during rehash
>     
> This patch fixes a typo rhashtable_lookup_compare where we fail
> to recompute the hash when looking up the new table.  This causes
> elements to be missed and potentially a crash during a resize.
> 
> Reported-by: Thomas Graf <tgraf@suug.ch>
> Signed-off-by: Herbert Xu <herbert@gondor.apana.org.au>

Applied.