Coverage Report

Created: 2025-06-10 13:21

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/bitcoin/src/txorphanage.cpp
Line
Count
Source
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
bool TxOrphanage::AddTx(const CTransactionRef& tx, NodeId peer)
16
302k
{
17
302k
    const Txid& hash = tx->GetHash();
18
302k
    const Wtxid& wtxid = tx->GetWitnessHash();
19
302k
    if (auto it{m_orphans.find(wtxid)}; it != m_orphans.end()) {
  Branch (19:41): [True: 7.65k, False: 295k]
20
7.65k
        AddAnnouncer(wtxid, peer);
21
        // No new orphan entry was created. An announcer may have been added.
22
7.65k
        return false;
23
7.65k
    }
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
295k
    unsigned int sz = GetTransactionWeight(*tx);
33
295k
    if (sz > MAX_STANDARD_TX_WEIGHT)
  Branch (33:9): [True: 0, False: 295k]
34
0
    {
35
0
        LogDebug(BCLog::TXPACKAGES, "ignoring large orphan tx (size: %u, txid: %s, wtxid: %s)\n", sz, hash.ToString(), wtxid.ToString());
36
0
        return false;
37
0
    }
38
39
295k
    auto ret = m_orphans.emplace(wtxid, OrphanTx{{tx, {peer}, Now<NodeSeconds>() + ORPHAN_TX_EXPIRE_TIME}, m_orphan_list.size()});
40
295k
    assert(ret.second);
  Branch (40:5): [True: 295k, False: 0]
41
295k
    m_orphan_list.push_back(ret.first);
42
344k
    for (const CTxIn& txin : tx->vin) {
  Branch (42:28): [True: 344k, False: 295k]
43
344k
        m_outpoint_to_orphan_it[txin.prevout].insert(ret.first);
44
344k
    }
45
295k
    m_total_orphan_usage += sz;
46
295k
    m_total_announcements += 1;
47
295k
    auto& peer_info = m_peer_orphanage_info.try_emplace(peer).first->second;
48
295k
    peer_info.m_total_usage += sz;
49
50
295k
    LogDebug(BCLog::TXPACKAGES, "stored orphan tx %s (wtxid=%s), weight: %u (mapsz %u outsz %u)\n", hash.ToString(), wtxid.ToString(), sz,
51
295k
             m_orphans.size(), m_outpoint_to_orphan_it.size());
52
295k
    return true;
53
295k
}
54
55
bool TxOrphanage::AddAnnouncer(const Wtxid& wtxid, NodeId peer)
56
17.7k
{
57
17.7k
    const auto it = m_orphans.find(wtxid);
58
17.7k
    if (it != m_orphans.end()) {
  Branch (58:9): [True: 17.7k, False: 0]
59
17.7k
        Assume(!it->second.announcers.empty());
60
17.7k
        const auto ret = it->second.announcers.insert(peer);
61
17.7k
        if (ret.second) {
  Branch (61:13): [True: 17.7k, False: 0]
62
17.7k
            auto& peer_info = m_peer_orphanage_info.try_emplace(peer).first->second;
63
17.7k
            peer_info.m_total_usage += it->second.GetUsage();
64
17.7k
            m_total_announcements += 1;
65
17.7k
            LogDebug(BCLog::TXPACKAGES, "added peer=%d as announcer of orphan tx %s\n", peer, wtxid.ToString());
66
17.7k
            return true;
67
17.7k
        }
68
17.7k
    }
69
0
    return false;
70
17.7k
}
71
72
int TxOrphanage::EraseTx(const Wtxid& wtxid)
73
353k
{
74
353k
    std::map<Wtxid, OrphanTx>::iterator it = m_orphans.find(wtxid);
75
353k
    if (it == m_orphans.end())
  Branch (75:9): [True: 58.0k, False: 295k]
76
58.0k
        return 0;
77
295k
    for (const CTxIn& txin : it->second.tx->vin)
  Branch (77:28): [True: 344k, False: 295k]
78
344k
    {
79
344k
        auto itPrev = m_outpoint_to_orphan_it.find(txin.prevout);
80
344k
        if (itPrev == m_outpoint_to_orphan_it.end())
  Branch (80:13): [True: 0, False: 344k]
81
0
            continue;
82
344k
        itPrev->second.erase(it);
83
344k
        if (itPrev->second.empty())
  Branch (83:13): [True: 316k, False: 28.9k]
84
316k
            m_outpoint_to_orphan_it.erase(itPrev);
85
344k
    }
86
87
295k
    const auto tx_size{it->second.GetUsage()};
88
295k
    m_total_orphan_usage -= tx_size;
89
295k
    m_total_announcements -= it->second.announcers.size();
90
    // Decrement each announcer's m_total_usage
91
295k
    for (const auto& peer : it->second.announcers) {
  Branch (91:27): [True: 93.9k, False: 295k]
92
93.9k
        auto peer_it = m_peer_orphanage_info.find(peer);
93
93.9k
        if (Assume(peer_it != m_peer_orphanage_info.end())) {
94
93.9k
            peer_it->second.m_total_usage -= tx_size;
95
93.9k
        }
96
93.9k
    }
97
98
295k
    size_t old_pos = it->second.list_pos;
99
295k
    assert(m_orphan_list[old_pos] == it);
  Branch (99:5): [True: 295k, False: 0]
100
295k
    if (old_pos + 1 != m_orphan_list.size()) {
  Branch (100:9): [True: 262k, False: 32.3k]
101
        // Unless we're deleting the last entry in m_orphan_list, move the last
102
        // entry to the position we're deleting.
103
262k
        auto it_last = m_orphan_list.back();
104
262k
        m_orphan_list[old_pos] = it_last;
105
262k
        it_last->second.list_pos = old_pos;
106
262k
    }
107
295k
    const auto& txid = it->second.tx->GetHash();
108
    // Time spent in orphanage = difference between current and entry time.
109
    // Entry time is equal to ORPHAN_TX_EXPIRE_TIME earlier than entry's expiry.
110
295k
    LogDebug(BCLog::TXPACKAGES, "   removed orphan tx %s (wtxid=%s) after %ds\n", txid.ToString(), wtxid.ToString(),
111
295k
             Ticks<std::chrono::seconds>(NodeClock::now() + ORPHAN_TX_EXPIRE_TIME - it->second.nTimeExpire));
112
295k
    m_orphan_list.pop_back();
113
114
295k
    m_orphans.erase(it);
115
295k
    return 1;
116
295k
}
117
118
void TxOrphanage::EraseForPeer(NodeId peer)
119
88.7k
{
120
    // Zeroes out this peer's m_total_usage.
121
88.7k
    m_peer_orphanage_info.erase(peer);
122
123
88.7k
    int nErased = 0;
124
88.7k
    std::map<Wtxid, OrphanTx>::iterator iter = m_orphans.begin();
125
872k
    while (iter != m_orphans.end())
  Branch (125:12): [True: 784k, False: 88.7k]
126
784k
    {
127
        // increment to avoid iterator becoming invalid after erasure
128
784k
        auto& [wtxid, orphan] = *iter++;
129
784k
        auto orphan_it = orphan.announcers.find(peer);
130
784k
        if (orphan_it != orphan.announcers.end()) {
  Branch (130:13): [True: 219k, False: 565k]
131
219k
            orphan.announcers.erase(peer);
132
219k
            m_total_announcements -= 1;
133
134
            // No remaining announcers: clean up entry
135
219k
            if (orphan.announcers.empty()) {
  Branch (135:17): [True: 206k, False: 12.8k]
136
206k
                nErased += EraseTx(orphan.tx->GetWitnessHash());
137
206k
            }
138
219k
        }
139
784k
    }
140
88.7k
    if (nErased > 0) LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) from peer=%d\n", nErased, peer);
  Branch (140:9): [True: 12.7k, False: 75.9k]
