1// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file. See the AUTHORS file for names of contributors.
4
5#include "leveldb/db.h"
6
7#include <atomic>
8#include <cinttypes>
9#include <string>
10
11#include "gtest/gtest.h"
12#include "db/db_impl.h"
13#include "db/filename.h"
14#include "db/version_set.h"
15#include "db/write_batch_internal.h"
16#include "leveldb/cache.h"
17#include "leveldb/env.h"
18#include "leveldb/filter_policy.h"
19#include "leveldb/table.h"
20#include "port/port.h"
21#include "port/thread_annotations.h"
22#include "util/hash.h"
23#include "util/logging.h"
24#include "util/mutexlock.h"
25#include "util/testutil.h"
26
27namespace leveldb {
28
29static std::string RandomString(Random* rnd, int len) {
30 std::string r;
31 test::RandomString(rnd, len, &r);
32 return r;
33}
34
35static std::string RandomKey(Random* rnd) {
36 int len =
37 (rnd->OneIn(3) ? 1 // Short sometimes to encourage collisions
38 : (rnd->OneIn(100) ? rnd->Skewed(10) : rnd->Uniform(10)));
39 return test::RandomKey(rnd, len);
40}
41
42namespace {
43class AtomicCounter {
44 public:
45 AtomicCounter() : count_(0) {}
46 void Increment() { IncrementBy(1); }
47 void IncrementBy(int count) LOCKS_EXCLUDED(mu_) {
48 MutexLock l(&mu_);
49 count_ += count;
50 }
51 int Read() LOCKS_EXCLUDED(mu_) {
52 MutexLock l(&mu_);
53 return count_;
54 }
55 void Reset() LOCKS_EXCLUDED(mu_) {
56 MutexLock l(&mu_);
57 count_ = 0;
58 }
59
60 private:
61 port::Mutex mu_;
62 int count_ GUARDED_BY(mu_);
63};
64
65void DelayMilliseconds(int millis) {
66 Env::Default()->SleepForMicroseconds(millis * 1000);
67}
68} // namespace
69
70// Test Env to override default Env behavior for testing.
71class TestEnv : public EnvWrapper {
72 public:
73 explicit TestEnv(Env* base) : EnvWrapper(base), ignore_dot_files_(false) {}
74
75 void SetIgnoreDotFiles(bool ignored) { ignore_dot_files_ = ignored; }
76
77 Status GetChildren(const std::string& dir,
78 std::vector<std::string>* result) override {
79 Status s = target()->GetChildren(dir, result);
80 if (!s.ok() || !ignore_dot_files_) {
81 return s;
82 }
83
84 std::vector<std::string>::iterator it = result->begin();
85 while (it != result->end()) {
86 if ((*it == ".") || (*it == "..")) {
87 it = result->erase(it);
88 } else {
89 ++it;
90 }
91 }
92
93 return s;
94 }
95
96 private:
97 bool ignore_dot_files_;
98};
99
100// Special Env used to delay background operations.
101class SpecialEnv : public EnvWrapper {
102 public:
103 // sstable/log Sync() calls are blocked while this pointer is non-null.
104 std::atomic<bool> delay_data_sync_;
105
106 // sstable/log Sync() calls return an error.
107 std::atomic<bool> data_sync_error_;
108
109 // Simulate no-space errors while this pointer is non-null.
110 std::atomic<bool> no_space_;
111
112 // Simulate non-writable file system while this pointer is non-null.
113 std::atomic<bool> non_writable_;
114
115 // Force sync of manifest files to fail while this pointer is non-null.
116 std::atomic<bool> manifest_sync_error_;
117
118 // Force write to manifest files to fail while this pointer is non-null.
119 std::atomic<bool> manifest_write_error_;
120
121 bool count_random_reads_;
122 AtomicCounter random_read_counter_;
123
124 explicit SpecialEnv(Env* base)
125 : EnvWrapper(base),
126 delay_data_sync_(false),
127 data_sync_error_(false),
128 no_space_(false),
129 non_writable_(false),
130 manifest_sync_error_(false),
131 manifest_write_error_(false),
132 count_random_reads_(false) {}
133
134 Status NewWritableFile(const std::string& f, WritableFile** r) {
135 class DataFile : public WritableFile {
136 private:
137 SpecialEnv* const env_;
138 WritableFile* const base_;
139
140 public:
141 DataFile(SpecialEnv* env, WritableFile* base) : env_(env), base_(base) {}
142 ~DataFile() { delete base_; }
143 Status Append(const Slice& data) {
144 if (env_->no_space_.load(std::memory_order_acquire)) {
145 // Drop writes on the floor
146 return Status::OK();
147 } else {
148 return base_->Append(data);
149 }
150 }
151 Status Close() { return base_->Close(); }
152 Status Flush() { return base_->Flush(); }
153 Status Sync() {
154 if (env_->data_sync_error_.load(std::memory_order_acquire)) {
155 return Status::IOError("simulated data sync error");
156 }
157 while (env_->delay_data_sync_.load(std::memory_order_acquire)) {
158 DelayMilliseconds(100);
159 }
160 return base_->Sync();
161 }
162 };
163 class ManifestFile : public WritableFile {
164 private:
165 SpecialEnv* env_;
166 WritableFile* base_;
167
168 public:
169 ManifestFile(SpecialEnv* env, WritableFile* b) : env_(env), base_(b) {}
170 ~ManifestFile() { delete base_; }
171 Status Append(const Slice& data) {
172 if (env_->manifest_write_error_.load(std::memory_order_acquire)) {
173 return Status::IOError("simulated writer error");
174 } else {
175 return base_->Append(data);
176 }
177 }
178 Status Close() { return base_->Close(); }
179 Status Flush() { return base_->Flush(); }
180 Status Sync() {
181 if (env_->manifest_sync_error_.load(std::memory_order_acquire)) {
182 return Status::IOError("simulated sync error");
183 } else {
184 return base_->Sync();
185 }
186 }
187 };
188
189 if (non_writable_.load(std::memory_order_acquire)) {
190 return Status::IOError("simulated write error");
191 }
192
193 Status s = target()->NewWritableFile(f, r);
194 if (s.ok()) {
195 if (strstr(f.c_str(), ".ldb") != nullptr ||
196 strstr(f.c_str(), ".log") != nullptr) {
197 *r = new DataFile(this, *r);
198 } else if (strstr(f.c_str(), "MANIFEST") != nullptr) {
199 *r = new ManifestFile(this, *r);
200 }
201 }
202 return s;
203 }
204
205 Status NewRandomAccessFile(const std::string& f, RandomAccessFile** r) {
206 class CountingFile : public RandomAccessFile {
207 private:
208 RandomAccessFile* target_;
209 AtomicCounter* counter_;
210
211 public:
212 CountingFile(RandomAccessFile* target, AtomicCounter* counter)
213 : target_(target), counter_(counter) {}
214 ~CountingFile() override { delete target_; }
215 Status Read(uint64_t offset, size_t n, Slice* result,
216 char* scratch) const override {
217 counter_->Increment();
218 return target_->Read(offset, n, result, scratch);
219 }
220 };
221
222 Status s = target()->NewRandomAccessFile(f, r);
223 if (s.ok() && count_random_reads_) {
224 *r = new CountingFile(*r, &random_read_counter_);
225 }
226 return s;
227 }
228};
229
230class DBTest : public testing::Test {
231 public:
232 std::string dbname_;
233 SpecialEnv* env_;
234 DB* db_;
235
236 Options last_options_;
237
238 DBTest() : env_(new SpecialEnv(Env::Default())), option_config_(kDefault) {
239 filter_policy_ = NewBloomFilterPolicy(10);
240 dbname_ = testing::TempDir() + "db_test";
241 DestroyDB(dbname_, Options());
242 db_ = nullptr;
243 Reopen();
244 }
245
246 ~DBTest() {
247 delete db_;
248 DestroyDB(dbname_, Options());
249 delete env_;
250 delete filter_policy_;
251 }
252
253 // Switch to a fresh database with the next option configuration to
254 // test. Return false if there are no more configurations to test.
255 bool ChangeOptions() {
256 option_config_++;
257 if (option_config_ >= kEnd) {
258 return false;
259 } else {
260 DestroyAndReopen();
261 return true;
262 }
263 }
264
265 // Return the current option configuration.
266 Options CurrentOptions() {
267 Options options;
268 options.reuse_logs = false;
269 switch (option_config_) {
270 case kReuse:
271 options.reuse_logs = true;
272 break;
273 case kFilter:
274 options.filter_policy = filter_policy_;
275 break;
276 case kUncompressed:
277 options.compression = kNoCompression;
278 break;
279 default:
280 break;
281 }
282 return options;
283 }
284
285 DBImpl* dbfull() { return reinterpret_cast<DBImpl*>(db_); }
286
287 void Reopen(Options* options = nullptr) {
288 ASSERT_LEVELDB_OK(TryReopen(options));
289 }
290
291 void Close() {
292 delete db_;
293 db_ = nullptr;
294 }
295
296 void DestroyAndReopen(Options* options = nullptr) {
297 delete db_;
298 db_ = nullptr;
299 DestroyDB(dbname_, Options());
300 ASSERT_LEVELDB_OK(TryReopen(options));
301 }
302
303 Status TryReopen(Options* options) {
304 delete db_;
305 db_ = nullptr;
306 Options opts;
307 if (options != nullptr) {
308 opts = *options;
309 } else {
310 opts = CurrentOptions();
311 opts.create_if_missing = true;
312 }
313 last_options_ = opts;
314
315 return DB::Open(opts, dbname_, &db_);
316 }
317
318 Status Put(const std::string& k, const std::string& v) {
319 return db_->Put(WriteOptions(), k, v);
320 }
321
322 Status Delete(const std::string& k) { return db_->Delete(WriteOptions(), k); }
323
324 std::string Get(const std::string& k, const Snapshot* snapshot = nullptr) {
325 ReadOptions options;
326 options.snapshot = snapshot;
327 std::string result;
328 Status s = db_->Get(options, k, &result);
329 if (s.IsNotFound()) {
330 result = "NOT_FOUND";
331 } else if (!s.ok()) {
332 result = s.ToString();
333 }
334 return result;
335 }
336
337 // Return a string that contains all key,value pairs in order,
338 // formatted like "(k1->v1)(k2->v2)".
339 std::string Contents() {
340 std::vector<std::string> forward;
341 std::string result;
342 Iterator* iter = db_->NewIterator(ReadOptions());
343 for (iter->SeekToFirst(); iter->Valid(); iter->Next()) {
344 std::string s = IterStatus(iter);
345 result.push_back('(');
346 result.append(s);
347 result.push_back(')');
348 forward.push_back(s);
349 }
350
351 // Check reverse iteration results are the reverse of forward results
352 size_t matched = 0;
353 for (iter->SeekToLast(); iter->Valid(); iter->Prev()) {
354 EXPECT_LT(matched, forward.size());
355 EXPECT_EQ(IterStatus(iter), forward[forward.size() - matched - 1]);
356 matched++;
357 }
358 EXPECT_EQ(matched, forward.size());
359
360 delete iter;
361 return result;
362 }
363
364 std::string AllEntriesFor(const Slice& user_key) {
365 Iterator* iter = dbfull()->TEST_NewInternalIterator();
366 InternalKey target(user_key, kMaxSequenceNumber, kTypeValue);
367 iter->Seek(target.Encode());
368 std::string result;
369 if (!iter->status().ok()) {
370 result = iter->status().ToString();
371 } else {
372 result = "[ ";
373 bool first = true;
374 while (iter->Valid()) {
375 ParsedInternalKey ikey;
376 if (!ParseInternalKey(iter->key(), &ikey)) {
377 result += "CORRUPTED";
378 } else {
379 if (last_options_.comparator->Compare(ikey.user_key, user_key) != 0) {
380 break;
381 }
382 if (!first) {
383 result += ", ";
384 }
385 first = false;
386 switch (ikey.type) {
387 case kTypeValue:
388 result += iter->value().ToString();
389 break;
390 case kTypeDeletion:
391 result += "DEL";
392 break;
393 }
394 }
395 iter->Next();
396 }
397 if (!first) {
398 result += " ";
399 }
400 result += "]";
401 }
402 delete iter;
403 return result;
404 }
405
406 int NumTableFilesAtLevel(int level) {
407 std::string property;
408 EXPECT_TRUE(db_->GetProperty(
409 "leveldb.num-files-at-level" + NumberToString(level), &property));
410 return std::stoi(property);
411 }
412
413 int TotalTableFiles() {
414 int result = 0;
415 for (int level = 0; level < config::kNumLevels; level++) {
416 result += NumTableFilesAtLevel(level);
417 }
418 return result;
419 }
420
421 // Return spread of files per level
422 std::string FilesPerLevel() {
423 std::string result;
424 int last_non_zero_offset = 0;
425 for (int level = 0; level < config::kNumLevels; level++) {
426 int f = NumTableFilesAtLevel(level);
427 char buf[100];
428 std::snprintf(buf, sizeof(buf), "%s%d", (level ? "," : ""), f);
429 result += buf;
430 if (f > 0) {
431 last_non_zero_offset = result.size();
432 }
433 }
434 result.resize(last_non_zero_offset);
435 return result;
436 }
437
438 int CountFiles() {
439 std::vector<std::string> files;
440 env_->GetChildren(dbname_, &files);
441 return static_cast<int>(files.size());
442 }
443
444 uint64_t Size(const Slice& start, const Slice& limit) {
445 Range r(start, limit);
446 uint64_t size;
447 db_->GetApproximateSizes(&r, 1, &size);
448 return size;
449 }
450
451 void Compact(const Slice& start, const Slice& limit) {
452 db_->CompactRange(&start, &limit);
453 }
454
455 // Do n memtable compactions, each of which produces an sstable
456 // covering the range [small_key,large_key].
457 void MakeTables(int n, const std::string& small_key,
458 const std::string& large_key) {
459 for (int i = 0; i < n; i++) {
460 Put(small_key, "begin");
461 Put(large_key, "end");
462 dbfull()->TEST_CompactMemTable();
463 }
464 }
465
466 // Prevent pushing of new sstables into deeper levels by adding
467 // tables that cover a specified range to all levels.
468 void FillLevels(const std::string& smallest, const std::string& largest) {
469 MakeTables(config::kNumLevels, smallest, largest);
470 }
471
472 void DumpFileCounts(const char* label) {
473 std::fprintf(stderr, "---\n%s:\n", label);
474 std::fprintf(
475 stderr, "maxoverlap: %lld\n",
476 static_cast<long long>(dbfull()->TEST_MaxNextLevelOverlappingBytes()));
477 for (int level = 0; level < config::kNumLevels; level++) {
478 int num = NumTableFilesAtLevel(level);
479 if (num > 0) {
480 std::fprintf(stderr, " level %3d : %d files\n", level, num);
481 }
482 }
483 }
484
485 std::string DumpSSTableList() {
486 std::string property;
487 db_->GetProperty("leveldb.sstables", &property);
488 return property;
489 }
490
491 std::string IterStatus(Iterator* iter) {
492 std::string result;
493 if (iter->Valid()) {
494 result = iter->key().ToString() + "->" + iter->value().ToString();
495 } else {
496 result = "(invalid)";
497 }
498 return result;
499 }
500
501 bool DeleteAnSSTFile() {
502 std::vector<std::string> filenames;
503 EXPECT_LEVELDB_OK(env_->GetChildren(dbname_, &filenames));
504 uint64_t number;
505 FileType type;
506 for (size_t i = 0; i < filenames.size(); i++) {
507 if (ParseFileName(filenames[i], &number, &type) && type == kTableFile) {
508 EXPECT_LEVELDB_OK(env_->RemoveFile(TableFileName(dbname_, number)));
509 return true;
510 }
511 }
512 return false;
513 }
514
515 // Returns number of files renamed.
516 int RenameLDBToSST() {
517 std::vector<std::string> filenames;
518 EXPECT_LEVELDB_OK(env_->GetChildren(dbname_, &filenames));
519 uint64_t number;
520 FileType type;
521 int files_renamed = 0;
522 for (size_t i = 0; i < filenames.size(); i++) {
523 if (ParseFileName(filenames[i], &number, &type) && type == kTableFile) {
524 const std::string from = TableFileName(dbname_, number);
525 const std::string to = SSTTableFileName(dbname_, number);
526 EXPECT_LEVELDB_OK(env_->RenameFile(from, to));
527 files_renamed++;
528 }
529 }
530 return files_renamed;
531 }
532
533 private:
534 // Sequence of option configurations to try
535 enum OptionConfig { kDefault, kReuse, kFilter, kUncompressed, kEnd };
536
537 const FilterPolicy* filter_policy_;
538 int option_config_;
539};
540
541TEST_F(DBTest, Empty) {
542 do {
543 ASSERT_TRUE(db_ != nullptr);
544 ASSERT_EQ("NOT_FOUND", Get("foo"));
545 } while (ChangeOptions());
546}
547
548TEST_F(DBTest, EmptyKey) {
549 do {
550 ASSERT_LEVELDB_OK(Put("", "v1"));
551 ASSERT_EQ("v1", Get(""));
552 ASSERT_LEVELDB_OK(Put("", "v2"));
553 ASSERT_EQ("v2", Get(""));
554 } while (ChangeOptions());
555}
556
557TEST_F(DBTest, EmptyValue) {
558 do {
559 ASSERT_LEVELDB_OK(Put("key", "v1"));
560 ASSERT_EQ("v1", Get("key"));
561 ASSERT_LEVELDB_OK(Put("key", ""));
562 ASSERT_EQ("", Get("key"));
563 ASSERT_LEVELDB_OK(Put("key", "v2"));
564 ASSERT_EQ("v2", Get("key"));
565 } while (ChangeOptions());
566}
567
568TEST_F(DBTest, ReadWrite) {
569 do {
570 ASSERT_LEVELDB_OK(Put("foo", "v1"));
571 ASSERT_EQ("v1", Get("foo"));
572 ASSERT_LEVELDB_OK(Put("bar", "v2"));
573 ASSERT_LEVELDB_OK(Put("foo", "v3"));
574 ASSERT_EQ("v3", Get("foo"));
575 ASSERT_EQ("v2", Get("bar"));
576 } while (ChangeOptions());
577}
578
579TEST_F(DBTest, PutDeleteGet) {
580 do {
581 ASSERT_LEVELDB_OK(db_->Put(WriteOptions(), "foo", "v1"));
582 ASSERT_EQ("v1", Get("foo"));
583 ASSERT_LEVELDB_OK(db_->Put(WriteOptions(), "foo", "v2"));
584 ASSERT_EQ("v2", Get("foo"));
585 ASSERT_LEVELDB_OK(db_->Delete(WriteOptions(), "foo"));
586 ASSERT_EQ("NOT_FOUND", Get("foo"));
587 } while (ChangeOptions());
588}
589
590TEST_F(DBTest, GetFromImmutableLayer) {
591 do {
592 Options options = CurrentOptions();
593 options.env = env_;
594 options.write_buffer_size = 100000; // Small write buffer
595 Reopen(&options);
596
597 ASSERT_LEVELDB_OK(Put("foo", "v1"));
598 ASSERT_EQ("v1", Get("foo"));
599
600 // Block sync calls.
601 env_->delay_data_sync_.store(true, std::memory_order_release);
602 Put("k1", std::string(100000, 'x')); // Fill memtable.
603 Put("k2", std::string(100000, 'y')); // Trigger compaction.
604 ASSERT_EQ("v1", Get("foo"));
605 // Release sync calls.
606 env_->delay_data_sync_.store(false, std::memory_order_release);
607 } while (ChangeOptions());
608}
609
610TEST_F(DBTest, GetFromVersions) {
611 do {
612 ASSERT_LEVELDB_OK(Put("foo", "v1"));
613 dbfull()->TEST_CompactMemTable();
614 ASSERT_EQ("v1", Get("foo"));
615 } while (ChangeOptions());
616}
617
618TEST_F(DBTest, GetMemUsage) {
619 do {
620 ASSERT_LEVELDB_OK(Put("foo", "v1"));
621 std::string val;
622 ASSERT_TRUE(db_->GetProperty("leveldb.approximate-memory-usage", &val));
623 int mem_usage = std::stoi(val);
624 ASSERT_GT(mem_usage, 0);
625 ASSERT_LT(mem_usage, 5 * 1024 * 1024);
626 } while (ChangeOptions());
627}
628
629TEST_F(DBTest, GetSnapshot) {
630 do {
631 // Try with both a short key and a long key
632 for (int i = 0; i < 2; i++) {
633 std::string key = (i == 0) ? std::string("foo") : std::string(200, 'x');
634 ASSERT_LEVELDB_OK(Put(key, "v1"));
635 const Snapshot* s1 = db_->GetSnapshot();
636 ASSERT_LEVELDB_OK(Put(key, "v2"));
637 ASSERT_EQ("v2", Get(key));
638 ASSERT_EQ("v1", Get(key, s1));
639 dbfull()->TEST_CompactMemTable();
640 ASSERT_EQ("v2", Get(key));
641 ASSERT_EQ("v1", Get(key, s1));
642 db_->ReleaseSnapshot(s1);
643 }
644 } while (ChangeOptions());
645}
646
647TEST_F(DBTest, GetIdenticalSnapshots) {
648 do {
649 // Try with both a short key and a long key
650 for (int i = 0; i < 2; i++) {
651 std::string key = (i == 0) ? std::string("foo") : std::string(200, 'x');
652 ASSERT_LEVELDB_OK(Put(key, "v1"));
653 const Snapshot* s1 = db_->GetSnapshot();
654 const Snapshot* s2 = db_->GetSnapshot();
655 const Snapshot* s3 = db_->GetSnapshot();
656 ASSERT_LEVELDB_OK(Put(key, "v2"));
657 ASSERT_EQ("v2", Get(key));
658 ASSERT_EQ("v1", Get(key, s1));
659 ASSERT_EQ("v1", Get(key, s2));
660 ASSERT_EQ("v1", Get(key, s3));
661 db_->ReleaseSnapshot(s1);
662 dbfull()->TEST_CompactMemTable();
663 ASSERT_EQ("v2", Get(key));
664 ASSERT_EQ("v1", Get(key, s2));
665 db_->ReleaseSnapshot(s2);
666 ASSERT_EQ("v1", Get(key, s3));
667 db_->ReleaseSnapshot(s3);
668 }
669 } while (ChangeOptions());
670}
671
672TEST_F(DBTest, IterateOverEmptySnapshot) {
673 do {
674 const Snapshot* snapshot = db_->GetSnapshot();
675 ReadOptions read_options;
676 read_options.snapshot = snapshot;
677 ASSERT_LEVELDB_OK(Put("foo", "v1"));
678 ASSERT_LEVELDB_OK(Put("foo", "v2"));
679
680 Iterator* iterator1 = db_->NewIterator(read_options);
681 iterator1->SeekToFirst();
682 ASSERT_TRUE(!iterator1->Valid());
683 delete iterator1;
684
685 dbfull()->TEST_CompactMemTable();
686
687 Iterator* iterator2 = db_->NewIterator(read_options);
688 iterator2->SeekToFirst();
689 ASSERT_TRUE(!iterator2->Valid());
690 delete iterator2;
691
692 db_->ReleaseSnapshot(snapshot);
693 } while (ChangeOptions());
694}
695
696TEST_F(DBTest, GetLevel0Ordering) {
697 do {
698 // Check that we process level-0 files in correct order. The code
699 // below generates two level-0 files where the earlier one comes
700 // before the later one in the level-0 file list since the earlier
701 // one has a smaller "smallest" key.
702 ASSERT_LEVELDB_OK(Put("bar", "b"));
703 ASSERT_LEVELDB_OK(Put("foo", "v1"));
704 dbfull()->TEST_CompactMemTable();
705 ASSERT_LEVELDB_OK(Put("foo", "v2"));
706 dbfull()->TEST_CompactMemTable();
707 ASSERT_EQ("v2", Get("foo"));
708 } while (ChangeOptions());
709}
710
711TEST_F(DBTest, GetOrderedByLevels) {
712 do {
713 ASSERT_LEVELDB_OK(Put("foo", "v1"));
714 Compact("a", "z");
715 ASSERT_EQ("v1", Get("foo"));
716 ASSERT_LEVELDB_OK(Put("foo", "v2"));
717 ASSERT_EQ("v2", Get("foo"));
718 dbfull()->TEST_CompactMemTable();
719 ASSERT_EQ("v2", Get("foo"));
720 } while (ChangeOptions());
721}
722
723TEST_F(DBTest, GetPicksCorrectFile) {
724 do {
725 // Arrange to have multiple files in a non-level-0 level.
726 ASSERT_LEVELDB_OK(Put("a", "va"));
727 Compact("a", "b");
728 ASSERT_LEVELDB_OK(Put("x", "vx"));
729 Compact("x", "y");
730 ASSERT_LEVELDB_OK(Put("f", "vf"));
731 Compact("f", "g");
732 ASSERT_EQ("va", Get("a"));
733 ASSERT_EQ("vf", Get("f"));
734 ASSERT_EQ("vx", Get("x"));
735 } while (ChangeOptions());
736}
737
738TEST_F(DBTest, GetEncountersEmptyLevel) {
739 do {
740 // Arrange for the following to happen:
741 // * sstable A in level 0
742 // * nothing in level 1
743 // * sstable B in level 2
744 // Then do enough Get() calls to arrange for an automatic compaction
745 // of sstable A. A bug would cause the compaction to be marked as
746 // occurring at level 1 (instead of the correct level 0).
747
748 // Step 1: First place sstables in levels 0 and 2
749 int compaction_count = 0;
750 while (NumTableFilesAtLevel(0) == 0 || NumTableFilesAtLevel(2) == 0) {
751 ASSERT_LE(compaction_count, 100) << "could not fill levels 0 and 2";
752 compaction_count++;
753 Put("a", "begin");
754 Put("z", "end");
755 dbfull()->TEST_CompactMemTable();
756 }
757
758 // Step 2: clear level 1 if necessary.
759 dbfull()->TEST_CompactRange(1, nullptr, nullptr);
760 ASSERT_EQ(NumTableFilesAtLevel(0), 1);
761 ASSERT_EQ(NumTableFilesAtLevel(1), 0);
762 ASSERT_EQ(NumTableFilesAtLevel(2), 1);
763
764 // Step 3: read a bunch of times
765 for (int i = 0; i < 1000; i++) {
766 ASSERT_EQ("NOT_FOUND", Get("missing"));
767 }
768
769 // Step 4: Wait for compaction to finish
770 DelayMilliseconds(1000);
771
772 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
773 } while (ChangeOptions());
774}
775
776TEST_F(DBTest, IterEmpty) {
777 Iterator* iter = db_->NewIterator(ReadOptions());
778
779 iter->SeekToFirst();
780 ASSERT_EQ(IterStatus(iter), "(invalid)");
781
782 iter->SeekToLast();
783 ASSERT_EQ(IterStatus(iter), "(invalid)");
784
785 iter->Seek("foo");
786 ASSERT_EQ(IterStatus(iter), "(invalid)");
787
788 delete iter;
789}
790
791TEST_F(DBTest, IterSingle) {
792 ASSERT_LEVELDB_OK(Put("a", "va"));
793 Iterator* iter = db_->NewIterator(ReadOptions());
794
795 iter->SeekToFirst();
796 ASSERT_EQ(IterStatus(iter), "a->va");
797 iter->Next();
798 ASSERT_EQ(IterStatus(iter), "(invalid)");
799 iter->SeekToFirst();
800 ASSERT_EQ(IterStatus(iter), "a->va");
801 iter->Prev();
802 ASSERT_EQ(IterStatus(iter), "(invalid)");
803
804 iter->SeekToLast();
805 ASSERT_EQ(IterStatus(iter), "a->va");
806 iter->Next();
807 ASSERT_EQ(IterStatus(iter), "(invalid)");
808 iter->SeekToLast();
809 ASSERT_EQ(IterStatus(iter), "a->va");
810 iter->Prev();
811 ASSERT_EQ(IterStatus(iter), "(invalid)");
812
813 iter->Seek("");
814 ASSERT_EQ(IterStatus(iter), "a->va");
815 iter->Next();
816 ASSERT_EQ(IterStatus(iter), "(invalid)");
817
818 iter->Seek("a");
819 ASSERT_EQ(IterStatus(iter), "a->va");
820 iter->Next();
821 ASSERT_EQ(IterStatus(iter), "(invalid)");
822
823 iter->Seek("b");
824 ASSERT_EQ(IterStatus(iter), "(invalid)");
825
826 delete iter;
827}
828
829TEST_F(DBTest, IterMulti) {
830 ASSERT_LEVELDB_OK(Put("a", "va"));
831 ASSERT_LEVELDB_OK(Put("b", "vb"));
832 ASSERT_LEVELDB_OK(Put("c", "vc"));
833 Iterator* iter = db_->NewIterator(ReadOptions());
834
835 iter->SeekToFirst();
836 ASSERT_EQ(IterStatus(iter), "a->va");
837 iter->Next();
838 ASSERT_EQ(IterStatus(iter), "b->vb");
839 iter->Next();
840 ASSERT_EQ(IterStatus(iter), "c->vc");
841 iter->Next();
842 ASSERT_EQ(IterStatus(iter), "(invalid)");
843 iter->SeekToFirst();
844 ASSERT_EQ(IterStatus(iter), "a->va");
845 iter->Prev();
846 ASSERT_EQ(IterStatus(iter), "(invalid)");
847
848 iter->SeekToLast();
849 ASSERT_EQ(IterStatus(iter), "c->vc");
850 iter->Prev();
851 ASSERT_EQ(IterStatus(iter), "b->vb");
852 iter->Prev();
853 ASSERT_EQ(IterStatus(iter), "a->va");
854 iter->Prev();
855 ASSERT_EQ(IterStatus(iter), "(invalid)");
856 iter->SeekToLast();
857 ASSERT_EQ(IterStatus(iter), "c->vc");
858 iter->Next();
859 ASSERT_EQ(IterStatus(iter), "(invalid)");
860
861 iter->Seek("");
862 ASSERT_EQ(IterStatus(iter), "a->va");
863 iter->Seek("a");
864 ASSERT_EQ(IterStatus(iter), "a->va");
865 iter->Seek("ax");
866 ASSERT_EQ(IterStatus(iter), "b->vb");
867 iter->Seek("b");
868 ASSERT_EQ(IterStatus(iter), "b->vb");
869 iter->Seek("z");
870 ASSERT_EQ(IterStatus(iter), "(invalid)");
871
872 // Switch from reverse to forward
873 iter->SeekToLast();
874 iter->Prev();
875 iter->Prev();
876 iter->Next();
877 ASSERT_EQ(IterStatus(iter), "b->vb");
878
879 // Switch from forward to reverse
880 iter->SeekToFirst();
881 iter->Next();
882 iter->Next();
883 iter->Prev();
884 ASSERT_EQ(IterStatus(iter), "b->vb");
885
886 // Make sure iter stays at snapshot
887 ASSERT_LEVELDB_OK(Put("a", "va2"));
888 ASSERT_LEVELDB_OK(Put("a2", "va3"));
889 ASSERT_LEVELDB_OK(Put("b", "vb2"));
890 ASSERT_LEVELDB_OK(Put("c", "vc2"));
891 ASSERT_LEVELDB_OK(Delete("b"));
892 iter->SeekToFirst();
893 ASSERT_EQ(IterStatus(iter), "a->va");
894 iter->Next();
895 ASSERT_EQ(IterStatus(iter), "b->vb");
896 iter->Next();
897 ASSERT_EQ(IterStatus(iter), "c->vc");
898 iter->Next();
899 ASSERT_EQ(IterStatus(iter), "(invalid)");
900 iter->SeekToLast();
901 ASSERT_EQ(IterStatus(iter), "c->vc");
902 iter->Prev();
903 ASSERT_EQ(IterStatus(iter), "b->vb");
904 iter->Prev();
905 ASSERT_EQ(IterStatus(iter), "a->va");
906 iter->Prev();
907 ASSERT_EQ(IterStatus(iter), "(invalid)");
908
909 delete iter;
910}
911
912TEST_F(DBTest, IterSmallAndLargeMix) {
913 ASSERT_LEVELDB_OK(Put("a", "va"));
914 ASSERT_LEVELDB_OK(Put("b", std::string(100000, 'b')));
915 ASSERT_LEVELDB_OK(Put("c", "vc"));
916 ASSERT_LEVELDB_OK(Put("d", std::string(100000, 'd')));
917 ASSERT_LEVELDB_OK(Put("e", std::string(100000, 'e')));
918
919 Iterator* iter = db_->NewIterator(ReadOptions());
920
921 iter->SeekToFirst();
922 ASSERT_EQ(IterStatus(iter), "a->va");
923 iter->Next();
924 ASSERT_EQ(IterStatus(iter), "b->" + std::string(100000, 'b'));
925 iter->Next();
926 ASSERT_EQ(IterStatus(iter), "c->vc");
927 iter->Next();
928 ASSERT_EQ(IterStatus(iter), "d->" + std::string(100000, 'd'));
929 iter->Next();
930 ASSERT_EQ(IterStatus(iter), "e->" + std::string(100000, 'e'));
931 iter->Next();
932 ASSERT_EQ(IterStatus(iter), "(invalid)");
933
934 iter->SeekToLast();
935 ASSERT_EQ(IterStatus(iter), "e->" + std::string(100000, 'e'));
936 iter->Prev();
937 ASSERT_EQ(IterStatus(iter), "d->" + std::string(100000, 'd'));
938 iter->Prev();
939 ASSERT_EQ(IterStatus(iter), "c->vc");
940 iter->Prev();
941 ASSERT_EQ(IterStatus(iter), "b->" + std::string(100000, 'b'));
942 iter->Prev();
943 ASSERT_EQ(IterStatus(iter), "a->va");
944 iter->Prev();
945 ASSERT_EQ(IterStatus(iter), "(invalid)");
946
947 delete iter;
948}
949
950TEST_F(DBTest, IterMultiWithDelete) {
951 do {
952 ASSERT_LEVELDB_OK(Put("a", "va"));
953 ASSERT_LEVELDB_OK(Put("b", "vb"));
954 ASSERT_LEVELDB_OK(Put("c", "vc"));
955 ASSERT_LEVELDB_OK(Delete("b"));
956 ASSERT_EQ("NOT_FOUND", Get("b"));
957
958 Iterator* iter = db_->NewIterator(ReadOptions());
959 iter->Seek("c");
960 ASSERT_EQ(IterStatus(iter), "c->vc");
961 iter->Prev();
962 ASSERT_EQ(IterStatus(iter), "a->va");
963 delete iter;
964 } while (ChangeOptions());
965}
966
967TEST_F(DBTest, IterMultiWithDeleteAndCompaction) {
968 do {
969 ASSERT_LEVELDB_OK(Put("b", "vb"));
970 ASSERT_LEVELDB_OK(Put("c", "vc"));
971 ASSERT_LEVELDB_OK(Put("a", "va"));
972 dbfull()->TEST_CompactMemTable();
973 ASSERT_LEVELDB_OK(Delete("b"));
974 ASSERT_EQ("NOT_FOUND", Get("b"));
975
976 Iterator* iter = db_->NewIterator(ReadOptions());
977 iter->Seek("c");
978 ASSERT_EQ(IterStatus(iter), "c->vc");
979 iter->Prev();
980 ASSERT_EQ(IterStatus(iter), "a->va");
981 iter->Seek("b");
982 ASSERT_EQ(IterStatus(iter), "c->vc");
983 delete iter;
984 } while (ChangeOptions());
985}
986
987TEST_F(DBTest, Recover) {
988 do {
989 ASSERT_LEVELDB_OK(Put("foo", "v1"));
990 ASSERT_LEVELDB_OK(Put("baz", "v5"));
991
992 Reopen();
993 ASSERT_EQ("v1", Get("foo"));
994
995 ASSERT_EQ("v1", Get("foo"));
996 ASSERT_EQ("v5", Get("baz"));
997 ASSERT_LEVELDB_OK(Put("bar", "v2"));
998 ASSERT_LEVELDB_OK(Put("foo", "v3"));
999
1000 Reopen();
1001 ASSERT_EQ("v3", Get("foo"));
1002 ASSERT_LEVELDB_OK(Put("foo", "v4"));
1003 ASSERT_EQ("v4", Get("foo"));
1004 ASSERT_EQ("v2", Get("bar"));
1005 ASSERT_EQ("v5", Get("baz"));
1006 } while (ChangeOptions());
1007}
1008
1009TEST_F(DBTest, RecoveryWithEmptyLog) {
1010 do {
1011 ASSERT_LEVELDB_OK(Put("foo", "v1"));
1012 ASSERT_LEVELDB_OK(Put("foo", "v2"));
1013 Reopen();
1014 Reopen();
1015 ASSERT_LEVELDB_OK(Put("foo", "v3"));
1016 Reopen();
1017 ASSERT_EQ("v3", Get("foo"));
1018 } while (ChangeOptions());
1019}
1020
1021// Check that writes done during a memtable compaction are recovered
1022// if the database is shutdown during the memtable compaction.
1023TEST_F(DBTest, RecoverDuringMemtableCompaction) {
1024 do {
1025 Options options = CurrentOptions();
1026 options.env = env_;
1027 options.write_buffer_size = 1000000;
1028 Reopen(&options);
1029
1030 // Trigger a long memtable compaction and reopen the database during it
1031 ASSERT_LEVELDB_OK(Put("foo", "v1")); // Goes to 1st log file
1032 ASSERT_LEVELDB_OK(
1033 Put("big1", std::string(10000000, 'x'))); // Fills memtable
1034 ASSERT_LEVELDB_OK(
1035 Put("big2", std::string(1000, 'y'))); // Triggers compaction
1036 ASSERT_LEVELDB_OK(Put("bar", "v2")); // Goes to new log file
1037
1038 Reopen(&options);
1039 ASSERT_EQ("v1", Get("foo"));
1040 ASSERT_EQ("v2", Get("bar"));
1041 ASSERT_EQ(std::string(10000000, 'x'), Get("big1"));
1042 ASSERT_EQ(std::string(1000, 'y'), Get("big2"));
1043 } while (ChangeOptions());
1044}
1045
1046static std::string Key(int i) {
1047 char buf[100];
1048 std::snprintf(buf, sizeof(buf), "key%06d", i);
1049 return std::string(buf);
1050}
1051
1052TEST_F(DBTest, MinorCompactionsHappen) {
1053 Options options = CurrentOptions();
1054 options.write_buffer_size = 10000;
1055 Reopen(&options);
1056
1057 const int N = 500;
1058
1059 int starting_num_tables = TotalTableFiles();
1060 for (int i = 0; i < N; i++) {
1061 ASSERT_LEVELDB_OK(Put(Key(i), Key(i) + std::string(1000, 'v')));
1062 }
1063 int ending_num_tables = TotalTableFiles();
1064 ASSERT_GT(ending_num_tables, starting_num_tables);
1065
1066 for (int i = 0; i < N; i++) {
1067 ASSERT_EQ(Key(i) + std::string(1000, 'v'), Get(Key(i)));
1068 }
1069
1070 Reopen();
1071
1072 for (int i = 0; i < N; i++) {
1073 ASSERT_EQ(Key(i) + std::string(1000, 'v'), Get(Key(i)));
1074 }
1075}
1076
1077TEST_F(DBTest, RecoverWithLargeLog) {
1078 {
1079 Options options = CurrentOptions();
1080 Reopen(&options);
1081 ASSERT_LEVELDB_OK(Put("big1", std::string(200000, '1')));
1082 ASSERT_LEVELDB_OK(Put("big2", std::string(200000, '2')));
1083 ASSERT_LEVELDB_OK(Put("small3", std::string(10, '3')));
1084 ASSERT_LEVELDB_OK(Put("small4", std::string(10, '4')));
1085 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1086 }
1087
1088 // Make sure that if we re-open with a small write buffer size that
1089 // we flush table files in the middle of a large log file.
1090 Options options = CurrentOptions();
1091 options.write_buffer_size = 100000;
1092 Reopen(&options);
1093 ASSERT_EQ(NumTableFilesAtLevel(0), 3);
1094 ASSERT_EQ(std::string(200000, '1'), Get("big1"));
1095 ASSERT_EQ(std::string(200000, '2'), Get("big2"));
1096 ASSERT_EQ(std::string(10, '3'), Get("small3"));
1097 ASSERT_EQ(std::string(10, '4'), Get("small4"));
1098 ASSERT_GT(NumTableFilesAtLevel(0), 1);
1099}
1100
1101TEST_F(DBTest, CompactionsGenerateMultipleFiles) {
1102 Options options = CurrentOptions();
1103 options.write_buffer_size = 100000000; // Large write buffer
1104 Reopen(&options);
1105
1106 Random rnd(301);
1107
1108 // Write 8MB (80 values, each 100K)
1109 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1110 std::vector<std::string> values;
1111 for (int i = 0; i < 80; i++) {
1112 values.push_back(RandomString(&rnd, 100000));
1113 ASSERT_LEVELDB_OK(Put(Key(i), values[i]));
1114 }
1115
1116 // Reopening moves updates to level-0
1117 Reopen(&options);
1118 dbfull()->TEST_CompactRange(0, nullptr, nullptr);
1119
1120 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1121 ASSERT_GT(NumTableFilesAtLevel(1), 1);
1122 for (int i = 0; i < 80; i++) {
1123 ASSERT_EQ(Get(Key(i)), values[i]);
1124 }
1125}
1126
1127TEST_F(DBTest, RepeatedWritesToSameKey) {
1128 Options options = CurrentOptions();
1129 options.env = env_;
1130 options.write_buffer_size = 100000; // Small write buffer
1131 Reopen(&options);
1132
1133 // We must have at most one file per level except for level-0,
1134 // which may have up to kL0_StopWritesTrigger files.
1135 const int kMaxFiles = config::kNumLevels + config::kL0_StopWritesTrigger;
1136
1137 Random rnd(301);
1138 std::string value = RandomString(&rnd, 2 * options.write_buffer_size);
1139 for (int i = 0; i < 5 * kMaxFiles; i++) {
1140 Put("key", value);
1141 ASSERT_LE(TotalTableFiles(), kMaxFiles);
1142 std::fprintf(stderr, "after %d: %d files\n", i + 1, TotalTableFiles());
1143 }
1144}
1145
1146TEST_F(DBTest, SparseMerge) {
1147 Options options = CurrentOptions();
1148 options.compression = kNoCompression;
1149 Reopen(&options);
1150
1151 FillLevels("A", "Z");
1152
1153 // Suppose there is:
1154 // small amount of data with prefix A
1155 // large amount of data with prefix B
1156 // small amount of data with prefix C
1157 // and that recent updates have made small changes to all three prefixes.
1158 // Check that we do not do a compaction that merges all of B in one shot.
1159 const std::string value(1000, 'x');
1160 Put("A", "va");
1161 // Write approximately 100MB of "B" values
1162 for (int i = 0; i < 100000; i++) {
1163 char key[100];
1164 std::snprintf(key, sizeof(key), "B%010d", i);
1165 Put(key, value);
1166 }
1167 Put("C", "vc");
1168 dbfull()->TEST_CompactMemTable();
1169 dbfull()->TEST_CompactRange(0, nullptr, nullptr);
1170
1171 // Make sparse update
1172 Put("A", "va2");
1173 Put("B100", "bvalue2");
1174 Put("C", "vc2");
1175 dbfull()->TEST_CompactMemTable();
1176
1177 // Compactions should not cause us to create a situation where
1178 // a file overlaps too much data at the next level.
1179 ASSERT_LE(dbfull()->TEST_MaxNextLevelOverlappingBytes(), 20 * 1048576);
1180 dbfull()->TEST_CompactRange(0, nullptr, nullptr);
1181 ASSERT_LE(dbfull()->TEST_MaxNextLevelOverlappingBytes(), 20 * 1048576);
1182 dbfull()->TEST_CompactRange(1, nullptr, nullptr);
1183 ASSERT_LE(dbfull()->TEST_MaxNextLevelOverlappingBytes(), 20 * 1048576);
1184}
1185
1186static bool Between(uint64_t val, uint64_t low, uint64_t high) {
1187 bool result = (val >= low) && (val <= high);
1188 if (!result) {
1189 std::fprintf(stderr, "Value %llu is not in range [%llu, %llu]\n",
1190 (unsigned long long)(val), (unsigned long long)(low),
1191 (unsigned long long)(high));
1192 }
1193 return result;
1194}
1195
1196TEST_F(DBTest, ApproximateSizes) {
1197 do {
1198 Options options = CurrentOptions();
1199 options.write_buffer_size = 100000000; // Large write buffer
1200 options.compression = kNoCompression;
1201 DestroyAndReopen();
1202
1203 ASSERT_TRUE(Between(Size("", "xyz"), 0, 0));
1204 Reopen(&options);
1205 ASSERT_TRUE(Between(Size("", "xyz"), 0, 0));
1206
1207 // Write 8MB (80 values, each 100K)
1208 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1209 const int N = 80;
1210 static const int S1 = 100000;
1211 static const int S2 = 105000; // Allow some expansion from metadata
1212 Random rnd(301);
1213 for (int i = 0; i < N; i++) {
1214 ASSERT_LEVELDB_OK(Put(Key(i), RandomString(&rnd, S1)));
1215 }
1216
1217 // 0 because GetApproximateSizes() does not account for memtable space
1218 ASSERT_TRUE(Between(Size("", Key(50)), 0, 0));
1219
1220 if (options.reuse_logs) {
1221 // Recovery will reuse memtable, and GetApproximateSizes() does not
1222 // account for memtable usage;
1223 Reopen(&options);
1224 ASSERT_TRUE(Between(Size("", Key(50)), 0, 0));
1225 continue;
1226 }
1227
1228 // Check sizes across recovery by reopening a few times
1229 for (int run = 0; run < 3; run++) {
1230 Reopen(&options);
1231
1232 for (int compact_start = 0; compact_start < N; compact_start += 10) {
1233 for (int i = 0; i < N; i += 10) {
1234 ASSERT_TRUE(Between(Size("", Key(i)), S1 * i, S2 * i));
1235 ASSERT_TRUE(Between(Size("", Key(i) + ".suffix"), S1 * (i + 1),
1236 S2 * (i + 1)));
1237 ASSERT_TRUE(Between(Size(Key(i), Key(i + 10)), S1 * 10, S2 * 10));
1238 }
1239 ASSERT_TRUE(Between(Size("", Key(50)), S1 * 50, S2 * 50));
1240 ASSERT_TRUE(Between(Size("", Key(50) + ".suffix"), S1 * 50, S2 * 50));
1241
1242 std::string cstart_str = Key(compact_start);
1243 std::string cend_str = Key(compact_start + 9);
1244 Slice cstart = cstart_str;
1245 Slice cend = cend_str;
1246 dbfull()->TEST_CompactRange(0, &cstart, &cend);
1247 }
1248
1249 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1250 ASSERT_GT(NumTableFilesAtLevel(1), 0);
1251 }
1252 } while (ChangeOptions());
1253}
1254
1255TEST_F(DBTest, ApproximateSizes_MixOfSmallAndLarge) {
1256 do {
1257 Options options = CurrentOptions();
1258 options.compression = kNoCompression;
1259 Reopen();
1260
1261 Random rnd(301);
1262 std::string big1 = RandomString(&rnd, 100000);
1263 ASSERT_LEVELDB_OK(Put(Key(0), RandomString(&rnd, 10000)));
1264 ASSERT_LEVELDB_OK(Put(Key(1), RandomString(&rnd, 10000)));
1265 ASSERT_LEVELDB_OK(Put(Key(2), big1));
1266 ASSERT_LEVELDB_OK(Put(Key(3), RandomString(&rnd, 10000)));
1267 ASSERT_LEVELDB_OK(Put(Key(4), big1));
1268 ASSERT_LEVELDB_OK(Put(Key(5), RandomString(&rnd, 10000)));
1269 ASSERT_LEVELDB_OK(Put(Key(6), RandomString(&rnd, 300000)));
1270 ASSERT_LEVELDB_OK(Put(Key(7), RandomString(&rnd, 10000)));
1271
1272 if (options.reuse_logs) {
1273 // Need to force a memtable compaction since recovery does not do so.
1274 ASSERT_LEVELDB_OK(dbfull()->TEST_CompactMemTable());
1275 }
1276
1277 // Check sizes across recovery by reopening a few times
1278 for (int run = 0; run < 3; run++) {
1279 Reopen(&options);
1280
1281 ASSERT_TRUE(Between(Size("", Key(0)), 0, 0));
1282 ASSERT_TRUE(Between(Size("", Key(1)), 10000, 11000));
1283 ASSERT_TRUE(Between(Size("", Key(2)), 20000, 21000));
1284 ASSERT_TRUE(Between(Size("", Key(3)), 120000, 121000));
1285 ASSERT_TRUE(Between(Size("", Key(4)), 130000, 131000));
1286 ASSERT_TRUE(Between(Size("", Key(5)), 230000, 231000));
1287 ASSERT_TRUE(Between(Size("", Key(6)), 240000, 241000));
1288 ASSERT_TRUE(Between(Size("", Key(7)), 540000, 541000));
1289 ASSERT_TRUE(Between(Size("", Key(8)), 550000, 560000));
1290
1291 ASSERT_TRUE(Between(Size(Key(3), Key(5)), 110000, 111000));
1292
1293 dbfull()->TEST_CompactRange(0, nullptr, nullptr);
1294 }
1295 } while (ChangeOptions());
1296}
1297
1298TEST_F(DBTest, IteratorPinsRef) {
1299 Put("foo", "hello");
1300
1301 // Get iterator that will yield the current contents of the DB.
1302 Iterator* iter = db_->NewIterator(ReadOptions());
1303
1304 // Write to force compactions
1305 Put("foo", "newvalue1");
1306 for (int i = 0; i < 100; i++) {
1307 ASSERT_LEVELDB_OK(
1308 Put(Key(i), Key(i) + std::string(100000, 'v'))); // 100K values
1309 }
1310 Put("foo", "newvalue2");
1311
1312 iter->SeekToFirst();
1313 ASSERT_TRUE(iter->Valid());
1314 ASSERT_EQ("foo", iter->key().ToString());
1315 ASSERT_EQ("hello", iter->value().ToString());
1316 iter->Next();
1317 ASSERT_TRUE(!iter->Valid());
1318 delete iter;
1319}
1320
1321TEST_F(DBTest, Snapshot) {
1322 do {
1323 Put("foo", "v1");
1324 const Snapshot* s1 = db_->GetSnapshot();
1325 Put("foo", "v2");
1326 const Snapshot* s2 = db_->GetSnapshot();
1327 Put("foo", "v3");
1328 const Snapshot* s3 = db_->GetSnapshot();
1329
1330 Put("foo", "v4");
1331 ASSERT_EQ("v1", Get("foo", s1));
1332 ASSERT_EQ("v2", Get("foo", s2));
1333 ASSERT_EQ("v3", Get("foo", s3));
1334 ASSERT_EQ("v4", Get("foo"));
1335
1336 db_->ReleaseSnapshot(s3);
1337 ASSERT_EQ("v1", Get("foo", s1));
1338 ASSERT_EQ("v2", Get("foo", s2));
1339 ASSERT_EQ("v4", Get("foo"));
1340
1341 db_->ReleaseSnapshot(s1);
1342 ASSERT_EQ("v2", Get("foo", s2));
1343 ASSERT_EQ("v4", Get("foo"));
1344
1345 db_->ReleaseSnapshot(s2);
1346 ASSERT_EQ("v4", Get("foo"));
1347 } while (ChangeOptions());
1348}
1349
1350TEST_F(DBTest, HiddenValuesAreRemoved) {
1351 do {
1352 Random rnd(301);
1353 FillLevels("a", "z");
1354
1355 std::string big = RandomString(&rnd, 50000);
1356 Put("foo", big);
1357 Put("pastfoo", "v");
1358 const Snapshot* snapshot = db_->GetSnapshot();
1359 Put("foo", "tiny");
1360 Put("pastfoo2", "v2"); // Advance sequence number one more
1361
1362 ASSERT_LEVELDB_OK(dbfull()->TEST_CompactMemTable());
1363 ASSERT_GT(NumTableFilesAtLevel(0), 0);
1364
1365 ASSERT_EQ(big, Get("foo", snapshot));
1366 ASSERT_TRUE(Between(Size("", "pastfoo"), 50000, 60000));
1367 db_->ReleaseSnapshot(snapshot);
1368 ASSERT_EQ(AllEntriesFor("foo"), "[ tiny, " + big + " ]");
1369 Slice x("x");
1370 dbfull()->TEST_CompactRange(0, nullptr, &x);
1371 ASSERT_EQ(AllEntriesFor("foo"), "[ tiny ]");
1372 ASSERT_EQ(NumTableFilesAtLevel(0), 0);
1373 ASSERT_GE(NumTableFilesAtLevel(1), 1);
1374 dbfull()->TEST_CompactRange(1, nullptr, &x);
1375 ASSERT_EQ(AllEntriesFor("foo"), "[ tiny ]");
1376
1377 ASSERT_TRUE(Between(Size("", "pastfoo"), 0, 1000));
1378 } while (ChangeOptions());
1379}
1380
1381TEST_F(DBTest, DeletionMarkers1) {
1382 Put("foo", "v1");
1383 ASSERT_LEVELDB_OK(dbfull()->TEST_CompactMemTable());
1384 const int last = config::kMaxMemCompactLevel;
1385 ASSERT_EQ(NumTableFilesAtLevel(last), 1); // foo => v1 is now in last level
1386
1387 // Place a table at level last-1 to prevent merging with preceding mutation
1388 Put("a", "begin");
1389 Put("z", "end");
1390 dbfull()->TEST_CompactMemTable();
1391 ASSERT_EQ(NumTableFilesAtLevel(last), 1);
1392 ASSERT_EQ(NumTableFilesAtLevel(last - 1), 1);
1393
1394 Delete("foo");
1395 Put("foo", "v2");
1396 ASSERT_EQ(AllEntriesFor("foo"), "[ v2, DEL, v1 ]");
1397 ASSERT_LEVELDB_OK(dbfull()->TEST_CompactMemTable()); // Moves to level last-2
1398 ASSERT_EQ(AllEntriesFor("foo"), "[ v2, DEL, v1 ]");
1399 Slice z("z");
1400 dbfull()->TEST_CompactRange(last - 2, nullptr, &z);
1401 // DEL eliminated, but v1 remains because we aren't compacting that level
1402 // (DEL can be eliminated because v2 hides v1).
1403 ASSERT_EQ(AllEntriesFor("foo"), "[ v2, v1 ]");
1404 dbfull()->TEST_CompactRange(last - 1, nullptr, nullptr);
1405 // Merging last-1 w/ last, so we are the base level for "foo", so
1406 // DEL is removed. (as is v1).
1407 ASSERT_EQ(AllEntriesFor("foo"), "[ v2 ]");
1408}
1409
1410TEST_F(DBTest, DeletionMarkers2) {
1411 Put("foo", "v1");
1412 ASSERT_LEVELDB_OK(dbfull()->TEST_CompactMemTable());
1413 const int last = config::kMaxMemCompactLevel;
1414 ASSERT_EQ(NumTableFilesAtLevel(last), 1); // foo => v1 is now in last level
1415
1416 // Place a table at level last-1 to prevent merging with preceding mutation
1417 Put("a", "begin");
1418 Put("z", "end");
1419 dbfull()->TEST_CompactMemTable();
1420 ASSERT_EQ(NumTableFilesAtLevel(last), 1);
1421 ASSERT_EQ(NumTableFilesAtLevel(last - 1), 1);
1422
1423 Delete("foo");
1424 ASSERT_EQ(AllEntriesFor("foo"), "[ DEL, v1 ]");
1425 ASSERT_LEVELDB_OK(dbfull()->TEST_CompactMemTable()); // Moves to level last-2
1426 ASSERT_EQ(AllEntriesFor("foo"), "[ DEL, v1 ]");
1427 dbfull()->TEST_CompactRange(last - 2, nullptr, nullptr);
1428 // DEL kept: "last" file overlaps
1429 ASSERT_EQ(AllEntriesFor("foo"), "[ DEL, v1 ]");
1430 dbfull()->TEST_CompactRange(last - 1, nullptr, nullptr);
1431 // Merging last-1 w/ last, so we are the base level for "foo", so
1432 // DEL is removed. (as is v1).
1433 ASSERT_EQ(AllEntriesFor("foo"), "[ ]");
1434}
1435
1436TEST_F(DBTest, OverlapInLevel0) {
1437 do {
1438 ASSERT_EQ(config::kMaxMemCompactLevel, 2) << "Fix test to match config";
1439
1440 // Fill levels 1 and 2 to disable the pushing of new memtables to levels >
1441 // 0.
1442 ASSERT_LEVELDB_OK(Put("100", "v100"));
1443 ASSERT_LEVELDB_OK(Put("999", "v999"));
1444 dbfull()->TEST_CompactMemTable();
1445 ASSERT_LEVELDB_OK(Delete("100"));
1446 ASSERT_LEVELDB_OK(Delete("999"));
1447 dbfull()->TEST_CompactMemTable();
1448 ASSERT_EQ("0,1,1", FilesPerLevel());
1449
1450 // Make files spanning the following ranges in level-0:
1451 // files[0] 200 .. 900
1452 // files[1] 300 .. 500
1453 // Note that files are sorted by smallest key.
1454 ASSERT_LEVELDB_OK(Put("300", "v300"));
1455 ASSERT_LEVELDB_OK(Put("500", "v500"));
1456 dbfull()->TEST_CompactMemTable();
1457 ASSERT_LEVELDB_OK(Put("200", "v200"));
1458 ASSERT_LEVELDB_OK(Put("600", "v600"));
1459 ASSERT_LEVELDB_OK(Put("900", "v900"));
1460 dbfull()->TEST_CompactMemTable();
1461 ASSERT_EQ("2,1,1", FilesPerLevel());
1462
1463 // Compact away the placeholder files we created initially
1464 dbfull()->TEST_CompactRange(1, nullptr, nullptr);
1465 dbfull()->TEST_CompactRange(2, nullptr, nullptr);
1466 ASSERT_EQ("2", FilesPerLevel());
1467
1468 // Do a memtable compaction. Before bug-fix, the compaction would
1469 // not detect the overlap with level-0 files and would incorrectly place
1470 // the deletion in a deeper level.
1471 ASSERT_LEVELDB_OK(Delete("600"));
1472 dbfull()->TEST_CompactMemTable();
1473 ASSERT_EQ("3", FilesPerLevel());
1474 ASSERT_EQ("NOT_FOUND", Get("600"));
1475 } while (ChangeOptions());
1476}
1477
1478TEST_F(DBTest, L0_CompactionBug_Issue44_a) {
1479 Reopen();
1480 ASSERT_LEVELDB_OK(Put("b", "v"));
1481 Reopen();
1482 ASSERT_LEVELDB_OK(Delete("b"));
1483 ASSERT_LEVELDB_OK(Delete("a"));
1484 Reopen();
1485 ASSERT_LEVELDB_OK(Delete("a"));
1486 Reopen();
1487 ASSERT_LEVELDB_OK(Put("a", "v"));
1488 Reopen();
1489 Reopen();
1490 ASSERT_EQ("(a->v)", Contents());
1491 DelayMilliseconds(1000); // Wait for compaction to finish
1492 ASSERT_EQ("(a->v)", Contents());
1493}
1494
1495TEST_F(DBTest, L0_CompactionBug_Issue44_b) {
1496 Reopen();
1497 Put("", "");
1498 Reopen();
1499 Delete("e");
1500 Put("", "");
1501 Reopen();
1502 Put("c", "cv");
1503 Reopen();
1504 Put("", "");
1505 Reopen();
1506 Put("", "");
1507 DelayMilliseconds(1000); // Wait for compaction to finish
1508 Reopen();
1509 Put("d", "dv");
1510 Reopen();
1511 Put("", "");
1512 Reopen();
1513 Delete("d");
1514 Delete("b");
1515 Reopen();
1516 ASSERT_EQ("(->)(c->cv)", Contents());
1517 DelayMilliseconds(1000); // Wait for compaction to finish
1518 ASSERT_EQ("(->)(c->cv)", Contents());
1519}
1520
1521TEST_F(DBTest, Fflush_Issue474) {
1522 static const int kNum = 100000;
1523 Random rnd(test::RandomSeed());
1524 for (int i = 0; i < kNum; i++) {
1525 std::fflush(nullptr);
1526 ASSERT_LEVELDB_OK(Put(RandomKey(&rnd), RandomString(&rnd, 100)));
1527 }
1528}
1529
1530TEST_F(DBTest, ComparatorCheck) {
1531 class NewComparator : public Comparator {
1532 public:
1533 const char* Name() const override { return "leveldb.NewComparator"; }
1534 int Compare(const Slice& a, const Slice& b) const override {
1535 return BytewiseComparator()->Compare(a, b);
1536 }
1537 void FindShortestSeparator(std::string* s, const Slice& l) const override {
1538 BytewiseComparator()->FindShortestSeparator(s, l);
1539 }
1540 void FindShortSuccessor(std::string* key) const override {
1541 BytewiseComparator()->FindShortSuccessor(key);
1542 }
1543 };
1544 NewComparator cmp;
1545 Options new_options = CurrentOptions();
1546 new_options.comparator = &cmp;
1547 Status s = TryReopen(&new_options);
1548 ASSERT_TRUE(!s.ok());
1549 ASSERT_TRUE(s.ToString().find("comparator") != std::string::npos)
1550 << s.ToString();
1551}
1552
1553TEST_F(DBTest, CustomComparator) {
1554 class NumberComparator : public Comparator {
1555 public:
1556 const char* Name() const override { return "test.NumberComparator"; }
1557 int Compare(const Slice& a, const Slice& b) const override {
1558 return ToNumber(a) - ToNumber(b);
1559 }
1560 void FindShortestSeparator(std::string* s, const Slice& l) const override {
1561 ToNumber(*s); // Check format
1562 ToNumber(l); // Check format
1563 }
1564 void FindShortSuccessor(std::string* key) const override {
1565 ToNumber(*key); // Check format
1566 }
1567
1568 private:
1569 static int ToNumber(const Slice& x) {
1570 // Check that there are no extra characters.
1571 EXPECT_TRUE(x.size() >= 2 && x[0] == '[' && x[x.size() - 1] == ']')
1572 << EscapeString(x);
1573 int val;
1574 char ignored;
1575 EXPECT_TRUE(sscanf(x.ToString().c_str(), "[%i]%c", &val, &ignored) == 1)
1576 << EscapeString(x);
1577 return val;
1578 }
1579 };
1580 NumberComparator cmp;
1581 Options new_options = CurrentOptions();
1582 new_options.create_if_missing = true;
1583 new_options.comparator = &cmp;
1584 new_options.filter_policy = nullptr; // Cannot use bloom filters
1585 new_options.write_buffer_size = 1000; // Compact more often
1586 DestroyAndReopen(&new_options);
1587 ASSERT_LEVELDB_OK(Put("[10]", "ten"));
1588 ASSERT_LEVELDB_OK(Put("[0x14]", "twenty"));
1589 for (int i = 0; i < 2; i++) {
1590 ASSERT_EQ("ten", Get("[10]"));
1591 ASSERT_EQ("ten", Get("[0xa]"));
1592 ASSERT_EQ("twenty", Get("[20]"));
1593 ASSERT_EQ("twenty", Get("[0x14]"));
1594 ASSERT_EQ("NOT_FOUND", Get("[15]"));
1595 ASSERT_EQ("NOT_FOUND", Get("[0xf]"));
1596 Compact("[0]", "[9999]");
1597 }
1598
1599 for (int run = 0; run < 2; run++) {
1600 for (int i = 0; i < 1000; i++) {
1601 char buf[100];
1602 std::snprintf(buf, sizeof(buf), "[%d]", i * 10);
1603 ASSERT_LEVELDB_OK(Put(buf, buf));
1604 }
1605 Compact("[0]", "[1000000]");
1606 }
1607}
1608
1609TEST_F(DBTest, ManualCompaction) {
1610 ASSERT_EQ(config::kMaxMemCompactLevel, 2)
1611 << "Need to update this test to match kMaxMemCompactLevel";
1612
1613 MakeTables(3, "p", "q");
1614 ASSERT_EQ("1,1,1", FilesPerLevel());
1615
1616 // Compaction range falls before files
1617 Compact("", "c");
1618 ASSERT_EQ("1,1,1", FilesPerLevel());
1619
1620 // Compaction range falls after files
1621 Compact("r", "z");
1622 ASSERT_EQ("1,1,1", FilesPerLevel());
1623
1624 // Compaction range overlaps files
1625 Compact("p1", "p9");
1626 ASSERT_EQ("0,0,1", FilesPerLevel());
1627
1628 // Populate a different range
1629 MakeTables(3, "c", "e");
1630 ASSERT_EQ("1,1,2", FilesPerLevel());
1631
1632 // Compact just the new range
1633 Compact("b", "f");
1634 ASSERT_EQ("0,0,2", FilesPerLevel());
1635
1636 // Compact all
1637 MakeTables(1, "a", "z");
1638 ASSERT_EQ("0,1,2", FilesPerLevel());
1639 db_->CompactRange(nullptr, nullptr);
1640 ASSERT_EQ("0,0,1", FilesPerLevel());
1641}
1642
1643TEST_F(DBTest, DBOpen_Options) {
1644 std::string dbname = testing::TempDir() + "db_options_test";
1645 DestroyDB(dbname, Options());
1646
1647 // Does not exist, and create_if_missing == false: error
1648 DB* db = nullptr;
1649 Options opts;
1650 opts.create_if_missing = false;
1651 Status s = DB::Open(opts, dbname, &db);
1652 ASSERT_TRUE(strstr(s.ToString().c_str(), "does not exist") != nullptr);
1653 ASSERT_TRUE(db == nullptr);
1654
1655 // Does not exist, and create_if_missing == true: OK
1656 opts.create_if_missing = true;
1657 s = DB::Open(opts, dbname, &db);
1658 ASSERT_LEVELDB_OK(s);
1659 ASSERT_TRUE(db != nullptr);
1660
1661 delete db;
1662 db = nullptr;
1663
1664 // Does exist, and error_if_exists == true: error
1665 opts.create_if_missing = false;
1666 opts.error_if_exists = true;
1667 s = DB::Open(opts, dbname, &db);
1668 ASSERT_TRUE(strstr(s.ToString().c_str(), "exists") != nullptr);
1669 ASSERT_TRUE(db == nullptr);
1670
1671 // Does exist, and error_if_exists == false: OK
1672 opts.create_if_missing = true;
1673 opts.error_if_exists = false;
1674 s = DB::Open(opts, dbname, &db);
1675 ASSERT_LEVELDB_OK(s);
1676 ASSERT_TRUE(db != nullptr);
1677
1678 delete db;
1679 db = nullptr;
1680}
1681
1682TEST_F(DBTest, DestroyEmptyDir) {
1683 std::string dbname = testing::TempDir() + "db_empty_dir";
1684 TestEnv env(Env::Default());
1685 env.RemoveDir(dbname);
1686 ASSERT_TRUE(!env.FileExists(dbname));
1687
1688 Options opts;
1689 opts.env = &env;
1690
1691 ASSERT_LEVELDB_OK(env.CreateDir(dbname));
1692 ASSERT_TRUE(env.FileExists(dbname));
1693 std::vector<std::string> children;
1694 ASSERT_LEVELDB_OK(env.GetChildren(dbname, &children));
1695 // The stock Env's do not filter out '.' and '..' special files.
1696 ASSERT_EQ(2, children.size());
1697 ASSERT_LEVELDB_OK(DestroyDB(dbname, opts));
1698 ASSERT_TRUE(!env.FileExists(dbname));
1699
1700 // Should also be destroyed if Env is filtering out dot files.
1701 env.SetIgnoreDotFiles(true);
1702 ASSERT_LEVELDB_OK(env.CreateDir(dbname));
1703 ASSERT_TRUE(env.FileExists(dbname));
1704 ASSERT_LEVELDB_OK(env.GetChildren(dbname, &children));
1705 ASSERT_EQ(0, children.size());
1706 ASSERT_LEVELDB_OK(DestroyDB(dbname, opts));
1707 ASSERT_TRUE(!env.FileExists(dbname));
1708}
1709
1710TEST_F(DBTest, DestroyOpenDB) {
1711 std::string dbname = testing::TempDir() + "open_db_dir";
1712 env_->RemoveDir(dbname);
1713 ASSERT_TRUE(!env_->FileExists(dbname));
1714
1715 Options opts;
1716 opts.create_if_missing = true;
1717 DB* db = nullptr;
1718 ASSERT_LEVELDB_OK(DB::Open(opts, dbname, &db));
1719 ASSERT_TRUE(db != nullptr);
1720
1721 // Must fail to destroy an open db.
1722 ASSERT_TRUE(env_->FileExists(dbname));
1723 ASSERT_TRUE(!DestroyDB(dbname, Options()).ok());
1724 ASSERT_TRUE(env_->FileExists(dbname));
1725
1726 delete db;
1727 db = nullptr;
1728
1729 // Should succeed destroying a closed db.
1730 ASSERT_LEVELDB_OK(DestroyDB(dbname, Options()));
1731 ASSERT_TRUE(!env_->FileExists(dbname));
1732}
1733
1734TEST_F(DBTest, Locking) {
1735 DB* db2 = nullptr;
1736 Status s = DB::Open(CurrentOptions(), dbname_, &db2);
1737 ASSERT_TRUE(!s.ok()) << "Locking did not prevent re-opening db";
1738}
1739
1740// Check that number of files does not grow when we are out of space
1741TEST_F(DBTest, NoSpace) {
1742 Options options = CurrentOptions();
1743 options.env = env_;
1744 Reopen(&options);
1745
1746 ASSERT_LEVELDB_OK(Put("foo", "v1"));
1747 ASSERT_EQ("v1", Get("foo"));
1748 Compact("a", "z");
1749 const int num_files = CountFiles();
1750 // Force out-of-space errors.
1751 env_->no_space_.store(true, std::memory_order_release);
1752 for (int i = 0; i < 10; i++) {
1753 for (int level = 0; level < config::kNumLevels - 1; level++) {
1754 dbfull()->TEST_CompactRange(level, nullptr, nullptr);
1755 }
1756 }
1757 env_->no_space_.store(false, std::memory_order_release);
1758 ASSERT_LT(CountFiles(), num_files + 3);
1759}
1760
1761TEST_F(DBTest, NonWritableFileSystem) {
1762 Options options = CurrentOptions();
1763 options.write_buffer_size = 1000;
1764 options.env = env_;
1765 Reopen(&options);
1766 ASSERT_LEVELDB_OK(Put("foo", "v1"));
1767 // Force errors for new files.
1768 env_->non_writable_.store(true, std::memory_order_release);
1769 std::string big(100000, 'x');
1770 int errors = 0;
1771 for (int i = 0; i < 20; i++) {
1772 std::fprintf(stderr, "iter %d; errors %d\n", i, errors);
1773 if (!Put("foo", big).ok()) {
1774 errors++;
1775 DelayMilliseconds(100);
1776 }
1777 }
1778 ASSERT_GT(errors, 0);
1779 env_->non_writable_.store(false, std::memory_order_release);
1780}
1781
1782TEST_F(DBTest, WriteSyncError) {
1783 // Check that log sync errors cause the DB to disallow future writes.
1784
1785 // (a) Cause log sync calls to fail
1786 Options options = CurrentOptions();
1787 options.env = env_;
1788 Reopen(&options);
1789 env_->data_sync_error_.store(true, std::memory_order_release);
1790
1791 // (b) Normal write should succeed
1792 WriteOptions w;
1793 ASSERT_LEVELDB_OK(db_->Put(w, "k1", "v1"));
1794 ASSERT_EQ("v1", Get("k1"));
1795
1796 // (c) Do a sync write; should fail
1797 w.sync = true;
1798 ASSERT_TRUE(!db_->Put(w, "k2", "v2").ok());
1799 ASSERT_EQ("v1", Get("k1"));
1800 ASSERT_EQ("NOT_FOUND", Get("k2"));
1801
1802 // (d) make sync behave normally
1803 env_->data_sync_error_.store(false, std::memory_order_release);
1804
1805 // (e) Do a non-sync write; should fail
1806 w.sync = false;
1807 ASSERT_TRUE(!db_->Put(w, "k3", "v3").ok());
1808 ASSERT_EQ("v1", Get("k1"));
1809 ASSERT_EQ("NOT_FOUND", Get("k2"));
1810 ASSERT_EQ("NOT_FOUND", Get("k3"));
1811}
1812
1813TEST_F(DBTest, ManifestWriteError) {
1814 // Test for the following problem:
1815 // (a) Compaction produces file F
1816 // (b) Log record containing F is written to MANIFEST file, but Sync() fails
1817 // (c) GC deletes F
1818 // (d) After reopening DB, reads fail since deleted F is named in log record
1819
1820 // We iterate twice. In the second iteration, everything is the
1821 // same except the log record never makes it to the MANIFEST file.
1822 for (int iter = 0; iter < 2; iter++) {
1823 std::atomic<bool>* error_type = (iter == 0) ? &env_->manifest_sync_error_
1824 : &env_->manifest_write_error_;
1825
1826 // Insert foo=>bar mapping
1827 Options options = CurrentOptions();
1828 options.env = env_;
1829 options.create_if_missing = true;
1830 options.error_if_exists = false;
1831 DestroyAndReopen(&options);
1832 ASSERT_LEVELDB_OK(Put("foo", "bar"));
1833 ASSERT_EQ("bar", Get("foo"));
1834
1835 // Memtable compaction (will succeed)
1836 dbfull()->TEST_CompactMemTable();
1837 ASSERT_EQ("bar", Get("foo"));
1838 const int last = config::kMaxMemCompactLevel;
1839 ASSERT_EQ(NumTableFilesAtLevel(last), 1); // foo=>bar is now in last level
1840
1841 // Merging compaction (will fail)
1842 error_type->store(true, std::memory_order_release);
1843 dbfull()->TEST_CompactRange(last, nullptr, nullptr); // Should fail
1844 ASSERT_EQ("bar", Get("foo"));
1845
1846 // Recovery: should not lose data
1847 error_type->store(false, std::memory_order_release);
1848 Reopen(&options);
1849 ASSERT_EQ("bar", Get("foo"));
1850 }
1851}
1852
1853TEST_F(DBTest, MissingSSTFile) {
1854 ASSERT_LEVELDB_OK(Put("foo", "bar"));
1855 ASSERT_EQ("bar", Get("foo"));
1856
1857 // Dump the memtable to disk.
1858 dbfull()->TEST_CompactMemTable();
1859 ASSERT_EQ("bar", Get("foo"));
1860
1861 Close();
1862 ASSERT_TRUE(DeleteAnSSTFile());
1863 Options options = CurrentOptions();
1864 options.paranoid_checks = true;
1865 Status s = TryReopen(&options);
1866 ASSERT_TRUE(!s.ok());
1867 ASSERT_TRUE(s.ToString().find("issing") != std::string::npos) << s.ToString();
1868}
1869
1870TEST_F(DBTest, StillReadSST) {
1871 ASSERT_LEVELDB_OK(Put("foo", "bar"));
1872 ASSERT_EQ("bar", Get("foo"));
1873
1874 // Dump the memtable to disk.
1875 dbfull()->TEST_CompactMemTable();
1876 ASSERT_EQ("bar", Get("foo"));
1877 Close();
1878 ASSERT_GT(RenameLDBToSST(), 0);
1879 Options options = CurrentOptions();
1880 options.paranoid_checks = true;
1881 Status s = TryReopen(&options);
1882 ASSERT_TRUE(s.ok());
1883 ASSERT_EQ("bar", Get("foo"));
1884}
1885
1886TEST_F(DBTest, FilesDeletedAfterCompaction) {
1887 ASSERT_LEVELDB_OK(Put("foo", "v2"));
1888 Compact("a", "z");
1889 const int num_files = CountFiles();
1890 for (int i = 0; i < 10; i++) {
1891 ASSERT_LEVELDB_OK(Put("foo", "v2"));
1892 Compact("a", "z");
1893 }
1894 ASSERT_EQ(CountFiles(), num_files);
1895}
1896
1897TEST_F(DBTest, BloomFilter) {
1898 env_->count_random_reads_ = true;
1899 Options options = CurrentOptions();
1900 options.env = env_;
1901 options.block_cache = NewLRUCache(0); // Prevent cache hits
1902 options.filter_policy = NewBloomFilterPolicy(10);
1903 Reopen(&options);
1904
1905 // Populate multiple layers
1906 const int N = 10000;
1907 for (int i = 0; i < N; i++) {
1908 ASSERT_LEVELDB_OK(Put(Key(i), Key(i)));
1909 }
1910 Compact("a", "z");
1911 for (int i = 0; i < N; i += 100) {
1912 ASSERT_LEVELDB_OK(Put(Key(i), Key(i)));
1913 }
1914 dbfull()->TEST_CompactMemTable();
1915
1916 // Prevent auto compactions triggered by seeks
1917 env_->delay_data_sync_.store(true, std::memory_order_release);
1918
1919 // Lookup present keys. Should rarely read from small sstable.
1920 env_->random_read_counter_.Reset();
1921 for (int i = 0; i < N; i++) {
1922 ASSERT_EQ(Key(i), Get(Key(i)));
1923 }
1924 int reads = env_->random_read_counter_.Read();
1925 std::fprintf(stderr, "%d present => %d reads\n", N, reads);
1926 ASSERT_GE(reads, N);
1927 ASSERT_LE(reads, N + 2 * N / 100);
1928
1929 // Lookup present keys. Should rarely read from either sstable.
1930 env_->random_read_counter_.Reset();
1931 for (int i = 0; i < N; i++) {
1932 ASSERT_EQ("NOT_FOUND", Get(Key(i) + ".missing"));
1933 }
1934 reads = env_->random_read_counter_.Read();
1935 std::fprintf(stderr, "%d missing => %d reads\n", N, reads);
1936 ASSERT_LE(reads, 3 * N / 100);
1937
1938 env_->delay_data_sync_.store(false, std::memory_order_release);
1939 Close();
1940 delete options.block_cache;
1941 delete options.filter_policy;
1942}
1943
1944// Multi-threaded test:
1945namespace {
1946
1947static const int kNumThreads = 4;
1948static const int kTestSeconds = 10;
1949static const int kNumKeys = 1000;
1950
1951struct MTState {
1952 DBTest* test;
1953 std::atomic<bool> stop;
1954 std::atomic<int> counter[kNumThreads];
1955 std::atomic<bool> thread_done[kNumThreads];
1956};
1957
1958struct MTThread {
1959 MTState* state;
1960 int id;
1961};
1962
1963static void MTThreadBody(void* arg) {
1964 MTThread* t = reinterpret_cast<MTThread*>(arg);
1965 int id = t->id;
1966 DB* db = t->state->test->db_;
1967 int counter = 0;
1968 std::fprintf(stderr, "... starting thread %d\n", id);
1969 Random rnd(1000 + id);
1970 std::string value;
1971 char valbuf[1500];
1972 while (!t->state->stop.load(std::memory_order_acquire)) {
1973 t->state->counter[id].store(counter, std::memory_order_release);
1974
1975 int key = rnd.Uniform(kNumKeys);
1976 char keybuf[20];
1977 std::snprintf(keybuf, sizeof(keybuf), "%016d", key);
1978
1979 if (rnd.OneIn(2)) {
1980 // Write values of the form <key, my id, counter>.
1981 // We add some padding for force compactions.
1982 std::snprintf(valbuf, sizeof(valbuf), "%d.%d.%-1000d", key, id,
1983 static_cast<int>(counter));
1984 ASSERT_LEVELDB_OK(db->Put(WriteOptions(), Slice(keybuf), Slice(valbuf)));
1985 } else {
1986 // Read a value and verify that it matches the pattern written above.
1987 Status s = db->Get(ReadOptions(), Slice(keybuf), &value);
1988 if (s.IsNotFound()) {
1989 // Key has not yet been written
1990 } else {
1991 // Check that the writer thread counter is >= the counter in the value
1992 ASSERT_LEVELDB_OK(s);
1993 int k, w, c;
1994 ASSERT_EQ(3, sscanf(value.c_str(), "%d.%d.%d", &k, &w, &c)) << value;
1995 ASSERT_EQ(k, key);
1996 ASSERT_GE(w, 0);
1997 ASSERT_LT(w, kNumThreads);
1998 ASSERT_LE(c, t->state->counter[w].load(std::memory_order_acquire));
1999 }
2000 }
2001 counter++;
2002 }
2003 t->state->thread_done[id].store(true, std::memory_order_release);
2004 std::fprintf(stderr, "... stopping thread %d after %d ops\n", id, counter);
2005}
2006
2007} // namespace
2008
2009TEST_F(DBTest, MultiThreaded) {
2010 do {
2011 // Initialize state
2012 MTState mt;
2013 mt.test = this;
2014 mt.stop.store(false, std::memory_order_release);
2015 for (int id = 0; id < kNumThreads; id++) {
2016 mt.counter[id].store(false, std::memory_order_release);
2017 mt.thread_done[id].store(false, std::memory_order_release);
2018 }
2019
2020 // Start threads
2021 MTThread thread[kNumThreads];
2022 for (int id = 0; id < kNumThreads; id++) {
2023 thread[id].state = &mt;
2024 thread[id].id = id;
2025 env_->StartThread(MTThreadBody, &thread[id]);
2026 }
2027
2028 // Let them run for a while
2029 DelayMilliseconds(kTestSeconds * 1000);
2030
2031 // Stop the threads and wait for them to finish
2032 mt.stop.store(true, std::memory_order_release);
2033 for (int id = 0; id < kNumThreads; id++) {
2034 while (!mt.thread_done[id].load(std::memory_order_acquire)) {
2035 DelayMilliseconds(100);
2036 }
2037 }
2038 } while (ChangeOptions());
2039}
2040
2041namespace {
2042typedef std::map<std::string, std::string> KVMap;
2043}
2044
2045class ModelDB : public DB {
2046 public:
2047 class ModelSnapshot : public Snapshot {
2048 public:
2049 KVMap map_;
2050 };
2051
2052 explicit ModelDB(const Options& options) : options_(options) {}
2053 ~ModelDB() override = default;
2054 Status Put(const WriteOptions& o, const Slice& k, const Slice& v) override {
2055 return DB::Put(o, k, v);
2056 }
2057 Status Delete(const WriteOptions& o, const Slice& key) override {
2058 return DB::Delete(o, key);
2059 }
2060 Status Get(const ReadOptions& options, const Slice& key,
2061 std::string* value) override {
2062 assert(false); // Not implemented
2063 return Status::NotFound(key);
2064 }
2065 Iterator* NewIterator(const ReadOptions& options) override {
2066 if (options.snapshot == nullptr) {
2067 KVMap* saved = new KVMap;
2068 *saved = map_;
2069 return new ModelIter(saved, true);
2070 } else {
2071 const KVMap* snapshot_state =
2072 &(reinterpret_cast<const ModelSnapshot*>(options.snapshot)->map_);
2073 return new ModelIter(snapshot_state, false);
2074 }
2075 }
2076 const Snapshot* GetSnapshot() override {
2077 ModelSnapshot* snapshot = new ModelSnapshot;
2078 snapshot->map_ = map_;
2079 return snapshot;
2080 }
2081
2082 void ReleaseSnapshot(const Snapshot* snapshot) override {
2083 delete reinterpret_cast<const ModelSnapshot*>(snapshot);
2084 }
2085 Status Write(const WriteOptions& options, WriteBatch* batch) override {
2086 class Handler : public WriteBatch::Handler {
2087 public:
2088 KVMap* map_;
2089 void Put(const Slice& key, const Slice& value) override {
2090 (*map_)[key.ToString()] = value.ToString();
2091 }
2092 void Delete(const Slice& key) override { map_->erase(key.ToString()); }
2093 };
2094 Handler handler;
2095 handler.map_ = &map_;
2096 return batch->Iterate(&handler);
2097 }
2098
2099 bool GetProperty(const Slice& property, std::string* value) override {
2100 return false;
2101 }
2102 void GetApproximateSizes(const Range* r, int n, uint64_t* sizes) override {
2103 for (int i = 0; i < n; i++) {
2104 sizes[i] = 0;
2105 }
2106 }
2107 void CompactRange(const Slice* start, const Slice* end) override {}
2108
2109 private:
2110 class ModelIter : public Iterator {
2111 public:
2112 ModelIter(const KVMap* map, bool owned)
2113 : map_(map), owned_(owned), iter_(map_->end()) {}
2114 ~ModelIter() override {
2115 if (owned_) delete map_;
2116 }
2117 bool Valid() const override { return iter_ != map_->end(); }
2118 void SeekToFirst() override { iter_ = map_->begin(); }
2119 void SeekToLast() override {
2120 if (map_->empty()) {
2121 iter_ = map_->end();
2122 } else {
2123 iter_ = map_->find(map_->rbegin()->first);
2124 }
2125 }
2126 void Seek(const Slice& k) override {
2127 iter_ = map_->lower_bound(k.ToString());
2128 }
2129 void Next() override { ++iter_; }
2130 void Prev() override { --iter_; }
2131 Slice key() const override { return iter_->first; }
2132 Slice value() const override { return iter_->second; }
2133 Status status() const override { return Status::OK(); }
2134
2135 private:
2136 const KVMap* const map_;
2137 const bool owned_; // Do we own map_
2138 KVMap::const_iterator iter_;
2139 };
2140 const Options options_;
2141 KVMap map_;
2142};
2143
2144static bool CompareIterators(int step, DB* model, DB* db,
2145 const Snapshot* model_snap,
2146 const Snapshot* db_snap) {
2147 ReadOptions options;
2148 options.snapshot = model_snap;
2149 Iterator* miter = model->NewIterator(options);
2150 options.snapshot = db_snap;
2151 Iterator* dbiter = db->NewIterator(options);
2152 bool ok = true;
2153 int count = 0;
2154 std::vector<std::string> seek_keys;
2155 // Compare equality of all elements using Next(). Save some of the keys for
2156 // comparing Seek equality.
2157 for (miter->SeekToFirst(), dbiter->SeekToFirst();
2158 ok && miter->Valid() && dbiter->Valid(); miter->Next(), dbiter->Next()) {
2159 count++;
2160 if (miter->key().compare(dbiter->key()) != 0) {
2161 std::fprintf(stderr, "step %d: Key mismatch: '%s' vs. '%s'\n", step,
2162 EscapeString(miter->key()).c_str(),
2163 EscapeString(dbiter->key()).c_str());
2164 ok = false;
2165 break;
2166 }
2167
2168 if (miter->value().compare(dbiter->value()) != 0) {
2169 std::fprintf(stderr,
2170 "step %d: Value mismatch for key '%s': '%s' vs. '%s'\n",
2171 step, EscapeString(miter->key()).c_str(),
2172 EscapeString(miter->value()).c_str(),
2173 EscapeString(miter->value()).c_str());
2174 ok = false;
2175 break;
2176 }
2177
2178 if (count % 10 == 0) {
2179 seek_keys.push_back(miter->key().ToString());
2180 }
2181 }
2182
2183 if (ok) {
2184 if (miter->Valid() != dbiter->Valid()) {
2185 std::fprintf(stderr, "step %d: Mismatch at end of iterators: %d vs. %d\n",
2186 step, miter->Valid(), dbiter->Valid());
2187 ok = false;
2188 }
2189 }
2190
2191 if (ok) {
2192 // Validate iterator equality when performing seeks.
2193 for (auto kiter = seek_keys.begin(); ok && kiter != seek_keys.end();
2194 ++kiter) {
2195 miter->Seek(*kiter);
2196 dbiter->Seek(*kiter);
2197 if (!miter->Valid() || !dbiter->Valid()) {
2198 std::fprintf(stderr, "step %d: Seek iterators invalid: %d vs. %d\n",
2199 step, miter->Valid(), dbiter->Valid());
2200 ok = false;
2201 }
2202 if (miter->key().compare(dbiter->key()) != 0) {
2203 std::fprintf(stderr, "step %d: Seek key mismatch: '%s' vs. '%s'\n",
2204 step, EscapeString(miter->key()).c_str(),
2205 EscapeString(dbiter->key()).c_str());
2206 ok = false;
2207 break;
2208 }
2209
2210 if (miter->value().compare(dbiter->value()) != 0) {
2211 std::fprintf(
2212 stderr,
2213 "step %d: Seek value mismatch for key '%s': '%s' vs. '%s'\n", step,
2214 EscapeString(miter->key()).c_str(),
2215 EscapeString(miter->value()).c_str(),
2216 EscapeString(miter->value()).c_str());
2217 ok = false;
2218 break;
2219 }
2220 }
2221 }
2222
2223 std::fprintf(stderr, "%d entries compared: ok=%d\n", count, ok);
2224 delete miter;
2225 delete dbiter;
2226 return ok;
2227}
2228
2229TEST_F(DBTest, Randomized) {
2230 Random rnd(test::RandomSeed());
2231 do {
2232 ModelDB model(CurrentOptions());
2233 const int N = 10000;
2234 const Snapshot* model_snap = nullptr;
2235 const Snapshot* db_snap = nullptr;
2236 std::string k, v;
2237 for (int step = 0; step < N; step++) {
2238 if (step % 100 == 0) {
2239 std::fprintf(stderr, "Step %d of %d\n", step, N);
2240 }
2241 // TODO(sanjay): Test Get() works
2242 int p = rnd.Uniform(100);
2243 if (p < 45) { // Put
2244 k = RandomKey(&rnd);
2245 v = RandomString(
2246 &rnd, rnd.OneIn(20) ? 100 + rnd.Uniform(100) : rnd.Uniform(8));
2247 ASSERT_LEVELDB_OK(model.Put(WriteOptions(), k, v));
2248 ASSERT_LEVELDB_OK(db_->Put(WriteOptions(), k, v));
2249
2250 } else if (p < 90) { // Delete
2251 k = RandomKey(&rnd);
2252 ASSERT_LEVELDB_OK(model.Delete(WriteOptions(), k));
2253 ASSERT_LEVELDB_OK(db_->Delete(WriteOptions(), k));
2254
2255 } else { // Multi-element batch
2256 WriteBatch b;
2257 const int num = rnd.Uniform(8);
2258 for (int i = 0; i < num; i++) {
2259 if (i == 0 || !rnd.OneIn(10)) {
2260 k = RandomKey(&rnd);
2261 } else {
2262 // Periodically re-use the same key from the previous iter, so
2263 // we have multiple entries in the write batch for the same key
2264 }
2265 if (rnd.OneIn(2)) {
2266 v = RandomString(&rnd, rnd.Uniform(10));
2267 b.Put(k, v);
2268 } else {
2269 b.Delete(k);
2270 }
2271 }
2272 ASSERT_LEVELDB_OK(model.Write(WriteOptions(), &b));
2273 ASSERT_LEVELDB_OK(db_->Write(WriteOptions(), &b));
2274 }
2275
2276 if ((step % 100) == 0) {
2277 ASSERT_TRUE(CompareIterators(step, &model, db_, nullptr, nullptr));
2278 ASSERT_TRUE(CompareIterators(step, &model, db_, model_snap, db_snap));
2279 // Save a snapshot from each DB this time that we'll use next
2280 // time we compare things, to make sure the current state is
2281 // preserved with the snapshot
2282 if (model_snap != nullptr) model.ReleaseSnapshot(model_snap);
2283 if (db_snap != nullptr) db_->ReleaseSnapshot(db_snap);
2284
2285 Reopen();
2286 ASSERT_TRUE(CompareIterators(step, &model, db_, nullptr, nullptr));
2287
2288 model_snap = model.GetSnapshot();
2289 db_snap = db_->GetSnapshot();
2290 }
2291 }
2292 if (model_snap != nullptr) model.ReleaseSnapshot(model_snap);
2293 if (db_snap != nullptr) db_->ReleaseSnapshot(db_snap);
2294 } while (ChangeOptions());
2295}
2296
2297} // namespace leveldb
2298