Prepare database format for multi-stage block processing

This commit adds a status field and a transaction counter to the block
indexes.

4 files changed, 197 insertions, 75 deletions

diff --git a/src/db.cpp b/src/db.cpp
index 5ca9ea2c34..e77ddd77e1 100644
--- a/src/db.cpp
+++ b/src/db.cpp
@@ -622,6 +622,9 @@ bool LoadBlockIndex(CChainDB &chaindb)
     {
         CBlockIndex* pindex = item.second;
         pindex->bnChainWork = (pindex->pprev ? pindex->pprev->bnChainWork : 0) + pindex->GetBlockWork();
+        pindex->nChainTx = (pindex->pprev ? pindex->pprev->nChainTx : 0) + pindex->nTx;
+        if ((pindex->nStatus & BLOCK_VALID_MASK) >= BLOCK_VALID_TRANSACTIONS && !(pindex->nStatus & BLOCK_FAILED_MASK))
+            setBlockIndexValid.insert(pindex);
     }
 
     // Load block file info
@@ -727,20 +730,23 @@ bool CChainDB::LoadBlockIndexGuts()
             CBlockIndex* pindexNew = InsertBlockIndex(diskindex.GetBlockHash());
             pindexNew->pprev          = InsertBlockIndex(diskindex.hashPrev);
             pindexNew->nHeight        = diskindex.nHeight;
-            pindexNew->pos            = diskindex.pos;
+            pindexNew->nFile          = diskindex.nFile;
+            pindexNew->nDataPos       = diskindex.nDataPos;
             pindexNew->nUndoPos       = diskindex.nUndoPos;
             pindexNew->nVersion       = diskindex.nVersion;
             pindexNew->hashMerkleRoot = diskindex.hashMerkleRoot;
             pindexNew->nTime          = diskindex.nTime;
             pindexNew->nBits          = diskindex.nBits;
             pindexNew->nNonce         = diskindex.nNonce;
+            pindexNew->nStatus        = diskindex.nStatus;
+            pindexNew->nTx            = diskindex.nTx;
 
             // Watch for genesis block
             if (pindexGenesisBlock == NULL && diskindex.GetBlockHash() == hashGenesisBlock)
                 pindexGenesisBlock = pindexNew;
 
             if (!pindexNew->CheckIndex())
-                return error("LoadBlockIndex() : CheckIndex failed at %d", pindexNew->nHeight);
+                return error("LoadBlockIndex() : CheckIndex failed: %s", pindexNew->ToString().c_str());
         }
         else
         {
diff --git a/src/init.cpp b/src/init.cpp
index 85aa4f6007..99e2bba376 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -781,38 +781,9 @@ bool AppInit2()
     // ********************************************************* Step 9: import blocks
 
     // scan for better chains in the block chain database, that are not yet connected in the active best chain
-    CBlockIndex *pindexFoundBest = pindexBest;
-    for (std::map<uint256,CBlockIndex*>::iterator it = mapBlockIndex.begin(); it != mapBlockIndex.end(); it++) {
-        CBlockIndex *pindex = it->second;
-        if (pindexFoundBest==NULL || pindex->bnChainWork > pindexFoundBest->bnChainWork)
-            pindexFoundBest = pindex;
-    }
-    if (pindexFoundBest != pindexBest) {
-        uiInterface.InitMessage(_("Importing blocks from block database..."));
-        uint64 nTxs = 0;
-        uint64 nBlocks = 0;
-        std::vector<CBlockIndex*> vAttach;
-        vAttach.reserve(pindexFoundBest->nHeight - (pindexBest==NULL ? 0 : pindexBest->nHeight));
-        while (pindexFoundBest && pindexFoundBest->bnChainWork > (pindexBest==NULL ? 0 : pindexBest->bnChainWork)) {
-            vAttach.push_back(pindexFoundBest);
-            pindexFoundBest = pindexFoundBest->pprev;
-        }
-        for (std::vector<CBlockIndex*>::reverse_iterator it = vAttach.rbegin(); it != vAttach.rend(); it++) {
-            CBlockIndex *pindex = *it;
-            CBlock block;
-            if (!block.ReadFromDisk(pindex))
-                break;
-            nTxs += block.vtx.size();
-            nBlocks++;
-            if (pindex->nHeight == 0 || nTxs + nBlocks*3 > 500) {
-                nTxs=0;
-                nBlocks=0;
-                block.SetBestChain(pindex);
-            }
-            if (fRequestShutdown)
-                break;
-        }
-    }
+    uiInterface.InitMessage(_("Importing blocks from block database..."));
+    if (!ConnectBestBlock())
+        strErrors << "Failed to connect best block";
 
     std::vector<boost::filesystem::path> *vPath = new std::vector<boost::filesystem::path>();
     if (mapArgs.count("-loadblock"))
diff --git a/src/main.cpp b/src/main.cpp
index 42f70c023c..b077eb9d6e 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -37,6 +37,7 @@ CBigNum bnBestChainWork = 0;
 CBigNum bnBestInvalidWork = 0;
 uint256 hashBestChain = 0;
 CBlockIndex* pindexBest = NULL;
+set<CBlockIndex*, CBlockIndexWorkComparator> setBlockIndexValid; // may contain all CBlockIndex*'s that have validness >=BLOCK_VALID_TRANSACTIONS, and must contain those who aren't failed
 int64 nTimeBestReceived = 0;
 bool fImporting = false;
 
@@ -1156,6 +1157,62 @@ void static InvalidChainFound(CBlockIndex* pindexNew)
         printf("InvalidChainFound: Warning: Displayed transactions may not be correct! You may need to upgrade, or other nodes may need to upgrade.\n");
 }
 
