| Message ID | 876016r9z5.fsf@notabene.neil.brown.name |
|---|---|
| State | Changes Requested, archived |
| Delegated to: | David Miller |
| Headers | show |
| Series | [net-next] rhashtable: detect when object movement between tables might have invalidated a lookup | expand |
From: NeilBrown <neilb@suse.com> Date: Mon, 23 Jul 2018 11:56:14 +1000 > 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 is repeated. ... > This is a simplified version of a previous patch. > It provides NULLS_MARKER support only for the specific use case > which is currently thought be valuable to in-tree users > of rhashtables. Neil, this doesn't even compile: In file included from lib/rhashtable.c:28: lib/rhashtable.c: In function ‘rht_bucket_nested’: ./include/linux/rhashtable.h:79:2: error: initializer element is not computable at load time ((void *)NULLS_MARKER(((unsigned long) (ptr)) >> 1)) ^ lib/rhashtable.c:1178:43: note: in expansion of macro ‘RHT_NULLS_MARKER’ static struct rhash_head __rcu *rhnull = RHT_NULLS_MARKER(&rhnull); ^~~~~~~~~~~~~~~~ make[1]: *** [scripts/Makefile.build:318: lib/rhashtable.o] Error 1 make: *** [Makefile:1653: lib/rhashtable.o] Error 2 I imagine you have a mix of other changes or whatever in your tree, so I'll give you the benefit of the doubt. But this is the second time this has happened with your rhashtable changes, so...
On Thu, Jul 26 2018, David Miller wrote: > From: NeilBrown <neilb@suse.com> > Date: Mon, 23 Jul 2018 11:56:14 +1000 > >> 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 is repeated. > ... >> This is a simplified version of a previous patch. >> It provides NULLS_MARKER support only for the specific use case >> which is currently thought be valuable to in-tree users >> of rhashtables. > > Neil, this doesn't even compile: > > In file included from lib/rhashtable.c:28: > lib/rhashtable.c: In function ‘rht_bucket_nested’: > ./include/linux/rhashtable.h:79:2: error: initializer element is not computable at load time > ((void *)NULLS_MARKER(((unsigned long) (ptr)) >> 1)) > ^ > lib/rhashtable.c:1178:43: note: in expansion of macro ‘RHT_NULLS_MARKER’ > static struct rhash_head __rcu *rhnull = RHT_NULLS_MARKER(&rhnull); > ^~~~~~~~~~~~~~~~ > make[1]: *** [scripts/Makefile.build:318: lib/rhashtable.o] Error 1 > make: *** [Makefile:1653: lib/rhashtable.o] Error 2 > > I imagine you have a mix of other changes or whatever in your tree, so I'll > give you the benefit of the doubt. > > But this is the second time this has happened with your rhashtable changes, > so... Your displeasure is understandable. I had fixed this, but hadn't refreshed the patch - though I had updated the patch description to explain the change I had to make - second sentence of: 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_nexted() need to be initialised at run time. This is what I meant to send - it does compile. Thanks, NeilBrown From: NeilBrown <neilb@suse.com> Date: Mon, 25 Jun 2018 08:09:16 +1000 Subject: [PATCH] rhashtable: detect when object movement between tables might have invalidated a lookup 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 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_nexted() need to be initialised at run time. Any caller of a lookup function must 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 for NULLS_MARKERs such as allocating with SLAB_TYPESAFE_BY_RCU or changing the key of an object and re-inserting it in the 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> --- include/linux/rhashtable.h | 25 +++++++++++++++++-------- lib/rhashtable.c | 8 +++++--- 2 files changed, 22 insertions(+), 11 deletions(-) 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 ae4223e0f5bc..0b1baede369c 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -1175,8 +1175,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; @@ -1194,8 +1193,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;
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 ae4223e0f5bc..ac48f026a8c3 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -1175,8 +1175,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 = RHT_NULLS_MARKER(&rhnull); unsigned int index = hash & ((1 << tbl->nest) - 1); unsigned int size = tbl->size >> tbl->nest; unsigned int subhash = hash;
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 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_nexted() need to be initialised at run time. Any caller of a lookup function must 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 for NULLS_MARKERs such as allocating with SLAB_TYPESAFE_BY_RCU or changing the key of an object and re-inserting it in the 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 is a simplified version of a previous patch. It provides NULLS_MARKER support only for the specific use case which is currently thought be valuable to in-tree users of rhashtables. Thanks, NeilBrown include/linux/rhashtable.h | 25 +++++++++++++++++-------- lib/rhashtable.c | 3 +-- 2 files changed, 18 insertions(+), 10 deletions(-)