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 #include <set>
7
8 #include "table/block_based/full_filter_block.h"
9 #include "rocksdb/filter_policy.h"
10 #include "table/block_based/block_based_table_reader.h"
11 #include "table/block_based/mock_block_based_table.h"
12 #include "table/block_based/filter_policy_internal.h"
13 #include "test_util/testharness.h"
14 #include "test_util/testutil.h"
15 #include "util/coding.h"
16 #include "util/hash.h"
17 #include "util/string_util.h"
18
19 namespace ROCKSDB_NAMESPACE {
20
21 class TestFilterBitsBuilder : public FilterBitsBuilder {
22 public:
TestFilterBitsBuilder()23 explicit TestFilterBitsBuilder() {}
24
25 // Add Key to filter
AddKey(const Slice & key)26 void AddKey(const Slice& key) override {
27 hash_entries_.push_back(Hash(key.data(), key.size(), 1));
28 }
29
30 // Generate the filter using the keys that are added
Finish(std::unique_ptr<const char[]> * buf)31 Slice Finish(std::unique_ptr<const char[]>* buf) override {
32 uint32_t len = static_cast<uint32_t>(hash_entries_.size()) * 4;
33 char* data = new char[len];
34 for (size_t i = 0; i < hash_entries_.size(); i++) {
35 EncodeFixed32(data + i * 4, hash_entries_[i]);
36 }
37 const char* const_data = data;
38 buf->reset(const_data);
39 return Slice(data, len);
40 }
41
42 private:
43 std::vector<uint32_t> hash_entries_;
44 };
45
46 class MockBlockBasedTable : public BlockBasedTable {
47 public:
MockBlockBasedTable(Rep * rep)48 explicit MockBlockBasedTable(Rep* rep)
49 : BlockBasedTable(rep, nullptr /* block_cache_tracer */) {}
50 };
51
52 class TestFilterBitsReader : public FilterBitsReader {
53 public:
TestFilterBitsReader(const Slice & contents)54 explicit TestFilterBitsReader(const Slice& contents)
55 : data_(contents.data()), len_(static_cast<uint32_t>(contents.size())) {}
56
57 // Silence compiler warning about overloaded virtual
58 using FilterBitsReader::MayMatch;
MayMatch(const Slice & entry)59 bool MayMatch(const Slice& entry) override {
60 uint32_t h = Hash(entry.data(), entry.size(), 1);
61 for (size_t i = 0; i + 4 <= len_; i += 4) {
62 if (h == DecodeFixed32(data_ + i)) {
63 return true;
64 }
65 }
66 return false;
67 }
68
69 private:
70 const char* data_;
71 uint32_t len_;
72 };
73
74
75 class TestHashFilter : public FilterPolicy {
76 public:
Name() const77 const char* Name() const override { return "TestHashFilter"; }
78
CreateFilter(const Slice * keys,int n,std::string * dst) const79 void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
80 for (int i = 0; i < n; i++) {
81 uint32_t h = Hash(keys[i].data(), keys[i].size(), 1);
82 PutFixed32(dst, h);
83 }
84 }
85
KeyMayMatch(const Slice & key,const Slice & filter) const86 bool KeyMayMatch(const Slice& key, const Slice& filter) const override {
87 uint32_t h = Hash(key.data(), key.size(), 1);
88 for (unsigned int i = 0; i + 4 <= filter.size(); i += 4) {
89 if (h == DecodeFixed32(filter.data() + i)) {
90 return true;
91 }
92 }
93 return false;
94 }
95
GetFilterBitsBuilder() const96 FilterBitsBuilder* GetFilterBitsBuilder() const override {
97 return new TestFilterBitsBuilder();
98 }
99
GetFilterBitsReader(const Slice & contents) const100 FilterBitsReader* GetFilterBitsReader(const Slice& contents) const override {
101 return new TestFilterBitsReader(contents);
102 }
103 };
104
105 class PluginFullFilterBlockTest : public mock::MockBlockBasedTableTester,
106 public testing::Test {
107 public:
PluginFullFilterBlockTest()108 PluginFullFilterBlockTest()
109 : mock::MockBlockBasedTableTester(new TestHashFilter) {}
110 };
111
TEST_F(PluginFullFilterBlockTest,PluginEmptyBuilder)112 TEST_F(PluginFullFilterBlockTest, PluginEmptyBuilder) {
113 FullFilterBlockBuilder builder(nullptr, true, GetBuilder());
114 Slice slice = builder.Finish();
115 ASSERT_EQ("", EscapeString(slice));
116
117 CachableEntry<ParsedFullFilterBlock> block(
118 new ParsedFullFilterBlock(table_options_.filter_policy.get(),
119 BlockContents(slice)),
120 nullptr /* cache */, nullptr /* cache_handle */, true /* own_value */);
121
122 FullFilterBlockReader reader(table_.get(), std::move(block));
123 // Remain same symantic with blockbased filter
124 ASSERT_TRUE(reader.KeyMayMatch("foo", /*prefix_extractor=*/nullptr,
125 /*block_offset=*/kNotValid,
126 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
127 /*get_context=*/nullptr,
128 /*lookup_context=*/nullptr));
129 }
130
TEST_F(PluginFullFilterBlockTest,PluginSingleChunk)131 TEST_F(PluginFullFilterBlockTest, PluginSingleChunk) {
132 FullFilterBlockBuilder builder(nullptr, true, GetBuilder());
133 builder.Add("foo");
134 builder.Add("bar");
135 builder.Add("box");
136 builder.Add("box");
137 builder.Add("hello");
138 Slice slice = builder.Finish();
139
140 CachableEntry<ParsedFullFilterBlock> block(
141 new ParsedFullFilterBlock(table_options_.filter_policy.get(),
142 BlockContents(slice)),
143 nullptr /* cache */, nullptr /* cache_handle */, true /* own_value */);
144
145 FullFilterBlockReader reader(table_.get(), std::move(block));
146 ASSERT_TRUE(reader.KeyMayMatch("foo", /*prefix_extractor=*/nullptr,
147 /*block_offset=*/kNotValid,
148 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
149 /*get_context=*/nullptr,
150 /*lookup_context=*/nullptr));
151 ASSERT_TRUE(reader.KeyMayMatch("bar", /*prefix_extractor=*/nullptr,
152 /*block_offset=*/kNotValid,
153 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
154 /*get_context=*/nullptr,
155 /*lookup_context=*/nullptr));
156 ASSERT_TRUE(reader.KeyMayMatch("box", /*prefix_extractor=*/nullptr,
157 /*block_offset=*/kNotValid,
158 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
159 /*get_context=*/nullptr,
160 /*lookup_context=*/nullptr));
161 ASSERT_TRUE(reader.KeyMayMatch("hello", /*prefix_extractor=*/nullptr,
162 /*block_offset=*/kNotValid,
163 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
164 /*get_context=*/nullptr,
165 /*lookup_context=*/nullptr));
166 ASSERT_TRUE(reader.KeyMayMatch("foo", /*prefix_extractor=*/nullptr,
167 /*block_offset=*/kNotValid,
168 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
169 /*get_context=*/nullptr,
170 /*lookup_context=*/nullptr));
171 ASSERT_TRUE(!reader.KeyMayMatch(
172 "missing", /*prefix_extractor=*/nullptr, /*block_offset=*/kNotValid,
173 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
174 /*lookup_context=*/nullptr));
175 ASSERT_TRUE(!reader.KeyMayMatch(
176 "other", /*prefix_extractor=*/nullptr, /*block_offset=*/kNotValid,
177 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
178 /*lookup_context=*/nullptr));
179 }
180
181 class FullFilterBlockTest : public mock::MockBlockBasedTableTester,
182 public testing::Test {
183 public:
FullFilterBlockTest()184 FullFilterBlockTest()
185 : mock::MockBlockBasedTableTester(NewBloomFilterPolicy(10, false)) {}
186 };
187
TEST_F(FullFilterBlockTest,EmptyBuilder)188 TEST_F(FullFilterBlockTest, EmptyBuilder) {
189 FullFilterBlockBuilder builder(nullptr, true, GetBuilder());
190 Slice slice = builder.Finish();
191 ASSERT_EQ("", EscapeString(slice));
192
193 CachableEntry<ParsedFullFilterBlock> block(
194 new ParsedFullFilterBlock(table_options_.filter_policy.get(),
195 BlockContents(slice)),
196 nullptr /* cache */, nullptr /* cache_handle */, true /* own_value */);
197
198 FullFilterBlockReader reader(table_.get(), std::move(block));
199 // Remain same symantic with blockbased filter
200 ASSERT_TRUE(reader.KeyMayMatch("foo", /*prefix_extractor=*/nullptr,
201 /*block_offset=*/kNotValid,
202 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
203 /*get_context=*/nullptr,
204 /*lookup_context=*/nullptr));
205 }
206
207 class CountUniqueFilterBitsBuilderWrapper : public FilterBitsBuilder {
208 std::unique_ptr<FilterBitsBuilder> b_;
209 std::set<std::string> uniq_;
210
211 public:
CountUniqueFilterBitsBuilderWrapper(FilterBitsBuilder * b)212 explicit CountUniqueFilterBitsBuilderWrapper(FilterBitsBuilder* b) : b_(b) {}
213
~CountUniqueFilterBitsBuilderWrapper()214 ~CountUniqueFilterBitsBuilderWrapper() override {}
215
AddKey(const Slice & key)216 void AddKey(const Slice& key) override {
217 b_->AddKey(key);
218 uniq_.insert(key.ToString());
219 }
220
Finish(std::unique_ptr<const char[]> * buf)221 Slice Finish(std::unique_ptr<const char[]>* buf) override {
222 Slice rv = b_->Finish(buf);
223 uniq_.clear();
224 return rv;
225 }
226
CalculateNumEntry(const uint32_t bytes)227 int CalculateNumEntry(const uint32_t bytes) override {
228 return b_->CalculateNumEntry(bytes);
229 }
230
CountUnique()231 size_t CountUnique() { return uniq_.size(); }
232 };
233
TEST_F(FullFilterBlockTest,DuplicateEntries)234 TEST_F(FullFilterBlockTest, DuplicateEntries) {
235 { // empty prefixes
236 std::unique_ptr<const SliceTransform> prefix_extractor(
237 NewFixedPrefixTransform(0));
238 auto bits_builder = new CountUniqueFilterBitsBuilderWrapper(GetBuilder());
239 const bool WHOLE_KEY = true;
240 FullFilterBlockBuilder builder(prefix_extractor.get(), WHOLE_KEY,
241 bits_builder);
242 ASSERT_EQ(0, builder.NumAdded());
243 ASSERT_EQ(0, bits_builder->CountUnique());
244 // adds key and empty prefix; both abstractions count them
245 builder.Add("key1");
246 ASSERT_EQ(2, builder.NumAdded());
247 ASSERT_EQ(2, bits_builder->CountUnique());
248 // Add different key (unique) and also empty prefix (not unique).
249 // From here in this test, it's immaterial whether the block builder
250 // can count unique keys.
251 builder.Add("key2");
252 ASSERT_EQ(3, bits_builder->CountUnique());
253 // Empty key -> nothing unique
254 builder.Add("");
255 ASSERT_EQ(3, bits_builder->CountUnique());
256 }
257
258 // mix of empty and non-empty
259 std::unique_ptr<const SliceTransform> prefix_extractor(
260 NewFixedPrefixTransform(7));
261 auto bits_builder = new CountUniqueFilterBitsBuilderWrapper(GetBuilder());
262 const bool WHOLE_KEY = true;
263 FullFilterBlockBuilder builder(prefix_extractor.get(), WHOLE_KEY,
264 bits_builder);
265 ASSERT_EQ(0, builder.NumAdded());
266 builder.Add(""); // test with empty key too
267 builder.Add("prefix1key1");
268 builder.Add("prefix1key1");
269 builder.Add("prefix1key2");
270 builder.Add("prefix1key3");
271 builder.Add("prefix2key4");
272 // 1 empty, 2 non-empty prefixes, and 4 non-empty keys
273 ASSERT_EQ(1 + 2 + 4, bits_builder->CountUnique());
274 }
275
TEST_F(FullFilterBlockTest,SingleChunk)276 TEST_F(FullFilterBlockTest, SingleChunk) {
277 FullFilterBlockBuilder builder(nullptr, true, GetBuilder());
278 ASSERT_EQ(0, builder.NumAdded());
279 builder.Add("foo");
280 builder.Add("bar");
281 builder.Add("box");
282 builder.Add("box");
283 builder.Add("hello");
284 ASSERT_EQ(5, builder.NumAdded());
285 Slice slice = builder.Finish();
286
287 CachableEntry<ParsedFullFilterBlock> block(
288 new ParsedFullFilterBlock(table_options_.filter_policy.get(),
289 BlockContents(slice)),
290 nullptr /* cache */, nullptr /* cache_handle */, true /* own_value */);
291
292 FullFilterBlockReader reader(table_.get(), std::move(block));
293 ASSERT_TRUE(reader.KeyMayMatch("foo", /*prefix_extractor=*/nullptr,
294 /*block_offset=*/kNotValid,
295 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
296 /*get_context=*/nullptr,
297 /*lookup_context=*/nullptr));
298 ASSERT_TRUE(reader.KeyMayMatch("bar", /*prefix_extractor=*/nullptr,
299 /*block_offset=*/kNotValid,
300 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
301 /*get_context=*/nullptr,
302 /*lookup_context=*/nullptr));
303 ASSERT_TRUE(reader.KeyMayMatch("box", /*prefix_extractor=*/nullptr,
304 /*block_offset=*/kNotValid,
305 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
306 /*get_context=*/nullptr,
307 /*lookup_context=*/nullptr));
308 ASSERT_TRUE(reader.KeyMayMatch("hello", /*prefix_extractor=*/nullptr,
309 /*block_offset=*/kNotValid,
310 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
311 /*get_context=*/nullptr,
312 /*lookup_context=*/nullptr));
313 ASSERT_TRUE(reader.KeyMayMatch("foo", /*prefix_extractor=*/nullptr,
314 /*block_offset=*/kNotValid,
315 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
316 /*get_context=*/nullptr,
317 /*lookup_context=*/nullptr));
318 ASSERT_TRUE(!reader.KeyMayMatch(
319 "missing", /*prefix_extractor=*/nullptr, /*block_offset=*/kNotValid,
320 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
321 /*lookup_context=*/nullptr));
322 ASSERT_TRUE(!reader.KeyMayMatch(
323 "other", /*prefix_extractor=*/nullptr, /*block_offset=*/kNotValid,
324 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
325 /*lookup_context=*/nullptr));
326 }
327
328 } // namespace ROCKSDB_NAMESPACE
329
main(int argc,char ** argv)330 int main(int argc, char** argv) {
331 ::testing::InitGoogleTest(&argc, argv);
332 return RUN_ALL_TESTS();
333 }
334