svn commit: r364219 - in head: share/man/man9 sys/conf sys/contrib/pcg-c/include sys/kern sys/libkern sys/sys
Mateusz Guzik
mjguzik at gmail.com
Thu Aug 13 21:06:44 UTC 2020
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 at 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 at 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 at 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>
More information about the svn-src-all
mailing list