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