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