From af456842e13ab83cfeb44f3638b62652b201281c Mon Sep 17 00:00:00 2001 From: Thiago Macieira Date: Wed, 11 Oct 2017 15:28:40 +0200 Subject: Change QRandomGenerator to have a deterministic mode Now only QRandomGenerator::system() will access the system-wide RNG, which we document to be cryptographically-safe and possibly backed by a true HWRNG. Everything else just wraps a Mersenne Twister. Change-Id: I0a103569c81b4711a649fffd14ec8cd3469425df Reviewed-by: Lars Knoll --- src/corelib/global/qrandom.cpp | 707 ++++++++++++++++++++++++++--------------- src/corelib/global/qrandom.h | 160 +++++++--- src/corelib/global/qrandom_p.h | 17 + 3 files changed, 581 insertions(+), 303 deletions(-) (limited to 'src/corelib') diff --git a/src/corelib/global/qrandom.cpp b/src/corelib/global/qrandom.cpp index 17f25ead86..44b807d745 100644 --- a/src/corelib/global/qrandom.cpp +++ b/src/corelib/global/qrandom.cpp @@ -43,10 +43,8 @@ #include "qrandom.h" #include "qrandom_p.h" #include +#include #include -#include - -#include #include @@ -86,6 +84,7 @@ DECLSPEC_IMPORT BOOLEAN WINAPI SystemFunction036(PVOID RandomBuffer, ULONG Rando #undef Q_ASSERT_X #undef Q_ASSERT #define Q_ASSERT(cond) assert(cond) +#define Q_ASSERT_X(cond, x, msg) assert(cond && msg) #if defined(QT_NO_DEBUG) && !defined(QT_FORCE_ASSERTS) # define NDEBUG 1 #endif @@ -122,13 +121,41 @@ static QT_FUNCTION_TARGET(RDRND) qssize_t qt_random_cpu(void *buffer, qssize_t c out: return ptr - reinterpret_cast(buffer); } +#else +static qssize_t qt_random_cpu(void *, qssize_t) +{ + return 0; +} #endif namespace { -#if QT_CONFIG(getentropy) -class SystemRandom +static QBasicMutex globalPRNGMutex; + +struct PRNGLocker +{ + const bool locked; + PRNGLocker(const QRandomGenerator *that) + : locked(that == nullptr || that == QRandomGenerator::global()) + { + if (locked) + globalPRNGMutex.lock(); + } + ~PRNGLocker() + { + if (locked) + globalPRNGMutex.unlock(); + } +}; +} + +enum { + // may be "overridden" by a member enum + FillBufferNoexcept = true +}; + +struct QRandomGenerator::SystemGenerator : public QRandomGenerator::SystemGeneratorBase { -public: +#if QT_CONFIG(getentropy) static qssize_t fillBuffer(void *buffer, qssize_t count) Q_DECL_NOTHROW { // getentropy can read at most 256 bytes, so break the reading @@ -146,94 +173,94 @@ public: Q_UNUSED(ret); return count; } -}; #elif defined(Q_OS_UNIX) -class SystemRandom -{ - static QBasicAtomicInt s_fdp1; // "file descriptor plus 1" - static int openDevice(); -#ifdef Q_CC_GNU - // If it's not GCC or GCC-like, then we'll leak the file descriptor - __attribute__((destructor)) -#endif - static void closeDevice(); - SystemRandom() {} -public: - enum { EfficientBufferFill = true }; - static qssize_t fillBuffer(void *buffer, qssize_t count); -}; -QBasicAtomicInt SystemRandom::s_fdp1 = Q_BASIC_ATOMIC_INITIALIZER(0); + QBasicAtomicInt fdp1; // "file descriptor plus 1" + int openDevice() + { + int fd = fdp1.loadAcquire() - 1; + if (fd != -1) + return fd; + + fd = qt_safe_open("/dev/urandom", O_RDONLY); + if (fd == -1) + fd = qt_safe_open("/dev/random", O_RDONLY | O_NONBLOCK); + if (fd == -1) { + // failed on both, set to -2 so we won't try again + fd = -2; + } -void SystemRandom::closeDevice() -{ - int fd = s_fdp1.loadAcquire() - 1; - if (fd >= 0) - qt_safe_close(fd); -} + int opened_fdp1; + if (fdp1.testAndSetOrdered(0, fd + 1, opened_fdp1)) + return fd; -int SystemRandom::openDevice() -{ - int fd = s_fdp1.loadAcquire() - 1; - if (fd != -1) - return fd; - - fd = qt_safe_open("/dev/urandom", O_RDONLY); - if (fd == -1) - fd = qt_safe_open("/dev/random", O_RDONLY | O_NONBLOCK); - if (fd == -1) { - // failed on both, set to -2 so we won't try again - fd = -2; + // failed, another thread has opened the file descriptor + if (fd >= 0) + qt_safe_close(fd); + return opened_fdp1 - 1; } - int opened_fdp1; - if (s_fdp1.testAndSetOrdered(0, fd + 1, opened_fdp1)) { - if (fd >= 0) { - static const SystemRandom closer; - Q_UNUSED(closer); - } - return fd; +#ifdef Q_CC_GNU + // If it's not GCC or GCC-like, then we'll leak the file descriptor + __attribute__((destructor)) +#endif + static void closeDevice() + { + int fd = static_cast(system()->storage.sys).fdp1.load() - 1; + if (fd >= 0) + qt_safe_close(fd); } - // failed, another thread has opened the file descriptor - if (fd >= 0) - qt_safe_close(fd); - return opened_fdp1 - 1; -} + SystemGenerator() : fdp1 Q_BASIC_ATOMIC_INITIALIZER(0) {} -qssize_t SystemRandom::fillBuffer(void *buffer, qssize_t count) -{ - int fd = openDevice(); - if (Q_UNLIKELY(fd < 0)) - return 0; + qssize_t fillBuffer(void *buffer, qssize_t count) + { + int fd = openDevice(); + if (Q_UNLIKELY(fd < 0)) + return 0; - qint64 n = qt_safe_read(fd, buffer, count); - return qMax(n, 0); // ignore any errors -} -#endif // Q_OS_UNIX + qint64 n = qt_safe_read(fd, buffer, count); + return qMax(n, 0); // ignore any errors + } -#if defined(Q_OS_WIN) && !defined(Q_OS_WINRT) -class SystemRandom -{ -public: - static qssize_t fillBuffer(void *buffer, qssize_t count) Q_DECL_NOTHROW +#elif defined(Q_OS_WIN) && !defined(Q_OS_WINRT) + qssize_t fillBuffer(void *buffer, qssize_t count) Q_DECL_NOTHROW { auto RtlGenRandom = SystemFunction036; return RtlGenRandom(buffer, ULONG(count)) ? count: 0; } -}; #elif defined(Q_OS_WINRT) -class SystemRandom -{ -public: - static qssize_t fillBuffer(void *, qssize_t) Q_DECL_NOTHROW + qssize_t fillBuffer(void *, qssize_t) Q_DECL_NOTHROW { // always use the fallback return 0; } -}; #endif // Q_OS_WINRT -} // unnamed namespace + + static SystemGenerator &self() + { + return static_cast(QRandomGenerator::system()->storage.sys); + } + void generate(quint32 *begin, quint32 *end) Q_DECL_NOEXCEPT_EXPR(FillBufferNoexcept); + + // For std::mersenne_twister_engine implementations that use something + // other than quint32 (unsigned int) to fill their buffers. + template void generate(T *begin, T *end) + { + Q_STATIC_ASSERT(sizeof(T) >= sizeof(quint32)); + if (sizeof(T) == sizeof(quint32)) { + // Microsoft Visual Studio uses unsigned long, but that's still 32-bit + generate(reinterpret_cast(begin), reinterpret_cast(end)); + } else { + // Slow path. Fix your C++ library. + std::generate(begin, end, [this]() { + quint32 datum; + generate(&datum, &datum + 1); + return datum; + }); + } + } +}; #if defined(Q_OS_WIN) static void fallback_update_seed(unsigned) {} @@ -252,6 +279,7 @@ static void fallback_update_seed(unsigned) {} static void fallback_fill(quint32 *, qssize_t) Q_DECL_NOTHROW { // no fallback necessary, getentropy cannot fail under normal circumstances + Q_UNREACHABLE(); } #elif defined(Q_OS_BSD4) static void fallback_update_seed(unsigned) {} @@ -347,26 +375,11 @@ static void fallback_fill(quint32 *ptr, qssize_t left) Q_DECL_NOTHROW } #endif -static qssize_t fill_cpu(quint32 *buffer, qssize_t count) Q_DECL_NOTHROW -{ -#if defined(Q_PROCESSOR_X86) && QT_COMPILER_SUPPORTS_HERE(RDRND) - if (qCpuHasFeature(RDRND) && (uint(qt_randomdevice_control) & SkipHWRNG) == 0) - return qt_random_cpu(buffer, count); -#else - Q_UNUSED(buffer); - Q_UNUSED(count); -#endif - return 0; -} - -static Q_NEVER_INLINE void fill(void *begin, void *end) - Q_DECL_NOEXCEPT_EXPR(noexcept(SystemRandom::fillBuffer(nullptr, 1))) +Q_NEVER_INLINE void QRandomGenerator::SystemGenerator::generate(quint32 *begin, quint32 *end) + Q_DECL_NOEXCEPT_EXPR(FillBufferNoexcept) { - // Verify that the pointers are properly aligned for 32-bit - Q_ASSERT(quintptr(begin) % sizeof(quint32) == 0); - Q_ASSERT(quintptr(end) % sizeof(quint32) == 0); - quint32 *buffer = reinterpret_cast(begin); - qssize_t count = reinterpret_cast(end) - buffer; + quint32 *buffer = begin; + qssize_t count = end - begin; if (Q_UNLIKELY(uint(qt_randomdevice_control) & SetRandomData)) { uint value = uint(qt_randomdevice_control) & RandomDataMask; @@ -374,10 +387,13 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) return; } - qssize_t filled = fill_cpu(buffer, count); + qssize_t filled = 0; + if (qt_has_hwrng() && (uint(qt_randomdevice_control) & SkipHWRNG) == 0) + filled += qt_random_cpu(buffer, count); + if (filled != count && (uint(qt_randomdevice_control) & SkipSystemRNG) == 0) { qssize_t bytesFilled = - SystemRandom::fillBuffer(buffer + filled, (count - filled) * qssize_t(sizeof(*buffer))); + fillBuffer(buffer + filled, (count - filled) * qssize_t(sizeof(*buffer))); filled += bytesFilled / qssize_t(sizeof(*buffer)); } if (filled) @@ -392,85 +408,153 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) /*! \class QRandomGenerator \inmodule QtCore + \reentrant \since 5.10 \brief The QRandomGenerator class allows one to obtain random values from a - high-quality, seed-less Random Number Generator. + high-quality Random Number Generator. QRandomGenerator may be used to generate random values from a high-quality - random number generator. Unlike qrand(), QRandomGenerator does not need to be - seeded. That also means it is not possible to force it to produce a - reliable sequence, which may be needed for debugging. + random number generator. Like the C++ random engines, QRandomGenerator can + be seeded with user-provided values through the constructor. + When seeded, the sequence of numbers generated by this + class is deterministic. That is to say, given the same seed data, + QRandomGenerator will generate the same sequence of numbers. But given + different seeds, the results should be considerably different. + + QRandomGenerator::global() returns a global instance of QRandomGenerator + that Qt will ensure to be securely seeded. This object is thread-safe, may + be shared for most uses, and is always seeded from + QRandomGenerator::system() + + QRandomGenerator::system() may be used to access the system's + cryptographically-safe random generator. On Unix systems, it's equivalent + to reading from \c {/dev/urandom} or the \c {getrandom()} or \c + {getentropy()} system calls. The class can generate 32-bit or 64-bit quantities, or fill an array of those. The most common way of generating new values is to call the generate(), generate64() or fillRange() functions. One would use it as: \code - quint32 value = QRandomGenerator::generate(); + quint32 value = QRandomGenerator::global()->generate(); + \endcode + + Additionally, it provides a floating-point function generateDouble() that + returns a number in the range [0, 1) (that is, inclusive of zero and + exclusive of 1). There's also a set of convenience functions that + facilitate obtaining a random number in a bounded, integral range. + + \section1 Seeding and determinism + + QRandomGenerator may be seeded with specific seed data. When that is done, + the numbers generated by the object will always be the same, as in the + following example: + + \code + QRandomGenerator prng1(1234), prng2(1234); + Q_ASSERT(prng1.generate32() == prng2.generate32()); + Q_ASSERT(prng1.generate64() == prng2.generate64()); \endcode - Additionally, it provides a floating-point function generateDouble() that returns - a number in the range [0, 1) (that is, inclusive of zero and exclusive of - 1). There's also a set of convenience functions that facilitate obtaining a - random number in a bounded, integral range. + The seed data takes the form of one or more 32-bit words. The ideal seed + size is approximately equal to the size of the QRandomGenerator class + itself. Due to mixing of the seed data, QRandomGenerator cannot guarantee + that distinct seeds will produce different sequences. + + QRandomGenerator::global() is always seeded from + QRandomGenerator::system(), so it's not possible to make it produce + identical sequences. - \warning This class is not suitable for bulk data creation. See below for the - technical reasons. + \section1 Bulk data - \section1 Frequency and entropy exhaustion + When operating in deterministic mode, QRandomGenerator may be used for bulk + data generation. In fact, applications that do not need + cryptographically-secure or true random data are advised to use a regular + QRandomGenerator instead of QRandomGenerator::system() for their random + data needs. - QRandomGenerator does not need to be seeded and instead uses operating system - or hardware facilities to generate random numbers. On some systems and with - certain hardware, those facilities are true Random Number Generators. - However, if they are true RNGs, those facilities have finite entropy source - and thus may fail to produce any results if the entropy pool is exhausted. + For ease of use, QRandomGenerator provides a global object that can + be easily used, as in the following example: + + \code + int x = QRandomGenerator::global()->generate32(); + int y = QRandomGenerator::global()->generate32(); + int w = QRandomGenerator::global()->bounded(16384); + int h = QRandomGenerator::global()->bounded(16384); + \endcode + + \section1 System-wide random number generator + + QRandomGenerator::system() may be used to access the system-wide random + number generator, which is cryptographically-safe on all systems that Qt + runs on. This function will use hardware facilities to generate random + numbers where available. On such systems, those facilities are true Random + Number Generators. However, if they are true RNGs, those facilities have + finite entropy sources and thus may fail to produce any results if their + entropy pool is exhausted. If that happens, first the operating system then QRandomGenerator will fall back to Pseudo Random Number Generators of decreasing qualities (Qt's - fallback generator being the simplest). Therefore, QRandomGenerator should - not be used for high-frequency random number generation, lest the entropy - pool become empty. As a rule of thumb, this class should not be called upon - to generate more than a kilobyte per second of random data (note: this may - vary from system to system). + fallback generator being the simplest). Whether those generators are still + of cryptographic quality is implementation-defined. Therefore, + QRandomGenerator::system() should not be used for high-frequency random + number generation, lest the entropy pool become empty. As a rule of thumb, + this class should not be called upon to generate more than a kilobyte per + second of random data (note: this may vary from system to system). If an application needs true RNG data in bulk, it should use the operating - system facilities (such as \c{/dev/random} on Unix systems) directly and - wait for entropy to become available. If true RNG is not required, - applications should instead use a PRNG engines and can use QRandomGenerator to - seed those. + system facilities (such as \c{/dev/random} on Linux) directly and wait for + entropy to become available. If the application requires PRNG engines of + cryptographic quality but not of true randomness, + QRandomGenerator::system() may still be used (see section below). + + If neither a true RNG nor a cryptographically secure PRNG are required, + applications should instead use PRNG engines like QRandomGenerator's + deterministic mode and those from the C++ Standard Library. + QRandomGenerator::system() can be used to seed those. + + \section2 Fallback quality + + QRandomGenerator::system() uses the operating system facilities to obtain + random numbers, which attempt to collect real entropy from the surrounding + environment to produce true random numbers. However, it's possible that the + entropy pool becomes exhausted, in which case the operating system will + fall back to a pseudo-random engine for a time. Under no circumstances will + QRandomGenerator::system() block, waiting for more entropy to be collected. + + The following operating systems guarantee that the results from their + random-generation API will be of at least cryptographically-safe quality, + even if the entropy pool is exhausted: Apple OSes (Darwin), BSDs, Linux, + Windows. Barring a system installation problem (such as \c{/dev/urandom} + not being readable by the current process), QRandomGenerator::system() will + therefore have the same guarantees. + + On other operating systems, QRandomGenerator will fall back to a PRNG of + good numeric distribution, but it cannot guarantee proper seeding in all + cases. Please consult the OS documentation for more information. + + Applications that require QRandomGenerator not to fall back to + non-cryptographic quality generators are advised to check their operating + system documentation or restrict their deployment to one of the above. + + \section1 Reentrancy and thread-safety + + QRandomGenerator is reentrant, meaning that multiple threads can operate on + this class at the same time, so long as they operate on different objects. + If multiple threads need to share one PRNG sequence, external locking by a + mutex is required. + + The exceptions are the objects returned by QRandomGenerator::global() and + QRandomGenerator::system(): those objects are thread-safe and may be used + by any thread without external locking. Note that thread-safety does not + extend to copying those objects: they should always be used by reference. \section1 Standard C++ Library compatibility - QRandomGenerator is modeled after - \c{\l{http://en.cppreference.com/w/cpp/numeric/random/random_device}{std::random_device}} - and may be used in almost all contexts that the Standard Library can. - QRandomGenerator attempts to use either the same engine that backs - \c{std::random_device} or a better one. Note that \c{std::random_device} is - also allowed to fail if the source entropy pool becomes exhausted, in which - case it will throw an exception. QRandomGenerator never throws, but may abort - program execution instead. - - Like the Standard Library class, QRandomGenerator can be used to seed Standard - Library deterministic random engines from \c{}, such as the - Mersenne Twister. Unlike \c{std::random_device}, QRandomGenerator also - implements the API of - \c{\l{http://en.cppreference.com/w/cpp/numeric/random/seed_seq}{std::seed_seq}}, - allowing it to seed the deterministic engines directly. - - The following code can be used to create and seed the - implementation-defined default deterministic PRNG, then use it to fill a - block range: - - \code - QRandomGenerator rd; - std::default_random_engine rng(rd); - std::generate(block.begin(), block.end(), rng); - - // equivalent to: - for (auto &v : block) - v = rng(); - \endcode + QRandomGenerator is modeled after the requirements for random number + engines in the C++ Standard Library and may be used in almost all contexts + that the Standard Library engines can. QRandomGenerator is also compatible with the uniform distribution classes \c{std::uniform_int_distribution} and \c{std:uniform_real_distribution}, as @@ -479,57 +563,101 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) [1, 2.5): \code - QRandomGenerator64 rd; std::uniform_real_distribution dist(1, 2.5); - return dist(rd); + return dist(*QRandomGenerator::global()); \endcode - Note the use of the QRandomGenerator64 class instead of QRandomGenerator to - obtain 64 bits of random data in a single call, though it is not required - to make the algorithm work (the Standard Library functions will make as - many calls as required to obtain enough bits of random data for the desired - range). - \sa QRandomGenerator64, qrand() */ /*! - \fn QRandomGenerator::QRandomGenerator() - \internal - Defaulted constructor, does nothing. + \fn QRandomGenerator::QRandomGenerator(quint32 seed) + + Initializes this QRandomGenerator object with the value \a seed as + the seed. Two objects constructed with the same seed value will + produce the same number sequence. */ /*! - \typedef QRandomGenerator::result_type + \fn QRandomGenerator::QRandomGenerator(const quint32 (&seedBuffer)[N]) + \overload - A typedef to the type that operator()() returns. That is, quint32. + Initializes this QRandomGenerator object with the values found in the + array \a seedBuffer as the seed. Two objects constructed or reseeded with + the same seed value will produce the same number sequence. + */ - \sa operator()() +/*! + \fn QRandomGenerator::QRandomGenerator(const quint32 *seedBuffer, qssize_t len) + \overload + + Initializes this QRandomGenerator object with \a len values found in + the array \a seedBuffer as the seed. Two objects constructed or reseeded + with the same seed value will produce the same number sequence. + + This constructor is equivalent to: + \code + std::seed_seq sseq(seedBuffer, seedBuffer + len); + QRandomGenerator generator(sseq); + \endcode */ /*! - \fn result_type QRandomGenerator::operator()() + \fn QRandomGenerator::QRandomGenerator(const quint32 *begin, const quin32 *end) + \overload - Generates a 32-bit random quantity and returns it. + Initializes this QRandomGenerator object with the values found in the range + from \a begin to \a end as the seed. Two objects constructed or reseeded + with the same seed value will produce the same number sequence. - \sa QRandomGenerator::generate(), QRandomGenerator::generate64() + This constructor is equivalent to: + \code + std::seed_seq sseq(begin, end); + QRandomGenerator generator(sseq); + \endcode + */ + +/*! + \fn QRandomGenerator::QRandomGenerator(std::seed_seq &sseq) + \overload + + Initializes this QRandomGenerator object with the seed sequence \a + sseq as the seed. Two objects constructed or reseeded with the same seed + value will produce the same number sequence. */ /*! - \fn double QRandomGenerator::entropy() const + \fn QRandomGenerator::QRandomGenerator(const QRandomGenerator &other) - Returns the estimate of the entropy in the random generator source. + Creates a copy of the generator state in the \a other object. If \a other is + QRandomGenerator::system() or a copy of that, this object will also read + from the operating system random-generating facilities. In that case, the + sequences generated by the two objects will be different. - This function exists to comply with the Standard Library requirements for - \c{\l{http://en.cppreference.com/w/cpp/numeric/random/random_device}{std::random_device}} - but it does not and cannot ever work. It is not possible to obtain a - reliable entropy value in a shared entropy pool in a multi-tasking system, - as other processes or threads may use that entropy. Any value non-zero - value that this function could return would be obsolete by the time the - user code reached it. + In all other cases, the new QRandomGenerator object will start at the same + position in the deterministic sequence as the \a other object was. Both + objects will generate the same sequence from this point on. - Since QRandomGenerator attempts to use a hardware Random Number Generator, - this function always returns 0.0. + For that reason, it is not adviseable to create a copy of + QRandomGenerator::global(). If one needs an exclusive deterministic + generator, consider instead creating a new object and seeding it from + QRandomGenerator::system(). + */ + +/*! + \typedef QRandomGenerator::result_type + + A typedef to the type that operator()() returns. That is, quint32. + + \sa operator()() + */ + +/*! + \fn result_type QRandomGenerator::operator()() + + Generates a 32-bit random quantity and returns it. + + \sa generate(), generate64() */ /*! @@ -537,7 +665,7 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) Returns the minimum value that QRandomGenerator may ever generate. That is, 0. - \sa max(), QRandomGenerator64::max() + \sa max(), QRandomGenerator64::min() */ /*! @@ -556,7 +684,7 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) and \a end. This function is equivalent to (and is implemented as): \code - std::generate(begin, end, []() { return generate(); }); + std::generate(begin, end, [this]() { return generate(); }); \endcode This function complies with the requirements for the function @@ -569,7 +697,7 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) quantities, one can write: \code - std::generate(begin, end, []() { return QRandomGenerator::generate64(); }); + std::generate(begin, end, []() { return QRandomGenerator::global()->generate64(); }); \endcode If the range refers to contiguous memory (such as an array or the data from @@ -647,26 +775,26 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) */ /*! - \fn qreal QRandomGenerator::bounded(qreal sup) + \fn qreal QRandomGenerator::bounded(qreal highest) Generates one random qreal in the range between 0 (inclusive) and \a - sup (exclusive). This function is equivalent to and is implemented as: + highest (exclusive). This function is equivalent to and is implemented as: \code - return generateDouble() * sup; + return generateDouble() * highest; \endcode \sa generateDouble(), bounded() */ /*! - \fn quint32 QRandomGenerator::bounded(quint32 sup) + \fn quint32 QRandomGenerator::bounded(quint32 highest) \overload Generates one random 32-bit quantity in the range between 0 (inclusive) and - \a sup (exclusive). The same result may also be obtained by using + \a highest (exclusive). The same result may also be obtained by using \c{\l{http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution}{std::uniform_int_distribution}} - with parameters 0 and \c{sup - 1}. That class can also be used to obtain + with parameters 0 and \c{highest - 1}. That class can also be used to obtain quantities larger than 32 bits. For example, to obtain a value between 0 and 255 (inclusive), one would write: @@ -685,11 +813,11 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) */ /*! - \fn quint32 QRandomGenerator::bounded(int sup) + \fn quint32 QRandomGenerator::bounded(int highest) \overload Generates one random 32-bit quantity in the range between 0 (inclusive) and - \a sup (exclusive). \a sup must not be negative. + \a highest (exclusive). \a highest must not be negative. Note that this function cannot be used to obtain values in the full 32-bit range of int. Instead, use generate() and cast to int. @@ -698,13 +826,13 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) */ /*! - \fn quint32 QRandomGenerator::bounded(quint32 min, quint32 sup) + \fn quint32 QRandomGenerator::bounded(quint32 lowest, quint32 highest) \overload - Generates one random 32-bit quantity in the range between \a min (inclusive) - and \a sup (exclusive). The same result may also be obtained by using + Generates one random 32-bit quantity in the range between \a lowest (inclusive) + and \a highest (exclusive). The same result may also be obtained by using \c{\l{http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution}{std::uniform_int_distribution}} - with parameters \a min and \c{\a sup - 1}. That class can also be used to + with parameters \a lowest and \c{\a highest - 1}. That class can also be used to obtain quantities larger than 32 bits. For example, to obtain a value between 1000 (incl.) and 2000 (excl.), one @@ -722,11 +850,11 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) */ /*! - \fn quint32 QRandomGenerator::bounded(int min, int sup) + \fn quint32 QRandomGenerator::bounded(int lowest, int highest) \overload - Generates one random 32-bit quantity in the range between \a min - (inclusive) and \a sup (exclusive), both of which may be negative. + Generates one random 32-bit quantity in the range between \a lowest + (inclusive) and \a highest (exclusive), both of which may be negative. Note that this function cannot be used to obtain values in the full 32-bit range of int. Instead, use generate() and cast to int. @@ -734,6 +862,54 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) \sa generate(), generate64(), generateDouble() */ +/*! + \fn QRandomGenerator *QRandomGenerator::system() + \threadsafe + + Returns a pointer to a shared QRandomGenerator that always uses the + facilities provided by the operating system to generate random numbers. The + system facilities are considered to be cryptographically safe on at least + the following operating systems: Apple OSes (Darwin), BSDs, Linux, Windows. + That may also be the case on other operating systems. + + They are also possibly backed by a true hardware random number generator. + For that reason, the QRandomGenerator returned by this function should not + be used for bulk data generation. Instead, use it to seed QRandomGenerator + or a random engine from the header. + + The object returned by this function is thread-safe and may be used in any + thread without locks. It may also be copied and the resulting + QRandomGenerator will also access the operating system facilities, but they + will not generate the same sequence. + + \sa global() +*/ + +/*! + \fn QRandomGenerator *QRandomGenerator::global() + \threadsafe + + Returns a pointer to a shared QRandomGenerator that was seeded using + QRandomGenerator::system(). This function should be used to create random data + without the expensive creation of a securely-seeded QRandomGenerator for a + specific use or storing the rather large QRandomGenerator object. + large QRandomGenerator object. + + For example, the following creates a random RGB color: + + \code + return QColor::fromRgb(QRandomGenerator::global()->generate()); + \endcode + + Accesses to this object are thread-safe and it may therefore be used in any + thread without locks. The object may also be copied and the sequence + produced by the copy will be the same as the shared object will produce. + Note, however, that if there are other threads accessing the global object, + those threads may obtain samples at unpredictable intervals. + + \sa system() +*/ + /*! \class QRandomGenerator64 \inmodule QtCore @@ -755,10 +931,11 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) */ /*! - \fn QRandomGenerator64::QRandomGenerator64() - \internal - Defaulted constructor, does nothing. - */ + \fn QRandomGenerator64::QRandomGenerator64(const QRandomGenerator &other) + \internal + + Creates a copy. +*/ /*! \typedef QRandomGenerator64::result_type @@ -793,80 +970,78 @@ static Q_NEVER_INLINE void fill(void *begin, void *end) \sa QRandomGenerator::generate(), QRandomGenerator::generate64() */ -/*! - \fn double QRandomGenerator64::entropy() const - - Returns the estimate of the entropy in the random generator source. - - This function exists to comply with the Standard Library requirements for - \c{\l{http://en.cppreference.com/w/cpp/numeric/random/random_device}{std::random_device}} - but it does not and cannot ever work. It is not possible to obtain a - reliable entropy value in a shared entropy pool in a multi-tasking system, - as other processes or threads may use that entropy. Any value non-zero - value that this function could return would be obsolete by the time the - user code reached it. - - Since QRandomGenerator64 attempts to use a hardware Random Number Generator, - this function always returns 0.0. - */ - -/*! - \fn result_type QRandomGenerator64::min() - - Returns the minimum value that QRandomGenerator64 may ever generate. That is, 0. - - \sa max(), QRandomGenerator::max() - */ +inline QRandomGenerator::Storage::Storage() +{ + // nothing +} -/*! - \fn result_type QRandomGenerator64::max() +inline QRandomGenerator64::QRandomGenerator64(System s) + : QRandomGenerator(s) +{ +} - Returns the maximum value that QRandomGenerator64 may ever generate. That is, - \c {std::numeric_limits::max()}. +QRandomGenerator64 *QRandomGenerator64::system() +{ + static QRandomGenerator64 system(System{}); + return &system; +} - \sa min(), QRandomGenerator::max() - */ +QRandomGenerator64 *QRandomGenerator64::global() +{ + PRNGLocker lock(nullptr); + static QRandomGenerator64 global(System{}); + if (global.type == SystemRNG) { + // seed with the system CSPRNG and change the type + new (&global.storage.engine()) RandomEngine(static_cast(system()->storage.sys)); + global.type = MersenneTwister; + } -/*! - Generates one 32-bit random value and returns it. + return &global; +} - Note about casting to a signed integer: all bits returned by this function - are random, so there's a 50% chance that the most significant bit will be - set. If you wish to cast the returned value to int and keep it positive, - you should mask the sign bit off: +/// \internal +inline QRandomGenerator::QRandomGenerator(System) + : type(SystemRNG) +{ + Q_STATIC_ASSERT(sizeof(storage) >= sizeof(SystemGenerator)); + new (&storage) SystemGenerator(); +} - \code - int value = QRandomGenerator::generate() & std::numeric_limits::max(); - \endcode - \sa generate64(), generateDouble() - */ -quint32 QRandomGenerator::generate() +QRandomGenerator::QRandomGenerator(const QRandomGenerator &other) + : type(other.type) { - quint32 ret; - fill(&ret, &ret + 1); - return ret; + if (type != SystemRNG) { + PRNGLocker lock(&other); + storage.engine() = other.storage.engine(); + } } -/*! - Generates one 64-bit random value and returns it. +QRandomGenerator &QRandomGenerator::operator=(const QRandomGenerator &other) +{ + if (this != &other) { + if (Q_UNLIKELY(this == system()) || Q_UNLIKELY(this == global())) + qFatal("Attempted to overwrite a QRandomGenerator to system() or global()."); - Note about casting to a signed integer: all bits returned by this function - are random, so there's a 50% chance that the most significant bit will be - set. If you wish to cast the returned value to qint64 and keep it positive, - you should mask the sign bit off: + if ((type = other.type) != SystemRNG) { + PRNGLocker lock(&other); + storage.engine() = other.storage.engine(); + } + } + return *this; +} - \code - qint64 value = QRandomGenerator::generate64() & std::numeric_limits::max(); - \endcode +QRandomGenerator::QRandomGenerator(std::seed_seq &sseq) Q_DECL_NOTHROW + : type(MersenneTwister) +{ + new (&storage.engine()) RandomEngine(sseq); +} - \sa generate(), generateDouble(), QRandomGenerator64 - */ -quint64 QRandomGenerator::generate64() +QRandomGenerator::QRandomGenerator(const quint32 *begin, const quint32 *end) + : type(MersenneTwister) { - quint64 ret; - fill(&ret, &ret + 1); - return ret; + std::seed_seq s(begin, end); + new (&storage.engine()) RandomEngine(s); } /*! @@ -875,9 +1050,19 @@ quint64 QRandomGenerator::generate64() Fills the range pointed by \a buffer and \a bufferEnd with 32-bit random values. The buffer must be correctly aligned. */ -void QRandomGenerator::fillRange_helper(void *buffer, void *bufferEnd) +void QRandomGenerator::_fillRange(void *buffer, void *bufferEnd) { - fill(buffer, bufferEnd); + // Verify that the pointers are properly aligned for 32-bit + Q_ASSERT(quintptr(buffer) % sizeof(quint32) == 0); + Q_ASSERT(quintptr(bufferEnd) % sizeof(quint32) == 0); + quint32 *begin = static_cast(buffer); + quint32 *end = static_cast(bufferEnd); + + if (type == SystemRNG || Q_UNLIKELY(uint(qt_randomdevice_control) & (UseSystemRNG|SetRandomData))) + return SystemGenerator::self().generate(begin, end); + + PRNGLocker lock(this); + std::generate(begin, end, [this]() { return storage.engine()(); }); } #if defined(Q_OS_ANDROID) && (__ANDROID_API__ < 21) diff --git a/src/corelib/global/qrandom.h b/src/corelib/global/qrandom.h index 049495d4e8..e6fd4f02de 100644 --- a/src/corelib/global/qrandom.h +++ b/src/corelib/global/qrandom.h @@ -42,6 +42,7 @@ #include #include // for std::generate +#include // for std::mt19937 QT_BEGIN_NAMESPACE @@ -51,19 +52,37 @@ class QRandomGenerator template using IfValidUInt = typename std::enable_if::value && sizeof(UInt) >= sizeof(uint), bool>::type; public: - static QRandomGenerator system() { return {}; } - static QRandomGenerator global() { return {}; } - QRandomGenerator() = default; - - // ### REMOVE BEFORE 5.10 - QRandomGenerator *operator->() { return this; } - static quint32 get32() { return generate(); } - static quint64 get64() { return generate64(); } - static qreal getReal() { return generateDouble(); } - - static Q_CORE_EXPORT quint32 generate(); - static Q_CORE_EXPORT quint64 generate64(); - static double generateDouble() + QRandomGenerator(quint32 seed = 1) + : QRandomGenerator(&seed, 1) + {} + template QRandomGenerator(const quint32 (&seedBuffer)[N]) + : QRandomGenerator(seedBuffer, seedBuffer + N) + {} + QRandomGenerator(const quint32 *seedBuffer, qssize_t len) + : QRandomGenerator(seedBuffer, seedBuffer + len) + {} + Q_CORE_EXPORT QRandomGenerator(std::seed_seq &sseq) Q_DECL_NOTHROW; + Q_CORE_EXPORT QRandomGenerator(const quint32 *begin, const quint32 *end); + + // copy constructor & assignment operator (move unnecessary) + Q_CORE_EXPORT QRandomGenerator(const QRandomGenerator &other); + Q_CORE_EXPORT QRandomGenerator &operator=(const QRandomGenerator &other); + + quint32 generate() + { + quint32 ret; + fillRange(&ret, 1); + return ret; + } + + quint64 generate64() + { + quint32 buf[2]; + fillRange(buf); + return buf[0] | (quint64(buf[1]) << 32); + } + + double generateDouble() { // IEEE 754 double precision has: // 1 bit sign @@ -77,87 +96,144 @@ public: return double(x) / double(limit); } - static qreal bounded(qreal sup) + double bounded(double highest) { - return generateDouble() * sup; + return generateDouble() * highest; } - static quint32 bounded(quint32 sup) + quint32 bounded(quint32 highest) { quint64 value = generate(); - value *= sup; + value *= highest; value /= (max)() + quint64(1); return quint32(value); } - static int bounded(int sup) + int bounded(int highest) { - return int(bounded(quint32(sup))); + return int(bounded(quint32(highest))); } - static quint32 bounded(quint32 min, quint32 sup) + quint32 bounded(quint32 lowest, quint32 highest) { - return bounded(sup - min) + min; + return bounded(highest - lowest) + lowest; } - static int bounded(int min, int sup) + int bounded(int lowest, int highest) { - return bounded(sup - min) + min; + return bounded(highest - lowest) + lowest; } template = true> - static void fillRange(UInt *buffer, qssize_t count) + void fillRange(UInt *buffer, qssize_t count) { - fillRange_helper(buffer, buffer + count); + _fillRange(buffer, buffer + count); } template = true> - static void fillRange(UInt (&buffer)[N]) + void fillRange(UInt (&buffer)[N]) { - fillRange_helper(buffer, buffer + N); + _fillRange(buffer, buffer + N); } // API like std::seed_seq template void generate(ForwardIterator begin, ForwardIterator end) { - auto generator = static_cast(&QRandomGenerator::generate); - std::generate(begin, end, generator); + std::generate(begin, end, [this]() { return generate(); }); } void generate(quint32 *begin, quint32 *end) { - fillRange_helper(begin, end); + _fillRange(begin, end); } - // API like std::random_device + // API like std:: random engines typedef quint32 result_type; result_type operator()() { return generate(); } - double entropy() const Q_DECL_NOTHROW { return 0.0; } static Q_DECL_CONSTEXPR result_type min() { return (std::numeric_limits::min)(); } static Q_DECL_CONSTEXPR result_type max() { return (std::numeric_limits::max)(); } + static inline QRandomGenerator *system(); + static inline QRandomGenerator *global(); + +protected: + enum System {}; + QRandomGenerator(System); + private: - static Q_CORE_EXPORT void fillRange_helper(void *buffer, void *bufferEnd); + Q_CORE_EXPORT void _fillRange(void *buffer, void *bufferEnd); + + friend class QRandomGenerator64; + struct SystemGeneratorBase {}; + struct SystemGenerator; + typedef std::mt19937 RandomEngine; + + union Storage { + SystemGeneratorBase sys; +#ifdef Q_COMPILER_UNRESTRICTED_UNIONS + RandomEngine twister; + RandomEngine &engine() { return twister; } + const RandomEngine &engine() const { return twister; } +#else + std::aligned_storage::type buffer; + RandomEngine &engine() { return reinterpret_cast(buffer); } + const RandomEngine &engine() const { return reinterpret_cast(buffer); } +#endif + + Q_STATIC_ASSERT_X(std::is_trivially_destructible::value, + "std::mersenne_twister not trivially destructible as expected"); + Storage(); + }; + uint type; + Storage storage; }; -class QRandomGenerator64 +class QRandomGenerator64 : public QRandomGenerator { + QRandomGenerator64(System); public: - static QRandomGenerator64 system() { return {}; } - static QRandomGenerator64 global() { return {}; } - QRandomGenerator64() = default; - - static quint64 generate() { return QRandomGenerator::generate64(); } + // unshadow generate() overloads, since we'll override. + using QRandomGenerator::generate; + quint64 generate() { return generate64(); } - // API like std::random_device typedef quint64 result_type; - result_type operator()() { return QRandomGenerator::generate64(); } - double entropy() const Q_DECL_NOTHROW { return 0.0; } + result_type operator()() { return generate64(); } + +#ifndef Q_QDOC + QRandomGenerator64(quint32 seed = 1) + : QRandomGenerator(seed) + {} + template QRandomGenerator64(const quint32 (&seedBuffer)[N]) + : QRandomGenerator(seedBuffer) + {} + QRandomGenerator64(const quint32 *seedBuffer, qssize_t len) + : QRandomGenerator(seedBuffer, len) + {} + QRandomGenerator64(std::seed_seq &sseq) Q_DECL_NOTHROW + : QRandomGenerator(sseq) + {} + QRandomGenerator64(const quint32 *begin, const quint32 *end) + : QRandomGenerator(begin, end) + {} + QRandomGenerator64(const QRandomGenerator &other) : QRandomGenerator(other) {} + static Q_DECL_CONSTEXPR result_type min() { return (std::numeric_limits::min)(); } static Q_DECL_CONSTEXPR result_type max() { return (std::numeric_limits::max)(); } + static Q_CORE_EXPORT QRandomGenerator64 *system(); + static Q_CORE_EXPORT QRandomGenerator64 *global(); +#endif // Q_QDOC }; +inline QRandomGenerator *QRandomGenerator::system() +{ + return QRandomGenerator64::system(); +} + +inline QRandomGenerator *QRandomGenerator::global() +{ + return QRandomGenerator64::global(); +} QT_END_NAMESPACE diff --git a/src/corelib/global/qrandom_p.h b/src/corelib/global/qrandom_p.h index 525a73cce4..917a91098e 100644 --- a/src/corelib/global/qrandom_p.h +++ b/src/corelib/global/qrandom_p.h @@ -52,10 +52,12 @@ // #include "qglobal_p.h" +#include QT_BEGIN_NAMESPACE enum QRandomGeneratorControl { + UseSystemRNG = 1, SkipSystemRNG = 2, SkipHWRNG = 4, SetRandomData = 8, @@ -64,6 +66,11 @@ enum QRandomGeneratorControl { RandomDataMask = 0xfffffff0 }; +enum RNGType { + SystemRNG = 0, + MersenneTwister = 1 +}; + #if defined(QT_BUILD_INTERNAL) && defined(QT_BUILD_CORE_LIB) Q_CORE_EXPORT QBasicAtomicInteger qt_randomdevice_control = Q_BASIC_ATOMIC_INITIALIZER(0U); #elif defined(QT_BUILD_INTERNAL) @@ -72,6 +79,16 @@ extern Q_CORE_EXPORT QBasicAtomicInteger qt_randomdevice_control; enum { qt_randomdevice_control = 0 }; #endif +inline bool qt_has_hwrng() +{ +#if defined(Q_PROCESSOR_X86) && QT_COMPILER_SUPPORTS_HERE(RDRND) + return qCpuHasFeature(RDRND); +#else + return false; +#endif +} + + QT_END_NAMESPACE #endif // QRANDOM_P_H -- cgit v1.2.3