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