Split orphan handling from net_processing into txorphanage

ajtowns commented at 1:42 am on February 11, 2021: member

Splits orphan handling into its own module and reduces global usage.

fanquake added the label P2P on Feb 11, 2021

ajtowns added the label Refactoring on Feb 11, 2021

DrahtBot commented at 5:54 am on February 11, 2021: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#21270 ([Bundle 4/n] Prune g_chainman usage in validation-adjacent modules by dongcarl)
#21224 ([p2p] Halt processing of unrequested transactions by ariard)
#21162 (Net Processing: Move RelayTransaction() into PeerManager by jnewbery)
#21160 (Net/Net processing: Move tx inventory into net_processing by jnewbery)
#21061 ([p2p] Introduce node rebroadcast module by amitiuttarwar)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

ajtowns force-pushed on Feb 15, 2021

ajtowns commented at 2:32 am on February 15, 2021: member

Rebased for conflict with #21062

jnewbery commented at 11:42 am on February 15, 2021: member

Concept ACK. Will review once this is rebased and out of draft status.

ajtowns force-pushed on Feb 15, 2021

ajtowns marked this as ready for review on Feb 15, 2021

ajtowns force-pushed on Feb 15, 2021

ajtowns commented at 2:24 pm on February 15, 2021: member

Rebased, tweaked the orphan code a little, and cleaned up the results some. Should be ready for review.

amitiuttarwar commented at 3:42 am on February 16, 2021: contributor

concept ACK, starting to review.

two thoughts for now-

I don’t quite understand the context of the first commit. There are other commits that are essentially move-only, so wondering how you grouped together the changes in that commit.
Are you open to some feedback around improvements of code you moved around? eg. using chrono instead of ints? or are you trying to keep the diff as minimal as possible? I personally think it’d be a good time for stuff that would be small, clear improvements, but won’t leave those sorts of review comments if you’re not interested :)

ajtowns commented at 7:30 am on February 17, 2021: member

@amitiuttarwar 1) The first commit just sets up the new files and moves whole functions / globals into it. Later commits are pulling code out into their own functions, restructuring functions into classes, etc. 2) hmm, I was ignoring chrono stuff since #21015 exists, but I guess it didn’t switch COrphanTx to chrono. Not sure it makes sense to add more things to this PR versus adding to the #20758 backlog. [EDIT: ie, feel free to add suggestions to 20758, but maybe this PR already has enough stuff in scope?]

DrahtBot added the label Needs rebase on Feb 20, 2021

ajtowns force-pushed on Feb 25, 2021

in src/txorphanage.cpp:10 in 649cad4fc8 outdated

 5+#include <txorphanage.h>
 6+
 7+#include <consensus/validation.h>
 8+#include <policy/policy.h>
 9+
10+#include <assert.h>

jnewbery commented at 10:18 am on February 25, 2021:

It’s generally recommended to include the c++ versions of the c headers:

0#include <cassert>

in src/txorphanage.cpp:157 in 649cad4fc8 outdated

152+
153+bool TxOrphanage::HaveTx(const GenTxid& gtxid)
154+{
155+    LOCK(g_cs_orphans);
156+    if (gtxid.IsWtxid()) {
157+        return m_wtxid_to_orphan_it.count(gtxid.GetHash()) > 0;

jnewbery commented at 10:59 am on February 25, 2021:

Possibly slightly more idiomatic to drop the > 0:

0        return m_wtxid_to_orphan_it.count(gtxid.GetHash());

Same below

in src/txorphanage.h:33 in 649cad4fc8 outdated

28+
29+    /** Check if we already have an orphan transaction (by txid or wtxid) */
30+    bool HaveTx(const GenTxid& gtxid) EXCLUSIVE_LOCKS_REQUIRED(!g_cs_orphans);
31+
32+    /** Get the details of an orphan transaction (returns nullptr if not found) */
33+    OrphanTx* GetTx(const uint256& txid) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);

jnewbery commented at 11:14 am on February 25, 2021:

This feels like it’s exposing too much of the internals to the caller. The pointer is only valid as long as m_orphans isn’t updated while it’s being held. That’s protected by g_cs_orphans, but it still feels unnecessary.

The only parts of OrphanTx that are needed by the caller in the one place this is used are the CTransactionRef and the NodeId, both of which are cheap to copy. How about:

0    /** Get a transation ref and originating peer for an orphan transaction
1      * (transaction ref will be nullptr if not found) */
2    std::pair<CTransactionRef, NodeId> GetTx(const uint256& txid) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);

 0iff --git a/src/net_processing.cpp b/src/net_processing.cpp
 1index df3de89094..b138844a50 100644
 2--- a/src/net_processing.cpp
 3+++ b/src/net_processing.cpp
 4@@ -2057,17 +2057,16 @@ void PeerManagerImpl::ProcessOrphanTx(std::set<uint256>& orphan_work_set)
 5         const uint256 orphanHash = *orphan_work_set.begin();
 6         orphan_work_set.erase(orphan_work_set.begin());
 7 
 8-        const TxOrphanage::OrphanTx* orphantx = m_orphanage.GetTx(orphanHash);
 9-        if (orphantx == nullptr) continue;
