Merge bitcoin/bitcoin#16981: Improve runtime performance of --reindex

db929893ef0bc86ea2708cdbcf41152240cd7c73 Faster -reindex by initially deserializing only headers (Larry Ruane)
c72de9990ae8f1744006d9c852023b882d5ed80c util: add CBufferedFile::SkipTo() to move ahead in the stream (Larry Ruane)
48a68908ba3d5e077cda7bd1e908b923fbead824 Add LoadExternalBlockFile() benchmark (Larry Ruane)

Pull request description:

  ### Background
  During the first part of reindexing, `LoadExternalBlockFile()` sequentially reads raw blocks from the `blocks/blk00nnn.dat` files (rather than receiving them from peers, as with initial block download) and eventually adds all of them to the block index. When an individual block is initially read, it can't be immediately added unless all its ancestors have been added, which is rare (only about 8% of the time), because the blocks are not sorted by height. When the block can't be immediately added to the block index, its disk location is saved in a map so it can be added later. When its parent is later added to the block index, `LoadExternalBlockFile()` reads and deserializes the block from disk a second time and adds it to the block index. Most blocks (92%) get deserialized twice.

  ### This PR
  During the initial read, it's rarely useful to deserialize the entire block; only the header is needed to determine if the block can be added to the block index immediately. This change to `LoadExternalBlockFile()` initially deserializes only a block's header, then deserializes the entire block only if it can be added immediately. This reduces reindex time on mainnet by 7 hours on a Raspberry Pi, which translates to around a 25% reduction in the first part of reindexing (adding blocks to the index), and about a 6% reduction in overall reindex time.

  Summary: The performance gain is the result of deserializing each block only once, except its header which is deserialized twice, but the header is only 80 bytes.

ACKs for top commit:
  andrewtoth:
    ACK db929893ef0bc86ea2708cdbcf41152240cd7c73
  achow101:
    ACK db929893ef0bc86ea2708cdbcf41152240cd7c73
  aureleoules:
    ACK db929893ef0bc86ea2708cdbcf41152240cd7c73 - minor changes and new benchmark since last review
  theStack:
    re-ACK db929893ef0bc86ea2708cdbcf41152240cd7c73
  stickies-v:
    re-ACK db929893e

Tree-SHA512: 5a5377192c11edb5b662e18f511c9beb8f250bc88aeadf2f404c92c3232a7617bade50477ebf16c0602b9bd3b68306d3ee7615de58acfd8cae664d28bb7b0136

1 files changed, 50 insertions, 0 deletions

diff --git a/test/functional/feature_reindex.py b/test/functional/feature_reindex.py
index 44040f426f..0f6a8fd0d2 100755
--- a/test/functional/feature_reindex.py
+++ b/test/functional/feature_reindex.py
@@ -7,9 +7,12 @@
 - Start a single node and generate 3 blocks.
 - Stop the node and restart it with -reindex. Verify that the node has reindexed up to block 3.
 - Stop the node and restart it with -reindex-chainstate. Verify that the node has reindexed up to block 3.
+- Verify that out-of-order blocks are correctly processed, see LoadExternalBlockFile()
 """
 
+import os
 from test_framework.test_framework import BitcoinTestFramework
+from test_framework.p2p import MAGIC_BYTES
 from test_framework.util import assert_equal
 
 
@@ -27,11 +30,58 @@ class ReindexTest(BitcoinTestFramework):
         assert_equal(self.nodes[0].getblockcount(), blockcount)  # start_node is blocking on reindex
         self.log.info("Success")
 
+    # Check that blocks can be processed out of order
+    def out_of_order(self):
+        # The previous test created 12 blocks
+        assert_equal(self.nodes[0].getblockcount(), 12)
+        self.stop_nodes()
+
+        # In this test environment, blocks will always be in order (since
+        # we're generating them rather than getting them from peers), so to
+        # test out-of-order handling, swap blocks 1 and 2 on disk.
+        blk0 = os.path.join(self.nodes[0].datadir, self.nodes[0].chain, 'blocks', 'blk00000.dat')
+        with open(blk0, 'r+b') as bf:
+            # Read at least the first few blocks (including genesis)
+            b = bf.read(2000)
+
+            # Find the offsets of blocks 2, 3, and 4 (the first 3 blocks beyond genesis)
+            # by searching for the regtest marker bytes (see pchMessageStart).
+            def find_block(b, start):
+                return b.find(MAGIC_BYTES["regtest"], start)+4
+
+            genesis_start = find_block(b, 0)
+            assert_equal(genesis_start, 4)
+            b2_start = find_block(b, genesis_start)
+            b3_start = find_block(b, b2_start)
+            b4_start = find_block(b, b3_start)
+
+            # Blocks 2 and 3 should be the same size.
+            assert_equal(b3_start-b2_start, b4_start-b3_start)
+
+            # Swap the second and third blocks (don't disturb the genesis block).
+            bf.seek(b2_start)
+            bf.write(b[b3_start:b4_start])
+            bf.write(b[b2_start:b3_start])
+
+        # The reindexing code should detect and accommodate out of order blocks.
+        with self.nodes[0].assert_debug_log([
+            'LoadExternalBlockFile: Out of order block',
+            'LoadExternalBlockFile: Processing out of order child',
+        ]):
+            extra_args = [["-reindex"]]
+            self.start_nodes(extra_args)
+
+        # All blocks should be accepted and processed.
+        assert_equal(self.nodes[0].getblockcount(), 12)
+
     def run_test(self):
         self.reindex(False)
         self.reindex(True)
         self.reindex(False)
         self.reindex(True)
 
+        self.out_of_order()
+
+
 if __name__ == '__main__':
     ReindexTest().main()