[PATCH 00/10] /dev/random fixups

The real-time Linux folks didn't like add_interrupt_randomness()
taking a spinlock since it is called in the low-level interrupt
routine. Using atomic_t's and cmpxchg is also too expensive on some
of the older architectures. So we'll bite the bullet and use
ACCESS_ONCE() and smp_rmb()/smp_wmb() to minimize the race windows
when mixing in the entropy pool.

Also, we will use a trylock when trying to increase then entropy
accounting during the interrupt path to avoid taking a spinlock there;
if there is contention, we will simply not credit the entropy count,
thus failing safe. Thanks to Dan Carpenter for suggesting this
approach.

Signed-off-by: "Theodore Ts'o"

drivers/char/random.c | 41 ++++++++++++++++++++++++--
1 file changed, 24 insertions(+), 17 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 53b3e85..789709e 100644
a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -418,9 +418,9 @@ struct entropy_store {
/* read-write data: */
spinlock_t lock;
unsigned add_ptr;
+ unsigned input_rotate;
int entropy_count;
int entropy_total;
- int input_rotate;
unsigned int initialized:1;
__u8 last_data[EXTRACT_SIZE];
};
@@ -478,16 +478,16 @@ static void mix_pool_bytes_extract(struct entropy_store *r, const void *in,
__u32 w;
unsigned long flags;

- /* Taps are constant, so we can load them without holding r->lock. */
tap1 = r->poolinfo->tap1;
tap2 = r->poolinfo->tap2;
tap3 = r->poolinfo->tap3;
tap4 = r->poolinfo->tap4;
tap5 = r->poolinfo->tap5;

- spin_lock_irqsave(&r->lock, flags);
- input_rotate = r->input_rotate;
- i = r->add_ptr;
+ local_irq_save(flags);
+ smp_rmb();
+ input_rotate = ACCESS_ONCE(r->input_rotate);
+ i = ACCESS_ONCE(r->add_ptr);

/* mix one byte at a time to simplify size handling and churn faster */
while (nbytes--) {
@@ -514,19 +514,19 @@ static void mix_pool_bytes_extract(struct entropy_store *r, const void *in,
input_rotate += i ? 7 : 14;
}

- r->input_rotate = input_rotate;
- r->add_ptr = i;
+ ACCESS_ONCE(r->input_rotate) = input_rotate;
+ ACCESS_ONCE(r->add_ptr) = i;
+ local_irq_restore(flags);
+ smp_wmb();

if (out)
for (j = 0; j < 16; j++)
((__u32 *)out)[j] = r->pool[(i - j) & wordmask];
-
- spin_unlock_irqrestore(&r->lock, flags);
}

static void mix_pool_bytes(struct entropy_store *r, const void *in, int bytes)
{
- mix_pool_bytes_extract(r, in, bytes, NULL);
+ mix_pool_bytes_extract(r, in, bytes, NULL);
}

struct fast_pool {
@@ -558,10 +558,12 @@ static void fast_mix(struct fast_pool *f, const void *in, int nbytes)
f->rotate = input_rotate;
}

+#define CREDIT_ENTROPY_BITS_NOWAIT 0x01
+
/*
* Credit (or debit) the entropy store with n bits of entropy
*/
-static void credit_entropy_bits(struct entropy_store *r, int nbits)
+static void credit_entropy_bits(struct entropy_store *r, int nbits, int fl)
{
unsigned long flags;
int entropy_count;
@@ -569,7 +571,11 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
if (!nbits)
return;

- spin_lock_irqsave(&r->lock, flags);
+ if (fl & CREDIT_ENTROPY_BITS_NOWAIT) {
+ if (!spin_trylock_irqsave(&r->lock, flags))
+ return;
+ } else
+ spin_lock_irqsave(&r->lock, flags);

DEBUG_ENT("added %d entropy credits to %s", nbits, r->name);
entropy_count = r->entropy_count;
@@ -592,6 +598,7 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits)
wake_up_interruptible(&random_read_wait);
kill_fasync(&fasync, SIGIO, POLL_IN);
}
+
spin_unlock_irqrestore(&r->lock, flags);
}

@@ -714,7 +721,7 @@ static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
* and limit entropy entimate to 12 bits.
*/
credit_entropy_bits(&input_pool,
- min_t(int, fls(delta>>1), 11));
+ min_t(int, fls(delta>>1), 11), 0);
}
out:
preempt_enable();
@@ -764,7 +771,7 @@ void add_interrupt_randomness(int irq)

