[PATCH 0/2] rhashtable_walk fixes

These two patches apply on top of my previous "rhashtable: reset iter
when rhashtable_walk_start sees new table" patch.

The first fixes a bug that I found in rhltable_insert().

The second is an alternate to my "rhashtable: allow a walk of the hash
table without missing object."
This version doesn't require an API change and should be reliable for
rhltables too (my first version didn't handle these correctly).

Thanks,
NeilBrown


---

NeilBrown (2):
      rhashtable: fix insertion of in rhltable when duplicate found.
      rhashtable: improve rhashtable_walk stability when stop/start used.


 include/linux/rhashtable.h |    4 +++-
 lib/rhashtable.c           |   48 ++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 47 insertions(+), 5 deletions(-)

--
Signature

When rhltable_insert() finds an entry with the same key,
it splices the new entry at the start of a list of entries with the
same key.
It stores the address of the new object in *pprev, but in general this
is *not* the location where the match was found (though in a common
case where the hash chain has one element, it will be).
To fix this, pprev should be updated every time we find an object that
doesn't match.

This patch changes the behaviour for non-slow insertion in that now
insertion happens at the end of a chain rather than at the head.
I don't think this is an important change.

Signed-off-by: NeilBrown <redacted>
---
 include/linux/rhashtable.h |    4 +++-
 lib/rhashtable.c           |    4 +++-
 2 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index c9df2527e0cd..668a21f04b09 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h

@@ -766,8 +766,10 @@ static inline void *__rhashtable_insert_fast(
 		if (!key ||
 		    (params.obj_cmpfn ?
 		     params.obj_cmpfn(&arg, rht_obj(ht, head)) :
-		     rhashtable_compare(&arg, rht_obj(ht, head))))
+		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
+			pprev = &head->next;
 			continue;
+		}
 
 		data = rht_obj(ht, head);
 

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 394de09a162c..72e56f89e20c 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c

@@ -506,8 +506,10 @@ static void *rhashtable_lookup_one(struct rhashtable *ht,
 		if (!key ||
 		    (ht->p.obj_cmpfn ?
 		     ht->p.obj_cmpfn(&arg, rht_obj(ht, head)) :
-		     rhashtable_compare(&arg, rht_obj(ht, head))))
+		     rhashtable_compare(&arg, rht_obj(ht, head)))) {
+			pprev = &head->next;
 			continue;
+		}
 
 		if (!ht->rhlist)
 			return rht_obj(ht, head);

When a walk of an rhashtable is interrupted with rhastable_walk_stop()
and then rhashtable_walk_start(), the location to restart from is based
on a 'skip' count in the current hash chain, and this can be incorrect
if insertions or deletions have happened.  This does not happen when
the walk is not stopped and started as iter->p is a placeholder which
is safe to use while holding the RCU read lock.

In rhashtable_walk_start() we can revalidate that 'p' is still in the
same hash chain.  If it isn't then the current method is still used.

With this patch, if a rhashtable walker ensures that the current
object remains in the table over a stop/start period (possibly by
elevating the reference count if that is sufficient), it can be sure
that a walk will not miss objects that were in the hashtable for the
whole time of the walk.

rhashtable_walk_start() may not find the object even though it is
still in the hashtable if a rehash has moved it to a new table.  In
this case it will (eventually) get -EAGAIN and will need to proceed
through the whole table again to be sure to see everything at least
once.

Signed-off-by: NeilBrown <redacted>
---
 lib/rhashtable.c |   44 +++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 41 insertions(+), 3 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 72e56f89e20c..46cf0cc6cefc 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c

@@ -725,6 +725,7 @@ int rhashtable_walk_start_check(struct rhashtable_iter *iter)
 	__acquires(RCU)
 {
 	struct rhashtable *ht = iter->ht;
+	bool rhlist = ht->rhlist;
 
 	rcu_read_lock();
 

@@ -733,13 +734,52 @@ int rhashtable_walk_start_check(struct rhashtable_iter *iter)
 		list_del(&iter->walker.list);
 	spin_unlock(&ht->lock);
 
-	if (!iter->walker.tbl && !iter->end_of_table) {
+	if (iter->end_of_table)
+		return 0;
+	if (!iter->walker.tbl) {
 		iter->walker.tbl = rht_dereference_rcu(ht->tbl, ht);
 		iter->slot = 0;
 		iter->skip = 0;
 		return -EAGAIN;
 	}
 
+	if (iter->p && !rhlist) {
+		/*
+		 * We need to validate that 'p' is still in the table, and
+		 * if so, update 'skip'
+		 */
+		struct rhash_head *p;
+		int skip = 0;
+		rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
+			skip++;
+			if (p == iter->p) {
+				iter->skip = skip;
+				goto found;
+			}
+		}
+		iter->p = NULL;
+	} else if (iter->p && rhlist) {
+		/* Need to validate that 'list' is still in the table, and
+		 * if so, update 'skip' and 'p'.
+		 */
+		struct rhash_head *p;
+		struct rhlist_head *list;
+		int skip = 0;
+		rht_for_each_rcu(p, iter->walker.tbl, iter->slot) {
+			for (list = container_of(p, struct rhlist_head, rhead);
+			     list;
+			     list = rcu_dereference(list->next)) {
+				skip++;
+				if (list == iter->list) {
+					iter->p = p;
+					skip = skip;
+					goto found;
+				}
+			}
+		}
+		iter->p = NULL;
+	}
+found:
 	return 0;
 }
 EXPORT_SYMBOL_GPL(rhashtable_walk_start_check);

