/dev/random: Assorted fixes and cleanups

PATCH In review Matt Mackall 4 participants 33 messages Mar 25, 2004 – Mar 27, 2004

Subsystems (2)

Proc sysctl Random number driver

lore

Share & tools

lore

Matt Mackall

author

2004-03-25 23:58 UTC #2 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~fix-random-wait +11 ~~-12~~

diff -puN drivers/char/random.c~fix-random-wait drivers/char/random.c
@@ -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;
 		}

Matt Mackall

author

2004-03-25 23:58 UTC #4 lore raw

PATCH 4/22 /dev/random: remove outdated RNDGETPOOL ioctl

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~kill-getstate +2 ~~-38~~

diff -puN drivers/char/random.c~kill-getstate drivers/char/random.c
@@ -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;

include/linux/compat_ioctl.h renamed from include/linux/compat_ioctl.h~kill-getstate +0 -1

diff -puN include/linux/compat_ioctl.h~kill-getstate include/linux/compat_ioctl.h
@@ -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)

include/linux/random.h renamed from include/linux/random.h~kill-getstate +1 -4

diff -puN include/linux/random.h~kill-getstate include/linux/random.h
@@ -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.)
  */

Matt Mackall

author

2004-03-26 00:00 UTC #1 lore raw

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

In reply to Matt Mackall

Simplify entropy debugging

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

drivers/char/random.c renamed from drivers/char/random.c~debug-cleanup +10 ~~-37~~

diff -puN drivers/char/random.c~debug-cleanup drivers/char/random.c
@@ -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;
 		}

Matt Mackall

author

2004-03-26 00:01 UTC #10 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~debit-entropy +17 ~~-13~~

diff -puN drivers/char/random.c~debit-entropy drivers/char/random.c
@@ -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);
 }

Matt Mackall

author

2004-03-26 00:01 UTC #9 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~extract-min-max +23 ~~-15~~

diff -puN drivers/char/random.c~extract-min-max drivers/char/random.c
@@ -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);
 }

Matt Mackall

author

2004-03-26 00:01 UTC #13 lore raw

PATCH 13/22 /dev/random: kill extract_timer_state

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~kill-extract-state +0 -3

diff -puN drivers/char/random.c~kill-extract-state drivers/char/random.c
@@ -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);

Matt Mackall

author

2004-03-26 00:01 UTC #5 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~pool-rename +56 ~~-62~~

diff -puN drivers/char/random.c~pool-rename drivers/char/random.c
@@ -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 */

Matt Mackall

author

2004-03-26 00:01 UTC #8 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~bug-on-grb +2 -7

diff -puN drivers/char/random.c~bug-on-grb drivers/char/random.c
@@ -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);

Matt Mackall

author

2004-03-26 00:02 UTC #0 lore raw

cover /dev/random: Assorted fixes and cleanups

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.

Matt Mackall

author

2004-03-26 00:02 UTC #3 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~kill-pool-resize +3 ~~-85~~

diff -puN drivers/char/random.c~kill-pool-resize drivers/char/random.c
@@ -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 */

include/linux/sysctl.h renamed from include/linux/sysctl.h~kill-pool-resize +0 -1

diff -puN include/linux/sysctl.h~kill-pool-resize include/linux/sysctl.h
@@ -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,

Matt Mackall

author

2004-03-26 00:04 UTC #15 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~kill-sha-variants +0 ~~-146~~

diff -puN drivers/char/random.c~kill-sha-variants drivers/char/random.c
@@ -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
 
 /*********************************************************************
  *

Matt Mackall

author

2004-03-26 00:04 UTC #18 lore raw

PATCH 18/22 /dev/random: bitop cleanup

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~ln-to-fls +1 ~~-41~~

diff -puN drivers/char/random.c~ln-to-fls drivers/char/random.c
@@ -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);
 }

Matt Mackall

author

2004-03-26 00:04 UTC #19 lore raw

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

/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(-)

drivers/char/random.c renamed from drivers/char/random.c~random-sched-clock +9 ~~-12~~

diff -puN drivers/char/random.c~random-sched-clock drivers/char/random.c
@@ -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)

Matt Mackall

author

2004-03-26 00:04 UTC #16 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~random-waitqueue +0 ~~-10~~

diff -puN drivers/char/random.c~random-waitqueue drivers/char/random.c
@@ -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;

Matt Mackall

author

2004-03-26 00:05 UTC #12 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~nonblocking-pool +17 ~~-15~~

diff -puN drivers/char/random.c~nonblocking-pool drivers/char/random.c
@@ -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);
 }

Matt Mackall

author

2004-03-26 00:08 UTC #22 lore raw

PATCH 22/22 /dev/random: update credits

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~random-credit +2 -2

diff -puN drivers/char/random.c~random-credit drivers/char/random.c
@@ -1,8 +1,8 @@
 /*
  * random.c -- A strong random number generator
  *
- * Version 1.89, last modified 19-Sep-99
- * 
+ * Version 1.99  Matt Mackall <[email protected]> Oct 2003
+ *
  * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  All
  * rights reserved.
  *

Matt Mackall

author

2004-03-26 00:16 UTC #14 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~kill-md5 +12 ~~-148~~

diff -puN drivers/char/random.c~kill-md5 drivers/char/random.c
@@ -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 */
 }

