| Message ID | 87zhtkeimx.fsf@notabene.neil.brown.name |
|---|---|
| State | Deferred, archived |
| Delegated to: | David Miller |
| Headers | show |
| Series | [net-next] rhashtable: further improve stability of rhashtable_walk | expand |
On Wed, Dec 05, 2018 at 02:51:02PM +1100, NeilBrown wrote: > > If the sequence: > obj = rhashtable_walk_next(iter); > rhashtable_walk_stop(iter); > rhashtable_remove_fast(ht, &obj->head, params); > rhashtable_walk_start(iter); > > races with another thread inserting or removing > an object on the same hash chain, a subsequent > rhashtable_walk_next() is not guaranteed to get the "next" > object. It is possible that an object could be > repeated, or missed. > > This can be made more reliable by keeping the objects in a hash chain > sorted by memory address. A subsequent rhashtable_walk_next() > call can reliably find the correct position in the list, and thus > find the 'next' object. > > It is not possible to take this approach with an rhltable as keeping > the hash chain in order is not so easy. When the first object with a > given key is removed, it is replaced in the chain with the next > object with the same key, and the address of that object may not be > correctly ordered. > I have not yet found any way to achieve the same stability > with rhltables, that doesn't have a major impact on lookup > or insert. No code currently in Linux would benefit from > such extra stability. > > With this patch: > - a new object is always inserted after the last object with a > smaller address, or at the start. > - when rhashtable_walk_start() is called, it records that 'p' is not > 'safe', meaning that it cannot be dereferenced. The revalidation > that was previously done here is moved to rhashtable_walk_next() > - when rhashtable_walk_next() is called while p is not NULL and not > safe, it walks the chain looking for the first object with an > address greater than p and returns that. If there is none, it moves > to the next hash chain. > > Signed-off-by: NeilBrown <neilb@suse.com> > --- > > This is a resend of a patch that I sent back in July. I couldn't > applied then because it assumed another rhashtable patch which hadn't > landed yet - it now has. I thought we had agreed to drop this because nobody needs it currently and it doesn't handle rhlist? Cheers,
On Fri, Dec 07 2018, Herbert Xu wrote: > On Wed, Dec 05, 2018 at 02:51:02PM +1100, NeilBrown wrote: >> >> If the sequence: >> obj = rhashtable_walk_next(iter); >> rhashtable_walk_stop(iter); >> rhashtable_remove_fast(ht, &obj->head, params); >> rhashtable_walk_start(iter); >> >> races with another thread inserting or removing >> an object on the same hash chain, a subsequent >> rhashtable_walk_next() is not guaranteed to get the "next" >> object. It is possible that an object could be >> repeated, or missed. >> >> This can be made more reliable by keeping the objects in a hash chain >> sorted by memory address. A subsequent rhashtable_walk_next() >> call can reliably find the correct position in the list, and thus >> find the 'next' object. >> >> It is not possible to take this approach with an rhltable as keeping >> the hash chain in order is not so easy. When the first object with a >> given key is removed, it is replaced in the chain with the next >> object with the same key, and the address of that object may not be >> correctly ordered. >> I have not yet found any way to achieve the same stability >> with rhltables, that doesn't have a major impact on lookup >> or insert. No code currently in Linux would benefit from >> such extra stability. >> >> With this patch: >> - a new object is always inserted after the last object with a >> smaller address, or at the start. >> - when rhashtable_walk_start() is called, it records that 'p' is not >> 'safe', meaning that it cannot be dereferenced. The revalidation >> that was previously done here is moved to rhashtable_walk_next() >> - when rhashtable_walk_next() is called while p is not NULL and not >> safe, it walks the chain looking for the first object with an >> address greater than p and returns that. If there is none, it moves >> to the next hash chain. >> >> Signed-off-by: NeilBrown <neilb@suse.com> >> --- >> >> This is a resend of a patch that I sent back in July. I couldn't >> applied then because it assumed another rhashtable patch which hadn't >> landed yet - it now has. > > I thought we had agreed to drop this because nobody needs it > currently and it doesn't handle rhlist? Hi Herbert, I think it was agreed that I would not pursue features that were only of use to out-of-tree code, but I don't think that applies here. This is not a feature, this is a quality-of-implementation improvement. There are users in the kernel today which use rhashtable_walk_stop()/rhashtable_walk_start() to drop out of RCU protection for periods during the walk. Any such user might miss seeing an object that has been in the table for a while - sure that is less than optimal, and should be fixed if the cost is small. There are currently no rhlist users which use stop/start to drop out of RCU, so there is no clear value in fixing that case, or cost in not fixing it. Thanks, 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
Hi Neil: On Mon, Dec 10, 2018 at 09:50:43AM +1100, NeilBrown wrote: > I think it was agreed that I would not pursue features that were only > of use to out-of-tree code, but I don't think that applies here. This > is not a feature, this is a quality-of-implementation improvement. > There are users in the kernel today which use > rhashtable_walk_stop()/rhashtable_walk_start() > to drop out of RCU protection for periods during the walk. > Any such user might miss seeing an object that has been in the table > for a while - sure that is less than optimal, and should be fixed if > the cost is small. > > There are currently no rhlist users which use stop/start to drop out > of RCU, so there is no clear value in fixing that case, or cost in not > fixing it. I think the complexities of this patch outweighs any benefit. Walking an rhashtable is inherently unreliable, due to rehashing. If you need an 100% reliable walking mechanism, then add your own linked list alongside the hash table like xfrm does. Having said that, if the current code is missing items that existed prior to the start of the walk (in the absence of a rehash) then that would be a bug that we should fix. Anything else like duplicates just needs to be accepted by the caller. So please explain how can an object be missed then we can work on fixing that and that only. Thanks,
On Tue, Dec 11 2018, Herbert Xu wrote: > Hi Neil: > > On Mon, Dec 10, 2018 at 09:50:43AM +1100, NeilBrown wrote: >> I think it was agreed that I would not pursue features that were only >> of use to out-of-tree code, but I don't think that applies here. This >> is not a feature, this is a quality-of-implementation improvement. >> There are users in the kernel today which use >> rhashtable_walk_stop()/rhashtable_walk_start() >> to drop out of RCU protection for periods during the walk. >> Any such user might miss seeing an object that has been in the table >> for a while - sure that is less than optimal, and should be fixed if >> the cost is small. >> >> There are currently no rhlist users which use stop/start to drop out >> of RCU, so there is no clear value in fixing that case, or cost in not >> fixing it. > > I think the complexities of this patch outweighs any benefit. > > Walking an rhashtable is inherently unreliable, due to rehashing. > If you need an 100% reliable walking mechanism, then add your own > linked list alongside the hash table like xfrm does. > > Having said that, if the current code is missing items that existed > prior to the start of the walk (in the absence of a rehash) then > that would be a bug that we should fix. Anything else like > duplicates just needs to be accepted by the caller. > > So please explain how can an object be missed then we can work on > fixing that and that only. The commit comment gives the context: If the sequence: obj = rhashtable_walk_next(iter); rhashtable_walk_stop(iter); rhashtable_remove_fast(ht, &obj->head, params); rhashtable_walk_start(iter); races with another thread inserting or removing an object on the same hash chain, a subsequent rhashtable_walk_next() is not guaranteed to get the "next" object. It is possible that an object could be repeated, or missed. The rhashtable_walk_start() at the end of this sequence will find that iter->p is not null (it will be precisely &obj->head) and will look for it in the chain, but will not find it (because of the remove_fast). So it sets iter->p to NULL. This causes rhashtable_walk_next() to fall through to __rhashtable_walk_find_next() which looks for the entry number item->skip in the chain for item->slot. ->skip will be the index for the entry just beyond obj->head. Since that has been removed, it is actually the index for the object one further on. So if obj->head was not the last entry in the chain, the object after it will be missed. The code in tipc_nl_sk_walk() is fairly similar to this pattern in that the sock_put() call could potentially result in a call to rhashtable_remove_fast(). It avoids the problem by ensuring that the rhashtable_remove_fast() is *after* the rhashtable_walk_start(). If the rhashtable_remove_fast() happened from some other thread due to a race, the walk could still miss an object. Currently, the only way to protect against this is to hold a reference to an object across rhashtable_walk_stop()/rhashtable_walk_start(). Sometimes that is easy to do, other times - not so much. So I think this is a real bug - it is quite unlikely to hit, but possibly. You need a chain with at least 2 objects, you need rhashtable_walk_stop() to be called after visiting an object other than the last object, and you need some thread (this or some other) to remove that object from the table. The patch that I posted aims to fix that bug, and only that bug. The only alternative that I can think of is to document that this can happen and advise that a reference should be held to the last visited object when stop/start is called, or in some other way ensure that it doesn't get removed. Thanks, NeilBrown > > Thanks, > -- > 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 Wed, Dec 12, 2018 at 11:02:35AM +1100, NeilBrown wrote: > > So I think this is a real bug - it is quite unlikely to hit, but > possibly. > You need a chain with at least 2 objects, you need > rhashtable_walk_stop() to be called after visiting an object other than > the last object, and you need some thread (this or some other) to remove > that object from the table. > > The patch that I posted aims to fix that bug, and only that bug. > The only alternative that I can think of is to document that this can > happen and advise that a reference should be held to the last visited > object when stop/start is called, or in some other way ensure that it > doesn't get removed. Thanks for reminding me of the issue you were trying to fix. So going back into the email archives, I suggested at the very start that we could just insert the walker objects into the actual hash table. That would solve the issue for both rhashtable and rhlist. Could we do that rather than using this ordered list that only works for rhashtable? Cheers,
On Wed, Dec 12 2018, Herbert Xu wrote: > On Wed, Dec 12, 2018 at 11:02:35AM +1100, NeilBrown wrote: >> >> So I think this is a real bug - it is quite unlikely to hit, but >> possibly. >> You need a chain with at least 2 objects, you need >> rhashtable_walk_stop() to be called after visiting an object other than >> the last object, and you need some thread (this or some other) to remove >> that object from the table. >> >> The patch that I posted aims to fix that bug, and only that bug. >> The only alternative that I can think of is to document that this can >> happen and advise that a reference should be held to the last visited >> object when stop/start is called, or in some other way ensure that it >> doesn't get removed. > > Thanks for reminding me of the issue you were trying to fix. > > So going back into the email archives, I suggested at the very > start that we could just insert the walker objects into the actual > hash table. That would solve the issue for both rhashtable and > rhlist. > > Could we do that rather than using this ordered list that only > works for rhashtable? No. that doesn't work. When you remove the walker object from the hash chain, you need to wait for the RCU grace period to expire before you can safely insert back into the chain. Inserting into a different chain isn't quite so bad now that the nulls-marker stuff is working, a lookup thread will notice the move and retry the lookup. So you would substantially slow down the rhashtable_walk_start() step. I've tried to think of various ways to over come this problem, such as walking backwards through each chain - it is fairly safe to move and object earlier in the chain - but all the approaches I have tried make the code much more complex. Thanks, 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 Wed, Dec 12, 2018 at 05:41:29PM +1100, NeilBrown wrote: > > So you would substantially slow down the rhashtable_walk_start() step. This whole thing is meant for uses such as /proc and netlink enumeration. Speed is definitely not a prerogative of these iterators. For that matter, if speed was an issue then surely you would not drop out of the RCU read lock at all while iterating. It sounds to me like you're trying to use this interface for something that it's simply not designed to do. Cheers,
On Wed, Dec 12 2018, Herbert Xu wrote: > On Wed, Dec 12, 2018 at 05:41:29PM +1100, NeilBrown wrote: >> >> So you would substantially slow down the rhashtable_walk_start() step. > > This whole thing is meant for uses such as /proc and netlink > enumeration. Speed is definitely not a prerogative of these > iterators. An RCU grace period is typically 10s of milliseconds. It doesn't take very many of those to start being noticed. > > For that matter, if speed was an issue then surely you would > not drop out of the RCU read lock at all while iterating. tipc_nl_sk_walk() drops out of RCU for every object. I don't know what it is used for, but I doubt that making it thousands of times slower would be a good thing. > > It sounds to me like you're trying to use this interface for > something that it's simply not designed to do. I'm just trying to make sure we have a reliable data structure which I can use without having to be worried that I might accidentally hit some unsupported behaviour. I don't really see why you think my patch is all that complex. The only conceptual change is that hash chains are now ordered, and ordered chains are easy to understand. The biggest part of the code change is just moving some code from rhashtable_walk_start() to rhashtable_walk_next(). Why don't you like it? Thanks, 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 Wed, Dec 12, 2018 at 07:49:08PM +1100, NeilBrown wrote: > On Wed, Dec 12 2018, Herbert Xu wrote: > > > On Wed, Dec 12, 2018 at 05:41:29PM +1100, NeilBrown wrote: > >> > >> So you would substantially slow down the rhashtable_walk_start() step. > > > > This whole thing is meant for uses such as /proc and netlink > > enumeration. Speed is definitely not a prerogative of these > > iterators. > > An RCU grace period is typically 10s of milliseconds. It doesn't take > very many of those to start being noticed. Why would you even need an RCU grace period for deleting and adding the walker object to the bucket list? You just allocate a new one each time and free the old one after an RCU grace period. I don't see where the latency is coming from. > > For that matter, if speed was an issue then surely you would > > not drop out of the RCU read lock at all while iterating. > > tipc_nl_sk_walk() drops out of RCU for every object. > I don't know what it is used for, but I doubt that making it thousands > of times slower would be a good thing. Now you're conflating two different things. Dropping the RCU isn't necessarily slow. We were talking about waiting for an RCU grace period which would only come into play if you were suspending the walk indefinitely. Actually as I said above even there you don't really need to wait. > > It sounds to me like you're trying to use this interface for > > something that it's simply not designed to do. > > I'm just trying to make sure we have a reliable data structure which I > can use without having to be worried that I might accidentally hit some > unsupported behaviour. Now that is something I agree with. > I don't really see why you think my patch is all that complex. > The only conceptual change is that hash chains are now ordered, and > ordered chains are easy to understand. > The biggest part of the code change is just moving some code from > rhashtable_walk_start() to rhashtable_walk_next(). > > Why don't you like it? My main beef is the fact that it doesn't work with rhlist. So down the track either we'll have to add more complexity for rhlist or we will have to rip this out again do something completely different. Cheers,
On Thu, Dec 13 2018, Herbert Xu wrote: > On Wed, Dec 12, 2018 at 07:49:08PM +1100, NeilBrown wrote: >> On Wed, Dec 12 2018, Herbert Xu wrote: >> >> > On Wed, Dec 12, 2018 at 05:41:29PM +1100, NeilBrown wrote: >> >> >> >> So you would substantially slow down the rhashtable_walk_start() step. >> > >> > This whole thing is meant for uses such as /proc and netlink >> > enumeration. Speed is definitely not a prerogative of these >> > iterators. >> >> An RCU grace period is typically 10s of milliseconds. It doesn't take >> very many of those to start being noticed. > > Why would you even need an RCU grace period for deleting and adding > the walker object to the bucket list? You just allocate a new one > each time and free the old one after an RCU grace period. I don't > see where the latency is coming from. Yes, you could rcu_free the old one and allocate a new one. Then you would have to be ready to deal with memory allocation failure which complicates usage (I already don't like that rhashtable_insert() can report -ENOMEM!). Another problem with inserting a marker object on rhashtable_walk_stop() is that it might not be clear where to insert it. You would have to take the spinlock, and then you might find that the location that you want to mark has been deleted from the list. I think you can probably still manage a reliable placement, but it could get messy. > >> > For that matter, if speed was an issue then surely you would >> > not drop out of the RCU read lock at all while iterating. >> >> tipc_nl_sk_walk() drops out of RCU for every object. >> I don't know what it is used for, but I doubt that making it thousands >> of times slower would be a good thing. > > Now you're conflating two different things. Dropping the RCU > isn't necessarily slow. We were talking about waiting for an > RCU grace period which would only come into play if you were > suspending the walk indefinitely. Actually as I said above even > there you don't really need to wait. How would rhashtable_walk_stop() know if it was indefinite or not? Yes, if you allocate a new marker on each rhashtable_walk_start() (passing in a gfp_t and coping with errors) then you don't need to wait a grace period. If you reuse one to avoid the errors, you do. > >> > It sounds to me like you're trying to use this interface for >> > something that it's simply not designed to do. >> >> I'm just trying to make sure we have a reliable data structure which I >> can use without having to be worried that I might accidentally hit some >> unsupported behaviour. > > Now that is something I agree with. > >> I don't really see why you think my patch is all that complex. >> The only conceptual change is that hash chains are now ordered, and >> ordered chains are easy to understand. >> The biggest part of the code change is just moving some code from >> rhashtable_walk_start() to rhashtable_walk_next(). >> >> Why don't you like it? > > My main beef is the fact that it doesn't work with rhlist. So down > the track either we'll have to add more complexity for rhlist or > we will have to rip this out again do something completely different. You have previously said that functionality which isn't needed by current code should not be a concern. No current code ever stops and restarts an rhlist walk, so this shouldn't be relevant. Solve that problem when/if we come to it. If this is really the main beef, then let's turn the question around. Suppose this patch had landed before rhltables had landed. How would we implement rhltables without breaking this functionality? Keeping all the objects with the same key in a linked list is clearly a good idea - make this a circular list as there is no obvious "first". *Not* keeping them all in the hash chain is ideal, but not essential. I see three costs with this. One is that we would compare the same key multiple times for lookup. How much of a problem is that? A failing compare is usually quite quick, and most rhltable uses have inline memcmp for comparison (admittedly not all). The second cost is tracking the chain length against elasticity. We could flag one object with each key as a 'master' (low bit of the 'next' pointer) and only count the masters. When lookup raced with remove this might get a slightly incorrect count, but I don't think that hurts. Finally, there is more pointer chasing as the chains are longer. Was performance part of the reason for adding rhltables? It isn't mentioned in the commit message, but it is easy to miss things. Thanks, 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 Thu, Dec 13, 2018 at 02:48:59PM +1100, NeilBrown wrote: > > Yes, you could rcu_free the old one and allocate a new one. Then you > would have to be ready to deal with memory allocation failure which > complicates usage (I already don't like that rhashtable_insert() can > report -ENOMEM!). Yes there will be a cost to dealing with allocation failure but at least it'll work reliably in all cases. For the intended use-case of dumping things to user-space allocation failure is a non-issue. > > Now you're conflating two different things. Dropping the RCU > > isn't necessarily slow. We were talking about waiting for an > > RCU grace period which would only come into play if you were > > suspending the walk indefinitely. Actually as I said above even > > there you don't really need to wait. > > How would rhashtable_walk_stop() know if it was indefinite or not? You assume that it's always indefinite because the typical usage of stop is because we have run out of memory and must wait for user- space to read what we have produced so far to free up memory. > *Not* keeping them all in the hash chain is ideal, but not essential. > I see three costs with this. > One is that we would compare the same key multiple times for lookup. > How much of a problem is that? A failing compare is usually quite quick, > and most rhltable uses have inline memcmp for comparison (admittedly not > all). > > The second cost is tracking the chain length against elasticity. > We could flag one object with each key as a 'master' (low bit of the > 'next' pointer) and only count the masters. When lookup raced with > remove this might get a slightly incorrect count, but I don't think that > hurts. > > Finally, there is more pointer chasing as the chains are longer. The biggest problem is that you can no longer return the lookup result. When you perform a lookup on rhltable you need to return all the matching objects, not just a random one. Cheers,
diff --git a/include/linux/rhashtable-types.h b/include/linux/rhashtable-types.h index 763d613ce2c2..bc3e84547ba7 100644 --- a/include/linux/rhashtable-types.h +++ b/include/linux/rhashtable-types.h @@ -126,6 +126,7 @@ struct rhashtable_iter { struct rhashtable_walker walker; unsigned int slot; unsigned int skip; + bool p_is_unsafe; bool end_of_table; }; diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h index 20f9c6af7473..4a8056b66bfb 100644 --- a/include/linux/rhashtable.h +++ b/include/linux/rhashtable.h @@ -635,7 +635,12 @@ static inline void *__rhashtable_insert_fast( (params.obj_cmpfn ? params.obj_cmpfn(&arg, rht_obj(ht, head)) : rhashtable_compare(&arg, rht_obj(ht, head)))) { - pprev = &head->next; + if (rhlist) { + pprev = &head->next; + } else { + if (head < obj) + pprev = &head->next; + } continue; } @@ -1131,7 +1136,8 @@ static inline int rhashtable_walk_init(struct rhashtable *ht, * Note that if you restart a walk after rhashtable_walk_stop you * may see the same object twice. Also, you may miss objects if * there are removals in between rhashtable_walk_stop and the next - * call to rhashtable_walk_start. + * call to rhashtable_walk_start. Note that this is different to + * rhashtable_walk_enter() which never misses objects. * * For a completely stable walk you should construct your own data * structure outside the hash table. diff --git a/lib/rhashtable.c b/lib/rhashtable.c index 852ffa5160f1..d4154b9a29a1 100644 --- a/lib/rhashtable.c +++ b/lib/rhashtable.c @@ -225,6 +225,7 @@ static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash) struct bucket_table *old_tbl = rht_dereference(ht->tbl, ht); struct bucket_table *new_tbl = rhashtable_last_table(ht, old_tbl); struct rhash_head __rcu **pprev = rht_bucket_var(old_tbl, old_hash); + struct rhash_head __rcu **inspos; int err = -EAGAIN; struct rhash_head *head, *next, *entry; spinlock_t *new_bucket_lock; @@ -253,12 +254,15 @@ static int rhashtable_rehash_one(struct rhashtable *ht, unsigned int old_hash) new_bucket_lock = rht_bucket_lock(new_tbl, new_hash); spin_lock_nested(new_bucket_lock, SINGLE_DEPTH_NESTING); - head = rht_dereference_bucket(new_tbl->buckets[new_hash], - new_tbl, new_hash); - + inspos = &new_tbl->buckets[new_hash]; + head = rht_dereference_bucket(*inspos, new_tbl, new_hash); + while (!rht_is_a_nulls(head) && head < entry) { + inspos = &head->next; + head = rht_dereference_bucket(*inspos, new_tbl, new_hash); + } RCU_INIT_POINTER(entry->next, head); - rcu_assign_pointer(new_tbl->buckets[new_hash], entry); + rcu_assign_pointer(*inspos, entry); spin_unlock(new_bucket_lock); rcu_assign_pointer(*pprev, next); @@ -554,6 +558,10 @@ static struct bucket_table *rhashtable_insert_one(struct rhashtable *ht, return ERR_PTR(-ENOMEM); head = rht_dereference_bucket(*pprev, tbl, hash); + while (!ht->rhlist && !rht_is_a_nulls(head) && head < obj) { + pprev = &head->next; + head = rht_dereference_bucket(*pprev, tbl, hash); + } RCU_INIT_POINTER(obj->next, head); if (ht->rhlist) { @@ -648,10 +656,10 @@ EXPORT_SYMBOL_GPL(rhashtable_insert_slow); * * This function prepares a hash table walk. * - * Note that if you restart a walk after rhashtable_walk_stop you - * may see the same object twice. Also, you may miss objects if - * there are removals in between rhashtable_walk_stop and the next - * call to rhashtable_walk_start. + * A walk is guaranteed to return every object that was in + * the table before this call, and is still in the table when + * rhashtable_walk_next() returns NULL. Duplicates can be + * seen, but only if there is a rehash event during the walk. * * For a completely stable walk you should construct your own data * structure outside the hash table. @@ -735,19 +743,10 @@ int rhashtable_walk_start_check(struct rhashtable_iter *iter) if (iter->p && !rhlist) { /* - * We need to validate that 'p' is still in the table, and - * if so, update 'skip' + * 'p' will be revalidated when rhashtable_walk_next() + * is called. */ - 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; + iter->p_is_unsafe = true; } else if (iter->p && rhlist) { /* Need to validate that 'list' is still in the table, and * if so, update 'skip' and 'p'. @@ -864,15 +863,39 @@ void *rhashtable_walk_next(struct rhashtable_iter *iter) bool rhlist = ht->rhlist; if (p) { - if (!rhlist || !(list = rcu_dereference(list->next))) { - p = rcu_dereference(p->next); - list = container_of(p, struct rhlist_head, rhead); - } - if (!rht_is_a_nulls(p)) { - iter->skip++; - iter->p = p; - iter->list = list; - return rht_obj(ht, rhlist ? &list->rhead : p); + if (!rhlist && iter->p_is_unsafe) { + /* + * First time next() was called after start(). + * Need to find location of 'p' in the list. + */ + struct rhash_head *p; + + iter->skip = 0; + rht_for_each_rcu(p, iter->walker.tbl, iter->slot) { + iter->skip++; + if (p <= iter->p) + continue; + + /* p is the next object after iter->p */ + iter->p = p; + iter->p_is_unsafe = false; + return rht_obj(ht, p); + } + /* There is no "next" object in the list, move + * to next hash chain. + */ + } else { + if (!rhlist || !(list = rcu_dereference(list->next))) { + p = rcu_dereference(p->next); + list = container_of(p, struct rhlist_head, + rhead); + } + if (!rht_is_a_nulls(p)) { + iter->skip++; + iter->p = p; + iter->list = list; + return rht_obj(ht, rhlist ? &list->rhead : p); + } } /* At the end of this slot, switch to next one and then find @@ -882,6 +905,7 @@ void *rhashtable_walk_next(struct rhashtable_iter *iter) iter->slot++; } + iter->p_is_unsafe = false; return __rhashtable_walk_find_next(iter); } EXPORT_SYMBOL_GPL(rhashtable_walk_next);
If the sequence: obj = rhashtable_walk_next(iter); rhashtable_walk_stop(iter); rhashtable_remove_fast(ht, &obj->head, params); rhashtable_walk_start(iter); races with another thread inserting or removing an object on the same hash chain, a subsequent rhashtable_walk_next() is not guaranteed to get the "next" object. It is possible that an object could be repeated, or missed. This can be made more reliable by keeping the objects in a hash chain sorted by memory address. A subsequent rhashtable_walk_next() call can reliably find the correct position in the list, and thus find the 'next' object. It is not possible to take this approach with an rhltable as keeping the hash chain in order is not so easy. When the first object with a given key is removed, it is replaced in the chain with the next object with the same key, and the address of that object may not be correctly ordered. I have not yet found any way to achieve the same stability with rhltables, that doesn't have a major impact on lookup or insert. No code currently in Linux would benefit from such extra stability. With this patch: - a new object is always inserted after the last object with a smaller address, or at the start. - when rhashtable_walk_start() is called, it records that 'p' is not 'safe', meaning that it cannot be dereferenced. The revalidation that was previously done here is moved to rhashtable_walk_next() - when rhashtable_walk_next() is called while p is not NULL and not safe, it walks the chain looking for the first object with an address greater than p and returns that. If there is none, it moves to the next hash chain. Signed-off-by: NeilBrown <neilb@suse.com> --- This is a resend of a patch that I sent back in July. I couldn't applied then because it assumed another rhashtable patch which hadn't landed yet - it now has. NeilBrown include/linux/rhashtable-types.h | 1 + include/linux/rhashtable.h | 10 ++++- lib/rhashtable.c | 82 ++++++++++++++++++++++++++-------------- 3 files changed, 62 insertions(+), 31 deletions(-)