Inside Bitcoin

501        unsigned int num_erased_this_round{0};
502        unsigned int starting_num_ann{it_worst_peer->second.m_count_announcements};
503        while (NeedsTrim()) {
504            if (!Assume(it_ann != m_orphans.get<ByPeer>().end())) break;
505            if (!Assume(it_ann->m_announcer == worst_peer)) break;
506
507            Erase<ByPeer>(it_ann++);
508            num_erased += 1;
509            num_erased_this_round += 1;
510
511            // If we erased the last orphan from this peer, it_worst_peer will be invalidated.
512            it_worst_peer = m_peer_orphanage_info.find(worst_peer);
513            if (it_worst_peer == m_peer_orphanage_info.end() ||
514                ByRatioNegSize{it_worst_peer->second.GetDosScore(max_lat, max_mem)} <= ByRatioNegSize{dos_threshold}) break;
515        }
516        LogDebug(BCLog::TXPACKAGES, "peer=%d orphanage overflow, removed %u of %u announcements\n", worst_peer, num_erased_this_round, starting_num_ann);
517
518        if (!NeedsTrim()) break;
519
520        // Unless this peer is empty, put it back in the heap so we continue to consider evicting its orphans.
521        // We may select this peer for evictions again if there are multiple DoSy peers.
522        if (it_worst_peer != m_peer_orphanage_info.end() && it_worst_peer->second.m_count_announcements > 0) {
523            heap_peer_dos.emplace_back(worst_peer, it_worst_peer->second.GetDosScore(max_lat, max_mem));
524            std::push_heap(heap_peer_dos.begin(), heap_peer_dos.end(), compare_score);
525        }
526    } while (true);
527
528    const auto remaining_unique_orphans{CountUniqueOrphans()};
529    LogDebug(BCLog::TXPACKAGES, "orphanage overflow, removed %u tx (%u announcements)\n", original_unique_txns - remaining_unique_orphans, num_erased);
530}
531
532std::vector<std::pair<Wtxid, NodeId>> TxOrphanageImpl::AddChildrenToWorkSet(const CTransaction& tx, FastRandomContext& rng)
533{
534    if (m_orphans.empty()) return {};
535
536    std::vector<std::pair<Wtxid, NodeId>> ret;
537    auto& index_by_wtxid = m_orphans.get<ByWtxid>();
538    for (unsigned int i = 0; i < tx.vout.size(); i++) {
539        const auto it_by_prev = m_outpoint_to_orphan_wtxids.find(COutPoint(tx.GetHash(), i));
540        if (it_by_prev != m_outpoint_to_orphan_wtxids.end()) {
541            for (const auto& wtxid : it_by_prev->second) {
542                // If a reconsiderable announcement for this wtxid already exists, skip it.
543                if (m_reconsiderable_wtxids.contains(wtxid)) continue;
544
545                // Belt and suspenders, each entry in m_outpoint_to_orphan_wtxids should always have at least 1 announcement.
546                auto it = index_by_wtxid.lower_bound(ByWtxidView{wtxid, MIN_PEER});
547                if (!Assume(it != index_by_wtxid.end() && it->m_tx->GetWitnessHash() == wtxid)) continue;
548
549                // Select a random peer to assign orphan processing, reducing wasted work if the orphan is still missing
550                // inputs. However, we don't want to create an issue in which the assigned peer can purposefully stop us
551                // from processing the orphan by disconnecting.
552                auto it_end = index_by_wtxid.upper_bound(ByWtxidView{wtxid, MAX_PEER});
553                const auto num_announcers{std::distance(it, it_end)};
554                if (!Assume(num_announcers > 0)) continue;
555                std::advance(it, rng.randrange(num_announcers));
556
557                if (!Assume(it->m_tx->GetWitnessHash() == wtxid)) break;
558
559                // Mark this orphan as ready to be reconsidered.
560                static constexpr auto mark_reconsidered_modifier = [](auto& ann) { ann.m_reconsider = true; };
561                Assume(!it->m_reconsider);
562                index_by_wtxid.modify(it, mark_reconsidered_modifier);
563                ret.emplace_back(wtxid, it->m_announcer);
564                m_reconsiderable_wtxids.insert(wtxid);
565
566                LogDebug(BCLog::TXPACKAGES, "added %s (wtxid=%s) to peer %d workset\n",
567                            it->m_tx->GetHash().ToString(), it->m_tx->GetWitnessHash().ToString(), it->m_announcer);
568            }
569        }
570    }
571    return ret;
572}
573
574bool TxOrphanageImpl::HaveTx(const Wtxid& wtxid) const
575{
576    auto it_lower = m_orphans.get<ByWtxid>().lower_bound(ByWtxidView{wtxid, MIN_PEER});
577    return it_lower != m_orphans.get<ByWtxid>().end() && it_lower->m_tx->GetWitnessHash() == wtxid;
578}
579
580CTransactionRef TxOrphanageImpl::GetTx(const Wtxid& wtxid) const
581{
582    auto it_lower = m_orphans.get<ByWtxid>().lower_bound(ByWtxidView{wtxid, MIN_PEER});
583    if (it_lower != m_orphans.get<ByWtxid>().end() && it_lower->m_tx->GetWitnessHash() == wtxid) return it_lower->m_tx;
584    return nullptr;
585}
586
587bool TxOrphanageImpl::HaveTxFromPeer(const Wtxid& wtxid, NodeId peer) const
588{
589    return m_orphans.get<ByWtxid>().count(ByWtxidView{wtxid, peer}) > 0;
590}
591
592/** If there is a tx that can be reconsidered, return it and set it back to
593 * non-reconsiderable. Otherwise, return a nullptr. */
594CTransactionRef TxOrphanageImpl::GetTxToReconsider(NodeId peer)
595{
596    auto it = m_orphans.get<ByPeer>().lower_bound(ByPeerView{peer, true, 0});
597    if (it != m_orphans.get<ByPeer>().end() && it->m_announcer == peer && it->m_reconsider) {
598        // Flip m_reconsider. Even if this transaction stays in orphanage, it shouldn't be
599        // reconsidered again until there is a new reason to do so.
600        static constexpr auto mark_reconsidered_modifier = [](auto& ann) { ann.m_reconsider = false; };
601        m_orphans.get<ByPeer>().modify(it, mark_reconsidered_modifier);
602        // As there is exactly one m_reconsider announcement per reconsiderable wtxids, flipping
603        // the m_reconsider flag means the wtxid is no longer reconsiderable.
604        m_reconsiderable_wtxids.erase(it->m_tx->GetWitnessHash());
605        return it->m_tx;
606    }
607    return nullptr;
608}
609
610/** Return whether there is a tx that can be reconsidered. */
611bool TxOrphanageImpl::HaveTxToReconsider(NodeId peer)
612{
613    auto it = m_orphans.get<ByPeer>().lower_bound(ByPeerView{peer, true, 0});
614    return it != m_orphans.get<ByPeer>().end() && it->m_announcer == peer && it->m_reconsider;
615}
616
617void TxOrphanageImpl::EraseForBlock(const CBlock& block)
618{
619    if (m_orphans.empty()) return;
620
621    std::set<Wtxid> wtxids_to_erase;
622    for (const CTransactionRef& ptx : block.vtx) {
623        const CTransaction& block_tx = *ptx;
624
625        // Which orphan pool entries must we evict?
626        for (const auto& input : block_tx.vin) {
627            auto it_prev = m_outpoint_to_orphan_wtxids.find(input.prevout);
628            if (it_prev != m_outpoint_to_orphan_wtxids.end()) {
629                // Copy all wtxids to wtxids_to_erase.
630                std::copy(it_prev->second.cbegin(), it_prev->second.cend(), std::inserter(wtxids_to_erase, wtxids_to_erase.end()));
631            }
632        }
633    }
634
635    unsigned int num_erased{0};
636    for (const auto& wtxid : wtxids_to_erase) {
637        // Don't use EraseTx here because it calls LimitOrphans and announcements deleted in that call are not reflected
638        // in its return result. Waiting until the end to do LimitOrphans helps save repeated computation and allows us
639        // to check that num_erased is what we expect.
640        num_erased += EraseTxInternal(wtxid) ? 1 : 0;
641    }
642
643    if (num_erased != 0) {
644        LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) included or conflicted by block\n", num_erased);
645    }
646    Assume(wtxids_to_erase.size() == num_erased);
647
648    // Deletions can cause the orphanage's MaxGlobalUsage to decrease, so we may need to trim here.
649    LimitOrphans();
650}
651
652std::vector<CTransactionRef> TxOrphanageImpl::GetChildrenFromSamePeer(const CTransactionRef& parent, NodeId peer) const
653{
654    std::vector<CTransactionRef> children_found;
655    const auto& parent_txid{parent->GetHash()};
656
657    // Iterate through all orphans from this peer, in reverse order, so that more recent
658    // transactions are added first. Doing so helps avoid work when one of the orphans replaced
659    // an earlier one. Since we require the NodeId to match, one peer's announcement order does
660    // not bias how we process other peer's orphans.
661    auto& index_by_peer = m_orphans.get<ByPeer>();
662    auto it_upper = index_by_peer.upper_bound(ByPeerView{peer, true, std::numeric_limits<uint64_t>::max()});
663    auto it_lower = index_by_peer.lower_bound(ByPeerView{peer, false, 0});
664
665    while (it_upper != it_lower) {
666        --it_upper;
667        if (!Assume(it_upper->m_announcer == peer)) break;
668        // Check if this tx spends from parent.
669        for (const auto& input : it_upper->m_tx->vin) {
670            if (input.prevout.hash == parent_txid) {
671                children_found.emplace_back(it_upper->m_tx);
672                break;
673            }
674        }
675    }
676    return children_found;
677}
678
679std::vector<TxOrphanage::OrphanInfo> TxOrphanageImpl::GetOrphanTransactions() const
680{
681    std::vector<TxOrphanage::OrphanInfo> result;
682    result.reserve(m_unique_orphans);
683
684    auto& index_by_wtxid = m_orphans.get<ByWtxid>();
685    auto it = index_by_wtxid.begin();
686    std::set<NodeId> this_orphan_announcers;
687    while (it != index_by_wtxid.end()) {
688        this_orphan_announcers.insert(it->m_announcer);
689        // If this is the last entry, or the next entry has a different wtxid, build a OrphanInfo.
690        if (std::next(it) == index_by_wtxid.end() || std::next(it)->m_tx->GetWitnessHash() != it->m_tx->GetWitnessHash()) {
691            result.emplace_back(it->m_tx, std::move(this_orphan_announcers));
692            this_orphan_announcers.clear();
693        }
694
695        ++it;
696    }
697    Assume(m_unique_orphans == result.size());
698
699    return result;
700}
701
702void TxOrphanageImpl::SanityCheck() const
703{
704    std::unordered_map<NodeId, PeerDoSInfo> reconstructed_peer_info;
705    std::map<Wtxid, std::pair<TxOrphanage::Usage, TxOrphanage::Count>> unique_wtxids_to_scores;
706    std::set<COutPoint> all_outpoints;
707    std::set<Wtxid> reconstructed_reconsiderable_wtxids;
708
709    for (auto it = m_orphans.begin(); it != m_orphans.end(); ++it) {
710        for (const auto& input : it->m_tx->vin) {
711            all_outpoints.insert(input.prevout);
712        }
713        unique_wtxids_to_scores.emplace(it->m_tx->GetWitnessHash(), std::make_pair(it->GetMemUsage(), it->GetLatencyScore() - 1));
714
715        auto& peer_info = reconstructed_peer_info[it->m_announcer];
716        peer_info.m_total_usage += it->GetMemUsage();
717        peer_info.m_count_announcements += 1;
718        peer_info.m_total_latency_score += it->GetLatencyScore();
719
720        if (it->m_reconsider) {
721            auto [_, added] = reconstructed_reconsiderable_wtxids.insert(it->m_tx->GetWitnessHash());
722            // Check that there is only ever 1 announcement per wtxid with m_reconsider set.
723            assert(added);
724        }
725    }
726    assert(reconstructed_peer_info.size() == m_peer_orphanage_info.size());
727
728    // Recalculated per-peer stats are identical to m_peer_orphanage_info
729    assert(reconstructed_peer_info == m_peer_orphanage_info);
730
731    // Recalculated set of reconsiderable wtxids must match.
732    assert(m_reconsiderable_wtxids == reconstructed_reconsiderable_wtxids);
733
734    // All outpoints exist in m_outpoint_to_orphan_wtxids, all keys in m_outpoint_to_orphan_wtxids correspond to some
735    // orphan, and all wtxids referenced in m_outpoint_to_orphan_wtxids are also in m_orphans.
736    // This ensures m_outpoint_to_orphan_wtxids is cleaned up.
737    assert(all_outpoints.size() == m_outpoint_to_orphan_wtxids.size());
738    for (const auto& [outpoint, wtxid_set] : m_outpoint_to_orphan_wtxids) {
739        assert(all_outpoints.contains(outpoint));
740        for (const auto& wtxid : wtxid_set) {
741            assert(unique_wtxids_to_scores.contains(wtxid));
742        }
743    }
744
745    // Cached m_unique_orphans value is correct.
746    assert(m_orphans.size() >= m_unique_orphans);
747    assert(m_orphans.size() <= m_peer_orphanage_info.size() * m_unique_orphans);
748    assert(unique_wtxids_to_scores.size() == m_unique_orphans);
749
750    const auto calculated_dedup_usage = std::accumulate(unique_wtxids_to_scores.begin(), unique_wtxids_to_scores.end(),