replace linked lists for event queue with circular buffer,

which gives two advantages -- faster and smaller.
do not arc4_stir on pool overflow, it takes too much time, instead
just hash data in and keep entropy count trim.
some minor cleanups here and there.
fixes overdropping of entropy on non-idle system load.
provos@ ok

1 files changed, 91 insertions, 89 deletions

diff --git a/sys/dev/rnd.c b/sys/dev/rnd.c
index dede449fae9..77a4c54e419 100644
--- a/sys/dev/rnd.c
+++ b/sys/dev/rnd.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: rnd.c,v 1.38 2000/04/18 15:11:28 hugh Exp $	*/
+/*	$OpenBSD: rnd.c,v 1.39 2000/06/08 02:39:08 mickey Exp $	*/
 
 /*
  * random.c -- A strong random number generator
@@ -229,13 +229,6 @@
  * Any flaws in the design are solely my responsibility, and should
  * not be attributed to the Phil, Colin, or any of authors of PGP.
  *
- * The code for SHA transform was taken from Peter Gutmann's
- * implementation, which has been placed in the public domain.
- * The code for MD5 transform was taken from Colin Plumb's
- * implementation, which has been placed in the public domain.
- * The MD5 cryptographic checksum was devised by Ronald Rivest, and is
- * documented in RFC 1321, "The MD5 Message Digest Algorithm".
- *
  * Further background information on this topic may be obtained from
  * RFC 1750, "Randomness Recommendations for Security", by Donald
  * Eastlake, Steve Crocker, and Jeff Schiller.
@@ -361,8 +354,8 @@ int	rnd_debug = 0x0000;
  */
 
 /* pIII/333 reported to have some drops w/ these numbers */
-#define QEVLEN 96
-#define QEVSLOW 64 /* yet another 0.75 for 60-minutes hour /-; */
+#define QEVLEN (1024 / sizeof(struct rand_event))
+#define QEVSLOW (QEVLEN * 3 / 4) /* yet another 0.75 for 60-minutes hour /-; */
 #define QEVSBITS 12
 
 /* There is actually only one of these, globally. */
@@ -372,7 +365,6 @@ struct random_bucket {
 	u_char	input_rotate;
 	u_int32_t pool[POOLWORDS];
 	u_int	asleep;
-	u_int	queued;
 	u_int	tmo;
 };
 
@@ -393,9 +385,8 @@ struct arc4_stream {
 };
 
 struct rand_event {
-	struct rand_event *re_next;
 	struct timer_rand_state *re_state;
-	u_char re_nbits;
+	u_int re_nbits;
 	u_int re_time;
 	u_int re_val;
 };
@@ -405,8 +396,7 @@ struct random_bucket random_state;
 struct arc4_stream arc4random_state;
 struct timer_rand_state rnd_states[RND_SRC_NUM];
 struct rand_event rnd_event_space[QEVLEN];
-struct rand_event *rnd_event_q;
-struct rand_event *rnd_event_free;
+struct rand_event *rnd_event_head, *rnd_event_tail;
 
 int rnd_attached;
 int arc4random_initialized;
@@ -422,6 +412,46 @@ static __inline u_int32_t roll(u_int32_t w, int i)
 	return w;
 }
 
+/* must be called at a proper spl, returns ptr to the next event */
+static __inline struct rand_event *
+rnd_get(void)
+{
+	struct rand_event *p = rnd_event_tail;
+
+	if (p == rnd_event_head)
+		return NULL;
+
+	if (p + 1 == &rnd_event_space[QEVLEN])
+		rnd_event_tail = rnd_event_space;
+	else
+		rnd_event_tail++;
+
+	return p;
+}
+
+/* must be called at a proper spl, returns next available item */
+static __inline struct rand_event *
+rnd_put(void)
+{
+	struct rand_event *p = rnd_event_head + 1;
+
+	if (p == &rnd_event_space[QEVLEN])
+		p = rnd_event_space;
+
+	if (p == rnd_event_tail)
+		return NULL;
+
+	return rnd_event_head = p;
+}
+
+/* must be called at a proper spl, returns number of items in the queue */
+static __inline int
+rnd_qlen(void)
+{
+	int len = rnd_event_head - rnd_event_tail;
+	return (len < 0)? -len : len;
+}
+
 void dequeue_randomness __P((void *));
 
 static __inline void add_entropy_words __P((const u_int32_t *, u_int n));
