Page MenuHomePhabricator
Differential D6787 Diff 21915 src/avalanche/test/peermanager_tests.cpp

Changeset View

Standalone View

View Options

src/avalanche/test/peermanager_tests.cpp

Show All 10 Lines
BOOST_FIXTURE_TEST_SUITE(peermanager_tests, BasicTestingSetup) BOOST_FIXTURE_TEST_SUITE(peermanager_tests, BasicTestingSetup)
BOOST_AUTO_TEST_CASE(select_peer_linear) { BOOST_AUTO_TEST_CASE(select_peer_linear) {
// No peers. // No peers.
BOOST_CHECK_EQUAL(selectPeerImpl({}, 0, 0), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl({}, 0, 0), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl({}, 1, 3), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl({}, 1, 3), NO_PEER);
// One peer // One peer
const std::vector<Slot> oneslot = {{100, 100}}; const std::vector<Slot> oneslot = {{100, 100, 23}};
// Undershoot // Undershoot
BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 0, 300), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 0, 300), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 42, 300), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 42, 300), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 99, 300), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 99, 300), NO_PEER);
// Nailed it // Nailed it
BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 100, 300), 0); BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 100, 300), 23);
BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 142, 300), 0); BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 142, 300), 23);
BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 199, 300), 0); BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 199, 300), 23);
// Overshoot // Overshoot
BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 200, 300), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 200, 300), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 242, 300), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 242, 300), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 299, 300), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(oneslot, 299, 300), NO_PEER);
// Two peers // Two peers
const std::vector<Slot> twoslots = {{100, 100}, {300, 100}}; const std::vector<Slot> twoslots = {{100, 100, 69}, {300, 100, 42}};
// Undershoot // Undershoot
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 0, 500), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 0, 500), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 42, 500), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 42, 500), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 99, 500), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 99, 500), NO_PEER);
// First entry // First entry
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 100, 500), 0); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 100, 500), 69);
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 142, 500), 0); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 142, 500), 69);
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 199, 500), 0); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 199, 500), 69);
// In betwenn // In betwenn
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 200, 500), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 200, 500), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 242, 500), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 242, 500), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 299, 500), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 299, 500), NO_PEER);
// Second entry // Second entry
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 300, 500), 1); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 300, 500), 42);
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 342, 500), 1); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 342, 500), 42);
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 399, 500), 1); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 399, 500), 42);
// Overshoot // Overshoot
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 400, 500), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 400, 500), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 442, 500), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 442, 500), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 499, 500), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(twoslots, 499, 500), NO_PEER);
} }
BOOST_AUTO_TEST_CASE(select_peer_dichotomic) { BOOST_AUTO_TEST_CASE(select_peer_dichotomic) {
std::vector<Slot> slots; std::vector<Slot> slots;
// 100 peers of size 1 with 1 empty element apart. // 100 peers of size 1 with 1 empty element apart.
uint64_t max = 1; uint64_t max = 1;
for (int i = 0; i < 100; i++) { for (int i = 0; i < 100; i++) {
slots.emplace_back(max, 1); slots.emplace_back(max, 1, i);
max += 2; max += 2;
} }
BOOST_CHECK_EQUAL(selectPeerImpl(slots, 4, max), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(slots, 4, max), NO_PEER);
// Check that we get what we expect. // Check that we get what we expect.
for (int i = 0; i < 100; i++) { for (int i = 0; i < 100; i++) {
BOOST_CHECK_EQUAL(selectPeerImpl(slots, 2 * i, max), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(slots, 2 * i, max), NO_PEER);
Show All 14 LinesBOOST_AUTO_TEST_CASE(select_peer_dichotomic) {
BOOST_CHECK_EQUAL(selectPeerImpl(slots, 200, max), 99); BOOST_CHECK_EQUAL(selectPeerImpl(slots, 200, max), 99);
BOOST_CHECK_EQUAL(selectPeerImpl(slots, 256, max), 99); BOOST_CHECK_EQUAL(selectPeerImpl(slots, 256, max), 99);
BOOST_CHECK_EQUAL(selectPeerImpl(slots, 299, max), 99); BOOST_CHECK_EQUAL(selectPeerImpl(slots, 299, max), 99);
BOOST_CHECK_EQUAL(selectPeerImpl(slots, 300, max), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(slots, 300, max), NO_PEER);
// Update the slots to be heavily skewed toward the first element. // Update the slots to be heavily skewed toward the first element.
for (int i = 0; i < 100; i++) { for (int i = 0; i < 100; i++) {
slots[i] = Slot(slots[i].getStart() + 100, slots[i].getScore()); slots[i] = Slot(slots[i].getStart() + 100, slots[i].getScore(),
slots[i].getPeerId());
} }
slots[0] = Slot(1, slots[0].getStop() - 1); slots[0] = Slot(1, slots[0].getStop() - 1, slots[0].getPeerId());
slots[99] = slots[99].withScore(1); slots[99] = slots[99].withScore(1);
max = slots[99].getStop(); max = slots[99].getStop();
BOOST_CHECK_EQUAL(max, 300); BOOST_CHECK_EQUAL(max, 300);
BOOST_CHECK_EQUAL(selectPeerImpl(slots, 0, max), NO_PEER); BOOST_CHECK_EQUAL(selectPeerImpl(slots, 0, max), NO_PEER);
BOOST_CHECK_EQUAL(selectPeerImpl(slots, 1, max), 0); BOOST_CHECK_EQUAL(selectPeerImpl(slots, 1, max), 0);
BOOST_CHECK_EQUAL(selectPeerImpl(slots, 42, max), 0); BOOST_CHECK_EQUAL(selectPeerImpl(slots, 42, max), 0);
Show All 15 Lines for (int c = 0; c < 1000; c++) {
max += InsecureRandBits(3); max += InsecureRandBits(3);
return r; return r;
}; };
for (size_t i = 0; i < size; i++) { for (size_t i = 0; i < size; i++) {
const uint64_t start = next(); const uint64_t start = next();
const uint32_t score = InsecureRandBits(3); const uint32_t score = InsecureRandBits(3);
max += score; max += score;
slots.emplace_back(start, score); slots.emplace_back(start, score, i);
} }
for (int k = 0; k < 100; k++) { for (int k = 0; k < 100; k++) {
uint64_t s = InsecureRandRange(max); uint64_t s = InsecureRandRange(max);
auto i = selectPeerImpl(slots, s, max); auto i = selectPeerImpl(slots, s, max);
// /!\ Because of the way we construct the vector, the peer id is
// always the index. This might not be the case in practice.
BOOST_CHECK(i == NO_PEER || slots[i].contains(s)); BOOST_CHECK(i == NO_PEER || slots[i].contains(s));
} }
} }
} }
BOOST_AUTO_TEST_CASE(add_peer) { BOOST_AUTO_TEST_CASE(add_peer) {
// No peers. // No peers.
PeerManager pm; PeerManager pm;
BOOST_CHECK_EQUAL(pm.selectPeer(), NO_PEER); BOOST_CHECK_EQUAL(pm.selectPeer(), NO_PEER);
// One peer, we always return it. // One peer, we always return it.
pm.addPeer(100); PeerId peer0 = pm.addPeer(100);
BOOST_CHECK_EQUAL(pm.selectPeer(), 0); BOOST_CHECK_EQUAL(pm.selectPeer(), peer0);
// Two peers, verify ratio. // Two peers, verify ratio.
pm.addPeer(200); PeerId peer1 = pm.addPeer(200);
std::array<int, 3> results = {}; std::unordered_map<PeerId, int> results = {};
for (int i = 0; i < 10000; i++) { for (int i = 0; i < 10000; i++) {
size_t p = pm.selectPeer(); size_t p = pm.selectPeer();
BOOST_CHECK(p <= 1); BOOST_CHECK(p == peer0 || p == peer1);
results[p]++; results[p]++;
} }
BOOST_CHECK(abs(2 * results[0] - results[1]) < 500); BOOST_CHECK(abs(2 * results[0] - results[1]) < 500);
// Three peers, verify ratio. // Three peers, verify ratio.
pm.addPeer(100); PeerId peer2 = pm.addPeer(100);
results = {}; results.clear();
for (int i = 0; i < 10000; i++) { for (int i = 0; i < 10000; i++) {
size_t p = pm.selectPeer(); size_t p = pm.selectPeer();
BOOST_CHECK(p <= 2); BOOST_CHECK(p == peer0 || p == peer1 || p == peer2);
results[p]++; results[p]++;
} }
BOOST_CHECK(abs(results[0] - results[1] + results[2]) < 500); BOOST_CHECK(abs(results[0] - results[1] + results[2]) < 500);
} }
BOOST_AUTO_TEST_CASE(remove_peer) { BOOST_AUTO_TEST_CASE(remove_peer) {
// No peers. // No peers.
PeerManager pm; PeerManager pm;
BOOST_CHECK_EQUAL(pm.selectPeer(), NO_PEER); BOOST_CHECK_EQUAL(pm.selectPeer(), NO_PEER);
// Add 4 peers. // Add 4 peers.
std::array<PeerId, 8> peerids;
for (int i = 0; i < 4; i++) { for (int i = 0; i < 4; i++) {
pm.addPeer(100); peerids[i] = pm.addPeer(100);
} }
BOOST_CHECK_EQUAL(pm.getSlotCount(), 400);
BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
for (int i = 0; i < 100; i++) { for (int i = 0; i < 100; i++) {
size_t p = pm.selectPeer(); PeerId p = pm.selectPeer();
BOOST_CHECK(p <= 4); BOOST_CHECK(p == peerids[0] || p == peerids[1] || p == peerids[2] ||
p == peerids[3]);
} }
// Remove one peer, it nevers show up now. // Remove one peer, it nevers show up now.
pm.removePeer(3); BOOST_CHECK(pm.removePeer(peerids[2]));
BOOST_CHECK_EQUAL(pm.getSlotCount(), 400);
BOOST_CHECK_EQUAL(pm.getFragmentation(), 100);
for (int i = 0; i < 100; i++) { for (int i = 0; i < 100; i++) {
size_t p = pm.selectPeer(); PeerId p = pm.selectPeer();
BOOST_CHECK(p < 4); BOOST_CHECK(p == peerids[0] || p == peerids[1] || p == peerids[3]);
BOOST_CHECK(p != 3);
} }
// Add 4 more peers. // Add 4 more peers.
for (int i = 0; i < 4; i++) { for (int i = 0; i < 4; i++) {
pm.addPeer(100); peerids[i + 4] = pm.addPeer(100);
} }
pm.removePeer(0); BOOST_CHECK_EQUAL(pm.getSlotCount(), 800);
pm.removePeer(7); BOOST_CHECK_EQUAL(pm.getFragmentation(), 100);
BOOST_CHECK(pm.removePeer(peerids[0]));
BOOST_CHECK_EQUAL(pm.getSlotCount(), 800);
BOOST_CHECK_EQUAL(pm.getFragmentation(), 200);
// Removing the last entry do not increase fragmentation.
BOOST_CHECK(pm.removePeer(peerids[7]));
BOOST_CHECK_EQUAL(pm.getSlotCount(), 700);
BOOST_CHECK_EQUAL(pm.getFragmentation(), 200);
for (int i = 0; i < 100; i++) { for (int i = 0; i < 100; i++) {
size_t p = pm.selectPeer(); PeerId p = pm.selectPeer();
BOOST_CHECK(p < 8); BOOST_CHECK(p == peerids[1] || p == peerids[3] || p == peerids[4] ||
BOOST_CHECK(p != 0); p == peerids[5] || p == peerids[6]);
BOOST_CHECK(p != 3);
BOOST_CHECK(p != 7);
} }
// Removing non existent peers fails.
BOOST_CHECK(!pm.removePeer(peerids[0]));
BOOST_CHECK(!pm.removePeer(peerids[2]));
BOOST_CHECK(!pm.removePeer(peerids[7]));
BOOST_CHECK(!pm.removePeer(NO_PEER));
} }
BOOST_AUTO_TEST_CASE(rescore_peer, *boost::unit_test::timeout(5)) { BOOST_AUTO_TEST_CASE(rescore_peer, *boost::unit_test::timeout(5)) {
// No peers. // No peers.
PeerManager pm; PeerManager pm;
BOOST_CHECK_EQUAL(pm.selectPeer(), NO_PEER); BOOST_CHECK_EQUAL(pm.selectPeer(), NO_PEER);
// Add 4 peers. // Add 4 peers.
std::array<PeerId, 4> peerids;
for (int i = 0; i < 4; i++) { for (int i = 0; i < 4; i++) {
pm.addPeer(100); peerids[i] = pm.addPeer(100);
} }
BOOST_CHECK_EQUAL(pm.getSlotCount(), 400); BOOST_CHECK_EQUAL(pm.getSlotCount(), 400);
BOOST_CHECK_EQUAL(pm.getFragmentation(), 0); BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
for (int i = 0; i < 100; i++) { for (int i = 0; i < 100; i++) {
size_t p = pm.selectPeer(); PeerId p = pm.selectPeer();
BOOST_CHECK(p <= 4); BOOST_CHECK(p == peerids[0] || p == peerids[1] || p == peerids[2] ||
p == peerids[3]);
} }
// Set one peer's score to 0, it nevers show up now. // Set one peer's score to 0, it nevers show up now.
pm.rescorePeer(1, 0); BOOST_CHECK(pm.rescorePeer(peerids[1], 0));
BOOST_CHECK_EQUAL(pm.getSlotCount(), 400); BOOST_CHECK_EQUAL(pm.getSlotCount(), 400);
BOOST_CHECK_EQUAL(pm.getFragmentation(), 100); BOOST_CHECK_EQUAL(pm.getFragmentation(), 100);
for (int i = 0; i < 100; i++) { for (int i = 0; i < 100; i++) {
size_t p = pm.selectPeer(); PeerId p = pm.selectPeer();
BOOST_CHECK(p < 4); BOOST_CHECK(p == peerids[0] || p == peerids[2] || p == peerids[3]);
BOOST_CHECK(p != 1);
} }
// "resurrect" the peer. // "resurrect" the peer.
pm.rescorePeer(1, 100); BOOST_CHECK(pm.rescorePeer(peerids[1], 100));
BOOST_CHECK_EQUAL(pm.getSlotCount(), 400); BOOST_CHECK_EQUAL(pm.getSlotCount(), 400);
BOOST_CHECK_EQUAL(pm.getFragmentation(), 0); BOOST_CHECK_EQUAL(pm.getFragmentation(), 0);
while (true) { while (true) {
size_t p = pm.selectPeer(); PeerId p = pm.selectPeer();
if (p == 1) { BOOST_CHECK(p == peerids[0] || p == peerids[1] || p == peerids[2] ||
p == peerids[3]);
// Make sure peer 1 reappeared.
if (p == peerids[1]) {
break; break;
} }
} }
// Grow the peer to a point where it needs to be reallocated. // Grow the peer to a point where it needs to be reallocated.
pm.rescorePeer(1, 200); BOOST_CHECK(pm.rescorePeer(peerids[1], 200));
BOOST_CHECK_EQUAL(pm.getSlotCount(), 600); BOOST_CHECK_EQUAL(pm.getSlotCount(), 600);
BOOST_CHECK_EQUAL(pm.getFragmentation(), 100); BOOST_CHECK_EQUAL(pm.getFragmentation(), 100);
for (int i = 0; i < 25; i++) { for (int i = 0; i < 25; i++) {
while (true) { while (true) {
size_t p = pm.selectPeer(); PeerId p = pm.selectPeer();
BOOST_CHECK(p < 5); BOOST_CHECK(p == peerids[0] || p == peerids[1] || p == peerids[2] ||
BOOST_CHECK(p != 1); p == peerids[3]);
if (p == 4) { // Make sure peer 1 reappeared.
if (p == peerids[1]) {
break; break;
} }
} }
} }
} }
BOOST_AUTO_TEST_SUITE_END() BOOST_AUTO_TEST_SUITE_END()