Date: Thu, 13 Aug 2020 23:06:41 +0200 From: Mateusz Guzik <mjguzik@gmail.com> To: Conrad Meyer <cem@freebsd.org> Cc: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: Re: svn commit: r364219 - in head: share/man/man9 sys/conf sys/contrib/pcg-c/include sys/kern sys/libkern sys/sys Message-ID: <CAGudoHFSO=FY9EH7mm=d4x3nEePr__ReOqExXNUHGD9A_dzzUg@mail.gmail.com> In-Reply-To: <202008132048.07DKmEO9069055@repo.freebsd.org> References: <202008132048.07DKmEO9069055@repo.freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
I have trouble deciphering. Is this callable from interrupt context? If not, the code should assert it's not executing in one. If yes, it should probably just sched_pin. On 8/13/20, Conrad Meyer <cem@freebsd.org> wrote: > Author: cem > Date: Thu Aug 13 20:48:14 2020 > New Revision: 364219 > URL: https://svnweb.freebsd.org/changeset/base/364219 > > Log: > 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 > > Added: > head/share/man/man9/prng.9 (contents, props changed) > head/sys/kern/subr_prng.c (contents, props changed) > head/sys/sys/prng.h (contents, props changed) > Modified: > head/share/man/man9/Makefile > head/sys/conf/files > head/sys/contrib/pcg-c/include/pcg_variants.h > head/sys/libkern/random.c > > Modified: head/share/man/man9/Makefile > ============================================================================== > --- head/share/man/man9/Makefile Thu Aug 13 20:28:35 2020 (r364218) > +++ head/share/man/man9/Makefile Thu Aug 13 20:48:14 2020 (r364219) > @@ -272,6 +272,7 @@ MAN= accept_filter.9 \ > printf.9 \ > prison_check.9 \ > priv.9 \ > + prng.9 \ > proc_rwmem.9 \ > pseudofs.9 \ > psignal.9 \ > @@ -1745,6 +1746,10 @@ MLINKS+=printf.9 log.9 \ > 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 \ > > Added: head/share/man/man9/prng.9 > ============================================================================== > --- /dev/null 00:00:00 1970 (empty, because file is newly added) > +++ head/share/man/man9/prng.9 Thu Aug 13 20:48:14 2020 (r364219) > @@ -0,0 +1,99 @@ > +.\"- > +.\" Copyright 2020 Conrad Meyer <cem@FreeBSD.org>. 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 . > > Modified: head/sys/conf/files > ============================================================================== > --- head/sys/conf/files Thu Aug 13 20:28:35 2020 (r364218) > +++ head/sys/conf/files Thu Aug 13 20:48:14 2020 (r364219) > @@ -3834,6 +3834,7 @@ kern/subr_pctrie.c standard > 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 > > Modified: head/sys/contrib/pcg-c/include/pcg_variants.h > ============================================================================== > --- head/sys/contrib/pcg-c/include/pcg_variants.h Thu Aug 13 20:28:35 > 2020 (r364218) > +++ head/sys/contrib/pcg-c/include/pcg_variants.h Thu Aug 13 20:48:14 > 2020 (r364219) > @@ -36,22 +36,16 @@ > #ifndef PCG_VARIANTS_H_INCLUDED > #define PCG_VARIANTS_H_INCLUDED 1 > > -#include <inttypes.h> > - > -#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 @@ inline uint8_t pcg_rotr_8(uint8_t value, unsigned int > * 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 uint8_t pcg_rotr_8(uint8_t value, unsigned int > > 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 uint16_t pcg_rotr_16(uint16_t value, unsigned i > > 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 uint32_t pcg_rotr_32(uint32_t value, unsigned i > > 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 @@ typedef struct pcg_state_setseq_128 > pcg128i_random_t > #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 @@ extern void pcg64_advance(pcg128_t delta); > #define PCG128I_INITIALIZER PCG_STATE_SETSEQ_128_INITIALIZER > #endif > > -#if __cplusplus > +#ifdef __cplusplus > } > #endif > > > Added: head/sys/kern/subr_prng.c > ============================================================================== > --- /dev/null 00:00:00 1970 (empty, because file is newly added) > +++ head/sys/kern/subr_prng.c Thu Aug 13 20:48:14 2020 (r364219) > @@ -0,0 +1,131 @@ > +/*- > + * SPDX-License-Identifier: BSD-2-Clause-FreeBSD > + * > + * Copyright 2020 Conrad Meyer <cem@FreeBSD.org>. 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 <sys/cdefs.h> > +__FBSDID("$FreeBSD$"); > + > +#include <sys/param.h> > +#include <sys/kernel.h> > +#include <sys/pcpu.h> > +#include <sys/prng.h> > +#include <sys/smp.h> > +#include <sys/systm.h> > + > +#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); > +} > > Modified: head/sys/libkern/random.c > ============================================================================== > --- head/sys/libkern/random.c Thu Aug 13 20:28:35 2020 (r364218) > +++ head/sys/libkern/random.c Thu Aug 13 20:48:14 2020 (r364219) > @@ -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()); > } > > Added: head/sys/sys/prng.h > ============================================================================== > --- /dev/null 00:00:00 1970 (empty, because file is newly added) > +++ head/sys/sys/prng.h Thu Aug 13 20:48:14 2020 (r364219) > @@ -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 <contrib/pcg-c/include/pcg_variants.h> > + > +#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 > -- Mateusz Guzik <mjguzik gmail.com>
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAGudoHFSO=FY9EH7mm=d4x3nEePr__ReOqExXNUHGD9A_dzzUg>