Messages in this thread Patch in this message | | | From | NeilBrown <> | Date | Fri, 27 Jul 2018 08:04:40 +1000 | Subject | Re: [PATCH net-next] rhashtable: detect when object movement between tables might have invalidated a lookup |
| |
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; -- 2.14.0.rc0.dirty [unhandled content-type:application/pgp-signature] | |