Tidy up ProcessOrphanTx #19498

jnewbery · 2020-07-12T10:30:29Z

Originally a follow-up to #19364, this simplifies the logic in ProcessOrphanTx() and removes unused variables.

jnewbery · 2020-07-12T10:32:39Z

@jonatack @troygiorshev - you both concept ACKed this branch in #19364.

jonatack

ACK on the doxygen comments. The pure refactoring changes seem ok. I hesitate with the commits where refactoring is mixed with behavior changes: are the behavior changes desirable in themselves or ignorable side effects; are the benefits worth the review and risk.

src/net_processing.cpp

DrahtBot · 2020-07-12T17:14:42Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

validation/util: add GetTransactionFee #20025 (validation/util: add GetTransactionFee by gzhao408)
net: guard vRecvGetData with cs_vRecv and orphan_work_set with g_cs_orphans #19911 (net: guard vRecvGetData with cs_vRecv and orphan_work_set with g_cs_orphans by narula)
validation: re-delegate absurd fee checking from mempool to clients #19339 (validation: re-delegate absurd fee checking from mempool to clients by gzhao408)

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.

jnewbery · 2020-07-12T17:15:57Z

are the behavior changes desirable in themselves or ignorable side effects

There are no observable functional changes. The behavior changes are simply in the timing of how items are popped off the orphan_work_set list. They make the control flow of the function much easier to follow. After these changes either:

orphan_work_set is empty and the function does nothing; or
the function pops one item off orphan_work_set and processes it.

jnewbery · 2020-07-15T09:48:57Z

rebased

jnewbery · 2020-07-16T09:36:06Z

rebased

jnewbery · 2020-07-23T10:07:37Z

rebased

troygiorshev

almost-ACK

+💯 to removing old outdated comments! 👏👏

Travis failure is unrelated

src/net_processing.cpp

jnewbery · 2020-07-24T08:12:44Z

Thanks for the review @troygiorshev . I've addressed your comment in the lastest force-push: https://github.com/bitcoin/bitcoin/compare/eb30f87e0972faae78df7c6116bc18f6fad7b353..833bccc522703f87d0d46b190a9a29bcb633c615

troygiorshev · 2020-07-24T11:26:20Z

tACK 833bccc via git range-diff master eb30f87 833bccc

amitiuttarwar

yay tidy! thanks for the cleanup and docs, the code makes more sense.

is my understanding correct that there is a v. small change in behavior in ProcessOrphanTx- previously, if an orphan taken off the orphan_work_set was not accepted to mempool bc of missing additional parents & there are more orphans in the work set, the while loop would continue & process the next one. with these changes it will consider max of one orphan per run. seems like an edge case & acceptable shift, but would like to confirm my understanding.

src/net_processing.cpp

amitiuttarwar · 2020-07-25T03:02:04Z

src/net_processing.cpp

+    /** Index from COutPoint into the mapOrphanTransactions. Used to remove
+     *  orphan transactions from the mapOrphanTransactions */
+    std::map<COutPoint, std::set<std::map<uint256, COrphanTx>::iterator, IteratorComparator>> mapOrphanTransactionsByPrev GUARDED_BY(g_cs_orphans);
+    /** Orphan transactions listed in random order for random eviction */


1/3 nit on this comment, 2/3 for my understanding-
these orphans aren't listed exactly random right? AddOrphanTx adds the entries to in the order they are seen, but EraseOrphanTx introduces some randomness bc it deletes an entry by swapping out the last element (which I'm still trying to understand the point of).

seems the point of this data structure is to enable LimitOrphanTxSize to easily choose a random orphan to erase by providing a vector interface?

if my understanding is correct, I think it'd be clearer to say "List of orphan transactions to enable random eviction"

these orphans aren't listed exactly random right?

if my understanding is correct, I think it'd be clearer to say "List of orphan transactions to enable random eviction"

You're correct. I've now fixed the comment. Thank you!

