Re: [PATCH net-next] rhashtable: further improve stability of rhashtable_walk

From: NeilBrown
Date: Tue Dec 11 2018 - 19:02:48 EST

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_remove_fast(ht, &obj->head, params);

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
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
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,
> --
> Email: Herbert Xu <herbert@xxxxxxxxxxxxxxxxxxx>
> Home Page:
> PGP Key:

Attachment: signature.asc
Description: PGP signature