Possible race in rt_mutex_adjust_prio_chain

Possible race in rt_mutex_adjust_prio_chain

[Henry Wu]

[-- Attachment #1: Type: text/plain, Size: 5634 bytes --]

Hi,

I found that it's not safe to change waiter->prio after waiter
dequeued from mutex's waiter rbtree because it's still on owner's
pi_waiters rbtree. From my analysis, waiters on pi_waiters rbtree
should be protected by pi_lock of task which have pi_waiters and
corresponding rt_mutex's wait_lock, but pi_waiters is shared by many
locks owned by this task, so actually we serialize changes on
pi_waiters only by pi_lock.

`rt_mutex_adjust_prio_chain' changes key of nodes of pi_waiters rbtree
without pi_lock and pi_waiters rbtree's invariant is violated. Maybe
we are enqueuing waiter on other cpu and pi_waiters rbtree will be
corrupted.

I attach a source file which can trigger this violation. I tested it
on Ubuntu 20.04 LTS with 5.4 kernel.

$ sudo ./a.out
pid: 39949
prio: 39
    PID     LWP TTY          TIME CMD
  39949   39949 pts/1    00:00:00 a.out
  39949   39950 pts/1    00:00:00 waiter-0
  39949   39951 pts/1    00:00:00 waiter-1
.............
prio: 20
prio: 20
prio: 20
prio: 20
prio: 20
prio: 20
prio: 20
.............
prio: 21
prio: 21
prio: 21
prio: 21
prio: 21
prio: 21
prio: 21
prio: 21
prio: 21
prio: 21
prio: 21
    PID     LWP TTY          TIME CMD
  39949   39949 pts/1    00:00:00 a.out
  39949   39950 pts/1    00:00:00 waiter-0
  39949   39951 pts/1    00:00:00 waiter-1
  39949   39952 pts/1    00:00:00 waiter-2
  39949   39953 pts/1    00:00:00 waiter-3
  39949   39954 pts/1    00:00:00 waiter-4
  39949   39955 pts/1    00:00:00 waiter-5
  39949   39956 pts/1    00:00:00 waiter-6
  39949   39957 pts/1    00:00:00 waiter-7
  39949   39958 pts/1    00:00:00 waiter-8
  39949   39959 pts/1    00:00:00 waiter-9
  39949   39960 pts/1    00:00:00 waiter-10
  39949   39961 pts/1    00:00:00 waiter-11
  39949   39962 pts/1    00:00:00 waiter-12
  39949   39963 pts/1    00:00:00 waiter-13
  39949   39964 pts/1    00:00:00 waiter-14
  39949   39965 pts/1    00:00:00 waiter-15
  39949   39966 pts/1    00:00:00 waiter-16
  39949   39967 pts/1    00:00:00 waiter-17
  39949   39968 pts/1    00:00:00 waiter-18
  39949   39969 pts/1    00:00:00 changer-0
  39949   39970 pts/1    00:00:00 changer-1
  39949   39971 pts/1    00:00:00 changer-2
  39949   39972 pts/1    00:00:00 changer-3
  39949   39973 pts/1    00:00:00 changer-4
  39949   39974 pts/1    00:00:00 changer-5
  39949   39975 pts/1    00:00:00 changer-6
  39949   39976 pts/1    00:00:00 changer-7
  39949   39977 pts/1    00:00:00 changer-8
  39949   39978 pts/1    00:00:00 changer-9
  39949   39979 pts/1    00:00:00 changer-10
  39949   39980 pts/1    00:00:00 changer-11
  39949   39981 pts/1    00:00:00 changer-12
  39949   39982 pts/1    00:00:00 changer-13
  39949   39983 pts/1    00:00:00 changer-14
  39949   39984 pts/1    00:00:00 changer-15
  39949   39985 pts/1    00:00:00 changer-16
  39949   39986 pts/1    00:00:00 changer-17
  39949   39987 pts/1    00:00:00 changer-18
found race, hang...

$ crash
crash> task -R prio,normal_prio,pi_waiters 39949
PID: 39949  TASK: ffff956a5c8b2f00  CPU: 2   COMMAND: "a.out"
  prio = 121,
  normal_prio = 139,
  pi_waiters = {
    rb_root = {
      rb_node = 0xffffb24941f43d40
    },
    rb_leftmost = 0xffffb24941f8bd40
  },

crash> print (struct rb_node *)0xffffb24941f43d40
$62 = (struct rb_node *) 0xffffb24941f43d40
crash> print *(struct rt_mutex_waiter *)((void *)$ - 24)
$63 = {
  tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0x0,
    rb_left = 0x0
  },
  pi_tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0xffffb24941f13d40,
    rb_left = 0xffffb24941f4bd40
  },
  task = 0xffff956a6c008000,
  lock = 0xffff956920b80970,
  prio = 130,
  deadline = 0
}
crash> print $62->rb_left
$64 = (struct rb_node *) 0xffffb24941f4bd40
crash> print *(struct rt_mutex_waiter *)((void *)$ - 24)
$65 = {
  tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0x0,
    rb_left = 0x0
  },
  pi_tree_entry = {
    __rb_parent_color = 18446658626441723201,
    rb_right = 0xffffb24941f63d40,
    rb_left = 0xffffb24941f5bd40
  },
  task = 0xffff956a594baf00,
  lock = 0xffff956920b80190,
  prio = 126,
  deadline = 0
}
crash> print $62->rb_left->rb_left
$66 = (struct rb_node *) 0xffffb24941f5bd40
crash> print *(struct rt_mutex_waiter *)((void *)$ - 24)
$67 = {
  tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0x0,
    rb_left = 0x0
  },
  pi_tree_entry = {
    __rb_parent_color = 18446658626441755968,
    rb_right = 0xffffb24941f73d40,
    rb_left = 0xffffb24941f2bd40
  },
  task = 0xffff956a64edaf00,
  lock = 0xffff956a8d481670,
  prio = 123,
  deadline = 0
}
crash> print $62->rb_left->rb_left->rb_left
$68 = (struct rb_node *) 0xffffb24941f2bd40
crash> print *(struct rt_mutex_waiter *)((void *)$ - 24)
$69 = {
  tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0x0,
    rb_left = 0x0
  },
  pi_tree_entry = {
    __rb_parent_color = 18446658626441821505,
    rb_right = 0xffffb24940e47d40,
    rb_left = 0xffffb24941f8bd40
  },
  task = 0xffff956a62ae0000,
  lock = 0xffff956a76c5c250,
  prio = 120,
  deadline = 0
}
crash> print $62->rb_left->rb_left->rb_left->rb_left
$70 = (struct rb_node *) 0xffffb24941f8bd40
crash> print *(struct rt_mutex_waiter *)((void *)$ - 24)
$71 = {
  tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0x0,
    rb_left = 0x0
  },
  pi_tree_entry = {
    __rb_parent_color = 18446658626441624896,
    rb_right = 0x0,
    rb_left = 0x0
  },
  task = 0xffff956a597dc680,
  lock = 0xffff956920b802b0,
  prio = 121,
  deadline = 0
}
crash>

From the last two rt_mutex_waiter we see that leftmost waiter's prio
is 121 but it's parent is 120.

Sorry for the inconvenience if I made a mistake. Thanks!

Henry

[-- Attachment #2: pi.c --]
[-- Type: text/x-csrc, Size: 5424 bytes --]

#define _GNU_SOURCE

#include <assert.h>
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <sched.h>
#include <errno.h>
#include <sys/syscall.h>

#define PCOUNT 19

// Copied from related header.
struct sched_attr {
	uint32_t size;

	uint32_t sched_policy;
	uint64_t sched_flags;

	/* SCHED_NORMAL, SCHED_BATCH */
	int32_t sched_nice;

	/* SCHED_FIFO, SCHED_RR */
	uint32_t sched_priority;

	/* SCHED_DEADLINE */
	uint64_t sched_runtime;
	uint64_t sched_deadline;
	uint64_t sched_period;

	/* Utilization hints */
	uint32_t sched_util_min;
	uint32_t sched_util_max;
};

static pthread_mutex_t mutexes[PCOUNT];

static void init_mutex(pthread_mutex_t *mutex) {
	pthread_mutexattr_t attr;
	int ret;

	ret = pthread_mutexattr_init(&attr);
	assert(!ret);
	ret = pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
	assert(!ret);

	ret = pthread_mutex_init(mutex, &attr);
	assert(!ret);

	pthread_mutexattr_destroy(&attr);
}

enum thread_type {
	WAITER,
	PRIO_CHANGER,
};

static struct thread_spec {
	enum thread_type type;
	int name_index;
	int nice;
	pthread_barrier_t *barrier;

	// Used by waiter.
	pthread_mutex_t *wait_mutex;
	pid_t pid_save;
	
	// Used by prio changer.
	pid_t *waiter_pid;
} thread_specs[PCOUNT * 2];

static pthread_t threads[PCOUNT * 2];
static int thread_count = 0;

static int barrier_wait(pthread_barrier_t *barrier) {
	if (!barrier) {
		return 0;
	}

	int ret = pthread_barrier_wait(barrier);
	assert(!ret || ret == PTHREAD_BARRIER_SERIAL_THREAD);

	return ret;
}

static int sched_getattr(pid_t pid, struct sched_attr *attr, int flags) {
	return syscall(SYS_sched_getattr, pid, attr, sizeof(*attr), flags);
}

static int sched_setattr(pid_t pid, struct sched_attr *attr, int flags) {
	return syscall(SYS_sched_setattr, pid, attr, flags);
}

static void *prio_change_loop(struct thread_spec *spec) {
	struct sched_attr attr;
	int ret;

	for (;;) {
		barrier_wait(spec->barrier);

		ret = sched_getattr(*spec->waiter_pid, &attr, 0);
		if (ret < 0) {
			perror("sched_getattr");
			assert(0);
		}
		
		attr.sched_nice = spec->nice;
	
		ret = sched_setattr(*spec->waiter_pid, &attr, 0);
		if (ret < 0) {
			perror("sched_setattr");
			exit(1);
		}

		barrier_wait(spec->barrier);
	}
}

static void *thread(void *arg) {
	struct thread_spec *spec = arg;
	char name[64];
	int ret;
	
	snprintf(name, sizeof(name), "%s-%d", 
			spec->type == WAITER ? "waiter" : "changer", 
			spec->name_index);
	ret = pthread_setname_np(pthread_self(), name);
	assert(!ret);

	switch (spec->type) {
	case WAITER:
		spec->pid_save = gettid();

		barrier_wait(spec->barrier);

		ret = nice(spec->nice);
		assert(ret >= 0);

		ret = pthread_mutex_lock(spec->wait_mutex);
		assert(!ret);
		break;
	case PRIO_CHANGER:
		prio_change_loop(spec);
		break;
	default:
		assert(0);
		break;
	}

	return NULL;
}

static void create_thread(struct thread_spec *spec) {
	int ret;

	ret = pthread_create(&threads[thread_count++], NULL, thread, spec);
	assert(!ret);
}

static int print_prio() {
	FILE *file = fopen("/proc/self/stat", "r");
	assert(file);

	char comm[64];
	int tmp, prio, ret;
	ret = fscanf(file, "%d %s %c %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d",
			&tmp, comm, comm, &tmp, &tmp, &tmp, &tmp, &tmp, &tmp,
			&tmp, &tmp, &tmp, &tmp, &tmp, &tmp, &tmp, &tmp, &prio);
	assert(ret == 18);

	printf("prio: %d\n", prio);

	fclose(file);

	return prio;
}

static void print_threads(pid_t process_pid) {
	char cmd[128];
	snprintf(cmd, sizeof(cmd), "ps -L -p %d", process_pid);
	system(cmd);
}

int main(void) {
	pid_t pid;
	int ret;

	pid = getpid();
	printf("pid: %d\n", pid);

	for (int i = 0; i < sizeof(mutexes) / sizeof(mutexes[0]); ++i) {
		init_mutex(&mutexes[i]);
		ret = pthread_mutex_lock(&mutexes[i]);
		assert(!ret);
	}

	pthread_barrier_t barrier;
	ret = pthread_barrier_init(&barrier, NULL, PCOUNT + 1);
	assert(!ret);

	for (int i = 0; i < PCOUNT; ++i) {
		struct thread_spec *spec = &thread_specs[i];
		
		spec->type = WAITER;
		spec->name_index = i;
		spec->nice = 18;
		spec->wait_mutex = &mutexes[i];
		spec->barrier = &barrier;

		create_thread(spec);
	}

	// Wait for filling of pid_save.
	barrier_wait(&barrier);

	for (int i = 0; i < PCOUNT; ++i) {
		struct thread_spec *spec = &thread_specs[i + 19];

		spec->type = PRIO_CHANGER; 
		spec->name_index = i;
		spec->nice = 0;
		spec->barrier = &barrier;
		spec->waiter_pid = &thread_specs[i].pid_save;

		create_thread(spec);
	}

	nice(19);

	print_prio();
	print_threads(pid);

	//sleep(60);
	//printf("launch!\n");

	srandom(time(NULL));
	int iter = 0;
	for (;;) {
		++iter;
		for (int i = 0; i < PCOUNT; ++i) {
			thread_specs[i + 19].nice = (iter % 2) ? i : 18 - i;
		}

		for (int i = 0; i < PCOUNT; ++i) {
			int pos = random() % PCOUNT;
			int tmp = thread_specs[pos + 19].nice;
			thread_specs[pos + 19].nice = thread_specs[19].nice;
			thread_specs[19].nice = tmp;
		}

		barrier_wait(&barrier);
		barrier_wait(&barrier);

		//system("echo iteration > /sys/kernel/debug/tracing/trace_marker");

		int prio, unexpected_times = 0;
		do {
			prio = print_prio();
			if (prio != 20) {
				++unexpected_times;
				if (unexpected_times > 10) {
					print_threads(pid);
					printf("found race, hang...\n");
					while (1) {
						sleep(3600);
					}
				}
			}
		} while (prio != 20);
	}

	for (int i = 0; i < thread_count; ++i) {
		pthread_join(threads[i], NULL);
	}

	return 0;
}

Re: Possible race in rt_mutex_adjust_prio_chain

[Peter Zijlstra]

On Thu, Jul 06, 2023 at 02:08:20PM +0800, Henry Wu wrote:
> Hi,
> 
> I found that it's not safe to change waiter->prio after waiter
> dequeued from mutex's waiter rbtree because it's still on owner's
> pi_waiters rbtree. From my analysis, waiters on pi_waiters rbtree
> should be protected by pi_lock of task which have pi_waiters and
> corresponding rt_mutex's wait_lock, but pi_waiters is shared by many
> locks owned by this task, so actually we serialize changes on
> pi_waiters only by pi_lock.
> 
> `rt_mutex_adjust_prio_chain' changes key of nodes of pi_waiters rbtree
> without pi_lock and pi_waiters rbtree's invariant is violated. Maybe
> we are enqueuing waiter on other cpu and pi_waiters rbtree will be
> corrupted.

Are you talking about [7];

Where we do waiter_update_prio() while only
holding [L] rtmutex->wait_lock.

VS

rt_mutex_adjust_prio() / task_top_pi_waiter() that accesses ->pi_waiters
while holding [P] task->pi_lock.

?

I'll go stare at that in more detail -- but I wanted to verify that's
what you're talking about.

> I attach a source file which can trigger this violation. I tested it
> on Ubuntu 20.04 LTS with 5.4 kernel.

Well, that's a horribly old kernel :-( Please double check on v6.4 and
consult that code for the discussion above -- I'm really not too
interested in debugging something ancient.

Re: Possible race in rt_mutex_adjust_prio_chain

[Peter Zijlstra]

On Thu, Jul 06, 2023 at 02:01:03PM +0200, Peter Zijlstra wrote:
> On Thu, Jul 06, 2023 at 02:08:20PM +0800, Henry Wu wrote:
> > Hi,
> > 
> > I found that it's not safe to change waiter->prio after waiter
> > dequeued from mutex's waiter rbtree because it's still on owner's
> > pi_waiters rbtree. From my analysis, waiters on pi_waiters rbtree
> > should be protected by pi_lock of task which have pi_waiters and
> > corresponding rt_mutex's wait_lock, but pi_waiters is shared by many
> > locks owned by this task, so actually we serialize changes on
> > pi_waiters only by pi_lock.
> > 
> > `rt_mutex_adjust_prio_chain' changes key of nodes of pi_waiters rbtree
> > without pi_lock and pi_waiters rbtree's invariant is violated. Maybe
> > we are enqueuing waiter on other cpu and pi_waiters rbtree will be
> > corrupted.
> 
> Are you talking about [7];
> 
> Where we do waiter_update_prio() while only
> holding [L] rtmutex->wait_lock.
> 
> VS
> 
> rt_mutex_adjust_prio() / task_top_pi_waiter() that accesses ->pi_waiters
> while holding [P] task->pi_lock.
> 
> ?
> 
> I'll go stare at that in more detail -- but I wanted to verify that's
> what you're talking about.

Current notes...

We hold [L] from 5-13; we hold [P1] 1-8 and [P2] 10-13

  P1 - blocked task
  P2 - lock owner

  7  holds [L]+[P1]
     modifies the values, which, temporarily, messes up the pi_waiters tree

  11 holds [L]+[P2]
     requeues the waiter on pi_waiter, restoring pi_waiters tree

pi_waiters is modified by:

  - rt_mutex_{en,de}queue_pi(); which are used:

   - [11] (holds [L]+[P2])
   - try_to_wake_rt_mutex() [L]+[P3] ?!? (P3 will be owner,
					  but is not yet)
   - task_blocks_on_rt_mutex() [L]+[P2]
   - mark_wakeup_next_waiter() [L]+[P2] (current is owner,
					 gives up lock)
   - remove_waiter() [L]+[P2]

pi_waiters is used by:

  - task_top_pi_waiter(), asserts [P], this is used:

    - rt_mutex_adjust_prio(), which asserts [P2] (*), is used:

      - [11] (holds [L])
      - task_blocks_on_rt_mutex() (holds [L])
      - mark_wakeup_next_waiter() (holds [L])
      - remove_waiter() (holds [L])

      (*)(see patch below -- adding more assertions)

    - [3] -- does *NOT* hold [L], does hold [P]


Now, [3] doesn't hold [L], but since 'all' modifications are done under
[L]+[P], just holding [P] should provide a stable read. Except [7], that
messes up the tree while not holding (the right!) [P].

It's late, I'll have to continue staring at this tomorrow!


---
 kernel/locking/rtmutex.c        | 17 +++++++++++------
 kernel/locking/rtmutex_common.h |  1 +
 2 files changed, 12 insertions(+), 6 deletions(-)

diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 728f434de2bb..ff64054fc24c 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -472,10 +472,13 @@ rt_mutex_dequeue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
 	RB_CLEAR_NODE(&waiter->pi_tree_entry);
 }
 
-static __always_inline void rt_mutex_adjust_prio(struct task_struct *p)
+static __always_inline void rt_mutex_adjust_prio(struct rt_mutex_base *lock,
+						 struct task_struct *p)
 {
 	struct task_struct *pi_task = NULL;
 
+	lockdep_assert_held(&lock->wait_lock);
+	lockdep_assert(rt_mutex_owner(lock) == p);
 	lockdep_assert_held(&p->pi_lock);
 
 	if (task_has_pi_waiters(p))
@@ -922,7 +925,7 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
 		 */
 		rt_mutex_dequeue_pi(task, prerequeue_top_waiter);
 		rt_mutex_enqueue_pi(task, waiter);
-		rt_mutex_adjust_prio(task);
+		rt_mutex_adjust_prio(lock, task);
 
 	} else if (prerequeue_top_waiter == waiter) {
 		/*
@@ -938,7 +941,7 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
 		rt_mutex_dequeue_pi(task, waiter);
 		waiter = rt_mutex_top_waiter(lock);
 		rt_mutex_enqueue_pi(task, waiter);
-		rt_mutex_adjust_prio(task);
+		rt_mutex_adjust_prio(lock, task);
 	} else {
 		/*
 		 * Nothing changed. No need to do any priority
@@ -1187,7 +1190,7 @@ static int __sched task_blocks_on_rt_mutex(struct rt_mutex_base *lock,
 		rt_mutex_dequeue_pi(owner, top_waiter);
 		rt_mutex_enqueue_pi(owner, waiter);
 
-		rt_mutex_adjust_prio(owner);
+		rt_mutex_adjust_prio(lock, owner);
 		if (owner->pi_blocked_on)
 			chain_walk = 1;
 	} else if (rt_mutex_cond_detect_deadlock(waiter, chwalk)) {
@@ -1234,6 +1237,8 @@ static void __sched mark_wakeup_next_waiter(struct rt_wake_q_head *wqh,
 {
 	struct rt_mutex_waiter *waiter;
 
+	lockdep_assert_held(&lock->wait_lock);
+
 	raw_spin_lock(&current->pi_lock);
 
 	waiter = rt_mutex_top_waiter(lock);
@@ -1246,7 +1251,7 @@ static void __sched mark_wakeup_next_waiter(struct rt_wake_q_head *wqh,
 	 * task unblocks.
 	 */
 	rt_mutex_dequeue_pi(current, waiter);
-	rt_mutex_adjust_prio(current);
+	rt_mutex_adjust_prio(lock, current);
 
 	/*
 	 * As we are waking up the top waiter, and the waiter stays
@@ -1482,7 +1487,7 @@ static void __sched remove_waiter(struct rt_mutex_base *lock,
 	if (rt_mutex_has_waiters(lock))
 		rt_mutex_enqueue_pi(owner, rt_mutex_top_waiter(lock));
 
-	rt_mutex_adjust_prio(owner);
+	rt_mutex_adjust_prio(lock, owner);
 
 	/* Store the lock on which owner is blocked or NULL */
 	next_lock = task_blocked_on_lock(owner);
diff --git a/kernel/locking/rtmutex_common.h b/kernel/locking/rtmutex_common.h
index c47e8361bfb5..a71cd0f2eea9 100644
--- a/kernel/locking/rtmutex_common.h
+++ b/kernel/locking/rtmutex_common.h
@@ -127,6 +127,7 @@ static inline int task_has_pi_waiters(struct task_struct *p)
 
 static inline struct rt_mutex_waiter *task_top_pi_waiter(struct task_struct *p)
 {
+	lockdep_assert_held(&p->pi_lock);
 	return rb_entry(p->pi_waiters.rb_leftmost, struct rt_mutex_waiter,
 			pi_tree_entry);
 }

Re: Possible race in rt_mutex_adjust_prio_chain

[Henry Wu]

Hi, Peter.

Peter Zijlstra <peterz@infradead.org> 于2023年7月7日周五 03:58写道：
>
> Current notes...
>
> We hold [L] from 5-13; we hold [P1] 1-8 and [P2] 10-13
>
>   P1 - blocked task
>   P2 - lock owner
>
>   7  holds [L]+[P1]
>      modifies the values, which, temporarily, messes up the pi_waiters tree
>
>   11 holds [L]+[P2]
>      requeues the waiter on pi_waiter, restoring pi_waiters tree
>
> pi_waiters is modified by:
>
>   - rt_mutex_{en,de}queue_pi(); which are used:
>
>    - [11] (holds [L]+[P2])
>    - try_to_wake_rt_mutex() [L]+[P3] ?!? (P3 will be owner,
>                                           but is not yet)
>    - task_blocks_on_rt_mutex() [L]+[P2]
>    - mark_wakeup_next_waiter() [L]+[P2] (current is owner,
>                                          gives up lock)
>    - remove_waiter() [L]+[P2]
>
> pi_waiters is used by:
>
>   - task_top_pi_waiter(), asserts [P], this is used:
>
>     - rt_mutex_adjust_prio(), which asserts [P2] (*), is used:
>
>       - [11] (holds [L])
>       - task_blocks_on_rt_mutex() (holds [L])
>       - mark_wakeup_next_waiter() (holds [L])
>       - remove_waiter() (holds [L])
>
>       (*)(see patch below -- adding more assertions)
>
>     - [3] -- does *NOT* hold [L], does hold [P]
>
>
> Now, [3] doesn't hold [L], but since 'all' modifications are done under
> [L]+[P], just holding [P] should provide a stable read. Except [7], that
> messes up the tree while not holding (the right!) [P].
>
> It's late, I'll have to continue staring at this tomorrow!
>

Your analysis is correct! I try to quote part of my previous reply
with correct format:

CPU0                              CPU1
.........                         ..........
                                  rt_mutex_adjust_prio_chain(C)
rt_mutex_adjust_prio_chain(B)
......
[7] update waiter->prio
(Now A's pi_waiters rbtree is
 corrupted temporarily)
......                            [11] enqueue operation may select
                                  insert position according to corrupted
                                  waiter node CPU0 created.
[11] Even though we fixed
corrupted waiter now, we
are not sure about pi_waiters's
sanity because other cpu may
create new invariant violation
based on our violation.

Fwd: Possible race in rt_mutex_adjust_prio_chain

[Henry Wu]

[-- Attachment #1: Type: text/plain, Size: 7482 bytes --]

I forget to CC linux-kernel, sorry for duplicate mail.

Hi, Peter.

Peter Zijlstra <peterz@infradead.org> 于2023年7月6日周四 20:01写道：
>
> On Thu, Jul 06, 2023 at 02:08:20PM +0800, Henry Wu wrote:
> > Hi,
> >
> > I found that it's not safe to change waiter->prio after waiter
> > dequeued from mutex's waiter rbtree because it's still on owner's
> > pi_waiters rbtree. From my analysis, waiters on pi_waiters rbtree
> > should be protected by pi_lock of task which have pi_waiters and
> > corresponding rt_mutex's wait_lock, but pi_waiters is shared by many
> > locks owned by this task, so actually we serialize changes on
> > pi_waiters only by pi_lock.
> >
> > `rt_mutex_adjust_prio_chain' changes key of nodes of pi_waiters rbtree
> > without pi_lock and pi_waiters rbtree's invariant is violated. Maybe
> > we are enqueuing waiter on other cpu and pi_waiters rbtree will be
> > corrupted.
>
> Are you talking about [7];
>
> Where we do waiter_update_prio() while only
> holding [L] rtmutex->wait_lock.
>
> VS
>
> rt_mutex_adjust_prio() / task_top_pi_waiter() that accesses ->pi_waiters
> while holding [P] task->pi_lock.
>
> ?
>
> I'll go stare at that in more detail -- but I wanted to verify that's
> what you're talking about.
>

I refered step 7. I checked every call site of rt_mutex_adjust_prio()
and all of them are protected by the right pi_lock.

Imagine a scenario that we have two rt_mutex (M1, M2) and three
threads (A, B, C). Both rt_mutex are owned by thread A. B is blocked
when acquiring M1 and C is blocked when acquiring M2. We use
sched_setattr to change priority of B and C.

CPU0                                             CPU1
.........                                              ..........

rt_mutex_adjust_prio_chain(C)
rt_mutex_adjust_prio_chain(B)
......
[7] update waiter->prio
(Now A's pi_waiters rbtree is
 corrupted temporarily)
......                                                 [11] enqueue
operation may select
                                                       insert position
according to corrupted
                                                       waiter node CPU0 created.
[11] Even though we fixed
corrupted waiter now, we
are not sure about pi_waiters's
sanity because other cpu may
create new invariant violation
based on our violation.

> > I attach a source file which can trigger this violation. I tested it
> > on Ubuntu 20.04 LTS with 5.4 kernel.
>
> Well, that's a horribly old kernel :-( Please double check on v6.4 and
> consult that code for the discussion above -- I'm really not too
> interested in debugging something ancient.

I revised my code to make it work on 6.4.2 and fixed one logic error.
I tested it on Fedora 38 with kernel 6.4.2-858.vanilla.fc38.x86_64.
You can find the new code in attachment.

$ sudo ./a.out
.........................
prio: -21
prio: -21
prio: -21
prio: -21
prio: -21
prio: -21
prio: -20
prio: -20
prio: -20
prio: -20
prio: -20
prio: -20
prio: -20
prio: -20
prio: -20
prio: -20
prio: -20
    PID     LWP TTY          TIME CMD
   4564    4564 pts/0    00:00:01 a.out
   4564    4565 pts/0    00:00:00 waiter-0
   4564    4566 pts/0    00:00:00 waiter-1
   4564    4567 pts/0    00:00:00 waiter-2
   4564    4568 pts/0    00:00:00 waiter-3
   4564    4569 pts/0    00:00:00 waiter-4
   4564    4570 pts/0    00:00:00 waiter-5
   4564    4571 pts/0    00:00:00 waiter-6
   4564    4572 pts/0    00:00:00 waiter-7
   4564    4573 pts/0    00:00:00 waiter-8
   4564    4574 pts/0    00:00:00 waiter-9
   4564    4575 pts/0    00:00:00 waiter-10
   4564    4576 pts/0    00:00:00 waiter-11
   4564    4577 pts/0    00:00:00 waiter-12
   4564    4578 pts/0    00:00:00 waiter-13
   4564    4579 pts/0    00:00:00 waiter-14
   4564    4580 pts/0    00:00:00 waiter-15
   4564    4581 pts/0    00:00:00 waiter-16
   4564    4582 pts/0    00:00:00 waiter-17
   4564    4583 pts/0    00:00:00 waiter-18
   4564    4584 pts/0    00:00:00 waiter-19
   4564    4585 pts/0    00:00:00 changer-0
   4564    4586 pts/0    00:00:00 changer-1
   4564    4587 pts/0    00:00:00 changer-2
   4564    4588 pts/0    00:00:00 changer-3
   4564    4589 pts/0    00:00:00 changer-4
   4564    4590 pts/0    00:00:00 changer-5
   4564    4591 pts/0    00:00:00 changer-6
   4564    4592 pts/0    00:00:00 changer-7
   4564    4593 pts/0    00:00:00 changer-8
   4564    4594 pts/0    00:00:00 changer-9
   4564    4595 pts/0    00:00:00 changer-10
   4564    4596 pts/0    00:00:00 changer-11
   4564    4597 pts/0    00:00:00 changer-12
   4564    4598 pts/0    00:00:00 changer-13
   4564    4599 pts/0    00:00:00 changer-14
   4564    4600 pts/0    00:00:00 changer-15
   4564    4601 pts/0    00:00:00 changer-16
   4564    4602 pts/0    00:00:00 changer-17
   4564    4603 pts/0    00:00:00 changer-18
   4564    4604 pts/0    00:00:00 changer-19
found race, hang...

$ sudo crash --no_module
.....................
crash> task -R prio,normal_prio,rt_priority,pi_waiters 4564
PID: 4564     TASK: ffff9b7c8480a8c0  CPU: 3    COMMAND: "a.out"
  prio = 80,
  normal_prio = 120,
  rt_priority = 0,
  pi_waiters = {
    rb_root = {
      rb_node = 0xffffb5bad2ddfcf8
    },
    rb_leftmost = 0xffffb5bad2da7d98
  },

crash> print (struct rb_node *)0xffffb5bad2ddfcf8
$1 = (struct rb_node *) 0xffffb5bad2ddfcf8
crash> print *(struct rt_mutex_waiter *)((void *)$ - 24)
$2 = {
  tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0x0,
    rb_left = 0x0
  },
  pi_tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0xffffb5bad2df7d28,
    rb_left = 0xffffb5bad2dafd68
  },
  task = 0xffff9b7c80388000,
  lock = 0xffff9b7caa2cceb0,
  wake_state = 3,
  prio = 89,
  deadline = 0,
  ww_ctx = 0x0
}
crash> print $1->rb_left
$3 = (struct rb_node *) 0xffffb5bad2dafd68
crash> print *(struct rt_mutex_waiter *)((void *)$ - 24)
$4 = {
  tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0x0,
    rb_left = 0x0
  },
  pi_tree_entry = {
    __rb_parent_color = 18446662412739149049,
    rb_right = 0xffffb5bad2defdb8,
    rb_left = 0xffffb5bad2dbfd30
  },
  task = 0xffff9b7d2bca28c0,
  lock = 0xffff9b7d004a2970,
  wake_state = 3,
  prio = 83,
  deadline = 0,
  ww_ctx = 0x0
}
crash> print $1->rb_left->rb_left
$5 = (struct rb_node *) 0xffffb5bad2dbfd30
crash> print *(struct rt_mutex_waiter *)((void *)$ - 24)
$6 = {
  tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0x0,
    rb_left = 0x0
  },
  pi_tree_entry = {
    __rb_parent_color = 18446662412738952552,
    rb_right = 0xffffb5bad2d87d18,
    rb_left = 0xffffb5bad2da7d98
  },
  task = 0xffff9b7cfd55a8c0,
  lock = 0xffff9b7caa2cc6d0,
  wake_state = 3,
  prio = 79,
  deadline = 0,
  ww_ctx = 0x0
}
crash> print $1->rb_left->rb_left->rb_left
$7 = (struct rb_node *) 0xffffb5bad2da7d98
crash> print *(struct rt_mutex_waiter *)((void *)$ - 24)
$8 = {
  tree_entry = {
    __rb_parent_color = 1,
    rb_right = 0x0,
    rb_left = 0x0
  },
  pi_tree_entry = {
    __rb_parent_color = 18446662412739018033,
    rb_right = 0x0,
    rb_left = 0x0
  },
  task = 0xffff9b7c80bd0000,
  lock = 0xffff9b7caa2ccb50,
  wake_state = 3,
  prio = 80,
  deadline = 0,
  ww_ctx = 0x0
}
crash>

