[PATCH 1/10] random pt2: cleanup waitqueue logic, fix missed wakeup

[PATCH 1/10] random pt2: cleanup waitqueue logic, fix missed wakeup

[Matt Mackall]

Original code checked in output pool for missed wakeup avoidance,
while waker (batch_entropy_process) checked input pool which could
result in a missed wakeup.

Move to wait_event_interruptible style
Delete superfluous waitqueue

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:27:58.178748133 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:27:58.951649596 -0800
@@ -1587,7 +1587,6 @@
 static ssize_t
 random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos)
 {
-	DECLARE_WAITQUEUE(wait, current);
 	ssize_t n, retval = 0, count = 0;
 
 	if (nbytes == 0)
@@ -1613,20 +1612,20 @@
 				retval = -EAGAIN;
 				break;
 			}
+
+			DEBUG_ENT("sleeping?\n");
+
+			wait_event_interruptible(random_read_wait,
+				random_state->entropy_count >=
+						 random_read_wakeup_thresh);
+
+			DEBUG_ENT("awake\n");
+
 			if (signal_pending(current)) {
 				retval = -ERESTARTSYS;
 				break;
 			}
 
-			set_current_state(TASK_INTERRUPTIBLE);
-			add_wait_queue(&random_read_wait, &wait);
-
-			if (sec_random_state->entropy_count / 8 == 0)
-				schedule();
-
-			set_current_state(TASK_RUNNING);
-			remove_wait_queue(&random_read_wait, &wait);
-
 			continue;
 		}
 

[PATCH 2/10] random pt2: kill pool clearing

[Matt Mackall]

Remove pool clearing. We've only ever cleared one of three pools and
there's no good reason to do it. Instead just reset the entropy count.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:27:58.951649596 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:28:00.196490892 -0800
@@ -546,15 +546,6 @@
 	return 0;
 }
 
-/* Clear the entropy pool and associated counters. */
-static void clear_entropy_store(struct entropy_store *r)
-{
-	r->add_ptr = 0;
-	r->entropy_count = 0;
-	r->input_rotate = 0;
-	memset(r->pool, 0, r->poolinfo.POOLBYTES);
-}
-
 /*
  * This function adds a byte into the entropy "pool".  It does not
  * update the entropy estimate.  The caller should call
@@ -1531,9 +1522,6 @@
 	if (create_entropy_store(SECONDARY_POOL_SIZE, "urandom",
 				 &urandom_state))
 		goto err;
-	clear_entropy_store(random_state);
-	clear_entropy_store(sec_random_state);
-	clear_entropy_store(urandom_state);
 	init_std_data(random_state);
 	init_std_data(sec_random_state);
 	init_std_data(urandom_state);
@@ -1765,10 +1753,10 @@
 		random_state->entropy_count = 0;
 		return 0;
 	case RNDCLEARPOOL:
-		/* Clear the entropy pool and associated counters. */
+		/* Clear the entropy pool counters. */
 		if (!capable(CAP_SYS_ADMIN))
 			return -EPERM;
-		clear_entropy_store(random_state);
+		random_state->entropy_count = 0;
 		init_std_data(random_state);
 		return 0;
 	default:

[PATCH 4/10] random pt2: re-init all pools on zero

[Matt Mackall]

Re-init all three pools in ioctls
Clear entropy count in init_std_data under a lock
Add kerneldoc comment

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:28:01.110374382 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:28:02.593185340 -0800
@@ -1473,16 +1473,14 @@
 
 EXPORT_SYMBOL(get_random_bytes);
 