10+        auto [tx, from_peer] = m_orphanage.GetTx(orphanHash);
11+        if (!tx) continue;
12 
13-        const CTransactionRef porphanTx = orphantx->tx;
14-        const MempoolAcceptResult result = AcceptToMemoryPool(::ChainstateActive(), m_mempool, porphanTx, false /* bypass_limits */);
15+        const MempoolAcceptResult result = AcceptToMemoryPool(::ChainstateActive(), m_mempool, tx, false /* bypass_limits */);
16         const TxValidationState& state = result.m_state;
17 
18         if (result.m_result_type == MempoolAcceptResult::ResultType::VALID) {
19             LogPrint(BCLog::MEMPOOL, "   accepted orphan tx %s\n", orphanHash.ToString());
20-            RelayTransaction(orphanHash, porphanTx->GetWitnessHash(), m_connman);
21-            m_orphanage.AddChildrenToWorkSet(*porphanTx, orphan_work_set);
22+            RelayTransaction(orphanHash, tx->GetWitnessHash(), m_connman);
23+            m_orphanage.AddChildrenToWorkSet(*tx, orphan_work_set);
24             m_orphanage.EraseTx(orphanHash);
25             for (const CTransactionRef& removedTx : result.m_replaced_transactions.value()) {
26                 AddToCompactExtraTransactions(removedTx);
27@@ -2077,10 +2076,10 @@ void PeerManagerImpl::ProcessOrphanTx(std::set<uint256>& orphan_work_set)
28             if (state.IsInvalid()) {
29                 LogPrint(BCLog::MEMPOOL, "   invalid orphan tx %s from peer=%d. %s\n",
30                     orphanHash.ToString(),
31-                    orphantx->fromPeer,
32+                    from_peer,
33                     state.ToString());
34                 // Maybe punish peer that gave us an invalid orphan tx
35-                MaybePunishNodeForTx(orphantx->fromPeer, state);
36+                MaybePunishNodeForTx(from_peer, state);
37             }
38             // Has inputs but not accepted to mempool
39             // Probably non-standard or insufficient fee
40@@ -2100,7 +2099,7 @@ void PeerManagerImpl::ProcessOrphanTx(std::set<uint256>& orphan_work_set)
41                 // for concerns around weakening security of unupgraded nodes
42                 // if we start doing this too early.
43                 assert(recentRejects);
44-                recentRejects->insert(porphanTx->GetWitnessHash());
45+                recentRejects->insert(tx->GetWitnessHash());
46                 // If the transaction failed for TX_INPUTS_NOT_STANDARD,
47                 // then we know that the witness was irrelevant to the policy
48                 // failure, since this check depends only on the txid
49@@ -2109,10 +2108,10 @@ void PeerManagerImpl::ProcessOrphanTx(std::set<uint256>& orphan_work_set)
50                 // processing of this transaction in the event that child
51                 // transactions are later received (resulting in
52                 // parent-fetching by txid via the orphan-handling logic).
53-                if (state.GetResult() == TxValidationResult::TX_INPUTS_NOT_STANDARD && porphanTx->GetWitnessHash() != porphanTx->GetHash()) {
54+                if (state.GetResult() == TxValidationResult::TX_INPUTS_NOT_STANDARD && tx->GetWitnessHash() != tx->GetHash()) {
55                     // We only add the txid if it differs from the wtxid, to
56                     // avoid wasting entries in the rolling bloom filter.
57-                    recentRejects->insert(porphanTx->GetHash());
58+                    recentRejects->insert(tx->GetHash());
59                 }
60             }
61             m_orphanage.EraseTx(orphanHash);
62diff --git a/src/txorphanage.cpp b/src/txorphanage.cpp
63index a634bde953..a311984705 100644
64--- a/src/txorphanage.cpp
65+++ b/src/txorphanage.cpp
66@@ -160,13 +160,13 @@ bool TxOrphanage::HaveTx(const GenTxid& gtxid)
67     }
68 }
69 
70-TxOrphanage::OrphanTx* TxOrphanage::GetTx(const uint256& txid)
71+std::pair<CTransactionRef, NodeId> TxOrphanage::GetTx(const uint256& txid)
72 {
73     AssertLockHeld(g_cs_orphans);
74 
75     const auto it = m_orphans.find(txid);
76-    if (it == m_orphans.end()) return nullptr;
77-    return &it->second;
78+    if (it == m_orphans.end()) return {nullptr, 0};
79+    return {it->second.tx, it->second.fromPeer};
80 }
81 
82 void TxOrphanage::EraseForBlock(const CBlock& block)
83diff --git a/src/txorphanage.h b/src/txorphanage.h
84index f33415ad95..bf1249a154 100644
85--- a/src/txorphanage.h
86+++ b/src/txorphanage.h
87@@ -30,7 +30,7 @@ public:
88     bool HaveTx(const GenTxid& gtxid) EXCLUSIVE_LOCKS_REQUIRED(!g_cs_orphans);
89 
90     /** Get the details of an orphan transaction (returns nullptr if not found) */
91-    OrphanTx* GetTx(const uint256& txid) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);
92+    std::pair<CTransactionRef, NodeId> GetTx(const uint256& txid) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);
93 
94     /** Erase an orphan by txid */
95     int EraseTx(const uint256& txid) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);

