[RFC] enhanced version of net_random()

While doing the network emulator, I discovered that the default net_random()
is too stupid, and get_random_bytes() is more than needed. Rather than put
another function in just for sch_netem, how about making net_random() smarter?
The tin-hat crowd already replace net_random() with get_random_bytes anyway.

Here is a proposed alternative to use a longer period PRNG for net_random().
The choice of TT800 was because it was freely available, had a long period,
was fast and relatively small footprint. The existing net_random() was not
really thread safe, but was immune to thread corruption. 

Signed-off-by: Stephen Hemminger <redacted>

diff -Nru a/net/core/utils.c b/net/core/utils.c

--- a/net/core/utils.c	2004-08-12 10:40:05 -07:00
+++ b/net/core/utils.c	2004-08-12 10:40:05 -07:00

@@ -2,6 +2,7 @@
  *	Generic address resultion entity
  *
  *	Authors:
+ *	net_random update to TT800 Stephen Hemminger
  *	net_random Alan Cox
  *	net_ratelimit Andy Kleen
  *

@@ -23,6 +24,7 @@
 #include <asm/system.h>
 #include <asm/uaccess.h>
 
+#ifdef CONFIG_EMBEDDED
 static unsigned long net_rand_seed = 152L;
 
 unsigned long net_random(void)

@@ -34,8 +36,79 @@
 void net_srandom(unsigned long entropy)
 {
 	net_rand_seed ^= entropy;
+ 	net_random();
+}
+#else
+/*
+ * This is the TT800 twisted Global Finite Shift Register random number
+ * generator originally by M. Matsumoto, email: matumoto@math.keio.ac.jp.
+ * July 8th 1996 Version 
+ *
+ * See: ACM Transactions on Modelling and Computer Simulation, 
+ * Vol. 4, No. 3, 1994, pages 254-266. 
+ *
+ * It has a large period 2^800 and good distribution properties
+ * up to dimension 25, and passes statistical tests.
+ *
+ * Don't use for cryptographic purposes, see get_random_bytes instead.
+ */
+#define N 25
+#define M 7
+
+static unsigned long net_rand_seed[N] = {
+	0x95f24dab, 0x0b685215, 0xe76ccae7, 0xaf3ec239, 0x715fad23,
+	0x24a590ad, 0x69e4b5ef, 0xbf456141, 0x96bc1b7b, 0xa7bdf825,
+	0xc1de75b7, 0x8858a9c9, 0x2da87693, 0xb657f9dd, 0xffdc8a9f,
+	0x8121da71, 0x8b823ecb, 0x885d05f5, 0x4e20cd47, 0x5a9ad5d9,
+	0x512c0c03, 0xea857ccd, 0x4cc1d30f, 0x8891a8a1, 0xa6b7aadb
+};
+
+static spinlock_t net_random_lock = SPIN_LOCK_UNLOCKED;
+
+unsigned long net_random(void)
+{
+	unsigned long y;
+	unsigned long flags;
+	static int k;
+	static const unsigned long mag01[2]={ 0x0, 0x8ebfd028 };
+#define X net_rand_seed
+
+	/* generate N words at one time */
+	spin_lock_irqsave(&net_random_lock, flags);
+	if (k == N) {
+		int kk;
+		for (kk=0; kk< N - M; kk++) {
+			X[kk] = X[kk+M] ^ (X[kk] >> 1) ^ mag01[X[kk] % 2];
+		}
+
+		for (; kk < N; kk++) {
+			X[kk] = X[kk+(M-N)] ^ (X[kk] >> 1) ^ mag01[X[kk] % 2];
+		}
+		k = 0;
+	}
+
+	y = X[k];
+	y ^= (y << 7) & 0x2b5b2500; /* s and b, magic vectors */
+	y ^= (y << 15) & 0xdb8b0000; /* t and c, magic vectors */
+
+	/* 
+	 * the following line was added by Makoto Matsumoto in the 1996 version
+	 * to improve lower bit's corellation.
+	 * Delete this line to o use the code published in 1994.
+	 */
+	y ^= (y >> 16); /* added to the 1994 version */
+	k++;
+	spin_unlock_irqrestore(&net_random_lock, flags);
+#undef X
+	return y;
+}
+
+void net_srandom(unsigned long entropy)
+{
+	net_rand_seed[0] ^= entropy;
 	net_random();
 }
