blob: 10cd116fadeaaf7188f8d50e80e40f8528482977 [file] [log] [blame]
// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Random number generation
package runtime
import (
"internal/chacha8rand"
"internal/goarch"
"runtime/internal/math"
"unsafe"
_ "unsafe" // for go:linkname
)
// OS-specific startup can set startupRand if the OS passes
// random data to the process at startup time.
// For example Linux passes 16 bytes in the auxv vector.
var startupRand []byte
// globalRand holds the global random state.
// It is only used at startup and for creating new m's.
// Otherwise the per-m random state should be used
// by calling goodrand.
var globalRand struct {
lock mutex
seed [32]byte
state chacha8rand.State
init bool
}
var readRandomFailed bool
// randinit initializes the global random state.
// It must be called before any use of grand.
func randinit() {
lock(&globalRand.lock)
if globalRand.init {
fatal("randinit twice")
}
seed := &globalRand.seed
if startupRand != nil {
for i, c := range startupRand {
seed[i%len(seed)] ^= c
}
clear(startupRand)
startupRand = nil
} else {
if readRandom(seed[:]) != len(seed) {
// readRandom should never fail, but if it does we'd rather
// not make Go binaries completely unusable, so make up
// some random data based on the current time.
readRandomFailed = true
readTimeRandom(seed[:])
}
}
globalRand.state.Init(*seed)
clear(seed[:])
globalRand.init = true
unlock(&globalRand.lock)
}
// readTimeRandom stretches any entropy in the current time
// into entropy the length of r and XORs it into r.
// This is a fallback for when readRandom does not read
// the full requested amount.
// Whatever entropy r already contained is preserved.
func readTimeRandom(r []byte) {
// Inspired by wyrand.
// An earlier version of this code used getg().m.procid as well,
// but note that this is called so early in startup that procid
// is not initialized yet.
v := uint64(nanotime())
for len(r) > 0 {
v ^= 0xa0761d6478bd642f
v *= 0xe7037ed1a0b428db
size := 8
if len(r) < 8 {
size = len(r)
}
for i := 0; i < size; i++ {
r[i] ^= byte(v >> (8 * i))
}
r = r[size:]
v = v>>32 | v<<32
}
}
// bootstrapRand returns a random uint64 from the global random generator.
func bootstrapRand() uint64 {
lock(&globalRand.lock)
if !globalRand.init {
fatal("randinit missed")
}
for {
if x, ok := globalRand.state.Next(); ok {
unlock(&globalRand.lock)
return x
}
globalRand.state.Refill()
}
}
// bootstrapRandReseed reseeds the bootstrap random number generator,
// clearing from memory any trace of previously returned random numbers.
func bootstrapRandReseed() {
lock(&globalRand.lock)
if !globalRand.init {
fatal("randinit missed")
}
globalRand.state.Reseed()
unlock(&globalRand.lock)
}
// rand32 is uint32(rand()), called from compiler-generated code.
//go:nosplit
func rand32() uint32 {
return uint32(rand())
}
// rand returns a random uint64 from the per-m chacha8 state.
// Do not change signature: used via linkname from other packages.
//go:nosplit
//go:linkname rand
func rand() uint64 {
// Note: We avoid acquirem here so that in the fast path
// there is just a getg, an inlined c.Next, and a return.
// The performance difference on a 16-core AMD is
// 3.7ns/call this way versus 4.3ns/call with acquirem (+16%).
mp := getg().m
c := &mp.chacha8
for {
// Note: c.Next is marked nosplit,
// so we don't need to use mp.locks
// on the fast path, which is that the
// first attempt succeeds.
x, ok := c.Next()
if ok {
return x
}
mp.locks++ // hold m even though c.Refill may do stack split checks
c.Refill()
mp.locks--
}
}
// mrandinit initializes the random state of an m.
func mrandinit(mp *m) {
var seed [4]uint64
for i := range seed {
seed[i] = bootstrapRand()
}
bootstrapRandReseed() // erase key we just extracted
mp.chacha8.Init64(seed)
mp.cheaprand = rand()
}
// randn is like rand() % n but faster.
// Do not change signature: used via linkname from other packages.
//go:nosplit
//go:linkname randn
func randn(n uint32) uint32 {
// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
return uint32((uint64(uint32(rand())) * uint64(n)) >> 32)
}
// cheaprand is a non-cryptographic-quality 32-bit random generator
// suitable for calling at very high frequency (such as during scheduling decisions)
// and at sensitive moments in the runtime (such as during stack unwinding).
// it is "cheap" in the sense of both expense and quality.
//
// cheaprand must not be exported to other packages:
// the rule is that other packages using runtime-provided
// randomness must always use rand.
//go:nosplit
func cheaprand() uint32 {
mp := getg().m
// Implement wyrand: https://github.com/wangyi-fudan/wyhash
// Only the platform that math.Mul64 can be lowered
// by the compiler should be in this list.
if goarch.IsAmd64|goarch.IsArm64|goarch.IsPpc64|
goarch.IsPpc64le|goarch.IsMips64|goarch.IsMips64le|
goarch.IsS390x|goarch.IsRiscv64|goarch.IsLoong64 == 1 {
mp.cheaprand += 0xa0761d6478bd642f
hi, lo := math.Mul64(mp.cheaprand, mp.cheaprand^0xe7037ed1a0b428db)
return uint32(hi ^ lo)
}
// Implement xorshift64+: 2 32-bit xorshift sequences added together.
// Shift triplet [17,7,16] was calculated as indicated in Marsaglia's
// Xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf
// This generator passes the SmallCrush suite, part of TestU01 framework:
// http://simul.iro.umontreal.ca/testu01/tu01.html
t := (*[2]uint32)(unsafe.Pointer(&mp.cheaprand))
s1, s0 := t[0], t[1]
s1 ^= s1 << 17
s1 = s1 ^ s0 ^ s1>>7 ^ s0>>16
t[0], t[1] = s0, s1
return s0 + s1
}
// cheaprand64 is a non-cryptographic-quality 63-bit random generator
// suitable for calling at very high frequency (such as during sampling decisions).
// it is "cheap" in the sense of both expense and quality.
//
// cheaprand64 must not be exported to other packages:
// the rule is that other packages using runtime-provided
// randomness must always use rand.
//go:nosplit
func cheaprand64() int64 {
return int64(cheaprand())<<31 ^ int64(cheaprand())
}
// cheaprandn is like cheaprand() % n but faster.
//
// cheaprandn must not be exported to other packages:
// the rule is that other packages using runtime-provided
// randomness must always use randn.
//go:nosplit
func cheaprandn(n uint32) uint32 {
// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
return uint32((uint64(cheaprand()) * uint64(n)) >> 32)
}
// Too much legacy code has go:linkname references
// to runtime.fastrand and friends, so keep these around for now.
// Code should migrate to math/rand/v2.Uint64,
// which is just as fast, but that's only available in Go 1.22+.
// It would be reasonable to remove these in Go 1.24.
// Do not call these from package runtime.
//go:linkname legacy_fastrand runtime.fastrand
func legacy_fastrand() uint32 {
return uint32(rand())
}
//go:linkname legacy_fastrandn runtime.fastrandn
func legacy_fastrandn(n uint32) uint32 {
return randn(n)
}
//go:linkname legacy_fastrand64 runtime.fastrand64
func legacy_fastrand64() uint64 {
return rand()
}