TxOrphanage: account for size of orphans and count announcements

glozow commented at 2:14 pm on February 6, 2025: member

Part of orphan resolution project, see #27463.

Definitions:

Announcement is a unique pair (wtxid, nodeid). We can have multiple announcers for the same orphan since #31397.
Size is the weight of an orphan. I’m calling it “size” and “bytes” because I think we can refine it in the future to be memusage or be otherwise more representative of the orphan’s actual cost on our memory. However, I am open to naming changes.

This is part 1/2 of a project to also add limits on orphan size and count. However, this PR does not change behavior, just adds internal counters/tracking and a fuzzer. I will also open a second PR that adds behavior changes, which requires updating a lot of our tests and careful thinking about DoS.

glozow added the label P2P on Feb 6, 2025

DrahtBot commented at 2:14 pm on February 6, 2025: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/31810.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	marcofleon, instagibbs, sipa

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

in src/txorphanage.h:105 in 52f4985d22 outdated

100     struct OrphanTx : public OrphanTxBase {
101         size_t list_pos;
102     };
103 
104+    /** Total size of all entries in m_orphans. */
105+    unsigned int m_total_orphan_size{0};

instagibbs commented at 2:32 pm on February 6, 2025:

can we at least internally call it weight, even if externally we don’t?

glozow commented at 7:59 pm on February 6, 2025:

So m_total_orphan_weight, PeerOrphanInfo::m_total_weight?

Are BytesFromPeer and TotalOrphanBytes ok? Or do we want WeightFromPeer and TotalOrphanWeight? Or maybe UsageByPeer and TotalOrphanUsage?

instagibbs commented at 8:09 pm on February 6, 2025:

I like Usage :+1:

glozow commented at 8:17 pm on February 6, 2025:

m_total_orphan_usage, m_total_usage, UsageByPeer, TotalOrphanUsage?

glozow commented at 8:46 pm on February 6, 2025:

done

fanquake added this to the milestone 29.x on Feb 6, 2025

fanquake requested review from instagibbs on Feb 6, 2025

in src/test/fuzz/txorphan.cpp:206 in 76af0b4d99 outdated

202@@ -158,6 +203,7 @@ FUZZ_TARGET(txorphan, .init = initialize_orphanage)
203                     Assert(orphanage.Size() <= limit);
204                 });
205 
206+            orphanage.SanityCheck();

dergoegge commented at 3:04 pm on February 6, 2025:

nit: Sanity checking is always better to do after a loop like this, as it doesn’t increase the oracle power and just makes the test slower

glozow commented at 7:56 pm on February 6, 2025:

Moved out of the loop

in src/txorphanage.cpp:336 in 76af0b4d99 outdated

