ceph/src/rocksdb/table/block_based/block_based_filter_block.h

   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
  45   virtual bool IsBlockBased() override { return true; }
  46   virtual void StartBlock(uint64_t block_offset) override;
  47   virtual void Add(const Slice& key) override;
  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, const ReadOptions& ro,
  89       FilePrefetchBuffer* prefetch_buffer, bool use_cache, bool prefetch,
  90       bool pin, BlockCacheLookupContext* lookup_context);
  91
  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