Differential D6818 Diff 22015 src/avalanche/peermanager.cpp

Changeset View

Standalone View

src/avalanche/peermanager.cpp

// Copyright (c) 2020 The Bitcoin developers		// Copyright (c) 2020 The Bitcoin developers
// Distributed under the MIT software license, see the accompanying		// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.		// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <avalanche/peermanager.h>		#include <avalanche/peermanager.h>

#include <random.h>		#include <random.h>

#include <cassert>		#include <cassert>

PeerId PeerManager::addPeer(PeerId p, uint32_t score) {		PeerId PeerManager::addPeer(PeerId p, uint32_t score) {
auto inserted = peerIndices.emplace(p, slots.size());		auto inserted = peers.emplace(p, Peer(score, uint32_t(slots.size())));
assert(inserted.second);		assert(inserted.second);

const uint64_t start = slotCount;		const uint64_t start = slotCount;
slots.emplace_back(start, score, p);		slots.emplace_back(start, score, p);
slotCount = start + score;		slotCount = start + score;
return p;		return p;
}		}

bool PeerManager::removePeer(PeerId p) {		bool PeerManager::removePeer(PeerId p) {
auto it = peerIndices.find(p);		auto it = peers.find(p);
if (it == peerIndices.end()) {		if (it == peers.end()) {
return false;		return false;
}		}

size_t i = it->second;		size_t i = it->second.index;
assert(i < slots.size());		assert(i < slots.size());

if (i + 1 == slots.size()) {		if (i + 1 == slots.size()) {
slots.pop_back();		slots.pop_back();
slotCount = slots.empty() ? 0 : slots.back().getStop();		slotCount = slots.empty() ? 0 : slots.back().getStop();
} else {		} else {
fragmentation += slots[i].getScore();		fragmentation += slots[i].getScore();
slots[i] = slots[i].withPeerId(NO_PEER);		slots[i] = slots[i].withPeerId(NO_PEER);
}		}

peerIndices.erase(it);		peers.erase(it);
return true;		return true;
}		}

bool PeerManager::rescorePeer(PeerId p, uint32_t score) {		bool PeerManager::rescorePeer(PeerId p, uint32_t score) {
auto it = peerIndices.find(p);		auto it = peers.find(p);
if (it == peerIndices.end()) {		if (it == peers.end()) {
return false;		return false;
}		}

size_t i = it->second;		size_t i = it->second.index;
assert(i < slots.size());		assert(i < slots.size());

		// Update the peer's score.
		it->second.score = score;

		// Update the slot allocation to reflect the new score.
const uint64_t start = slots[i].getStart();		const uint64_t start = slots[i].getStart();

// If this is the last element, we can extend/shrink easily.		// If this is the last element, we can extend/shrink easily.
if (i + 1 == slots.size()) {		if (i + 1 == slots.size()) {
slots[i] = slots[i].withScore(score);		slots[i] = slots[i].withScore(score);
slotCount = slots[i].getStop();		slotCount = slots[i].getStop();
return true;		return true;
}		}

const uint64_t stop = start + score;		const uint64_t stop = start + score;
const uint64_t nextStart = slots[i + 1].getStart();		const uint64_t nextStart = slots[i + 1].getStart();

// We can extend in place.		// We can extend in place.
if (stop <= nextStart) {		if (stop <= nextStart) {
fragmentation += (slots[i].getStop() - stop);		fragmentation += (slots[i].getStop() - stop);
slots[i] = slots[i].withScore(score);		slots[i] = slots[i].withScore(score);
return true;		return true;
}		}

// So we need to insert a new entry.		// So we need to insert a new entry.
fragmentation += slots[i].getScore();		fragmentation += slots[i].getScore();
slots[i] = slots[i].withPeerId(NO_PEER);		slots[i] = slots[i].withPeerId(NO_PEER);
it->second = slots.size();		it->second.index = uint32_t(slots.size());
const uint64_t newStart = slotCount;		const uint64_t newStart = slotCount;
slots.emplace_back(newStart, score, p);		slots.emplace_back(newStart, score, p);
slotCount = newStart + score;		slotCount = newStart + score;

return true;		return true;
}		}

