Overhaul the entropy device:

o Each source gets its own queue, which is a FIFO, not a ring buffer.
  The FIFOs are implemented with the sys/queue.h macros. The separation
  is so that a low entropy/high rate source can't swamp the harvester
  with low-grade entropy and destroy the reseeds.

o Each FIFO is limited to 256 (set as a macro, so adjustable) events
  queueable. Full FIFOs are ignored by the harvester. This is to
  prevent memory wastage, and helps to keep the kernel thread CPU
  usage within reasonable limits.

o There is no need to break up the event harvesting into ${burst}
  sized chunks, so retire that feature.

o Break the device away from its roots with the memory device, and
  allow it to get its major number automagically.

5 files changed, 101 insertions, 123 deletions

diff --git a/sys/dev/random/harvest.c b/sys/dev/random/harvest.c
index b73450d..fd94bd2 100644
--- a/sys/dev/random/harvest.c
+++ b/sys/dev/random/harvest.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2000 Mark R V Murray
+ * Copyright (c) 2000, 2001, 2002, 2003 Mark R V Murray
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -29,16 +29,16 @@
 __FBSDID("$FreeBSD$");
 
 #include <sys/param.h>
-#include <sys/systm.h>
-#include <sys/types.h>
-#include <sys/queue.h>
 #include <sys/kthread.h>
 #include <sys/lock.h>
+#include <sys/malloc.h>
 #include <sys/mutex.h>
 #include <sys/poll.h>
+#include <sys/queue.h>
+#include <sys/random.h>
 #include <sys/selinfo.h>
 #include <sys/sysctl.h>
-#include <sys/random.h>
+#include <sys/systm.h>
 
 #include <machine/cpu.h>
 
diff --git a/sys/dev/random/hash.c b/sys/dev/random/hash.c
index 716633d..53ddb3c 100644
--- a/sys/dev/random/hash.c
+++ b/sys/dev/random/hash.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2000 Mark R V Murray
+ * Copyright (c) 2000, 2001, 2002, 2003 Mark R V Murray
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
diff --git a/sys/dev/random/randomdev.c b/sys/dev/random/randomdev.c
index 48618e9..68793e5 100644
--- a/sys/dev/random/randomdev.c
+++ b/sys/dev/random/randomdev.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2000 Mark R V Murray
+ * Copyright (c) 2000, 2001, 2002, 2003 Mark R V Murray
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -53,41 +53,40 @@ __FBSDID("$FreeBSD$");
 
 #include <dev/random/randomdev.h>
 
-static d_open_t		random_open;
 static d_close_t	random_close;
 static d_read_t		random_read;
 static d_write_t	random_write;
 static d_ioctl_t	random_ioctl;
 static d_poll_t		random_poll;
 
-#define CDEV_MAJOR	2
-#define RANDOM_MINOR	3
+#define RANDOM_MINOR	0
+
+#define RANDOM_FIFO_MAX	256	/* How many events to queue up */
 
 static struct cdevsw random_cdevsw = {
-	.d_open =	random_open,
 	.d_close =	random_close,
 	.d_read =	random_read,
 	.d_write =	random_write,
 	.d_ioctl =	random_ioctl,
 	.d_poll =	random_poll,
 	.d_name =	"random",
-	.d_maj =	CDEV_MAJOR,
 };
 
 static void random_kthread(void *);
 static void random_harvest_internal(u_int64_t, void *, u_int, u_int, u_int, enum esource);
 static void random_write_internal(void *, int);
 
-/* Ring buffer holding harvested entropy */
-static struct harvestring {
-	volatile u_int	head;
-	volatile u_int	tail;
-	struct harvest	data[HARVEST_RING_SIZE];
-} harvestring;
+MALLOC_DEFINE(M_ENTROPY, "entropy", "Entropy harvesting buffers");
+
+/* FIFO queues holding harvested entropy */
+static struct harvestfifo {
+	struct mtx lock;
+	int count;
+	STAILQ_HEAD(harvestlist, harvest) head;
+} harvestfifo[ENTROPYSOURCE];
 
 static struct random_systat {
 	u_int		seeded;	/* 0 causes blocking 1 allows normal output */
-	u_int		burst;	/* number of events to do before sleeping */
 	struct selinfo	rsel;	/* For poll(2) */
 } random_systat;
 