-/*********************************************************************
- *
- * Functions to interface with Linux
- *
- *********************************************************************/
-
 /*
- * Initialize the random pool with standard stuff.
+ * init_std_data - initialize pool with system data
  *
- * NOTE: This is an OS-dependent function.
+ * @r: pool to initialize
+ *
+ * This function clears the pool's entropy count and mixes some system
+ * data into the pool to prepare it for use. The pool is not cleared
+ * as that can only decrease the entropy in the pool.
  */
 static void init_std_data(struct entropy_store *r)
 {
@@ -1490,6 +1488,11 @@
 	__u32 words[2];
 	char *p;
 	int i;
+	unsigned long flags;
+
+	spin_lock_irqsave(&r->lock, flags);
+	r->entropy_count = 0;
+	spin_unlock_irqrestore(&r->lock, flags);
 
 	do_gettimeofday(&tv);
 	words[0] = tv.tv_sec;
@@ -1752,8 +1755,9 @@
 		/* Clear the entropy pool counters. */
 		if (!capable(CAP_SYS_ADMIN))
 			return -EPERM;
-		random_state->entropy_count = 0;
 		init_std_data(random_state);
+		init_std_data(sec_random_state);
+		init_std_data(urandom_state);
 		return 0;
 	default:
 		return -EINVAL;

[PATCH 3/10] random pt2: combine legacy ioctls

[Matt Mackall]

ZAPENTCNT is now effectively identical to RNDCLEARPOOL, fall through

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:28:00.196490892 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:28:01.110374382 -0800
@@ -1748,10 +1748,6 @@
 			wake_up_interruptible(&random_read_wait);
 		return 0;
 	case RNDZAPENTCNT:
-		if (!capable(CAP_SYS_ADMIN))
-			return -EPERM;
-		random_state->entropy_count = 0;
-		return 0;
 	case RNDCLEARPOOL:
 		/* Clear the entropy pool counters. */
 		if (!capable(CAP_SYS_ADMIN))

[PATCH 8/10] random pt2: kill 2.2 compat waitqueue defs

[Matt Mackall]

Remove Linux 2.2 compatibility cruft.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:28:05.741783928 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:28:06.993624332 -0800
@@ -380,16 +380,6 @@
  */
 
 /*
- * Linux 2.2 compatibility
- */
-#ifndef DECLARE_WAITQUEUE
-#define DECLARE_WAITQUEUE(WAIT, PTR) struct wait_queue WAIT = { PTR, NULL }
-#endif
-#ifndef DECLARE_WAIT_QUEUE_HEAD
-#define DECLARE_WAIT_QUEUE_HEAD(WAIT) struct wait_queue *WAIT
-#endif
-
-/*
  * Static global variables
  */
 static struct entropy_store *random_state; /* The default global store */

[PATCH 6/10] random pt2: kill memsets of static data

[Matt Mackall]

Remove redundant memsets of BSS data

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:28:03.909017586 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:28:04.834899546 -0800
@@ -1499,8 +1499,6 @@
 
 static int __init rand_initialize(void)
 {
-	int i;
-
 	if (create_entropy_store(DEFAULT_POOL_SIZE, "primary", &random_state))
 		goto err;
 	if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state))
@@ -1517,10 +1515,6 @@
 #ifdef CONFIG_SYSCTL
 	sysctl_init_random(random_state);
 #endif
-	for (i = 0; i < NR_IRQS; i++)
-		irq_timer_state[i] = NULL;
-	memset(&input_timer_state, 0, sizeof(struct timer_rand_state));
-	memset(&extract_timer_state, 0, sizeof(struct timer_rand_state));
 	extract_timer_state.dont_count_entropy = 1;
 	return 0;
 err:

[PATCH 5/10] random pt2: simplify initialization

[Matt Mackall]

Simplify the init code

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:28:02.593185340 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:28:03.909017586 -0800
@@ -1485,9 +1485,6 @@
 static void init_std_data(struct entropy_store *r)
 {
 	struct timeval tv;
-	__u32 words[2];
-	char *p;
-	int i;
 	unsigned long flags;
 
 	spin_lock_irqsave(&r->lock, flags);
@@ -1495,20 +1492,9 @@
 	spin_unlock_irqrestore(&r->lock, flags);
 
 	do_gettimeofday(&tv);
-	words[0] = tv.tv_sec;
-	words[1] = tv.tv_usec;
-	add_entropy_words(r, words, 2);
-
-	/*
-	 *	This doesn't lock system.utsname. However, we are generating
-	 *	entropy so a race with a name set here is fine.
-	 */
-	p = (char *) &system_utsname;
-	for (i = sizeof(system_utsname) / sizeof(words); i; i--) {
-		memcpy(words, p, sizeof(words));
-		add_entropy_words(r, words, sizeof(words)/4);
-		p += sizeof(words);
-	}
+	add_entropy_words(r, (__u32 *)&tv, sizeof(tv)/4);
+	add_entropy_words(r, (__u32 *)&system_utsname,
+			  sizeof(system_utsname)/4);
 }
 
 static int __init rand_initialize(void)

