1// Copyright (c) 2012 Pieter Wuille
2// Copyright (c) 2012-present The Bitcoin Core developers
3// Distributed under the MIT software license, see the accompanying
4// file COPYING or http://www.opensource.org/licenses/mit-license.php.
5
6#include <bitcoin-build-config.h> // IWYU pragma: keep
7
8#include <addrman.h>
9#include <addrman_impl.h>
10
11#include <hash.h>
12#include <logging/timer.h>
13#include <netaddress.h>
14#include <netgroup.h>
15#include <protocol.h>
16#include <random.h>
17#include <serialize.h>
18#include <streams.h>
19#include <tinyformat.h>
20#include <uint256.h>
21#include <util/check.h>
22#include <util/log.h>
23#include <util/time.h>
24
25#include <cmath>
26#include <optional>
27
28
29int AddrInfo::GetTriedBucket(const uint256& nKey, const NetGroupManager& netgroupman) const
30{
31    uint64_t hash1 = (HashWriter{} << nKey << GetKey()).GetCheapHash();
32    uint64_t hash2 = (HashWriter{} << nKey << netgroupman.GetGroup(*this) << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP)).GetCheapHash();
33    return hash2 % ADDRMAN_TRIED_BUCKET_COUNT;
34}
35
36int AddrInfo::GetNewBucket(const uint256& nKey, const CNetAddr& src, const NetGroupManager& netgroupman) const
37{
38    std::vector<unsigned char> vchSourceGroupKey = netgroupman.GetGroup(src);
39    uint64_t hash1 = (HashWriter{} << nKey << netgroupman.GetGroup(*this) << vchSourceGroupKey).GetCheapHash();
40    uint64_t hash2 = (HashWriter{} << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP)).GetCheapHash();
41    return hash2 % ADDRMAN_NEW_BUCKET_COUNT;
42}
43
44int AddrInfo::GetBucketPosition(const uint256& nKey, bool fNew, int bucket) const
45{
46    uint64_t hash1 = (HashWriter{} << nKey << (fNew ? uint8_t{'N'} : uint8_t{'K'}) << bucket << GetKey()).GetCheapHash();
47    return hash1 % ADDRMAN_BUCKET_SIZE;
48}
49
50bool AddrInfo::IsTerrible(NodeSeconds now) const
51{
52    if (now - m_last_try <= 1min) { // never remove things tried in the last minute
53        return false;
54    }
55
56    if (nTime > now + 10min) { // came in a flying DeLorean
57        return true;
58    }
59
60    if (now - nTime > ADDRMAN_HORIZON) { // not seen in recent history
61        return true;
62    }
63
64    if (TicksSinceEpoch<std::chrono::seconds>(m_last_success) == 0 && nAttempts >= ADDRMAN_RETRIES) { // tried N times and never a success
65        return true;
66    }
67
68    if (now - m_last_success > ADDRMAN_MIN_FAIL && nAttempts >= ADDRMAN_MAX_FAILURES) { // N successive failures in the last week
69        return true;
70    }
71
72    return false;
73}
74
75double AddrInfo::GetChance(NodeSeconds now) const
76{
77    double fChance = 1.0;
78
79    // deprioritize very recent attempts away
80    if (now - m_last_try < 10min) {
81        fChance *= 0.01;
82    }
83
84    // deprioritize 66% after each failed attempt, but at most 1/28th to avoid the search taking forever or overly penalizing outages.
85    fChance *= pow(0.66, std::min(nAttempts, 8));
86
87    return fChance;
88}
89
90AddrManImpl::AddrManImpl(const NetGroupManager& netgroupman, bool deterministic, int32_t consistency_check_ratio)
91    : insecure_rand{deterministic}
92    , nKey{deterministic ? uint256{1} : insecure_rand.rand256()}
93    , m_consistency_check_ratio{consistency_check_ratio}
94    , m_netgroupman{netgroupman}
95{
96    for (auto& bucket : vvNew) {
97        for (auto& entry : bucket) {
98            entry = -1;
99        }
100    }
101    for (auto& bucket : vvTried) {
102        for (auto& entry : bucket) {
103            entry = -1;
104        }
105    }
106}
107
108AddrManImpl::~AddrManImpl()
109{
110    nKey.SetNull();
111}
112
113template <typename Stream>
114void AddrManImpl::Serialize(Stream& s_) const
115{
116    LOCK(cs);
117
118    /**
119     * Serialized format.
120     * * format version byte (@see `Format`)
121     * * lowest compatible format version byte. This is used to help old software decide
122     *   whether to parse the file. For example:
123     *   * Bitcoin Core version N knows how to parse up to format=3. If a new format=4 is
124     *     introduced in version N+1 that is compatible with format=3 and it is known that
125     *     version N will be able to parse it, then version N+1 will write
126     *     (format=4, lowest_compatible=3) in the first two bytes of the file, and so
127     *     version N will still try to parse it.
128     *   * Bitcoin Core version N+2 introduces a new incompatible format=5. It will write
129     *     (format=5, lowest_compatible=5) and so any versions that do not know how to parse
130     *     format=5 will not try to read the file.
131     * * nKey
132     * * nNew
133     * * nTried
134     * * number of "new" buckets XOR 2**30
135     * * all new addresses (total count: nNew)
136     * * all tried addresses (total count: nTried)
137     * * for each new bucket:
138     *   * number of elements
139     *   * for each element: index in the serialized "all new addresses"
140     * * asmap version
141     *
142     * 2**30 is xorred with the number of buckets to make addrman deserializer v0 detect it
143     * as incompatible. This is necessary because it did not check the version number on
144     * deserialization.
145     *
146     * vvNew, vvTried, mapInfo, mapAddr and vRandom are never encoded explicitly;
147     * they are instead reconstructed from the other information.
148     *
149     * This format is more complex, but significantly smaller (at most 1.5 MiB), and supports
150     * changes to the ADDRMAN_ parameters without breaking the on-disk structure.
151     *
152     * We don't use SERIALIZE_METHODS since the serialization and deserialization code has
153     * very little in common.
154     */
155
156    // Always serialize in the latest version (FILE_FORMAT).
157    ParamsStream s{s_, CAddress::V2_DISK};
158
159    s << static_cast<uint8_t>(FILE_FORMAT);
160
161    // Increment `lowest_compatible` iff a newly introduced format is incompatible with
162    // the previous one.
163    static constexpr uint8_t lowest_compatible = Format::V4_MULTIPORT;
164    s << static_cast<uint8_t>(INCOMPATIBILITY_BASE + lowest_compatible);
165
166    s << nKey;
167    s << nNew;
168    s << nTried;
169
170    int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT ^ (1 << 30);
171    s << nUBuckets;
172    std::unordered_map<nid_type, int> mapUnkIds;
173    int nIds = 0;
174    for (const auto& entry : mapInfo) {
175        mapUnkIds[entry.first] = nIds;
176        const AddrInfo& info = entry.second;
177        if (info.nRefCount) {
178            assert(nIds != nNew); // this means nNew was wrong, oh ow
179            s << info;
180            nIds++;
181        }
182    }
183    nIds = 0;
184    for (const auto& entry : mapInfo) {
185        const AddrInfo& info = entry.second;
186        if (info.fInTried) {
187            assert(nIds != nTried); // this means nTried was wrong, oh ow
188            s << info;
189            nIds++;
190        }
191    }
192    for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
193        int nSize = 0;
194        for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
195            if (vvNew[bucket][i] != -1)
196                nSize++;
197        }
198        s << nSize;
199        for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
200            if (vvNew[bucket][i] != -1) {
201                int nIndex = mapUnkIds[vvNew[bucket][i]];
202                s << nIndex;
203            }
204        }
205    }
206    // Store asmap version after bucket entries so that it
207    // can be ignored by older clients for backward compatibility.
208    s << m_netgroupman.GetAsmapVersion();
209}
210
211template <typename Stream>
212void AddrManImpl::Unserialize(Stream& s_)
213{
214    LOCK(cs);
215
216    assert(vRandom.empty());
217
218    Format format;
219    s_ >> Using<CustomUintFormatter<1>>(format);
220
221    const auto ser_params = (format >= Format::V3_BIP155 ? CAddress::V2_DISK : CAddress::V1_DISK);
222    ParamsStream s{s_, ser_params};
223
224    uint8_t compat;
225    s >> compat;
226    if (compat < INCOMPATIBILITY_BASE) {
227        throw std::ios_base::failure(strprintf(
228            "Corrupted addrman database: The compat value (%u) "
229            "is lower than the expected minimum value %u.",
230            compat, INCOMPATIBILITY_BASE));
231    }
232    const uint8_t lowest_compatible = compat - INCOMPATIBILITY_BASE;
233    if (lowest_compatible > FILE_FORMAT) {
234        throw InvalidAddrManVersionError(strprintf(
235            "Unsupported format of addrman database: %u. It is compatible with formats >=%u, "
236            "but the maximum supported by this version of %s is %u.",
237            uint8_t{format}, lowest_compatible, CLIENT_NAME, uint8_t{FILE_FORMAT}));
238    }
239
240    s >> nKey;
241    s >> nNew;
242    s >> nTried;
243    int nUBuckets = 0;
244    s >> nUBuckets;
245    if (format >= Format::V1_DETERMINISTIC) {
246        nUBuckets ^= (1 << 30);
247    }
248
249    if (nNew > ADDRMAN_NEW_BUCKET_COUNT * ADDRMAN_BUCKET_SIZE || nNew < 0) {
250        throw std::ios_base::failure(