[PATCH 0/22] /dev/random: Assorted fixes and cleanups

[PATCH 0/22] /dev/random: Assorted fixes and cleanups

[Matt Mackall]

This is a collection of fixes and cleanups for the Linux /dev/random
driver including:

- more robust/correct entropy accounting and reseed logic
- starvation avoidance for simultaneous /dev/random and /dev/urandom
  users
- remove entropy batching
- wakeup bug fix
- remove various legacy code
- remove i386isms

I've broken this into a bunch of very simple bits, so I'm afraid the
patch count is rather high by non-gregkh standards.

These patches have been tested by various people since pre-2.6.0 and
have been in my -tiny tree since its inception. Andrew, please queue
these in -mm for wider testing/review.

[PATCH 2/22] /dev/random: Cleanup sleep logic

[Matt Mackall]

Cleanup /dev/random sleep logic

Original code checked in output pool rather than input pool for wakeup
Move to wait_event_interruptible style
Delete superfluous waitqueue


 tiny-mpm/drivers/char/random.c |   23 +++++++++++------------
 1 files changed, 11 insertions(+), 12 deletions(-)

diff -puN drivers/char/random.c~fix-random-wait drivers/char/random.c
--- tiny/drivers/char/random.c~fix-random-wait	2004-03-20 13:35:06.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:35:06.000000000 -0600
@@ -1556,9 +1556,8 @@ void rand_initialize_disk(struct gendisk
 static ssize_t
 random_read(struct file * file, char * buf, size_t nbytes, loff_t *ppos)
 {
-	DECLARE_WAITQUEUE(wait, current);
-	ssize_t			n, retval = 0, count = 0;
-	
+	ssize_t	n, retval = 0, count = 0;
+
 	if (nbytes == 0)
 		return 0;
 
@@ -1582,20 +1581,20 @@ random_read(struct file * file, char * b
 				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 4/22] /dev/random: remove outdated RNDGETPOOL ioctl

[Matt Mackall]

/dev/random  remove outdated RNDGETPOOL ioctl

Remove RNDGETPOOL ioctl, which has outlived its usefulness for
debugging as it only atomically captures the state of one pool.
There's no other value (except to attackers) of direct access to the
input pool from userspace.


 tiny-mpm/drivers/char/random.c        |   40 +---------------------------------
 tiny-mpm/include/linux/compat_ioctl.h |    1 
 tiny-mpm/include/linux/random.h       |    5 ----
 3 files changed, 3 insertions(+), 43 deletions(-)

diff -puN drivers/char/random.c~kill-getstate drivers/char/random.c
--- tiny/drivers/char/random.c~kill-getstate	2004-03-20 13:38:12.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:12.000000000 -0600
@@ -1671,10 +1671,9 @@ static int
 random_ioctl(struct inode * inode, struct file * file,
 	     unsigned int cmd, unsigned long arg)
 {
-	int *p, *tmp, size, ent_count;
+	int *p, size, ent_count;
 	int retval;
-	unsigned long flags;
-	
+
 	switch (cmd) {
 	case RNDGETENTCNT:
 		ent_count = random_state->entropy_count;
@@ -1694,41 +1693,6 @@ random_ioctl(struct inode * inode, struc
 		if (random_state->entropy_count >= random_read_wakeup_thresh)
 			wake_up_interruptible(&random_read_wait);
 		return 0;
-	case RNDGETPOOL:
-		if (!capable(CAP_SYS_ADMIN))
-			return -EPERM;
-		p = (int *) arg;
-		if (get_user(size, p) ||
-		    put_user(random_state->poolinfo.poolwords, p++))
-			return -EFAULT;
-		if (size < 0)
-			return -EFAULT;
-		if (size > random_state->poolinfo.poolwords)
-			size = random_state->poolinfo.poolwords;
-
-		/* prepare to atomically snapshot pool */
-
-		tmp = kmalloc(size * sizeof(__u32), GFP_KERNEL);
-
-		if (!tmp)
-			return -ENOMEM;
-
-		spin_lock_irqsave(&random_state->lock, flags);
-		ent_count = random_state->entropy_count;
-		memcpy(tmp, random_state->pool, size * sizeof(__u32));
-		spin_unlock_irqrestore(&random_state->lock, flags);
-
-		if (!copy_to_user(p, tmp, size * sizeof(__u32))) {
-			kfree(tmp);
-			return -EFAULT;
-		}
-
-		kfree(tmp);
-
-		if(put_user(ent_count, p++))
-			return -EFAULT;
-
-		return 0;
 	case RNDADDENTROPY:
 		if (!capable(CAP_SYS_ADMIN))
 			return -EPERM;
diff -puN include/linux/compat_ioctl.h~kill-getstate include/linux/compat_ioctl.h
--- tiny/include/linux/compat_ioctl.h~kill-getstate	2004-03-20 13:38:12.000000000 -0600
+++ tiny-mpm/include/linux/compat_ioctl.h	2004-03-20 13:38:12.000000000 -0600
@@ -584,7 +584,6 @@ COMPATIBLE_IOCTL(WDIOC_KEEPALIVE)
 /* Big R */
 COMPATIBLE_IOCTL(RNDGETENTCNT)
 COMPATIBLE_IOCTL(RNDADDTOENTCNT)
-COMPATIBLE_IOCTL(RNDGETPOOL)
 COMPATIBLE_IOCTL(RNDADDENTROPY)
 COMPATIBLE_IOCTL(RNDZAPENTCNT)
 COMPATIBLE_IOCTL(RNDCLEARPOOL)
diff -puN include/linux/random.h~kill-getstate include/linux/random.h
--- tiny/include/linux/random.h~kill-getstate	2004-03-20 13:38:12.000000000 -0600
+++ tiny-mpm/include/linux/random.h	2004-03-20 13:38:12.000000000 -0600
@@ -17,10 +17,7 @@
 /* Add to (or subtract from) the entropy count.  (Superuser only.) */
 #define RNDADDTOENTCNT	_IOW( 'R', 0x01, int )
 
-/* Get the contents of the entropy pool.  (Superuser only.) */
-#define RNDGETPOOL	_IOR( 'R', 0x02, int [2] )
-
-/* 
+/*
  * Write bytes into the entropy pool and add to the entropy count.
  * (Superuser only.)
  */

_

[PATCH 1/22] /dev/random: Simplify entropy debugging

[Matt Mackall]

Simplify entropy debugging



 tiny-mpm/drivers/char/random.c |   47 ++++++++---------------------------------
 1 files changed, 10 insertions(+), 37 deletions(-)

diff -puN drivers/char/random.c~debug-cleanup drivers/char/random.c
--- tiny/drivers/char/random.c~debug-cleanup	2004-03-13 13:00:13.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-13 13:00:13.000000000 -0600
@@ -477,7 +477,10 @@ static inline __u32 int_ln_12bits(__u32 
 #endif
 
 #if 0
-#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random: " fmt, ## arg)
+#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random %04d %04d: " fmt,\
+	random_state->entropy_count,\
+	sec_random_state->entropy_count,\
+	## arg)
 #else
 #define DEBUG_ENT(fmt, arg...) do {} while (0)
 #endif
@@ -624,9 +627,7 @@ static void credit_entropy_store(struct 
 	} else {
 		r->entropy_count += nbits;
 		if (nbits)
-			DEBUG_ENT("%04d %04d : added %d bits to %s\n",
-				  random_state->entropy_count,
-				  sec_random_state->entropy_count,
+			DEBUG_ENT("added %d bits to %s\n",
 				  nbits,
 				  r == sec_random_state ? "secondary" :
 				  r == random_state ? "primary" : "unknown");
@@ -1300,10 +1301,8 @@ static inline void xfer_secondary_pool(s
 		int bytes = max_t(int, random_read_wakeup_thresh / 8,
 				min_t(int, nbytes, TMP_BUF_SIZE));
 
-		DEBUG_ENT("%04d %04d : going to reseed %s with %d bits "
+		DEBUG_ENT("going to reseed %s with %d bits "
 			  "(%d of %d requested)\n",
-			  random_state->entropy_count,
-			  sec_random_state->entropy_count,
 			  r == sec_random_state ? "secondary" : "unknown",
 			  bytes * 8, nbytes * 8, r->entropy_count);
 
@@ -1346,9 +1345,7 @@ static ssize_t extract_entropy(struct en
 	/* Hold lock while accounting */
 	spin_lock_irqsave(&r->lock, cpuflags);
 
-	DEBUG_ENT("%04d %04d : trying to extract %d bits from %s\n",
-		  random_state->entropy_count,
-		  sec_random_state->entropy_count,
+	DEBUG_ENT("trying to extract %d bits from %s\n",
 		  nbytes * 8,
 		  r == sec_random_state ? "secondary" :
 		  r == random_state ? "primary" : "unknown");
@@ -1364,9 +1361,7 @@ static ssize_t extract_entropy(struct en
 	if (r->entropy_count < random_write_wakeup_thresh)
 		wake_up_interruptible(&random_write_wait);
 
-	DEBUG_ENT("%04d %04d : debiting %d bits from %s%s\n",
-		  random_state->entropy_count,
-		  sec_random_state->entropy_count,
+	DEBUG_ENT("debiting %d bits from %s%s\n",
 		  nbytes * 8,
 		  r == sec_random_state ? "secondary" :
 		  r == random_state ? "primary" : "unknown",
@@ -1386,15 +1381,7 @@ static ssize_t extract_entropy(struct en
 				break;
 			}
 
-			DEBUG_ENT("%04d %04d : extract feeling sleepy (%d bytes left)\n",
-				  random_state->entropy_count,
-				  sec_random_state->entropy_count, nbytes);
-
 			schedule();
-
-			DEBUG_ENT("%04d %04d : extract woke up\n",
-				  random_state->entropy_count,
-				  sec_random_state->entropy_count);
 		}
 
 		/* Hash the pool to get the output */
@@ -1580,20 +1567,14 @@ random_read(struct file * file, char * b
 		if (n > SEC_XFER_SIZE)
 			n = SEC_XFER_SIZE;
 
-		DEBUG_ENT("%04d %04d : reading %d bits, p: %d s: %d\n",
-			  random_state->entropy_count,
-			  sec_random_state->entropy_count,
-			  n*8, random_state->entropy_count,
-			  sec_random_state->entropy_count);
+		DEBUG_ENT("reading %d bits\n", n*8);
 
 		n = extract_entropy(sec_random_state, buf, n,
 				    EXTRACT_ENTROPY_USER |
 				    EXTRACT_ENTROPY_LIMIT |
 				    EXTRACT_ENTROPY_SECONDARY);
 
-		DEBUG_ENT("%04d %04d : read got %d bits (%d still needed)\n",
-			  random_state->entropy_count,
-			  sec_random_state->entropy_count,
+		DEBUG_ENT("read got %d bits (%d still needed)\n",
 			  n*8, (nbytes-n)*8);
 
 		if (n == 0) {
@@ -1606,10 +1587,6 @@ random_read(struct file * file, char * b
 				break;
 			}
 
-			DEBUG_ENT("%04d %04d : sleeping?\n",
-				  random_state->entropy_count,
-				  sec_random_state->entropy_count);
-
 			set_current_state(TASK_INTERRUPTIBLE);
 			add_wait_queue(&random_read_wait, &wait);
 
@@ -1619,10 +1596,6 @@ random_read(struct file * file, char * b
 			set_current_state(TASK_RUNNING);
 			remove_wait_queue(&random_read_wait, &wait);
 
-			DEBUG_ENT("%04d %04d : waking up\n",
-				  random_state->entropy_count,
-				  sec_random_state->entropy_count);
-
 			continue;
 		}
 

_

[PATCH 3/22] /dev/random: remove broken resizing sysctl

[Matt Mackall]

/dev/random  remove broken resizing sysctl

Remove random pool resizing sysctl. It's racy in hard to fix ways and
doesn't really warrant fixing. 4kbits (512 bytes) of entropy pool
should be more than big enough and too small to be a memory concern.
It also doesn't adjust the other pool size(s).



 tiny-mpm/drivers/char/random.c  |   88 +---------------------------------------
 tiny-mpm/include/linux/sysctl.h |    1 
 2 files changed, 3 insertions(+), 86 deletions(-)

diff -puN drivers/char/random.c~kill-pool-resize drivers/char/random.c
--- tiny/drivers/char/random.c~kill-pool-resize	2004-03-20 13:35:17.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:35:17.000000000 -0600
@@ -550,14 +550,7 @@ static void clear_entropy_store(struct e
 	r->input_rotate = 0;
 	memset(r->pool, 0, r->poolinfo.POOLBYTES);
 }
-#ifdef CONFIG_SYSCTL
-static void free_entropy_store(struct entropy_store *r)
-{
-	if (r->pool)
-		kfree(r->pool);
-	kfree(r);
-}
-#endif
+
 /*
  * This function adds a byte into the entropy "pool".  It does not
  * update the entropy estimate.  The caller should call
@@ -1819,78 +1812,12 @@ EXPORT_SYMBOL(generate_random_uuid);
 
 #include <linux/sysctl.h>
 
-static int sysctl_poolsize;
 static int min_read_thresh, max_read_thresh;
 static int min_write_thresh, max_write_thresh;
 static char sysctl_bootid[16];
 
 /*
- * This function handles a request from the user to change the pool size 
- * of the primary entropy store.
- */
-static int change_poolsize(int poolsize)
-{
-	struct entropy_store	*new_store, *old_store;
-	int			ret;
-	
-	if ((ret = create_entropy_store(poolsize, &new_store)))
-		return ret;
-
-	add_entropy_words(new_store, random_state->pool,
-			  random_state->poolinfo.poolwords);
-	credit_entropy_store(new_store, random_state->entropy_count);
-
-	sysctl_init_random(new_store);
-	old_store = random_state;
-	random_state = batch_work.data = new_store;
-	free_entropy_store(old_store);
-	return 0;
-}
-
-static int proc_do_poolsize(ctl_table *table, int write, struct file *filp,
-			    void *buffer, size_t *lenp)
-{
-	int	ret;
-
-	sysctl_poolsize = random_state->poolinfo.POOLBYTES;
-
-	ret = proc_dointvec(table, write, filp, buffer, lenp);
-	if (ret || !write ||
-	    (sysctl_poolsize == random_state->poolinfo.POOLBYTES))
-		return ret;
-
-	return change_poolsize(sysctl_poolsize);
-}
-
-static int poolsize_strategy(ctl_table *table, int *name, int nlen,
-			     void *oldval, size_t *oldlenp,
-			     void *newval, size_t newlen, void **context)
-{
-	int	len;
-	
-	sysctl_poolsize = random_state->poolinfo.POOLBYTES;
-
-	/*
-	 * We only handle the write case, since the read case gets
-	 * handled by the default handler (and we don't care if the
-	 * write case happens twice; it's harmless).
-	 */
-	if (newval && newlen) {
-		len = newlen;
-		if (len > table->maxlen)
-			len = table->maxlen;
-		if (copy_from_user(table->data, newval, len))
-			return -EFAULT;
-	}
-
-	if (sysctl_poolsize != random_state->poolinfo.POOLBYTES)
-		return change_poolsize(sysctl_poolsize);
-
-	return 0;
-}
-
-/*
- * These functions is used to return both the bootid UUID, and random
+ * These functions are used to return both the bootid UUID, and random
  * UUID.  The difference is in whether table->data is NULL; if it is,
  * then a new UUID is generated and returned to the user.
  * 
@@ -1956,15 +1883,6 @@ static int uuid_strategy(ctl_table *tabl
 
 ctl_table random_table[] = {
 	{
-		.ctl_name	= RANDOM_POOLSIZE,
-		.procname	= "poolsize",
-		.data		= &sysctl_poolsize,
-		.maxlen		= sizeof(int),
-		.mode		= 0644,
-		.proc_handler	= &proc_do_poolsize,
-		.strategy	= &poolsize_strategy,
-	},
-	{
 		.ctl_name	= RANDOM_ENTROPY_COUNT,
 		.procname	= "entropy_avail",
 		.maxlen		= sizeof(int),
@@ -2018,7 +1936,7 @@ static void sysctl_init_random(struct en
 	min_read_thresh = 8;
 	min_write_thresh = 0;
 	max_read_thresh = max_write_thresh = random_state->poolinfo.POOLBITS;
-	random_table[1].data = &random_state->entropy_count;
+	random_table[0].data = &random_state->entropy_count;
 }
 #endif 	/* CONFIG_SYSCTL */
 
diff -puN include/linux/sysctl.h~kill-pool-resize include/linux/sysctl.h
--- tiny/include/linux/sysctl.h~kill-pool-resize	2004-03-20 13:35:17.000000000 -0600
+++ tiny-mpm/include/linux/sysctl.h	2004-03-20 13:35:17.000000000 -0600
@@ -188,7 +188,6 @@ enum
 /* /proc/sys/kernel/random */
 enum
 {
-	RANDOM_POOLSIZE=1,
 	RANDOM_ENTROPY_COUNT=2,
 	RANDOM_READ_THRESH=3,
 	RANDOM_WRITE_THRESH=4,

_

[PATCH 6/22] /dev/random: simplify pool initialization

[Matt Mackall]

/dev/random  simplify pool initialization


 tiny-mpm/drivers/char/random.c |   86 ++++++++++++++++-------------------------
 1 files changed, 35 insertions(+), 51 deletions(-)

diff -puN drivers/char/random.c~pool-init drivers/char/random.c
--- tiny/drivers/char/random.c~pool-init	2004-03-20 13:38:19.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:19.000000000 -0600
@@ -497,19 +497,12 @@ struct entropy_store {
 	unsigned add_ptr;
 	int entropy_count;
 	int input_rotate;
-	struct poolinfo poolinfo;
-	__u32 *pool;
+	struct poolinfo *poolinfo;
 	spinlock_t lock;
+	__u32 pool[0];
 };
 
-/*
- * Initialize the entropy store.  The input argument is the size of
- * the random pool.
- *
- * Returns an negative error if there is a problem.
- */
-static int create_entropy_store(int size, const char *name,
-				struct entropy_store **ret_bucket)
+static struct entropy_store *create_entropy_store(int size, const char *name)
 {
 	struct	entropy_store	*r;
 	struct	poolinfo	*p;
@@ -524,25 +517,18 @@ static int create_entropy_store(int size
 			break;
 	}
 	if (p->poolwords == 0)
-		return -EINVAL;
+		return 0;
 
-	r = kmalloc(sizeof(struct entropy_store), GFP_KERNEL);
+	r = kmalloc(sizeof(struct entropy_store)+POOLBYTES, GFP_KERNEL);
 	if (!r)
-		return -ENOMEM;
+		return 0;
 
-	memset (r, 0, sizeof(struct entropy_store));
-	r->poolinfo = *p;
+	memset(r, 0, sizeof(struct entropy_store));
+	r->poolinfo = p;
 	r->name = name;
-
-	r->pool = kmalloc(POOLBYTES, GFP_KERNEL);
-	if (!r->pool) {
-		kfree(r);
-		return -ENOMEM;
-	}
-	memset(r->pool, 0, POOLBYTES);
 	r->lock = SPIN_LOCK_UNLOCKED;
-	*ret_bucket = r;
-	return 0;
+
+	return r;
 }
 
 /* Clear the entropy pool and associated counters. */
@@ -551,11 +537,11 @@ static void clear_entropy_store(struct e
 	r->add_ptr = 0;
 	r->entropy_count = 0;
 	r->input_rotate = 0;
-	memset(r->pool, 0, r->poolinfo.POOLBYTES);
+	memset(r->pool, 0, r->poolinfo->POOLBYTES);
 }
 
 /*
- * This function adds a byte into the entropy "pool".  It does not
+ * This function adds words into the entropy "pool".  It does not
  * update the entropy estimate.  The caller should call
  * credit_entropy_store if this is appropriate.
  * 
@@ -572,7 +558,7 @@ static void add_entropy_words(struct ent
 		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
 	unsigned i;
 	int new_rotate;
-	int wordmask = r->poolinfo.poolwords - 1;
+	int wordmask = r->poolinfo->poolwords - 1;
 	__u32 w;
 	unsigned long flags;
 
@@ -593,11 +579,11 @@ static void add_entropy_words(struct ent
 		r->input_rotate = new_rotate & 31;
 
 		/* XOR in the various taps */
-		w ^= r->pool[(i + r->poolinfo.tap1) & wordmask];
-		w ^= r->pool[(i + r->poolinfo.tap2) & wordmask];
-		w ^= r->pool[(i + r->poolinfo.tap3) & wordmask];
-		w ^= r->pool[(i + r->poolinfo.tap4) & wordmask];
-		w ^= r->pool[(i + r->poolinfo.tap5) & wordmask];
+		w ^= r->pool[(i + r->poolinfo->tap1) & wordmask];
+		w ^= r->pool[(i + r->poolinfo->tap2) & wordmask];
+		w ^= r->pool[(i + r->poolinfo->tap3) & wordmask];
+		w ^= r->pool[(i + r->poolinfo->tap4) & wordmask];
+		w ^= r->pool[(i + r->poolinfo->tap5) & wordmask];
 		w ^= r->pool[i];
 		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
 	}
@@ -618,8 +604,8 @@ static void credit_entropy_store(struct 
 		DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
 			  r->entropy_count, nbits);
 		r->entropy_count = 0;
-	} else if (r->entropy_count + nbits > r->poolinfo.POOLBITS) {
-		r->entropy_count = r->poolinfo.POOLBITS;
+	} else if (r->entropy_count + nbits > r->poolinfo->POOLBITS) {
+		r->entropy_count = r->poolinfo->POOLBITS;
 	} else {
 		r->entropy_count += nbits;
 		if (nbits)
@@ -714,7 +700,7 @@ EXPORT_SYMBOL(batch_entropy_store);
 static void batch_entropy_process(void *private_)
 {
 	struct entropy_store *r	= (struct entropy_store *) private_, *p;
-	int max_entropy = r->poolinfo.POOLBITS;
+	int max_entropy = r->poolinfo->POOLBITS;
 	unsigned head, tail;
 
 	/* Mixing into the pool is expensive, so copy over the batch
@@ -738,7 +724,7 @@ static void batch_entropy_process(void *
 		if (r->entropy_count >= max_entropy) {
 			r = (r == blocking_pool) ? input_pool :
 							blocking_pool;
-			max_entropy = r->poolinfo.POOLBITS;
+			max_entropy = r->poolinfo->POOLBITS;
 		}
 		add_entropy_words(r, batch_entropy_copy[tail].data, 2);
 		credit_entropy_store(r, batch_entropy_copy[tail].credit);
@@ -1290,7 +1276,7 @@ static inline void xfer_secondary_pool(s
 				       size_t nbytes, __u32 *tmp)
 {
 	if (r->entropy_count < nbytes * 8 &&
-	    r->entropy_count < r->poolinfo.POOLBITS) {
+	    r->entropy_count < r->poolinfo->POOLBITS) {
 		int bytes = max_t(int, random_read_wakeup_thresh / 8,
 				min_t(int, nbytes, TMP_BUF_SIZE));
 
@@ -1328,8 +1314,8 @@ static ssize_t extract_entropy(struct en
 
 
 	/* Redundant, but just in case... */
-	if (r->entropy_count > r->poolinfo.POOLBITS)
-		r->entropy_count = r->poolinfo.POOLBITS;
+	if (r->entropy_count > r->poolinfo->POOLBITS)
+		r->entropy_count = r->poolinfo->POOLBITS;
 
 	if (flags & EXTRACT_ENTROPY_SECONDARY)
 		xfer_secondary_pool(r, nbytes, tmp);
@@ -1386,7 +1372,7 @@ static ssize_t extract_entropy(struct en
 		 * attempts to find previous ouputs), unless the hash
 		 * function can be inverted.
 		 */
-		for (i = 0, x = 0; i < r->poolinfo.poolwords; i += 16, x+=2) {
+		for (i = 0, x = 0; i < r->poolinfo->poolwords; i += 16, x+=2) {
 			HASH_TRANSFORM(tmp, r->pool+i);
 			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);
 		}
@@ -1482,15 +1468,15 @@ static int __init rand_initialize(void)
 {
 	int i;
 
-	if (create_entropy_store(INPUT_POOL_SIZE, "input", &input_pool))
-		goto err;
+	input_pool = create_entropy_store(INPUT_POOL_SIZE, "input");
+	blocking_pool = create_entropy_store(BLOCKING_POOL_SIZE, "blocking");
+
+	if (!(input_pool && blocking_pool))
+		return -1;
+
 	if (batch_entropy_init(BATCH_ENTROPY_SIZE, input_pool))
-		goto err;
-	if (create_entropy_store(BLOCKING_POOL_SIZE, "blocking",
-				 &blocking_pool))
-		goto err;
-	clear_entropy_store(input_pool);
-	clear_entropy_store(blocking_pool);
+		return -1;
+
 	init_std_data(input_pool);
 #ifdef CONFIG_SYSCTL
 	sysctl_init_random(input_pool);
@@ -1502,8 +1488,6 @@ static int __init rand_initialize(void)
 	memset(&extract_timer_state, 0, sizeof(struct timer_rand_state));
 	extract_timer_state.dont_count_entropy = 1;
 	return 0;
-err:
-	return -1;
 }
 module_init(rand_initialize);
 
@@ -1893,7 +1877,7 @@ static void sysctl_init_random(struct en
 {
 	min_read_thresh = 8;
 	min_write_thresh = 0;
-	max_read_thresh = max_write_thresh = pool->poolinfo.POOLBITS;
+	max_read_thresh = max_write_thresh = pool->poolinfo->POOLBITS;
 	random_table[0].data = &pool->entropy_count;
 }
 #endif 	/* CONFIG_SYSCTL */

_

[PATCH 5/22] /dev/random: pool struct cleanup and rename

[Matt Mackall]

/dev/random  pool struct cleanup and rename

Give pools more meaningful names and embed name field in pool struct.
Preparation for multiple output pools.


 tiny-mpm/drivers/char/random.c |  118 +++++++++++++++++++----------------------
 1 files changed, 56 insertions(+), 62 deletions(-)

diff -puN drivers/char/random.c~pool-rename drivers/char/random.c
--- tiny/drivers/char/random.c~pool-rename	2004-03-20 13:38:16.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:16.000000000 -0600
@@ -263,8 +263,8 @@
 /*
  * Configuration information
  */
-#define DEFAULT_POOL_SIZE 512
-#define SECONDARY_POOL_SIZE 128
+#define INPUT_POOL_SIZE 512
+#define BLOCKING_POOL_SIZE 128
 #define BATCH_ENTROPY_SIZE 256
 #define USE_SHA
 
@@ -286,7 +286,7 @@ static int random_write_wakeup_thresh = 
  * samples to avoid wasting CPU time and reduce lock contention.
  */
 
-static int trickle_thresh = DEFAULT_POOL_SIZE * 7;
+static int trickle_thresh = INPUT_POOL_SIZE * 7;
 
 static DEFINE_PER_CPU(int, trickle_count) = 0;
 
@@ -399,8 +399,8 @@ static struct poolinfo {
 /*
  * Static global variables
  */
-static struct entropy_store *random_state; /* The default global store */
-static struct entropy_store *sec_random_state; /* secondary store */
+static struct entropy_store *input_pool; /* The default global store */
+static struct entropy_store *blocking_pool; /* secondary store */
 static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
 static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
 
@@ -408,7 +408,7 @@ static DECLARE_WAIT_QUEUE_HEAD(random_wr
  * Forward procedure declarations
  */
 #ifdef CONFIG_SYSCTL
-static void sysctl_init_random(struct entropy_store *random_state);
+static void sysctl_init_random(struct entropy_store *pool);
 #endif
 
 /*****************************************************************
@@ -478,8 +478,8 @@ static inline __u32 int_ln_12bits(__u32 
 
 #if 0
 #define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random %04d %04d: " fmt,\
-	random_state->entropy_count,\
-	sec_random_state->entropy_count,\
+	input_pool->entropy_count,\
+	blocking_pool->entropy_count,\
 	## arg)
 #else
 #define DEBUG_ENT(fmt, arg...) do {} while (0)
@@ -493,11 +493,12 @@ static inline __u32 int_ln_12bits(__u32 
  **********************************************************************/
 
 struct entropy_store {
-	unsigned	add_ptr;
-	int		entropy_count;
-	int		input_rotate;
+	const char *name;
+	unsigned add_ptr;
+	int entropy_count;
+	int input_rotate;
 	struct poolinfo poolinfo;
-	__u32		*pool;
+	__u32 *pool;
 	spinlock_t lock;
 };
 
@@ -507,7 +508,8 @@ struct entropy_store {
  *
  * Returns an negative error if there is a problem.
  */
-static int create_entropy_store(int size, struct entropy_store **ret_bucket)
+static int create_entropy_store(int size, const char *name,
+				struct entropy_store **ret_bucket)
 {
 	struct	entropy_store	*r;
 	struct	poolinfo	*p;
@@ -530,6 +532,7 @@ static int create_entropy_store(int size
 
 	memset (r, 0, sizeof(struct entropy_store));
 	r->poolinfo = *p;
+	r->name = name;
 
 	r->pool = kmalloc(POOLBYTES, GFP_KERNEL);
 	if (!r->pool) {
@@ -620,10 +623,7 @@ static void credit_entropy_store(struct 
 	} else {
 		r->entropy_count += nbits;
 		if (nbits)
-			DEBUG_ENT("added %d bits to %s\n",
-				  nbits,
-				  r == sec_random_state ? "secondary" :
-				  r == random_state ? "primary" : "unknown");
+			DEBUG_ENT("added %d bits to %s\n", nbits, r->name);
 	}
 
 	spin_unlock_irqrestore(&r->lock, flags);
@@ -707,9 +707,9 @@ void batch_entropy_store(u32 a, u32 b, i
 EXPORT_SYMBOL(batch_entropy_store);
 
 /*
- * Flush out the accumulated entropy operations, adding entropy to the passed
- * store (normally random_state).  If that store has enough entropy, alternate
- * between randomizing the data of the primary and secondary stores.
+ * Flush out the accumulated entropy operations, adding entropy to the
+ * input pool.  If that pool has enough entropy, alternate
+ * between randomizing the data of all pools.
  */
 static void batch_entropy_process(void *private_)
 {
@@ -736,8 +736,8 @@ static void batch_entropy_process(void *
 	p = r;
 	while (head != tail) {
 		if (r->entropy_count >= max_entropy) {
-			r = (r == sec_random_state) ?	random_state :
-							sec_random_state;
+			r = (r == blocking_pool) ? input_pool :
+							blocking_pool;
 			max_entropy = r->poolinfo.POOLBITS;
 		}
 		add_entropy_words(r, batch_entropy_copy[tail].data, 2);
@@ -785,7 +785,7 @@ static void add_timer_randomness(struct 
 	int		entropy = 0;
 
 	/* if over the trickle threshold, use only 1 in 4096 samples */
-	if ( random_state->entropy_count > trickle_thresh &&
+	if ( input_pool->entropy_count > trickle_thresh &&
 	     (__get_cpu_var(trickle_count)++ & 0xfff))
 		return;
 
@@ -1295,11 +1295,10 @@ static inline void xfer_secondary_pool(s
 				min_t(int, nbytes, TMP_BUF_SIZE));
 
 		DEBUG_ENT("going to reseed %s with %d bits "
-			  "(%d of %d requested)\n",
-			  r == sec_random_state ? "secondary" : "unknown",
+			  "(%d of %d requested)\n", r->name,
 			  bytes * 8, nbytes * 8, r->entropy_count);
 
-		bytes=extract_entropy(random_state, tmp, bytes,
+		bytes=extract_entropy(input_pool, tmp, bytes,
 				      EXTRACT_ENTROPY_LIMIT);
 		add_entropy_words(r, tmp, bytes);
 		credit_entropy_store(r, bytes*8);
@@ -1338,10 +1337,7 @@ static ssize_t extract_entropy(struct en
 	/* Hold lock while accounting */
 	spin_lock_irqsave(&r->lock, cpuflags);
 
-	DEBUG_ENT("trying to extract %d bits from %s\n",
-		  nbytes * 8,
-		  r == sec_random_state ? "secondary" :
-		  r == random_state ? "primary" : "unknown");
+	DEBUG_ENT("trying to extract %d bits from %s\n", nbytes * 8, r->name);
 
 	if (flags & EXTRACT_ENTROPY_LIMIT && nbytes >= r->entropy_count / 8)
 		nbytes = r->entropy_count / 8;
@@ -1354,10 +1350,7 @@ static ssize_t extract_entropy(struct en
 	if (r->entropy_count < random_write_wakeup_thresh)
 		wake_up_interruptible(&random_write_wait);
 
-	DEBUG_ENT("debiting %d bits from %s%s\n",
-		  nbytes * 8,
-		  r == sec_random_state ? "secondary" :
-		  r == random_state ? "primary" : "unknown",
+	DEBUG_ENT("debiting %d bits from %s%s\n", nbytes * 8, r->name,
 		  flags & EXTRACT_ENTROPY_LIMIT ? "" : " (unlimited)");
 
 	spin_unlock_irqrestore(&r->lock, cpuflags);
@@ -1438,11 +1431,11 @@ static ssize_t extract_entropy(struct en
  */
 void get_random_bytes(void *buf, int nbytes)
 {
-	if (sec_random_state)  
-		extract_entropy(sec_random_state, (char *) buf, nbytes, 
+	if (blocking_pool)
+		extract_entropy(blocking_pool, (char *) buf, nbytes,
 				EXTRACT_ENTROPY_SECONDARY);
-	else if (random_state)
-		extract_entropy(random_state, (char *) buf, nbytes, 0);
+	else if (input_pool)
+		extract_entropy(input_pool, (char *) buf, nbytes, 0);
 	else
 		printk(KERN_NOTICE "get_random_bytes called before "
 				   "random driver initialization\n");
@@ -1489,17 +1482,18 @@ static int __init rand_initialize(void)
 {
 	int i;
 
-	if (create_entropy_store(DEFAULT_POOL_SIZE, &random_state))
+	if (create_entropy_store(INPUT_POOL_SIZE, "input", &input_pool))
 		goto err;
-	if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state))
+	if (batch_entropy_init(BATCH_ENTROPY_SIZE, input_pool))
 		goto err;
-	if (create_entropy_store(SECONDARY_POOL_SIZE, &sec_random_state))
+	if (create_entropy_store(BLOCKING_POOL_SIZE, "blocking",
+				 &blocking_pool))
 		goto err;
-	clear_entropy_store(random_state);
-	clear_entropy_store(sec_random_state);
-	init_std_data(random_state);
+	clear_entropy_store(input_pool);
+	clear_entropy_store(blocking_pool);
+	init_std_data(input_pool);
 #ifdef CONFIG_SYSCTL
-	sysctl_init_random(random_state);
+	sysctl_init_random(input_pool);
 #endif
 	for (i = 0; i < NR_IRQS; i++)
 		irq_timer_state[i] = NULL;
@@ -1561,7 +1555,7 @@ random_read(struct file * file, char * b
 
 		DEBUG_ENT("reading %d bits\n", n*8);
 
-		n = extract_entropy(sec_random_state, buf, n,
+		n = extract_entropy(blocking_pool, buf, n,
 				    EXTRACT_ENTROPY_USER |
 				    EXTRACT_ENTROPY_LIMIT |
 				    EXTRACT_ENTROPY_SECONDARY);
@@ -1578,7 +1572,7 @@ random_read(struct file * file, char * b
 			DEBUG_ENT("sleeping?\n");
 
 			wait_event_interruptible(random_read_wait,
-				random_state->entropy_count >=
+				input_pool->entropy_count >=
 						 random_read_wakeup_thresh);
 
 			DEBUG_ENT("awake\n");
@@ -1615,7 +1609,7 @@ static ssize_t
 urandom_read(struct file * file, char * buf,
 		      size_t nbytes, loff_t *ppos)
 {
-	return extract_entropy(sec_random_state, buf, nbytes,
+	return extract_entropy(blocking_pool, buf, nbytes,
 			       EXTRACT_ENTROPY_USER |
 			       EXTRACT_ENTROPY_SECONDARY);
 }
@@ -1628,9 +1622,9 @@ random_poll(struct file *file, poll_tabl
 	poll_wait(file, &random_read_wait, wait);
 	poll_wait(file, &random_write_wait, wait);
 	mask = 0;
-	if (random_state->entropy_count >= random_read_wakeup_thresh)
+	if (input_pool->entropy_count >= random_read_wakeup_thresh)
 		mask |= POLLIN | POLLRDNORM;
-	if (random_state->entropy_count < random_write_wakeup_thresh)
+	if (input_pool->entropy_count < random_write_wakeup_thresh)
 		mask |= POLLOUT | POLLWRNORM;
 	return mask;
 }
@@ -1656,7 +1650,7 @@ random_write(struct file * file, const c
 		c -= bytes;
 		p += bytes;
 
-		add_entropy_words(random_state, buf, (bytes + 3) / 4);
+		add_entropy_words(input_pool, buf, (bytes + 3) / 4);
 	}
 	if (p == buffer) {
 		return (ssize_t)ret;
@@ -1676,7 +1670,7 @@ random_ioctl(struct inode * inode, struc
 
 	switch (cmd) {
 	case RNDGETENTCNT:
-		ent_count = random_state->entropy_count;
+		ent_count = input_pool->entropy_count;
 		if (put_user(ent_count, (int *) arg))
 			return -EFAULT;
 		return 0;
@@ -1685,12 +1679,12 @@ random_ioctl(struct inode * inode, struc
 			return -EPERM;
 		if (get_user(ent_count, (int *) arg))
 			return -EFAULT;
-		credit_entropy_store(random_state, ent_count);
+		credit_entropy_store(input_pool, ent_count);
 		/*
 		 * Wake up waiting processes if we have enough
 		 * entropy.
 		 */
-		if (random_state->entropy_count >= random_read_wakeup_thresh)
+		if (input_pool->entropy_count >= random_read_wakeup_thresh)
 			wake_up_interruptible(&random_read_wait);
 		return 0;
 	case RNDADDENTROPY:
@@ -1707,25 +1701,25 @@ random_ioctl(struct inode * inode, struc
 				      size, &file->f_pos);
 		if (retval < 0)
 			return retval;
-		credit_entropy_store(random_state, ent_count);
+		credit_entropy_store(input_pool, ent_count);
 		/*
 		 * Wake up waiting processes if we have enough
 		 * entropy.
 		 */
-		if (random_state->entropy_count >= random_read_wakeup_thresh)
+		if (input_pool->entropy_count >= random_read_wakeup_thresh)
 			wake_up_interruptible(&random_read_wait);
 		return 0;
 	case RNDZAPENTCNT:
 		if (!capable(CAP_SYS_ADMIN))
 			return -EPERM;
-		random_state->entropy_count = 0;
+		input_pool->entropy_count = 0;
 		return 0;
 	case RNDCLEARPOOL:
 		/* Clear the entropy pool and associated counters. */
 		if (!capable(CAP_SYS_ADMIN))
 			return -EPERM;
-		clear_entropy_store(random_state);
-		init_std_data(random_state);
+		clear_entropy_store(input_pool);
+		init_std_data(input_pool);
 		return 0;
 	default:
 		return -EINVAL;
@@ -1895,12 +1889,12 @@ ctl_table random_table[] = {
 	{ .ctl_name = 0 }
 };
 
-static void sysctl_init_random(struct entropy_store *random_state)
+static void sysctl_init_random(struct entropy_store *pool)
 {
 	min_read_thresh = 8;
 	min_write_thresh = 0;
-	max_read_thresh = max_write_thresh = random_state->poolinfo.POOLBITS;
-	random_table[0].data = &random_state->entropy_count;
+	max_read_thresh = max_write_thresh = pool->poolinfo.POOLBITS;
+	random_table[0].data = &pool->entropy_count;
 }
 #endif 	/* CONFIG_SYSCTL */
 

_

[PATCH 7/22] /dev/random: simplify reseed logic

[Matt Mackall]

/dev/random  simplify reseed logic

Automatically reseed from input pool when pulling from output pools.


 tiny-mpm/drivers/char/random.c |   20 ++++++--------------
 1 files changed, 6 insertions(+), 14 deletions(-)

diff -puN drivers/char/random.c~kill-extract-secondary drivers/char/random.c
--- tiny/drivers/char/random.c~kill-extract-secondary	2004-03-20 13:38:20.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:20.000000000 -0600
@@ -1259,8 +1259,7 @@ static void MD5Transform(__u32 buf[HASH_
  *********************************************************************/
 
 #define EXTRACT_ENTROPY_USER		1
-#define EXTRACT_ENTROPY_SECONDARY	2
-#define EXTRACT_ENTROPY_LIMIT		4
+#define EXTRACT_ENTROPY_LIMIT		2
 #define TMP_BUF_SIZE			(HASH_BUFFER_SIZE + HASH_EXTRA_SIZE)
 #define SEC_XFER_SIZE			(TMP_BUF_SIZE*4)
 
@@ -1298,10 +1297,6 @@ static inline void xfer_secondary_pool(s
  * number of bytes that are actually obtained.  If the EXTRACT_ENTROPY_USER
  * flag is given, then the buf pointer is assumed to be in user space.
  *
- * If the EXTRACT_ENTROPY_SECONDARY flag is given, then we are actually
- * extracting entropy from the secondary pool, and can refill from the
- * primary pool if needed.
- *
  * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
  */
 static ssize_t extract_entropy(struct entropy_store *r, void * buf,
@@ -1317,7 +1312,7 @@ static ssize_t extract_entropy(struct en
 	if (r->entropy_count > r->poolinfo->POOLBITS)
 		r->entropy_count = r->poolinfo->POOLBITS;
 
-	if (flags & EXTRACT_ENTROPY_SECONDARY)
+	if (r != input_pool)
 		xfer_secondary_pool(r, nbytes, tmp);
 
 	/* Hold lock while accounting */
@@ -1418,10 +1413,9 @@ static ssize_t extract_entropy(struct en
 void get_random_bytes(void *buf, int nbytes)
 {
 	if (blocking_pool)
-		extract_entropy(blocking_pool, (char *) buf, nbytes,
-				EXTRACT_ENTROPY_SECONDARY);
+		extract_entropy(blocking_pool, buf, nbytes, 0);
 	else if (input_pool)
-		extract_entropy(input_pool, (char *) buf, nbytes, 0);
+		extract_entropy(input_pool, buf, nbytes, 0);
 	else
 		printk(KERN_NOTICE "get_random_bytes called before "
 				   "random driver initialization\n");
@@ -1541,8 +1535,7 @@ random_read(struct file * file, char * b
 
 		n = extract_entropy(blocking_pool, buf, n,
 				    EXTRACT_ENTROPY_USER |
-				    EXTRACT_ENTROPY_LIMIT |
-				    EXTRACT_ENTROPY_SECONDARY);
+				    EXTRACT_ENTROPY_LIMIT);
 
 		DEBUG_ENT("read got %d bits (%d still needed)\n",
 			  n*8, (nbytes-n)*8);
@@ -1594,8 +1587,7 @@ urandom_read(struct file * file, char * 
 		      size_t nbytes, loff_t *ppos)
 {
 	return extract_entropy(blocking_pool, buf, nbytes,
-			       EXTRACT_ENTROPY_USER |
-			       EXTRACT_ENTROPY_SECONDARY);
+			       EXTRACT_ENTROPY_USER);
 }
 
 static unsigned int

_

[PATCH 8/22] /dev/random: BUG on premature random users

[Matt Mackall]

/dev/random  BUG on premature random users

Generate a fatal error if we try to use the get_random_bytes before
we're initialized.


 tiny-mpm/drivers/char/random.c |    9 ++-------
 1 files changed, 2 insertions(+), 7 deletions(-)

diff -puN drivers/char/random.c~bug-on-grb drivers/char/random.c
--- tiny/drivers/char/random.c~bug-on-grb	2004-03-20 13:38:22.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:22.000000000 -0600
@@ -1412,13 +1412,8 @@ static ssize_t extract_entropy(struct en
  */
 void get_random_bytes(void *buf, int nbytes)
 {
-	if (blocking_pool)
-		extract_entropy(blocking_pool, buf, nbytes, 0);
-	else if (input_pool)
-		extract_entropy(input_pool, buf, nbytes, 0);
-	else
-		printk(KERN_NOTICE "get_random_bytes called before "
-				   "random driver initialization\n");
+	BUG_ON(!blocking_pool);
+	extract_entropy(blocking_pool, buf, nbytes, 0);
 }
 
 EXPORT_SYMBOL(get_random_bytes);

_

[PATCH 9/22] /dev/random: more robust catastrophic reseed logic

[Matt Mackall]

/dev/random  more robust catastrophic reseed logic

When reseeding, we always do a "catastrophic reseed" where we pull
enough new bits to make the new state unguessable from outputs even if we
knew the old state. So we must do the checks against the minimum
reseed amount under the pool lock in extract_entropy.


 tiny-mpm/drivers/char/random.c |   38 +++++++++++++++++++++++---------------
 1 files changed, 23 insertions(+), 15 deletions(-)

diff -puN drivers/char/random.c~extract-min-max drivers/char/random.c
--- tiny/drivers/char/random.c~extract-min-max	2004-03-20 13:38:25.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:25.000000000 -0600
@@ -1264,7 +1264,7 @@ static void MD5Transform(__u32 buf[HASH_
 #define SEC_XFER_SIZE			(TMP_BUF_SIZE*4)
 
 static ssize_t extract_entropy(struct entropy_store *r, void * buf,
-			       size_t nbytes, int flags);
+			       size_t nbytes, int min, int flags);
 
 /*
  * This utility inline function is responsible for transfering entropy
@@ -1276,14 +1276,14 @@ static inline void xfer_secondary_pool(s
 {
 	if (r->entropy_count < nbytes * 8 &&
 	    r->entropy_count < r->poolinfo->POOLBITS) {
-		int bytes = max_t(int, random_read_wakeup_thresh / 8,
-				min_t(int, nbytes, TMP_BUF_SIZE));
+		int bytes = min_t(int, nbytes, TMP_BUF_SIZE);
 
 		DEBUG_ENT("going to reseed %s with %d bits "
 			  "(%d of %d requested)\n", r->name,
 			  bytes * 8, nbytes * 8, r->entropy_count);
 
 		bytes=extract_entropy(input_pool, tmp, bytes,
+				      random_read_wakeup_thresh / 8,
 				      EXTRACT_ENTROPY_LIMIT);
 		add_entropy_words(r, tmp, bytes);
 		credit_entropy_store(r, bytes*8);
@@ -1297,10 +1297,13 @@ static inline void xfer_secondary_pool(s
  * number of bytes that are actually obtained.  If the EXTRACT_ENTROPY_USER
  * flag is given, then the buf pointer is assumed to be in user space.
  *
+ * If we have less than min bytes of entropy available, exit without
+ * transferring any. This helps avoid racing when reseeding.
+ *
  * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
  */
 static ssize_t extract_entropy(struct entropy_store *r, void * buf,
-			       size_t nbytes, int flags)
+			       size_t nbytes, int min, int flags)
 {
 	ssize_t ret, i;
 	__u32 tmp[TMP_BUF_SIZE];
@@ -1320,16 +1323,21 @@ static ssize_t extract_entropy(struct en
 
 	DEBUG_ENT("trying to extract %d bits from %s\n", nbytes * 8, r->name);
 
-	if (flags & EXTRACT_ENTROPY_LIMIT && nbytes >= r->entropy_count / 8)
-		nbytes = r->entropy_count / 8;
+	if (r->entropy_count / 8 < min) {
+		nbytes = 0;
+	} else {
+		if (flags & EXTRACT_ENTROPY_LIMIT &&
+		    nbytes >= r->entropy_count / 8)
+			nbytes = r->entropy_count / 8;
 
-	if (r->entropy_count / 8 >= nbytes)
-		r->entropy_count -= nbytes*8;
-	else
-		r->entropy_count = 0;
+		if (r->entropy_count / 8 >= nbytes)
+			r->entropy_count -= nbytes*8;
+		else
+			r->entropy_count = 0;
 
-	if (r->entropy_count < random_write_wakeup_thresh)
-		wake_up_interruptible(&random_write_wait);
+		if (r->entropy_count < random_write_wakeup_thresh)
+			wake_up_interruptible(&random_write_wait);
+	}
 
 	DEBUG_ENT("debiting %d bits from %s%s\n", nbytes * 8, r->name,
 		  flags & EXTRACT_ENTROPY_LIMIT ? "" : " (unlimited)");
@@ -1413,7 +1421,7 @@ static ssize_t extract_entropy(struct en
 void get_random_bytes(void *buf, int nbytes)
 {
 	BUG_ON(!blocking_pool);
-	extract_entropy(blocking_pool, buf, nbytes, 0);
+	extract_entropy(blocking_pool, buf, nbytes, 0, 0);
 }
 
 EXPORT_SYMBOL(get_random_bytes);
@@ -1528,7 +1536,7 @@ random_read(struct file * file, char * b
 
 		DEBUG_ENT("reading %d bits\n", n*8);
 
-		n = extract_entropy(blocking_pool, buf, n,
+		n = extract_entropy(blocking_pool, buf, n, 0,
 				    EXTRACT_ENTROPY_USER |
 				    EXTRACT_ENTROPY_LIMIT);
 
@@ -1581,7 +1589,7 @@ static ssize_t
 urandom_read(struct file * file, char * buf,
 		      size_t nbytes, loff_t *ppos)
 {
-	return extract_entropy(blocking_pool, buf, nbytes,
+	return extract_entropy(blocking_pool, buf, nbytes, 0,
 			       EXTRACT_ENTROPY_USER);
 }
 

_

[PATCH 10/22] /dev/random: entropy reserve logic for starvation preve

[Matt Mackall]

/dev/random  entropy reserve logic for starvation prevention

Additional parameter to allow keeping an entropy reserve in the input
pool. Groundwork for /dev/urandom vs /dev/random starvation prevention.

 tiny-mpm/drivers/char/random.c |   30 +++++++++++++++++-------------
 1 files changed, 17 insertions(+), 13 deletions(-)

diff -puN drivers/char/random.c~debit-entropy drivers/char/random.c
--- tiny/drivers/char/random.c~debit-entropy	2004-03-20 13:38:26.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:26.000000000 -0600
@@ -1264,7 +1264,7 @@ static void MD5Transform(__u32 buf[HASH_
 #define SEC_XFER_SIZE			(TMP_BUF_SIZE*4)
 
 static ssize_t extract_entropy(struct entropy_store *r, void * buf,
-			       size_t nbytes, int min, int flags);
+			       size_t nbytes, int min, int rsvd, int flags);
 
 /*
  * This utility inline function is responsible for transfering entropy
@@ -1283,7 +1283,7 @@ static inline void xfer_secondary_pool(s
 			  bytes * 8, nbytes * 8, r->entropy_count);
 
 		bytes=extract_entropy(input_pool, tmp, bytes,
-				      random_read_wakeup_thresh / 8,
+				      random_read_wakeup_thresh / 8, 0,
 				      EXTRACT_ENTROPY_LIMIT);
 		add_entropy_words(r, tmp, bytes);
 		credit_entropy_store(r, bytes*8);
@@ -1297,13 +1297,15 @@ static inline void xfer_secondary_pool(s
  * number of bytes that are actually obtained.  If the EXTRACT_ENTROPY_USER
  * flag is given, then the buf pointer is assumed to be in user space.
  *
- * If we have less than min bytes of entropy available, exit without
- * transferring any. This helps avoid racing when reseeding.
+ * The min parameter specifies the minimum amount we can pull before
+ * failing to avoid races that defeat catastrophic reseeding while the
+ * reserved parameter indicates how much entropy we must leave in the
+ * pool after each pull to avoid starving other readers.
  *
  * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
  */
 static ssize_t extract_entropy(struct entropy_store *r, void * buf,
-			       size_t nbytes, int min, int flags)
+			       size_t nbytes, int min, int reserved, int flags)
 {
 	ssize_t ret, i;
 	__u32 tmp[TMP_BUF_SIZE];
@@ -1323,17 +1325,19 @@ static ssize_t extract_entropy(struct en
 
 	DEBUG_ENT("trying to extract %d bits from %s\n", nbytes * 8, r->name);
 
-	if (r->entropy_count / 8 < min) {
+	/* Can we pull enough? */
+	if (r->entropy_count / 8 < min + reserved) {
 		nbytes = 0;
 	} else {
+		/* If limited, never pull more than available */
 		if (flags & EXTRACT_ENTROPY_LIMIT &&
-		    nbytes >= r->entropy_count / 8)
-			nbytes = r->entropy_count / 8;
+		    nbytes + reserved >= r->entropy_count / 8)
+			nbytes = r->entropy_count/8 - reserved;
 
-		if (r->entropy_count / 8 >= nbytes)
+		if(r->entropy_count / 8 >= nbytes + reserved)
 			r->entropy_count -= nbytes*8;
 		else
-			r->entropy_count = 0;
+			r->entropy_count = reserved;
 
 		if (r->entropy_count < random_write_wakeup_thresh)
 			wake_up_interruptible(&random_write_wait);
@@ -1421,7 +1425,7 @@ static ssize_t extract_entropy(struct en
 void get_random_bytes(void *buf, int nbytes)
 {
 	BUG_ON(!blocking_pool);
-	extract_entropy(blocking_pool, buf, nbytes, 0, 0);
+	extract_entropy(blocking_pool, buf, nbytes, 0, 0, 0);
 }
 
 EXPORT_SYMBOL(get_random_bytes);
@@ -1536,7 +1540,7 @@ random_read(struct file * file, char * b
 
 		DEBUG_ENT("reading %d bits\n", n*8);
 
-		n = extract_entropy(blocking_pool, buf, n, 0,
+		n = extract_entropy(blocking_pool, buf, n, 0, 0,
 				    EXTRACT_ENTROPY_USER |
 				    EXTRACT_ENTROPY_LIMIT);
 
@@ -1589,7 +1593,7 @@ static ssize_t
 urandom_read(struct file * file, char * buf,
 		      size_t nbytes, loff_t *ppos)
 {
-	return extract_entropy(blocking_pool, buf, nbytes, 0,
+	return extract_entropy(blocking_pool, buf, nbytes, 0, 0,
 			       EXTRACT_ENTROPY_USER);
 }
 

_

[PATCH 12/22] /dev/random: add pool for /dev/urandom to prevent starv

[Matt Mackall]

/dev/random  add pool for /dev/urandom to prevent starvation

Prevent readers of /dev/urandom from starving readers of /dev/random
by adding a second output pool for nonblocking reads. /dev/urandom
will always leave enough entropy in input pool for /dev/random to
reseed itself.


 tiny-mpm/drivers/char/random.c |   32 +++++++++++++++++---------------
 1 files changed, 17 insertions(+), 15 deletions(-)

diff -puN drivers/char/random.c~nonblocking-pool drivers/char/random.c
--- tiny/drivers/char/random.c~nonblocking-pool	2004-03-20 13:38:28.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:28.000000000 -0600
@@ -399,8 +399,7 @@ static struct poolinfo {
 /*
  * Static global variables
  */
-static struct entropy_store *input_pool; /* The default global store */
-static struct entropy_store *blocking_pool; /* secondary store */
+static struct entropy_store *input_pool, *blocking_pool, *nonblocking_pool;
 static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
 static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
 
@@ -477,9 +476,11 @@ static inline __u32 int_ln_12bits(__u32 
 #endif
 
 #if 0
-#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random %04d %04d: " fmt,\
+#define DEBUG_ENT(fmt, arg...) \
+printk(KERN_DEBUG "random %04d %04d %04d: " fmt,\
 	input_pool->entropy_count,\
 	blocking_pool->entropy_count,\
+	nonblocking_pool->entropy_count,\
 	## arg)
 #else
 #define DEBUG_ENT(fmt, arg...) do {} while (0)
@@ -700,8 +701,7 @@ EXPORT_SYMBOL(batch_entropy_store);
  */
 static void batch_entropy_process(void *private_)
 {
-	struct entropy_store *r	= (struct entropy_store *) private_, *p;
-	int max_entropy = r->poolinfo->POOLBITS;
+	struct entropy_store *r	= input_pool;
 	unsigned head, tail;
 
 	/* Mixing into the pool is expensive, so copy over the batch
@@ -720,18 +720,17 @@ static void batch_entropy_process(void *
 
 	spin_unlock_irq(&batch_lock);
 
-	p = r;
 	while (head != tail) {
-		if (r->entropy_count >= max_entropy) {
-			r = (r == blocking_pool) ? input_pool :
-							blocking_pool;
-			max_entropy = r->poolinfo->POOLBITS;
-		}
+		if (r->entropy_count >= r->poolinfo->POOLBITS)
+			r = blocking_pool;
+		if (r->entropy_count >= r->poolinfo->POOLBITS)
+			r = nonblocking_pool;
+
 		add_entropy_words(r, batch_entropy_copy[tail].data, 2);
 		credit_entropy_store(r, batch_entropy_copy[tail].credit);
 		tail = (tail+1) & (batch_max-1);
 	}
-	if (p->entropy_count >= random_read_wakeup_thresh)
+	if (input_pool->entropy_count >= random_read_wakeup_thresh)
 		wake_up_interruptible(&random_read_wait);
 }
 
@@ -1427,7 +1426,7 @@ static ssize_t extract_entropy(struct en
 void get_random_bytes(void *buf, int nbytes)
 {
 	BUG_ON(!blocking_pool);
-	extract_entropy(blocking_pool, buf, nbytes, 0, 0, 0);
+	extract_entropy(nonblocking_pool, buf, nbytes, 0, 0, 0);
 }
 
 EXPORT_SYMBOL(get_random_bytes);
@@ -1473,8 +1472,11 @@ static int __init rand_initialize(void)
 
 	input_pool = create_entropy_store(INPUT_POOL_SIZE, "input");
 	blocking_pool = create_entropy_store(BLOCKING_POOL_SIZE, "blocking");
+	nonblocking_pool = create_entropy_store(BLOCKING_POOL_SIZE,
+						"nonblocking");
+	nonblocking_pool->reserved = 1;
 
-	if (!(input_pool && blocking_pool))
+	if (!(input_pool && blocking_pool && nonblocking_pool))
 		return -1;
 
 	if (batch_entropy_init(BATCH_ENTROPY_SIZE, input_pool))
@@ -1595,7 +1597,7 @@ static ssize_t
 urandom_read(struct file * file, char * buf,
 		      size_t nbytes, loff_t *ppos)
 {
-	return extract_entropy(blocking_pool, buf, nbytes, 0, 0,
+	return extract_entropy(nonblocking_pool, buf, nbytes, 0, 0,
 			       EXTRACT_ENTROPY_USER);
 }
 

_

[PATCH 11/22] /dev/random: flag pools that need entropy reserve

[Matt Mackall]

/dev/random  flag pools that need entropy reserve

Add flag for pools that need to leave an entropy reserve


 tiny-mpm/drivers/char/random.c |    4 +++-
 1 files changed, 3 insertions(+), 1 deletion(-)

diff -puN drivers/char/random.c~reserved-in-struct drivers/char/random.c
--- tiny/drivers/char/random.c~reserved-in-struct	2004-03-20 13:38:27.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:27.000000000 -0600
@@ -497,6 +497,7 @@ struct entropy_store {
 	unsigned add_ptr;
 	int entropy_count;
 	int input_rotate;
+	int reserved;
 	struct poolinfo *poolinfo;
 	spinlock_t lock;
 	__u32 pool[0];
@@ -1277,13 +1278,14 @@ static inline void xfer_secondary_pool(s
 	if (r->entropy_count < nbytes * 8 &&
 	    r->entropy_count < r->poolinfo->POOLBITS) {
 		int bytes = min_t(int, nbytes, TMP_BUF_SIZE);
+		int reserved = r->reserved ? random_read_wakeup_thresh/4 : 0;
 
 		DEBUG_ENT("going to reseed %s with %d bits "
 			  "(%d of %d requested)\n", r->name,
 			  bytes * 8, nbytes * 8, r->entropy_count);
 
 		bytes=extract_entropy(input_pool, tmp, bytes,
-				      random_read_wakeup_thresh / 8, 0,
+				      random_read_wakeup_thresh/8, reserved,
 				      EXTRACT_ENTROPY_LIMIT);
 		add_entropy_words(r, tmp, bytes);
 		credit_entropy_store(r, bytes*8);

_

[PATCH 13/22] /dev/random: kill extract_timer_state

[Matt Mackall]

/dev/random  kill extract_timer_state

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.


 tiny-mpm/drivers/char/random.c |    3 ---
 1 files changed, 3 deletions(-)

diff -puN drivers/char/random.c~kill-extract-state drivers/char/random.c
--- tiny/drivers/char/random.c~kill-extract-state	2004-03-20 13:38:30.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:30.000000000 -0600
@@ -749,7 +749,6 @@ struct timer_rand_state {
 
 static struct timer_rand_state keyboard_timer_state;
 static struct timer_rand_state mouse_timer_state;
-static struct timer_rand_state extract_timer_state;
 static struct timer_rand_state *irq_timer_state[NR_IRQS];
 
 /*
@@ -1490,8 +1489,6 @@ static int __init rand_initialize(void)
 		irq_timer_state[i] = NULL;
 	memset(&keyboard_timer_state, 0, sizeof(struct timer_rand_state));
 	memset(&mouse_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;
 }
 module_init(rand_initialize);

_

[PATCH 16/22] /dev/random: kill 2.2 cruft

[Matt Mackall]

/dev/random  kill 2.2 cruft

Remove Linux 2.2 compatibility cruft.


 tiny-mpm/drivers/char/random.c |   10 ----------
 1 files changed, 10 deletions(-)

diff -puN drivers/char/random.c~random-waitqueue drivers/char/random.c
--- tiny/drivers/char/random.c~random-waitqueue	2004-03-20 13:38:35.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:35.000000000 -0600
@@ -382,16 +382,6 @@ static struct poolinfo {
  */
 
 /*
- * 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 *input_pool, *blocking_pool, *nonblocking_pool;

_

[PATCH 15/22] /dev/random: kill unrolled SHA code

[Matt Mackall]

/dev/random  kill unrolled SHA code

Kill the unrolled SHA variants. In the future, we can use cryptoapi
for faster hash functions.

 tiny-mpm/drivers/char/random.c |  146 -----------------------------------------
 1 files changed, 146 deletions(-)

diff -puN drivers/char/random.c~kill-sha-variants drivers/char/random.c
--- tiny/drivers/char/random.c~kill-sha-variants	2004-03-20 13:38:34.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:34.000000000 -0600
@@ -885,9 +885,6 @@ EXPORT_SYMBOL(add_disk_randomness);
 #define HASH_BUFFER_SIZE 5
 #define HASH_EXTRA_SIZE 80
 
-/* Various size/speed tradeoffs are available.  Choose 0..3. */
-#define SHA_CODE_SIZE 0
-
 /*
  * SHA transform algorithm, taken from code written by Peter Gutmann,
  * and placed in the public domain.
@@ -909,10 +906,6 @@ EXPORT_SYMBOL(add_disk_randomness);
 
 #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 ) )
-
-
 static void sha_transform(__u32 digest[85], __u32 const data[16])
 {
     __u32 A, B, C, D, E;     /* Local vars */
@@ -940,11 +933,6 @@ static void sha_transform(__u32 digest[8
     E = digest[ 4 ];
 
     /* Heavy mangling, in 4 sub-rounds of 20 iterations each. */
-#if SHA_CODE_SIZE == 0
-    /*
-     * Approximately 50% of the speed of the largest version, but
-     * takes up 1/16 the space.  Saves about 6k on an i386 kernel.
-     */
     for (i = 0; i < 80; i++) {
 	if (i < 40) {
 	    if (i < 20)
@@ -960,139 +948,6 @@ static void sha_transform(__u32 digest[8
 	TEMP += ROTL(5, A) + E + W[i];
 	E = D; D = C; C = ROTL(30, B); 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;
-    }
-    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;
-    }
-    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;
-    }
-    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;
-    }
-#elif SHA_CODE_SIZE == 2
-    for (i = 0; i < 20; i += 5) {
-	subRound( A, B, C, D, E, f1, K1, W[ i   ] );
-	subRound( E, A, B, C, D, f1, K1, W[ i+1 ] );
-	subRound( D, E, A, B, C, f1, K1, W[ i+2 ] );
-	subRound( C, D, E, A, B, f1, K1, W[ i+3 ] );
-	subRound( B, C, D, E, A, f1, K1, W[ i+4 ] );
-    }
-    for (; i < 40; i += 5) {
-	subRound( A, B, C, D, E, f2, K2, W[ i   ] );
-	subRound( E, A, B, C, D, f2, K2, W[ i+1 ] );
-	subRound( D, E, A, B, C, f2, K2, W[ i+2 ] );
-	subRound( C, D, E, A, B, f2, K2, W[ i+3 ] );
-	subRound( B, C, D, E, A, f2, K2, W[ i+4 ] );
-    }
-    for (; i < 60; i += 5) {
-	subRound( A, B, C, D, E, f3, K3, W[ i   ] );
-	subRound( E, A, B, C, D, f3, K3, W[ i+1 ] );
-	subRound( D, E, A, B, C, f3, K3, W[ i+2 ] );
-	subRound( C, D, E, A, B, f3, K3, W[ i+3 ] );
-	subRound( B, C, D, E, A, f3, K3, W[ i+4 ] );
-    }
-    for (; i < 80; i += 5) {
-	subRound( A, B, C, D, E, f4, K4, W[ i   ] );
-	subRound( E, A, B, C, D, f4, K4, W[ i+1 ] );
-	subRound( D, E, A, B, C, f4, K4, W[ i+2 ] );
-	subRound( C, D, E, A, B, f4, K4, W[ i+3 ] );
-	subRound( B, C, D, E, A, f4, K4, W[ i+4 ] );
-    }
-#elif SHA_CODE_SIZE == 3 /* Really large version */
-    subRound( A, B, C, D, E, f1, K1, W[  0 ] );
-    subRound( E, A, B, C, D, f1, K1, W[  1 ] );
-    subRound( D, E, A, B, C, f1, K1, W[  2 ] );
-    subRound( C, D, E, A, B, f1, K1, W[  3 ] );
-    subRound( B, C, D, E, A, f1, K1, W[  4 ] );
-    subRound( A, B, C, D, E, f1, K1, W[  5 ] );
-    subRound( E, A, B, C, D, f1, K1, W[  6 ] );
-    subRound( D, E, A, B, C, f1, K1, W[  7 ] );
-    subRound( C, D, E, A, B, f1, K1, W[  8 ] );
-    subRound( B, C, D, E, A, f1, K1, W[  9 ] );
-    subRound( A, B, C, D, E, f1, K1, W[ 10 ] );
-    subRound( E, A, B, C, D, f1, K1, W[ 11 ] );
-    subRound( D, E, A, B, C, f1, K1, W[ 12 ] );
-    subRound( C, D, E, A, B, f1, K1, W[ 13 ] );
-    subRound( B, C, D, E, A, f1, K1, W[ 14 ] );
-    subRound( A, B, C, D, E, f1, K1, W[ 15 ] );
-    subRound( E, A, B, C, D, f1, K1, W[ 16 ] );
-    subRound( D, E, A, B, C, f1, K1, W[ 17 ] );
-    subRound( C, D, E, A, B, f1, K1, W[ 18 ] );
-    subRound( B, C, D, E, A, f1, K1, W[ 19 ] );
-
-    subRound( A, B, C, D, E, f2, K2, W[ 20 ] );
-    subRound( E, A, B, C, D, f2, K2, W[ 21 ] );
-    subRound( D, E, A, B, C, f2, K2, W[ 22 ] );
-    subRound( C, D, E, A, B, f2, K2, W[ 23 ] );
-    subRound( B, C, D, E, A, f2, K2, W[ 24 ] );
-    subRound( A, B, C, D, E, f2, K2, W[ 25 ] );
-    subRound( E, A, B, C, D, f2, K2, W[ 26 ] );
-    subRound( D, E, A, B, C, f2, K2, W[ 27 ] );
-    subRound( C, D, E, A, B, f2, K2, W[ 28 ] );
-    subRound( B, C, D, E, A, f2, K2, W[ 29 ] );
-    subRound( A, B, C, D, E, f2, K2, W[ 30 ] );
-    subRound( E, A, B, C, D, f2, K2, W[ 31 ] );
-    subRound( D, E, A, B, C, f2, K2, W[ 32 ] );
-    subRound( C, D, E, A, B, f2, K2, W[ 33 ] );
-    subRound( B, C, D, E, A, f2, K2, W[ 34 ] );
-    subRound( A, B, C, D, E, f2, K2, W[ 35 ] );
-    subRound( E, A, B, C, D, f2, K2, W[ 36 ] );
-    subRound( D, E, A, B, C, f2, K2, W[ 37 ] );
-    subRound( C, D, E, A, B, f2, K2, W[ 38 ] );
-    subRound( B, C, D, E, A, f2, K2, W[ 39 ] );
-    
-    subRound( A, B, C, D, E, f3, K3, W[ 40 ] );
-    subRound( E, A, B, C, D, f3, K3, W[ 41 ] );
-    subRound( D, E, A, B, C, f3, K3, W[ 42 ] );
-    subRound( C, D, E, A, B, f3, K3, W[ 43 ] );
-    subRound( B, C, D, E, A, f3, K3, W[ 44 ] );
-    subRound( A, B, C, D, E, f3, K3, W[ 45 ] );
-    subRound( E, A, B, C, D, f3, K3, W[ 46 ] );
-    subRound( D, E, A, B, C, f3, K3, W[ 47 ] );
-    subRound( C, D, E, A, B, f3, K3, W[ 48 ] );
-    subRound( B, C, D, E, A, f3, K3, W[ 49 ] );
-    subRound( A, B, C, D, E, f3, K3, W[ 50 ] );
-    subRound( E, A, B, C, D, f3, K3, W[ 51 ] );
-    subRound( D, E, A, B, C, f3, K3, W[ 52 ] );
-    subRound( C, D, E, A, B, f3, K3, W[ 53 ] );
-    subRound( B, C, D, E, A, f3, K3, W[ 54 ] );
-    subRound( A, B, C, D, E, f3, K3, W[ 55 ] );
-    subRound( E, A, B, C, D, f3, K3, W[ 56 ] );
-    subRound( D, E, A, B, C, f3, K3, W[ 57 ] );
-    subRound( C, D, E, A, B, f3, K3, W[ 58 ] );
-    subRound( B, C, D, E, A, f3, K3, W[ 59 ] );
-
-    subRound( A, B, C, D, E, f4, K4, W[ 60 ] );
-    subRound( E, A, B, C, D, f4, K4, W[ 61 ] );
-    subRound( D, E, A, B, C, f4, K4, W[ 62 ] );
-    subRound( C, D, E, A, B, f4, K4, W[ 63 ] );
-    subRound( B, C, D, E, A, f4, K4, W[ 64 ] );
-    subRound( A, B, C, D, E, f4, K4, W[ 65 ] );
-    subRound( E, A, B, C, D, f4, K4, W[ 66 ] );
-    subRound( D, E, A, B, C, f4, K4, W[ 67 ] );
-    subRound( C, D, E, A, B, f4, K4, W[ 68 ] );
-    subRound( B, C, D, E, A, f4, K4, W[ 69 ] );
-    subRound( A, B, C, D, E, f4, K4, W[ 70 ] );
-    subRound( E, A, B, C, D, f4, K4, W[ 71 ] );
-    subRound( D, E, A, B, C, f4, K4, W[ 72 ] );
-    subRound( C, D, E, A, B, f4, K4, W[ 73 ] );
-    subRound( B, C, D, E, A, f4, K4, W[ 74 ] );
-    subRound( A, B, C, D, E, f4, K4, W[ 75 ] );
-    subRound( E, A, B, C, D, f4, K4, W[ 76 ] );
-    subRound( D, E, A, B, C, f4, K4, W[ 77 ] );
-    subRound( C, D, E, A, B, f4, K4, W[ 78 ] );
-    subRound( B, C, D, E, A, f4, K4, W[ 79 ] );
-#else
-#error Illegal SHA_CODE_SIZE
-#endif
 
     /* Build message digest */
     digest[ 0 ] += A;
@@ -1114,7 +969,6 @@ static void sha_transform(__u32 digest[8
 #undef K2
 #undef K3	
 #undef K4	
-#undef subRound
 
 /*********************************************************************
  *

_

[PATCH 14/22] /dev/random: kill unused md5 copy

[Matt Mackall]

/dev/random  kill unused md5 copy

Remove long-dead md5 code

 tiny-mpm/drivers/char/random.c |  160 +++--------------------------------------
 1 files changed, 12 insertions(+), 148 deletions(-)

diff -puN drivers/char/random.c~kill-md5 drivers/char/random.c
--- tiny/drivers/char/random.c~kill-md5	2004-03-20 13:38:31.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:31.000000000 -0600
@@ -221,17 +221,13 @@
  * number generator, which speed up the mixing function of the entropy
  * pool, taken from PGPfone.  Dale Worley has also contributed many
  * useful ideas and suggestions to improve this driver.
- * 
+ *
  * Any flaws in the design are solely my responsibility, and should
  * not be attributed to the Phil, Colin, or any of authors of PGP.
- * 
+ *
  * The code for SHA transform was taken from Peter Gutmann's
  * implementation, which has been placed in the public domain.
- * The code for MD5 transform was taken from Colin Plumb's
- * implementation, which has been placed in the public domain.
- * The MD5 cryptographic checksum was devised by Ronald Rivest, and is
- * documented in RFC 1321, "The MD5 Message Digest Algorithm".
- * 
+ *
  * Further background information on this topic may be obtained from
  * RFC 1750, "Randomness Recommendations for Security", by Donald
  * Eastlake, Steve Crocker, and Jeff Schiller.
@@ -266,7 +262,6 @@
 #define INPUT_POOL_SIZE 512
 #define BLOCKING_POOL_SIZE 128
 #define BATCH_ENTROPY_SIZE 256
-#define USE_SHA
 
 /*
  * The minimum number of bits of entropy before we wake up a read on
@@ -872,9 +867,9 @@ EXPORT_SYMBOL(add_disk_randomness);
 
 /*
  * This chunk of code defines a function
- * void HASH_TRANSFORM(__u32 digest[HASH_BUFFER_SIZE + HASH_EXTRA_SIZE],
+ * void sha_transform(__u32 digest[HASH_BUFFER_SIZE + HASH_EXTRA_SIZE],
  * 		__u32 const data[16])
- * 
+ *
  * The function hashes the input data to produce a digest in the first
  * HASH_BUFFER_SIZE words of the digest[] array, and uses HASH_EXTRA_SIZE
  * more words for internal purposes.  (This buffer is exported so the
@@ -882,24 +877,13 @@ EXPORT_SYMBOL(add_disk_randomness);
  * and tacking it onto the end of the digest[] array is the quick and
  * dirty way of doing it.)
  *
- * It so happens that MD5 and SHA share most of the initial vector
- * used to initialize the digest[] array before the first call:
- * 1) 0x67452301
- * 2) 0xefcdab89
- * 3) 0x98badcfe
- * 4) 0x10325476
- * 5) 0xc3d2e1f0 (SHA only)
- * 
  * For /dev/random purposes, the length of the data being hashed is
  * fixed in length, so appending a bit count in the usual way is not
  * cryptographically necessary.
  */
 
-#ifdef USE_SHA
-
 #define HASH_BUFFER_SIZE 5
 #define HASH_EXTRA_SIZE 80
-#define HASH_TRANSFORM SHATransform
 
 /* Various size/speed tradeoffs are available.  Choose 0..3. */
 #define SHA_CODE_SIZE 0
@@ -929,7 +913,7 @@ EXPORT_SYMBOL(add_disk_randomness);
     ( e += ROTL( 5, a ) + f( b, c, d ) + k + data, b = ROTL( 30, b ) )
 
 
-static void SHATransform(__u32 digest[85], __u32 const data[16])
+static void sha_transform(__u32 digest[85], __u32 const data[16])
 {
     __u32 A, B, C, D, E;     /* Local vars */
     __u32 TEMP;
@@ -1131,125 +1115,6 @@ static void SHATransform(__u32 digest[85
 #undef K3	
 #undef K4	
 #undef subRound
-	
-#else /* !USE_SHA - Use MD5 */
-
-#define HASH_BUFFER_SIZE 4
-#define HASH_EXTRA_SIZE 0
-#define HASH_TRANSFORM MD5Transform
-	
-/*
- * MD5 transform algorithm, taken from code written by Colin Plumb,
- * and put into the public domain
- */
-
-/* The four core functions - F1 is optimized somewhat */
-
-/* #define F1(x, y, z) (x & y | ~x & z) */
-#define F1(x, y, z) (z ^ (x & (y ^ z)))
-#define F2(x, y, z) F1(z, x, y)
-#define F3(x, y, z) (x ^ y ^ z)
-#define F4(x, y, z) (y ^ (x | ~z))
-
-/* This is the central step in the MD5 algorithm. */
-#define MD5STEP(f, w, x, y, z, data, s) \
-	( w += f(x, y, z) + data,  w = w<<s | w>>(32-s),  w += x )
-
-/*
- * The core of the MD5 algorithm, this alters an existing MD5 hash to
- * reflect the addition of 16 longwords of new data.  MD5Update blocks
- * the data and converts bytes into longwords for this routine.
- */
-static void MD5Transform(__u32 buf[HASH_BUFFER_SIZE], __u32 const in[16])
-{
-	__u32 a, b, c, d;
-
-	a = buf[0];
-	b = buf[1];
-	c = buf[2];
-	d = buf[3];
-
-	MD5STEP(F1, a, b, c, d, in[ 0]+0xd76aa478,  7);
-	MD5STEP(F1, d, a, b, c, in[ 1]+0xe8c7b756, 12);
-	MD5STEP(F1, c, d, a, b, in[ 2]+0x242070db, 17);
-	MD5STEP(F1, b, c, d, a, in[ 3]+0xc1bdceee, 22);
-	MD5STEP(F1, a, b, c, d, in[ 4]+0xf57c0faf,  7);
-	MD5STEP(F1, d, a, b, c, in[ 5]+0x4787c62a, 12);
-	MD5STEP(F1, c, d, a, b, in[ 6]+0xa8304613, 17);
-	MD5STEP(F1, b, c, d, a, in[ 7]+0xfd469501, 22);
-	MD5STEP(F1, a, b, c, d, in[ 8]+0x698098d8,  7);
-	MD5STEP(F1, d, a, b, c, in[ 9]+0x8b44f7af, 12);
-	MD5STEP(F1, c, d, a, b, in[10]+0xffff5bb1, 17);
-	MD5STEP(F1, b, c, d, a, in[11]+0x895cd7be, 22);
-	MD5STEP(F1, a, b, c, d, in[12]+0x6b901122,  7);
-	MD5STEP(F1, d, a, b, c, in[13]+0xfd987193, 12);
-	MD5STEP(F1, c, d, a, b, in[14]+0xa679438e, 17);
-	MD5STEP(F1, b, c, d, a, in[15]+0x49b40821, 22);
-
-	MD5STEP(F2, a, b, c, d, in[ 1]+0xf61e2562,  5);
-	MD5STEP(F2, d, a, b, c, in[ 6]+0xc040b340,  9);
-	MD5STEP(F2, c, d, a, b, in[11]+0x265e5a51, 14);
-	MD5STEP(F2, b, c, d, a, in[ 0]+0xe9b6c7aa, 20);
-	MD5STEP(F2, a, b, c, d, in[ 5]+0xd62f105d,  5);
-	MD5STEP(F2, d, a, b, c, in[10]+0x02441453,  9);
-	MD5STEP(F2, c, d, a, b, in[15]+0xd8a1e681, 14);
-	MD5STEP(F2, b, c, d, a, in[ 4]+0xe7d3fbc8, 20);
-	MD5STEP(F2, a, b, c, d, in[ 9]+0x21e1cde6,  5);
-	MD5STEP(F2, d, a, b, c, in[14]+0xc33707d6,  9);
-	MD5STEP(F2, c, d, a, b, in[ 3]+0xf4d50d87, 14);
-	MD5STEP(F2, b, c, d, a, in[ 8]+0x455a14ed, 20);
-	MD5STEP(F2, a, b, c, d, in[13]+0xa9e3e905,  5);
-	MD5STEP(F2, d, a, b, c, in[ 2]+0xfcefa3f8,  9);
-	MD5STEP(F2, c, d, a, b, in[ 7]+0x676f02d9, 14);
-	MD5STEP(F2, b, c, d, a, in[12]+0x8d2a4c8a, 20);
-
-	MD5STEP(F3, a, b, c, d, in[ 5]+0xfffa3942,  4);
-	MD5STEP(F3, d, a, b, c, in[ 8]+0x8771f681, 11);
-	MD5STEP(F3, c, d, a, b, in[11]+0x6d9d6122, 16);
-	MD5STEP(F3, b, c, d, a, in[14]+0xfde5380c, 23);
-	MD5STEP(F3, a, b, c, d, in[ 1]+0xa4beea44,  4);
-	MD5STEP(F3, d, a, b, c, in[ 4]+0x4bdecfa9, 11);
-	MD5STEP(F3, c, d, a, b, in[ 7]+0xf6bb4b60, 16);
-	MD5STEP(F3, b, c, d, a, in[10]+0xbebfbc70, 23);
-	MD5STEP(F3, a, b, c, d, in[13]+0x289b7ec6,  4);
-	MD5STEP(F3, d, a, b, c, in[ 0]+0xeaa127fa, 11);
-	MD5STEP(F3, c, d, a, b, in[ 3]+0xd4ef3085, 16);
-	MD5STEP(F3, b, c, d, a, in[ 6]+0x04881d05, 23);
-	MD5STEP(F3, a, b, c, d, in[ 9]+0xd9d4d039,  4);
-	MD5STEP(F3, d, a, b, c, in[12]+0xe6db99e5, 11);
-	MD5STEP(F3, c, d, a, b, in[15]+0x1fa27cf8, 16);
-	MD5STEP(F3, b, c, d, a, in[ 2]+0xc4ac5665, 23);
-
-	MD5STEP(F4, a, b, c, d, in[ 0]+0xf4292244,  6);
-	MD5STEP(F4, d, a, b, c, in[ 7]+0x432aff97, 10);
-	MD5STEP(F4, c, d, a, b, in[14]+0xab9423a7, 15);
-	MD5STEP(F4, b, c, d, a, in[ 5]+0xfc93a039, 21);
-	MD5STEP(F4, a, b, c, d, in[12]+0x655b59c3,  6);
-	MD5STEP(F4, d, a, b, c, in[ 3]+0x8f0ccc92, 10);
-	MD5STEP(F4, c, d, a, b, in[10]+0xffeff47d, 15);
-	MD5STEP(F4, b, c, d, a, in[ 1]+0x85845dd1, 21);
-	MD5STEP(F4, a, b, c, d, in[ 8]+0x6fa87e4f,  6);
-	MD5STEP(F4, d, a, b, c, in[15]+0xfe2ce6e0, 10);
-	MD5STEP(F4, c, d, a, b, in[ 6]+0xa3014314, 15);
-	MD5STEP(F4, b, c, d, a, in[13]+0x4e0811a1, 21);
-	MD5STEP(F4, a, b, c, d, in[ 4]+0xf7537e82,  6);
-	MD5STEP(F4, d, a, b, c, in[11]+0xbd3af235, 10);
-	MD5STEP(F4, c, d, a, b, in[ 2]+0x2ad7d2bb, 15);
-	MD5STEP(F4, b, c, d, a, in[ 9]+0xeb86d391, 21);
-
-	buf[0] += a;
-	buf[1] += b;
-	buf[2] += c;
-	buf[3] += d;
-}
-
-#undef F1
-#undef F2
-#undef F3
-#undef F4
-#undef MD5STEP
-
-#endif /* !USE_SHA */
 
 /*********************************************************************
  *
@@ -1368,9 +1233,8 @@ static ssize_t extract_entropy(struct en
 		tmp[1] = 0xefcdab89;
 		tmp[2] = 0x98badcfe;
 		tmp[3] = 0x10325476;
-#ifdef USE_SHA
 		tmp[4] = 0xc3d2e1f0;
-#endif
+
 		/*
 		 * As we hash the pool, we mix intermediate values of
 		 * the hash back into the pool.  This eliminates
@@ -1380,7 +1244,7 @@ static ssize_t extract_entropy(struct en
 		 * function can be inverted.
 		 */
 		for (i = 0, x = 0; i < r->poolinfo->poolwords; i += 16, x+=2) {
-			HASH_TRANSFORM(tmp, r->pool+i);
+			sha_transform(tmp, r->pool+i);
 			add_entropy_words(r, &tmp[x%HASH_BUFFER_SIZE], 1);
 		}
 		
@@ -2277,7 +2141,7 @@ __u32 secure_tcp_syn_cookie(__u32 saddr,
 	tmp[0]=saddr;
 	tmp[1]=daddr;
 	tmp[2]=(sport << 16) + dport;
-	HASH_TRANSFORM(tmp+16, tmp);
+	sha_transform(tmp+16, tmp);
 	seq = tmp[17] + sseq + (count << COOKIEBITS);
 
 	memcpy(tmp+3, syncookie_secret[1], sizeof(syncookie_secret[1]));
@@ -2285,7 +2149,7 @@ __u32 secure_tcp_syn_cookie(__u32 saddr,
 	tmp[1]=daddr;
 	tmp[2]=(sport << 16) + dport;
 	tmp[3] = count;	/* minute counter */
-	HASH_TRANSFORM(tmp+16, tmp);
+	sha_transform(tmp+16, tmp);
 
 	/* Add in the second hash and the data */
 	return seq + ((tmp[17] + data) & COOKIEMASK);
@@ -2314,7 +2178,7 @@ __u32 check_tcp_syn_cookie(__u32 cookie,
 	tmp[0]=saddr;
 	tmp[1]=daddr;
 	tmp[2]=(sport << 16) + dport;
-	HASH_TRANSFORM(tmp+16, tmp);
+	sha_transform(tmp+16, tmp);
 	cookie -= tmp[17] + sseq;
 	/* Cookie is now reduced to (count * 2^24) ^ (hash % 2^24) */
 
@@ -2327,7 +2191,7 @@ __u32 check_tcp_syn_cookie(__u32 cookie,
 	tmp[1] = daddr;
 	tmp[2] = (sport << 16) + dport;
 	tmp[3] = count - diff;	/* minute counter */
-	HASH_TRANSFORM(tmp+16, tmp);
+	sha_transform(tmp+16, tmp);
 
 	return (cookie - tmp[17]) & COOKIEMASK;	/* Leaving the data behind */
 }

_

[PATCH 18/22] /dev/random: bitop cleanup

[Matt Mackall]

/dev/random  bitop cleanup

Remove incorrectly named ln and x86 asm function and replace with fls
bitop.


 tiny-mpm/drivers/char/random.c |   42 -----------------------------------------
 1 files changed, 1 insertion(+), 41 deletions(-)

diff -puN drivers/char/random.c~ln-to-fls drivers/char/random.c
--- tiny/drivers/char/random.c~ln-to-fls	2004-03-20 13:38:38.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:38.000000000 -0600
@@ -420,43 +420,6 @@ static inline __u32 rotate_left(int i, _
 }
 #endif
 
-/*
- * 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
 #define DEBUG_ENT(fmt, arg...) \
 printk(KERN_DEBUG "random %04d %04d %04d: " fmt,\
@@ -800,10 +763,7 @@ static void add_timer_randomness(struct 
 		 * 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);
 	}
 	batch_entropy_store(num, time, entropy);
 }

_

[PATCH 17/22] /dev/random: minor shrinkage

[Matt Mackall]

/dev/random  minor shrinkage

#ifdef out unused pool sizes (more than makes up for size of
 nonblocking pool)

mark some functions init


 tiny-mpm/drivers/char/random.c |   26 ++++++++++++--------------
 1 files changed, 12 insertions(+), 14 deletions(-)

diff -puN drivers/char/random.c~shrink-random drivers/char/random.c
--- tiny/drivers/char/random.c~shrink-random	2004-03-20 13:38:37.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:37.000000000 -0600
@@ -297,41 +297,38 @@ static struct poolinfo {
 	int	poolwords;
 	int	tap1, tap2, tap3, tap4, tap5;
 } poolinfo_table[] = {
+	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
+	{ 128,	103,	76,	51,	25,	1 },
+	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
+	{ 32,	26,	20,	14,	7,	1 },
+#if 0
 	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
 	{ 2048,	1638,	1231,	819,	411,	1 },
 
 	/* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
 	{ 1024,	817,	615,	412,	204,	1 },
-#if 0				/* Alternate polynomial */
+
 	/* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
 	{ 1024,	819,	616,	410,	207,	2 },
-#endif
 
 	/* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
 	{ 512,	411,	308,	208,	104,	1 },
-#if 0				/* Alternates */
+
 	/* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
 	{ 512,	409,	307,	206,	102,	2 },
 	/* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */
 	{ 512,	409,	309,	205,	103,	2 },
-#endif
 
 	/* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
 	{ 256,	205,	155,	101,	52,	1 },
 
-	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
-	{ 128,	103,	76,	51,	25,	1 },
-#if 0	/* Alternate polynomial */
 	/* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
 	{ 128,	103,	78,	51,	27,	2 },
-#endif
 
 	/* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */
 	{ 64,	52,	39,	26,	14,	1 },
 
-	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
-	{ 32,	26,	20,	14,	7,	1 },
-
+#endif
 	{ 0,	0,	0,	0,	0,	0 },
 };
 
@@ -489,7 +486,8 @@ struct entropy_store {
 	__u32 pool[0];
 };
 
-static struct entropy_store *create_entropy_store(int size, const char *name)
+static struct entropy_store __init *create_entropy_store(
+	int size, const char *name)
 {
 	struct	entropy_store	*r;
 	struct	poolinfo	*p;
@@ -1149,7 +1147,7 @@ EXPORT_SYMBOL(get_random_bytes);
  *
  * NOTE: This is an OS-dependent function.
  */
-static void init_std_data(struct entropy_store *r)
+static void __init init_std_data(struct entropy_store *r)
 {
 	struct timeval 	tv;
 	__u32		words[2];
@@ -1581,7 +1579,7 @@ ctl_table random_table[] = {
 	{ .ctl_name = 0 }
 };
 
-static void sysctl_init_random(struct entropy_store *pool)
+static void __init sysctl_init_random(struct entropy_store *pool)
 {
 	min_read_thresh = 8;
 	min_write_thresh = 0;

_

[PATCH 22/22] /dev/random: update credits

[Matt Mackall]

/dev/random  update credits

Update dates, add contact info


 tiny-mpm/drivers/char/random.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff -puN drivers/char/random.c~random-credit drivers/char/random.c
--- tiny/drivers/char/random.c~random-credit	2004-03-20 13:38:53.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:53.000000000 -0600
@@ -1,8 +1,8 @@
 /*
  * random.c -- A strong random number generator
  *
- * Version 1.89, last modified 19-Sep-99
- * 
+ * Version 1.99  Matt Mackall <mpm@selenic.com> Oct 2003
+ *
  * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  All
  * rights reserved.
  *

_

[PATCH 21/22] /dev/random: kill batching of entropy mixing

[Matt Mackall]

/dev/random  kill batching of entropy mixing

Rather than batching up entropy samples, resulting in longer lock hold
times when we actually process the samples, mix in samples
immediately. The trickle code should eliminate almost all the
additional interrupt-time overhead this would otherwise incur, with or
without locking.



 tiny-mpm/drivers/char/random.c  |  150 +++++-----------------------------------
 tiny-mpm/include/linux/random.h |    2 
 2 files changed, 19 insertions(+), 133 deletions(-)

diff -puN drivers/char/random.c~kill-batching drivers/char/random.c
--- tiny/drivers/char/random.c~kill-batching	2004-03-20 13:38:50.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:50.000000000 -0600
@@ -245,7 +245,6 @@
 #include <linux/poll.h>
 #include <linux/init.h>
 #include <linux/fs.h>
-#include <linux/workqueue.h>
 #include <linux/genhd.h>
 #include <linux/interrupt.h>
 #include <linux/spinlock.h>
@@ -262,7 +261,6 @@
  */
 #define INPUT_POOL_SIZE 512
 #define BLOCKING_POOL_SIZE 128
-#define BATCH_ENTROPY_SIZE 256
 
 /*
  * The minimum number of bits of entropy before we wake up a read on
@@ -541,123 +539,6 @@ static void credit_entropy_store(struct 
 	spin_unlock_irqrestore(&r->lock, flags);
 }
 
-/**********************************************************************
- *
- * Entropy batch input management
- *
- * We batch entropy to be added to avoid increasing interrupt latency
- *
- **********************************************************************/
-
-struct sample {
-	__u32 data[2];
-	int credit;
-};
-
-static struct sample *batch_entropy_pool, *batch_entropy_copy;
-static int	batch_head, batch_tail;
-static spinlock_t batch_lock = SPIN_LOCK_UNLOCKED;
-
-static int	batch_max;
-static void batch_entropy_process(void *private_);
-static DECLARE_WORK(batch_work, batch_entropy_process, NULL);
-
-/* note: the size must be a power of 2 */
-static int __init batch_entropy_init(int size, struct entropy_store *r)
-{
-	batch_entropy_pool = kmalloc(size*sizeof(struct sample), GFP_KERNEL);
-	if (!batch_entropy_pool)
-		return -1;
-	batch_entropy_copy = kmalloc(size*sizeof(struct sample), GFP_KERNEL);
-	if (!batch_entropy_copy) {
-		kfree(batch_entropy_pool);
-		return -1;
-	}
-	batch_head = batch_tail = 0;
-	batch_work.data = r;
-	batch_max = size;
-	return 0;
-}
-
-/*
- * Changes to the entropy data is put into a queue rather than being added to
- * the entropy counts directly.  This is presumably to avoid doing heavy
- * hashing calculations during an interrupt in add_timer_randomness().
- * Instead, the entropy is only added to the pool by keventd.
- */
-void batch_entropy_store(u32 a, u32 b, int num)
-{
-	int new;
-	unsigned long flags;
-
-	if (!batch_max)
-		return;
-
-	spin_lock_irqsave(&batch_lock, flags);
-
-	batch_entropy_pool[batch_head].data[0] = a;
-	batch_entropy_pool[batch_head].data[1] = b;
-	batch_entropy_pool[batch_head].credit = num;
-
-	if (((batch_head - batch_tail) & (batch_max-1)) >= (batch_max / 2)) {
-		/*
-		 * Schedule it for the next timer tick:
-		 */
-		schedule_delayed_work(&batch_work, 1);
-	}
-
-	new = (batch_head+1) & (batch_max-1);
-	if (new == batch_tail) {
-		DEBUG_ENT("batch entropy buffer full\n");
-	} else {
-		batch_head = new;
-	}
-
-	spin_unlock_irqrestore(&batch_lock, flags);
-}
-
-EXPORT_SYMBOL(batch_entropy_store);
-
-/*
- * Flush out the accumulated entropy operations, adding entropy to the
- * input pool.  If that pool has enough entropy, alternate
- * between randomizing the data of all pools.
- */
-static void batch_entropy_process(void *private_)
-{
-	struct entropy_store *r	= input_pool;
-	unsigned head, tail;
-
-	/* Mixing into the pool is expensive, so copy over the batch
-	 * data and release the batch lock. The pool is at least half
-	 * full, so don't worry too much about copying only the used
-	 * part.
-	 */
-	spin_lock_irq(&batch_lock);
-
-	memcpy(batch_entropy_copy, batch_entropy_pool,
-	       batch_max*sizeof(struct sample));
-
-	head = batch_head;
-	tail = batch_tail;
-	batch_tail = batch_head;
-
-	spin_unlock_irq(&batch_lock);
-
-	while (head != tail) {
-		if (r->entropy_count >= r->poolinfo->POOLBITS)
-			r = blocking_pool;
-		if (r->entropy_count >= r->poolinfo->POOLBITS)
-			r = nonblocking_pool;
-
-		add_entropy_words(r, batch_entropy_copy[tail].data, 2);
-		credit_entropy_store(r, batch_entropy_copy[tail].credit);
-		tail = (tail+1) & (batch_max-1);
-	}
-	if (input_pool->entropy_count >= random_read_wakeup_thresh)
-		wake_up_interruptible(&random_read_wait);
-}
-
 /*********************************************************************
  *
  * Entropy input management
@@ -689,10 +570,10 @@ static struct timer_rand_state *irq_time
  */
 static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 {
+	struct entropy_store *r	= input_pool;
 	long long clock;
-	u32 time;
-	__s32		delta, delta2, delta3;
-	int		entropy = 0;
+	u32 data[2], time;
+	__s32 delta, delta2, delta3;
 
 	/* if over the trickle threshold, use only 1 in 4096 samples */
 	if ( input_pool->entropy_count > trickle_thresh &&
@@ -702,6 +583,18 @@ static void add_timer_randomness(struct 
 	/* Use slow clock for conservative entropy estimation */
 	time = jiffies;
 
+	/* Mix in fast clock for entropy data */
+	clock = sched_clock();
+	data[0] = num ^ (clock >> 32);
+	data[1] = time ^ (u32)clock;
+
+	if (r->entropy_count >= r->poolinfo->POOLBITS)
+		r = blocking_pool;
+	if (r->entropy_count >= r->poolinfo->POOLBITS)
+		r = nonblocking_pool;
+
+	add_entropy_words(r, data, 2);
+
 	/*
 	 * Calculate number of bits of randomness we probably added.
 	 * We take into account the first, second and third-order deltas
@@ -733,13 +626,11 @@ static void add_timer_randomness(struct 
 		 * Round down by 1 bit on general principles,
 		 * and limit entropy entimate to 12 bits.
 		 */
-		entropy = min_t(int, fls(delta>>1), 11);
-	}
+		credit_entropy_store(r, min_t(int, fls(delta>>1), 11));
 
-	/* Mix in fast clock for entropy data */
-	clock = sched_clock();
-	num ^= clock >> 32;
-	batch_entropy_store(num, time ^ (u32)clock, entropy);
+		if (input_pool->entropy_count >= random_read_wakeup_thresh)
+			wake_up_interruptible(&random_read_wait);
+	}
 }
 
 void add_keyboard_randomness(unsigned char scancode)
@@ -1115,9 +1006,6 @@ static int __init rand_initialize(void)
 	if (!(input_pool && blocking_pool && nonblocking_pool))
 		return -1;
 
-	if (batch_entropy_init(BATCH_ENTROPY_SIZE, input_pool))
-		return -1;
-
 	init_std_data(input_pool);
 #ifdef CONFIG_SYSCTL
 	sysctl_init_random(input_pool);
diff -puN include/linux/random.h~kill-batching include/linux/random.h
--- tiny/include/linux/random.h~kill-batching	2004-03-20 13:38:50.000000000 -0600
+++ tiny-mpm/include/linux/random.h	2004-03-20 13:38:50.000000000 -0600
@@ -41,8 +41,6 @@ struct rand_pool_info {
 
 extern void rand_initialize_irq(int irq);
 
-extern void batch_entropy_store(u32 a, u32 b, int num);
-
 extern void add_keyboard_randomness(unsigned char scancode);
 extern void add_mouse_randomness(__u32 mouse_data);
 extern void add_interrupt_randomness(int irq);

_

[PATCH 20/22] /dev/random: cleanup rol bitop

[Matt Mackall]

/dev/random  cleanup rol bitop

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.


 tiny-mpm/drivers/char/random.c |   40 +++++++---------------------------------
 1 files changed, 7 insertions(+), 33 deletions(-)

diff -puN drivers/char/random.c~kill-rotate drivers/char/random.c
--- tiny/drivers/char/random.c~kill-rotate	2004-03-20 15:04:42.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 15:08:19.000000000 -0600
@@ -393,33 +393,10 @@ static DECLARE_WAIT_QUEUE_HEAD(random_wr
 static void sysctl_init_random(struct entropy_store *pool);
 #endif
 
-/*****************************************************************
- *
- * Utility functions, with some ASM defined functions for speed
- * 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)
+static inline __u32 rol32(__u32 word, int shift)
 {
-	return (word << i) | (word >> (32 - i));
-	
+	return (word << shift) | (word >> (32 - shift));
 }
-#else
-static inline __u32 rotate_left(int i, __u32 word)
-{
-	__asm__("roll %%cl,%0"
-		:"=r" (word)
-		:"0" (word),"c" (i));
-	return word;
-}
-#endif
 
 #if 0
 #define DEBUG_ENT(fmt, arg...) \
@@ -514,7 +491,7 @@ static void add_entropy_words(struct ent
 	spin_lock_irqsave(&r->lock, flags);
 
 	while (nwords--) {
-		w = rotate_left(r->input_rotate, *in++);
+		w = rol32(*in++, r->input_rotate);
 		i = r->add_ptr = (r->add_ptr - 1) & wordmask;
 		/*
 		 * Normally, we add 7 bits of rotation to the pool.
@@ -849,8 +826,6 @@ EXPORT_SYMBOL(add_disk_randomness);
 #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 ) ) )
-
 static void sha_transform(__u32 digest[85], __u32 const data[16])
 {
     __u32 A, B, C, D, E;     /* Local vars */
@@ -867,7 +842,7 @@ static void sha_transform(__u32 digest[8
     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 */
@@ -890,8 +865,8 @@ static void sha_transform(__u32 digest[8
 	    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;
     }
 
     /* Build message digest */
@@ -905,7 +880,6 @@ static void sha_transform(__u32 digest[8
 #undef W
 }
 
-#undef ROTL
 #undef f1
 #undef f2
 #undef f3
@@ -1646,7 +1620,7 @@ __u32 halfMD4Transform(__u32 buf[4], __u
 		else
 			a += H(b,c,d) + K3;
 		a += in[(int)p[i]];
-		a = rotate_left(a, s[i]);
+		a = rol32(a, s[i]);
 		e = d; d = c; c = b; b = a; a = e;
 	}
 

_

[PATCH 19/22] /dev/random: use sched_clock for timing data

[Matt Mackall]

/dev/random  use sched_clock for timing data

Use the sched_clock() source for timing data, to get jiffies or better
resolution on all arches.


 tiny-mpm/drivers/char/random.c |   21 +++++++++------------
 1 files changed, 9 insertions(+), 12 deletions(-)

diff -puN drivers/char/random.c~random-sched-clock drivers/char/random.c
--- tiny/drivers/char/random.c~random-sched-clock	2004-03-20 13:38:46.000000000 -0600
+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:46.000000000 -0600
@@ -250,6 +250,7 @@
 #include <linux/interrupt.h>
 #include <linux/spinlock.h>
 #include <linux/percpu.h>
+#include <linux/sched.h>
 
 #include <asm/processor.h>
 #include <asm/uaccess.h>
@@ -711,7 +712,8 @@ static struct timer_rand_state *irq_time
  */
 static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
 {
-	__u32		time;
+	long long clock;
+	u32 time;
 	__s32		delta, delta2, delta3;
 	int		entropy = 0;
 
@@ -720,17 +722,8 @@ static void add_timer_randomness(struct 
 	     (__get_cpu_var(trickle_count)++ & 0xfff))
 		return;
 
-#if defined (__i386__) || defined (__x86_64__)
-	if (cpu_has_tsc) {
-		__u32 high;
-		rdtsc(time, high);
-		num ^= high;
-	} else {
-		time = jiffies;
-	}
-#else
+	/* Use slow clock for conservative entropy estimation */
 	time = jiffies;
-#endif
 
 	/*
 	 * Calculate number of bits of randomness we probably added.
@@ -765,7 +758,11 @@ static void add_timer_randomness(struct 
 		 */
 		entropy = min_t(int, fls(delta>>1), 11);
 	}
-	batch_entropy_store(num, time, entropy);
+
+	/* Mix in fast clock for entropy data */
+	clock = sched_clock();
+	num ^= clock >> 32;
+	batch_entropy_store(num, time ^ (u32)clock, entropy);
 }
 
 void add_keyboard_randomness(unsigned char scancode)

_

Re: [PATCH 2/22] /dev/random: Cleanup sleep logic

[Andrew Morton]

Matt Mackall <mpm@selenic.com> wrote:
>
> Cleanup /dev/random sleep logic
> 
> Original code checked in output pool rather than input pool for wakeup

So what is the rationale for switching it over to the primary pool?

Re: [PATCH 3/22] /dev/random: remove broken resizing sysctl

[Andrew Morton]

Matt Mackall <mpm@selenic.com> wrote:
>
> /dev/random  remove broken resizing sysctl

This could break things.  Shouldn't we leave the /proc entry there
and print a friendly message in the sysctl handler?

Re: [PATCH 4/22] /dev/random: remove outdated RNDGETPOOL ioctl

[Andrew Morton]

Matt Mackall <mpm@selenic.com> wrote:
>
> Remove RNDGETPOOL ioctl,

ditto.

Re: [PATCH 15/22] /dev/random: kill unrolled SHA code

[Jeff Garzik]

Matt Mackall wrote:
> /dev/random  kill unrolled SHA code
> 
> Kill the unrolled SHA variants. In the future, we can use cryptoapi
> for faster hash functions.
> 
>  tiny-mpm/drivers/char/random.c |  146 -----------------------------------------
>  1 files changed, 146 deletions(-)
> 
> diff -puN drivers/char/random.c~kill-sha-variants drivers/char/random.c
> --- tiny/drivers/char/random.c~kill-sha-variants	2004-03-20 13:38:34.000000000 -0600
> +++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:34.000000000 -0600
> @@ -885,9 +885,6 @@ EXPORT_SYMBOL(add_disk_randomness);
>  #define HASH_BUFFER_SIZE 5
>  #define HASH_EXTRA_SIZE 80
>  
> -/* Various size/speed tradeoffs are available.  Choose 0..3. */
> -#define SHA_CODE_SIZE 0


So we go from "fast" to "I hope it gets faster in the future"?

	Jeff

Re: [PATCH 2/22] /dev/random: Cleanup sleep logic

[Matt Mackall]

On Thu, Mar 25, 2004 at 04:14:04PM -0800, Andrew Morton wrote:
> Matt Mackall <mpm@selenic.com> wrote:
> >
> > Cleanup /dev/random sleep logic
> > 
> > Original code checked in output pool rather than input pool for wakeup
> 
> So what is the rationale for switching it over to the primary pool?

Because the primary (input) pool is where entropy appears. If we check
the secondary (output) pool, we can go to sleep when there's still
entropy available.

-- 
Matt Mackall : http://www.selenic.com : Linux development and consulting

Re: [PATCH 3/22] /dev/random: remove broken resizing sysctl

[Matt Mackall]

On Thu, Mar 25, 2004 at 04:15:23PM -0800, Andrew Morton wrote:
> Matt Mackall <mpm@selenic.com> wrote:
> >
> > /dev/random  remove broken resizing sysctl
> 
> This could break things.  Shouldn't we leave the /proc entry there
> and print a friendly message in the sysctl handler?

I could do that, yes. I would be really surprised if there were any
users, however.

-- 
Matt Mackall : http://www.selenic.com : Linux development and consulting

Re: [PATCH 15/22] /dev/random: kill unrolled SHA code

[Matt Mackall]

On Thu, Mar 25, 2004 at 08:43:13PM -0500, Jeff Garzik wrote:
> Matt Mackall wrote:
> >/dev/random  kill unrolled SHA code
> >
> >Kill the unrolled SHA variants. In the future, we can use cryptoapi
> >for faster hash functions.
> >
> > tiny-mpm/drivers/char/random.c |  146 
> > 1 files changed, 146 deletions(-)
> >
> >diff -puN drivers/char/random.c~kill-sha-variants drivers/char/random.c
> >13:38:34.000000000 -0600
> >+++ tiny-mpm/drivers/char/random.c	2004-03-20 13:38:34.000000000 -0600
> >@@ -885,9 +885,6 @@ EXPORT_SYMBOL(add_disk_randomness);
> > #define HASH_BUFFER_SIZE 5
> > #define HASH_EXTRA_SIZE 80
> > 
> >-/* Various size/speed tradeoffs are available.  Choose 0..3. */
> >-#define SHA_CODE_SIZE 0
> 
> 
> So we go from "fast" to "I hope it gets faster in the future"?

No, we go from "moderately fast and dead code duplicated in /crypto"
to "same speed and one step closer to merging with /crypto". This bit
can be dropped for now, I've got the other bits deeper in my queue.

-- 
Matt Mackall : http://www.selenic.com : Linux development and consulting

Re: [PATCH 15/22] /dev/random: kill unrolled SHA code

[Jamie Lokier]

Matt Mackall wrote:
> > So we go from "fast" to "I hope it gets faster in the future"?
> 
> No, we go from "moderately fast and dead code duplicated in /crypto"
> to "same speed and one step closer to merging with /crypto". This bit
> can be dropped for now, I've got the other bits deeper in my queue.

I suggest applying this patch.  All it does is delete unused code.

-- Jamie

Re: [PATCH 21/22] /dev/random: kill batching of entropy mixing

[Jamie Lokier]

Matt Mackall wrote:
> Rather than batching up entropy samples, resulting in longer lock hold
> times when we actually process the samples, mix in samples
> immediately. The trickle code should eliminate almost all the
> additional interrupt-time overhead this would otherwise incur, with or
> without locking.

What do you mean by "the trickle code"?  I didn't see anything in your
patch set which makes the interrupt-time overhead faster.

-- Jamie

Re: [PATCH 21/22] /dev/random: kill batching of entropy mixing

[Matt Mackall]

On Sat, Mar 27, 2004 at 01:52:45PM +0000, Jamie Lokier wrote:
> Matt Mackall wrote:
> > Rather than batching up entropy samples, resulting in longer lock hold
> > times when we actually process the samples, mix in samples
> > immediately. The trickle code should eliminate almost all the
> > additional interrupt-time overhead this would otherwise incur, with or
> > without locking.
> 
> What do you mean by "the trickle code"?  I didn't see anything in your
> patch set which makes the interrupt-time overhead faster.

This code which is in the existing driver to prevent pathological lock
contention on large SMP:

        /* if over the trickle threshold, use only 1 in 4096 samples
	*/
        if ( input_pool.entropy_count > trickle_thresh &&
             (__get_cpu_var(trickle_count)++ & 0xfff))
                return;

-- 
Matt Mackall : http://www.selenic.com : Linux development and consulting