diff --git a/src/avalanche/peermanager.cpp b/src/avalanche/peermanager.cpp index 8c056c39f..88c66c792 100644 --- a/src/avalanche/peermanager.cpp +++ b/src/avalanche/peermanager.cpp @@ -1,111 +1,111 @@ // Copyright (c) 2020 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include #include -void PeerManager::addPeer(uint64_t score) { +void PeerManager::addPeer(uint32_t score) { const uint64_t start = slotCount; slots.emplace_back(start, score); slotCount = start + score; } -void PeerManager::rescorePeer(size_t i, uint64_t score) { +void PeerManager::rescorePeer(size_t i, uint32_t score) { assert(i < slots.size()); const uint64_t start = slots[i].getStart(); // If this is the last element, we can extend/shrink easily. if (i + 1 == slots.size()) { slots[i] = slots[i].withScore(score); slotCount = slots[i].getStop(); return; } const uint64_t stop = start + score; const uint64_t nextStart = slots[i + 1].getStart(); // We can extend in place. if (stop <= nextStart) { fragmentation += (slots[i].getStop() - stop); slots[i] = slots[i].withScore(score); return; } // So we remove and insert a new entry. addPeer(score); removePeer(i); } size_t PeerManager::selectPeer() const { if (slots.empty()) { return NO_PEER; } const uint64_t max = slotCount; while (true) { size_t i = selectPeerImpl(slots, GetRand(max), max); if (i != NO_PEER) { return i; } } } size_t selectPeerImpl(const std::vector &slots, const uint64_t slot, const uint64_t max) { assert(slot <= max); size_t begin = 0, end = slots.size(); uint64_t bottom = 0, top = max; // Try to find the slot using dichotomic search. while ((end - begin) > 8) { // The slot we picked in not allocated. if (slot < bottom || slot >= top) { return NO_PEER; } // Guesstimate the position of the slot. size_t i = begin + ((slot - bottom) * (end - begin) / (top - bottom)); assert(begin <= i && i < end); // We have a match. if (slots[i].contains(slot)) { return i; } // We undershooted. if (slots[i].precedes(slot)) { begin = i + 1; if (begin >= end) { return NO_PEER; } bottom = slots[begin].getStart(); continue; } // We overshooted. if (slots[i].follows(slot)) { end = i; top = slots[end].getStart(); continue; } // We have an unalocated slot. return NO_PEER; } // Enough of that nonsense, let fallback to linear search. for (size_t i = begin; i < end; i++) { // We have a match. if (slots[i].contains(slot)) { return i; } } // We failed to find a slot, retry. return NO_PEER; } diff --git a/src/avalanche/peermanager.h b/src/avalanche/peermanager.h index 33cfd4779..525e2da5c 100644 --- a/src/avalanche/peermanager.h +++ b/src/avalanche/peermanager.h @@ -1,58 +1,58 @@ // Copyright (c) 2020 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_PEERMANAGER_H #define BITCOIN_AVALANCHE_PEERMANAGER_H #include #include #include static constexpr size_t NO_PEER = ~size_t(0); struct Slot { private: uint64_t start; - uint64_t score; + uint32_t score; public: - Slot(uint64_t startIn, uint64_t scoreIn) : start(startIn), score(scoreIn) {} + Slot(uint64_t startIn, uint32_t scoreIn) : start(startIn), score(scoreIn) {} Slot withScore(uint64_t scoreIn) { return Slot(start, scoreIn); } uint64_t getStart() const { return start; } uint64_t getStop() const { return start + score; } - uint64_t getScore() const { return score; } + uint32_t getScore() const { return score; } bool contains(uint64_t slot) const { return getStart() <= slot && slot < getStop(); } bool precedes(uint64_t slot) const { return slot >= getStop(); } bool follows(uint64_t slot) const { return getStart() > slot; } }; class PeerManager { std::vector slots; uint64_t slotCount = 0; uint64_t fragmentation = 0; public: - void addPeer(uint64_t score); - void rescorePeer(size_t i, uint64_t score); + void addPeer(uint32_t score); + void rescorePeer(size_t i, uint32_t score); void removePeer(size_t i) { rescorePeer(i, 0); } size_t selectPeer() const; // Accssors. uint64_t getSlotCount() const { return slotCount; } uint64_t getFragmentation() const { return fragmentation; } }; /** * This is an internal method that is exposed for testing purposes. */ size_t selectPeerImpl(const std::vector &slots, const uint64_t slot, const uint64_t max); #endif // BITCOIN_AVALANCHE_PEERMANAGER_H