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