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