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