net: bound orphan blocks and stop asking a peer the same question twice (#70)

Two defects that feed each other. Measured on a 32-core production node:
1287 of 4117 processed blocks arrived with a missing parent, 97 arrived
that the node already had, and 490 transactions arrived whose inputs were
unknown.

mapOrphanBlocks had no ceiling at all. Orphan transactions have had one
since 0.1.0 -- MAX_ORPHAN_TRANSACTIONS with LimitOrphanTx -- and blocks
never did. An orphan block whose parent never turns up stays in memory for
the life of the process, each one holding a whole block, and a peer can
send an unlimited number of them just by inventing the previous-block hash.
LimitOrphanBlocks mirrors the transaction one: random eviction, both maps
kept in step, and the CBlock deleted because mapOrphanBlocks owns it.

Every orphan block also fired a getblocks at the sender, and an inv for a
block already held as an orphan fired another, with no filtering. So a node
missing part of the chain asked the same peer the same question over and
over, and the duplicate answers made more orphans, which asked again.
CNode::PushGetBlocks remembers the last request and drops a repeat -- the
same fix Bitcoin made in e2c2648c1.

One trap found by testing rather than by reading: eviction picks at random
and may pick the block just inserted, so GetOrphanRoot has to be read out
of pblock before LimitOrphanBlocks runs, not after. The first version had
that backwards and would have read freed memory.

Verified with fabricated orphans, four of the seven sharing one
hashPrevBlock so the multimap path is exercised: 7 in, limit(3) leaves 3,
limit(0) leaves 0, both maps in step at every stage, no crash. Then a run
against the live network to 4348 with no scaffolding left behind.

The storm itself was not reproducible on demand -- the network is healthy
today and produced one orphan block in seven minutes -- so there is no
before/after on the metric that motivated this.

4 files changed, 93 insertions, 3 deletions

diff --git a/src/main.cpp b/src/main.cpp
index b147ddd..4bc9c4d 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -293,6 +293,43 @@ void AddOrphanTx(const CDataStream& vMsg)
 // grow this map until the node runs out of memory. Evict at random rather than
 // in map order, so an attacker cannot keep its own orphans resident by
 // choosing hashes that sort low.
+// Drop orphan blocks at random until we are back under the ceiling.
+//
+// Random rather than oldest-first, matching LimitOrphanTx below: there is no
+// arrival order recorded, and an attacker who knew the eviction rule could aim
+// at it. Dropping one costs nothing that matters -- if its parent ever shows
+// up, the block is requested again like any other.
+//
+// Both maps have to be kept in step, and the CBlock itself has to be deleted:
+// mapOrphanBlocks owns it.
+void LimitOrphanBlocks(unsigned int nMaxOrphans)
+{
+    while (mapOrphanBlocks.size() > nMaxOrphans)
+    {
+        uint256 randomhash;
+        for (int i = 0; i < 4; i++)
+            ((uint64*)&randomhash)[i] = GetRand(_UI64_MAX);
+        map<uint256, CBlock*>::iterator it = mapOrphanBlocks.lower_bound(randomhash);
+        if (it == mapOrphanBlocks.end())
+            it = mapOrphanBlocks.begin();
+
+        CBlock* pblock = it->second;
+        uint256 hashPrev = pblock->hashPrevBlock;
+
+        for (multimap<uint256, CBlock*>::iterator mi = mapOrphanBlocksByPrev.lower_bound(hashPrev);
+             mi != mapOrphanBlocksByPrev.upper_bound(hashPrev);)
+        {
+            if (mi->second == pblock)
+                mapOrphanBlocksByPrev.erase(mi++);
+            else
+                ++mi;
+        }
+
+        mapOrphanBlocks.erase(it);
+        delete pblock;
+    }
+}
+
 void LimitOrphanTx(unsigned int nMaxOrphans)
 {
     while (mapOrphanTransactions.size() > nMaxOrphans)
@@ -1468,9 +1505,16 @@ bool ProcessBlock(CNode* pfrom, CBlock* pblock)
         mapOrphanBlocks.insert(make_pair(hash, pblock));
         mapOrphanBlocksByPrev.insert(make_pair(pblock->hashPrevBlock, pblock));
 
+        // Read what we need out of pblock before trimming: eviction picks at
+        // random and is perfectly entitled to pick the block just inserted,
+        // which would leave the GetOrphanRoot call below reading freed memory.
+        uint256 hashOrphanRoot = GetOrphanRoot(pblock);
+
+        LimitOrphanBlocks(MAX_ORPHAN_BLOCKS);
+
         // Ask this guy to fill in what we're missing
         if (pfrom)
-            pfrom->PushMessage("getblocks", CBlockLocator(pindexBest), GetOrphanRoot(pblock));
+            pfrom->PushGetBlocks(pindexBest, hashOrphanRoot);
         return true;
     }
 
@@ -2047,7 +2091,7 @@ bool ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv)
         if (!fAskedForBlocks && !pfrom->fClient)
         {
             fAskedForBlocks = true;
-            pfrom->PushMessage("getblocks", CBlockLocator(pindexBest), uint256(0));
+            pfrom->PushGetBlocks(pindexBest, uint256(0));
         }
 
         // Introduce ourselves and hand over the .btf peers that answered us.
