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