Replace setInventoryKnown with a rolling bloom filter.

Github-Pull: #7133
Rebased-From: ec73ef37eccfeda76de55c4ff93ea54d4e69e1ec e20672479ef7f2048c2e27494397641d47a4d88d 6b849350ab074a7ccb80ecbef387f59e1271ded6 b6a0da45db8d534e7a77d1cebe382cd5d83ba9b8 d41e44c9accb3df84e0abbc602cc76b72754d382 aa4b0c26b0a94ca6164c441aae723e118554d214

7 files changed, 15 insertions, 165 deletions

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<unsigned int, uint256> 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 <set>
-#include <vector>
-#include <utility>
-
-/** STL-like set container that only keeps the most recent N elements. */
-template <typename T>
-class mruset
-{
-public:
-    typedef T key_type;
-    typedef T value_type;
-    typedef typename std::set<T>::iterator iterator;
-    typedef typename std::set<T>::const_iterator const_iterator;
-    typedef typename std::set<T>::size_type size_type;
-
-protected:
-    std::set<T> set;
-    std::vector<iterator> 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<T>& a, const mruset<T>& b) { return a.set == b.set; }
-    bool inline friend operator==(const mruset<T>& a, const std::set<T>& b) { return a.set == b; }
-    bool inline friend operator<(const mruset<T>& a, const mruset<T>& b) { return a.set < b.set; }
-    std::pair<iterator, bool> insert(const key_type& x)
-    {
-        std::pair<iterator, bool> 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<uint256> setKnown;
 
     // inventory based relay
-    mruset<CInv> setInventoryKnown;
+    CRollingBloomFilter filterInventoryKnown;
     std::vector<CInv> vInventoryToSend;
     CCriticalSection cs_inventory;
     std::set<uint256> 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 <set>
-
-#include <boost/test/unit_test.hpp>
-
-#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<int> 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<int> rep;
-        std::set<int> 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<int> 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()