[PATCH 7/10] random pt2: kill dead extract_state struct

[Matt Mackall]

Remove unused extract_timer_state struct. It was formerly used to
feedback zero-entropy timing samples while extracting entropy, but
that had a tendency to overwhelm the batch processing queue and
prevent storing real samples.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:28:04.834899546 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:28:05.741783928 -0800
@@ -777,7 +777,6 @@
 };
 
 static struct timer_rand_state input_timer_state;
-static struct timer_rand_state extract_timer_state;
 static struct timer_rand_state *irq_timer_state[NR_IRQS];
 
 /*
@@ -1515,7 +1514,6 @@
 #ifdef CONFIG_SYSCTL
 	sysctl_init_random(random_state);
 #endif
-	extract_timer_state.dont_count_entropy = 1;
 	return 0;
 err:
 	return -1;

[PATCH 9/10] random pt2: kill redundant rotate_left definitions

[Matt Mackall]

We've got three definitions of rotate_left. Remove x86 and duplicate
rotate definitions. Remaining definition is fixed up such that recent
gcc will generate rol instructions on x86 at least.

A later patch will move this to bitops and clean up the other tree users.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:28:06.993624332 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:28:07.768525540 -0800
@@ -401,26 +401,10 @@
  * purposes
  *
  *****************************************************************/
-
-/*
- * Unfortunately, while the GCC optimizer for the i386 understands how
- * to optimize a static rotate left of x bits, it doesn't know how to
- * deal with a variable rotate of x bits.  So we use a bit of asm magic.
- */
-#if (!defined (__i386__))
-static inline __u32 rotate_left(int i, __u32 word)
-{
-	return (word << i) | (word >> (32 - i));
-}
-#else
-static inline __u32 rotate_left(int i, __u32 word)
+static inline __u32 rol32(__u32 word, int shift)
 {
-	__asm__("roll %%cl,%0"
-		:"=r" (word)
-		:"0" (word),"c" (i));
-	return word;
+	return (word << shift) | (word >> (32 - shift));
 }
-#endif
 
 /*
  * More asm magic....
@@ -572,7 +556,7 @@
 	add_ptr = r->add_ptr;
 
 	while (nwords--) {
-		w = rotate_left(input_rotate, next_w);
+		w = rol32(input_rotate, next_w);
 		if (nwords > 0)
 			next_w = *in++;
 		i = add_ptr = (add_ptr - 1) & wordmask;
@@ -941,10 +925,8 @@
 #define K3  0x8F1BBCDCL			/* Rounds 40-59: sqrt(5) * 2^30 */
 #define K4  0xCA62C1D6L			/* Rounds 60-79: sqrt(10) * 2^30 */
 
-#define ROTL(n,X)  (((X) << n ) | ((X) >> (32 - n)))
-
 #define subRound(a, b, c, d, e, f, k, data) \
-    (e += ROTL(5, a) + f(b, c, d) + k + data, b = ROTL(30, b))
+    (e += rol32(a, 5) + f(b, c, d) + k + data, b = rol32(b, 30))
 
 static void SHATransform(__u32 digest[85], __u32 const data[16])
 {
@@ -962,7 +944,7 @@
 	memcpy(W, data, 16*sizeof(__u32));
 	for (i = 0; i < 64; i++) {
 		TEMP = W[i] ^ W[i+2] ^ W[i+8] ^ W[i+13];
-		W[i+16] = ROTL(1, TEMP);
+		W[i+16] = rol32(TEMP, 1);
 	}
 
 	/* Set up first buffer and local data buffer */
@@ -990,25 +972,25 @@
 			else
 				TEMP = f4(B, C, D) + K4;
 		}
