Home | History | Annotate | Line # | Download | only in lloadd 
      1 /*	$NetBSD: epoch.h,v 1.3 2025/09/05 21:16:24 christos Exp $	*/
      2 
      3 /* epoch.h - epoch based memory reclamation */
      4 /* $OpenLDAP$ */
      5 /* This work is part of OpenLDAP Software <http://www.openldap.org/>.
      6  *
      7  * Copyright 2018-2024 The OpenLDAP Foundation.
      8  * All rights reserved.
      9  *
     10  * Redistribution and use in source and binary forms, with or without
     11  * modification, are permitted only as authorized by the OpenLDAP
     12  * Public License.
     13  *
     14  * A copy of this license is available in the file LICENSE in the
     15  * top-level directory of the distribution or, alternatively, at
     16  * <http://www.OpenLDAP.org/license.html>.
     17  */
     18 
     19 #ifndef __LLOAD_EPOCH_H
     20 #define __LLOAD_EPOCH_H
     21 
     22 /** @file epoch.h
     23  *
     24  * Implementation of epoch based memory reclamation, in principle
     25  * similar to the algorithm presented in
     26  * https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
     27  */
     28 
     29 typedef uintptr_t epoch_t;
     30 
     31 /** @brief A callback function used to free object and associated data */
     32 typedef void (dispose_cb)( void *object );
     33 
     34 /** @brief Initiate global state */
     35 void epoch_init( void );
     36 
     37 /** @brief Finalise global state and free any objects still pending */
     38 void epoch_shutdown( void );
     39 
     40 /** @brief Register thread as active
     41  *
     42  * In order to safely access managed objects, a thread should call
     43  * this function or make sure no other thread is running (e.g. config
     44  * pause, late shutdown). After calling this, it is guaranteed that no
     45  * reachable objects will be freed before all threads have called
     46  * `epoch_leave( current_epoch + 1 )` so it is essential that there
     47  * is an upper limit to the amount of time between #epoch_join and
     48  * corresponding #epoch_leave or the number of unfreed objects might
     49  * grow without bounds.
     50  *
     51  * To simplify locking, memory is only freed when the current epoch
     52  * is advanced rather than on leaving it.
     53  *
     54  * Can be safely called multiple times by the same thread as long as
     55  * a matching #epoch_leave() call is made eventually.
     56  *
     57  * @return The observed epoch, to be passed to #epoch_leave()
     58  */
     59 epoch_t epoch_join( void );
     60 
     61 /** @brief Register thread as inactive
     62  *
     63  * A thread should call this after they are finished with work
     64  * performed since matching call to #epoch_join(). It is not safe
     65  * to keep a local reference to managed objects after this call
     66  * unless other precautions have been made to prevent it being
     67  * released.
     68  *
     69  * @param[in] epoch Epoch identifier returned by a previous call to
     70  * #epoch_join().
     71  */
     72 void epoch_leave( epoch_t epoch );
     73 
     74 /** @brief Return an unreachable object to be freed
     75  *
     76  * The object should already be unreachable at the point of call and
     77  * cb will be invoked when no other thread that could have seen it
     78  * is active any more. This happens when we have advanced by two
     79  * epochs.
     80  *
     81  * @param[in] ptr Object to be released/freed
     82  * @param[in] cb Callback to invoke when safe to do so
     83  */
     84 void epoch_append( void *ptr, dispose_cb *cb );
     85 
     86 /**
     87  * \defgroup Reference counting helpers
     88  */
     89 /**@{*/
     90 
     91 /** @brief Acquire a reference if possible
     92  *
     93  * Atomically, check reference count is non-zero and increment if so.
     94  * Returns old reference count.
     95  *
     96  * @param[in] refp Pointer to a reference counter
     97  * @return 0 if reference was already zero, non-zero if reference
     98  * count was successfully incremented
     99  */
    100 int acquire_ref( uintptr_t *refp );
    101 
    102 /** @brief Check reference count and try to decrement
    103  *
    104  * Atomically, decrement reference count if non-zero and register
    105  * object if decremented to zero. Returning previous reference count.
    106  *
    107  * @param[in] refp Pointer to a reference counter
    108  * @param[in] object The managed object
    109  * @param[in] cb Callback to invoke when safe to do so
    110  * @return 0 if reference was already zero, non-zero if reference
    111  * count was non-zero at the time of call
    112  */
    113 int try_release_ref(
    114         uintptr_t *refp,
    115         void *object,
    116         dispose_cb *unlink_cb,
    117         dispose_cb *destroy_cb );
    118 
    119 /** @brief Read reference count
    120  *
    121  * @param[in] object Pointer to the managed object
    122  * @param[in] ref_field Member where reference count is stored in
    123  * the object
    124  * @return Current value of reference counter
    125  */
    126 #define IS_ALIVE( object, ref_field ) \
    127     __atomic_load_n( &(object)->ref_field, __ATOMIC_ACQUIRE )
    128 
    129 /** @brief Release reference
    130  *
    131  * A cheaper alternative to #try_release_ref(), safe only when we know
    132  * reference count was already non-zero.
    133  *
    134  * @param[in] object The managed object
    135  * @param[in] ref_field Member where reference count is stored in
    136  * the object
    137  * @param[in] cb Callback to invoke when safe to do so
    138  */
    139 #define RELEASE_REF( object, ref_field, cb ) \
    140     do { \
    141         assert( IS_ALIVE( (object), ref_field ) ); \
    142         if ( !__atomic_sub_fetch( \
    143                      &(object)->ref_field, 1, __ATOMIC_ACQ_REL ) ) { \
    144             epoch_append( object, (dispose_cb *)cb ); \
    145         } \
    146     } while (0)
    147 
    148 /**@}*/
    149 
    150 #endif /* __LLOAD_EPOCH_H */
    151