diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index c57a67d3d..2460ea23d 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -1,735 +1,736 @@ # Copyright (c) 2017 The Bitcoin developers project(bitcoind) set(CMAKE_CXX_STANDARD 17) set(CMAKE_CXX_STANDARD_REQUIRED ON) # Default visibility is hidden on all targets. set(CMAKE_C_VISIBILITY_PRESET hidden) set(CMAKE_CXX_VISIBILITY_PRESET hidden) option(BUILD_BITCOIN_WALLET "Activate the wallet functionality" ON) option(BUILD_BITCOIN_ZMQ "Activate the ZeroMQ functionalities" ON) option(BUILD_BITCOIN_CLI "Build bitcoin-cli" ON) option(BUILD_BITCOIN_TX "Build bitcoin-tx" ON) option(BUILD_BITCOIN_QT "Build bitcoin-qt" ON) option(BUILD_BITCOIN_SEEDER "Build bitcoin-seeder" ON) option(BUILD_LIBBITCOINCONSENSUS "Build the bitcoinconsenus shared library" ON) option(ENABLE_BIP70 "Enable BIP70 (payment protocol) support in GUI" ON) option(ENABLE_HARDENING "Harden the executables" ON) option(ENABLE_REDUCE_EXPORTS "Reduce the amount of exported symbols" OFF) option(ENABLE_STATIC_LIBSTDCXX "Statically link libstdc++" OFF) option(ENABLE_GLIBC_BACK_COMPAT "Enable Glibc compatibility features" OFF) option(ENABLE_QRCODE "Enable QR code display" ON) option(ENABLE_UPNP "Enable UPnP support" ON) option(START_WITH_UPNP "Make UPnP the default to map ports" OFF) option(ENABLE_CLANG_TIDY "Enable clang-tidy checks for Bitcoin ABC" OFF) option(ENABLE_PROFILING "Select the profiling tool to use" OFF) # Linker option if(CMAKE_CROSSCOMPILING) set(DEFAULT_LINKER "") elseif(CMAKE_CXX_COMPILER_ID STREQUAL "Clang") set(DEFAULT_LINKER lld) elseif(CMAKE_CXX_COMPILER_ID STREQUAL "GNU") set(DEFAULT_LINKER gold) else() set(DEFAULT_LINKER "") endif() set(USE_LINKER "${DEFAULT_LINKER}" CACHE STRING "Linker to be used (default: ${DEFAULT_LINKER}). Set to empty string to use the system's default.") set(OS_WITH_JEMALLOC_AS_SYSTEM_DEFAULT "Android" "FreeBSD" "NetBSD" ) if(NOT CMAKE_SYSTEM_NAME IN_LIST OS_WITH_JEMALLOC_AS_SYSTEM_DEFAULT) set(USE_JEMALLOC_DEFAULT ON) endif() # FIXME: Building against jemalloc causes the software to segfault on OSX. # See https://github.com/Bitcoin-ABC/bitcoin-abc/issues/401 if(${CMAKE_SYSTEM_NAME} MATCHES "Darwin" AND NOT CMAKE_CROSSCOMPILING) set(USE_JEMALLOC_DEFAULT OFF) endif() option(USE_JEMALLOC "Use jemalloc as an allocation library" ${USE_JEMALLOC_DEFAULT}) if(${CMAKE_SYSTEM_NAME} MATCHES "Linux") set(DEFAULT_ENABLE_DBUS_NOTIFICATIONS ON) endif() option(ENABLE_DBUS_NOTIFICATIONS "Enable DBus desktop notifications. Linux only." ${DEFAULT_ENABLE_DBUS_NOTIFICATIONS}) # If ccache is available, then use it. find_program(CCACHE ccache) if(CCACHE) message(STATUS "Using ccache: ${CCACHE}") set(CMAKE_C_COMPILER_LAUNCHER ${CCACHE}) set(CMAKE_CXX_COMPILER_LAUNCHER ${CCACHE}) endif(CCACHE) # Disable what we do not need for the native build. include(NativeExecutable) native_add_cmake_flags( "-DBUILD_BITCOIN_WALLET=OFF" "-DBUILD_BITCOIN_QT=OFF" "-DBUILD_BITCOIN_ZMQ=OFF" "-DENABLE_QRCODE=OFF" "-DENABLE_UPNP=OFF" "-DUSE_JEMALLOC=OFF" "-DENABLE_CLANG_TIDY=OFF" "-DENABLE_BIP70=OFF" ) if(ENABLE_CLANG_TIDY) include(ClangTidy) endif() if(ENABLE_SANITIZERS) include(Sanitizers) enable_sanitizers(${ENABLE_SANITIZERS}) endif() include(AddCompilerFlags) if(USE_LINKER) set(LINKER_FLAG "-fuse-ld=${USE_LINKER}") check_linker_flag(IS_LINKER_SUPPORTED ${LINKER_FLAG}) if(NOT IS_LINKER_SUPPORTED) message(FATAL_ERROR "The ${USE_LINKER} linker is not supported, make sure ${USE_LINKER} is properly installed or use -DUSE_LINKER= to use the system's linker") endif() add_linker_flags(${LINKER_FLAG}) endif() # Prefer -g3, defaults to -g if unavailable foreach(LANGUAGE C CXX) set(COMPILER_DEBUG_LEVEL -g) check_compiler_flags(G3_IS_SUPPORTED ${LANGUAGE} -g3) if(${G3_IS_SUPPORTED}) set(COMPILER_DEBUG_LEVEL -g3) endif() add_compile_options_to_configuration_for_language(Debug ${LANGUAGE} ${COMPILER_DEBUG_LEVEL}) endforeach() # Define the debugging symbols DEBUG and DEBUG_LOCKORDER when the Debug build # type is selected. add_compile_definitions_to_configuration(Debug DEBUG DEBUG_LOCKORDER) # Add -ftrapv when building in Debug add_compile_options_to_configuration(Debug -ftrapv) # All versions of gcc that we commonly use for building are subject to bug # https://gcc.gnu.org/bugzilla/show_bug.cgi?id=90348. To work around that, set # -fstack-reuse=none for all gcc builds. (Only gcc understands this flag) if(CMAKE_CXX_COMPILER_ID MATCHES "GNU") add_compiler_flags(-fstack-reuse=none) endif() if(${CMAKE_SYSTEM_NAME} MATCHES "Windows") # Ensure that WINDRES_PREPROC is enabled when using windres. list(APPEND CMAKE_RC_FLAGS "-DWINDRES_PREPROC") # Build all static so there is no dll file to distribute. add_linker_flags(-static) add_compile_definitions( # Windows 7 _WIN32_WINNT=0x0601 # Internet Explorer 5.01 (!) _WIN32_IE=0x0501 # Define WIN32_LEAN_AND_MEAN to exclude APIs such as Cryptography, DDE, # RPC, Shell, and Windows Sockets. WIN32_LEAN_AND_MEAN ) endif() if(${CMAKE_SYSTEM_NAME} MATCHES "Darwin") add_compile_definitions(MAC_OSX OBJC_OLD_DISPATCH_PROTOTYPES=0) add_linker_flags(-Wl,-dead_strip_dylibs) endif() if(ENABLE_REDUCE_EXPORTS) # Default visibility is set by CMAKE__VISIBILITY_PRESET, but this # doesn't tell if the visibility set is effective. # Check if the flag -fvisibility=hidden is supported, as using the hidden # visibility is a requirement to reduce exports. check_compiler_flags(HAS_CXX_FVISIBILITY CXX -fvisibility=hidden) if(NOT HAS_CXX_FVISIBILITY) message(FATAL_ERROR "Cannot set default symbol visibility. Use -DENABLE_REDUCE_EXPORTS=OFF.") endif() # Also hide symbols from static libraries add_linker_flags(-Wl,--exclude-libs,libstdc++) endif() # Enable statically linking libstdc++ if(ENABLE_STATIC_LIBSTDCXX) add_linker_flags(-static-libstdc++) endif() set(CMAKE_POSITION_INDEPENDENT_CODE ON) if(ENABLE_HARDENING) # Enable stack protection add_cxx_compiler_flags(-fstack-protector-all -Wstack-protector) # Enable some buffer overflow checking, except in -O0 builds which # do not support them add_compiler_flags(-U_FORTIFY_SOURCE) add_compile_options($<$>:-D_FORTIFY_SOURCE=2>) # Enable ASLR (these flags are primarily targeting MinGw) add_linker_flags(-Wl,--dynamicbase -Wl,--nxcompat -Wl,--high-entropy-va) # Make the relocated sections read-only add_linker_flags(-Wl,-z,relro -Wl,-z,now) # CMake provides the POSITION_INDEPENDENT_CODE property to set PIC/PIE. cmake_policy(SET CMP0083 NEW) include(CheckPIESupported) check_pie_supported() if(${CMAKE_SYSTEM_NAME} MATCHES "Windows") # MinGw provides its own libssp for stack smashing protection link_libraries(ssp) endif() endif() if(ENABLE_PROFILING MATCHES "gprof") message(STATUS "Enable profiling with gprof") # -pg is incompatible with -pie. Since hardening and profiling together # doesn't make sense, we simply make them mutually exclusive here. # Additionally, hardened toolchains may force -pie by default, in which # case it needs to be turned off with -no-pie. if(ENABLE_HARDENING) message(FATAL_ERROR "Profiling with gprof requires disabling hardening with -DENABLE_HARDENING=OFF.") endif() add_linker_flags(-no-pie) add_compiler_flags(-pg) add_linker_flags(-pg) endif() # Enable warning add_c_compiler_flags(-Wnested-externs -Wstrict-prototypes) add_compiler_flags( -Wall -Wextra -Wformat -Wgnu -Wvla -Wcast-align -Wunused-parameter -Wmissing-braces -Wthread-safety -Wrange-loop-analysis -Wredundant-decls -Wunreachable-code-loop-increment -Wsign-compare -Wconditional-uninitialized ) add_compiler_flag_group(-Wformat -Wformat-security) add_cxx_compiler_flags( -Wredundant-move ) if(CMAKE_CXX_COMPILER_ID STREQUAL "Clang") # GCC has no flag variant which is granular enough to avoid raising the clang # -Wshadow-uncaptured-local equivalent. This is causing a lot of warnings # on serialize.h which cannot be disabled locally, so drop the flag. add_compiler_flags( -Wshadow -Wshadow-field ) endif() option(EXTRA_WARNINGS "Enable extra warnings" OFF) if(EXTRA_WARNINGS) add_cxx_compiler_flags(-Wsuggest-override) else() add_compiler_flags(-Wno-unused-parameter) add_compiler_flags(-Wno-implicit-fallthrough) endif() # libtool style configure add_subdirectory(config) # Enable LFS (Large File Support) on targets that don't have it natively. # This should be defined before the libraries are included as leveldb need the # definition to be set. if(NOT HAVE_LARGE_FILE_SUPPORT) add_compile_definitions(_FILE_OFFSET_BITS=64) add_linker_flags(-Wl,--large-address-aware) endif() if(ENABLE_GLIBC_BACK_COMPAT) # Wrap some glibc functions with ours add_linker_flags(-Wl,--wrap=__divmoddi4) add_linker_flags(-Wl,--wrap=log2f) if(NOT HAVE_LARGE_FILE_SUPPORT) add_linker_flags(-Wl,--wrap=fcntl -Wl,--wrap=fcntl64) endif() endif() if(USE_JEMALLOC) # Most of the sanitizers require their instrumented allocation functions to # be fully functional. This is obviously the case for all the memory related # sanitizers (asan, lsan, msan) but not only. if(ENABLE_SANITIZERS) message(WARNING "Jemalloc is incompatible with the sanitizers and has been disabled.") else() find_package(Jemalloc 3.6.0 REQUIRED) link_libraries(Jemalloc::jemalloc) endif() endif() # Make sure that all the global compiler and linker flags are set BEFORE # including the libraries so they apply as needed. # libraries add_subdirectory(crypto) add_subdirectory(leveldb) add_subdirectory(secp256k1) add_subdirectory(univalue) # Find the git root, and returns the full path to the .git/logs/HEAD file if # it exists. function(find_git_head_logs_file RESULT) find_package(Git) if(GIT_FOUND) execute_process( COMMAND "${GIT_EXECUTABLE}" "rev-parse" "--show-toplevel" WORKING_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}" OUTPUT_VARIABLE GIT_ROOT RESULT_VARIABLE GIT_RESULT OUTPUT_STRIP_TRAILING_WHITESPACE ERROR_QUIET ) if(GIT_RESULT EQUAL 0) set(GIT_LOGS_DIR "${GIT_ROOT}/.git/logs") set(GIT_HEAD_LOGS_FILE "${GIT_LOGS_DIR}/HEAD") # If the .git/logs/HEAD does not exist, create it if(NOT EXISTS "${GIT_HEAD_LOGS_FILE}") file(MAKE_DIRECTORY "${GIT_LOGS_DIR}") file(TOUCH "${GIT_HEAD_LOGS_FILE}") endif() set(${RESULT} "${GIT_HEAD_LOGS_FILE}" PARENT_SCOPE) endif() endif() endfunction() find_git_head_logs_file(GIT_HEAD_LOGS_FILE) set(OBJ_DIR "${CMAKE_CURRENT_BINARY_DIR}/obj") file(MAKE_DIRECTORY "${OBJ_DIR}") set(BUILD_HEADER "${OBJ_DIR}/build.h") set(BUILD_HEADER_TMP "${BUILD_HEADER}.tmp") add_custom_command( DEPENDS "${GIT_HEAD_LOGS_FILE}" "${CMAKE_SOURCE_DIR}/share/genbuild.sh" OUTPUT "${BUILD_HEADER}" COMMAND "${CMAKE_SOURCE_DIR}/share/genbuild.sh" "${BUILD_HEADER_TMP}" "${CMAKE_SOURCE_DIR}" COMMAND ${CMAKE_COMMAND} -E copy_if_different "${BUILD_HEADER_TMP}" "${BUILD_HEADER}" COMMAND ${CMAKE_COMMAND} -E remove "${BUILD_HEADER_TMP}" ) # Because the Bitcoin ABc source code is disorganised, we # end up with a bunch of libraries without any apparent # cohesive structure. This is inherited from Bitcoin Core # and reflecting this. # TODO: Improve the structure once cmake is rocking. # Various completely unrelated features shared by all executables. add_library(util chainparamsbase.cpp clientversion.cpp compat/glibcxx_sanity.cpp compat/strnlen.cpp fs.cpp interfaces/handler.cpp logging.cpp random.cpp randomenv.cpp rcu.cpp rpc/request.cpp blockdb.cpp support/cleanse.cpp support/lockedpool.cpp sync.cpp threadinterrupt.cpp uint256.cpp util/asmap.cpp util/bip32.cpp util/bytevectorhash.cpp util/error.cpp util/message.cpp util/moneystr.cpp util/settings.cpp util/spanparsing.cpp util/strencodings.cpp util/string.cpp util/system.cpp util/threadnames.cpp util/time.cpp util/url.cpp # obj/build.h "${BUILD_HEADER}" ) target_compile_definitions(util PUBLIC HAVE_CONFIG_H HAVE_BUILD_INFO) target_include_directories(util PUBLIC . # To access the config/ and obj/ directories ${CMAKE_CURRENT_BINARY_DIR} ) if(ENABLE_GLIBC_BACK_COMPAT) target_sources(util PRIVATE compat/glibc_compat.cpp) endif() # Target specific configs if(${CMAKE_SYSTEM_NAME} MATCHES "Windows") set(Boost_USE_STATIC_LIBS ON) set(Boost_USE_STATIC_RUNTIME ON) set(Boost_THREADAPI win32) find_package(SHLWAPI REQUIRED) target_link_libraries(util SHLWAPI::shlwapi) find_library(WS2_32_LIBRARY NAMES ws2_32) target_link_libraries(util ${WS2_32_LIBRARY}) target_compile_definitions(util PUBLIC BOOST_THREAD_USE_LIB) endif() target_link_libraries(util univalue crypto) macro(link_event TARGET) non_native_target_link_libraries(${TARGET} Event 2.0.22 ${ARGN}) endmacro() link_event(util event) macro(link_boost TARGET) non_native_target_link_libraries(${TARGET} Boost 1.59 ${ARGN}) endmacro() link_boost(util filesystem thread) # Make sure boost uses std::atomic (it doesn't before 1.63) target_compile_definitions(util PUBLIC BOOST_SP_USE_STD_ATOMIC BOOST_AC_USE_STD_ATOMIC) function(add_network_sources NETWORK_SOURCES) set(NETWORK_DIR abc) list(TRANSFORM ARGN PREPEND "networks/${NETWORK_DIR}/" OUTPUT_VARIABLE NETWORK_SOURCES ) set(NETWORK_SOURCES ${NETWORK_SOURCES} PARENT_SCOPE) endfunction() add_network_sources(NETWORK_SOURCES checkpoints.cpp network.cpp chainparamsconstants.cpp ) # More completely unrelated features shared by all executables. # Because nothing says this is different from util than "common" add_library(common amount.cpp base58.cpp bloom.cpp cashaddr.cpp cashaddrenc.cpp chainparams.cpp config.cpp consensus/merkle.cpp coins.cpp compressor.cpp eventloop.cpp feerate.cpp core_read.cpp core_write.cpp key.cpp key_io.cpp merkleblock.cpp net_permissions.cpp netaddress.cpp netbase.cpp outputtype.cpp policy/policy.cpp primitives/block.cpp protocol.cpp psbt.cpp rpc/rawtransaction_util.cpp rpc/util.cpp scheduler.cpp salteduint256hasher.cpp versionbitsinfo.cpp warnings.cpp ${NETWORK_SOURCES} ) target_link_libraries(common bitcoinconsensus util secp256k1 script) # script library add_library(script script/bitfield.cpp script/descriptor.cpp script/interpreter.cpp script/script.cpp script/script_error.cpp script/sigencoding.cpp script/sign.cpp script/signingprovider.cpp script/standard.cpp ) target_link_libraries(script common) # libbitcoinconsensus add_library(bitcoinconsensus arith_uint256.cpp hash.cpp primitives/transaction.cpp pubkey.cpp uint256.cpp util/strencodings.cpp consensus/tx_check.cpp ) target_link_libraries(bitcoinconsensus script) include(InstallationHelper) if(BUILD_LIBBITCOINCONSENSUS) target_compile_definitions(bitcoinconsensus PUBLIC BUILD_BITCOIN_INTERNAL HAVE_CONSENSUS_LIB ) install_shared_library(bitcoinconsensus script/bitcoinconsensus.cpp PUBLIC_HEADER script/bitcoinconsensus.h ) endif() # Bitcoin server facilities add_library(server addrdb.cpp addrman.cpp avalanche/delegation.cpp avalanche/delegationbuilder.cpp avalanche/orphanproofpool.cpp avalanche/peermanager.cpp avalanche/processor.cpp avalanche/proof.cpp avalanche/proofbuilder.cpp banman.cpp blockencodings.cpp blockfilter.cpp blockindex.cpp chain.cpp checkpoints.cpp config.cpp consensus/activation.cpp consensus/tx_verify.cpp dbwrapper.cpp dnsseeds.cpp flatfile.cpp httprpc.cpp httpserver.cpp index/base.cpp index/blockfilterindex.cpp index/txindex.cpp init.cpp interfaces/chain.cpp interfaces/node.cpp miner.cpp minerfund.cpp net.cpp net_processing.cpp node/coin.cpp node/coinstats.cpp node/context.cpp node/psbt.cpp node/transaction.cpp node/ui_interface.cpp noui.cpp policy/fees.cpp policy/settings.cpp pow/aserti32d.cpp pow/daa.cpp pow/eda.cpp pow/grasberg.cpp pow/pow.cpp rest.cpp rpc/abc.cpp rpc/avalanche.cpp rpc/blockchain.cpp rpc/command.cpp rpc/mining.cpp rpc/misc.cpp rpc/net.cpp rpc/rawtransaction.cpp rpc/server.cpp script/scriptcache.cpp script/sigcache.cpp shutdown.cpp timedata.cpp torcontrol.cpp txdb.cpp txmempool.cpp + txrequest.cpp validation.cpp validationinterface.cpp versionbits.cpp ) target_include_directories(server PRIVATE leveldb/helpers/memenv) target_link_libraries(server bitcoinconsensus leveldb memenv ) link_event(server event) if(NOT ${CMAKE_SYSTEM_NAME} MATCHES "Windows") link_event(server pthreads) endif() if(ENABLE_UPNP) find_package(MiniUPnPc 1.9 REQUIRED) target_link_libraries(server MiniUPnPc::miniupnpc) if(${CMAKE_SYSTEM_NAME} MATCHES "Windows") # TODO: check if we are really using a static library. Assume this is # the one from the depends for now since the native windows build is not # supported. target_compile_definitions(server PUBLIC -DSTATICLIB PUBLIC -DMINIUPNP_STATICLIB ) endif() endif() # Test suites. add_subdirectory(test) add_subdirectory(avalanche/test) add_subdirectory(pow/test) # Benchmark suite. add_subdirectory(bench) include(BinaryTest) include(WindowsVersionInfo) # Wallet if(BUILD_BITCOIN_WALLET) add_subdirectory(wallet) target_link_libraries(server wallet) # bitcoin-wallet add_executable(bitcoin-wallet bitcoin-wallet.cpp) generate_windows_version_info(bitcoin-wallet DESCRIPTION "CLI tool for ${PACKAGE_NAME} wallets" ) target_link_libraries(bitcoin-wallet wallet-tool common util) add_to_symbols_check(bitcoin-wallet) add_to_security_check(bitcoin-wallet) install_target(bitcoin-wallet) install_manpages(bitcoin-wallet) else() target_sources(server PRIVATE dummywallet.cpp) endif() # ZeroMQ if(BUILD_BITCOIN_ZMQ) add_subdirectory(zmq) target_link_libraries(server zmq) endif() # RPC client support add_library(rpcclient compat/stdin.cpp rpc/client.cpp ) target_link_libraries(rpcclient univalue util) # bitcoin-seeder if(BUILD_BITCOIN_SEEDER) add_subdirectory(seeder) endif() # bitcoin-cli if(BUILD_BITCOIN_CLI) add_executable(bitcoin-cli bitcoin-cli.cpp) generate_windows_version_info(bitcoin-cli DESCRIPTION "JSON-RPC client for ${PACKAGE_NAME}" ) target_link_libraries(bitcoin-cli common rpcclient) link_event(bitcoin-cli event) add_to_symbols_check(bitcoin-cli) add_to_security_check(bitcoin-cli) install_target(bitcoin-cli) install_manpages(bitcoin-cli) endif() # bitcoin-tx if(BUILD_BITCOIN_TX) add_executable(bitcoin-tx bitcoin-tx.cpp) generate_windows_version_info(bitcoin-tx DESCRIPTION "CLI Bitcoin transaction editor utility" ) target_link_libraries(bitcoin-tx bitcoinconsensus) add_to_symbols_check(bitcoin-tx) add_to_security_check(bitcoin-tx) install_target(bitcoin-tx) install_manpages(bitcoin-tx) endif() # bitcoind add_executable(bitcoind bitcoind.cpp) target_link_libraries(bitcoind server) generate_windows_version_info(bitcoind DESCRIPTION "Bitcoin node with a JSON-RPC server" ) add_to_symbols_check(bitcoind) add_to_security_check(bitcoind) install_target(bitcoind) install_manpages(bitcoind) # Bitcoin-qt if(BUILD_BITCOIN_QT) add_subdirectory(qt) endif() diff --git a/src/txrequest.cpp b/src/txrequest.cpp new file mode 100644 index 000000000..fecfb4d8c --- /dev/null +++ b/src/txrequest.cpp @@ -0,0 +1,756 @@ +// Copyright (c) 2020 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 + +namespace { + +/** + * The various states a (txid, peer) pair can be in. + * + * Note that CANDIDATE is split up into 3 substates (DELAYED, BEST, READY), + * allowing more efficient implementation. Also note that the sorting order of + * ByTxIdView relies on the specific order of values in this enum. + * + * Expected behaviour is: + * - When first announced by a peer, the state is CANDIDATE_DELAYED until + * reqtime is reached. + * - Announcements that have reached their reqtime but not been requested will + * be either CANDIDATE_READY or CANDIDATE_BEST. Neither of those has an + * expiration time; they remain in that state until they're requested or no + * longer needed. CANDIDATE_READY announcements are promoted to + * CANDIDATE_BEST when they're the best one left. + * - When requested, an announcement will be in state REQUESTED until expiry + * is reached. + * - If expiry is reached, or the peer replies to the request (either with + * NOTFOUND or the tx), the state becomes COMPLETED. + */ +enum class State : uint8_t { + /** A CANDIDATE announcement whose reqtime is in the future. */ + CANDIDATE_DELAYED, + /** + * A CANDIDATE announcement that's not CANDIDATE_DELAYED or CANDIDATE_BEST. + */ + CANDIDATE_READY, + /** + * The best CANDIDATE for a given txid; only if there is no REQUESTED + * announcement already for that txid. The CANDIDATE_BEST is the + * highest-priority announcement among all CANDIDATE_READY (and _BEST) ones + * for that txid. + */ + CANDIDATE_BEST, + /** A REQUESTED announcement. */ + REQUESTED, + /** A COMPLETED announcement. */ + COMPLETED, +}; + +//! Type alias for sequence numbers. +using SequenceNumber = uint64_t; + +/** + * An announcement. This is the data we track for each txid that is announced + * to us by each peer. + */ +struct Announcement { + /** TxId that was announced. */ + const TxId m_txid; + /** + * For CANDIDATE_{DELAYED,BEST,READY} the reqtime; for REQUESTED the + * expiry. + */ + std::chrono::microseconds m_time; + /** What peer the request was from. */ + const NodeId m_peer; + /** What sequence number this announcement has. */ + const SequenceNumber m_sequence : 60; + /** Whether the request is preferred. */ + const bool m_preferred : 1; + + /** + * What state this announcement is in. + * This is a uint8_t instead of a State to silence a GCC warning in versions + * prior to 8.4 and 9.3. See + * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61414 + */ + uint8_t m_state : 3; + + /** Convert m_state to a State enum. */ + State GetState() const { return static_cast(m_state); } + + /** Convert a State enum to a uint8_t and store it in m_state. */ + void SetState(State state) { m_state = static_cast(state); } + + /** + * Whether this announcement is selected. There can be at most 1 selected + * peer per txid. + */ + bool IsSelected() const { + return GetState() == State::CANDIDATE_BEST || + GetState() == State::REQUESTED; + } + + /** Whether this announcement is waiting for a certain time to pass. */ + bool IsWaiting() const { + return GetState() == State::REQUESTED || + GetState() == State::CANDIDATE_DELAYED; + } + + /** + * Whether this announcement can feasibly be selected if the current + * IsSelected() one disappears. + */ + bool IsSelectable() const { + return GetState() == State::CANDIDATE_READY || + GetState() == State::CANDIDATE_BEST; + } + + /** + * Construct a new announcement from scratch, initially in + * CANDIDATE_DELAYED state. + */ + Announcement(const TxId &txid, NodeId peer, bool preferred, + std::chrono::microseconds reqtime, SequenceNumber sequence) + : m_txid(txid), m_time(reqtime), m_peer(peer), m_sequence(sequence), + m_preferred(preferred), + m_state(static_cast(State::CANDIDATE_DELAYED)) {} +}; + +//! Type alias for priorities. +using Priority = uint64_t; + +/** + * A functor with embedded salt that computes priority of an announcement. + * + * Higher priorities are selected first. + */ +class PriorityComputer { + const uint64_t m_k0, m_k1; + +public: + explicit PriorityComputer(bool deterministic) + : m_k0{deterministic ? 0 : GetRand(0xFFFFFFFFFFFFFFFF)}, + m_k1{deterministic ? 0 : GetRand(0xFFFFFFFFFFFFFFFF)} {} + + Priority operator()(const TxId &txid, NodeId peer, bool preferred) const { + uint64_t low_bits = CSipHasher(m_k0, m_k1) + .Write(txid.begin(), txid.size()) + .Write(peer) + .Finalize() >> + 1; + return low_bits | uint64_t{preferred} << 63; + } + + Priority operator()(const Announcement &ann) const { + return operator()(ann.m_txid, ann.m_peer, ann.m_preferred); + } +}; + +// Definitions for the 3 indexes used in the main data structure. +// +// Each index has a By* type to identify it, a By*View data type to represent +// the view of announcement it is sorted by, and an By*ViewExtractor type to +// convert an announcement into the By*View type. See +// https://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/reference/key_extraction.html#key_extractors +// for more information about the key extraction concept. + +// The ByPeer index is sorted by (peer, state == CANDIDATE_BEST, txid) +// +// Uses: +// * Looking up existing announcements by peer/txid, by checking both (peer, +// false, txid) and (peer, true, txid). +// * Finding all CANDIDATE_BEST announcements for a given peer in +// GetRequestable. +struct ByPeer {}; +using ByPeerView = std::tuple; +struct ByPeerViewExtractor { + using result_type = ByPeerView; + result_type operator()(const Announcement &ann) const { + return ByPeerView{ann.m_peer, ann.GetState() == State::CANDIDATE_BEST, + ann.m_txid}; + } +}; + +// The ByTxId index is sorted by (txid, state, priority). +// +// Note: priority == 0 whenever state != CANDIDATE_READY. +// +// Uses: +// * Deleting all announcements with a given txid in ForgetTxId. +// * Finding the best CANDIDATE_READY to convert to CANDIDATE_BEST, when no +// other CANDIDATE_READY or REQUESTED announcement exists for that txid. +// * Determining when no more non-COMPLETED announcements for a given txid +// exist, so the COMPLETED ones can be deleted. +struct ByTxId {}; +using ByTxIdView = std::tuple; +class ByTxIdViewExtractor { + const PriorityComputer &m_computer; + +public: + ByTxIdViewExtractor(const PriorityComputer &computer) + : m_computer(computer) {} + using result_type = ByTxIdView; + result_type operator()(const Announcement &ann) const { + const Priority prio = + (ann.GetState() == State::CANDIDATE_READY) ? m_computer(ann) : 0; + return ByTxIdView{ann.m_txid, ann.GetState(), prio}; + } +}; + +enum class WaitState { + //! Used for announcements that need efficient testing of "is their + //! timestamp in the future?". + FUTURE_EVENT, + //! Used for announcements whose timestamp is not relevant. + NO_EVENT, + //! Used for announcements that need efficient testing of "is their + //! timestamp in the past?". + PAST_EVENT, +}; + +WaitState GetWaitState(const Announcement &ann) { + if (ann.IsWaiting()) { + return WaitState::FUTURE_EVENT; + } + if (ann.IsSelectable()) { + return WaitState::PAST_EVENT; + } + return WaitState::NO_EVENT; +} + +// The ByTime index is sorted by (wait_state, time). +// +// All announcements with a timestamp in the future can be found by iterating +// the index forward from the beginning. All announcements with a timestamp in +// the past can be found by iterating the index backwards from the end. +// +// Uses: +// * Finding CANDIDATE_DELAYED announcements whose reqtime has passed, and +// REQUESTED announcements whose expiry has passed. +// * Finding CANDIDATE_READY/BEST announcements whose reqtime is in the future +// (when the clock time went backwards). +struct ByTime {}; +using ByTimeView = std::pair; +struct ByTimeViewExtractor { + using result_type = ByTimeView; + result_type operator()(const Announcement &ann) const { + return ByTimeView{GetWaitState(ann), ann.m_time}; + } +}; + +/** + * Data type for the main data structure (Announcement objects with + * ByPeer/ByTxId/ByTime indexes). + */ +using Index = boost::multi_index_container< + Announcement, + boost::multi_index::indexed_by< + boost::multi_index::ordered_unique, + ByPeerViewExtractor>, + boost::multi_index::ordered_non_unique, + ByTxIdViewExtractor>, + boost::multi_index::ordered_non_unique, + ByTimeViewExtractor>>>; + +/** Helper type to simplify syntax of iterator types. */ +template using Iter = typename Index::index::type::iterator; + +/** Per-peer statistics object. */ +struct PeerInfo { + //! Total number of announcements for this peer. + size_t m_total = 0; + //! Number of COMPLETED announcements for this peer. + size_t m_completed = 0; + //! Number of REQUESTED announcements for this peer. + size_t m_requested = 0; +}; + +} // namespace + +/** Actual implementation for TxRequestTracker's data structure. */ +class TxRequestTracker::Impl { + //! The current sequence number. Increases for every announcement. This is + //! used to sort txid returned by GetRequestable in announcement order. + SequenceNumber m_current_sequence{0}; + + //! This tracker's priority computer. + const PriorityComputer m_computer; + + //! This tracker's main data structure. + Index m_index; + + //! Map with this tracker's per-peer statistics. + std::unordered_map m_peerinfo; + + //! Wrapper around Index::...::erase that keeps m_peerinfo up to date. + template Iter Erase(Iter it) { + auto peerit = m_peerinfo.find(it->m_peer); + peerit->second.m_completed -= it->GetState() == State::COMPLETED; + peerit->second.m_requested -= it->GetState() == State::REQUESTED; + if (--peerit->second.m_total == 0) { + m_peerinfo.erase(peerit); + } + return m_index.get().erase(it); + } + + //! Wrapper around Index::...::modify that keeps m_peerinfo up to date. + template + void Modify(Iter it, Modifier modifier) { + auto peerit = m_peerinfo.find(it->m_peer); + peerit->second.m_completed -= it->GetState() == State::COMPLETED; + peerit->second.m_requested -= it->GetState() == State::REQUESTED; + m_index.get().modify(it, std::move(modifier)); + peerit->second.m_completed += it->GetState() == State::COMPLETED; + peerit->second.m_requested += it->GetState() == State::REQUESTED; + } + + //! Convert a CANDIDATE_DELAYED announcement into a CANDIDATE_READY. If this + //! makes it the new best CANDIDATE_READY (and no REQUESTED exists) and + //! better than the CANDIDATE_BEST (if any), it becomes the new + //! CANDIDATE_BEST. + void PromoteCandidateReady(Iter it) { + assert(it != m_index.get().end()); + assert(it->GetState() == State::CANDIDATE_DELAYED); + // Convert CANDIDATE_DELAYED to CANDIDATE_READY first. + Modify(it, [](Announcement &ann) { + ann.SetState(State::CANDIDATE_READY); + }); + // The following code relies on the fact that the ByTxId is sorted by + // txid, and then by state (first _DELAYED, then _READY, then + // _BEST/REQUESTED). Within the _READY announcements, the best one + // (highest priority) comes last. Thus, if an existing _BEST exists for + // the same txid that this announcement may be preferred over, it must + // immediately follow the newly created _READY. + auto it_next = std::next(it); + if (it_next == m_index.get().end() || + it_next->m_txid != it->m_txid || + it_next->GetState() == State::COMPLETED) { + // This is the new best CANDIDATE_READY, and there is no + // IsSelected() announcement for this txid already. + Modify(it, [](Announcement &ann) { + ann.SetState(State::CANDIDATE_BEST); + }); + } else if (it_next->GetState() == State::CANDIDATE_BEST) { + Priority priority_old = m_computer(*it_next); + Priority priority_new = m_computer(*it); + if (priority_new > priority_old) { + // There is a CANDIDATE_BEST announcement already, but this one + // is better. + Modify(it_next, [](Announcement &ann) { + ann.SetState(State::CANDIDATE_READY); + }); + Modify(it, [](Announcement &ann) { + ann.SetState(State::CANDIDATE_BEST); + }); + } + } + } + + //! Change the state of an announcement to something non-IsSelected(). If it + //! was IsSelected(), the next best announcement will be marked + //! CANDIDATE_BEST. + void ChangeAndReselect(Iter it, State new_state) { + assert(new_state == State::COMPLETED || + new_state == State::CANDIDATE_DELAYED); + assert(it != m_index.get().end()); + if (it->IsSelected() && it != m_index.get().begin()) { + auto it_prev = std::prev(it); + // The next best CANDIDATE_READY, if any, immediately precedes the + // REQUESTED or CANDIDATE_BEST announcement in the ByTxId index. + if (it_prev->m_txid == it->m_txid && + it_prev->GetState() == State::CANDIDATE_READY) { + // If one such CANDIDATE_READY exists (for this txid), convert + // it to CANDIDATE_BEST. + Modify(it_prev, [](Announcement &ann) { + ann.SetState(State::CANDIDATE_BEST); + }); + } + } + Modify( + it, [new_state](Announcement &ann) { ann.SetState(new_state); }); + } + + //! Check if 'it' is the only announcement for a given txid that isn't + //! COMPLETED. + bool IsOnlyNonCompleted(Iter it) { + assert(it != m_index.get().end()); + // Not allowed to call this on COMPLETED announcements. + assert(it->GetState() != State::COMPLETED); + + // This announcement has a predecessor that belongs to the same txid. + // Due to ordering, and the fact that 'it' is not COMPLETED, its + // predecessor cannot be COMPLETED here. + if (it != m_index.get().begin() && + std::prev(it)->m_txid == it->m_txid) { + return false; + } + + // This announcement has a successor that belongs to the same txid, + // and is not COMPLETED. + if (std::next(it) != m_index.get().end() && + std::next(it)->m_txid == it->m_txid && + std::next(it)->GetState() != State::COMPLETED) { + return false; + } + + return true; + } + + /** + * Convert any announcement to a COMPLETED one. If there are no + * non-COMPLETED announcements left for this txid, they are deleted. If + * this was a REQUESTED announcement, and there are other CANDIDATEs left, + * the best one is made CANDIDATE_BEST. Returns whether the announcement + * still exists. + */ + bool MakeCompleted(Iter it) { + assert(it != m_index.get().end()); + + // Nothing to be done if it's already COMPLETED. + if (it->GetState() == State::COMPLETED) { + return true; + } + + if (IsOnlyNonCompleted(it)) { + // This is the last non-COMPLETED announcement for this txid. + // Delete all. + TxId txid = it->m_txid; + do { + it = Erase(it); + } while (it != m_index.get().end() && it->m_txid == txid); + return false; + } + + // Mark the announcement COMPLETED, and select the next best + // announcement (the first CANDIDATE_READY) if needed. + ChangeAndReselect(it, State::COMPLETED); + + return true; + } + + //! Make the data structure consistent with a given point in time: + //! - REQUESTED annoucements with expiry <= now are turned into COMPLETED. + //! - CANDIDATE_DELAYED announcements with reqtime <= now are turned into + //! CANDIDATE_{READY,BEST}. + //! - CANDIDATE_{READY,BEST} announcements with reqtime > now are turned + //! into CANDIDATE_DELAYED. + void SetTimePoint(std::chrono::microseconds now) { + // Iterate over all CANDIDATE_DELAYED and REQUESTED from old to new, as + // long as they're in the past, and convert them to CANDIDATE_READY and + // COMPLETED respectively. + while (!m_index.empty()) { + auto it = m_index.get().begin(); + if (it->GetState() == State::CANDIDATE_DELAYED && + it->m_time <= now) { + PromoteCandidateReady(m_index.project(it)); + } else if (it->GetState() == State::REQUESTED && + it->m_time <= now) { + MakeCompleted(m_index.project(it)); + } else { + break; + } + } + + while (!m_index.empty()) { + // If time went backwards, we may need to demote CANDIDATE_BEST and + // CANDIDATE_READY announcements back to CANDIDATE_DELAYED. This is + // an unusual edge case, and unlikely to matter in production. + // However, it makes it much easier to specify and test + // TxRequestTracker::Impl's behaviour. + auto it = std::prev(m_index.get().end()); + if (it->IsSelectable() && it->m_time > now) { + ChangeAndReselect(m_index.project(it), + State::CANDIDATE_DELAYED); + } else { + break; + } + } + } + +public: + Impl(bool deterministic) + : m_computer(deterministic), + // Explicitly initialize m_index as we need to pass a reference to + // m_computer to ByTxHashViewExtractor. + m_index(boost::make_tuple( + boost::make_tuple(ByPeerViewExtractor(), std::less()), + boost::make_tuple(ByTxIdViewExtractor(m_computer), + std::less()), + boost::make_tuple(ByTimeViewExtractor(), + std::less()))) {} + + // Disable copying and assigning (a default copy won't work due the stateful + // ByTxIdViewExtractor). + Impl(const Impl &) = delete; + Impl &operator=(const Impl &) = delete; + + void DisconnectedPeer(NodeId peer) { + auto &index = m_index.get(); + auto it = + index.lower_bound(ByPeerView{peer, false, TxId(uint256::ZERO)}); + while (it != index.end() && it->m_peer == peer) { + // Check what to continue with after this iteration. 'it' will be + // deleted in what follows, so we need to decide what to continue + // with afterwards. There are a number of cases to consider: + // - std::next(it) is end() or belongs to a different peer. In that + // case, this is the last iteration of the loop (denote this by + // setting it_next to end()). + // - 'it' is not the only non-COMPLETED announcement for its txid. + // This means it will be deleted, but no other Announcement + // objects will be modified. Continue with std::next(it) if it + // belongs to the same peer, but decide this ahead of time (as + // 'it' may change position in what follows). + // - 'it' is the only non-COMPLETED announcement for its txid. This + // means it will be deleted along with all other announcements for + // the same txid - which may include std::next(it). However, other + // than 'it', no announcements for the same peer can be affected + // (due to (peer, txid) uniqueness). In other words, the situation + // where std::next(it) is deleted can only occur if std::next(it) + // belongs to a different peer but the same txid as 'it'. This is + // covered by the first bulletpoint already, and we'll have set + // it_next to end(). + auto it_next = + (std::next(it) == index.end() || std::next(it)->m_peer != peer) + ? index.end() + : std::next(it); + // If the announcement isn't already COMPLETED, first make it + // COMPLETED (which will mark other CANDIDATEs as CANDIDATE_BEST, or + // delete all of a txid's announcements if no non-COMPLETED ones are + // left). + if (MakeCompleted(m_index.project(it))) { + // Then actually delete the announcement (unless it was already + // deleted by MakeCompleted). + Erase(it); + } + it = it_next; + } + } + + void ForgetTxId(const TxId &txid) { + auto it = m_index.get().lower_bound( + ByTxIdView{txid, State::CANDIDATE_DELAYED, 0}); + while (it != m_index.get().end() && it->m_txid == txid) { + it = Erase(it); + } + } + + void ReceivedInv(NodeId peer, const TxId &txid, bool preferred, + std::chrono::microseconds reqtime) { + // Bail out if we already have a CANDIDATE_BEST announcement for this + // (txid, peer) combination. The case where there is a + // non-CANDIDATE_BEST announcement already will be caught by the + // uniqueness property of the ByPeer index when we try to emplace the + // new object below. + if (m_index.get().count(ByPeerView{peer, true, txid})) { + return; + } + + // Try creating the announcement with CANDIDATE_DELAYED state (which + // will fail due to the uniqueness of the ByPeer index if a + // non-CANDIDATE_BEST announcement already exists with the same txid + // and peer). Bail out in that case. + auto ret = m_index.get().emplace(txid, peer, preferred, reqtime, + m_current_sequence); + if (!ret.second) { + return; + } + + // Update accounting metadata. + ++m_peerinfo[peer].m_total; + ++m_current_sequence; + } + + //! Find the TxIds to request now from peer. + std::vector GetRequestable(NodeId peer, + std::chrono::microseconds now) { + // Move time. + SetTimePoint(now); + + // Find all CANDIDATE_BEST announcements for this peer. + std::vector selected; + auto it_peer = m_index.get().lower_bound( + ByPeerView{peer, true, TxId(uint256::ZERO)}); + while (it_peer != m_index.get().end() && + it_peer->m_peer == peer && + it_peer->GetState() == State::CANDIDATE_BEST) { + selected.emplace_back(&*it_peer); + ++it_peer; + } + + // Sort by sequence number. + std::sort(selected.begin(), selected.end(), + [](const Announcement *a, const Announcement *b) { + return a->m_sequence < b->m_sequence; + }); + + // Convert to TxId and return. + std::vector ret; + ret.reserve(selected.size()); + std::transform(selected.begin(), selected.end(), + std::back_inserter(ret), + [](const Announcement *ann) { return ann->m_txid; }); + return ret; + } + + void RequestedTx(NodeId peer, const TxId &txid, + std::chrono::microseconds expiry) { + auto it = m_index.get().find(ByPeerView{peer, true, txid}); + if (it == m_index.get().end()) { + // There is no CANDIDATE_BEST announcement, look for a _READY or + // _DELAYED instead. If the caller only ever invokes RequestedTx + // with the values returned by GetRequestable, and no other + // non-const functions other than ForgetTxHash and GetRequestable in + // between, this branch will never execute (as txids returned by + // GetRequestable always correspond to CANDIDATE_BEST + // announcements). + + it = m_index.get().find(ByPeerView{peer, false, txid}); + if (it == m_index.get().end() || + (it->GetState() != State::CANDIDATE_DELAYED && + it->GetState() != State::CANDIDATE_READY)) { + // There is no CANDIDATE announcement tracked for this peer, so + // we have nothing to do. Either this txid wasn't tracked at + // all (and the caller should have called ReceivedInv), or it + // was already requested and/or completed for other reasons and + // this is just a superfluous RequestedTx call. + return; + } + + // Look for an existing CANDIDATE_BEST or REQUESTED with the same + // txid. We only need to do this if the found announcement had a + // different state than CANDIDATE_BEST. If it did, invariants + // guarantee that no other CANDIDATE_BEST or REQUESTED can exist. + auto it_old = m_index.get().lower_bound( + ByTxIdView{txid, State::CANDIDATE_BEST, 0}); + if (it_old != m_index.get().end() && + it_old->m_txid == txid) { + if (it_old->GetState() == State::CANDIDATE_BEST) { + // The data structure's invariants require that there can be + // at most one CANDIDATE_BEST or one REQUESTED announcement + // per txid (but not both simultaneously), so we have to + // convert any existing CANDIDATE_BEST to another + // CANDIDATE_* when constructing another REQUESTED. It + // doesn't matter whether we pick CANDIDATE_READY or + // _DELAYED here, as SetTimePoint() will correct it at + // GetRequestable() time. If time only goes forward, it will + // always be _READY, so pick that to avoid extra work in + // SetTimePoint(). + Modify(it_old, [](Announcement &ann) { + ann.SetState(State::CANDIDATE_READY); + }); + } else if (it_old->GetState() == State::REQUESTED) { + // As we're no longer waiting for a response to the previous + // REQUESTED announcement, convert it to COMPLETED. This + // also helps guaranteeing progress. + Modify(it_old, [](Announcement &ann) { + ann.SetState(State::COMPLETED); + }); + } + } + } + + Modify(it, [expiry](Announcement &ann) { + ann.SetState(State::REQUESTED); + ann.m_time = expiry; + }); + } + + void ReceivedResponse(NodeId peer, const TxId &txid) { + // We need to search the ByPeer index for both (peer, false, txid) and + // (peer, true, txid). + auto it = m_index.get().find(ByPeerView{peer, false, txid}); + if (it == m_index.get().end()) { + it = m_index.get().find(ByPeerView{peer, true, txid}); + } + if (it != m_index.get().end()) { + MakeCompleted(m_index.project(it)); + } + } + + size_t CountInFlight(NodeId peer) const { + auto it = m_peerinfo.find(peer); + if (it != m_peerinfo.end()) { + return it->second.m_requested; + } + return 0; + } + + size_t CountCandidates(NodeId peer) const { + auto it = m_peerinfo.find(peer); + if (it != m_peerinfo.end()) { + return it->second.m_total - it->second.m_requested - + it->second.m_completed; + } + return 0; + } + + size_t Count(NodeId peer) const { + auto it = m_peerinfo.find(peer); + if (it != m_peerinfo.end()) { + return it->second.m_total; + } + return 0; + } + + //! Count how many announcements are being tracked in total across all peers + //! and transactions. + size_t Size() const { return m_index.size(); } +}; + +TxRequestTracker::TxRequestTracker(bool deterministic) + : m_impl{std::make_unique(deterministic)} {} + +TxRequestTracker::~TxRequestTracker() = default; + +void TxRequestTracker::ForgetTxId(const TxId &txid) { + m_impl->ForgetTxId(txid); +} +void TxRequestTracker::DisconnectedPeer(NodeId peer) { + m_impl->DisconnectedPeer(peer); +} +size_t TxRequestTracker::CountInFlight(NodeId peer) const { + return m_impl->CountInFlight(peer); +} +size_t TxRequestTracker::CountCandidates(NodeId peer) const { + return m_impl->CountCandidates(peer); +} +size_t TxRequestTracker::Count(NodeId peer) const { + return m_impl->Count(peer); +} +size_t TxRequestTracker::Size() const { + return m_impl->Size(); +} + +void TxRequestTracker::ReceivedInv(NodeId peer, const TxId &txid, + bool preferred, + std::chrono::microseconds reqtime) { + m_impl->ReceivedInv(peer, txid, preferred, reqtime); +} + +void TxRequestTracker::RequestedTx(NodeId peer, const TxId &txid, + std::chrono::microseconds expiry) { + m_impl->RequestedTx(peer, txid, expiry); +} + +void TxRequestTracker::ReceivedResponse(NodeId peer, const TxId &txid) { + m_impl->ReceivedResponse(peer, txid); +} + +std::vector +TxRequestTracker::GetRequestable(NodeId peer, std::chrono::microseconds now) { + return m_impl->GetRequestable(peer, now); +} diff --git a/src/txrequest.h b/src/txrequest.h new file mode 100644 index 000000000..28719c9e0 --- /dev/null +++ b/src/txrequest.h @@ -0,0 +1,244 @@ +// Copyright (c) 2020 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_TXREQUEST_H +#define BITCOIN_TXREQUEST_H + +#include // For NodeId +#include + +#include +#include + +#include + +/** + * Data structure to keep track of, and schedule, transaction downloads from + * peers. + * + * === Specification === + * + * We keep track of which peers have announced which transactions, and use that + * to determine which requests should go to which peer, when, and in what order. + * + * The following information is tracked per peer/tx combination + * ("announcement"): + * - Which peer announced it (through their NodeId) + * - The txid of the transaction + * - What the earliest permitted time is that that transaction can be requested + * from that peer (called "reqtime"). + * - Whether it's from a "preferred" peer or not. Which announcements get this + * flag is determined by the caller, but this is designed for outbound peers, + * or other peers that we have a higher level of trust in. Even when the + * peers' preferredness changes, the preferred flag of existing announcements + * from that peer won't change. + * - Whether or not the transaction was requested already, and if so, when it + * times out (called "expiry"). + * - Whether or not the transaction request failed already (timed out, or + * invalid transaction or NOTFOUND was received). + * + * Transaction requests are then assigned to peers, following these rules: + * + * - No transaction is requested as long as another request for the same txid + * is outstanding (it needs to fail first by passing expiry, or a NOTFOUND or + * invalid transaction has to be received for it). + * + * Rationale: to avoid wasting bandwidth on multiple copies of the same + * transaction. + * + * - The same transaction is never requested twice from the same peer, unless + * the announcement was forgotten in between, and re-announced. Announcements + * are forgotten only: + * - If a peer goes offline, all its announcements are forgotten. + * - If a transaction has been successfully received, or is otherwise no + * longer needed, the caller can call ForgetTxId, which removes all + * announcements across all peers with the specified txid. + * - If for a given txid only already-failed announcements remain, they are + * all forgotten. + * + * Rationale: giving a peer multiple chances to announce a transaction would + * allow them to bias requests in their favor, worsening + * transaction censoring attacks. The flip side is that as long as + * an attacker manages to prevent us from receiving a transaction, + * failed announcements (including those from honest peers) will + * linger longer, increasing memory usage somewhat. The impact of + * this is limited by imposing a cap on the number of tracked + * announcements per peer. As failed requests in response to + * announcements from honest peers should be rare, this almost + * solely hinders attackers. + * Transaction censoring attacks can be done by announcing + * transactions quickly while not answering requests for them. See + * https://allquantor.at/blockchainbib/pdf/miller2015topology.pdf + * for more information. + * + * - Transactions are not requested from a peer until its reqtime has passed. + * + * Rationale: enable the calling code to define a delay for less-than-ideal + * peers, so that (presumed) better peers have a chance to give + * their announcement first. + * + * - If multiple viable candidate peers exist according to the above rules, pick + * a peer as follows: + * + * - If any preferred peers are available, non-preferred peers are not + * considered for what follows. + * + * Rationale: preferred peers are more trusted by us, so are less likely to + * be under attacker control. + * + * - Pick a uniformly random peer among the candidates. + * + * Rationale: random assignments are hard to influence for attackers. + * + * Together these rules strike a balance between being fast in non-adverserial + * conditions and minimizing susceptibility to censorship attacks. An attacker + * that races the network: + * - Will be unsuccessful if all preferred connections are honest (and there is + * at least one preferred connection). + * - If there are P preferred connections of which Ph>=1 are honest, the + * attacker can delay us from learning about a transaction by k expiration + * periods, where k ~ 1 + NHG(N=P-1,K=P-Ph-1,r=1), which has mean P/(Ph+1) + * (where NHG stands for Negative Hypergeometric distribution). The "1 +" is + * due to the fact that the attacker can be the first to announce through a + * preferred connection in this scenario, which very likely means they get the + * first request. + * - If all P preferred connections are to the attacker, and there are NP + * non-preferred connections of which NPh>=1 are honest, where we assume that + * the attacker can disconnect and reconnect those connections, the + * distribution becomes k ~ P + NB(p=1-NPh/NP,r=1) (where NB stands for + * Negative Binomial distribution), which has mean P-1+NP/NPh. + * + * Complexity: + * - Memory usage is proportional to the total number of tracked announcements + * (Size()) plus the number of peers with a nonzero number of tracked + * announcements. + * - CPU usage is generally logarithmic in the total number of tracked + * announcements, plus the number of announcements affected by an operation + * (amortized O(1) per announcement). + */ +class TxRequestTracker { + // Avoid littering this header file with implementation details. + class Impl; + const std::unique_ptr m_impl; + +public: + //! Construct a TxRequestTracker. + explicit TxRequestTracker(bool deterministic = false); + ~TxRequestTracker(); + + // Conceptually, the data structure consists of a collection of + // "announcements", one for each peer/txid combination: + // + // - CANDIDATE announcements represent transactions that were announced by a + // peer, and that become available for download after their reqtime has + // passed. + // + // - REQUESTED announcements represent transactions that have been + // requested, and which we're awaiting a response for from that peer. + // Their expiry value determines when the request times out. + // + // - COMPLETED announcements represent transactions that have been requested + // from a peer, and a NOTFOUND or a transaction was received in response + // (valid or not), or they timed out. They're only kept around to prevent + // requesting them again. If only COMPLETED announcements for a given txid + // remain (so no CANDIDATE or REQUESTED ones), all of them are deleted + // (this is an invariant, and maintained by all operations below). + // + // The operations below manipulate the data structure. + + /** + * Adds a new CANDIDATE announcement. + * + * Does nothing if one already exists for that (txid, peer) combination + * (whether it's CANDIDATE, REQUESTED, or COMPLETED). + */ + void ReceivedInv(NodeId peer, const TxId &txid, bool preferred, + std::chrono::microseconds reqtime); + + /** + * Deletes all announcements for a given peer. + * + * It should be called when a peer goes offline. + */ + void DisconnectedPeer(NodeId peer); + + /** + * Deletes all announcements for a given txid. + * + * This should be called when a transaction is no longer needed. The caller + * should ensure that new announcements for the same txid will not trigger + * new ReceivedInv calls, at least in the short term after this call. + */ + void ForgetTxId(const TxId &txid); + + /** + * Find the txids to request now from peer. + * + * It does the following: + * - Convert all REQUESTED announcements (for all txids/peers) with + * (expiry <= now) to COMPLETED ones. + * - Requestable announcements are selected: CANDIDATE announcements from + * the specified peer with (reqtime <= now) for which no existing + * REQUESTED announcement with the same txid from a different peer + * exists, and for which the specified peer is the best choice among all + * (reqtime <= now) CANDIDATE announcements with the same txid (subject + * to preferredness rules, and tiebreaking using a deterministic salted + * hash of peer and txid). + * - The selected announcements are returned in announcement order (even + * if multiple were added at the same time, or when the clock went + * backwards while they were being added). This is done to minimize + * disruption from dependent transactions being requested out of order: + * if multiple dependent transactions are announced simultaneously by one + * peer, and end up being requested from them, the requests will happen + * in announcement order. + */ + std::vector GetRequestable(NodeId peer, + std::chrono::microseconds now); + + /** + * Marks a transaction as requested, with a specified expiry. + * + * If no CANDIDATE announcement for the provided peer and txid exists, this + * call has no effect. Otherwise: + * - That announcement is converted to REQUESTED. + * - If any other REQUESTED announcement for the same txid already + * existed, it means an unexpected request was made (GetRequestable will + * never advise doing so). In this case it is converted to COMPLETED, as + * we're no longer waiting for a response to it. + */ + void RequestedTx(NodeId peer, const TxId &txid, + std::chrono::microseconds expiry); + + /** + * Converts a CANDIDATE or REQUESTED announcement to a COMPLETED one. If no + * such announcement exists for the provided peer and txid, nothing happens. + * + * It should be called whenever a transaction or NOTFOUND was received from + * a peer. When the transaction is not needed entirely anymore, ForgetTxId + * should be called instead of, or in addition to, this call. + */ + void ReceivedResponse(NodeId peer, const TxId &txid); + + // The operations below inspect the data structure. + + /** Count how many REQUESTED announcements a peer has. */ + size_t CountInFlight(NodeId peer) const; + + /** Count how many CANDIDATE announcements a peer has. */ + size_t CountCandidates(NodeId peer) const; + + /** + * Count how many announcements a peer has (REQUESTED, CANDIDATE, and + * COMPLETED combined). + */ + size_t Count(NodeId peer) const; + + /** + * Count how many announcements are being tracked in total across all peers + * and transaction hashes. + */ + size_t Size() const; +}; + +#endif // BITCOIN_TXREQUEST_H diff --git a/src/uint256.cpp b/src/uint256.cpp index bacc91dce..4f2b5b995 100644 --- a/src/uint256.cpp +++ b/src/uint256.cpp @@ -1,73 +1,74 @@ // 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 #include template base_blob::base_blob(const std::vector &vch) { assert(vch.size() == sizeof(m_data)); memcpy(m_data, vch.data(), sizeof(m_data)); } template std::string base_blob::GetHex() const { uint8_t m_data_rev[WIDTH]; for (int i = 0; i < WIDTH; ++i) { m_data_rev[i] = m_data[WIDTH - 1 - i]; } return HexStr(m_data_rev); } template void base_blob::SetHex(const char *psz) { memset(m_data, 0, sizeof(m_data)); // skip leading spaces while (IsSpace(*psz)) { psz++; } // skip 0x if (psz[0] == '0' && ToLower(psz[1]) == 'x') { psz += 2; } // hex string to uint size_t digits = 0; while (::HexDigit(psz[digits]) != -1) { digits++; } uint8_t *p1 = (uint8_t *)m_data; uint8_t *pend = p1 + WIDTH; while (digits > 0 && p1 < pend) { *p1 = ::HexDigit(psz[--digits]); if (digits > 0) { *p1 |= uint8_t(::HexDigit(psz[--digits])) << 4; p1++; } } } template void base_blob::SetHex(const std::string &str) { SetHex(str.c_str()); } // Explicit instantiations for base_blob<160> template base_blob<160>::base_blob(const std::vector &); template std::string base_blob<160>::GetHex() const; template std::string base_blob<160>::ToString() const; template void base_blob<160>::SetHex(const char *); template void base_blob<160>::SetHex(const std::string &); // Explicit instantiations for base_blob<256> template base_blob<256>::base_blob(const std::vector &); template std::string base_blob<256>::GetHex() const; template std::string base_blob<256>::ToString() const; template void base_blob<256>::SetHex(const char *); template void base_blob<256>::SetHex(const std::string &); +const uint256 uint256::ZERO(0); const uint256 uint256::ONE(1); diff --git a/src/uint256.h b/src/uint256.h index 0b3c4b76b..0732096e1 100644 --- a/src/uint256.h +++ b/src/uint256.h @@ -1,169 +1,170 @@ // 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. #ifndef BITCOIN_UINT256_H #define BITCOIN_UINT256_H #include #include #include #include #include /** Template base class for fixed-sized opaque blobs. */ template class base_blob { protected: static constexpr int WIDTH = BITS / 8; uint8_t m_data[WIDTH]; public: /* construct 0 value by default */ constexpr base_blob() : m_data() {} /* constructor for constants between 1 and 255 */ constexpr explicit base_blob(uint8_t v) : m_data{v} {} explicit base_blob(const std::vector &vch); bool IsNull() const { for (int i = 0; i < WIDTH; i++) { if (m_data[i] != 0) { return false; } } return true; } void SetNull() { memset(m_data, 0, sizeof(m_data)); } inline int Compare(const base_blob &other) const { for (size_t i = 0; i < sizeof(m_data); i++) { uint8_t a = m_data[sizeof(m_data) - 1 - i]; uint8_t b = other.m_data[sizeof(m_data) - 1 - i]; if (a > b) { return 1; } if (a < b) { return -1; } } return 0; } friend inline bool operator==(const base_blob &a, const base_blob &b) { return a.Compare(b) == 0; } friend inline bool operator!=(const base_blob &a, const base_blob &b) { return a.Compare(b) != 0; } friend inline bool operator<(const base_blob &a, const base_blob &b) { return a.Compare(b) < 0; } friend inline bool operator<=(const base_blob &a, const base_blob &b) { return a.Compare(b) <= 0; } friend inline bool operator>(const base_blob &a, const base_blob &b) { return a.Compare(b) > 0; } friend inline bool operator>=(const base_blob &a, const base_blob &b) { return a.Compare(b) >= 0; } std::string GetHex() const; void SetHex(const char *psz); void SetHex(const std::string &str); std::string ToString() const { return GetHex(); } const uint8_t *data() const { return m_data; } uint8_t *data() { return m_data; } uint8_t *begin() { return &m_data[0]; } uint8_t *end() { return &m_data[WIDTH]; } const uint8_t *begin() const { return &m_data[0]; } const uint8_t *end() const { return &m_data[WIDTH]; } unsigned int size() const { return sizeof(m_data); } uint64_t GetUint64(int pos) const { const uint8_t *ptr = m_data + pos * 8; return uint64_t(ptr[0]) | (uint64_t(ptr[1]) << 8) | (uint64_t(ptr[2]) << 16) | (uint64_t(ptr[3]) << 24) | (uint64_t(ptr[4]) << 32) | (uint64_t(ptr[5]) << 40) | (uint64_t(ptr[6]) << 48) | (uint64_t(ptr[7]) << 56); } template void Serialize(Stream &s) const { s.write((char *)m_data, sizeof(m_data)); } template void Unserialize(Stream &s) { s.read((char *)m_data, sizeof(m_data)); } }; /** * 160-bit opaque blob. * @note This type is called uint160 for historical reasons only. It is an * opaque blob of 160 bits and has no integer operations. */ class uint160 : public base_blob<160> { public: constexpr uint160() {} explicit uint160(const std::vector &vch) : base_blob<160>(vch) {} }; /** * 256-bit opaque blob. * @note This type is called uint256 for historical reasons only. It is an * opaque blob of 256 bits and has no integer operations. Use arith_uint256 if * those are required. */ class uint256 : public base_blob<256> { public: constexpr uint256() {} constexpr explicit uint256(uint8_t v) : base_blob<256>(v) {} explicit uint256(const std::vector &vch) : base_blob<256>(vch) {} + static const uint256 ZERO; static const uint256 ONE; }; /** * uint256 from const char *. * This is a separate function because the constructor uint256(const char*) can * result in dangerously catching uint256(0). */ inline uint256 uint256S(const char *str) { uint256 rv; rv.SetHex(str); return rv; } /** * uint256 from std::string. * This is a separate function because the constructor uint256(const std::string * &str) can result in dangerously catching uint256(0) via std::string(const * char*). */ inline uint256 uint256S(const std::string &str) { uint256 rv; rv.SetHex(str); return rv; } inline uint160 uint160S(const char *str) { uint160 rv; rv.SetHex(str); return rv; } inline uint160 uint160S(const std::string &str) { uint160 rv; rv.SetHex(str); return rv; } #endif // BITCOIN_UINT256_H