diff options
| author | Wladimir J. van der Laan <laanwj@protonmail.com> | 2020-01-28 16:59:07 +0100 |
|---|---|---|
| committer | Wladimir J. van der Laan <laanwj@protonmail.com> | 2020-01-28 16:59:07 +0100 |
| commit | 20a6babfa9a66f5432ef19c6c433b4357560f853 (patch) | |
| tree | 0834cbc4054d41dfb8de5ec90143b4415adbc41d /src/leveldb/util | |
| parent | 2755b2b1092d0286022cf3cc3028e96f6bee2b34 (diff) | |
| parent | 66480821b36c839ab7615cb9309850015bceadb0 (diff) | |
Update to leveldb upstream using subtree merge
Diffstat (limited to 'src/leveldb/util')
44 files changed, 3582 insertions, 2353 deletions
diff --git a/src/leveldb/util/arena.cc b/src/leveldb/util/arena.cc index 74078213ee..46e3b2eb8f 100644 --- a/src/leveldb/util/arena.cc +++ b/src/leveldb/util/arena.cc @@ -3,16 +3,13 @@ // found in the LICENSE file. See the AUTHORS file for names of contributors. #include "util/arena.h" -#include <assert.h> namespace leveldb { static const int kBlockSize = 4096; -Arena::Arena() : memory_usage_(0) { - alloc_ptr_ = NULL; // First allocation will allocate a block - alloc_bytes_remaining_ = 0; -} +Arena::Arena() + : alloc_ptr_(nullptr), alloc_bytes_remaining_(0), memory_usage_(0) {} Arena::~Arena() { for (size_t i = 0; i < blocks_.size(); i++) { @@ -40,8 +37,9 @@ char* Arena::AllocateFallback(size_t bytes) { char* Arena::AllocateAligned(size_t bytes) { const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8; - assert((align & (align-1)) == 0); // Pointer size should be a power of 2 - size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1); + static_assert((align & (align - 1)) == 0, + "Pointer size should be a power of 2"); + size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align - 1); size_t slop = (current_mod == 0 ? 0 : align - current_mod); size_t needed = bytes + slop; char* result; @@ -53,15 +51,15 @@ char* Arena::AllocateAligned(size_t bytes) { // AllocateFallback always returned aligned memory result = AllocateFallback(bytes); } - assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0); + assert((reinterpret_cast<uintptr_t>(result) & (align - 1)) == 0); return result; } char* Arena::AllocateNewBlock(size_t block_bytes) { char* result = new char[block_bytes]; blocks_.push_back(result); - memory_usage_.NoBarrier_Store( - reinterpret_cast<void*>(MemoryUsage() + block_bytes + sizeof(char*))); + memory_usage_.fetch_add(block_bytes + sizeof(char*), + std::memory_order_relaxed); return result; } diff --git a/src/leveldb/util/arena.h b/src/leveldb/util/arena.h index 48bab33741..68fc55d4dd 100644 --- a/src/leveldb/util/arena.h +++ b/src/leveldb/util/arena.h @@ -5,29 +5,33 @@ #ifndef STORAGE_LEVELDB_UTIL_ARENA_H_ #define STORAGE_LEVELDB_UTIL_ARENA_H_ +#include <atomic> +#include <cassert> +#include <cstddef> +#include <cstdint> #include <vector> -#include <assert.h> -#include <stddef.h> -#include <stdint.h> -#include "port/port.h" namespace leveldb { class Arena { public: Arena(); + + Arena(const Arena&) = delete; + Arena& operator=(const Arena&) = delete; + ~Arena(); // Return a pointer to a newly allocated memory block of "bytes" bytes. char* Allocate(size_t bytes); - // Allocate memory with the normal alignment guarantees provided by malloc + // Allocate memory with the normal alignment guarantees provided by malloc. char* AllocateAligned(size_t bytes); // Returns an estimate of the total memory usage of data allocated // by the arena. size_t MemoryUsage() const { - return reinterpret_cast<uintptr_t>(memory_usage_.NoBarrier_Load()); + return memory_usage_.load(std::memory_order_relaxed); } private: @@ -42,11 +46,10 @@ class Arena { std::vector<char*> blocks_; // Total memory usage of the arena. - port::AtomicPointer memory_usage_; - - // No copying allowed - Arena(const Arena&); - void operator=(const Arena&); + // + // TODO(costan): This member is accessed via atomics, but the others are + // accessed without any locking. Is this OK? + std::atomic<size_t> memory_usage_; }; inline char* Arena::Allocate(size_t bytes) { diff --git a/src/leveldb/util/arena_test.cc b/src/leveldb/util/arena_test.cc index 58e870ec44..e917228f42 100644 --- a/src/leveldb/util/arena_test.cc +++ b/src/leveldb/util/arena_test.cc @@ -9,14 +9,12 @@ namespace leveldb { -class ArenaTest { }; +class ArenaTest {}; -TEST(ArenaTest, Empty) { - Arena arena; -} +TEST(ArenaTest, Empty) { Arena arena; } TEST(ArenaTest, Simple) { - std::vector<std::pair<size_t, char*> > allocated; + std::vector<std::pair<size_t, char*>> allocated; Arena arena; const int N = 100000; size_t bytes = 0; @@ -26,8 +24,9 @@ TEST(ArenaTest, Simple) { if (i % (N / 10) == 0) { s = i; } else { - s = rnd.OneIn(4000) ? rnd.Uniform(6000) : - (rnd.OneIn(10) ? rnd.Uniform(100) : rnd.Uniform(20)); + s = rnd.OneIn(4000) + ? rnd.Uniform(6000) + : (rnd.OneIn(10) ? rnd.Uniform(100) : rnd.Uniform(20)); } if (s == 0) { // Our arena disallows size 0 allocations. @@ -47,7 +46,7 @@ TEST(ArenaTest, Simple) { bytes += s; allocated.push_back(std::make_pair(s, r)); ASSERT_GE(arena.MemoryUsage(), bytes); - if (i > N/10) { + if (i > N / 10) { ASSERT_LE(arena.MemoryUsage(), bytes * 1.10); } } @@ -63,6 +62,4 @@ TEST(ArenaTest, Simple) { } // namespace leveldb -int main(int argc, char** argv) { - return leveldb::test::RunAllTests(); -} +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } diff --git a/src/leveldb/util/bloom.cc b/src/leveldb/util/bloom.cc index bf3e4ca6e9..87547a7e62 100644 --- a/src/leveldb/util/bloom.cc +++ b/src/leveldb/util/bloom.cc @@ -15,24 +15,17 @@ static uint32_t BloomHash(const Slice& key) { } class BloomFilterPolicy : public FilterPolicy { - private: - size_t bits_per_key_; - size_t k_; - public: - explicit BloomFilterPolicy(int bits_per_key) - : bits_per_key_(bits_per_key) { + explicit BloomFilterPolicy(int bits_per_key) : bits_per_key_(bits_per_key) { // We intentionally round down to reduce probing cost a little bit k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2) if (k_ < 1) k_ = 1; if (k_ > 30) k_ = 30; } - virtual const char* Name() const { - return "leveldb.BuiltinBloomFilter2"; - } + const char* Name() const override { return "leveldb.BuiltinBloomFilter2"; } - virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const { + void CreateFilter(const Slice* keys, int n, std::string* dst) const override { // Compute bloom filter size (in both bits and bytes) size_t bits = n * bits_per_key_; @@ -54,13 +47,13 @@ class BloomFilterPolicy : public FilterPolicy { const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits for (size_t j = 0; j < k_; j++) { const uint32_t bitpos = h % bits; - array[bitpos/8] |= (1 << (bitpos % 8)); + array[bitpos / 8] |= (1 << (bitpos % 8)); h += delta; } } } - virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const { + bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override { const size_t len = bloom_filter.size(); if (len < 2) return false; @@ -69,7 +62,7 @@ class BloomFilterPolicy : public FilterPolicy { // Use the encoded k so that we can read filters generated by // bloom filters created using different parameters. - const size_t k = array[len-1]; + const size_t k = array[len - 1]; if (k > 30) { // Reserved for potentially new encodings for short bloom filters. // Consider it a match. @@ -80,13 +73,17 @@ class BloomFilterPolicy : public FilterPolicy { const uint32_t delta = (h >> 17) | (h << 15); // Rotate right 17 bits for (size_t j = 0; j < k; j++) { const uint32_t bitpos = h % bits; - if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false; + if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false; h += delta; } return true; } + + private: + size_t bits_per_key_; + size_t k_; }; -} +} // namespace const FilterPolicy* NewBloomFilterPolicy(int bits_per_key) { return new BloomFilterPolicy(bits_per_key); diff --git a/src/leveldb/util/bloom_test.cc b/src/leveldb/util/bloom_test.cc index 1b87a2be3f..436daa9e99 100644 --- a/src/leveldb/util/bloom_test.cc +++ b/src/leveldb/util/bloom_test.cc @@ -19,26 +19,17 @@ static Slice Key(int i, char* buffer) { } class BloomTest { - private: - const FilterPolicy* policy_; - std::string filter_; - std::vector<std::string> keys_; - public: - BloomTest() : policy_(NewBloomFilterPolicy(10)) { } + BloomTest() : policy_(NewBloomFilterPolicy(10)) {} - ~BloomTest() { - delete policy_; - } + ~BloomTest() { delete policy_; } void Reset() { keys_.clear(); filter_.clear(); } - void Add(const Slice& s) { - keys_.push_back(s.ToString()); - } + void Add(const Slice& s) { keys_.push_back(s.ToString()); } void Build() { std::vector<Slice> key_slices; @@ -52,16 +43,14 @@ class BloomTest { if (kVerbose >= 2) DumpFilter(); } - size_t FilterSize() const { - return filter_.size(); - } + size_t FilterSize() const { return filter_.size(); } void DumpFilter() { fprintf(stderr, "F("); - for (size_t i = 0; i+1 < filter_.size(); i++) { + for (size_t i = 0; i + 1 < filter_.size(); i++) { const unsigned int c = static_cast<unsigned int>(filter_[i]); for (int j = 0; j < 8; j++) { - fprintf(stderr, "%c", (c & (1 <<j)) ? '1' : '.'); + fprintf(stderr, "%c", (c & (1 << j)) ? '1' : '.'); } } fprintf(stderr, ")\n"); @@ -84,11 +73,16 @@ class BloomTest { } return result / 10000.0; } + + private: + const FilterPolicy* policy_; + std::string filter_; + std::vector<std::string> keys_; }; TEST(BloomTest, EmptyFilter) { - ASSERT_TRUE(! Matches("hello")); - ASSERT_TRUE(! Matches("world")); + ASSERT_TRUE(!Matches("hello")); + ASSERT_TRUE(!Matches("world")); } TEST(BloomTest, Small) { @@ -96,8 +90,8 @@ TEST(BloomTest, Small) { Add("world"); ASSERT_TRUE(Matches("hello")); ASSERT_TRUE(Matches("world")); - ASSERT_TRUE(! Matches("x")); - ASSERT_TRUE(! Matches("foo")); + ASSERT_TRUE(!Matches("x")); + ASSERT_TRUE(!Matches("foo")); } static int NextLength(int length) { @@ -140,23 +134,23 @@ TEST(BloomTest, VaryingLengths) { double rate = FalsePositiveRate(); if (kVerbose >= 1) { fprintf(stderr, "False positives: %5.2f%% @ length = %6d ; bytes = %6d\n", - rate*100.0, length, static_cast<int>(FilterSize())); + rate * 100.0, length, static_cast<int>(FilterSize())); } - ASSERT_LE(rate, 0.02); // Must not be over 2% - if (rate > 0.0125) mediocre_filters++; // Allowed, but not too often - else good_filters++; + ASSERT_LE(rate, 0.02); // Must not be over 2% + if (rate > 0.0125) + mediocre_filters++; // Allowed, but not too often + else + good_filters++; } if (kVerbose >= 1) { - fprintf(stderr, "Filters: %d good, %d mediocre\n", - good_filters, mediocre_filters); + fprintf(stderr, "Filters: %d good, %d mediocre\n", good_filters, + mediocre_filters); } - ASSERT_LE(mediocre_filters, good_filters/5); + ASSERT_LE(mediocre_filters, good_filters / 5); } // Different bits-per-byte } // namespace leveldb -int main(int argc, char** argv) { - return leveldb::test::RunAllTests(); -} +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } diff --git a/src/leveldb/util/cache.cc b/src/leveldb/util/cache.cc index ce46886171..12de306cad 100644 --- a/src/leveldb/util/cache.cc +++ b/src/leveldb/util/cache.cc @@ -8,13 +8,13 @@ #include "leveldb/cache.h" #include "port/port.h" +#include "port/thread_annotations.h" #include "util/hash.h" #include "util/mutexlock.h" namespace leveldb { -Cache::~Cache() { -} +Cache::~Cache() {} namespace { @@ -45,21 +45,19 @@ struct LRUHandle { LRUHandle* next_hash; LRUHandle* next; LRUHandle* prev; - size_t charge; // TODO(opt): Only allow uint32_t? + size_t charge; // TODO(opt): Only allow uint32_t? size_t key_length; - bool in_cache; // Whether entry is in the cache. - uint32_t refs; // References, including cache reference, if present. - uint32_t hash; // Hash of key(); used for fast sharding and comparisons - char key_data[1]; // Beginning of key + bool in_cache; // Whether entry is in the cache. + uint32_t refs; // References, including cache reference, if present. + uint32_t hash; // Hash of key(); used for fast sharding and comparisons + char key_data[1]; // Beginning of key Slice key() const { - // For cheaper lookups, we allow a temporary Handle object - // to store a pointer to a key in "value". - if (next == this) { - return *(reinterpret_cast<Slice*>(value)); - } else { - return Slice(key_data, key_length); - } + // next_ is only equal to this if the LRU handle is the list head of an + // empty list. List heads never have meaningful keys. + assert(next != this); + + return Slice(key_data, key_length); } }; @@ -70,7 +68,7 @@ struct LRUHandle { // 4.4.3's builtin hashtable. class HandleTable { public: - HandleTable() : length_(0), elems_(0), list_(NULL) { Resize(); } + HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); } ~HandleTable() { delete[] list_; } LRUHandle* Lookup(const Slice& key, uint32_t hash) { @@ -80,9 +78,9 @@ class HandleTable { LRUHandle* Insert(LRUHandle* h) { LRUHandle** ptr = FindPointer(h->key(), h->hash); LRUHandle* old = *ptr; - h->next_hash = (old == NULL ? NULL : old->next_hash); + h->next_hash = (old == nullptr ? nullptr : old->next_hash); *ptr = h; - if (old == NULL) { + if (old == nullptr) { ++elems_; if (elems_ > length_) { // Since each cache entry is fairly large, we aim for a small @@ -96,7 +94,7 @@ class HandleTable { LRUHandle* Remove(const Slice& key, uint32_t hash) { LRUHandle** ptr = FindPointer(key, hash); LRUHandle* result = *ptr; - if (result != NULL) { + if (result != nullptr) { *ptr = result->next_hash; --elems_; } @@ -115,8 +113,7 @@ class HandleTable { // pointer to the trailing slot in the corresponding linked list. LRUHandle** FindPointer(const Slice& key, uint32_t hash) { LRUHandle** ptr = &list_[hash & (length_ - 1)]; - while (*ptr != NULL && - ((*ptr)->hash != hash || key != (*ptr)->key())) { + while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) { ptr = &(*ptr)->next_hash; } return ptr; @@ -132,7 +129,7 @@ class HandleTable { uint32_t count = 0; for (uint32_t i = 0; i < length_; i++) { LRUHandle* h = list_[i]; - while (h != NULL) { + while (h != nullptr) { LRUHandle* next = h->next_hash; uint32_t hash = h->hash; LRUHandle** ptr = &new_list[hash & (new_length - 1)]; @@ -159,8 +156,8 @@ class LRUCache { void SetCapacity(size_t capacity) { capacity_ = capacity; } // Like Cache methods, but with an extra "hash" parameter. - Cache::Handle* Insert(const Slice& key, uint32_t hash, - void* value, size_t charge, + Cache::Handle* Insert(const Slice& key, uint32_t hash, void* value, + size_t charge, void (*deleter)(const Slice& key, void* value)); Cache::Handle* Lookup(const Slice& key, uint32_t hash); void Release(Cache::Handle* handle); @@ -173,32 +170,31 @@ class LRUCache { private: void LRU_Remove(LRUHandle* e); - void LRU_Append(LRUHandle*list, LRUHandle* e); + void LRU_Append(LRUHandle* list, LRUHandle* e); void Ref(LRUHandle* e); void Unref(LRUHandle* e); - bool FinishErase(LRUHandle* e); + bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_); // Initialized before use. size_t capacity_; // mutex_ protects the following state. mutable port::Mutex mutex_; - size_t usage_; + size_t usage_ GUARDED_BY(mutex_); // Dummy head of LRU list. // lru.prev is newest entry, lru.next is oldest entry. // Entries have refs==1 and in_cache==true. - LRUHandle lru_; + LRUHandle lru_ GUARDED_BY(mutex_); // Dummy head of in-use list. // Entries are in use by clients, and have refs >= 2 and in_cache==true. - LRUHandle in_use_; + LRUHandle in_use_ GUARDED_BY(mutex_); - HandleTable table_; + HandleTable table_ GUARDED_BY(mutex_); }; -LRUCache::LRUCache() - : usage_(0) { +LRUCache::LRUCache() : capacity_(0), usage_(0) { // Make empty circular linked lists. lru_.next = &lru_; lru_.prev = &lru_; @@ -208,7 +204,7 @@ LRUCache::LRUCache() LRUCache::~LRUCache() { assert(in_use_.next == &in_use_); // Error if caller has an unreleased handle - for (LRUHandle* e = lru_.next; e != &lru_; ) { + for (LRUHandle* e = lru_.next; e != &lru_;) { LRUHandle* next = e->next; assert(e->in_cache); e->in_cache = false; @@ -229,11 +225,12 @@ void LRUCache::Ref(LRUHandle* e) { void LRUCache::Unref(LRUHandle* e) { assert(e->refs > 0); e->refs--; - if (e->refs == 0) { // Deallocate. + if (e->refs == 0) { // Deallocate. assert(!e->in_cache); (*e->deleter)(e->key(), e->value); free(e); - } else if (e->in_cache && e->refs == 1) { // No longer in use; move to lru_ list. + } else if (e->in_cache && e->refs == 1) { + // No longer in use; move to lru_ list. LRU_Remove(e); LRU_Append(&lru_, e); } @@ -255,7 +252,7 @@ void LRUCache::LRU_Append(LRUHandle* list, LRUHandle* e) { Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) { MutexLock l(&mutex_); LRUHandle* e = table_.Lookup(key, hash); - if (e != NULL) { + if (e != nullptr) { Ref(e); } return reinterpret_cast<Cache::Handle*>(e); @@ -266,13 +263,14 @@ void LRUCache::Release(Cache::Handle* handle) { Unref(reinterpret_cast<LRUHandle*>(handle)); } -Cache::Handle* LRUCache::Insert( - const Slice& key, uint32_t hash, void* value, size_t charge, - void (*deleter)(const Slice& key, void* value)) { +Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value, + size_t charge, + void (*deleter)(const Slice& key, + void* value)) { MutexLock l(&mutex_); - LRUHandle* e = reinterpret_cast<LRUHandle*>( - malloc(sizeof(LRUHandle)-1 + key.size())); + LRUHandle* e = + reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size())); e->value = value; e->deleter = deleter; e->charge = charge; @@ -288,8 +286,10 @@ Cache::Handle* LRUCache::Insert( LRU_Append(&in_use_, e); usage_ += charge; FinishErase(table_.Insert(e)); - } // else don't cache. (Tests use capacity_==0 to turn off caching.) - + } else { // don't cache. (capacity_==0 is supported and turns off caching.) + // next is read by key() in an assert, so it must be initialized + e->next = nullptr; + } while (usage_ > capacity_ && lru_.next != &lru_) { LRUHandle* old = lru_.next; assert(old->refs == 1); @@ -302,17 +302,17 @@ Cache::Handle* LRUCache::Insert( return reinterpret_cast<Cache::Handle*>(e); } -// If e != NULL, finish removing *e from the cache; it has already been removed -// from the hash table. Return whether e != NULL. Requires mutex_ held. +// If e != nullptr, finish removing *e from the cache; it has already been +// removed from the hash table. Return whether e != nullptr. bool LRUCache::FinishErase(LRUHandle* e) { - if (e != NULL) { + if (e != nullptr) { assert(e->in_cache); LRU_Remove(e); e->in_cache = false; usage_ -= e->charge; Unref(e); } - return e != NULL; + return e != nullptr; } void LRUCache::Erase(const Slice& key, uint32_t hash) { @@ -345,49 +345,46 @@ class ShardedLRUCache : public Cache { return Hash(s.data(), s.size(), 0); } - static uint32_t Shard(uint32_t hash) { - return hash >> (32 - kNumShardBits); - } + static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); } public: - explicit ShardedLRUCache(size_t capacity) - : last_id_(0) { + explicit ShardedLRUCache(size_t capacity) : last_id_(0) { const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards; for (int s = 0; s < kNumShards; s++) { shard_[s].SetCapacity(per_shard); } } - virtual ~ShardedLRUCache() { } - virtual Handle* Insert(const Slice& key, void* value, size_t charge, - void (*deleter)(const Slice& key, void* value)) { + ~ShardedLRUCache() override {} + Handle* Insert(const Slice& key, void* value, size_t charge, + void (*deleter)(const Slice& key, void* value)) override { const uint32_t hash = HashSlice(key); return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter); } - virtual Handle* Lookup(const Slice& key) { + Handle* Lookup(const Slice& key) override { const uint32_t hash = HashSlice(key); return shard_[Shard(hash)].Lookup(key, hash); } - virtual void Release(Handle* handle) { + void Release(Handle* handle) override { LRUHandle* h = reinterpret_cast<LRUHandle*>(handle); shard_[Shard(h->hash)].Release(handle); } - virtual void Erase(const Slice& key) { + void Erase(const Slice& key) override { const uint32_t hash = HashSlice(key); shard_[Shard(hash)].Erase(key, hash); } - virtual void* Value(Handle* handle) { + void* Value(Handle* handle) override { return reinterpret_cast<LRUHandle*>(handle)->value; } - virtual uint64_t NewId() { + uint64_t NewId() override { MutexLock l(&id_mutex_); return ++(last_id_); } - virtual void Prune() { + void Prune() override { for (int s = 0; s < kNumShards; s++) { shard_[s].Prune(); } } - virtual size_t TotalCharge() const { + size_t TotalCharge() const override { size_t total = 0; for (int s = 0; s < kNumShards; s++) { total += shard_[s].TotalCharge(); @@ -398,8 +395,6 @@ class ShardedLRUCache : public Cache { } // end anonymous namespace -Cache* NewLRUCache(size_t capacity) { - return new ShardedLRUCache(capacity); -} +Cache* NewLRUCache(size_t capacity) { return new ShardedLRUCache(capacity); } } // namespace leveldb diff --git a/src/leveldb/util/cache_test.cc b/src/leveldb/util/cache_test.cc index 468f7a6425..974334b9f8 100644 --- a/src/leveldb/util/cache_test.cc +++ b/src/leveldb/util/cache_test.cc @@ -25,8 +25,6 @@ static int DecodeValue(void* v) { return reinterpret_cast<uintptr_t>(v); } class CacheTest { public: - static CacheTest* current_; - static void Deleter(const Slice& key, void* v) { current_->deleted_keys_.push_back(DecodeKey(key)); current_->deleted_values_.push_back(DecodeValue(v)); @@ -37,18 +35,14 @@ class CacheTest { std::vector<int> deleted_values_; Cache* cache_; - CacheTest() : cache_(NewLRUCache(kCacheSize)) { - current_ = this; - } + CacheTest() : cache_(NewLRUCache(kCacheSize)) { current_ = this; } - ~CacheTest() { - delete cache_; - } + ~CacheTest() { delete cache_; } int Lookup(int key) { Cache::Handle* handle = cache_->Lookup(EncodeKey(key)); - const int r = (handle == NULL) ? -1 : DecodeValue(cache_->Value(handle)); - if (handle != NULL) { + const int r = (handle == nullptr) ? -1 : DecodeValue(cache_->Value(handle)); + if (handle != nullptr) { cache_->Release(handle); } return r; @@ -64,9 +58,9 @@ class CacheTest { &CacheTest::Deleter); } - void Erase(int key) { - cache_->Erase(EncodeKey(key)); - } + void Erase(int key) { cache_->Erase(EncodeKey(key)); } + + static CacheTest* current_; }; CacheTest* CacheTest::current_; @@ -75,18 +69,18 @@ TEST(CacheTest, HitAndMiss) { Insert(100, 101); ASSERT_EQ(101, Lookup(100)); - ASSERT_EQ(-1, Lookup(200)); - ASSERT_EQ(-1, Lookup(300)); + ASSERT_EQ(-1, Lookup(200)); + ASSERT_EQ(-1, Lookup(300)); Insert(200, 201); ASSERT_EQ(101, Lookup(100)); ASSERT_EQ(201, Lookup(200)); - ASSERT_EQ(-1, Lookup(300)); + ASSERT_EQ(-1, Lookup(300)); Insert(100, 102); ASSERT_EQ(102, Lookup(100)); ASSERT_EQ(201, Lookup(200)); - ASSERT_EQ(-1, Lookup(300)); + ASSERT_EQ(-1, Lookup(300)); ASSERT_EQ(1, deleted_keys_.size()); ASSERT_EQ(100, deleted_keys_[0]); @@ -100,14 +94,14 @@ TEST(CacheTest, Erase) { Insert(100, 101); Insert(200, 201); Erase(100); - ASSERT_EQ(-1, Lookup(100)); + ASSERT_EQ(-1, Lookup(100)); ASSERT_EQ(201, Lookup(200)); ASSERT_EQ(1, deleted_keys_.size()); ASSERT_EQ(100, deleted_keys_[0]); ASSERT_EQ(101, deleted_values_[0]); Erase(100); - ASSERT_EQ(-1, Lookup(100)); + ASSERT_EQ(-1, Lookup(100)); ASSERT_EQ(201, Lookup(200)); ASSERT_EQ(1, deleted_keys_.size()); } @@ -146,8 +140,8 @@ TEST(CacheTest, EvictionPolicy) { // Frequently used entry must be kept around, // as must things that are still in use. for (int i = 0; i < kCacheSize + 100; i++) { - Insert(1000+i, 2000+i); - ASSERT_EQ(2000+i, Lookup(1000+i)); + Insert(1000 + i, 2000 + i); + ASSERT_EQ(2000 + i, Lookup(1000 + i)); ASSERT_EQ(101, Lookup(100)); } ASSERT_EQ(101, Lookup(100)); @@ -160,12 +154,12 @@ TEST(CacheTest, UseExceedsCacheSize) { // Overfill the cache, keeping handles on all inserted entries. std::vector<Cache::Handle*> h; for (int i = 0; i < kCacheSize + 100; i++) { - h.push_back(InsertAndReturnHandle(1000+i, 2000+i)); + h.push_back(InsertAndReturnHandle(1000 + i, 2000 + i)); } // Check that all the entries can be found in the cache. for (int i = 0; i < h.size(); i++) { - ASSERT_EQ(2000+i, Lookup(1000+i)); + ASSERT_EQ(2000 + i, Lookup(1000 + i)); } for (int i = 0; i < h.size(); i++) { @@ -181,9 +175,9 @@ TEST(CacheTest, HeavyEntries) { const int kHeavy = 10; int added = 0; int index = 0; - while (added < 2*kCacheSize) { + while (added < 2 * kCacheSize) { const int weight = (index & 1) ? kLight : kHeavy; - Insert(index, 1000+index, weight); + Insert(index, 1000 + index, weight); added += weight; index++; } @@ -194,10 +188,10 @@ TEST(CacheTest, HeavyEntries) { int r = Lookup(i); if (r >= 0) { cached_weight += weight; - ASSERT_EQ(1000+i, r); + ASSERT_EQ(1000 + i, r); } } - ASSERT_LE(cached_weight, kCacheSize + kCacheSize/10); + ASSERT_LE(cached_weight, kCacheSize + kCacheSize / 10); } TEST(CacheTest, NewId) { @@ -219,8 +213,14 @@ TEST(CacheTest, Prune) { ASSERT_EQ(-1, Lookup(2)); } -} // namespace leveldb +TEST(CacheTest, ZeroSizeCache) { + delete cache_; + cache_ = NewLRUCache(0); -int main(int argc, char** argv) { - return leveldb::test::RunAllTests(); + Insert(1, 100); + ASSERT_EQ(-1, Lookup(1)); } + +} // namespace leveldb + +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } diff --git a/src/leveldb/util/coding.cc b/src/leveldb/util/coding.cc index 21e3186d5d..df3fa10f0d 100644 --- a/src/leveldb/util/coding.cc +++ b/src/leveldb/util/coding.cc @@ -6,32 +6,6 @@ namespace leveldb { -void EncodeFixed32(char* buf, uint32_t value) { - if (port::kLittleEndian) { - memcpy(buf, &value, sizeof(value)); - } else { - buf[0] = value & 0xff; - buf[1] = (value >> 8) & 0xff; - buf[2] = (value >> 16) & 0xff; - buf[3] = (value >> 24) & 0xff; - } -} - -void EncodeFixed64(char* buf, uint64_t value) { - if (port::kLittleEndian) { - memcpy(buf, &value, sizeof(value)); - } else { - buf[0] = value & 0xff; - buf[1] = (value >> 8) & 0xff; - buf[2] = (value >> 16) & 0xff; - buf[3] = (value >> 24) & 0xff; - buf[4] = (value >> 32) & 0xff; - buf[5] = (value >> 40) & 0xff; - buf[6] = (value >> 48) & 0xff; - buf[7] = (value >> 56) & 0xff; - } -} - void PutFixed32(std::string* dst, uint32_t value) { char buf[sizeof(value)]; EncodeFixed32(buf, value); @@ -46,28 +20,28 @@ void PutFixed64(std::string* dst, uint64_t value) { char* EncodeVarint32(char* dst, uint32_t v) { // Operate on characters as unsigneds - unsigned char* ptr = reinterpret_cast<unsigned char*>(dst); + uint8_t* ptr = reinterpret_cast<uint8_t*>(dst); static const int B = 128; - if (v < (1<<7)) { + if (v < (1 << 7)) { *(ptr++) = v; - } else if (v < (1<<14)) { + } else if (v < (1 << 14)) { *(ptr++) = v | B; - *(ptr++) = v>>7; - } else if (v < (1<<21)) { + *(ptr++) = v >> 7; + } else if (v < (1 << 21)) { *(ptr++) = v | B; - *(ptr++) = (v>>7) | B; - *(ptr++) = v>>14; - } else if (v < (1<<28)) { + *(ptr++) = (v >> 7) | B; + *(ptr++) = v >> 14; + } else if (v < (1 << 28)) { *(ptr++) = v | B; - *(ptr++) = (v>>7) | B; - *(ptr++) = (v>>14) | B; - *(ptr++) = v>>21; + *(ptr++) = (v >> 7) | B; + *(ptr++) = (v >> 14) | B; + *(ptr++) = v >> 21; } else { *(ptr++) = v | B; - *(ptr++) = (v>>7) | B; - *(ptr++) = (v>>14) | B; - *(ptr++) = (v>>21) | B; - *(ptr++) = v>>28; + *(ptr++) = (v >> 7) | B; + *(ptr++) = (v >> 14) | B; + *(ptr++) = (v >> 21) | B; + *(ptr++) = v >> 28; } return reinterpret_cast<char*>(ptr); } @@ -80,12 +54,12 @@ void PutVarint32(std::string* dst, uint32_t v) { char* EncodeVarint64(char* dst, uint64_t v) { static const int B = 128; - unsigned char* ptr = reinterpret_cast<unsigned char*>(dst); + uint8_t* ptr = reinterpret_cast<uint8_t*>(dst); while (v >= B) { - *(ptr++) = (v & (B-1)) | B; + *(ptr++) = v | B; v >>= 7; } - *(ptr++) = static_cast<unsigned char>(v); + *(ptr++) = static_cast<uint8_t>(v); return reinterpret_cast<char*>(ptr); } @@ -109,12 +83,11 @@ int VarintLength(uint64_t v) { return len; } -const char* GetVarint32PtrFallback(const char* p, - const char* limit, +const char* GetVarint32PtrFallback(const char* p, const char* limit, uint32_t* value) { uint32_t result = 0; for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) { - uint32_t byte = *(reinterpret_cast<const unsigned char*>(p)); + uint32_t byte = *(reinterpret_cast<const uint8_t*>(p)); p++; if (byte & 128) { // More bytes are present @@ -125,14 +98,14 @@ const char* GetVarint32PtrFallback(const char* p, return reinterpret_cast<const char*>(p); } } - return NULL; + return nullptr; } bool GetVarint32(Slice* input, uint32_t* value) { const char* p = input->data(); const char* limit = p + input->size(); const char* q = GetVarint32Ptr(p, limit, value); - if (q == NULL) { + if (q == nullptr) { return false; } else { *input = Slice(q, limit - q); @@ -143,7 +116,7 @@ bool GetVarint32(Slice* input, uint32_t* value) { const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* value) { uint64_t result = 0; for (uint32_t shift = 0; shift <= 63 && p < limit; shift += 7) { - uint64_t byte = *(reinterpret_cast<const unsigned char*>(p)); + uint64_t byte = *(reinterpret_cast<const uint8_t*>(p)); p++; if (byte & 128) { // More bytes are present @@ -154,14 +127,14 @@ const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* value) { return reinterpret_cast<const char*>(p); } } - return NULL; + return nullptr; } bool GetVarint64(Slice* input, uint64_t* value) { const char* p = input->data(); const char* limit = p + input->size(); const char* q = GetVarint64Ptr(p, limit, value); - if (q == NULL) { + if (q == nullptr) { return false; } else { *input = Slice(q, limit - q); @@ -173,16 +146,15 @@ const char* GetLengthPrefixedSlice(const char* p, const char* limit, Slice* result) { uint32_t len; p = GetVarint32Ptr(p, limit, &len); - if (p == NULL) return NULL; - if (p + len > limit) return NULL; + if (p == nullptr) return nullptr; + if (p + len > limit) return nullptr; *result = Slice(p, len); return p + len; } bool GetLengthPrefixedSlice(Slice* input, Slice* result) { uint32_t len; - if (GetVarint32(input, &len) && - input->size() >= len) { + if (GetVarint32(input, &len) && input->size() >= len) { *result = Slice(input->data(), len); input->remove_prefix(len); return true; diff --git a/src/leveldb/util/coding.h b/src/leveldb/util/coding.h index 3993c4a755..1983ae7173 100644 --- a/src/leveldb/util/coding.h +++ b/src/leveldb/util/coding.h @@ -10,87 +10,147 @@ #ifndef STORAGE_LEVELDB_UTIL_CODING_H_ #define STORAGE_LEVELDB_UTIL_CODING_H_ -#include <stdint.h> -#include <string.h> +#include <cstdint> +#include <cstring> #include <string> + #include "leveldb/slice.h" #include "port/port.h" namespace leveldb { // Standard Put... routines append to a string -extern void PutFixed32(std::string* dst, uint32_t value); -extern void PutFixed64(std::string* dst, uint64_t value); -extern void PutVarint32(std::string* dst, uint32_t value); -extern void PutVarint64(std::string* dst, uint64_t value); -extern void PutLengthPrefixedSlice(std::string* dst, const Slice& value); +void PutFixed32(std::string* dst, uint32_t value); +void PutFixed64(std::string* dst, uint64_t value); +void PutVarint32(std::string* dst, uint32_t value); +void PutVarint64(std::string* dst, uint64_t value); +void PutLengthPrefixedSlice(std::string* dst, const Slice& value); // Standard Get... routines parse a value from the beginning of a Slice // and advance the slice past the parsed value. -extern bool GetVarint32(Slice* input, uint32_t* value); -extern bool GetVarint64(Slice* input, uint64_t* value); -extern bool GetLengthPrefixedSlice(Slice* input, Slice* result); +bool GetVarint32(Slice* input, uint32_t* value); +bool GetVarint64(Slice* input, uint64_t* value); +bool GetLengthPrefixedSlice(Slice* input, Slice* result); // Pointer-based variants of GetVarint... These either store a value // in *v and return a pointer just past the parsed value, or return -// NULL on error. These routines only look at bytes in the range +// nullptr on error. These routines only look at bytes in the range // [p..limit-1] -extern const char* GetVarint32Ptr(const char* p,const char* limit, uint32_t* v); -extern const char* GetVarint64Ptr(const char* p,const char* limit, uint64_t* v); +const char* GetVarint32Ptr(const char* p, const char* limit, uint32_t* v); +const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* v); // Returns the length of the varint32 or varint64 encoding of "v" -extern int VarintLength(uint64_t v); +int VarintLength(uint64_t v); // Lower-level versions of Put... that write directly into a character buffer +// and return a pointer just past the last byte written. // REQUIRES: dst has enough space for the value being written -extern void EncodeFixed32(char* dst, uint32_t value); -extern void EncodeFixed64(char* dst, uint64_t value); +char* EncodeVarint32(char* dst, uint32_t value); +char* EncodeVarint64(char* dst, uint64_t value); + +// TODO(costan): Remove port::kLittleEndian and the fast paths based on +// std::memcpy when clang learns to optimize the generic code, as +// described in https://bugs.llvm.org/show_bug.cgi?id=41761 +// +// The platform-independent code in DecodeFixed{32,64}() gets optimized to mov +// on x86 and ldr on ARM64, by both clang and gcc. However, only gcc optimizes +// the platform-independent code in EncodeFixed{32,64}() to mov / str. // Lower-level versions of Put... that write directly into a character buffer -// and return a pointer just past the last byte written. // REQUIRES: dst has enough space for the value being written -extern char* EncodeVarint32(char* dst, uint32_t value); -extern char* EncodeVarint64(char* dst, uint64_t value); + +inline void EncodeFixed32(char* dst, uint32_t value) { + uint8_t* const buffer = reinterpret_cast<uint8_t*>(dst); + + if (port::kLittleEndian) { + // Fast path for little-endian CPUs. All major compilers optimize this to a + // single mov (x86_64) / str (ARM) instruction. + std::memcpy(buffer, &value, sizeof(uint32_t)); + return; + } + + // Platform-independent code. + // Currently, only gcc optimizes this to a single mov / str instruction. + buffer[0] = static_cast<uint8_t>(value); + buffer[1] = static_cast<uint8_t>(value >> 8); + buffer[2] = static_cast<uint8_t>(value >> 16); + buffer[3] = static_cast<uint8_t>(value >> 24); +} + +inline void EncodeFixed64(char* dst, uint64_t value) { + uint8_t* const buffer = reinterpret_cast<uint8_t*>(dst); + + if (port::kLittleEndian) { + // Fast path for little-endian CPUs. All major compilers optimize this to a + // single mov (x86_64) / str (ARM) instruction. + std::memcpy(buffer, &value, sizeof(uint64_t)); + return; + } + + // Platform-independent code. + // Currently, only gcc optimizes this to a single mov / str instruction. + buffer[0] = static_cast<uint8_t>(value); + buffer[1] = static_cast<uint8_t>(value >> 8); + buffer[2] = static_cast<uint8_t>(value >> 16); + buffer[3] = static_cast<uint8_t>(value >> 24); + buffer[4] = static_cast<uint8_t>(value >> 32); + buffer[5] = static_cast<uint8_t>(value >> 40); + buffer[6] = static_cast<uint8_t>(value >> 48); + buffer[7] = static_cast<uint8_t>(value >> 56); +} // Lower-level versions of Get... that read directly from a character buffer // without any bounds checking. inline uint32_t DecodeFixed32(const char* ptr) { + const uint8_t* const buffer = reinterpret_cast<const uint8_t*>(ptr); + if (port::kLittleEndian) { - // Load the raw bytes + // Fast path for little-endian CPUs. All major compilers optimize this to a + // single mov (x86_64) / ldr (ARM) instruction. uint32_t result; - memcpy(&result, ptr, sizeof(result)); // gcc optimizes this to a plain load + std::memcpy(&result, buffer, sizeof(uint32_t)); return result; - } else { - return ((static_cast<uint32_t>(static_cast<unsigned char>(ptr[0]))) - | (static_cast<uint32_t>(static_cast<unsigned char>(ptr[1])) << 8) - | (static_cast<uint32_t>(static_cast<unsigned char>(ptr[2])) << 16) - | (static_cast<uint32_t>(static_cast<unsigned char>(ptr[3])) << 24)); } + + // Platform-independent code. + // Clang and gcc optimize this to a single mov / ldr instruction. + return (static_cast<uint32_t>(buffer[0])) | + (static_cast<uint32_t>(buffer[1]) << 8) | + (static_cast<uint32_t>(buffer[2]) << 16) | + (static_cast<uint32_t>(buffer[3]) << 24); } inline uint64_t DecodeFixed64(const char* ptr) { + const uint8_t* const buffer = reinterpret_cast<const uint8_t*>(ptr); + if (port::kLittleEndian) { - // Load the raw bytes + // Fast path for little-endian CPUs. All major compilers optimize this to a + // single mov (x86_64) / ldr (ARM) instruction. uint64_t result; - memcpy(&result, ptr, sizeof(result)); // gcc optimizes this to a plain load + std::memcpy(&result, buffer, sizeof(uint64_t)); return result; - } else { - uint64_t lo = DecodeFixed32(ptr); - uint64_t hi = DecodeFixed32(ptr + 4); - return (hi << 32) | lo; } + + // Platform-independent code. + // Clang and gcc optimize this to a single mov / ldr instruction. + return (static_cast<uint64_t>(buffer[0])) | + (static_cast<uint64_t>(buffer[1]) << 8) | + (static_cast<uint64_t>(buffer[2]) << 16) | + (static_cast<uint64_t>(buffer[3]) << 24) | + (static_cast<uint64_t>(buffer[4]) << 32) | + (static_cast<uint64_t>(buffer[5]) << 40) | + (static_cast<uint64_t>(buffer[6]) << 48) | + (static_cast<uint64_t>(buffer[7]) << 56); } // Internal routine for use by fallback path of GetVarint32Ptr -extern const char* GetVarint32PtrFallback(const char* p, - const char* limit, - uint32_t* value); -inline const char* GetVarint32Ptr(const char* p, - const char* limit, +const char* GetVarint32PtrFallback(const char* p, const char* limit, + uint32_t* value); +inline const char* GetVarint32Ptr(const char* p, const char* limit, uint32_t* value) { if (p < limit) { - uint32_t result = *(reinterpret_cast<const unsigned char*>(p)); + uint32_t result = *(reinterpret_cast<const uint8_t*>(p)); if ((result & 128) == 0) { *value = result; return p + 1; diff --git a/src/leveldb/util/coding_test.cc b/src/leveldb/util/coding_test.cc index 521541ea61..0d2a0c51f6 100644 --- a/src/leveldb/util/coding_test.cc +++ b/src/leveldb/util/coding_test.cc @@ -2,13 +2,14 @@ // 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/coding.h" +#include <vector> +#include "util/coding.h" #include "util/testharness.h" namespace leveldb { -class Coding { }; +class Coding {}; TEST(Coding, Fixed32) { std::string s; @@ -38,15 +39,15 @@ TEST(Coding, Fixed64) { uint64_t v = static_cast<uint64_t>(1) << power; uint64_t actual; actual = DecodeFixed64(p); - ASSERT_EQ(v-1, actual); + ASSERT_EQ(v - 1, actual); p += sizeof(uint64_t); actual = DecodeFixed64(p); - ASSERT_EQ(v+0, actual); + ASSERT_EQ(v + 0, actual); p += sizeof(uint64_t); actual = DecodeFixed64(p); - ASSERT_EQ(v+1, actual); + ASSERT_EQ(v + 1, actual); p += sizeof(uint64_t); } } @@ -88,7 +89,7 @@ TEST(Coding, Varint32) { uint32_t actual; const char* start = p; p = GetVarint32Ptr(p, limit, &actual); - ASSERT_TRUE(p != NULL); + ASSERT_TRUE(p != nullptr); ASSERT_EQ(expected, actual); ASSERT_EQ(VarintLength(actual), p - start); } @@ -107,8 +108,8 @@ TEST(Coding, Varint64) { // Test values near powers of two const uint64_t power = 1ull << k; values.push_back(power); - values.push_back(power-1); - values.push_back(power+1); + values.push_back(power - 1); + values.push_back(power + 1); } std::string s; @@ -123,19 +124,18 @@ TEST(Coding, Varint64) { uint64_t actual; const char* start = p; p = GetVarint64Ptr(p, limit, &actual); - ASSERT_TRUE(p != NULL); + ASSERT_TRUE(p != nullptr); ASSERT_EQ(values[i], actual); ASSERT_EQ(VarintLength(actual), p - start); } ASSERT_EQ(p, limit); - } TEST(Coding, Varint32Overflow) { uint32_t result; std::string input("\x81\x82\x83\x84\x85\x11"); - ASSERT_TRUE(GetVarint32Ptr(input.data(), input.data() + input.size(), &result) - == NULL); + ASSERT_TRUE(GetVarint32Ptr(input.data(), input.data() + input.size(), + &result) == nullptr); } TEST(Coding, Varint32Truncation) { @@ -144,17 +144,18 @@ TEST(Coding, Varint32Truncation) { PutVarint32(&s, large_value); uint32_t result; for (size_t len = 0; len < s.size() - 1; len++) { - ASSERT_TRUE(GetVarint32Ptr(s.data(), s.data() + len, &result) == NULL); + ASSERT_TRUE(GetVarint32Ptr(s.data(), s.data() + len, &result) == nullptr); } - ASSERT_TRUE(GetVarint32Ptr(s.data(), s.data() + s.size(), &result) != NULL); + ASSERT_TRUE(GetVarint32Ptr(s.data(), s.data() + s.size(), &result) != + nullptr); ASSERT_EQ(large_value, result); } TEST(Coding, Varint64Overflow) { uint64_t result; std::string input("\x81\x82\x83\x84\x85\x81\x82\x83\x84\x85\x11"); - ASSERT_TRUE(GetVarint64Ptr(input.data(), input.data() + input.size(), &result) - == NULL); + ASSERT_TRUE(GetVarint64Ptr(input.data(), input.data() + input.size(), + &result) == nullptr); } TEST(Coding, Varint64Truncation) { @@ -163,9 +164,10 @@ TEST(Coding, Varint64Truncation) { PutVarint64(&s, large_value); uint64_t result; for (size_t len = 0; len < s.size() - 1; len++) { - ASSERT_TRUE(GetVarint64Ptr(s.data(), s.data() + len, &result) == NULL); + ASSERT_TRUE(GetVarint64Ptr(s.data(), s.data() + len, &result) == nullptr); } - ASSERT_TRUE(GetVarint64Ptr(s.data(), s.data() + s.size(), &result) != NULL); + ASSERT_TRUE(GetVarint64Ptr(s.data(), s.data() + s.size(), &result) != + nullptr); ASSERT_EQ(large_value, result); } @@ -191,6 +193,4 @@ TEST(Coding, Strings) { } // namespace leveldb -int main(int argc, char** argv) { - return leveldb::test::RunAllTests(); -} +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } diff --git a/src/leveldb/util/comparator.cc b/src/leveldb/util/comparator.cc index 4b7b5724ef..c5766e9462 100644 --- a/src/leveldb/util/comparator.cc +++ b/src/leveldb/util/comparator.cc @@ -2,33 +2,34 @@ // 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 <algorithm> -#include <stdint.h> #include "leveldb/comparator.h" + +#include <algorithm> +#include <cstdint> +#include <string> +#include <type_traits> + #include "leveldb/slice.h" -#include "port/port.h" #include "util/logging.h" +#include "util/no_destructor.h" namespace leveldb { -Comparator::~Comparator() { } +Comparator::~Comparator() = default; namespace { class BytewiseComparatorImpl : public Comparator { public: - BytewiseComparatorImpl() { } + BytewiseComparatorImpl() = default; - virtual const char* Name() const { - return "leveldb.BytewiseComparator"; - } + const char* Name() const override { return "leveldb.BytewiseComparator"; } - virtual int Compare(const Slice& a, const Slice& b) const { + int Compare(const Slice& a, const Slice& b) const override { return a.compare(b); } - virtual void FindShortestSeparator( - std::string* start, - const Slice& limit) const { + void FindShortestSeparator(std::string* start, + const Slice& limit) const override { // Find length of common prefix size_t min_length = std::min(start->size(), limit.size()); size_t diff_index = 0; @@ -50,14 +51,14 @@ class BytewiseComparatorImpl : public Comparator { } } - virtual void FindShortSuccessor(std::string* key) const { + void FindShortSuccessor(std::string* key) const override { // Find first character that can be incremented size_t n = key->size(); for (size_t i = 0; i < n; i++) { const uint8_t byte = (*key)[i]; if (byte != static_cast<uint8_t>(0xff)) { (*key)[i] = byte + 1; - key->resize(i+1); + key->resize(i + 1); return; } } @@ -66,16 +67,9 @@ class BytewiseComparatorImpl : public Comparator { }; } // namespace -static port::OnceType once = LEVELDB_ONCE_INIT; -static const Comparator* bytewise; - -static void InitModule() { - bytewise = new BytewiseComparatorImpl; -} - const Comparator* BytewiseComparator() { - port::InitOnce(&once, InitModule); - return bytewise; + static NoDestructor<BytewiseComparatorImpl> singleton; + return singleton.get(); } } // namespace leveldb diff --git a/src/leveldb/util/crc32c.cc b/src/leveldb/util/crc32c.cc index b3f40eeeed..c2e61f7dba 100644 --- a/src/leveldb/util/crc32c.cc +++ b/src/leveldb/util/crc32c.cc @@ -2,11 +2,11 @@ // 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. // -// A portable implementation of crc32c, optimized to handle -// four bytes at a time. +// A portable implementation of crc32c. #include "util/crc32c.h" +#include <stddef.h> #include <stdint.h> #include "port/port.h" @@ -15,283 +15,256 @@ namespace leveldb { namespace crc32c { -static const uint32_t table0_[256] = { - 0x00000000, 0xf26b8303, 0xe13b70f7, 0x1350f3f4, - 0xc79a971f, 0x35f1141c, 0x26a1e7e8, 0xd4ca64eb, - 0x8ad958cf, 0x78b2dbcc, 0x6be22838, 0x9989ab3b, - 0x4d43cfd0, 0xbf284cd3, 0xac78bf27, 0x5e133c24, - 0x105ec76f, 0xe235446c, 0xf165b798, 0x030e349b, - 0xd7c45070, 0x25afd373, 0x36ff2087, 0xc494a384, - 0x9a879fa0, 0x68ec1ca3, 0x7bbcef57, 0x89d76c54, - 0x5d1d08bf, 0xaf768bbc, 0xbc267848, 0x4e4dfb4b, - 0x20bd8ede, 0xd2d60ddd, 0xc186fe29, 0x33ed7d2a, - 0xe72719c1, 0x154c9ac2, 0x061c6936, 0xf477ea35, - 0xaa64d611, 0x580f5512, 0x4b5fa6e6, 0xb93425e5, - 0x6dfe410e, 0x9f95c20d, 0x8cc531f9, 0x7eaeb2fa, - 0x30e349b1, 0xc288cab2, 0xd1d83946, 0x23b3ba45, - 0xf779deae, 0x05125dad, 0x1642ae59, 0xe4292d5a, - 0xba3a117e, 0x4851927d, 0x5b016189, 0xa96ae28a, - 0x7da08661, 0x8fcb0562, 0x9c9bf696, 0x6ef07595, - 0x417b1dbc, 0xb3109ebf, 0xa0406d4b, 0x522bee48, - 0x86e18aa3, 0x748a09a0, 0x67dafa54, 0x95b17957, - 0xcba24573, 0x39c9c670, 0x2a993584, 0xd8f2b687, - 0x0c38d26c, 0xfe53516f, 0xed03a29b, 0x1f682198, - 0x5125dad3, 0xa34e59d0, 0xb01eaa24, 0x42752927, - 0x96bf4dcc, 0x64d4cecf, 0x77843d3b, 0x85efbe38, - 0xdbfc821c, 0x2997011f, 0x3ac7f2eb, 0xc8ac71e8, - 0x1c661503, 0xee0d9600, 0xfd5d65f4, 0x0f36e6f7, - 0x61c69362, 0x93ad1061, 0x80fde395, 0x72966096, - 0xa65c047d, 0x5437877e, 0x4767748a, 0xb50cf789, - 0xeb1fcbad, 0x197448ae, 0x0a24bb5a, 0xf84f3859, - 0x2c855cb2, 0xdeeedfb1, 0xcdbe2c45, 0x3fd5af46, - 0x7198540d, 0x83f3d70e, 0x90a324fa, 0x62c8a7f9, - 0xb602c312, 0x44694011, 0x5739b3e5, 0xa55230e6, - 0xfb410cc2, 0x092a8fc1, 0x1a7a7c35, 0xe811ff36, - 0x3cdb9bdd, 0xceb018de, 0xdde0eb2a, 0x2f8b6829, - 0x82f63b78, 0x709db87b, 0x63cd4b8f, 0x91a6c88c, - 0x456cac67, 0xb7072f64, 0xa457dc90, 0x563c5f93, - 0x082f63b7, 0xfa44e0b4, 0xe9141340, 0x1b7f9043, - 0xcfb5f4a8, 0x3dde77ab, 0x2e8e845f, 0xdce5075c, - 0x92a8fc17, 0x60c37f14, 0x73938ce0, 0x81f80fe3, - 0x55326b08, 0xa759e80b, 0xb4091bff, 0x466298fc, - 0x1871a4d8, 0xea1a27db, 0xf94ad42f, 0x0b21572c, - 0xdfeb33c7, 0x2d80b0c4, 0x3ed04330, 0xccbbc033, - 0xa24bb5a6, 0x502036a5, 0x4370c551, 0xb11b4652, - 0x65d122b9, 0x97baa1ba, 0x84ea524e, 0x7681d14d, - 0x2892ed69, 0xdaf96e6a, 0xc9a99d9e, 0x3bc21e9d, - 0xef087a76, 0x1d63f975, 0x0e330a81, 0xfc588982, - 0xb21572c9, 0x407ef1ca, 0x532e023e, 0xa145813d, - 0x758fe5d6, 0x87e466d5, 0x94b49521, 0x66df1622, - 0x38cc2a06, 0xcaa7a905, 0xd9f75af1, 0x2b9cd9f2, - 0xff56bd19, 0x0d3d3e1a, 0x1e6dcdee, 0xec064eed, - 0xc38d26c4, 0x31e6a5c7, 0x22b65633, 0xd0ddd530, - 0x0417b1db, 0xf67c32d8, 0xe52cc12c, 0x1747422f, - 0x49547e0b, 0xbb3ffd08, 0xa86f0efc, 0x5a048dff, - 0x8ecee914, 0x7ca56a17, 0x6ff599e3, 0x9d9e1ae0, - 0xd3d3e1ab, 0x21b862a8, 0x32e8915c, 0xc083125f, - 0x144976b4, 0xe622f5b7, 0xf5720643, 0x07198540, - 0x590ab964, 0xab613a67, 0xb831c993, 0x4a5a4a90, - 0x9e902e7b, 0x6cfbad78, 0x7fab5e8c, 0x8dc0dd8f, - 0xe330a81a, 0x115b2b19, 0x020bd8ed, 0xf0605bee, - 0x24aa3f05, 0xd6c1bc06, 0xc5914ff2, 0x37faccf1, - 0x69e9f0d5, 0x9b8273d6, 0x88d28022, 0x7ab90321, - 0xae7367ca, 0x5c18e4c9, 0x4f48173d, 0xbd23943e, - 0xf36e6f75, 0x0105ec76, 0x12551f82, 0xe03e9c81, - 0x34f4f86a, 0xc69f7b69, 0xd5cf889d, 0x27a40b9e, - 0x79b737ba, 0x8bdcb4b9, 0x988c474d, 0x6ae7c44e, - 0xbe2da0a5, 0x4c4623a6, 0x5f16d052, 0xad7d5351 -}; -static const uint32_t table1_[256] = { - 0x00000000, 0x13a29877, 0x274530ee, 0x34e7a899, - 0x4e8a61dc, 0x5d28f9ab, 0x69cf5132, 0x7a6dc945, - 0x9d14c3b8, 0x8eb65bcf, 0xba51f356, 0xa9f36b21, - 0xd39ea264, 0xc03c3a13, 0xf4db928a, 0xe7790afd, - 0x3fc5f181, 0x2c6769f6, 0x1880c16f, 0x0b225918, - 0x714f905d, 0x62ed082a, 0x560aa0b3, 0x45a838c4, - 0xa2d13239, 0xb173aa4e, 0x859402d7, 0x96369aa0, - 0xec5b53e5, 0xfff9cb92, 0xcb1e630b, 0xd8bcfb7c, - 0x7f8be302, 0x6c297b75, 0x58ced3ec, 0x4b6c4b9b, - 0x310182de, 0x22a31aa9, 0x1644b230, 0x05e62a47, - 0xe29f20ba, 0xf13db8cd, 0xc5da1054, 0xd6788823, - 0xac154166, 0xbfb7d911, 0x8b507188, 0x98f2e9ff, - 0x404e1283, 0x53ec8af4, 0x670b226d, 0x74a9ba1a, - 0x0ec4735f, 0x1d66eb28, 0x298143b1, 0x3a23dbc6, - 0xdd5ad13b, 0xcef8494c, 0xfa1fe1d5, 0xe9bd79a2, - 0x93d0b0e7, 0x80722890, 0xb4958009, 0xa737187e, - 0xff17c604, 0xecb55e73, 0xd852f6ea, 0xcbf06e9d, - 0xb19da7d8, 0xa23f3faf, 0x96d89736, 0x857a0f41, - 0x620305bc, 0x71a19dcb, 0x45463552, 0x56e4ad25, - 0x2c896460, 0x3f2bfc17, 0x0bcc548e, 0x186eccf9, - 0xc0d23785, 0xd370aff2, 0xe797076b, 0xf4359f1c, - 0x8e585659, 0x9dface2e, 0xa91d66b7, 0xbabffec0, - 0x5dc6f43d, 0x4e646c4a, 0x7a83c4d3, 0x69215ca4, - 0x134c95e1, 0x00ee0d96, 0x3409a50f, 0x27ab3d78, - 0x809c2506, 0x933ebd71, 0xa7d915e8, 0xb47b8d9f, - 0xce1644da, 0xddb4dcad, 0xe9537434, 0xfaf1ec43, - 0x1d88e6be, 0x0e2a7ec9, 0x3acdd650, 0x296f4e27, - 0x53028762, 0x40a01f15, 0x7447b78c, 0x67e52ffb, - 0xbf59d487, 0xacfb4cf0, 0x981ce469, 0x8bbe7c1e, - 0xf1d3b55b, 0xe2712d2c, 0xd69685b5, 0xc5341dc2, - 0x224d173f, 0x31ef8f48, 0x050827d1, 0x16aabfa6, - 0x6cc776e3, 0x7f65ee94, 0x4b82460d, 0x5820de7a, - 0xfbc3faf9, 0xe861628e, 0xdc86ca17, 0xcf245260, - 0xb5499b25, 0xa6eb0352, 0x920cabcb, 0x81ae33bc, - 0x66d73941, 0x7575a136, 0x419209af, 0x523091d8, - 0x285d589d, 0x3bffc0ea, 0x0f186873, 0x1cbaf004, - 0xc4060b78, 0xd7a4930f, 0xe3433b96, 0xf0e1a3e1, - 0x8a8c6aa4, 0x992ef2d3, 0xadc95a4a, 0xbe6bc23d, - 0x5912c8c0, 0x4ab050b7, 0x7e57f82e, 0x6df56059, - 0x1798a91c, 0x043a316b, 0x30dd99f2, 0x237f0185, - 0x844819fb, 0x97ea818c, 0xa30d2915, 0xb0afb162, - 0xcac27827, 0xd960e050, 0xed8748c9, 0xfe25d0be, - 0x195cda43, 0x0afe4234, 0x3e19eaad, 0x2dbb72da, - 0x57d6bb9f, 0x447423e8, 0x70938b71, 0x63311306, - 0xbb8de87a, 0xa82f700d, 0x9cc8d894, 0x8f6a40e3, - 0xf50789a6, 0xe6a511d1, 0xd242b948, 0xc1e0213f, - 0x26992bc2, 0x353bb3b5, 0x01dc1b2c, 0x127e835b, - 0x68134a1e, 0x7bb1d269, 0x4f567af0, 0x5cf4e287, - 0x04d43cfd, 0x1776a48a, 0x23910c13, 0x30339464, - 0x4a5e5d21, 0x59fcc556, 0x6d1b6dcf, 0x7eb9f5b8, - 0x99c0ff45, 0x8a626732, 0xbe85cfab, 0xad2757dc, - 0xd74a9e99, 0xc4e806ee, 0xf00fae77, 0xe3ad3600, - 0x3b11cd7c, 0x28b3550b, 0x1c54fd92, 0x0ff665e5, - 0x759baca0, 0x663934d7, 0x52de9c4e, 0x417c0439, - 0xa6050ec4, 0xb5a796b3, 0x81403e2a, 0x92e2a65d, - 0xe88f6f18, 0xfb2df76f, 0xcfca5ff6, 0xdc68c781, - 0x7b5fdfff, 0x68fd4788, 0x5c1aef11, 0x4fb87766, - 0x35d5be23, 0x26772654, 0x12908ecd, 0x013216ba, - 0xe64b1c47, 0xf5e98430, 0xc10e2ca9, 0xd2acb4de, - 0xa8c17d9b, 0xbb63e5ec, 0x8f844d75, 0x9c26d502, - 0x449a2e7e, 0x5738b609, 0x63df1e90, 0x707d86e7, - 0x0a104fa2, 0x19b2d7d5, 0x2d557f4c, 0x3ef7e73b, - 0xd98eedc6, 0xca2c75b1, 0xfecbdd28, 0xed69455f, - 0x97048c1a, 0x84a6146d, 0xb041bcf4, 0xa3e32483 -}; -static const uint32_t table2_[256] = { - 0x00000000, 0xa541927e, 0x4f6f520d, 0xea2ec073, - 0x9edea41a, 0x3b9f3664, 0xd1b1f617, 0x74f06469, - 0x38513ec5, 0x9d10acbb, 0x773e6cc8, 0xd27ffeb6, - 0xa68f9adf, 0x03ce08a1, 0xe9e0c8d2, 0x4ca15aac, - 0x70a27d8a, 0xd5e3eff4, 0x3fcd2f87, 0x9a8cbdf9, - 0xee7cd990, 0x4b3d4bee, 0xa1138b9d, 0x045219e3, - 0x48f3434f, 0xedb2d131, 0x079c1142, 0xa2dd833c, - 0xd62de755, 0x736c752b, 0x9942b558, 0x3c032726, - 0xe144fb14, 0x4405696a, 0xae2ba919, 0x0b6a3b67, - 0x7f9a5f0e, 0xdadbcd70, 0x30f50d03, 0x95b49f7d, - 0xd915c5d1, 0x7c5457af, 0x967a97dc, 0x333b05a2, - 0x47cb61cb, 0xe28af3b5, 0x08a433c6, 0xade5a1b8, - 0x91e6869e, 0x34a714e0, 0xde89d493, 0x7bc846ed, - 0x0f382284, 0xaa79b0fa, 0x40577089, 0xe516e2f7, - 0xa9b7b85b, 0x0cf62a25, 0xe6d8ea56, 0x43997828, - 0x37691c41, 0x92288e3f, 0x78064e4c, 0xdd47dc32, - 0xc76580d9, 0x622412a7, 0x880ad2d4, 0x2d4b40aa, - 0x59bb24c3, 0xfcfab6bd, 0x16d476ce, 0xb395e4b0, - 0xff34be1c, 0x5a752c62, 0xb05bec11, 0x151a7e6f, - 0x61ea1a06, 0xc4ab8878, 0x2e85480b, 0x8bc4da75, - 0xb7c7fd53, 0x12866f2d, 0xf8a8af5e, 0x5de93d20, - 0x29195949, 0x8c58cb37, 0x66760b44, 0xc337993a, - 0x8f96c396, 0x2ad751e8, 0xc0f9919b, 0x65b803e5, - 0x1148678c, 0xb409f5f2, 0x5e273581, 0xfb66a7ff, - 0x26217bcd, 0x8360e9b3, 0x694e29c0, 0xcc0fbbbe, - 0xb8ffdfd7, 0x1dbe4da9, 0xf7908dda, 0x52d11fa4, - 0x1e704508, 0xbb31d776, 0x511f1705, 0xf45e857b, - 0x80aee112, 0x25ef736c, 0xcfc1b31f, 0x6a802161, - 0x56830647, 0xf3c29439, 0x19ec544a, 0xbcadc634, - 0xc85da25d, 0x6d1c3023, 0x8732f050, 0x2273622e, - 0x6ed23882, 0xcb93aafc, 0x21bd6a8f, 0x84fcf8f1, - 0xf00c9c98, 0x554d0ee6, 0xbf63ce95, 0x1a225ceb, - 0x8b277743, 0x2e66e53d, 0xc448254e, 0x6109b730, - 0x15f9d359, 0xb0b84127, 0x5a968154, 0xffd7132a, - 0xb3764986, 0x1637dbf8, 0xfc191b8b, 0x595889f5, - 0x2da8ed9c, 0x88e97fe2, 0x62c7bf91, 0xc7862def, - 0xfb850ac9, 0x5ec498b7, 0xb4ea58c4, 0x11abcaba, - 0x655baed3, 0xc01a3cad, 0x2a34fcde, 0x8f756ea0, - 0xc3d4340c, 0x6695a672, 0x8cbb6601, 0x29faf47f, - 0x5d0a9016, 0xf84b0268, 0x1265c21b, 0xb7245065, - 0x6a638c57, 0xcf221e29, 0x250cde5a, 0x804d4c24, - 0xf4bd284d, 0x51fcba33, 0xbbd27a40, 0x1e93e83e, - 0x5232b292, 0xf77320ec, 0x1d5de09f, 0xb81c72e1, - 0xccec1688, 0x69ad84f6, 0x83834485, 0x26c2d6fb, - 0x1ac1f1dd, 0xbf8063a3, 0x55aea3d0, 0xf0ef31ae, - 0x841f55c7, 0x215ec7b9, 0xcb7007ca, 0x6e3195b4, - 0x2290cf18, 0x87d15d66, 0x6dff9d15, 0xc8be0f6b, - 0xbc4e6b02, 0x190ff97c, 0xf321390f, 0x5660ab71, - 0x4c42f79a, 0xe90365e4, 0x032da597, 0xa66c37e9, - 0xd29c5380, 0x77ddc1fe, 0x9df3018d, 0x38b293f3, - 0x7413c95f, 0xd1525b21, 0x3b7c9b52, 0x9e3d092c, - 0xeacd6d45, 0x4f8cff3b, 0xa5a23f48, 0x00e3ad36, - 0x3ce08a10, 0x99a1186e, 0x738fd81d, 0xd6ce4a63, - 0xa23e2e0a, 0x077fbc74, 0xed517c07, 0x4810ee79, - 0x04b1b4d5, 0xa1f026ab, 0x4bdee6d8, 0xee9f74a6, - 0x9a6f10cf, 0x3f2e82b1, 0xd50042c2, 0x7041d0bc, - 0xad060c8e, 0x08479ef0, 0xe2695e83, 0x4728ccfd, - 0x33d8a894, 0x96993aea, 0x7cb7fa99, 0xd9f668e7, - 0x9557324b, 0x3016a035, 0xda386046, 0x7f79f238, - 0x0b899651, 0xaec8042f, 0x44e6c45c, 0xe1a75622, - 0xdda47104, 0x78e5e37a, 0x92cb2309, 0x378ab177, - 0x437ad51e, 0xe63b4760, 0x0c158713, 0xa954156d, - 0xe5f54fc1, 0x40b4ddbf, 0xaa9a1dcc, 0x0fdb8fb2, - 0x7b2bebdb, 0xde6a79a5, 0x3444b9d6, 0x91052ba8 -}; -static const uint32_t table3_[256] = { - 0x00000000, 0xdd45aab8, 0xbf672381, 0x62228939, - 0x7b2231f3, 0xa6679b4b, 0xc4451272, 0x1900b8ca, - 0xf64463e6, 0x2b01c95e, 0x49234067, 0x9466eadf, - 0x8d665215, 0x5023f8ad, 0x32017194, 0xef44db2c, - 0xe964b13d, 0x34211b85, 0x560392bc, 0x8b463804, - 0x924680ce, 0x4f032a76, 0x2d21a34f, 0xf06409f7, - 0x1f20d2db, 0xc2657863, 0xa047f15a, 0x7d025be2, - 0x6402e328, 0xb9474990, 0xdb65c0a9, 0x06206a11, - 0xd725148b, 0x0a60be33, 0x6842370a, 0xb5079db2, - 0xac072578, 0x71428fc0, 0x136006f9, 0xce25ac41, - 0x2161776d, 0xfc24ddd5, 0x9e0654ec, 0x4343fe54, - 0x5a43469e, 0x8706ec26, 0xe524651f, 0x3861cfa7, - 0x3e41a5b6, 0xe3040f0e, 0x81268637, 0x5c632c8f, - 0x45639445, 0x98263efd, 0xfa04b7c4, 0x27411d7c, - 0xc805c650, 0x15406ce8, 0x7762e5d1, 0xaa274f69, - 0xb327f7a3, 0x6e625d1b, 0x0c40d422, 0xd1057e9a, - 0xaba65fe7, 0x76e3f55f, 0x14c17c66, 0xc984d6de, - 0xd0846e14, 0x0dc1c4ac, 0x6fe34d95, 0xb2a6e72d, - 0x5de23c01, 0x80a796b9, 0xe2851f80, 0x3fc0b538, - 0x26c00df2, 0xfb85a74a, 0x99a72e73, 0x44e284cb, - 0x42c2eeda, 0x9f874462, 0xfda5cd5b, 0x20e067e3, - 0x39e0df29, 0xe4a57591, 0x8687fca8, 0x5bc25610, - 0xb4868d3c, 0x69c32784, 0x0be1aebd, 0xd6a40405, - 0xcfa4bccf, 0x12e11677, 0x70c39f4e, 0xad8635f6, - 0x7c834b6c, 0xa1c6e1d4, 0xc3e468ed, 0x1ea1c255, - 0x07a17a9f, 0xdae4d027, 0xb8c6591e, 0x6583f3a6, - 0x8ac7288a, 0x57828232, 0x35a00b0b, 0xe8e5a1b3, - 0xf1e51979, 0x2ca0b3c1, 0x4e823af8, 0x93c79040, - 0x95e7fa51, 0x48a250e9, 0x2a80d9d0, 0xf7c57368, - 0xeec5cba2, 0x3380611a, 0x51a2e823, 0x8ce7429b, - 0x63a399b7, 0xbee6330f, 0xdcc4ba36, 0x0181108e, - 0x1881a844, 0xc5c402fc, 0xa7e68bc5, 0x7aa3217d, - 0x52a0c93f, 0x8fe56387, 0xedc7eabe, 0x30824006, - 0x2982f8cc, 0xf4c75274, 0x96e5db4d, 0x4ba071f5, - 0xa4e4aad9, 0x79a10061, 0x1b838958, 0xc6c623e0, - 0xdfc69b2a, 0x02833192, 0x60a1b8ab, 0xbde41213, - 0xbbc47802, 0x6681d2ba, 0x04a35b83, 0xd9e6f13b, - 0xc0e649f1, 0x1da3e349, 0x7f816a70, 0xa2c4c0c8, - 0x4d801be4, 0x90c5b15c, 0xf2e73865, 0x2fa292dd, - 0x36a22a17, 0xebe780af, 0x89c50996, 0x5480a32e, - 0x8585ddb4, 0x58c0770c, 0x3ae2fe35, 0xe7a7548d, - 0xfea7ec47, 0x23e246ff, 0x41c0cfc6, 0x9c85657e, - 0x73c1be52, 0xae8414ea, 0xcca69dd3, 0x11e3376b, - 0x08e38fa1, 0xd5a62519, 0xb784ac20, 0x6ac10698, - 0x6ce16c89, 0xb1a4c631, 0xd3864f08, 0x0ec3e5b0, - 0x17c35d7a, 0xca86f7c2, 0xa8a47efb, 0x75e1d443, - 0x9aa50f6f, 0x47e0a5d7, 0x25c22cee, 0xf8878656, - 0xe1873e9c, 0x3cc29424, 0x5ee01d1d, 0x83a5b7a5, - 0xf90696d8, 0x24433c60, 0x4661b559, 0x9b241fe1, - 0x8224a72b, 0x5f610d93, 0x3d4384aa, 0xe0062e12, - 0x0f42f53e, 0xd2075f86, 0xb025d6bf, 0x6d607c07, - 0x7460c4cd, 0xa9256e75, 0xcb07e74c, 0x16424df4, - 0x106227e5, 0xcd278d5d, 0xaf050464, 0x7240aedc, - 0x6b401616, 0xb605bcae, 0xd4273597, 0x09629f2f, - 0xe6264403, 0x3b63eebb, 0x59416782, 0x8404cd3a, - 0x9d0475f0, 0x4041df48, 0x22635671, 0xff26fcc9, - 0x2e238253, 0xf36628eb, 0x9144a1d2, 0x4c010b6a, - 0x5501b3a0, 0x88441918, 0xea669021, 0x37233a99, - 0xd867e1b5, 0x05224b0d, 0x6700c234, 0xba45688c, - 0xa345d046, 0x7e007afe, 0x1c22f3c7, 0xc167597f, - 0xc747336e, 0x1a0299d6, 0x782010ef, 0xa565ba57, - 0xbc65029d, 0x6120a825, 0x0302211c, 0xde478ba4, - 0x31035088, 0xec46fa30, 0x8e647309, 0x5321d9b1, - 0x4a21617b, 0x9764cbc3, 0xf54642fa, 0x2803e842 -}; +namespace { -// Used to fetch a naturally-aligned 32-bit word in little endian byte-order -static inline uint32_t LE_LOAD32(const uint8_t *p) { - return DecodeFixed32(reinterpret_cast<const char*>(p)); +const uint32_t kByteExtensionTable[256] = { + 0x00000000, 0xf26b8303, 0xe13b70f7, 0x1350f3f4, 0xc79a971f, 0x35f1141c, + 0x26a1e7e8, 0xd4ca64eb, 0x8ad958cf, 0x78b2dbcc, 0x6be22838, 0x9989ab3b, + 0x4d43cfd0, 0xbf284cd3, 0xac78bf27, 0x5e133c24, 0x105ec76f, 0xe235446c, + 0xf165b798, 0x030e349b, 0xd7c45070, 0x25afd373, 0x36ff2087, 0xc494a384, + 0x9a879fa0, 0x68ec1ca3, 0x7bbcef57, 0x89d76c54, 0x5d1d08bf, 0xaf768bbc, + 0xbc267848, 0x4e4dfb4b, 0x20bd8ede, 0xd2d60ddd, 0xc186fe29, 0x33ed7d2a, + 0xe72719c1, 0x154c9ac2, 0x061c6936, 0xf477ea35, 0xaa64d611, 0x580f5512, + 0x4b5fa6e6, 0xb93425e5, 0x6dfe410e, 0x9f95c20d, 0x8cc531f9, 0x7eaeb2fa, + 0x30e349b1, 0xc288cab2, 0xd1d83946, 0x23b3ba45, 0xf779deae, 0x05125dad, + 0x1642ae59, 0xe4292d5a, 0xba3a117e, 0x4851927d, 0x5b016189, 0xa96ae28a, + 0x7da08661, 0x8fcb0562, 0x9c9bf696, 0x6ef07595, 0x417b1dbc, 0xb3109ebf, + 0xa0406d4b, 0x522bee48, 0x86e18aa3, 0x748a09a0, 0x67dafa54, 0x95b17957, + 0xcba24573, 0x39c9c670, 0x2a993584, 0xd8f2b687, 0x0c38d26c, 0xfe53516f, + 0xed03a29b, 0x1f682198, 0x5125dad3, 0xa34e59d0, 0xb01eaa24, 0x42752927, + 0x96bf4dcc, 0x64d4cecf, 0x77843d3b, 0x85efbe38, 0xdbfc821c, 0x2997011f, + 0x3ac7f2eb, 0xc8ac71e8, 0x1c661503, 0xee0d9600, 0xfd5d65f4, 0x0f36e6f7, + 0x61c69362, 0x93ad1061, 0x80fde395, 0x72966096, 0xa65c047d, 0x5437877e, + 0x4767748a, 0xb50cf789, 0xeb1fcbad, 0x197448ae, 0x0a24bb5a, 0xf84f3859, + 0x2c855cb2, 0xdeeedfb1, 0xcdbe2c45, 0x3fd5af46, 0x7198540d, 0x83f3d70e, + 0x90a324fa, 0x62c8a7f9, 0xb602c312, 0x44694011, 0x5739b3e5, 0xa55230e6, + 0xfb410cc2, 0x092a8fc1, 0x1a7a7c35, 0xe811ff36, 0x3cdb9bdd, 0xceb018de, + 0xdde0eb2a, 0x2f8b6829, 0x82f63b78, 0x709db87b, 0x63cd4b8f, 0x91a6c88c, + 0x456cac67, 0xb7072f64, 0xa457dc90, 0x563c5f93, 0x082f63b7, 0xfa44e0b4, + 0xe9141340, 0x1b7f9043, 0xcfb5f4a8, 0x3dde77ab, 0x2e8e845f, 0xdce5075c, + 0x92a8fc17, 0x60c37f14, 0x73938ce0, 0x81f80fe3, 0x55326b08, 0xa759e80b, + 0xb4091bff, 0x466298fc, 0x1871a4d8, 0xea1a27db, 0xf94ad42f, 0x0b21572c, + 0xdfeb33c7, 0x2d80b0c4, 0x3ed04330, 0xccbbc033, 0xa24bb5a6, 0x502036a5, + 0x4370c551, 0xb11b4652, 0x65d122b9, 0x97baa1ba, 0x84ea524e, 0x7681d14d, + 0x2892ed69, 0xdaf96e6a, 0xc9a99d9e, 0x3bc21e9d, 0xef087a76, 0x1d63f975, + 0x0e330a81, 0xfc588982, 0xb21572c9, 0x407ef1ca, 0x532e023e, 0xa145813d, + 0x758fe5d6, 0x87e466d5, 0x94b49521, 0x66df1622, 0x38cc2a06, 0xcaa7a905, + 0xd9f75af1, 0x2b9cd9f2, 0xff56bd19, 0x0d3d3e1a, 0x1e6dcdee, 0xec064eed, + 0xc38d26c4, 0x31e6a5c7, 0x22b65633, 0xd0ddd530, 0x0417b1db, 0xf67c32d8, + 0xe52cc12c, 0x1747422f, 0x49547e0b, 0xbb3ffd08, 0xa86f0efc, 0x5a048dff, + 0x8ecee914, 0x7ca56a17, 0x6ff599e3, 0x9d9e1ae0, 0xd3d3e1ab, 0x21b862a8, + 0x32e8915c, 0xc083125f, 0x144976b4, 0xe622f5b7, 0xf5720643, 0x07198540, + 0x590ab964, 0xab613a67, 0xb831c993, 0x4a5a4a90, 0x9e902e7b, 0x6cfbad78, + 0x7fab5e8c, 0x8dc0dd8f, 0xe330a81a, 0x115b2b19, 0x020bd8ed, 0xf0605bee, + 0x24aa3f05, 0xd6c1bc06, 0xc5914ff2, 0x37faccf1, 0x69e9f0d5, 0x9b8273d6, + 0x88d28022, 0x7ab90321, 0xae7367ca, 0x5c18e4c9, 0x4f48173d, 0xbd23943e, + 0xf36e6f75, 0x0105ec76, 0x12551f82, 0xe03e9c81, 0x34f4f86a, 0xc69f7b69, + 0xd5cf889d, 0x27a40b9e, 0x79b737ba, 0x8bdcb4b9, 0x988c474d, 0x6ae7c44e, + 0xbe2da0a5, 0x4c4623a6, 0x5f16d052, 0xad7d5351}; + +const uint32_t kStrideExtensionTable0[256] = { + 0x00000000, 0x30d23865, 0x61a470ca, 0x517648af, 0xc348e194, 0xf39ad9f1, + 0xa2ec915e, 0x923ea93b, 0x837db5d9, 0xb3af8dbc, 0xe2d9c513, 0xd20bfd76, + 0x4035544d, 0x70e76c28, 0x21912487, 0x11431ce2, 0x03171d43, 0x33c52526, + 0x62b36d89, 0x526155ec, 0xc05ffcd7, 0xf08dc4b2, 0xa1fb8c1d, 0x9129b478, + 0x806aa89a, 0xb0b890ff, 0xe1ced850, 0xd11ce035, 0x4322490e, 0x73f0716b, + 0x228639c4, 0x125401a1, 0x062e3a86, 0x36fc02e3, 0x678a4a4c, 0x57587229, + 0xc566db12, 0xf5b4e377, 0xa4c2abd8, 0x941093bd, 0x85538f5f, 0xb581b73a, + 0xe4f7ff95, 0xd425c7f0, 0x461b6ecb, 0x76c956ae, 0x27bf1e01, 0x176d2664, + 0x053927c5, 0x35eb1fa0, 0x649d570f, 0x544f6f6a, 0xc671c651, 0xf6a3fe34, + 0xa7d5b69b, 0x97078efe, 0x8644921c, 0xb696aa79, 0xe7e0e2d6, 0xd732dab3, + 0x450c7388, 0x75de4bed, 0x24a80342, 0x147a3b27, 0x0c5c750c, 0x3c8e4d69, + 0x6df805c6, 0x5d2a3da3, 0xcf149498, 0xffc6acfd, 0xaeb0e452, 0x9e62dc37, + 0x8f21c0d5, 0xbff3f8b0, 0xee85b01f, 0xde57887a, 0x4c692141, 0x7cbb1924, + 0x2dcd518b, 0x1d1f69ee, 0x0f4b684f, 0x3f99502a, 0x6eef1885, 0x5e3d20e0, + 0xcc0389db, 0xfcd1b1be, 0xada7f911, 0x9d75c174, 0x8c36dd96, 0xbce4e5f3, + 0xed92ad5c, 0xdd409539, 0x4f7e3c02, 0x7fac0467, 0x2eda4cc8, 0x1e0874ad, + 0x0a724f8a, 0x3aa077ef, 0x6bd63f40, 0x5b040725, 0xc93aae1e, 0xf9e8967b, + 0xa89eded4, 0x984ce6b1, 0x890ffa53, 0xb9ddc236, 0xe8ab8a99, 0xd879b2fc, + 0x4a471bc7, 0x7a9523a2, 0x2be36b0d, 0x1b315368, 0x096552c9, 0x39b76aac, + 0x68c12203, 0x58131a66, 0xca2db35d, 0xfaff8b38, 0xab89c397, 0x9b5bfbf2, + 0x8a18e710, 0xbacadf75, 0xebbc97da, 0xdb6eafbf, 0x49500684, 0x79823ee1, + 0x28f4764e, 0x18264e2b, 0x18b8ea18, 0x286ad27d, 0x791c9ad2, 0x49cea2b7, + 0xdbf00b8c, 0xeb2233e9, 0xba547b46, 0x8a864323, 0x9bc55fc1, 0xab1767a4, + 0xfa612f0b, 0xcab3176e, 0x588dbe55, 0x685f8630, 0x3929ce9f, 0x09fbf6fa, + 0x1baff75b, 0x2b7dcf3e, 0x7a0b8791, 0x4ad9bff4, 0xd8e716cf, 0xe8352eaa, + 0xb9436605, 0x89915e60, 0x98d24282, 0xa8007ae7, 0xf9763248, 0xc9a40a2d, + 0x5b9aa316, 0x6b489b73, 0x3a3ed3dc, 0x0aecebb9, 0x1e96d09e, 0x2e44e8fb, + 0x7f32a054, 0x4fe09831, 0xddde310a, 0xed0c096f, 0xbc7a41c0, 0x8ca879a5, + 0x9deb6547, 0xad395d22, 0xfc4f158d, 0xcc9d2de8, 0x5ea384d3, 0x6e71bcb6, + 0x3f07f419, 0x0fd5cc7c, 0x1d81cddd, 0x2d53f5b8, 0x7c25bd17, 0x4cf78572, + 0xdec92c49, 0xee1b142c, 0xbf6d5c83, 0x8fbf64e6, 0x9efc7804, 0xae2e4061, + 0xff5808ce, 0xcf8a30ab, 0x5db49990, 0x6d66a1f5, 0x3c10e95a, 0x0cc2d13f, + 0x14e49f14, 0x2436a771, 0x7540efde, 0x4592d7bb, 0xd7ac7e80, 0xe77e46e5, + 0xb6080e4a, 0x86da362f, 0x97992acd, 0xa74b12a8, 0xf63d5a07, 0xc6ef6262, + 0x54d1cb59, 0x6403f33c, 0x3575bb93, 0x05a783f6, 0x17f38257, 0x2721ba32, + 0x7657f29d, 0x4685caf8, 0xd4bb63c3, 0xe4695ba6, 0xb51f1309, 0x85cd2b6c, + 0x948e378e, 0xa45c0feb, 0xf52a4744, 0xc5f87f21, 0x57c6d61a, 0x6714ee7f, + 0x3662a6d0, 0x06b09eb5, 0x12caa592, 0x22189df7, 0x736ed558, 0x43bced3d, + 0xd1824406, 0xe1507c63, 0xb02634cc, 0x80f40ca9, 0x91b7104b, 0xa165282e, + 0xf0136081, 0xc0c158e4, 0x52fff1df, 0x622dc9ba, 0x335b8115, 0x0389b970, + 0x11ddb8d1, 0x210f80b4, 0x7079c81b, 0x40abf07e, 0xd2955945, 0xe2476120, + 0xb331298f, 0x83e311ea, 0x92a00d08, 0xa272356d, 0xf3047dc2, 0xc3d645a7, + 0x51e8ec9c, 0x613ad4f9, 0x304c9c56, 0x009ea433}; + +const uint32_t kStrideExtensionTable1[256] = { + 0x00000000, 0x54075546, 0xa80eaa8c, 0xfc09ffca, 0x55f123e9, 0x01f676af, + 0xfdff8965, 0xa9f8dc23, 0xabe247d2, 0xffe51294, 0x03eced5e, 0x57ebb818, + 0xfe13643b, 0xaa14317d, 0x561dceb7, 0x021a9bf1, 0x5228f955, 0x062fac13, + 0xfa2653d9, 0xae21069f, 0x07d9dabc, 0x53de8ffa, 0xafd77030, 0xfbd02576, + 0xf9cabe87, 0xadcdebc1, 0x51c4140b, 0x05c3414d, 0xac3b9d6e, 0xf83cc828, + 0x043537e2, 0x503262a4, 0xa451f2aa, 0xf056a7ec, 0x0c5f5826, 0x58580d60, + 0xf1a0d143, 0xa5a78405, 0x59ae7bcf, 0x0da92e89, 0x0fb3b578, 0x5bb4e03e, + 0xa7bd1ff4, 0xf3ba4ab2, 0x5a429691, 0x0e45c3d7, 0xf24c3c1d, 0xa64b695b, + 0xf6790bff, 0xa27e5eb9, 0x5e77a173, 0x0a70f435, 0xa3882816, 0xf78f7d50, + 0x0b86829a, 0x5f81d7dc, 0x5d9b4c2d, 0x099c196b, 0xf595e6a1, 0xa192b3e7, + 0x086a6fc4, 0x5c6d3a82, 0xa064c548, 0xf463900e, 0x4d4f93a5, 0x1948c6e3, + 0xe5413929, 0xb1466c6f, 0x18beb04c, 0x4cb9e50a, 0xb0b01ac0, 0xe4b74f86, + 0xe6add477, 0xb2aa8131, 0x4ea37efb, 0x1aa42bbd, 0xb35cf79e, 0xe75ba2d8, + 0x1b525d12, 0x4f550854, 0x1f676af0, 0x4b603fb6, 0xb769c07c, 0xe36e953a, + 0x4a964919, 0x1e911c5f, 0xe298e395, 0xb69fb6d3, 0xb4852d22, 0xe0827864, + 0x1c8b87ae, 0x488cd2e8, 0xe1740ecb, 0xb5735b8d, 0x497aa447, 0x1d7df101, + 0xe91e610f, 0xbd193449, 0x4110cb83, 0x15179ec5, 0xbcef42e6, 0xe8e817a0, + 0x14e1e86a, 0x40e6bd2c, 0x42fc26dd, 0x16fb739b, 0xeaf28c51, 0xbef5d917, + 0x170d0534, 0x430a5072, 0xbf03afb8, 0xeb04fafe, 0xbb36985a, 0xef31cd1c, + 0x133832d6, 0x473f6790, 0xeec7bbb3, 0xbac0eef5, 0x46c9113f, 0x12ce4479, + 0x10d4df88, 0x44d38ace, 0xb8da7504, 0xecdd2042, 0x4525fc61, 0x1122a927, + 0xed2b56ed, 0xb92c03ab, 0x9a9f274a, 0xce98720c, 0x32918dc6, 0x6696d880, + 0xcf6e04a3, 0x9b6951e5, 0x6760ae2f, 0x3367fb69, 0x317d6098, 0x657a35de, + 0x9973ca14, 0xcd749f52, 0x648c4371, 0x308b1637, 0xcc82e9fd, 0x9885bcbb, + 0xc8b7de1f, 0x9cb08b59, 0x60b97493, 0x34be21d5, 0x9d46fdf6, 0xc941a8b0, + 0x3548577a, 0x614f023c, 0x635599cd, 0x3752cc8b, 0xcb5b3341, 0x9f5c6607, + 0x36a4ba24, 0x62a3ef62, 0x9eaa10a8, 0xcaad45ee, 0x3eced5e0, 0x6ac980a6, + 0x96c07f6c, 0xc2c72a2a, 0x6b3ff609, 0x3f38a34f, 0xc3315c85, 0x973609c3, + 0x952c9232, 0xc12bc774, 0x3d2238be, 0x69256df8, 0xc0ddb1db, 0x94dae49d, + 0x68d31b57, 0x3cd44e11, 0x6ce62cb5, 0x38e179f3, 0xc4e88639, 0x90efd37f, + 0x39170f5c, 0x6d105a1a, 0x9119a5d0, 0xc51ef096, 0xc7046b67, 0x93033e21, + 0x6f0ac1eb, 0x3b0d94ad, 0x92f5488e, 0xc6f21dc8, 0x3afbe202, 0x6efcb744, + 0xd7d0b4ef, 0x83d7e1a9, 0x7fde1e63, 0x2bd94b25, 0x82219706, 0xd626c240, + 0x2a2f3d8a, 0x7e2868cc, 0x7c32f33d, 0x2835a67b, 0xd43c59b1, 0x803b0cf7, + 0x29c3d0d4, 0x7dc48592, 0x81cd7a58, 0xd5ca2f1e, 0x85f84dba, 0xd1ff18fc, + 0x2df6e736, 0x79f1b270, 0xd0096e53, 0x840e3b15, 0x7807c4df, 0x2c009199, + 0x2e1a0a68, 0x7a1d5f2e, 0x8614a0e4, 0xd213f5a2, 0x7beb2981, 0x2fec7cc7, + 0xd3e5830d, 0x87e2d64b, 0x73814645, 0x27861303, 0xdb8fecc9, 0x8f88b98f, + 0x267065ac, 0x727730ea, 0x8e7ecf20, 0xda799a66, 0xd8630197, 0x8c6454d1, + 0x706dab1b, 0x246afe5d, 0x8d92227e, 0xd9957738, 0x259c88f2, 0x719bddb4, + 0x21a9bf10, 0x75aeea56, 0x89a7159c, 0xdda040da, 0x74589cf9, 0x205fc9bf, + 0xdc563675, 0x88516333, 0x8a4bf8c2, 0xde4cad84, 0x2245524e, 0x76420708, + 0xdfbadb2b, 0x8bbd8e6d, 0x77b471a7, 0x23b324e1}; + +const uint32_t kStrideExtensionTable2[256] = { + 0x00000000, 0x678efd01, 0xcf1dfa02, 0xa8930703, 0x9bd782f5, 0xfc597ff4, + 0x54ca78f7, 0x334485f6, 0x3243731b, 0x55cd8e1a, 0xfd5e8919, 0x9ad07418, + 0xa994f1ee, 0xce1a0cef, 0x66890bec, 0x0107f6ed, 0x6486e636, 0x03081b37, + 0xab9b1c34, 0xcc15e135, 0xff5164c3, 0x98df99c2, 0x304c9ec1, 0x57c263c0, + 0x56c5952d, 0x314b682c, 0x99d86f2f, 0xfe56922e, 0xcd1217d8, 0xaa9cead9, + 0x020fedda, 0x658110db, 0xc90dcc6c, 0xae83316d, 0x0610366e, 0x619ecb6f, + 0x52da4e99, 0x3554b398, 0x9dc7b49b, 0xfa49499a, 0xfb4ebf77, 0x9cc04276, + 0x34534575, 0x53ddb874, 0x60993d82, 0x0717c083, 0xaf84c780, 0xc80a3a81, + 0xad8b2a5a, 0xca05d75b, 0x6296d058, 0x05182d59, 0x365ca8af, 0x51d255ae, + 0xf94152ad, 0x9ecfafac, 0x9fc85941, 0xf846a440, 0x50d5a343, 0x375b5e42, + 0x041fdbb4, 0x639126b5, 0xcb0221b6, 0xac8cdcb7, 0x97f7ee29, 0xf0791328, + 0x58ea142b, 0x3f64e92a, 0x0c206cdc, 0x6bae91dd, 0xc33d96de, 0xa4b36bdf, + 0xa5b49d32, 0xc23a6033, 0x6aa96730, 0x0d279a31, 0x3e631fc7, 0x59ede2c6, + 0xf17ee5c5, 0x96f018c4, 0xf371081f, 0x94fff51e, 0x3c6cf21d, 0x5be20f1c, + 0x68a68aea, 0x0f2877eb, 0xa7bb70e8, 0xc0358de9, 0xc1327b04, 0xa6bc8605, + 0x0e2f8106, 0x69a17c07, 0x5ae5f9f1, 0x3d6b04f0, 0x95f803f3, 0xf276fef2, + 0x5efa2245, 0x3974df44, 0x91e7d847, 0xf6692546, 0xc52da0b0, 0xa2a35db1, + 0x0a305ab2, 0x6dbea7b3, 0x6cb9515e, 0x0b37ac5f, 0xa3a4ab5c, 0xc42a565d, + 0xf76ed3ab, 0x90e02eaa, 0x387329a9, 0x5ffdd4a8, 0x3a7cc473, 0x5df23972, + 0xf5613e71, 0x92efc370, 0xa1ab4686, 0xc625bb87, 0x6eb6bc84, 0x09384185, + 0x083fb768, 0x6fb14a69, 0xc7224d6a, 0xa0acb06b, 0x93e8359d, 0xf466c89c, + 0x5cf5cf9f, 0x3b7b329e, 0x2a03aaa3, 0x4d8d57a2, 0xe51e50a1, 0x8290ada0, + 0xb1d42856, 0xd65ad557, 0x7ec9d254, 0x19472f55, 0x1840d9b8, 0x7fce24b9, + 0xd75d23ba, 0xb0d3debb, 0x83975b4d, 0xe419a64c, 0x4c8aa14f, 0x2b045c4e, + 0x4e854c95, 0x290bb194, 0x8198b697, 0xe6164b96, 0xd552ce60, 0xb2dc3361, + 0x1a4f3462, 0x7dc1c963, 0x7cc63f8e, 0x1b48c28f, 0xb3dbc58c, 0xd455388d, + 0xe711bd7b, 0x809f407a, 0x280c4779, 0x4f82ba78, 0xe30e66cf, 0x84809bce, + 0x2c139ccd, 0x4b9d61cc, 0x78d9e43a, 0x1f57193b, 0xb7c41e38, 0xd04ae339, + 0xd14d15d4, 0xb6c3e8d5, 0x1e50efd6, 0x79de12d7, 0x4a9a9721, 0x2d146a20, + 0x85876d23, 0xe2099022, 0x878880f9, 0xe0067df8, 0x48957afb, 0x2f1b87fa, + 0x1c5f020c, 0x7bd1ff0d, 0xd342f80e, 0xb4cc050f, 0xb5cbf3e2, 0xd2450ee3, + 0x7ad609e0, 0x1d58f4e1, 0x2e1c7117, 0x49928c16, 0xe1018b15, 0x868f7614, + 0xbdf4448a, 0xda7ab98b, 0x72e9be88, 0x15674389, 0x2623c67f, 0x41ad3b7e, + 0xe93e3c7d, 0x8eb0c17c, 0x8fb73791, 0xe839ca90, 0x40aacd93, 0x27243092, + 0x1460b564, 0x73ee4865, 0xdb7d4f66, 0xbcf3b267, 0xd972a2bc, 0xbefc5fbd, + 0x166f58be, 0x71e1a5bf, 0x42a52049, 0x252bdd48, 0x8db8da4b, 0xea36274a, + 0xeb31d1a7, 0x8cbf2ca6, 0x242c2ba5, 0x43a2d6a4, 0x70e65352, 0x1768ae53, + 0xbffba950, 0xd8755451, 0x74f988e6, 0x137775e7, 0xbbe472e4, 0xdc6a8fe5, + 0xef2e0a13, 0x88a0f712, 0x2033f011, 0x47bd0d10, 0x46bafbfd, 0x213406fc, + 0x89a701ff, 0xee29fcfe, 0xdd6d7908, 0xbae38409, 0x1270830a, 0x75fe7e0b, + 0x107f6ed0, 0x77f193d1, 0xdf6294d2, 0xb8ec69d3, 0x8ba8ec25, 0xec261124, + 0x44b51627, 0x233beb26, 0x223c1dcb, 0x45b2e0ca, 0xed21e7c9, 0x8aaf1ac8, + 0xb9eb9f3e, 0xde65623f, 0x76f6653c, 0x1178983d}; + +const uint32_t kStrideExtensionTable3[256] = { + 0x00000000, 0xf20c0dfe, 0xe1f46d0d, 0x13f860f3, 0xc604aceb, 0x3408a115, + 0x27f0c1e6, 0xd5fccc18, 0x89e52f27, 0x7be922d9, 0x6811422a, 0x9a1d4fd4, + 0x4fe183cc, 0xbded8e32, 0xae15eec1, 0x5c19e33f, 0x162628bf, 0xe42a2541, + 0xf7d245b2, 0x05de484c, 0xd0228454, 0x222e89aa, 0x31d6e959, 0xc3dae4a7, + 0x9fc30798, 0x6dcf0a66, 0x7e376a95, 0x8c3b676b, 0x59c7ab73, 0xabcba68d, + 0xb833c67e, 0x4a3fcb80, 0x2c4c517e, 0xde405c80, 0xcdb83c73, 0x3fb4318d, + 0xea48fd95, 0x1844f06b, 0x0bbc9098, 0xf9b09d66, 0xa5a97e59, 0x57a573a7, + 0x445d1354, 0xb6511eaa, 0x63add2b2, 0x91a1df4c, 0x8259bfbf, 0x7055b241, + 0x3a6a79c1, 0xc866743f, 0xdb9e14cc, 0x29921932, 0xfc6ed52a, 0x0e62d8d4, + 0x1d9ab827, 0xef96b5d9, 0xb38f56e6, 0x41835b18, 0x527b3beb, 0xa0773615, + 0x758bfa0d, 0x8787f7f3, 0x947f9700, 0x66739afe, 0x5898a2fc, 0xaa94af02, + 0xb96ccff1, 0x4b60c20f, 0x9e9c0e17, 0x6c9003e9, 0x7f68631a, 0x8d646ee4, + 0xd17d8ddb, 0x23718025, 0x3089e0d6, 0xc285ed28, 0x17792130, 0xe5752cce, + 0xf68d4c3d, 0x048141c3, 0x4ebe8a43, 0xbcb287bd, 0xaf4ae74e, 0x5d46eab0, + 0x88ba26a8, 0x7ab62b56, 0x694e4ba5, 0x9b42465b, 0xc75ba564, 0x3557a89a, + 0x26afc869, 0xd4a3c597, 0x015f098f, 0xf3530471, 0xe0ab6482, 0x12a7697c, + 0x74d4f382, 0x86d8fe7c, 0x95209e8f, 0x672c9371, 0xb2d05f69, 0x40dc5297, + 0x53243264, 0xa1283f9a, 0xfd31dca5, 0x0f3dd15b, 0x1cc5b1a8, 0xeec9bc56, + 0x3b35704e, 0xc9397db0, 0xdac11d43, 0x28cd10bd, 0x62f2db3d, 0x90fed6c3, + 0x8306b630, 0x710abbce, 0xa4f677d6, 0x56fa7a28, 0x45021adb, 0xb70e1725, + 0xeb17f41a, 0x191bf9e4, 0x0ae39917, 0xf8ef94e9, 0x2d1358f1, 0xdf1f550f, + 0xcce735fc, 0x3eeb3802, 0xb13145f8, 0x433d4806, 0x50c528f5, 0xa2c9250b, + 0x7735e913, 0x8539e4ed, 0x96c1841e, 0x64cd89e0, 0x38d46adf, 0xcad86721, + 0xd92007d2, 0x2b2c0a2c, 0xfed0c634, 0x0cdccbca, 0x1f24ab39, 0xed28a6c7, + 0xa7176d47, 0x551b60b9, 0x46e3004a, 0xb4ef0db4, 0x6113c1ac, 0x931fcc52, + 0x80e7aca1, 0x72eba15f, 0x2ef24260, 0xdcfe4f9e, 0xcf062f6d, 0x3d0a2293, + 0xe8f6ee8b, 0x1afae375, 0x09028386, 0xfb0e8e78, 0x9d7d1486, 0x6f711978, + 0x7c89798b, 0x8e857475, 0x5b79b86d, 0xa975b593, 0xba8dd560, 0x4881d89e, + 0x14983ba1, 0xe694365f, 0xf56c56ac, 0x07605b52, 0xd29c974a, 0x20909ab4, + 0x3368fa47, 0xc164f7b9, 0x8b5b3c39, 0x795731c7, 0x6aaf5134, 0x98a35cca, + 0x4d5f90d2, 0xbf539d2c, 0xacabfddf, 0x5ea7f021, 0x02be131e, 0xf0b21ee0, + 0xe34a7e13, 0x114673ed, 0xc4babff5, 0x36b6b20b, 0x254ed2f8, 0xd742df06, + 0xe9a9e704, 0x1ba5eafa, 0x085d8a09, 0xfa5187f7, 0x2fad4bef, 0xdda14611, + 0xce5926e2, 0x3c552b1c, 0x604cc823, 0x9240c5dd, 0x81b8a52e, 0x73b4a8d0, + 0xa64864c8, 0x54446936, 0x47bc09c5, 0xb5b0043b, 0xff8fcfbb, 0x0d83c245, + 0x1e7ba2b6, 0xec77af48, 0x398b6350, 0xcb876eae, 0xd87f0e5d, 0x2a7303a3, + 0x766ae09c, 0x8466ed62, 0x979e8d91, 0x6592806f, 0xb06e4c77, 0x42624189, + 0x519a217a, 0xa3962c84, 0xc5e5b67a, 0x37e9bb84, 0x2411db77, 0xd61dd689, + 0x03e11a91, 0xf1ed176f, 0xe215779c, 0x10197a62, 0x4c00995d, 0xbe0c94a3, + 0xadf4f450, 0x5ff8f9ae, 0x8a0435b6, 0x78083848, 0x6bf058bb, 0x99fc5545, + 0xd3c39ec5, 0x21cf933b, 0x3237f3c8, 0xc03bfe36, 0x15c7322e, 0xe7cb3fd0, + 0xf4335f23, 0x063f52dd, 0x5a26b1e2, 0xa82abc1c, 0xbbd2dcef, 0x49ded111, + 0x9c221d09, 0x6e2e10f7, 0x7dd67004, 0x8fda7dfa}; + +// CRCs are pre- and post- conditioned by xoring with all ones. +static constexpr const uint32_t kCRC32Xor = static_cast<uint32_t>(0xffffffffU); + +// Reads a little-endian 32-bit integer from a 32-bit-aligned buffer. +inline uint32_t ReadUint32LE(const uint8_t* buffer) { + return DecodeFixed32(reinterpret_cast<const char*>(buffer)); } +// Returns the smallest address >= the given address that is aligned to N bytes. +// +// N must be a power of two. +template <int N> +constexpr inline const uint8_t* RoundUp(const uint8_t* pointer) { + return reinterpret_cast<uint8_t*>( + (reinterpret_cast<uintptr_t>(pointer) + (N - 1)) & + ~static_cast<uintptr_t>(N - 1)); +} + +} // namespace + // Determine if the CPU running this program can accelerate the CRC32C // calculation. static bool CanAccelerateCRC32C() { - if (!port::HasAcceleratedCRC32C()) - return false; - - // Double-check that the accelerated implementation functions correctly. // port::AcceleretedCRC32C returns zero when unable to accelerate. static const char kTestCRCBuffer[] = "TestCRCBuffer"; static const char kBufSize = sizeof(kTestCRCBuffer) - 1; @@ -300,54 +273,107 @@ static bool CanAccelerateCRC32C() { return port::AcceleratedCRC32C(0, kTestCRCBuffer, kBufSize) == kTestCRCValue; } -uint32_t Extend(uint32_t crc, const char* buf, size_t size) { +uint32_t Extend(uint32_t crc, const char* data, size_t n) { static bool accelerate = CanAccelerateCRC32C(); if (accelerate) { - return port::AcceleratedCRC32C(crc, buf, size); + return port::AcceleratedCRC32C(crc, data, n); } - const uint8_t *p = reinterpret_cast<const uint8_t *>(buf); - const uint8_t *e = p + size; - uint32_t l = crc ^ 0xffffffffu; + const uint8_t* p = reinterpret_cast<const uint8_t*>(data); + const uint8_t* e = p + n; + uint32_t l = crc ^ kCRC32Xor; + +// Process one byte at a time. +#define STEP1 \ + do { \ + int c = (l & 0xff) ^ *p++; \ + l = kByteExtensionTable[c] ^ (l >> 8); \ + } while (0) -#define STEP1 do { \ - int c = (l & 0xff) ^ *p++; \ - l = table0_[c] ^ (l >> 8); \ -} while (0) -#define STEP4 do { \ - uint32_t c = l ^ LE_LOAD32(p); \ - p += 4; \ - l = table3_[c & 0xff] ^ \ - table2_[(c >> 8) & 0xff] ^ \ - table1_[(c >> 16) & 0xff] ^ \ - table0_[c >> 24]; \ -} while (0) +// Process one of the 4 strides of 4-byte data. +#define STEP4(s) \ + do { \ + crc##s = ReadUint32LE(p + s * 4) ^ kStrideExtensionTable3[crc##s & 0xff] ^ \ + kStrideExtensionTable2[(crc##s >> 8) & 0xff] ^ \ + kStrideExtensionTable1[(crc##s >> 16) & 0xff] ^ \ + kStrideExtensionTable0[crc##s >> 24]; \ + } while (0) - // Point x at first 4-byte aligned byte in string. This might be - // just past the end of the string. - const uintptr_t pval = reinterpret_cast<uintptr_t>(p); - const uint8_t* x = reinterpret_cast<const uint8_t*>(((pval + 3) >> 2) << 2); +// Process a 16-byte swath of 4 strides, each of which has 4 bytes of data. +#define STEP16 \ + do { \ + STEP4(0); \ + STEP4(1); \ + STEP4(2); \ + STEP4(3); \ + p += 16; \ + } while (0) + +// Process 4 bytes that were already loaded into a word. +#define STEP4W(w) \ + do { \ + w ^= l; \ + for (size_t i = 0; i < 4; ++i) { \ + w = (w >> 8) ^ kByteExtensionTable[w & 0xff]; \ + } \ + l = w; \ + } while (0) + + // Point x at first 4-byte aligned byte in the buffer. This might be past the + // end of the buffer. + const uint8_t* x = RoundUp<4>(p); if (x <= e) { - // Process bytes until finished or p is 4-byte aligned + // Process bytes p is 4-byte aligned. while (p != x) { STEP1; } } - // Process bytes 16 at a time - while ((e-p) >= 16) { - STEP4; STEP4; STEP4; STEP4; - } - // Process bytes 4 at a time - while ((e-p) >= 4) { - STEP4; + + if ((e - p) >= 16) { + // Load a 16-byte swath into the stride partial results. + uint32_t crc0 = ReadUint32LE(p + 0 * 4) ^ l; + uint32_t crc1 = ReadUint32LE(p + 1 * 4); + uint32_t crc2 = ReadUint32LE(p + 2 * 4); + uint32_t crc3 = ReadUint32LE(p + 3 * 4); + p += 16; + + // It is possible to get better speeds (at least on x86) by interleaving + // prefetching 256 bytes ahead with processing 64 bytes at a time. See the + // portable implementation in https://github.com/google/crc32c/. + + // Process one 16-byte swath at a time. + while ((e - p) >= 16) { + STEP16; + } + + // Advance one word at a time as far as possible. + while ((e - p) >= 4) { + STEP4(0); + uint32_t tmp = crc0; + crc0 = crc1; + crc1 = crc2; + crc2 = crc3; + crc3 = tmp; + p += 4; + } + + // Combine the 4 partial stride results. + l = 0; + STEP4W(crc0); + STEP4W(crc1); + STEP4W(crc2); + STEP4W(crc3); } - // Process the last few bytes + + // Process the last few bytes. while (p != e) { STEP1; } +#undef STEP4W +#undef STEP16 #undef STEP4 #undef STEP1 - return l ^ 0xffffffffu; + return l ^ kCRC32Xor; } } // namespace crc32c diff --git a/src/leveldb/util/crc32c.h b/src/leveldb/util/crc32c.h index 1d7e5c075d..98fabb0d2f 100644 --- a/src/leveldb/util/crc32c.h +++ b/src/leveldb/util/crc32c.h @@ -14,12 +14,10 @@ namespace crc32c { // Return the crc32c of concat(A, data[0,n-1]) where init_crc is the // crc32c of some string A. Extend() is often used to maintain the // crc32c of a stream of data. -extern uint32_t Extend(uint32_t init_crc, const char* data, size_t n); +uint32_t Extend(uint32_t init_crc, const char* data, size_t n); // Return the crc32c of data[0,n-1] -inline uint32_t Value(const char* data, size_t n) { - return Extend(0, data, n); -} +inline uint32_t Value(const char* data, size_t n) { return Extend(0, data, n); } static const uint32_t kMaskDelta = 0xa282ead8ul; diff --git a/src/leveldb/util/crc32c_test.cc b/src/leveldb/util/crc32c_test.cc index 4b957ee120..18a8494824 100644 --- a/src/leveldb/util/crc32c_test.cc +++ b/src/leveldb/util/crc32c_test.cc @@ -8,7 +8,7 @@ namespace leveldb { namespace crc32c { -class CRC { }; +class CRC {}; TEST(CRC, StandardResults) { // From rfc3720 section B.4. @@ -30,30 +30,19 @@ TEST(CRC, StandardResults) { } ASSERT_EQ(0x113fdb5c, Value(buf, sizeof(buf))); - unsigned char data[48] = { - 0x01, 0xc0, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, - 0x14, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x04, 0x00, - 0x00, 0x00, 0x00, 0x14, - 0x00, 0x00, 0x00, 0x18, - 0x28, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, - 0x02, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, + uint8_t data[48] = { + 0x01, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00, + 0x00, 0x00, 0x00, 0x14, 0x00, 0x00, 0x00, 0x18, 0x28, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, }; ASSERT_EQ(0xd9963a56, Value(reinterpret_cast<char*>(data), sizeof(data))); } -TEST(CRC, Values) { - ASSERT_NE(Value("a", 1), Value("foo", 3)); -} +TEST(CRC, Values) { ASSERT_NE(Value("a", 1), Value("foo", 3)); } TEST(CRC, Extend) { - ASSERT_EQ(Value("hello world", 11), - Extend(Value("hello ", 6), "world", 5)); + ASSERT_EQ(Value("hello world", 11), Extend(Value("hello ", 6), "world", 5)); } TEST(CRC, Mask) { @@ -67,6 +56,4 @@ TEST(CRC, Mask) { } // namespace crc32c } // namespace leveldb -int main(int argc, char** argv) { - return leveldb::test::RunAllTests(); -} +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } diff --git a/src/leveldb/util/env.cc b/src/leveldb/util/env.cc index c58a0821ef..d2f0aef326 100644 --- a/src/leveldb/util/env.cc +++ b/src/leveldb/util/env.cc @@ -6,30 +6,24 @@ namespace leveldb { -Env::~Env() { -} +Env::~Env() = default; Status Env::NewAppendableFile(const std::string& fname, WritableFile** result) { return Status::NotSupported("NewAppendableFile", fname); } -SequentialFile::~SequentialFile() { -} +SequentialFile::~SequentialFile() = default; -RandomAccessFile::~RandomAccessFile() { -} +RandomAccessFile::~RandomAccessFile() = default; -WritableFile::~WritableFile() { -} +WritableFile::~WritableFile() = default; -Logger::~Logger() { -} +Logger::~Logger() = default; -FileLock::~FileLock() { -} +FileLock::~FileLock() = default; void Log(Logger* info_log, const char* format, ...) { - if (info_log != NULL) { + if (info_log != nullptr) { va_list ap; va_start(ap, format); info_log->Logv(format, ap); @@ -38,8 +32,7 @@ void Log(Logger* info_log, const char* format, ...) { } static Status DoWriteStringToFile(Env* env, const Slice& data, - const std::string& fname, - bool should_sync) { + const std::string& fname, bool should_sync) { WritableFile* file; Status s = env->NewWritableFile(fname, &file); if (!s.ok()) { @@ -94,7 +87,6 @@ Status ReadFileToString(Env* env, const std::string& fname, std::string* data) { return s; } -EnvWrapper::~EnvWrapper() { -} +EnvWrapper::~EnvWrapper() {} } // namespace leveldb diff --git a/src/leveldb/util/env_posix.cc b/src/leveldb/util/env_posix.cc index f77918313e..9f5863a0f3 100644 --- a/src/leveldb/util/env_posix.cc +++ b/src/leveldb/util/env_posix.cc @@ -1,706 +1,906 @@ // 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. -#if !defined(LEVELDB_PLATFORM_WINDOWS) #include <dirent.h> -#include <errno.h> #include <fcntl.h> #include <pthread.h> -#include <stdio.h> -#include <stdlib.h> -#include <string.h> #include <sys/mman.h> #include <sys/resource.h> #include <sys/stat.h> #include <sys/time.h> #include <sys/types.h> -#include <time.h> #include <unistd.h> -#include <deque> + +#include <atomic> +#include <cerrno> +#include <cstddef> +#include <cstdint> +#include <cstdio> +#include <cstdlib> +#include <cstring> #include <limits> +#include <queue> #include <set> +#include <string> +#include <thread> +#include <type_traits> +#include <utility> + #include "leveldb/env.h" #include "leveldb/slice.h" +#include "leveldb/status.h" #include "port/port.h" -#include "util/logging.h" -#include "util/mutexlock.h" -#include "util/posix_logger.h" +#include "port/thread_annotations.h" #include "util/env_posix_test_helper.h" +#include "util/posix_logger.h" namespace leveldb { namespace { -static int open_read_only_file_limit = -1; -static int mmap_limit = -1; +// Set by EnvPosixTestHelper::SetReadOnlyMMapLimit() and MaxOpenFiles(). +int g_open_read_only_file_limit = -1; + +// Up to 4096 mmap regions for 64-bit binaries; none for 32-bit. +constexpr const int kDefaultMmapLimit = (sizeof(void*) >= 8) ? 4096 : 0; + +// Can be set using EnvPosixTestHelper::SetReadOnlyMMapLimit(). +int g_mmap_limit = kDefaultMmapLimit; -static Status IOError(const std::string& context, int err_number) { - return Status::IOError(context, strerror(err_number)); +// Common flags defined for all posix open operations +#if defined(HAVE_O_CLOEXEC) +constexpr const int kOpenBaseFlags = O_CLOEXEC; +#else +constexpr const int kOpenBaseFlags = 0; +#endif // defined(HAVE_O_CLOEXEC) + +constexpr const size_t kWritableFileBufferSize = 65536; + +Status PosixError(const std::string& context, int error_number) { + if (error_number == ENOENT) { + return Status::NotFound(context, std::strerror(error_number)); + } else { + return Status::IOError(context, std::strerror(error_number)); + } } // Helper class to limit resource usage to avoid exhaustion. // Currently used to limit read-only file descriptors and mmap file usage -// so that we do not end up running out of file descriptors, virtual memory, -// or running into kernel performance problems for very large databases. +// so that we do not run out of file descriptors or virtual memory, or run into +// kernel performance problems for very large databases. class Limiter { public: - // Limit maximum number of resources to |n|. - Limiter(intptr_t n) { - SetAllowed(n); - } + // Limit maximum number of resources to |max_acquires|. + Limiter(int max_acquires) : acquires_allowed_(max_acquires) {} + + Limiter(const Limiter&) = delete; + Limiter operator=(const Limiter&) = delete; // If another resource is available, acquire it and return true. // Else return false. bool Acquire() { - if (GetAllowed() <= 0) { - return false; - } - MutexLock l(&mu_); - intptr_t x = GetAllowed(); - if (x <= 0) { - return false; - } else { - SetAllowed(x - 1); - return true; - } + int old_acquires_allowed = + acquires_allowed_.fetch_sub(1, std::memory_order_relaxed); + + if (old_acquires_allowed > 0) return true; + + acquires_allowed_.fetch_add(1, std::memory_order_relaxed); + return false; } // Release a resource acquired by a previous call to Acquire() that returned // true. - void Release() { - MutexLock l(&mu_); - SetAllowed(GetAllowed() + 1); - } + void Release() { acquires_allowed_.fetch_add(1, std::memory_order_relaxed); } private: - port::Mutex mu_; - port::AtomicPointer allowed_; - - intptr_t GetAllowed() const { - return reinterpret_cast<intptr_t>(allowed_.Acquire_Load()); - } - - // REQUIRES: mu_ must be held - void SetAllowed(intptr_t v) { - allowed_.Release_Store(reinterpret_cast<void*>(v)); - } - - Limiter(const Limiter&); - void operator=(const Limiter&); + // The number of available resources. + // + // This is a counter and is not tied to the invariants of any other class, so + // it can be operated on safely using std::memory_order_relaxed. + std::atomic<int> acquires_allowed_; }; -class PosixSequentialFile: public SequentialFile { - private: - std::string filename_; - FILE* file_; - +// Implements sequential read access in a file using read(). +// +// Instances of this class are thread-friendly but not thread-safe, as required +// by the SequentialFile API. +class PosixSequentialFile final : public SequentialFile { public: - PosixSequentialFile(const std::string& fname, FILE* f) - : filename_(fname), file_(f) { } - virtual ~PosixSequentialFile() { fclose(file_); } - - virtual Status Read(size_t n, Slice* result, char* scratch) { - Status s; - size_t r = fread_unlocked(scratch, 1, n, file_); - *result = Slice(scratch, r); - if (r < n) { - if (feof(file_)) { - // We leave status as ok if we hit the end of the file - } else { - // A partial read with an error: return a non-ok status - s = IOError(filename_, errno); + PosixSequentialFile(std::string filename, int fd) + : fd_(fd), filename_(filename) {} + ~PosixSequentialFile() override { close(fd_); } + + Status Read(size_t n, Slice* result, char* scratch) override { + Status status; + while (true) { + ::ssize_t read_size = ::read(fd_, scratch, n); + if (read_size < 0) { // Read error. + if (errno == EINTR) { + continue; // Retry + } + status = PosixError(filename_, errno); + break; } + *result = Slice(scratch, read_size); + break; } - return s; + return status; } - virtual Status Skip(uint64_t n) { - if (fseek(file_, n, SEEK_CUR)) { - return IOError(filename_, errno); + Status Skip(uint64_t n) override { + if (::lseek(fd_, n, SEEK_CUR) == static_cast<off_t>(-1)) { + return PosixError(filename_, errno); } return Status::OK(); } - virtual std::string GetName() const { return filename_; } -}; + virtual std::string GetName() const override { return filename_; } -// pread() based random-access -class PosixRandomAccessFile: public RandomAccessFile { private: - std::string filename_; - bool temporary_fd_; // If true, fd_ is -1 and we open on every read. - int fd_; - Limiter* limiter_; + const int fd_; + const std::string filename_; +}; +// Implements random read access in a file using pread(). +// +// Instances of this class are thread-safe, as required by the RandomAccessFile +// API. Instances are immutable and Read() only calls thread-safe library +// functions. +class PosixRandomAccessFile final : public RandomAccessFile { public: - PosixRandomAccessFile(const std::string& fname, int fd, Limiter* limiter) - : filename_(fname), fd_(fd), limiter_(limiter) { - temporary_fd_ = !limiter->Acquire(); - if (temporary_fd_) { - // Open file on every access. - close(fd_); - fd_ = -1; + // The new instance takes ownership of |fd|. |fd_limiter| must outlive this + // instance, and will be used to determine if . + PosixRandomAccessFile(std::string filename, int fd, Limiter* fd_limiter) + : has_permanent_fd_(fd_limiter->Acquire()), + fd_(has_permanent_fd_ ? fd : -1), + fd_limiter_(fd_limiter), + filename_(std::move(filename)) { + if (!has_permanent_fd_) { + assert(fd_ == -1); + ::close(fd); // The file will be opened on every read. } } - virtual ~PosixRandomAccessFile() { - if (!temporary_fd_) { - close(fd_); - limiter_->Release(); + ~PosixRandomAccessFile() override { + if (has_permanent_fd_) { + assert(fd_ != -1); + ::close(fd_); + fd_limiter_->Release(); } } - virtual Status Read(uint64_t offset, size_t n, Slice* result, - char* scratch) const { + Status Read(uint64_t offset, size_t n, Slice* result, + char* scratch) const override { int fd = fd_; - if (temporary_fd_) { - fd = open(filename_.c_str(), O_RDONLY); + if (!has_permanent_fd_) { + fd = ::open(filename_.c_str(), O_RDONLY | kOpenBaseFlags); if (fd < 0) { - return IOError(filename_, errno); + return PosixError(filename_, errno); } } - Status s; - ssize_t r = pread(fd, scratch, n, static_cast<off_t>(offset)); - *result = Slice(scratch, (r < 0) ? 0 : r); - if (r < 0) { - // An error: return a non-ok status - s = IOError(filename_, errno); + assert(fd != -1); + + Status status; + ssize_t read_size = ::pread(fd, scratch, n, static_cast<off_t>(offset)); + *result = Slice(scratch, (read_size < 0) ? 0 : read_size); + if (read_size < 0) { + // An error: return a non-ok status. + status = PosixError(filename_, errno); } - if (temporary_fd_) { + if (!has_permanent_fd_) { // Close the temporary file descriptor opened earlier. - close(fd); + assert(fd != fd_); + ::close(fd); } - return s; + return status; } - virtual std::string GetName() const { return filename_; } -}; + virtual std::string GetName() const override { return filename_; } -// mmap() based random-access -class PosixMmapReadableFile: public RandomAccessFile { private: - std::string filename_; - void* mmapped_region_; - size_t length_; - Limiter* limiter_; + const bool has_permanent_fd_; // If false, the file is opened on every read. + const int fd_; // -1 if has_permanent_fd_ is false. + Limiter* const fd_limiter_; + const std::string filename_; +}; +// Implements random read access in a file using mmap(). +// +// Instances of this class are thread-safe, as required by the RandomAccessFile +// API. Instances are immutable and Read() only calls thread-safe library +// functions. +class PosixMmapReadableFile final : public RandomAccessFile { public: - // base[0,length-1] contains the mmapped contents of the file. - PosixMmapReadableFile(const std::string& fname, void* base, size_t length, - Limiter* limiter) - : filename_(fname), mmapped_region_(base), length_(length), - limiter_(limiter) { - } - - virtual ~PosixMmapReadableFile() { - munmap(mmapped_region_, length_); - limiter_->Release(); - } - - virtual Status Read(uint64_t offset, size_t n, Slice* result, - char* scratch) const { - Status s; + // mmap_base[0, length-1] points to the memory-mapped contents of the file. It + // must be the result of a successful call to mmap(). This instances takes + // over the ownership of the region. + // + // |mmap_limiter| must outlive this instance. The caller must have already + // aquired the right to use one mmap region, which will be released when this + // instance is destroyed. + PosixMmapReadableFile(std::string filename, char* mmap_base, size_t length, + Limiter* mmap_limiter) + : mmap_base_(mmap_base), + length_(length), + mmap_limiter_(mmap_limiter), + filename_(std::move(filename)) {} + + ~PosixMmapReadableFile() override { + ::munmap(static_cast<void*>(mmap_base_), length_); + mmap_limiter_->Release(); + } + + Status Read(uint64_t offset, size_t n, Slice* result, + char* scratch) const override { if (offset + n > length_) { *result = Slice(); - s = IOError(filename_, EINVAL); - } else { - *result = Slice(reinterpret_cast<char*>(mmapped_region_) + offset, n); + return PosixError(filename_, EINVAL); } - return s; + + *result = Slice(mmap_base_ + offset, n); + return Status::OK(); } - virtual std::string GetName() const { return filename_; } -}; + virtual std::string GetName() const override { return filename_; } -class PosixWritableFile : public WritableFile { private: - std::string filename_; - FILE* file_; + char* const mmap_base_; + const size_t length_; + Limiter* const mmap_limiter_; + const std::string filename_; +}; +class PosixWritableFile final : public WritableFile { public: - PosixWritableFile(const std::string& fname, FILE* f) - : filename_(fname), file_(f) { } - - ~PosixWritableFile() { - if (file_ != NULL) { + PosixWritableFile(std::string filename, int fd) + : pos_(0), + fd_(fd), + is_manifest_(IsManifest(filename)), + filename_(std::move(filename)), + dirname_(Dirname(filename_)) {} + + ~PosixWritableFile() override { + if (fd_ >= 0) { // Ignoring any potential errors - fclose(file_); + Close(); } } - virtual Status Append(const Slice& data) { - size_t r = fwrite_unlocked(data.data(), 1, data.size(), file_); - if (r != data.size()) { - return IOError(filename_, errno); + Status Append(const Slice& data) override { + size_t write_size = data.size(); + const char* write_data = data.data(); + + // Fit as much as possible into buffer. + size_t copy_size = std::min(write_size, kWritableFileBufferSize - pos_); + std::memcpy(buf_ + pos_, write_data, copy_size); + write_data += copy_size; + write_size -= copy_size; + pos_ += copy_size; + if (write_size == 0) { + return Status::OK(); } - return Status::OK(); + + // Can't fit in buffer, so need to do at least one write. + Status status = FlushBuffer(); + if (!status.ok()) { + return status; + } + + // Small writes go to buffer, large writes are written directly. + if (write_size < kWritableFileBufferSize) { + std::memcpy(buf_, write_data, write_size); + pos_ = write_size; + return Status::OK(); + } + return WriteUnbuffered(write_data, write_size); } - virtual Status Close() { - Status result; - if (fclose(file_) != 0) { - result = IOError(filename_, errno); + Status Close() override { + Status status = FlushBuffer(); + const int close_result = ::close(fd_); + if (close_result < 0 && status.ok()) { + status = PosixError(filename_, errno); } - file_ = NULL; - return result; + fd_ = -1; + return status; } - virtual Status Flush() { - if (fflush_unlocked(file_) != 0) { - return IOError(filename_, errno); + Status Flush() override { return FlushBuffer(); } + + Status Sync() override { + // Ensure new files referred to by the manifest are in the filesystem. + // + // This needs to happen before the manifest file is flushed to disk, to + // avoid crashing in a state where the manifest refers to files that are not + // yet on disk. + Status status = SyncDirIfManifest(); + if (!status.ok()) { + return status; + } + + status = FlushBuffer(); + if (!status.ok()) { + return status; + } + + return SyncFd(fd_, filename_, false); + } + + private: + Status FlushBuffer() { + Status status = WriteUnbuffered(buf_, pos_); + pos_ = 0; + return status; + } + + Status WriteUnbuffered(const char* data, size_t size) { + while (size > 0) { + ssize_t write_result = ::write(fd_, data, size); + if (write_result < 0) { + if (errno == EINTR) { + continue; // Retry + } + return PosixError(filename_, errno); + } + data += write_result; + size -= write_result; } return Status::OK(); } Status SyncDirIfManifest() { - const char* f = filename_.c_str(); - const char* sep = strrchr(f, '/'); - Slice basename; - std::string dir; - if (sep == NULL) { - dir = "."; - basename = f; + Status status; + if (!is_manifest_) { + return status; + } + + int fd = ::open(dirname_.c_str(), O_RDONLY | kOpenBaseFlags); + if (fd < 0) { + status = PosixError(dirname_, errno); } else { - dir = std::string(f, sep - f); - basename = sep + 1; + status = SyncFd(fd, dirname_, true); + ::close(fd); + } + return status; + } + + // Ensures that all the caches associated with the given file descriptor's + // data are flushed all the way to durable media, and can withstand power + // failures. + // + // The path argument is only used to populate the description string in the + // returned Status if an error occurs. + static Status SyncFd(int fd, const std::string& fd_path, bool syncing_dir) { +#if HAVE_FULLFSYNC + // On macOS and iOS, fsync() doesn't guarantee durability past power + // failures. fcntl(F_FULLFSYNC) is required for that purpose. Some + // filesystems don't support fcntl(F_FULLFSYNC), and require a fallback to + // fsync(). + if (::fcntl(fd, F_FULLFSYNC) == 0) { + return Status::OK(); } - Status s; - if (basename.starts_with("MANIFEST")) { - int fd = open(dir.c_str(), O_RDONLY); - if (fd < 0) { - s = IOError(dir, errno); - } else { - if (fsync(fd) < 0 && errno != EINVAL) { - s = IOError(dir, errno); - } - close(fd); - } +#endif // HAVE_FULLFSYNC + +#if HAVE_FDATASYNC + bool sync_success = ::fdatasync(fd) == 0; +#else + bool sync_success = ::fsync(fd) == 0; +#endif // HAVE_FDATASYNC + + if (sync_success) { + return Status::OK(); } - return s; + // Do not crash if filesystem can't fsync directories + // (see https://github.com/bitcoin/bitcoin/pull/10000) + if (syncing_dir && errno == EINVAL) { + return Status::OK(); + } + return PosixError(fd_path, errno); } - virtual Status Sync() { - // Ensure new files referred to by the manifest are in the filesystem. - Status s = SyncDirIfManifest(); - if (!s.ok()) { - return s; + // Returns the directory name in a path pointing to a file. + // + // Returns "." if the path does not contain any directory separator. + static std::string Dirname(const std::string& filename) { + std::string::size_type separator_pos = filename.rfind('/'); + if (separator_pos == std::string::npos) { + return std::string("."); } - if (fflush_unlocked(file_) != 0 || - fdatasync(fileno(file_)) != 0) { - s = Status::IOError(filename_, strerror(errno)); + // The filename component should not contain a path separator. If it does, + // the splitting was done incorrectly. + assert(filename.find('/', separator_pos + 1) == std::string::npos); + + return filename.substr(0, separator_pos); + } + + // Extracts the file name from a path pointing to a file. + // + // The returned Slice points to |filename|'s data buffer, so it is only valid + // while |filename| is alive and unchanged. + static Slice Basename(const std::string& filename) { + std::string::size_type separator_pos = filename.rfind('/'); + if (separator_pos == std::string::npos) { + return Slice(filename); } - return s; + // The filename component should not contain a path separator. If it does, + // the splitting was done incorrectly. + assert(filename.find('/', separator_pos + 1) == std::string::npos); + + return Slice(filename.data() + separator_pos + 1, + filename.length() - separator_pos - 1); } - virtual std::string GetName() const { return filename_; } + // True if the given file is a manifest file. + static bool IsManifest(const std::string& filename) { + return Basename(filename).starts_with("MANIFEST"); + } + + virtual std::string GetName() const override { return filename_; } + + // buf_[0, pos_ - 1] contains data to be written to fd_. + char buf_[kWritableFileBufferSize]; + size_t pos_; + int fd_; + + const bool is_manifest_; // True if the file's name starts with MANIFEST. + const std::string filename_; + const std::string dirname_; // The directory of filename_. }; -static int LockOrUnlock(int fd, bool lock) { +int LockOrUnlock(int fd, bool lock) { errno = 0; - struct flock f; - memset(&f, 0, sizeof(f)); - f.l_type = (lock ? F_WRLCK : F_UNLCK); - f.l_whence = SEEK_SET; - f.l_start = 0; - f.l_len = 0; // Lock/unlock entire file - return fcntl(fd, F_SETLK, &f); + struct ::flock file_lock_info; + std::memset(&file_lock_info, 0, sizeof(file_lock_info)); + file_lock_info.l_type = (lock ? F_WRLCK : F_UNLCK); + file_lock_info.l_whence = SEEK_SET; + file_lock_info.l_start = 0; + file_lock_info.l_len = 0; // Lock/unlock entire file. + return ::fcntl(fd, F_SETLK, &file_lock_info); } +// Instances are thread-safe because they are immutable. class PosixFileLock : public FileLock { public: - int fd_; - std::string name_; + PosixFileLock(int fd, std::string filename) + : fd_(fd), filename_(std::move(filename)) {} + + int fd() const { return fd_; } + const std::string& filename() const { return filename_; } + + private: + const int fd_; + const std::string filename_; }; -// Set of locked files. We keep a separate set instead of just -// relying on fcntrl(F_SETLK) since fcntl(F_SETLK) does not provide -// any protection against multiple uses from the same process. +// Tracks the files locked by PosixEnv::LockFile(). +// +// We maintain a separate set instead of relying on fcntl(F_SETLK) because +// fcntl(F_SETLK) does not provide any protection against multiple uses from the +// same process. +// +// Instances are thread-safe because all member data is guarded by a mutex. class PosixLockTable { - private: - port::Mutex mu_; - std::set<std::string> locked_files_; public: - bool Insert(const std::string& fname) { - MutexLock l(&mu_); - return locked_files_.insert(fname).second; - } - void Remove(const std::string& fname) { - MutexLock l(&mu_); + bool Insert(const std::string& fname) LOCKS_EXCLUDED(mu_) { + mu_.Lock(); + bool succeeded = locked_files_.insert(fname).second; + mu_.Unlock(); + return succeeded; + } + void Remove(const std::string& fname) LOCKS_EXCLUDED(mu_) { + mu_.Lock(); locked_files_.erase(fname); + mu_.Unlock(); } + + private: + port::Mutex mu_; + std::set<std::string> locked_files_ GUARDED_BY(mu_); }; class PosixEnv : public Env { public: PosixEnv(); - virtual ~PosixEnv() { - char msg[] = "Destroying Env::Default()\n"; - fwrite(msg, 1, sizeof(msg), stderr); - abort(); - } - - virtual Status NewSequentialFile(const std::string& fname, - SequentialFile** result) { - FILE* f = fopen(fname.c_str(), "r"); - if (f == NULL) { - *result = NULL; - return IOError(fname, errno); - } else { - *result = new PosixSequentialFile(fname, f); - return Status::OK(); + ~PosixEnv() override { + static const char msg[] = + "PosixEnv singleton destroyed. Unsupported behavior!\n"; + std::fwrite(msg, 1, sizeof(msg), stderr); + std::abort(); + } + + Status NewSequentialFile(const std::string& filename, + SequentialFile** result) override { + int fd = ::open(filename.c_str(), O_RDONLY | kOpenBaseFlags); + if (fd < 0) { + *result = nullptr; + return PosixError(filename, errno); } + + *result = new PosixSequentialFile(filename, fd); + return Status::OK(); } - virtual Status NewRandomAccessFile(const std::string& fname, - RandomAccessFile** result) { - *result = NULL; - Status s; - int fd = open(fname.c_str(), O_RDONLY); + Status NewRandomAccessFile(const std::string& filename, + RandomAccessFile** result) override { + *result = nullptr; + int fd = ::open(filename.c_str(), O_RDONLY | kOpenBaseFlags); if (fd < 0) { - s = IOError(fname, errno); - } else if (mmap_limit_.Acquire()) { - uint64_t size; - s = GetFileSize(fname, &size); - if (s.ok()) { - void* base = mmap(NULL, size, PROT_READ, MAP_SHARED, fd, 0); - if (base != MAP_FAILED) { - *result = new PosixMmapReadableFile(fname, base, size, &mmap_limit_); - } else { - s = IOError(fname, errno); - } - } - close(fd); - if (!s.ok()) { - mmap_limit_.Release(); + return PosixError(filename, errno); + } + + if (!mmap_limiter_.Acquire()) { + *result = new PosixRandomAccessFile(filename, fd, &fd_limiter_); + return Status::OK(); + } + + uint64_t file_size; + Status status = GetFileSize(filename, &file_size); + if (status.ok()) { + void* mmap_base = + ::mmap(/*addr=*/nullptr, file_size, PROT_READ, MAP_SHARED, fd, 0); + if (mmap_base != MAP_FAILED) { + *result = new PosixMmapReadableFile(filename, + reinterpret_cast<char*>(mmap_base), + file_size, &mmap_limiter_); + } else { + status = PosixError(filename, errno); } - } else { - *result = new PosixRandomAccessFile(fname, fd, &fd_limit_); } - return s; + ::close(fd); + if (!status.ok()) { + mmap_limiter_.Release(); + } + return status; } - virtual Status NewWritableFile(const std::string& fname, - WritableFile** result) { - Status s; - FILE* f = fopen(fname.c_str(), "w"); - if (f == NULL) { - *result = NULL; - s = IOError(fname, errno); - } else { - *result = new PosixWritableFile(fname, f); + Status NewWritableFile(const std::string& filename, + WritableFile** result) override { + int fd = ::open(filename.c_str(), + O_TRUNC | O_WRONLY | O_CREAT | kOpenBaseFlags, 0644); + if (fd < 0) { + *result = nullptr; + return PosixError(filename, errno); } - return s; + + *result = new PosixWritableFile(filename, fd); + return Status::OK(); } - virtual Status NewAppendableFile(const std::string& fname, - WritableFile** result) { - Status s; - FILE* f = fopen(fname.c_str(), "a"); - if (f == NULL) { - *result = NULL; - s = IOError(fname, errno); - } else { - *result = new PosixWritableFile(fname, f); + Status NewAppendableFile(const std::string& filename, + WritableFile** result) override { + int fd = ::open(filename.c_str(), + O_APPEND | O_WRONLY | O_CREAT | kOpenBaseFlags, 0644); + if (fd < 0) { + *result = nullptr; + return PosixError(filename, errno); } - return s; + + *result = new PosixWritableFile(filename, fd); + return Status::OK(); } - virtual bool FileExists(const std::string& fname) { - return access(fname.c_str(), F_OK) == 0; + bool FileExists(const std::string& filename) override { + return ::access(filename.c_str(), F_OK) == 0; } - virtual Status GetChildren(const std::string& dir, - std::vector<std::string>* result) { + Status GetChildren(const std::string& directory_path, + std::vector<std::string>* result) override { result->clear(); - DIR* d = opendir(dir.c_str()); - if (d == NULL) { - return IOError(dir, errno); + ::DIR* dir = ::opendir(directory_path.c_str()); + if (dir == nullptr) { + return PosixError(directory_path, errno); } - struct dirent* entry; - while ((entry = readdir(d)) != NULL) { - result->push_back(entry->d_name); + struct ::dirent* entry; + while ((entry = ::readdir(dir)) != nullptr) { + result->emplace_back(entry->d_name); } - closedir(d); + ::closedir(dir); return Status::OK(); } - virtual Status DeleteFile(const std::string& fname) { - Status result; - if (unlink(fname.c_str()) != 0) { - result = IOError(fname, errno); + Status DeleteFile(const std::string& filename) override { + if (::unlink(filename.c_str()) != 0) { + return PosixError(filename, errno); } - return result; + return Status::OK(); } - virtual Status CreateDir(const std::string& name) { - Status result; - if (mkdir(name.c_str(), 0755) != 0) { - result = IOError(name, errno); + Status CreateDir(const std::string& dirname) override { + if (::mkdir(dirname.c_str(), 0755) != 0) { + return PosixError(dirname, errno); } - return result; + return Status::OK(); } - virtual Status DeleteDir(const std::string& name) { - Status result; - if (rmdir(name.c_str()) != 0) { - result = IOError(name, errno); + Status DeleteDir(const std::string& dirname) override { + if (::rmdir(dirname.c_str()) != 0) { + return PosixError(dirname, errno); } - return result; + return Status::OK(); } - virtual Status GetFileSize(const std::string& fname, uint64_t* size) { - Status s; - struct stat sbuf; - if (stat(fname.c_str(), &sbuf) != 0) { + Status GetFileSize(const std::string& filename, uint64_t* size) override { + struct ::stat file_stat; + if (::stat(filename.c_str(), &file_stat) != 0) { *size = 0; - s = IOError(fname, errno); - } else { - *size = sbuf.st_size; + return PosixError(filename, errno); } - return s; + *size = file_stat.st_size; + return Status::OK(); } - virtual Status RenameFile(const std::string& src, const std::string& target) { - Status result; - if (rename(src.c_str(), target.c_str()) != 0) { - result = IOError(src, errno); + Status RenameFile(const std::string& from, const std::string& to) override { + if (std::rename(from.c_str(), to.c_str()) != 0) { + return PosixError(from, errno); } - return result; + return Status::OK(); } - virtual Status LockFile(const std::string& fname, FileLock** lock) { - *lock = NULL; - Status result; - int fd = open(fname.c_str(), O_RDWR | O_CREAT, 0644); + Status LockFile(const std::string& filename, FileLock** lock) override { + *lock = nullptr; + + int fd = ::open(filename.c_str(), O_RDWR | O_CREAT | kOpenBaseFlags, 0644); if (fd < 0) { - result = IOError(fname, errno); - } else if (!locks_.Insert(fname)) { - close(fd); - result = Status::IOError("lock " + fname, "already held by process"); - } else if (LockOrUnlock(fd, true) == -1) { - result = IOError("lock " + fname, errno); - close(fd); - locks_.Remove(fname); - } else { - PosixFileLock* my_lock = new PosixFileLock; - my_lock->fd_ = fd; - my_lock->name_ = fname; - *lock = my_lock; + return PosixError(filename, errno); } - return result; + + if (!locks_.Insert(filename)) { + ::close(fd); + return Status::IOError("lock " + filename, "already held by process"); + } + + if (LockOrUnlock(fd, true) == -1) { + int lock_errno = errno; + ::close(fd); + locks_.Remove(filename); + return PosixError("lock " + filename, lock_errno); + } + + *lock = new PosixFileLock(fd, filename); + return Status::OK(); } - virtual Status UnlockFile(FileLock* lock) { - PosixFileLock* my_lock = reinterpret_cast<PosixFileLock*>(lock); - Status result; - if (LockOrUnlock(my_lock->fd_, false) == -1) { - result = IOError("unlock", errno); + Status UnlockFile(FileLock* lock) override { + PosixFileLock* posix_file_lock = static_cast<PosixFileLock*>(lock); + if (LockOrUnlock(posix_file_lock->fd(), false) == -1) { + return PosixError("unlock " + posix_file_lock->filename(), errno); } - locks_.Remove(my_lock->name_); - close(my_lock->fd_); - delete my_lock; - return result; + locks_.Remove(posix_file_lock->filename()); + ::close(posix_file_lock->fd()); + delete posix_file_lock; + return Status::OK(); } - virtual void Schedule(void (*function)(void*), void* arg); + void Schedule(void (*background_work_function)(void* background_work_arg), + void* background_work_arg) override; - virtual void StartThread(void (*function)(void* arg), void* arg); + void StartThread(void (*thread_main)(void* thread_main_arg), + void* thread_main_arg) override { + std::thread new_thread(thread_main, thread_main_arg); + new_thread.detach(); + } - virtual Status GetTestDirectory(std::string* result) { - const char* env = getenv("TEST_TMPDIR"); + Status GetTestDirectory(std::string* result) override { + const char* env = std::getenv("TEST_TMPDIR"); if (env && env[0] != '\0') { *result = env; } else { char buf[100]; - snprintf(buf, sizeof(buf), "/tmp/leveldbtest-%d", int(geteuid())); + std::snprintf(buf, sizeof(buf), "/tmp/leveldbtest-%d", + static_cast<int>(::geteuid())); *result = buf; } - // Directory may already exist + + // The CreateDir status is ignored because the directory may already exist. CreateDir(*result); + return Status::OK(); } - static uint64_t gettid() { - pthread_t tid = pthread_self(); - uint64_t thread_id = 0; - memcpy(&thread_id, &tid, std::min(sizeof(thread_id), sizeof(tid))); - return thread_id; - } + Status NewLogger(const std::string& filename, Logger** result) override { + int fd = ::open(filename.c_str(), + O_APPEND | O_WRONLY | O_CREAT | kOpenBaseFlags, 0644); + if (fd < 0) { + *result = nullptr; + return PosixError(filename, errno); + } - virtual Status NewLogger(const std::string& fname, Logger** result) { - FILE* f = fopen(fname.c_str(), "w"); - if (f == NULL) { - *result = NULL; - return IOError(fname, errno); + std::FILE* fp = ::fdopen(fd, "w"); + if (fp == nullptr) { + ::close(fd); + *result = nullptr; + return PosixError(filename, errno); } else { - *result = new PosixLogger(f, &PosixEnv::gettid); + *result = new PosixLogger(fp); return Status::OK(); } } - virtual uint64_t NowMicros() { - struct timeval tv; - gettimeofday(&tv, NULL); - return static_cast<uint64_t>(tv.tv_sec) * 1000000 + tv.tv_usec; + uint64_t NowMicros() override { + static constexpr uint64_t kUsecondsPerSecond = 1000000; + struct ::timeval tv; + ::gettimeofday(&tv, nullptr); + return static_cast<uint64_t>(tv.tv_sec) * kUsecondsPerSecond + tv.tv_usec; } - virtual void SleepForMicroseconds(int micros) { - usleep(micros); + void SleepForMicroseconds(int micros) override { + std::this_thread::sleep_for(std::chrono::microseconds(micros)); } private: - void PthreadCall(const char* label, int result) { - if (result != 0) { - fprintf(stderr, "pthread %s: %s\n", label, strerror(result)); - abort(); - } - } + void BackgroundThreadMain(); - // BGThread() is the body of the background thread - void BGThread(); - static void* BGThreadWrapper(void* arg) { - reinterpret_cast<PosixEnv*>(arg)->BGThread(); - return NULL; + static void BackgroundThreadEntryPoint(PosixEnv* env) { + env->BackgroundThreadMain(); } - pthread_mutex_t mu_; - pthread_cond_t bgsignal_; - pthread_t bgthread_; - bool started_bgthread_; + // Stores the work item data in a Schedule() call. + // + // Instances are constructed on the thread calling Schedule() and used on the + // background thread. + // + // This structure is thread-safe beacuse it is immutable. + struct BackgroundWorkItem { + explicit BackgroundWorkItem(void (*function)(void* arg), void* arg) + : function(function), arg(arg) {} + + void (*const function)(void*); + void* const arg; + }; - // Entry per Schedule() call - struct BGItem { void* arg; void (*function)(void*); }; - typedef std::deque<BGItem> BGQueue; - BGQueue queue_; + port::Mutex background_work_mutex_; + port::CondVar background_work_cv_ GUARDED_BY(background_work_mutex_); + bool started_background_thread_ GUARDED_BY(background_work_mutex_); - PosixLockTable locks_; - Limiter mmap_limit_; - Limiter fd_limit_; + std::queue<BackgroundWorkItem> background_work_queue_ + GUARDED_BY(background_work_mutex_); + + PosixLockTable locks_; // Thread-safe. + Limiter mmap_limiter_; // Thread-safe. + Limiter fd_limiter_; // Thread-safe. }; // Return the maximum number of concurrent mmaps. -static int MaxMmaps() { - if (mmap_limit >= 0) { - return mmap_limit; - } - // Up to 4096 mmaps for 64-bit binaries; none for smaller pointer sizes. - mmap_limit = sizeof(void*) >= 8 ? 4096 : 0; - return mmap_limit; -} +int MaxMmaps() { return g_mmap_limit; } // Return the maximum number of read-only files to keep open. -static intptr_t MaxOpenFiles() { - if (open_read_only_file_limit >= 0) { - return open_read_only_file_limit; +int MaxOpenFiles() { + if (g_open_read_only_file_limit >= 0) { + return g_open_read_only_file_limit; } - struct rlimit rlim; - if (getrlimit(RLIMIT_NOFILE, &rlim)) { + struct ::rlimit rlim; + if (::getrlimit(RLIMIT_NOFILE, &rlim)) { // getrlimit failed, fallback to hard-coded default. - open_read_only_file_limit = 50; + g_open_read_only_file_limit = 50; } else if (rlim.rlim_cur == RLIM_INFINITY) { - open_read_only_file_limit = std::numeric_limits<int>::max(); + g_open_read_only_file_limit = std::numeric_limits<int>::max(); } else { // Allow use of 20% of available file descriptors for read-only files. - open_read_only_file_limit = rlim.rlim_cur / 5; + g_open_read_only_file_limit = rlim.rlim_cur / 5; } - return open_read_only_file_limit; + return g_open_read_only_file_limit; } +} // namespace + PosixEnv::PosixEnv() - : started_bgthread_(false), - mmap_limit_(MaxMmaps()), - fd_limit_(MaxOpenFiles()) { - PthreadCall("mutex_init", pthread_mutex_init(&mu_, NULL)); - PthreadCall("cvar_init", pthread_cond_init(&bgsignal_, NULL)); -} + : background_work_cv_(&background_work_mutex_), + started_background_thread_(false), + mmap_limiter_(MaxMmaps()), + fd_limiter_(MaxOpenFiles()) {} -void PosixEnv::Schedule(void (*function)(void*), void* arg) { - PthreadCall("lock", pthread_mutex_lock(&mu_)); +void PosixEnv::Schedule( + void (*background_work_function)(void* background_work_arg), + void* background_work_arg) { + background_work_mutex_.Lock(); - // Start background thread if necessary - if (!started_bgthread_) { - started_bgthread_ = true; - PthreadCall( - "create thread", - pthread_create(&bgthread_, NULL, &PosixEnv::BGThreadWrapper, this)); + // Start the background thread, if we haven't done so already. + if (!started_background_thread_) { + started_background_thread_ = true; + std::thread background_thread(PosixEnv::BackgroundThreadEntryPoint, this); + background_thread.detach(); } - // If the queue is currently empty, the background thread may currently be - // waiting. - if (queue_.empty()) { - PthreadCall("signal", pthread_cond_signal(&bgsignal_)); + // If the queue is empty, the background thread may be waiting for work. + if (background_work_queue_.empty()) { + background_work_cv_.Signal(); } - // Add to priority queue - queue_.push_back(BGItem()); - queue_.back().function = function; - queue_.back().arg = arg; - - PthreadCall("unlock", pthread_mutex_unlock(&mu_)); + background_work_queue_.emplace(background_work_function, background_work_arg); + background_work_mutex_.Unlock(); } -void PosixEnv::BGThread() { +void PosixEnv::BackgroundThreadMain() { while (true) { - // Wait until there is an item that is ready to run - PthreadCall("lock", pthread_mutex_lock(&mu_)); - while (queue_.empty()) { - PthreadCall("wait", pthread_cond_wait(&bgsignal_, &mu_)); + background_work_mutex_.Lock(); + + // Wait until there is work to be done. + while (background_work_queue_.empty()) { + background_work_cv_.Wait(); } - void (*function)(void*) = queue_.front().function; - void* arg = queue_.front().arg; - queue_.pop_front(); + assert(!background_work_queue_.empty()); + auto background_work_function = background_work_queue_.front().function; + void* background_work_arg = background_work_queue_.front().arg; + background_work_queue_.pop(); - PthreadCall("unlock", pthread_mutex_unlock(&mu_)); - (*function)(arg); + background_work_mutex_.Unlock(); + background_work_function(background_work_arg); } } namespace { -struct StartThreadState { - void (*user_function)(void*); - void* arg; + +// Wraps an Env instance whose destructor is never created. +// +// Intended usage: +// using PlatformSingletonEnv = SingletonEnv<PlatformEnv>; +// void ConfigurePosixEnv(int param) { +// PlatformSingletonEnv::AssertEnvNotInitialized(); +// // set global configuration flags. +// } +// Env* Env::Default() { +// static PlatformSingletonEnv default_env; +// return default_env.env(); +// } +template <typename EnvType> +class SingletonEnv { + public: + SingletonEnv() { +#if !defined(NDEBUG) + env_initialized_.store(true, std::memory_order::memory_order_relaxed); +#endif // !defined(NDEBUG) + static_assert(sizeof(env_storage_) >= sizeof(EnvType), + "env_storage_ will not fit the Env"); + static_assert(alignof(decltype(env_storage_)) >= alignof(EnvType), + "env_storage_ does not meet the Env's alignment needs"); + new (&env_storage_) EnvType(); + } + ~SingletonEnv() = default; + + SingletonEnv(const SingletonEnv&) = delete; + SingletonEnv& operator=(const SingletonEnv&) = delete; + + Env* env() { return reinterpret_cast<Env*>(&env_storage_); } + + static void AssertEnvNotInitialized() { +#if !defined(NDEBUG) + assert(!env_initialized_.load(std::memory_order::memory_order_relaxed)); +#endif // !defined(NDEBUG) + } + + private: + typename std::aligned_storage<sizeof(EnvType), alignof(EnvType)>::type + env_storage_; +#if !defined(NDEBUG) + static std::atomic<bool> env_initialized_; +#endif // !defined(NDEBUG) }; -} -static void* StartThreadWrapper(void* arg) { - StartThreadState* state = reinterpret_cast<StartThreadState*>(arg); - state->user_function(state->arg); - delete state; - return NULL; -} -void PosixEnv::StartThread(void (*function)(void* arg), void* arg) { - pthread_t t; - StartThreadState* state = new StartThreadState; - state->user_function = function; - state->arg = arg; - PthreadCall("start thread", - pthread_create(&t, NULL, &StartThreadWrapper, state)); -} +#if !defined(NDEBUG) +template <typename EnvType> +std::atomic<bool> SingletonEnv<EnvType>::env_initialized_; +#endif // !defined(NDEBUG) -} // namespace +using PosixDefaultEnv = SingletonEnv<PosixEnv>; -static pthread_once_t once = PTHREAD_ONCE_INIT; -static Env* default_env; -static void InitDefaultEnv() { default_env = new PosixEnv; } +} // namespace void EnvPosixTestHelper::SetReadOnlyFDLimit(int limit) { - assert(default_env == NULL); - open_read_only_file_limit = limit; + PosixDefaultEnv::AssertEnvNotInitialized(); + g_open_read_only_file_limit = limit; } void EnvPosixTestHelper::SetReadOnlyMMapLimit(int limit) { - assert(default_env == NULL); - mmap_limit = limit; + PosixDefaultEnv::AssertEnvNotInitialized(); + g_mmap_limit = limit; } Env* Env::Default() { - pthread_once(&once, InitDefaultEnv); - return default_env; + static PosixDefaultEnv env_container; + return env_container.env(); } } // namespace leveldb - -#endif diff --git a/src/leveldb/util/env_posix_test.cc b/src/leveldb/util/env_posix_test.cc index 295f8ae440..9675d739ad 100644 --- a/src/leveldb/util/env_posix_test.cc +++ b/src/leveldb/util/env_posix_test.cc @@ -2,27 +2,182 @@ // 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 "leveldb/env.h" +#include <sys/resource.h> +#include <sys/wait.h> +#include <unistd.h> + +#include <cstdio> +#include <cstdlib> +#include <cstring> +#include <string> +#include <unordered_set> +#include <vector> +#include "leveldb/env.h" #include "port/port.h" -#include "util/testharness.h" #include "util/env_posix_test_helper.h" +#include "util/testharness.h" + +#if HAVE_O_CLOEXEC + +namespace { + +// Exit codes for the helper process spawned by TestCloseOnExec* tests. +// Useful for debugging test failures. +constexpr int kTextCloseOnExecHelperExecFailedCode = 61; +constexpr int kTextCloseOnExecHelperDup2FailedCode = 62; +constexpr int kTextCloseOnExecHelperFoundOpenFdCode = 63; + +// Global set by main() and read in TestCloseOnExec. +// +// The argv[0] value is stored in a std::vector instead of a std::string because +// std::string does not return a mutable pointer to its buffer until C++17. +// +// The vector stores the string pointed to by argv[0], plus the trailing null. +std::vector<char>* GetArgvZero() { + static std::vector<char> program_name; + return &program_name; +} + +// Command-line switch used to run this test as the CloseOnExecSwitch helper. +static const char kTestCloseOnExecSwitch[] = "--test-close-on-exec-helper"; + +// Executed in a separate process by TestCloseOnExec* tests. +// +// main() delegates to this function when the test executable is launched with +// a special command-line switch. TestCloseOnExec* tests fork()+exec() the test +// executable and pass the special command-line switch. +// + +// main() delegates to this function when the test executable is launched with +// a special command-line switch. TestCloseOnExec* tests fork()+exec() the test +// executable and pass the special command-line switch. +// +// When main() delegates to this function, the process probes whether a given +// file descriptor is open, and communicates the result via its exit code. +int TestCloseOnExecHelperMain(char* pid_arg) { + int fd = std::atoi(pid_arg); + // When given the same file descriptor twice, dup2() returns -1 if the + // file descriptor is closed, or the given file descriptor if it is open. + if (::dup2(fd, fd) == fd) { + std::fprintf(stderr, "Unexpected open fd %d\n", fd); + return kTextCloseOnExecHelperFoundOpenFdCode; + } + // Double-check that dup2() is saying the file descriptor is closed. + if (errno != EBADF) { + std::fprintf(stderr, "Unexpected errno after calling dup2 on fd %d: %s\n", + fd, std::strerror(errno)); + return kTextCloseOnExecHelperDup2FailedCode; + } + return 0; +} + +// File descriptors are small non-negative integers. +// +// Returns void so the implementation can use ASSERT_EQ. +void GetMaxFileDescriptor(int* result_fd) { + // Get the maximum file descriptor number. + ::rlimit fd_rlimit; + ASSERT_EQ(0, ::getrlimit(RLIMIT_NOFILE, &fd_rlimit)); + *result_fd = fd_rlimit.rlim_cur; +} + +// Iterates through all possible FDs and returns the currently open ones. +// +// Returns void so the implementation can use ASSERT_EQ. +void GetOpenFileDescriptors(std::unordered_set<int>* open_fds) { + int max_fd = 0; + GetMaxFileDescriptor(&max_fd); + + for (int fd = 0; fd < max_fd; ++fd) { + if (::dup2(fd, fd) != fd) { + // When given the same file descriptor twice, dup2() returns -1 if the + // file descriptor is closed, or the given file descriptor if it is open. + // + // Double-check that dup2() is saying the fd is closed. + ASSERT_EQ(EBADF, errno) + << "dup2() should set errno to EBADF on closed file descriptors"; + continue; + } + open_fds->insert(fd); + } +} + +// Finds an FD open since a previous call to GetOpenFileDescriptors(). +// +// |baseline_open_fds| is the result of a previous GetOpenFileDescriptors() +// call. Assumes that exactly one FD was opened since that call. +// +// Returns void so the implementation can use ASSERT_EQ. +void GetNewlyOpenedFileDescriptor( + const std::unordered_set<int>& baseline_open_fds, int* result_fd) { + std::unordered_set<int> open_fds; + GetOpenFileDescriptors(&open_fds); + for (int fd : baseline_open_fds) { + ASSERT_EQ(1, open_fds.count(fd)) + << "Previously opened file descriptor was closed during test setup"; + open_fds.erase(fd); + } + ASSERT_EQ(1, open_fds.size()) + << "Expected exactly one newly opened file descriptor during test setup"; + *result_fd = *open_fds.begin(); +} + +// Check that a fork()+exec()-ed child process does not have an extra open FD. +void CheckCloseOnExecDoesNotLeakFDs( + const std::unordered_set<int>& baseline_open_fds) { + // Prepare the argument list for the child process. + // execv() wants mutable buffers. + char switch_buffer[sizeof(kTestCloseOnExecSwitch)]; + std::memcpy(switch_buffer, kTestCloseOnExecSwitch, + sizeof(kTestCloseOnExecSwitch)); + + int probed_fd; + GetNewlyOpenedFileDescriptor(baseline_open_fds, &probed_fd); + std::string fd_string = std::to_string(probed_fd); + std::vector<char> fd_buffer(fd_string.begin(), fd_string.end()); + fd_buffer.emplace_back('\0'); + + // The helper process is launched with the command below. + // env_posix_tests --test-close-on-exec-helper 3 + char* child_argv[] = {GetArgvZero()->data(), switch_buffer, fd_buffer.data(), + nullptr}; + + constexpr int kForkInChildProcessReturnValue = 0; + int child_pid = fork(); + if (child_pid == kForkInChildProcessReturnValue) { + ::execv(child_argv[0], child_argv); + std::fprintf(stderr, "Error spawning child process: %s\n", strerror(errno)); + std::exit(kTextCloseOnExecHelperExecFailedCode); + } + + int child_status = 0; + ASSERT_EQ(child_pid, ::waitpid(child_pid, &child_status, 0)); + ASSERT_TRUE(WIFEXITED(child_status)) + << "The helper process did not exit with an exit code"; + ASSERT_EQ(0, WEXITSTATUS(child_status)) + << "The helper process encountered an error"; +} + +} // namespace + +#endif // HAVE_O_CLOEXEC namespace leveldb { -static const int kDelayMicros = 100000; static const int kReadOnlyFileLimit = 4; static const int kMMapLimit = 4; class EnvPosixTest { public: - Env* env_; - EnvPosixTest() : env_(Env::Default()) { } - static void SetFileLimits(int read_only_file_limit, int mmap_limit) { EnvPosixTestHelper::SetReadOnlyFDLimit(read_only_file_limit); EnvPosixTestHelper::SetReadOnlyMMapLimit(mmap_limit); } + + EnvPosixTest() : env_(Env::Default()) {} + + Env* env_; }; TEST(EnvPosixTest, TestOpenOnRead) { @@ -31,8 +186,8 @@ TEST(EnvPosixTest, TestOpenOnRead) { ASSERT_OK(env_->GetTestDirectory(&test_dir)); std::string test_file = test_dir + "/open_on_read.txt"; - FILE* f = fopen(test_file.c_str(), "w"); - ASSERT_TRUE(f != NULL); + FILE* f = fopen(test_file.c_str(), "we"); + ASSERT_TRUE(f != nullptr); const char kFileData[] = "abcdefghijklmnopqrstuvwxyz"; fputs(kFileData, f); fclose(f); @@ -56,9 +211,138 @@ TEST(EnvPosixTest, TestOpenOnRead) { ASSERT_OK(env_->DeleteFile(test_file)); } +#if HAVE_O_CLOEXEC + +TEST(EnvPosixTest, TestCloseOnExecSequentialFile) { + std::unordered_set<int> open_fds; + GetOpenFileDescriptors(&open_fds); + + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + std::string file_path = test_dir + "/close_on_exec_sequential.txt"; + ASSERT_OK(WriteStringToFile(env_, "0123456789", file_path)); + + leveldb::SequentialFile* file = nullptr; + ASSERT_OK(env_->NewSequentialFile(file_path, &file)); + CheckCloseOnExecDoesNotLeakFDs(open_fds); + delete file; + + ASSERT_OK(env_->DeleteFile(file_path)); +} + +TEST(EnvPosixTest, TestCloseOnExecRandomAccessFile) { + std::unordered_set<int> open_fds; + GetOpenFileDescriptors(&open_fds); + + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + std::string file_path = test_dir + "/close_on_exec_random_access.txt"; + ASSERT_OK(WriteStringToFile(env_, "0123456789", file_path)); + + // Exhaust the RandomAccessFile mmap limit. This way, the test + // RandomAccessFile instance below is backed by a file descriptor, not by an + // mmap region. + leveldb::RandomAccessFile* mmapped_files[kReadOnlyFileLimit] = {nullptr}; + for (int i = 0; i < kReadOnlyFileLimit; i++) { + ASSERT_OK(env_->NewRandomAccessFile(file_path, &mmapped_files[i])); + } + + leveldb::RandomAccessFile* file = nullptr; + ASSERT_OK(env_->NewRandomAccessFile(file_path, &file)); + CheckCloseOnExecDoesNotLeakFDs(open_fds); + delete file; + + for (int i = 0; i < kReadOnlyFileLimit; i++) { + delete mmapped_files[i]; + } + ASSERT_OK(env_->DeleteFile(file_path)); +} + +TEST(EnvPosixTest, TestCloseOnExecWritableFile) { + std::unordered_set<int> open_fds; + GetOpenFileDescriptors(&open_fds); + + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + std::string file_path = test_dir + "/close_on_exec_writable.txt"; + ASSERT_OK(WriteStringToFile(env_, "0123456789", file_path)); + + leveldb::WritableFile* file = nullptr; + ASSERT_OK(env_->NewWritableFile(file_path, &file)); + CheckCloseOnExecDoesNotLeakFDs(open_fds); + delete file; + + ASSERT_OK(env_->DeleteFile(file_path)); +} + +TEST(EnvPosixTest, TestCloseOnExecAppendableFile) { + std::unordered_set<int> open_fds; + GetOpenFileDescriptors(&open_fds); + + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + std::string file_path = test_dir + "/close_on_exec_appendable.txt"; + ASSERT_OK(WriteStringToFile(env_, "0123456789", file_path)); + + leveldb::WritableFile* file = nullptr; + ASSERT_OK(env_->NewAppendableFile(file_path, &file)); + CheckCloseOnExecDoesNotLeakFDs(open_fds); + delete file; + + ASSERT_OK(env_->DeleteFile(file_path)); +} + +TEST(EnvPosixTest, TestCloseOnExecLockFile) { + std::unordered_set<int> open_fds; + GetOpenFileDescriptors(&open_fds); + + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + std::string file_path = test_dir + "/close_on_exec_lock.txt"; + ASSERT_OK(WriteStringToFile(env_, "0123456789", file_path)); + + leveldb::FileLock* lock = nullptr; + ASSERT_OK(env_->LockFile(file_path, &lock)); + CheckCloseOnExecDoesNotLeakFDs(open_fds); + ASSERT_OK(env_->UnlockFile(lock)); + + ASSERT_OK(env_->DeleteFile(file_path)); +} + +TEST(EnvPosixTest, TestCloseOnExecLogger) { + std::unordered_set<int> open_fds; + GetOpenFileDescriptors(&open_fds); + + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + std::string file_path = test_dir + "/close_on_exec_logger.txt"; + ASSERT_OK(WriteStringToFile(env_, "0123456789", file_path)); + + leveldb::Logger* file = nullptr; + ASSERT_OK(env_->NewLogger(file_path, &file)); + CheckCloseOnExecDoesNotLeakFDs(open_fds); + delete file; + + ASSERT_OK(env_->DeleteFile(file_path)); +} + +#endif // HAVE_O_CLOEXEC + } // namespace leveldb int main(int argc, char** argv) { +#if HAVE_O_CLOEXEC + // Check if we're invoked as a helper program, or as the test suite. + for (int i = 1; i < argc; ++i) { + if (!std::strcmp(argv[i], kTestCloseOnExecSwitch)) { + return TestCloseOnExecHelperMain(argv[i + 1]); + } + } + + // Save argv[0] early, because googletest may modify argv. + GetArgvZero()->assign(argv[0], argv[0] + std::strlen(argv[0]) + 1); +#endif // HAVE_O_CLOEXEC + // All tests currently run with the same read-only file limits. leveldb::EnvPosixTest::SetFileLimits(leveldb::kReadOnlyFileLimit, leveldb::kMMapLimit); diff --git a/src/leveldb/util/env_test.cc b/src/leveldb/util/env_test.cc index 839ae56a1a..7db03fc11c 100644 --- a/src/leveldb/util/env_test.cc +++ b/src/leveldb/util/env_test.cc @@ -4,72 +4,144 @@ #include "leveldb/env.h" +#include <algorithm> + #include "port/port.h" +#include "port/thread_annotations.h" +#include "util/mutexlock.h" #include "util/testharness.h" +#include "util/testutil.h" namespace leveldb { static const int kDelayMicros = 100000; -static const int kReadOnlyFileLimit = 4; -static const int kMMapLimit = 4; class EnvTest { - private: - port::Mutex mu_; - std::string events_; - public: + EnvTest() : env_(Env::Default()) {} + Env* env_; - EnvTest() : env_(Env::Default()) { } }; -static void SetBool(void* ptr) { - reinterpret_cast<port::AtomicPointer*>(ptr)->NoBarrier_Store(ptr); +TEST(EnvTest, ReadWrite) { + Random rnd(test::RandomSeed()); + + // Get file to use for testing. + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + std::string test_file_name = test_dir + "/open_on_read.txt"; + WritableFile* writable_file; + ASSERT_OK(env_->NewWritableFile(test_file_name, &writable_file)); + + // Fill a file with data generated via a sequence of randomly sized writes. + static const size_t kDataSize = 10 * 1048576; + std::string data; + while (data.size() < kDataSize) { + int len = rnd.Skewed(18); // Up to 2^18 - 1, but typically much smaller + std::string r; + test::RandomString(&rnd, len, &r); + ASSERT_OK(writable_file->Append(r)); + data += r; + if (rnd.OneIn(10)) { + ASSERT_OK(writable_file->Flush()); + } + } + ASSERT_OK(writable_file->Sync()); + ASSERT_OK(writable_file->Close()); + delete writable_file; + + // Read all data using a sequence of randomly sized reads. + SequentialFile* sequential_file; + ASSERT_OK(env_->NewSequentialFile(test_file_name, &sequential_file)); + std::string read_result; + std::string scratch; + while (read_result.size() < data.size()) { + int len = std::min<int>(rnd.Skewed(18), data.size() - read_result.size()); + scratch.resize(std::max(len, 1)); // at least 1 so &scratch[0] is legal + Slice read; + ASSERT_OK(sequential_file->Read(len, &read, &scratch[0])); + if (len > 0) { + ASSERT_GT(read.size(), 0); + } + ASSERT_LE(read.size(), len); + read_result.append(read.data(), read.size()); + } + ASSERT_EQ(read_result, data); + delete sequential_file; } TEST(EnvTest, RunImmediately) { - port::AtomicPointer called (NULL); - env_->Schedule(&SetBool, &called); - env_->SleepForMicroseconds(kDelayMicros); - ASSERT_TRUE(called.NoBarrier_Load() != NULL); + struct RunState { + port::Mutex mu; + port::CondVar cvar{&mu}; + bool called = false; + + static void Run(void* arg) { + RunState* state = reinterpret_cast<RunState*>(arg); + MutexLock l(&state->mu); + ASSERT_EQ(state->called, false); + state->called = true; + state->cvar.Signal(); + } + }; + + RunState state; + env_->Schedule(&RunState::Run, &state); + + MutexLock l(&state.mu); + while (!state.called) { + state.cvar.Wait(); + } } TEST(EnvTest, RunMany) { - port::AtomicPointer last_id (NULL); + struct RunState { + port::Mutex mu; + port::CondVar cvar{&mu}; + int last_id = 0; + }; + + struct Callback { + RunState* state_; // Pointer to shared state. + const int id_; // Order# for the execution of this callback. - struct CB { - port::AtomicPointer* last_id_ptr; // Pointer to shared slot - uintptr_t id; // Order# for the execution of this callback + Callback(RunState* s, int id) : state_(s), id_(id) {} - CB(port::AtomicPointer* p, int i) : last_id_ptr(p), id(i) { } + static void Run(void* arg) { + Callback* callback = reinterpret_cast<Callback*>(arg); + RunState* state = callback->state_; - static void Run(void* v) { - CB* cb = reinterpret_cast<CB*>(v); - void* cur = cb->last_id_ptr->NoBarrier_Load(); - ASSERT_EQ(cb->id-1, reinterpret_cast<uintptr_t>(cur)); - cb->last_id_ptr->Release_Store(reinterpret_cast<void*>(cb->id)); + MutexLock l(&state->mu); + ASSERT_EQ(state->last_id, callback->id_ - 1); + state->last_id = callback->id_; + state->cvar.Signal(); } }; - // Schedule in different order than start time - CB cb1(&last_id, 1); - CB cb2(&last_id, 2); - CB cb3(&last_id, 3); - CB cb4(&last_id, 4); - env_->Schedule(&CB::Run, &cb1); - env_->Schedule(&CB::Run, &cb2); - env_->Schedule(&CB::Run, &cb3); - env_->Schedule(&CB::Run, &cb4); - - env_->SleepForMicroseconds(kDelayMicros); - void* cur = last_id.Acquire_Load(); - ASSERT_EQ(4, reinterpret_cast<uintptr_t>(cur)); + RunState state; + Callback callback1(&state, 1); + Callback callback2(&state, 2); + Callback callback3(&state, 3); + Callback callback4(&state, 4); + env_->Schedule(&Callback::Run, &callback1); + env_->Schedule(&Callback::Run, &callback2); + env_->Schedule(&Callback::Run, &callback3); + env_->Schedule(&Callback::Run, &callback4); + + MutexLock l(&state.mu); + while (state.last_id != 4) { + state.cvar.Wait(); + } } struct State { port::Mutex mu; - int val; - int num_running; + port::CondVar cvar{&mu}; + + int val GUARDED_BY(mu); + int num_running GUARDED_BY(mu); + + State(int val, int num_running) : val(val), num_running(num_running) {} }; static void ThreadBody(void* arg) { @@ -77,30 +149,89 @@ static void ThreadBody(void* arg) { s->mu.Lock(); s->val += 1; s->num_running -= 1; + s->cvar.Signal(); s->mu.Unlock(); } TEST(EnvTest, StartThread) { - State state; - state.val = 0; - state.num_running = 3; + State state(0, 3); for (int i = 0; i < 3; i++) { env_->StartThread(&ThreadBody, &state); } - while (true) { - state.mu.Lock(); - int num = state.num_running; - state.mu.Unlock(); - if (num == 0) { - break; - } - env_->SleepForMicroseconds(kDelayMicros); + + MutexLock l(&state.mu); + while (state.num_running != 0) { + state.cvar.Wait(); } ASSERT_EQ(state.val, 3); } -} // namespace leveldb +TEST(EnvTest, TestOpenNonExistentFile) { + // Write some test data to a single file that will be opened |n| times. + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + + std::string non_existent_file = test_dir + "/non_existent_file"; + ASSERT_TRUE(!env_->FileExists(non_existent_file)); + + RandomAccessFile* random_access_file; + Status status = + env_->NewRandomAccessFile(non_existent_file, &random_access_file); + ASSERT_TRUE(status.IsNotFound()); -int main(int argc, char** argv) { - return leveldb::test::RunAllTests(); + SequentialFile* sequential_file; + status = env_->NewSequentialFile(non_existent_file, &sequential_file); + ASSERT_TRUE(status.IsNotFound()); } + +TEST(EnvTest, ReopenWritableFile) { + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + std::string test_file_name = test_dir + "/reopen_writable_file.txt"; + env_->DeleteFile(test_file_name); + + WritableFile* writable_file; + ASSERT_OK(env_->NewWritableFile(test_file_name, &writable_file)); + std::string data("hello world!"); + ASSERT_OK(writable_file->Append(data)); + ASSERT_OK(writable_file->Close()); + delete writable_file; + + ASSERT_OK(env_->NewWritableFile(test_file_name, &writable_file)); + data = "42"; + ASSERT_OK(writable_file->Append(data)); + ASSERT_OK(writable_file->Close()); + delete writable_file; + + ASSERT_OK(ReadFileToString(env_, test_file_name, &data)); + ASSERT_EQ(std::string("42"), data); + env_->DeleteFile(test_file_name); +} + +TEST(EnvTest, ReopenAppendableFile) { + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + std::string test_file_name = test_dir + "/reopen_appendable_file.txt"; + env_->DeleteFile(test_file_name); + + WritableFile* appendable_file; + ASSERT_OK(env_->NewAppendableFile(test_file_name, &appendable_file)); + std::string data("hello world!"); + ASSERT_OK(appendable_file->Append(data)); + ASSERT_OK(appendable_file->Close()); + delete appendable_file; + + ASSERT_OK(env_->NewAppendableFile(test_file_name, &appendable_file)); + data = "42"; + ASSERT_OK(appendable_file->Append(data)); + ASSERT_OK(appendable_file->Close()); + delete appendable_file; + + ASSERT_OK(ReadFileToString(env_, test_file_name, &data)); + ASSERT_EQ(std::string("hello world!42"), data); + env_->DeleteFile(test_file_name); +} + +} // namespace leveldb + +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } diff --git a/src/leveldb/util/env_win.cc b/src/leveldb/util/env_win.cc deleted file mode 100644 index 830332abe9..0000000000 --- a/src/leveldb/util/env_win.cc +++ /dev/null @@ -1,902 +0,0 @@ -// This file contains source that originates from: -// http://code.google.com/p/leveldbwin/source/browse/trunk/win32_impl_src/env_win32.h -// http://code.google.com/p/leveldbwin/source/browse/trunk/win32_impl_src/port_win32.cc -// Those files don't have any explicit license headers but the -// project (http://code.google.com/p/leveldbwin/) lists the 'New BSD License' -// as the license. -#if defined(LEVELDB_PLATFORM_WINDOWS) -#include <map> - - -#include "leveldb/env.h" - -#include "port/port.h" -#include "leveldb/slice.h" -#include "util/logging.h" - -#include <shlwapi.h> -#include <process.h> -#include <cstring> -#include <stdio.h> -#include <errno.h> -#include <io.h> -#include <algorithm> - -#ifdef max -#undef max -#endif - -#ifndef va_copy -#define va_copy(d,s) ((d) = (s)) -#endif - -#if defined DeleteFile -#undef DeleteFile -#endif - -//Declarations -namespace leveldb -{ - -namespace Win32 -{ - -#define DISALLOW_COPY_AND_ASSIGN(TypeName) \ - TypeName(const TypeName&); \ - void operator=(const TypeName&) - -std::string GetCurrentDir(); -std::wstring GetCurrentDirW(); - -static const std::string CurrentDir = GetCurrentDir(); -static const std::wstring CurrentDirW = GetCurrentDirW(); - -std::string& ModifyPath(std::string& path); -std::wstring& ModifyPath(std::wstring& path); - -std::string GetLastErrSz(); -std::wstring GetLastErrSzW(); - -size_t GetPageSize(); - -typedef void (*ScheduleProc)(void*) ; - -struct WorkItemWrapper -{ - WorkItemWrapper(ScheduleProc proc_,void* content_); - ScheduleProc proc; - void* pContent; -}; - -DWORD WINAPI WorkItemWrapperProc(LPVOID pContent); - -class Win32SequentialFile : public SequentialFile -{ -public: - friend class Win32Env; - virtual ~Win32SequentialFile(); - virtual Status Read(size_t n, Slice* result, char* scratch); - virtual Status Skip(uint64_t n); - BOOL isEnable(); - virtual std::string GetName() const { return _filename; } -private: - BOOL _Init(); - void _CleanUp(); - Win32SequentialFile(const std::string& fname); - std::string _filename; - ::HANDLE _hFile; - DISALLOW_COPY_AND_ASSIGN(Win32SequentialFile); -}; - -class Win32RandomAccessFile : public RandomAccessFile -{ -public: - friend class Win32Env; - virtual ~Win32RandomAccessFile(); - virtual Status Read(uint64_t offset, size_t n, Slice* result,char* scratch) const; - BOOL isEnable(); - virtual std::string GetName() const { return _filename; } -private: - BOOL _Init(LPCWSTR path); - void _CleanUp(); - Win32RandomAccessFile(const std::string& fname); - HANDLE _hFile; - const std::string _filename; - DISALLOW_COPY_AND_ASSIGN(Win32RandomAccessFile); -}; - -class Win32WritableFile : public WritableFile -{ -public: - Win32WritableFile(const std::string& fname, bool append); - ~Win32WritableFile(); - - virtual Status Append(const Slice& data); - virtual Status Close(); - virtual Status Flush(); - virtual Status Sync(); - BOOL isEnable(); - virtual std::string GetName() const { return filename_; } -private: - std::string filename_; - ::HANDLE _hFile; -}; - -class Win32FileLock : public FileLock -{ -public: - friend class Win32Env; - virtual ~Win32FileLock(); - BOOL isEnable(); -private: - BOOL _Init(LPCWSTR path); - void _CleanUp(); - Win32FileLock(const std::string& fname); - HANDLE _hFile; - std::string _filename; - DISALLOW_COPY_AND_ASSIGN(Win32FileLock); -}; - -class Win32Logger : public Logger -{ -public: - friend class Win32Env; - virtual ~Win32Logger(); - virtual void Logv(const char* format, va_list ap); -private: - explicit Win32Logger(WritableFile* pFile); - WritableFile* _pFileProxy; - DISALLOW_COPY_AND_ASSIGN(Win32Logger); -}; - -class Win32Env : public Env -{ -public: - Win32Env(); - virtual ~Win32Env(); - virtual Status NewSequentialFile(const std::string& fname, - SequentialFile** result); - - virtual Status NewRandomAccessFile(const std::string& fname, - RandomAccessFile** result); - virtual Status NewWritableFile(const std::string& fname, - WritableFile** result); - virtual Status NewAppendableFile(const std::string& fname, - WritableFile** result); - - virtual bool FileExists(const std::string& fname); - - virtual Status GetChildren(const std::string& dir, - std::vector<std::string>* result); - - virtual Status DeleteFile(const std::string& fname); - - virtual Status CreateDir(const std::string& dirname); - - virtual Status DeleteDir(const std::string& dirname); - - virtual Status GetFileSize(const std::string& fname, uint64_t* file_size); - - virtual Status RenameFile(const std::string& src, - const std::string& target); - - virtual Status LockFile(const std::string& fname, FileLock** lock); - - virtual Status UnlockFile(FileLock* lock); - - virtual void Schedule( - void (*function)(void* arg), - void* arg); - - virtual void StartThread(void (*function)(void* arg), void* arg); - - virtual Status GetTestDirectory(std::string* path); - - //virtual void Logv(WritableFile* log, const char* format, va_list ap); - - virtual Status NewLogger(const std::string& fname, Logger** result); - - virtual uint64_t NowMicros(); - - virtual void SleepForMicroseconds(int micros); -}; - -void ToWidePath(const std::string& value, std::wstring& target) { - wchar_t buffer[MAX_PATH]; - MultiByteToWideChar(CP_UTF8, 0, value.c_str(), -1, buffer, MAX_PATH); - target = buffer; -} - -void ToNarrowPath(const std::wstring& value, std::string& target) { - char buffer[MAX_PATH]; - WideCharToMultiByte(CP_UTF8, 0, value.c_str(), -1, buffer, MAX_PATH, NULL, NULL); - target = buffer; -} - -std::wstring GetCurrentDirW() -{ - WCHAR path[MAX_PATH]; - ::GetModuleFileNameW(::GetModuleHandleW(NULL),path,MAX_PATH); - *wcsrchr(path,L'\\') = 0; - return std::wstring(path); -} - -std::string GetCurrentDir() -{ - std::string path; - ToNarrowPath(GetCurrentDirW(), path); - return path; -} - -std::string& ModifyPath(std::string& path) -{ - if(path[0] == '/' || path[0] == '\\'){ - path = CurrentDir + path; - } - std::replace(path.begin(),path.end(),'/','\\'); - - return path; -} - -std::wstring& ModifyPath(std::wstring& path) -{ - if(path[0] == L'/' || path[0] == L'\\'){ - path = CurrentDirW + path; - } - std::replace(path.begin(),path.end(),L'/',L'\\'); - return path; -} - -std::string GetLastErrSz() -{ - LPWSTR lpMsgBuf; - FormatMessageW( - FORMAT_MESSAGE_ALLOCATE_BUFFER | - FORMAT_MESSAGE_FROM_SYSTEM | - FORMAT_MESSAGE_IGNORE_INSERTS, - NULL, - GetLastError(), - 0, // Default language - (LPWSTR) &lpMsgBuf, - 0, - NULL - ); - std::string Err; - ToNarrowPath(lpMsgBuf, Err); - LocalFree( lpMsgBuf ); - return Err; -} - -std::wstring GetLastErrSzW() -{ - LPVOID lpMsgBuf; - FormatMessageW( - FORMAT_MESSAGE_ALLOCATE_BUFFER | - FORMAT_MESSAGE_FROM_SYSTEM | - FORMAT_MESSAGE_IGNORE_INSERTS, - NULL, - GetLastError(), - 0, // Default language - (LPWSTR) &lpMsgBuf, - 0, - NULL - ); - std::wstring Err = (LPCWSTR)lpMsgBuf; - LocalFree(lpMsgBuf); - return Err; -} - -WorkItemWrapper::WorkItemWrapper( ScheduleProc proc_,void* content_ ) : - proc(proc_),pContent(content_) -{ - -} - -DWORD WINAPI WorkItemWrapperProc(LPVOID pContent) -{ - WorkItemWrapper* item = static_cast<WorkItemWrapper*>(pContent); - ScheduleProc TempProc = item->proc; - void* arg = item->pContent; - delete item; - TempProc(arg); - return 0; -} - -size_t GetPageSize() -{ - SYSTEM_INFO si; - GetSystemInfo(&si); - return std::max(si.dwPageSize,si.dwAllocationGranularity); -} - -const size_t g_PageSize = GetPageSize(); - - -Win32SequentialFile::Win32SequentialFile( const std::string& fname ) : - _filename(fname),_hFile(NULL) -{ - _Init(); -} - -Win32SequentialFile::~Win32SequentialFile() -{ - _CleanUp(); -} - -Status Win32SequentialFile::Read( size_t n, Slice* result, char* scratch ) -{ - Status sRet; - DWORD hasRead = 0; - if(_hFile && ReadFile(_hFile,scratch,n,&hasRead,NULL) ){ - *result = Slice(scratch,hasRead); - } else { - sRet = Status::IOError(_filename, Win32::GetLastErrSz() ); - } - return sRet; -} - -Status Win32SequentialFile::Skip( uint64_t n ) -{ - Status sRet; - LARGE_INTEGER Move,NowPointer; - Move.QuadPart = n; - if(!SetFilePointerEx(_hFile,Move,&NowPointer,FILE_CURRENT)){ - sRet = Status::IOError(_filename,Win32::GetLastErrSz()); - } - return sRet; -} - -BOOL Win32SequentialFile::isEnable() -{ - return _hFile ? TRUE : FALSE; -} - -BOOL Win32SequentialFile::_Init() -{ - std::wstring path; - ToWidePath(_filename, path); - _hFile = CreateFileW(path.c_str(), - GENERIC_READ, - FILE_SHARE_READ | FILE_SHARE_WRITE, - NULL, - OPEN_EXISTING, - FILE_ATTRIBUTE_NORMAL | FILE_FLAG_SEQUENTIAL_SCAN, - NULL); - if (_hFile == INVALID_HANDLE_VALUE) - _hFile = NULL; - return _hFile ? TRUE : FALSE; -} - -void Win32SequentialFile::_CleanUp() -{ - if(_hFile){ - CloseHandle(_hFile); - _hFile = NULL; - } -} - -Win32RandomAccessFile::Win32RandomAccessFile( const std::string& fname ) : - _filename(fname),_hFile(NULL) -{ - std::wstring path; - ToWidePath(fname, path); - _Init( path.c_str() ); -} - -Win32RandomAccessFile::~Win32RandomAccessFile() -{ - _CleanUp(); -} - -Status Win32RandomAccessFile::Read(uint64_t offset,size_t n,Slice* result,char* scratch) const -{ - Status sRet; - OVERLAPPED ol = {0}; - ZeroMemory(&ol,sizeof(ol)); - ol.Offset = (DWORD)offset; - ol.OffsetHigh = (DWORD)(offset >> 32); - DWORD hasRead = 0; - if(!ReadFile(_hFile,scratch,n,&hasRead,&ol)) - sRet = Status::IOError(_filename,Win32::GetLastErrSz()); - else - *result = Slice(scratch,hasRead); - return sRet; -} - -BOOL Win32RandomAccessFile::_Init( LPCWSTR path ) -{ - BOOL bRet = FALSE; - if(!_hFile) - _hFile = ::CreateFileW(path,GENERIC_READ,FILE_SHARE_READ|FILE_SHARE_WRITE,NULL,OPEN_EXISTING, - FILE_ATTRIBUTE_NORMAL | FILE_FLAG_RANDOM_ACCESS,NULL); - if(!_hFile || _hFile == INVALID_HANDLE_VALUE ) - _hFile = NULL; - else - bRet = TRUE; - return bRet; -} - -BOOL Win32RandomAccessFile::isEnable() -{ - return _hFile ? TRUE : FALSE; -} - -void Win32RandomAccessFile::_CleanUp() -{ - if(_hFile){ - ::CloseHandle(_hFile); - _hFile = NULL; - } -} - -Win32WritableFile::Win32WritableFile(const std::string& fname, bool append) - : filename_(fname) -{ - std::wstring path; - ToWidePath(fname, path); - // NewAppendableFile: append to an existing file, or create a new one - // if none exists - this is OPEN_ALWAYS behavior, with - // FILE_APPEND_DATA to avoid having to manually position the file - // pointer at the end of the file. - // NewWritableFile: create a new file, delete if it exists - this is - // CREATE_ALWAYS behavior. This file is used for writing only so - // use GENERIC_WRITE. - _hFile = CreateFileW(path.c_str(), - append ? FILE_APPEND_DATA : GENERIC_WRITE, - FILE_SHARE_READ|FILE_SHARE_DELETE|FILE_SHARE_WRITE, - NULL, - append ? OPEN_ALWAYS : CREATE_ALWAYS, - FILE_ATTRIBUTE_NORMAL, - NULL); - // CreateFileW returns INVALID_HANDLE_VALUE in case of error, always check isEnable() before use -} - -Win32WritableFile::~Win32WritableFile() -{ - if (_hFile != INVALID_HANDLE_VALUE) - Close(); -} - -Status Win32WritableFile::Append(const Slice& data) -{ - DWORD r = 0; - if (!WriteFile(_hFile, data.data(), data.size(), &r, NULL) || r != data.size()) { - return Status::IOError("Win32WritableFile.Append::WriteFile: "+filename_, Win32::GetLastErrSz()); - } - return Status::OK(); -} - -Status Win32WritableFile::Close() -{ - if (!CloseHandle(_hFile)) { - return Status::IOError("Win32WritableFile.Close::CloseHandle: "+filename_, Win32::GetLastErrSz()); - } - _hFile = INVALID_HANDLE_VALUE; - return Status::OK(); -} - -Status Win32WritableFile::Flush() -{ - // Nothing to do here, there are no application-side buffers - return Status::OK(); -} - -Status Win32WritableFile::Sync() -{ - if (!FlushFileBuffers(_hFile)) { - return Status::IOError("Win32WritableFile.Sync::FlushFileBuffers "+filename_, Win32::GetLastErrSz()); - } - return Status::OK(); -} - -BOOL Win32WritableFile::isEnable() -{ - return _hFile != INVALID_HANDLE_VALUE; -} - -Win32FileLock::Win32FileLock( const std::string& fname ) : - _hFile(NULL),_filename(fname) -{ - std::wstring path; - ToWidePath(fname, path); - _Init(path.c_str()); -} - -Win32FileLock::~Win32FileLock() -{ - _CleanUp(); -} - -BOOL Win32FileLock::_Init( LPCWSTR path ) -{ - BOOL bRet = FALSE; - if(!_hFile) - _hFile = ::CreateFileW(path,0,0,NULL,CREATE_ALWAYS,FILE_ATTRIBUTE_NORMAL,NULL); - if(!_hFile || _hFile == INVALID_HANDLE_VALUE ){ - _hFile = NULL; - } - else - bRet = TRUE; - return bRet; -} - -void Win32FileLock::_CleanUp() -{ - ::CloseHandle(_hFile); - _hFile = NULL; -} - -BOOL Win32FileLock::isEnable() -{ - return _hFile ? TRUE : FALSE; -} - -Win32Logger::Win32Logger(WritableFile* pFile) : _pFileProxy(pFile) -{ - assert(_pFileProxy); -} - -Win32Logger::~Win32Logger() -{ - if(_pFileProxy) - delete _pFileProxy; -} - -void Win32Logger::Logv( const char* format, va_list ap ) -{ - uint64_t thread_id = ::GetCurrentThreadId(); - - // We try twice: the first time with a fixed-size stack allocated buffer, - // and the second time with a much larger dynamically allocated buffer. - char buffer[500]; - for (int iter = 0; iter < 2; iter++) { - char* base; - int bufsize; - if (iter == 0) { - bufsize = sizeof(buffer); - base = buffer; - } else { - bufsize = 30000; - base = new char[bufsize]; - } - char* p = base; - char* limit = base + bufsize; - - SYSTEMTIME st; - GetLocalTime(&st); - p += snprintf(p, limit - p, - "%04d/%02d/%02d-%02d:%02d:%02d.%06d %llx ", - int(st.wYear), - int(st.wMonth), - int(st.wDay), - int(st.wHour), - int(st.wMinute), - int(st.wMinute), - int(st.wMilliseconds), - static_cast<long long unsigned int>(thread_id)); - - // Print the message - if (p < limit) { - va_list backup_ap; - va_copy(backup_ap, ap); - p += vsnprintf(p, limit - p, format, backup_ap); - va_end(backup_ap); - } - - // Truncate to available space if necessary - if (p >= limit) { - if (iter == 0) { - continue; // Try again with larger buffer - } else { - p = limit - 1; - } - } - - // Add newline if necessary - if (p == base || p[-1] != '\n') { - *p++ = '\n'; - } - - assert(p <= limit); - DWORD hasWritten = 0; - if(_pFileProxy){ - _pFileProxy->Append(Slice(base, p - base)); - _pFileProxy->Flush(); - } - if (base != buffer) { - delete[] base; - } - break; - } -} - -bool Win32Env::FileExists(const std::string& fname) -{ - std::string path = fname; - std::wstring wpath; - ToWidePath(ModifyPath(path), wpath); - return ::PathFileExistsW(wpath.c_str()) ? true : false; -} - -Status Win32Env::GetChildren(const std::string& dir, std::vector<std::string>* result) -{ - Status sRet; - ::WIN32_FIND_DATAW wfd; - std::string path = dir; - ModifyPath(path); - path += "\\*.*"; - std::wstring wpath; - ToWidePath(path, wpath); - - ::HANDLE hFind = ::FindFirstFileW(wpath.c_str() ,&wfd); - if(hFind && hFind != INVALID_HANDLE_VALUE){ - BOOL hasNext = TRUE; - std::string child; - while(hasNext){ - ToNarrowPath(wfd.cFileName, child); - if(child != ".." && child != ".") { - result->push_back(child); - } - hasNext = ::FindNextFileW(hFind,&wfd); - } - ::FindClose(hFind); - } - else - sRet = Status::IOError(dir,"Could not get children."); - return sRet; -} - -void Win32Env::SleepForMicroseconds( int micros ) -{ - ::Sleep((micros + 999) /1000); -} - - -Status Win32Env::DeleteFile( const std::string& fname ) -{ - Status sRet; - std::string path = fname; - std::wstring wpath; - ToWidePath(ModifyPath(path), wpath); - - if(!::DeleteFileW(wpath.c_str())) { - sRet = Status::IOError(path, "Could not delete file."); - } - return sRet; -} - -Status Win32Env::GetFileSize( const std::string& fname, uint64_t* file_size ) -{ - Status sRet; - std::string path = fname; - std::wstring wpath; - ToWidePath(ModifyPath(path), wpath); - - HANDLE file = ::CreateFileW(wpath.c_str(), - GENERIC_READ,FILE_SHARE_READ|FILE_SHARE_WRITE,NULL,OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL,NULL); - LARGE_INTEGER li; - if(::GetFileSizeEx(file,&li)){ - *file_size = (uint64_t)li.QuadPart; - }else - sRet = Status::IOError(path,"Could not get the file size."); - CloseHandle(file); - return sRet; -} - -Status Win32Env::RenameFile( const std::string& src, const std::string& target ) -{ - Status sRet; - std::string src_path = src; - std::wstring wsrc_path; - ToWidePath(ModifyPath(src_path), wsrc_path); - std::string target_path = target; - std::wstring wtarget_path; - ToWidePath(ModifyPath(target_path), wtarget_path); - - if(!MoveFileW(wsrc_path.c_str(), wtarget_path.c_str() ) ){ - DWORD err = GetLastError(); - if(err == 0x000000b7){ - if(!::DeleteFileW(wtarget_path.c_str() ) ) - sRet = Status::IOError(src, "Could not rename file."); - else if(!::MoveFileW(wsrc_path.c_str(), - wtarget_path.c_str() ) ) - sRet = Status::IOError(src, "Could not rename file."); - } - } - return sRet; -} - -Status Win32Env::LockFile( const std::string& fname, FileLock** lock ) -{ - Status sRet; - std::string path = fname; - ModifyPath(path); - Win32FileLock* _lock = new Win32FileLock(path); - if(!_lock->isEnable()){ - delete _lock; - *lock = NULL; - sRet = Status::IOError(path, "Could not lock file."); - } - else - *lock = _lock; - return sRet; -} - -Status Win32Env::UnlockFile( FileLock* lock ) -{ - Status sRet; - delete lock; - return sRet; -} - -void Win32Env::Schedule( void (*function)(void* arg), void* arg ) -{ - QueueUserWorkItem(Win32::WorkItemWrapperProc, - new Win32::WorkItemWrapper(function,arg), - WT_EXECUTEDEFAULT); -} - -void Win32Env::StartThread( void (*function)(void* arg), void* arg ) -{ - ::_beginthread(function,0,arg); -} - -Status Win32Env::GetTestDirectory( std::string* path ) -{ - Status sRet; - WCHAR TempPath[MAX_PATH]; - ::GetTempPathW(MAX_PATH,TempPath); - ToNarrowPath(TempPath, *path); - path->append("leveldb\\test\\"); - ModifyPath(*path); - return sRet; -} - -uint64_t Win32Env::NowMicros() -{ -#ifndef USE_VISTA_API -#define GetTickCount64 GetTickCount -#endif - return (uint64_t)(GetTickCount64()*1000); -} - -static Status CreateDirInner( const std::string& dirname ) -{ - Status sRet; - std::wstring dirnameW; - ToWidePath(dirname, dirnameW); - DWORD attr = ::GetFileAttributesW(dirnameW.c_str()); - if (attr == INVALID_FILE_ATTRIBUTES) { // doesn't exist: - std::size_t slash = dirname.find_last_of("\\"); - if (slash != std::string::npos){ - sRet = CreateDirInner(dirname.substr(0, slash)); - if (!sRet.ok()) return sRet; - } - BOOL result = ::CreateDirectoryW(dirnameW.c_str(), NULL); - if (result == FALSE) { - sRet = Status::IOError(dirname, "Could not create directory."); - return sRet; - } - } - return sRet; -} - -Status Win32Env::CreateDir( const std::string& dirname ) -{ - std::string path = dirname; - if(path[path.length() - 1] != '\\'){ - path += '\\'; - } - ModifyPath(path); - - return CreateDirInner(path); -} - -Status Win32Env::DeleteDir( const std::string& dirname ) -{ - Status sRet; - std::wstring path; - ToWidePath(dirname, path); - ModifyPath(path); - if(!::RemoveDirectoryW( path.c_str() ) ){ - sRet = Status::IOError(dirname, "Could not delete directory."); - } - return sRet; -} - -Status Win32Env::NewSequentialFile( const std::string& fname, SequentialFile** result ) -{ - Status sRet; - std::string path = fname; - ModifyPath(path); - Win32SequentialFile* pFile = new Win32SequentialFile(path); - if(pFile->isEnable()){ - *result = pFile; - }else { - delete pFile; - sRet = Status::IOError(path, Win32::GetLastErrSz()); - } - return sRet; -} - -Status Win32Env::NewRandomAccessFile( const std::string& fname, RandomAccessFile** result ) -{ - Status sRet; - std::string path = fname; - Win32RandomAccessFile* pFile = new Win32RandomAccessFile(ModifyPath(path)); - if(!pFile->isEnable()){ - delete pFile; - *result = NULL; - sRet = Status::IOError(path, Win32::GetLastErrSz()); - }else - *result = pFile; - return sRet; -} - -Status Win32Env::NewLogger( const std::string& fname, Logger** result ) -{ - Status sRet; - std::string path = fname; - // Logs are opened with write semantics, not with append semantics - // (see PosixEnv::NewLogger) - Win32WritableFile* pMapFile = new Win32WritableFile(ModifyPath(path), false); - if(!pMapFile->isEnable()){ - delete pMapFile; - *result = NULL; - sRet = Status::IOError(path,"could not create a logger."); - }else - *result = new Win32Logger(pMapFile); - return sRet; -} - -Status Win32Env::NewWritableFile( const std::string& fname, WritableFile** result ) -{ - Status sRet; - std::string path = fname; - Win32WritableFile* pFile = new Win32WritableFile(ModifyPath(path), false); - if(!pFile->isEnable()){ - *result = NULL; - sRet = Status::IOError(fname,Win32::GetLastErrSz()); - }else - *result = pFile; - return sRet; -} - -Status Win32Env::NewAppendableFile( const std::string& fname, WritableFile** result ) -{ - Status sRet; - std::string path = fname; - Win32WritableFile* pFile = new Win32WritableFile(ModifyPath(path), true); - if(!pFile->isEnable()){ - *result = NULL; - sRet = Status::IOError(fname,Win32::GetLastErrSz()); - }else - *result = pFile; - return sRet; -} - -Win32Env::Win32Env() -{ - -} - -Win32Env::~Win32Env() -{ - -} - - -} // Win32 namespace - -static port::OnceType once = LEVELDB_ONCE_INIT; -static Env* default_env; -static void InitDefaultEnv() { default_env = new Win32::Win32Env(); } - -Env* Env::Default() { - port::InitOnce(&once, InitDefaultEnv); - return default_env; -} - -} // namespace leveldb - -#endif // defined(LEVELDB_PLATFORM_WINDOWS) diff --git a/src/leveldb/util/env_windows.cc b/src/leveldb/util/env_windows.cc new file mode 100644 index 0000000000..1834206562 --- /dev/null +++ b/src/leveldb/util/env_windows.cc @@ -0,0 +1,849 @@ +// Copyright (c) 2018 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. + +// Prevent Windows headers from defining min/max macros and instead +// use STL. +#ifndef NOMINMAX +#define NOMINMAX +#endif // ifndef NOMINMAX +#include <windows.h> + +#include <algorithm> +#include <atomic> +#include <chrono> +#include <condition_variable> +#include <cstddef> +#include <cstdint> +#include <cstdlib> +#include <cstring> +#include <memory> +#include <mutex> +#include <queue> +#include <sstream> +#include <string> +#include <vector> + +#include "leveldb/env.h" +#include "leveldb/slice.h" +#include "port/port.h" +#include "port/thread_annotations.h" +#include "util/env_windows_test_helper.h" +#include "util/logging.h" +#include "util/mutexlock.h" +#include "util/windows_logger.h" + +#if defined(DeleteFile) +#undef DeleteFile +#endif // defined(DeleteFile) + +namespace leveldb { + +namespace { + +constexpr const size_t kWritableFileBufferSize = 65536; + +// Up to 1000 mmaps for 64-bit binaries; none for 32-bit. +constexpr int kDefaultMmapLimit = (sizeof(void*) >= 8) ? 1000 : 0; + +// Can be set by by EnvWindowsTestHelper::SetReadOnlyMMapLimit(). +int g_mmap_limit = kDefaultMmapLimit; + +std::string GetWindowsErrorMessage(DWORD error_code) { + std::string message; + char* error_text = nullptr; + // Use MBCS version of FormatMessage to match return value. + size_t error_text_size = ::FormatMessageA( + FORMAT_MESSAGE_FROM_SYSTEM | FORMAT_MESSAGE_ALLOCATE_BUFFER | + FORMAT_MESSAGE_IGNORE_INSERTS, + nullptr, error_code, MAKELANGID(LANG_NEUTRAL, SUBLANG_DEFAULT), + reinterpret_cast<char*>(&error_text), 0, nullptr); + if (!error_text) { + return message; + } + message.assign(error_text, error_text_size); + ::LocalFree(error_text); + return message; +} + +Status WindowsError(const std::string& context, DWORD error_code) { + if (error_code == ERROR_FILE_NOT_FOUND || error_code == ERROR_PATH_NOT_FOUND) + return Status::NotFound(context, GetWindowsErrorMessage(error_code)); + return Status::IOError(context, GetWindowsErrorMessage(error_code)); +} + +class ScopedHandle { + public: + ScopedHandle(HANDLE handle) : handle_(handle) {} + ScopedHandle(const ScopedHandle&) = delete; + ScopedHandle(ScopedHandle&& other) noexcept : handle_(other.Release()) {} + ~ScopedHandle() { Close(); } + + ScopedHandle& operator=(const ScopedHandle&) = delete; + + ScopedHandle& operator=(ScopedHandle&& rhs) noexcept { + if (this != &rhs) handle_ = rhs.Release(); + return *this; + } + + bool Close() { + if (!is_valid()) { + return true; + } + HANDLE h = handle_; + handle_ = INVALID_HANDLE_VALUE; + return ::CloseHandle(h); + } + + bool is_valid() const { + return handle_ != INVALID_HANDLE_VALUE && handle_ != nullptr; + } + + HANDLE get() const { return handle_; } + + HANDLE Release() { + HANDLE h = handle_; + handle_ = INVALID_HANDLE_VALUE; + return h; + } + + private: + HANDLE handle_; +}; + +// Helper class to limit resource usage to avoid exhaustion. +// Currently used to limit read-only file descriptors and mmap file usage +// so that we do not run out of file descriptors or virtual memory, or run into +// kernel performance problems for very large databases. +class Limiter { + public: + // Limit maximum number of resources to |max_acquires|. + Limiter(int max_acquires) : acquires_allowed_(max_acquires) {} + + Limiter(const Limiter&) = delete; + Limiter operator=(const Limiter&) = delete; + + // If another resource is available, acquire it and return true. + // Else return false. + bool Acquire() { + int old_acquires_allowed = + acquires_allowed_.fetch_sub(1, std::memory_order_relaxed); + + if (old_acquires_allowed > 0) return true; + + acquires_allowed_.fetch_add(1, std::memory_order_relaxed); + return false; + } + + // Release a resource acquired by a previous call to Acquire() that returned + // true. + void Release() { acquires_allowed_.fetch_add(1, std::memory_order_relaxed); } + + private: + // The number of available resources. + // + // This is a counter and is not tied to the invariants of any other class, so + // it can be operated on safely using std::memory_order_relaxed. + std::atomic<int> acquires_allowed_; +}; + +class WindowsSequentialFile : public SequentialFile { + public: + WindowsSequentialFile(std::string filename, ScopedHandle handle) + : handle_(std::move(handle)), filename_(std::move(filename)) {} + ~WindowsSequentialFile() override {} + + Status Read(size_t n, Slice* result, char* scratch) override { + DWORD bytes_read; + // DWORD is 32-bit, but size_t could technically be larger. However leveldb + // files are limited to leveldb::Options::max_file_size which is clamped to + // 1<<30 or 1 GiB. + assert(n <= std::numeric_limits<DWORD>::max()); + if (!::ReadFile(handle_.get(), scratch, static_cast<DWORD>(n), &bytes_read, + nullptr)) { + return WindowsError(filename_, ::GetLastError()); + } + + *result = Slice(scratch, bytes_read); + return Status::OK(); + } + + Status Skip(uint64_t n) override { + LARGE_INTEGER distance; + distance.QuadPart = n; + if (!::SetFilePointerEx(handle_.get(), distance, nullptr, FILE_CURRENT)) { + return WindowsError(filename_, ::GetLastError()); + } + return Status::OK(); + } + + std::string GetName() const override { return filename_; } + + private: + const ScopedHandle handle_; + const std::string filename_; +}; + +class WindowsRandomAccessFile : public RandomAccessFile { + public: + WindowsRandomAccessFile(std::string filename, ScopedHandle handle) + : handle_(std::move(handle)), filename_(std::move(filename)) {} + + ~WindowsRandomAccessFile() override = default; + + Status Read(uint64_t offset, size_t n, Slice* result, + char* scratch) const override { + DWORD bytes_read = 0; + OVERLAPPED overlapped = {0}; + + overlapped.OffsetHigh = static_cast<DWORD>(offset >> 32); + overlapped.Offset = static_cast<DWORD>(offset); + if (!::ReadFile(handle_.get(), scratch, static_cast<DWORD>(n), &bytes_read, + &overlapped)) { + DWORD error_code = ::GetLastError(); + if (error_code != ERROR_HANDLE_EOF) { + *result = Slice(scratch, 0); + return Status::IOError(filename_, GetWindowsErrorMessage(error_code)); + } + } + + *result = Slice(scratch, bytes_read); + return Status::OK(); + } + + std::string GetName() const override { return filename_; } + + private: + const ScopedHandle handle_; + const std::string filename_; +}; + +class WindowsMmapReadableFile : public RandomAccessFile { + public: + // base[0,length-1] contains the mmapped contents of the file. + WindowsMmapReadableFile(std::string filename, char* mmap_base, size_t length, + Limiter* mmap_limiter) + : mmap_base_(mmap_base), + length_(length), + mmap_limiter_(mmap_limiter), + filename_(std::move(filename)) {} + + ~WindowsMmapReadableFile() override { + ::UnmapViewOfFile(mmap_base_); + mmap_limiter_->Release(); + } + + Status Read(uint64_t offset, size_t n, Slice* result, + char* scratch) const override { + if (offset + n > length_) { + *result = Slice(); + return WindowsError(filename_, ERROR_INVALID_PARAMETER); + } + + *result = Slice(mmap_base_ + offset, n); + return Status::OK(); + } + + std::string GetName() const override { return filename_; } + + private: + char* const mmap_base_; + const size_t length_; + Limiter* const mmap_limiter_; + const std::string filename_; +}; + +class WindowsWritableFile : public WritableFile { + public: + WindowsWritableFile(std::string filename, ScopedHandle handle) + : pos_(0), handle_(std::move(handle)), filename_(std::move(filename)) {} + + ~WindowsWritableFile() override = default; + + Status Append(const Slice& data) override { + size_t write_size = data.size(); + const char* write_data = data.data(); + + // Fit as much as possible into buffer. + size_t copy_size = std::min(write_size, kWritableFileBufferSize - pos_); + std::memcpy(buf_ + pos_, write_data, copy_size); + write_data += copy_size; + write_size -= copy_size; + pos_ += copy_size; + if (write_size == 0) { + return Status::OK(); + } + + // Can't fit in buffer, so need to do at least one write. + Status status = FlushBuffer(); + if (!status.ok()) { + return status; + } + + // Small writes go to buffer, large writes are written directly. + if (write_size < kWritableFileBufferSize) { + std::memcpy(buf_, write_data, write_size); + pos_ = write_size; + return Status::OK(); + } + return WriteUnbuffered(write_data, write_size); + } + + Status Close() override { + Status status = FlushBuffer(); + if (!handle_.Close() && status.ok()) { + status = WindowsError(filename_, ::GetLastError()); + } + return status; + } + + Status Flush() override { return FlushBuffer(); } + + Status Sync() override { + // On Windows no need to sync parent directory. Its metadata will be updated + // via the creation of the new file, without an explicit sync. + + Status status = FlushBuffer(); + if (!status.ok()) { + return status; + } + + if (!::FlushFileBuffers(handle_.get())) { + return Status::IOError(filename_, + GetWindowsErrorMessage(::GetLastError())); + } + return Status::OK(); + } + + std::string GetName() const override { return filename_; } + + private: + Status FlushBuffer() { + Status status = WriteUnbuffered(buf_, pos_); + pos_ = 0; + return status; + } + + Status WriteUnbuffered(const char* data, size_t size) { + DWORD bytes_written; + if (!::WriteFile(handle_.get(), data, static_cast<DWORD>(size), + &bytes_written, nullptr)) { + return Status::IOError(filename_, + GetWindowsErrorMessage(::GetLastError())); + } + return Status::OK(); + } + + // buf_[0, pos_-1] contains data to be written to handle_. + char buf_[kWritableFileBufferSize]; + size_t pos_; + + ScopedHandle handle_; + const std::string filename_; +}; + +// Lock or unlock the entire file as specified by |lock|. Returns true +// when successful, false upon failure. Caller should call ::GetLastError() +// to determine cause of failure +bool LockOrUnlock(HANDLE handle, bool lock) { + if (lock) { + return ::LockFile(handle, + /*dwFileOffsetLow=*/0, /*dwFileOffsetHigh=*/0, + /*nNumberOfBytesToLockLow=*/MAXDWORD, + /*nNumberOfBytesToLockHigh=*/MAXDWORD); + } else { + return ::UnlockFile(handle, + /*dwFileOffsetLow=*/0, /*dwFileOffsetHigh=*/0, + /*nNumberOfBytesToLockLow=*/MAXDWORD, + /*nNumberOfBytesToLockHigh=*/MAXDWORD); + } +} + +class WindowsFileLock : public FileLock { + public: + WindowsFileLock(ScopedHandle handle, std::string filename) + : handle_(std::move(handle)), filename_(std::move(filename)) {} + + const ScopedHandle& handle() const { return handle_; } + const std::string& filename() const { return filename_; } + + private: + const ScopedHandle handle_; + const std::string filename_; +}; + +class WindowsEnv : public Env { + public: + WindowsEnv(); + ~WindowsEnv() override { + static const char msg[] = + "WindowsEnv singleton destroyed. Unsupported behavior!\n"; + std::fwrite(msg, 1, sizeof(msg), stderr); + std::abort(); + } + + Status NewSequentialFile(const std::string& filename, + SequentialFile** result) override { + *result = nullptr; + DWORD desired_access = GENERIC_READ; + DWORD share_mode = FILE_SHARE_READ; + auto wFilename = toUtf16(filename); + ScopedHandle handle = ::CreateFileW( + wFilename.c_str(), desired_access, share_mode, + /*lpSecurityAttributes=*/nullptr, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, + /*hTemplateFile=*/nullptr); + if (!handle.is_valid()) { + return WindowsError(filename, ::GetLastError()); + } + + *result = new WindowsSequentialFile(filename, std::move(handle)); + return Status::OK(); + } + + Status NewRandomAccessFile(const std::string& filename, + RandomAccessFile** result) override { + *result = nullptr; + DWORD desired_access = GENERIC_READ; + DWORD share_mode = FILE_SHARE_READ; + auto wFilename = toUtf16(filename); + ScopedHandle handle = + ::CreateFileW(wFilename.c_str(), desired_access, share_mode, + /*lpSecurityAttributes=*/nullptr, OPEN_EXISTING, + FILE_ATTRIBUTE_READONLY, + /*hTemplateFile=*/nullptr); + if (!handle.is_valid()) { + return WindowsError(filename, ::GetLastError()); + } + if (!mmap_limiter_.Acquire()) { + *result = new WindowsRandomAccessFile(filename, std::move(handle)); + return Status::OK(); + } + + LARGE_INTEGER file_size; + Status status; + if (!::GetFileSizeEx(handle.get(), &file_size)) { + mmap_limiter_.Release(); + return WindowsError(filename, ::GetLastError()); + } + + ScopedHandle mapping = + ::CreateFileMappingW(handle.get(), + /*security attributes=*/nullptr, PAGE_READONLY, + /*dwMaximumSizeHigh=*/0, + /*dwMaximumSizeLow=*/0, + /*lpName=*/nullptr); + if (mapping.is_valid()) { + void* mmap_base = ::MapViewOfFile(mapping.get(), FILE_MAP_READ, + /*dwFileOffsetHigh=*/0, + /*dwFileOffsetLow=*/0, + /*dwNumberOfBytesToMap=*/0); + if (mmap_base) { + *result = new WindowsMmapReadableFile( + filename, reinterpret_cast<char*>(mmap_base), + static_cast<size_t>(file_size.QuadPart), &mmap_limiter_); + return Status::OK(); + } + } + mmap_limiter_.Release(); + return WindowsError(filename, ::GetLastError()); + } + + Status NewWritableFile(const std::string& filename, + WritableFile** result) override { + DWORD desired_access = GENERIC_WRITE; + DWORD share_mode = 0; // Exclusive access. + auto wFilename = toUtf16(filename); + ScopedHandle handle = ::CreateFileW( + wFilename.c_str(), desired_access, share_mode, + /*lpSecurityAttributes=*/nullptr, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, + /*hTemplateFile=*/nullptr); + if (!handle.is_valid()) { + *result = nullptr; + return WindowsError(filename, ::GetLastError()); + } + + *result = new WindowsWritableFile(filename, std::move(handle)); + return Status::OK(); + } + + Status NewAppendableFile(const std::string& filename, + WritableFile** result) override { + DWORD desired_access = FILE_APPEND_DATA; + DWORD share_mode = 0; // Exclusive access. + auto wFilename = toUtf16(filename); + ScopedHandle handle = ::CreateFileW( + wFilename.c_str(), desired_access, share_mode, + /*lpSecurityAttributes=*/nullptr, OPEN_ALWAYS, FILE_ATTRIBUTE_NORMAL, + /*hTemplateFile=*/nullptr); + if (!handle.is_valid()) { + *result = nullptr; + return WindowsError(filename, ::GetLastError()); + } + + *result = new WindowsWritableFile(filename, std::move(handle)); + return Status::OK(); + } + + bool FileExists(const std::string& filename) override { + auto wFilename = toUtf16(filename); + return GetFileAttributesW(wFilename.c_str()) != INVALID_FILE_ATTRIBUTES; + } + + Status GetChildren(const std::string& directory_path, + std::vector<std::string>* result) override { + const std::string find_pattern = directory_path + "\\*"; + WIN32_FIND_DATAW find_data; + auto wFind_pattern = toUtf16(find_pattern); + HANDLE dir_handle = ::FindFirstFileW(wFind_pattern.c_str(), &find_data); + if (dir_handle == INVALID_HANDLE_VALUE) { + DWORD last_error = ::GetLastError(); + if (last_error == ERROR_FILE_NOT_FOUND) { + return Status::OK(); + } + return WindowsError(directory_path, last_error); + } + do { + char base_name[_MAX_FNAME]; + char ext[_MAX_EXT]; + + auto find_data_filename = toUtf8(find_data.cFileName); + if (!_splitpath_s(find_data_filename.c_str(), nullptr, 0, nullptr, 0, + base_name, ARRAYSIZE(base_name), ext, ARRAYSIZE(ext))) { + result->emplace_back(std::string(base_name) + ext); + } + } while (::FindNextFileW(dir_handle, &find_data)); + DWORD last_error = ::GetLastError(); + ::FindClose(dir_handle); + if (last_error != ERROR_NO_MORE_FILES) { + return WindowsError(directory_path, last_error); + } + return Status::OK(); + } + + Status DeleteFile(const std::string& filename) override { + auto wFilename = toUtf16(filename); + if (!::DeleteFileW(wFilename.c_str())) { + return WindowsError(filename, ::GetLastError()); + } + return Status::OK(); + } + + Status CreateDir(const std::string& dirname) override { + auto wDirname = toUtf16(dirname); + if (!::CreateDirectoryW(wDirname.c_str(), nullptr)) { + return WindowsError(dirname, ::GetLastError()); + } + return Status::OK(); + } + + Status DeleteDir(const std::string& dirname) override { + auto wDirname = toUtf16(dirname); + if (!::RemoveDirectoryW(wDirname.c_str())) { + return WindowsError(dirname, ::GetLastError()); + } + return Status::OK(); + } + + Status GetFileSize(const std::string& filename, uint64_t* size) override { + WIN32_FILE_ATTRIBUTE_DATA file_attributes; + auto wFilename = toUtf16(filename); + if (!::GetFileAttributesExW(wFilename.c_str(), GetFileExInfoStandard, + &file_attributes)) { + return WindowsError(filename, ::GetLastError()); + } + ULARGE_INTEGER file_size; + file_size.HighPart = file_attributes.nFileSizeHigh; + file_size.LowPart = file_attributes.nFileSizeLow; + *size = file_size.QuadPart; + return Status::OK(); + } + + Status RenameFile(const std::string& from, const std::string& to) override { + // Try a simple move first. It will only succeed when |to| doesn't already + // exist. + auto wFrom = toUtf16(from); + auto wTo = toUtf16(to); + if (::MoveFileW(wFrom.c_str(), wTo.c_str())) { + return Status::OK(); + } + DWORD move_error = ::GetLastError(); + + // Try the full-blown replace if the move fails, as ReplaceFile will only + // succeed when |to| does exist. When writing to a network share, we may not + // be able to change the ACLs. Ignore ACL errors then + // (REPLACEFILE_IGNORE_MERGE_ERRORS). + if (::ReplaceFileW(wTo.c_str(), wFrom.c_str(), /*lpBackupFileName=*/nullptr, + REPLACEFILE_IGNORE_MERGE_ERRORS, + /*lpExclude=*/nullptr, /*lpReserved=*/nullptr)) { + return Status::OK(); + } + DWORD replace_error = ::GetLastError(); + // In the case of FILE_ERROR_NOT_FOUND from ReplaceFile, it is likely that + // |to| does not exist. In this case, the more relevant error comes from the + // call to MoveFile. + if (replace_error == ERROR_FILE_NOT_FOUND || + replace_error == ERROR_PATH_NOT_FOUND) { + return WindowsError(from, move_error); + } else { + return WindowsError(from, replace_error); + } + } + + Status LockFile(const std::string& filename, FileLock** lock) override { + *lock = nullptr; + Status result; + auto wFilename = toUtf16(filename); + ScopedHandle handle = ::CreateFileW( + wFilename.c_str(), GENERIC_READ | GENERIC_WRITE, FILE_SHARE_READ, + /*lpSecurityAttributes=*/nullptr, OPEN_ALWAYS, FILE_ATTRIBUTE_NORMAL, + nullptr); + if (!handle.is_valid()) { + result = WindowsError(filename, ::GetLastError()); + } else if (!LockOrUnlock(handle.get(), true)) { + result = WindowsError("lock " + filename, ::GetLastError()); + } else { + *lock = new WindowsFileLock(std::move(handle), filename); + } + return result; + } + + Status UnlockFile(FileLock* lock) override { + WindowsFileLock* windows_file_lock = + reinterpret_cast<WindowsFileLock*>(lock); + if (!LockOrUnlock(windows_file_lock->handle().get(), false)) { + return WindowsError("unlock " + windows_file_lock->filename(), + ::GetLastError()); + } + delete windows_file_lock; + return Status::OK(); + } + + void Schedule(void (*background_work_function)(void* background_work_arg), + void* background_work_arg) override; + + void StartThread(void (*thread_main)(void* thread_main_arg), + void* thread_main_arg) override { + std::thread new_thread(thread_main, thread_main_arg); + new_thread.detach(); + } + + Status GetTestDirectory(std::string* result) override { + const char* env = getenv("TEST_TMPDIR"); + if (env && env[0] != '\0') { + *result = env; + return Status::OK(); + } + + wchar_t wtmp_path[MAX_PATH]; + if (!GetTempPathW(ARRAYSIZE(wtmp_path), wtmp_path)) { + return WindowsError("GetTempPath", ::GetLastError()); + } + std::string tmp_path = toUtf8(std::wstring(wtmp_path)); + std::stringstream ss; + ss << tmp_path << "leveldbtest-" << std::this_thread::get_id(); + *result = ss.str(); + + // Directory may already exist + CreateDir(*result); + return Status::OK(); + } + + Status NewLogger(const std::string& filename, Logger** result) override { + auto wFilename = toUtf16(filename); + std::FILE* fp = _wfopen(wFilename.c_str(), L"w"); + if (fp == nullptr) { + *result = nullptr; + return WindowsError(filename, ::GetLastError()); + } else { + *result = new WindowsLogger(fp); + return Status::OK(); + } + } + + uint64_t NowMicros() override { + // GetSystemTimeAsFileTime typically has a resolution of 10-20 msec. + // TODO(cmumford): Switch to GetSystemTimePreciseAsFileTime which is + // available in Windows 8 and later. + FILETIME ft; + ::GetSystemTimeAsFileTime(&ft); + // Each tick represents a 100-nanosecond intervals since January 1, 1601 + // (UTC). + uint64_t num_ticks = + (static_cast<uint64_t>(ft.dwHighDateTime) << 32) + ft.dwLowDateTime; + return num_ticks / 10; + } + + void SleepForMicroseconds(int micros) override { + std::this_thread::sleep_for(std::chrono::microseconds(micros)); + } + + private: + void BackgroundThreadMain(); + + static void BackgroundThreadEntryPoint(WindowsEnv* env) { + env->BackgroundThreadMain(); + } + + // Stores the work item data in a Schedule() call. + // + // Instances are constructed on the thread calling Schedule() and used on the + // background thread. + // + // This structure is thread-safe beacuse it is immutable. + struct BackgroundWorkItem { + explicit BackgroundWorkItem(void (*function)(void* arg), void* arg) + : function(function), arg(arg) {} + + void (*const function)(void*); + void* const arg; + }; + + port::Mutex background_work_mutex_; + port::CondVar background_work_cv_ GUARDED_BY(background_work_mutex_); + bool started_background_thread_ GUARDED_BY(background_work_mutex_); + + std::queue<BackgroundWorkItem> background_work_queue_ + GUARDED_BY(background_work_mutex_); + + Limiter mmap_limiter_; // Thread-safe. + + // Converts a Windows wide multi-byte UTF-16 string to a UTF-8 string. + // See http://utf8everywhere.org/#windows + std::string toUtf8(const std::wstring& wstr) { + if (wstr.empty()) return std::string(); + int size_needed = WideCharToMultiByte( + CP_UTF8, 0, &wstr[0], (int)wstr.size(), NULL, 0, NULL, NULL); + std::string strTo(size_needed, 0); + WideCharToMultiByte(CP_UTF8, 0, &wstr[0], (int)wstr.size(), &strTo[0], + size_needed, NULL, NULL); + return strTo; + } + + // Converts a UTF-8 string to a Windows UTF-16 multi-byte wide character + // string. + // See http://utf8everywhere.org/#windows + std::wstring toUtf16(const std::string& str) { + if (str.empty()) return std::wstring(); + int size_needed = + MultiByteToWideChar(CP_UTF8, 0, &str[0], (int)str.size(), NULL, 0); + std::wstring strTo(size_needed, 0); + MultiByteToWideChar(CP_UTF8, 0, &str[0], (int)str.size(), &strTo[0], + size_needed); + return strTo; + } +}; + +// Return the maximum number of concurrent mmaps. +int MaxMmaps() { return g_mmap_limit; } + +WindowsEnv::WindowsEnv() + : background_work_cv_(&background_work_mutex_), + started_background_thread_(false), + mmap_limiter_(MaxMmaps()) {} + +void WindowsEnv::Schedule( + void (*background_work_function)(void* background_work_arg), + void* background_work_arg) { + background_work_mutex_.Lock(); + + // Start the background thread, if we haven't done so already. + if (!started_background_thread_) { + started_background_thread_ = true; + std::thread background_thread(WindowsEnv::BackgroundThreadEntryPoint, this); + background_thread.detach(); + } + + // If the queue is empty, the background thread may be waiting for work. + if (background_work_queue_.empty()) { + background_work_cv_.Signal(); + } + + background_work_queue_.emplace(background_work_function, background_work_arg); + background_work_mutex_.Unlock(); +} + +void WindowsEnv::BackgroundThreadMain() { + while (true) { + background_work_mutex_.Lock(); + + // Wait until there is work to be done. + while (background_work_queue_.empty()) { + background_work_cv_.Wait(); + } + + assert(!background_work_queue_.empty()); + auto background_work_function = background_work_queue_.front().function; + void* background_work_arg = background_work_queue_.front().arg; + background_work_queue_.pop(); + + background_work_mutex_.Unlock(); + background_work_function(background_work_arg); + } +} + +// Wraps an Env instance whose destructor is never created. +// +// Intended usage: +// using PlatformSingletonEnv = SingletonEnv<PlatformEnv>; +// void ConfigurePosixEnv(int param) { +// PlatformSingletonEnv::AssertEnvNotInitialized(); +// // set global configuration flags. +// } +// Env* Env::Default() { +// static PlatformSingletonEnv default_env; +// return default_env.env(); +// } +template <typename EnvType> +class SingletonEnv { + public: + SingletonEnv() { +#if !defined(NDEBUG) + env_initialized_.store(true, std::memory_order::memory_order_relaxed); +#endif // !defined(NDEBUG) + static_assert(sizeof(env_storage_) >= sizeof(EnvType), + "env_storage_ will not fit the Env"); + static_assert(alignof(decltype(env_storage_)) >= alignof(EnvType), + "env_storage_ does not meet the Env's alignment needs"); + new (&env_storage_) EnvType(); + } + ~SingletonEnv() = default; + + SingletonEnv(const SingletonEnv&) = delete; + SingletonEnv& operator=(const SingletonEnv&) = delete; + + Env* env() { return reinterpret_cast<Env*>(&env_storage_); } + + static void AssertEnvNotInitialized() { +#if !defined(NDEBUG) + assert(!env_initialized_.load(std::memory_order::memory_order_relaxed)); +#endif // !defined(NDEBUG) + } + + private: + typename std::aligned_storage<sizeof(EnvType), alignof(EnvType)>::type + env_storage_; +#if !defined(NDEBUG) + static std::atomic<bool> env_initialized_; +#endif // !defined(NDEBUG) +}; + +#if !defined(NDEBUG) +template <typename EnvType> +std::atomic<bool> SingletonEnv<EnvType>::env_initialized_; +#endif // !defined(NDEBUG) + +using WindowsDefaultEnv = SingletonEnv<WindowsEnv>; + +} // namespace + +void EnvWindowsTestHelper::SetReadOnlyMMapLimit(int limit) { + WindowsDefaultEnv::AssertEnvNotInitialized(); + g_mmap_limit = limit; +} + +Env* Env::Default() { + static WindowsDefaultEnv env_container; + return env_container.env(); +} + +} // namespace leveldb diff --git a/src/leveldb/util/env_windows_test.cc b/src/leveldb/util/env_windows_test.cc new file mode 100644 index 0000000000..3c22133891 --- /dev/null +++ b/src/leveldb/util/env_windows_test.cc @@ -0,0 +1,64 @@ +// Copyright (c) 2018 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 "leveldb/env.h" + +#include "port/port.h" +#include "util/env_windows_test_helper.h" +#include "util/testharness.h" + +namespace leveldb { + +static const int kMMapLimit = 4; + +class EnvWindowsTest { + public: + static void SetFileLimits(int mmap_limit) { + EnvWindowsTestHelper::SetReadOnlyMMapLimit(mmap_limit); + } + + EnvWindowsTest() : env_(Env::Default()) {} + + Env* env_; +}; + +TEST(EnvWindowsTest, TestOpenOnRead) { + // Write some test data to a single file that will be opened |n| times. + std::string test_dir; + ASSERT_OK(env_->GetTestDirectory(&test_dir)); + std::string test_file = test_dir + "/open_on_read.txt"; + + FILE* f = fopen(test_file.c_str(), "w"); + ASSERT_TRUE(f != nullptr); + const char kFileData[] = "abcdefghijklmnopqrstuvwxyz"; + fputs(kFileData, f); + fclose(f); + + // Open test file some number above the sum of the two limits to force + // leveldb::WindowsEnv to switch from mapping the file into memory + // to basic file reading. + const int kNumFiles = kMMapLimit + 5; + leveldb::RandomAccessFile* files[kNumFiles] = {0}; + for (int i = 0; i < kNumFiles; i++) { + ASSERT_OK(env_->NewRandomAccessFile(test_file, &files[i])); + } + char scratch; + Slice read_result; + for (int i = 0; i < kNumFiles; i++) { + ASSERT_OK(files[i]->Read(i, 1, &read_result, &scratch)); + ASSERT_EQ(kFileData[i], read_result[0]); + } + for (int i = 0; i < kNumFiles; i++) { + delete files[i]; + } + ASSERT_OK(env_->DeleteFile(test_file)); +} + +} // namespace leveldb + +int main(int argc, char** argv) { + // All tests currently run with the same read-only file limits. + leveldb::EnvWindowsTest::SetFileLimits(leveldb::kMMapLimit); + return leveldb::test::RunAllTests(); +} diff --git a/src/leveldb/util/env_windows_test_helper.h b/src/leveldb/util/env_windows_test_helper.h new file mode 100644 index 0000000000..e6f6020561 --- /dev/null +++ b/src/leveldb/util/env_windows_test_helper.h @@ -0,0 +1,25 @@ +// Copyright 2018 (c) 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_ENV_WINDOWS_TEST_HELPER_H_ +#define STORAGE_LEVELDB_UTIL_ENV_WINDOWS_TEST_HELPER_H_ + +namespace leveldb { + +class EnvWindowsTest; + +// A helper for the Windows Env to facilitate testing. +class EnvWindowsTestHelper { + private: + friend class CorruptionTest; + friend class EnvWindowsTest; + + // Set the maximum number of read-only files that will be mapped via mmap. + // Must be called before creating an Env. + static void SetReadOnlyMMapLimit(int limit); +}; + +} // namespace leveldb + +#endif // STORAGE_LEVELDB_UTIL_ENV_WINDOWS_TEST_HELPER_H_ diff --git a/src/leveldb/util/filter_policy.cc b/src/leveldb/util/filter_policy.cc index 7b045c8c91..90fd754d64 100644 --- a/src/leveldb/util/filter_policy.cc +++ b/src/leveldb/util/filter_policy.cc @@ -6,6 +6,6 @@ namespace leveldb { -FilterPolicy::~FilterPolicy() { } +FilterPolicy::~FilterPolicy() {} } // namespace leveldb diff --git a/src/leveldb/util/hash.cc b/src/leveldb/util/hash.cc index ed439ce7a2..dd47c110ee 100644 --- a/src/leveldb/util/hash.cc +++ b/src/leveldb/util/hash.cc @@ -2,15 +2,19 @@ // 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/hash.h" + #include <string.h> + #include "util/coding.h" -#include "util/hash.h" // The FALLTHROUGH_INTENDED macro can be used to annotate implicit fall-through // between switch labels. The real definition should be provided externally. // This one is a fallback version for unsupported compilers. #ifndef FALLTHROUGH_INTENDED -#define FALLTHROUGH_INTENDED do { } while (0) +#define FALLTHROUGH_INTENDED \ + do { \ + } while (0) #endif namespace leveldb { @@ -34,13 +38,13 @@ uint32_t Hash(const char* data, size_t n, uint32_t seed) { // Pick up remaining bytes switch (limit - data) { case 3: - h += static_cast<unsigned char>(data[2]) << 16; + h += static_cast<uint8_t>(data[2]) << 16; FALLTHROUGH_INTENDED; case 2: - h += static_cast<unsigned char>(data[1]) << 8; + h += static_cast<uint8_t>(data[1]) << 8; FALLTHROUGH_INTENDED; case 1: - h += static_cast<unsigned char>(data[0]); + h += static_cast<uint8_t>(data[0]); h *= m; h ^= (h >> r); break; @@ -48,5 +52,4 @@ uint32_t Hash(const char* data, size_t n, uint32_t seed) { return h; } - } // namespace leveldb diff --git a/src/leveldb/util/hash.h b/src/leveldb/util/hash.h index 8889d56be8..74bdb6e7b2 100644 --- a/src/leveldb/util/hash.h +++ b/src/leveldb/util/hash.h @@ -12,8 +12,8 @@ namespace leveldb { -extern uint32_t Hash(const char* data, size_t n, uint32_t seed); +uint32_t Hash(const char* data, size_t n, uint32_t seed); -} +} // namespace leveldb #endif // STORAGE_LEVELDB_UTIL_HASH_H_ diff --git a/src/leveldb/util/hash_test.cc b/src/leveldb/util/hash_test.cc index eaa1c92c23..21f8171da6 100644 --- a/src/leveldb/util/hash_test.cc +++ b/src/leveldb/util/hash_test.cc @@ -7,26 +7,18 @@ namespace leveldb { -class HASH { }; +class HASH {}; TEST(HASH, SignedUnsignedIssue) { - const unsigned char data1[1] = {0x62}; - const unsigned char data2[2] = {0xc3, 0x97}; - const unsigned char data3[3] = {0xe2, 0x99, 0xa5}; - const unsigned char data4[4] = {0xe1, 0x80, 0xb9, 0x32}; - const unsigned char data5[48] = { - 0x01, 0xc0, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, - 0x14, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x04, 0x00, - 0x00, 0x00, 0x00, 0x14, - 0x00, 0x00, 0x00, 0x18, - 0x28, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, - 0x02, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, + const uint8_t data1[1] = {0x62}; + const uint8_t data2[2] = {0xc3, 0x97}; + const uint8_t data3[3] = {0xe2, 0x99, 0xa5}; + const uint8_t data4[4] = {0xe1, 0x80, 0xb9, 0x32}; + const uint8_t data5[48] = { + 0x01, 0xc0, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x04, 0x00, + 0x00, 0x00, 0x00, 0x14, 0x00, 0x00, 0x00, 0x18, 0x28, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, }; ASSERT_EQ(Hash(0, 0, 0xbc9f1d34), 0xbc9f1d34); @@ -49,6 +41,4 @@ TEST(HASH, SignedUnsignedIssue) { } // namespace leveldb -int main(int argc, char** argv) { - return leveldb::test::RunAllTests(); -} +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } diff --git a/src/leveldb/util/histogram.cc b/src/leveldb/util/histogram.cc index bb95f583ea..65092c88f2 100644 --- a/src/leveldb/util/histogram.cc +++ b/src/leveldb/util/histogram.cc @@ -2,36 +2,174 @@ // 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/histogram.h" + #include <math.h> #include <stdio.h> + #include "port/port.h" -#include "util/histogram.h" namespace leveldb { const double Histogram::kBucketLimit[kNumBuckets] = { - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20, 25, 30, 35, 40, 45, - 50, 60, 70, 80, 90, 100, 120, 140, 160, 180, 200, 250, 300, 350, 400, 450, - 500, 600, 700, 800, 900, 1000, 1200, 1400, 1600, 1800, 2000, 2500, 3000, - 3500, 4000, 4500, 5000, 6000, 7000, 8000, 9000, 10000, 12000, 14000, - 16000, 18000, 20000, 25000, 30000, 35000, 40000, 45000, 50000, 60000, - 70000, 80000, 90000, 100000, 120000, 140000, 160000, 180000, 200000, - 250000, 300000, 350000, 400000, 450000, 500000, 600000, 700000, 800000, - 900000, 1000000, 1200000, 1400000, 1600000, 1800000, 2000000, 2500000, - 3000000, 3500000, 4000000, 4500000, 5000000, 6000000, 7000000, 8000000, - 9000000, 10000000, 12000000, 14000000, 16000000, 18000000, 20000000, - 25000000, 30000000, 35000000, 40000000, 45000000, 50000000, 60000000, - 70000000, 80000000, 90000000, 100000000, 120000000, 140000000, 160000000, - 180000000, 200000000, 250000000, 300000000, 350000000, 400000000, - 450000000, 500000000, 600000000, 700000000, 800000000, 900000000, - 1000000000, 1200000000, 1400000000, 1600000000, 1800000000, 2000000000, - 2500000000.0, 3000000000.0, 3500000000.0, 4000000000.0, 4500000000.0, - 5000000000.0, 6000000000.0, 7000000000.0, 8000000000.0, 9000000000.0, - 1e200, + 1, + 2, + 3, + 4, + 5, + 6, + 7, + 8, + 9, + 10, + 12, + 14, + 16, + 18, + 20, + 25, + 30, + 35, + 40, + 45, + 50, + 60, + 70, + 80, + 90, + 100, + 120, + 140, + 160, + 180, + 200, + 250, + 300, + 350, + 400, + 450, + 500, + 600, + 700, + 800, + 900, + 1000, + 1200, + 1400, + 1600, + 1800, + 2000, + 2500, + 3000, + 3500, + 4000, + 4500, + 5000, + 6000, + 7000, + 8000, + 9000, + 10000, + 12000, + 14000, + 16000, + 18000, + 20000, + 25000, + 30000, + 35000, + 40000, + 45000, + 50000, + 60000, + 70000, + 80000, + 90000, + 100000, + 120000, + 140000, + 160000, + 180000, + 200000, + 250000, + 300000, + 350000, + 400000, + 450000, + 500000, + 600000, + 700000, + 800000, + 900000, + 1000000, + 1200000, + 1400000, + 1600000, + 1800000, + 2000000, + 2500000, + 3000000, + 3500000, + 4000000, + 4500000, + 5000000, + 6000000, + 7000000, + 8000000, + 9000000, + 10000000, + 12000000, + 14000000, + 16000000, + 18000000, + 20000000, + 25000000, + 30000000, + 35000000, + 40000000, + 45000000, + 50000000, + 60000000, + 70000000, + 80000000, + 90000000, + 100000000, + 120000000, + 140000000, + 160000000, + 180000000, + 200000000, + 250000000, + 300000000, + 350000000, + 400000000, + 450000000, + 500000000, + 600000000, + 700000000, + 800000000, + 900000000, + 1000000000, + 1200000000, + 1400000000, + 1600000000, + 1800000000, + 2000000000, + 2500000000.0, + 3000000000.0, + 3500000000.0, + 4000000000.0, + 4500000000.0, + 5000000000.0, + 6000000000.0, + 7000000000.0, + 8000000000.0, + 9000000000.0, + 1e200, }; void Histogram::Clear() { - min_ = kBucketLimit[kNumBuckets-1]; + min_ = kBucketLimit[kNumBuckets - 1]; max_ = 0; num_ = 0; sum_ = 0; @@ -66,9 +204,7 @@ void Histogram::Merge(const Histogram& other) { } } -double Histogram::Median() const { - return Percentile(50.0); -} +double Histogram::Median() const { return Percentile(50.0); } double Histogram::Percentile(double p) const { double threshold = num_ * (p / 100.0); @@ -77,7 +213,7 @@ double Histogram::Percentile(double p) const { sum += buckets_[b]; if (sum >= threshold) { // Scale linearly within this bucket - double left_point = (b == 0) ? 0 : kBucketLimit[b-1]; + double left_point = (b == 0) ? 0 : kBucketLimit[b - 1]; double right_point = kBucketLimit[b]; double left_sum = sum - buckets_[b]; double right_sum = sum; @@ -105,12 +241,10 @@ double Histogram::StandardDeviation() const { std::string Histogram::ToString() const { std::string r; char buf[200]; - snprintf(buf, sizeof(buf), - "Count: %.0f Average: %.4f StdDev: %.2f\n", - num_, Average(), StandardDeviation()); + snprintf(buf, sizeof(buf), "Count: %.0f Average: %.4f StdDev: %.2f\n", num_, + Average(), StandardDeviation()); r.append(buf); - snprintf(buf, sizeof(buf), - "Min: %.4f Median: %.4f Max: %.4f\n", + snprintf(buf, sizeof(buf), "Min: %.4f Median: %.4f Max: %.4f\n", (num_ == 0.0 ? 0.0 : min_), Median(), max_); r.append(buf); r.append("------------------------------------------------------\n"); @@ -119,17 +253,16 @@ std::string Histogram::ToString() const { for (int b = 0; b < kNumBuckets; b++) { if (buckets_[b] <= 0.0) continue; sum += buckets_[b]; - snprintf(buf, sizeof(buf), - "[ %7.0f, %7.0f ) %7.0f %7.3f%% %7.3f%% ", - ((b == 0) ? 0.0 : kBucketLimit[b-1]), // left - kBucketLimit[b], // right - buckets_[b], // count - mult * buckets_[b], // percentage - mult * sum); // cumulative percentage + snprintf(buf, sizeof(buf), "[ %7.0f, %7.0f ) %7.0f %7.3f%% %7.3f%% ", + ((b == 0) ? 0.0 : kBucketLimit[b - 1]), // left + kBucketLimit[b], // right + buckets_[b], // count + mult * buckets_[b], // percentage + mult * sum); // cumulative percentage r.append(buf); // Add hash marks based on percentage; 20 marks for 100%. - int marks = static_cast<int>(20*(buckets_[b] / num_) + 0.5); + int marks = static_cast<int>(20 * (buckets_[b] / num_) + 0.5); r.append(marks, '#'); r.push_back('\n'); } diff --git a/src/leveldb/util/histogram.h b/src/leveldb/util/histogram.h index 1ef9f3c8ab..4da60fba45 100644 --- a/src/leveldb/util/histogram.h +++ b/src/leveldb/util/histogram.h @@ -11,8 +11,8 @@ namespace leveldb { class Histogram { public: - Histogram() { } - ~Histogram() { } + Histogram() {} + ~Histogram() {} void Clear(); void Add(double value); @@ -21,20 +21,22 @@ class Histogram { std::string ToString() const; private: + enum { kNumBuckets = 154 }; + + double Median() const; + double Percentile(double p) const; + double Average() const; + double StandardDeviation() const; + + static const double kBucketLimit[kNumBuckets]; + double min_; double max_; double num_; double sum_; double sum_squares_; - enum { kNumBuckets = 154 }; - static const double kBucketLimit[kNumBuckets]; double buckets_[kNumBuckets]; - - double Median() const; - double Percentile(double p) const; - double Average() const; - double StandardDeviation() const; }; } // namespace leveldb diff --git a/src/leveldb/util/logging.cc b/src/leveldb/util/logging.cc index db6160c8f1..75e9d037d3 100644 --- a/src/leveldb/util/logging.cc +++ b/src/leveldb/util/logging.cc @@ -8,6 +8,9 @@ #include <stdarg.h> #include <stdio.h> #include <stdlib.h> + +#include <limits> + #include "leveldb/env.h" #include "leveldb/slice.h" @@ -15,7 +18,7 @@ namespace leveldb { void AppendNumberTo(std::string* str, uint64_t num) { char buf[30]; - snprintf(buf, sizeof(buf), "%llu", (unsigned long long) num); + snprintf(buf, sizeof(buf), "%llu", (unsigned long long)num); str->append(buf); } @@ -46,27 +49,36 @@ std::string EscapeString(const Slice& value) { } bool ConsumeDecimalNumber(Slice* in, uint64_t* val) { - uint64_t v = 0; - int digits = 0; - while (!in->empty()) { - unsigned char c = (*in)[0]; - if (c >= '0' && c <= '9') { - ++digits; - const int delta = (c - '0'); - static const uint64_t kMaxUint64 = ~static_cast<uint64_t>(0); - if (v > kMaxUint64/10 || - (v == kMaxUint64/10 && delta > kMaxUint64%10)) { - // Overflow - return false; - } - v = (v * 10) + delta; - in->remove_prefix(1); - } else { - break; + // Constants that will be optimized away. + constexpr const uint64_t kMaxUint64 = std::numeric_limits<uint64_t>::max(); + constexpr const char kLastDigitOfMaxUint64 = + '0' + static_cast<char>(kMaxUint64 % 10); + + uint64_t value = 0; + + // reinterpret_cast-ing from char* to uint8_t* to avoid signedness. + const uint8_t* start = reinterpret_cast<const uint8_t*>(in->data()); + + const uint8_t* end = start + in->size(); + const uint8_t* current = start; + for (; current != end; ++current) { + const uint8_t ch = *current; + if (ch < '0' || ch > '9') break; + + // Overflow check. + // kMaxUint64 / 10 is also constant and will be optimized away. + if (value > kMaxUint64 / 10 || + (value == kMaxUint64 / 10 && ch > kLastDigitOfMaxUint64)) { + return false; } + + value = (value * 10) + (ch - '0'); } - *val = v; - return (digits > 0); + + *val = value; + const size_t digits_consumed = current - start; + in->remove_prefix(digits_consumed); + return digits_consumed != 0; } } // namespace leveldb diff --git a/src/leveldb/util/logging.h b/src/leveldb/util/logging.h index 1b450d2480..8ff2da86b4 100644 --- a/src/leveldb/util/logging.h +++ b/src/leveldb/util/logging.h @@ -8,9 +8,11 @@ #ifndef STORAGE_LEVELDB_UTIL_LOGGING_H_ #define STORAGE_LEVELDB_UTIL_LOGGING_H_ -#include <stdio.h> #include <stdint.h> +#include <stdio.h> + #include <string> + #include "port/port.h" namespace leveldb { @@ -19,24 +21,24 @@ class Slice; class WritableFile; // Append a human-readable printout of "num" to *str -extern void AppendNumberTo(std::string* str, uint64_t num); +void AppendNumberTo(std::string* str, uint64_t num); // Append a human-readable printout of "value" to *str. // Escapes any non-printable characters found in "value". -extern void AppendEscapedStringTo(std::string* str, const Slice& value); +void AppendEscapedStringTo(std::string* str, const Slice& value); // Return a human-readable printout of "num" -extern std::string NumberToString(uint64_t num); +std::string NumberToString(uint64_t num); // Return a human-readable version of "value". // Escapes any non-printable characters found in "value". -extern std::string EscapeString(const Slice& value); +std::string EscapeString(const Slice& value); // Parse a human-readable number from "*in" into *value. On success, // advances "*in" past the consumed number and sets "*val" to the // numeric value. Otherwise, returns false and leaves *in in an // unspecified state. -extern bool ConsumeDecimalNumber(Slice* in, uint64_t* val); +bool ConsumeDecimalNumber(Slice* in, uint64_t* val); } // namespace leveldb diff --git a/src/leveldb/util/logging_test.cc b/src/leveldb/util/logging_test.cc new file mode 100644 index 0000000000..389cbeb14f --- /dev/null +++ b/src/leveldb/util/logging_test.cc @@ -0,0 +1,143 @@ +// Copyright (c) 2018 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 <limits> +#include <string> + +#include "leveldb/slice.h" +#include "util/logging.h" +#include "util/testharness.h" + +namespace leveldb { + +class Logging {}; + +TEST(Logging, NumberToString) { + ASSERT_EQ("0", NumberToString(0)); + ASSERT_EQ("1", NumberToString(1)); + ASSERT_EQ("9", NumberToString(9)); + + ASSERT_EQ("10", NumberToString(10)); + ASSERT_EQ("11", NumberToString(11)); + ASSERT_EQ("19", NumberToString(19)); + ASSERT_EQ("99", NumberToString(99)); + + ASSERT_EQ("100", NumberToString(100)); + ASSERT_EQ("109", NumberToString(109)); + ASSERT_EQ("190", NumberToString(190)); + ASSERT_EQ("123", NumberToString(123)); + ASSERT_EQ("12345678", NumberToString(12345678)); + + static_assert(std::numeric_limits<uint64_t>::max() == 18446744073709551615U, + "Test consistency check"); + ASSERT_EQ("18446744073709551000", NumberToString(18446744073709551000U)); + ASSERT_EQ("18446744073709551600", NumberToString(18446744073709551600U)); + ASSERT_EQ("18446744073709551610", NumberToString(18446744073709551610U)); + ASSERT_EQ("18446744073709551614", NumberToString(18446744073709551614U)); + ASSERT_EQ("18446744073709551615", NumberToString(18446744073709551615U)); +} + +void ConsumeDecimalNumberRoundtripTest(uint64_t number, + const std::string& padding = "") { + std::string decimal_number = NumberToString(number); + std::string input_string = decimal_number + padding; + Slice input(input_string); + Slice output = input; + uint64_t result; + ASSERT_TRUE(ConsumeDecimalNumber(&output, &result)); + ASSERT_EQ(number, result); + ASSERT_EQ(decimal_number.size(), output.data() - input.data()); + ASSERT_EQ(padding.size(), output.size()); +} + +TEST(Logging, ConsumeDecimalNumberRoundtrip) { + ConsumeDecimalNumberRoundtripTest(0); + ConsumeDecimalNumberRoundtripTest(1); + ConsumeDecimalNumberRoundtripTest(9); + + ConsumeDecimalNumberRoundtripTest(10); + ConsumeDecimalNumberRoundtripTest(11); + ConsumeDecimalNumberRoundtripTest(19); + ConsumeDecimalNumberRoundtripTest(99); + + ConsumeDecimalNumberRoundtripTest(100); + ConsumeDecimalNumberRoundtripTest(109); + ConsumeDecimalNumberRoundtripTest(190); + ConsumeDecimalNumberRoundtripTest(123); + ASSERT_EQ("12345678", NumberToString(12345678)); + + for (uint64_t i = 0; i < 100; ++i) { + uint64_t large_number = std::numeric_limits<uint64_t>::max() - i; + ConsumeDecimalNumberRoundtripTest(large_number); + } +} + +TEST(Logging, ConsumeDecimalNumberRoundtripWithPadding) { + ConsumeDecimalNumberRoundtripTest(0, " "); + ConsumeDecimalNumberRoundtripTest(1, "abc"); + ConsumeDecimalNumberRoundtripTest(9, "x"); + + ConsumeDecimalNumberRoundtripTest(10, "_"); + ConsumeDecimalNumberRoundtripTest(11, std::string("\0\0\0", 3)); + ConsumeDecimalNumberRoundtripTest(19, "abc"); + ConsumeDecimalNumberRoundtripTest(99, "padding"); + + ConsumeDecimalNumberRoundtripTest(100, " "); + + for (uint64_t i = 0; i < 100; ++i) { + uint64_t large_number = std::numeric_limits<uint64_t>::max() - i; + ConsumeDecimalNumberRoundtripTest(large_number, "pad"); + } +} + +void ConsumeDecimalNumberOverflowTest(const std::string& input_string) { + Slice input(input_string); + Slice output = input; + uint64_t result; + ASSERT_EQ(false, ConsumeDecimalNumber(&output, &result)); +} + +TEST(Logging, ConsumeDecimalNumberOverflow) { + static_assert(std::numeric_limits<uint64_t>::max() == 18446744073709551615U, + "Test consistency check"); + ConsumeDecimalNumberOverflowTest("18446744073709551616"); + ConsumeDecimalNumberOverflowTest("18446744073709551617"); + ConsumeDecimalNumberOverflowTest("18446744073709551618"); + ConsumeDecimalNumberOverflowTest("18446744073709551619"); + ConsumeDecimalNumberOverflowTest("18446744073709551620"); + ConsumeDecimalNumberOverflowTest("18446744073709551621"); + ConsumeDecimalNumberOverflowTest("18446744073709551622"); + ConsumeDecimalNumberOverflowTest("18446744073709551623"); + ConsumeDecimalNumberOverflowTest("18446744073709551624"); + ConsumeDecimalNumberOverflowTest("18446744073709551625"); + ConsumeDecimalNumberOverflowTest("18446744073709551626"); + + ConsumeDecimalNumberOverflowTest("18446744073709551700"); + + ConsumeDecimalNumberOverflowTest("99999999999999999999"); +} + +void ConsumeDecimalNumberNoDigitsTest(const std::string& input_string) { + Slice input(input_string); + Slice output = input; + uint64_t result; + ASSERT_EQ(false, ConsumeDecimalNumber(&output, &result)); + ASSERT_EQ(input.data(), output.data()); + ASSERT_EQ(input.size(), output.size()); +} + +TEST(Logging, ConsumeDecimalNumberNoDigits) { + ConsumeDecimalNumberNoDigitsTest(""); + ConsumeDecimalNumberNoDigitsTest(" "); + ConsumeDecimalNumberNoDigitsTest("a"); + ConsumeDecimalNumberNoDigitsTest(" 123"); + ConsumeDecimalNumberNoDigitsTest("a123"); + ConsumeDecimalNumberNoDigitsTest(std::string("\000123", 4)); + ConsumeDecimalNumberNoDigitsTest(std::string("\177123", 4)); + ConsumeDecimalNumberNoDigitsTest(std::string("\377123", 4)); +} + +} // namespace leveldb + +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } diff --git a/src/leveldb/util/mutexlock.h b/src/leveldb/util/mutexlock.h index 1ff5a9efa1..0cb2e250fb 100644 --- a/src/leveldb/util/mutexlock.h +++ b/src/leveldb/util/mutexlock.h @@ -22,20 +22,18 @@ namespace leveldb { class SCOPED_LOCKABLE MutexLock { public: - explicit MutexLock(port::Mutex *mu) EXCLUSIVE_LOCK_FUNCTION(mu) - : mu_(mu) { + explicit MutexLock(port::Mutex* mu) EXCLUSIVE_LOCK_FUNCTION(mu) : mu_(mu) { this->mu_->Lock(); } ~MutexLock() UNLOCK_FUNCTION() { this->mu_->Unlock(); } + MutexLock(const MutexLock&) = delete; + MutexLock& operator=(const MutexLock&) = delete; + private: - port::Mutex *const mu_; - // No copying allowed - MutexLock(const MutexLock&); - void operator=(const MutexLock&); + port::Mutex* const mu_; }; } // namespace leveldb - #endif // STORAGE_LEVELDB_UTIL_MUTEXLOCK_H_ diff --git a/src/leveldb/util/no_destructor.h b/src/leveldb/util/no_destructor.h new file mode 100644 index 0000000000..a0d3b8703d --- /dev/null +++ b/src/leveldb/util/no_destructor.h @@ -0,0 +1,46 @@ +// Copyright (c) 2018 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_NO_DESTRUCTOR_H_ +#define STORAGE_LEVELDB_UTIL_NO_DESTRUCTOR_H_ + +#include <type_traits> +#include <utility> + +namespace leveldb { + +// Wraps an instance whose destructor is never called. +// +// This is intended for use with function-level static variables. +template <typename InstanceType> +class NoDestructor { + public: + template <typename... ConstructorArgTypes> + explicit NoDestructor(ConstructorArgTypes&&... constructor_args) { + static_assert(sizeof(instance_storage_) >= sizeof(InstanceType), + "instance_storage_ is not large enough to hold the instance"); + static_assert( + alignof(decltype(instance_storage_)) >= alignof(InstanceType), + "instance_storage_ does not meet the instance's alignment requirement"); + new (&instance_storage_) + InstanceType(std::forward<ConstructorArgTypes>(constructor_args)...); + } + + ~NoDestructor() = default; + + NoDestructor(const NoDestructor&) = delete; + NoDestructor& operator=(const NoDestructor&) = delete; + + InstanceType* get() { + return reinterpret_cast<InstanceType*>(&instance_storage_); + } + + private: + typename std::aligned_storage<sizeof(InstanceType), + alignof(InstanceType)>::type instance_storage_; +}; + +} // namespace leveldb + +#endif // STORAGE_LEVELDB_UTIL_NO_DESTRUCTOR_H_ diff --git a/src/leveldb/util/no_destructor_test.cc b/src/leveldb/util/no_destructor_test.cc new file mode 100644 index 0000000000..b41caca694 --- /dev/null +++ b/src/leveldb/util/no_destructor_test.cc @@ -0,0 +1,47 @@ +// Copyright (c) 2018 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 <cstdint> +#include <cstdlib> +#include <utility> + +#include "util/no_destructor.h" +#include "util/testharness.h" + +namespace leveldb { + +namespace { + +struct DoNotDestruct { + public: + DoNotDestruct(uint32_t a, uint64_t b) : a(a), b(b) {} + ~DoNotDestruct() { std::abort(); } + + // Used to check constructor argument forwarding. + uint32_t a; + uint64_t b; +}; + +constexpr const uint32_t kGoldenA = 0xdeadbeef; +constexpr const uint64_t kGoldenB = 0xaabbccddeeffaabb; + +} // namespace + +class NoDestructorTest {}; + +TEST(NoDestructorTest, StackInstance) { + NoDestructor<DoNotDestruct> instance(kGoldenA, kGoldenB); + ASSERT_EQ(kGoldenA, instance.get()->a); + ASSERT_EQ(kGoldenB, instance.get()->b); +} + +TEST(NoDestructorTest, StaticInstance) { + static NoDestructor<DoNotDestruct> instance(kGoldenA, kGoldenB); + ASSERT_EQ(kGoldenA, instance.get()->a); + ASSERT_EQ(kGoldenB, instance.get()->b); +} + +} // namespace leveldb + +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } diff --git a/src/leveldb/util/options.cc b/src/leveldb/util/options.cc index b5e6227613..62de5bf0d2 100644 --- a/src/leveldb/util/options.cc +++ b/src/leveldb/util/options.cc @@ -9,22 +9,6 @@ namespace leveldb { -Options::Options() - : comparator(BytewiseComparator()), - create_if_missing(false), - error_if_exists(false), - paranoid_checks(false), - env(Env::Default()), - info_log(NULL), - write_buffer_size(4<<20), - max_open_files(1000), - block_cache(NULL), - block_size(4096), - block_restart_interval(16), - max_file_size(2<<20), - compression(kSnappyCompression), - reuse_logs(false), - filter_policy(NULL) { -} +Options::Options() : comparator(BytewiseComparator()), env(Env::Default()) {} } // namespace leveldb diff --git a/src/leveldb/util/posix_logger.h b/src/leveldb/util/posix_logger.h index c063c2b7cb..28e15d10b4 100644 --- a/src/leveldb/util/posix_logger.h +++ b/src/leveldb/util/posix_logger.h @@ -3,94 +3,126 @@ // found in the LICENSE file. See the AUTHORS file for names of contributors. // // Logger implementation that can be shared by all environments -// where enough Posix functionality is available. +// where enough posix functionality is available. #ifndef STORAGE_LEVELDB_UTIL_POSIX_LOGGER_H_ #define STORAGE_LEVELDB_UTIL_POSIX_LOGGER_H_ -#include <algorithm> -#include <stdio.h> #include <sys/time.h> -#include <time.h> + +#include <cassert> +#include <cstdarg> +#include <cstdio> +#include <ctime> +#include <sstream> +#include <thread> + #include "leveldb/env.h" namespace leveldb { -class PosixLogger : public Logger { - private: - FILE* file_; - uint64_t (*gettid_)(); // Return the thread id for the current thread +class PosixLogger final : public Logger { public: - PosixLogger(FILE* f, uint64_t (*gettid)()) : file_(f), gettid_(gettid) { } - virtual ~PosixLogger() { - fclose(file_); - } - virtual void Logv(const char* format, va_list ap) { - const uint64_t thread_id = (*gettid_)(); - - // We try twice: the first time with a fixed-size stack allocated buffer, - // and the second time with a much larger dynamically allocated buffer. - char buffer[500]; - for (int iter = 0; iter < 2; iter++) { - char* base; - int bufsize; - if (iter == 0) { - bufsize = sizeof(buffer); - base = buffer; - } else { - bufsize = 30000; - base = new char[bufsize]; - } - char* p = base; - char* limit = base + bufsize; - - struct timeval now_tv; - gettimeofday(&now_tv, NULL); - const time_t seconds = now_tv.tv_sec; - struct tm t; - localtime_r(&seconds, &t); - p += snprintf(p, limit - p, - "%04d/%02d/%02d-%02d:%02d:%02d.%06d %llx ", - t.tm_year + 1900, - t.tm_mon + 1, - t.tm_mday, - t.tm_hour, - t.tm_min, - t.tm_sec, - static_cast<int>(now_tv.tv_usec), - static_cast<long long unsigned int>(thread_id)); - - // Print the message - if (p < limit) { - va_list backup_ap; - va_copy(backup_ap, ap); - p += vsnprintf(p, limit - p, format, backup_ap); - va_end(backup_ap); - } + // Creates a logger that writes to the given file. + // + // The PosixLogger instance takes ownership of the file handle. + explicit PosixLogger(std::FILE* fp) : fp_(fp) { assert(fp != nullptr); } + + ~PosixLogger() override { std::fclose(fp_); } + + void Logv(const char* format, va_list arguments) override { + // Record the time as close to the Logv() call as possible. + struct ::timeval now_timeval; + ::gettimeofday(&now_timeval, nullptr); + const std::time_t now_seconds = now_timeval.tv_sec; + struct std::tm now_components; + ::localtime_r(&now_seconds, &now_components); + + // Record the thread ID. + constexpr const int kMaxThreadIdSize = 32; + std::ostringstream thread_stream; + thread_stream << std::this_thread::get_id(); + std::string thread_id = thread_stream.str(); + if (thread_id.size() > kMaxThreadIdSize) { + thread_id.resize(kMaxThreadIdSize); + } - // Truncate to available space if necessary - if (p >= limit) { - if (iter == 0) { - continue; // Try again with larger buffer - } else { - p = limit - 1; + // We first attempt to print into a stack-allocated buffer. If this attempt + // fails, we make a second attempt with a dynamically allocated buffer. + constexpr const int kStackBufferSize = 512; + char stack_buffer[kStackBufferSize]; + static_assert(sizeof(stack_buffer) == static_cast<size_t>(kStackBufferSize), + "sizeof(char) is expected to be 1 in C++"); + + int dynamic_buffer_size = 0; // Computed in the first iteration. + for (int iteration = 0; iteration < 2; ++iteration) { + const int buffer_size = + (iteration == 0) ? kStackBufferSize : dynamic_buffer_size; + char* const buffer = + (iteration == 0) ? stack_buffer : new char[dynamic_buffer_size]; + + // Print the header into the buffer. + int buffer_offset = snprintf( + buffer, buffer_size, "%04d/%02d/%02d-%02d:%02d:%02d.%06d %s ", + now_components.tm_year + 1900, now_components.tm_mon + 1, + now_components.tm_mday, now_components.tm_hour, now_components.tm_min, + now_components.tm_sec, static_cast<int>(now_timeval.tv_usec), + thread_id.c_str()); + + // The header can be at most 28 characters (10 date + 15 time + + // 3 delimiters) plus the thread ID, which should fit comfortably into the + // static buffer. + assert(buffer_offset <= 28 + kMaxThreadIdSize); + static_assert(28 + kMaxThreadIdSize < kStackBufferSize, + "stack-allocated buffer may not fit the message header"); + assert(buffer_offset < buffer_size); + + // Print the message into the buffer. + std::va_list arguments_copy; + va_copy(arguments_copy, arguments); + buffer_offset += + std::vsnprintf(buffer + buffer_offset, buffer_size - buffer_offset, + format, arguments_copy); + va_end(arguments_copy); + + // The code below may append a newline at the end of the buffer, which + // requires an extra character. + if (buffer_offset >= buffer_size - 1) { + // The message did not fit into the buffer. + if (iteration == 0) { + // Re-run the loop and use a dynamically-allocated buffer. The buffer + // will be large enough for the log message, an extra newline and a + // null terminator. + dynamic_buffer_size = buffer_offset + 2; + continue; } + + // The dynamically-allocated buffer was incorrectly sized. This should + // not happen, assuming a correct implementation of (v)snprintf. Fail + // in tests, recover by truncating the log message in production. + assert(false); + buffer_offset = buffer_size - 1; } - // Add newline if necessary - if (p == base || p[-1] != '\n') { - *p++ = '\n'; + // Add a newline if necessary. + if (buffer[buffer_offset - 1] != '\n') { + buffer[buffer_offset] = '\n'; + ++buffer_offset; } - assert(p <= limit); - fwrite(base, 1, p - base, file_); - fflush(file_); - if (base != buffer) { - delete[] base; + assert(buffer_offset <= buffer_size); + std::fwrite(buffer, 1, buffer_offset, fp_); + std::fflush(fp_); + + if (iteration != 0) { + delete[] buffer; } break; } } + + private: + std::FILE* const fp_; }; } // namespace leveldb diff --git a/src/leveldb/util/random.h b/src/leveldb/util/random.h index ddd51b1c7b..76f7daf52a 100644 --- a/src/leveldb/util/random.h +++ b/src/leveldb/util/random.h @@ -15,6 +15,7 @@ namespace leveldb { class Random { private: uint32_t seed_; + public: explicit Random(uint32_t s) : seed_(s & 0x7fffffffu) { // Avoid bad seeds. @@ -23,8 +24,8 @@ class Random { } } 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 + 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 // @@ -54,9 +55,7 @@ class Random { // 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)); - } + uint32_t Skewed(int max_log) { return Uniform(1 << Uniform(max_log + 1)); } }; } // namespace leveldb diff --git a/src/leveldb/util/status.cc b/src/leveldb/util/status.cc index a44f35b314..15ce747d80 100644 --- a/src/leveldb/util/status.cc +++ b/src/leveldb/util/status.cc @@ -2,9 +2,11 @@ // 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 "leveldb/status.h" + #include <stdio.h> + #include "port/port.h" -#include "leveldb/status.h" namespace leveldb { @@ -18,8 +20,8 @@ const char* Status::CopyState(const char* state) { Status::Status(Code code, const Slice& msg, const Slice& msg2) { assert(code != kOk); - const uint32_t len1 = msg.size(); - const uint32_t len2 = msg2.size(); + const uint32_t len1 = static_cast<uint32_t>(msg.size()); + const uint32_t len2 = static_cast<uint32_t>(msg2.size()); const uint32_t size = len1 + (len2 ? (2 + len2) : 0); char* result = new char[size + 5]; memcpy(result, &size, sizeof(size)); @@ -34,7 +36,7 @@ Status::Status(Code code, const Slice& msg, const Slice& msg2) { } std::string Status::ToString() const { - if (state_ == NULL) { + if (state_ == nullptr) { return "OK"; } else { char tmp[30]; @@ -59,8 +61,8 @@ std::string Status::ToString() const { type = "IO error: "; break; default: - snprintf(tmp, sizeof(tmp), "Unknown code(%d): ", - static_cast<int>(code())); + snprintf(tmp, sizeof(tmp), + "Unknown code(%d): ", static_cast<int>(code())); type = tmp; break; } diff --git a/src/leveldb/util/status_test.cc b/src/leveldb/util/status_test.cc new file mode 100644 index 0000000000..2842319fbd --- /dev/null +++ b/src/leveldb/util/status_test.cc @@ -0,0 +1,40 @@ +// Copyright (c) 2018 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 <utility> + +#include "leveldb/slice.h" +#include "leveldb/status.h" +#include "util/testharness.h" + +namespace leveldb { + +TEST(Status, MoveConstructor) { + { + Status ok = Status::OK(); + Status ok2 = std::move(ok); + + ASSERT_TRUE(ok2.ok()); + } + + { + Status status = Status::NotFound("custom NotFound status message"); + Status status2 = std::move(status); + + ASSERT_TRUE(status2.IsNotFound()); + ASSERT_EQ("NotFound: custom NotFound status message", status2.ToString()); + } + + { + Status self_moved = Status::IOError("custom IOError status message"); + + // Needed to bypass compiler warning about explicit move-assignment. + Status& self_moved_reference = self_moved; + self_moved_reference = std::move(self_moved); + } +} + +} // namespace leveldb + +int main(int argc, char** argv) { return leveldb::test::RunAllTests(); } diff --git a/src/leveldb/util/testharness.cc b/src/leveldb/util/testharness.cc index 402fab34d7..318ecfa3b7 100644 --- a/src/leveldb/util/testharness.cc +++ b/src/leveldb/util/testharness.cc @@ -4,11 +4,15 @@ #include "util/testharness.h" -#include <string> #include <stdlib.h> #include <sys/stat.h> #include <sys/types.h> +#include <string> +#include <vector> + +#include "leveldb/env.h" + namespace leveldb { namespace test { @@ -19,10 +23,10 @@ struct Test { void (*func)(); }; std::vector<Test>* tests; -} +} // namespace bool RegisterTest(const char* base, const char* name, void (*func)()) { - if (tests == NULL) { + if (tests == nullptr) { tests = new std::vector<Test>; } Test t; @@ -37,14 +41,14 @@ int RunAllTests() { const char* matcher = getenv("LEVELDB_TESTS"); int num = 0; - if (tests != NULL) { + if (tests != nullptr) { for (size_t i = 0; i < tests->size(); i++) { const Test& t = (*tests)[i]; - if (matcher != NULL) { + if (matcher != nullptr) { std::string name = t.base; name.push_back('.'); name.append(t.name); - if (strstr(name.c_str(), matcher) == NULL) { + if (strstr(name.c_str(), matcher) == nullptr) { continue; } } @@ -66,7 +70,7 @@ std::string TmpDir() { int RandomSeed() { const char* env = getenv("TEST_RANDOM_SEED"); - int result = (env != NULL ? atoi(env) : 301); + int result = (env != nullptr ? atoi(env) : 301); if (result <= 0) { result = 301; } diff --git a/src/leveldb/util/testharness.h b/src/leveldb/util/testharness.h index da4fe68bb4..72cd1629eb 100644 --- a/src/leveldb/util/testharness.h +++ b/src/leveldb/util/testharness.h @@ -7,10 +7,10 @@ #include <stdio.h> #include <stdlib.h> + #include <sstream> -#include "leveldb/env.h" -#include "leveldb/slice.h" -#include "util/random.h" + +#include "leveldb/status.h" namespace leveldb { namespace test { @@ -27,15 +27,15 @@ namespace test { // // Returns 0 if all tests pass. // Dies or returns a non-zero value if some test fails. -extern int RunAllTests(); +int RunAllTests(); // Return the directory to use for temporary storage. -extern std::string TmpDir(); +std::string TmpDir(); // Return a randomization seed for this run. Typically returns the // same number on repeated invocations of this binary, but automated // runs may be able to vary the seed. -extern int RandomSeed(); +int RandomSeed(); // An instance of Tester is allocated to hold temporary state during // the execution of an assertion. @@ -47,9 +47,7 @@ class Tester { std::stringstream ss_; public: - Tester(const char* f, int l) - : ok_(true), fname_(f), line_(l) { - } + Tester(const char* f, int l) : ok_(true), fname_(f), line_(l) {} ~Tester() { if (!ok_) { @@ -74,14 +72,14 @@ class Tester { return *this; } -#define BINARY_OP(name,op) \ - template <class X, class Y> \ - Tester& name(const X& x, const Y& y) { \ - if (! (x op y)) { \ - ss_ << " failed: " << x << (" " #op " ") << y; \ - ok_ = false; \ - } \ - return *this; \ +#define BINARY_OP(name, op) \ + template <class X, class Y> \ + Tester& name(const X& x, const Y& y) { \ + if (!(x op y)) { \ + ss_ << " failed: " << x << (" " #op " ") << y; \ + ok_ = false; \ + } \ + return *this; \ } BINARY_OP(IsEq, ==) @@ -104,33 +102,38 @@ class Tester { #define ASSERT_TRUE(c) ::leveldb::test::Tester(__FILE__, __LINE__).Is((c), #c) #define ASSERT_OK(s) ::leveldb::test::Tester(__FILE__, __LINE__).IsOk((s)) -#define ASSERT_EQ(a,b) ::leveldb::test::Tester(__FILE__, __LINE__).IsEq((a),(b)) -#define ASSERT_NE(a,b) ::leveldb::test::Tester(__FILE__, __LINE__).IsNe((a),(b)) -#define ASSERT_GE(a,b) ::leveldb::test::Tester(__FILE__, __LINE__).IsGe((a),(b)) -#define ASSERT_GT(a,b) ::leveldb::test::Tester(__FILE__, __LINE__).IsGt((a),(b)) -#define ASSERT_LE(a,b) ::leveldb::test::Tester(__FILE__, __LINE__).IsLe((a),(b)) -#define ASSERT_LT(a,b) ::leveldb::test::Tester(__FILE__, __LINE__).IsLt((a),(b)) - -#define TCONCAT(a,b) TCONCAT1(a,b) -#define TCONCAT1(a,b) a##b - -#define TEST(base,name) \ -class TCONCAT(_Test_,name) : public base { \ - public: \ - void _Run(); \ - static void _RunIt() { \ - TCONCAT(_Test_,name) t; \ - t._Run(); \ - } \ -}; \ -bool TCONCAT(_Test_ignored_,name) = \ - ::leveldb::test::RegisterTest(#base, #name, &TCONCAT(_Test_,name)::_RunIt); \ -void TCONCAT(_Test_,name)::_Run() +#define ASSERT_EQ(a, b) \ + ::leveldb::test::Tester(__FILE__, __LINE__).IsEq((a), (b)) +#define ASSERT_NE(a, b) \ + ::leveldb::test::Tester(__FILE__, __LINE__).IsNe((a), (b)) +#define ASSERT_GE(a, b) \ + ::leveldb::test::Tester(__FILE__, __LINE__).IsGe((a), (b)) +#define ASSERT_GT(a, b) \ + ::leveldb::test::Tester(__FILE__, __LINE__).IsGt((a), (b)) +#define ASSERT_LE(a, b) \ + ::leveldb::test::Tester(__FILE__, __LINE__).IsLe((a), (b)) +#define ASSERT_LT(a, b) \ + ::leveldb::test::Tester(__FILE__, __LINE__).IsLt((a), (b)) + +#define TCONCAT(a, b) TCONCAT1(a, b) +#define TCONCAT1(a, b) a##b + +#define TEST(base, name) \ + class TCONCAT(_Test_, name) : public base { \ + public: \ + void _Run(); \ + static void _RunIt() { \ + TCONCAT(_Test_, name) t; \ + t._Run(); \ + } \ + }; \ + bool TCONCAT(_Test_ignored_, name) = ::leveldb::test::RegisterTest( \ + #base, #name, &TCONCAT(_Test_, name)::_RunIt); \ + void TCONCAT(_Test_, name)::_Run() // Register the specified test. Typically not used directly, but // invoked via the macro expansion of TEST. -extern bool RegisterTest(const char* base, const char* name, void (*func)()); - +bool RegisterTest(const char* base, const char* name, void (*func)()); } // namespace test } // namespace leveldb diff --git a/src/leveldb/util/testutil.cc b/src/leveldb/util/testutil.cc index bee56bf75f..6b151b9e64 100644 --- a/src/leveldb/util/testutil.cc +++ b/src/leveldb/util/testutil.cc @@ -12,7 +12,7 @@ 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<char>(' ' + rnd->Uniform(95)); // ' ' .. '~' + (*dst)[i] = static_cast<char>(' ' + rnd->Uniform(95)); // ' ' .. '~' } return Slice(*dst); } @@ -20,9 +20,8 @@ Slice RandomString(Random* rnd, int len, std::string* 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' - }; + 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))]; @@ -30,9 +29,8 @@ std::string RandomKey(Random* rnd, int len) { return result; } - -extern Slice CompressibleString(Random* rnd, double compressed_fraction, - size_t len, std::string* dst) { +Slice CompressibleString(Random* rnd, double compressed_fraction, size_t len, + std::string* dst) { int raw = static_cast<int>(len * compressed_fraction); if (raw < 1) raw = 1; std::string raw_data; diff --git a/src/leveldb/util/testutil.h b/src/leveldb/util/testutil.h index d7e4583702..bb4051ba07 100644 --- a/src/leveldb/util/testutil.h +++ b/src/leveldb/util/testutil.h @@ -5,6 +5,7 @@ #ifndef STORAGE_LEVELDB_UTIL_TESTUTIL_H_ #define STORAGE_LEVELDB_UTIL_TESTUTIL_H_ +#include "helpers/memenv/memenv.h" #include "leveldb/env.h" #include "leveldb/slice.h" #include "util/random.h" @@ -14,17 +15,17 @@ namespace test { // Store in *dst a random string of length "len" and return a Slice that // references the generated data. -extern Slice RandomString(Random* rnd, int len, std::string* dst); +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.). -extern std::string RandomKey(Random* rnd, int len); +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. -extern Slice CompressibleString(Random* rnd, double compressed_fraction, - size_t len, std::string* dst); +Slice CompressibleString(Random* rnd, double compressed_fraction, size_t len, + std::string* dst); // A wrapper that allows injection of errors. class ErrorEnv : public EnvWrapper { @@ -32,25 +33,27 @@ class ErrorEnv : public EnvWrapper { bool writable_file_error_; int num_writable_file_errors_; - ErrorEnv() : EnvWrapper(Env::Default()), - writable_file_error_(false), - num_writable_file_errors_(0) { } + ErrorEnv() + : EnvWrapper(NewMemEnv(Env::Default())), + writable_file_error_(false), + num_writable_file_errors_(0) {} + ~ErrorEnv() override { delete target(); } - virtual Status NewWritableFile(const std::string& fname, - WritableFile** result) { + Status NewWritableFile(const std::string& fname, + WritableFile** result) override { if (writable_file_error_) { ++num_writable_file_errors_; - *result = NULL; + *result = nullptr; return Status::IOError(fname, "fake error"); } return target()->NewWritableFile(fname, result); } - virtual Status NewAppendableFile(const std::string& fname, - WritableFile** result) { + Status NewAppendableFile(const std::string& fname, + WritableFile** result) override { if (writable_file_error_) { ++num_writable_file_errors_; - *result = NULL; + *result = nullptr; return Status::IOError(fname, "fake error"); } return target()->NewAppendableFile(fname, result); diff --git a/src/leveldb/util/windows_logger.h b/src/leveldb/util/windows_logger.h new file mode 100644 index 0000000000..92960638d1 --- /dev/null +++ b/src/leveldb/util/windows_logger.h @@ -0,0 +1,124 @@ +// Copyright (c) 2018 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. +// +// Logger implementation for the Windows platform. + +#ifndef STORAGE_LEVELDB_UTIL_WINDOWS_LOGGER_H_ +#define STORAGE_LEVELDB_UTIL_WINDOWS_LOGGER_H_ + +#include <cassert> +#include <cstdarg> +#include <cstdio> +#include <ctime> +#include <sstream> +#include <thread> + +#include "leveldb/env.h" + +namespace leveldb { + +class WindowsLogger final : public Logger { + public: + // Creates a logger that writes to the given file. + // + // The PosixLogger instance takes ownership of the file handle. + explicit WindowsLogger(std::FILE* fp) : fp_(fp) { assert(fp != nullptr); } + + ~WindowsLogger() override { std::fclose(fp_); } + + void Logv(const char* format, va_list arguments) override { + // Record the time as close to the Logv() call as possible. + SYSTEMTIME now_components; + ::GetLocalTime(&now_components); + + // Record the thread ID. + constexpr const int kMaxThreadIdSize = 32; + std::ostringstream thread_stream; + thread_stream << std::this_thread::get_id(); + std::string thread_id = thread_stream.str(); + if (thread_id.size() > kMaxThreadIdSize) { + thread_id.resize(kMaxThreadIdSize); + } + + // We first attempt to print into a stack-allocated buffer. If this attempt + // fails, we make a second attempt with a dynamically allocated buffer. + constexpr const int kStackBufferSize = 512; + char stack_buffer[kStackBufferSize]; + static_assert(sizeof(stack_buffer) == static_cast<size_t>(kStackBufferSize), + "sizeof(char) is expected to be 1 in C++"); + + int dynamic_buffer_size = 0; // Computed in the first iteration. + for (int iteration = 0; iteration < 2; ++iteration) { + const int buffer_size = + (iteration == 0) ? kStackBufferSize : dynamic_buffer_size; + char* const buffer = + (iteration == 0) ? stack_buffer : new char[dynamic_buffer_size]; + + // Print the header into the buffer. + int buffer_offset = snprintf( + buffer, buffer_size, "%04d/%02d/%02d-%02d:%02d:%02d.%06d %s ", + now_components.wYear, now_components.wMonth, now_components.wDay, + now_components.wHour, now_components.wMinute, now_components.wSecond, + static_cast<int>(now_components.wMilliseconds * 1000), + thread_id.c_str()); + + // The header can be at most 28 characters (10 date + 15 time + + // 3 delimiters) plus the thread ID, which should fit comfortably into the + // static buffer. + assert(buffer_offset <= 28 + kMaxThreadIdSize); + static_assert(28 + kMaxThreadIdSize < kStackBufferSize, + "stack-allocated buffer may not fit the message header"); + assert(buffer_offset < buffer_size); + + // Print the message into the buffer. + std::va_list arguments_copy; + va_copy(arguments_copy, arguments); + buffer_offset += + std::vsnprintf(buffer + buffer_offset, buffer_size - buffer_offset, + format, arguments_copy); + va_end(arguments_copy); + + // The code below may append a newline at the end of the buffer, which + // requires an extra character. + if (buffer_offset >= buffer_size - 1) { + // The message did not fit into the buffer. + if (iteration == 0) { + // Re-run the loop and use a dynamically-allocated buffer. The buffer + // will be large enough for the log message, an extra newline and a + // null terminator. + dynamic_buffer_size = buffer_offset + 2; + continue; + } + + // The dynamically-allocated buffer was incorrectly sized. This should + // not happen, assuming a correct implementation of (v)snprintf. Fail + // in tests, recover by truncating the log message in production. + assert(false); + buffer_offset = buffer_size - 1; + } + + // Add a newline if necessary. + if (buffer[buffer_offset - 1] != '\n') { + buffer[buffer_offset] = '\n'; + ++buffer_offset; + } + + assert(buffer_offset <= buffer_size); + std::fwrite(buffer, 1, buffer_offset, fp_); + std::fflush(fp_); + + if (iteration != 0) { + delete[] buffer; + } + break; + } + } + + private: + std::FILE* const fp_; +}; + +} // namespace leveldb + +#endif // STORAGE_LEVELDB_UTIL_WINDOWS_LOGGER_H_ |