1 // SPDX-License-Identifier: GPL-2.0
14 #include <trace/events/lock.h>
27 static void do_six_unlock_type(struct six_lock *lock, enum six_lock_type type);
38 	/* Value we add to the lock in order to take the lock: */
41 	/* If the lock has this value (used as a mask), taking the lock fails: */
44 	/* Mask that indicates lock is held for this type: */
47 	/* Waitlist we wakeup when releasing the lock: */
72 static inline void six_set_bitmask(struct six_lock *lock, u32 mask)  in six_set_bitmask()  argument
74 	if ((atomic_read(&lock->state) & mask) != mask)  in six_set_bitmask()
75 		atomic_or(mask, &lock->state);  in six_set_bitmask()
78 static inline void six_clear_bitmask(struct six_lock *lock, u32 mask)  in six_clear_bitmask()  argument
80 	if (atomic_read(&lock->state) & mask)  in six_clear_bitmask()
81 		atomic_and(~mask, &lock->state);  in six_clear_bitmask()
84 static inline void six_set_owner(struct six_lock *lock, enum six_lock_type type,  in six_set_owner()  argument
91 		EBUG_ON(lock->owner);  in six_set_owner()
92 		lock->owner = owner;  in six_set_owner()
94 		EBUG_ON(lock->owner != current);  in six_set_owner()
98 static inline unsigned pcpu_read_count(struct six_lock *lock)  in pcpu_read_count()  argument
104 		read_count += *per_cpu_ptr(lock->readers, cpu);  in pcpu_read_count()
109  * __do_six_trylock() - main trylock routine
114  * for anoter thread taking the competing lock type, and we may havve to do a
115  * wakeup: when a wakeup is required, we return -1 - wakeup_type.
117 static int __do_six_trylock(struct six_lock *lock, enum six_lock_type type,  in __do_six_trylock()  argument
123 	EBUG_ON(type == SIX_LOCK_write && lock->owner != task);  in __do_six_trylock()
125 		(try != !(atomic_read(&lock->state) & SIX_LOCK_HELD_write)));  in __do_six_trylock()
130 	 * The basic idea behind this algorithm is that you can implement a lock  in __do_six_trylock()
134 	 * has the lock" and another for "thread b has the lock".  in __do_six_trylock()
136 	 * To take the lock, a thread sets its variable indicating that it holds  in __do_six_trylock()
137 	 * the lock, then issues a full memory barrier, then reads from the  in __do_six_trylock()
139 	 * the lock. If we raced, we backoff and retry/sleep.  in __do_six_trylock()
141 	 * Failure to take the lock may cause a spurious trylock failure in  in __do_six_trylock()
142 	 * another thread, because we temporarily set the lock to indicate that  in __do_six_trylock()
147 	 * Therefore, if we fail to get the lock, and there were waiters of the  in __do_six_trylock()
154 	if (type == SIX_LOCK_read && lock->readers) {  in __do_six_trylock()
156 		this_cpu_inc(*lock->readers); /* signal that we own lock */  in __do_six_trylock()
160 		old = atomic_read(&lock->state);  in __do_six_trylock()
163 		this_cpu_sub(*lock->readers, !ret);  in __do_six_trylock()
168 			if (atomic_read(&lock->state) & SIX_LOCK_WAITING_write)  in __do_six_trylock()
169 				ret = -1 - SIX_LOCK_write;  in __do_six_trylock()
171 	} else if (type == SIX_LOCK_write && lock->readers) {  in __do_six_trylock()
173 			atomic_add(SIX_LOCK_HELD_write, &lock->state);  in __do_six_trylock()
177 		ret = !pcpu_read_count(lock);  in __do_six_trylock()
180 			old = atomic_sub_return(SIX_LOCK_HELD_write, &lock->state);  in __do_six_trylock()
182 				ret = -1 - SIX_LOCK_read;  in __do_six_trylock()
185 		old = atomic_read(&lock->state);  in __do_six_trylock()
192 		} while (!atomic_try_cmpxchg_acquire(&lock->state, &old, old + l[type].lock_val));  in __do_six_trylock()
194 		EBUG_ON(ret && !(atomic_read(&lock->state) & l[type].held_mask));  in __do_six_trylock()
198 		six_set_owner(lock, type, old, task);  in __do_six_trylock()
201 		(atomic_read(&lock->state) & SIX_LOCK_HELD_write));  in __do_six_trylock()
206 static void __six_lock_wakeup(struct six_lock *lock, enum six_lock_type lock_type)  in __six_lock_wakeup()  argument
215 	raw_spin_lock(&lock->wait_lock);  in __six_lock_wakeup()
217 	list_for_each_entry_safe(w, next, &lock->wait_list, list) {  in __six_lock_wakeup()
218 		if (w->lock_want != lock_type)  in __six_lock_wakeup()
225 		ret = __do_six_trylock(lock, lock_type, w->task, false);  in __six_lock_wakeup()
231 		 * against the wakee noticing w->lock_acquired, returning, and  in __six_lock_wakeup()
234 		task = get_task_struct(w->task);  in __six_lock_wakeup()
235 		__list_del(w->list.prev, w->list.next);  in __six_lock_wakeup()
238 		 * __list_del before setting w->lock_acquired; @w is on the  in __six_lock_wakeup()
240 		 * after it sees w->lock_acquired with no other locking:  in __six_lock_wakeup()
243 		smp_store_release(&w->lock_acquired, true);  in __six_lock_wakeup()
248 	six_clear_bitmask(lock, SIX_LOCK_WAITING_read << lock_type);  in __six_lock_wakeup()
250 	raw_spin_unlock(&lock->wait_lock);  in __six_lock_wakeup()
253 		lock_type = -ret - 1;  in __six_lock_wakeup()
259 static void six_lock_wakeup(struct six_lock *lock, u32 state,  in six_lock_wakeup()  argument
262 	if (lock_type == SIX_LOCK_write && (state & SIX_LOCK_HELD_read))  in six_lock_wakeup()
265 	if (!(state & (SIX_LOCK_WAITING_read << lock_type)))  in six_lock_wakeup()
268 	__six_lock_wakeup(lock, lock_type);  in six_lock_wakeup()
272 static bool do_six_trylock(struct six_lock *lock, enum six_lock_type type, bool try)  in do_six_trylock()  argument
276 	ret = __do_six_trylock(lock, type, current, try);  in do_six_trylock()
278 		__six_lock_wakeup(lock, -ret - 1);  in do_six_trylock()
284  * six_trylock_ip - attempt to take a six lock without blocking
285  * @lock:	lock to take
291 bool six_trylock_ip(struct six_lock *lock, enum six_lock_type type, unsigned long ip)  in six_trylock_ip()  argument
293 	if (!do_six_trylock(lock, type, true))  in six_trylock_ip()
297 		six_acquire(&lock->dep_map, 1, type == SIX_LOCK_read, ip);  in six_trylock_ip()
303  * six_relock_ip - attempt to re-take a lock that was held previously
304  * @lock:	lock to take
306  * @seq:	lock sequence number obtained from six_lock_seq() while lock was
312 bool six_relock_ip(struct six_lock *lock, enum six_lock_type type,  in six_relock_ip()  argument
315 	if (six_lock_seq(lock) != seq || !six_trylock_ip(lock, type, ip))  in six_relock_ip()
318 	if (six_lock_seq(lock) != seq) {  in six_relock_ip()
319 		six_unlock_ip(lock, type, ip);  in six_relock_ip()
329 static inline bool six_owner_running(struct six_lock *lock)  in six_owner_running()  argument
333 	 * acquiring the lock and setting the owner field. If we're an RT task  in six_owner_running()
334 	 * that will live-lock because we won't let the owner complete.  in six_owner_running()
337 	struct task_struct *owner = READ_ONCE(lock->owner);  in six_owner_running()
344 static inline bool six_optimistic_spin(struct six_lock *lock,  in six_optimistic_spin()  argument
354 	if (lock->wait_list.next != &wait->list)  in six_optimistic_spin()
357 	if (atomic_read(&lock->state) & SIX_LOCK_NOSPIN)  in six_optimistic_spin()
363 	while (!need_resched() && six_owner_running(lock)) {  in six_optimistic_spin()
366 		 * wait->lock_acquired: pairs with the smp_store_release in  in six_optimistic_spin()
369 		if (smp_load_acquire(&wait->lock_acquired)) {  in six_optimistic_spin()
375 			six_set_bitmask(lock, SIX_LOCK_NOSPIN);  in six_optimistic_spin()
381 		 * everything in this loop to be re-loaded. We don't need  in six_optimistic_spin()
394 static inline bool six_optimistic_spin(struct six_lock *lock,  in six_optimistic_spin()  argument
404 static int six_lock_slowpath(struct six_lock *lock, enum six_lock_type type,  in six_lock_slowpath()  argument
412 		EBUG_ON(atomic_read(&lock->state) & SIX_LOCK_HELD_write);  in six_lock_slowpath()
413 		atomic_add(SIX_LOCK_HELD_write, &lock->state);  in six_lock_slowpath()
417 	trace_contention_begin(lock, 0);  in six_lock_slowpath()
418 	lock_contended(&lock->dep_map, ip);  in six_lock_slowpath()
420 	wait->task		= current;  in six_lock_slowpath()
421 	wait->lock_want		= type;  in six_lock_slowpath()
422 	wait->lock_acquired	= false;  in six_lock_slowpath()
424 	raw_spin_lock(&lock->wait_lock);  in six_lock_slowpath()
425 	six_set_bitmask(lock, SIX_LOCK_WAITING_read << type);  in six_lock_slowpath()
427 	 * Retry taking the lock after taking waitlist lock, in case we raced  in six_lock_slowpath()
430 	ret = __do_six_trylock(lock, type, current, false);  in six_lock_slowpath()
432 		wait->start_time = local_clock();  in six_lock_slowpath()
434 		if (!list_empty(&lock->wait_list)) {  in six_lock_slowpath()
436 				list_last_entry(&lock->wait_list,  in six_lock_slowpath()
439 			if (time_before_eq64(wait->start_time, last->start_time))  in six_lock_slowpath()
440 				wait->start_time = last->start_time + 1;  in six_lock_slowpath()
443 		list_add_tail(&wait->list, &lock->wait_list);  in six_lock_slowpath()
445 	raw_spin_unlock(&lock->wait_lock);  in six_lock_slowpath()
453 		__six_lock_wakeup(lock, -ret - 1);  in six_lock_slowpath()
457 	if (six_optimistic_spin(lock, wait, type))  in six_lock_slowpath()
465 		 * wait->lock_acquired: pairs with the smp_store_release in  in six_lock_slowpath()
468 		if (smp_load_acquire(&wait->lock_acquired))  in six_lock_slowpath()
471 		ret = should_sleep_fn ? should_sleep_fn(lock, p) : 0;  in six_lock_slowpath()
478 			 * acquired the lock - should_sleep_fn() might have  in six_lock_slowpath()
479 			 * modified external state (e.g. when the deadlock cycle  in six_lock_slowpath()
482 			raw_spin_lock(&lock->wait_lock);  in six_lock_slowpath()
483 			acquired = wait->lock_acquired;  in six_lock_slowpath()
485 				list_del(&wait->list);  in six_lock_slowpath()
486 			raw_spin_unlock(&lock->wait_lock);  in six_lock_slowpath()
489 				do_six_unlock_type(lock, type);  in six_lock_slowpath()
499 		six_clear_bitmask(lock, SIX_LOCK_HELD_write);  in six_lock_slowpath()
500 		six_lock_wakeup(lock, atomic_read(&lock->state), SIX_LOCK_read);  in six_lock_slowpath()
502 	trace_contention_end(lock, 0);  in six_lock_slowpath()
508  * six_lock_ip_waiter - take a lock, with full waitlist interface
509  * @lock:	lock to take
511  * @wait:	pointer to wait object, which will be added to lock's waitlist
521  * @wait object should be embedded into the struct that tracks held locks -
522  * which must also be accessible in a thread-safe way.
525  * lock's waiters, and for each waiter recursively walk their held locks.
527  * When this function must block, @wait will be added to @lock's waitlist before
529  * removed from the lock waitlist until the lock has been successfully acquired,
537 int six_lock_ip_waiter(struct six_lock *lock, enum six_lock_type type,  in six_lock_ip_waiter()  argument
544 	wait->start_time = 0;  in six_lock_ip_waiter()
547 		six_acquire(&lock->dep_map, 0, type == SIX_LOCK_read, ip);  in six_lock_ip_waiter()
549 	ret = do_six_trylock(lock, type, true) ? 0  in six_lock_ip_waiter()
550 		: six_lock_slowpath(lock, type, wait, should_sleep_fn, p, ip);  in six_lock_ip_waiter()
553 		six_release(&lock->dep_map, ip);  in six_lock_ip_waiter()
555 		lock_acquired(&lock->dep_map, ip);  in six_lock_ip_waiter()
562 static void do_six_unlock_type(struct six_lock *lock, enum six_lock_type type)  in do_six_unlock_type()  argument
564 	u32 state;  in do_six_unlock_type()  local
567 		lock->owner = NULL;  in do_six_unlock_type()
570 	    lock->readers) {  in do_six_unlock_type()
572 		this_cpu_dec(*lock->readers);  in do_six_unlock_type()
574 		state = atomic_read(&lock->state);  in do_six_unlock_type()
579 			v += atomic_read(&lock->state) & SIX_LOCK_NOSPIN;  in do_six_unlock_type()
581 		EBUG_ON(!(atomic_read(&lock->state) & l[type].held_mask));  in do_six_unlock_type()
582 		state = atomic_sub_return_release(v, &lock->state);  in do_six_unlock_type()
585 	six_lock_wakeup(lock, state, l[type].unlock_wakeup);  in do_six_unlock_type()
589  * six_unlock_ip - drop a six lock
590  * @lock:	lock to unlock
594  * When a lock is held multiple times (because six_lock_incement()) was used),
595  * this decrements the 'lock held' counter by one.
598  * six_lock_read(&foo->lock);				read count 1
599  * six_lock_increment(&foo->lock, SIX_LOCK_read);	read count 2
600  * six_lock_unlock(&foo->lock, SIX_LOCK_read);		read count 1
601  * six_lock_unlock(&foo->lock, SIX_LOCK_read);		read count 0
603 void six_unlock_ip(struct six_lock *lock, enum six_lock_type type, unsigned long ip)  in six_unlock_ip()  argument
606 		!(atomic_read(&lock->state) & SIX_LOCK_HELD_intent));  in six_unlock_ip()
609 		lock->owner != current);  in six_unlock_ip()
612 		six_release(&lock->dep_map, ip);  in six_unlock_ip()
614 		lock->seq++;  in six_unlock_ip()
617 	    lock->intent_lock_recurse) {  in six_unlock_ip()
618 		--lock->intent_lock_recurse;  in six_unlock_ip()
622 	do_six_unlock_type(lock, type);  in six_unlock_ip()
627  * six_lock_downgrade - convert an intent lock to a read lock
628  * @lock:	lock to dowgrade
630  * @lock will have read count incremented and intent count decremented
632 void six_lock_downgrade(struct six_lock *lock)  in six_lock_downgrade()  argument
634 	six_lock_increment(lock, SIX_LOCK_read);  in six_lock_downgrade()
635 	six_unlock_intent(lock);  in six_lock_downgrade()
640  * six_lock_tryupgrade - attempt to convert read lock to an intent lock
641  * @lock:	lock to upgrade
643  * On success, @lock will have intent count incremented and read count
648 bool six_lock_tryupgrade(struct six_lock *lock)  in six_lock_tryupgrade()  argument
650 	u32 old = atomic_read(&lock->state), new;  in six_lock_tryupgrade()
658 		if (!lock->readers) {  in six_lock_tryupgrade()
660 			new -= l[SIX_LOCK_read].lock_val;  in six_lock_tryupgrade()
664 	} while (!atomic_try_cmpxchg_acquire(&lock->state, &old, new));  in six_lock_tryupgrade()
666 	if (lock->readers)  in six_lock_tryupgrade()
667 		this_cpu_dec(*lock->readers);  in six_lock_tryupgrade()
669 	six_set_owner(lock, SIX_LOCK_intent, old, current);  in six_lock_tryupgrade()
676  * six_trylock_convert - attempt to convert a held lock from one type to another
677  * @lock:	lock to upgrade
681  * On success, @lock will have intent count incremented and read count
686 bool six_trylock_convert(struct six_lock *lock,  in six_trylock_convert()  argument
696 		six_lock_downgrade(lock);  in six_trylock_convert()
699 		return six_lock_tryupgrade(lock);  in six_trylock_convert()
705  * six_lock_increment - increase held lock count on a lock that is already held
706  * @lock:	lock to increment
709  * @lock must already be held, with a lock type that is greater than or equal to
712  * A corresponding six_unlock_type() call will be required for @lock to be fully
715 void six_lock_increment(struct six_lock *lock, enum six_lock_type type)  in six_lock_increment()  argument
717 	six_acquire(&lock->dep_map, 0, type == SIX_LOCK_read, _RET_IP_);  in six_lock_increment()
723 		if (lock->readers) {  in six_lock_increment()
724 			this_cpu_inc(*lock->readers);  in six_lock_increment()
726 			EBUG_ON(!(atomic_read(&lock->state) &  in six_lock_increment()
729 			atomic_add(l[type].lock_val, &lock->state);  in six_lock_increment()
733 		EBUG_ON(!(atomic_read(&lock->state) & SIX_LOCK_HELD_intent));  in six_lock_increment()
734 		lock->intent_lock_recurse++;  in six_lock_increment()
744  * six_lock_wakeup_all - wake up all waiters on @lock
745  * @lock:	lock to wake up waiters for
747  * Wakeing up waiters will cause them to re-run should_sleep_fn, which may then
748  * abort the lock operation.
750  * This function is never needed in a bug-free program; it's only useful in
753 void six_lock_wakeup_all(struct six_lock *lock)  in six_lock_wakeup_all()  argument
755 	u32 state = atomic_read(&lock->state);  in six_lock_wakeup_all()  local
758 	six_lock_wakeup(lock, state, SIX_LOCK_read);  in six_lock_wakeup_all()
759 	six_lock_wakeup(lock, state, SIX_LOCK_intent);  in six_lock_wakeup_all()
760 	six_lock_wakeup(lock, state, SIX_LOCK_write);  in six_lock_wakeup_all()
762 	raw_spin_lock(&lock->wait_lock);  in six_lock_wakeup_all()
763 	list_for_each_entry(w, &lock->wait_list, list)  in six_lock_wakeup_all()
764 		wake_up_process(w->task);  in six_lock_wakeup_all()
765 	raw_spin_unlock(&lock->wait_lock);  in six_lock_wakeup_all()
770  * six_lock_counts - return held lock counts, for each lock type
771  * @lock:	lock to return counters for
773  * Return: the number of times a lock is held for read, intent and write.
775 struct six_lock_count six_lock_counts(struct six_lock *lock)  in six_lock_counts()  argument
779 	ret.n[SIX_LOCK_read]	= !lock->readers  in six_lock_counts()
780 		? atomic_read(&lock->state) & SIX_LOCK_HELD_read  in six_lock_counts()
781 		: pcpu_read_count(lock);  in six_lock_counts()
782 	ret.n[SIX_LOCK_intent]	= !!(atomic_read(&lock->state) & SIX_LOCK_HELD_intent) +  in six_lock_counts()
783 		lock->intent_lock_recurse;  in six_lock_counts()
784 	ret.n[SIX_LOCK_write]	= !!(atomic_read(&lock->state) & SIX_LOCK_HELD_write);  in six_lock_counts()
791  * six_lock_readers_add - directly manipulate reader count of a lock
792  * @lock:	lock to add/subtract readers for
795  * When an upper layer is implementing lock reentrency, we may have both read
796  * and intent locks on the same lock.
798  * When we need to take a write lock, the read locks will cause self-deadlock,
800  * current thread and which are held by a different thread - it does no
801  * per-thread tracking of held locks.
804  * failed, count up its own read locks, subtract them, take the write lock, and
805  * then re-add them.
807  * As in any other situation when taking a write lock, @lock must be held for
808  * intent one (or more) times, so @lock will never be left unlocked.
810 void six_lock_readers_add(struct six_lock *lock, int nr)  in six_lock_readers_add()  argument
812 	if (lock->readers) {  in six_lock_readers_add()
813 		this_cpu_add(*lock->readers, nr);  in six_lock_readers_add()
815 		EBUG_ON((int) (atomic_read(&lock->state) & SIX_LOCK_HELD_read) + nr < 0);  in six_lock_readers_add()
817 		atomic_add(nr, &lock->state);  in six_lock_readers_add()
823  * six_lock_exit - release resources held by a lock prior to freeing
824  * @lock:	lock to exit
826  * When a lock was initialized in percpu mode (SIX_OLCK_INIT_PCPU), this is
829 void six_lock_exit(struct six_lock *lock)  in six_lock_exit()  argument
831 	WARN_ON(lock->readers && pcpu_read_count(lock));  in six_lock_exit()
832 	WARN_ON(atomic_read(&lock->state) & SIX_LOCK_HELD_read);  in six_lock_exit()
834 	free_percpu(lock->readers);  in six_lock_exit()
835 	lock->readers = NULL;  in six_lock_exit()
839 void __six_lock_init(struct six_lock *lock, const char *name,  in __six_lock_init()  argument
842 	atomic_set(&lock->state, 0);  in __six_lock_init()
843 	raw_spin_lock_init(&lock->wait_lock);  in __six_lock_init()
844 	INIT_LIST_HEAD(&lock->wait_list);  in __six_lock_init()
846 	debug_check_no_locks_freed((void *) lock, sizeof(*lock));  in __six_lock_init()
847 	lockdep_init_map(&lock->dep_map, name, key, 0);  in __six_lock_init()
859 		 * same semantics in non-percpu mode: callers can check for  in __six_lock_init()
860 		 * failure if they wish by checking lock->readers, but generally  in __six_lock_init()
863 		lock->readers = alloc_percpu(unsigned);  in __six_lock_init()