base/rand_util.h

   1 // Copyright 2012 The Chromium Authors
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef BASE_RAND_UTIL_H_
   6 #define BASE_RAND_UTIL_H_
   7
   8 #include <stddef.h>
   9 #include <stdint.h>
  10
  11 #include <algorithm>
  12 #include <string>
  13
  14 #include "base/base_export.h"
  15 #include "base/compiler_specific.h"
  16 #include "base/gtest_prod_util.h"
  17 #include "build/build_config.h"
  18
  19 #if !BUILDFLAG(IS_NACL)
  20 #include "third_party/boringssl/src/include/openssl/rand.h"
  21 #endif
  22
  23 namespace memory_simulator {
  24 class MemoryHolder;
  25 }
  26
  27 namespace base {
  28
  29 class TimeDelta;
  30
  31 namespace internal {
  32
  33 #if BUILDFLAG(IS_ANDROID)
  34 // Sets the implementation of RandBytes according to the corresponding
  35 // base::Feature. Thread safe: allows to switch while RandBytes() is in use.
  36 void ConfigureRandBytesFieldTrial();
  37 #endif
  38
  39 #if !BUILDFLAG(IS_NACL)
  40 void ConfigureBoringSSLBackedRandBytesFieldTrial();
  41 #endif
  42
  43 // Returns a random double in range [0, 1). For use in allocator shim to avoid
  44 // infinite recursion. Thread-safe.
  45 BASE_EXPORT double RandDoubleAvoidAllocation();
  46
  47 }  // namespace internal
  48
  49 // Returns a random number in range [0, UINT64_MAX]. Thread-safe.
  50 BASE_EXPORT uint64_t RandUint64();
  51
  52 // Returns a random number between min and max (inclusive). Thread-safe.
  53 //
  54 // TODO(crbug.com/1488681): Change from fully-closed to half-closed (i.e.
  55 // exclude `max`) to parallel other APIs here.
  56 BASE_EXPORT int RandInt(int min, int max);
  57
  58 // Returns a random number in range [0, range).  Thread-safe.
  59 BASE_EXPORT uint64_t RandGenerator(uint64_t range);
  60
  61 // Returns a random double in range [0, 1). Thread-safe.
  62 BASE_EXPORT double RandDouble();
  63
  64 // Returns a random float in range [0, 1). Thread-safe.
  65 BASE_EXPORT float RandFloat();
  66
  67 // Returns a random duration in [`start`, `limit`). Thread-safe.
  68 //
  69 // REQUIRES: `start` < `limit`
  70 BASE_EXPORT TimeDelta RandTimeDelta(TimeDelta start, TimeDelta limit);
  71
  72 // Returns a random duration in [`TimeDelta()`, `limit`). Thread-safe.
  73 //
  74 // REQUIRES: `limit.is_positive()`
  75 BASE_EXPORT TimeDelta RandTimeDeltaUpTo(TimeDelta limit);
  76
  77 // Given input |bits|, convert with maximum precision to a double in
  78 // the range [0, 1). Thread-safe.
  79 BASE_EXPORT double BitsToOpenEndedUnitInterval(uint64_t bits);
  80
  81 // Given input `bits`, convert with maximum precision to a float in the range
  82 // [0, 1). Thread-safe.
  83 BASE_EXPORT float BitsToOpenEndedUnitIntervalF(uint64_t bits);
  84
  85 // Fills |output_length| bytes of |output| with random data. Thread-safe.
  86 //
  87 // Although implementations are required to use a cryptographically secure
  88 // random number source, code outside of base/ that relies on this should use
  89 // crypto::RandBytes instead to ensure the requirement is easily discoverable.
  90 BASE_EXPORT void RandBytes(void* output, size_t output_length);
  91
  92 // Fills a string of length |length| with random data and returns it.
  93 // |length| should be nonzero. Thread-safe.
  94 //
  95 // Note that this is a variation of |RandBytes| with a different return type.
  96 // The returned string is likely not ASCII/UTF-8. Use with care.
  97 //
  98 // Although implementations are required to use a cryptographically secure
  99 // random number source, code outside of base/ that relies on this should use
 100 // crypto::RandBytes instead to ensure the requirement is easily discoverable.
 101 BASE_EXPORT std::string RandBytesAsString(size_t length);
 102
 103 // An STL UniformRandomBitGenerator backed by RandUint64.
 104 class RandomBitGenerator {
 105  public:
 106   using result_type = uint64_t;
 107   static constexpr result_type min() { return 0; }
 108   static constexpr result_type max() { return UINT64_MAX; }
 109   result_type operator()() const { return RandUint64(); }
 110
 111   RandomBitGenerator() = default;
 112   ~RandomBitGenerator() = default;
 113 };
 114
 115 #if !BUILDFLAG(IS_NACL)
 116 class NonAllocatingRandomBitGenerator {
 117  public:
 118   using result_type = uint64_t;
 119   static constexpr result_type min() { return 0; }
 120   static constexpr result_type max() { return UINT64_MAX; }
 121   result_type operator()() const {
 122     uint64_t result;
 123     RAND_get_system_entropy_for_custom_prng(reinterpret_cast<uint8_t*>(&result),
 124                                             sizeof(result));
 125     return result;
 126   }
 127
 128   NonAllocatingRandomBitGenerator() = default;
 129   ~NonAllocatingRandomBitGenerator() = default;
 130 };
 131 #endif
 132
 133 // Shuffles [first, last) randomly. Thread-safe.
 134 template <typename Itr>
 135 void RandomShuffle(Itr first, Itr last) {
 136   std::shuffle(first, last, RandomBitGenerator());
 137 }
 138
 139 #if BUILDFLAG(IS_POSIX)
 140 BASE_EXPORT int GetUrandomFD();
 141 #endif
 142
 143 class MetricsSubSampler;
 144
 145 // Fast, insecure pseudo-random number generator.
 146 //
 147 // WARNING: This is not the generator you are looking for. This has significant
 148 // caveats:
 149 //   - It is non-cryptographic, so easy to miuse
 150 //   - It is neither fork() nor clone()-safe.
 151 //   - Synchronization is up to the client.
 152 //
 153 // Always prefer base::Rand*() above, unless you have a use case where its
 154 // overhead is too high, or system calls are disallowed.
 155 //
 156 // Performance: As of 2021, rough overhead on Linux on a desktop machine of
 157 // base::RandUint64() is ~800ns per call (it performs a system call). On Windows
 158 // it is lower. On the same machine, this generator's cost is ~2ns per call,
 159 // regardless of platform.
 160 //
 161 // This is different from |Rand*()| above as it is guaranteed to never make a
 162 // system call to generate a new number, except to seed it.  This should *never*
 163 // be used for cryptographic applications, and is not thread-safe.
 164 //
 165 // It is seeded using base::RandUint64() in the constructor, meaning that it
 166 // doesn't need to be seeded. It can be re-seeded though, with
 167 // ReseedForTesting(). Its period is long enough that it should not need to be
 168 // re-seeded during use.
 169 //
 170 // Uses the XorShift128+ generator under the hood.
 171 class BASE_EXPORT InsecureRandomGenerator {
 172  public:
 173   // Never use outside testing, not enough entropy.
 174   void ReseedForTesting(uint64_t seed);
 175
 176   uint32_t RandUint32();
 177   uint64_t RandUint64();
 178   // In [0, 1).
 179   double RandDouble();
 180
 181  private:
 182   InsecureRandomGenerator();
 183   // State.
 184   uint64_t a_ = 0, b_ = 0;
 185
 186   // Before adding a new friend class, make sure that the overhead of
 187   // base::Rand*() is too high, using something more representative than a
 188   // microbenchmark.
 189
 190   // Uses the generator to fill memory pages with random content to make them
 191   // hard to compress, in a simulation tool not bundled with Chrome. CPU
 192   // overhead must be minimized to correctly measure memory effects.
 193   friend class memory_simulator::MemoryHolder;
 194   // Uses the generator to sub-sample metrics.
 195   friend class MetricsSubSampler;
 196
 197   FRIEND_TEST_ALL_PREFIXES(RandUtilTest,
 198                            InsecureRandomGeneratorProducesBothValuesOfAllBits);
 199   FRIEND_TEST_ALL_PREFIXES(RandUtilTest, InsecureRandomGeneratorChiSquared);
 200   FRIEND_TEST_ALL_PREFIXES(RandUtilTest, InsecureRandomGeneratorRandDouble);
 201   FRIEND_TEST_ALL_PREFIXES(RandUtilPerfTest, InsecureRandomRandUint64);
 202 };
 203
 204 class BASE_EXPORT MetricsSubSampler {
 205  public:
 206   MetricsSubSampler();
 207   bool ShouldSample(double probability);
 208
 209   // Disables subsampling in a scope. Useful for testing.
 210   class BASE_EXPORT ScopedDisableForTesting {
 211    public:
 212     ScopedDisableForTesting();
 213     ~ScopedDisableForTesting();
 214   };
 215
 216  private:
 217   InsecureRandomGenerator generator_;
 218 };
 219
 220 }  // namespace base
 221
 222 #endif  // BASE_RAND_UTIL_H_