+#endif
 
 int net_msg_cost = 5*HZ;
 int net_msg_burst = 10;

On Thu, 12 Aug 2004 10:48:35 -0700
Stephen Hemminger [off-list ref] wrote:

Here is a proposed alternative to use a longer period PRNG for net_random().
The choice of TT800 was because it was freely available, had a long period,
was fast and relatively small footprint. The existing net_random() was not
really thread safe, but was immune to thread corruption. 

Any chance of a version that doesn't grab a global lock and
disable interrupts every call? :(

Stephen Hemminger wrote:

While doing the network emulator, I discovered that the default net_random()
is too stupid, and get_random_bytes() is more than needed. Rather than put
another function in just for sch_netem, how about making net_random() smarter?
The tin-hat crowd already replace net_random() with get_random_bytes anyway.

Here is a proposed alternative to use a longer period PRNG for net_random().
The choice of TT800 was because it was freely available, had a long period,
was fast and relatively small footprint. The existing net_random() was not
really thread safe, but was immune to thread corruption. 

Is it really worth the extra spin lock & math?  Maybe we could have a
net_more_random() method instead that encompasses this improved random logic?

Ben

-- 
Ben Greear [off-list ref]
Candela Technologies Inc  http://www.candelatech.com

Here is another alternative, using tansworthe generator.  It uses percpu
state. The one small semantic change is the net_srandom() only affects
the current cpu's seed.  The problem was that having it change all cpu's
seed would mean adding locking and the only user's today are a couple of
places that feed in mac address to try make sure address resolution to
collide.

diff -Nru a/include/linux/net.h b/include/linux/net.h

--- a/include/linux/net.h	2004-08-13 11:48:43 -07:00
+++ b/include/linux/net.h	2004-08-13 11:48:43 -07:00

@@ -169,6 +169,7 @@
 extern int	     net_ratelimit(void);
 extern unsigned long net_random(void);
 extern void	     net_srandom(unsigned long);
+extern void	     net_random_init(void);
 
 extern int   	     kernel_sendmsg(struct socket *sock, struct msghdr *msg,
 				    struct kvec *vec, size_t num, size_t len);

diff -Nru a/net/core/dev.c b/net/core/dev.c

--- a/net/core/dev.c	2004-08-13 11:48:43 -07:00
+++ b/net/core/dev.c	2004-08-13 11:48:43 -07:00

@@ -3280,6 +3280,8 @@
 
 	BUG_ON(!dev_boot_phase);
 
+	net_random_init();
+
 	if (dev_proc_init())
 		goto out;
 

diff -Nru a/net/core/utils.c b/net/core/utils.c

--- a/net/core/utils.c	2004-08-13 11:48:43 -07:00
+++ b/net/core/utils.c	2004-08-13 11:48:43 -07:00

@@ -19,22 +19,116 @@
 #include <linux/mm.h>
 #include <linux/string.h>
 #include <linux/types.h>
+#include <linux/random.h>
+#include <linux/percpu.h>
 
 #include <asm/system.h>
 #include <asm/uaccess.h>
 
-static unsigned long net_rand_seed = 152L;
+
+/*
+  This is a maximally equidistributed combined Tausworthe generator
+  based on code from GNU Scientific Library 1.5 (30 Jun 2004)
+
+   x_n = (s1_n ^ s2_n ^ s3_n) 
+
+   s1_{n+1} = (((s1_n & 4294967294) <<12) ^ (((s1_n <<13) ^ s1_n) >>19))
+   s2_{n+1} = (((s2_n & 4294967288) << 4) ^ (((s2_n << 2) ^ s2_n) >>25))
+   s3_{n+1} = (((s3_n & 4294967280) <<17) ^ (((s3_n << 3) ^ s3_n) >>11))
+
+   The period of this generator is about 2^88.
+
+   From: P. L'Ecuyer, "Maximally Equidistributed Combined Tausworthe
+   Generators", Mathematics of Computation, 65, 213 (1996), 203--213.
+
+   This is available on the net from L'Ecuyer's home page,
+
+   http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
+   ftp://ftp.iro.umontreal.ca/pub/simulation/lecuyer/papers/tausme.ps 
+
+   There is an erratum in the paper "Tables of Maximally
+   Equidistributed Combined LFSR Generators", Mathematics of
+   Computation, 68, 225 (1999), 261--269:
+   http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
+
+        ... the k_j most significant bits of z_j must be non-
+        zero, for each j. (Note: this restriction also applies to the 
+        computer code given in [4], but was mistakenly not mentioned in
+        that paper.)
+   
+   This affects the seeding procedure by imposing the requirement
+   s1 > 1, s2 > 7, s3 > 15.
+
+*/
+struct nrnd_state {
+	u32 s1, s2, s3;
+};
+
+static DEFINE_PER_CPU(struct nrnd_state, net_rand_state);
+
+static u32 __net_random(struct nrnd_state *state)
+{
+#define TAUSWORTHE(s,a,b,c,d) ((s&c)<<d) ^ (((s <<a) ^ s)>>b)
+
+	state->s1 = TAUSWORTHE(state->s1, 13, 19, 4294967294UL, 12);
+	state->s2 = TAUSWORTHE(state->s2, 2, 25, 4294967288UL, 4);
+	state->s3 = TAUSWORTHE(state->s3, 3, 11, 4294967280UL, 17);
+
+	return (state->s1 ^ state->s2 ^ state->s3);
+}
+
+static void __net_srandom(struct nrnd_state *state, unsigned long entropy)
+{
+	u32 s = state->s1 ^ entropy;
+
+	if (s == 0)
+		s = 1;      /* default seed is 1 */
+
+#define LCG(n) (69069 * n)
+	state->s1 = LCG(s);
+	state->s2 = LCG(state->s1);
+	state->s3 = LCG(state->s2);
+
+	/* "warm it up" */
+	__net_random(state);
+	__net_random(state);
+	__net_random(state);
+	__net_random(state);
+	__net_random(state);
+	__net_random(state);
+}
+
 
 unsigned long net_random(void)
 {
-	net_rand_seed=net_rand_seed*69069L+1;
-        return net_rand_seed^jiffies;
+	unsigned long r;
+	struct nrnd_state *state = &get_cpu_var(net_rand_state);
+	r = __net_random(state);
+	put_cpu_var(state);
+	return r;
 }
 
+
 void net_srandom(unsigned long entropy)
 {
-	net_rand_seed ^= entropy;
-	net_random();
+	struct nrnd_state *state = &get_cpu_var(net_rand_state);
+	__net_srandom(state, entropy);
+	put_cpu_var(state);
+}
+
+void __init net_random_init(void)
+{
+	int i;
+	unsigned long seed[NR_CPUS];
+
+	get_random_bytes(seed, sizeof(seed));
+
+	for (i = 0; i < NR_CPUS; i++) {
+		struct nrnd_state *state = &per_cpu(net_rand_state,i);
+
+		memset(state, 0, sizeof(*state));
+		__net_srandom(state, seed[i]);
+	}
 }
 
 int net_msg_cost = 5*HZ;

On Fri, 13 Aug 2004 11:51:40 -0700
Stephen Hemminger [off-list ref] wrote:

Here is another alternative, using tansworthe generator.  It uses percpu
state. The one small semantic change is the net_srandom() only affects
the current cpu's seed.  The problem was that having it change all cpu's
seed would mean adding locking 

I would just update the other CPUs without locking. Taking
a random number from a partially updated state shouldn't be a big 
issue.

-Andi

On Fri, 13 Aug 2004 21:28:57 +0200
Andi Kleen [off-list ref] wrote:

On Fri, 13 Aug 2004 11:51:40 -0700
Stephen Hemminger [off-list ref] wrote:

quoted

Here is another alternative, using tansworthe generator.  It uses percpu
state. The one small semantic change is the net_srandom() only affects
the current cpu's seed.  The problem was that having it change all cpu's
seed would mean adding locking 

I would just update the other CPUs without locking. Taking
a random number from a partially updated state shouldn't be a big 
issue.

I personally don't think we need to touch the other cpus
at all, and that having a different current seed on each
cpu might actually be a good thing.

Stephen, I like this one a lot, especially compared to
what we had before.  I'm going to add this to my tree for
the time being.

Is there a reason why get_random_bytes() is unsuitable?

Keeping the number of PRNGs in the kernel to a minimum should a goal we can
all share.

JLC

On Thu, Aug 12, 2004 at 10:48:35AM -0700, Stephen Hemminger wrote:

On Fri, 20 Aug 2004 13:59:52 -0400
Jean-Luc Cooke [off-list ref] wrote:

Is there a reason why get_random_bytes() is unsuitable?

Keeping the number of PRNGs in the kernel to a minimum should a goal we can
all share.

Too expensive, this routine will get called potentially multiple times
per packet.

On Aug 20, 2004  13:59 -0400, Jean-Luc Cooke wrote:

Is there a reason why get_random_bytes() is unsuitable?

Keeping the number of PRNGs in the kernel to a minimum should a goal we can
all share.

For some uses a decent PRNG is enough, and the overhead of get_random_bytes()
is much too high.  We've needed something like this for a long time (something
that gives decenly uniform numbers) and hacks to use useconds/cycles/etc do
not cut it.  I for one welcome a simple in-kernel interface to
e.g. get_urandom_bytes() (or net_random() as this is maybe inappropriately
called) that is only pseudo-random but fast and efficient.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://members.shaw.ca/adilger/             http://members.shaw.ca/golinux/

