rand.go

     1  // Copyright 2023 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Random number generation
     6  
     7  package runtime
     8  
     9  import (
    10  	"internal/chacha8rand"
    11  	"internal/goarch"
    12  	"runtime/internal/math"
    13  	"unsafe"
    14  	_ "unsafe" // for go:linkname
    15  )
    16  
    17  // OS-specific startup can set startupRand if the OS passes
    18  // random data to the process at startup time.
    19  // For example Linux passes 16 bytes in the auxv vector.
    20  var startupRand []byte
    21  
    22  // globalRand holds the global random state.
    23  // It is only used at startup and for creating new m's.
    24  // Otherwise the per-m random state should be used
    25  // by calling goodrand.
    26  var globalRand struct {
    27  	lock  mutex
    28  	seed  [32]byte
    29  	state chacha8rand.State
    30  	init  bool
    31  }
    32  
    33  var readRandomFailed bool
    34  
    35  // randinit initializes the global random state.
    36  // It must be called before any use of grand.
    37  func randinit() {
    38  	lock(&globalRand.lock)
    39  	if globalRand.init {
    40  		fatal("randinit twice")
    41  	}
    42  
    43  	seed := &globalRand.seed
    44  	if startupRand != nil {
    45  		for i, c := range startupRand {
    46  			seed[i%len(seed)] ^= c
    47  		}
    48  		clear(startupRand)
    49  		startupRand = nil
    50  	} else {
    51  		if readRandom(seed[:]) != len(seed) {
    52  			// readRandom should never fail, but if it does we'd rather
    53  			// not make Go binaries completely unusable, so make up
    54  			// some random data based on the current time.
    55  			readRandomFailed = true
    56  			readTimeRandom(seed[:])
    57  		}
    58  	}
    59  	globalRand.state.Init(*seed)
    60  	clear(seed[:])
    61  	globalRand.init = true
    62  	unlock(&globalRand.lock)
    63  }
    64  
    65  // readTimeRandom stretches any entropy in the current time
    66  // into entropy the length of r and XORs it into r.
    67  // This is a fallback for when readRandom does not read
    68  // the full requested amount.
    69  // Whatever entropy r already contained is preserved.
    70  func readTimeRandom(r []byte) {
    71  	// Inspired by wyrand.
    72  	// An earlier version of this code used getg().m.procid as well,
    73  	// but note that this is called so early in startup that procid
    74  	// is not initialized yet.
    75  	v := uint64(nanotime())
    76  	for len(r) > 0 {
    77  		v ^= 0xa0761d6478bd642f
    78  		v *= 0xe7037ed1a0b428db
    79  		size := 8
    80  		if len(r) < 8 {
    81  			size = len(r)
    82  		}
    83  		for i := 0; i < size; i++ {
    84  			r[i] ^= byte(v >> (8 * i))
    85  		}
    86  		r = r[size:]
    87  		v = v>>32 | v<<32
    88  	}
    89  }
    90  
    91  // bootstrapRand returns a random uint64 from the global random generator.
    92  func bootstrapRand() uint64 {
    93  	lock(&globalRand.lock)
    94  	if !globalRand.init {
    95  		fatal("randinit missed")
    96  	}
    97  	for {
    98  		if x, ok := globalRand.state.Next(); ok {
    99  			unlock(&globalRand.lock)
   100  			return x
   101  		}
   102  		globalRand.state.Refill()
   103  	}
   104  }
   105  
   106  // bootstrapRandReseed reseeds the bootstrap random number generator,
   107  // clearing from memory any trace of previously returned random numbers.
   108  func bootstrapRandReseed() {
   109  	lock(&globalRand.lock)
   110  	if !globalRand.init {
   111  		fatal("randinit missed")
   112  	}
   113  	globalRand.state.Reseed()
   114  	unlock(&globalRand.lock)
   115  }
   116  
   117  // rand32 is uint32(rand()), called from compiler-generated code.
   118  //go:nosplit
   119  func rand32() uint32 {
   120  	return uint32(rand())
   121  }
   122  
   123  // rand returns a random uint64 from the per-m chacha8 state.
   124  // Do not change signature: used via linkname from other packages.
   125  //go:nosplit
   126  //go:linkname rand
   127  func rand() uint64 {
   128  	// Note: We avoid acquirem here so that in the fast path
   129  	// there is just a getg, an inlined c.Next, and a return.
   130  	// The performance difference on a 16-core AMD is
   131  	// 3.7ns/call this way versus 4.3ns/call with acquirem (+16%).
   132  	mp := getg().m
   133  	c := &mp.chacha8
   134  	for {
   135  		// Note: c.Next is marked nosplit,
   136  		// so we don't need to use mp.locks
   137  		// on the fast path, which is that the
   138  		// first attempt succeeds.
   139  		x, ok := c.Next()
   140  		if ok {
   141  			return x
   142  		}
   143  		mp.locks++ // hold m even though c.Refill may do stack split checks
   144  		c.Refill()
   145  		mp.locks--
   146  	}
   147  }
   148  
   149  // mrandinit initializes the random state of an m.
   150  func mrandinit(mp *m) {
   151  	var seed [4]uint64
   152  	for i := range seed {
   153  		seed[i] = bootstrapRand()
   154  	}
   155  	bootstrapRandReseed() // erase key we just extracted
   156  	mp.chacha8.Init64(seed)
   157  	mp.cheaprand = rand()
   158  }
   159  
   160  // randn is like rand() % n but faster.
   161  // Do not change signature: used via linkname from other packages.
   162  //go:nosplit
   163  //go:linkname randn
   164  func randn(n uint32) uint32 {
   165  	// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
   166  	return uint32((uint64(uint32(rand())) * uint64(n)) >> 32)
   167  }
   168  
   169  // cheaprand is a non-cryptographic-quality 32-bit random generator
   170  // suitable for calling at very high frequency (such as during scheduling decisions)
   171  // and at sensitive moments in the runtime (such as during stack unwinding).
   172  // it is "cheap" in the sense of both expense and quality.
   173  //
   174  // cheaprand must not be exported to other packages:
   175  // the rule is that other packages using runtime-provided
   176  // randomness must always use rand.
   177  //go:nosplit
   178  func cheaprand() uint32 {
   179  	mp := getg().m
   180  	// Implement wyrand: https://github.com/wangyi-fudan/wyhash
   181  	// Only the platform that math.Mul64 can be lowered
   182  	// by the compiler should be in this list.
   183  	if goarch.IsAmd64|goarch.IsArm64|goarch.IsPpc64|
   184  		goarch.IsPpc64le|goarch.IsMips64|goarch.IsMips64le|
   185  		goarch.IsS390x|goarch.IsRiscv64|goarch.IsLoong64 == 1 {
   186  		mp.cheaprand += 0xa0761d6478bd642f
   187  		hi, lo := math.Mul64(mp.cheaprand, mp.cheaprand^0xe7037ed1a0b428db)
   188  		return uint32(hi ^ lo)
   189  	}
   190  
   191  	// Implement xorshift64+: 2 32-bit xorshift sequences added together.
   192  	// Shift triplet [17,7,16] was calculated as indicated in Marsaglia's
   193  	// Xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf
   194  	// This generator passes the SmallCrush suite, part of TestU01 framework:
   195  	// http://simul.iro.umontreal.ca/testu01/tu01.html
   196  	t := (*[2]uint32)(unsafe.Pointer(&mp.cheaprand))
   197  	s1, s0 := t[0], t[1]
   198  	s1 ^= s1 << 17
   199  	s1 = s1 ^ s0 ^ s1>>7 ^ s0>>16
   200  	t[0], t[1] = s0, s1
   201  	return s0 + s1
   202  }
   203  
   204  // cheaprand64 is a non-cryptographic-quality 63-bit random generator
   205  // suitable for calling at very high frequency (such as during sampling decisions).
   206  // it is "cheap" in the sense of both expense and quality.
   207  //
   208  // cheaprand64 must not be exported to other packages:
   209  // the rule is that other packages using runtime-provided
   210  // randomness must always use rand.
   211  //go:nosplit
   212  func cheaprand64() int64 {
   213  	return int64(cheaprand())<<31 ^ int64(cheaprand())
   214  }
   215  
   216  // cheaprandn is like cheaprand() % n but faster.
   217  //
   218  // cheaprandn must not be exported to other packages:
   219  // the rule is that other packages using runtime-provided
   220  // randomness must always use randn.
   221  //go:nosplit
   222  func cheaprandn(n uint32) uint32 {
   223  	// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
   224  	return uint32((uint64(cheaprand()) * uint64(n)) >> 32)
   225  }
   226  
   227  // Too much legacy code has go:linkname references
   228  // to runtime.fastrand and friends, so keep these around for now.
   229  // Code should migrate to math/rand/v2.Uint64,
   230  // which is just as fast, but that's only available in Go 1.22+.
   231  // It would be reasonable to remove these in Go 1.24.
   232  // Do not call these from package runtime.
   233  
   234  //go:linkname legacy_fastrand runtime.fastrand
   235  func legacy_fastrand() uint32 {
   236  	return uint32(rand())
   237  }
   238  
   239  //go:linkname legacy_fastrandn runtime.fastrandn
   240  func legacy_fastrandn(n uint32) uint32 {
   241  	return randn(n)
   242  }
   243  
   244  //go:linkname legacy_fastrand64 runtime.fastrand64
   245  func legacy_fastrand64() uint64 {
   246  	return rand()
   247  }
   248
View as plain text