Coverage Report

Created: 2026-04-29 19:21

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/tmp/bitcoin/src/wallet/migrate.cpp
Line
Count
Source
1
// Copyright (c) 2024-present The Bitcoin Core developers
2
// Distributed under the MIT software license, see the accompanying
3
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5
#include <compat/byteswap.h>
6
#include <crypto/common.h>
7
#include <logging.h>
8
#include <streams.h>
9
#include <util/translation.h>
10
#include <wallet/migrate.h>
11
12
#include <array>
13
#include <cstddef>
14
#include <optional>
15
#include <stdexcept>
16
#include <variant>
17
#include <vector>
18
19
namespace wallet {
20
// Magic bytes in both endianness's
21
constexpr uint32_t BTREE_MAGIC = 0x00053162;    // If the file endianness matches our system, we see this magic
22
constexpr uint32_t BTREE_MAGIC_OE = 0x62310500; // If the file endianness is the other one, we will see this magic
23
24
// Subdatabase name
25
static const std::vector<std::byte> SUBDATABASE_NAME = {std::byte{'m'}, std::byte{'a'}, std::byte{'i'}, std::byte{'n'}};
26
27
enum class PageType : uint8_t {
28
    /*
29
     * BDB has several page types, most of which we do not use
30
     * They are listed here for completeness, but commented out
31
     * to avoid opening something unintended.
32
    INVALID = 0,         // Invalid page type
33
    DUPLICATE = 1,       // Duplicate. Deprecated and no longer used
34
    HASH_UNSORTED = 2,   // Hash pages. Deprecated.
35
    RECNO_INTERNAL = 4,  // Recno internal
36
    RECNO_LEAF = 6,      // Recno leaf
37
    HASH_META = 8,       // Hash metadata
38
    QUEUE_META = 10,     // Queue Metadata
39
    QUEUE_DATA = 11,     // Queue Data
40
    DUPLICATE_LEAF = 12, // Off-page duplicate leaf
41
    HASH_SORTED = 13,    // Sorted hash page
42
    */
43
    BTREE_INTERNAL = 3, // BTree internal
44
    BTREE_LEAF = 5,     // BTree leaf
45
    OVERFLOW_DATA = 7,  // Overflow
46
    BTREE_META = 9,     // BTree metadata
47
};
48
49
enum class RecordType : uint8_t {
50
    KEYDATA = 1,
51
    // DUPLICATE = 2,       Unused as our databases do not support duplicate records
52
    OVERFLOW_DATA = 3,
53
    DELETE_FLAG = 0x80, // Indicate this record is deleted. This is OR'd with the real type.
54
};
55
56
enum class BTreeFlags : uint32_t {
57
    /*
58
     * BTree databases have feature flags, but we do not use them except for
59
     * subdatabases. The unused flags are included for completeness, but commented out
60
     * to avoid accidental use.
61
    DUP = 1,         // Duplicates
62
    RECNO = 2,       // Recno tree
63
    RECNUM = 4,      // BTree: Maintain record counts
64
    FIXEDLEN = 8,    // Recno: fixed length records
65
    RENUMBER = 0x10, // Recno: renumber on insert/delete
66
    DUPSORT = 0x40,  // Duplicates are sorted
67
    COMPRESS = 0x80, // Compressed
68
    */
69
    SUBDB = 0x20, // Subdatabases
70
};
71
72
/** Berkeley DB BTree metadata page layout */
73
class MetaPage
74
{
75
public:
76
    uint32_t lsn_file;             // Log Sequence Number file
77
    uint32_t lsn_offset;           // Log Sequence Number offset
78
    uint32_t page_num;             // Current page number
79
    uint32_t magic;                // Magic number
80
    uint32_t version;              // Version
81
    uint32_t pagesize;             // Page size
82
    uint8_t encrypt_algo;          // Encryption algorithm
83
    PageType type;                 // Page type
84
    uint8_t metaflags;             // Meta-only flags
85
    uint8_t unused1;               // Unused
86
    uint32_t free_list;            // Free list page number
87
    uint32_t last_page;            // Page number of last page in db
88
    uint32_t partitions;           // Number of partitions
89
    uint32_t key_count;            // Cached key count
90
    uint32_t record_count;         // Cached record count
91
    BTreeFlags flags;              // Flags
92
    std::array<std::byte, 20> uid; // 20 byte unique file ID
93
    uint32_t unused2;              // Unused
94
    uint32_t minkey;               // Minimum key
95
    uint32_t re_len;               // Recno: fixed length record length
96
    uint32_t re_pad;               // Recno: fixed length record pad
97
    uint32_t root;                 // Root page number
98
    char unused3[368];             // 92 * 4 bytes of unused space
99
    uint32_t crypto_magic;         // Crypto magic number
100
    char trash[12];                // 3 * 4 bytes of trash space
101
    unsigned char iv[20];          // Crypto IV
102
    unsigned char chksum[16];      // Checksum
103
104
    bool other_endian;
105
    uint32_t expected_page_num;
106
107
92
    MetaPage(uint32_t expected_page_num) : expected_page_num(expected_page_num) {}
108
    MetaPage() = delete;
109
110
    template <typename Stream>
111
    void Unserialize(Stream& s)
112
92
    {
113
92
        s >> lsn_file;
114
92
        s >> lsn_offset;
115
92
        s >> page_num;
116
92
        s >> magic;
117
92
        s >> version;
118
92
        s >> pagesize;
119
92
        s >> encrypt_algo;
120
121
92
        other_endian = magic == BTREE_MAGIC_OE;
122
123
92
        uint8_t uint8_type;
124
92
        s >> uint8_type;
125
92
        type = static_cast<PageType>(uint8_type);
126
127
92
        s >> metaflags;
128
92
        s >> unused1;
129
92
        s >> free_list;
130
92
        s >> last_page;
131
92
        s >> partitions;
132
92
        s >> key_count;
133
92
        s >> record_count;
134
135
92
        uint32_t uint32_flags;
136
92
        s >> uint32_flags;
137
92
        if (other_endian) {
138
0
            uint32_flags = internal_bswap_32(uint32_flags);
139
0
        }
140
92
        flags = static_cast<BTreeFlags>(uint32_flags);
141
142
92
        s >> uid;
143
92
        s >> unused2;
144
92
        s >> minkey;
145
92
        s >> re_len;
146
92
        s >> re_pad;
147
92
        s >> root;
148
92
        s >> unused3;
149
92
        s >> crypto_magic;
150
92
        s >> trash;
151
92
        s >> iv;
152
92
        s >> chksum;
153
154
92
        if (other_endian) {
155
0
            lsn_file = internal_bswap_32(lsn_file);
156
0
            lsn_offset = internal_bswap_32(lsn_offset);
157
0
            page_num = internal_bswap_32(page_num);
158
0
            magic = internal_bswap_32(magic);
159
0
            version = internal_bswap_32(version);
160
0
            pagesize = internal_bswap_32(pagesize);
161
0
            free_list = internal_bswap_32(free_list);
162
0
            last_page = internal_bswap_32(last_page);
163
0
            partitions = internal_bswap_32(partitions);
164
0
            key_count = internal_bswap_32(key_count);
165
0
            record_count = internal_bswap_32(record_count);
166
0
            unused2 = internal_bswap_32(unused2);
167
0
            minkey = internal_bswap_32(minkey);
168
0
            re_len = internal_bswap_32(re_len);
169
0
            re_pad = internal_bswap_32(re_pad);
170
0
            root = internal_bswap_32(root);
171
0
            crypto_magic = internal_bswap_32(crypto_magic);
172
0
        }
173
174
        // Page number must match
175
92
        if (page_num != expected_page_num) {
176
0
            throw std::runtime_error("Meta page number mismatch");
177
0
        }
178
179
        // Check magic
180
92
        if (magic != BTREE_MAGIC) {
181
0
            throw std::runtime_error("Not a BDB file");
182
0
        }
183
184
        // Only version 9 is supported
185
92
        if (version != 9) {
186
0
            throw std::runtime_error("Unsupported BDB data file version number");
187
0
        }
188
189
        // Page size must be 512 <= pagesize <= 64k, and be a power of 2
190
92
        if (pagesize < 512 || pagesize > 65536 || (pagesize & (pagesize - 1)) != 0) {
191
0
            throw std::runtime_error("Bad page size");
192
0
        }
193
194
        // Page type must be the btree type
195
92
        if (type != PageType::BTREE_META) {
196
0
            throw std::runtime_error("Unexpected page type, should be 9 (BTree Metadata)");
197
0
        }
198
199
        // Only supported meta-flag is subdatabase
200
92
        if (flags != BTreeFlags::SUBDB) {
201
0
            throw std::runtime_error("Unexpected database flags, should only be 0x20 (subdatabases)");
202
0
        }
203
92
    }
204
};
205
206
/** General class for records in a BDB BTree database. Contains common fields. */
207
class RecordHeader
208
{
209
public:
210
    uint16_t len;    // Key/data item length
211
    RecordType type; // Page type (BDB has this; includes a DELETE_FLAG that we track separately)
212
    bool deleted;    // Whether the DELETE_FLAG was set on type
213
214
    static constexpr size_t SIZE = 3; // The record header is 3 bytes
215
216
    bool other_endian;
217
218
2.64k
    RecordHeader(bool other_endian) : other_endian(other_endian) {}
219
    RecordHeader() = delete;
220
221
    template <typename Stream>
222
    void Unserialize(Stream& s)
223
2.64k
    {
224
2.64k
        s >> len;
225
226
2.64k
        uint8_t uint8_type;
227
2.64k
        s >> uint8_type;
228
2.64k
        type = static_cast<RecordType>(uint8_type & ~static_cast<uint8_t>(RecordType::DELETE_FLAG));
229
2.64k
        deleted = uint8_type & static_cast<uint8_t>(RecordType::DELETE_FLAG);
230
231
2.64k
        if (other_endian) {
232
0
            len = internal_bswap_16(len);
233
0
        }
234
2.64k
    }
235
};
236
237
/** Class for data in the record directly */
238
class DataRecord
239
{
240
public:
241
2.60k
    DataRecord(const RecordHeader& header) : m_header(header) {}
242
    DataRecord() = delete;
243
244
    RecordHeader m_header;
245
246
    std::vector<std::byte> data; // Variable length key/data item
247
248
    template <typename Stream>
249
    void Unserialize(Stream& s)
250
2.60k
    {
251
2.60k
        data.resize(m_header.len);
252
2.60k
        s.read(std::as_writable_bytes(std::span(data.data(), data.size())));
253
2.60k
    }
254
};
255
256
/** Class for records representing internal nodes of the BTree. */
257
class InternalRecord
258
{
259
public:
260
41
    InternalRecord(const RecordHeader& header) : m_header(header) {}
261
    InternalRecord() = delete;
262
263
    RecordHeader m_header;
264
265
    uint8_t unused;              // Padding, unused
266
    uint32_t page_num;           // Page number of referenced page
267
    uint32_t records;            // Subtree record count
268
    std::vector<std::byte> data; // Variable length key item
269
270
    static constexpr size_t FIXED_SIZE = 9; // Size of fixed data is 9 bytes
271
272
    template <typename Stream>
273
    void Unserialize(Stream& s)
274
41
    {
275
41
        s >> unused;
276
41
        s >> page_num;
277
41
        s >> records;
278
279
41
        data.resize(m_header.len);
280
41
        s.read(std::as_writable_bytes(std::span(data.data(), data.size())));
281
282
41
        if (m_header.other_endian) {
283
0
            page_num = internal_bswap_32(page_num);
284
0
            records = internal_bswap_32(records);
285
0
        }
286
41
    }
287
};
288
289
/** Class for records representing overflow records of the BTree.
290
 * Overflow records point to a page which contains the data in the record.
291
 * Those pages may point to further pages with the rest of the data if it does not fit
292
 * in one page */
293
class OverflowRecord
294
{
295
public:
296
0
    OverflowRecord(const RecordHeader& header) : m_header(header) {}
297
    OverflowRecord() = delete;
298
299
    RecordHeader m_header;
300
301
    uint8_t unused2;      // Padding, unused
302
    uint32_t page_number; // Page number where data begins
303
    uint32_t item_len;    // Total length of item
304
305
    static constexpr size_t SIZE = 9; // Overflow record is always 9 bytes
306
307
    template <typename Stream>
308
    void Unserialize(Stream& s)
309
0
    {
310
0
        s >> unused2;
311
0
        s >> page_number;
312
0
        s >> item_len;
313
314
0
        if (m_header.other_endian) {
315
0
            page_number = internal_bswap_32(page_number);
316
0
            item_len = internal_bswap_32(item_len);
317
0
        }
318
0
    }
319
};
320
321
/** A generic data page in the database. Contains fields common to all data pages. */
322
class PageHeader
323
{
324
public:
325
    uint32_t lsn_file;   // Log Sequence Number file
326
    uint32_t lsn_offset; // Log Sequence Number offset
327
    uint32_t page_num;   // Current page number
328
    uint32_t prev_page;  // Previous page number
329
    uint32_t next_page;  // Next page number
330
    uint16_t entries;    // Number of items on the page
331
    uint16_t hf_offset;  // High free byte page offset
332
    uint8_t level;       // Btree page level
333
    PageType type;       // Page type
334
335
    static constexpr int64_t SIZE = 26; // The header is 26 bytes
336
337
    uint32_t expected_page_num;
338
    bool other_endian;
339
340
133
    PageHeader(uint32_t page_num, bool other_endian) : expected_page_num(page_num), other_endian(other_endian) {}
341
    PageHeader() = delete;
342
343
    template <typename Stream>
344
    void Unserialize(Stream& s)
345
133
    {
346
133
        s >> lsn_file;
347
133
        s >> lsn_offset;
348
133
        s >> page_num;
349
133
        s >> prev_page;
350
133
        s >> next_page;
351
133
        s >> entries;
352
133
        s >> hf_offset;
353
133
        s >> level;
354
355
133
        uint8_t uint8_type;
356
133
        s >> uint8_type;
357
133
        type = static_cast<PageType>(uint8_type);
358
359
133
        if (other_endian) {
360
0
            lsn_file = internal_bswap_32(lsn_file);
361
0
            lsn_offset = internal_bswap_32(lsn_offset);
362
0
            page_num = internal_bswap_32(page_num);
363
0
            prev_page = internal_bswap_32(prev_page);
364
0
            next_page = internal_bswap_32(next_page);
365
0
            entries = internal_bswap_16(entries);
366
0
            hf_offset = internal_bswap_16(hf_offset);
367
0
        }
368
369
133
        if (expected_page_num != page_num) {
370
0
            throw std::runtime_error("Page number mismatch");
371
0
        }
372
133
        if ((type != PageType::OVERFLOW_DATA && level < 1) || (type == PageType::OVERFLOW_DATA && level != 0)) {
373
0
            throw std::runtime_error("Bad btree level");
374
0
        }
375
133
    }
376
};
377
378
/** A page of records in the database */
379
class RecordsPage
380
{
381
public:
382
119
    RecordsPage(const PageHeader& header) : m_header(header) {}
383
    RecordsPage() = delete;
384
385
    PageHeader m_header;
386
387
    std::vector<uint16_t> indexes;
388
    std::vector<std::variant<DataRecord, OverflowRecord>> records;
389
390
    template <typename Stream>
391
    void Unserialize(Stream& s)
392
119
    {
393
        // Current position within the page
394
119
        int64_t pos = PageHeader::SIZE;
395
396
        // Get the items
397
2.72k
        for (uint32_t i = 0; i < m_header.entries; ++i) {
398
            // Get the index
399
2.60k
            uint16_t index;
400
2.60k
            s >> index;
401
2.60k
            if (m_header.other_endian) {
402
0
                index = internal_bswap_16(index);
403
0
            }
404
2.60k
            indexes.push_back(index);
405
2.60k
            pos += sizeof(uint16_t);
406
407
            // Go to the offset from the index
408
2.60k
            int64_t to_jump = index - pos;
409
2.60k
            if (to_jump < 0) {
410
0
                throw std::runtime_error("Data record position not in page");
411
0
            }
412
2.60k
            s.ignore(to_jump);
413
414
            // Read the record
415
2.60k
            RecordHeader rec_hdr(m_header.other_endian);
416
2.60k
            s >> rec_hdr;
417
2.60k
            to_jump += RecordHeader::SIZE;
418
419
2.60k
            switch (rec_hdr.type) {
420
2.60k
            case RecordType::KEYDATA: {
421
2.60k
                DataRecord record(rec_hdr);
422
2.60k
                s >> record;
423
2.60k
                records.emplace_back(record);
424
2.60k
                to_jump += rec_hdr.len;
425
2.60k
                break;
426
0
            }
427
0
            case RecordType::OVERFLOW_DATA: {
428
0
                OverflowRecord record(rec_hdr);
429
0
                s >> record;
430
0
                records.emplace_back(record);
431
0
                to_jump += OverflowRecord::SIZE;
432
0
                break;
433
0
            }
434
0
            default:
435
0
                throw std::runtime_error("Unknown record type in records page");
436
2.60k
            }
437
438
            // Go back to the indexes
439
2.60k
            s.seek(-to_jump, SEEK_CUR);
440
2.60k
        }
441
119
    }
442
};
443
444
/** A page containing overflow data */
445
class OverflowPage
446
{
447
public:
448
0
    OverflowPage(const PageHeader& header) : m_header(header) {}
449
    OverflowPage() = delete;
450
451
    PageHeader m_header;
452
453
    // BDB overloads some page fields to store overflow page data
454
    // hf_offset contains the length of the overflow data stored on this page
455
    // entries contains a reference count for references to this item
456
457
    // The overflow data itself. Begins immediately following header
458
    std::vector<std::byte> data;
459
460
    template <typename Stream>
461
    void Unserialize(Stream& s)
462
0
    {
463
0
        data.resize(m_header.hf_offset);
464
0
        s.read(std::as_writable_bytes(std::span(data.data(), data.size())));
465
0
    }
466
};
467
468
/** A page of records in the database */
469
class InternalPage
470
{
471
public:
472
14
    InternalPage(const PageHeader& header) : m_header(header) {}
473
    InternalPage() = delete;
474
475
    PageHeader m_header;
476
477
    std::vector<uint16_t> indexes;
478
    std::vector<InternalRecord> records;
479
480
    template <typename Stream>
481
    void Unserialize(Stream& s)
482
14
    {
483
        // Current position within the page
484
14
        int64_t pos = PageHeader::SIZE;
485
486
        // Get the items
487
55
        for (uint32_t i = 0; i < m_header.entries; ++i) {
488
            // Get the index
489
41
            uint16_t index;
490
41
            s >> index;
491
41
            if (m_header.other_endian) {
492
0
                index = internal_bswap_16(index);
493
0
            }
494
41
            indexes.push_back(index);
495
41
            pos += sizeof(uint16_t);
496
497
            // Go to the offset from the index
498
41
            int64_t to_jump = index - pos;
499
41
            if (to_jump < 0) {
500
0
                throw std::runtime_error("Internal record position not in page");
501
0
            }
502
41
            s.ignore(to_jump);
503
504
            // Read the record
505
41
            RecordHeader rec_hdr(m_header.other_endian);
506
41
            s >> rec_hdr;
507
41
            to_jump += RecordHeader::SIZE;
508
509
41
            if (rec_hdr.type != RecordType::KEYDATA) {
510
0
                throw std::runtime_error("Unknown record type in internal page");
511
0
            }
512
41
            InternalRecord record(rec_hdr);
513
41
            s >> record;
514
41
            records.emplace_back(record);
515
41
            to_jump += InternalRecord::FIXED_SIZE + rec_hdr.len;
516
517
            // Go back to the indexes
518
41
            s.seek(-to_jump, SEEK_CUR);
519
41
        }
520
14
    }
521
};
522
523
static void SeekToPage(AutoFile& s, uint32_t page_num, uint32_t page_size)
524
358
{
525
358
    int64_t pos = int64_t{page_num} * page_size;
526
358
    s.seek(pos, SEEK_SET);
527
358
}
528
529
void BerkeleyRODatabase::Open()
530
46
{
531
    // Open the file
532
46
    FILE* file = fsbridge::fopen(m_filepath, "rb");
533
46
    AutoFile db_file(file);
534
46
    if (db_file.IsNull()) {
535
0
        throw std::runtime_error("BerkeleyRODatabase: Failed to open database file");
536
0
    }
537
538
46
    uint32_t page_size = 4096; // Default page size
539
540
    // Read the outer metapage
541
    // Expected page number is 0
542
46
    MetaPage outer_meta(0);
543
46
    db_file >> outer_meta;
544
46
    page_size = outer_meta.pagesize;
545
546
    // Verify the size of the file is a multiple of the page size
547
46
    const int64_t size{db_file.size()};
548
549
    // Since BDB stores everything in a page, the file size should be a multiple of the page size;
550
    // However, BDB doesn't actually check that this is the case, and enforcing this check results
551
    // in us rejecting a database that BDB would not, so this check needs to be excluded.
552
    // This is left commented out as a reminder to not accidentally implement this in the future.
553
    // if (size % page_size != 0) {
554
    //     throw std::runtime_error("File size is not a multiple of page size");
555
    // }
556
557
    // Check the last page number
558
46
    uint32_t expected_last_page{uint32_t((size / page_size) - 1)};
559
46
    if (outer_meta.last_page != expected_last_page) {
560
0
        throw std::runtime_error("Last page number could not fit in file");
561
0
    }
562
563
    // Make sure encryption is disabled
564
46
    if (outer_meta.encrypt_algo != 0) {
565
0
        throw std::runtime_error("BDB builtin encryption is not supported");
566
0
    }
567
568
    // Check all Log Sequence Numbers (LSN) point to file 0 and offset 1 which indicates that the LSNs were
569
    // reset and that the log files are not necessary to get all of the data in the database.
570
225
    for (uint32_t i = 0; i < outer_meta.last_page; ++i) {
571
        // The LSN is composed of 2 32-bit ints, the first is a file id, the second an offset
572
        // It will always be the first 8 bytes of a page, so we deserialize it directly for every page
573
179
        uint32_t file;
574
179
        uint32_t offset;
575
179
        SeekToPage(db_file, i, page_size);
576
179
        db_file >> file >> offset;
577
179
        if (outer_meta.other_endian) {
578
0
            file = internal_bswap_32(file);
579
0
            offset = internal_bswap_32(offset);
580
0
        }
581
179
        if (file != 0 || offset != 1) {
582
0
            throw std::runtime_error("LSNs are not reset, this database is not completely flushed. Please reopen then close the database with a version that has BDB support");
583
0
        }
584
179
    }
585
586
    // Read the root page
587
46
    SeekToPage(db_file, outer_meta.root, page_size);
588
46
    PageHeader header(outer_meta.root, outer_meta.other_endian);
589
46
    db_file >> header;
590
46
    if (header.type != PageType::BTREE_LEAF) {
591
0
        throw std::runtime_error("Unexpected outer database root page type");
592
0
    }
593
46
    if (header.entries != 2) {
594
0
        throw std::runtime_error("Unexpected number of entries in outer database root page");
595
0
    }
596
46
    RecordsPage page(header);
597
46
    db_file >> page;
598
599
    // First record should be the string "main"
600
46
    if (!std::holds_alternative<DataRecord>(page.records.at(0)) || std::get<DataRecord>(page.records.at(0)).data != SUBDATABASE_NAME) {
601
0
        throw std::runtime_error("Subdatabase has an unexpected name");
602
0
    }
603
    // Check length of page number for subdatabase location
604
46
    if (!std::holds_alternative<DataRecord>(page.records.at(1)) || std::get<DataRecord>(page.records.at(1)).m_header.len != 4) {
605
0
        throw std::runtime_error("Subdatabase page number has unexpected length");
606
0
    }
607
608
    // Read subdatabase page number
609
    // It is written as a big endian 32 bit number
610
46
    uint32_t main_db_page = ReadBE32(std::get<DataRecord>(page.records.at(1)).data.data());
611
612
    // The main database is in a page that doesn't exist
613
46
    if (main_db_page > outer_meta.last_page) {
614
0
        throw std::runtime_error("Page number is greater than database last page");
615
0
    }
616
617
    // Read the inner metapage
618
46
    SeekToPage(db_file, main_db_page, page_size);
619
46
    MetaPage inner_meta(main_db_page);
620
46
    db_file >> inner_meta;
621
622
46
    if (inner_meta.pagesize != page_size) {
623
0
        throw std::runtime_error("Unexpected page size");
624
0
    }
625
626
46
    if (inner_meta.last_page > outer_meta.last_page) {
627
0
        throw std::runtime_error("Subdatabase last page is greater than database last page");
628
0
    }
629
630
    // Make sure encryption is disabled
631
46
    if (inner_meta.encrypt_algo != 0) {
632
0
        throw std::runtime_error("BDB builtin encryption is not supported");
633
0
    }
634
635
    // Do a DFS through the BTree, starting at root
636
46
    std::vector<uint32_t> pages{inner_meta.root};
637
133
    while (pages.size() > 0) {
638
87
        uint32_t curr_page = pages.back();
639
        // It turns out BDB completely ignores this last_page field and doesn't actually update it to the correct
640
        // last page. While we should be checking this, we can't.
641
        // This is left commented out as a reminder to not accidentally implement this in the future.
642
        // if (curr_page > inner_meta.last_page) {
643
        //     throw std::runtime_error("Page number is greater than subdatabase last page");
644
        // }
645
87
        pages.pop_back();
646
87
        SeekToPage(db_file, curr_page, page_size);
647
87
        PageHeader header(curr_page, inner_meta.other_endian);
648
87
        db_file >> header;
649
87
        switch (header.type) {
650
14
        case PageType::BTREE_INTERNAL: {
651
14
            InternalPage int_page(header);
652
14
            db_file >> int_page;
653
41
            for (const InternalRecord& rec : int_page.records) {
654
41
                if (rec.m_header.deleted) continue;
655
41
                pages.push_back(rec.page_num);
656
41
            }
657
14
            break;
658
0
        }
659
73
        case PageType::BTREE_LEAF: {
660
73
            RecordsPage rec_page(header);
661
73
            db_file >> rec_page;
662
73
            if (rec_page.records.size() % 2 != 0) {
663
                // BDB stores key value pairs in consecutive records, thus an odd number of records is unexpected
664
0
                throw std::runtime_error("Records page has odd number of records");
665
0
            }
666
73
            bool is_key = true;
667
73
            std::vector<std::byte> key;
668
2.51k
            for (const std::variant<DataRecord, OverflowRecord>& rec : rec_page.records) {
669
2.51k
                std::vector<std::byte> data;
670
2.51k
                if (const DataRecord* drec = std::get_if<DataRecord>(&rec)) {
671
2.51k
                    if (drec->m_header.deleted) continue;
672
2.51k
                    data = drec->data;
673
2.51k
                } else if (const OverflowRecord* orec = std::get_if<OverflowRecord>(&rec)) {
674
0
                    if (orec->m_header.deleted) continue;
675
0
                    uint32_t next_page = orec->page_number;
676
0
                    while (next_page != 0) {
677
0
                        SeekToPage(db_file, next_page, page_size);
678
0
                        PageHeader opage_header(next_page, inner_meta.other_endian);
679
0
                        db_file >> opage_header;
680
0
                        if (opage_header.type != PageType::OVERFLOW_DATA) {
681
0
                            throw std::runtime_error("Bad overflow record page type");
682
0
                        }
683
0
                        OverflowPage opage(opage_header);
684
0
                        db_file >> opage;
685
0
                        data.insert(data.end(), opage.data.begin(), opage.data.end());
686
0
                        next_page = opage_header.next_page;
687
0
                    }
688
0
                }
689
690
2.51k
                if (is_key) {
691
1.25k
                    key = data;
692
1.25k
                } else {
693
1.25k
                    m_records.emplace(SerializeData{key.begin(), key.end()}, SerializeData{data.begin(), data.end()});
694
1.25k
                    key.clear();
695
1.25k
                }
696
2.51k
                is_key = !is_key;
697
2.51k
            }
698
73
            break;
699
73
        }
700
73
        default:
701
0
            throw std::runtime_error("Unexpected page type");
702
87
        }
703
87
    }
704
46
}
705
706
std::unique_ptr<DatabaseBatch> BerkeleyRODatabase::MakeBatch()
707
90
{
708
90
    return std::make_unique<BerkeleyROBatch>(*this);
709
90
}
710
711
bool BerkeleyRODatabase::Backup(const std::string& dest) const
712
46
{
713
46
    fs::path src(m_filepath);
714
46
    fs::path dst(fs::PathFromString(dest));
715
716
46
    if (fs::is_directory(dst)) {
717
0
        dst = BDBDataFile(dst);
718
0
    }
719
46
    try {
720
46
        if (fs::exists(dst) && fs::equivalent(src, dst)) {
721
0
            LogWarning("cannot backup to wallet source file %s", fs::PathToString(dst));
722
0
            return false;
723
0
        }
724
725
46
        fs::copy_file(src, dst, fs::copy_options::overwrite_existing);
726
46
        LogInfo("copied %s to %s\n", fs::PathToString(m_filepath), fs::PathToString(dst));
727
46
        return true;
728
46
    } catch (const fs::filesystem_error& e) {
729
0
        LogWarning("error copying %s to %s - %s\n", fs::PathToString(m_filepath), fs::PathToString(dst), e.code().message());
730
0
        return false;
731
0
    }
732
46
}
733
734
bool BerkeleyROBatch::ReadKey(DataStream&& key, DataStream& value)
735
92
{
736
92
    SerializeData key_data{key.begin(), key.end()};
737
92
    const auto it{m_database.m_records.find(key_data)};
738
92
    if (it == m_database.m_records.end()) {
739
0
        return false;
740
0
    }
741
92
    auto val = it->second;
742
92
    value.clear();
743
92
    value.write(std::span(val));
744
92
    return true;
745
92
}
746
747
bool BerkeleyROBatch::HasKey(DataStream&& key)
748
0
{
749
0
    SerializeData key_data{key.begin(), key.end()};
750
0
    return m_database.m_records.contains(key_data);
751
0
}
752
753
BerkeleyROCursor::BerkeleyROCursor(const BerkeleyRODatabase& database, std::span<const std::byte> prefix)
754
917
    : m_database(database)
755
917
{
756
917
    std::tie(m_cursor, m_cursor_end) = m_database.m_records.equal_range(BytePrefix{prefix});
757
917
}
758
759
DatabaseCursor::Status BerkeleyROCursor::Next(DataStream& ssKey, DataStream& ssValue)
760
3.04k
{
761
3.04k
    if (m_cursor == m_cursor_end) {
762
917
        return DatabaseCursor::Status::DONE;
763
917
    }
764
2.13k
    ssKey.write(std::span(m_cursor->first));
765
2.13k
    ssValue.write(std::span(m_cursor->second));
766
2.13k
    m_cursor++;
767
2.13k
    return DatabaseCursor::Status::MORE;
768
3.04k
}
769
770
std::unique_ptr<DatabaseCursor> BerkeleyROBatch::GetNewPrefixCursor(std::span<const std::byte> prefix)
771
874
{
772
874
    return std::make_unique<BerkeleyROCursor>(m_database, prefix);
773
874
}
774
775
std::unique_ptr<BerkeleyRODatabase> MakeBerkeleyRODatabase(const fs::path& path, const DatabaseOptions& options, DatabaseStatus& status, bilingual_str& error)
776
46
{
777
46
    fs::path data_file = BDBDataFile(path);
778
46
    try {
779
46
        std::unique_ptr<BerkeleyRODatabase> db = std::make_unique<BerkeleyRODatabase>(data_file);
780
46
        status = DatabaseStatus::SUCCESS;
781
46
        return db;
782
46
    } catch (const std::runtime_error& e) {
783
0
        error.original = e.what();
784
0
        status = DatabaseStatus::FAILED_LOAD;
785
0
        return nullptr;
786
0
    }
787
46
}
788
} // namespace wallet