329+
330+    // Check that cached PeerOrphanInfo::m_total_size is correct
331+    std::map<NodeId, unsigned int> counted_size_per_peer;
332+
333+    for (const auto& [wtxid, orphan] : m_orphans) {
334+        counted_total_announcements += orphan.announcers.size();

instagibbs commented at 3:12 pm on February 6, 2025:

nit: can assert number of announcers must be non-0 while we’re here.

in src/txorphanage.h:108 in 76af0b4d99 outdated

103@@ -104,6 +104,10 @@ class TxOrphanage {
104         return peer_it == m_peer_orphanage_info.end() ? 0 : peer_it->second.m_total_size;
105     }
106 
107+    /** Check consistency between PeerOrphanInfo and m_orphans. Recalculate counters and ensure they
108+     * match. what is cached. */

instagibbs commented at 3:15 pm on February 6, 2025:

extra period?

in src/test/fuzz/txorphan.cpp:129 in 03ff11cae3 outdated

124+                            Assert(orphanage.TotalOrphanBytes() == tx_weight + total_bytes_start);
125+                            Assert(tx_weight <= MAX_STANDARD_TX_WEIGHT);
126+                        } else {
127+                            // Peer may have been added as an announcer.
128+                            if (orphanage.BytesFromPeer(peer_id) == tx_weight + total_peer_bytes_start) {
129+                                Assert(orphanage.HaveTxFromPeer(tx->GetWitnessHash(), peer_id));

instagibbs commented at 3:17 pm on February 6, 2025:

can use wtxid here

in src/test/fuzz/txorphan.cpp:190 in 03ff11cae3 outdated

186                     have_tx = orphanage.HaveTx(tx->GetWitnessHash());
187+                    have_tx_and_peer = orphanage.HaveTxFromPeer(wtxid, peer_id);
188                     // have_tx should be false and EraseTx should fail
189                     {
190-                        Assert(!have_tx && !orphanage.EraseTx(tx->GetWitnessHash()));
191+                        Assert(!have_tx && !have_tx_and_peer && !orphanage.EraseTx(tx->GetWitnessHash()));

instagibbs commented at 3:17 pm on February 6, 2025:

can use wtxid here

in src/txorphanage.cpp:347 in 76af0b4d99 outdated

338+            auto& count_peer_entry = counted_size_per_peer.try_emplace(peer).first->second;
339+            count_peer_entry += orphan.GetSize();
340+        }
341+    }
342+
343+    Assume(counted_total_announcements == m_total_announcements);

instagibbs commented at 3:26 pm on February 6, 2025:

while we’re here could also assert m_total_announcements >= m_total_orphan_size

glozow commented at 7:53 pm on February 6, 2025:

That doesn’t seem likely to be true? Do you mean >= m_orphans.size()?

instagibbs commented at 7:54 pm on February 6, 2025:

oops, yes

glozow commented at 7:56 pm on February 6, 2025:

(I added that instead)

instagibbs approved

instagibbs commented at 3:28 pm on February 6, 2025: member

ACK 76af0b4d993c3a5a4a9c37f40d85b9996b38e7a0

Agree with #31810 (review)

and up for litigating the naming of size vs weight.

glozow force-pushed on Feb 6, 2025

in src/txorphanage.cpp:89 in e27c94d335 outdated

83@@ -80,6 +84,11 @@ int TxOrphanage::EraseTx(const Wtxid& wtxid)
84 
85     const auto tx_size{it->second.GetSize()};
86     m_total_orphan_size -= tx_size;
87+    // Decrement each announcer's m_total_size
88+    for (const auto& peer : it->second.announcers) {
89+        auto& peer_info = m_peer_orphanage_info.try_emplace(peer).first->second;

sipa commented at 8:02 pm on February 6, 2025:

Is the try_emplace necessary here? Given that we’re immediately decrementing peer_info.m_total_size after, I think the assumption is that the m_peer_orphanage_info object for peer peer must already exist here, so a find should suffice?

glozow commented at 8:47 pm on February 6, 2025:

good point, done

in src/txorphanage.h:131 in e27c94d335 outdated

126+        /** Total weight of orphans for which this peer is an announcer.
127+         * If orphans are provided by different peers, its weight will be accounted for in each
128+         * PeerOrphanInfo, so the total of all peers' m_total_size may be larger than
129+         * m_total_orphan_size. If a peer is removed as an announcer, even if the orphan still
130+         * remains in the orphanage, this number will be decremented. */
131+        unsigned int m_total_size{0};

sipa commented at 8:26 pm on February 6, 2025:

It looks like there is no accounting for the number of announcements per peer? Is the idea that we use the m_work_set.size() as overestimate? If so, can the SanityCheck verify that for every (wtxid, peer) announcement pair, a wtxid entry exists in peer’s m_work_set?

glozow commented at 8:37 pm on February 6, 2025:

The work set isn’t really tied to m_orphans, as it can include orphans that have been erased, so I don’t think that would make sense.

I’m planning to make m_orphan_list a per-peer thing and use the size() of that as the announcement count per peer. I will add a loop to SanityCheck() then to ensure it is consistent with m_orphans.

[txorphanage] account for weight of orphans 59cd0f0e09

[refactor] change per-peer workset to info map within orphanage

No change for now, moving from map of NodeId->workset to
NodeId->PeerOrphanInfo struct that holds the workset.

In future commits, we will start tracking more things per-peer in the
orphanage.

672c69c688

[txorphanage] add per-peer weight accounting e5ea7daee0

[txorphanage] track the total number of announcements c289217c01

add orphanage byte accounting to TxDownloadManagerImpl::CheckIsEmpty() 982ce10178

[fuzz] txorphan byte accounting

Co-authored-by: Greg Sanders <gsanders87@gmail.com>

22dccea553

glozow force-pushed on Feb 6, 2025

marcofleon commented at 3:47 pm on February 7, 2025: contributor

Code review ACK 2a279acd89fa37fec94c66dde7408a3a9627f49a

Confirmed that there’s no behavior change. This PR is adding tracking of total tx weight in the orphan map, total announcements, and the total weight of announced orphans for each peer. I ran the updated txorphan and txdownloadman_impl fuzz tests for ~120 cpu hours each.

nit: I believe that CheckInvariants() could be outside of the loop in the txdownloadman_impl harness and have the same checking power, which should speed up the test a bit.

DrahtBot requested review from instagibbs on Feb 7, 2025

fanquake removed this from the milestone 29.x on Feb 7, 2025

fanquake added this to the milestone 29.0 on Feb 7, 2025

in src/test/fuzz/txorphan.cpp:207 in 2a279acd89 outdated

203@@ -159,6 +204,8 @@ FUZZ_TARGET(txorphan, .init = initialize_orphanage)
204                 });
205 
206         }
207+        orphanage.SanityCheck();

