Changeset View
Changeset View
Standalone View
Standalone View
src/avalanche.cpp
Show All 34 Lines | #else | ||||
* https://www.playingwithpointers.com/blog/swar.html | * https://www.playingwithpointers.com/blog/swar.html | ||||
*/ | */ | ||||
v = v - ((v >> 1) & 0x55555555); | v = v - ((v >> 1) & 0x55555555); | ||||
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); | v = (v & 0x33333333) + ((v >> 2) & 0x33333333); | ||||
return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; | return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; | ||||
#endif | #endif | ||||
} | } | ||||
bool VoteRecord::registerVote(uint32_t error) { | bool VoteRecord::registerVote(NodeId nodeid, uint32_t error) { | ||||
// We just got a new vote, so there is one less inflight request. | // We just got a new vote, so there is one less inflight request. | ||||
clearInflightRequest(); | clearInflightRequest(); | ||||
// Keep track of how many votes were registered. | // We want to avoid having the same node voting twice in a quorum. | ||||
successfulVotes++; | if (!addNodeToQuorum(nodeid)) { | ||||
return false; | |||||
} | |||||
/** | /** | ||||
* The result of the vote is determined from the error code. If the error | * The result of the vote is determined from the error code. If the error | ||||
* code is 0, there is no error and therefore the vote is yes. If there is | * code is 0, there is no error and therefore the vote is yes. If there is | ||||
* an error, we check the most significant bit to decide if the vote is a no | * an error, we check the most significant bit to decide if the vote is a no | ||||
* (for instance, the block is invalid) or is the vote inconclusive (for | * (for instance, the block is invalid) or is the vote inconclusive (for | ||||
* instance, the queried node does not have the block yet). | * instance, the queried node does not have the block yet). | ||||
*/ | */ | ||||
Show All 24 Lines | if (isAccepted() == yes) { | ||||
return getConfidence() == AVALANCHE_FINALIZATION_SCORE; | return getConfidence() == AVALANCHE_FINALIZATION_SCORE; | ||||
} | } | ||||
// The round changed our state. We reset the confidence. | // The round changed our state. We reset the confidence. | ||||
confidence = yes; | confidence = yes; | ||||
return true; | return true; | ||||
} | } | ||||
bool VoteRecord::addNodeToQuorum(NodeId nodeid) { | |||||
if (nodeid == NO_NODE) { | |||||
// Helpful for testing. | |||||
return true; | |||||
} | |||||
// MMIX Linear Congruent Generator. | |||||
const uint64_t r1 = 6364136223846793005 * nodeid + 1442695040888963407; | |||||
// Fibonacci hashing. | |||||
const uint64_t r2 = 11400714819323198485ull * (nodeid ^ seed); | |||||
// Combine and extract hash. | |||||
const uint16_t h = (r1 + r2) >> 48; | |||||
/** | |||||
* Check if the node is in the filter. | |||||
*/ | |||||
for (size_t i = 1; i < nodeFilter.size(); i++) { | |||||
if (nodeFilter[(successfulVotes + i) % nodeFilter.size()] == h) { | |||||
return false; | |||||
} | |||||
} | |||||
/** | |||||
* Add the node which just voted to the filter. | |||||
*/ | |||||
nodeFilter[successfulVotes % nodeFilter.size()] = h; | |||||
successfulVotes++; | |||||
return true; | |||||
} | |||||
bool VoteRecord::registerPoll() const { | bool VoteRecord::registerPoll() const { | ||||
uint8_t count = inflight.load(); | uint8_t count = inflight.load(); | ||||
while (count < AVALANCHE_MAX_INFLIGHT_POLL) { | while (count < AVALANCHE_MAX_INFLIGHT_POLL) { | ||||
if (inflight.compare_exchange_weak(count, count + 1)) { | if (inflight.compare_exchange_weak(count, count + 1)) { | ||||
return true; | return true; | ||||
} | } | ||||
} | } | ||||
▲ Show 20 Lines • Show All 135 Lines • ▼ Show 20 Lines | std::map<CBlockIndex *, AvalancheVote> responseIndex; | ||||
auto it = w->find(pindex); | auto it = w->find(pindex); | ||||
if (it == w.end()) { | if (it == w.end()) { | ||||
// We are not voting on that item anymore. | // We are not voting on that item anymore. | ||||
continue; | continue; | ||||
} | } | ||||
auto &vr = it->second; | auto &vr = it->second; | ||||
if (!vr.registerVote(v.GetError())) { | if (!vr.registerVote(nodeid, v.GetError())) { | ||||
// This vote did not provide any extra information, move on. | // This vote did not provide any extra information, move on. | ||||
continue; | continue; | ||||
} | } | ||||
if (!vr.hasFinalized()) { | if (!vr.hasFinalized()) { | ||||
// This item has note been finalized, so we have nothing more to | // This item has note been finalized, so we have nothing more to | ||||
// do. | // do. | ||||
updates.emplace_back( | updates.emplace_back( | ||||
▲ Show 20 Lines • Show All 230 Lines • Show Last 20 Lines |