Add txrequest fuzz tests

This adds a fuzz test that reimplements a naive reimplementation of
TxRequestTracker (with up to 16 fixed peers and 16 fixed txhashes),
and compares the real implementation against it.

2 files changed, 375 insertions, 0 deletions

diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 368ca638b0..44a1f0c914 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -151,6 +151,7 @@ FUZZ_TARGETS = \
   test/fuzz/tx_in_deserialize \
   test/fuzz/tx_out \
   test/fuzz/txoutcompressor_deserialize \
+  test/fuzz/txrequest \
   test/fuzz/txundo_deserialize \
   test/fuzz/uint160_deserialize \
   test/fuzz/uint256_deserialize
@@ -1215,6 +1216,12 @@ test_fuzz_txoutcompressor_deserialize_LDADD = $(FUZZ_SUITE_LD_COMMON)
 test_fuzz_txoutcompressor_deserialize_LDFLAGS = $(FUZZ_SUITE_LDFLAGS_COMMON)
 test_fuzz_txoutcompressor_deserialize_SOURCES = test/fuzz/deserialize.cpp
 
+test_fuzz_txrequest_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
+test_fuzz_txrequest_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
+test_fuzz_txrequest_LDADD = $(FUZZ_SUITE_LD_COMMON)
+test_fuzz_txrequest_LDFLAGS = $(FUZZ_SUITE_LDFLAGS_COMMON)
+test_fuzz_txrequest_SOURCES = test/fuzz/txrequest.cpp
+
 test_fuzz_txundo_deserialize_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) -DTXUNDO_DESERIALIZE=1
 test_fuzz_txundo_deserialize_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
 test_fuzz_txundo_deserialize_LDADD = $(FUZZ_SUITE_LD_COMMON)
diff --git a/src/test/fuzz/txrequest.cpp b/src/test/fuzz/txrequest.cpp
new file mode 100644
index 0000000000..4a8e32d105
--- /dev/null
+++ b/src/test/fuzz/txrequest.cpp
@@ -0,0 +1,368 @@
+// 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 <crypto/common.h>
+#include <crypto/sha256.h>
+#include <crypto/siphash.h>
+#include <primitives/transaction.h>
+#include <test/fuzz/fuzz.h>
+#include <txrequest.h>
+
+#include <bitset>
+#include <cstdint>
+#include <queue>
+#include <vector>
+
+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::chrono::microseconds, std::vector<std::chrono::microseconds>,
+        std::greater<std::chrono::microseconds>> 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, GenTxid{is_wtxid, 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<std::tuple<uint64_t, int, bool>> 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].GetHash());
+            assert(std::get<2>(result[pos]) == actual[pos].IsWtxid());
+        }
+    }
+
+    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<uint8_t>& 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();
+}