diff --git a/src/addrdb.cpp b/src/addrdb.cpp index 5f6ef135b..edbd625c2 100644 --- a/src/addrdb.cpp +++ b/src/addrdb.cpp @@ -1,208 +1,208 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -#include "addrdb.h" - -#include "addrman.h" -#include "chainparams.h" -#include "clientversion.h" -#include "fs.h" -#include "hash.h" -#include "random.h" -#include "streams.h" -#include "tinyformat.h" -#include "util.h" +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include CBanDB::CBanDB(const CChainParams &chainParamsIn) : chainParams(chainParamsIn) { pathBanlist = GetDataDir() / "banlist.dat"; } bool CBanDB::Write(const banmap_t &banSet) { // Generate random temporary filename unsigned short randv = 0; GetRandBytes((uint8_t *)&randv, sizeof(randv)); std::string tmpfn = strprintf("banlist.dat.%04x", randv); // serialize banlist, checksum data up to that point, then append csum CDataStream ssBanlist(SER_DISK, CLIENT_VERSION); ssBanlist << FLATDATA(chainParams.DiskMagic()); ssBanlist << banSet; uint256 hash = Hash(ssBanlist.begin(), ssBanlist.end()); ssBanlist << hash; // open temp output file, and associate with CAutoFile fs::path pathTmp = GetDataDir() / tmpfn; FILE *file = fsbridge::fopen(pathTmp, "wb"); CAutoFile fileout(file, SER_DISK, CLIENT_VERSION); if (fileout.IsNull()) return error("%s: Failed to open file %s", __func__, pathTmp.string()); // Write and commit header, data try { fileout << ssBanlist; } catch (const std::exception &e) { return error("%s: Serialize or I/O error - %s", __func__, e.what()); } FileCommit(fileout.Get()); fileout.fclose(); // replace existing banlist.dat, if any, with new banlist.dat.XXXX if (!RenameOver(pathTmp, pathBanlist)) return error("%s: Rename-into-place failed", __func__); return true; } bool CBanDB::Read(banmap_t &banSet) { // open input file, and associate with CAutoFile FILE *file = fsbridge::fopen(pathBanlist, "rb"); CAutoFile filein(file, SER_DISK, CLIENT_VERSION); if (filein.IsNull()) return error("%s: Failed to open file %s", __func__, pathBanlist.string()); // use file size to size memory buffer uint64_t fileSize = fs::file_size(pathBanlist); uint64_t dataSize = 0; // Don't try to resize to a negative number if file is small if (fileSize >= sizeof(uint256)) dataSize = fileSize - sizeof(uint256); std::vector vchData; vchData.resize(dataSize); uint256 hashIn; // read data and checksum from file try { filein.read((char *)&vchData[0], dataSize); filein >> hashIn; } catch (const std::exception &e) { return error("%s: Deserialize or I/O error - %s", __func__, e.what()); } filein.fclose(); CDataStream ssBanlist(vchData, SER_DISK, CLIENT_VERSION); // verify stored checksum matches input data uint256 hashTmp = Hash(ssBanlist.begin(), ssBanlist.end()); if (hashIn != hashTmp) return error("%s: Checksum mismatch, data corrupted", __func__); uint8_t pchMsgTmp[4]; try { // de-serialize file header (network specific magic number) and .. ssBanlist >> FLATDATA(pchMsgTmp); // ... verify the network matches ours if (memcmp(pchMsgTmp, std::begin(chainParams.DiskMagic()), sizeof(pchMsgTmp))) { return error("%s: Invalid network magic number", __func__); } // de-serialize ban data ssBanlist >> banSet; } catch (const std::exception &e) { return error("%s: Deserialize or I/O error - %s", __func__, e.what()); } return true; } CAddrDB::CAddrDB(const CChainParams &chainParamsIn) : chainParams(chainParamsIn) { pathAddr = GetDataDir() / "peers.dat"; } bool CAddrDB::Write(const CAddrMan &addr) { // Generate random temporary filename unsigned short randv = 0; GetRandBytes((uint8_t *)&randv, sizeof(randv)); std::string tmpfn = strprintf("peers.dat.%04x", randv); // serialize addresses, checksum data up to that point, then append csum CDataStream ssPeers(SER_DISK, CLIENT_VERSION); ssPeers << FLATDATA(chainParams.DiskMagic()); ssPeers << addr; uint256 hash = Hash(ssPeers.begin(), ssPeers.end()); ssPeers << hash; // open temp output file, and associate with CAutoFile fs::path pathTmp = GetDataDir() / tmpfn; FILE *file = fsbridge::fopen(pathTmp, "wb"); CAutoFile fileout(file, SER_DISK, CLIENT_VERSION); if (fileout.IsNull()) return error("%s: Failed to open file %s", __func__, pathTmp.string()); // Write and commit header, data try { fileout << ssPeers; } catch (const std::exception &e) { return error("%s: Serialize or I/O error - %s", __func__, e.what()); } FileCommit(fileout.Get()); fileout.fclose(); // replace existing peers.dat, if any, with new peers.dat.XXXX if (!RenameOver(pathTmp, pathAddr)) return error("%s: Rename-into-place failed", __func__); return true; } bool CAddrDB::Read(CAddrMan &addr) { // open input file, and associate with CAutoFile FILE *file = fsbridge::fopen(pathAddr, "rb"); CAutoFile filein(file, SER_DISK, CLIENT_VERSION); if (filein.IsNull()) return error("%s: Failed to open file %s", __func__, pathAddr.string()); // use file size to size memory buffer uint64_t fileSize = fs::file_size(pathAddr); uint64_t dataSize = 0; // Don't try to resize to a negative number if file is small if (fileSize >= sizeof(uint256)) dataSize = fileSize - sizeof(uint256); std::vector vchData; vchData.resize(dataSize); uint256 hashIn; // read data and checksum from file try { filein.read((char *)&vchData[0], dataSize); filein >> hashIn; } catch (const std::exception &e) { return error("%s: Deserialize or I/O error - %s", __func__, e.what()); } filein.fclose(); CDataStream ssPeers(vchData, SER_DISK, CLIENT_VERSION); // verify stored checksum matches input data uint256 hashTmp = Hash(ssPeers.begin(), ssPeers.end()); if (hashIn != hashTmp) return error("%s: Checksum mismatch, data corrupted", __func__); return Read(addr, ssPeers); } bool CAddrDB::Read(CAddrMan &addr, CDataStream &ssPeers) { uint8_t pchMsgTmp[4]; try { // de-serialize file header (network specific magic number) and .. ssPeers >> FLATDATA(pchMsgTmp); // ... verify the network matches ours if (memcmp(pchMsgTmp, std::begin(chainParams.DiskMagic()), sizeof(pchMsgTmp))) { return error("%s: Invalid network magic number", __func__); } // de-serialize address data into one CAddrMan object ssPeers >> addr; } catch (const std::exception &e) { // de-serialization has failed, ensure addrman is left in a clean state addr.Clear(); return error("%s: Deserialize or I/O error - %s", __func__, e.what()); } return true; } diff --git a/src/addrdb.h b/src/addrdb.h index 5008fa4ff..a13c45490 100644 --- a/src/addrdb.h +++ b/src/addrdb.h @@ -1,97 +1,97 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_ADDRDB_H #define BITCOIN_ADDRDB_H -#include "fs.h" -#include "serialize.h" +#include +#include #include #include class CSubNet; class CAddrMan; class CDataStream; class CChainParams; typedef enum BanReason { BanReasonUnknown = 0, BanReasonNodeMisbehaving = 1, BanReasonManuallyAdded = 2 } BanReason; class CBanEntry { public: static const int CURRENT_VERSION = 1; int nVersion; int64_t nCreateTime; int64_t nBanUntil; uint8_t banReason; CBanEntry() { SetNull(); } explicit CBanEntry(int64_t nCreateTimeIn) { SetNull(); nCreateTime = nCreateTimeIn; } ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(this->nVersion); READWRITE(nCreateTime); READWRITE(nBanUntil); READWRITE(banReason); } void SetNull() { nVersion = CBanEntry::CURRENT_VERSION; nCreateTime = 0; nBanUntil = 0; banReason = BanReasonUnknown; } std::string banReasonToString() const { switch (banReason) { case BanReasonNodeMisbehaving: return "node misbehaving"; case BanReasonManuallyAdded: return "manually added"; default: return "unknown"; } } }; typedef std::map banmap_t; /** Access to the (IP) address database (peers.dat) */ class CAddrDB { private: fs::path pathAddr; const CChainParams &chainParams; public: CAddrDB(const CChainParams &chainParams); bool Write(const CAddrMan &addr); bool Read(CAddrMan &addr); bool Read(CAddrMan &addr, CDataStream &ssPeers); }; /** Access to the banlist database (banlist.dat) */ class CBanDB { private: fs::path pathBanlist; const CChainParams &chainParams; public: CBanDB(const CChainParams &chainParams); bool Write(const banmap_t &banSet); bool Read(banmap_t &banSet); }; #endif // BITCOIN_ADDRDB_H diff --git a/src/addrman.cpp b/src/addrman.cpp index 6dcb37f85..74f7d17e9 100644 --- a/src/addrman.cpp +++ b/src/addrman.cpp @@ -1,719 +1,719 @@ // Copyright (c) 2012 Pieter Wuille // Copyright (c) 2012-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -#include "addrman.h" +#include -#include "hash.h" -#include "serialize.h" -#include "streams.h" +#include +#include +#include #include int CAddrInfo::GetTriedBucket(const uint256 &nKey) const { uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << GetKey()) .GetHash() .GetCheapHash(); uint64_t hash2 = (CHashWriter(SER_GETHASH, 0) << nKey << GetGroup() << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP)) .GetHash() .GetCheapHash(); return hash2 % ADDRMAN_TRIED_BUCKET_COUNT; } int CAddrInfo::GetNewBucket(const uint256 &nKey, const CNetAddr &src) const { std::vector vchSourceGroupKey = src.GetGroup(); uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << GetGroup() << vchSourceGroupKey) .GetHash() .GetCheapHash(); uint64_t hash2 = (CHashWriter(SER_GETHASH, 0) << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP)) .GetHash() .GetCheapHash(); return hash2 % ADDRMAN_NEW_BUCKET_COUNT; } int CAddrInfo::GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const { uint64_t hash1 = (CHashWriter(SER_GETHASH, 0) << nKey << (fNew ? 'N' : 'K') << nBucket << GetKey()) .GetHash() .GetCheapHash(); return hash1 % ADDRMAN_BUCKET_SIZE; } bool CAddrInfo::IsTerrible(int64_t nNow) const { // never remove things tried in the last minute if (nLastTry && nLastTry >= nNow - 60) { return false; } // came in a flying DeLorean if (nTime > nNow + 10 * 60) { return true; } // not seen in recent history if (nTime == 0 || nNow - nTime > ADDRMAN_HORIZON_DAYS * 24 * 60 * 60) { return true; } // tried N times and never a success if (nLastSuccess == 0 && nAttempts >= ADDRMAN_RETRIES) { return true; } if (nNow - nLastSuccess > ADDRMAN_MIN_FAIL_DAYS * 24 * 60 * 60 && nAttempts >= ADDRMAN_MAX_FAILURES) { // N successive failures in the last week return true; } return false; } double CAddrInfo::GetChance(int64_t nNow) const { double fChance = 1.0; int64_t nSinceLastTry = std::max(nNow - nLastTry, 0); // deprioritize very recent attempts away if (nSinceLastTry < 60 * 10) { fChance *= 0.01; } // deprioritize 66% after each failed attempt, but at most 1/28th to avoid // the search taking forever or overly penalizing outages. fChance *= std::pow(0.66, std::min(nAttempts, 8)); return fChance; } CAddrInfo *CAddrMan::Find(const CNetAddr &addr, int *pnId) { std::map::iterator it = mapAddr.find(addr); if (it == mapAddr.end()) { return nullptr; } if (pnId) { *pnId = (*it).second; } std::map::iterator it2 = mapInfo.find((*it).second); if (it2 != mapInfo.end()) { return &(*it2).second; } return nullptr; } CAddrInfo *CAddrMan::Create(const CAddress &addr, const CNetAddr &addrSource, int *pnId) { int nId = nIdCount++; mapInfo[nId] = CAddrInfo(addr, addrSource); mapAddr[addr] = nId; mapInfo[nId].nRandomPos = vRandom.size(); vRandom.push_back(nId); if (pnId) { *pnId = nId; } return &mapInfo[nId]; } void CAddrMan::SwapRandom(unsigned int nRndPos1, unsigned int nRndPos2) { if (nRndPos1 == nRndPos2) { return; } assert(nRndPos1 < vRandom.size() && nRndPos2 < vRandom.size()); int nId1 = vRandom[nRndPos1]; int nId2 = vRandom[nRndPos2]; assert(mapInfo.count(nId1) == 1); assert(mapInfo.count(nId2) == 1); mapInfo[nId1].nRandomPos = nRndPos2; mapInfo[nId2].nRandomPos = nRndPos1; vRandom[nRndPos1] = nId2; vRandom[nRndPos2] = nId1; } void CAddrMan::Delete(int nId) { assert(mapInfo.count(nId) != 0); CAddrInfo &info = mapInfo[nId]; assert(!info.fInTried); assert(info.nRefCount == 0); SwapRandom(info.nRandomPos, vRandom.size() - 1); vRandom.pop_back(); mapAddr.erase(info); mapInfo.erase(nId); nNew--; } void CAddrMan::ClearNew(int nUBucket, int nUBucketPos) { // if there is an entry in the specified bucket, delete it. if (vvNew[nUBucket][nUBucketPos] != -1) { int nIdDelete = vvNew[nUBucket][nUBucketPos]; CAddrInfo &infoDelete = mapInfo[nIdDelete]; assert(infoDelete.nRefCount > 0); infoDelete.nRefCount--; vvNew[nUBucket][nUBucketPos] = -1; if (infoDelete.nRefCount == 0) { Delete(nIdDelete); } } } void CAddrMan::MakeTried(CAddrInfo &info, int nId) { // remove the entry from all new buckets for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) { int pos = info.GetBucketPosition(nKey, true, bucket); if (vvNew[bucket][pos] == nId) { vvNew[bucket][pos] = -1; info.nRefCount--; } } nNew--; assert(info.nRefCount == 0); // which tried bucket to move the entry to int nKBucket = info.GetTriedBucket(nKey); int nKBucketPos = info.GetBucketPosition(nKey, false, nKBucket); // first make space to add it (the existing tried entry there is moved to // new, deleting whatever is there). if (vvTried[nKBucket][nKBucketPos] != -1) { // find an item to evict int nIdEvict = vvTried[nKBucket][nKBucketPos]; assert(mapInfo.count(nIdEvict) == 1); CAddrInfo &infoOld = mapInfo[nIdEvict]; // Remove the to-be-evicted item from the tried set. infoOld.fInTried = false; vvTried[nKBucket][nKBucketPos] = -1; nTried--; // find which new bucket it belongs to int nUBucket = infoOld.GetNewBucket(nKey); int nUBucketPos = infoOld.GetBucketPosition(nKey, true, nUBucket); ClearNew(nUBucket, nUBucketPos); assert(vvNew[nUBucket][nUBucketPos] == -1); // Enter it into the new set again. infoOld.nRefCount = 1; vvNew[nUBucket][nUBucketPos] = nIdEvict; nNew++; } assert(vvTried[nKBucket][nKBucketPos] == -1); vvTried[nKBucket][nKBucketPos] = nId; nTried++; info.fInTried = true; } void CAddrMan::Good_(const CService &addr, bool test_before_evict, int64_t nTime) { int nId; nLastGood = nTime; CAddrInfo *pinfo = Find(addr, &nId); // if not found, bail out if (!pinfo) { return; } CAddrInfo &info = *pinfo; // check whether we are talking about the exact same CService (including // same port) if (info != addr) { return; } // update info info.nLastSuccess = nTime; info.nLastTry = nTime; info.nAttempts = 0; // nTime is not updated here, to avoid leaking information about // currently-connected peers. // if it is already in the tried set, don't do anything else if (info.fInTried) { return; } // find a bucket it is in now int nRnd = RandomInt(ADDRMAN_NEW_BUCKET_COUNT); int nUBucket = -1; for (unsigned int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) { int nB = (n + nRnd) % ADDRMAN_NEW_BUCKET_COUNT; int nBpos = info.GetBucketPosition(nKey, true, nB); if (vvNew[nB][nBpos] == nId) { nUBucket = nB; break; } } // if no bucket is found, something bad happened; // TODO: maybe re-add the node, but for now, just bail out if (nUBucket == -1) { return; } // which tried bucket to move the entry to int tried_bucket = info.GetTriedBucket(nKey); int tried_bucket_pos = info.GetBucketPosition(nKey, false, tried_bucket); // Will moving this address into tried evict another entry? if (test_before_evict && (vvTried[tried_bucket][tried_bucket_pos] != -1)) { LogPrint(BCLog::ADDRMAN, "Collision inserting element into tried table, moving %s to " "m_tried_collisions=%d\n", addr.ToString(), m_tried_collisions.size()); if (m_tried_collisions.size() < ADDRMAN_SET_TRIED_COLLISION_SIZE) { m_tried_collisions.insert(nId); } } else { LogPrint(BCLog::ADDRMAN, "Moving %s to tried\n", addr.ToString()); // move nId to the tried tables MakeTried(info, nId); } } bool CAddrMan::Add_(const CAddress &addr, const CNetAddr &source, int64_t nTimePenalty) { if (!addr.IsRoutable()) { return false; } bool fNew = false; int nId; CAddrInfo *pinfo = Find(addr, &nId); // Do not set a penalty for a source's self-announcement if (addr == source) { nTimePenalty = 0; } if (pinfo) { // periodically update nTime bool fCurrentlyOnline = (GetAdjustedTime() - addr.nTime < 24 * 60 * 60); int64_t nUpdateInterval = (fCurrentlyOnline ? 60 * 60 : 24 * 60 * 60); if (addr.nTime && (!pinfo->nTime || pinfo->nTime < addr.nTime - nUpdateInterval - nTimePenalty)) { pinfo->nTime = std::max((int64_t)0, addr.nTime - nTimePenalty); } // add services pinfo->nServices = ServiceFlags(pinfo->nServices | addr.nServices); // do not update if no new information is present if (!addr.nTime || (pinfo->nTime && addr.nTime <= pinfo->nTime)) { return false; } // do not update if the entry was already in the "tried" table if (pinfo->fInTried) { return false; } // do not update if the max reference count is reached if (pinfo->nRefCount == ADDRMAN_NEW_BUCKETS_PER_ADDRESS) { return false; } // stochastic test: previous nRefCount == N: 2^N times harder to // increase it int nFactor = 1; for (int n = 0; n < pinfo->nRefCount; n++) { nFactor *= 2; } if (nFactor > 1 && (RandomInt(nFactor) != 0)) { return false; } } else { pinfo = Create(addr, source, &nId); pinfo->nTime = std::max((int64_t)0, (int64_t)pinfo->nTime - nTimePenalty); nNew++; fNew = true; } int nUBucket = pinfo->GetNewBucket(nKey, source); int nUBucketPos = pinfo->GetBucketPosition(nKey, true, nUBucket); if (vvNew[nUBucket][nUBucketPos] != nId) { bool fInsert = vvNew[nUBucket][nUBucketPos] == -1; if (!fInsert) { CAddrInfo &infoExisting = mapInfo[vvNew[nUBucket][nUBucketPos]]; if (infoExisting.IsTerrible() || (infoExisting.nRefCount > 1 && pinfo->nRefCount == 0)) { // Overwrite the existing new table entry. fInsert = true; } } if (fInsert) { ClearNew(nUBucket, nUBucketPos); pinfo->nRefCount++; vvNew[nUBucket][nUBucketPos] = nId; } else if (pinfo->nRefCount == 0) { Delete(nId); } } return fNew; } void CAddrMan::Attempt_(const CService &addr, bool fCountFailure, int64_t nTime) { CAddrInfo *pinfo = Find(addr); // if not found, bail out if (!pinfo) { return; } CAddrInfo &info = *pinfo; // check whether we are talking about the exact same CService (including // same port) if (info != addr) { return; } // update info info.nLastTry = nTime; if (fCountFailure && info.nLastCountAttempt < nLastGood) { info.nLastCountAttempt = nTime; info.nAttempts++; } } CAddrInfo CAddrMan::Select_(bool newOnly) { if (size() == 0) { return CAddrInfo(); } if (newOnly && nNew == 0) { return CAddrInfo(); } // Use a 50% chance for choosing between tried and new table entries. if (!newOnly && (nTried > 0 && (nNew == 0 || RandomInt(2) == 0))) { // use a tried node double fChanceFactor = 1.0; while (1) { int nKBucket = RandomInt(ADDRMAN_TRIED_BUCKET_COUNT); int nKBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE); while (vvTried[nKBucket][nKBucketPos] == -1) { nKBucket = (nKBucket + insecure_rand.randbits( ADDRMAN_TRIED_BUCKET_COUNT_LOG2)) % ADDRMAN_TRIED_BUCKET_COUNT; nKBucketPos = (nKBucketPos + insecure_rand.randbits( ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE; } int nId = vvTried[nKBucket][nKBucketPos]; assert(mapInfo.count(nId) == 1); CAddrInfo &info = mapInfo[nId]; if (RandomInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30)) { return info; } fChanceFactor *= 1.2; } } else { // use a new node double fChanceFactor = 1.0; while (1) { int nUBucket = RandomInt(ADDRMAN_NEW_BUCKET_COUNT); int nUBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE); while (vvNew[nUBucket][nUBucketPos] == -1) { nUBucket = (nUBucket + insecure_rand.randbits( ADDRMAN_NEW_BUCKET_COUNT_LOG2)) % ADDRMAN_NEW_BUCKET_COUNT; nUBucketPos = (nUBucketPos + insecure_rand.randbits( ADDRMAN_BUCKET_SIZE_LOG2)) % ADDRMAN_BUCKET_SIZE; } int nId = vvNew[nUBucket][nUBucketPos]; assert(mapInfo.count(nId) == 1); CAddrInfo &info = mapInfo[nId]; if (RandomInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30)) { return info; } fChanceFactor *= 1.2; } } } #ifdef DEBUG_ADDRMAN int CAddrMan::Check_() { std::set setTried; std::map mapNew; if (vRandom.size() != nTried + nNew) { return -7; } for (const auto &entry : mapInfo) { int n = entry.first; const CAddrInfo &info = entry.second; if (info.fInTried) { if (!info.nLastSuccess) { return -1; } if (info.nRefCount) { return -2; } setTried.insert(n); } else { if (info.nRefCount < 0 || info.nRefCount > ADDRMAN_NEW_BUCKETS_PER_ADDRESS) { return -3; } if (!info.nRefCount) { return -4; } mapNew[n] = info.nRefCount; } if (mapAddr[info] != n) { return -5; } if (info.nRandomPos < 0 || info.nRandomPos >= vRandom.size() || vRandom[info.nRandomPos] != n) { return -14; } if (info.nLastTry < 0) { return -6; } if (info.nLastSuccess < 0) { return -8; } } if (setTried.size() != nTried) { return -9; } if (mapNew.size() != nNew) { return -10; } for (int n = 0; n < ADDRMAN_TRIED_BUCKET_COUNT; n++) { for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) { if (vvTried[n][i] != -1) { if (!setTried.count(vvTried[n][i])) { return -11; } if (mapInfo[vvTried[n][i]].GetTriedBucket(nKey) != n) { return -17; } if (mapInfo[vvTried[n][i]].GetBucketPosition(nKey, false, n) != i) { return -18; } setTried.erase(vvTried[n][i]); } } } for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) { for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) { if (vvNew[n][i] != -1) { if (!mapNew.count(vvNew[n][i])) { return -12; } if (mapInfo[vvNew[n][i]].GetBucketPosition(nKey, true, n) != i) { return -19; } if (--mapNew[vvNew[n][i]] == 0) { mapNew.erase(vvNew[n][i]); } } } } if (setTried.size()) { return -13; } if (mapNew.size()) { return -15; } if (nKey.IsNull()) { return -16; } return 0; } #endif void CAddrMan::GetAddr_(std::vector &vAddr) { unsigned int nNodes = ADDRMAN_GETADDR_MAX_PCT * vRandom.size() / 100; if (nNodes > ADDRMAN_GETADDR_MAX) nNodes = ADDRMAN_GETADDR_MAX; // gather a list of random nodes, skipping those of low quality for (unsigned int n = 0; n < vRandom.size(); n++) { if (vAddr.size() >= nNodes) { break; } int nRndPos = RandomInt(vRandom.size() - n) + n; SwapRandom(n, nRndPos); assert(mapInfo.count(vRandom[n]) == 1); const CAddrInfo &ai = mapInfo[vRandom[n]]; if (!ai.IsTerrible()) { vAddr.push_back(ai); } } } void CAddrMan::Connected_(const CService &addr, int64_t nTime) { CAddrInfo *pinfo = Find(addr); // if not found, bail out if (!pinfo) { return; } CAddrInfo &info = *pinfo; // check whether we are talking about the exact same CService (including // same port) if (info != addr) { return; } // update info int64_t nUpdateInterval = 20 * 60; if (nTime - info.nTime > nUpdateInterval) { info.nTime = nTime; } } void CAddrMan::SetServices_(const CService &addr, ServiceFlags nServices) { CAddrInfo *pinfo = Find(addr); // if not found, bail out if (!pinfo) { return; } CAddrInfo &info = *pinfo; // check whether we are talking about the exact same CService (including // same port) if (info != addr) { return; } // update info info.nServices = nServices; } int CAddrMan::RandomInt(int nMax) { return GetRandInt(nMax); } void CAddrMan::ResolveCollisions_() { const int64_t adjustedTime = GetAdjustedTime(); for (std::set::iterator it = m_tried_collisions.begin(); it != m_tried_collisions.end();) { int id_new = *it; bool erase_collision = false; // If id_new not found in mapInfo remove it from m_tried_collisions. auto id_new_it = mapInfo.find(id_new); if (id_new_it == mapInfo.end()) { erase_collision = true; } else { CAddrInfo &info_new = id_new_it->second; // Which tried bucket to move the entry to. int tried_bucket = info_new.GetTriedBucket(nKey); int tried_bucket_pos = info_new.GetBucketPosition(nKey, false, tried_bucket); if (!info_new.IsValid()) { // id_new may no longer map to a valid address erase_collision = true; } else if (vvTried[tried_bucket][tried_bucket_pos] != -1) { // The position in the tried bucket is not empty // Get the to-be-evicted address that is being tested int id_old = vvTried[tried_bucket][tried_bucket_pos]; CAddrInfo &info_old = mapInfo[id_old]; // Has successfully connected in last X hours if (adjustedTime - info_old.nLastSuccess < ADDRMAN_REPLACEMENT_SECONDS) { erase_collision = true; } else if (adjustedTime - info_old.nLastTry < ADDRMAN_REPLACEMENT_SECONDS) { // attempted to connect and failed in last X hours // Give address at least 60 seconds to successfully connect if (GetAdjustedTime() - info_old.nLastTry > 60) { LogPrint(BCLog::ADDRMAN, "Swapping %s for %s in tried table\n", info_new.ToString(), info_old.ToString()); // Replaces an existing address already in the tried // table with the new address Good_(info_new, false, GetAdjustedTime()); erase_collision = true; } } } else { // Collision is not actually a collision anymore Good_(info_new, false, adjustedTime); erase_collision = true; } } if (erase_collision) { m_tried_collisions.erase(it++); } else { it++; } } } CAddrInfo CAddrMan::SelectTriedCollision_() { if (m_tried_collisions.size() == 0) { return CAddrInfo(); } std::set::iterator it = m_tried_collisions.begin(); // Selects a random element from m_tried_collisions. std::advance(it, GetRandInt(m_tried_collisions.size())); int id_new = *it; // If id_new not found in mapInfo remove it from m_tried_collisions. auto id_new_it = mapInfo.find(id_new); if (id_new_it == mapInfo.end()) { m_tried_collisions.erase(it); return CAddrInfo(); } CAddrInfo &newInfo = id_new_it->second; // which tried bucket to move the entry to int tried_bucket = newInfo.GetTriedBucket(nKey); int tried_bucket_pos = newInfo.GetBucketPosition(nKey, false, tried_bucket); int id_old = vvTried[tried_bucket][tried_bucket_pos]; return mapInfo[id_old]; } diff --git a/src/addrman.h b/src/addrman.h index e22b9a4ab..f37afc0a9 100644 --- a/src/addrman.h +++ b/src/addrman.h @@ -1,661 +1,661 @@ // Copyright (c) 2012 Pieter Wuille // Copyright (c) 2012-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_ADDRMAN_H #define BITCOIN_ADDRMAN_H -#include "netaddress.h" -#include "protocol.h" -#include "random.h" -#include "sync.h" -#include "timedata.h" -#include "util.h" +#include +#include +#include +#include +#include +#include #include #include #include #include /** * Extended statistics about a CAddress */ class CAddrInfo : public CAddress { public: //! last try whatsoever by us (memory only) int64_t nLastTry; //! last counted attempt (memory only) int64_t nLastCountAttempt; private: //! where knowledge about this address first came from CNetAddr source; //! last successful connection by us int64_t nLastSuccess; //! connection attempts since last successful attempt int nAttempts; //! reference count in new sets (memory only) int nRefCount; //! in tried set? (memory only) bool fInTried; //! position in vRandom int nRandomPos; friend class CAddrMan; public: ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(*static_cast(this)); READWRITE(source); READWRITE(nLastSuccess); READWRITE(nAttempts); } void Init() { nLastSuccess = 0; nLastTry = 0; nLastCountAttempt = 0; nAttempts = 0; nRefCount = 0; fInTried = false; nRandomPos = -1; } CAddrInfo(const CAddress &addrIn, const CNetAddr &addrSource) : CAddress(addrIn), source(addrSource) { Init(); } CAddrInfo() : CAddress(), source() { Init(); } //! Calculate in which "tried" bucket this entry belongs int GetTriedBucket(const uint256 &nKey) const; //! Calculate in which "new" bucket this entry belongs, given a certain //! source int GetNewBucket(const uint256 &nKey, const CNetAddr &src) const; //! Calculate in which "new" bucket this entry belongs, using its default //! source int GetNewBucket(const uint256 &nKey) const { return GetNewBucket(nKey, source); } //! Calculate in which position of a bucket to store this entry. int GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const; //! Determine whether the statistics about this entry are bad enough so that //! it can just be deleted bool IsTerrible(int64_t nNow = GetAdjustedTime()) const; //! Calculate the relative chance this entry should be given when selecting //! nodes to connect to double GetChance(int64_t nNow = GetAdjustedTime()) const; }; /** Stochastic address manager * * Design goals: * * Keep the address tables in-memory, and asynchronously dump the entire * table to peers.dat. * * Make sure no (localized) attacker can fill the entire table with his * nodes/addresses. * * To that end: * * Addresses are organized into buckets. * * Addresses that have not yet been tried go into 1024 "new" buckets. * * Based on the address range (/16 for IPv4) of the source of * information, 64 buckets are selected at random. * * The actual bucket is chosen from one of these, based on the range in * which the address itself is located. * * One single address can occur in up to 8 different buckets to increase * selection chances for addresses that * are seen frequently. The chance for increasing this multiplicity * decreases exponentially. * * When adding a new address to a full bucket, a randomly chosen entry * (with a bias favoring less recently seen * ones) is removed from it first. * * Addresses of nodes that are known to be accessible go into 256 "tried" * buckets. * * Each address range selects at random 8 of these buckets. * * The actual bucket is chosen from one of these, based on the full * address. * * When adding a new good address to a full bucket, a randomly chosen * entry (with a bias favoring less recently * tried ones) is evicted from it, back to the "new" buckets. * * Bucket selection is based on cryptographic hashing, using a * randomly-generated 256-bit key, which should not * be observable by adversaries. * * Several indexes are kept for high performance. Defining DEBUG_ADDRMAN * will introduce frequent (and expensive) * consistency checks for the entire data structure. */ //! total number of buckets for tried addresses #define ADDRMAN_TRIED_BUCKET_COUNT_LOG2 8 //! total number of buckets for new addresses #define ADDRMAN_NEW_BUCKET_COUNT_LOG2 10 //! maximum allowed number of entries in buckets for new and tried addresses #define ADDRMAN_BUCKET_SIZE_LOG2 6 //! over how many buckets entries with tried addresses from a single group (/16 //! for IPv4) are spread #define ADDRMAN_TRIED_BUCKETS_PER_GROUP 8 //! over how many buckets entries with new addresses originating from a single //! group are spread #define ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP 64 //! in how many buckets for entries with new addresses a single address may //! occur #define ADDRMAN_NEW_BUCKETS_PER_ADDRESS 8 //! how old addresses can maximally be #define ADDRMAN_HORIZON_DAYS 30 //! after how many failed attempts we give up on a new node #define ADDRMAN_RETRIES 3 //! how many successive failures are allowed ... #define ADDRMAN_MAX_FAILURES 10 //! ... in at least this many days #define ADDRMAN_MIN_FAIL_DAYS 7 //! how recent a successful connection should be before we allow an address to //! be evicted from tried #define ADDRMAN_REPLACEMENT_SECONDS (4 * 60 * 60) //! the maximum percentage of nodes to return in a getaddr call #define ADDRMAN_GETADDR_MAX_PCT 23 //! the maximum number of nodes to return in a getaddr call #define ADDRMAN_GETADDR_MAX 2500 //! Convenience #define ADDRMAN_TRIED_BUCKET_COUNT (1 << ADDRMAN_TRIED_BUCKET_COUNT_LOG2) #define ADDRMAN_NEW_BUCKET_COUNT (1 << ADDRMAN_NEW_BUCKET_COUNT_LOG2) #define ADDRMAN_BUCKET_SIZE (1 << ADDRMAN_BUCKET_SIZE_LOG2) //! the maximum number of tried addr collisions to store #define ADDRMAN_SET_TRIED_COLLISION_SIZE 10 /** * Stochastical (IP) address manager */ class CAddrMan { private: //! critical section to protect the inner data structures mutable CCriticalSection cs; //! last used nId int nIdCount; //! table with information about all nIds std::map mapInfo; //! find an nId based on its network address std::map mapAddr; //! randomly-ordered vector of all nIds std::vector vRandom; // number of "tried" entries int nTried; //! list of "tried" buckets int vvTried[ADDRMAN_TRIED_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE]; //! number of (unique) "new" entries int nNew; //! list of "new" buckets int vvNew[ADDRMAN_NEW_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE]; //! last time Good was called (memory only) int64_t nLastGood; //! Holds addrs inserted into tried table that collide with existing //! entries. Test-before-evict discpline used to resolve these collisions. std::set m_tried_collisions; protected: //! secret key to randomize bucket select with uint256 nKey; //! Source of random numbers for randomization in inner loops FastRandomContext insecure_rand; //! Find an entry. CAddrInfo *Find(const CNetAddr &addr, int *pnId = nullptr); //! find an entry, creating it if necessary. //! nTime and nServices of the found node are updated, if necessary. CAddrInfo *Create(const CAddress &addr, const CNetAddr &addrSource, int *pnId = nullptr); //! Swap two elements in vRandom. void SwapRandom(unsigned int nRandomPos1, unsigned int nRandomPos2); //! Move an entry from the "new" table(s) to the "tried" table void MakeTried(CAddrInfo &info, int nId); //! Delete an entry. It must not be in tried, and have refcount 0. void Delete(int nId); //! Clear a position in a "new" table. This is the only place where entries //! are actually deleted. void ClearNew(int nUBucket, int nUBucketPos); //! Mark an entry "good", possibly moving it from "new" to "tried". void Good_(const CService &addr, bool test_before_evict, int64_t time); //! Add an entry to the "new" table. bool Add_(const CAddress &addr, const CNetAddr &source, int64_t nTimePenalty); //! Mark an entry as attempted to connect. void Attempt_(const CService &addr, bool fCountFailure, int64_t nTime); //! Select an address to connect to, if newOnly is set to true, only the new //! table is selected from. CAddrInfo Select_(bool newOnly); //! See if any to-be-evicted tried table entries have been tested and if so //! resolve the collisions. void ResolveCollisions_(); //! Return a random to-be-evicted tried table address. CAddrInfo SelectTriedCollision_(); //! Wraps GetRandInt to allow tests to override RandomInt and make it //! determinismistic. virtual int RandomInt(int nMax); #ifdef DEBUG_ADDRMAN //! Perform consistency check. Returns an error code or zero. int Check_(); #endif //! Select several addresses at once. void GetAddr_(std::vector &vAddr); //! Mark an entry as currently-connected-to. void Connected_(const CService &addr, int64_t nTime); //! Update an entry's service bits. void SetServices_(const CService &addr, ServiceFlags nServices); public: /** * serialized format: * * version byte (currently 1) * * 0x20 + nKey (serialized as if it were a vector, for backward * compatibility) * * nNew * * nTried * * number of "new" buckets XOR 2**30 * * all nNew addrinfos in vvNew * * all nTried addrinfos in vvTried * * for each bucket: * * number of elements * * for each element: index * * 2**30 is xorred with the number of buckets to make addrman deserializer * v0 detect it as incompatible. This is necessary because it did not check * the version number on deserialization. * * Notice that vvTried, mapAddr and vVector are never encoded explicitly; * they are instead reconstructed from the other information. * * vvNew is serialized, but only used if ADDRMAN_UNKNOWN_BUCKET_COUNT didn't * change, otherwise it is reconstructed as well. * * This format is more complex, but significantly smaller (at most 1.5 MiB), * and supports changes to the ADDRMAN_ parameters without breaking the * on-disk structure. * * We don't use ADD_SERIALIZE_METHODS since the serialization and * deserialization code has very little in common. */ template void Serialize(Stream &s) const { LOCK(cs); uint8_t nVersion = 1; s << nVersion; s << uint8_t(32); s << nKey; s << nNew; s << nTried; int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT ^ (1 << 30); s << nUBuckets; std::map mapUnkIds; int nIds = 0; for (const auto &entry : mapInfo) { mapUnkIds[entry.first] = nIds; const CAddrInfo &info = entry.second; if (info.nRefCount) { // this means nNew was wrong, oh ow assert(nIds != nNew); s << info; nIds++; } } nIds = 0; for (const auto &entry : mapInfo) { const CAddrInfo &info = entry.second; if (info.fInTried) { // this means nTried was wrong, oh ow assert(nIds != nTried); s << info; nIds++; } } for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) { int nSize = 0; for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) { if (vvNew[bucket][i] != -1) nSize++; } s << nSize; for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) { if (vvNew[bucket][i] != -1) { int nIndex = mapUnkIds[vvNew[bucket][i]]; s << nIndex; } } } } template void Unserialize(Stream &s) { LOCK(cs); Clear(); uint8_t nVersion; s >> nVersion; uint8_t nKeySize; s >> nKeySize; if (nKeySize != 32) { throw std::ios_base::failure( "Incorrect keysize in addrman deserialization"); } s >> nKey; s >> nNew; s >> nTried; int nUBuckets = 0; s >> nUBuckets; if (nVersion != 0) { nUBuckets ^= (1 << 30); } if (nNew > ADDRMAN_NEW_BUCKET_COUNT * ADDRMAN_BUCKET_SIZE) { throw std::ios_base::failure( "Corrupt CAddrMan serialization, nNew exceeds limit."); } if (nTried > ADDRMAN_TRIED_BUCKET_COUNT * ADDRMAN_BUCKET_SIZE) { throw std::ios_base::failure( "Corrupt CAddrMan serialization, nTried exceeds limit."); } // Deserialize entries from the new table. for (int n = 0; n < nNew; n++) { CAddrInfo &info = mapInfo[n]; s >> info; mapAddr[info] = n; info.nRandomPos = vRandom.size(); vRandom.push_back(n); if (nVersion != 1 || nUBuckets != ADDRMAN_NEW_BUCKET_COUNT) { // In case the new table data cannot be used (nVersion unknown, // or bucket count wrong), immediately try to give them a // reference based on their primary source address. int nUBucket = info.GetNewBucket(nKey); int nUBucketPos = info.GetBucketPosition(nKey, true, nUBucket); if (vvNew[nUBucket][nUBucketPos] == -1) { vvNew[nUBucket][nUBucketPos] = n; info.nRefCount++; } } } nIdCount = nNew; // Deserialize entries from the tried table. int nLost = 0; for (int n = 0; n < nTried; n++) { CAddrInfo info; s >> info; int nKBucket = info.GetTriedBucket(nKey); int nKBucketPos = info.GetBucketPosition(nKey, false, nKBucket); if (vvTried[nKBucket][nKBucketPos] == -1) { info.nRandomPos = vRandom.size(); info.fInTried = true; vRandom.push_back(nIdCount); mapInfo[nIdCount] = info; mapAddr[info] = nIdCount; vvTried[nKBucket][nKBucketPos] = nIdCount; nIdCount++; } else { nLost++; } } nTried -= nLost; // Deserialize positions in the new table (if possible). for (int bucket = 0; bucket < nUBuckets; bucket++) { int nSize = 0; s >> nSize; for (int n = 0; n < nSize; n++) { int nIndex = 0; s >> nIndex; if (nIndex >= 0 && nIndex < nNew) { CAddrInfo &info = mapInfo[nIndex]; int nUBucketPos = info.GetBucketPosition(nKey, true, bucket); if (nVersion == 1 && nUBuckets == ADDRMAN_NEW_BUCKET_COUNT && vvNew[bucket][nUBucketPos] == -1 && info.nRefCount < ADDRMAN_NEW_BUCKETS_PER_ADDRESS) { info.nRefCount++; vvNew[bucket][nUBucketPos] = nIndex; } } } } // Prune new entries with refcount 0 (as a result of collisions). int nLostUnk = 0; for (std::map::const_iterator it = mapInfo.begin(); it != mapInfo.end();) { if (it->second.fInTried == false && it->second.nRefCount == 0) { std::map::const_iterator itCopy = it++; Delete(itCopy->first); nLostUnk++; } else { it++; } } if (nLost + nLostUnk > 0) { LogPrint(BCLog::ADDRMAN, "addrman lost %i new and %i tried addresses due to " "collisions\n", nLostUnk, nLost); } Check(); } void Clear() { std::vector().swap(vRandom); nKey = GetRandHash(); for (size_t bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) { for (size_t entry = 0; entry < ADDRMAN_BUCKET_SIZE; entry++) { vvNew[bucket][entry] = -1; } } for (size_t bucket = 0; bucket < ADDRMAN_TRIED_BUCKET_COUNT; bucket++) { for (size_t entry = 0; entry < ADDRMAN_BUCKET_SIZE; entry++) { vvTried[bucket][entry] = -1; } } nIdCount = 0; nTried = 0; nNew = 0; // Initially at 1 so that "never" is strictly worse. nLastGood = 1; } CAddrMan() { Clear(); } ~CAddrMan() { nKey.SetNull(); } //! Return the number of (unique) addresses in all tables. size_t size() const { // TODO: Cache this in an atomic to avoid this overhead LOCK(cs); return vRandom.size(); } //! Consistency check void Check() { #ifdef DEBUG_ADDRMAN { LOCK(cs); int err; if ((err = Check_())) { LogPrintf("ADDRMAN CONSISTENCY CHECK FAILED!!! err=%i\n", err); } } #endif } //! Add a single address. bool Add(const CAddress &addr, const CNetAddr &source, int64_t nTimePenalty = 0) { LOCK(cs); bool fRet = false; Check(); fRet |= Add_(addr, source, nTimePenalty); Check(); if (fRet) { LogPrint(BCLog::ADDRMAN, "Added %s from %s: %i tried, %i new\n", addr.ToStringIPPort(), source.ToString(), nTried, nNew); } return fRet; } //! Add multiple addresses. bool Add(const std::vector &vAddr, const CNetAddr &source, int64_t nTimePenalty = 0) { LOCK(cs); int nAdd = 0; Check(); for (const CAddress &a : vAddr) { nAdd += Add_(a, source, nTimePenalty) ? 1 : 0; } Check(); if (nAdd) { LogPrint(BCLog::ADDRMAN, "Added %i addresses from %s: %i tried, %i new\n", nAdd, source.ToString(), nTried, nNew); } return nAdd > 0; } //! Mark an entry as accessible. void Good(const CService &addr, bool test_before_evict = true, int64_t nTime = GetAdjustedTime()) { LOCK(cs); Check(); Good_(addr, test_before_evict, nTime); Check(); } //! Mark an entry as connection attempted to. void Attempt(const CService &addr, bool fCountFailure, int64_t nTime = GetAdjustedTime()) { LOCK(cs); Check(); Attempt_(addr, fCountFailure, nTime); Check(); } //! See if any to-be-evicted tried table entries have been tested and if so //! resolve the collisions. void ResolveCollisions() { LOCK(cs); Check(); ResolveCollisions_(); Check(); } //! Randomly select an address in tried that another address is attempting //! to evict. CAddrInfo SelectTriedCollision() { CAddrInfo ret; { LOCK(cs); Check(); ret = SelectTriedCollision_(); Check(); } return ret; } /** * Choose an address to connect to. */ CAddrInfo Select(bool newOnly = false) { CAddrInfo addrRet; { LOCK(cs); Check(); addrRet = Select_(newOnly); Check(); } return addrRet; } //! Return a bunch of addresses, selected at random. std::vector GetAddr() { Check(); std::vector vAddr; { LOCK(cs); GetAddr_(vAddr); } Check(); return vAddr; } //! Mark an entry as currently-connected-to. void Connected(const CService &addr, int64_t nTime = GetAdjustedTime()) { LOCK(cs); Check(); Connected_(addr, nTime); Check(); } void SetServices(const CService &addr, ServiceFlags nServices) { LOCK(cs); Check(); SetServices_(addr, nServices); Check(); } }; #endif // BITCOIN_ADDRMAN_H diff --git a/src/amount.cpp b/src/amount.cpp index 9084e9ead..21f5f18fd 100644 --- a/src/amount.cpp +++ b/src/amount.cpp @@ -1,16 +1,16 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Copyright (c) 2017-2018 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -#include "amount.h" +#include -#include "tinyformat.h" +#include const std::string CURRENCY_UNIT = "BCH"; std::string Amount::ToString() const { return strprintf("%d.%08d %s", *this / COIN, (*this % COIN) / SATOSHI, CURRENCY_UNIT); } diff --git a/src/amount.h b/src/amount.h index c73b01484..fc2b0c9e6 100644 --- a/src/amount.h +++ b/src/amount.h @@ -1,165 +1,165 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Copyright (c) 2017-2018 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_AMOUNT_H #define BITCOIN_AMOUNT_H -#include "serialize.h" +#include #include #include #include #include struct Amount { private: int64_t amount; explicit constexpr Amount(int64_t _amount) : amount(_amount) {} public: constexpr Amount() : amount(0) {} constexpr Amount(const Amount &_camount) : amount(_camount.amount) {} static constexpr Amount zero() { return Amount(0); } static constexpr Amount satoshi() { return Amount(1); } /** * Implement standard operators */ Amount &operator+=(const Amount a) { amount += a.amount; return *this; } Amount &operator-=(const Amount a) { amount -= a.amount; return *this; } /** * Equality */ friend constexpr bool operator==(const Amount a, const Amount b) { return a.amount == b.amount; } friend constexpr bool operator!=(const Amount a, const Amount b) { return !(a == b); } /** * Comparison */ friend constexpr bool operator<(const Amount a, const Amount b) { return a.amount < b.amount; } friend constexpr bool operator>(const Amount a, const Amount b) { return b < a; } friend constexpr bool operator<=(const Amount a, const Amount b) { return !(a > b); } friend constexpr bool operator>=(const Amount a, const Amount b) { return !(a < b); } /** * Unary minus */ constexpr Amount operator-() const { return Amount(-amount); } /** * Addition and subtraction. */ friend constexpr Amount operator+(const Amount a, const Amount b) { return Amount(a.amount + b.amount); } friend constexpr Amount operator-(const Amount a, const Amount b) { return a + -b; } /** * Multiplication */ friend constexpr Amount operator*(const int64_t a, const Amount b) { return Amount(a * b.amount); } friend constexpr Amount operator*(const int a, const Amount b) { return Amount(a * b.amount); } /** * Division */ constexpr int64_t operator/(const Amount b) const { return amount / b.amount; } constexpr Amount operator/(const int64_t b) const { return Amount(amount / b); } constexpr Amount operator/(const int b) const { return Amount(amount / b); } Amount &operator/=(const int64_t n) { amount /= n; return *this; } /** * Modulus */ constexpr Amount operator%(const Amount b) const { return Amount(amount % b.amount); } constexpr Amount operator%(const int64_t b) const { return Amount(amount % b); } constexpr Amount operator%(const int b) const { return Amount(amount % b); } /** * Do not implement double ops to get an error with double and ensure * casting to integer is explicit. */ friend constexpr Amount operator*(const double a, const Amount b) = delete; constexpr Amount operator/(const double b) const = delete; constexpr Amount operator%(const double b) const = delete; // ostream support friend std::ostream &operator<<(std::ostream &stream, const Amount &ca) { return stream << ca.amount; } std::string ToString() const; // serialization support ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(amount); } }; static constexpr Amount SATOSHI = Amount::satoshi(); static constexpr Amount CASH = 100 * SATOSHI; static constexpr Amount COIN = 100000000 * SATOSHI; static constexpr Amount CENT = COIN / 100; extern const std::string CURRENCY_UNIT; /** * No amount larger than this (in satoshi) is valid. * * Note that this constant is *not* the total money supply, which in Bitcoin * currently happens to be less than 21,000,000 BCH for various reasons, but * rather a sanity check. As this sanity check is used by consensus-critical * validation code, the exact value of the MAX_MONEY constant is consensus * critical; in unusual circumstances like a(nother) overflow bug that allowed * for the creation of coins out of thin air modification could lead to a fork. */ static const Amount MAX_MONEY = 21000000 * COIN; inline bool MoneyRange(const Amount nValue) { return nValue >= Amount::zero() && nValue <= MAX_MONEY; } #endif // BITCOIN_AMOUNT_H diff --git a/src/arith_uint256.cpp b/src/arith_uint256.cpp index e441b7d57..628640265 100644 --- a/src/arith_uint256.cpp +++ b/src/arith_uint256.cpp @@ -1,236 +1,236 @@ // Copyright (c) 2009-2010 Satoshi Nakamoto // Copyright (c) 2009-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -#include "arith_uint256.h" +#include -#include "crypto/common.h" -#include "uint256.h" -#include "utilstrencodings.h" +#include +#include +#include #include #include template base_uint::base_uint(const std::string &str) { SetHex(str); } template base_uint &base_uint::operator<<=(unsigned int shift) { base_uint a(*this); for (int i = 0; i < WIDTH; i++) pn[i] = 0; int k = shift / 32; shift = shift % 32; for (int i = 0; i < WIDTH; i++) { if (i + k + 1 < WIDTH && shift != 0) pn[i + k + 1] |= (a.pn[i] >> (32 - shift)); if (i + k < WIDTH) pn[i + k] |= (a.pn[i] << shift); } return *this; } template base_uint &base_uint::operator>>=(unsigned int shift) { base_uint a(*this); for (int i = 0; i < WIDTH; i++) pn[i] = 0; int k = shift / 32; shift = shift % 32; for (int i = 0; i < WIDTH; i++) { if (i - k - 1 >= 0 && shift != 0) pn[i - k - 1] |= (a.pn[i] << (32 - shift)); if (i - k >= 0) pn[i - k] |= (a.pn[i] >> shift); } return *this; } template base_uint &base_uint::operator*=(uint32_t b32) { uint64_t carry = 0; for (int i = 0; i < WIDTH; i++) { uint64_t n = carry + (uint64_t)b32 * pn[i]; pn[i] = n & 0xffffffff; carry = n >> 32; } return *this; } template base_uint &base_uint::operator*=(const base_uint &b) { base_uint a = *this; *this = 0; for (int j = 0; j < WIDTH; j++) { uint64_t carry = 0; for (int i = 0; i + j < WIDTH; i++) { uint64_t n = carry + pn[i + j] + (uint64_t)a.pn[j] * b.pn[i]; pn[i + j] = n & 0xffffffff; carry = n >> 32; } } return *this; } template base_uint &base_uint::operator/=(const base_uint &b) { // make a copy, so we can shift. base_uint div = b; // make a copy, so we can subtract. base_uint num = *this; // the quotient. *this = 0; int num_bits = num.bits(); int div_bits = div.bits(); if (div_bits == 0) throw uint_error("Division by zero"); // the result is certainly 0. if (div_bits > num_bits) return *this; int shift = num_bits - div_bits; // shift so that div and num align. div <<= shift; while (shift >= 0) { if (num >= div) { num -= div; // set a bit of the result. pn[shift / 32] |= (1 << (shift & 31)); } // shift back. div >>= 1; shift--; } // num now contains the remainder of the division. return *this; } template int base_uint::CompareTo(const base_uint &b) const { for (int i = WIDTH - 1; i >= 0; i--) { if (pn[i] < b.pn[i]) return -1; if (pn[i] > b.pn[i]) return 1; } return 0; } template bool base_uint::EqualTo(uint64_t b) const { for (int i = WIDTH - 1; i >= 2; i--) { if (pn[i]) return false; } if (pn[1] != (b >> 32)) return false; if (pn[0] != (b & 0xfffffffful)) return false; return true; } template double base_uint::getdouble() const { double ret = 0.0; double fact = 1.0; for (int i = 0; i < WIDTH; i++) { ret += fact * pn[i]; fact *= 4294967296.0; } return ret; } template std::string base_uint::GetHex() const { return ArithToUint256(*this).GetHex(); } template void base_uint::SetHex(const char *psz) { *this = UintToArith256(uint256S(psz)); } template void base_uint::SetHex(const std::string &str) { SetHex(str.c_str()); } template std::string base_uint::ToString() const { return (GetHex()); } template unsigned int base_uint::bits() const { for (int pos = WIDTH - 1; pos >= 0; pos--) { if (pn[pos]) { for (int nbits = 31; nbits > 0; nbits--) { if (pn[pos] & 1 << nbits) { return 32 * pos + nbits + 1; } } return 32 * pos + 1; } } return 0; } // Explicit instantiations for base_uint<256> template base_uint<256>::base_uint(const std::string &); template base_uint<256> &base_uint<256>::operator<<=(unsigned int); template base_uint<256> &base_uint<256>::operator>>=(unsigned int); template base_uint<256> &base_uint<256>::operator*=(uint32_t b32); template base_uint<256> &base_uint<256>::operator*=(const base_uint<256> &b); template base_uint<256> &base_uint<256>::operator/=(const base_uint<256> &b); template int base_uint<256>::CompareTo(const base_uint<256> &) const; template bool base_uint<256>::EqualTo(uint64_t) const; template double base_uint<256>::getdouble() const; template std::string base_uint<256>::GetHex() const; template std::string base_uint<256>::ToString() const; template void base_uint<256>::SetHex(const char *); template void base_uint<256>::SetHex(const std::string &); template unsigned int base_uint<256>::bits() const; // This implementation directly uses shifts instead of going through an // intermediate MPI representation. arith_uint256 &arith_uint256::SetCompact(uint32_t nCompact, bool *pfNegative, bool *pfOverflow) { int nSize = nCompact >> 24; uint32_t nWord = nCompact & 0x007fffff; if (nSize <= 3) { nWord >>= 8 * (3 - nSize); *this = nWord; } else { *this = nWord; *this <<= 8 * (nSize - 3); } if (pfNegative) *pfNegative = nWord != 0 && (nCompact & 0x00800000) != 0; if (pfOverflow) *pfOverflow = nWord != 0 && ((nSize > 34) || (nWord > 0xff && nSize > 33) || (nWord > 0xffff && nSize > 32)); return *this; } uint32_t arith_uint256::GetCompact(bool fNegative) const { int nSize = (bits() + 7) / 8; uint32_t nCompact = 0; if (nSize <= 3) { nCompact = GetLow64() << 8 * (3 - nSize); } else { arith_uint256 bn = *this >> 8 * (nSize - 3); nCompact = bn.GetLow64(); } // The 0x00800000 bit denotes the sign. // Thus, if it is already set, divide the mantissa by 256 and increase the // exponent. if (nCompact & 0x00800000) { nCompact >>= 8; nSize++; } assert((nCompact & ~0x007fffff) == 0); assert(nSize < 256); nCompact |= nSize << 24; nCompact |= (fNegative && (nCompact & 0x007fffff) ? 0x00800000 : 0); return nCompact; } uint256 ArithToUint256(const arith_uint256 &a) { uint256 b; for (int x = 0; x < a.WIDTH; ++x) WriteLE32(b.begin() + x * 4, a.pn[x]); return b; } arith_uint256 UintToArith256(const uint256 &a) { arith_uint256 b; for (int x = 0; x < b.WIDTH; ++x) b.pn[x] = ReadLE32(a.begin() + x * 4); return b; } diff --git a/src/avalanche.cpp b/src/avalanche.cpp index 5fce827e2..5eb50c8ee 100644 --- a/src/avalanche.cpp +++ b/src/avalanche.cpp @@ -1,510 +1,510 @@ // Copyright (c) 2018 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -#include "avalanche.h" - -#include "chain.h" -#include "config/bitcoin-config.h" -#include "netmessagemaker.h" -#include "reverse_iterator.h" -#include "scheduler.h" -#include "validation.h" +#include + +#include +#include +#include +#include +#include +#include #include /** * Run the avalanche event loop every 10ms. */ static const int64_t AVALANCHE_TIME_STEP_MILLISECONDS = 10; /** * Maximum item count that can be polled at once. */ static const size_t AVALANCHE_MAX_ELEMENT_POLL = 4096; static uint32_t countBits(uint32_t v) { #if HAVE_DECL___BUILTIN_POPCOUNT return __builtin_popcount(v); #else /** * Computes the number of bits set in each group of 8bits then uses a * multiplication to sum all of them in the 8 most significant bits and * return these. * More detailed explanation can be found at * https://www.playingwithpointers.com/blog/swar.html */ v = v - ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); return (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; #endif } bool VoteRecord::registerVote(NodeId nodeid, uint32_t error) { // We just got a new vote, so there is one less inflight request. clearInflightRequest(); // We want to avoid having the same node voting twice in a quorum. if (!addNodeToQuorum(nodeid)) { return false; } /** * 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 * 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 * instance, the queried node does not have the block yet). */ votes = (votes << 1) | (error == 0); consider = (consider << 1) | (int32_t(error) >= 0); /** * We compute the number of yes and/or no votes as follow: * * votes: 1010 * consider: 1100 * * yes votes: 1000 using votes & consider * no votes: 0100 using ~votes & consider */ bool yes = countBits(votes & consider & 0xff) > 6; if (!yes) { bool no = countBits(~votes & consider & 0xff) > 6; if (!no) { // The round is inconclusive. return false; } } // If the round is in agreement with previous rounds, increase confidence. if (isAccepted() == yes) { confidence += 2; return getConfidence() == AVALANCHE_FINALIZATION_SCORE; } // The round changed our state. We reset the confidence. confidence = yes; 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 { uint8_t count = inflight.load(); while (count < AVALANCHE_MAX_INFLIGHT_POLL) { if (inflight.compare_exchange_weak(count, count + 1)) { return true; } } return false; } static bool IsWorthPolling(const CBlockIndex *pindex) { AssertLockHeld(cs_main); if (pindex->nStatus.isInvalid()) { // No point polling invalid blocks. return false; } if (IsBlockFinalized(pindex)) { // There is no point polling finalized block. return false; } return true; } bool AvalancheProcessor::addBlockToReconcile(const CBlockIndex *pindex) { bool isAccepted; { LOCK(cs_main); if (!IsWorthPolling(pindex)) { // There is no point polling this block. return false; } isAccepted = chainActive.Contains(pindex); } return vote_records.getWriteView() ->insert(std::make_pair(pindex, VoteRecord(isAccepted))) .second; } bool AvalancheProcessor::isAccepted(const CBlockIndex *pindex) const { auto r = vote_records.getReadView(); auto it = r->find(pindex); if (it == r.end()) { return false; } return it->second.isAccepted(); } int AvalancheProcessor::getConfidence(const CBlockIndex *pindex) const { auto r = vote_records.getReadView(); auto it = r->find(pindex); if (it == r.end()) { return -1; } return it->second.getConfidence(); } bool AvalancheProcessor::registerVotes( NodeId nodeid, const AvalancheResponse &response, std::vector &updates) { { // Save the time at which we can query again. auto w = peerSet.getWriteView(); auto it = w->find(nodeid); if (it != w->end()) { w->modify(it, [&response](Peer &p) { // FIXME: This will override the time even when we received an // old stale message. This should check that the message is // indeed the most up to date one before updating the time. p.nextRequestTime = std::chrono::steady_clock::now() + std::chrono::milliseconds(response.getCooldown()); }); } } std::vector invs; { // Check that the query exists. auto w = queries.getWriteView(); auto it = w->find(std::make_tuple(nodeid, response.getRound())); if (it == w.end()) { // NB: The request may be old, so we don't increase banscore. return false; } invs = std::move(it->invs); w->erase(it); } // Verify that the request and the vote are consistent. const std::vector &votes = response.GetVotes(); size_t size = invs.size(); if (votes.size() != size) { // TODO: increase banscore for inconsistent response. // NB: This isn't timeout but actually node misbehaving. return false; } for (size_t i = 0; i < size; i++) { if (invs[i].hash != votes[i].GetHash()) { // TODO: increase banscore for inconsistent response. // NB: This isn't timeout but actually node misbehaving. return false; } } std::map responseIndex; { LOCK(cs_main); for (auto &v : votes) { BlockMap::iterator mi = mapBlockIndex.find(v.GetHash()); if (mi == mapBlockIndex.end()) { // This should not happen, but just in case... continue; } CBlockIndex *pindex = mi->second; if (!IsWorthPolling(pindex)) { // There is no point polling this block. continue; } responseIndex.insert(std::make_pair(pindex, v)); } } { // Register votes. auto w = vote_records.getWriteView(); for (auto &p : responseIndex) { CBlockIndex *pindex = p.first; const AvalancheVote &v = p.second; auto it = w->find(pindex); if (it == w.end()) { // We are not voting on that item anymore. continue; } auto &vr = it->second; if (!vr.registerVote(nodeid, v.GetError())) { // This vote did not provide any extra information, move on. continue; } if (!vr.hasFinalized()) { // This item has note been finalized, so we have nothing more to // do. updates.emplace_back( pindex, vr.isAccepted() ? AvalancheBlockUpdate::Status::Accepted : AvalancheBlockUpdate::Status::Rejected); continue; } // We just finalized a vote. If it is valid, then let the caller // know. Either way, remove the item from the map. updates.emplace_back(pindex, vr.isAccepted() ? AvalancheBlockUpdate::Status::Finalized : AvalancheBlockUpdate::Status::Invalid); w->erase(it); } } return true; } bool AvalancheProcessor::addPeer(NodeId nodeid, int64_t score) { return peerSet.getWriteView() ->insert({nodeid, score, std::chrono::steady_clock::now()}) .second; } bool AvalancheProcessor::startEventLoop(CScheduler &scheduler) { LOCK(cs_running); if (running) { // Do not start the event loop twice. return false; } running = true; // Start the event loop. scheduler.scheduleEvery( [this]() -> bool { runEventLoop(); if (!stopRequest) { return true; } LOCK(cs_running); running = false; cond_running.notify_all(); // A stop request was made. return false; }, AVALANCHE_TIME_STEP_MILLISECONDS); return true; } bool AvalancheProcessor::stopEventLoop() { WAIT_LOCK(cs_running, lock); if (!running) { return false; } // Request avalanche to stop. stopRequest = true; // Wait for avalanche to stop. cond_running.wait(lock, [this]() EXCLUSIVE_LOCKS_REQUIRED(cs_running) { return !running; }); stopRequest = false; return true; } std::vector AvalancheProcessor::getInvsForNextPoll(bool forPoll) const { std::vector invs; auto r = vote_records.getReadView(); for (const std::pair &p : reverse_iterate(r)) { const CBlockIndex *pindex = p.first; { LOCK(cs_main); if (!IsWorthPolling(pindex)) { // Obviously do not poll if the block is not worth polling. continue; } } // Check if we can run poll. const bool shouldPoll = forPoll ? p.second.registerPoll() : p.second.shouldPoll(); if (!shouldPoll) { continue; } // We don't have a decision, we need more votes. invs.emplace_back(MSG_BLOCK, pindex->GetBlockHash()); if (invs.size() >= AVALANCHE_MAX_ELEMENT_POLL) { // Make sure we do not produce more invs than specified by the // protocol. return invs; } } return invs; } NodeId AvalancheProcessor::getSuitableNodeToQuery() { auto r = peerSet.getReadView(); auto it = r->get().begin(); if (it == r->get().end()) { return NO_NODE; } if (it->nextRequestTime <= std::chrono::steady_clock::now()) { return it->nodeid; } return NO_NODE; } void AvalancheProcessor::clearTimedoutRequests() { auto now = std::chrono::steady_clock::now(); std::map timedout_items{}; { // Clear expired requests. auto w = queries.getWriteView(); auto it = w->get().begin(); while (it != w->get().end() && it->timeout < now) { for (auto &i : it->invs) { timedout_items[i]++; } w->get().erase(it++); } } if (timedout_items.empty()) { return; } // In flight request accounting. for (const auto &p : timedout_items) { const CInv &inv = p.first; assert(inv.type == MSG_BLOCK); CBlockIndex *pindex; { LOCK(cs_main); BlockMap::iterator mi = mapBlockIndex.find(inv.hash); if (mi == mapBlockIndex.end()) { continue; } pindex = mi->second; } auto w = vote_records.getWriteView(); auto it = w->find(pindex); if (it == w.end()) { continue; } it->second.clearInflightRequest(p.second); } } void AvalancheProcessor::runEventLoop() { // First things first, check if we have requests that timed out and clear // them. clearTimedoutRequests(); while (true) { NodeId nodeid = getSuitableNodeToQuery(); if (nodeid == NO_NODE) { return; } /** * If we lost contact to that node, then we remove it from nodeids, but * never add the request to queries, which ensures bad nodes get cleaned * up over time. */ std::vector invs; bool hasSent = connman->ForNode(nodeid, [this, &invs](CNode *pnode) { invs = getInvsForNextPoll(); if (invs.empty()) { return false; } uint64_t current_round = round++; { // Compute the time at which this requests times out. auto timeout = std::chrono::steady_clock::now() + queryTimeoutDuration; // Register the query. queries.getWriteView()->insert( {pnode->GetId(), current_round, timeout, invs}); // Set the timeout. auto w = peerSet.getWriteView(); auto it = w->find(pnode->GetId()); if (it != w->end()) { w->modify(it, [&timeout](Peer &p) { p.nextRequestTime = timeout; }); } } // Send the query to the node. connman->PushMessage( pnode, CNetMsgMaker(pnode->GetSendVersion()) .Make(NetMsgType::AVAPOLL, AvalanchePoll(current_round, std::move(invs)))); return true; }); // Success! if (hasSent || invs.empty()) { return; } // This node is obsolete, delete it. peerSet.getWriteView()->erase(nodeid); } } diff --git a/src/avalanche.h b/src/avalanche.h index 219df25e7..2b7234dba 100644 --- a/src/avalanche.h +++ b/src/avalanche.h @@ -1,354 +1,354 @@ // Copyright (c) 2018 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_H #define BITCOIN_AVALANCHE_H -#include "blockindexworkcomparator.h" -#include "net.h" -#include "protocol.h" // for CInv -#include "rwcollection.h" -#include "serialize.h" -#include "uint256.h" +#include +#include +#include // for CInv +#include +#include +#include #include #include #include #include #include #include #include #include #include #include class Config; class CBlockIndex; class CScheduler; namespace { /** * Finalization score. */ static const int AVALANCHE_FINALIZATION_SCORE = 128; /** * How long before we consider that a query timed out. */ static const int AVALANCHE_DEFAULT_QUERY_TIMEOUT_DURATION_MILLISECONDS = 10000; /** * How many inflight requests can exist for one item. */ static const int AVALANCHE_MAX_INFLIGHT_POLL = 10; /** * Special NodeId that represent no node. */ static const NodeId NO_NODE = -1; } /** * Vote history. */ struct VoteRecord { private: // confidence's LSB bit is the result. Higher bits are actual confidence // score. uint16_t confidence = 0; // Historical record of votes. uint8_t votes = 0; // Each bit indicate if the vote is to be considered. uint8_t consider = 0; // How many in flight requests exists for this element. mutable std::atomic inflight{0}; // Seed for pseudorandom operations. const uint32_t seed = 0; // Track how many successful votes occured. uint32_t successfulVotes = 0; // Track the nodes which are part of the quorum. std::array nodeFilter{{0, 0, 0, 0, 0, 0, 0, 0}}; public: VoteRecord(bool accepted) : confidence(accepted) {} /** * Copy semantic */ VoteRecord(const VoteRecord &other) : confidence(other.confidence), votes(other.votes), consider(other.consider), inflight(other.inflight.load()), successfulVotes(other.successfulVotes), nodeFilter(other.nodeFilter) { } /** * Vote accounting facilities. */ bool isAccepted() const { return confidence & 0x01; } uint16_t getConfidence() const { return confidence >> 1; } bool hasFinalized() const { return getConfidence() >= AVALANCHE_FINALIZATION_SCORE; } /** * Register a new vote for an item and update confidence accordingly. * Returns true if the acceptance or finalization state changed. */ bool registerVote(NodeId nodeid, uint32_t error); /** * Register that a request is being made regarding that item. * The method is made const so that it can be accessed via a read only view * of vote_records. It's not a problem as it is made thread safe. */ bool registerPoll() const; /** * Return if this item is in condition to be polled at the moment. */ bool shouldPoll() const { return inflight < AVALANCHE_MAX_INFLIGHT_POLL; } /** * Clear `count` inflight requests. */ void clearInflightRequest(uint8_t count = 1) { inflight -= count; } private: /** * Add the node to the quorum. * Returns true if the node was added, false if the node already was in the * quorum. */ bool addNodeToQuorum(NodeId nodeid); }; class AvalancheVote { uint32_t error; uint256 hash; public: AvalancheVote() : error(-1), hash() {} AvalancheVote(uint32_t errorIn, uint256 hashIn) : error(errorIn), hash(hashIn) {} const uint256 &GetHash() const { return hash; } uint32_t GetError() const { return error; } // serialization support ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(error); READWRITE(hash); } }; class AvalancheResponse { uint64_t round; uint32_t cooldown; std::vector votes; public: AvalancheResponse(uint64_t roundIn, uint32_t cooldownIn, std::vector votesIn) : round(roundIn), cooldown(cooldownIn), votes(votesIn) {} uint64_t getRound() const { return round; } uint32_t getCooldown() const { return cooldown; } const std::vector &GetVotes() const { return votes; } // serialization support ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(round); READWRITE(cooldown); READWRITE(votes); } }; class AvalanchePoll { uint64_t round; std::vector invs; public: AvalanchePoll(uint64_t roundIn, std::vector invsIn) : round(roundIn), invs(invsIn) {} const std::vector &GetInvs() const { return invs; } // serialization support ADD_SERIALIZE_METHODS; template inline void SerializationOp(Stream &s, Operation ser_action) { READWRITE(round); READWRITE(invs); } }; class AvalancheBlockUpdate { union { CBlockIndex *pindex; uintptr_t raw; }; static const size_t STATUS_BITS = 2; static const uintptr_t MASK = (1 << STATUS_BITS) - 1; static_assert( alignof(CBlockIndex) >= (1 << STATUS_BITS), "CBlockIndex alignement doesn't allow for Status to be stored."); public: enum Status : uint8_t { Invalid, Rejected, Accepted, Finalized, }; AvalancheBlockUpdate(CBlockIndex *pindexIn, Status statusIn) : pindex(pindexIn) { raw |= statusIn; } Status getStatus() const { return Status(raw & MASK); } CBlockIndex *getBlockIndex() { return reinterpret_cast(raw & ~MASK); } const CBlockIndex *getBlockIndex() const { return const_cast(this)->getBlockIndex(); } }; typedef std::map BlockVoteMap; struct next_request_time {}; struct query_timeout {}; class AvalancheProcessor { private: CConnman *connman; std::chrono::milliseconds queryTimeoutDuration; /** * Blocks to run avalanche on. */ RWCollection vote_records; /** * Keep track of peers and queries sent. */ std::atomic round; typedef std::chrono::time_point TimePoint; struct Peer { NodeId nodeid; int64_t score; TimePoint nextRequestTime; }; typedef boost::multi_index_container< Peer, boost::multi_index::indexed_by< // index by nodeid boost::multi_index::hashed_unique< boost::multi_index::member>, // sorted by nextRequestTime boost::multi_index::ordered_non_unique< boost::multi_index::tag, boost::multi_index::member>>> PeerSet; RWCollection peerSet; struct Query { NodeId nodeid; uint64_t round; TimePoint timeout; /** * We declare this as mutable so it can be modified in the multi_index. * This is ok because we do not use this field to index in anyway. * * /!\ Do not use any mutable field as index. */ mutable std::vector invs; }; typedef boost::multi_index_container< Query, boost::multi_index::indexed_by< // index by nodeid/round boost::multi_index::ordered_unique< boost::multi_index::composite_key< Query, boost::multi_index::member, boost::multi_index::member>>, // sorted by timeout boost::multi_index::ordered_non_unique< boost::multi_index::tag, boost::multi_index::member>>> QuerySet; RWCollection queries; /** * Start stop machinery. */ std::atomic stopRequest; bool running GUARDED_BY(cs_running); CWaitableCriticalSection cs_running; std::condition_variable cond_running; public: AvalancheProcessor(CConnman *connmanIn) : connman(connmanIn), queryTimeoutDuration( AVALANCHE_DEFAULT_QUERY_TIMEOUT_DURATION_MILLISECONDS), round(0), stopRequest(false), running(false) {} ~AvalancheProcessor() { stopEventLoop(); } void setQueryTimeoutDuration(std::chrono::milliseconds d) { queryTimeoutDuration = d; } bool addBlockToReconcile(const CBlockIndex *pindex); bool isAccepted(const CBlockIndex *pindex) const; int getConfidence(const CBlockIndex *pindex) const; bool registerVotes(NodeId nodeid, const AvalancheResponse &response, std::vector &updates); bool addPeer(NodeId nodeid, int64_t score); bool startEventLoop(CScheduler &scheduler); bool stopEventLoop(); private: void runEventLoop(); void clearTimedoutRequests(); std::vector getInvsForNextPoll(bool forPoll = true) const; NodeId getSuitableNodeToQuery(); friend struct AvalancheTest; }; #endif // BITCOIN_AVALANCHE_H diff --git a/src/base58.cpp b/src/base58.cpp index 265cc0ecb..18889f86b 100644 --- a/src/base58.cpp +++ b/src/base58.cpp @@ -1,303 +1,304 @@ // Copyright (c) 2014-2016 The Bitcoin Core developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -#include "base58.h" +#include -#include "hash.h" -#include "script/script.h" -#include "uint256.h" -#include "utilstrencodings.h" +#include +#include