Bitcoin ABC  0.24.11
P2P Digital Currency
invrequest.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 <invrequest.h>
6 
7 #include <crypto/siphash.h>
8 #include <net.h>
9 #include <random.h>
10 
11 #include <boost/multi_index/ordered_index.hpp>
12 #include <boost/multi_index_container.hpp>
13 
14 #include <cassert>
15 #include <chrono>
16 #include <functional>
17 #include <unordered_map>
18 #include <utility>
19 
20 namespace {
21 
42 enum class State : uint8_t {
44  CANDIDATE_DELAYED,
48  CANDIDATE_READY,
55  CANDIDATE_BEST,
57  REQUESTED,
59  COMPLETED,
60 };
61 
63 using SequenceNumber = uint64_t;
64 
69 struct Announcement {
71  const uint256 m_invid;
76  std::chrono::microseconds m_time;
78  const NodeId m_peer;
80  const SequenceNumber m_sequence : 60;
82  const bool m_preferred : 1;
83 
90  uint8_t m_state : 3;
91 
93  State GetState() const { return static_cast<State>(m_state); }
94 
96  void SetState(State state) { m_state = static_cast<uint8_t>(state); }
97 
102  bool IsSelected() const {
103  return GetState() == State::CANDIDATE_BEST ||
104  GetState() == State::REQUESTED;
105  }
106 
108  bool IsWaiting() const {
109  return GetState() == State::REQUESTED ||
110  GetState() == State::CANDIDATE_DELAYED;
111  }
112 
117  bool IsSelectable() const {
118  return GetState() == State::CANDIDATE_READY ||
119  GetState() == State::CANDIDATE_BEST;
120  }
121 
126  Announcement(const uint256 &invid, NodeId peer, bool preferred,
127  std::chrono::microseconds reqtime, SequenceNumber sequence)
128  : m_invid(invid), m_time(reqtime), m_peer(peer), m_sequence(sequence),
129  m_preferred(preferred),
130  m_state(static_cast<uint8_t>(State::CANDIDATE_DELAYED)) {}
131 };
132 
134 using Priority = uint64_t;
135 
141 class PriorityComputer {
142  const uint64_t m_k0, m_k1;
143 
144 public:
145  explicit PriorityComputer(bool deterministic)
146  : m_k0{deterministic ? 0 : GetRand(0xFFFFFFFFFFFFFFFF)},
147  m_k1{deterministic ? 0 : GetRand(0xFFFFFFFFFFFFFFFF)} {}
148 
149  Priority operator()(const uint256 &invid, NodeId peer,
150  bool preferred) const {
151  uint64_t low_bits = CSipHasher(m_k0, m_k1)
152  .Write(invid.begin(), invid.size())
153  .Write(peer)
154  .Finalize() >>
155  1;
156  return low_bits | uint64_t{preferred} << 63;
157  }
158 
159  Priority operator()(const Announcement &ann) const {
160  return operator()(ann.m_invid, ann.m_peer, ann.m_preferred);
161  }
162 };
163 
164 // Definitions for the 3 indexes used in the main data structure.
165 //
166 // Each index has a By* type to identify it, a By*View data type to represent
167 // the view of announcement it is sorted by, and an By*ViewExtractor type to
168 // convert an announcement into the By*View type. See
169 // https://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/reference/key_extraction.html#key_extractors
170 // for more information about the key extraction concept.
171 
172 // The ByPeer index is sorted by (peer, state == CANDIDATE_BEST, invid)
173 //
174 // Uses:
175 // * Looking up existing announcements by peer/invid, by checking both (peer,
176 // false, invid) and (peer, true, invid).
177 // * Finding all CANDIDATE_BEST announcements for a given peer in
178 // GetRequestable.
179 struct ByPeer {};
180 using ByPeerView = std::tuple<NodeId, bool, const uint256 &>;
181 struct ByPeerViewExtractor {
182  using result_type = ByPeerView;
183  result_type operator()(const Announcement &ann) const {
184  return ByPeerView{ann.m_peer, ann.GetState() == State::CANDIDATE_BEST,
185  ann.m_invid};
186  }
187 };
188 
189 // The ByInvId index is sorted by (invid, state, priority).
190 //
191 // Note: priority == 0 whenever state != CANDIDATE_READY.
192 //
193 // Uses:
194 // * Deleting all announcements with a given invid in ForgetInvId.
195 // * Finding the best CANDIDATE_READY to convert to CANDIDATE_BEST, when no
196 // other CANDIDATE_READY or REQUESTED announcement exists for that invid.
197 // * Determining when no more non-COMPLETED announcements for a given invid
198 // exist, so the COMPLETED ones can be deleted.
199 struct ByInvId {};
200 using ByInvIdView = std::tuple<const uint256 &, State, Priority>;
201 class ByInvIdViewExtractor {
202  const PriorityComputer &m_computer;
203 
204 public:
205  ByInvIdViewExtractor(const PriorityComputer &computer)
206  : m_computer(computer) {}
207  using result_type = ByInvIdView;
208  result_type operator()(const Announcement &ann) const {
209  const Priority prio =
210  (ann.GetState() == State::CANDIDATE_READY) ? m_computer(ann) : 0;
211  return ByInvIdView{ann.m_invid, ann.GetState(), prio};
212  }
213 };
214 
215 enum class WaitState {
218  FUTURE_EVENT,
220  NO_EVENT,
223  PAST_EVENT,
224 };
225 
226 WaitState GetWaitState(const Announcement &ann) {
227  if (ann.IsWaiting()) {
228  return WaitState::FUTURE_EVENT;
229  }
230  if (ann.IsSelectable()) {
231  return WaitState::PAST_EVENT;
232  }
233  return WaitState::NO_EVENT;
234 }
235 
236 // The ByTime index is sorted by (wait_state, time).
237 //
238 // All announcements with a timestamp in the future can be found by iterating
239 // the index forward from the beginning. All announcements with a timestamp in
240 // the past can be found by iterating the index backwards from the end.
241 //
242 // Uses:
243 // * Finding CANDIDATE_DELAYED announcements whose reqtime has passed, and
244 // REQUESTED announcements whose expiry has passed.
245 // * Finding CANDIDATE_READY/BEST announcements whose reqtime is in the future
246 // (when the clock time went backwards).
247 struct ByTime {};
248 using ByTimeView = std::pair<WaitState, std::chrono::microseconds>;
249 struct ByTimeViewExtractor {
250  using result_type = ByTimeView;
251  result_type operator()(const Announcement &ann) const {
252  return ByTimeView{GetWaitState(ann), ann.m_time};
253  }
254 };
255 
260 using Index = boost::multi_index_container<
261  Announcement,
262  boost::multi_index::indexed_by<
263  boost::multi_index::ordered_unique<boost::multi_index::tag<ByPeer>,
264  ByPeerViewExtractor>,
265  boost::multi_index::ordered_non_unique<boost::multi_index::tag<ByInvId>,
266  ByInvIdViewExtractor>,
267  boost::multi_index::ordered_non_unique<boost::multi_index::tag<ByTime>,
268  ByTimeViewExtractor>>>;
269 
271 template <typename Tag> using Iter = typename Index::index<Tag>::type::iterator;
272 
274 struct PeerInfo {
276  size_t m_total = 0;
278  size_t m_completed = 0;
280  size_t m_requested = 0;
281 };
282 
284 struct InvIdInfo {
286  size_t m_candidate_delayed = 0;
288  size_t m_candidate_ready = 0;
290  size_t m_candidate_best = 0;
293  size_t m_requested = 0;
296  Priority m_priority_candidate_best = std::numeric_limits<Priority>::max();
299  Priority m_priority_best_candidate_ready =
300  std::numeric_limits<Priority>::min();
302  std::vector<NodeId> m_peers;
303 };
304 
306 bool operator==(const PeerInfo &a, const PeerInfo &b) {
307  return std::tie(a.m_total, a.m_completed, a.m_requested) ==
308  std::tie(b.m_total, b.m_completed, b.m_requested);
309 };
310 
314 std::unordered_map<NodeId, PeerInfo> RecomputePeerInfo(const Index &index) {
315  std::unordered_map<NodeId, PeerInfo> ret;
316  for (const Announcement &ann : index) {
317  PeerInfo &info = ret[ann.m_peer];
318  ++info.m_total;
319  info.m_requested += (ann.GetState() == State::REQUESTED);
320  info.m_completed += (ann.GetState() == State::COMPLETED);
321  }
322  return ret;
323 }
324 
326 std::map<uint256, InvIdInfo>
327 ComputeInvIdInfo(const Index &index, const PriorityComputer &computer) {
328  std::map<uint256, InvIdInfo> ret;
329  for (const Announcement &ann : index) {
330  InvIdInfo &info = ret[ann.m_invid];
331  // Classify how many announcements of each state we have for this invid.
332  info.m_candidate_delayed +=
333  (ann.GetState() == State::CANDIDATE_DELAYED);
334  info.m_candidate_ready += (ann.GetState() == State::CANDIDATE_READY);
335  info.m_candidate_best += (ann.GetState() == State::CANDIDATE_BEST);
336  info.m_requested += (ann.GetState() == State::REQUESTED);
337  // And track the priority of the best CANDIDATE_READY/CANDIDATE_BEST
338  // announcements.
339  if (ann.GetState() == State::CANDIDATE_BEST) {
340  info.m_priority_candidate_best = computer(ann);
341  }
342  if (ann.GetState() == State::CANDIDATE_READY) {
343  info.m_priority_best_candidate_ready =
344  std::max(info.m_priority_best_candidate_ready, computer(ann));
345  }
346  // Also keep track of which peers this invid has an announcement for
347  // (so we can detect duplicates).
348  info.m_peers.push_back(ann.m_peer);
349  }
350  return ret;
351 }
352 
353 } // namespace
354 
359  SequenceNumber m_current_sequence{0};
360 
362  const PriorityComputer m_computer;
363 
366  Index m_index;
367 
369  std::unordered_map<NodeId, PeerInfo> m_peerinfo;
370 
371 public:
372  void SanityCheck() const {
373  // Recompute m_peerdata from m_index. This verifies the data in it as it
374  // should just be caching statistics on m_index. It also verifies the
375  // invariant that no PeerInfo announcements with m_total==0 exist.
376  assert(m_peerinfo == RecomputePeerInfo(m_index));
377 
378  // Calculate per-invid statistics from m_index, and validate
379  // invariants.
380  for (auto &item : ComputeInvIdInfo(m_index, m_computer)) {
381  InvIdInfo &info = item.second;
382 
383  // Cannot have only COMPLETED peer (invid should have been forgotten
384  // already)
385  assert(info.m_candidate_delayed + info.m_candidate_ready +
386  info.m_candidate_best + info.m_requested >
387  0);
388 
389  // Can have at most 1 CANDIDATE_BEST/REQUESTED peer
390  assert(info.m_candidate_best + info.m_requested <= 1);
391 
392  // If there are any CANDIDATE_READY announcements, there must be
393  // exactly one CANDIDATE_BEST or REQUESTED announcement.
394  if (info.m_candidate_ready > 0) {
395  assert(info.m_candidate_best + info.m_requested == 1);
396  }
397 
398  // If there is both a CANDIDATE_READY and a CANDIDATE_BEST
399  // announcement, the CANDIDATE_BEST one must be at least as good
400  // (equal or higher priority) as the best CANDIDATE_READY.
401  if (info.m_candidate_ready && info.m_candidate_best) {
402  assert(info.m_priority_candidate_best >=
403  info.m_priority_best_candidate_ready);
404  }
405 
406  // No invid can have been announced by the same peer twice.
407  std::sort(info.m_peers.begin(), info.m_peers.end());
408  assert(
409  std::adjacent_find(info.m_peers.begin(), info.m_peers.end()) ==
410  info.m_peers.end());
411  }
412  }
413 
414  void PostGetRequestableSanityCheck(std::chrono::microseconds now) const {
415  for (const Announcement &ann : m_index) {
416  if (ann.IsWaiting()) {
417  // REQUESTED and CANDIDATE_DELAYED must have a time in the
418  // future (they should have been converted to
419  // COMPLETED/CANDIDATE_READY respectively).
420  assert(ann.m_time > now);
421  } else if (ann.IsSelectable()) {
422  // CANDIDATE_READY and CANDIDATE_BEST cannot have a time in the
423  // future (they should have remained CANDIDATE_DELAYED, or
424  // should have been converted back to it if time went
425  // backwards).
426  assert(ann.m_time <= now);
427  }
428  }
429  }
430 
431 private:
433  template <typename Tag> Iter<Tag> Erase(Iter<Tag> it) {
434  auto peerit = m_peerinfo.find(it->m_peer);
435  peerit->second.m_completed -= it->GetState() == State::COMPLETED;
436  peerit->second.m_requested -= it->GetState() == State::REQUESTED;
437  if (--peerit->second.m_total == 0) {
438  m_peerinfo.erase(peerit);
439  }
440  return m_index.get<Tag>().erase(it);
441  }
442 
444  template <typename Tag, typename Modifier>
445  void Modify(Iter<Tag> it, Modifier modifier) {
446  auto peerit = m_peerinfo.find(it->m_peer);
447  peerit->second.m_completed -= it->GetState() == State::COMPLETED;
448  peerit->second.m_requested -= it->GetState() == State::REQUESTED;
449  m_index.get<Tag>().modify(it, std::move(modifier));
450  peerit->second.m_completed += it->GetState() == State::COMPLETED;
451  peerit->second.m_requested += it->GetState() == State::REQUESTED;
452  }
453 
458  void PromoteCandidateReady(Iter<ByInvId> it) {
459  assert(it != m_index.get<ByInvId>().end());
460  assert(it->GetState() == State::CANDIDATE_DELAYED);
461  // Convert CANDIDATE_DELAYED to CANDIDATE_READY first.
462  Modify<ByInvId>(it, [](Announcement &ann) {
463  ann.SetState(State::CANDIDATE_READY);
464  });
465  // The following code relies on the fact that the ByInvId is sorted by
466  // invid, and then by state (first _DELAYED, then _READY, then
467  // _BEST/REQUESTED). Within the _READY announcements, the best one
468  // (highest priority) comes last. Thus, if an existing _BEST exists for
469  // the same invid that this announcement may be preferred over, it must
470  // immediately follow the newly created _READY.
471  auto it_next = std::next(it);
472  if (it_next == m_index.get<ByInvId>().end() ||
473  it_next->m_invid != it->m_invid ||
474  it_next->GetState() == State::COMPLETED) {
475  // This is the new best CANDIDATE_READY, and there is no
476  // IsSelected() announcement for this invid already.
477  Modify<ByInvId>(it, [](Announcement &ann) {
478  ann.SetState(State::CANDIDATE_BEST);
479  });
480  } else if (it_next->GetState() == State::CANDIDATE_BEST) {
481  Priority priority_old = m_computer(*it_next);
482  Priority priority_new = m_computer(*it);
483  if (priority_new > priority_old) {
484  // There is a CANDIDATE_BEST announcement already, but this one
485  // is better.
486  Modify<ByInvId>(it_next, [](Announcement &ann) {
487  ann.SetState(State::CANDIDATE_READY);
488  });
489  Modify<ByInvId>(it, [](Announcement &ann) {
490  ann.SetState(State::CANDIDATE_BEST);
491  });
492  }
493  }
494  }
495 
499  void ChangeAndReselect(Iter<ByInvId> it, State new_state) {
500  assert(new_state == State::COMPLETED ||
501  new_state == State::CANDIDATE_DELAYED);
502  assert(it != m_index.get<ByInvId>().end());
503  if (it->IsSelected() && it != m_index.get<ByInvId>().begin()) {
504  auto it_prev = std::prev(it);
505  // The next best CANDIDATE_READY, if any, immediately precedes the
506  // REQUESTED or CANDIDATE_BEST announcement in the ByInvId index.
507  if (it_prev->m_invid == it->m_invid &&
508  it_prev->GetState() == State::CANDIDATE_READY) {
509  // If one such CANDIDATE_READY exists (for this invid), convert
510  // it to CANDIDATE_BEST.
511  Modify<ByInvId>(it_prev, [](Announcement &ann) {
512  ann.SetState(State::CANDIDATE_BEST);
513  });
514  }
515  }
516  Modify<ByInvId>(
517  it, [new_state](Announcement &ann) { ann.SetState(new_state); });
518  }
519 
522  bool IsOnlyNonCompleted(Iter<ByInvId> it) {
523  assert(it != m_index.get<ByInvId>().end());
524  // Not allowed to call this on COMPLETED announcements.
525  assert(it->GetState() != State::COMPLETED);
526 
527  // This announcement has a predecessor that belongs to the same invid.
528  // Due to ordering, and the fact that 'it' is not COMPLETED, its
529  // predecessor cannot be COMPLETED here.
530  if (it != m_index.get<ByInvId>().begin() &&
531  std::prev(it)->m_invid == it->m_invid) {
532  return false;
533  }
534 
535  // This announcement has a successor that belongs to the same invid,
536  // and is not COMPLETED.
537  if (std::next(it) != m_index.get<ByInvId>().end() &&
538  std::next(it)->m_invid == it->m_invid &&
539  std::next(it)->GetState() != State::COMPLETED) {
540  return false;
541  }
542 
543  return true;
544  }
545 
553  bool MakeCompleted(Iter<ByInvId> it) {
554  assert(it != m_index.get<ByInvId>().end());
555 
556  // Nothing to be done if it's already COMPLETED.
557  if (it->GetState() == State::COMPLETED) {
558  return true;
559  }
560 
561  if (IsOnlyNonCompleted(it)) {
562  // This is the last non-COMPLETED announcement for this invid.
563  // Delete all.
564  uint256 invid = it->m_invid;
565  do {
566  it = Erase<ByInvId>(it);
567  } while (it != m_index.get<ByInvId>().end() &&
568  it->m_invid == invid);
569  return false;
570  }
571 
572  // Mark the announcement COMPLETED, and select the next best
573  // announcement (the first CANDIDATE_READY) if needed.
574  ChangeAndReselect(it, State::COMPLETED);
575 
576  return true;
577  }
578 
585  void SetTimePoint(std::chrono::microseconds now,
586  ClearExpiredFun clearExpired,
587  EmplaceExpiredFun emplaceExpired) {
588  clearExpired();
589  // Iterate over all CANDIDATE_DELAYED and REQUESTED from old to new, as
590  // long as they're in the past, and convert them to CANDIDATE_READY and
591  // COMPLETED respectively.
592  while (!m_index.empty()) {
593  auto it = m_index.get<ByTime>().begin();
594  if (it->GetState() == State::CANDIDATE_DELAYED &&
595  it->m_time <= now) {
596  PromoteCandidateReady(m_index.project<ByInvId>(it));
597  } else if (it->GetState() == State::REQUESTED &&
598  it->m_time <= now) {
599  emplaceExpired(it->m_peer, it->m_invid);
600  MakeCompleted(m_index.project<ByInvId>(it));
601  } else {
602  break;
603  }
604  }
605 
606  while (!m_index.empty()) {
607  // If time went backwards, we may need to demote CANDIDATE_BEST and
608  // CANDIDATE_READY announcements back to CANDIDATE_DELAYED. This is
609  // an unusual edge case, and unlikely to matter in production.
610  // However, it makes it much easier to specify and test
611  // InvRequestTracker::Impl's behaviour.
612  auto it = std::prev(m_index.get<ByTime>().end());
613  if (it->IsSelectable() && it->m_time > now) {
614  ChangeAndReselect(m_index.project<ByInvId>(it),
615  State::CANDIDATE_DELAYED);
616  } else {
617  break;
618  }
619  }
620  }
621 
622 public:
623  InvRequestTrackerImpl(bool deterministic)
624  : m_computer(deterministic),
625  // Explicitly initialize m_index as we need to pass a reference to
626  // m_computer to ByInvIdViewExtractor.
627  m_index(boost::make_tuple(
628  boost::make_tuple(ByPeerViewExtractor(), std::less<ByPeerView>()),
629  boost::make_tuple(ByInvIdViewExtractor(m_computer),
630  std::less<ByInvIdView>()),
631  boost::make_tuple(ByTimeViewExtractor(),
632  std::less<ByTimeView>()))) {}
633 
634  // Disable copying and assigning (a default copy won't work due the stateful
635  // ByInvIdViewExtractor).
638 
639  ~InvRequestTrackerImpl() = default;
640 
642  auto &index = m_index.get<ByPeer>();
643  auto it =
644  index.lower_bound(ByPeerView{peer, false, uint256(uint256::ZERO)});
645  while (it != index.end() && it->m_peer == peer) {
646  // Check what to continue with after this iteration. 'it' will be
647  // deleted in what follows, so we need to decide what to continue
648  // with afterwards. There are a number of cases to consider:
649  // - std::next(it) is end() or belongs to a different peer. In that
650  // case, this is the last iteration of the loop (denote this by
651  // setting it_next to end()).
652  // - 'it' is not the only non-COMPLETED announcement for its invid.
653  // This means it will be deleted, but no other Announcement
654  // objects will be modified. Continue with std::next(it) if it
655  // belongs to the same peer, but decide this ahead of time (as
656  // 'it' may change position in what follows).
657  // - 'it' is the only non-COMPLETED announcement for its invid. This
658  // means it will be deleted along with all other announcements for
659  // the same invid - which may include std::next(it). However,
660  // other than 'it', no announcements for the same peer can be
661  // affected (due to (peer, invid) uniqueness). In other words, the
662  // situation where std::next(it) is deleted can only occur if
663  // std::next(it) belongs to a different peer but the same invid as
664  // 'it'. This is covered by the first bulletpoint already, and
665  // we'll have set it_next to end().
666  auto it_next =
667  (std::next(it) == index.end() || std::next(it)->m_peer != peer)
668  ? index.end()
669  : std::next(it);
670  // If the announcement isn't already COMPLETED, first make it
671  // COMPLETED (which will mark other CANDIDATEs as CANDIDATE_BEST, or
672  // delete all of a invid's announcements if no non-COMPLETED ones
673  // are left).
674  if (MakeCompleted(m_index.project<ByInvId>(it))) {
675  // Then actually delete the announcement (unless it was already
676  // deleted by MakeCompleted).
677  Erase<ByPeer>(it);
678  }
679  it = it_next;
680  }
681  }
682 
683  void ForgetInvId(const uint256 &invid) {
684  auto it = m_index.get<ByInvId>().lower_bound(
685  ByInvIdView{invid, State::CANDIDATE_DELAYED, 0});
686  while (it != m_index.get<ByInvId>().end() && it->m_invid == invid) {
687  it = Erase<ByInvId>(it);
688  }
689  }
690 
691  void ReceivedInv(NodeId peer, const uint256 &invid, bool preferred,
692  std::chrono::microseconds reqtime) {
693  // Bail out if we already have a CANDIDATE_BEST announcement for this
694  // (invid, peer) combination. The case where there is a
695  // non-CANDIDATE_BEST announcement already will be caught by the
696  // uniqueness property of the ByPeer index when we try to emplace the
697  // new object below.
698  if (m_index.get<ByPeer>().count(ByPeerView{peer, true, invid})) {
699  return;
700  }
701 
702  // Try creating the announcement with CANDIDATE_DELAYED state (which
703  // will fail due to the uniqueness of the ByPeer index if a
704  // non-CANDIDATE_BEST announcement already exists with the same invid
705  // and peer). Bail out in that case.
706  auto ret = m_index.get<ByPeer>().emplace(invid, peer, preferred,
707  reqtime, m_current_sequence);
708  if (!ret.second) {
709  return;
710  }
711 
712  // Update accounting metadata.
713  ++m_peerinfo[peer].m_total;
715  }
716 
718  std::vector<uint256> GetRequestable(NodeId peer,
719  std::chrono::microseconds now,
720  ClearExpiredFun clearExpired,
721  EmplaceExpiredFun emplaceExpired) {
722  // Move time.
723  SetTimePoint(now, clearExpired, emplaceExpired);
724 
725  // Find all CANDIDATE_BEST announcements for this peer.
726  std::vector<const Announcement *> selected;
727  auto it_peer = m_index.get<ByPeer>().lower_bound(
728  ByPeerView{peer, true, uint256(uint256::ZERO)});
729  while (it_peer != m_index.get<ByPeer>().end() &&
730  it_peer->m_peer == peer &&
731  it_peer->GetState() == State::CANDIDATE_BEST) {
732  selected.emplace_back(&*it_peer);
733  ++it_peer;
734  }
735 
736  // Sort by sequence number.
737  std::sort(selected.begin(), selected.end(),
738  [](const Announcement *a, const Announcement *b) {
739  return a->m_sequence < b->m_sequence;
740  });
741 
742  // Convert to InvId and return.
743  std::vector<uint256> ret;
744  ret.reserve(selected.size());
745  std::transform(selected.begin(), selected.end(),
746  std::back_inserter(ret),
747  [](const Announcement *ann) { return ann->m_invid; });
748  return ret;
749  }
750 
751  void RequestedData(NodeId peer, const uint256 &invid,
752  std::chrono::microseconds expiry) {
753  auto it = m_index.get<ByPeer>().find(ByPeerView{peer, true, invid});
754  if (it == m_index.get<ByPeer>().end()) {
755  // There is no CANDIDATE_BEST announcement, look for a _READY or
756  // _DELAYED instead. If the caller only ever invokes RequestedData
757  // with the values returned by GetRequestable, and no other
758  // non-const functions other than ForgetInvId and GetRequestable in
759  // between, this branch will never execute (as invids returned by
760  // GetRequestable always correspond to CANDIDATE_BEST
761  // announcements).
762 
763  it = m_index.get<ByPeer>().find(ByPeerView{peer, false, invid});
764  if (it == m_index.get<ByPeer>().end() ||
765  (it->GetState() != State::CANDIDATE_DELAYED &&
766  it->GetState() != State::CANDIDATE_READY)) {
767  // There is no CANDIDATE announcement tracked for this peer, so
768  // we have nothing to do. Either this invid wasn't tracked at
769  // all (and the caller should have called ReceivedInv), or it
770  // was already requested and/or completed for other reasons and
771  // this is just a superfluous RequestedData call.
772  return;
773  }
774 
775  // Look for an existing CANDIDATE_BEST or REQUESTED with the same
776  // invid. We only need to do this if the found announcement had a
777  // different state than CANDIDATE_BEST. If it did, invariants
778  // guarantee that no other CANDIDATE_BEST or REQUESTED can exist.
779  auto it_old = m_index.get<ByInvId>().lower_bound(
780  ByInvIdView{invid, State::CANDIDATE_BEST, 0});
781  if (it_old != m_index.get<ByInvId>().end() &&
782  it_old->m_invid == invid) {
783  if (it_old->GetState() == State::CANDIDATE_BEST) {
784  // The data structure's invariants require that there can be
785  // at most one CANDIDATE_BEST or one REQUESTED announcement
786  // per invid (but not both simultaneously), so we have to
787  // convert any existing CANDIDATE_BEST to another
788  // CANDIDATE_* when constructing another REQUESTED. It
789  // doesn't matter whether we pick CANDIDATE_READY or
790  // _DELAYED here, as SetTimePoint() will correct it at
791  // GetRequestable() time. If time only goes forward, it will
792  // always be _READY, so pick that to avoid extra work in
793  // SetTimePoint().
794  Modify<ByInvId>(it_old, [](Announcement &ann) {
795  ann.SetState(State::CANDIDATE_READY);
796  });
797  } else if (it_old->GetState() == State::REQUESTED) {
798  // As we're no longer waiting for a response to the previous
799  // REQUESTED announcement, convert it to COMPLETED. This
800  // also helps guaranteeing progress.
801  Modify<ByInvId>(it_old, [](Announcement &ann) {
802  ann.SetState(State::COMPLETED);
803  });
804  }
805  }
806  }
807 
808  Modify<ByPeer>(it, [expiry](Announcement &ann) {
809  ann.SetState(State::REQUESTED);
810  ann.m_time = expiry;
811  });
812  }
813 
814  void ReceivedResponse(NodeId peer, const uint256 &invid) {
815  // We need to search the ByPeer index for both (peer, false, invid) and
816  // (peer, true, invid).
817  auto it = m_index.get<ByPeer>().find(ByPeerView{peer, false, invid});
818  if (it == m_index.get<ByPeer>().end()) {
819  it = m_index.get<ByPeer>().find(ByPeerView{peer, true, invid});
820  }
821  if (it != m_index.get<ByPeer>().end()) {
822  MakeCompleted(m_index.project<ByInvId>(it));
823  }
824  }
825 
826  size_t CountInFlight(NodeId peer) const {
827  auto it = m_peerinfo.find(peer);
828  if (it != m_peerinfo.end()) {
829  return it->second.m_requested;
830  }
831  return 0;
832  }
833 
834  size_t CountCandidates(NodeId peer) const {
835  auto it = m_peerinfo.find(peer);
836  if (it != m_peerinfo.end()) {
837  return it->second.m_total - it->second.m_requested -
838  it->second.m_completed;
839  }
840  return 0;
841  }
842 
843  size_t Count(NodeId peer) const {
844  auto it = m_peerinfo.find(peer);
845  if (it != m_peerinfo.end()) {
846  return it->second.m_total;
847  }
848  return 0;
849  }
850 
853  size_t Size() const { return m_index.size(); }
854 
855  uint64_t ComputePriority(const uint256 &invid, NodeId peer,
856  bool preferred) const {
857  // Return Priority as a uint64_t as Priority is internal.
858  return uint64_t{m_computer(invid, peer, preferred)};
859  }
860 };
861 
862 std::unique_ptr<InvRequestTrackerImplInterface>
864  return std::make_unique<InvRequestTrackerImpl>(deterministic);
865 }
InvRequestTrackerImpl::m_computer
const PriorityComputer m_computer
This tracker's priority computer.
Definition: invrequest.cpp:362
InvRequestTrackerImpl::PromoteCandidateReady
void PromoteCandidateReady(Iter< ByInvId > it)
Convert a CANDIDATE_DELAYED announcement into a CANDIDATE_READY.
Definition: invrequest.cpp:458
InvRequestTrackerImpl::MakeCompleted
bool MakeCompleted(Iter< ByInvId > it)
Convert any announcement to a COMPLETED one.
Definition: invrequest.cpp:553
InvRequestTrackerImpl::CountCandidates
size_t CountCandidates(NodeId peer) const
Definition: invrequest.cpp:834
InvRequestTrackerImpl::DisconnectedPeer
void DisconnectedPeer(NodeId peer)
Definition: invrequest.cpp:641
InvRequestTrackerImpl::SetTimePoint
void SetTimePoint(std::chrono::microseconds now, ClearExpiredFun clearExpired, EmplaceExpiredFun emplaceExpired)
Make the data structure consistent with a given point in time:
Definition: invrequest.cpp:585
InvRequestTrackerImpl::ForgetInvId
void ForgetInvId(const uint256 &invid)
Definition: invrequest.cpp:683
InvRequestTrackerImpl::CountInFlight
size_t CountInFlight(NodeId peer) const
Definition: invrequest.cpp:826
InvRequestTrackerImpl::Size
size_t Size() const
Count how many announcements are being tracked in total across all peers and transactions.
Definition: invrequest.cpp:853
InvRequestTrackerImpl::GetRequestable
std::vector< uint256 > GetRequestable(NodeId peer, std::chrono::microseconds now, ClearExpiredFun clearExpired, EmplaceExpiredFun emplaceExpired)
Find the InvIds to request now from peer.
Definition: invrequest.cpp:718
InvRequestTrackerImpl::InvRequestTrackerImpl
InvRequestTrackerImpl(bool deterministic)
Definition: invrequest.cpp:623
InvRequestTrackerImpl::RequestedData
void RequestedData(NodeId peer, const uint256 &invid, std::chrono::microseconds expiry)
Definition: invrequest.cpp:751
invrequest.h
InvRequestTrackerImpl::ReceivedInv
void ReceivedInv(NodeId peer, const uint256 &invid, bool preferred, std::chrono::microseconds reqtime)
Definition: invrequest.cpp:691
GetRand
uint64_t GetRand(uint64_t nMax) noexcept
Generate a uniform random integer in the range [0..range).
Definition: random.cpp:650
CSipHasher
SipHash-2-4.
Definition: siphash.h:13
siphash.h
random.h
InvRequestTrackerImpl::operator=
InvRequestTrackerImpl & operator=(const InvRequestTrackerImpl &)=delete
CSipHasher::Finalize
uint64_t Finalize() const
Compute the 64-bit SipHash-2-4 of the data written so far.
Definition: siphash.cpp:82
InvRequestTrackerImpl::ComputePriority
uint64_t ComputePriority(const uint256 &invid, NodeId peer, bool preferred) const
Definition: invrequest.cpp:855
InvRequestTrackerImpl::Count
size_t Count(NodeId peer) const
Definition: invrequest.cpp:843
InvRequestTrackerImpl::m_index
Index m_index
This tracker's main data structure.
Definition: invrequest.cpp:366
uint256::ZERO
static const uint256 ZERO
Definition: uint256.h:132
InvRequestTrackerImpl::PostGetRequestableSanityCheck
void PostGetRequestableSanityCheck(std::chrono::microseconds now) const
Definition: invrequest.cpp:414
uint256
256-bit opaque blob.
Definition: uint256.h:127
InvRequestTrackerImpl::m_peerinfo
std::unordered_map< NodeId, PeerInfo > m_peerinfo
Map with this tracker's per-peer statistics.
Definition: invrequest.cpp:369
operator==
bool operator==(const CNetAddr &a, const CNetAddr &b)
Definition: netaddress.cpp:604
base_blob::begin
uint8_t * begin()
Definition: uint256.h:83
InvRequestTrackerImplInterface::EmplaceExpiredFun
const std::function< void(const NodeId &, const uint256 &)> & EmplaceExpiredFun
Definition: invrequest.h:133
InvRequestTrackerImpl::~InvRequestTrackerImpl
~InvRequestTrackerImpl()=default
InvRequestTrackerImpl::Modify
void Modify(Iter< Tag > it, Modifier modifier)
Wrapper around Index::...::modify that keeps m_peerinfo up to date.
Definition: invrequest.cpp:445
InvRequestTrackerImplInterface::ClearExpiredFun
const std::function< void()> & ClearExpiredFun
Definition: invrequest.h:131
InvRequestTrackerImplInterface::BuildImpl
static std::unique_ptr< InvRequestTrackerImplInterface > BuildImpl(bool deterministic)
Definition: invrequest.cpp:863
InvRequestTrackerImpl::m_current_sequence
SequenceNumber m_current_sequence
The current sequence number.
Definition: invrequest.cpp:359
InvRequestTrackerImpl::SanityCheck
void SanityCheck() const
Definition: invrequest.cpp:372
InvRequestTrackerImpl::IsOnlyNonCompleted
bool IsOnlyNonCompleted(Iter< ByInvId > it)
Check if 'it' is the only announcement for a given invid that isn't COMPLETED.
Definition: invrequest.cpp:522
NodeId
int64_t NodeId
Definition: nodeid.h:10
InvRequestTrackerImpl::ReceivedResponse
void ReceivedResponse(NodeId peer, const uint256 &invid)
Definition: invrequest.cpp:814
net.h
base_blob::size
unsigned int size() const
Definition: uint256.h:91
InvRequestTrackerImpl::ChangeAndReselect
void ChangeAndReselect(Iter< ByInvId > it, State new_state)
Change the state of an announcement to something non-IsSelected().
Definition: invrequest.cpp:499
InvRequestTrackerImplInterface
Data structure to keep track of, and schedule, inventory downloads from peers.
Definition: invrequest.h:121
InvRequestTrackerImpl
Actual implementation for InvRequestTracker's data structure.
Definition: invrequest.cpp:356
InvRequestTrackerImpl::Erase
Iter< Tag > Erase(Iter< Tag > it)
Wrapper around Index::...::erase that keeps m_peerinfo up to date.
Definition: invrequest.cpp:433
CSipHasher::Write
CSipHasher & Write(uint64_t data)
Hash a 64-bit integer worth of data.
Definition: siphash.cpp:36