bdb.py raw
1 #!/usr/bin/env python3
2 # Copyright (c) 2020-2021 The Limenka 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 Utilities for working directly with the wallet's BDB database file
7
8 This is specific to the configuration of BDB used in this project:
9 - Outer database contains single subdatabase named 'main'
10 - btree
11 - btree internal, leaf and overflow pages
12
13 Each key-value pair is two entries in a btree leaf, which optionally refers to overflow pages
14 if the data doesn't fit into a single page. The first entry is the key, the one that follows
15 is the value. And so on. Note that the entry data is itself not in the correct order. Instead
16 entry offsets are stored in the correct order and those offsets are needed to then retrieve
17 the data itself. Note that this implementation currently only supports reading databases that
18 are in the same endianness as the host.
19
20 Page format can be found in BDB source code dbinc/db_page.h
21
22 `db_dump -da wallet.dat` is useful to see the data in a wallet.dat BDB file
23 """
24
25 import struct
26
27 # Important constants
28 PAGE_HEADER_SIZE = 26
29 OUTER_META_PAGE = 0
30
31 # Page type values
32 BTREE_INTERNAL = 3
33 BTREE_LEAF = 5
34 OVERFLOW_DATA = 7
35 BTREE_META = 9
36
37 # Record type values
38 RECORD_KEYDATA = 1
39 RECORD_OVERFLOW_DATA = 3
40
41 # Some magic numbers for sanity checking
42 BTREE_MAGIC = 0x053162
43 DB_VERSION = 9
44 SUBDATABASE_NAME = b'main'
45
46 # Deserializes an internal, leaf or overflow page into a dict.
47 # In addition to the common page header fields, the result contains an 'entries'
48 # array of dicts with the following fields, depending on the page type:
49 # internal page [BTREE_INTERNAL]:
50 # - 'page_num': referenced page number (used to find further pages to process)
51 # leaf page [BTREE_LEAF]:
52 # - 'record_type': record type, must be RECORD_KEYDATA or RECORD_OVERFLOW_DATA
53 # - 'data': binary data (key or value payload), if record type is RECORD_KEYDATA
54 # - 'page_num': referenced overflow page number, if record type is RECORD_OVERFLOW_DATA
55 # overflow page [OVERFLOW_DATA]:
56 # - 'data': binary data (part of key or value payload)
57 def dump_page(data):
58 page_info = {}
59 page_header = data[0:26]
60 _, pgno, prev_pgno, next_pgno, entries, hf_offset, level, pg_type = struct.unpack('QIIIHHBB', page_header)
61 page_info['pgno'] = pgno
62 page_info['prev_pgno'] = prev_pgno
63 page_info['next_pgno'] = next_pgno
64 page_info['hf_offset'] = hf_offset
65 page_info['level'] = level
66 page_info['pg_type'] = pg_type
67 page_info['entry_offsets'] = struct.unpack('{}H'.format(entries), data[26:26 + entries * 2])
68 page_info['entries'] = []
69
70 assert pg_type in (BTREE_INTERNAL, BTREE_LEAF, OVERFLOW_DATA)
71
72 if pg_type == OVERFLOW_DATA:
73 assert entries == 1
74 page_info['entries'].append({'data': data[26:26 + hf_offset]})
75 return page_info
76
77 for i in range(0, entries):
78 entry = {}
79 offset = page_info['entry_offsets'][i]
80 record_header = data[offset:offset + 3]
81 offset += 3
82 e_len, record_type = struct.unpack('HB', record_header)
83
84 if pg_type == BTREE_INTERNAL:
85 assert record_type == RECORD_KEYDATA
86 internal_record_data = data[offset:offset + 9]
87 _, page_num, _ = struct.unpack('=BII', internal_record_data)
88 entry['page_num'] = page_num
89 elif pg_type == BTREE_LEAF:
90 assert record_type in (RECORD_KEYDATA, RECORD_OVERFLOW_DATA)
91 entry['record_type'] = record_type
92 if record_type == RECORD_KEYDATA:
93 entry['data'] = data[offset:offset + e_len]
94 elif record_type == RECORD_OVERFLOW_DATA:
95 overflow_record_data = data[offset:offset + 9]
96 _, page_num, _ = struct.unpack('=BII', overflow_record_data)
97 entry['page_num'] = page_num
98
99 page_info['entries'].append(entry)
100
101 return page_info
102
103 # Deserializes a btree metadata page into a dict.
104 # Does a simple sanity check on the magic value, type, and version
105 def dump_meta_page(page):
106 # metadata page
107 # general metadata
108 metadata = {}
109 meta_page = page[0:72]
110 _, pgno, magic, version, pagesize, encrypt_alg, pg_type, metaflags, _, free, last_pgno, nparts, key_count, record_count, flags, uid = struct.unpack('QIIIIBBBBIIIIII20s', meta_page)
111 metadata['pgno'] = pgno
112 metadata['magic'] = magic
113 metadata['version'] = version
114 metadata['pagesize'] = pagesize
115 metadata['encrypt_alg'] = encrypt_alg
116 metadata['pg_type'] = pg_type
117 metadata['metaflags'] = metaflags
118 metadata['free'] = free
119 metadata['last_pgno'] = last_pgno
120 metadata['nparts'] = nparts
121 metadata['key_count'] = key_count
122 metadata['record_count'] = record_count
123 metadata['flags'] = flags
124 metadata['uid'] = uid.hex().encode()
125
126 assert magic == BTREE_MAGIC, 'bdb magic does not match bdb btree magic'
127 assert pg_type == BTREE_META, 'Metadata page is not a btree metadata page'
128 assert version == DB_VERSION, 'Database too new'
129
130 # btree metadata
131 btree_meta_page = page[72:512]
132 _, minkey, re_len, re_pad, root, _, crypto_magic, _, iv, chksum = struct.unpack('IIIII368sI12s16s20s', btree_meta_page)
133 metadata['minkey'] = minkey
134 metadata['re_len'] = re_len
135 metadata['re_pad'] = re_pad
136 metadata['root'] = root
137 metadata['crypto_magic'] = crypto_magic
138 metadata['iv'] = iv.hex().encode()
139 metadata['chksum'] = chksum.hex().encode()
140
141 return metadata
142
143 # Given the dict from dump_leaf_page, get the key-value pairs and put them into a dict
144 def extract_kv_pairs(page_data, pages):
145 out = {}
146 last_key = None
147 for i, entry in enumerate(page_data['entries']):
148 data = b''
149 if entry['record_type'] == RECORD_KEYDATA:
150 data = entry['data']
151 elif entry['record_type'] == RECORD_OVERFLOW_DATA:
152 next_page = entry['page_num']
153 while next_page != 0:
154 opage = pages[next_page]
155 opage_info = dump_page(opage)
156 data += opage_info['entries'][0]['data']
157 next_page = opage_info['next_pgno']
158
159 # By virtue of these all being pairs, even number entries are keys, and odd are values
160 if i % 2 == 0:
161 out[entry['data']] = b''
162 last_key = data
163 else:
164 out[last_key] = data
165 return out
166
167 # Extract the key-value pairs of the BDB file given in filename
168 def dump_bdb_kv(filename):
169 # Read in the BDB file and start deserializing it
170 pages = []
171 with open(filename, 'rb') as f:
172 # Determine pagesize first
173 data = f.read(PAGE_HEADER_SIZE)
174 pagesize = struct.unpack('I', data[20:24])[0]
175 assert pagesize in (512, 1024, 2048, 4096, 8192, 16384, 32768, 65536)
176
177 # Read rest of first page
178 data += f.read(pagesize - PAGE_HEADER_SIZE)
179 assert len(data) == pagesize
180
181 # Read all remaining pages
182 while len(data) > 0:
183 pages.append(data)
184 data = f.read(pagesize)
185
186 # Sanity check the meta pages, read root page
187 outer_meta_info = dump_meta_page(pages[OUTER_META_PAGE])
188 root_page_info = dump_page(pages[outer_meta_info['root']])
189 assert root_page_info['pg_type'] == BTREE_LEAF
190 assert len(root_page_info['entries']) == 2
191 assert root_page_info['entries'][0]['data'] == SUBDATABASE_NAME
192 assert len(root_page_info['entries'][1]['data']) == 4
193 inner_meta_page = int.from_bytes(root_page_info['entries'][1]['data'], 'big')
194 inner_meta_info = dump_meta_page(pages[inner_meta_page])
195
196 # Fetch the kv pairs from the pages
197 kv = {}
198 pages_to_process = [inner_meta_info['root']]
199 while len(pages_to_process) > 0:
200 curr_page_no = pages_to_process.pop()
201 assert curr_page_no <= outer_meta_info['last_pgno']
202 info = dump_page(pages[curr_page_no])
203 assert info['pg_type'] in (BTREE_INTERNAL, BTREE_LEAF)
204 if info['pg_type'] == BTREE_INTERNAL:
205 for entry in info['entries']:
206 pages_to_process.append(entry['page_num'])
207 elif info['pg_type'] == BTREE_LEAF:
208 info_kv = extract_kv_pairs(info, pages)
209 kv = {**kv, **info_kv}
210 return kv
211