13 #include <boost/multi_index_container.hpp>
14 #include <boost/multi_index/ordered_index.hpp>
17 #include <unordered_map>
38 enum class State : uint8_t {
54 using SequenceNumber = uint64_t;
61 std::chrono::microseconds m_time;
65 const SequenceNumber m_sequence : 59;
67 const bool m_preferred : 1;
69 const bool m_is_wtxid : 1;
77 State GetState()
const {
return static_cast<State
>(m_state); }
80 void SetState(State state) { m_state =
static_cast<uint8_t
>(state); }
83 bool IsSelected()
const
85 return GetState() == State::CANDIDATE_BEST || GetState() == State::REQUESTED;
89 bool IsWaiting()
const
91 return GetState() == State::REQUESTED || GetState() == State::CANDIDATE_DELAYED;
95 bool IsSelectable()
const
97 return GetState() == State::CANDIDATE_READY || GetState() == State::CANDIDATE_BEST;
101 Announcement(
const GenTxid& gtxid,
NodeId peer,
bool preferred, std::chrono::microseconds reqtime,
102 SequenceNumber sequence) :
103 m_txhash(gtxid.GetHash()), m_time(reqtime), m_peer(peer), m_sequence(sequence), m_preferred(preferred),
104 m_is_wtxid(gtxid.IsWtxid()), m_state(static_cast<uint8_t>(State::CANDIDATE_DELAYED)) {}
108 using Priority = uint64_t;
114 class PriorityComputer {
115 const uint64_t m_k0, m_k1;
117 explicit PriorityComputer(
bool deterministic) :
118 m_k0{deterministic ? 0 :
GetRand(0xFFFFFFFFFFFFFFFF)},
119 m_k1{deterministic ? 0 :
GetRand(0xFFFFFFFFFFFFFFFF)} {}
121 Priority operator()(
const uint256& txhash,
NodeId peer,
bool preferred)
const
124 return low_bits | uint64_t{preferred} << 63;
127 Priority operator()(
const Announcement& ann)
const
129 return operator()(ann.m_txhash, ann.m_peer, ann.m_preferred);
147 using ByPeerView = std::tuple<NodeId, bool, const uint256&>;
148 struct ByPeerViewExtractor
150 using result_type = ByPeerView;
151 result_type operator()(
const Announcement& ann)
const
153 return ByPeerView{ann.m_peer, ann.GetState() == State::CANDIDATE_BEST, ann.m_txhash};
168 using ByTxHashView = std::tuple<const uint256&, State, Priority>;
169 class ByTxHashViewExtractor {
170 const PriorityComputer& m_computer;
172 explicit ByTxHashViewExtractor(
const PriorityComputer& computer) : m_computer(computer) {}
173 using result_type = ByTxHashView;
174 result_type operator()(
const Announcement& ann)
const
176 const Priority prio = (ann.GetState() == State::CANDIDATE_READY) ? m_computer(ann) : 0;
177 return ByTxHashView{ann.m_txhash, ann.GetState(), prio};
181 enum class WaitState {
190 WaitState GetWaitState(
const Announcement& ann)
192 if (ann.IsWaiting())
return WaitState::FUTURE_EVENT;
193 if (ann.IsSelectable())
return WaitState::PAST_EVENT;
194 return WaitState::NO_EVENT;
207 using ByTimeView = std::pair<WaitState, std::chrono::microseconds>;
208 struct ByTimeViewExtractor
210 using result_type = ByTimeView;
211 result_type operator()(
const Announcement& ann)
const
213 return ByTimeView{GetWaitState(ann), ann.m_time};
218 using Index = boost::multi_index_container<
220 boost::multi_index::indexed_by<
221 boost::multi_index::ordered_unique<boost::multi_index::tag<ByPeer>, ByPeerViewExtractor>,
222 boost::multi_index::ordered_non_unique<boost::multi_index::tag<ByTxHash>, ByTxHashViewExtractor>,
223 boost::multi_index::ordered_non_unique<boost::multi_index::tag<ByTime>, ByTimeViewExtractor>
228 template<
typename Tag>
229 using Iter =
typename Index::index<Tag>::type::iterator;
234 size_t m_completed = 0;
235 size_t m_requested = 0;
242 size_t m_candidate_delayed = 0;
244 size_t m_candidate_ready = 0;
246 size_t m_candidate_best = 0;
248 size_t m_requested = 0;
250 Priority m_priority_candidate_best = std::numeric_limits<Priority>::max();
252 Priority m_priority_best_candidate_ready = std::numeric_limits<Priority>::min();
254 std::vector<NodeId> m_peers;
258 bool operator==(
const PeerInfo& a,
const PeerInfo& b)
260 return std::tie(a.m_total, a.m_completed, a.m_requested) ==
261 std::tie(b.m_total, b.m_completed, b.m_requested);
265 std::unordered_map<NodeId, PeerInfo> RecomputePeerInfo(
const Index& index)
267 std::unordered_map<NodeId, PeerInfo>
ret;
268 for (
const Announcement& ann : index) {
269 PeerInfo& info =
ret[ann.m_peer];
271 info.m_requested += (ann.GetState() == State::REQUESTED);
272 info.m_completed += (ann.GetState() == State::COMPLETED);
278 std::map<uint256, TxHashInfo> ComputeTxHashInfo(
const Index& index,
const PriorityComputer& computer)
280 std::map<uint256, TxHashInfo>
ret;
281 for (
const Announcement& ann : index) {
282 TxHashInfo& info =
ret[ann.m_txhash];
284 info.m_candidate_delayed += (ann.GetState() == State::CANDIDATE_DELAYED);
285 info.m_candidate_ready += (ann.GetState() == State::CANDIDATE_READY);
286 info.m_candidate_best += (ann.GetState() == State::CANDIDATE_BEST);
287 info.m_requested += (ann.GetState() == State::REQUESTED);
289 if (ann.GetState() == State::CANDIDATE_BEST) {
290 info.m_priority_candidate_best = computer(ann);
292 if (ann.GetState() == State::CANDIDATE_READY) {
293 info.m_priority_best_candidate_ready = std::max(info.m_priority_best_candidate_ready, computer(ann));
296 info.m_peers.push_back(ann.m_peer);
332 TxHashInfo& info = item.second;
335 assert(info.m_candidate_delayed + info.m_candidate_ready + info.m_candidate_best + info.m_requested > 0);
338 assert(info.m_candidate_best + info.m_requested <= 1);
342 if (info.m_candidate_ready > 0) {
343 assert(info.m_candidate_best + info.m_requested == 1);
348 if (info.m_candidate_ready && info.m_candidate_best) {
349 assert(info.m_priority_candidate_best >= info.m_priority_best_candidate_ready);
353 std::sort(info.m_peers.begin(), info.m_peers.end());
354 assert(std::adjacent_find(info.m_peers.begin(), info.m_peers.end()) == info.m_peers.end());
360 for (
const Announcement& ann :
m_index) {
361 if (ann.IsWaiting()) {
365 }
else if (ann.IsSelectable()) {
368 assert(ann.m_time <= now);
375 template<
typename Tag>
379 peerit->second.m_completed -= it->GetState() == State::COMPLETED;
380 peerit->second.m_requested -= it->GetState() == State::REQUESTED;
381 if (--peerit->second.m_total == 0)
m_peerinfo.erase(peerit);
382 return m_index.get<Tag>().erase(it);
386 template<
typename Tag,
typename Modifier>
387 void Modify(Iter<Tag> it, Modifier modifier)
390 peerit->second.m_completed -= it->GetState() == State::COMPLETED;
391 peerit->second.m_requested -= it->GetState() == State::REQUESTED;
392 m_index.get<Tag>().modify(it, std::move(modifier));
393 peerit->second.m_completed += it->GetState() == State::COMPLETED;
394 peerit->second.m_requested += it->GetState() == State::REQUESTED;
403 assert(it->GetState() == State::CANDIDATE_DELAYED);
405 Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_READY); });
410 auto it_next = std::next(it);
411 if (it_next ==
m_index.get<ByTxHash>().end() || it_next->m_txhash != it->m_txhash ||
412 it_next->GetState() == State::COMPLETED) {
415 Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); });
416 }
else if (it_next->GetState() == State::CANDIDATE_BEST) {
419 if (priority_new > priority_old) {
421 Modify<ByTxHash>(it_next, [](Announcement& ann){ ann.SetState(State::CANDIDATE_READY); });
422 Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); });
431 assert(new_state == State::COMPLETED || new_state == State::CANDIDATE_DELAYED);
433 if (it->IsSelected() && it !=
m_index.get<ByTxHash>().begin()) {
434 auto it_prev = std::prev(it);
437 if (it_prev->m_txhash == it->m_txhash && it_prev->GetState() == State::CANDIDATE_READY) {
439 Modify<ByTxHash>(it_prev, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); });
442 Modify<ByTxHash>(it, [new_state](Announcement& ann){ ann.SetState(new_state); });
449 assert(it->GetState() != State::COMPLETED);
453 if (it !=
m_index.get<ByTxHash>().begin() && std::prev(it)->m_txhash == it->m_txhash)
return false;
456 if (std::next(it) !=
m_index.get<ByTxHash>().end() && std::next(it)->m_txhash == it->m_txhash &&
457 std::next(it)->GetState() != State::COMPLETED)
return false;
470 if (it->GetState() == State::COMPLETED)
return true;
476 it = Erase<ByTxHash>(it);
477 }
while (it !=
m_index.get<ByTxHash>().end() && it->m_txhash == txhash);
492 void SetTimePoint(std::chrono::microseconds now, std::vector<std::pair<NodeId, GenTxid>>* expired)
494 if (expired) expired->clear();
499 auto it =
m_index.get<ByTime>().begin();
500 if (it->GetState() == State::CANDIDATE_DELAYED && it->m_time <= now) {
502 }
else if (it->GetState() == State::REQUESTED && it->m_time <= now) {
503 if (expired) expired->emplace_back(it->m_peer,
ToGenTxid(*it));
514 auto it = std::prev(
m_index.get<ByTime>().end());
515 if (it->IsSelectable() && it->m_time > now) {
524 explicit Impl(
bool deterministic) :
528 boost::make_tuple(ByPeerViewExtractor(),
std::less<ByPeerView>()),
529 boost::make_tuple(ByTxHashViewExtractor(
m_computer),
std::less<ByTxHashView>()),
530 boost::make_tuple(ByTimeViewExtractor(),
std::less<ByTimeView>())
539 auto& index =
m_index.get<ByPeer>();
540 auto it = index.lower_bound(ByPeerView{peer,
false,
uint256::ZERO});
541 while (it != index.end() && it->m_peer == peer) {
555 auto it_next = (std::next(it) == index.end() || std::next(it)->m_peer != peer) ? index.end() :
570 auto it =
m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_DELAYED, 0});
571 while (it !=
m_index.get<ByTxHash>().end() && it->m_txhash == txhash) {
572 it = Erase<ByTxHash>(it);
577 std::chrono::microseconds reqtime)
582 if (
m_index.get<ByPeer>().count(ByPeerView{peer, true, gtxid.GetHash()}))
return;
588 if (!
ret.second)
return;
597 std::vector<std::pair<NodeId, GenTxid>>* expired)
603 std::vector<const Announcement*> selected;
605 while (it_peer !=
m_index.get<ByPeer>().end() && it_peer->m_peer == peer &&
606 it_peer->GetState() == State::CANDIDATE_BEST) {
607 selected.emplace_back(&*it_peer);
612 std::sort(selected.begin(), selected.end(), [](
const Announcement* a,
const Announcement* b) {
613 return a->m_sequence < b->m_sequence;
617 std::vector<GenTxid>
ret;
618 ret.reserve(selected.size());
619 std::transform(selected.begin(), selected.end(), std::back_inserter(
ret), [](
const Announcement* ann) {
620 return ToGenTxid(*ann);
627 auto it =
m_index.get<ByPeer>().find(ByPeerView{peer,
true, txhash});
628 if (it ==
m_index.get<ByPeer>().end()) {
634 it =
m_index.get<ByPeer>().find(ByPeerView{peer,
false, txhash});
635 if (it ==
m_index.get<ByPeer>().end() || (it->GetState() != State::CANDIDATE_DELAYED &&
636 it->GetState() != State::CANDIDATE_READY)) {
646 auto it_old =
m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_BEST, 0});
647 if (it_old !=
m_index.get<ByTxHash>().end() && it_old->m_txhash == txhash) {
648 if (it_old->GetState() == State::CANDIDATE_BEST) {
655 Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::CANDIDATE_READY); });
656 }
else if (it_old->GetState() == State::REQUESTED) {
659 Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::COMPLETED); });
664 Modify<ByPeer>(it, [expiry](Announcement& ann) {
665 ann.SetState(State::REQUESTED);
673 auto it =
m_index.get<ByPeer>().find(ByPeerView{peer,
false, txhash});
674 if (it ==
m_index.get<ByPeer>().end()) {
675 it =
m_index.get<ByPeer>().find(ByPeerView{peer,
true, txhash});
683 if (it !=
m_peerinfo.end())
return it->second.m_requested;
690 if (it !=
m_peerinfo.end())
return it->second.m_total - it->second.m_requested - it->second.m_completed;
697 if (it !=
m_peerinfo.end())
return it->second.m_total;
707 return uint64_t{
m_computer(txhash, peer, preferred)};
727 m_impl->PostGetRequestableSanityCheck(now);
731 std::chrono::microseconds reqtime)
733 m_impl->ReceivedInv(peer, gtxid, preferred, reqtime);
738 m_impl->RequestedTx(peer, txhash, expiry);
743 m_impl->ReceivedResponse(peer, txhash);
747 std::vector<std::pair<NodeId, GenTxid>>* expired)
749 return m_impl->GetRequestable(peer, now, expired);
754 return m_impl->ComputePriority(txhash, peer, preferred);
uint64_t Finalize() const
Compute the 64-bit SipHash-2-4 of the data written so far.
CSipHasher & Write(uint64_t data)
Hash a 64-bit integer worth of data It is treated as if this was the little-endian interpretation of ...
A generic txid reference (txid or wtxid).
static GenTxid Wtxid(const uint256 &hash)
Actual implementation for TxRequestTracker's data structure.
const PriorityComputer m_computer
This tracker's priority computer.
Iter< Tag > Erase(Iter< Tag > it)
Wrapper around Index::...::erase that keeps m_peerinfo up to date.
void PromoteCandidateReady(Iter< ByTxHash > it)
Convert a CANDIDATE_DELAYED announcement into a CANDIDATE_READY.
SequenceNumber m_current_sequence
The current sequence number.
void ReceivedResponse(NodeId peer, const uint256 &txhash)
size_t CountInFlight(NodeId peer) const
std::vector< GenTxid > GetRequestable(NodeId peer, std::chrono::microseconds now, std::vector< std::pair< NodeId, GenTxid >> *expired)
Find the GenTxids to request now from peer.
size_t Size() const
Count how many announcements are being tracked in total across all peers and transactions.
void ReceivedInv(NodeId peer, const GenTxid >xid, bool preferred, std::chrono::microseconds reqtime)
Impl(const Impl &)=delete
bool MakeCompleted(Iter< ByTxHash > it)
Convert any announcement to a COMPLETED one.
void PostGetRequestableSanityCheck(std::chrono::microseconds now) const
Index m_index
This tracker's main data structure. See SanityCheck() for the invariants that apply to it.
bool IsOnlyNonCompleted(Iter< ByTxHash > it)
Check if 'it' is the only announcement for a given txhash that isn't COMPLETED.
Impl & operator=(const Impl &)=delete
void ForgetTxHash(const uint256 &txhash)
uint64_t ComputePriority(const uint256 &txhash, NodeId peer, bool preferred) const
std::unordered_map< NodeId, PeerInfo > m_peerinfo
Map with this tracker's per-peer statistics.
void RequestedTx(NodeId peer, const uint256 &txhash, std::chrono::microseconds expiry)
void ChangeAndReselect(Iter< ByTxHash > it, State new_state)
Change the state of an announcement to something non-IsSelected().
size_t CountCandidates(NodeId peer) const
void SetTimePoint(std::chrono::microseconds now, std::vector< std::pair< NodeId, GenTxid >> *expired)
Make the data structure consistent with a given point in time:
size_t Count(NodeId peer) const
void Modify(Iter< Tag > it, Modifier modifier)
Wrapper around Index::...::modify that keeps m_peerinfo up to date.
void DisconnectedPeer(NodeId peer)
Data structure to keep track of, and schedule, transaction downloads from peers.
void ReceivedInv(NodeId peer, const GenTxid >xid, bool preferred, std::chrono::microseconds reqtime)
Adds a new CANDIDATE announcement.
void SanityCheck() const
Run internal consistency check (testing only).
size_t CountInFlight(NodeId peer) const
Count how many REQUESTED announcements a peer has.
size_t CountCandidates(NodeId peer) const
Count how many CANDIDATE announcements a peer has.
TxRequestTracker(bool deterministic=false)
Construct a TxRequestTracker.
const std::unique_ptr< Impl > m_impl
void DisconnectedPeer(NodeId peer)
Deletes all announcements for a given peer.
void ReceivedResponse(NodeId peer, const uint256 &txhash)
Converts a CANDIDATE or REQUESTED announcement to a COMPLETED one.
uint64_t ComputePriority(const uint256 &txhash, NodeId peer, bool preferred) const
Access to the internal priority computation (testing only)
void PostGetRequestableSanityCheck(std::chrono::microseconds now) const
Run a time-dependent internal consistency check (testing only).
void RequestedTx(NodeId peer, const uint256 &txhash, std::chrono::microseconds expiry)
Marks a transaction as requested, with a specified expiry.
size_t Count(NodeId peer) const
Count how many announcements a peer has (REQUESTED, CANDIDATE, and COMPLETED combined).
size_t Size() const
Count how many announcements are being tracked in total across all peers and transaction hashes.
std::vector< GenTxid > GetRequestable(NodeId peer, std::chrono::microseconds now, std::vector< std::pair< NodeId, GenTxid >> *expired=nullptr)
Find the txids to request now from peer.
void ForgetTxHash(const uint256 &txhash)
Deletes all announcements for a given txhash (both txid and wtxid ones).
static constexpr unsigned int size()
constexpr unsigned char * begin()
static const uint256 ZERO
bool operator==(const CNetAddr &a, const CNetAddr &b)
GenTxid ToGenTxid(const CInv &inv)
Convert a TX/WITNESS_TX/WTX CInv to a GenTxid.
T GetRand(T nMax=std::numeric_limits< T >::max()) noexcept
Generate a uniform random integer of type T in the range [0..nMax) nMax defaults to std::numeric_limi...