From f31955d9da152e5e849575f0297f8fe1904cbfbc Mon Sep 17 00:00:00 2001 From: Gregory Maxwell Date: Thu, 26 Nov 2015 05:25:30 +0000 Subject: Replace setInventoryKnown with a rolling bloom filter. Github-Pull: #7133 Rebased-From: ec73ef37eccfeda76de55c4ff93ea54d4e69e1ec e20672479ef7f2048c2e27494397641d47a4d88d 6b849350ab074a7ccb80ecbef387f59e1271ded6 b6a0da45db8d534e7a77d1cebe382cd5d83ba9b8 d41e44c9accb3df84e0abbc602cc76b72754d382 aa4b0c26b0a94ca6164c441aae723e118554d214 --- qa/rpc-tests/sendheaders.py | 2 +- src/Makefile.am | 1 - src/Makefile.test.include | 1 - src/main.cpp | 19 +++++------ src/mruset.h | 65 ------------------------------------ src/net.cpp | 3 +- src/net.h | 10 +++--- src/test/mruset_tests.cpp | 81 --------------------------------------------- 8 files changed, 16 insertions(+), 166 deletions(-) delete mode 100644 src/mruset.h delete mode 100644 src/test/mruset_tests.cpp diff --git a/qa/rpc-tests/sendheaders.py b/qa/rpc-tests/sendheaders.py index d7f4292090..63e071805a 100755 --- a/qa/rpc-tests/sendheaders.py +++ b/qa/rpc-tests/sendheaders.py @@ -389,7 +389,7 @@ class SendHeadersTest(BitcoinTestFramework): # Use getblocks/getdata test_node.send_getblocks(locator = [fork_point]) - assert_equal(test_node.check_last_announcement(inv=new_block_hashes[0:-1]), True) + assert_equal(test_node.check_last_announcement(inv=new_block_hashes), True) test_node.get_data(new_block_hashes) test_node.wait_for_block(new_block_hashes[-1]) diff --git a/src/Makefile.am b/src/Makefile.am index bb627a5448..5da1a873de 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -117,7 +117,6 @@ BITCOIN_CORE_H = \ memusage.h \ merkleblock.h \ miner.h \ - mruset.h \ net.h \ netbase.h \ noui.h \ diff --git a/src/Makefile.test.include b/src/Makefile.test.include index 4d0894b711..d89132f806 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -59,7 +59,6 @@ BITCOIN_TESTS =\ test/mempool_tests.cpp \ test/merkle_tests.cpp \ test/miner_tests.cpp \ - test/mruset_tests.cpp \ test/multisig_tests.cpp \ test/netbase_tests.cpp \ test/pmt_tests.cpp \ diff --git a/src/main.cpp b/src/main.cpp index b200109a6a..f7b9d073ed 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -4187,8 +4187,7 @@ void static ProcessGetData(CNode* pfrom, const Consensus::Params& consensusParam // however we MUST always provide at least what the remote peer needs typedef std::pair PairType; BOOST_FOREACH(PairType& pair, merkleBlock.vMatchedTxn) - if (!pfrom->setInventoryKnown.count(CInv(MSG_TX, pair.second))) - pfrom->PushMessage("tx", block.vtx[pair.first]); + pfrom->PushMessage("tx", block.vtx[pair.first]); } // else // no response @@ -5568,7 +5567,7 @@ bool SendMessages(CNode* pto, bool fSendTrickle) vInvWait.reserve(pto->vInventoryToSend.size()); BOOST_FOREACH(const CInv& inv, pto->vInventoryToSend) { - if (pto->setInventoryKnown.count(inv)) + if (inv.type == MSG_TX && pto->filterInventoryKnown.contains(inv.hash)) continue; // trickle out tx inv to protect privacy @@ -5589,15 +5588,13 @@ bool SendMessages(CNode* pto, bool fSendTrickle) } } - // returns true if wasn't already contained in the set - if (pto->setInventoryKnown.insert(inv).second) + pto->filterInventoryKnown.insert(inv.hash); + + vInv.push_back(inv); + if (vInv.size() >= 1000) { - vInv.push_back(inv); - if (vInv.size() >= 1000) - { - pto->PushMessage("inv", vInv); - vInv.clear(); - } + pto->PushMessage("inv", vInv); + vInv.clear(); } } pto->vInventoryToSend = vInvWait; diff --git a/src/mruset.h b/src/mruset.h deleted file mode 100644 index 398aa173bf..0000000000 --- a/src/mruset.h +++ /dev/null @@ -1,65 +0,0 @@ -// Copyright (c) 2012-2015 The Bitcoin Core developers -// Distributed under the MIT software license, see the accompanying -// file COPYING or http://www.opensource.org/licenses/mit-license.php. - -#ifndef BITCOIN_MRUSET_H -#define BITCOIN_MRUSET_H - -#include -#include -#include - -/** STL-like set container that only keeps the most recent N elements. */ -template -class mruset -{ -public: - typedef T key_type; - typedef T value_type; - typedef typename std::set::iterator iterator; - typedef typename std::set::const_iterator const_iterator; - typedef typename std::set::size_type size_type; - -protected: - std::set set; - std::vector order; - size_type first_used; - size_type first_unused; - const size_type nMaxSize; - -public: - mruset(size_type nMaxSizeIn = 1) : nMaxSize(nMaxSizeIn) { clear(); } - iterator begin() const { return set.begin(); } - iterator end() const { return set.end(); } - size_type size() const { return set.size(); } - bool empty() const { return set.empty(); } - iterator find(const key_type& k) const { return set.find(k); } - size_type count(const key_type& k) const { return set.count(k); } - void clear() - { - set.clear(); - order.assign(nMaxSize, set.end()); - first_used = 0; - first_unused = 0; - } - bool inline friend operator==(const mruset& a, const mruset& b) { return a.set == b.set; } - bool inline friend operator==(const mruset& a, const std::set& b) { return a.set == b; } - bool inline friend operator<(const mruset& a, const mruset& b) { return a.set < b.set; } - std::pair insert(const key_type& x) - { - std::pair ret = set.insert(x); - if (ret.second) { - if (set.size() == nMaxSize + 1) { - set.erase(order[first_used]); - order[first_used] = set.end(); - if (++first_used == nMaxSize) first_used = 0; - } - order[first_unused] = ret.first; - if (++first_unused == nMaxSize) first_unused = 0; - } - return ret; - } - size_type max_size() const { return nMaxSize; } -}; - -#endif // BITCOIN_MRUSET_H diff --git a/src/net.cpp b/src/net.cpp index e5659efc01..a8aa97feec 100644 --- a/src/net.cpp +++ b/src/net.cpp @@ -2342,7 +2342,7 @@ unsigned int SendBufferSize() { return 1000*GetArg("-maxsendbuffer", DEFAULT_MAX CNode::CNode(SOCKET hSocketIn, const CAddress& addrIn, const std::string& addrNameIn, bool fInboundIn) : ssSend(SER_NETWORK, INIT_PROTO_VERSION), addrKnown(5000, 0.001), - setInventoryKnown(SendBufferSize() / 1000) + filterInventoryKnown(50000, 0.000001) { nServices = 0; hSocket = hSocketIn; @@ -2369,6 +2369,7 @@ CNode::CNode(SOCKET hSocketIn, const CAddress& addrIn, const std::string& addrNa nSendOffset = 0; hashContinue = uint256(); nStartingHeight = -1; + filterInventoryKnown.reset(); fGetAddr = false; fRelayTxes = false; pfilter = new CBloomFilter(); diff --git a/src/net.h b/src/net.h index a5a5c770d6..6886d070bf 100644 --- a/src/net.h +++ b/src/net.h @@ -9,7 +9,6 @@ #include "bloom.h" #include "compat.h" #include "limitedmap.h" -#include "mruset.h" #include "netbase.h" #include "protocol.h" #include "random.h" @@ -388,7 +387,7 @@ public: std::set setKnown; // inventory based relay - mruset setInventoryKnown; + CRollingBloomFilter filterInventoryKnown; std::vector vInventoryToSend; CCriticalSection cs_inventory; std::set setAskFor; @@ -497,7 +496,7 @@ public: { { LOCK(cs_inventory); - setInventoryKnown.insert(inv); + filterInventoryKnown.insert(inv.hash); } } @@ -505,8 +504,9 @@ public: { { LOCK(cs_inventory); - if (!setInventoryKnown.count(inv)) - vInventoryToSend.push_back(inv); + if (inv.type == MSG_TX && filterInventoryKnown.contains(inv.hash)) + return; + vInventoryToSend.push_back(inv); } } diff --git a/src/test/mruset_tests.cpp b/src/test/mruset_tests.cpp deleted file mode 100644 index 2b68f8899e..0000000000 --- a/src/test/mruset_tests.cpp +++ /dev/null @@ -1,81 +0,0 @@ -// Copyright (c) 2012-2013 The Bitcoin Core developers -// Distributed under the MIT software license, see the accompanying -// file COPYING or http://www.opensource.org/licenses/mit-license.php. - -#include "mruset.h" - -#include "random.h" -#include "util.h" -#include "test/test_bitcoin.h" - -#include - -#include - -#define NUM_TESTS 16 -#define MAX_SIZE 100 - -using namespace std; - -BOOST_FIXTURE_TEST_SUITE(mruset_tests, BasicTestingSetup) - -BOOST_AUTO_TEST_CASE(mruset_test) -{ - // The mruset being tested. - mruset mru(5000); - - // Run the test 10 times. - for (int test = 0; test < 10; test++) { - // Reset mru. - mru.clear(); - - // A deque + set to simulate the mruset. - std::deque rep; - std::set all; - - // Insert 10000 random integers below 15000. - for (int j=0; j<10000; j++) { - int add = GetRandInt(15000); - mru.insert(add); - - // Add the number to rep/all as well. - if (all.count(add) == 0) { - all.insert(add); - rep.push_back(add); - if (all.size() == 5001) { - all.erase(rep.front()); - rep.pop_front(); - } - } - - // Do a full comparison between mru and the simulated mru every 1000 and every 5001 elements. - if (j % 1000 == 0 || j % 5001 == 0) { - mruset mru2 = mru; // Also try making a copy - - // Check that all elements that should be in there, are in there. - BOOST_FOREACH(int x, rep) { - BOOST_CHECK(mru.count(x)); - BOOST_CHECK(mru2.count(x)); - } - - // Check that all elements that are in there, should be in there. - BOOST_FOREACH(int x, mru) { - BOOST_CHECK(all.count(x)); - } - - // Check that all elements that are in there, should be in there. - BOOST_FOREACH(int x, mru2) { - BOOST_CHECK(all.count(x)); - } - - for (int t = 0; t < 10; t++) { - int r = GetRandInt(15000); - BOOST_CHECK(all.count(r) == mru.count(r)); - BOOST_CHECK(all.count(r) == mru2.count(r)); - } - } - } - } -} - -BOOST_AUTO_TEST_SUITE_END() -- cgit v1.2.3