instagibbs commented at 5:51 pm on February 7, 2025:

nit: this could be moved completely outside the loops for the same checking power

glozow commented at 5:58 pm on February 7, 2025:

Isn’t it already out of the loop?

glozow commented at 6:01 pm on February 7, 2025:

Oh nvm, there are 2 loops, yes

glozow commented at 6:56 pm on February 7, 2025:

done

instagibbs approved

instagibbs commented at 5:51 pm on February 7, 2025: member

reACK 2a279acd89fa37fec94c66dde7408a3a9627f49a

[fuzz] TxOrphanage::SanityCheck accounting e107bf78f9

glozow force-pushed on Feb 7, 2025

glozow commented at 6:57 pm on February 7, 2025: member

nit: I believe that CheckInvariants() could be outside of the loop in the txdownloadman_impl harness

the checks are now out of the loop

marcofleon commented at 7:16 pm on February 7, 2025: contributor

reACK e107bf78f9d722fcdeb5c1fba5a784dd7747e12f

DrahtBot requested review from instagibbs on Feb 7, 2025

instagibbs commented at 7:27 pm on February 7, 2025: member

reACK https://github.com/bitcoin/bitcoin/pull/31810/commits/e107bf78f9d722fcdeb5c1fba5a784dd7747e12f

in src/txorphanage.h:106 in 59cd0f0e09 outdated

101     struct OrphanTx : public OrphanTxBase {
102         size_t list_pos;
103     };
104 
105+    /** Total usage (weight) of all entries in m_orphans. */
106+    unsigned int m_total_orphan_usage{0};

sipa commented at 9:33 pm on February 7, 2025:

If we permit 4MWu per-peer reservation, and have a 1000 peers, we’re not very far away from the unsigned int limit $2^{32}-1$. We were thinking about using only 1/10 of that for inbound, so we’re really still a factor 10x away, but that still feels close enough that perhaps this should be an int64_t instead.

(can be done as a follow-up, since this isn’t a concern with the current orphan eviction policies)

glozow commented at 1:13 pm on February 10, 2025:

Changed to int64_t in #31829

in src/txorphanage.h:132 in e5ea7daee0 outdated

127+        /** Total weight of orphans for which this peer is an announcer.
128+         * If orphans are provided by different peers, its weight will be accounted for in each
129+         * PeerOrphanInfo, so the total of all peers' m_total_usage may be larger than
130+         * m_total_orphan_size. If a peer is removed as an announcer, even if the orphan still
131+         * remains in the orphanage, this number will be decremented. */
132+        unsigned int m_total_usage{0};

sipa commented at 9:51 pm on February 7, 2025:

Similar comment as for the global usage account: if that becomes a 64-bit integer, it may be best to do the same here (because when the global limit is not reached, nothing will prevent a single peer from consuming the full global limit).

Similarly, can be done in a follow-up.

in src/txorphanage.cpp:339 in e107bf78f9

334+
335+    for (const auto& [wtxid, orphan] : m_orphans) {
336+        counted_total_announcements += orphan.announcers.size();
337+        counted_total_usage += orphan.GetUsage();
338+
339+        Assume(!orphan.announcers.empty());

sipa commented at 10:01 pm on February 7, 2025:

If we want to (eventually) call this function in functional tests or so, outside of fuzz tests, using Assert() is better than Assume() (as the the latter won’t do anything outside of test builds).

sipa commented at 10:01 pm on February 7, 2025: member

utACK e107bf78f9d722fcdeb5c1fba5a784dd7747e12f

Just nits.

fanquake merged this on Feb 10, 2025

fanquake closed this on Feb 10, 2025

glozow deleted the branch on Feb 10, 2025

glozow commented at 1:13 pm on February 10, 2025: member

Next PR is #31829

TxOrphanage: account for size of orphans and count announcements #31810

Code Coverage & Benchmarks

Reviews