Revert "SERVER-43641 upgrade random.h"

This reverts commit 96da177c6ae7b7ed0f29983ad033d8a59524b0b2.

3 files changed, 157 insertions, 255 deletions

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