From c0b9d06b6688088fd167b0c1f897934185074c01 Mon Sep 17 00:00:00 2001 From: KunoiSayami Date: Sun, 7 Nov 2021 20:06:38 +0800 Subject: feat: Add googletest Signed-off-by: KunoiSayami --- .gitmodules | 3 + CMakeLists.txt | 16 ++- headers/random.h | 57 -------- headers/skiplist.cuh | 359 ++++++++++++++++++++++++++++++++++++++++++++++ tests/arena_test.cu | 2 +- tests/skiplist_test.cu | 376 +++++++++++++++++++++++++++++++++++++++++++++++++ thirdparty/googletest | 1 + utils/random.h | 57 ++++++++ utils/testutil.cpp | 51 +++++++ utils/testutil.cuh | 88 ++++++++++++ 10 files changed, 950 insertions(+), 60 deletions(-) create mode 100644 .gitmodules delete mode 100644 headers/random.h create mode 100644 headers/skiplist.cuh create mode 100644 tests/skiplist_test.cu create mode 160000 thirdparty/googletest create mode 100644 utils/random.h create mode 100644 utils/testutil.cpp create mode 100644 utils/testutil.cuh diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..3380c92 --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "thirdparty/googletest"] + path = thirdparty/googletest + url = https://github.com/google/googletest.git diff --git a/CMakeLists.txt b/CMakeLists.txt index 0a22fb5..b33b646 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -10,11 +10,23 @@ add_library(cleveldb "") target_sources( cleveldb PUBLIC + "utils/testutil.cuh" + "utils/testutil.cpp" "headers/arena.cuh" "headers/arena.cu" - "headers/random.h" + "utils/random.h" + "headers/skiplist.cuh" ) +enable_testing() +set(gtest_force_shared_crt ON CACHE BOOL "" FORCE) +set(install_gtest OFF) +set(install_gmock OFF) +set(build_gmock ON) + + +add_subdirectory("thirdparty/googletest") + function(cleveldb_test test_file) get_filename_component(test_target_name "${test_file}" NAME_WE) @@ -22,7 +34,7 @@ function(cleveldb_test test_file) target_sources(arena_test PRIVATE "${test_file}") - target_link_libraries("${test_target_name}" cleveldb) + target_link_libraries("${test_target_name}" cleveldb gtest) add_test(NAME "${test_target_name}" COMMAND "${test_target_name}") endfunction(cleveldb_test) diff --git a/headers/random.h b/headers/random.h deleted file mode 100644 index 2b04757..0000000 --- a/headers/random.h +++ /dev/null @@ -1,57 +0,0 @@ -#ifndef CLEVELDB_RANDOM_H -#define CLEVELDB_RANDOM_H -#include - -namespace cleveldb { - -// A very simple random number generator. Not especially good at -// generating truly random bits, but good enough for our needs in this -// package. - class Random { - private: - uint32_t seed_; - - public: - explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) { - // Avoid bad seeds. - if (seed_ == 0 || seed_ == 2147483647L) { - seed_ = 1; - } - } - uint32_t Next() { - static const uint32_t M = 2147483647L; // 2^31-1 - static const uint64_t A = 16807; // bits 14, 8, 7, 5, 2, 1, 0 - // We are computing - // seed_ = (seed_ * A) % M, where M = 2^31-1 - // - // seed_ must not be zero or M, or else all subsequent computed values - // will be zero or M respectively. For all other values, seed_ will end - // up cycling through every number in [1,M-1] - uint64_t product = seed_ * A; - - // Compute (product % M) using the fact that ((x << 31) % M) == x. - seed_ = static_cast((product >> 31) + (product & M)); - // The first reduction may overflow by 1 bit, so we may need to - // repeat. mod == M is not possible; using > allows the faster - // sign-bit-based test. - if (seed_ > M) { - seed_ -= M; - } - return seed_; - } - // Returns a uniformly distributed value in the range [0..n-1] - // REQUIRES: n > 0 - uint32_t Uniform(int n) { return Next() % n; } - - // Randomly returns true ~"1/n" of the time, and false otherwise. - // REQUIRES: n > 0 - bool OneIn(int n) { return (Next() % n) == 0; } - - // Skewed: pick "base" uniformly from range [0,max_log] and then - // return "base" random bits. The effect is to pick a number in the - // range [0,2^max_log-1] with exponential bias towards smaller numbers. - uint32_t Skewed(int max_log) { return Uniform(1 << Uniform(max_log + 1)); } - }; - -} // namespace cleveldb -#endif //CLEVELDB_RANDOM_H diff --git a/headers/skiplist.cuh b/headers/skiplist.cuh new file mode 100644 index 0000000..fb19f7e --- /dev/null +++ b/headers/skiplist.cuh @@ -0,0 +1,359 @@ +// +// Created by user on 05/11/2021. +// + +#ifndef CLEVELDB_SKIPLIST_CUH +#define CLEVELDB_SKIPLIST_CUH + +#include +#include +#include + +#include "arena.h" +#include "../utils/random.h" + +namespace cleveldb { + + class Arena; + + template + class SkipList { + private: + struct Node; + + public: + // Create a new SkipList object that will use "cmp" for comparing keys, + // and will allocate memory using "*arena". Objects allocated in the arena + // must remain allocated for the lifetime of the skiplist object. + explicit SkipList(Comparator cmp, Arena* arena); + + SkipList(const SkipList&) = delete; + SkipList& operator=(const SkipList&) = delete; + + // Insert key into the list. + // REQUIRES: nothing that compares equal to key is currently in the list. + void Insert(const Key& key); + + // Returns true iff an entry that compares equal to key is in the list. + bool Contains(const Key& key) const; + + // Iteration over the contents of a skip list + class Iterator { + public: + // Initialize an iterator over the specified list. + // The returned iterator is not valid. + explicit Iterator(const SkipList* list); + + // Returns true iff the iterator is positioned at a valid node. + bool Valid() const; + + // Returns the key at the current position. + // REQUIRES: Valid() + const Key& key() const; + + // Advances to the next position. + // REQUIRES: Valid() + void Next(); + + // Advances to the previous position. + // REQUIRES: Valid() + void Prev(); + + // Advance to the first entry with a key >= target + void Seek(const Key& target); + + // Position at the first entry in list. + // Final state of iterator is Valid() iff list is not empty. + void SeekToFirst(); + + // Position at the last entry in list. + // Final state of iterator is Valid() iff list is not empty. + void SeekToLast(); + + private: + const SkipList* list_; + Node* node_; + // Intentionally copyable + }; + + private: + enum { kMaxHeight = 12 }; + + inline int GetMaxHeight() const { + return max_height_.load(std::memory_order_relaxed); + } + + Node* NewNode(const Key& key, int height); + int RandomHeight(); + bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); } + + // Return true if key is greater than the data stored in "n" + bool KeyIsAfterNode(const Key& key, Node* n) const; + + // Return the earliest node that comes at or after key. + // Return nullptr if there is no such node. + // + // If prev is non-null, fills prev[level] with pointer to previous + // node at "level" for every level in [0..max_height_-1]. + Node* FindGreaterOrEqual(const Key& key, Node** prev) const; + + // Return the latest node with a key < key. + // Return head_ if there is no such node. + Node* FindLessThan(const Key& key) const; + + // Return the last node in the list. + // Return head_ if list is empty. + Node* FindLast() const; + + // Immutable after construction + Comparator const compare_; + Arena* const arena_; // Arena used for allocations of nodes + + Node* const head_; + + // Modified only by Insert(). Read racily by readers, but stale + // values are ok. + std::atomic max_height_; // Height of the entire list + + // Read/written only by Insert(). + Random rnd_; + }; + +// Implementation details follow + template + struct SkipList::Node { + explicit Node(const Key& k) : key(k) {} + + Key const key; + + // Accessors/mutators for links. Wrapped in methods so we can + // add the appropriate barriers as necessary. + Node* Next(int n) { + assert(n >= 0); + // Use an 'acquire load' so that we observe a fully initialized + // version of the returned Node. + return next_[n].load(std::memory_order_acquire); + } + void SetNext(int n, Node* x) { + assert(n >= 0); + // Use a 'release store' so that anybody who reads through this + // pointer observes a fully initialized version of the inserted node. + next_[n].store(x, std::memory_order_release); + } + + // No-barrier variants that can be safely used in a few locations. + Node* NoBarrier_Next(int n) { + assert(n >= 0); + return next_[n].load(std::memory_order_relaxed); + } + void NoBarrier_SetNext(int n, Node* x) { + assert(n >= 0); + next_[n].store(x, std::memory_order_relaxed); + } + + private: + // Array of length equal to the node height. next_[0] is lowest level link. + std::atomic next_[1]; + }; + + template + typename SkipList::Node* SkipList::NewNode( + const Key& key, int height) { + char* const node_memory = arena_->AllocateAligned( + sizeof(Node) + sizeof(std::atomic) * (height - 1)); + return new (node_memory) Node(key); + } + + template + inline SkipList::Iterator::Iterator(const SkipList* list) { + list_ = list; + node_ = nullptr; + } + + template + inline bool SkipList::Iterator::Valid() const { + return node_ != nullptr; + } + + template + inline const Key& SkipList::Iterator::key() const { + assert(Valid()); + return node_->key; + } + + template + inline void SkipList::Iterator::Next() { + assert(Valid()); + node_ = node_->Next(0); + } + + template + inline void SkipList::Iterator::Prev() { + // Instead of using explicit "prev" links, we just search for the + // last node that falls before key. + assert(Valid()); + node_ = list_->FindLessThan(node_->key); + if (node_ == list_->head_) { + node_ = nullptr; + } + } + + template + inline void SkipList::Iterator::Seek(const Key& target) { + node_ = list_->FindGreaterOrEqual(target, nullptr); + } + + template + inline void SkipList::Iterator::SeekToFirst() { + node_ = list_->head_->Next(0); + } + + template + inline void SkipList::Iterator::SeekToLast() { + node_ = list_->FindLast(); + if (node_ == list_->head_) { + node_ = nullptr; + } + } + + template + int SkipList::RandomHeight() { + // Increase height with probability 1 in kBranching + static const unsigned int kBranching = 4; + int height = 1; + while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) { + height++; + } + assert(height > 0); + assert(height <= kMaxHeight); + return height; + } + + template + bool SkipList::KeyIsAfterNode(const Key& key, Node* n) const { + // null n is considered infinite + return (n != nullptr) && (compare_(n->key, key) < 0); + } + + template + typename SkipList::Node* + SkipList::FindGreaterOrEqual(const Key& key, + Node** prev) const { + Node* x = head_; + int level = GetMaxHeight() - 1; + while (true) { + Node* next = x->Next(level); + if (KeyIsAfterNode(key, next)) { + // Keep searching in this list + x = next; + } else { + if (prev != nullptr) prev[level] = x; + if (level == 0) { + return next; + } else { + // Switch to next list + level--; + } + } + } + } + + template + typename SkipList::Node* + SkipList::FindLessThan(const Key& key) const { + Node* x = head_; + int level = GetMaxHeight() - 1; + while (true) { + assert(x == head_ || compare_(x->key, key) < 0); + Node* next = x->Next(level); + if (next == nullptr || compare_(next->key, key) >= 0) { + if (level == 0) { + return x; + } else { + // Switch to next list + level--; + } + } else { + x = next; + } + } + } + + template + typename SkipList::Node* SkipList::FindLast() + const { + Node* x = head_; + int level = GetMaxHeight() - 1; + while (true) { + Node* next = x->Next(level); + if (next == nullptr) { + if (level == 0) { + return x; + } else { + // Switch to next list + level--; + } + } else { + x = next; + } + } + } + + template + SkipList::SkipList(Comparator cmp, Arena* arena) + : compare_(cmp), + arena_(arena), + head_(NewNode(0 /* any key will do */, kMaxHeight)), + max_height_(1), + rnd_(0xdeadbeef) { + for (int i = 0; i < kMaxHeight; i++) { + head_->SetNext(i, nullptr); + } + } + + template + void SkipList::Insert(const Key& key) { + // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual() + // here since Insert() is externally synchronized. + Node* prev[kMaxHeight]; + Node* x = FindGreaterOrEqual(key, prev); + + // Our data structure does not allow duplicate insertion + assert(x == nullptr || !Equal(key, x->key)); + + int height = RandomHeight(); + if (height > GetMaxHeight()) { + for (int i = GetMaxHeight(); i < height; i++) { + prev[i] = head_; + } + // It is ok to mutate max_height_ without any synchronization + // with concurrent readers. A concurrent reader that observes + // the new value of max_height_ will see either the old value of + // new level pointers from head_ (nullptr), or a new value set in + // the loop below. In the former case the reader will + // immediately drop to the next level since nullptr sorts after all + // keys. In the latter case the reader will use the new node. + max_height_.store(height, std::memory_order_relaxed); + } + + x = NewNode(key, height); + for (int i = 0; i < height; i++) { + // NoBarrier_SetNext() suffices since we will add a barrier when + // we publish a pointer to "x" in prev[i]. + x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i)); + prev[i]->SetNext(i, x); + } + } + + template + bool SkipList::Contains(const Key& key) const { + Node* x = FindGreaterOrEqual(key, nullptr); + if (x != nullptr && Equal(key, x->key)) { + return true; + } else { + return false; + } + } + +} // namespace cleveldb +#endif //CLEVELDB_SKIPLIST_CUH diff --git a/tests/arena_test.cu b/tests/arena_test.cu index be9795d..9be7739 100644 --- a/tests/arena_test.cu +++ b/tests/arena_test.cu @@ -1,5 +1,5 @@ #include "../headers/arena.cuh" -#include "../headers/random.h" +#include "../utils/random.h" using namespace cleveldb; diff --git a/tests/skiplist_test.cu b/tests/skiplist_test.cu new file mode 100644 index 0000000..d636708 --- /dev/null +++ b/tests/skiplist_test.cu @@ -0,0 +1,376 @@ +// +// Created by user on 06/11/2021. +// + +// Copyright (c) 2011 The LevelDB Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. See the AUTHORS file for names of contributors. + +#include "db/skiplist.h" + +#include +#include + +#include "gtest/gtest.h" +#include "leveldb/env.h" +#include "port/thread_annotations.h" +#include "util/arena.h" +#include "util/hash.h" +#include "util/random.h" +#include "util/testutil.h" + +namespace leveldb { + + typedef uint64_t Key; + + struct Comparator { + int operator()(const Key& a, const Key& b) const { + if (a < b) { + return -1; + } else if (a > b) { + return +1; + } else { + return 0; + } + } + }; + + TEST(SkipTest, Empty) { + Arena arena; + Comparator cmp; + SkipList list(cmp, &arena); + ASSERT_TRUE(!list.Contains(10)); + + SkipList::Iterator iter(&list); + ASSERT_TRUE(!iter.Valid()); + iter.SeekToFirst(); + ASSERT_TRUE(!iter.Valid()); + iter.Seek(100); + ASSERT_TRUE(!iter.Valid()); + iter.SeekToLast(); + ASSERT_TRUE(!iter.Valid()); +} + +TEST(SkipTest, InsertAndLookup) { +const int N = 2000; +const int R = 5000; +Random rnd(1000); +std::set keys; +Arena arena; +Comparator cmp; +SkipList list(cmp, &arena); +for (int i = 0; i < N; i++) { +Key key = rnd.Next() % R; +if (keys.insert(key).second) { +list.Insert(key); +} +} + +for (int i = 0; i < R; i++) { +if (list.Contains(i)) { +ASSERT_EQ(keys.count(i), 1); +} else { +ASSERT_EQ(keys.count(i), 0); +} +} + +// Simple iterator tests +{ +SkipList::Iterator iter(&list); +ASSERT_TRUE(!iter.Valid()); + +iter.Seek(0); +ASSERT_TRUE(iter.Valid()); +ASSERT_EQ(*(keys.begin()), iter.key()); + +iter.SeekToFirst(); +ASSERT_TRUE(iter.Valid()); +ASSERT_EQ(*(keys.begin()), iter.key()); + +iter.SeekToLast(); +ASSERT_TRUE(iter.Valid()); +ASSERT_EQ(*(keys.rbegin()), iter.key()); +} + +// Forward iteration test +for (int i = 0; i < R; i++) { +SkipList::Iterator iter(&list); +iter.Seek(i); + +// Compare against model iterator +std::set::iterator model_iter = keys.lower_bound(i); +for (int j = 0; j < 3; j++) { +if (model_iter == keys.end()) { +ASSERT_TRUE(!iter.Valid()); +break; +} else { +ASSERT_TRUE(iter.Valid()); +ASSERT_EQ(*model_iter, iter.key()); +++model_iter; +iter.Next(); +} +} +} + +// Backward iteration test +{ +SkipList::Iterator iter(&list); +iter.SeekToLast(); + +// Compare against model iterator +for (std::set::reverse_iterator model_iter = keys.rbegin(); +model_iter != keys.rend(); ++model_iter) { +ASSERT_TRUE(iter.Valid()); +ASSERT_EQ(*model_iter, iter.key()); +iter.Prev(); +} +ASSERT_TRUE(!iter.Valid()); +} +} + +// We want to make sure that with a single writer and multiple +// concurrent readers (with no synchronization other than when a +// reader's iterator is created), the reader always observes all the +// data that was present in the skip list when the iterator was +// constructed. Because insertions are happening concurrently, we may +// also observe new values that were inserted since the iterator was +// constructed, but we should never miss any values that were present +// at iterator construction time. +// +// We generate multi-part keys: +// +// where: +// key is in range [0..K-1] +// gen is a generation number for key +// hash is hash(key,gen) +// +// The insertion code picks a random key, sets gen to be 1 + the last +// generation number inserted for that key, and sets hash to Hash(key,gen). +// +// At the beginning of a read, we snapshot the last inserted +// generation number for each key. We then iterate, including random +// calls to Next() and Seek(). For every key we encounter, we +// check that it is either expected given the initial snapshot or has +// been concurrently added since the iterator started. +class ConcurrentTest { +private: + static constexpr uint32_t K = 4; + + static uint64_t key(Key key) { return (key >> 40); } + static uint64_t gen(Key key) { return (key >> 8) & 0xffffffffu; } + static uint64_t hash(Key key) { return key & 0xff; } + + static uint64_t HashNumbers(uint64_t k, uint64_t g) { + uint64_t data[2] = {k, g}; + return Hash(reinterpret_cast(data), sizeof(data), 0); + } + + static Key MakeKey(uint64_t k, uint64_t g) { + static_assert(sizeof(Key) == sizeof(uint64_t), ""); + assert(k <= K); // We sometimes pass K to seek to the end of the skiplist + assert(g <= 0xffffffffu); + return ((k << 40) | (g << 8) | (HashNumbers(k, g) & 0xff)); + } + + static bool IsValidKey(Key k) { + return hash(k) == (HashNumbers(key(k), gen(k)) & 0xff); + } + + static Key RandomTarget(Random* rnd) { + switch (rnd->Next() % 10) { + case 0: + // Seek to beginning + return MakeKey(0, 0); + case 1: + // Seek to end + return MakeKey(K, 0); + default: + // Seek to middle + return MakeKey(rnd->Next() % K, 0); + } + } + + // Per-key generation + struct State { + std::atomic generation[K]; + void Set(int k, int v) { + generation[k].store(v, std::memory_order_release); + } + int Get(int k) { return generation[k].load(std::memory_order_acquire); } + + State() { + for (int k = 0; k < K; k++) { + Set(k, 0); + } + } + }; + + // Current state of the test + State current_; + + Arena arena_; + + // SkipList is not protected by mu_. We just use a single writer + // thread to modify it. + SkipList list_; + +public: + ConcurrentTest() : list_(Comparator(), &arena_) {} + + // REQUIRES: External synchronization + void WriteStep(Random* rnd) { + const uint32_t k = rnd->Next() % K; + const intptr_t g = current_.Get(k) + 1; + const Key key = MakeKey(k, g); + list_.Insert(key); + current_.Set(k, g); + } + + void ReadStep(Random* rnd) { + // Remember the initial committed state of the skiplist. + State initial_state; + for (int k = 0; k < K; k++) { + initial_state.Set(k, current_.Get(k)); + } + + Key pos = RandomTarget(rnd); + SkipList::Iterator iter(&list_); + iter.Seek(pos); + while (true) { + Key current; + if (!iter.Valid()) { + current = MakeKey(K, 0); + } else { + current = iter.key(); + ASSERT_TRUE(IsValidKey(current)) << current; + } + ASSERT_LE(pos, current) << "should not go backwards"; + + // Verify that everything in [pos,current) was not present in + // initial_state. + while (pos < current) { + ASSERT_LT(key(pos), K) << pos; + + // Note that generation 0 is never inserted, so it is ok if + // <*,0,*> is missing. + ASSERT_TRUE((gen(pos) == 0) || + (gen(pos) > static_cast(initial_state.Get(key(pos))))) + << "key: " << key(pos) << "; gen: " << gen(pos) + << "; initgen: " << initial_state.Get(key(pos)); + + // Advance to next key in the valid key space + if (key(pos) < key(current)) { + pos = MakeKey(key(pos) + 1, 0); + } else { + pos = MakeKey(key(pos), gen(pos) + 1); + } + } + + if (!iter.Valid()) { + break; + } + + if (rnd->Next() % 2) { + iter.Next(); + pos = MakeKey(key(pos), gen(pos) + 1); + } else { + Key new_target = RandomTarget(rnd); + if (new_target > pos) { + pos = new_target; + iter.Seek(new_target); + } + } + } + } +}; + +// Needed when building in C++11 mode. +constexpr uint32_t ConcurrentTest::K; + +// Simple test that does single-threaded testing of the ConcurrentTest +// scaffolding. +TEST(SkipTest, ConcurrentWithoutThreads) { +ConcurrentTest test; +Random rnd(test::RandomSeed()); +for (int i = 0; i < 10000; i++) { +test.ReadStep(&rnd); +test.WriteStep(&rnd); +} +} + +class TestState { +public: + ConcurrentTest t_; + int seed_; + std::atomic quit_flag_; + + enum ReaderState { STARTING, RUNNING, DONE }; + + explicit TestState(int s) + : seed_(s), quit_flag_(false), state_(STARTING), state_cv_(&mu_) {} + + void Wait(ReaderState s) LOCKS_EXCLUDED(mu_) { + mu_.Lock(); + while (state_ != s) { + state_cv_.Wait(); + } + mu_.Unlock(); + } + + void Change(ReaderState s) LOCKS_EXCLUDED(mu_) { + mu_.Lock(); + state_ = s; + state_cv_.Signal(); + mu_.Unlock(); + } + +private: + port::Mutex mu_; + ReaderState state_ GUARDED_BY(mu_); + port::CondVar state_cv_ GUARDED_BY(mu_); +}; + +static void ConcurrentReader(void* arg) { + TestState* state = reinterpret_cast(arg); + Random rnd(state->seed_); + int64_t reads = 0; + state->Change(TestState::RUNNING); + while (!state->quit_flag_.load(std::memory_order_acquire)) { + state->t_.ReadStep(&rnd); + ++reads; + } + state->Change(TestState::DONE); +} + +static void RunConcurrent(int run) { + const int seed = test::RandomSeed() + (run * 100); + Random rnd(seed); + const int N = 1000; + const int kSize = 1000; + for (int i = 0; i < N; i++) { + if ((i % 100) == 0) { + std::fprintf(stderr, "Run %d of %d\n", i, N); + } + TestState state(seed + 1); + Env::Default()->Schedule(ConcurrentReader, &state); + state.Wait(TestState::RUNNING); + for (int i = 0; i < kSize; i++) { + state.t_.WriteStep(&rnd); + } + state.quit_flag_.store(true, std::memory_order_release); + state.Wait(TestState::DONE); + } +} + +TEST(SkipTest, Concurrent1) { RunConcurrent(1); } +TEST(SkipTest, Concurrent2) { RunConcurrent(2); } +TEST(SkipTest, Concurrent3) { RunConcurrent(3); } +TEST(SkipTest, Concurrent4) { RunConcurrent(4); } +TEST(SkipTest, Concurrent5) { RunConcurrent(5); } + +} // namespace leveldb + +int main(int argc, char** argv) { + testing::InitGoogleTest(&argc, argv); + return RUN_ALL_TESTS(); +} diff --git a/thirdparty/googletest b/thirdparty/googletest new file mode 160000 index 0000000..bf0701d --- /dev/null +++ b/thirdparty/googletest @@ -0,0 +1 @@ +Subproject commit bf0701daa9f5b30e5882e2f8f9a5280bcba87e77 diff --git a/utils/random.h b/utils/random.h new file mode 100644 index 0000000..2b04757 --- /dev/null +++ b/utils/random.h @@ -0,0 +1,57 @@ +#ifndef CLEVELDB_RANDOM_H +#define CLEVELDB_RANDOM_H +#include + +namespace cleveldb { + +// A very simple random number generator. Not especially good at +// generating truly random bits, but good enough for our needs in this +// package. + class Random { + private: + uint32_t seed_; + + public: + explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) { + // Avoid bad seeds. + if (seed_ == 0 || seed_ == 2147483647L) { + seed_ = 1; + } + } + uint32_t Next() { + static const uint32_t M = 2147483647L; // 2^31-1 + static const uint64_t A = 16807; // bits 14, 8, 7, 5, 2, 1, 0 + // We are computing + // seed_ = (seed_ * A) % M, where M = 2^31-1 + // + // seed_ must not be zero or M, or else all subsequent computed values + // will be zero or M respectively. For all other values, seed_ will end + // up cycling through every number in [1,M-1] + uint64_t product = seed_ * A; + + // Compute (product % M) using the fact that ((x << 31) % M) == x. + seed_ = static_cast((product >> 31) + (product & M)); + // The first reduction may overflow by 1 bit, so we may need to + // repeat. mod == M is not possible; using > allows the faster + // sign-bit-based test. + if (seed_ > M) { + seed_ -= M; + } + return seed_; + } + // Returns a uniformly distributed value in the range [0..n-1] + // REQUIRES: n > 0 + uint32_t Uniform(int n) { return Next() % n; } + + // Randomly returns true ~"1/n" of the time, and false otherwise. + // REQUIRES: n > 0 + bool OneIn(int n) { return (Next() % n) == 0; } + + // Skewed: pick "base" uniformly from range [0,max_log] and then + // return "base" random bits. The effect is to pick a number in the + // range [0,2^max_log-1] with exponential bias towards smaller numbers. + uint32_t Skewed(int max_log) { return Uniform(1 << Uniform(max_log + 1)); } + }; + +} // namespace cleveldb +#endif //CLEVELDB_RANDOM_H diff --git a/utils/testutil.cpp b/utils/testutil.cpp new file mode 100644 index 0000000..1d3e04c --- /dev/null +++ b/utils/testutil.cpp @@ -0,0 +1,51 @@ +// Copyright (c) 2011 The LevelDB Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. See the AUTHORS file for names of contributors. + +#include "util/testutil.h" + +#include + +#include "util/random.h" + +namespace cleveldb { + namespace test { + + Slice RandomString(Random* rnd, int len, std::string* dst) { + dst->resize(len); + for (int i = 0; i < len; i++) { + (*dst)[i] = static_cast(' ' + rnd->Uniform(95)); // ' ' .. '~' + } + return Slice(*dst); + } + + std::string RandomKey(Random* rnd, int len) { + // Make sure to generate a wide variety of characters so we + // test the boundary conditions for short-key optimizations. + static const char kTestChars[] = {'\0', '\1', 'a', 'b', 'c', + 'd', 'e', '\xfd', '\xfe', '\xff'}; + std::string result; + for (int i = 0; i < len; i++) { + result += kTestChars[rnd->Uniform(sizeof(kTestChars))]; + } + return result; + } + + Slice CompressibleString(Random* rnd, double compressed_fraction, size_t len, + std::string* dst) { + int raw = static_cast(len * compressed_fraction); + if (raw < 1) raw = 1; + std::string raw_data; + RandomString(rnd, raw, &raw_data); + + // Duplicate the random data until we have filled "len" bytes + dst->clear(); + while (dst->size() < len) { + dst->append(raw_data); + } + dst->resize(len); + return Slice(*dst); + } + + } // namespace test +} // namespace leveldb diff --git a/utils/testutil.cuh b/utils/testutil.cuh new file mode 100644 index 0000000..f33e691 --- /dev/null +++ b/utils/testutil.cuh @@ -0,0 +1,88 @@ +#ifndef CLEVELDB_TESTUTIL_CUH + +// Copyright (c) 2011 The LevelDB Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. See the AUTHORS file for names of contributors. + +#ifndef STORAGE_LEVELDB_UTIL_TESTUTIL_H_ +#define STORAGE_LEVELDB_UTIL_TESTUTIL_H_ + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "helpers/memenv/memenv.h" +#include "leveldb/env.h" +#include "leveldb/slice.h" +#include "util/random.h" + +namespace cleveldb { + namespace test { + + MATCHER(IsOK, "") { return arg.ok(); } + +// Macros for testing the results of functions that return leveldb::Status or +// absl::StatusOr (for any type T). +#define EXPECT_LEVELDB_OK(expression) \ + EXPECT_THAT(expression, leveldb::test::IsOK()) +#define ASSERT_LEVELDB_OK(expression) \ + ASSERT_THAT(expression, leveldb::test::IsOK()) + +// Returns the random seed used at the start of the current test run. + inline int RandomSeed() { + return testing::UnitTest::GetInstance()->random_seed(); + } + +// Store in *dst a random string of length "len" and return a Slice that +// references the generated data. + Slice RandomString(Random* rnd, int len, std::string* dst); + +// Return a random key with the specified length that may contain interesting +// characters (e.g. \x00, \xff, etc.). + std::string RandomKey(Random* rnd, int len); + +// Store in *dst a string of length "len" that will compress to +// "N*compressed_fraction" bytes and return a Slice that references +// the generated data. + Slice CompressibleString(Random* rnd, double compressed_fraction, size_t len, + std::string* dst); + +// A wrapper that allows injection of errors. + class ErrorEnv : public EnvWrapper { + public: + bool writable_file_error_; + int num_writable_file_errors_; + + ErrorEnv() + : EnvWrapper(NewMemEnv(Env::Default())), + writable_file_error_(false), + num_writable_file_errors_(0) {} + ~ErrorEnv() override { delete target(); } + + Status NewWritableFile(const std::string& fname, + WritableFile** result) override { + if (writable_file_error_) { + ++num_writable_file_errors_; + *result = nullptr; + return Status::IOError(fname, "fake error"); + } + return target()->NewWritableFile(fname, result); + } + + Status NewAppendableFile(const std::string& fname, + WritableFile** result) override { + if (writable_file_error_) { + ++num_writable_file_errors_; + *result = nullptr; + return Status::IOError(fname, "fake error"); + } + return target()->NewAppendableFile(fname, result); + } + }; + +} // namespace test +} // namespace leveldb + +#endif // STORAGE_LEVELDB_UTIL_TESTUTIL_H_ + +#define CLEVELDB_TESTUTIL_CUH + +#endif //CLEVELDB_TESTUTIL_CUH -- cgit v1.3.1