+void static InvalidBlockFound(CBlockIndex *pindex) {
+    pindex->nStatus |= BLOCK_FAILED_VALID;
+    CChainDB().WriteBlockIndex(CDiskBlockIndex(pindex));
+    setBlockIndexValid.erase(pindex);
+    InvalidChainFound(pindex);
+    if (pindex->pnext)
+        ConnectBestBlock(); // reorganise away from the failed block
+}
+
+bool ConnectBestBlock() {
+    do {
+        CBlockIndex *pindexNewBest;
+
+        {
+            std::set<CBlockIndex*,CBlockIndexWorkComparator>::reverse_iterator it = setBlockIndexValid.rbegin();
+            if (it == setBlockIndexValid.rend())
+                return true;
+            pindexNewBest = *it;
+        }
+
+        if (pindexNewBest == pindexBest)
+            return true; // nothing to do
+
+        // check ancestry
+        CBlockIndex *pindexTest = pindexNewBest;
+        std::vector<CBlockIndex*> vAttach;
+        do {
+            if (pindexTest->nStatus & BLOCK_FAILED_MASK) {
+                // mark descendants failed
+                CChainDB chaindb;
+                CBlockIndex *pindexFailed = pindexNewBest;
+                while (pindexTest != pindexFailed) {
+                    pindexFailed->nStatus |= BLOCK_FAILED_CHILD;
+                    setBlockIndexValid.erase(pindexFailed);
+                    chaindb.WriteBlockIndex(CDiskBlockIndex(pindexFailed));
+                    pindexFailed = pindexFailed->pprev;
+                }
+                InvalidChainFound(pindexNewBest);
+                break;
+            }
+
+            if (pindexBest == NULL || pindexTest->bnChainWork > pindexBest->bnChainWork)
+                vAttach.push_back(pindexTest);
+
+            if (pindexTest->pprev == NULL || pindexTest->pnext != NULL) {
+                reverse(vAttach.begin(), vAttach.end());
+                BOOST_FOREACH(CBlockIndex *pindexSwitch, vAttach)
+                    if (!SetBestChain(pindexSwitch))
+                        return false;
+                return true;
+            }
+            pindexTest = pindexTest->pprev;
+        } while(true);
+    } while(true);
+}
+
 void CBlock::UpdateTime(const CBlockIndex* pindexPrev)
 {
     nTime = max(pindexPrev->GetMedianTimePast()+1, GetAdjustedTime());
@@ -1522,17 +1579,24 @@ bool CBlock::ConnectBlock(CBlockIndex* pindex, CCoinsViewCache &view, bool fJust
         return true;
 
     // Write undo information to disk
-    if (pindex->GetUndoPos().IsNull())
+    if (pindex->GetUndoPos().IsNull() || (pindex->nStatus & BLOCK_VALID_MASK) < BLOCK_VALID_SCRIPTS)
     {
         CChainDB chaindb;
-        CDiskBlockPos pos;
-        if (!FindUndoPos(chaindb, pindex->pos.nFile, pos, ::GetSerializeSize(blockundo, SER_DISK, CLIENT_VERSION) + 8))
-            return error("ConnectBlock() : FindUndoPos failed");
-        if (!blockundo.WriteToDisk(pos))
-            return error("ConnectBlock() : CBlockUndo::WriteToDisk failed");
-
-        // update nUndoPos in block index
-        pindex->nUndoPos = pos.nPos + 1;
+
+        if (pindex->GetUndoPos().IsNull()) {
+            CDiskBlockPos pos;
+            if (!FindUndoPos(chaindb, pindex->nFile, pos, ::GetSerializeSize(blockundo, SER_DISK, CLIENT_VERSION) + 8))
+                return error("ConnectBlock() : FindUndoPos failed");
+            if (!blockundo.WriteToDisk(pos))
+                return error("ConnectBlock() : CBlockUndo::WriteToDisk failed");
+
+            // update nUndoPos in block index
+            pindex->nUndoPos = pos.nPos;
+            pindex->nStatus |= BLOCK_HAVE_UNDO;
+        }
+
+        pindex->nStatus = (pindex->nStatus & ~BLOCK_VALID_MASK) | BLOCK_VALID_SCRIPTS;
+
         CDiskBlockIndex blockindex(pindex);
         if (!chaindb.WriteBlockIndex(blockindex))
             return error("ConnectBlock() : WriteBlockIndex failed");
@@ -1549,7 +1613,7 @@ bool CBlock::ConnectBlock(CBlockIndex* pindex, CCoinsViewCache &view, bool fJust
     return true;
 }
 
-bool CBlock::SetBestChain(CBlockIndex* pindexNew)
+bool SetBestChain(CBlockIndex* pindexNew)
 {
     CCoinsViewCache &view = *pcoinsTip;
 
@@ -1620,24 +1684,19 @@ bool CBlock::SetBestChain(CBlockIndex* pindexNew)
     vector<CTransaction> vDelete;
     BOOST_FOREACH(CBlockIndex *pindex, vConnect) {
         CBlock block;
-        CBlock *pblock;
-        if (pindex == pindexNew) // connecting *this block
-            pblock = this;
-        else { // other block; read it from disk
-            if (!block.ReadFromDisk(pindex))
-                return error("SetBestBlock() : ReadFromDisk for connect failed");
-            pblock = &block;
-        }
+        if (!block.ReadFromDisk(pindex))
+            return error("SetBestBlock() : ReadFromDisk for connect failed");
         CCoinsViewCache viewTemp(view, true);
-        if (!pblock->ConnectBlock(pindex, viewTemp)) {
+        if (!block.ConnectBlock(pindex, viewTemp)) {
             InvalidChainFound(pindexNew);
+            InvalidBlockFound(pindex);
             return error("SetBestBlock() : ConnectBlock %s failed", pindex->GetBlockHash().ToString().substr(0,20).c_str());
         }
         if (!viewTemp.Flush())
             return error("SetBestBlock() : Cache flush failed after connect");
 
         // Queue memory transactions to delete
-        BOOST_FOREACH(const CTransaction& tx, pblock->vtx)
+        BOOST_FOREACH(const CTransaction& tx, block.vtx)
             vDelete.push_back(tx);
     }
 
@@ -1683,8 +1742,8 @@ bool CBlock::SetBestChain(CBlockIndex* pindexNew)
     bnBestChainWork = pindexNew->bnChainWork;
     nTimeBestReceived = GetTime();
     nTransactionsUpdated++;
-    printf("SetBestChain: new best=%s  height=%d  work=%s  date=%s\n",
-      hashBestChain.ToString().substr(0,20).c_str(), nBestHeight, bnBestChainWork.ToString().c_str(),
+    printf("SetBestChain: new best=%s  height=%d  work=%s  tx=%lu  date=%s\n",
+      hashBestChain.ToString().substr(0,20).c_str(), nBestHeight, bnBestChainWork.ToString().c_str(), (unsigned long)pindexNew->nChainTx,
       DateTimeStrFormat("%x %H:%M:%S", pindexBest->GetBlockTime()).c_str());
 
     // Check the version of the last 100 blocks to see if we need to upgrade:
@@ -1736,9 +1795,14 @@ bool CBlock::AddToBlockIndex(const CDiskBlockPos &pos)
         pindexNew->pprev = (*miPrev).second;
         pindexNew->nHeight = pindexNew->pprev->nHeight + 1;
     }
+    pindexNew->nTx = vtx.size();
     pindexNew->bnChainWork = (pindexNew->pprev ? pindexNew->pprev->bnChainWork : 0) + pindexNew->GetBlockWork();
-    pindexNew->pos = pos;
+    pindexNew->nChainTx = (pindexNew->pprev ? pindexNew->pprev->nChainTx : 0) + pindexNew->nTx;
+    pindexNew->nFile = pos.nFile;
+    pindexNew->nDataPos = pos.nPos;
     pindexNew->nUndoPos = 0;
+    pindexNew->nStatus = BLOCK_VALID_TRANSACTIONS | BLOCK_HAVE_DATA;
+    setBlockIndexValid.insert(pindexNew);
 
     CChainDB chaindb;
     if (!chaindb.TxnBegin())
@@ -1747,8 +1811,8 @@ bool CBlock::AddToBlockIndex(const CDiskBlockPos &pos)
     if (!chaindb.TxnCommit())
         return false;
 
-    // New best
-    if (!SetBestChain(pindexNew))
+    // New best?
+    if (!ConnectBestBlock())
         return false;
 
     if (pindexNew == pindexBest)
diff --git a/src/main.h b/src/main.h
index 1150ca4c02..687171ef7c 100644
--- a/src/main.h
+++ b/src/main.h
@@ -23,6 +23,8 @@ class CInv;
 class CRequestTracker;
 class CNode;
 
+class CBlockIndexWorkComparator;
+
 static const unsigned int MAX_BLOCK_SIZE = 1000000;
 static const unsigned int MAX_BLOCK_SIZE_GEN = MAX_BLOCK_SIZE/2;
 static const unsigned int MAX_BLOCK_SIGOPS = MAX_BLOCK_SIZE/50;
@@ -55,6 +57,7 @@ extern CScript COINBASE_FLAGS;
 
 extern CCriticalSection cs_main;
 extern std::map<uint256, CBlockIndex*> mapBlockIndex;
+extern std::set<CBlockIndex*, CBlockIndexWorkComparator> setBlockIndexValid;
 extern uint256 hashGenesisBlock;
 extern CBlockIndex* pindexGenesisBlock;
 extern int nBestHeight;
@@ -114,6 +117,9 @@ int GetNumBlocksOfPeers();
 bool IsInitialBlockDownload();
 std::string GetWarnings(std::string strFor);
 bool GetTransaction(const uint256 &hash, CTransaction &tx, uint256 &hashBlock, bool fAllowSlow = false);
+bool SetBestChain(CBlockIndex* pindexNew);
+bool ConnectBestBlock();
+
 
 
 
@@ -1234,9 +1240,6 @@ public:
     // Read a block from disk
     bool ReadFromDisk(const CBlockIndex* pindex, bool fReadTransactions=true);
 
-    // Make this block (with given index) the new tip of the active block chain
-    bool SetBestChain(CBlockIndex* pindexNew);
-
     // Add this block to the block index, and if necessary, switch the active block chain to this
     bool AddToBlockIndex(const CDiskBlockPos &pos);
 
@@ -1308,6 +1311,24 @@ extern CCriticalSection cs_LastBlockFile;
 extern CBlockFileInfo infoLastBlockFile;
 extern int nLastBlockFile;
 
+enum BlockStatus {
+    BLOCK_VALID_UNKNOWN      =    0,
+    BLOCK_VALID_HEADER       =    1, // parsed, version ok, hash satisfies claimed PoW, 1 <= vtx count <= max, timestamp not in future
+    BLOCK_VALID_TREE         =    2, // parent found, difficulty matches, timestamp >= median previous, checkpoint
+    BLOCK_VALID_TRANSACTIONS =    3, // only first tx is coinbase, 2 <= coinbase input script length <= 100, transactions valid, no duplicate txids, sigops, size, merkle root
+    BLOCK_VALID_CHAIN        =    4, // outputs do not overspend inputs, no double spends, coinbase output ok, immature coinbase spends, BIP30
+    BLOCK_VALID_SCRIPTS      =    5, // scripts/signatures ok
+    BLOCK_VALID_MASK         =    7,
+
+    BLOCK_HAVE_DATA          =    8, // full block available in blk*.dat
+    BLOCK_HAVE_UNDO          =   16, // undo data available in rev*.dat
+    BLOCK_HAVE_MASK          =   24,
+
+    BLOCK_FAILED_VALID       =   32, // stage after last reached validness failed
+    BLOCK_FAILED_CHILD       =   64, // descends from failed block
+    BLOCK_FAILED_MASK        =   96
+};
+
 /** The block chain is a tree shaped structure starting with the
  * genesis block at the root, with each block potentially having multiple
  * candidates to be the next block.  pprev and pnext link a path through the
@@ -1318,14 +1339,40 @@ extern int nLastBlockFile;
 class CBlockIndex
 {
 public:
+    // pointer to the hash of the block, if any. memory is owned by this CBlockIndex
     const uint256* phashBlock;
+
+    // pointer to the index of the predecessor of this block
     CBlockIndex* pprev;
+
+    // (memory only) pointer to the index of the *active* successor of this block
     CBlockIndex* pnext;
+
+    // height of the entry in the chain. The genesis block has height 0
     int nHeight;
-    CDiskBlockPos pos;
+
+    // Which # file this block is stored in (blk?????.dat)
+    int nFile;
+
+    // Byte offset within blk?????.dat where this block's data is stored
+    unsigned int nDataPos;
+
+    // Byte offset within rev?????.dat where this block's undo data is stored
     unsigned int nUndoPos;
+
+    // (memory only) Total amount of work (expected number of hashes) in the chain up to and including this block
     CBigNum bnChainWork;
 
+    // Number of transactions in this block.
+    // Note: in a potential headers-first mode, this number cannot be relied upon
+    unsigned int nTx;
+
+    // (memory only) Number of transactions in the chain up to and including this block
+    unsigned int nChainTx; // change to 64-bit type when necessary; won't happen before 2030
+
+    // Verification status of this block. See enum BlockStatus
+    unsigned int nStatus;
+
     // block header
     int nVersion;
     uint256 hashMerkleRoot;
@@ -1340,9 +1387,13 @@ public:
         pprev = NULL;
         pnext = NULL;
         nHeight = 0;
-        pos.SetNull();
+        nFile = 0;
+        nDataPos = 0;
         nUndoPos = 0;
         bnChainWork = 0;
+        nTx = 0;
+        nChainTx = 0;
+        nStatus = 0;
 
         nVersion       = 0;
         hashMerkleRoot = 0;
@@ -1357,9 +1408,13 @@ public:
         pprev = NULL;
         pnext = NULL;
         nHeight = 0;
-        pos.SetNull();
+        nFile = 0;
+        nDataPos = 0;
         nUndoPos = 0;
         bnChainWork = 0;
+        nTx = 0;
+        nChainTx = 0;
+        nStatus = 0;
 
         nVersion       = block.nVersion;
         hashMerkleRoot = block.hashMerkleRoot;
@@ -1369,15 +1424,22 @@ public:
     }
 
     CDiskBlockPos GetBlockPos() const {
-        return pos;
+        CDiskBlockPos ret;
+        if (nStatus & BLOCK_HAVE_DATA) {
+            ret.nFile = nFile;
+            ret.nPos  = nDataPos;
+        } else
+            ret.SetNull();
+        return ret;
     }
 
     CDiskBlockPos GetUndoPos() const {
-        CDiskBlockPos ret = pos;
-        if (nUndoPos == 0)
+        CDiskBlockPos ret;
+        if (nStatus & BLOCK_HAVE_UNDO) {
+            ret.nFile = nFile;
+            ret.nPos  = nUndoPos;
+        } else
             ret.SetNull();
-        else
-            ret.nPos = nUndoPos - 1;
         return ret;
     }
 
@@ -1472,6 +1534,19 @@ public:
     }
 };
 
+struct CBlockIndexWorkComparator
+{
+    bool operator()(CBlockIndex *pa, CBlockIndex *pb) {
+        if (pa->bnChainWork > pb->bnChainWork) return false;
+        if (pa->bnChainWork < pb->bnChainWork) return true;
+
+        if (pa->GetBlockHash() < pb->GetBlockHash()) return false;
+        if (pa->GetBlockHash() > pb->GetBlockHash()) return true;
+
+        return false; // identical blocks
+    }
+};
+
 
 
 /** Used to marshal pointers into hashes for db storage. */
@@ -1491,11 +1566,17 @@ public:
     IMPLEMENT_SERIALIZE
     (
         if (!(nType & SER_GETHASH))
-            READWRITE(nVersion);
-
-        READWRITE(nHeight);
-        READWRITE(pos);
-        READWRITE(nUndoPos);
+            READWRITE(VARINT(nVersion));
+
+        READWRITE(VARINT(nHeight));
+        READWRITE(VARINT(nStatus));
+        READWRITE(VARINT(nTx));
+        if (nStatus & (BLOCK_HAVE_DATA | BLOCK_HAVE_UNDO))
+            READWRITE(VARINT(nFile));
+        if (nStatus & BLOCK_HAVE_DATA)
+            READWRITE(VARINT(nDataPos));
+        if (nStatus & BLOCK_HAVE_UNDO)
+            READWRITE(VARINT(nUndoPos));
 
         // block header
         READWRITE(this->nVersion);