ajtowns commented at 2:59 pm on February 26, 2021:

Done. First instance of structure binding in the codebase?

in src/txorphanage.cpp:200 in 649cad4fc8 outdated

194+    if (vOrphanErase.size()) {
195+        int nErased = 0;
196+        for (const uint256& orphanHash : vOrphanErase) {
197+            nErased += EraseTx(orphanHash);
198+        }
199+        LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx included or conflicted by block\n", nErased);

jnewbery commented at 11:17 am on February 25, 2021:

Can you include logging.h rather than relying on it being included transitively?

It might also make sense to change all these logs’ categories to NET at some point?

in src/txorphanage.h:36 in 649cad4fc8 outdated

37+
38+    /** Erase all orphans announced by a peer (eg, after that peer disconnects) */
39+    void EraseForPeer(NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);
40+
41+    /** Erase all orphans included in / invalidated by a new block */
42+    void EraseForBlock(const CBlock& block) EXCLUSIVE_LOCKS_REQUIRED(!g_cs_orphans);

jnewbery commented at 11:35 am on February 25, 2021:

This is using the definition for CBlock which is included transitively through txorphanage.h -> net.h -> chainparams.h -> primitives/block.h.

You could erase that dependency, so that the orphanage has no concept of blocks:

0    /** Erase orphans */
1    void EraseOrphans(const std::vector<CTransactionRef>& txs) EXCLUSIVE_LOCKS_REQUIRED(!g_cs_orphans);

And then calling this from net_processing with:

m_orphanage.EraseOrphans(pblock->vtx);

ajtowns commented at 3:04 pm on February 26, 2021:

Definite nack on the comment change – the function erases orphans that are double-spent by txs in the block, not just orphans that are included in the block directly.

I’m not against having vtx dereferenced in the caller, but the logic seems specific to a block arriving: if it were just an in-mempool tx double-spending an orphan tx, it might be that the orphan is actually a successful RBF and should be accepted once we know all its parents. So I think having it be the actual block as the argument makes sense; and since it’s a lightweight header that’s transitively included anyway, I’ve kept it as-is (but included the header explicitly).

jnewbery commented at 5:02 pm on February 26, 2021:

Ah, good point about erasing orphans that are conflicted by the block. I agree that it’s fine to keep this as it is.

Thanks for including primitives/block.h

in src/txorphanage.h:48 in 649cad4fc8 outdated

43+
44+    /** Limit the orphanage to the given maximum */
45+    unsigned int LimitOrphans(unsigned int max_orphans) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);
46+
47+    /** A set of orphans to be tested for potential acceptance into the mempool */
48+    using WorkSet = std::set<uint256>;

jnewbery commented at 11:41 am on February 25, 2021:

I’m not sure if this alias is very useful. It’s only used in two places.

in src/net_processing.cpp:1091 in 649cad4fc8 outdated

1087@@ -1119,10 +1088,10 @@ bool PeerManagerImpl::GetNodeStateStats(NodeId nodeid, CNodeStateStats &stats)
1088 
1089 //////////////////////////////////////////////////////////////////////////////
1090 //
1091-// mapOrphanTransactions
1092+// Orphan handling

jnewbery commented at 11:44 am on February 25, 2021:

If you’re touching this comment, then maybe just remove it. These section markers have long outlived their usefulness.

in src/net_processing.cpp:4951 in 649cad4fc8 outdated

4758@@ -4948,15 +4759,3 @@ bool PeerManagerImpl::SendMessages(CNode* pto)
4759     return true;
4760 }
4761 
4762-class CNetProcessingCleanup

jnewbery commented at 11:45 am on February 25, 2021:

:heart:

in src/test/denialofservice_tests.cpp:287 in 649cad4fc8 outdated

283@@ -295,15 +284,23 @@ BOOST_AUTO_TEST_CASE(DoS_bantime)
284     peerLogic->FinalizeNode(dummyNode, dummy);
285 }
286 
287-static CTransactionRef RandomOrphan()
288+class TxOrphanageTest : public TxOrphanage

jnewbery commented at 11:47 am on February 25, 2021:

It might make sense to move the orphanage unit tests into their own file now that txorphanage has been split out from net_processing?

ajtowns commented at 2:20 pm on February 26, 2021:

