Skip to contentSkip to conversation

random: code cleanups

PATCH Applied Greg Price 2 participants 22 messages Nov 13, 2013 – Dec 7, 2013 Random number driver

lore
Share & tools
lore

Greg Price

author
#0 lore raw

v2 cover random: code cleanups

This series has my cleanups rebased onto the random.git tree, at v3.11-20-g392a546.

Four of the patches touch comments only. Three simplify code without changing its behavior (total diffstat: 32 insertions, 64 deletions). One drops a use of the lock where it doesn't now protect anything, and one tightens slightly a bound on a sysctl value to avoid a pathological case.

The bugfix that was in v1 was taken care of by Peter in a283b5c45 ("random: allow fractional bits to be tracked").

Cheers,
Greg

Greg Price (9):
random: fix typos / spelling errors in comments
random: fix comment on proc_do_uuid
random: fix description of get_random_bytes
random: simplify loop in random_read
random: fix comment on "account"
random: simplify accounting logic
random: forget lock in lockless accounting
random: tighten bound on random_read_wakeup_thresh
random: simplify accounting code

 drivers/char/random.c | 144 +++++++++++++++++++++-----------------------------
 1 file changed, 60 insertions(+), 84 deletions(-)
Signature · 1 line
1.8.3.2
author
#1 lore raw

PATCH v2 1/9 random: fix typos / spelling errors in comments

Cc "Theodore Ts'o" <[email protected]>
---
 drivers/char/random.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
drivers/char/random.c +3 -3
index cdf4cfb..ed72be5 100644
@@ -308,7 +308,7 @@ static int random_read_wakeup_thresh = 64;
 static int random_write_wakeup_thresh = 28 * OUTPUT_POOL_WORDS;
 
 /*
- * The minimum number of seconds between urandom pool resending.  We
+ * The minimum number of seconds between urandom pool reseeding.  We
  * do this to limit the amount of entropy that can be drained from the
  * input pool even if there are heavy demands on /dev/urandom.
  */
@@ -325,7 +325,7 @@ static int random_min_urandom_seed = 60;
  * Register.  (See M. Matsumoto & Y. Kurita, 1992.  Twisted GFSR
  * generators.  ACM Transactions on Modeling and Computer Simulation
  * 2(3):179-194.  Also see M. Matsumoto & Y. Kurita, 1994.  Twisted
- * GFSR generators II.  ACM Transactions on Mdeling and Computer
+ * GFSR generators II.  ACM Transactions on Modeling and Computer
  * Simulation 4:254-266)
  *
  * Thanks to Colin Plumb for suggesting this.
@@ -1040,7 +1040,7 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
 		sha_transform(hash.w, (__u8 *)(r->pool + i), workspace);
 
 	/*
-	 * If we have a architectural hardware random number
+	 * If we have an architectural hardware random number
 	 * generator, mix that in, too.
 	 */
 	for (i = 0; i < LONGS(20); i++) {
Signature · 1 line
1.8.3.2
author
#3 lore raw

PATCH v2 2/9 random: fix comment on proc_do_uuid

In reply to Greg Price

There's only one function here now, as uuid_strategy is long gone. Also make the bit about "If accesses via ..." clearer.

Cc "Theodore Ts'o" <[email protected]>
---
 drivers/char/random.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
drivers/char/random.c +4 -4
index ed72be5..e11ee4e 100644
@@ -1516,13 +1516,13 @@ static int max_write_thresh = INPUT_POOL_WORDS * 32;
 static char sysctl_bootid[16];
 
 /*
- * These functions is used to return both the bootid UUID, and random
+ * This function is 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.
  *
- * If the user accesses this via the proc interface, it will be returned
- * as an ASCII string in the standard UUID format.  If accesses via the
- * sysctl system call, it is returned as 16 bytes of binary data.
+ * If the user accesses this via the proc interface, the UUID will be
+ * returned as an ASCII string in the standard UUID format; if via the
+ * sysctl system call, as 16 bytes of binary data.
  */
 static int proc_do_uuid(struct ctl_table *table, int write,
 			void __user *buffer, size_t *lenp, loff_t *ppos)
Signature · 1 line
1.8.3.2
author
#5 lore raw

PATCH v2 3/9 random: fix description of get_random_bytes

In reply to Greg Price

After this remark was written, commit d2e7c96af added a use of arch_get_random_long() inside the get_random_bytes codepath. The main point stands, but it needs to be reworded.

Cc "Theodore Ts'o" <[email protected]>
---
 drivers/char/random.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)