@@ -535,8 +565,6 @@ void
 randomattach(void)
 {
 	int i;
-	struct timeval tv;
-	struct rand_event *rep;
 
 	if (rnd_attached) {
 #ifdef RNDEBUG
@@ -552,16 +580,17 @@ randomattach(void)
 	rnd_states[RND_SRC_TRUE].max_entropy = 1;
 
 	bzero(&rndstats, sizeof(rndstats));
+
 	bzero(&rnd_event_space, sizeof(rnd_event_space));
-	rnd_event_free = rnd_event_space;
-	for (rep = rnd_event_space; rep < &rnd_event_space[QEVLEN-1]; rep++)
-		rep->re_next = rep + 1;
+	rnd_event_head = rnd_event_tail = rnd_event_space;
+
 	for (i = 0; i < 256; i++)
 		arc4random_state.s[i] = i;
-	microtime(&tv);
-	timeout_set(&rnd_timeout, dequeue_randomness, NULL);
-	timeout_set(&arc4_timeout, arc4_reinit, NULL);
 	arc4_reinit(NULL);
+
+	timeout_set(&rnd_timeout, dequeue_randomness, &random_state);
+	timeout_set(&arc4_timeout, arc4_reinit, NULL);
+
 	rnd_attached = 1;
 }
 
@@ -608,13 +637,10 @@ add_entropy_words(buf, n)
 		0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
 		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278
 	};
-	u_int i;
-	int new_rotate;
-	u_int32_t w;
 
 	while (n--) {
-		w = roll(*buf, random_state.input_rotate);
-		i = random_state.add_ptr =
+		register u_int32_t w = roll(*buf, random_state.input_rotate);
+		register u_int i = random_state.add_ptr =
 		    (random_state.add_ptr - 1) & (POOLWORDS - 1);
 		/*
 		 * Normally, we add 7 bits of rotation to the pool.
@@ -622,18 +648,16 @@ add_entropy_words(buf, n)
 		 * rotation, so that successive passes spread the
 		 * input bits across the pool evenly.
 		 */
-		new_rotate = random_state.input_rotate + 14;
-		if (i)
-			new_rotate = random_state.input_rotate + 7;
-		random_state.input_rotate = new_rotate & 31;
+		random_state.input_rotate =
+		    (random_state.input_rotate + (i? 7 : 14)) & 31;
 
 		/* XOR in the various taps */
-		w ^= random_state.pool[(i+TAP1)&(POOLWORDS-1)];
-		w ^= random_state.pool[(i+TAP2)&(POOLWORDS-1)];
-		w ^= random_state.pool[(i+TAP3)&(POOLWORDS-1)];
-		w ^= random_state.pool[(i+TAP4)&(POOLWORDS-1)];
-		w ^= random_state.pool[(i+TAP5)&(POOLWORDS-1)];
-		w ^= random_state.pool[i];
+		w ^= random_state.pool[(i+TAP1) & (POOLWORDS-1)] ^
+		     random_state.pool[(i+TAP2) & (POOLWORDS-1)] ^
+		     random_state.pool[(i+TAP3) & (POOLWORDS-1)] ^
+		     random_state.pool[(i+TAP4) & (POOLWORDS-1)] ^
+		     random_state.pool[(i+TAP5) & (POOLWORDS-1)] ^
+		     random_state.pool[i];
 		random_state.pool[i] = (w >> 3) ^ twist_table[w & 7];
 	}
 }