Key order invariant of pi_waiters had been violated by the last two
waiters above.

Thanks.

Henry

[-- Attachment #2: pi_642.c --]
[-- Type: text/x-c-code, Size: 5389 bytes --]

#define _GNU_SOURCE

#include <assert.h>
#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <sched.h>
#include <errno.h>
#include <sys/syscall.h>

#define PCOUNT 20
#define EXPECTED_PRIO -21

// Copied from related header.
struct sched_attr {
	uint32_t size;

	uint32_t sched_policy;
	uint64_t sched_flags;

	/* SCHED_NORMAL, SCHED_BATCH */
	int32_t sched_nice;

	/* SCHED_FIFO, SCHED_RR */
	uint32_t sched_priority;

	/* SCHED_DEADLINE */
	uint64_t sched_runtime;
	uint64_t sched_deadline;
	uint64_t sched_period;

	/* Utilization hints */
	uint32_t sched_util_min;
	uint32_t sched_util_max;
};

static pthread_mutex_t mutexes[PCOUNT];

static void init_mutex(pthread_mutex_t *mutex) {
	pthread_mutexattr_t attr;
	int ret;

	ret = pthread_mutexattr_init(&attr);
	assert(!ret);
	ret = pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
	assert(!ret);

	ret = pthread_mutex_init(mutex, &attr);
	assert(!ret);

	pthread_mutexattr_destroy(&attr);
}

enum thread_type {
	WAITER,
	PRIO_CHANGER,
};

static struct thread_spec {
	enum thread_type type;
	int name_index;
	pthread_barrier_t *barrier;

	// Used by waiter.
	pthread_mutex_t *wait_mutex;
	pid_t pid_save;
	
	// Used by prio changer.
	pid_t *waiter_pid;
	uint32_t prio;
} thread_specs[PCOUNT * 2];

static pthread_t threads[PCOUNT * 2];
static int thread_count = 0;

static int barrier_wait(pthread_barrier_t *barrier) {
	if (!barrier) {
		return 0;
	}

	int ret = pthread_barrier_wait(barrier);
	assert(!ret || ret == PTHREAD_BARRIER_SERIAL_THREAD);

	return ret;
}

static int sched_getattr(pid_t pid, struct sched_attr *attr, int flags) {
	return syscall(SYS_sched_getattr, pid, attr, sizeof(*attr), flags);
}

static int sched_setattr(pid_t pid, struct sched_attr *attr, int flags) {
	return syscall(SYS_sched_setattr, pid, attr, flags);
}

static void *prio_change_loop(struct thread_spec *spec) {
	struct sched_attr attr;
	int ret;

	for (;;) {
		barrier_wait(spec->barrier);

		ret = sched_getattr(*spec->waiter_pid, &attr, 0);
		if (ret < 0) {
			perror("sched_getattr");
			assert(0);
		}
		
		attr.sched_policy = SCHED_RR;
		attr.sched_priority = spec->prio;
	
		ret = sched_setattr(*spec->waiter_pid, &attr, 0);
		if (ret < 0) {
			perror("sched_setattr");
			exit(1);
		}

		barrier_wait(spec->barrier);
	}
}

static void *thread(void *arg) {
	struct thread_spec *spec = arg;
	char name[64];
	int ret;
	
	snprintf(name, sizeof(name), "%s-%d", 
			spec->type == WAITER ? "waiter" : "changer", 
			spec->name_index);
	ret = pthread_setname_np(pthread_self(), name);
	assert(!ret);

	switch (spec->type) {
	case WAITER:
		spec->pid_save = gettid();

		barrier_wait(spec->barrier);

		ret = pthread_mutex_lock(spec->wait_mutex);
		assert(!ret);
		break;
	case PRIO_CHANGER:
		prio_change_loop(spec);
		break;
	default:
		assert(0);
		break;
	}

	return NULL;
}

static void create_thread(struct thread_spec *spec) {
	int ret;

	ret = pthread_create(&threads[thread_count++], NULL, thread, spec);
	assert(!ret);
}

static int print_prio() {
	FILE *file = fopen("/proc/self/stat", "r");
	assert(file);

	char comm[64];
	int tmp, prio, ret;
	ret = fscanf(file, "%d %s %c %d %d %d %d %d %d %d %d %d %d %d %d %d %d %d",
			&tmp, comm, comm, &tmp, &tmp, &tmp, &tmp, &tmp, &tmp,
			&tmp, &tmp, &tmp, &tmp, &tmp, &tmp, &tmp, &tmp, &prio);
	assert(ret == 18);

	printf("prio: %d\n", prio);

	fclose(file);

	return prio;
}

static void print_threads(pid_t process_pid) {
	char cmd[128];
	snprintf(cmd, sizeof(cmd), "ps -L -p %d", process_pid);
	system(cmd);
}

int main(void) {
	pid_t pid;
	int ret;

	pid = getpid();
	printf("pid: %d\n", pid);

	for (int i = 0; i < sizeof(mutexes) / sizeof(mutexes[0]); ++i) {
		init_mutex(&mutexes[i]);
		ret = pthread_mutex_lock(&mutexes[i]);
		assert(!ret);
	}

	pthread_barrier_t barrier;
	ret = pthread_barrier_init(&barrier, NULL, PCOUNT + 1);
	assert(!ret);

	for (int i = 0; i < PCOUNT; ++i) {
		struct thread_spec *spec = &thread_specs[i];
		
		spec->type = WAITER;
		spec->name_index = i;
		spec->wait_mutex = &mutexes[i];
		spec->barrier = &barrier;

		create_thread(spec);
	}

	// Wait for filling of pid_save.
	barrier_wait(&barrier);

	for (int i = 0; i < PCOUNT; ++i) {
		struct thread_spec *spec = &thread_specs[i + PCOUNT];

		spec->type = PRIO_CHANGER; 
		spec->name_index = i;
		spec->prio = 99;
		spec->barrier = &barrier;
		spec->waiter_pid = &thread_specs[i].pid_save;

		create_thread(spec);
	}

	print_prio();
	print_threads(pid);

	srandom(time(NULL));
	int iter = 0;
	for (;;) {
		++iter;
		for (int i = 0; i < PCOUNT; ++i) {
			thread_specs[i + PCOUNT].prio = (iter % 2) ? i + 1 : PCOUNT - i;
		}

		for (int i = 0; i < PCOUNT; ++i) {
			int pos = random() % PCOUNT;
			int tmp = thread_specs[pos + PCOUNT].prio;
			thread_specs[pos + PCOUNT].prio = thread_specs[PCOUNT].prio;
			thread_specs[PCOUNT].prio = tmp;
		}

		barrier_wait(&barrier);
		barrier_wait(&barrier);

		//system("echo iteration > /sys/kernel/debug/tracing/trace_marker");

		for (int try = 0; ; ++try) {
			int prio = print_prio();
			if (prio == EXPECTED_PRIO) {
				// Try a new iteration.
				break;
			}

			if (try >= 10) {
				print_threads(pid);
				printf("found race, hang...\n");
				while (1) {
					sleep(3600);
				}
			}
		}
	}

	for (int i = 0; i < thread_count; ++i) {
		pthread_join(threads[i], NULL);
	}

	return 0;
}

Re: Fwd: Possible race in rt_mutex_adjust_prio_chain

[Peter Zijlstra]

On Fri, Jul 07, 2023 at 10:09:04AM +0800, Henry Wu wrote:

> Imagine a scenario that we have two rt_mutex (M1, M2) and three
> threads (A, B, C). Both rt_mutex are owned by thread A. B is blocked
> when acquiring M1 and C is blocked when acquiring M2. We use
> sched_setattr to change priority of B and C.

      A
     / \
    M1  M2
    |   |
    B   C

And in that case L will be two different locks, which I overlooked
yesterday. So L can't save the day.

This means I either need to take P2 earlier in overlap with P1 -- which
is tricky at best -- or duplicate the data to retain consistency.

Duplicating the data would still leave the logical race condition in
that a concurrent observer will not observe the waiter in the 'right'
location, however it should be harmless since both will continue the
propagate their resp state.

The below implements this duplication and seems to not insta-crash.

I'll endeavour to write a few comments and a Changelog to go with it.

---
 kernel/locking/rtmutex.c        | 93 ++++++++++++++++++++++++-----------------
 kernel/locking/rtmutex_api.c    |  2 +-
 kernel/locking/rtmutex_common.h | 34 +++++++++------
 3 files changed, 76 insertions(+), 53 deletions(-)

diff --git a/kernel/locking/rtmutex.c b/kernel/locking/rtmutex.c
index 728f434de2bb..3af6772cebb6 100644
--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -336,18 +336,27 @@ static __always_inline int __waiter_prio(struct task_struct *task)
 static __always_inline void
 waiter_update_prio(struct rt_mutex_waiter *waiter, struct task_struct *task)
 {
-	waiter->prio = __waiter_prio(task);
-	waiter->deadline = task->dl.deadline;
+	waiter->tree.prio = __waiter_prio(task);
+	waiter->tree.deadline = task->dl.deadline;
+}
+
+static __always_inline void
+waiter_clone_prio(struct rt_mutex_waiter *waiter)
+{
+	waiter->pi_tree.prio = waiter->tree.prio;
+	waiter->pi_tree.deadline = waiter->tree.deadline;
 }
 
 /*
- * Only use with rt_mutex_waiter_{less,equal}()
+ * Only use with rt_waiter_node_{less,equal}()
  */
+#define task_to_waiter_node(p) \
+	&(struct rt_waiter_node){ .prio = __waiter_prio(p), .deadline = (p)->dl.deadline }
 #define task_to_waiter(p)	\
-	&(struct rt_mutex_waiter){ .prio = __waiter_prio(p), .deadline = (p)->dl.deadline }
+	&(struct rt_mutex_waiter){ .tree = *task_to_waiter_node(p) }
 
-static __always_inline int rt_mutex_waiter_less(struct rt_mutex_waiter *left,
-						struct rt_mutex_waiter *right)
+static __always_inline int rt_waiter_node_less(struct rt_waiter_node *left,
+					       struct rt_waiter_node *right)
 {
 	if (left->prio < right->prio)
 		return 1;
@@ -364,8 +373,8 @@ static __always_inline int rt_mutex_waiter_less(struct rt_mutex_waiter *left,
 	return 0;
 }
 
-static __always_inline int rt_mutex_waiter_equal(struct rt_mutex_waiter *left,
-						 struct rt_mutex_waiter *right)
+static __always_inline int rt_waiter_node_equal(struct rt_waiter_node *left,
+						 struct rt_waiter_node *right)
 {
 	if (left->prio != right->prio)
 		return 0;
@@ -385,7 +394,7 @@ static __always_inline int rt_mutex_waiter_equal(struct rt_mutex_waiter *left,
 static inline bool rt_mutex_steal(struct rt_mutex_waiter *waiter,
 				  struct rt_mutex_waiter *top_waiter)
 {
-	if (rt_mutex_waiter_less(waiter, top_waiter))
+	if (rt_waiter_node_less(&waiter->tree, &top_waiter->tree))
 		return true;
 
 #ifdef RT_MUTEX_BUILD_SPINLOCKS
@@ -393,30 +402,30 @@ static inline bool rt_mutex_steal(struct rt_mutex_waiter *waiter,
 	 * Note that RT tasks are excluded from same priority (lateral)
 	 * steals to prevent the introduction of an unbounded latency.
 	 */
-	if (rt_prio(waiter->prio) || dl_prio(waiter->prio))
+	if (rt_prio(waiter->tree.prio) || dl_prio(waiter->tree.prio))
 		return false;
 
-	return rt_mutex_waiter_equal(waiter, top_waiter);
+	return rt_waiter_node_equal(&waiter->tree, &top_waiter->tree);
 #else
 	return false;
 #endif
 }
 
 #define __node_2_waiter(node) \
-	rb_entry((node), struct rt_mutex_waiter, tree_entry)
+	rb_entry((node), struct rt_mutex_waiter, tree.entry)
 
 static __always_inline bool __waiter_less(struct rb_node *a, const struct rb_node *b)
 {
 	struct rt_mutex_waiter *aw = __node_2_waiter(a);
 	struct rt_mutex_waiter *bw = __node_2_waiter(b);
 
-	if (rt_mutex_waiter_less(aw, bw))
+	if (rt_waiter_node_less(&aw->tree, &bw->tree))
 		return 1;
 
 	if (!build_ww_mutex())
 		return 0;
 
-	if (rt_mutex_waiter_less(bw, aw))
+	if (rt_waiter_node_less(&bw->tree, &aw->tree))
 		return 0;
 
 	/* NOTE: relies on waiter->ww_ctx being set before insertion */
@@ -434,48 +443,54 @@ static __always_inline bool __waiter_less(struct rb_node *a, const struct rb_nod
 static __always_inline void
 rt_mutex_enqueue(struct rt_mutex_base *lock, struct rt_mutex_waiter *waiter)
 {
-	rb_add_cached(&waiter->tree_entry, &lock->waiters, __waiter_less);
+	rb_add_cached(&waiter->tree.entry, &lock->waiters, __waiter_less);
 }
 
 static __always_inline void
 rt_mutex_dequeue(struct rt_mutex_base *lock, struct rt_mutex_waiter *waiter)
 {
-	if (RB_EMPTY_NODE(&waiter->tree_entry))
+	if (RB_EMPTY_NODE(&waiter->tree.entry))
 		return;
 
-	rb_erase_cached(&waiter->tree_entry, &lock->waiters);
-	RB_CLEAR_NODE(&waiter->tree_entry);
+	rb_erase_cached(&waiter->tree.entry, &lock->waiters);
+	RB_CLEAR_NODE(&waiter->tree.entry);
 }
 
-#define __node_2_pi_waiter(node) \
-	rb_entry((node), struct rt_mutex_waiter, pi_tree_entry)
+#define __node_2_rt_node(node) \
+	rb_entry((node), struct rt_waiter_node, entry)
 
-static __always_inline bool
-__pi_waiter_less(struct rb_node *a, const struct rb_node *b)
+static __always_inline bool __pi_waiter_less(struct rb_node *a, const struct rb_node *b)
 {
-	return rt_mutex_waiter_less(__node_2_pi_waiter(a), __node_2_pi_waiter(b));
+	return rt_waiter_node_less(__node_2_rt_node(a), __node_2_rt_node(b));
 }
 
 static __always_inline void
 rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
 {
-	rb_add_cached(&waiter->pi_tree_entry, &task->pi_waiters, __pi_waiter_less);
+	lockdep_assert_held(&task->pi_lock);
+
+	rb_add_cached(&waiter->pi_tree.entry, &task->pi_waiters, __pi_waiter_less);
 }
 
 static __always_inline void
 rt_mutex_dequeue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
 {
-	if (RB_EMPTY_NODE(&waiter->pi_tree_entry))
+	lockdep_assert_held(&task->pi_lock);
+
+	if (RB_EMPTY_NODE(&waiter->pi_tree.entry))
 		return;
 
-	rb_erase_cached(&waiter->pi_tree_entry, &task->pi_waiters);
-	RB_CLEAR_NODE(&waiter->pi_tree_entry);
+	rb_erase_cached(&waiter->pi_tree.entry, &task->pi_waiters);
+	RB_CLEAR_NODE(&waiter->pi_tree.entry);
 }
 
-static __always_inline void rt_mutex_adjust_prio(struct task_struct *p)
+static __always_inline void rt_mutex_adjust_prio(struct rt_mutex_base *lock,
+						 struct task_struct *p)
 {
 	struct task_struct *pi_task = NULL;
 
+	lockdep_assert_held(&lock->wait_lock);
+	lockdep_assert(rt_mutex_owner(lock) == p);
 	lockdep_assert_held(&p->pi_lock);
 
 	if (task_has_pi_waiters(p))
@@ -756,7 +771,7 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
 	 * enabled we continue, but stop the requeueing in the chain
 	 * walk.
 	 */
-	if (rt_mutex_waiter_equal(waiter, task_to_waiter(task))) {
+	if (rt_waiter_node_equal(&waiter->tree, task_to_waiter_node(task))) {
 		if (!detect_deadlock)
 			goto out_unlock_pi;
 		else
@@ -874,11 +889,6 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
 	 * or
 	 *
 	 *   DL CBS enforcement advancing the effective deadline.
-	 *
-	 * Even though pi_waiters also uses these fields, and that tree is only
-	 * updated in [11], we can do this here, since we hold [L], which
-	 * serializes all pi_waiters access and rb_erase() does not care about
-	 * the values of the node being removed.
 	 */
 	waiter_update_prio(waiter, task);
 
@@ -921,8 +931,9 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
 		 * and adjust the priority of the owner.
 		 */
 		rt_mutex_dequeue_pi(task, prerequeue_top_waiter);
+		waiter_clone_prio(waiter);
 		rt_mutex_enqueue_pi(task, waiter);
-		rt_mutex_adjust_prio(task);
+		rt_mutex_adjust_prio(lock, task);
 
 	} else if (prerequeue_top_waiter == waiter) {
 		/*
@@ -937,8 +948,9 @@ static int __sched rt_mutex_adjust_prio_chain(struct task_struct *task,
 		 */
 		rt_mutex_dequeue_pi(task, waiter);
 		waiter = rt_mutex_top_waiter(lock);
+		waiter_clone_prio(waiter);
 		rt_mutex_enqueue_pi(task, waiter);
-		rt_mutex_adjust_prio(task);
+		rt_mutex_adjust_prio(lock, task);
 	} else {
 		/*
 		 * Nothing changed. No need to do any priority
@@ -1154,6 +1166,7 @@ static int __sched task_blocks_on_rt_mutex(struct rt_mutex_base *lock,
 	waiter->task = task;
 	waiter->lock = lock;
 	waiter_update_prio(waiter, task);
+	waiter_clone_prio(waiter);
 
 	/* Get the top priority waiter on the lock */
 	if (rt_mutex_has_waiters(lock))
@@ -1187,7 +1200,7 @@ static int __sched task_blocks_on_rt_mutex(struct rt_mutex_base *lock,
 		rt_mutex_dequeue_pi(owner, top_waiter);
 		rt_mutex_enqueue_pi(owner, waiter);
 
-		rt_mutex_adjust_prio(owner);
+		rt_mutex_adjust_prio(lock, owner);
 		if (owner->pi_blocked_on)
 			chain_walk = 1;
 	} else if (rt_mutex_cond_detect_deadlock(waiter, chwalk)) {
@@ -1234,6 +1247,8 @@ static void __sched mark_wakeup_next_waiter(struct rt_wake_q_head *wqh,
 {
 	struct rt_mutex_waiter *waiter;
 
+	lockdep_assert_held(&lock->wait_lock);
+
 	raw_spin_lock(&current->pi_lock);
 
 	waiter = rt_mutex_top_waiter(lock);
@@ -1246,7 +1261,7 @@ static void __sched mark_wakeup_next_waiter(struct rt_wake_q_head *wqh,
 	 * task unblocks.
 	 */
 	rt_mutex_dequeue_pi(current, waiter);
-	rt_mutex_adjust_prio(current);
+	rt_mutex_adjust_prio(lock, current);
 
 	/*
 	 * As we are waking up the top waiter, and the waiter stays
@@ -1482,7 +1497,7 @@ static void __sched remove_waiter(struct rt_mutex_base *lock,
 	if (rt_mutex_has_waiters(lock))
 		rt_mutex_enqueue_pi(owner, rt_mutex_top_waiter(lock));
 
-	rt_mutex_adjust_prio(owner);
+	rt_mutex_adjust_prio(lock, owner);
 
 	/* Store the lock on which owner is blocked or NULL */
 	next_lock = task_blocked_on_lock(owner);
diff --git a/kernel/locking/rtmutex_api.c b/kernel/locking/rtmutex_api.c
index cb9fdff76a8a..a6974d044593 100644
--- a/kernel/locking/rtmutex_api.c
+++ b/kernel/locking/rtmutex_api.c
@@ -459,7 +459,7 @@ void __sched rt_mutex_adjust_pi(struct task_struct *task)
 	raw_spin_lock_irqsave(&task->pi_lock, flags);
 
 	waiter = task->pi_blocked_on;
-	if (!waiter || rt_mutex_waiter_equal(waiter, task_to_waiter(task))) {
+	if (!waiter || rt_waiter_node_equal(&waiter->tree, task_to_waiter_node(task))) {
 		raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 		return;
 	}
diff --git a/kernel/locking/rtmutex_common.h b/kernel/locking/rtmutex_common.h
index c47e8361bfb5..3d7457bffd43 100644
--- a/kernel/locking/rtmutex_common.h
+++ b/kernel/locking/rtmutex_common.h
@@ -17,27 +17,34 @@
 #include <linux/rtmutex.h>
 #include <linux/sched/wake_q.h>
 
+
+/*
+ * @prio:		Priority of the waiter
+ * @deadline:		Deadline of the waiter if applicable
+ */
+struct rt_waiter_node {
+	struct rb_node	entry;
+	int		prio;
+	u64		deadline;
+};
+
 /*
  * This is the control structure for tasks blocked on a rt_mutex,
  * which is allocated on the kernel stack on of the blocked task.
  *
- * @tree_entry:		pi node to enqueue into the mutex waiters tree
- * @pi_tree_entry:	pi node to enqueue into the mutex owner waiters tree
+ * @tree:		pi node to enqueue into the mutex waiters tree
+ * @pi_tree:		pi node to enqueue into the mutex owner waiters tree
  * @task:		task reference to the blocked task
  * @lock:		Pointer to the rt_mutex on which the waiter blocks
  * @wake_state:		Wakeup state to use (TASK_NORMAL or TASK_RTLOCK_WAIT)
- * @prio:		Priority of the waiter
- * @deadline:		Deadline of the waiter if applicable
  * @ww_ctx:		WW context pointer
  */
 struct rt_mutex_waiter {
-	struct rb_node		tree_entry;
-	struct rb_node		pi_tree_entry;
+	struct rt_waiter_node	tree;
+	struct rt_waiter_node	pi_tree;
 	struct task_struct	*task;
 	struct rt_mutex_base	*lock;
 	unsigned int		wake_state;
-	int			prio;
-	u64			deadline;
 	struct ww_acquire_ctx	*ww_ctx;
 };
 
@@ -105,7 +112,7 @@ static inline bool rt_mutex_waiter_is_top_waiter(struct rt_mutex_base *lock,
 {
 	struct rb_node *leftmost = rb_first_cached(&lock->waiters);
 
-	return rb_entry(leftmost, struct rt_mutex_waiter, tree_entry) == waiter;
+	return rb_entry(leftmost, struct rt_mutex_waiter, tree.entry) == waiter;
 }
 
 static inline struct rt_mutex_waiter *rt_mutex_top_waiter(struct rt_mutex_base *lock)
@@ -114,7 +121,7 @@ static inline struct rt_mutex_waiter *rt_mutex_top_waiter(struct rt_mutex_base *
 	struct rt_mutex_waiter *w = NULL;
 
 	if (leftmost) {
-		w = rb_entry(leftmost, struct rt_mutex_waiter, tree_entry);
+		w = rb_entry(leftmost, struct rt_mutex_waiter, tree.entry);
 		BUG_ON(w->lock != lock);
 	}
 	return w;
@@ -127,8 +134,9 @@ static inline int task_has_pi_waiters(struct task_struct *p)
 
 static inline struct rt_mutex_waiter *task_top_pi_waiter(struct task_struct *p)
 {
+	lockdep_assert_held(&p->pi_lock);
 	return rb_entry(p->pi_waiters.rb_leftmost, struct rt_mutex_waiter,
-			pi_tree_entry);
+			pi_tree.entry);
 }
 
 #define RT_MUTEX_HAS_WAITERS	1UL
@@ -190,8 +198,8 @@ static inline void debug_rt_mutex_free_waiter(struct rt_mutex_waiter *waiter)
 static inline void rt_mutex_init_waiter(struct rt_mutex_waiter *waiter)
 {
 	debug_rt_mutex_init_waiter(waiter);
-	RB_CLEAR_NODE(&waiter->pi_tree_entry);
-	RB_CLEAR_NODE(&waiter->tree_entry);
+	RB_CLEAR_NODE(&waiter->pi_tree.entry);
+	RB_CLEAR_NODE(&waiter->tree.entry);
 	waiter->wake_state = TASK_NORMAL;
 	waiter->task = NULL;
 }

Re: Fwd: Possible race in rt_mutex_adjust_prio_chain

[Mike Galbraith]

On Fri, 2023-07-07 at 14:59 +0200, Peter Zijlstra wrote:
>
> The below implements this duplication and seems to not insta-crash.

RT bits of ww_mutex.h needed tree_entry -> tree.entry.  Modulo that, RT
seems content.

	-Mike

Re: Fwd: Possible race in rt_mutex_adjust_prio_chain

[Peter Zijlstra]

On Fri, Jul 07, 2023 at 05:39:38PM +0200, Mike Galbraith wrote:
> On Fri, 2023-07-07 at 14:59 +0200, Peter Zijlstra wrote:
> >
> > The below implements this duplication and seems to not insta-crash.
> 
> RT bits of ww_mutex.h needed tree_entry -> tree.entry.  Modulo that, RT
> seems content.

Ah indeed, just in time. Added, I'll post a real patch soon.

Re: Fwd: Possible race in rt_mutex_adjust_prio_chain

[Henry Wu]

Hi, Peter and Mike.

Mike Galbraith <efault@gmx.de> 于2023年7月7日周五 23:39写道：
>
> On Fri, 2023-07-07 at 14:59 +0200, Peter Zijlstra wrote:
> >
> > The below implements this duplication and seems to not insta-crash.
>
> RT bits of ww_mutex.h needed tree_entry -> tree.entry.  Modulo that, RT
> seems content.
>
>         -Mike

I patched my kernel with Peter's patch and tested it with my test
program. I haven't seen any race so far and I will test more tomorrow.
Fedora's default kernel config doesn't enable CONFIG_PREEMPT_RT so I
didn't come across with compile error. I will test final patch if
available.

Re: Fwd: Possible race in rt_mutex_adjust_prio_chain

[Peter Zijlstra]

On Sat, Jul 08, 2023 at 01:28:25AM +0800, Henry Wu wrote:

> I will test final patch if available.

https://lkml.kernel.org/r/20230707161052.GF2883469%40hirez.programming.kicks-ass.net

Does that work for you; could you reply with a tested-by if possible?

Re: Fwd: Possible race in rt_mutex_adjust_prio_chain

[Henry Wu]

Peter:

Peter Zijlstra <peterz@infradead.org> 于2023年7月13日周四 20:55写道：
>
> On Sat, Jul 08, 2023 at 01:28:25AM +0800, Henry Wu wrote:
>
> > I will test final patch if available.
>
> https://lkml.kernel.org/r/20230707161052.GF2883469%40hirez.programming.kicks-ass.net
>
> Does that work for you; could you reply with a tested-by if possible?

Sorry, I missed your patch and I will test it as soon as possible. I
will reply in two days.

Sincerely,

Henry