Some simple improvements to the RNG code

sipa commented at 10:57 pm on October 31, 2018: member

This improves a few minor issues with the RNG code:

Avoid calling GetRand*() functions (which currently invoke OpenSSL, later may switch to using our own RNG pool) inside loops in addrman, networking code, KnapsackSolver, and LimitOrphanSize
Fix a currently unreachable bug in FastRandomContext::randbytes.
Make a number of simplifications to the unit tests’ randomness code (some tests unnecessarily used their own RNG or the OpenSSL one, instead of using the unit test specific insecure_rand_ctx).
As a precaution, make it illegal to copy a FastRandomContext.

fanquake added the label Refactoring on Oct 31, 2018

DrahtBot commented at 11:38 pm on October 31, 2018: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#14626 (Select orphan transaction uniformly for eviction by sipa)
#14605 (Return of the Banman by dongcarl)
#13462 (Simplify common case of CHashWriter and drop SerializeHash by Empact)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

sipa force-pushed on Nov 1, 2018

in src/test/random_tests.cpp:43 in 5b7f385597 outdated

39@@ -40,9 +40,9 @@ BOOST_AUTO_TEST_CASE(fastrandom_tests)
40     // Check that a nondeterministic ones are not
41     FastRandomContext ctx3;
42     FastRandomContext ctx4;
43+    BOOST_CHECK(ctx3.randbytes(7) != ctx4.randbytes(7));

practicalswift commented at 9:58 am on November 1, 2018:

Should the randbytes, rand256 and rand256 tests each get their own pair of FastRandomContext:s to properly test for non-determinism? That way the ordering of the test won’t matter.

sipa commented at 5:18 pm on November 1, 2018:

Good idea, done.

practicalswift commented at 10:00 am on November 1, 2018: contributor

Concept ACK @sipa Regarding randbytes – very nice find! How was that issue found?

practicalswift commented at 10:12 am on November 1, 2018: contributor

This also works around a bug in libstdc++ std::shuffle that may cause type::operator=(type&&) to be invoked on itself, which the library’s debug mode detects and panics on.

How did you trigger this? I’ve built with -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC in the past and haven’t encountered this. I also tried now and I was unable to reproduce.

Assuming a build with -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC – would the issue be triggered by make check or running the test suite?

I’m running:

0$ g++ --version
1g++ (Ubuntu 7.3.0-16ubuntu3) 7.3.0
2$ dpkg -l | grep libstd
3ii  libstdc++-7-dev:amd64                                       7.3.0-16ubuntu3                   amd64        GNU Standard C++ Library v3 (development files)
4ii  libstdc++6:amd64                                            8-20180414-1ubuntu2               amd64        GNU Standard C++ Library v3

MarcoFalke commented at 2:00 pm on November 1, 2018: member

