Bitcoin ABC  0.22.13
P2P Digital Currency
peermanager.cpp
Go to the documentation of this file.
1 // Copyright (c) 2020 The Bitcoin developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
6 
7 #include <avalanche/delegation.h>
8 #include <avalanche/validation.h>
9 #include <random.h>
10 #include <validation.h> // For ChainstateActive()
11 
12 #include <cassert>
13 
14 namespace avalanche {
15 
16 bool PeerManager::addNode(NodeId nodeid, const Proof &proof,
17  const Delegation &delegation) {
18  auto it = fetchOrCreatePeer(proof);
19  if (it == peers.end()) {
20  return false;
21  }
22 
23  const PeerId peerid = it->peerid;
24 
25  DelegationState state;
26  CPubKey pubkey;
27  if (!delegation.verify(state, proof, pubkey)) {
28  return false;
29  }
30 
31  auto nit = nodes.find(nodeid);
32  if (nit == nodes.end()) {
33  if (!nodes.emplace(nodeid, peerid, std::move(pubkey)).second) {
34  return false;
35  }
36  } else {
37  const PeerId oldpeerid = nit->peerid;
38  if (!nodes.modify(nit, [&](Node &n) {
39  n.peerid = peerid;
40  n.pubkey = std::move(pubkey);
41  })) {
42  return false;
43  }
44 
45  // We actually have this node already, we need to update it.
46  bool success = removeNodeFromPeer(peers.find(oldpeerid));
47  assert(success);
48 
49  // Make sure it is not invalidated.
50  it = peers.find(peerid);
51  }
52 
53  bool success = addNodeToPeer(it);
54  assert(success);
55 
56  return true;
57 }
58 
59 bool PeerManager::addNodeToPeer(const PeerSet::iterator &it) {
60  assert(it != peers.end());
61  return peers.modify(it, [&](Peer &p) {
62  if (p.node_count++ > 0) {
63  // We are done.
64  return;
65  }
66 
67  // We ned to allocate this peer.
68  p.index = uint32_t(slots.size());
69  const uint32_t score = p.getScore();
70  const uint64_t start = slotCount;
71  slots.emplace_back(start, score, it->peerid);
72  slotCount = start + score;
73  });
74 }
75 
77  auto it = nodes.find(nodeid);
78  if (it == nodes.end()) {
79  return false;
80  }
81 
82  const PeerId peerid = it->peerid;
83  nodes.erase(it);
84 
85  // Keep the track of the reference count.
86  bool success = removeNodeFromPeer(peers.find(peerid));
87  assert(success);
88 
89  return true;
90 }
91 
92 bool PeerManager::removeNodeFromPeer(const PeerSet::iterator &it,
93  uint32_t count) {
94  assert(it != peers.end());
95  assert(count <= it->node_count);
96  if (count == 0) {
97  // This is a NOOP.
98  return false;
99  }
100 
101  const uint32_t new_count = it->node_count - count;
102  if (!peers.modify(it, [&](Peer &p) { p.node_count = new_count; })) {
103  return false;
104  }
105 
106  if (new_count > 0) {
107  // We are done.
108  return true;
109  }
110 
111  // There are no more node left, we need to cleanup.
112  const size_t i = it->index;
113  assert(i < slots.size());
114  if (i + 1 == slots.size()) {
115  slots.pop_back();
116  slotCount = slots.empty() ? 0 : slots.back().getStop();
117  } else {
118  fragmentation += slots[i].getScore();
119  slots[i] = slots[i].withPeerId(NO_PEER);
120  }
121 
122  return true;
123 }
124 
126  std::function<bool(const Node &n)> func) const {
127  auto it = nodes.find(nodeid);
128  return it != nodes.end() && func(*it);
129 }
130 
132  auto it = nodes.find(nodeid);
133  if (it == nodes.end()) {
134  return false;
135  }
136 
137  return nodes.modify(it, [&](Node &n) { n.nextRequestTime = timeout; });
138 }
139 
141  for (int retry = 0; retry < SELECT_NODE_MAX_RETRY; retry++) {
142  const PeerId p = selectPeer();
143 
144  // If we cannot find a peer, it may be due to the fact that it is
145  // unlikely due to high fragmentation, so compact and retry.
146  if (p == NO_PEER) {
147  compact();
148  continue;
149  }
150 
151  // See if that peer has an available node.
152  auto &nview = nodes.get<next_request_time>();
153  auto it = nview.lower_bound(boost::make_tuple(p, TimePoint()));
154  if (it != nview.end() && it->peerid == p &&
155  it->nextRequestTime <= std::chrono::steady_clock::now()) {
156  return it->nodeid;
157  }
158  }
159 
160  return NO_NODE;
161 }
162 
164  std::vector<PeerId> invalidPeers;
165 
166  {
167  LOCK(cs_main);
168 
169  const CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
170  for (const auto &p : peers) {
171  ProofValidationState state;
172  if (!p.proof.verify(state, coins)) {
173  invalidPeers.push_back(p.peerid);
174  }
175  }
176  }
177 
178  for (const auto &pid : invalidPeers) {
179  removePeer(pid);
180  }
181 }
182 
184  auto it = fetchOrCreatePeer(proof);
185  return it == peers.end() ? NO_PEER : it->peerid;
186 }
187 
188 PeerManager::PeerSet::iterator
190  {
191  // Check if we already know of that peer.
192  auto &pview = peers.get<proof_index>();
193  auto it = pview.find(proof.getId());
194  if (it != pview.end()) {
195  return peers.project<0>(it);
196  }
197  }
198 
199  {
200  // Reject invalid proof.
201  LOCK(cs_main);
202  const CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
203 
204  ProofValidationState state;
205  if (!proof.verify(state, coins)) {
206  return peers.end();
207  }
208  }
209 
210  // New peer means new peerid!
211  const PeerId peerid = nextPeerId++;
212 
213  // Attach UTXOs to this proof.
214  std::unordered_set<PeerId> conflicting_peerids;
215  for (const auto &s : proof.getStakes()) {
216  auto p = utxos.emplace(s.getStake().getUTXO(), peerid);
217  if (!p.second) {
218  // We have a collision with an existing proof.
219  conflicting_peerids.insert(p.first->second);
220  }
221  }
222 
223  // For now, if there is a conflict, just ceanup the mess.
224  if (conflicting_peerids.size() > 0) {
225  for (const auto &s : proof.getStakes()) {
226  auto it = utxos.find(s.getStake().getUTXO());
227  assert(it != utxos.end());
228 
229  // We need to delete that one.
230  if (it->second == peerid) {
231  utxos.erase(it);
232  }
233  }
234 
235  return peers.end();
236  }
237 
238  // We have no peer for this proof, time to create it.
239  auto inserted = peers.emplace(peerid, proof);
240  assert(inserted.second);
241 
242  return inserted.first;
243 }
244 
245 bool PeerManager::removePeer(const PeerId peerid) {
246  auto it = peers.find(peerid);
247  if (it == peers.end()) {
248  return false;
249  }
250 
251  // Remove all nodes from this peer.
252  removeNodeFromPeer(it, it->node_count);
253 
254  // Remove nodes associated with this peer, unless their timeout is still
255  // active. This ensure that we don't overquery them in case they are
256  // subsequently added to another peer.
257  auto &nview = nodes.get<next_request_time>();
258  nview.erase(nview.lower_bound(boost::make_tuple(peerid, TimePoint())),
259  nview.upper_bound(boost::make_tuple(
260  peerid, std::chrono::steady_clock::now())));
261 
262  // Release UTXOs attached to this proof.
263  for (const auto &s : it->proof.getStakes()) {
264  bool deleted = utxos.erase(s.getStake().getUTXO()) > 0;
265  assert(deleted);
266  }
267 
268  peers.erase(it);
269  return true;
270 }
271 
273  if (slots.empty() || slotCount == 0) {
274  return NO_PEER;
275  }
276 
277  const uint64_t max = slotCount;
278  for (int retry = 0; retry < SELECT_PEER_MAX_RETRY; retry++) {
279  size_t i = selectPeerImpl(slots, GetRand(max), max);
280  if (i != NO_PEER) {
281  return i;
282  }
283  }
284 
285  return NO_PEER;
286 }
287 
289  // There is nothing to compact.
290  if (fragmentation == 0) {
291  return 0;
292  }
293 
294  std::vector<Slot> newslots;
295  newslots.reserve(peers.size());
296 
297  uint64_t prevStop = 0;
298  uint32_t i = 0;
299  for (auto it = peers.begin(); it != peers.end(); it++) {
300  if (it->node_count == 0) {
301  continue;
302  }
303 
304  newslots.emplace_back(prevStop, it->getScore(), it->peerid);
305  prevStop = slots[i].getStop();
306  if (!peers.modify(it, [&](Peer &p) { p.index = i++; })) {
307  return 0;
308  }
309  }
310 
311  slots = std::move(newslots);
312 
313  const uint64_t saved = slotCount - prevStop;
314  slotCount = prevStop;
315  fragmentation = 0;
316 
317  return saved;
318 }
319 
320 bool PeerManager::verify() const {
321  uint64_t prevStop = 0;
322  for (size_t i = 0; i < slots.size(); i++) {
323  const Slot &s = slots[i];
324 
325  // Slots must be in correct order.
326  if (s.getStart() < prevStop) {
327  return false;
328  }
329 
330  prevStop = s.getStop();
331 
332  // If this is a dead slot, then nothing more needs to be checked.
333  if (s.getPeerId() == NO_PEER) {
334  continue;
335  }
336 
337  // We have a live slot, verify index.
338  auto it = peers.find(s.getPeerId());
339  if (it == peers.end() || it->index != i) {
340  return false;
341  }
342  }
343 
344  for (const auto &p : peers) {
345  // Count node attached to this peer.
346  const auto count_nodes = [&]() {
347  size_t count = 0;
348  auto &nview = nodes.get<next_request_time>();
349  auto begin =
350  nview.lower_bound(boost::make_tuple(p.peerid, TimePoint()));
351  auto end =
352  nview.upper_bound(boost::make_tuple(p.peerid + 1, TimePoint()));
353 
354  for (auto it = begin; it != end; ++it) {
355  count++;
356  }
357 
358  return count;
359  };
360 
361  if (p.node_count != count_nodes()) {
362  return false;
363  }
364 
365  // If there are no nodes attached to this peer, then we are done.
366  if (p.node_count == 0) {
367  continue;
368  }
369 
370  // The index must point to a slot refering to this peer.
371  if (p.index >= slots.size() || slots[p.index].getPeerId() != p.peerid) {
372  return false;
373  }
374 
375  // If the score do not match, same thing.
376  if (slots[p.index].getScore() != p.getScore()) {
377  return false;
378  }
379  }
380 
381  return true;
382 }
383 
384 PeerId selectPeerImpl(const std::vector<Slot> &slots, const uint64_t slot,
385  const uint64_t max) {
386  assert(slot <= max);
387 
388  size_t begin = 0, end = slots.size();
389  uint64_t bottom = 0, top = max;
390 
391  // Try to find the slot using dichotomic search.
392  while ((end - begin) > 8) {
393  // The slot we picked in not allocated.
394  if (slot < bottom || slot >= top) {
395  return NO_PEER;
396  }
397 
398  // Guesstimate the position of the slot.
399  size_t i = begin + ((slot - bottom) * (end - begin) / (top - bottom));
400  assert(begin <= i && i < end);
401 
402  // We have a match.
403  if (slots[i].contains(slot)) {
404  return slots[i].getPeerId();
405  }
406 
407  // We undershooted.
408  if (slots[i].precedes(slot)) {
409  begin = i + 1;
410  if (begin >= end) {
411  return NO_PEER;
412  }
413 
414  bottom = slots[begin].getStart();
415  continue;
416  }
417 
418  // We overshooted.
419  if (slots[i].follows(slot)) {
420  end = i;
421  top = slots[end].getStart();
422  continue;
423  }
424 
425  // We have an unalocated slot.
426  return NO_PEER;
427  }
428 
429  // Enough of that nonsense, let fallback to linear search.
430  for (size_t i = begin; i < end; i++) {
431  // We have a match.
432  if (slots[i].contains(slot)) {
433  return slots[i].getPeerId();
434  }
435  }
436 
437  // We failed to find a slot, retry.
438  return NO_PEER;
439 }
440 
441 } // namespace avalanche
uint64_t compact()
Trigger maintenance of internal datastructures.
static constexpr NodeId NO_NODE
Special NodeId that represent no node.
Definition: net.h:104
uint64_t GetRand(uint64_t nMax) noexcept
Definition: random.cpp:641
bool removeNode(NodeId nodeid)
Definition: peermanager.cpp:76
const std::vector< SignedStake > & getStakes() const
Definition: proof.h:114
bool verify() const
Perform consistency check on internal data structures.
bool verify(DelegationState &state, const Proof &proof, CPubKey &auth) const
Definition: delegation.cpp:40
bool removeNodeFromPeer(const PeerSet::iterator &it, uint32_t count=1)
Definition: peermanager.cpp:92
bool updateNextRequestTime(NodeId nodeid, TimePoint timeout)
PeerId getPeerId() const
Definition: peermanager.h:52
PeerId selectPeer() const
Randomly select a peer to poll.
PeerId selectPeerImpl(const std::vector< Slot > &slots, const uint64_t slot, const uint64_t max)
This is an internal method that is exposed for testing purposes.
CChainState & ChainstateActive()
Definition: validation.cpp:72
NodeId selectNode()
Randomly select a node to poll.
uint64_t getStart() const
Definition: peermanager.h:49
bool addNodeToPeer(const PeerSet::iterator &it)
Definition: peermanager.cpp:59
#define LOCK(cs)
Definition: sync.h:230
An encapsulated public key.
Definition: pubkey.h:31
uint32_t getScore() const
Definition: peermanager.h:72
bool addNode(NodeId nodeid, const Proof &proof, const Delegation &delegation)
Node API.
Definition: peermanager.cpp:16
RecursiveMutex cs_main
Global state.
Definition: validation.cpp:95
PeerSet::iterator fetchOrCreatePeer(const Proof &proof)
int64_t NodeId
Definition: net.h:99
bool verify(ProofValidationState &state) const
Definition: proof.cpp:52
uint32_t node_count
Definition: peermanager.h:64
bool removePeer(const PeerId peerid)
Remove an existing peer.
const ProofId & getId() const
Definition: proof.h:116
TimePoint nextRequestTime
Definition: node.h:24
static constexpr int SELECT_PEER_MAX_RETRY
Definition: peermanager.h:130
std::vector< Slot > slots
Definition: peermanager.h:90
static int count
Definition: tests.c:35
PeerId getPeerId(const Proof &proof)
Provide the PeerId associated with the given proof.
std::chrono::time_point< std::chrono::steady_clock > TimePoint
Definition: node.h:17
uint64_t getStop() const
Definition: peermanager.h:50
CCoinsViewCache & CoinsTip() EXCLUSIVE_LOCKS_REQUIRED(cs_main)
Definition: validation.h:775
std::unordered_map< COutPoint, PeerId, SaltedOutpointHasher > utxos
Definition: peermanager.h:111
CCoinsView that adds a memory cache for transactions to another CCoinsView.
Definition: coins.h:231
static constexpr int SELECT_NODE_MAX_RETRY
Definition: peermanager.h:131
static constexpr PeerId NO_PEER
Definition: node.h:15
void updatedBlockTip()
Update the peer set when a nw block is connected.
uint32_t index
Definition: peermanager.h:63
uint32_t PeerId
Definition: node.h:14
bool forNode(NodeId nodeid, std::function< bool(const Node &n)> func) const