--- /dev/null
+/*
+ * Copyright 2014 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef FOLLY_RANDOM_H_
+#error This file may only be included from folly/Random.h
+#endif
+
+namespace folly {
+
+namespace detail {
+
+// Return the state size needed by RNG, expressed as a number of uint32_t
+// integers. Specialized for all templates specified in the C++11 standard.
+// For some (mersenne_twister_engine), this is exported as a state_size static
+// data member; for others, the standard shows formulas.
+
+template <class RNG> struct StateSize {
+ // A sane default.
+ static constexpr size_t value = 512;
+};
+
+template <class RNG>
+constexpr size_t StateSize<RNG>::value;
+
+template <class UIntType, UIntType a, UIntType c, UIntType m>
+struct StateSize<std::linear_congruential_engine<UIntType, a, c, m>> {
+ // From the standard [rand.eng.lcong], this is ceil(log2(m) / 32) + 3,
+ // which is the same as ceil(ceil(log2(m) / 32) + 3, and
+ // ceil(log2(m)) <= std::numeric_limits<UIntType>::digits
+ static constexpr size_t value =
+ (std::numeric_limits<UIntType>::digits + 31) / 32 + 3;
+};
+
+template <class UIntType, UIntType a, UIntType c, UIntType m>
+constexpr size_t
+StateSize<std::linear_congruential_engine<UIntType, a, c, m>>::value;
+
+template <class UIntType, size_t w, size_t n, size_t m, size_t r,
+ UIntType a, size_t u, UIntType d, size_t s,
+ UIntType b, size_t t,
+ UIntType c, size_t l, UIntType f>
+struct StateSize<std::mersenne_twister_engine<UIntType, w, n, m, r,
+ a, u, d, s, b, t, c, l, f>> {
+ static constexpr size_t value =
+ std::mersenne_twister_engine<UIntType, w, n, m, r,
+ a, u, d, s, b, t, c, l, f>::state_size;
+};
+
+template <class UIntType, size_t w, size_t n, size_t m, size_t r,
+ UIntType a, size_t u, UIntType d, size_t s,
+ UIntType b, size_t t,
+ UIntType c, size_t l, UIntType f>
+constexpr size_t
+StateSize<std::mersenne_twister_engine<UIntType, w, n, m, r,
+ a, u, d, s, b, t, c, l, f>>::value;
+
+#if FOLLY_USE_SIMD_PRNG
+
+template <class UIntType, size_t m, size_t pos1, size_t sl1, size_t sl2,
+ size_t sr1, size_t sr2, uint32_t msk1, uint32_t msk2, uint32_t msk3,
+ uint32_t msk4, uint32_t parity1, uint32_t parity2, uint32_t parity3,
+ uint32_t parity4>
+struct StateSize<__gnu_cxx::simd_fast_mersenne_twister_engine<
+ UIntType, m, pos1, sl1, sl2, sr1, sr2, msk1, msk2, msk3, msk4,
+ parity1, parity2, parity3, parity4>> {
+ static constexpr size_t value =
+ __gnu_cxx::simd_fast_mersenne_twister_engine<
+ UIntType, m, pos1, sl1, sl2, sr1, sr2,
+ msk1, msk2, msk3, msk4,
+ parity1, parity2, parity3, parity4>::state_size;
+};
+
+template <class UIntType, size_t m, size_t pos1, size_t sl1, size_t sl2,
+ size_t sr1, size_t sr2, uint32_t msk1, uint32_t msk2, uint32_t msk3,
+ uint32_t msk4, uint32_t parity1, uint32_t parity2, uint32_t parity3,
+ uint32_t parity4>
+constexpr size_t
+StateSize<__gnu_cxx::simd_fast_mersenne_twister_engine<
+ UIntType, m, pos1, sl1, sl2, sr1, sr2, msk1, msk2, msk3, msk4,
+ parity1, parity2, parity3, parity4>>::value;
+
+#endif
+
+template <class UIntType, size_t w, size_t s, size_t r>
+struct StateSize<std::subtract_with_carry_engine<UIntType, w, s, r>> {
+ // [rand.eng.sub]: r * ceil(w / 32)
+ static constexpr size_t value = r * ((w + 31) / 32);
+};
+
+template <class UIntType, size_t w, size_t s, size_t r>
+constexpr size_t
+StateSize<std::subtract_with_carry_engine<UIntType, w, s, r>>::value;
+
+template <class RNG>
+std::seed_seq generateSeed() {
+ std::array<uint32_t, StateSize<RNG>::value> seed_data;
+ Random::secureRandom(seed_data.begin(), seed_data.size() * sizeof(uint32_t));
+ return std::seed_seq(std::begin(seed_data), std::end(seed_data));
+}
+
+} // namespace detail
+
+template <class RNG>
+void Random::seed(ValidRNG<RNG>& rng) {
+ auto s = detail::generateSeed<RNG>();
+ rng.seed(s);
+}
+
+template <class RNG>
+auto Random::create() -> ValidRNG<RNG> {
+ auto s = detail::generateSeed<RNG>();
+ return RNG(s);
+}
+
+} // namespaces
#include <random>
#include <array>
-#if __GNUC_PREREQ(4, 8) && !defined(ANDROID)
-#include <ext/random>
-#define USE_SIMD_PRNG
-#endif
+#include <glog/logging.h>
+#include "folly/File.h"
+#include "folly/FileUtil.h"
namespace folly {
namespace {
-std::atomic<uint32_t> seedInput(0);
+
+// Keep it open for the duration of the program
+File randomDevice("/dev/urandom");
+
+void readRandomDevice(void* data, size_t size) {
+ PCHECK(readFull(randomDevice.fd(), data, size) == size);
}
-uint32_t randomNumberSeed() {
- struct timeval tv;
- gettimeofday(&tv, nullptr);
- const uint32_t kPrime0 = 51551;
- const uint32_t kPrime1 = 61631;
- const uint32_t kPrime2 = 64997;
- const uint32_t kPrime3 = 111857;
- return kPrime0 * (seedInput++)
- + kPrime1 * static_cast<uint32_t>(getpid())
- + kPrime2 * static_cast<uint32_t>(tv.tv_sec)
- + kPrime3 * static_cast<uint32_t>(tv.tv_usec);
+class BufferedRandomDevice {
+ public:
+ static constexpr size_t kDefaultBufferSize = 128;
+
+ explicit BufferedRandomDevice(size_t bufferSize = kDefaultBufferSize);
+
+ void get(void* data, size_t size) {
+ if (LIKELY(size <= remaining())) {
+ memcpy(data, ptr_, size);
+ ptr_ += size;
+ } else {
+ getSlow(static_cast<unsigned char*>(data), size);
+ }
+ }
+
+ private:
+ void getSlow(unsigned char* data, size_t size);
+
+ inline size_t remaining() const {
+ return buffer_.get() + bufferSize_ - ptr_;
+ }
+
+ const size_t bufferSize_;
+ std::unique_ptr<unsigned char[]> buffer_;
+ unsigned char* ptr_;
+};
+
+BufferedRandomDevice::BufferedRandomDevice(size_t bufferSize)
+ : bufferSize_(bufferSize),
+ buffer_(new unsigned char[bufferSize]),
+ ptr_(buffer_.get() + bufferSize) { // refill on first use
}
+void BufferedRandomDevice::getSlow(unsigned char* data, size_t size) {
+ DCHECK_GT(size, remaining());
+ if (size >= bufferSize_) {
+ // Just read directly.
+ readRandomDevice(data, size);
+ return;
+ }
+
+ size_t copied = remaining();
+ memcpy(data, ptr_, copied);
+ data += copied;
+ size -= copied;
+
+ // refill
+ readRandomDevice(buffer_.get(), bufferSize_);
+ ptr_ = buffer_.get();
+
+ memcpy(data, ptr_, size);
+ ptr_ += size;
+}
+
+ThreadLocal<BufferedRandomDevice> bufferedRandomDevice;
+
+} // namespace
+
+void Random::secureRandom(void* data, size_t size) {
+ bufferedRandomDevice->get(data, size);
+}
folly::ThreadLocalPtr<ThreadLocalPRNG::LocalInstancePRNG>
ThreadLocalPRNG::localInstance;
class ThreadLocalPRNG::LocalInstancePRNG {
-#ifdef USE_SIMD_PRNG
- typedef __gnu_cxx::sfmt19937 RNG;
-#else
- typedef std::mt19937 RNG;
-#endif
-
- static RNG makeRng() {
- std::array<int, RNG::state_size> seed_data;
- std::random_device r;
- std::generate_n(seed_data.data(), seed_data.size(), std::ref(r));
- std::seed_seq seq(std::begin(seed_data), std::end(seed_data));
- return RNG(seq);
- }
-
public:
- LocalInstancePRNG() : rng(std::move(makeRng())) {}
+ LocalInstancePRNG() : rng(Random::create()) { }
- RNG rng;
+ Random::DefaultGenerator rng;
};
ThreadLocalPRNG::LocalInstancePRNG* ThreadLocalPRNG::initLocal() {
* limitations under the License.
*/
-#ifndef FOLLY_BASE_RANDOM_H_
-#define FOLLY_BASE_RANDOM_H_
+#ifndef FOLLY_RANDOM_H_
+#define FOLLY_RANDOM_H_
+#include <type_traits>
#include <random>
#include <stdint.h>
#include "folly/ThreadLocal.h"
-namespace folly {
-
-/*
- * Return a good seed for a random number generator.
- */
-uint32_t randomNumberSeed();
+#if __GNUC_PREREQ(4, 8) && !defined(ANDROID)
+#include <ext/random>
+#define FOLLY_USE_SIMD_PRNG 1
+#endif
-class Random;
+namespace folly {
/**
* A PRNG with one instance per thread. This PRNG uses a mersenne twister random
};
-
class Random {
private:
RNG>::type;
public:
+ // Default generator type.
+#if FOLLY_USE_SIMD_PRNG
+ typedef __gnu_cxx::sfmt19937 DefaultGenerator;
+#else
+ typedef std::mt19937 DefaultGenerator;
+#endif
+
+ /**
+ * Get secure random bytes. (On Linux and OSX, this means /dev/urandom).
+ */
+ static void secureRandom(void* data, size_t len);
+
+ /**
+ * Shortcut to get a secure random value of integral type.
+ */
+ template <class T>
+ static typename std::enable_if<
+ std::is_integral<T>::value && !std::is_same<T,bool>::value,
+ T>::type
+ secureRandom() {
+ T val;
+ secureRandom(&val, sizeof(val));
+ return val;
+ }
+
+ /**
+ * (Re-)Seed an existing RNG with a good seed.
+ *
+ * Note that you should usually use ThreadLocalPRNG unless you need
+ * reproducibility (such as during a test), in which case you'd want
+ * to create a RNG with a good seed in production, and seed it yourself
+ * in test.
+ */
+ template <class RNG = DefaultGenerator>
+ static void seed(ValidRNG<RNG>& rng);
+
+ /**
+ * Create a new RNG, seeded with a good seed.
+ *
+ * Note that you should usually use ThreadLocalPRNG unless you need
+ * reproducibility (such as during a test), in which case you'd want
+ * to create a RNG with a good seed in production, and seed it yourself
+ * in test.
+ */
+ template <class RNG = DefaultGenerator>
+ static ValidRNG<RNG> create();
/**
* Returns a random uint32_t
*/
template<class RNG = ThreadLocalPRNG>
- static uint32_t rand32(ValidRNG<RNG> rrng = RNG()) {
- uint32_t r = rrng.operator()();
+ static uint32_t rand32(ValidRNG<RNG> rng = RNG()) {
+ uint32_t r = rng.operator()();
return r;
}
};
+/*
+ * Return a good seed for a random number generator.
+ * Note that this is a legacy function, as it returns a 32-bit value, which
+ * is too small to be useful as a "real" RNG seed. Use the functions in class
+ * Random instead.
+ */
+inline uint32_t randomNumberSeed() {
+ return Random::rand32();
}
+}
+
+#include "folly/Random-inl.h"
+
#endif
projects / folly.git / commitdiff