qrandom.cpp

Go to the documentation of this file.

/****************************************************************************
**
** Copyright (C) 2021 Intel Corporation.
** Copyright (C) 2021 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/
 
// for rand_s
#define _CRT_RAND_S
 
#include "qrandom.h"
#include "qrandom_p.h"
#include <qendian.h>
#include <qmutex.h>
#include <qobjectdefs.h>
#include <qthreadstorage.h>
 
#include <errno.h>
 
#if QT_CONFIG(getauxval)
#  include <sys/auxv.h>
#endif
 
#if QT_CONFIG(getentropy) && __has_include(<sys/random.h>)
#  include <sys/random.h>
#elif !QT_CONFIG(getentropy) && (!defined(Q_OS_BSD4) || defined(__GLIBC__)) && !defined(Q_OS_WIN)
#  include "qdeadlinetimer.h"
#  include "qhashfunctions.h"
#endif // !QT_CONFIG(getentropy)
 
#ifdef Q_OS_UNIX
#  include <fcntl.h>
#  include <private/qcore_unix_p.h>
#else
#  include <qt_windows.h>
 
// RtlGenRandom is not exported by its name in advapi32.dll, but as SystemFunction036
// See https://msdn.microsoft.com/en-us/library/windows/desktop/aa387694(v=vs.85).aspx
// Implementation inspired on https://hg.mozilla.org/mozilla-central/file/722fdbff1efc/security/nss/lib/freebl/win_rand.c#l146
// Argument why this is safe to use: https://bugzilla.mozilla.org/show_bug.cgi?id=504270
extern "C" {
DECLSPEC_IMPORT BOOLEAN WINAPI SystemFunction036(PVOID RandomBuffer, ULONG RandomBufferLength);
}
#endif
 
// This file is too low-level for regular Q_ASSERT (the logging framework may
// recurse back), so use regular assert()
#undef NDEBUG
#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
#include <assert.h>
 
QT_BEGIN_NAMESPACE
 
enum {
    // may be "overridden" by a member enum
    FillBufferNoexcept = true
};
 
#if defined(QT_BUILD_INTERNAL)
QBasicAtomicInteger<uint> qt_randomdevice_control = Q_BASIC_ATOMIC_INITIALIZER(0U);
#endif
 
struct QRandomGenerator::SystemGenerator
{
#if QT_CONFIG(getentropy)
    static qsizetype fillBuffer(void *buffer, qsizetype count) noexcept
    {
        // getentropy can read at most 256 bytes, so break the reading
        qsizetype read = 0;
        while (count - read > 256) {
            // getentropy can't fail under normal circumstances
            int ret = getentropy(reinterpret_cast<uchar *>(buffer) + read, 256);
            Q_ASSERT(ret == 0);
            Q_UNUSED(ret);
            read += 256;
        }
 
        int ret = getentropy(reinterpret_cast<uchar *>(buffer) + read, count - read);
        Q_ASSERT(ret == 0);
        Q_UNUSED(ret);
        return count;
    }
 
#elif defined(Q_OS_UNIX)
    enum { FillBufferNoexcept = false };
 
    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;
        }
 
        int opened_fdp1;
        if (fdp1.testAndSetOrdered(0, fd + 1, opened_fdp1))
            return fd;
 
        // failed, another thread has opened the file descriptor
        if (fd >= 0)
            qt_safe_close(fd);
        return opened_fdp1 - 1;
    }
 
#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 = self().fdp1.loadRelaxed() - 1;
        if (fd >= 0)
            qt_safe_close(fd);
    }
 
    constexpr SystemGenerator() : fdp1 Q_BASIC_ATOMIC_INITIALIZER(0) {}
 
    qsizetype fillBuffer(void *buffer, qsizetype count)
    {
        int fd = openDevice();
        if (Q_UNLIKELY(fd < 0))
            return 0;
 
        qint64 n = qt_safe_read(fd, buffer, count);
        return qMax<qsizetype>(n, 0);        // ignore any errors
    }
 
#elif defined(Q_OS_WIN)
    static qsizetype fillBuffer(void *buffer, qsizetype count) noexcept
    {
        auto RtlGenRandom = SystemFunction036;
        return RtlGenRandom(buffer, ULONG(count)) ? count: 0;
    }
#endif // Q_OS_WIN
 
    static SystemGenerator &self();
    typedef quint32 result_type;
    void generate(quint32 *begin, quint32 *end) noexcept(FillBufferNoexcept);
 
    // For std::mersenne_twister_engine implementations that use something
    // other than quint32 (unsigned int) to fill their buffers.
    template<typename T>
    void generate(T *begin, T *end)
    {
        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<quint32 *>(begin), reinterpret_cast<quint32 *>(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) {}
static void fallback_fill(quint32 *ptr, qsizetype left) noexcept
{
    // on Windows, rand_s is a high-quality random number generator
    // and it requires no seeding
    std::generate(ptr, ptr + left, []() {
        unsigned value;
        rand_s(&value);
        return value;
    });
}
#elif QT_CONFIG(getentropy)
static void fallback_update_seed(unsigned) {}
static void fallback_fill(quint32 *, qsizetype) noexcept
{
    // no fallback necessary, getentropy cannot fail under normal circumstances
    Q_UNREACHABLE();
}
#elif defined(Q_OS_BSD4) && !defined(__GLIBC__)
static void fallback_update_seed(unsigned) {}
static void fallback_fill(quint32 *ptr, qsizetype left) noexcept
{
    // BSDs have arc4random(4) and these work even in chroot(2)
    arc4random_buf(ptr, left * sizeof(*ptr));
}
#else
static QBasicAtomicInteger<unsigned> seed = Q_BASIC_ATOMIC_INITIALIZER(0U);
static void fallback_update_seed(unsigned value)
{
    // Update the seed to be used for the fallback mechanism, if we need to.
    // We can't use QtPrivate::QHashCombine here because that is not an atomic
    // operation. A simple XOR will have to do then.
    seed.fetchAndXorRelaxed(value);
}
 
Q_NEVER_INLINE
#ifdef Q_CC_GNU
__attribute__((cold))   // this function is pretty big, so optimize for size
#endif
static void fallback_fill(quint32 *ptr, qsizetype left) noexcept
{
    quint32 scratch[12];    // see element count below
    quint32 *end = scratch;
 
    auto foldPointer = [](quintptr v) {
        if (sizeof(quintptr) == sizeof(quint32)) {
            // For 32-bit systems, we simply return the pointer.
            return quint32(v);
        } else {
            // For 64-bit systems, we try to return the variable part of the
            // pointer. On current x86-64 and AArch64, the top 17 bits are
            // architecturally required to be the same, but in reality the top
            // 24 bits on Linux are likely to be the same for all processes.
            return quint32(v >> (32 - 24));
        }
    };
 
    Q_ASSERT(left);
 
    *end++ = foldPointer(quintptr(&seed));          // 1: variable in this library/executable's .data
    *end++ = foldPointer(quintptr(&scratch));       // 2: variable in the stack
    *end++ = foldPointer(quintptr(&errno));         // 3: veriable either in libc or thread-specific
    *end++ = foldPointer(quintptr(reinterpret_cast<void*>(strerror)));   // 4: function in libc (and unlikely to be a macro)
 
#ifndef QT_BOOTSTRAPPED
    quint64 nsecs = QDeadlineTimer::current(Qt::PreciseTimer).deadline();
    *end++ = quint32(nsecs);    // 5
#endif
 
    if (quint32 v = seed.loadRelaxed())
        *end++ = v; // 6
 
#if QT_CONFIG(getauxval)
    // works on Linux -- all modern libc have getauxval
#  ifdef AT_RANDOM
    // ELF's auxv AT_RANDOM has 16 random bytes
    // (other ELF-based systems don't seem to have AT_RANDOM)
    ulong auxvSeed = getauxval(AT_RANDOM);
    if (auxvSeed) {
        memcpy(end, reinterpret_cast<void *>(auxvSeed), 16);
        end += 4;   // 7 to 10
    }
#  endif
 
    // Both AT_BASE and AT_SYSINFO_EHDR have some randomness in them due to the
    // system's ASLR, even if many bits are the same. They also have randomness
    // between them.
#  ifdef AT_BASE
    // present at least on the BSDs too, indicates the address of the loader
    ulong base = getauxval(AT_BASE);
    if (base)
        *end++ = foldPointer(base); // 11
#  endif
#  ifdef AT_SYSINFO_EHDR
    // seems to be Linux-only, indicates the global page of the sysinfo
    ulong sysinfo_ehdr = getauxval(AT_SYSINFO_EHDR);
    if (sysinfo_ehdr)
        *end++ = foldPointer(sysinfo_ehdr); // 12
#  endif
#endif
 
    Q_ASSERT(end <= std::end(scratch));
 
    // this is highly inefficient, we should save the generator across calls...
    std::seed_seq sseq(scratch, end);
    std::mt19937 generator(sseq);
    std::generate(ptr, ptr + left, generator);
 
    fallback_update_seed(*ptr);
}
#endif
 
Q_NEVER_INLINE void QRandomGenerator::SystemGenerator::generate(quint32 *begin, quint32 *end)
    noexcept(FillBufferNoexcept)
{
    quint32 *buffer = begin;
    qsizetype count = end - begin;
 
    if (Q_UNLIKELY(uint(qt_randomdevice_control.loadAcquire()) & SetRandomData)) {
        uint value = uint(qt_randomdevice_control.loadAcquire()) & RandomDataMask;
        std::fill_n(buffer, count, value);
        return;
    }
 
    qsizetype filled = 0;
    if (qHasHwrng() && (uint(qt_randomdevice_control.loadAcquire()) & SkipHWRNG) == 0)
        filled += qRandomCpu(buffer, count);
 
    if (filled != count && (uint(qt_randomdevice_control.loadAcquire()) & SkipSystemRNG) == 0) {
        qsizetype bytesFilled =
                fillBuffer(buffer + filled, (count - filled) * qsizetype(sizeof(*buffer)));
        filled += bytesFilled / qsizetype(sizeof(*buffer));
    }
    if (filled)
        fallback_update_seed(*buffer);
 
    if (Q_UNLIKELY(filled != count)) {
        // failed to fill the entire buffer, try the faillback mechanism
        fallback_fill(buffer + filled, count - filled);
    }
}
 
struct QRandomGenerator::SystemAndGlobalGenerators
{
    // Construction notes:
    // 1) The global PRNG state is in a different cacheline compared to the
    //    mutex that protects it. This avoids any false cacheline sharing of
    //    the state in case another thread tries to lock the mutex. It's not
    //    a common scenario, but since sizeof(QRandomGenerator) >= 2560, the
    //    overhead is actually acceptable.
    // 2) We use both alignas(T) and alignas(64) because some implementations
    //    can't align to more than a primitive type's alignment.
    // 3) We don't store the entire system QRandomGenerator, only the space
    //    used by the QRandomGenerator::type member. This is fine because we
    //    (ab)use the common initial sequence exclusion to aliasing rules.
    QBasicMutex globalPRNGMutex;
    struct ShortenedSystem { uint type; } system_;
    SystemGenerator sys;
    alignas(64) struct {
        alignas(QRandomGenerator64) uchar data[sizeof(QRandomGenerator64)];
    } global_;
 
    constexpr SystemAndGlobalGenerators()
        : globalPRNGMutex{}, system_{0}, sys{}, global_{}
    {}
 
    void confirmLiteral()
    {
#if !defined(Q_OS_INTEGRITY)
        // Integrity's compiler is unable to guarantee g's alignment for some reason.
        constexpr SystemAndGlobalGenerators g = {};
        Q_UNUSED(g);
#endif
    }
 
    static SystemAndGlobalGenerators *self()
    {
        static SystemAndGlobalGenerators g;
        static_assert(sizeof(g) > sizeof(QRandomGenerator64));
        return &g;
    }
 
    static QRandomGenerator64 *system()
    {
        // Though we never call the constructor, the system QRandomGenerator is
        // properly initialized by the zero initialization performed in self().
        // Though QRandomGenerator is has non-vacuous initialization, we
        // consider it initialized because of the common initial sequence.
        return reinterpret_cast<QRandomGenerator64 *>(&self()->system_);
    }
 
    static QRandomGenerator64 *globalNoInit()
    {
        // This function returns the pointer to the global QRandomGenerator,
        // but does not initialize it. Only call it directly if you meant to do
        // a pointer comparison.
        return reinterpret_cast<QRandomGenerator64 *>(&self()->global_);
    }
 
    static void securelySeed(QRandomGenerator *rng)
    {
        // force reconstruction, just to be pedantic
        new (rng) QRandomGenerator{System{}};
 
        rng->type = MersenneTwister;
        new (&rng->storage.engine()) RandomEngine(self()->sys);
    }
 
    struct PRNGLocker
    {
        const bool locked;
        PRNGLocker(const QRandomGenerator *that)
            : locked(that == globalNoInit())
        {
            if (locked)
                self()->globalPRNGMutex.lock();
        }
        ~PRNGLocker()
        {
            if (locked)
                self()->globalPRNGMutex.unlock();
        }
    };
};
 
inline QRandomGenerator::SystemGenerator &QRandomGenerator::SystemGenerator::self()
{
    return SystemAndGlobalGenerators::self()->sys;
}
 
constexpr QRandomGenerator::Storage::Storage()
    : dummy(0)
{
    // nothing
}
 
inline QRandomGenerator64::QRandomGenerator64(System s)
    : QRandomGenerator(s)
{
}
 
QRandomGenerator64 *QRandomGenerator64::system()
{
    auto self = SystemAndGlobalGenerators::system();
    Q_ASSERT(self->type == SystemRNG);
    return self;
}
 
QRandomGenerator64 *QRandomGenerator64::global()
{
    auto self = SystemAndGlobalGenerators::globalNoInit();
 
    // Yes, this is a double-checked lock.
    // We can return even if the type is not completely initialized yet:
    // any thread trying to actually use the contents of the random engine
    // will necessarily wait on the lock.
    if (Q_LIKELY(self->type != SystemRNG))
        return self;
 
    SystemAndGlobalGenerators::PRNGLocker locker(self);
    if (self->type == SystemRNG)
        SystemAndGlobalGenerators::securelySeed(self);
 
    return self;
}
 
QRandomGenerator64 QRandomGenerator64::securelySeeded()
{
    QRandomGenerator64 result(System{});
    SystemAndGlobalGenerators::securelySeed(&result);
    return result;
}
 
inline QRandomGenerator::QRandomGenerator(System)
    : type(SystemRNG)
{
    // don't touch storage
}
 
QRandomGenerator::QRandomGenerator(const QRandomGenerator &other)
    : type(other.type)
{
    Q_ASSERT(this != system());
    Q_ASSERT(this != SystemAndGlobalGenerators::globalNoInit());
 
    if (type != SystemRNG) {
        SystemAndGlobalGenerators::PRNGLocker lock(&other);
        storage.engine() = other.storage.engine();
    }
}
 
QRandomGenerator &QRandomGenerator::operator=(const QRandomGenerator &other)
{
    if (Q_UNLIKELY(this == system()) || Q_UNLIKELY(this == SystemAndGlobalGenerators::globalNoInit()))
        qFatal("Attempted to overwrite a QRandomGenerator to system() or global().");
 
    if ((type = other.type) != SystemRNG) {
        SystemAndGlobalGenerators::PRNGLocker lock(&other);
        storage.engine() = other.storage.engine();
    }
    return *this;
}
 
QRandomGenerator::QRandomGenerator(std::seed_seq &sseq) noexcept
    : type(MersenneTwister)
{
    Q_ASSERT(this != system());
    Q_ASSERT(this != SystemAndGlobalGenerators::globalNoInit());
 
    new (&storage.engine()) RandomEngine(sseq);
}
 
QRandomGenerator::QRandomGenerator(const quint32 *begin, const quint32 *end)
    : type(MersenneTwister)
{
    Q_ASSERT(this != system());
    Q_ASSERT(this != SystemAndGlobalGenerators::globalNoInit());
 
    std::seed_seq s(begin, end);
    new (&storage.engine()) RandomEngine(s);
}
 
void QRandomGenerator::discard(unsigned long long z)
{
    if (Q_UNLIKELY(type == SystemRNG))
        return;
 
    SystemAndGlobalGenerators::PRNGLocker lock(this);
    storage.engine().discard(z);
}
 
bool operator==(const QRandomGenerator &rng1, const QRandomGenerator &rng2)
{
    if (rng1.type != rng2.type)
        return false;
    if (rng1.type == SystemRNG)
        return true;
 
    // Lock global() if either is it (otherwise this locking is a no-op)
    using PRNGLocker = QRandomGenerator::SystemAndGlobalGenerators::PRNGLocker;
    PRNGLocker locker(&rng1 == QRandomGenerator::global() ? &rng1 : &rng2);
    return rng1.storage.engine() == rng2.storage.engine();
}
 
quint64 QRandomGenerator::_fillRange(void *buffer, qptrdiff count)
{
    // Verify that the pointers are properly aligned for 32-bit
    Q_ASSERT(quintptr(buffer) % sizeof(quint32) == 0);
    Q_ASSERT(count >= 0);
    Q_ASSERT(buffer || count <= 2);
 
    quint64 dummy;
    quint32 *begin = static_cast<quint32 *>(buffer ? buffer : &dummy);
    quint32 *end = begin + count;
 
    if (type == SystemRNG || Q_UNLIKELY(uint(qt_randomdevice_control.loadAcquire()) & (UseSystemRNG|SetRandomData))) {
        SystemGenerator::self().generate(begin, end);
    } else {
        SystemAndGlobalGenerators::PRNGLocker lock(this);
        std::generate(begin, end, [this]() { return storage.engine()(); });
    }
 
    if (end - begin == 1)
        return *begin;
    return begin[0] | (quint64(begin[1]) << 32);
}
 
// helper function to call fillBuffer, since we need something to be
// argument-dependent
template <typename Generator, typename FillBufferType, typename T>
static qsizetype callFillBuffer(FillBufferType f, T *v)
{
    if constexpr (std::is_member_function_pointer_v<FillBufferType>) {
        // member function, need an object
        return (Generator::self().*f)(v, sizeof(*v));
    } else {
        // static, call directly
        return f(v, sizeof(*v));
    }
}
 
QRandomGenerator::InitialRandomData qt_initial_random_value() noexcept
{
#if QT_CONFIG(getauxval) && defined(AT_RANDOM)
    auto at_random_ptr = reinterpret_cast<size_t *>(getauxval(AT_RANDOM));
    if (at_random_ptr)
        return qFromUnaligned<QRandomGenerator::InitialRandomData>(at_random_ptr);
#endif
 
    // bypass the hardware RNG, which would mean initializing qsimd.cpp
 
    QRandomGenerator::InitialRandomData v;
    for (int attempts = 16; attempts; --attempts) {
        using Generator = QRandomGenerator::SystemGenerator;
        auto fillBuffer = &Generator::fillBuffer;
        if (callFillBuffer<Generator>(fillBuffer, &v) != sizeof(v))
            continue;
 
        return v;
    }
 
    quint32 data[sizeof(v) / sizeof(quint32)];
    fallback_fill(data, std::size(data));
    memcpy(v.data, data, sizeof(v.data));
    return v;
}
 
QT_END_NAMESPACE