Inside Bitcoin

251        do {
252            ret = m_rng.randbits(63);
253            ok = m_runner.peerset.insert(ret).second;
254        } while(!ok);
255        return ret;
256    }
257
258    std::chrono::microseconds Now() const { return m_now; }
259};
260
261/** Add to scenario a test with a single tx announced by a single peer.
262 *
263 * config is an integer in [0, 32), which controls which variant of the test is used.
264 */
265void TxRequestTest::BuildSingleTest(Scenario& scenario, int config)
266{
267    auto peer = scenario.NewPeer();
268    auto gtxid = scenario.NewGTxid();
269    bool immediate = config & 1;
270    bool preferred = config & 2;
271    auto delay = immediate ? NO_TIME : RandomTime8s();
272
273    scenario.SetTestName(strprintf("Single(config=%i)", config));
274
275    // Receive an announcement, either immediately requestable or delayed.
276    scenario.ReceivedInv(peer, gtxid, preferred, immediate ? MIN_TIME : scenario.Now() + delay);
277    if (immediate) {
278        scenario.Check(peer, {gtxid}, 1, 0, 0, "s1");
279    } else {
280        scenario.Check(peer, {}, 1, 0, 0, "s2");
281        scenario.AdvanceTime(delay - MICROSECOND);
282        scenario.Check(peer, {}, 1, 0, 0, "s3");
283        scenario.AdvanceTime(MICROSECOND);
284        scenario.Check(peer, {gtxid}, 1, 0, 0, "s4");
285    }
286
287    if (config >> 3) { // We'll request the transaction
288        scenario.AdvanceTime(RandomTime8s());
289        auto expiry = RandomTime8s();
290        scenario.Check(peer, {gtxid}, 1, 0, 0, "s5");
291        scenario.RequestedTx(peer, gtxid.ToUint256(), scenario.Now() + expiry);
292        scenario.Check(peer, {}, 0, 1, 0, "s6");
293
294        if ((config >> 3) == 1) { // The request will time out
295            scenario.AdvanceTime(expiry - MICROSECOND);
296            scenario.Check(peer, {}, 0, 1, 0, "s7");
297            scenario.AdvanceTime(MICROSECOND);
298            scenario.Check(peer, {}, 0, 0, 0, "s8");
299            scenario.CheckExpired(peer, gtxid);
300            return;
301        } else {
302            scenario.AdvanceTime(std::chrono::microseconds{m_rng.randrange(expiry.count())});
303            scenario.Check(peer, {}, 0, 1, 0, "s9");
304            if ((config >> 3) == 3) { // A response will arrive for the transaction
305                scenario.ReceivedResponse(peer, gtxid.ToUint256());
306                scenario.Check(peer, {}, 0, 0, 0, "s10");
307                return;
308            }
309        }
310    }
311
312    if (config & 4) { // The peer will go offline
313        scenario.DisconnectedPeer(peer);
314    } else { // The transaction is no longer needed
315        scenario.ForgetTxHash(gtxid.ToUint256());
316    }
317    scenario.Check(peer, {}, 0, 0, 0, "s11");
318}
319
320/** Add to scenario a test with a single tx announced by two peers, to verify the
321 *  right peer is selected for requests.
322 *
323 * config is an integer in [0, 32), which controls which variant of the test is used.
324 */
325void TxRequestTest::BuildPriorityTest(Scenario& scenario, int config)
326{
327    scenario.SetTestName(strprintf("Priority(config=%i)", config));
328
329    // Two peers. They will announce in order {peer1, peer2}.
330    auto peer1 = scenario.NewPeer(), peer2 = scenario.NewPeer();
331    // Construct a transaction that under random rules would be preferred by peer2 or peer1,
332    // depending on configuration.
333    bool prio1 = config & 1;
334    auto gtxid = prio1 ? scenario.NewGTxid({{peer1, peer2}}) : scenario.NewGTxid({{peer2, peer1}});
335    bool pref1 = config & 2, pref2 = config & 4;
336
337    scenario.ReceivedInv(peer1, gtxid, pref1, MIN_TIME);
338    scenario.Check(peer1, {gtxid}, 1, 0, 0, "p1");
339    if (m_rng.randbool()) {
340        scenario.AdvanceTime(RandomTime8s());
341        scenario.Check(peer1, {gtxid}, 1, 0, 0, "p2");
342    }
343
344    scenario.ReceivedInv(peer2, gtxid, pref2, MIN_TIME);
345    bool stage2_prio =
346        // At this point, peer2 will be given priority if:
347        // - It is preferred and peer1 is not
348        (pref2 && !pref1) ||
349        // - They're in the same preference class,
350        //   and the randomized priority favors peer2 over peer1.
351        (pref1 == pref2 && !prio1);
352    NodeId priopeer = stage2_prio ? peer2 : peer1, otherpeer = stage2_prio ? peer1 : peer2;
353    scenario.Check(otherpeer, {}, 1, 0, 0, "p3");
354    scenario.Check(priopeer, {gtxid}, 1, 0, 0, "p4");
355    if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
356    scenario.Check(otherpeer, {}, 1, 0, 0, "p5");
357    scenario.Check(priopeer, {gtxid}, 1, 0, 0, "p6");
358
359    // We possibly request from the selected peer.
360    if (config & 8) {
361        scenario.RequestedTx(priopeer, gtxid.ToUint256(), MAX_TIME);
362        scenario.Check(priopeer, {}, 0, 1, 0, "p7");
363        scenario.Check(otherpeer, {}, 1, 0, 0, "p8");
364        if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
365    }
366
367    // The peer which was selected (or requested from) now goes offline, or a NOTFOUND is received from them.
368    if (config & 16) {
369        scenario.DisconnectedPeer(priopeer);
370    } else {
371        scenario.ReceivedResponse(priopeer, gtxid.ToUint256());
372    }
373    if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
374    scenario.Check(priopeer, {}, 0, 0, !(config & 16), "p8");
375    scenario.Check(otherpeer, {gtxid}, 1, 0, 0, "p9");
376    if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
377
378    // Now the other peer goes offline.
379    scenario.DisconnectedPeer(otherpeer);
380    if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
381    scenario.Check(peer1, {}, 0, 0, 0, "p10");
382    scenario.Check(peer2, {}, 0, 0, 0, "p11");
383}
384
385/** Add to scenario a randomized test in which N peers announce the same transaction, to verify
386 *  the order in which they are requested. */
387void TxRequestTest::BuildBigPriorityTest(Scenario& scenario, int peers)
388{
389    scenario.SetTestName(strprintf("BigPriority(peers=%i)", peers));
390
391    // We will have N peers announce the same transaction.
392    std::map<NodeId, bool> preferred;
393    std::vector<NodeId> pref_peers, npref_peers;
394    int num_pref = m_rng.randrange(peers + 1) ; // Some preferred, ...
395    int num_npref = peers - num_pref; // some not preferred.
396    for (int i = 0; i < num_pref; ++i) {
397        pref_peers.push_back(scenario.NewPeer());
398        preferred[pref_peers.back()] = true;
399    }
400    for (int i = 0; i < num_npref; ++i) {
401        npref_peers.push_back(scenario.NewPeer());
402        preferred[npref_peers.back()] = false;
403    }
404    // Make a list of all peers, in order of intended request order (concatenation of pref_peers and npref_peers).
405    std::vector<NodeId> request_order;
406    request_order.reserve(num_pref + num_npref);
407    for (int i = 0; i < num_pref; ++i) request_order.push_back(pref_peers[i]);
408    for (int i = 0; i < num_npref; ++i) request_order.push_back(npref_peers[i]);
409
410    // Determine the announcement order randomly.
411    std::vector<NodeId> announce_order = request_order;
412    std::shuffle(announce_order.begin(), announce_order.end(), m_rng);
413
414    // Find a gtxid whose txhash prioritization is consistent with the required ordering within pref_peers and
415    // within npref_peers.
416    auto gtxid = scenario.NewGTxid({pref_peers, npref_peers});
417
418    // Decide reqtimes in opposite order of the expected request order. This means that as time passes we expect the
419    // to-be-requested-from-peer will change every time a subsequent reqtime is passed.
420    std::map<NodeId, std::chrono::microseconds> reqtimes;
421    auto reqtime = scenario.Now();
422    for (int i = peers - 1; i >= 0; --i) {
423        reqtime += RandomTime8s();
424        reqtimes[request_order[i]] = reqtime;
425    }
426
427    // Actually announce from all peers simultaneously (but in announce_order).
428    for (const auto peer : announce_order) {
429        scenario.ReceivedInv(peer, gtxid, preferred[peer], reqtimes[peer]);
430    }
431    for (const auto peer : announce_order) {
432        scenario.Check(peer, {}, 1, 0, 0, "b1");
433    }
434
435    // Let time pass and observe the to-be-requested-from peer change, from nonpreferred to preferred, and from
436    // high priority to low priority within each class.
437    for (int i = peers - 1; i >= 0; --i) {
438        scenario.AdvanceTime(reqtimes[request_order[i]] - scenario.Now() - MICROSECOND);
439        scenario.Check(request_order[i], {}, 1, 0, 0, "b2");
440        scenario.AdvanceTime(MICROSECOND);
441        scenario.Check(request_order[i], {gtxid}, 1, 0, 0, "b3");
442    }
443
444    // Peers now in random order go offline, or send NOTFOUNDs. At every point in time the new to-be-requested-from
445    // peer should be the best remaining one, so verify this after every response.
446    for (int i = 0; i < peers; ++i) {
447        if (m_rng.randbool()) scenario.AdvanceTime(RandomTime8s());
448        const int pos = m_rng.randrange(request_order.size());
449        const auto peer = request_order[pos];
450        request_order.erase(request_order.begin() + pos);
451        if (m_rng.randbool()) {
452            scenario.DisconnectedPeer(peer);
453            scenario.Check(peer, {}, 0, 0, 0, "b4");
454        } else {
455            scenario.ReceivedResponse(peer, gtxid.ToUint256());
456            scenario.Check(peer, {}, 0, 0, request_order.size() > 0, "b5");
457        }
458        if (request_order.size()) {
459            scenario.Check(request_order[0], {gtxid}, 1, 0, 0, "b6");
460        }
461    }
462
463    // Everything is gone in the end.
464    for (const auto peer : announce_order) {
465        scenario.Check(peer, {}, 0, 0, 0, "b7");
466    }
467}
468
469/** Add to scenario a test with one peer announcing two transactions, to verify they are
470 *  fetched in announcement order.
471 *
472 *  config is an integer in [0, 4) inclusive, and selects the variant of the test.
473 */
474void TxRequestTest::BuildRequestOrderTest(Scenario& scenario, int config)
475{
476    scenario.SetTestName(strprintf("RequestOrder(config=%i)", config));
477
478    auto peer = scenario.NewPeer();
479    auto gtxid1 = scenario.NewGTxid();
480    auto gtxid2 = scenario.NewGTxid();
481
482    auto reqtime2 = scenario.Now() + RandomTime8s();
483    auto reqtime1 = reqtime2 + RandomTime8s();
484
485    scenario.ReceivedInv(peer, gtxid1, config & 1, reqtime1);
486    // Simulate time going backwards by giving the second announcement an earlier reqtime.
487    scenario.ReceivedInv(peer, gtxid2, config & 2, reqtime2);
488
489    scenario.AdvanceTime(reqtime2 - MICROSECOND - scenario.Now());
490    scenario.Check(peer, {}, 2, 0, 0, "o1");
491    scenario.AdvanceTime(MICROSECOND);
492    scenario.Check(peer, {gtxid2}, 2, 0, 0, "o2");
493    scenario.AdvanceTime(reqtime1 - MICROSECOND - scenario.Now());
494    scenario.Check(peer, {gtxid2}, 2, 0, 0, "o3");
495    scenario.AdvanceTime(MICROSECOND);
496    // Even with time going backwards in between announcements, the return value of GetRequestable is in
497    // announcement order.
498    scenario.Check(peer, {gtxid1, gtxid2}, 2, 0, 0, "o4");
499
500    scenario.DisconnectedPeer(peer);