Replace setInventoryKnown with a rolling bloom filter.

gmaxwell · sipa · commit ec73ef37eccf · 2015-11-30T12:53:48.000+01:00
Mruset setInventoryKnown was reduced to a remarkably small 1000
 entries as a side effect of sendbuffer size reductions in 2012.

This removes setInventoryKnown filtering from merkleBlock responses
 because false positives there are especially unattractive and
 also because I'm not sure if there aren't race conditions around
 the relay pool that would cause some transactions there to
 be suppressed. (Also, ProcessGetData was accessing
 setInventoryKnown without taking the required lock.)
diff --git a/src/main.cpp b/src/main.cpp
@@ -4138,8 +4138,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
@@ -5511,7 +5510,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 (pto->setInventoryKnown.contains(inv.hash))
                     continue;
 
                 // trickle out tx inv to protect privacy
@@ -5532,9 +5531,9 @@ bool SendMessages(CNode* pto, bool fSendTrickle)
                     }
                 }
 
-                // returns true if wasn't already contained in the set
-                if (pto->setInventoryKnown.insert(inv).second)
+                if (!pto->setInventoryKnown.contains(inv.hash))
                 {
+                    pto->setInventoryKnown.insert(inv.hash);
                     vInv.push_back(inv);
                     if (vInv.size() >= 1000)
                     {
diff --git 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)
+    setInventoryKnown(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;
+    setInventoryKnown.reset();
     fGetAddr = false;
     fRelayTxes = false;
     pfilter = new CBloomFilter();
diff --git a/src/net.h b/src/net.h
@@ -386,7 +386,7 @@ class CNode
     std::set<uint256> setKnown;
 
     // inventory based relay
-    mruset<CInv> setInventoryKnown;
+    CRollingBloomFilter setInventoryKnown;
     std::vector<CInv> vInventoryToSend;
     CCriticalSection cs_inventory;
     std::multimap<int64_t, CInv> mapAskFor;
@@ -494,15 +494,15 @@ class CNode
     {
         {
             LOCK(cs_inventory);
-            setInventoryKnown.insert(inv);
+            setInventoryKnown.insert(inv.hash);
         }
     }
 
     void PushInventory(const CInv& inv)
     {
         {
             LOCK(cs_inventory);
-            if (!setInventoryKnown.count(inv))
+            if (!setInventoryKnown.contains(inv.hash))
                 vInventoryToSend.push_back(inv);
         }
     }

Original file line number	Diff line number	Diff line change
`@@ -4138,8 +4138,7 @@ void static ProcessGetData(CNode* pfrom, const Consensus::Params& consensusParam`
`4138`	`4138`	`// however we MUST always provide at least what the remote peer needs`
`4139`	`4139`	`typedef std::pair<unsigned int, uint256> PairType;`
`4140`	`4140`	`BOOST_FOREACH(PairType& pair, merkleBlock.vMatchedTxn)`
`4141`		`- if (!pfrom->setInventoryKnown.count(CInv(MSG_TX, pair.second)))`
`4142`		`- pfrom->PushMessage("tx", block.vtx[pair.first]);`
	`4141`	`+ pfrom->PushMessage("tx", block.vtx[pair.first]);`
`4143`	`4142`	`}`
`4144`	`4143`	`// else`
`4145`	`4144`	`// no response`
`@@ -5511,7 +5510,7 @@ bool SendMessages(CNode* pto, bool fSendTrickle)`
`5511`	`5510`	`vInvWait.reserve(pto->vInventoryToSend.size());`
`5512`	`5511`	`BOOST_FOREACH(const CInv& inv, pto->vInventoryToSend)`
`5513`	`5512`	`{`
`5514`		`- if (pto->setInventoryKnown.count(inv))`
	`5513`	`+ if (pto->setInventoryKnown.contains(inv.hash))`
`5515`	`5514`	`continue;`
`5516`	`5515`
`5517`	`5516`	`// trickle out tx inv to protect privacy`
`@@ -5532,9 +5531,9 @@ bool SendMessages(CNode* pto, bool fSendTrickle)`
`5532`	`5531`	`}`
`5533`	`5532`	`}`
`5534`	`5533`
`5535`		`- // returns true if wasn't already contained in the set`
`5536`		`- if (pto->setInventoryKnown.insert(inv).second)`
	`5534`	`+ if (!pto->setInventoryKnown.contains(inv.hash))`
`5537`	`5535`	`{`
	`5536`	`+ pto->setInventoryKnown.insert(inv.hash);`
`5538`	`5537`	`vInv.push_back(inv);`
`5539`	`5538`	`if (vInv.size() >= 1000)`
`5540`	`5539`	`{`
Original file line number	Diff line number	Diff line change
`@@ -386,7 +386,7 @@ class CNode`
`386`	`386`	`std::set<uint256> setKnown;`
`387`	`387`
`388`	`388`	`// inventory based relay`
`389`		`- mruset<CInv> setInventoryKnown;`
	`389`	`+ CRollingBloomFilter setInventoryKnown;`
`390`	`390`	`std::vector<CInv> vInventoryToSend;`
`391`	`391`	`CCriticalSection cs_inventory;`
`392`	`392`	`std::multimap<int64_t, CInv> mapAskFor;`
`@@ -494,15 +494,15 @@ class CNode`
`494`	`494`	`{`
`495`	`495`	`{`
`496`	`496`	`LOCK(cs_inventory);`
`497`		`- setInventoryKnown.insert(inv);`
	`497`	`+ setInventoryKnown.insert(inv.hash);`
`498`	`498`	`}`
`499`	`499`	`}`
`500`	`500`
`501`	`501`	`void PushInventory(const CInv& inv)`
`502`	`502`	`{`
`503`	`503`	`{`
`504`	`504`	`LOCK(cs_inventory);`
`505`		`- if (!setInventoryKnown.count(inv))`
	`505`	`+ if (!setInventoryKnown.contains(inv.hash))`
`506`	`506`	`vInventoryToSend.push_back(inv);`
`507`	`507`	`}`
`508`	`508`	`}`