@@ -654,6 +678,7 @@ void
 enqueue_randomness(state, val)
 	int	state, val;
 {
+	struct random_bucket *rs = &random_state;
 	struct timer_rand_state *p;
 	struct timeval	tv;
 	register struct rand_event *rep;
@@ -721,7 +746,7 @@ enqueue_randomness(state, val)
 		 * the logic is to drop low-entropy entries,
 		 * in hope for dequeuing to be more sourcefull
 		 */
-		if (random_state.queued > QEVSLOW && nbits < QEVSBITS) {
+		if (rnd_qlen() > QEVSLOW && nbits < QEVSBITS) {
 			rndstats.rnd_drople++;
 			return;
 		}
@@ -732,29 +757,23 @@ enqueue_randomness(state, val)
 		nbits = 8 * sizeof(val) - 1;
 
 	s = splhigh();
-	if ((rep = rnd_event_free) == NULL) {
+	if ((rep = rnd_put()) == NULL) {
 		rndstats.rnd_drops++;
 		splx(s);
 		return;
 	}
-	rnd_event_free = rep->re_next;
 
 	rep->re_state = p;
 	rep->re_nbits = nbits;
 	rep->re_time = time;
 	rep->re_val = val;
 
-	rep->re_next = rnd_event_q;
-	rnd_event_q = rep;
-	rep = rep->re_next;
-	random_state.queued++;
-
 	rndstats.rnd_enqs++;
 	rndstats.rnd_ed[nbits]++;
 	rndstats.rnd_sc[state]++;
 	rndstats.rnd_sb[state] += nbits;
 
-	if (++random_state.queued > QEVSLOW/2 && !random_state.tmo) {
+	if (rnd_qlen() > QEVSLOW/2 && !rs->tmo) {
 		random_state.tmo++;
 		timeout_add(&rnd_timeout, 1);
 	}
@@ -765,59 +784,46 @@ void
 dequeue_randomness(v)
 	void *v;
 {
+	struct random_bucket *rs = v;
 	register struct rand_event *rep;
-	u_int32_t val, time;
+	u_int32_t buf[2];
 	u_int nbits;
 	int s;
 
 	timeout_del(&rnd_timeout);
 	rndstats.rnd_deqs++;
 
-	do {
-		s = splhigh();
-		if (rnd_event_q == NULL) {
-			splx(s);
-			break;
-		}
-		rep = rnd_event_q;
-		rnd_event_q = rep->re_next;
-		random_state.queued--;
+	s = splhigh();
+	while ((rep = rnd_get())) {
 
-		val = rep->re_val;
-		time = rep->re_time;
+		buf[0] = rep->re_time;
+		buf[1] = rep->re_val;
 		nbits = rep->re_nbits;
-
-		rep->re_next = rnd_event_free;
-		rnd_event_free = rep;
 		splx(s);
 
-		/* Prevent overflow */
-		if ((random_state.entropy_count + nbits) > POOLBITS &&
-		    arc4random_state.cnt > 253)
-			arc4_stir();
+		add_entropy_words(buf, 2);
 
-		add_entropy_words(&val, 1);
-		add_entropy_words(&time, 1);
-
-		random_state.entropy_count += nbits;
 		rndstats.rnd_total += nbits;
-		if (random_state.entropy_count > POOLBITS)
-			random_state.entropy_count = POOLBITS;
+		rs->entropy_count += nbits;
+		if (rs->entropy_count > POOLBITS)
+			rs->entropy_count = POOLBITS;
 
-		if (random_state.entropy_count > 8 &&
-		    random_state.asleep != 0) {
+		if (rs->asleep && rs->entropy_count > 8) {
 #ifdef	RNDEBUG
 			if (rnd_debug & RD_WAIT)
 				printf("rnd: wakeup[%u]{%u}\n",
-				    random_state.asleep,
-				    random_state.entropy_count);
+				    rs->asleep,
+				    rs->entropy_count);
 #endif
-			random_state.asleep--;
-			wakeup(&random_state.asleep);
+			rs->asleep--;
+			wakeup((void *)&rs->asleep);
 		}
-	} while(1);
 
-	random_state.tmo = 0;
+		s = splhigh();
+	}
+
+	rs->tmo = 0;
+	splx(s);
 }
 
 #if POOLWORDS % 16
@@ -835,19 +841,16 @@ extract_entropy(buf, nbytes)
 	register u_int8_t *buf;
 	int	nbytes;
 {
+	struct random_bucket *rs = &random_state;
 	MD5_CTX tmp;
 	u_char buffer[16];
 
 	add_timer_randomness(nbytes);
 
-	/* Redundant, but just in case... */
-	if (random_state.entropy_count > POOLBITS)
-		random_state.entropy_count = POOLBITS;
-
-	if (random_state.entropy_count / 8 > nbytes)
-		random_state.entropy_count -= nbytes*8;
+	if (rs->entropy_count / 8 > nbytes)
+		rs->entropy_count -= nbytes*8;
 	else
-		random_state.entropy_count = 0;
+		rs->entropy_count = 0;
 
 	while (nbytes) {
 		register u_char *p = buf;
@@ -860,8 +863,7 @@ extract_entropy(buf, nbytes)
 
 		/* Hash the pool to get the output */
 		MD5Init(&tmp);
-		MD5Update(&tmp, (u_int8_t*)random_state.pool,
-		    sizeof(random_state.pool));
+		MD5Update(&tmp, (u_int8_t*)rs->pool, sizeof(rs->pool));
 		MD5Final(p, &tmp);
 
 		/*