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