replacement algorithm. initialize a 64K-short buffer using Durstenfeld

shuffle. Upon allocation, swap-permute the new value to a random slot in
the 0..32K-1 th entry of the buffer as we move forward, ensuring randomness
but also satisfying the non-repeating property we need.  Also avoid the value
of 0, since IP ID's of 0 are special.  Inspired by Dillon's implementation.
We believe this is easier to read though, initializes with less bias, handles
the ID of 0 properly, and wins speed tests.
Thanks a lot to mcbride and djm for doing a bunch of statistical and speed
analysis, and comments from nordin
ok mcbride djm

1 files changed, 59 insertions, 167 deletions

diff --git a/sys/netinet/ip_id.c b/sys/netinet/ip_id.c
index f557519f76f..a8aef8c299b 100644
--- a/sys/netinet/ip_id.c
+++ b/sys/netinet/ip_id.c
@@ -1,188 +1,80 @@
-/* $OpenBSD: ip_id.c,v 1.15 2007/11/26 09:28:33 martynas Exp $ */
+/*	$OpenBSD: ip_id.c,v 1.16 2008/02/29 03:37:26 deraadt Exp $ */
 
 /*
- * Copyright 1998 Niels Provos <provos@citi.umich.edu>
- * All rights reserved.
+ * Copyright (c) 2008 Theo de Raadt, Ryan McBride
+ * 
+ * Slightly different algorithm from the one designed by
+ * Matthew Dillon <dillon@backplane.com> for The DragonFly Project
+ * 
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
  *
- * Theo de Raadt <deraadt@openbsd.org> came up with the idea of using
- * such a mathematical system to generate more random (yet non-repeating)
- * ids to solve the resolver/named problem.  But Niels designed the
- * actual system based on the constraints.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
- * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
- * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
- * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
- * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
 
 /*
- * seed = random 15bit
- * n = prime, g0 = generator to n,
- * j = random so that gcd(j,n-1) == 1
- * g = g0^j mod n will be a generator again.
- *
- * X[0] = random seed.
- * X[n] = a*X[n-1]+b mod m is a Linear Congruential Generator
- * with a = 7^(even random) mod m,
- *      b = random with gcd(b,m) == 1
- *      m = 31104 and a maximal period of m-1.
- *
- * The transaction id is determined by:
- * id[n] = seed xor (g^X[n] mod n)
- *
- * Effectively the id is restricted to the lower 15 bits, thus
- * yielding two different cycles by toggling the msb on and off.
- * This avoids reuse issues caused by reseeding.
+ * Random ip sequence number generator.  Use the system PRNG to shuffle
+ * the 65536 entry ID space.  We reshuffle the ID we pick out of the array
+ * into the previous 32767 cells, providing an guarantee that an ID will not
+ * be reused for at least 32768 calls.
  */
-
 #include <sys/param.h>
-#include <sys/kernel.h>
-
 #include <dev/rndvar.h>
 
-#define RU_OUT  180		/* Time after wich will be reseeded */
-#define RU_MAX	30000		/* Uniq cycle, avoid blackjack prediction */
-#define RU_GEN	2		/* Starting generator */
-#define RU_N	32749		/* RU_N-1 = 2*2*3*2729 */
-#define RU_AGEN	7		/* determine ru_a as RU_AGEN^(2*rand) */
-#define RU_M	31104		/* RU_M = 2^7*3^5 - don't change */
-
-#define PFAC_N 3
-const static u_int16_t pfacts[PFAC_N] = {
-	2,
-	3,
-	2729
-};
+static u_int16_t ip_shuffle[65536];
+static int isindex = 0;
 
-static u_int16_t ru_x;
-static u_int16_t ru_seed, ru_seed2;
-static u_int16_t ru_a, ru_b;
-static u_int16_t ru_g;
-static u_int16_t ru_counter = 0;
-static u_int16_t ru_msb = 0;
-static long ru_reseed;
-static u_int32_t tmp;		/* Storage for unused random */
-
-u_int16_t pmod(u_int16_t, u_int16_t, u_int16_t);
-void ip_initid(void);
 u_int16_t ip_randomid(void);
 
 /*
- * Do a fast modular exponation, returned value will be in the range
- * of 0 - (mod-1)
- */
-
-u_int16_t
-pmod(u_int16_t gen, u_int16_t expo, u_int16_t mod)
-{
-	u_int16_t s, t, u;
-
-	s = 1;
-	t = gen;
-	u = expo;
-
-	while (u) {
-		if (u & 1)
-			s = (s*t) % mod;
-		u >>= 1;
-		t = (t*t) % mod;
-	}
-	return (s);
-}
-
-/*
- * Initializes the seed and chooses a suitable generator. Also toggles
- * the msb flag. The msb flag is used to generate two distinct
- * cycles of random numbers and thus avoiding reuse of ids.
+ * Return a random IP id.  Shuffle the new value we get into the previous half
+ * of the ip_shuffle ring (-32767 or swap with ourself), to avoid duplicates
+ * occuring too quickly but also still be random.
  *
- * This function is called from id_randomid() when needed, an
- * application does not have to worry about it.
+ * 0 is a special IP ID -- don't return it.
  */
