Bitcoin Core  22.99.0
P2P Digital Currency
txorphanage.cpp
Go to the documentation of this file.
1 // Copyright (c) 2021 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #include <txorphanage.h>
6 
7 #include <consensus/validation.h>
8 #include <logging.h>
9 #include <policy/policy.h>
10 
11 #include <cassert>
12 
14 static constexpr int64_t ORPHAN_TX_EXPIRE_TIME = 20 * 60;
16 static constexpr int64_t ORPHAN_TX_EXPIRE_INTERVAL = 5 * 60;
17 
19 
21 {
23 
24  const uint256& hash = tx->GetHash();
25  if (m_orphans.count(hash))
26  return false;
27 
28  // Ignore big transactions, to avoid a
29  // send-big-orphans memory exhaustion attack. If a peer has a legitimate
30  // large transaction with a missing parent then we assume
31  // it will rebroadcast it later, after the parent transaction(s)
32  // have been mined or received.
33  // 100 orphans, each of which is at most 100,000 bytes big is
34  // at most 10 megabytes of orphans and somewhat more byprev index (in the worst case):
35  unsigned int sz = GetTransactionWeight(*tx);
36  if (sz > MAX_STANDARD_TX_WEIGHT)
37  {
38  LogPrint(BCLog::MEMPOOL, "ignoring large orphan tx (size: %u, hash: %s)\n", sz, hash.ToString());
39  return false;
40  }
41 
42  auto ret = m_orphans.emplace(hash, OrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME, m_orphan_list.size()});
43  assert(ret.second);
44  m_orphan_list.push_back(ret.first);
45  // Allow for lookups in the orphan pool by wtxid, as well as txid
46  m_wtxid_to_orphan_it.emplace(tx->GetWitnessHash(), ret.first);
47  for (const CTxIn& txin : tx->vin) {
48  m_outpoint_to_orphan_it[txin.prevout].insert(ret.first);
49  }
50 
51  LogPrint(BCLog::MEMPOOL, "stored orphan tx %s (mapsz %u outsz %u)\n", hash.ToString(),
52  m_orphans.size(), m_outpoint_to_orphan_it.size());
53  return true;
54 }
55 
56 int TxOrphanage::EraseTx(const uint256& txid)
57 {
59  std::map<uint256, OrphanTx>::iterator it = m_orphans.find(txid);
60  if (it == m_orphans.end())
61  return 0;
62  for (const CTxIn& txin : it->second.tx->vin)
63  {
64  auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout);
65  if (itPrev == m_outpoint_to_orphan_it.end())
66  continue;
67  itPrev->second.erase(it);
68  if (itPrev->second.empty())
69  m_outpoint_to_orphan_it.erase(itPrev);
70  }
71 
72  size_t old_pos = it->second.list_pos;
73  assert(m_orphan_list[old_pos] == it);
74  if (old_pos + 1 != m_orphan_list.size()) {
75  // Unless we're deleting the last entry in m_orphan_list, move the last
76  // entry to the position we're deleting.
77  auto it_last = m_orphan_list.back();
78  m_orphan_list[old_pos] = it_last;
79  it_last->second.list_pos = old_pos;
80  }
81  m_orphan_list.pop_back();
82  m_wtxid_to_orphan_it.erase(it->second.tx->GetWitnessHash());
83 
84  m_orphans.erase(it);
85  return 1;
86 }
87 
89 {
91 
92  int nErased = 0;
93  std::map<uint256, OrphanTx>::iterator iter = m_orphans.begin();
94  while (iter != m_orphans.end())
95  {
96  std::map<uint256, OrphanTx>::iterator maybeErase = iter++; // increment to avoid iterator becoming invalid
97  if (maybeErase->second.fromPeer == peer)
98  {
99  nErased += EraseTx(maybeErase->second.tx->GetHash());
100  }
101  }
102  if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx from peer=%d\n", nErased, peer);
103 }
104 
105 unsigned int TxOrphanage::LimitOrphans(unsigned int max_orphans)
106 {
108 
109  unsigned int nEvicted = 0;
110  static int64_t nNextSweep;
111  int64_t nNow = GetTime();
112  if (nNextSweep <= nNow) {
113  // Sweep out expired orphan pool entries:
114  int nErased = 0;
115  int64_t nMinExpTime = nNow + ORPHAN_TX_EXPIRE_TIME - ORPHAN_TX_EXPIRE_INTERVAL;
116  std::map<uint256, OrphanTx>::iterator iter = m_orphans.begin();
117  while (iter != m_orphans.end())
118  {
119  std::map<uint256, OrphanTx>::iterator maybeErase = iter++;
120  if (maybeErase->second.nTimeExpire <= nNow) {
121  nErased += EraseTx(maybeErase->second.tx->GetHash());
122  } else {
123  nMinExpTime = std::min(maybeErase->second.nTimeExpire, nMinExpTime);
124  }
125  }
126  // Sweep again 5 minutes after the next entry that expires in order to batch the linear scan.
127  nNextSweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL;
128  if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx due to expiration\n", nErased);
129  }
130  FastRandomContext rng;
131  while (m_orphans.size() > max_orphans)
132  {
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;
139 }
140 
141 void TxOrphanage::AddChildrenToWorkSet(const CTransaction& tx, std::set<uint256>& orphan_work_set) const
142 {
144  for (unsigned int i = 0; i < tx.vout.size(); i++) {
145  const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(tx.GetHash(), i));
146  if (it_by_prev != m_outpoint_to_orphan_it.end()) {
147  for (const auto& elem : it_by_prev->second) {
148  orphan_work_set.insert(elem->first);
149  }
150  }
151  }
152 }
153 
154 bool TxOrphanage::HaveTx(const GenTxid& gtxid) const
155 {
157  if (gtxid.IsWtxid()) {
158  return m_wtxid_to_orphan_it.count(gtxid.GetHash());
159  } else {
160  return m_orphans.count(gtxid.GetHash());
161  }
162 }
163 
164 std::pair<CTransactionRef, NodeId> TxOrphanage::GetTx(const uint256& txid) const
165 {
167 
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)
174 {
176 
177  std::vector<uint256> vOrphanErase;
178 
179  for (const CTransactionRef& ptx : block.vtx) {
180  const CTransaction& tx = *ptx;
181 
182  // Which orphan pool entries must we evict?
183  for (const auto& txin : tx.vin) {
184  auto itByPrev = m_outpoint_to_orphan_it.find(txin.prevout);
185  if (itByPrev == m_outpoint_to_orphan_it.end()) continue;
186  for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) {
187  const CTransaction& orphanTx = *(*mi)->second.tx;
188  const uint256& orphanHash = orphanTx.GetHash();
189  vOrphanErase.push_back(orphanHash);
190  }
191  }
192  }
193 
194  // Erase orphan transactions included or precluded by this block
195  if (vOrphanErase.size()) {
196  int nErased = 0;
197  for (const uint256& orphanHash : vOrphanErase) {
198  nErased += EraseTx(orphanHash);
199  }
200  LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx included or conflicted by block\n", nErased);
201  }
202 }
CTxIn
An input of a transaction.
Definition: transaction.h:65
NodeId
int64_t NodeId
Definition: net.h:87
policy.h
CTransaction::vin
const std::vector< CTxIn > vin
Definition: transaction.h:270
TxOrphanage::OrphanTx
Definition: txorphanage.h:58
assert
assert(!tx.IsCoinBase())
TxOrphanage::EraseTx
int EraseTx(const uint256 &txid) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
Erase an orphan by txid.
Definition: txorphanage.cpp:56
GenTxid
A generic txid reference (txid or wtxid).
Definition: transaction.h:390
TxOrphanage::GetTx
bool HaveTx(const GenTxid &gtxid) const LOCKS_EXCLUDED(std::pair< CTransactionRef, NodeId > GetTx(const uint256 &txid) const EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
Check if we already have an orphan transaction (by txid or wtxid)
Definition: txorphanage.h:32
validation.h
GetTime
int64_t GetTime()
DEPRECATED Use either GetTimeSeconds (not mockable) or GetTime<T> (mockable)
Definition: time.cpp:26
ORPHAN_TX_EXPIRE_TIME
static constexpr int64_t ORPHAN_TX_EXPIRE_TIME
Expiration time for orphan transactions in seconds.
Definition: txorphanage.cpp:14
AnnotatedMixin< std::recursive_mutex >
CTransactionRef
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:386
TxOrphanage::LimitOrphans
void EraseForBlock(const CBlock &block) LOCKS_EXCLUDED(unsigned int LimitOrphans(unsigned int max_orphans) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
Erase all orphans included in or invalidated by a new block.
Definition: txorphanage.h:44
CTransaction
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:259
AssertLockHeld
AssertLockHeld(pool.cs)
GenTxid::IsWtxid
bool IsWtxid() const
Definition: transaction.h:396
TxOrphanage::AddChildrenToWorkSet
void AddChildrenToWorkSet(const CTransaction &tx, std::set< uint256 > &orphan_work_set) const EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
Add any orphans that list a particular tx as a parent into a peer's work set (ie orphans that may hav...
Definition: txorphanage.cpp:141
CTransaction::vout
const std::vector< CTxOut > vout
Definition: transaction.h:271
base_blob::ToString
std::string ToString() const
Definition: uint256.cpp:64
uint256
256-bit opaque blob.
Definition: uint256.h:124
LogPrint
#define LogPrint(category,...)
Definition: logging.h:191
CBlock
Definition: block.h:62
MAX_STANDARD_TX_WEIGHT
static const unsigned int MAX_STANDARD_TX_WEIGHT
The maximum weight for transactions we're willing to relay/mine.
Definition: policy.h:24
GetTransactionWeight
static int64_t GetTransactionWeight(const CTransaction &tx)
Definition: validation.h:146
CBlock::vtx
std::vector< CTransactionRef > vtx
Definition: block.h:66
GenTxid::GetHash
const uint256 & GetHash() const
Definition: transaction.h:397
BCLog::MEMPOOL
@ MEMPOOL
Definition: logging.h:40
LOCK
#define LOCK(cs)
Definition: sync.h:226
CTxIn::prevout
COutPoint prevout
Definition: transaction.h:68
logging.h
FastRandomContext::randrange
uint64_t randrange(uint64_t range) noexcept
Generate a random integer in the range [0..range).
Definition: random.h:190
TxOrphanage::AddTx
bool AddTx(const CTransactionRef &tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
Add a new orphan transaction.
Definition: txorphanage.cpp:20
CTransaction::GetHash
const uint256 & GetHash() const
Definition: transaction.h:302
COutPoint
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:26
TxOrphanage::EraseForPeer
void EraseForPeer(NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
Erase all orphans announced by a peer (eg, after that peer disconnects)
Definition: txorphanage.cpp:88
txorphanage.h
ORPHAN_TX_EXPIRE_INTERVAL
static constexpr int64_t ORPHAN_TX_EXPIRE_INTERVAL
Minimum time between orphan transactions expire time checks in seconds.
Definition: txorphanage.cpp:16
g_cs_orphans
RecursiveMutex g_cs_orphans
Guards orphan transactions and extra txs for compact blocks.
Definition: txorphanage.cpp:18
FastRandomContext
Fast randomness source.
Definition: random.h:119