linux-kernel - Re: [PATCH 4/6] rhashtable: allow a walk of the hash table without missing objects.

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <87a7us4qje.fsf@notabene.neil.brown.name>
Date:   Wed, 28 Mar 2018 18:17:57 +1100
From:   NeilBrown <neilb@...e.com>
To:     Herbert Xu <herbert@...dor.apana.org.au>
Cc:     Thomas Graf <tgraf@...g.ch>, netdev@...r.kernel.org,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH 4/6] rhashtable: allow a walk of the hash table without missing objects.

On Wed, Mar 28 2018, Herbert Xu wrote:

> On Wed, Mar 28, 2018 at 08:54:41AM +1100, NeilBrown wrote:
>>
>> Possibly.
>> I particularly want the interface to require that you pass the
>> previously returned object to _continue. That makes it easy to see that
>> the object is still being used.  If someone changes to code to delete
>> the object before the _continue, there should be a strong hint that it
>> won't work.
>> 
>> Maybe it would be better to make it a WARN_ON()
>> 
>>   if (!obj || WARN_ON(iter->p != obj))
>>          iter->p = NULL;
>
> This doesn't really protect against the case where obj is removed.
> All it proves is that the user saved a copy of obj which we already
> did anyway.

True.  We ultimately need to trust the user not to do something silly.
We can do little things to help catch obvious errors though.  That was
my intent with the WARN_ON.

>
> To detect an actual removal you'd need to traverse the list.

Yes.  You could reset ->skip to zero and search for the given object.
That feels a bit like excess hand-holding to me, but probably wouldn't
be too expensive.  It only happens when you need to drop out of RCU, and
in that case you are probably already doing something expensive.

>
> I have another idea: we could save insert the walkers into the
> hash table chain at the end, essentially as a hidden list.  We
> can mark it with a flag like rht_marker so that normal traversal
> doesn't see it.
>
> That way the removal code can simply traverse that list and inform
> them that the iterator is invalid.

Sounds like over-kill to me.
It might be reasonable to have a CONFIG_DEBUG_RHASHTABLE which enables
extra to code to catch misuse, but I don't see the justification for
always performing these checks.
The DEBUG code could just scan the chain (usually quite short) to see if
the given element is present.  Of course it might have already been
rehashed to the next table, so you would to allow for that possibility -
probably check tbl->rehash.

Thanks,
NeilBrown

>
> Cheers,
> -- 
> Email: Herbert Xu <herbert@...dor.apana.org.au>
> Home Page: http://gondor.apana.org.au/~herbert/
> PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Download attachment "signature.asc" of type "application/pgp-signature" (833 bytes)