Branch data Line data Source code
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 : : #include <rte_branch_prediction.h>
26 : : #include <rte_stdatomic.h>
27 : :
28 : : #ifdef __cplusplus
29 : : extern "C" {
30 : : #endif
31 : :
32 : : /**
33 : : * The rte_mcslock_t type.
34 : : */
35 : : typedef struct rte_mcslock {
36 : : RTE_ATOMIC(struct rte_mcslock *) next;
37 : : RTE_ATOMIC(int) locked; /* 1 if the queue locked, 0 otherwise */
38 : : } rte_mcslock_t;
39 : :
40 : : /**
41 : : * Take the MCS lock.
42 : : *
43 : : * @param msl
44 : : * A pointer to the pointer of a MCS lock.
45 : : * When the lock is initialized or declared, the msl pointer should be
46 : : * set to NULL.
47 : : * @param me
48 : : * A pointer to a new node of MCS lock. Each CPU/thread acquiring the
49 : : * lock should use its 'own node'.
50 : : */
51 : : static inline void
52 : 2993954 : rte_mcslock_lock(RTE_ATOMIC(rte_mcslock_t *) *msl, rte_mcslock_t *me)
53 : : {
54 : : rte_mcslock_t *prev;
55 : :
56 : : /* Init me node */
57 : 2993954 : rte_atomic_store_explicit(&me->locked, 1, rte_memory_order_relaxed);
58 : 2993954 : rte_atomic_store_explicit(&me->next, NULL, rte_memory_order_relaxed);
59 : :
60 : : /*
61 : : * A0/R0: Queue might be empty, perform the exchange (RMW) with both acquire and
62 : : * release semantics:
63 : : * A0: Acquire — synchronizes with both R0 and R2.
64 : : * Must synchronize with R0 to ensure that this thread observes predecessor's
65 : : * initialization of its lock object or risk them overwriting this thread's
66 : : * update to the next of the same object via store to prev->next.
67 : : *
68 : : * Must synchronize with R2 the releasing CAS in unlock(), this will ensure
69 : : * that all prior critical-section writes become visible to this thread.
70 : : *
71 : : * R0: Release — ensures the successor observes our initialization of me->next;
72 : : * without it, me->next could be overwritten to NULL after the successor
73 : : * sets its own address, causing deadlock. This release synchronizes with
74 : : * A0 above.
75 : : */
76 : 2993954 : prev = rte_atomic_exchange_explicit(msl, me, rte_memory_order_acq_rel);
77 [ + + ]: 2993954 : if (likely(prev == NULL)) {
78 : : /* Queue was empty, no further action required,
79 : : * proceed with lock taken.
80 : : */
81 : : return;
82 : : }
83 : :
84 : : /*
85 : : * R1: With the relaxed memory model of C/C++, it's essential that after
86 : : * we link ourselves by storing prev->next = me, the owner of prev must
87 : : * observe our prior initialization of me->locked. Otherwise it could
88 : : * clear me->locked before we set it to 1, which may deadlock.
89 : : * Perform a releasing store so the predecessor's acquire loads A2 and A3
90 : : * observes our initialization, establishing a happens-before from those
91 : : * writes.
92 : : */
93 : 1897638 : rte_atomic_store_explicit(&prev->next, me, rte_memory_order_release);
94 : :
95 : : /*
96 : : * A1: If the lock has already been acquired, it first atomically
97 : : * places the node at the end of the queue and then proceeds
98 : : * to spin on me->locked until the previous lock holder resets
99 : : * the me->locked in rte_mcslock_unlock().
100 : : * This load must synchronize with store-release R3 to ensure that
101 : : * all updates to critical section by previous lock holder is visible
102 : : * to this thread after acquiring the lock.
103 : : */
104 : : rte_wait_until_equal_32((uint32_t *)(uintptr_t)&me->locked, 0, rte_memory_order_acquire);
105 : : }
106 : :
107 : : /**
108 : : * Release the MCS lock.
109 : : *
110 : : * @param msl
111 : : * A pointer to the pointer of a MCS lock.
112 : : * @param me
113 : : * A pointer to the node of MCS lock passed in rte_mcslock_lock.
114 : : */
115 : : static inline void
116 : 3000005 : rte_mcslock_unlock(RTE_ATOMIC(rte_mcslock_t *) *msl, RTE_ATOMIC(rte_mcslock_t *) me)
117 : : {
118 : : /*
119 : : * A2: Check whether a successor is already queued.
120 : : * Load me->next with acquire semantics so it can synchronize with the
121 : : * successor’s release store R1. This guarantees that the successor’s
122 : : * initialization of its lock object (me) is completed before we observe
123 : : * it here, preventing a race between this thread’s store-release to
124 : : * me->next->locked and the successor’s store to me->locked.
125 : : */
126 [ + + ]: 3000005 : if (likely(rte_atomic_load_explicit(&me->next, rte_memory_order_acquire) == NULL)) {
127 : : /* No, last member in the queue. */
128 : : rte_mcslock_t *save_me = me;
129 : :
130 : : /*
131 : : * R2: Try to release the lock by swinging *msl from save_me to NULL.
132 : : * Use release semantics so all critical section writes become
133 : : * visible to the next lock acquirer.
134 : : */
135 [ + + ]: 2118919 : if (likely(rte_atomic_compare_exchange_strong_explicit(msl, &save_me, NULL,
136 : : rte_memory_order_release, rte_memory_order_relaxed)))
137 : : return;
138 : :
139 : : /*
140 : : * A3: Another thread was enqueued concurrently, so the CAS and the lock
141 : : * release failed. Wait until the successor sets our 'next' pointer.
142 : : * This load must synchronize with the successor’s release store (R1) to
143 : : * ensure that the successor’s initialization completes before we observe
144 : : * it here. This ordering prevents a race between this thread’s later
145 : : * store-release to me->next->locked and the successor’s store to me->locked.
146 : : */
147 : : RTE_ATOMIC(uintptr_t) *next;
148 : : next = (__rte_atomic uintptr_t *)&me->next;
149 [ + + ]: 1467906 : RTE_WAIT_UNTIL_MASKED(next, UINTPTR_MAX, !=, 0, rte_memory_order_acquire);
150 : : }
151 : :
152 : : /*
153 : : * R3: Pass the lock to the successor.
154 : : * Use a release store to synchronize with A1 when clearing me->next->locked
155 : : * so the successor observes our critical section writes after it sees locked
156 : : * become 0.
157 : : */
158 : 1897638 : rte_atomic_store_explicit(&me->next->locked, 0, rte_memory_order_release);
159 : : }
160 : :
161 : : /**
162 : : * Try to take the lock.
163 : : *
164 : : * @param msl
165 : : * A pointer to the pointer of a MCS lock.
166 : : * @param me
167 : : * A pointer to a new node of MCS lock.
168 : : * @return
169 : : * 1 if the lock is successfully taken; 0 otherwise.
170 : : */
171 : : static inline int
172 : : rte_mcslock_trylock(RTE_ATOMIC(rte_mcslock_t *) *msl, rte_mcslock_t *me)
173 : : {
174 : : /* Init me node */
175 : 2 : rte_atomic_store_explicit(&me->next, NULL, rte_memory_order_relaxed);
176 : :
177 : : /* Try to lock */
178 : : rte_mcslock_t *expected = NULL;
179 : :
180 : : /*
181 : : * A4/R4: The lock can be acquired only when the queue is empty.
182 : : * The compare-and-exchange operation must use acquire and release
183 : : * semantics for the same reasons described in the rte_mcslock_lock()
184 : : * function’s empty-queue case (see A0/R0 for details).
185 : : */
186 [ + - + - ]: 2 : return rte_atomic_compare_exchange_strong_explicit(msl, &expected, me,
187 : : rte_memory_order_acq_rel, rte_memory_order_relaxed);
188 : : }
189 : :
190 : : /**
191 : : * Test if the lock is taken.
192 : : *
193 : : * @param msl
194 : : * A pointer to a MCS lock node.
195 : : * @return
196 : : * 1 if the lock is currently taken; 0 otherwise.
197 : : */
198 : : static inline int
199 : : rte_mcslock_is_locked(RTE_ATOMIC(rte_mcslock_t *) msl)
200 : : {
201 [ - + ]: 1 : return (rte_atomic_load_explicit(&msl, rte_memory_order_relaxed) != NULL);
202 : : }
203 : :
204 : : #ifdef __cplusplus
205 : : }
206 : : #endif
207 : :
208 : : #endif /* _RTE_MCSLOCK_H_ */
|
