Source file src/runtime/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/byteorder" 11 "internal/chacha8rand" 12 "internal/goarch" 13 "math/bits" 14 "unsafe" 15 _ "unsafe" // for go:linkname 16 ) 17 18 // OS-specific startup can set startupRand if the OS passes 19 // random data to the process at startup time. 20 // For example Linux passes 16 bytes in the auxv vector. 21 var startupRand []byte 22 23 // globalRand holds the global random state. 24 // It is only used at startup and for creating new m's. 25 // Otherwise the per-m random state should be used 26 // by calling goodrand. 27 var globalRand struct { 28 lock mutex 29 seed [32]byte 30 state chacha8rand.State 31 init bool 32 } 33 34 var readRandomFailed bool 35 36 // randinit initializes the global random state. 37 // It must be called before any use of grand. 38 func randinit() { 39 lock(&globalRand.lock) 40 if globalRand.init { 41 fatal("randinit twice") 42 } 43 44 seed := &globalRand.seed 45 if len(startupRand) >= 16 && 46 // Check that at least the first two words of startupRand weren't 47 // cleared by any libc initialization. 48 !allZero(startupRand[:8]) && !allZero(startupRand[8:16]) { 49 for i, c := range startupRand { 50 seed[i%len(seed)] ^= c 51 } 52 } else { 53 if readRandom(seed[:]) != len(seed) || allZero(seed[:]) { 54 // readRandom should never fail, but if it does we'd rather 55 // not make Go binaries completely unusable, so make up 56 // some random data based on the current time. 57 readRandomFailed = true 58 readTimeRandom(seed[:]) 59 } 60 } 61 globalRand.state.Init(*seed) 62 clear(seed[:]) 63 64 if startupRand != nil { 65 // Overwrite startupRand instead of clearing it, in case cgo programs 66 // access it after we used it. 67 for len(startupRand) > 0 { 68 buf := make([]byte, 8) 69 for { 70 if x, ok := globalRand.state.Next(); ok { 71 byteorder.BEPutUint64(buf, x) 72 break 73 } 74 globalRand.state.Refill() 75 } 76 n := copy(startupRand, buf) 77 startupRand = startupRand[n:] 78 } 79 startupRand = nil 80 } 81 82 globalRand.init = true 83 unlock(&globalRand.lock) 84 } 85 86 // readTimeRandom stretches any entropy in the current time 87 // into entropy the length of r and XORs it into r. 88 // This is a fallback for when readRandom does not read 89 // the full requested amount. 90 // Whatever entropy r already contained is preserved. 91 func readTimeRandom(r []byte) { 92 // Inspired by wyrand. 93 // An earlier version of this code used getg().m.procid as well, 94 // but note that this is called so early in startup that procid 95 // is not initialized yet. 96 v := uint64(nanotime()) 97 for len(r) > 0 { 98 v ^= 0xa0761d6478bd642f 99 v *= 0xe7037ed1a0b428db 100 size := 8 101 if len(r) < 8 { 102 size = len(r) 103 } 104 for i := 0; i < size; i++ { 105 r[i] ^= byte(v >> (8 * i)) 106 } 107 r = r[size:] 108 v = v>>32 | v<<32 109 } 110 } 111 112 func allZero(b []byte) bool { 113 var acc byte 114 for _, x := range b { 115 acc |= x 116 } 117 return acc == 0 118 } 119 120 // Used in internal/runtime/maps 121 // bootstrapRand returns a random uint64 from the global random generator. 122 // 123 //go:linknamestd bootstrapRand 124 func bootstrapRand() uint64 { 125 lock(&globalRand.lock) 126 if !globalRand.init { 127 fatal("randinit missed") 128 } 129 for { 130 if x, ok := globalRand.state.Next(); ok { 131 unlock(&globalRand.lock) 132 return x 133 } 134 globalRand.state.Refill() 135 } 136 } 137 138 // bootstrapRandReseed reseeds the bootstrap random number generator, 139 // clearing from memory any trace of previously returned random numbers. 140 func bootstrapRandReseed() { 141 lock(&globalRand.lock) 142 if !globalRand.init { 143 fatal("randinit missed") 144 } 145 globalRand.state.Reseed() 146 unlock(&globalRand.lock) 147 } 148 149 // rand32 is uint32(rand()), called from compiler-generated code. 150 // 151 //go:nosplit 152 func rand32() uint32 { 153 return uint32(rand()) 154 } 155 156 // rand returns a random uint64 from the per-m chacha8 state. 157 // This is called from compiler-generated code. 158 // 159 // Do not change signature: used via linkname from other packages. 160 // 161 //go:nosplit 162 //go:linkname rand 163 func rand() uint64 { 164 // Note: We avoid acquirem here so that in the fast path 165 // there is just a getg, an inlined c.Next, and a return. 166 // The performance difference on a 16-core AMD is 167 // 3.7ns/call this way versus 4.3ns/call with acquirem (+16%). 168 mp := getg().m 169 c := &mp.chacha8 170 for { 171 // Note: c.Next is marked nosplit, 172 // so we don't need to use mp.locks 173 // on the fast path, which is that the 174 // first attempt succeeds. 175 x, ok := c.Next() 176 if ok { 177 return x 178 } 179 mp.locks++ // hold m even though c.Refill may do stack split checks 180 c.Refill() 181 mp.locks-- 182 } 183 } 184 185 //go:linkname maps_rand internal/runtime/maps.rand 186 func maps_rand() uint64 { 187 return rand() 188 } 189 190 // mrandinit initializes the random state of an m. 191 func mrandinit(mp *m) { 192 var seed [4]uint64 193 for i := range seed { 194 seed[i] = bootstrapRand() 195 } 196 bootstrapRandReseed() // erase key we just extracted 197 mp.chacha8.Init64(seed) 198 mp.cheaprand = uint32(rand()) 199 mp.cheaprand64 = rand() 200 } 201 202 // randn is like rand() % n but faster. 203 // Do not change signature: used via linkname from other packages. 204 // 205 //go:nosplit 206 //go:linkname randn 207 func randn(n uint32) uint32 { 208 // See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ 209 return uint32((uint64(uint32(rand())) * uint64(n)) >> 32) 210 } 211 212 // cheaprand is a non-cryptographic-quality 32-bit random generator 213 // suitable for calling at very high frequency (such as during scheduling decisions) 214 // and at sensitive moments in the runtime (such as during stack unwinding). 215 // it is "cheap" in the sense of both expense and quality. 216 // 217 // cheaprand must not be exported to other packages: 218 // the rule is that other packages using runtime-provided 219 // randomness must always use rand. 220 // 221 // cheaprand should be an internal detail, 222 // but widely used packages access it using linkname. 223 // Notable members of the hall of shame include: 224 // - github.com/bytedance/gopkg 225 // 226 // Do not remove or change the type signature. 227 // See go.dev/issue/67401. 228 // 229 //go:linkname cheaprand 230 //go:nosplit 231 func cheaprand() uint32 { 232 mp := getg().m 233 // Implement wyrand: https://github.com/wangyi-fudan/wyhash 234 // Only the platform that supports 64-bit multiplication 235 // natively should be allowed. 236 if bits.UintSize == 64 { 237 mp.cheaprand += 0x53c5ca59 238 hi, lo := bits.Mul32(mp.cheaprand, mp.cheaprand^0x74743c1b) 239 return hi ^ lo 240 } 241 242 // Implement xorshift64+: 2 32-bit xorshift sequences added together. 243 // Shift triplet [17,7,16] was calculated as indicated in Marsaglia's 244 // Xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf 245 // This generator passes the SmallCrush suite, part of TestU01 framework: 246 // http://simul.iro.umontreal.ca/testu01/tu01.html 247 t := (*[2]uint32)(unsafe.Pointer(&mp.cheaprand64)) 248 s1, s0 := t[0], t[1] 249 s1 ^= s1 << 17 250 s1 = s1 ^ s0 ^ s1>>7 ^ s0>>16 251 t[0], t[1] = s0, s1 252 return s0 + s1 253 } 254 255 // cheaprand64 is a non-cryptographic-quality 63-bit random generator 256 // suitable for calling at very high frequency (such as during sampling decisions). 257 // it is "cheap" in the sense of both expense and quality. 258 // 259 // cheaprand64 must not be exported to other packages: 260 // the rule is that other packages using runtime-provided 261 // randomness must always use rand. 262 // 263 // cheaprand64 should be an internal detail, 264 // but widely used packages access it using linkname. 265 // Notable members of the hall of shame include: 266 // - github.com/zhangyunhao116/fastrand 267 // 268 // Do not remove or change the type signature. 269 // See go.dev/issue/67401. 270 // 271 //go:linkname cheaprand64 272 //go:nosplit 273 func cheaprand64() int64 { 274 return int64(cheaprandu64() & ^(uint64(1) << 63)) 275 } 276 277 // cheaprandu64 is a non-cryptographic-quality 64-bit random generator 278 // suitable for calling at very high frequency (such as during sampling decisions). 279 // it is "cheap" in the sense of both expense and quality. 280 // 281 // cheaprandu64 must not be exported to other packages: 282 // the rule is that other packages using runtime-provided 283 // randomness must always use rand. 284 // 285 //go:nosplit 286 func cheaprandu64() uint64 { 287 // Implement wyrand: https://github.com/wangyi-fudan/wyhash 288 // Only the platform that bits.Mul64 can be lowered 289 // by the compiler should be in this list. 290 if goarch.IsAmd64|goarch.IsArm64|goarch.IsPpc64| 291 goarch.IsPpc64le|goarch.IsMips64|goarch.IsMips64le| 292 goarch.IsS390x|goarch.IsRiscv64|goarch.IsLoong64 == 1 { 293 mp := getg().m 294 // Implement wyrand: https://github.com/wangyi-fudan/wyhash 295 mp.cheaprand64 += 0xa0761d6478bd642f 296 hi, lo := bits.Mul64(mp.cheaprand64, mp.cheaprand64^0xe7037ed1a0b428db) 297 return hi ^ lo 298 } 299 300 return uint64(cheaprand())<<32 | uint64(cheaprand()) 301 } 302 303 // cheaprandn is like cheaprand() % n but faster. 304 // 305 // cheaprandn must not be exported to other packages: 306 // the rule is that other packages using runtime-provided 307 // randomness must always use randn. 308 // 309 // cheaprandn should be an internal detail, 310 // but widely used packages access it using linkname. 311 // Notable members of the hall of shame include: 312 // - github.com/phuslu/log 313 // 314 // Do not remove or change the type signature. 315 // See go.dev/issue/67401. 316 // 317 //go:linkname cheaprandn 318 //go:nosplit 319 func cheaprandn(n uint32) uint32 { 320 // See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ 321 return uint32((uint64(cheaprand()) * uint64(n)) >> 32) 322 } 323 324 // Too much legacy code has go:linkname references 325 // to runtime.fastrand and friends, so keep these around for now. 326 // Code should migrate to math/rand/v2.Uint64, 327 // which is just as fast, but that's only available in Go 1.22+. 328 // It would be reasonable to remove these in Go 1.24. 329 // Do not call these from package runtime. 330 331 //go:linkname legacy_fastrand runtime.fastrand 332 func legacy_fastrand() uint32 { 333 return uint32(rand()) 334 } 335 336 //go:linkname legacy_fastrandn runtime.fastrandn 337 func legacy_fastrandn(n uint32) uint32 { 338 return randn(n) 339 } 340 341 //go:linkname legacy_fastrand64 runtime.fastrand64 342 func legacy_fastrand64() uint64 { 343 return rand() 344 } 345