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