Changeset View
Changeset View
Standalone View
Standalone View
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 Lines | BOOST_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() |