diff options
24 files changed, 279 insertions, 300 deletions
diff --git a/src/mongo/bson/oid.cpp b/src/mongo/bson/oid.cpp index ebceefa04fa..0f08d6c56b6 100644 --- a/src/mongo/bson/oid.cpp +++ b/src/mongo/bson/oid.cpp @@ -54,9 +54,9 @@ OID::InstanceUnique _instanceUnique; MONGO_INITIALIZER_GENERAL(OIDGeneration, MONGO_NO_PREREQUISITES, ("default")) (InitializerContext* context) { - SecureRandom entropy; - counter = std::make_unique<AtomicWord<int64_t>>(entropy.nextInt64()); - _instanceUnique = OID::InstanceUnique::generate(entropy); + std::unique_ptr<SecureRandom> entropy(SecureRandom::create()); + counter = std::make_unique<AtomicWord<int64_t>>(entropy->nextInt64()); + _instanceUnique = OID::InstanceUnique::generate(*entropy); return Status::OK(); } @@ -72,8 +72,9 @@ OID::Increment OID::Increment::next() { } OID::InstanceUnique OID::InstanceUnique::generate(SecureRandom& entropy) { + int64_t rand = entropy.nextInt64(); OID::InstanceUnique u; - entropy.fill(u.bytes, kInstanceUniqueSize); + std::memcpy(u.bytes, &rand, kInstanceUniqueSize); return u; } @@ -118,8 +119,8 @@ size_t OID::Hasher::operator()(const OID& oid) const { } void OID::regenMachineId() { - SecureRandom entropy; - _instanceUnique = InstanceUnique::generate(entropy); + std::unique_ptr<SecureRandom> entropy(SecureRandom::create()); + _instanceUnique = InstanceUnique::generate(*entropy); } unsigned OID::getMachineId() { diff --git a/src/mongo/client/sasl_scram_client_conversation.cpp b/src/mongo/client/sasl_scram_client_conversation.cpp index 8947068f3da..c0f38495822 100644 --- a/src/mongo/client/sasl_scram_client_conversation.cpp +++ b/src/mongo/client/sasl_scram_client_conversation.cpp @@ -82,10 +82,14 @@ StatusWith<bool> SaslSCRAMClientConversation::_firstStep(std::string* outputData } // Create text-based nonce as base64 encoding of a binary blob of length multiple of 3 - static constexpr size_t nonceLenQWords = 3; + const int nonceLenQWords = 3; uint64_t binaryNonce[nonceLenQWords]; - SecureRandom().fill(binaryNonce, sizeof(binaryNonce)); + unique_ptr<SecureRandom> sr(SecureRandom::create()); + + binaryNonce[0] = sr->nextInt64(); + binaryNonce[1] = sr->nextInt64(); + binaryNonce[2] = sr->nextInt64(); std::string user = _saslClientSession->getParameter(SaslClientSession::parameterUser).toString(); diff --git a/src/mongo/crypto/mechanism_scram.h b/src/mongo/crypto/mechanism_scram.h index 5e0265679ea..fcb16331830 100644 --- a/src/mongo/crypto/mechanism_scram.h +++ b/src/mongo/crypto/mechanism_scram.h @@ -102,9 +102,15 @@ public: } static std::vector<std::uint8_t> generateSecureRandomSalt() { - std::vector<std::uint8_t> salt(saltLength()); - SecureRandom().fill(salt.data(), salt.size()); - return salt; + // Express salt length as a number of quad words, rounded up. + constexpr auto qwords = (saltLength() + sizeof(std::int64_t) - 1) / sizeof(std::int64_t); + std::array<std::int64_t, qwords> userSalt; + + std::unique_ptr<SecureRandom> sr(SecureRandom::create()); + std::generate(userSalt.begin(), userSalt.end(), [&sr] { return sr->nextInt64(); }); + return std::vector<std::uint8_t>(reinterpret_cast<std::uint8_t*>(userSalt.data()), + reinterpret_cast<std::uint8_t*>(userSalt.data()) + + saltLength()); } private: diff --git a/src/mongo/crypto/symmetric_crypto.cpp b/src/mongo/crypto/symmetric_crypto.cpp index 0a6bbc2e916..32d888cfbbb 100644 --- a/src/mongo/crypto/symmetric_crypto.cpp +++ b/src/mongo/crypto/symmetric_crypto.cpp @@ -48,7 +48,12 @@ namespace mongo { namespace crypto { +namespace { +std::unique_ptr<SecureRandom> random; +} // namespace + MONGO_INITIALIZER(CreateKeyEntropySource)(InitializerContext* context) { + random = std::unique_ptr<SecureRandom>(SecureRandom::create()); return Status::OK(); } @@ -85,8 +90,16 @@ std::string getStringFromCipherMode(aesMode mode) { SymmetricKey aesGenerate(size_t keySize, SymmetricKeyId keyId) { invariant(keySize == sym256KeySize); + SecureVector<uint8_t> key(keySize); - SecureRandom().fill(key->data(), key->size()); + + size_t offset = 0; + while (offset < keySize) { + std::uint64_t randomValue = random->nextInt64(); + memcpy(key->data() + offset, &randomValue, sizeof(randomValue)); + offset += sizeof(randomValue); + } + return SymmetricKey(std::move(key), aesAlgorithm, std::move(keyId)); } diff --git a/src/mongo/db/auth/sasl_scram_server_conversation.cpp b/src/mongo/db/auth/sasl_scram_server_conversation.cpp index 897d502533a..fc223097b4f 100644 --- a/src/mongo/db/auth/sasl_scram_server_conversation.cpp +++ b/src/mongo/db/auth/sasl_scram_server_conversation.cpp @@ -235,7 +235,11 @@ StatusWith<std::tuple<bool, std::string>> SaslSCRAMServerMechanism<Policy>::_fir const int nonceLenQWords = 3; uint64_t binaryNonce[nonceLenQWords]; - SecureRandom().fill(binaryNonce, sizeof(binaryNonce)); + std::unique_ptr<SecureRandom> sr(SecureRandom::create()); + + binaryNonce[0] = sr->nextInt64(); + binaryNonce[1] = sr->nextInt64(); + binaryNonce[2] = sr->nextInt64(); _nonce = clientNonce + base64::encode(reinterpret_cast<char*>(binaryNonce), sizeof(binaryNonce)); diff --git a/src/mongo/db/commands/authentication_commands.cpp b/src/mongo/db/commands/authentication_commands.cpp index dd273d77faa..5115bc9293d 100644 --- a/src/mongo/db/commands/authentication_commands.cpp +++ b/src/mongo/db/commands/authentication_commands.cpp @@ -201,7 +201,7 @@ private: */ class CmdGetNonce : public BasicCommand { public: - CmdGetNonce() : BasicCommand("getnonce") {} + CmdGetNonce() : BasicCommand("getnonce"), _random(SecureRandom::create()) {} AllowedOnSecondary secondaryAllowed(ServiceContext*) const override { return AllowedOnSecondary::kAlways; @@ -240,11 +240,11 @@ public: private: int64_t getNextNonce() { stdx::lock_guard<SimpleMutex> lk(_randMutex); - return _random.nextInt64(); + return _random->nextInt64(); } SimpleMutex _randMutex; // Synchronizes accesses to _random. - SecureRandom _random; + std::unique_ptr<SecureRandom> _random; } cmdGetNonce; bool CmdAuthenticate::run(OperationContext* opCtx, diff --git a/src/mongo/db/cursor_manager.cpp b/src/mongo/db/cursor_manager.cpp index b1ea5fd20ba..d2daf732184 100644 --- a/src/mongo/db/cursor_manager.cpp +++ b/src/mongo/db/cursor_manager.cpp @@ -100,7 +100,7 @@ std::pair<Status, int> CursorManager::killCursorsWithMatchingSessions( } CursorManager::CursorManager() - : _random(std::make_unique<PseudoRandom>(SecureRandom().nextInt64())), + : _random(std::make_unique<PseudoRandom>(SecureRandom::create()->nextInt64())), _cursorMap(std::make_unique<Partitioned<stdx::unordered_map<CursorId, ClientCursor*>>>()) {} CursorManager::~CursorManager() { diff --git a/src/mongo/db/db.cpp b/src/mongo/db/db.cpp index 64f6416f1ab..2b84068ac50 100644 --- a/src/mongo/db/db.cpp +++ b/src/mongo/db/db.cpp @@ -852,7 +852,7 @@ void setUpReplication(ServiceContext* serviceContext) { std::make_unique<repl::TopologyCoordinator>(topoCoordOptions), replicationProcess, storageInterface, - SecureRandom().nextInt64()); + SecureRandom::create()->nextInt64()); repl::ReplicationCoordinator::set(serviceContext, std::move(replCoord)); repl::setOplogCollectionName(serviceContext); diff --git a/src/mongo/db/repl/idempotency_test.cpp b/src/mongo/db/repl/idempotency_test.cpp index fb4e286122f..96143015561 100644 --- a/src/mongo/db/repl/idempotency_test.cpp +++ b/src/mongo/db/repl/idempotency_test.cpp @@ -165,7 +165,7 @@ void RandomizedIdempotencyTest::runIdempotencyTestCase() { const double kDocProbability = 0.375; const double kArrProbability = 0.0; - this->seed = SecureRandom().nextInt64(); + this->seed = SecureRandom::create()->nextInt64(); PseudoRandom seedGenerator(this->seed); RandomizedScalarGenerator scalarGenerator{PseudoRandom(seedGenerator.nextInt64())}; UpdateSequenceGenerator updateGenerator( diff --git a/src/mongo/db/repl/idempotency_update_sequence_test.cpp b/src/mongo/db/repl/idempotency_update_sequence_test.cpp index 6402d3ee95c..cace6b830b0 100644 --- a/src/mongo/db/repl/idempotency_update_sequence_test.cpp +++ b/src/mongo/db/repl/idempotency_update_sequence_test.cpp @@ -52,13 +52,12 @@ size_t getPathDepth_forTest(const std::string& path) { namespace { -PseudoRandom random(SecureRandom().nextInt64()); - TEST(UpdateGenTest, FindsAllPaths) { std::set<StringData> fields{"a", "b"}; size_t depth = 1; size_t length = 1; + PseudoRandom random(SecureRandom::create()->nextInt64()); TrivialScalarGenerator trivialScalarGenerator; UpdateSequenceGenerator generator({fields, depth, length}, random, &trivialScalarGenerator); @@ -90,6 +89,7 @@ TEST(UpdateGenTest, NoDuplicatePaths) { size_t depth = 2; size_t length = 2; + PseudoRandom random(SecureRandom::create()->nextInt64()); TrivialScalarGenerator trivialScalarGenerator; UpdateSequenceGenerator generator({fields, depth, length}, random, &trivialScalarGenerator); @@ -111,6 +111,7 @@ TEST(UpdateGenTest, UpdatesHaveValidPaths) { size_t depth = 1; size_t length = 1; + PseudoRandom random(SecureRandom::create()->nextInt64()); TrivialScalarGenerator trivialScalarGenerator; UpdateSequenceGenerator generator({fields, depth, length}, random, &trivialScalarGenerator); auto update = generator.generateUpdate(); @@ -149,6 +150,7 @@ TEST(UpdateGenTest, UpdatesAreNotAmbiguous) { size_t depth = 1; size_t length = 1; + PseudoRandom random(SecureRandom::create()->nextInt64()); TrivialScalarGenerator trivialScalarGenerator; UpdateSequenceGenerator generator({fields, depth, length}, random, &trivialScalarGenerator); auto update = generator.generateUpdate(); @@ -196,6 +198,7 @@ TEST(UpdateGenTest, UpdatesPreserveDepthConstraint) { size_t depth = 2; size_t length = 1; + PseudoRandom random(SecureRandom::create()->nextInt64()); TrivialScalarGenerator trivialScalarGenerator; UpdateSequenceGenerator generator( {fields, depth, length, 0.333, 0.333, 0.334}, random, &trivialScalarGenerator); @@ -232,6 +235,7 @@ TEST(UpdateGenTest, OnlyGenerateUnset) { size_t depth = 1; size_t length = 1; + PseudoRandom random(SecureRandom::create()->nextInt64()); TrivialScalarGenerator trivialScalarGenerator; UpdateSequenceGenerator generatorNoSet( {fields, depth, length, 0.0, 0.0, 0.0}, random, &trivialScalarGenerator); @@ -253,6 +257,7 @@ TEST(UpdateGenTest, OnlySetUpdatesWithScalarValue) { size_t depth = 1; size_t length = 1; + PseudoRandom random(SecureRandom::create()->nextInt64()); TrivialScalarGenerator trivialScalarGenerator; UpdateSequenceGenerator generatorNoUnsetAndOnlyScalar( {fields, depth, length, 1.0, 0.0, 0.0}, random, &trivialScalarGenerator); @@ -280,6 +285,7 @@ TEST(UpdateGenTest, OnlySetUpdatesWithScalarsAtMaxDepth) { size_t depth = 2; size_t length = 1; + PseudoRandom random(SecureRandom::create()->nextInt64()); TrivialScalarGenerator trivialScalarGenerator; UpdateSequenceGenerator generatorNeverScalar( {fields, depth, length, 0.0, 0.5, 0.5}, random, &trivialScalarGenerator); diff --git a/src/mongo/db/repl/replication_coordinator_impl.cpp b/src/mongo/db/repl/replication_coordinator_impl.cpp index 30aacb1f88e..7f38affaee1 100644 --- a/src/mongo/db/repl/replication_coordinator_impl.cpp +++ b/src/mongo/db/repl/replication_coordinator_impl.cpp @@ -167,13 +167,13 @@ void lockAndCall(stdx::unique_lock<Latch>* lk, const std::function<void()>& fn) */ BSONObj incrementConfigVersionByRandom(BSONObj config) { BSONObjBuilder builder; - SecureRandom generator; for (BSONObjIterator iter(config); iter.more(); iter.next()) { BSONElement elem = *iter; if (elem.fieldNameStringData() == ReplSetConfig::kVersionFieldName && elem.isNumber()) { - const int random = generator.nextInt32(100'000); + std::unique_ptr<SecureRandom> generator(SecureRandom::create()); + const int random = std::abs(static_cast<int>(generator->nextInt64()) % 100000); builder.appendIntOrLL(ReplSetConfig::kVersionFieldName, - elem.numberLong() + 10'000 + random); + elem.numberLong() + 10000 + random); } else { builder.append(elem); } diff --git a/src/mongo/db/s/session_catalog_migration_source.cpp b/src/mongo/db/s/session_catalog_migration_source.cpp index 56182591c96..15dd677e0ba 100644 --- a/src/mongo/db/s/session_catalog_migration_source.cpp +++ b/src/mongo/db/s/session_catalog_migration_source.cpp @@ -52,7 +52,7 @@ namespace mongo { namespace { -PseudoRandom hashGenerator(SecureRandom().nextInt64()); +PseudoRandom hashGenerator(std::unique_ptr<SecureRandom>(SecureRandom::create())->nextInt64()); boost::optional<repl::OplogEntry> fetchPrePostImageOplog(OperationContext* opCtx, const repl::OplogEntry& oplog) { diff --git a/src/mongo/db/storage/durable_catalog_impl.cpp b/src/mongo/db/storage/durable_catalog_impl.cpp index 0189a8d22b1..0bc79d049ba 100644 --- a/src/mongo/db/storage/durable_catalog_impl.cpp +++ b/src/mongo/db/storage/durable_catalog_impl.cpp @@ -397,7 +397,7 @@ DurableCatalogImpl::~DurableCatalogImpl() { } std::string DurableCatalogImpl::_newRand() { - return str::stream() << SecureRandom().nextInt64(); + return str::stream() << std::unique_ptr<SecureRandom>(SecureRandom::create())->nextInt64(); } bool DurableCatalogImpl::_hasEntryCollidingWithRand() const { diff --git a/src/mongo/db/time_proof_service.cpp b/src/mongo/db/time_proof_service.cpp index da65e441712..7e29f0b2254 100644 --- a/src/mongo/db/time_proof_service.cpp +++ b/src/mongo/db/time_proof_service.cpp @@ -45,9 +45,15 @@ namespace mongo { const uint64_t kRangeMask = 0x0000'0000'0000'FFFF; TimeProofService::Key TimeProofService::generateRandomKey() { - std::array<std::uint8_t, SHA1Block::kHashLength> keyBuffer; - SecureRandom().fill(keyBuffer.data(), keyBuffer.size()); - return fassert(40384, SHA1Block::fromBuffer(keyBuffer.data(), keyBuffer.size())); + // SecureRandom only produces 64-bit numbers, so 3 is the minimum for 20 random bytes. + const size_t kRandomNumbers = 3; + std::array<std::int64_t, kRandomNumbers> keyBuffer; + std::unique_ptr<SecureRandom> rng(SecureRandom::create()); + std::generate(keyBuffer.begin(), keyBuffer.end(), [&] { return rng->nextInt64(); }); + + return fassert(40384, + SHA1Block::fromBuffer(reinterpret_cast<std::uint8_t*>(keyBuffer.data()), + SHA1Block::kHashLength)); } TimeProofService::TimeProof TimeProofService::getProof(LogicalTime time, const Key& key) { diff --git a/src/mongo/platform/random.cpp b/src/mongo/platform/random.cpp index 9ed392adf1c..f12ffb57a5d 100644 --- a/src/mongo/platform/random.cpp +++ b/src/mongo/platform/random.cpp @@ -39,59 +39,75 @@ #include <bcrypt.h> #else #include <errno.h> -#include <fcntl.h> #endif #define _CRT_RAND_S -#include <array> #include <cstdlib> #include <fstream> #include <iostream> #include <limits> #include <memory> -#include <random> #include "mongo/util/assert_util.h" #include "mongo/util/log.h" -#ifdef _WIN32 -#define SECURE_RANDOM_BCRYPT -#elif defined(__linux__) || defined(__sun) || defined(__APPLE__) || defined(__FreeBSD__) || \ - defined(__EMSCRIPTEN__) -#define SECURE_RANDOM_URANDOM -#elif defined(__OpenBSD__) -#define SECURE_RANDOM_ARCFOUR -#else -#error "Must implement SecureRandom for platform" -#endif - namespace mongo { +// ---- PseudoRandom ----- + +uint32_t PseudoRandom::nextUInt32() { + uint32_t t = _x ^ (_x << 11); + _x = _y; + _y = _z; + _z = _w; + return _w = _w ^ (_w >> 19) ^ (t ^ (t >> 8)); +} + namespace { +const uint32_t default_y = 362436069; +const uint32_t default_z = 521288629; +const uint32_t default_w = 88675123; +} // namespace -template <size_t N> -struct Buffer { - uint64_t pop() { - return arr[--avail]; - } - uint8_t* fillPtr() { - return reinterpret_cast<uint8_t*>(arr.data() + avail); - } - size_t fillSize() { - return sizeof(uint64_t) * (arr.size() - avail); - } - void setFilled() { - avail = arr.size(); - } +PseudoRandom::PseudoRandom(uint32_t seed) { + _x = seed; + _y = default_y; + _z = default_z; + _w = default_w; +} - std::array<uint64_t, N> arr; - size_t avail = 0; -}; +PseudoRandom::PseudoRandom(int32_t seed) : PseudoRandom(static_cast<uint32_t>(seed)) {} + +PseudoRandom::PseudoRandom(int64_t seed) + : PseudoRandom(static_cast<uint32_t>(seed >> 32) ^ static_cast<uint32_t>(seed)) {} + +int32_t PseudoRandom::nextInt32() { + return nextUInt32(); +} + +int64_t PseudoRandom::nextInt64() { + uint64_t a = nextUInt32(); + uint64_t b = nextUInt32(); + return (a << 32) | b; +} + +double PseudoRandom::nextCanonicalDouble() { + double result; + do { + auto generated = static_cast<uint64_t>(nextInt64()); + result = static_cast<double>(generated) / std::numeric_limits<uint64_t>::max(); + } while (result == 1.0); + return result; +} + +// --- SecureRandom ---- -#if defined(SECURE_RANDOM_BCRYPT) -class Source { +SecureRandom::~SecureRandom() {} + +#ifdef _WIN32 +class WinSecureRandom : public SecureRandom { public: - Source() { + WinSecureRandom() { auto ntstatus = ::BCryptOpenAlgorithmProvider( &_algHandle, BCRYPT_RNG_ALGORITHM, MS_PRIMITIVE_PROVIDER, 0); if (ntstatus != STATUS_SUCCESS) { @@ -102,7 +118,7 @@ public: } } - ~Source() { + virtual ~WinSecureRandom() { auto ntstatus = ::BCryptCloseAlgorithmProvider(_algHandle, 0); if (ntstatus != STATUS_SUCCESS) { warning() << "Failed to close crypto algorithm provider destroying secure random " @@ -111,99 +127,75 @@ public: } } - size_t refill(uint8_t* buf, size_t n) { - auto ntstatus = ::BCryptGenRandom(_algHandle, reinterpret_cast<PUCHAR>(buf), n, 0); + int64_t nextInt64() { + int64_t value; + auto ntstatus = + ::BCryptGenRandom(_algHandle, reinterpret_cast<PUCHAR>(&value), sizeof(value), 0); if (ntstatus != STATUS_SUCCESS) { error() << "Failed to generate random number from secure random object; NTSTATUS: " << ntstatus; fassertFailed(28814); } - return n; + return value; } private: BCRYPT_ALG_HANDLE _algHandle; }; -#endif // SECURE_RANDOM_BCRYPT -#if defined(SECURE_RANDOM_URANDOM) -class Source { +std::unique_ptr<SecureRandom> SecureRandom::create() { + return std::make_unique<WinSecureRandom>(); +} + +#elif defined(__linux__) || defined(__sun) || defined(__APPLE__) || defined(__FreeBSD__) || \ + defined(__EMSCRIPTEN__) + +class InputStreamSecureRandom : public SecureRandom { public: - size_t refill(uint8_t* buf, size_t n) { - size_t i = 0; - while (i < n) { - ssize_t r; - while ((r = read(sharedFd(), buf + i, n - i)) == -1) { - if (errno == EINTR) { - continue; - } else { - auto errSave = errno; - error() << "SecureRandom: read `" << kFn << "`: " << strerror(errSave); - fassertFailed(28840); - } - } - i += r; + InputStreamSecureRandom(const char* fn) { + _in = std::make_unique<std::ifstream>(fn, std::ios::binary | std::ios::in); + if (!_in->is_open()) { + error() << "cannot open " << fn << " " << strerror(errno); + fassertFailed(28839); } - return i; } -private: - static constexpr const char* kFn = "/dev/urandom"; - static int sharedFd() { - // Retain the urandom fd forever. - // Kernel ensures that concurrent `read` calls don't mingle their data. - // http://lkml.iu.edu//hypermail/linux/kernel/0412.1/0181.html - static const int fd = [] { - int f; - while ((f = open(kFn, 0)) == -1) { - if (errno == EINTR) { - continue; - } else { - auto errSave = errno; - error() << "SecureRandom: open `" << kFn << "`: " << strerror(errSave); - fassertFailed(28839); - } - } - return f; - }(); - return fd; + int64_t nextInt64() { + int64_t r; + _in->read(reinterpret_cast<char*>(&r), sizeof(r)); + if (_in->fail()) { + error() << "InputStreamSecureRandom failed to generate random bytes"; + fassertFailed(28840); + } + return r; } -}; -#endif // SECURE_RANDOM_URANDOM -#if defined(SECURE_RANDOM_ARCFOUR) -class Source { -public: - size_t refill(uint8_t* buf, size_t n) { - arc4random_buf(buf, n); - return n; - } +private: + std::unique_ptr<std::ifstream> _in; }; -#endif // SECURE_RANDOM_ARCFOUR -} // namespace +std::unique_ptr<SecureRandom> SecureRandom::create() { + return std::make_unique<InputStreamSecureRandom>("/dev/urandom"); +} -class SecureUrbg::State { +#elif defined(__OpenBSD__) + +class Arc4SecureRandom : public SecureRandom { public: - uint64_t get() { - if (!_buffer.avail) { - size_t n = _source.refill(_buffer.fillPtr(), _buffer.fillSize()); - _buffer.avail += n / sizeof(uint64_t); - } - return _buffer.pop(); + int64_t nextInt64() { + int64_t value; + arc4random_buf(&value, sizeof(value)); + return value; } - -private: - Source _source; - Buffer<16> _buffer; }; -SecureUrbg::SecureUrbg() : _state{std::make_unique<State>()} {} +std::unique_ptr<SecureRandom> SecureRandom::create() { + return std::make_unique<Arc4SecureRandom>(); +} -SecureUrbg::~SecureUrbg() = default; +#else -uint64_t SecureUrbg::operator()() { - return _state->get(); -} +#error Must implement SecureRandom for platform +#endif } // namespace mongo diff --git a/src/mongo/platform/random.h b/src/mongo/platform/random.h index 3521399c896..6ef2a9bf114 100644 --- a/src/mongo/platform/random.h +++ b/src/mongo/platform/random.h @@ -29,142 +29,86 @@ #pragma once -#include <algorithm> #include <cstdint> -#include <cstring> #include <limits> #include <memory> -#include <random> namespace mongo { /** - * A uniform random bit generator based on XorShift. * Uses http://en.wikipedia.org/wiki/Xorshift */ -class XorShift128 { +class PseudoRandom { public: - using result_type = uint32_t; + PseudoRandom(int32_t seed); - static constexpr result_type min() { - return std::numeric_limits<result_type>::lowest(); - } + PseudoRandom(uint32_t seed); - static constexpr result_type max() { - return std::numeric_limits<result_type>::max(); - } + PseudoRandom(int64_t seed); - explicit XorShift128(uint32_t seed) : _x{seed} {} + int32_t nextInt32(); - result_type operator()() { - uint32_t t = _x ^ (_x << 11); - _x = _y; - _y = _z; - _z = _w; - return _w = _w ^ (_w >> 19) ^ (t ^ (t >> 8)); - } + int64_t nextInt64(); -private: - uint32_t _x; // seed - uint32_t _y = 362436069; - uint32_t _z = 521288629; - uint32_t _w = 88675123; -}; + /** + * Returns a random number in the range [0, 1). + */ + double nextCanonicalDouble(); -/** The SecureUrbg impls all produce the full range of uint64_t. */ -class SecureUrbg { -public: - using result_type = uint64_t; - static constexpr result_type min() { - return std::numeric_limits<result_type>::lowest(); - } - static constexpr result_type max() { - return std::numeric_limits<result_type>::max(); + /** + * @return a number between 0 and max + */ + int32_t nextInt32(int32_t max) { + return static_cast<uint32_t>(nextInt32()) % static_cast<uint32_t>(max); } - // Details including State vary by platform and are deferred to the .cpp file. - SecureUrbg(); - ~SecureUrbg(); - result_type operator()(); - -private: - class State; - std::unique_ptr<State> _state; -}; - -// Provides mongo-traditional functions around a pluggable UniformRandomBitGenerator. -template <typename Urbg> -class RandomBase { -public: - using urbg_type = Urbg; + /** + * @return a number between 0 and max + */ + int64_t nextInt64(int64_t max) { + return static_cast<uint64_t>(nextInt64()) % static_cast<uint64_t>(max); + } - RandomBase() : _urbg{} {} - explicit RandomBase(urbg_type u) : _urbg{std::move(u)} {} + /** + * This returns an object that adapts PseudoRandom such that it + * can be used as the third argument to std::shuffle. Note that + * the lifetime of the returned object must be a subset of the + * lifetime of the PseudoRandom object. + */ + auto urbg() { - /** The underlying generator */ - urbg_type& urbg() { - return _urbg; - } + class URBG { + public: + explicit URBG(PseudoRandom* impl) : _impl(impl) {} - /** A random number in the range [0, 1). */ - double nextCanonicalDouble() { - return std::uniform_real_distribution<double>{0, 1}(_urbg); - } + using result_type = uint64_t; - /** A number uniformly distributed over all possible values. */ - int32_t nextInt32() { - return _nextAny<int32_t>(); - } + static constexpr result_type min() { + return std::numeric_limits<result_type>::min(); + } - /** A number uniformly distributed over all possible values. */ - int64_t nextInt64() { - return _nextAny<int64_t>(); - } + static constexpr result_type max() { + return std::numeric_limits<result_type>::max(); + } - /** A number in the half-open interval [0, max) */ - int32_t nextInt32(int32_t max) { - return std::uniform_int_distribution<int32_t>(0, max - 1)(_urbg); - } + result_type operator()() { + return _impl->nextInt64(); + } - /** A number in the half-open interval [0, max) */ - int64_t nextInt64(int64_t max) { - return std::uniform_int_distribution<int64_t>(0, max - 1)(_urbg); - } + private: + PseudoRandom* _impl; + }; - /** Fill array `buf` with `n` random bytes. */ - void fill(void* buf, size_t n) { - const auto p = static_cast<uint8_t*>(buf); - size_t written = 0; - while (written < n) { - uint64_t t = nextInt64(); - size_t w = std::min(n - written, sizeof(t)); - std::memcpy(p + written, &t, w); - written += w; - } + return URBG(this); } private: - template <typename T> - T _nextAny() { - using Limits = std::numeric_limits<T>; - return std::uniform_int_distribution<T>(Limits::lowest(), Limits::max())(_urbg); - } + uint32_t nextUInt32(); - urbg_type _urbg; -}; - -/** - * A Pseudorandom generator that's not cryptographically secure, but very fast and small. - */ -class PseudoRandom : public RandomBase<XorShift128> { - using Base = RandomBase<XorShift128>; - -public: - explicit PseudoRandom(uint32_t seed) : Base{XorShift128{seed}} {} - explicit PseudoRandom(int32_t seed) : PseudoRandom{static_cast<uint32_t>(seed)} {} - explicit PseudoRandom(uint64_t seed) - : PseudoRandom{static_cast<uint32_t>(seed ^ (seed >> 32))} {} - explicit PseudoRandom(int64_t seed) : PseudoRandom{static_cast<uint64_t>(seed)} {} + uint32_t _x; + uint32_t _y; + uint32_t _z; + uint32_t _w; }; /** @@ -172,11 +116,12 @@ public: * Suitable for nonce/crypto * Slower than PseudoRandom, so only use when really need */ -class SecureRandom : public RandomBase<SecureUrbg> { - using Base = RandomBase<SecureUrbg>; - +class SecureRandom { public: - using Base::Base; -}; + virtual ~SecureRandom(); + virtual int64_t nextInt64() = 0; + + static std::unique_ptr<SecureRandom> create(); +}; } // namespace mongo diff --git a/src/mongo/platform/random_test.cpp b/src/mongo/platform/random_test.cpp index c3271f8b926..ee82a89490f 100644 --- a/src/mongo/platform/random_test.cpp +++ b/src/mongo/platform/random_test.cpp @@ -134,13 +134,13 @@ TEST(RandomTest, NextCanonicalDistinctValues) { } /** - * Test that nextCanonicalDouble() is at least very likely to return values in [0,1). + * Test that nextCanonicalDouble() always returns values between 0 and 1. */ TEST(RandomTest, NextCanonicalWithinRange) { PseudoRandom prng(10); - for (size_t i = 0; i < 1'000'000; ++i) { + for (int i = 0; i < 100; i++) { double next = prng.nextCanonicalDouble(); - ASSERT_GTE(next, 0.0); + ASSERT_LTE(0.0, next); ASSERT_LT(next, 1.0); } } @@ -211,47 +211,12 @@ TEST(RandomTest, NextInt64InRange) { } } -/** - * Test uniformity of nextInt32(max) - */ -TEST(RandomTest, NextInt32Uniformity) { - PseudoRandom prng(10); - /* Break the range into sections. */ - /* Check that all sections get roughly equal # of hits */ - constexpr int32_t kMax = (int32_t{3} << 29) - 1; - constexpr size_t kBuckets = 64; - constexpr size_t kNIter = 1'000'000; - constexpr double mu = kNIter / kBuckets; - constexpr double muSqInv = 1. / (mu * mu); - std::vector<size_t> hist(kBuckets); - for (size_t i = 0; i < kNIter; ++i) { - auto next = prng.nextInt32(kMax); - ASSERT_GTE(next, 0); - ASSERT_LTE(next, kMax); - ++hist[double(next) * kBuckets / (kMax + 1)]; - } - if (kDebugBuild) { - for (size_t i = 0; i < hist.size(); ++i) { - double dev = std::pow(std::pow((hist[i] - mu) / mu, 2), .5); - unittest::log() << format(FMT_STRING(" [{:4}] count:{:4}, dev:{:6f}, {}"), - i, - hist[i], - dev, - std::string(hist[i] / 256, '*')); - } - } - for (size_t i = 0; i < hist.size(); ++i) { - double dev = std::pow(std::pow(hist[i] - mu, 2) * muSqInv, .5); - ASSERT_LT(dev, 0.1) << format(FMT_STRING("hist[{}]={}, mu={}"), i, hist[i], mu); - } -} - TEST(RandomTest, Secure1) { - auto a = SecureRandom(); - auto b = SecureRandom(); + auto a = SecureRandom::create(); + auto b = SecureRandom::create(); for (int i = 0; i < 100; i++) { - ASSERT_NOT_EQUALS(a.nextInt64(), b.nextInt64()); + ASSERT_NOT_EQUALS(a->nextInt64(), b->nextInt64()); } } } // namespace mongo diff --git a/src/mongo/s/query/cluster_cursor_manager.cpp b/src/mongo/s/query/cluster_cursor_manager.cpp index 56dd270a742..03dfd1114f5 100644 --- a/src/mongo/s/query/cluster_cursor_manager.cpp +++ b/src/mongo/s/query/cluster_cursor_manager.cpp @@ -148,7 +148,8 @@ void ClusterCursorManager::PinnedCursor::returnAndKillCursor() { } ClusterCursorManager::ClusterCursorManager(ClockSource* clockSource) - : _clockSource(clockSource), _pseudoRandom(SecureRandom().nextInt64()) { + : _clockSource(clockSource), + _pseudoRandom(std::unique_ptr<SecureRandom>(SecureRandom::create())->nextInt64()) { invariant(_clockSource); } diff --git a/src/mongo/s/sharding_initialization.cpp b/src/mongo/s/sharding_initialization.cpp index 8f4285e26e9..83ebcdfdda0 100644 --- a/src/mongo/s/sharding_initialization.cpp +++ b/src/mongo/s/sharding_initialization.cpp @@ -152,11 +152,13 @@ std::unique_ptr<executor::TaskExecutor> makeShardingTaskExecutor( } std::string generateDistLockProcessId(OperationContext* opCtx) { + std::unique_ptr<SecureRandom> rng(SecureRandom::create()); + return str::stream() << HostAndPort(getHostName(), serverGlobalParams.port).toString() << ':' << durationCount<Seconds>( opCtx->getServiceContext()->getPreciseClockSource()->now().toDurationSinceEpoch()) - << ':' << SecureRandom().nextInt64(); + << ':' << rng->nextInt64(); } Status initializeGlobalShardingState(OperationContext* opCtx, diff --git a/src/mongo/shell/shell_utils.cpp b/src/mongo/shell/shell_utils.cpp index d8568cb72d3..fc9f9e4d420 100644 --- a/src/mongo/shell/shell_utils.cpp +++ b/src/mongo/shell/shell_utils.cpp @@ -311,7 +311,8 @@ BSONObj JSSrand(const BSONObj& a, void* data) { if (a.nFields() == 1 && a.firstElement().isNumber()) seed = static_cast<unsigned int>(a.firstElement().numberLong()); else { - seed = static_cast<unsigned int>(SecureRandom().nextInt64()); + std::unique_ptr<SecureRandom> rand(SecureRandom::create()); + seed = static_cast<unsigned int>(rand->nextInt64()); } _prng = PseudoRandom(seed); return BSON("" << static_cast<double>(seed)); diff --git a/src/mongo/tools/mongobridge_options.cpp b/src/mongo/tools/mongobridge_options.cpp index 81a116df714..79d27417659 100644 --- a/src/mongo/tools/mongobridge_options.cpp +++ b/src/mongo/tools/mongobridge_options.cpp @@ -70,7 +70,8 @@ Status storeMongoBridgeOptions(const moe::Environment& params, } if (!params.count("seed")) { - mongoBridgeGlobalParams.seed = SecureRandom().nextInt64(); + std::unique_ptr<SecureRandom> seedSource{SecureRandom::create()}; + mongoBridgeGlobalParams.seed = seedSource->nextInt64(); } else { mongoBridgeGlobalParams.seed = static_cast<int64_t>(params["seed"].as<long>()); } diff --git a/src/mongo/tools/mongoebench_options.cpp b/src/mongo/tools/mongoebench_options.cpp index f2982ee028a..0ba4394d976 100644 --- a/src/mongo/tools/mongoebench_options.cpp +++ b/src/mongo/tools/mongoebench_options.cpp @@ -94,7 +94,7 @@ Status storeMongoeBenchOptions(const moe::Environment& params, } int64_t seed = params.count("seed") ? static_cast<int64_t>(params["seed"].as<long>()) - : SecureRandom().nextInt64(); + : SecureRandom::create()->nextInt64(); if (mongoeBenchGlobalParams.preConfig) { mongoeBenchGlobalParams.preConfig->randomSeed = seed; diff --git a/src/mongo/util/fail_point.cpp b/src/mongo/util/fail_point.cpp index 52e0e12b949..389a809ef23 100644 --- a/src/mongo/util/fail_point.cpp +++ b/src/mongo/util/fail_point.cpp @@ -31,9 +31,7 @@ #include "mongo/util/fail_point.h" -#include <limits> #include <memory> -#include <random> #include "mongo/bson/util/bson_extract.h" #include "mongo/platform/random.h" @@ -45,12 +43,39 @@ namespace mongo { namespace { -/** The per-thread PRNG used by fail-points. */ -thread_local PseudoRandom threadPrng{SecureRandom().nextInt64()}; + +/** + * Type representing the per-thread PRNG used by fail-points. + */ +class FailPointPRNG { +public: + FailPointPRNG() : _prng(std::unique_ptr<SecureRandom>(SecureRandom::create())->nextInt64()) {} + + void resetSeed(int32_t seed) { + _prng = PseudoRandom(seed); + } + + int32_t nextPositiveInt32() { + return _prng.nextInt32() & ~(1 << 31); + } + + static FailPointPRNG* current() { + if (!_failPointPrng) + _failPointPrng = std::make_unique<FailPointPRNG>(); + return _failPointPrng.get(); + } + +private: + PseudoRandom _prng; + static thread_local std::unique_ptr<FailPointPRNG> _failPointPrng; +}; + +thread_local std::unique_ptr<FailPointPRNG> FailPointPRNG::_failPointPrng; + } // namespace void FailPoint::setThreadPRNGSeed(int32_t seed) { - threadPrng = PseudoRandom(seed); + FailPointPRNG::current()->resetSeed(seed); } FailPoint::FailPoint() = default; @@ -116,10 +141,10 @@ FailPoint::RetCode FailPoint::slowShouldFailOpenBlock( case alwaysOn: return slowOn; case random: { - std::uniform_int_distribution<int> distribution{}; - if (distribution(threadPrng.urbg()) < _timesOrPeriod.load()) { + const int maxActivationValue = _timesOrPeriod.load(); + if (FailPointPRNG::current()->nextPositiveInt32() < maxActivationValue) return slowOn; - } + return slowOff; } case nTimes: { diff --git a/src/mongo/util/uuid.cpp b/src/mongo/util/uuid.cpp index 63ca7bc1e2d..d729777cf30 100644 --- a/src/mongo/util/uuid.cpp +++ b/src/mongo/util/uuid.cpp @@ -43,7 +43,7 @@ namespace mongo { namespace { Mutex uuidGenMutex; -SecureRandom uuidGen; +auto uuidGen = SecureRandom::create(); // Regex to match valid version 4 UUIDs with variant bits set std::regex uuidRegex("[0-9a-fA-F]{8}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{12}", @@ -97,12 +97,19 @@ bool UUID::isRFC4122v4() const { } UUID UUID::gen() { - UUIDStorage randomBytes; + int64_t randomWords[2]; + { stdx::lock_guard<Latch> lk(uuidGenMutex); - uuidGen.fill(&randomBytes, sizeof(randomBytes)); + + // Generate 128 random bits + randomWords[0] = uuidGen->nextInt64(); + randomWords[1] = uuidGen->nextInt64(); } + UUIDStorage randomBytes; + memcpy(&randomBytes, randomWords, sizeof(randomBytes)); + // Set version in high 4 bits of byte 6 and variant in high 2 bits of byte 8, see RFC 4122, // section 4.1.1, 4.1.2 and 4.1.3. randomBytes[6] &= 0x0f; |