Branch data Line data Source code
1 : : // Copyright (c) 2021-2022 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 : : #include <primitives/transaction.h>
11 : : #include <util/time.h>
12 : :
13 : : #include <cassert>
14 : :
15 : 571 : bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer)
16 : : {
17 : 571 : const Txid& hash = tx->GetHash();
18 : 571 : const Wtxid& wtxid = tx->GetWitnessHash();
19 [ + + ]: 571 : if (auto it{m_orphans.find(wtxid)}; it != m_orphans.end()) {
20 : 8 : AddAnnouncer(wtxid, peer);
21 : : // No new orphan entry was created. An announcer may have been added.
22 : 8 : return false;
23 : : }
24 : :
25 : : // Ignore big transactions, to avoid a
26 : : // send-big-orphans memory exhaustion attack. If a peer has a legitimate
27 : : // large transaction with a missing parent then we assume
28 : : // it will rebroadcast it later, after the parent transaction(s)
29 : : // have been mined or received.
30 : : // 100 orphans, each of which is at most 100,000 bytes big is
31 : : // at most 10 megabytes of orphans and somewhat more byprev index (in the worst case):
32 : 563 : unsigned int sz = GetTransactionWeight(*tx);
33 [ + + ]: 563 : if (sz > MAX_STANDARD_TX_WEIGHT)
34 : : {
35 [ + - + - : 22 : LogDebug(BCLog::TXPACKAGES, "ignoring large orphan tx (size: %u, txid: %s, wtxid: %s)\n", sz, hash.ToString(), wtxid.ToString());
+ - ]
36 : 11 : return false;
37 : : }
38 : :
39 [ + - + - : 1656 : auto ret = m_orphans.emplace(wtxid, OrphanTx{{tx, {peer}, Now<NodeSeconds>() + ORPHAN_TX_EXPIRE_TIME}, m_orphan_list.size()});
+ - - + -
- ]
40 [ - + ]: 552 : assert(ret.second);
41 : 552 : m_orphan_list.push_back(ret.first);
42 [ + + ]: 1179 : for (const CTxIn& txin : tx->vin) {
43 : 627 : m_outpoint_to_orphan_it[txin.prevout].insert(ret.first);
44 : : }
45 : :
46 [ + - + - : 1104 : LogDebug(BCLog::TXPACKAGES, "stored orphan tx %s (wtxid=%s), weight: %u (mapsz %u outsz %u)\n", hash.ToString(), wtxid.ToString(), sz,
+ - ]
47 : : m_orphans.size(), m_outpoint_to_orphan_it.size());
48 : : return true;
49 : : }
50 : :
51 : 18 : bool TxOrphanage::AddAnnouncer(const Wtxid& wtxid, NodeId peer)
52 : : {
53 : 18 : const auto it = m_orphans.find(wtxid);
54 [ + - ]: 18 : if (it != m_orphans.end()) {
55 : 18 : Assume(!it->second.announcers.empty());
56 : 18 : const auto ret = it->second.announcers.insert(peer);
57 [ + + ]: 18 : if (ret.second) {
58 [ + - + - ]: 30 : LogDebug(BCLog::TXPACKAGES, "added peer=%d as announcer of orphan tx %s\n", peer, wtxid.ToString());
59 : 15 : return true;
60 : : }
61 : : }
62 : : return false;
63 : : }
64 : :
65 : 12400 : int TxOrphanage::EraseTx(const Wtxid& wtxid)
66 : : {
67 : 12400 : std::map<Wtxid, OrphanTx>::iterator it = m_orphans.find(wtxid);
68 [ + + ]: 12400 : if (it == m_orphans.end())
69 : : return 0;
70 [ + + ]: 1022 : for (const CTxIn& txin : it->second.tx->vin)
71 : : {
72 : 523 : auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout);
73 [ - + ]: 523 : if (itPrev == m_outpoint_to_orphan_it.end())
74 : 0 : continue;
75 : 523 : itPrev->second.erase(it);
76 [ + + ]: 523 : if (itPrev->second.empty())
77 : 502 : m_outpoint_to_orphan_it.erase(itPrev);
78 : : }
79 : :
80 [ - + ]: 499 : size_t old_pos = it->second.list_pos;
81 [ - + ]: 499 : assert(m_orphan_list[old_pos] == it);
82 [ + + ]: 499 : if (old_pos + 1 != m_orphan_list.size()) {
83 : : // Unless we're deleting the last entry in m_orphan_list, move the last
84 : : // entry to the position we're deleting.
85 : 371 : auto it_last = m_orphan_list.back();
86 : 371 : m_orphan_list[old_pos] = it_last;
87 : 371 : it_last->second.list_pos = old_pos;
88 : : }
89 : 499 : const auto& txid = it->second.tx->GetHash();
90 : : // Time spent in orphanage = difference between current and entry time.
91 : : // Entry time is equal to ORPHAN_TX_EXPIRE_TIME earlier than entry's expiry.
92 [ + - + - : 998 : LogDebug(BCLog::TXPACKAGES, " removed orphan tx %s (wtxid=%s) after %ds\n", txid.ToString(), wtxid.ToString(),
+ - ]
93 : : Ticks<std::chrono::seconds>(NodeClock::now() + ORPHAN_TX_EXPIRE_TIME - it->second.nTimeExpire));
94 : 499 : m_orphan_list.pop_back();
95 : :
96 : 499 : m_orphans.erase(it);
97 : 499 : return 1;
98 : : }
99 : :
100 : 1568 : void TxOrphanage::EraseForPeer(NodeId peer)
101 : : {
102 : 1568 : m_peer_work_set.erase(peer);
103 : :
104 : 1568 : int nErased = 0;
105 : 1568 : std::map<Wtxid, OrphanTx>::iterator iter = m_orphans.begin();
106 [ + + ]: 3761 : while (iter != m_orphans.end())
107 : : {
108 : : // increment to avoid iterator becoming invalid after erasure
109 : 625 : auto& [wtxid, orphan] = *iter++;
110 : 625 : auto orphan_it = orphan.announcers.find(peer);
111 [ + + ]: 625 : if (orphan_it != orphan.announcers.end()) {
112 : 232 : orphan.announcers.erase(peer);
113 : :
114 : : // No remaining announcers: clean up entry
115 [ + + ]: 232 : if (orphan.announcers.empty()) {
116 : 223 : nErased += EraseTx(orphan.tx->GetWitnessHash());
117 : : }
118 : : }
119 : : }
120 [ + + + - ]: 1568 : if (nErased > 0) LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) from peer=%d\n", nErased, peer);
121 : 1568 : }
122 : :
123 : 439 : void TxOrphanage::LimitOrphans(unsigned int max_orphans, FastRandomContext& rng)
124 : : {
125 : 439 : unsigned int nEvicted = 0;
126 : 439 : auto nNow{Now<NodeSeconds>()};
127 [ + + ]: 439 : if (m_next_sweep <= nNow) {
128 : : // Sweep out expired orphan pool entries:
129 : 66 : int nErased = 0;
130 : 66 : auto nMinExpTime{nNow + ORPHAN_TX_EXPIRE_TIME - ORPHAN_TX_EXPIRE_INTERVAL};
131 : 66 : std::map<Wtxid, OrphanTx>::iterator iter = m_orphans.begin();
132 [ + + ]: 225 : while (iter != m_orphans.end())
133 : : {
134 : 159 : std::map<Wtxid, OrphanTx>::iterator maybeErase = iter++;
135 [ + + ]: 159 : if (maybeErase->second.nTimeExpire <= nNow) {
136 : 1 : nErased += EraseTx(maybeErase->first);
137 : : } else {
138 : 158 : nMinExpTime = std::min(maybeErase->second.nTimeExpire, nMinExpTime);
139 : : }
140 : : }
141 : : // Sweep again 5 minutes after the next entry that expires in order to batch the linear scan.
142 : 66 : m_next_sweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL;
143 [ + + + - ]: 66 : if (nErased > 0) LogDebug(BCLog::TXPACKAGES, "Erased %d orphan tx due to expiration\n", nErased);
144 : : }
145 [ + + ]: 536 : while (m_orphans.size() > max_orphans)
146 : : {
147 : : // Evict a random orphan:
148 : 97 : size_t randompos = rng.randrange(m_orphan_list.size());
149 : 97 : EraseTx(m_orphan_list[randompos]->first);
150 : 97 : ++nEvicted;
151 : : }
152 [ + + + - ]: 439 : if (nEvicted > 0) LogDebug(BCLog::TXPACKAGES, "orphanage overflow, removed %u tx\n", nEvicted);
153 : 439 : }
154 : :
155 : 11827 : void TxOrphanage::AddChildrenToWorkSet(const CTransaction& tx)
156 : : {
157 [ + + ]: 33721 : for (unsigned int i = 0; i < tx.vout.size(); i++) {
158 : 21894 : const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(tx.GetHash(), i));
159 [ + + ]: 21894 : if (it_by_prev != m_outpoint_to_orphan_it.end()) {
160 [ + + ]: 247 : for (const auto& elem : it_by_prev->second) {
161 : : // Belt and suspenders, each orphan should always have at least 1 announcer.
162 [ - + ]: 125 : if (!Assume(!elem->second.announcers.empty())) continue;
163 [ + + ]: 253 : for (const auto announcer: elem->second.announcers) {
164 : : // Get this source peer's work set, emplacing an empty set if it didn't exist
165 : : // (note: if this peer wasn't still connected, we would have removed the orphan tx already)
166 : 128 : std::set<Wtxid>& orphan_work_set = m_peer_work_set.try_emplace(announcer).first->second;
167 : : // Add this tx to the work set
168 : 128 : orphan_work_set.insert(elem->first);
169 [ + - + - : 256 : LogDebug(BCLog::TXPACKAGES, "added %s (wtxid=%s) to peer %d workset\n",
+ - ]
170 : : tx.GetHash().ToString(), tx.GetWitnessHash().ToString(), announcer);
171 : : }
172 : : }
173 : : }
174 : : }
175 : 11827 : }
176 : :
177 : 61591 : bool TxOrphanage::HaveTx(const Wtxid& wtxid) const
178 : : {
179 : 61591 : return m_orphans.count(wtxid);
180 : : }
181 : :
182 : 26465 : CTransactionRef TxOrphanage::GetTx(const Wtxid& wtxid) const
183 : : {
184 : 26465 : auto it = m_orphans.find(wtxid);
185 [ + + + - ]: 26465 : return it != m_orphans.end() ? it->second.tx : nullptr;
186 : : }
187 : :
188 : 453 : bool TxOrphanage::HaveTxFromPeer(const Wtxid& wtxid, NodeId peer) const
189 : : {
190 : 453 : auto it = m_orphans.find(wtxid);
191 [ + + + + ]: 453 : return (it != m_orphans.end() && it->second.announcers.contains(peer));
192 : : }
193 : :
194 : 403527 : CTransactionRef TxOrphanage::GetTxToReconsider(NodeId peer)
195 : : {
196 : 403527 : auto work_set_it = m_peer_work_set.find(peer);
197 [ + + ]: 403527 : if (work_set_it != m_peer_work_set.end()) {
198 : 833 : auto& work_set = work_set_it->second;
199 [ + + ]: 834 : while (!work_set.empty()) {
200 : 128 : Wtxid wtxid = *work_set.begin();
201 : 128 : work_set.erase(work_set.begin());
202 : :
203 : 128 : const auto orphan_it = m_orphans.find(wtxid);
204 [ + + ]: 128 : if (orphan_it != m_orphans.end()) {
205 [ + - ]: 127 : return orphan_it->second.tx;
206 : : }
207 : : }
208 : : }
209 : 403400 : return nullptr;
210 : : }
211 : :
212 : 158710 : bool TxOrphanage::HaveTxToReconsider(NodeId peer)
213 : : {
214 : 158710 : auto work_set_it = m_peer_work_set.find(peer);
215 [ + + ]: 158710 : if (work_set_it != m_peer_work_set.end()) {
216 : 568 : auto& work_set = work_set_it->second;
217 : 568 : return !work_set.empty();
218 : : }
219 : : return false;
220 : : }
221 : :
222 : 117874 : void TxOrphanage::EraseForBlock(const CBlock& block)
223 : : {
224 : 117874 : std::vector<Wtxid> vOrphanErase;
225 : :
226 [ + + ]: 278094 : for (const CTransactionRef& ptx : block.vtx) {
227 : 160220 : const CTransaction& tx = *ptx;
228 : :
229 : : // Which orphan pool entries must we evict?
230 [ + + ]: 344142 : for (const auto& txin : tx.vin) {
231 : 183922 : auto itByPrev = m_outpoint_to_orphan_it.find(txin.prevout);
232 [ + + ]: 183922 : if (itByPrev == m_outpoint_to_orphan_it.end()) continue;
233 [ + + ]: 56 : for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) {
234 [ + - ]: 28 : const CTransaction& orphanTx = *(*mi)->second.tx;
235 [ + - ]: 28 : vOrphanErase.push_back(orphanTx.GetWitnessHash());
236 : : }
237 : : }
238 : : }
239 : :
240 : : // Erase orphan transactions included or precluded by this block
241 [ + + ]: 117874 : if (vOrphanErase.size()) {
242 : 7 : int nErased = 0;
243 [ + + ]: 35 : for (const auto& orphanHash : vOrphanErase) {
244 [ + - ]: 28 : nErased += EraseTx(orphanHash);
245 : : }
246 [ + - + - : 7 : LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) included or conflicted by block\n", nErased);
+ - ]
247 : : }
248 : 117874 : }
249 : :
250 : 61 : std::vector<CTransactionRef> TxOrphanage::GetChildrenFromSamePeer(const CTransactionRef& parent, NodeId nodeid) const
251 : : {
252 : : // First construct a vector of iterators to ensure we do not return duplicates of the same tx
253 : : // and so we can sort by nTimeExpire.
254 : 61 : std::vector<OrphanMap::iterator> iters;
255 : :
256 : : // For each output, get all entries spending this prevout, filtering for ones from the specified peer.
257 [ + + ]: 144 : for (unsigned int i = 0; i < parent->vout.size(); i++) {
258 : 83 : const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(parent->GetHash(), i));
259 [ + + ]: 83 : if (it_by_prev != m_outpoint_to_orphan_it.end()) {
260 [ + + ]: 111 : for (const auto& elem : it_by_prev->second) {
261 [ + + ]: 60 : if (elem->second.announcers.contains(nodeid)) {
262 [ + - ]: 46 : iters.emplace_back(elem);
263 : : }
264 : : }
265 : : }
266 : : }
267 : :
268 : : // Sort by address so that duplicates can be deleted. At the same time, sort so that more recent
269 : : // orphans (which expire later) come first. Break ties based on address, as nTimeExpire is
270 : : // quantified in seconds and it is possible for orphans to have the same expiry.
271 [ + - ]: 89 : std::sort(iters.begin(), iters.end(), [](const auto& lhs, const auto& rhs) {
272 [ + - ]: 28 : if (lhs->second.nTimeExpire == rhs->second.nTimeExpire) {
273 : 28 : return &(*lhs) < &(*rhs);
274 : : } else {
275 : 0 : return lhs->second.nTimeExpire > rhs->second.nTimeExpire;
276 : : }
277 : : });
278 : : // Erase duplicates
279 : 61 : iters.erase(std::unique(iters.begin(), iters.end()), iters.end());
280 : :
281 : : // Convert to a vector of CTransactionRef
282 : 61 : std::vector<CTransactionRef> children_found;
283 [ + - ]: 61 : children_found.reserve(iters.size());
284 [ + + ]: 98 : for (const auto& child_iter : iters) {
285 [ + - ]: 37 : children_found.emplace_back(child_iter->second.tx);
286 : : }
287 : 61 : return children_found;
288 : 61 : }
289 : :
290 : 161 : std::vector<TxOrphanage::OrphanTxBase> TxOrphanage::GetOrphanTransactions() const
291 : : {
292 : 161 : std::vector<OrphanTxBase> ret;
293 [ + - ]: 161 : ret.reserve(m_orphans.size());
294 [ + + ]: 10514 : for (auto const& o : m_orphans) {
295 [ + - ]: 20706 : ret.push_back({o.second.tx, o.second.announcers, o.second.nTimeExpire});
296 : : }
297 : 161 : return ret;
298 [ + - + - ]: 10353 : }
|
