16 #include <boost/test/unit_test.hpp>
22 constexpr std::chrono::microseconds MIN_TIME = std::chrono::microseconds::min();
23 constexpr std::chrono::microseconds MAX_TIME = std::chrono::microseconds::max();
24 constexpr std::chrono::microseconds MICROSECOND = std::chrono::microseconds{1};
25 constexpr std::chrono::microseconds NO_TIME = std::chrono::microseconds{0};
28 using Action = std::pair<std::chrono::microseconds, std::function<void()>>;
40 std::vector<Action> actions;
43 std::set<NodeId> peerset;
46 std::set<uint256> txhashset;
51 std::multiset<std::pair<NodeId, GenTxid>> expired;
54 std::chrono::microseconds RandomTime8s() {
return std::chrono::microseconds{1 +
InsecureRandBits(23)}; }
55 std::chrono::microseconds RandomTime1y() {
return std::chrono::microseconds{1 +
InsecureRandBits(45)}; }
69 std::chrono::microseconds m_now;
70 std::string m_testname;
73 Scenario(Runner& runner, std::chrono::microseconds starttime) : m_runner(runner), m_now(starttime) {}
76 void SetTestName(std::string testname)
78 m_testname = std::move(testname);
82 void AdvanceTime(std::chrono::microseconds amount)
84 assert(amount.count() >= 0);
89 void ForgetTxHash(
const uint256& txhash)
91 auto& runner = m_runner;
92 runner.actions.emplace_back(m_now, [=,&runner]() {
93 runner.txrequest.ForgetTxHash(txhash);
94 runner.txrequest.SanityCheck();
99 void ReceivedInv(
NodeId peer,
const GenTxid& gtxid,
bool pref, std::chrono::microseconds reqtime)
101 auto& runner = m_runner;
102 runner.actions.emplace_back(m_now, [=,&runner]() {
103 runner.txrequest.ReceivedInv(peer, gtxid, pref, reqtime);
104 runner.txrequest.SanityCheck();
109 void DisconnectedPeer(
NodeId peer)
111 auto& runner = m_runner;
112 runner.actions.emplace_back(m_now, [=,&runner]() {
113 runner.txrequest.DisconnectedPeer(peer);
114 runner.txrequest.SanityCheck();
119 void RequestedTx(
NodeId peer,
const uint256& txhash, std::chrono::microseconds exptime)
121 auto& runner = m_runner;
122 runner.actions.emplace_back(m_now, [=,&runner]() {
123 runner.txrequest.RequestedTx(peer, txhash, exptime);
124 runner.txrequest.SanityCheck();
131 auto& runner = m_runner;
132 runner.actions.emplace_back(m_now, [=,&runner]() {
133 runner.txrequest.ReceivedResponse(peer, txhash);
134 runner.txrequest.SanityCheck();
149 void Check(
NodeId peer,
const std::vector<GenTxid>& expected,
size_t candidates,
size_t inflight,
150 size_t completed,
const std::string& checkname,
151 std::chrono::microseconds offset = std::chrono::microseconds{0})
153 const auto comment = m_testname +
" " + checkname;
154 auto& runner = m_runner;
155 const auto now = m_now;
156 assert(offset.count() <= 0);
157 runner.actions.emplace_back(m_now, [=,&runner]() {
158 std::vector<std::pair<NodeId, GenTxid>> expired_now;
159 auto ret = runner.txrequest.GetRequestable(peer, now + offset, &expired_now);
160 for (
const auto& entry : expired_now) runner.expired.insert(entry);
161 runner.txrequest.SanityCheck();
162 runner.txrequest.PostGetRequestableSanityCheck(now + offset);
163 size_t total = candidates + inflight + completed;
164 size_t real_total = runner.txrequest.Count(peer);
165 size_t real_candidates = runner.txrequest.CountCandidates(peer);
166 size_t real_inflight = runner.txrequest.CountInFlight(peer);
167 BOOST_CHECK_MESSAGE(real_total == total,
strprintf(
"[" + comment +
"] total %i (%i expected)", real_total, total));
168 BOOST_CHECK_MESSAGE(real_inflight == inflight,
strprintf(
"[" + comment +
"] inflight %i (%i expected)", real_inflight, inflight));
169 BOOST_CHECK_MESSAGE(real_candidates == candidates,
strprintf(
"[" + comment +
"] candidates %i (%i expected)", real_candidates, candidates));
170 BOOST_CHECK_MESSAGE(
ret == expected,
"[" + comment +
"] mismatching requestables");
180 const auto& testname = m_testname;
181 auto& runner = m_runner;
182 runner.actions.emplace_back(m_now, [=,&runner]() {
183 auto it = runner.expired.find(std::pair<NodeId, GenTxid>{peer, gtxid});
184 BOOST_CHECK_MESSAGE(it != runner.expired.end(),
"[" + testname +
"] missing expiration");
185 if (it != runner.expired.end()) runner.expired.erase(it);
197 uint256 NewTxHash(
const std::vector<std::vector<NodeId>>& orders = {})
204 for (
const auto& order : orders) {
205 for (
size_t pos = 1; pos < order.size(); ++pos) {
206 uint64_t prio_prev = m_runner.txrequest.ComputePriority(
ret, order[pos - 1],
true);
207 uint64_t prio_cur = m_runner.txrequest.ComputePriority(
ret, order[pos],
true);
208 if (prio_prev <= prio_cur) {
216 ok = m_runner.txhashset.insert(
ret).second;
223 GenTxid NewGTxid(
const std::vector<std::vector<NodeId>>& orders = {})
236 ok = m_runner.peerset.insert(
ret).second;
241 std::chrono::microseconds
Now()
const {
return m_now; }
248 void BuildSingleTest(Scenario& scenario,
int config)
250 auto peer = scenario.NewPeer();
251 auto gtxid = scenario.NewGTxid();
252 bool immediate = config & 1;
253 bool preferred = config & 2;
254 auto delay = immediate ? NO_TIME : RandomTime8s();
256 scenario.SetTestName(
strprintf(
"Single(config=%i)", config));
259 scenario.ReceivedInv(peer, gtxid, preferred, immediate ? MIN_TIME : scenario.Now() + delay);
261 scenario.Check(peer, {gtxid}, 1, 0, 0,
"s1");
263 scenario.Check(peer, {}, 1, 0, 0,
"s2");
264 scenario.AdvanceTime(delay - MICROSECOND);
265 scenario.Check(peer, {}, 1, 0, 0,
"s3");
266 scenario.AdvanceTime(MICROSECOND);
267 scenario.Check(peer, {gtxid}, 1, 0, 0,
"s4");
271 scenario.AdvanceTime(RandomTime8s());
272 auto expiry = RandomTime8s();
273 scenario.Check(peer, {gtxid}, 1, 0, 0,
"s5");
274 scenario.RequestedTx(peer, gtxid.
GetHash(), scenario.Now() + expiry);
275 scenario.Check(peer, {}, 0, 1, 0,
"s6");
277 if ((config >> 3) == 1) {
278 scenario.AdvanceTime(expiry - MICROSECOND);
279 scenario.Check(peer, {}, 0, 1, 0,
"s7");
280 scenario.AdvanceTime(MICROSECOND);
281 scenario.Check(peer, {}, 0, 0, 0,
"s8");
282 scenario.CheckExpired(peer, gtxid);
285 scenario.AdvanceTime(std::chrono::microseconds{
InsecureRandRange(expiry.count())});
286 scenario.Check(peer, {}, 0, 1, 0,
"s9");
287 if ((config >> 3) == 3) {
288 scenario.ReceivedResponse(peer, gtxid.
GetHash());
289 scenario.Check(peer, {}, 0, 0, 0,
"s10");
296 scenario.DisconnectedPeer(peer);
298 scenario.ForgetTxHash(gtxid.
GetHash());
300 scenario.Check(peer, {}, 0, 0, 0,
"s11");
308 void BuildPriorityTest(Scenario& scenario,
int config)
310 scenario.SetTestName(
strprintf(
"Priority(config=%i)", config));
313 auto peer1 = scenario.NewPeer(), peer2 = scenario.NewPeer();
316 bool prio1 = config & 1;
317 auto gtxid = prio1 ? scenario.NewGTxid({{peer1, peer2}}) : scenario.NewGTxid({{peer2, peer1}});
318 bool pref1 = config & 2, pref2 = config & 4;
320 scenario.ReceivedInv(peer1, gtxid, pref1, MIN_TIME);
321 scenario.Check(peer1, {gtxid}, 1, 0, 0,
"p1");
323 scenario.AdvanceTime(RandomTime8s());
324 scenario.Check(peer1, {gtxid}, 1, 0, 0,
"p2");
327 scenario.ReceivedInv(peer2, gtxid, pref2, MIN_TIME);
334 (pref1 == pref2 && !prio1);
335 NodeId priopeer = stage2_prio ? peer2 : peer1, otherpeer = stage2_prio ? peer1 : peer2;
336 scenario.Check(otherpeer, {}, 1, 0, 0,
"p3");
337 scenario.Check(priopeer, {gtxid}, 1, 0, 0,
"p4");
339 scenario.Check(otherpeer, {}, 1, 0, 0,
"p5");
340 scenario.Check(priopeer, {gtxid}, 1, 0, 0,
"p6");
344 scenario.RequestedTx(priopeer, gtxid.
GetHash(), MAX_TIME);
345 scenario.Check(priopeer, {}, 0, 1, 0,
"p7");
346 scenario.Check(otherpeer, {}, 1, 0, 0,
"p8");
352 scenario.DisconnectedPeer(priopeer);
354 scenario.ReceivedResponse(priopeer, gtxid.
GetHash());
357 scenario.Check(priopeer, {}, 0, 0, !(config & 16),
"p8");
358 scenario.Check(otherpeer, {gtxid}, 1, 0, 0,
"p9");
362 scenario.DisconnectedPeer(otherpeer);
364 scenario.Check(peer1, {}, 0, 0, 0,
"p10");
365 scenario.Check(peer2, {}, 0, 0, 0,
"p11");
370 void BuildBigPriorityTest(Scenario& scenario,
int peers)
372 scenario.SetTestName(
strprintf(
"BigPriority(peers=%i)", peers));
375 std::map<NodeId, bool> preferred;
376 std::vector<NodeId> pref_peers, npref_peers;
378 int num_npref = peers - num_pref;
379 for (
int i = 0; i < num_pref; ++i) {
380 pref_peers.push_back(scenario.NewPeer());
381 preferred[pref_peers.back()] =
true;
383 for (
int i = 0; i < num_npref; ++i) {
384 npref_peers.push_back(scenario.NewPeer());
385 preferred[npref_peers.back()] =
false;
388 std::vector<NodeId> request_order;
389 request_order.reserve(num_pref + num_npref);
390 for (
int i = 0; i < num_pref; ++i) request_order.push_back(pref_peers[i]);
391 for (
int i = 0; i < num_npref; ++i) request_order.push_back(npref_peers[i]);
394 std::vector<NodeId> announce_order = request_order;
399 auto gtxid = scenario.NewGTxid({pref_peers, npref_peers});
403 std::map<NodeId, std::chrono::microseconds> reqtimes;
404 auto reqtime = scenario.Now();
405 for (
int i = peers - 1; i >= 0; --i) {
406 reqtime += RandomTime8s();
407 reqtimes[request_order[i]] = reqtime;
411 for (
const auto peer : announce_order) {
412 scenario.ReceivedInv(peer, gtxid, preferred[peer], reqtimes[peer]);
414 for (
const auto peer : announce_order) {
415 scenario.Check(peer, {}, 1, 0, 0,
"b1");
420 for (
int i = peers - 1; i >= 0; --i) {
421 scenario.AdvanceTime(reqtimes[request_order[i]] - scenario.Now() - MICROSECOND);
422 scenario.Check(request_order[i], {}, 1, 0, 0,
"b2");
423 scenario.AdvanceTime(MICROSECOND);
424 scenario.Check(request_order[i], {gtxid}, 1, 0, 0,
"b3");
429 for (
int i = 0; i < peers; ++i) {
432 const auto peer = request_order[pos];
433 request_order.erase(request_order.begin() + pos);
435 scenario.DisconnectedPeer(peer);
436 scenario.Check(peer, {}, 0, 0, 0,
"b4");
438 scenario.ReceivedResponse(peer, gtxid.
GetHash());
439 scenario.Check(peer, {}, 0, 0, request_order.size() > 0,
"b5");
441 if (request_order.size()) {
442 scenario.Check(request_order[0], {gtxid}, 1, 0, 0,
"b6");
447 for (
const auto peer : announce_order) {
448 scenario.Check(peer, {}, 0, 0, 0,
"b7");
457 void BuildRequestOrderTest(Scenario& scenario,
int config)
459 scenario.SetTestName(
strprintf(
"RequestOrder(config=%i)", config));
461 auto peer = scenario.NewPeer();
462 auto gtxid1 = scenario.NewGTxid();
463 auto gtxid2 = scenario.NewGTxid();
465 auto reqtime2 = scenario.Now() + RandomTime8s();
466 auto reqtime1 = reqtime2 + RandomTime8s();
468 scenario.ReceivedInv(peer, gtxid1, config & 1, reqtime1);
470 scenario.ReceivedInv(peer, gtxid2, config & 2, reqtime2);
472 scenario.AdvanceTime(reqtime2 - MICROSECOND - scenario.Now());
473 scenario.Check(peer, {}, 2, 0, 0,
"o1");
474 scenario.AdvanceTime(MICROSECOND);
475 scenario.Check(peer, {gtxid2}, 2, 0, 0,
"o2");
476 scenario.AdvanceTime(reqtime1 - MICROSECOND - scenario.Now());
477 scenario.Check(peer, {gtxid2}, 2, 0, 0,
"o3");
478 scenario.AdvanceTime(MICROSECOND);
481 scenario.Check(peer, {gtxid1, gtxid2}, 2, 0, 0,
"o4");
483 scenario.DisconnectedPeer(peer);
484 scenario.Check(peer, {}, 0, 0, 0,
"o5");
492 void BuildWtxidTest(Scenario& scenario,
int config)
494 scenario.SetTestName(
strprintf(
"Wtxid(config=%i)", config));
496 auto peerT = scenario.NewPeer();
497 auto peerW = scenario.NewPeer();
498 auto txhash = scenario.NewTxHash();
502 auto reqtimeT =
InsecureRandBool() ? MIN_TIME : scenario.Now() + RandomTime8s();
503 auto reqtimeW =
InsecureRandBool() ? MIN_TIME : scenario.Now() + RandomTime8s();
507 scenario.ReceivedInv(peerT, txid, config & 2, reqtimeT);
509 scenario.ReceivedInv(peerW, wtxid, !(config & 2), reqtimeW);
511 scenario.ReceivedInv(peerW, wtxid, !(config & 2), reqtimeW);
513 scenario.ReceivedInv(peerT, txid, config & 2, reqtimeT);
518 auto max_reqtime = std::max(reqtimeT, reqtimeW);
519 if (max_reqtime > scenario.Now()) scenario.AdvanceTime(max_reqtime - scenario.Now());
521 scenario.Check(peerT, {txid}, 1, 0, 0,
"w1");
522 scenario.Check(peerW, {}, 1, 0, 0,
"w2");
524 scenario.Check(peerT, {}, 1, 0, 0,
"w3");
525 scenario.Check(peerW, {wtxid}, 1, 0, 0,
"w4");
529 auto expiry = RandomTime8s();
531 scenario.RequestedTx(peerT, txid.GetHash(), scenario.Now() + expiry);
532 scenario.Check(peerT, {}, 0, 1, 0,
"w5");
533 scenario.Check(peerW, {}, 1, 0, 0,
"w6");
535 scenario.RequestedTx(peerW, wtxid.GetHash(), scenario.Now() + expiry);
536 scenario.Check(peerT, {}, 1, 0, 0,
"w7");
537 scenario.Check(peerW, {}, 0, 1, 0,
"w8");
542 scenario.AdvanceTime(expiry);
544 scenario.Check(peerT, {}, 0, 0, 1,
"w9");
545 scenario.Check(peerW, {wtxid}, 1, 0, 0,
"w10");
546 scenario.CheckExpired(peerT, txid);
548 scenario.Check(peerT, {txid}, 1, 0, 0,
"w11");
549 scenario.Check(peerW, {}, 0, 0, 1,
"w12");
550 scenario.CheckExpired(peerW, wtxid);
556 scenario.ForgetTxHash(txhash);
557 scenario.Check(peerT, {}, 0, 0, 0,
"w13");
558 scenario.Check(peerW, {}, 0, 0, 0,
"w14");
562 void BuildTimeBackwardsTest(Scenario& scenario)
564 auto peer1 = scenario.NewPeer();
565 auto peer2 = scenario.NewPeer();
566 auto gtxid = scenario.NewGTxid({{peer1, peer2}});
569 auto reqtime = scenario.Now() + RandomTime8s();
570 scenario.ReceivedInv(peer2, gtxid,
true, reqtime);
571 scenario.Check(peer2, {}, 1, 0, 0,
"r1");
572 scenario.AdvanceTime(reqtime - scenario.Now());
573 scenario.Check(peer2, {gtxid}, 1, 0, 0,
"r2");
575 scenario.Check(peer2, {}, 1, 0, 0,
"r3", -MICROSECOND);
577 scenario.Check(peer2, {gtxid}, 1, 0, 0,
"r4");
581 scenario.ReceivedInv(peer1, gtxid,
true, MAX_TIME);
582 scenario.Check(peer2, {gtxid}, 1, 0, 0,
"r5");
583 scenario.Check(peer1, {}, 1, 0, 0,
"r6");
587 auto expiry = scenario.Now() + RandomTime8s();
588 scenario.RequestedTx(peer1, gtxid.
GetHash(), expiry);
589 scenario.Check(peer1, {}, 0, 1, 0,
"r7");
590 scenario.Check(peer2, {}, 1, 0, 0,
"r8");
593 scenario.AdvanceTime(expiry - scenario.Now());
594 scenario.Check(peer1, {}, 0, 0, 1,
"r9");
595 scenario.Check(peer2, {gtxid}, 1, 0, 0,
"r10");
596 scenario.CheckExpired(peer1, gtxid);
597 scenario.Check(peer1, {}, 0, 0, 1,
"r11", -MICROSECOND);
598 scenario.Check(peer2, {gtxid}, 1, 0, 0,
"r12", -MICROSECOND);
602 scenario.DisconnectedPeer(peer2);
603 scenario.Check(peer1, {}, 0, 0, 0,
"r13");
604 scenario.Check(peer2, {}, 0, 0, 0,
"r14");
608 void BuildWeirdRequestsTest(Scenario& scenario)
610 auto peer1 = scenario.NewPeer();
611 auto peer2 = scenario.NewPeer();
612 auto gtxid1 = scenario.NewGTxid({{peer1, peer2}});
613 auto gtxid2 = scenario.NewGTxid({{peer2, peer1}});
616 scenario.ReceivedInv(peer1, gtxid1,
true, MIN_TIME);
617 scenario.Check(peer1, {gtxid1}, 1, 0, 0,
"q1");
621 scenario.ReceivedInv(peer2, gtxid2,
true, MIN_TIME);
622 scenario.Check(peer1, {gtxid1}, 1, 0, 0,
"q2");
623 scenario.Check(peer2, {gtxid2}, 1, 0, 0,
"q3");
627 scenario.RequestedTx(peer1, gtxid2.GetHash(), MAX_TIME);
628 scenario.Check(peer1, {gtxid1}, 1, 0, 0,
"q4");
629 scenario.Check(peer2, {gtxid2}, 1, 0, 0,
"q5");
633 auto expiryA = scenario.Now() + RandomTime8s();
634 scenario.RequestedTx(peer1, gtxid1.GetHash(), expiryA);
635 scenario.Check(peer1, {}, 0, 1, 0,
"q6");
636 scenario.Check(peer2, {gtxid2}, 1, 0, 0,
"q7");
639 auto expiryB = expiryA + RandomTime8s();
640 scenario.RequestedTx(peer1, gtxid1.GetHash(), expiryB);
641 scenario.Check(peer1, {}, 0, 1, 0,
"q8");
642 scenario.Check(peer2, {gtxid2}, 1, 0, 0,
"q9");
645 scenario.ReceivedInv(peer2, gtxid1,
true, MIN_TIME);
646 scenario.Check(peer1, {}, 0, 1, 0,
"q10");
647 scenario.Check(peer2, {gtxid2}, 2, 0, 0,
"q11");
650 scenario.AdvanceTime(expiryA - scenario.Now());
651 scenario.Check(peer1, {}, 0, 0, 1,
"q12");
652 scenario.Check(peer2, {gtxid2, gtxid1}, 2, 0, 0,
"q13");
653 scenario.CheckExpired(peer1, gtxid1);
657 scenario.RequestedTx(peer1, gtxid1.GetHash(), MAX_TIME);
658 scenario.Check(peer1, {}, 0, 0, 1,
"q14");
659 scenario.Check(peer2, {gtxid2, gtxid1}, 2, 0, 0,
"q15");
663 scenario.ReceivedInv(peer1, gtxid2,
true, MIN_TIME);
664 scenario.Check(peer1, {}, 1, 0, 1,
"q16");
665 scenario.Check(peer2, {gtxid2, gtxid1}, 2, 0, 0,
"q17");
669 scenario.RequestedTx(peer1, gtxid2.GetHash(), MAX_TIME);
670 scenario.Check(peer1, {}, 0, 1, 1,
"q18");
671 scenario.Check(peer2, {gtxid1}, 2, 0, 0,
"q19");
675 scenario.RequestedTx(peer2, gtxid2.GetHash(), MAX_TIME);
676 scenario.Check(peer1, {}, 0, 0, 2,
"q20");
677 scenario.Check(peer2, {gtxid1}, 1, 1, 0,
"q21");
680 scenario.DisconnectedPeer(peer2);
681 scenario.Check(peer1, {}, 0, 0, 0,
"q22");
682 scenario.Check(peer2, {}, 0, 0, 0,
"q23");
685 void TestInterleavedScenarios()
688 std::vector<std::function<void(Scenario&)>> builders;
690 for (
int n = 0; n < 64; ++n) {
691 builders.emplace_back([n](Scenario& scenario){ BuildWtxidTest(scenario, n); });
692 builders.emplace_back([n](Scenario& scenario){ BuildRequestOrderTest(scenario, n & 3); });
693 builders.emplace_back([n](Scenario& scenario){ BuildSingleTest(scenario, n & 31); });
694 builders.emplace_back([n](Scenario& scenario){ BuildPriorityTest(scenario, n & 31); });
695 builders.emplace_back([n](Scenario& scenario){ BuildBigPriorityTest(scenario, (n & 7) + 1); });
696 builders.emplace_back([](Scenario& scenario){ BuildTimeBackwardsTest(scenario); });
697 builders.emplace_back([](Scenario& scenario){ BuildWeirdRequestsTest(scenario); });
703 auto starttime = RandomTime1y();
705 while (builders.size()) {
708 auto scenario_start = starttime + RandomTime8s() + RandomTime8s() + RandomTime8s();
709 Scenario scenario(runner, scenario_start);
710 for (
int j = 0; builders.size() && j < 10; ++j) {
711 builders.back()(scenario);
718 std::stable_sort(runner.actions.begin(), runner.actions.end(), [](
const Action& a1,
const Action& a2) {
719 return a1.first < a2.first;
723 for (
auto& action : runner.actions) {
735 for (
int i = 0; i < 5; ++i) {
736 TestInterleavedScenarios();
A generic txid reference (txid or wtxid).
const uint256 & GetHash() const LIFETIMEBOUND
static GenTxid Wtxid(const uint256 &hash)
static GenTxid Txid(const uint256 &hash)
Data structure to keep track of, and schedule, transaction downloads from peers.
BOOST_AUTO_TEST_SUITE_END()
#define BOOST_CHECK_EQUAL(v1, v2)
#define BOOST_CHECK(expr)
void Shuffle(I first, I last, R &&rng)
More efficient than using std::shuffle on a FastRandomContext.
FastRandomContext g_insecure_rand_ctx
This global and the helpers that use it are not thread-safe.
static uint64_t InsecureRandRange(uint64_t range)
static uint256 InsecureRand256()
static uint64_t InsecureRandBits(int bits)
static bool InsecureRandBool()
T Now()
Return the current time point cast to the given precision.
BOOST_AUTO_TEST_CASE(TxRequestTest)