drivers/char/random.c +3 -2
index e11ee4e..6d3627d 100644
@@ -1174,8 +1174,9 @@ static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
 /*
  * This function is the exported kernel interface.  It returns some
  * number of good random numbers, suitable for key generation, seeding
- * TCP sequence numbers, etc.  It does not use the hw random number
- * generator, if available; use get_random_bytes_arch() for that.
+ * TCP sequence numbers, etc.  It does not rely on the hardware random
+ * number generator.  For random bytes direct from the hardware RNG
+ * (when available), use get_random_bytes_arch().
  */
 void get_random_bytes(void *buf, int nbytes)
 {
Signature · 1 line
1.8.3.2
author
#7 lore raw

PATCH v2 4/9 random: simplify loop in random_read

In reply to Greg Price

The loop condition never changes until just before a break, so we might as well write it as a constant. Also since v2.6.33-rc7~40^2~2 ("random: drop weird m_time/a_time manipulation") we don't do anything after the loop finishes, so the 'break's might as well return directly. Some other simplifications.

The behavior should be identical except that I've changed a debug message.

Cc "Theodore Ts'o" <[email protected]>
---
 drivers/char/random.c | 57 ++++++++++++++++-----------------------------------
 1 file changed, 18 insertions(+), 39 deletions(-)
drivers/char/random.c +18 -39
index 6d3627d..cf1357b 100644
@@ -1289,53 +1289,32 @@ void rand_initialize_disk(struct gendisk *disk)
 static ssize_t
 random_read(struct file *file, char __user *buf, size_t nbytes, loff_t *ppos)
 {
-	ssize_t n, retval = 0, count = 0;
+	ssize_t n;
 
 	if (nbytes == 0)
 		return 0;
 
-	while (nbytes > 0) {
-		n = nbytes;
-		if (n > SEC_XFER_SIZE)
-			n = SEC_XFER_SIZE;
-
-		n = extract_entropy_user(&blocking_pool, buf, n);
-
-		if (n < 0) {
-			retval = n;
-			break;
-		}
-
+	nbytes = min_t(size_t, nbytes, SEC_XFER_SIZE);
+	while (1) {
+		n = extract_entropy_user(&blocking_pool, buf, nbytes);
+		if (n < 0)
+			return n;
 		trace_random_read(n*8, (nbytes-n)*8,
 				  ENTROPY_BITS(&blocking_pool),
 				  ENTROPY_BITS(&input_pool));
-
-		if (n == 0) {
-			if (file->f_flags & O_NONBLOCK) {
-				retval = -EAGAIN;
-				break;
-			}
-
-			wait_event_interruptible(random_read_wait,
-				ENTROPY_BITS(&input_pool) >=
-				random_read_wakeup_thresh);
-
-			if (signal_pending(current)) {
-				retval = -ERESTARTSYS;
-				break;
-			}
-
-			continue;
-		}
-
-		count += n;
-		buf += n;
-		nbytes -= n;
-		break;		/* This break makes the device work */
-				/* like a named pipe */
+		if (n > 0)
+			return n;
+		/* Pool is (near) empty.  Maybe wait and retry. */
+
+		if (file->f_flags & O_NONBLOCK)
+			return -EAGAIN;
+
+		wait_event_interruptible(random_read_wait,
+			ENTROPY_BITS(&input_pool) >=
+			random_read_wakeup_thresh);
+		if (signal_pending(current))
+			return -ERESTARTSYS;
 	}
-
-	return (count ? count : retval);
 }
 
 static ssize_t
Signature · 1 line
1.8.3.2
author
#10 lore raw

PATCH v2 5/9 random: fix comment on "account"

In reply to Greg Price

This comment didn't quite keep up as extract_entropy() was split into four functions. Put each bit by the function it describes.

Cc "Theodore Ts'o" <[email protected]>
---
 drivers/char/random.c | 31 +++++++++++++++++++++----------
 1 file changed, 21 insertions(+), 10 deletions(-)
drivers/char/random.c +21 -10
index cf1357b..fe7ecdd 100644
@@ -962,17 +962,9 @@ static void push_to_pool(struct work_struct *work)
 }
 
 /*
- * These functions extracts randomness from the "entropy pool", and
- * returns it in a buffer.
- *
- * 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.
+ * This function decides how many bytes to actually take from the
+ * given pool, and also debits the entropy count accordingly.
  */
-
 static size_t account(struct entropy_store *r, size_t nbytes, int min,
 		      int reserved)
 {
@@ -1022,6 +1014,12 @@ retry:
 	return ibytes;
 }
 
+/*
+ * This function does the actual extraction for extract_entropy and
+ * extract_entropy_user.
+ *
+ * Note: we assume that .poolwords is a multiple of 16 words.
+ */
 static void extract_buf(struct entropy_store *r, __u8 *out)
 {
 	int i;
@@ -1083,6 +1081,15 @@ static void extract_buf(struct entropy_store *r, __u8 *out)
 	memset(&hash, 0, sizeof(hash));
 }
 
+/*
+ * This function extracts randomness from the "entropy pool", and
+ * returns it in a buffer.
+ *
+ * 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.
+ */
 static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 				 size_t nbytes, int min, int reserved)
 {
@@ -1133,6 +1140,10 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
 	return ret;
 }
 
