2 #include <linux/log2.h>
3 #include <linux/preempt.h>
4 #include <linux/rcupdate.h>
5 #include <linux/sched.h>
6 #include <linux/sched/rt.h>
10 #define six_acquire(l, t) lock_acquire(l, 0, t, 0, 0, NULL, _RET_IP_)
11 #define six_release(l) lock_release(l, 0, _RET_IP_)
13 #define __SIX_LOCK_HELD_read __SIX_VAL(read_lock, ~0)
14 #define __SIX_LOCK_HELD_intent __SIX_VAL(intent_lock, ~0)
15 #define __SIX_LOCK_HELD_write __SIX_VAL(seq, 1)
17 struct six_lock_vals {
18 /* Value we add to the lock in order to take the lock: */
21 /* If the lock has this value (used as a mask), taking the lock fails: */
24 /* Value we add to the lock in order to release the lock: */
27 /* Mask that indicates lock is held for this type: */
30 /* Waitlist we wakeup when releasing the lock: */
31 enum six_lock_type unlock_wakeup;
36 .lock_val = __SIX_VAL(read_lock, 1), \
37 .lock_fail = __SIX_LOCK_HELD_write, \
38 .unlock_val = -__SIX_VAL(read_lock, 1), \
39 .held_mask = __SIX_LOCK_HELD_read, \
40 .unlock_wakeup = SIX_LOCK_write, \
42 [SIX_LOCK_intent] = { \
43 .lock_val = __SIX_VAL(intent_lock, 1), \
44 .lock_fail = __SIX_LOCK_HELD_intent, \
45 .unlock_val = -__SIX_VAL(intent_lock, 1), \
46 .held_mask = __SIX_LOCK_HELD_intent, \
47 .unlock_wakeup = SIX_LOCK_intent, \
49 [SIX_LOCK_write] = { \
50 .lock_val = __SIX_VAL(seq, 1), \
51 .lock_fail = __SIX_LOCK_HELD_read, \
52 .unlock_val = __SIX_VAL(seq, 1), \
53 .held_mask = __SIX_LOCK_HELD_write, \
54 .unlock_wakeup = SIX_LOCK_read, \
58 static void six_set_owner(struct six_lock *lock, enum six_lock_type type)
60 if (type == SIX_LOCK_intent)
61 lock->owner = current;
64 static void six_clear_owner(struct six_lock *lock, enum six_lock_type type)
66 if (type == SIX_LOCK_intent)
70 static inline bool __six_trylock_type(struct six_lock *lock,
71 enum six_lock_type type)
73 const struct six_lock_vals l[] = LOCK_VALS;
74 union six_lock_state old;
75 u64 v = READ_ONCE(lock->state.v);
80 EBUG_ON(type == SIX_LOCK_write &&
81 ((old.v & __SIX_LOCK_HELD_write) ||
82 !(old.v & __SIX_LOCK_HELD_intent)));
84 if (old.v & l[type].lock_fail)
86 } while ((v = atomic64_cmpxchg_acquire(&lock->state.counter,
88 old.v + l[type].lock_val)) != old.v);
92 bool six_trylock_type(struct six_lock *lock, enum six_lock_type type)
94 bool ret = __six_trylock_type(lock, type);
97 six_acquire(&lock->dep_map, 1);
98 six_set_owner(lock, type);
104 bool six_relock_type(struct six_lock *lock, enum six_lock_type type,
107 const struct six_lock_vals l[] = LOCK_VALS;
108 union six_lock_state old;
109 u64 v = READ_ONCE(lock->state.v);
114 if (old.seq != seq || old.v & l[type].lock_fail)
116 } while ((v = atomic64_cmpxchg_acquire(&lock->state.counter,
118 old.v + l[type].lock_val)) != old.v);
120 six_acquire(&lock->dep_map, 1);
121 six_set_owner(lock, type);
125 struct six_lock_waiter {
126 struct list_head list;
127 struct task_struct *task;
130 /* This is probably up there with the more evil things I've done */
131 #define waitlist_bitnr(id) ilog2((((union six_lock_state) { .waiters = 1 << (id) }).l))
133 static inline int six_can_spin_on_owner(struct six_lock *lock)
135 struct task_struct *owner;
142 owner = READ_ONCE(lock->owner);
144 retval = owner->on_cpu;
147 * if lock->owner is not set, the mutex owner may have just acquired
148 * it and not set the owner yet or the mutex has been released.
153 static bool six_spin_on_owner(struct six_lock *lock, struct task_struct *owner)
158 while (lock->owner == owner) {
160 * Ensure we emit the owner->on_cpu, dereference _after_
161 * checking lock->owner still matches owner. If that fails,
162 * owner might point to freed memory. If it still matches,
163 * the rcu_read_lock() ensures the memory stays valid.
167 if (!owner->on_cpu || need_resched()) {
179 static bool six_optimistic_spin(struct six_lock *lock, enum six_lock_type type)
181 struct task_struct *task = current;
183 if (type == SIX_LOCK_write)
187 if (!six_can_spin_on_owner(lock))
190 if (!osq_lock(&lock->osq))
194 struct task_struct *owner;
197 * If there's an owner, wait for it to either
198 * release the lock or go to sleep.
200 owner = READ_ONCE(lock->owner);
201 if (owner && !six_spin_on_owner(lock, owner))
204 if (__six_trylock_type(lock, type)) {
205 osq_unlock(&lock->osq);
211 * When there's no owner, we might have preempted between the
212 * owner acquiring the lock and setting the owner field. If
213 * we're an RT task that will live-lock because we won't let
214 * the owner complete.
216 if (!owner && (need_resched() || rt_task(task)))
220 * The cpu_relax() call is a compiler barrier which forces
221 * everything in this loop to be re-loaded. We don't need
222 * memory barriers as we'll eventually observe the right
223 * values at the cost of a few extra spins.
228 osq_unlock(&lock->osq);
233 * If we fell out of the spin path because of need_resched(),
234 * reschedule now, before we try-lock again. This avoids getting
235 * scheduled out right after we obtained the lock.
243 void six_lock_type(struct six_lock *lock, enum six_lock_type type)
245 const struct six_lock_vals l[] = LOCK_VALS;
246 union six_lock_state old, new;
247 struct six_lock_waiter wait;
250 six_acquire(&lock->dep_map, 0);
252 if (__six_trylock_type(lock, type))
255 if (six_optimistic_spin(lock, type))
258 lock_contended(&lock->dep_map, _RET_IP_);
260 INIT_LIST_HEAD(&wait.list);
264 set_current_state(TASK_UNINTERRUPTIBLE);
265 if (list_empty_careful(&wait.list)) {
266 raw_spin_lock(&lock->wait_lock);
267 list_add_tail(&wait.list, &lock->wait_list[type]);
268 raw_spin_unlock(&lock->wait_lock);
271 v = READ_ONCE(lock->state.v);
275 if (!(old.v & l[type].lock_fail))
276 new.v += l[type].lock_val;
277 else if (!(new.waiters & (1 << type)))
278 new.waiters |= 1 << type;
280 break; /* waiting bit already set */
281 } while ((v = atomic64_cmpxchg_acquire(&lock->state.counter,
282 old.v, new.v)) != old.v);
284 if (!(old.v & l[type].lock_fail))
290 __set_current_state(TASK_RUNNING);
292 if (!list_empty_careful(&wait.list)) {
293 raw_spin_lock(&lock->wait_lock);
294 list_del_init(&wait.list);
295 raw_spin_unlock(&lock->wait_lock);
298 lock_acquired(&lock->dep_map, _RET_IP_);
299 six_set_owner(lock, type);
302 static inline void six_lock_wakeup(struct six_lock *lock,
303 union six_lock_state state,
304 unsigned waitlist_id)
306 struct list_head *wait_list = &lock->wait_list[waitlist_id];
307 struct six_lock_waiter *w, *next;
309 if (waitlist_id == SIX_LOCK_write && state.read_lock)
312 if (!(state.waiters & (1 << waitlist_id)))
315 clear_bit(waitlist_bitnr(waitlist_id),
316 (unsigned long *) &lock->state.v);
318 raw_spin_lock(&lock->wait_lock);
320 list_for_each_entry_safe(w, next, wait_list, list) {
321 list_del_init(&w->list);
323 if (wake_up_process(w->task) &&
324 waitlist_id != SIX_LOCK_read) {
325 if (!list_empty(wait_list))
326 set_bit(waitlist_bitnr(waitlist_id),
327 (unsigned long *) &lock->state.v);
332 raw_spin_unlock(&lock->wait_lock);
335 void six_unlock_type(struct six_lock *lock, enum six_lock_type type)
337 const struct six_lock_vals l[] = LOCK_VALS;
338 union six_lock_state state;
340 six_clear_owner(lock, type);
342 EBUG_ON(!(lock->state.v & l[type].held_mask));
343 EBUG_ON(type == SIX_LOCK_write &&
344 !(lock->state.v & __SIX_LOCK_HELD_intent));
346 state.v = atomic64_add_return_release(l[type].unlock_val,
347 &lock->state.counter);
348 six_release(&lock->dep_map);
349 six_lock_wakeup(lock, state, l[type].unlock_wakeup);
352 bool six_trylock_convert(struct six_lock *lock,
353 enum six_lock_type from,
354 enum six_lock_type to)
356 const struct six_lock_vals l[] = LOCK_VALS;
357 union six_lock_state old, new;
358 u64 v = READ_ONCE(lock->state.v);
362 new.v += l[from].unlock_val;
364 if (new.v & l[to].lock_fail)
366 } while ((v = atomic64_cmpxchg_acquire(&lock->state.counter,
368 new.v + l[to].lock_val)) != old.v);
370 six_clear_owner(lock, from);
371 six_set_owner(lock, to);
373 six_lock_wakeup(lock, new, l[from].unlock_wakeup);
379 * Increment read/intent lock count, assuming we already have it read or intent
382 void six_lock_increment(struct six_lock *lock, enum six_lock_type type)
384 const struct six_lock_vals l[] = LOCK_VALS;
386 EBUG_ON(type == SIX_LOCK_write);
387 six_acquire(&lock->dep_map, 0);
389 /* XXX: assert already locked, and that we don't overflow: */
391 atomic64_add(l[type].lock_val, &lock->state.counter);
394 /* Convert from intent to read: */
395 void six_lock_downgrade(struct six_lock *lock)
397 six_lock_increment(lock, SIX_LOCK_read);
398 six_unlock_intent(lock);