diff --git a/src/avalanche.cpp b/src/avalanche.cpp index d8251f9637..6a32df6ba3 100644 --- a/src/avalanche.cpp +++ b/src/avalanche.cpp @@ -1,164 +1,180 @@ // Copyright (c) 2018 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "avalanche.h" #include "chain.h" #include "netmessagemaker.h" #include "scheduler.h" #include "validation.h" #include bool AvalancheProcessor::addBlockToReconcile(const CBlockIndex *pindex) { return vote_records.getWriteView() ->insert(std::make_pair(pindex, VoteRecord())) .second; } static const VoteRecord * GetRecord(const RWCollection &vote_records, const CBlockIndex *pindex) { auto r = vote_records.getReadView(); auto it = r->find(pindex); if (it == r.end()) { return nullptr; } return &it->second; } bool AvalancheProcessor::isAccepted(const CBlockIndex *pindex) const { if (auto vr = GetRecord(vote_records, pindex)) { - return vr->isValid(); + return vr->isAccepted(); } return false; } -bool AvalancheProcessor::hasFinalized(const CBlockIndex *pindex) const { - if (auto vr = GetRecord(vote_records, pindex)) { - return vr->hasFinalized(); - } - - return false; -} - -bool AvalancheProcessor::registerVotes(const AvalancheResponse &response) { +bool AvalancheProcessor::registerVotes( + const AvalancheResponse &response, + std::vector &updates) { const std::vector &votes = response.GetVotes(); - std::map responseIndex; + std::map responseIndex; { LOCK(cs_main); for (auto &v : votes) { BlockMap::iterator mi = mapBlockIndex.find(v.GetHash()); if (mi == mapBlockIndex.end()) { // This should not happen, but just in case... continue; } responseIndex.insert(std::make_pair(mi->second, v)); } } { // Register votes. auto w = vote_records.getWriteView(); for (auto &p : responseIndex) { - const CBlockIndex *pindex = p.first; + CBlockIndex *pindex = p.first; const AvalancheVote &v = p.second; auto it = w->find(pindex); if (it == w.end()) { // We are not voting on that item anymore. continue; } - it->second.registerVote(v.IsValid()); + auto &vr = it->second; + if (!vr.registerVote(v.IsValid())) { + // This vote did not provide any extra information, move on. + continue; + } + + if (!vr.hasFinalized()) { + // This item has note been finalized, so we have nothing more to + // do. + updates.emplace_back( + pindex, + vr.isAccepted() ? AvalancheBlockUpdate::Status::Accepted + : AvalancheBlockUpdate::Status::Rejected); + continue; + } + + // We just finalized a vote. If it is valid, then let the caller + // know. Either way, remove the item from the map. + updates.emplace_back(pindex, + vr.isAccepted() + ? AvalancheBlockUpdate::Status::Finalized + : AvalancheBlockUpdate::Status::Invalid); + w->erase(it); } } return true; } namespace { /** * Run the avalanche event loop every 10ms. */ static int64_t AVALANCHE_TIME_STEP_MILLISECONDS = 10; /** * Maximum item that can be polled at once. */ static size_t AVALANCHE_MAX_ELEMENT_POLL = 4096; } bool AvalancheProcessor::startEventLoop(CScheduler &scheduler) { LOCK(cs_running); if (running) { // Do not start the event loop twice. return false; } running = true; // Start the event loop. scheduler.scheduleEvery( [this]() -> bool { if (!stopRequest) { return true; } LOCK(cs_running); running = false; cond_running.notify_all(); // A stop request was made. return false; }, AVALANCHE_TIME_STEP_MILLISECONDS); return true; } bool AvalancheProcessor::stopEventLoop() { WAIT_LOCK(cs_running, lock); if (!running) { return false; } // Request avalanche to stop. stopRequest = true; // Wait for avalanche to stop. cond_running.wait(lock, [this] { return !running; }); stopRequest = false; return true; } std::vector AvalancheProcessor::getInvsForNextPoll() const { std::vector invs; auto r = vote_records.getReadView(); for (const std::pair &p : boost::adaptors::reverse(r)) { const VoteRecord &v = p.second; if (v.hasFinalized()) { // If this has finalized, we can just skip. continue; } // We don't have a decision, we need more votes. invs.emplace_back(MSG_BLOCK, p.first->GetBlockHash()); if (invs.size() >= AVALANCHE_MAX_ELEMENT_POLL) { // Make sure we do not produce more invs than specified by the // protocol. return invs; } } return invs; } diff --git a/src/avalanche.h b/src/avalanche.h index cf0bb8aff8..5c8eab539d 100644 --- a/src/avalanche.h +++ b/src/avalanche.h @@ -1,176 +1,210 @@ // Copyright (c) 2018 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_AVALANCHE_H #define BITCOIN_AVALANCHE_H #include "blockindexworkcomparator.h" #include "net.h" #include "protocol.h" // for CInv #include "rwcollection.h" #include "serialize.h" #include "uint256.h" #include #include #include #include class Config; class CBlockIndex; class CScheduler; namespace { /** * Finalization score. */ static int AVALANCHE_FINALIZATION_SCORE = 128; } /** * Vote history. */ struct VoteRecord { private: // Historical record of votes. uint16_t votes; // confidence's LSB bit is the result. Higher bits are actual confidence // score. uint16_t confidence; /** * Return the number of bits set in an integer value. * TODO: There are compiler intrinsics to do that, but we'd need to get them * detected so this will do for now. */ static uint32_t countBits(uint32_t value) { uint32_t count = 0; while (value) { // If the value is non zero, then at least one bit is set. count++; // Clear the rightmost bit set. value &= (value - 1); } return count; } public: VoteRecord() : votes(0xaaaa), confidence(0) {} - bool isValid() const { return confidence & 0x01; } + bool isAccepted() const { return confidence & 0x01; } uint16_t getConfidence() const { return confidence >> 1; } bool hasFinalized() const { return getConfidence() >= AVALANCHE_FINALIZATION_SCORE; } + /** + * Register a new vote for an item and update confidence accordingly. + * Returns true if the acceptance or finalization state changed. + */ bool registerVote(bool vote) { votes = (votes << 1) | vote; auto bits = countBits(votes & 0xff); bool yes = bits > 6; bool no = bits < 2; if (!yes && !no) { // The vote is inconclusive. return false; } - if (isValid() == yes) { + if (isAccepted() == yes) { // If the vote is in agreement with our internal status, increase // confidence. confidence += 2; - } else { - // The vote did not agree with our internal state, in that case, - // reset confidence. - confidence = yes; + return getConfidence() == AVALANCHE_FINALIZATION_SCORE; } + // The vote did not agree with our internal state, in that case, reset + // confidence. + confidence = yes; return true; } }; class AvalancheVote { uint32_t error; uint256 hash; public: AvalancheVote() : error(-1), hash() {} AvalancheVote(uint32_t errorIn, uint256 hashIn) : error(errorIn), hash(hashIn) {} const uint256 &GetHash() const { return hash; } bool IsValid() const { return error == 0; } // serialization support ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(error); READWRITE(hash); } }; class AvalancheResponse { uint32_t cooldown; std::vector votes; public: AvalancheResponse(uint32_t cooldownIn, std::vector votesIn) : cooldown(cooldownIn), votes(votesIn) {} const std::vector &GetVotes() const { return votes; } // serialization support ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(cooldown); READWRITE(votes); } }; +class AvalancheBlockUpdate { + union { + CBlockIndex *pindex; + size_t raw; + }; + +public: + enum Status : uint8_t { + Invalid, + Rejected, + Accepted, + Finalized, + }; + + AvalancheBlockUpdate(CBlockIndex *pindexIn, Status statusIn) + : pindex(pindexIn) { + raw |= statusIn; + } + + Status getStatus() const { return Status(raw & 0x03); } + + CBlockIndex *getBlockIndex() { + return reinterpret_cast(raw & -size_t(0x04)); + } + + const CBlockIndex *getBlockIndex() const { + return const_cast(this)->getBlockIndex(); + } +}; + typedef std::map BlockVoteMap; class AvalancheProcessor { private: /** * Blocks to run avalanche on. */ RWCollection vote_records; /** * Start stop machinery. */ std::atomic stopRequest; bool running GUARDED_BY(cs_running); CWaitableCriticalSection cs_running; std::condition_variable cond_running; public: AvalancheProcessor() : stopRequest(false), running(false) {} ~AvalancheProcessor() { stopEventLoop(); } bool addBlockToReconcile(const CBlockIndex *pindex); bool isAccepted(const CBlockIndex *pindex) const; - bool hasFinalized(const CBlockIndex *pindex) const; - bool registerVotes(const AvalancheResponse &response); + bool registerVotes(const AvalancheResponse &response, + std::vector &updates); bool startEventLoop(CScheduler &scheduler); bool stopEventLoop(); private: std::vector getInvsForNextPoll() const; friend struct AvalancheTest; }; #endif // BITCOIN_AVALANCHE_H diff --git a/src/test/avalanche_tests.cpp b/src/test/avalanche_tests.cpp index 39ddf45355..291cf0484e 100644 --- a/src/test/avalanche_tests.cpp +++ b/src/test/avalanche_tests.cpp @@ -1,276 +1,352 @@ // Copyright (c) 2010 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "avalanche.h" #include "test/test_bitcoin.h" #include struct AvalancheTest { static std::vector getInvsForNextPoll(const AvalancheProcessor &p) { return p.getInvsForNextPoll(); } }; BOOST_FIXTURE_TEST_SUITE(avalanche_tests, TestChain100Setup) #define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, confidence) \ vr.registerVote(vote); \ - BOOST_CHECK_EQUAL(vr.isValid(), state); \ + BOOST_CHECK_EQUAL(vr.isAccepted(), state); \ BOOST_CHECK_EQUAL(vr.hasFinalized(), finalized); \ BOOST_CHECK_EQUAL(vr.getConfidence(), confidence); BOOST_AUTO_TEST_CASE(vote_record) { VoteRecord vr; // Check initial state. - BOOST_CHECK_EQUAL(vr.isValid(), false); + BOOST_CHECK_EQUAL(vr.isAccepted(), false); BOOST_CHECK_EQUAL(vr.hasFinalized(), false); BOOST_CHECK_EQUAL(vr.getConfidence(), 0); // We register one vote for, which keep things at 4/4. REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0); // One more and we are at 5/3. REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0); // One more and we are at 5/3. REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0); // One more and we are at 6/2. REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0); // One more and we are at 6/2. REGISTER_VOTE_AND_CHECK(vr, true, false, false, 0); // Next vote will flip state, and confidence will increase as long as we // vote yes. for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { REGISTER_VOTE_AND_CHECK(vr, true, true, false, i); } // The next vote will finalize the decision. REGISTER_VOTE_AND_CHECK(vr, false, true, true, AVALANCHE_FINALIZATION_SCORE); // Now that we have two no votes, confidence stop increasing. for (int i = 0; i < 5; i++) { REGISTER_VOTE_AND_CHECK(vr, false, true, true, AVALANCHE_FINALIZATION_SCORE); } // Next vote will flip state, and confidence will increase as long as we // vote no. for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { REGISTER_VOTE_AND_CHECK(vr, false, false, false, i); } // The next vote will finalize the decision. REGISTER_VOTE_AND_CHECK(vr, true, false, true, AVALANCHE_FINALIZATION_SCORE); } +BOOST_AUTO_TEST_CASE(block_update) { + CBlockIndex index; + CBlockIndex *pindex = &index; + + std::set status{ + AvalancheBlockUpdate::Status::Invalid, + AvalancheBlockUpdate::Status::Rejected, + AvalancheBlockUpdate::Status::Accepted, + AvalancheBlockUpdate::Status::Finalized, + }; + + for (auto s : status) { + AvalancheBlockUpdate abu(pindex, s); + BOOST_CHECK(abu.getBlockIndex() == pindex); + BOOST_CHECK_EQUAL(abu.getStatus(), s); + } +} + BOOST_AUTO_TEST_CASE(block_register) { AvalancheProcessor p; + std::vector updates; CBlock block = CreateAndProcessBlock({}, CScript()); const uint256 blockHash = block.GetHash(); const CBlockIndex *pindex = mapBlockIndex[blockHash]; // Querying for random block returns false. BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(!p.hasFinalized(pindex)); // Add a new block. Check it is added to the polls. BOOST_CHECK(p.addBlockToReconcile(pindex)); auto invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 1); BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK); BOOST_CHECK(invs[0].hash == blockHash); // Newly added blocks are also considered rejected. BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(!p.hasFinalized(pindex)); // Let's vote for this block a few times. AvalancheResponse resp{0, {AvalancheVote(0, blockHash)}}; for (int i = 0; i < 5; i++) { - p.registerVotes(resp); + p.registerVotes(resp, updates); BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(!p.hasFinalized(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 0); } + // Now the state will flip. + p.registerVotes(resp, updates); + BOOST_CHECK(p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindex); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Accepted); + updates = {}; + // Now it is accepted, but we can vote for it numerous times. - for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { - p.registerVotes(resp); + for (int i = 1; i < AVALANCHE_FINALIZATION_SCORE; i++) { + p.registerVotes(resp, updates); BOOST_CHECK(p.isAccepted(pindex)); - BOOST_CHECK(!p.hasFinalized(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 0); } // As long as it is not finalized, we poll. invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 1); BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK); BOOST_CHECK(invs[0].hash == blockHash); // Now finalize the decision. - resp = {0, {AvalancheVote(1, blockHash)}}; - p.registerVotes(resp); - BOOST_CHECK(p.isAccepted(pindex)); - BOOST_CHECK(p.hasFinalized(pindex)); + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindex); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Finalized); + updates = {}; // Once the decision is finalized, there is no poll for it. invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 0); // Now let's undo this and finalize rejection. - for (int i = 0; i < 5; i++) { - p.registerVotes(resp); - BOOST_CHECK(p.isAccepted(pindex)); - BOOST_CHECK(p.hasFinalized(pindex)); + BOOST_CHECK(p.addBlockToReconcile(pindex)); + invs = AvalancheTest::getInvsForNextPoll(p); + BOOST_CHECK_EQUAL(invs.size(), 1); + BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK); + BOOST_CHECK(invs[0].hash == blockHash); + + // Only 3 here as we don't need to flip state. + resp = {0, {AvalancheVote(1, blockHash)}}; + for (int i = 0; i < 3; i++) { + p.registerVotes(resp, updates); + BOOST_CHECK(!p.isAccepted(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 0); } // Now it is rejected, but we can vote for it numerous times. for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) { - p.registerVotes(resp); + p.registerVotes(resp, updates); BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(!p.hasFinalized(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 0); } // As long as it is not finalized, we poll. invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 1); BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK); BOOST_CHECK(invs[0].hash == blockHash); // Now finalize the decision. - p.registerVotes(resp); + p.registerVotes(resp, updates); BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(p.hasFinalized(pindex)); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindex); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Invalid); + updates = {}; // Once the decision is finalized, there is no poll for it. invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 0); // Adding the block twice does nothing. + BOOST_CHECK(p.addBlockToReconcile(pindex)); BOOST_CHECK(!p.addBlockToReconcile(pindex)); BOOST_CHECK(!p.isAccepted(pindex)); - BOOST_CHECK(p.hasFinalized(pindex)); } BOOST_AUTO_TEST_CASE(multi_block_register) { AvalancheProcessor p; CBlockIndex indexA, indexB; + std::vector updates; + // Make sure the block has a hash. CBlock blockA = CreateAndProcessBlock({}, CScript()); const uint256 blockHashA = blockA.GetHash(); const CBlockIndex *pindexA = mapBlockIndex[blockHashA]; CBlock blockB = CreateAndProcessBlock({}, CScript()); const uint256 blockHashB = blockB.GetHash(); const CBlockIndex *pindexB = mapBlockIndex[blockHashB]; // Querying for random block returns false. BOOST_CHECK(!p.isAccepted(pindexA)); BOOST_CHECK(!p.isAccepted(pindexB)); // Start voting on block A. BOOST_CHECK(p.addBlockToReconcile(pindexA)); auto invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 1); BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK); BOOST_CHECK(invs[0].hash == blockHashA); AvalancheResponse resp{ 0, {AvalancheVote(0, blockHashA), AvalancheVote(0, blockHashB)}}; - p.registerVotes(resp); + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 0); // Start voting on block B after one vote. BOOST_CHECK(p.addBlockToReconcile(pindexB)); invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 2); // Ensure B comes before A because it has accumulated more PoW. BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK); BOOST_CHECK(invs[0].hash == blockHashB); BOOST_CHECK_EQUAL(invs[1].type, MSG_BLOCK); BOOST_CHECK(invs[1].hash == blockHashA); + // Let's vote for this block a few times. + for (int i = 0; i < 4; i++) { + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 0); + } + + // Now the state will flip for A. + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindexA); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Accepted); + updates = {}; + + // And then for B. + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindexB); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Accepted); + updates = {}; + // Now it is rejected, but we can vote for it numerous times. - for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE + 4; i++) { - p.registerVotes(resp); + for (int i = 2; i < AVALANCHE_FINALIZATION_SCORE; i++) { + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 0); } // Next vote will finalize block A. - p.registerVotes(resp); + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindexA); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Finalized); + updates = {}; // We do not vote on A anymore. invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 1); BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK); BOOST_CHECK(invs[0].hash == blockHashB); // Next vote will finalize block B. - p.registerVotes(resp); + p.registerVotes(resp, updates); + BOOST_CHECK_EQUAL(updates.size(), 1); + BOOST_CHECK(updates[0].getBlockIndex() == pindexB); + BOOST_CHECK_EQUAL(updates[0].getStatus(), + AvalancheBlockUpdate::Status::Finalized); + updates = {}; // There is nothing left to vote on. invs = AvalancheTest::getInvsForNextPoll(p); BOOST_CHECK_EQUAL(invs.size(), 0); } BOOST_AUTO_TEST_CASE(event_loop) { AvalancheProcessor p; CScheduler s; // Starting the event loop. BOOST_CHECK(p.startEventLoop(s)); // There is one task planned in the next hour (our event loop). boost::chrono::system_clock::time_point start, stop; BOOST_CHECK_EQUAL(s.getQueueInfo(start, stop), 1); // Starting twice doesn't start it twice. BOOST_CHECK(!p.startEventLoop(s)); // Start the scheduler thread. std::thread schedulerThread(std::bind(&CScheduler::serviceQueue, &s)); // Stop event loop. BOOST_CHECK(p.stopEventLoop()); // We don't have any task scheduled anymore. BOOST_CHECK_EQUAL(s.getQueueInfo(start, stop), 0); // Can't stop the event loop twice. BOOST_CHECK(!p.stopEventLoop()); // Wait for the scheduler to stop. s.stop(true); schedulerThread.join(); } BOOST_AUTO_TEST_CASE(destructor) { CScheduler s; boost::chrono::system_clock::time_point start, stop; // Start the scheduler thread. std::thread schedulerThread(std::bind(&CScheduler::serviceQueue, &s)); { AvalancheProcessor p; BOOST_CHECK(p.startEventLoop(s)); BOOST_CHECK_EQUAL(s.getQueueInfo(start, stop), 1); } // Now that avalanche is destroyed, there is no more scheduled tasks. BOOST_CHECK_EQUAL(s.getQueueInfo(start, stop), 0); // Wait for the scheduler to stop. s.stop(true); schedulerThread.join(); } BOOST_AUTO_TEST_SUITE_END()