@@ -2110,7 +2154,7 @@ bool ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv)
             if (!fAlreadyHave)
                 pfrom->AskFor(inv);
             else if (inv.type == MSG_BLOCK && mapOrphanBlocks.count(inv.hash))
-                pfrom->PushMessage("getblocks", CBlockLocator(pindexBest), GetOrphanRoot(mapOrphanBlocks[inv.hash]));
+                pfrom->PushGetBlocks(pindexBest, GetOrphanRoot(mapOrphanBlocks[inv.hash]));
         }
     }
 
diff --git a/src/main.h b/src/main.h
index 2d5cb86..3bc1219 100644
--- a/src/main.h
+++ b/src/main.h
@@ -18,6 +18,13 @@ static const unsigned int MAX_SIZE = 0x02000000;
 // Ceiling on transactions held waiting for a parent that has not arrived.
 // They cost a peer nothing to send and are never validated, only stored.
 static const unsigned int MAX_ORPHAN_TRANSACTIONS = 100;
+// Blocks held waiting for a parent that has not arrived. Orphan transactions
+// have had a ceiling since 0.1.0 and orphan blocks never did: one whose parent
+// never turns up stays in memory for the life of the process, and a peer can
+// send an unlimited number of them by inventing the previous-block hash. They
+// are not free either -- each holds a whole block. A production node was
+// seeing 1287 of them against 4117 blocks processed.
+static const unsigned int MAX_ORPHAN_BLOCKS = 200;
 // Signature operations allowed in one block. Size alone does not bound what a
 // block costs to validate: every OP_CHECKSIG is an elliptic-curve verification,
 // so a block within the size limit could still hold millions of them and take
@@ -125,6 +132,8 @@ void PrintBlockTree();
 void AddOrphanTx(const CDataStream& vMsg);
 void EraseOrphanTx(uint256 hash);
 void LimitOrphanTx(unsigned int nMaxOrphans);
+// Same ceiling idea for orphan blocks, which never had one.
+void LimitOrphanBlocks(unsigned int nMaxOrphans);
 // nThreadId is 1..N, only for logging: it makes each miner's lines
 // distinguishable, which the dedup filter would otherwise collapse into one.
 bool BitcoinMiner(int nThreadId = 1);
diff --git a/src/net.cpp b/src/net.cpp
index ac8df82..37c081f 100644
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -181,6 +181,17 @@ bool AnySubscribed(unsigned int nChannel)
     return false;
 }
 
+void CNode::PushGetBlocks(CBlockIndex* pindexBegin, uint256 hashEnd)
+{
+    // Filter out duplicate requests.
+    if (pindexBegin == pindexLastGetBlocksBegin && hashEnd == hashLastGetBlocksEnd)
+        return;
+    pindexLastGetBlocksBegin = pindexBegin;
+    hashLastGetBlocksEnd     = hashEnd;
+
+    PushMessage("getblocks", CBlockLocator(pindexBegin), hashEnd);
+}
+
 bool CNode::IsSubscribed(unsigned int nChannel)
 {
     if (nChannel >= vfSubscribe.size())
diff --git a/src/net.h b/src/net.h
index 831a880..5e828c3 100644
--- a/src/net.h
+++ b/src/net.h
@@ -7,6 +7,9 @@ class CAddress;
 class CInv;
 class CRequestTracker;
 class CNode;
+// Defined in main.h, which is included after this file. Only ever used here as
+// a pointer, so the forward declaration is enough.
+class CBlockIndex;
 
 
 
@@ -533,6 +536,11 @@ public:
     // Last "btfpeers" we accepted from this node, to rate-limit the exchange.
     int64 nLastPexRecv;
 
+    // Last getblocks we sent this peer, so we do not ask the same question
+    // over and over. See CNode::PushGetBlocks.
+    CBlockIndex* pindexLastGetBlocksBegin;
+    uint256      hashLastGetBlocksEnd;
+
     // Liveness. A peer whose network path dies silently -- NAT drops an idle
     // mapping, a relay restarts, a route changes -- never sends FIN, so the
     // socket stays readable-never and the node simply stops hearing from it
@@ -565,6 +573,8 @@ public:
         nRefCount = 0;
         nReleaseTime = 0;
         nLastPexRecv = 0;
+        pindexLastGetBlocksBegin = NULL;
+        hashLastGetBlocksEnd = 0;
         nTimeConnected = GetTime();
         nLastSend = 0;
         nLastRecv = 0;
@@ -717,6 +727,22 @@ public:
 
 
 
+    // Ask this peer to fill in blocks we are missing, but only once per
+    // question.
+    //
+    // Every orphan block fires one of these, and an inv for a block we already
+    // hold as an orphan fires another. A node that is missing part of the
+    // chain therefore asks the same peer the same thing repeatedly: measured
+    // on a production node, 1287 orphan blocks out of 4117 processed, and 97
+    // "already have block" from the answers coming back more than once. The
+    // duplicate answers create more orphans, which fire more requests.
+    //
+    // Remembering the last question asked breaks that loop. Same fix Bitcoin
+    // made in e2c2648c1.
+    // Body lives in net.cpp: it builds a CBlockLocator, which main.h defines,
+    // and main.h is included after this file.
+    void PushGetBlocks(CBlockIndex* pindexBegin, uint256 hashEnd);
+
     void PushMessage(const char* pszCommand)
     {
         try