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 
18 bool TxOrphanage::AddTx(const CTransactionRef &tx, NodeId peer) {
19  LOCK(m_mutex);
20 
21  const TxId &txid = tx->GetId();
22  if (m_orphans.count(txid)) {
23  return false;
24  }
25 
26  // Ignore big transactions, to avoid a send-big-orphans memory exhaustion
27  // attack. If a peer has a legitimate large transaction with a missing
28  // parent then we assume it will rebroadcast it later, after the parent
29  // transaction(s) have been mined or received.
30  // 100 orphans, each of which is at most 100,000 bytes big is at most 10
31  // megabytes of orphans and somewhat more byprev index (in the worst case):
32  unsigned int sz = tx->GetTotalSize();
33  if (sz > MAX_STANDARD_TX_SIZE) {
35  "ignoring large orphan tx (size: %u, hash: %s)\n", sz,
36  txid.ToString());
37  return false;
38  }
39 
40  auto ret = m_orphans.emplace(
41  txid, OrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME,
42  m_orphan_list.size()});
43  assert(ret.second);
44  m_orphan_list.push_back(ret.first);
45  for (const CTxIn &txin : tx->vin) {
46  m_outpoint_to_orphan_it[txin.prevout].insert(ret.first);
47  }
48 
49  LogPrint(BCLog::TXPACKAGES, "stored orphan tx %s (mapsz %u outsz %u)\n",
50  txid.ToString(), m_orphans.size(), m_outpoint_to_orphan_it.size());
51  return true;
52 }
53 
54 int TxOrphanage::EraseTx(const TxId &txid) {
55  LOCK(m_mutex);
56  return EraseTxNoLock(txid);
57 }
58 
59 int TxOrphanage::EraseTxNoLock(const TxId &txid) {
61  std::map<TxId, OrphanTx>::iterator it = m_orphans.find(txid);
62  if (it == m_orphans.end()) {
63  return 0;
64  }
65  for (const CTxIn &txin : it->second.tx->vin) {
66  auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout);
67  if (itPrev == m_outpoint_to_orphan_it.end()) {
68  continue;
69  }
70  itPrev->second.erase(it);
71  if (itPrev->second.empty()) {
72  m_outpoint_to_orphan_it.erase(itPrev);
73  }
74  }
75 
76  size_t old_pos = it->second.list_pos;
77  assert(m_orphan_list[old_pos] == it);
78  if (old_pos + 1 != m_orphan_list.size()) {
79  // Unless we're deleting the last entry in m_orphan_list, move the last
80  // entry to the position we're deleting.
81  auto it_last = m_orphan_list.back();
82  m_orphan_list[old_pos] = it_last;
83  it_last->second.list_pos = old_pos;
84  }
85  LogPrint(BCLog::TXPACKAGES, " removed orphan tx %s \n", txid.ToString());
86  m_orphan_list.pop_back();
87 
88  m_orphans.erase(it);
89  return 1;
90 }
91 
93  LOCK(m_mutex);
94 
95  m_peer_work_set.erase(peer);
96 
97  int nErased = 0;
98  std::map<TxId, OrphanTx>::iterator iter = m_orphans.begin();
99  while (iter != m_orphans.end()) {
100  std::map<TxId, OrphanTx>::iterator maybeErase =
101  iter++; // increment to avoid iterator becoming invalid
102  if (maybeErase->second.fromPeer == peer) {
103  nErased += EraseTxNoLock(maybeErase->second.tx->GetId());
104  }
105  }
106  if (nErased > 0) {
107  LogPrint(BCLog::TXPACKAGES, "Erased %d orphan tx from peer=%d\n",
108  nErased, peer);
109  }
110 }
111 
112 unsigned int TxOrphanage::LimitOrphans(unsigned int max_orphans) {
113  LOCK(m_mutex);
114 
115  unsigned int nEvicted = 0;
116  static int64_t nNextSweep;
117  int64_t nNow = GetTime();
118  if (nNextSweep <= nNow) {
119  // Sweep out expired orphan pool entries:
120  int nErased = 0;
121  int64_t nMinExpTime =
123  std::map<TxId, OrphanTx>::iterator iter = m_orphans.begin();
124  while (iter != m_orphans.end()) {
125  std::map<TxId, OrphanTx>::iterator maybeErase = iter++;
126  if (maybeErase->second.nTimeExpire <= nNow) {
127  nErased += EraseTxNoLock(maybeErase->second.tx->GetId());
128  } else {
129  nMinExpTime =
130  std::min(maybeErase->second.nTimeExpire, nMinExpTime);
131  }
132  }
133  // Sweep again 5 minutes after the next entry that expires in order to
134  // batch the linear scan.
135  nNextSweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL;
136  if (nErased > 0) {
138  "Erased %d orphan tx due to expiration\n", nErased);
139  }
140  }
141  FastRandomContext rng;
142  while (m_orphans.size() > max_orphans) {
143  // Evict a random orphan:
144  size_t randompos = rng.randrange(m_orphan_list.size());
145  EraseTxNoLock(m_orphan_list[randompos]->first);
146  ++nEvicted;
147  }
148  return nEvicted;
149 }
150 
152  LOCK(m_mutex);
153 
154  for (size_t i = 0; i < tx.vout.size(); i++) {
155  const auto it_by_prev =
156  m_outpoint_to_orphan_it.find(COutPoint(tx.GetId(), i));
157  if (it_by_prev != m_outpoint_to_orphan_it.end()) {
158  for (const auto &elem : it_by_prev->second) {
159  // Get this peer's work set, emplacing an empty set if it didn't
160  // exist
161  std::set<TxId> &orphan_work_set =
162  m_peer_work_set.try_emplace(elem->second.fromPeer)
163  .first->second;
164  // Add this tx to the work set
165  orphan_work_set.insert(elem->first);
166  LogPrint(BCLog::TXPACKAGES, "added %s to peer %d workset\n",
167  tx.GetId().ToString(), elem->second.fromPeer);
168  }
169  }
170  }
171 }
172 
173 bool TxOrphanage::HaveTx(const TxId &txid) const {
174  LOCK(m_mutex);
175  return m_orphans.count(txid);
176 }
177 
179  LOCK(m_mutex);
180 
181  auto work_set_it = m_peer_work_set.find(peer);
182  if (work_set_it != m_peer_work_set.end()) {
183  auto &work_set = work_set_it->second;
184  while (!work_set.empty()) {
185  TxId txid = *work_set.begin();
186  work_set.erase(work_set.begin());
187 
188  const auto orphan_it = m_orphans.find(txid);
189  if (orphan_it != m_orphans.end()) {
190  return orphan_it->second.tx;
191  }
192  }
193  }
194  return nullptr;
195 }
196 
198  LOCK(m_mutex);
199 
200  auto work_set_it = m_peer_work_set.find(peer);
201  if (work_set_it != m_peer_work_set.end()) {
202  auto &work_set = work_set_it->second;
203  return !work_set.empty();
204  }
205  return false;
206 }
207 
208 void TxOrphanage::EraseForBlock(const CBlock &block) {
209  LOCK(m_mutex);
210 
211  std::vector<TxId> vOrphanErase;
212 
213  for (const CTransactionRef &ptx : block.vtx) {
214  const CTransaction &tx = *ptx;
215 
216  // Which orphan pool entries must we evict?
217  for (const auto &txin : tx.vin) {
218  auto itByPrev = m_outpoint_to_orphan_it.find(txin.prevout);
219  if (itByPrev == m_outpoint_to_orphan_it.end()) {
220  continue;
221  }
222 
223  for (auto mi = itByPrev->second.begin();
224  mi != itByPrev->second.end(); ++mi) {
225  const CTransaction &orphanTx = *(*mi)->second.tx;
226  const TxId &orphanId = orphanTx.GetId();
227  vOrphanErase.push_back(orphanId);
228  }
229  }
230  }
231 
232  // Erase orphan transactions included or precluded by this block
233  if (vOrphanErase.size()) {
234  int nErased = 0;
235  for (const auto &orphanId : vOrphanErase) {
236  nErased += EraseTxNoLock(orphanId);
237  }
239  "Erased %d orphan tx included or conflicted by block\n",
240  nErased);
241  }
242 }
Definition: block.h:60
std::vector< CTransactionRef > vtx
Definition: block.h:63
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:20
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:192
const std::vector< CTxOut > vout
Definition: transaction.h:207
const std::vector< CTxIn > vin
Definition: transaction.h:206
const TxId GetId() const
Definition: transaction.h:240
An input of a transaction.
Definition: transaction.h:59
COutPoint prevout
Definition: transaction.h:61
Fast randomness source.
Definition: random.h:156
uint64_t randrange(uint64_t range) noexcept
Generate a random integer in the range [0..range).
Definition: random.h:231
bool HaveTxToReconsider(NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
Does this peer have any work to do?
void AddChildrenToWorkSet(const CTransaction &tx) EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
Add any orphans that list a particular tx as a parent into the from peer's work set.
unsigned int LimitOrphans(unsigned int max_orphans) EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
Limit the orphanage to the given maximum.
void EraseForBlock(const CBlock &block) EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
Erase all orphans included in or invalidated by a new block.
Mutex m_mutex
Guards orphan transactions.
Definition: txorphanage.h:74
bool AddTx(const CTransactionRef &tx, NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
Add a new orphan transaction.
Definition: txorphanage.cpp:18
int EraseTxNoLock(const TxId &txid) EXCLUSIVE_LOCKS_REQUIRED(m_mutex)
Erase an orphan by txid.
Definition: txorphanage.cpp:59
int EraseTx(const TxId &txid) EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
Erase an orphan by txid.
Definition: txorphanage.cpp:54
bool HaveTx(const TxId &txid) const EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
Check if we already have an orphan transaction.
CTransactionRef GetTxToReconsider(NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
Extract a transaction from a peer's work set.
void EraseForPeer(NodeId peer) EXCLUSIVE_LOCKS_REQUIRED(!m_mutex)
Erase all orphans announced by a peer (eg, after that peer disconnects)
Definition: txorphanage.cpp:92
uint8_t * begin()
Definition: uint256.h:85
std::string ToString() const
Definition: uint256.h:80
#define LogPrint(category,...)
Definition: logging.h:211
@ TXPACKAGES
Definition: logging.h:70
int64_t NodeId
Definition: nodeid.h:10
static constexpr unsigned int MAX_STANDARD_TX_SIZE
The maximum size for transactions we're willing to relay/mine.
Definition: policy.h:34
std::shared_ptr< const CTransaction > CTransactionRef
Definition: transaction.h:315
A TxId is the identifier of a transaction.
Definition: txid.h:14
#define LOCK(cs)
Definition: sync.h:306
int64_t GetTime()
Definition: time.cpp:109
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())