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