+/*
+ * This function extracts randomness from the "entropy pool", and
+ * returns it in a userspace buffer.
+ */
 static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
 				    size_t nbytes)
 {
Signature · 1 line
1.8.3.2
author
#12 lore raw

PATCH v2 6/9 random: simplify accounting logic

In reply to Greg Price

This logic is exactly equivalent to the old logic, but it should be easier to see what it's doing.

The equivalence depends on one fact from outside this function:
when 'r->limit' is false, 'reserved' is zero. (Well, two facts; the other is that 'reserved' is never negative.)

Cc "Theodore Ts'o" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
---
 drivers/char/random.c | 12 ++++--------
 1 file changed, 4 insertions(+), 8 deletions(-)
drivers/char/random.c +4 -8
index fe7ecdd..5dffca8 100644
@@ -988,14 +988,10 @@ retry:
 		ibytes = 0;
 	} else {
 		/* If limited, never pull more than available */
-		if (r->limit && ibytes + reserved >= have_bytes)
-			ibytes = have_bytes - reserved;
-
-		if (have_bytes >= ibytes + reserved)
-			entropy_count -= ibytes << (ENTROPY_SHIFT + 3);
-		else
-			entropy_count = reserved << (ENTROPY_SHIFT + 3);
-
+		if (r->limit)
+			ibytes = min_t(size_t, ibytes, have_bytes - reserved);
+		entropy_count = max_t(int, 0,
+			    entropy_count - (ibytes << (ENTROPY_SHIFT + 3)));
 		if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
 			goto retry;
 
Signature · 1 line
1.8.3.2
author
#14 lore raw

PATCH v2 7/9 random: forget lock in lockless accounting

In reply to Greg Price

The only mutable data accessed here is ->entropy_count, but since 902c098a3 ("random: use lockless techniques in the interrupt path") that member isn't protected by the lock anyway. Since 10b3a32d2 ("random: fix accounting race condition") we use cmpxchg to protect our accesses to ->entropy_count here. Drop the use of the lock.

Cc Jiri Kosina <[email protected]>
Cc "Theodore Ts'o" <[email protected]>
---
 drivers/char/random.c | 4 ----
 1 file changed, 4 deletions(-)
drivers/char/random.c +0 -4
index 5dffca8..1f43f9e 100644
@@ -974,9 +974,6 @@ static size_t account(struct entropy_store *r, size_t nbytes, int min,
 	int entropy_count, orig;
 	size_t ibytes;
 
-	/* Hold lock while accounting */
-	spin_lock_irqsave(&r->lock, flags);
-
 	BUG_ON(r->entropy_count > r->poolinfo->poolfracbits);
 
 	/* Can we pull enough? */
@@ -999,7 +996,6 @@ retry:
 		    < random_write_wakeup_thresh)
 			wakeup_write = 1;
 	}
