diff --git a/src/addrman.cpp b/src/addrman.cpp index 74f7d17e9..35aeae56f 100644 --- a/src/addrman.cpp +++ b/src/addrman.cpp @@ -1,719 +1,716 @@ // 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 #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 nRnd = insecure_rand.randrange(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)) { + if (nFactor > 1 && (insecure_rand.randrange(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))) { + if (!newOnly && + (nTried > 0 && (nNew == 0 || insecure_rand.randbool() == 0))) { // use a tried node double fChanceFactor = 1.0; while (1) { - int nKBucket = RandomInt(ADDRMAN_TRIED_BUCKET_COUNT); - int nKBucketPos = RandomInt(ADDRMAN_BUCKET_SIZE); + int nKBucket = insecure_rand.randrange(ADDRMAN_TRIED_BUCKET_COUNT); + int nKBucketPos = insecure_rand.randrange(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) < + if (insecure_rand.randbits(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); + int nUBucket = insecure_rand.randrange(ADDRMAN_NEW_BUCKET_COUNT); + int nUBucketPos = insecure_rand.randrange(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) < + if (insecure_rand.randbits(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; + int nRndPos = insecure_rand.randrange(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())); + // Selects a random element from m_tried_collisions + std::advance(it, insecure_rand.randrange(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 49b26736f..ae977a70f 100644 --- a/src/addrman.h +++ b/src/addrman.h @@ -1,671 +1,667 @@ // 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 #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) { READWRITEAS(CAddress, *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 { protected: //! critical section to protect the inner data structures mutable CCriticalSection cs; private: //! last used nId int nIdCount GUARDED_BY(cs); //! table with information about all nIds std::map mapInfo GUARDED_BY(cs); //! find an nId based on its network address std::map mapAddr GUARDED_BY(cs); //! randomly-ordered vector of all nIds std::vector vRandom GUARDED_BY(cs); // number of "tried" entries int nTried GUARDED_BY(cs); //! list of "tried" buckets int vvTried[ADDRMAN_TRIED_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE] GUARDED_BY(cs); //! number of (unique) "new" entries int nNew GUARDED_BY(cs); //! list of "new" buckets int vvNew[ADDRMAN_NEW_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE] GUARDED_BY(cs); //! last time Good was called (memory only) int64_t nLastGood GUARDED_BY(cs); //! 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) EXCLUSIVE_LOCKS_REQUIRED(cs); //! 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) EXCLUSIVE_LOCKS_REQUIRED(cs); //! Swap two elements in vRandom. void SwapRandom(unsigned int nRandomPos1, unsigned int nRandomPos2) EXCLUSIVE_LOCKS_REQUIRED(cs); //! Move an entry from the "new" table(s) to the "tried" table void MakeTried(CAddrInfo &info, int nId) EXCLUSIVE_LOCKS_REQUIRED(cs); //! Delete an entry. It must not be in tried, and have refcount 0. void Delete(int nId) EXCLUSIVE_LOCKS_REQUIRED(cs); //! Clear a position in a "new" table. This is the only place where entries //! are actually deleted. void ClearNew(int nUBucket, int nUBucketPos) EXCLUSIVE_LOCKS_REQUIRED(cs); //! Mark an entry "good", possibly moving it from "new" to "tried". void Good_(const CService &addr, bool test_before_evict, int64_t time) EXCLUSIVE_LOCKS_REQUIRED(cs); //! Add an entry to the "new" table. bool Add_(const CAddress &addr, const CNetAddr &source, int64_t nTimePenalty) EXCLUSIVE_LOCKS_REQUIRED(cs); //! Mark an entry as attempted to connect. void Attempt_(const CService &addr, bool fCountFailure, int64_t nTime) EXCLUSIVE_LOCKS_REQUIRED(cs); //! Select an address to connect to, if newOnly is set to true, only the new //! table is selected from. CAddrInfo Select_(bool newOnly) EXCLUSIVE_LOCKS_REQUIRED(cs); //! See if any to-be-evicted tried table entries have been tested and if so //! resolve the collisions. void ResolveCollisions_() EXCLUSIVE_LOCKS_REQUIRED(cs); //! Return a random to-be-evicted tried table address. CAddrInfo SelectTriedCollision_() EXCLUSIVE_LOCKS_REQUIRED(cs); - //! 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_() EXCLUSIVE_LOCKS_REQUIRED(cs); #endif //! Select several addresses at once. void GetAddr_(std::vector &vAddr) EXCLUSIVE_LOCKS_REQUIRED(cs); //! Mark an entry as currently-connected-to. void Connected_(const CService &addr, int64_t nTime) EXCLUSIVE_LOCKS_REQUIRED(cs); //! Update an entry's service bits. void SetServices_(const CService &addr, ServiceFlags nServices) EXCLUSIVE_LOCKS_REQUIRED(cs); 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() { LOCK(cs); std::vector().swap(vRandom); - nKey = GetRandHash(); + nKey = insecure_rand.rand256(); 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; mapInfo.clear(); mapAddr.clear(); } 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/test/addrman_tests.cpp b/src/test/addrman_tests.cpp index 7f5f1dfa9..07f8a087e 100644 --- a/src/test/addrman_tests.cpp +++ b/src/test/addrman_tests.cpp @@ -1,693 +1,688 @@ // 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 #include #include #include #include #include #include class CAddrManTest : public CAddrMan { uint64_t state; public: CAddrManTest() { state = 1; } //! Ensure that bucket placement is always the same for testing purposes. void MakeDeterministic() { nKey.SetNull(); insecure_rand = FastRandomContext(true); } - int RandomInt(int nMax) override { - state = (CHashWriter(SER_GETHASH, 0) << state).GetHash().GetCheapHash(); - return (unsigned int)(state % nMax); - } - CAddrInfo *Find(const CNetAddr &addr, int *pnId = nullptr) { LOCK(cs); return CAddrMan::Find(addr, pnId); } CAddrInfo *Create(const CAddress &addr, const CNetAddr &addrSource, int *pnId = nullptr) { LOCK(cs); return CAddrMan::Create(addr, addrSource, pnId); } void Delete(int nId) { LOCK(cs); CAddrMan::Delete(nId); } // Simulates connection failure so that we can test eviction of offline // nodes void SimConnFail(CService &addr) { LOCK(cs); int64_t nLastSuccess = 1; // Set last good connection in the deep past. Good_(addr, true, nLastSuccess); bool count_failure = false; int64_t nLastTry = GetAdjustedTime() - 61; Attempt(addr, count_failure, nLastTry); } }; static CNetAddr ResolveIP(const char *ip) { CNetAddr addr; BOOST_CHECK_MESSAGE(LookupHost(ip, addr, false), strprintf("failed to resolve: %s", ip)); return addr; } static CNetAddr ResolveIP(std::string ip) { return ResolveIP(ip.c_str()); } static CService ResolveService(const char *ip, int port = 0) { CService serv; BOOST_CHECK_MESSAGE(Lookup(ip, serv, port, false), strprintf("failed to resolve: %s:%i", ip, port)); return serv; } static CService ResolveService(std::string ip, int port = 0) { return ResolveService(ip.c_str(), port); } BOOST_FIXTURE_TEST_SUITE(addrman_tests, BasicTestingSetup) BOOST_AUTO_TEST_CASE(addrman_simple) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); CNetAddr source = ResolveIP("252.2.2.2"); // Test: Does Addrman respond correctly when empty. BOOST_CHECK_EQUAL(addrman.size(), 0); CAddrInfo addr_null = addrman.Select(); BOOST_CHECK_EQUAL(addr_null.ToString(), "[::]:0"); // Test: Does Addrman::Add work as expected. CService addr1 = ResolveService("250.1.1.1", 8333); BOOST_CHECK(addrman.Add(CAddress(addr1, NODE_NONE), source)); BOOST_CHECK_EQUAL(addrman.size(), 1); CAddrInfo addr_ret1 = addrman.Select(); BOOST_CHECK_EQUAL(addr_ret1.ToString(), "250.1.1.1:8333"); // Test: Does IP address deduplication work correctly. // Expected dup IP should not be added. CService addr1_dup = ResolveService("250.1.1.1", 8333); BOOST_CHECK(!addrman.Add(CAddress(addr1_dup, NODE_NONE), source)); BOOST_CHECK_EQUAL(addrman.size(), 1); // Test: New table has one addr and we add a diff addr we should // have at least one addr. // Note that addrman's size cannot be tested reliably after insertion, as // hash collisions may occur. But we can always be sure of at least one // success. CService addr2 = ResolveService("250.1.1.2", 8333); BOOST_CHECK(addrman.Add(CAddress(addr2, NODE_NONE), source)); BOOST_CHECK(addrman.size() >= 1); // Test: AddrMan::Clear() should empty the new table. addrman.Clear(); BOOST_CHECK_EQUAL(addrman.size(), 0); CAddrInfo addr_null2 = addrman.Select(); BOOST_CHECK_EQUAL(addr_null2.ToString(), "[::]:0"); // Test: AddrMan::Add multiple addresses works as expected std::vector vAddr; vAddr.push_back(CAddress(ResolveService("250.1.1.3", 8333), NODE_NONE)); vAddr.push_back(CAddress(ResolveService("250.1.1.4", 8333), NODE_NONE)); BOOST_CHECK(addrman.Add(vAddr, source)); BOOST_CHECK(addrman.size() >= 1); } BOOST_AUTO_TEST_CASE(addrman_ports) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); CNetAddr source = ResolveIP("252.2.2.2"); BOOST_CHECK_EQUAL(addrman.size(), 0); // Test: Addr with same IP but diff port does not replace existing addr. CService addr1 = ResolveService("250.1.1.1", 8333); addrman.Add(CAddress(addr1, NODE_NONE), source); BOOST_CHECK_EQUAL(addrman.size(), 1); CService addr1_port = ResolveService("250.1.1.1", 8334); addrman.Add(CAddress(addr1_port, NODE_NONE), source); BOOST_CHECK_EQUAL(addrman.size(), 1); CAddrInfo addr_ret2 = addrman.Select(); BOOST_CHECK_EQUAL(addr_ret2.ToString(), "250.1.1.1:8333"); // Test: Add same IP but diff port to tried table, it doesn't get added. // Perhaps this is not ideal behavior but it is the current behavior. addrman.Good(CAddress(addr1_port, NODE_NONE)); BOOST_CHECK_EQUAL(addrman.size(), 1); bool newOnly = true; CAddrInfo addr_ret3 = addrman.Select(newOnly); BOOST_CHECK_EQUAL(addr_ret3.ToString(), "250.1.1.1:8333"); } BOOST_AUTO_TEST_CASE(addrman_select) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); CNetAddr source = ResolveIP("252.2.2.2"); // Test: Select from new with 1 addr in new. CService addr1 = ResolveService("250.1.1.1", 8333); addrman.Add(CAddress(addr1, NODE_NONE), source); BOOST_CHECK_EQUAL(addrman.size(), 1); bool newOnly = true; CAddrInfo addr_ret1 = addrman.Select(newOnly); BOOST_CHECK_EQUAL(addr_ret1.ToString(), "250.1.1.1:8333"); // Test: move addr to tried, select from new expected nothing returned. addrman.Good(CAddress(addr1, NODE_NONE)); BOOST_CHECK_EQUAL(addrman.size(), 1); CAddrInfo addr_ret2 = addrman.Select(newOnly); BOOST_CHECK_EQUAL(addr_ret2.ToString(), "[::]:0"); CAddrInfo addr_ret3 = addrman.Select(); BOOST_CHECK_EQUAL(addr_ret3.ToString(), "250.1.1.1:8333"); BOOST_CHECK_EQUAL(addrman.size(), 1); // Add three addresses to new table. CService addr2 = ResolveService("250.3.1.1", 8333); CService addr3 = ResolveService("250.3.2.2", 9999); CService addr4 = ResolveService("250.3.3.3", 9999); addrman.Add(CAddress(addr2, NODE_NONE), ResolveService("250.3.1.1", 8333)); addrman.Add(CAddress(addr3, NODE_NONE), ResolveService("250.3.1.1", 8333)); addrman.Add(CAddress(addr4, NODE_NONE), ResolveService("250.4.1.1", 8333)); // Add three addresses to tried table. CService addr5 = ResolveService("250.4.4.4", 8333); CService addr6 = ResolveService("250.4.5.5", 7777); CService addr7 = ResolveService("250.4.6.6", 8333); addrman.Add(CAddress(addr5, NODE_NONE), ResolveService("250.3.1.1", 8333)); addrman.Good(CAddress(addr5, NODE_NONE)); addrman.Add(CAddress(addr6, NODE_NONE), ResolveService("250.3.1.1", 8333)); addrman.Good(CAddress(addr6, NODE_NONE)); addrman.Add(CAddress(addr7, NODE_NONE), ResolveService("250.1.1.3", 8333)); addrman.Good(CAddress(addr7, NODE_NONE)); // Test: 6 addrs + 1 addr from last test = 7. BOOST_CHECK_EQUAL(addrman.size(), 7); // Test: Select pulls from new and tried regardless of port number. std::set ports; for (int i = 0; i < 20; ++i) { ports.insert(addrman.Select().GetPort()); } BOOST_CHECK_EQUAL(ports.size(), 3); } BOOST_AUTO_TEST_CASE(addrman_new_collisions) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); CNetAddr source = ResolveIP("252.2.2.2"); BOOST_CHECK_EQUAL(addrman.size(), 0); for (unsigned int i = 1; i < 18; i++) { CService addr = ResolveService("250.1.1." + std::to_string(i)); addrman.Add(CAddress(addr, NODE_NONE), source); // Test: No collision in new table yet. BOOST_CHECK_EQUAL(addrman.size(), i); } // Test: new table collision! CService addr1 = ResolveService("250.1.1.18"); addrman.Add(CAddress(addr1, NODE_NONE), source); BOOST_CHECK_EQUAL(addrman.size(), 17); CService addr2 = ResolveService("250.1.1.19"); addrman.Add(CAddress(addr2, NODE_NONE), source); BOOST_CHECK_EQUAL(addrman.size(), 18); } BOOST_AUTO_TEST_CASE(addrman_tried_collisions) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); CNetAddr source = ResolveIP("252.2.2.2"); BOOST_CHECK_EQUAL(addrman.size(), 0); for (unsigned int i = 1; i < 80; i++) { CService addr = ResolveService("250.1.1." + std::to_string(i)); addrman.Add(CAddress(addr, NODE_NONE), source); addrman.Good(CAddress(addr, NODE_NONE)); // Test: No collision in tried table yet. BOOST_CHECK_EQUAL(addrman.size(), i); } // Test: tried table collision! CService addr1 = ResolveService("250.1.1.80"); addrman.Add(CAddress(addr1, NODE_NONE), source); BOOST_CHECK_EQUAL(addrman.size(), 79); CService addr2 = ResolveService("250.1.1.81"); addrman.Add(CAddress(addr2, NODE_NONE), source); BOOST_CHECK_EQUAL(addrman.size(), 80); } BOOST_AUTO_TEST_CASE(addrman_find) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); BOOST_CHECK_EQUAL(addrman.size(), 0); CAddress addr1 = CAddress(ResolveService("250.1.2.1", 8333), NODE_NONE); CAddress addr2 = CAddress(ResolveService("250.1.2.1", 9999), NODE_NONE); CAddress addr3 = CAddress(ResolveService("251.255.2.1", 8333), NODE_NONE); CNetAddr source1 = ResolveIP("250.1.2.1"); CNetAddr source2 = ResolveIP("250.1.2.2"); addrman.Add(addr1, source1); addrman.Add(addr2, source2); addrman.Add(addr3, source1); // Test: ensure Find returns an IP matching what we searched on. CAddrInfo *info1 = addrman.Find(addr1); BOOST_REQUIRE(info1); BOOST_CHECK_EQUAL(info1->ToString(), "250.1.2.1:8333"); // Test: Find does not discriminate by port number. CAddrInfo *info2 = addrman.Find(addr2); BOOST_REQUIRE(info2); BOOST_CHECK_EQUAL(info2->ToString(), info1->ToString()); // Test: Find returns another IP matching what we searched on. CAddrInfo *info3 = addrman.Find(addr3); BOOST_REQUIRE(info3); BOOST_CHECK_EQUAL(info3->ToString(), "251.255.2.1:8333"); } BOOST_AUTO_TEST_CASE(addrman_create) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); BOOST_CHECK_EQUAL(addrman.size(), 0); CAddress addr1 = CAddress(ResolveService("250.1.2.1", 8333), NODE_NONE); CNetAddr source1 = ResolveIP("250.1.2.1"); int nId; CAddrInfo *pinfo = addrman.Create(addr1, source1, &nId); // Test: The result should be the same as the input addr. BOOST_CHECK_EQUAL(pinfo->ToString(), "250.1.2.1:8333"); CAddrInfo *info2 = addrman.Find(addr1); BOOST_CHECK_EQUAL(info2->ToString(), "250.1.2.1:8333"); } BOOST_AUTO_TEST_CASE(addrman_delete) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); BOOST_CHECK_EQUAL(addrman.size(), 0); CAddress addr1 = CAddress(ResolveService("250.1.2.1", 8333), NODE_NONE); CNetAddr source1 = ResolveIP("250.1.2.1"); int nId; addrman.Create(addr1, source1, &nId); // Test: Delete should actually delete the addr. BOOST_CHECK_EQUAL(addrman.size(), 1); addrman.Delete(nId); BOOST_CHECK_EQUAL(addrman.size(), 0); CAddrInfo *info2 = addrman.Find(addr1); BOOST_CHECK(info2 == nullptr); } BOOST_AUTO_TEST_CASE(addrman_getaddr) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); // Test: Sanity check, GetAddr should never return anything if addrman // is empty. BOOST_CHECK_EQUAL(addrman.size(), 0); std::vector vAddr1 = addrman.GetAddr(); BOOST_CHECK_EQUAL(vAddr1.size(), 0); CAddress addr1 = CAddress(ResolveService("250.250.2.1", 8333), NODE_NONE); addr1.nTime = GetAdjustedTime(); // Set time so isTerrible = false CAddress addr2 = CAddress(ResolveService("250.251.2.2", 9999), NODE_NONE); addr2.nTime = GetAdjustedTime(); CAddress addr3 = CAddress(ResolveService("251.252.2.3", 8333), NODE_NONE); addr3.nTime = GetAdjustedTime(); CAddress addr4 = CAddress(ResolveService("252.253.3.4", 8333), NODE_NONE); addr4.nTime = GetAdjustedTime(); CAddress addr5 = CAddress(ResolveService("252.254.4.5", 8333), NODE_NONE); addr5.nTime = GetAdjustedTime(); CNetAddr source1 = ResolveIP("250.1.2.1"); CNetAddr source2 = ResolveIP("250.2.3.3"); // Test: Ensure GetAddr works with new addresses. addrman.Add(addr1, source1); addrman.Add(addr2, source2); addrman.Add(addr3, source1); addrman.Add(addr4, source2); addrman.Add(addr5, source1); // GetAddr returns 23% of addresses, 23% of 5 is 1 rounded down. BOOST_CHECK_EQUAL(addrman.GetAddr().size(), 1); // Test: Ensure GetAddr works with new and tried addresses. addrman.Good(CAddress(addr1, NODE_NONE)); addrman.Good(CAddress(addr2, NODE_NONE)); BOOST_CHECK_EQUAL(addrman.GetAddr().size(), 1); // Test: Ensure GetAddr still returns 23% when addrman has many addrs. for (unsigned int i = 1; i < (8 * 256); i++) { int octet1 = i % 256; int octet2 = i >> 8 % 256; std::string strAddr = std::to_string(octet1) + "." + std::to_string(octet2) + ".1.23"; CAddress addr = CAddress(ResolveService(strAddr), NODE_NONE); // Ensure that for all addrs in addrman, isTerrible == false. addr.nTime = GetAdjustedTime(); addrman.Add(addr, ResolveIP(strAddr)); if (i % 8 == 0) addrman.Good(addr); } std::vector vAddr = addrman.GetAddr(); size_t percent23 = (addrman.size() * 23) / 100; BOOST_CHECK_EQUAL(vAddr.size(), percent23); BOOST_CHECK_EQUAL(vAddr.size(), 461); // (Addrman.size() < number of addresses added) due to address collisions. BOOST_CHECK_EQUAL(addrman.size(), 2006); } BOOST_AUTO_TEST_CASE(caddrinfo_get_tried_bucket) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); CAddress addr1 = CAddress(ResolveService("250.1.1.1", 8333), NODE_NONE); CAddress addr2 = CAddress(ResolveService("250.1.1.1", 9999), NODE_NONE); CNetAddr source1 = ResolveIP("250.1.1.1"); CAddrInfo info1 = CAddrInfo(addr1, source1); uint256 nKey1 = (uint256)(CHashWriter(SER_GETHASH, 0) << 1).GetHash(); uint256 nKey2 = (uint256)(CHashWriter(SER_GETHASH, 0) << 2).GetHash(); BOOST_CHECK_EQUAL(info1.GetTriedBucket(nKey1), 40); // Test: Make sure key actually randomizes bucket placement. A fail on // this test could be a security issue. BOOST_CHECK(info1.GetTriedBucket(nKey1) != info1.GetTriedBucket(nKey2)); // Test: Two addresses with same IP but different ports can map to // different buckets because they have different keys. CAddrInfo info2 = CAddrInfo(addr2, source1); BOOST_CHECK(info1.GetKey() != info2.GetKey()); BOOST_CHECK(info1.GetTriedBucket(nKey1) != info2.GetTriedBucket(nKey1)); std::set buckets; for (int i = 0; i < 255; i++) { CAddrInfo infoi = CAddrInfo( CAddress(ResolveService("250.1.1." + std::to_string(i)), NODE_NONE), ResolveIP("250.1.1." + std::to_string(i))); int bucket = infoi.GetTriedBucket(nKey1); buckets.insert(bucket); } // Test: IP addresses in the same group (\16 prefix for IPv4) should // never get more than 8 buckets BOOST_CHECK_EQUAL(buckets.size(), 8); buckets.clear(); for (int j = 0; j < 255; j++) { CAddrInfo infoj = CAddrInfo( CAddress(ResolveService("250." + std::to_string(j) + ".1.1"), NODE_NONE), ResolveIP("250." + std::to_string(j) + ".1.1")); int bucket = infoj.GetTriedBucket(nKey1); buckets.insert(bucket); } // Test: IP addresses in the different groups should map to more than // 8 buckets. BOOST_CHECK_EQUAL(buckets.size(), 160); } BOOST_AUTO_TEST_CASE(caddrinfo_get_new_bucket) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); CAddress addr1 = CAddress(ResolveService("250.1.2.1", 8333), NODE_NONE); CAddress addr2 = CAddress(ResolveService("250.1.2.1", 9999), NODE_NONE); CNetAddr source1 = ResolveIP("250.1.2.1"); CAddrInfo info1 = CAddrInfo(addr1, source1); uint256 nKey1 = (uint256)(CHashWriter(SER_GETHASH, 0) << 1).GetHash(); uint256 nKey2 = (uint256)(CHashWriter(SER_GETHASH, 0) << 2).GetHash(); // Test: Make sure the buckets are what we expect BOOST_CHECK_EQUAL(info1.GetNewBucket(nKey1), 786); BOOST_CHECK_EQUAL(info1.GetNewBucket(nKey1, source1), 786); // Test: Make sure key actually randomizes bucket placement. A fail on // this test could be a security issue. BOOST_CHECK(info1.GetNewBucket(nKey1) != info1.GetNewBucket(nKey2)); // Test: Ports should not effect bucket placement in the addr CAddrInfo info2 = CAddrInfo(addr2, source1); BOOST_CHECK(info1.GetKey() != info2.GetKey()); BOOST_CHECK_EQUAL(info1.GetNewBucket(nKey1), info2.GetNewBucket(nKey1)); std::set buckets; for (int i = 0; i < 255; i++) { CAddrInfo infoi = CAddrInfo( CAddress(ResolveService("250.1.1." + std::to_string(i)), NODE_NONE), ResolveIP("250.1.1." + std::to_string(i))); int bucket = infoi.GetNewBucket(nKey1); buckets.insert(bucket); } // Test: IP addresses in the same group (\16 prefix for IPv4) should // always map to the same bucket. BOOST_CHECK_EQUAL(buckets.size(), 1); buckets.clear(); for (int j = 0; j < 4 * 255; j++) { CAddrInfo infoj = CAddrInfo( CAddress(ResolveService(std::to_string(250 + (j / 255)) + "." + std::to_string(j % 256) + ".1.1"), NODE_NONE), ResolveIP("251.4.1.1")); int bucket = infoj.GetNewBucket(nKey1); buckets.insert(bucket); } // Test: IP addresses in the same source groups should map to no more // than 64 buckets. BOOST_CHECK(buckets.size() <= 64); buckets.clear(); for (int p = 0; p < 255; p++) { CAddrInfo infoj = CAddrInfo(CAddress(ResolveService("250.1.1.1"), NODE_NONE), ResolveIP("250." + std::to_string(p) + ".1.1")); int bucket = infoj.GetNewBucket(nKey1); buckets.insert(bucket); } // Test: IP addresses in the different source groups should map to more // than 64 buckets. BOOST_CHECK(buckets.size() > 64); } BOOST_AUTO_TEST_CASE(addrman_selecttriedcollision) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); BOOST_CHECK(addrman.size() == 0); // Empty addrman should return blank addrman info. BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); // Add twenty two addresses. CNetAddr source = ResolveIP("252.2.2.2"); for (unsigned int i = 1; i < 23; i++) { CService addr = ResolveService("250.1.1." + std::to_string(i)); addrman.Add(CAddress(addr, NODE_NONE), source); addrman.Good(addr); // No collisions yet. BOOST_CHECK(addrman.size() == i); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); } // Ensure Good handles duplicates well. for (unsigned int i = 1; i < 23; i++) { CService addr = ResolveService("250.1.1." + std::to_string(i)); addrman.Good(addr); BOOST_CHECK(addrman.size() == 22); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); } } BOOST_AUTO_TEST_CASE(addrman_noevict) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); // Add twenty two addresses. CNetAddr source = ResolveIP("252.2.2.2"); for (unsigned int i = 1; i < 23; i++) { CService addr = ResolveService("250.1.1." + std::to_string(i)); addrman.Add(CAddress(addr, NODE_NONE), source); addrman.Good(addr); // No collision yet. BOOST_CHECK(addrman.size() == i); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); } // Collision between 23 and 19. CService addr23 = ResolveService("250.1.1.23"); addrman.Add(CAddress(addr23, NODE_NONE), source); addrman.Good(addr23); BOOST_CHECK(addrman.size() == 23); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "250.1.1.19:0"); // 23 should be discarded and 19 not evicted. addrman.ResolveCollisions(); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); // Lets create two collisions. for (unsigned int i = 24; i < 33; i++) { CService addr = ResolveService("250.1.1." + std::to_string(i)); addrman.Add(CAddress(addr, NODE_NONE), source); addrman.Good(addr); BOOST_CHECK(addrman.size() == i); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); } // Cause a collision. CService addr33 = ResolveService("250.1.1.33"); addrman.Add(CAddress(addr33, NODE_NONE), source); addrman.Good(addr33); BOOST_CHECK(addrman.size() == 33); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "250.1.1.27:0"); // Cause a second collision. addrman.Add(CAddress(addr23, NODE_NONE), source); addrman.Good(addr23); BOOST_CHECK(addrman.size() == 33); BOOST_CHECK(addrman.SelectTriedCollision().ToString() != "[::]:0"); addrman.ResolveCollisions(); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); } BOOST_AUTO_TEST_CASE(addrman_evictionworks) { CAddrManTest addrman; // Set addrman addr placement to be deterministic. addrman.MakeDeterministic(); BOOST_CHECK(addrman.size() == 0); // Empty addrman should return blank addrman info. BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); // Add twenty two addresses. CNetAddr source = ResolveIP("252.2.2.2"); for (unsigned int i = 1; i < 23; i++) { CService addr = ResolveService("250.1.1." + std::to_string(i)); addrman.Add(CAddress(addr, NODE_NONE), source); addrman.Good(addr); // No collision yet. BOOST_CHECK(addrman.size() == i); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); } // Collision between 23 and 19. CService addr = ResolveService("250.1.1.23"); addrman.Add(CAddress(addr, NODE_NONE), source); addrman.Good(addr); BOOST_CHECK(addrman.size() == 23); CAddrInfo info = addrman.SelectTriedCollision(); BOOST_CHECK(info.ToString() == "250.1.1.19:0"); // Ensure test of address fails, so that it is evicted. addrman.SimConnFail(info); // Should swap 23 for 19. addrman.ResolveCollisions(); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); // If 23 was swapped for 19, then this should cause no collisions. addrman.Add(CAddress(addr, NODE_NONE), source); addrman.Good(addr); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); // If we insert 19 is should collide with 23. CService addr19 = ResolveService("250.1.1.19"); addrman.Add(CAddress(addr19, NODE_NONE), source); addrman.Good(addr19); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "250.1.1.23:0"); addrman.ResolveCollisions(); BOOST_CHECK(addrman.SelectTriedCollision().ToString() == "[::]:0"); } BOOST_AUTO_TEST_SUITE_END()