I think that would be a good idea for a later PR (particularly one that added more test coverage)

in src/net_processing.cpp:3129 in 649cad4fc8 outdated

3140@@ -3330,11 +3141,11 @@ void PeerManagerImpl::ProcessMessage(CNode& pfrom, const std::string& msg_type,
3141                 m_txrequest.ForgetTxHash(tx.GetHash());
3142                 m_txrequest.ForgetTxHash(tx.GetWitnessHash());
3143 
3144-                // DoS prevention: do not allow mapOrphanTransactions to grow unbounded (see CVE-2012-3789)
3145+                // DoS prevention: do not allow m_orphanage to grow unbounded (see CVE-2012-3789)
3146                 unsigned int nMaxOrphanTx = (unsigned int)std::max((int64_t)0, gArgs.GetArg("-maxorphantx", DEFAULT_MAX_ORPHAN_TRANSACTIONS));
3147-                unsigned int nEvicted = LimitOrphanTxSize(nMaxOrphanTx);
3148+                unsigned int nEvicted = m_orphanage.LimitOrphans(nMaxOrphanTx);

jnewbery commented at 11:51 am on February 25, 2021:

Doesn’t have to be in this PR, but perhaps a future PR could make nMaxOrphanTx a ctor argument, and then just call LimitOrphans() without an argument. This is the only place in the non-test code that LimitOrphans is called, and it’s always with the same argument.

In fact, once const nMaxOrphanTx is a member of the orphanage, we don’t need a LimitOrphans() call at all. We can just limit the size within the TxOrphanage::AddTx function.

ajtowns commented at 2:21 pm on February 26, 2021:

Not sure about the const part – it might make sense for the limit to change depending on how much pressure there is in the mempool at large. Agree otherwise.

amitiuttarwar commented at 2:45 am on March 2, 2021:

+1 came here to make a very similar suggestion :)

in src/net_processing.cpp:1105 in 649cad4fc8 outdated

