tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

rand_util.h (7384B)

      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) && !defined(MOZ_SANDBOX)
     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) && !defined(MOZ_SANDBOX)
     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) && !defined(MOZ_SANDBOX)
    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_