1 // Copyright (c) 2020-present 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>
9 #include <primitives/transaction.h>
10 #include <random.h>
11 #include <uint256.h>
12 13 #include <boost/multi_index/indexed_by.hpp>
14 #include <boost/multi_index/ordered_index.hpp>
15 #include <boost/multi_index/sequenced_index.hpp>
16 #include <boost/multi_index/tag.hpp>
17 #include <boost/multi_index_container.hpp>
18 #include <boost/tuple/tuple.hpp>
19 20 #include <chrono>
21 #include <unordered_map>
22 #include <utility>
23 24 #include <cassert>
25 26 namespace {
27 28 /** The various states a (txhash,peer) pair can be in.
29 *
30 * Note that CANDIDATE is split up into 3 substates (DELAYED, BEST, READY), allowing more efficient implementation.
31 * Also note that the sorting order of ByTxHashView relies on the specific order of values in this enum.
32 *
33 * Expected behaviour is:
34 * - When first announced by a peer, the state is CANDIDATE_DELAYED until reqtime is reached.
35 * - Announcements that have reached their reqtime but not been requested will be either CANDIDATE_READY or
36 * CANDIDATE_BEST. Neither of those has an expiration time; they remain in that state until they're requested or
37 * no longer needed. CANDIDATE_READY announcements are promoted to CANDIDATE_BEST when they're the best one left.
38 * - When requested, an announcement will be in state REQUESTED until expiry is reached.
39 * - If expiry is reached, or the peer replies to the request (either with NOTFOUND or the tx), the state becomes
40 * COMPLETED.
41 */
42 enum class State : uint8_t {
43 /** A CANDIDATE announcement whose reqtime is in the future. */
44 CANDIDATE_DELAYED,
45 /** A CANDIDATE announcement that's not CANDIDATE_DELAYED or CANDIDATE_BEST. */
46 CANDIDATE_READY,
47 /** The best CANDIDATE for a given txhash; only if there is no REQUESTED announcement already for that txhash.
48 * The CANDIDATE_BEST is the highest-priority announcement among all CANDIDATE_READY (and _BEST) ones for that
49 * txhash. */
50 CANDIDATE_BEST,
51 /** A REQUESTED announcement. */
52 REQUESTED,
53 /** A COMPLETED announcement. */
54 COMPLETED,
55 };
56 57 //! Type alias for sequence numbers.
58 using SequenceNumber = uint64_t;
59 60 /** An announcement. This is the data we track for each txid or wtxid that is announced to us by each peer. */
61 struct Announcement {
62 /** Txid or wtxid that was announced. */
63 const GenTxid m_gtxid;
64 /** For CANDIDATE_{DELAYED,BEST,READY} the reqtime; for REQUESTED the expiry. */
65 std::chrono::microseconds m_time;
66 /** What peer the request was from. */
67 const NodeId m_peer;
68 /** What sequence number this announcement has. */
69 const SequenceNumber m_sequence : 59;
70 /** Whether the request is preferred. */
71 const bool m_preferred : 1;
72 /** What state this announcement is in. */
73 State m_state : 3 {State::CANDIDATE_DELAYED};
74 State GetState() const { return m_state; }
75 void SetState(State state) { m_state = state; }
76 77 /** Whether this announcement is selected. There can be at most 1 selected peer per txhash. */
78 bool IsSelected() const
79 {
80 return GetState() == State::CANDIDATE_BEST || GetState() == State::REQUESTED;
81 }
82 83 /** Whether this announcement is waiting for a certain time to pass. */
84 bool IsWaiting() const
85 {
86 return GetState() == State::REQUESTED || GetState() == State::CANDIDATE_DELAYED;
87 }
88 89 /** Whether this announcement can feasibly be selected if the current IsSelected() one disappears. */
90 bool IsSelectable() const
91 {
92 return GetState() == State::CANDIDATE_READY || GetState() == State::CANDIDATE_BEST;
93 }
94 95 /** Construct a new announcement from scratch, initially in CANDIDATE_DELAYED state. */
96 Announcement(const GenTxid& gtxid, NodeId peer, bool preferred, std::chrono::microseconds reqtime,
97 SequenceNumber sequence)
98 : m_gtxid(gtxid), m_time(reqtime), m_peer(peer), m_sequence(sequence), m_preferred(preferred) {}
99 };
100 101 //! Type alias for priorities.
102 using Priority = uint64_t;
103 104 /** A functor with embedded salt that computes priority of an announcement.
105 *
106 * Higher priorities are selected first.
107 */
108 class PriorityComputer {
109 const uint64_t m_k0, m_k1;
110 public:
111 explicit PriorityComputer(bool deterministic) :
112 m_k0{deterministic ? 0 : FastRandomContext().rand64()},
113 m_k1{deterministic ? 0 : FastRandomContext().rand64()} {}
114 115 Priority operator()(const uint256& txhash, NodeId peer, bool preferred) const
116 {
117 uint64_t low_bits = CSipHasher(m_k0, m_k1).Write(txhash).Write(peer).Finalize() >> 1;
118 return low_bits | uint64_t{preferred} << 63;
119 }
120 121 Priority operator()(const Announcement& ann) const
122 {
123 return operator()(ann.m_gtxid.ToUint256(), ann.m_peer, ann.m_preferred);
124 }
125 };
126 127 // Definitions for the 3 indexes used in the main data structure.
128 //
129 // Each index has a By* type to identify it, a By*View data type to represent the view of announcement it is sorted
130 // by, and an By*ViewExtractor type to convert an announcement into the By*View type.
131 // See https://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/reference/key_extraction.html#key_extractors
132 // for more information about the key extraction concept.
133 134 // The ByPeer index is sorted by (peer, state == CANDIDATE_BEST, txhash)
135 //
136 // Uses:
137 // * Looking up existing announcements by peer/txhash, by checking both (peer, false, txhash) and
138 // (peer, true, txhash).
139 // * Finding all CANDIDATE_BEST announcements for a given peer in GetRequestable.
140 struct ByPeer {};
141 using ByPeerView = std::tuple<NodeId, bool, const uint256&>;
142 struct ByPeerViewExtractor
143 {
144 using result_type = ByPeerView;
145 result_type operator()(const Announcement& ann) const
146 {
147 return ByPeerView{ann.m_peer, ann.GetState() == State::CANDIDATE_BEST, ann.m_gtxid.ToUint256()};
148 }
149 };
150 151 // The ByTxHash index is sorted by (txhash, state, priority).
152 //
153 // Note: priority == 0 whenever state != CANDIDATE_READY.
154 //
155 // Uses:
156 // * Deleting all announcements with a given txhash in ForgetTxHash.
157 // * Finding the best CANDIDATE_READY to convert to CANDIDATE_BEST, when no other CANDIDATE_READY or REQUESTED
158 // announcement exists for that txhash.
159 // * Determining when no more non-COMPLETED announcements for a given txhash exist, so the COMPLETED ones can be
160 // deleted.
161 struct ByTxHash {};
162 using ByTxHashView = std::tuple<const uint256&, State, Priority>;
163 class ByTxHashViewExtractor {
164 const PriorityComputer& m_computer;
165 public:
166 explicit ByTxHashViewExtractor(const PriorityComputer& computer) : m_computer(computer) {}
167 using result_type = ByTxHashView;
168 result_type operator()(const Announcement& ann) const
169 {
170 const Priority prio = (ann.GetState() == State::CANDIDATE_READY) ? m_computer(ann) : 0;
171 return ByTxHashView{ann.m_gtxid.ToUint256(), ann.GetState(), prio};
172 }
173 };
174 175 enum class WaitState {
176 //! Used for announcements that need efficient testing of "is their timestamp in the future?".
177 FUTURE_EVENT,
178 //! Used for announcements whose timestamp is not relevant.
179 NO_EVENT,
180 //! Used for announcements that need efficient testing of "is their timestamp in the past?".
181 PAST_EVENT,
182 };
183 184 WaitState GetWaitState(const Announcement& ann)
185 {
186 if (ann.IsWaiting()) return WaitState::FUTURE_EVENT;
187 if (ann.IsSelectable()) return WaitState::PAST_EVENT;
188 return WaitState::NO_EVENT;
189 }
190 191 // The ByTime index is sorted by (wait_state, time).
192 //
193 // All announcements with a timestamp in the future can be found by iterating the index forward from the beginning.
194 // All announcements with a timestamp in the past can be found by iterating the index backwards from the end.
195 //
196 // Uses:
197 // * Finding CANDIDATE_DELAYED announcements whose reqtime has passed, and REQUESTED announcements whose expiry has
198 // passed.
199 // * Finding CANDIDATE_READY/BEST announcements whose reqtime is in the future (when the clock time went backwards).
200 struct ByTime {};
201 using ByTimeView = std::pair<WaitState, std::chrono::microseconds>;
202 struct ByTimeViewExtractor
203 {
204 using result_type = ByTimeView;
205 result_type operator()(const Announcement& ann) const
206 {
207 return ByTimeView{GetWaitState(ann), ann.m_time};
208 }
209 };
210 211 212 /** Data type for the main data structure (Announcement objects with ByPeer/ByTxHash/ByTime indexes). */
213 using Index = boost::multi_index_container<
214 Announcement,
215 boost::multi_index::indexed_by<
216 boost::multi_index::ordered_unique<boost::multi_index::tag<ByPeer>, ByPeerViewExtractor>,
217 boost::multi_index::ordered_non_unique<boost::multi_index::tag<ByTxHash>, ByTxHashViewExtractor>,
218 boost::multi_index::ordered_non_unique<boost::multi_index::tag<ByTime>, ByTimeViewExtractor>
219 >
220 >;
221 222 /** Helper type to simplify syntax of iterator types. */
223 template<typename Tag>
224 using Iter = typename Index::index<Tag>::type::iterator;
225 226 /** Per-peer statistics object. */
227 struct PeerInfo {
228 size_t m_total = 0; //!< Total number of announcements for this peer.
229 size_t m_completed = 0; //!< Number of COMPLETED announcements for this peer.
230 size_t m_requested = 0; //!< Number of REQUESTED announcements for this peer.
231 };
232 233 /** Per-txhash statistics object. Only used for sanity checking. */
234 struct TxHashInfo
235 {
236 //! Number of CANDIDATE_DELAYED announcements for this txhash.
237 size_t m_candidate_delayed = 0;
238 //! Number of CANDIDATE_READY announcements for this txhash.
239 size_t m_candidate_ready = 0;
240 //! Number of CANDIDATE_BEST announcements for this txhash (at most one).
241 size_t m_candidate_best = 0;
242 //! Number of REQUESTED announcements for this txhash (at most one; mutually exclusive with CANDIDATE_BEST).
243 size_t m_requested = 0;
244 //! The priority of the CANDIDATE_BEST announcement if one exists, or max() otherwise.
245 Priority m_priority_candidate_best = std::numeric_limits<Priority>::max();
246 //! The highest priority of all CANDIDATE_READY announcements (or min() if none exist).
247 Priority m_priority_best_candidate_ready = std::numeric_limits<Priority>::min();
248 //! All peers we have an announcement for this txhash for.
249 std::vector<NodeId> m_peers;
250 };
251 252 /** Compare two PeerInfo objects. Only used for sanity checking. */
253 bool operator==(const PeerInfo& a, const PeerInfo& b)
254 {
255 return std::tie(a.m_total, a.m_completed, a.m_requested) ==
256 std::tie(b.m_total, b.m_completed, b.m_requested);
257 };
258 259 /** (Re)compute the PeerInfo map from the index. Only used for sanity checking. */
260 std::unordered_map<NodeId, PeerInfo> RecomputePeerInfo(const Index& index)
261 {
262 std::unordered_map<NodeId, PeerInfo> ret;
263 for (const Announcement& ann : index) {
264 PeerInfo& info = ret[ann.m_peer];
265 ++info.m_total;
266 info.m_requested += (ann.GetState() == State::REQUESTED);
267 info.m_completed += (ann.GetState() == State::COMPLETED);
268 }
269 return ret;
270 }
271 272 /** Compute the TxHashInfo map. Only used for sanity checking. */
273 std::map<uint256, TxHashInfo> ComputeTxHashInfo(const Index& index, const PriorityComputer& computer)
274 {
275 std::map<uint256, TxHashInfo> ret;
276 for (const Announcement& ann : index) {
277 TxHashInfo& info = ret[ann.m_gtxid.ToUint256()];
278 // Classify how many announcements of each state we have for this txhash.
279 info.m_candidate_delayed += (ann.GetState() == State::CANDIDATE_DELAYED);
280 info.m_candidate_ready += (ann.GetState() == State::CANDIDATE_READY);
281 info.m_candidate_best += (ann.GetState() == State::CANDIDATE_BEST);
282 info.m_requested += (ann.GetState() == State::REQUESTED);
283 // And track the priority of the best CANDIDATE_READY/CANDIDATE_BEST announcements.
284 if (ann.GetState() == State::CANDIDATE_BEST) {
285 info.m_priority_candidate_best = computer(ann);
286 }
287 if (ann.GetState() == State::CANDIDATE_READY) {
288 info.m_priority_best_candidate_ready = std::max(info.m_priority_best_candidate_ready, computer(ann));
289 }
290 // Also keep track of which peers this txhash has an announcement for (so we can detect duplicates).
291 info.m_peers.push_back(ann.m_peer);
292 }
293 return ret;
294 }
295 296 } // namespace
297 298 /** Actual implementation for TxRequestTracker's data structure. */
299 class TxRequestTracker::Impl {
300 //! The current sequence number. Increases for every announcement. This is used to sort txhashes returned by
301 //! GetRequestable in announcement order.
302 SequenceNumber m_current_sequence{0};
303 304 //! This tracker's priority computer.
305 const PriorityComputer m_computer;
306 307 //! This tracker's main data structure. See SanityCheck() for the invariants that apply to it.
308 Index m_index;
309 310 //! Map with this tracker's per-peer statistics.
311 std::unordered_map<NodeId, PeerInfo> m_peerinfo;
312 313 public:
314 void SanityCheck() const
315 {
316 // Recompute m_peerdata from m_index. This verifies the data in it as it should just be caching statistics
317 // on m_index. It also verifies the invariant that no PeerInfo announcements with m_total==0 exist.
318 assert(m_peerinfo == RecomputePeerInfo(m_index));
319 320 // Calculate per-txhash statistics from m_index, and validate invariants.
321 for (auto& item : ComputeTxHashInfo(m_index, m_computer)) {
322 TxHashInfo& info = item.second;
323 324 // Cannot have only COMPLETED peer (txhash should have been forgotten already)
325 assert(info.m_candidate_delayed + info.m_candidate_ready + info.m_candidate_best + info.m_requested > 0);
326 327 // Can have at most 1 CANDIDATE_BEST/REQUESTED peer
328 assert(info.m_candidate_best + info.m_requested <= 1);
329 330 // If there are any CANDIDATE_READY announcements, there must be exactly one CANDIDATE_BEST or REQUESTED
331 // announcement.
332 if (info.m_candidate_ready > 0) {
333 assert(info.m_candidate_best + info.m_requested == 1);
334 }
335 336 // If there is both a CANDIDATE_READY and a CANDIDATE_BEST announcement, the CANDIDATE_BEST one must be
337 // at least as good (equal or higher priority) as the best CANDIDATE_READY.
338 if (info.m_candidate_ready && info.m_candidate_best) {
339 assert(info.m_priority_candidate_best >= info.m_priority_best_candidate_ready);
340 }
341 342 // No txhash can have been announced by the same peer twice.
343 std::sort(info.m_peers.begin(), info.m_peers.end());
344 assert(std::adjacent_find(info.m_peers.begin(), info.m_peers.end()) == info.m_peers.end());
345 }
346 }
347 348 void PostGetRequestableSanityCheck(std::chrono::microseconds now) const
349 {
350 for (const Announcement& ann : m_index) {
351 if (ann.IsWaiting()) {
352 // REQUESTED and CANDIDATE_DELAYED must have a time in the future (they should have been converted
353 // to COMPLETED/CANDIDATE_READY respectively).
354 assert(ann.m_time > now);
355 } else if (ann.IsSelectable()) {
356 // CANDIDATE_READY and CANDIDATE_BEST cannot have a time in the future (they should have remained
357 // CANDIDATE_DELAYED, or should have been converted back to it if time went backwards).
358 assert(ann.m_time <= now);
359 }
360 }
361 }
362 363 private:
364 //! Wrapper around Index::...::erase that keeps m_peerinfo up to date.
365 template<typename Tag>
366 Iter<Tag> Erase(Iter<Tag> it)
367 {
368 auto peerit = m_peerinfo.find(it->m_peer);
369 peerit->second.m_completed -= it->GetState() == State::COMPLETED;
370 peerit->second.m_requested -= it->GetState() == State::REQUESTED;
371 if (--peerit->second.m_total == 0) m_peerinfo.erase(peerit);
372 return m_index.get<Tag>().erase(it);
373 }
374 375 //! Wrapper around Index::...::modify that keeps m_peerinfo up to date.
376 template<typename Tag, typename Modifier>
377 void Modify(Iter<Tag> it, Modifier modifier)
378 {
379 auto peerit = m_peerinfo.find(it->m_peer);
380 peerit->second.m_completed -= it->GetState() == State::COMPLETED;
381 peerit->second.m_requested -= it->GetState() == State::REQUESTED;
382 m_index.get<Tag>().modify(it, std::move(modifier));
383 peerit->second.m_completed += it->GetState() == State::COMPLETED;
384 peerit->second.m_requested += it->GetState() == State::REQUESTED;
385 }
386 387 //! Convert a CANDIDATE_DELAYED announcement into a CANDIDATE_READY. If this makes it the new best
388 //! CANDIDATE_READY (and no REQUESTED exists) and better than the CANDIDATE_BEST (if any), it becomes the new
389 //! CANDIDATE_BEST.
390 void PromoteCandidateReady(Iter<ByTxHash> it)
391 {
392 assert(it != m_index.get<ByTxHash>().end());
393 assert(it->GetState() == State::CANDIDATE_DELAYED);
394 // Convert CANDIDATE_DELAYED to CANDIDATE_READY first.
395 Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_READY); });
396 // The following code relies on the fact that the ByTxHash is sorted by txhash, and then by state (first
397 // _DELAYED, then _READY, then _BEST/REQUESTED). Within the _READY announcements, the best one (highest
398 // priority) comes last. Thus, if an existing _BEST exists for the same txhash that this announcement may
399 // be preferred over, it must immediately follow the newly created _READY.
400 auto it_next = std::next(it);
401 if (it_next == m_index.get<ByTxHash>().end() || it_next->m_gtxid.ToUint256() != it->m_gtxid.ToUint256() ||
402 it_next->GetState() == State::COMPLETED) {
403 // This is the new best CANDIDATE_READY, and there is no IsSelected() announcement for this txhash
404 // already.
405 Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); });
406 } else if (it_next->GetState() == State::CANDIDATE_BEST) {
407 Priority priority_old = m_computer(*it_next);
408 Priority priority_new = m_computer(*it);
409 if (priority_new > priority_old) {
410 // There is a CANDIDATE_BEST announcement already, but this one is better.
411 Modify<ByTxHash>(it_next, [](Announcement& ann){ ann.SetState(State::CANDIDATE_READY); });
412 Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); });
413 }
414 }
415 }
416 417 //! Change the state of an announcement to something non-IsSelected(). If it was IsSelected(), the next best
418 //! announcement will be marked CANDIDATE_BEST.
419 void ChangeAndReselect(Iter<ByTxHash> it, State new_state)
420 {
421 assert(new_state == State::COMPLETED || new_state == State::CANDIDATE_DELAYED);
422 assert(it != m_index.get<ByTxHash>().end());
423 if (it->IsSelected() && it != m_index.get<ByTxHash>().begin()) {
424 auto it_prev = std::prev(it);
425 // The next best CANDIDATE_READY, if any, immediately precedes the REQUESTED or CANDIDATE_BEST
426 // announcement in the ByTxHash index.
427 if (it_prev->m_gtxid.ToUint256() == it->m_gtxid.ToUint256() && it_prev->GetState() == State::CANDIDATE_READY) {
428 // If one such CANDIDATE_READY exists (for this txhash), convert it to CANDIDATE_BEST.
429 Modify<ByTxHash>(it_prev, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); });
430 }
431 }
432 Modify<ByTxHash>(it, [new_state](Announcement& ann){ ann.SetState(new_state); });
433 }
434 435 //! Check if 'it' is the only announcement for a given txhash that isn't COMPLETED.
436 bool IsOnlyNonCompleted(Iter<ByTxHash> it)
437 {
438 assert(it != m_index.get<ByTxHash>().end());
439 assert(it->GetState() != State::COMPLETED); // Not allowed to call this on COMPLETED announcements.
440 441 // This announcement has a predecessor that belongs to the same txhash. Due to ordering, and the
442 // fact that 'it' is not COMPLETED, its predecessor cannot be COMPLETED here.
443 if (it != m_index.get<ByTxHash>().begin() && std::prev(it)->m_gtxid.ToUint256() == it->m_gtxid.ToUint256()) return false;
444 445 // This announcement has a successor that belongs to the same txhash, and is not COMPLETED.
446 if (std::next(it) != m_index.get<ByTxHash>().end() && std::next(it)->m_gtxid.ToUint256() == it->m_gtxid.ToUint256() &&
447 std::next(it)->GetState() != State::COMPLETED) return false;
448 449 return true;
450 }
451 452 /** Convert any announcement to a COMPLETED one. If there are no non-COMPLETED announcements left for this
453 * txhash, they are deleted. If this was a REQUESTED announcement, and there are other CANDIDATEs left, the
454 * best one is made CANDIDATE_BEST. Returns whether the announcement still exists. */
455 bool MakeCompleted(Iter<ByTxHash> it)
456 {
457 assert(it != m_index.get<ByTxHash>().end());
458 459 // Nothing to be done if it's already COMPLETED.
460 if (it->GetState() == State::COMPLETED) return true;
461 462 if (IsOnlyNonCompleted(it)) {
463 // This is the last non-COMPLETED announcement for this txhash. Delete all.
464 uint256 txhash = it->m_gtxid.ToUint256();
465 do {
466 it = Erase<ByTxHash>(it);
467 } while (it != m_index.get<ByTxHash>().end() && it->m_gtxid.ToUint256() == txhash);
468 return false;
469 }
470 471 // Mark the announcement COMPLETED, and select the next best announcement (the first CANDIDATE_READY) if
472 // needed.
473 ChangeAndReselect(it, State::COMPLETED);
474 475 return true;
476 }
477 478 //! Make the data structure consistent with a given point in time:
479 //! - REQUESTED announcements with expiry <= now are turned into COMPLETED.
480 //! - CANDIDATE_DELAYED announcements with reqtime <= now are turned into CANDIDATE_{READY,BEST}.
481 //! - CANDIDATE_{READY,BEST} announcements with reqtime > now are turned into CANDIDATE_DELAYED.
482 void SetTimePoint(std::chrono::microseconds now, std::vector<std::pair<NodeId, GenTxid>>* expired)
483 {
484 if (expired) expired->clear();
485 486 // Iterate over all CANDIDATE_DELAYED and REQUESTED from old to new, as long as they're in the past,
487 // and convert them to CANDIDATE_READY and COMPLETED respectively.
488 while (!m_index.empty()) {
489 auto it = m_index.get<ByTime>().begin();
490 if (it->GetState() == State::CANDIDATE_DELAYED && it->m_time <= now) {
491 PromoteCandidateReady(m_index.project<ByTxHash>(it));
492 } else if (it->GetState() == State::REQUESTED && it->m_time <= now) {
493 if (expired) expired->emplace_back(it->m_peer, it->m_gtxid);
494 MakeCompleted(m_index.project<ByTxHash>(it));
495 } else {
496 break;
497 }
498 }
499 500 while (!m_index.empty()) {
501 // If time went backwards, we may need to demote CANDIDATE_BEST and CANDIDATE_READY announcements back
502 // to CANDIDATE_DELAYED. This is an unusual edge case, and unlikely to matter in production. However,
503 // it makes it much easier to specify and test TxRequestTracker::Impl's behaviour.
504 auto it = std::prev(m_index.get<ByTime>().end());
505 if (it->IsSelectable() && it->m_time > now) {
506 ChangeAndReselect(m_index.project<ByTxHash>(it), State::CANDIDATE_DELAYED);
507 } else {
508 break;
509 }
510 }
511 }
512 513 public:
514 explicit Impl(bool deterministic) :
515 m_computer(deterministic),
516 // Explicitly initialize m_index as we need to pass a reference to m_computer to ByTxHashViewExtractor.
517 m_index(boost::make_tuple(
518 boost::make_tuple(ByPeerViewExtractor(), std::less<ByPeerView>()),
519 boost::make_tuple(ByTxHashViewExtractor(m_computer), std::less<ByTxHashView>()),
520 boost::make_tuple(ByTimeViewExtractor(), std::less<ByTimeView>())
521 )) {}
522 523 // Disable copying and assigning (a default copy won't work due the stateful ByTxHashViewExtractor).
524 Impl(const Impl&) = delete;
525 Impl& operator=(const Impl&) = delete;
526 527 void DisconnectedPeer(NodeId peer)
528 {
529 auto& index = m_index.get<ByPeer>();
530 auto it = index.lower_bound(ByPeerView{peer, false, uint256::ZERO});
531 while (it != index.end() && it->m_peer == peer) {
532 // Check what to continue with after this iteration. 'it' will be deleted in what follows, so we need to
533 // decide what to continue with afterwards. There are a number of cases to consider:
534 // - std::next(it) is end() or belongs to a different peer. In that case, this is the last iteration
535 // of the loop (denote this by setting it_next to end()).
536 // - 'it' is not the only non-COMPLETED announcement for its txhash. This means it will be deleted, but
537 // no other Announcement objects will be modified. Continue with std::next(it) if it belongs to the
538 // same peer, but decide this ahead of time (as 'it' may change position in what follows).
539 // - 'it' is the only non-COMPLETED announcement for its txhash. This means it will be deleted along
540 // with all other announcements for the same txhash - which may include std::next(it). However, other
541 // than 'it', no announcements for the same peer can be affected (due to (peer, txhash) uniqueness).
542 // In other words, the situation where std::next(it) is deleted can only occur if std::next(it)
543 // belongs to a different peer but the same txhash as 'it'. This is covered by the first bulletpoint
544 // already, and we'll have set it_next to end().
545 auto it_next = (std::next(it) == index.end() || std::next(it)->m_peer != peer) ? index.end() :
546 std::next(it);
547 // If the announcement isn't already COMPLETED, first make it COMPLETED (which will mark other
548 // CANDIDATEs as CANDIDATE_BEST, or delete all of a txhash's announcements if no non-COMPLETED ones are
549 // left).
550 if (MakeCompleted(m_index.project<ByTxHash>(it))) {
551 // Then actually delete the announcement (unless it was already deleted by MakeCompleted).
552 Erase<ByPeer>(it);
553 }
554 it = it_next;
555 }
556 }
557 558 void ForgetTxHash(const uint256& txhash)
559 {
560 auto it = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_DELAYED, 0});
561 while (it != m_index.get<ByTxHash>().end() && it->m_gtxid.ToUint256() == txhash) {
562 it = Erase<ByTxHash>(it);
563 }
564 }
565 566 void GetCandidatePeers(const uint256& txhash, std::vector<NodeId>& result_peers) const
567 {
568 auto it = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_DELAYED, 0});
569 while (it != m_index.get<ByTxHash>().end() && it->m_gtxid.ToUint256() == txhash && it->GetState() != State::COMPLETED) {
570 result_peers.push_back(it->m_peer);
571 ++it;
572 }
573 }
574 575 void ReceivedInv(NodeId peer, const GenTxid& gtxid, bool preferred,
576 std::chrono::microseconds reqtime)
577 {
578 // Bail out if we already have a CANDIDATE_BEST announcement for this (txhash, peer) combination. The case
579 // where there is a non-CANDIDATE_BEST announcement already will be caught by the uniqueness property of the
580 // ByPeer index when we try to emplace the new object below.
581 if (m_index.get<ByPeer>().count(ByPeerView{peer, true, gtxid.ToUint256()})) return;
582 583 // Try creating the announcement with CANDIDATE_DELAYED state (which will fail due to the uniqueness
584 // of the ByPeer index if a non-CANDIDATE_BEST announcement already exists with the same txhash and peer).
585 // Bail out in that case.
586 auto ret = m_index.get<ByPeer>().emplace(gtxid, peer, preferred, reqtime, m_current_sequence);
587 if (!ret.second) return;
588 589 // Update accounting metadata.
590 ++m_peerinfo[peer].m_total;
591 ++m_current_sequence;
592 }
593 594 //! Find the GenTxids to request now from peer.
595 std::vector<GenTxid> GetRequestable(NodeId peer, std::chrono::microseconds now,
596 std::vector<std::pair<NodeId, GenTxid>>* expired)
597 {
598 // Move time.
599 SetTimePoint(now, expired);
600 601 // Find all CANDIDATE_BEST announcements for this peer.
602 std::vector<const Announcement*> selected;
603 auto it_peer = m_index.get<ByPeer>().lower_bound(ByPeerView{peer, true, uint256::ZERO});
604 while (it_peer != m_index.get<ByPeer>().end() && it_peer->m_peer == peer &&
605 it_peer->GetState() == State::CANDIDATE_BEST) {
606 selected.emplace_back(&*it_peer);
607 ++it_peer;
608 }
609 610 // Sort by sequence number.
611 std::sort(selected.begin(), selected.end(), [](const Announcement* a, const Announcement* b) {
612 return a->m_sequence < b->m_sequence;
613 });
614 615 // Convert to GenTxid and return.
616 std::vector<GenTxid> ret;
617 ret.reserve(selected.size());
618 std::transform(selected.begin(), selected.end(), std::back_inserter(ret), [](const Announcement* ann) {
619 return ann->m_gtxid;
620 });
621 return ret;
622 }
623 624 void RequestedTx(NodeId peer, const uint256& txhash, std::chrono::microseconds expiry)
625 {
626 auto it = m_index.get<ByPeer>().find(ByPeerView{peer, true, txhash});
627 if (it == m_index.get<ByPeer>().end()) {
628 // There is no CANDIDATE_BEST announcement, look for a _READY or _DELAYED instead. If the caller only
629 // ever invokes RequestedTx with the values returned by GetRequestable, and no other non-const functions
630 // other than ForgetTxHash and GetRequestable in between, this branch will never execute (as txhashes
631 // returned by GetRequestable always correspond to CANDIDATE_BEST announcements).
632 633 it = m_index.get<ByPeer>().find(ByPeerView{peer, false, txhash});
634 if (it == m_index.get<ByPeer>().end() || (it->GetState() != State::CANDIDATE_DELAYED &&
635 it->GetState() != State::CANDIDATE_READY)) {
636 // There is no CANDIDATE announcement tracked for this peer, so we have nothing to do. Either this
637 // txhash wasn't tracked at all (and the caller should have called ReceivedInv), or it was already
638 // requested and/or completed for other reasons and this is just a superfluous RequestedTx call.
639 return;
640 }
641 642 // Look for an existing CANDIDATE_BEST or REQUESTED with the same txhash. We only need to do this if the
643 // found announcement had a different state than CANDIDATE_BEST. If it did, invariants guarantee that no
644 // other CANDIDATE_BEST or REQUESTED can exist.
645 auto it_old = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_BEST, 0});
646 if (it_old != m_index.get<ByTxHash>().end() && it_old->m_gtxid.ToUint256() == txhash) {
647 if (it_old->GetState() == State::CANDIDATE_BEST) {
648 // The data structure's invariants require that there can be at most one CANDIDATE_BEST or one
649 // REQUESTED announcement per txhash (but not both simultaneously), so we have to convert any
650 // existing CANDIDATE_BEST to another CANDIDATE_* when constructing another REQUESTED.
651 // It doesn't matter whether we pick CANDIDATE_READY or _DELAYED here, as SetTimePoint()
652 // will correct it at GetRequestable() time. If time only goes forward, it will always be
653 // _READY, so pick that to avoid extra work in SetTimePoint().
654 Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::CANDIDATE_READY); });
655 } else if (it_old->GetState() == State::REQUESTED) {
656 // As we're no longer waiting for a response to the previous REQUESTED announcement, convert it
657 // to COMPLETED. This also helps guaranteeing progress.
658 Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::COMPLETED); });
659 }
660 }
661 }
662 663 Modify<ByPeer>(it, [expiry](Announcement& ann) {
664 ann.SetState(State::REQUESTED);
665 ann.m_time = expiry;
666 });
667 }
668 669 void ReceivedResponse(NodeId peer, const uint256& txhash)
670 {
671 // We need to search the ByPeer index for both (peer, false, txhash) and (peer, true, txhash).
672 auto it = m_index.get<ByPeer>().find(ByPeerView{peer, false, txhash});
673 if (it == m_index.get<ByPeer>().end()) {
674 it = m_index.get<ByPeer>().find(ByPeerView{peer, true, txhash});
675 }
676 if (it != m_index.get<ByPeer>().end()) MakeCompleted(m_index.project<ByTxHash>(it));
677 }
678 679 size_t CountInFlight(NodeId peer) const
680 {
681 auto it = m_peerinfo.find(peer);
682 if (it != m_peerinfo.end()) return it->second.m_requested;
683 return 0;
684 }
685 686 size_t CountCandidates(NodeId peer) const
687 {
688 auto it = m_peerinfo.find(peer);
689 if (it != m_peerinfo.end()) return it->second.m_total - it->second.m_requested - it->second.m_completed;
690 return 0;
691 }
692 693 size_t Count(NodeId peer) const
694 {
695 auto it = m_peerinfo.find(peer);
696 if (it != m_peerinfo.end()) return it->second.m_total;
697 return 0;
698 }
699 700 //! Count how many announcements are being tracked in total across all peers and transactions.
701 size_t Size() const { return m_index.size(); }
702 703 uint64_t ComputePriority(const uint256& txhash, NodeId peer, bool preferred) const
704 {
705 // Return Priority as a uint64_t as Priority is internal.
706 return uint64_t{m_computer(txhash, peer, preferred)};
707 }
708 709 };
710 711 TxRequestTracker::TxRequestTracker(bool deterministic) :
712 m_impl{std::make_unique<TxRequestTracker::Impl>(deterministic)} {}
713 714 TxRequestTracker::~TxRequestTracker() = default;
715 716 void TxRequestTracker::ForgetTxHash(const uint256& txhash) { m_impl->ForgetTxHash(txhash); }
717 void TxRequestTracker::DisconnectedPeer(NodeId peer) { m_impl->DisconnectedPeer(peer); }
718 size_t TxRequestTracker::CountInFlight(NodeId peer) const { return m_impl->CountInFlight(peer); }
719 size_t TxRequestTracker::CountCandidates(NodeId peer) const { return m_impl->CountCandidates(peer); }
720 size_t TxRequestTracker::Count(NodeId peer) const { return m_impl->Count(peer); }
721 size_t TxRequestTracker::Size() const { return m_impl->Size(); }
722 void TxRequestTracker::GetCandidatePeers(const uint256& txhash, std::vector<NodeId>& result_peers) const { return m_impl->GetCandidatePeers(txhash, result_peers); }
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 741 void TxRequestTracker::ReceivedResponse(NodeId peer, const uint256& txhash)
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 }
756