diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/addrman.cpp | 270 | ||||
| -rw-r--r-- | src/addrman.h | 167 |
2 files changed, 231 insertions, 206 deletions
diff --git a/src/addrman.cpp b/src/addrman.cpp index 0c09a24470..8310f0fe70 100644 --- a/src/addrman.cpp +++ b/src/addrman.cpp @@ -14,12 +14,12 @@ int CAddrInfo::GetTriedBucket(const uint256& nKey) const { CDataStream ss1(SER_GETHASH, 0); std::vector<unsigned char> vchKey = GetKey(); - ss1 << ((unsigned char)32) << nKey << vchKey; + ss1 << nKey << vchKey; uint64_t hash1 = Hash(ss1.begin(), ss1.end()).GetCheapHash(); CDataStream ss2(SER_GETHASH, 0); std::vector<unsigned char> vchGroupKey = GetGroup(); - ss2 << ((unsigned char)32) << nKey << vchGroupKey << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP); + ss2 << nKey << vchGroupKey << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP); uint64_t hash2 = Hash(ss2.begin(), ss2.end()).GetCheapHash(); return hash2 % ADDRMAN_TRIED_BUCKET_COUNT; } @@ -29,15 +29,24 @@ int CAddrInfo::GetNewBucket(const uint256& nKey, const CNetAddr& src) const CDataStream ss1(SER_GETHASH, 0); std::vector<unsigned char> vchGroupKey = GetGroup(); std::vector<unsigned char> vchSourceGroupKey = src.GetGroup(); - ss1 << ((unsigned char)32) << nKey << vchGroupKey << vchSourceGroupKey; + ss1 << nKey << vchGroupKey << vchSourceGroupKey; uint64_t hash1 = Hash(ss1.begin(), ss1.end()).GetCheapHash(); CDataStream ss2(SER_GETHASH, 0); - ss2 << ((unsigned char)32) << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP); + ss2 << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP); uint64_t hash2 = Hash(ss2.begin(), ss2.end()).GetCheapHash(); return hash2 % ADDRMAN_NEW_BUCKET_COUNT; } +int CAddrInfo::GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const +{ + CDataStream ss1(SER_GETHASH, 0); + std::vector<unsigned char> vchKey = GetKey(); + ss1 << nKey << (fNew ? 'N' : 'K') << nBucket << vchKey; + uint64_t hash1 = Hash(ss1.begin(), ss1.end()).GetCheapHash(); + return hash1 % ADDRMAN_BUCKET_SIZE; +} + bool CAddrInfo::IsTerrible(int64_t nNow) const { if (nLastTry && nLastTry >= nNow - 60) // never remove things tried in the last minute @@ -128,85 +137,44 @@ void CAddrMan::SwapRandom(unsigned int nRndPos1, unsigned int nRndPos2) vRandom[nRndPos2] = nId1; } -int CAddrMan::SelectTried(int nKBucket) +void CAddrMan::Delete(int nId) { - std::vector<int>& vTried = vvTried[nKBucket]; - - // randomly shuffle the first few elements (using the entire list) - // find the least recently tried among them - int64_t nOldest = -1; - int nOldestPos = -1; - for (unsigned int i = 0; i < ADDRMAN_TRIED_ENTRIES_INSPECT_ON_EVICT && i < vTried.size(); i++) { - int nPos = GetRandInt(vTried.size() - i) + i; - int nTemp = vTried[nPos]; - vTried[nPos] = vTried[i]; - vTried[i] = nTemp; - assert(nOldest == -1 || mapInfo.count(nTemp) == 1); - if (nOldest == -1 || mapInfo[nTemp].nLastSuccess < mapInfo[nOldest].nLastSuccess) { - nOldest = nTemp; - nOldestPos = nPos; - } - } + assert(mapInfo.count(nId) != 0); + CAddrInfo& info = mapInfo[nId]; + assert(!info.fInTried); + assert(info.nRefCount == 0); - return nOldestPos; + SwapRandom(info.nRandomPos, vRandom.size() - 1); + vRandom.pop_back(); + mapAddr.erase(info); + mapInfo.erase(nId); + nNew--; } -int CAddrMan::ShrinkNew(int nUBucket) +void CAddrMan::ClearNew(int nUBucket, int nUBucketPos) { - assert(nUBucket >= 0 && (unsigned int)nUBucket < vvNew.size()); - std::set<int>& vNew = vvNew[nUBucket]; - - // first look for deletable items - for (std::set<int>::iterator it = vNew.begin(); it != vNew.end(); it++) { - assert(mapInfo.count(*it)); - CAddrInfo& info = mapInfo[*it]; - if (info.IsTerrible()) { - if (--info.nRefCount == 0) { - SwapRandom(info.nRandomPos, vRandom.size() - 1); - vRandom.pop_back(); - mapAddr.erase(info); - mapInfo.erase(*it); - nNew--; - } - vNew.erase(it); - return 0; - } - } - - // otherwise, select four randomly, and pick the oldest of those to replace - int n[4] = {GetRandInt(vNew.size()), GetRandInt(vNew.size()), GetRandInt(vNew.size()), GetRandInt(vNew.size())}; - int nI = 0; - int nOldest = -1; - for (std::set<int>::iterator it = vNew.begin(); it != vNew.end(); it++) { - if (nI == n[0] || nI == n[1] || nI == n[2] || nI == n[3]) { - assert(nOldest == -1 || mapInfo.count(*it) == 1); - if (nOldest == -1 || mapInfo[*it].nTime < mapInfo[nOldest].nTime) - nOldest = *it; + // 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); } - nI++; - } - assert(mapInfo.count(nOldest) == 1); - CAddrInfo& info = mapInfo[nOldest]; - if (--info.nRefCount == 0) { - SwapRandom(info.nRandomPos, vRandom.size() - 1); - vRandom.pop_back(); - mapAddr.erase(info); - mapInfo.erase(nOldest); - nNew--; } - vNew.erase(nOldest); - - return 1; } -void CAddrMan::MakeTried(CAddrInfo& info, int nId, int nOrigin) +void CAddrMan::MakeTried(CAddrInfo& info, int nId) { - assert(vvNew[nOrigin].count(nId) == 1); - // remove the entry from all new buckets - for (std::vector<std::set<int> >::iterator it = vvNew.begin(); it != vvNew.end(); it++) { - if ((*it).erase(nId)) + 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--; @@ -214,44 +182,36 @@ void CAddrMan::MakeTried(CAddrInfo& info, int nId, int nOrigin) // which tried bucket to move the entry to int nKBucket = info.GetTriedBucket(nKey); - std::vector<int>& vTried = vvTried[nKBucket]; - - // first check whether there is place to just add it - if (vTried.size() < ADDRMAN_TRIED_BUCKET_SIZE) { - vTried.push_back(nId); - nTried++; - info.fInTried = true; - return; - } - - // otherwise, find an item to evict - int nPos = SelectTried(nKBucket); - - // find which new bucket it belongs to - assert(mapInfo.count(vTried[nPos]) == 1); - int nUBucket = mapInfo[vTried[nPos]].GetNewBucket(nKey); - std::set<int>& vNew = vvNew[nUBucket]; - - // remove the to-be-replaced tried entry from the tried set - CAddrInfo& infoOld = mapInfo[vTried[nPos]]; - infoOld.fInTried = false; - infoOld.nRefCount = 1; - // do not update nTried, as we are going to move something else there immediately - - // check whether there is place in that one, - if (vNew.size() < ADDRMAN_NEW_BUCKET_SIZE) { - // if so, move it back there - vNew.insert(vTried[nPos]); - } else { - // otherwise, move it to the new bucket nId came from (there is certainly place there) - vvNew[nOrigin].insert(vTried[nPos]); + 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++; } - nNew++; + assert(vvTried[nKBucket][nKBucketPos] == -1); - vTried[nPos] = nId; - // we just overwrote an entry in vTried; no need to update nTried + vvTried[nKBucket][nKBucketPos] = nId; + nTried++; info.fInTried = true; - return; } void CAddrMan::Good_(const CService& addr, int64_t nTime) @@ -281,12 +241,12 @@ void CAddrMan::Good_(const CService& addr, int64_t nTime) return; // find a bucket it is in now - int nRnd = GetRandInt(vvNew.size()); + int nRnd = GetRandInt(ADDRMAN_NEW_BUCKET_COUNT); int nUBucket = -1; - for (unsigned int n = 0; n < vvNew.size(); n++) { - int nB = (n + nRnd) % vvNew.size(); - std::set<int>& vNew = vvNew[nB]; - if (vNew.count(nId)) { + 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; } @@ -300,7 +260,7 @@ void CAddrMan::Good_(const CService& addr, int64_t nTime) LogPrint("addrman", "Moving %s to tried\n", addr.ToString()); // move nId to the tried tables - MakeTried(info, nId, nUBucket); + MakeTried(info, nId); } bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimePenalty) @@ -348,12 +308,25 @@ bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimeP } int nUBucket = pinfo->GetNewBucket(nKey, source); - std::set<int>& vNew = vvNew[nUBucket]; - if (!vNew.count(nId)) { - pinfo->nRefCount++; - if (vNew.size() == ADDRMAN_NEW_BUCKET_SIZE) - ShrinkNew(nUBucket); - vvNew[nUBucket].insert(nId); + 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; } @@ -388,13 +361,13 @@ CAddress CAddrMan::Select_(int nUnkBias) // use a tried node double fChanceFactor = 1.0; while (1) { - int nKBucket = GetRandInt(vvTried.size()); - std::vector<int>& vTried = vvTried[nKBucket]; - if (vTried.size() == 0) + int nKBucket = GetRandInt(ADDRMAN_TRIED_BUCKET_COUNT); + int nKBucketPos = GetRandInt(ADDRMAN_BUCKET_SIZE); + if (vvTried[nKBucket][nKBucketPos] == -1) continue; - int nPos = GetRandInt(vTried.size()); - assert(mapInfo.count(vTried[nPos]) == 1); - CAddrInfo& info = mapInfo[vTried[nPos]]; + int nId = vvTried[nKBucket][nKBucketPos]; + assert(mapInfo.count(nId) == 1); + CAddrInfo& info = mapInfo[nId]; if (GetRandInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30)) return info; fChanceFactor *= 1.2; @@ -403,16 +376,13 @@ CAddress CAddrMan::Select_(int nUnkBias) // use a new node double fChanceFactor = 1.0; while (1) { - int nUBucket = GetRandInt(vvNew.size()); - std::set<int>& vNew = vvNew[nUBucket]; - if (vNew.size() == 0) + int nUBucket = GetRandInt(ADDRMAN_NEW_BUCKET_COUNT); + int nUBucketPos = GetRandInt(ADDRMAN_BUCKET_SIZE); + if (vvNew[nUBucket][nUBucketPos] == -1) continue; - int nPos = GetRandInt(vNew.size()); - std::set<int>::iterator it = vNew.begin(); - while (nPos--) - it++; - assert(mapInfo.count(*it) == 1); - CAddrInfo& info = mapInfo[*it]; + int nId = vvNew[nUBucket][nUBucketPos]; + assert(mapInfo.count(nId) == 1); + CAddrInfo& info = mapInfo[nId]; if (GetRandInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30)) return info; fChanceFactor *= 1.2; @@ -460,22 +430,30 @@ int CAddrMan::Check_() if (mapNew.size() != nNew) return -10; - for (int n = 0; n < vvTried.size(); n++) { - std::vector<int>& vTried = vvTried[n]; - for (std::vector<int>::iterator it = vTried.begin(); it != vTried.end(); it++) { - if (!setTried.count(*it)) - return -11; - setTried.erase(*it); + 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 < vvNew.size(); n++) { - std::set<int>& vNew = vvNew[n]; - for (std::set<int>::iterator it = vNew.begin(); it != vNew.end(); it++) { - if (!mapNew.count(*it)) - return -12; - if (--mapNew[*it] == 0) - mapNew.erase(*it); + 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]); + } } } diff --git a/src/addrman.h b/src/addrman.h index 04c7b32eaf..f7c6318448 100644 --- a/src/addrman.h +++ b/src/addrman.h @@ -10,7 +10,6 @@ #include "random.h" #include "sync.h" #include "timedata.h" -#include "uint256.h" #include "util.h" #include <map> @@ -91,6 +90,9 @@ public: 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; @@ -128,14 +130,11 @@ public: //! total number of buckets for tried addresses #define ADDRMAN_TRIED_BUCKET_COUNT 64 -//! maximum allowed number of entries in buckets for tried addresses -#define ADDRMAN_TRIED_BUCKET_SIZE 64 - //! total number of buckets for new addresses #define ADDRMAN_NEW_BUCKET_COUNT 256 -//! maximum allowed number of entries in buckets for new addresses -#define ADDRMAN_NEW_BUCKET_SIZE 64 +//! maximum allowed number of entries in buckets for new and tried addresses +#define ADDRMAN_BUCKET_SIZE 64 //! over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread #define ADDRMAN_TRIED_BUCKETS_PER_GROUP 4 @@ -146,9 +145,6 @@ public: //! in how many buckets for entries with new addresses a single address may occur #define ADDRMAN_NEW_BUCKETS_PER_ADDRESS 4 -//! how many entries in a bucket with tried addresses are inspected, when selecting one to replace -#define ADDRMAN_TRIED_ENTRIES_INSPECT_ON_EVICT 4 - //! how old addresses can maximally be #define ADDRMAN_HORIZON_DAYS 30 @@ -195,13 +191,13 @@ private: int nTried; //! list of "tried" buckets - std::vector<std::vector<int> > vvTried; + int vvTried[ADDRMAN_TRIED_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE]; //! number of (unique) "new" entries int nNew; //! list of "new" buckets - std::vector<std::set<int> > vvNew; + int vvNew[ADDRMAN_NEW_BUCKET_COUNT][ADDRMAN_BUCKET_SIZE]; protected: @@ -215,17 +211,14 @@ protected: //! Swap two elements in vRandom. void SwapRandom(unsigned int nRandomPos1, unsigned int nRandomPos2); - //! Return position in given bucket to replace. - int SelectTried(int nKBucket); + //! Move an entry from the "new" table(s) to the "tried" table + void MakeTried(CAddrInfo& info, int nId); - //! Remove an element from a "new" bucket. - //! This is the only place where actual deletions occur. - //! Elements are never deleted while in the "tried" table, only possibly evicted back to the "new" table. - int ShrinkNew(int nUBucket); + //! Delete an entry. It must not be in tried, and have refcount 0. + void Delete(int nId); - //! Move an entry from the "new" table(s) to the "tried" table - //! @pre vvUnkown[nOrigin].count(nId) != 0 - void MakeTried(CAddrInfo& info, int nId, int nOrigin); + //! 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, int64_t nTime); @@ -254,17 +247,21 @@ protected: public: /** * serialized format: - * * version byte (currently 0) - * * nKey + * * version byte (currently 1) + * * 0x20 + nKey (serialized as if it were a vector, for backward compatibility) * * nNew * * nTried - * * number of "new" buckets + * * 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. * @@ -276,49 +273,53 @@ public: * * We don't use ADD_SERIALIZE_METHODS since the serialization and deserialization code has * very little in common. - * */ template<typename Stream> void Serialize(Stream &s, int nType, int nVersionDummy) const { LOCK(cs); - unsigned char nVersion = 0; + unsigned char nVersion = 1; s << nVersion; s << ((unsigned char)32); s << nKey; s << nNew; s << nTried; - int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT; + int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT ^ (1 << 30); s << nUBuckets; std::map<int, int> mapUnkIds; int nIds = 0; for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); it++) { - if (nIds == nNew) break; // this means nNew was wrong, oh ow mapUnkIds[(*it).first] = nIds; const CAddrInfo &info = (*it).second; if (info.nRefCount) { + assert(nIds != nNew); // this means nNew was wrong, oh ow s << info; nIds++; } } nIds = 0; for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); it++) { - if (nIds == nTried) break; // this means nTried was wrong, oh ow const CAddrInfo &info = (*it).second; if (info.fInTried) { + assert(nIds != nTried); // this means nTried was wrong, oh ow s << info; nIds++; } } - for (std::vector<std::set<int> >::const_iterator it = vvNew.begin(); it != vvNew.end(); it++) { - const std::set<int> &vNew = (*it); - int nSize = vNew.size(); + 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 (std::set<int>::const_iterator it2 = vNew.begin(); it2 != vNew.end(); it2++) { - int nIndex = mapUnkIds[*it2]; - s << nIndex; + for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) { + if (vvNew[bucket][i] != -1) { + int nIndex = mapUnkIds[vvNew[bucket][i]]; + s << nIndex; + } } } } @@ -328,67 +329,97 @@ public: { LOCK(cs); + Clear(); + unsigned char nVersion; s >> nVersion; unsigned char nKeySize; s >> nKeySize; - if (nKeySize != 32) throw std::ios_base::failure("Incorrect keysize in addrman"); + if (nKeySize != 32) throw std::ios_base::failure("Incorrect keysize in addrman deserialization"); s >> nKey; s >> nNew; s >> nTried; - int nUBuckets = 0; s >> nUBuckets; - nIdCount = 0; - mapInfo.clear(); - mapAddr.clear(); - vRandom.clear(); - vvTried = std::vector<std::vector<int> >(ADDRMAN_TRIED_BUCKET_COUNT, std::vector<int>(0)); - vvNew = std::vector<std::set<int> >(ADDRMAN_NEW_BUCKET_COUNT, std::set<int>()); + if (nVersion != 0) { + nUBuckets ^= (1 << 30); + } + + // 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 (nUBuckets != ADDRMAN_NEW_BUCKET_COUNT) { - vvNew[info.GetNewBucket(nKey)].insert(n); - info.nRefCount++; + 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; - std::vector<int> &vTried = vvTried[info.GetTriedBucket(nKey)]; - if (vTried.size() < ADDRMAN_TRIED_BUCKET_SIZE) { + 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; - vTried.push_back(nIdCount); + vvTried[nKBucket][nKBucketPos] = nIdCount; nIdCount++; } else { nLost++; } } nTried -= nLost; - for (int b = 0; b < nUBuckets; b++) { - std::set<int> &vNew = vvNew[b]; + + // 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; - CAddrInfo &info = mapInfo[nIndex]; - if (nUBuckets == ADDRMAN_NEW_BUCKET_COUNT && info.nRefCount < ADDRMAN_NEW_BUCKETS_PER_ADDRESS) { - info.nRefCount++; - vNew.insert(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<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); ) { + if (it->second.fInTried == false && it->second.nRefCount == 0) { + std::map<int, CAddrInfo>::const_iterator itCopy = it++; + Delete(itCopy->first); + nLostUnk++; + } else { + it++; + } + } + if (nLost + nLostUnk > 0) { + LogPrint("addrman", "addrman lost %i new and %i tried addresses due to collisions\n", nLostUnk, nLost); + } + + Check(); } unsigned int GetSerializeSize(int nType, int nVersion) const @@ -396,18 +427,34 @@ public: return (CSizeComputer(nType, nVersion) << *this).size(); } - CAddrMan() : vRandom(0), vvTried(ADDRMAN_TRIED_BUCKET_COUNT, std::vector<int>(0)), vvNew(ADDRMAN_NEW_BUCKET_COUNT, std::set<int>()) + void Clear() { - nKey = GetRandHash(); + std::vector<int>().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; + nIdCount = 0; + nTried = 0; + nNew = 0; + } + + CAddrMan() + { + Clear(); } ~CAddrMan() { - nKey.SetNull(); + nKey.SetNull(); } //! Return the number of (unique) addresses in all tables. |