addrman: Fix new table bucketing during unserialization #20557

        const bool restore_bucketing{nUBuckets == ADDRMAN_NEW_BUCKET_COUNT &&

fixed

This comment is weird in general. I don't think we have anything like ADDRMAN_UNKNOWN_BUCKET_COUNT anymore?

Should be talking about ADDRMAN_NEW_BUCKET_COUNT, ADDRMAN_NEW_BUCKETS_PER_ADDRESS.

Thanks, changed to ADDRMAN_NEW_BUCKET_COUNT.

So this happens if a new version of Bitcoin Core reduced ADDRMAN_NEW_BUCKETS_PER_ADDRESS, and in this case we completely forget the extra addrs.

Why do you think it's more reasonable? Assuming addrman is less-than-half-full, there's a good chance this odd addr can find a new place without evicting anything.

Because ADDRMAN_NEW_BUCKETS_PER_ADDRESS should be an invariant in addrman. No entry should appear in no more than ADDRMAN_NEW_BUCKETS_PER_ADDRESS buckets.

@naumenkogs if a new Bitcoin Core reduces ADDRMAN_NEW_BUCKETS_PER_ADDRESS from 8 to e.g. 6 and this condition becomes true in the new version, then the address is already in 6 buckets in memory. So we would not completely forget it, or do I miss something?

In commit "[addrman] Don't rebucket new table entries unnecessarily" (a5c9b04959f443372400f9a736c6eaf5502284a1)

It would be good if comment could say when this condition happens. Particularly if there is any case where it's expected to happen, or if it can only happen loading bad data.

Also, discarding entries after max buckets reached seems like another subtle change in behavior that could benefit from a simple unit test. (Or if this an unimportant edge case that doesn't merit a test, maybe it also doesn't merit special handling in the code.)

I'll expand this comment in a follow-up.

I find it hard to parse "restore the entry's new buckets".

1. Not only buckets, but also positions.
2. What exactly is "restore" is also a bit unclear, I'm thinking if there's a better verb. Perhaps just "use the serialized [...]"

Changed wording to "If the bucket count and asmap checksum haven't changed, then attempt to restore the entries to the buckets/positions they were in before serialization." Hopefully that's clearer!

Just to clarify... this is the number of entries in this bucket, right? Not the capacity of the bucket, which is ADDRMAN_BUCKET_SIZE?

Exactly (see the comment above about serialization format: https://github.com/jnewbery/bitcoin/blob/dbdf63c6d82ae8d1ca73f11d1b8844614f0bf8e3/src/addrman.h#L341)

I just thought both being called "size" is a bit confusing so num_entries would have been my choice for naming, but it's the nittiest of nits, non-blocking

I agree that this is confusing. I've renamed to num_entries.

So you're removing the format >= Format::V2_ASMAP condition here because otherwise it'd be impossible for serialized_asmap_checksum == supplied_asmap_checksum yes?

Correct. If format == V1_DETERMINISTIC, then serialized_asmap_checksum must be 0.

vVector does not exist. More importantly - none of the members is serialized explicitly/directly. So, I think the following changes would make a better description of the source code:

diff --git i/src/addrman.h w/src/addrman.h
index cde864f25..983a1f4fd 100644
--- i/src/addrman.h
+++ w/src/addrman.h
@@ -332,29 +332,26 @@ public:
      *     (format=5, lowest_compatible=5) and so any versions that do not know how to parse
      *     format=5 will not try to read the file.
      * * nKey
      * * nNew
      * * nTried
      * * number of "new" buckets XOR 2**30
-     * * all nNew addrinfos in vvNew
-     * * all nTried addrinfos in vvTried
-     * * for each bucket:
+     * * all new addresses (total count: nNew)
+     * * all tried addresses (total count: nTried)
+     * * for each new bucket:
      *   * number of elements
-     *   * for each element: index
+     *   * for each element: index in the serialized "all new addresses"
      * * asmap checksum
      *
      * 2**30 is xorred with the number of buckets to make addrman deserializer v0 detect it
      * as incompatible. This is necessary because it did not check the version number on
      * deserialization.
      *
-     * Notice that vvTried, mapAddr and vVector are never encoded explicitly;
+     * Notice that vvNew, vvTried, mapAddr, mapInfo and vRandom are never encoded explicitly;
      * they are instead reconstructed from the other information.
      *
-     * vvNew is serialized, but only used if ADDRMAN_NEW_BUCKET_COUNT and the asmap checksum
-     * 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 SERIALIZE_METHODS since the serialization and deserialization code has
      * very little in common.
      */

Why vvNew is not serialized? Because vvNew[i][j] contains the id under which the element can be found in mapInfo. We serialize a condensed version of vvNew (without the -1s), but instead of that id we store an index in the serialized list of CAddrInfo which exists only on disk.

Good suggestions. I've added a new commit that makes these changes.

Thanks! s/vVector/vRandom/ in that commit - there is no member named vVector. Also, consider adding mapInfo to the list of members that "are never encoded explicitly" - the ids (the keys of that map) are not serialized, only the values (and in different order than in the map).

Thanks. I applied the diff by hand and missed those. Now fixed!

Under what conditions could it happen that restore_bucketing is false and vvNew[bucket][bucket_position] != -1 (occupied)?

Is it only if ADDRMAN_BUCKET_SIZE has been changed? If that has happened then we shouldn't try to restore the bucketing (i.e. should set restore_bucketing to false), but unfortunately the old ADDRMAN_BUCKET_SIZE is not saved on disk, so we can only indirectly observe that the file was written with a different ADDRMAN_BUCKET_SIZE.

(the above is not a suggestion for a change, just a few questions to confirm my understanding is correct)

If both restore_bucketing is false and vvNew[bucket][bucket_position] != -1 then it means that two addresses hash into the same position in the same new bucket, which is possible based on the source address. restore_bucketing would be false if the number of new buckets had changed or the as map had changed.

Yes! So it follows that (correct me if I am wrong):

• If restore_bucketing is true then vvNew[bucket][bucket_position] == -1 is also true (position is free, not occupied). So the if condition can be reduced to just if (restore_bucketing) {.

• If restore_bucketing is false then vvNew[bucket][bucket_position] == -1 may be true or false depending on the hashing. In this case too, the if condition is equivalent to just if (restore_bucketing) {.

I think vvNew[bucket][bucket_position] == -1 is just a belt-and-suspenders. It shouldn't be hit (if so, then something has gone wrong with the position serializing/deserializing to place two addresses in the same bucket/position). I think you're right that we can just remove it, but can we leave that as a follow-up? We can't fix all of addrman's problems in one PR :)

Alright, so either we are both correct that this is redundant and not needed, or we are both wrong!

If we are wrong, and it can happen that restore_bucketing is true and vvNew[bucket][bucket_position] == -1 is false (occupied!) then moving the LogPrint() call was wrong because it would have been executed inside the else branch and now it will not be executed because now it is conditional only on restore_bucketing.

If restore_bucketing is false, then this will be printed for every address, possibly many times. But it does not include the address itself. What about printing the address:

                LogPrint(BCLog::ADDRMAN, "Bucketing method was updated, re-bucketing addrman entry from disk for %s\n", info.ToString());

or print the generic message once:

                if (!printed) {
                    LogPrint(BCLog::ADDRMAN, "Bucketing method was updated, re-bucketing addrman entries from disk\n");
                    printed = true;
                }

Good catch! I'm just going to move the log to outside the loop to avoid it printing many times. Only printing once seems to be the original intent of this log. Improved logging can be left for a future PR.

s/restore_bucketing/!restore_bucketing/ in 9a0760db4?

:man_facepalming: You're right of course. I'll fix.

In commit "[addrman] Fix new table bucketing during unserialization" (b4c5fda417dd9ff8bf9fe24a87d384a649e3730d)

Could avoid some verbosity here with

-        for (auto bucket_entry : bucket_entries) {
-            int bucket{bucket_entry.first};
-            const int n{bucket_entry.second};
+        for (auto [bucket, n] : bucket_entries) {

:heart: structured bindings. Good suggestion. I'll do in a follow-up.

In commit "[addrman] Fix new table bucketing during unserialization" (b4c5fda417dd9ff8bf9fe24a87d384a649e3730d)

Seems like having a data structure here is superfluous if it's just going to be filled up then immediately iterated over and discarded. Maybe it would make sense to remove this vector later.

I think that vector could be avoided only if we could seek into the stream. Then we could change the current:

read new buckets
read asmap checksum
process the new buckets that were read, depending on the asmap checksum

to

seek forward and read the asmap checksum (last 32 bytes)
seek back and read+process the new bucketing data, depending on the asmap checksum

We only know how we're going to use the vector after we've deserialized the asmap_checksum field, so I don't think we can get rid of it.

In commit "[addrman] Fix new table bucketing during unserialization" (b4c5fda417dd9ff8bf9fe24a87d384a649e3730d)

It would be good to have some test coverage for this. A functional test might be hard but I would think a c++ unit test should be straightforward. Past bugs predict future bugs so a test here could steer coverage in a useful direction.

A test is in the baking at https://github.com/jnewbery/bitcoin/pull/18.

I definitely agree. @vasild has a test here: https://github.com/jnewbery/bitcoin/pull/18 which can be added after this PR.

The old code iterates over mapInfo[0..nNew], so we were guaranteed that all CAddrInfos in the new table make their way into vvNew (either in the old buckets, or newly assigned ones in the else block below). With the new code, we have an implicit assumption that bucket_entries.size() == nNew. Is that safe to assume? I think it is but just wanted to ask since we are iterating over a different part of the serialized data now.

I think bucket_entries.size() >= nNew, let me use an example:

mapInfo[id=3] = 1.1.1.1
// for the example, I pick up some arbitrary indexes in vvNew
vvNew[2][5] = id=3
vvNew[4][9] = id=3
nNew = 1

This would be serialized on disk as:

1 (nNew)
0 (nTried)
1024 (new_bucket_count)
1.1.1.1 (list of new addresses) (*)
(zero tried addresses)
0 (number of elements in vvNew[0])
0 (number of elements in vvNew[1])
1 (number of elements in vvNew[2])
0 (the index in (*) of the first non empty element in vvNew[2])
0 (number of elements in vvNew[3])
1 (number of elements in vvNew[4])
0 (the index in (*) of the first non empty element in vvNew[4])
0 (number of elements in vvNew[5])
...
0 (number of elements in vvNew[1023])

During unserialization, in the new code from this PR, this will result in:

bucket_entries[0] = (bucket = 2, index in (*) = 0)
bucket_entries[1] = (bucket = 4, index in (*) = 0)

So, bucket_entries.size() = 2 while nNew = 1.

This was part of the bug that this PR fixes. nNew is the total number of new addrs. Each new addr can appear in more than one new bucket, so the number of entries in bucket_entries could be higher than nNew. The old code was potentially throwing away these additional placements.

(nit) since entry_index can be confused with the for-loop index, perhaps entry_id is better (to match nIdCount)?

That variable entry_index describes the index of the address in the disk-only list of new addresses (marked as (*) in the comment above).

I think that should not be confused with the in-memory-only "id" and entry_index describes it well.

I think that's a reasonable suggestion, but not worth invalidating the existing ACKs.

Thank you! I actually tripped over this while reading the old code.

(nit) could this is a scripted-diff?

(nit) could this is a scripted-diff?

Scripted diffs are useful when there are many occurrences of a string across multiple files. This string is used in 7 places, so is easy enough to review by eye.

In the format above aren't lines 340-342 an encoding of vvNew? If so, why remove this comment?

No, because the memory-only id may not equal to the disk-only index in the serialized "all new addresses".

See the line above. vvNew isn't encoded explicitly but is reconstructed.

In commit "[addrman] Don't rebucket new table entries unnecessarily" (a5c9b04959f443372400f9a736c6eaf5502284a1)

Just some notes to make sure I'm following this correctly.

• The restore_bucketing change here is aesthetic and the only actual change this line is dropping the format >= Format::V2_ASMAP condition.
• The effect of dropping format condition is this will now keep existing bucket positions instead of rebucketing when an old format is loaded and there is no asmap. ("Only rebucket if" in commit description means "Use existing bucket positions if")
• In the case where an old format is loaded an there is an asmap, this logic isn't triggered because the serialized_asmap_checksum == supplied_asmap_checksum condition is false.
• Maybe could be a unit test checking old format number + no asmap uses existing bucket positions

The restore_bucketing change here is aesthetic and the only actual change this line is dropping the format >= Format::V2_ASMAP condition.

Right, this condition doesn't change during loop iterations, so it's clearer to move it out of the loop, mark it const, and only do a conditional check inside the loop on what can change over iterations.

The effect of dropping format condition is this will now keep existing bucket positions instead of rebucketing when an old format is loaded and there is no asmap. ("Only rebucket if" in commit description means "Use existing bucket positions if")

That's right. If the file format is old (no asmap), and we don't have an asmap, then we gain nothing by dropping new bucket positions.

In the case where an old format is loaded an there is an asmap, this logic isn't triggered because the serialized_asmap_checksum == supplied_asmap_checksum condition is false.

Right.

Maybe could be a unit test checking old format number + no asmap uses existing bucket positions

Perhaps. It's a bit difficult to test because we can't easily serialize addrman in the old format.