txrequest_tests.cpp raw
1 // Copyright (c) 2020-2021 The Limenka 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
6 #include <txrequest.h>
7 #include <uint256.h>
8
9 #include <test/util/random.h>
10 #include <test/util/setup_common.h>
11
12 #include <algorithm>
13 #include <functional>
14 #include <vector>
15
16 #include <boost/test/unit_test.hpp>
17
18 namespace {
19
20 class Scenario;
21
22 struct TxRequestTest : BasicTestingSetup {
23 std::chrono::microseconds RandomTime8s();
24 std::chrono::microseconds RandomTime1y();
25 void BuildSingleTest(Scenario& scenario, int config);
26 void BuildPriorityTest(Scenario& scenario, int config);
27 void BuildBigPriorityTest(Scenario& scenario, int peers);
28 void BuildRequestOrderTest(Scenario& scenario, int config);
29 void BuildWtxidTest(Scenario& scenario, int config);
30 void BuildTimeBackwardsTest(Scenario& scenario);
31 void BuildWeirdRequestsTest(Scenario& scenario);
32 void TestInterleavedScenarios();
33 };
34
35 constexpr std::chrono::microseconds MIN_TIME = std::chrono::microseconds::min();
36 constexpr std::chrono::microseconds MAX_TIME = std::chrono::microseconds::max();
37 constexpr std::chrono::microseconds MICROSECOND = std::chrono::microseconds{1};
38 constexpr std::chrono::microseconds NO_TIME = std::chrono::microseconds{0};
39
40 /** An Action is a function to call at a particular (simulated) timestamp. */
41 using Action = std::pair<std::chrono::microseconds, std::function<void()>>;
42
43 /** Object that stores actions from multiple interleaved scenarios, and data shared across them.
44 *
45 * The Scenario below is used to fill this.
46 */
47 struct Runner
48 {
49 /** The TxRequestTracker being tested. */
50 TxRequestTracker txrequest;
51
52 /** List of actions to be executed (in order of increasing timestamp). */
53 std::vector<Action> actions;
54
55 /** Which node ids have been assigned already (to prevent reuse). */
56 std::set<NodeId> peerset;
57
58 /** Which txhashes have been assigned already (to prevent reuse). */
59 std::set<uint256> txhashset;
60
61 /** Which (peer, gtxid) combinations are known to be expired. These need to be accumulated here instead of
62 * checked directly in the GetRequestable return value to avoid introducing a dependency between the various
63 * parallel tests. */
64 std::multiset<std::pair<NodeId, GenTxid>> expired;
65 };
66
67 std::chrono::microseconds TxRequestTest::RandomTime8s() { return std::chrono::microseconds{1 + m_rng.randbits(23)}; }
68 std::chrono::microseconds TxRequestTest::RandomTime1y() { return std::chrono::microseconds{1 + m_rng.randbits(45)}; }
69
70 /** A proxy for a Runner that helps build a sequence of consecutive test actions on a TxRequestTracker.
71 *
72 * Each Scenario is a proxy through which actions for the (sequential) execution of various tests are added to a
73 * Runner. The actions from multiple scenarios are then run concurrently, resulting in these tests being performed
74 * against a TxRequestTracker in parallel. Every test has its own unique txhashes and NodeIds which are not
75 * reused in other tests, and thus they should be independent from each other. Running them in parallel however
76 * means that we verify the behavior (w.r.t. one test's txhashes and NodeIds) even when the state of the data
77 * structure is more complicated due to the presence of other tests.
78 */
79 class Scenario
80 {
81 FastRandomContext& m_rng;
82 Runner& m_runner;
83 std::chrono::microseconds m_now;
84 std::string m_testname;
85
86 public:
87 Scenario(FastRandomContext& rng, Runner& runner, std::chrono::microseconds starttime) : m_rng(rng), m_runner(runner), m_now(starttime) {}
88
89 /** Set a name for the current test, to give more clear error messages. */
90 void SetTestName(std::string testname)
91 {
92 m_testname = std::move(testname);
93 }
94
95 /** Advance this Scenario's time; this affects the timestamps newly scheduled events get. */
96 void AdvanceTime(std::chrono::microseconds amount)
97 {
98 assert(amount.count() >= 0);
99 m_now += amount;
100 }
101
102 /** Schedule a ForgetTxHash call at the Scheduler's current time. */
103 void ForgetTxHash(const uint256& txhash)
104 {
105 auto& runner = m_runner;
106 runner.actions.emplace_back(m_now, [=,&runner]() {
107 runner.txrequest.ForgetTxHash(txhash);
108 runner.txrequest.SanityCheck();
109 });
110 }
111
112 /** Schedule a ReceivedInv call at the Scheduler's current time. */
113 void ReceivedInv(NodeId peer, const GenTxid& gtxid, bool pref, std::chrono::microseconds reqtime)
114 {
115 auto& runner = m_runner;
116 runner.actions.emplace_back(m_now, [=,&runner]() {
117 runner.txrequest.ReceivedInv(peer, gtxid, pref, reqtime);
118 runner.txrequest.SanityCheck();
119 });
120 }
121
122 /** Schedule a DisconnectedPeer call at the Scheduler's current time. */
123 void DisconnectedPeer(NodeId peer)
124 {
125 auto& runner = m_runner;
126 runner.actions.emplace_back(m_now, [=,&runner]() {
127 runner.txrequest.DisconnectedPeer(peer);
128 runner.txrequest.SanityCheck();
129 });
130 }
131
132 /** Schedule a RequestedTx call at the Scheduler's current time. */
133 void RequestedTx(NodeId peer, const uint256& txhash, std::chrono::microseconds exptime)
134 {
135 auto& runner = m_runner;
136 runner.actions.emplace_back(m_now, [=,&runner]() {
137 runner.txrequest.RequestedTx(peer, txhash, exptime);
138 runner.txrequest.SanityCheck();
139 });
140 }
141
142 /** Schedule a ReceivedResponse call at the Scheduler's current time. */
143 void ReceivedResponse(NodeId peer, const uint256& txhash)
144 {
145 auto& runner = m_runner;
146 runner.actions.emplace_back(m_now, [=,&runner]() {
147 runner.txrequest.ReceivedResponse(peer, txhash);
148 runner.txrequest.SanityCheck();
149 });
150 }
151
152 /** Schedule calls to verify the TxRequestTracker's state at the Scheduler's current time.
153 *
154 * @param peer The peer whose state will be inspected.
155 * @param expected The expected return value for GetRequestable(peer)
156 * @param candidates The expected return value CountCandidates(peer)
157 * @param inflight The expected return value CountInFlight(peer)
158 * @param completed The expected return value of Count(peer), minus candidates and inflight.
159 * @param checkname An arbitrary string to include in error messages, for test identificatrion.
160 * @param offset Offset with the current time to use (must be <= 0). This allows simulations of time going
161 * backwards (but note that the ordering of this event only follows the scenario's m_now.
162 */
163 void Check(NodeId peer, const std::vector<GenTxid>& expected, size_t candidates, size_t inflight,
164 size_t completed, const std::string& checkname,
165 std::chrono::microseconds offset = std::chrono::microseconds{0})
166 {
167 const auto comment = m_testname + " " + checkname;
168 auto& runner = m_runner;
169 const auto now = m_now;
170 assert(offset.count() <= 0);
171 runner.actions.emplace_back(m_now, [=,&runner]() {
172 std::vector<std::pair<NodeId, GenTxid>> expired_now;
173 auto ret = runner.txrequest.GetRequestable(peer, now + offset, &expired_now);
174 for (const auto& entry : expired_now) runner.expired.insert(entry);
175 runner.txrequest.SanityCheck();
176 runner.txrequest.PostGetRequestableSanityCheck(now + offset);
177 size_t total = candidates + inflight + completed;
178 size_t real_total = runner.txrequest.Count(peer);
179 size_t real_candidates = runner.txrequest.CountCandidates(peer);
180 size_t real_inflight = runner.txrequest.CountInFlight(peer);
181 BOOST_CHECK_MESSAGE(real_total == total, strprintf("[%s] total %i (%i expected)", comment, real_total, total));
182 BOOST_CHECK_MESSAGE(real_inflight == inflight, strprintf("[%s] inflight %i (%i expected)", comment, real_inflight, inflight));
183 BOOST_CHECK_MESSAGE(real_candidates == candidates, strprintf("[%s] candidates %i (%i expected)", comment, real_candidates, candidates));
184 BOOST_CHECK_MESSAGE(ret == expected, strprintf("[%s] mismatching requestables", comment));
185 });
186 }
187
188 /** Verify that an announcement for gtxid by peer has expired some time before this check is scheduled.
189 *
190 * Every expected expiration should be accounted for through exactly one call to this function.
191 */
192 void CheckExpired(NodeId peer, GenTxid gtxid)
193 {
194 const auto& testname = m_testname;
195 auto& runner = m_runner;
196 runner.actions.emplace_back(m_now, [=,&runner]() {
197 auto it = runner.expired.find(std::pair<NodeId, GenTxid>{peer, gtxid});
198 BOOST_CHECK_MESSAGE(it != runner.expired.end(), "[" + testname + "] missing expiration");
199 if (it != runner.expired.end()) runner.expired.erase(it);
200 });
201 }
202
203 /** Generate a random txhash, whose priorities for certain peers are constrained.
204 *
205 * For example, NewTxHash({{p1,p2,p3},{p2,p4,p5}}) will generate a txhash T such that both:
206 * - priority(p1,T) > priority(p2,T) > priority(p3,T)
207 * - priority(p2,T) > priority(p4,T) > priority(p5,T)
208 * where priority is the predicted internal TxRequestTracker's priority, assuming all announcements
209 * are within the same preferredness class.
210 */
211 uint256 NewTxHash(const std::vector<std::vector<NodeId>>& orders = {})
212 {
213 uint256 ret;
214 bool ok;
215 do {
216 ret = m_rng.rand256();
217 ok = true;
218 for (const auto& order : orders) {
219 for (size_t pos = 1; pos < order.size(); ++pos) {
220 uint64_t prio_prev = m_runner.txrequest.ComputePriority(ret, order[pos - 1], true);
221 uint64_t prio_cur = m_runner.txrequest.ComputePriority(ret, order[pos], true);
222 if (prio_prev <= prio_cur) {
223 ok = false;
224 break;
225 }
226 }
227 if (!ok) break;
228 }
229 if (ok) {
230 ok = m_runner.txhashset.insert(ret).second;
231 }
232 } while(!ok);
233 return ret;
234 }
235
236 /** Generate a random GenTxid; the txhash follows NewTxHash; the is_wtxid flag is random. */
237 GenTxid NewGTxid(const std::vector<std::vector<NodeId>>& orders = {})
238 {
239 return m_rng.randbool() ? GenTxid::Wtxid(NewTxHash(orders)) : GenTxid::Txid(NewTxHash(orders));
240 }
241
242 /** Generate a new random NodeId to use as peer. The same NodeId is never returned twice
243 * (across all Scenarios combined). */
244 NodeId NewPeer()
245 {
246 bool ok;
247 NodeId ret;
248 do {
249 ret = m_rng.randbits(63);
250 ok = m_runner.peerset.insert(ret).second;
251 } while(!ok);
252 return ret;
253 }
254
255 std::chrono::microseconds Now() const { return m_now; }
256 };
257
258 /** Add to scenario a test with a single tx announced by a single peer.
259 *
260 * config is an integer in [0, 32), which controls which variant of the test is used.
261 */
262 void TxRequestTest::BuildSingleTest(Scenario& scenario, int config)
263 {
264 auto peer = scenario.NewPeer();
265 auto gtxid = scenario.NewGTxid();
266 bool immediate = config & 1;
267 bool preferred = config & 2;
268 auto delay = immediate ? NO_TIME : RandomTime8s();
269
270 scenario.SetTestName(strprintf("Single(config=%i)", config));
271
272 // Receive an announcement, either immediately requestable or delayed.
273 scenario.ReceivedInv(peer, gtxid, preferred, immediate ? MIN_TIME : scenario.Now() + delay);
274 if (immediate) {
275 scenario.Check(peer, {gtxid}, 1, 0, 0, "s1");
276 } else {
277 scenario.Check(peer, {}, 1, 0, 0, "s2");
278 scenario.AdvanceTime(delay - MICROSECOND);
279 scenario.Check(peer, {}, 1, 0, 0, "s3");
280 scenario.AdvanceTime(MICROSECOND);
281 scenario.Check(peer, {gtxid}, 1, 0, 0, "s4");
282 }
283
284 if (config >> 3) { // We'll request the transaction
285 scenario.AdvanceTime(RandomTime8s());
286 auto expiry = RandomTime8s();
287 scenario.Check(peer, {gtxid}, 1, 0, 0, "s5");
288 scenario.RequestedTx(peer, gtxid.GetHash(), scenario.Now() + expiry);
289 scenario.Check(peer, {}, 0, 1, 0, "s6");
290
291 if ((config >> 3) == 1) { // The request will time out
292 scenario.AdvanceTime(expiry - MICROSECOND);
293 scenario.Check(peer, {}, 0, 1, 0, "s7");
294 scenario.AdvanceTime(MICROSECOND);
295 scenario.Check(peer, {}, 0, 0, 0, "s8");
296 scenario.CheckExpired(peer, gtxid);
297 return;
298 } else {
299 scenario.AdvanceTime(std::chrono::microseconds{m_rng.randrange(expiry.count())});
300 scenario.Check(peer, {}, 0, 1, 0, "s9");
301 if ((config >> 3) == 3) { // A response will arrive for the transaction
302 scenario.ReceivedResponse(peer, gtxid.GetHash());
303 scenario.Check(peer, {}, 0, 0, 0, "s10");
304 return;
305 }
306 }
307 }
308
309 if (config & 4) { // The peer will go offline
310 scenario.DisconnectedPeer(peer);
311 } else { // The transaction is no longer needed
312 scenario.ForgetTxHash(gtxid.GetHash());
313 }
314 scenario.Check(peer, {}, 0, 0, 0, "s11");
315 }
316
317 /** Add to scenario a test with a single tx announced by two peers, to verify the
318 * right peer is selected for requests.
319 *
320 * config is an integer in [0, 32), which controls which variant of the test is used.
321 */
322 void TxRequestTest::BuildPriorityTest(Scenario& scenario, int config)
323 {
324 scenario.SetTestName(strprintf("Priority(config=%i)", config));
325
326 // Two peers. They will announce in order {peer1, peer2}.
327 auto peer1 = scenario.NewPeer(), peer2 = scenario.NewPeer();
328 // Construct a transaction that under random rules would be preferred by peer2 or peer1,
329 // depending on configuration.
330 bool prio1 = config & 1;
331 auto gtxid = prio1 ? scenario.NewGTxid({{peer1, peer2}}) : scenario.NewGTxid({{peer2, peer1}});
332 bool pref1 = config & 2, pref2 = config & 4;
333
334 scenario.ReceivedInv(peer1, gtxid, pref1, MIN_TIME);
335 scenario.Check(peer1, {gtxid}, 1, 0, 0, "p1");
336 if (m_rng.randbool()) {
337 scenario.AdvanceTime(RandomTime8s());
338 scenario.Check(peer1, {gtxid}, 1, 0, 0, "p2");
339 }
340
341 scenario.ReceivedInv(peer2, gtxid, pref2, MIN_TIME);
342 bool stage2_prio =
343 // At this point, peer2 will be given priority if:
344 // - It is preferred and peer1 is not
345 (pref2 && !pref1) ||
346 // - They're in the same preference class,
347 // and the randomized priority favors peer2 over peer1.
348 (pref1 == pref2 && !prio1);
349 NodeId priopeer = stage2_prio ? peer2 : peer1, otherpeer = stage2_prio ? peer1 : peer2;
350 scenario.Check(otherpeer, {}, 1, 0, 0, "p3");
351 scenario.Check(priopeer, {gtxid}, 1, 0, 0, "p4");
352 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
353 scenario.Check(otherpeer, {}, 1, 0, 0, "p5");
354 scenario.Check(priopeer, {gtxid}, 1, 0, 0, "p6");
355
356 // We possibly request from the selected peer.
357 if (config & 8) {
358 scenario.RequestedTx(priopeer, gtxid.GetHash(), MAX_TIME);
359 scenario.Check(priopeer, {}, 0, 1, 0, "p7");
360 scenario.Check(otherpeer, {}, 1, 0, 0, "p8");
361 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
362 }
363
364 // The peer which was selected (or requested from) now goes offline, or a NOTFOUND is received from them.
365 if (config & 16) {
366 scenario.DisconnectedPeer(priopeer);
367 } else {
368 scenario.ReceivedResponse(priopeer, gtxid.GetHash());
369 }
370 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
371 scenario.Check(priopeer, {}, 0, 0, !(config & 16), "p8");
372 scenario.Check(otherpeer, {gtxid}, 1, 0, 0, "p9");
373 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
374
375 // Now the other peer goes offline.
376 scenario.DisconnectedPeer(otherpeer);
377 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
378 scenario.Check(peer1, {}, 0, 0, 0, "p10");
379 scenario.Check(peer2, {}, 0, 0, 0, "p11");
380 }
381
382 /** Add to scenario a randomized test in which N peers announce the same transaction, to verify
383 * the order in which they are requested. */
384 void TxRequestTest::BuildBigPriorityTest(Scenario& scenario, int peers)
385 {
386 scenario.SetTestName(strprintf("BigPriority(peers=%i)", peers));
387
388 // We will have N peers announce the same transaction.
389 std::map<NodeId, bool> preferred;
390 std::vector<NodeId> pref_peers, npref_peers;
391 int num_pref = m_rng.randrange(peers + 1) ; // Some preferred, ...
392 int num_npref = peers - num_pref; // some not preferred.
393 for (int i = 0; i < num_pref; ++i) {
394 pref_peers.push_back(scenario.NewPeer());
395 preferred[pref_peers.back()] = true;
396 }
397 for (int i = 0; i < num_npref; ++i) {
398 npref_peers.push_back(scenario.NewPeer());
399 preferred[npref_peers.back()] = false;
400 }
401 // Make a list of all peers, in order of intended request order (concatenation of pref_peers and npref_peers).
402 std::vector<NodeId> request_order;
403 request_order.reserve(num_pref + num_npref);
404 for (int i = 0; i < num_pref; ++i) request_order.push_back(pref_peers[i]);
405 for (int i = 0; i < num_npref; ++i) request_order.push_back(npref_peers[i]);
406
407 // Determine the announcement order randomly.
408 std::vector<NodeId> announce_order = request_order;
409 std::shuffle(announce_order.begin(), announce_order.end(), m_rng);
410
411 // Find a gtxid whose txhash prioritization is consistent with the required ordering within pref_peers and
412 // within npref_peers.
413 auto gtxid = scenario.NewGTxid({pref_peers, npref_peers});
414
415 // Decide reqtimes in opposite order of the expected request order. This means that as time passes we expect the
416 // to-be-requested-from-peer will change every time a subsequent reqtime is passed.
417 std::map<NodeId, std::chrono::microseconds> reqtimes;
418 auto reqtime = scenario.Now();
419 for (int i = peers - 1; i >= 0; --i) {
420 reqtime += RandomTime8s();
421 reqtimes[request_order[i]] = reqtime;
422 }
423
424 // Actually announce from all peers simultaneously (but in announce_order).
425 for (const auto peer : announce_order) {
426 scenario.ReceivedInv(peer, gtxid, preferred[peer], reqtimes[peer]);
427 }
428 for (const auto peer : announce_order) {
429 scenario.Check(peer, {}, 1, 0, 0, "b1");
430 }
431
432 // Let time pass and observe the to-be-requested-from peer change, from nonpreferred to preferred, and from
433 // high priority to low priority within each class.
434 for (int i = peers - 1; i >= 0; --i) {
435 scenario.AdvanceTime(reqtimes[request_order[i]] - scenario.Now() - MICROSECOND);
436 scenario.Check(request_order[i], {}, 1, 0, 0, "b2");
437 scenario.AdvanceTime(MICROSECOND);
438 scenario.Check(request_order[i], {gtxid}, 1, 0, 0, "b3");
439 }
440
441 // Peers now in random order go offline, or send NOTFOUNDs. At every point in time the new to-be-requested-from
442 // peer should be the best remaining one, so verify this after every response.
443 for (int i = 0; i < peers; ++i) {
444 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
445 const int pos = m_rng.randrange(request_order.size());
446 const auto peer = request_order[pos];
447 request_order.erase(request_order.begin() + pos);
448 if (m_rng.randbool()) {
449 scenario.DisconnectedPeer(peer);
450 scenario.Check(peer, {}, 0, 0, 0, "b4");
451 } else {
452 scenario.ReceivedResponse(peer, gtxid.GetHash());
453 scenario.Check(peer, {}, 0, 0, request_order.size() > 0, "b5");
454 }
455 if (request_order.size()) {
456 scenario.Check(request_order[0], {gtxid}, 1, 0, 0, "b6");
457 }
458 }
459
460 // Everything is gone in the end.
461 for (const auto peer : announce_order) {
462 scenario.Check(peer, {}, 0, 0, 0, "b7");
463 }
464 }
465
466 /** Add to scenario a test with one peer announcing two transactions, to verify they are
467 * fetched in announcement order.
468 *
469 * config is an integer in [0, 4) inclusive, and selects the variant of the test.
470 */
471 void TxRequestTest::BuildRequestOrderTest(Scenario& scenario, int config)
472 {
473 scenario.SetTestName(strprintf("RequestOrder(config=%i)", config));
474
475 auto peer = scenario.NewPeer();
476 auto gtxid1 = scenario.NewGTxid();
477 auto gtxid2 = scenario.NewGTxid();
478
479 auto reqtime2 = scenario.Now() + RandomTime8s();
480 auto reqtime1 = reqtime2 + RandomTime8s();
481
482 scenario.ReceivedInv(peer, gtxid1, config & 1, reqtime1);
483 // Simulate time going backwards by giving the second announcement an earlier reqtime.
484 scenario.ReceivedInv(peer, gtxid2, config & 2, reqtime2);
485
486 scenario.AdvanceTime(reqtime2 - MICROSECOND - scenario.Now());
487 scenario.Check(peer, {}, 2, 0, 0, "o1");
488 scenario.AdvanceTime(MICROSECOND);
489 scenario.Check(peer, {gtxid2}, 2, 0, 0, "o2");
490 scenario.AdvanceTime(reqtime1 - MICROSECOND - scenario.Now());
491 scenario.Check(peer, {gtxid2}, 2, 0, 0, "o3");
492 scenario.AdvanceTime(MICROSECOND);
493 // Even with time going backwards in between announcements, the return value of GetRequestable is in
494 // announcement order.
495 scenario.Check(peer, {gtxid1, gtxid2}, 2, 0, 0, "o4");
496
497 scenario.DisconnectedPeer(peer);
498 scenario.Check(peer, {}, 0, 0, 0, "o5");
499 }
500
501 /** Add to scenario a test that verifies behavior related to both txid and wtxid with the same
502 * hash being announced.
503 *
504 * config is an integer in [0, 4) inclusive, and selects the variant of the test used.
505 */
506 void TxRequestTest::BuildWtxidTest(Scenario& scenario, int config)
507 {
508 scenario.SetTestName(strprintf("Wtxid(config=%i)", config));
509
510 auto peerT = scenario.NewPeer();
511 auto peerW = scenario.NewPeer();
512 auto txhash = scenario.NewTxHash();
513 auto txid{GenTxid::Txid(txhash)};
514 auto wtxid{GenTxid::Wtxid(txhash)};
515
516 auto reqtimeT = m_rng.randbool() ? MIN_TIME : scenario.Now() + RandomTime8s();
517 auto reqtimeW = m_rng.randbool() ? MIN_TIME : scenario.Now() + RandomTime8s();
518
519 // Announce txid first or wtxid first.
520 if (config & 1) {
521 scenario.ReceivedInv(peerT, txid, config & 2, reqtimeT);
522 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
523 scenario.ReceivedInv(peerW, wtxid, !(config & 2), reqtimeW);
524 } else {
525 scenario.ReceivedInv(peerW, wtxid, !(config & 2), reqtimeW);
526 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
527 scenario.ReceivedInv(peerT, txid, config & 2, reqtimeT);
528 }
529
530 // Let time pass if needed, and check that the preferred announcement (txid or wtxid)
531 // is correctly to-be-requested (and with the correct wtxidness).
532 auto max_reqtime = std::max(reqtimeT, reqtimeW);
533 if (max_reqtime > scenario.Now()) scenario.AdvanceTime(max_reqtime - scenario.Now());
534 if (config & 2) {
535 scenario.Check(peerT, {txid}, 1, 0, 0, "w1");
536 scenario.Check(peerW, {}, 1, 0, 0, "w2");
537 } else {
538 scenario.Check(peerT, {}, 1, 0, 0, "w3");
539 scenario.Check(peerW, {wtxid}, 1, 0, 0, "w4");
540 }
541
542 // Let the preferred announcement be requested. It's not going to be delivered.
543 auto expiry = RandomTime8s();
544 if (config & 2) {
545 scenario.RequestedTx(peerT, txid.GetHash(), scenario.Now() + expiry);
546 scenario.Check(peerT, {}, 0, 1, 0, "w5");
547 scenario.Check(peerW, {}, 1, 0, 0, "w6");
548 } else {
549 scenario.RequestedTx(peerW, wtxid.GetHash(), scenario.Now() + expiry);
550 scenario.Check(peerT, {}, 1, 0, 0, "w7");
551 scenario.Check(peerW, {}, 0, 1, 0, "w8");
552 }
553
554 // After reaching expiration time of the preferred announcement, verify that the
555 // remaining one is requestable
556 scenario.AdvanceTime(expiry);
557 if (config & 2) {
558 scenario.Check(peerT, {}, 0, 0, 1, "w9");
559 scenario.Check(peerW, {wtxid}, 1, 0, 0, "w10");
560 scenario.CheckExpired(peerT, txid);
561 } else {
562 scenario.Check(peerT, {txid}, 1, 0, 0, "w11");
563 scenario.Check(peerW, {}, 0, 0, 1, "w12");
564 scenario.CheckExpired(peerW, wtxid);
565 }
566
567 // If a good transaction with either that hash as wtxid or txid arrives, both
568 // announcements are gone.
569 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
570 scenario.ForgetTxHash(txhash);
571 scenario.Check(peerT, {}, 0, 0, 0, "w13");
572 scenario.Check(peerW, {}, 0, 0, 0, "w14");
573 }
574
575 /** Add to scenario a test that exercises clocks that go backwards. */
576 void TxRequestTest::BuildTimeBackwardsTest(Scenario& scenario)
577 {
578 auto peer1 = scenario.NewPeer();
579 auto peer2 = scenario.NewPeer();
580 auto gtxid = scenario.NewGTxid({{peer1, peer2}});
581
582 // Announce from peer2.
583 auto reqtime = scenario.Now() + RandomTime8s();
584 scenario.ReceivedInv(peer2, gtxid, true, reqtime);
585 scenario.Check(peer2, {}, 1, 0, 0, "r1");
586 scenario.AdvanceTime(reqtime - scenario.Now());
587 scenario.Check(peer2, {gtxid}, 1, 0, 0, "r2");
588 // Check that if the clock goes backwards by 1us, the transaction would stop being requested.
589 scenario.Check(peer2, {}, 1, 0, 0, "r3", -MICROSECOND);
590 // But it reverts to being requested if time goes forward again.
591 scenario.Check(peer2, {gtxid}, 1, 0, 0, "r4");
592
593 // Announce from peer1.
594 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
595 scenario.ReceivedInv(peer1, gtxid, true, MAX_TIME);
596 scenario.Check(peer2, {gtxid}, 1, 0, 0, "r5");
597 scenario.Check(peer1, {}, 1, 0, 0, "r6");
598
599 // Request from peer1.
600 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
601 auto expiry = scenario.Now() + RandomTime8s();
602 scenario.RequestedTx(peer1, gtxid.GetHash(), expiry);
603 scenario.Check(peer1, {}, 0, 1, 0, "r7");
604 scenario.Check(peer2, {}, 1, 0, 0, "r8");
605
606 // Expiration passes.
607 scenario.AdvanceTime(expiry - scenario.Now());
608 scenario.Check(peer1, {}, 0, 0, 1, "r9");
609 scenario.Check(peer2, {gtxid}, 1, 0, 0, "r10"); // Request goes back to peer2.
610 scenario.CheckExpired(peer1, gtxid);
611 scenario.Check(peer1, {}, 0, 0, 1, "r11", -MICROSECOND); // Going back does not unexpire.
612 scenario.Check(peer2, {gtxid}, 1, 0, 0, "r12", -MICROSECOND);
613
614 // Peer2 goes offline, meaning no viable announcements remain.
615 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
616 scenario.DisconnectedPeer(peer2);
617 scenario.Check(peer1, {}, 0, 0, 0, "r13");
618 scenario.Check(peer2, {}, 0, 0, 0, "r14");
619 }
620
621 /** Add to scenario a test that involves RequestedTx() calls for txhashes not returned by GetRequestable. */
622 void TxRequestTest::BuildWeirdRequestsTest(Scenario& scenario)
623 {
624 auto peer1 = scenario.NewPeer();
625 auto peer2 = scenario.NewPeer();
626 auto gtxid1 = scenario.NewGTxid({{peer1, peer2}});
627 auto gtxid2 = scenario.NewGTxid({{peer2, peer1}});
628
629 // Announce gtxid1 by peer1.
630 scenario.ReceivedInv(peer1, gtxid1, true, MIN_TIME);
631 scenario.Check(peer1, {gtxid1}, 1, 0, 0, "q1");
632
633 // Announce gtxid2 by peer2.
634 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
635 scenario.ReceivedInv(peer2, gtxid2, true, MIN_TIME);
636 scenario.Check(peer1, {gtxid1}, 1, 0, 0, "q2");
637 scenario.Check(peer2, {gtxid2}, 1, 0, 0, "q3");
638
639 // We request gtxid2 from *peer1* - no effect.
640 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
641 scenario.RequestedTx(peer1, gtxid2.GetHash(), MAX_TIME);
642 scenario.Check(peer1, {gtxid1}, 1, 0, 0, "q4");
643 scenario.Check(peer2, {gtxid2}, 1, 0, 0, "q5");
644
645 // Now request gtxid1 from peer1 - marks it as REQUESTED.
646 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
647 auto expiryA = scenario.Now() + RandomTime8s();
648 scenario.RequestedTx(peer1, gtxid1.GetHash(), expiryA);
649 scenario.Check(peer1, {}, 0, 1, 0, "q6");
650 scenario.Check(peer2, {gtxid2}, 1, 0, 0, "q7");
651
652 // Request it a second time - nothing happens, as it's already REQUESTED.
653 auto expiryB = expiryA + RandomTime8s();
654 scenario.RequestedTx(peer1, gtxid1.GetHash(), expiryB);
655 scenario.Check(peer1, {}, 0, 1, 0, "q8");
656 scenario.Check(peer2, {gtxid2}, 1, 0, 0, "q9");
657
658 // Also announce gtxid1 from peer2 now, so that the txhash isn't forgotten when the peer1 request expires.
659 scenario.ReceivedInv(peer2, gtxid1, true, MIN_TIME);
660 scenario.Check(peer1, {}, 0, 1, 0, "q10");
661 scenario.Check(peer2, {gtxid2}, 2, 0, 0, "q11");
662
663 // When reaching expiryA, it expires (not expiryB, which is later).
664 scenario.AdvanceTime(expiryA - scenario.Now());
665 scenario.Check(peer1, {}, 0, 0, 1, "q12");
666 scenario.Check(peer2, {gtxid2, gtxid1}, 2, 0, 0, "q13");
667 scenario.CheckExpired(peer1, gtxid1);
668
669 // Requesting it yet again from peer1 doesn't do anything, as it's already COMPLETED.
670 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
671 scenario.RequestedTx(peer1, gtxid1.GetHash(), MAX_TIME);
672 scenario.Check(peer1, {}, 0, 0, 1, "q14");
673 scenario.Check(peer2, {gtxid2, gtxid1}, 2, 0, 0, "q15");
674
675 // Now announce gtxid2 from peer1.
676 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
677 scenario.ReceivedInv(peer1, gtxid2, true, MIN_TIME);
678 scenario.Check(peer1, {}, 1, 0, 1, "q16");
679 scenario.Check(peer2, {gtxid2, gtxid1}, 2, 0, 0, "q17");
680
681 // And request it from peer1 (weird as peer2 has the preference).
682 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
683 scenario.RequestedTx(peer1, gtxid2.GetHash(), MAX_TIME);
684 scenario.Check(peer1, {}, 0, 1, 1, "q18");
685 scenario.Check(peer2, {gtxid1}, 2, 0, 0, "q19");
686
687 // If peer2 now (normally) requests gtxid2, the existing request by peer1 becomes COMPLETED.
688 if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
689 scenario.RequestedTx(peer2, gtxid2.GetHash(), MAX_TIME);
690 scenario.Check(peer1, {}, 0, 0, 2, "q20");
691 scenario.Check(peer2, {gtxid1}, 1, 1, 0, "q21");
692
693 // If peer2 goes offline, no viable announcements remain.
694 scenario.DisconnectedPeer(peer2);
695 scenario.Check(peer1, {}, 0, 0, 0, "q22");
696 scenario.Check(peer2, {}, 0, 0, 0, "q23");
697 }
698
699 void TxRequestTest::TestInterleavedScenarios()
700 {
701 // Create a list of functions which add tests to scenarios.
702 std::vector<std::function<void(Scenario&)>> builders;
703 // Add instances of every test, for every configuration.
704 for (int n = 0; n < 64; ++n) {
705 builders.emplace_back([this, n](Scenario& scenario) { BuildWtxidTest(scenario, n); });
706 builders.emplace_back([this, n](Scenario& scenario) { BuildRequestOrderTest(scenario, n & 3); });
707 builders.emplace_back([this, n](Scenario& scenario) { BuildSingleTest(scenario, n & 31); });
708 builders.emplace_back([this, n](Scenario& scenario) { BuildPriorityTest(scenario, n & 31); });
709 builders.emplace_back([this, n](Scenario& scenario) { BuildBigPriorityTest(scenario, (n & 7) + 1); });
710 builders.emplace_back([this](Scenario& scenario) { BuildTimeBackwardsTest(scenario); });
711 builders.emplace_back([this](Scenario& scenario) { BuildWeirdRequestsTest(scenario); });
712 }
713 // Randomly shuffle all those functions.
714 std::shuffle(builders.begin(), builders.end(), m_rng);
715
716 Runner runner;
717 auto starttime = RandomTime1y();
718 // Construct many scenarios, and run (up to) 10 randomly-chosen tests consecutively in each.
719 while (builders.size()) {
720 // Introduce some variation in the start time of each scenario, so they don't all start off
721 // concurrently, but get a more random interleaving.
722 auto scenario_start = starttime + RandomTime8s() + RandomTime8s() + RandomTime8s();
723 Scenario scenario(m_rng, runner, scenario_start);
724 for (int j = 0; builders.size() && j < 10; ++j) {
725 builders.back()(scenario);
726 builders.pop_back();
727 }
728 }
729 // Sort all the actions from all those scenarios chronologically, resulting in the actions from
730 // distinct scenarios to become interleaved. Use stable_sort so that actions from one scenario
731 // aren't reordered w.r.t. each other.
732 std::stable_sort(runner.actions.begin(), runner.actions.end(), [](const Action& a1, const Action& a2) {
733 return a1.first < a2.first;
734 });
735
736 // Run all actions from all scenarios, in order.
737 for (auto& action : runner.actions) {
738 action.second();
739 }
740
741 BOOST_CHECK_EQUAL(runner.txrequest.Size(), 0U);
742 BOOST_CHECK(runner.expired.empty());
743 }
744
745 } // namespace
746
747 BOOST_FIXTURE_TEST_SUITE(txrequest_tests, TxRequestTest)
748
749 BOOST_AUTO_TEST_CASE(TxRequestTest)
750 {
751 for (int i = 0; i < 5; ++i) {
752 TestInterleavedScenarios();
753 }
754 }
755
756 BOOST_AUTO_TEST_SUITE_END()
757