141
88.7k
}
142
143
void TxOrphanage::LimitOrphans(unsigned int max_orphans, FastRandomContext& rng)
144
295k
{
145
295k
    unsigned int nEvicted = 0;
146
295k
    auto nNow{Now<NodeSeconds>()};
147
295k
    if (m_next_sweep <= nNow) {
  Branch (147:9): [True: 9.21k, False: 286k]
148
        // Sweep out expired orphan pool entries:
149
9.21k
        int nErased = 0;
150
9.21k
        auto nMinExpTime{nNow + ORPHAN_TX_EXPIRE_TIME - ORPHAN_TX_EXPIRE_INTERVAL};
151
9.21k
        std::map<Wtxid, OrphanTx>::iterator iter = m_orphans.begin();
152
73.9k
        while (iter != m_orphans.end())
  Branch (152:16): [True: 64.7k, False: 9.21k]
153
64.7k
        {
154
64.7k
            std::map<Wtxid, OrphanTx>::iterator maybeErase = iter++;
155
64.7k
            if (maybeErase->second.nTimeExpire <= nNow) {
  Branch (155:17): [True: 54.8k, False: 9.87k]
156
54.8k
                nErased += EraseTx(maybeErase->first);
157
54.8k
            } else {
158
9.87k
                nMinExpTime = std::min(maybeErase->second.nTimeExpire, nMinExpTime);
159
9.87k
            }
160
64.7k
        }
161
        // Sweep again 5 minutes after the next entry that expires in order to batch the linear scan.
162
9.21k
        m_next_sweep = nMinExpTime + ORPHAN_TX_EXPIRE_INTERVAL;
163
9.21k
        if (nErased > 0) LogDebug(BCLog::TXPACKAGES, "Erased %d orphan tx due to expiration\n", nErased);
  Branch (163:13): [True: 2.18k, False: 7.03k]
164
9.21k
    }
165
317k
    while (m_orphans.size() > max_orphans)
  Branch (165:12): [True: 22.6k, False: 295k]
166
22.6k
    {
167
        // Evict a random orphan:
168
22.6k
        size_t randompos = rng.randrange(m_orphan_list.size());
169
22.6k
        EraseTx(m_orphan_list[randompos]->first);
170
22.6k
        ++nEvicted;
171
22.6k
    }
172
295k
    if (nEvicted > 0) LogDebug(BCLog::TXPACKAGES, "orphanage overflow, removed %u tx\n", nEvicted);
  Branch (172:9): [True: 22.6k, False: 272k]
173
295k
}
174
175
void TxOrphanage::AddChildrenToWorkSet(const CTransaction& tx, FastRandomContext& rng)
176
38.1k
{
177
80.5k
    for (unsigned int i = 0; i < tx.vout.size(); i++) {
  Branch (177:30): [True: 42.3k, False: 38.1k]
178
42.3k
        const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(tx.GetHash(), i));
179
42.3k
        if (it_by_prev != m_outpoint_to_orphan_it.end()) {
  Branch (179:13): [True: 7.70k, False: 34.6k]
180
11.1k
            for (const auto& elem : it_by_prev->second) {
  Branch (180:35): [True: 11.1k, False: 7.70k]
181
                // Belt and suspenders, each orphan should always have at least 1 announcer.
182
11.1k
                if (!Assume(!elem->second.announcers.empty())) continue;
  Branch (182:21): [True: 0, False: 11.1k]
183
184
                // Select a random peer to assign orphan processing, reducing wasted work if the orphan is still missing
185
                // inputs. However, we don't want to create an issue in which the assigned peer can purposefully stop us
186
                // from processing the orphan by disconnecting.
187
11.1k
                auto announcer_iter = std::begin(elem->second.announcers);
188
11.1k
                std::advance(announcer_iter, rng.randrange(elem->second.announcers.size()));
189
11.1k
                auto announcer = *(announcer_iter);
190
191
                // Get this source peer's work set, emplacing an empty set if it didn't exist
192
                // (note: if this peer wasn't still connected, we would have removed the orphan tx already)
193
11.1k
                std::set<Wtxid>& orphan_work_set = m_peer_orphanage_info.try_emplace(announcer).first->second.m_work_set;
194
                // Add this tx to the work set
195
11.1k
                orphan_work_set.insert(elem->first);
196
11.1k
                LogDebug(BCLog::TXPACKAGES, "added %s (wtxid=%s) to peer %d workset\n",
197
11.1k
                         tx.GetHash().ToString(), tx.GetWitnessHash().ToString(), announcer);
198
11.1k
            }
199
7.70k
        }
200
42.3k
    }
