Re: [PATCH 6/8] rhashtable: further improve stability of rhashtable_walk

Herbert Xu
2018-05-05T09:42:18Z

On Fri, May 04, 2018 at 01:54:14PM +1000, 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 (certainly not so easy) to achieve this 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.
> No current user of rhltable_walk_enter() calls
> rhashtable_walk_start() more than once, so no current code
> could benefit from a more reliable walk of rhltables.
>
> This patch only attempts to improve walks for rhashtables.
> - 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>

I'm a bit torn on this. On the hand this is definitely an improvement
over the status quo. On the other this does not work on rhltable and
we do have a way of fixing it for both rhashtable and rhltable.

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