Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/tls-earlyentropy]: src/sys Entropy estimation changes:
details: https://anonhg.NetBSD.org/src/rev/b5d812aa0bac
branches: tls-earlyentropy
changeset: 795263:b5d812aa0bac
user: tls <tls%NetBSD.org@localhost>
date: Mon Apr 07 02:00:00 2014 +0000
description:
Entropy estimation changes:
1) Avoid wraparound problems with delta estimator by making estimation
framework 64-bit.
2) Adjust rnd_counter to always return a 64-bit value, accordingly.
3) Make delta estimator generic and create two instances: delta-time and
delta-value.
4) Add LZF estimator -- used mostly to protect us against injection of
bulk data we think is random but is really constant.
5) Allow value and time estimation/collection to be controlled separately.
6) Expose estimator performance to userspace.
diffstat:
sys/kern/kern_rndpool.c | 10 +-
sys/kern/kern_rndq.c | 455 +++++++++++++++++++++++++++++++++++------------
sys/sys/rnd.h | 89 ++++++++-
3 files changed, 423 insertions(+), 131 deletions(-)
diffs (truncated from 1061 to 300 lines):
diff -r 230433403adf -r b5d812aa0bac sys/kern/kern_rndpool.c
--- a/sys/kern/kern_rndpool.c Mon Apr 07 01:10:55 2014 +0000
+++ b/sys/kern/kern_rndpool.c Mon Apr 07 02:00:00 2014 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: kern_rndpool.c,v 1.5 2013/08/29 01:04:49 tls Exp $ */
+/* $NetBSD: kern_rndpool.c,v 1.5.2.1 2014/04/07 02:00:00 tls Exp $ */
/*-
* Copyright (c) 1997 The NetBSD Foundation, Inc.
@@ -31,7 +31,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_rndpool.c,v 1.5 2013/08/29 01:04:49 tls Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_rndpool.c,v 1.5.2.1 2014/04/07 02:00:00 tls Exp $");
#include <sys/param.h>
#include <sys/systm.h>
@@ -85,6 +85,12 @@
return (rp->stats.curentropy);
}
+void
+rndpool_set_entropy_count(rndpool_t *rp, u_int32_t count)
+{
+ rp->stats.curentropy = count;
+}
+
void rndpool_get_stats(rndpool_t *rp, void *rsp, int size)
{
diff -r 230433403adf -r b5d812aa0bac sys/kern/kern_rndq.c
--- a/sys/kern/kern_rndq.c Mon Apr 07 01:10:55 2014 +0000
+++ b/sys/kern/kern_rndq.c Mon Apr 07 02:00:00 2014 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: kern_rndq.c,v 1.23 2014/03/11 20:26:08 pooka Exp $ */
+/* $NetBSD: kern_rndq.c,v 1.23.2.1 2014/04/07 02:00:00 tls Exp $ */
/*-
* Copyright (c) 1997-2013 The NetBSD Foundation, Inc.
@@ -32,7 +32,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_rndq.c,v 1.23 2014/03/11 20:26:08 pooka Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_rndq.c,v 1.23.2.1 2014/04/07 02:00:00 tls Exp $");
#include <sys/param.h>
#include <sys/ioctl.h>
@@ -63,7 +63,7 @@
#endif
#ifdef RND_DEBUG
-#define DPRINTF(l,x) if (rnd_debug & (l)) printf x
+#define DPRINTF(l,x) if (rnd_debug & (l)) rnd_printf x
int rnd_debug = 0;
#else
#define DPRINTF(l,x)
@@ -81,6 +81,10 @@
#define RND_VERBOSE
#endif
+#ifdef RND_VERBOSE
+static unsigned int deltacnt;
+#endif
+
/*
* This is a little bit of state information attached to each device that we
* collect entropy from. This is simply a collection buffer, and when it
@@ -93,7 +97,7 @@
krndsource_t *source;
int cursor;
int entropy;
- u_int32_t ts[RND_SAMPLE_COUNT];
+ uint64_t ts[RND_SAMPLE_COUNT];
u_int32_t values[RND_SAMPLE_COUNT];
} rnd_sample_t;
@@ -129,31 +133,45 @@
/* LIST_ENTRY list */
.name = { 'N', 'o', 'C', 'o', 'l', 'l', 'e', 'c', 't',
0, 0, 0, 0, 0, 0, 0 },
- .last_time = 0, .last_delta = 0, .last_delta2 = 0, .total = 0,
+ .total = 0,
.type = RND_TYPE_UNKNOWN,
.flags = (RND_FLAG_NO_COLLECT |
- RND_FLAG_NO_ESTIMATE |
- RND_TYPE_UNKNOWN),
+ RND_FLAG_NO_ESTIMATE),
.state = NULL,
.test_cnt = 0,
.test = NULL
};
+
+static krndsource_t rnd_source_anonymous = {
+ /* LIST_ENTRY list */
+ .name = { 'A', 'n', 'o', 'n', 'y', 'm', 'o', 'u', 's',
+ 0, 0, 0, 0, 0, 0, 0 },
+ .total = 0,
+ .type = RND_TYPE_UNKNOWN,
+ .flags = (RND_FLAG_COLLECT_TIME|
+ RND_FLAG_COLLECT_VALUE|
+ RND_FLAG_ESTIMATE_TIME),
+ .state = NULL,
+ .test_cnt = 0,
+ .test = NULL
+};
+
void *rnd_process, *rnd_wakeup;
struct callout skew_callout;
-void rnd_wakeup_readers(void);
-static inline u_int32_t rnd_estimate_entropy(krndsource_t *, u_int32_t);
-static inline u_int32_t rnd_counter(void);
+void rnd_wakeup_readers(void);
+static inline uint64_t rnd_counter(void);
static void rnd_intr(void *);
static void rnd_wake(void *);
static void rnd_process_events(void);
u_int32_t rnd_extract_data_locked(void *, u_int32_t, u_int32_t); /* XXX */
static void rnd_add_data_ts(krndsource_t *, const void *const,
- uint32_t, uint32_t, uint32_t);
+ uint32_t, uint32_t, uint64_t);
static inline void rnd_schedule_process(void);
int rnd_ready = 0;
int rnd_initial_entropy = 0;
+int rnd_printing = 0;
#ifdef DIAGNOSTIC
static int rnd_tested = 0;
@@ -165,6 +183,23 @@
rndsave_t *boot_rsp;
+static inline void
+rnd_printf(const char *fmt, ...)
+{
+ va_list ap;
+
+ membar_consumer();
+ if (rnd_printing) {
+ return;
+ }
+ rnd_printing = 1;
+ membar_producer();
+ va_start(ap, fmt);
+ vprintf(fmt, ap);
+ va_end(ap);
+ rnd_printing = 0;
+}
+
void
rnd_init_softint(void) {
rnd_process = softint_establish(SOFTINT_SERIAL|SOFTINT_MPSAFE,
@@ -175,21 +210,25 @@
}
/*
- * Generate a 32-bit counter. This should be more machine dependent,
- * using cycle counters and the like when possible.
+ * Generate a 64-bit counter.
*/
-static inline u_int32_t
+static inline uint64_t
rnd_counter(void)
{
- struct timeval tv;
+ struct timespec ts;
+ uint64_t ret;
#if defined(__HAVE_CPU_COUNTER)
- if (cpu_hascounter())
- return (cpu_counter32());
+ if (cpu_hascounter() && sizeof(cpu_counter() == sizeof(uint64_t))) {
+ return (cpu_counter());
+ }
#endif
if (rnd_ready) {
- microtime(&tv);
- return (tv.tv_sec * 1000000 + tv.tv_usec);
+ nanouptime(&ts);
+ ret = ts.tv_sec;
+ ret *= (uint64_t)1000000000;
+ ret += ts.tv_nsec;
+ return ret;
}
/* when called from rnd_init, its too early to call microtime safely */
return (0);
@@ -243,7 +282,7 @@
KASSERT(rs->getarg != NULL);
rs->get(byteswanted, rs->getarg);
#ifdef RND_VERBOSE
- printf("rnd: asking source %s for %zu bytes\n",
+ rnd_printf("rnd: asking source %s for %zu bytes\n",
rs->name, byteswanted);
#endif
}
@@ -271,7 +310,7 @@
} else {
#ifdef RND_VERBOSE
if (__predict_false(!rnd_initial_entropy))
- printf("rnd: have initial entropy (%zu)\n",
+ rnd_printf("rnd: have initial entropy (%zu)\n",
entropy_count);
#endif
rnd_empty = 0;
@@ -282,42 +321,85 @@
rndsinks_distribute();
}
+static uint32_t
+rnd_lz_estimate(krndsource_t *rs, rnd_lz_t *const est,
+ const void *const data, uint32_t len)
+{
+ const uint8_t *const cdata = data;
+ size_t c = 0, wherein = 0, cursor = est->cursor;
+ size_t isz = sizeof(est->in), osz = sizeof(est->out);
+ LZF_STATE *state = &est->state;
+ uint8_t *in = est->in, *out = est->out;
+ uint32_t total = 0;
+
+ KASSERT(rs != NULL);
+ KASSERT(cursor < isz);
+ KASSERT(cursor < osz);
+
+ /* We don't loop, so the maximum estimate we will
+ ever return is one internal-buffer-size worth of bits. */
+
+ if (cursor + len - wherein >= isz) {
+ c = lzf_compress_r(in, cursor, out,
+ cursor, *state);
+ memset(out, 0, osz);
+ memset(in, 0, isz);
+ if (c == 0) {
+ c = cursor;
+ }
+ total += c;
+ wherein += cursor;
+ cursor = 0;
+ } else {
+ memcpy(in + cursor, cdata + wherein, len - wherein);
+ cursor += len - wherein;
+ wherein += len - wherein;
+ }
+
+ total *= NBBY;
+
+ /*
+ * Compressing a stream of zeroes gives us 144 output
+ * bits per input kilobyte -- pure overhead, not entropy.
+ */
+ total = total > 144 ? total - 144 : 0;
+
+ /* LZF is not a very good LZ compressor! */
+ total /= 2;
+
+ est->cursor = cursor;
+ est->inbytes += len;
+ est->outbits += total;
+
+ return est->outbits > rs->total ? est->outbits - rs->total : 0;
+}
+
/*
- * Use the timing of the event to estimate the entropy gathered.
+ * Use the timing/value of the event to estimate the entropy gathered.
* If all the differentials (first, second, and third) are non-zero, return
* non-zero. If any of these are zero, return zero.
*/
-static inline u_int32_t
-rnd_estimate_entropy(krndsource_t *rs, u_int32_t t)
+static inline uint32_t
+rnd_delta_estimate(rnd_delta_t *d, uint64_t v, int64_t delta)
{
- int32_t delta, delta2, delta3;
+ int64_t delta2, delta3;
- /*
- * If the time counter has overflowed, calculate the real difference.
- * If it has not, it is simplier.
- */
- if (t < rs->last_time)
- delta = UINT_MAX - rs->last_time + t;
- else
- delta = rs->last_time - t;
-
- if (delta < 0)
- delta = -delta;
+ d->insamples++;
/*
* Calculate the second and third order differentials
*/
- delta2 = rs->last_delta - delta;
+ delta2 = d->dx - delta;
if (delta2 < 0)
delta2 = -delta2;
- delta3 = rs->last_delta2 - delta2;
Home |
Main Index |
Thread Index |
Old Index