Changeset View
Changeset View
Standalone View
Standalone View
src/invrequest.h
Show First 20 Lines • Show All 45 Lines • ▼ Show 20 Lines | |||||
* Rationale: to avoid wasting bandwidth on multiple copies of the same | * Rationale: to avoid wasting bandwidth on multiple copies of the same | ||||
* inventory. | * inventory. | ||||
* | * | ||||
* - The same inventory is never requested twice from the same peer, unless | * - The same inventory is never requested twice from the same peer, unless | ||||
* the announcement was forgotten in between, and re-announced. Announcements | * the announcement was forgotten in between, and re-announced. Announcements | ||||
* are forgotten only: | * are forgotten only: | ||||
* - If a peer goes offline, all its announcements are forgotten. | * - If a peer goes offline, all its announcements are forgotten. | ||||
* - If an inventory has been successfully received, or is otherwise no | * - If an inventory has been successfully received, or is otherwise no | ||||
* longer needed, the caller can call ForgetTxId, which removes all | * longer needed, the caller can call ForgetInvId, which removes all | ||||
* announcements across all peers with the specified invid. | * announcements across all peers with the specified invid. | ||||
* - If for a given invid only already-failed announcements remain, they are | * - If for a given invid only already-failed announcements remain, they are | ||||
* all forgotten. | * all forgotten. | ||||
* | * | ||||
* Rationale: giving a peer multiple chances to announce an inventory would | * Rationale: giving a peer multiple chances to announce an inventory would | ||||
* allow them to bias requests in their favor, worsening | * allow them to bias requests in their favor, worsening | ||||
* inventory censoring attacks. The flip side is that as long as | * inventory censoring attacks. The flip side is that as long as | ||||
* an attacker manages to prevent us from receiving an inventory, | * an attacker manages to prevent us from receiving an inventory, | ||||
▲ Show 20 Lines • Show All 51 Lines • ▼ Show 20 Lines | |||||
* announcements. | * announcements. | ||||
* - CPU usage is generally logarithmic in the total number of tracked | * - CPU usage is generally logarithmic in the total number of tracked | ||||
* announcements, plus the number of announcements affected by an operation | * announcements, plus the number of announcements affected by an operation | ||||
* (amortized O(1) per announcement). | * (amortized O(1) per announcement). | ||||
*/ | */ | ||||
// Avoid littering this header file with implementation details. | // Avoid littering this header file with implementation details. | ||||
class Impl { | class Impl { | ||||
template <class InvId> friend class TxRequestTracker; | template <class InvId> friend class InvRequestTracker; | ||||
// The base class is responsible for building the child implementation. | // The base class is responsible for building the child implementation. | ||||
// This is a hack that allows for hiding the concrete implementation details | // This is a hack that allows for hiding the concrete implementation details | ||||
// from the callsite. | // from the callsite. | ||||
static std::unique_ptr<Impl> BuildImpl(bool deterministic); | static std::unique_ptr<Impl> BuildImpl(bool deterministic); | ||||
protected: | protected: | ||||
using clearExpiredFun = const std::function<void()> &; | using clearExpiredFun = const std::function<void()> &; | ||||
using emplaceExpiredFun = | using emplaceExpiredFun = | ||||
const std::function<void(const NodeId &, const uint256 &)> &; | const std::function<void(const NodeId &, const uint256 &)> &; | ||||
virtual void ReceivedInv(NodeId peer, const uint256 &invid, bool preferred, | virtual void ReceivedInv(NodeId peer, const uint256 &invid, bool preferred, | ||||
std::chrono::microseconds reqtime) = 0; | std::chrono::microseconds reqtime) = 0; | ||||
virtual void DisconnectedPeer(NodeId peer) = 0; | virtual void DisconnectedPeer(NodeId peer) = 0; | ||||
virtual void ForgetTxId(const uint256 &invid) = 0; | virtual void ForgetInvId(const uint256 &invid) = 0; | ||||
virtual std::vector<uint256> | virtual std::vector<uint256> | ||||
GetRequestable(NodeId peer, std::chrono::microseconds now, | GetRequestable(NodeId peer, std::chrono::microseconds now, | ||||
clearExpiredFun clearExpired, | clearExpiredFun clearExpired, | ||||
emplaceExpiredFun emplaceExpired) = 0; | emplaceExpiredFun emplaceExpired) = 0; | ||||
virtual void RequestedTx(NodeId peer, const uint256 &invid, | virtual void RequestedData(NodeId peer, const uint256 &invid, | ||||
std::chrono::microseconds expiry) = 0; | std::chrono::microseconds expiry) = 0; | ||||
virtual void ReceivedResponse(NodeId peer, const uint256 &invid) = 0; | virtual void ReceivedResponse(NodeId peer, const uint256 &invid) = 0; | ||||
virtual size_t CountInFlight(NodeId peer) const = 0; | virtual size_t CountInFlight(NodeId peer) const = 0; | ||||
virtual size_t CountCandidates(NodeId peer) const = 0; | virtual size_t CountCandidates(NodeId peer) const = 0; | ||||
virtual size_t Count(NodeId peer) const = 0; | virtual size_t Count(NodeId peer) const = 0; | ||||
virtual size_t Size() const = 0; | virtual size_t Size() const = 0; | ||||
virtual uint64_t ComputePriority(const uint256 &invid, NodeId peer, | virtual uint64_t ComputePriority(const uint256 &invid, NodeId peer, | ||||
bool preferred) const = 0; | bool preferred) const = 0; | ||||
virtual void SanityCheck() const = 0; | virtual void SanityCheck() const = 0; | ||||
virtual void | virtual void | ||||
PostGetRequestableSanityCheck(std::chrono::microseconds now) const = 0; | PostGetRequestableSanityCheck(std::chrono::microseconds now) const = 0; | ||||
public: | public: | ||||
virtual ~Impl() = default; | virtual ~Impl() = default; | ||||
}; | }; | ||||
template <class InvId> class TxRequestTracker { | template <class InvId> class InvRequestTracker { | ||||
/* | /* | ||||
* Only uint256-based InvId types are supported for now. | * Only uint256-based InvId types are supported for now. | ||||
* FIXME: use a template constraint when C++20 is available. | * FIXME: use a template constraint when C++20 is available. | ||||
*/ | */ | ||||
static_assert(std::is_base_of<uint256, InvId>::value, | static_assert(std::is_base_of<uint256, InvId>::value, | ||||
"InvRequestTracker inv id type should be uint256 or derived"); | "InvRequestTracker inv id type should be uint256 or derived"); | ||||
const std::unique_ptr<Impl> m_impl; | const std::unique_ptr<Impl> m_impl; | ||||
public: | public: | ||||
//! Construct a TxRequestTracker. | //! Construct a InvRequestTracker. | ||||
explicit TxRequestTracker(bool deterministic = false); | explicit InvRequestTracker(bool deterministic = false); | ||||
~TxRequestTracker(); | ~InvRequestTracker(); | ||||
// Conceptually, the data structure consists of a collection of | // Conceptually, the data structure consists of a collection of | ||||
// "announcements", one for each peer/invid combination: | // "announcements", one for each peer/invid combination: | ||||
// | // | ||||
// - CANDIDATE announcements represent inventories that were announced by a | // - CANDIDATE announcements represent inventories that were announced by a | ||||
// peer, and that become available for download after their reqtime has | // peer, and that become available for download after their reqtime has | ||||
// passed. | // passed. | ||||
// | // | ||||
Show All 28 Lines | public: | ||||
/** | /** | ||||
* Deletes all announcements for a given invid. | * Deletes all announcements for a given invid. | ||||
* | * | ||||
* This should be called when an inventory is no longer needed. The caller | * This should be called when an inventory is no longer needed. The caller | ||||
* should ensure that new announcements for the same invid will not trigger | * should ensure that new announcements for the same invid will not trigger | ||||
* new ReceivedInv calls, at least in the short term after this call. | * new ReceivedInv calls, at least in the short term after this call. | ||||
*/ | */ | ||||
void ForgetTxId(const InvId &invid); | void ForgetInvId(const InvId &invid); | ||||
/** | /** | ||||
* Find the invids to request now from peer. | * Find the invids to request now from peer. | ||||
* | * | ||||
* It does the following: | * It does the following: | ||||
* - Convert all REQUESTED announcements (for all invids/peers) with | * - Convert all REQUESTED announcements (for all invids/peers) with | ||||
* (expiry <= now) to COMPLETED ones. These are returned in expired, if | * (expiry <= now) to COMPLETED ones. These are returned in expired, if | ||||
* non-nullptr. | * non-nullptr. | ||||
Show All 22 Lines | public: | ||||
* If no CANDIDATE announcement for the provided peer and invid exists, this | * If no CANDIDATE announcement for the provided peer and invid exists, this | ||||
* call has no effect. Otherwise: | * call has no effect. Otherwise: | ||||
* - That announcement is converted to REQUESTED. | * - That announcement is converted to REQUESTED. | ||||
* - If any other REQUESTED announcement for the same invid already | * - If any other REQUESTED announcement for the same invid already | ||||
* existed, it means an unexpected request was made (GetRequestable will | * existed, it means an unexpected request was made (GetRequestable will | ||||
* never advise doing so). In this case it is converted to COMPLETED, as | * never advise doing so). In this case it is converted to COMPLETED, as | ||||
* we're no longer waiting for a response to it. | * we're no longer waiting for a response to it. | ||||
*/ | */ | ||||
void RequestedTx(NodeId peer, const InvId &invid, | void RequestedData(NodeId peer, const InvId &invid, | ||||
std::chrono::microseconds expiry); | std::chrono::microseconds expiry); | ||||
/** | /** | ||||
* Converts a CANDIDATE or REQUESTED announcement to a COMPLETED one. If no | * Converts a CANDIDATE or REQUESTED announcement to a COMPLETED one. If no | ||||
* such announcement exists for the provided peer and invid, nothing | * such announcement exists for the provided peer and invid, nothing | ||||
* happens. | * happens. | ||||
* | * | ||||
* It should be called whenever an inventory or NOTFOUND was received from | * It should be called whenever an inventory or NOTFOUND was received from | ||||
* a peer. When the inventory is not needed entirely anymore, ForgetTxId | * a peer. When the inventory is not needed entirely anymore, ForgetInvId | ||||
* should be called instead of, or in addition to, this call. | * should be called instead of, or in addition to, this call. | ||||
*/ | */ | ||||
void ReceivedResponse(NodeId peer, const InvId &invid); | void ReceivedResponse(NodeId peer, const InvId &invid); | ||||
// The operations below inspect the data structure. | // The operations below inspect the data structure. | ||||
/** Count how many REQUESTED announcements a peer has. */ | /** Count how many REQUESTED announcements a peer has. */ | ||||
size_t CountInFlight(NodeId peer) const; | size_t CountInFlight(NodeId peer) const; | ||||
Show All 25 Lines | public: | ||||
* | * | ||||
* This can only be called immediately after GetRequestable, with the same | * This can only be called immediately after GetRequestable, with the same | ||||
* 'now' parameter. | * 'now' parameter. | ||||
*/ | */ | ||||
void PostGetRequestableSanityCheck(std::chrono::microseconds now) const; | void PostGetRequestableSanityCheck(std::chrono::microseconds now) const; | ||||
}; | }; | ||||
template <class InvId> | template <class InvId> | ||||
TxRequestTracker<InvId>::TxRequestTracker(bool deterministic) | InvRequestTracker<InvId>::InvRequestTracker(bool deterministic) | ||||
: m_impl{Impl::BuildImpl(deterministic)} {} | : m_impl{Impl::BuildImpl(deterministic)} {} | ||||
template <class InvId> TxRequestTracker<InvId>::~TxRequestTracker() = default; | template <class InvId> InvRequestTracker<InvId>::~InvRequestTracker() = default; | ||||
template <class InvId> | template <class InvId> | ||||
void TxRequestTracker<InvId>::ForgetTxId(const InvId &invid) { | void InvRequestTracker<InvId>::ForgetInvId(const InvId &invid) { | ||||
m_impl->ForgetTxId(invid); | m_impl->ForgetInvId(invid); | ||||
} | } | ||||
template <class InvId> | template <class InvId> | ||||
void TxRequestTracker<InvId>::DisconnectedPeer(NodeId peer) { | void InvRequestTracker<InvId>::DisconnectedPeer(NodeId peer) { | ||||
m_impl->DisconnectedPeer(peer); | m_impl->DisconnectedPeer(peer); | ||||
} | } | ||||
template <class InvId> | template <class InvId> | ||||
size_t TxRequestTracker<InvId>::CountInFlight(NodeId peer) const { | size_t InvRequestTracker<InvId>::CountInFlight(NodeId peer) const { | ||||
return m_impl->CountInFlight(peer); | return m_impl->CountInFlight(peer); | ||||
} | } | ||||
template <class InvId> | template <class InvId> | ||||
size_t TxRequestTracker<InvId>::CountCandidates(NodeId peer) const { | size_t InvRequestTracker<InvId>::CountCandidates(NodeId peer) const { | ||||
return m_impl->CountCandidates(peer); | return m_impl->CountCandidates(peer); | ||||
} | } | ||||
template <class InvId> | template <class InvId> | ||||
size_t TxRequestTracker<InvId>::Count(NodeId peer) const { | size_t InvRequestTracker<InvId>::Count(NodeId peer) const { | ||||
return m_impl->Count(peer); | return m_impl->Count(peer); | ||||
} | } | ||||
template <class InvId> size_t TxRequestTracker<InvId>::Size() const { | template <class InvId> size_t InvRequestTracker<InvId>::Size() const { | ||||
return m_impl->Size(); | return m_impl->Size(); | ||||
} | } | ||||
template <class InvId> void TxRequestTracker<InvId>::SanityCheck() const { | template <class InvId> void InvRequestTracker<InvId>::SanityCheck() const { | ||||
m_impl->SanityCheck(); | m_impl->SanityCheck(); | ||||
} | } | ||||
template <class InvId> | template <class InvId> | ||||
void TxRequestTracker<InvId>::PostGetRequestableSanityCheck( | void InvRequestTracker<InvId>::PostGetRequestableSanityCheck( | ||||
std::chrono::microseconds now) const { | std::chrono::microseconds now) const { | ||||
m_impl->PostGetRequestableSanityCheck(now); | m_impl->PostGetRequestableSanityCheck(now); | ||||
} | } | ||||
template <class InvId> | template <class InvId> | ||||
void TxRequestTracker<InvId>::ReceivedInv(NodeId peer, const InvId &invid, | void InvRequestTracker<InvId>::ReceivedInv(NodeId peer, const InvId &invid, | ||||
bool preferred, | bool preferred, | ||||
std::chrono::microseconds reqtime) { | std::chrono::microseconds reqtime) { | ||||
m_impl->ReceivedInv(peer, invid, preferred, reqtime); | m_impl->ReceivedInv(peer, invid, preferred, reqtime); | ||||
} | } | ||||
template <class InvId> | template <class InvId> | ||||
void TxRequestTracker<InvId>::RequestedTx(NodeId peer, const InvId &invid, | void InvRequestTracker<InvId>::RequestedData(NodeId peer, const InvId &invid, | ||||
std::chrono::microseconds expiry) { | std::chrono::microseconds expiry) { | ||||
m_impl->RequestedTx(peer, invid, expiry); | m_impl->RequestedData(peer, invid, expiry); | ||||
} | } | ||||
template <class InvId> | template <class InvId> | ||||
void TxRequestTracker<InvId>::ReceivedResponse(NodeId peer, | void InvRequestTracker<InvId>::ReceivedResponse(NodeId peer, | ||||
const InvId &invid) { | const InvId &invid) { | ||||
m_impl->ReceivedResponse(peer, invid); | m_impl->ReceivedResponse(peer, invid); | ||||
} | } | ||||
template <class InvId> | template <class InvId> | ||||
std::vector<InvId> TxRequestTracker<InvId>::GetRequestable( | std::vector<InvId> InvRequestTracker<InvId>::GetRequestable( | ||||
NodeId peer, std::chrono::microseconds now, | NodeId peer, std::chrono::microseconds now, | ||||
std::vector<std::pair<NodeId, InvId>> *expired) { | std::vector<std::pair<NodeId, InvId>> *expired) { | ||||
Impl::clearExpiredFun clearExpired = [expired]() { | Impl::clearExpiredFun clearExpired = [expired]() { | ||||
if (expired) { | if (expired) { | ||||
expired->clear(); | expired->clear(); | ||||
} | } | ||||
}; | }; | ||||
Impl::emplaceExpiredFun emplaceExpired = [expired](const NodeId &nodeid, | Impl::emplaceExpiredFun emplaceExpired = [expired](const NodeId &nodeid, | ||||
const uint256 &invid) { | const uint256 &invid) { | ||||
if (expired) { | if (expired) { | ||||
expired->emplace_back(nodeid, InvId(invid)); | expired->emplace_back(nodeid, InvId(invid)); | ||||
} | } | ||||
}; | }; | ||||
std::vector<uint256> hashes = | std::vector<uint256> hashes = | ||||
m_impl->GetRequestable(peer, now, clearExpired, emplaceExpired); | m_impl->GetRequestable(peer, now, clearExpired, emplaceExpired); | ||||
return std::vector<InvId>(hashes.begin(), hashes.end()); | return std::vector<InvId>(hashes.begin(), hashes.end()); | ||||
} | } | ||||
template <class InvId> | template <class InvId> | ||||
uint64_t TxRequestTracker<InvId>::ComputePriority(const InvId &invid, | uint64_t InvRequestTracker<InvId>::ComputePriority(const InvId &invid, | ||||
NodeId peer, | NodeId peer, | ||||
bool preferred) const { | bool preferred) const { | ||||
return m_impl->ComputePriority(invid, peer, preferred); | return m_impl->ComputePriority(invid, peer, preferred); | ||||
} | } | ||||
#endif // BITCOIN_INVREQUEST_H | #endif // BITCOIN_INVREQUEST_H |