aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/addrman.cpp99
-rw-r--r--src/addrman.h43
-rw-r--r--src/net.cpp9
-rw-r--r--src/test/addrman_tests.cpp187
4 files changed, 319 insertions, 19 deletions
diff --git a/src/addrman.cpp b/src/addrman.cpp
index 9eefffb45b..9a7fad4900 100644
--- a/src/addrman.cpp
+++ b/src/addrman.cpp
@@ -187,7 +187,7 @@ void CAddrMan::MakeTried(CAddrInfo& info, int nId)
info.fInTried = true;
}
-void CAddrMan::Good_(const CService& addr, int64_t nTime)
+void CAddrMan::Good_(const CService& addr, bool test_before_evict, int64_t nTime)
{
int nId;
@@ -233,10 +233,22 @@ void CAddrMan::Good_(const CService& addr, int64_t nTime)
if (nUBucket == -1)
return;
- LogPrint(BCLog::ADDRMAN, "Moving %s to tried\n", addr.ToString());
+ // 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, "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);
+ // move nId to the tried tables
+ MakeTried(info, nId);
+ }
}
bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimePenalty)
@@ -521,3 +533,82 @@ void CAddrMan::SetServices_(const CService& addr, ServiceFlags nServices)
int CAddrMan::RandomInt(int nMax){
return GetRandInt(nMax);
}
+
+void CAddrMan::ResolveCollisions_()
+{
+ for (std::set<int>::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
+ if (mapInfo.count(id_new) != 1) {
+ erase_collision = true;
+ } else {
+ CAddrInfo& info_new = mapInfo[id_new];
+
+ // 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 (GetAdjustedTime() - info_old.nLastSuccess < ADDRMAN_REPLACEMENT_HOURS*(60*60)) {
+ erase_collision = true;
+ } else if (GetAdjustedTime() - info_old.nLastTry < ADDRMAN_REPLACEMENT_HOURS*(60*60)) { // 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, "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, GetAdjustedTime());
+ 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<int>::iterator it = m_tried_collisions.begin();
+
+ // Selects a random element from m_tried_collisions
+ std::advance(it, GetRandInt(m_tried_collisions.size()));
+ int id_new = *it;
+
+ // If id_new not found in mapInfo remove it from m_tried_collisions
+ if (mapInfo.count(id_new) != 1) {
+ m_tried_collisions.erase(it);
+ return CAddrInfo();
+ }
+
+ CAddrInfo& newInfo = mapInfo[id_new];
+
+ // 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 38da754afb..67423c6c55 100644
--- a/src/addrman.h
+++ b/src/addrman.h
@@ -165,6 +165,9 @@ public:
//! ... 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_HOURS 4
+
//! the maximum percentage of nodes to return in a getaddr call
#define ADDRMAN_GETADDR_MAX_PCT 23
@@ -176,6 +179,9 @@ public:
#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
*/
@@ -212,6 +218,9 @@ private:
//! last time Good was called (memory only)
int64_t nLastGood;
+ //! Holds addrs inserted into tried table that collide with existing entries. Test-before-evict discpline used to resolve these collisions.
+ std::set<int> m_tried_collisions;
+
protected:
//! secret key to randomize bucket select with
uint256 nKey;
@@ -239,7 +248,7 @@ protected:
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);
+ void Good_(const CService &addr, bool test_before_evict, int64_t time);
//! Add an entry to the "new" table.
bool Add_(const CAddress &addr, const CNetAddr& source, int64_t nTimePenalty);
@@ -250,6 +259,12 @@ protected:
//! Select an address to connect to, if newOnly is set to true, only the new table is selected from.
CAddrInfo Select_(bool newOnly);
+ //! See if any to-be-evicted tried table entries have been tested and if so resolve the collisions.
+ void ResolveCollisions_();
+
+ //! Return a random to-be-evicted tried table address.
+ CAddrInfo SelectTriedCollision_();
+
//! Wraps GetRandInt to allow tests to override RandomInt and make it determinismistic.
virtual int RandomInt(int nMax);
@@ -537,11 +552,11 @@ public:
}
//! Mark an entry as accessible.
- void Good(const CService &addr, int64_t nTime = GetAdjustedTime())
+ void Good(const CService &addr, bool test_before_evict = true, int64_t nTime = GetAdjustedTime())
{
LOCK(cs);
Check();
- Good_(addr, nTime);
+ Good_(addr, test_before_evict, nTime);
Check();
}
@@ -554,6 +569,28 @@ public:
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.
*/
diff --git a/src/net.cpp b/src/net.cpp
index c7c19f83a1..f7e6c300b1 100644
--- a/src/net.cpp
+++ b/src/net.cpp
@@ -1828,11 +1828,18 @@ void CConnman::ThreadOpenConnections(const std::vector<std::string> connect)
}
}
+ addrman.ResolveCollisions();
+
int64_t nANow = GetAdjustedTime();
int nTries = 0;
while (!interruptNet)
{
- CAddrInfo addr = addrman.Select(fFeeler);
+ CAddrInfo addr = addrman.SelectTriedCollision();
+
+ // SelectTriedCollision returns an invalid address if it is empty.
+ if (!fFeeler || !addr.IsValid()) {
+ addr = addrman.Select(fFeeler);
+ }
// if we selected an invalid address, restart
if (!addr.IsValid() || setConnected.count(addr.GetGroup()) || IsLocal(addr))
diff --git a/src/test/addrman_tests.cpp b/src/test/addrman_tests.cpp
index b338d6d366..0d8bd90119 100644
--- a/src/test/addrman_tests.cpp
+++ b/src/test/addrman_tests.cpp
@@ -52,6 +52,17 @@ public:
{
CAddrMan::Delete(nId);
}
+
+ // Simulates connection failure so that we can test eviction of offline nodes
+ void SimConnFail(CService& addr)
+ {
+ int64_t nLastSuccess = 1;
+ Good_(addr, true, nLastSuccess); // Set last good connection in the deep past.
+
+ bool count_failure = false;
+ int64_t nLastTry = GetAdjustedTime()-61;
+ Attempt(addr, count_failure, nLastTry);
+ }
};
static CNetAddr ResolveIP(const char* ip)
@@ -226,7 +237,7 @@ BOOST_AUTO_TEST_CASE(addrman_new_collisions)
BOOST_CHECK_EQUAL(addrman.size(), 0);
for (unsigned int i = 1; i < 18; i++) {
- CService addr = ResolveService("250.1.1." + boost::to_string(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.
@@ -252,7 +263,7 @@ BOOST_AUTO_TEST_CASE(addrman_tried_collisions)
BOOST_CHECK_EQUAL(addrman.size(), 0);
for (unsigned int i = 1; i < 80; i++) {
- CService addr = ResolveService("250.1.1." + boost::to_string(i));
+ CService addr = ResolveService("250.1.1." + std::to_string(i));
addrman.Add(CAddress(addr, NODE_NONE), source);
addrman.Good(CAddress(addr, NODE_NONE));
@@ -385,7 +396,7 @@ BOOST_AUTO_TEST_CASE(addrman_getaddr)
for (unsigned int i = 1; i < (8 * 256); i++) {
int octet1 = i % 256;
int octet2 = i >> 8 % 256;
- std::string strAddr = boost::to_string(octet1) + "." + boost::to_string(octet2) + ".1.23";
+ 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.
@@ -436,8 +447,8 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_tried_bucket)
std::set<int> buckets;
for (int i = 0; i < 255; i++) {
CAddrInfo infoi = CAddrInfo(
- CAddress(ResolveService("250.1.1." + boost::to_string(i)), NODE_NONE),
- ResolveIP("250.1.1." + boost::to_string(i)));
+ 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);
}
@@ -448,8 +459,8 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_tried_bucket)
buckets.clear();
for (int j = 0; j < 255; j++) {
CAddrInfo infoj = CAddrInfo(
- CAddress(ResolveService("250." + boost::to_string(j) + ".1.1"), NODE_NONE),
- ResolveIP("250." + boost::to_string(j) + ".1.1"));
+ 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);
}
@@ -488,8 +499,8 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_new_bucket)
std::set<int> buckets;
for (int i = 0; i < 255; i++) {
CAddrInfo infoi = CAddrInfo(
- CAddress(ResolveService("250.1.1." + boost::to_string(i)), NODE_NONE),
- ResolveIP("250.1.1." + boost::to_string(i)));
+ 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);
}
@@ -501,7 +512,7 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_new_bucket)
for (int j = 0; j < 4 * 255; j++) {
CAddrInfo infoj = CAddrInfo(CAddress(
ResolveService(
- boost::to_string(250 + (j / 255)) + "." + boost::to_string(j % 256) + ".1.1"), NODE_NONE),
+ 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);
@@ -514,7 +525,7 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_new_bucket)
for (int p = 0; p < 255; p++) {
CAddrInfo infoj = CAddrInfo(
CAddress(ResolveService("250.1.1.1"), NODE_NONE),
- ResolveIP("250." + boost::to_string(p) + ".1.1"));
+ ResolveIP("250." + std::to_string(p) + ".1.1"));
int bucket = infoj.GetNewBucket(nKey1);
buckets.insert(bucket);
}
@@ -522,4 +533,158 @@ BOOST_AUTO_TEST_CASE(caddrinfo_get_new_bucket)
// 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()
generated by cgit v1.2.3 (git 2.26.2) at 2024-07-02 21:41:28 +0000