diff --git a/src/radix.h b/src/radix.h index 0467874ee..585555ef4 100644 --- a/src/radix.h +++ b/src/radix.h @@ -1,362 +1,362 @@ // Copyright (c) 2019 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_RADIX_H #define BITCOIN_RADIX_H #include #include #include #include #include #include #include /** * This is a radix tree storing values identified by a unique key. * * The tree is composed of nodes (RadixNode) containing an array of * RadixElement. The key is split into chunks of a few bits that serve as an * index into that array. RadixElement is a discriminated union of either a * RadixNode* representing the next level in the tree, or a T* representing a * leaf. New RadixNode are added lazily when two leaves would go in the same * slot. * * Reads walk the tree using sequential atomic loads, and insertions are done * using CAS, which ensures both can be executed lock free. Removing any * elements from the tree can also be done using CAS, but requires waiting for * other readers before being destroyed. The tree uses RCU to track which thread * is reading the tree, which allows deletion to wait for other readers to be up * to speed before destroying anything. It is therefore crucial that the lock be * taken before reading anything in the tree. */ template struct RadixTree { private: static const int BITS = 4; static const int MASK = (1 << BITS) - 1; static const size_t CHILD_PER_LEVEL = 1 << BITS; - using K = typename std::remove_reference().getId())>::type; - static const size_t KEY_BITS = 8 * sizeof(K); + static const size_t KEY_BITS = 8 * sizeof(KeyType); static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS; struct RadixElement; struct RadixNode; std::atomic root; public: RadixTree() : root(RadixElement()) {} ~RadixTree() { root.load().decrementRefCount(); } /** * Copy semantic. */ RadixTree(const RadixTree &src) : RadixTree() { { RCULock lock; RadixElement e = src.root.load(); e.incrementRefCount(); root = e; } // Make sure we the writes in the tree are behind us so // this copy won't mutate behind our back. RCULock::synchronize(); } RadixTree &operator=(const RadixTree &rhs) { { RCULock lock; RadixElement e = rhs.root.load(); e.incrementRefCount(); root.load().decrementRefCount(); root = e; } // Make sure we the writes in the tree are behind us so // this copy won't mutate behind our back. RCULock::synchronize(); return *this; } /** * Move semantic. */ RadixTree(RadixTree &&src) : RadixTree() { *this = std::move(src); } RadixTree &operator=(RadixTree &&rhs) { { RCULock lock; RadixElement e = rhs.root.load(); rhs.root = root.load(); root = e; } return *this; } /** * Insert a value into the tree. * Returns true if the value was inserted, false if it was already present. */ bool insert(const RCUPtr &value) { return insert(value->getId(), value); } /** * Get the value corresponding to a key. * Returns the value if found, nullptr if not. */ - RCUPtr get(const K &key) { + RCUPtr get(const KeyType &key) { uint32_t level = TOP_LEVEL; RCULock lock; RadixElement e = root.load(); // Find a leaf. while (e.isNode()) { e = e.getNode()->get(level--, key)->load(); } T *leaf = e.getLeaf(); if (leaf == nullptr || leaf->getId() != key) { // We failed to find the proper element. return RCUPtr(); } // The leaf is non-null and the keys match. We have our guy. return RCUPtr::copy(leaf); } - RCUPtr get(const K &key) const { + RCUPtr get(const KeyType &key) const { T const *ptr = const_cast(this)->get(key).release(); return RCUPtr::acquire(ptr); } #define SEEK_LEAF_LOOP() \ RadixElement e = eptr->load(); \ \ /* Walk down the tree until we find a leaf for our node. */ \ do { \ while (e.isNode()) { \ Node: \ auto nptr = e.getNode(); \ if (!nptr->isShared()) { \ eptr = nptr->get(level--, key); \ e = eptr->load(); \ continue; \ } \ \ auto copy = std::make_unique(*nptr); \ if (!eptr->compare_exchange_strong(e, RadixElement(copy.get()))) { \ /* We failed to insert our subtree, just try again. */ \ continue; \ } \ \ /* We have a subtree, resume normal operations from there. */ \ e.decrementRefCount(); \ eptr = copy->get(level--, key); \ e = eptr->load(); \ copy.release(); \ } \ } while (0) /** * Remove an element from the tree. * Returns the removed element, or nullptr if there isn't one. */ - RCUPtr remove(const K &key) { + RCUPtr remove(const KeyType &key) { uint32_t level = TOP_LEVEL; RCULock lock; std::atomic *eptr = &root; SEEK_LEAF_LOOP(); T *leaf = e.getLeaf(); if (leaf == nullptr || leaf->getId() != key) { // We failed to find the proper element. return RCUPtr(); } // We have the proper element, try to delete it. if (eptr->compare_exchange_strong(e, RadixElement())) { return RCUPtr::acquire(leaf); } // The element was replaced, either by a subtree or another element. if (e.isNode()) { goto Node; } // The element in the slot is not the one we are looking for. return RCUPtr(); } private: - bool insert(const K &key, RCUPtr value) { + bool insert(const KeyType &key, RCUPtr value) { uint32_t level = TOP_LEVEL; RCULock lock; std::atomic *eptr = &root; while (true) { SEEK_LEAF_LOOP(); // If the slot is empty, try to insert right there. if (e.getLeaf() == nullptr) { if (eptr->compare_exchange_strong(e, RadixElement(value.get()))) { value.release(); return true; } // CAS failed, we may have a node in there now. if (e.isNode()) { goto Node; } } // The element was already in the tree. - const K &leafKey = e.getLeaf()->getId(); + const KeyType &leafKey = e.getLeaf()->getId(); if (key == leafKey) { return false; } // There is an element there, but it isn't a subtree. We need to // convert it into a subtree and resume insertion into that subtree. auto newChild = std::make_unique(level, leafKey, e); if (eptr->compare_exchange_strong(e, RadixElement(newChild.get()))) { // We have a subtree, resume normal operations from there. newChild.release(); } else { // We failed to insert our subtree, clean it before it is freed. newChild->get(level, leafKey)->store(RadixElement()); } } } #undef SEEK_LEAF_LOOP struct RadixElement { private: union { RadixNode *node; T *leaf; uintptr_t raw; }; static const uintptr_t DISCRIMINANT = 0x01; bool getDiscriminant() const { return (raw & DISCRIMINANT) != 0; } public: explicit RadixElement() noexcept : raw(DISCRIMINANT) {} explicit RadixElement(RadixNode *nodeIn) noexcept : node(nodeIn) {} explicit RadixElement(T *leafIn) noexcept : leaf(leafIn) { raw |= DISCRIMINANT; } /** * RadixElement is designed to be a dumb wrapper. This allows any * container to release what is held by the RadixElement. */ void incrementRefCount() { if (isNode()) { RCUPtr::copy(getNode()).release(); } else { RCUPtr::copy(getLeaf()).release(); } } void decrementRefCount() { if (isNode()) { RadixNode *ptr = getNode(); RCUPtr::acquire(ptr); } else { T *ptr = getLeaf(); RCUPtr::acquire(ptr); } } /** * Node features. */ bool isNode() const { return !getDiscriminant(); } RadixNode *getNode() { assert(isNode()); return node; } const RadixNode *getNode() const { assert(isNode()); return node; } /** * Leaf features. */ bool isLeaf() const { return getDiscriminant(); } T *getLeaf() { assert(isLeaf()); return reinterpret_cast(raw & ~DISCRIMINANT); } const T *getLeaf() const { assert(isLeaf()); return const_cast(this)->getLeaf(); } }; struct RadixNode { IMPLEMENT_RCU_REFCOUNT(uint64_t); private: union { std::array, CHILD_PER_LEVEL> children; std::array non_atomic_children_DO_NOT_USE; }; public: - RadixNode(uint32_t level, const K &key, RadixElement e) + RadixNode(uint32_t level, const KeyType &key, RadixElement e) : non_atomic_children_DO_NOT_USE() { get(level, key)->store(e); } ~RadixNode() { for (RadixElement e : non_atomic_children_DO_NOT_USE) { e.decrementRefCount(); } } RadixNode(const RadixNode &rhs) : non_atomic_children_DO_NOT_USE() { for (size_t i = 0; i < CHILD_PER_LEVEL; i++) { auto e = rhs.children[i].load(); e.incrementRefCount(); non_atomic_children_DO_NOT_USE[i] = e; } } RadixNode &operator=(const RadixNode &) = delete; - std::atomic *get(uint32_t level, const K &key) { + std::atomic *get(uint32_t level, const KeyType &key) { return &children[(key >> (level * BITS)) & MASK]; } bool isShared() const { return refcount > 0; } }; // Make sure the alignment works for T and RadixElement. static_assert(alignof(T) > 1, "T's alignment must be 2 or more."); static_assert(alignof(RadixNode) > 1, "RadixNode alignment must be 2 or more."); }; #endif // BITCOIN_RADIX_H