netdev - Re: [v3 PATCH 0/9] rhashtable: Multiple rehashing

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: <20150324023729.GA7973@gondor.apana.org.au>
Date:	Tue, 24 Mar 2015 13:37:30 +1100
From:	Herbert Xu <herbert@...dor.apana.org.au>
To:	David Miller <davem@...emloft.net>
Cc:	tgraf@...g.ch, eric.dumazet@...il.com, kaber@...sh.net,
	josh@...htriplett.org, paulmck@...ux.vnet.ibm.com,
	netdev@...r.kernel.org
Subject: Re: [v3 PATCH 0/9] rhashtable: Multiple rehashing

On Mon, Mar 23, 2015 at 10:09:13PM -0400, David Miller wrote:
> From: Herbert Xu <herbert@...dor.apana.org.au>
> Date: Tue, 24 Mar 2015 00:49:55 +1100
> 
> > This series introduces multiple rehashing.
> 
> This looks great, nice work.  All applied to net-next.

Thanks!

> Could you please add a comment next to the "16" from patch
> #9 explaining why that value was choosen and the invariants
> that influence it?

Sure.

---8<---
rhashtable: Add comment on choice of elasticity value

This patch adds a comment on the choice of the value 16 as the
maximum chain length before we force a rehash.

Signed-off-by: Herbert Xu <herbert@...dor.apana.org.au>

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index e96ad1a..8514f7c 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -736,6 +736,18 @@ int rhashtable_init(struct rhashtable *ht,
 
 	ht->p.min_size = max(ht->p.min_size, HASH_MIN_SIZE);
 
+	/* The maximum (not average) chain length grows with the
+	 * size of the hash table, at a rate of (log N)/(log log N).
+	 * The value of 16 is selected so that even if the hash
+	 * table grew to 2^32 you would not expect the maximum
+	 * chain length to exceed it unless we are under attack
+	 * (or extremely unlucky).
+	 *
+	 * As this limit is only to detect attacks, we don't need
+	 * to set it to a lower value as you'd need the chain
+	 * length to vastly exceed 16 to have any real effect
+	 * on the system.
+	 */
 	if (!params->insecure_elasticity)
 		ht->elasticity = 16;
 
-- 
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
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html