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 : 228909 : bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer)
16 : : {
17 : 228909 : const Txid& hash = tx->GetHash();
18 : 228909 : const Wtxid& wtxid = tx->GetWitnessHash();
19 [ + + ]: 228909 : if (auto it{m_orphans.find(wtxid)}; it != m_orphans.end()) {
20 : 209886 : AddAnnouncer(wtxid, peer);
21 : : // No new orphan entry was created. An announcer may have been added.
22 : 209886 : 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 : 19023 : unsigned int sz = GetTransactionWeight(*tx);
33 [ + + ]: 19023 : if (sz > MAX_STANDARD_TX_WEIGHT)
34 : : {
35 [ - + - - : 274 : LogDebug(BCLog::TXPACKAGES, "ignoring large orphan tx (size: %u, txid: %s, wtxid: %s)\n", sz, hash.ToString(), wtxid.ToString());
- - ]
36 : 274 : return false;
37 : : }
38 : :
39 [ + - + - : 56247 : auto ret = m_orphans.emplace(wtxid, OrphanTx{{tx, {peer}, Now<NodeSeconds>() + ORPHAN_TX_EXPIRE_TIME}, m_orphan_list.size()});
+ - - + -
- ]
40 [ - + ]: 18749 : assert(ret.second);
41 : 18749 : m_orphan_list.push_back(ret.first);
42 [ + + ]: 5811701 : for (const CTxIn& txin : tx->vin) {
43 : 5792952 : m_outpoint_to_orphan_it[txin.prevout].insert(ret.first);
44 : : }
45 : :
46 [ - + - - : 18749 : 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 : 210974 : bool TxOrphanage::AddAnnouncer(const Wtxid& wtxid, NodeId peer)
52 : : {
53 : 210974 : const auto it = m_orphans.find(wtxid);
54 [ + + ]: 210974 : if (it != m_orphans.end()) {
55 : 210164 : Assume(!it->second.announcers.empty());
56 : 210164 : const auto ret = it->second.announcers.insert(peer);
57 [ + + ]: 210164 : if (ret.second) {
58 [ - + - - ]: 2598 : LogDebug(BCLog::TXPACKAGES, "added peer=%d as announcer of orphan tx %s\n", peer, wtxid.ToString());
59 : 2598 : return true;
60 : : }
61 : : }
62 : : return false;
63 : : }
64 : :
65 : 47252 : int TxOrphanage::EraseTx(const Wtxid& wtxid)
66 : : {
67 : 47252 : std::map<Wtxid, OrphanTx>::iterator it = m_orphans.find(wtxid);
68 [ + + ]: 47252 : if (it == m_orphans.end())
69 : : return 0;
70 [ + + ]: 5707418 : for (const CTxIn& txin : it->second.tx->vin)
71 : : {
72 : 5689580 : auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout);
73 [ + + ]: 5689580 : if (itPrev == m_outpoint_to_orphan_it.end())
74 : 5568172 : continue;
75 : 121408 : itPrev->second.erase(it);
76 [ + + ]: 121408 : if (itPrev->second.empty())
77 : 92344 : m_outpoint_to_orphan_it.erase(itPrev);
78 : : }
79 : :
80 [ - + ]: 17838 : size_t old_pos = it->second.list_pos;
81 [ - + ]: 17838 : assert(m_orphan_list[old_pos] == it);
82 [ + + ]: 17838 : 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 : 2675 : auto it_last = m_orphan_list.back();
86 : 2675 : m_orphan_list[old_pos] = it_last;
87 : 2675 : it_last->second.list_pos = old_pos;
88 : : }
89 : 17838 : 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 [ - + - - : 17838 : 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 : 17838 : m_orphan_list.pop_back();
95 : :
96 : 17838 : m_orphans.erase(it);
97 : 17838 : return 1;
98 : : }
99 : :
100 : 73929 : void TxOrphanage::EraseForPeer(NodeId peer)
101 : : {
102 : 73929 : m_peer_work_set.erase(peer);
103 : :
104 : 73929 : int nErased = 0;
105 : 73929 : std::map<Wtxid, OrphanTx>::iterator iter = m_orphans.begin();
106 [ + + ]: 156512 : while (iter != m_orphans.end())
107 : : {
108 : : // increment to avoid iterator becoming invalid after erasure
109 : 8654 : auto& [wtxid, orphan] = *iter++;
110 : 8654 : auto orphan_it = orphan.announcers.find(peer);
111 [ + + ]: 8654 : if (orphan_it != orphan.announcers.end()) {
112 : 4461 : orphan.announcers.erase(peer);
113 : :
114 : : // No remaining announcers: clean up entry
115 [ + + ]: 4461 : if (orphan.announcers.empty()) {
116 : 4294 : nErased += EraseTx(orphan.tx->GetWitnessHash());
117 : : }
118 : : }
119 : : }
120 [ + + - + ]: 73929 : if (nErased > 0) LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) from peer=%d\n", nErased, peer);
121 : 73929 : }
122 : :
123 : 184754 : void TxOrphanage::LimitOrphans(unsigned int max_orphans, FastRandomContext& rng)
124 : : {
125 : 184754 : unsigned int nEvicted = 0;
126 : 184754 : auto nNow{Now<NodeSeconds>()};
127 [ + + ]: 184754 : if (m_next_sweep <= nNow) {
128 : : // Sweep out expired orphan pool entries:
129 : 418 : int nErased = 0;
130 : 418 : auto nMinExpTime{nNow + ORPHAN_TX_EXPIRE_TIME - ORPHAN_TX_EXPIRE_INTERVAL};
131 : 418 : std::map<Wtxid, OrphanTx>::iterator iter = m_orphans.begin();
132 [ + + ]: 1021 : while (iter != m_orphans.end())
133 : : {
134 : 603 : std::map<Wtxid, OrphanTx>::iterator maybeErase = iter++;
135 [ + + ]: 603 : if (maybeErase->second.nTimeExpire <= nNow) {
136 : 301 : nErased += EraseTx(maybeErase->first);
137 : : } else {
138 : 302 : 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 : 418 : m_next_sweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL;
143 [ + + - + ]: 418 : if (nErased > 0) LogDebug(BCLog::TXPACKAGES, "Erased %d orphan tx due to expiration\n", nErased);
144 : : }
145 [ + + ]: 184759 : while (m_orphans.size() > max_orphans)
146 : : {
147 : : // Evict a random orphan:
148 : 5 : size_t randompos = rng.randrange(m_orphan_list.size());
149 : 5 : EraseTx(m_orphan_list[randompos]->first);
150 : 5 : ++nEvicted;
151 : : }
152 [ + + - + ]: 184754 : if (nEvicted > 0) LogDebug(BCLog::TXPACKAGES, "orphanage overflow, removed %u tx\n", nEvicted);
153 : 184754 : }
154 : :
155 : 3759 : void TxOrphanage::AddChildrenToWorkSet(const CTransaction& tx)
156 : : {
157 [ + + ]: 372945 : for (unsigned int i = 0; i < tx.vout.size(); i++) {
158 : 369186 : const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(tx.GetHash(), i));
159 [ + + ]: 369186 : if (it_by_prev != m_outpoint_to_orphan_it.end()) {
160 [ + + ]: 9304 : for (const auto& elem : it_by_prev->second) {
161 : : // Belt and suspenders, each orphan should always have at least 1 announcer.
162 [ - + ]: 5000 : if (!Assume(!elem->second.announcers.empty())) continue;
163 [ + + ]: 12654 : 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 : 7654 : std::set<Wtxid>& orphan_work_set = m_peer_work_set.try_emplace(announcer).first->second;
167 : : // Add this tx to the work set
168 : 7654 : orphan_work_set.insert(elem->first);
169 [ - + - - : 7654 : 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 : 3759 : }
176 : :
177 : 635874 : bool TxOrphanage::HaveTx(const Wtxid& wtxid) const
178 : : {
179 : 635874 : return m_orphans.count(wtxid);
180 : : }
181 : :
182 : 5505 : CTransactionRef TxOrphanage::GetTx(const Wtxid& wtxid) const
183 : : {
184 : 5505 : auto it = m_orphans.find(wtxid);
185 [ + + + - ]: 5505 : return it != m_orphans.end() ? it->second.tx : nullptr;
186 : : }
187 : :
188 : 6779 : bool TxOrphanage::HaveTxFromPeer(const Wtxid& wtxid, NodeId peer) const
189 : : {
190 : 6779 : auto it = m_orphans.find(wtxid);
191 [ + + + + ]: 6779 : return (it != m_orphans.end() && it->second.announcers.contains(peer));
192 : : }
193 : :
194 : 1316641 : CTransactionRef TxOrphanage::GetTxToReconsider(NodeId peer)
195 : : {
196 : 1316641 : auto work_set_it = m_peer_work_set.find(peer);
197 [ + + ]: 1316641 : if (work_set_it != m_peer_work_set.end()) {
198 : 98 : auto& work_set = work_set_it->second;
199 [ + + ]: 99 : while (!work_set.empty()) {
200 : 96 : Wtxid wtxid = *work_set.begin();
201 : 96 : work_set.erase(work_set.begin());
202 : :
203 : 96 : const auto orphan_it = m_orphans.find(wtxid);
204 [ + + ]: 96 : if (orphan_it != m_orphans.end()) {
205 [ + - ]: 95 : return orphan_it->second.tx;
206 : : }
207 : : }
208 : : }
209 : 1316546 : return nullptr;
210 : : }
211 : :
212 : 98833 : bool TxOrphanage::HaveTxToReconsider(NodeId peer)
213 : : {
214 : 98833 : auto work_set_it = m_peer_work_set.find(peer);
215 [ + + ]: 98833 : if (work_set_it != m_peer_work_set.end()) {
216 : 3 : auto& work_set = work_set_it->second;
217 : 3 : return !work_set.empty();
218 : : }
219 : : return false;
220 : : }
221 : :
222 : 7439 : void TxOrphanage::EraseForBlock(const CBlock& block)
223 : : {
224 : 7439 : std::vector<Wtxid> vOrphanErase;
225 : :
226 [ + + ]: 14878 : for (const CTransactionRef& ptx : block.vtx) {
227 : 7439 : const CTransaction& tx = *ptx;
228 : :
229 : : // Which orphan pool entries must we evict?
230 [ + + ]: 83820 : for (const auto& txin : tx.vin) {
231 : 76381 : auto itByPrev = m_outpoint_to_orphan_it.find(txin.prevout);
232 [ + - ]: 76381 : if (itByPrev == m_outpoint_to_orphan_it.end()) continue;
233 [ # # ]: 0 : for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) {
234 [ # # ]: 0 : const CTransaction& orphanTx = *(*mi)->second.tx;
235 [ # # ]: 0 : vOrphanErase.push_back(orphanTx.GetWitnessHash());
236 : : }
237 : : }
238 : : }
239 : :
240 : : // Erase orphan transactions included or precluded by this block
241 [ - + ]: 7439 : if (vOrphanErase.size()) {
242 : 0 : int nErased = 0;
243 [ # # ]: 0 : for (const auto& orphanHash : vOrphanErase) {
244 [ # # ]: 0 : nErased += EraseTx(orphanHash);
245 : : }
246 [ # # # # : 0 : LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) included or conflicted by block\n", nErased);
# # ]
247 : : }
248 : 7439 : }
249 : :
250 : 3392 : 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 : 3392 : std::vector<OrphanMap::iterator> iters;
255 : :
256 : : // For each output, get all entries spending this prevout, filtering for ones from the specified peer.
257 [ + + ]: 245155 : for (unsigned int i = 0; i < parent->vout.size(); i++) {
258 : 241763 : const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(parent->GetHash(), i));
259 [ + + ]: 241763 : if (it_by_prev != m_outpoint_to_orphan_it.end()) {
260 [ + + ]: 9302 : for (const auto& elem : it_by_prev->second) {
261 [ + + ]: 4999 : if (elem->second.announcers.contains(nodeid)) {
262 [ + - ]: 1506 : 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 [ + + ]: 7029 : std::sort(iters.begin(), iters.end(), [](const auto& lhs, const auto& rhs) {
272 [ + + ]: 3637 : if (lhs->second.nTimeExpire == rhs->second.nTimeExpire) {
273 : 3359 : return &(*lhs) < &(*rhs);
274 : : } else {
275 : 278 : return lhs->second.nTimeExpire > rhs->second.nTimeExpire;
276 : : }
277 : : });
278 : : // Erase duplicates
279 : 3392 : iters.erase(std::unique(iters.begin(), iters.end()), iters.end());
280 : :
281 : : // Convert to a vector of CTransactionRef
282 : 3392 : std::vector<CTransactionRef> children_found;
283 [ + - ]: 3392 : children_found.reserve(iters.size());
284 [ + + ]: 4229 : for (const auto& child_iter : iters) {
285 [ + - ]: 837 : children_found.emplace_back(child_iter->second.tx);
286 : : }
287 : 3392 : return children_found;
288 : 3392 : }
289 : :
290 : 6 : std::vector<TxOrphanage::OrphanTxBase> TxOrphanage::GetOrphanTransactions() const
291 : : {
292 : 6 : std::vector<OrphanTxBase> ret;
293 [ + - ]: 6 : ret.reserve(m_orphans.size());
294 [ - + ]: 6 : for (auto const& o : m_orphans) {
295 [ # # ]: 0 : ret.push_back({o.second.tx, o.second.announcers, o.second.nTimeExpire});
296 : : }
297 : 6 : return ret;
298 [ # # # # ]: 0 : }
|
