Blame view
kernel/locking/osq_lock.c
5.6 KB
b24413180 License cleanup: ... |
1 |
// SPDX-License-Identifier: GPL-2.0 |
fb0527bd5 locking/mutexes: ... |
2 |
#include <linux/percpu.h> |
fb0527bd5 locking/mutexes: ... |
3 |
#include <linux/sched.h> |
d84b6728c locking/mcs: Bett... |
4 |
#include <linux/osq_lock.h> |
fb0527bd5 locking/mutexes: ... |
5 6 7 8 9 10 11 12 13 |
/* * An MCS like lock especially tailored for optimistic spinning for sleeping * lock implementations (mutex, rwsem, etc). * * Using a single mcs node per CPU is safe because sleeping locks should not be * called from interrupt context and we have preemption disabled while * spinning. */ |
046a619d8 locking/spinlocks... |
14 |
static DEFINE_PER_CPU_SHARED_ALIGNED(struct optimistic_spin_node, osq_node); |
fb0527bd5 locking/mutexes: ... |
15 16 |
/* |
90631822c locking/spinlocks... |
17 18 19 20 21 22 23 |
* We use the value 0 to represent "no CPU", thus the encoded value * will be the CPU number incremented by 1. */ static inline int encode_cpu(int cpu_nr) { return cpu_nr + 1; } |
5aff60a19 locking/osq: Brea... |
24 25 26 27 |
static inline int node_cpu(struct optimistic_spin_node *node) { return node->cpu - 1; } |
90631822c locking/spinlocks... |
28 29 30 31 32 33 34 35 |
static inline struct optimistic_spin_node *decode_cpu(int encoded_cpu_val) { int cpu_nr = encoded_cpu_val - 1; return per_cpu_ptr(&osq_node, cpu_nr); } /* |
fb0527bd5 locking/mutexes: ... |
36 37 38 |
* Get a stable @node->next pointer, either for unlock() or unqueue() purposes. * Can return NULL in case we were the last queued and we updated @lock instead. */ |
046a619d8 locking/spinlocks... |
39 |
static inline struct optimistic_spin_node * |
90631822c locking/spinlocks... |
40 |
osq_wait_next(struct optimistic_spin_queue *lock, |
046a619d8 locking/spinlocks... |
41 42 |
struct optimistic_spin_node *node, struct optimistic_spin_node *prev) |
fb0527bd5 locking/mutexes: ... |
43 |
{ |
046a619d8 locking/spinlocks... |
44 |
struct optimistic_spin_node *next = NULL; |
90631822c locking/spinlocks... |
45 46 47 48 49 50 51 52 53 |
int curr = encode_cpu(smp_processor_id()); int old; /* * If there is a prev node in queue, then the 'old' value will be * the prev node's CPU #, else it's set to OSQ_UNLOCKED_VAL since if * we're currently last in queue, then the queue will then become empty. */ old = prev ? prev->cpu : OSQ_UNLOCKED_VAL; |
fb0527bd5 locking/mutexes: ... |
54 55 |
for (;;) { |
90631822c locking/spinlocks... |
56 |
if (atomic_read(&lock->tail) == curr && |
c55a6ffa6 locking/osq: Rela... |
57 |
atomic_cmpxchg_acquire(&lock->tail, curr, old) == curr) { |
fb0527bd5 locking/mutexes: ... |
58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
/* * We were the last queued, we moved @lock back. @prev * will now observe @lock and will complete its * unlock()/unqueue(). */ break; } /* * We must xchg() the @node->next value, because if we were to * leave it in, a concurrent unlock()/unqueue() from * @node->next might complete Step-A and think its @prev is * still valid. * * If the concurrent unlock()/unqueue() wins the race, we'll * wait for either @lock to point to us, through its Step-B, or * wait for a new @node->next from its Step-C. */ if (node->next) { next = xchg(&node->next, NULL); if (next) break; } |
f2f09a4ce locking/core: Rem... |
81 |
cpu_relax(); |
fb0527bd5 locking/mutexes: ... |
82 83 84 85 |
} return next; } |
90631822c locking/spinlocks... |
86 |
bool osq_lock(struct optimistic_spin_queue *lock) |
fb0527bd5 locking/mutexes: ... |
87 |
{ |
046a619d8 locking/spinlocks... |
88 89 |
struct optimistic_spin_node *node = this_cpu_ptr(&osq_node); struct optimistic_spin_node *prev, *next; |
90631822c locking/spinlocks... |
90 91 |
int curr = encode_cpu(smp_processor_id()); int old; |
fb0527bd5 locking/mutexes: ... |
92 93 94 |
node->locked = 0; node->next = NULL; |
90631822c locking/spinlocks... |
95 |
node->cpu = curr; |
fb0527bd5 locking/mutexes: ... |
96 |
|
c55a6ffa6 locking/osq: Rela... |
97 |
/* |
b4b29f948 locking/osq: Fix ... |
98 99 100 101 |
* We need both ACQUIRE (pairs with corresponding RELEASE in * unlock() uncontended, or fastpath) and RELEASE (to publish * the node fields we just initialised) semantics when updating * the lock tail. |
c55a6ffa6 locking/osq: Rela... |
102 |
*/ |
b4b29f948 locking/osq: Fix ... |
103 |
old = atomic_xchg(&lock->tail, curr); |
90631822c locking/spinlocks... |
104 |
if (old == OSQ_UNLOCKED_VAL) |
fb0527bd5 locking/mutexes: ... |
105 |
return true; |
90631822c locking/spinlocks... |
106 107 |
prev = decode_cpu(old); node->prev = prev; |
50972fe78 locking/osq_lock:... |
108 109 110 111 112 113 114 115 116 117 118 119 |
/* * osq_lock() unqueue * * node->prev = prev osq_wait_next() * WMB MB * prev->next = node next->prev = prev // unqueue-C * * Here 'node->prev' and 'next->prev' are the same variable and we need * to ensure these stores happen in-order to avoid corrupting the list. */ smp_wmb(); |
4d3199e4c locking: Remove A... |
120 |
WRITE_ONCE(prev->next, node); |
fb0527bd5 locking/mutexes: ... |
121 122 123 124 125 126 127 128 129 |
/* * Normally @prev is untouchable after the above store; because at that * moment unlock can proceed and wipe the node element from stack. * * However, since our nodes are static per-cpu storage, we're * guaranteed their existence -- this allows us to apply * cmpxchg in an attempt to undo our queueing. */ |
4d3199e4c locking: Remove A... |
130 |
while (!READ_ONCE(node->locked)) { |
fb0527bd5 locking/mutexes: ... |
131 132 |
/* * If we need to reschedule bail... so we can block. |
5aff60a19 locking/osq: Brea... |
133 134 |
* Use vcpu_is_preempted() to avoid waiting for a preempted * lock holder: |
fb0527bd5 locking/mutexes: ... |
135 |
*/ |
5aff60a19 locking/osq: Brea... |
136 |
if (need_resched() || vcpu_is_preempted(node_cpu(node->prev))) |
fb0527bd5 locking/mutexes: ... |
137 |
goto unqueue; |
f2f09a4ce locking/core: Rem... |
138 |
cpu_relax(); |
fb0527bd5 locking/mutexes: ... |
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 |
} return true; unqueue: /* * Step - A -- stabilize @prev * * Undo our @prev->next assignment; this will make @prev's * unlock()/unqueue() wait for a next pointer since @lock points to us * (or later). */ for (;;) { if (prev->next == node && cmpxchg(&prev->next, node, NULL) == node) break; /* * We can only fail the cmpxchg() racing against an unlock(), * in which case we should observe @node->locked becomming * true. */ if (smp_load_acquire(&node->locked)) return true; |
f2f09a4ce locking/core: Rem... |
163 |
cpu_relax(); |
fb0527bd5 locking/mutexes: ... |
164 165 166 167 168 |
/* * Or we race against a concurrent unqueue()'s step-B, in which * case its step-C will write us a new @node->prev pointer. */ |
4d3199e4c locking: Remove A... |
169 |
prev = READ_ONCE(node->prev); |
fb0527bd5 locking/mutexes: ... |
170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 |
} /* * Step - B -- stabilize @next * * Similar to unlock(), wait for @node->next or move @lock from @node * back to @prev. */ next = osq_wait_next(lock, node, prev); if (!next) return false; /* * Step - C -- unlink * * @prev is stable because its still waiting for a new @prev->next * pointer, @next is stable because our @node->next pointer is NULL and * it will wait in Step-A. */ |
4d3199e4c locking: Remove A... |
190 191 |
WRITE_ONCE(next->prev, prev); WRITE_ONCE(prev->next, next); |
fb0527bd5 locking/mutexes: ... |
192 193 194 |
return false; } |
90631822c locking/spinlocks... |
195 |
void osq_unlock(struct optimistic_spin_queue *lock) |
fb0527bd5 locking/mutexes: ... |
196 |
{ |
33ecd2083 locking/spinlocks... |
197 |
struct optimistic_spin_node *node, *next; |
90631822c locking/spinlocks... |
198 |
int curr = encode_cpu(smp_processor_id()); |
fb0527bd5 locking/mutexes: ... |
199 200 201 202 |
/* * Fast path for the uncontended case. */ |
c55a6ffa6 locking/osq: Rela... |
203 204 |
if (likely(atomic_cmpxchg_release(&lock->tail, curr, OSQ_UNLOCKED_VAL) == curr)) |
fb0527bd5 locking/mutexes: ... |
205 206 207 208 209 |
return; /* * Second most likely case. */ |
33ecd2083 locking/spinlocks... |
210 |
node = this_cpu_ptr(&osq_node); |
fb0527bd5 locking/mutexes: ... |
211 212 |
next = xchg(&node->next, NULL); if (next) { |
4d3199e4c locking: Remove A... |
213 |
WRITE_ONCE(next->locked, 1); |
fb0527bd5 locking/mutexes: ... |
214 215 216 217 218 |
return; } next = osq_wait_next(lock, node, NULL); if (next) |
4d3199e4c locking: Remove A... |
219 |
WRITE_ONCE(next->locked, 1); |
fb0527bd5 locking/mutexes: ... |
220 |
} |