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 #include "table/block_based/block_based_filter_block.h"
11 #include "rocksdb/filter_policy.h"
12 #include "table/block_based/block_based_table_reader.h"
13 #include "table/block_based/mock_block_based_table.h"
14 #include "test_util/testharness.h"
15 #include "test_util/testutil.h"
16 #include "util/coding.h"
17 #include "util/hash.h"
18 #include "util/string_util.h"
19
20 namespace ROCKSDB_NAMESPACE {
21
22 // For testing: emit an array with one hash value per key
23 class TestHashFilter : public FilterPolicy {
24 public:
Name() const25 const char* Name() const override { return "TestHashFilter"; }
26
CreateFilter(const Slice * keys,int n,std::string * dst) const27 void CreateFilter(const Slice* keys, int n, std::string* dst) const override {
28 for (int i = 0; i < n; i++) {
29 uint32_t h = Hash(keys[i].data(), keys[i].size(), 1);
30 PutFixed32(dst, h);
31 }
32 }
33
KeyMayMatch(const Slice & key,const Slice & filter) const34 bool KeyMayMatch(const Slice& key, const Slice& filter) const override {
35 uint32_t h = Hash(key.data(), key.size(), 1);
36 for (unsigned int i = 0; i + 4 <= filter.size(); i += 4) {
37 if (h == DecodeFixed32(filter.data() + i)) {
38 return true;
39 }
40 }
41 return false;
42 }
43 };
44
45 class MockBlockBasedTable : public BlockBasedTable {
46 public:
MockBlockBasedTable(Rep * rep)47 explicit MockBlockBasedTable(Rep* rep)
48 : BlockBasedTable(rep, nullptr /* block_cache_tracer */) {}
49 };
50
51 class FilterBlockTest : public mock::MockBlockBasedTableTester,
52 public testing::Test {
53 public:
FilterBlockTest()54 FilterBlockTest() : mock::MockBlockBasedTableTester(new TestHashFilter) {}
55 };
56
TEST_F(FilterBlockTest,EmptyBuilder)57 TEST_F(FilterBlockTest, EmptyBuilder) {
58 BlockBasedFilterBlockBuilder builder(nullptr, table_options_);
59 Slice slice(builder.Finish());
60 ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(slice));
61
62 CachableEntry<BlockContents> block(
63 new BlockContents(slice), nullptr /* cache */, nullptr /* cache_handle */,
64 true /* own_value */);
65
66 BlockBasedFilterBlockReader reader(table_.get(), std::move(block));
67 ASSERT_TRUE(reader.KeyMayMatch(
68 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/uint64_t{0},
69 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
70 /*lookup_context=*/nullptr));
71 ASSERT_TRUE(reader.KeyMayMatch(
72 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/100000,
73 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
74 /*lookup_context=*/nullptr));
75 }
76
TEST_F(FilterBlockTest,SingleChunk)77 TEST_F(FilterBlockTest, SingleChunk) {
78 BlockBasedFilterBlockBuilder builder(nullptr, table_options_);
79 ASSERT_EQ(0, builder.NumAdded());
80 builder.StartBlock(100);
81 builder.Add("foo");
82 builder.Add("bar");
83 builder.Add("box");
84 builder.StartBlock(200);
85 builder.Add("box");
86 builder.StartBlock(300);
87 builder.Add("hello");
88 ASSERT_EQ(5, builder.NumAdded());
89 Slice slice(builder.Finish());
90
91 CachableEntry<BlockContents> block(
92 new BlockContents(slice), nullptr /* cache */, nullptr /* cache_handle */,
93 true /* own_value */);
94
95 BlockBasedFilterBlockReader reader(table_.get(), std::move(block));
96 ASSERT_TRUE(reader.KeyMayMatch("foo", /*prefix_extractor=*/nullptr,
97 /*block_offset=*/100,
98 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
99 /*get_context=*/nullptr,
100 /*lookup_context=*/nullptr));
101 ASSERT_TRUE(reader.KeyMayMatch("bar", /*prefix_extractor=*/nullptr,
102 /*block_offset=*/100,
103 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
104 /*get_context=*/nullptr,
105 /*lookup_context=*/nullptr));
106 ASSERT_TRUE(reader.KeyMayMatch("box", /*prefix_extractor=*/nullptr,
107 /*block_offset=*/100,
108 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
109 /*get_context=*/nullptr,
110 /*lookup_context=*/nullptr));
111 ASSERT_TRUE(reader.KeyMayMatch("hello", /*prefix_extractor=*/nullptr,
112 /*block_offset=*/100,
113 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
114 /*get_context=*/nullptr,
115 /*lookup_context=*/nullptr));
116 ASSERT_TRUE(reader.KeyMayMatch("foo", /*prefix_extractor=*/nullptr,
117 /*block_offset=*/100,
118 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
119 /*get_context=*/nullptr,
120 /*lookup_context=*/nullptr));
121 ASSERT_TRUE(!reader.KeyMayMatch(
122 "missing", /*prefix_extractor=*/nullptr, /*block_offset=*/100,
123 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
124 /*lookup_context=*/nullptr));
125 ASSERT_TRUE(!reader.KeyMayMatch(
126 "other", /*prefix_extractor=*/nullptr, /*block_offset=*/100,
127 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
128 /*lookup_context=*/nullptr));
129 }
130
TEST_F(FilterBlockTest,MultiChunk)131 TEST_F(FilterBlockTest, MultiChunk) {
132 BlockBasedFilterBlockBuilder builder(nullptr, table_options_);
133
134 // First filter
135 builder.StartBlock(0);
136 builder.Add("foo");
137 builder.StartBlock(2000);
138 builder.Add("bar");
139
140 // Second filter
141 builder.StartBlock(3100);
142 builder.Add("box");
143
144 // Third filter is empty
145
146 // Last filter
147 builder.StartBlock(9000);
148 builder.Add("box");
149 builder.Add("hello");
150
151 Slice slice(builder.Finish());
152
153 CachableEntry<BlockContents> block(
154 new BlockContents(slice), nullptr /* cache */, nullptr /* cache_handle */,
155 true /* own_value */);
156
157 BlockBasedFilterBlockReader reader(table_.get(), std::move(block));
158
159 // Check first filter
160 ASSERT_TRUE(reader.KeyMayMatch("foo", /*prefix_extractor=*/nullptr,
161 /*block_offset=*/uint64_t{0},
162 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
163 /*get_context=*/nullptr,
164 /*lookup_context=*/nullptr));
165 ASSERT_TRUE(reader.KeyMayMatch("bar", /*prefix_extractor=*/nullptr,
166 /*block_offset=*/2000,
167 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
168 /*get_context=*/nullptr,
169 /*lookup_context=*/nullptr));
170 ASSERT_TRUE(!reader.KeyMayMatch(
171 "box", /*prefix_extractor=*/nullptr, /*block_offset=*/uint64_t{0},
172 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
173 /*lookup_context=*/nullptr));
174 ASSERT_TRUE(!reader.KeyMayMatch(
175 "hello", /*prefix_extractor=*/nullptr, /*block_offset=*/uint64_t{0},
176 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
177 /*lookup_context=*/nullptr));
178
179 // Check second filter
180 ASSERT_TRUE(reader.KeyMayMatch("box", /*prefix_extractor=*/nullptr,
181 /*block_offset=*/3100,
182 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
183 /*get_context=*/nullptr,
184 /*lookup_context=*/nullptr));
185 ASSERT_TRUE(!reader.KeyMayMatch(
186 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/3100,
187 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
188 /*lookup_context=*/nullptr));
189 ASSERT_TRUE(!reader.KeyMayMatch(
190 "bar", /*prefix_extractor=*/nullptr, /*block_offset=*/3100,
191 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
192 /*lookup_context=*/nullptr));
193 ASSERT_TRUE(!reader.KeyMayMatch(
194 "hello", /*prefix_extractor=*/nullptr, /*block_offset=*/3100,
195 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
196 /*lookup_context=*/nullptr));
197
198 // Check third filter (empty)
199 ASSERT_TRUE(!reader.KeyMayMatch(
200 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/4100,
201 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
202 /*lookup_context=*/nullptr));
203 ASSERT_TRUE(!reader.KeyMayMatch(
204 "bar", /*prefix_extractor=*/nullptr, /*block_offset=*/4100,
205 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
206 /*lookup_context=*/nullptr));
207 ASSERT_TRUE(!reader.KeyMayMatch(
208 "box", /*prefix_extractor=*/nullptr, /*block_offset=*/4100,
209 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
210 /*lookup_context=*/nullptr));
211 ASSERT_TRUE(!reader.KeyMayMatch(
212 "hello", /*prefix_extractor=*/nullptr, /*block_offset=*/4100,
213 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
214 /*lookup_context=*/nullptr));
215
216 // Check last filter
217 ASSERT_TRUE(reader.KeyMayMatch("box", /*prefix_extractor=*/nullptr,
218 /*block_offset=*/9000,
219 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
220 /*get_context=*/nullptr,
221 /*lookup_context=*/nullptr));
222 ASSERT_TRUE(reader.KeyMayMatch("hello", /*prefix_extractor=*/nullptr,
223 /*block_offset=*/9000,
224 /*no_io=*/false, /*const_ikey_ptr=*/nullptr,
225 /*get_context=*/nullptr,
226 /*lookup_context=*/nullptr));
227 ASSERT_TRUE(!reader.KeyMayMatch(
228 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/9000,
229 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
230 /*lookup_context=*/nullptr));
231 ASSERT_TRUE(!reader.KeyMayMatch(
232 "bar", /*prefix_extractor=*/nullptr, /*block_offset=*/9000,
233 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
234 /*lookup_context=*/nullptr));
235 }
236
237 // Test for block based filter block
238 // use new interface in FilterPolicy to create filter builder/reader
239 class BlockBasedFilterBlockTest : public mock::MockBlockBasedTableTester,
240 public testing::Test {
241 public:
BlockBasedFilterBlockTest()242 BlockBasedFilterBlockTest()
243 : mock::MockBlockBasedTableTester(NewBloomFilterPolicy(10, true)) {}
244 };
245
TEST_F(BlockBasedFilterBlockTest,BlockBasedEmptyBuilder)246 TEST_F(BlockBasedFilterBlockTest, BlockBasedEmptyBuilder) {
247 FilterBlockBuilder* builder =
248 new BlockBasedFilterBlockBuilder(nullptr, table_options_);
249 Slice slice(builder->Finish());
250 ASSERT_EQ("\\x00\\x00\\x00\\x00\\x0b", EscapeString(slice));
251
252 CachableEntry<BlockContents> block(
253 new BlockContents(slice), nullptr /* cache */, nullptr /* cache_handle */,
254 true /* own_value */);
255
256 FilterBlockReader* reader =
257 new BlockBasedFilterBlockReader(table_.get(), std::move(block));
258 ASSERT_TRUE(reader->KeyMayMatch(
259 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/uint64_t{0},
260 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
261 /*lookup_context=*/nullptr));
262 ASSERT_TRUE(reader->KeyMayMatch(
263 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/10000,
264 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
265 /*lookup_context=*/nullptr));
266
267 delete builder;
268 delete reader;
269 }
270
TEST_F(BlockBasedFilterBlockTest,BlockBasedSingleChunk)271 TEST_F(BlockBasedFilterBlockTest, BlockBasedSingleChunk) {
272 FilterBlockBuilder* builder =
273 new BlockBasedFilterBlockBuilder(nullptr, table_options_);
274 builder->StartBlock(100);
275 builder->Add("foo");
276 builder->Add("bar");
277 builder->Add("box");
278 builder->StartBlock(200);
279 builder->Add("box");
280 builder->StartBlock(300);
281 builder->Add("hello");
282 Slice slice(builder->Finish());
283
284 CachableEntry<BlockContents> block(
285 new BlockContents(slice), nullptr /* cache */, nullptr /* cache_handle */,
286 true /* own_value */);
287
288 FilterBlockReader* reader =
289 new BlockBasedFilterBlockReader(table_.get(), std::move(block));
290 ASSERT_TRUE(reader->KeyMayMatch(
291 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/100,
292 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
293 /*lookup_context=*/nullptr));
294 ASSERT_TRUE(reader->KeyMayMatch(
295 "bar", /*prefix_extractor=*/nullptr, /*block_offset=*/100,
296 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
297 /*lookup_context=*/nullptr));
298 ASSERT_TRUE(reader->KeyMayMatch(
299 "box", /*prefix_extractor=*/nullptr, /*block_offset=*/100,
300 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
301 /*lookup_context=*/nullptr));
302 ASSERT_TRUE(reader->KeyMayMatch(
303 "hello", /*prefix_extractor=*/nullptr, /*block_offset=*/100,
304 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
305 /*lookup_context=*/nullptr));
306 ASSERT_TRUE(reader->KeyMayMatch(
307 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/100,
308 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
309 /*lookup_context=*/nullptr));
310 ASSERT_TRUE(!reader->KeyMayMatch(
311 "missing", /*prefix_extractor=*/nullptr, /*block_offset=*/100,
312 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
313 /*lookup_context=*/nullptr));
314 ASSERT_TRUE(!reader->KeyMayMatch(
315 "other", /*prefix_extractor=*/nullptr, /*block_offset=*/100,
316 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
317 /*lookup_context=*/nullptr));
318
319 delete builder;
320 delete reader;
321 }
322
TEST_F(BlockBasedFilterBlockTest,BlockBasedMultiChunk)323 TEST_F(BlockBasedFilterBlockTest, BlockBasedMultiChunk) {
324 FilterBlockBuilder* builder =
325 new BlockBasedFilterBlockBuilder(nullptr, table_options_);
326
327 // First filter
328 builder->StartBlock(0);
329 builder->Add("foo");
330 builder->StartBlock(2000);
331 builder->Add("bar");
332
333 // Second filter
334 builder->StartBlock(3100);
335 builder->Add("box");
336
337 // Third filter is empty
338
339 // Last filter
340 builder->StartBlock(9000);
341 builder->Add("box");
342 builder->Add("hello");
343
344 Slice slice(builder->Finish());
345
346 CachableEntry<BlockContents> block(
347 new BlockContents(slice), nullptr /* cache */, nullptr /* cache_handle */,
348 true /* own_value */);
349
350 FilterBlockReader* reader =
351 new BlockBasedFilterBlockReader(table_.get(), std::move(block));
352
353 // Check first filter
354 ASSERT_TRUE(reader->KeyMayMatch(
355 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/uint64_t{0},
356 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
357 /*lookup_context=*/nullptr));
358 ASSERT_TRUE(reader->KeyMayMatch(
359 "bar", /*prefix_extractor=*/nullptr, /*block_offset=*/2000,
360 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
361 /*lookup_context=*/nullptr));
362 ASSERT_TRUE(!reader->KeyMayMatch(
363 "box", /*prefix_extractor=*/nullptr, /*block_offset=*/uint64_t{0},
364 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
365 /*lookup_context=*/nullptr));
366 ASSERT_TRUE(!reader->KeyMayMatch(
367 "hello", /*prefix_extractor=*/nullptr, /*block_offset=*/uint64_t{0},
368 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
369 /*lookup_context=*/nullptr));
370
371 // Check second filter
372 ASSERT_TRUE(reader->KeyMayMatch(
373 "box", /*prefix_extractor=*/nullptr, /*block_offset=*/3100,
374 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
375 /*lookup_context=*/nullptr));
376 ASSERT_TRUE(!reader->KeyMayMatch(
377 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/3100,
378 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
379 /*lookup_context=*/nullptr));
380 ASSERT_TRUE(!reader->KeyMayMatch(
381 "bar", /*prefix_extractor=*/nullptr, /*block_offset=*/3100,
382 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
383 /*lookup_context=*/nullptr));
384 ASSERT_TRUE(!reader->KeyMayMatch(
385 "hello", /*prefix_extractor=*/nullptr, /*block_offset=*/3100,
386 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
387 /*lookup_context=*/nullptr));
388
389 // Check third filter (empty)
390 ASSERT_TRUE(!reader->KeyMayMatch(
391 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/4100,
392 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
393 /*lookup_context=*/nullptr));
394 ASSERT_TRUE(!reader->KeyMayMatch(
395 "bar", /*prefix_extractor=*/nullptr, /*block_offset=*/4100,
396 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
397 /*lookup_context=*/nullptr));
398 ASSERT_TRUE(!reader->KeyMayMatch(
399 "box", /*prefix_extractor=*/nullptr, /*block_offset=*/4100,
400 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
401 /*lookup_context=*/nullptr));
402 ASSERT_TRUE(!reader->KeyMayMatch(
403 "hello", /*prefix_extractor=*/nullptr, /*block_offset=*/4100,
404 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
405 /*lookup_context=*/nullptr));
406
407 // Check last filter
408 ASSERT_TRUE(reader->KeyMayMatch(
409 "box", /*prefix_extractor=*/nullptr, /*block_offset=*/9000,
410 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
411 /*lookup_context=*/nullptr));
412 ASSERT_TRUE(reader->KeyMayMatch(
413 "hello", /*prefix_extractor=*/nullptr, /*block_offset=*/9000,
414 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
415 /*lookup_context=*/nullptr));
416 ASSERT_TRUE(!reader->KeyMayMatch(
417 "foo", /*prefix_extractor=*/nullptr, /*block_offset=*/9000,
418 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
419 /*lookup_context=*/nullptr));
420 ASSERT_TRUE(!reader->KeyMayMatch(
421 "bar", /*prefix_extractor=*/nullptr, /*block_offset=*/9000,
422 /*no_io=*/false, /*const_ikey_ptr=*/nullptr, /*get_context=*/nullptr,
423 /*lookup_context=*/nullptr));
424
425 delete builder;
426 delete reader;
427 }
428
429 } // namespace ROCKSDB_NAMESPACE
430
main(int argc,char ** argv)431 int main(int argc, char** argv) {
432 ::testing::InitGoogleTest(&argc, argv);
433 return RUN_ALL_TESTS();
434 }
435