diff options
Diffstat (limited to 'db')
| -rw-r--r-- | db/memtable.h | 2 | ||||
| -rw-r--r-- | db/skiplist.cu | 1 | ||||
| -rw-r--r-- | db/skiplist.cuh | 383 | ||||
| -rw-r--r-- | db/skiplist.h | 2 | ||||
| -rw-r--r-- | db/skiplist_test.cu (renamed from db/skiplist_test.cc) | 65 |
5 files changed, 445 insertions, 8 deletions
diff --git a/db/memtable.h b/db/memtable.h index 3d3444b..1099504 100644 --- a/db/memtable.h +++ b/db/memtable.h @@ -11,7 +11,7 @@ #include "leveldb/db.h" -#include "util/arena.cuh" +#include "util/arena.h" namespace leveldb { diff --git a/db/skiplist.cu b/db/skiplist.cu new file mode 100644 index 0000000..c6517e2 --- /dev/null +++ b/db/skiplist.cu @@ -0,0 +1 @@ +#include "db/skiplist.cuh" diff --git a/db/skiplist.cuh b/db/skiplist.cuh new file mode 100644 index 0000000..5310d9c --- /dev/null +++ b/db/skiplist.cuh @@ -0,0 +1,383 @@ +// 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_DB_SKIPLIST_H_ +#define STORAGE_LEVELDB_DB_SKIPLIST_H_ + +// Thread safety +// ------------- +// +// Writes require external synchronization, most likely a mutex. +// Reads require a guarantee that the SkipList will not be destroyed +// while the read is in progress. Apart from that, reads progress +// without any internal locking or synchronization. +// +// Invariants: +// +// (1) Allocated nodes are never deleted until the SkipList is +// destroyed. This is trivially guaranteed by the code since we +// never delete any skip list nodes. +// +// (2) The contents of a Node except for the next/prev pointers are +// immutable after the Node has been linked into the SkipList. +// Only Insert() modifies the list, and it is careful to initialize +// a node and use release-stores to publish the nodes in one or +// more lists. +// +// ... prev vs. next pointer ordering ... + +#include <atomic> +#include <cassert> +#include <cstdlib> +#include <cuda/atomic> + +#include "util/arena.cuh" +#include "util/random.cuh" + +namespace leveldb { + +class Arena; + +template <typename Key, class Comparator> +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. + __device__ 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 + __device__ 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 }; + + __device__ inline int GetMaxHeight() const { + return max_height_.load(cuda::memory_order_relaxed); + } + + __device__ Node* NewNode(const Key& key, int height); + __device__ int RandomHeight(); + __device__ 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]. + __device__ 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. + cuda::atomic<int> max_height_; // Height of the entire list + + // Read/written only by Insert(). + Random rnd_; +}; + +// Implementation details follow +template <typename Key, class Comparator> +struct SkipList<Key, Comparator>::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); + } + __device__ 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. + __device__ Node* NoBarrier_Next(int n) { + assert(n >= 0); + return next_[n].load(std::memory_order_relaxed); + } + __device__ 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<Node*> next_[1]; +}; + +template <typename Key, class Comparator> +__device__ typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::NewNode( + const Key& key, int height) { + char* const node_memory = arena_->AllocateAligned( + sizeof(Node) + sizeof(std::atomic<Node*>) * (height - 1)); + return new (node_memory) Node(key); +} + +template <typename Key, class Comparator> +inline SkipList<Key, Comparator>::Iterator::Iterator(const SkipList* list) { + list_ = list; + node_ = nullptr; +} + +template <typename Key, class Comparator> +inline bool SkipList<Key, Comparator>::Iterator::Valid() const { + return node_ != nullptr; +} + +template <typename Key, class Comparator> +inline const Key& SkipList<Key, Comparator>::Iterator::key() const { + assert(Valid()); + return node_->key; +} + +template <typename Key, class Comparator> +inline void SkipList<Key, Comparator>::Iterator::Next() { + assert(Valid()); + node_ = node_->Next(0); +} + +template <typename Key, class Comparator> +inline void SkipList<Key, Comparator>::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 <typename Key, class Comparator> +__device__ inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) { + node_ = list_->FindGreaterOrEqual(target, nullptr); +} + +template <typename Key, class Comparator> +inline void SkipList<Key, Comparator>::Iterator::SeekToFirst() { + node_ = list_->head_->Next(0); +} + +template <typename Key, class Comparator> +inline void SkipList<Key, Comparator>::Iterator::SeekToLast() { + node_ = list_->FindLast(); + if (node_ == list_->head_) { + node_ = nullptr; + } +} + +template <typename Key, class Comparator> +__device__ int SkipList<Key, Comparator>::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 <typename Key, class Comparator> +bool SkipList<Key, Comparator>::KeyIsAfterNode(const Key& key, Node* n) const { + // null n is considered infinite + return (n != nullptr) && (compare_(n->key, key) < 0); +} + +template <typename Key, class Comparator> +typename SkipList<Key, Comparator>::Node* +__device__ SkipList<Key, Comparator>::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 Key, class Comparator> +typename SkipList<Key, Comparator>::Node* +SkipList<Key, Comparator>::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 Key, class Comparator> +typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::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 <typename Key, class Comparator> +SkipList<Key, Comparator>::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 <typename Key, class Comparator> +__device__ void SkipList<Key, Comparator>::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, cuda::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 <typename Key, class Comparator> +bool SkipList<Key, Comparator>::Contains(const Key& key) const { + Node* x = FindGreaterOrEqual(key, nullptr); + if (x != nullptr && Equal(key, x->key)) { + return true; + } else { + return false; + } +} + +} // namespace leveldb + +#endif // STORAGE_LEVELDB_DB_SKIPLIST_H_ diff --git a/db/skiplist.h b/db/skiplist.h index 13df778..a59b45b 100644 --- a/db/skiplist.h +++ b/db/skiplist.h @@ -31,7 +31,7 @@ #include <cassert> #include <cstdlib> -#include "util/arena.cuh" +#include "util/arena.h" #include "util/random.h" namespace leveldb { diff --git a/db/skiplist_test.cc b/db/skiplist_test.cu index 402cb47..53f60f8 100644 --- a/db/skiplist_test.cc +++ b/db/skiplist_test.cu @@ -2,9 +2,8 @@ // 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 <atomic> +#include "db/skiplist.cuh" +//#include <atomic> #include <set> #include "leveldb/env.h" @@ -13,7 +12,7 @@ #include "port/thread_annotations.h" #include "util/arena.cuh" #include "util/hash.h" -#include "util/random.h" +#include "util/random.cuh" #include "util/testutil.h" #include "gtest/gtest.h" @@ -34,7 +33,7 @@ struct Comparator { } }; -TEST(SkipTest, Empty) { +/*TEST(SkipTest, Empty) { Arena arena; Comparator cmp; SkipList<Key, Comparator> list(cmp, &arena); @@ -281,8 +280,61 @@ class ConcurrentTest { } } } -}; +};*/ + + +__device__ void update_list(SkipList<Key, Comparator> * l, Key key) { + l->Insert(key); +} + +__global__ void insert_skiplist(SkipList<Key, Comparator> * l, Random * rnd) { + unsigned row = threadIdx.x + blockIdx.x * blockDim.x; + for (int i = 0; i < 1000; i++ ) { + update_list(l, rnd->Next()); + } +} + + + +__host__ void host_insert_test() { + constexpr size_t sz_size = 1024; + Arena arena; + Comparator cmp; + Key * keys; + //SkipList<Key, Comparator> list(cmp, &arena); + + SkipList<Key, Comparator> * ptr_list; + Random * device_rnd; + + //cudaMallocManaged((void**)&keys, sizeof(Key) * sz_size); + cudaMallocManaged((void**)&device_rnd, sizeof(Random)); + cudaMallocManaged((void**)&ptr_list, sizeof(SkipList<Key, Comparator>)); + + ptr_list = new SkipList<Key, Comparator>(cmp, &arena); + device_rnd = new Random(test::RandomSeed()); + /* + for (int i = 0; i < 1000; i++) { + keys[i] = .Next(); + }*/ + + dim3 blockSize(32, 1); + + dim3 gridSize(32, 1); + + insert_skiplist<<<gridSize, blockSize>>>(ptr_list, device_rnd); + + cudaDeviceSynchronize(); + + cudaFree(&device_rnd); + cudaFree(ptr_list); +} + + +TEST(SkipTest, TestCudaInsert) { + host_insert_test(); +} +/* // Needed when building in C++11 mode. constexpr uint32_t ConcurrentTest::K; @@ -366,6 +418,7 @@ TEST(SkipTest, Concurrent2) { RunConcurrent(2); } TEST(SkipTest, Concurrent3) { RunConcurrent(3); } TEST(SkipTest, Concurrent4) { RunConcurrent(4); } TEST(SkipTest, Concurrent5) { RunConcurrent(5); } +*/ } // namespace leveldb |