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