r = nonblocking_pool.initialized ? &input_pool : &nonblocking_pool;
mix_pool_bytes(r, &fast_pool->pool, sizeof(fast_pool->pool));
- credit_entropy_bits(r, 1);
+ credit_entropy_bits(r, 1, CREDIT_ENTROPY_BITS_NOWAIT);
}

#ifdef CONFIG_BLOCK
@@ -816,7 +823,7 @@ static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
bytes = extract_entropy(r->pull, tmp, bytes,
random_read_wakeup_thresh / 8, rsvd);
mix_pool_bytes(r, tmp, bytes);
- credit_entropy_bits(r, bytes*8);
+ credit_entropy_bits(r, bytes*8, 0);
}
}

@@ -1211,7 +1218,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
return -EPERM;
if (get_user(ent_count, p))
return -EFAULT;
- credit_entropy_bits(&input_pool, ent_count);
+ credit_entropy_bits(&input_pool, ent_count, 0);
return 0;
case RNDADDENTROPY:
if (!capable(CAP_SYS_ADMIN))
@@ -1226,7 +1233,7 @@ static long random_ioctl(struct file *f, unsigned int cmd, unsigned long arg)
size);
if (retval < 0)
return retval;
- credit_entropy_bits(&input_pool, ent_count);
+ credit_entropy_bits(&input_pool, ent_count, 0);
return 0;
case RNDZAPENTCNT:
case RNDCLEARPOOL:
1.7.11.1.108.gb129051

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

From: Linus Torvalds

Add a new interface, add_device_randomness() for adding data to the
random pool that is likely to differ between two devices (or possibly
even per boot). This would be things like MAC addresses or serial
numbers, or the read-out of the RTC. This does *not* add any actual
entropy to the pool, but it initializes the pool to different values
for devices that might otherwise be identical and have very little
entropy available to them (particularly common in the embedded world).

[ Modified by tytso to mix in a timestamp, since there may be some
variability caused by the time needed to detect/configure the hardware
in question. ]

Signed-off-by: Linus Torvalds
Signed-off-by: "Theodore Ts'o"
Cc:

drivers/char/random.c | 28 ++++++++++++++++++++++++++++
include/linux/random.h | 1 +
2 files changed, 29 insertions(+)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 789709e..59ddcce 100644
a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -125,11 +125,20 @@
* The current exported interfaces for gathering environmental noise
* from the devices are:
*
+ * void add_device_randomness(const void *buf, unsigned int size);
* void add_input_randomness(unsigned int type, unsigned int code,
* unsigned int value);
* void add_interrupt_randomness(int irq);
* void add_disk_randomness(struct gendisk *disk);
*
+ * add_device_randomness() is for adding data to the random pool that
+ * is likely to differ between two devices (or possibly even per boot).
+ * This would be things like MAC addresses or serial numbers, or the
+ * read-out of the RTC. This does *not* add any actual entropy to the
+ * pool, but it initializes the pool to different values for devices
+ * that might otherwise be identical and have very little entropy
+ * available to them (particularly common in the embedded world).
+ *
* add_input_randomness() uses the input layer interrupt timing, as well as
* the event type information from the hardware.
*
@@ -652,6 +661,25 @@ static void set_timer_rand_state(unsigned int irq,
}
#endif

+/*
+ * Add device- or boot-specific data to the input and nonblocking
+ * pools to help initialize them to unique values.
+ *
+ * None of this adds any entropy, it is meant to avoid the
+ * problem of the nonblocking pool having similar initial state
+ * across largely identical devices.
+ */
+void add_device_randomness(const void *buf, unsigned int size)
+{
+ unsigned long time = get_cycles() ^ jiffies;
+
+ mix_pool_bytes(&input_pool, buf, size);
+ mix_pool_bytes(&input_pool, &time, sizeof(time));
+ mix_pool_bytes(&nonblocking_pool, buf, size);
+ mix_pool_bytes(&nonblocking_pool, &time, sizeof(time));
+}
+EXPORT_SYMBOL(add_device_randomness);
+
static struct timer_rand_state input_timer_state;

