netdev - Re: rhashtable issue

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: <173248963527.1734440.16500857468413237164@noble.neil.brown.name>
Date: Mon, 25 Nov 2024 10:07:15 +1100
From: "NeilBrown" <neilb@...e.de>
To: "Kent Overstreet" <kent.overstreet@...ux.dev>
Cc: "Herbert Xu" <herbert@...dor.apana.org.au>, "Thomas Graf" <tgraf@...g.ch>,
 netdev@...r.kernel.org
Subject: Re: rhashtable issue - -EBUSY

On Mon, 25 Nov 2024, Kent Overstreet wrote:
> On Sun, Nov 24, 2024 at 09:01:26PM +1100, NeilBrown wrote:
> > On Sun, 24 Nov 2024, Herbert Xu wrote:
> > > On Sun, Nov 24, 2024 at 08:25:38PM +1100, NeilBrown wrote:
> > > >
> > > > Failure should not just be extremely unlikely.  It should be
> > > > mathematically impossible. 
> > > 
> > > Please define mathematically impossible.  If you mean zero then
> > > it's pointless since modern computers are known to have non-zero
> > > failure rates.
> > 
> > mathematically assuming perfect hardware.  i.e.  an analysis of the
> > software would show there is no way for an error to be returned.
> > 
> > > 
> > > If you have a definite value in mind, then we could certainly
> > > tailor the maximum elasticity to achieve that goal.
> > 
> > I don't think there is any need to change the elasticity.  Rehashing
> > whenever the longest chain reaches 16 seems reasonable - though some
> > simple rate limiting to avoid a busy-loop with a bad hash function would
> > not be unwelcome.
> > 
> > But I don't see any justification for refusing an insertion because we
> > haven't achieved the short chains yet.  Certainly a WARN_ON_ONCE or a
> > rate-limited WARN_ON might be appropriate.  Developers should be told
> > when their hash function isn't good enough.
> > But requiring developers to test for errors and to come up with some way
> > to manage them (sleep and try again is all I can think of) doesn't help anyone.
> 
> Agreed, sleep until the rehash finishes seems like what we're after, and
> that should be in the rhashtable code.
> 

No, it shouldn't be in the rhashtable code.  It is a work-around that
shouldn't be needed.
The rhashtable insert code mustn't sleep as the caller might hold locks.
Currently the caller needs to release locks, sleep an arbitrary time,
then retry.

The rhashtable code should simply insert the new item when it is asked
to.  The failure is a deliberate choice that can easily be avoid.

The only case that is at all difficult is when a "nested" table is used.
In this case the table of pointers is allocated incrementally and the
target slot might not yet exist in the "last" table and an ATOMIC
allocation might fail.  In that case the new entry should be inserted in
the penultimate table, and that might have some interesting locking
issues.

NeilBrown