-void
-ip_initid(void)
-{
-	u_int16_t j, i;
-	int noprime = 1;
-
-	ru_x = ((tmp = arc4random()) & 0xFFFF) % RU_M;
-
-	/* 15 bits of random seed */
-	ru_seed = (tmp >> 16) & 0x7FFF;
-	ru_seed2 = arc4random() & 0x7FFF;
-
-	/* Determine the LCG we use */
-	ru_b = ((tmp = arc4random()) & 0xfffe) | 1;
-	ru_a = pmod(RU_AGEN, (tmp >> 16) & 0xfffe, RU_M);
-	while (ru_b % 3 == 0)
-		ru_b += 2;
-
-	j = (tmp = arc4random()) % RU_N;
-	tmp = tmp >> 16;
-
-	/*
-	 * Do a fast gcd(j,RU_N-1), so we can find a j with
-	 * gcd(j, RU_N-1) == 1, giving a new generator for
-	 * RU_GEN^j mod RU_N
-	 */
-
-	while (noprime) {
-		for (i = 0; i < PFAC_N; i++)
-			if (j % pfacts[i] == 0)
-				break;
-
-		if (i >= PFAC_N)
-			noprime = 0;
-		else
-			j = (j+1) % RU_N;
-	}
-
-	ru_g = pmod(RU_GEN,j,RU_N);
-	ru_counter = 0;
-
-	ru_reseed = time_second + RU_OUT;
-	ru_msb = ru_msb == 0x8000 ? 0 : 0x8000;
-}
-
 u_int16_t
 ip_randomid(void)
 {
-	int i, n;
-
-	if (ru_counter >= RU_MAX || time_second > ru_reseed)
-		ip_initid();
-
-#if 0
-	if (!tmp)
-		tmp = arc4random();
-
-	/* Skip a random number of ids */
-	n = tmp & 0x3; tmp = tmp >> 2;
-	if (ru_counter + n >= RU_MAX)
-		ip_initid();
-#else
-	n = 0;
-#endif
-
-	for (i = 0; i <= n; i++)
-		/* Linear Congruential Generator */
-		ru_x = (ru_a * ru_x + ru_b) % RU_M;
-
-	ru_counter += i;
+	static int ipid_initialized;
+	u_int16_t si, r;
+	int i, i2;
+
+	if (!ipid_initialized) {
+		ipid_initialized = 1;
+
+		/*
+		 * Initialize using a Durstenfeld shuffle. Even if our PRNG
+		 * is imperfect at boot time, we have deferred doing this until
+		 * the first packet being sent and now must generate an ID.
+		 */
+		for (i = 0; i < sizeof(ip_shuffle)/sizeof(ip_shuffle[0]); ++i)
+			ip_shuffle[i] = i;
+		for (i = sizeof(ip_shuffle)/sizeof(ip_shuffle[0]); --i; ) {
+			/* disregard the modulo bias because it is small */
+			i2 = arc4random() % (i + 1);
+			r = ip_shuffle[i];
+			ip_shuffle[i] = ip_shuffle[i2];
+			ip_shuffle[i2] = r;
+		}
+	}
 
-	return (ru_seed ^ pmod(ru_g,ru_seed2 + ru_x, RU_N)) | ru_msb;
+	do {
+		arc4random_bytes(&si, sizeof(si));
+		i = isindex & 0xFFFF;
+		i2 = (isindex - (si & 0x7FFF)) & 0xFFFF;
+		r = ip_shuffle[i];
+		ip_shuffle[i] = ip_shuffle[i2];
+		ip_shuffle[i2] = r;
+		isindex++;
+	} while (r == 0);
+
+	return (r);
 }