blockfilterindex.cpp raw
1 // Copyright (c) 2018-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 <index/blockfilterindex.h>
6
7 #include <blockfilter.h>
8 #include <chain.h>
9 #include <common/args.h>
10 #include <dbwrapper.h>
11 #include <flatfile.h>
12 #include <hash.h>
13 #include <index/base.h>
14 #include <index/db_key.h>
15 #include <interfaces/chain.h>
16 #include <interfaces/types.h>
17 #include <serialize.h>
18 #include <streams.h>
19 #include <sync.h>
20 #include <uint256.h>
21 #include <util/check.h>
22 #include <util/fs.h>
23 #include <util/hasher.h>
24 #include <util/log.h>
25 #include <util/syserror.h>
26
27 #include <cerrno>
28 #include <exception>
29 #include <map>
30 #include <optional>
31 #include <stdexcept>
32 #include <string>
33 #include <tuple>
34 #include <utility>
35 #include <vector>
36
37 /* The index database stores three items for each block: the disk location of the encoded filter,
38 * its dSHA256 hash, and the header. Those belonging to blocks on the active chain are indexed by
39 * height, and those belonging to blocks that have been reorganized out of the active chain are
40 * indexed by block hash. This ensures that filter data for any block that becomes part of the
41 * active chain can always be retrieved, alleviating timing concerns.
42 *
43 * The filters themselves are stored in flat files and referenced by the LevelDB entries. This
44 * minimizes the amount of data written to LevelDB and keeps the database values constant size. The
45 * disk location of the next block filter to be written (represented as a FlatFilePos) is stored
46 * under the DB_FILTER_POS key.
47 *
48 * The logic for keys is shared with other indexes, see index/db_key.h.
49 */
50 constexpr uint8_t DB_FILTER_POS{'P'};
51
52 constexpr unsigned int MAX_FLTR_FILE_SIZE{16_MiB};
53 /** The pre-allocation chunk size for fltr?????.dat files */
54 constexpr unsigned int FLTR_FILE_CHUNK_SIZE{1_MiB};
55 /** Maximum size of the cfheaders cache
56 * We have a limit to prevent a bug in filling this cache
57 * potentially turning into an OOM. At 2000 entries, this cache
58 * is big enough for a 2,000,000 length block chain, which
59 * we should be enough until ~2047. */
60 constexpr size_t CF_HEADERS_CACHE_MAX_SZ{2000};
61
62 namespace {
63
64 std::string BlockFilterThreadName(BlockFilterType filter_type)
65 {
66 switch (filter_type) {
67 case BlockFilterType::BASIC: return "blkfltbscidx";
68 case BlockFilterType::INVALID: return "";
69 } // no default case, so the compiler can warn about missing cases
70 assert(false);
71 }
72
73 struct DBVal {
74 uint256 hash;
75 uint256 header;
76 FlatFilePos pos;
77
78 SERIALIZE_METHODS(DBVal, obj) { READWRITE(obj.hash, obj.header, obj.pos); }
79 };
80
81 }; // namespace
82
83 static std::map<BlockFilterType, BlockFilterIndex> g_filter_indexes;
84
85 BlockFilterIndex::BlockFilterIndex(std::unique_ptr<interfaces::Chain> chain, BlockFilterType filter_type,
86 size_t n_cache_size, bool f_memory, bool f_wipe)
87 : BaseIndex(std::move(chain), BlockFilterTypeName(filter_type) + " block filter index", BlockFilterThreadName(filter_type))
88 , m_filter_type(filter_type)
89 {
90 const std::string& filter_name = BlockFilterTypeName(filter_type);
91 if (filter_name.empty()) throw std::invalid_argument("unknown filter_type");
92
93 fs::path path = gArgs.GetDataDirNet() / "indexes" / "blockfilter" / fs::u8path(filter_name);
94 fs::create_directories(path);
95
96 m_db = std::make_unique<BaseIndex::DB>(path / "db", n_cache_size, f_memory, f_wipe);
97 m_filter_fileseq = std::make_unique<FlatFileSeq>(std::move(path), "fltr", FLTR_FILE_CHUNK_SIZE);
98 }
99
100 interfaces::Chain::NotifyOptions BlockFilterIndex::CustomOptions()
101 {
102 interfaces::Chain::NotifyOptions options;
103 options.connect_undo_data = true;
104 return options;
105 }
106
107 bool BlockFilterIndex::CustomInit(const std::optional<interfaces::BlockRef>& block)
108 {
109 if (!m_db->Read(DB_FILTER_POS, m_next_filter_pos)) {
110 // Check that the cause of the read failure is that the key does not exist. Any other errors
111 // indicate database corruption or a disk failure, and starting the index would cause
112 // further corruption.
113 if (m_db->Exists(DB_FILTER_POS)) {
114 LogError("Cannot read current %s state; index may be corrupted",
115 GetName());
116 return false;
117 }
118
119 // If the DB_FILTER_POS is not set, then initialize to the first location.
120 m_next_filter_pos.nFile = 0;
121 m_next_filter_pos.nPos = 0;
122 }
123
124 if (block) {
125 auto op_last_header = ReadFilterHeader(block->height, block->hash);
126 if (!op_last_header) {
127 LogError("Cannot read last block filter header; index may be corrupted");
128 return false;
129 }
130 m_last_header = *op_last_header;
131 }
132
133 return true;
134 }
135
136 bool BlockFilterIndex::CustomCommit(CDBBatch& batch)
137 {
138 const FlatFilePos& pos = m_next_filter_pos;
139
140 // Flush current filter file to disk.
141 AutoFile file{m_filter_fileseq->Open(pos)};
142 if (file.IsNull()) {
143 LogError("Failed to open filter file %d", pos.nFile);
144 return false;
145 }
146 if (!file.Commit()) {
147 LogError("Failed to commit filter file %d", pos.nFile);
148 (void)file.fclose();
149 return false;
150 }
151 if (file.fclose() != 0) {
152 LogError("Failed to close filter file %d after commit: %s", pos.nFile, SysErrorString(errno));
153 return false;
154 }
155
156 batch.Write(DB_FILTER_POS, pos);
157 return true;
158 }
159
160 bool BlockFilterIndex::ReadFilterFromDisk(const FlatFilePos& pos, const uint256& hash, BlockFilter& filter) const
161 {
162 AutoFile filein{m_filter_fileseq->Open(pos, true)};
163 if (filein.IsNull()) {
164 return false;
165 }
166
167 // Check that the hash of the encoded_filter matches the one stored in the db.
168 uint256 block_hash;
169 std::vector<uint8_t> encoded_filter;
170 try {
171 filein >> block_hash >> encoded_filter;
172 if (Hash(encoded_filter) != hash) {
173 LogError("Checksum mismatch in filter decode.");
174 return false;
175 }
176 filter = BlockFilter(GetFilterType(), block_hash, std::move(encoded_filter), /*skip_decode_check=*/true);
177 }
178 catch (const std::exception& e) {
179 LogError("Failed to deserialize block filter from disk: %s", e.what());
180 return false;
181 }
182
183 return true;
184 }
185
186 size_t BlockFilterIndex::WriteFilterToDisk(FlatFilePos& pos, const BlockFilter& filter)
187 {
188 assert(filter.GetFilterType() == GetFilterType());
189
190 uint64_t data_size{
191 GetSerializeSize(filter.GetBlockHash()) +
192 GetSerializeSize(filter.GetEncodedFilter())};
193
194 // If writing the filter would overflow the file, flush and move to the next one.
195 if (pos.nPos + data_size > MAX_FLTR_FILE_SIZE) {
196 AutoFile last_file{m_filter_fileseq->Open(pos)};
197 if (last_file.IsNull()) {
198 LogError("Failed to open filter file %d", pos.nFile);
199 return 0;
200 }
201 if (!last_file.Truncate(pos.nPos)) {
202 LogError("Failed to truncate filter file %d", pos.nFile);
203 return 0;
204 }
205 if (!last_file.Commit()) {
206 LogError("Failed to commit filter file %d", pos.nFile);
207 (void)last_file.fclose();
208 return 0;
209 }
210 if (last_file.fclose() != 0) {
211 LogError("Failed to close filter file %d after commit: %s", pos.nFile, SysErrorString(errno));
212 return 0;
213 }
214
215 pos.nFile++;
216 pos.nPos = 0;
217 }
218
219 // Pre-allocate sufficient space for filter data.
220 bool out_of_space;
221 m_filter_fileseq->Allocate(pos, data_size, out_of_space);
222 if (out_of_space) {
223 LogError("out of disk space");
224 return 0;
225 }
226
227 AutoFile fileout{m_filter_fileseq->Open(pos)};
228 if (fileout.IsNull()) {
229 LogError("Failed to open filter file %d", pos.nFile);
230 return 0;
231 }
232
233 fileout << filter.GetBlockHash() << filter.GetEncodedFilter();
234
235 if (fileout.fclose() != 0) {
236 LogError("Failed to close filter file %d: %s", pos.nFile, SysErrorString(errno));
237 return 0;
238 }
239
240 return data_size;
241 }
242
243 std::optional<uint256> BlockFilterIndex::ReadFilterHeader(int height, const uint256& expected_block_hash)
244 {
245 std::pair<uint256, DBVal> read_out;
246 if (!m_db->Read(index_util::DBHeightKey(height), read_out)) {
247 return std::nullopt;
248 }
249
250 if (read_out.first != expected_block_hash) {
251 LogError("previous block header belongs to unexpected block %s; expected %s",
252 read_out.first.ToString(), expected_block_hash.ToString());
253 return std::nullopt;
254 }
255
256 return read_out.second.header;
257 }
258
259 bool BlockFilterIndex::CustomAppend(const interfaces::BlockInfo& block)
260 {
261 BlockFilter filter(m_filter_type, *Assert(block.data), *Assert(block.undo_data));
262 const uint256& header = filter.ComputeHeader(m_last_header);
263 bool res = Write(filter, block.height, header);
264 if (res) m_last_header = header; // update last header
265 return res;
266 }
267
268 bool BlockFilterIndex::Write(const BlockFilter& filter, uint32_t block_height, const uint256& filter_header)
269 {
270 size_t bytes_written = WriteFilterToDisk(m_next_filter_pos, filter);
271 if (bytes_written == 0) return false;
272
273 std::pair<uint256, DBVal> value;
274 value.first = filter.GetBlockHash();
275 value.second.hash = filter.GetHash();
276 value.second.header = filter_header;
277 value.second.pos = m_next_filter_pos;
278
279 m_db->Write(index_util::DBHeightKey(block_height), value);
280
281 m_next_filter_pos.nPos += bytes_written;
282 return true;
283 }
284
285 bool BlockFilterIndex::CustomRemove(const interfaces::BlockInfo& block)
286 {
287 CDBBatch batch(*m_db);
288 std::unique_ptr<CDBIterator> db_it(m_db->NewIterator());
289
290 // During a reorg, we need to copy block filter that is getting disconnected from the
291 // height index to the hash index so we can still find it when the height index entry
292 // is overwritten.
293 if (!index_util::CopyHeightIndexToHashIndex<DBVal>(*db_it, batch, m_name, block.height)) {
294 return false;
295 }
296
297 // The latest filter position gets written in Commit by the call to the BaseIndex::Rewind.
298 // But since this creates new references to the filter, the position should get updated here
299 // atomically as well in case Commit fails.
300 batch.Write(DB_FILTER_POS, m_next_filter_pos);
301 m_db->WriteBatch(batch);
302
303 // Update cached header to the previous block hash
304 m_last_header = *Assert(ReadFilterHeader(block.height - 1, *Assert(block.prev_hash)));
305 return true;
306 }
307
308 static bool LookupRange(CDBWrapper& db, const std::string& index_name, int start_height,
309 const CBlockIndex* stop_index, std::vector<DBVal>& results)
310 {
311 if (start_height < 0) {
312 LogError("start height (%d) is negative", start_height);
313 return false;
314 }
315 if (start_height > stop_index->nHeight) {
316 LogError("start height (%d) is greater than stop height (%d)",
317 start_height, stop_index->nHeight);
318 return false;
319 }
320
321 size_t results_size = static_cast<size_t>(stop_index->nHeight - start_height + 1);
322 std::vector<std::pair<uint256, DBVal>> values(results_size);
323
324 index_util::DBHeightKey key(start_height);
325 std::unique_ptr<CDBIterator> db_it(db.NewIterator());
326 db_it->Seek(index_util::DBHeightKey(start_height));
327 for (int height = start_height; height <= stop_index->nHeight; ++height) {
328 if (!db_it->Valid() || !db_it->GetKey(key) || key.height != height) {
329 return false;
330 }
331
332 size_t i = static_cast<size_t>(height - start_height);
333 if (!db_it->GetValue(values[i])) {
334 LogError("unable to read value in %s at key (%c, %d)",
335 index_name, index_util::DB_BLOCK_HEIGHT, height);
336 return false;
337 }
338
339 db_it->Next();
340 }
341
342 results.resize(results_size);
343
344 // Iterate backwards through block indexes collecting results in order to access the block hash
345 // of each entry in case we need to look it up in the hash index.
346 for (const CBlockIndex* block_index = stop_index;
347 block_index && block_index->nHeight >= start_height;
348 block_index = block_index->pprev) {
349 uint256 block_hash = block_index->GetBlockHash();
350
351 size_t i = static_cast<size_t>(block_index->nHeight - start_height);
352 if (block_hash == values[i].first) {
353 results[i] = std::move(values[i].second);
354 continue;
355 }
356
357 if (!db.Read(index_util::DBHashKey(block_hash), results[i])) {
358 LogError("unable to read value in %s at key (%c, %s)",
359 index_name, index_util::DB_BLOCK_HASH, block_hash.ToString());
360 return false;
361 }
362 }
363
364 return true;
365 }
366
367 bool BlockFilterIndex::LookupFilter(const CBlockIndex* block_index, BlockFilter& filter_out) const
368 {
369 DBVal entry;
370 if (!index_util::LookUpOne(*m_db, {block_index->GetBlockHash(), block_index->nHeight}, entry)) {
371 return false;
372 }
373
374 return ReadFilterFromDisk(entry.pos, entry.hash, filter_out);
375 }
376
377 bool BlockFilterIndex::LookupFilterHeader(const CBlockIndex* block_index, uint256& header_out)
378 {
379 LOCK(m_cs_headers_cache);
380
381 bool is_checkpoint{block_index->nHeight % CFCHECKPT_INTERVAL == 0};
382
383 if (is_checkpoint) {
384 // Try to find the block in the headers cache if this is a checkpoint height.
385 auto header = m_headers_cache.find(block_index->GetBlockHash());
386 if (header != m_headers_cache.end()) {
387 header_out = header->second;
388 return true;
389 }
390 }
391
392 DBVal entry;
393 if (!index_util::LookUpOne(*m_db, {block_index->GetBlockHash(), block_index->nHeight}, entry)) {
394 return false;
395 }
396
397 if (is_checkpoint &&
398 m_headers_cache.size() < CF_HEADERS_CACHE_MAX_SZ) {
399 // Add to the headers cache if this is a checkpoint height.
400 m_headers_cache.emplace(block_index->GetBlockHash(), entry.header);
401 }
402
403 header_out = entry.header;
404 return true;
405 }
406
407 bool BlockFilterIndex::LookupFilterRange(int start_height, const CBlockIndex* stop_index,
408 std::vector<BlockFilter>& filters_out) const
409 {
410 std::vector<DBVal> entries;
411 if (!LookupRange(*m_db, m_name, start_height, stop_index, entries)) {
412 return false;
413 }
414
415 filters_out.resize(entries.size());
416 auto filter_pos_it = filters_out.begin();
417 for (const auto& entry : entries) {
418 if (!ReadFilterFromDisk(entry.pos, entry.hash, *filter_pos_it)) {
419 return false;
420 }
421 ++filter_pos_it;
422 }
423
424 return true;
425 }
426
427 bool BlockFilterIndex::LookupFilterHashRange(int start_height, const CBlockIndex* stop_index,
428 std::vector<uint256>& hashes_out) const
429
430 {
431 std::vector<DBVal> entries;
432 if (!LookupRange(*m_db, m_name, start_height, stop_index, entries)) {
433 return false;
434 }
435
436 hashes_out.clear();
437 hashes_out.reserve(entries.size());
438 for (const auto& entry : entries) {
439 hashes_out.push_back(entry.hash);
440 }
441 return true;
442 }
443
444 BlockFilterIndex* GetBlockFilterIndex(BlockFilterType filter_type)
445 {
446 auto it = g_filter_indexes.find(filter_type);
447 return it != g_filter_indexes.end() ? &it->second : nullptr;
448 }
449
450 void ForEachBlockFilterIndex(std::function<void (BlockFilterIndex&)> fn)
451 {
452 for (auto& entry : g_filter_indexes) fn(entry.second);
453 }
454
455 bool InitBlockFilterIndex(std::function<std::unique_ptr<interfaces::Chain>()> make_chain, BlockFilterType filter_type,
456 size_t n_cache_size, bool f_memory, bool f_wipe)
457 {
458 auto result = g_filter_indexes.emplace(std::piecewise_construct,
459 std::forward_as_tuple(filter_type),
460 std::forward_as_tuple(make_chain(), filter_type,
461 n_cache_size, f_memory, f_wipe));
462 return result.second;
463 }
464
465 bool DestroyBlockFilterIndex(BlockFilterType filter_type)
466 {
467 return g_filter_indexes.erase(filter_type);
468 }
469
470 void DestroyAllBlockFilterIndexes()
471 {
472 g_filter_indexes.clear();
473 }
474