Add prng(9) API

Add prng(9) as a replacement for random(9) in the kernel.

There are two major differences from random(9) and random(3):

- General prng(9) APIs (prng32(9), etc) do not guarantee an
  implementation or particular sequence; they should not be used for
  repeatable simulations.

- However, specific named API families are also exposed (for now: PCG),
  and those are expected to be repeatable (when so-guaranteed by the named
  algorithm).

Some minor differences from random(3) and earlier random(9):

- PRNG state for the general prng(9) APIs is per-CPU; this eliminates
  contention on PRNG state in SMP workloads.  Each PCPU generator in an
  SMP system produces a unique sequence.

- Better statistical properties than the Park-Miller ("minstd") PRNG
  (longer period, uniform distribution in all bits, passes
  BigCrush/PractRand analysis).

- Faster than Park-Miller ("minstd") PRNG -- no division is required to
  step PCG-family PRNGs.

For now, random(9) becomes a thin shim around prng32().  Eventually I
would like to mechanically switch consumers over to the explicit API.

Reviewed by:	kib, markj (previous version both)
Discussed with:	markm
Differential Revision:	https://reviews.freebsd.org/D25916

1 files changed, 3 insertions, 32 deletions

diff --git a/sys/libkern/random.c b/sys/libkern/random.c
index e5e9de6108e1..23a8887fa49b 100644
--- a/sys/libkern/random.c
+++ b/sys/libkern/random.c
@@ -36,43 +36,14 @@ __FBSDID("$FreeBSD$");
 
 #include <sys/types.h>
 #include <sys/libkern.h>
+#include <sys/prng.h>
 #include <sys/systm.h>
 
-static u_long randseed = 937186357; /* after srandom(1), NSHUFF counted */
-
 /*
- * Pseudo-random number generator for perturbing the profiling clock,
- * and whatever else we might use it for.  The result is uniform on
- * [0, 2^31 - 1].
+ * Pseudo-random number generator.  The result is uniform in [0, 2^31 - 1].
  */
 u_long
 random(void)
 {
-	static bool warned = false;
-
-	long x, hi, lo, t;
-
-	/* Warn only once, or it gets very spammy. */
-	if (!warned) {
-		gone_in(13,
-		    "random(9) is the obsolete Park-Miller LCG from 1988");
-		warned = true;
-	}
-
-	/*
-	 * Compute x[n + 1] = (7^5 * x[n]) mod (2^31 - 1).
-	 * From "Random number generators: good ones are hard to find",
-	 * Park and Miller, Communications of the ACM, vol. 31, no. 10,
-	 * October 1988, p. 1195.
-	 */
-	/* Can't be initialized with 0, so use another value. */
-	if ((x = randseed) == 0)
-		x = 123459876;
-	hi = x / 127773;
-	lo = x % 127773;
-	t = 16807 * lo - 2836 * hi;
-	if (t < 0)
-		t += 0x7fffffff;
-	randseed = t;
-	return (t);
+	return (prng32());
 }