Bitcoin ABC  0.26.3
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 
20 bool TxOrphanage::AddTx(const CTransactionRef &tx, NodeId peer) {
22 
23  const TxId &txid = tx->GetId();
24  if (m_orphans.count(txid)) {
25  return false;
26  }
27 
28  // Ignore big transactions, to avoid a send-big-orphans memory exhaustion
29  // attack. If a peer has a legitimate large transaction with a missing
30  // parent then we assume it will rebroadcast it later, after the parent
31  // transaction(s) have been mined or received.
32  // 100 orphans, each of which is at most 100,000 bytes big is at most 10
33  // megabytes of orphans and somewhat more byprev index (in the worst case):
34  unsigned int sz = tx->GetTotalSize();
35  if (sz > MAX_STANDARD_TX_SIZE) {
37  "ignoring large orphan tx (size: %u, hash: %s)\n", sz,
38  txid.ToString());
39  return false;
40  }
41 
42  auto ret = m_orphans.emplace(
43  txid, OrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME,
44  m_orphan_list.size()});
45  assert(ret.second);
46  m_orphan_list.push_back(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",
52  txid.ToString(), m_orphans.size(), m_outpoint_to_orphan_it.size());
53  return true;
54 }
55 
56 int TxOrphanage::EraseTx(const TxId &txid) {
58  std::map<TxId, OrphanTx>::iterator it = m_orphans.find(txid);
59  if (it == m_orphans.end()) {
60  return 0;
61  }
62  for (const CTxIn &txin : it->second.tx->vin) {
63  auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout);
64  if (itPrev == m_outpoint_to_orphan_it.end()) {
65  continue;
66  }
67  itPrev->second.erase(it);
68  if (itPrev->second.empty()) {
69  m_outpoint_to_orphan_it.erase(itPrev);
70  }
71  }
72 
73  size_t old_pos = it->second.list_pos;
74  assert(m_orphan_list[old_pos] == it);
75  if (old_pos + 1 != m_orphan_list.size()) {
76  // Unless we're deleting the last entry in m_orphan_list, move the last
77  // entry to the position we're deleting.
78  auto it_last = m_orphan_list.back();
79  m_orphan_list[old_pos] = it_last;
80  it_last->second.list_pos = old_pos;
81  }
82  m_orphan_list.pop_back();
83 
84  m_orphans.erase(it);
85  return 1;
86 }
87 
90 
91  int nErased = 0;
92  std::map<TxId, OrphanTx>::iterator iter = m_orphans.begin();
93  while (iter != m_orphans.end()) {
94  std::map<TxId, OrphanTx>::iterator maybeErase =
95  iter++; // increment to avoid iterator becoming invalid
96  if (maybeErase->second.fromPeer == peer) {
97  nErased += EraseTx(maybeErase->second.tx->GetId());
98  }
99  }
100  if (nErased > 0) {
101  LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx from peer=%d\n", nErased,
102  peer);
103  }
104 }
105 
106 unsigned int TxOrphanage::LimitOrphans(unsigned int max_orphans) {
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 =
117  std::map<TxId, OrphanTx>::iterator iter = m_orphans.begin();
118  while (iter != m_orphans.end()) {
119  std::map<TxId, OrphanTx>::iterator maybeErase = iter++;
120  if (maybeErase->second.nTimeExpire <= nNow) {
121  nErased += EraseTx(maybeErase->second.tx->GetId());
122  } else {
123  nMinExpTime =
124  std::min(maybeErase->second.nTimeExpire, nMinExpTime);
125  }
126  }
127  // Sweep again 5 minutes after the next entry that expires in order to
128  // batch the linear scan.
129  nNextSweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL;
130  if (nErased > 0) {
131  LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx due to expiration\n",
132  nErased);
133  }
134  }
135  FastRandomContext rng;
136  while (m_orphans.size() > max_orphans) {
137  // Evict a random orphan:
138  size_t randompos = rng.randrange(m_orphan_list.size());
139  EraseTx(m_orphan_list[randompos]->first);
140  ++nEvicted;
141  }
142  return nEvicted;
143 }
144 
146  std::set<TxId> &orphan_work_set) const {
148  for (size_t i = 0; i < tx.vout.size(); i++) {
149  const auto it_by_prev =
150  m_outpoint_to_orphan_it.find(COutPoint(tx.GetId(), i));
151  if (it_by_prev != m_outpoint_to_orphan_it.end()) {
152  for (const auto &elem : it_by_prev->second) {
153  orphan_work_set.insert(elem->first);
154  }
155  }
156  }
157 }
158 
159 bool TxOrphanage::HaveTx(const TxId &txid) const {
161  return m_orphans.count(txid);
162 }
163 
164 std::pair<CTransactionRef, NodeId> TxOrphanage::GetTx(const TxId &txid) const {
166 
167  const auto it = m_orphans.find(txid);
168  if (it == m_orphans.end()) {
169  return {nullptr, -1};
170  }
171  return {it->second.tx, it->second.fromPeer};
172 }
173 
174 void TxOrphanage::EraseForBlock(const CBlock &block) {
176 
177  std::vector<TxId> 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()) {
186  continue;
187  }
188 
189  for (auto mi = itByPrev->second.begin();
190  mi != itByPrev->second.end(); ++mi) {
191  const CTransaction &orphanTx = *(*mi)->second.tx;
192  const TxId &orphanId = orphanTx.GetId();
193  vOrphanErase.push_back(orphanId);
194  }
195  }
196  }
197 
198  // Erase orphan transactions included or precluded by this block
199  if (vOrphanErase.size()) {
200  int nErased = 0;
201  for (const auto &orphanId : vOrphanErase) {
202  nErased += EraseTx(orphanId);
203  }
205  "Erased %d orphan tx included or conflicted by block\n",
206  nErased);
207  }
208 }
Definition: block.h:55
std::vector< CTransactionRef > vtx
Definition: block.h:58
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:22
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:194
const std::vector< CTxOut > vout
Definition: transaction.h:211
const std::vector< CTxIn > vin
Definition: transaction.h:210
const TxId GetId() const
Definition: transaction.h:244
An input of a transaction.
Definition: transaction.h:61
COutPoint prevout
Definition: transaction.h:63
Fast randomness source.
Definition: random.h:129
uint64_t randrange(uint64_t range) noexcept
Generate a random integer in the range [0..range).
Definition: random.h:204
bool HaveTx(const TxId &txid) const LOCKS_EXCLUDED(g_cs_orphans)
Check if we already have an orphan transaction.
std::pair< CTransactionRef, NodeId > GetTx(const TxId &txid) const EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
Get an orphan transaction and its originating peer (Transaction ref will be nullptr if not found)
void EraseForBlock(const CBlock &block) LOCKS_EXCLUDED(g_cs_orphans)
Erase all orphans included in or invalidated by a new block.
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
bool AddTx(const CTransactionRef &tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
Add a new orphan transaction.
Definition: txorphanage.cpp:20
unsigned int LimitOrphans(unsigned int max_orphans) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
Limit the orphanage to the given maximum.
void AddChildrenToWorkSet(const CTransaction &tx, std::set< TxId > &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...
int EraseTx(const TxId &txid) EXCLUSIVE_LOCKS_REQUIRED(g_cs_orphans)
Erase an orphan by txid.
Definition: txorphanage.cpp:56
std::string ToString() const
Definition: uint256.h:78
#define LogPrint(category,...)
Definition: logging.h:208
@ MEMPOOL
Definition: logging.h:41
int64_t NodeId
Definition: nodeid.h:10
static const unsigned int MAX_STANDARD_TX_SIZE
The maximum size for transactions we're willing to relay/mine.
Definition: policy.h:33
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:319
A TxId is the identifier of a transaction.
Definition: txid.h:14
#define LOCK(cs)
Definition: sync.h:243
T GetTime()
Return system time (or mocked time, if set)
Definition: time.cpp:71
RecursiveMutex g_cs_orphans
Guards orphan transactions and extra txs for compact blocks.
Definition: txorphanage.cpp:18
static constexpr int64_t ORPHAN_TX_EXPIRE_INTERVAL
Minimum time between orphan transactions expire time checks in seconds.
Definition: txorphanage.cpp:16
static constexpr int64_t ORPHAN_TX_EXPIRE_TIME
Expiration time for orphan transactions in seconds.
Definition: txorphanage.cpp:14
AssertLockHeld(pool.cs)
assert(!tx.IsCoinBase())