On Fri, 20 Aug 2004, Andreas Dilger wrote:

On Aug 20, 2004  13:59 -0400, Jean-Luc Cooke wrote:

quoted

Is there a reason why get_random_bytes() is unsuitable?

Keeping the number of PRNGs in the kernel to a minimum should a goal we can
all share.

For some uses a decent PRNG is enough, and the overhead of get_random_bytes()
is much too high.  We've needed something like this for a long time (something
that gives decenly uniform numbers) and hacks to use useconds/cycles/etc do
not cut it.  I for one welcome a simple in-kernel interface to
e.g. get_urandom_bytes() (or net_random() as this is maybe inappropriately
called) that is only pseudo-random but fast and efficient.

Cheers, Andreas
--
Andreas Dilger

The attached code will certainly work on Intel machines. It is
in the public domain, having been modified by myself to produce
a very long sequence...

I wouldn't suggest converting it to 'C' because the rotation
takes many CPU instructions when one tries to do the test, shift,
and OR in 'C',

Cheers,
Dick Johnson
Penguin : Linux version 2.4.26 on an i686 machine (5570.56 BogoMips).
            Note 96.31% of all statistics are fiction.

On Fri, 20 Aug 2004 15:22:09 -0400 (EDT)
"Richard B. Johnson" [off-list ref] wrote:

