txrequest.cpp
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 State GetState() const { return m_state; } 78 void SetState(State state) { m_state = state; } 79 80 /** Whether this announcement is selected. There can be at most 1 selected peer per txhash. */ 81 bool IsSelected() const 82 { 83 return GetState() == State::CANDIDATE_BEST || GetState() == State::REQUESTED; 84 } 85 86 /** Whether this announcement is waiting for a certain time to pass. */ 87 bool IsWaiting() const 88 { 89 return GetState() == State::REQUESTED || GetState() == State::CANDIDATE_DELAYED; 90 } 91 92 /** Whether this announcement can feasibly be selected if the current IsSelected() one disappears. */ 93 bool IsSelectable() const 94 { 95 return GetState() == State::CANDIDATE_READY || GetState() == State::CANDIDATE_BEST; 96 } 97 98 /** Construct a new announcement from scratch, initially in CANDIDATE_DELAYED state. */ 99 Announcement(const GenTxid& gtxid, NodeId peer, bool preferred, std::chrono::microseconds reqtime, 100 SequenceNumber sequence) 101 : m_txhash(gtxid.GetHash()), m_time(reqtime), m_peer(peer), m_sequence(sequence), m_preferred(preferred), 102 m_is_wtxid{gtxid.IsWtxid()} {} 103 }; 104 105 //! Type alias for priorities. 106 using Priority = uint64_t; 107 108 /** A functor with embedded salt that computes priority of an announcement. 109 * 110 * Higher priorities are selected first. 111 */ 112 class PriorityComputer { 113 const uint64_t m_k0, m_k1; 114 public: 115 explicit PriorityComputer(bool deterministic) : 116 m_k0{deterministic ? 0 : FastRandomContext().rand64()}, 117 m_k1{deterministic ? 0 : FastRandomContext().rand64()} {} 118 119 Priority operator()(const uint256& txhash, NodeId peer, bool preferred) const 120 { 121 uint64_t low_bits = CSipHasher(m_k0, m_k1).Write(txhash).Write(peer).Finalize() >> 1; 122 return low_bits | uint64_t{preferred} << 63; 123 } 124 125 Priority operator()(const Announcement& ann) const 126 { 127 return operator()(ann.m_txhash, ann.m_peer, ann.m_preferred); 128 } 129 }; 130 131 // Definitions for the 3 indexes used in the main data structure. 132 // 133 // Each index has a By* type to identify it, a By*View data type to represent the view of announcement it is sorted 134 // by, and an By*ViewExtractor type to convert an announcement into the By*View type. 135 // See https://www.boost.org/doc/libs/1_58_0/libs/multi_index/doc/reference/key_extraction.html#key_extractors 136 // for more information about the key extraction concept. 137 138 // The ByPeer index is sorted by (peer, state == CANDIDATE_BEST, txhash) 139 // 140 // Uses: 141 // * Looking up existing announcements by peer/txhash, by checking both (peer, false, txhash) and 142 // (peer, true, txhash). 143 // * Finding all CANDIDATE_BEST announcements for a given peer in GetRequestable. 144 struct ByPeer {}; 145 using ByPeerView = std::tuple<NodeId, bool, const uint256&>; 146 struct ByPeerViewExtractor 147 { 148 using result_type = ByPeerView; 149 result_type operator()(const Announcement& ann) const 150 { 151 return ByPeerView{ann.m_peer, ann.GetState() == State::CANDIDATE_BEST, ann.m_txhash}; 152 } 153 }; 154 155 // The ByTxHash index is sorted by (txhash, state, priority). 156 // 157 // Note: priority == 0 whenever state != CANDIDATE_READY. 158 // 159 // Uses: 160 // * Deleting all announcements with a given txhash in ForgetTxHash. 161 // * Finding the best CANDIDATE_READY to convert to CANDIDATE_BEST, when no other CANDIDATE_READY or REQUESTED 162 // announcement exists for that txhash. 163 // * Determining when no more non-COMPLETED announcements for a given txhash exist, so the COMPLETED ones can be 164 // deleted. 165 struct ByTxHash {}; 166 using ByTxHashView = std::tuple<const uint256&, State, Priority>; 167 class ByTxHashViewExtractor { 168 const PriorityComputer& m_computer; 169 public: 170 explicit ByTxHashViewExtractor(const PriorityComputer& computer) : m_computer(computer) {} 171 using result_type = ByTxHashView; 172 result_type operator()(const Announcement& ann) const 173 { 174 const Priority prio = (ann.GetState() == State::CANDIDATE_READY) ? m_computer(ann) : 0; 175 return ByTxHashView{ann.m_txhash, ann.GetState(), prio}; 176 } 177 }; 178 179 enum class WaitState { 180 //! Used for announcements that need efficient testing of "is their timestamp in the future?". 181 FUTURE_EVENT, 182 //! Used for announcements whose timestamp is not relevant. 183 NO_EVENT, 184 //! Used for announcements that need efficient testing of "is their timestamp in the past?". 185 PAST_EVENT, 186 }; 187 188 WaitState GetWaitState(const Announcement& ann) 189 { 190 if (ann.IsWaiting()) return WaitState::FUTURE_EVENT; 191 if (ann.IsSelectable()) return WaitState::PAST_EVENT; 192 return WaitState::NO_EVENT; 193 } 194 195 // The ByTime index is sorted by (wait_state, time). 196 // 197 // All announcements with a timestamp in the future can be found by iterating the index forward from the beginning. 198 // All announcements with a timestamp in the past can be found by iterating the index backwards from the end. 199 // 200 // Uses: 201 // * Finding CANDIDATE_DELAYED announcements whose reqtime has passed, and REQUESTED announcements whose expiry has 202 // passed. 203 // * Finding CANDIDATE_READY/BEST announcements whose reqtime is in the future (when the clock time went backwards). 204 struct ByTime {}; 205 using ByTimeView = std::pair<WaitState, std::chrono::microseconds>; 206 struct ByTimeViewExtractor 207 { 208 using result_type = ByTimeView; 209 result_type operator()(const Announcement& ann) const 210 { 211 return ByTimeView{GetWaitState(ann), ann.m_time}; 212 } 213 }; 214 215 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 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 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 bool operator==(const PeerInfo& a, const PeerInfo& b) 260 { 261 return std::tie(a.m_total, a.m_completed, a.m_requested) == 262 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 std::unordered_map<NodeId, PeerInfo> RecomputePeerInfo(const Index& index) 267 { 268 std::unordered_map<NodeId, PeerInfo> ret; 269 for (const Announcement& ann : index) { 270 PeerInfo& info = ret[ann.m_peer]; 271 ++info.m_total; 272 info.m_requested += (ann.GetState() == State::REQUESTED); 273 info.m_completed += (ann.GetState() == State::COMPLETED); 274 } 275 return ret; 276 } 277 278 /** Compute the TxHashInfo map. Only used for sanity checking. */ 279 std::map<uint256, TxHashInfo> ComputeTxHashInfo(const Index& index, const PriorityComputer& computer) 280 { 281 std::map<uint256, TxHashInfo> ret; 282 for (const Announcement& ann : index) { 283 TxHashInfo& info = ret[ann.m_txhash]; 284 // Classify how many announcements of each state we have for this txhash. 285 info.m_candidate_delayed += (ann.GetState() == State::CANDIDATE_DELAYED); 286 info.m_candidate_ready += (ann.GetState() == State::CANDIDATE_READY); 287 info.m_candidate_best += (ann.GetState() == State::CANDIDATE_BEST); 288 info.m_requested += (ann.GetState() == State::REQUESTED); 289 // And track the priority of the best CANDIDATE_READY/CANDIDATE_BEST announcements. 290 if (ann.GetState() == State::CANDIDATE_BEST) { 291 info.m_priority_candidate_best = computer(ann); 292 } 293 if (ann.GetState() == State::CANDIDATE_READY) { 294 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 info.m_peers.push_back(ann.m_peer); 298 } 299 return ret; 300 } 301 302 GenTxid ToGenTxid(const Announcement& ann) 303 { 304 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 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 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 assert(m_peerinfo == RecomputePeerInfo(m_index)); 330 331 // Calculate per-txhash statistics from m_index, and validate invariants. 332 for (auto& item : ComputeTxHashInfo(m_index, m_computer)) { 333 TxHashInfo& info = item.second; 334 335 // Cannot have only COMPLETED peer (txhash should have been forgotten already) 336 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 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 if (info.m_candidate_ready > 0) { 344 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 if (info.m_candidate_ready && info.m_candidate_best) { 350 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 std::sort(info.m_peers.begin(), info.m_peers.end()); 355 assert(std::adjacent_find(info.m_peers.begin(), info.m_peers.end()) == info.m_peers.end()); 356 } 357 } 358 359 void PostGetRequestableSanityCheck(std::chrono::microseconds now) const 360 { 361 for (const Announcement& ann : m_index) { 362 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 assert(ann.m_time > now); 366 } 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 assert(ann.m_time <= now); 370 } 371 } 372 } 373 374 private: 375 //! Wrapper around Index::...::erase that keeps m_peerinfo up to date. 376 template<typename Tag> 377 Iter<Tag> Erase(Iter<Tag> it) 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 if (--peerit->second.m_total == 0) m_peerinfo.erase(peerit); 383 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 void Modify(Iter<Tag> it, Modifier modifier) 389 { 390 auto peerit = m_peerinfo.find(it->m_peer); 391 peerit->second.m_completed -= it->GetState() == State::COMPLETED; 392 peerit->second.m_requested -= it->GetState() == State::REQUESTED; 393 m_index.get<Tag>().modify(it, std::move(modifier)); 394 peerit->second.m_completed += it->GetState() == State::COMPLETED; 395 peerit->second.m_requested += it->GetState() == State::REQUESTED; 396 } 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 void PromoteCandidateReady(Iter<ByTxHash> it) 402 { 403 assert(it != m_index.get<ByTxHash>().end()); 404 assert(it->GetState() == State::CANDIDATE_DELAYED); 405 // Convert CANDIDATE_DELAYED to CANDIDATE_READY first. 406 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 auto it_next = std::next(it); 412 if (it_next == m_index.get<ByTxHash>().end() || it_next->m_txhash != it->m_txhash || 413 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 Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); }); 417 } else if (it_next->GetState() == State::CANDIDATE_BEST) { 418 Priority priority_old = m_computer(*it_next); 419 Priority priority_new = m_computer(*it); 420 if (priority_new > priority_old) { 421 // There is a CANDIDATE_BEST announcement already, but this one is better. 422 Modify<ByTxHash>(it_next, [](Announcement& ann){ ann.SetState(State::CANDIDATE_READY); }); 423 Modify<ByTxHash>(it, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); }); 424 } 425 } 426 } 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 void ChangeAndReselect(Iter<ByTxHash> it, State new_state) 431 { 432 assert(new_state == State::COMPLETED || new_state == State::CANDIDATE_DELAYED); 433 assert(it != m_index.get<ByTxHash>().end()); 434 if (it->IsSelected() && it != m_index.get<ByTxHash>().begin()) { 435 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 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 Modify<ByTxHash>(it_prev, [](Announcement& ann){ ann.SetState(State::CANDIDATE_BEST); }); 441 } 442 } 443 Modify<ByTxHash>(it, [new_state](Announcement& ann){ ann.SetState(new_state); }); 444 } 445 446 //! Check if 'it' is the only announcement for a given txhash that isn't COMPLETED. 447 bool IsOnlyNonCompleted(Iter<ByTxHash> it) 448 { 449 assert(it != m_index.get<ByTxHash>().end()); 450 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 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 if (std::next(it) != m_index.get<ByTxHash>().end() && std::next(it)->m_txhash == it->m_txhash && 458 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 bool MakeCompleted(Iter<ByTxHash> it) 467 { 468 assert(it != m_index.get<ByTxHash>().end()); 469 470 // Nothing to be done if it's already COMPLETED. 471 if (it->GetState() == State::COMPLETED) return true; 472 473 if (IsOnlyNonCompleted(it)) { 474 // This is the last non-COMPLETED announcement for this txhash. Delete all. 475 uint256 txhash = it->m_txhash; 476 do { 477 it = Erase<ByTxHash>(it); 478 } 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 ChangeAndReselect(it, State::COMPLETED); 485 486 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 void SetTimePoint(std::chrono::microseconds now, std::vector<std::pair<NodeId, GenTxid>>* expired) 494 { 495 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 while (!m_index.empty()) { 500 auto it = m_index.get<ByTime>().begin(); 501 if (it->GetState() == State::CANDIDATE_DELAYED && it->m_time <= now) { 502 PromoteCandidateReady(m_index.project<ByTxHash>(it)); 503 } else if (it->GetState() == State::REQUESTED && it->m_time <= now) { 504 if (expired) expired->emplace_back(it->m_peer, ToGenTxid(*it)); 505 MakeCompleted(m_index.project<ByTxHash>(it)); 506 } else { 507 break; 508 } 509 } 510 511 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 auto it = std::prev(m_index.get<ByTime>().end()); 516 if (it->IsSelectable() && it->m_time > now) { 517 ChangeAndReselect(m_index.project<ByTxHash>(it), State::CANDIDATE_DELAYED); 518 } else { 519 break; 520 } 521 } 522 } 523 524 public: 525 explicit Impl(bool deterministic) : 526 m_computer(deterministic), 527 // Explicitly initialize m_index as we need to pass a reference to m_computer to ByTxHashViewExtractor. 528 m_index(boost::make_tuple( 529 boost::make_tuple(ByPeerViewExtractor(), std::less<ByPeerView>()), 530 boost::make_tuple(ByTxHashViewExtractor(m_computer), std::less<ByTxHashView>()), 531 boost::make_tuple(ByTimeViewExtractor(), std::less<ByTimeView>()) 532 )) {} 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 void DisconnectedPeer(NodeId peer) 539 { 540 auto& index = m_index.get<ByPeer>(); 541 auto it = index.lower_bound(ByPeerView{peer, false, uint256::ZERO}); 542 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 auto it_next = (std::next(it) == index.end() || std::next(it)->m_peer != peer) ? index.end() : 557 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 if (MakeCompleted(m_index.project<ByTxHash>(it))) { 562 // Then actually delete the announcement (unless it was already deleted by MakeCompleted). 563 Erase<ByPeer>(it); 564 } 565 it = it_next; 566 } 567 } 568 569 void ForgetTxHash(const uint256& txhash) 570 { 571 auto it = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_DELAYED, 0}); 572 while (it != m_index.get<ByTxHash>().end() && it->m_txhash == txhash) { 573 it = Erase<ByTxHash>(it); 574 } 575 } 576 577 void GetCandidatePeers(const uint256& txhash, std::vector<NodeId>& result_peers) const 578 { 579 auto it = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_DELAYED, 0}); 580 while (it != m_index.get<ByTxHash>().end() && it->m_txhash == txhash && it->GetState() != State::COMPLETED) { 581 result_peers.push_back(it->m_peer); 582 ++it; 583 } 584 } 585 586 void ReceivedInv(NodeId peer, const GenTxid& gtxid, bool preferred, 587 std::chrono::microseconds reqtime) 588 { 589 // Bail out if we already have a CANDIDATE_BEST announcement for this (txhash, peer) combination. The case 590 // where there is a non-CANDIDATE_BEST announcement already will be caught by the uniqueness property of the 591 // ByPeer index when we try to emplace the new object below. 592 if (m_index.get<ByPeer>().count(ByPeerView{peer, true, gtxid.GetHash()})) return; 593 594 // Try creating the announcement with CANDIDATE_DELAYED state (which will fail due to the uniqueness 595 // of the ByPeer index if a non-CANDIDATE_BEST announcement already exists with the same txhash and peer). 596 // Bail out in that case. 597 auto ret = m_index.get<ByPeer>().emplace(gtxid, peer, preferred, reqtime, m_current_sequence); 598 if (!ret.second) return; 599 600 // Update accounting metadata. 601 ++m_peerinfo[peer].m_total; 602 ++m_current_sequence; 603 } 604 605 //! Find the GenTxids to request now from peer. 606 std::vector<GenTxid> GetRequestable(NodeId peer, std::chrono::microseconds now, 607 std::vector<std::pair<NodeId, GenTxid>>* expired) 608 { 609 // Move time. 610 SetTimePoint(now, expired); 611 612 // Find all CANDIDATE_BEST announcements for this peer. 613 std::vector<const Announcement*> selected; 614 auto it_peer = m_index.get<ByPeer>().lower_bound(ByPeerView{peer, true, uint256::ZERO}); 615 while (it_peer != m_index.get<ByPeer>().end() && it_peer->m_peer == peer && 616 it_peer->GetState() == State::CANDIDATE_BEST) { 617 selected.emplace_back(&*it_peer); 618 ++it_peer; 619 } 620 621 // Sort by sequence number. 622 std::sort(selected.begin(), selected.end(), [](const Announcement* a, const Announcement* b) { 623 return a->m_sequence < b->m_sequence; 624 }); 625 626 // Convert to GenTxid and return. 627 std::vector<GenTxid> ret; 628 ret.reserve(selected.size()); 629 std::transform(selected.begin(), selected.end(), std::back_inserter(ret), [](const Announcement* ann) { 630 return ToGenTxid(*ann); 631 }); 632 return ret; 633 } 634 635 void RequestedTx(NodeId peer, const uint256& txhash, std::chrono::microseconds expiry) 636 { 637 auto it = m_index.get<ByPeer>().find(ByPeerView{peer, true, txhash}); 638 if (it == m_index.get<ByPeer>().end()) { 639 // There is no CANDIDATE_BEST announcement, look for a _READY or _DELAYED instead. If the caller only 640 // ever invokes RequestedTx with the values returned by GetRequestable, and no other non-const functions 641 // other than ForgetTxHash and GetRequestable in between, this branch will never execute (as txhashes 642 // returned by GetRequestable always correspond to CANDIDATE_BEST announcements). 643 644 it = m_index.get<ByPeer>().find(ByPeerView{peer, false, txhash}); 645 if (it == m_index.get<ByPeer>().end() || (it->GetState() != State::CANDIDATE_DELAYED && 646 it->GetState() != State::CANDIDATE_READY)) { 647 // There is no CANDIDATE announcement tracked for this peer, so we have nothing to do. Either this 648 // txhash wasn't tracked at all (and the caller should have called ReceivedInv), or it was already 649 // requested and/or completed for other reasons and this is just a superfluous RequestedTx call. 650 return; 651 } 652 653 // Look for an existing CANDIDATE_BEST or REQUESTED with the same txhash. We only need to do this if the 654 // found announcement had a different state than CANDIDATE_BEST. If it did, invariants guarantee that no 655 // other CANDIDATE_BEST or REQUESTED can exist. 656 auto it_old = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_BEST, 0}); 657 if (it_old != m_index.get<ByTxHash>().end() && it_old->m_txhash == txhash) { 658 if (it_old->GetState() == State::CANDIDATE_BEST) { 659 // The data structure's invariants require that there can be at most one CANDIDATE_BEST or one 660 // REQUESTED announcement per txhash (but not both simultaneously), so we have to convert any 661 // existing CANDIDATE_BEST to another CANDIDATE_* when constructing another REQUESTED. 662 // It doesn't matter whether we pick CANDIDATE_READY or _DELAYED here, as SetTimePoint() 663 // will correct it at GetRequestable() time. If time only goes forward, it will always be 664 // _READY, so pick that to avoid extra work in SetTimePoint(). 665 Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::CANDIDATE_READY); }); 666 } else if (it_old->GetState() == State::REQUESTED) { 667 // As we're no longer waiting for a response to the previous REQUESTED announcement, convert it 668 // to COMPLETED. This also helps guaranteeing progress. 669 Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::COMPLETED); }); 670 } 671 } 672 } 673 674 Modify<ByPeer>(it, [expiry](Announcement& ann) { 675 ann.SetState(State::REQUESTED); 676 ann.m_time = expiry; 677 }); 678 } 679 680 void ReceivedResponse(NodeId peer, const uint256& txhash) 681 { 682 // We need to search the ByPeer index for both (peer, false, txhash) and (peer, true, txhash). 683 auto it = m_index.get<ByPeer>().find(ByPeerView{peer, false, txhash}); 684 if (it == m_index.get<ByPeer>().end()) { 685 it = m_index.get<ByPeer>().find(ByPeerView{peer, true, txhash}); 686 } 687 if (it != m_index.get<ByPeer>().end()) MakeCompleted(m_index.project<ByTxHash>(it)); 688 } 689 690 size_t CountInFlight(NodeId peer) const 691 { 692 auto it = m_peerinfo.find(peer); 693 if (it != m_peerinfo.end()) return it->second.m_requested; 694 return 0; 695 } 696 697 size_t CountCandidates(NodeId peer) const 698 { 699 auto it = m_peerinfo.find(peer); 700 if (it != m_peerinfo.end()) return it->second.m_total - it->second.m_requested - it->second.m_completed; 701 return 0; 702 } 703 704 size_t Count(NodeId peer) const 705 { 706 auto it = m_peerinfo.find(peer); 707 if (it != m_peerinfo.end()) return it->second.m_total; 708 return 0; 709 } 710 711 //! Count how many announcements are being tracked in total across all peers and transactions. 712 size_t Size() const { return m_index.size(); } 713 714 uint64_t ComputePriority(const uint256& txhash, NodeId peer, bool preferred) const 715 { 716 // Return Priority as a uint64_t as Priority is internal. 717 return uint64_t{m_computer(txhash, peer, preferred)}; 718 } 719 720 }; 721 722 TxRequestTracker::TxRequestTracker(bool deterministic) : 723 m_impl{std::make_unique<TxRequestTracker::Impl>(deterministic)} {} 724 725 TxRequestTracker::~TxRequestTracker() = default; 726 727 void TxRequestTracker::ForgetTxHash(const uint256& txhash) { m_impl->ForgetTxHash(txhash); } 728 void TxRequestTracker::DisconnectedPeer(NodeId peer) { m_impl->DisconnectedPeer(peer); } 729 size_t TxRequestTracker::CountInFlight(NodeId peer) const { return m_impl->CountInFlight(peer); } 730 size_t TxRequestTracker::CountCandidates(NodeId peer) const { return m_impl->CountCandidates(peer); } 731 size_t TxRequestTracker::Count(NodeId peer) const { return m_impl->Count(peer); } 732 size_t TxRequestTracker::Size() const { return m_impl->Size(); } 733 void TxRequestTracker::GetCandidatePeers(const uint256& txhash, std::vector<NodeId>& result_peers) const { return m_impl->GetCandidatePeers(txhash, result_peers); } 734 void TxRequestTracker::SanityCheck() const { m_impl->SanityCheck(); } 735 736 void TxRequestTracker::PostGetRequestableSanityCheck(std::chrono::microseconds now) const 737 { 738 m_impl->PostGetRequestableSanityCheck(now); 739 } 740 741 void TxRequestTracker::ReceivedInv(NodeId peer, const GenTxid& gtxid, bool preferred, 742 std::chrono::microseconds reqtime) 743 { 744 m_impl->ReceivedInv(peer, gtxid, preferred, reqtime); 745 } 746 747 void TxRequestTracker::RequestedTx(NodeId peer, const uint256& txhash, std::chrono::microseconds expiry) 748 { 749 m_impl->RequestedTx(peer, txhash, expiry); 750 } 751 752 void TxRequestTracker::ReceivedResponse(NodeId peer, const uint256& txhash) 753 { 754 m_impl->ReceivedResponse(peer, txhash); 755 } 756 757 std::vector<GenTxid> TxRequestTracker::GetRequestable(NodeId peer, std::chrono::microseconds now, 758 std::vector<std::pair<NodeId, GenTxid>>* expired) 759 { 760 return m_impl->GetRequestable(peer, now, expired); 761 } 762 763 uint64_t TxRequestTracker::ComputePriority(const uint256& txhash, NodeId peer, bool preferred) const 764 { 765 return m_impl->ComputePriority(txhash, peer, preferred); 766 }