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