folly/folly/synchronization/HazptrDomain.h

/*
 * 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 <folly/Executor.h>
#include <folly/Memory.h>
#include <folly/Portability.h>
#include <folly/container/F14Set.h>
#include <folly/synchronization/AsymmetricThreadFence.h>
#include <folly/synchronization/Hazptr-fwd.h>
#include <folly/synchronization/HazptrObj.h>
#include <folly/synchronization/HazptrRec.h>
#include <folly/synchronization/HazptrThrLocal.h>

///
/// Classes related to hazard pointer domains.
///

namespace folly {

class Executor;

namespace detail {

/** Threshold for the number of retired objects to trigger
    asynchronous reclamation. */
constexpr int hazptr_domain_rcount_threshold() { … }

folly::Executor::KeepAlive<> hazptr_get_default_executor();

} // namespace detail

/**
 *  hazptr_domain
 *
 *  A domain manages a set of hazard pointers and a set of retired objects.
 *
 *  Most user code need not specify any domains.
 *
 *  Notes on destruction order and tagged objects:
 *  - Tagged objects support reclamation order guarantees (i.e.,
 *    synchronous reclamation). A call to cleanup_cohort_tag(tag)
 *    guarantees that all objects with the specified tag are reclaimed
 *    before the function returns.
 *  - There are two types of reclamation operations to consider:
 *   - Asynchronous reclamation: It is triggered by meeting some
 *     threshold for the number of retired objects or the time since
 *     the last asynchronous reclamation. Reclaimed objects may have
 *     different tags or no tags. Hazard pointers are checked and only
 *     unprotected objects are reclaimed. This type is expected to be
 *     expensive but infrequent and the cost is amortized over a large
 *     number of reclaimed objects. This type is needed to guarantee
 *     an upper bound on unreclaimed reclaimable objects.
 *   - Synchronous reclamation: It is invoked by calling
 *     cleanup_cohort_tag for a specific tag. All objects with the
 *     specified tag must be reclaimed unconditionally before
 *     returning from such a function call. Hazard pointers are not
 *     checked. This type of reclamation operation is expected to be
 *     inexpensive and may be invoked more frequently than
 *     asynchronous reclamation.
 *  - Tagged retired objects are kept in a sharded list in the domain
 *    structure.
 *  - Both asynchronous and synchronous reclamation pop all the
 *    objects in the tagged list(s) and sort them into two sets of
 *    reclaimable and unreclaimable objects. The objects in the
 *    reclaimable set are reclaimed and the objects in the
 *    unreclaimable set are pushed back in the tagged list(s).
 *  - The tagged list(s) are locked between popping all objects and
 *    pushing back unreclaimable objects, in order to guarantee that
 *    synchronous reclamation operations do not miss any objects.
 *  - Asynchronous reclamation can release the lock(s) on the tagged
 *    list(s) before reclaiming reclaimable objects, because it pushes
 *    reclaimable tagged objects in their respective cohorts, which
 *    would handle concurrent synchronous reclamation of such objects
 *    properly.
 *  - Synchronous reclamation operations can release the lock on the
 *    tagged list shard before reclaiming objects because the sets of
 *    reclaimable objects by different synchronous reclamation
 *    operations are disjoint.
 */
template <template <typename> class Atom>
class hazptr_domain { … }; // hazptr_domain

/**
 *  Free functions related to hazptr domains
 */

/** default_hazptr_domain: Returns reference to the default domain */

template <template <typename> class Atom>
struct hazptr_default_domain_helper { … };

template <>
struct hazptr_default_domain_helper<std::atomic> { … };

template <template <typename> class Atom>
FOLLY_ALWAYS_INLINE hazptr_domain<Atom>& default_hazptr_domain() { … }

template <template <typename> class Atom>
FOLLY_ALWAYS_INLINE hazard_pointer_domain<Atom>&
hazard_pointer_default_domain() { … }

/** hazptr_domain_push_retired: push a list of retired objects into a domain */
template <template <typename> class Atom>
void hazptr_domain_push_retired(
    hazptr_obj_list<Atom>& l, hazptr_domain<Atom>& domain) noexcept { … }

/** hazptr_retire */
template <template <typename> class Atom, typename T, typename D>
FOLLY_ALWAYS_INLINE void hazptr_retire(T* obj, D reclaim) { … }

/** hazptr_cleanup: Reclaims all reclaimable objects retired to the domain */
template <template <typename> class Atom>
void hazptr_cleanup(hazptr_domain<Atom>& domain) noexcept { … }

template <template <typename> class Atom>
void hazard_pointer_clean_up(hazard_pointer_domain<Atom>& domain) noexcept { … }

} // namespace folly