refactor: Drop g_orphan_list global #19374
Conversation
|
cc @sipa |
src/net_processing.cpp
Outdated
| size_t randompos = rng.randrange(g_orphan_list.size()); | ||
| EraseOrphanTx(g_orphan_list[randompos]->first); | ||
| auto iter = mapOrphanTransactions.begin(); | ||
| std::advance(iter, rng.randrange(mapOrphanTransactions.size())); |
There was a problem hiding this comment.
That's O(n) in the number of orphan transactions. I don't think that's acceptable.
There was a problem hiding this comment.
Even with given DEFAULT_MAX_ORPHAN_TRANSACTIONS = 100 ?
There was a problem hiding this comment.
Benchmarked on the custom branch:
- master
$ ./src/bench/bench_bitcoin -filter="OrphanTxPool"
# Benchmark, evals, iterations, total, min, max, median
OrphanTxPool, 5, 10000, 2.42326, 4.83155e-05, 4.87947e-05, 4.83993e-0
- this PR
$ ./src/bench/bench_bitcoin -filter="OrphanTxPool"
# Benchmark, evals, iterations, total, min, max, median
OrphanTxPool, 5, 10000, 2.95478, 5.87594e-05, 5.95669e-05, 5.9013e-05
There was a problem hiding this comment.
Thanks for providing actual numbers. I agree it's not so much of a concern in light of those - though I'm also not convinced it's worth the code simplification, especially if we'd ever want/need to increase the maximum number of orphans.
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. ConflictsReviewers, this pull request conflicts with the following ones:
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. |
|
So, am I correct that we have this redundant If that's the case, I don't have strong opinion here. The code seems correct, but the trade-offs I don't know. |
|
Updated 1263a64 -> 4286e39 (pr19374.01 -> pr19374.02, diff):
Benchmarking results (using #19377):
|
This change is required to replace std::map with std::unordered_map for mapOrphanTransactions as iterators could be invalidated on rehashing.
|
Updated 4286e39 -> 538a57f (pr19374.02 -> pr19374.03, diff):
|
Dropped g_orphan_list global. To get the random element from an std::unordered_map the fact is used that internal container hashes are uniformly distributed.
|
Updated 538a57f -> d02fcd0 (pr19374.03 -> pr19374.04, diff):
|
| for (const CTxIn& txin : tx->vin) { | ||
| mapOrphanTransactionsByPrev[txin.prevout].insert(ret.first); | ||
| mapOrphanTransactionsByPrev[txin.prevout].insert(hash); |
There was a problem hiding this comment.
It feels a little scary that we're adding references to a uint256 where the lifetime of that object is only as long as the transaction exists in the mapOrphanTransactions. The logic looks fine (and is the same as the existing logic where we're storing iterators which are only valid as long as the tx exists in mapOrphanTransactions), but it feels slightly dangerous.
There was a problem hiding this comment.
the lifetime of that object is only as long as the transaction exists in the mapOrphanTransactions
I think that is incorrect. The hash reference that we insert into mapOrphanTransactionsByPrev is created here:
bitcoin/src/net_processing.cpp
Line 897 in d02fcd0
and the GetHash() method returns a reference to its CTransaction::hash member:
bitcoin/src/primitives/transaction.h
Line 303 in d02fcd0
So, the reference is valid as long as the CTransaction object is valid (pointed to by the first argument of AddOrphanTx()).
Verifying whether the CTransaction object outlives the reference saved in mapOrphanTransactionsByPrev is a bit obscure.
Saving uint256 instead of uint256& looks more robust, also considering possible future changes. It would require 32 bytes instead of 8 (+24 bytes per transaction).
There was a problem hiding this comment.
the reference is valid as long as the CTransaction object is valid
Right, and I believe that for an orphan transaction, the only shared_ptr to the CTransaction is held in mapOrphanTransactions. As soon as it gets removed from that map, then the CTransaction will be destructed and the uint256& will be dangling.
Saving uint256 instead of uint256& looks more robust, also considering possible future changes. It would require 32 bytes instead of 8 (+24 bytes per transaction).
This would require an additional 24 bytes per transaction input, not per transaction.
There was a problem hiding this comment.
As soon as it gets removed from that map, then the CTransaction will be destructed and the uint256& will be dangling.
In EraseOrphanTx() a transaction is erased from mapOrphanTransactions only after its inputs have been erased from mapOrphanTransactionsByPrev().
So, no dangling uint256& are expected.
| { | ||
| nErased += EraseOrphanTx(maybeErase->second.tx->GetHash()); | ||
|
|
||
| std::vector<OrphanTxPool::iterator> erase_candidates; |
There was a problem hiding this comment.
why not make this a vector of uint256s?
There was a problem hiding this comment.
why not make this a vector of
uint256s?
std::vector<OrphanTxPool::iterator> is more effective (both time and memory), I think.
| }; | ||
| RecursiveMutex g_cs_orphans; | ||
| std::map<uint256, COrphanTx> mapOrphanTransactions GUARDED_BY(g_cs_orphans); | ||
| using OrphanTxPool = std::unordered_map<uint256, COrphanTx, SaltedTxidHasher>; |
There was a problem hiding this comment.
Since SaltedTxidHasher is no longer just used by the mempool, it should be moved out of txmempool.cpp. Maybe validation.cpp or primitives/transaction.cpp?
There was a problem hiding this comment.
... and maybe renamed because it is hashing uint256 which is broader than Txid?
| while (mapOrphanTransactions.size() > nMaxOrphans) | ||
| { | ||
| // Evict a random orphan: | ||
| size_t randompos = rng.randrange(g_orphan_list.size()); | ||
| EraseOrphanTx(g_orphan_list[randompos]->first); | ||
| EraseOrphanTx(mapOrphanTransactions.begin()->first); |
There was a problem hiding this comment.
I think this will exhibit different qualities from the current eviction logic. Currently, each eviction is an independent event, where every element has a 1/101 chance of being evicted. The new logic has dependent events. If a tx hashes to a bucket towards the end of the unordered_map, then it's unlikely to be evicted in any of these events, or put another way, if it doesn't get evicted in one round, the probability of it being evicted in a subsequent round is <1/101. I'm not sure if that's a problem.
|
I don't think the new random eviction logic leads to uniform independent events. See comment #19374 (comment). An alternative way to do this, which I think would be closer to uniform, independent events would be to go back to using an ordered map, but key by salted-txid. When the 101st transaction needs to be added to the map, then evict the tx with upper_bound of the salted-txid of the tx-to-be-inserted. We only ever evict an orphan transaction immediately after adding the 101st, and it should be fine to reverse that order (evict-then-insert rather than insert-then-evict). |
|
@jnewbery that is an interesting observation! BackgroundQuickly I thought that in the vector (before this PR) we insert at the end and remove a random element, whereas with the hash table (unordered_map, this PR) we insert at a random position and remove from the front, so it shouldn't make a difference. However, there is a catch! With the hash table we insert at a random position at the hash table array, which is not the same as "at a random position within the existent elements" (thanks for the elaboration over IM!). If the existent elements are grouped near the end of the hash table array, then inserting at a random position at that hash table array will likely make the new element the leftmost one (and so it will be evicted soon). And this is exactly what happens when we keep removing the leftmost elements - grouping near the end and very often removing the element we just added. StatsI gathered some statistics to verify the above - I did 100000x (
master @ 205b87d: pr @ d02fcd0: pr @ d02fcd0 + improvement suggested by @jnewbery: The improvement consists of using this container: class Cmp
{
public:
bool operator()(const uint256& lhs, const uint256& rhs) const {
return m_hasher(lhs) < m_hasher(rhs);
}
private:
const SaltedTxidHasher m_hasher;
};
using OrphanTxPool = std::map<uint256, COrphanTx, Cmp>;swapping the order of the calls to Analysis
VerdictLet's go with @jnewbery's improvement suggestion! |
Here is some explanation - the chance of a transaction surviving
|
|
Thanks for the very detailed investigation @vasild !
Right. In current master, eviction is a negative binomial distribution with r=1 and p=1/101. Each eviction is an independent Bernoulli trial, and as you point out, the chance of survival decreases geometrically over time. If you go to https://homepage.divms.uiowa.edu/~mbognar/applets/nb1.html and plug in r=1 and p=0.01, you'll see the expected graph. Evictions in the current branch of this PR are not independent events. As you insert random elements into the set and remove from the left, the set skews more and more to the right, so in future insert-and-remove-one events, the just-inserted element is more and more likely to be the leftmost. Eviction in my suggested change are also not perfectly independent events, but I expect they're 'good enough'. Adding an element to the set and removing the next along should keep the set randomly distributed across the entire range, so every element has ~equal chance of being removed in the next insert-and-remove-one event. |
|
What's the motivation for this change? It seems like an awful lot of work to save what seems to be a single pointer per orphan transaction... |
To achieve uniformity of transaction selection for its eviction from the orphan pool #14626 added the The recent changes are really unjustified. So closing. |
|
Just out of curiosity, here is the eviction distribution without #14626 revert #14626 on top of master @ 7d9008f and add samplingcommit 944e7a8a0 (HEAD -> master)
Parent: 5d1e3b803
Author: Hennadii Stepanov <32963518+hebasto@users.noreply.github.com>
AuthorDate: Fri Jun 26 18:09:27 2020 +0300
Commit: Vasil Dimov <vd@FreeBSD.org>
CommitDate: Fri Jul 3 11:02:51 2020 +0200
gpg: Signature made Fri Jul 3 11:02:58 2020 CEST
gpg: using RSA key E64D8D45614DB07545D9CCC154DF06F64B55CBBF
gpg: Good signature from "Vasil Dimov <vd@myforest.net>" [ultimate]
gpg: aka "Vasil Dimov <vd@FreeBSD.org>" [ultimate]
gpg: aka "Vasil Dimov <vasild@gmail.com>" [ultimate]
collect stats + test
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
index a9f5ce429..29a53be2e 100644
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -141,12 +141,20 @@ struct COrphanTx {
int64_t nTimeExpire;
size_t list_pos;
};
RecursiveMutex g_cs_orphans;
std::map<uint256, COrphanTx> mapOrphanTransactions GUARDED_BY(g_cs_orphans);
+// keys: transaction age at the time of its eviction from mapOrphanTransactions
+// values: number of transactions evicted that were that old
+std::map<uint32_t, uint32_t> g_eviction_ages;
+
+// keys: the age of the oldest transaction in mapOrphanTransactions when some tx is evicted
+// values: number of times this age was the maximum age after some tx is evicted
+std::map<uint32_t, uint32_t> g_max_ages;
+
void EraseOrphansFor(NodeId peer);
/** Increase a node's misbehavior score. */
void Misbehaving(NodeId nodeid, int howmuch, const std::string& message="") EXCLUSIVE_LOCKS_REQUIRED(cs_main);
// Internal stuff
@@ -932,12 +940,43 @@ bool AddOrphanTx(const CTransactionRef& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRE
LogPrint(BCLog::MEMPOOL, "stored orphan tx %s (mapsz %u outsz %u)\n", hash.ToString(),
mapOrphanTransactions.size(), mapOrphanTransactionsByPrev.size());
return true;
}
+void PrintOrphanStats() EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
+{
+ std::cout << "eviction_ages = np.array([";
+ for (const auto& e : g_eviction_ages) {
+ const auto& age = e.first;
+ std::cout << age << ",";
+ }
+ std::cout << "])" << std::endl;
+
+ std::cout << "eviction_counts = [";
+ for (const auto& e : g_eviction_ages) {
+ const auto& count = e.second;
+ std::cout << count << ",";
+ }
+ std::cout << "]" << std::endl;
+
+ std::cout << "max_ages = np.array([";
+ for (const auto& e : g_max_ages) {
+ const auto& age = e.first;
+ std::cout << age << ",";
+ }
+ std::cout << "])" << std::endl;
+
+ std::cout << "max_counts = [";
+ for (const auto& e : g_max_ages) {
+ const auto& count = e.second;
+ std::cout << count << ",";
+ }
+ std::cout << "]" << std::endl;
+}
+
int static EraseOrphanTx(uint256 hash) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
{
std::map<uint256, COrphanTx>::iterator it = mapOrphanTransactions.find(hash);
if (it == mapOrphanTransactions.end())
return 0;
for (const CTxIn& txin : it->second.tx->vin)
@@ -979,13 +1018,13 @@ void EraseOrphansFor(NodeId peer)
}
}
if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx from peer=%d\n", nErased, peer);
}
-unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans)
+unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans, uint32_t i)
{
LOCK(g_cs_orphans);
unsigned int nEvicted = 0;
static int64_t nNextSweep;
int64_t nNow = GetTime();
@@ -1012,12 +1051,24 @@ unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans)
{
// Evict a random orphan:
uint256 randomhash = rng.rand256();
std::map<uint256, COrphanTx>::iterator it = mapOrphanTransactions.lower_bound(randomhash);
if (it == mapOrphanTransactions.end())
it = mapOrphanTransactions.begin();
+
+ const uint32_t age_of_evicted = i - it->second.tx->nLockTime;
+ ++g_eviction_ages[age_of_evicted];
+ uint32_t oldest_tx_age = 0;
+ for (const auto& t : mapOrphanTransactions) {
+ const uint32_t current_tx_age = i - t.second.tx->nLockTime;
+ if (current_tx_age > oldest_tx_age) {
+ oldest_tx_age = current_tx_age;
+ }
+ }
+ ++g_max_ages[oldest_tx_age];
+
EraseOrphanTx(it->first);
++nEvicted;
}
return nEvicted;
}
@@ -2869,13 +2920,13 @@ void ProcessMessage(
if (!AlreadyHave(_inv, mempool)) RequestTx(State(pfrom.GetId()), _inv.hash, current_time);
}
AddOrphanTx(ptx, pfrom.GetId());
// DoS prevention: do not allow mapOrphanTransactions to grow unbounded (see CVE-2012-3789)
unsigned int nMaxOrphanTx = (unsigned int)std::max((int64_t)0, gArgs.GetArg("-maxorphantx", DEFAULT_MAX_ORPHAN_TRANSACTIONS));
- unsigned int nEvicted = LimitOrphanTxSize(nMaxOrphanTx);
+ unsigned int nEvicted = LimitOrphanTxSize(nMaxOrphanTx, 0);
if (nEvicted > 0) {
LogPrint(BCLog::MEMPOOL, "mapOrphan overflow, removed %u tx\n", nEvicted);
}
} else {
LogPrint(BCLog::MEMPOOL, "not keeping orphan with rejected parents %s\n",tx.GetHash().ToString());
// We will continue to reject this tx since it has rejected
diff --git a/src/test/denialofservice_tests.cpp b/src/test/denialofservice_tests.cpp
index 348b17053..75b59871c 100644
--- a/src/test/denialofservice_tests.cpp
+++ b/src/test/denialofservice_tests.cpp
@@ -40,14 +40,15 @@ struct CConnmanTest : public CConnman {
vNodes.clear();
}
};
// Tests these internal-to-net_processing.cpp methods:
extern bool AddOrphanTx(const CTransactionRef& tx, NodeId peer);
+extern void PrintOrphanStats();
extern void EraseOrphansFor(NodeId peer);
-extern unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans);
+extern unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans, uint32_t i);
extern void Misbehaving(NodeId nodeid, int howmuch, const std::string& message="");
struct COrphanTx {
CTransactionRef tx;
NodeId fromPeer;
int64_t nTimeExpire;
@@ -436,15 +437,40 @@ BOOST_AUTO_TEST_CASE(DoS_mapOrphans)
size_t sizeBefore = mapOrphanTransactions.size();
EraseOrphansFor(i);
BOOST_CHECK(mapOrphanTransactions.size() < sizeBefore);
}
// Test LimitOrphanTxSize() function:
- LimitOrphanTxSize(40);
+ LimitOrphanTxSize(40, 0);
BOOST_CHECK(mapOrphanTransactions.size() <= 40);
- LimitOrphanTxSize(10);
+ LimitOrphanTxSize(10, 0);
BOOST_CHECK(mapOrphanTransactions.size() <= 10);
- LimitOrphanTxSize(0);
+ LimitOrphanTxSize(0, 0);
BOOST_CHECK(mapOrphanTransactions.empty());
}
+BOOST_AUTO_TEST_CASE(lifetime)
+{
+ CKey key;
+ key.MakeNewKey(true);
+ FillableSigningProvider keystore;
+ BOOST_CHECK(keystore.AddKey(key));
+
+ for (uint32_t i = 0; i < 100000; i++) {
+ CMutableTransaction tx;
+ tx.vin.resize(1);
+ tx.vin[0].prevout.n = 0;
+ tx.vin[0].prevout.hash = InsecureRand256();
+ tx.vin[0].scriptSig << OP_1;
+ tx.vout.resize(1);
+ tx.vout[0].nValue = 1*CENT;
+ tx.vout[0].scriptPubKey = GetScriptForDestination(PKHash(key.GetPubKey()));
+ tx.nLockTime = i;
+
+ AddOrphanTx(MakeTransactionRef(tx), i);
+ LimitOrphanTxSize(100, i);
+ }
+
+ PrintOrphanStats();
+}
+
BOOST_AUTO_TEST_SUITE_END()
commit 5d1e3b803
Parent: 7d9008f43
Author: Vasil Dimov <vd@FreeBSD.org>
AuthorDate: Fri Jul 3 10:51:39 2020 +0200
Commit: Vasil Dimov <vd@FreeBSD.org>
CommitDate: Fri Jul 3 10:51:39 2020 +0200
gpg: Signature made Fri Jul 3 10:51:58 2020 CEST
gpg: using RSA key E64D8D45614DB07545D9CCC154DF06F64B55CBBF
gpg: Good signature from "Vasil Dimov <vd@myforest.net>" [ultimate]
gpg: aka "Vasil Dimov <vd@FreeBSD.org>" [ultimate]
gpg: aka "Vasil Dimov <vasild@gmail.com>" [ultimate]
revert part of https://github.com/bitcoin/bitcoin/pull/14626
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
index 80e58a6db..a9f5ce429 100644
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -1008,14 +1008,17 @@ unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans)
if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx due to expiration\n", nErased);
}
FastRandomContext rng;
B6EA
while (mapOrphanTransactions.size() > nMaxOrphans)
{
// Evict a random orphan:
- size_t randompos = rng.randrange(g_orphan_list.size());
- EraseOrphanTx(g_orphan_list[randompos]->first);
+ uint256 randomhash = rng.rand256();
+ std::map<uint256, COrphanTx>::iterator it = mapOrphanTransactions.lower_bound(randomhash);
+ if (it == mapOrphanTransactions.end())
+ it = mapOrphanTransactions.begin();
+ EraseOrphanTx(it->first);
++nEvicted;
}
return nEvicted;
}
/** |
This PR partially reverts changes from 7257353, but does not change the uniformly eviction behavior introduced in #14626.