it deletes an entry by swapping out the last element (which I'm still trying to understand the point of)

This is because g_orphan_list is a std::vector, which is a contiguous-memory container. It can't have gaps in the underlying array. The normal way to erase an element from the middle of the vector is to delete it and then shift all the following elements forward by one position. That's expensive, and would invalidate all of the list_pos values that point back to a position in the vector. It's more efficient to copy the last element to the position of the element you want to delete, fix up the list_pos of just that COrphanTx, and then pop of the (now duplicate) last element.

does this sound right:

it seems to me that list_pos is tracked for this reason. so the alternative would be if we removed list_pos & used in the built in vector erase function. the tradeoff would be less efficiency.

the current design choice is to store this additional field on every COrphanTx to reduce an O(n) operation on the g_orphan_list vector, where n <= 100 | -maxorphantx. but I don't have much idea of how often we erase orphans in practice. so small increase in memory for small decrease in processing time?

Yes, this is the only reason we store list_pos. Without it, we'd have to do a (relatively) expensive erase from the middle of the vector.

src/net_processing.cpp

maflcko · 2020-09-07T07:14:58Z

Concept ACK

DrahtBot · 2020-09-07T17:40:10Z

🐙 This pull request conflicts with the target branch and needs rebase.

_{Want to unsubscribe from rebase notifications on this pull request? Just convert this pull request to a "draft".}

There is a keyword that allows us to break out of loops. Use it. There's a small change in behaviour here: if we process multiple orphans that are still orphans, then we'll only call mempool.check() once at the end, instead of after processing each tx.

This starts empty, and is only added to if we're about to exit the function (so we never read from it).

Also rename orphan_state to state. Both the comment and the variable name are leftover from when this logic was part of ProcessMessage().

…OrphanTx

jnewbery · 2020-09-07T19:13:09Z

Rebased

troygiorshev · 2020-09-23T02:50:35Z

ACK 001343f

This is a rather straightforward PR now.

sipa · 2020-09-30T01:08:09Z

utACK 001343f

maflcko · 2020-09-30T13:53:07Z

ACK 001343f 🌮

Show signature and timestamp

Signature:

Timestamp of file with hash bf74cbfe89c193a0e98cecd45019f0465bbd807c268f14767ecff37e07f76fe5 -

001343f ProcessOrphanTx: Move AddToCompactExtraTransactions call into ProcessOrphanTx (John Newbery) 4fce726 ProcessOrphanTx: Remove aliases (John Newbery) e07c5d9 ProcessOrphanTx: Remove outdated commented (John Newbery) 4763b51 ProcessOrphanTx: remove useless setMisbehaving set (John Newbery) 55c79a9 ProcessOrphanTx: remove useless done variable (John Newbery) 6e8dd99 [net processing] Add doxygen comments for orphan data and function (John Newbery) Pull request description: Originally a follow-up to bitcoin#19364, this simplifies the logic in ProcessOrphanTx() and removes unused variables. ACKs for top commit: troygiorshev: ACK 001343f sipa: utACK 001343f MarcoFalke: ACK 001343f 🌮 Tree-SHA512: be558457f2e08ebb6bddcd49bdd75bd410c3650da44a76c688fc9f07822f94d5a1af93fa1342678052b2c8163cdb9745c352c7884325ab0a41fa593c3eb89116

Summary: PR description: > Originally a follow-up to #19364, this simplifies the logic in ProcessOrphanTx() and removes unused variables. This is a backport of [[bitcoin/bitcoin#19498 | core#19498]] [1/5] bitcoin/bitcoin@6e8dd99 Note: The `removed_txn` parameter does not exist in ProcessOrphanTx in Bitcoin ABC. This part of the logic was dropped in D1175, and was already unused by then. It seems to be related to RBF (see [[https://github.com/bitcoin/bitcoin/pull/21062/commits/f82baf0762f60c2ca5ffc339b095f9271d7c2f33#diff-d3c243938494b10666b44404a27af7d84b44a72b85a27431e0c89e181462ca6eR200|following comment]]). The last commit of this PR only deals with this parameter, so it is not relevant to Bitcoin ABC. Test Plan: proofreading Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D10412

Summary: > There is a keyword that allows us to break out of loops. Use it. > > There's a small change in behaviour here: if we process multiple orphans > that are still orphans, then we'll only call mempool.check() once at the > end, instead of after processing each tx. This is a backport of [[bitcoin/bitcoin#19498 | core#19498]] [2/5] bitcoin/bitcoin@55c79a9 Depends on D10412 Test Plan: `ninja all check-all` Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Differential Revision: https://reviews.bitcoinabc.org/D10413

Summary: Original commit: > This starts empty, and is only added to if we're about to > exit the function (so we never read from it). In the Bitcoin ABC codebase, `setMisbehaving` was replaced with `rejectCountPerNode` in D2676, and in D6683 it stopped being used. This is a backport of [[bitcoin/bitcoin#19498 | core#19498]] [3/5] bitcoin/bitcoin@4763b51 Depends on D10413 Test Plan: `ninja all check-all` Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Subscribers: majcosta Differential Revision: https://reviews.bitcoinabc.org/D10414

Summary: Also rename orphan_state to state. Both the comment and the variable name are leftover from when this logic was part of ProcessMessage(). This is a backport of [[bitcoin/bitcoin#19498 | core#19498]] [4/5] bitcoin/bitcoin@e07c5d9 Depends on D10414 Test Plan: `ninja all check-all` Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Subscribers: majcosta Differential Revision: https://reviews.bitcoinabc.org/D10415

Summary: This is a backport of [[bitcoin/bitcoin#19498 | core#19498]] [5/5] bitcoin/bitcoin@4fce726 Depends on D10415 Test Plan: `ninja all check-all` Reviewers: #bitcoin_abc, majcosta Reviewed By: #bitcoin_abc, majcosta Subscribers: majcosta Differential Revision: https://reviews.bitcoinabc.org/D10416

fanquake added the P2P label Jul 12, 2020

jonatack reviewed Jul 12, 2020

View reviewed changes

src/net_processing.cpp Outdated Show resolved Hide resolved

src/net_processing.cpp Outdated Show resolved Hide resolved

src/net_processing.cpp Outdated Show resolved Hide resolved

This was referenced Jul 12, 2020

log: Properly log txs rejected from mempool #18990

Merged

refactor: replace CConnman pointers by references in net_processing.cpp #19174

Merged

DrahtBot added the Needs rebase label Jul 14, 2020

jnewbery force-pushed the 2020-07-orphan-tidy branch from 9c954f4 to 9f18dc3 Compare July 15, 2020 09:43

DrahtBot added Needs rebase and removed Needs rebase labels Jul 15, 2020

jnewbery force-pushed the 2020-07-orphan-tidy branch from 9f18dc3 to e26e8e8 Compare July 16, 2020 09:36

jnewbery removed the Needs rebase label Jul 16, 2020

This was referenced Jul 17, 2020

refactor: Replace RecursiveMutex with Mutex in CTxMemPool #19306

Closed

Revert "refactor: replace CConnman pointers by references in net_processing.cpp" #19542

Closed

Use wtxid for transaction relay #18044

Merged

DrahtBot added the Needs rebase label Jul 22, 2020

jnewbery force-pushed the 2020-07-orphan-tidy branch from e26e8e8 to eb30f87 Compare July 23, 2020 10:07

DrahtBot removed the Needs rebase label Jul 23, 2020

troygiorshev reviewed Jul 23, 2020

View reviewed changes

src/net_processing.cpp Outdated Show resolved Hide resolved

src/net_processing.cpp Outdated Show resolved Hide resolved

jnewbery force-pushed the 2020-07-orphan-tidy branch 3 times, most recently from eb30f87 to 833bccc Compare July 24, 2020 08:12

amitiuttarwar reviewed Jul 25, 2020

View reviewed changes

DrahtBot mentioned this pull request Jul 26, 2020

validation: re-delegate absurd fee checking from mempool to clients #19339

Merged

This was referenced Sep 4, 2020

scripted-diff: Restore AssertLockHeld after #19668, remove LockAssertion #19865

Closed

Avoid locking CTxMemPool::cs recursively in some cases #19872

Closed

maflcko added the Refactoring label Sep 7, 2020

DrahtBot added the Needs rebase label Sep 7, 2020

jnewbery added 6 commits September 7, 2020 19:55

[net processing] Add doxygen comments for orphan data and function

6e8dd99

ProcessOrphanTx: remove useless setMisbehaving set

4763b51

This starts empty, and is only added to if we're about to exit the function (so we never read from it).

ProcessOrphanTx: Remove outdated commented

e07c5d9

Also rename orphan_state to state. Both the comment and the variable name are leftover from when this logic was part of ProcessMessage().

ProcessOrphanTx: Remove aliases

4fce726

ProcessOrphanTx: Move AddToCompactExtraTransactions call into Process…

001343f

…OrphanTx

jnewbery force-pushed the 2020-07-orphan-tidy branch from e59bbcd to 001343f Compare September 7, 2020 19:12

jnewbery removed the Needs rebase label Sep 7, 2020

DrahtBot mentioned this pull request Sep 19, 2020

net: guard vRecvGetData with cs_vRecv and orphan_work_set with g_cs_orphans #19911

Merged

DrahtBot mentioned this pull request Sep 26, 2020

validation/util: add GetTransactionFee #20025

Closed

fanquake requested a review from amitiuttarwar September 30, 2020 05:23

maflcko merged commit 7b7cb70 into bitcoin:master Sep 30, 2020

jnewbery deleted the 2020-07-orphan-tidy branch September 30, 2020 14:02

bitcoin locked as resolved and limited conversation to collaborators Feb 15, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Tidy up ProcessOrphanTx #19498

Tidy up ProcessOrphanTx #19498

jnewbery commented Jul 12, 2020

jnewbery commented Jul 12, 2020

jonatack left a comment

DrahtBot commented Jul 12, 2020 •

edited

Loading

jnewbery commented Jul 12, 2020

jnewbery commented Jul 15, 2020

jnewbery commented Jul 16, 2020

jnewbery commented Jul 23, 2020

troygiorshev left a comment

jnewbery commented Jul 24, 2020

troygiorshev commented Jul 24, 2020

amitiuttarwar left a comment

amitiuttarwar Jul 25, 2020

jnewbery Jul 27, 2020

amitiuttarwar Jul 27, 2020 •

edited by jnewbery

Loading

jnewbery Jul 28, 2020

maflcko commented Sep 7, 2020

DrahtBot commented Sep 7, 2020

jnewbery commented Sep 7, 2020

troygiorshev commented Sep 23, 2020

sipa commented Sep 30, 2020

maflcko commented Sep 30, 2020

Tidy up ProcessOrphanTx #19498

Tidy up ProcessOrphanTx #19498

Conversation

jnewbery commented Jul 12, 2020

jnewbery commented Jul 12, 2020

jonatack left a comment

Choose a reason for hiding this comment

DrahtBot commented Jul 12, 2020 • edited Loading

Conflicts

jnewbery commented Jul 12, 2020

jnewbery commented Jul 15, 2020

jnewbery commented Jul 16, 2020

jnewbery commented Jul 23, 2020

troygiorshev left a comment

Choose a reason for hiding this comment

jnewbery commented Jul 24, 2020

troygiorshev commented Jul 24, 2020

amitiuttarwar left a comment

Choose a reason for hiding this comment

amitiuttarwar Jul 25, 2020

Choose a reason for hiding this comment

jnewbery Jul 27, 2020

Choose a reason for hiding this comment

amitiuttarwar Jul 27, 2020 • edited by jnewbery Loading

Choose a reason for hiding this comment

jnewbery Jul 28, 2020

Choose a reason for hiding this comment

maflcko commented Sep 7, 2020

DrahtBot commented Sep 7, 2020

jnewbery commented Sep 7, 2020

troygiorshev commented Sep 23, 2020

sipa commented Sep 30, 2020

maflcko commented Sep 30, 2020

DrahtBot commented Jul 12, 2020 •

edited

Loading

amitiuttarwar Jul 27, 2020 •

edited by jnewbery

Loading