[PATCH v2 1/2] locking/rtmutex: Handle empty waiters tree in try_to_take_rt_mutex()

[PATCH v2 1/2] locking/rtmutex: Handle empty waiters tree in try_to_take_rt_mutex()

[Quchaosheng]

The waiter branch of try_to_take_rt_mutex() reads the top waiter from the
lock waiters tree and passes it to rt_mutex_steal() without checking that
the tree still has waiters.

rt_mutex_slowlock_block() calls try_to_take_rt_mutex() in a loop with a
waiter that was enqueued before the loop.  The loop drops wait_lock around
rt_mutex_schedule(), so another task can acquire and release the lock and
dequeue the waiter in the meantime.  The loop then calls
try_to_take_rt_mutex() again with a waiter that is no longer part of the
waiters tree.

With an empty waiters tree, rt_mutex_top_waiter() returns NULL, so
rt_mutex_steal() dereferences a NULL rt_waiter_node and reads tree.prio at
offset 0x18.  syzbot reports this as a general protection fault in
try_to_take_rt_mutex on PREEMPT_RT:

  general protection fault, probably for non-canonical address
  0xdffffc0000000003
  KASAN: null-ptr-deref in range [0x18-0x1f]
  RIP: 0010:try_to_take_rt_mutex+0x177/0xac0 kernel/locking/rtmutex.c:1138
  Call Trace:
   __rt_mutex_slowlock_locked+0x1fe5/0x25b0
   __rwbase_read_lock+0xc3/0x190
   down_read+0x132/0x200
   inode_lock_shared
   lookup_slow+0x46/0x70
   link_path_walk+0xd2a/0x1910
   path_openat+0x1ce/0x1d60

Take the lock and skip the steal attempt when the waiters tree is empty.
rt_mutex_owner() was already checked above, so the lock is free and the
waiter is the only candidate.  rt_mutex_dequeue() already returns early for
a waiter that is not queued, so the skipped call is a no-op, and
rt_mutex_set_owner() clears the transient RT_MUTEX_HAS_WAITERS state.  The
waiter == NULL branch handles an empty tree the same way.

