diff --git a/src/invrequest.h b/src/invrequest.h --- a/src/invrequest.h +++ b/src/invrequest.h @@ -7,7 +7,6 @@ #include #include // For NodeId -#include #include #include @@ -17,6 +16,7 @@ #include #include #include +#include #include /** @@ -123,7 +123,14 @@ * announcements, plus the number of announcements affected by an operation * (amortized O(1) per announcement). */ -class InvRequestTracker { +template class InvRequestTracker { + /* + * Only uint256-based InvId types are supported for now. + * FIXME: use a template constraint when C++20 is available. + */ + static_assert(std::is_base_of::value, + "InvRequestTracker inv id type should be uint256 or derived"); + /** * The various states a (invid, peer) pair can be in. * @@ -174,7 +181,7 @@ */ struct Announcement { /** InvId that was announced. */ - const TxId m_invid; + const InvId m_invid; /** * For CANDIDATE_{DELAYED,BEST,READY} the reqtime; for REQUESTED the * expiry. @@ -229,7 +236,7 @@ * Construct a new announcement from scratch, initially in * CANDIDATE_DELAYED state. */ - Announcement(const TxId &invid, NodeId peer, bool preferred, + Announcement(const InvId &invid, NodeId peer, bool preferred, std::chrono::microseconds reqtime, SequenceNumber sequence) : m_invid(invid), m_time(reqtime), m_peer(peer), m_sequence(sequence), m_preferred(preferred), @@ -252,7 +259,7 @@ : m_k0{deterministic ? 0 : GetRand(0xFFFFFFFFFFFFFFFF)}, m_k1{deterministic ? 0 : GetRand(0xFFFFFFFFFFFFFFFF)} {} - Priority operator()(const TxId &invid, NodeId peer, + Priority operator()(const InvId &invid, NodeId peer, bool preferred) const { uint64_t low_bits = CSipHasher(m_k0, m_k1) .Write(invid.begin(), invid.size()) @@ -285,7 +292,7 @@ // * Finding all CANDIDATE_BEST announcements for a given peer in // GetRequestable. struct ByPeer {}; - using ByPeerView = std::tuple; + using ByPeerView = std::tuple; struct ByPeerViewExtractor { using result_type = ByPeerView; result_type operator()(const Announcement &ann) const { @@ -306,7 +313,7 @@ // * Determining when no more non-COMPLETED announcements for a given invid // exist, so the COMPLETED ones can be deleted. struct ByInvId {}; - using ByInvIdView = std::tuple; + using ByInvIdView = std::tuple; class ByInvIdViewExtractor { const PriorityComputer &m_computer; @@ -381,7 +388,7 @@ /** Helper type to simplify syntax of iterator types. */ template - using Iter = typename Index::index::type::iterator; + using Iter = typename Index::template index::type::iterator; /** Per-peer statistics object. */ struct PeerInfo { @@ -440,9 +447,9 @@ } /** Compute the InvIdInfo map. Only used for sanity checking. */ - static std::map + static std::map ComputeInvIdInfo(const Index &index, const PriorityComputer &computer) { - std::map ret; + std::map ret; for (const Announcement &ann : index) { InvIdInfo &info = ret[ann.m_invid]; // Classify how many announcements of each state we have for this @@ -477,7 +484,7 @@ if (--peerit->second.m_total == 0) { m_peerinfo.erase(peerit); } - return m_index.get().erase(it); + return m_index.template get().erase(it); } //! Wrapper around Index::...::modify that keeps m_peerinfo up to date. @@ -486,7 +493,7 @@ 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)); + m_index.template get().modify(it, std::move(modifier)); peerit->second.m_completed += it->GetState() == State::COMPLETED; peerit->second.m_requested += it->GetState() == State::REQUESTED; } @@ -496,7 +503,7 @@ //! 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 != m_index.template get().end()); assert(it->GetState() == State::CANDIDATE_DELAYED); // Convert CANDIDATE_DELAYED to CANDIDATE_READY first. Modify(it, [](Announcement &ann) { @@ -509,7 +516,7 @@ // the same invid 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() || + if (it_next == m_index.template get().end() || it_next->m_invid != it->m_invid || it_next->GetState() == State::COMPLETED) { // This is the new best CANDIDATE_READY, and there is no @@ -539,8 +546,8 @@ 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()) { + assert(it != m_index.template get().end()); + if (it->IsSelected() && it != m_index.template 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 ByInvId index. @@ -560,21 +567,21 @@ //! Check if 'it' is the only announcement for a given invid that isn't //! COMPLETED. bool IsOnlyNonCompleted(Iter it) { - assert(it != m_index.get().end()); + assert(it != m_index.template 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 invid. // Due to ordering, and the fact that 'it' is not COMPLETED, its // predecessor cannot be COMPLETED here. - if (it != m_index.get().begin() && + if (it != m_index.template get().begin() && std::prev(it)->m_invid == it->m_invid) { return false; } // This announcement has a successor that belongs to the same invid, // and is not COMPLETED. - if (std::next(it) != m_index.get().end() && + if (std::next(it) != m_index.template get().end() && std::next(it)->m_invid == it->m_invid && std::next(it)->GetState() != State::COMPLETED) { return false; @@ -591,7 +598,7 @@ * still exists. */ bool MakeCompleted(Iter it) { - assert(it != m_index.get().end()); + assert(it != m_index.template get().end()); // Nothing to be done if it's already COMPLETED. if (it->GetState() == State::COMPLETED) { @@ -601,10 +608,10 @@ if (IsOnlyNonCompleted(it)) { // This is the last non-COMPLETED announcement for this invid. // Delete all. - TxId invid = it->m_invid; + InvId invid = it->m_invid; do { it = Erase(it); - } while (it != m_index.get().end() && + } while (it != m_index.template get().end() && it->m_invid == invid); return false; } @@ -623,7 +630,7 @@ //! - CANDIDATE_{READY,BEST} announcements with reqtime > now are turned //! into CANDIDATE_DELAYED. void SetTimePoint(std::chrono::microseconds now, - std::vector> *expired) { + std::vector> *expired) { if (expired) { expired->clear(); } @@ -631,16 +638,16 @@ // 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(); + auto it = m_index.template get().begin(); if (it->GetState() == State::CANDIDATE_DELAYED && it->m_time <= now) { - PromoteCandidateReady(m_index.project(it)); + PromoteCandidateReady(m_index.template project(it)); } else if (it->GetState() == State::REQUESTED && it->m_time <= now) { if (expired) { expired->emplace_back(it->m_peer, it->m_invid); } - MakeCompleted(m_index.project(it)); + MakeCompleted(m_index.template project(it)); } else { break; } @@ -652,9 +659,9 @@ // an unusual edge case, and unlikely to matter in production. // However, it makes it much easier to specify and test // InvRequestTracker::Impl's behaviour. - auto it = std::prev(m_index.get().end()); + auto it = std::prev(m_index.template get().end()); if (it->IsSelectable() && it->m_time > now) { - ChangeAndReselect(m_index.project(it), + ChangeAndReselect(m_index.template project(it), State::CANDIDATE_DELAYED); } else { break; @@ -722,14 +729,15 @@ * Does nothing if one already exists for that (invid, peer) combination * (whether it's CANDIDATE, REQUESTED, or COMPLETED). */ - void ReceivedInv(NodeId peer, const TxId &invid, bool preferred, + void ReceivedInv(NodeId peer, const InvId &invid, bool preferred, std::chrono::microseconds reqtime) { // Bail out if we already have a CANDIDATE_BEST announcement for this // (invid, 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, invid})) { + if (m_index.template get().count( + ByPeerView{peer, true, invid})) { return; } @@ -737,8 +745,8 @@ // will fail due to the uniqueness of the ByPeer index if a // non-CANDIDATE_BEST announcement already exists with the same invid // and peer). Bail out in that case. - auto ret = m_index.get().emplace(invid, peer, preferred, - reqtime, m_current_sequence); + auto ret = m_index.template get().emplace( + invid, peer, preferred, reqtime, m_current_sequence); if (!ret.second) { return; } @@ -754,9 +762,9 @@ * It should be called when a peer goes offline. */ void DisconnectedPeer(NodeId peer) { - auto &index = m_index.get(); + auto &index = m_index.template get(); auto it = - index.lower_bound(ByPeerView{peer, false, TxId(uint256::ZERO)}); + index.lower_bound(ByPeerView{peer, false, InvId(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 @@ -786,7 +794,7 @@ // COMPLETED (which will mark other CANDIDATEs as CANDIDATE_BEST, or // delete all of an invid's announcements if no non-COMPLETED ones // are left). - if (MakeCompleted(m_index.project(it))) { + if (MakeCompleted(m_index.template project(it))) { // Then actually delete the announcement (unless it was already // deleted by MakeCompleted). Erase(it); @@ -802,10 +810,11 @@ * should ensure that new announcements for the same invid will not trigger * new ReceivedInv calls, at least in the short term after this call. */ - void ForgetInvId(const TxId &invid) { - auto it = m_index.get().lower_bound( + void ForgetInvId(const InvId &invid) { + auto it = m_index.template get().lower_bound( ByInvIdView{invid, State::CANDIDATE_DELAYED, 0}); - while (it != m_index.get().end() && it->m_invid == invid) { + while (it != m_index.template get().end() && + it->m_invid == invid) { it = Erase(it); } } @@ -832,17 +841,17 @@ * peer, and end up being requested from them, the requests will happen * in announcement order. */ - std::vector + std::vector GetRequestable(NodeId peer, std::chrono::microseconds now, - std::vector> *expired) { + std::vector> *expired) { // Move time. SetTimePoint(now, expired); // 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() && + auto it_peer = m_index.template get().lower_bound( + ByPeerView{peer, true, InvId(uint256::ZERO)}); + while (it_peer != m_index.template get().end() && it_peer->m_peer == peer && it_peer->GetState() == State::CANDIDATE_BEST) { selected.emplace_back(&*it_peer); @@ -856,7 +865,7 @@ }); // Convert to InvId and return. - std::vector ret; + std::vector ret; ret.reserve(selected.size()); std::transform(selected.begin(), selected.end(), std::back_inserter(ret), @@ -875,10 +884,11 @@ * never advise doing so). In this case it is converted to COMPLETED, as * we're no longer waiting for a response to it. */ - void RequestedData(NodeId peer, const TxId &invid, + void RequestedData(NodeId peer, const InvId &invid, std::chrono::microseconds expiry) { - auto it = m_index.get().find(ByPeerView{peer, true, invid}); - if (it == m_index.get().end()) { + auto it = + m_index.template get().find(ByPeerView{peer, true, invid}); + if (it == m_index.template get().end()) { // There is no CANDIDATE_BEST announcement, look for a _READY or // _DELAYED instead. If the caller only ever invokes RequestedData // with the values returned by GetRequestable, and no other @@ -887,8 +897,9 @@ // GetRequestable always correspond to CANDIDATE_BEST // announcements). - it = m_index.get().find(ByPeerView{peer, false, invid}); - if (it == m_index.get().end() || + it = m_index.template get().find( + ByPeerView{peer, false, invid}); + if (it == m_index.template get().end() || (it->GetState() != State::CANDIDATE_DELAYED && it->GetState() != State::CANDIDATE_READY)) { // There is no CANDIDATE announcement tracked for this peer, so @@ -903,9 +914,9 @@ // invid. 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( + auto it_old = m_index.template get().lower_bound( ByInvIdView{invid, State::CANDIDATE_BEST, 0}); - if (it_old != m_index.get().end() && + if (it_old != m_index.template get().end() && it_old->m_invid == invid) { if (it_old->GetState() == State::CANDIDATE_BEST) { // The data structure's invariants require that there can be @@ -947,15 +958,17 @@ * a peer. When the inventory is not needed entirely anymore, ForgetInvId * should be called instead of, or in addition to, this call. */ - void ReceivedResponse(NodeId peer, const TxId &invid) { + void ReceivedResponse(NodeId peer, const InvId &invid) { // We need to search the ByPeer index for both (peer, false, invid) and // (peer, true, invid). - auto it = m_index.get().find(ByPeerView{peer, false, invid}); - if (it == m_index.get().end()) { - it = m_index.get().find(ByPeerView{peer, true, invid}); + auto it = + m_index.template get().find(ByPeerView{peer, false, invid}); + if (it == m_index.template get().end()) { + it = m_index.template get().find( + ByPeerView{peer, true, invid}); } - if (it != m_index.get().end()) { - MakeCompleted(m_index.project(it)); + if (it != m_index.template get().end()) { + MakeCompleted(m_index.template project(it)); } } @@ -999,7 +1012,7 @@ size_t Size() const { return m_index.size(); } /** Access to the internal priority computation (testing only) */ - uint64_t ComputePriority(const TxId &invid, NodeId peer, + uint64_t ComputePriority(const InvId &invid, NodeId peer, bool preferred) const { // Return Priority as a uint64_t as Priority is internal. return uint64_t{m_computer(invid, peer, preferred)}; diff --git a/src/net_processing.h b/src/net_processing.h --- a/src/net_processing.h +++ b/src/net_processing.h @@ -207,7 +207,7 @@ BanMan *const m_banman; ChainstateManager &m_chainman; CTxMemPool &m_mempool; - InvRequestTracker m_txrequest GUARDED_BY(::cs_main); + InvRequestTracker m_txrequest GUARDED_BY(::cs_main); //! Next time to check for stale tip int64_t m_stale_tip_check_time; diff --git a/src/test/fuzz/txrequest.cpp b/src/test/fuzz/txrequest.cpp --- a/src/test/fuzz/txrequest.cpp +++ b/src/test/fuzz/txrequest.cpp @@ -70,7 +70,7 @@ */ class Tester { //! InvRequestTracker object being tested. - InvRequestTracker m_tracker; + InvRequestTracker m_tracker; //! States for txid/peer combinations in the naive data structure. enum class State { diff --git a/src/test/txrequest_tests.cpp b/src/test/txrequest_tests.cpp --- a/src/test/txrequest_tests.cpp +++ b/src/test/txrequest_tests.cpp @@ -32,7 +32,7 @@ */ struct Runner { /** The InvRequestTracker being tested. */ - InvRequestTracker txrequest; + InvRequestTracker txrequest; /** List of actions to be executed (in order of increasing timestamp). */ std::vector actions;