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: <Z0KaexOJM1phuJKS@gondor.apana.org.au>
Date: Sun, 24 Nov 2024 11:16:11 +0800
From: Herbert Xu <herbert@...dor.apana.org.au>
To: Kent Overstreet <kent.overstreet@...ux.dev>
Cc: Thomas Graf <tgraf@...g.ch>, netdev@...r.kernel.org,
	Neil Brown <neilb@...e.de>
Subject: Re: rhashtable issue - -EBUSY

On Sat, Nov 23, 2024 at 12:21:21PM -0500, Kent Overstreet wrote:
> I'm seeing an issue where rhashtable inserts sporadically return -EBUSY,
> thrown from rhashtable_insert_rehash() when there's already a rehash in
> progress, i.e. rehashes aren't keeping up.

EBUSY should never happen *if* you're using the hash table correctly.
It is expected to happen if you insert multiple identical entries
into the same hash table (the correct thing to do in that case is
to use rhltable which is designed to accomodate multiple entries
with the same key).

Now assuming that is not the case and you are using rhashtable
correctly, this is when an EBUSY will occur during an insert:

1) The hash table elasticity has been violated, meaning that
more than 16 entries are in a single chain.

2) The hash table is below 50% capacity (meaning that statistically
we do not expect 1) to be true).

3) An existing rehash is already taking place.

The reason we have the EBUSY mechanism in place is to prevent
the case where we are being actively attacked by a hostile
actor, who has somehow compromised our hash function.

The first line of defence is to change our hash function and
conduct a rehash.  This is what would have occured if 3) is
false.

Once a rehash is in place, if we hit 1) + 2) again, then it
means that our defence was futile and the hostile actor is
still able to create arbitrarily long hash chains (possibly
by compromising our RNG since we use that for the rehash),
and as we do not have any defence mechanism for that, it is
better to just fail.

Of course this is meant to be impossible to hit in practice.
Whenever it has occurred in the past, it's always been because
people were tring to insert identical keyed entries into the
same table (Use rhltable instead).

Theoretically it is also possible to hit this if your hash
table was immense (expected worst-case hash chain length is
log N / log log N), but it has never been hit in the past
with our default elasticity of 16.

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