[RFC] enhanced version of net_random()

[RFC] enhanced version of net_random()

[Stephen Hemminger]

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 <shemminger@osdl.org>

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;

Re: [RFC] enhanced version of net_random()

[David S. Miller]

On Thu, 12 Aug 2004 10:48:35 -0700
Stephen Hemminger <shemminger@osdl.org> 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? :(

Re: [RFC] enhanced version of net_random()

[Stephen Hemminger]

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;

Re: [RFC] enhanced version of net_random()

[Andi Kleen]

On Fri, 13 Aug 2004 11:51:40 -0700
Stephen Hemminger <shemminger@osdl.org> 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

Re: [RFC] enhanced version of net_random()

[David S. Miller]

On Fri, 13 Aug 2004 21:28:57 +0200
Andi Kleen <ak@suse.de> wrote:

> On Fri, 13 Aug 2004 11:51:40 -0700
> Stephen Hemminger <shemminger@osdl.org> 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.

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.

Re: [RFC] enhanced version of net_random()

[Ben Greear]

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 <greearb@candelatech.com>
Candela Technologies Inc  http://www.candelatech.com

Re: [RFC] enhanced version of net_random()

[Jean-Luc Cooke]

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:
> 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 <shemminger@osdl.org>
> 
> 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;
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [RFC] enhanced version of net_random()

[David S. Miller]

On Fri, 20 Aug 2004 13:59:52 -0400
Jean-Luc Cooke <jlcooke@certainkey.com> 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.

Re: [RFC] enhanced version of net_random()

[Andreas Dilger]

[-- Attachment #1: Type: text/plain, Size: 810 bytes --]

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/


[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [RFC] enhanced version of net_random()

[Richard B. Johnson]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1186 bytes --]

On Fri, 20 Aug 2004, Andreas Dilger wrote:

> 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

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.


[-- Attachment #2: Type: TEXT/PLAIN, Size: 1530 bytes --]


#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
#
#   File rnd.S            Created 04-FEB-1999        Richard B. Johnson
#
#   Simple random number generator. Based upon Alan R. Miller's
#   algorithm. Professor of Metallurgy, University of New Mexico
#   Institute of Mining and Technology, circa 1980. Published
#   In the 8080/Z-80 Assembly Language manual he wrote.
#
#   unsigned size_t rnd((size_t *) seed);
#
#   The seed can be initialized with time(&seed); on each boot.
#

MAGIC  = 0x72b6078b 
INTPTR = 0x08
DIVISR = 0x0c
.section	.text
.global		rnd
.type		rnd,@function
.align	0x04
rnd:	pushl	%ebx
	movl	INTPTR(%esp), %ebx
	movl	(%ebx), %eax
	rorl	$3, %eax
	addl	$MAGIC, %eax
	movl	%eax, (%ebx)
	popl	%ebx
        ret

#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
#
#	This returns a random number between 0 and one less than the
#	input divisor, i.e. n mod rand(x).
#
#	size_t modrnd((size_t *) seed, size_t divisor);
#
.type	modrnd,@function
.global	modrnd
.align	0x04

modrnd:	pushl	%ebx
	movl	INTPTR(%esp), %ebx
	movl	(%ebx), %eax
	rorl	$3, %eax
	addl	$MAGIC, %eax
	movl	%eax, (%ebx)
	xorl	%edx, %edx
	divl	DIVISR(%esp)
	movl	%edx, %eax
	popl	%ebx
        ret
.end
#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Re: [RFC] enhanced version of net_random()

[David S. Miller]

On Fri, 20 Aug 2004 15:22:09 -0400 (EDT)
"Richard B. Johnson" <root@chaos.analogic.com> 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.

Re: [RFC] enhanced version of net_random()

[Jean-Luc Cooke]

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" <root@chaos.analogic.com> 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.

Re: [RFC] enhanced version of net_random()

[Andi Kleen]

On Fri, 20 Aug 2004 12:48:23 -0700
"David S. Miller" <davem@redhat.com> wrote:

> > 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

Re: [RFC] enhanced version of net_random()

[Stephen Hemminger]

> 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

Re: [RFC] enhanced version of net_random()

[Richard B. Johnson]

On Mon, 23 Aug 2004, Stephen Hemminger 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...
> >
> > 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.

Re: [RFC] enhanced version of net_random()

[Lee Revell]

On Fri, 2004-08-20 at 14:59, Andreas Dilger wrote:
> 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.

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 

Re: [RFC] enhanced version of net_random()

[Alan Cox]

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.