Re: [PATCH, RFC 03/12] random: Allow fractional bits to be tracked
On 09/22/2013 09:01 PM, Theodore Ts'o wrote: > I've added the following changes to this patch since upon testing, > there were some uses of r->entropy_count that were not properly > converted from using fractional bits to bits. > Thanks for catching that. -hpa -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH, RFC 03/12] random: Allow fractional bits to be tracked
I've added the following changes to this patch since upon testing,
there were some uses of r->entropy_count that were not properly
converted from using fractional bits to bits.
- Ted
diff --git a/drivers/char/random.c b/drivers/char/random.c
index 1547338..8654b7e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -286,6 +286,7 @@
* entropy_count, trickle_thresh
*/
#define ENTROPY_SHIFT 3
+#define ENTROPY_BITS(r) ((r)->entropy_count >> ENTROPY_SHIFT)
/*
* The minimum number of bits of entropy before we wake up a read on
@@ -618,7 +619,8 @@ retry:
r->initialized = 1;
}
- trace_credit_entropy_bits(r->name, nbits, entropy_count,
+ trace_credit_entropy_bits(r->name, nbits,
+ entropy_count >> ENTROPY_SHIFT,
r->entropy_total, _RET_IP_);
/* should we wake readers? */
@@ -695,7 +697,7 @@ static void add_timer_randomness(struct timer_rand_state
*state, unsigned num)
preempt_disable();
/* if over the trickle threshold, use only 1 in 4096 samples */
- if (input_pool.entropy_count > trickle_thresh &&
+ if (ENTROPY_BITS(_pool) > trickle_thresh &&
((__this_cpu_inc_return(trickle_count) - 1) & 0xfff))
goto out;
@@ -999,7 +1001,7 @@ static ssize_t extract_entropy(struct entropy_store *r,
void *buf,
r->last_data_init = true;
spin_unlock_irqrestore(>lock, flags);
trace_extract_entropy(r->name, EXTRACT_SIZE,
- r->entropy_count, _RET_IP_);
+ ENTROPY_BITS(r), _RET_IP_);
xfer_secondary_pool(r, EXTRACT_SIZE);
extract_buf(r, tmp);
spin_lock_irqsave(>lock, flags);
@@ -1008,7 +1010,7 @@ static ssize_t extract_entropy(struct entropy_store *r,
void *buf,
spin_unlock_irqrestore(>lock, flags);
}
- trace_extract_entropy(r->name, nbytes, r->entropy_count, _RET_IP_);
+ trace_extract_entropy(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
xfer_secondary_pool(r, nbytes);
nbytes = account(r, nbytes, min, reserved);
@@ -1041,7 +1043,7 @@ static ssize_t extract_entropy_user(struct entropy_store
*r, void __user *buf,
ssize_t ret = 0, i;
__u8 tmp[EXTRACT_SIZE];
- trace_extract_entropy_user(r->name, nbytes, r->entropy_count, _RET_IP_);
+ trace_extract_entropy_user(r->name, nbytes, ENTROPY_BITS(r), _RET_IP_);
xfer_secondary_pool(r, nbytes);
nbytes = account(r, nbytes, 0, 0);
@@ -1213,8 +1215,8 @@ random_read(struct file *file, char __user *buf, size_t
nbytes, loff_t *ppos)
DEBUG_ENT("sleeping?\n");
wait_event_interruptible(random_read_wait,
- input_pool.entropy_count >=
-random_read_wakeup_thresh);
+ ENTROPY_BITS(_pool) >=
+ random_read_wakeup_thresh);
DEBUG_ENT("awake\n");
@@ -1250,9 +1252,9 @@ random_poll(struct file *file, poll_table * wait)
poll_wait(file, _read_wait, wait);
poll_wait(file, _write_wait, wait);
mask = 0;
- if (input_pool.entropy_count >= random_read_wakeup_thresh)
+ if (ENTROPY_BITS(_pool) >= random_read_wakeup_thresh)
mask |= POLLIN | POLLRDNORM;
- if (input_pool.entropy_count < random_write_wakeup_thresh)
+ if (ENTROPY_BITS(_pool) < random_write_wakeup_thresh)
mask |= POLLOUT | POLLWRNORM;
return mask;
}
@@ -1303,7 +1305,7 @@ static long random_ioctl(struct file *f, unsigned int
cmd, unsigned long arg)
switch (cmd) {
case RNDGETENTCNT:
/* inherently racy, no point locking */
- ent_count = input_pool.entropy_count >> ENTROPY_SHIFT;
+ ent_count = ENTROPY_BITS(_pool);
if (put_user(ent_count, p))
return -EFAULT;
return 0;
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[PATCH, RFC 03/12] random: Allow fractional bits to be tracked
From: "H. Peter Anvin"
Allow fractional bits of entropy to be tracked by scaling the entropy
counter (fixed point). This will be used in a subsequent patch that
accounts for entropy lost due to overwrites.
Signed-off-by: H. Peter Anvin
Cc:
Signed-off-by: Theodore Ts'o
---
drivers/char/random.c | 118 ++
1 file changed, 81 insertions(+), 37 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index e973658..1547338 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -280,6 +280,14 @@
#define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
/*
+ * To allow fractional bits to be tracked, the following fields contain
+ * this many fractional bits:
+ *
+ * entropy_count, trickle_thresh
+ */
+#define ENTROPY_SHIFT 3
+
+/*
* The minimum number of bits of entropy before we wake up a read on
* /dev/random. Should be enough to do a significant reseed.
*/
@@ -296,8 +304,7 @@ static int random_write_wakeup_thresh = 128;
* When the input pool goes over trickle_thresh, start dropping most
* samples to avoid wasting CPU time and reduce lock contention.
*/
-
-static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;
+static const int trickle_thresh = (INPUT_POOL_WORDS * 28) << ENTROPY_SHIFT;
static DEFINE_PER_CPU(int, trickle_count);
@@ -311,8 +318,8 @@ static DEFINE_PER_CPU(int, trickle_count);
*/
static struct poolinfo {
- int poolbitshift, poolwords, poolbytes, poolbits;
-#define S(x) ilog2(x)+5, (x), (x)*4, (x)*32
+ int poolbitshift, poolwords, poolbytes, poolbits, poolfracbits;
+#define S(x) ilog2(x)+5, (x), (x)*4, (x)*32, (x) << (ENTROPY_SHIFT+5)
int tap1, tap2, tap3, tap4, tap5;
} poolinfo_table[] = {
/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
@@ -581,7 +588,9 @@ static void fast_mix(struct fast_pool *f, const void *in,
int nbytes)
}
/*
- * Credit (or debit) the entropy store with n bits of entropy
+ * Credit (or debit) the entropy store with n bits of entropy.
+ * Use credit_entropy_bits_safe() if the value comes from userspace
+ * or otherwise should be checked for extreme values.
*/
static void credit_entropy_bits(struct entropy_store *r, int nbits)
{
@@ -593,13 +602,13 @@ static void credit_entropy_bits(struct entropy_store *r,
int nbits)
DEBUG_ENT("added %d entropy credits to %s\n", nbits, r->name);
retry:
entropy_count = orig = ACCESS_ONCE(r->entropy_count);
- entropy_count += nbits;
+ entropy_count += nbits << ENTROPY_SHIFT;
if (entropy_count < 0) {
DEBUG_ENT("negative entropy/overflow\n");
entropy_count = 0;
- } else if (entropy_count > r->poolinfo->poolbits)
- entropy_count = r->poolinfo->poolbits;
+ } else if (entropy_count > r->poolinfo->poolfracbits)
+ entropy_count = r->poolinfo->poolfracbits;
if (cmpxchg(>entropy_count, orig, entropy_count) != orig)
goto retry;
@@ -613,12 +622,24 @@ retry:
r->entropy_total, _RET_IP_);
/* should we wake readers? */
- if (r == _pool && entropy_count >= random_read_wakeup_thresh) {
+ if (r == _pool &&
+ (entropy_count >> ENTROPY_SHIFT) >= random_read_wakeup_thresh) {
wake_up_interruptible(_read_wait);
kill_fasync(, SIGIO, POLL_IN);
}
}
+static void credit_entropy_bits_safe(struct entropy_store *r, int nbits)
+{
+ const int nbits_max = (int)(~0U >> (ENTROPY_SHIFT + 1));
+
+ /* Cap the value to avoid overflows */
+ nbits = min(nbits, nbits_max);
+ nbits = max(nbits, -nbits_max);
+
+ credit_entropy_bits(r, nbits);
+}
+
/*
*
* Entropy input management
@@ -813,8 +834,9 @@ static void xfer_secondary_pool(struct entropy_store *r,
size_t nbytes)
{
__u32 tmp[OUTPUT_POOL_WORDS];
- if (r->pull && r->entropy_count < nbytes * 8 &&
- r->entropy_count < r->poolinfo->poolbits) {
+ if (r->pull &&
+ r->entropy_count < (nbytes << (ENTROPY_SHIFT + 3)) &&
+ r->entropy_count < r->poolinfo->poolfracbits) {
/* If we're limited, always leave two wakeup worth's BITS */
int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
int bytes = nbytes;
@@ -826,7 +848,8 @@ static void xfer_secondary_pool(struct entropy_store *r,
size_t nbytes)
DEBUG_ENT("going to reseed %s with %d bits "
"(%zu of %d requested)\n",
- r->name, bytes * 8, nbytes * 8, r->entropy_count);
+ r->name, bytes * 8, nbytes * 8,
+ r->entropy_count >> ENTROPY_SHIFT);
bytes = extract_entropy(r->pull, tmp, bytes,
[PATCH, RFC 03/12] random: Allow fractional bits to be tracked
From: H. Peter Anvin h...@zytor.com
Allow fractional bits of entropy to be tracked by scaling the entropy
counter (fixed point). This will be used in a subsequent patch that
accounts for entropy lost due to overwrites.
Signed-off-by: H. Peter Anvin h...@linux.intel.com
Cc: sta...@vger.kernel.org
Signed-off-by: Theodore Ts'o ty...@mit.edu
---
drivers/char/random.c | 118 ++
1 file changed, 81 insertions(+), 37 deletions(-)
diff --git a/drivers/char/random.c b/drivers/char/random.c
index e973658..1547338 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -280,6 +280,14 @@
#define LONGS(x) (((x) + sizeof(unsigned long) - 1)/sizeof(unsigned long))
/*
+ * To allow fractional bits to be tracked, the following fields contain
+ * this many fractional bits:
+ *
+ * entropy_count, trickle_thresh
+ */
+#define ENTROPY_SHIFT 3
+
+/*
* The minimum number of bits of entropy before we wake up a read on
* /dev/random. Should be enough to do a significant reseed.
*/
@@ -296,8 +304,7 @@ static int random_write_wakeup_thresh = 128;
* When the input pool goes over trickle_thresh, start dropping most
* samples to avoid wasting CPU time and reduce lock contention.
*/
-
-static int trickle_thresh __read_mostly = INPUT_POOL_WORDS * 28;
+static const int trickle_thresh = (INPUT_POOL_WORDS * 28) ENTROPY_SHIFT;
static DEFINE_PER_CPU(int, trickle_count);
@@ -311,8 +318,8 @@ static DEFINE_PER_CPU(int, trickle_count);
*/
static struct poolinfo {
- int poolbitshift, poolwords, poolbytes, poolbits;
-#define S(x) ilog2(x)+5, (x), (x)*4, (x)*32
+ int poolbitshift, poolwords, poolbytes, poolbits, poolfracbits;
+#define S(x) ilog2(x)+5, (x), (x)*4, (x)*32, (x) (ENTROPY_SHIFT+5)
int tap1, tap2, tap3, tap4, tap5;
} poolinfo_table[] = {
/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
@@ -581,7 +588,9 @@ static void fast_mix(struct fast_pool *f, const void *in,
int nbytes)
}
/*
- * Credit (or debit) the entropy store with n bits of entropy
+ * Credit (or debit) the entropy store with n bits of entropy.
+ * Use credit_entropy_bits_safe() if the value comes from userspace
+ * or otherwise should be checked for extreme values.
*/
static void credit_entropy_bits(struct entropy_store *r, int nbits)
{
@@ -593,13 +602,13 @@ static void credit_entropy_bits(struct entropy_store *r,
int nbits)
DEBUG_ENT(added %d entropy credits to %s\n, nbits, r-name);
retry:
entropy_count = orig = ACCESS_ONCE(r-entropy_count);
- entropy_count += nbits;
+ entropy_count += nbits ENTROPY_SHIFT;
if (entropy_count 0) {
DEBUG_ENT(negative entropy/overflow\n);
entropy_count = 0;
- } else if (entropy_count r-poolinfo-poolbits)
- entropy_count = r-poolinfo-poolbits;
+ } else if (entropy_count r-poolinfo-poolfracbits)
+ entropy_count = r-poolinfo-poolfracbits;
if (cmpxchg(r-entropy_count, orig, entropy_count) != orig)
goto retry;
@@ -613,12 +622,24 @@ retry:
r-entropy_total, _RET_IP_);
/* should we wake readers? */
- if (r == input_pool entropy_count = random_read_wakeup_thresh) {
+ if (r == input_pool
+ (entropy_count ENTROPY_SHIFT) = random_read_wakeup_thresh) {
wake_up_interruptible(random_read_wait);
kill_fasync(fasync, SIGIO, POLL_IN);
}
}
+static void credit_entropy_bits_safe(struct entropy_store *r, int nbits)
+{
+ const int nbits_max = (int)(~0U (ENTROPY_SHIFT + 1));
+
+ /* Cap the value to avoid overflows */
+ nbits = min(nbits, nbits_max);
+ nbits = max(nbits, -nbits_max);
+
+ credit_entropy_bits(r, nbits);
+}
+
/*
*
* Entropy input management
@@ -813,8 +834,9 @@ static void xfer_secondary_pool(struct entropy_store *r,
size_t nbytes)
{
__u32 tmp[OUTPUT_POOL_WORDS];
- if (r-pull r-entropy_count nbytes * 8
- r-entropy_count r-poolinfo-poolbits) {
+ if (r-pull
+ r-entropy_count (nbytes (ENTROPY_SHIFT + 3))
+ r-entropy_count r-poolinfo-poolfracbits) {
/* If we're limited, always leave two wakeup worth's BITS */
int rsvd = r-limit ? 0 : random_read_wakeup_thresh/4;
int bytes = nbytes;
@@ -826,7 +848,8 @@ static void xfer_secondary_pool(struct entropy_store *r,
size_t nbytes)
DEBUG_ENT(going to reseed %s with %d bits
(%zu of %d requested)\n,
- r-name, bytes * 8, nbytes * 8, r-entropy_count);
+ r-name, bytes * 8, nbytes * 8,
+ r-entropy_count ENTROPY_SHIFT);
bytes = extract_entropy(r-pull, tmp, bytes,
Re: [PATCH, RFC 03/12] random: Allow fractional bits to be tracked
I've added the following changes to this patch since upon testing,
there were some uses of r-entropy_count that were not properly
converted from using fractional bits to bits.
- Ted
diff --git a/drivers/char/random.c b/drivers/char/random.c
index 1547338..8654b7e 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -286,6 +286,7 @@
* entropy_count, trickle_thresh
*/
#define ENTROPY_SHIFT 3
+#define ENTROPY_BITS(r) ((r)-entropy_count ENTROPY_SHIFT)
/*
* The minimum number of bits of entropy before we wake up a read on
@@ -618,7 +619,8 @@ retry:
r-initialized = 1;
}
- trace_credit_entropy_bits(r-name, nbits, entropy_count,
+ trace_credit_entropy_bits(r-name, nbits,
+ entropy_count ENTROPY_SHIFT,
r-entropy_total, _RET_IP_);
/* should we wake readers? */
@@ -695,7 +697,7 @@ static void add_timer_randomness(struct timer_rand_state
*state, unsigned num)
preempt_disable();
/* if over the trickle threshold, use only 1 in 4096 samples */
- if (input_pool.entropy_count trickle_thresh
+ if (ENTROPY_BITS(input_pool) trickle_thresh
((__this_cpu_inc_return(trickle_count) - 1) 0xfff))
goto out;
@@ -999,7 +1001,7 @@ static ssize_t extract_entropy(struct entropy_store *r,
void *buf,
r-last_data_init = true;
spin_unlock_irqrestore(r-lock, flags);
trace_extract_entropy(r-name, EXTRACT_SIZE,
- r-entropy_count, _RET_IP_);
+ ENTROPY_BITS(r), _RET_IP_);
xfer_secondary_pool(r, EXTRACT_SIZE);
extract_buf(r, tmp);
spin_lock_irqsave(r-lock, flags);
@@ -1008,7 +1010,7 @@ static ssize_t extract_entropy(struct entropy_store *r,
void *buf,
spin_unlock_irqrestore(r-lock, flags);
}
- trace_extract_entropy(r-name, nbytes, r-entropy_count, _RET_IP_);
+ trace_extract_entropy(r-name, nbytes, ENTROPY_BITS(r), _RET_IP_);
xfer_secondary_pool(r, nbytes);
nbytes = account(r, nbytes, min, reserved);
@@ -1041,7 +1043,7 @@ static ssize_t extract_entropy_user(struct entropy_store
*r, void __user *buf,
ssize_t ret = 0, i;
__u8 tmp[EXTRACT_SIZE];
- trace_extract_entropy_user(r-name, nbytes, r-entropy_count, _RET_IP_);
+ trace_extract_entropy_user(r-name, nbytes, ENTROPY_BITS(r), _RET_IP_);
xfer_secondary_pool(r, nbytes);
nbytes = account(r, nbytes, 0, 0);
@@ -1213,8 +1215,8 @@ random_read(struct file *file, char __user *buf, size_t
nbytes, loff_t *ppos)
DEBUG_ENT(sleeping?\n);
wait_event_interruptible(random_read_wait,
- input_pool.entropy_count =
-random_read_wakeup_thresh);
+ ENTROPY_BITS(input_pool) =
+ random_read_wakeup_thresh);
DEBUG_ENT(awake\n);
@@ -1250,9 +1252,9 @@ random_poll(struct file *file, poll_table * wait)
poll_wait(file, random_read_wait, wait);
poll_wait(file, random_write_wait, wait);
mask = 0;
- if (input_pool.entropy_count = random_read_wakeup_thresh)
+ if (ENTROPY_BITS(input_pool) = random_read_wakeup_thresh)
mask |= POLLIN | POLLRDNORM;
- if (input_pool.entropy_count random_write_wakeup_thresh)
+ if (ENTROPY_BITS(input_pool) random_write_wakeup_thresh)
mask |= POLLOUT | POLLWRNORM;
return mask;
}
@@ -1303,7 +1305,7 @@ static long random_ioctl(struct file *f, unsigned int
cmd, unsigned long arg)
switch (cmd) {
case RNDGETENTCNT:
/* inherently racy, no point locking */
- ent_count = input_pool.entropy_count ENTROPY_SHIFT;
+ ent_count = ENTROPY_BITS(input_pool);
if (put_user(ent_count, p))
return -EFAULT;
return 0;
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH, RFC 03/12] random: Allow fractional bits to be tracked
On 09/22/2013 09:01 PM, Theodore Ts'o wrote: I've added the following changes to this patch since upon testing, there were some uses of r-entropy_count that were not properly converted from using fractional bits to bits. Thanks for catching that. -hpa -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
