diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/addrman.cpp | 8 | ||||
| -rw-r--r-- | src/addrman.h | 239 |
2 files changed, 128 insertions, 119 deletions
diff --git a/src/addrman.cpp b/src/addrman.cpp index 7b674a66e7..7ff21b00ec 100644 --- a/src/addrman.cpp +++ b/src/addrman.cpp @@ -1,5 +1,5 @@ // Copyright (c) 2012 Pieter Wuille -// Distributed under the MIT/X11 software license, see the accompanying +// Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "addrman.h" @@ -39,7 +39,7 @@ int CAddrInfo::GetNewBucket(const std::vector<unsigned char>& nKey, const CNetAd bool CAddrInfo::IsTerrible(int64_t nNow) const { - if (nLastTry && nLastTry >= nNow - 60) // never remove things tried the last minute + if (nLastTry && nLastTry >= nNow - 60) // never remove things tried in the last minute return false; if (nTime > nNow + 10 * 60) // came in a flying DeLorean @@ -131,7 +131,7 @@ int CAddrMan::SelectTried(int nKBucket) { std::vector<int>& vTried = vvTried[nKBucket]; - // random shuffle the first few elements (using the entire list) + // randomly shuffle the first few elements (using the entire list) // find the least recently tried among them int64_t nOldest = -1; int nOldestPos = -1; @@ -211,7 +211,7 @@ void CAddrMan::MakeTried(CAddrInfo& info, int nId, int nOrigin) assert(info.nRefCount == 0); - // what tried bucket to move the entry to + // which tried bucket to move the entry to int nKBucket = info.GetTriedBucket(nKey); std::vector<int>& vTried = vvTried[nKBucket]; diff --git a/src/addrman.h b/src/addrman.h index 5fd698f18a..914086fc76 100644 --- a/src/addrman.h +++ b/src/addrman.h @@ -1,5 +1,5 @@ // Copyright (c) 2012 Pieter Wuille -// Distributed under the MIT/X11 software license, see the accompanying +// Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef _BITCOIN_ADDRMAN @@ -17,29 +17,31 @@ #include <stdint.h> #include <vector> -/** Extended statistics about a CAddress */ +/** + * Extended statistics about a CAddress + */ class CAddrInfo : public CAddress { private: - // where knowledge about this address first came from + //! where knowledge about this address first came from CNetAddr source; - // last successful connection by us + //! last successful connection by us int64_t nLastSuccess; - // last try whatsoever by us: + //! last try whatsoever by us: // int64_t CAddress::nLastTry - // connection attempts since last successful attempt + //! connection attempts since last successful attempt int nAttempts; - // reference count in new sets (memory only) + //! reference count in new sets (memory only) int nRefCount; - // in tried set? (memory only) + //! in tried set? (memory only) bool fInTried; - // position in vRandom + //! position in vRandom int nRandomPos; friend class CAddrMan; @@ -76,200 +78,205 @@ public: Init(); } - // Calculate in which "tried" bucket this entry belongs + //! Calculate in which "tried" bucket this entry belongs int GetTriedBucket(const std::vector<unsigned char> &nKey) const; - // Calculate in which "new" bucket this entry belongs, given a certain source + //! Calculate in which "new" bucket this entry belongs, given a certain source int GetNewBucket(const std::vector<unsigned char> &nKey, const CNetAddr& src) const; - // Calculate in which "new" bucket this entry belongs, using its default source + //! Calculate in which "new" bucket this entry belongs, using its default source int GetNewBucket(const std::vector<unsigned char> &nKey) const { return GetNewBucket(nKey, source); } - // Determine whether the statistics about this entry are bad enough so that it can just be deleted + //! Determine whether the statistics about this entry are bad enough so that it can just be deleted bool IsTerrible(int64_t nNow = GetAdjustedTime()) const; - // Calculate the relative chance this entry should be given when selecting nodes to connect to + //! Calculate the relative chance this entry should be given when selecting nodes to connect to double GetChance(int64_t nNow = GetAdjustedTime()) const; }; -// Stochastic address manager -// -// Design goals: -// * 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 data structure. - -// total number of buckets for tried addresses +/** Stochastic address manager + * + * Design goals: + * * Keep the address tables in-memory, and asynchronously dump the entire to able in peers.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 data structure. + */ + +//! total number of buckets for tried addresses #define ADDRMAN_TRIED_BUCKET_COUNT 64 -// maximum allowed number of entries in buckets for tried addresses +//! maximum allowed number of entries in buckets for tried addresses #define ADDRMAN_TRIED_BUCKET_SIZE 64 -// total number of buckets for new addresses +//! total number of buckets for new addresses #define ADDRMAN_NEW_BUCKET_COUNT 256 -// maximum allowed number of entries in buckets for new addresses +//! 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 +//! 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 +//! 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 +//! 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 +//! 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 +//! how old addresses can maximally be #define ADDRMAN_HORIZON_DAYS 30 -// after how many failed attempts we give up on a new node +//! after how many failed attempts we give up on a new node #define ADDRMAN_RETRIES 3 -// how many successive failures are allowed ... +//! how many successive failures are allowed ... #define ADDRMAN_MAX_FAILURES 10 -// ... in at least this many days +//! ... in at least this many days #define ADDRMAN_MIN_FAIL_DAYS 7 -// the maximum percentage of nodes to return in a getaddr call +//! 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 +//! the maximum number of nodes to return in a getaddr call #define ADDRMAN_GETADDR_MAX 2500 -/** Stochastical (IP) address manager */ +/** + * Stochastical (IP) address manager + */ class CAddrMan { private: - // critical section to protect the inner data structures + //! critical section to protect the inner data structures mutable CCriticalSection cs; - // secret key to randomize bucket select with + //! secret key to randomize bucket select with std::vector<unsigned char> nKey; - // last used nId + //! last used nId int nIdCount; - // table with information about all nIds + //! table with information about all nIds std::map<int, CAddrInfo> mapInfo; - // find an nId based on its network address + //! find an nId based on its network address std::map<CNetAddr, int> mapAddr; - // randomly-ordered vector of all nIds + //! randomly-ordered vector of all nIds std::vector<int> vRandom; // number of "tried" entries int nTried; - // list of "tried" buckets + //! list of "tried" buckets std::vector<std::vector<int> > vvTried; - // number of (unique) "new" entries + //! number of (unique) "new" entries int nNew; - // list of "new" buckets + //! list of "new" buckets std::vector<std::set<int> > vvNew; protected: - // Find an entry. + //! 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. + //! find an entry, creating it if necessary. + //! nTime and nServices of the found node are updated, if necessary. CAddrInfo* Create(const CAddress &addr, const CNetAddr &addrSource, int *pnId = NULL); - // Swap two elements in vRandom. + //! Swap two elements in vRandom. void SwapRandom(unsigned int nRandomPos1, unsigned int nRandomPos2); - // Return position in given bucket to replace. + //! 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. + //! 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); - // Move an entry from the "new" table(s) to the "tried" table - // @pre vvUnkown[nOrigin].count(nId) != 0 + //! 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". + //! Mark an entry "good", possibly moving it from "new" to "tried". void Good_(const CService &addr, int64_t nTime); - // Add an entry to the "new" table. + //! Add an entry to the "new" table. bool Add_(const CAddress &addr, const CNetAddr& source, int64_t nTimePenalty); - // Mark an entry as attempted to connect. + //! Mark an entry as attempted to connect. void Attempt_(const CService &addr, int64_t nTime); - // Select an address to connect to. - // nUnkBias determines how much to favor new addresses over tried ones (min=0, max=100) + //! 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. + //! Perform consistency check. Returns an error code or zero. int Check_(); #endif - // Select several addresses at once. + //! Select several addresses at once. void GetAddr_(std::vector<CAddress> &vAddr); - // Mark an entry as currently-connected-to. + //! Mark an entry as currently-connected-to. void Connected_(const CService &addr, int64_t nTime); public: - // serialized format: - // * version byte (currently 0) - // * nKey - // * nNew - // * nTried - // * number of "new" buckets - // * all nNew addrinfos in vvNew - // * all nTried addrinfos 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. - // - // We don't use ADD_SERIALIZE_METHODS since the serialization and deserialization code has - // very little in common. + /** + * serialized format: + * * version byte (currently 0) + * * nKey + * * nNew + * * nTried + * * number of "new" buckets + * * all nNew addrinfos in vvNew + * * all nTried addrinfos 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. + * + * 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 { @@ -394,13 +401,13 @@ public: nNew = 0; } - // Return the number of (unique) addresses in all tables. + //! Return the number of (unique) addresses in all tables. int size() { return vRandom.size(); } - // Consistency check + //! Consistency check void Check() { #ifdef DEBUG_ADDRMAN @@ -413,7 +420,7 @@ public: #endif } - // Add a single address. + //! Add a single address. bool Add(const CAddress &addr, const CNetAddr& source, int64_t nTimePenalty = 0) { bool fRet = false; @@ -428,7 +435,7 @@ public: return fRet; } - // Add multiple addresses. + //! Add multiple addresses. bool Add(const std::vector<CAddress> &vAddr, const CNetAddr& source, int64_t nTimePenalty = 0) { int nAdd = 0; @@ -444,7 +451,7 @@ public: return nAdd > 0; } - // Mark an entry as accessible. + //! Mark an entry as accessible. void Good(const CService &addr, int64_t nTime = GetAdjustedTime()) { { @@ -455,7 +462,7 @@ public: } } - // Mark an entry as connection attempted to. + //! Mark an entry as connection attempted to. void Attempt(const CService &addr, int64_t nTime = GetAdjustedTime()) { { @@ -466,8 +473,10 @@ public: } } - // Choose an address to connect to. - // nUnkBias determines how much "new" entries are favored over "tried" ones (0-100). + /** + * 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; @@ -480,7 +489,7 @@ public: return addrRet; } - // Return a bunch of addresses, selected at random. + //! Return a bunch of addresses, selected at random. std::vector<CAddress> GetAddr() { Check(); @@ -493,7 +502,7 @@ public: return vAddr; } - // Mark an entry as currently-connected-to. + //! Mark an entry as currently-connected-to. void Connected(const CService &addr, int64_t nTime = GetAdjustedTime()) { { |