From owner-svn-src-projects@FreeBSD.ORG Sun Oct 6 09:55:31 2013 Return-Path: Delivered-To: svn-src-projects@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTP id D6FC21000; Sun, 6 Oct 2013 09:55:31 +0000 (UTC) (envelope-from markm@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:1900:2254:2068::e6a:0]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id B457521C0; Sun, 6 Oct 2013 09:55:31 +0000 (UTC) Received: from svn.freebsd.org ([127.0.1.70]) by svn.freebsd.org (8.14.7/8.14.7) with ESMTP id r969tVHV047718; Sun, 6 Oct 2013 09:55:31 GMT (envelope-from markm@svn.freebsd.org) Received: (from markm@localhost) by svn.freebsd.org (8.14.7/8.14.5/Submit) id r969tTmH047691; Sun, 6 Oct 2013 09:55:29 GMT (envelope-from markm@svn.freebsd.org) Message-Id: <201310060955.r969tTmH047691@svn.freebsd.org> From: Mark Murray Date: Sun, 6 Oct 2013 09:55:29 +0000 (UTC) To: src-committers@freebsd.org, svn-src-projects@freebsd.org Subject: svn commit: r256081 - projects/random_number_generator/sys/dev/random X-SVN-Group: projects MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-BeenThere: svn-src-projects@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "SVN commit messages for the src " projects" tree" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 06 Oct 2013 09:55:31 -0000 Author: markm Date: Sun Oct 6 09:55:28 2013 New Revision: 256081 URL: http://svnweb.freebsd.org/changeset/base/256081 Log: SNAPSHOT. Simplify the malloc pools; We only need one for this device. Simplify the harvest queue. Marginally improve the entropy pool hashing, making it a bit faster in the process. Connect up the hardware "live" source harvesting. This is simplistic for now, and will need to be made rate-adaptive. All of the above passes a compile test but needs to be debugged. Modified: projects/random_number_generator/sys/dev/random/dummy_rng.c projects/random_number_generator/sys/dev/random/ivy.c projects/random_number_generator/sys/dev/random/live_entropy_sources.c projects/random_number_generator/sys/dev/random/live_entropy_sources.h projects/random_number_generator/sys/dev/random/nehemiah.c projects/random_number_generator/sys/dev/random/random_adaptors.c projects/random_number_generator/sys/dev/random/random_harvestq.c projects/random_number_generator/sys/dev/random/randomdev.c projects/random_number_generator/sys/dev/random/randomdev.h projects/random_number_generator/sys/dev/random/randomdev_soft.c projects/random_number_generator/sys/dev/random/randomdev_soft.h projects/random_number_generator/sys/dev/random/yarrow.c Modified: projects/random_number_generator/sys/dev/random/dummy_rng.c ============================================================================== --- projects/random_number_generator/sys/dev/random/dummy_rng.c Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/dummy_rng.c Sun Oct 6 09:55:28 2013 (r256081) @@ -30,6 +30,7 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include #include #include #include Modified: projects/random_number_generator/sys/dev/random/ivy.c ============================================================================== --- projects/random_number_generator/sys/dev/random/ivy.c Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/ivy.c Sun Oct 6 09:55:28 2013 (r256081) @@ -32,6 +32,7 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include #include #include #include @@ -40,9 +41,11 @@ __FBSDID("$FreeBSD$"); #include #include +#include +#include +#include #include #include -#include #define RETRY_COUNT 10 Modified: projects/random_number_generator/sys/dev/random/live_entropy_sources.c ============================================================================== --- projects/random_number_generator/sys/dev/random/live_entropy_sources.c Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/live_entropy_sources.c Sun Oct 6 09:55:28 2013 (r256081) @@ -40,9 +40,12 @@ __FBSDID("$FreeBSD$"); #include #include +#include + #include #include #include +#include #include "live_entropy_sources.h" @@ -52,9 +55,6 @@ static struct sx les_lock; /* need a sle #define LES_THRESHOLD 10 -MALLOC_DEFINE(M_LIVE_ENTROPY_SRCS, "live_entropy_sources", - "Live Entropy Sources"); - void live_entropy_source_register(struct random_hardware_source *rsource) { @@ -62,8 +62,7 @@ live_entropy_source_register(struct rand KASSERT(rsource != NULL, ("invalid input to %s", __func__)); - les = malloc(sizeof(struct live_entropy_sources), M_LIVE_ENTROPY_SRCS, - M_WAITOK); + les = malloc(sizeof(struct live_entropy_sources), M_ENTROPY, M_WAITOK); les->rsource = rsource; sx_xlock(&les_lock); @@ -82,7 +81,7 @@ live_entropy_source_deregister(struct ra LIST_FOREACH(les, &sources, entries) { if (les->rsource == rsource) { LIST_REMOVE(les, entries); - free(les, M_LIVE_ENTROPY_SRCS); + free(les, M_ENTROPY); break; } } @@ -136,12 +135,16 @@ live_entropy_sources_init(void *unused) * number of rounds, which should be a multiple of the number * of entropy accumulation pools in use; 2 for Yarrow and 32 * for Fortuna. + * + * BEWARE!!! + * This function runs inside the RNG thread! Don't do anything silly! */ void -live_entropy_sources_feed(int rounds) +live_entropy_sources_feed(int rounds, event_proc_f entropy_processor) { + static struct harvest event; + static uint8_t buf[HARVESTSIZE]; struct live_entropy_sources *les; - uint8_t buf[HARVESTSIZE]; int i, n; sx_slock(&les_lock); @@ -157,14 +160,19 @@ live_entropy_sources_feed(int rounds) * This should be quick, since it's a live entropy * source. */ - n = les->rsource->read(buf, sizeof(buf)); /* FIXME: Whine loudly if this didn't work. */ + n = les->rsource->read(buf, sizeof(buf)); + n = MIN(n, HARVESTSIZE); + + event.somecounter = get_cyclecount(); + event.size = n; + event.bits = (n*8)/2; + event.source = les->rsource->source; + memcpy(event.entropy, buf, n); + + /* Do the actual entropy insertion */ + entropy_processor(&event); - /* - * FIXME: Cannot harvest this stuff into the queue; - * the poor thing will choke to death! - */ - random_harvest(buf, n, 0, les->rsource->source); } } Modified: projects/random_number_generator/sys/dev/random/live_entropy_sources.h ============================================================================== --- projects/random_number_generator/sys/dev/random/live_entropy_sources.h Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/live_entropy_sources.h Sun Oct 6 09:55:28 2013 (r256081) @@ -42,7 +42,7 @@ struct live_entropy_sources { void live_entropy_source_register(struct random_hardware_source *); void live_entropy_source_deregister(struct random_hardware_source *); -void live_entropy_sources_feed(int); +void live_entropy_sources_feed(int, event_proc_f); #define LIVE_ENTROPY_SRC_MODULE(name, modevent, ver) \ static moduledata_t name##_mod = { \ Modified: projects/random_number_generator/sys/dev/random/nehemiah.c ============================================================================== --- projects/random_number_generator/sys/dev/random/nehemiah.c Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/nehemiah.c Sun Oct 6 09:55:28 2013 (r256081) @@ -31,6 +31,7 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include #include #include #include @@ -40,9 +41,11 @@ __FBSDID("$FreeBSD$"); #include #include +#include +#include +#include #include #include -#include static void random_nehemiah_init(void); static void random_nehemiah_deinit(void); Modified: projects/random_number_generator/sys/dev/random/random_adaptors.c ============================================================================== --- projects/random_number_generator/sys/dev/random/random_adaptors.c Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/random_adaptors.c Sun Oct 6 09:55:28 2013 (r256081) @@ -55,8 +55,6 @@ static struct sysctl_ctx_list random_cli struct random_adaptor *random_adaptor; -MALLOC_DEFINE(M_RANDOM_ADAPTORS, "random_adaptors", "Random adaptors buffers"); - int random_adaptor_register(const char *name, struct random_adaptor *rsp) { @@ -64,8 +62,7 @@ random_adaptor_register(const char *name KASSERT(name != NULL && rsp != NULL, ("invalid input to %s", __func__)); - rpp = malloc(sizeof(struct random_adaptors), M_RANDOM_ADAPTORS, - M_WAITOK); + rpp = malloc(sizeof(struct random_adaptors), M_ENTROPY, M_WAITOK); rpp->name = name; rpp->rsp = rsp; Modified: projects/random_number_generator/sys/dev/random/random_harvestq.c ============================================================================== --- projects/random_number_generator/sys/dev/random/random_harvestq.c Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/random_harvestq.c Sun Oct 6 09:55:28 2013 (r256081) @@ -39,17 +39,17 @@ __FBSDID("$FreeBSD$"); #include #include #include +#include #include #include +#include #include - -#include "random_harvestq.h" +#include +#include #define RANDOM_FIFO_MAX 1024 /* How many events to queue up */ -MALLOC_DEFINE(M_ENTROPY, "entropy", "Entropy harvesting buffers"); - /* * The harvest mutex protects the consistency of the entropy fifos and * empty fifo. @@ -66,7 +66,7 @@ struct entropyfifo { static struct entropyfifo emptyfifo; /* Harvested entropy */ -static struct entropyfifo harvestfifo[ENTROPYSOURCE]; +static struct entropyfifo harvestfifo; /* <0 to end the kthread, 0 to let it run, 1 to flush the harvest queues */ int random_kthread_control = 0; @@ -79,8 +79,7 @@ random_kthread(void *arg) STAILQ_HEAD(, harvest) local_queue; struct harvest *event = NULL; int local_count; - enum esource source; - event_proc_f func = arg; + event_proc_f entropy_processor = arg; STAILQ_INIT(&local_queue); local_count = 0; @@ -89,16 +88,14 @@ random_kthread(void *arg) mtx_lock_spin(&harvest_mtx); for (; random_kthread_control >= 0;) { - /* Cycle through all the entropy sources */ - for (source = RANDOM_START; source < ENTROPYSOURCE; source++) { - /* - * Drain entropy source records into a thread-local - * queue for processing while not holding the mutex. - */ - STAILQ_CONCAT(&local_queue, &harvestfifo[source].head); - local_count += harvestfifo[source].count; - harvestfifo[source].count = 0; - } + /* + * Grab all the entropy events. + * Drain entropy source records into a thread-local + * queue for processing while not holding the mutex. + */ + STAILQ_CONCAT(&local_queue, &harvestfifo.head); + local_count += harvestfifo.count; + harvestfifo.count = 0; /* * Deal with events, if any. @@ -107,7 +104,7 @@ random_kthread(void *arg) if (!STAILQ_EMPTY(&local_queue)) { mtx_unlock_spin(&harvest_mtx); STAILQ_FOREACH(event, &local_queue, next) - func(event); + entropy_processor(event); mtx_lock_spin(&harvest_mtx); STAILQ_CONCAT(&emptyfifo.head, &local_queue); emptyfifo.count += local_count; @@ -118,16 +115,10 @@ random_kthread(void *arg) local_count)); /* - * Do Hardware/fast RNG source processing here. + * Do only one round of the hardware sources for now. + * Later we'll need to make it rate-adaptive. */ -#if 0 - while (hardware_source) { - event = hardware_source->read(); - func(event); - hardware_source++; - /* Throttle somehow? */ - } -#endif + live_entropy_sources_feed(1, entropy_processor); /* * If a queue flush was commanded, it has now happened, @@ -153,22 +144,22 @@ random_harvestq_init(event_proc_f cb) { int error, i; struct harvest *np; - enum esource e; /* Initialise the harvest fifos */ + + /* Contains the currently unused event structs. */ STAILQ_INIT(&emptyfifo.head); - emptyfifo.count = 0; for (i = 0; i < RANDOM_FIFO_MAX; i++) { np = malloc(sizeof(struct harvest), M_ENTROPY, M_WAITOK); STAILQ_INSERT_TAIL(&emptyfifo.head, np, next); } - for (e = RANDOM_START; e < ENTROPYSOURCE; e++) { - STAILQ_INIT(&harvestfifo[e].head); - harvestfifo[e].count = 0; - } + emptyfifo.count = RANDOM_FIFO_MAX; - mtx_init(&harvest_mtx, "entropy harvest mutex", NULL, MTX_SPIN); + /* Will contain the queued-up events. */ + STAILQ_INIT(&harvestfifo.head); + harvestfifo.count = 0; + mtx_init(&harvest_mtx, "entropy harvest mutex", NULL, MTX_SPIN); /* Start the hash/reseed thread */ error = kproc_create(random_kthread, cb, @@ -182,7 +173,6 @@ void random_harvestq_deinit(void) { struct harvest *np; - enum esource e; /* Destroy the harvest fifos */ while (!STAILQ_EMPTY(&emptyfifo.head)) { @@ -190,20 +180,26 @@ random_harvestq_deinit(void) STAILQ_REMOVE_HEAD(&emptyfifo.head, next); free(np, M_ENTROPY); } - for (e = RANDOM_START; e < ENTROPYSOURCE; e++) { - while (!STAILQ_EMPTY(&harvestfifo[e].head)) { - np = STAILQ_FIRST(&harvestfifo[e].head); - STAILQ_REMOVE_HEAD(&harvestfifo[e].head, next); - free(np, M_ENTROPY); - } + emptyfifo.count = 0; + while (!STAILQ_EMPTY(&harvestfifo.head)) { + np = STAILQ_FIRST(&harvestfifo.head); + STAILQ_REMOVE_HEAD(&harvestfifo.head, next); + free(np, M_ENTROPY); } + harvestfifo.count = 0; mtx_destroy(&harvest_mtx); } /* - * Entropy harvesting routine. This is supposed to be fast; do - * not do anything slow in here! + * Entropy harvesting routine. + * This is supposed to be fast; do not do anything slow in here! + * + * It is also illegal (and morally reprehensible) to insert any + * high-rate data here. "High-rate" is define as a data source + * that will usually cause lots of failures of the "Lockless read" + * check a few lines below. This includes the "always-on" sources + * like the Intel "rdrand" or the VIA Nehamiah "xstore" sources. */ void random_harvestq_internal(u_int64_t somecounter, const void *entropy, @@ -215,21 +211,21 @@ random_harvestq_internal(u_int64_t somec ("random_harvest_internal: origin %d invalid\n", origin)); /* Lockless read to avoid lock operations if fifo is full. */ - if (harvestfifo[origin].count >= RANDOM_FIFO_MAX) + if (harvestfifo.count >= RANDOM_FIFO_MAX) return; mtx_lock_spin(&harvest_mtx); /* - * Don't make the harvest queues too big - help to prevent low-grade - * entropy swamping + * On't overfill the harvest queue; this could steal all + * our memory. */ - if (harvestfifo[origin].count < RANDOM_FIFO_MAX) { + if (harvestfifo.count < RANDOM_FIFO_MAX) { event = STAILQ_FIRST(&emptyfifo.head); if (event != NULL) { /* Add the harvested data to the fifo */ STAILQ_REMOVE_HEAD(&emptyfifo.head, next); - harvestfifo[origin].count++; + emptyfifo.count--; event->somecounter = somecounter; event->size = count; event->bits = bits; @@ -239,21 +235,11 @@ random_harvestq_internal(u_int64_t somec count = MIN(count, HARVESTSIZE); memcpy(event->entropy, entropy, count); -#if 0 - { - int i; - printf("Harvest:%16jX ", event->somecounter); - for (i = 0; i < event->size; i++) - printf("%02X", event->entropy[i]); - for (; i < 16; i++) - printf(" "); - printf(" %2d %2d %02X\n", event->size, event->bits, event->source); - } -#endif - - STAILQ_INSERT_TAIL(&harvestfifo[origin].head, + STAILQ_INSERT_TAIL(&harvestfifo.head, event, next); + harvestfifo.count++; } } + mtx_unlock_spin(&harvest_mtx); } Modified: projects/random_number_generator/sys/dev/random/randomdev.c ============================================================================== --- projects/random_number_generator/sys/dev/random/randomdev.c Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/randomdev.c Sun Oct 6 09:55:28 2013 (r256081) @@ -52,9 +52,11 @@ __FBSDID("$FreeBSD$"); #include #include +#include +#include #include +#include #include -#include #define RANDOM_MINOR 0 @@ -72,6 +74,8 @@ static struct cdevsw random_cdevsw = { .d_name = "random", }; +MALLOC_DEFINE(M_ENTROPY, "entropy", "Entropy harvesting buffers"); + /* For use with make_dev(9)/destroy_dev(9). */ static struct cdev *random_dev; @@ -82,10 +86,6 @@ random_read(struct cdev *dev __unused, s int c, error = 0; void *random_buf; - /* XXX: Harvest some entropy from live entropy sources, if available */ - live_entropy_sources_feed(65); /* 65 is meaningless -- - need to decide appropriate value */ - /* Blocking logic */ if (!random_adaptor->seeded) error = (*random_adaptor->block)(flag); @@ -93,7 +93,7 @@ random_read(struct cdev *dev __unused, s /* The actual read */ if (!error) { - random_buf = (void *)malloc(PAGE_SIZE, M_TEMP, M_WAITOK); + random_buf = (void *)malloc(PAGE_SIZE, M_ENTROPY, M_WAITOK); while (uio->uio_resid > 0 && !error) { c = MIN(uio->uio_resid, PAGE_SIZE); @@ -104,7 +104,7 @@ random_read(struct cdev *dev __unused, s * optional housekeeping */ (*random_adaptor->read)(NULL, 0); - free(random_buf, M_TEMP); + free(random_buf, M_ENTROPY); } Modified: projects/random_number_generator/sys/dev/random/randomdev.h ============================================================================== --- projects/random_number_generator/sys/dev/random/randomdev.h Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/randomdev.h Sun Oct 6 09:55:28 2013 (r256081) @@ -30,6 +30,8 @@ * and non algorithm-specific for the entropy processor */ +MALLOC_DECLARE(M_ENTROPY); + typedef void random_init_func_t(void); typedef void random_deinit_func_t(void); typedef int random_block_func_t(int); Modified: projects/random_number_generator/sys/dev/random/randomdev_soft.c ============================================================================== --- projects/random_number_generator/sys/dev/random/randomdev_soft.c Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/randomdev_soft.c Sun Oct 6 09:55:28 2013 (r256081) @@ -53,9 +53,10 @@ __FBSDID("$FreeBSD$"); #include #include -#include #include #include +#include +#include #if defined(YARROW_RNG) #include #endif @@ -63,7 +64,6 @@ __FBSDID("$FreeBSD$"); #include #endif -#include "random_harvestq.h" static int randomdev_poll(int event, struct thread *td); static int randomdev_block(int flag); Modified: projects/random_number_generator/sys/dev/random/randomdev_soft.h ============================================================================== --- projects/random_number_generator/sys/dev/random/randomdev_soft.h Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/randomdev_soft.h Sun Oct 6 09:55:28 2013 (r256081) @@ -41,8 +41,6 @@ #define HARVESTSIZE 16 /* max size of each harvested entropy unit */ -MALLOC_DECLARE(M_ENTROPY); - /* These are used to queue harvested packets of entropy. The entropy * buffer size is pretty arbitrary. */ Modified: projects/random_number_generator/sys/dev/random/yarrow.c ============================================================================== --- projects/random_number_generator/sys/dev/random/yarrow.c Sun Oct 6 09:37:57 2013 (r256080) +++ projects/random_number_generator/sys/dev/random/yarrow.c Sun Oct 6 09:55:28 2013 (r256081) @@ -97,6 +97,7 @@ clear_counter(void) /* 128-bit C = C + 1 */ /* Nothing to see here, folks, just an ugly mess. */ +/* TODO: Make a Galois counter instead? */ static void increment_counter(void) { @@ -113,13 +114,25 @@ random_process_event(struct harvest *eve struct source *source; enum esource src; - /* Unpack the event into the appropriate source accumulator */ +#if 1 + /* Do this better with DTrace */ + { + int i; + + printf("Harvest:%16jX ", event->somecounter); + for (i = 0; i < event->size; i++) + printf("%02X", event->entropy[i]); + for (; i < 16; i++) + printf(" "); + printf(" %2d %2d %02X\n", event->size, event->bits, event->source); + } +#endif + + /* Accumulate the event into the appropriate pool */ pl = random_state.which; source = &random_state.pool[pl].source[event->source]; - randomdev_hash_iterate(&random_state.pool[pl].hash, event->entropy, - sizeof(event->entropy)); - randomdev_hash_iterate(&random_state.pool[pl].hash, &event->somecounter, - sizeof(event->somecounter)); + randomdev_hash_iterate(&random_state.pool[pl].hash, event, + sizeof(*event)); source->bits += event->bits; /* Count the over-threshold sources in each pool */