From nobody Thu Apr 9 21:57:23 2026 Received: from casper.infradead.org (casper.infradead.org [90.155.50.34]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2D5E03E123D for ; Thu, 5 Mar 2026 19:55:50 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=90.155.50.34 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1772740553; cv=none; b=kil26PFST7JjT5E9mw60SBItzbrJBsdBfe+MqumcQJCNmcth8UPD53u2j3Gnf7/YzvNcHi3LVCxjGEGcLQoHR71Ilp0yuMvsws0Aw4Yf+bZLjEEXlomPckxmTR/7+OAlfBTe21tUXSiDFaEw4ZZiGPbL/hF/bBnAhaZ1cHrvz70= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1772740553; c=relaxed/simple; bh=aiXptpPWFyzmvgRmE/7zRmQS5SN9KFZthYgyLZv66As=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=CmObW1m0EHh1GR/qB9YpS8JR89bIK08XncC6quGyN525spuT/VkZir3RNvOiy4u11nJBmlO3T+rRXmSFFrdmHO1MPYD8o4VKmtfvOhwR9KeBoXriR5SN1EbQZ+uKIGsxwNyPhRVt/CanfteCbn7pvRx5d/EdQBCMfVc54PUlH5E= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org; spf=none smtp.mailfrom=infradead.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b=GMFAA5l+; arc=none smtp.client-ip=90.155.50.34 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=infradead.org Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=infradead.org Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="GMFAA5l+" DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=casper.20170209; h=Content-Transfer-Encoding:MIME-Version: References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Sender:Reply-To: Content-Type:Content-ID:Content-Description; bh=777Q1eBBiI5jR1iz/ArGmsTPTNXMXX/GIX3RGqh5TdU=; b=GMFAA5l+39hYvl46GNyehW5uVI EpqSuo1B+nQVVeCue4PvCscT/iIEfgjzuKYkpJjl0iAAeL5gewOj5RAiaDdmMZw3jxCs/HIGNidiM vsGiCMW39k6WtmMG1DHS7CEcX7jMkwWybgX0dFb3FpXc1Y/NSWSLv1oBBBYk9DOdWPSgbFouejVZe meg4a8iABzvoB2jwdm4o0hfk2bSzNvXrd3/rVsPmUTdyjZgBZ7jmUDnh4+EZShwDXYCFrA++Krs4Z ONrfytUOlVXAO26gFPj052Lnxr9KkeuRh4ew2vkBgf7ef8Pg9KzYBWFc3YjW9skRoyO9PxnOgrwxR a8QK4Zsw==; Received: from willy by casper.infradead.org with local (Exim 4.98.2 #2 (Red Hat Linux)) id 1vyEnT-0000000FYWC-3HjM; Thu, 05 Mar 2026 19:55:47 +0000 From: "Matthew Wilcox (Oracle)" To: Peter Zijlstra Cc: "Matthew Wilcox (Oracle)" , Ingo Molnar , Will Deacon , Boqun Feng , Waiman Long , linux-kernel@vger.kernel.org Subject: [PATCH 1/3] rwsem: Remove the list_head from struct rw_semaphore Date: Thu, 5 Mar 2026 19:55:41 +0000 Message-ID: <20260305195545.3707590-2-willy@infradead.org> X-Mailer: git-send-email 2.51.0 In-Reply-To: <20260305195545.3707590-1-willy@infradead.org> References: <20260305195545.3707590-1-willy@infradead.org> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Instead of embedding a list_head in struct rw_semaphore, store a pointer to the first waiter. The list of waiters remains a doubly linked list so we can efficiently add to the tail of the list, remove from the front (or middle) of the list. Some of the list manipulation becomes more complicated, but it's a reasonable tradeoff on the slow paths to shrink some core data structures like struct inode. Signed-off-by: Matthew Wilcox (Oracle) --- include/linux/rwsem.h | 8 ++-- kernel/locking/rwsem.c | 89 +++++++++++++++++++++++++++--------------- 2 files changed, 61 insertions(+), 36 deletions(-) diff --git a/include/linux/rwsem.h b/include/linux/rwsem.h index f1aaf676a874..1771c96a01d2 100644 --- a/include/linux/rwsem.h +++ b/include/linux/rwsem.h @@ -57,7 +57,7 @@ struct rw_semaphore { struct optimistic_spin_queue osq; /* spinner MCS lock */ #endif raw_spinlock_t wait_lock; - struct list_head wait_list; + struct rwsem_waiter *first_waiter; #ifdef CONFIG_DEBUG_RWSEMS void *magic; #endif @@ -104,7 +104,7 @@ static inline void rwsem_assert_held_write_nolockdep(co= nst struct rw_semaphore * .owner =3D ATOMIC_LONG_INIT(0), \ __RWSEM_OPT_INIT(name) \ .wait_lock =3D __RAW_SPIN_LOCK_UNLOCKED(name.wait_lock),\ - .wait_list =3D LIST_HEAD_INIT((name).wait_list), \ + .first_waiter =3D NULL, \ __RWSEM_DEBUG_INIT(name) \ __RWSEM_DEP_MAP_INIT(name) } =20 @@ -127,9 +127,9 @@ do { \ * rwsem to see if somebody from an incompatible type is wanting access to= the * lock. */ -static inline int rwsem_is_contended(struct rw_semaphore *sem) +static inline bool rwsem_is_contended(struct rw_semaphore *sem) { - return !list_empty(&sem->wait_list); + return sem->first_waiter !=3D NULL; } =20 #if defined(CONFIG_DEBUG_RWSEMS) || defined(CONFIG_DETECT_HUNG_TASK_BLOCKE= R) diff --git a/kernel/locking/rwsem.c b/kernel/locking/rwsem.c index 24df4d98f7d2..6030d5d81ccc 100644 --- a/kernel/locking/rwsem.c +++ b/kernel/locking/rwsem.c @@ -72,7 +72,7 @@ #c, atomic_long_read(&(sem)->count), \ (unsigned long) sem->magic, \ atomic_long_read(&(sem)->owner), (long)current, \ - list_empty(&(sem)->wait_list) ? "" : "not ")) \ + (sem)->first_waiter ? "" : "not ")) \ debug_locks_off(); \ } while (0) #else @@ -321,7 +321,7 @@ void __init_rwsem(struct rw_semaphore *sem, const char = *name, #endif atomic_long_set(&sem->count, RWSEM_UNLOCKED_VALUE); raw_spin_lock_init(&sem->wait_lock); - INIT_LIST_HEAD(&sem->wait_list); + sem->first_waiter =3D NULL; atomic_long_set(&sem->owner, 0L); #ifdef CONFIG_RWSEM_SPIN_ON_OWNER osq_lock_init(&sem->osq); @@ -341,8 +341,6 @@ struct rwsem_waiter { unsigned long timeout; bool handoff_set; }; -#define rwsem_first_waiter(sem) \ - list_first_entry(&sem->wait_list, struct rwsem_waiter, list) =20 enum rwsem_wake_type { RWSEM_WAKE_ANY, /* Wake whatever's at head of wait list */ @@ -365,12 +363,21 @@ enum rwsem_wake_type { */ #define MAX_READERS_WAKEUP 0x100 =20 -static inline void -rwsem_add_waiter(struct rw_semaphore *sem, struct rwsem_waiter *waiter) +static inline +bool __rwsem_del_waiter(struct rw_semaphore *sem, struct rwsem_waiter *wai= ter) { - lockdep_assert_held(&sem->wait_lock); - list_add_tail(&waiter->list, &sem->wait_list); - /* caller will set RWSEM_FLAG_WAITERS */ + if (list_empty(&waiter->list)) { + sem->first_waiter =3D NULL; + return true; + } + + if (sem->first_waiter =3D=3D waiter) { + sem->first_waiter =3D list_first_entry(&waiter->list, + struct rwsem_waiter, list); + } + list_del(&waiter->list); + + return false; } =20 /* @@ -385,14 +392,22 @@ static inline bool rwsem_del_waiter(struct rw_semaphore *sem, struct rwsem_waiter *waiter) { lockdep_assert_held(&sem->wait_lock); - list_del(&waiter->list); - if (likely(!list_empty(&sem->wait_list))) + if (__rwsem_del_waiter(sem, waiter)) return true; - atomic_long_andnot(RWSEM_FLAG_HANDOFF | RWSEM_FLAG_WAITERS, &sem->count); return false; } =20 +static inline struct rwsem_waiter *next_waiter(const struct rw_semaphore *= sem, + const struct rwsem_waiter *waiter) +{ + struct rwsem_waiter *next =3D list_first_entry(&waiter->list, + struct rwsem_waiter, list); + if (next =3D=3D sem->first_waiter) + return NULL; + return next; +} + /* * 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 @@ -411,7 +426,7 @@ 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; + struct rwsem_waiter *waiter, *next; long oldcount, woken =3D 0, adjustment =3D 0; struct list_head wlist; =20 @@ -421,7 +436,7 @@ static void rwsem_mark_wake(struct rw_semaphore *sem, * Take a peek at the queue head waiter such that we can determine * the wakeup(s) to perform. */ - waiter =3D rwsem_first_waiter(sem); + waiter =3D sem->first_waiter; =20 if (waiter->type =3D=3D RWSEM_WAITING_FOR_WRITE) { if (wake_type =3D=3D RWSEM_WAKE_ANY) { @@ -506,25 +521,28 @@ static void rwsem_mark_wake(struct rw_semaphore *sem, * 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) { + do { + next =3D next_waiter(sem, waiter); if (waiter->type =3D=3D RWSEM_WAITING_FOR_WRITE) continue; =20 woken++; list_move_tail(&waiter->list, &wlist); + if (sem->first_waiter =3D=3D waiter) + sem->first_waiter =3D next; =20 /* * Limit # of readers that can be woken up per wakeup call. */ if (unlikely(woken >=3D MAX_READERS_WAKEUP)) break; - } + } while ((waiter =3D next) !=3D NULL); =20 adjustment =3D woken * RWSEM_READER_BIAS - adjustment; lockevent_cond_inc(rwsem_wake_reader, woken); =20 oldcount =3D atomic_long_read(&sem->count); - if (list_empty(&sem->wait_list)) { + if (!sem->first_waiter) { /* * Combined with list_move_tail() above, this implies * rwsem_del_waiter(). @@ -545,7 +563,7 @@ static void rwsem_mark_wake(struct rw_semaphore *sem, atomic_long_add(adjustment, &sem->count); =20 /* 2nd pass */ - list_for_each_entry_safe(waiter, tmp, &wlist, list) { + list_for_each_entry_safe(waiter, next, &wlist, list) { struct task_struct *tsk; =20 tsk =3D waiter->task; @@ -577,7 +595,7 @@ rwsem_del_wake_waiter(struct rw_semaphore *sem, struct = rwsem_waiter *waiter, struct wake_q_head *wake_q) __releases(&sem->wait_lock) { - bool first =3D rwsem_first_waiter(sem) =3D=3D waiter; + bool first =3D sem->first_waiter =3D=3D waiter; =20 wake_q_init(wake_q); =20 @@ -603,7 +621,7 @@ rwsem_del_wake_waiter(struct rw_semaphore *sem, struct = rwsem_waiter *waiter, static inline bool rwsem_try_write_lock(struct rw_semaphore *sem, struct rwsem_waiter *waiter) { - struct rwsem_waiter *first =3D rwsem_first_waiter(sem); + struct rwsem_waiter *first =3D sem->first_waiter; long count, new; =20 lockdep_assert_held(&sem->wait_lock); @@ -639,7 +657,7 @@ static inline bool rwsem_try_write_lock(struct rw_semap= hore *sem, new |=3D RWSEM_WRITER_LOCKED; new &=3D ~RWSEM_FLAG_HANDOFF; =20 - if (list_is_singular(&sem->wait_list)) + if (list_empty(&first->list)) new &=3D ~RWSEM_FLAG_WAITERS; } } while (!atomic_long_try_cmpxchg_acquire(&sem->count, &count, new)); @@ -659,7 +677,8 @@ static inline bool rwsem_try_write_lock(struct rw_semap= hore *sem, * Have rwsem_try_write_lock() fully imply rwsem_del_waiter() on * success. */ - list_del(&waiter->list); + __rwsem_del_waiter(sem, waiter); + rwsem_set_owner(sem); return true; } @@ -994,7 +1013,7 @@ rwsem_down_read_slowpath(struct rw_semaphore *sem, lon= g count, unsigned int stat { long adjustment =3D -RWSEM_READER_BIAS; long rcnt =3D (count >> RWSEM_READER_SHIFT); - struct rwsem_waiter waiter; + struct rwsem_waiter waiter, *first; DEFINE_WAKE_Q(wake_q); =20 /* @@ -1019,7 +1038,7 @@ rwsem_down_read_slowpath(struct rw_semaphore *sem, lo= ng count, unsigned int stat */ if ((rcnt =3D=3D 1) && (count & RWSEM_FLAG_WAITERS)) { raw_spin_lock_irq(&sem->wait_lock); - if (!list_empty(&sem->wait_list)) + if (sem->first_waiter) rwsem_mark_wake(sem, RWSEM_WAKE_READ_OWNED, &wake_q); raw_spin_unlock_irq(&sem->wait_lock); @@ -1035,7 +1054,8 @@ rwsem_down_read_slowpath(struct rw_semaphore *sem, lo= ng count, unsigned int stat waiter.handoff_set =3D false; =20 raw_spin_lock_irq(&sem->wait_lock); - if (list_empty(&sem->wait_list)) { + first =3D sem->first_waiter; + if (!first) { /* * In case the wait queue is empty and the lock isn't owned * by a writer, this reader can exit the slowpath and return @@ -1051,8 +1071,11 @@ rwsem_down_read_slowpath(struct rw_semaphore *sem, l= ong count, unsigned int stat return sem; } adjustment +=3D RWSEM_FLAG_WAITERS; + INIT_LIST_HEAD(&waiter.list); + sem->first_waiter =3D &waiter; + } else { + list_add_tail(&waiter.list, &first->list); } - rwsem_add_waiter(sem, &waiter); =20 /* we're now waiting on the lock, but no longer actively locking */ count =3D atomic_long_add_return(adjustment, &sem->count); @@ -1110,7 +1133,7 @@ rwsem_down_read_slowpath(struct rw_semaphore *sem, lo= ng count, unsigned int stat static struct rw_semaphore __sched * rwsem_down_write_slowpath(struct rw_semaphore *sem, int state) { - struct rwsem_waiter waiter; + struct rwsem_waiter waiter, *first; DEFINE_WAKE_Q(wake_q); =20 /* do optimistic spinning and steal lock if possible */ @@ -1129,10 +1152,10 @@ rwsem_down_write_slowpath(struct rw_semaphore *sem,= int state) waiter.handoff_set =3D false; =20 raw_spin_lock_irq(&sem->wait_lock); - rwsem_add_waiter(sem, &waiter); =20 - /* we're now waiting on the lock */ - if (rwsem_first_waiter(sem) !=3D &waiter) { + first =3D sem->first_waiter; + if (first) { + list_add_tail(&waiter.list, &first->list); rwsem_cond_wake_waiter(sem, atomic_long_read(&sem->count), &wake_q); if (!wake_q_empty(&wake_q)) { @@ -1145,6 +1168,8 @@ rwsem_down_write_slowpath(struct rw_semaphore *sem, i= nt state) raw_spin_lock_irq(&sem->wait_lock); } } else { + INIT_LIST_HEAD(&waiter.list); + sem->first_waiter =3D &waiter; atomic_long_or(RWSEM_FLAG_WAITERS, &sem->count); } =20 @@ -1218,7 +1243,7 @@ static struct rw_semaphore *rwsem_wake(struct rw_sema= phore *sem) =20 raw_spin_lock_irqsave(&sem->wait_lock, flags); =20 - if (!list_empty(&sem->wait_list)) + if (sem->first_waiter) rwsem_mark_wake(sem, RWSEM_WAKE_ANY, &wake_q); =20 raw_spin_unlock_irqrestore(&sem->wait_lock, flags); @@ -1239,7 +1264,7 @@ static struct rw_semaphore *rwsem_downgrade_wake(stru= ct rw_semaphore *sem) =20 raw_spin_lock_irqsave(&sem->wait_lock, flags); =20 - if (!list_empty(&sem->wait_list)) + if (sem->first_waiter) rwsem_mark_wake(sem, RWSEM_WAKE_READ_OWNED, &wake_q); =20 raw_spin_unlock_irqrestore(&sem->wait_lock, flags); --=20 2.47.3