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 : :
11 : : #include <cassert>
12 : :
13 : : /** Expiration time for orphan transactions in seconds */
14 : : static constexpr int64_t ORPHAN_TX_EXPIRE_TIME = 20 * 60;
15 : : /** Minimum time between orphan transactions expire time checks in seconds */
16 : : static constexpr int64_t ORPHAN_TX_EXPIRE_INTERVAL = 5 * 60;
17 [ + - ]: 190 :
18 [ + - ]: 190 :
19 : 98210 : bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer)
20 : : {
21 : 98210 : LOCK(m_mutex);
22 : :
23 [ + - ]: 98210 : const uint256& hash = tx->GetHash();
24 [ + - + + ]: 98210 : if (m_orphans.count(hash))
25 : 22506 : return false;
26 : :
27 : : // Ignore big transactions, to avoid a
28 : : // send-big-orphans memory exhaustion attack. If a peer has a legitimate
29 : : // large transaction with a missing parent then we assume
30 : : // it will rebroadcast it later, after the parent transaction(s)
31 : : // have been mined or received.
32 : : // 100 orphans, each of which is at most 100,000 bytes big is
33 : : // at most 10 megabytes of orphans and somewhat more byprev index (in the worst case):
34 [ + - ]: 75704 : unsigned int sz = GetTransactionWeight(*tx);
35 [ + + ]: 75704 : if (sz > MAX_STANDARD_TX_WEIGHT)
36 : : {
37 [ + - + - : 3694 : LogPrint(BCLog::MEMPOOL, "ignoring large orphan tx (size: %u, hash: %s)\n", sz, hash.ToString());
# # # # #
# # # ]
38 : 3694 : return false;
39 : : }
40 : :
41 [ + - + - ]: 72010 : auto ret = m_orphans.emplace(hash, OrphanTx{tx, peer, GetTime() + ORPHAN_TX_EXPIRE_TIME, m_orphan_list.size()});
42 [ + - ]: 72010 : assert(ret.second);
43 [ + - ]: 72010 : m_orphan_list.push_back(ret.first);
44 : : // Allow for lookups in the orphan pool by wtxid, as well as txid
45 [ + - + - ]: 72010 : m_wtxid_to_orphan_it.emplace(tx->GetWitnessHash(), ret.first);
46 [ + + ]: 2425601 : for (const CTxIn& txin : tx->vin) {
47 [ + - + - ]: 2353591 : m_outpoint_to_orphan_it[txin.prevout].insert(ret.first);
48 : : }
49 : :
50 [ + - + - : 72010 : LogPrint(BCLog::MEMPOOL, "stored orphan tx %s (mapsz %u outsz %u)\n", hash.ToString(),
# # # # #
# # # ]
51 : : m_orphans.size(), m_outpoint_to_orphan_it.size());
52 : 72010 : return true;
53 : 98210 : }
54 : :
55 : 71564 : int TxOrphanage::EraseTx(const uint256& txid)
56 : : {
57 : 71564 : LOCK(m_mutex);
58 [ + - ]: 71564 : return _EraseTx(txid);
59 : 71564 : }
60 : :
61 : 133183 : int TxOrphanage::_EraseTx(const uint256& txid)
62 : : {
63 : 133183 : AssertLockHeld(m_mutex);
64 : 133183 : std::map<uint256, OrphanTx>::iterator it = m_orphans.find(txid);
65 [ + + ]: 133183 : if (it == m_orphans.end())
66 : 65000 : return 0;
67 [ + + ]: 2270069 : for (const CTxIn& txin : it->second.tx->vin)
68 : : {
69 : 2201886 : auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout);
70 [ + + ]: 2201886 : if (itPrev == m_outpoint_to_orphan_it.end())
71 : 154220 : continue;
72 : 2047666 : itPrev->second.erase(it);
73 [ + + ]: 2047666 : if (itPrev->second.empty())
74 : 1368495 : m_outpoint_to_orphan_it.erase(itPrev);
75 : : }
76 : :
77 : 68183 : size_t old_pos = it->second.list_pos;
78 [ + - ]: 68183 : assert(m_orphan_list[old_pos] == it);
79 [ + - + + ]: 68373 : if (old_pos + 1 != m_orphan_list.size()) {
80 : : // Unless we're deleting the last entry in m_orphan_list, move the last
81 : : // entry to the position we're deleting.
82 : 51595 : auto it_last = m_orphan_list.back();
83 : 51595 : m_orphan_list[old_pos] = it_last;
84 : 51595 : it_last->second.list_pos = old_pos;
85 : 51595 : }
86 : 68183 : m_orphan_list.pop_back();
87 : 68183 : m_wtxid_to_orphan_it.erase(it->second.tx->GetWitnessHash());
88 : :
89 : 68183 : m_orphans.erase(it);
90 : 68183 : return 1;
91 : 133183 : }
92 : :
93 : 151240 : void TxOrphanage::EraseForPeer(NodeId peer)
94 : : {
95 : 151240 : LOCK(m_mutex);
96 : :
97 [ + - ]: 151240 : m_peer_work_set.erase(peer);
98 : :
99 : 151240 : int nErased = 0;
100 : 151240 : std::map<uint256, OrphanTx>::iterator iter = m_orphans.begin();
101 [ + + ]: 261887 : while (iter != m_orphans.end())
102 : : {
103 : 110647 : std::map<uint256, OrphanTx>::iterator maybeErase = iter++; // increment to avoid iterator becoming invalid
104 [ + + ]: 110647 : if (maybeErase->second.fromPeer == peer)
105 : : {
106 [ + - + - ]: 45310 : nErased += _EraseTx(maybeErase->second.tx->GetHash());
107 : 45310 : }
108 : : }
109 [ + + + - : 151240 : if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx from peer=%d\n", nErased, peer);
+ - # # #
# # # ]
110 : 151240 : }
111 : :
112 : 76973 : void TxOrphanage::LimitOrphans(unsigned int max_orphans)
113 : : {
114 : 76973 : LOCK(m_mutex);
115 : :
116 : 76973 : unsigned int nEvicted = 0;
117 : : static int64_t nNextSweep;
118 [ + - ]: 76973 : int64_t nNow = GetTime();
119 [ + + ]: 76973 : if (nNextSweep <= nNow) {
120 : : // Sweep out expired orphan pool entries:
121 : 21 : int nErased = 0;
122 : 21 : int64_t nMinExpTime = nNow + ORPHAN_TX_EXPIRE_TIME - ORPHAN_TX_EXPIRE_INTERVAL;
123 : 21 : std::map<uint256, OrphanTx>::iterator iter = m_orphans.begin();
124 [ + + ]: 41 : while (iter != m_orphans.end())
125 : : {
126 : 20 : std::map<uint256, OrphanTx>::iterator maybeErase = iter++;
127 [ + + ]: 20 : if (maybeErase->second.nTimeExpire <= nNow) {
128 [ + - + - ]: 6 : nErased += _EraseTx(maybeErase->second.tx->GetHash());
129 : 6 : } else {
130 [ + - ]: 14 : nMinExpTime = std::min(maybeErase->second.nTimeExpire, nMinExpTime);
131 : : }
132 : : }
133 : : // Sweep again 5 minutes after the next entry that expires in order to batch the linear scan.
134 : 21 : nNextSweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL;
135 [ + + + - : 21 : if (nErased > 0) LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx due to expiration\n", nErased);
+ - # # #
# # # ]
136 : 21 : }
137 : 76973 : FastRandomContext rng;
138 [ + + ]: 93276 : while (m_orphans.size() > max_orphans)
139 : : {
140 : : // Evict a random orphan:
141 : 16303 : size_t randompos = rng.randrange(m_orphan_list.size());
142 [ + - ]: 16303 : _EraseTx(m_orphan_list[randompos]->first);
143 : 16303 : ++nEvicted;
144 : : }
145 [ + + + - : 76973 : if (nEvicted > 0) LogPrint(BCLog::MEMPOOL, "orphanage overflow, removed %u tx\n", nEvicted);
+ - # # #
# # # ]
146 : 76973 : }
147 : :
148 : 11187 : void TxOrphanage::AddChildrenToWorkSet(const CTransaction& tx)
149 : : {
150 : 11187 : LOCK(m_mutex);
151 : :
152 : :
153 [ + + ]: 19615175 : for (unsigned int i = 0; i < tx.vout.size(); i++) {
154 [ + - + - : 19603988 : const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(tx.GetHash(), i));
+ - ]
155 [ + + ]: 19603988 : if (it_by_prev != m_outpoint_to_orphan_it.end()) {
156 [ + + ]: 18779 : for (const auto& elem : it_by_prev->second) {
157 : : // Get this source peer's work set, emplacing an empty set if it didn't exist
158 : : // (note: if this peer wasn't still connected, we would have removed the orphan tx already)
159 [ + - ]: 13468 : std::set<uint256>& orphan_work_set = m_peer_work_set.try_emplace(elem->second.fromPeer).first->second;
160 : : // Add this tx to the work set
161 [ + - ]: 13468 : orphan_work_set.insert(elem->first);
162 : : }
163 : 5311 : }
164 : 19603988 : }
165 : 11187 : }
166 : :
167 : 1909323 : bool TxOrphanage::HaveTx(const GenTxid& gtxid) const
168 : : {
169 : 1909323 : LOCK(m_mutex);
170 [ + - + + ]: 1909323 : if (gtxid.IsWtxid()) {
171 [ + - + - ]: 307951 : return m_wtxid_to_orphan_it.count(gtxid.GetHash());
172 : : } else {
173 [ + - + - ]: 1601372 : return m_orphans.count(gtxid.GetHash());
174 : : }
175 : 1909323 : }
176 : :
177 : 3669144 : CTransactionRef TxOrphanage::GetTxToReconsider(NodeId peer)
178 : : {
179 : 3669144 : LOCK(m_mutex);
180 : :
181 [ + - ]: 3669144 : auto work_set_it = m_peer_work_set.find(peer);
182 [ + + ]: 3669144 : if (work_set_it != m_peer_work_set.end()) {
183 : 2 : auto& work_set = work_set_it->second;
184 [ + - ]: 2 : while (!work_set.empty()) {
185 : 2 : uint256 txid = *work_set.begin();
186 [ + - ]: 2 : work_set.erase(work_set.begin());
187 : :
188 [ + - ]: 2 : const auto orphan_it = m_orphans.find(txid);
189 [ - + ]: 2 : if (orphan_it != m_orphans.end()) {
190 : 2 : return orphan_it->second.tx;
191 : : }
192 : : }
193 : 0 : }
194 : 3669142 : return nullptr;
195 : 3669144 : }
196 : :
197 : 1671569 : bool TxOrphanage::HaveTxToReconsider(NodeId peer)
198 : : {
199 : 1671569 : LOCK(m_mutex);
200 : :
201 [ + - ]: 1671569 : auto work_set_it = m_peer_work_set.find(peer);
202 [ - + ]: 1671569 : if (work_set_it != m_peer_work_set.end()) {
203 : 0 : auto& work_set = work_set_it->second;
204 : 0 : return !work_set.empty();
205 : : }
206 : 1671569 : return false;
207 : 1671569 : }
208 : :
209 : 0 : void TxOrphanage::EraseForBlock(const CBlock& block)
210 : : {
211 : 0 : LOCK(m_mutex);
212 : :
213 : 0 : std::vector<uint256> vOrphanErase;
214 : :
215 [ # # ]: 0 : for (const CTransactionRef& ptx : block.vtx) {
216 : 0 : const CTransaction& tx = *ptx;
217 : :
218 : : // Which orphan pool entries must we evict?
219 [ # # ]: 0 : for (const auto& txin : tx.vin) {
220 [ # # ]: 0 : auto itByPrev = m_outpoint_to_orphan_it.find(txin.prevout);
221 [ # # ]: 0 : if (itByPrev == m_outpoint_to_orphan_it.end()) continue;
222 [ # # ]: 0 : for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) {
223 : 0 : const CTransaction& orphanTx = *(*mi)->second.tx;
224 [ # # ]: 0 : const uint256& orphanHash = orphanTx.GetHash();
225 [ # # ]: 0 : vOrphanErase.push_back(orphanHash);
226 : 0 : }
227 : : }
228 : : }
229 : :
230 : : // Erase orphan transactions included or precluded by this block
231 [ # # ]: 0 : if (vOrphanErase.size()) {
232 : 0 : int nErased = 0;
233 [ # # ]: 0 : for (const uint256& orphanHash : vOrphanErase) {
234 [ # # ]: 0 : nErased += _EraseTx(orphanHash);
235 : : }
236 [ # # # # : 0 : LogPrint(BCLog::MEMPOOL, "Erased %d orphan tx included or conflicted by block\n", nErased);
# # # # #
# ]
237 : 0 : }
238 : 0 : }
|