201
38.1k
}
202
203
bool TxOrphanage::HaveTx(const Wtxid& wtxid) const
204
1.78M
{
205
1.78M
    return m_orphans.count(wtxid);
206
1.78M
}
207
208
CTransactionRef TxOrphanage::GetTx(const Wtxid& wtxid) const
209
413k
{
210
413k
    auto it = m_orphans.find(wtxid);
211
413k
    return it != m_orphans.end() ? it->second.tx : nullptr;
  Branch (211:12): [True: 28.2k, False: 385k]
212
413k
}
213
214
bool TxOrphanage::HaveTxFromPeer(const Wtxid& wtxid, NodeId peer) const
215
329k
{
216
329k
    auto it = m_orphans.find(wtxid);
217
329k
    return (it != m_orphans.end() && it->second.announcers.contains(peer));
  Branch (217:13): [True: 34.5k, False: 295k]
  Branch (217:38): [True: 16.8k, False: 17.7k]
218
329k
}
219
220
CTransactionRef TxOrphanage::GetTxToReconsider(NodeId peer)
221
42.4M
{
222
42.4M
    auto peer_it = m_peer_orphanage_info.find(peer);
223
42.4M
    if (peer_it == m_peer_orphanage_info.end()) return nullptr;
  Branch (223:9): [True: 37.6M, False: 4.80M]
224
225
4.80M
    auto& work_set = peer_it->second.m_work_set;
226
4.80M
    while (!work_set.empty()) {
  Branch (226:12): [True: 9.46k, False: 4.79M]
227
9.46k
        Wtxid wtxid = *work_set.begin();
228
9.46k
        work_set.erase(work_set.begin());
229
230
9.46k
        const auto orphan_it = m_orphans.find(wtxid);
231
9.46k
        if (orphan_it != m_orphans.end()) {
  Branch (231:13): [True: 9.41k, False: 49]
232
9.41k
            return orphan_it->second.tx;
233
9.41k
        }
234
9.46k
    }
235
4.79M
    return nullptr;
236
4.80M
}
237
238
bool TxOrphanage::HaveTxToReconsider(NodeId peer)
239
5.50M
{
240
5.50M
    auto peer_it = m_peer_orphanage_info.find(peer);
241
5.50M
    if (peer_it == m_peer_orphanage_info.end()) return false;
  Branch (241:9): [True: 3.32M, False: 2.17M]
242
243
2.17M
    auto& work_set = peer_it->second.m_work_set;
244
2.17M
    return !work_set.empty();
245
5.50M
}
246
247
void TxOrphanage::EraseForBlock(const CBlock& block)
248
2.23M
{
249
2.23M
    std::vector<Wtxid> vOrphanErase;
250
251
2.25M
    for (const CTransactionRef& ptx : block.vtx) {
  Branch (251:37): [True: 2.25M, False: 2.23M]
252
2.25M
        const CTransaction& tx = *ptx;
253
254
        // Which orphan pool entries must we evict?
255
2.25M
        for (const auto& txin : tx.vin) {
  Branch (255:31): [True: 2.25M, False: 2.25M]
256
2.25M
            auto itByPrev = m_outpoint_to_orphan_it.find(txin.prevout);
257
2.25M
            if (itByPrev == m_outpoint_to_orphan_it.end()) continue;
  Branch (257:17): [True: 2.25M, False: 2.24k]
258
4.57k
            for (auto mi = itByPrev->second.begin(); mi != itByPrev->second.end(); ++mi) {
  Branch (258:54): [True: 2.32k, False: 2.24k]
259
2.32k
                const CTransaction& orphanTx = *(*mi)->second.tx;
260
2.32k
                vOrphanErase.push_back(orphanTx.GetWitnessHash());
261
2.32k
            }
262
2.24k
        }
263
2.25M
    }
264
265
    // Erase orphan transactions included or precluded by this block
266
2.23M
    if (vOrphanErase.size()) {
  Branch (266:9): [True: 459, False: 2.23M]
267
459
        int nErased = 0;
268
2.32k
        for (const auto& orphanHash : vOrphanErase) {
  Branch (268:37): [True: 2.32k, False: 459]
269
2.32k
            nErased += EraseTx(orphanHash);
270
2.32k
        }
271
459
        LogDebug(BCLog::TXPACKAGES, "Erased %d orphan transaction(s) included or conflicted by block\n", nErased);
272
459
    }
273
2.23M
}
274
275
std::vector<CTransactionRef> TxOrphanage::GetChildrenFromSamePeer(const CTransactionRef& parent, NodeId nodeid) const
276
4.76k
{
277
    // First construct a vector of iterators to ensure we do not return duplicates of the same tx
278
    // and so we can sort by nTimeExpire.
279
4.76k
    std::vector<OrphanMap::iterator> iters;
280
281
    // For each output, get all entries spending this prevout, filtering for ones from the specified peer.
282
16.1k
    for (unsigned int i = 0; i < parent->vout.size(); i++) {
  Branch (282:30): [True: 11.3k, False: 4.76k]
283
11.3k
        const auto it_by_prev = m_outpoint_to_orphan_it.find(COutPoint(parent->GetHash(), i));
284
11.3k
        if (it_by_prev != m_outpoint_to_orphan_it.end()) {
  Branch (284:13): [True: 7.46k, False: 3.91k]
285
16.8k
            for (const auto& elem : it_by_prev->second) {
  Branch (285:35): [True: 16.8k, False: 7.46k]
286
16.8k
                if (elem->second.announcers.contains(nodeid)) {
  Branch (286:21): [True: 15.3k, False: 1.48k]
287
15.3k
                    iters.emplace_back(elem);
288
15.3k
                }
289
16.8k
            }
290
7.46k
        }
291
11.3k
    }
292
293
    // Sort by address so that duplicates can be deleted. At the same time, sort so that more recent
294
    // orphans (which expire later) come first.  Break ties based on address, as nTimeExpire is
295
    // quantified in seconds and it is possible for orphans to have the same expiry.
296
57.3k
    std::sort(iters.begin(), iters.end(), [](const auto& lhs, const auto& rhs) {
297
57.3k
        if (lhs->second.nTimeExpire == rhs->second.nTimeExpire) {
  Branch (297:13): [True: 51.1k, False: 6.22k]
298
51.1k
            return &(*lhs) < &(*rhs);
299
51.1k
        } else {
300
6.22k
            return lhs->second.nTimeExpire > rhs->second.nTimeExpire;
301
6.22k
        }
302
57.3k
    });
303
    // Erase duplicates
304
4.76k
    iters.erase(std::unique(iters.begin(), iters.end()), iters.end());
305
306
    // Convert to a vector of CTransactionRef
307
4.76k
    std::vector<CTransactionRef> children_found;
308
4.76k
    children_found.reserve(iters.size());
309
5.47k
    for (const auto& child_iter : iters) {
  Branch (309:33): [True: 5.47k, False: 4.76k]
310
5.47k
        children_found.emplace_back(child_iter->second.tx);
311
5.47k
    }
312
4.76k
    return children_found;
313
4.76k
}
314
315
std::vector<TxOrphanage::OrphanTxBase> TxOrphanage::GetOrphanTransactions() const
316
0
{
317
0
    std::vector<OrphanTxBase> ret;
318
0
    ret.reserve(m_orphans.size());
319
0
    for (auto const& o : m_orphans) {
  Branch (319:24): [True: 0, False: 0]
320
0
        ret.push_back({o.second.tx, o.second.announcers, o.second.nTimeExpire});
321
0
    }
322
0
    return ret;
323
0
}
324
325
void TxOrphanage::SanityCheck() const
326
0
{
327
    // Check that cached m_total_announcements is correct
328
0
    unsigned int counted_total_announcements{0};
329
    // Check that m_total_orphan_usage is correct
330
0
    unsigned int counted_total_usage{0};
331
332
    // Check that cached PeerOrphanInfo::m_total_size is correct
333
0
    std::map<NodeId, unsigned int> counted_size_per_peer;
334
335
0
    for (const auto& [wtxid, orphan] : m_orphans) {
  Branch (335:38): [True: 0, False: 0]
336
0
        counted_total_announcements += orphan.announcers.size();
337
0
        counted_total_usage += orphan.GetUsage();
338
339
0
        Assume(!orphan.announcers.empty());
340
0
        for (const auto& peer : orphan.announcers) {
  Branch (340:31): [True: 0, False: 0]
341
0
            auto& count_peer_entry = counted_size_per_peer.try_emplace(peer).first->second;
342
0
            count_peer_entry += orphan.GetUsage();
343
0
        }
344
0
    }
345
346
0
    Assume(m_total_announcements >= m_orphans.size());
347
0
    Assume(counted_total_announcements == m_total_announcements);
348
0
    Assume(counted_total_usage == m_total_orphan_usage);
349
350
    // There must be an entry in m_peer_orphanage_info for each peer
351
    // However, there may be m_peer_orphanage_info entries corresponding to peers for whom we
352
    // previously had orphans but no longer do.
353
0
    Assume(counted_size_per_peer.size() <= m_peer_orphanage_info.size());
354
355
0
    for (const auto& [peerid, info] : m_peer_orphanage_info) {
  Branch (355:37): [True: 0, False: 0]
356
0
        auto it_counted = counted_size_per_peer.find(peerid);
357
0
        if (it_counted == counted_size_per_peer.end()) {
  Branch (357:13): [True: 0, False: 0]
358
0
            Assume(info.m_total_usage == 0);
359
0
        } else {
360
0
            Assume(it_counted->second == info.m_total_usage);
361
0
        }
362
0
    }
363
0
}