123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326 |
- /*
- * Copyright 2018-present 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 <folly/synchronization/Hazptr-fwd.h>
- #include <folly/synchronization/HazptrObj.h>
- #include <glog/logging.h>
- #include <atomic>
- #include <stack>
- ///
- /// Classes related to link counted objects and automatic retirement.
- ///
- namespace folly {
- /**
- * hazptr_root
- *
- * Link to counted objects. When destroyed unlinks the linked object
- * if any.
- *
- * Template parameter T must support a member function unlink(),
- * inherited from hazptr_obj_base_linked.
- *
- * Use example: Bucket heads in ConcurrentHashMap.
- */
- template <typename T, template <typename> class Atom>
- class hazptr_root {
- Atom<T*> link_;
- public:
- explicit hazptr_root(T* p = nullptr) noexcept : link_(p) {}
- ~hazptr_root() {
- auto p = link_.load(std::memory_order_relaxed);
- if (p) {
- p->unlink();
- }
- }
- const Atom<T*>& operator()() const noexcept {
- return link_;
- }
- Atom<T*>& operator()() noexcept {
- return link_;
- }
- }; // hazptr_root
- /**
- * hazptr_obj_linked
- *
- * Base class template for link counted objects.
- * Supports:
- * - Protecting descendants of protected objects.
- * - One-pass reclamation of long immutable chains of objects.
- * - Automatic reclamation of acyclic structures.
- *
- * Two inbound link counts are maintained per object:
- * - Link count: Represents the number of links from mutable paths.
- * - Ref count: Represents the number of links from immutable paths.
- * [Note: The ref count is one less than such links plus one if
- * the object hasn't gone through matching with hazard pointers
- * without finding a match. That is, a new object without inbound
- * links has a ref count of 0 and an about-to-be-reclaimed object
- * can be viewed to have a ref count of -1.]
- *
- * User code can increment the link and ref counts by calling
- * acquire_link and acquire_ref or their variants that require the
- * user to guarantee thread safety. There are no public functions to
- * decrement the counts explicitly. Counts are decremented implicitly
- * as described in hazptr_obj_base_linked.
- */
- template <template <typename> class Atom>
- class hazptr_obj_linked : public hazptr_obj<Atom> {
- using Count = uint32_t;
- static constexpr Count kRef = 1u;
- static constexpr Count kLink = 1u << 16;
- static constexpr Count kRefMask = kLink - 1u;
- static constexpr Count kLinkMask = ~kRefMask;
- Atom<Count> count_{0};
- public:
- void acquire_link() noexcept {
- count_inc(kLink);
- }
- void acquire_link_safe() noexcept {
- count_inc_safe(kLink);
- }
- void acquire_ref() noexcept {
- count_inc(kRef);
- }
- void acquire_ref_safe() noexcept {
- count_inc_safe(kRef);
- }
- private:
- template <typename, template <typename> class, typename>
- friend class hazptr_obj_base_linked;
- Count count() const noexcept {
- return count_.load(std::memory_order_acquire);
- }
- void count_set(Count val) noexcept {
- count_.store(val, std::memory_order_release);
- }
- void count_inc(Count add) noexcept {
- auto oldval = count_.fetch_add(add, std::memory_order_acq_rel);
- DCHECK_LT(oldval & kLinkMask, kLinkMask);
- DCHECK_LT(oldval & kRefMask, kRefMask);
- }
- void count_inc_safe(Count add) noexcept {
- auto oldval = count();
- count_set(oldval + add);
- DCHECK_LT(oldval & kLinkMask, kLinkMask);
- DCHECK_LT(oldval & kRefMask, kRefMask);
- }
- bool count_cas(Count& oldval, Count newval) noexcept {
- return count_.compare_exchange_weak(
- oldval, newval, std::memory_order_acq_rel, std::memory_order_acquire);
- }
- bool release_link() noexcept {
- auto sub = kLink;
- auto oldval = count();
- while (true) {
- DCHECK_GT(oldval & kLinkMask, 0u);
- if (oldval == kLink) {
- count_set(0u);
- return true;
- }
- if (count_cas(oldval, oldval - sub)) {
- return false;
- }
- }
- }
- bool release_ref() noexcept {
- auto sub = kRef;
- auto oldval = count();
- while (true) {
- if (oldval == 0u) {
- if (kIsDebug) {
- count_set(kRefMask);
- }
- return true;
- }
- DCHECK_GT(oldval & kRefMask, 0u);
- if (count_cas(oldval, oldval - sub)) {
- return false;
- }
- }
- }
- bool downgrade_link() noexcept {
- auto oldval = count();
- auto sub = kLink - kRef;
- while (true) {
- if (oldval == kLink) {
- count_set(kRef);
- return true;
- }
- if (count_cas(oldval, oldval - sub)) {
- return (oldval & kLinkMask) == kLink;
- }
- }
- }
- }; // hazptr_obj_linked
- /**
- * hazptr_obj_base_linked
- *
- * Base class template for link counted objects.
- *
- * Supports both *explicit* and *implicit* object retirement, depending
- * on whether object removal is *certain* or *uncertain*.
- *
- * A derived object's removal is certain when it is always possible
- * to reason based only on the local state of user code when an
- * object is removed, i.e., becomes unreachable from static
- * roots. Otherwise, removal is uncertain.
- *
- * For example, Removal in UnboundedQueue is certain, whereas removal
- * is ConcurrentHashMap is uncertain.
- *
- * If removal is certain, user code can call retire() explicitly.
- * Otherwise, user code should call unlink() whenever an inbound
- * link to the object is changed. Calls to unlink() automatically
- * retire the object when the link count is decremented to 0. [Note:
- * A ref count greater than 0 does not delay retiring an object.]
- *
- * Derived type T must define a member function template
- * template <typename S>
- * void push_links(bool m, S& s) {
- * if (m) { // m stands mutable links
- * // for each outbound mutable pointer p call
- * // s.push(p);
- * } else {
- * // for each outbound immutable pointer p call
- * // s.push(p);
- * }
- * }
- *
- * T may have both, either, or none of the two types of outbound
- * links. For example, UnboundedQueue Segment has an immutable
- * link, and ConcurrentHashMap NodeT has a mutable link.
- */
- template <typename T, template <typename> class Atom, typename D>
- class hazptr_obj_base_linked : public hazptr_obj_linked<Atom>,
- public hazptr_deleter<T, D> {
- using Stack = std::stack<hazptr_obj_base_linked<T, Atom, D>*>;
- public:
- void retire() {
- this->pre_retire_check(); // defined in hazptr_obj
- set_reclaim();
- this->push_to_retired(
- default_hazptr_domain<Atom>()); // defined in hazptr_obj
- }
- /* unlink: Retire object if last link is released. */
- void unlink() {
- if (this->release_link()) { // defined in hazptr_obj_linked
- downgrade_retire_immutable_descendants();
- retire();
- }
- }
- /* unlink_and_reclaim_unchecked: Reclaim object if the last link is
- released, without checking hazard pointers. To be called only
- when the object cannot possibly be protected by any hazard
- pointers. */
- void unlink_and_reclaim_unchecked() {
- if (this->release_link()) { // defined in hazptr_obj_linked
- DCHECK_EQ(this->count(), 0u);
- delete_self();
- }
- }
- private:
- void set_reclaim() noexcept {
- this->reclaim_ = [](hazptr_obj<Atom>* p, hazptr_obj_list<Atom>& l) {
- auto obj = static_cast<hazptr_obj_base_linked<T, Atom, D>*>(p);
- if (obj->release_ref()) { // defined in hazptr_obj_linked
- obj->release_delete_immutable_descendants();
- obj->release_retire_mutable_children(l);
- obj->delete_self();
- }
- };
- }
- void downgrade_retire_immutable_descendants() {
- Stack s;
- call_push_links(false, s);
- while (!s.empty()) {
- auto p = s.top();
- s.pop();
- if (p && p->downgrade_link()) {
- p->call_push_links(false, s);
- p->retire();
- }
- }
- }
- void release_delete_immutable_descendants() {
- Stack s;
- call_push_links(false, s);
- while (!s.empty()) {
- auto p = s.top();
- s.pop();
- if (p && p->release_ref()) {
- p->call_push_links(false, s);
- p->delete_self();
- }
- }
- }
- void release_retire_mutable_children(hazptr_obj_list<Atom>& l) {
- Stack s;
- call_push_links(true, s);
- while (!s.empty()) {
- auto p = s.top();
- s.pop();
- if (p->release_link()) {
- p->pre_retire_check(); // defined in hazptr_obj
- p->set_reclaim();
- l.push(p); // treated as if retired immediately
- }
- }
- }
- void call_push_links(bool m, Stack& s) {
- static_cast<T*>(this)->push_links(m, s); // to be defined in T
- }
- void delete_self() {
- this->delete_obj(static_cast<T*>(this)); // defined in hazptr_deleter
- }
- }; // hazptr_obj_base_linked
- } // namespace folly
|