Reported-by: syzbot+917245f59371bf1d27f7@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=917245f59371bf1d27f7
Signed-off-by: Quchaosheng <quchaosheng000406@163.com>
---
v2:
 - Reword the comment to "may have been dequeued" (Waiman Long).
   "can have been" is unusual; upstream uses "may have been" for this.
 - No functional change.

 kernel/locking/rtmutex.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 4728631ae..4a6b22027 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -1131,6 +1131,16 @@ try_to_take_rt_mutex(struct rt_mutex_base *lock, struct task_struct *task,
 	if (waiter) {
 		struct rt_mutex_waiter *top_waiter = rt_mutex_top_waiter(lock);
 
+		/*
+		 * The waiter may have been dequeued while the lock was
+		 * dropped. In that case the waiters tree is empty and
+		 * top_waiter is NULL, so there is nothing to steal from.
+		 * Take the lock and leave the transient state to
+		 * rt_mutex_set_owner() below.
+		 */
+		if (!top_waiter)
+			goto takeit;
+
 		/*
 		 * If waiter is the highest priority waiter of @lock,
 		 * or allowed to steal it, take it over.

[PATCH v3] locking/rtmutex: Handle empty waiters tree in try_to_take_rt_mutex()

[Quchaosheng]

The waiter branch of try_to_take_rt_mutex() reads the top waiter from the
lock waiters tree and passes it to rt_mutex_steal() without checking that
the tree still has waiters.

rt_mutex_slowlock_block() calls try_to_take_rt_mutex() in a loop with a
waiter that was enqueued before the loop.  The loop drops wait_lock around
rt_mutex_schedule(), so another task can acquire and release the lock and
dequeue the waiter in the meantime.  The loop then calls
try_to_take_rt_mutex() again with a waiter that is no longer part of the
waiters tree.

With an empty waiters tree, rt_mutex_top_waiter() returns NULL, so
rt_mutex_steal() dereferences a NULL rt_waiter_node and reads tree.prio at
offset 0x18.  syzbot reports this as a general protection fault in
try_to_take_rt_mutex on PREEMPT_RT:

  general protection fault, probably for non-canonical address
  0xdffffc0000000003
  KASAN: null-ptr-deref in range [0x18-0x1f]
  RIP: 0010:try_to_take_rt_mutex+0x177/0xac0 kernel/locking/rtmutex.c:1138
  Call Trace:
   __rt_mutex_slowlock_locked+0x1fe5/0x25b0
   __rwbase_read_lock+0xc3/0x190
   down_read+0x132/0x200
   inode_lock_shared
   lookup_slow+0x46/0x70
   link_path_walk+0xd2a/0x1910
   path_openat+0x1ce/0x1d60

Take the lock and skip the steal attempt when the waiters tree is empty.
rt_mutex_owner() was already checked above, so the lock is free and the
waiter is the only candidate.  rt_mutex_dequeue() already returns early for
a waiter that is not queued, so the skipped call is a no-op, and
rt_mutex_set_owner() clears the transient RT_MUTEX_HAS_WAITERS state.  The
waiter == NULL branch handles an empty tree the same way.

Fixes: 48eb3f4fcfd3 ("locking/rtmutex: Implement equal priority lock stealing")
Reported-by: syzbot+917245f59371bf1d27f7@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=917245f59371bf1d27f7
Signed-off-by: Quchaosheng <quchaosheng000406@163.com>
---
v3: Add the Fixes: tag and use the wording suggested by Waiman Long.
    No functional change.

v2: Reword the comment.  No functional change.

 kernel/locking/rtmutex.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 4728631ae..4a6b22027 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -1131,6 +1131,16 @@ try_to_take_rt_mutex(struct rt_mutex_base *lock, struct task_struct *task,
 	if (waiter) {
 		struct rt_mutex_waiter *top_waiter = rt_mutex_top_waiter(lock);
 
+		/*
+		 * The waiter could have been dequeued while the lock was
+		 * dropped. In that case the waiters tree is empty and
+		 * top_waiter is NULL, so there is nothing to steal from.
+		 * Take the lock and leave the transient state to
+		 * rt_mutex_set_owner() below.
+		 */
+		if (!top_waiter)
+			goto takeit;
+
 		/*
 		 * If waiter is the highest priority waiter of @lock,
 		 * or allowed to steal it, take it over.
-- 
2.43.0

Re: [PATCH v3] locking/rtmutex: Handle empty waiters tree in try_to_take_rt_mutex()

[Waiman Long]

On 9/16/26 3:33 AM, Quchaosheng wrote:
> The waiter branch of try_to_take_rt_mutex() reads the top waiter from the
> lock waiters tree and passes it to rt_mutex_steal() without checking that
> the tree still has waiters.
>
> rt_mutex_slowlock_block() calls try_to_take_rt_mutex() in a loop with a
> waiter that was enqueued before the loop.  The loop drops wait_lock around
> rt_mutex_schedule(), so another task can acquire and release the lock and
> dequeue the waiter in the meantime.  The loop then calls
> try_to_take_rt_mutex() again with a waiter that is no longer part of the
> waiters tree.
>
> With an empty waiters tree, rt_mutex_top_waiter() returns NULL, so
> rt_mutex_steal() dereferences a NULL rt_waiter_node and reads tree.prio at
> offset 0x18.  syzbot reports this as a general protection fault in
> try_to_take_rt_mutex on PREEMPT_RT:
>
>    general protection fault, probably for non-canonical address
>    0xdffffc0000000003
>    KASAN: null-ptr-deref in range [0x18-0x1f]
>    RIP: 0010:try_to_take_rt_mutex+0x177/0xac0 kernel/locking/rtmutex.c:1138
>    Call Trace:
>     __rt_mutex_slowlock_locked+0x1fe5/0x25b0
>     __rwbase_read_lock+0xc3/0x190
>     down_read+0x132/0x200
>     inode_lock_shared
>     lookup_slow+0x46/0x70
>     link_path_walk+0xd2a/0x1910
>     path_openat+0x1ce/0x1d60
>
> Take the lock and skip the steal attempt when the waiters tree is empty.
> rt_mutex_owner() was already checked above, so the lock is free and the
> waiter is the only candidate.  rt_mutex_dequeue() already returns early for
> a waiter that is not queued, so the skipped call is a no-op, and
> rt_mutex_set_owner() clears the transient RT_MUTEX_HAS_WAITERS state.  The
> waiter == NULL branch handles an empty tree the same way.
>
> Fixes: 48eb3f4fcfd3 ("locking/rtmutex: Implement equal priority lock stealing")
> Reported-by: syzbot+917245f59371bf1d27f7@syzkaller.appspotmail.com
> Closes: https://syzkaller.appspot.com/bug?extid=917245f59371bf1d27f7
> Signed-off-by: Quchaosheng <quchaosheng000406@163.com>
> ---
> v3: Add the Fixes: tag and use the wording suggested by Waiman Long.
>      No functional change.
>
> v2: Reword the comment.  No functional change.
>
>   kernel/locking/rtmutex.c | 10 ++++++++++
>   1 file changed, 10 insertions(+)
>
> diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
> index 4728631ae..4a6b22027 100644
> --- a/kernel/locking/rtmutex.c
> +++ b/kernel/locking/rtmutex.c
> @@ -1131,6 +1131,16 @@ try_to_take_rt_mutex(struct rt_mutex_base *lock, struct task_struct *task,
>   	if (waiter) {
>   		struct rt_mutex_waiter *top_waiter = rt_mutex_top_waiter(lock);
>   
> +		/*
> +		 * The waiter could have been dequeued while the lock was
> +		 * dropped. In that case the waiters tree is empty and
> +		 * top_waiter is NULL, so there is nothing to steal from.
> +		 * Take the lock and leave the transient state to
> +		 * rt_mutex_set_owner() below.
> +		 */
> +		if (!top_waiter)
> +			goto takeit;
> +
>   		/*
>   		 * If waiter is the highest priority waiter of @lock,
>   		 * or allowed to steal it, take it over.

Nit: It does not clearly state the top_waiter cannot be NULL when the 
given waiter is NULL. So NULL check isn't required in the else branch.

Anyway, the change makes sense.

Reviewed-by: Waiman Long <longman@redhat.com>

[PATCH v4] locking/rtmutex: Handle empty waiters tree in try_to_take_rt_mutex()

[Quchaosheng]

The waiter branch of try_to_take_rt_mutex() reads the top waiter from the
lock waiters tree and passes it to rt_mutex_steal() without checking that
the tree still has waiters.

rt_mutex_slowlock_block() calls try_to_take_rt_mutex() in a loop with a
waiter that was enqueued before the loop.  The loop drops wait_lock around
rt_mutex_schedule(), so another task can acquire and release the lock and
dequeue the waiter in the meantime.  The loop then calls
try_to_take_rt_mutex() again with a waiter that is no longer part of the
waiters tree.

With an empty waiters tree, rt_mutex_top_waiter() returns NULL, so
rt_mutex_steal() dereferences a NULL rt_waiter_node and reads tree.prio at
offset 0x18.  syzbot reports this as a general protection fault in
try_to_take_rt_mutex on PREEMPT_RT:

  general protection fault, probably for non-canonical address
  0xdffffc0000000003
  KASAN: null-ptr-deref in range [0x18-0x1f]
  RIP: 0010:try_to_take_rt_mutex+0x177/0xac0 kernel/locking/rtmutex.c:1138
  Call Trace:
   __rt_mutex_slowlock_locked+0x1fe5/0x25b0
   __rwbase_read_lock+0xc3/0x190
   down_read+0x132/0x200
   inode_lock_shared
   lookup_slow+0x46/0x70
   link_path_walk+0xd2a/0x1910
   path_openat+0x1ce/0x1d60

Take the lock and skip the steal attempt when the waiters tree is empty.
rt_mutex_owner() was already checked above, so the lock is free and the
waiter is the only candidate.  rt_mutex_dequeue() already returns early for
a waiter that is not queued, so the skipped call is a no-op, and
rt_mutex_set_owner() clears the transient RT_MUTEX_HAS_WAITERS state.  The
waiter == NULL branch handles an empty tree the same way.

Fixes: 48eb3f4fcfd3 ("locking/rtmutex: Implement equal priority lock stealing")
Reported-by: syzbot+917245f59371bf1d27f7@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=917245f59371bf1d27f7
Assisted-by: LLM
Signed-off-by: Quchaosheng <quchaosheng000406@163.com>
Reviewed-by: Waiman Long <longman@redhat.com>
---
v4: Add the Assisted-by: tag required by coding-assistants.rst, and add the
    Reviewed-by from Waiman Long.  No functional change.

v3: Add the Fixes: tag and use the wording suggested by Waiman Long.
    No functional change.

v2: Reword the comment.  No functional change.

 kernel/locking/rtmutex.c | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 4728631ae..4a6b22027 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -1131,6 +1131,16 @@ try_to_take_rt_mutex(struct rt_mutex_base *lock, struct task_struct *task,
 	if (waiter) {
 		struct rt_mutex_waiter *top_waiter = rt_mutex_top_waiter(lock);
 
+		/*
+		 * The waiter could have been dequeued while the lock was
+		 * dropped. In that case the waiters tree is empty and
+		 * top_waiter is NULL, so there is nothing to steal from.
+		 * Take the lock and leave the transient state to
+		 * rt_mutex_set_owner() below.
+		 */
+		if (!top_waiter)
+			goto takeit;
+
 		/*
 		 * If waiter is the highest priority waiter of @lock,
 		 * or allowed to steal it, take it over.
-- 
2.43.0