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