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);
303 return {ann.m_is_wtxid, ann.m_txhash};
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);
386 template<
typename Tag,
typename 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();
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>();
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});
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});
675 it =
m_index.get<ByPeer>().find(ByPeerView{peer,
true, txhash});
690 if (
it !=
m_peerinfo.end())
return it->second.m_total -
it->second.m_requested -
it->second.m_completed;
707 return uint64_t{
m_computer(txhash, peer, preferred)};
713 m_impl{std::make_unique<TxRequestTracker::Impl>(deterministic)} {}
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);