diff --git a/src/Makefile.test.include b/src/Makefile.test.include index 2bab78142c..4a64145c4d 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -1,192 +1,193 @@ # Copyright (c) 2013-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. TESTS += test/test_bitcoin LOG_DRIVER = $(srcdir)/test/test-bitcoin-driver EXTRA_DIST += test/test-bitcoin-driver bin_PROGRAMS += test/test_bitcoin noinst_PROGRAMS += test/test_bitcoin_fuzzy TEST_SRCDIR = test TEST_BINARY=test/test_bitcoin$(EXEEXT) JSON_TEST_FILES = \ test/data/script_tests.json \ test/data/base58_keys_valid.json \ test/data/base58_encode_decode.json \ test/data/base58_keys_invalid.json \ test/data/tx_invalid.json \ test/data/tx_valid.json \ test/data/sighash.json RAW_TEST_FILES = GENERATED_TEST_FILES = $(JSON_TEST_FILES:.json=.json.h) $(RAW_TEST_FILES:.raw=.raw.h) # test_bitcoin binary # BITCOIN_TESTS =\ test/arith_uint256_tests.cpp \ test/scriptnum10.h \ test/addrman_tests.cpp \ test/amount_tests.cpp \ test/allocator_tests.cpp \ test/base32_tests.cpp \ test/base58_tests.cpp \ test/base64_tests.cpp \ test/bip32_tests.cpp \ test/blockcheck_tests.cpp \ test/blockencodings_tests.cpp \ test/blockindex_tests.cpp \ test/blockstatus_tests.cpp \ test/bloom_tests.cpp \ test/bswap_tests.cpp \ test/cashaddr_tests.cpp \ test/cashaddrenc_tests.cpp \ test/checkdatasig_tests.cpp \ test/checkpoints_tests.cpp \ + test/checkqueue_tests.cpp \ test/coins_tests.cpp \ test/compress_tests.cpp \ test/config_tests.cpp \ test/core_io_tests.cpp \ test/crypto_tests.cpp \ test/cuckoocache_tests.cpp \ test/dbwrapper_tests.cpp \ test/DoS_tests.cpp \ test/dstencode_tests.cpp \ test/excessiveblock_tests.cpp \ test/feerate_tests.cpp \ test/getarg_tests.cpp \ test/hash_tests.cpp \ test/inv_tests.cpp \ test/jsonutil.cpp \ test/jsonutil.h \ test/key_tests.cpp \ test/limitedmap_tests.cpp \ test/main_tests.cpp \ test/mempool_tests.cpp \ test/merkle_tests.cpp \ test/miner_tests.cpp \ test/monolith_opcodes.cpp \ test/multisig_tests.cpp \ test/net_tests.cpp \ test/netbase_tests.cpp \ test/pmt_tests.cpp \ test/policyestimator_tests.cpp \ test/pow_tests.cpp \ test/prevector_tests.cpp \ test/raii_event_tests.cpp \ test/random_tests.cpp \ test/reverselock_tests.cpp \ test/rpc_tests.cpp \ test/sanity_tests.cpp \ test/scheduler_tests.cpp \ test/script_commitment_tests.cpp \ test/script_P2SH_tests.cpp \ test/script_tests.cpp \ test/scriptflags.cpp \ test/scriptflags.h \ test/scriptnum_tests.cpp \ test/serialize_tests.cpp \ test/sigencoding_tests.cpp \ test/sighash_tests.cpp \ test/sighashtype_tests.cpp \ test/sigopcount_tests.cpp \ test/sigutil.cpp \ test/sigutil.h \ test/skiplist_tests.cpp \ test/streams_tests.cpp \ test/test_bitcoin.cpp \ test/test_bitcoin.h \ test/test_bitcoin_main.cpp \ test/testutil.cpp \ test/testutil.h \ test/timedata_tests.cpp \ test/transaction_tests.cpp \ test/txvalidationcache_tests.cpp \ test/versionbits_tests.cpp \ test/uint256_tests.cpp \ test/undo_tests.cpp \ test/univalue_tests.cpp \ test/util_tests.cpp \ test/validation_tests.cpp \ test/work_comparator_tests.cpp if ENABLE_WALLET BITCOIN_TESTS += \ wallet/test/wallet_test_fixture.cpp \ wallet/test/wallet_test_fixture.h \ wallet/test/accounting_tests.cpp \ wallet/test/wallet_tests.cpp \ wallet/test/walletdb_tests.cpp \ wallet/test/crypto_tests.cpp endif test_test_bitcoin_SOURCES = $(BITCOIN_TESTS) $(JSON_TEST_FILES) $(RAW_TEST_FILES) test_test_bitcoin_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -I$(builddir)/test/ $(TESTDEFS) $(EVENT_CFLAGS) test_test_bitcoin_LDADD = if ENABLE_WALLET test_test_bitcoin_LDADD += $(LIBBITCOIN_WALLET) endif test_test_bitcoin_LDADD += $(LIBBITCOIN_SERVER) $(LIBBITCOIN_CLI) $(LIBBITCOIN_COMMON) $(LIBBITCOIN_UTIL) $(LIBBITCOIN_CONSENSUS) $(LIBBITCOIN_CRYPTO) $(LIBUNIVALUE) \ $(LIBLEVELDB) $(LIBLEVELDB_SSE42) $(LIBMEMENV) $(BOOST_LIBS) $(BOOST_UNIT_TEST_FRAMEWORK_LIB) $(LIBSECP256K1) $(EVENT_LIBS) $(EVENT_PTHREADS_LIBS) test_test_bitcoin_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) test_test_bitcoin_LDADD += $(LIBBITCOIN_CONSENSUS) $(BDB_LIBS) $(SSL_LIBS) $(CRYPTO_LIBS) $(MINIUPNPC_LIBS) test_test_bitcoin_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) -static if ENABLE_ZMQ test_test_bitcoin_LDADD += $(ZMQ_LIBS) endif # # test_bitcoin_fuzzy binary # test_test_bitcoin_fuzzy_SOURCES = test/test_bitcoin_fuzzy.cpp test_test_bitcoin_fuzzy_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) test_test_bitcoin_fuzzy_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) test_test_bitcoin_fuzzy_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) test_test_bitcoin_fuzzy_LDADD = \ $(LIBUNIVALUE) \ $(LIBBITCOIN_SERVER) \ $(LIBBITCOIN_COMMON) \ $(LIBBITCOIN_UTIL) \ $(LIBBITCOIN_CONSENSUS) \ $(LIBBITCOIN_CRYPTO) \ $(LIBSECP256K1) test_test_bitcoin_fuzzy_LDADD += $(BOOST_LIBS) $(CRYPTO_LIBS) # nodist_test_test_bitcoin_SOURCES = $(GENERATED_TEST_FILES) $(BITCOIN_TESTS): $(GENERATED_TEST_FILES) CLEAN_BITCOIN_TEST = test/*.gcda test/*.gcno $(GENERATED_TEST_FILES) CLEANFILES += $(CLEAN_BITCOIN_TEST) bitcoin_test: $(TEST_BINARY) bitcoin_test_check: $(TEST_BINARY) FORCE $(MAKE) check-TESTS TESTS=$^ bitcoin_test_clean : FORCE rm -f $(CLEAN_BITCOIN_TEST) $(test_test_bitcoin_OBJECTS) $(TEST_BINARY) check-local: @echo "Running test/util/bitcoin-util-test.py..." $(top_builddir)/test/util/bitcoin-util-test.py $(AM_V_at)$(MAKE) $(AM_MAKEFLAGS) -C secp256k1 check if EMBEDDED_UNIVALUE $(AM_V_at)$(MAKE) $(AM_MAKEFLAGS) -C univalue check endif %.json.h: %.json @$(MKDIR_P) $(@D) @{ \ echo "namespace json_tests{" && \ echo "static unsigned const char $(*F)[] = {" && \ $(HEXDUMP) -v -e '8/1 "0x%02x, "' -e '"\n"' $< | $(SED) -e 's/0x ,//g' && \ echo "};};"; \ } > "$@.new" && mv -f "$@.new" "$@" @echo "Generated $@" diff --git a/src/checkqueue.h b/src/checkqueue.h index 8e5dadb472..6532d8a77c 100644 --- a/src/checkqueue.h +++ b/src/checkqueue.h @@ -1,201 +1,214 @@ -// Copyright (c) 2012-2015 The Bitcoin Core developers +// Copyright (c) 2012-2018 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_CHECKQUEUE_H #define BITCOIN_CHECKQUEUE_H +#include + #include #include #include -#include #include template class CCheckQueueControl; /** * Queue for verifications that have to be performed. * The verifications are represented by a type T, which must provide an * operator(), returning a bool. * * One thread (the master) is assumed to push batches of verifications onto the * queue, where they are processed by N-1 worker threads. When the master is * done adding work, it temporarily joins the worker pool as an N'th worker, * until all jobs are done. */ template class CCheckQueue { private: //! Mutex to protect the inner state boost::mutex mutex; //! Worker threads block on this when out of work boost::condition_variable condWorker; //! Master thread blocks on this when out of work boost::condition_variable condMaster; //! The queue of elements to be processed. //! As the order of booleans doesn't matter, it is used as a LIFO (stack) std::vector queue; //! The number of workers (including the master) that are idle. int nIdle; //! The total number of workers (including the master). int nTotal; //! The temporary evaluation result. bool fAllOk; /** * Number of verifications that haven't completed yet. * This includes elements that are no longer queued, but still in the * worker's own batches. */ unsigned int nTodo; - //! Whether we're shutting down. - bool fQuit; - //! The maximum number of elements to be processed in one batch unsigned int nBatchSize; /** Internal function that does bulk of the verification work. */ bool Loop(bool fMaster = false) { boost::condition_variable &cond = fMaster ? condMaster : condWorker; std::vector vChecks; vChecks.reserve(nBatchSize); unsigned int nNow = 0; bool fOk = true; do { { boost::unique_lock lock(mutex); // first do the clean-up of the previous loop run (allowing us // to do it in the same critsect) if (nNow) { fAllOk &= fOk; nTodo -= nNow; - if (nTodo == 0 && !fMaster) + if (nTodo == 0 && !fMaster) { // We processed the last element; inform the master it // can exit and return the result condMaster.notify_one(); + } } else { // first iteration nTotal++; } // logically, the do loop starts here while (queue.empty()) { - if ((fMaster || fQuit) && nTodo == 0) { + if (fMaster && nTodo == 0) { nTotal--; bool fRet = fAllOk; // reset the status for new work later - if (fMaster) fAllOk = true; + if (fMaster) { + fAllOk = true; + } // return the current status return fRet; } nIdle++; cond.wait(lock); // wait nIdle--; } // Decide how many work units to process now. // * Do not try to do everything at once, but aim for // increasingly smaller batches so all workers finish // approximately simultaneously. // * Try to account for idle jobs which will instantly start // helping. // * Don't do batches smaller than 1 (duh), or larger than // nBatchSize. nNow = std::max(1U, std::min(nBatchSize, (unsigned int)queue.size() / (nTotal + nIdle + 1))); vChecks.resize(nNow); for (unsigned int i = 0; i < nNow; i++) { // We want the lock on the mutex to be as short as possible, // so swap jobs from the global queue to the local batch // vector instead of copying. vChecks[i].swap(queue.back()); queue.pop_back(); } // Check whether we need to do work at all fOk = fAllOk; } // execute work for (T &check : vChecks) { - if (fOk) fOk = check(); + if (fOk) { + fOk = check(); + } } vChecks.clear(); } while (true); } public: + //! Mutex to ensure only one concurrent CCheckQueueControl + boost::mutex ControlMutex; + //! Create a new check queue - CCheckQueue(unsigned int nBatchSizeIn) - : nIdle(0), nTotal(0), fAllOk(true), nTodo(0), fQuit(false), + explicit CCheckQueue(unsigned int nBatchSizeIn) + : nIdle(0), nTotal(0), fAllOk(true), nTodo(0), nBatchSize(nBatchSizeIn) {} //! Worker thread void Thread() { Loop(); } //! Wait until execution finishes, and return whether all evaluations were //! successful. bool Wait() { return Loop(true); } //! Add a batch of checks to the queue void Add(std::vector &vChecks) { boost::unique_lock lock(mutex); for (T &check : vChecks) { - queue.push_back(std::move(check)); + queue.push_back(T()); + check.swap(queue.back()); } nTodo += vChecks.size(); if (vChecks.size() == 1) { condWorker.notify_one(); } else if (vChecks.size() > 1) { condWorker.notify_all(); } } ~CCheckQueue() {} - - bool IsIdle() { - boost::unique_lock lock(mutex); - return (nTotal == nIdle && nTodo == 0 && fAllOk == true); - } }; /** * RAII-style controller object for a CCheckQueue that guarantees the passed * queue is finished before continuing. */ template class CCheckQueueControl { private: - CCheckQueue *pqueue; + CCheckQueue *const pqueue; bool fDone; public: - CCheckQueueControl(CCheckQueue *pqueueIn) + CCheckQueueControl() = delete; + CCheckQueueControl(const CCheckQueueControl &) = delete; + CCheckQueueControl &operator=(const CCheckQueueControl &) = delete; + explicit CCheckQueueControl(CCheckQueue *const pqueueIn) : pqueue(pqueueIn), fDone(false) { // passed queue is supposed to be unused, or nullptr if (pqueue != nullptr) { - bool isIdle = pqueue->IsIdle(); - assert(isIdle); + ENTER_CRITICAL_SECTION(pqueue->ControlMutex); } } bool Wait() { - if (pqueue == nullptr) return true; + if (pqueue == nullptr) { + return true; + } bool fRet = pqueue->Wait(); fDone = true; return fRet; } void Add(std::vector &vChecks) { - if (pqueue != nullptr) pqueue->Add(vChecks); + if (pqueue != nullptr) { + pqueue->Add(vChecks); + } } ~CCheckQueueControl() { - if (!fDone) Wait(); + if (!fDone) { + Wait(); + } + if (pqueue != nullptr) { + LEAVE_CRITICAL_SECTION(pqueue->ControlMutex); + } } }; #endif // BITCOIN_CHECKQUEUE_H diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt index 5c6951d22f..6394af6c74 100644 --- a/src/test/CMakeLists.txt +++ b/src/test/CMakeLists.txt @@ -1,164 +1,165 @@ # Copyright (c) 2018 The Bitcoin developers project(bitcoin-test) # Process json files. file(MAKE_DIRECTORY "${CMAKE_CURRENT_BINARY_DIR}/data") find_program(PYTHON python) function(gen_json_header NAME) set(HEADERS "") foreach(f ${ARGN}) set(h "${CMAKE_CURRENT_BINARY_DIR}/${f}.h") # Get the proper name for the test variable. get_filename_component(TEST_NAME ${f} NAME_WE) add_custom_command(OUTPUT ${h} COMMAND ${PYTHON} ARGS "${CMAKE_CURRENT_SOURCE_DIR}/data/generate_header.py" "${TEST_NAME}" "${CMAKE_CURRENT_SOURCE_DIR}/${f}" > ${h} MAIN_DEPENDENCY ${f} DEPENDS "data/generate_header.py" VERBATIM ) list(APPEND HEADERS ${h}) endforeach(f) set(${NAME} "${HEADERS}" PARENT_SCOPE) endfunction() gen_json_header(JSON_HEADERS data/script_tests.json data/base58_keys_valid.json data/base58_encode_decode.json data/base58_keys_invalid.json data/tx_invalid.json data/tx_valid.json data/sighash.json ) include(TestSuite) create_test_suite(bitcoin) add_dependencies(check check-bitcoin) add_test_to_suite(bitcoin test_bitcoin arith_uint256_tests.cpp addrman_tests.cpp amount_tests.cpp allocator_tests.cpp base32_tests.cpp base58_tests.cpp base64_tests.cpp bip32_tests.cpp blockcheck_tests.cpp blockencodings_tests.cpp blockindex_tests.cpp blockstatus_tests.cpp bloom_tests.cpp bswap_tests.cpp cashaddr_tests.cpp cashaddrenc_tests.cpp checkdatasig_tests.cpp checkpoints_tests.cpp + checkqueue_tests.cpp coins_tests.cpp compress_tests.cpp config_tests.cpp core_io_tests.cpp crypto_tests.cpp cuckoocache_tests.cpp dbwrapper_tests.cpp DoS_tests.cpp dstencode_tests.cpp excessiveblock_tests.cpp feerate_tests.cpp getarg_tests.cpp hash_tests.cpp inv_tests.cpp jsonutil.cpp key_tests.cpp limitedmap_tests.cpp main_tests.cpp mempool_tests.cpp merkle_tests.cpp miner_tests.cpp monolith_opcodes.cpp multisig_tests.cpp net_tests.cpp netbase_tests.cpp pmt_tests.cpp policyestimator_tests.cpp pow_tests.cpp prevector_tests.cpp raii_event_tests.cpp random_tests.cpp reverselock_tests.cpp rpc_tests.cpp sanity_tests.cpp scheduler_tests.cpp script_commitment_tests.cpp script_P2SH_tests.cpp script_tests.cpp scriptflags.cpp scriptnum_tests.cpp serialize_tests.cpp sigencoding_tests.cpp sighash_tests.cpp sighashtype_tests.cpp sigopcount_tests.cpp sigutil.cpp skiplist_tests.cpp streams_tests.cpp test_bitcoin.cpp test_bitcoin_main.cpp testutil.cpp timedata_tests.cpp transaction_tests.cpp txvalidationcache_tests.cpp versionbits_tests.cpp uint256_tests.cpp undo_tests.cpp univalue_tests.cpp util_tests.cpp validation_tests.cpp work_comparator_tests.cpp # Tests generated from JSON ${JSON_HEADERS} ) target_include_directories(test_bitcoin PUBLIC # To access the generated json headers. ${CMAKE_CURRENT_BINARY_DIR} PRIVATE ${OPENSSL_INCLUDE_DIR} ) find_package(Boost 1.58 REQUIRED unit_test_framework) target_link_libraries(test_bitcoin Boost::unit_test_framework rpcclient server) # We need to detect if the BOOST_TEST_DYN_LINK flag is required. set(CMAKE_REQUIRED_LIBRARIES Boost::unit_test_framework) check_cxx_source_compiles(" #define BOOST_TEST_DYN_LINK #define BOOST_TEST_MAIN #include " BOOST_TEST_DYN_LINK) if(BOOST_TEST_DYN_LINK) target_compile_definitions(test_bitcoin PRIVATE BOOST_TEST_DYN_LINK) endif(BOOST_TEST_DYN_LINK) if(BUILD_BITCOIN_WALLET) target_sources(test_bitcoin PRIVATE ../wallet/test/wallet_test_fixture.cpp ../wallet/test/accounting_tests.cpp ../wallet/test/wallet_tests.cpp ../wallet/test/walletdb_tests.cpp ../wallet/test/crypto_tests.cpp ) endif() diff --git a/src/test/checkqueue_tests.cpp b/src/test/checkqueue_tests.cpp new file mode 100644 index 0000000000..8e7b24bb33 --- /dev/null +++ b/src/test/checkqueue_tests.cpp @@ -0,0 +1,423 @@ +// Copyright (c) 2012-2018 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 +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include + +// BasicTestingSetup not sufficient because nScriptCheckThreads is not set +// otherwise. +BOOST_FIXTURE_TEST_SUITE(checkqueue_tests, TestingSetup) + +static const unsigned int QUEUE_BATCH_SIZE = 128; + +struct FakeCheck { + bool operator()() { return true; } + void swap(FakeCheck &x){}; +}; + +struct FakeCheckCheckCompletion { + static std::atomic n_calls; + bool operator()() { + n_calls.fetch_add(1, std::memory_order_relaxed); + return true; + } + void swap(FakeCheckCheckCompletion &x){}; +}; + +struct FailingCheck { + bool fails; + FailingCheck(bool _fails) : fails(_fails){}; + FailingCheck() : fails(true){}; + bool operator()() { return !fails; } + void swap(FailingCheck &x) { std::swap(fails, x.fails); }; +}; + +struct UniqueCheck { + static std::mutex m; + static std::unordered_multiset results; + size_t check_id; + UniqueCheck(size_t check_id_in) : check_id(check_id_in){}; + UniqueCheck() : check_id(0){}; + bool operator()() { + std::lock_guard l(m); + results.insert(check_id); + return true; + } + void swap(UniqueCheck &x) { std::swap(x.check_id, check_id); }; +}; + +struct MemoryCheck { + static std::atomic fake_allocated_memory; + bool b{false}; + bool operator()() { return true; } + MemoryCheck(){}; + MemoryCheck(const MemoryCheck &x) { + // We have to do this to make sure that destructor calls are paired + // + // Really, copy constructor should be deletable, but CCheckQueue breaks + // if it is deleted because of internal push_back. + fake_allocated_memory.fetch_add(b, std::memory_order_relaxed); + }; + MemoryCheck(bool b_) : b(b_) { + fake_allocated_memory.fetch_add(b, std::memory_order_relaxed); + }; + ~MemoryCheck() { + fake_allocated_memory.fetch_sub(b, std::memory_order_relaxed); + }; + void swap(MemoryCheck &x) { std::swap(b, x.b); }; +}; + +struct FrozenCleanupCheck { + static std::atomic nFrozen; + static std::condition_variable cv; + static std::mutex m; + // Freezing can't be the default initialized behavior given how the queue + // swaps in default initialized Checks. + bool should_freeze{false}; + bool operator()() { return true; } + FrozenCleanupCheck() {} + ~FrozenCleanupCheck() { + if (should_freeze) { + std::unique_lock l(m); + nFrozen.store(1, std::memory_order_relaxed); + cv.notify_one(); + cv.wait( + l, [] { return nFrozen.load(std::memory_order_relaxed) == 0; }); + } + } + void swap(FrozenCleanupCheck &x) { + std::swap(should_freeze, x.should_freeze); + }; +}; + +// Static Allocations +std::mutex FrozenCleanupCheck::m{}; +std::atomic FrozenCleanupCheck::nFrozen{0}; +std::condition_variable FrozenCleanupCheck::cv{}; +std::mutex UniqueCheck::m; +std::unordered_multiset UniqueCheck::results; +std::atomic FakeCheckCheckCompletion::n_calls{0}; +std::atomic MemoryCheck::fake_allocated_memory{0}; + +// Queue Typedefs +typedef CCheckQueue Correct_Queue; +typedef CCheckQueue Standard_Queue; +typedef CCheckQueue Failing_Queue; +typedef CCheckQueue Unique_Queue; +typedef CCheckQueue Memory_Queue; +typedef CCheckQueue FrozenCleanup_Queue; + +/** This test case checks that the CCheckQueue works properly + * with each specified size_t Checks pushed. + */ +static void Correct_Queue_range(std::vector range) { + auto small_queue = + std::unique_ptr(new Correct_Queue{QUEUE_BATCH_SIZE}); + boost::thread_group tg; + for (auto x = 0; x < nScriptCheckThreads; ++x) { + tg.create_thread([&] { small_queue->Thread(); }); + } + // Make vChecks here to save on malloc (this test can be slow...) + std::vector vChecks; + for (const size_t i : range) { + size_t total = i; + FakeCheckCheckCompletion::n_calls = 0; + CCheckQueueControl control(small_queue.get()); + while (total) { + vChecks.resize(std::min(total, (size_t)InsecureRandRange(10))); + total -= vChecks.size(); + control.Add(vChecks); + } + BOOST_REQUIRE(control.Wait()); + if (FakeCheckCheckCompletion::n_calls != i) { + BOOST_REQUIRE_EQUAL(FakeCheckCheckCompletion::n_calls, i); + BOOST_TEST_MESSAGE("Failure on trial " + << i << " expected, got " + << FakeCheckCheckCompletion::n_calls); + } + } + tg.interrupt_all(); + tg.join_all(); +} + +/** Test that 0 checks is correct + */ +BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Zero) { + std::vector range; + range.push_back((size_t)0); + Correct_Queue_range(range); +} +/** Test that 1 check is correct + */ +BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_One) { + std::vector range; + range.push_back((size_t)1); + Correct_Queue_range(range); +} +/** Test that MAX check is correct + */ +BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Max) { + std::vector range; + range.push_back(100000); + Correct_Queue_range(range); +} +/** Test that random numbers of checks are correct + */ +BOOST_AUTO_TEST_CASE(test_CheckQueue_Correct_Random) { + std::vector range; + range.reserve(100000 / 1000); + for (size_t i = 2; i < 100000; + i += std::max((size_t)1, (size_t)InsecureRandRange(std::min( + (size_t)1000, ((size_t)100000) - i)))) + range.push_back(i); + Correct_Queue_range(range); +} + +/** Test that failing checks are caught */ +BOOST_AUTO_TEST_CASE(test_CheckQueue_Catches_Failure) { + auto fail_queue = + std::unique_ptr(new Failing_Queue{QUEUE_BATCH_SIZE}); + + boost::thread_group tg; + for (auto x = 0; x < nScriptCheckThreads; ++x) { + tg.create_thread([&] { fail_queue->Thread(); }); + } + + for (size_t i = 0; i < 1001; ++i) { + CCheckQueueControl control(fail_queue.get()); + size_t remaining = i; + while (remaining) { + size_t r = InsecureRandRange(10); + + std::vector vChecks; + vChecks.reserve(r); + for (size_t k = 0; k < r && remaining; k++, remaining--) + vChecks.emplace_back(remaining == 1); + control.Add(vChecks); + } + bool success = control.Wait(); + if (i > 0) { + BOOST_REQUIRE(!success); + } else if (i == 0) { + BOOST_REQUIRE(success); + } + } + tg.interrupt_all(); + tg.join_all(); +} +// Test that a block validation which fails does not interfere with +// future blocks, ie, the bad state is cleared. +BOOST_AUTO_TEST_CASE(test_CheckQueue_Recovers_From_Failure) { + auto fail_queue = + std::unique_ptr(new Failing_Queue{QUEUE_BATCH_SIZE}); + boost::thread_group tg; + for (auto x = 0; x < nScriptCheckThreads; ++x) { + tg.create_thread([&] { fail_queue->Thread(); }); + } + + for (auto times = 0; times < 10; ++times) { + for (const bool end_fails : {true, false}) { + CCheckQueueControl control(fail_queue.get()); + { + std::vector vChecks; + vChecks.resize(100, false); + vChecks[99] = end_fails; + control.Add(vChecks); + } + bool r = control.Wait(); + BOOST_REQUIRE(r != end_fails); + } + } + tg.interrupt_all(); + tg.join_all(); +} + +// Test that unique checks are actually all called individually, rather than +// just one check being called repeatedly. Test that checks are not called +// more than once as well +BOOST_AUTO_TEST_CASE(test_CheckQueue_UniqueCheck) { + auto queue = + std::unique_ptr(new Unique_Queue{QUEUE_BATCH_SIZE}); + boost::thread_group tg; + for (auto x = 0; x < nScriptCheckThreads; ++x) { + tg.create_thread([&] { queue->Thread(); }); + } + + size_t COUNT = 100000; + size_t total = COUNT; + { + CCheckQueueControl control(queue.get()); + while (total) { + size_t r = InsecureRandRange(10); + std::vector vChecks; + for (size_t k = 0; k < r && total; k++) + vChecks.emplace_back(--total); + control.Add(vChecks); + } + } + bool r = true; + BOOST_REQUIRE_EQUAL(UniqueCheck::results.size(), COUNT); + for (size_t i = 0; i < COUNT; ++i) + r = r && UniqueCheck::results.count(i) == 1; + BOOST_REQUIRE(r); + tg.interrupt_all(); + tg.join_all(); +} + +// Test that blocks which might allocate lots of memory free their memory +// aggressively. +// +// This test attempts to catch a pathological case where by lazily freeing +// checks might mean leaving a check un-swapped out, and decreasing by 1 each +// time could leave the data hanging across a sequence of blocks. +BOOST_AUTO_TEST_CASE(test_CheckQueue_Memory) { + auto queue = + std::unique_ptr(new Memory_Queue{QUEUE_BATCH_SIZE}); + boost::thread_group tg; + for (auto x = 0; x < nScriptCheckThreads; ++x) { + tg.create_thread([&] { queue->Thread(); }); + } + for (size_t i = 0; i < 1000; ++i) { + size_t total = i; + { + CCheckQueueControl control(queue.get()); + while (total) { + size_t r = InsecureRandRange(10); + std::vector vChecks; + for (size_t k = 0; k < r && total; k++) { + total--; + // Each iteration leaves data at the front, back, and middle + // to catch any sort of deallocation failure + vChecks.emplace_back(total == 0 || total == i || + total == i / 2); + } + control.Add(vChecks); + } + } + BOOST_REQUIRE_EQUAL(MemoryCheck::fake_allocated_memory, 0U); + } + tg.interrupt_all(); + tg.join_all(); +} + +// Test that a new verification cannot occur until all checks +// have been destructed +BOOST_AUTO_TEST_CASE(test_CheckQueue_FrozenCleanup) { + auto queue = std::unique_ptr( + new FrozenCleanup_Queue{QUEUE_BATCH_SIZE}); + boost::thread_group tg; + bool fails = false; + for (auto x = 0; x < nScriptCheckThreads; ++x) { + tg.create_thread([&] { queue->Thread(); }); + } + std::thread t0([&]() { + CCheckQueueControl control(queue.get()); + std::vector vChecks(1); + // Freezing can't be the default initialized behavior given how the + // queue + // swaps in default initialized Checks (otherwise freezing destructor + // would get called twice). + vChecks[0].should_freeze = true; + control.Add(vChecks); + control.Wait(); // Hangs here + }); + { + std::unique_lock l(FrozenCleanupCheck::m); + // Wait until the queue has finished all jobs and frozen + FrozenCleanupCheck::cv.wait( + l, []() { return FrozenCleanupCheck::nFrozen == 1; }); + } + // Try to get control of the queue a bunch of times + for (auto x = 0; x < 100 && !fails; ++x) { + fails = queue->ControlMutex.try_lock(); + } + { + // Unfreeze (we need lock n case of spurious wakeup) + std::unique_lock l(FrozenCleanupCheck::m); + FrozenCleanupCheck::nFrozen = 0; + } + // Awaken frozen destructor + FrozenCleanupCheck::cv.notify_one(); + // Wait for control to finish + t0.join(); + tg.interrupt_all(); + tg.join_all(); + BOOST_REQUIRE(!fails); +} + +/** Test that CCheckQueueControl is threadsafe */ +BOOST_AUTO_TEST_CASE(test_CheckQueueControl_Locks) { + auto queue = + std::unique_ptr(new Standard_Queue{QUEUE_BATCH_SIZE}); + { + boost::thread_group tg; + std::atomic nThreads{0}; + std::atomic fails{0}; + for (size_t i = 0; i < 3; ++i) { + tg.create_thread([&] { + CCheckQueueControl control(queue.get()); + // While sleeping, no other thread should execute to this point + auto observed = ++nThreads; + MilliSleep(10); + fails += observed != nThreads; + }); + } + tg.join_all(); + BOOST_REQUIRE_EQUAL(fails, 0); + } + { + boost::thread_group tg; + std::mutex m; + std::condition_variable cv; + bool has_lock{false}; + bool has_tried{false}; + bool done{false}; + bool done_ack{false}; + { + std::unique_lock l(m); + tg.create_thread([&] { + CCheckQueueControl control(queue.get()); + std::unique_lock ll(m); + has_lock = true; + cv.notify_one(); + cv.wait(ll, [&] { return has_tried; }); + done = true; + cv.notify_one(); + // Wait until the done is acknowledged + // + cv.wait(ll, [&] { return done_ack; }); + }); + // Wait for thread to get the lock + cv.wait(l, [&]() { return has_lock; }); + bool fails = false; + for (auto x = 0; x < 100 && !fails; ++x) { + fails = queue->ControlMutex.try_lock(); + } + has_tried = true; + cv.notify_one(); + cv.wait(l, [&]() { return done; }); + // Acknowledge the done + done_ack = true; + cv.notify_one(); + BOOST_REQUIRE(!fails); + } + tg.join_all(); + } +} +BOOST_AUTO_TEST_SUITE_END()