The attached code will certainly work on Intel machines. It is
in the public domain, having been modified by myself to produce
a very long sequence...

How long a period does it have?  The one we're adding to the
networking has one which is 2^88.

I wouldn't suggest converting it to 'C' because the rotation
takes many CPU instructions when one tries to do the test, shift,
and OR in 'C',

You only need 2 'shifts' and an 'or' to do a rotate in C.
No tests are needed.

If speed is what you want, and you want a period > 2^N.

Then a single get_rand_bytes() to fill a seed of a simple LFSR might do.

Seed value will be N+1 bits long.

Rochard's PRNG does not have a period > 2^32, that's for sure.

JLC

On Fri, Aug 20, 2004 at 12:48:23PM -0700, David S. Miller wrote:

On Fri, 20 Aug 2004 15:22:09 -0400 (EDT)
"Richard B. Johnson" [off-list ref] wrote:

quoted

The attached code will certainly work on Intel machines. It is
in the public domain, having been modified by myself to produce
a very long sequence...

How long a period does it have?  The one we're adding to the
networking has one which is 2^88.

quoted

I wouldn't suggest converting it to 'C' because the rotation
takes many CPU instructions when one tries to do the test, shift,
and OR in 'C',

You only need 2 'shifts' and an 'or' to do a rotate in C.
No tests are needed.

