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 <streams.h>
8#include <util/log.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
19namespace wallet {
20// Magic bytes in both endianness's
21constexpr uint32_t BTREE_MAGIC = 0x00053162;    // If the file endianness matches our system, we see this magic
22constexpr uint32_t BTREE_MAGIC_OE = 0x62310500; // If the file endianness is the other one, we will see this magic
23
24// Subdatabase name
25static const std::vector<std::byte> SUBDATABASE_NAME = {std::byte{'m'}, std::byte{'a'}, std::byte{'i'}, std::byte{'n'}};
26
27enum 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
49enum 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
56enum 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 */
73class MetaPage
74{
75public:
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    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    {
113        s >> lsn_file;
114        s >> lsn_offset;
115        s >> page_num;
116        s >> magic;
117        s >> version;
118        s >> pagesize;
119        s >> encrypt_algo;
120
121        other_endian = magic == BTREE_MAGIC_OE;
122
123        uint8_t uint8_type;
124        s >> uint8_type;
125        type = static_cast<PageType>(uint8_type);
126
127        s >> metaflags;
128        s >> unused1;
129        s >> free_list;
130        s >> last_page;
131        s >> partitions;
132        s >> key_count;
133        s >> record_count;
134
135        uint32_t uint32_flags;
136        s >> uint32_flags;
137        if (other_endian) {
138            uint32_flags = internal_bswap_32(uint32_flags);
139        }
140        flags = static_cast<BTreeFlags>(uint32_flags);
141
142        s >> uid;
143        s >> unused2;
144        s >> minkey;
145        s >> re_len;
146        s >> re_pad;
147        s >> root;
148        s >> unused3;
149        s >> crypto_magic;
150        s >> trash;
151        s >> iv;
152        s >> chksum;
153
154        if (other_endian) {
155            lsn_file = internal_bswap_32(lsn_file);
156            lsn_offset = internal_bswap_32(lsn_offset);
157            page_num = internal_bswap_32(page_num);
158            magic = internal_bswap_32(magic);
159            version = internal_bswap_32(version);
160            pagesize = internal_bswap_32(pagesize);
161            free_list = internal_bswap_32(free_list);
162            last_page = internal_bswap_32(last_page);
163            partitions = internal_bswap_32(partitions);
164            key_count = internal_bswap_32(key_count);
165            record_count = internal_bswap_32(record_count);
166            unused2 = internal_bswap_32(unused2);
167            minkey = internal_bswap_32(minkey);
168            re_len = internal_bswap_32(re_len);
169            re_pad = internal_bswap_32(re_pad);
170            root = internal_bswap_32(root);
171            crypto_magic = internal_bswap_32(crypto_magic);
172        }
173
174        // Page number must match
175        if (page_num != expected_page_num) {
176            throw std::runtime_error("Meta page number mismatch");
177        }
178
179        // Check magic
180        if (magic != BTREE_MAGIC) {
181            throw std::runtime_error("Not a BDB file");
182        }
183
184        // Only version 9 is supported
185        if (version != 9) {
186            throw std::runtime_error("Unsupported BDB data file version number");
187        }
188
189        // Page size must be 512 <= pagesize <= 64k, and be a power of 2
190        if (pagesize < 512 || pagesize > 65536 || (pagesize & (pagesize - 1)) != 0) {
191            throw std::runtime_error("Bad page size");
192        }
193
194        // Page type must be the btree type
195        if (type != PageType::BTREE_META) {
196            throw std::runtime_error("Unexpected page type, should be 9 (BTree Metadata)");
197        }
198
199        // Only supported meta-flag is subdatabase
200        if (flags != BTreeFlags::SUBDB) {
201            throw std::runtime_error("Unexpected database flags, should only be 0x20 (subdatabases)");
202        }
203    }
204};
205
206/** General class for records in a BDB BTree database. Contains common fields. */
207class RecordHeader
208{
209public:
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    RecordHeader(bool other_endian) : other_endian(other_endian) {}
219    RecordHeader() = delete;
220
221    template <typename Stream>
222    void Unserialize(Stream& s)
223    {
224        s >> len;
225
226        uint8_t uint8_type;
227        s >> uint8_type;
228        type = static_cast<RecordType>(uint8_type & ~static_cast<uint8_t>(RecordType::DELETE_FLAG));
229        deleted = uint8_type & static_cast<uint8_t>(RecordType::DELETE_FLAG);
230
231        if (other_endian) {
232            len = internal_bswap_16(len);
233        }
234    }
235};
236
237/** Class for data in the record directly */
238class DataRecord
239{
240public:
241    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    {