From 596aa8952f0afec207e876bd99dcb4f4841a9aef Mon Sep 17 00:00:00 2001 From: Andrii Grynenko Date: Wed, 25 Nov 2015 20:03:55 -0800 Subject: [PATCH] New ReadMostlySharedPtr implementation Summary: This changes ReadMostlySharedPtr API to have 3 types: MainPtr, WeakPtr, SharedPtr. MainPtr and SharedPtr are equivalents of std::shared_ptr, and WeakPtr is an equivalent of std::weak_ptr. The only difference is that it can only be a single MainPtr, and while it's alive copying SharedPtr/WeakPtr or WeakPtr doesn't require atomic operations (and thus can be more performant than std::shared_ptr). Unlike original ReadMostlySharedPtr API, there're no thread-safety guarantees between reset() and getShared() for ReadMostlySharedPtr. ReadMostlySharedPtr can work with different RefCount implementations. This diff introduces RCURefCount (which is currently using liburcu) and TLRefCount. Reviewed By: djwatson Differential Revision: D2683572 fb-gh-sync-id: a7a03af4b1cf5f81a613368c6eebe70b2eaef064 --- folly/Makefile.am | 1 - folly/Random.cpp | 10 +- folly/ReadMostlySharedPtr.h | 187 --------- folly/ThreadLocal.h | 11 +- folly/experimental/RCURefCount.h | 158 ++++++++ folly/experimental/RCUUtils.cpp | 52 +++ folly/experimental/RCUUtils.h | 53 +++ folly/experimental/ReadMostlySharedPtr.h | 355 ++++++++++++++++ folly/experimental/TLRefCount.h | 171 ++++++++ .../test/ReadMostlySharedPtrBenchmark.cpp | 92 +++++ .../test/ReadMostlySharedPtrTest.cpp | 238 +++++++++++ folly/experimental/test/RefCountBenchmark.cpp | 97 +++++ folly/experimental/test/RefCountTest.cpp | 84 ++++ folly/test/ReadMostlySharedPtrBenchmark.cpp | 319 --------------- folly/test/ReadMostlySharedPtrTest.cpp | 382 ------------------ 15 files changed, 1314 insertions(+), 896 deletions(-) delete mode 100644 folly/ReadMostlySharedPtr.h create mode 100644 folly/experimental/RCURefCount.h create mode 100644 folly/experimental/RCUUtils.cpp create mode 100644 folly/experimental/RCUUtils.h create mode 100644 folly/experimental/ReadMostlySharedPtr.h create mode 100644 folly/experimental/TLRefCount.h create mode 100644 folly/experimental/test/ReadMostlySharedPtrBenchmark.cpp create mode 100644 folly/experimental/test/ReadMostlySharedPtrTest.cpp create mode 100644 folly/experimental/test/RefCountBenchmark.cpp create mode 100644 folly/experimental/test/RefCountTest.cpp delete mode 100644 folly/test/ReadMostlySharedPtrBenchmark.cpp delete mode 100644 folly/test/ReadMostlySharedPtrTest.cpp diff --git a/folly/Makefile.am b/folly/Makefile.am index 8dea8a12..c8e1d09c 100644 --- a/folly/Makefile.am +++ b/folly/Makefile.am @@ -249,7 +249,6 @@ nobase_follyinclude_HEADERS = \ Random.h \ Random-inl.h \ Range.h \ - ReadMostlySharedPtr.h \ RWSpinLock.h \ ScopeGuard.h \ SharedMutex.h \ diff --git a/folly/Random.cpp b/folly/Random.cpp index 62eb8f9f..899668c8 100644 --- a/folly/Random.cpp +++ b/folly/Random.cpp @@ -116,11 +116,6 @@ void Random::secureRandom(void* data, size_t size) { bufferedRandomDevice->get(data, size); } -ThreadLocalPRNG::ThreadLocalPRNG() { - static folly::ThreadLocal localInstance; - local_ = localInstance.get(); -} - class ThreadLocalPRNG::LocalInstancePRNG { public: LocalInstancePRNG() : rng(Random::create()) { } @@ -128,6 +123,11 @@ class ThreadLocalPRNG::LocalInstancePRNG { Random::DefaultGenerator rng; }; +ThreadLocalPRNG::ThreadLocalPRNG() { + static folly::ThreadLocal localInstance; + local_ = localInstance.get(); +} + uint32_t ThreadLocalPRNG::getImpl(LocalInstancePRNG* local) { return local->rng(); } diff --git a/folly/ReadMostlySharedPtr.h b/folly/ReadMostlySharedPtr.h deleted file mode 100644 index 9f714899..00000000 --- a/folly/ReadMostlySharedPtr.h +++ /dev/null @@ -1,187 +0,0 @@ -/* - * Copyright 2015 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -/* -*- Mode: C++; tab-width: 2; c-basic-offset: 2; indent-tabs-mode: nil -*- */ -#pragma once - -#include -#include -#include -#include -#include - -namespace folly { - -/** - * @file ReadMostlySharedPtr is a smart pointer that allows for high - * performance shared ownership of an object. In order to provide - * this, ReadMostlySharedPtr may potentially delay the destruction of - * a shared object for longer than a std::shared_ptr would, and - * depending on the implementation, may have slower updates. - * - * The load() method allows a reader to acquire a ReadPtr that - * maintains a reference to a single version of the object. Even if a - * writer calls store(), the ReadPtr will point to the version of the - * object that was in use at the time of the read. The old version of - * the object will only be destroyed after all outstanding ReadPtrs to - * that version have been destroyed. - */ - -template -class ReadMostlySharedPtr { - public: - constexpr explicit ReadMostlySharedPtr(std::unique_ptr&& ptr = nullptr) - : masterPtr_(std::move(ptr)) {} - - /** - * Replaces the managed object. - */ - void store(std::unique_ptr&& uptr) { - { - std::shared_ptr ptr(std::move(uptr)); - std::lock_guard lock(mutex_); - // Swap to avoid calling ~T() under the lock - std::swap(masterPtr_, ptr); - } - - { - // This also holds a lock that prevents destruction of thread cache - // entries, but not creation. If creating a thread cache entry for a new - // thread happens duting iteration, the entry is not guaranteed to - // be seen. It's fine for us: if load() created a new cache entry after - // we got accessor, it will see the updated pointer, so we don't need to - // clear the cache. - auto accessor = threadLocalCache_.accessAllThreads(); - - for (CachedPointer& local: accessor) { - std::lock_guard local_lock(local.lock); - // We could instead just assign masterPtr_ to local.ptr, but it's better - // if the thread allocates the Ptr for itself - the allocator is more - // likely to place its reference counter in a region optimal for access - // from that thread. - local.ptr.clear(); - } - } - } - - class ReadPtr { - friend class ReadMostlySharedPtr; - public: - ReadPtr() {} - void reset() { - ref_ = nullptr; - ptr_.reset(); - } - explicit operator bool() const { - return (ref_ != nullptr); - } - bool operator ==(T* ptr) const { - return ref_ == ptr; - } - bool operator ==(std::nullptr_t) const { - return ref_ == nullptr; - } - T* operator->() const { return ref_; } - T& operator*() const { return *ref_; } - T* get() const { return ref_; } - private: - explicit ReadPtr(std::shared_ptr& ptr) - : ptr_(ptr) - , ref_(ptr.get()) {} - std::shared_ptr ptr_; - T* ref_{nullptr}; - }; - - /** - * Returns a shared_ptr to the managed object. - */ - ReadPtr load() const { - auto& local = *threadLocalCache_; - - std::lock_guard local_lock(local.lock); - - if (!local.ptr.hasValue()) { - std::lock_guard lock(mutex_); - if (!masterPtr_) { - local.ptr.emplace(nullptr); - } else { - // The following expression is tricky. - // - // It creates a shared_ptr> that points to a copy of - // masterPtr_. The reference counter of this shared_ptr> - // will normally only be modified from this thread, which avoids - // cache line bouncing. (Though the caller is free to pass the pointer - // to other threads and bump reference counter from there) - // - // Then this shared_ptr> is turned into shared_ptr. - // This means that the returned shared_ptr will internally point to - // control block of the shared_ptr>, but will dereference - // to T, not shared_ptr. - local.ptr = makeCachedCopy(masterPtr_); - } - } - - // The return statement makes the copy before destroying local variables, - // so local.ptr is only accessed under local.lock here. - return ReadPtr(local.ptr.value()); - } - - private: - - // non copyable - ReadMostlySharedPtr(const ReadMostlySharedPtr&) = delete; - ReadMostlySharedPtr& operator=(const ReadMostlySharedPtr&) = delete; - - struct CachedPointer { - folly::Optional> ptr; - folly::SpinLock lock; - }; - - std::shared_ptr masterPtr_; - - // Instead of using Tag as tag for ThreadLocal, effectively use pair (T, Tag), - // which is more granular. - struct ThreadLocalTag {}; - - mutable folly::ThreadLocal threadLocalCache_; - - // Ensures safety between concurrent store() and load() calls - mutable std::mutex mutex_; - - std::shared_ptr - makeCachedCopy(const std::shared_ptr &ptr) const { - // For std::shared_ptr wrap a copy in another std::shared_ptr to - // avoid cache line bouncing. - // - // The following expression is tricky. - // - // It creates a shared_ptr> that points to a copy of - // masterPtr_. The reference counter of this shared_ptr> - // will normally only be modified from this thread, which avoids - // cache line bouncing. (Though the caller is free to pass the pointer - // to other threads and bump reference counter from there) - // - // Then this shared_ptr> is turned into shared_ptr. - // This means that the returned shared_ptr will internally point to - // control block of the shared_ptr>, but will dereference - // to T, not shared_ptr. - return std::shared_ptr( - std::make_shared>(ptr), ptr.get()); - } - -}; - -} diff --git a/folly/ThreadLocal.h b/folly/ThreadLocal.h index a0d93fb4..c55fdbeb 100644 --- a/folly/ThreadLocal.h +++ b/folly/ThreadLocal.h @@ -59,7 +59,13 @@ template class ThreadLocalPtr; template class ThreadLocal { public: - constexpr ThreadLocal() {} + constexpr ThreadLocal() : constructor_([]() { + return new T(); + }) {} + + explicit ThreadLocal(std::function constructor) : + constructor_(constructor) { + } T* get() const { T* ptr = tlp_.get(); @@ -98,12 +104,13 @@ class ThreadLocal { ThreadLocal& operator=(const ThreadLocal&) = delete; T* makeTlp() const { - T* ptr = new T(); + auto ptr = constructor_(); tlp_.reset(ptr); return ptr; } mutable ThreadLocalPtr tlp_; + std::function constructor_; }; /* diff --git a/folly/experimental/RCURefCount.h b/folly/experimental/RCURefCount.h new file mode 100644 index 00000000..567006ea --- /dev/null +++ b/folly/experimental/RCURefCount.h @@ -0,0 +1,158 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#pragma once + +#include +#include + +namespace folly { + +class RCURefCount { + public: + using Int = int64_t; + + RCURefCount() : + localCount_([&]() { + return new LocalRefCount(globalCount_); + }) { + } + + ~RCURefCount() noexcept { + assert(state_ == State::GLOBAL); + assert(globalCount_.load() == 0); + } + + // This can't increment from 0. + Int operator++() noexcept { + auto& localCount = *localCount_; + + std::lock_guard lg(RCUReadLock::instance()); + + if (LIKELY(state_ == State::LOCAL)) { + ++localCount; + + return 42; + } else if (state_ == State::GLOBAL_TRANSITION) { + ++globalCount_; + + return 42; + } else { + auto globalCount = globalCount_.load(); + + do { + if (!globalCount) { + return 0; + } + } while (!globalCount_.compare_exchange_weak(globalCount, + globalCount + 1)); + + return globalCount + 1; + } + } + + Int operator--() noexcept { + auto& localCount = *localCount_; + + std::lock_guard lg(RCUReadLock::instance()); + + if (LIKELY(state_ == State::LOCAL)) { + --localCount; + + return 42; + } else { + auto value = --globalCount_; + + if (state_ == State::GLOBAL) { + assert(value >= 0); + return value; + } else { + return 42; + } + } + } + + Int operator*() const { + std::lock_guard lg(RCUReadLock::instance()); + + if (state_ == State::GLOBAL) { + return globalCount_; + } + + return 42; + } + + void useGlobal() noexcept { + state_ = State::GLOBAL_TRANSITION; + + synchronize_rcu(); + // At this point everyone is using the global count + + auto accessor = localCount_.accessAllThreads(); + for (auto& count : accessor) { + count.collect(); + } + + state_ = State::GLOBAL; + + synchronize_rcu(); + // After this ++ or -- can return 0. + } + + private: + using AtomicInt = std::atomic; + + enum class State { + LOCAL, + GLOBAL_TRANSITION, + GLOBAL + }; + + class LocalRefCount { + public: + explicit LocalRefCount(AtomicInt& globalCount) : + count_(0), + globalCount_(globalCount) { + RCURegisterThread(); + } + + ~LocalRefCount() { + collect(); + } + + void collect() { + globalCount_ += count_; + count_ = 0; + } + + void operator++() { + ++count_; + } + + void operator--() { + --count_; + } + + private: + Int count_; + AtomicInt& globalCount_; + }; + + std::atomic state_{State::LOCAL}; + folly::ThreadLocal localCount_; + std::atomic globalCount_{1}; +}; + +} diff --git a/folly/experimental/RCUUtils.cpp b/folly/experimental/RCUUtils.cpp new file mode 100644 index 00000000..2f0593c9 --- /dev/null +++ b/folly/experimental/RCUUtils.cpp @@ -0,0 +1,52 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include + +#include +#include + + +namespace folly { + +namespace { + +struct RCURegisterThreadHelper { + RCURegisterThreadHelper() { + rcu_register_thread(); + } + + ~RCURegisterThreadHelper() { + rcu_unregister_thread(); + } + + bool alive{false}; +}; + +} + +bool RCURegisterThread() { + static folly::ThreadLocal* rcuRegisterThreadHelper = + new folly::ThreadLocal(); + + auto& helper = **rcuRegisterThreadHelper; + + auto ret = !helper.alive; + helper.alive = true; + + return ret; +} + +} diff --git a/folly/experimental/RCUUtils.h b/folly/experimental/RCUUtils.h new file mode 100644 index 00000000..4bf85e1a --- /dev/null +++ b/folly/experimental/RCUUtils.h @@ -0,0 +1,53 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#pragma once + +#include + +namespace folly { + +/** + * This must be called at least once from any thread, which uses RCUReadLock. + * First call should happen before RCUReadLock is used for the first time. Can + * be safely called more that once. + * + * Returns true when called for the first time from current thread. + */ +bool RCURegisterThread(); + +class RCUReadLock { + public: + static RCUReadLock& instance() { + // Both lock and unlock are static, so no need to worry about destruction + // order + static RCUReadLock instance; + return instance; + } + + static void lock() { + assert(RCURegisterThread() == false); + rcu_read_lock(); + } + + static void unlock() { + rcu_read_unlock(); + } + + private: + RCUReadLock() {} +}; + +} diff --git a/folly/experimental/ReadMostlySharedPtr.h b/folly/experimental/ReadMostlySharedPtr.h new file mode 100644 index 00000000..d6c04cdb --- /dev/null +++ b/folly/experimental/ReadMostlySharedPtr.h @@ -0,0 +1,355 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/* -*- Mode: C++; tab-width: 2; c-basic-offset: 2; indent-tabs-mode: nil -*- */ +#pragma once + +#include + +#include +#include + +namespace folly { + +template +class ReadMostlyMainPtr; +template +class ReadMostlyWeakPtr; +template +class ReadMostlySharedPtr; + +using DefaultRefCount = TLRefCount; + +namespace detail { + +template +class ReadMostlySharedPtrCore { + public: + T* get() { + return ptrRaw_; + } + + std::shared_ptr getShared() { + return ptr_; + } + + bool incref() { + return ++count_ > 0; + } + + void decref() { + if (--count_ == 0) { + ptrRaw_ = nullptr; + ptr_.reset(); + + decrefWeak(); + } + } + + void increfWeak() { + auto value = ++weakCount_; + assert(value > 0); + } + + void decrefWeak() { + if (--weakCount_ == 0) { + delete this; + } + } + + size_t useCount() const { + return *count_; + } + + ~ReadMostlySharedPtrCore() noexcept { + assert(*count_ == 0); + assert(*weakCount_ == 0); + } + + private: + friend class ReadMostlyMainPtr; + + explicit ReadMostlySharedPtrCore(std::shared_ptr ptr) : + ptrRaw_(ptr.get()), + ptr_(std::move(ptr)) { + } + + T* ptrRaw_; + RefCount count_; + RefCount weakCount_; + std::shared_ptr ptr_; +}; + +} + +template +class ReadMostlyMainPtr { + public: + ReadMostlyMainPtr() { + } + + explicit ReadMostlyMainPtr(std::shared_ptr ptr) { + reset(std::move(ptr)); + } + + ReadMostlyMainPtr(const ReadMostlyMainPtr&) = delete; + ReadMostlyMainPtr& operator=(const ReadMostlyMainPtr&) = delete; + + ReadMostlyMainPtr(ReadMostlyMainPtr&& other) noexcept { + *this = std::move(other); + } + + ReadMostlyMainPtr& operator=(ReadMostlyMainPtr&& other) noexcept { + std::swap(impl_, other.impl_); + + return *this; + } + + bool operator==(const ReadMostlyMainPtr& other) const { + return get() == other.get(); + } + + bool operator==(T* other) const { + return get() == other; + } + + bool operator==(const ReadMostlySharedPtr& other) const { + return get() == other.get(); + } + + ~ReadMostlyMainPtr() noexcept { + reset(); + } + + void reset() noexcept { + if (impl_) { + impl_->count_.useGlobal(); + impl_->weakCount_.useGlobal(); + impl_->decref(); + impl_ = nullptr; + } + } + + void reset(std::shared_ptr ptr) { + reset(); + if (ptr) { + impl_ = new detail::ReadMostlySharedPtrCore(std::move(ptr)); + } + } + + T* get() const { + if (impl_) { + return impl_->ptrRaw_; + } else { + return nullptr; + } + } + + std::shared_ptr getStdShared() { + if (impl_) { + return impl_->ptr_; + } else { + return {}; + } + } + + T& operator*() const { + return *get(); + } + + T* operator->() const { + return get(); + } + + ReadMostlySharedPtr getShared() const { + return ReadMostlySharedPtr(*this); + } + + explicit operator bool() const { + return impl_ != nullptr; + } + + private: + friend class ReadMostlyWeakPtr; + friend class ReadMostlySharedPtr; + + detail::ReadMostlySharedPtrCore* impl_{nullptr}; +}; + +template +class ReadMostlyWeakPtr { + public: + ReadMostlyWeakPtr() {} + + explicit ReadMostlyWeakPtr(const ReadMostlyMainPtr& mainPtr) { + reset(mainPtr.impl_); + } + + ReadMostlyWeakPtr(const ReadMostlyWeakPtr& other) { + *this = other; + } + + ReadMostlyWeakPtr& operator=(const ReadMostlyWeakPtr& other) { + reset(other.impl_); + return *this; + } + + ReadMostlyWeakPtr(ReadMostlyWeakPtr&& other) noexcept { + *this = other; + } + + ReadMostlyWeakPtr& operator=(ReadMostlyWeakPtr&& other) noexcept { + std::swap(impl_, other.impl_); + return *this; + } + + ~ReadMostlyWeakPtr() noexcept { + reset(nullptr); + } + + ReadMostlySharedPtr lock() { + return ReadMostlySharedPtr(*this); + } + + private: + friend class ReadMostlySharedPtr; + + void reset(detail::ReadMostlySharedPtrCore* impl) { + if (impl_) { + impl_->decrefWeak(); + } + impl_ = impl; + if (impl_) { + impl_->increfWeak(); + } + } + + detail::ReadMostlySharedPtrCore* impl_{nullptr}; +}; + +template +class ReadMostlySharedPtr { + public: + ReadMostlySharedPtr() {} + + explicit ReadMostlySharedPtr(const ReadMostlyWeakPtr& weakPtr) { + reset(weakPtr.impl_); + } + + // Generally, this shouldn't be used. + explicit ReadMostlySharedPtr(const ReadMostlyMainPtr& mainPtr) { + reset(mainPtr.impl_); + } + + ReadMostlySharedPtr(const ReadMostlySharedPtr& other) { + *this = other; + } + + ReadMostlySharedPtr& operator=(const ReadMostlySharedPtr& other) { + reset(other.impl_); + return *this; + } + + ReadMostlySharedPtr& operator=(const ReadMostlyWeakPtr& other) { + reset(other.impl_); + return *this; + } + + ReadMostlySharedPtr& operator=(const ReadMostlyMainPtr& other) { + reset(other.impl_); + return *this; + } + + ReadMostlySharedPtr(ReadMostlySharedPtr&& other) noexcept { + *this = std::move(other); + } + + ~ReadMostlySharedPtr() noexcept { + reset(nullptr); + } + + ReadMostlySharedPtr& operator=(ReadMostlySharedPtr&& other) noexcept { + std::swap(ptr_, other.ptr_); + std::swap(impl_, other.impl_); + return *this; + } + + bool operator==(const ReadMostlyMainPtr& other) const { + return get() == other.get(); + } + + bool operator==(T* other) const { + return get() == other; + } + + bool operator==(const ReadMostlySharedPtr& other) const { + return get() == other.get(); + } + + void reset() { + reset(nullptr); + } + + T* get() const { + return ptr_; + } + + std::shared_ptr getStdShared() const { + if (impl_) { + return impl_->ptr_; + } else { + return {}; + } + } + + T& operator*() const { + return *get(); + } + + T* operator->() const { + return get(); + } + + size_t use_count() const { + return impl_->useCount(); + } + + bool unique() const { + return use_count() == 1; + } + + explicit operator bool() const { + return impl_ != nullptr; + } + + private: + void reset(detail::ReadMostlySharedPtrCore* impl) { + if (impl_) { + impl_->decref(); + impl_ = nullptr; + ptr_ = nullptr; + } + + if (impl && impl->incref()) { + impl_ = impl; + ptr_ = impl->get(); + } + } + + T* ptr_{nullptr}; + detail::ReadMostlySharedPtrCore* impl_{nullptr}; +}; + +} diff --git a/folly/experimental/TLRefCount.h b/folly/experimental/TLRefCount.h new file mode 100644 index 00000000..c2b22091 --- /dev/null +++ b/folly/experimental/TLRefCount.h @@ -0,0 +1,171 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#pragma once + +#include + +namespace folly { + +class TLRefCount { + public: + using Int = int64_t; + + TLRefCount() : + localCount_([&]() { + return new LocalRefCount(*this); + }) { + } + + ~TLRefCount() noexcept { + assert(globalCount_.load() == 0); + assert(state_.load() == State::GLOBAL); + } + + // This can't increment from 0. + Int operator++() noexcept { + auto& localCount = *localCount_; + + if (++localCount) { + return 42; + } + + if (state_.load() == State::GLOBAL_TRANSITION) { + std::lock_guard lg(globalMutex_); + } + + assert(state_.load() == State::GLOBAL); + + auto value = globalCount_.load(); + do { + if (value == 0) { + return 0; + } + } while (!globalCount_.compare_exchange_weak(value, value+1)); + + return value + 1; + } + + Int operator--() noexcept { + auto& localCount = *localCount_; + + if (--localCount) { + return 42; + } + + if (state_.load() == State::GLOBAL_TRANSITION) { + std::lock_guard lg(globalMutex_); + } + + assert(state_.load() == State::GLOBAL); + + return --globalCount_; + } + + Int operator*() const { + if (state_ != State::GLOBAL) { + return 42; + } + return globalCount_.load(); + } + + void useGlobal() noexcept { + std::lock_guard lg(globalMutex_); + + state_ = State::GLOBAL_TRANSITION; + + auto accessor = localCount_.accessAllThreads(); + for (auto& count : accessor) { + count.collect(); + } + + state_ = State::GLOBAL; + } + + private: + using AtomicInt = std::atomic; + + enum class State { + LOCAL, + GLOBAL_TRANSITION, + GLOBAL + }; + + class LocalRefCount { + public: + explicit LocalRefCount(TLRefCount& refCount) : + refCount_(refCount) {} + + ~LocalRefCount() { + collect(); + } + + void collect() { + std::lock_guard lg(collectMutex_); + + if (collectDone_) { + return; + } + + collectCount_ = count_; + refCount_.globalCount_ += collectCount_; + collectDone_ = true; + } + + bool operator++() { + return update(1); + } + + bool operator--() { + return update(-1); + } + + private: + bool update(Int delta) { + if (UNLIKELY(refCount_.state_.load() != State::LOCAL)) { + return false; + } + + auto count = count_ += delta; + + if (UNLIKELY(refCount_.state_.load() != State::LOCAL)) { + std::lock_guard lg(collectMutex_); + + if (!collectDone_) { + return true; + } + if (collectCount_ != count) { + return false; + } + } + + return true; + } + + Int count_{0}; + TLRefCount& refCount_; + + std::mutex collectMutex_; + Int collectCount_{0}; + bool collectDone_; + }; + + std::atomic state_{State::LOCAL}; + folly::ThreadLocal localCount_; + std::atomic globalCount_{1}; + std::mutex globalMutex_; +}; + +} diff --git a/folly/experimental/test/ReadMostlySharedPtrBenchmark.cpp b/folly/experimental/test/ReadMostlySharedPtrBenchmark.cpp new file mode 100644 index 00000000..0d75c28a --- /dev/null +++ b/folly/experimental/test/ReadMostlySharedPtrBenchmark.cpp @@ -0,0 +1,92 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/* -*- Mode: C++; tab-width: 2; c-basic-offset: 2; indent-tabs-mode: nil -*- */ + +#include +#include +#include +#include +#include + +#include + +template class MainPtr, + template class WeakPtr, + size_t threadCount> +void benchmark(size_t n) { + MainPtr mainPtr(folly::make_unique(42)); + + std::vector ts; + + for (size_t t = 0; t < threadCount; ++t) { + ts.emplace_back([&]() { + WeakPtr weakPtr(mainPtr); + + for (size_t i = 0; i < n; ++i) { + weakPtr.lock(); + } + }); + } + + for (auto& t: ts) { + t.join(); + } +} + +template +using RCUMainPtr = folly::ReadMostlyMainPtr; +template +using RCUWeakPtr = folly::ReadMostlyWeakPtr; +template +using TLMainPtr = folly::ReadMostlyMainPtr; +template +using TLWeakPtr = folly::ReadMostlyWeakPtr; + + +BENCHMARK(WeakPtrOneThread, n) { + benchmark(n); +} + +BENCHMARK(WeakPtrFourThreads, n) { + benchmark(n); +} + +BENCHMARK(RCUReadMostlyWeakPtrOneThread, n) { + benchmark(n); +} + +BENCHMARK(RCUReadMostlyWeakPtrFourThreads, n) { + benchmark(n); +} + +BENCHMARK(TLReadMostlyWeakPtrOneThread, n) { + benchmark(n); +} + +BENCHMARK(TLReadMostlyWeakPtrFourThreads, n) { + benchmark(n); +} + +int main(int argc, char** argv) { + gflags::ParseCommandLineFlags(&argc, &argv, true); + gflags::SetCommandLineOptionWithMode( + "bm_min_usec", "100000", gflags::SET_FLAG_IF_DEFAULT + ); + + folly::runBenchmarks(); + + return 0; +} diff --git a/folly/experimental/test/ReadMostlySharedPtrTest.cpp b/folly/experimental/test/ReadMostlySharedPtrTest.cpp new file mode 100644 index 00000000..65b79309 --- /dev/null +++ b/folly/experimental/test/ReadMostlySharedPtrTest.cpp @@ -0,0 +1,238 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/* -*- Mode: C++; tab-width: 2; c-basic-offset: 2; indent-tabs-mode: nil -*- */ + +#include +#include +#include +#include +#include +#include + +#include +#include + +using folly::ReadMostlyMainPtr; +using folly::ReadMostlyWeakPtr; +using folly::ReadMostlySharedPtr; + +// send SIGALRM to test process after this many seconds +const unsigned int TEST_TIMEOUT = 10; + +class ReadMostlySharedPtrTest : public ::testing::Test { + public: + ReadMostlySharedPtrTest() { + alarm(TEST_TIMEOUT); + } +}; + +struct TestObject { + int value; + std::atomic& counter; + + TestObject(int value, std::atomic& counter) + : value(value), counter(counter) { + ++counter; + } + + ~TestObject() { + assert(counter.load() > 0); + --counter; + } +}; + +// One side calls requestAndWait(), the other side calls waitForRequest(), +// does something and calls completed(). +class Coordinator { + public: + void requestAndWait() { + requestBaton_.post(); + completeBaton_.wait(); + } + + void waitForRequest() { + folly::RCURegisterThread(); + requestBaton_.wait(); + } + + void completed() { + completeBaton_.post(); + } + + private: + folly::Baton<> requestBaton_; + folly::Baton<> completeBaton_; +}; + +TEST_F(ReadMostlySharedPtrTest, BasicStores) { + ReadMostlyMainPtr ptr; + + // Store 1. + std::atomic cnt1{0}; + ptr.reset(folly::make_unique(1, cnt1)); + EXPECT_EQ(1, cnt1.load()); + + // Store 2, check that 1 is destroyed. + std::atomic cnt2{0}; + ptr.reset(folly::make_unique(2, cnt2)); + EXPECT_EQ(1, cnt2.load()); + EXPECT_EQ(0, cnt1.load()); + + // Store nullptr, check that 2 is destroyed. + ptr.reset(nullptr); + EXPECT_EQ(0, cnt2.load()); +} + +TEST_F(ReadMostlySharedPtrTest, BasicLoads) { + std::atomic cnt2{0}; + ReadMostlySharedPtr x; + + { + ReadMostlyMainPtr ptr; + + // Check that ptr is initially nullptr. + EXPECT_EQ(ptr.get(), nullptr); + + std::atomic cnt1{0}; + ptr.reset(folly::make_unique(1, cnt1)); + EXPECT_EQ(1, cnt1.load()); + + x = ptr; + EXPECT_EQ(1, x->value); + + ptr.reset(folly::make_unique(2, cnt2)); + EXPECT_EQ(1, cnt2.load()); + EXPECT_EQ(1, cnt1.load()); + + x = ptr; + EXPECT_EQ(2, x->value); + EXPECT_EQ(0, cnt1.load()); + + ptr.reset(nullptr); + EXPECT_EQ(1, cnt2.load()); + } + + EXPECT_EQ(1, cnt2.load()); + + x.reset(); + EXPECT_EQ(0, cnt2.load()); +} + +TEST_F(ReadMostlySharedPtrTest, LoadsFromThreads) { + std::atomic cnt{0}; + + { + ReadMostlyMainPtr ptr; + Coordinator loads[7]; + + std::thread t1([&] { + loads[0].waitForRequest(); + EXPECT_EQ(ptr.getShared(), nullptr); + loads[0].completed(); + + loads[3].waitForRequest(); + EXPECT_EQ(2, ptr.getShared()->value); + loads[3].completed(); + + loads[4].waitForRequest(); + EXPECT_EQ(4, ptr.getShared()->value); + loads[4].completed(); + + loads[5].waitForRequest(); + EXPECT_EQ(5, ptr.getShared()->value); + loads[5].completed(); + }); + + std::thread t2([&] { + loads[1].waitForRequest(); + EXPECT_EQ(1, ptr.getShared()->value); + loads[1].completed(); + + loads[2].waitForRequest(); + EXPECT_EQ(2, ptr.getShared()->value); + loads[2].completed(); + + loads[6].waitForRequest(); + EXPECT_EQ(5, ptr.getShared()->value); + loads[6].completed(); + }); + + loads[0].requestAndWait(); + + ptr.reset(folly::make_unique(1, cnt)); + loads[1].requestAndWait(); + + ptr.reset(folly::make_unique(2, cnt)); + loads[2].requestAndWait(); + loads[3].requestAndWait(); + + ptr.reset(folly::make_unique(3, cnt)); + ptr.reset(folly::make_unique(4, cnt)); + loads[4].requestAndWait(); + + ptr.reset(folly::make_unique(5, cnt)); + loads[5].requestAndWait(); + loads[6].requestAndWait(); + + EXPECT_EQ(1, cnt.load()); + + t1.join(); + t2.join(); + } + + EXPECT_EQ(0, cnt.load()); +} + +TEST_F(ReadMostlySharedPtrTest, Ctor) { + std::atomic cnt1{0}; + { + ReadMostlyMainPtr ptr( + folly::make_unique(1, cnt1)); + + EXPECT_EQ(1, ptr.getShared()->value); + } + + EXPECT_EQ(0, cnt1.load()); +} + +TEST_F(ReadMostlySharedPtrTest, ClearingCache) { + ReadMostlyMainPtr ptr; + + // Store 1. + std::atomic cnt1{0}; + ptr.reset(folly::make_unique(1, cnt1)); + + Coordinator c; + + std::thread t([&] { + // Cache the pointer for this thread. + ptr.getShared(); + c.requestAndWait(); + }); + + // Wait for the thread to cache pointer. + c.waitForRequest(); + EXPECT_EQ(1, cnt1.load()); + + // Store 2 and check that 1 is destroyed. + std::atomic cnt2{0}; + ptr.reset(folly::make_unique(2, cnt2)); + EXPECT_EQ(0, cnt1.load()); + + // Unblock thread. + c.completed(); + t.join(); +} diff --git a/folly/experimental/test/RefCountBenchmark.cpp b/folly/experimental/test/RefCountBenchmark.cpp new file mode 100644 index 00000000..4ea30f6d --- /dev/null +++ b/folly/experimental/test/RefCountBenchmark.cpp @@ -0,0 +1,97 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include + +#include +#include +#include + +namespace folly { + +template +void shutdown(Counter&) { +} + +void shutdown(RCURefCount& c) { + c.useGlobal(); + --c; +} + +void shutdown(TLRefCount& c) { + c.useGlobal(); + --c; +} + +template +void benchmark(size_t n) { + Counter x; + + std::vector ts; + + for (size_t t = 0; t < threadCount; ++t) { + ts.emplace_back([&]() { + for (size_t i = 0; i < n; ++i) { + ++x; + } + for (size_t i = 0; i < n; ++i) { + --x; + } + }); + } + + for (auto& t: ts) { + t.join(); + } + + shutdown(x); +} + +BENCHMARK(atomicOneThread, n) { + benchmark, 1>(n); +} + +BENCHMARK(atomicFourThreads, n) { + benchmark, 4>(n); +} + +BENCHMARK(RCURefCountOneThread, n) { + benchmark(n); +} + +BENCHMARK(RCURefCountFourThreads, n) { + benchmark(n); +} + +BENCHMARK(TLRefCountOneThread, n) { + benchmark(n); +} + +BENCHMARK(TLRefCountFourThreads, n) { + benchmark(n); +} + +} + +int main(int argc, char** argv) { + gflags::ParseCommandLineFlags(&argc, &argv, true); + gflags::SetCommandLineOptionWithMode( + "bm_min_usec", "100000", gflags::SET_FLAG_IF_DEFAULT + ); + + folly::runBenchmarks(); + + return 0; +} diff --git a/folly/experimental/test/RefCountTest.cpp b/folly/experimental/test/RefCountTest.cpp new file mode 100644 index 00000000..74fa2447 --- /dev/null +++ b/folly/experimental/test/RefCountTest.cpp @@ -0,0 +1,84 @@ +/* + * Copyright 2015 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#include + +#include +#include +#include + +#include + +namespace folly { + +template +void basicTest() { + constexpr size_t numIters = 100000; + constexpr size_t numThreads = 10; + + size_t got0 = 0; + + RefCount count; + + folly::Baton<> b; + + std::vector ts; + for (size_t t = 0; t < numThreads; ++t) { + ts.emplace_back([&count, &b, &got0, numIters, t]() { + for (size_t i = 0; i < numIters; ++i) { + auto ret = ++count; + + EXPECT_TRUE(ret > 1); + } + + if (t == 0) { + b.post(); + } + + for (size_t i = 0; i < numIters; ++i) { + auto ret = --count; + + if (ret == 0) { + ++got0; + EXPECT_EQ(numIters - 1, i); + } + } + }); + } + + b.wait(); + + count.useGlobal(); + EXPECT_TRUE(--count > 0); + + for (auto& t: ts) { + t.join(); + } + + EXPECT_EQ(1, got0); + + EXPECT_EQ(0, ++count); + EXPECT_EQ(0, ++count); +} + +TEST(RCURefCount, Basic) { + basicTest(); +} + +TEST(TLRefCount, Basic) { + basicTest(); +} + +} diff --git a/folly/test/ReadMostlySharedPtrBenchmark.cpp b/folly/test/ReadMostlySharedPtrBenchmark.cpp deleted file mode 100644 index 37abfc05..00000000 --- a/folly/test/ReadMostlySharedPtrBenchmark.cpp +++ /dev/null @@ -1,319 +0,0 @@ -/* - * Copyright 2015 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -/* -*- Mode: C++; tab-width: 2; c-basic-offset: 2; indent-tabs-mode: nil -*- */ - -#include -#include -#include -#include -#include - -#include - -/** - * @file Benchmark comparing three implementations of ReadMostlySharedPtr. - * - * Run with something like --bm_min_usec=100000. - */ - -namespace slow { - -// An implementation with thread local cache of shared_ptrs. -template -class ReadMostlySharedPtr : boost::noncopyable { - public: - explicit ReadMostlySharedPtr(std::shared_ptr ptr = nullptr) { - master_.ptr = std::move(ptr); - master_.version.store(1); - } - - std::shared_ptr store(std::shared_ptr ptr) { - std::lock_guard guard(mutex_); - std::swap(master_.ptr, ptr); - master_.version.fetch_add(1); - return ptr; - } - - std::shared_ptr load() const { - // We are the only thread accessing threadLocalCache_->version so it is - // fine to use memory_order_relaxed - auto local_version = - threadLocalCache_->version.load(std::memory_order_relaxed); - if (local_version != master_.version.load()) { - std::lock_guard guard(mutex_); - threadLocalCache_->ptr = master_.ptr; - threadLocalCache_->version.store(master_.version.load(), - std::memory_order_relaxed); - } - return threadLocalCache_->ptr; - } - - private: - struct VersionedPointer : boost::noncopyable { - VersionedPointer() : version(0) { } - std::shared_ptr ptr; - std::atomic version; - }; - - folly::ThreadLocal threadLocalCache_; - VersionedPointer master_; - - // Ensures safety between concurrent store() and load() calls - mutable std::mutex mutex_; -}; - -} - - -/** - * At the moment the fastest implementation in this benchmark. - * A real RCU implementation would most likely be significantly better. - */ -namespace fast { - -/** - * Contains a version number and a shared_ptr that points to the most recent - * object. The load() method uses thread-local storage to efficiently return - * the current pointer without locking when the pointer has not changed. - * The version of the pointer in thread-local cache is compared to the - * master version. If the master is found to be newer, it is copied into - * the thread-local cache under a lock. The store() method grabs the lock, - * updates the master pointer and bumps the version number. - * - * The downside is that it doesn't clear or update thread-local cache - * when updating the pointer. This means that old instances of T can stay - * alive in thread-local cache indefinitely if load() is not called from - * some threads. - */ -template -class ReadMostlySharedPtr : boost::noncopyable { - public: - explicit ReadMostlySharedPtr(std::shared_ptr ptr = nullptr) { - masterPtr_ = std::move(ptr); - masterVersion_.store(1); - } - - /** - * Replaces the managed object. - */ - void store(std::shared_ptr ptr) { - { - std::lock_guard guard(mutex_); - // Swap to avoid calling ~T() under the lock - std::swap(masterPtr_, ptr); - masterVersion_.fetch_add(1); - } - } - - /** - * Returns a shared_ptr to the managed object. - */ - std::shared_ptr load() const { - auto& local = *threadLocalCache_; - if (local.version != masterVersion_.load()) { - std::lock_guard guard(mutex_); - - if (!masterPtr_) { - local.ptr = nullptr; - } else { - // The following expression is tricky. - // - // It creates a shared_ptr> that points to a copy of - // masterPtr_. The reference counter of this shared_ptr> - // will normally only be modified from this thread, which avoids - // cache line bouncing. (Though the caller is free to pass the pointer - // to other threads and bump reference counter from there) - // - // Then this shared_ptr> is turned into shared_ptr. - // This means that the returned shared_ptr will internally point to - // control block of the shared_ptr>, but will dereference - // to T, not shared_ptr. - local.ptr = std::shared_ptr( - std::make_shared>(masterPtr_), - masterPtr_.get()); - } - - local.version = masterVersion_.load(); - } - return local.ptr; - } - - private: - struct VersionedPointer : boost::noncopyable { - VersionedPointer() { } - std::shared_ptr ptr; - uint64_t version = 0; - }; - - folly::ThreadLocal threadLocalCache_; - - std::shared_ptr masterPtr_; - std::atomic masterVersion_; - - // Ensures safety between concurrent store() and load() calls - mutable std::mutex mutex_; -}; - -} - - -template -void benchReads(int n) { - PtrInt ptr(folly::make_unique(42)); - for (int i = 0; i < n; ++i) { - auto val = ptr.load(); - folly::doNotOptimizeAway(val.get()); - } -} - -template -void benchWrites(int n) { - PtrInt ptr; - for (int i = 0; i < n; ++i) { - ptr.store(folly::make_unique(3)); - } -} - -template -void benchReadsWhenWriting(int n) { - PtrInt ptr; - std::atomic shutdown {false}; - std::thread writing_thread; - - BENCHMARK_SUSPEND { - writing_thread = std::thread([&] { - for (uint64_t i = 0; !shutdown.load(); ++i) { - ptr.store(folly::make_unique(3)); - } - }); - } - - for (int i = 0; i < n; ++i) { - auto val = ptr.load(); - folly::doNotOptimizeAway(val.get()); - } - - BENCHMARK_SUSPEND { - shutdown.store(true); - writing_thread.join(); - } -} - - -template -void benchWritesWhenReading(int n) { - PtrInt ptr; - std::atomic shutdown {false}; - std::thread reading_thread; - - BENCHMARK_SUSPEND { - reading_thread = std::thread([&] { - for (uint64_t i = 0; !shutdown.load(); ++i) { - auto val = ptr.load(); - folly::doNotOptimizeAway(val.get()); - } - }); - } - - - for (int i = 0; i < n; ++i) { - ptr.store(folly::make_unique(3)); - } - - BENCHMARK_SUSPEND { - shutdown.store(true); - reading_thread.join(); - } -} - - -template -void benchReadsIn10Threads(int n) { - PtrInt ptr(folly::make_unique(27)); - std::vector threads(10); - int n_per_thread = n; - - for (std::thread& t: threads) { - t = std::thread([&] { - for (int i = 0; i < n; ++i) { - auto val = ptr.load(); - folly::doNotOptimizeAway(val.get()); - } - }); - } - - for (std::thread& t: threads) { - t.join(); - } -} - - -#define BENCH(name) \ - BENCHMARK(name ## _Slow, n) { \ - bench ## name >(n); \ - } \ - BENCHMARK(name ## _ReadMostlySharedPtr, n) { \ - bench ## name >(n);\ - } \ - BENCHMARK(name ## _FastReadMostlySharedPtr, n) { \ - bench ## name >(n); \ - } \ - BENCHMARK_DRAW_LINE(); - - -BENCH(Reads) -BENCH(Writes) -BENCH(ReadsWhenWriting) -BENCH(WritesWhenReading) -BENCH(ReadsIn10Threads) - -int main(int argc, char** argv) { - gflags::ParseCommandLineFlags(&argc, &argv, true); - gflags::SetCommandLineOptionWithMode( - "bm_min_usec", "100000", gflags::SET_FLAG_IF_DEFAULT - ); - - folly::runBenchmarks(); - - return 0; -} - -/* -============================================================================ -folly/test/ReadMostlySharedPtrBenchmark.cpp relative time/iter iters/s -============================================================================ -Reads_Slow 21.05ns 47.52M -Reads_ReadMostlySharedPtr 30.57ns 32.71M -Reads_FastReadMostlySharedPtr 21.24ns 47.09M ----------------------------------------------------------------------------- -Writes_Slow 117.52ns 8.51M -Writes_ReadMostlySharedPtr 145.26ns 6.88M -Writes_FastReadMostlySharedPtr 116.26ns 8.60M ----------------------------------------------------------------------------- -ReadsWhenWriting_Slow 56.18ns 17.80M -ReadsWhenWriting_ReadMostlySharedPtr 141.32ns 7.08M -ReadsWhenWriting_FastReadMostlySharedPtr 51.82ns 19.30M ----------------------------------------------------------------------------- -WritesWhenReading_Slow 828.32ns 1.21M -WritesWhenReading_ReadMostlySharedPtr 3.00us 333.63K -WritesWhenReading_FastReadMostlySharedPtr 677.28ns 1.48M ----------------------------------------------------------------------------- -ReadsIn10Threads_Slow 509.37ns 1.96M -ReadsIn10Threads_ReadMostlySharedPtr 34.33ns 29.13M -ReadsIn10Threads_FastReadMostlySharedPtr 26.31ns 38.00M ----------------------------------------------------------------------------- -============================================================================ -*/ diff --git a/folly/test/ReadMostlySharedPtrTest.cpp b/folly/test/ReadMostlySharedPtrTest.cpp deleted file mode 100644 index 2aeb4fca..00000000 --- a/folly/test/ReadMostlySharedPtrTest.cpp +++ /dev/null @@ -1,382 +0,0 @@ -/* - * Copyright 2015 Facebook, Inc. - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -/* -*- Mode: C++; tab-width: 2; c-basic-offset: 2; indent-tabs-mode: nil -*- */ - -#include -#include -#include -#include -#include -#include - -#include - -using folly::ReadMostlySharedPtr; - -// send SIGALRM to test process after this many seconds -const unsigned int TEST_TIMEOUT = 10; - -class ReadMostlySharedPtrTest : public ::testing::Test { - public: - ReadMostlySharedPtrTest() { - alarm(TEST_TIMEOUT); - } -}; - -struct TestObject { - int value; - std::atomic& counter; - - TestObject(int value, std::atomic& counter) - : value(value), counter(counter) { - ++counter; - } - - ~TestObject() { - assert(counter.load() > 0); - --counter; - } -}; - -// One side calls requestAndWait(), the other side calls waitForRequest(), -// does something and calls completed(). -class Coordinator { - public: - void requestAndWait() { - { - std::lock_guard lock(mutex); - assert(!is_requested); - assert(!is_completed); - is_requested = true; - } - cv.notify_all(); - { - std::unique_lock lock(mutex); - cv.wait(lock, [&] { return is_completed; }); - } - } - - void waitForRequest() { - std::unique_lock lock(mutex); - assert(!is_completed); - cv.wait(lock, [&] { return is_requested; }); - } - - void completed() { - { - std::lock_guard lock(mutex); - assert(is_requested); - is_completed = true; - } - cv.notify_all(); - } - - private: - bool is_requested = false; - bool is_completed = false; - std::condition_variable cv; - std::mutex mutex; -}; - -TEST_F(ReadMostlySharedPtrTest, BasicStores) { - ReadMostlySharedPtr ptr; - - // Store 1. - std::atomic cnt1{0}; - ptr.store(folly::make_unique(1, cnt1)); - EXPECT_EQ(1, cnt1.load()); - - // Store 2, check that 1 is destroyed. - std::atomic cnt2{0}; - ptr.store(folly::make_unique(2, cnt2)); - EXPECT_EQ(1, cnt2.load()); - EXPECT_EQ(0, cnt1.load()); - - // Store nullptr, check that 2 is destroyed. - ptr.store(nullptr); - EXPECT_EQ(0, cnt2.load()); -} - -TEST_F(ReadMostlySharedPtrTest, BasicLoads) { - std::atomic cnt2{0}; - ReadMostlySharedPtr::ReadPtr x; - - { - ReadMostlySharedPtr ptr; - - // Check that ptr is initially nullptr. - EXPECT_EQ(ptr.load(), nullptr); - - std::atomic cnt1{0}; - ptr.store(folly::make_unique(1, cnt1)); - EXPECT_EQ(1, cnt1.load()); - - x = ptr.load(); - EXPECT_EQ(1, x->value); - - ptr.store(folly::make_unique(2, cnt2)); - EXPECT_EQ(1, cnt2.load()); - EXPECT_EQ(1, cnt1.load()); - - x = ptr.load(); - EXPECT_EQ(2, x->value); - EXPECT_EQ(0, cnt1.load()); - - ptr.store(nullptr); - EXPECT_EQ(1, cnt2.load()); - } - - EXPECT_EQ(1, cnt2.load()); - - x.reset(); - EXPECT_EQ(0, cnt2.load()); -} - -TEST_F(ReadMostlySharedPtrTest, LoadsFromThreads) { - std::atomic cnt{0}; - - { - ReadMostlySharedPtr ptr; - Coordinator loads[7]; - - std::thread t1([&] { - loads[0].waitForRequest(); - EXPECT_EQ(ptr.load(), nullptr); - loads[0].completed(); - - loads[3].waitForRequest(); - EXPECT_EQ(2, ptr.load()->value); - loads[3].completed(); - - loads[4].waitForRequest(); - EXPECT_EQ(4, ptr.load()->value); - loads[4].completed(); - - loads[5].waitForRequest(); - EXPECT_EQ(5, ptr.load()->value); - loads[5].completed(); - }); - - std::thread t2([&] { - loads[1].waitForRequest(); - EXPECT_EQ(1, ptr.load()->value); - loads[1].completed(); - - loads[2].waitForRequest(); - EXPECT_EQ(2, ptr.load()->value); - loads[2].completed(); - - loads[6].waitForRequest(); - EXPECT_EQ(5, ptr.load()->value); - loads[6].completed(); - }); - - loads[0].requestAndWait(); - - ptr.store(folly::make_unique(1, cnt)); - loads[1].requestAndWait(); - - ptr.store(folly::make_unique(2, cnt)); - loads[2].requestAndWait(); - loads[3].requestAndWait(); - - ptr.store(folly::make_unique(3, cnt)); - ptr.store(folly::make_unique(4, cnt)); - loads[4].requestAndWait(); - - ptr.store(folly::make_unique(5, cnt)); - loads[5].requestAndWait(); - loads[6].requestAndWait(); - - EXPECT_EQ(1, cnt.load()); - - t1.join(); - t2.join(); - } - - EXPECT_EQ(0, cnt.load()); -} - -TEST_F(ReadMostlySharedPtrTest, Ctor) { - std::atomic cnt1{0}; - { - ReadMostlySharedPtr ptr( - folly::make_unique(1, cnt1)); - - EXPECT_EQ(1, ptr.load()->value); - } - - EXPECT_EQ(0, cnt1.load()); -} - -TEST_F(ReadMostlySharedPtrTest, ClearingCache) { - ReadMostlySharedPtr ptr; - - // Store 1. - std::atomic cnt1{0}; - ptr.store(folly::make_unique(1, cnt1)); - - Coordinator c; - - std::thread t([&] { - // Cache the pointer for this thread. - ptr.load(); - c.requestAndWait(); - }); - - // Wait for the thread to cache pointer. - c.waitForRequest(); - EXPECT_EQ(1, cnt1.load()); - - // Store 2 and check that 1 is destroyed. - std::atomic cnt2{0}; - ptr.store(folly::make_unique(2, cnt2)); - EXPECT_EQ(0, cnt1.load()); - - // Unblock thread. - c.completed(); - t.join(); -} - -TEST_F(ReadMostlySharedPtrTest, SlowDestructor) { - struct Thingy { - Coordinator* dtor; - - Thingy(Coordinator* dtor = nullptr) : dtor(dtor) {} - - ~Thingy() { - if (dtor) { - dtor->requestAndWait(); - } - } - }; - - Coordinator dtor; - - ReadMostlySharedPtr ptr; - ptr.store(folly::make_unique(&dtor)); - - std::thread t([&] { - // This will block in ~Thingy(). - ptr.store(folly::make_unique()); - }); - - // Wait until store() in thread calls ~T(). - dtor.waitForRequest(); - // Do a store while another store() is stuck in ~T(). - ptr.store(folly::make_unique()); - // Let the other store() go. - dtor.completed(); - - t.join(); -} - -TEST_F(ReadMostlySharedPtrTest, StressTest) { - const int ptr_count = 2; - const int thread_count = 5; - const std::chrono::milliseconds duration(100); - const std::chrono::milliseconds upd_delay(1); - const std::chrono::milliseconds respawn_delay(1); - - struct Instance { - std::atomic value{0}; - std::atomic prev_value{0}; - ReadMostlySharedPtr ptr; - }; - - struct Thread { - std::thread t; - std::atomic shutdown{false}; - }; - - std::atomic counter(0); - std::vector instances(ptr_count); - std::vector threads(thread_count); - std::atomic seed(0); - - // Threads that call load() and checking value. - auto thread_func = [&](int t) { - pthread_setname_np(pthread_self(), - ("load" + folly::to(t)).c_str()); - std::mt19937 rnd(++seed); - while (!threads[t].shutdown.load()) { - Instance& instance = instances[rnd() % instances.size()]; - int val1 = instance.prev_value.load(); - auto p = instance.ptr.load(); - int val = p ? p->value : 0; - int val2 = instance.value.load(); - EXPECT_LE(val1, val); - EXPECT_LE(val, val2); - } - }; - - for (size_t t = 0; t < threads.size(); ++t) { - threads[t].t = std::thread(thread_func, t); - } - - std::atomic shutdown(false); - - // Thread that calls store() occasionally. - std::thread update_thread([&] { - pthread_setname_np(pthread_self(), "store"); - std::mt19937 rnd(++seed); - while (!shutdown.load()) { - Instance& instance = instances[rnd() % instances.size()]; - int val = ++instance.value; - instance.ptr.store(folly::make_unique(val, counter)); - ++instance.prev_value; - /* sleep override */ - std::this_thread::sleep_for(upd_delay); - } - }); - - // Thread that joins and spawns load() threads occasionally. - std::thread respawn_thread([&] { - pthread_setname_np(pthread_self(), "respawn"); - std::mt19937 rnd(++seed); - while (!shutdown.load()) { - int t = rnd() % threads.size(); - threads[t].shutdown.store(true); - threads[t].t.join(); - threads[t].shutdown.store(false); - threads[t].t = std::thread(thread_func, t); - - /* sleep override */ - std::this_thread::sleep_for(respawn_delay); - } - }); - - // Let all of this run for some time. - /* sleep override */ - std::this_thread::sleep_for(duration); - - // Shut all of this down. - shutdown.store(true); - - update_thread.join(); - respawn_thread.join(); - for (auto& t: threads) { - t.shutdown.store(true); - t.t.join(); - } - - for (auto& instance: instances) { - instance.ptr.store(nullptr); - EXPECT_EQ(instance.value.load(), instance.prev_value.load()); - } - - EXPECT_EQ(0, counter.load()); -} -- 2.34.1