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 <[email protected]>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
signature.asc
Description: PGP signature
