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 #pragma once
6
7 #include <string>
8 #include <vector>
9
10 #include "rocksdb/slice.h"
11
12 #include "port/port.h"
13 #include "util/bloom_impl.h"
14 #include "util/hash.h"
15
16 #include "third-party/folly/folly/ConstexprMath.h"
17
18 #include <memory>
19
20 namespace ROCKSDB_NAMESPACE {
21 class Slice;
pin() -> Guard22 class Allocator;
23 class Logger;
24
25 // A legacy Bloom filter implementation used by Plain Table db format, for
26 // schema backward compatibility. Not for use in new filter applications.
27 class PlainTableBloomV1 {
is_pinned() -> bool28 public:
29 // allocator: pass allocator to bloom filter, hence trace the usage of memory
30 // total_bits: fixed total bits for the bloom
31 // num_probes: number of hash probes for a single key
32 // locality: If positive, optimize for cache line locality, 0 otherwise.
33 // hash_func: customized hash function
34 // huge_page_tlb_size: if >0, try to allocate bloom bytes from huge page TLB
35 // within this page size. Need to reserve huge pages for
36 // it to be allocated, like:
37 // sysctl -w vm.nr_hugepages=20
38 // See linux doc Documentation/vm/hugetlbpage.txt
39 explicit PlainTableBloomV1(uint32_t num_probes = 6);
40 void SetTotalBits(Allocator* allocator, uint32_t total_bits,
41 uint32_t locality, size_t huge_page_tlb_size,
42 Logger* logger);
43
44 ~PlainTableBloomV1() {}
45
46 // Assuming single threaded access to this function.
47 void AddHash(uint32_t hash);
48
49 // Multithreaded access to this function is OK
50 bool MayContainHash(uint32_t hash) const;
51
pin_while_exiting()52 void Prefetch(uint32_t hash);
53
54 uint32_t GetNumBlocks() const { return kNumBlocks; }
55
drop(&mut self)56 Slice GetRawData() const { return Slice(data_, GetTotalBits() / 8); }
57
58 void SetRawData(char* raw_data, uint32_t total_bits, uint32_t num_blocks = 0);
59
60 uint32_t GetTotalBits() const { return kTotalBits; }
61
62 bool IsInitialized() const { return kNumBlocks > 0 || kTotalBits > 0; }
63
64 private:
65 uint32_t kTotalBits;
66 uint32_t kNumBlocks;
67 const uint32_t kNumProbes;
68
69 char* data_;
70
71 static constexpr int LOG2_CACHE_LINE_SIZE =
72 folly::constexpr_log2(CACHE_LINE_SIZE);
73 };
74
75 #if defined(_MSC_VER)
76 #pragma warning(push)
77 // local variable is initialized but not referenced
78 #pragma warning(disable : 4189)
79 #endif
80 inline void PlainTableBloomV1::Prefetch(uint32_t h) {
81 if (kNumBlocks != 0) {
82 uint32_t ignored;
83 LegacyLocalityBloomImpl</*ExtraRotates*/ true>::PrepareHashMayMatch(
84 h, kNumBlocks, data_, &ignored, LOG2_CACHE_LINE_SIZE);
85 }
86 }
87 #if defined(_MSC_VER)
88 #pragma warning(pop)
89 #endif
90
91 inline bool PlainTableBloomV1::MayContainHash(uint32_t h) const {
92 assert(IsInitialized());
93 if (kNumBlocks != 0) {
94 return LegacyLocalityBloomImpl<true>::HashMayMatch(
95 h, kNumBlocks, kNumProbes, data_, LOG2_CACHE_LINE_SIZE);
96 } else {
97 return LegacyNoLocalityBloomImpl::HashMayMatch(h, kTotalBits, kNumProbes,
98 data_);
99 }
100 }
101
102 inline void PlainTableBloomV1::AddHash(uint32_t h) {
103 assert(IsInitialized());
104 if (kNumBlocks != 0) {
105 LegacyLocalityBloomImpl<true>::AddHash(h, kNumBlocks, kNumProbes, data_,
106 LOG2_CACHE_LINE_SIZE);
107 } else {
108 LegacyNoLocalityBloomImpl::AddHash(h, kTotalBits, kNumProbes, data_);
109 }
110 }
111
112 class BloomBlockBuilder {
113 public:
114 static const std::string kBloomBlock;
115
116 explicit BloomBlockBuilder(uint32_t num_probes = 6) : bloom_(num_probes) {}
117
118 void SetTotalBits(Allocator* allocator, uint32_t total_bits,
119 uint32_t locality, size_t huge_page_tlb_size,
120 Logger* logger) {
121 bloom_.SetTotalBits(allocator, total_bits, locality, huge_page_tlb_size,
122 logger);
123 }
124
125 uint32_t GetNumBlocks() const { return bloom_.GetNumBlocks(); }
126
127 void AddKeysHashes(const std::vector<uint32_t>& keys_hashes);
128
129 Slice Finish();
130
131 private:
132 PlainTableBloomV1 bloom_;
133 };
134
135 }; // namespace ROCKSDB_NAMESPACE
136