Index: share/man/man9/Makefile =================================================================== --- share/man/man9/Makefile +++ share/man/man9/Makefile @@ -272,6 +272,7 @@ printf.9 \ prison_check.9 \ priv.9 \ + prng.9 \ proc_rwmem.9 \ pseudofs.9 \ psignal.9 \ @@ -1746,6 +1747,10 @@ printf.9 uprintf.9 MLINKS+=priv.9 priv_check.9 \ priv.9 priv_check_cred.9 +MLINKS+=prng.9 prng32.9 \ + prng.9 prng32_bounded.9 \ + prng.9 prng64.9 \ + prng.9 prng64_bounded.9 MLINKS+=proc_rwmem.9 proc_readmem.9 \ proc_rwmem.9 proc_writemem.9 MLINKS+=psignal.9 gsignal.9 \ Index: share/man/man9/prng.9 =================================================================== --- /dev/null +++ share/man/man9/prng.9 @@ -0,0 +1,99 @@ +.\"- +.\" Copyright 2020 Conrad Meyer . All rights reserved. +.\" +.\" 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 AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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. +.\" +.\" $FreeBSD$ +.\" +.Dd August 5, 2020 +.Dt PRNG 9 +.Os +.Sh NAME +.Nm prng +.Nd "Kernel pseudo-random number generators" +.Sh SYNOPSIS +.In sys/prng.h +.Ft uint32_t +.Fn prng32 void +.Ft uint32_t +.Fn prng32_bounded "uint32_t bound" +.Ft uint64_t +.Fn prng64 void +.Ft uint64_t +.Fn prng64_bounded "uint64_t bound" +.Sh DESCRIPTION +.Ss GENERIC PRNG ROUTINES +.Nm +is a family of fast, +.Em non-cryptographic +pseudo-random number generators. +Unlike +.Xr random 9 , +.Fn prng32 , +.Fn prng32_bounded , +.Fn prng64 , +and +.Fn prng64_bounded +avoid shared global state, removing unnecessary contention on SMP +systems. +The routines are not explicitly tied to any specific implementation, and +may produce different specific sequences on different hosts, reboots, or +versions of +.Fx . +Different CPUs in SMP systems are guaranteed to produce different sequences of +integers. +.Pp +For +.Em cryptographically secure +random numbers generated by the +.Xr random 4 +kernel cryptographically secure random number generator subsystem, see +.Xr arc4random 9 . +.Pp +.Bl -tag -width indent +.It Fn prng32 +Generate a 32-bit integer uniformly distributed in [0, 2^32-1]. +.It Fn prng32_bounded bound +Generate an integer uniformly in the range [0, bound-1]. +.It Fn prng64 +Generate a 64-bit integer uniformly distributed in [0, 2^64-1]. +.It Fn prng64_bounded bound +Generate an integer uniformly in the range [0, bound-1]. +.El +.Pp +These routines are not reentrant; they are not safe to use in interrupt +handlers ("interrupt filters" in +.Xr bus_setup_intr 9 +terminology). +They are safe to use in all other kernel contexts, including interrupt threads +("ithreads"). +.Ss REPRODUCIBLE PRNG APIS +In addition to these per-CPU helpers, the +.In sys/prng.h +header also exposes the entire API of the PCG family of PRNGs as inline +functions. +The PCG-C API is described in full at +.Lk https://www.pcg-random.org/using-pcg-c.html . +.Sh HISTORY +.Nm +was introduced in +.Fx 13 . Index: sys/conf/files =================================================================== --- sys/conf/files +++ sys/conf/files @@ -3840,6 +3840,7 @@ kern/subr_pidctrl.c standard kern/subr_power.c standard kern/subr_prf.c standard +kern/subr_prng.c standard kern/subr_prof.c standard kern/subr_rangeset.c standard kern/subr_rman.c standard Index: sys/contrib/pcg-c/include/pcg_variants.h =================================================================== --- sys/contrib/pcg-c/include/pcg_variants.h +++ sys/contrib/pcg-c/include/pcg_variants.h @@ -36,22 +36,16 @@ #ifndef PCG_VARIANTS_H_INCLUDED #define PCG_VARIANTS_H_INCLUDED 1 -#include - -#if __SIZEOF_INT128__ +#if defined(__SIZEOF_INT128__) && __SIZEOF_INT128__ typedef __uint128_t pcg128_t; #define PCG_128BIT_CONSTANT(high,low) \ ((((pcg128_t)high) << 64) + low) #define PCG_HAS_128BIT_OPS 1 +#else + #define PCG_HAS_128BIT_OPS 0 #endif -#if __GNUC_GNU_INLINE__ && !defined(__cplusplus) - #error Nonstandard GNU inlining semantics. Compile with -std=c99 or better. - /* We could instead use macros PCG_INLINE and PCG_EXTERN_INLINE - but better to just reject ancient C code. */ -#endif - -#if __cplusplus +#ifdef __cplusplus extern "C" { #endif @@ -65,8 +59,8 @@ * recognizing idiomatic rotate code, so for clang we actually provide * assembler directives (enabled with PCG_USE_INLINE_ASM). Boo, hiss. */ -#if PCG_USE_INLINE_ASM && __clang__ && (__x86_64__ || __i386__) - asm ("rorb %%cl, %0" : "=r" (value) : "0" (value), "c" (rot)); +#if PCG_USE_INLINE_ASM && defined(__clang__) && (defined(__x86_64__) || defined(__i386__)) + __asm__ ("rorb %%cl, %0" : "=r" (value) : "0" (value), "c" (rot)); return value; #else return (value >> rot) | (value << ((- rot) & 7)); @@ -75,8 +69,8 @@ inline uint16_t pcg_rotr_16(uint16_t value, unsigned int rot) { -#if PCG_USE_INLINE_ASM && __clang__ && (__x86_64__ || __i386__) - asm ("rorw %%cl, %0" : "=r" (value) : "0" (value), "c" (rot)); +#if PCG_USE_INLINE_ASM && defined(__clang__) && (defined(__x86_64__) || defined(__i386__)) + __asm__ ("rorw %%cl, %0" : "=r" (value) : "0" (value), "c" (rot)); return value; #else return (value >> rot) | (value << ((- rot) & 15)); @@ -85,8 +79,8 @@ inline uint32_t pcg_rotr_32(uint32_t value, unsigned int rot) { -#if PCG_USE_INLINE_ASM && __clang__ && (__x86_64__ || __i386__) - asm ("rorl %%cl, %0" : "=r" (value) : "0" (value), "c" (rot)); +#if PCG_USE_INLINE_ASM && defined(__clang__) && (defined(__x86_64__) || defined(__i386__)) + __asm__ ("rorl %%cl, %0" : "=r" (value) : "0" (value), "c" (rot)); return value; #else return (value >> rot) | (value << ((- rot) & 31)); @@ -95,10 +89,10 @@ inline uint64_t pcg_rotr_64(uint64_t value, unsigned int rot) { -#if 0 && PCG_USE_INLINE_ASM && __clang__ && __x86_64__ +#if 0 && PCG_USE_INLINE_ASM && defined(__clang__) && (defined(__x86_64__) || defined(__i386__)) /* For whatever reason, clang actually *does* generate rotq by itself, so we don't need this code. */ - asm ("rorq %%cl, %0" : "=r" (value) : "0" (value), "c" (rot)); + __asm__ ("rorq %%cl, %0" : "=r" (value) : "0" (value), "c" (rot)); return value; #else return (value >> rot) | (value << ((- rot) & 63)); @@ -2491,18 +2485,6 @@ #define pcg128i_advance_r pcg_setseq_128_advance_r #endif -extern uint32_t pcg32_random(void); -extern uint32_t pcg32_boundedrand(uint32_t bound); -extern void pcg32_srandom(uint64_t seed, uint64_t seq); -extern void pcg32_advance(uint64_t delta); - -#if PCG_HAS_128BIT_OPS -extern uint64_t pcg64_random(void); -extern uint64_t pcg64_boundedrand(uint64_t bound); -extern void pcg64_srandom(pcg128_t seed, pcg128_t seq); -extern void pcg64_advance(pcg128_t delta); -#endif - /* * Static initialization constants (if you can't call srandom for some * bizarre reason). @@ -2536,7 +2518,7 @@ #define PCG128I_INITIALIZER PCG_STATE_SETSEQ_128_INITIALIZER #endif -#if __cplusplus +#ifdef __cplusplus } #endif Index: sys/kern/subr_prng.c =================================================================== --- /dev/null +++ sys/kern/subr_prng.c @@ -0,0 +1,131 @@ +/*- + * SPDX-License-Identifier: BSD-2-Clause-FreeBSD + * + * Copyright 2020 Conrad Meyer . All rights reserved. + * + * 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 AND CONTRIBUTORS ``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 OR CONTRIBUTORS 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. + */ + +#include +__FBSDID("$FreeBSD$"); + +#include +#include +#include +#include +#include +#include + +#if !PCG_HAS_128BIT_OPS +/* On 32-bit platforms, gang together two 32-bit generators. */ +typedef struct { + pcg32u_random_t states[2]; +} pcg64u_random_t; + +static inline void +pcg64u_srandom_r(pcg64u_random_t *state64, uint64_t seed) +{ + pcg32u_srandom_r(&state64->states[0], seed); + pcg32u_srandom_r(&state64->states[1], seed); +} + +static inline uint64_t +pcg64u_random_r(pcg64u_random_t *state64) +{ + return ((((uint64_t)pcg32u_random_r(&state64->states[0])) << 32) | + pcg32u_random_r(&state64->states[1])); +} + +static inline uint64_t +pcg64u_boundedrand_r(pcg64u_random_t *state64, uint64_t bound) +{ + uint64_t threshold = -bound % bound; + for (;;) { + uint64_t r = pcg64u_random_r(state64); + if (r >= threshold) + return (r % bound); + } +} +#endif + +DPCPU_DEFINE_STATIC(pcg32u_random_t, pcpu_prng32_state); +DPCPU_DEFINE_STATIC(pcg64u_random_t, pcpu_prng64_state); + +static void +prng_init(void *dummy __unused) +{ + pcg32u_random_t *state; + pcg64u_random_t *state64; + int i; + + CPU_FOREACH(i) { + state = DPCPU_ID_PTR(i, pcpu_prng32_state); + pcg32u_srandom_r(state, 1); + state64 = DPCPU_ID_PTR(i, pcpu_prng64_state); + pcg64u_srandom_r(state64, 1); + } +} +SYSINIT(prng_init, SI_SUB_CPU, SI_ORDER_ANY, prng_init, NULL); + +uint32_t +prng32(void) +{ + uint32_t r; + + critical_enter(); + r = pcg32u_random_r(DPCPU_PTR(pcpu_prng32_state)); + critical_exit(); + return (r); +} + +uint32_t +prng32_bounded(uint32_t bound) +{ + uint32_t r; + + critical_enter(); + r = pcg32u_boundedrand_r(DPCPU_PTR(pcpu_prng32_state), bound); + critical_exit(); + return (r); +} + +uint64_t +prng64(void) +{ + uint64_t r; + + critical_enter(); + r = pcg64u_random_r(DPCPU_PTR(pcpu_prng64_state)); + critical_exit(); + return (r); +} + +uint64_t +prng64_bounded(uint64_t bound) +{ + uint64_t r; + + critical_enter(); + r = pcg64u_boundedrand_r(DPCPU_PTR(pcpu_prng64_state), bound); + critical_exit(); + return (r); +} Index: sys/libkern/random.c =================================================================== --- sys/libkern/random.c +++ sys/libkern/random.c @@ -36,43 +36,14 @@ #include #include +#include #include -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()); } Index: sys/sys/prng.h =================================================================== --- /dev/null +++ sys/sys/prng.h @@ -0,0 +1,20 @@ +/*- + * This file is in the public domain. + * + * $FreeBSD$ + */ + +#ifndef _SYS_PRNG_H_ +#define _SYS_PRNG_H_ + +#define PCG_USE_INLINE_ASM 1 +#include + +#ifdef _KERNEL +__uint32_t prng32(void); +__uint32_t prng32_bounded(__uint32_t bound); +__uint64_t prng64(void); +__uint64_t prng64_bounded(__uint64_t bound); +#endif + +#endif