/* * Copyright (c) Meta Platforms, Inc. and affiliates. * * 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 <atomic> #include <stack> #include <glog/logging.h> #include <folly/synchronization/Hazptr-fwd.h> #include <folly/synchronization/HazptrObj.h> /// /// 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 { … }; // 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> { … }; // 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> { … }; // hazptr_obj_base_linked } // namespace folly
Codebase Browser
folly