PeerId PeerManager::selectPeer() const {		PeerId PeerManager::selectPeer() const {
if (slots.empty() \|\| slotCount == 0) {		if (slots.empty() \|\| slotCount == 0) {
return NO_PEER;		return NO_PEER;
}		}

const uint64_t max = slotCount;		const uint64_t max = slotCount;
for (int retry = 0; retry < SELECT_PEER_MAX_RETRY; retry++) {		for (int retry = 0; retry < SELECT_PEER_MAX_RETRY; retry++) {
size_t i = selectPeerImpl(slots, GetRand(max), max);		size_t i = selectPeerImpl(slots, GetRand(max), max);
if (i != NO_PEER) {		if (i != NO_PEER) {
return i;		return i;
}		}
}		}

return NO_PEER;		return NO_PEER;
}		}

uint64_t PeerManager::compact() {		uint64_t PeerManager::compact() {
auto clearLastElements = [this] {		// Shrink the vector to the expected size.
while (!slots.empty() && slots.back().getPeerId() == NO_PEER) {		while (slots.size() > peers.size()) {
slots.pop_back();		slots.pop_back();
}		}
};

// Always make sure that the last element is not dead.
clearLastElements();

uint64_t prevStop = 0;		uint64_t prevStop = 0;
for (size_t i = 0; i < slots.size(); i++) {		uint32_t i = 0;
if (slots[i].getPeerId() != NO_PEER) {		for (auto &pair : peers) {
// This element is good, just slide it to the right position.		PeerId pid = pair.first;
slots[i] = slots[i].withStart(prevStop);		Peer &p = pair.second;
prevStop = slots[i].getStop();
continue;
}

// This element is dead, put the last one it its place.		slots[i] = Slot(prevStop, p.score, pid);
slots[i] = slots.back().withStart(prevStop);
prevStop = slots[i].getStop();		prevStop = slots[i].getStop();

assert(slots[i].getPeerId() != NO_PEER);		p.index = i++;
peerIndices[slots[i].getPeerId()] = i;

slots.pop_back();
clearLastElements();
}		}

const uint64_t saved = slotCount - prevStop;		const uint64_t saved = slotCount - prevStop;
slotCount = prevStop;		slotCount = prevStop;
fragmentation = 0;		fragmentation = 0;

return saved;		return saved;
}		}
Show All 11 Lines	for (size_t i = 0; i < slots.size(); i++) {
prevStop = s.getStop();		prevStop = s.getStop();

// If this is a dead slot, then nothing more needs to be checked.		// If this is a dead slot, then nothing more needs to be checked.
if (s.getPeerId() == NO_PEER) {		if (s.getPeerId() == NO_PEER) {
continue;		continue;
}		}

// We have a live slot, verify index.		// We have a live slot, verify index.
auto it = peerIndices.find(s.getPeerId());		auto it = peers.find(s.getPeerId());
if (it == peerIndices.end() \|\| it->second != i) {		if (it == peers.end() \|\| it->second.index != i) {
return false;		return false;
}		}
}		}

for (const auto &pair : peerIndices) {		for (const auto &pair : peers) {
auto p = pair.first;		auto p = pair.first;
auto i = pair.second;		auto i = pair.second.index;
		auto s = pair.second.score;

// The index must point to a slot refering to this peer.		// The index must point to a slot refering to this peer.
if (i >= slots.size() \|\| slots[i].getPeerId() != p) {		if (i >= slots.size() \|\| slots[i].getPeerId() != p) {
return false;		return false;
}		}

		// If the score do not match, same thing.
		if (slots[i].getScore() != s) {
		return false;
		}
}		}

return true;		return true;
}		}

PeerId selectPeerImpl(const std::vector<Slot> &slots, const uint64_t slot,		PeerId selectPeerImpl(const std::vector<Slot> &slots, const uint64_t slot,
const uint64_t max) {		const uint64_t max) {
assert(slot <= max);		assert(slot <= max);
▲ Show 20 Lines • Show All 53 Lines • Show Last 20 Lines