linux-kernel - [PATCH, RFC 11/12] random: speed up the fast

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: <1379882338-7209-12-git-send-email-tytso@mit.edu>
Date:	Sun, 22 Sep 2013 16:38:57 -0400
From:	Theodore Ts'o <tytso@....edu>
To:	Linux Kernel Developers List <linux-kernel@...r.kernel.org>
Cc:	hpa@...or.com, joern@...fs.org, macro@...ux-mips.org,
	ralf@...ux-mips.org, dave.taht@...il.com, blogic@...nwrt.org,
	andrewmcgr@...il.com, smueller@...onox.de, geert@...ux-m68k.org,
	tg@...bsd.de, Theodore Ts'o <tytso@....edu>
Subject: [PATCH, RFC 11/12] random: speed up the fast_mix function by a factor of four

By mixing the entropy in chunks of 32-bit words instead of byte by
byte, we can speed up the fast_mix function significantly.  Since it
is called on every single interrupt, on systems with a very heavy
interrupt load, this can make a noticeable different.

Signed-off-by: "Theodore Ts'o" <tytso@....edu>
Reported-by: Jörn Engel <joern@...fs.org>
---
 drivers/char/random.c | 30 +++++++++++++++++-------------
 1 file changed, 17 insertions(+), 13 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 3439b1c..86879d1 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -583,21 +583,26 @@ struct fast_pool {
  * collector.  It's hardcoded for an 128 bit pool and assumes that any
  * locks that might be needed are taken by the caller.
  */
-static void fast_mix(struct fast_pool *f, const void *in, int nbytes)
+static void fast_mix(struct fast_pool *f, __u32 input[4])
 {
-	const char	*bytes = in;
 	__u32		w;
-	unsigned	i = f->count;
 	unsigned	input_rotate = f->rotate;
 
-	while (nbytes--) {
-		w = rol32(*bytes++, input_rotate & 31) ^ f->pool[i & 3] ^
-			f->pool[(i + 1) & 3];
-		f->pool[i & 3] = (w >> 3) ^ twist_table[w & 7];
-		input_rotate += (i++ & 3) ? 7 : 14;
-	}
-	f->count = i;
+	w = rol32(input[0], input_rotate) ^ f->pool[0] ^ f->pool[3];
+	f->pool[0] = (w >> 3) ^ twist_table[w & 7];
+	input_rotate = (input_rotate + 14) & 31;
+	w = rol32(input[1], input_rotate) ^ f->pool[1] ^ f->pool[0];
+	f->pool[1] = (w >> 3) ^ twist_table[w & 7];
+	input_rotate = (input_rotate + 7) & 31;
+	w = rol32(input[2], input_rotate) ^ f->pool[2] ^ f->pool[1];
+	f->pool[2] = (w >> 3) ^ twist_table[w & 7];
+	input_rotate = (input_rotate + 7) & 31;
+	w = rol32(input[3], input_rotate) ^ f->pool[3] ^ f->pool[2];
+	f->pool[3] = (w >> 3) ^ twist_table[w & 7];
+	input_rotate = (input_rotate + 7) & 31;
+
 	f->rotate = input_rotate;
+	f->count++;
 }
 
 /*
@@ -836,10 +841,9 @@ void add_interrupt_randomness(int irq, int irq_flags)
 		input[3] = ip >> 32;
 	}
 
-	fast_mix(fast_pool, input, sizeof(input));
+	fast_mix(fast_pool, input);
 
-	if ((fast_pool->count & 1023) &&
-	    !time_after(now, fast_pool->last + HZ))
+	if ((fast_pool->count & 63) && !time_after(now, fast_pool->last + HZ))
 		return;
 
 	fast_pool->last = now;
-- 
1.7.12.rc0.22.gcdd159b

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/