FreeBSD/Linux Kernel Cross Reference
sys/sys/smr.h

     /*-
      * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
      *
      * Copyright (c) 2019, 2020 Jeffrey Roberson <jeff@FreeBSD.org>
      *
      * Redistribution and use in source and binary forms, with or without
      * modification, are permitted provided that the following conditions
      * are met:
      * 1. Redistributions of source code must retain the above copyright
     *    notice unmodified, this list of conditions, and the following
     *    disclaimer.
     * 2. Redistributions in binary form must reproduce the above copyright
     *    notice, this list of conditions and the following disclaimer in the
     *    documentation and/or other materials provided with the distribution.
     *
     * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     *
     * $FreeBSD$
     *
     */
    
    #ifndef _SYS_SMR_H_
    #define _SYS_SMR_H_
    
    #include <sys/_smr.h>
    
    /*
     * Safe memory reclamation.  See subr_smr.c for a description of the
     * algorithm, and smr_types.h for macros to define and access SMR-protected
     * data structures.
     *
     * Readers synchronize with smr_enter()/exit() and writers may either
     * free directly to a SMR UMA zone or use smr_synchronize or wait.
     */
    
    /*
     * Modular arithmetic for comparing sequence numbers that have
     * potentially wrapped.  Copied from tcp_seq.h.
     */
    #define SMR_SEQ_LT(a, b)        ((smr_delta_t)((a)-(b)) < 0)
    #define SMR_SEQ_LEQ(a, b)       ((smr_delta_t)((a)-(b)) <= 0)
    #define SMR_SEQ_GT(a, b)        ((smr_delta_t)((a)-(b)) > 0)
    #define SMR_SEQ_GEQ(a, b)       ((smr_delta_t)((a)-(b)) >= 0)
    #define SMR_SEQ_DELTA(a, b)     ((smr_delta_t)((a)-(b)))
    #define SMR_SEQ_MIN(a, b)       (SMR_SEQ_LT((a), (b)) ? (a) : (b))
    #define SMR_SEQ_MAX(a, b)       (SMR_SEQ_GT((a), (b)) ? (a) : (b))
    
    #define SMR_SEQ_INVALID         0
    
    /* Shared SMR state. */
    union s_wr {
            struct {
                    smr_seq_t       seq;    /* Current write sequence #. */
                    int             ticks;  /* tick of last update (LAZY) */
            };
            uint64_t        _pair;
    };
    struct smr_shared {
            const char      *s_name;        /* Name for debugging/reporting. */
            union s_wr      s_wr;           /* Write sequence */
            smr_seq_t       s_rd_seq;       /* Minimum observed read sequence. */
    };
    typedef struct smr_shared *smr_shared_t;
    
    /* Per-cpu SMR state. */
    struct smr {
            smr_seq_t       c_seq;          /* Current observed sequence. */
            smr_shared_t    c_shared;       /* Shared SMR state. */
            int             c_deferred;     /* Deferred advance counter. */
            int             c_limit;        /* Deferred advance limit. */
            int             c_flags;        /* SMR Configuration */
    };
    
    #define SMR_LAZY        0x0001          /* Higher latency write, fast read. */
    #define SMR_DEFERRED    0x0002          /* Aggregate updates to wr_seq. */
    
    /*
     * Return the current write sequence number.  This is not the same as the
     * current goal which may be in the future.
     */
    static inline smr_seq_t
    smr_shared_current(smr_shared_t s)
    {
    
            return (atomic_load_int(&s->s_wr.seq));
    }
    
    static inline smr_seq_t
    smr_current(smr_t smr)
    {
   
           return (smr_shared_current(zpcpu_get(smr)->c_shared));
   }
   
   /*
    * Enter a read section.
    */
   static inline void
   smr_enter(smr_t smr)
   {
   
           critical_enter();
           smr = zpcpu_get(smr);
           KASSERT((smr->c_flags & SMR_LAZY) == 0,
               ("smr_enter(%s) lazy smr.", smr->c_shared->s_name));
           KASSERT(smr->c_seq == 0,
               ("smr_enter(%s) does not support recursion.",
               smr->c_shared->s_name));
   
           /*
            * Store the current observed write sequence number in our
            * per-cpu state so that it can be queried via smr_poll().
            * Frees that are newer than this stored value will be
            * deferred until we call smr_exit().
            *
            * Subsequent loads must not be re-ordered with the store.  On
            * x86 platforms, any locked instruction will provide this
            * guarantee, so as an optimization we use a single operation to
            * both store the cached write sequence number and provide the
            * requisite barrier, taking advantage of the fact that
            * SMR_SEQ_INVALID is zero.
            *
            * It is possible that a long delay between loading the wr_seq
            * and storing the c_seq could create a situation where the
            * rd_seq advances beyond our stored c_seq.  In this situation
            * only the observed wr_seq is stale, the fence still orders
            * the load.  See smr_poll() for details on how this condition
            * is detected and handled there.
            */
   #if defined(__amd64__) || defined(__i386__)
           atomic_add_acq_int(&smr->c_seq, smr_shared_current(smr->c_shared));
   #else
           atomic_store_int(&smr->c_seq, smr_shared_current(smr->c_shared));
           atomic_thread_fence_seq_cst();
   #endif
   }
   
   /*
    * Exit a read section.
    */
   static inline void
   smr_exit(smr_t smr)
   {
   
           smr = zpcpu_get(smr);
           CRITICAL_ASSERT(curthread);
           KASSERT((smr->c_flags & SMR_LAZY) == 0,
               ("smr_exit(%s) lazy smr.", smr->c_shared->s_name));
           KASSERT(smr->c_seq != SMR_SEQ_INVALID,
               ("smr_exit(%s) not in a smr section.", smr->c_shared->s_name));
   
           /*
            * Clear the recorded sequence number.  This allows poll() to
            * detect CPUs not in read sections.
            *
            * Use release semantics to retire any stores before the sequence
            * number is cleared.
            */
           atomic_store_rel_int(&smr->c_seq, SMR_SEQ_INVALID);
           critical_exit();
   }
   
   /*
    * Enter a lazy smr section.  This is used for read-mostly state that
    * can tolerate a high free latency.
    */
   static inline void
   smr_lazy_enter(smr_t smr)
   {
   
           critical_enter();
           smr = zpcpu_get(smr);
           KASSERT((smr->c_flags & SMR_LAZY) != 0,
               ("smr_lazy_enter(%s) non-lazy smr.", smr->c_shared->s_name));
           KASSERT(smr->c_seq == 0,
               ("smr_lazy_enter(%s) does not support recursion.",
               smr->c_shared->s_name));
   
           /*
            * This needs no serialization.  If an interrupt occurs before we
            * assign sr_seq to c_seq any speculative loads will be discarded.
            * If we assign a stale wr_seq value due to interrupt we use the
            * same algorithm that renders smr_enter() safe.
            */
           atomic_store_int(&smr->c_seq, smr_shared_current(smr->c_shared));
   }
   
   /*
    * Exit a lazy smr section.  This is used for read-mostly state that
    * can tolerate a high free latency.
    */
   static inline void
   smr_lazy_exit(smr_t smr)
   {
   
           smr = zpcpu_get(smr);
           CRITICAL_ASSERT(curthread);
           KASSERT((smr->c_flags & SMR_LAZY) != 0,
               ("smr_lazy_enter(%s) non-lazy smr.", smr->c_shared->s_name));
           KASSERT(smr->c_seq != SMR_SEQ_INVALID,
               ("smr_lazy_exit(%s) not in a smr section.", smr->c_shared->s_name));
   
           /*
            * All loads/stores must be retired before the sequence becomes
            * visible.  The fence compiles away on amd64.  Another
            * alternative would be to omit the fence but store the exit
            * time and wait 1 tick longer.
            */
           atomic_thread_fence_rel();
           atomic_store_int(&smr->c_seq, SMR_SEQ_INVALID);
           critical_exit();
   }
   
   /*
    * Advances the write sequence number.  Returns the sequence number
    * required to ensure that all modifications are visible to readers.
    */
   smr_seq_t smr_advance(smr_t smr);
   
   /*
    * Returns true if a goal sequence has been reached.  If
    * wait is true this will busy loop until success.
    */
   bool smr_poll(smr_t smr, smr_seq_t goal, bool wait);
   
   /* Create a new SMR context. */
   smr_t smr_create(const char *name, int limit, int flags);
   
   /* Destroy the context. */
   void smr_destroy(smr_t smr);
   
   /*
    * Blocking wait for all readers to observe 'goal'.
    */
   static inline bool
   smr_wait(smr_t smr, smr_seq_t goal)
   {
   
           return (smr_poll(smr, goal, true));
   }
   
   /*
    * Synchronize advances the write sequence and returns when all
    * readers have observed it. 
    *
    * If your application can cache a sequence number returned from
    * smr_advance() and poll or wait at a later time there will
    * be less chance of busy looping while waiting for readers.
    */
   static inline void
   smr_synchronize(smr_t smr)
   {
   
           smr_wait(smr, smr_advance(smr));
   }
   
   /* Only at startup. */
   void smr_init(void);
   
   #endif  /* _SYS_SMR_H_ */

Cache object: 276a28978a0d25188eb46353e3ee21f3