From 3c7fe0e5a0ee1abf4dc263ae5310e68253c866e1 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 29 Sep 2020 16:10:16 -0700 Subject: Add txrequest unit tests Add unit tests for TxRequestTracker. Several scenarios are tested, randomly interleaved with eachother. Includes a test by Antoine Riard (ariard). --- src/txrequest.cpp | 134 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 133 insertions(+), 1 deletion(-) (limited to 'src/txrequest.cpp') diff --git a/src/txrequest.cpp b/src/txrequest.cpp index bb64a00847..cabdc63957 100644 --- a/src/txrequest.cpp +++ b/src/txrequest.cpp @@ -228,6 +228,69 @@ struct PeerInfo { size_t m_requested = 0; //!< Number of REQUESTED announcements for this peer. }; +/** Per-txhash statistics object. Only used for sanity checking. */ +struct TxHashInfo +{ + //! Number of CANDIDATE_DELAYED announcements for this txhash. + size_t m_candidate_delayed = 0; + //! Number of CANDIDATE_READY announcements for this txhash. + size_t m_candidate_ready = 0; + //! Number of CANDIDATE_BEST announcements for this txhash (at most one). + size_t m_candidate_best = 0; + //! Number of REQUESTED announcements for this txhash (at most one; mutually exclusive with CANDIDATE_BEST). + size_t m_requested = 0; + //! The priority of the CANDIDATE_BEST announcement if one exists, or max() otherwise. + Priority m_priority_candidate_best = std::numeric_limits::max(); + //! The highest priority of all CANDIDATE_READY announcements (or min() if none exist). + Priority m_priority_best_candidate_ready = std::numeric_limits::min(); + //! All peers we have an announcement for this txhash for. + std::vector m_peers; +}; + +/** Compare two PeerInfo objects. Only used for sanity checking. */ +bool operator==(const PeerInfo& a, const PeerInfo& b) +{ + return std::tie(a.m_total, a.m_completed, a.m_requested) == + std::tie(b.m_total, b.m_completed, b.m_requested); +}; + +/** (Re)compute the PeerInfo map from the index. Only used for sanity checking. */ +std::unordered_map RecomputePeerInfo(const Index& index) +{ + std::unordered_map ret; + for (const Announcement& ann : index) { + PeerInfo& info = ret[ann.m_peer]; + ++info.m_total; + info.m_requested += (ann.m_state == State::REQUESTED); + info.m_completed += (ann.m_state == State::COMPLETED); + } + return ret; +} + +/** Compute the TxHashInfo map. Only used for sanity checking. */ +std::map ComputeTxHashInfo(const Index& index, const PriorityComputer& computer) +{ + std::map ret; + for (const Announcement& ann : index) { + TxHashInfo& info = ret[ann.m_txhash]; + // Classify how many announcements of each state we have for this txhash. + info.m_candidate_delayed += (ann.m_state == State::CANDIDATE_DELAYED); + info.m_candidate_ready += (ann.m_state == State::CANDIDATE_READY); + info.m_candidate_best += (ann.m_state == State::CANDIDATE_BEST); + info.m_requested += (ann.m_state == State::REQUESTED); + // And track the priority of the best CANDIDATE_READY/CANDIDATE_BEST announcements. + if (ann.m_state == State::CANDIDATE_BEST) { + info.m_priority_candidate_best = computer(ann); + } + if (ann.m_state == State::CANDIDATE_READY) { + info.m_priority_best_candidate_ready = std::max(info.m_priority_best_candidate_ready, computer(ann)); + } + // Also keep track of which peers this txhash has an announcement for (so we can detect duplicates). + info.m_peers.push_back(ann.m_peer); + } + return ret; +} + } // namespace /** Actual implementation for TxRequestTracker's data structure. */ @@ -239,12 +302,63 @@ class TxRequestTracker::Impl { //! This tracker's priority computer. const PriorityComputer m_computer; - //! This tracker's main data structure. + //! This tracker's main data structure. See SanityCheck() for the invariants that apply to it. Index m_index; //! Map with this tracker's per-peer statistics. std::unordered_map m_peerinfo; +public: + void SanityCheck() const + { + // Recompute m_peerdata from m_index. This verifies the data in it as it should just be caching statistics + // on m_index. It also verifies the invariant that no PeerInfo announcements with m_total==0 exist. + assert(m_peerinfo == RecomputePeerInfo(m_index)); + + // Calculate per-txhash statistics from m_index, and validate invariants. + for (auto& item : ComputeTxHashInfo(m_index, m_computer)) { + TxHashInfo& info = item.second; + + // Cannot have only COMPLETED peer (txhash should have been forgotten already) + assert(info.m_candidate_delayed + info.m_candidate_ready + info.m_candidate_best + info.m_requested > 0); + + // Can have at most 1 CANDIDATE_BEST/REQUESTED peer + assert(info.m_candidate_best + info.m_requested <= 1); + + // If there are any CANDIDATE_READY announcements, there must be exactly one CANDIDATE_BEST or REQUESTED + // announcement. + if (info.m_candidate_ready > 0) { + assert(info.m_candidate_best + info.m_requested == 1); + } + + // If there is both a CANDIDATE_READY and a CANDIDATE_BEST announcement, the CANDIDATE_BEST one must be + // at least as good (equal or higher priority) as the best CANDIDATE_READY. + if (info.m_candidate_ready && info.m_candidate_best) { + assert(info.m_priority_candidate_best >= info.m_priority_best_candidate_ready); + } + + // No txhash can have been announced by the same peer twice. + std::sort(info.m_peers.begin(), info.m_peers.end()); + assert(std::adjacent_find(info.m_peers.begin(), info.m_peers.end()) == info.m_peers.end()); + } + } + + void PostGetRequestableSanityCheck(std::chrono::microseconds now) const + { + for (const Announcement& ann : m_index) { + if (ann.IsWaiting()) { + // REQUESTED and CANDIDATE_DELAYED must have a time in the future (they should have been converted + // to COMPLETED/CANDIDATE_READY respectively). + assert(ann.m_time > now); + } else if (ann.IsSelectable()) { + // CANDIDATE_READY and CANDIDATE_BEST cannot have a time in the future (they should have remained + // CANDIDATE_DELAYED, or should have been converted back to it if time went backwards). + assert(ann.m_time <= now); + } + } + } + +private: //! Wrapper around Index::...::erase that keeps m_peerinfo up to date. template Iter Erase(Iter it) @@ -570,6 +684,13 @@ public: //! Count how many announcements are being tracked in total across all peers and transactions. size_t Size() const { return m_index.size(); } + + uint64_t ComputePriority(const uint256& txhash, NodeId peer, bool preferred) const + { + // Return Priority as a uint64_t as Priority is internal. + return uint64_t{m_computer(txhash, peer, preferred)}; + } + }; TxRequestTracker::TxRequestTracker(bool deterministic) : @@ -583,6 +704,12 @@ size_t TxRequestTracker::CountInFlight(NodeId peer) const { return m_impl->Count 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::SanityCheck() const { m_impl->SanityCheck(); } + +void TxRequestTracker::PostGetRequestableSanityCheck(std::chrono::microseconds now) const +{ + m_impl->PostGetRequestableSanityCheck(now); +} void TxRequestTracker::ReceivedInv(NodeId peer, const GenTxid& gtxid, bool preferred, std::chrono::microseconds reqtime) @@ -604,3 +731,8 @@ std::vector TxRequestTracker::GetRequestable(NodeId peer, std::chrono:: { return m_impl->GetRequestable(peer, now); } + +uint64_t TxRequestTracker::ComputePriority(const uint256& txhash, NodeId peer, bool preferred) const +{ + return m_impl->ComputePriority(txhash, peer, preferred); +} -- cgit v1.2.3