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  	"internal/runtime/math"
    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 = rand()
   196  }
   197  
   198  // randn is like rand() % n but faster.
   199  // Do not change signature: used via linkname from other packages.
   200  //
   201  //go:nosplit
   202  //go:linkname randn
   203  func randn(n uint32) uint32 {
   204  	// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
   205  	return uint32((uint64(uint32(rand())) * uint64(n)) >> 32)
   206  }
   207  
   208  // cheaprand is a non-cryptographic-quality 32-bit random generator
   209  // suitable for calling at very high frequency (such as during scheduling decisions)
   210  // and at sensitive moments in the runtime (such as during stack unwinding).
   211  // it is "cheap" in the sense of both expense and quality.
   212  //
   213  // cheaprand must not be exported to other packages:
   214  // the rule is that other packages using runtime-provided
   215  // randomness must always use rand.
   216  //
   217  // cheaprand should be an internal detail,
   218  // but widely used packages access it using linkname.
   219  // Notable members of the hall of shame include:
   220  //   - github.com/bytedance/gopkg
   221  //
   222  // Do not remove or change the type signature.
   223  // See go.dev/issue/67401.
   224  //
   225  //go:linkname cheaprand
   226  //go:nosplit
   227  func cheaprand() uint32 {
   228  	mp := getg().m
   229  	// Implement wyrand: https://github.com/wangyi-fudan/wyhash
   230  	// Only the platform that math.Mul64 can be lowered
   231  	// by the compiler should be in this list.
   232  	if goarch.IsAmd64|goarch.IsArm64|goarch.IsPpc64|
   233  		goarch.IsPpc64le|goarch.IsMips64|goarch.IsMips64le|
   234  		goarch.IsS390x|goarch.IsRiscv64|goarch.IsLoong64 == 1 {
   235  		mp.cheaprand += 0xa0761d6478bd642f
   236  		hi, lo := math.Mul64(mp.cheaprand, mp.cheaprand^0xe7037ed1a0b428db)
   237  		return uint32(hi ^ lo)
   238  	}
   239  
   240  	// Implement xorshift64+: 2 32-bit xorshift sequences added together.
   241  	// Shift triplet [17,7,16] was calculated as indicated in Marsaglia's
   242  	// Xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf
   243  	// This generator passes the SmallCrush suite, part of TestU01 framework:
   244  	// http://simul.iro.umontreal.ca/testu01/tu01.html
   245  	t := (*[2]uint32)(unsafe.Pointer(&mp.cheaprand))
   246  	s1, s0 := t[0], t[1]
   247  	s1 ^= s1 << 17
   248  	s1 = s1 ^ s0 ^ s1>>7 ^ s0>>16
   249  	t[0], t[1] = s0, s1
   250  	return s0 + s1
   251  }
   252  
   253  // cheaprand64 is a non-cryptographic-quality 63-bit random generator
   254  // suitable for calling at very high frequency (such as during sampling decisions).
   255  // it is "cheap" in the sense of both expense and quality.
   256  //
   257  // cheaprand64 must not be exported to other packages:
   258  // the rule is that other packages using runtime-provided
   259  // randomness must always use rand.
   260  //
   261  // cheaprand64 should be an internal detail,
   262  // but widely used packages access it using linkname.
   263  // Notable members of the hall of shame include:
   264  //   - github.com/zhangyunhao116/fastrand
   265  //
   266  // Do not remove or change the type signature.
   267  // See go.dev/issue/67401.
   268  //
   269  //go:linkname cheaprand64
   270  //go:nosplit
   271  func cheaprand64() int64 {
   272  	return int64(cheaprand())<<31 ^ int64(cheaprand())
   273  }
   274  
   275  // cheaprandn is like cheaprand() % n but faster.
   276  //
   277  // cheaprandn must not be exported to other packages:
   278  // the rule is that other packages using runtime-provided
   279  // randomness must always use randn.
   280  //
   281  // cheaprandn should be an internal detail,
   282  // but widely used packages access it using linkname.
   283  // Notable members of the hall of shame include:
   284  //   - github.com/phuslu/log
   285  //
   286  // Do not remove or change the type signature.
   287  // See go.dev/issue/67401.
   288  //
   289  //go:linkname cheaprandn
   290  //go:nosplit
   291  func cheaprandn(n uint32) uint32 {
   292  	// See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
   293  	return uint32((uint64(cheaprand()) * uint64(n)) >> 32)
   294  }
   295  
   296  // Too much legacy code has go:linkname references
   297  // to runtime.fastrand and friends, so keep these around for now.
   298  // Code should migrate to math/rand/v2.Uint64,
   299  // which is just as fast, but that's only available in Go 1.22+.
   300  // It would be reasonable to remove these in Go 1.24.
   301  // Do not call these from package runtime.
   302  
   303  //go:linkname legacy_fastrand runtime.fastrand
   304  func legacy_fastrand() uint32 {
   305  	return uint32(rand())
   306  }
   307  
   308  //go:linkname legacy_fastrandn runtime.fastrandn
   309  func legacy_fastrandn(n uint32) uint32 {
   310  	return randn(n)
   311  }
   312  
   313  //go:linkname legacy_fastrand64 runtime.fastrand64
   314  func legacy_fastrand64() uint64 {
   315  	return rand()
   316  }
   317
View as plain text