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

On Tue, Dec 11 2018, Herbert Xu wrote:

Hi Neil:

On Mon, Dec 10, 2018 at 09:50:43AM +1100, NeilBrown wrote:

quoted

 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 [off-list ref]
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt