1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2019 Arm Limited
5 #ifndef _RTE_MCSLOCK_H_
6 #define _RTE_MCSLOCK_H_
13 * This file defines the main data structure and APIs for MCS queued lock.
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.
26 #include <rte_lcore.h>
27 #include <rte_common.h>
28 #include <rte_pause.h>
29 #include <rte_branch_prediction.h>
32 * The rte_mcslock_t type.
34 typedef struct rte_mcslock {
35 struct rte_mcslock *next;
36 int locked; /* 1 if the queue locked, 0 otherwise */
43 * A pointer to the pointer of a MCS lock.
44 * When the lock is initialized or declared, the msl pointer should be
47 * A pointer to a new node of MCS lock. Each CPU/thread acquiring the
48 * lock should use its 'own node'.
51 rte_mcslock_lock(rte_mcslock_t **msl, rte_mcslock_t *me)
56 __atomic_store_n(&me->locked, 1, __ATOMIC_RELAXED);
57 __atomic_store_n(&me->next, NULL, __ATOMIC_RELAXED);
59 /* If the queue is empty, the exchange operation is enough to acquire
60 * the lock. Hence, the exchange operation requires acquire semantics.
61 * The store to me->next above should complete before the node is
62 * visible to other CPUs/threads. Hence, the exchange operation requires
63 * release semantics as well.
65 prev = __atomic_exchange_n(msl, me, __ATOMIC_ACQ_REL);
66 if (likely(prev == NULL)) {
67 /* Queue was empty, no further action required,
68 * proceed with lock taken.
72 /* The store to me->next above should also complete before the node is
73 * visible to predecessor thread releasing the lock. Hence, the store
74 * prev->next also requires release semantics. Note that, for example,
75 * on ARM, the release semantics in the exchange operation is not
76 * strong as a release fence and is not sufficient to enforce the
79 __atomic_store_n(&prev->next, me, __ATOMIC_RELEASE);
81 /* The while-load of me->locked should not move above the previous
82 * store to prev->next. Otherwise it will cause a deadlock. Need a
85 __atomic_thread_fence(__ATOMIC_ACQ_REL);
86 /* If the lock has already been acquired, it first atomically
87 * places the node at the end of the queue and then proceeds
88 * to spin on me->locked until the previous lock holder resets
89 * the me->locked using mcslock_unlock().
91 rte_wait_until_equal_32((uint32_t *)&me->locked, 0, __ATOMIC_ACQUIRE);
95 * Release the MCS lock.
98 * A pointer to the pointer of a MCS lock.
100 * A pointer to the node of MCS lock passed in rte_mcslock_lock.
103 rte_mcslock_unlock(rte_mcslock_t **msl, rte_mcslock_t *me)
105 /* Check if there are more nodes in the queue. */
106 if (likely(__atomic_load_n(&me->next, __ATOMIC_RELAXED) == NULL)) {
107 /* No, last member in the queue. */
108 rte_mcslock_t *save_me = __atomic_load_n(&me, __ATOMIC_RELAXED);
110 /* Release the lock by setting it to NULL */
111 if (likely(__atomic_compare_exchange_n(msl, &save_me, NULL, 0,
112 __ATOMIC_RELEASE, __ATOMIC_RELAXED)))
115 /* Speculative execution would be allowed to read in the
116 * while-loop first. This has the potential to cause a
117 * deadlock. Need a load barrier.
119 __atomic_thread_fence(__ATOMIC_ACQUIRE);
120 /* More nodes added to the queue by other CPUs.
121 * Wait until the next pointer is set.
124 next = (uintptr_t *)&me->next;
125 RTE_WAIT_UNTIL_MASKED(next, UINTPTR_MAX, !=, 0,
129 /* Pass lock to next waiter. */
130 __atomic_store_n(&me->next->locked, 0, __ATOMIC_RELEASE);
134 * Try to take the lock.
137 * A pointer to the pointer of a MCS lock.
139 * A pointer to a new node of MCS lock.
141 * 1 if the lock is successfully taken; 0 otherwise.
144 rte_mcslock_trylock(rte_mcslock_t **msl, rte_mcslock_t *me)
147 __atomic_store_n(&me->next, NULL, __ATOMIC_RELAXED);
150 rte_mcslock_t *expected = NULL;
152 /* The lock can be taken only when the queue is empty. Hence,
153 * the compare-exchange operation requires acquire semantics.
154 * The store to me->next above should complete before the node
155 * is visible to other CPUs/threads. Hence, the compare-exchange
156 * operation requires release semantics as well.
158 return __atomic_compare_exchange_n(msl, &expected, me, 0,
159 __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
163 * Test if the lock is taken.
166 * A pointer to a MCS lock node.
168 * 1 if the lock is currently taken; 0 otherwise.
171 rte_mcslock_is_locked(rte_mcslock_t *msl)
173 return (__atomic_load_n(&msl, __ATOMIC_RELAXED) != NULL);
180 #endif /* _RTE_MCSLOCK_H_ */