From 6019aaaa140e5280812c0ecf69a1a1ec3d4af523 Mon Sep 17 00:00:00 2001 From: Tudor Bosman Date: Thu, 19 Jun 2014 20:46:10 -0700 Subject: [PATCH] Make randomNumberSeed read from /dev/urandom Summary: Because @lesha asked "why not" and I couldn't give him an answer. Test Plan: random_test Reviewed By: bmaurer@fb.com Subscribers: bmaurer, folly@lists, jhj, kma, lesha, sdoroshenko, soren FB internal diff: D1394401 --- folly/FileUtil.cpp | 2 +- folly/Random-inl.h | 128 ++++++++++++++++++++++++++++++++++++++ folly/Random.cpp | 102 ++++++++++++++++++++---------- folly/Random.h | 80 ++++++++++++++++++++---- folly/test/RandomTest.cpp | 13 ++++ 5 files changed, 280 insertions(+), 45 deletions(-) create mode 100644 folly/Random-inl.h diff --git a/folly/FileUtil.cpp b/folly/FileUtil.cpp index 6b153fd1..6ef48e85 100644 --- a/folly/FileUtil.cpp +++ b/folly/FileUtil.cpp @@ -43,7 +43,7 @@ int closeNoInt(int fd) { // Interestingly enough, the Single Unix Specification says that the state // of the file descriptor is unspecified if close returns EINTR. In that // case, the safe thing to do is also not to retry close() -- leaking a file - // descriptor is probably better than closing the wrong file. + // descriptor is definitely better than closing the wrong file. if (r == -1 && errno == EINTR) { r = 0; } diff --git a/folly/Random-inl.h b/folly/Random-inl.h new file mode 100644 index 00000000..9da9a824 --- /dev/null +++ b/folly/Random-inl.h @@ -0,0 +1,128 @@ +/* + * 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 struct StateSize { + // A sane default. + static constexpr size_t value = 512; +}; + +template +constexpr size_t StateSize::value; + +template +struct StateSize> { + // 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::digits + static constexpr size_t value = + (std::numeric_limits::digits + 31) / 32 + 3; +}; + +template +constexpr size_t +StateSize>::value; + +template +struct StateSize> { + static constexpr size_t value = + std::mersenne_twister_engine::state_size; +}; + +template +constexpr size_t +StateSize>::value; + +#if FOLLY_USE_SIMD_PRNG + +template +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 +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 +struct StateSize> { + // [rand.eng.sub]: r * ceil(w / 32) + static constexpr size_t value = r * ((w + 31) / 32); +}; + +template +constexpr size_t +StateSize>::value; + +template +std::seed_seq generateSeed() { + std::array::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 +void Random::seed(ValidRNG& rng) { + auto s = detail::generateSeed(); + rng.seed(s); +} + +template +auto Random::create() -> ValidRNG { + auto s = detail::generateSeed(); + return RNG(s); +} + +} // namespaces diff --git a/folly/Random.cpp b/folly/Random.cpp index a2c04df3..1398bd08 100644 --- a/folly/Random.cpp +++ b/folly/Random.cpp @@ -22,53 +22,91 @@ #include #include -#if __GNUC_PREREQ(4, 8) && !defined(ANDROID) -#include -#define USE_SIMD_PRNG -#endif +#include +#include "folly/File.h" +#include "folly/FileUtil.h" namespace folly { namespace { -std::atomic 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(getpid()) - + kPrime2 * static_cast(tv.tv_sec) - + kPrime3 * static_cast(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(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 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; + +} // namespace + +void Random::secureRandom(void* data, size_t size) { + bufferedRandomDevice->get(data, size); +} folly::ThreadLocalPtr 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 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() { diff --git a/folly/Random.h b/folly/Random.h index 5ce860a2..09cf7a17 100644 --- a/folly/Random.h +++ b/folly/Random.h @@ -14,21 +14,20 @@ * limitations under the License. */ -#ifndef FOLLY_BASE_RANDOM_H_ -#define FOLLY_BASE_RANDOM_H_ +#ifndef FOLLY_RANDOM_H_ +#define FOLLY_RANDOM_H_ +#include #include #include #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 +#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 @@ -83,7 +82,6 @@ class ThreadLocalPRNG { }; - class Random { private: @@ -93,13 +91,59 @@ class Random { 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 + static typename std::enable_if< + std::is_integral::value && !std::is_same::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 + static void seed(ValidRNG& 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 + static ValidRNG create(); /** * Returns a random uint32_t */ template - static uint32_t rand32(ValidRNG rrng = RNG()) { - uint32_t r = rrng.operator()(); + static uint32_t rand32(ValidRNG rng = RNG()) { + uint32_t r = rng.operator()(); return r; } @@ -197,6 +241,18 @@ class Random { }; +/* + * 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 diff --git a/folly/test/RandomTest.cpp b/folly/test/RandomTest.cpp index dee97698..e6f11f03 100644 --- a/folly/test/RandomTest.cpp +++ b/folly/test/RandomTest.cpp @@ -29,6 +29,19 @@ using namespace folly; +TEST(Random, StateSize) { + using namespace folly::detail; + + // uint_fast32_t is uint64_t on x86_64, w00t + EXPECT_EQ(sizeof(uint_fast32_t) / 4 + 3, + StateSize::value); + EXPECT_EQ(624, StateSize::value); +#if FOLLY_USE_SIMD_PRNG + EXPECT_EQ(624, StateSize<__gnu_cxx::sfmt19937>::value); +#endif + EXPECT_EQ(24, StateSize::value); +} + TEST(Random, Simple) { uint32_t prev = 0, seed = 0; for (int i = 0; i < 1024; ++i) { -- 2.34.1