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  // bootstrapRand returns a random uint64 from the global random generator.
   121  func bootstrapRand() uint64 {
   122  	lock(&globalRand.lock)
   123  	if !globalRand.init {
   124  		fatal("randinit missed")
   125  	}
   126  	for {
   127  		if x, ok := globalRand.state.Next(); ok {
   128  			unlock(&globalRand.lock)
   129  			return x
   130  		}
   131  		globalRand.state.Refill()
   132  	}
   133  }
   134  
   135  // bootstrapRandReseed reseeds the bootstrap random number generator,
   136  // clearing from memory any trace of previously returned random numbers.
   137  func bootstrapRandReseed() {
   138  	lock(&globalRand.lock)
   139  	if !globalRand.init {
   140  		fatal("randinit missed")
   141  	}
   142  	globalRand.state.Reseed()
   143  	unlock(&globalRand.lock)
   144  }
   145  
   146  // rand32 is uint32(rand()), called from compiler-generated code.
   147  //
   148  //go:nosplit
   149  func rand32() uint32 {
   150  	return uint32(rand())
   151  }
   152  
   153  // rand returns a random uint64 from the per-m chacha8 state.
   154  // This is called from compiler-generated code.
   155  //
   156  // Do not change signature: used via linkname from other packages.
   157  //
   158  //go:nosplit
   159  //go:linkname rand
   160  func rand() uint64 {
   161  	// Note: We avoid acquirem here so that in the fast path
   162  	// there is just a getg, an inlined c.Next, and a return.
   163  	// The performance difference on a 16-core AMD is
   164  	// 3.7ns/call this way versus 4.3ns/call with acquirem (+16%).
   165  	mp := getg().m
   166  	c := &mp.chacha8
   167  	for {
   168  		// Note: c.Next is marked nosplit,
   169  		// so we don't need to use mp.locks
   170  		// on the fast path, which is that the
   171  		// first attempt succeeds.
   172  		x, ok := c.Next()
   173  		if ok {
   174  			return x
   175  		}
   176  		mp.locks++ // hold m even though c.Refill may do stack split checks
   177  		c.Refill()
   178  		mp.locks--
   179  	}
   180  }
   181  
   182  //go:linkname maps_rand internal/runtime/maps.rand
   183  func maps_rand() uint64 {
   184  	return rand()
   185  }
   186  
   187  // mrandinit initializes the random state of an m.
   188  func mrandinit(mp *m) {
   189  	var seed [4]uint64
   190  	for i := range seed {
   191  		seed[i] = bootstrapRand()
   192  	}
   193  	bootstrapRandReseed() // erase key we just extracted
   194  	mp.chacha8.Init64(seed)
   195  	mp.cheaprand = uint32(rand())
   196  	mp.cheaprand64 = rand()
   197  }
   198  
   199  // randn is like rand() % n but faster.
   200  // Do not change signature: used via linkname from other packages.
   201  //
   202  //go:nosplit
   203  //go:linkname randn
   204  func randn(n uint32) uint32 {
   205  	// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
   206  	return uint32((uint64(uint32(rand())) * uint64(n)) >> 32)
   207  }
   208  
   209  // cheaprand is a non-cryptographic-quality 32-bit random generator
   210  // suitable for calling at very high frequency (such as during scheduling decisions)
   211  // and at sensitive moments in the runtime (such as during stack unwinding).
   212  // it is "cheap" in the sense of both expense and quality.
   213  //
   214  // cheaprand must not be exported to other packages:
   215  // the rule is that other packages using runtime-provided
   216  // randomness must always use rand.
   217  //
   218  // cheaprand should be an internal detail,
   219  // but widely used packages access it using linkname.
   220  // Notable members of the hall of shame include:
   221  //   - github.com/bytedance/gopkg
   222  //
   223  // Do not remove or change the type signature.
   224  // See go.dev/issue/67401.
   225  //
   226  //go:linkname cheaprand
   227  //go:nosplit
   228  func cheaprand() uint32 {
   229  	mp := getg().m
   230  	// Implement wyrand: https://github.com/wangyi-fudan/wyhash
   231  	// Only the platform that supports 64-bit multiplication
   232  	// natively should be allowed.
   233  	if bits.UintSize == 64 {
   234  		mp.cheaprand += 0x53c5ca59
   235  		hi, lo := bits.Mul32(mp.cheaprand, mp.cheaprand^0x74743c1b)
   236  		return hi ^ lo
   237  	}
   238  
   239  	// Implement xorshift64+: 2 32-bit xorshift sequences added together.
   240  	// Shift triplet [17,7,16] was calculated as indicated in Marsaglia's
   241  	// Xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf
   242  	// This generator passes the SmallCrush suite, part of TestU01 framework:
   243  	// http://simul.iro.umontreal.ca/testu01/tu01.html
   244  	t := (*[2]uint32)(unsafe.Pointer(&mp.cheaprand64))
   245  	s1, s0 := t[0], t[1]
   246  	s1 ^= s1 << 17
   247  	s1 = s1 ^ s0 ^ s1>>7 ^ s0>>16
   248  	t[0], t[1] = s0, s1
   249  	return s0 + s1
   250  }
   251  
   252  // cheaprand64 is a non-cryptographic-quality 63-bit random generator
   253  // suitable for calling at very high frequency (such as during sampling decisions).
   254  // it is "cheap" in the sense of both expense and quality.
   255  //
   256  // cheaprand64 must not be exported to other packages:
   257  // the rule is that other packages using runtime-provided
   258  // randomness must always use rand.
   259  //
   260  // cheaprand64 should be an internal detail,
   261  // but widely used packages access it using linkname.
   262  // Notable members of the hall of shame include:
   263  //   - github.com/zhangyunhao116/fastrand
   264  //
   265  // Do not remove or change the type signature.
   266  // See go.dev/issue/67401.
   267  //
   268  //go:linkname cheaprand64
   269  //go:nosplit
   270  func cheaprand64() int64 {
   271  	return int64(cheaprandu64() & ^(uint64(1) << 63))
   272  }
   273  
   274  // cheaprandu64 is a non-cryptographic-quality 64-bit random generator
   275  // suitable for calling at very high frequency (such as during sampling decisions).
   276  // it is "cheap" in the sense of both expense and quality.
   277  //
   278  // cheaprandu64 must not be exported to other packages:
   279  // the rule is that other packages using runtime-provided
   280  // randomness must always use rand.
   281  //
   282  //go:nosplit
   283  func cheaprandu64() uint64 {
   284  	// Implement wyrand: https://github.com/wangyi-fudan/wyhash
   285  	// Only the platform that bits.Mul64 can be lowered
   286  	// by the compiler should be in this list.
   287  	if goarch.IsAmd64|goarch.IsArm64|goarch.IsPpc64|
   288  		goarch.IsPpc64le|goarch.IsMips64|goarch.IsMips64le|
   289  		goarch.IsS390x|goarch.IsRiscv64|goarch.IsLoong64 == 1 {
   290  		mp := getg().m
   291  		// Implement wyrand: https://github.com/wangyi-fudan/wyhash
   292  		mp.cheaprand64 += 0xa0761d6478bd642f
   293  		hi, lo := bits.Mul64(mp.cheaprand64, mp.cheaprand64^0xe7037ed1a0b428db)
   294  		return hi ^ lo
   295  	}
   296  
   297  	return uint64(cheaprand())<<32 | uint64(cheaprand())
   298  }
   299  
   300  // cheaprandn is like cheaprand() % n but faster.
   301  //
   302  // cheaprandn must not be exported to other packages:
   303  // the rule is that other packages using runtime-provided
   304  // randomness must always use randn.
   305  //
   306  // cheaprandn should be an internal detail,
   307  // but widely used packages access it using linkname.
   308  // Notable members of the hall of shame include:
   309  //   - github.com/phuslu/log
   310  //
   311  // Do not remove or change the type signature.
   312  // See go.dev/issue/67401.
   313  //
   314  //go:linkname cheaprandn
   315  //go:nosplit
   316  func cheaprandn(n uint32) uint32 {
   317  	// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
   318  	return uint32((uint64(cheaprand()) * uint64(n)) >> 32)
   319  }
   320  
   321  // Too much legacy code has go:linkname references
   322  // to runtime.fastrand and friends, so keep these around for now.
   323  // Code should migrate to math/rand/v2.Uint64,
   324  // which is just as fast, but that's only available in Go 1.22+.
   325  // It would be reasonable to remove these in Go 1.24.
   326  // Do not call these from package runtime.
   327  
   328  //go:linkname legacy_fastrand runtime.fastrand
   329  func legacy_fastrand() uint32 {
   330  	return uint32(rand())
   331  }
   332  
   333  //go:linkname legacy_fastrandn runtime.fastrandn
   334  func legacy_fastrandn(n uint32) uint32 {
   335  	return randn(n)
   336  }
   337  
   338  //go:linkname legacy_fastrand64 runtime.fastrand64
   339  func legacy_fastrand64() uint64 {
   340  	return rand()
   341  }
   342
View as plain text