1101@@ -1133,126 +1102,17 @@ static void AddToCompactExtraTransactions(const CTransactionRef& tx) EXCLUSIVE_L
1102     vExtraTxnForCompactIt = (vExtraTxnForCompactIt + 1) % max_extra_txn;
1103 }
1104 
1105-bool AddOrphanTx(const CTransactionRef& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
1106+bool PeerManagerImpl::AddOrphanTx(const CTransactionRef& tx, NodeId peer)

jnewbery commented at 11:56 am on February 25, 2021:

Consider just removing this function entirely:

it’s only called in one place
it consists of two function calls
the return value is discarded

ajtowns commented at 2:49 pm on February 26, 2021:

Dang, why didn’t I think of that.

jnewbery commented at 12:01 pm on February 25, 2021: member

utACK 649cad4fc8fcc107a02a5e448cf9495d38e18add

Mostly style comments, with a couple of requests for minor changes to the interface that I think would improve the encapsulation.

DrahtBot removed the label Needs rebase on Feb 25, 2021

move-only: Add txorphanage module

This module captures orphan tracking code for tx relay.

Can be reviewed with --color-moved=dimmed-zebra

9d5313df7e

txorphanage: Pass uint256 by reference instead of value 81dd57e5b1

txorphanage: Add lock annotations

EraseOrphansFor was called both with and without g_cs_orphans held,
correct that so that it's always called with it already held.

LimitOrphanTxSize was always called with g_cs_orphans held, so
add annotations and don't lock it a second time.

38a11c355a

txorphanage: Extract AddChildrenToWorkSet

Extract some common code into AddChildrenToWorkSet function.

(It's a hard knock life)

ee135c8d5b

txorphanage: Extract HaveOrphanTx

Extract some common code into HaveOrphanTx function.

83679ffc60

txorphanage: Extract GetOrphanTx

Extract orphan lookup code into GetOrphanTx function.

f294da7274

txorphanage: Extract OrphanageAddTx

Extract code from AddOrphanTx into OrphanageAddTx.

1041616d7e

denialofservices_tests: check txorphanage's AddTx

Rather than checking net_processing's internal implementation of
AddOrphanTx, test txorphanage's exported AddTx interface. Note that
this means AddToCompactExtraTransactions is no longer tested here.

26d1a6ccd5

net_processing: drop AddOrphanTx

All the interesting functionality of AddOrphanTx is already in other
functions, so call those functions directly in the one place that
AddOrphanTx was used.

3c4c3c2fdd

txorphanage: Extract EraseOrphansForBlock

Extract code that erases orphans when a new block is found into
EraseOrphansForBlock.

03257b832d

in src/txorphanage.h:22 in 649cad4fc8 outdated

17+class TxOrphanage {
18+public:
19+    struct OrphanTx {
20+        CTransactionRef tx;
21+        NodeId fromPeer;
22+        int64_t nTimeExpire;

glozow commented at 1:54 pm on February 25, 2021:

I think these could be const, they should never change?

0        const NodeId fromPeer;
1        const int64_t nTimeExpire;

ajtowns commented at 8:59 am on March 2, 2021:

The CTransactionRef tx could be const as well; the only entry that changes after insertion is list_pos. Not sure there’s much benefit to adding the const annotations for that though.

ajtowns force-pushed on Feb 26, 2021

ajtowns commented at 3:06 pm on February 26, 2021: member

Added most of jnewbery’s suggestions, and also added some missing const annotations on TxOrphanage methods.

txorphanage: Move functions and data into class

Collects all the orphan handling globals into a single member var in
net_processing, and ensures access is encapuslated into the interface
functions. Also adds doxygen comments for methods.

6bd4963c06

scripted-diff: Update txorphanage naming convention

-BEGIN VERIFY SCRIPT-
sed -i 's/mapOrphanTransactionsByPrev/m_outpoint_to_orphan_it/g' src/txorphanage.h src/txorphanage.cpp
sed -i 's/mapOrphanTransactions/m_orphans/g' src/txorphanage.h src/txorphanage.cpp src/net_processing.cpp src/test/denialofservice_tests.cpp
sed -i 's/g_orphan_list/m_orphan_list/g' src/txorphanage.h src/txorphanage.cpp
sed -i 's/g_orphans_by_wtxid/m_wtxid_to_orphan_it/g' src/txorphanage.h src/txorphanage.cpp
sed -i 's/nMaxOrphans/max_orphans/g' src/txorphanage.h src/txorphanage.cpp
sed -i 's/COrphanTx/OrphanTx/g' src/txorphanage.h src/txorphanage.cpp src/test/denialofservice_tests.cpp
-END VERIFY SCRIPT-

f8c0688b94

net_processing: move AddToCompactExtraTransactions into PeerManagerImpl

Allows making vExtraTxnForCompact and vExtraTxnForCompactIt member vars
instead of globals.

eeeafb324e

ajtowns force-pushed on Feb 26, 2021

in src/txorphanage.h:26 in eeeafb324e outdated

21+    bool AddTx(const CTransactionRef& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);
22+
23+    /** Check if we already have an orphan transaction (by txid or wtxid) */
24+    bool HaveTx(const GenTxid& gtxid) const EXCLUSIVE_LOCKS_REQUIRED(!g_cs_orphans);
25+
26+    /** Get the details of an orphan transaction (returns nullptr if not found) */

jnewbery commented at 9:32 am on February 27, 2021:

Perhaps update this comment to reflect the new return value:

0    /** Get a transation ref and originating peer for an orphan transaction
1      * (transaction ref will be nullptr if not found) */```

in src/txorphanage.h:35 in eeeafb324e outdated

30+    int EraseTx(const uint256& txid) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);
31+
32+    /** Erase all orphans announced by a peer (eg, after that peer disconnects) */
33+    void EraseForPeer(NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);
34+
35+    /** Erase all orphans included in / invalidated by a new block */

jnewbery commented at 9:41 am on February 27, 2021:

0    /** Erase all orphans included in or invalidated by a new block */

is slightly clearer. The / could be interpreted as ‘and’.

jnewbery commented at 10:04 am on February 27, 2021: member

utACK eeeafb324ef6057f40b5c5fdd8464110e809b0f7

Two tiny style suggestions inline.

The last commit (net_processing: move AddToCompactExtraTransactions into PeerManagerImpl) doesn’t really need to be in this PR. No harm in having it here, but could equally wait until the next PR (which could also change AddToCompactExtraTransactions(), vExtraTxnForCompact and vExtraTxnForCompactIt to be guarded by cs_main).

in src/txorphanage.h:73 in eeeafb324e outdated

68+    /** Index from the parents' COutPoint into the m_orphans. Used
69+     *  to remove orphan transactions from the m_orphans */
70+    std::map<COutPoint, std::set<OrphanMap::iterator, IteratorComparator>> m_outpoint_to_orphan_it GUARDED_BY(g_cs_orphans);
71+
72+    /** Orphan transactions in vector for quick random eviction */
73+    std::vector<OrphanMap::iterator> m_orphan_list GUARDED_BY(g_cs_orphans);

glozow commented at 7:42 pm on March 1, 2021:

~Question: Would using a std::list be simpler? It looks like we use list_pos + swapping with the last element to get better performance on random eviction in a vector, but why not just use a linked list?~

in src/txorphanage.h:77 in eeeafb324e outdated

72+    /** Orphan transactions in vector for quick random eviction */
73+    std::vector<OrphanMap::iterator> m_orphan_list GUARDED_BY(g_cs_orphans);
74+
75+    /** Index from wtxid into the m_orphans to lookup orphan
76+     *  transactions using their witness ids. */
77+    std::map<uint256, OrphanMap::iterator> m_wtxid_to_orphan_it GUARDED_BY(g_cs_orphans);

glozow commented at 7:50 pm on March 1, 2021:

Question: This data structure doesn’t seem entirely necessary to me… Would it be better to just have HaveTx search for the tx in m_orphans using std::find_if() and a predicate like [&, uint256 wtxid](OrphanTx& orphan) { return orphan.tx->GetWitnessHash() == wtxid } ?

amitiuttarwar commented at 2:36 am on March 2, 2021:

hmm, it seems like a tradeoff between memory & runtime complexity. the HaveTx lookup is currently logarithmic, but using a find_if would be linear. I’m guessing opting for the additional data structure was chosen to minimize the runtime impact on the program since we call this function so frequently (at least.. for every txid in inv messages, before we send a getdata, when processing a tx)

in src/txorphanage.h:16 in eeeafb324e outdated

11+#include <sync.h>
12+
13+/** Guards orphan transactions and extra txs for compact blocks */
14+extern RecursiveMutex g_cs_orphans;
15+
16+/** Data structure to keep track of orphan transactions

glozow commented at 8:29 pm on March 1, 2021:

Technically not guaranteed to be orphans? I think adding a bit more overall context could help someone looking at orphan handling for the first time (was the case for me)

0/** A class to temporarily track transactions we believe to be orphans (failed on TX_MISSING_INPUTS)
1* while we request the missing parent(s). Since we cannot distinguish orphans from bad transactions
2* with nonexistent inputs, we limit orphan count, size, and duration we'll keep them around for.

glozow commented at 9:05 pm on March 1, 2021: member

utACK eeeafb324e

I know this is mostly a move-only PR, but I kind of treated it as “a tour of orphan handling” so I have a bunch of questions, heh. Thanks for adding comments too!

in src/net_processing.cpp:1006 in 38a11c355a outdated

1002@@ -1003,7 +1003,7 @@ void PeerManagerImpl::FinalizeNode(const CNode& node, bool& fUpdateConnectionTim
1003     for (const QueuedBlock& entry : state->vBlocksInFlight) {
1004         mapBlocksInFlight.erase(entry.hash);
1005     }
1006-    EraseOrphansFor(nodeid);
1007+    WITH_LOCK(g_cs_orphans, EraseOrphansFor(nodeid));

amitiuttarwar commented at 0:58 am on March 2, 2021:

In commit 38a11c355acfc15134c682571b3d92f66b0e7c3c, “txorphanage: Add lock annotations”

Is the main advantage of moving where we grab g_cs_orphans from EraseOrphansFor into the call site in FinalizeNode to allow for the clang safety annotations / dynamic AssertLockHeld check? Since my understanding is that FinalizeNode is sometimes called with g_cs_orphans already held, so this doesn’t seem to reduce the recursive locking.

ajtowns commented at 9:31 am on March 2, 2021:

denialofservice_tests locks g_cs_orphans then calls EraseOrphansFor, so it would have required more changes to have EraseOrphansFor do the locking.

I don’t think FinalizeNode is called from anywhere that holds g_cs_orphans? Am I missing somewhere?

jnewbery commented at 11:39 am on March 2, 2021:

Here: https://github.com/bitcoin/bitcoin/blob/b9f41df1ead4b6a83a51fc41966b111c8459c313/src/init.cpp#L213-L214 ?

ajtowns commented at 1:33 pm on March 2, 2021:

Yes, that’s it!

StopNodes() calls DeleteNode() calls FinalizeNode() calls EraseForPeer(); with EraseForPeer needing g_cs_orphans. StopNodes locks cs_vNodes before calling DeleteNode, so g_cs_orphans has to be locked before calling CConnman::StopNodes but only if it’s linked to a PeerManagerImpl.

StopNodes is also called from ~CConnman so that path will still get a lock order violation error, I think.

DeleteNode is also called from DisconnectNodes which is called from ThreadSocketHandler; but there it’s called after cs_vNodes is released, so lock ordering is not an issue, but g_cs_orphans still has to get locked prior to doing the work in EraseForPeer, so responsibility can’t be moved all the way back up the chain.

So I don’t think there’s a simple way to make it non-recursive for this PR; for a future PR, I think the aim is to make g_cs_orphans become private: TxOrphanage::m_mutex and not have it be the last thing locked / first thing released so that the ordering constraint goes away, and then it should trivially be non-recursive.

jnewbery commented at 2:35 pm on March 2, 2021:

for a future PR, I think the aim is to make g_cs_orphans become private: TxOrphanage::m_mutex and not have it be the last thing locked / first thing released so that the ordering constraint goes away, and then it should trivially be non-recursive.

Concept ACK :)

ajtowns commented at 4:39 pm on March 2, 2021:

https://github.com/ajtowns/bitcoin/commits/202102-orphanworkset has work-in-progress that turns g_cs_orphans a protected m_mutex, doesn’t quite turn orphans back into the responsibility of who sent them rather than who sent their final parent though.

in src/net_processing.cpp:2107 in f294da7274 outdated

2103@@ -2104,10 +2104,9 @@ void PeerManagerImpl::ProcessOrphanTx(std::set<uint256>& orphan_work_set)
2104         const uint256 orphanHash = *orphan_work_set.begin();
2105         orphan_work_set.erase(orphan_work_set.begin());
2106 
2107-        auto orphan_it = mapOrphanTransactions.find(orphanHash);
2108-        if (orphan_it == mapOrphanTransactions.end()) continue;
2109+        const auto [porphanTx, from_peer] = GetOrphanTx(orphanHash);

amitiuttarwar commented at 1:31 am on March 2, 2021:

aw yeah, that structure binding ✨

sipa commented at 3:00 am on March 2, 2021:

Woah! I forgot we got that with C++17.

in src/txorphanage.h:33 in 6bd4963c06 outdated

46 
47-/** Map from txid to orphan transaction record. Limited by
48- *  -maxorphantx/DEFAULT_MAX_ORPHAN_TRANSACTIONS */
49-extern std::map<uint256, COrphanTx> mapOrphanTransactions GUARDED_BY(g_cs_orphans);
50+    /** Erase all orphans announced by a peer (eg, after that peer disconnects) */
51+    void EraseForPeer(NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);

amitiuttarwar commented at 2:13 am on March 2, 2021:

Is there a reason peer here and AddTx, EraseForPeer are non-const? I think they can be but since most things in this header are constified & it’s consistently the peer NodeId that’s not, I’m wondering if I’m missing something.

Also, I like the const member functions, that’s awesome for communicating/enforcing the intention of the functions.

ajtowns commented at 9:35 am on March 2, 2021:

I don’t usually add const to arguments that are passed by vaue rather than reference – it makes no difference to the caller; and not much difference to the implementation.

amitiuttarwar commented at 8:03 pm on March 2, 2021:

ah, right. thanks

amitiuttarwar commented at 2:49 am on March 2, 2021: contributor

code review ACK eeeafb324e

the orphanage is v. beautiful! my least favorite thing about it is the two-line if statements without parenthesis (they were copied over in move-only commits), but I’ll survive :)

txorphanage: comment improvements 5e50e2d1b9

ajtowns force-pushed on Mar 2, 2021

ajtowns commented at 9:43 am on March 2, 2021: member

Added a commit to update comments with suggestions. @jnewbery yeah, other commit could have been dropped – it was only there to move AddOrphan into PeerManagerImpl so that m_orphanage could also be in PeerManagerImpl, but that stopped being an issue after doing away with net_processing’s AddOrphan – but should be pretty harmless to leave it there.

jnewbery commented at 11:37 am on March 2, 2021: member

utACK 5e50e2d1b9

amitiuttarwar commented at 8:04 pm on March 2, 2021: contributor

utACK 5e50e2d1b95e7ca7709a9671ab21f1164b8d0cb8

glozow commented at 11:47 pm on March 2, 2021: member

re ACK https://github.com/bitcoin/bitcoin/pull/21148/commits/5e50e2d1b95e7ca7709a9671ab21f1164b8d0cb8, comment updates

laanwj commented at 9:16 am on March 4, 2021: member

the orphanage is v. beautiful! my least favorite thing about it is the two-line if statements without parenthesis (they were copied over in move-only commits), but I’ll survive :)

Yes I like how this cleanly encapsulates the transaction orphan handling, exposing a single documented interface in a small header file.

It is clearly an improvement. The only thing I don’t completely understand is why the g_cs_orphans lock is global and not on the orphanage itself, but maybe that’s too much impact? I think lock refactoring could be a topic for a future PR, anyhow, no need to hold this up.

Code review ACK 5e50e2d1b95e7ca7709a9671ab21f1164b8d0cb8

laanwj merged this on Mar 4, 2021

laanwj closed this on Mar 4, 2021

jnewbery commented at 10:13 am on March 4, 2021: member

The only thing I don’t completely understand is why the g_cs_orphans lock is global and not on the orphanage itself, but maybe that’s too much impact?

g_cs_orphans is still used to guard some objects outside the orphange (Peer.m_orphan_work_set and vExtraTxnForCompact). The plan is for future PRs to remove those dependencies and make the orphan mutex a member of the orphanage.

laanwj commented at 12:08 pm on March 4, 2021: member

@jnewbery Good to know, thanks!

in src/txorphanage.cpp:154 in 5e50e2d1b9

149+            }
150+        }
151+    }
152+}
153+
154+bool TxOrphanage::HaveTx(const GenTxid& gtxid) const

ariard commented at 2:37 pm on March 4, 2021:

Let’s say an attacker sends an invalid orphan Z to Alice. Such orphan will be stored in m_orphans until expiration time, random eviction or parent reception. Another honest peer Bob announce Z’s parent and Z through txid-relay to Alice. Announcement for Z from Bob won’t be scheduled for request by AddTxAnnouncement() as it’ll be bounced off before due to a positive AlreadyHaveTx().

If Bob sends a valid Z’s parent, it should be accepted but Alice’s version of Z will be rejected as invalid. Assuming Bob is initial broadcaster of Z and same trick is repeated against all his tx-relay peers, Z won’t propagate until next Bob rebroadcast.

Is the following description correct ? If yes, I don’t think that’s concerning, assuming Bob rebroadcast frequency is pretty high (which is the case for time-sensitive Bitcoin applications).

Though not introduced by this PR.

ajtowns commented at 8:40 am on March 7, 2021:

I think what you’re saying is: Bob has tx P (parent) and a child of that tx C. Mallory knows both and malleates the witness of C so that it creates a new invalid tx X that has the same txid as C but obviously a different wtxid. Mallory relays X to Alice before Alice hears about P or C. Alice adds X to the orphan pool and requests P from Mallory by wtxid.

I think the expected behaviour is then: Carol announces both P and C to Alice; if wtxid relay is active, both are announced via wtxid so don’t conflict with X, and both are requested. If the request for P from Mallory is still active, C will be requested first, and when we receive it, we’ll see there’s already an entry for that txid in the orphan pool and ignore it. I’m not sure if we’ll re-request from other honest peers at that point in normal usage; though I think this is a case where #21061 would eventually save the day.

ariard commented at 12:43 pm on March 8, 2021:

I’m not sure if we’ll re-request from other honest peers at that point in normal usage

Once the transaction is rejected from orphanage in reason of an already present orphan, we forget its txid/wtxid from tx-requester. So effectively, we shouldn’t re-request it from other onest peers at that stage. Ultimately, parent P withhold by Mallory should expire, Alice will fetch a valid parent P from another peer. When Bob rebroadcasts C, Mallory isn’t able to interfere anymore as malleated X will be rejected directly, without being logged in orphan pool.

Yes I agree #21061 should make things better.

in src/txorphanage.cpp:138 in 5e50e2d1b9

133+        // Evict a random orphan:
134+        size_t randompos = rng.randrange(m_orphan_list.size());
135+        EraseTx(m_orphan_list[randompos]->first);
136+        ++nEvicted;
137+    }
138+    return nEvicted;

ariard commented at 2:54 pm on March 4, 2021:

Couldn’t the “orphanage overflow” log L3131 in net_processing be moved here instead of returning nEvicted ? And change the message to dissociate clearly expiration-from-eviction.

in src/txorphanage.cpp:173 in 5e50e2d1b9

168+    const auto it = m_orphans.find(txid);
169+    if (it == m_orphans.end()) return {nullptr, -1};
170+    return {it->second.tx, it->second.fromPeer};
171+}
172+
173+void TxOrphanage::EraseForBlock(const CBlock& block)

ariard commented at 3:06 pm on March 4, 2021:

If we had a std::map<uint256, OrphanMap::iterator> m_parentid_to_orphan_it index we could update each peer’s orphan_work_set in function of the parent received through this block.

Otherwise, I think you might have stalling valid orphans never re-processed. Any ulterior parent announcement should be bounce off by m_recent_confirmed_transactions. Though rare enough to not be worthy of the complexity…

in src/txorphanage.h:29 in 5e50e2d1b9

24+    bool AddTx(const CTransactionRef& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans);
25+
26+    /** Check if we already have an orphan transaction (by txid or wtxid) */
27+    bool HaveTx(const GenTxid& gtxid) const EXCLUSIVE_LOCKS_REQUIRED(!g_cs_orphans);
28+
29+    /** Get an orphan transaction and its orginating peer

ariard commented at 3:07 pm on March 4, 2021:

nit: originating

ariard commented at 3:21 pm on March 4, 2021: member

Post-Merge Code Review ACK 5e50e2d

sidhujag referenced this in commit 97ba38785d on Mar 4, 2021

MarcoFalke commented at 11:12 am on March 5, 2021: member

pm ACK

MarcoFalke referenced this in commit 1ae65b4c5f on Apr 26, 2022

Fabcien referenced this in commit 88e2059986 on May 19, 2022

Fabcien referenced this in commit c387f12e99 on May 19, 2022

Fabcien referenced this in commit 20450c9649 on May 19, 2022

Fabcien referenced this in commit d621e806ab on May 19, 2022

Fabcien referenced this in commit 4c724a272e on May 19, 2022

Fabcien referenced this in commit 718ec97231 on May 19, 2022

Fabcien referenced this in commit c15f8c9cc4 on May 19, 2022

Fabcien referenced this in commit ec313f0eff on May 19, 2022

Fabcien referenced this in commit 48a4a4c730 on May 19, 2022

Fabcien referenced this in commit 66572c1f0d on May 19, 2022

Fabcien referenced this in commit 8b798a60c8 on May 19, 2022

Fabcien referenced this in commit 1af37678b5 on May 19, 2022

DrahtBot locked this on Aug 16, 2022

Split orphan handling from net_processing into txorphanage #21148

Conflicts