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