From 341735eb8f42e898cf9d4d130709471e5d01abe2 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sat, 12 Jul 2014 00:02:35 +0200 Subject: Headers-first synchronization Many changes: * Do not use 'getblocks', but 'getheaders', and use it to build a headers tree. * Blocks are fetched in parallel from all available outbound peers, using a limited moving window. When one peer stalls the movement of the window, it is disconnected. * No more orphan blocks. At all. We only ever request a block for which we have verified the headers, and store it to disk immediately. This means that a disk-fill attack would require PoW. * Require protocol version 31800 for every peer (released in december 2010). * No more syncnode (we sync from everyone we can, though limited to 1 during initial *headers* sync). * Introduce some extra named constants, comments and asserts. --- src/main.cpp | 608 ++++++++++++++++++++++++++++++++--------------------------- 1 file changed, 334 insertions(+), 274 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index fc8167e40e..816cab7e1f 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -56,14 +56,6 @@ CFeeRate minRelayTxFee = CFeeRate(1000); CTxMemPool mempool(::minRelayTxFee); -struct COrphanBlock { - uint256 hashBlock; - uint256 hashPrev; - vector vchBlock; -}; -map mapOrphanBlocks; -multimap mapOrphanBlocksByPrev; - struct COrphanTx { CTransaction tx; NodeId fromPeer; @@ -106,6 +98,12 @@ namespace { // The set of all CBlockIndex entries with BLOCK_VALID_TRANSACTIONS or better that are at least // as good as our current tip. Entries may be failed, though. set setBlockIndexValid; + // Best header we've seen so far (used for getheaders queries' starting points). + CBlockIndex *pindexBestHeader = NULL; + // Number of nodes with fSyncStarted. + int nSyncStarted = 0; + // All pairs A->B, where A (or one if its ancestors) misses transactions, but B has transactions. + multimap mapBlocksUnlinked; CCriticalSection cs_LastBlockFile; CBlockFileInfo infoLastBlockFile; @@ -125,11 +123,10 @@ namespace { // Protected by cs_main. struct QueuedBlock { uint256 hash; + CBlockIndex *pindex; // Optional. int64_t nTime; // Time of "getdata" request in microseconds. - int nQueuedBefore; // Number of blocks in flight at the time of request. }; map::iterator> > mapBlocksInFlight; - map::iterator> > mapBlocksToDownload; } // anon namespace @@ -220,22 +217,24 @@ struct CNodeState { CBlockIndex *pindexBestKnownBlock; // The hash of the last unknown block this peer has announced. uint256 hashLastUnknownBlock; + // The last full block we both have. + CBlockIndex *pindexLastCommonBlock; + // Whether we've started headers synchronization with this peer. + bool fSyncStarted; + // Since when we're stalling block download progress (in microseconds), or 0. + int64_t nStallingSince; list vBlocksInFlight; int nBlocksInFlight; - list vBlocksToDownload; - int nBlocksToDownload; - int64_t nLastBlockReceive; - int64_t nLastBlockProcess; CNodeState() { nMisbehavior = 0; fShouldBan = false; pindexBestKnownBlock = NULL; hashLastUnknownBlock = uint256(0); - nBlocksToDownload = 0; + pindexLastCommonBlock = NULL; + fSyncStarted = false; + nStallingSince = 0; nBlocksInFlight = 0; - nLastBlockReceive = 0; - nLastBlockProcess = 0; } }; @@ -266,64 +265,37 @@ void FinalizeNode(NodeId nodeid) { LOCK(cs_main); CNodeState *state = State(nodeid); + if (state->fSyncStarted) + nSyncStarted--; + BOOST_FOREACH(const QueuedBlock& entry, state->vBlocksInFlight) mapBlocksInFlight.erase(entry.hash); - BOOST_FOREACH(const uint256& hash, state->vBlocksToDownload) - mapBlocksToDownload.erase(hash); EraseOrphansFor(nodeid); mapNodeState.erase(nodeid); } // Requires cs_main. -void MarkBlockAsReceived(const uint256 &hash, NodeId nodeFrom = -1) { - map::iterator> >::iterator itToDownload = mapBlocksToDownload.find(hash); - if (itToDownload != mapBlocksToDownload.end()) { - CNodeState *state = State(itToDownload->second.first); - state->vBlocksToDownload.erase(itToDownload->second.second); - state->nBlocksToDownload--; - mapBlocksToDownload.erase(itToDownload); - } - +void MarkBlockAsReceived(const uint256& hash) { map::iterator> >::iterator itInFlight = mapBlocksInFlight.find(hash); if (itInFlight != mapBlocksInFlight.end()) { CNodeState *state = State(itInFlight->second.first); state->vBlocksInFlight.erase(itInFlight->second.second); state->nBlocksInFlight--; - if (itInFlight->second.first == nodeFrom) - state->nLastBlockReceive = GetTimeMicros(); + state->nStallingSince = 0; mapBlocksInFlight.erase(itInFlight); } } // Requires cs_main. -bool AddBlockToQueue(NodeId nodeid, const uint256 &hash) { - if (mapBlocksToDownload.count(hash) || mapBlocksInFlight.count(hash)) - return false; - - CNodeState *state = State(nodeid); - if (state == NULL) - return false; - - list::iterator it = state->vBlocksToDownload.insert(state->vBlocksToDownload.end(), hash); - state->nBlocksToDownload++; - if (state->nBlocksToDownload > 5000) - Misbehaving(nodeid, 10); - mapBlocksToDownload[hash] = std::make_pair(nodeid, it); - return true; -} - -// Requires cs_main. -void MarkBlockAsInFlight(NodeId nodeid, const uint256 &hash) { +void MarkBlockAsInFlight(NodeId nodeid, const uint256& hash, CBlockIndex *pindex = NULL) { CNodeState *state = State(nodeid); assert(state != NULL); // Make sure it's not listed somewhere already. MarkBlockAsReceived(hash); - QueuedBlock newentry = {hash, GetTimeMicros(), state->nBlocksInFlight}; - if (state->nBlocksInFlight == 0) - state->nLastBlockReceive = newentry.nTime; // Reset when a first request is sent. + QueuedBlock newentry = {hash, pindex, GetTimeMicros()}; list::iterator it = state->vBlocksInFlight.insert(state->vBlocksInFlight.end(), newentry); state->nBlocksInFlight++; mapBlocksInFlight[hash] = std::make_pair(nodeid, it); @@ -362,6 +334,103 @@ void UpdateBlockAvailability(NodeId nodeid, const uint256 &hash) { } } +/** Find the last common ancestor two blocks have. + * Both pa and pb must be non-NULL. */ +CBlockIndex* LastCommonAncestor(CBlockIndex* pa, CBlockIndex* pb) { + if (pa->nHeight > pb->nHeight) { + pa = pa->GetAncestor(pb->nHeight); + } else if (pb->nHeight > pa->nHeight) { + pb = pb->GetAncestor(pa->nHeight); + } + + while (pa != pb && pa && pb) { + pa = pa->pprev; + pb = pb->pprev; + } + + // Eventually all chain branches meet at the genesis block. + assert(pa == pb); + return pa; +} + +/** Update pindexLastCommonBlock and add not-in-flight missing successors to vBlocks, until it has + * at most count entries. */ +void FindNextBlocksToDownload(NodeId nodeid, unsigned int count, std::vector& vBlocks, NodeId& nodeStaller) { + if (count == 0) + return; + + vBlocks.reserve(vBlocks.size() + count); + CNodeState *state = State(nodeid); + assert(state != NULL); + + // Make sure pindexBestKnownBlock is up to date, we'll need it. + ProcessBlockAvailability(nodeid); + + if (state->pindexBestKnownBlock == NULL || state->pindexBestKnownBlock->nChainWork < chainActive.Tip()->nChainWork) { + // This peer has nothing interesting. + return; + } + + if (state->pindexLastCommonBlock == NULL) { + // Bootstrap quickly by guessing a parent of our best tip is the forking point. + // Guessing wrong in either direction is not a problem. + state->pindexLastCommonBlock = chainActive[std::min(state->pindexBestKnownBlock->nHeight, chainActive.Height())]; + } + + // If the peer reorganized, our previous pindexLastCommonBlock may not be an ancestor + // of their current tip anymore. Go back enough to fix that. + state->pindexLastCommonBlock = LastCommonAncestor(state->pindexLastCommonBlock, state->pindexBestKnownBlock); + if (state->pindexLastCommonBlock == state->pindexBestKnownBlock) + return; + + std::vector vToFetch; + CBlockIndex *pindexWalk = state->pindexLastCommonBlock; + // Never fetch further than the best block we know the peer has, or more than BLOCK_DOWNLOAD_WINDOW + 1 beyond our + // current tip. The +1 is so we can detect stalling, namely if we would be able to download that next block if the + // window were 1 larger. + int nMaxHeight = std::min(state->pindexBestKnownBlock->nHeight, chainActive.Height() + BLOCK_DOWNLOAD_WINDOW + 1); + NodeId waitingfor = -1; + while (pindexWalk->nHeight < nMaxHeight) { + // Read up to 128 (or more, if more blocks than that are needed) successors of pindexWalk (towards + // pindexBestKnownBlock) into vToFetch. We fetch 128, because CBlockIndex::GetAncestor may be as expensive + // as iterating over ~100 CBlockIndex* entries anyway. + int nToFetch = std::min(nMaxHeight - pindexWalk->nHeight, std::max(count - vBlocks.size(), 128)); + vToFetch.resize(nToFetch); + pindexWalk = state->pindexBestKnownBlock->GetAncestor(pindexWalk->nHeight + nToFetch); + vToFetch[nToFetch - 1] = pindexWalk; + for (unsigned int i = nToFetch - 1; i > 0; i--) { + vToFetch[i - 1] = vToFetch[i]->pprev; + } + + // Iterate over those blocks in vToFetch (in forward direction), adding the ones that + // are not yet downloaded and not in flight to vBlocks. In the mean time, update + // pindexLastCommonBlock as long as all ancestors are already downloaded. + BOOST_FOREACH(CBlockIndex* pindex, vToFetch) { + if (pindex->nStatus & BLOCK_HAVE_DATA) { + if (pindex->nChainTx) + state->pindexLastCommonBlock = pindex; + } else if (mapBlocksInFlight.count(pindex->GetBlockHash()) == 0) { + // The block is not already downloaded, and not yet in flight. + if (pindex->nHeight > chainActive.Height() + (int)BLOCK_DOWNLOAD_WINDOW) { + // We reached the end of the window. + if (vBlocks.size() == 0 && waitingfor != nodeid) { + // We aren't able to fetch anything, but we would be if the download window was one larger. + nodeStaller = waitingfor; + } + return; + } + vBlocks.push_back(pindex); + if (vBlocks.size() == count) { + return; + } + } else if (waitingfor == -1) { + // This is the first already-in-flight block. + waitingfor = mapBlocksInFlight[pindex->GetBlockHash()].first; + } + } + } +} + } // anon namespace bool GetNodeStateStats(NodeId nodeid, CNodeStateStats &stats) { @@ -1086,46 +1155,6 @@ bool ReadBlockFromDisk(CBlock& block, const CBlockIndex* pindex) return true; } -uint256 static GetOrphanRoot(const uint256& hash) -{ - map::iterator it = mapOrphanBlocks.find(hash); - if (it == mapOrphanBlocks.end()) - return hash; - - // Work back to the first block in the orphan chain - do { - map::iterator it2 = mapOrphanBlocks.find(it->second->hashPrev); - if (it2 == mapOrphanBlocks.end()) - return it->first; - it = it2; - } while(true); -} - -// Remove a random orphan block (which does not have any dependent orphans). -void static PruneOrphanBlocks() -{ - if (mapOrphanBlocksByPrev.size() <= (size_t)std::max((int64_t)0, GetArg("-maxorphanblocks", DEFAULT_MAX_ORPHAN_BLOCKS))) - return; - - // Pick a random orphan block. - int pos = insecure_rand() % mapOrphanBlocksByPrev.size(); - std::multimap::iterator it = mapOrphanBlocksByPrev.begin(); - while (pos--) it++; - - // As long as this block has other orphans depending on it, move to one of those successors. - do { - std::multimap::iterator it2 = mapOrphanBlocksByPrev.find(it->second->hashBlock); - if (it2 == mapOrphanBlocksByPrev.end()) - break; - it = it2; - } while(1); - - uint256 hash = it->second->hashBlock; - delete it->second; - mapOrphanBlocksByPrev.erase(it); - mapOrphanBlocks.erase(hash); -} - CAmount GetBlockValue(int nHeight, const CAmount& nFees) { int64_t nSubsidy = 50 * COIN; @@ -1664,11 +1693,6 @@ bool ConnectBlock(CBlock& block, CValidationState& state, CBlockIndex* pindex, C if (fJustCheck) return true; - // Correct transaction counts. - pindex->nTx = block.vtx.size(); - if (pindex->pprev) - pindex->nChainTx = pindex->pprev->nChainTx + block.vtx.size(); - // Write undo information to disk if (pindex->GetUndoPos().IsNull() || !pindex->IsValid(BLOCK_VALID_SCRIPTS)) { @@ -1900,6 +1924,8 @@ static CBlockIndex* FindMostWorkChain() { CBlockIndex *pindexTest = pindexNew; bool fInvalidAncestor = false; while (pindexTest && !chainActive.Contains(pindexTest)) { + assert(pindexTest->nStatus & BLOCK_HAVE_DATA); + assert(pindexTest->nChainTx || pindexTest->nHeight == 0); if (pindexTest->nStatus & BLOCK_FAILED_MASK) { // Candidate has an invalid ancestor, remove entire chain from the set. if (pindexBestInvalid == NULL || pindexNew->nChainWork > pindexBestInvalid->nChainWork) @@ -2032,7 +2058,7 @@ bool ActivateBestChain(CValidationState &state, CBlock *pblock) { return true; } -CBlockIndex* AddToBlockIndex(CBlockHeader& block) +CBlockIndex* AddToBlockIndex(const CBlockHeader& block) { // Check for duplicate uint256 hash = block.GetHash(); @@ -2043,10 +2069,10 @@ CBlockIndex* AddToBlockIndex(CBlockHeader& block) // Construct new block index object CBlockIndex* pindexNew = new CBlockIndex(block); assert(pindexNew); - { - LOCK(cs_nBlockSequenceId); - pindexNew->nSequenceId = nBlockSequenceId++; - } + // We assign the sequence id to blocks only when the full data is available, + // to avoid miners withholding blocks but broadcasting headers, to get a + // competitive advantage. + pindexNew->nSequenceId = 0; BlockMap::iterator mi = mapBlockIndex.insert(make_pair(hash, pindexNew)).first; pindexNew->phashBlock = &((*mi).first); BlockMap::iterator miPrev = mapBlockIndex.find(block.hashPrevBlock); @@ -2058,6 +2084,11 @@ CBlockIndex* AddToBlockIndex(CBlockHeader& block) } pindexNew->nChainWork = (pindexNew->pprev ? pindexNew->pprev->nChainWork : 0) + pindexNew->GetBlockWork(); pindexNew->RaiseValidity(BLOCK_VALID_TREE); + if (pindexBestHeader == NULL || pindexBestHeader->nChainWork < pindexNew->nChainWork) + pindexBestHeader = pindexNew; + + // Ok if it fails, we'll download the header again next time. + pblocktree->WriteBlockIndex(CDiskBlockIndex(pindexNew)); return pindexNew; } @@ -2066,30 +2097,45 @@ CBlockIndex* AddToBlockIndex(CBlockHeader& block) bool ReceivedBlockTransactions(const CBlock &block, CValidationState& state, CBlockIndex *pindexNew, const CDiskBlockPos& pos) { pindexNew->nTx = block.vtx.size(); - if (pindexNew->pprev) { - // Not the genesis block. - if (pindexNew->pprev->nChainTx) { - // This parent's block's total number transactions is known, so compute outs. - pindexNew->nChainTx = pindexNew->pprev->nChainTx + pindexNew->nTx; - } else { - // The total number of transactions isn't known yet. - // We will compute it when the block is connected. - pindexNew->nChainTx = 0; - } - } else { - // Genesis block. - pindexNew->nChainTx = pindexNew->nTx; - } + pindexNew->nChainTx = 0; pindexNew->nFile = pos.nFile; pindexNew->nDataPos = pos.nPos; pindexNew->nUndoPos = 0; pindexNew->nStatus |= BLOCK_HAVE_DATA; + pindexNew->RaiseValidity(BLOCK_VALID_TRANSACTIONS); + { + LOCK(cs_nBlockSequenceId); + pindexNew->nSequenceId = nBlockSequenceId++; + } - if (pindexNew->RaiseValidity(BLOCK_VALID_TRANSACTIONS)) - setBlockIndexValid.insert(pindexNew); + if (pindexNew->pprev == NULL || pindexNew->pprev->nChainTx) { + // If pindexNew is the genesis block or all parents are BLOCK_VALID_TRANSACTIONS. + deque queue; + queue.push_back(pindexNew); - if (!pblocktree->WriteBlockIndex(CDiskBlockIndex(pindexNew))) - return state.Abort("Failed to write block index"); + // Recursively process any descendant blocks that now may be eligible to be connected. + while (!queue.empty()) { + CBlockIndex *pindex = queue.front(); + queue.pop_front(); + pindex->nChainTx = (pindex->pprev ? pindex->pprev->nChainTx : 0) + pindex->nTx; + setBlockIndexValid.insert(pindex); + std::pair::iterator, std::multimap::iterator> range = mapBlocksUnlinked.equal_range(pindex); + while (range.first != range.second) { + std::multimap::iterator it = range.first; + queue.push_back(it->second); + range.first++; + mapBlocksUnlinked.erase(it); + } + if (!pblocktree->WriteBlockIndex(CDiskBlockIndex(pindex))) + return state.Abort("Failed to write block index"); + } + } else { + if (pindexNew->pprev && pindexNew->pprev->IsValid(BLOCK_VALID_TREE)) { + mapBlocksUnlinked.insert(std::make_pair(pindexNew->pprev, pindexNew)); + } + if (!pblocktree->WriteBlockIndex(CDiskBlockIndex(pindexNew))) + return state.Abort("Failed to write block index"); + } return true; } @@ -2205,12 +2251,31 @@ bool CheckBlockHeader(const CBlockHeader& block, CValidationState& state, bool f bool CheckBlock(const CBlock& block, CValidationState& state, bool fCheckPOW, bool fCheckMerkleRoot) { - // These are checks that are independent of context - // that can be verified before saving an orphan block. + // These are checks that are independent of context. if (!CheckBlockHeader(block, state, fCheckPOW)) return false; + // Check the merkle root. + if (fCheckMerkleRoot) { + bool mutated; + uint256 hashMerkleRoot2 = block.BuildMerkleTree(&mutated); + if (block.hashMerkleRoot != hashMerkleRoot2) + return state.DoS(100, error("CheckBlock() : hashMerkleRoot mismatch"), + REJECT_INVALID, "bad-txnmrklroot", true); + + // Check for merkle tree malleability (CVE-2012-2459): repeating sequences + // of transactions in a block without affecting the merkle root of a block, + // while still invalidating it. + if (mutated) + return state.DoS(100, error("CheckBlock() : duplicate transaction"), + REJECT_INVALID, "bad-txns-duplicate", true); + } + + // All potential-corruption validation must be done before we do any + // transaction validation, as otherwise we may mark the header as invalid + // because we receive the wrong transactions for it. + // Size limits if (block.vtx.empty() || block.vtx.size() > MAX_BLOCK_SIZE || ::GetSerializeSize(block, SER_NETWORK, PROTOCOL_VERSION) > MAX_BLOCK_SIZE) return state.DoS(100, error("CheckBlock() : size limits failed"), @@ -2230,15 +2295,6 @@ bool CheckBlock(const CBlock& block, CValidationState& state, bool fCheckPOW, bo if (!CheckTransaction(tx, state)) return error("CheckBlock() : CheckTransaction failed"); - // Check for merkle tree malleability (CVE-2012-2459): repeating sequences - // of transactions in a block without affecting the merkle root of a block, - // while still invalidating it. - bool mutated; - uint256 hashMerkleRoot2 = block.BuildMerkleTree(&mutated); - if (mutated) - return state.DoS(100, error("CheckBlock() : duplicate transaction"), - REJECT_INVALID, "bad-txns-duplicate", true); - unsigned int nSigOps = 0; BOOST_FOREACH(const CTransaction& tx, block.vtx) { @@ -2248,15 +2304,10 @@ bool CheckBlock(const CBlock& block, CValidationState& state, bool fCheckPOW, bo return state.DoS(100, error("CheckBlock() : out-of-bounds SigOpCount"), REJECT_INVALID, "bad-blk-sigops", true); - // Check merkle root - if (fCheckMerkleRoot && block.hashMerkleRoot != hashMerkleRoot2) - return state.DoS(100, error("CheckBlock() : hashMerkleRoot mismatch"), - REJECT_INVALID, "bad-txnmrklroot", true); - return true; } -bool AcceptBlockHeader(CBlockHeader& block, CValidationState& state, CBlockIndex** ppindex) +bool AcceptBlockHeader(const CBlockHeader& block, CValidationState& state, CBlockIndex** ppindex) { AssertLockHeld(cs_main); // Check for duplicate @@ -2264,9 +2315,13 @@ bool AcceptBlockHeader(CBlockHeader& block, CValidationState& state, CBlockIndex BlockMap::iterator miSelf = mapBlockIndex.find(hash); CBlockIndex *pindex = NULL; if (miSelf != mapBlockIndex.end()) { + // Block header is already known. pindex = miSelf->second; + if (ppindex) + *ppindex = pindex; if (pindex->nStatus & BLOCK_FAILED_MASK) return state.Invalid(error("%s : block is marked invalid", __func__), 0, "duplicate"); + return true; } CBlockIndex* pcheckpoint = Checkpoints::GetLastCheckpoint(); @@ -2344,6 +2399,12 @@ bool AcceptBlock(CBlock& block, CValidationState& state, CBlockIndex** ppindex, if (!AcceptBlockHeader(block, state, &pindex)) return false; + if (pindex->nStatus & BLOCK_HAVE_DATA) { + // TODO: deal better with duplicate blocks. + // return state.DoS(20, error("AcceptBlock() : already have block %d %s", pindex->nHeight, pindex->GetBlockHash().ToString()), REJECT_DUPLICATE, "duplicate"); + return true; + } + if (!CheckBlock(block, state)) { if (state.IsInvalid() && !state.CorruptionPossible()) { pindex->nStatus |= BLOCK_FAILED_VALID; @@ -2456,93 +2517,26 @@ void CBlockIndex::BuildSkip() pskip = pprev->GetAncestor(GetSkipHeight(nHeight)); } -void PushGetBlocks(CNode* pnode, CBlockIndex* pindexBegin, uint256 hashEnd) -{ - AssertLockHeld(cs_main); - // Filter out duplicate requests - if (pindexBegin == pnode->pindexLastGetBlocksBegin && hashEnd == pnode->hashLastGetBlocksEnd) - return; - pnode->pindexLastGetBlocksBegin = pindexBegin; - pnode->hashLastGetBlocksEnd = hashEnd; - - pnode->PushMessage("getblocks", chainActive.GetLocator(pindexBegin), hashEnd); -} - bool ProcessBlock(CValidationState &state, CNode* pfrom, CBlock* pblock, CDiskBlockPos *dbp) { - // Check for duplicate - uint256 hash = pblock->GetHash(); - - { - LOCK(cs_main); - if (mapBlockIndex.count(hash)) - return state.Invalid(error("ProcessBlock() : already have block %d %s", mapBlockIndex[hash]->nHeight, hash.ToString()), 0, "duplicate"); - if (mapOrphanBlocks.count(hash)) - return state.Invalid(error("ProcessBlock() : already have block (orphan) %s", hash.ToString()), 0, "duplicate"); - // Preliminary checks - if (!CheckBlock(*pblock, state)) - return error("ProcessBlock() : CheckBlock FAILED"); + bool checked = CheckBlock(*pblock, state); - // If we don't already have its previous block (with full data), shunt it off to holding area until we get it - BlockMap::iterator it = mapBlockIndex.find(pblock->hashPrevBlock); - if (pblock->hashPrevBlock != 0 && (it == mapBlockIndex.end() || !(it->second->nStatus & BLOCK_HAVE_DATA))) { - LogPrintf("ProcessBlock: ORPHAN BLOCK %lu, prev=%s\n", (unsigned long)mapOrphanBlocks.size(), pblock->hashPrevBlock.ToString()); - - // Accept orphans as long as there is a node to request its parents from - if (pfrom) { - PruneOrphanBlocks(); - COrphanBlock* pblock2 = new COrphanBlock(); - { - CDataStream ss(SER_DISK, CLIENT_VERSION); - ss << *pblock; - pblock2->vchBlock = std::vector(ss.begin(), ss.end()); - } - pblock2->hashBlock = hash; - pblock2->hashPrev = pblock->hashPrevBlock; - mapOrphanBlocks.insert(make_pair(hash, pblock2)); - mapOrphanBlocksByPrev.insert(make_pair(pblock2->hashPrev, pblock2)); - - // Ask this guy to fill in what we're missing - PushGetBlocks(pfrom, chainActive.Tip(), GetOrphanRoot(hash)); + LOCK(cs_main); + MarkBlockAsReceived(pblock->GetHash()); + if (!checked) { + return error("ProcessBlock() : CheckBlock FAILED"); } - return true; - } - // Store to disk - CBlockIndex *pindex = NULL; - bool ret = AcceptBlock(*pblock, state, &pindex, dbp); - if (!ret) - return error("ProcessBlock() : AcceptBlock FAILED"); - - // Recursively process any orphan blocks that depended on this one - vector vWorkQueue; - vWorkQueue.push_back(hash); - for (unsigned int i = 0; i < vWorkQueue.size(); i++) - { - uint256 hashPrev = vWorkQueue[i]; - for (multimap::iterator mi = mapOrphanBlocksByPrev.lower_bound(hashPrev); - mi != mapOrphanBlocksByPrev.upper_bound(hashPrev); - ++mi) - { - CBlock block; - { - CDataStream ss(mi->second->vchBlock, SER_DISK, CLIENT_VERSION); - ss >> block; - } - block.BuildMerkleTree(); - // Use a dummy CValidationState so someone can't setup nodes to counter-DoS based on orphan resolution (that is, feeding people an invalid block based on LegitBlockX in order to get anyone relaying LegitBlockX banned) - CValidationState stateDummy; - CBlockIndex *pindexChild = NULL; - if (AcceptBlock(block, stateDummy, &pindexChild)) - vWorkQueue.push_back(mi->second->hashBlock); - mapOrphanBlocks.erase(mi->second->hashBlock); - delete mi->second; + // Store to disk + CBlockIndex *pindex = NULL; + bool ret = AcceptBlock(*pblock, state, &pindex, dbp); + if (pindex && pfrom) { + mapBlockSource[pindex->GetBlockHash()] = pfrom->GetId(); } - mapOrphanBlocksByPrev.erase(hashPrev); - } - + if (!ret) + return error("ProcessBlock() : AcceptBlock FAILED"); } if (!ActivateBestChain(state, pblock)) @@ -2808,13 +2802,26 @@ bool static LoadBlockIndexDB() { CBlockIndex* pindex = item.second; pindex->nChainWork = (pindex->pprev ? pindex->pprev->nChainWork : 0) + pindex->GetBlockWork(); - pindex->nChainTx = (pindex->pprev ? pindex->pprev->nChainTx : 0) + pindex->nTx; - if (pindex->IsValid(BLOCK_VALID_TRANSACTIONS)) + if (pindex->nStatus & BLOCK_HAVE_DATA) { + if (pindex->pprev) { + if (pindex->pprev->nChainTx) { + pindex->nChainTx = pindex->pprev->nChainTx + pindex->nTx; + } else { + pindex->nChainTx = 0; + mapBlocksUnlinked.insert(std::make_pair(pindex->pprev, pindex)); + } + } else { + pindex->nChainTx = pindex->nTx; + } + } + if (pindex->IsValid(BLOCK_VALID_TRANSACTIONS) && (pindex->nChainTx || pindex->pprev == NULL)) setBlockIndexValid.insert(pindex); if (pindex->nStatus & BLOCK_FAILED_MASK && (!pindexBestInvalid || pindex->nChainWork > pindexBestInvalid->nChainWork)) pindexBestInvalid = pindex; if (pindex->pprev) pindex->BuildSkip(); + if (pindex->IsValid(BLOCK_VALID_TREE) && (pindexBestHeader == NULL || CBlockIndexWorkComparator()(pindexBestHeader, pindex))) + pindexBestHeader = pindex; } // Load block file info @@ -3226,8 +3233,7 @@ bool static AlreadyHave(const CInv& inv) pcoinsTip->HaveCoins(inv.hash); } case MSG_BLOCK: - return mapBlockIndex.count(inv.hash) || - mapOrphanBlocks.count(inv.hash); + return mapBlockIndex.count(inv.hash); } // Don't know what it is, just say we already got one return true; @@ -3375,10 +3381,6 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, return true; } - { - LOCK(cs_main); - State(pfrom->GetId())->nLastBlockProcess = GetTimeMicros(); - } @@ -3587,6 +3589,8 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, LOCK(cs_main); + std::vector vToFetch; + for (unsigned int nInv = 0; nInv < vInv.size(); nInv++) { const CInv &inv = vInv[nInv]; @@ -3597,19 +3601,29 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, bool fAlreadyHave = AlreadyHave(inv); LogPrint("net", "got inv: %s %s peer=%d\n", inv.ToString(), fAlreadyHave ? "have" : "new", pfrom->id); - if (!fAlreadyHave) { - if (!fImporting && !fReindex) { - if (inv.type == MSG_BLOCK) - AddBlockToQueue(pfrom->GetId(), inv.hash); - else - pfrom->AskFor(inv); - } - } else if (inv.type == MSG_BLOCK && mapOrphanBlocks.count(inv.hash)) { - PushGetBlocks(pfrom, chainActive.Tip(), GetOrphanRoot(inv.hash)); - } + if (!fAlreadyHave && !fImporting && !fReindex && inv.type != MSG_BLOCK) + pfrom->AskFor(inv); - if (inv.type == MSG_BLOCK) + if (inv.type == MSG_BLOCK) { UpdateBlockAvailability(pfrom->GetId(), inv.hash); + if (!fAlreadyHave && !fImporting && !fReindex && !mapBlocksInFlight.count(inv.hash)) { + // First request the headers preceeding the announced block. In the normal fully-synced + // case where a new block is announced that succeeds the current tip (no reorganization), + // there are no such headers. + // Secondly, and only when we are close to being synced, we request the announced block directly, + // to avoid an extra round-trip. Note that we must *first* ask for the headers, so by the + // time the block arrives, the header chain leading up to it is already validated. Not + // doing this will result in the received block being rejected as an orphan in case it is + // not a direct successor. + pfrom->PushMessage("getheaders", chainActive.GetLocator(pindexBestHeader), inv.hash); + if (chainActive.Tip()->GetBlockTime() > GetAdjustedTime() - Params().TargetSpacing() * 20) { + vToFetch.push_back(inv); + // Mark block as in flight already, even though the actual "getdata" message only goes out + // later (within the same cs_main lock, though). + MarkBlockAsInFlight(pfrom->GetId(), inv.hash); + } + } + } // Track requests for our stuff g_signals.Inventory(inv.hash); @@ -3619,6 +3633,9 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, return error("send buffer size() = %u", pfrom->nSendSize); } } + + if (!vToFetch.empty()) + pfrom->PushMessage("getdata", vToFetch); } @@ -3706,7 +3723,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, // we must use CBlocks, as CBlockHeaders won't include the 0x00 nTx count at the end vector vHeaders; - int nLimit = 2000; + int nLimit = MAX_HEADERS_RESULTS; LogPrint("net", "getheaders %d to %s\n", (pindex ? pindex->nHeight : -1), hashStop.ToString()); for (; pindex; pindex = chainActive.Next(pindex)) { @@ -3826,22 +3843,66 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, } + else if (strCommand == "headers" && !fImporting && !fReindex) // Ignore headers received while importing + { + std::vector headers; + + // Bypass the normal CBlock deserialization, as we don't want to risk deserializing 2000 full blocks. + unsigned int nCount = ReadCompactSize(vRecv); + if (nCount > MAX_HEADERS_RESULTS) { + Misbehaving(pfrom->GetId(), 20); + return error("headers message size = %u", nCount); + } + headers.resize(nCount); + for (unsigned int n = 0; n < nCount; n++) { + vRecv >> headers[n]; + ReadCompactSize(vRecv); // ignore tx count; assume it is 0. + } + + LOCK(cs_main); + + if (nCount == 0) { + // Nothing interesting. Stop asking this peers for more headers. + return true; + } + + CBlockIndex *pindexLast = NULL; + BOOST_FOREACH(const CBlockHeader& header, headers) { + CValidationState state; + if (pindexLast != NULL && header.hashPrevBlock != pindexLast->GetBlockHash()) { + Misbehaving(pfrom->GetId(), 20); + return error("non-continuous headers sequence"); + } + if (!AcceptBlockHeader(header, state, &pindexLast)) { + int nDoS; + if (state.IsInvalid(nDoS)) { + if (nDoS > 0) + Misbehaving(pfrom->GetId(), nDoS); + return error("invalid header received"); + } + } + } + + if (pindexLast) + UpdateBlockAvailability(pfrom->GetId(), pindexLast->GetBlockHash()); + + if (nCount == MAX_HEADERS_RESULTS && pindexLast) { + // Headers message had its maximum size; the peer may have more headers. + // TODO: optimize: if pindexLast is an ancestor of chainActive.Tip or pindexBestHeader, continue + // from there instead. + pfrom->PushMessage("getheaders", chainActive.GetLocator(pindexLast), uint256(0)); + } + } + else if (strCommand == "block" && !fImporting && !fReindex) // Ignore blocks received while importing { CBlock block; vRecv >> block; - LogPrint("net", "received block %s peer=%d\n", block.GetHash().ToString(), pfrom->id); - CInv inv(MSG_BLOCK, block.GetHash()); - pfrom->AddInventoryKnown(inv); + LogPrint("net", "received block %s peer=%d\n", inv.hash.ToString(), pfrom->id); - { - LOCK(cs_main); - // Remember who we got this block from. - mapBlockSource[inv.hash] = pfrom->GetId(); - MarkBlockAsReceived(inv.hash, pfrom->GetId()); - } + pfrom->AddInventoryKnown(inv); CValidationState state; ProcessBlock(state, pfrom, &block); @@ -4323,9 +4384,17 @@ bool SendMessages(CNode* pto, bool fSendTrickle) state.rejects.clear(); // Start block sync - if (pto->fStartSync && !fImporting && !fReindex) { - pto->fStartSync = false; - PushGetBlocks(pto, chainActive.Tip(), uint256(0)); + if (pindexBestHeader == NULL) + pindexBestHeader = chainActive.Tip(); + bool fFetch = !pto->fInbound || (pindexBestHeader && (state.pindexLastCommonBlock ? state.pindexLastCommonBlock->nHeight : 0) + 144 > pindexBestHeader->nHeight); + if (!state.fSyncStarted && !pto->fClient && fFetch && !fImporting && !fReindex) { + // Only actively request headers from a single peer, unless we're close to today. + if (nSyncStarted == 0 || pindexBestHeader->GetBlockTime() > GetAdjustedTime() - 24 * 60 * 60) { + state.fSyncStarted = true; + nSyncStarted++; + CBlockIndex *pindexStart = pindexBestHeader->pprev ? pindexBestHeader->pprev : pindexBestHeader; + pto->PushMessage("getheaders", chainActive.GetLocator(pindexStart), uint256(0)); + } } // Resend wallet transactions that haven't gotten in a block yet @@ -4384,35 +4453,32 @@ bool SendMessages(CNode* pto, bool fSendTrickle) if (!vInv.empty()) pto->PushMessage("inv", vInv); - - // Detect stalled peers. Require that blocks are in flight, we haven't - // received a (requested) block in one minute, and that all blocks are - // in flight for over two minutes, since we first had a chance to - // process an incoming block. + // Detect whether we're stalling int64_t nNow = GetTimeMicros(); - if (!pto->fDisconnect && state.nBlocksInFlight && - state.nLastBlockReceive < state.nLastBlockProcess - BLOCK_DOWNLOAD_TIMEOUT*1000000 && - state.vBlocksInFlight.front().nTime < state.nLastBlockProcess - 2*BLOCK_DOWNLOAD_TIMEOUT*1000000) { - LogPrintf("Peer %s is stalling block download, disconnecting\n", state.name); + if (!pto->fDisconnect && state.nStallingSince && state.nStallingSince < nNow - 1000000 * BLOCK_STALLING_TIMEOUT) { + // Stalling only triggers when the block download window cannot move. During normal steady state, + // the download window should be much larger than the to-be-downloaded set of blocks, so disconnection + // should only happen during initial block download. + LogPrintf("Peer=%d is stalling block download, disconnecting\n", pto->id); pto->fDisconnect = true; } - // Update knowledge of peer's block availability. - ProcessBlockAvailability(pto->GetId()); - // // Message: getdata (blocks) // vector vGetData; - while (!pto->fDisconnect && state.nBlocksToDownload && state.nBlocksInFlight < MAX_BLOCKS_IN_TRANSIT_PER_PEER) { - uint256 hash = state.vBlocksToDownload.front(); - vGetData.push_back(CInv(MSG_BLOCK, hash)); - MarkBlockAsInFlight(pto->GetId(), hash); - LogPrint("net", "Requesting block %s peer=%d\n", hash.ToString(), pto->id); - if (vGetData.size() >= 1000) - { - pto->PushMessage("getdata", vGetData); - vGetData.clear(); + if (!pto->fDisconnect && !pto->fClient && fFetch && state.nBlocksInFlight < MAX_BLOCKS_IN_TRANSIT_PER_PEER) { + vector vToDownload; + NodeId staller = -1; + FindNextBlocksToDownload(pto->GetId(), MAX_BLOCKS_IN_TRANSIT_PER_PEER - state.nBlocksInFlight, vToDownload, staller); + BOOST_FOREACH(CBlockIndex *pindex, vToDownload) { + vGetData.push_back(CInv(MSG_BLOCK, pindex->GetBlockHash())); + MarkBlockAsInFlight(pto->GetId(), pindex->GetBlockHash(), pindex); + LogPrint("net", "Requesting block %s peer=%d\n", pindex->GetBlockHash().ToString(), pto->id); + } + if (state.nBlocksInFlight == 0 && staller != -1) { + if (State(staller)->nStallingSince == 0) + State(staller)->nStallingSince = nNow; } } @@ -4519,12 +4585,6 @@ public: delete (*it1).second; mapBlockIndex.clear(); - // orphan blocks - std::map::iterator it2 = mapOrphanBlocks.begin(); - for (; it2 != mapOrphanBlocks.end(); it2++) - delete (*it2).second; - mapOrphanBlocks.clear(); - // orphan transactions mapOrphanTransactions.clear(); mapOrphanTransactionsByPrev.clear(); -- cgit v1.2.3 From ad6e6017127ec2a3a8d1a71aaab7a6e945c5b0f9 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sat, 12 Jul 2014 00:03:10 +0200 Subject: RPC additions after headers-first --- src/main.cpp | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 816cab7e1f..604ca670ef 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -41,6 +41,7 @@ CCriticalSection cs_main; BlockMap mapBlockIndex; CChain chainActive; +CBlockIndex *pindexBestHeader = NULL; int64_t nTimeBestReceived = 0; CWaitableCriticalSection csBestBlock; CConditionVariable cvBlockChange; @@ -51,6 +52,7 @@ bool fTxIndex = false; bool fIsBareMultisigStd = true; unsigned int nCoinCacheSize = 5000; + /** Fees smaller than this (in satoshi) are considered zero fee (for relaying and mining) */ CFeeRate minRelayTxFee = CFeeRate(1000); @@ -98,8 +100,6 @@ namespace { // The set of all CBlockIndex entries with BLOCK_VALID_TRANSACTIONS or better that are at least // as good as our current tip. Entries may be failed, though. set setBlockIndexValid; - // Best header we've seen so far (used for getheaders queries' starting points). - CBlockIndex *pindexBestHeader = NULL; // Number of nodes with fSyncStarted. int nSyncStarted = 0; // All pairs A->B, where A (or one if its ancestors) misses transactions, but B has transactions. @@ -440,6 +440,11 @@ bool GetNodeStateStats(NodeId nodeid, CNodeStateStats &stats) { return false; stats.nMisbehavior = state->nMisbehavior; stats.nSyncHeight = state->pindexBestKnownBlock ? state->pindexBestKnownBlock->nHeight : -1; + stats.nCommonHeight = state->pindexLastCommonBlock ? state->pindexLastCommonBlock->nHeight : -1; + BOOST_FOREACH(const QueuedBlock& queue, state->vBlocksInFlight) { + if (queue.pindex) + stats.vHeightInFlight.push_back(queue.pindex->nHeight); + } return true; } -- cgit v1.2.3 From f244c99c96636136678f17e7ef3952a864613ad0 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Sat, 6 Sep 2014 21:16:25 +0200 Subject: Remove CheckMinWork, as we always know all parent headers --- src/main.cpp | 17 ----------------- 1 file changed, 17 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 604ca670ef..dba4292f50 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -2329,23 +2329,6 @@ bool AcceptBlockHeader(const CBlockHeader& block, CValidationState& state, CBloc return true; } - CBlockIndex* pcheckpoint = Checkpoints::GetLastCheckpoint(); - if (pcheckpoint && block.hashPrevBlock != (chainActive.Tip() ? chainActive.Tip()->GetBlockHash() : uint256(0))) - { - // Extra checks to prevent "fill up memory by spamming with bogus blocks" - int64_t deltaTime = block.GetBlockTime() - pcheckpoint->GetBlockTime(); - if (deltaTime < 0) - { - return state.DoS(100, error("%s : block with timestamp before last checkpoint", __func__), - REJECT_CHECKPOINT, "time-too-old"); - } - if (!CheckMinWork(block.nBits, pcheckpoint->nBits, deltaTime)) - { - return state.DoS(100, error("%s : block with too little proof-of-work", __func__), - REJECT_INVALID, "bad-diffbits"); - } - } - // Get prev block index CBlockIndex* pindexPrev = NULL; int nHeight = 0; -- cgit v1.2.3 From 4c93322923130b1554937de44545d949c54a6e39 Mon Sep 17 00:00:00 2001 From: R E Broadley Date: Tue, 2 Sep 2014 17:16:32 +0700 Subject: Improve getheaders (sending) logging --- src/main.cpp | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index dba4292f50..f032882ff8 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -3610,6 +3610,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, // later (within the same cs_main lock, though). MarkBlockAsInFlight(pfrom->GetId(), inv.hash); } + LogPrint("net", "getheaders (%d) %s to peer=%d\n", pindexBestHeader->nHeight, inv.hash.ToString(), pfrom->id); } } @@ -3712,7 +3713,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, // we must use CBlocks, as CBlockHeaders won't include the 0x00 nTx count at the end vector vHeaders; int nLimit = MAX_HEADERS_RESULTS; - LogPrint("net", "getheaders %d to %s\n", (pindex ? pindex->nHeight : -1), hashStop.ToString()); + LogPrint("net", "getheaders %d to %s from peer=%d\n", (pindex ? pindex->nHeight : -1), hashStop.ToString(), pfrom->id); for (; pindex; pindex = chainActive.Next(pindex)) { vHeaders.push_back(pindex->GetBlockHeader()); @@ -3878,6 +3879,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, // Headers message had its maximum size; the peer may have more headers. // TODO: optimize: if pindexLast is an ancestor of chainActive.Tip or pindexBestHeader, continue // from there instead. + LogPrint("net", "more getheaders (%d) to end to peer=%d (startheight:%d)\n", pindexLast->nHeight, pfrom->id, pfrom->nStartingHeight); pfrom->PushMessage("getheaders", chainActive.GetLocator(pindexLast), uint256(0)); } } @@ -4381,6 +4383,7 @@ bool SendMessages(CNode* pto, bool fSendTrickle) state.fSyncStarted = true; nSyncStarted++; CBlockIndex *pindexStart = pindexBestHeader->pprev ? pindexBestHeader->pprev : pindexBestHeader; + LogPrint("net", "initial getheaders (%d) to peer=%d (startheight:%d)\n", pindexStart->nHeight, pto->id, pto->nStartingHeight); pto->PushMessage("getheaders", chainActive.GetLocator(pindexStart), uint256(0)); } } -- cgit v1.2.3 From 1bcee67ee780bc44d22b2e44783a04bc330d4f1f Mon Sep 17 00:00:00 2001 From: R E Broadley Date: Thu, 4 Sep 2014 01:31:01 +0700 Subject: Better logging of stalling --- src/main.cpp | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index f032882ff8..c5ad82c14e 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -4468,8 +4468,10 @@ bool SendMessages(CNode* pto, bool fSendTrickle) LogPrint("net", "Requesting block %s peer=%d\n", pindex->GetBlockHash().ToString(), pto->id); } if (state.nBlocksInFlight == 0 && staller != -1) { - if (State(staller)->nStallingSince == 0) + if (State(staller)->nStallingSince == 0) { State(staller)->nStallingSince = nNow; + LogPrint("net", "Stall started peer=%d\n", staller); + } } } -- cgit v1.2.3 From 1af838b3393ac3d4f6b75ef56f907cb760695952 Mon Sep 17 00:00:00 2001 From: R E Broadley Date: Fri, 5 Sep 2014 22:32:22 +0700 Subject: Add height to "Requesting block" debug --- src/main.cpp | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index c5ad82c14e..a2e50b2934 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -4465,7 +4465,8 @@ bool SendMessages(CNode* pto, bool fSendTrickle) BOOST_FOREACH(CBlockIndex *pindex, vToDownload) { vGetData.push_back(CInv(MSG_BLOCK, pindex->GetBlockHash())); MarkBlockAsInFlight(pto->GetId(), pindex->GetBlockHash(), pindex); - LogPrint("net", "Requesting block %s peer=%d\n", pindex->GetBlockHash().ToString(), pto->id); + LogPrint("net", "Requesting block %s (%d) peer=%d\n", pindex->GetBlockHash().ToString(), + pindex->nHeight, pto->id); } if (state.nBlocksInFlight == 0 && staller != -1) { if (State(staller)->nStallingSince == 0) { -- cgit v1.2.3 From e17bd58392bb81d5343d0b73e4aa6b113f5828f9 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Mon, 6 Oct 2014 08:31:33 +0200 Subject: Rename setBlockIndexValid to setBlockIndexCandidates --- src/main.cpp | 30 +++++++++++++++--------------- 1 file changed, 15 insertions(+), 15 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index a2e50b2934..bb16b716dc 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -99,7 +99,7 @@ namespace { // The set of all CBlockIndex entries with BLOCK_VALID_TRANSACTIONS or better that are at least // as good as our current tip. Entries may be failed, though. - set setBlockIndexValid; + set setBlockIndexCandidates; // Number of nodes with fSyncStarted. int nSyncStarted = 0; // All pairs A->B, where A (or one if its ancestors) misses transactions, but B has transactions. @@ -1318,7 +1318,7 @@ void static InvalidBlockFound(CBlockIndex *pindex, const CValidationState &state if (!state.CorruptionPossible()) { pindex->nStatus |= BLOCK_FAILED_VALID; pblocktree->WriteBlockIndex(CDiskBlockIndex(pindex)); - setBlockIndexValid.erase(pindex); + setBlockIndexCandidates.erase(pindex); InvalidChainFound(pindex); } } @@ -1918,8 +1918,8 @@ static CBlockIndex* FindMostWorkChain() { // Find the best candidate header. { - std::set::reverse_iterator it = setBlockIndexValid.rbegin(); - if (it == setBlockIndexValid.rend()) + std::set::reverse_iterator it = setBlockIndexCandidates.rbegin(); + if (it == setBlockIndexCandidates.rend()) return NULL; pindexNew = *it; } @@ -1938,10 +1938,10 @@ static CBlockIndex* FindMostWorkChain() { CBlockIndex *pindexFailed = pindexNew; while (pindexTest != pindexFailed) { pindexFailed->nStatus |= BLOCK_FAILED_CHILD; - setBlockIndexValid.erase(pindexFailed); + setBlockIndexCandidates.erase(pindexFailed); pindexFailed = pindexFailed->pprev; } - setBlockIndexValid.erase(pindexTest); + setBlockIndexCandidates.erase(pindexTest); fInvalidAncestor = true; break; } @@ -1990,15 +1990,15 @@ static bool ActivateBestChainStep(CValidationState &state, CBlockIndex *pindexMo return false; } } else { - // Delete all entries in setBlockIndexValid that are worse than our new current block. + // Delete all entries in setBlockIndexCandidates that are worse than our new current block. // Note that we can't delete the current block itself, as we may need to return to it later in case a // reorganization to a better block fails. - std::set::iterator it = setBlockIndexValid.begin(); - while (setBlockIndexValid.value_comp()(*it, chainActive.Tip())) { - setBlockIndexValid.erase(it++); + std::set::iterator it = setBlockIndexCandidates.begin(); + while (setBlockIndexCandidates.value_comp()(*it, chainActive.Tip())) { + setBlockIndexCandidates.erase(it++); } - // Either the current tip or a successor of it we're working towards is left in setBlockIndexValid. - assert(!setBlockIndexValid.empty()); + // Either the current tip or a successor of it we're working towards is left in setBlockIndexCandidates. + assert(!setBlockIndexCandidates.empty()); if (!pindexOldTip || chainActive.Tip()->nChainWork > pindexOldTip->nChainWork) { // We're in a better position than we were. Return temporarily to release the lock. break; @@ -2123,7 +2123,7 @@ bool ReceivedBlockTransactions(const CBlock &block, CValidationState& state, CBl CBlockIndex *pindex = queue.front(); queue.pop_front(); pindex->nChainTx = (pindex->pprev ? pindex->pprev->nChainTx : 0) + pindex->nTx; - setBlockIndexValid.insert(pindex); + setBlockIndexCandidates.insert(pindex); std::pair::iterator, std::multimap::iterator> range = mapBlocksUnlinked.equal_range(pindex); while (range.first != range.second) { std::multimap::iterator it = range.first; @@ -2803,7 +2803,7 @@ bool static LoadBlockIndexDB() } } if (pindex->IsValid(BLOCK_VALID_TRANSACTIONS) && (pindex->nChainTx || pindex->pprev == NULL)) - setBlockIndexValid.insert(pindex); + setBlockIndexCandidates.insert(pindex); if (pindex->nStatus & BLOCK_FAILED_MASK && (!pindexBestInvalid || pindex->nChainWork > pindexBestInvalid->nChainWork)) pindexBestInvalid = pindex; if (pindex->pprev) @@ -2947,7 +2947,7 @@ bool CVerifyDB::VerifyDB(CCoinsView *coinsview, int nCheckLevel, int nCheckDepth void UnloadBlockIndex() { mapBlockIndex.clear(); - setBlockIndexValid.clear(); + setBlockIndexCandidates.clear(); chainActive.SetTip(NULL); pindexBestInvalid = NULL; } -- cgit v1.2.3 From ad96e7ccd94679d9125a436ceb5b476aacdfca82 Mon Sep 17 00:00:00 2001 From: "Wladimir J. van der Laan" Date: Tue, 7 Oct 2014 18:06:30 +0200 Subject: Make -reindex cope with out-of-order blocks Remember out-of-order block headers along with disk positions. This is likely the simplest and least-impact way to make -reindex work with headers first. Based on top of #4468. --- src/main.cpp | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 54 insertions(+), 8 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index bb16b716dc..ad133e1bb8 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -3070,6 +3070,8 @@ void PrintBlockTree() bool LoadExternalBlockFile(FILE* fileIn, CDiskBlockPos *dbp) { + // Map of disk positions for blocks with unknown parent (only used for reindex) + static std::multimap mapBlocksUnknownParent; int64_t nStart = GetTimeMillis(); int nLoaded = 0; @@ -3112,20 +3114,64 @@ bool LoadExternalBlockFile(FILE* fileIn, CDiskBlockPos *dbp) try { // read block uint64_t nBlockPos = blkdat.GetPos(); + if (nBlockPos < nStartByte) // skip already indexed part + continue; + if (dbp) + dbp->nPos = nBlockPos; blkdat.SetLimit(nBlockPos + nSize); + + // read block header + CBlockHeader blockhdr; + blkdat >> blockhdr; + nRewind = blkdat.GetPos(); + + // process block header + uint256 hash = blockhdr.GetHash(); + if (hash != Params().HashGenesisBlock() && mapBlockIndex.find(blockhdr.hashPrevBlock) == mapBlockIndex.end()) { + LogPrint("reindex", "%s: Out of order block %s, parent %s not known\n", __func__, hash.ToString(), + blockhdr.hashPrevBlock.ToString()); + if (dbp) + mapBlocksUnknownParent.insert(std::make_pair(blockhdr.hashPrevBlock, *dbp)); + // TODO a slight optimization would be: blkdat.Skip(nSize - 80) + continue; + } + + // read block + blkdat.SetPos(nBlockPos); CBlock block; blkdat >> block; nRewind = blkdat.GetPos(); // process block - if (nBlockPos >= nStartByte) { - if (dbp) - dbp->nPos = nBlockPos; - CValidationState state; - if (ProcessBlock(state, NULL, &block, dbp)) - nLoaded++; - if (state.IsError()) - break; + CValidationState state; + if (ProcessBlock(state, NULL, &block, dbp)) + nLoaded++; + if (state.IsError()) + break; + + // Recursively process earlier encountered successors of this block + deque queue; + queue.push_back(hash); + while (!queue.empty()) { + uint256 head = queue.front(); + queue.pop_front(); + std::pair::iterator, std::multimap::iterator> range = mapBlocksUnknownParent.equal_range(head); + while (range.first != range.second) { + std::multimap::iterator it = range.first; + if (ReadBlockFromDisk(block, it->second)) + { + LogPrintf("%s: Processing out of order child %s of %s\n", __func__, block.GetHash().ToString(), + head.ToString()); + CValidationState dummy; + if (ProcessBlock(dummy, NULL, &block, &it->second)) + { + nLoaded++; + queue.push_back(block.GetHash()); + } + } + range.first++; + mapBlocksUnknownParent.erase(it); + } } } catch (std::exception &e) { LogPrintf("%s : Deserialize or I/O error - %s", __func__, e.what()); -- cgit v1.2.3 From 16d5194165c8c83492b95f431a664d98c40ff254 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 7 Oct 2014 21:15:32 +0200 Subject: Skip reindexed blocks individually Instead of skipping to the last reindexed block in each file (which could jump over processed out-of-order blocks), just skip each already processed block individually. --- src/main.cpp | 49 ++++++++++++++++--------------------------------- 1 file changed, 16 insertions(+), 33 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index ad133e1bb8..908f4c95b6 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -3078,15 +3078,6 @@ bool LoadExternalBlockFile(FILE* fileIn, CDiskBlockPos *dbp) try { // This takes over fileIn and calls fclose() on it in the CBufferedFile destructor CBufferedFile blkdat(fileIn, 2*MAX_BLOCK_SIZE, MAX_BLOCK_SIZE+8, SER_DISK, CLIENT_VERSION); - uint64_t nStartByte = 0; - if (dbp) { - // (try to) skip already indexed part - CBlockFileInfo info; - if (pblocktree->ReadBlockFileInfo(dbp->nFile, info)) { - nStartByte = info.nSize; - blkdat.Seek(info.nSize); - } - } uint64_t nRewind = blkdat.GetPos(); while (!blkdat.eof()) { boost::this_thread::interruption_point(); @@ -3114,40 +3105,32 @@ bool LoadExternalBlockFile(FILE* fileIn, CDiskBlockPos *dbp) try { // read block uint64_t nBlockPos = blkdat.GetPos(); - if (nBlockPos < nStartByte) // skip already indexed part - continue; if (dbp) dbp->nPos = nBlockPos; blkdat.SetLimit(nBlockPos + nSize); - - // read block header - CBlockHeader blockhdr; - blkdat >> blockhdr; + blkdat.SetPos(nBlockPos); + CBlock block; + blkdat >> block; nRewind = blkdat.GetPos(); - // process block header - uint256 hash = blockhdr.GetHash(); - if (hash != Params().HashGenesisBlock() && mapBlockIndex.find(blockhdr.hashPrevBlock) == mapBlockIndex.end()) { + // detect out of order blocks, and store them for later + uint256 hash = block.GetHash(); + if (hash != Params().HashGenesisBlock() && mapBlockIndex.find(block.hashPrevBlock) == mapBlockIndex.end()) { LogPrint("reindex", "%s: Out of order block %s, parent %s not known\n", __func__, hash.ToString(), - blockhdr.hashPrevBlock.ToString()); + block.hashPrevBlock.ToString()); if (dbp) - mapBlocksUnknownParent.insert(std::make_pair(blockhdr.hashPrevBlock, *dbp)); - // TODO a slight optimization would be: blkdat.Skip(nSize - 80) + mapBlocksUnknownParent.insert(std::make_pair(block.hashPrevBlock, *dbp)); continue; } - // read block - blkdat.SetPos(nBlockPos); - CBlock block; - blkdat >> block; - nRewind = blkdat.GetPos(); - - // process block - CValidationState state; - if (ProcessBlock(state, NULL, &block, dbp)) - nLoaded++; - if (state.IsError()) - break; + // process in case the block isn't known yet + if (mapBlockIndex.count(hash) == 0) { + CValidationState state; + if (ProcessBlock(state, NULL, &block, dbp)) + nLoaded++; + if (state.IsError()) + break; + } // Recursively process earlier encountered successors of this block deque queue; -- cgit v1.2.3 From afc32c5eeada01b141706e32f0405bdb86c00f04 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Fri, 10 Oct 2014 13:13:47 -0700 Subject: Fix rebuild-chainstate feature and improve its performance Previous refactorings broke the ability to rebuild the chainstate by deleting the chainstate directory, resulting in an incorrect "Incorrect or no genesis block found" error message. Fix that. Also, improve the performance of ActivateBestBlockStep by using the skiplist to only discover a few potential blocks to connect at a time, instead of all blocks forever - as we likely bail out after connecting a single one anyway. --- src/main.cpp | 17 ++++++++++++++--- 1 file changed, 14 insertions(+), 3 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 908f4c95b6..0612f584ac 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -1968,12 +1968,20 @@ static bool ActivateBestChainStep(CValidationState &state, CBlockIndex *pindexMo // Build list of new blocks to connect. std::vector vpindexToConnect; - vpindexToConnect.reserve(pindexMostWork->nHeight - (pindexFork ? pindexFork->nHeight : -1)); - CBlockIndex *pindexIter = pindexMostWork; - while (pindexIter && pindexIter != pindexFork) { + bool fContinue = true; + int nHeight = pindexFork ? pindexFork->nHeight : -1; + while (fContinue && nHeight != pindexMostWork->nHeight) { + // Don't iterate the entire list of potential improvements toward the best tip, as we likely only need + // a few blocks along the way. + int nTargetHeight = std::min(nHeight + 32, pindexMostWork->nHeight); + vpindexToConnect.clear(); + vpindexToConnect.reserve(nTargetHeight - nHeight); + CBlockIndex *pindexIter = pindexMostWork->GetAncestor(nTargetHeight); + while (pindexIter && pindexIter->nHeight != nHeight) { vpindexToConnect.push_back(pindexIter); pindexIter = pindexIter->pprev; } + nHeight = nTargetHeight; // Connect new blocks. BOOST_REVERSE_FOREACH(CBlockIndex *pindexConnect, vpindexToConnect) { @@ -1984,6 +1992,7 @@ static bool ActivateBestChainStep(CValidationState &state, CBlockIndex *pindexMo InvalidChainFound(vpindexToConnect.back()); state = CValidationState(); fInvalidFound = true; + fContinue = false; break; } else { // A system error occurred (disk space, database error, ...). @@ -2001,10 +2010,12 @@ static bool ActivateBestChainStep(CValidationState &state, CBlockIndex *pindexMo assert(!setBlockIndexCandidates.empty()); if (!pindexOldTip || chainActive.Tip()->nChainWork > pindexOldTip->nChainWork) { // We're in a better position than we were. Return temporarily to release the lock. + fContinue = false; break; } } } + } // Callbacks/notifications for a new best chain. if (fInvalidFound) -- cgit v1.2.3 From e11b2ce4c63b87efa60b163b50d155969ccd7e08 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 14 Oct 2014 15:41:23 -0700 Subject: Fix large reorgs --- src/main.cpp | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'src/main.cpp') diff --git a/src/main.cpp b/src/main.cpp index 0612f584ac..f5fd7561c6 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -385,10 +385,11 @@ void FindNextBlocksToDownload(NodeId nodeid, unsigned int count, std::vector vToFetch; CBlockIndex *pindexWalk = state->pindexLastCommonBlock; - // Never fetch further than the best block we know the peer has, or more than BLOCK_DOWNLOAD_WINDOW + 1 beyond our - // current tip. The +1 is so we can detect stalling, namely if we would be able to download that next block if the - // window were 1 larger. - int nMaxHeight = std::min(state->pindexBestKnownBlock->nHeight, chainActive.Height() + BLOCK_DOWNLOAD_WINDOW + 1); + // Never fetch further than the best block we know the peer has, or more than BLOCK_DOWNLOAD_WINDOW + 1 beyond the last + // linked block we have in common with this peer. The +1 is so we can detect stalling, namely if we would be able to + // download that next block if the window were 1 larger. + int nWindowEnd = state->pindexLastCommonBlock->nHeight + BLOCK_DOWNLOAD_WINDOW; + int nMaxHeight = std::min(state->pindexBestKnownBlock->nHeight, nWindowEnd + 1); NodeId waitingfor = -1; while (pindexWalk->nHeight < nMaxHeight) { // Read up to 128 (or more, if more blocks than that are needed) successors of pindexWalk (towards @@ -411,7 +412,7 @@ void FindNextBlocksToDownload(NodeId nodeid, unsigned int count, std::vectorpindexLastCommonBlock = pindex; } else if (mapBlocksInFlight.count(pindex->GetBlockHash()) == 0) { // The block is not already downloaded, and not yet in flight. - if (pindex->nHeight > chainActive.Height() + (int)BLOCK_DOWNLOAD_WINDOW) { + if (pindex->nHeight > nWindowEnd) { // We reached the end of the window. if (vBlocks.size() == 0 && waitingfor != nodeid) { // We aren't able to fetch anything, but we would be if the download window was one larger. -- cgit v1.2.3