| Message ID | 87muqbtev6.fsf@notabene.neil.brown.name |
|---|---|
| State | Changes Requested, archived |
| Delegated to: | David Miller |
| Headers | show |
| Series | rhashtable: detect when object movement between tables might have invalidated a lookup | expand |
On Thu, Nov 15, 2018 at 10:32:13AM +1100, NeilBrown wrote: > > +#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))) Why are you shifting this by one? > 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; I don't understand why you can't continue to do NULLS_MARKER(0) or RHT_NULLS_MARKER(0). Cheers,
E On Fri, Nov 16 2018, Herbert Xu wrote: > On Thu, Nov 15, 2018 at 10:32:13AM +1100, NeilBrown wrote: >> >> +#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))) > > Why are you shifting this by one? NULLS_MARKER assumes a hash value in which the bottom bits are most likely to be unique. To convert this to a pointer which certainly not valid, it shifts left by 1 and sets the lsb. We aren't passing a hash value, but are passing an address instead. In this case the bottom 2 bits are certain to be 0, and the top bit could contain valuable information (on a 32bit system). The best way to turn a pointer into a certainly-invalid pointer is to just set the lsb. By shifting right by one, we discard an uninteresting bit, preserve all the interesting bits, and effectively just set the lsb. I could add a comment explaining that if you like. > >> 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; > > I don't understand why you can't continue to do NULLS_MARKER(0) or > RHT_NULLS_MARKER(0). Because then the test + } while (he != RHT_NULLS_MARKER(head)); in __rhashtable_lookup() would always succeed, and it would loop forever. Thanks for the review. NeilBrown > > Cheers, > -- > 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
On Fri, Nov 16, 2018 at 05:59:19PM +1100, NeilBrown wrote: > > NULLS_MARKER assumes a hash value in which the bottom bits are most > likely to be unique. To convert this to a pointer which certainly not > valid, it shifts left by 1 and sets the lsb. > We aren't passing a hash value, but are passing an address instead. > In this case the bottom 2 bits are certain to be 0, and the top bit > could contain valuable information (on a 32bit system). > The best way to turn a pointer into a certainly-invalid pointer > is to just set the lsb. By shifting right by one, we discard an > uninteresting bit, preserve all the interesting bits, and effectively > just set the lsb. > > I could add a comment explaining that if you like. The top-bit is most likely to be fixed and offer no real value. > >> 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; > > > > I don't understand why you can't continue to do NULLS_MARKER(0) or > > RHT_NULLS_MARKER(0). > > Because then the test > > + } while (he != RHT_NULLS_MARKER(head)); > > in __rhashtable_lookup() would always succeed, and it would loop > forever. This change is only necessary because of your shifting change above, which AFAICS adds no real benefit. Cheers,
On Mon, Nov 19, 2018 at 11:54:15AM +0800, Herbert Xu 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; > > > > > > I don't understand why you can't continue to do NULLS_MARKER(0) or > > > RHT_NULLS_MARKER(0). > > > > Because then the test > > > > + } while (he != RHT_NULLS_MARKER(head)); > > > > in __rhashtable_lookup() would always succeed, and it would loop > > forever. > > This change is only necessary because of your shifting change > above, which AFAICS adds no real benefit. I take that back. Because of your shift which cancels out the shift in NULLS_MARKER, it would appear that this should work just fine with RHT_NULLS_MARRKER(0), no? IOW, it would appear that RHT_NULLS_MARKER(0) = RHT_NULLS_MARKER(RHT_NULLS_MARKER(0)) Thanks,
On Mon, Nov 19, 2018 at 11:56:35AM +0800, Herbert Xu wrote: > > I take that back. Because of your shift which cancels out the > shift in NULLS_MARKER, it would appear that this should work just > fine with RHT_NULLS_MARRKER(0), no? IOW, it would appear that > > RHT_NULLS_MARKER(0) = RHT_NULLS_MARKER(RHT_NULLS_MARKER(0)) My emails to Neil are bouncing: neilb@suse.com host smtp.glb1.softwaregrp.com [15.124.2.87] SMTP error from remote mail server after RCPT TO:<neilb@suse.com>: 550 Cannot process address Cheers,
From: Herbert Xu <herbert@gondor.apana.org.au> Date: Mon, 19 Nov 2018 12:06:34 +0800 > On Mon, Nov 19, 2018 at 11:56:35AM +0800, Herbert Xu wrote: >> >> I take that back. Because of your shift which cancels out the >> shift in NULLS_MARKER, it would appear that this should work just >> fine with RHT_NULLS_MARRKER(0), no? IOW, it would appear that >> >> RHT_NULLS_MARKER(0) = RHT_NULLS_MARKER(RHT_NULLS_MARKER(0)) > > My emails to Neil are bouncing: > > neilb@suse.com > host smtp.glb1.softwaregrp.com [15.124.2.87] > SMTP error from remote mail server after RCPT TO:<neilb@suse.com>: > 550 Cannot process address Yeah this just started happening 2 days ago.
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h index eb7111039247..8cc240f14834 100644 --- a/include/linux/rhashtable.h +++ b/include/linux/rhashtable.h @@ -75,8 +75,10 @@ struct bucket_table { struct rhash_head __rcu *buckets[] ____cacheline_aligned_in_smp; }; +#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 +473,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 +481,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;
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> --- I sent this patch back in July, but I made a bit of a mess of it. Here it is again, with a bit more care. Previously in Commit: 9f9a707738aa ("rhashtable: remove nulls_base and related code.") I removed some 'nulls' related code that wasn't being used and wasn't usable. This patch adds code to provide the functionality that the removed code was intended for. Specifically, it is now possible to move an object in one rhashtable into another rhashtable, and still provide correct lookup(etc) semantics. If a lookup is performed on a table from which objects can be moved, then a found object will have been in the table at some point during the looku, but might not still be there. If that lookup returns failure, then you can be sure that there was no matching object in the table for the entire duration of the lookup. This patch doesn't provide code to safely move an object. It just adds enough code that the already-existing references to NULLS_MARKER()s make sense. NeilBrown include/linux/rhashtable.h | 25 +++++++++++++++++-------- lib/rhashtable.c | 8 +++++--- 2 files changed, 22 insertions(+), 11 deletions(-)