diff --git a/src/test/fuzz/CMakeLists.txt b/src/test/fuzz/CMakeLists.txt --- a/src/test/fuzz/CMakeLists.txt +++ b/src/test/fuzz/CMakeLists.txt @@ -160,6 +160,7 @@ transaction tx_in tx_out + txrequest ) add_deserialize_fuzz_targets( diff --git a/src/test/fuzz/txrequest.cpp b/src/test/fuzz/txrequest.cpp new file mode 100644 --- /dev/null +++ b/src/test/fuzz/txrequest.cpp @@ -0,0 +1,390 @@ +// 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 + +namespace { + +constexpr int MAX_TXHASHES = 16; +constexpr int MAX_PEERS = 16; + +//! Randomly generated GenTxids used in this test (length is MAX_TXHASHES). +uint256 TXHASHES[MAX_TXHASHES]; + +//! Precomputed random durations (positive and negative, each ~exponentially +//! distributed). +std::chrono::microseconds DELAYS[256]; + +struct Initializer { + Initializer() { + for (uint8_t txhash = 0; txhash < MAX_TXHASHES; txhash += 1) { + CSHA256().Write(&txhash, 1).Finalize(TXHASHES[txhash].begin()); + } + int i = 0; + // DELAYS[N] for N=0..15 is just N microseconds. + for (; i < 16; ++i) { + DELAYS[i] = std::chrono::microseconds{i}; + } + // DELAYS[N] for N=16..127 has randomly-looking but roughly + // exponentially increasing values up to 198.416453 seconds. + for (; i < 128; ++i) { + int diff_bits = ((i - 10) * 2) / 9; + uint64_t diff = + 1 + (CSipHasher(0, 0).Write(i).Finalize() >> (64 - diff_bits)); + DELAYS[i] = DELAYS[i - 1] + std::chrono::microseconds{diff}; + } + // DELAYS[N] for N=128..255 are negative delays with the same magnitude + // as N=0..127. + for (; i < 256; ++i) { + DELAYS[i] = -DELAYS[255 - i]; + } + } +} g_initializer; + +/** Tester class for TxRequestTracker + * + * It includes a naive reimplementation of its behavior, for a limited set + * of MAX_TXHASHES distinct txids, and MAX_PEERS peer identifiers. + * + * All of the public member functions perform the same operation on + * an actual TxRequestTracker and on the state of the reimplementation. + * The output of GetRequestable is compared with the expected value + * as well. + * + * Check() calls the TxRequestTracker's sanity check, plus compares the + * output of the constant accessors (Size(), CountLoad(), CountTracked()) + * with expected values. + */ +class Tester { + //! TxRequestTracker object being tested. + TxRequestTracker m_tracker; + + //! States for txid/peer combinations in the naive data structure. + enum class State { + NOTHING, //!< Absence of this txid/peer combination + + // Note that this implementation does not distinguish between + // DELAYED/READY/BEST variants of CANDIDATE. + CANDIDATE, + REQUESTED, + COMPLETED, + }; + + //! Sequence numbers, incremented whenever a new CANDIDATE is added. + uint64_t m_current_sequence{0}; + + //! List of future 'events' (all inserted reqtimes/exptimes). This is used + //! to implement AdvanceToEvent. + std::priority_queue, + std::greater> + m_events; + + //! Information about a txhash/peer combination. + struct Announcement { + std::chrono::microseconds m_time; + uint64_t m_sequence; + State m_state{State::NOTHING}; + bool m_preferred; + bool m_is_wtxid; + uint64_t m_priority; //!< Precomputed priority. + }; + + //! Information about all txhash/peer combination. + Announcement m_announcements[MAX_TXHASHES][MAX_PEERS]; + + //! The current time; can move forward and backward. + std::chrono::microseconds m_now{244466666}; + + //! Delete txhashes whose only announcements are COMPLETED. + void Cleanup(int txhash) { + bool all_nothing = true; + for (int peer = 0; peer < MAX_PEERS; ++peer) { + const Announcement &ann = m_announcements[txhash][peer]; + if (ann.m_state != State::NOTHING) { + if (ann.m_state != State::COMPLETED) { + return; + } + all_nothing = false; + } + } + if (all_nothing) { + return; + } + for (int peer = 0; peer < MAX_PEERS; ++peer) { + m_announcements[txhash][peer].m_state = State::NOTHING; + } + } + + //! Find the current best peer to request from for a txhash (or -1 if none). + int GetSelected(int txhash) const { + int ret = -1; + uint64_t ret_priority = 0; + for (int peer = 0; peer < MAX_PEERS; ++peer) { + const Announcement &ann = m_announcements[txhash][peer]; + // Return -1 if there already is a (non-expired) in-flight request. + if (ann.m_state == State::REQUESTED) { + return -1; + } + // If it's a viable candidate, see if it has lower priority than the + // best one so far. + if (ann.m_state == State::CANDIDATE && ann.m_time <= m_now) { + if (ret == -1 || ann.m_priority > ret_priority) { + std::tie(ret, ret_priority) = + std::tie(peer, ann.m_priority); + } + } + } + return ret; + } + +public: + Tester() : m_tracker(true) {} + + std::chrono::microseconds Now() const { return m_now; } + + void AdvanceTime(std::chrono::microseconds offset) { + m_now += offset; + while (!m_events.empty() && m_events.top() <= m_now) { + m_events.pop(); + } + } + + void AdvanceToEvent() { + while (!m_events.empty() && m_events.top() <= m_now) { + m_events.pop(); + } + if (!m_events.empty()) { + m_now = m_events.top(); + m_events.pop(); + } + } + + void DisconnectedPeer(int peer) { + // Apply to naive structure: all announcements for that peer are wiped. + for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) { + if (m_announcements[txhash][peer].m_state != State::NOTHING) { + m_announcements[txhash][peer].m_state = State::NOTHING; + Cleanup(txhash); + } + } + + // Call TxRequestTracker's implementation. + m_tracker.DisconnectedPeer(peer); + } + + void ForgetTxHash(int txhash) { + // Apply to naive structure: all announcements for that txhash are + // wiped. + for (int peer = 0; peer < MAX_PEERS; ++peer) { + m_announcements[txhash][peer].m_state = State::NOTHING; + } + Cleanup(txhash); + + // Call TxRequestTracker's implementation. + m_tracker.ForgetTxHash(TXHASHES[txhash]); + } + + void ReceivedInv(int peer, int txhash, bool is_wtxid, bool preferred, + std::chrono::microseconds reqtime) { + // Apply to naive structure: if no announcement for txidnum/peer + // combination already, create a new CANDIDATE; otherwise do nothing. + Announcement &ann = m_announcements[txhash][peer]; + if (ann.m_state == State::NOTHING) { + ann.m_preferred = preferred; + ann.m_state = State::CANDIDATE; + ann.m_time = reqtime; + ann.m_is_wtxid = is_wtxid; + ann.m_sequence = m_current_sequence++; + ann.m_priority = m_tracker.ComputePriority(TXHASHES[txhash], peer, + ann.m_preferred); + + // Add event so that AdvanceToEvent can quickly jump to the point + // where its reqtime passes. + if (reqtime > m_now) { + m_events.push(reqtime); + } + } + + // Call TxRequestTracker's implementation. + m_tracker.ReceivedInv(peer, TxId{TXHASHES[txhash]}, preferred, reqtime); + } + + void RequestedTx(int peer, int txhash, std::chrono::microseconds exptime) { + // Apply to naive structure: if a CANDIDATE announcement exists for + // peer/txhash, convert it to REQUESTED, and change any existing + // REQUESTED announcement for the same txhash to COMPLETED. + if (m_announcements[txhash][peer].m_state == State::CANDIDATE) { + for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) { + if (m_announcements[txhash][peer2].m_state == + State::REQUESTED) { + m_announcements[txhash][peer2].m_state = State::COMPLETED; + } + } + m_announcements[txhash][peer].m_state = State::REQUESTED; + m_announcements[txhash][peer].m_time = exptime; + } + + // Add event so that AdvanceToEvent can quickly jump to the point where + // its exptime passes. + if (exptime > m_now) { + m_events.push(exptime); + } + + // Call TxRequestTracker's implementation. + m_tracker.RequestedTx(peer, TXHASHES[txhash], exptime); + } + + void ReceivedResponse(int peer, int txhash) { + // Apply to naive structure: convert anything to COMPLETED. + if (m_announcements[txhash][peer].m_state != State::NOTHING) { + m_announcements[txhash][peer].m_state = State::COMPLETED; + Cleanup(txhash); + } + + // Call TxRequestTracker's implementation. + m_tracker.ReceivedResponse(peer, TXHASHES[txhash]); + } + + void GetRequestable(int peer) { + // Implement using naive structure: + + //! list of (sequence number, txhash, is_wtxid) tuples. + std::vector> result; + for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) { + // Mark any expired REQUESTED announcements as COMPLETED. + for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) { + Announcement &ann2 = m_announcements[txhash][peer2]; + if (ann2.m_state == State::REQUESTED && ann2.m_time <= m_now) { + ann2.m_state = State::COMPLETED; + break; + } + } + // And delete txids with only COMPLETED announcements left. + Cleanup(txhash); + // CANDIDATEs for which this announcement has the highest priority + // get returned. + const Announcement &ann = m_announcements[txhash][peer]; + if (ann.m_state == State::CANDIDATE && + GetSelected(txhash) == peer) { + result.emplace_back(ann.m_sequence, txhash, ann.m_is_wtxid); + } + } + // Sort the results by sequence number. + std::sort(result.begin(), result.end()); + + // Compare with TxRequestTracker's implementation. + const auto actual = m_tracker.GetRequestable(peer, m_now); + + m_tracker.PostGetRequestableSanityCheck(m_now); + assert(result.size() == actual.size()); + for (size_t pos = 0; pos < actual.size(); ++pos) { + assert(TXHASHES[std::get<1>(result[pos])] == actual[pos]); + } + } + + void Check() { + // Compare CountTracked and CountLoad with naive structure. + size_t total = 0; + for (int peer = 0; peer < MAX_PEERS; ++peer) { + size_t tracked = 0; + size_t inflight = 0; + size_t candidates = 0; + for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) { + tracked += + m_announcements[txhash][peer].m_state != State::NOTHING; + inflight += + m_announcements[txhash][peer].m_state == State::REQUESTED; + candidates += + m_announcements[txhash][peer].m_state == State::CANDIDATE; + } + assert(m_tracker.Count(peer) == tracked); + assert(m_tracker.CountInFlight(peer) == inflight); + assert(m_tracker.CountCandidates(peer) == candidates); + total += tracked; + } + // Compare Size. + assert(m_tracker.Size() == total); + + // Invoke internal consistency check of TxRequestTracker object. + m_tracker.SanityCheck(); + } +}; +} // namespace + +void test_one_input(const std::vector &buffer) { + // Tester object (which encapsulates a TxRequestTracker). + Tester tester; + + // Decode the input as a sequence of instructions with parameters + auto it = buffer.begin(); + while (it != buffer.end()) { + int cmd = *(it++) % 11; + int peer, txidnum, delaynum; + switch (cmd) { + case 0: // Make time jump to the next event (m_time of CANDIDATE or + // REQUESTED) + tester.AdvanceToEvent(); + break; + case 1: // Change time + delaynum = it == buffer.end() ? 0 : *(it++); + tester.AdvanceTime(DELAYS[delaynum]); + break; + case 2: // Query for requestable txs + peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS; + tester.GetRequestable(peer); + break; + case 3: // Peer went offline + peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS; + tester.DisconnectedPeer(peer); + break; + case 4: // No longer need tx + txidnum = it == buffer.end() ? 0 : *(it++); + tester.ForgetTxHash(txidnum % MAX_TXHASHES); + break; + case 5: // Received immediate preferred inv + case 6: // Same, but non-preferred. + peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS; + txidnum = it == buffer.end() ? 0 : *(it++); + tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, + (txidnum / MAX_TXHASHES) & 1, cmd & 1, + std::chrono::microseconds::min()); + break; + case 7: // Received delayed preferred inv + case 8: // Same, but non-preferred. + peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS; + txidnum = it == buffer.end() ? 0 : *(it++); + delaynum = it == buffer.end() ? 0 : *(it++); + tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, + (txidnum / MAX_TXHASHES) & 1, cmd & 1, + tester.Now() + DELAYS[delaynum]); + break; + case 9: // Requested tx from peer + peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS; + txidnum = it == buffer.end() ? 0 : *(it++); + delaynum = it == buffer.end() ? 0 : *(it++); + tester.RequestedTx(peer, txidnum % MAX_TXHASHES, + tester.Now() + DELAYS[delaynum]); + break; + case 10: // Received response + peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS; + txidnum = it == buffer.end() ? 0 : *(it++); + tester.ReceivedResponse(peer, txidnum % MAX_TXHASHES); + break; + default: + assert(false); + } + } + tester.Check(); +}