[PATCH 0/6 v2 net-next] rhashtable fixes

[PATCH 0/6 v2 net-next] rhashtable fixes

[Thomas Graf]

This series fixes all remaining known issues with rhashtable that
have been reported. In particular the race condition reported by
Ying Xue.

---
Dave/Herbert: I'm posting this now as it fixes real issues. I'm
fine with taking Herbert's rehash patches instead if they resolve
all the reported issues as well.

v2:
 - Rebased on top of Herbert Xu's iterator code
 - Fixed last remaining race that remained. Special thanks
   to Daniel Borkmann for assistance while debugging.

Thomas Graf (6):
  rhashtable: key_hashfn() must return full hash value
  rhashtable: Use a single bucket lock for sibling buckets
  rhashtable: Wait for RCU readers after final unzip work
  rhashtable: Dump bucket tables on locking violation under
    PROVE_LOCKING
  rhashtable: Add more lock verification
  rhashtable: Avoid bucket cross reference after removal

 lib/rhashtable.c | 305 ++++++++++++++++++++++++++++++-------------------------
 1 file changed, 167 insertions(+), 138 deletions(-)

[PATCH 1/6] rhashtable: key_hashfn() must return full hash value

[Thomas Graf]

The value computed by key_hashfn() is used by rhashtable_lookup_compare()
to traverse both tables during a resize. key_hashfn() must therefore
return the hash value without the buckets mask applied so it can be
masked to the size of each individual table.

Fixes: 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
Signed-off-by: Thomas Graf <tgraf@suug.ch>
---
 lib/rhashtable.c | 8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 0579191..71fd0dd 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -94,13 +94,7 @@ static u32 obj_raw_hashfn(const struct rhashtable *ht, const void *ptr)
 
 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 >>= HASH_RESERVED_SPACE;
-
-	return rht_bucket_index(tbl, hash);
+	return ht->p.hashfn(key, len, ht->p.hash_rnd) >> HASH_RESERVED_SPACE;
 }
 
 static u32 head_hashfn(const struct rhashtable *ht,
-- 
1.9.3

[PATCH 2/6] rhashtable: Use a single bucket lock for sibling buckets

[Thomas Graf]

rhashtable currently allows to use a bucket lock per bucket. This
requires multiple levels of complicated nested locking because when
resizing, a single bucket of the smaller table will map to two
buckets in the larger table. So far rhashtable has explicitly locked
both buckets in the larger table.

By excluding the highest bit of the hash from the bucket lock map and
thus only allowing locks to buckets in a ratio of 1:2, the locking
can be simplified a lot without losing the benefits of multiple locks.
Larger tables which benefit from multiple locks will not have a single
lock per bucket anyway.

Signed-off-by: Thomas Graf <tgraf@suug.ch>
---
 lib/rhashtable.c | 170 ++++++++++++++++++++++---------------------------------
 1 file changed, 69 insertions(+), 101 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 71fd0dd..cea4244 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -1,7 +1,7 @@
 /*
  * Resizable, Scalable, Concurrent Hash Table
  *
- * Copyright (c) 2014 Thomas Graf <tgraf@suug.ch>
+ * Copyright (c) 2014-2015 Thomas Graf <tgraf@suug.ch>
  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
  *
  * Based on the following paper:
@@ -34,12 +34,17 @@
 enum {
 	RHT_LOCK_NORMAL,
 	RHT_LOCK_NESTED,
-	RHT_LOCK_NESTED2,
 };
 
 /* The bucket lock is selected based on the hash and protects mutations
  * on a group of hash buckets.
  *
+ * A maximum of tbl->size/2 bucket locks is allocated. This ensures that
+ * a single lock always covers both buckets which may both contains
+ * entries which link to the same bucket of the old table during resizing.
+ * This allows to simplify the locking as locking the bucket in both
+ * tables during resize always guarantee protection.
+ *
  * IMPORTANT: When holding the bucket lock of both the old and new table
  * during expansions and shrinking, the old bucket lock must always be
  * acquired first.
@@ -128,8 +133,8 @@ static int alloc_bucket_locks(struct rhashtable *ht, struct bucket_table *tbl)
 	nr_pcpus = min_t(unsigned int, nr_pcpus, 32UL);
 	size = roundup_pow_of_two(nr_pcpus * ht->p.locks_mul);
 
-	/* Never allocate more than one lock per bucket */
-	size = min_t(unsigned int, size, tbl->size);
+	/* Never allocate more than 0.5 locks per bucket */
+	size = min_t(unsigned int, size, tbl->size >> 1);
 
 	if (sizeof(spinlock_t) != 0) {
 #ifdef CONFIG_NUMA
@@ -211,13 +216,36 @@ bool rht_shrink_below_30(const struct rhashtable *ht, size_t new_size)
 }
 EXPORT_SYMBOL_GPL(rht_shrink_below_30);
 
-static void hashtable_chain_unzip(const struct rhashtable *ht,
+static void lock_buckets(struct bucket_table *new_tbl,
+			 struct bucket_table *old_tbl, unsigned int hash)
+	__acquires(old_bucket_lock)
+{
+	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);
+}
+
+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));
+}
+
+/**
+ * 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(const struct rhashtable *ht,
 				  const struct bucket_table *new_tbl,
 				  struct bucket_table *old_tbl,
 				  size_t old_hash)
 {
 	struct rhash_head *he, *p, *next;
-	spinlock_t *new_bucket_lock, *new_bucket_lock2 = NULL;
 	unsigned int new_hash, new_hash2;
 
 	ASSERT_BUCKET_LOCK(old_tbl, old_hash);
@@ -226,10 +254,10 @@ static void hashtable_chain_unzip(const struct rhashtable *ht,
 	p = rht_dereference_bucket(old_tbl->buckets[old_hash], old_tbl,
 				   old_hash);
 	if (rht_is_a_nulls(p))
-		return;
+		return false;
 
-	new_hash = new_hash2 = head_hashfn(ht, new_tbl, p);
-	new_bucket_lock = bucket_lock(new_tbl, new_hash);
+	new_hash = head_hashfn(ht, new_tbl, p);
+	ASSERT_BUCKET_LOCK(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
@@ -237,22 +265,14 @@ static void hashtable_chain_unzip(const struct rhashtable *ht,
 	 */
 	rht_for_each_continue(he, p->next, old_tbl, old_hash) {
 		new_hash2 = head_hashfn(ht, new_tbl, he);
+		ASSERT_BUCKET_LOCK(new_tbl, new_hash2);
+
 		if (new_hash != new_hash2)
 			break;
 		p = he;
 	}
 	rcu_assign_pointer(old_tbl->buckets[old_hash], p->next);
 
-	spin_lock_bh_nested(new_bucket_lock, RHT_LOCK_NESTED);
-
-	/* If we have encountered an entry that maps to a different bucket in
-	 * the new table, lock down that bucket as well as we might cut off
-	 * the end of the chain.
-	 */
-	new_bucket_lock2 = bucket_lock(new_tbl, new_hash);
-	if (new_bucket_lock != new_bucket_lock2)
-		spin_lock_bh_nested(new_bucket_lock2, RHT_LOCK_NESTED2);
-
 	/* Find the subsequent node which does hash to the same
 	 * bucket as node P, or NULL if no such node exists.
 	 */
@@ -271,21 +291,16 @@ static void hashtable_chain_unzip(const struct rhashtable *ht,
 	 */
 	rcu_assign_pointer(p->next, next);
 
-	if (new_bucket_lock != new_bucket_lock2)
-		spin_unlock_bh(new_bucket_lock2);
-	spin_unlock_bh(new_bucket_lock);
+	p = rht_dereference_bucket(old_tbl->buckets[old_hash], old_tbl,
+				   old_hash);
+
+	return !rht_is_a_nulls(p);
 }
 
 static void link_old_to_new(struct bucket_table *new_tbl,
 			    unsigned int new_hash, struct rhash_head *entry)
 {
-	spinlock_t *new_bucket_lock;
-
-	new_bucket_lock = bucket_lock(new_tbl, new_hash);
-
-	spin_lock_bh_nested(new_bucket_lock, RHT_LOCK_NESTED);
 	rcu_assign_pointer(*bucket_tail(new_tbl, new_hash), entry);
-	spin_unlock_bh(new_bucket_lock);
 }
 
 /**
@@ -308,7 +323,6 @@ int rhashtable_expand(struct rhashtable *ht)
 {
 	struct bucket_table *new_tbl, *old_tbl = rht_dereference(ht->tbl, ht);
 	struct rhash_head *he;
-	spinlock_t *old_bucket_lock;
 	unsigned int new_hash, old_hash;
 	bool complete = false;
 
@@ -338,16 +352,14 @@ int rhashtable_expand(struct rhashtable *ht)
 	 */
 	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);
+		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(new_tbl, new_hash, he);
 				break;
 			}
 		}
-		spin_unlock_bh(old_bucket_lock);
+		unlock_buckets(new_tbl, old_tbl, new_hash);
 	}
 
 	/* Publish the new table pointer. Lookups may now traverse
@@ -370,18 +382,13 @@ int rhashtable_expand(struct rhashtable *ht)
 		 */
 		complete = true;
 		for (old_hash = 0; old_hash < old_tbl->size; old_hash++) {
-			struct rhash_head *head;
+			lock_buckets(new_tbl, old_tbl, old_hash);
 
-			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))
+			if (hashtable_chain_unzip(ht, new_tbl, old_tbl,
+						  old_hash))
 				complete = false;
 
-			spin_unlock_bh(old_bucket_lock);
+			unlock_buckets(new_tbl, old_tbl, old_hash);
 		}
 	}
 
@@ -409,7 +416,6 @@ EXPORT_SYMBOL_GPL(rhashtable_expand);
 int rhashtable_shrink(struct rhashtable *ht)
 {
 	struct bucket_table *new_tbl, *tbl = rht_dereference(ht->tbl, ht);
-	spinlock_t *new_bucket_lock, *old_bucket_lock1, *old_bucket_lock2;
 	unsigned int new_hash;
 
 	ASSERT_RHT_MUTEX(ht);
@@ -427,36 +433,16 @@ int rhashtable_shrink(struct rhashtable *ht)
 	 * 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);
-		}
+		lock_buckets(new_tbl, tbl, new_hash);
 
 		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);
+		unlock_buckets(new_tbl, tbl, new_hash);
 	}
 
 	/* Publish the new, valid hash table */
@@ -547,19 +533,18 @@ 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;
-	spinlock_t *lock;
+	struct bucket_table *tbl, *old_tbl;
 	unsigned hash;
 
 	rcu_read_lock();
 
 	tbl = rht_dereference_rcu(ht->future_tbl, ht);
+	old_tbl = rht_dereference_rcu(ht->tbl, ht);
 	hash = head_hashfn(ht, tbl, obj);
-	lock = bucket_lock(tbl, hash);
 
-	spin_lock_bh(lock);
+	lock_buckets(tbl, old_tbl, hash);
 	__rhashtable_insert(ht, obj, tbl, hash);
-	spin_unlock_bh(lock);
+	unlock_buckets(tbl, old_tbl, hash);
 
 	rcu_read_unlock();
 }