-	spin_unlock_irqrestore(&r->lock, flags);
 
 	trace_debit_entropy(r->name, 8 * ibytes);
 	if (wakeup_write) {
Signature · 1 line
1.8.3.2
author
#16 lore raw

PATCH v2 8/9 random: tighten bound on random_read_wakeup_thresh

In reply to Greg Price

We use this value in a few places other than its literal meaning, in particular in _xfer_secondary_pool() as a minimum number of bits to pull from the input pool at a time into either output pool. It doesn't make sense to pull more bits than the whole size of an output pool.

We could and possibly should separate the quantities "how much should the input pool have to have to wake up /dev/random readers" and "how much should we transfer from the input to an output pool at a time", but nobody is likely to be sad they can't set the first quantity to more than 1024 bits, so for now just limit them both.

Cc "Theodore Ts'o" <[email protected]>
---
 drivers/char/random.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
drivers/char/random.c +1 -1
index 1f43f9e..865c8db 100644
@@ -1494,7 +1494,7 @@ EXPORT_SYMBOL(generate_random_uuid);
 #include <linux/sysctl.h>
 
 static int min_read_thresh = 8, min_write_thresh;
-static int max_read_thresh = INPUT_POOL_WORDS * 32;
+static int max_read_thresh = OUTPUT_POOL_WORDS * 32;
 static int max_write_thresh = INPUT_POOL_WORDS * 32;
 static char sysctl_bootid[16];
 
Signature · 1 line
1.8.3.2
author
#18 lore raw

PATCH v2 9/9 random: simplify accounting code

In reply to Greg Price

With this we handle "reserved" in just one place. As a bonus the code becomes less nested, and the "wakeup_write" flag variable becomes unnecessary. The variable "flags" was already unused.

This code behaves identically to the previous version except in two pathological cases that don't occur. If the argument "nbytes" is already less than "min", then we didn't previously enforce "min". If r->limit is false while "reserved" is nonzero, then we previously applied "reserved" in checking whether we had enough bits, even though we don't apply it to actually limit how many we take. The callers of account() never exercise either of these cases.

Before the previous commit, it was possible for "nbytes" to be less than "min" if userspace chose a pathological configuration, but no longer.

Cc "Theodore Ts'o" <[email protected]>
Cc Jiri Kosina <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
---
 drivers/char/random.c | 27 ++++++++++-----------------
 1 file changed, 10 insertions(+), 17 deletions(-)
drivers/char/random.c +10 -17
index 865c8db..87b41b0 100644
@@ -968,8 +968,6 @@ static void push_to_pool(struct work_struct *work)
 static size_t account(struct entropy_store *r, size_t nbytes, int min,
 		      int reserved)
 {
-	unsigned long flags;
-	int wakeup_write = 0;
 	int have_bytes;
 	int entropy_count, orig;
 	size_t ibytes;
@@ -981,24 +979,19 @@ retry:
 	entropy_count = orig = ACCESS_ONCE(r->entropy_count);
 	have_bytes = entropy_count >> (ENTROPY_SHIFT + 3);
 	ibytes = nbytes;
-	if (have_bytes < min + reserved) {
+	/* If limited, never pull more than available */
+	if (r->limit)
+		ibytes = min_t(size_t, ibytes, have_bytes - reserved);
+	if (ibytes < min)
 		ibytes = 0;
-	} else {
-		/* If limited, never pull more than available */
-		if (r->limit)
-			ibytes = min_t(size_t, ibytes, have_bytes - reserved);
-		entropy_count = max_t(int, 0,
-			    entropy_count - (ibytes << (ENTROPY_SHIFT + 3)));
-		if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
-			goto retry;
-
-		if ((r->entropy_count >> ENTROPY_SHIFT)
-		    < random_write_wakeup_thresh)
-			wakeup_write = 1;
-	}
+	entropy_count = max_t(int, 0,
+			      entropy_count - (ibytes << (ENTROPY_SHIFT + 3)));
+	if (ibytes && cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
+		goto retry;
 
 	trace_debit_entropy(r->name, 8 * ibytes);
-	if (wakeup_write) {
+	if (ibytes &&
+	    (r->entropy_count >> ENTROPY_SHIFT) < random_write_wakeup_thresh) {
 		wake_up_interruptible(&random_write_wait);
 		kill_fasync(&fasync, SIGIO, POLL_OUT);
 	}
Signature · 1 line
1.8.3.2
maintainer
#8 lore raw

Re: [PATCH 4/9] random: simplify loop in random_read

In reply to Greg Price
Quoted 11 lines · Greg Price

The loop condition never changes until just before a break, so we might as well write it as a constant. Also since v2.6.33-rc7~40^2~2 ("random: drop weird m_time/a_time manipulation") we don't do anything after the loop finishes, so the 'break's might as well return directly. Some other simplifications.

The behavior should be identical except that I've changed a debug message.

Cc "Theodore Ts'o" <[email protected]>

Applied, although I slightly edited the commit description the the debug message mentioned in the description was removed since the first version of your patch series, and it wasn't updated as part of the rebase.

- Ted

maintainer Applied
#13 lore raw

Re: [PATCH 6/9] random: simplify accounting logic

In reply to Greg Price
Quoted 6 lines · Greg Price

This logic is exactly equivalent to the old logic, but it should be easier to see what it's doing.

The equivalence depends on one fact from outside this function:
when 'r->limit' is false, 'reserved' is zero. (Well, two facts; the other is that 'reserved' is never negative.)

Applied, thanks.

- Ted

maintainer Applied
#15 lore raw

Re: [PATCH 7/9] random: forget lock in lockless accounting

In reply to Greg Price
Quoted 5 lines · Greg Price

The only mutable data accessed here is ->entropy_count, but since 902c098a3 ("random: use lockless techniques in the interrupt path") that member isn't protected by the lock anyway. Since 10b3a32d2 ("random: fix accounting race condition") we use cmpxchg to protect our accesses to ->entropy_count here. Drop the use of the lock.

Applied, with a slight change to clarify the commit description:

    The only mutable data accessed here is ->entropy_count, but since
    10b3a32d2 ("random: fix accounting race condition") we use cmpxchg to
    protect our accesses to ->entropy_count here.  Drop the use of the
    lock.

Thanks!

- Ted

author
#9 lore raw

Re: [PATCH 4/9] random: simplify loop in random_read

In reply to Theodore Ts'o
Quoted 4 lines · Theodore Ts'o

Applied, although I slightly edited the commit description the the debug message mentioned in the description was removed since the first version of your patch series, and it wasn't updated as part of the rebase.

Ah, good catch. Thanks!

Greg

maintainer Applied
#17 lore raw

Re: [PATCH 8/9] random: tighten bound on random_read_wakeup_thresh

In reply to Greg Price
Quoted 6 lines · Greg Price

We use this value in a few places other than its literal meaning, in particular in _xfer_secondary_pool() as a minimum number of bits to pull from the input pool at a time into either output pool. It doesn't make sense to pull more bits than the whole size of an output pool.

Quoted 8 lines

We could and possibly should separate the quantities "how much should the input pool have to have to wake up /dev/random readers" and "how much should we transfer from the input to an output pool at a time", but nobody is likely to be sad they can't set the first quantity to more than 1024 bits, so for now just limit them both.

Cc "Theodore Ts'o" <[email protected]>

Thanks, applied.

- Ted

maintainer
#19 lore raw

Re: [PATCH 9/9] random: simplify accounting code

In reply to Greg Price

drivers/char/random.c retry: · line 990

Quoted 4 lines · Greg Price
drivers/char/random.c +4 -0
+	entropy_count = max_t(int, 0,
+			      entropy_count - (ibytes << (ENTROPY_SHIFT + 3)));
+	if (ibytes && cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
+		goto retry;

I wonder if we would be better dropping the test for ibytes here, so the above condition reads:

	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
		goto retry;

It further simplifies the code, and it means that if we it turns out that ibytes is zero (meaning there was no entropy available) but some additional entropy comes in, we might acutally end up retrying and successfully grabbing that entropy for the caller.

- Ted

author
#20 lore raw

Re: [PATCH 9/9] random: simplify accounting code

Quoted 7 lines · Theodore Ts'o

drivers/char/random.c retry: · line 990

Quoted 2 lines · Greg Price
drivers/char/random.c +2 -0
+	if (ibytes && cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
+		goto retry;

I wonder if we would be better dropping the test for ibytes here, so the above condition reads:

Quoted 7 lines
	if (cmpxchg(&r->entropy_count, orig, entropy_count) != orig)
		goto retry;

It further simplifies the code, and it means that if we it turns out that ibytes is zero (meaning there was no entropy available) but some additional entropy comes in, we might acutally end up retrying and successfully grabbing that entropy for the caller.

Sure, that'd be reasonable. I didn't do that mainly because I wanted to preserve existing behavior wherever possible in these cleanups, to make them easy to read and review.

Greg

maintainer
#21 lore raw

Re: [PATCH 9/9] random: simplify accounting code

Quoted 4 lines · Greg Price

Sure, that'd be reasonable. I didn't do that mainly because I wanted to preserve existing behavior wherever possible in these cleanups, to make them easy to read and review.

I'll make that change and apply this patch, thanks.

- Ted