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) 2011 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 #ifndef ROCKSDB_LITE
11 
12 #include <algorithm>
13 #include <set>
14 
15 #include "db/db_impl/db_impl.h"
16 #include "db/version_set.h"
17 #include "db/write_batch_internal.h"
18 #include "file/filename.h"
19 #include "rocksdb/cache.h"
20 #include "rocksdb/compaction_filter.h"
21 #include "rocksdb/db.h"
22 #include "rocksdb/env.h"
23 #include "rocksdb/filter_policy.h"
24 #include "rocksdb/slice_transform.h"
25 #include "rocksdb/table.h"
26 #include "table/meta_blocks.h"
27 #include "table/plain/plain_table_bloom.h"
28 #include "table/plain/plain_table_factory.h"
29 #include "table/plain/plain_table_key_coding.h"
30 #include "table/plain/plain_table_reader.h"
31 #include "table/table_builder.h"
32 #include "test_util/testharness.h"
33 #include "test_util/testutil.h"
34 #include "util/cast_util.h"
35 #include "util/hash.h"
36 #include "util/mutexlock.h"
37 #include "util/random.h"
38 #include "util/string_util.h"
39 #include "utilities/merge_operators.h"
40 
41 
42 namespace ROCKSDB_NAMESPACE {
43 class PlainTableKeyDecoderTest : public testing::Test {};
44 
TEST_F(PlainTableKeyDecoderTest,ReadNonMmap)45 TEST_F(PlainTableKeyDecoderTest, ReadNonMmap) {
46   Random rnd(301);
47   const uint32_t kLength = 2222;
48   std::string tmp = rnd.RandomString(kLength);
49   Slice contents(tmp);
50   test::StringSource* string_source =
51       new test::StringSource(contents, 0, false);
52   std::unique_ptr<FSRandomAccessFile> holder(string_source);
53   std::unique_ptr<RandomAccessFileReader> file_reader(
54       new RandomAccessFileReader(std::move(holder), "test"));
55   std::unique_ptr<PlainTableReaderFileInfo> file_info(
56       new PlainTableReaderFileInfo(std::move(file_reader), EnvOptions(),
57                                    kLength));
58 
59   {
60     PlainTableFileReader reader(file_info.get());
61 
62     const uint32_t kReadSize = 77;
63     for (uint32_t pos = 0; pos < kLength; pos += kReadSize) {
64       uint32_t read_size = std::min(kLength - pos, kReadSize);
65       Slice out;
66       ASSERT_TRUE(reader.Read(pos, read_size, &out));
67       ASSERT_EQ(0, out.compare(tmp.substr(pos, read_size)));
68     }
69 
70     ASSERT_LT(uint32_t(string_source->total_reads()), kLength / kReadSize / 2);
71   }
72 
73   std::vector<std::vector<std::pair<uint32_t, uint32_t>>> reads = {
74       {{600, 30}, {590, 30}, {600, 20}, {600, 40}},
75       {{800, 20}, {100, 20}, {500, 20}, {1500, 20}, {100, 20}, {80, 20}},
76       {{1000, 20}, {500, 20}, {1000, 50}},
77       {{1000, 20}, {500, 20}, {500, 20}},
78       {{1000, 20}, {500, 20}, {200, 20}, {500, 20}},
79       {{1000, 20}, {500, 20}, {200, 20}, {1000, 50}},
80       {{600, 500}, {610, 20}, {100, 20}},
81       {{500, 100}, {490, 100}, {550, 50}},
82   };
83 
84   std::vector<int> num_file_reads = {2, 6, 2, 2, 4, 3, 2, 2};
85 
86   for (size_t i = 0; i < reads.size(); i++) {
87     string_source->set_total_reads(0);
88     PlainTableFileReader reader(file_info.get());
89     for (auto p : reads[i]) {
90       Slice out;
91       ASSERT_TRUE(reader.Read(p.first, p.second, &out));
92       ASSERT_EQ(0, out.compare(tmp.substr(p.first, p.second)));
93     }
94     ASSERT_EQ(num_file_reads[i], string_source->total_reads());
95   }
96 }
97 
98 class PlainTableDBTest : public testing::Test,
99                          public testing::WithParamInterface<bool> {
100  protected:
101  private:
102   std::string dbname_;
103   Env* env_;
104   DB* db_;
105 
106   bool mmap_mode_;
107   Options last_options_;
108 
109  public:
PlainTableDBTest()110   PlainTableDBTest() : env_(Env::Default()) {}
111 
~PlainTableDBTest()112   ~PlainTableDBTest() override {
113     delete db_;
114     EXPECT_OK(DestroyDB(dbname_, Options()));
115   }
116 
SetUp()117   void SetUp() override {
118     mmap_mode_ = GetParam();
119     dbname_ = test::PerThreadDBPath("plain_table_db_test");
120     EXPECT_OK(DestroyDB(dbname_, Options()));
121     db_ = nullptr;
122     Reopen();
123   }
124 
125   // Return the current option configuration.
CurrentOptions()126   Options CurrentOptions() {
127     Options options;
128 
129     PlainTableOptions plain_table_options;
130     plain_table_options.user_key_len = 0;
131     plain_table_options.bloom_bits_per_key = 2;
132     plain_table_options.hash_table_ratio = 0.8;
133     plain_table_options.index_sparseness = 3;
134     plain_table_options.huge_page_tlb_size = 0;
135     plain_table_options.encoding_type = kPrefix;
136     plain_table_options.full_scan_mode = false;
137     plain_table_options.store_index_in_file = false;
138 
139     options.table_factory.reset(NewPlainTableFactory(plain_table_options));
140     options.memtable_factory.reset(NewHashLinkListRepFactory(4, 0, 3, true));
141 
142     options.prefix_extractor.reset(NewFixedPrefixTransform(8));
143     options.allow_mmap_reads = mmap_mode_;
144     options.allow_concurrent_memtable_write = false;
145     options.unordered_write = false;
146     return options;
147   }
148 
dbfull()149   DBImpl* dbfull() { return static_cast_with_check<DBImpl>(db_); }
150 
Reopen(Options * options=nullptr)151   void Reopen(Options* options = nullptr) {
152     ASSERT_OK(TryReopen(options));
153   }
154 
Close()155   void Close() {
156     delete db_;
157     db_ = nullptr;
158   }
159 
mmap_mode() const160   bool mmap_mode() const { return mmap_mode_; }
161 
DestroyAndReopen(Options * options=nullptr)162   void DestroyAndReopen(Options* options = nullptr) {
163     //Destroy using last options
164     Destroy(&last_options_);
165     ASSERT_OK(TryReopen(options));
166   }
167 
Destroy(Options * options)168   void Destroy(Options* options) {
169     delete db_;
170     db_ = nullptr;
171     ASSERT_OK(DestroyDB(dbname_, *options));
172   }
173 
PureReopen(Options * options,DB ** db)174   Status PureReopen(Options* options, DB** db) {
175     return DB::Open(*options, dbname_, db);
176   }
177 
ReopenForReadOnly(Options * options)178   Status ReopenForReadOnly(Options* options) {
179     delete db_;
180     db_ = nullptr;
181     return DB::OpenForReadOnly(*options, dbname_, &db_);
182   }
183 
TryReopen(Options * options=nullptr)184   Status TryReopen(Options* options = nullptr) {
185     delete db_;
186     db_ = nullptr;
187     Options opts;
188     if (options != nullptr) {
189       opts = *options;
190     } else {
191       opts = CurrentOptions();
192       opts.create_if_missing = true;
193     }
194     last_options_ = opts;
195 
196     return DB::Open(opts, dbname_, &db_);
197   }
198 
Put(const Slice & k,const Slice & v)199   Status Put(const Slice& k, const Slice& v) {
200     return db_->Put(WriteOptions(), k, v);
201   }
202 
Delete(const std::string & k)203   Status Delete(const std::string& k) {
204     return db_->Delete(WriteOptions(), k);
205   }
206 
Get(const std::string & k,const Snapshot * snapshot=nullptr)207   std::string Get(const std::string& k, const Snapshot* snapshot = nullptr) {
208     ReadOptions options;
209     options.snapshot = snapshot;
210     std::string result;
211     Status s = db_->Get(options, k, &result);
212     if (s.IsNotFound()) {
213       result = "NOT_FOUND";
214     } else if (!s.ok()) {
215       result = s.ToString();
216     }
217     return result;
218   }
219 
220 
NumTableFilesAtLevel(int level)221   int NumTableFilesAtLevel(int level) {
222     std::string property;
223     EXPECT_TRUE(db_->GetProperty(
224         "rocksdb.num-files-at-level" + NumberToString(level), &property));
225     return atoi(property.c_str());
226   }
227 
228   // Return spread of files per level
FilesPerLevel()229   std::string FilesPerLevel() {
230     std::string result;
231     size_t last_non_zero_offset = 0;
232     for (int level = 0; level < db_->NumberLevels(); level++) {
233       int f = NumTableFilesAtLevel(level);
234       char buf[100];
235       snprintf(buf, sizeof(buf), "%s%d", (level ? "," : ""), f);
236       result += buf;
237       if (f > 0) {
238         last_non_zero_offset = result.size();
239       }
240     }
241     result.resize(last_non_zero_offset);
242     return result;
243   }
244 
IterStatus(Iterator * iter)245   std::string IterStatus(Iterator* iter) {
246     std::string result;
247     if (iter->Valid()) {
248       result = iter->key().ToString() + "->" + iter->value().ToString();
249     } else {
250       result = "(invalid)";
251     }
252     return result;
253   }
254 };
255 
TEST_P(PlainTableDBTest,Empty)256 TEST_P(PlainTableDBTest, Empty) {
257   ASSERT_TRUE(dbfull() != nullptr);
258   ASSERT_EQ("NOT_FOUND", Get("0000000000000foo"));
259 }
260 
261 extern const uint64_t kPlainTableMagicNumber;
262 
263 class TestPlainTableReader : public PlainTableReader {
264  public:
TestPlainTableReader(const EnvOptions & env_options,const InternalKeyComparator & icomparator,EncodingType encoding_type,uint64_t file_size,int bloom_bits_per_key,double hash_table_ratio,size_t index_sparseness,const TableProperties * table_properties,std::unique_ptr<RandomAccessFileReader> && file,const ImmutableOptions & ioptions,const SliceTransform * prefix_extractor,bool * expect_bloom_not_match,bool store_index_in_file,uint32_t column_family_id,const std::string & column_family_name)265   TestPlainTableReader(
266       const EnvOptions& env_options, const InternalKeyComparator& icomparator,
267       EncodingType encoding_type, uint64_t file_size, int bloom_bits_per_key,
268       double hash_table_ratio, size_t index_sparseness,
269       const TableProperties* table_properties,
270       std::unique_ptr<RandomAccessFileReader>&& file,
271       const ImmutableOptions& ioptions, const SliceTransform* prefix_extractor,
272       bool* expect_bloom_not_match, bool store_index_in_file,
273       uint32_t column_family_id, const std::string& column_family_name)
274       : PlainTableReader(ioptions, std::move(file), env_options, icomparator,
275                          encoding_type, file_size, table_properties,
276                          prefix_extractor),
277         expect_bloom_not_match_(expect_bloom_not_match) {
278     Status s = MmapDataIfNeeded();
279     EXPECT_TRUE(s.ok());
280 
281     s = PopulateIndex(const_cast<TableProperties*>(table_properties),
282                       bloom_bits_per_key, hash_table_ratio, index_sparseness,
283                       2 * 1024 * 1024);
284     EXPECT_TRUE(s.ok());
285 
286     TableProperties* props = const_cast<TableProperties*>(table_properties);
287     EXPECT_EQ(column_family_id, static_cast<uint32_t>(props->column_family_id));
288     EXPECT_EQ(column_family_name, props->column_family_name);
289     if (store_index_in_file) {
290       auto bloom_version_ptr = props->user_collected_properties.find(
291           PlainTablePropertyNames::kBloomVersion);
292       EXPECT_TRUE(bloom_version_ptr != props->user_collected_properties.end());
293       EXPECT_EQ(bloom_version_ptr->second, std::string("1"));
294       if (ioptions.bloom_locality > 0) {
295         auto num_blocks_ptr = props->user_collected_properties.find(
296             PlainTablePropertyNames::kNumBloomBlocks);
297         EXPECT_TRUE(num_blocks_ptr != props->user_collected_properties.end());
298       }
299     }
300     table_properties_.reset(props);
301   }
302 
~TestPlainTableReader()303   ~TestPlainTableReader() override {}
304 
305  private:
MatchBloom(uint32_t hash) const306   bool MatchBloom(uint32_t hash) const override {
307     bool ret = PlainTableReader::MatchBloom(hash);
308     if (*expect_bloom_not_match_) {
309       EXPECT_TRUE(!ret);
310     } else {
311       EXPECT_TRUE(ret);
312     }
313     return ret;
314   }
315   bool* expect_bloom_not_match_;
316 };
317 
318 extern const uint64_t kPlainTableMagicNumber;
319 class TestPlainTableFactory : public PlainTableFactory {
320  public:
TestPlainTableFactory(bool * expect_bloom_not_match,const PlainTableOptions & options,uint32_t column_family_id,std::string column_family_name)321   explicit TestPlainTableFactory(bool* expect_bloom_not_match,
322                                  const PlainTableOptions& options,
323                                  uint32_t column_family_id,
324                                  std::string column_family_name)
325       : PlainTableFactory(options),
326         bloom_bits_per_key_(options.bloom_bits_per_key),
327         hash_table_ratio_(options.hash_table_ratio),
328         index_sparseness_(options.index_sparseness),
329         store_index_in_file_(options.store_index_in_file),
330         expect_bloom_not_match_(expect_bloom_not_match),
331         column_family_id_(column_family_id),
332         column_family_name_(std::move(column_family_name)) {}
333 
334   using PlainTableFactory::NewTableReader;
NewTableReader(const ReadOptions &,const TableReaderOptions & table_reader_options,std::unique_ptr<RandomAccessFileReader> && file,uint64_t file_size,std::unique_ptr<TableReader> * table,bool) const335   Status NewTableReader(
336       const ReadOptions& /*ro*/, const TableReaderOptions& table_reader_options,
337       std::unique_ptr<RandomAccessFileReader>&& file, uint64_t file_size,
338       std::unique_ptr<TableReader>* table,
339       bool /*prefetch_index_and_filter_in_cache*/) const override {
340     TableProperties* props = nullptr;
341     auto s =
342         ReadTableProperties(file.get(), file_size, kPlainTableMagicNumber,
343                             table_reader_options.ioptions, &props,
344                             true /* compression_type_missing */);
345     EXPECT_TRUE(s.ok());
346 
347     if (store_index_in_file_) {
348       BlockHandle bloom_block_handle;
349       s = FindMetaBlock(file.get(), file_size, kPlainTableMagicNumber,
350                         table_reader_options.ioptions,
351                         BloomBlockBuilder::kBloomBlock, &bloom_block_handle,
352                         /* compression_type_missing */ true);
353       EXPECT_TRUE(s.ok());
354 
355       BlockHandle index_block_handle;
356       s = FindMetaBlock(file.get(), file_size, kPlainTableMagicNumber,
357                         table_reader_options.ioptions,
358                         PlainTableIndexBuilder::kPlainTableIndexBlock,
359                         &index_block_handle, /* compression_type_missing */ true);
360       EXPECT_TRUE(s.ok());
361     }
362 
363     auto& user_props = props->user_collected_properties;
364     auto encoding_type_prop =
365         user_props.find(PlainTablePropertyNames::kEncodingType);
366     assert(encoding_type_prop != user_props.end());
367     EncodingType encoding_type = static_cast<EncodingType>(
368         DecodeFixed32(encoding_type_prop->second.c_str()));
369 
370     std::unique_ptr<PlainTableReader> new_reader(new TestPlainTableReader(
371         table_reader_options.env_options,
372         table_reader_options.internal_comparator, encoding_type, file_size,
373         bloom_bits_per_key_, hash_table_ratio_, index_sparseness_, props,
374         std::move(file), table_reader_options.ioptions,
375         table_reader_options.prefix_extractor, expect_bloom_not_match_,
376         store_index_in_file_, column_family_id_, column_family_name_));
377 
378     *table = std::move(new_reader);
379     return s;
380   }
381 
382  private:
383   int bloom_bits_per_key_;
384   double hash_table_ratio_;
385   size_t index_sparseness_;
386   bool store_index_in_file_;
387   bool* expect_bloom_not_match_;
388   const uint32_t column_family_id_;
389   const std::string column_family_name_;
390 };
391 
TEST_P(PlainTableDBTest,BadOptions1)392 TEST_P(PlainTableDBTest, BadOptions1) {
393   // Build with a prefix extractor
394   ASSERT_OK(Put("1000000000000foo", "v1"));
395   ASSERT_OK(dbfull()->TEST_FlushMemTable());
396 
397   // Bad attempt to re-open without a prefix extractor
398   Options options = CurrentOptions();
399   options.prefix_extractor.reset();
400   ASSERT_EQ(
401       "Invalid argument: Prefix extractor is missing when opening a PlainTable "
402       "built using a prefix extractor",
403       TryReopen(&options).ToString());
404 
405   // Bad attempt to re-open with different prefix extractor
406   options.prefix_extractor.reset(NewFixedPrefixTransform(6));
407   ASSERT_EQ(
408       "Invalid argument: Prefix extractor given doesn't match the one used to "
409       "build PlainTable",
410       TryReopen(&options).ToString());
411 
412   // Correct prefix extractor
413   options.prefix_extractor.reset(NewFixedPrefixTransform(8));
414   Reopen(&options);
415   ASSERT_EQ("v1", Get("1000000000000foo"));
416 }
417 
TEST_P(PlainTableDBTest,BadOptions2)418 TEST_P(PlainTableDBTest, BadOptions2) {
419   Options options = CurrentOptions();
420   options.prefix_extractor.reset();
421   options.create_if_missing = true;
422   DestroyAndReopen(&options);
423   // Build without a prefix extractor
424   // (apparently works even if hash_table_ratio > 0)
425   ASSERT_OK(Put("1000000000000foo", "v1"));
426   // Build without a prefix extractor, this call will fail and returns the
427   // status for this bad attempt.
428   ASSERT_NOK(dbfull()->TEST_FlushMemTable());
429 
430   // Bad attempt to re-open with hash_table_ratio > 0 and no prefix extractor
431   Status s = TryReopen(&options);
432   ASSERT_EQ(
433       "Not implemented: PlainTable requires a prefix extractor enable prefix "
434       "hash mode.",
435       s.ToString());
436 
437   // OK to open with hash_table_ratio == 0 and no prefix extractor
438   PlainTableOptions plain_table_options;
439   plain_table_options.hash_table_ratio = 0;
440   options.table_factory.reset(NewPlainTableFactory(plain_table_options));
441   Reopen(&options);
442   ASSERT_EQ("v1", Get("1000000000000foo"));
443 
444   // OK to open newly with a prefix_extractor and hash table; builds index
445   // in memory.
446   options = CurrentOptions();
447   Reopen(&options);
448   ASSERT_EQ("v1", Get("1000000000000foo"));
449 }
450 
TEST_P(PlainTableDBTest,Flush)451 TEST_P(PlainTableDBTest, Flush) {
452   for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
453        huge_page_tlb_size += 2 * 1024 * 1024) {
454     for (EncodingType encoding_type : {kPlain, kPrefix}) {
455     for (int bloom = -1; bloom <= 117; bloom += 117) {
456       const int bloom_bits = std::max(bloom, 0);
457       const bool full_scan_mode = bloom < 0;
458       for (int total_order = 0; total_order <= 1; total_order++) {
459         for (int store_index_in_file = 0; store_index_in_file <= 1;
460              ++store_index_in_file) {
461           Options options = CurrentOptions();
462           options.create_if_missing = true;
463           // Set only one bucket to force bucket conflict.
464           // Test index interval for the same prefix to be 1, 2 and 4
465           if (total_order) {
466             options.prefix_extractor.reset();
467 
468             PlainTableOptions plain_table_options;
469             plain_table_options.user_key_len = 0;
470             plain_table_options.bloom_bits_per_key = bloom_bits;
471             plain_table_options.hash_table_ratio = 0;
472             plain_table_options.index_sparseness = 2;
473             plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
474             plain_table_options.encoding_type = encoding_type;
475             plain_table_options.full_scan_mode = full_scan_mode;
476             plain_table_options.store_index_in_file = store_index_in_file;
477 
478             options.table_factory.reset(
479                 NewPlainTableFactory(plain_table_options));
480           } else {
481             PlainTableOptions plain_table_options;
482             plain_table_options.user_key_len = 0;
483             plain_table_options.bloom_bits_per_key = bloom_bits;
484             plain_table_options.hash_table_ratio = 0.75;
485             plain_table_options.index_sparseness = 16;
486             plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
487             plain_table_options.encoding_type = encoding_type;
488             plain_table_options.full_scan_mode = full_scan_mode;
489             plain_table_options.store_index_in_file = store_index_in_file;
490 
491             options.table_factory.reset(
492                 NewPlainTableFactory(plain_table_options));
493           }
494           DestroyAndReopen(&options);
495           uint64_t int_num;
496           ASSERT_TRUE(dbfull()->GetIntProperty(
497               "rocksdb.estimate-table-readers-mem", &int_num));
498           ASSERT_EQ(int_num, 0U);
499 
500           ASSERT_OK(Put("1000000000000foo", "v1"));
501           ASSERT_OK(Put("0000000000000bar", "v2"));
502           ASSERT_OK(Put("1000000000000foo", "v3"));
503           ASSERT_OK(dbfull()->TEST_FlushMemTable());
504 
505           ASSERT_TRUE(dbfull()->GetIntProperty(
506               "rocksdb.estimate-table-readers-mem", &int_num));
507           ASSERT_GT(int_num, 0U);
508 
509           TablePropertiesCollection ptc;
510           ASSERT_OK(
511               reinterpret_cast<DB*>(dbfull())->GetPropertiesOfAllTables(&ptc));
512           ASSERT_EQ(1U, ptc.size());
513           auto row = ptc.begin();
514           auto tp = row->second;
515 
516           if (full_scan_mode) {
517             // Does not support Get/Seek
518             std::unique_ptr<Iterator> iter(dbfull()->NewIterator(ReadOptions()));
519             iter->SeekToFirst();
520             ASSERT_TRUE(iter->Valid());
521             ASSERT_EQ("0000000000000bar", iter->key().ToString());
522             ASSERT_EQ("v2", iter->value().ToString());
523             iter->Next();
524             ASSERT_TRUE(iter->Valid());
525             ASSERT_EQ("1000000000000foo", iter->key().ToString());
526             ASSERT_EQ("v3", iter->value().ToString());
527             iter->Next();
528             ASSERT_TRUE(!iter->Valid());
529             ASSERT_TRUE(iter->status().ok());
530           } else {
531             if (!store_index_in_file) {
532               ASSERT_EQ(total_order ? "4" : "12",
533                         (tp->user_collected_properties)
534                             .at("plain_table_hash_table_size"));
535               ASSERT_EQ("0", (tp->user_collected_properties)
536                                  .at("plain_table_sub_index_size"));
537             } else {
538               ASSERT_EQ("0", (tp->user_collected_properties)
539                                  .at("plain_table_hash_table_size"));
540               ASSERT_EQ("0", (tp->user_collected_properties)
541                                  .at("plain_table_sub_index_size"));
542             }
543             ASSERT_EQ("v3", Get("1000000000000foo"));
544             ASSERT_EQ("v2", Get("0000000000000bar"));
545           }
546         }
547         }
548       }
549     }
550   }
551 }
552 
TEST_P(PlainTableDBTest,Flush2)553 TEST_P(PlainTableDBTest, Flush2) {
554   for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
555        huge_page_tlb_size += 2 * 1024 * 1024) {
556     for (EncodingType encoding_type : {kPlain, kPrefix}) {
557     for (int bloom_bits = 0; bloom_bits <= 117; bloom_bits += 117) {
558       for (int total_order = 0; total_order <= 1; total_order++) {
559         for (int store_index_in_file = 0; store_index_in_file <= 1;
560              ++store_index_in_file) {
561           if (encoding_type == kPrefix && total_order) {
562             continue;
563           }
564           if (!bloom_bits && store_index_in_file) {
565             continue;
566           }
567           if (total_order && store_index_in_file) {
568           continue;
569         }
570         bool expect_bloom_not_match = false;
571         Options options = CurrentOptions();
572         options.create_if_missing = true;
573         // Set only one bucket to force bucket conflict.
574         // Test index interval for the same prefix to be 1, 2 and 4
575         PlainTableOptions plain_table_options;
576         if (total_order) {
577           options.prefix_extractor = nullptr;
578           plain_table_options.hash_table_ratio = 0;
579           plain_table_options.index_sparseness = 2;
580         } else {
581           plain_table_options.hash_table_ratio = 0.75;
582           plain_table_options.index_sparseness = 16;
583         }
584         plain_table_options.user_key_len = kPlainTableVariableLength;
585         plain_table_options.bloom_bits_per_key = bloom_bits;
586         plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
587         plain_table_options.encoding_type = encoding_type;
588         plain_table_options.store_index_in_file = store_index_in_file;
589         options.table_factory.reset(new TestPlainTableFactory(
590             &expect_bloom_not_match, plain_table_options,
591             0 /* column_family_id */, kDefaultColumnFamilyName));
592 
593         DestroyAndReopen(&options);
594         ASSERT_OK(Put("0000000000000bar", "b"));
595         ASSERT_OK(Put("1000000000000foo", "v1"));
596         ASSERT_OK(dbfull()->TEST_FlushMemTable());
597 
598         ASSERT_OK(Put("1000000000000foo", "v2"));
599         ASSERT_OK(dbfull()->TEST_FlushMemTable());
600         ASSERT_EQ("v2", Get("1000000000000foo"));
601 
602         ASSERT_OK(Put("0000000000000eee", "v3"));
603         ASSERT_OK(dbfull()->TEST_FlushMemTable());
604         ASSERT_EQ("v3", Get("0000000000000eee"));
605 
606         ASSERT_OK(Delete("0000000000000bar"));
607         ASSERT_OK(dbfull()->TEST_FlushMemTable());
608         ASSERT_EQ("NOT_FOUND", Get("0000000000000bar"));
609 
610         ASSERT_OK(Put("0000000000000eee", "v5"));
611         ASSERT_OK(Put("9000000000000eee", "v5"));
612         ASSERT_OK(dbfull()->TEST_FlushMemTable());
613         ASSERT_EQ("v5", Get("0000000000000eee"));
614 
615         // Test Bloom Filter
616         if (bloom_bits > 0) {
617           // Neither key nor value should exist.
618           expect_bloom_not_match = true;
619           ASSERT_EQ("NOT_FOUND", Get("5_not00000000bar"));
620           // Key doesn't exist any more but prefix exists.
621           if (total_order) {
622             ASSERT_EQ("NOT_FOUND", Get("1000000000000not"));
623             ASSERT_EQ("NOT_FOUND", Get("0000000000000not"));
624           }
625           expect_bloom_not_match = false;
626         }
627       }
628       }
629     }
630     }
631   }
632 }
633 
TEST_P(PlainTableDBTest,Immortal)634 TEST_P(PlainTableDBTest, Immortal) {
635   for (EncodingType encoding_type : {kPlain, kPrefix}) {
636     Options options = CurrentOptions();
637     options.create_if_missing = true;
638     options.max_open_files = -1;
639     // Set only one bucket to force bucket conflict.
640     // Test index interval for the same prefix to be 1, 2 and 4
641     PlainTableOptions plain_table_options;
642     plain_table_options.hash_table_ratio = 0.75;
643     plain_table_options.index_sparseness = 16;
644     plain_table_options.user_key_len = kPlainTableVariableLength;
645     plain_table_options.bloom_bits_per_key = 10;
646     plain_table_options.encoding_type = encoding_type;
647     options.table_factory.reset(NewPlainTableFactory(plain_table_options));
648 
649     DestroyAndReopen(&options);
650     ASSERT_OK(Put("0000000000000bar", "b"));
651     ASSERT_OK(Put("1000000000000foo", "v1"));
652     ASSERT_OK(dbfull()->TEST_FlushMemTable());
653 
654     int copied = 0;
655     ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->SetCallBack(
656         "GetContext::SaveValue::PinSelf", [&](void* /*arg*/) { copied++; });
657     ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->EnableProcessing();
658     ASSERT_EQ("b", Get("0000000000000bar"));
659     ASSERT_EQ("v1", Get("1000000000000foo"));
660     ASSERT_EQ(2, copied);
661     copied = 0;
662 
663     Close();
664     ASSERT_OK(ReopenForReadOnly(&options));
665 
666     ASSERT_EQ("b", Get("0000000000000bar"));
667     ASSERT_EQ("v1", Get("1000000000000foo"));
668     ASSERT_EQ("NOT_FOUND", Get("1000000000000bar"));
669     if (mmap_mode()) {
670       ASSERT_EQ(0, copied);
671     } else {
672       ASSERT_EQ(2, copied);
673     }
674     ROCKSDB_NAMESPACE::SyncPoint::GetInstance()->DisableProcessing();
675   }
676 }
677 
TEST_P(PlainTableDBTest,Iterator)678 TEST_P(PlainTableDBTest, Iterator) {
679   for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
680        huge_page_tlb_size += 2 * 1024 * 1024) {
681     for (EncodingType encoding_type : {kPlain, kPrefix}) {
682     for (int bloom_bits = 0; bloom_bits <= 117; bloom_bits += 117) {
683       for (int total_order = 0; total_order <= 1; total_order++) {
684         if (encoding_type == kPrefix && total_order == 1) {
685           continue;
686         }
687         bool expect_bloom_not_match = false;
688         Options options = CurrentOptions();
689         options.create_if_missing = true;
690         // Set only one bucket to force bucket conflict.
691         // Test index interval for the same prefix to be 1, 2 and 4
692         if (total_order) {
693           options.prefix_extractor = nullptr;
694 
695           PlainTableOptions plain_table_options;
696           plain_table_options.user_key_len = 16;
697           plain_table_options.bloom_bits_per_key = bloom_bits;
698           plain_table_options.hash_table_ratio = 0;
699           plain_table_options.index_sparseness = 2;
700           plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
701           plain_table_options.encoding_type = encoding_type;
702 
703           options.table_factory.reset(new TestPlainTableFactory(
704               &expect_bloom_not_match, plain_table_options,
705               0 /* column_family_id */, kDefaultColumnFamilyName));
706         } else {
707           PlainTableOptions plain_table_options;
708           plain_table_options.user_key_len = 16;
709           plain_table_options.bloom_bits_per_key = bloom_bits;
710           plain_table_options.hash_table_ratio = 0.75;
711           plain_table_options.index_sparseness = 16;
712           plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
713           plain_table_options.encoding_type = encoding_type;
714 
715           options.table_factory.reset(new TestPlainTableFactory(
716               &expect_bloom_not_match, plain_table_options,
717               0 /* column_family_id */, kDefaultColumnFamilyName));
718         }
719         DestroyAndReopen(&options);
720 
721         ASSERT_OK(Put("1000000000foo002", "v_2"));
722         ASSERT_OK(Put("0000000000000bar", "random"));
723         ASSERT_OK(Put("1000000000foo001", "v1"));
724         ASSERT_OK(Put("3000000000000bar", "bar_v"));
725         ASSERT_OK(Put("1000000000foo003", "v__3"));
726         ASSERT_OK(Put("1000000000foo004", "v__4"));
727         ASSERT_OK(Put("1000000000foo005", "v__5"));
728         ASSERT_OK(Put("1000000000foo007", "v__7"));
729         ASSERT_OK(Put("1000000000foo008", "v__8"));
730         ASSERT_OK(dbfull()->TEST_FlushMemTable());
731         ASSERT_EQ("v1", Get("1000000000foo001"));
732         ASSERT_EQ("v__3", Get("1000000000foo003"));
733         Iterator* iter = dbfull()->NewIterator(ReadOptions());
734         iter->Seek("1000000000foo000");
735         ASSERT_TRUE(iter->Valid());
736         ASSERT_EQ("1000000000foo001", iter->key().ToString());
737         ASSERT_EQ("v1", iter->value().ToString());
738 
739         iter->Next();
740         ASSERT_TRUE(iter->Valid());
741         ASSERT_EQ("1000000000foo002", iter->key().ToString());
742         ASSERT_EQ("v_2", iter->value().ToString());
743 
744         iter->Next();
745         ASSERT_TRUE(iter->Valid());
746         ASSERT_EQ("1000000000foo003", iter->key().ToString());
747         ASSERT_EQ("v__3", iter->value().ToString());
748 
749         iter->Next();
750         ASSERT_TRUE(iter->Valid());
751         ASSERT_EQ("1000000000foo004", iter->key().ToString());
752         ASSERT_EQ("v__4", iter->value().ToString());
753 
754         iter->Seek("3000000000000bar");
755         ASSERT_TRUE(iter->Valid());
756         ASSERT_EQ("3000000000000bar", iter->key().ToString());
757         ASSERT_EQ("bar_v", iter->value().ToString());
758 
759         iter->Seek("1000000000foo000");
760         ASSERT_TRUE(iter->Valid());
761         ASSERT_EQ("1000000000foo001", iter->key().ToString());
762         ASSERT_EQ("v1", iter->value().ToString());
763 
764         iter->Seek("1000000000foo005");
765         ASSERT_TRUE(iter->Valid());
766         ASSERT_EQ("1000000000foo005", iter->key().ToString());
767         ASSERT_EQ("v__5", iter->value().ToString());
768 
769         iter->Seek("1000000000foo006");
770         ASSERT_TRUE(iter->Valid());
771         ASSERT_EQ("1000000000foo007", iter->key().ToString());
772         ASSERT_EQ("v__7", iter->value().ToString());
773 
774         iter->Seek("1000000000foo008");
775         ASSERT_TRUE(iter->Valid());
776         ASSERT_EQ("1000000000foo008", iter->key().ToString());
777         ASSERT_EQ("v__8", iter->value().ToString());
778 
779         if (total_order == 0) {
780           iter->Seek("1000000000foo009");
781           ASSERT_TRUE(iter->Valid());
782           ASSERT_EQ("3000000000000bar", iter->key().ToString());
783         }
784 
785         // Test Bloom Filter
786         if (bloom_bits > 0) {
787           if (!total_order) {
788             // Neither key nor value should exist.
789             expect_bloom_not_match = true;
790             iter->Seek("2not000000000bar");
791             ASSERT_TRUE(!iter->Valid());
792             ASSERT_EQ("NOT_FOUND", Get("2not000000000bar"));
793             expect_bloom_not_match = false;
794           } else {
795             expect_bloom_not_match = true;
796             ASSERT_EQ("NOT_FOUND", Get("2not000000000bar"));
797             expect_bloom_not_match = false;
798           }
799         }
800         ASSERT_OK(iter->status());
801         delete iter;
802       }
803     }
804     }
805   }
806 }
807 
808 namespace {
NthKey(size_t n,char filler)809 std::string NthKey(size_t n, char filler) {
810   std::string rv(16, filler);
811   rv[0] = n % 10;
812   rv[1] = (n / 10) % 10;
813   rv[2] = (n / 100) % 10;
814   rv[3] = (n / 1000) % 10;
815   return rv;
816 }
817 }  // anonymous namespace
818 
TEST_P(PlainTableDBTest,BloomSchema)819 TEST_P(PlainTableDBTest, BloomSchema) {
820   Options options = CurrentOptions();
821   options.create_if_missing = true;
822   for (int bloom_locality = 0; bloom_locality <= 1; bloom_locality++) {
823     options.bloom_locality = bloom_locality;
824     PlainTableOptions plain_table_options;
825     plain_table_options.user_key_len = 16;
826     plain_table_options.bloom_bits_per_key = 3;  // high FP rate for test
827     plain_table_options.hash_table_ratio = 0.75;
828     plain_table_options.index_sparseness = 16;
829     plain_table_options.huge_page_tlb_size = 0;
830     plain_table_options.encoding_type = kPlain;
831 
832     bool expect_bloom_not_match = false;
833     options.table_factory.reset(new TestPlainTableFactory(
834         &expect_bloom_not_match, plain_table_options, 0 /* column_family_id */,
835         kDefaultColumnFamilyName));
836     DestroyAndReopen(&options);
837 
838     for (unsigned i = 0; i < 2345; ++i) {
839       ASSERT_OK(Put(NthKey(i, 'y'), "added"));
840     }
841     ASSERT_OK(dbfull()->TEST_FlushMemTable());
842     ASSERT_EQ("added", Get(NthKey(42, 'y')));
843 
844     for (unsigned i = 0; i < 32; ++i) {
845       // Known pattern of Bloom filter false positives can detect schema change
846       // with high probability. Known FPs stuffed into bits:
847       uint32_t pattern;
848       if (!bloom_locality) {
849         pattern = 1785868347UL;
850       } else if (CACHE_LINE_SIZE == 64U) {
851         pattern = 2421694657UL;
852       } else if (CACHE_LINE_SIZE == 128U) {
853         pattern = 788710956UL;
854       } else {
855         ASSERT_EQ(CACHE_LINE_SIZE, 256U);
856         pattern = 163905UL;
857       }
858       bool expect_fp = pattern & (1UL << i);
859       // fprintf(stderr, "expect_fp@%u: %d\n", i, (int)expect_fp);
860       expect_bloom_not_match = !expect_fp;
861       ASSERT_EQ("NOT_FOUND", Get(NthKey(i, 'n')));
862     }
863   }
864 }
865 
866 namespace {
MakeLongKey(size_t length,char c)867 std::string MakeLongKey(size_t length, char c) {
868   return std::string(length, c);
869 }
870 }  // namespace
871 
TEST_P(PlainTableDBTest,IteratorLargeKeys)872 TEST_P(PlainTableDBTest, IteratorLargeKeys) {
873   Options options = CurrentOptions();
874 
875   PlainTableOptions plain_table_options;
876   plain_table_options.user_key_len = 0;
877   plain_table_options.bloom_bits_per_key = 0;
878   plain_table_options.hash_table_ratio = 0;
879 
880   options.table_factory.reset(NewPlainTableFactory(plain_table_options));
881   options.create_if_missing = true;
882   options.prefix_extractor.reset();
883   DestroyAndReopen(&options);
884 
885   std::string key_list[] = {
886       MakeLongKey(30, '0'),
887       MakeLongKey(16, '1'),
888       MakeLongKey(32, '2'),
889       MakeLongKey(60, '3'),
890       MakeLongKey(90, '4'),
891       MakeLongKey(50, '5'),
892       MakeLongKey(26, '6')
893   };
894 
895   for (size_t i = 0; i < 7; i++) {
896     ASSERT_OK(Put(key_list[i], ToString(i)));
897   }
898 
899   ASSERT_OK(dbfull()->TEST_FlushMemTable());
900 
901   Iterator* iter = dbfull()->NewIterator(ReadOptions());
902   iter->Seek(key_list[0]);
903 
904   for (size_t i = 0; i < 7; i++) {
905     ASSERT_TRUE(iter->Valid());
906     ASSERT_EQ(key_list[i], iter->key().ToString());
907     ASSERT_EQ(ToString(i), iter->value().ToString());
908     iter->Next();
909   }
910 
911   ASSERT_TRUE(!iter->Valid());
912 
913   delete iter;
914 }
915 
916 namespace {
MakeLongKeyWithPrefix(size_t length,char c)917 std::string MakeLongKeyWithPrefix(size_t length, char c) {
918   return "00000000" + std::string(length - 8, c);
919 }
920 }  // namespace
921 
TEST_P(PlainTableDBTest,IteratorLargeKeysWithPrefix)922 TEST_P(PlainTableDBTest, IteratorLargeKeysWithPrefix) {
923   Options options = CurrentOptions();
924 
925   PlainTableOptions plain_table_options;
926   plain_table_options.user_key_len = 16;
927   plain_table_options.bloom_bits_per_key = 0;
928   plain_table_options.hash_table_ratio = 0.8;
929   plain_table_options.index_sparseness = 3;
930   plain_table_options.huge_page_tlb_size = 0;
931   plain_table_options.encoding_type = kPrefix;
932 
933   options.table_factory.reset(NewPlainTableFactory(plain_table_options));
934   options.create_if_missing = true;
935   DestroyAndReopen(&options);
936 
937   std::string key_list[] = {
938       MakeLongKeyWithPrefix(30, '0'), MakeLongKeyWithPrefix(16, '1'),
939       MakeLongKeyWithPrefix(32, '2'), MakeLongKeyWithPrefix(60, '3'),
940       MakeLongKeyWithPrefix(90, '4'), MakeLongKeyWithPrefix(50, '5'),
941       MakeLongKeyWithPrefix(26, '6')};
942 
943   for (size_t i = 0; i < 7; i++) {
944     ASSERT_OK(Put(key_list[i], ToString(i)));
945   }
946 
947   ASSERT_OK(dbfull()->TEST_FlushMemTable());
948 
949   Iterator* iter = dbfull()->NewIterator(ReadOptions());
950   iter->Seek(key_list[0]);
951 
952   for (size_t i = 0; i < 7; i++) {
953     ASSERT_TRUE(iter->Valid());
954     ASSERT_EQ(key_list[i], iter->key().ToString());
955     ASSERT_EQ(ToString(i), iter->value().ToString());
956     iter->Next();
957   }
958 
959   ASSERT_TRUE(!iter->Valid());
960 
961   delete iter;
962 }
963 
TEST_P(PlainTableDBTest,IteratorReverseSuffixComparator)964 TEST_P(PlainTableDBTest, IteratorReverseSuffixComparator) {
965   Options options = CurrentOptions();
966   options.create_if_missing = true;
967   // Set only one bucket to force bucket conflict.
968   // Test index interval for the same prefix to be 1, 2 and 4
969   test::SimpleSuffixReverseComparator comp;
970   options.comparator = &comp;
971   DestroyAndReopen(&options);
972 
973   ASSERT_OK(Put("1000000000foo002", "v_2"));
974   ASSERT_OK(Put("0000000000000bar", "random"));
975   ASSERT_OK(Put("1000000000foo001", "v1"));
976   ASSERT_OK(Put("3000000000000bar", "bar_v"));
977   ASSERT_OK(Put("1000000000foo003", "v__3"));
978   ASSERT_OK(Put("1000000000foo004", "v__4"));
979   ASSERT_OK(Put("1000000000foo005", "v__5"));
980   ASSERT_OK(Put("1000000000foo007", "v__7"));
981   ASSERT_OK(Put("1000000000foo008", "v__8"));
982   ASSERT_OK(dbfull()->TEST_FlushMemTable());
983   ASSERT_EQ("v1", Get("1000000000foo001"));
984   ASSERT_EQ("v__3", Get("1000000000foo003"));
985   Iterator* iter = dbfull()->NewIterator(ReadOptions());
986   iter->Seek("1000000000foo009");
987   ASSERT_TRUE(iter->Valid());
988   ASSERT_EQ("1000000000foo008", iter->key().ToString());
989   ASSERT_EQ("v__8", iter->value().ToString());
990 
991   iter->Next();
992   ASSERT_TRUE(iter->Valid());
993   ASSERT_EQ("1000000000foo007", iter->key().ToString());
994   ASSERT_EQ("v__7", iter->value().ToString());
995 
996   iter->Next();
997   ASSERT_TRUE(iter->Valid());
998   ASSERT_EQ("1000000000foo005", iter->key().ToString());
999   ASSERT_EQ("v__5", iter->value().ToString());
1000 
1001   iter->Next();
1002   ASSERT_TRUE(iter->Valid());
1003   ASSERT_EQ("1000000000foo004", iter->key().ToString());
1004   ASSERT_EQ("v__4", iter->value().ToString());
1005 
1006   iter->Seek("3000000000000bar");
1007   ASSERT_TRUE(iter->Valid());
1008   ASSERT_EQ("3000000000000bar", iter->key().ToString());
1009   ASSERT_EQ("bar_v", iter->value().ToString());
1010 
1011   iter->Seek("1000000000foo005");
1012   ASSERT_TRUE(iter->Valid());
1013   ASSERT_EQ("1000000000foo005", iter->key().ToString());
1014   ASSERT_EQ("v__5", iter->value().ToString());
1015 
1016   iter->Seek("1000000000foo006");
1017   ASSERT_TRUE(iter->Valid());
1018   ASSERT_EQ("1000000000foo005", iter->key().ToString());
1019   ASSERT_EQ("v__5", iter->value().ToString());
1020 
1021   iter->Seek("1000000000foo008");
1022   ASSERT_TRUE(iter->Valid());
1023   ASSERT_EQ("1000000000foo008", iter->key().ToString());
1024   ASSERT_EQ("v__8", iter->value().ToString());
1025 
1026   iter->Seek("1000000000foo000");
1027   ASSERT_TRUE(iter->Valid());
1028   ASSERT_EQ("3000000000000bar", iter->key().ToString());
1029 
1030   delete iter;
1031 }
1032 
TEST_P(PlainTableDBTest,HashBucketConflict)1033 TEST_P(PlainTableDBTest, HashBucketConflict) {
1034   for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
1035        huge_page_tlb_size += 2 * 1024 * 1024) {
1036     for (unsigned char i = 1; i <= 3; i++) {
1037       Options options = CurrentOptions();
1038       options.create_if_missing = true;
1039       // Set only one bucket to force bucket conflict.
1040       // Test index interval for the same prefix to be 1, 2 and 4
1041 
1042       PlainTableOptions plain_table_options;
1043       plain_table_options.user_key_len = 16;
1044       plain_table_options.bloom_bits_per_key = 0;
1045       plain_table_options.hash_table_ratio = 0;
1046       plain_table_options.index_sparseness = 2 ^ i;
1047       plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
1048 
1049       options.table_factory.reset(NewPlainTableFactory(plain_table_options));
1050 
1051       DestroyAndReopen(&options);
1052       ASSERT_OK(Put("5000000000000fo0", "v1"));
1053       ASSERT_OK(Put("5000000000000fo1", "v2"));
1054       ASSERT_OK(Put("5000000000000fo2", "v"));
1055       ASSERT_OK(Put("2000000000000fo0", "v3"));
1056       ASSERT_OK(Put("2000000000000fo1", "v4"));
1057       ASSERT_OK(Put("2000000000000fo2", "v"));
1058       ASSERT_OK(Put("2000000000000fo3", "v"));
1059 
1060       ASSERT_OK(dbfull()->TEST_FlushMemTable());
1061 
1062       ASSERT_EQ("v1", Get("5000000000000fo0"));
1063       ASSERT_EQ("v2", Get("5000000000000fo1"));
1064       ASSERT_EQ("v3", Get("2000000000000fo0"));
1065       ASSERT_EQ("v4", Get("2000000000000fo1"));
1066 
1067       ASSERT_EQ("NOT_FOUND", Get("5000000000000bar"));
1068       ASSERT_EQ("NOT_FOUND", Get("2000000000000bar"));
1069       ASSERT_EQ("NOT_FOUND", Get("5000000000000fo8"));
1070       ASSERT_EQ("NOT_FOUND", Get("2000000000000fo8"));
1071 
1072       ReadOptions ro;
1073       Iterator* iter = dbfull()->NewIterator(ro);
1074 
1075       iter->Seek("5000000000000fo0");
1076       ASSERT_TRUE(iter->Valid());
1077       ASSERT_EQ("5000000000000fo0", iter->key().ToString());
1078       iter->Next();
1079       ASSERT_TRUE(iter->Valid());
1080       ASSERT_EQ("5000000000000fo1", iter->key().ToString());
1081 
1082       iter->Seek("5000000000000fo1");
1083       ASSERT_TRUE(iter->Valid());
1084       ASSERT_EQ("5000000000000fo1", iter->key().ToString());
1085 
1086       iter->Seek("2000000000000fo0");
1087       ASSERT_TRUE(iter->Valid());
1088       ASSERT_EQ("2000000000000fo0", iter->key().ToString());
1089       iter->Next();
1090       ASSERT_TRUE(iter->Valid());
1091       ASSERT_EQ("2000000000000fo1", iter->key().ToString());
1092 
1093       iter->Seek("2000000000000fo1");
1094       ASSERT_TRUE(iter->Valid());
1095       ASSERT_EQ("2000000000000fo1", iter->key().ToString());
1096 
1097       iter->Seek("2000000000000bar");
1098       ASSERT_TRUE(iter->Valid());
1099       ASSERT_EQ("2000000000000fo0", iter->key().ToString());
1100 
1101       iter->Seek("5000000000000bar");
1102       ASSERT_TRUE(iter->Valid());
1103       ASSERT_EQ("5000000000000fo0", iter->key().ToString());
1104 
1105       iter->Seek("2000000000000fo8");
1106       ASSERT_TRUE(!iter->Valid() ||
1107                   options.comparator->Compare(iter->key(), "20000001") > 0);
1108 
1109       iter->Seek("5000000000000fo8");
1110       ASSERT_TRUE(!iter->Valid());
1111 
1112       iter->Seek("1000000000000fo2");
1113       ASSERT_TRUE(!iter->Valid());
1114 
1115       iter->Seek("3000000000000fo2");
1116       ASSERT_TRUE(!iter->Valid());
1117 
1118       iter->Seek("8000000000000fo2");
1119       ASSERT_TRUE(!iter->Valid());
1120 
1121       ASSERT_OK(iter->status());
1122       delete iter;
1123     }
1124   }
1125 }
1126 
TEST_P(PlainTableDBTest,HashBucketConflictReverseSuffixComparator)1127 TEST_P(PlainTableDBTest, HashBucketConflictReverseSuffixComparator) {
1128   for (size_t huge_page_tlb_size = 0; huge_page_tlb_size <= 2 * 1024 * 1024;
1129        huge_page_tlb_size += 2 * 1024 * 1024) {
1130     for (unsigned char i = 1; i <= 3; i++) {
1131       Options options = CurrentOptions();
1132       options.create_if_missing = true;
1133       test::SimpleSuffixReverseComparator comp;
1134       options.comparator = &comp;
1135       // Set only one bucket to force bucket conflict.
1136       // Test index interval for the same prefix to be 1, 2 and 4
1137 
1138       PlainTableOptions plain_table_options;
1139       plain_table_options.user_key_len = 16;
1140       plain_table_options.bloom_bits_per_key = 0;
1141       plain_table_options.hash_table_ratio = 0;
1142       plain_table_options.index_sparseness = 2 ^ i;
1143       plain_table_options.huge_page_tlb_size = huge_page_tlb_size;
1144 
1145       options.table_factory.reset(NewPlainTableFactory(plain_table_options));
1146       DestroyAndReopen(&options);
1147       ASSERT_OK(Put("5000000000000fo0", "v1"));
1148       ASSERT_OK(Put("5000000000000fo1", "v2"));
1149       ASSERT_OK(Put("5000000000000fo2", "v"));
1150       ASSERT_OK(Put("2000000000000fo0", "v3"));
1151       ASSERT_OK(Put("2000000000000fo1", "v4"));
1152       ASSERT_OK(Put("2000000000000fo2", "v"));
1153       ASSERT_OK(Put("2000000000000fo3", "v"));
1154 
1155       ASSERT_OK(dbfull()->TEST_FlushMemTable());
1156 
1157       ASSERT_EQ("v1", Get("5000000000000fo0"));
1158       ASSERT_EQ("v2", Get("5000000000000fo1"));
1159       ASSERT_EQ("v3", Get("2000000000000fo0"));
1160       ASSERT_EQ("v4", Get("2000000000000fo1"));
1161 
1162       ASSERT_EQ("NOT_FOUND", Get("5000000000000bar"));
1163       ASSERT_EQ("NOT_FOUND", Get("2000000000000bar"));
1164       ASSERT_EQ("NOT_FOUND", Get("5000000000000fo8"));
1165       ASSERT_EQ("NOT_FOUND", Get("2000000000000fo8"));
1166 
1167       ReadOptions ro;
1168       Iterator* iter = dbfull()->NewIterator(ro);
1169 
1170       iter->Seek("5000000000000fo1");
1171       ASSERT_TRUE(iter->Valid());
1172       ASSERT_EQ("5000000000000fo1", iter->key().ToString());
1173       iter->Next();
1174       ASSERT_TRUE(iter->Valid());
1175       ASSERT_EQ("5000000000000fo0", iter->key().ToString());
1176 
1177       iter->Seek("5000000000000fo1");
1178       ASSERT_TRUE(iter->Valid());
1179       ASSERT_EQ("5000000000000fo1", iter->key().ToString());
1180 
1181       iter->Seek("2000000000000fo1");
1182       ASSERT_TRUE(iter->Valid());
1183       ASSERT_EQ("2000000000000fo1", iter->key().ToString());
1184       iter->Next();
1185       ASSERT_TRUE(iter->Valid());
1186       ASSERT_EQ("2000000000000fo0", iter->key().ToString());
1187 
1188       iter->Seek("2000000000000fo1");
1189       ASSERT_TRUE(iter->Valid());
1190       ASSERT_EQ("2000000000000fo1", iter->key().ToString());
1191 
1192       iter->Seek("2000000000000var");
1193       ASSERT_TRUE(iter->Valid());
1194       ASSERT_EQ("2000000000000fo3", iter->key().ToString());
1195 
1196       iter->Seek("5000000000000var");
1197       ASSERT_TRUE(iter->Valid());
1198       ASSERT_EQ("5000000000000fo2", iter->key().ToString());
1199 
1200       std::string seek_key = "2000000000000bar";
1201       iter->Seek(seek_key);
1202       ASSERT_TRUE(!iter->Valid() ||
1203                   options.prefix_extractor->Transform(iter->key()) !=
1204                       options.prefix_extractor->Transform(seek_key));
1205 
1206       iter->Seek("1000000000000fo2");
1207       ASSERT_TRUE(!iter->Valid());
1208 
1209       iter->Seek("3000000000000fo2");
1210       ASSERT_TRUE(!iter->Valid());
1211 
1212       iter->Seek("8000000000000fo2");
1213       ASSERT_TRUE(!iter->Valid());
1214 
1215       ASSERT_OK(iter->status());
1216       delete iter;
1217     }
1218   }
1219 }
1220 
TEST_P(PlainTableDBTest,NonExistingKeyToNonEmptyBucket)1221 TEST_P(PlainTableDBTest, NonExistingKeyToNonEmptyBucket) {
1222   Options options = CurrentOptions();
1223   options.create_if_missing = true;
1224   // Set only one bucket to force bucket conflict.
1225   // Test index interval for the same prefix to be 1, 2 and 4
1226   PlainTableOptions plain_table_options;
1227   plain_table_options.user_key_len = 16;
1228   plain_table_options.bloom_bits_per_key = 0;
1229   plain_table_options.hash_table_ratio = 0;
1230   plain_table_options.index_sparseness = 5;
1231 
1232   options.table_factory.reset(NewPlainTableFactory(plain_table_options));
1233   DestroyAndReopen(&options);
1234   ASSERT_OK(Put("5000000000000fo0", "v1"));
1235   ASSERT_OK(Put("5000000000000fo1", "v2"));
1236   ASSERT_OK(Put("5000000000000fo2", "v3"));
1237 
1238   ASSERT_OK(dbfull()->TEST_FlushMemTable());
1239 
1240   ASSERT_EQ("v1", Get("5000000000000fo0"));
1241   ASSERT_EQ("v2", Get("5000000000000fo1"));
1242   ASSERT_EQ("v3", Get("5000000000000fo2"));
1243 
1244   ASSERT_EQ("NOT_FOUND", Get("8000000000000bar"));
1245   ASSERT_EQ("NOT_FOUND", Get("1000000000000bar"));
1246 
1247   Iterator* iter = dbfull()->NewIterator(ReadOptions());
1248 
1249   iter->Seek("5000000000000bar");
1250   ASSERT_TRUE(iter->Valid());
1251   ASSERT_EQ("5000000000000fo0", iter->key().ToString());
1252 
1253   iter->Seek("5000000000000fo8");
1254   ASSERT_TRUE(!iter->Valid());
1255 
1256   iter->Seek("1000000000000fo2");
1257   ASSERT_TRUE(!iter->Valid());
1258 
1259   iter->Seek("8000000000000fo2");
1260   ASSERT_TRUE(!iter->Valid());
1261 
1262   ASSERT_OK(iter->status());
1263   delete iter;
1264 }
1265 
Key(int i)1266 static std::string Key(int i) {
1267   char buf[100];
1268   snprintf(buf, sizeof(buf), "key_______%06d", i);
1269   return std::string(buf);
1270 }
1271 
TEST_P(PlainTableDBTest,CompactionTrigger)1272 TEST_P(PlainTableDBTest, CompactionTrigger) {
1273   Options options = CurrentOptions();
1274   options.write_buffer_size = 120 << 10;  // 120KB
1275   options.num_levels = 3;
1276   options.level0_file_num_compaction_trigger = 3;
1277   Reopen(&options);
1278 
1279   Random rnd(301);
1280 
1281   for (int num = 0; num < options.level0_file_num_compaction_trigger - 1;
1282       num++) {
1283     std::vector<std::string> values;
1284     // Write 120KB (10 values, each 12K)
1285     for (int i = 0; i < 10; i++) {
1286       values.push_back(rnd.RandomString(12 << 10));
1287       ASSERT_OK(Put(Key(i), values[i]));
1288     }
1289     ASSERT_OK(Put(Key(999), ""));
1290     ASSERT_OK(dbfull()->TEST_WaitForFlushMemTable());
1291     ASSERT_EQ(NumTableFilesAtLevel(0), num + 1);
1292   }
1293 
1294   //generate one more file in level-0, and should trigger level-0 compaction
1295   std::vector<std::string> values;
1296   for (int i = 0; i < 12; i++) {
1297     values.push_back(rnd.RandomString(10000));
1298     ASSERT_OK(Put(Key(i), values[i]));
1299   }
1300   ASSERT_OK(Put(Key(999), ""));
1301   ASSERT_OK(dbfull()->TEST_WaitForCompact());
1302 
1303   ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1304   ASSERT_EQ(NumTableFilesAtLevel(1), 1);
1305 }
1306 
TEST_P(PlainTableDBTest,AdaptiveTable)1307 TEST_P(PlainTableDBTest, AdaptiveTable) {
1308   Options options = CurrentOptions();
1309   options.create_if_missing = true;
1310 
1311   options.table_factory.reset(NewPlainTableFactory());
1312   DestroyAndReopen(&options);
1313 
1314   ASSERT_OK(Put("1000000000000foo", "v1"));
1315   ASSERT_OK(Put("0000000000000bar", "v2"));
1316   ASSERT_OK(Put("1000000000000foo", "v3"));
1317   ASSERT_OK(dbfull()->TEST_FlushMemTable());
1318 
1319   options.create_if_missing = false;
1320   std::shared_ptr<TableFactory> block_based_factory(
1321       NewBlockBasedTableFactory());
1322   std::shared_ptr<TableFactory> plain_table_factory(
1323       NewPlainTableFactory());
1324   std::shared_ptr<TableFactory> dummy_factory;
1325   options.table_factory.reset(NewAdaptiveTableFactory(
1326       block_based_factory, block_based_factory, plain_table_factory));
1327   Reopen(&options);
1328   ASSERT_EQ("v3", Get("1000000000000foo"));
1329   ASSERT_EQ("v2", Get("0000000000000bar"));
1330 
1331   ASSERT_OK(Put("2000000000000foo", "v4"));
1332   ASSERT_OK(Put("3000000000000bar", "v5"));
1333   ASSERT_OK(dbfull()->TEST_FlushMemTable());
1334   ASSERT_EQ("v4", Get("2000000000000foo"));
1335   ASSERT_EQ("v5", Get("3000000000000bar"));
1336 
1337   Reopen(&options);
1338   ASSERT_EQ("v3", Get("1000000000000foo"));
1339   ASSERT_EQ("v2", Get("0000000000000bar"));
1340   ASSERT_EQ("v4", Get("2000000000000foo"));
1341   ASSERT_EQ("v5", Get("3000000000000bar"));
1342 
1343   options.paranoid_checks = false;
1344   options.table_factory.reset(NewBlockBasedTableFactory());
1345   Reopen(&options);
1346   ASSERT_NE("v3", Get("1000000000000foo"));
1347 
1348   options.paranoid_checks = false;
1349   options.table_factory.reset(NewPlainTableFactory());
1350   Reopen(&options);
1351   ASSERT_NE("v5", Get("3000000000000bar"));
1352 }
1353 
1354 INSTANTIATE_TEST_CASE_P(PlainTableDBTest, PlainTableDBTest, ::testing::Bool());
1355 
1356 }  // namespace ROCKSDB_NAMESPACE
1357 
main(int argc,char ** argv)1358 int main(int argc, char** argv) {
1359   ::testing::InitGoogleTest(&argc, argv);
1360   return RUN_ALL_TESTS();
1361 }
1362 
1363 #else
1364 #include <stdio.h>
1365 
main(int,char **)1366 int main(int /*argc*/, char** /*argv*/) {
1367   fprintf(stderr, "SKIPPED as plain table is not supported in ROCKSDB_LITE\n");
1368   return 0;
1369 }
1370 
1371 #endif  // !ROCKSDB_LITE
1372