Bitcoin Core  22.99.0
P2P Digital Currency
txrequest.cpp
Go to the documentation of this file.
1 // Copyright (c) 2020 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #include <txrequest.h>
6 
7 #include <crypto/siphash.h>
8 #include <net.h>
10 #include <random.h>
11 #include <uint256.h>
12 
13 #include <boost/multi_index_container.hpp>
14 #include <boost/multi_index/ordered_index.hpp>
15 
16 #include <chrono>
17 #include <unordered_map>
18 #include <utility>
19 
20 #include <assert.h>
21 
22 namespace {
23 
38 enum class State : uint8_t {
40  CANDIDATE_DELAYED,
42  CANDIDATE_READY,
46  CANDIDATE_BEST,
48  REQUESTED,
50  COMPLETED,
51 };
52 
54 using SequenceNumber = uint64_t;
55 
57 struct Announcement {
59  const uint256 m_txhash;
61  std::chrono::microseconds m_time;
63  const NodeId m_peer;
65  const SequenceNumber m_sequence : 59;
67  const bool m_preferred : 1;
69  const bool m_is_wtxid : 1;
70 
74  uint8_t m_state : 3;
75 
77  State GetState() const { return static_cast<State>(m_state); }
78 
80  void SetState(State state) { m_state = static_cast<uint8_t>(state); }
81 
83  bool IsSelected() const
84  {
85  return GetState() == State::CANDIDATE_BEST || GetState() == State::REQUESTED;
86  }
87 
89  bool IsWaiting() const
90  {
91  return GetState() == State::REQUESTED || GetState() == State::CANDIDATE_DELAYED;
92  }
93 
95  bool IsSelectable() const
96  {
97  return GetState() == State::CANDIDATE_READY || GetState() == State::CANDIDATE_BEST;
98  }
99 
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)) {}
105 };
106 
108 using Priority = uint64_t;
109 
114 class PriorityComputer {
115  const uint64_t m_k0, m_k1;
116 public:
117  explicit PriorityComputer(bool deterministic) :
118  m_k0{deterministic ? 0 : GetRand(0xFFFFFFFFFFFFFFFF)},
119  m_k1{deterministic ? 0 : GetRand(0xFFFFFFFFFFFFFFFF)} {}
120 
121  Priority operator()(const uint256& txhash, NodeId peer, bool preferred) const
122  {
123  uint64_t low_bits = CSipHasher(m_k0, m_k1).Write(txhash.begin(), txhash.size()).Write(peer).Finalize() >> 1;
124  return low_bits | uint64_t{preferred} << 63;
125  }
126 
127  Priority operator()(const Announcement& ann) const
128  {
129  return operator()(ann.m_txhash, ann.m_peer, ann.m_preferred);
130  }
131 };
132 
133 // Definitions for the 3 indexes used in the main data structure.
134 //
135 // Each index has a By* type to identify it, a By*View data type to represent the view of announcement it is sorted
136 // by, and an By*ViewExtractor type to convert an announcement into the By*View type.
137 // See https://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/reference/key_extraction.html#key_extractors
138 // for more information about the key extraction concept.
139 
140 // The ByPeer index is sorted by (peer, state == CANDIDATE_BEST, txhash)
141 //
142 // Uses:
143 // * Looking up existing announcements by peer/txhash, by checking both (peer, false, txhash) and
144 // (peer, true, txhash).
145 // * Finding all CANDIDATE_BEST announcements for a given peer in GetRequestable.
146 struct ByPeer {};
147 using ByPeerView = std::tuple<NodeId, bool, const uint256&>;
148 struct ByPeerViewExtractor
149 {
150  using result_type = ByPeerView;
151  result_type operator()(const Announcement& ann) const
152  {
153  return ByPeerView{ann.m_peer, ann.GetState() == State::CANDIDATE_BEST, ann.m_txhash};
154  }
155 };
156 
157 // The ByTxHash index is sorted by (txhash, state, priority).
158 //
159 // Note: priority == 0 whenever state != CANDIDATE_READY.
160 //
161 // Uses:
162 // * Deleting all announcements with a given txhash in ForgetTxHash.
163 // * Finding the best CANDIDATE_READY to convert to CANDIDATE_BEST, when no other CANDIDATE_READY or REQUESTED
164 // announcement exists for that txhash.
165 // * Determining when no more non-COMPLETED announcements for a given txhash exist, so the COMPLETED ones can be
166 // deleted.
167 struct ByTxHash {};
168 using ByTxHashView = std::tuple<const uint256&, State, Priority>;
169 class ByTxHashViewExtractor {
170  const PriorityComputer& m_computer;
171 public:
172  explicit ByTxHashViewExtractor(const PriorityComputer& computer) : m_computer(computer) {}
173  using result_type = ByTxHashView;
174  result_type operator()(const Announcement& ann) const
175  {
176  const Priority prio = (ann.GetState() == State::CANDIDATE_READY) ? m_computer(ann) : 0;
177  return ByTxHashView{ann.m_txhash, ann.GetState(), prio};
178  }
179 };
180 
181 enum class WaitState {
183  FUTURE_EVENT,
185  NO_EVENT,
187  PAST_EVENT,
188 };
189 
190 WaitState GetWaitState(const Announcement& ann)
191 {
192  if (ann.IsWaiting()) return WaitState::FUTURE_EVENT;
193  if (ann.IsSelectable()) return WaitState::PAST_EVENT;
194  return WaitState::NO_EVENT;
195 }
196 
197 // The ByTime index is sorted by (wait_state, time).
198 //
199 // All announcements with a timestamp in the future can be found by iterating the index forward from the beginning.
200 // All announcements with a timestamp in the past can be found by iterating the index backwards from the end.
201 //
202 // Uses:
203 // * Finding CANDIDATE_DELAYED announcements whose reqtime has passed, and REQUESTED announcements whose expiry has
204 // passed.
205 // * Finding CANDIDATE_READY/BEST announcements whose reqtime is in the future (when the clock time went backwards).
206 struct ByTime {};
207 using ByTimeView = std::pair<WaitState, std::chrono::microseconds>;
208 struct ByTimeViewExtractor
209 {
210  using result_type = ByTimeView;
211  result_type operator()(const Announcement& ann) const
212  {
213  return ByTimeView{GetWaitState(ann), ann.m_time};
214  }
215 };
216 
218 using Index = boost::multi_index_container<
219  Announcement,
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>
224  >
225 >;
226 
228 template<typename Tag>
229 using Iter = typename Index::index<Tag>::type::iterator;
230 
232 struct PeerInfo {
233  size_t m_total = 0;
234  size_t m_completed = 0;
235  size_t m_requested = 0;
236 };
237 
239 struct TxHashInfo
240 {
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;
255 };
256 
258 bool operator==(const PeerInfo& a, const PeerInfo& b)
259 {
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);
262 };
263 
265 std::unordered_map<NodeId, PeerInfo> RecomputePeerInfo(const Index& index)
266 {
267  std::unordered_map<NodeId, PeerInfo> ret;
268  for (const Announcement& ann : index) {
269  PeerInfo& info = ret[ann.m_peer];
270  ++info.m_total;
271  info.m_requested += (ann.GetState() == State::REQUESTED);
272  info.m_completed += (ann.GetState() == State::COMPLETED);
273  }
274  return ret;
275 }
276 
278 std::map<uint256, TxHashInfo> ComputeTxHashInfo(const Index& index, const PriorityComputer& computer)
279 {
280  std::map<uint256, TxHashInfo> ret;
281  for (const Announcement& ann : index) {
282  TxHashInfo& info = ret[ann.m_txhash];
283  // Classify how many announcements of each state we have for this 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);
288  // And track the priority of the best CANDIDATE_READY/CANDIDATE_BEST announcements.
289  if (ann.GetState() == State::CANDIDATE_BEST) {
290  info.m_priority_candidate_best = computer(ann);
291  }
292  if (ann.GetState() == State::CANDIDATE_READY) {
293  info.m_priority_best_candidate_ready = std::max(info.m_priority_best_candidate_ready, computer(ann));
294  }
295  // Also keep track of which peers this txhash has an announcement for (so we can detect duplicates).
296  info.m_peers.push_back(ann.m_peer);
297  }
298  return ret;
299 }
300 
301 GenTxid ToGenTxid(const Announcement& ann)
302 {
303  return {ann.m_is_wtxid, ann.m_txhash};
304 }
305 
306 } // namespace
307 
312  SequenceNumber m_current_sequence{0};
313 
315  const PriorityComputer m_computer;
316 
318  Index m_index;
319 
321  std::unordered_map<NodeId, PeerInfo> m_peerinfo;
322 
323 public:
324  void SanityCheck() const
325  {
326  // Recompute m_peerdata from m_index. This verifies the data in it as it should just be caching statistics
327  // on m_index. It also verifies the invariant that no PeerInfo announcements with m_total==0 exist.
328  assert(m_peerinfo == RecomputePeerInfo(m_index));
329 
330  // Calculate per-txhash statistics from m_index, and validate invariants.
331  for (auto& item : ComputeTxHashInfo(m_index, m_computer)) {
332  TxHashInfo& info = item.second;
333 
334  // Cannot have only COMPLETED peer (txhash should have been forgotten already)
335  assert(info.m_candidate_delayed + info.m_candidate_ready + info.m_candidate_best + info.m_requested > 0);
336 
337  // Can have at most 1 CANDIDATE_BEST/REQUESTED peer
338  assert(info.m_candidate_best + info.m_requested <= 1);
339 
340  // If there are any CANDIDATE_READY announcements, there must be exactly one CANDIDATE_BEST or REQUESTED
341  // announcement.
342  if (info.m_candidate_ready > 0) {
343  assert(info.m_candidate_best + info.m_requested == 1);
344  }
345 
346  // If there is both a CANDIDATE_READY and a CANDIDATE_BEST announcement, the CANDIDATE_BEST one must be
347  // at least as good (equal or higher priority) as the best CANDIDATE_READY.
348  if (info.m_candidate_ready && info.m_candidate_best) {
349  assert(info.m_priority_candidate_best >= info.m_priority_best_candidate_ready);
350  }
351 
352  // No txhash can have been announced by the same peer twice.
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());
355  }
356  }
357 
358  void PostGetRequestableSanityCheck(std::chrono::microseconds now) const
359  {
360  for (const Announcement& ann : m_index) {
361  if (ann.IsWaiting()) {
362  // REQUESTED and CANDIDATE_DELAYED must have a time in the future (they should have been converted
363  // to COMPLETED/CANDIDATE_READY respectively).
364  assert(ann.m_time > now);
365  } else if (ann.IsSelectable()) {
366  // CANDIDATE_READY and CANDIDATE_BEST cannot have a time in the future (they should have remained
367  // CANDIDATE_DELAYED, or should have been converted back to it if time went backwards).
368  assert(ann.m_time <= now);
369  }
370  }
371  }
372 
373 private:
375  template<typename Tag>
376  Iter<Tag> Erase(Iter<Tag> it)
377  {
378  auto peerit = m_peerinfo.find(it->m_peer);
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);
383  }
384 
386  template<typename Tag, typename Modifier>
387  void Modify(Iter<Tag> it, Modifier modifier)
388  {
389  auto peerit = m_peerinfo.find(it->m_peer);
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;
395  }
396 
400  void PromoteCandidateReady(Iter<ByTxHash> it)
401  {
402  assert(it != m_index.get<ByTxHash>().end());
403  assert(it->GetState() == State::CANDIDATE_DELAYED);
404  // Convert CANDIDATE_DELAYED to CANDIDATE_READY first.
405  Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_READY); });
406  // The following code relies on the fact that the ByTxHash is sorted by txhash, and then by state (first
407  // _DELAYED, then _READY, then _BEST/REQUESTED). Within the _READY announcements, the best one (highest
408  // priority) comes last. Thus, if an existing _BEST exists for the same txhash that this announcement may
409  // be preferred over, it must immediately follow the newly created _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) {
413  // This is the new best CANDIDATE_READY, and there is no IsSelected() announcement for this txhash
414  // already.
415  Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); });
416  } else if (it_next->GetState() == State::CANDIDATE_BEST) {
417  Priority priority_old = m_computer(*it_next);
418  Priority priority_new = m_computer(*it);
419  if (priority_new > priority_old) {
420  // There is a CANDIDATE_BEST announcement already, but this one is better.
421  Modify<ByTxHash>(it_next, [](Announcement& ann){ ann.SetState(State::CANDIDATE_READY); });
422  Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); });
423  }
424  }
425  }
426 
429  void ChangeAndReselect(Iter<ByTxHash> it, State new_state)
430  {
431  assert(new_state == State::COMPLETED || new_state == State::CANDIDATE_DELAYED);
432  assert(it != m_index.get<ByTxHash>().end());
433  if (it->IsSelected() && it != m_index.get<ByTxHash>().begin()) {
434  auto it_prev = std::prev(it);
435  // The next best CANDIDATE_READY, if any, immediately precedes the REQUESTED or CANDIDATE_BEST
436  // announcement in the ByTxHash index.
437  if (it_prev->m_txhash == it->m_txhash && it_prev->GetState() == State::CANDIDATE_READY) {
438  // If one such CANDIDATE_READY exists (for this txhash), convert it to CANDIDATE_BEST.
439  Modify<ByTxHash>(it_prev, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); });
440  }
441  }
442  Modify<ByTxHash>(it, [new_state](Announcement& ann){ ann.SetState(new_state); });
443  }
444 
446  bool IsOnlyNonCompleted(Iter<ByTxHash> it)
447  {
448  assert(it != m_index.get<ByTxHash>().end());
449  assert(it->GetState() != State::COMPLETED); // Not allowed to call this on COMPLETED announcements.
450 
451  // This announcement has a predecessor that belongs to the same txhash. Due to ordering, and the
452  // fact that 'it' is not COMPLETED, its predecessor cannot be COMPLETED here.
453  if (it != m_index.get<ByTxHash>().begin() && std::prev(it)->m_txhash == it->m_txhash) return false;
454 
455  // This announcement has a successor that belongs to the same txhash, and is not COMPLETED.
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;
458 
459  return true;
460  }
461 
465  bool MakeCompleted(Iter<ByTxHash> it)
466  {
467  assert(it != m_index.get<ByTxHash>().end());
468 
469  // Nothing to be done if it's already COMPLETED.
470  if (it->GetState() == State::COMPLETED) return true;
471 
472  if (IsOnlyNonCompleted(it)) {
473  // This is the last non-COMPLETED announcement for this txhash. Delete all.
474  uint256 txhash = it->m_txhash;
475  do {
476  it = Erase<ByTxHash>(it);
477  } while (it != m_index.get<ByTxHash>().end() && it->m_txhash == txhash);
478  return false;
479  }
480 
481  // Mark the announcement COMPLETED, and select the next best announcement (the first CANDIDATE_READY) if
482  // needed.
483  ChangeAndReselect(it, State::COMPLETED);
484 
485  return true;
486  }
487 
492  void SetTimePoint(std::chrono::microseconds now, std::vector<std::pair<NodeId, GenTxid>>* expired)
493  {
494  if (expired) expired->clear();
495 
496  // Iterate over all CANDIDATE_DELAYED and REQUESTED from old to new, as long as they're in the past,
497  // and convert them to CANDIDATE_READY and COMPLETED respectively.
498  while (!m_index.empty()) {
499  auto it = m_index.get<ByTime>().begin();
500  if (it->GetState() == State::CANDIDATE_DELAYED && it->m_time <= now) {
501  PromoteCandidateReady(m_index.project<ByTxHash>(it));
502  } else if (it->GetState() == State::REQUESTED && it->m_time <= now) {
503  if (expired) expired->emplace_back(it->m_peer, ToGenTxid(*it));
504  MakeCompleted(m_index.project<ByTxHash>(it));
505  } else {
506  break;
507  }
508  }
509 
510  while (!m_index.empty()) {
511  // If time went backwards, we may need to demote CANDIDATE_BEST and CANDIDATE_READY announcements back
512  // to CANDIDATE_DELAYED. This is an unusual edge case, and unlikely to matter in production. However,
513  // it makes it much easier to specify and test TxRequestTracker::Impl's behaviour.
514  auto it = std::prev(m_index.get<ByTime>().end());
515  if (it->IsSelectable() && it->m_time > now) {
516  ChangeAndReselect(m_index.project<ByTxHash>(it), State::CANDIDATE_DELAYED);
517  } else {
518  break;
519  }
520  }
521  }
522 
523 public:
524  explicit Impl(bool deterministic) :
525  m_computer(deterministic),
526  // Explicitly initialize m_index as we need to pass a reference to m_computer to ByTxHashViewExtractor.
527  m_index(boost::make_tuple(
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>())
531  )) {}
532 
533  // Disable copying and assigning (a default copy won't work due the stateful ByTxHashViewExtractor).
534  Impl(const Impl&) = delete;
535  Impl& operator=(const Impl&) = delete;
536 
538  {
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) {
542  // Check what to continue with after this iteration. 'it' will be deleted in what follows, so we need to
543  // decide what to continue with afterwards. There are a number of cases to consider:
544  // - std::next(it) is end() or belongs to a different peer. In that case, this is the last iteration
545  // of the loop (denote this by setting it_next to end()).
546  // - 'it' is not the only non-COMPLETED announcement for its txhash. This means it will be deleted, but
547  // no other Announcement objects will be modified. Continue with std::next(it) if it belongs to the
548  // same peer, but decide this ahead of time (as 'it' may change position in what follows).
549  // - 'it' is the only non-COMPLETED announcement for its txhash. This means it will be deleted along
550  // with all other announcements for the same txhash - which may include std::next(it). However, other
551  // than 'it', no announcements for the same peer can be affected (due to (peer, txhash) uniqueness).
552  // In other words, the situation where std::next(it) is deleted can only occur if std::next(it)
553  // belongs to a different peer but the same txhash as 'it'. This is covered by the first bulletpoint
554  // already, and we'll have set it_next to end().
555  auto it_next = (std::next(it) == index.end() || std::next(it)->m_peer != peer) ? index.end() :
556  std::next(it);
557  // If the announcement isn't already COMPLETED, first make it COMPLETED (which will mark other
558  // CANDIDATEs as CANDIDATE_BEST, or delete all of a txhash's announcements if no non-COMPLETED ones are
559  // left).
560  if (MakeCompleted(m_index.project<ByTxHash>(it))) {
561  // Then actually delete the announcement (unless it was already deleted by MakeCompleted).
562  Erase<ByPeer>(it);
563  }
564  it = it_next;
565  }
566  }
567 
568  void ForgetTxHash(const uint256& txhash)
569  {
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);
573  }
574  }
575 
576  void ReceivedInv(NodeId peer, const GenTxid& gtxid, bool preferred,
577  std::chrono::microseconds reqtime)
578  {
579  // Bail out if we already have a CANDIDATE_BEST announcement for this (txhash, peer) combination. The case
580  // where there is a non-CANDIDATE_BEST announcement already will be caught by the uniqueness property of the
581  // ByPeer index when we try to emplace the new object below.
582  if (m_index.get<ByPeer>().count(ByPeerView{peer, true, gtxid.GetHash()})) return;
583 
584  // Try creating the announcement with CANDIDATE_DELAYED state (which will fail due to the uniqueness
585  // of the ByPeer index if a non-CANDIDATE_BEST announcement already exists with the same txhash and peer).
586  // Bail out in that case.
587  auto ret = m_index.get<ByPeer>().emplace(gtxid, peer, preferred, reqtime, m_current_sequence);
588  if (!ret.second) return;
589 
590  // Update accounting metadata.
591  ++m_peerinfo[peer].m_total;
593  }
594 
596  std::vector<GenTxid> GetRequestable(NodeId peer, std::chrono::microseconds now,
597  std::vector<std::pair<NodeId, GenTxid>>* expired)
598  {
599  // Move time.
600  SetTimePoint(now, expired);
601 
602  // Find all CANDIDATE_BEST announcements for this peer.
603  std::vector<const Announcement*> selected;
604  auto it_peer = m_index.get<ByPeer>().lower_bound(ByPeerView{peer, true, uint256::ZERO});
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);
608  ++it_peer;
609  }
610 
611  // Sort by sequence number.
612  std::sort(selected.begin(), selected.end(), [](const Announcement* a, const Announcement* b) {
613  return a->m_sequence < b->m_sequence;
614  });
615 
616  // Convert to GenTxid and return.
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);
621  });
622  return ret;
623  }
624 
625  void RequestedTx(NodeId peer, const uint256& txhash, std::chrono::microseconds expiry)
626  {
627  auto it = m_index.get<ByPeer>().find(ByPeerView{peer, true, txhash});
628  if (it == m_index.get<ByPeer>().end()) {
629  // There is no CANDIDATE_BEST announcement, look for a _READY or _DELAYED instead. If the caller only
630  // ever invokes RequestedTx with the values returned by GetRequestable, and no other non-const functions
631  // other than ForgetTxHash and GetRequestable in between, this branch will never execute (as txhashes
632  // returned by GetRequestable always correspond to CANDIDATE_BEST announcements).
633 
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)) {
637  // There is no CANDIDATE announcement tracked for this peer, so we have nothing to do. Either this
638  // txhash wasn't tracked at all (and the caller should have called ReceivedInv), or it was already
639  // requested and/or completed for other reasons and this is just a superfluous RequestedTx call.
640  return;
641  }
642 
643  // Look for an existing CANDIDATE_BEST or REQUESTED with the same txhash. We only need to do this if the
644  // found announcement had a different state than CANDIDATE_BEST. If it did, invariants guarantee that no
645  // other CANDIDATE_BEST or REQUESTED can exist.
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) {
649  // The data structure's invariants require that there can be at most one CANDIDATE_BEST or one
650  // REQUESTED announcement per txhash (but not both simultaneously), so we have to convert any
651  // existing CANDIDATE_BEST to another CANDIDATE_* when constructing another REQUESTED.
652  // It doesn't matter whether we pick CANDIDATE_READY or _DELAYED here, as SetTimePoint()
653  // will correct it at GetRequestable() time. If time only goes forward, it will always be
654  // _READY, so pick that to avoid extra work in SetTimePoint().
655  Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::CANDIDATE_READY); });
656  } else if (it_old->GetState() == State::REQUESTED) {
657  // As we're no longer waiting for a response to the previous REQUESTED announcement, convert it
658  // to COMPLETED. This also helps guaranteeing progress.
659  Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::COMPLETED); });
660  }
661  }
662  }
663 
664  Modify<ByPeer>(it, [expiry](Announcement& ann) {
665  ann.SetState(State::REQUESTED);
666  ann.m_time = expiry;
667  });
668  }
669 
670  void ReceivedResponse(NodeId peer, const uint256& txhash)
671  {
672  // We need to search the ByPeer index for both (peer, false, txhash) and (peer, true, txhash).
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});
676  }
677  if (it != m_index.get<ByPeer>().end()) MakeCompleted(m_index.project<ByTxHash>(it));
678  }
679 
680  size_t CountInFlight(NodeId peer) const
681  {
682  auto it = m_peerinfo.find(peer);
683  if (it != m_peerinfo.end()) return it->second.m_requested;
684  return 0;
685  }
686 
687  size_t CountCandidates(NodeId peer) const
688  {
689  auto it = m_peerinfo.find(peer);
690  if (it != m_peerinfo.end()) return it->second.m_total - it->second.m_requested - it->second.m_completed;
691  return 0;
692  }
693 
694  size_t Count(NodeId peer) const
695  {
696  auto it = m_peerinfo.find(peer);
697  if (it != m_peerinfo.end()) return it->second.m_total;
698  return 0;
699  }
700 
702  size_t Size() const { return m_index.size(); }
703 
704  uint64_t ComputePriority(const uint256& txhash, NodeId peer, bool preferred) const
705  {
706  // Return Priority as a uint64_t as Priority is internal.
707  return uint64_t{m_computer(txhash, peer, preferred)};
708  }
709 
710 };
711 
713  m_impl{std::make_unique<TxRequestTracker::Impl>(deterministic)} {}
714 
716 
717 void TxRequestTracker::ForgetTxHash(const uint256& txhash) { m_impl->ForgetTxHash(txhash); }
718 void TxRequestTracker::DisconnectedPeer(NodeId peer) { m_impl->DisconnectedPeer(peer); }
719 size_t TxRequestTracker::CountInFlight(NodeId peer) const { return m_impl->CountInFlight(peer); }
720 size_t TxRequestTracker::CountCandidates(NodeId peer) const { return m_impl->CountCandidates(peer); }
721 size_t TxRequestTracker::Count(NodeId peer) const { return m_impl->Count(peer); }
722 size_t TxRequestTracker::Size() const { return m_impl->Size(); }
723 void TxRequestTracker::SanityCheck() const { m_impl->SanityCheck(); }
724 
725 void TxRequestTracker::PostGetRequestableSanityCheck(std::chrono::microseconds now) const
726 {
727  m_impl->PostGetRequestableSanityCheck(now);
728 }
729 
730 void TxRequestTracker::ReceivedInv(NodeId peer, const GenTxid& gtxid, bool preferred,
731  std::chrono::microseconds reqtime)
732 {
733  m_impl->ReceivedInv(peer, gtxid, preferred, reqtime);
734 }
735 
736 void TxRequestTracker::RequestedTx(NodeId peer, const uint256& txhash, std::chrono::microseconds expiry)
737 {
738  m_impl->RequestedTx(peer, txhash, expiry);
739 }
740 
742 {
743  m_impl->ReceivedResponse(peer, txhash);
744 }
745 
746 std::vector<GenTxid> TxRequestTracker::GetRequestable(NodeId peer, std::chrono::microseconds now,
747  std::vector<std::pair<NodeId, GenTxid>>* expired)
748 {
749  return m_impl->GetRequestable(peer, now, expired);
750 }
751 
752 uint64_t TxRequestTracker::ComputePriority(const uint256& txhash, NodeId peer, bool preferred) const
753 {
754  return m_impl->ComputePriority(txhash, peer, preferred);
755 }
TxRequestTracker::CountInFlight
size_t CountInFlight(NodeId peer) const
Count how many REQUESTED announcements a peer has.
Definition: txrequest.cpp:719
TxRequestTracker::Impl::m_peerinfo
std::unordered_map< NodeId, PeerInfo > m_peerinfo
Map with this tracker's per-peer statistics.
Definition: txrequest.cpp:321
NodeId
int64_t NodeId
Definition: net.h:87
assert
assert(!tx.IsCoinBase())
TxRequestTracker::Impl::ChangeAndReselect
void ChangeAndReselect(Iter< ByTxHash > it, State new_state)
Change the state of an announcement to something non-IsSelected().
Definition: txrequest.cpp:429
GenTxid
A generic txid reference (txid or wtxid).
Definition: transaction.h:390
TxRequestTracker::Impl
Actual implementation for TxRequestTracker's data structure.
Definition: txrequest.cpp:309
transaction.h
TxRequestTracker::Impl::m_index
Index m_index
This tracker's main data structure. See SanityCheck() for the invariants that apply to it.
Definition: txrequest.cpp:318
TxRequestTracker::Impl::Size
size_t Size() const
Count how many announcements are being tracked in total across all peers and transactions.
Definition: txrequest.cpp:702
uint256.h
TxRequestTracker::Size
size_t Size() const
Count how many announcements are being tracked in total across all peers and transaction hashes.
Definition: txrequest.cpp:722
base_blob::size
static constexpr unsigned int size()
Definition: uint256.h:78
txrequest.h
TxRequestTracker::Count
size_t Count(NodeId peer) const
Count how many announcements a peer has (REQUESTED, CANDIDATE, and COMPLETED combined).
Definition: txrequest.cpp:721
GetRand
uint64_t GetRand(uint64_t nMax) noexcept
Generate a uniform random integer in the range [0..range).
Definition: random.cpp:591
CSipHasher
SipHash-2-4.
Definition: siphash.h:13
TxRequestTracker::Impl::PromoteCandidateReady
void PromoteCandidateReady(Iter< ByTxHash > it)
Convert a CANDIDATE_DELAYED announcement into a CANDIDATE_READY.
Definition: txrequest.cpp:400
TxRequestTracker::Impl::operator=
Impl & operator=(const Impl &)=delete
siphash.h
random.h
TxRequestTracker::Impl::RequestedTx
void RequestedTx(NodeId peer, const uint256 &txhash, std::chrono::microseconds expiry)
Definition: txrequest.cpp:625
TxRequestTracker::m_impl
const std::unique_ptr< Impl > m_impl
Definition: txrequest.h:98
TxRequestTracker::Impl::m_current_sequence
SequenceNumber m_current_sequence
The current sequence number.
Definition: txrequest.cpp:312
TxRequestTracker::Impl::ForgetTxHash
void ForgetTxHash(const uint256 &txhash)
Definition: txrequest.cpp:568
TxRequestTracker::Impl::ComputePriority
uint64_t ComputePriority(const uint256 &txhash, NodeId peer, bool preferred) const
Definition: txrequest.cpp:704
TxRequestTracker::Impl::Erase
Iter< Tag > Erase(Iter< Tag > it)
Wrapper around Index::...::erase that keeps m_peerinfo up to date.
Definition: txrequest.cpp:376
TxRequestTracker::ForgetTxHash
void ForgetTxHash(const uint256 &txhash)
Deletes all announcements for a given txhash (both txid and wtxid ones).
Definition: txrequest.cpp:717
CSipHasher::Finalize
uint64_t Finalize() const
Compute the 64-bit SipHash-2-4 of the data written so far.
Definition: siphash.cpp:76
TxRequestTracker::CountCandidates
size_t CountCandidates(NodeId peer) const
Count how many CANDIDATE announcements a peer has.
Definition: txrequest.cpp:720
TxRequestTracker::~TxRequestTracker
~TxRequestTracker()
TxRequestTracker::RequestedTx
void RequestedTx(NodeId peer, const uint256 &txhash, std::chrono::microseconds expiry)
Marks a transaction as requested, with a specified expiry.
Definition: txrequest.cpp:736
uint256::ZERO
static const uint256 ZERO
Definition: uint256.h:129
uint256
256-bit opaque blob.
Definition: uint256.h:124
operator==
bool operator==(const CNetAddr &a, const CNetAddr &b)
Definition: netaddress.cpp:636
TxRequestTracker::GetRequestable
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.
Definition: txrequest.cpp:746
TxRequestTracker::TxRequestTracker
TxRequestTracker(bool deterministic=false)
Construct a TxRequestTracker.
Definition: txrequest.cpp:712
TxRequestTracker::PostGetRequestableSanityCheck
void PostGetRequestableSanityCheck(std::chrono::microseconds now) const
Run a time-dependent internal consistency check (testing only).
Definition: txrequest.cpp:725
ToGenTxid
GenTxid ToGenTxid(const CInv &inv)
Convert a TX/WITNESS_TX/WTX CInv to a GenTxid.
Definition: protocol.cpp:223
TxRequestTracker::Impl::SanityCheck
void SanityCheck() const
Definition: txrequest.cpp:324
TxRequestTracker::Impl::Count
size_t Count(NodeId peer) const
Definition: txrequest.cpp:694
TxRequestTracker::Impl::DisconnectedPeer
void DisconnectedPeer(NodeId peer)
Definition: txrequest.cpp:537
TxRequestTracker::Impl::ReceivedResponse
void ReceivedResponse(NodeId peer, const uint256 &txhash)
Definition: txrequest.cpp:670
TxRequestTracker::Impl::Impl
Impl(bool deterministic)
Definition: txrequest.cpp:524
TxRequestTracker::Impl::IsOnlyNonCompleted
bool IsOnlyNonCompleted(Iter< ByTxHash > it)
Check if 'it' is the only announcement for a given txhash that isn't COMPLETED.
Definition: txrequest.cpp:446
TxRequestTracker::SanityCheck
void SanityCheck() const
Run internal consistency check (testing only).
Definition: txrequest.cpp:723
TxRequestTracker::Impl::m_computer
const PriorityComputer m_computer
This tracker's priority computer.
Definition: txrequest.cpp:315
TxRequestTracker::Impl::CountInFlight
size_t CountInFlight(NodeId peer) const
Definition: txrequest.cpp:680
TxRequestTracker::Impl::MakeCompleted
bool MakeCompleted(Iter< ByTxHash > it)
Convert any announcement to a COMPLETED one.
Definition: txrequest.cpp:465
TxRequestTracker::Impl::SetTimePoint
void SetTimePoint(std::chrono::microseconds now, std::vector< std::pair< NodeId, GenTxid >> *expired)
Make the data structure consistent with a given point in time:
Definition: txrequest.cpp:492
TxRequestTracker::Impl::GetRequestable
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.
Definition: txrequest.cpp:596
TxRequestTracker::ReceivedInv
void ReceivedInv(NodeId peer, const GenTxid &gtxid, bool preferred, std::chrono::microseconds reqtime)
Adds a new CANDIDATE announcement.
Definition: txrequest.cpp:730
TxRequestTracker::Impl::ReceivedInv
void ReceivedInv(NodeId peer, const GenTxid &gtxid, bool preferred, std::chrono::microseconds reqtime)
Definition: txrequest.cpp:576
TxRequestTracker::Impl::Modify
void Modify(Iter< Tag > it, Modifier modifier)
Wrapper around Index::...::modify that keeps m_peerinfo up to date.
Definition: txrequest.cpp:387
TxRequestTracker::DisconnectedPeer
void DisconnectedPeer(NodeId peer)
Deletes all announcements for a given peer.
Definition: txrequest.cpp:718
TxRequestTracker::ReceivedResponse
void ReceivedResponse(NodeId peer, const uint256 &txhash)
Converts a CANDIDATE or REQUESTED announcement to a COMPLETED one.
Definition: txrequest.cpp:741
net.h
TxRequestTracker::ComputePriority
uint64_t ComputePriority(const uint256 &txhash, NodeId peer, bool preferred) const
Access to the internal priority computation (testing only)
Definition: txrequest.cpp:752
base_blob::begin
unsigned char * begin()
Definition: uint256.h:58
TxRequestTracker::Impl::PostGetRequestableSanityCheck
void PostGetRequestableSanityCheck(std::chrono::microseconds now) const
Definition: txrequest.cpp:358
TxRequestTracker::Impl::CountCandidates
size_t CountCandidates(NodeId peer) const
Definition: txrequest.cpp:687
CSipHasher::Write
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 ...
Definition: siphash.cpp:28