rand_util.h 5.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161
  1. // Copyright (c) 2012 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef BASE_RAND_UTIL_H_
  5. #define BASE_RAND_UTIL_H_
  6. #include <stddef.h>
  7. #include <stdint.h>
  8. #include <algorithm>
  9. #include <string>
  10. #include "base/base_export.h"
  11. #include "base/gtest_prod_util.h"
  12. #include "build/build_config.h"
  13. namespace partition_alloc {
  14. class RandomGenerator;
  15. } // namespace partition_alloc
  16. namespace base {
  17. // Returns a random number in range [0, UINT64_MAX]. Thread-safe.
  18. BASE_EXPORT uint64_t RandUint64();
  19. // Returns a random number between min and max (inclusive). Thread-safe.
  20. BASE_EXPORT int RandInt(int min, int max);
  21. // Returns a random number in range [0, range). Thread-safe.
  22. BASE_EXPORT uint64_t RandGenerator(uint64_t range);
  23. // Returns a random double in range [0, 1). Thread-safe.
  24. BASE_EXPORT double RandDouble();
  25. // Given input |bits|, convert with maximum precision to a double in
  26. // the range [0, 1). Thread-safe.
  27. BASE_EXPORT double BitsToOpenEndedUnitInterval(uint64_t bits);
  28. #if BUILDFLAG(IS_ANDROID)
  29. // Sets the implementation of RandBytes according to the corresponding
  30. // base::Feature. Thread safe: allows to switch while RandBytes() is in use.
  31. BASE_EXPORT void ConfigureRandBytesFieldTrial();
  32. #endif
  33. // Fills |output_length| bytes of |output| with random data. Thread-safe.
  34. //
  35. // Although implementations are required to use a cryptographically secure
  36. // random number source, code outside of base/ that relies on this should use
  37. // crypto::RandBytes instead to ensure the requirement is easily discoverable.
  38. BASE_EXPORT void RandBytes(void* output, size_t output_length);
  39. // Fills a string of length |length| with random data and returns it.
  40. // |length| should be nonzero. Thread-safe.
  41. //
  42. // Note that this is a variation of |RandBytes| with a different return type.
  43. // The returned string is likely not ASCII/UTF-8. Use with care.
  44. //
  45. // Although implementations are required to use a cryptographically secure
  46. // random number source, code outside of base/ that relies on this should use
  47. // crypto::RandBytes instead to ensure the requirement is easily discoverable.
  48. BASE_EXPORT std::string RandBytesAsString(size_t length);
  49. // An STL UniformRandomBitGenerator backed by RandUint64.
  50. // TODO(tzik): Consider replacing this with a faster implementation.
  51. class RandomBitGenerator {
  52. public:
  53. using result_type = uint64_t;
  54. static constexpr result_type min() { return 0; }
  55. static constexpr result_type max() { return UINT64_MAX; }
  56. result_type operator()() const { return RandUint64(); }
  57. RandomBitGenerator() = default;
  58. ~RandomBitGenerator() = default;
  59. };
  60. // Shuffles [first, last) randomly. Thread-safe.
  61. template <typename Itr>
  62. void RandomShuffle(Itr first, Itr last) {
  63. std::shuffle(first, last, RandomBitGenerator());
  64. }
  65. #if BUILDFLAG(IS_POSIX)
  66. BASE_EXPORT int GetUrandomFD();
  67. #endif
  68. class MetricsSubSampler;
  69. // Fast, insecure pseudo-random number generator.
  70. //
  71. // WARNING: This is not the generator you are looking for. This has significant
  72. // caveats:
  73. // - It is non-cryptographic, so easy to miuse
  74. // - It is neither fork() nor clone()-safe.
  75. // - Synchronization is up to the client.
  76. //
  77. // Always prefer base::Rand*() above, unless you have a use case where its
  78. // overhead is too high, or system calls are disallowed.
  79. //
  80. // Performance: As of 2021, rough overhead on Linux on a desktop machine of
  81. // base::RandUint64() is ~800ns per call (it performs a system call). On Windows
  82. // it is lower. On the same machine, this generator's cost is ~2ns per call,
  83. // regardless of platform.
  84. //
  85. // This is different from |Rand*()| above as it is guaranteed to never make a
  86. // system call to generate a new number, except to seed it. This should *never*
  87. // be used for cryptographic applications, and is not thread-safe.
  88. //
  89. // It is seeded using base::RandUint64() in the constructor, meaning that it
  90. // doesn't need to be seeded. It can be re-seeded though, with
  91. // ReseedForTesting(). Its period is long enough that it should not need to be
  92. // re-seeded during use.
  93. //
  94. // Uses the XorShift128+ generator under the hood.
  95. class BASE_EXPORT InsecureRandomGenerator {
  96. public:
  97. // Never use outside testing, not enough entropy.
  98. void ReseedForTesting(uint64_t seed);
  99. uint32_t RandUint32();
  100. uint64_t RandUint64();
  101. // In [0, 1).
  102. double RandDouble();
  103. private:
  104. InsecureRandomGenerator();
  105. // State.
  106. uint64_t a_ = 0, b_ = 0;
  107. // Before adding a new friend class, make sure that the overhead of
  108. // base::Rand*() is too high, using something more representative than a
  109. // microbenchmark.
  110. //
  111. // PartitionAlloc allocations should not take more than 40-50ns per
  112. // malloc()/free() pair, otherwise high-level benchmarks regress, and does not
  113. // need a secure PRNG, as it's used for ASLR and zeroing some allocations at
  114. // free() time.
  115. friend class ::partition_alloc::RandomGenerator;
  116. // Uses the generator to sub-sample metrics.
  117. friend class MetricsSubSampler;
  118. FRIEND_TEST_ALL_PREFIXES(RandUtilTest,
  119. InsecureRandomGeneratorProducesBothValuesOfAllBits);
  120. FRIEND_TEST_ALL_PREFIXES(RandUtilTest, InsecureRandomGeneratorChiSquared);
  121. FRIEND_TEST_ALL_PREFIXES(RandUtilTest, InsecureRandomGeneratorRandDouble);
  122. FRIEND_TEST_ALL_PREFIXES(RandUtilPerfTest, InsecureRandomRandUint64);
  123. };
  124. class BASE_EXPORT MetricsSubSampler {
  125. public:
  126. MetricsSubSampler();
  127. bool ShouldSample(double probability);
  128. private:
  129. InsecureRandomGenerator generator_;
  130. };
  131. } // namespace base
  132. #endif // BASE_RAND_UTIL_H_