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 2 : namespace {
18 2 :
19 : constexpr int MAX_TXHASHES = 16;
20 : constexpr int MAX_PEERS = 16;
21 :
22 : //! Randomly generated GenTxids used in this test (length is MAX_TXHASHES).
23 : uint256 TXHASHES[MAX_TXHASHES];
24 :
25 2 : //! Precomputed random durations (positive and negative, each ~exponentially distributed).
26 : std::chrono::microseconds DELAYS[256];
27 :
28 : struct Initializer
29 : {
30 2 : Initializer()
31 : {
32 34 : for (uint8_t txhash = 0; txhash < MAX_TXHASHES; txhash += 1) {
33 32 : CSHA256().Write(&txhash, 1).Finalize(TXHASHES[txhash].begin());
34 32 : }
35 2 : int i = 0;
36 : // DELAYS[N] for N=0..15 is just N microseconds.
37 34 : for (; i < 16; ++i) {
38 32 : DELAYS[i] = std::chrono::microseconds{i};
39 32 : }
40 : // DELAYS[N] for N=16..127 has randomly-looking but roughly exponentially increasing values up to
41 : // 198.416453 seconds.
42 226 : for (; i < 128; ++i) {
43 224 : int diff_bits = ((i - 10) * 2) / 9;
44 224 : uint64_t diff = 1 + (CSipHasher(0, 0).Write(i).Finalize() >> (64 - diff_bits));
45 224 : DELAYS[i] = DELAYS[i - 1] + std::chrono::microseconds{diff};
46 224 : }
47 : // DELAYS[N] for N=128..255 are negative delays with the same magnitude as N=0..127.
48 258 : for (; i < 256; ++i) {
49 256 : DELAYS[i] = -DELAYS[255 - i];
50 256 : }
51 2 : }
52 2 : } 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 : 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 2 : 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 2 : //! Sequence numbers, incremented whenever a new CANDIDATE is added.
84 0 : 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 0 : struct Announcement
92 : {
93 : std::chrono::microseconds m_time;
94 : uint64_t m_sequence;
95 0 : 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 0 : std::chrono::microseconds m_now{244466666};
106 :
107 : //! Delete txhashes whose only announcements are COMPLETED.
108 0 : void Cleanup(int txhash)
109 : {
110 0 : bool all_nothing = true;
111 0 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
112 0 : const Announcement& ann = m_announcements[txhash][peer];
113 0 : if (ann.m_state != State::NOTHING) {
114 0 : if (ann.m_state != State::COMPLETED) return;
115 0 : all_nothing = false;
116 0 : }
117 0 : }
118 0 : if (all_nothing) return;
119 0 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
120 0 : m_announcements[txhash][peer].m_state = State::NOTHING;
121 0 : }
122 0 : }
123 :
124 : //! Find the current best peer to request from for a txhash (or -1 if none).
125 0 : int GetSelected(int txhash) const
126 : {
127 0 : int ret = -1;
128 0 : uint64_t ret_priority = 0;
129 0 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
130 0 : const Announcement& ann = m_announcements[txhash][peer];
131 : // Return -1 if there already is a (non-expired) in-flight request.
132 0 : 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 0 : if (ann.m_state == State::CANDIDATE && ann.m_time <= m_now) {
135 0 : if (ret == -1 || ann.m_priority > ret_priority) {
136 0 : std::tie(ret, ret_priority) = std::tie(peer, ann.m_priority);
137 0 : }
138 0 : }
139 0 : }
140 0 : return ret;
141 0 : }
142 :
143 : public:
144 0 : Tester() : m_tracker(true) {}
145 :
146 0 : std::chrono::microseconds Now() const { return m_now; }
147 :
148 0 : void AdvanceTime(std::chrono::microseconds offset)
149 : {
150 0 : m_now += offset;
151 0 : while (!m_events.empty() && m_events.top() <= m_now) m_events.pop();
152 0 : }
153 :
154 0 : void AdvanceToEvent()
155 : {
156 0 : while (!m_events.empty() && m_events.top() <= m_now) m_events.pop();
157 0 : if (!m_events.empty()) {
158 0 : m_now = m_events.top();
159 0 : m_events.pop();
160 0 : }
161 0 : }
162 :
163 0 : void DisconnectedPeer(int peer)
164 : {
165 : // Apply to naive structure: all announcements for that peer are wiped.
166 0 : for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
167 0 : if (m_announcements[txhash][peer].m_state != State::NOTHING) {
168 0 : m_announcements[txhash][peer].m_state = State::NOTHING;
169 0 : Cleanup(txhash);
170 0 : }
171 0 : }
172 :
173 : // Call TxRequestTracker's implementation.
174 0 : m_tracker.DisconnectedPeer(peer);
175 0 : }
176 :
177 0 : void ForgetTxHash(int txhash)
178 : {
179 : // Apply to naive structure: all announcements for that txhash are wiped.
180 0 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
181 0 : m_announcements[txhash][peer].m_state = State::NOTHING;
182 0 : }
183 0 : Cleanup(txhash);
184 :
185 : // Call TxRequestTracker's implementation.
186 0 : m_tracker.ForgetTxHash(TXHASHES[txhash]);
187 0 : }
188 :
189 0 : 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 0 : Announcement& ann = m_announcements[txhash][peer];
194 0 : if (ann.m_state == State::NOTHING) {
195 0 : ann.m_preferred = preferred;
196 0 : ann.m_state = State::CANDIDATE;
197 0 : ann.m_time = reqtime;
198 0 : ann.m_is_wtxid = is_wtxid;
199 0 : ann.m_sequence = m_current_sequence++;
200 0 : 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 0 : if (reqtime > m_now) m_events.push(reqtime);
204 0 : }
205 :
206 : // Call TxRequestTracker's implementation.
207 0 : m_tracker.ReceivedInv(peer, is_wtxid ? GenTxid::Wtxid(TXHASHES[txhash]) : GenTxid::Txid(TXHASHES[txhash]), preferred, reqtime);
208 0 : }
209 :
210 0 : void RequestedTx(int peer, int txhash, std::chrono::microseconds exptime)
211 : {
212 : // Apply to naive structure: if a CANDIDATE announcement exists for peer/txhash,
213 : // convert it to REQUESTED, and change any existing REQUESTED announcement for the same txhash to COMPLETED.
214 0 : if (m_announcements[txhash][peer].m_state == State::CANDIDATE) {
215 0 : for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) {
216 0 : if (m_announcements[txhash][peer2].m_state == State::REQUESTED) {
217 0 : m_announcements[txhash][peer2].m_state = State::COMPLETED;
218 0 : }
219 0 : }
220 0 : m_announcements[txhash][peer].m_state = State::REQUESTED;
221 0 : m_announcements[txhash][peer].m_time = exptime;
222 0 : }
223 :
224 : // Add event so that AdvanceToEvent can quickly jump to the point where its exptime passes.
225 0 : if (exptime > m_now) m_events.push(exptime);
226 :
227 : // Call TxRequestTracker's implementation.
228 0 : m_tracker.RequestedTx(peer, TXHASHES[txhash], exptime);
229 0 : }
230 :
231 0 : void ReceivedResponse(int peer, int txhash)
232 : {
233 : // Apply to naive structure: convert anything to COMPLETED.
234 0 : if (m_announcements[txhash][peer].m_state != State::NOTHING) {
235 0 : m_announcements[txhash][peer].m_state = State::COMPLETED;
236 0 : Cleanup(txhash);
237 0 : }
238 :
239 : // Call TxRequestTracker's implementation.
240 0 : m_tracker.ReceivedResponse(peer, TXHASHES[txhash]);
241 0 : }
242 :
243 0 : void GetRequestable(int peer)
244 : {
245 : // Implement using naive structure:
246 :
247 : //! list of (sequence number, txhash, is_wtxid) tuples.
248 0 : std::vector<std::tuple<uint64_t, int, bool>> result;
249 0 : std::vector<std::pair<NodeId, GenTxid>> expected_expired;
250 0 : for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
251 : // Mark any expired REQUESTED announcements as COMPLETED.
252 0 : for (int peer2 = 0; peer2 < MAX_PEERS; ++peer2) {
253 0 : Announcement& ann2 = m_announcements[txhash][peer2];
254 0 : if (ann2.m_state == State::REQUESTED && ann2.m_time <= m_now) {
255 0 : expected_expired.emplace_back(peer2, ann2.m_is_wtxid ? GenTxid::Wtxid(TXHASHES[txhash]) : GenTxid::Txid(TXHASHES[txhash]));
256 0 : ann2.m_state = State::COMPLETED;
257 0 : break;
258 : }
259 0 : }
260 : // And delete txids with only COMPLETED announcements left.
261 0 : Cleanup(txhash);
262 : // CANDIDATEs for which this announcement has the highest priority get returned.
263 0 : const Announcement& ann = m_announcements[txhash][peer];
264 0 : if (ann.m_state == State::CANDIDATE && GetSelected(txhash) == peer) {
265 0 : result.emplace_back(ann.m_sequence, txhash, ann.m_is_wtxid);
266 0 : }
267 0 : }
268 : // Sort the results by sequence number.
269 0 : std::sort(result.begin(), result.end());
270 0 : std::sort(expected_expired.begin(), expected_expired.end());
271 :
272 : // Compare with TxRequestTracker's implementation.
273 0 : std::vector<std::pair<NodeId, GenTxid>> expired;
274 0 : const auto actual = m_tracker.GetRequestable(peer, m_now, &expired);
275 0 : std::sort(expired.begin(), expired.end());
276 0 : assert(expired == expected_expired);
277 :
278 0 : m_tracker.PostGetRequestableSanityCheck(m_now);
279 0 : assert(result.size() == actual.size());
280 0 : for (size_t pos = 0; pos < actual.size(); ++pos) {
281 0 : assert(TXHASHES[std::get<1>(result[pos])] == actual[pos].GetHash());
282 0 : assert(std::get<2>(result[pos]) == actual[pos].IsWtxid());
283 0 : }
284 0 : }
285 :
286 0 : void Check()
287 : {
288 : // Compare CountTracked and CountLoad with naive structure.
289 0 : size_t total = 0;
290 0 : for (int peer = 0; peer < MAX_PEERS; ++peer) {
291 0 : size_t tracked = 0;
292 0 : size_t inflight = 0;
293 0 : size_t candidates = 0;
294 0 : for (int txhash = 0; txhash < MAX_TXHASHES; ++txhash) {
295 0 : tracked += m_announcements[txhash][peer].m_state != State::NOTHING;
296 0 : inflight += m_announcements[txhash][peer].m_state == State::REQUESTED;
297 0 : candidates += m_announcements[txhash][peer].m_state == State::CANDIDATE;
298 0 : }
299 0 : assert(m_tracker.Count(peer) == tracked);
300 0 : assert(m_tracker.CountInFlight(peer) == inflight);
301 0 : assert(m_tracker.CountCandidates(peer) == candidates);
302 0 : total += tracked;
303 0 : }
304 : // Compare Size.
305 0 : assert(m_tracker.Size() == total);
306 :
307 : // Invoke internal consistency check of TxRequestTracker object.
308 0 : m_tracker.SanityCheck();
309 0 : }
310 : };
311 : } // namespace
312 :
313 4 : FUZZ_TARGET(txrequest)
314 : {
315 : // Tester object (which encapsulates a TxRequestTracker).
316 0 : Tester tester;
317 :
318 : // Decode the input as a sequence of instructions with parameters
319 0 : auto it = buffer.begin();
320 0 : while (it != buffer.end()) {
321 0 : int cmd = *(it++) % 11;
322 : int peer, txidnum, delaynum;
323 0 : switch (cmd) {
324 : case 0: // Make time jump to the next event (m_time of CANDIDATE or REQUESTED)
325 0 : tester.AdvanceToEvent();
326 0 : break;
327 : case 1: // Change time
328 0 : delaynum = it == buffer.end() ? 0 : *(it++);
329 0 : tester.AdvanceTime(DELAYS[delaynum]);
330 0 : break;
331 : case 2: // Query for requestable txs
332 0 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
333 0 : tester.GetRequestable(peer);
334 0 : break;
335 : case 3: // Peer went offline
336 0 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
337 0 : tester.DisconnectedPeer(peer);
338 0 : break;
339 : case 4: // No longer need tx
340 0 : txidnum = it == buffer.end() ? 0 : *(it++);
341 0 : tester.ForgetTxHash(txidnum % MAX_TXHASHES);
342 0 : break;
343 : case 5: // Received immediate preferred inv
344 : case 6: // Same, but non-preferred.
345 0 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
346 0 : txidnum = it == buffer.end() ? 0 : *(it++);
347 0 : tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, (txidnum / MAX_TXHASHES) & 1, cmd & 1,
348 0 : std::chrono::microseconds::min());
349 0 : break;
350 : case 7: // Received delayed preferred inv
351 : case 8: // Same, but non-preferred.
352 0 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
353 0 : txidnum = it == buffer.end() ? 0 : *(it++);
354 0 : delaynum = it == buffer.end() ? 0 : *(it++);
355 0 : tester.ReceivedInv(peer, txidnum % MAX_TXHASHES, (txidnum / MAX_TXHASHES) & 1, cmd & 1,
356 0 : tester.Now() + DELAYS[delaynum]);
357 0 : break;
358 : case 9: // Requested tx from peer
359 0 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
360 0 : txidnum = it == buffer.end() ? 0 : *(it++);
361 0 : delaynum = it == buffer.end() ? 0 : *(it++);
362 0 : tester.RequestedTx(peer, txidnum % MAX_TXHASHES, tester.Now() + DELAYS[delaynum]);
363 0 : break;
364 : case 10: // Received response
365 0 : peer = it == buffer.end() ? 0 : *(it++) % MAX_PEERS;
366 0 : txidnum = it == buffer.end() ? 0 : *(it++);
367 0 : tester.ReceivedResponse(peer, txidnum % MAX_TXHASHES);
368 0 : break;
369 : default:
370 0 : assert(false);
371 : }
372 : }
373 0 : tester.Check();
374 0 : }
|
