From e1f433d2c47f623ceb5d1d1aee7605fefb71b846 Mon Sep 17 00:00:00 2001 From: Billy Donahue Date: Wed, 9 Oct 2019 17:09:10 +0000 Subject: SERVER-43641 upgrade random.h This reverts commit a40b196bd3cecd0b66a6323f57e6f08efe0af392. --- src/mongo/bson/oid.cpp | 13 +- .../client/sasl_scram_client_conversation.cpp | 8 +- src/mongo/crypto/mechanism_scram.h | 12 +- src/mongo/crypto/symmetric_crypto.cpp | 15 +- .../db/auth/sasl_scram_server_conversation.cpp | 6 +- src/mongo/db/commands/authentication_commands.cpp | 6 +- src/mongo/db/cursor_manager.cpp | 2 +- src/mongo/db/db.cpp | 2 +- src/mongo/db/free_mon/free_mon_controller_test.cpp | 2 +- src/mongo/db/repl/idempotency_test.cpp | 2 +- .../db/repl/idempotency_update_sequence_test.cpp | 10 +- src/mongo/db/repl/replication_coordinator_impl.cpp | 6 +- .../db/s/session_catalog_migration_source.cpp | 2 +- src/mongo/db/storage/durable_catalog_impl.cpp | 2 +- src/mongo/db/time_proof_service.cpp | 12 +- src/mongo/platform/random.cpp | 198 +++++++++++---------- src/mongo/platform/random.h | 167 +++++++++++------ src/mongo/platform/random_test.cpp | 47 ++++- src/mongo/s/query/cluster_cursor_manager.cpp | 3 +- src/mongo/s/sharding_initialization.cpp | 4 +- src/mongo/shell/shell_utils.cpp | 3 +- src/mongo/tools/mongobridge_options.cpp | 3 +- src/mongo/tools/mongoebench_options.cpp | 2 +- src/mongo/util/fail_point.cpp | 40 +---- src/mongo/util/uuid.cpp | 13 +- 25 files changed, 302 insertions(+), 278 deletions(-) diff --git a/src/mongo/bson/oid.cpp b/src/mongo/bson/oid.cpp index 0f08d6c56b6..ebceefa04fa 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) { - std::unique_ptr entropy(SecureRandom::create()); - counter = std::make_unique>(entropy->nextInt64()); - _instanceUnique = OID::InstanceUnique::generate(*entropy); + SecureRandom entropy; + counter = std::make_unique>(entropy.nextInt64()); + _instanceUnique = OID::InstanceUnique::generate(entropy); return Status::OK(); } @@ -72,9 +72,8 @@ OID::Increment OID::Increment::next() { } OID::InstanceUnique OID::InstanceUnique::generate(SecureRandom& entropy) { - int64_t rand = entropy.nextInt64(); OID::InstanceUnique u; - std::memcpy(u.bytes, &rand, kInstanceUniqueSize); + entropy.fill(u.bytes, kInstanceUniqueSize); return u; } @@ -119,8 +118,8 @@ size_t OID::Hasher::operator()(const OID& oid) const { } void OID::regenMachineId() { - std::unique_ptr entropy(SecureRandom::create()); - _instanceUnique = InstanceUnique::generate(*entropy); + SecureRandom entropy; + _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 c0f38495822..8947068f3da 100644 --- a/src/mongo/client/sasl_scram_client_conversation.cpp +++ b/src/mongo/client/sasl_scram_client_conversation.cpp @@ -82,14 +82,10 @@ StatusWith SaslSCRAMClientConversation::_firstStep(std::string* outputData } // Create text-based nonce as base64 encoding of a binary blob of length multiple of 3 - const int nonceLenQWords = 3; + static constexpr size_t nonceLenQWords = 3; uint64_t binaryNonce[nonceLenQWords]; - unique_ptr sr(SecureRandom::create()); - - binaryNonce[0] = sr->nextInt64(); - binaryNonce[1] = sr->nextInt64(); - binaryNonce[2] = sr->nextInt64(); + SecureRandom().fill(binaryNonce, sizeof(binaryNonce)); 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 fcb16331830..5e0265679ea 100644 --- a/src/mongo/crypto/mechanism_scram.h +++ b/src/mongo/crypto/mechanism_scram.h @@ -102,15 +102,9 @@ public: } static std::vector generateSecureRandomSalt() { - // 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 userSalt; - - std::unique_ptr sr(SecureRandom::create()); - std::generate(userSalt.begin(), userSalt.end(), [&sr] { return sr->nextInt64(); }); - return std::vector(reinterpret_cast(userSalt.data()), - reinterpret_cast(userSalt.data()) + - saltLength()); + std::vector salt(saltLength()); + SecureRandom().fill(salt.data(), salt.size()); + return salt; } private: diff --git a/src/mongo/crypto/symmetric_crypto.cpp b/src/mongo/crypto/symmetric_crypto.cpp index 32d888cfbbb..0a6bbc2e916 100644 --- a/src/mongo/crypto/symmetric_crypto.cpp +++ b/src/mongo/crypto/symmetric_crypto.cpp @@ -48,12 +48,7 @@ namespace mongo { namespace crypto { -namespace { -std::unique_ptr random; -} // namespace - MONGO_INITIALIZER(CreateKeyEntropySource)(InitializerContext* context) { - random = std::unique_ptr(SecureRandom::create()); return Status::OK(); } @@ -90,16 +85,8 @@ std::string getStringFromCipherMode(aesMode mode) { SymmetricKey aesGenerate(size_t keySize, SymmetricKeyId keyId) { invariant(keySize == sym256KeySize); - SecureVector key(keySize); - - size_t offset = 0; - while (offset < keySize) { - std::uint64_t randomValue = random->nextInt64(); - memcpy(key->data() + offset, &randomValue, sizeof(randomValue)); - offset += sizeof(randomValue); - } - + SecureRandom().fill(key->data(), key->size()); 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 fc223097b4f..897d502533a 100644 --- a/src/mongo/db/auth/sasl_scram_server_conversation.cpp +++ b/src/mongo/db/auth/sasl_scram_server_conversation.cpp @@ -235,11 +235,7 @@ StatusWith> SaslSCRAMServerMechanism::_fir const int nonceLenQWords = 3; uint64_t binaryNonce[nonceLenQWords]; - std::unique_ptr sr(SecureRandom::create()); - - binaryNonce[0] = sr->nextInt64(); - binaryNonce[1] = sr->nextInt64(); - binaryNonce[2] = sr->nextInt64(); + SecureRandom().fill(binaryNonce, sizeof(binaryNonce)); _nonce = clientNonce + base64::encode(reinterpret_cast(binaryNonce), sizeof(binaryNonce)); diff --git a/src/mongo/db/commands/authentication_commands.cpp b/src/mongo/db/commands/authentication_commands.cpp index 5115bc9293d..dd273d77faa 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"), _random(SecureRandom::create()) {} + CmdGetNonce() : BasicCommand("getnonce") {} AllowedOnSecondary secondaryAllowed(ServiceContext*) const override { return AllowedOnSecondary::kAlways; @@ -240,11 +240,11 @@ public: private: int64_t getNextNonce() { stdx::lock_guard lk(_randMutex); - return _random->nextInt64(); + return _random.nextInt64(); } SimpleMutex _randMutex; // Synchronizes accesses to _random. - std::unique_ptr _random; + 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 d2daf732184..b1ea5fd20ba 100644 --- a/src/mongo/db/cursor_manager.cpp +++ b/src/mongo/db/cursor_manager.cpp @@ -100,7 +100,7 @@ std::pair CursorManager::killCursorsWithMatchingSessions( } CursorManager::CursorManager() - : _random(std::make_unique(SecureRandom::create()->nextInt64())), + : _random(std::make_unique(SecureRandom().nextInt64())), _cursorMap(std::make_unique>>()) {} CursorManager::~CursorManager() { diff --git a/src/mongo/db/db.cpp b/src/mongo/db/db.cpp index 2dc91c831d8..269304be6e3 100644 --- a/src/mongo/db/db.cpp +++ b/src/mongo/db/db.cpp @@ -852,7 +852,7 @@ void setUpReplication(ServiceContext* serviceContext) { std::make_unique(topoCoordOptions), replicationProcess, storageInterface, - SecureRandom::create()->nextInt64()); + SecureRandom().nextInt64()); repl::ReplicationCoordinator::set(serviceContext, std::move(replCoord)); repl::setOplogCollectionName(serviceContext); diff --git a/src/mongo/db/free_mon/free_mon_controller_test.cpp b/src/mongo/db/free_mon/free_mon_controller_test.cpp index 13939a35142..296b3700b93 100644 --- a/src/mongo/db/free_mon/free_mon_controller_test.cpp +++ b/src/mongo/db/free_mon/free_mon_controller_test.cpp @@ -74,7 +74,7 @@ namespace mongo { namespace { auto makeRandom() { - auto seed = SecureRandom::create()->nextInt64(); + auto seed = SecureRandom().nextInt64(); unittest::log() << "PseudoRandom(" << std::showbase << std::hex << seed << std::dec << std::noshowbase << ")"; return PseudoRandom(seed); diff --git a/src/mongo/db/repl/idempotency_test.cpp b/src/mongo/db/repl/idempotency_test.cpp index 34fe562c2c8..4eacc99fb52 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::create()->nextInt64(); + this->seed = SecureRandom().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 cace6b830b0..6402d3ee95c 100644 --- a/src/mongo/db/repl/idempotency_update_sequence_test.cpp +++ b/src/mongo/db/repl/idempotency_update_sequence_test.cpp @@ -52,12 +52,13 @@ size_t getPathDepth_forTest(const std::string& path) { namespace { +PseudoRandom random(SecureRandom().nextInt64()); + TEST(UpdateGenTest, FindsAllPaths) { std::set 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); @@ -89,7 +90,6 @@ 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,7 +111,6 @@ 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(); @@ -150,7 +149,6 @@ 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(); @@ -198,7 +196,6 @@ 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); @@ -235,7 +232,6 @@ 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); @@ -257,7 +253,6 @@ 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); @@ -285,7 +280,6 @@ 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 3eba44e99a7..4b796ccd2ee 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* lk, const std::function& 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()) { - std::unique_ptr generator(SecureRandom::create()); - const int random = std::abs(static_cast(generator->nextInt64()) % 100000); + const int random = generator.nextInt32(100'000); builder.appendIntOrLL(ReplSetConfig::kVersionFieldName, - elem.numberLong() + 10000 + random); + elem.numberLong() + 10'000 + 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 15dd677e0ba..56182591c96 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(std::unique_ptr(SecureRandom::create())->nextInt64()); +PseudoRandom hashGenerator(SecureRandom().nextInt64()); boost::optional 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 0bc79d049ba..0189a8d22b1 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() << std::unique_ptr(SecureRandom::create())->nextInt64(); + return str::stream() << SecureRandom().nextInt64(); } bool DurableCatalogImpl::_hasEntryCollidingWithRand() const { diff --git a/src/mongo/db/time_proof_service.cpp b/src/mongo/db/time_proof_service.cpp index 7e29f0b2254..da65e441712 100644 --- a/src/mongo/db/time_proof_service.cpp +++ b/src/mongo/db/time_proof_service.cpp @@ -45,15 +45,9 @@ namespace mongo { const uint64_t kRangeMask = 0x0000'0000'0000'FFFF; TimeProofService::Key TimeProofService::generateRandomKey() { - // SecureRandom only produces 64-bit numbers, so 3 is the minimum for 20 random bytes. - const size_t kRandomNumbers = 3; - std::array keyBuffer; - std::unique_ptr rng(SecureRandom::create()); - std::generate(keyBuffer.begin(), keyBuffer.end(), [&] { return rng->nextInt64(); }); - - return fassert(40384, - SHA1Block::fromBuffer(reinterpret_cast(keyBuffer.data()), - SHA1Block::kHashLength)); + std::array keyBuffer; + SecureRandom().fill(keyBuffer.data(), keyBuffer.size()); + return fassert(40384, SHA1Block::fromBuffer(keyBuffer.data(), keyBuffer.size())); } TimeProofService::TimeProof TimeProofService::getProof(LogicalTime time, const Key& key) { diff --git a/src/mongo/platform/random.cpp b/src/mongo/platform/random.cpp index f12ffb57a5d..9ed392adf1c 100644 --- a/src/mongo/platform/random.cpp +++ b/src/mongo/platform/random.cpp @@ -39,75 +39,59 @@ #include #else #include +#include #endif #define _CRT_RAND_S +#include #include #include #include #include #include +#include #include "mongo/util/assert_util.h" #include "mongo/util/log.h" -namespace mongo { - -// ---- PseudoRandom ----- +#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 -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 mongo { namespace { -const uint32_t default_y = 362436069; -const uint32_t default_z = 521288629; -const uint32_t default_w = 88675123; -} // namespace - -PseudoRandom::PseudoRandom(uint32_t seed) { - _x = seed; - _y = default_y; - _z = default_z; - _w = default_w; -} -PseudoRandom::PseudoRandom(int32_t seed) : PseudoRandom(static_cast(seed)) {} - -PseudoRandom::PseudoRandom(int64_t seed) - : PseudoRandom(static_cast(seed >> 32) ^ static_cast(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(nextInt64()); - result = static_cast(generated) / std::numeric_limits::max(); - } while (result == 1.0); - return result; -} - -// --- SecureRandom ---- +template +struct Buffer { + uint64_t pop() { + return arr[--avail]; + } + uint8_t* fillPtr() { + return reinterpret_cast(arr.data() + avail); + } + size_t fillSize() { + return sizeof(uint64_t) * (arr.size() - avail); + } + void setFilled() { + avail = arr.size(); + } -SecureRandom::~SecureRandom() {} + std::array arr; + size_t avail = 0; +}; -#ifdef _WIN32 -class WinSecureRandom : public SecureRandom { +#if defined(SECURE_RANDOM_BCRYPT) +class Source { public: - WinSecureRandom() { + Source() { auto ntstatus = ::BCryptOpenAlgorithmProvider( &_algHandle, BCRYPT_RNG_ALGORITHM, MS_PRIMITIVE_PROVIDER, 0); if (ntstatus != STATUS_SUCCESS) { @@ -118,7 +102,7 @@ public: } } - virtual ~WinSecureRandom() { + ~Source() { auto ntstatus = ::BCryptCloseAlgorithmProvider(_algHandle, 0); if (ntstatus != STATUS_SUCCESS) { warning() << "Failed to close crypto algorithm provider destroying secure random " @@ -127,75 +111,99 @@ public: } } - int64_t nextInt64() { - int64_t value; - auto ntstatus = - ::BCryptGenRandom(_algHandle, reinterpret_cast(&value), sizeof(value), 0); + size_t refill(uint8_t* buf, size_t n) { + auto ntstatus = ::BCryptGenRandom(_algHandle, reinterpret_cast(buf), n, 0); if (ntstatus != STATUS_SUCCESS) { error() << "Failed to generate random number from secure random object; NTSTATUS: " << ntstatus; fassertFailed(28814); } - return value; + return n; } private: BCRYPT_ALG_HANDLE _algHandle; }; +#endif // SECURE_RANDOM_BCRYPT -std::unique_ptr SecureRandom::create() { - return std::make_unique(); -} - -#elif defined(__linux__) || defined(__sun) || defined(__APPLE__) || defined(__FreeBSD__) || \ - defined(__EMSCRIPTEN__) - -class InputStreamSecureRandom : public SecureRandom { +#if defined(SECURE_RANDOM_URANDOM) +class Source { public: - InputStreamSecureRandom(const char* fn) { - _in = std::make_unique(fn, std::ios::binary | std::ios::in); - if (!_in->is_open()) { - error() << "cannot open " << fn << " " << strerror(errno); - fassertFailed(28839); - } - } - - int64_t nextInt64() { - int64_t r; - _in->read(reinterpret_cast(&r), sizeof(r)); - if (_in->fail()) { - error() << "InputStreamSecureRandom failed to generate random bytes"; - fassertFailed(28840); + 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; } - return r; + return i; } private: - std::unique_ptr _in; + 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; + } }; +#endif // SECURE_RANDOM_URANDOM -std::unique_ptr SecureRandom::create() { - return std::make_unique("/dev/urandom"); -} +#if defined(SECURE_RANDOM_ARCFOUR) +class Source { +public: + size_t refill(uint8_t* buf, size_t n) { + arc4random_buf(buf, n); + return n; + } +}; +#endif // SECURE_RANDOM_ARCFOUR -#elif defined(__OpenBSD__) +} // namespace -class Arc4SecureRandom : public SecureRandom { +class SecureUrbg::State { public: - int64_t nextInt64() { - int64_t value; - arc4random_buf(&value, sizeof(value)); - return value; + uint64_t get() { + if (!_buffer.avail) { + size_t n = _source.refill(_buffer.fillPtr(), _buffer.fillSize()); + _buffer.avail += n / sizeof(uint64_t); + } + return _buffer.pop(); } + +private: + Source _source; + Buffer<16> _buffer; }; -std::unique_ptr SecureRandom::create() { - return std::make_unique(); -} +SecureUrbg::SecureUrbg() : _state{std::make_unique()} {} -#else +SecureUrbg::~SecureUrbg() = default; -#error Must implement SecureRandom for platform +uint64_t SecureUrbg::operator()() { + return _state->get(); +} -#endif } // namespace mongo diff --git a/src/mongo/platform/random.h b/src/mongo/platform/random.h index 6ef2a9bf114..3521399c896 100644 --- a/src/mongo/platform/random.h +++ b/src/mongo/platform/random.h @@ -29,86 +29,142 @@ #pragma once +#include #include +#include #include #include +#include namespace mongo { /** + * A uniform random bit generator based on XorShift. * Uses http://en.wikipedia.org/wiki/Xorshift */ -class PseudoRandom { +class XorShift128 { public: - PseudoRandom(int32_t seed); + using result_type = uint32_t; - PseudoRandom(uint32_t seed); + static constexpr result_type min() { + return std::numeric_limits::lowest(); + } - PseudoRandom(int64_t seed); + static constexpr result_type max() { + return std::numeric_limits::max(); + } - int32_t nextInt32(); + explicit XorShift128(uint32_t seed) : _x{seed} {} - int64_t nextInt64(); + result_type operator()() { + uint32_t t = _x ^ (_x << 11); + _x = _y; + _y = _z; + _z = _w; + return _w = _w ^ (_w >> 19) ^ (t ^ (t >> 8)); + } - /** - * Returns a random number in the range [0, 1). - */ - double nextCanonicalDouble(); +private: + uint32_t _x; // seed + uint32_t _y = 362436069; + uint32_t _z = 521288629; + uint32_t _w = 88675123; +}; - /** - * @return a number between 0 and max - */ - int32_t nextInt32(int32_t max) { - return static_cast(nextInt32()) % static_cast(max); +/** 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::lowest(); } - - /** - * @return a number between 0 and max - */ - int64_t nextInt64(int64_t max) { - return static_cast(nextInt64()) % static_cast(max); + static constexpr result_type max() { + return std::numeric_limits::max(); } - /** - * 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() { + // Details including State vary by platform and are deferred to the .cpp file. + SecureUrbg(); + ~SecureUrbg(); + result_type operator()(); - class URBG { - public: - explicit URBG(PseudoRandom* impl) : _impl(impl) {} +private: + class State; + std::unique_ptr _state; +}; + +// Provides mongo-traditional functions around a pluggable UniformRandomBitGenerator. +template +class RandomBase { +public: + using urbg_type = Urbg; - using result_type = uint64_t; + RandomBase() : _urbg{} {} + explicit RandomBase(urbg_type u) : _urbg{std::move(u)} {} + + /** The underlying generator */ + urbg_type& urbg() { + return _urbg; + } + + /** A random number in the range [0, 1). */ + double nextCanonicalDouble() { + return std::uniform_real_distribution{0, 1}(_urbg); + } - static constexpr result_type min() { - return std::numeric_limits::min(); - } + /** A number uniformly distributed over all possible values. */ + int32_t nextInt32() { + return _nextAny(); + } - static constexpr result_type max() { - return std::numeric_limits::max(); - } + /** A number uniformly distributed over all possible values. */ + int64_t nextInt64() { + return _nextAny(); + } - result_type operator()() { - return _impl->nextInt64(); - } + /** A number in the half-open interval [0, max) */ + int32_t nextInt32(int32_t max) { + return std::uniform_int_distribution(0, max - 1)(_urbg); + } - private: - PseudoRandom* _impl; - }; + /** A number in the half-open interval [0, max) */ + int64_t nextInt64(int64_t max) { + return std::uniform_int_distribution(0, max - 1)(_urbg); + } - return URBG(this); + /** Fill array `buf` with `n` random bytes. */ + void fill(void* buf, size_t n) { + const auto p = static_cast(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; + } } private: - uint32_t nextUInt32(); + template + T _nextAny() { + using Limits = std::numeric_limits; + return std::uniform_int_distribution(Limits::lowest(), Limits::max())(_urbg); + } - uint32_t _x; - uint32_t _y; - uint32_t _z; - uint32_t _w; + urbg_type _urbg; +}; + +/** + * A Pseudorandom generator that's not cryptographically secure, but very fast and small. + */ +class PseudoRandom : public RandomBase { + using Base = RandomBase; + +public: + explicit PseudoRandom(uint32_t seed) : Base{XorShift128{seed}} {} + explicit PseudoRandom(int32_t seed) : PseudoRandom{static_cast(seed)} {} + explicit PseudoRandom(uint64_t seed) + : PseudoRandom{static_cast(seed ^ (seed >> 32))} {} + explicit PseudoRandom(int64_t seed) : PseudoRandom{static_cast(seed)} {} }; /** @@ -116,12 +172,11 @@ private: * Suitable for nonce/crypto * Slower than PseudoRandom, so only use when really need */ -class SecureRandom { -public: - virtual ~SecureRandom(); - - virtual int64_t nextInt64() = 0; +class SecureRandom : public RandomBase { + using Base = RandomBase; - static std::unique_ptr create(); +public: + using Base::Base; }; + } // namespace mongo diff --git a/src/mongo/platform/random_test.cpp b/src/mongo/platform/random_test.cpp index ee82a89490f..c3271f8b926 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() always returns values between 0 and 1. + * Test that nextCanonicalDouble() is at least very likely to return values in [0,1). */ TEST(RandomTest, NextCanonicalWithinRange) { PseudoRandom prng(10); - for (int i = 0; i < 100; i++) { + for (size_t i = 0; i < 1'000'000; ++i) { double next = prng.nextCanonicalDouble(); - ASSERT_LTE(0.0, next); + ASSERT_GTE(next, 0.0); ASSERT_LT(next, 1.0); } } @@ -211,12 +211,47 @@ 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 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::create(); - auto b = SecureRandom::create(); + auto a = SecureRandom(); + auto b = SecureRandom(); 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 03dfd1114f5..56dd270a742 100644 --- a/src/mongo/s/query/cluster_cursor_manager.cpp +++ b/src/mongo/s/query/cluster_cursor_manager.cpp @@ -148,8 +148,7 @@ void ClusterCursorManager::PinnedCursor::returnAndKillCursor() { } ClusterCursorManager::ClusterCursorManager(ClockSource* clockSource) - : _clockSource(clockSource), - _pseudoRandom(std::unique_ptr(SecureRandom::create())->nextInt64()) { + : _clockSource(clockSource), _pseudoRandom(SecureRandom().nextInt64()) { invariant(_clockSource); } diff --git a/src/mongo/s/sharding_initialization.cpp b/src/mongo/s/sharding_initialization.cpp index 83ebcdfdda0..8f4285e26e9 100644 --- a/src/mongo/s/sharding_initialization.cpp +++ b/src/mongo/s/sharding_initialization.cpp @@ -152,13 +152,11 @@ std::unique_ptr makeShardingTaskExecutor( } std::string generateDistLockProcessId(OperationContext* opCtx) { - std::unique_ptr rng(SecureRandom::create()); - return str::stream() << HostAndPort(getHostName(), serverGlobalParams.port).toString() << ':' << durationCount( opCtx->getServiceContext()->getPreciseClockSource()->now().toDurationSinceEpoch()) - << ':' << rng->nextInt64(); + << ':' << SecureRandom().nextInt64(); } Status initializeGlobalShardingState(OperationContext* opCtx, diff --git a/src/mongo/shell/shell_utils.cpp b/src/mongo/shell/shell_utils.cpp index c7834d5a060..d45789ca403 100644 --- a/src/mongo/shell/shell_utils.cpp +++ b/src/mongo/shell/shell_utils.cpp @@ -311,8 +311,7 @@ BSONObj JSSrand(const BSONObj& a, void* data) { if (a.nFields() == 1 && a.firstElement().isNumber()) seed = static_cast(a.firstElement().numberLong()); else { - std::unique_ptr rand(SecureRandom::create()); - seed = static_cast(rand->nextInt64()); + seed = static_cast(SecureRandom().nextInt64()); } _prng = PseudoRandom(seed); return BSON("" << static_cast(seed)); diff --git a/src/mongo/tools/mongobridge_options.cpp b/src/mongo/tools/mongobridge_options.cpp index 79d27417659..81a116df714 100644 --- a/src/mongo/tools/mongobridge_options.cpp +++ b/src/mongo/tools/mongobridge_options.cpp @@ -70,8 +70,7 @@ Status storeMongoBridgeOptions(const moe::Environment& params, } if (!params.count("seed")) { - std::unique_ptr seedSource{SecureRandom::create()}; - mongoBridgeGlobalParams.seed = seedSource->nextInt64(); + mongoBridgeGlobalParams.seed = SecureRandom().nextInt64(); } else { mongoBridgeGlobalParams.seed = static_cast(params["seed"].as()); } diff --git a/src/mongo/tools/mongoebench_options.cpp b/src/mongo/tools/mongoebench_options.cpp index 0ba4394d976..f2982ee028a 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(params["seed"].as()) - : SecureRandom::create()->nextInt64(); + : SecureRandom().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 60050da7055..af757e2bd49 100644 --- a/src/mongo/util/fail_point.cpp +++ b/src/mongo/util/fail_point.cpp @@ -33,7 +33,10 @@ #include "mongo/util/fail_point.h" #include + +#include #include +#include #include "mongo/base/init.h" #include "mongo/bson/json.h" @@ -58,38 +61,13 @@ MONGO_INITIALIZER_GENERAL(AllFailPointsRegistered, (), ()) return Status::OK(); } -/** - * Type representing the per-thread PRNG used by fail-points. - */ -class FailPointPRNG { -public: - FailPointPRNG() : _prng(std::unique_ptr(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(); - return _failPointPrng.get(); - } - -private: - PseudoRandom _prng; - static thread_local std::unique_ptr _failPointPrng; -}; - -thread_local std::unique_ptr FailPointPRNG::_failPointPrng; +/** The per-thread PRNG used by fail-points. */ +thread_local PseudoRandom threadPrng{SecureRandom().nextInt64()}; } // namespace void FailPoint::setThreadPRNGSeed(int32_t seed) { - FailPointPRNG::current()->resetSeed(seed); + threadPrng = PseudoRandom(seed); } FailPoint::FailPoint() = default; @@ -155,10 +133,10 @@ FailPoint::RetCode FailPoint::_slowShouldFailOpenBlock( case alwaysOn: return slowOn; case random: { - const int maxActivationValue = _timesOrPeriod.load(); - if (FailPointPRNG::current()->nextPositiveInt32() < maxActivationValue) + std::uniform_int_distribution distribution{}; + if (distribution(threadPrng.urbg()) < _timesOrPeriod.load()) { return slowOn; - + } return slowOff; } case nTimes: { diff --git a/src/mongo/util/uuid.cpp b/src/mongo/util/uuid.cpp index d729777cf30..63ca7bc1e2d 100644 --- a/src/mongo/util/uuid.cpp +++ b/src/mongo/util/uuid.cpp @@ -43,7 +43,7 @@ namespace mongo { namespace { Mutex uuidGenMutex; -auto uuidGen = SecureRandom::create(); +SecureRandom uuidGen; // 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,19 +97,12 @@ bool UUID::isRFC4122v4() const { } UUID UUID::gen() { - int64_t randomWords[2]; - + UUIDStorage randomBytes; { stdx::lock_guard lk(uuidGenMutex); - - // Generate 128 random bits - randomWords[0] = uuidGen->nextInt64(); - randomWords[1] = uuidGen->nextInt64(); + uuidGen.fill(&randomBytes, sizeof(randomBytes)); } - 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; -- cgit v1.2.1