diff --git a/src/rcu.h b/src/rcu.h index 832797565..50fca382f 100644 --- a/src/rcu.h +++ b/src/rcu.h @@ -1,206 +1,233 @@ // Copyright (c) 2018 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #ifndef BITCOIN_RCU_H #define BITCOIN_RCU_H #include #include #include #include #include #include +#include #include #include class RCUInfos; class RCUReadLock; class RCUInfos { std::atomic state; std::atomic next; std::map> cleanups; // The largest revision possible means unlocked. static const uint64_t UNLOCKED = -uint64_t(1); RCUInfos(); ~RCUInfos(); void readLock() { assert(!isLocked()); state.store(revision.load()); } void readFree() { assert(isLocked()); state.store(UNLOCKED); } bool isLocked() const { return state.load() != UNLOCKED; } void registerCleanup(const std::function &f) { cleanups.emplace(++revision, f); } void synchronize(); void runCleanups(); uint64_t hasSyncedTo(uint64_t cutoff = UNLOCKED); friend class RCULock; friend struct RCUTest; static std::atomic revision; static thread_local RCUInfos infos; }; class RCULock : public boost::noncopyable { RCUInfos *infos; RCULock(RCUInfos *infosIn) : infos(infosIn) { infos->readLock(); } friend class RCUInfos; public: RCULock() : RCULock(&RCUInfos::infos) {} ~RCULock() { infos->readFree(); } static bool isLocked() { return RCUInfos::infos.isLocked(); } static void registerCleanup(const std::function &f) { RCUInfos::infos.registerCleanup(f); } static void synchronize() { RCUInfos::infos.synchronize(); } }; template class RCUPtr { T *ptr; // Private construction, so factories have to be used. explicit RCUPtr(T *ptrIn) : ptr(ptrIn) {} public: RCUPtr() : ptr(nullptr) {} ~RCUPtr() { if (ptr != nullptr) { ptr->release(); } } /** * Acquire ownership of some pointer. */ static RCUPtr acquire(T *&ptrIn) { RCUPtr ret(ptrIn); ptrIn = nullptr; return ret; } /** * Construct a new object that is owned by the pointer. */ template static RCUPtr make(Args &&... args) { return RCUPtr(new T(std::forward(args)...)); } /** * Construct a new RCUPtr without transfering owership. */ static RCUPtr copy(T *ptr) { if (ptr != nullptr) { ptr->acquire(); } return RCUPtr::acquire(ptr); } /** * Copy semantic. */ RCUPtr(const RCUPtr &src) : ptr(src.ptr) { if (ptr != nullptr) { ptr->acquire(); } } RCUPtr &operator=(const RCUPtr &rhs) { RCUPtr tmp(rhs); std::swap(ptr, tmp.ptr); return *this; } /** * Move semantic. */ RCUPtr(RCUPtr &&src) : RCUPtr() { std::swap(ptr, src.ptr); } RCUPtr &operator=(RCUPtr &&rhs) { std::swap(ptr, rhs.ptr); return *this; } /** * Get allows to access the undelying pointer. RCUPtr keeps ownership. */ T *get() { return ptr; } const T *get() const { return ptr; } /** * Release transfers ownership of the pointer from RCUPtr to the caller. */ T *release() { T *oldPtr = ptr; ptr = nullptr; return oldPtr; } /** * Operator overloading for convenience. */ T *operator->() { return ptr; } const T *operator->() const { return ptr; } T &operator*() { return *ptr; } const T &operator*() const { return *ptr; } explicit operator bool() const { return ptr != nullptr; } + + /** + * Equality checks. + */ + friend bool operator==(const RCUPtr &lhs, const T *rhs) { + return lhs.get() == rhs; + } + + friend bool operator==(const RCUPtr &lhs, const RCUPtr &rhs) { + return lhs == rhs.get(); + } + + friend bool operator!=(const RCUPtr &lhs, const T *rhs) { + return !(lhs == rhs); + } + + friend bool operator!=(const RCUPtr &lhs, const RCUPtr &rhs) { + return !(lhs == rhs); + } + + /** + * ostream support. + */ + friend std::ostream &operator<<(std::ostream &stream, const RCUPtr &ptr) { + return stream << ptr.ptr; + } }; #define IMPLEMENT_RCU_REFCOUNT(T) \ private: \ std::atomic refcount{0}; \ \ void acquire() { refcount++; } \ \ bool tryDecrement() { \ T count = refcount.load(); \ while (count > 0) { \ if (refcount.compare_exchange_weak(count, count - 1)) { \ return true; \ } \ } \ \ return false; \ } \ \ void release() { \ if (tryDecrement()) { \ return; \ } \ \ RCULock::registerCleanup([this] { \ if (tryDecrement()) { \ return; \ } \ \ delete this; \ }); \ } \ \ static_assert(std::is_integral::value, "T must be an integral type."); \ static_assert(std::is_unsigned::value, "T must be unsigned."); \ \ template friend class ::RCUPtr #endif // BITCOIN_RCU_H diff --git a/src/test/rcu_tests.cpp b/src/test/rcu_tests.cpp index 2131361f0..4d7864624 100644 --- a/src/test/rcu_tests.cpp +++ b/src/test/rcu_tests.cpp @@ -1,366 +1,388 @@ // Copyright (c) 2018 The Bitcoin developers // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include "rcu.h" #include "test/test_bitcoin.h" #include #include struct RCUTest { static uint64_t getRevision() { return RCUInfos::revision.load(); } static uint64_t hasSyncedTo(uint64_t syncRev) { return RCUInfos::infos.hasSyncedTo(syncRev); } static std::map> &getCleanups() { return RCUInfos::infos.cleanups; } }; BOOST_FIXTURE_TEST_SUITE(rcu_tests, BasicTestingSetup) enum RCUTestStep { Init, Locked, LockAck, RCULocked, Synchronizing, Synchronized, }; #define WAIT_FOR_STEP(step) \ do { \ cond.notify_all(); \ } while (!cond.wait_for(lock, std::chrono::milliseconds(1), \ [&] { return otherstep == step; })) void synchronize(std::atomic &step, const std::atomic &otherstep, CWaitableCriticalSection &cs, std::condition_variable &cond, std::atomic &syncRev) { assert(step == RCUTestStep::Init); { WAIT_LOCK(cs, lock); step = RCUTestStep::Locked; // Wait for our lock to be acknowledged. WAIT_FOR_STEP(RCUTestStep::LockAck); RCULock rculock; // Update step. step = RCUTestStep::RCULocked; // Wait for master. WAIT_FOR_STEP(RCUTestStep::RCULocked); } // Update step. syncRev = RCUTest::getRevision() + 1; step = RCUTestStep::Synchronizing; assert(!RCUTest::hasSyncedTo(syncRev)); // We wait for readers. RCULock::synchronize(); // Update step. step = RCUTestStep::Synchronized; } void lockAndWaitForSynchronize(std::atomic &step, const std::atomic &otherstep, CWaitableCriticalSection &cs, std::condition_variable &cond, std::atomic &syncRev) { assert(step == RCUTestStep::Init); WAIT_LOCK(cs, lock); // Wait for th eother thread to be locked. WAIT_FOR_STEP(RCUTestStep::Locked); step = RCUTestStep::LockAck; // Wait for the synchronizing tread to take its RCU lock. WAIT_FOR_STEP(RCUTestStep::RCULocked); assert(!RCUTest::hasSyncedTo(syncRev)); { RCULock rculock; // Update master step. step = RCUTestStep::RCULocked; while (RCUTest::getRevision() < syncRev) { WAIT_FOR_STEP(RCUTestStep::Synchronizing); } assert(RCUTest::getRevision() >= syncRev); assert(otherstep.load() == RCUTestStep::Synchronizing); } assert(RCUTest::hasSyncedTo(syncRev) >= syncRev); WAIT_FOR_STEP(RCUTestStep::Synchronized); } static const int COUNT = 128; BOOST_AUTO_TEST_CASE(synchronize_test) { CWaitableCriticalSection cs; std::condition_variable cond; std::atomic parentstep; std::atomic childstep; std::atomic syncRev; for (int i = 0; i < COUNT; i++) { parentstep = RCUTestStep::Init; childstep = RCUTestStep::Init; syncRev = RCUTest::getRevision() + 1; std::thread tlock([&] { lockAndWaitForSynchronize(parentstep, childstep, cs, cond, syncRev); }); std::thread tsync( [&] { synchronize(childstep, parentstep, cs, cond, syncRev); }); tlock.join(); tsync.join(); } } /** * Version of Boost::test prior to 1.64 have issues when dealing with nullptr_t. * In order to work around this, we ensure that the null pointers are typed in a * way that Boost will like better. * * TODO: Use nullptr directly once the minimum version of boost is 1.64 or more. */ #define NULLPTR(T) static_cast(nullptr) BOOST_AUTO_TEST_CASE(cleanup_test) { BOOST_CHECK(RCUTest::getCleanups().empty()); bool isClean1 = false; RCULock::registerCleanup([&] { isClean1 = true; }); BOOST_CHECK(!isClean1); BOOST_CHECK_EQUAL(RCUTest::getCleanups().size(), 1); BOOST_CHECK_EQUAL(RCUTest::getRevision(), RCUTest::getCleanups().begin()->first); // Synchronize runs the cleanups. RCULock::synchronize(); BOOST_CHECK(RCUTest::getCleanups().empty()); BOOST_CHECK(isClean1); // Check multiple callbacks. isClean1 = false; bool isClean2 = false; bool isClean3 = false; RCULock::registerCleanup([&] { isClean1 = true; }); RCULock::registerCleanup([&] { isClean2 = true; }); RCULock::registerCleanup([&] { isClean3 = true; }); BOOST_CHECK_EQUAL(RCUTest::getCleanups().size(), 3); RCULock::synchronize(); BOOST_CHECK(RCUTest::getCleanups().empty()); BOOST_CHECK(isClean1); BOOST_CHECK(isClean2); BOOST_CHECK(isClean3); // Check callbacks adding each others. isClean1 = false; isClean2 = false; isClean3 = false; RCULock::registerCleanup([&] { isClean1 = true; RCULock::registerCleanup([&] { isClean2 = true; RCULock::registerCleanup([&] { isClean3 = true; }); }); }); BOOST_CHECK_EQUAL(RCUTest::getCleanups().size(), 1); RCULock::synchronize(); BOOST_CHECK(RCUTest::getCleanups().empty()); BOOST_CHECK(isClean1); BOOST_CHECK(isClean2); BOOST_CHECK(isClean3); } class RCURefTestItem { IMPLEMENT_RCU_REFCOUNT(uint32_t); const std::function cleanupfun; public: explicit RCURefTestItem(const std::function &fun) : cleanupfun(fun) {} ~RCURefTestItem() { cleanupfun(); } uint32_t getRefCount() const { return refcount.load(); } }; -BOOST_AUTO_TEST_CASE(rcuref_test) { +BOOST_AUTO_TEST_CASE(rcuptr_test) { // Make sure it works for null. { RCURefTestItem *ptr = nullptr; RCUPtr::copy(ptr); RCUPtr::acquire(ptr); } // Check the destruction mechanism. bool isDestroyed = false; { auto rcuptr = RCUPtr::make([&] { isDestroyed = true; }); BOOST_CHECK_EQUAL(rcuptr->getRefCount(), 0); } // rcuptr waits for synchronization to destroy. BOOST_CHECK(!isDestroyed); RCULock::synchronize(); BOOST_CHECK(isDestroyed); // Check that copy behaves properly. isDestroyed = false; RCUPtr gptr; { auto rcuptr = RCUPtr::make([&] { isDestroyed = true; }); BOOST_CHECK_EQUAL(rcuptr->getRefCount(), 0); gptr = rcuptr; BOOST_CHECK_EQUAL(rcuptr->getRefCount(), 1); BOOST_CHECK_EQUAL(gptr->getRefCount(), 1); auto rcuptrcopy = rcuptr; BOOST_CHECK_EQUAL(rcuptrcopy->getRefCount(), 2); BOOST_CHECK_EQUAL(rcuptr->getRefCount(), 2); BOOST_CHECK_EQUAL(gptr->getRefCount(), 2); } BOOST_CHECK_EQUAL(gptr->getRefCount(), 0); RCULock::synchronize(); BOOST_CHECK(!isDestroyed); gptr = RCUPtr(); BOOST_CHECK(!isDestroyed); RCULock::synchronize(); BOOST_CHECK(isDestroyed); +} + +BOOST_AUTO_TEST_CASE(rcuptr_operator_test) { + auto gptr = RCUPtr(); + auto ptr = new RCURefTestItem([] {}); + auto oldPtr = ptr; + + auto altptr = RCUPtr::make([] {}); // Check various operators. BOOST_CHECK_EQUAL(gptr.get(), NULLPTR(RCURefTestItem)); - BOOST_CHECK_EQUAL(gptr.get(), &*gptr); + BOOST_CHECK_EQUAL(&*gptr, NULLPTR(RCURefTestItem)); + BOOST_CHECK_EQUAL(gptr, NULLPTR(RCURefTestItem)); BOOST_CHECK(!gptr); - auto ptr = new RCURefTestItem([] {}); - auto oldPtr = ptr; + auto copyptr = gptr; + BOOST_CHECK(gptr == nullptr); + BOOST_CHECK(gptr != oldPtr); + BOOST_CHECK(gptr == copyptr); + BOOST_CHECK(gptr != altptr); + gptr = RCUPtr::acquire(ptr); + BOOST_CHECK_EQUAL(ptr, NULLPTR(RCURefTestItem)); BOOST_CHECK_EQUAL(gptr.get(), oldPtr); BOOST_CHECK_EQUAL(&*gptr, oldPtr); + BOOST_CHECK_EQUAL(gptr, oldPtr); BOOST_CHECK(gptr); + + copyptr = gptr; + BOOST_CHECK(gptr != nullptr); + BOOST_CHECK(gptr == oldPtr); + BOOST_CHECK(gptr == copyptr); + BOOST_CHECK(gptr != altptr); } class RCURefMoveTestItem { const std::function cleanupfun; public: explicit RCURefMoveTestItem(const std::function &fun) : cleanupfun(fun) {} ~RCURefMoveTestItem() { cleanupfun(); } void acquire() { throw std::runtime_error("RCUPtr incremented the refcount"); } void release() { RCULock::registerCleanup([this] { delete this; }); } }; -BOOST_AUTO_TEST_CASE(move_rcuref_test) { +BOOST_AUTO_TEST_CASE(move_rcuptr_test) { bool isDestroyed = false; // Check tat copy is failing. auto rcuptr1 = RCUPtr::make([&] { isDestroyed = true; }); BOOST_CHECK_THROW(rcuptr1->acquire(), std::runtime_error); BOOST_CHECK_THROW(auto rcuptrcopy = rcuptr1;, std::runtime_error); // Try to move. auto rcuptr2 = std::move(rcuptr1); RCULock::synchronize(); BOOST_CHECK(!isDestroyed); // Move to a local and check proper destruction. { auto rcuptr3 = std::move(rcuptr2); } BOOST_CHECK(!isDestroyed); RCULock::synchronize(); BOOST_CHECK(isDestroyed); // Let's try to swap. isDestroyed = false; rcuptr1 = RCUPtr::make([&] { isDestroyed = true; }); std::swap(rcuptr1, rcuptr2); RCULock::synchronize(); BOOST_CHECK(!isDestroyed); // Chain moves to make sure there are no double free. { auto rcuptr3 = std::move(rcuptr2); auto rcuptr4 = std::move(rcuptr3); std::swap(rcuptr1, rcuptr4); } RCULock::synchronize(); BOOST_CHECK(!isDestroyed); // Check we can return from a function. { auto r = ([&] { auto moved = std::move(rcuptr1); return moved; })(); RCULock::synchronize(); BOOST_CHECK(!isDestroyed); } BOOST_CHECK(!isDestroyed); RCULock::synchronize(); BOOST_CHECK(isDestroyed); // Acquire/release workflow. isDestroyed = false; auto ptr = new RCURefMoveTestItem([&] { isDestroyed = true; }); auto ptrCopy = ptr; BOOST_CHECK_THROW(RCUPtr::copy(ptr), std::runtime_error); rcuptr1 = RCUPtr::acquire(ptr); - BOOST_CHECK_EQUAL(rcuptr1.get(), ptrCopy); + BOOST_CHECK_EQUAL(rcuptr1, ptrCopy); BOOST_CHECK_EQUAL(ptr, NULLPTR(RCURefMoveTestItem)); ptr = rcuptr1.release(); - BOOST_CHECK_EQUAL(rcuptr1.get(), NULLPTR(RCURefMoveTestItem)); + BOOST_CHECK_EQUAL(rcuptr1, NULLPTR(RCURefMoveTestItem)); BOOST_CHECK_EQUAL(ptr, ptrCopy); RCULock::synchronize(); BOOST_CHECK(!isDestroyed); RCUPtr::acquire(ptr); + BOOST_CHECK_EQUAL(ptr, NULLPTR(RCURefMoveTestItem)); BOOST_CHECK(!isDestroyed); RCULock::synchronize(); BOOST_CHECK(isDestroyed); } BOOST_AUTO_TEST_SUITE_END()