Page MenuHomePhabricator
Files F14864384

D11450.id33695.diff
No OneTemporary
Actions

D11450.id33695.diff
View Options

diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h
--- a/src/avalanche/peermanager.h
+++ b/src/avalanche/peermanager.h
@@ -8,9 +8,11 @@
#include <avalanche/node.h>
#include <avalanche/proof.h>
#include <avalanche/proofpool.h>
+#include <avalanche/proofradixtreeadapter.h>
#include <coins.h>
#include <consensus/validation.h>
#include <pubkey.h>
+#include <radix.h>
#include <salteduint256hasher.h>
#include <util/time.h>
@@ -155,6 +157,9 @@
ProofPool conflictingProofPool;
ProofPool orphanProofPool;
+ using ProofRadixTree = RadixTree<const Proof, ProofRadixTreeAdapter>;
+ ProofRadixTree shareableProofs;
+
using NodeSet = boost::multi_index_container<
Node,
bmi::indexed_by<
@@ -356,6 +361,10 @@
bool isOrphan(const ProofId &proofid) const;
bool isInConflictingPool(const ProofId &proofid) const;
+ const ProofRadixTree &getShareableProofsSnapshot() const {
+ return shareableProofs;
+ }
+
private:
template <typename ProofContainer>
void moveToConflictingPool(const ProofContainer &proofs);
diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp
--- a/src/avalanche/peermanager.cpp
+++ b/src/avalanche/peermanager.cpp
@@ -313,6 +313,9 @@
auto inserted = peers.emplace(peerid, proof, nextCooldownTimePoint);
assert(inserted.second);
+ auto insertedRadixTree = shareableProofs.insert(proof);
+ assert(insertedRadixTree);
+
// Add to our registered score when adding to the peer list
totalPeersScore += proof->getScore();
@@ -503,6 +506,9 @@
// Release UTXOs attached to this proof.
validProofPool.removeProof(it->getProofId());
+ auto removed = shareableProofs.remove(Uint256RadixKey(it->getProofId()));
+ assert(removed != nullptr);
+
m_unbroadcast_proofids.erase(it->getProofId());
// Remove the peer from the PeerSet and remove its score from the registered
@@ -662,6 +668,11 @@
if (slots[p.index].getScore() != p.getScore()) {
return false;
}
+
+ // Check the proof is in the radix tree
+ if (shareableProofs.get(p.getProofId()) == nullptr) {
+ return false;
+ }
}
// Check our accumulated scores against our registred and allocated scores
@@ -678,7 +689,10 @@
return false;
}
- return true;
+ // Check there is no dangling proof in the radix tree
+ return shareableProofs.forEachLeaf([&](RCUPtr<const Proof> pLeaf) {
+ return isBoundToPeer(pLeaf->getId());
+ });
}
PeerId selectPeerImpl(const std::vector<Slot> &slots, const uint64_t slot,
diff --git a/src/avalanche/proofradixtreeadapter.h b/src/avalanche/proofradixtreeadapter.h
new file mode 100644
--- /dev/null
+++ b/src/avalanche/proofradixtreeadapter.h
@@ -0,0 +1,22 @@
+// Copyright (c) 2022 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_PROOFRADIXTREEADAPTER_H
+#define BITCOIN_AVALANCHE_PROOFRADIXTREEADAPTER_H
+
+#include <avalanche/proof.h>
+#include <uint256radixkey.h>
+
+namespace avalanche {
+
+/**
+ * Radix tree adapter for storing a proof as a tree element.
+ */
+struct ProofRadixTreeAdapter {
+ Uint256RadixKey getId(const Proof &proof) const { return proof.getId(); }
+};
+
+} // namespace avalanche
+
+#endif // BITCOIN_AVALANCHE_PROOFRADIXTREEADAPTER_H
diff --git a/src/avalanche/test/peermanager_tests.cpp b/src/avalanche/test/peermanager_tests.cpp
--- a/src/avalanche/test/peermanager_tests.cpp
+++ b/src/avalanche/test/peermanager_tests.cpp
@@ -1625,4 +1625,120 @@
checkScores(0, 0);
}
+BOOST_FIXTURE_TEST_CASE(proof_radix_tree, NoCoolDownFixture) {
+ avalanche::PeerManager pm;
+
+ gArgs.ForceSetArg("-enableavalancheproofreplacement", "1");
+
+ struct ProofComparatorById {
+ bool operator()(const ProofRef &lhs, const ProofRef &rhs) const {
+ return lhs->getId() < rhs->getId();
+ };
+ };
+ using ProofSetById = std::set<ProofRef, ProofComparatorById>;
+ // Maintain a list of the expected proofs through this test
+ ProofSetById expectedProofs;
+
+ auto matchExpectedContent = [&](const auto &tree) {
+ auto it = expectedProofs.begin();
+ return tree.forEachLeaf([&](auto pLeaf) {
+ return it != expectedProofs.end() &&
+ pLeaf->getId() == (*it++)->getId();
+ });
+ };
+
+ CKey key = CKey::MakeCompressedKey();
+ const int64_t sequence = 10;
+
+ // Add some initial proofs
+ for (size_t i = 0; i < 10; i++) {
+ auto outpoint = createUtxo(key);
+ auto proof = buildProofWithSequence(key, {{outpoint}}, sequence);
+ BOOST_CHECK(pm.registerProof(proof));
+ expectedProofs.insert(std::move(proof));
+ }
+
+ const auto &treeRef = pm.getShareableProofsSnapshot();
+ BOOST_CHECK(matchExpectedContent(treeRef));
+
+ // Create a copy
+ auto tree = pm.getShareableProofsSnapshot();
+
+ // Adding more proofs doesn't change the tree...
+ ProofSetById addedProofs;
+ std::vector<COutPoint> outpointsToSpend;
+ for (size_t i = 0; i < 10; i++) {
+ auto outpoint = createUtxo(key);
+ auto proof = buildProofWithSequence(key, {{outpoint}}, sequence);
+ BOOST_CHECK(pm.registerProof(proof));
+ addedProofs.insert(std::move(proof));
+ outpointsToSpend.push_back(std::move(outpoint));
+ }
+
+ BOOST_CHECK(matchExpectedContent(tree));
+
+ // ...until we get a new copy
+ tree = pm.getShareableProofsSnapshot();
+ expectedProofs.insert(addedProofs.begin(), addedProofs.end());
+ BOOST_CHECK(matchExpectedContent(tree));
+
+ // Spend some coins to make the associated proofs invalid
+ {
+ LOCK(cs_main);
+ CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
+ for (const auto &outpoint : outpointsToSpend) {
+ coins.SpendCoin(outpoint);
+ }
+ }
+
+ pm.updatedBlockTip();
+
+ // This doesn't change the tree...
+ BOOST_CHECK(matchExpectedContent(tree));
+
+ // ...until we get a new copy
+ tree = pm.getShareableProofsSnapshot();
+ for (const auto &proof : addedProofs) {
+ BOOST_CHECK_EQUAL(expectedProofs.erase(proof), 1);
+ }
+ BOOST_CHECK(matchExpectedContent(tree));
+
+ // Add some more proof for which we will create conflicts
+ std::vector<ProofRef> conflictingProofs;
+ std::vector<COutPoint> conflictingOutpoints;
+ for (size_t i = 0; i < 10; i++) {
+ auto outpoint = createUtxo(key);
+ auto proof = buildProofWithSequence(key, {{outpoint}}, sequence);
+ BOOST_CHECK(pm.registerProof(proof));
+ conflictingProofs.push_back(std::move(proof));
+ conflictingOutpoints.push_back(std::move(outpoint));
+ }
+
+ tree = pm.getShareableProofsSnapshot();
+ expectedProofs.insert(conflictingProofs.begin(), conflictingProofs.end());
+ BOOST_CHECK(matchExpectedContent(tree));
+
+ // Build a bunch of conflicting proofs, half better, half worst
+ for (size_t i = 0; i < 10; i += 2) {
+ // The worst proof is not added to the expected set
+ BOOST_CHECK(!pm.registerProof(buildProofWithSequence(
+ key, {{conflictingOutpoints[i]}}, sequence - 1)));
+
+ // But the better proof should replace its conflicting one
+ auto replacementProof = buildProofWithSequence(
+ key, {{conflictingOutpoints[i + 1]}}, sequence + 1);
+ BOOST_CHECK(pm.registerProof(replacementProof));
+ BOOST_CHECK_EQUAL(expectedProofs.erase(conflictingProofs[i + 1]), 1);
+ BOOST_CHECK(expectedProofs.insert(replacementProof).second);
+ }
+
+ tree = pm.getShareableProofsSnapshot();
+ BOOST_CHECK(matchExpectedContent(tree));
+
+ // Check for consistency
+ pm.verify();
+
+ gArgs.ClearForcedArg("-enableavalancheproofreplacement");
+}
+
BOOST_AUTO_TEST_SUITE_END()

File Metadata

Mime Type
text/plain
Expires
Tue, May 20, 19:18 (3 h, 23 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
5865766
Default Alt Text
D11450.id33695.diff (7 KB)

Event Timeline