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