@@ -582,21 +567,20 @@ EXPORT_SYMBOL_GPL(rhashtable_insert);
  */
 bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
 {
-	struct bucket_table *tbl;
+	struct bucket_table *tbl, *new_tbl, *old_tbl;
 	struct rhash_head __rcu **pprev;
 	struct rhash_head *he;
-	spinlock_t *lock;
-	unsigned int hash;
+	unsigned int hash, new_hash;
 	bool ret = false;
 
 	rcu_read_lock();
-	tbl = rht_dereference_rcu(ht->tbl, ht);
-	hash = head_hashfn(ht, tbl, obj);
-
-	lock = bucket_lock(tbl, hash);
-	spin_lock_bh(lock);
+	tbl = old_tbl = rht_dereference_rcu(ht->tbl, ht);
+	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
+	new_hash = head_hashfn(ht, new_tbl, 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) {
@@ -615,18 +599,12 @@ restart:
 	 * resizing. Thus traversing both is fine and the added cost is
 	 * very rare.
 	 */
-	if (tbl != rht_dereference_rcu(ht->future_tbl, ht)) {
-		spin_unlock_bh(lock);
-
-		tbl = rht_dereference_rcu(ht->future_tbl, ht);
-		hash = head_hashfn(ht, tbl, obj);
-
-		lock = bucket_lock(tbl, hash);
-		spin_lock_bh(lock);
+	if (tbl != new_tbl) {
+		tbl = new_tbl;
 		goto restart;
 	}
 
-	spin_unlock_bh(lock);
+	unlock_buckets(new_tbl, old_tbl, new_hash);
 
 	if (ret) {
 		atomic_dec(&ht->nelems);
@@ -782,24 +760,17 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
 				      void *arg)
 {
 	struct bucket_table *new_tbl, *old_tbl;
-	spinlock_t *new_bucket_lock, *old_bucket_lock;
-	u32 new_hash, old_hash;
+	u32 new_hash;
 	bool success = true;
 
 	BUG_ON(!ht->p.key_len);
 
 	rcu_read_lock();
-
 	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	old_hash = head_hashfn(ht, old_tbl, obj);
-	old_bucket_lock = bucket_lock(old_tbl, old_hash);
-	spin_lock_bh(old_bucket_lock);
-
 	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
 	new_hash = head_hashfn(ht, new_tbl, obj);
-	new_bucket_lock = bucket_lock(new_tbl, new_hash);
-	if (unlikely(old_tbl != new_tbl))
-		spin_lock_bh_nested(new_bucket_lock, RHT_LOCK_NESTED);
+
+	lock_buckets(new_tbl, old_tbl, new_hash);
 
 	if (rhashtable_lookup_compare(ht, rht_obj(ht, obj) + ht->p.key_offset,
 				      compare, arg)) {
@@ -810,10 +781,7 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
 	__rhashtable_insert(ht, obj, new_tbl, new_hash);
 
 exit:
-	if (unlikely(old_tbl != new_tbl))
-		spin_unlock_bh(new_bucket_lock);
-	spin_unlock_bh(old_bucket_lock);
-
+	unlock_buckets(new_tbl, old_tbl, new_hash);
 	rcu_read_unlock();
 
 	return success;
-- 
1.9.3

[PATCH 3/6] rhashtable: Wait for RCU readers after final unzip work

[Thomas Graf]

We need to wait for all RCU readers to complete after the last bit of
unzipping has been completed. Otherwise the old table is freed up
prematurely.

Fixes: 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")
Signed-off-by: Thomas Graf <tgraf@suug.ch>
---
 lib/rhashtable.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index cea4244..fd1033d 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -392,6 +392,8 @@ int rhashtable_expand(struct rhashtable *ht)
 		}
 	}
 
+	synchronize_rcu();
+
 	bucket_table_free(old_tbl);
 	return 0;
 }
-- 
1.9.3

[PATCH 4/6] rhashtable: Dump bucket tables on locking violation under PROVE_LOCKING

[Thomas Graf]

This simplifies debugging of locking violations if compiled with
CONFIG_PROVE_LOCKING.

Signed-off-by: Thomas Graf <tgraf@suug.ch>
---
 lib/rhashtable.c | 99 ++++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 75 insertions(+), 24 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index fd1033d..c2c3949 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -54,26 +54,6 @@ static spinlock_t *bucket_lock(const struct bucket_table *tbl, u32 hash)
 	return &tbl->locks[hash & tbl->locks_mask];
 }
 
-#define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
-#define ASSERT_BUCKET_LOCK(TBL, HASH) \
-	BUG_ON(!lockdep_rht_bucket_is_held(TBL, HASH))
-
-#ifdef CONFIG_PROVE_LOCKING
-int lockdep_rht_mutex_is_held(struct rhashtable *ht)
-{
-	return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
-}
-EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
-
-int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
-{
-	spinlock_t *lock = bucket_lock(tbl, hash);
-
-	return (debug_locks) ? lockdep_is_held(lock) : 1;
-}
-EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
-#endif
-
 static void *rht_obj(const struct rhashtable *ht, const struct rhash_head *he)
 {
 	return (void *) he - ht->p.head_offset;
@@ -109,6 +89,77 @@ static u32 head_hashfn(const struct rhashtable *ht,
 	return rht_bucket_index(tbl, obj_raw_hashfn(ht, rht_obj(ht, he)));
 }
 
+#ifdef CONFIG_PROVE_LOCKING
+static void debug_dump_buckets(const struct rhashtable *ht,
+			       const struct bucket_table *tbl)
+{
+	struct rhash_head *he;
+	unsigned int i, hash;
+
+	for (i = 0; i < tbl->size; i++) {
+		pr_warn(" [Bucket %d] ", i);
+		rht_for_each_rcu(he, tbl, i) {
+			hash = head_hashfn(ht, tbl, he);
+			pr_cont("[hash = %#x, lock = %p] ",
+				hash, bucket_lock(tbl, hash));
+		}
+		pr_cont("\n");
+	}
+
+}
+
+static void debug_dump_table(struct rhashtable *ht,
+			     const struct bucket_table *tbl,
+			     unsigned int hash)
+{
+	struct bucket_table *old_tbl, *future_tbl;
+
+	pr_emerg("BUG: lock for hash %#x in table %p not held\n",
+		 hash, tbl);
+
+	rcu_read_lock();
+	future_tbl = rht_dereference_rcu(ht->future_tbl, ht);
+	old_tbl = rht_dereference_rcu(ht->tbl, ht);
+	if (future_tbl != old_tbl) {
+		pr_warn("Future table %p (size: %zd)\n",
+			future_tbl, future_tbl->size);
+		debug_dump_buckets(ht, future_tbl);
+	}
+
+	pr_warn("Table %p (size: %zd)\n", old_tbl, old_tbl->size);
+	debug_dump_buckets(ht, old_tbl);
+
+	rcu_read_unlock();
+}
+
+#define ASSERT_RHT_MUTEX(HT) BUG_ON(!lockdep_rht_mutex_is_held(HT))
+#define ASSERT_BUCKET_LOCK(HT, TBL, HASH)				\
+	do {								\
+		if (unlikely(!lockdep_rht_bucket_is_held(TBL, HASH))) {	\
+			debug_dump_table(HT, TBL, HASH);		\
+			BUG();						\
+		}							\
+	} while (0)
+
+int lockdep_rht_mutex_is_held(struct rhashtable *ht)
+{
+	return (debug_locks) ? lockdep_is_held(&ht->mutex) : 1;
+}
+EXPORT_SYMBOL_GPL(lockdep_rht_mutex_is_held);
+
+int lockdep_rht_bucket_is_held(const struct bucket_table *tbl, u32 hash)
+{
+	spinlock_t *lock = bucket_lock(tbl, hash);
+
+	return (debug_locks) ? lockdep_is_held(lock) : 1;
+}
+EXPORT_SYMBOL_GPL(lockdep_rht_bucket_is_held);
+#else
+#define ASSERT_RHT_MUTEX(HT)
+#define ASSERT_BUCKET_LOCK(HT, TBL, HASH)
+#endif
+
+
 static struct rhash_head __rcu **bucket_tail(struct bucket_table *tbl, u32 n)
 {
 	struct rhash_head __rcu **pprev;
@@ -240,7 +291,7 @@ static void unlock_buckets(struct bucket_table *new_tbl,
  *
  * Returns true if no more work needs to be performed on the bucket.
  */
-static bool hashtable_chain_unzip(const struct rhashtable *ht,
+static bool hashtable_chain_unzip(struct rhashtable *ht,
 				  const struct bucket_table *new_tbl,
 				  struct bucket_table *old_tbl,
 				  size_t old_hash)
@@ -248,7 +299,7 @@ static bool hashtable_chain_unzip(const struct rhashtable *ht,
 	struct rhash_head *he, *p, *next;
 	unsigned int new_hash, new_hash2;
 
-	ASSERT_BUCKET_LOCK(old_tbl, old_hash);
+	ASSERT_BUCKET_LOCK(ht, old_tbl, old_hash);
 
 	/* Old bucket empty, no work needed. */
 	p = rht_dereference_bucket(old_tbl->buckets[old_hash], old_tbl,
@@ -257,7 +308,7 @@ static bool hashtable_chain_unzip(const struct rhashtable *ht,
 		return false;
 
 	new_hash = head_hashfn(ht, new_tbl, p);
-	ASSERT_BUCKET_LOCK(new_tbl, new_hash);
+	ASSERT_BUCKET_LOCK(ht, 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
@@ -265,7 +316,7 @@ static bool hashtable_chain_unzip(const struct rhashtable *ht,
 	 */
 	rht_for_each_continue(he, p->next, old_tbl, old_hash) {
 		new_hash2 = head_hashfn(ht, new_tbl, he);
-		ASSERT_BUCKET_LOCK(new_tbl, new_hash2);
+		ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash2);
 
 		if (new_hash != new_hash2)
 			break;
-- 
1.9.3

[PATCH 5/6] rhashtable: Add more lock verification

[Thomas Graf]

Catch hash miscalculations which result in hard to track down race
conditions.

Signed-off-by: Thomas Graf <tgraf@suug.ch>
---
 lib/rhashtable.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index c2c3949..ef0816b 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -348,9 +348,11 @@ static bool hashtable_chain_unzip(struct rhashtable *ht,
 	return !rht_is_a_nulls(p);
 }
 
-static void link_old_to_new(struct bucket_table *new_tbl,
+static void link_old_to_new(struct rhashtable *ht, struct bucket_table *new_tbl,
 			    unsigned int new_hash, struct rhash_head *entry)
 {
+	ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
+
 	rcu_assign_pointer(*bucket_tail(new_tbl, new_hash), entry);
 }
 
@@ -406,7 +408,7 @@ int rhashtable_expand(struct rhashtable *ht)
 		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(new_tbl, new_hash, he);
+				link_old_to_new(ht, new_tbl, new_hash, he);
 				break;
 			}
 		}
@@ -492,6 +494,7 @@ int rhashtable_shrink(struct rhashtable *ht)
 
 		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]);
 
@@ -557,6 +560,8 @@ static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 	struct rhash_head *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
@@ -641,6 +646,7 @@ restart:
 			continue;
 		}
 
+		ASSERT_BUCKET_LOCK(ht, tbl, hash);
 		rcu_assign_pointer(*pprev, obj->next);
 
 		ret = true;
-- 
1.9.3

[PATCH 6/6] rhashtable: Avoid bucket cross reference after removal

[Thomas Graf]

During a resize, when two buckets in the larger table map to
a single bucket in the smaller table and the new table has already
been (partially) linked to the old table. Removal of an element
may result the bucket in the larger table to point to entries
which all hash to a different value than the bucket index. Thus
causing two buckets to point to the same sub chain after unzipping.
This is not illegal *during* the resize phase but after it has
completed.

Keep the old table around until all of the unzipping is done to
allow the removal code to only search for matching hashed entries
during this special period.

Reported-by: Ying Xue <ying.xue@windriver.com>
Fixes: 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
Signed-off-by: Thomas Graf <tgraf@suug.ch>
---
 lib/rhashtable.c | 26 +++++++++++++++++---------
 1 file changed, 17 insertions(+), 9 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index ef0816b..5919d63 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -415,12 +415,6 @@ int rhashtable_expand(struct rhashtable *ht)
 		unlock_buckets(new_tbl, old_tbl, new_hash);
 	}
 
-	/* 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
@@ -445,6 +439,7 @@ int rhashtable_expand(struct rhashtable *ht)
 		}
 	}
 
+	rcu_assign_pointer(ht->tbl, new_tbl);
 	synchronize_rcu();
 
 	bucket_table_free(old_tbl);
@@ -627,14 +622,14 @@ 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;
+	struct rhash_head *he, *he2;
 	unsigned int hash, new_hash;
 	bool ret = false;
 
 	rcu_read_lock();
 	tbl = old_tbl = rht_dereference_rcu(ht->tbl, ht);
 	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	new_hash = head_hashfn(ht, new_tbl, obj);
+	new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
 
 	lock_buckets(new_tbl, old_tbl, new_hash);
 restart:
@@ -647,8 +642,21 @@ restart:
 		}
 
 		ASSERT_BUCKET_LOCK(ht, tbl, hash);
-		rcu_assign_pointer(*pprev, obj->next);
 
+		if (unlikely(new_tbl != tbl)) {
+			rht_for_each_continue(he2, he->next, tbl, hash) {
+				if (head_hashfn(ht, tbl, he2) == hash) {
+					rcu_assign_pointer(*pprev, he2);
+					goto found;
+				}
+			}
+
+			INIT_RHT_NULLS_HEAD(*pprev, ht, hash);
+		} else {
+			rcu_assign_pointer(*pprev, obj->next);
+		}
+
+found:
 		ret = true;
 		break;
 	}
-- 
1.9.3

Re: [PATCH 0/6 v2 net-next] rhashtable fixes

[Ying Xue]

Hi Thomas,

After I applied the sires, it sounds like panic doesn't occur any more. But soft
lockup still happens although the frequency of its reproduction is much lower
than before. Please take a look at its relevant log:

root@localhost:/mnt# ./bind2 10000
Create 10000 ports
^[[A[   83.760030] ------------[ cut here ]------------
[   83.760428] WARNING: CPU: 6 PID: 0 at net/sched/sch_generic.c:303
dev_watchdog+0x247/0x250()
[   83.760944] NETDEV WATCHDOG: eth0 (e1000): transmit queue 0 timed out
[   83.761357] Modules linked in: tipc
[   83.761607] CPU: 6 PID: 0 Comm: swapper/6 Not tainted 3.19.0-rc6+ #185
[   83.762025] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2007
[   83.762385]  000000000000012f ffff880017d83d08 ffffffff8175d285 000000000000104b
[   83.762884]  ffff880017d83d58 ffff880017d83d48 ffffffff81059717 ffffffff00000000
[   83.763384]  ffff880015e92000 ffff880015e923e0 ffff88000008ae00 0000000000000001
[   83.763883] Call Trace:
[   83.764018]  <IRQ>  [<ffffffff8175d285>] dump_stack+0x4c/0x65
[   83.764018]  [<ffffffff81059717>] warn_slowpath_common+0x97/0xe0
[   83.764018]  [<ffffffff81059816>] warn_slowpath_fmt+0x46/0x50
[   83.764018]  [<ffffffff81654617>] dev_watchdog+0x247/0x250
[   83.764018]  [<ffffffff816543d0>] ? pfifo_fast_dequeue+0xe0/0xe0
[   83.764018]  [<ffffffff816543d0>] ? pfifo_fast_dequeue+0xe0/0xe0
[   83.764018]  [<ffffffff810c5ebc>] call_timer_fn+0x8c/0x1e0
[   83.764018]  [<ffffffff810c5e35>] ? call_timer_fn+0x5/0x1e0
[   83.764018]  [<ffffffff817669d0>] ? _raw_spin_unlock_irq+0x30/0x40
[   83.764018]  [<ffffffff816543d0>] ? pfifo_fast_dequeue+0xe0/0xe0
[   83.764018]  [<ffffffff810c7994>] run_timer_softirq+0x2d4/0x320
[   83.764018]  [<ffffffff810d6214>] ? clockevents_program_event+0x74/0x100
[   83.764018]  [<ffffffff8105d653>] __do_softirq+0x123/0x360
[   83.764018]  [<ffffffff8105db2e>] irq_exit+0x8e/0xb0
[   83.764018]  [<ffffffff81769b2a>] smp_apic_timer_interrupt+0x4a/0x60
[   83.764018]  [<ffffffff81767eaf>] apic_timer_interrupt+0x6f/0x80
[   83.764018]  <EOI>  [<ffffffff8100d174>] ? default_idle+0x24/0x100
[   83.764018]  [<ffffffff8100d172>] ? default_idle+0x22/0x100
[   83.764018]  [<ffffffff8100daaf>] arch_cpu_idle+0xf/0x20
[   83.764018]  [<ffffffff8109a509>] cpu_startup_entry+0x2c9/0x3c0
[   83.764018]  [<ffffffff810d5ea2>] ? clockevents_register_device+0xe2/0x140
[   83.764018]  [<ffffffff810333c1>] start_secondary+0x141/0x150
[   83.764018] ---[ end trace 57f25794303fa7e9 ]---
[   83.776059] e1000 0000:00:03.0 eth0: Reset adapter
[   88.088005] NMI watchdog: BUG: soft lockup - CPU#0 stuck for 23s! [bind2:667]
[   88.088005] Modules linked in: tipc
[   88.088005] irq event stamp: 25367
[   88.088005] hardirqs last  enabled at (25366): [<ffffffff81767be0>]
restore_args+0x0/0x30
[   88.088005] hardirqs last disabled at (25367): [<ffffffff81767eaa>]
apic_timer_interrupt+0x6a/0x80
[   88.088005] softirqs last  enabled at (11842): [<ffffffff8139d66a>]
unlock_buckets+0x5a/0x70
[   88.088005] softirqs last disabled at (11880): [<ffffffff8139d51a>]
lock_buckets+0x3a/0x80
[   88.088005] CPU: 0 PID: 667 Comm: bind2 Tainted: G        W      3.19.0-rc6+ #185
[   88.088005] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2007
[   88.088005] task: ffff880015038000 ti: ffff880000198000 task.ti: ffff880000198000
[   88.088005] RIP: 0010:[<ffffffff81390b6a>]  [<ffffffff81390b6a>] memcmp+0x3a/0x50
[   88.088005] RSP: 0018:ffff88000019bcf8  EFLAGS: 00000212
[   88.088005] RAX: 00000000000000a8 RBX: ffff880000198000 RCX: 000000000000002b
[   88.088005] RDX: 0000000000000004 RSI: ffff8800153dd87c RDI: ffff88000019747c
[   88.088005] RBP: ffff88000019bcf8 R08: 000000002d196482 R09: ffff8800153dd87c
[   88.088005] R10: 0000000000000002 R11: 0000000000000001 R12: 0000000000000000
[   88.088005] R13: 0000000000000001 R14: 0000000000000000 R15: 0000000000000000
[   88.088005] FS:  0000000000000000(0000) GS:ffff880017c00000(0063)
knlGS:00000000f75b3900
[   88.088005] CS:  0010 DS: 002b ES: 002b CR0: 000000008005003b
[   88.088005] CR2: 0000000008acec4c CR3: 000000001479e000 CR4: 00000000000006f0
[   88.088005] Stack:
[   88.088005]  ffff88000019bd08 ffffffff8139d698 ffff88000019bd68 ffffffff8139e5ce
[   88.088005]  ffffffff8139e540 00000002810a6a25 069b23b200000000 ffff88001328e000
[   88.088005]  ffff88000019bd68 ffff880000149090 ffff88001328e000 00000000000001b2
[   88.088005] Call Trace:
[   88.088005]  [<ffffffff8139d698>] rhashtable_compare+0x18/0x20
[   88.088005]  [<ffffffff8139e5ce>] rhashtable_lookup_compare+0x8e/0x120
[   88.088005]  [<ffffffff8139e540>] ? rht_deferred_worker+0xa0/0xa0
[   88.088005]  [<ffffffff8139e72f>] rhashtable_lookup_compare_insert+0x9f/0x110
[   88.088005]  [<ffffffff8139e6c5>] ? rhashtable_lookup_compare_insert+0x35/0x110
[   88.088005]  [<ffffffff8139d680>] ? unlock_buckets+0x70/0x70
[   88.088005]  [<ffffffff8139e7d2>] rhashtable_lookup_insert+0x32/0x40
[   88.088005]  [<ffffffffa00164ec>] tipc_sk_create+0x1ec/0x340 [tipc]
[   88.088005]  [<ffffffffa00163a2>] ? tipc_sk_create+0xa2/0x340 [tipc]
[   88.088005]  [<ffffffff81615e60>] __sock_create+0x170/0x270
[   88.088005]  [<ffffffff81615daf>] ? __sock_create+0xbf/0x270
[   88.088005]  [<ffffffff81615fc0>] sock_create+0x30/0x40
[   88.088005]  [<ffffffff81616d36>] SyS_socket+0x36/0xb0
[   88.088005]  [<ffffffff8118500f>] ? might_fault+0xaf/0xc0
[   88.088005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[   88.088005]  [<ffffffff816523bb>] compat_SyS_socketcall+0x6b/0x200
[   88.088005]  [<ffffffff817693f3>] sysenter_dispatch+0x7/0x1f
[   88.088005]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[   88.088005] Code: b6 0e 29 c8 75 25 48 83 ea 01 31 c9 eb 18 0f 1f 00 44 0f b6
4c 0f 01 44 0f b6 44 0e 01 48 83 c1 01 45 29 c1 75 0b 48 39 d1 75 e6 <5d> c3 0f
1f 40 00 44 89 c8 5d c3 66 66 2e 0f 1f 84 00 00 00 00
[  116.088006] NMI watchdog: BUG: soft lockup - CPU#0 stuck for 23s! [bind2:667]
[  116.088006] Modules linked in: tipc
[  116.088006] irq event stamp: 39357
[  116.088006] hardirqs last  enabled at (39356): [<ffffffff81767be0>]
restore_args+0x0/0x30
[  116.088006] hardirqs last disabled at (39357): [<ffffffff81767eaa>]
apic_timer_interrupt+0x6a/0x80
[  116.088006] softirqs last  enabled at (11842): [<ffffffff8139d66a>]
unlock_buckets+0x5a/0x70
[  116.088006] softirqs last disabled at (11880): [<ffffffff8139d51a>]
lock_buckets+0x3a/0x80
[  116.088006] CPU: 0 PID: 667 Comm: bind2 Tainted: G        W    L 3.19.0-rc6+ #185
[  116.088006] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2007
[  116.088006] task: ffff880015038000 ti: ffff880000198000 task.ti: ffff880000198000
[  116.088006] RIP: 0010:[<ffffffff81390b3e>]  [<ffffffff81390b3e>] memcmp+0xe/0x50
[  116.088006] RSP: 0018:ffff88000019bcf8  EFLAGS: 00000202
[  116.088006] RAX: 00000000000000d3 RBX: ffffffff81767be0 RCX: 000000000000002b
[  116.088006] RDX: 0000000000000004 RSI: ffff8800153dd87c RDI: ffff88000019747c
[  116.088006] RBP: ffff88000019bcf8 R08: 000000002d196482 R09: ffff8800153dd87c
[  116.088006] R10: 0000000000000002 R11: 0000000000000001 R12: ffff88000019bc68
[  116.088006] R13: 0000000000000046 R14: ffff880000198000 R15: ffff880015038000
[  116.088006] FS:  0000000000000000(0000) GS:ffff880017c00000(0063)
knlGS:00000000f75b3900
[  116.088006] CS:  0010 DS: 002b ES: 002b CR0: 000000008005003b
[  116.088006] CR2: 0000000008acec4c CR3: 000000001479e000 CR4: 00000000000006f0
[  116.088006] Stack:
[  116.088006]  ffff88000019bd08 ffffffff8139d698 ffff88000019bd68 ffffffff8139e5ce
[  116.088006]  ffffffff8139e540 00000002810a6a25 069b23b200000000 ffff88001328e000
[  116.088006]  ffff88000019bd68 ffff880000149090 ffff88001328e000 00000000000001b2
[  116.088006] Call Trace:
[  116.088006]  [<ffffffff8139d698>] rhashtable_compare+0x18/0x20
[  116.088006]  [<ffffffff8139e5ce>] rhashtable_lookup_compare+0x8e/0x120
[  116.088006]  [<ffffffff8139e540>] ? rht_deferred_worker+0xa0/0xa0
[  116.088006]  [<ffffffff8139e72f>] rhashtable_lookup_compare_insert+0x9f/0x110
[  116.088006]  [<ffffffff8139e6c5>] ? rhashtable_lookup_compare_insert+0x35/0x110
[  116.088006]  [<ffffffff8139d680>] ? unlock_buckets+0x70/0x70
[  116.088006]  [<ffffffff8139e7d2>] rhashtable_lookup_insert+0x32/0x40
[  116.088006]  [<ffffffffa00164ec>] tipc_sk_create+0x1ec/0x340 [tipc]
[  116.088006]  [<ffffffffa00163a2>] ? tipc_sk_create+0xa2/0x340 [tipc]
[  116.088006]  [<ffffffff81615e60>] __sock_create+0x170/0x270
[  116.088006]  [<ffffffff81615daf>] ? __sock_create+0xbf/0x270
[  116.088006]  [<ffffffff81615fc0>] sock_create+0x30/0x40
[  116.088006]  [<ffffffff81616d36>] SyS_socket+0x36/0xb0
[  116.088006]  [<ffffffff8118500f>] ? might_fault+0xaf/0xc0
[  116.088006]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  116.088006]  [<ffffffff816523bb>] compat_SyS_socketcall+0x6b/0x200
[  116.088006]  [<ffffffff817693f3>] sysenter_dispatch+0x7/0x1f
[  116.088006]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[  116.088006] Code: 06 01 5d c3 66 0f 1f 84 00 00 00 00 00 31 c0 c6 06 00 5d c3
66 0f 1f 84 00 00 00 00 00 55 31 c0 48 85 d2 48 89 e5 74 2f 0f b6 07 <0f> b6 0e
29 c8 75 25 48 83 ea 01 31 c9 eb 18 0f 1f 00 44 0f b6
[  121.200005] INFO: rcu_sched self-detected stall on CPU { 0}  (t=15000 jiffies
g=915 c=914 q=1273)
[  121.200005] Task dump for CPU 0:
[  121.200005] bind2           R  running task        0   667    614 0x20020008
[  121.200005]  0000000000000266 ffff880017c03d68 ffffffff81086c26 ffffffff81086b88
[  121.200005]  00000000bd07bd06 0000000000000000 ffffffff81c53940 ffff880017c03d88
[  121.200005]  ffffffff8108a57f ffffffff81c53940 ffffffff81c53940 ffff880017c03db8
[  121.200005] Call Trace:
[  121.200005]  <IRQ>  [<ffffffff81086c26>] sched_show_task+0x106/0x170
[  121.200005]  [<ffffffff81086b88>] ? sched_show_task+0x68/0x170
[  121.200005]  [<ffffffff8108a57f>] dump_cpu_task+0x3f/0x50
[  121.200005]  [<ffffffff810bfa7b>] rcu_dump_cpu_stacks+0x8b/0xc0
[  121.200005]  [<ffffffff810c33d0>] rcu_check_callbacks+0x480/0x6d0
[  121.200005]  [<ffffffff810a133d>] ? trace_hardirqs_off+0xd/0x10
[  121.200005]  [<ffffffff810c8408>] update_process_times+0x38/0x70
[  121.200005]  [<ffffffff810d8623>] tick_sched_handle.isra.15+0x33/0x70
[  121.200005]  [<ffffffff810d88cb>] tick_sched_timer+0x4b/0x80
[  121.200005]  [<ffffffff810c8d8b>] __run_hrtimer+0x9b/0x290
[  121.200005]  [<ffffffff810d8880>] ? tick_sched_do_timer+0x40/0x40
[  121.200005]  [<ffffffff810c95e4>] ? hrtimer_interrupt+0x74/0x260
[  121.200005]  [<ffffffff810c9677>] hrtimer_interrupt+0x107/0x260
[  121.200005]  [<ffffffff8139d680>] ? unlock_buckets+0x70/0x70
[  121.200005]  [<ffffffff81034cb9>] local_apic_timer_interrupt+0x39/0x60
[  121.200005]  [<ffffffff81769b25>] smp_apic_timer_interrupt+0x45/0x60
[  121.200005]  [<ffffffff81767eaf>] apic_timer_interrupt+0x6f/0x80
[  121.200005]  <EOI>  [<ffffffff8139e5c8>] ? rhashtable_lookup_compare+0x88/0x120
[  121.200005]  [<ffffffff8139e5ce>] ? rhashtable_lookup_compare+0x8e/0x120
[  121.200005]  [<ffffffff8139e540>] ? rht_deferred_worker+0xa0/0xa0
[  121.200005]  [<ffffffff8139e72f>] rhashtable_lookup_compare_insert+0x9f/0x110
[  121.200005]  [<ffffffff8139e6c5>] ? rhashtable_lookup_compare_insert+0x35/0x110
[  121.200005]  [<ffffffff8139d680>] ? unlock_buckets+0x70/0x70
[  121.200005]  [<ffffffff8139e7d2>] rhashtable_lookup_insert+0x32/0x40
[  121.200005]  [<ffffffffa00164ec>] tipc_sk_create+0x1ec/0x340 [tipc]
[  121.200005]  [<ffffffffa00163a2>] ? tipc_sk_create+0xa2/0x340 [tipc]
[  121.200005]  [<ffffffff81615e60>] __sock_create+0x170/0x270
[  121.200005]  [<ffffffff81615daf>] ? __sock_create+0xbf/0x270
[  121.200005]  [<ffffffff81615fc0>] sock_create+0x30/0x40
[  121.200005]  [<ffffffff81616d36>] SyS_socket+0x36/0xb0
[  121.200005]  [<ffffffff8118500f>] ? might_fault+0xaf/0xc0
[  121.200005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  121.200005]  [<ffffffff816523bb>] compat_SyS_socketcall+0x6b/0x200
[  121.200005]  [<ffffffff817693f3>] sysenter_dispatch+0x7/0x1f
[  121.200005]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[  121.220016] INFO: rcu_sched detected stalls on CPUs/tasks: { 0} (detected by
5, t=15006 jiffies, g=915, c=914, q=1273)
[  121.223334] Task dump for CPU 0:
[  121.223334] bind2           R  running task        0   667    614 0x20020008
[  121.223334]  000000000000002b 0000000000000004 ffff8800153dd87c ffff88000019747c
[  121.223334]  ffffffffffffff10 ffffffff81390b6a ffff8800153dd87c ffff880000197000
[  121.228029]  ffffffffffffff10 ffffffff8139e5c8 0000000000000010 ffff88000019bd08
[  121.228029] Call Trace:
[  121.228029]  [<ffffffff8139e5c8>] ? rhashtable_lookup_compare+0x88/0x120
[  121.228029]  [<ffffffff8139d698>] ? rhashtable_compare+0x18/0x20
[  121.228029]  [<ffffffff8139e5ce>] ? rhashtable_lookup_compare+0x8e/0x120
[  121.228029]  [<ffffffff8139e540>] ? rht_deferred_worker+0xa0/0xa0
[  121.228029]  [<ffffffff8139e72f>] ? rhashtable_lookup_compare_insert+0x9f/0x110
[  121.228029]  [<ffffffff8139e6c5>] ? rhashtable_lookup_compare_insert+0x35/0x110
[  121.228029]  [<ffffffff8139d680>] ? unlock_buckets+0x70/0x70
[  121.236021]  [<ffffffff8139e7d2>] ? rhashtable_lookup_insert+0x32/0x40
[  121.236021]  [<ffffffffa00164ec>] ? tipc_sk_create+0x1ec/0x340 [tipc]
[  121.236021]  [<ffffffffa00163a2>] ? tipc_sk_create+0xa2/0x340 [tipc]
[  121.236021]  [<ffffffff81615e60>] ? __sock_create+0x170/0x270
[  121.236021]  [<ffffffff81615daf>] ? __sock_create+0xbf/0x270
[  121.236021]  [<ffffffff81615fc0>] ? sock_create+0x30/0x40
[  121.236021]  [<ffffffff81616d36>] ? SyS_socket+0x36/0xb0
[  121.236021]  [<ffffffff8118500f>] ? might_fault+0xaf/0xc0
[  121.236021]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  121.244025]  [<ffffffff816523bb>] ? compat_SyS_socketcall+0x6b/0x200
[  121.244025]  [<ffffffff817693f3>] ? sysenter_dispatch+0x7/0x1f
[  121.244025]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[  148.088005] NMI watchdog: BUG: soft lockup - CPU#0 stuck for 22s! [bind2:667]
[  148.088005] Modules linked in: tipc
[  148.088005] irq event stamp: 55335
[  148.088005] hardirqs last  enabled at (55334): [<ffffffff81767be0>]
restore_args+0x0/0x30
[  148.088005] hardirqs last disabled at (55335): [<ffffffff81767eaa>]
apic_timer_interrupt+0x6a/0x80
[  148.088005] softirqs last  enabled at (11842): [<ffffffff8139d66a>]
unlock_buckets+0x5a/0x70
[  148.088005] softirqs last disabled at (11880): [<ffffffff8139d51a>]
lock_buckets+0x3a/0x80
[  148.088005] CPU: 0 PID: 667 Comm: bind2 Tainted: G        W    L 3.19.0-rc6+ #185
[  148.088005] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2007
[  148.088005] task: ffff880015038000 ti: ffff880000198000 task.ti: ffff880000198000
[  148.088005] RIP: 0010:[<ffffffff81390b31>]  [<ffffffff81390b31>] memcmp+0x1/0x50
[  148.088005] RSP: 0018:ffff88000019bcf8  EFLAGS: 00000282
[  148.088005] RAX: ffff880000149090 RBX: ffff88000019bc78 RCX: 000000000000002b
[  148.088005] RDX: 0000000000000004 RSI: ffff8800153dd87c RDI: ffff88000019747c
[  148.088005] RBP: ffff88000019bd08 R08: 000000002d196482 R09: ffff8800153dd87c
[  148.088005] R10: 0000000000000002 R11: 0000000000000001 R12: ffff880000198000
[  148.088005] R13: ffff880015038000 R14: 0000000000000000 R15: 0000000000000001
[  148.088005] FS:  0000000000000000(0000) GS:ffff880017c00000(0063)
knlGS:00000000f75b3900
[  148.088005] CS:  0010 DS: 002b ES: 002b CR0: 000000008005003b
[  148.088005] CR2: 0000000008acec4c CR3: 000000001479e000 CR4: 00000000000006f0
[  148.088005] Stack:
[  148.088005]  ffff88000019bd08 ffffffff8139d698 ffff88000019bd68 ffffffff8139e5ce
[  148.088005]  ffffffff8139e540 00000002810a6a25 069b23b200000000 ffff88001328e000
[  148.088005]  ffff88000019bd68 ffff880000149090 ffff88001328e000 00000000000001b2
[  148.088005] Call Trace:
[  148.088005]  [<ffffffff8139d698>] ? rhashtable_compare+0x18/0x20
[  148.088005]  [<ffffffff8139e5ce>] rhashtable_lookup_compare+0x8e/0x120
[  148.088005]  [<ffffffff8139e540>] ? rht_deferred_worker+0xa0/0xa0
[  148.088005]  [<ffffffff8139e72f>] rhashtable_lookup_compare_insert+0x9f/0x110
[  148.088005]  [<ffffffff8139e6c5>] ? rhashtable_lookup_compare_insert+0x35/0x110
[  148.088005]  [<ffffffff8139d680>] ? unlock_buckets+0x70/0x70
[  148.088005]  [<ffffffff8139e7d2>] rhashtable_lookup_insert+0x32/0x40
[  148.088005]  [<ffffffffa00164ec>] tipc_sk_create+0x1ec/0x340 [tipc]
[  148.088005]  [<ffffffffa00163a2>] ? tipc_sk_create+0xa2/0x340 [tipc]
[  148.088005]  [<ffffffff81615e60>] __sock_create+0x170/0x270
[  148.088005]  [<ffffffff81615daf>] ? __sock_create+0xbf/0x270
[  148.088005]  [<ffffffff81615fc0>] sock_create+0x30/0x40
[  148.088005]  [<ffffffff81616d36>] SyS_socket+0x36/0xb0
[  148.088005]  [<ffffffff8118500f>] ? might_fault+0xaf/0xc0
[  148.088005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  148.088005]  [<ffffffff816523bb>] compat_SyS_socketcall+0x6b/0x200
[  148.088005]  [<ffffffff817693f3>] sysenter_dispatch+0x7/0x1f
[  148.088005]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[  148.088005] Code: 00 00 3c 30 74 14 3c 31 75 e9 31 c0 c6 06 01 5d c3 66 0f 1f
84 00 00 00 00 00 31 c0 c6 06 00 5d c3 66 0f 1f 84 00 00 00 00 00 55 <31> c0 48
85 d2 48 89 e5 74 2f 0f b6 07 0f b6 0e 29 c8 75 25 48

Regards,
Ying

On 02/05/2015 09:03 AM, Thomas Graf wrote:
> This series fixes all remaining known issues with rhashtable that
> have been reported. In particular the race condition reported by
> Ying Xue.
> 
> ---
> Dave/Herbert: I'm posting this now as it fixes real issues. I'm
> fine with taking Herbert's rehash patches instead if they resolve
> all the reported issues as well.
> 
> v2:
>  - Rebased on top of Herbert Xu's iterator code
>  - Fixed last remaining race that remained. Special thanks
>    to Daniel Borkmann for assistance while debugging.
> 
> Thomas Graf (6):
>   rhashtable: key_hashfn() must return full hash value
>   rhashtable: Use a single bucket lock for sibling buckets
>   rhashtable: Wait for RCU readers after final unzip work
>   rhashtable: Dump bucket tables on locking violation under
>     PROVE_LOCKING
>   rhashtable: Add more lock verification
>   rhashtable: Avoid bucket cross reference after removal
> 
>  lib/rhashtable.c | 305 ++++++++++++++++++++++++++++++-------------------------
>  1 file changed, 167 insertions(+), 138 deletions(-)
> 
> 

Re: [PATCH 0/6 v2 net-next] rhashtable fixes

[Thomas Graf]

On 02/05/15 at 10:32am, Ying Xue wrote:
> After I applied the sires, it sounds like panic doesn't occur any more. But soft
> lockup still happens although the frequency of its reproduction is much lower
> than before. Please take a look at its relevant log:

Thanks for testing and the report. I had run your bind_netlink test
overnight on a 4 CPU VM. Anything particular that might help trigger it?

Re: [PATCH 0/6 v2 net-next] rhashtable fixes

[Ying Xue]

On 02/05/2015 04:47 PM, Thomas Graf wrote:
> On 02/05/15 at 10:32am, Ying Xue wrote:
>> After I applied the sires, it sounds like panic doesn't occur any more. But soft
>> lockup still happens although the frequency of its reproduction is much lower
>> than before. Please take a look at its relevant log:
> 
> Thanks for testing and the report. I had run your bind_netlink test
> overnight on a 4 CPU VM. Anything particular that might help trigger it?
> 
> 

My hardware platform seems a bit advanced than you, for example, I run the test
case on a 8 CPU VM.

Additionally, I guess the port number you gave the bind_netlink application is a
little small, for instance, my given port number is 9000. Below is my complete
procedures about how to reproduce the soft lockup issue in my environment:

root@localhost:/mnt# gcc -Wall -o bind-netlink bind_netlink.c
root@localhost:/mnt# ulimit -n 100000
root@localhost:/mnt# ./bind-netlink 9000
Create 9000 ports
Created 1000 ports
Created 2000 ports
Created 3000 ports
Created 4000 ports
Created 5000 ports
Created 6000 ports
Created 7000 ports
Created 8000 ports
Created 9000 ports
Ports successfully created, terminating
root@localhost:/mnt# ./bind-netlink 9000
Create 9000 ports
Created 1000 ports
Created 2000 ports
Created 3000 ports
Created 4000 ports
Created 5000 ports
Created 6000 ports
Created 7000 ports
Created 8000 ports
Created 9000 ports
Ports successfully created, terminating
root@localhost:/mnt# ./bind-netlink 9000
Create 9000 ports
[  442.800079] ------------[ cut here ]------------
[  442.800456] WARNING: CPU: 2 PID: 0 at net/sched/sch_generic.c:303
dev_watchdog+0x247/0x250()
[  442.801002] NETDEV WATCHDOG: eth0 (e1000): transmit queue 0 timed out
[  442.801419] Modules linked in: tipc
[  442.801671] CPU: 2 PID: 0 Comm: swapper/2 Not tainted 3.19.0-rc6+ #185
[  442.802091] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2007
[  442.802460]  000000000000012f ffff880017c83d08 ffffffff8175d285 000000000000104e
[  442.802969]  ffff880017c83d58 ffff880017c83d48 ffffffff81059717 ffffffff00000000
[  442.803482]  ffff880015eb2000 ffff880015eb23e0 ffff88000008ae00 0000000000000001
[  442.803981] Call Trace:
[  442.804067]  <IRQ>  [<ffffffff8175d285>] dump_stack+0x4c/0x65
[  442.804067]  [<ffffffff81059717>] warn_slowpath_common+0x97/0xe0
[  442.804067]  [<ffffffff81059816>] warn_slowpath_fmt+0x46/0x50
[  442.804067]  [<ffffffff81654617>] dev_watchdog+0x247/0x250
[  442.804067]  [<ffffffff816543d0>] ? pfifo_fast_dequeue+0xe0/0xe0
[  442.804067]  [<ffffffff816543d0>] ? pfifo_fast_dequeue+0xe0/0xe0
[  442.804067]  [<ffffffff810c5ebc>] call_timer_fn+0x8c/0x1e0
[  442.804067]  [<ffffffff810c5e35>] ? call_timer_fn+0x5/0x1e0
[  442.804067]  [<ffffffff817669d0>] ? _raw_spin_unlock_irq+0x30/0x40
[  442.804067]  [<ffffffff816543d0>] ? pfifo_fast_dequeue+0xe0/0xe0
[  442.804067]  [<ffffffff810c7994>] run_timer_softirq+0x2d4/0x320
[  442.804067]  [<ffffffff810d6214>] ? clockevents_program_event+0x74/0x100
[  442.804067]  [<ffffffff8105d653>] __do_softirq+0x123/0x360
[  442.804067]  [<ffffffff8105db2e>] irq_exit+0x8e/0xb0
[  442.804067]  [<ffffffff81769b2a>] smp_apic_timer_interrupt+0x4a/0x60
[  442.804067]  [<ffffffff81767eaf>] apic_timer_interrupt+0x6f/0x80
[  442.804067]  <EOI>  [<ffffffff8100d174>] ? default_idle+0x24/0x100
[  442.804067]  [<ffffffff8100d172>] ? default_idle+0x22/0x100
[  442.804067]  [<ffffffff8100daaf>] arch_cpu_idle+0xf/0x20
[  442.804067]  [<ffffffff8109a509>] cpu_startup_entry+0x2c9/0x3c0
[  442.804067]  [<ffffffff810d5ea2>] ? clockevents_register_device+0xe2/0x140
[  442.804067]  [<ffffffff810333c1>] start_secondary+0x141/0x150
[  442.804067] ---[ end trace 839863d69c70be7a ]---
[  442.804067] e1000 0000:00:03.0 eth0: Reset adapter
[  452.716005] NMI watchdog: BUG: soft lockup - CPU#7 stuck for 22s!
[bind-netlink:641]
[  452.716005] Modules linked in: tipc
[  452.716005] irq event stamp: 16417
[  452.716005] hardirqs last  enabled at (16416): [<ffffffff81767be0>]
restore_args+0x0/0x30
[  452.716005] hardirqs last disabled at (16417): [<ffffffff81767eaa>]
apic_timer_interrupt+0x6a/0x80
[  452.716005] softirqs last  enabled at (4280): [<ffffffff8161893f>]
lock_sock_nested+0x4f/0xc0
[  452.716005] softirqs last disabled at (4282): [<ffffffff8139d51a>]
lock_buckets+0x3a/0x80
[  452.716005] CPU: 7 PID: 641 Comm: bind-netlink Tainted: G        W
3.19.0-rc6+ #185
[  452.716005] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2007
[  452.716005] task: ffff880013f4c220 ti: ffff880014558000 task.ti: ffff880014558000
[  452.716005] RIP: 0010:[<ffffffff8165d900>]  [<ffffffff8165d900>]
netlink_compare+0x10/0x30
[  452.716005] RSP: 0018:ffff88001455bcf0  EFLAGS: 00000293
[  452.716005] RAX: 0000000000000000 RBX: 0000000000000004 RCX: 000000000bfbcdfb
[  452.716005] RDX: 00000000000002ae RSI: ffff88001455bdb8 RDI: ffff88001651b800
[  452.716005] RBP: ffff88001455bd48 R08: 00000000bef85eb8 R09: ffff880011bf1c68
[  452.716005] R10: 0000000000000004 R11: 0000000000000001 R12: ffffffff81767be0
[  452.716005] R13: ffffffff810c2d18 R14: ffff88001455bc58 R15: 0000000000000046
[  452.716005] FS:  0000000000000000(0000) GS:ffff880017dc0000(0063)
knlGS:00000000f753e900
[  452.716005] CS:  0010 DS: 002b ES: 002b CR0: 000000008005003b
[  452.716005] CR2: 00000000f75f8b30 CR3: 0000000015abd000 CR4: 00000000000006e0
[  452.716005] Stack:
[  452.716005]  ffffffff8139e5ce ffffffff8139e540 000000028105d9c8 00c662f713caac00
[  452.716005]  ffff880013d15200 ffff88001455bd48 ffff880016500000 ffff880013caac00
[  452.716005]  0000000000000007 ffff880013d15200 ffff880011bf1e08 ffff88001455bda8
[  452.716005] Call Trace:
[  452.716005]  [<ffffffff8139e5ce>] ? rhashtable_lookup_compare+0x8e/0x120
[  452.716005]  [<ffffffff8139e540>] ? rht_deferred_worker+0xa0/0xa0
[  452.716005]  [<ffffffff8139e72f>] rhashtable_lookup_compare_insert+0x9f/0x110
[  452.716005]  [<ffffffff8139e6c5>] ? rhashtable_lookup_compare_insert+0x35/0x110
[  452.716005]  [<ffffffff8165d8f0>] ? netlink_overrun+0x50/0x50
[  452.716005]  [<ffffffff8165e1d3>] ? netlink_insert+0x43/0xf0
[  452.716005]  [<ffffffff8165e221>] netlink_insert+0x91/0xf0
[  452.716005]  [<ffffffff81660550>] netlink_bind+0x210/0x260
[  452.716005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  452.716005]  [<ffffffff810a5b10>] ? lock_release_non_nested+0xa0/0x340
[  452.716005]  [<ffffffff81616ce4>] SYSC_bind+0xa4/0xc0
[  452.716005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  452.716005]  [<ffffffff81616fde>] SyS_bind+0xe/0x10
[  452.716005]  [<ffffffff816523f8>] compat_SyS_socketcall+0xa8/0x200
[  452.716005]  [<ffffffff817693f3>] sysenter_dispatch+0x7/0x1f
[  452.716005]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[  452.716005] Code: f0 ff 83 98 01 00 00 48 83 c4 08 5b 5d c3 66 66 66 66 2e 0f
1f 84 00 00 00 00 00 0f 1f 44 00 00 31 c0 8b 56 08 39 97 68 04 00 00 <55> 48 89
e5 74 0a 5d c3 0f 1f 84 00 00 00 00 00 48 8b 47 30 48
[  480.716005] NMI watchdog: BUG: soft lockup - CPU#7 stuck for 22s!
[bind-netlink:641]
[  480.716005] Modules linked in: tipc
[  480.716005] irq event stamp: 30405
[  480.716005] hardirqs last  enabled at (30404): [<ffffffff81767be0>]
restore_args+0x0/0x30
[  480.716005] hardirqs last disabled at (30405): [<ffffffff81767eaa>]
apic_timer_interrupt+0x6a/0x80
[  480.716005] softirqs last  enabled at (4280): [<ffffffff8161893f>]
lock_sock_nested+0x4f/0xc0
[  480.716005] softirqs last disabled at (4282): [<ffffffff8139d51a>]
lock_buckets+0x3a/0x80
[  480.716005] CPU: 7 PID: 641 Comm: bind-netlink Tainted: G        W    L
3.19.0-rc6+ #185
[  480.716005] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2007
[  480.716005] task: ffff880013f4c220 ti: ffff880014558000 task.ti: ffff880014558000
[  480.716005] RIP: 0010:[<ffffffff8139e5c1>]  [<ffffffff8139e5c1>]
rhashtable_lookup_compare+0x81/0x120
[  480.716005] RSP: 0018:ffff88001455bcf8  EFLAGS: 00000246
[  480.716005] RAX: 0000000000000000 RBX: ffffffff81767be0 RCX: 000000000bfbcdfb
[  480.716005] RDX: 00000000000002ae RSI: ffff88001455bdb8 RDI: ffff88001651b800
[  480.716005] RBP: ffff88001455bd48 R08: 00000000bef85eb8 R09: ffff880011bf1c68
[  480.716005] R10: 0000000000000004 R11: 0000000000000001 R12: ffff88001455bc68
[  480.716005] R13: 0000000000000046 R14: ffff880014558000 R15: ffff880013f4c220
[  480.716005] FS:  0000000000000000(0000) GS:ffff880017dc0000(0063)
knlGS:00000000f753e900
[  480.716005] CS:  0010 DS: 002b ES: 002b CR0: 000000008005003b
[  480.716005] CR2: 00000000f75f8b30 CR3: 0000000015abd000 CR4: 00000000000006e0
[  480.716005] Stack:
[  480.716005]  ffffffff8139e540 000000028105d9c8 00c662f713caac00 ffff880013d15200
[  480.716005]  ffff88001455bd48 ffff880016500000 ffff880013caac00 0000000000000007
[  480.716005]  ffff880013d15200 ffff880011bf1e08 ffff88001455bda8 ffffffff8139e72f
[  480.716005] Call Trace:
[  480.716005]  [<ffffffff8139e540>] ? rht_deferred_worker+0xa0/0xa0
[  480.716005]  [<ffffffff8139e72f>] rhashtable_lookup_compare_insert+0x9f/0x110
[  480.716005]  [<ffffffff8139e6c5>] ? rhashtable_lookup_compare_insert+0x35/0x110
[  480.716005]  [<ffffffff8165d8f0>] ? netlink_overrun+0x50/0x50
[  480.716005]  [<ffffffff8165e1d3>] ? netlink_insert+0x43/0xf0
[  480.716005]  [<ffffffff8165e221>] netlink_insert+0x91/0xf0
[  480.716005]  [<ffffffff81660550>] netlink_bind+0x210/0x260
[  480.716005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  480.716005]  [<ffffffff810a5b10>] ? lock_release_non_nested+0xa0/0x340
[  480.716005]  [<ffffffff81616ce4>] SYSC_bind+0xa4/0xc0
[  480.716005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  480.716005]  [<ffffffff81616fde>] SyS_bind+0xe/0x10
[  480.716005]  [<ffffffff816523f8>] compat_SyS_socketcall+0xa8/0x200
[  480.716005]  [<ffffffff817693f3>] sysenter_dispatch+0x7/0x1f
[  480.716005]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[  480.716005] Code: 73 20 48 89 45 c8 ff 53 60 c1 e8 05 89 45 c4 48 8b 55 c8 48
8b 02 83 e8 01 23 45 c4 48 83 c0 02 4c 8b 74 c2 08 41 f6 c6 01 75 1a <4c> 89 f7
48 2b 7b 30 4c 89 ee 41 ff d4 84 c0 75 46 4d 8b 36 41
[  488.456005] INFO: rcu_sched self-detected stall on CPU { 7}  (t=15000 jiffies
g=472 c=471 q=113)
[  488.456005] Task dump for CPU 7:
[  488.456005] bind-netlink    R  running task        0   641    569 0x20020008
[  488.456005]  0000000000000239 ffff880017dc3d68 ffffffff81086c26 ffffffff81086b88
[  488.456005]  000000003b803b7f 0000000000000007 ffffffff81c53940 ffff880017dc3d88
[  488.456005]  ffffffff8108a57f ffffffff81c53940 ffffffff81c53940 ffff880017dc3db8
[  488.456005] Call Trace:
[  488.456005]  <IRQ>  [<ffffffff81086c26>] sched_show_task+0x106/0x170
[  488.456005]  [<ffffffff81086b88>] ? sched_show_task+0x68/0x170
[  488.456005]  [<ffffffff8108a57f>] dump_cpu_task+0x3f/0x50
[  488.456005]  [<ffffffff810bfa7b>] rcu_dump_cpu_stacks+0x8b/0xc0
[  488.456005]  [<ffffffff810c33d0>] rcu_check_callbacks+0x480/0x6d0
[  488.456005]  [<ffffffff810a133d>] ? trace_hardirqs_off+0xd/0x10
[  488.456005]  [<ffffffff810c8408>] update_process_times+0x38/0x70
[  488.456005]  [<ffffffff810d8623>] tick_sched_handle.isra.15+0x33/0x70
[  488.456005]  [<ffffffff810d88cb>] tick_sched_timer+0x4b/0x80
[  488.456005]  [<ffffffff810c8d8b>] __run_hrtimer+0x9b/0x290
[  488.456005]  [<ffffffff810d8880>] ? tick_sched_do_timer+0x40/0x40
[  488.456005]  [<ffffffff810c95e4>] ? hrtimer_interrupt+0x74/0x260
[  488.456005]  [<ffffffff810c9677>] hrtimer_interrupt+0x107/0x260
[  488.456005]  [<ffffffff8165d8f0>] ? netlink_overrun+0x50/0x50
[  488.456005]  [<ffffffff81034cb9>] local_apic_timer_interrupt+0x39/0x60
[  488.456005]  [<ffffffff81769b25>] smp_apic_timer_interrupt+0x45/0x60
[  488.456005]  [<ffffffff81767eaf>] apic_timer_interrupt+0x6f/0x80
[  488.456005]  <EOI>  [<ffffffff81767be0>] ? retint_restore_args+0xe/0xe
[  488.456005]  [<ffffffff8165d900>] ? netlink_compare+0x10/0x30
[  488.456005]  [<ffffffff8139e5ce>] ? rhashtable_lookup_compare+0x8e/0x120
[  488.456005]  [<ffffffff8139e540>] ? rht_deferred_worker+0xa0/0xa0
[  488.456005]  [<ffffffff8139e72f>] rhashtable_lookup_compare_insert+0x9f/0x110
[  488.456005]  [<ffffffff8139e6c5>] ? rhashtable_lookup_compare_insert+0x35/0x110
[  488.456005]  [<ffffffff8165d8f0>] ? netlink_overrun+0x50/0x50
[  488.456005]  [<ffffffff8165e1d3>] ? netlink_insert+0x43/0xf0
[  488.456005]  [<ffffffff8165e221>] netlink_insert+0x91/0xf0
[  488.456005]  [<ffffffff81660550>] netlink_bind+0x210/0x260
[  488.456005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  488.456005]  [<ffffffff810a5b10>] ? lock_release_non_nested+0xa0/0x340
[  488.456005]  [<ffffffff81616ce4>] SYSC_bind+0xa4/0xc0
[  488.456005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  488.456005]  [<ffffffff81616fde>] SyS_bind+0xe/0x10
[  488.456005]  [<ffffffff816523f8>] compat_SyS_socketcall+0xa8/0x200
[  488.456005]  [<ffffffff817693f3>] sysenter_dispatch+0x7/0x1f
[  488.456005]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[  488.468021] INFO: rcu_sched detected stalls on CPUs/tasks: { 7} (detected by
3, t=15005 jiffies, g=472, c=471, q=113)
[  488.468021] Task dump for CPU 7:
[  488.468021] bind-netlink    R  running task        0   641    569 0x20020008
[  488.468021]  0000000000000000 0000000000000000 ffff88001455bf28 0000000000000002
[  488.468021]  00000000ff856f80 000000000000000c ffff88001455bf28 ffffffff81616fde
[  488.468021]  ffff88001455bf78 ffffffff816523f8 0000000000000001 ff856f980000002f
[  488.468021] Call Trace:
[  488.468021]  [<ffffffff81616fde>] ? SyS_bind+0xe/0x10
[  488.468021]  [<ffffffff816523f8>] ? compat_SyS_socketcall+0xa8/0x200
[  488.468021]  [<ffffffff817693f3>] ? sysenter_dispatch+0x7/0x1f
[  488.468021]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[  512.716007] NMI watchdog: BUG: soft lockup - CPU#7 stuck for 22s!
[bind-netlink:641]
[  512.716007] Modules linked in: tipc
[  512.716007] irq event stamp: 46383
[  512.716007] hardirqs last  enabled at (46382): [<ffffffff81767be0>]
restore_args+0x0/0x30
[  512.716007] hardirqs last disabled at (46383): [<ffffffff81767eaa>]
apic_timer_interrupt+0x6a/0x80
[  512.716007] softirqs last  enabled at (4280): [<ffffffff8161893f>]
lock_sock_nested+0x4f/0xc0
[  512.716007] softirqs last disabled at (4282): [<ffffffff8139d51a>]
lock_buckets+0x3a/0x80
[  512.716007] CPU: 7 PID: 641 Comm: bind-netlink Tainted: G        W    L
3.19.0-rc6+ #185
[  512.716007] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2007
[  512.716007] task: ffff880013f4c220 ti: ffff880014558000 task.ti: ffff880014558000
[  512.716007] RIP: 0010:[<ffffffff8165d900>]  [<ffffffff8165d900>]
netlink_compare+0x10/0x30
[  512.716007] RSP: 0018:ffff88001455bcf0  EFLAGS: 00000293
[  512.716007] RAX: 0000000000000000 RBX: ffffffff81767be0 RCX: 000000000bfbcdfb
[  512.716007] RDX: 00000000000002ae RSI: ffff88001455bdb8 RDI: ffff88001651b800
[  512.716007] RBP: ffff88001455bd48 R08: 00000000bef85eb8 R09: ffff880011bf1c68
[  512.716007] R10: 0000000000000004 R11: 0000000000000001 R12: ffff88001455bc68
[  512.716007] R13: 0000000000000046 R14: ffff880014558000 R15: ffff880013f4c220
[  512.716007] FS:  0000000000000000(0000) GS:ffff880017dc0000(0063)
knlGS:00000000f753e900
[  512.716007] CS:  0010 DS: 002b ES: 002b CR0: 000000008005003b
[  512.716007] CR2: 00000000f75f8b30 CR3: 0000000015abd000 CR4: 00000000000006e0
[  512.716007] Stack:
[  512.716007]  ffffffff8139e5ce ffffffff8139e540 000000028105d9c8 00c662f713caac00
[  512.716007]  ffff880013d15200 ffff88001455bd48 ffff880016500000 ffff880013caac00
[  512.716007]  0000000000000007 ffff880013d15200 ffff880011bf1e08 ffff88001455bda8
[  512.716007] Call Trace:
[  512.716007]  [<ffffffff8139e5ce>] ? rhashtable_lookup_compare+0x8e/0x120
[  512.716007]  [<ffffffff8139e540>] ? rht_deferred_worker+0xa0/0xa0
[  512.716007]  [<ffffffff8139e72f>] rhashtable_lookup_compare_insert+0x9f/0x110
[  512.716007]  [<ffffffff8139e6c5>] ? rhashtable_lookup_compare_insert+0x35/0x110
[  512.716007]  [<ffffffff8165d8f0>] ? netlink_overrun+0x50/0x50
[  512.716007]  [<ffffffff8165e1d3>] ? netlink_insert+0x43/0xf0
[  512.716007]  [<ffffffff8165e221>] netlink_insert+0x91/0xf0
[  512.716007]  [<ffffffff81660550>] netlink_bind+0x210/0x260
[  512.716007]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  512.716007]  [<ffffffff810a5b10>] ? lock_release_non_nested+0xa0/0x340
[  512.716007]  [<ffffffff81616ce4>] SYSC_bind+0xa4/0xc0
[  512.716007]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  512.716007]  [<ffffffff81616fde>] SyS_bind+0xe/0x10
[  512.716007]  [<ffffffff816523f8>] compat_SyS_socketcall+0xa8/0x200
[  512.716007]  [<ffffffff817693f3>] sysenter_dispatch+0x7/0x1f
[  512.716007]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[  512.716007] Code: f0 ff 83 98 01 00 00 48 83 c4 08 5b 5d c3 66 66 66 66 2e 0f
1f 84 00 00 00 00 00 0f 1f 44 00 00 31 c0 8b 56 08 39 97 68 04 00 00 <55> 48 89
e5 74 0a 5d c3 0f 1f 84 00 00 00 00 00 48 8b 47 30 48
[  540.716005] NMI watchdog: BUG: soft lockup - CPU#7 stuck for 22s!
[bind-netlink:641]
[  540.716005] Modules linked in: tipc
[  540.716005] irq event stamp: 60371
[  540.716005] hardirqs last  enabled at (60370): [<ffffffff81767be0>]
restore_args+0x0/0x30
[  540.716005] hardirqs last disabled at (60371): [<ffffffff81767eaa>]
apic_timer_interrupt+0x6a/0x80
[  540.716005] softirqs last  enabled at (4280): [<ffffffff8161893f>]
lock_sock_nested+0x4f/0xc0
[  540.716005] softirqs last disabled at (4282): [<ffffffff8139d51a>]
lock_buckets+0x3a/0x80
[  540.716005] CPU: 7 PID: 641 Comm: bind-netlink Tainted: G        W    L
3.19.0-rc6+ #185
[  540.716005] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2007
[  540.716005] task: ffff880013f4c220 ti: ffff880014558000 task.ti: ffff880014558000
[  540.716005] RIP: 0010:[<ffffffff8165d900>]  [<ffffffff8165d900>]
netlink_compare+0x10/0x30
[  540.716005] RSP: 0018:ffff88001455bcf0  EFLAGS: 00000293
[  540.716005] RAX: 0000000000000000 RBX: ffffffff81767be0 RCX: 000000000bfbcdfb
[  540.716005] RDX: 00000000000002ae RSI: ffff88001455bdb8 RDI: ffff88001651b800
[  540.716005] RBP: ffff88001455bd48 R08: 00000000bef85eb8 R09: ffff880011bf1c68
[  540.716005] R10: 0000000000000004 R11: 0000000000000001 R12: ffff88001455bc68
[  540.716005] R13: 0000000000000046 R14: ffff880014558000 R15: ffff880013f4c220
[  540.716005] FS:  0000000000000000(0000) GS:ffff880017dc0000(0063)
knlGS:00000000f753e900
[  540.716005] CS:  0010 DS: 002b ES: 002b CR0: 000000008005003b
[  540.716005] CR2: 00000000f75f8b30 CR3: 0000000015abd000 CR4: 00000000000006e0
[  540.716005] Stack:
[  540.716005]  ffffffff8139e5ce ffffffff8139e540 000000028105d9c8 00c662f713caac00
[  540.716005]  ffff880013d15200 ffff88001455bd48 ffff880016500000 ffff880013caac00
[  540.716005]  0000000000000007 ffff880013d15200 ffff880011bf1e08 ffff88001455bda8
[  540.716005] Call Trace:
[  540.716005]  [<ffffffff8139e5ce>] ? rhashtable_lookup_compare+0x8e/0x120
[  540.716005]  [<ffffffff8139e540>] ? rht_deferred_worker+0xa0/0xa0
[  540.716005]  [<ffffffff8139e72f>] rhashtable_lookup_compare_insert+0x9f/0x110
[  540.716005]  [<ffffffff8139e6c5>] ? rhashtable_lookup_compare_insert+0x35/0x110
[  540.716005]  [<ffffffff8165d8f0>] ? netlink_overrun+0x50/0x50
[  540.716005]  [<ffffffff8165e1d3>] ? netlink_insert+0x43/0xf0
[  540.716005]  [<ffffffff8165e221>] netlink_insert+0x91/0xf0
[  540.716005]  [<ffffffff81660550>] netlink_bind+0x210/0x260
[  540.716005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  540.716005]  [<ffffffff810a5b10>] ? lock_release_non_nested+0xa0/0x340
[  540.716005]  [<ffffffff81616ce4>] SYSC_bind+0xa4/0xc0
[  540.716005]  [<ffffffff81184fc6>] ? might_fault+0x66/0xc0
[  540.716005]  [<ffffffff81616fde>] SyS_bind+0xe/0x10
[  540.716005]  [<ffffffff816523f8>] compat_SyS_socketcall+0xa8/0x200
[  540.716005]  [<ffffffff817693f3>] sysenter_dispatch+0x7/0x1f
[  540.716005]  [<ffffffff8139660e>] ? trace_hardirqs_on_thunk+0x3a/0x3f
[  540.716005] Code: f0 ff 83 98 01 00 00 48 83 c4 08 5b 5d c3 66 66 66 66 2e 0f
1f 84 00 00 00 00 00 0f 1f 44 00 00 31 c0 8b 56 08 39 97 68 04 00 00 <55> 48 89
e5 74 0a 5d c3 0f 1f 84 00 00 00 00 00 48 8b 47 30

Regards,
Ying

Re: [PATCH 0/6 v2 net-next] rhashtable fixes

[Thomas Graf]

On 02/05/15 at 05:14pm, Ying Xue wrote:
> On 02/05/2015 04:47 PM, Thomas Graf wrote:
> > On 02/05/15 at 10:32am, Ying Xue wrote:
> >> After I applied the sires, it sounds like panic doesn't occur any more. But soft
> >> lockup still happens although the frequency of its reproduction is much lower
> >> than before. Please take a look at its relevant log:
> > 
> > Thanks for testing and the report. I had run your bind_netlink test
> > overnight on a 4 CPU VM. Anything particular that might help trigger it?

Thanks. I will keep trying to reproduce. Can you try the following
patch in the meantime?

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 5919d63..1c65be2 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -593,7 +593,7 @@ void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
 
 	tbl = rht_dereference_rcu(ht->future_tbl, ht);
 	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	hash = head_hashfn(ht, tbl, obj);
+	hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
 
 	lock_buckets(tbl, old_tbl, hash);
 	__rhashtable_insert(ht, obj, tbl, hash);
@@ -835,7 +835,7 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
 	rcu_read_lock();
 	old_tbl = rht_dereference_rcu(ht->tbl, ht);
 	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	new_hash = head_hashfn(ht, new_tbl, obj);
+	new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
 
 	lock_buckets(new_tbl, old_tbl, new_hash);
 

Re: [PATCH 0/6 v2 net-next] rhashtable fixes

[David Miller]

From: Thomas Graf <tgraf@suug.ch>
Date: Thu,  5 Feb 2015 02:03:30 +0100

> This series fixes all remaining known issues with rhashtable that
> have been reported. In particular the race condition reported by
> Ying Xue.
> 
> ---
> Dave/Herbert: I'm posting this now as it fixes real issues. I'm
> fine with taking Herbert's rehash patches instead if they resolve
> all the reported issues as well.

Herbert, please tell me what you'd like me to do.

Re: [PATCH 0/6 v2 net-next] rhashtable fixes

[Ying Xue]

On 02/05/2015 06:19 PM, Thomas Graf wrote:
> On 02/05/15 at 05:14pm, Ying Xue wrote:
>> On 02/05/2015 04:47 PM, Thomas Graf wrote:
>>> On 02/05/15 at 10:32am, Ying Xue wrote:
>>>> After I applied the sires, it sounds like panic doesn't occur any more. But soft
>>>> lockup still happens although the frequency of its reproduction is much lower
>>>> than before. Please take a look at its relevant log:
>>>
>>> Thanks for testing and the report. I had run your bind_netlink test
>>> overnight on a 4 CPU VM. Anything particular that might help trigger it?
> 
> Thanks. I will keep trying to reproduce. Can you try the following
> patch in the meantime?
>

After I applied the below change on the latest net-next tree with the series
patches, panic happens during kernel boot stage as follows:

[    0.720502] smpboot: Total of 8 processors activated (54278.37 BogoMIPS)
[    0.728325] devtmpfs: initialized
[    0.729961] evm: security.selinux
[    0.730308] evm: security.SMACK64
[    0.730600] evm: security.capability
[    0.732507] RTC time:  2:26:37, date: 02/06/15
[    0.733240] NET: Registered protocol family 16
[    0.733729] BUG: unable to handle kernel paging request at ffff880042724fb0
[    0.734371] IP: [<ffffffff8139dd82>] __rhashtable_insert+0x22/0xb0
[    0.734936] PGD 2c50067 PUD 0
[    0.735254] Oops: 0000 [#1] SMP
[    0.735578] Modules linked in:
[    0.735870] CPU: 0 PID: 1 Comm: swapper/0 Not tainted 3.19.0-rc6+ #186
[    0.736000] Hardware name: Bochs Bochs, BIOS Bochs 01/01/2007
[    0.736000] task: ffff880016db8000 ti: ffff880016db4000 task.ti: ffff880016db4000
[    0.736000] RIP: 0010:[<ffffffff8139dd82>]  [<ffffffff8139dd82>]
__rhashtable_insert+0x22/0xb0
[    0.736000] RSP: 0000:ffff880016db7b78  EFLAGS: 00010286
[    0.736000] RAX: 0000000000000000 RBX: ffff880016500000 RCX: 000000000574ff73
[    0.736000] RDX: ffff880016ca5400 RSI: ffff88001651be08 RDI: ffff880016500000
[    0.736000] RBP: ffff880016db7bb8 R08: 0000000000000000 R09: 0000000000000001
[    0.736000] R10: 0000000000000000 R11: 0000000000000001 R12: ffff880016ca5400
[    0.736000] R13: ffff880016ca5400 R14: 000000000574ff73 R15: ffff880016ca5400
[    0.736000] FS:  0000000000000000(0000) GS:ffff880017c00000(0000)
knlGS:0000000000000000
[    0.736000] CS:  0010 DS: 0000 ES: 0000 CR0: 000000008005003b
[    0.736000] CR2: ffff880042724fb0 CR3: 0000000001c11000 CR4: 00000000000006f0
[    0.736000] Stack:
[    0.736000]  0574ff7300000000 ffff880016ca5400 ffff880016db7bb8 ffff880016500000
[    0.736000]  ffff88001651be08 ffff880016ca5400 000000000574ff73 ffff880016ca5400
[    0.736000]  ffff880016db7c18 ffffffff8139e841 ffffffff8139e775 ffff88001651b800
[    0.736000] Call Trace:
[    0.736000]  [<ffffffff8139e841>] rhashtable_lookup_compare_insert+0x101/0x110
[    0.736000]  [<ffffffff8139e775>] ? rhashtable_lookup_compare_insert+0x35/0x110
[    0.736000]  [<ffffffff8165d800>] ? jhash+0xe0/0x160
[    0.736000]  [<ffffffff8165e1b3>] ? netlink_insert+0x43/0xf0
[    0.736000]  [<ffffffff8165e201>] netlink_insert+0x91/0xf0
[    0.736000]  [<ffffffff81660a31>] __netlink_kernel_create+0x121/0x260
[    0.736000]  [<ffffffff816288cf>] ? register_pernet_subsys+0x1f/0x50
[    0.736000]  [<ffffffff8164136d>] rtnetlink_net_init+0x4d/0x70
[    0.736000]  [<ffffffff81641fe0>] ? rtnl_unlock+0x10/0x10
[    0.736000]  [<ffffffff8162848e>] ops_init+0x4e/0x150
[    0.736000]  [<ffffffff810a6afd>] ? trace_hardirqs_on+0xd/0x10
[    0.736000]  [<ffffffff81628793>] register_pernet_operations+0xf3/0x190
[    0.736000]  [<ffffffff810a6afd>] ? trace_hardirqs_on+0xd/0x10
[    0.736000]  [<ffffffff816288de>] register_pernet_subsys+0x2e/0x50
[    0.736000]  [<ffffffff81d89e03>] rtnetlink_init+0x10/0x16b
[    0.736000]  [<ffffffff81d8b0bf>] netlink_proto_init+0x194/0x1af
[    0.736000]  [<ffffffff8165d720>] ? __tcf_em_tree_match+0x160/0x160
[    0.736000]  [<ffffffff8139d380>] ? percpu_ida_alloc+0x3c0/0x3c0
[    0.736000]  [<ffffffff8139d3b0>] ? rht_grow_above_75+0x30/0x30
[    0.736000]  [<ffffffff81d8af2b>] ? tc_action_init+0x55/0x55
[    0.736000]  [<ffffffff810002d9>] do_one_initcall+0x89/0x1c0
[    0.736000]  [<ffffffff81d361a1>] kernel_init_freeable+0x1a3/0x23d
[    0.736000]  [<ffffffff81d358f2>] ? do_early_param+0x86/0x86
[    0.736000]  [<ffffffff8174fa10>] ? rest_init+0xd0/0xd0
[    0.736000]  [<ffffffff8174fa1e>] kernel_init+0xe/0xf0
[    0.736000]  [<ffffffff81766eec>] ret_from_fork+0x7c/0xb0
[    0.736000]  [<ffffffff8174fa10>] ? rest_init+0xd0/0xd0
[    0.736000] Code: 2e 0f 1f 84 00 00 00 00 00 55 48 89 e5 48 83 ec 40 4c 89 75
f0 41 89 ce 48 89 5d d8 4c 89 65 e0 4c 89 6d e8 49 89 d4 4c 89 7d f8 <4a> 8b 54
f2 18 48 89 fb 49 89 f5 4c 89 e7 89 ce 41 89 cf 48 89
[    0.736000] RIP  [<ffffffff8139dd82>] __rhashtable_insert+0x22/0xb0
[    0.736000]  RSP <ffff880016db7b78>
[    0.736000] CR2: ffff880042724fb0
[    0.736000] ---[ end trace 0747bcdb7a563e55 ]---
[    0.736000] Kernel panic - not syncing: Fatal exception in interrupt
[    0.736000] ---[ end Kernel panic - not syncing: Fatal exception in interrupt

Regards,
Ying

> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index 5919d63..1c65be2 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -593,7 +593,7 @@ void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
>  
>  	tbl = rht_dereference_rcu(ht->future_tbl, ht);
>  	old_tbl = rht_dereference_rcu(ht->tbl, ht);
> -	hash = head_hashfn(ht, tbl, obj);
> +	hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
>  
>  	lock_buckets(tbl, old_tbl, hash);
>  	__rhashtable_insert(ht, obj, tbl, hash);
> @@ -835,7 +835,7 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
>  	rcu_read_lock();
>  	old_tbl = rht_dereference_rcu(ht->tbl, ht);
>  	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
> -	new_hash = head_hashfn(ht, new_tbl, obj);
> +	new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
>  
>  	lock_buckets(new_tbl, old_tbl, new_hash);
>  
> 
> 
> 

Re: [PATCH 0/6 v2 net-next] rhashtable fixes

[Thomas Graf]

On 02/06/15 at 10:36am, Ying Xue wrote:
> After I applied the below change on the latest net-next tree with the series
> patches, panic happens during kernel boot stage as follows:

Sorry about that. I must have booted the wrong kernel. On the positive
side, I was able to reproduce the original race today. The key was to
use 8 instead of 4 CPUs in the VM. I'm testing with the fixed build
right now.

[PATCH net-next] rhashtable: Fix remove logic to avoid cross references between buckets

[Thomas Graf]

The remove logic properly searched the remaining chain for a matching
entry with an identical hash but it did this while searching from both
the old and new table. Instead in order to not leave stale references
behind we need to:

 1. When growing and searching from the new table:
    Search remaining chain for entry with same hash to avoid having
    the new table directly point to a entry with a different hash.

 2. When shrinking and searching from the old table:
    Check if the element after the removed would create a cross
    reference and avoid it if so.

These bugs were present from the beginning in nft_hash.

Also, both insert functions calculated the hash based on the mask of
the new table. This worked while growing. Wwhile shrinking, the mask
of the inew table is smaller than the mask of the old table. This lead
to a bit not being taken into account when selecting the bucket lock
and thus caused the wrong bucket to be locked eventually.

Fixes: 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")
Fixes: 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
Reported-by: Ying Xue <ying.xue@windriver.com>
Signed-off-by: Thomas Graf <tgraf@suug.ch>
---
 lib/rhashtable.c | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 5919d63..e96fc00 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -552,8 +552,10 @@ static void rhashtable_wakeup_worker(struct rhashtable *ht)
 static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
 				struct bucket_table *tbl, u32 hash)
 {
-	struct rhash_head *head = rht_dereference_bucket(tbl->buckets[hash],
-							 tbl, hash);
+	struct rhash_head *head;
+
+	hash = rht_bucket_index(tbl, hash);
+	head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
 
 	ASSERT_BUCKET_LOCK(ht, tbl, hash);
 
@@ -593,7 +595,7 @@ void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
 
 	tbl = rht_dereference_rcu(ht->future_tbl, ht);
 	old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	hash = head_hashfn(ht, tbl, obj);
+	hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
 
 	lock_buckets(tbl, old_tbl, hash);
 	__rhashtable_insert(ht, obj, tbl, hash);
@@ -627,8 +629,8 @@ bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
 	bool ret = false;
 
 	rcu_read_lock();
-	tbl = old_tbl = rht_dereference_rcu(ht->tbl, ht);
-	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
+	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);
@@ -643,15 +645,19 @@ restart:
 
 		ASSERT_BUCKET_LOCK(ht, tbl, hash);
 
-		if (unlikely(new_tbl != tbl)) {
-			rht_for_each_continue(he2, he->next, 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;
 				}
 			}
 
-			INIT_RHT_NULLS_HEAD(*pprev, ht, hash);
+			rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash));
 		} else {
 			rcu_assign_pointer(*pprev, obj->next);
 		}
@@ -666,8 +672,8 @@ found:
 	 * resizing. Thus traversing both is fine and the added cost is
 	 * very rare.
 	 */
-	if (tbl != new_tbl) {
-		tbl = new_tbl;
+	if (tbl != old_tbl) {
+		tbl = old_tbl;
 		goto restart;
 	}
 
@@ -835,7 +841,7 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
 	rcu_read_lock();
 	old_tbl = rht_dereference_rcu(ht->tbl, ht);
 	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
-	new_hash = head_hashfn(ht, new_tbl, obj);
+	new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
 
 	lock_buckets(new_tbl, old_tbl, new_hash);
 
-- 
1.9.3

Re: [PATCH 0/6 v2 net-next] rhashtable fixes

[David Miller]

From: Thomas Graf <tgraf@suug.ch>
Date: Thu,  5 Feb 2015 02:03:30 +0100

> This series fixes all remaining known issues with rhashtable that
> have been reported. In particular the race condition reported by
> Ying Xue.
> 
> ---
> Dave/Herbert: I'm posting this now as it fixes real issues. I'm
> fine with taking Herbert's rehash patches instead if they resolve
> all the reported issues as well.
> 
> v2:
>  - Rebased on top of Herbert Xu's iterator code
>  - Fixed last remaining race that remained. Special thanks
>    to Daniel Borkmann for assistance while debugging.

Since this supposedly fixes crashes on bootup for some people
I'm applying this series now.

Herbert, I apologize in advance if this makes your work more
difficult but I asked you yesterday what you wanted me to
do with this series...

Thanks.

Re: [PATCH net-next] rhashtable: Fix remove logic to avoid cross references between buckets

[David Miller]

From: Thomas Graf <tgraf@suug.ch>
Date: Fri, 6 Feb 2015 16:08:43 +0000

> The remove logic properly searched the remaining chain for a matching
> entry with an identical hash but it did this while searching from both
> the old and new table. Instead in order to not leave stale references
> behind we need to:
> 
>  1. When growing and searching from the new table:
>     Search remaining chain for entry with same hash to avoid having
>     the new table directly point to a entry with a different hash.
> 
>  2. When shrinking and searching from the old table:
>     Check if the element after the removed would create a cross
>     reference and avoid it if so.
> 
> These bugs were present from the beginning in nft_hash.
> 
> Also, both insert functions calculated the hash based on the mask of
> the new table. This worked while growing. Wwhile shrinking, the mask
> of the inew table is smaller than the mask of the old table. This lead
> to a bit not being taken into account when selecting the bucket lock
> and thus caused the wrong bucket to be locked eventually.
> 
> Fixes: 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")
> Fixes: 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
> Reported-by: Ying Xue <ying.xue@windriver.com>
> Signed-off-by: Thomas Graf <tgraf@suug.ch>

Applied.

Re: [PATCH net-next] rhashtable: Fix remove logic to avoid cross references between buckets

[Ying Xue]

On 02/07/2015 12:08 AM, Thomas Graf wrote:
> The remove logic properly searched the remaining chain for a matching
> entry with an identical hash but it did this while searching from both
> the old and new table. Instead in order to not leave stale references
> behind we need to:
> 
>  1. When growing and searching from the new table:
>     Search remaining chain for entry with same hash to avoid having
>     the new table directly point to a entry with a different hash.
> 
>  2. When shrinking and searching from the old table:
>     Check if the element after the removed would create a cross
>     reference and avoid it if so.
> 
> These bugs were present from the beginning in nft_hash.
> 
> Also, both insert functions calculated the hash based on the mask of
> the new table. This worked while growing. Wwhile shrinking, the mask
> of the inew table is smaller than the mask of the old table. This lead
> to a bit not being taken into account when selecting the bucket lock
> and thus caused the wrong bucket to be locked eventually.
> 

Good Job!
My previously reported issue has been gone, thanks for your hard work!

Regards,
Ying

> Fixes: 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")
> Fixes: 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
> Reported-by: Ying Xue <ying.xue@windriver.com>
> Signed-off-by: Thomas Graf <tgraf@suug.ch>
> ---
>  lib/rhashtable.c | 28 +++++++++++++++++-----------
>  1 file changed, 17 insertions(+), 11 deletions(-)
> 
> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index 5919d63..e96fc00 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -552,8 +552,10 @@ static void rhashtable_wakeup_worker(struct rhashtable *ht)
>  static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
>  				struct bucket_table *tbl, u32 hash)
>  {
> -	struct rhash_head *head = rht_dereference_bucket(tbl->buckets[hash],
> -							 tbl, hash);
> +	struct rhash_head *head;
> +
> +	hash = rht_bucket_index(tbl, hash);
> +	head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
>  
>  	ASSERT_BUCKET_LOCK(ht, tbl, hash);
>  
> @@ -593,7 +595,7 @@ void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
>  
>  	tbl = rht_dereference_rcu(ht->future_tbl, ht);
>  	old_tbl = rht_dereference_rcu(ht->tbl, ht);
> -	hash = head_hashfn(ht, tbl, obj);
> +	hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
>  
>  	lock_buckets(tbl, old_tbl, hash);
>  	__rhashtable_insert(ht, obj, tbl, hash);
> @@ -627,8 +629,8 @@ bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
>  	bool ret = false;
>  
>  	rcu_read_lock();
> -	tbl = old_tbl = rht_dereference_rcu(ht->tbl, ht);
> -	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
> +	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);
> @@ -643,15 +645,19 @@ restart:
>  
>  		ASSERT_BUCKET_LOCK(ht, tbl, hash);
>  
> -		if (unlikely(new_tbl != tbl)) {
> -			rht_for_each_continue(he2, he->next, 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;
>  				}
>  			}
>  
> -			INIT_RHT_NULLS_HEAD(*pprev, ht, hash);
> +			rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash));
>  		} else {
>  			rcu_assign_pointer(*pprev, obj->next);
>  		}
> @@ -666,8 +672,8 @@ found:
>  	 * resizing. Thus traversing both is fine and the added cost is
>  	 * very rare.
>  	 */
> -	if (tbl != new_tbl) {
> -		tbl = new_tbl;
> +	if (tbl != old_tbl) {
> +		tbl = old_tbl;
>  		goto restart;
>  	}
>  
> @@ -835,7 +841,7 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
>  	rcu_read_lock();
>  	old_tbl = rht_dereference_rcu(ht->tbl, ht);
>  	new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
> -	new_hash = head_hashfn(ht, new_tbl, obj);
> +	new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
>  
>  	lock_buckets(new_tbl, old_tbl, new_hash);
>  
> 

RE: [PATCH 2/6] rhashtable: Use a single bucket lock for sibling buckets

[David Laight]

From: Thomas Graf
> Sent: 05 February 2015 01:04
> rhashtable currently allows to use a bucket lock per bucket. This
> requires multiple levels of complicated nested locking because when
> resizing, a single bucket of the smaller table will map to two
> buckets in the larger table. So far rhashtable has explicitly locked
> both buckets in the larger table.

> By excluding the highest bit of the hash from the bucket lock map and
> thus only allowing locks to buckets in a ratio of 1:2, the locking

Surely you mean 1:2^n ??

> can be simplified a lot without losing the benefits of multiple locks.
> Larger tables which benefit from multiple locks will not have a single
> lock per bucket anyway.

I'd presume that for a very large table the number of locks required
is related to the number of cpus rather than the table size itself.
Once the hash chains are short the lock is less likely to be contended
anyway. My brain can't think through the cache implications though.

This makes me think that you never really need to increase the number
of locks (which is probably quite tricky), and definitely don't need
to reduce the number of locks (probably harder).
This would mean that the table can't get smaller than the number of locks.
This in itself isn't really an issue.

	David