On Fri, 2004-08-20 at 14:59, Andreas Dilger wrote:

On Aug 20, 2004  13:59 -0400, Jean-Luc Cooke wrote:

quoted

Is there a reason why get_random_bytes() is unsuitable?

Keeping the number of PRNGs in the kernel to a minimum should a goal we can
all share.

For some uses a decent PRNG is enough, and the overhead of get_random_bytes()
is much too high.

Agreed.  I have numbers to support the above.

  We've needed something like this for a long time (something
that gives decenly uniform numbers) and hacks to use useconds/cycles/etc do
not cut it.  I for one welcome a simple in-kernel interface to
e.g. get_urandom_bytes() (or net_random() as this is maybe inappropriately
called) that is only pseudo-random but fast and efficient.

One problem is that AIUI, we incur this overhead even if a hardware RNG
is present.  This does not seem right.  Hardware RNGs are increasingly
common, Linux supports hardware RNGs from AMD, Intel, and VIA.

Lee 

On Gwe, 2004-08-20 at 22:24, Lee Revell wrote:

One problem is that AIUI, we incur this overhead even if a hardware RNG
is present.  This does not seem right.  Hardware RNGs are increasingly
common, Linux supports hardware RNGs from AMD, Intel, and VIA.

Hardware RNG's are actually fairly slow and thus are better as sources
to perturb a PRNG.

On Fri, 20 Aug 2004 12:48:23 -0700
"David S. Miller" [off-list ref] wrote:

quoted

I wouldn't suggest converting it to 'C' because the rotation
takes many CPU instructions when one tries to do the test, shift,
and OR in 'C',

You only need 2 'shifts' and an 'or' to do a rotate in C.
No tests are needed.

gcc is clever enough to detect the common C patterns for rotate
and generate a real ROL when the CPU supports it.

-Andi

The attached code will certainly work on Intel machines. It is
in the public domain, having been modified by myself to produce
a very long sequence...

I wouldn't suggest converting it to 'C' because the rotation
takes many CPU instructions when one tries to do the test, shift,
and OR in 'C',

Cheers,
Dick Johnson
Penguin : Linux version 2.4.26 on an i686 machine (5570.56 BogoMips).
            Note 96.31% of all statistics are fiction.

My choice of PRNG was not random. I am not a mathematician (IANAM),
but what I was looking for was:

+ well researched
+ fast
+ good distribution
+ small seed (since per cpu)
+ Free and open

The second version uses tausworthe because it was the fastest in the GNU scientific
library and had good properties.

See:

http://www1.physik.tu-muenchen.de/~gammel/matpack/html/LibDoc/Numbers/Random.html
----------
Returns integer pseudorandom numbers uniformly distributed within [0,4294967295].
The period length is approximately 288 (which is 3*1026).

This is Pierre L'Ecuyer's 1996 three-component Tausworthe generator "taus88"

This generator is very fast and passes all standard statistical tests.

P. L'Ecuyer, Maximally equidistributed combined Tausworthe generators, Mathematics of Computation 65, 203-213 (1996), see Figure 4.
P. L'Ecuyer, Random number generation, chapter 4 of the Handbook on Simulation, Ed. Jerry Banks, Wiley, 1997.
--------
http://www.gnu.org/software/gsl/manual/gsl-ref_17.html

Performance
The following table shows the relative performance of a selection the available random number generators. The fastest simulation quality generators are taus, gfsr4 and mt19937. The generators which offer the best mathematically-proven quality are those based on the RANLUX algorithm.

1754 k ints/sec,    870 k doubles/sec, taus
1613 k ints/sec,    855 k doubles/sec, gfsr4
1370 k ints/sec,    769 k doubles/sec, mt19937
 565 k ints/sec,    571 k doubles/sec, ranlxs0
 400 k ints/sec,    405 k doubles/sec, ranlxs1
 490 k ints/sec,    389 k doubles/sec, mrg
 407 k ints/sec,    297 k doubles/sec, ranlux
 243 k ints/sec,    254 k doubles/sec, ranlxd1
 251 k ints/sec,    253 k doubles/sec, ranlxs2
 238 k ints/sec,    215 k doubles/sec, cmrg
 247 k ints/sec,    198 k doubles/sec, ranlux389
 141 k ints/sec,    140 k doubles/sec, ranlxd2

