netdev - [PATCH net-next 2/2] rhashtable: Quick initial growth of tables

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: <1430434005-6143-3-git-send-email-tgraf@suug.ch>
Date:	Thu, 30 Apr 2015 22:46:45 +0000
From:	Thomas Graf <tgraf@...g.ch>
To:	davem@...emloft.net
Cc:	netdev@...r.kernel.org, herbert@...dor.apana.org.au,
	kaber@...sh.net
Subject: [PATCH net-next 2/2] rhashtable: Quick initial growth of tables

Grow the table quicker than 2x in the beginning to avoid long chains
of rehashes. The effect is observable in the self-test where table
jumps are reduced to a minimum after a lot of entries have been added
in a short period of time. The iterator is able to get a consistent
view most of the time.

Signed-off-by: Thomas Graf <tgraf@...g.ch>
---
 lib/rhashtable.c | 37 +++++++++++++++++++++++++++++++++++--
 1 file changed, 35 insertions(+), 2 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 4936fc4..23e7f18 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -271,6 +271,38 @@ static int rhashtable_rehash_table(struct rhashtable *ht)
 	return rht_dereference(new_tbl->future_tbl, ht) ? -EAGAIN : 0;
 }
 
+static int table_growth_log(unsigned int size)
+{
+	/*
+	 * Table growth:
+	 *     2 ->   64
+	 *     4 ->  128
+	 *     8 ->  128
+	 *    16 ->  256
+	 *    32 ->  512
+	 *    64 ->  512
+	 *   128 -> 1024
+	 *   256 -> 2048
+	 *   512 -> 2048
+	 *  1024 -> 4096
+	 *  2048 -> 8192
+	 *  4096 -> 8192
+	 */
+	int log = 5 - (ilog2(size) / 3);
+
+	return log > 1 ? log : 1;
+}
+
+static unsigned int grow_table(struct rhashtable *ht, unsigned int old_size)
+{
+	unsigned int new_size;
+
+	new_size = old_size << table_growth_log(old_size);
+	new_size = min(new_size, ht->p.max_size);
+
+	return new_size;
+}
+
 /**
  * rhashtable_expand - Expand hash table while allowing concurrent lookups
  * @ht:		the hash table to expand
@@ -295,7 +327,8 @@ static int rhashtable_expand(struct rhashtable *ht)
 
 	old_tbl = rhashtable_last_table(ht, old_tbl);
 
-	new_tbl = bucket_table_alloc(ht, old_tbl->size * 2, GFP_KERNEL);
+	new_tbl = bucket_table_alloc(ht, grow_table(ht, old_tbl->size),
+				     GFP_KERNEL);
 	if (new_tbl == NULL)
 		return -ENOMEM;
 
@@ -404,7 +437,7 @@ int rhashtable_insert_rehash(struct rhashtable *ht)
 	size = tbl->size;
 
 	if (rht_grow_above_75(ht, tbl))
-		size *= 2;
+		size = grow_table(ht, size);
 	/* Do not schedule more than one rehash */
 	else if (old_tbl != tbl)
 		return -EBUSY;
-- 
1.9.3

--
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