aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorPieter Wuille <pieter.wuille@gmail.com>2018-10-31 17:24:38 -0700
committerPieter Wuille <pieter.wuille@gmail.com>2018-12-13 13:46:33 -0800
commit7257353b93e9f45e67071b0b86a0313e7a70aaaa (patch)
tree24a754e18aa3701d608d824182b1c55a5746d654 /src
parent9a4334443085970a42792db3528695585fe7053b (diff)
Select orphan transaction uniformly for eviction
The previous code was biased towards evicting transactions whose txid has a larger gap (lexicographically) with the previous txid in the orphan pool.
Diffstat (limited to 'src')
-rw-r--r--src/net_processing.cpp25
1 files changed, 19 insertions, 6 deletions
diff --git a/src/net_processing.cpp b/src/net_processing.cpp
index 0e222bdfa4..17e8578f57 100644
--- a/src/net_processing.cpp
+++ b/src/net_processing.cpp
@@ -69,6 +69,7 @@ struct COrphanTx {
CTransactionRef tx;
NodeId fromPeer;
int64_t nTimeExpire;
+ size_t list_pos;
};
CCriticalSection g_cs_orphans;
std::map<uint256, COrphanTx> mapOrphanTransactions GUARDED_BY(g_cs_orphans);
@@ -170,6 +171,8 @@ namespace {
};
std::map<COutPoint, std::set<std::map<uint256, COrphanTx>::iterator, IteratorComparator>> mapOrphanTransactionsByPrev GUARDED_BY(g_cs_orphans);
+ std::vector<std::map<uint256, COrphanTx>::iterator> g_orphan_list GUARDED_BY(g_cs_orphans); //! For random eviction
+
static size_t vExtraTxnForCompactIt GUARDED_BY(g_cs_orphans) = 0;
static std::vector<std::pair<uint256, CTransactionRef>> vExtraTxnForCompact GUARDED_BY(g_cs_orphans);
} // namespace
@@ -706,8 +709,9 @@ bool AddOrphanTx(const CTransactionRef& tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRE
return false;
}
- auto ret = mapOrphanTransactions.emplace(hash, COrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME});
+ auto ret = mapOrphanTransactions.emplace(hash, COrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME, g_orphan_list.size()});
assert(ret.second);
+ g_orphan_list.push_back(ret.first);
for (const CTxIn& txin : tx->vin) {
mapOrphanTransactionsByPrev[txin.prevout].insert(ret.first);
}
@@ -733,6 +737,18 @@ int static EraseOrphanTx(uint256 hash) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
if (itPrev->second.empty())
mapOrphanTransactionsByPrev.erase(itPrev);
}
+
+ size_t old_pos = it->second.list_pos;
+ assert(g_orphan_list[old_pos] == it);
+ if (old_pos + 1 != g_orphan_list.size()) {
+ // Unless we're deleting the last entry in g_orphan_list, move the last
+ // entry to the position we're deleting.
+ auto it_last = g_orphan_list.back();
+ g_orphan_list[old_pos] = it_last;
+ it_last->second.list_pos = old_pos;
+ }
+ g_orphan_list.pop_back();
+
mapOrphanTransactions.erase(it);
return 1;
}
@@ -783,11 +799,8 @@ unsigned int LimitOrphanTxSize(unsigned int nMaxOrphans)
while (mapOrphanTransactions.size() > 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();
- EraseOrphanTx(it->first);
+ size_t randompos = rng.randrange(g_orphan_list.size());
+ EraseOrphanTx(g_orphan_list[randompos]->first);
++nEvicted;
}
return nEvicted;