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 : 2995008 : 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 : 2995008 : rte_atomic_store_explicit(&me->locked, 1, rte_memory_order_relaxed);
58 : 2995008 : rte_atomic_store_explicit(&me->next, NULL, rte_memory_order_relaxed);
59 : :
60 : : /* If the queue is empty, the exchange operation is enough to acquire
61 : : * the lock. Hence, the exchange operation requires acquire semantics.
62 : : * The store to me->next above should complete before the node is
63 : : * visible to other CPUs/threads. Hence, the exchange operation requires
64 : : * release semantics as well.
65 : : */
66 : 2995008 : prev = rte_atomic_exchange_explicit(msl, me, rte_memory_order_acq_rel);
67 [ + + ]: 2995008 : if (likely(prev == NULL)) {
68 : : /* Queue was empty, no further action required,
69 : : * proceed with lock taken.
70 : : */
71 : : return;
72 : : }
73 : : /* The store to me->next above should also complete before the node is
74 : : * visible to predecessor thread releasing the lock. Hence, the store
75 : : * prev->next also requires release semantics. Note that, for example,
76 : : * on ARM, the release semantics in the exchange operation is not
77 : : * strong as a release fence and is not sufficient to enforce the
78 : : * desired order here.
79 : : */
80 : 1624550 : rte_atomic_store_explicit(&prev->next, me, rte_memory_order_release);
81 : :
82 : : /* The while-load of me->locked should not move above the previous
83 : : * store to prev->next. Otherwise it will cause a deadlock. Need a
84 : : * store-load barrier.
85 : : */
86 : : rte_atomic_thread_fence(rte_memory_order_acq_rel);
87 : : /* If the lock has already been acquired, it first atomically
88 : : * places the node at the end of the queue and then proceeds
89 : : * to spin on me->locked until the previous lock holder resets
90 : : * the me->locked using mcslock_unlock().
91 : : */
92 : : rte_wait_until_equal_32((uint32_t *)(uintptr_t)&me->locked, 0, rte_memory_order_acquire);
93 : : }
94 : :
95 : : /**
96 : : * Release the MCS lock.
97 : : *
98 : : * @param msl
99 : : * A pointer to the pointer of a MCS lock.
100 : : * @param me
101 : : * A pointer to the node of MCS lock passed in rte_mcslock_lock.
102 : : */
103 : : static inline void
104 : 3000005 : rte_mcslock_unlock(RTE_ATOMIC(rte_mcslock_t *) *msl, RTE_ATOMIC(rte_mcslock_t *) me)
105 : : {
106 : : /* Check if there are more nodes in the queue. */
107 [ + + ]: 3000005 : if (likely(rte_atomic_load_explicit(&me->next, rte_memory_order_relaxed) == NULL)) {
108 : : /* No, last member in the queue. */
109 : 2305730 : rte_mcslock_t *save_me = rte_atomic_load_explicit(&me, rte_memory_order_relaxed);
110 : :
111 : : /* Release the lock by setting it to NULL */
112 [ + + ]: 2305730 : if (likely(rte_atomic_compare_exchange_strong_explicit(msl, &save_me, NULL,
113 : : rte_memory_order_release, rte_memory_order_relaxed)))
114 : : return;
115 : :
116 : : /* Speculative execution would be allowed to read in the
117 : : * while-loop first. This has the potential to cause a
118 : : * deadlock. Need a load barrier.
119 : : */
120 : : rte_atomic_thread_fence(rte_memory_order_acquire);
121 : : /* More nodes added to the queue by other CPUs.
122 : : * Wait until the next pointer is set.
123 : : */
124 : : RTE_ATOMIC(uintptr_t) *next;
125 : 930275 : next = (__rte_atomic uintptr_t *)&me->next;
126 [ + + ]: 1248541 : RTE_WAIT_UNTIL_MASKED(next, UINTPTR_MAX, !=, 0, rte_memory_order_relaxed);
127 : : }
128 : :
129 : : /* Pass lock to next waiter. */
130 : 1624550 : rte_atomic_store_explicit(&me->next->locked, 0, rte_memory_order_release);
131 : : }
132 : :
133 : : /**
134 : : * Try to take the lock.
135 : : *
136 : : * @param msl
137 : : * A pointer to the pointer of a MCS lock.
138 : : * @param me
139 : : * A pointer to a new node of MCS lock.
140 : : * @return
141 : : * 1 if the lock is successfully taken; 0 otherwise.
142 : : */
143 : : static inline int
144 : : rte_mcslock_trylock(RTE_ATOMIC(rte_mcslock_t *) *msl, rte_mcslock_t *me)
145 : : {
146 : : /* Init me node */
147 : 2 : rte_atomic_store_explicit(&me->next, NULL, rte_memory_order_relaxed);
148 : :
149 : : /* Try to lock */
150 : : rte_mcslock_t *expected = NULL;
151 : :
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.
157 : : */
158 [ + - + - ]: 2 : return rte_atomic_compare_exchange_strong_explicit(msl, &expected, me,
159 : : rte_memory_order_acq_rel, rte_memory_order_relaxed);
160 : : }
161 : :
162 : : /**
163 : : * Test if the lock is taken.
164 : : *
165 : : * @param msl
166 : : * A pointer to a MCS lock node.
167 : : * @return
168 : : * 1 if the lock is currently taken; 0 otherwise.
169 : : */
170 : : static inline int
171 : : rte_mcslock_is_locked(RTE_ATOMIC(rte_mcslock_t *) msl)
172 : : {
173 [ - + ]: 1 : return (rte_atomic_load_explicit(&msl, rte_memory_order_relaxed) != NULL);
174 : : }
175 : :
176 : : #ifdef __cplusplus
177 : : }
178 : : #endif
179 : :
180 : : #endif /* _RTE_MCSLOCK_H_ */
|