1852 k ints/sec,    935 k doubles/sec, ran3
 813 k ints/sec,    575 k doubles/sec, ran0
 787 k ints/sec,    476 k doubles/sec, ran1
 379 k ints/sec,    292 k doubles/sec, ran2

On Mon, 23 Aug 2004, Stephen Hemminger wrote:

quoted

The attached code will certainly work on Intel machines. It is
in the public domain, having been modified by myself to produce
a very long sequence...

I wouldn't suggest converting it to 'C' because the rotation
takes many CPU instructions when one tries to do the test, shift,
and OR in 'C',

My choice of PRNG was not random. I am not a mathematician (IANAM),
but what I was looking for was:

+ well researched
+ fast
+ good distribution
+ small seed (since per cpu)
+ Free and open

The second version uses tausworthe because it was the fastest in the GNU scientific
library and had good properties.

See:

http://www1.physik.tu-muenchen.de/~gammel/matpack/html/LibDoc/Numbers/Random.html
----------
Returns integer pseudorandom numbers uniformly distributed within [0,4294967295].
The period length is approximately 288 (which is 3*1026).

This is Pierre L'Ecuyer's 1996 three-component Tausworthe generator "taus88"

This generator is very fast and passes all standard statistical tests.

P. L'Ecuyer, Maximally equidistributed combined Tausworthe generators, Mathematics of Computation 65, 203-213 (1996), see Figure 4.
P. L'Ecuyer, Random number generation, chapter 4 of the Handbook on Simulation, Ed. Jerry Banks, Wiley, 1997.
--------
http://www.gnu.org/software/gsl/manual/gsl-ref_17.html

Performance
The following table shows the relative performance of a selection the available random number generators. The fastest simulation quality generators are taus, gfsr4 and mt19937. The generators which offer the best mathematically-proven quality are those based on the RANLUX algorithm.

1754 k ints/sec,    870 k doubles/sec, taus
1613 k ints/sec,    855 k doubles/sec, gfsr4
1370 k ints/sec,    769 k doubles/sec, mt19937
 565 k ints/sec,    571 k doubles/sec, ranlxs0
 400 k ints/sec,    405 k doubles/sec, ranlxs1
 490 k ints/sec,    389 k doubles/sec, mrg
 407 k ints/sec,    297 k doubles/sec, ranlux
 243 k ints/sec,    254 k doubles/sec, ranlxd1
 251 k ints/sec,    253 k doubles/sec, ranlxs2
 238 k ints/sec,    215 k doubles/sec, cmrg
 247 k ints/sec,    198 k doubles/sec, ranlux389
 141 k ints/sec,    140 k doubles/sec, ranlxd2

1852 k ints/sec,    935 k doubles/sec, ran3
 813 k ints/sec,    575 k doubles/sec, ran0
 787 k ints/sec,    476 k doubles/sec, ran1
 379 k ints/sec,    292 k doubles/sec, ran2

The rnd that I submitted is fast. That's all. For communications
it has been found to be good enough. Remember the saying; "Better
is the enemy of good enough". It obviously can't have a period
of better than 2^32 and, in fact, it has a period of:

	4294896635 [0xfffeebfb].

This generates 199,962,632 integers per second on this 2.8 GHz machine.
This is a callable procedure that uses a pointer to private
data. The speed could be improved if this overhead is not required.

The distribution has also been found to be good enough for spread-
spectrum use. There are no missing codes although a sorted-
list of return values will show that there are some values (codes)
that are generated close together, in other words some people
expect that if you get a return code of '1', the next one won't
be '2', but something "very far away". This generator seems
to work more like "real world" noise sources except that such
noise sources may give you duplicate values, which this won't.

Depending upon how much time you wish to waste for making it
better than "good enough", this can be cascaded to give a
period of any length (you use one generator to produce the
"magic number" for another, etc.)



Cheers,
Dick Johnson
Penguin : Linux version 2.4.26 on an i686 machine (5570.56 BogoMips).
            Note 96.31% of all statistics are fiction.