-		TEMP += ROTL(5, A) + E + W[i];
-		E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
+		TEMP += rol32(A, 5) + E + W[i];
+		E = D; D = C; C = rol32(B, 30); B = A; A = TEMP;
 	}
 #elif SHA_CODE_SIZE == 1
 	for (i = 0; i < 20; i++) {
-		TEMP = f1(B, C, D) + K1 + ROTL(5, A) + E + W[i];
-		E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
+		TEMP = f1(B, C, D) + K1 + rol32(A, 5) + E + W[i];
+		E = D; D = C; C = rol32(B, 30); B = A; A = TEMP;
 	}
 	for (; i < 40; i++) {
-		TEMP = f2(B, C, D) + K2 + ROTL(5, A) + E + W[i];
-		E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
+		TEMP = f2(B, C, D) + K2 + rol32(A, 5) + E + W[i];
+		E = D; D = C; C = rol32(B, 30); B = A; A = TEMP;
 	}
 	for (; i < 60; i++) {
-		TEMP = f3(B, C, D) + K3 + ROTL(5, A) + E + W[i];
-		E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
+		TEMP = f3(B, C, D) + K3 + rol32(A, 5) + E + W[i];
+		E = D; D = C; C = rol22(B, 30); B = A; A = TEMP;
 	}
 	for (; i < 80; i++) {
-		TEMP = f4(B, C, D) + K4 + ROTL(5, A) + E + W[i];
-		E = D; D = C; C = ROTL(30, B); B = A; A = TEMP;
+		TEMP = f4(B, C, D) + K4 + rol32(A, 5) + E + W[i];
+		E = D; D = C; C = rol32(B, 30); B = A; A = TEMP;
 	}
 #elif SHA_CODE_SIZE == 2
 	for (i = 0; i < 20; i += 5) {
@@ -1138,7 +1120,6 @@
 #undef W
 }
 
-#undef ROTL
 #undef f1
 #undef f2
 #undef f3

[PATCH 10/10] random pt2: kill misnamed log2

[Matt Mackall]

Remove incorrectly named ln (it's log2!) and x86 asm function and
replace with fls bitop.

Signed-off-by: Matt Mackall <mpm@selenic.com>

Index: rnd/drivers/char/random.c
===================================================================
--- rnd.orig/drivers/char/random.c	2005-01-12 21:28:07.768525540 -0800
+++ rnd/drivers/char/random.c	2005-01-12 21:28:08.700406735 -0800
@@ -395,54 +395,11 @@
 static void sysctl_init_random(struct entropy_store *random_state);
 #endif
 
-/*****************************************************************
- *
- * Utility functions, with some ASM defined functions for speed
- * purposes
- *
- *****************************************************************/
 static inline __u32 rol32(__u32 word, int shift)
 {
 	return (word << shift) | (word >> (32 - shift));
 }
 
-/*
- * More asm magic....
- *
- * For entropy estimation, we need to do an integral base 2
- * logarithm.
- *
- * Note the "12bits" suffix - this is used for numbers between
- * 0 and 4095 only.  This allows a few shortcuts.
- */
-#if 0	/* Slow but clear version */
-static inline __u32 int_ln_12bits(__u32 word)
-{
-	__u32 nbits = 0;
-
-	while (word >>= 1)
-		nbits++;
-	return nbits;
-}
-#else	/* Faster (more clever) version, courtesy Colin Plumb */
-static inline __u32 int_ln_12bits(__u32 word)
-{
-	/* Smear msbit right to make an n-bit mask */
-	word |= word >> 8;
-	word |= word >> 4;
-	word |= word >> 2;
-	word |= word >> 1;
-	/* Remove one bit to make this a logarithm */
-	word >>= 1;
-	/* Count the bits set in the word */
-	word -= (word >> 1) & 0x555;
-	word = (word & 0x333) + ((word >> 2) & 0x333);
-	word += (word >> 4);
-	word += (word >> 8);
-	return word & 15;
-}
-#endif
-
 #if 0
 static int debug = 0;
 module_param(debug, bool, 0644);
@@ -808,10 +765,7 @@
 		 * Round down by 1 bit on general principles,
 		 * and limit entropy entimate to 12 bits.
 		 */
-		delta >>= 1;
-		delta &= (1 << 12) - 1;
-
-		entropy = int_ln_12bits(delta);
+		entropy = min_t(int, fls(delta>>1), 11);
 	}
 
 	/*