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