// SPDX-License-Identifier: GPL-2.0/* kernel/rwsem.c: R/W semaphores, public implementation * * Written by David Howells (dhowells@redhat.com). * Derived from asm-i386/semaphore.h * * Writer lock-stealing by Alex Shi <alex.shi@intel.com> * and Michel Lespinasse <walken@google.com> * * Optimistic spinning by Tim Chen <tim.c.chen@intel.com> * and Davidlohr Bueso <davidlohr@hp.com>. Based on mutexes. * * Rwsem count bit fields re-definition and rwsem rearchitecture by * Waiman Long <longman@redhat.com> and * Peter Zijlstra <peterz@infradead.org>. */ #include <linux/types.h>#include <linux/kernel.h>#include <linux/sched.h>#include <linux/sched/rt.h>#include <linux/sched/task.h>#include <linux/sched/debug.h>#include <linux/sched/wake_q.h>#include <linux/sched/signal.h>#include <linux/sched/clock.h>#include <linux/export.h>#include <linux/rwsem.h>#include <linux/atomic.h> #ifndef CONFIG_PREEMPT_RT#include "lock_events.h" /* * The least significant 2 bits of the owner value has the following * meanings when set. *  - Bit 0: RWSEM_READER_OWNED - The rwsem is owned by readers *  - Bit 1: RWSEM_NONSPINNABLE - Cannot spin on a reader-owned lock * * When the rwsem is reader-owned and a spinning writer has timed out, * the nonspinnable bit will be set to disable optimistic spinning.  * When a writer acquires a rwsem, it puts its task_struct pointer * into the owner field. It is cleared after an unlock. * * When a reader acquires a rwsem, it will also puts its task_struct * pointer into the owner field with the RWSEM_READER_OWNED bit set. * On unlock, the owner field will largely be left untouched. So * for a free or reader-owned rwsem, the owner value may contain * information about the last reader that acquires the rwsem. * * That information may be helpful in debugging cases where the system * seems to hang on a reader owned rwsem especially if only one reader * is involved. Ideally we would like to track all the readers that own * a rwsem, but the overhead is simply too big. * * A fast path reader optimistic lock stealing is supported when the rwsem * is previously owned by a writer and the following conditions are met: *  - OSQ is empty *  - rwsem is not currently writer owned *  - the handoff isn't set. */#define RWSEM_READER_OWNED	(1UL << 0)#define RWSEM_NONSPINNABLE	(1UL << 1)#define RWSEM_OWNER_FLAGS_MASK	(RWSEM_READER_OWNED | RWSEM_NONSPINNABLE) #ifdef CONFIG_DEBUG_RWSEMS# define DEBUG_RWSEMS_WARN_ON(c, sem)	do {			\	if (!debug_locks_silent &&				\	    WARN_ONCE(c, "DEBUG_RWSEMS_WARN_ON(%s): count = 0x%lx, magic = 0x%lx, owner = 0x%lx, curr 0x%lx, list %sempty\n",\		#c, atomic_long_read(&(sem)->count),		\		(unsigned long) sem->magic,			\		atomic_long_read(&(sem)->owner), (long)current,	\		list_empty(&(sem)->wait_list) ? "" : "not "))	\			debug_locks_off();			\	} while (0)#else# define DEBUG_RWSEMS_WARN_ON(c, sem)#endif /* * On 64-bit architectures, the bit definitions of the count are: * * Bit  0    - writer locked bit * Bit  1    - waiters present bit * Bit  2    - lock handoff bit * Bits 3-7  - reserved * Bits 8-62 - 55-bit reader count * Bit  63   - read fail bit * * On 32-bit architectures, the bit definitions of the count are: * * Bit  0    - writer locked bit * Bit  1    - waiters present bit * Bit  2    - lock handoff bit * Bits 3-7  - reserved * Bits 8-30 - 23-bit reader count * Bit  31   - read fail bit * * It is not likely that the most significant bit (read fail bit) will ever * be set. This guard bit is still checked anyway in the down_read() fastpath * just in case we need to use up more of the reader bits for other purpose * in the future. * * atomic_long_fetch_add() is used to obtain reader lock, whereas * atomic_long_cmpxchg() will be used to obtain writer lock. * * There are three places where the lock handoff bit may be set or cleared. * 1) rwsem_mark_wake() for readers. * 2) rwsem_try_write_lock() for writers. * 3) Error path of rwsem_down_write_slowpath(). * * For all the above cases, wait_lock will be held. A writer must also * be the first one in the wait_list to be eligible for setting the handoff * bit. So concurrent setting/clearing of handoff bit is not possible. */#define RWSEM_WRITER_LOCKED	(1UL << 0)#define RWSEM_FLAG_WAITERS	(1UL << 1)#define RWSEM_FLAG_HANDOFF	(1UL << 2)#define RWSEM_FLAG_READFAIL	(1UL << (BITS_PER_LONG - 1)) #define RWSEM_READER_SHIFT	8#define RWSEM_READER_BIAS	(1UL << RWSEM_READER_SHIFT)#define RWSEM_READER_MASK	(~(RWSEM_READER_BIAS - 1))#define RWSEM_WRITER_MASK	RWSEM_WRITER_LOCKED#define RWSEM_LOCK_MASK		(RWSEM_WRITER_MASK|RWSEM_READER_MASK)#define RWSEM_READ_FAILED_MASK	(RWSEM_WRITER_MASK|RWSEM_FLAG_WAITERS|\				 RWSEM_FLAG_HANDOFF|RWSEM_FLAG_READFAIL) /* * All writes to owner are protected by WRITE_ONCE() to make sure that * store tearing can't happen as optimistic spinners may read and use * the owner value concurrently without lock. Read from owner, however, * may not need READ_ONCE() as long as the pointer value is only used * for comparison and isn't being dereferenced. */static inline void rwsem_set_owner(struct rw_semaphore *sem){	atomic_long_set(&sem->owner, (long)current);} static inline void rwsem_clear_owner(struct rw_semaphore *sem){	atomic_long_set(&sem->owner, 0);} /* * Test the flags in the owner field. */static inline bool rwsem_test_oflags(struct rw_semaphore *sem, long flags){	return atomic_long_read(&sem->owner) & flags;} /* * The task_struct pointer of the last owning reader will be left in * the owner field. * * Note that the owner value just indicates the task has owned the rwsem * previously, it may not be the real owner or one of the real owners * anymore when that field is examined, so take it with a grain of salt. * * The reader non-spinnable bit is preserved. */static inline void __rwsem_set_reader_owned(struct rw_semaphore *sem,					    struct task_struct *owner){	unsigned long val = (unsigned long)owner | RWSEM_READER_OWNED |		(atomic_long_read(&sem->owner) & RWSEM_NONSPINNABLE); 	atomic_long_set(&sem->owner, val);} static inline void rwsem_set_reader_owned(struct rw_semaphore *sem){	__rwsem_set_reader_owned(sem, current);} /* * Return true if the rwsem is owned by a reader. */static inline bool is_rwsem_reader_owned(struct rw_semaphore *sem){#ifdef CONFIG_DEBUG_RWSEMS	/*	 * Check the count to see if it is write-locked.	 */	long count = atomic_long_read(&sem->count); 	if (count & RWSEM_WRITER_MASK)		return false;#endif	return rwsem_test_oflags(sem, RWSEM_READER_OWNED);} #ifdef CONFIG_DEBUG_RWSEMS/* * With CONFIG_DEBUG_RWSEMS configured, it will make sure that if there * is a task pointer in owner of a reader-owned rwsem, it will be the * real owner or one of the real owners. The only exception is when the * unlock is done by up_read_non_owner(). */static inline void rwsem_clear_reader_owned(struct rw_semaphore *sem){	unsigned long val = atomic_long_read(&sem->owner); 	while ((val & ~RWSEM_OWNER_FLAGS_MASK) == (unsigned long)current) {		if (atomic_long_try_cmpxchg(&sem->owner, &val,					    val & RWSEM_OWNER_FLAGS_MASK))			return;	}}#elsestatic inline void rwsem_clear_reader_owned(struct rw_semaphore *sem){}#endif /* * Set the RWSEM_NONSPINNABLE bits if the RWSEM_READER_OWNED flag * remains set. Otherwise, the operation will be aborted. */static inline void rwsem_set_nonspinnable(struct rw_semaphore *sem){	unsigned long owner = atomic_long_read(&sem->owner); 	do {		if (!(owner & RWSEM_READER_OWNED))			break;		if (owner & RWSEM_NONSPINNABLE)			break;	} while (!atomic_long_try_cmpxchg(&sem->owner, &owner,					  owner | RWSEM_NONSPINNABLE));} static inline bool rwsem_read_trylock(struct rw_semaphore *sem, long *cntp){	*cntp = atomic_long_add_return_acquire(RWSEM_READER_BIAS, &sem->count); 	if (WARN_ON_ONCE(*cntp < 0))		rwsem_set_nonspinnable(sem); 	if (!(*cntp & RWSEM_READ_FAILED_MASK)) {		rwsem_set_reader_owned(sem);		return true;	} 	return false;} static inline bool rwsem_write_trylock(struct rw_semaphore *sem){	long tmp = RWSEM_UNLOCKED_VALUE; 	if (atomic_long_try_cmpxchg_acquire(&sem->count, &tmp, RWSEM_WRITER_LOCKED)) {		rwsem_set_owner(sem);		return true;	} 	return false;} /* * Return just the real task structure pointer of the owner */static inline struct task_struct *rwsem_owner(struct rw_semaphore *sem){	return (struct task_struct *)		(atomic_long_read(&sem->owner) & ~RWSEM_OWNER_FLAGS_MASK);} /* * Return the real task structure pointer of the owner and the embedded * flags in the owner. pflags must be non-NULL. */static inline struct task_struct *rwsem_owner_flags(struct rw_semaphore *sem, unsigned long *pflags){	unsigned long owner = atomic_long_read(&sem->owner); 	*pflags = owner & RWSEM_OWNER_FLAGS_MASK;	return (struct task_struct *)(owner & ~RWSEM_OWNER_FLAGS_MASK);} /* * Guide to the rw_semaphore's count field. * * When the RWSEM_WRITER_LOCKED bit in count is set, the lock is owned * by a writer. * * The lock is owned by readers when * (1) the RWSEM_WRITER_LOCKED isn't set in count, * (2) some of the reader bits are set in count, and * (3) the owner field has RWSEM_READ_OWNED bit set. * * Having some reader bits set is not enough to guarantee a readers owned * lock as the readers may be in the process of backing out from the count * and a writer has just released the lock. So another writer may steal * the lock immediately after that. */ /* * Initialize an rwsem: */void __init_rwsem(struct rw_semaphore *sem, const char *name,		  struct lock_class_key *key){#ifdef CONFIG_DEBUG_LOCK_ALLOC	/*	 * Make sure we are not reinitializing a held semaphore:	 */	debug_check_no_locks_freed((void *)sem, sizeof(*sem));	lockdep_init_map_wait(&sem->dep_map, name, key, 0, LD_WAIT_SLEEP);#endif#ifdef CONFIG_DEBUG_RWSEMS	sem->magic = sem;#endif	atomic_long_set(&sem->count, RWSEM_UNLOCKED_VALUE);	raw_spin_lock_init(&sem->wait_lock);	INIT_LIST_HEAD(&sem->wait_list);	atomic_long_set(&sem->owner, 0L);#ifdef CONFIG_RWSEM_SPIN_ON_OWNER	osq_lock_init(&sem->osq);#endif}EXPORT_SYMBOL(__init_rwsem); enum rwsem_waiter_type {	RWSEM_WAITING_FOR_WRITE,	RWSEM_WAITING_FOR_READ}; struct rwsem_waiter {	struct list_head list;	struct task_struct *task;	enum rwsem_waiter_type type;	unsigned long timeout;};#define rwsem_first_waiter(sem) \	list_first_entry(&sem->wait_list, struct rwsem_waiter, list) enum rwsem_wake_type {	RWSEM_WAKE_ANY,		/* Wake whatever's at head of wait list */	RWSEM_WAKE_READERS,	/* Wake readers only */	RWSEM_WAKE_READ_OWNED	/* Waker thread holds the read lock */}; enum writer_wait_state {	WRITER_NOT_FIRST,	/* Writer is not first in wait list */	WRITER_FIRST,		/* Writer is first in wait list     */	WRITER_HANDOFF		/* Writer is first & handoff needed */}; /* * The typical HZ value is either 250 or 1000. So set the minimum waiting * time to at least 4ms or 1 jiffy (if it is higher than 4ms) in the wait * queue before initiating the handoff protocol. */#define RWSEM_WAIT_TIMEOUT	DIV_ROUND_UP(HZ, 250) /* * Magic number to batch-wakeup waiting readers, even when writers are * also present in the queue. This both limits the amount of work the * waking thread must do and also prevents any potential counter overflow, * however unlikely. */#define MAX_READERS_WAKEUP	0x100 /* * handle the lock release when processes blocked on it that can now run * - if we come here from up_xxxx(), then the RWSEM_FLAG_WAITERS bit must *   have been set. * - there must be someone on the queue * - the wait_lock must be held by the caller * - tasks are marked for wakeup, the caller must later invoke wake_up_q() *   to actually wakeup the blocked task(s) and drop the reference count, *   preferably when the wait_lock is released * - woken process blocks are discarded from the list after having task zeroed * - writers are only marked woken if downgrading is false */static void rwsem_mark_wake(struct rw_semaphore *sem,			    enum rwsem_wake_type wake_type,			    struct wake_q_head *wake_q){	struct rwsem_waiter *waiter, *tmp;	long oldcount, woken = 0, adjustment = 0;	struct list_head wlist; 	lockdep_assert_held(&sem->wait_lock); 	/*	 * Take a peek at the queue head waiter such that we can determine	 * the wakeup(s) to perform.	 */	waiter = rwsem_first_waiter(sem); 	if (waiter->type == RWSEM_WAITING_FOR_WRITE) {		if (wake_type == RWSEM_WAKE_ANY) {			/*			 * Mark writer at the front of the queue for wakeup.			 * Until the task is actually later awoken later by			 * the caller, other writers are able to steal it.			 * Readers, on the other hand, will block as they			 * will notice the queued writer.			 */			wake_q_add(wake_q, waiter->task);			lockevent_inc(rwsem_wake_writer);		} 		return;	} 	/*	 * No reader wakeup if there are too many of them already.	 */	if (unlikely(atomic_long_read(&sem->count) < 0))		return; 	/*	 * Writers might steal the lock before we grant it to the next reader.	 * We prefer to do the first reader grant before counting readers	 * so we can bail out early if a writer stole the lock.	 */	if (wake_type != RWSEM_WAKE_READ_OWNED) {		struct task_struct *owner; 		adjustment = RWSEM_READER_BIAS;		oldcount = atomic_long_fetch_add(adjustment, &sem->count);		if (unlikely(oldcount & RWSEM_WRITER_MASK)) {			/*			 * When we've been waiting "too" long (for writers			 * to give up the lock), request a HANDOFF to			 * force the issue.			 */			if (!(oldcount & RWSEM_FLAG_HANDOFF) &&			    time_after(jiffies, waiter->timeout)) {				adjustment -= RWSEM_FLAG_HANDOFF;				lockevent_inc(rwsem_rlock_handoff);			} 			atomic_long_add(-adjustment, &sem->count);			return;		}		/*		 * Set it to reader-owned to give spinners an early		 * indication that readers now have the lock.		 * The reader nonspinnable bit seen at slowpath entry of		 * the reader is copied over.		 */		owner = waiter->task;		__rwsem_set_reader_owned(sem, owner);	} 	/*	 * Grant up to MAX_READERS_WAKEUP read locks to all the readers in the	 * queue. We know that the woken will be at least 1 as we accounted	 * for above. Note we increment the 'active part' of the count by the	 * number of readers before waking any processes up.	 *	 * This is an adaptation of the phase-fair R/W locks where at the	 * reader phase (first waiter is a reader), all readers are eligible	 * to acquire the lock at the same time irrespective of their order	 * in the queue. The writers acquire the lock according to their	 * order in the queue.	 *	 * We have to do wakeup in 2 passes to prevent the possibility that	 * the reader count may be decremented before it is incremented. It	 * is because the to-be-woken waiter may not have slept yet. So it	 * may see waiter->task got cleared, finish its critical section and	 * do an unlock before the reader count increment.	 *	 * 1) Collect the read-waiters in a separate list, count them and	 *    fully increment the reader count in rwsem.	 * 2) For each waiters in the new list, clear waiter->task and	 *    put them into wake_q to be woken up later.	 */	INIT_LIST_HEAD(&wlist);	list_for_each_entry_safe(waiter, tmp, &sem->wait_list, list) {		if (waiter->type == RWSEM_WAITING_FOR_WRITE)			continue; 		woken++;		list_move_tail(&waiter->list, &wlist); 		/*		 * Limit # of readers that can be woken up per wakeup call.		 */		if (woken >= MAX_READERS_WAKEUP)			break;	} 	adjustment = woken * RWSEM_READER_BIAS - adjustment;	lockevent_cond_inc(rwsem_wake_reader, woken);	if (list_empty(&sem->wait_list)) {		/* hit end of list above */		adjustment -= RWSEM_FLAG_WAITERS;	} 	/*	 * When we've woken a reader, we no longer need to force writers

Lines 1–500 of 1654. Load more