@@ -109,8 +108,6 @@ random_check_boolean(SYSCTL_HANDLER_ARGS)
         return sysctl_handle_int(oidp, oidp->oid_arg1, oidp->oid_arg2, req);
 }
 
-RANDOM_CHECK_UINT(burst, 0, 20);
-
 SYSCTL_NODE(_kern, OID_AUTO, random, CTLFLAG_RW,
 	0, "Random Number Generator");
 SYSCTL_NODE(_kern_random, OID_AUTO, sys, CTLFLAG_RW,
@@ -118,9 +115,6 @@ SYSCTL_NODE(_kern_random, OID_AUTO, sys, CTLFLAG_RW,
 SYSCTL_PROC(_kern_random_sys, OID_AUTO, seeded,
 	CTLTYPE_INT|CTLFLAG_RW, &random_systat.seeded, 1,
 	random_check_boolean, "I", "Seeded State");
-SYSCTL_PROC(_kern_random_sys, OID_AUTO, burst,
-	CTLTYPE_INT|CTLFLAG_RW, &random_systat.burst, 20,
-	random_check_uint_burst, "I", "Harvest Burst Size");
 SYSCTL_NODE(_kern_random_sys, OID_AUTO, harvest, CTLFLAG_RW,
 	0, "Entropy Sources");
 SYSCTL_PROC(_kern_random_sys_harvest, OID_AUTO, ethernet,
@@ -138,28 +132,10 @@ SYSCTL_PROC(_kern_random_sys_harvest, OID_AUTO, swi,
 
 /* ARGSUSED */
 static int
-random_open(dev_t dev __unused, int flags, int fmt __unused, struct thread *td)
-{
-	int error;
-
-	if (flags & FWRITE) {
-		error = suser(td);
-		if (error)
-			return (error);
-		error = securelevel_gt(td->td_ucred, 0);
-		if (error)
-			return (error);
-	}
-	return 0;
-}
-
-/* ARGSUSED */
-static int
 random_close(dev_t dev __unused, int flags, int fmt __unused, struct thread *td)
 {
 	if (flags & FWRITE) {
-		if (!(suser(td) ||
-		    securelevel_gt(td->td_ucred, 0)))
+		if (suser(td) == 0 && securelevel_gt(td->td_ucred, 0) == 0)
 			random_reseed();
 	}
 	return 0;
@@ -250,7 +226,8 @@ random_poll(dev_t dev __unused, int events, struct thread *td)
 static int
 random_modevent(module_t mod __unused, int type, void *data __unused)
 {
-	int	error;
+	int	error, i;
+	struct harvest *np;
 
 	switch(type) {
 	case MOD_LOAD:
@@ -261,14 +238,12 @@ random_modevent(module_t mod __unused, int type, void *data __unused)
 		 */
 		random_systat.seeded = 1;
 
-		/* Number of envents to process off the harvest
-		 * queue before giving it a break and sleeping
-		 */
-		random_systat.burst = 20;
-
-		/* Initialise the harvest ringbuffer */
-		harvestring.head = 0;
-		harvestring.tail = 0;
+		/* Initialise the harvest fifos */
+		for (i = 0; i < ENTROPYSOURCE; i++) {
+			STAILQ_INIT(&harvestfifo[i].head);
+			harvestfifo[i].count = 0;
+			mtx_init(&harvestfifo[i].lock, "entropy harvest", NULL, MTX_DEF);
+		}
 
 		if (bootverbose)
 			printf("random: <entropy source>\n");
@@ -298,6 +273,16 @@ random_modevent(module_t mod __unused, int type, void *data __unused)
 		random_kthread_control = -1;
 		tsleep((void *)&random_kthread_control, PUSER, "term", 0);
 
+		/* Destroy the harvest fifos */
+		for (i = 0; i < ENTROPYSOURCE; i++) {
+			while (!STAILQ_EMPTY(&harvestfifo[i].head)) {
+				np = STAILQ_FIRST(&harvestfifo[i].head);
+				STAILQ_REMOVE_HEAD(&harvestfifo[i].head, next);
+				free(np, M_ENTROPY);
+			}
+			mtx_destroy(&harvestfifo[i].lock);
+		}
+
 		random_deinit();
 
 		destroy_dev(random_dev);
@@ -318,51 +303,53 @@ DEV_MODULE(random, random_modevent, NULL);
 static void
 random_kthread(void *arg __unused)
 {
-	struct harvest	*event;
-	u_int		newtail, burst;
+	struct harvest	*event = NULL;
+	int		found, active;
+	enum esource	source;
 
-	/* Drain the harvest queue (in 'burst' size chunks,
-	 * if 'burst' > 0. If 'burst' == 0, then completely
-	 * drain the queue.
-	 */
-	for (burst = 0; ; burst++) {
+	/* Process until told to stop */
+	for (; random_kthread_control == 0;) {
 
-		if ((harvestring.tail == harvestring.head) ||
-			(random_systat.burst && burst == random_systat.burst)) {
-				tsleep(&harvestring, PUSER, "-", hz/10);
-				burst = 0;
+		active = 0;
 
-		}
-		else {
+		/* Cycle through all the entropy sources */
+		for (source = 0; source < ENTROPYSOURCE; source++) {
 
-			/* Suck a harvested entropy event out of the queue and
-			 * hand it to the event processor
-			 */
+			found = 0;
 
-			newtail = (harvestring.tail + 1) & HARVEST_RING_MASK;
-			event = &harvestring.data[harvestring.tail];
+			/* Lock up queue draining */
+			mtx_lock(&harvestfifo[source].lock);
 
-			/* Bump the ring counter. This action is assumed
-			 * to be atomic.
-			 */
-			harvestring.tail = newtail;
+			if (!STAILQ_EMPTY(&harvestfifo[source].head)) {
 
-			random_process_event(event);
+				/* Get a harvested entropy event */
+				harvestfifo[source].count--;
+				event = STAILQ_FIRST(&harvestfifo[source].head);
+				STAILQ_REMOVE_HEAD(&harvestfifo[source].head,
+					next);
+				active = found = 1;
 
-		}
+			}
+
+			/* Unlock the queue */
+			mtx_unlock(&harvestfifo[source].lock);
+
+			/* Deal with the event and dispose of it */
+			if (found) {
+				random_process_event(event);
+				free(event, M_ENTROPY);
+			}
 
-		/* Is the thread scheduled for a shutdown? */
-		if (random_kthread_control != 0) {
-#ifdef DEBUG
-			printf("Random kthread setting terminate\n");
-#endif
-			random_set_wakeup_exit(&random_kthread_control);
-			/* NOTREACHED */
-			break;
 		}
 
+		/* Found nothing, so don't belabour the issue */
+		if (!active)
+			tsleep(&harvestfifo, PUSER, "-", hz/10);
+
 	}
 
+	random_set_wakeup_exit(&random_kthread_control);
+	/* NOTREACHED */
 }
 
 /* Entropy harvesting routine. This is supposed to be fast; do
@@ -372,34 +359,38 @@ static void
 random_harvest_internal(u_int64_t somecounter, void *entropy, u_int count,
 	u_int bits, u_int frac, enum esource origin)
 {
-	struct harvest	*pharvest;
-	u_int		newhead;
+	struct harvest	*event;
 
-	newhead = (harvestring.head + 1) & HARVEST_RING_MASK;
+	/* Lock the particular fifo */
+	mtx_lock(&harvestfifo[origin].lock);
 
-	if (newhead != harvestring.tail) {
+	/* Don't make the harvest queues too big - memory is precious */
+	if (harvestfifo[origin].count < RANDOM_FIFO_MAX) {
+		
+		event = malloc(sizeof(struct harvest), M_ENTROPY, M_NOWAIT);
 
-		/* Add the harvested data to the ring buffer */
+		/* If we can't malloc() a buffer, tough */
+		if (event) {
 
-		pharvest = &harvestring.data[harvestring.head];
+			/* Add the harvested data to the fifo */
+			harvestfifo[origin].count++;
+			event->somecounter = somecounter;
+			event->size = count;
+			event->bits = bits;
+			event->frac = frac;
+			event->source = origin;
 
-		/* Stuff the harvested data into the ring */
-		pharvest->somecounter = somecounter;
-		count = count > HARVESTSIZE ? HARVESTSIZE : count;
-		memcpy(pharvest->entropy, entropy, count);
-		pharvest->size = count;
-		pharvest->bits = bits;
-		pharvest->frac = frac;
-		pharvest->source =
-		    origin < ENTROPYSOURCE ? origin : RANDOM_START;
+			/* XXXX Come back and make this dynamic! */
+			count = count > HARVESTSIZE ? HARVESTSIZE : count;
+			memcpy(event->entropy, entropy, count);
 
-		/* Bump the ring counter. This action is assumed
-		 * to be atomic.
-		 */
-		harvestring.head = newhead;
+			STAILQ_INSERT_TAIL(&harvestfifo[origin].head, event, next);
+		}
 
 	}
 
+	mtx_unlock(&harvestfifo[origin].lock);
+
 }
 
 static void
diff --git a/sys/dev/random/randomdev.h b/sys/dev/random/randomdev.h
index 359dc26..aa23fc8 100644
--- a/sys/dev/random/randomdev.h
+++ b/sys/dev/random/randomdev.h
@@ -46,14 +46,17 @@
 
 SYSCTL_DECL(_kern_random);
 
+MALLOC_DECLARE(M_ENTROPY);
+
 /* These are used to queue harvested packets of entropy. The entropy
  * buffer size is pretty arbitrary.
  */
 struct harvest {
-	u_int64_t somecounter;		/* fast counter for clock jitter */
+	uintmax_t somecounter;		/* fast counter for clock jitter */
 	u_char entropy[HARVESTSIZE];	/* the harvested entropy */
 	u_int size, bits, frac;		/* stats about the entropy */
 	enum esource source;		/* stats about the entropy */
+	STAILQ_ENTRY(harvest) next;	/* next item on the list */
 };
 
 void random_init(void);
diff --git a/sys/dev/random/yarrow.c b/sys/dev/random/yarrow.c
index c721df7..9d4bf03 100644
--- a/sys/dev/random/yarrow.c
+++ b/sys/dev/random/yarrow.c
@@ -1,5 +1,5 @@
 /*-
- * Copyright (c) 2000 Mark R V Murray
+ * Copyright (c) 2000, 2001, 2002, 2003 Mark R V Murray
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -29,12 +29,13 @@
 __FBSDID("$FreeBSD$");
 
 #include <sys/param.h>
-#include <sys/systm.h>
 #include <sys/kernel.h>
 #include <sys/lock.h>
+#include <sys/malloc.h>
 #include <sys/mutex.h>
 #include <sys/random.h>
 #include <sys/sysctl.h>
+#include <sys/systm.h>
 
 #include <crypto/rijndael/rijndael.h>
 #include <crypto/sha2/sha2.h>
@@ -43,8 +44,6 @@ __FBSDID("$FreeBSD$");
 #include <dev/random/randomdev.h>
 #include <dev/random/yarrow.h>
 
-/* #define DEBUG */
-
 RANDOM_CHECK_UINT(gengateinterval, 4, 64);
 RANDOM_CHECK_UINT(bins, 2, 16);
 RANDOM_CHECK_UINT(fastthresh, BLOCKSIZE/4, BLOCKSIZE);
@@ -164,10 +163,6 @@ reseed(u_int fastslow)
 	u_int i;
 	enum esource j;
 
-#ifdef DEBUG
-	printf("Reseed type %d\n", fastslow);
-#endif
-
 	/* The reseed task must not be jumped on */
 	mtx_lock(&random_reseed_mtx);
 
@@ -240,10 +235,6 @@ reseed(u_int fastslow)
 	/* Release the reseed mutex */
 	mtx_unlock(&random_reseed_mtx);
 
-#ifdef DEBUG
-	printf("Reseed finish\n");
-#endif
-
 	/* Unblock the device if it was blocked due to being unseeded */
 	random_unblock();
 }
@@ -315,10 +306,6 @@ generator_gate(void)
 	u_int i;
 	u_char temp[KEYSIZE];
 
-#ifdef DEBUG
-	printf("Generator gate\n");
-#endif
-
 	for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) {
 		random_state.counter[0]++;
 		yarrow_encrypt(&random_state.key, random_state.counter,
@@ -328,9 +315,6 @@ generator_gate(void)
 	yarrow_encrypt_init(&random_state.key, temp);
 	memset((void *)temp, 0, KEYSIZE);
 
-#ifdef DEBUG
-	printf("Generator gate finish\n");
-#endif
 }
 
 /* Helper routine to perform explicit reseeds */