Matt Mackall

author

2004-03-26 00:17 UTC #20 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~kill-rotate +7 ~~-33~~

diff -puN drivers/char/random.c~kill-rotate drivers/char/random.c
@@ -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;
 	}

Matt Mackall

author

2004-03-26 00:17 UTC #21 lore raw

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

/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(-)

drivers/char/random.c renamed from drivers/char/random.c~kill-batching +19 ~~-131~~

diff -puN drivers/char/random.c~kill-batching drivers/char/random.c
@@ -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);

include/linux/random.h renamed from include/linux/random.h~kill-batching +0 -2

diff -puN include/linux/random.h~kill-batching include/linux/random.h
@@ -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);

Matt Mackall

author

2004-03-26 00:29 UTC #17 lore raw

PATCH 17/22 /dev/random: minor shrinkage

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~shrink-random +12 ~~-14~~

diff -puN drivers/char/random.c~shrink-random drivers/char/random.c
@@ -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;

Andrew Morton

2004-03-26 00:32 UTC #28 lore raw

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

In reply to Matt Mackall

Quoted 2 lines · Matt Mackall

Remove RNDGETPOOL ioctl,

ditto.

Andrew Morton

2004-03-26 00:32 UTC #29 lore raw

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

In reply to Matt Mackall

Quoted 2 lines · Matt Mackall

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

Andrew Morton

2004-03-26 01:07 UTC #31 lore raw

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

In reply to Matt Mackall

Quoted 4 lines · Matt Mackall

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?

Matt Mackall

author

2004-03-26 01:11 UTC #11 lore raw

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

In reply to 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(-)

drivers/char/random.c renamed from drivers/char/random.c~reserved-in-struct +3 -1

diff -puN drivers/char/random.c~reserved-in-struct drivers/char/random.c
@@ -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);

Matt Mackall

author

2004-03-26 01:14 UTC #6 lore raw

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

In reply to Matt Mackall

/dev/random simplify pool initialization

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

drivers/char/random.c renamed from drivers/char/random.c~pool-init +35 ~~-51~~

diff -puN drivers/char/random.c~pool-init drivers/char/random.c
@@ -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 */

Matt Mackall

author

2004-03-26 01:24 UTC #7 lore raw

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

/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(-)

drivers/char/random.c renamed from drivers/char/random.c~kill-extract-secondary +6 ~~-14~~

diff -puN drivers/char/random.c~kill-extract-secondary drivers/char/random.c
@@ -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

Jeff Garzik

2004-03-26 01:43 UTC #25 lore raw

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

In reply to Matt Mackall

Quoted 12 lines · 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

drivers/char/random.c EXPORT_SYMBOL(add_disk_randomness); · line 889

Quoted 5 lines

drivers/char/random.c renamed from drivers/char/random.c~kill-sha-variants +0 -2

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

Matt Mackall

author

2004-03-26 03:50 UTC #32 lore raw

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

In reply to Andrew Morton

Quoted 7 lines · Andrew Morton

Quoted 4 lines · Matt Mackall
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.

Signature · 1 line

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

Matt Mackall

author

2004-03-26 03:53 UTC #30 lore raw

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

In reply to Andrew Morton

Quoted 6 lines · Andrew Morton

Quoted 2 lines · Matt Mackall
/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.

Signature · 1 line

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

Matt Mackall

author

2004-03-26 03:59 UTC #26 lore raw

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

In reply to Jeff Garzik

Quoted 16 lines · Jeff Garzik

Quoted 15 lines · 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 13:38:34.000000000 -0600
+++ tiny-mpm/drivers/char/random.c 2004-03-20 13:38:34.000000000 -0600
drivers/char/random.c renamed from drivers/char/random.c~kill-sha-variants +0 -0
@@ -885,9 +885,6 @@ EXPORT_SYMBOL(add_disk_randomness);
 #define HASH_BUFFER_SIZE 5
 #define HASH_EXTRA_SIZE 80
 

Quoted 5 lines

drivers/char/random.c EXPORT_SYMBOL(add_disk_randomness); · line 889
Quoted 2 lines
drivers/char/random.c renamed from drivers/char/random.c~kill-sha-variants +0 -2
-/* 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.

Signature · 1 line

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

Jamie Lokier

2004-03-27 13:49 UTC #27 lore raw

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

Quoted 5 lines · Matt Mackall

Quoted 1 line
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

Jamie Lokier

2004-03-27 13:52 UTC #23 lore raw

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

In reply to Matt Mackall

Quoted 5 lines · Matt Mackall

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

Matt Mackall

author

2004-03-27 15:17 UTC #24 lore raw

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

Quoted 9 lines · Jamie Lokier

Quoted 5 lines · Matt Mackall
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;

Signature · 1 line

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