Branch data Line data Source code
1 : : // Copyright (c) 2020-present 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 <txrequest.h>
6 : :
7 : : #include <crypto/common.h>
8 : : #include <crypto/sha256.h>
9 : : #include <crypto/siphash.h>
10 : : #include <primitives/transaction.h>
11 : : #include <test/fuzz/fuzz.h>
12 : : #include <util/check.h>
13 : :
14 : : #include <bitset>
15 : : #include <cstdint>
16 : : #include <queue>
17 : : #include <vector>
18 : :
19 : : namespace {
20 : :
21 : : constexpr int MAX_TXHASHES = 16;
22 : : constexpr int MAX_PEERS = 16;
23 : :
24 : : //! Randomly generated txhashes used in this test (length is MAX_TXHASHES).
25 : : uint256 TXHASHES[MAX_TXHASHES];
26 : :
27 : : //! Precomputed random durations (positive and negative, each ~exponentially distributed).
28 : : std::chrono::microseconds DELAYS[256];
29 : :
30 : : struct Initializer
31 : : {
32 : 238 : Initializer()
33 : : {
34 [ + + ]: 4046 : for (uint8_t txhash = 0; txhash < MAX_TXHASHES; txhash += 1) {
35 : 3808 : CSHA256().Write(&txhash, 1).Finalize(TXHASHES[txhash].begin());
36 : : }
37 : : int i = 0;
38 : : // DELAYS[N] for N=0..15 is just N microseconds.
39 [ + + ]: 4046 : for (; i < 16; ++i) {
40 : 3808 : DELAYS[i] = std::chrono::microseconds{i};
41 : : }
42 : : // DELAYS[N] for N=16..127 has randomly-looking but roughly exponentially increasing values up to
43 : : // 198.416453 seconds.
44 [ + + ]: 26894 : for (; i < 128; ++i) {
45 : 26656 : int diff_bits = ((i - 10) * 2) / 9;
46 : 26656 : uint64_t diff = 1 + (CSipHasher(0, 0).Write(i).Finalize() >> (64 - diff_bits));
47 : 26656 : DELAYS[i] = DELAYS[i - 1] + std::chrono::microseconds{diff};
48 : : }
49 : : // DELAYS[N] for N=128..255 are negative delays with the same magnitude as N=0..127.
50 [ + + ]: 30702 : for (; i < 256; ++i) {
51 : 30464 : DELAYS[i] = -DELAYS[255 - i];
52 : : }
53 : 238 : }
54 : : } g_initializer;
55 : :
56 : : /** Tester class for TxRequestTracker
57 : : *
58 : : * It includes a naive reimplementation of its behavior, for a limited set
59 : : * of MAX_TXHASHES distinct txids, and MAX_PEERS peer identifiers.
60 : : *
61 : : * All of the public member functions perform the same operation on
62 : : * an actual TxRequestTracker and on the state of the reimplementation.
63 : : * The output of GetRequestable is compared with the expected value
64 : : * as well.
65 : : *
66 : : * Check() calls the TxRequestTracker's sanity check, plus compares the
67 : : * output of the constant accessors (Size(), CountLoad(), CountTracked())
68 : : * with expected values.
69 : : */
70 : 358 : class Tester
71 : : {
72 : : //! TxRequestTracker object being tested.
73 : : TxRequestTracker m_tracker;
74 : :
75 : : //! States for txid/peer combinations in the naive data structure.
76 : : enum class State {
77 : : NOTHING, //!< Absence of this txid/peer combination
78 : :
79 : : // Note that this implementation does not distinguish between DELAYED/READY/BEST variants of CANDIDATE.
80 : : CANDIDATE,
81 : : REQUESTED,
82 : : COMPLETED,
83 : : };
84 : :
85 : : //! Sequence numbers, incremented whenever a new CANDIDATE is added.
86 : : uint64_t m_current_sequence{0};
87 : :
88 : : //! List of future 'events' (all inserted reqtimes/exptimes). This is used to implement AdvanceToEvent.
89 : : std::priority_queue<std::chrono::microseconds, std::vector<std::chrono::microseconds>,
90 : : std::greater<std::chrono::microseconds>> m_events;
91 : :
92 : : //! Information about a txhash/peer combination.
93 : 91648 : struct Announcement
94 : : {
95 : : std::chrono::microseconds m_time;
96 : : uint64_t m_sequence;
97 : : State m_state{State::NOTHING};
98 : : bool m_preferred;
99 : : bool m_is_wtxid;
100 : : uint64_t m_priority; //!< Precomputed priority.
101 : : };
102 : :
103 : : //! Information about all txhash/peer combination.
104 : : Announcement m_announcements[MAX_TXHASHES][MAX_PEERS];
105 : :
106 : : //! The current time; can move forward and backward.
107 : : std::chrono::microseconds m_now{244466666};
108 : :
109 : : //! Delete txhashes whose only announcements are COMPLETED.
110 : 3503207 : void Cleanup(int txhash)
111 : : {
112 : 3503207 : bool all_nothing = true;
113 [ + + ]: 35754551 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
114 : 34430635 : const Announcement& ann = m_announcements[txhash][peer];
115 [ + + ]: 34430635 : if (ann.m_state != State::NOTHING) {
116 [ + + ]: 2403786 : if (ann.m_state != State::COMPLETED) return;
117 : : all_nothing = false;
118 : : }
119 : : }
120 [ + + ]: 1323916 : if (all_nothing) return;
121 [ + + ]: 554625 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
122 : 522000 : m_announcements[txhash][peer].m_state = State::NOTHING;
123 : : }
124 : : }
125 : :
126 : : //! Find the current best peer to request from for a txhash (or -1 if none).
127 : 290564 : int GetSelected(int txhash) const
128 : : {
129 : 290564 : int ret = -1;
130 : 290564 : uint64_t ret_priority = 0;
131 [ + + ]: 4881642 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
132 : 4598623 : const Announcement& ann = m_announcements[txhash][peer];
133 : : // Return -1 if there already is a (non-expired) in-flight request.
134 [ + + ]: 4598623 : if (ann.m_state == State::REQUESTED) return -1;
135 : : // If it's a viable candidate, see if it has lower priority than the best one so far.
136 [ + + + + ]: 4591078 : if (ann.m_state == State::CANDIDATE && ann.m_time <= m_now) {
137 [ + + + + ]: 718680 : if (ret == -1 || ann.m_priority > ret_priority) {
138 : 423641 : std::tie(ret, ret_priority) = std::tie(peer, ann.m_priority);
139 : : }
140 : : }
141 : : }
142 : 283019 : return ret;
143 : : }
144 : :
145 : : public:
146 [ + + + + ]: 97734 : Tester() : m_tracker(true) {}
147 : :
148 : 813682 : std::chrono::microseconds Now() const { return m_now; }
149 : :
150 : 440142 : void AdvanceTime(std::chrono::microseconds offset)
151 : : {
152 : 440142 : m_now += offset;
153 [ + + + + ]: 541012 : while (!m_events.empty() && m_events.top() <= m_now) m_events.pop();
154 : 440142 : }
155 : :
156 : 816893 : void AdvanceToEvent()
157 : : {
158 [ + + + + ]: 944470 : while (!m_events.empty() && m_events.top() <= m_now) m_events.pop();
159 [ + + ]: 816893 : if (!m_events.empty()) {
160 : 173966 : m_now = m_events.top();
161 : 173966 : m_events.pop();
162 : : }
163 : 816893 : }
164 : :
165 : 162477 : void DisconnectedPeer(int peer)
166 : : {
167 : : // Apply to naive structure: all announcements for that peer are wiped.
168 [ + + ]: 2762109 : for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
169 [ + + ]: 2599632 : if (m_announcements[txhash][peer].m_state != State::NOTHING) {
170 : 222053 : m_announcements[txhash][peer].m_state = State::NOTHING;
171 : 222053 : Cleanup(txhash);
172 : : }
173 : : }
174 : :
175 : : // Call TxRequestTracker's implementation.
176 : 162477 : m_tracker.DisconnectedPeer(peer);
177 : 162477 : }
178 : :
179 : 203931 : void ForgetTxHash(int txhash)
180 : : {
181 : : // Apply to naive structure: all announcements for that txhash are wiped.
182 [ + + ]: 3466827 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
183 : 3262896 : m_announcements[txhash][peer].m_state = State::NOTHING;
184 : : }
185 : 203931 : Cleanup(txhash);
186 : :
187 : : // Call TxRequestTracker's implementation.
188 : 203931 : m_tracker.ForgetTxHash(TXHASHES[txhash]);
189 : 203931 : }
190 : :
191 : 772485 : void ReceivedInv(int peer, int txhash, bool is_wtxid, bool preferred, std::chrono::microseconds reqtime)
192 : : {
193 : : // Apply to naive structure: if no announcement for txidnum/peer combination
194 : : // already, create a new CANDIDATE; otherwise do nothing.
195 : 772485 : Announcement& ann = m_announcements[txhash][peer];
196 [ + + ]: 772485 : if (ann.m_state == State::NOTHING) {
197 : 514597 : ann.m_preferred = preferred;
198 : 514597 : ann.m_state = State::CANDIDATE;
199 : 514597 : ann.m_time = reqtime;
200 : 514597 : ann.m_is_wtxid = is_wtxid;
201 : 514597 : ann.m_sequence = m_current_sequence++;
202 : 514597 : ann.m_priority = m_tracker.ComputePriority(TXHASHES[txhash], peer, ann.m_preferred);
203 : :
204 : : // Add event so that AdvanceToEvent can quickly jump to the point where its reqtime passes.
205 [ + + ]: 514597 : if (reqtime > m_now) m_events.push(reqtime);
206 : : }
207 : :
208 : : // Call TxRequestTracker's implementation.
209 [ + + ]: 772485 : auto gtxid = is_wtxid ? GenTxid{Wtxid::FromUint256(TXHASHES[txhash])} : GenTxid{Txid::FromUint256(TXHASHES[txhash])};
210 : 772485 : m_tracker.ReceivedInv(peer, gtxid, preferred, reqtime);
211 : 772485 : }
212 : :
213 : 443215 : void RequestedTx(int peer, int txhash, std::chrono::microseconds exptime)
214 : : {
215 : : // Apply to naive structure: if a CANDIDATE announcement exists for peer/txhash,
216 : : // convert it to REQUESTED, and change any existing REQUESTED announcement for the same txhash to COMPLETED.
217 [ + + ]: 443215 : if (m_announcements[txhash][peer].m_state == State::CANDIDATE) {
218 [ + + ]: 1135056 : for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) {
219 [ + + ]: 1068288 : if (m_announcements[txhash][peer2].m_state == State::REQUESTED) {
220 : 11016 : m_announcements[txhash][peer2].m_state = State::COMPLETED;
221 : : }
222 : : }
223 : 66768 : m_announcements[txhash][peer].m_state = State::REQUESTED;
224 : 66768 : m_announcements[txhash][peer].m_time = exptime;
225 : : }
226 : :
227 : : // Add event so that AdvanceToEvent can quickly jump to the point where its exptime passes.
228 [ + + ]: 443215 : if (exptime > m_now) m_events.push(exptime);
229 : :
230 : : // Call TxRequestTracker's implementation.
231 : 443215 : m_tracker.RequestedTx(peer, TXHASHES[txhash], exptime);
232 : 443215 : }
233 : :
234 : 128387 : void ReceivedResponse(int peer, int txhash)
235 : : {
236 : : // Apply to naive structure: convert anything to COMPLETED.
237 [ + + ]: 128387 : if (m_announcements[txhash][peer].m_state != State::NOTHING) {
238 : 25767 : m_announcements[txhash][peer].m_state = State::COMPLETED;
239 : 25767 : Cleanup(txhash);
240 : : }
241 : :
242 : : // Call TxRequestTracker's implementation.
243 : 128387 : m_tracker.ReceivedResponse(peer, TXHASHES[txhash]);
244 : 128387 : }
245 : :
246 : 190716 : void GetRequestable(int peer)
247 : : {
248 : : // Implement using naive structure:
249 : :
250 : : //! list of (sequence number, txhash, is_wtxid) tuples.
251 : 190716 : std::vector<std::tuple<uint64_t, int, bool>> result;
252 : 190716 : std::vector<std::pair<NodeId, GenTxid>> expected_expired;
253 [ + + ]: 3242172 : for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
254 : : // Mark any expired REQUESTED announcements as COMPLETED.
255 [ + + ]: 51418712 : for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) {
256 : 48415314 : Announcement& ann2 = m_announcements[txhash][peer2];
257 [ + + + + ]: 48415314 : if (ann2.m_state == State::REQUESTED && ann2.m_time <= m_now) {
258 [ + + ]: 48058 : auto gtxid = ann2.m_is_wtxid ? GenTxid{Wtxid::FromUint256(TXHASHES[txhash])} : GenTxid{Txid::FromUint256(TXHASHES[txhash])};
259 [ + - ]: 48058 : expected_expired.emplace_back(peer2, gtxid);
260 : 48058 : ann2.m_state = State::COMPLETED;
261 : 48058 : break;
262 : : }
263 : : }
264 : : // And delete txids with only COMPLETED announcements left.
265 : 3051456 : Cleanup(txhash);
266 : : // CANDIDATEs for which this announcement has the highest priority get returned.
267 : 3051456 : const Announcement& ann = m_announcements[txhash][peer];
268 [ + + + + ]: 3051456 : if (ann.m_state == State::CANDIDATE && GetSelected(txhash) == peer) {
269 [ + - ]: 125242 : result.emplace_back(ann.m_sequence, txhash, ann.m_is_wtxid);
270 : : }
271 : : }
272 : : // Sort the results by sequence number.
273 : 190716 : std::sort(result.begin(), result.end());
274 : 190716 : std::sort(expected_expired.begin(), expected_expired.end());
275 : :
276 : : // Compare with TxRequestTracker's implementation.
277 : 190716 : std::vector<std::pair<NodeId, GenTxid>> expired;
278 [ + - ]: 190716 : const auto actual = m_tracker.GetRequestable(peer, m_now, &expired);
279 : 190716 : std::sort(expired.begin(), expired.end());
280 [ - + ]: 190716 : assert(expired == expected_expired);
281 : :
282 [ + - ]: 190716 : m_tracker.PostGetRequestableSanityCheck(m_now);
283 [ - + - + : 190716 : assert(result.size() == actual.size());
- + ]
284 [ + + ]: 315958 : for (size_t pos = 0; pos < actual.size(); ++pos) {
285 [ + + - - : 250484 : assert(TXHASHES[std::get<1>(result[pos])] == actual[pos].ToUint256());
+ ]
286 [ - + ]: 125242 : assert(std::get<2>(result[pos]) == actual[pos].IsWtxid());
287 : : }
288 : 190716 : }
289 : :
290 : 358 : void Check()
291 : : {
292 : : // Compare CountTracked and CountLoad with naive structure.
293 : 358 : size_t total = 0;
294 [ + + ]: 6086 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
295 : : size_t tracked = 0;
296 : : size_t inflight = 0;
297 : : size_t candidates = 0;
298 [ + + ]: 97376 : for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
299 : 91648 : tracked += m_announcements[txhash][peer].m_state != State::NOTHING;
300 : 91648 : inflight += m_announcements[txhash][peer].m_state == State::REQUESTED;
301 : 91648 : candidates += m_announcements[txhash][peer].m_state == State::CANDIDATE;
302 : :
303 : 91648 : std::bitset<MAX_PEERS> expected_announcers;
304 [ + + ]: 1558016 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
305 [ + + ]: 1466368 : if (m_announcements[txhash][peer].m_state == State::CANDIDATE || m_announcements[txhash][peer].m_state == State::REQUESTED) {
306 : 145344 : expected_announcers[peer] = true;
307 : : }
308 : : }
309 : 91648 : std::vector<NodeId> candidate_peers;
310 [ + - ]: 91648 : m_tracker.GetCandidatePeers(TXHASHES[txhash], candidate_peers);
311 [ - + - + ]: 91648 : assert(expected_announcers.count() == candidate_peers.size());
312 [ + + ]: 236992 : for (const auto& peer : candidate_peers) {
313 [ - + ]: 145344 : assert(expected_announcers[peer]);
314 : : }
315 : 91648 : }
316 [ - + ]: 5728 : assert(m_tracker.Count(peer) == tracked);
317 [ - + ]: 5728 : assert(m_tracker.CountInFlight(peer) == inflight);
318 [ - + ]: 5728 : assert(m_tracker.CountCandidates(peer) == candidates);
319 : 5728 : total += tracked;
320 : : }
321 : : // Compare Size.
322 [ - + ]: 358 : assert(m_tracker.Size() == total);
323 : :
324 : : // Invoke internal consistency check of TxRequestTracker object.
325 : 358 : m_tracker.SanityCheck();
326 : 358 : }
327 : : };
328 : : } // namespace
329 : :
330 [ + - ]: 834 : FUZZ_TARGET(txrequest)
331 : : {
332 : : // Tester object (which encapsulates a TxRequestTracker).
333 : 358 : Tester tester;
334 : :
335 : : // Decode the input as a sequence of instructions with parameters
336 : 358 : auto it = buffer.begin();
337 [ + + ]: 3158604 : while (it != buffer.end()) {
338 [ + + + + : 3158246 : int cmd = *(it++) % 11;
+ + + + +
- ]
339 : 3158246 : int peer, txidnum, delaynum;
340 [ + + + + : 3158246 : switch (cmd) {
+ + + + +
- ]
341 : 816893 : case 0: // Make time jump to the next event (m_time of CANDIDATE or REQUESTED)
342 : 816893 : tester.AdvanceToEvent();
343 : : break;
344 : 440142 : case 1: // Change time
345 [ + + ]: 440142 : delaynum = it == buffer.end() ? 0 : *(it++);
346 : 440142 : tester.AdvanceTime(DELAYS[delaynum]);
347 : : break;
348 : 190716 : case 2: // Query for requestable txs
349 [ + + ]: 190716 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
350 [ + - ]: 190716 : tester.GetRequestable(peer);
351 : : break;
352 : 162477 : case 3: // Peer went offline
353 [ + + ]: 162477 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
354 [ + - ]: 162477 : tester.DisconnectedPeer(peer);
355 : : break;
356 : 203931 : case 4: // No longer need tx
357 [ + + ]: 203931 : txidnum = it == buffer.end() ? 0 : *(it++);
358 [ + - ]: 203931 : tester.ForgetTxHash(txidnum % MAX_TXHASHES);
359 : : break;
360 : 402018 : case 5: // Received immediate preferred inv
361 : 402018 : case 6: // Same, but non-preferred.
362 [ + + ]: 402018 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
363 [ + + ]: 402018 : txidnum = it == buffer.end() ? 0 : *(it++);
364 [ + - ]: 402018 : tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, (txidnum / MAX_TXHASHES) & 1, cmd & 1,
365 : : std::chrono::microseconds::min());
366 : : break;
367 : 370467 : case 7: // Received delayed preferred inv
368 : 370467 : case 8: // Same, but non-preferred.
369 [ + + ]: 370467 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
370 [ + + ]: 370467 : txidnum = it == buffer.end() ? 0 : *(it++);
371 [ + + ]: 370467 : delaynum = it == buffer.end() ? 0 : *(it++);
372 : 370467 : tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, (txidnum / MAX_TXHASHES) & 1, cmd & 1,
373 [ + - ]: 370467 : tester.Now() + DELAYS[delaynum]);
374 : : break;
375 : 443215 : case 9: // Requested tx from peer
376 [ + + ]: 443215 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
377 [ + + ]: 443215 : txidnum = it == buffer.end() ? 0 : *(it++);
378 [ + + ]: 443215 : delaynum = it == buffer.end() ? 0 : *(it++);
379 [ + - ]: 443215 : tester.RequestedTx(peer, txidnum % MAX_TXHASHES, tester.Now() + DELAYS[delaynum]);
380 : : break;
381 : 128387 : case 10: // Received response
382 [ + + ]: 128387 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
383 [ + + ]: 128387 : txidnum = it == buffer.end() ? 0 : *(it++);
384 [ + - ]: 128387 : tester.ReceivedResponse(peer, txidnum % MAX_TXHASHES);
385 : : break;
386 : 0 : default:
387 : 0 : AssertUnreachable();
388 : : }
389 : : }
390 [ + - ]: 358 : tester.Check();
391 : 358 : }
|