diff --git a/src/random.cpp b/src/random.cpp index fcc514552..c10eabd78 100644 --- a/src/random.cpp +++ b/src/random.cpp @@ -1,483 +1,484 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "random.h" #include "crypto/sha512.h" #include "support/cleanse.h" #ifdef WIN32 #include "compat.h" // for Windows API #include #endif -#include "sync.h" // for WAIT_LOCK -#include "util.h" // for LogPrint() -#include "utilstrencodings.h" // for GetTime() +#include "logging.h" // for LogPrint() +#include "sync.h" // for WAIT_LOCK +#include "utiltime.h" // for GetTime() #include #include #include #include #ifndef WIN32 +#include #include #endif #ifdef HAVE_SYS_GETRANDOM #include #include #endif #if defined(HAVE_GETENTROPY) || \ (defined(HAVE_GETENTROPY_RAND) && defined(MAC_OSX)) #include #endif #if defined(HAVE_GETENTROPY_RAND) && defined(MAC_OSX) #include #endif #ifdef HAVE_SYSCTL_ARND #include #endif #include #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__) #include #endif #include #include [[noreturn]] static void RandFailure() { LogPrintf("Failed to read randomness, aborting\n"); std::abort(); } static inline int64_t GetPerformanceCounter() { // Read the hardware time stamp counter when available. // See https://en.wikipedia.org/wiki/Time_Stamp_Counter for more information. #if defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_X64)) return __rdtsc(); #elif !defined(_MSC_VER) && defined(__i386__) uint64_t r = 0; // Constrain the r variable to the eax:edx pair. __asm__ volatile("rdtsc" : "=A"(r)); return r; #elif !defined(_MSC_VER) && (defined(__x86_64__) || defined(__amd64__)) uint64_t r1 = 0, r2 = 0; // Constrain r1 to rax and r2 to rdx. __asm__ volatile("rdtsc" : "=a"(r1), "=d"(r2)); return (r2 << 32) | r1; #else // Fall back to using C++11 clock (usually microsecond or nanosecond // precision) return std::chrono::high_resolution_clock::now().time_since_epoch().count(); #endif } #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__) static std::atomic hwrand_initialized{false}; static bool rdrand_supported = false; static constexpr uint32_t CPUID_F1_ECX_RDRAND = 0x40000000; static void RDRandInit() { uint32_t eax, ebx, ecx, edx; if (__get_cpuid(1, &eax, &ebx, &ecx, &edx) && (ecx & CPUID_F1_ECX_RDRAND)) { LogPrintf("Using RdRand as an additional entropy source\n"); rdrand_supported = true; } hwrand_initialized.store(true); } #else static void RDRandInit() {} #endif static bool GetHWRand(uint8_t *ent32) { #if defined(__x86_64__) || defined(__amd64__) || defined(__i386__) assert(hwrand_initialized.load(std::memory_order_relaxed)); if (rdrand_supported) { uint8_t ok; // Not all assemblers support the rdrand instruction, write it in hex. #ifdef __i386__ for (int iter = 0; iter < 4; ++iter) { uint32_t r1, r2; __asm__ volatile(".byte 0x0f, 0xc7, 0xf0;" // rdrand %eax ".byte 0x0f, 0xc7, 0xf2;" // rdrand %edx "setc %2" : "=a"(r1), "=d"(r2), "=q"(ok)::"cc"); if (!ok) { return false; } WriteLE32(ent32 + 8 * iter, r1); WriteLE32(ent32 + 8 * iter + 4, r2); } #else uint64_t r1, r2, r3, r4; __asm__ volatile(".byte 0x48, 0x0f, 0xc7, 0xf0, " // rdrand %rax "0x48, 0x0f, 0xc7, 0xf3, " // rdrand %rbx "0x48, 0x0f, 0xc7, 0xf1, " // rdrand %rcx "0x48, 0x0f, 0xc7, 0xf2; " // rdrand %rdx "setc %4" : "=a"(r1), "=b"(r2), "=c"(r3), "=d"(r4), "=q"(ok)::"cc"); if (!ok) { return false; } WriteLE64(ent32, r1); WriteLE64(ent32 + 8, r2); WriteLE64(ent32 + 16, r3); WriteLE64(ent32 + 24, r4); #endif return true; } #endif return false; } void RandAddSeed() { // Seed with CPU performance counter int64_t nCounter = GetPerformanceCounter(); RAND_add(&nCounter, sizeof(nCounter), 1.5); memory_cleanse((void *)&nCounter, sizeof(nCounter)); } static void RandAddSeedPerfmon() { RandAddSeed(); #ifdef WIN32 // Don't need this on Linux, OpenSSL automatically uses /dev/urandom // Seed with the entire set of perfmon data // This can take up to 2 seconds, so only do it every 10 minutes static int64_t nLastPerfmon; if (GetTime() < nLastPerfmon + 10 * 60) { return; } nLastPerfmon = GetTime(); std::vector vData(250000, 0); long ret = 0; unsigned long nSize = 0; // Bail out at more than 10MB of performance data const size_t nMaxSize = 10000000; while (true) { nSize = vData.size(); ret = RegQueryValueExA(HKEY_PERFORMANCE_DATA, "Global", nullptr, nullptr, vData.data(), &nSize); if (ret != ERROR_MORE_DATA || vData.size() >= nMaxSize) { break; } // Grow size of buffer exponentially vData.resize(std::max((vData.size() * 3) / 2, nMaxSize)); } RegCloseKey(HKEY_PERFORMANCE_DATA); if (ret == ERROR_SUCCESS) { RAND_add(vData.data(), nSize, nSize / 100.0); memory_cleanse(vData.data(), nSize); LogPrint(BCLog::RAND, "%s: %lu bytes\n", __func__, nSize); } else { // Warn only once static bool warned = false; if (!warned) { LogPrintf("%s: Warning: RegQueryValueExA(HKEY_PERFORMANCE_DATA) " "failed with code %i\n", __func__, ret); warned = true; } } #endif } #ifndef WIN32 /** * Fallback: get 32 bytes of system entropy from /dev/urandom. The most * compatible way to get cryptographic randomness on UNIX-ish platforms. */ static void GetDevURandom(uint8_t *ent32) { int f = open("/dev/urandom", O_RDONLY); if (f == -1) { RandFailure(); } int have = 0; do { ssize_t n = read(f, ent32 + have, NUM_OS_RANDOM_BYTES - have); if (n <= 0 || n + have > NUM_OS_RANDOM_BYTES) { close(f); RandFailure(); } have += n; } while (have < NUM_OS_RANDOM_BYTES); close(f); } #endif /** Get 32 bytes of system entropy. */ void GetOSRand(uint8_t *ent32) { #if defined(WIN32) HCRYPTPROV hProvider; int ret = CryptAcquireContextW(&hProvider, nullptr, nullptr, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT); if (!ret) { RandFailure(); } ret = CryptGenRandom(hProvider, NUM_OS_RANDOM_BYTES, ent32); if (!ret) { RandFailure(); } CryptReleaseContext(hProvider, 0); #elif defined(HAVE_SYS_GETRANDOM) /** * Linux. From the getrandom(2) man page: * "If the urandom source has been initialized, reads of up to 256 bytes * will always return as many bytes as requested and will not be interrupted * by signals." */ int rv = syscall(SYS_getrandom, ent32, NUM_OS_RANDOM_BYTES, 0); if (rv != NUM_OS_RANDOM_BYTES) { if (rv < 0 && errno == ENOSYS) { /* Fallback for kernel <3.17: the return value will be -1 and errno * ENOSYS if the syscall is not available, in that case fall back * to /dev/urandom. */ GetDevURandom(ent32); } else { RandFailure(); } } #elif defined(HAVE_GETENTROPY) && defined(__OpenBSD__) /** * On OpenBSD this can return up to 256 bytes of entropy, will return an * error if more are requested. * The call cannot return less than the requested number of bytes. * getentropy is explicitly limited to openbsd here, as a similar (but not * the same) function may exist on other platforms via glibc. */ if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) { RandFailure(); } #elif defined(HAVE_GETENTROPY_RAND) && defined(MAC_OSX) // We need a fallback for OSX < 10.12 if (&getentropy != nullptr) { if (getentropy(ent32, NUM_OS_RANDOM_BYTES) != 0) { RandFailure(); } } else { GetDevURandom(ent32); } #elif defined(HAVE_SYSCTL_ARND) /** * FreeBSD and similar. It is possible for the call to return less bytes * than requested, so need to read in a loop. */ static const int name[2] = {CTL_KERN, KERN_ARND}; int have = 0; do { size_t len = NUM_OS_RANDOM_BYTES - have; if (sysctl(name, ARRAYLEN(name), ent32 + have, &len, nullptr, 0) != 0) { RandFailure(); } have += len; } while (have < NUM_OS_RANDOM_BYTES); #else /** * Fall back to /dev/urandom if there is no specific method implemented to * get system entropy for this OS. */ GetDevURandom(ent32); #endif } void GetRandBytes(uint8_t *buf, int num) { if (RAND_bytes(buf, num) != 1) { RandFailure(); } } static void AddDataToRng(void *data, size_t len); void RandAddSeedSleep() { int64_t nPerfCounter1 = GetPerformanceCounter(); std::this_thread::sleep_for(std::chrono::milliseconds(1)); int64_t nPerfCounter2 = GetPerformanceCounter(); // Combine with and update state AddDataToRng(&nPerfCounter1, sizeof(nPerfCounter1)); AddDataToRng(&nPerfCounter2, sizeof(nPerfCounter2)); memory_cleanse(&nPerfCounter1, sizeof(nPerfCounter1)); memory_cleanse(&nPerfCounter2, sizeof(nPerfCounter2)); } static CWaitableCriticalSection cs_rng_state; static uint8_t rng_state[32] = {0}; static uint64_t rng_counter = 0; static void AddDataToRng(void *data, size_t len) { CSHA512 hasher; hasher.Write((const uint8_t *)&len, sizeof(len)); hasher.Write((const uint8_t *)data, len); uint8_t buf[64]; { WAIT_LOCK(cs_rng_state, lock); hasher.Write(rng_state, sizeof(rng_state)); hasher.Write((const uint8_t *)&rng_counter, sizeof(rng_counter)); ++rng_counter; hasher.Finalize(buf); memcpy(rng_state, buf + 32, 32); } memory_cleanse(buf, 64); } void GetStrongRandBytes(uint8_t *out, int num) { assert(num <= 32); CSHA512 hasher; uint8_t buf[64]; // First source: OpenSSL's RNG RandAddSeedPerfmon(); GetRandBytes(buf, 32); hasher.Write(buf, 32); // Second source: OS RNG GetOSRand(buf); hasher.Write(buf, 32); // Third source: HW RNG, if available. if (GetHWRand(buf)) { hasher.Write(buf, 32); } // Combine with and update state { WAIT_LOCK(cs_rng_state, lock); hasher.Write(rng_state, sizeof(rng_state)); hasher.Write((const uint8_t *)&rng_counter, sizeof(rng_counter)); ++rng_counter; hasher.Finalize(buf); memcpy(rng_state, buf + 32, 32); } // Produce output memcpy(out, buf, num); memory_cleanse(buf, 64); } uint64_t GetRand(uint64_t nMax) { if (nMax == 0) { return 0; } // The range of the random source must be a multiple of the modulus to give // every possible output value an equal possibility uint64_t nRange = (std::numeric_limits::max() / nMax) * nMax; uint64_t nRand = 0; do { GetRandBytes((uint8_t *)&nRand, sizeof(nRand)); } while (nRand >= nRange); return (nRand % nMax); } int GetRandInt(int nMax) { return GetRand(nMax); } uint256 GetRandHash() { uint256 hash; GetRandBytes((uint8_t *)&hash, sizeof(hash)); return hash; } void FastRandomContext::RandomSeed() { uint256 seed = GetRandHash(); rng.SetKey(seed.begin(), 32); requires_seed = false; } uint256 FastRandomContext::rand256() { if (bytebuf_size < 32) { FillByteBuffer(); } uint256 ret; memcpy(ret.begin(), bytebuf + 64 - bytebuf_size, 32); bytebuf_size -= 32; return ret; } std::vector FastRandomContext::randbytes(size_t len) { std::vector ret(len); if (len > 0) { rng.Output(&ret[0], len); } return ret; } FastRandomContext::FastRandomContext(const uint256 &seed) : requires_seed(false), bytebuf_size(0), bitbuf_size(0) { rng.SetKey(seed.begin(), 32); } bool Random_SanityCheck() { uint64_t start = GetPerformanceCounter(); /** * This does not measure the quality of randomness, but it does test that * OSRandom() overwrites all 32 bytes of the output given a maximum number * of tries. */ static const ssize_t MAX_TRIES = 1024; uint8_t data[NUM_OS_RANDOM_BYTES]; /* Tracks which bytes have been overwritten at least once */ bool overwritten[NUM_OS_RANDOM_BYTES] = {}; int num_overwritten; int tries = 0; /** * Loop until all bytes have been overwritten at least once, or max number * tries reached. */ do { memset(data, 0, NUM_OS_RANDOM_BYTES); GetOSRand(data); for (int x = 0; x < NUM_OS_RANDOM_BYTES; ++x) { overwritten[x] |= (data[x] != 0); } num_overwritten = 0; for (int x = 0; x < NUM_OS_RANDOM_BYTES; ++x) { if (overwritten[x]) { num_overwritten += 1; } } tries += 1; } while (num_overwritten < NUM_OS_RANDOM_BYTES && tries < MAX_TRIES); /* If this failed, bailed out after too many tries */ if (num_overwritten != NUM_OS_RANDOM_BYTES) { return false; } // Check that GetPerformanceCounter increases at least during a GetOSRand() // call + 1ms sleep. std::this_thread::sleep_for(std::chrono::milliseconds(1)); uint64_t stop = GetPerformanceCounter(); if (stop == start) { return false; } // We called GetPerformanceCounter. Use it as entropy. RAND_add((const uint8_t *)&start, sizeof(start), 1); RAND_add((const uint8_t *)&stop, sizeof(stop), 1); return true; } FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDeterministic), bytebuf_size(0), bitbuf_size(0) { if (!fDeterministic) { return; } uint256 seed; rng.SetKey(seed.begin(), 32); } void RandomInit() { RDRandInit(); } diff --git a/src/sync.cpp b/src/sync.cpp index 870b53c77..359085e92 100644 --- a/src/sync.cpp +++ b/src/sync.cpp @@ -1,201 +1,203 @@ // Copyright (c) 2011-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "sync.h" -#include "util.h" +#include "logging.h" #include "utilstrencodings.h" #include +#include +#include #include #ifdef DEBUG_LOCKCONTENTION void PrintLockContention(const char *pszName, const char *pszFile, int nLine) { LogPrintf("LOCKCONTENTION: %s\n", pszName); LogPrintf("Locker: %s:%d\n", pszFile, nLine); } #endif /* DEBUG_LOCKCONTENTION */ #ifdef DEBUG_LOCKORDER // // Early deadlock detection. // Problem being solved: // Thread 1 locks A, then B, then C // Thread 2 locks D, then C, then A // --> may result in deadlock between the two threads, depending on when // they run. // Solution implemented here: // Keep track of pairs of locks: (A before B), (A before C), etc. // Complain if any thread tries to lock in a different order. // struct CLockLocation { CLockLocation(const char *pszName, const char *pszFile, int nLine, bool fTryIn) { mutexName = pszName; sourceFile = pszFile; sourceLine = nLine; fTry = fTryIn; } std::string ToString() const { return mutexName + " " + sourceFile + ":" + itostr(sourceLine) + (fTry ? " (TRY)" : ""); } private: bool fTry; std::string mutexName; std::string sourceFile; int sourceLine; }; typedef std::vector> LockStack; typedef std::map, LockStack> LockOrders; typedef std::set> InvLockOrders; struct LockData { // Very ugly hack: as the global constructs and destructors run single // threaded, we use this boolean to know whether LockData still exists, // as DeleteLock can get called by global CCriticalSection destructors // after LockData disappears. bool available; LockData() : available(true) {} ~LockData() { available = false; } LockOrders lockorders; InvLockOrders invlockorders; std::mutex dd_mutex; } static lockdata; static thread_local std::unique_ptr lockstack; static void potential_deadlock_detected(const std::pair &mismatch, const LockStack &s1, const LockStack &s2) { LogPrintf("POTENTIAL DEADLOCK DETECTED\n"); LogPrintf("Previous lock order was:\n"); for (const std::pair &i : s2) { if (i.first == mismatch.first) { LogPrintf(" (1)"); } if (i.first == mismatch.second) { LogPrintf(" (2)"); } LogPrintf(" %s\n", i.second.ToString()); } LogPrintf("Current lock order is:\n"); for (const std::pair &i : s1) { if (i.first == mismatch.first) { LogPrintf(" (1)"); } if (i.first == mismatch.second) { LogPrintf(" (2)"); } LogPrintf(" %s\n", i.second.ToString()); } if (g_debug_lockorder_abort) { fprintf(stderr, "Assertion failed: detected inconsistent lock order at " "%s:%i, details in debug log.\n", __FILE__, __LINE__); abort(); } throw std::logic_error("potential deadlock detected"); } static void push_lock(void *c, const CLockLocation &locklocation) { if (!lockstack) { lockstack.reset(new LockStack); } std::lock_guard lock(lockdata.dd_mutex); lockstack->push_back(std::make_pair(c, locklocation)); for (const std::pair &i : (*lockstack)) { if (i.first == c) break; std::pair p1 = std::make_pair(i.first, c); if (lockdata.lockorders.count(p1)) continue; lockdata.lockorders[p1] = (*lockstack); std::pair p2 = std::make_pair(c, i.first); lockdata.invlockorders.insert(p2); if (lockdata.lockorders.count(p2)) potential_deadlock_detected(p1, lockdata.lockorders[p2], lockdata.lockorders[p1]); } } static void pop_lock() { (*lockstack).pop_back(); } void EnterCritical(const char *pszName, const char *pszFile, int nLine, void *cs, bool fTry) { push_lock(cs, CLockLocation(pszName, pszFile, nLine, fTry)); } void LeaveCritical() { pop_lock(); } std::string LocksHeld() { std::string result; for (const std::pair &i : *lockstack) { result += i.second.ToString() + std::string("\n"); } return result; } void AssertLockHeldInternal(const char *pszName, const char *pszFile, int nLine, void *cs) { for (const std::pair &i : *lockstack) { if (i.first == cs) return; } fprintf(stderr, "Assertion failed: lock %s not held in %s:%i; locks held:\n%s", pszName, pszFile, nLine, LocksHeld().c_str()); abort(); } void AssertLockNotHeldInternal(const char *pszName, const char *pszFile, int nLine, void *cs) { for (const std::pair &i : *lockstack) { if (i.first == cs) { fprintf(stderr, "Assertion failed: lock %s held in %s:%i; locks held:\n%s", pszName, pszFile, nLine, LocksHeld().c_str()); abort(); } } } void DeleteLock(void *cs) { if (!lockdata.available) { // We're already shutting down. return; } std::lock_guard lock(lockdata.dd_mutex); std::pair item = std::make_pair(cs, nullptr); LockOrders::iterator it = lockdata.lockorders.lower_bound(item); while (it != lockdata.lockorders.end() && it->first.first == cs) { std::pair invitem = std::make_pair(it->first.second, it->first.first); lockdata.invlockorders.erase(invitem); lockdata.lockorders.erase(it++); } InvLockOrders::iterator invit = lockdata.invlockorders.lower_bound(item); while (invit != lockdata.invlockorders.end() && invit->first == cs) { std::pair invinvitem = std::make_pair(invit->second, invit->first); lockdata.lockorders.erase(invinvitem); lockdata.invlockorders.erase(invit++); } } bool g_debug_lockorder_abort = true; #endif /* DEBUG_LOCKORDER */