Bitcoin ABC  0.24.7
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 <algorithm>
13 #include <cassert>
14 
15 namespace avalanche {
16 
17 bool PeerManager::addNode(NodeId nodeid, const ProofId &proofid) {
18  auto &pview = peers.get<by_proofid>();
19  auto it = pview.find(proofid);
20  if (it == pview.end()) {
21  // If the node exists, it is actually updating its proof to an unknown
22  // one. In this case we need to remove it so it is not both active and
23  // pending at the same time.
24  removeNode(nodeid);
25  pendingNodes.emplace(proofid, nodeid);
26  return false;
27  }
28 
29  return addOrUpdateNode(peers.project<0>(it), nodeid);
30 }
31 
32 bool PeerManager::addOrUpdateNode(const PeerSet::iterator &it, NodeId nodeid) {
33  assert(it != peers.end());
34 
35  const PeerId peerid = it->peerid;
36 
37  auto nit = nodes.find(nodeid);
38  if (nit == nodes.end()) {
39  if (!nodes.emplace(nodeid, peerid).second) {
40  return false;
41  }
42  } else {
43  const PeerId oldpeerid = nit->peerid;
44  if (!nodes.modify(nit, [&](Node &n) { n.peerid = peerid; })) {
45  return false;
46  }
47 
48  // We actually have this node already, we need to update it.
49  bool success = removeNodeFromPeer(peers.find(oldpeerid));
50  assert(success);
51  }
52 
53  bool success = addNodeToPeer(it);
54  assert(success);
55 
56  // If the added node was in the pending set, remove it
57  pendingNodes.get<by_nodeid>().erase(nodeid);
58 
59  return true;
60 }
61 
62 bool PeerManager::addNodeToPeer(const PeerSet::iterator &it) {
63  assert(it != peers.end());
64  return peers.modify(it, [&](Peer &p) {
65  if (p.node_count++ > 0) {
66  // We are done.
67  return;
68  }
69 
70  // We need to allocate this peer.
71  p.index = uint32_t(slots.size());
72  const uint32_t score = p.getScore();
73  const uint64_t start = slotCount;
74  slots.emplace_back(start, score, it->peerid);
75  slotCount = start + score;
76  });
77 }
78 
80  auto it = nodes.find(nodeid);
81  if (it == nodes.end()) {
82  return false;
83  }
84 
85  const PeerId peerid = it->peerid;
86  nodes.erase(it);
87 
88  pendingNodes.get<by_nodeid>().erase(nodeid);
89 
90  // Keep the track of the reference count.
91  bool success = removeNodeFromPeer(peers.find(peerid));
92  assert(success);
93 
94  return true;
95 }
96 
97 bool PeerManager::removeNodeFromPeer(const PeerSet::iterator &it,
98  uint32_t count) {
99  // It is possible for nodes to be dangling. If there was an inflight query
100  // when the peer gets removed, the node was not erased. In this case there
101  // is nothing to do.
102  if (it == peers.end()) {
103  return true;
104  }
105 
106  assert(count <= it->node_count);
107  if (count == 0) {
108  // This is a NOOP.
109  return false;
110  }
111 
112  const uint32_t new_count = it->node_count - count;
113  if (!peers.modify(it, [&](Peer &p) { p.node_count = new_count; })) {
114  return false;
115  }
116 
117  if (new_count > 0) {
118  // We are done.
119  return true;
120  }
121 
122  // There are no more node left, we need to cleanup.
123  const size_t i = it->index;
124  assert(i < slots.size());
125  if (i + 1 == slots.size()) {
126  slots.pop_back();
127  slotCount = slots.empty() ? 0 : slots.back().getStop();
128  } else {
129  fragmentation += slots[i].getScore();
130  slots[i] = slots[i].withPeerId(NO_PEER);
131  }
132 
133  return true;
134 }
135 
137  auto it = nodes.find(nodeid);
138  if (it == nodes.end()) {
139  return false;
140  }
141 
142  return nodes.modify(it, [&](Node &n) { n.nextRequestTime = timeout; });
143 }
144 
145 static bool isOrphanState(const ProofValidationState &state) {
148 }
149 
151  if (exists(proof->getId())) {
152  // The proof is already registered, or orphaned.
153  return false;
154  }
155 
156  // Check the proof's validity.
157  ProofValidationState state;
158  // Using WITH_LOCK directly inside the if statement will trigger a cppcheck
159  // false positive syntax error
160  const bool valid = WITH_LOCK(
161  cs_main, return proof->verify(state, ::ChainstateActive().CoinsTip()));
162  if (!valid) {
163  if (isOrphanState(state)) {
164  orphanProofPool.addProof(proof);
165  }
166 
167  // Reject invalid proof.
168  return false;
169  }
170 
171  return createPeer(proof);
172 }
173 
175  for (int retry = 0; retry < SELECT_NODE_MAX_RETRY; retry++) {
176  const PeerId p = selectPeer();
177 
178  // If we cannot find a peer, it may be due to the fact that it is
179  // unlikely due to high fragmentation, so compact and retry.
180  if (p == NO_PEER) {
181  compact();
182  continue;
183  }
184 
185  // See if that peer has an available node.
186  auto &nview = nodes.get<next_request_time>();
187  auto it = nview.lower_bound(boost::make_tuple(p, TimePoint()));
188  if (it != nview.end() && it->peerid == p &&
189  it->nextRequestTime <= std::chrono::steady_clock::now()) {
190  return it->nodeid;
191  }
192  }
193 
194  return NO_NODE;
195 }
196 
198  std::vector<PeerId> invalidPeers;
199  std::vector<ProofRef> newOrphans;
200 
201  {
202  LOCK(cs_main);
203 
204  const CCoinsViewCache &coins = ::ChainstateActive().CoinsTip();
205  for (const auto &p : peers) {
206  ProofValidationState state;
207  if (!p.proof->verify(state, coins)) {
208  if (isOrphanState(state)) {
209  newOrphans.push_back(p.proof);
210  }
211  invalidPeers.push_back(p.peerid);
212  }
213  }
214  }
215 
216  // Remove the invalid peers before the orphans rescan. This makes it
217  // possible to pull back proofs with utxos that conflicted with these
218  // invalid peers.
219  for (const auto &pid : invalidPeers) {
220  removePeer(pid);
221  }
222 
223  orphanProofPool.rescan(*this);
224 
225  for (auto &p : newOrphans) {
227  }
228 }
229 
230 ProofRef PeerManager::getProof(const ProofId &proofid) const {
231  ProofRef proof = nullptr;
232 
233  forPeer(proofid, [&](const Peer &p) {
234  proof = p.proof;
235  return true;
236  });
237 
238  if (!proof) {
239  proof = orphanProofPool.getProof(proofid);
240  }
241 
242  return proof;
243 }
244 
245 bool PeerManager::isBoundToPeer(const ProofId &proofid) const {
246  auto &pview = peers.get<by_proofid>();
247  return pview.find(proofid) != pview.end();
248 }
249 
250 bool PeerManager::isOrphan(const ProofId &proofid) const {
251  return orphanProofPool.getProof(proofid) != nullptr;
252 }
253 
254 bool PeerManager::createPeer(const ProofRef &proof) {
255  assert(proof);
256 
257  switch (validProofPool.addProof(proof)) {
258  case ProofPool::AddProofStatus::REJECTED:
259  // The proof has conflicts, orphan the proof so it can be pulled
260  // back if the conflicting ones are invalidated.
261  orphanProofPool.addProof(proof);
262  return false;
263  case ProofPool::AddProofStatus::DUPLICATED:
264  // If the proof was already in the pool, don't duplicate the peer.
265  return false;
266  case ProofPool::AddProofStatus::SUCCEED:
267  break;
268 
269  // No default case, so the compiler can warn about missing cases
270  }
271 
272  // New peer means new peerid!
273  const PeerId peerid = nextPeerId++;
274 
275  // We have no peer for this proof, time to create it.
276  auto inserted = peers.emplace(peerid, proof);
277  assert(inserted.second);
278 
279  // If there are nodes waiting for this proof, add them
280  auto &pendingNodesView = pendingNodes.get<by_proofid>();
281  auto range = pendingNodesView.equal_range(proof->getId());
282 
283  // We want to update the nodes then remove them from the pending set. That
284  // will invalidate the range iterators, so we need to save the node ids
285  // first before we can loop over them.
286  std::vector<NodeId> nodeids;
287  nodeids.reserve(std::distance(range.first, range.second));
288  std::transform(range.first, range.second, std::back_inserter(nodeids),
289  [](const PendingNode &n) { return n.nodeid; });
290 
291  for (const NodeId &nodeid : nodeids) {
292  addOrUpdateNode(inserted.first, nodeid);
293  }
294 
295  return true;
296 }
297 
298 bool PeerManager::removePeer(const PeerId peerid) {
299  auto it = peers.find(peerid);
300  if (it == peers.end()) {
301  return false;
302  }
303 
304  // Remove all nodes from this peer.
305  removeNodeFromPeer(it, it->node_count);
306 
307  auto &nview = nodes.get<next_request_time>();
308 
309  // Add the nodes to the pending set
310  auto range = nview.equal_range(peerid);
311  for (auto &nit = range.first; nit != range.second; ++nit) {
312  pendingNodes.emplace(it->getProofId(), nit->nodeid);
313  };
314 
315  // Remove nodes associated with this peer, unless their timeout is still
316  // active. This ensure that we don't overquery them in case they are
317  // subsequently added to another peer.
318  nview.erase(nview.lower_bound(boost::make_tuple(peerid, TimePoint())),
319  nview.upper_bound(boost::make_tuple(
320  peerid, std::chrono::steady_clock::now())));
321 
322  // Release UTXOs attached to this proof.
323  validProofPool.removeProof(it->proof);
324 
325  m_unbroadcast_proofids.erase(it->proof->getId());
326 
327  peers.erase(it);
328  return true;
329 }
330 
332  if (slots.empty() || slotCount == 0) {
333  return NO_PEER;
334  }
335 
336  const uint64_t max = slotCount;
337  for (int retry = 0; retry < SELECT_PEER_MAX_RETRY; retry++) {
338  size_t i = selectPeerImpl(slots, GetRand(max), max);
339  if (i != NO_PEER) {
340  return i;
341  }
342  }
343 
344  return NO_PEER;
345 }
346 
348  // There is nothing to compact.
349  if (fragmentation == 0) {
350  return 0;
351  }
352 
353  std::vector<Slot> newslots;
354  newslots.reserve(peers.size());
355 
356  uint64_t prevStop = 0;
357  uint32_t i = 0;
358  for (auto it = peers.begin(); it != peers.end(); it++) {
359  if (it->node_count == 0) {
360  continue;
361  }
362 
363  newslots.emplace_back(prevStop, it->getScore(), it->peerid);
364  prevStop = slots[i].getStop();
365  if (!peers.modify(it, [&](Peer &p) { p.index = i++; })) {
366  return 0;
367  }
368  }
369 
370  slots = std::move(newslots);
371 
372  const uint64_t saved = slotCount - prevStop;
373  slotCount = prevStop;
374  fragmentation = 0;
375 
376  return saved;
377 }
378 
379 bool PeerManager::verify() const {
380  uint64_t prevStop = 0;
381  for (size_t i = 0; i < slots.size(); i++) {
382  const Slot &s = slots[i];
383 
384  // Slots must be in correct order.
385  if (s.getStart() < prevStop) {
386  return false;
387  }
388 
389  prevStop = s.getStop();
390 
391  // If this is a dead slot, then nothing more needs to be checked.
392  if (s.getPeerId() == NO_PEER) {
393  continue;
394  }
395 
396  // We have a live slot, verify index.
397  auto it = peers.find(s.getPeerId());
398  if (it == peers.end() || it->index != i) {
399  return false;
400  }
401  }
402 
403  std::unordered_set<COutPoint, SaltedOutpointHasher> peersUtxos;
404  for (const auto &p : peers) {
405  // A peer should have a proof attached
406  if (!p.proof) {
407  return false;
408  }
409 
410  // Check proof pool consistency
411  for (const auto &ss : p.proof->getStakes()) {
412  const COutPoint &outpoint = ss.getStake().getUTXO();
413  auto proof = validProofPool.getProof(outpoint);
414 
415  if (!proof) {
416  // Missing utxo
417  return false;
418  }
419  if (proof != p.proof) {
420  // Wrong proof
421  return false;
422  }
423 
424  if (!peersUtxos.emplace(outpoint).second) {
425  // Duplicated utxo
426  return false;
427  }
428  }
429 
430  // Count node attached to this peer.
431  const auto count_nodes = [&]() {
432  size_t count = 0;
433  auto &nview = nodes.get<next_request_time>();
434  auto begin =
435  nview.lower_bound(boost::make_tuple(p.peerid, TimePoint()));
436  auto end =
437  nview.upper_bound(boost::make_tuple(p.peerid + 1, TimePoint()));
438 
439  for (auto it = begin; it != end; ++it) {
440  count++;
441  }
442 
443  return count;
444  };
445 
446  if (p.node_count != count_nodes()) {
447  return false;
448  }
449 
450  // If there are no nodes attached to this peer, then we are done.
451  if (p.node_count == 0) {
452  continue;
453  }
454 
455  // The index must point to a slot refering to this peer.
456  if (p.index >= slots.size() || slots[p.index].getPeerId() != p.peerid) {
457  return false;
458  }
459 
460  // If the score do not match, same thing.
461  if (slots[p.index].getScore() != p.getScore()) {
462  return false;
463  }
464  }
465 
466  // We checked the utxo consistency for all our peers utxos already, so if
467  // the pool size differs from the expected one there are dangling utxos.
468  if (validProofPool.size() != peersUtxos.size()) {
469  return false;
470  }
471 
472  return true;
473 }
474 
475 PeerId selectPeerImpl(const std::vector<Slot> &slots, const uint64_t slot,
476  const uint64_t max) {
477  assert(slot <= max);
478 
479  size_t begin = 0, end = slots.size();
480  uint64_t bottom = 0, top = max;
481 
482  // Try to find the slot using dichotomic search.
483  while ((end - begin) > 8) {
484  // The slot we picked in not allocated.
485  if (slot < bottom || slot >= top) {
486  return NO_PEER;
487  }
488 
489  // Guesstimate the position of the slot.
490  size_t i = begin + ((slot - bottom) * (end - begin) / (top - bottom));
491  assert(begin <= i && i < end);
492 
493  // We have a match.
494  if (slots[i].contains(slot)) {
495  return slots[i].getPeerId();
496  }
497 
498  // We undershooted.
499  if (slots[i].precedes(slot)) {
500  begin = i + 1;
501  if (begin >= end) {
502  return NO_PEER;
503  }
504 
505  bottom = slots[begin].getStart();
506  continue;
507  }
508 
509  // We overshooted.
510  if (slots[i].follows(slot)) {
511  end = i;
512  top = slots[end].getStart();
513  continue;
514  }
515 
516  // We have an unalocated slot.
517  return NO_PEER;
518  }
519 
520  // Enough of that nonsense, let fallback to linear search.
521  for (size_t i = begin; i < end; i++) {
522  // We have a match.
523  if (slots[i].contains(slot)) {
524  return slots[i].getPeerId();
525  }
526  }
527 
528  // We failed to find a slot, retry.
529  return NO_PEER;
530 }
531 
533  // The proof should be bound to a peer
534  if (isBoundToPeer(proofid)) {
535  m_unbroadcast_proofids.insert(proofid);
536  }
537 }
538 
540  m_unbroadcast_proofids.erase(proofid);
541 }
542 
543 } // namespace avalanche
avalanche::PeerManager::verify
bool verify() const
Perform consistency check on internal data structures.
Definition: peermanager.cpp:379
avalanche::Slot
Definition: peermanager.h:37
avalanche::PeerManager::SELECT_PEER_MAX_RETRY
static constexpr int SELECT_PEER_MAX_RETRY
Definition: peermanager.h:158
delegation.h
count
static int count
Definition: tests.c:41
avalanche::PeerManager::nodes
NodeSet nodes
Definition: peermanager.h:142
avalanche::PeerManager::updateNextRequestTime
bool updateNextRequestTime(NodeId nodeid, TimePoint timeout)
Definition: peermanager.cpp:136
avalanche::PeerManager::compact
uint64_t compact()
Trigger maintenance of internal data structures.
Definition: peermanager.cpp:347
avalanche::PeerManager::nextPeerId
PeerId nextPeerId
Definition: peermanager.h:124
avalanche
Definition: avalanche.h:11
avalanche::PeerManager::addNode
bool addNode(NodeId nodeid, const ProofId &proofid)
Node API.
Definition: peermanager.cpp:17
avalanche::ProofValidationResult::HEIGHT_MISMATCH
@ HEIGHT_MISMATCH
avalanche::PeerManager::orphanProofPool
ProofPool orphanProofPool
Definition: peermanager.h:128
avalanche::PeerManager::addUnbroadcastProof
void addUnbroadcastProof(const ProofId &proofid)
Proof broadcast API.
Definition: peermanager.cpp:532
avalanche::PeerManager::peers
PeerSet peers
Definition: peermanager.h:125
avalanche::PeerManager::registerProof
bool registerProof(const ProofRef &proof)
Proof and Peer related API.
Definition: peermanager.cpp:150
avalanche::ProofId
Definition: proofid.h:17
avalanche::PeerManager::removeUnbroadcastProof
void removeUnbroadcastProof(const ProofId &proofid)
Definition: peermanager.cpp:539
WITH_LOCK
#define WITH_LOCK(cs, code)
Run code while locking a mutex.
Definition: sync.h:272
ChainstateActive
CChainState & ChainstateActive()
Please prefer the identical ChainstateManager::ActiveChainstate.
Definition: validation.cpp:80
avalanche::ProofPool::size
size_t size() const
Definition: proofpool.h:81
avalanche::Peer
Definition: peermanager.h:69
GetRand
uint64_t GetRand(uint64_t nMax) noexcept
Generate a uniform random integer in the range [0..range).
Definition: random.cpp:650
avalanche::ProofPool::addProof
AddProofStatus addProof(const ProofRef &proof)
Definition: proofpool.cpp:11
avalanche::PeerManager::removeNodeFromPeer
bool removeNodeFromPeer(const PeerSet::iterator &it, uint32_t count=1)
Definition: peermanager.cpp:97
validation.h
avalanche::PeerManager::isOrphan
bool isOrphan(const ProofId &proofid) const
Definition: peermanager.cpp:250
TimePoint
std::chrono::time_point< std::chrono::steady_clock > TimePoint
Definition: node.h:17
avalanche::Node::nextRequestTime
TimePoint nextRequestTime
Definition: node.h:24
avalanche::Slot::getPeerId
PeerId getPeerId() const
Definition: peermanager.h:60
avalanche::PeerManager::updatedBlockTip
void updatedBlockTip()
Update the peer set when a new block is connected.
Definition: peermanager.cpp:197
random.h
avalanche::PeerManager::exists
bool exists(const ProofId &proofid) const
Definition: peermanager.h:198
avalanche::selectPeerImpl
PeerId selectPeerImpl(const std::vector< Slot > &slots, const uint64_t slot, const uint64_t max)
Internal methods that are exposed for testing purposes.
Definition: peermanager.cpp:475
cs_main
RecursiveMutex cs_main
Global state.
Definition: validation.cpp:103
avalanche::PeerManager::removePeer
bool removePeer(const PeerId peerid)
Remove an existing peer.
Definition: peermanager.cpp:298
avalanche::ProofValidationState
Definition: validation.h:33
avalanche::Node
Definition: node.h:21
avalanche::PeerManager::addOrUpdateNode
bool addOrUpdateNode(const PeerSet::iterator &it, NodeId nodeid)
Definition: peermanager.cpp:32
avalanche::Peer::proof
ProofRef proof
Definition: peermanager.h:74
avalanche::PeerManager::SELECT_NODE_MAX_RETRY
static constexpr int SELECT_NODE_MAX_RETRY
Definition: peermanager.h:159
avalanche::PeerManager::removeNode
bool removeNode(NodeId nodeid)
Definition: peermanager.cpp:79
avalanche::PeerManager::validProofPool
ProofPool validProofPool
Definition: peermanager.h:127
avalanche::Peer::node_count
uint32_t node_count
Definition: peermanager.h:72
NO_NODE
static constexpr NodeId NO_NODE
Special NodeId that represent no node.
Definition: nodeid.h:15
ValidationState::GetResult
Result GetResult() const
Definition: validation.h:121
avalanche::PeerManager::fragmentation
uint64_t fragmentation
Definition: peermanager.h:110
avalanche::PendingNode
Definition: peermanager.h:94
avalanche::PeerManager::getProof
ProofRef getProof(const ProofId &proofid) const
Definition: peermanager.cpp:230
avalanche::ProofValidationResult::MISSING_UTXO
@ MISSING_UTXO
avalanche::ProofPool::rescan
void rescan(PeerManager &peerManager)
Definition: proofpool.cpp:58
peermanager.h
avalanche::PeerManager::selectPeer
PeerId selectPeer() const
Randomly select a peer to poll.
Definition: peermanager.cpp:331
avalanche::PeerManager::slots
std::vector< Slot > slots
Definition: peermanager.h:108
avalanche::PeerManager::forPeer
bool forPeer(const ProofId &proofid, Callable &&func) const
Definition: peermanager.h:203
CCoinsViewCache
CCoinsView that adds a memory cache for transactions to another CCoinsView.
Definition: coins.h:231
avalanche::isOrphanState
static bool isOrphanState(const ProofValidationState &state)
Definition: peermanager.cpp:145
avalanche::Peer::index
uint32_t index
Definition: peermanager.h:71
LOCK
#define LOCK(cs)
Definition: sync.h:241
avalanche::PeerManager::addNodeToPeer
bool addNodeToPeer(const PeerSet::iterator &it)
Definition: peermanager.cpp:62
avalanche::PeerManager::m_unbroadcast_proofids
std::unordered_set< ProofId, SaltedProofIdHasher > m_unbroadcast_proofids
Track proof ids to broadcast.
Definition: peermanager.h:164
avalanche::Peer::getScore
uint32_t getScore() const
Definition: peermanager.h:84
avalanche::PeerManager::isBoundToPeer
bool isBoundToPeer(const ProofId &proofid) const
Definition: peermanager.cpp:245
avalanche::ProofPool::removeProof
bool removeProof(ProofRef proof)
Definition: proofpool.cpp:53
avalanche::Slot::getStart
uint64_t getStart() const
Definition: peermanager.h:57
avalanche::PeerManager::createPeer
bool createPeer(const ProofRef &proof)
Definition: peermanager.cpp:254
NodeId
int64_t NodeId
Definition: nodeid.h:10
NO_PEER
static constexpr PeerId NO_PEER
Definition: node.h:15
avalanche::PeerManager::slotCount
uint64_t slotCount
Definition: peermanager.h:109
avalanche::ProofPool::getProof
ProofRef getProof(const ProofId &proofid) const
Definition: proofpool.cpp:67
COutPoint
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:22
avalanche::ProofRef
std::shared_ptr< const Proof > ProofRef
Definition: proof.h:163
avalanche::next_request_time
Definition: peermanager.h:92
CChainState::CoinsTip
CCoinsViewCache & CoinsTip() EXCLUSIVE_LOCKS_REQUIRED(cs_main)
Definition: validation.h:837
avalanche::PeerManager::pendingNodes
PendingNodeSet pendingNodes
Definition: peermanager.h:156
PeerId
uint32_t PeerId
Definition: node.h:14
avalanche::PeerManager::selectNode
NodeId selectNode()
Definition: peermanager.cpp:174
avalanche::Slot::getStop
uint64_t getStop() const
Definition: peermanager.h:58