@@ -915,8 +955,6 @@ void rhashtable_walk_stop(struct rhashtable_iter *iter)
 		iter->walker.tbl = NULL;
 	spin_unlock(&ht->lock);
 
-	iter->p = NULL;
-
 out:
 	rcu_read_unlock();
 }

On Thu, Mar 29, 2018 at 12:19:09PM +1100, NeilBrown wrote:

When rhltable_insert() finds an entry with the same key,
it splices the new entry at the start of a list of entries with the
same key.
It stores the address of the new object in *pprev, but in general this
is *not* the location where the match was found (though in a common
case where the hash chain has one element, it will be).
To fix this, pprev should be updated every time we find an object that
doesn't match.

This patch changes the behaviour for non-slow insertion in that now
insertion happens at the end of a chain rather than at the head.
I don't think this is an important change.

Signed-off-by: NeilBrown <redacted>

Thanks.  But Paul Blakey beat you to it :)

https://git.kernel.org/pub/scm/linux/kernel/git/davem/net-next.git/commit/?id=d3dcf8eb615537526bd42ff27a081d46d337816e
-- 
Email: Herbert Xu [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

On Thu, Mar 29, 2018 at 12:19:10PM +1100, NeilBrown wrote:

When a walk of an rhashtable is interrupted with rhastable_walk_stop()
and then rhashtable_walk_start(), the location to restart from is based
on a 'skip' count in the current hash chain, and this can be incorrect
if insertions or deletions have happened.  This does not happen when
the walk is not stopped and started as iter->p is a placeholder which
is safe to use while holding the RCU read lock.

In rhashtable_walk_start() we can revalidate that 'p' is still in the
same hash chain.  If it isn't then the current method is still used.

With this patch, if a rhashtable walker ensures that the current
object remains in the table over a stop/start period (possibly by
elevating the reference count if that is sufficient), it can be sure
that a walk will not miss objects that were in the hashtable for the
whole time of the walk.

rhashtable_walk_start() may not find the object even though it is
still in the hashtable if a rehash has moved it to a new table.  In
this case it will (eventually) get -EAGAIN and will need to proceed
through the whole table again to be sure to see everything at least
once.

Signed-off-by: NeilBrown <redacted>

Very nice!

Acked-by: Herbert Xu <herbert@gondor.apana.org.au>
-- 
Email: Herbert Xu [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

From: NeilBrown <redacted>
Date: Thu, 29 Mar 2018 12:19:09 +1100

These two patches apply on top of my previous "rhashtable: reset iter
when rhashtable_walk_start sees new table" patch.

The first fixes a bug that I found in rhltable_insert().

The second is an alternate to my "rhashtable: allow a walk of the hash
table without missing object."
This version doesn't require an API change and should be reliable for
rhltables too (my first version didn't handle these correctly).

Neil, please don't mix and match patches.

Also when you need to change a patch in a series, please post the entire
new series not just the patch that changes.

Patch #1 in this series is unnecessary.  As Herbert explained this has
been fixed already.

So please repost freshly the patches that are relevant and you want me
to consider for inclusion.  Also be explicit and clear about which of
my two networking trees you are targetting these changes.

Thank you.

On Fri, Mar 30 2018, David Miller wrote:

From: NeilBrown <redacted>
Date: Thu, 29 Mar 2018 12:19:09 +1100

quoted

These two patches apply on top of my previous "rhashtable: reset iter
when rhashtable_walk_start sees new table" patch.

The first fixes a bug that I found in rhltable_insert().

The second is an alternate to my "rhashtable: allow a walk of the hash
table without missing object."
This version doesn't require an API change and should be reliable for
rhltables too (my first version didn't handle these correctly).

Neil, please don't mix and match patches.

Also when you need to change a patch in a series, please post the entire
new series not just the patch that changes.

Patch #1 in this series is unnecessary.  As Herbert explained this has
been fixed already.

So please repost freshly the patches that are relevant and you want me
to consider for inclusion.  Also be explicit and clear about which of
my two networking trees you are targetting these changes.

Hi Dave,
 I'm sorry if I've caused some confusion, but I didn't think that I was
 submitting patches to you and know nothing about your two trees.
 I was submitting patches to Thomas and Herbert, the registered
 maintainers of rhashtable.  I assumed they would review, respond, and
 take responsibility for getting them upstream, if that's what they
 decided, based on whatever arrangements they have in place.

 If it is appropriate I can resend all of my patches that receive an
 Ack as a coherent series, and send this to you nominating a particular
 tree, but I'm unlikely to do that unless asked and told which tree to
 nominate.

Thanks,
NeilBrown

From: NeilBrown <redacted>
Date: Tue, 03 Apr 2018 12:23:40 +1000

 I'm sorry if I've caused some confusion, but I didn't think that I was
 submitting patches to you and know nothing about your two trees.
 I was submitting patches to Thomas and Herbert, the registered
 maintainers of rhashtable.  I assumed they would review, respond, and
 take responsibility for getting them upstream, if that's what they
 decided, based on whatever arrangements they have in place.

 If it is appropriate I can resend all of my patches that receive an
 Ack as a coherent series, and send this to you nominating a particular
 tree, but I'm unlikely to do that unless asked and told which tree to
 nominate.

Herbert and Thomas generally review rhashtable patches, but rhashtable
itself is generally maintained in the networking tree(s).  So once
they review and ACK it, I would apply it.