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