[v3] rhashtable: detect when object movement between tables might have invalidated a lookup
diff mbox series

Message ID 87pnuno479.fsf@notabene.neil.brown.name
State Accepted
Commit 82208d0d54ab85d8fedbb1c9a1960bd401a4ca1a
Headers show
Series
  • [v3] rhashtable: detect when object movement between tables might have invalidated a lookup
Related show

Commit Message

NeilBrown Nov. 29, 2018, 11:26 p.m. UTC
Some users of rhashtables might need to move an object from one table
to another -  this appears to be the reason for the incomplete usage
of NULLS markers.

To support these, we store a unique NULLS_MARKER at the end of
each chain, and when a search fails to find a match, we check
if the NULLS marker found was the expected one.  If not, the search
may not have examined all objects in the target bucket, so it is
repeated.

The unique NULLS_MARKER is derived from the address of the
head of the chain.  As this cannot be derived at load-time the
static rhnull in rht_bucket_nested() needs to be initialised
at run time.

Any caller of a lookup function must still be prepared for the
possibility that the object returned is in a different table - it
might have been there for some time.

Note that this does NOT provide support for other uses of
NULLS_MARKERs such as allocating with SLAB_TYPESAFE_BY_RCU or changing
the key of an object and re-inserting it in the same table.
These could only be done safely if new objects were inserted
at the *start* of a hash chain, and that is not currently the case.

Signed-off-by: NeilBrown <neilb@suse.com>
---

This version has an added comment to explain the ">>1" in
RHT_NULLS_MARKER().

Thanks,
NeilBrown

 include/linux/rhashtable.h | 34 ++++++++++++++++++++++++++--------
 lib/rhashtable.c           |  8 +++++---
 2 files changed, 31 insertions(+), 11 deletions(-)

Comments

Herbert Xu Dec. 1, 2018, 8:47 a.m. UTC | #1
On Fri, Nov 30, 2018 at 10:26:50AM +1100, NeilBrown wrote:
>
> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index 30526afa8343..852ffa5160f1 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -1179,8 +1179,7 @@ struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl,
>  					    unsigned int hash)
>  {
>  	const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
> -	static struct rhash_head __rcu *rhnull =
> -		(struct rhash_head __rcu *)NULLS_MARKER(0);
> +	static struct rhash_head __rcu *rhnull;
>  	unsigned int index = hash & ((1 << tbl->nest) - 1);
>  	unsigned int size = tbl->size >> tbl->nest;
>  	unsigned int subhash = hash;
> @@ -1198,8 +1197,11 @@ struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl,
>  		subhash >>= shift;
>  	}
>  
> -	if (!ntbl)
> +	if (!ntbl) {
> +		if (!rhnull)
> +			INIT_RHT_NULLS_HEAD(rhnull);
>  		return &rhnull;
> +	}

I think you missed my earlier reply beause of bouncing emails.

I think this is unnecessary because

	RHT_NULLS_MARKER(RHT_NULLS_MARKER(0)) = RHT_NULLS_MARKER(0)

Thanks,
NeilBrown Dec. 2, 2018, 10:20 p.m. UTC | #2
On Sat, Dec 01 2018, Herbert Xu wrote:

> On Fri, Nov 30, 2018 at 10:26:50AM +1100, NeilBrown wrote:
>>
>> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
>> index 30526afa8343..852ffa5160f1 100644
>> --- a/lib/rhashtable.c
>> +++ b/lib/rhashtable.c
>> @@ -1179,8 +1179,7 @@ struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl,
>>  					    unsigned int hash)
>>  {
>>  	const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
>> -	static struct rhash_head __rcu *rhnull =
>> -		(struct rhash_head __rcu *)NULLS_MARKER(0);
>> +	static struct rhash_head __rcu *rhnull;
>>  	unsigned int index = hash & ((1 << tbl->nest) - 1);
>>  	unsigned int size = tbl->size >> tbl->nest;
>>  	unsigned int subhash = hash;
>> @@ -1198,8 +1197,11 @@ struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl,
>>  		subhash >>= shift;
>>  	}
>>  
>> -	if (!ntbl)
>> +	if (!ntbl) {
>> +		if (!rhnull)
>> +			INIT_RHT_NULLS_HEAD(rhnull);
>>  		return &rhnull;
>> +	}
>
> I think you missed my earlier reply beause of bouncing emails.

Yeah, sorry about that.  I should have looked through an lkml archive
once I realized that was happening - I have now.

>
> I think this is unnecessary because
>
> 	RHT_NULLS_MARKER(RHT_NULLS_MARKER(0)) = RHT_NULLS_MARKER(0)
>

I don't understand how this is relevant.

I think you are saying that when rht_bucket_nested() finds that the
target page hasn't been allocated, it should return a pointer to a
static variable which contains RHT_NULLS_MARKER(0)

 static struct rhash_head *rhnull = RHT_NULLS_MARKER(0);

Then in __rhashtable_lookup(),
	head = rht_bucket(tbl, hash);

would result in 'head' having the value '&rhnull'.

Then
		rht_for_each_rcu_continue(he, *head, tbl, hash) {

would result in 'he' having the value RHT_NULLS_MARKER(0)

Then
	} while (he != RHT_NULLS_MARKER(head));

will compare RHT_NULLS_MARKER(0) with RHT_NULLS_MARKED(&rhnull)
and they will be different, so it will loop indefinitely.

With respect to the shifting, you wrote:

> The top-bit is most likely to be fixed and offer no real value.

