Inside Bitcoin

501            // If time went backwards, we may need to demote CANDIDATE_BEST and CANDIDATE_READY announcements back
502            // to CANDIDATE_DELAYED. This is an unusual edge case, and unlikely to matter in production. However,
503            // it makes it much easier to specify and test TxRequestTracker::Impl's behaviour.
504            auto it = std::prev(m_index.get<ByTime>().end());
505            if (it->IsSelectable() && it->m_time > now) {
506                ChangeAndReselect(m_index.project<ByTxHash>(it), State::CANDIDATE_DELAYED);
507            } else {
508                break;
509            }
510        }
511    }
512
513public:
514    explicit Impl(bool deterministic) :
515        m_computer(deterministic),
516        // Explicitly initialize m_index as we need to pass a reference to m_computer to ByTxHashViewExtractor.
517        m_index(boost::make_tuple(
518            boost::make_tuple(ByPeerViewExtractor(), std::less<ByPeerView>()),
519            boost::make_tuple(ByTxHashViewExtractor(m_computer), std::less<ByTxHashView>()),
520            boost::make_tuple(ByTimeViewExtractor(), std::less<ByTimeView>())
521        )) {}
522
523    // Disable copying and assigning (a default copy won't work due the stateful ByTxHashViewExtractor).
524    Impl(const Impl&) = delete;
525    Impl& operator=(const Impl&) = delete;
526
527    void DisconnectedPeer(NodeId peer)
528    {
529        auto& index = m_index.get<ByPeer>();
530        auto it = index.lower_bound(ByPeerView{peer, false, uint256::ZERO});
531        while (it != index.end() && it->m_peer == peer) {
532            // Check what to continue with after this iteration. 'it' will be deleted in what follows, so we need to
533            // decide what to continue with afterwards. There are a number of cases to consider:
534            // - std::next(it) is end() or belongs to a different peer. In that case, this is the last iteration
535            //   of the loop (denote this by setting it_next to end()).
536            // - 'it' is not the only non-COMPLETED announcement for its txhash. This means it will be deleted, but
537            //   no other Announcement objects will be modified. Continue with std::next(it) if it belongs to the
538            //   same peer, but decide this ahead of time (as 'it' may change position in what follows).
539            // - 'it' is the only non-COMPLETED announcement for its txhash. This means it will be deleted along
540            //   with all other announcements for the same txhash - which may include std::next(it). However, other
541            //   than 'it', no announcements for the same peer can be affected (due to (peer, txhash) uniqueness).
542            //   In other words, the situation where std::next(it) is deleted can only occur if std::next(it)
543            //   belongs to a different peer but the same txhash as 'it'. This is covered by the first bulletpoint
544            //   already, and we'll have set it_next to end().
545            auto it_next = (std::next(it) == index.end() || std::next(it)->m_peer != peer) ? index.end() :
546                std::next(it);
547            // If the announcement isn't already COMPLETED, first make it COMPLETED (which will mark other
548            // CANDIDATEs as CANDIDATE_BEST, or delete all of a txhash's announcements if no non-COMPLETED ones are
549            // left).
550            if (MakeCompleted(m_index.project<ByTxHash>(it))) {
551                // Then actually delete the announcement (unless it was already deleted by MakeCompleted).
552                Erase<ByPeer>(it);
553            }
554            it = it_next;
555        }
556    }
557
558    void ForgetTxHash(const uint256& txhash)
559    {
560        auto it = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_DELAYED, 0});
561        while (it != m_index.get<ByTxHash>().end() && it->m_gtxid.ToUint256() == txhash) {
562            it = Erase<ByTxHash>(it);
563        }
564    }
565
566    void GetCandidatePeers(const uint256& txhash, std::vector<NodeId>& result_peers) const
567    {
568        auto it = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_DELAYED, 0});
569        while (it != m_index.get<ByTxHash>().end() && it->m_gtxid.ToUint256() == txhash && it->GetState() != State::COMPLETED) {
570            result_peers.push_back(it->m_peer);
571            ++it;
572        }
573    }
574
575    void ReceivedInv(NodeId peer, const GenTxid& gtxid, bool preferred,
576                     std::chrono::microseconds reqtime)
577    {
578        // Bail out if we already have a CANDIDATE_BEST announcement for this (txhash, peer) combination. The case
579        // where there is a non-CANDIDATE_BEST announcement already will be caught by the uniqueness property of the
580        // ByPeer index when we try to emplace the new object below.
581        if (m_index.get<ByPeer>().count(ByPeerView{peer, true, gtxid.ToUint256()})) return;
582
583        // Try creating the announcement with CANDIDATE_DELAYED state (which will fail due to the uniqueness
584        // of the ByPeer index if a non-CANDIDATE_BEST announcement already exists with the same txhash and peer).
585        // Bail out in that case.
586        auto ret = m_index.get<ByPeer>().emplace(gtxid, peer, preferred, reqtime, m_current_sequence);
587        if (!ret.second) return;
588
589        // Update accounting metadata.
590        ++m_peerinfo[peer].m_total;
591        ++m_current_sequence;
592    }
593
594    //! Find the GenTxids to request now from peer.
595    std::vector<GenTxid> GetRequestable(NodeId peer, std::chrono::microseconds now,
596                                        std::vector<std::pair<NodeId, GenTxid>>* expired)
597    {
598        // Move time.
599        SetTimePoint(now, expired);
600
601        // Find all CANDIDATE_BEST announcements for this peer.
602        std::vector<const Announcement*> selected;
603        auto it_peer = m_index.get<ByPeer>().lower_bound(ByPeerView{peer, true, uint256::ZERO});
604        while (it_peer != m_index.get<ByPeer>().end() && it_peer->m_peer == peer &&
605            it_peer->GetState() == State::CANDIDATE_BEST) {
606            selected.emplace_back(&*it_peer);
607            ++it_peer;
608        }
609
610        // Sort by sequence number.
611        std::sort(selected.begin(), selected.end(), [](const Announcement* a, const Announcement* b) {
612            return a->m_sequence < b->m_sequence;
613        });
614
615        // Convert to GenTxid and return.
616        std::vector<GenTxid> ret;
617        ret.reserve(selected.size());
618        std::transform(selected.begin(), selected.end(), std::back_inserter(ret), [](const Announcement* ann) {
619            return ann->m_gtxid;
620        });
621        return ret;
622    }
623
624    void RequestedTx(NodeId peer, const uint256& txhash, std::chrono::microseconds expiry)
625    {
626        auto it = m_index.get<ByPeer>().find(ByPeerView{peer, true, txhash});
627        if (it == m_index.get<ByPeer>().end()) {
628            // There is no CANDIDATE_BEST announcement, look for a _READY or _DELAYED instead. If the caller only
629            // ever invokes RequestedTx with the values returned by GetRequestable, and no other non-const functions
630            // other than ForgetTxHash and GetRequestable in between, this branch will never execute (as txhashes
631            // returned by GetRequestable always correspond to CANDIDATE_BEST announcements).
632
633            it = m_index.get<ByPeer>().find(ByPeerView{peer, false, txhash});
634            if (it == m_index.get<ByPeer>().end() || (it->GetState() != State::CANDIDATE_DELAYED &&
635                                                      it->GetState() != State::CANDIDATE_READY)) {
636                // There is no CANDIDATE announcement tracked for this peer, so we have nothing to do. Either this
637                // txhash wasn't tracked at all (and the caller should have called ReceivedInv), or it was already
638                // requested and/or completed for other reasons and this is just a superfluous RequestedTx call.
639                return;
640            }
641
642            // Look for an existing CANDIDATE_BEST or REQUESTED with the same txhash. We only need to do this if the
643            // found announcement had a different state than CANDIDATE_BEST. If it did, invariants guarantee that no
644            // other CANDIDATE_BEST or REQUESTED can exist.
645            auto it_old = m_index.get<ByTxHash>().lower_bound(ByTxHashView{txhash, State::CANDIDATE_BEST, 0});
646            if (it_old != m_index.get<ByTxHash>().end() && it_old->m_gtxid.ToUint256() == txhash) {
647                if (it_old->GetState() == State::CANDIDATE_BEST) {
648                    // The data structure's invariants require that there can be at most one CANDIDATE_BEST or one
649                    // REQUESTED announcement per txhash (but not both simultaneously), so we have to convert any
650                    // existing CANDIDATE_BEST to another CANDIDATE_* when constructing another REQUESTED.
651                    // It doesn't matter whether we pick CANDIDATE_READY or _DELAYED here, as SetTimePoint()
652                    // will correct it at GetRequestable() time. If time only goes forward, it will always be
653                    // _READY, so pick that to avoid extra work in SetTimePoint().
654                    Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::CANDIDATE_READY); });
655                } else if (it_old->GetState() == State::REQUESTED) {
656                    // As we're no longer waiting for a response to the previous REQUESTED announcement, convert it
657                    // to COMPLETED. This also helps guaranteeing progress.
658                    Modify<ByTxHash>(it_old, [](Announcement& ann) { ann.SetState(State::COMPLETED); });
659                }
660            }
661        }
662
663        Modify<ByPeer>(it, [expiry](Announcement& ann) {
664            ann.SetState(State::REQUESTED);
665            ann.m_time = expiry;
666        });
667    }
668
669    void ReceivedResponse(NodeId peer, const uint256& txhash)
670    {
671        // We need to search the ByPeer index for both (peer, false, txhash) and (peer, true, txhash).
672        auto it = m_index.get<ByPeer>().find(ByPeerView{peer, false, txhash});
673        if (it == m_index.get<ByPeer>().end()) {
674            it = m_index.get<ByPeer>().find(ByPeerView{peer, true, txhash});
675        }
676        if (it != m_index.get<ByPeer>().end()) MakeCompleted(m_index.project<ByTxHash>(it));
677    }
678
679    size_t CountInFlight(NodeId peer) const
680    {
681        auto it = m_peerinfo.find(peer);
682        if (it != m_peerinfo.end()) return it->second.m_requested;
683        return 0;
684    }
685
686    size_t CountCandidates(NodeId peer) const
687    {
688        auto it = m_peerinfo.find(peer);
689        if (it != m_peerinfo.end()) return it->second.m_total - it->second.m_requested - it->second.m_completed;
690        return 0;
691    }
692
693    size_t Count(NodeId peer) const
694    {
695        auto it = m_peerinfo.find(peer);
696        if (it != m_peerinfo.end()) return it->second.m_total;
697        return 0;
698    }
699
700    //! Count how many announcements are being tracked in total across all peers and transactions.
701    size_t Size() const { return m_index.size(); }
702
703    uint64_t ComputePriority(const uint256& txhash, NodeId peer, bool preferred) const
704    {
705        // Return Priority as a uint64_t as Priority is internal.
706        return uint64_t{m_computer(txhash, peer, preferred)};
707    }
708
709};
710
711TxRequestTracker::TxRequestTracker(bool deterministic) :
712    m_impl{std::make_unique<TxRequestTracker::Impl>(deterministic)} {}
713
714TxRequestTracker::~TxRequestTracker() = default;
715
716void TxRequestTracker::ForgetTxHash(const uint256& txhash) { m_impl->ForgetTxHash(txhash); }
717void TxRequestTracker::DisconnectedPeer(NodeId peer) { m_impl->DisconnectedPeer(peer); }
718size_t TxRequestTracker::CountInFlight(NodeId peer) const { return m_impl->CountInFlight(peer); }
719size_t TxRequestTracker::CountCandidates(NodeId peer) const { return m_impl->CountCandidates(peer); }
720size_t TxRequestTracker::Count(NodeId peer) const { return m_impl->Count(peer); }
721size_t TxRequestTracker::Size() const { return m_impl->Size(); }
722void TxRequestTracker::GetCandidatePeers(const uint256& txhash, std::vector<NodeId>& result_peers) const { return m_impl->GetCandidatePeers(txhash, result_peers); }
723void TxRequestTracker::SanityCheck() const { m_impl->SanityCheck(); }
724
725void TxRequestTracker::PostGetRequestableSanityCheck(std::chrono::microseconds now) const
726{
727    m_impl->PostGetRequestableSanityCheck(now);
728}
729
730void TxRequestTracker::ReceivedInv(NodeId peer, const GenTxid& gtxid, bool preferred,
731                                   std::chrono::microseconds reqtime)
732{
733    m_impl->ReceivedInv(peer, gtxid, preferred, reqtime);
734}
735
736void TxRequestTracker::RequestedTx(NodeId peer, const uint256& txhash, std::chrono::microseconds expiry)
737{
738    m_impl->RequestedTx(peer, txhash, expiry);
739}
740
741void TxRequestTracker::ReceivedResponse(NodeId peer, const uint256& txhash)
742{
743    m_impl->ReceivedResponse(peer, txhash);
744}
745
746std::vector<GenTxid> TxRequestTracker::GetRequestable(NodeId peer, std::chrono::microseconds now,
747                                                      std::vector<std::pair<NodeId, GenTxid>>* expired)
748{
749    return m_impl->GetRequestable(peer, now, expired);
750}