diff options
Diffstat (limited to 'sys')
| -rw-r--r-- | sys/conf/files | 1 | ||||
| -rw-r--r-- | sys/contrib/pcg-c/include/pcg_variants.h | 44 | ||||
| -rw-r--r-- | sys/kern/subr_prng.c | 131 | ||||
| -rw-r--r-- | sys/libkern/random.c | 35 | ||||
| -rw-r--r-- | sys/sys/prng.h | 20 |
5 files changed, 168 insertions, 63 deletions
diff --git a/sys/conf/files b/sys/conf/files index 04e224437f93..052e8c238f43 100644 --- a/sys/conf/files +++ b/sys/conf/files @@ -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 diff --git a/sys/contrib/pcg-c/include/pcg_variants.h b/sys/contrib/pcg-c/include/pcg_variants.h index 768fb75ae93b..14f8e7aa2cf8 100644 --- a/sys/contrib/pcg-c/include/pcg_variants.h +++ b/sys/contrib/pcg-c/include/pcg_variants.h @@ -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 rot) * 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 rot) 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 int rot) 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 int rot) 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 diff --git a/sys/kern/subr_prng.c b/sys/kern/subr_prng.c new file mode 100644 index 000000000000..124a56e0e4ea --- /dev/null +++ b/sys/kern/subr_prng.c @@ -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); +} 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()); } diff --git a/sys/sys/prng.h b/sys/sys/prng.h new file mode 100644 index 000000000000..a1abe6ad1a11 --- /dev/null +++ b/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 <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 |