lib/librte_eal/include/generic/rte_mcslock.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2019 Arm Limited
   3  */
   4
   5 #ifndef _RTE_MCSLOCK_H_
   6 #define _RTE_MCSLOCK_H_
   7
   8 /**
   9  * @file
  10  *
  11  * RTE MCS lock
  12  *
  13  * This file defines the main data structure and APIs for MCS queued lock.
  14  *
  15  * The MCS lock (proposed by John M. Mellor-Crummey and Michael L. Scott)
  16  * provides scalability by spinning on a CPU/thread local variable which
  17  * avoids expensive cache bouncings. It provides fairness by maintaining
  18  * a list of acquirers and passing the lock to each CPU/thread in the order
  19  * they acquired the lock.
  20  */
  21
  22 #include <rte_lcore.h>
  23 #include <rte_common.h>
  24 #include <rte_pause.h>
  25
  26 /**
  27  * The rte_mcslock_t type.
  28  */
  29 typedef struct rte_mcslock {
  30         struct rte_mcslock *next;
  31         int locked; /* 1 if the queue locked, 0 otherwise */
  32 } rte_mcslock_t;
  33
  34 /**
  35  * Take the MCS lock.
  36  *
  37  * @param msl
  38  *   A pointer to the pointer of a MCS lock.
  39  *   When the lock is initialized or declared, the msl pointer should be
  40  *   set to NULL.
  41  * @param me
  42  *   A pointer to a new node of MCS lock. Each CPU/thread acquiring the
  43  *   lock should use its 'own node'.
  44  */
  45 static inline void
  46 rte_mcslock_lock(rte_mcslock_t **msl, rte_mcslock_t *me)
  47 {
  48         rte_mcslock_t *prev;
  49
  50         /* Init me node */
  51         __atomic_store_n(&me->locked, 1, __ATOMIC_RELAXED);
  52         __atomic_store_n(&me->next, NULL, __ATOMIC_RELAXED);
  53
  54         /* If the queue is empty, the exchange operation is enough to acquire
  55          * the lock. Hence, the exchange operation requires acquire semantics.
  56          * The store to me->next above should complete before the node is
  57          * visible to other CPUs/threads. Hence, the exchange operation requires
  58          * release semantics as well.
  59          */
  60         prev = __atomic_exchange_n(msl, me, __ATOMIC_ACQ_REL);
  61         if (likely(prev == NULL)) {
  62                 /* Queue was empty, no further action required,
  63                  * proceed with lock taken.
  64                  */
  65                 return;
  66         }
  67         __atomic_store_n(&prev->next, me, __ATOMIC_RELAXED);
  68
  69         /* The while-load of me->locked should not move above the previous
  70          * store to prev->next. Otherwise it will cause a deadlock. Need a
  71          * store-load barrier.
  72          */
  73         __atomic_thread_fence(__ATOMIC_ACQ_REL);
  74         /* If the lock has already been acquired, it first atomically
  75          * places the node at the end of the queue and then proceeds
  76          * to spin on me->locked until the previous lock holder resets
  77          * the me->locked using mcslock_unlock().
  78          */
  79         while (__atomic_load_n(&me->locked, __ATOMIC_ACQUIRE))
  80                 rte_pause();
  81 }
  82
  83 /**
  84  * Release the MCS lock.
  85  *
  86  * @param msl
  87  *   A pointer to the pointer of a MCS lock.
  88  * @param me
  89  *   A pointer to the node of MCS lock passed in rte_mcslock_lock.
  90  */
  91 static inline void
  92 rte_mcslock_unlock(rte_mcslock_t **msl, rte_mcslock_t *me)
  93 {
  94         /* Check if there are more nodes in the queue. */
  95         if (likely(__atomic_load_n(&me->next, __ATOMIC_RELAXED) == NULL)) {
  96                 /* No, last member in the queue. */
  97                 rte_mcslock_t *save_me = __atomic_load_n(&me, __ATOMIC_RELAXED);
  98
  99                 /* Release the lock by setting it to NULL */
 100                 if (likely(__atomic_compare_exchange_n(msl, &save_me, NULL, 0,
 101                                 __ATOMIC_RELEASE, __ATOMIC_RELAXED)))
 102                         return;
 103
 104                 /* Speculative execution would be allowed to read in the
 105                  * while-loop first. This has the potential to cause a
 106                  * deadlock. Need a load barrier.
 107                  */
 108                 __atomic_thread_fence(__ATOMIC_ACQUIRE);
 109                 /* More nodes added to the queue by other CPUs.
 110                  * Wait until the next pointer is set.
 111                  */
 112                 while (__atomic_load_n(&me->next, __ATOMIC_RELAXED) == NULL)
 113                         rte_pause();
 114         }
 115
 116         /* Pass lock to next waiter. */
 117         __atomic_store_n(&me->next->locked, 0, __ATOMIC_RELEASE);
 118 }
 119
 120 /**
 121  * Try to take the lock.
 122  *
 123  * @param msl
 124  *   A pointer to the pointer of a MCS lock.
 125  * @param me
 126  *   A pointer to a new node of MCS lock.
 127  * @return
 128  *   1 if the lock is successfully taken; 0 otherwise.
 129  */
 130 static inline int
 131 rte_mcslock_trylock(rte_mcslock_t **msl, rte_mcslock_t *me)
 132 {
 133         /* Init me node */
 134         __atomic_store_n(&me->next, NULL, __ATOMIC_RELAXED);
 135
 136         /* Try to lock */
 137         rte_mcslock_t *expected = NULL;
 138
 139         /* The lock can be taken only when the queue is empty. Hence,
 140          * the compare-exchange operation requires acquire semantics.
 141          * The store to me->next above should complete before the node
 142          * is visible to other CPUs/threads. Hence, the compare-exchange
 143          * operation requires release semantics as well.
 144          */
 145         return __atomic_compare_exchange_n(msl, &expected, me, 0,
 146                         __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
 147 }
 148
 149 /**
 150  * Test if the lock is taken.
 151  *
 152  * @param msl
 153  *   A pointer to a MCS lock node.
 154  * @return
 155  *   1 if the lock is currently taken; 0 otherwise.
 156  */
 157 static inline int
 158 rte_mcslock_is_locked(rte_mcslock_t *msl)
 159 {
 160         return (__atomic_load_n(&msl, __ATOMIC_RELAXED) != NULL);
 161 }
 162
 163 #endif /* _RTE_MCSLOCK_H_ */