Skip to contentSkip to conversation

rhashtable fixes

PATCH In review Thomas Graf 4 participants 19 messages Feb 5, 2015 – Feb 26, 2015

Subsystems (4)
lore
Share & tools
lore

Thomas Graf

author maintainer
#0 lore raw

v2 cover rhashtable fixes

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(-)
author maintainer
#1 lore raw

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

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")
---
 lib/rhashtable.c | 8 +-------
 1 file changed, 1 insertion(+), 7 deletions(-)
lib/rhashtable.c +1 -7
index 0579191..71fd0dd 100644
@@ -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,
Signature · 1 line
1.9.3
author maintainer
#2 lore raw

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

In reply to 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.

---
 lib/rhashtable.c | 170 ++++++++++++++++++++++---------------------------------
 1 file changed, 69 insertions(+), 101 deletions(-)
lib/rhashtable.c +69 -101
index 71fd0dd..cea4244 100644
@@ -1,7 +1,7 @@
 /*
  * Resizable, Scalable, Concurrent Hash Table
  *
- * Copyright (c) 2014 Thomas Graf <[email protected]>
+ * Copyright (c) 2014-2015 Thomas Graf <[email protected]>
  * Copyright (c) 2008-2014 Patrick McHardy <[email protected]>
  *
  * 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;
Signature · 1 line
1.9.3
#3 lore raw

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

From: Thomas Graf

Quoted 9 lines

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 ??

Quoted 3 lines

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

author maintainer
#4 lore raw

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

In reply to 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")
---
 lib/rhashtable.c | 2 ++
 1 file changed, 2 insertions(+)
lib/rhashtable.c +2 -0
index cea4244..fd1033d 100644
@@ -392,6 +392,8 @@ int rhashtable_expand(struct rhashtable *ht)
 		}
 	}
 
+	synchronize_rcu();
+
 	bucket_table_free(old_tbl);
 	return 0;
 }
Signature · 1 line
1.9.3
author maintainer
#5 lore raw

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

In reply to Thomas Graf

This simplifies debugging of locking violations if compiled with CONFIG_PROVE_LOCKING.

---
 lib/rhashtable.c | 99 ++++++++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 75 insertions(+), 24 deletions(-)
lib/rhashtable.c +75 -24
index fd1033d..c2c3949 100644
@@ -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;
Signature · 1 line
1.9.3
author maintainer
#6 lore raw

PATCH v2 5/6 rhashtable: Add more lock verification

In reply to Thomas Graf

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

---
 lib/rhashtable.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)
lib/rhashtable.c +8 -2
index c2c3949..ef0816b 100644
@@ -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;
Signature · 1 line
1.9.3
author maintainer
#7 lore raw

PATCH v2 6/6 rhashtable: Avoid bucket cross reference after removal

In reply to 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.

Fixes 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
---
 lib/rhashtable.c | 26 +++++++++++++++++---------
 1 file changed, 17 insertions(+), 9 deletions(-)
lib/rhashtable.c +17 -9
index ef0816b..5919d63 100644
@@ -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;
 	}
Signature · 1 line
1.9.3
#8 lore raw
In reply to Thomas Graf

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

Quoted 27 lines · 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(-)
author maintainer
#9 lore raw
Quoted 3 lines · Ying Xue

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?

#10 lore raw
Quoted 9 lines · Thomas Graf
Quoted 3 lines · Ying Xue

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

author maintainer
#11 lore raw
Quoted 8 lines · Ying Xue
Quoted 7 lines · Thomas Graf
Quoted 3 lines · Ying Xue

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?

lib/rhashtable.c +2 -2
index 5919d63..1c65be2 100644
@@ -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);
 
#12 lore raw
Quoted 7 lines · Thomas Graf
Quoted 6 lines · Ying Xue
Quoted 5 lines · Thomas Graf
Quoted 3 lines · Ying Xue

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:

Quoted 6 lines
Quoted 2 lines
Quoted 2 lines

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

Quoted 25 lines
lib/rhashtable.c +2 -2
index 5919d63..1c65be2 100644
@@ -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);
 
author maintainer
#13 lore raw
Quoted 2 lines · Ying Xue

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.

author maintainer
#14 lore raw

PATCH 1/1 rhashtable: Fix remove logic to avoid cross references between buckets

In reply to Ying Xue

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")
---
 lib/rhashtable.c | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)
lib/rhashtable.c +17 -11
index 5919d63..e96fc00 100644
@@ -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);
 
Signature · 1 line
1.9.3
maintainer Applied
#15 lore raw

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

From: Thomas Graf <[email protected]>
Date: Fri, 6 Feb 2015 16:08:43 +0000

Quoted 21 lines

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.

Quoted 4 lines
Fixes 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")
Fixes 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")

Applied.

#16 lore raw

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

In reply to Thomas Graf
Quoted 13 lines · 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.

Quoted 8 lines

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

Quoted 89 lines
Fixes 7e1e77636e36 ("lib: Resizable, Scalable, Concurrent Hash Table")
Fixes 97defe1ecf86 ("rhashtable: Per bucket locks & deferred expansion/shrinking")
---
 lib/rhashtable.c | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)
lib/rhashtable.c +17 -11
index 5919d63..e96fc00 100644
@@ -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);
 
maintainer
#17 lore raw
In reply to Thomas Graf

From: Thomas Graf <[email protected]>
Date: Thu, 5 Feb 2015 02:03:30 +0100

Quoted 8 lines

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.

maintainer
#18 lore raw
In reply to Thomas Graf

From: Thomas Graf <[email protected]>
Date: Thu, 5 Feb 2015 02:03:30 +0100

Quoted 9 lines

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.

Quoted 4 lines

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.