From 50262d89531692473ff557c1061aee22aa4cca1c Mon Sep 17 00:00:00 2001 From: Suhas Daftuar Date: Tue, 18 Nov 2014 22:16:32 +0100 Subject: Allow block announcements with headers This replaces using inv messages to announce new blocks, when a peer requests (via the new "sendheaders" message) that blocks be announced with headers instead of inv's. Since headers-first was introduced, peers send getheaders messages in response to an inv, which requires generating a block locator that is large compared to the size of the header being requested, and requires an extra round-trip before a reorg can be relayed. Save time by tracking headers that a peer is likely to know about, and send a headers chain that would connect to a peer's known headers, unless the chain would be too big, in which case we revert to sending an inv instead. Based off of @sipa's commit to announce all blocks in a reorg via inv, which has been squashed into this commit. Rebased-by: Pieter Wuille --- src/chain.cpp | 3 + src/main.cpp | 223 +++++++++++++++++++++++++++++++++++++++++++++++++++++++--- src/main.h | 3 + src/net.h | 9 +++ src/version.h | 5 +- 5 files changed, 232 insertions(+), 11 deletions(-) (limited to 'src') diff --git a/src/chain.cpp b/src/chain.cpp index 5b8ce076c4..3450ed6c3f 100644 --- a/src/chain.cpp +++ b/src/chain.cpp @@ -51,6 +51,9 @@ CBlockLocator CChain::GetLocator(const CBlockIndex *pindex) const { } const CBlockIndex *CChain::FindFork(const CBlockIndex *pindex) const { + if (pindex == NULL) { + return NULL; + } if (pindex->nHeight > Height()) pindex = pindex->GetAncestor(Height()); while (pindex && !Contains(pindex)) diff --git a/src/main.cpp b/src/main.cpp index 94fcd6223b..31913956b7 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -247,6 +247,8 @@ struct CNodeState { uint256 hashLastUnknownBlock; //! The last full block we both have. CBlockIndex *pindexLastCommonBlock; + //! The best header we have sent our peer. + CBlockIndex *pindexBestHeaderSent; //! Whether we've started headers synchronization with this peer. bool fSyncStarted; //! Since when we're stalling block download progress (in microseconds), or 0. @@ -256,6 +258,8 @@ struct CNodeState { int nBlocksInFlightValidHeaders; //! Whether we consider this a preferred download peer. bool fPreferredDownload; + //! Whether this peer wants invs or headers (when possible) for block announcements. + bool fPreferHeaders; CNodeState() { fCurrentlyConnected = false; @@ -264,11 +268,13 @@ struct CNodeState { pindexBestKnownBlock = NULL; hashLastUnknownBlock.SetNull(); pindexLastCommonBlock = NULL; + pindexBestHeaderSent = NULL; fSyncStarted = false; nStallingSince = 0; nBlocksInFlight = 0; nBlocksInFlightValidHeaders = 0; fPreferredDownload = false; + fPreferHeaders = false; } }; @@ -398,6 +404,22 @@ void UpdateBlockAvailability(NodeId nodeid, const uint256 &hash) { } } +// Requires cs_main +bool CanDirectFetch(const Consensus::Params &consensusParams) +{ + return chainActive.Tip()->GetBlockTime() > GetAdjustedTime() - consensusParams.nPowTargetSpacing * 20; +} + +// Requires cs_main +bool PeerHasHeader(CNodeState *state, CBlockIndex *pindex) +{ + if (state->pindexBestKnownBlock && pindex == state->pindexBestKnownBlock->GetAncestor(pindex->nHeight)) + return true; + if (state->pindexBestHeaderSent && pindex == state->pindexBestHeaderSent->GetAncestor(pindex->nHeight)) + return true; + return false; +} + /** Find the last common ancestor two blocks have. * Both pa and pb must be non-NULL. */ CBlockIndex* LastCommonAncestor(CBlockIndex* pa, CBlockIndex* pb) { @@ -2557,16 +2579,17 @@ static bool ActivateBestChainStep(CValidationState& state, const CChainParams& c * or an activated best chain. pblock is either NULL or a pointer to a block * that is already loaded (to avoid loading it again from disk). */ -bool ActivateBestChain(CValidationState& state, const CChainParams& chainparams, const CBlock* pblock) -{ - CBlockIndex *pindexNewTip = NULL; +bool ActivateBestChain(CValidationState &state, const CChainParams& chainparams, const CBlock *pblock) { CBlockIndex *pindexMostWork = NULL; do { boost::this_thread::interruption_point(); + CBlockIndex *pindexNewTip = NULL; + const CBlockIndex *pindexFork; bool fInitialDownload; { LOCK(cs_main); + CBlockIndex *pindexOldTip = chainActive.Tip(); pindexMostWork = FindMostWorkChain(); // Whether we have anything to do at all. @@ -2577,26 +2600,44 @@ bool ActivateBestChain(CValidationState& state, const CChainParams& chainparams, return false; pindexNewTip = chainActive.Tip(); + pindexFork = chainActive.FindFork(pindexOldTip); fInitialDownload = IsInitialBlockDownload(); } // When we reach this point, we switched to a new tip (stored in pindexNewTip). // Notifications/callbacks that can run without cs_main if (!fInitialDownload) { - uint256 hashNewTip = pindexNewTip->GetBlockHash(); + // Find the hashes of all blocks that weren't previously in the best chain. + std::vector vHashes; + CBlockIndex *pindexToAnnounce = pindexNewTip; + while (pindexToAnnounce != pindexFork) { + vHashes.push_back(pindexToAnnounce->GetBlockHash()); + pindexToAnnounce = pindexToAnnounce->pprev; + if (vHashes.size() == MAX_BLOCKS_TO_ANNOUNCE) { + // Limit announcements in case of a huge reorganization. + // Rely on the peer's synchronization mechanism in that case. + break; + } + } // Relay inventory, but don't relay old inventory during initial block download. int nBlockEstimate = 0; if (fCheckpointsEnabled) nBlockEstimate = Checkpoints::GetTotalBlocksEstimate(chainparams.Checkpoints()); { LOCK(cs_vNodes); - BOOST_FOREACH(CNode* pnode, vNodes) - if (chainActive.Height() > (pnode->nStartingHeight != -1 ? pnode->nStartingHeight - 2000 : nBlockEstimate)) - pnode->PushInventory(CInv(MSG_BLOCK, hashNewTip)); + BOOST_FOREACH(CNode* pnode, vNodes) { + if (chainActive.Height() > (pnode->nStartingHeight != -1 ? pnode->nStartingHeight - 2000 : nBlockEstimate)) { + BOOST_REVERSE_FOREACH(const uint256& hash, vHashes) { + pnode->PushBlockHash(hash); + } + } + } } // Notify external listeners about the new tip. - GetMainSignals().UpdatedBlockTip(pindexNewTip); - uiInterface.NotifyBlockTip(hashNewTip); + if (!vHashes.empty()) { + GetMainSignals().UpdatedBlockTip(pindexNewTip); + uiInterface.NotifyBlockTip(vHashes.front()); + } } } while(pindexMostWork != chainActive.Tip()); CheckBlockIndex(chainparams.GetConsensus()); @@ -4333,6 +4374,14 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, LOCK(cs_main); State(pfrom->GetId())->fCurrentlyConnected = true; } + + if (pfrom->nVersion >= SENDHEADERS_VERSION) { + // Tell our peer we prefer to receive headers rather than inv's + // We send this to non-NODE NETWORK peers as well, because even + // non-NODE NETWORK peers can announce blocks (such as pruning + // nodes) + pfrom->PushMessage("sendheaders"); + } } @@ -4402,6 +4451,12 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, pfrom->fDisconnect = true; } + else if (strCommand == "sendheaders") + { + LOCK(cs_main); + State(pfrom->GetId())->fPreferHeaders = true; + } + else if (strCommand == "inv") { @@ -4446,7 +4501,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, // not a direct successor. pfrom->PushMessage("getheaders", chainActive.GetLocator(pindexBestHeader), inv.hash); CNodeState *nodestate = State(pfrom->GetId()); - if (chainActive.Tip()->GetBlockTime() > GetAdjustedTime() - chainparams.GetConsensus().nPowTargetSpacing * 20 && + if (CanDirectFetch(chainparams.GetConsensus()) && nodestate->nBlocksInFlight < MAX_BLOCKS_IN_TRANSIT_PER_PEER) { vToFetch.push_back(inv); // Mark block as in flight already, even though the actual "getdata" message only goes out @@ -4554,6 +4609,8 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, LogPrint("net", "Ignoring getheaders from peer=%d because node is in initial block download\n", pfrom->id); return true; } + + CNodeState *nodestate = State(pfrom->GetId()); CBlockIndex* pindex = NULL; if (locator.IsNull()) { @@ -4581,6 +4638,11 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, if (--nLimit <= 0 || pindex->GetBlockHash() == hashStop) break; } + // pindex can be NULL either if we sent chainActive.Tip() OR + // if our peer has chainActive.Tip() (and thus we are sending an empty + // headers message). In both cases it's safe to update + // pindexBestHeaderSent to be our tip. + nodestate->pindexBestHeaderSent = pindex ? pindex : chainActive.Tip(); pfrom->PushMessage("headers", vHeaders); } @@ -4772,6 +4834,53 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv, pfrom->PushMessage("getheaders", chainActive.GetLocator(pindexLast), uint256()); } + bool fCanDirectFetch = CanDirectFetch(chainparams.GetConsensus()); + CNodeState *nodestate = State(pfrom->GetId()); + // If this set of headers is valid and ends in a block with at least as + // much work as our tip, download as much as possible. + if (fCanDirectFetch && pindexLast->IsValid(BLOCK_VALID_TREE) && chainActive.Tip()->nChainWork <= pindexLast->nChainWork) { + vector vToFetch; + CBlockIndex *pindexWalk = pindexLast; + // Calculate all the blocks we'd need to switch to pindexLast, up to a limit. + while (pindexWalk && !chainActive.Contains(pindexWalk) && vToFetch.size() <= MAX_BLOCKS_IN_TRANSIT_PER_PEER) { + if (!(pindexWalk->nStatus & BLOCK_HAVE_DATA) && + !mapBlocksInFlight.count(pindexWalk->GetBlockHash())) { + // We don't have this block, and it's not yet in flight. + vToFetch.push_back(pindexWalk); + } + pindexWalk = pindexWalk->pprev; + } + // If pindexWalk still isn't on our main chain, we're looking at a + // very large reorg at a time we think we're close to caught up to + // the main chain -- this shouldn't really happen. Bail out on the + // direct fetch and rely on parallel download instead. + if (!chainActive.Contains(pindexWalk)) { + LogPrint("net", "Large reorg, won't direct fetch to %s (%d)\n", + pindexLast->GetBlockHash().ToString(), + pindexLast->nHeight); + } else { + vector vGetData; + // Download as much as possible, from earliest to latest. + BOOST_REVERSE_FOREACH(CBlockIndex *pindex, vToFetch) { + if (nodestate->nBlocksInFlight >= MAX_BLOCKS_IN_TRANSIT_PER_PEER) { + // Can't download any more from this peer + break; + } + vGetData.push_back(CInv(MSG_BLOCK, pindex->GetBlockHash())); + MarkBlockAsInFlight(pfrom->GetId(), pindex->GetBlockHash(), chainparams.GetConsensus(), pindex); + LogPrint("net", "Requesting block %s from peer=%d\n", + pindex->GetBlockHash().ToString(), pfrom->id); + } + if (vGetData.size() > 1) { + LogPrint("net", "Downloading blocks toward %s (%d) via headers direct fetch\n", + pindexLast->GetBlockHash().ToString(), pindexLast->nHeight); + } + if (vGetData.size() > 0) { + pfrom->PushMessage("getdata", vGetData); + } + } + } + CheckBlockIndex(chainparams.GetConsensus()); } @@ -5297,6 +5406,100 @@ bool SendMessages(CNode* pto, bool fSendTrickle) GetMainSignals().Broadcast(nTimeBestReceived); } + // + // Try sending block announcements via headers + // + { + // If we have less than MAX_BLOCKS_TO_ANNOUNCE in our + // list of block hashes we're relaying, and our peer wants + // headers announcements, then find the first header + // not yet known to our peer but would connect, and send. + // If no header would connect, or if we have too many + // blocks, or if the peer doesn't want headers, just + // add all to the inv queue. + LOCK(pto->cs_inventory); + vector vHeaders; + bool fRevertToInv = (!state.fPreferHeaders || pto->vBlockHashesToAnnounce.size() > MAX_BLOCKS_TO_ANNOUNCE); + CBlockIndex *pBestIndex = NULL; // last header queued for delivery + ProcessBlockAvailability(pto->id); // ensure pindexBestKnownBlock is up-to-date + + if (!fRevertToInv) { + bool fFoundStartingHeader = false; + // Try to find first header that our peer doesn't have, and + // then send all headers past that one. If we come across any + // headers that aren't on chainActive, give up. + BOOST_FOREACH(const uint256 &hash, pto->vBlockHashesToAnnounce) { + BlockMap::iterator mi = mapBlockIndex.find(hash); + assert(mi != mapBlockIndex.end()); + CBlockIndex *pindex = mi->second; + if (chainActive[pindex->nHeight] != pindex) { + // Bail out if we reorged away from this block + fRevertToInv = true; + break; + } + assert(pBestIndex == NULL || pindex->pprev == pBestIndex); + pBestIndex = pindex; + if (fFoundStartingHeader) { + // add this to the headers message + vHeaders.push_back(pindex->GetBlockHeader()); + } else if (PeerHasHeader(&state, pindex)) { + continue; // keep looking for the first new block + } else if (pindex->pprev == NULL || PeerHasHeader(&state, pindex->pprev)) { + // Peer doesn't have this header but they do have the prior one. + // Start sending headers. + fFoundStartingHeader = true; + vHeaders.push_back(pindex->GetBlockHeader()); + } else { + // Peer doesn't have this header or the prior one -- nothing will + // connect, so bail out. + fRevertToInv = true; + break; + } + } + } + if (fRevertToInv) { + // If falling back to using an inv, just try to inv the tip. + // The last entry in vBlockHashesToAnnounce was our tip at some point + // in the past. + if (!pto->vBlockHashesToAnnounce.empty()) { + const uint256 &hashToAnnounce = pto->vBlockHashesToAnnounce.back(); + BlockMap::iterator mi = mapBlockIndex.find(hashToAnnounce); + assert(mi != mapBlockIndex.end()); + CBlockIndex *pindex = mi->second; + + // Warn if we're announcing a block that is not on the main chain. + // This should be very rare and could be optimized out. + // Just log for now. + if (chainActive[pindex->nHeight] != pindex) { + LogPrint("net", "Announcing block %s not on main chain (tip=%s)\n", + hashToAnnounce.ToString(), chainActive.Tip()->GetBlockHash().ToString()); + } + + // If the peer announced this block to us, don't inv it back. + // (Since block announcements may not be via inv's, we can't solely rely on + // setInventoryKnown to track this.) + if (!PeerHasHeader(&state, pindex)) { + pto->PushInventory(CInv(MSG_BLOCK, hashToAnnounce)); + LogPrint("net", "%s: sending inv peer=%d hash=%s\n", __func__, + pto->id, hashToAnnounce.ToString()); + } + } + } else if (!vHeaders.empty()) { + if (vHeaders.size() > 1) { + LogPrint("net", "%s: %u headers, range (%s, %s), to peer=%d\n", __func__, + vHeaders.size(), + vHeaders.front().GetHash().ToString(), + vHeaders.back().GetHash().ToString(), pto->id); + } else { + LogPrint("net", "%s: sending header %s to peer=%d\n", __func__, + vHeaders.front().GetHash().ToString(), pto->id); + } + pto->PushMessage("headers", vHeaders); + state.pindexBestHeaderSent = pBestIndex; + } + pto->vBlockHashesToAnnounce.clear(); + } + // // Message: inventory // diff --git a/src/main.h b/src/main.h index dfa2fcb537..3dec613fc7 100644 --- a/src/main.h +++ b/src/main.h @@ -98,6 +98,9 @@ static const unsigned int DEFAULT_BANSCORE_THRESHOLD = 100; static const bool DEFAULT_TESTSAFEMODE = false; +/** Maximum number of headers to announce when relaying blocks with headers message.*/ +static const unsigned int MAX_BLOCKS_TO_ANNOUNCE = 8; + struct BlockHasher { size_t operator()(const uint256& hash) const { return hash.GetCheapHash(); } diff --git a/src/net.h b/src/net.h index 3664ce9a70..fb299fb0b4 100644 --- a/src/net.h +++ b/src/net.h @@ -390,6 +390,9 @@ public: std::vector vInventoryToSend; CCriticalSection cs_inventory; std::multimap mapAskFor; + // Used for headers announcements - unfiltered blocks to relay + // Also protected by cs_inventory + std::vector vBlockHashesToAnnounce; // Ping time measurement: // The pong reply we're expecting, or 0 if no pong expected. @@ -504,6 +507,12 @@ public: } } + void PushBlockHash(const uint256 &hash) + { + LOCK(cs_inventory); + vBlockHashesToAnnounce.push_back(hash); + } + void AskFor(const CInv& inv); // TODO: Document the postcondition of this function. Is cs_vSend locked? diff --git a/src/version.h b/src/version.h index 6cdddf9255..f7cf18d0b6 100644 --- a/src/version.h +++ b/src/version.h @@ -9,7 +9,7 @@ * network protocol versioning */ -static const int PROTOCOL_VERSION = 70011; +static const int PROTOCOL_VERSION = 70012; //! initial proto version, to be increased after version/verack negotiation static const int INIT_PROTO_VERSION = 209; @@ -37,4 +37,7 @@ static const int MEMPOOL_GD_VERSION = 60002; //! "filter*" commands are disabled without NODE_BLOOM after and including this version static const int NO_BLOOM_VERSION = 70011; +//! "sendheaders" command and announcing blocks with headers starts with this version +static const int SENDHEADERS_VERSION = 70012; + #endif // BITCOIN_VERSION_H -- cgit v1.2.3