Travis failure:

 0/bin/bash: line 1: 27706 Aborted                 (core dumped) test/test_bitcoin -l test_suite -t "`cat wallet/test/coinselector_tests.cpp | grep -E "(BOOST_FIXTURE_TEST_SUITE\\(|BOOST_AUTO_TEST_SUITE\\()" | cut -d '(' -f 2 | cut -d ',' -f 1 | cut -d ')' -f 1`" > wallet/test/coinselector_tests.cpp.log 2>&1
 1Running 4 test cases...
 2Test cases order is shuffled using seed: 1449235911
 3Entering test module "Bitcoin Test Suite"
 4wallet/test/coinselector_tests.cpp(17): Entering test suite "coinselector_tests"
 5wallet/test/coinselector_tests.cpp(569): Entering test case "SelectCoins_test"
 6wallet/test/coinselector_tests.cpp(569): Leaving test case "SelectCoins_test"; testing time: 3726243us
 7wallet/test/coinselector_tests.cpp(267): Entering test case "knapsack_solver_test"
 8/usr/include/c++/7/debug/safe_iterator.h:374:
 9Error: attempt to advance a past-the-end iterator 1 steps, which falls 
10outside its valid range.
11Objects involved in the operation:
12    iterator @ 0x0x7fff06875e20 {
13      type = __gnu_debug::_Safe_iterator<__gnu_cxx::__normal_iterator<OutputGroup*, std::__cxx1998::vector<OutputGroup, std::allocator<OutputGroup> > >, std::__debug::vector<OutputGroup, std::allocator<OutputGroup> > > (mutable iterator);
14      state = past-the-end;
15      references sequence with type 'std::__debug::vector<OutputGroup, std::allocator<OutputGroup> >' @ 0x0x7fff068766e0
16    }
17unknown location(0): fatal error: in "coinselector_tests/knapsack_solver_test": signal: SIGABRT (application abort requested)
18wallet/test/coinselector_tests.cpp(281): last checkpoint
19wallet/test/coinselector_tests.cpp(267): Leaving test case "knapsack_solver_test"; testing time: 78734us
20wallet/test/coinselector_tests.cpp(122): Entering test case "bnb_search_test"
21test_bitcoin: key.cpp:344: void ECC_Start(): Assertion `secp256k1_context_sign == nullptr' failed.
22unknown location(0): fatal error: in "coinselector_tests/bnb_search_test": signal: SIGABRT (application abort requested)
23wallet/test/coinselector_tests.cpp(122): last checkpoint: "bnb_search_test" fixture entry.
24wallet/test/coinselector_tests.cpp(122): Leaving test case "bnb_search_test"; testing time: 271us
25wallet/test/coinselector_tests.cpp(546): Entering test case "ApproximateBestSubset"
26test_bitcoin: key.cpp:344: void ECC_Start(): Assertion `secp256k1_context_sign == nullptr' failed.
27unknown location(0): fatal error: in "coinselector_tests/ApproximateBestSubset": signal: SIGABRT (application abort requested)
28wallet/test/coinselector_tests.cpp(546): last checkpoint: "ApproximateBestSubset" fixture entry.
29wallet/test/coinselector_tests.cpp(546): Leaving test case "ApproximateBestSubset"; testing time: 158us
30wallet/test/coinselector_tests.cpp(17): Leaving test suite "coinselector_tests"; testing time: 3805580us
31Leaving test module "Bitcoin Test Suite"; testing time: 3805777us
32*** 3 failures are detected in the test module "Bitcoin Test Suite"

sipa force-pushed on Nov 1, 2018

sipa commented at 5:18 pm on November 1, 2018: member

@practicalswift

@sipa Regarding randbytes – very nice find! How was that issue found?

In a follow-up change I was working on, which replaced more use sites of GetRand* functions with FastRandomContexts. One unit test failed which tested that the leveldb obfuscation key was not all zeroes…

How did you trigger this? I’ve built with -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC in the past and haven’t encountered this. I also tried now and I was unable to reproduce.

Assuming a build with -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC – would the issue be triggered by make check or running the test suite?

Travis failed in an earlier version of this PR, in the Qt (!) unit tests. @MarcoFalke

Travis failure:

Fixed now.

in src/random.cpp:467 in 66e69f2e93 outdated

463@@ -463,6 +464,19 @@ FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDete
464     rng.SetKey(seed.begin(), 32);
465 }
466 
467+FastRandomContext& FastRandomContext::operator=(FastRandomContext&& from)

practicalswift commented at 7:17 am on November 2, 2018:

Mark noexcept? Rationale: “A throwing move violates most people’s reasonably assumptions. A non-throwing move will be used more efficiently by standard-library and language facilities.”

sipa commented at 8:47 pm on November 9, 2018:

Done.

in src/addrman.cpp:533 in 66e69f2e93 outdated

529@@ -530,8 +530,8 @@ void CAddrMan::SetServices_(const CService& addr, ServiceFlags nServices)
530     info.nServices = nServices;
531 }
532 
533-int CAddrMan::RandomInt(int nMax){
534-    return GetRandInt(nMax);
535+int CAddrMan::RandomInt(int max){

practicalswift commented at 7:18 am on November 2, 2018:

Use nMax to match declaration, or change declaration to max.

Nit: Add space before { :-)

sipa commented at 0:15 am on November 10, 2018:

Done, done.

sipa force-pushed on Nov 9, 2018

sipa force-pushed on Nov 10, 2018

gmaxwell commented at 9:39 pm on November 10, 2018: contributor

Concept ACK

in src/addrman.h:270 in 0d8797b1c7 outdated

265@@ -266,8 +266,8 @@ class CAddrMan
266     //! Return a random to-be-evicted tried table address.
267     CAddrInfo SelectTriedCollision_() EXCLUSIVE_LOCKS_REQUIRED(cs);
268 
269-    //! Wraps GetRandInt to allow tests to override RandomInt and make it determinismistic.
270-    virtual int RandomInt(int nMax);
271+    //! Shorthand for insecure_rand.randrange()
272+    int RandomInt(int range);

pstratem commented at 4:49 pm on November 14, 2018:

Is it really worth having the wrapper function if it’s not a test harness?

sipa commented at 8:22 pm on November 14, 2018:

Good point. Got rid of it entirely.

in src/random.cpp:467 in 8a652f5586 outdated

463@@ -464,6 +464,20 @@ FastRandomContext::FastRandomContext(bool fDeterministic) : requires_seed(!fDete
464     rng.SetKey(seed.begin(), 32);
465 }
466 
467+FastRandomContext& FastRandomContext::operator=(FastRandomContext&& from) noexcept

pstratem commented at 6:01 pm on November 14, 2018:

So this is copying, but setting the original context to reseed?

sipa commented at 8:24 pm on November 14, 2018:

Indeed, as documented in the .h file (the state of a moved-from object must be valid but may be unspecified, as it’s not supposed to be used again; choosing to set it to reseed is both fast and safe).

in src/random.h:157 in 9f92a5551a outdated

144+void Shuffle(I first, I last, R&& rng)
145+{
146+    while (first != last) {
147+        size_t j = rng.randrange(last - first);
148+        if (j) {
149+            using std::swap;

pstratem commented at 7:00 pm on November 14, 2018:

but why the using?

sipa commented at 8:25 pm on November 14, 2018:

That’s the suggested idiom, as it brings std::swap into scope, but also has access to possible user-defined swap implementations outside of std.

pstratem changes_requested

sipa force-pushed on Nov 14, 2018

in src/addrman.h:473 in f997e29a24 outdated

469@@ -473,7 +470,7 @@ class CAddrMan
470     {
471         LOCK(cs);
472         std::vector<int>().swap(vRandom);
473-        nKey = GetRandHash();
474+        nKey = insecure_rand.rand256();

MarcoFalke commented at 7:48 pm on November 16, 2018:

nit: Might as well rename it to m_insecure_rand, since it is only used in two places previously.

gmaxwell commented at 7:29 pm on November 21, 2018: contributor

utACK

sipa commented at 6:27 pm on November 30, 2018: member

Rebased.

sipa force-pushed on Nov 30, 2018

MarcoFalke commented at 9:06 pm on November 30, 2018: member

Looks like the unit tests don’t pass with the thread sanitizer enabled

DrahtBot added the label Needs rebase on Dec 12, 2018

Make addrman use its local RNG exclusively 9695f31d75

Use a local FastRandomContext in a few more places in net 8098379be5

Introduce a Shuffle for FastRandomContext and use it in wallet and coinselection 3db746beb4

Use a FastRandomContext in LimitOrphanTxSize 273d02580a

Bugfix: randbytes should seed when needed (non reachable issue) 8d98d42611

Make unit tests use the insecure_rand_ctx exclusively fd3e7973ff

Simplify testing RNG code 022cf47dd7

Do not permit copying FastRandomContexts e414486d56

sipa force-pushed on Dec 12, 2018

sipa commented at 10:32 pm on December 12, 2018: member

Rebased.

DrahtBot removed the label Needs rebase on Dec 12, 2018

laanwj commented at 12:58 pm on December 13, 2018: member

all straightforward changes utACK e414486d56b9f06af7aeb07ce13e3c3780c2b69b

laanwj added the label Utils/log/libs on Dec 13, 2018

laanwj merged this on Dec 13, 2018

laanwj closed this on Dec 13, 2018

laanwj referenced this in commit 378fdfabba on Dec 13, 2018

PastaPastaPasta referenced this in commit 4f38f5c2ef on Jan 14, 2021

random-zebra referenced this in commit 93f43f0f81 on Apr 14, 2021

kittywhiskers referenced this in commit d21ef7cb06 on Jul 2, 2021

kittywhiskers referenced this in commit 29a3d5b43e on Jul 2, 2021

kittywhiskers referenced this in commit 2b6e2d7a2a on Jul 2, 2021

kittywhiskers referenced this in commit cce296678a on Jul 4, 2021

kittywhiskers referenced this in commit 2614264ceb on Jul 9, 2021

kittywhiskers referenced this in commit b3dba89364 on Jul 9, 2021

kittywhiskers referenced this in commit 7dd3e9a1ee on Jul 15, 2021

kittywhiskers referenced this in commit 0892afd07c on Jul 16, 2021

PastaPastaPasta referenced this in commit b5eb262ad4 on Jul 19, 2021

PastaPastaPasta referenced this in commit 9009f57e27 on Jul 20, 2021

MarcoFalke locked this on Sep 8, 2021

Some simple improvements to the RNG code #14624

Conflicts