/*
diff --git a/include/linux/random.h b/include/linux/random.h
index 8f74538..6b55c51 100644
a/include/linux/random.h
+++ b/include/linux/random.h
@@ -50,6 +50,7 @@ struct rnd_state {

extern void rand_initialize_irq(int irq);

+extern void add_device_randomness(const void *, unsigned int);
extern void add_input_randomness(unsigned int type, unsigned int code,
unsigned int value);
extern void add_interrupt_randomness(int irq);
1.7.11.1.108.gb129051

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Signed-off-by: "Theodore Ts'o"

drivers/char/random.c | 11 ++++
include/trace/events/random.h | 132 ++++++++++++++++++++++++++++++++++++++++++
2 files changed, 143 insertions(+)
create mode 100644 include/trace/events/random.h

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 0423254..8f20e3d 100644
a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -265,6 +265,9 @@
#include <asm/ptrace.h>
#include <asm/io.h>

+#define CREATE_TRACE_POINTS
+#include <trace/events/random.h>
+
/*
* Configuration information
*/
@@ -487,6 +490,7 @@ static void mix_pool_bytes(struct entropy_store *r, const void *in,
__u32 w;
unsigned long flags;

+ trace_mix_pool_bytes(r->name, nbytes, _RET_IP_);
tap1 = r->poolinfo->tap1;
tap2 = r->poolinfo->tap2;
tap3 = r->poolinfo->tap3;
@@ -584,6 +588,7 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits, int fl)
DEBUG_ENT("added %d entropy credits to %s", nbits, r->name);
entropy_count = r->entropy_count;
entropy_count += nbits;
+
if (entropy_count < 0) {
DEBUG_ENT("negative entropy/overflow");
entropy_count = 0;
@@ -597,6 +602,9 @@ static void credit_entropy_bits(struct entropy_store *r, int nbits, int fl)
r->initialized = 1;
}

