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 : : #ifndef BITCOIN_TXORPHANAGE_H
6 : : #define BITCOIN_TXORPHANAGE_H
7 : :
8 : : #include <consensus/validation.h>
9 : : #include <net.h>
10 : : #include <primitives/block.h>
11 : : #include <primitives/transaction.h>
12 : : #include <sync.h>
13 : : #include <util/time.h>
14 : :
15 : : #include <map>
16 : : #include <set>
17 : :
18 : : /** Expiration time for orphan transactions */
19 : : static constexpr auto ORPHAN_TX_EXPIRE_TIME{20min};
20 : : /** Minimum time between orphan transactions expire time checks */
21 : : static constexpr auto ORPHAN_TX_EXPIRE_INTERVAL{5min};
22 : :
23 : : /** A class to track orphan transactions (failed on TX_MISSING_INPUTS)
24 : : * Since we cannot distinguish orphans from bad transactions with
25 : : * non-existent inputs, we heavily limit the number of orphans
26 : : * we keep and the duration we keep them for.
27 : : * Not thread-safe. Requires external synchronization.
28 : : */
29 : : class TxOrphanage {
30 : : public:
31 : : /** Add a new orphan transaction */
32 : : bool AddTx(const CTransactionRef& tx, NodeId peer);
33 : :
34 : : /** Add an additional announcer to an orphan if it exists. Otherwise, do nothing. */
35 : : bool AddAnnouncer(const Wtxid& wtxid, NodeId peer);
36 : :
37 : : CTransactionRef GetTx(const Wtxid& wtxid) const;
38 : :
39 : : /** Check if we already have an orphan transaction (by wtxid only) */
40 : : bool HaveTx(const Wtxid& wtxid) const;
41 : :
42 : : /** Check if a {tx, peer} exists in the orphanage.*/
43 : : bool HaveTxFromPeer(const Wtxid& wtxid, NodeId peer) const;
44 : :
45 : : /** Extract a transaction from a peer's work set
46 : : * Returns nullptr if there are no transactions to work on.
47 : : * Otherwise returns the transaction reference, and removes
48 : : * it from the work set.
49 : : */
50 : : CTransactionRef GetTxToReconsider(NodeId peer);
51 : :
52 : : /** Erase an orphan by wtxid */
53 : : int EraseTx(const Wtxid& wtxid);
54 : :
55 : : /** Maybe erase all orphans announced by a peer (eg, after that peer disconnects). If an orphan
56 : : * has been announced by another peer, don't erase, just remove this peer from the list of announcers. */
57 : : void EraseForPeer(NodeId peer);
58 : :
59 : : /** Erase all orphans included in or invalidated by a new block */
60 : : void EraseForBlock(const CBlock& block);
61 : :
62 : : /** Limit the orphanage to the given maximum */
63 : : void LimitOrphans(unsigned int max_orphans, FastRandomContext& rng);
64 : :
65 : : /** Add any orphans that list a particular tx as a parent into the from peer's work set */
66 : : void AddChildrenToWorkSet(const CTransaction& tx, FastRandomContext& rng);
67 : :
68 : : /** Does this peer have any work to do? */
69 : : bool HaveTxToReconsider(NodeId peer);
70 : :
71 : : /** Get all children that spend from this tx and were received from nodeid. Sorted from most
72 : : * recent to least recent. */
73 : : std::vector<CTransactionRef> GetChildrenFromSamePeer(const CTransactionRef& parent, NodeId nodeid) const;
74 : :
75 : : /** Return how many entries exist in the orphange */
76 : 19677 : size_t Size() const
77 : : {
78 [ - + ]: 19677 : return m_orphans.size();
79 : : }
80 : :
81 : : /** Allows providing orphan information externally */
82 : : struct OrphanTxBase {
83 : : CTransactionRef tx;
84 : : /** Peers added with AddTx or AddAnnouncer. */
85 : : std::set<NodeId> announcers;
86 : : NodeSeconds nTimeExpire;
87 : :
88 : : /** Get the weight of this transaction, an approximation of its memory usage. */
89 : 37462 : unsigned int GetUsage() const {
90 [ + - ]: 37462 : return GetTransactionWeight(*tx);
91 : : }
92 : : };
93 : :
94 : : std::vector<OrphanTxBase> GetOrphanTransactions() const;
95 : :
96 : : /** Get the total usage (weight) of all orphans. If an orphan has multiple announcers, its usage is
97 : : * only counted once within this total. */
98 [ - + ]: 429151 : unsigned int TotalOrphanUsage() const { return m_total_orphan_usage; }
99 : :
100 : : /** Total usage (weight) of orphans for which this peer is an announcer. If an orphan has multiple
101 : : * announcers, its weight will be accounted for in each PeerOrphanInfo, so the total of all
102 : : * peers' UsageByPeer() may be larger than TotalOrphanBytes(). */
103 : 525614 : unsigned int UsageByPeer(NodeId peer) const {
104 : 525614 : auto peer_it = m_peer_orphanage_info.find(peer);
105 [ + + ]: 525614 : return peer_it == m_peer_orphanage_info.end() ? 0 : peer_it->second.m_total_usage;
106 : : }
107 : :
108 : : /** Check consistency between PeerOrphanInfo and m_orphans. Recalculate counters and ensure they
109 : : * match what is cached. */
110 : : void SanityCheck() const;
111 : :
112 : : protected:
113 [ - + ]: 96225 : struct OrphanTx : public OrphanTxBase {
114 : : size_t list_pos;
115 : : };
116 : :
117 : : /** Total usage (weight) of all entries in m_orphans. */
118 : : unsigned int m_total_orphan_usage{0};
119 : :
120 : : /** Total number of <peer, tx> pairs. Can be larger than m_orphans.size() because multiple peers
121 : : * may have announced the same orphan. */
122 : : unsigned int m_total_announcements{0};
123 : :
124 : : /** Map from wtxid to orphan transaction record. Limited by
125 : : * -maxorphantx/DEFAULT_MAX_ORPHAN_TRANSACTIONS */
126 : : std::map<Wtxid, OrphanTx> m_orphans;
127 : :
128 : 5243 : struct PeerOrphanInfo {
129 : : /** List of transactions that should be reconsidered: added to in AddChildrenToWorkSet,
130 : : * removed from one-by-one with each call to GetTxToReconsider. The wtxids may refer to
131 : : * transactions that are no longer present in orphanage; these are lazily removed in
132 : : * GetTxToReconsider. */
133 : : std::set<Wtxid> m_work_set;
134 : :
135 : : /** Total weight of orphans for which this peer is an announcer.
136 : : * If orphans are provided by different peers, its weight will be accounted for in each
137 : : * PeerOrphanInfo, so the total of all peers' m_total_usage may be larger than
138 : : * m_total_orphan_size. If a peer is removed as an announcer, even if the orphan still
139 : : * remains in the orphanage, this number will be decremented. */
140 : : unsigned int m_total_usage{0};
141 : : };
142 : : std::map<NodeId, PeerOrphanInfo> m_peer_orphanage_info;
143 : :
144 : : using OrphanMap = decltype(m_orphans);
145 : :
146 : : struct IteratorComparator
147 : : {
148 : : template<typename I>
149 [ + - - + : 29821688 : bool operator()(const I& a, const I& b) const
+ + + + +
+ + + +
+ ]
150 : : {
151 [ + - - + : 29821688 : return a->first < b->first;
+ + + + +
+ + + +
+ ]
152 : : }
153 : : };
154 : :
155 : : /** Index from the parents' COutPoint into the m_orphans. Used
156 : : * to remove orphan transactions from the m_orphans */
157 : : std::map<COutPoint, std::set<OrphanMap::iterator, IteratorComparator>> m_outpoint_to_orphan_it;
158 : :
159 : : /** Orphan transactions in vector for quick random eviction */
160 : : std::vector<OrphanMap::iterator> m_orphan_list;
161 : :
162 : : /** Timestamp for the next scheduled sweep of expired orphans */
163 : : NodeSeconds m_next_sweep{0s};
164 : : };
165 : :
166 : : #endif // BITCOIN_TXORPHANAGE_H
|