While this might be likely, it is not certain, so not relevant.
On a 32bit machine with more than 2GB of physical memory, some memory
addresses will have 0 in the msb, some will have 1.
It is possible (however unlikely) that two hash buckets in different
tables will have the same address except for the msb.  If we ignore the
msb, we might incorrectly determine that we have reached the end of the
chain from the first bucket, whereas we actually reached the end of the
chain from the second bucket.

Thanks,
NeilBrown
Herbert Xu Dec. 3, 2018, 1:44 a.m. UTC | #3
On Mon, Dec 03, 2018 at 09:20:23AM +1100, NeilBrown wrote:
>
> I don't understand how this is relevant.

Thanks for the explanation, I had missed the double pointer part.
With that, I'm happy with this patch as it stands:

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

Cheers,
David Miller Dec. 3, 2018, 11:32 p.m. UTC | #4
From: NeilBrown <neilb@suse.com>
Date: Fri, 30 Nov 2018 10:26:50 +1100

> 
> Some users of rhashtables might need to move an object from one table
> to another -  this appears to be the reason for the incomplete usage
> of NULLS markers.
> 
> To support these, we store a unique NULLS_MARKER at the end of
> each chain, and when a search fails to find a match, we check
> if the NULLS marker found was the expected one.  If not, the search
> may not have examined all objects in the target bucket, so it is
> repeated.
> 
> The unique NULLS_MARKER is derived from the address of the
> head of the chain.  As this cannot be derived at load-time the
> static rhnull in rht_bucket_nested() needs to be initialised
> at run time.
> 
> Any caller of a lookup function must still be prepared for the
> possibility that the object returned is in a different table - it
> might have been there for some time.
> 
> Note that this does NOT provide support for other uses of
> NULLS_MARKERs such as allocating with SLAB_TYPESAFE_BY_RCU or changing
> the key of an object and re-inserting it in the same table.
> These could only be done safely if new objects were inserted
> at the *start* of a hash chain, and that is not currently the case.
> 
> Signed-off-by: NeilBrown <neilb@suse.com>

Applied to net-next.

Patch
diff mbox series

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index eb7111039247..ae507af54800 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -75,8 +75,19 @@  struct bucket_table {
 	struct rhash_head __rcu *buckets[] ____cacheline_aligned_in_smp;
 };
 
+/*
+ * NULLS_MARKER() expects a hash value with the low
+ * bits mostly likely to be significant, and it discards
+ * the msb.
+ * We git it an address, in which the bottom 2 bits are
+ * always 0, and the msb might be significant.
+ * So we shift the address down one bit to align with
+ * expectations and avoid losing a significant bit.
+ */
+#define	RHT_NULLS_MARKER(ptr)	\
+	((void *)NULLS_MARKER(((unsigned long) (ptr)) >> 1))
 #define INIT_RHT_NULLS_HEAD(ptr)	\
-	((ptr) = (typeof(ptr)) NULLS_MARKER(0))
+	((ptr) = RHT_NULLS_MARKER(&(ptr)))
 
 static inline bool rht_is_a_nulls(const struct rhash_head *ptr)
 {
@@ -471,6 +482,7 @@  static inline struct rhash_head *__rhashtable_lookup(
 		.ht = ht,
 		.key = key,
 	};
+	struct rhash_head __rcu * const *head;
 	struct bucket_table *tbl;
 	struct rhash_head *he;
 	unsigned int hash;
@@ -478,13 +490,19 @@  static inline struct rhash_head *__rhashtable_lookup(
 	tbl = rht_dereference_rcu(ht->tbl, ht);
 restart:
 	hash = rht_key_hashfn(ht, tbl, key, params);
-	rht_for_each_rcu(he, tbl, hash) {
-		if (params.obj_cmpfn ?
-		    params.obj_cmpfn(&arg, rht_obj(ht, he)) :
-		    rhashtable_compare(&arg, rht_obj(ht, he)))
-			continue;
-		return he;
-	}
+	head = rht_bucket(tbl, hash);
+	do {
+		rht_for_each_rcu_continue(he, *head, tbl, hash) {
+			if (params.obj_cmpfn ?
+			    params.obj_cmpfn(&arg, rht_obj(ht, he)) :
+			    rhashtable_compare(&arg, rht_obj(ht, he)))
+				continue;
+			return he;
+		}
+		/* An object might have been moved to a different hash chain,
+		 * while we walk along it - better check and retry.
+		 */
+	} while (he != RHT_NULLS_MARKER(head));
 
 	/* Ensure we see any new tables. */
 	smp_rmb();
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 30526afa8343..852ffa5160f1 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -1179,8 +1179,7 @@  struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl,
 					    unsigned int hash)
 {
 	const unsigned int shift = PAGE_SHIFT - ilog2(sizeof(void *));
-	static struct rhash_head __rcu *rhnull =
-		(struct rhash_head __rcu *)NULLS_MARKER(0);
+	static struct rhash_head __rcu *rhnull;
 	unsigned int index = hash & ((1 << tbl->nest) - 1);
 	unsigned int size = tbl->size >> tbl->nest;
 	unsigned int subhash = hash;
@@ -1198,8 +1197,11 @@  struct rhash_head __rcu **rht_bucket_nested(const struct bucket_table *tbl,
 		subhash >>= shift;
 	}
 
-	if (!ntbl)
+	if (!ntbl) {
+		if (!rhnull)
+			INIT_RHT_NULLS_HEAD(rhnull);
 		return &rhnull;
+	}
 
 	return &ntbl[subhash].bucket;