+ trace_credit_entropy_bits(r->name, nbits, entropy_count,
+ r->entropy_total, _RET_IP_);
+
/* should we wake readers? */
if (r == &input_pool && entropy_count >= random_read_wakeup_thresh) {
wake_up_interruptible(&random_read_wait);
@@ -952,6 +960,7 @@ static ssize_t extract_entropy(struct entropy_store *r, void *buf,
__u8 tmp[EXTRACT_SIZE];
unsigned long flags;

+ trace_extract_entropy(r->name, nbytes, r->entropy_count, _RET_IP_);
xfer_secondary_pool(r, nbytes);
nbytes = account(r, nbytes, min, reserved);

@@ -984,6 +993,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_);
xfer_secondary_pool(r, nbytes);
nbytes = account(r, nbytes, 0, 0);

@@ -1041,6 +1051,7 @@ void get_random_bytes_arch(void *buf, int nbytes)
{
char *p = buf;

+ trace_get_random_bytes(nbytes, _RET_IP_);
while (nbytes) {
unsigned long v;
int chunk = min(nbytes, (int)sizeof(unsigned long));
diff --git a/include/trace/events/random.h b/include/trace/events/random.h
new file mode 100644
index 0000000..754754d
/dev/null
+++ b/include/trace/events/random.h
@@ -0,0 +1,132 @@
+#undef TRACE_SYSTEM
+#define TRACE_SYSTEM random
+
+#if !defined(_TRACE_RANDOM_H) || defined(TRACE_HEADER_MULTI_READ)
+#define _TRACE_RANDOM_H
+
+#include <linux/writeback.h>
+#include <linux/tracepoint.h>
+
+TRACE_EVENT(mix_pool_bytes,
+ TP_PROTO(const char *pool_name, int bytes, unsigned long IP),
+
+ TP_ARGS(pool_name, bytes, IP),
+
+ TP_STRUCT__entry(
+ __field( const char *, pool_name )
+ __field( int, bytes )
+ __field(unsigned long, IP )
+ ),
+
+ TP_fast_assign(
+ __entry->pool_name = pool_name;
+ __entry->bytes = bytes;
+ __entry->IP = IP;
+ ),
+
+ TP_printk("pool %s bytes %d caller %pF",
+ __entry->pool_name, __entry->bytes, (void *)__entry->IP)
+);
+
+TRACE_EVENT(credit_entropy_bits,
+ TP_PROTO(const char *pool_name, int bits, int entropy_count,
+ int entropy_total, unsigned long IP),
+
+ TP_ARGS(pool_name, bits, entropy_count, entropy_total, IP),
+
+ TP_STRUCT__entry(
+ __field( const char *, pool_name )
+ __field( int, bits )
+ __field( int, entropy_count )
+ __field( int, entropy_total )
+ __field(unsigned long, IP )
+ ),
+
+ TP_fast_assign(
+ __entry->pool_name = pool_name;
+ __entry->bits = bits;
+ __entry->entropy_count = entropy_count;
+ __entry->entropy_total = entropy_total;
+ __entry->IP = IP;
+ ),
+
+ TP_printk("pool %s bits %d entropy_count %d entropy_total %d "
+ "caller %pF", __entry->pool_name, __entry->bits,
+ __entry->entropy_count, __entry->entropy_total,
+ (void *)__entry->IP)
+);
+
+TRACE_EVENT(get_random_bytes,
+ TP_PROTO(int nbytes, unsigned long IP),
+
+ TP_ARGS(nbytes, IP),
+
+ TP_STRUCT__entry(
+ __field( int, nbytes )
+ __field(unsigned long, IP )
+ ),
+
+ TP_fast_assign(
+ __entry->nbytes = nbytes;
+ __entry->IP = IP;
+ ),
+
+ TP_printk("nbytes %d caller %pF", __entry->nbytes, (void *)__entry->IP)
+);
+
+TRACE_EVENT(extract_entropy,
+ TP_PROTO(const char *pool_name, int nbytes, int entropy_count,
+ unsigned long IP),
+
+ TP_ARGS(pool_name, nbytes, entropy_count, IP),
+
+ TP_STRUCT__entry(
+ __field( const char *, pool_name )
+ __field( int, nbytes )
+ __field( int, entropy_count )
+ __field(unsigned long, IP )
+ ),
+
+ TP_fast_assign(
+ __entry->pool_name = pool_name;
+ __entry->nbytes = nbytes;
+ __entry->entropy_count = entropy_count;
+ __entry->IP = IP;
+ ),
+
+ TP_printk("pool %s nbytes %d entropy_count %d caller %pF",
+ __entry->pool_name, __entry->nbytes, __entry->entropy_count,
+ (void *)__entry->IP)
+);
+
+TRACE_EVENT(extract_entropy_user,
+ TP_PROTO(const char *pool_name, int nbytes, int entropy_count,
+ unsigned long IP),
+
+ TP_ARGS(pool_name, nbytes, entropy_count, IP),
+
+ TP_STRUCT__entry(
+ __field( const char *, pool_name )
+ __field( int, nbytes )
+ __field( int, entropy_count )
+ __field(unsigned long, IP )
+ ),
+
+ TP_fast_assign(
+ __entry->pool_name = pool_name;
+ __entry->nbytes = nbytes;
+ __entry->entropy_count = entropy_count;
+ __entry->IP = IP;
+ ),
+
+ TP_printk("pool %s nbytes %d entropy_count %d caller %pF",
+ __entry->pool_name, __entry->nbytes, __entry->entropy_count,
+ (void *)__entry->IP)
+);
+
+
+
+#endif /* _TRACE_RANDOM_H */
+
+/* This part must be outside protection */
+#include <trace/define_trace.h>
1.7.11.1.108.gb129051

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Cc: David Miller
Cc: Linus Torvalds
Signed-off-by: "Theodore Ts'o"
Cc:

net/core/dev.c | 3 +++
1 file changed, 3 insertions(+)

diff --git a/net/core/dev.c b/net/core/dev.c
index 6df2140..46f2f0c 100644
a/net/core/dev.c
+++ b/net/core/dev.c
@@ -5542,6 +5542,9 @@ int register_netdevice(struct net_device *dev)
dev_hold(dev);
list_netdevice(dev);

+ if (dev->dev_addr)
+ add_device_randomness(dev->dev_addr, dev->addr_len);
+
/* Notify protocols, that a new device appeared. */
ret = call_netdevice_notifiers(NETDEV_REGISTER, dev);
ret = notifier_to_errno(ret);
1.7.11.1.108.gb129051

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

On Thu, Jul 05, 2012 at 02:12:05PM -0400, Theodore Ts'o wrote:

The real-time Linux folks didn't like add_interrupt_randomness()
taking a spinlock since it is called in the low-level interrupt
routine. Using atomic_t's and cmpxchg is also too expensive on some
of the older architectures. So we'll bite the bullet and use
ACCESS_ONCE() and smp_rmb()/smp_wmb() to minimize the race windows
when mixing in the entropy pool.

Also, we will use a trylock when trying to increase then entropy
accounting during the interrupt path to avoid taking a spinlock there;
if there is contention, we will simply not credit the entropy count,
thus failing safe. Thanks to Dan Carpenter for suggesting this
approach.

Signed-off-by: "Theodore Ts'o"

Any reason you don't want this backported to the -stable series?

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/