1 // Copyright (c) 2011-present, Facebook, Inc. All rights reserved. 2 // This source code is licensed under both the GPLv2 (found in the 3 // COPYING file in the root directory) and Apache 2.0 License 4 // (found in the LICENSE.Apache file in the root directory). 5 // 6 // Copyright (c) 2012 The LevelDB Authors. All rights reserved. 7 // Use of this source code is governed by a BSD-style license that can be 8 // found in the LICENSE file. See the AUTHORS file for names of contributors. 9 // 10 // A filter block is stored near the end of a Table file. It contains 11 // filters (e.g., bloom filters) for all data blocks in the table combined 12 // into a single filter block. 13 14 #pragma once 15 16 #include <stddef.h> 17 #include <stdint.h> 18 #include <memory> 19 #include <string> 20 #include <vector> 21 22 #include "rocksdb/options.h" 23 #include "rocksdb/slice.h" 24 #include "rocksdb/slice_transform.h" 25 #include "table/block_based/filter_block_reader_common.h" 26 #include "table/format.h" 27 #include "util/hash.h" 28 29 namespace ROCKSDB_NAMESPACE { 30 31 // A BlockBasedFilterBlockBuilder is used to construct all of the filters for a 32 // particular Table. It generates a single string which is stored as 33 // a special block in the Table. 34 // 35 // The sequence of calls to BlockBasedFilterBlockBuilder must match the regexp: 36 // (StartBlock Add*)* Finish 37 class BlockBasedFilterBlockBuilder : public FilterBlockBuilder { 38 public: 39 BlockBasedFilterBlockBuilder(const SliceTransform* prefix_extractor, 40 const BlockBasedTableOptions& table_opt); 41 // No copying allowed 42 BlockBasedFilterBlockBuilder(const BlockBasedFilterBlockBuilder&) = delete; 43 void operator=(const BlockBasedFilterBlockBuilder&) = delete; 44 IsBlockBased()45 virtual bool IsBlockBased() override { return true; } 46 virtual void StartBlock(uint64_t block_offset) override; 47 virtual void Add(const Slice& key) override; NumAdded()48 virtual size_t NumAdded() const override { return num_added_; } 49 virtual Slice Finish(const BlockHandle& tmp, Status* status) override; 50 using FilterBlockBuilder::Finish; 51 52 private: 53 void AddKey(const Slice& key); 54 void AddPrefix(const Slice& key); 55 void GenerateFilter(); 56 57 // important: all of these might point to invalid addresses 58 // at the time of destruction of this filter block. destructor 59 // should NOT dereference them. 60 const FilterPolicy* policy_; 61 const SliceTransform* prefix_extractor_; 62 bool whole_key_filtering_; 63 64 size_t prev_prefix_start_; // the position of the last appended prefix 65 // to "entries_". 66 size_t prev_prefix_size_; // the length of the last appended prefix to 67 // "entries_". 68 std::string entries_; // Flattened entry contents 69 std::vector<size_t> start_; // Starting index in entries_ of each entry 70 std::string result_; // Filter data computed so far 71 std::vector<Slice> tmp_entries_; // policy_->CreateFilter() argument 72 std::vector<uint32_t> filter_offsets_; 73 size_t num_added_; // Number of keys added 74 }; 75 76 // A FilterBlockReader is used to parse filter from SST table. 77 // KeyMayMatch and PrefixMayMatch would trigger filter checking 78 class BlockBasedFilterBlockReader 79 : public FilterBlockReaderCommon<BlockContents> { 80 public: 81 BlockBasedFilterBlockReader(const BlockBasedTable* t, 82 CachableEntry<BlockContents>&& filter_block); 83 // No copying allowed 84 BlockBasedFilterBlockReader(const BlockBasedFilterBlockReader&) = delete; 85 void operator=(const BlockBasedFilterBlockReader&) = delete; 86 87 static std::unique_ptr<FilterBlockReader> Create( 88 const BlockBasedTable* table, FilePrefetchBuffer* prefetch_buffer, 89 bool use_cache, bool prefetch, bool pin, 90 BlockCacheLookupContext* lookup_context); 91 IsBlockBased()92 bool IsBlockBased() override { return true; } 93 94 bool KeyMayMatch(const Slice& key, const SliceTransform* prefix_extractor, 95 uint64_t block_offset, const bool no_io, 96 const Slice* const const_ikey_ptr, GetContext* get_context, 97 BlockCacheLookupContext* lookup_context) override; 98 bool PrefixMayMatch(const Slice& prefix, 99 const SliceTransform* prefix_extractor, 100 uint64_t block_offset, const bool no_io, 101 const Slice* const const_ikey_ptr, 102 GetContext* get_context, 103 BlockCacheLookupContext* lookup_context) override; 104 size_t ApproximateMemoryUsage() const override; 105 106 // convert this object to a human readable form 107 std::string ToString() const override; 108 109 private: 110 static bool ParseFieldsFromBlock(const BlockContents& contents, 111 const char** data, const char** offset, 112 size_t* num, size_t* base_lg); 113 114 bool MayMatch(const Slice& entry, uint64_t block_offset, bool no_io, 115 GetContext* get_context, 116 BlockCacheLookupContext* lookup_context) const; 117 }; 118 119 } // namespace ROCKSDB_NAMESPACE 120