[PATCH 0/2] rhashtable_walk fixes

[PATCH 0/2] rhashtable_walk fixes

[NeilBrown]

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

[PATCH 1/2] rhashtable: fix insertion of in rhltable when duplicate found.

[NeilBrown]

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 <neilb@suse.com>
---
 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);

[PATCH 2/2] rhashtable: improve rhashtable_walk stability when stop/start used.

[NeilBrown]

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 <neilb@suse.com>
---
 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();
 }

Re: [PATCH 1/2] rhashtable: fix insertion of in rhltable when duplicate found.

[Herbert Xu]

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 <neilb@suse.com>

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 <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH 2/2] rhashtable: improve rhashtable_walk stability when stop/start used.

[Herbert Xu]

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 <neilb@suse.com>

Very nice!

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

Re: [PATCH 0/2] rhashtable_walk fixes

[David Miller]

From: NeilBrown <neilb@suse.com>
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.

Re: [PATCH 0/2] rhashtable_walk fixes

[NeilBrown]

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

On Fri, Mar 30 2018, David Miller wrote:

> From: NeilBrown <neilb@suse.com>
> 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.

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 832 bytes --]

Re: [PATCH 0/2] rhashtable_walk fixes

[David Miller]

From: NeilBrown <neilb@suse.com>
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.