Differential D6787 Diff 21925 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>

void PeerManager::addPeer(uint32_t score) {		#include <cassert>

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

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

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

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

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

		peerIndices.erase(it);
		return true;
		}

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

void PeerManager::rescorePeer(size_t i, uint32_t score) {		size_t i = it->second;
assert(i < slots.size());		assert(i < slots.size());

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;		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;		return true;
}		}

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

		return true;
}		}

size_t PeerManager::selectPeer() const {		PeerId PeerManager::selectPeer() const {
if (slots.empty()) {		if (slots.empty()) {
return NO_PEER;		return NO_PEER;
}		}

const uint64_t max = slotCount;		const uint64_t max = slotCount;
while (true) {		while (true) {
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;
}		}
}		}
}		}

size_t 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);

size_t begin = 0, end = slots.size();		size_t begin = 0, end = slots.size();
uint64_t bottom = 0, top = max;		uint64_t bottom = 0, top = max;

// Try to find the slot using dichotomic search.		// Try to find the slot using dichotomic search.
while ((end - begin) > 8) {		while ((end - begin) > 8) {
// The slot we picked in not allocated.		// The slot we picked in not allocated.
if (slot < bottom \|\| slot >= top) {		if (slot < bottom \|\| slot >= top) {
return NO_PEER;		return NO_PEER;
}		}

// Guesstimate the position of the slot.		// Guesstimate the position of the slot.
size_t i = begin + ((slot - bottom) * (end - begin) / (top - bottom));		size_t i = begin + ((slot - bottom) * (end - begin) / (top - bottom));
assert(begin <= i && i < end);		assert(begin <= i && i < end);

// We have a match.		// We have a match.
if (slots[i].contains(slot)) {		if (slots[i].contains(slot)) {
return i;		return slots[i].getPeerId();
}		}

// We undershooted.		// We undershooted.
if (slots[i].precedes(slot)) {		if (slots[i].precedes(slot)) {
begin = i + 1;		begin = i + 1;
if (begin >= end) {		if (begin >= end) {
return NO_PEER;		return NO_PEER;
}		}
Show All 12 Lines	while ((end - begin) > 8) {
// We have an unalocated slot.		// We have an unalocated slot.
return NO_PEER;		return NO_PEER;
}		}

// Enough of that nonsense, let fallback to linear search.		// Enough of that nonsense, let fallback to linear search.
for (size_t i = begin; i < end; i++) {		for (size_t i = begin; i < end; i++) {
// We have a match.		// We have a match.
if (slots[i].contains(slot)) {		if (slots[i].contains(slot)) {
return i;		return slots[i].getPeerId();
}		}
}		}

// We failed to find a slot, retry.		// We failed to find a slot, retry.
return NO_PEER;		return NO_PEER;
}		}