diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp index 3cabec8d3..3ca34c68c 100644 --- a/src/avalanche/peermanager.cpp +++ b/src/avalanche/peermanager.cpp @@ -1,543 +1,543 @@ // Copyright (c) 2020 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include #include #include #include // For ChainstateActive() #include #include namespace avalanche { bool PeerManager::addNode(NodeId nodeid, const ProofId &proofid) { auto &pview = peers.get(); auto it = pview.find(proofid); if (it == pview.end()) { // If the node exists, it is actually updating its proof to an unknown // one. In this case we need to remove it so it is not both active and // pending at the same time. removeNode(nodeid); pendingNodes.emplace(proofid, nodeid); return false; } return addOrUpdateNode(peers.project<0>(it), nodeid); } bool PeerManager::addOrUpdateNode(const PeerSet::iterator &it, NodeId nodeid) { assert(it != peers.end()); const PeerId peerid = it->peerid; auto nit = nodes.find(nodeid); if (nit == nodes.end()) { if (!nodes.emplace(nodeid, peerid).second) { return false; } } else { const PeerId oldpeerid = nit->peerid; if (!nodes.modify(nit, [&](Node &n) { n.peerid = peerid; })) { return false; } // We actually have this node already, we need to update it. bool success = removeNodeFromPeer(peers.find(oldpeerid)); assert(success); } bool success = addNodeToPeer(it); assert(success); // If the added node was in the pending set, remove it pendingNodes.get().erase(nodeid); return true; } bool PeerManager::addNodeToPeer(const PeerSet::iterator &it) { assert(it != peers.end()); return peers.modify(it, [&](Peer &p) { if (p.node_count++ > 0) { // We are done. return; } // We need to allocate this peer. p.index = uint32_t(slots.size()); const uint32_t score = p.getScore(); const uint64_t start = slotCount; slots.emplace_back(start, score, it->peerid); slotCount = start + score; }); } bool PeerManager::removeNode(NodeId nodeid) { auto it = nodes.find(nodeid); if (it == nodes.end()) { return false; } const PeerId peerid = it->peerid; nodes.erase(it); pendingNodes.get().erase(nodeid); // Keep the track of the reference count. bool success = removeNodeFromPeer(peers.find(peerid)); assert(success); return true; } bool PeerManager::removeNodeFromPeer(const PeerSet::iterator &it, uint32_t count) { // It is possible for nodes to be dangling. If there was an inflight query // when the peer gets removed, the node was not erased. In this case there // is nothing to do. if (it == peers.end()) { return true; } assert(count <= it->node_count); if (count == 0) { // This is a NOOP. return false; } const uint32_t new_count = it->node_count - count; if (!peers.modify(it, [&](Peer &p) { p.node_count = new_count; })) { return false; } if (new_count > 0) { // We are done. return true; } // There are no more node left, we need to cleanup. const size_t i = it->index; assert(i < slots.size()); if (i + 1 == slots.size()) { slots.pop_back(); slotCount = slots.empty() ? 0 : slots.back().getStop(); } else { fragmentation += slots[i].getScore(); slots[i] = slots[i].withPeerId(NO_PEER); } return true; } bool PeerManager::updateNextRequestTime(NodeId nodeid, TimePoint timeout) { auto it = nodes.find(nodeid); if (it == nodes.end()) { return false; } return nodes.modify(it, [&](Node &n) { n.nextRequestTime = timeout; }); } static bool isOrphanState(const ProofValidationState &state) { return state.GetResult() == ProofValidationResult::MISSING_UTXO || state.GetResult() == ProofValidationResult::HEIGHT_MISMATCH; } bool PeerManager::registerProof(const ProofRef &proof) { if (exists(proof->getId())) { // The proof is already registered, or orphaned. return false; } // Check the proof's validity. ProofValidationState state; // Using WITH_LOCK directly inside the if statement will trigger a cppcheck // false positive syntax error const bool valid = WITH_LOCK( cs_main, return proof->verify(state, ::ChainstateActive().CoinsTip())); if (!valid) { if (isOrphanState(state)) { orphanProofs.addProof(proof); } // Reject invalid proof. return false; } return createPeer(proof); } NodeId PeerManager::selectNode() { for (int retry = 0; retry < SELECT_NODE_MAX_RETRY; retry++) { const PeerId p = selectPeer(); // If we cannot find a peer, it may be due to the fact that it is // unlikely due to high fragmentation, so compact and retry. if (p == NO_PEER) { compact(); continue; } // See if that peer has an available node. auto &nview = nodes.get(); auto it = nview.lower_bound(boost::make_tuple(p, TimePoint())); if (it != nview.end() && it->peerid == p && it->nextRequestTime <= std::chrono::steady_clock::now()) { return it->nodeid; } } return NO_NODE; } void PeerManager::updatedBlockTip() { std::vector invalidPeers; std::vector newOrphans; { LOCK(cs_main); const CCoinsViewCache &coins = ::ChainstateActive().CoinsTip(); for (const auto &p : peers) { ProofValidationState state; if (!p.proof->verify(state, coins)) { if (isOrphanState(state)) { newOrphans.push_back(p.proof); } invalidPeers.push_back(p.peerid); } } } // Remove the invalid peers before the orphans rescan. This makes it // possible to pull back proofs with utxos that conflicted with these // invalid peers. for (const auto &pid : invalidPeers) { removePeer(pid); } orphanProofs.rescan(*this); for (auto &p : newOrphans) { orphanProofs.addProof(p); } } ProofRef PeerManager::getProof(const ProofId &proofid) const { ProofRef proof = nullptr; forPeer(proofid, [&](const Peer &p) { proof = p.proof; return true; }); if (!proof) { proof = orphanProofs.getProof(proofid); } return proof; } bool PeerManager::isBoundToPeer(const ProofId &proofid) const { auto &pview = peers.get(); return pview.find(proofid) != pview.end(); } bool PeerManager::isOrphan(const ProofId &proofid) const { return orphanProofs.getProof(proofid) != nullptr; } bool PeerManager::createPeer(const ProofRef &proof) { assert(proof); switch (validProofPool.addProof(proof)) { case ProofPool::AddProofStatus::REJECTED: // The proof has conflicts, orphan the proof so it can be pulled // back if the conflicting ones are invalidated. orphanProofs.addProof(proof); return false; case ProofPool::AddProofStatus::DUPLICATED: // If the proof was already in the pool, don't duplicate the peer. return false; case ProofPool::AddProofStatus::SUCCEED: break; // No default case, so the compiler can warn about missing cases } // New peer means new peerid! const PeerId peerid = nextPeerId++; // We have no peer for this proof, time to create it. auto inserted = peers.emplace(peerid, proof); assert(inserted.second); // If there are nodes waiting for this proof, add them auto &pendingNodesView = pendingNodes.get(); auto range = pendingNodesView.equal_range(proof->getId()); // We want to update the nodes then remove them from the pending set. That // will invalidate the range iterators, so we need to save the node ids // first before we can loop over them. std::vector nodeids; nodeids.reserve(std::distance(range.first, range.second)); std::transform(range.first, range.second, std::back_inserter(nodeids), [](const PendingNode &n) { return n.nodeid; }); for (const NodeId &nodeid : nodeids) { addOrUpdateNode(inserted.first, nodeid); } return true; } bool PeerManager::removePeer(const PeerId peerid) { auto it = peers.find(peerid); if (it == peers.end()) { return false; } // Remove all nodes from this peer. removeNodeFromPeer(it, it->node_count); auto &nview = nodes.get(); // Add the nodes to the pending set auto range = nview.equal_range(peerid); for (auto &nit = range.first; nit != range.second; ++nit) { pendingNodes.emplace(it->getProofId(), nit->nodeid); }; // Remove nodes associated with this peer, unless their timeout is still // active. This ensure that we don't overquery them in case they are // subsequently added to another peer. nview.erase(nview.lower_bound(boost::make_tuple(peerid, TimePoint())), nview.upper_bound(boost::make_tuple( peerid, std::chrono::steady_clock::now()))); // Release UTXOs attached to this proof. validProofPool.removeProof(it->proof); m_unbroadcast_proofids.erase(it->proof->getId()); peers.erase(it); return true; } PeerId PeerManager::selectPeer() const { if (slots.empty() || slotCount == 0) { return NO_PEER; } const uint64_t max = slotCount; for (int retry = 0; retry < SELECT_PEER_MAX_RETRY; retry++) { size_t i = selectPeerImpl(slots, GetRand(max), max); if (i != NO_PEER) { return i; } } return NO_PEER; } uint64_t PeerManager::compact() { // There is nothing to compact. if (fragmentation == 0) { return 0; } std::vector newslots; newslots.reserve(peers.size()); uint64_t prevStop = 0; uint32_t i = 0; for (auto it = peers.begin(); it != peers.end(); it++) { if (it->node_count == 0) { continue; } newslots.emplace_back(prevStop, it->getScore(), it->peerid); prevStop = slots[i].getStop(); if (!peers.modify(it, [&](Peer &p) { p.index = i++; })) { return 0; } } slots = std::move(newslots); const uint64_t saved = slotCount - prevStop; slotCount = prevStop; fragmentation = 0; return saved; } bool PeerManager::verify() const { uint64_t prevStop = 0; for (size_t i = 0; i < slots.size(); i++) { const Slot &s = slots[i]; // Slots must be in correct order. if (s.getStart() < prevStop) { return false; } prevStop = s.getStop(); // If this is a dead slot, then nothing more needs to be checked. if (s.getPeerId() == NO_PEER) { continue; } // We have a live slot, verify index. auto it = peers.find(s.getPeerId()); if (it == peers.end() || it->index != i) { return false; } } std::unordered_set peersUtxos; for (const auto &p : peers) { // A peer should have a proof attached if (!p.proof) { return false; } // Check proof pool consistency for (const auto &ss : p.proof->getStakes()) { - auto it = validProofPool.pool.find(ss.getStake().getUTXO()); + const COutPoint &outpoint = ss.getStake().getUTXO(); + auto proof = validProofPool.getProof(outpoint); - if (it == validProofPool.pool.end()) { + if (!proof) { // Missing utxo return false; } - if (it->proof != p.proof) { + if (proof != p.proof) { // Wrong proof return false; } - if (!peersUtxos.emplace(it->getUTXO()).second) { + if (!peersUtxos.emplace(outpoint).second) { // Duplicated utxo return false; } } // Count node attached to this peer. const auto count_nodes = [&]() { size_t count = 0; auto &nview = nodes.get(); auto begin = nview.lower_bound(boost::make_tuple(p.peerid, TimePoint())); auto end = nview.upper_bound(boost::make_tuple(p.peerid + 1, TimePoint())); for (auto it = begin; it != end; ++it) { count++; } return count; }; if (p.node_count != count_nodes()) { return false; } // If there are no nodes attached to this peer, then we are done. if (p.node_count == 0) { continue; } // The index must point to a slot refering to this peer. if (p.index >= slots.size() || slots[p.index].getPeerId() != p.peerid) { return false; } // If the score do not match, same thing. if (slots[p.index].getScore() != p.getScore()) { return false; } } - // Check there is no dangling utxo - for (const auto &entry : validProofPool.pool) { - if (!peersUtxos.count(entry.getUTXO())) { - return false; - } + // We checked the utxo consistency for all our peers utxos already, so if + // the pool size differs from the expected one there are dangling utxos. + if (validProofPool.size() != peersUtxos.size()) { + return false; } return true; } PeerId selectPeerImpl(const std::vector &slots, const uint64_t slot, const uint64_t max) { assert(slot <= max); size_t begin = 0, end = slots.size(); uint64_t bottom = 0, top = max; // Try to find the slot using dichotomic search. while ((end - begin) > 8) { // The slot we picked in not allocated. if (slot < bottom || slot >= top) { return NO_PEER; } // Guesstimate the position of the slot. size_t i = begin + ((slot - bottom) * (end - begin) / (top - bottom)); assert(begin <= i && i < end); // We have a match. if (slots[i].contains(slot)) { return slots[i].getPeerId(); } // We undershooted. if (slots[i].precedes(slot)) { begin = i + 1; if (begin >= end) { return NO_PEER; } bottom = slots[begin].getStart(); continue; } // We overshooted. if (slots[i].follows(slot)) { end = i; top = slots[end].getStart(); continue; } // We have an unalocated slot. return NO_PEER; } // Enough of that nonsense, let fallback to linear search. for (size_t i = begin; i < end; i++) { // We have a match. if (slots[i].contains(slot)) { return slots[i].getPeerId(); } } // We failed to find a slot, retry. return NO_PEER; } void PeerManager::addUnbroadcastProof(const ProofId &proofid) { // The proof should be bound to a peer if (isBoundToPeer(proofid)) { m_unbroadcast_proofids.insert(proofid); } } void PeerManager::removeUnbroadcastProof(const ProofId &proofid) { m_unbroadcast_proofids.erase(proofid); } } // namespace avalanche diff --git a/src/avalanche/proofpool.cpp b/src/avalanche/proofpool.cpp index 5356e59cc..4a2b677e4 100644 --- a/src/avalanche/proofpool.cpp +++ b/src/avalanche/proofpool.cpp @@ -1,73 +1,78 @@ // Copyright (c) 2021 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include namespace avalanche { ProofPool::AddProofStatus ProofPool::addProof(const ProofRef &proof) { assert(proof); const ProofId &proofid = proof->getId(); auto &poolView = pool.get(); if (poolView.find(proofid) != poolView.end()) { return AddProofStatus::DUPLICATED; } // Attach UTXOs to this proof. std::unordered_set conflicting_proofs; for (size_t i = 0; i < proof->getStakes().size(); i++) { auto p = pool.emplace(i, proof); if (!p.second) { // We have a collision with an existing proof. conflicting_proofs.insert(p.first->proof); } } // For now, if there is a conflict, just cleanup the mess. if (conflicting_proofs.size() > 0) { for (const auto &s : proof->getStakes()) { auto it = pool.find(s.getStake().getUTXO()); assert(it != pool.end()); // We need to delete that one. if (it->proof->getId() == proofid) { pool.erase(it); } } return AddProofStatus::REJECTED; } return AddProofStatus::SUCCEED; } // Having the ProofRef passed by reference is risky because the proof could be // deleted during the erasure loop, so we pass it by value. Since it's a shared // pointer, the copy is cheap enough and should not have any significant impact // on performance. bool ProofPool::removeProof(ProofRef proof) { auto &poolView = pool.get(); return poolView.erase(proof->getId()); } void ProofPool::rescan(PeerManager &peerManager) { auto previousPool = std::move(pool); pool.clear(); for (auto &entry : previousPool) { peerManager.registerProof(entry.proof); } } ProofRef ProofPool::getProof(const ProofId &proofid) const { auto &poolView = pool.get(); auto it = poolView.find(proofid); return it == poolView.end() ? nullptr : it->proof; } +ProofRef ProofPool::getProof(const COutPoint &outpoint) const { + auto it = pool.find(outpoint); + return it == pool.end() ? nullptr : it->proof; +} + } // namespace avalanche diff --git a/src/avalanche/proofpool.h b/src/avalanche/proofpool.h index a7dd71d97..842911f67 100644 --- a/src/avalanche/proofpool.h +++ b/src/avalanche/proofpool.h @@ -1,82 +1,86 @@ // Copyright (c) 2021 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_PROOFPOOL_H #define BITCOIN_AVALANCHE_PROOFPOOL_H #include #include #include #include #include #include #include #include namespace avalanche { class PeerManager; struct ProofPoolEntry { size_t utxoIndex; ProofRef proof; const COutPoint &getUTXO() const { return proof->getStakes().at(utxoIndex).getStake().getUTXO(); } ProofPoolEntry(size_t _utxoIndex, ProofRef _proof) : utxoIndex(_utxoIndex), proof(std::move(_proof)) {} }; struct by_utxo; struct by_proofid; struct ProofPoolEntryProofIdKeyExtractor { using result_type = ProofId; result_type operator()(const ProofPoolEntry &entry) const { return entry.proof->getId(); } }; namespace bmi = boost::multi_index; /** * Map a proof to each utxo. A proof can be mapped with several utxos. */ -struct ProofPool { +class ProofPool { boost::multi_index_container< ProofPoolEntry, bmi::indexed_by< // index by utxo bmi::hashed_unique< bmi::tag, bmi::const_mem_fun, SaltedOutpointHasher>, // index by proofid bmi::hashed_non_unique, ProofPoolEntryProofIdKeyExtractor, SaltedProofIdHasher>>> pool; +public: enum AddProofStatus { REJECTED = 0, //!< Rejected due to conflicts SUCCEED = 1, //!< Added successfully DUPLICATED = 2, //!< Already in pool }; AddProofStatus addProof(const ProofRef &proof); bool removeProof(ProofRef proof); void rescan(PeerManager &peerManager); ProofRef getProof(const ProofId &proofid) const; + ProofRef getProof(const COutPoint &outpoint) const; + + size_t size() const { return pool.size(); } }; } // namespace avalanche #endif // BITCOIN_AVALANCHE_PROOFPOOL_H diff --git a/src/avalanche/test/proofpool_tests.cpp b/src/avalanche/test/proofpool_tests.cpp index af55fb450..54daf44e3 100644 --- a/src/avalanche/test/proofpool_tests.cpp +++ b/src/avalanche/test/proofpool_tests.cpp @@ -1,119 +1,119 @@ // Copyright (c) 2021 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include #include #include #include #include #include #include #include using namespace avalanche; BOOST_FIXTURE_TEST_SUITE(proofpool_tests, TestingSetup) BOOST_AUTO_TEST_CASE(add_remove_proof) { ProofPool testPool; std::vector proofs; for (size_t i = 0; i < 10; i++) { // Add a bunch of random proofs auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE); BOOST_CHECK_EQUAL(testPool.addProof(proof), ProofPool::AddProofStatus::SUCCEED); // Trying to add them again will return a duplicated status for (size_t j = 0; j < 10; j++) { BOOST_CHECK_EQUAL(testPool.addProof(proof), ProofPool::AddProofStatus::DUPLICATED); } proofs.push_back(std::move(proof)); } const CKey key = CKey::MakeCompressedKey(); const COutPoint conflictingOutpoint{TxId(GetRandHash()), 0}; auto buildProofWithSequence = [&](uint64_t sequence) { ProofBuilder pb(sequence, 0, key); BOOST_CHECK( pb.addUTXO(conflictingOutpoint, 10 * COIN, 123456, false, key)); return pb.build(); }; auto proof_seq10 = buildProofWithSequence(10); BOOST_CHECK_EQUAL(testPool.addProof(proof_seq10), ProofPool::AddProofStatus::SUCCEED); proofs.push_back(std::move(proof_seq10)); auto proof_seq20 = buildProofWithSequence(20); BOOST_CHECK_EQUAL(testPool.addProof(proof_seq20), ProofPool::AddProofStatus::REJECTED); // Removing proofs which are not in the pool will fail for (size_t i = 0; i < 10; i++) { BOOST_CHECK( !testPool.removeProof(buildRandomProof(MIN_VALID_PROOF_SCORE))); } for (auto proof : proofs) { BOOST_CHECK(testPool.removeProof(proof)); } - BOOST_CHECK(testPool.pool.empty()); + BOOST_CHECK_EQUAL(testPool.size(), 0); } BOOST_AUTO_TEST_CASE(rescan) { ProofPool testPool; avalanche::PeerManager pm; testPool.rescan(pm); - BOOST_CHECK(testPool.pool.empty()); + BOOST_CHECK_EQUAL(testPool.size(), 0); // No peer should be created bool hasPeer = false; pm.forEachPeer([&](const Peer &p) { hasPeer = true; }); BOOST_CHECK(!hasPeer); std::set poolProofs; for (size_t i = 0; i < 10; i++) { auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE); BOOST_CHECK_EQUAL(testPool.addProof(proof), ProofPool::AddProofStatus::SUCCEED); poolProofs.insert(std::move(proof)); } testPool.rescan(pm); // All the proofs should be registered as peer std::set pmProofs; pm.forEachPeer([&](const Peer &p) { pmProofs.insert(p.proof); }); BOOST_CHECK_EQUAL_COLLECTIONS(poolProofs.begin(), poolProofs.end(), pmProofs.begin(), pmProofs.end()); - BOOST_CHECK(testPool.pool.empty()); + BOOST_CHECK_EQUAL(testPool.size(), 0); } BOOST_AUTO_TEST_CASE(get_proof) { ProofPool testPool; for (size_t i = 0; i < 10; i++) { BOOST_CHECK(!testPool.getProof(ProofId(GetRandHash()))); } for (size_t i = 0; i < 10; i++) { auto proof = buildRandomProof(MIN_VALID_PROOF_SCORE); BOOST_CHECK_EQUAL(testPool.addProof(proof), ProofPool::AddProofStatus::SUCCEED); auto retrievedProof = testPool.getProof(proof->getId()); BOOST_CHECK_NE(retrievedProof, nullptr); BOOST_CHECK_EQUAL(retrievedProof->getId(), proof->getId()); } } BOOST_AUTO_TEST_SUITE_END()