From: Pieter Wuille Date: Wed, 4 Jan 2012 22:39:45 +0000 (+0100) Subject: CAddrMan: stochastic address manager X-Git-Tag: v0.4.0-unstable~129^2~139^2 X-Git-Url: https://git.novaco.in/?p=novacoin.git;a=commitdiff_plain;h=5fee401fe14aa6459428a26a82f764db70a6a0b9 CAddrMan: stochastic address manager Design goals: * Only keep a limited number of addresses around, so that addr.dat does not grow without bound. * Keep the address tables in-memory, and occasionally write the table to addr.dat. * Make sure no (localized) attacker can fill the entire table with his nodes/addresses. See comments in addrman.h for more detailed information. --- diff --git a/bitcoin-qt.pro b/bitcoin-qt.pro index 933f4a7..8cecc45 100644 --- a/bitcoin-qt.pro +++ b/bitcoin-qt.pro @@ -101,6 +101,7 @@ HEADERS += src/qt/bitcoingui.h \ src/qt/aboutdialog.h \ src/qt/editaddressdialog.h \ src/qt/bitcoinaddressvalidator.h \ + src/addrman.h \ src/base58.h \ src/bignum.h \ src/checkpoints.h \ @@ -174,6 +175,7 @@ SOURCES += src/qt/bitcoin.cpp src/qt/bitcoingui.cpp \ src/net.cpp \ src/irc.cpp \ src/checkpoints.cpp \ + src/addrman.cpp \ src/db.cpp \ src/json/json_spirit_writer.cpp \ src/json/json_spirit_value.cpp \ diff --git a/src/addrman.cpp b/src/addrman.cpp new file mode 100644 index 0000000..2ef666c --- /dev/null +++ b/src/addrman.cpp @@ -0,0 +1,506 @@ +// Copyright (c) 2012 Pieter Wuille +// Distributed under the MIT/X11 software license, see the accompanying +// file license.txt or http://www.opensource.org/licenses/mit-license.php. + +#include "addrman.h" + +using namespace std; + +int CAddrInfo::GetTriedBucket(const std::vector &nKey) const +{ + CDataStream ss1(SER_GETHASH); + std::vector vchKey = GetKey(); + ss1 << nKey << vchKey; + uint64 hash1 = Hash(ss1.begin(), ss1.end()).Get64(); + + CDataStream ss2(SER_GETHASH); + std::vector vchGroupKey = GetGroup(); + ss2 << nKey << vchGroupKey << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP); + uint64 hash2 = Hash(ss2.begin(), ss2.end()).Get64(); + return hash2 % ADDRMAN_TRIED_BUCKET_COUNT; +} + +int CAddrInfo::GetNewBucket(const std::vector &nKey, const CNetAddr& src) const +{ + CDataStream ss1(SER_GETHASH); + std::vector vchGroupKey = GetGroup(); + std::vector vchSourceGroupKey = src.GetGroup(); + ss1 << nKey << vchGroupKey << vchSourceGroupKey; + uint64 hash1 = Hash(ss1.begin(), ss1.end()).Get64(); + + CDataStream ss2(SER_GETHASH); + ss2 << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP); + uint64 hash2 = Hash(ss2.begin(), ss2.end()).Get64(); + return hash2 % ADDRMAN_NEW_BUCKET_COUNT; +} + +bool CAddrInfo::IsTerrible(int64 nNow) const +{ + if (nLastTry && nLastTry >= nNow-60) // never remove things tried the last minute + return false; + + if (nTime > nNow + 10*60) // came in a flying DeLorean + return true; + + if (nTime==0 || nNow-nTime > ADDRMAN_HORIZON_DAYS*86400) // not seen in over a month + return true; + + if (nLastSuccess==0 && nAttempts>=ADDRMAN_RETRIES) // tried three times and never a success + return true; + + if (nNow-nLastSuccess > ADDRMAN_MIN_FAIL_DAYS*86400 && nAttempts>=ADDRMAN_MAX_FAILURES) // 10 successive failures in the last week + return true; + + return false; +} + +double CAddrInfo::GetChance(int64 nNow) const +{ + double fChance = 1.0; + + int64 nSinceLastSeen = nNow - nTime; + int64 nSinceLastTry = nNow - nLastTry; + + if (nSinceLastSeen < 0) nSinceLastSeen = 0; + if (nSinceLastTry < 0) nSinceLastTry = 0; + + fChance *= 600.0 / (600.0 + nSinceLastSeen); + + // deprioritize very recent attempts away + if (nSinceLastTry < 60*10) + fChance *= 0.01; + + // deprioritize 50% after each failed attempt + for (int n=0; n::iterator it = mapAddr.find(addr); + if (it == mapAddr.end()) + return NULL; + if (pnId) + *pnId = (*it).second; + std::map::iterator it2 = mapInfo.find((*it).second); + if (it2 != mapInfo.end()) + return &(*it2).second; + return NULL; +} + +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(int nRndPos1, int nRndPos2) +{ + if (nRndPos1 == nRndPos2) + return; + + int nId1 = vRandom[nRndPos1]; + int nId2 = vRandom[nRndPos2]; + + mapInfo[nId1].nRandomPos = nRndPos2; + mapInfo[nId2].nRandomPos = nRndPos1; + + vRandom[nRndPos1] = nId2; + vRandom[nRndPos2] = nId1; +} + +int CAddrMan::SelectTried(int nKBucket) +{ + std::vector &vTried = vvTried[nKBucket]; + + // random shuffle the first few elements (using the entire list) + // find the least recently tried among them + int64 nOldest = -1; + for (int i=0; i &vNew = vvNew[nUBucket]; + + // first look for deletable items + for (std::set::iterator it = vNew.begin(); it != vNew.end(); 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::iterator it = vNew.begin(); it != vNew.end(); it++) + { + if (nI == n[0] || nI == n[1] || nI == n[2] || nI == n[3]) + { + if (nOldest == -1 || mapInfo[*it].nTime < mapInfo[nOldest].nTime) + nOldest = *it; + } + nI++; + } + 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) +{ + // remove the entry from all new buckets + for (std::vector >::iterator it = vvNew.begin(); it != vvNew.end(); it++) + { + if ((*it).erase(nId)) + info.nRefCount--; + } + nNew--; + + // what tried bucket to move the entry to + int nKBucket = info.GetTriedBucket(nKey); + std::vector &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 + int nUBucket = mapInfo[vTried[nPos]].GetNewBucket(nKey); + std::set &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]); + } + nNew++; + + vTried[nPos] = nId; + // we just overwrote an entry in vTried; no need to update nTried + info.fInTried = true; + return; +} + +void CAddrMan::Good_(const CService &addr, int64 nTime) +{ +// printf("Good: addr=%s\n", addr.ToString().c_str()); + + int nId; + 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.nTime = nTime; + info.nAttempts = 0; + + // 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 = GetRandInt(vvNew.size()); + int nUBucket = -1; + for (int n = 0; n < vvNew.size(); n++) + { + int nB = (n+nRnd) % vvNew.size(); + std::set &vNew = vvNew[nB]; + if (vNew.count(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; + + printf("Moving %s to tried\n", addr.ToString().c_str()); + + // move nId to the tried tables + MakeTried(info, nId, nUBucket); +} + +bool CAddrMan::Add_(const CAddress &addr, const CNetAddr& source, int64 nTimePenalty) +{ + if (!addr.IsRoutable()) + return false; + + bool fNew = false; + int nId; + CAddrInfo *pinfo = Find(addr, &nId); + + if (pinfo) + { + // periodically update nTime + bool fCurrentlyOnline = (GetAdjustedTime() - addr.nTime < 24 * 60 * 60); + int64 nUpdateInterval = (fCurrentlyOnline ? 60 * 60 : 24 * 60 * 60); + if (addr.nTime && (!pinfo->nTime || pinfo->nTime < addr.nTime - nUpdateInterval - nTimePenalty)) + pinfo->nTime = max((int64)0, addr.nTime - nTimePenalty); + + // add services + 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; nnRefCount; n++) + nFactor *= 2; + if (nFactor > 1 && (GetRandInt(nFactor) != 0)) + return false; + } else { + pinfo = Create(addr, source, &nId); + pinfo->nTime = max((int64)0, (int64)pinfo->nTime - nTimePenalty); +// printf("Added %s [nTime=%fhr]\n", pinfo->ToString().c_str(), (GetAdjustedTime() - pinfo->nTime) / 3600.0); + nNew++; + fNew = true; + } + + int nUBucket = pinfo->GetNewBucket(nKey, source); + std::set &vNew = vvNew[nUBucket]; + if (!vNew.count(nId)) + { + pinfo->nRefCount++; + if (vNew.size() == ADDRMAN_NEW_BUCKET_SIZE) + ShrinkNew(nUBucket); + vvNew[nUBucket].insert(nId); + } + return fNew; +} + +void CAddrMan::Attempt_(const CService &addr, int64 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; + info.nAttempts++; +} + +CAddress CAddrMan::Select_(int nUnkBias) +{ + 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 tried node + double fChanceFactor = 1.0; + while(1) + { + int nKBucket = GetRandInt(vvTried.size()); + std::vector &vTried = vvTried[nKBucket]; + if (vTried.size() == 0) continue; + int nPos = GetRandInt(vTried.size()); + CAddrInfo &info = mapInfo[vTried[nPos]]; + if (GetRandInt(1<<30) < fChanceFactor*info.GetChance()*(1<<30)) + return info; + fChanceFactor *= 1.2; + } + } else { + // use an new node + double fChanceFactor = 1.0; + while(1) + { + int nUBucket = GetRandInt(vvNew.size()); + std::set &vNew = vvNew[nUBucket]; + if (vNew.size() == 0) continue; + int nPos = GetRandInt(vNew.size()); + std::set::iterator it = vNew.begin(); + while (nPos--) + it++; + CAddrInfo &info = mapInfo[*it]; + if (GetRandInt(1<<30) < fChanceFactor*info.GetChance()*(1<<30)) + return info; + fChanceFactor *= 1.2; + } + } +} + +#ifdef DEBUG_ADDRMAN +int CAddrMan::Check_() +{ + std::set setTried; + std::map mapNew; + + if (vRandom.size() != nTried + nNew) return -7; + + for (std::map::iterator it = mapInfo.begin(); it != mapInfo.end(); it++) + { + int n = (*it).first; + CAddrInfo &info = (*it).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 &vTried = vvTried[n]; + for (std::vector::iterator it = vTried.begin(); it != vTried.end(); it++) + { + if (!setTried.count(*it)) return -11; + setTried.erase(*it); + } + } + + for (int n=0; n &vNew = vvNew[n]; + for (std::set::iterator it = vNew.begin(); it != vNew.end(); it++) + { + if (!mapNew.count(*it)) return -12; + if (--mapNew[*it] == 0) + mapNew.erase(*it); + } + } + + if (setTried.size()) return -13; + if (mapNew.size()) return -15; + + return 0; +} +#endif + +void CAddrMan::GetAddr_(std::vector &vAddr) +{ + int nNodes = ADDRMAN_GETADDR_MAX_PCT*vRandom.size()/100; + if (nNodes > ADDRMAN_GETADDR_MAX) + nNodes = ADDRMAN_GETADDR_MAX; + + // perform a random shuffle over the first nNodes elements of vRandom (selecting from all) + for (int n = 0; n nUpdateInterval) + info.nTime = nTime; +} diff --git a/src/addrman.h b/src/addrman.h new file mode 100644 index 0000000..350ecb2 --- /dev/null +++ b/src/addrman.h @@ -0,0 +1,499 @@ +// Copyright (c) 2012 Pieter Wuille +// Distributed under the MIT/X11 software license, see the accompanying +// file license.txt or http://www.opensource.org/licenses/mit-license.php. +#ifndef _BITCOIN_ADDRMAN +#define _BITCOIN_ADDRMAN 1 + +#include "netbase.h" +#include "protocol.h" +#include "util.h" + + +#include +#include + +#include + + +// Extended statistics about a CAddress +class CAddrInfo : public CAddress +{ +private: + // where knowledge about this address first came from + CNetAddr source; + + // last succesfull connection by us + int64 nLastSuccess; + + // last try whatsoever by us: + // int64 CAddress::nLastTry + + // connection attempts since last succesful 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: + + IMPLEMENT_SERIALIZE( + CAddress* pthis = (CAddress*)(this); + READWRITE(*pthis); + READWRITE(source); + READWRITE(nLastSuccess); + READWRITE(nAttempts); + ) + + void Init() + { + nLastSuccess = 0; + nLastTry = 0; + nAttempts = 0; + nRefCount = 0; + fInTried = false; + nRandomPos = -1; + } + + CAddrInfo(const CAddress &addrIn, const CNetAddr &addrSource) : CAddress(addrIn) + { + Init(); + } + + CAddrInfo() : CAddress(), source() + { + Init(); + } + + // Calculate in which "tried" bucket this entry belongs + int GetTriedBucket(const std::vector &nKey) const; + + // Calculate in which "new" bucket this entry belongs, given a certain source + int GetNewBucket(const std::vector &nKey, const CNetAddr& src) const; + + // Calculate in which "new" bucket this entry belongs, using its default source + int GetNewBucket(const std::vector &nKey) const + { + return GetNewBucket(nKey, source); + } + + // Determine whether the statistics about this entry are bad enough so that it can just be deleted + bool IsTerrible(int64 nNow = GetAdjustedTime()) const; + + // Calculate the relative chance this entry should be given when selecting nodes to connect to + double GetChance(int64 nNow = GetAdjustedTime()) const; + +}; + +// Stochastic address manager +// +// Design goals: +// * Only keep a limited number of addresses around, so that addr.dat and memory requirements do not grow without bound. +// * Keep the address tables in-memory, and asynchronously dump the entire to able in addr.dat. +// * Make sure no (localized) attacker can fill the entire table with his nodes/addresses. +// +// To that end: +// * Addresses are organized into buckets. +// * Address that have not yet been tried go into 256 "new" buckets. +// * Based on the address range (/16 for IPv4) of source of the information, 32 buckets are selected at random +// * The actual bucket is chosen from one of these, based on the range the address itself is located. +// * One single address can occur in up to 4 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 64 "tried" buckets. +// * Each address range selects at random 4 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 datastructure. + +// 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 + +// over how many buckets entries with tried addresses from a single group (/16 for IPv4) are spread +#define ADDRMAN_TRIED_BUCKETS_PER_GROUP 4 + +// over how many buckets entries with new addresses originating from a single group are spread +#define ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP 32 + +// 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 + +// 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 + +// 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 + +class CAddrMan +{ +private: + // critical section to protect the inner data structures + mutable CCriticalSection cs; + + // secret key to randomize bucket select with + std::vector nKey; + + // last used nId + int nIdCount; + + // table with information about all nId's + std::map mapInfo; + + // find an nId based on its network address + std::map mapAddr; + + // randomly-ordered vector of all nId's + std::vector vRandom; + + // number of "tried" entries + int nTried; + + // list of "tried" buckets + std::vector > vvTried; + + // number of (unique) "new" entries + int nNew; + + // list of "new" buckets + std::vector > vvNew; + +protected: + + // Find an entry. + CAddrInfo* Find(const CNetAddr& addr, int *pnId = NULL); + + // find an entry, creating it if necessary. + // nTime and nServices of found node is updated, if necessary. + CAddrInfo* Create(const CAddress &addr, const CNetAddr &addrSource, int *pnId = NULL); + + // Swap two elements in vRandom. + void SwapRandom(int nRandomPos1, int nRandomPos2); + + // Return position in given bucket to replace. + int SelectTried(int nKBucket); + + // Remove an element from a "new" bucket. + // This is the only place where actual deletes occur. + // They are never deleted while in the "tried" table, only possibly evicted back to the "new" table. + int ShrinkNew(int nUBucket); + + // 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); + + // Mark an entry "good", possibly moving it from "new" to "tried". + void Good_(const CService &addr, int64 nTime); + + // Add an entry to the "new" table. + bool Add_(const CAddress &addr, const CNetAddr& source, int64 nTimePenalty); + + // Mark an entry as attempted to connect. + void Attempt_(const CService &addr, int64 nTime); + + // Select an address to connect to. + // nUnkBias determines how much to favor new addresses over tried ones (min=0, max=100) + CAddress Select_(int nUnkBias); + +#ifdef DEBUG_ADDRMAN + // Perform consistency check. Returns an error code or zero. + int Check_(); +#endif + + // Select several addresses at once. + void GetAddr_(std::vector &vAddr); + + // Mark an entry as currently-connected-to. + void Connected_(const CService &addr, int64 nTime); + +public: + + IMPLEMENT_SERIALIZE + (({ + // serialized format: + // * version byte (currently 0) + // * nKey + // * nNew + // * nTried + // * number of "new" buckets + // * all nNew addrinfo's in vvNew + // * all nTried addrinfo's in vvTried + // * for each bucket: + // * number of elements + // * for each element: index + // + // 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_UNKOWN_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. + CRITICAL_BLOCK(cs) + { + unsigned char nVersion = 0; + READWRITE(nVersion); + READWRITE(nKey); + READWRITE(nNew); + READWRITE(nTried); + + CAddrMan *am = const_cast(this); + if (fWrite) + { + int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT; + READWRITE(nUBuckets); + std::map mapUnkIds; + int nIds = 0; + for (std::map::iterator it = am->mapInfo.begin(); it != am->mapInfo.end(); it++) + { + if (nIds == nNew) break; // this means nNew was wrong, oh ow + mapUnkIds[(*it).first] = nIds; + CAddrInfo &info = (*it).second; + if (info.nRefCount) + { + READWRITE(info); + nIds++; + } + } + nIds = 0; + for (std::map::iterator it = am->mapInfo.begin(); it != am->mapInfo.end(); it++) + { + if (nIds == nTried) break; // this means nTried was wrong, oh ow + CAddrInfo &info = (*it).second; + if (info.fInTried) + { + READWRITE(info); + nIds++; + } + } + for (std::vector >::iterator it = am->vvNew.begin(); it != am->vvNew.end(); it++) + { + const std::set &vNew = (*it); + int nSize = vNew.size(); + READWRITE(nSize); + for (std::set::iterator it2 = vNew.begin(); it2 != vNew.end(); it2++) + { + int nIndex = mapUnkIds[*it2]; + READWRITE(nIndex); + } + } + } else { + int nUBuckets = 0; + READWRITE(nUBuckets); + am->nIdCount = 0; + am->mapInfo.clear(); + am->mapAddr.clear(); + am->vRandom.clear(); + am->vvTried = std::vector >(ADDRMAN_TRIED_BUCKET_COUNT, std::vector(0)); + am->vvNew = std::vector >(ADDRMAN_NEW_BUCKET_COUNT, std::set()); + for (int n = 0; n < am->nNew; n++) + { + CAddrInfo &info = am->mapInfo[n]; + READWRITE(info); + am->mapAddr[info] = n; + info.nRandomPos = vRandom.size(); + am->vRandom.push_back(n); + if (nUBuckets != ADDRMAN_NEW_BUCKET_COUNT) + { + am->vvNew[info.GetNewBucket(am->nKey)].insert(n); + info.nRefCount++; + } + } + am->nIdCount = am->nNew; + int nLost = 0; + for (int n = 0; n < am->nTried; n++) + { + CAddrInfo info; + READWRITE(info); + std::vector &vTried = am->vvTried[info.GetTriedBucket(am->nKey)]; + if (vTried.size() < ADDRMAN_TRIED_BUCKET_SIZE) + { + info.nRandomPos = vRandom.size(); + info.fInTried = true; + am->vRandom.push_back(am->nIdCount); + am->mapInfo[am->nIdCount] = info; + am->mapAddr[info] = am->nIdCount; + vTried.push_back(am->nIdCount); + am->nIdCount++; + } else { + nLost++; + } + } + am->nTried -= nLost; + for (int b = 0; b < nUBuckets; b++) + { + std::set &vNew = am->vvNew[b]; + int nSize = 0; + READWRITE(nSize); + for (int n = 0; n < nSize; n++) + { + int nIndex = 0; + READWRITE(nIndex); + CAddrInfo &info = am->mapInfo[nIndex]; + if (nUBuckets == ADDRMAN_NEW_BUCKET_COUNT && info.nRefCount < ADDRMAN_NEW_BUCKETS_PER_ADDRESS) + { + info.nRefCount++; + vNew.insert(nIndex); + } + } + } + } + } + });) + + CAddrMan() : vRandom(0), vvTried(ADDRMAN_TRIED_BUCKET_COUNT, std::vector(0)), vvNew(ADDRMAN_NEW_BUCKET_COUNT, std::set()) + { + nKey.resize(32); + RAND_bytes(&nKey[0], 32); + + nIdCount = 0; + nTried = 0; + nNew = 0; + } + + // Return the number of (unique) addresses in all tables. + int size() + { + return vRandom.size(); + } + + // Consistency check + void Check() + { +#ifdef DEBUG_ADDRMAN + CRITICAL_BLOCK(cs) + { + int err; + if ((err=Check_())) + printf("ADDRMAN CONSISTENCY CHECK FAILED!!! err=%i\n", err); + } +#endif + } + + // Add a single address. + bool Add(const CAddress &addr, const CNetAddr& source, int64 nTimePenalty = 0) + { + bool fRet = false; + CRITICAL_BLOCK(cs) + { + Check(); + fRet |= Add_(addr, source, nTimePenalty); + Check(); + } + if (fRet) + printf("Added %s from %s: %i tried, %i new\n", addr.ToStringIPPort().c_str(), source.ToString().c_str(), nTried, nNew); + return fRet; + } + + // Add multiple addresses. + bool Add(const std::vector &vAddr, const CNetAddr& source, int64 nTimePenalty = 0) + { + int nAdd = 0; + CRITICAL_BLOCK(cs) + { + Check(); + for (std::vector::const_iterator it = vAddr.begin(); it != vAddr.end(); it++) + nAdd += Add_(*it, source, nTimePenalty) ? 1 : 0; + Check(); + } + if (nAdd) + printf("Added %i addresses from %s: %i tried, %i new\n", nAdd, source.ToString().c_str(), nTried, nNew); + return nAdd > 0; + } + + // Mark an entry as accessible. + void Good(const CService &addr, int64 nTime = GetAdjustedTime()) + { + CRITICAL_BLOCK(cs) + { + Check(); + Good_(addr, nTime); + Check(); + } + } + + // Mark an entry as connection attempted to. + void Attempt(const CService &addr, int64 nTime = GetAdjustedTime()) + { + CRITICAL_BLOCK(cs) + { + Check(); + Attempt_(addr, nTime); + Check(); + } + } + + // Choose an address to connect to. + // nUnkBias determines how much "new" entries are favored over "tried" ones (0-100). + CAddress Select(int nUnkBias = 50) + { + CAddress addrRet; + CRITICAL_BLOCK(cs) + { + Check(); + addrRet = Select_(nUnkBias); + Check(); + } + return addrRet; + } + + // Return a bunch of addresses, selected at random. + std::vector GetAddr() + { + Check(); + std::vector vAddr; + CRITICAL_BLOCK(cs) + GetAddr_(vAddr); + Check(); + return vAddr; + } + + // Mark an entry as currently-connected-to. + void Connected(const CService &addr, int64 nTime = GetAdjustedTime()) + { + CRITICAL_BLOCK(cs) + { + Check(); + Connected_(addr, nTime); + Check(); + } + } +}; + +#endif diff --git a/src/db.cpp b/src/db.cpp index ea6d46a..645f725 100644 --- a/src/db.cpp +++ b/src/db.cpp @@ -621,44 +621,65 @@ bool CAddrDB::WriteAddress(const CAddress& addr) return Write(make_pair(string("addr"), addr.GetKey()), addr); } +bool CAddrDB::WriteAddrman(const CAddrMan& addrman) +{ + return Write(string("addrman"), addrman); +} + bool CAddrDB::EraseAddress(const CAddress& addr) { return Erase(make_pair(string("addr"), addr.GetKey())); } -bool CAddrDB::LoadAddresses() +bool CAddrDB::LoadAddresses(bool &fUpdate) { - CRITICAL_BLOCK(cs_mapAddresses) + bool fAddrMan = false; + if (Read(string("addrman"), addrman)) { - // Get cursor - Dbc* pcursor = GetCursor(); - if (!pcursor) + printf("Loaded %i addresses\n", addrman.size()); + fAddrMan = true; + } + + vector vAddr; + + // Get cursor + Dbc* pcursor = GetCursor(); + if (!pcursor) + return false; + + loop + { + // Read next record + CDataStream ssKey; + CDataStream ssValue; + int ret = ReadAtCursor(pcursor, ssKey, ssValue); + if (ret == DB_NOTFOUND) + break; + else if (ret != 0) return false; - loop + // Unserialize + string strType; + ssKey >> strType; + if (strType == "addr") { - // Read next record - CDataStream ssKey; - CDataStream ssValue; - int ret = ReadAtCursor(pcursor, ssKey, ssValue); - if (ret == DB_NOTFOUND) - break; - else if (ret != 0) - return false; - - // Unserialize - string strType; - ssKey >> strType; - if (strType == "addr") + if (fAddrMan) + fUpdate = true; + else { CAddress addr; ssValue >> addr; - mapAddresses.insert(make_pair(addr.GetKey(), addr)); + vAddr.push_back(addr); } + } - pcursor->close(); + } + pcursor->close(); - printf("Loaded %d addresses\n", mapAddresses.size()); + if (!fAddrMan) + { + addrman.Add(vAddr, CNetAddr("0.0.0.0")); + printf("Loaded %i addresses\n", addrman.size()); } return true; @@ -666,7 +687,11 @@ bool CAddrDB::LoadAddresses() bool LoadAddresses() { - return CAddrDB("cr+").LoadAddresses(); + bool fUpdate = false; + bool fRet = CAddrDB("cr+").LoadAddresses(fUpdate); + if (fUpdate) + CDB::Rewrite("addr.dat", "\004addr"); + return fRet; } diff --git a/src/db.h b/src/db.h index 2611faa..81f7a98 100644 --- a/src/db.h +++ b/src/db.h @@ -16,6 +16,7 @@ class CAccount; class CAccountingEntry; class CAddress; +class CAddrMan; class CBlockLocator; class CDiskBlockIndex; class CDiskTxPos; @@ -307,7 +308,8 @@ private: public: bool WriteAddress(const CAddress& addr); bool EraseAddress(const CAddress& addr); - bool LoadAddresses(); + bool WriteAddrman(const CAddrMan& addr); + bool LoadAddresses(bool &fUpdate); }; bool LoadAddresses(); diff --git a/src/init.cpp b/src/init.cpp index b2c59ec..2b21f6d 100644 --- a/src/init.cpp +++ b/src/init.cpp @@ -543,7 +543,7 @@ bool AppInit2(int argc, char* argv[]) CAddress addr(CService(strAddr, GetDefaultPort(), fAllowDNS)); addr.nTime = 0; // so it won't relay unless successfully connected if (addr.IsValid()) - AddAddress(addr); + addrman.Add(addr, CNetAddr("127.0.0.1")); } } diff --git a/src/irc.cpp b/src/irc.cpp index 7a6f40c..09bacc1 100644 --- a/src/irc.cpp +++ b/src/irc.cpp @@ -341,7 +341,7 @@ void ThreadIRCSeed2(void* parg) if (DecodeAddress(pszName, addr)) { addr.nTime = GetAdjustedTime(); - if (AddAddress(addr, 51 * 60)) + if (addrman.Add(addr, addrConnect, 51 * 60)) printf("IRC got new address: %s\n", addr.ToString().c_str()); nGotIRCAddresses++; } diff --git a/src/main.cpp b/src/main.cpp index a9311e2..a8fabc3 100644 --- a/src/main.cpp +++ b/src/main.cpp @@ -2155,11 +2155,18 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) } // Get recent addresses - if (pfrom->nVersion >= 31402 || mapAddresses.size() < 1000) + if (pfrom->nVersion >= 31402 || addrman.size() < 1000) { pfrom->PushMessage("getaddr"); pfrom->fGetAddr = true; } + addrman.Good(pfrom->addr); + } else { + if (((CNetAddr)pfrom->addr) == (CNetAddr)addrFrom) + { + addrman.Add(addrFrom, addrFrom); + addrman.Good(addrFrom); + } } // Ask the first connected node for block updates @@ -2205,7 +2212,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) vRecv >> vAddr; // Don't want addr from older versions unless seeding - if (pfrom->nVersion < 31402 && mapAddresses.size() > 1000) + if (pfrom->nVersion < 31402 && addrman.size() > 1000) return true; if (vAddr.size() > 1000) { @@ -2214,8 +2221,6 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) } // Store the new addresses - CAddrDB addrDB; - addrDB.TxnBegin(); int64 nNow = GetAdjustedTime(); int64 nSince = nNow - 10 * 60; BOOST_FOREACH(CAddress& addr, vAddr) @@ -2227,7 +2232,6 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) continue; if (addr.nTime <= 100000000 || addr.nTime > nNow + 10 * 60) addr.nTime = nNow - 5 * 24 * 60 * 60; - AddAddress(addr, 2 * 60 * 60, &addrDB); pfrom->AddAddressKnown(addr); if (addr.nTime > nSince && !pfrom->fGetAddr && vAddr.size() <= 10 && addr.IsRoutable()) { @@ -2259,7 +2263,7 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) } } } - addrDB.TxnCommit(); // Save addresses (it's ok if this fails) + addrman.Add(vAddr, pfrom->addr, 2 * 60 * 60); if (vAddr.size() < 1000) pfrom->fGetAddr = false; } @@ -2500,25 +2504,10 @@ bool static ProcessMessage(CNode* pfrom, string strCommand, CDataStream& vRecv) else if (strCommand == "getaddr") { - // Nodes rebroadcast an addr every 24 hours pfrom->vAddrToSend.clear(); - int64 nSince = GetAdjustedTime() - 3 * 60 * 60; // in the last 3 hours - CRITICAL_BLOCK(cs_mapAddresses) - { - unsigned int nCount = 0; - BOOST_FOREACH(const PAIRTYPE(vector, CAddress)& item, mapAddresses) - { - const CAddress& addr = item.second; - if (addr.nTime > nSince) - nCount++; - } - BOOST_FOREACH(const PAIRTYPE(vector, CAddress)& item, mapAddresses) - { - const CAddress& addr = item.second; - if (addr.nTime > nSince && GetRand(nCount) < 2500) - pfrom->PushAddress(addr); - } - } + vector vAddr = addrman.GetAddr(); + BOOST_FOREACH(const CAddress &addr, vAddr) + pfrom->PushAddress(addr); } @@ -2760,35 +2749,6 @@ bool SendMessages(CNode* pto, bool fSendTrickle) nLastRebroadcast = GetTime(); } - // Clear out old addresses periodically so it's not too much work at once - static int64 nLastClear; - if (nLastClear == 0) - nLastClear = GetTime(); - if (GetTime() - nLastClear > 10 * 60 && vNodes.size() >= 3) - { - nLastClear = GetTime(); - CRITICAL_BLOCK(cs_mapAddresses) - { - CAddrDB addrdb; - int64 nSince = GetAdjustedTime() - 14 * 24 * 60 * 60; - for (map, CAddress>::iterator mi = mapAddresses.begin(); - mi != mapAddresses.end();) - { - const CAddress& addr = (*mi).second; - if (addr.nTime < nSince) - { - if (mapAddresses.size() < 1000 || GetTime() > nLastClear + 20) - break; - addrdb.EraseAddress(addr); - mapAddresses.erase(mi++); - } - else - mi++; - } - } - } - - // // Message: addr // diff --git a/src/makefile.linux-mingw b/src/makefile.linux-mingw index 9212698..40ce1dc 100644 --- a/src/makefile.linux-mingw +++ b/src/makefile.linux-mingw @@ -45,6 +45,7 @@ HEADERS = $(wildcard *.h) OBJS= \ obj/checkpoints.o \ obj/netbase.o \ + obj/addrman.o \ obj/crypter.o \ obj/key.o \ obj/db.o \ diff --git a/src/makefile.mingw b/src/makefile.mingw index c55e17a..f7dfcc7 100644 --- a/src/makefile.mingw +++ b/src/makefile.mingw @@ -43,6 +43,7 @@ HEADERS = $(wildcard *.h) OBJS= \ obj/checkpoints.o \ obj/netbase.o \ + obj/addrman.o \ obj/crypter.o \ obj/key.o \ obj/db.o \ diff --git a/src/makefile.osx b/src/makefile.osx index 9943271..8790d92 100644 --- a/src/makefile.osx +++ b/src/makefile.osx @@ -60,6 +60,7 @@ CFLAGS=-mmacosx-version-min=10.5 -arch i386 -O3 \ OBJS= \ obj/checkpoints.o \ obj/netbase.o \ + obj/addrman.o \ obj/crypter.o \ obj/key.o \ obj/db.o \ diff --git a/src/makefile.unix b/src/makefile.unix index 80b5bca..8d35460 100644 --- a/src/makefile.unix +++ b/src/makefile.unix @@ -91,6 +91,7 @@ xCXXFLAGS=-pthread -Wextra -Wno-sign-compare -Wno-char-subscripts -Wno-invalid-o OBJS= \ obj/checkpoints.o \ obj/netbase.o \ + obj/addrman.o \ obj/crypter.o \ obj/key.o \ obj/db.o \ diff --git a/src/net.cpp b/src/net.cpp index 546bc6a..08edafb 100644 --- a/src/net.cpp +++ b/src/net.cpp @@ -9,6 +9,7 @@ #include "net.h" #include "init.h" #include "strlcpy.h" +#include "addrman.h" #ifdef WIN32 #include @@ -49,11 +50,10 @@ static CNode* pnodeLocalHost = NULL; uint64 nLocalHostNonce = 0; array vnThreadsRunning; static SOCKET hListenSocket = INVALID_SOCKET; +CAddrMan addrman; vector vNodes; CCriticalSection cs_vNodes; -map, CAddress> mapAddresses; -CCriticalSection cs_mapAddresses; map mapRelay; deque > vRelayExpiration; CCriticalSection cs_mapRelay; @@ -279,86 +279,9 @@ void ThreadGetMyExternalIP(void* parg) -bool AddAddress(CAddress addr, int64 nTimePenalty, CAddrDB *pAddrDB) -{ - if (!addr.IsRoutable()) - return false; - if ((CService)addr == (CService)addrLocalHost) - return false; - addr.nTime = max((int64)0, (int64)addr.nTime - nTimePenalty); - bool fUpdated = false; - bool fNew = false; - CAddress addrFound = addr; - - CRITICAL_BLOCK(cs_mapAddresses) - { - map, CAddress>::iterator it = mapAddresses.find(addr.GetKey()); - if (it == mapAddresses.end()) - { - // New address - printf("AddAddress(%s)\n", addr.ToString().c_str()); - mapAddresses.insert(make_pair(addr.GetKey(), addr)); - fUpdated = true; - fNew = true; - } - else - { - addrFound = (*it).second; - if ((addrFound.nServices | addr.nServices) != addrFound.nServices) - { - // Services have been added - addrFound.nServices |= addr.nServices; - fUpdated = true; - } - bool fCurrentlyOnline = (GetAdjustedTime() - addr.nTime < 24 * 60 * 60); - int64 nUpdateInterval = (fCurrentlyOnline ? 60 * 60 : 24 * 60 * 60); - if (addrFound.nTime < addr.nTime - nUpdateInterval) - { - // Periodically update most recently seen time - addrFound.nTime = addr.nTime; - fUpdated = true; - } - } - } - // There is a nasty deadlock bug if this is done inside the cs_mapAddresses - // CRITICAL_BLOCK: - // Thread 1: begin db transaction (locks inside-db-mutex) - // then AddAddress (locks cs_mapAddresses) - // Thread 2: AddAddress (locks cs_mapAddresses) - // ... then db operation hangs waiting for inside-db-mutex - if (fUpdated) - { - if (pAddrDB) - pAddrDB->WriteAddress(addrFound); - else - CAddrDB().WriteAddress(addrFound); - } - return fNew; -} - void AddressCurrentlyConnected(const CService& addr) { - CAddress *paddrFound = NULL; - - CRITICAL_BLOCK(cs_mapAddresses) - { - // Only if it's been published already - map, CAddress>::iterator it = mapAddresses.find(addr.GetKey()); - if (it != mapAddresses.end()) - paddrFound = &(*it).second; - } - - if (paddrFound) - { - int64 nUpdateInterval = 20 * 60; - if (paddrFound->nTime < GetAdjustedTime() - nUpdateInterval) - { - // Periodically update most recently seen time - paddrFound->nTime = GetAdjustedTime(); - CAddrDB addrdb; - addrdb.WriteAddress(*paddrFound); - } - } + addrman.Connected(addr); } @@ -505,13 +428,11 @@ CNode* ConnectNode(CAddress addrConnect, int64 nTimeout) } /// debug print - printf("trying connection %s lastseen=%.1fhrs lasttry=%.1fhrs\n", + printf("trying connection %s lastseen=%.1fhrs\n", addrConnect.ToString().c_str(), - (double)(addrConnect.nTime - GetAdjustedTime())/3600.0, - (double)(addrConnect.nLastTry - GetAdjustedTime())/3600.0); + (double)(addrConnect.nTime - GetAdjustedTime())/3600.0); - CRITICAL_BLOCK(cs_mapAddresses) - mapAddresses[addrConnect.GetKey()].nLastTry = GetAdjustedTime(); + addrman.Attempt(addrConnect); // Connect SOCKET hSocket; @@ -1125,12 +1046,15 @@ void MapPort(bool /* unused fMapPort */) - -static const char *strDNSSeed[] = { - "bitseed.xf2.org", - "dnsseed.bluematt.me", - "seed.bitcoin.sipa.be", - "dnsseed.bitcoin.dashjr.org", +// DNS seeds +// Each pair gives a source name and a seed name. +// The first name is used as information source for addrman. +// The second name should resolve to a list of seed addresses. +static const char *strDNSSeed[][2] = { + {"xf2.org", "bitseed.xf2.org"}, + {"bluematt.me", "dnsseed.bluematt.me"}, + {"bitcoin.sipa.be", "seed.bitcoin.sipa.be"}, + {"dashjr.org", "dnsseed.bitcoin.dashjr.org"}, }; void ThreadDNSAddressSeed(void* parg) @@ -1163,22 +1087,18 @@ void ThreadDNSAddressSeed2(void* parg) for (int seed_idx = 0; seed_idx < ARRAYLEN(strDNSSeed); seed_idx++) { vector vaddr; - if (LookupHost(strDNSSeed[seed_idx], vaddr)) + vector vAdd; + if (LookupHost(strDNSSeed[seed_idx][1], vaddr)) { - CAddrDB addrDB; - addrDB.TxnBegin(); - BOOST_FOREACH (CNetAddr& ip, vaddr) + BOOST_FOREACH(CNetAddr& ip, vaddr) { - if (ip.IsRoutable()) - { - CAddress addr(CService(ip, GetDefaultPort()), NODE_NETWORK); - addr.nTime = 0; - AddAddress(addr, 0, &addrDB); - found++; - } + CAddress addr = CAddress(CService(ip, GetDefaultPort())); + addr.nTime = 0; + vAdd.push_back(addr); + found++; } - addrDB.TxnCommit(); // Save addresses (it's ok if this fails) } + addrman.Add(vAdd, CNetAddr(strDNSSeed[seed_idx][0], true)); } } @@ -1277,7 +1197,37 @@ unsigned int pnSeed[] = 0xc461d84a, 0xb2dbe247, }; +void DumpAddresses() +{ + CAddrDB adb; + adb.WriteAddrman(addrman); +} +void ThreadDumpAddress2(void* parg) +{ + vnThreadsRunning[THREAD_DUMPADDRESS]++; + while (!fShutdown) + { + DumpAddresses(); + vnThreadsRunning[THREAD_DUMPADDRESS]--; + Sleep(100000); + vnThreadsRunning[THREAD_DUMPADDRESS]++; + } + vnThreadsRunning[THREAD_DUMPADDRESS]--; +} + +void ThreadDumpAddress(void* parg) +{ + IMPLEMENT_RANDOMIZE_STACK(ThreadDumpAddress(parg)); + try + { + ThreadDumpAddress2(parg); + } + catch (std::exception& e) { + PrintException(&e, "ThreadDumpAddress()"); + } + printf("ThreadDumpAddress exiting\n"); +} void ThreadOpenConnections(void* parg) { @@ -1326,6 +1276,8 @@ void ThreadOpenConnections2(void* parg) int64 nStart = GetTime(); loop { + int nOutbound = 0; + vnThreadsRunning[THREAD_OPENCONNECTIONS]--; Sleep(500); vnThreadsRunning[THREAD_OPENCONNECTIONS]++; @@ -1335,7 +1287,7 @@ void ThreadOpenConnections2(void* parg) // Limit outbound connections loop { - int nOutbound = 0; + nOutbound = 0; CRITICAL_BLOCK(cs_vNodes) BOOST_FOREACH(CNode* pnode, vNodes) if (!pnode->fInbound) @@ -1353,16 +1305,11 @@ void ThreadOpenConnections2(void* parg) bool fAddSeeds = false; - CRITICAL_BLOCK(cs_mapAddresses) - { - // Add seed nodes if IRC isn't working - bool fTOR = (fUseProxy && addrProxy.GetPort() == 9050); - if (mapAddresses.empty() && (GetTime() - nStart > 60 || fTOR) && !fTestNet) - fAddSeeds = true; - } - - if (fAddSeeds) + // Add seed nodes if IRC isn't working + bool fTOR = (fUseProxy && addrProxy.GetPort() == 9050); + if (addrman.size()==0 && (GetTime() - nStart > 60 || fTOR) && !fTestNet) { + std::vector vAdd; for (int i = 0; i < ARRAYLEN(pnSeed); i++) { // It'll only connect to one or two seed nodes because once it connects, @@ -1374,8 +1321,9 @@ void ThreadOpenConnections2(void* parg) memcpy(&ip, &pnSeed[i], sizeof(ip)); CAddress addr(CService(ip, GetDefaultPort())); addr.nTime = GetTime()-GetRand(nOneWeek)-nOneWeek; - AddAddress(addr); + vAdd.push_back(addr); } + addrman.Add(vAdd, CNetAddr("127.0.0.1")); } // @@ -1393,59 +1341,28 @@ void ThreadOpenConnections2(void* parg) int64 nANow = GetAdjustedTime(); - CRITICAL_BLOCK(cs_mapAddresses) + int nTries = 0; + loop { - BOOST_FOREACH(const PAIRTYPE(vector, CAddress)& item, mapAddresses) - { - const CAddress& addr = item.second; - if (!addr.IsIPv4() || !addr.IsValid() || setConnected.count(addr.GetGroup())) - continue; - int64 nSinceLastSeen = nANow - addr.nTime; - int64 nSinceLastTry = nANow - addr.nLastTry; - - // Randomize the order in a deterministic way, putting the standard port first - int64 nRandomizer = (uint64)(nStart * 4951 + addr.nLastTry * 9567851 + addr.GetHash()) % (2 * 60 * 60); - if (addr.GetPort() != GetDefaultPort()) - nRandomizer += 2 * 60 * 60; - - // Last seen Base retry frequency - // <1 hour 10 min - // 1 hour 1 hour - // 4 hours 2 hours - // 24 hours 5 hours - // 48 hours 7 hours - // 7 days 13 hours - // 30 days 27 hours - // 90 days 46 hours - // 365 days 93 hours - int64 nDelay = (int64)(3600.0 * sqrt(fabs((double)nSinceLastSeen) / 3600.0) + nRandomizer); - - // Fast reconnect for one hour after last seen - if (nSinceLastSeen < 60 * 60) - nDelay = 10 * 60; - - // Limit retry frequency - if (nSinceLastTry < nDelay) - continue; + // use an nUnkBias between 10 (no outgoing connections) and 90 (8 outgoing connections) + CAddress addr = addrman.Select(10 + min(nOutbound,8)*10); - // If we have IRC, we'll be notified when they first come online, - // and again every 24 hours by the refresh broadcast. - if (nGotIRCAddresses > 0 && vNodes.size() >= 2 && nSinceLastSeen > 24 * 60 * 60) - continue; + // if we selected an invalid address, restart + if (!addr.IsIPv4() || !addr.IsValid() || setConnected.count(addr.GetGroup()) || addr == addrLocalHost) + break; - // Only try the old stuff if we don't have enough connections - if (vNodes.size() >= 8 && nSinceLastSeen > 24 * 60 * 60) - continue; + nTries++; - // If multiple addresses are ready, prioritize by time since - // last seen and time since last tried. - int64 nScore = min(nSinceLastTry, (int64)24 * 60 * 60) - nSinceLastSeen - nRandomizer; - if (nScore > nBest) - { - nBest = nScore; - addrConnect = addr; - } - } + // only consider very recently tried nodes after 30 failed attempts + if (nANow - addr.nLastTry < 600 && nTries < 30) + continue; + + // do not allow non-default ports, unless after 50 invalid addresses selected already + if (addr.GetPort() != GetDefaultPort() && nTries < 50) + continue; + + addrConnect = addr; + break; } if (addrConnect.IsValid()) @@ -1811,6 +1728,10 @@ void StartNode(void* parg) if (!CreateThread(ThreadMessageHandler, NULL)) printf("Error: CreateThread(ThreadMessageHandler) failed\n"); + // Dump network addresses + if (!CreateThread(ThreadDumpAddress, NULL)) + printf("Error; CreateThread(ThreadDumpAddress) failed\n"); + // Generate coins in the background GenerateBitcoins(fGenerateBitcoins, pwalletMain); } @@ -1840,10 +1761,11 @@ bool StopNode() if (fHaveUPnP && vnThreadsRunning[THREAD_UPNP] > 0) printf("ThreadMapPort still running\n"); if (vnThreadsRunning[THREAD_DNSSEED] > 0) printf("ThreadDNSAddressSeed still running\n"); if (vnThreadsRunning[THREAD_ADDEDCONNECTIONS] > 0) printf("ThreadOpenAddedConnections still running\n"); + if (vnThreadsRunning[THREAD_DUMPADDRESS] > 0) printf("ThreadDumpAddresses still running\n"); while (vnThreadsRunning[THREAD_MESSAGEHANDLER] > 0 || vnThreadsRunning[THREAD_RPCSERVER] > 0) Sleep(20); Sleep(50); - + DumpAddresses(); return true; } diff --git a/src/net.h b/src/net.h index 51a816d..6fd4944 100644 --- a/src/net.h +++ b/src/net.h @@ -16,6 +16,7 @@ #include "netbase.h" #include "protocol.h" +#include "addrman.h" class CAddrDB; class CRequestTracker; @@ -31,7 +32,6 @@ static const unsigned int PUBLISH_HOPS = 5; bool RecvLine(SOCKET hSocket, std::string& strLine); bool GetMyExternalIP(CNetAddr& ipRet); -bool AddAddress(CAddress addr, int64 nTimePenalty=0, CAddrDB *pAddrDB=NULL); void AddressCurrentlyConnected(const CService& addr); CNode* FindNode(const CNetAddr& ip); CNode* FindNode(const CService& ip); @@ -79,6 +79,7 @@ enum threadId THREAD_UPNP, THREAD_DNSSEED, THREAD_ADDEDCONNECTIONS, + THREAD_DUMPADDRESS, THREAD_MAX }; @@ -89,11 +90,10 @@ extern uint64 nLocalServices; extern CAddress addrLocalHost; extern uint64 nLocalHostNonce; extern boost::array vnThreadsRunning; +extern CAddrMan addrman; extern std::vector vNodes; extern CCriticalSection cs_vNodes; -extern std::map, CAddress> mapAddresses; -extern CCriticalSection cs_mapAddresses; extern std::map mapRelay; extern std::deque > vRelayExpiration; extern CCriticalSection cs_mapRelay; diff --git a/src/netbase.cpp b/src/netbase.cpp index 7799a65..baf7c41 100644 --- a/src/netbase.cpp +++ b/src/netbase.cpp @@ -519,15 +519,22 @@ bool CNetAddr::GetIn6Addr(struct in6_addr* pipv6Addr) const std::vector CNetAddr::GetGroup() const { std::vector vchRet; - int nClass = 0; // 0=IPv6, 1=IPv4, 255=unroutable + int nClass = 0; // 0=IPv6, 1=IPv4, 254=local, 255=unroutable int nStartByte = 0; int nBits = 16; - // for unroutable addresses, each address is considered different + // all local addresses belong to the same group + if (IsLocal()) + { + nClass = 254; + nBits = 0; + } + + // all unroutable addresses belong to the same group if (!IsRoutable()) { nClass = 255; - nBits = 128; + nBits = 0; } // for IPv4 addresses, '1' + the 16 higher-order bits of the IP // includes mapped IPv4, SIIT translated IPv4, and the well-known prefix diff --git a/src/protocol.h b/src/protocol.h index b70dd71..613c47f 100644 --- a/src/protocol.h +++ b/src/protocol.h @@ -94,7 +94,7 @@ class CAddress : public CService unsigned int nTime; // memory only - unsigned int nLastTry; + int64 nLastTry; }; class CInv diff --git a/src/uint256.h b/src/uint256.h index caf6fa1..783e706 100644 --- a/src/uint256.h +++ b/src/uint256.h @@ -348,6 +348,10 @@ public: return sizeof(pn); } + uint64 Get64(int n=0) const + { + return pn[2*n] | (uint64)pn[2*n+1] << 32; + } unsigned int GetSerializeSize(int nType=0, int nVersion=PROTOCOL_VERSION) const {