Merge pull request #5941

1d21ba2 Scale up addrman (Pieter Wuille)
c6a63ce Always use a 50% chance to choose between tried and new entries (Pieter Wuille)
f68ba3f Do not bias outgoing connections towards fresh addresses (Pieter Wuille)
a8ff7c6 Simplify hashing code (Pieter Wuille)
e6b343d Make addrman's bucket placement deterministic. (Pieter Wuille)
b23add5 Switch addrman key from vector to uint256 (Pieter Wuille)

1 files changed, 128 insertions, 167 deletions

diff --git a/src/addrman.cpp b/src/addrman.cpp
index 4b7e4d51b..5d9527f0e 100644
--- a/src/addrman.cpp
+++ b/src/addrman.cpp
@@ -10,34 +10,27 @@
 
 using namespace std;
 
-int CAddrInfo::GetTriedBucket(const std::vector<unsigned char>& nKey) const
+int CAddrInfo::GetTriedBucket(const uint256& nKey) const
 {
-    CDataStream ss1(SER_GETHASH, 0);
-    std::vector<unsigned char> vchKey = GetKey();
-    ss1 << nKey << vchKey;
-    uint64_t hash1 = Hash(ss1.begin(), ss1.end()).GetCheapHash();
-
-    CDataStream ss2(SER_GETHASH, 0);
-    std::vector<unsigned char> vchGroupKey = GetGroup();
-    ss2 << nKey << vchGroupKey << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP);
-    uint64_t hash2 = Hash(ss2.begin(), ss2.end()).GetCheapHash();
+    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 std::vector<unsigned char>& nKey, const CNetAddr& src) const
+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 << nKey << vchGroupKey << vchSourceGroupKey;
-    uint64_t hash1 = Hash(ss1.begin(), ss1.end()).GetCheapHash();
-
-    CDataStream ss2(SER_GETHASH, 0);
-    ss2 << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP);
-    uint64_t hash2 = Hash(ss2.begin(), ss2.end()).GetCheapHash();
+    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
 {
     if (nLastTry && nLastTry >= nNow - 60) // never remove things tried in the last minute
@@ -70,8 +63,6 @@ double CAddrInfo::GetChance(int64_t nNow) const
     if (nSinceLastTry < 0)
         nSinceLastTry = 0;
 
-    fChance *= 600.0 / (600.0 + nSinceLastSeen);
-
     // deprioritize very recent attempts away
     if (nSinceLastTry < 60 * 10)
         fChance *= 0.01;
@@ -128,85 +119,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 +164,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 +223,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 +242,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 +290,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;
 }
@@ -377,24 +332,23 @@ void CAddrMan::Attempt_(const CService& addr, int64_t nTime)
     info.nAttempts++;
 }
 
-CAddress CAddrMan::Select_(int nUnkBias)
+CAddress CAddrMan::Select_()
 {
     if (size() == 0)
         return CAddress();
 
-    double nCorTried = sqrt(nTried) * (100.0 - nUnkBias);
-    double nCorNew = sqrt(nNew) * nUnkBias;
-    if ((nCorTried + nCorNew) * GetRandInt(1 << 30) / (1 << 30) < nCorTried) {
+    // Use a 50% chance for choosing between tried and new table entries.
+    if (nTried > 0 && (nNew == 0 || GetRandInt(2) == 0)) {
         // 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 +357,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 +411,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]);
+            }
         }
     }
 
@@ -483,6 +442,8 @@ int CAddrMan::Check_()
         return -13;
     if (mapNew.size())
         return -15;
+    if (nKey.IsNull())
+        return -16;
 
     return 0;
 }