[PATCH rc5-rt2 3/3] plist: convert the code to new implementation

[PATCH rc5-rt2 3/3] plist: convert the code to new implementation

[Oleg Nesterov]

This patch blindly fixes compilation errors caused by
a previous patch.

 include/linux/rt_lock.h   |    8 ++--
 include/linux/sched.h     |    2 -
 include/linux/init_task.h |    2 -
 kernel/fork.c             |    2 -
 kernel/rt.c               |   78 ++++++++++++++++++++--------------------------
 5 files changed, 42 insertions(+), 50 deletions(-)

Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>

--- RT/include/linux/rt_lock.h~3_FIX	2005-12-17 19:59:45.000000000 +0300
+++ RT/include/linux/rt_lock.h	2005-12-18 22:23:40.000000000 +0300
@@ -24,7 +24,7 @@
  */
 struct rt_mutex {
 	raw_spinlock_t		wait_lock;
-	struct plist		wait_list;
+	struct pl_head		wait_list;
 	struct thread_info	*owner;
 # ifdef CONFIG_DEBUG_RT_LOCKING_MODE
 	raw_spinlock_t		debug_slock;
@@ -49,8 +49,8 @@ struct rt_mutex {
  */
 struct rt_mutex_waiter {
 	struct rt_mutex		*lock;
-	struct plist		list;
-	struct plist		pi_list;
+	struct pl_node		list;
+	struct pl_node		pi_list;
 	struct thread_info	*ti;
 #ifdef CONFIG_DEBUG_DEADLOCKS
 	unsigned long eip;
@@ -87,7 +87,7 @@ struct rt_mutex_waiter {
 # define __PLIST_INIT(lockname)
 #else
 # define __PLIST_INIT(lockname) \
-	, .wait_list = PLIST_INIT((lockname).wait_list, 140 /*MAX_PRIO*/)
+	, .wait_list = PL_HEAD_INIT((lockname).wait_list)
 #endif
 
 #define __RT_MUTEX_INITIALIZER(lockname) \
--- RT/include/linux/sched.h~3_FIX	2005-12-17 19:59:45.000000000 +0300
+++ RT/include/linux/sched.h	2005-12-18 00:21:43.000000000 +0300
@@ -1026,7 +1026,7 @@ struct task_struct {
 #endif
 	/* realtime bits */
 	struct list_head delayed_put;
-	struct plist pi_waiters;
+	struct pl_head pi_waiters;
 
 	/* RT deadlock detection and priority inheritance handling */
 	struct rt_mutex_waiter *blocked_on;
--- RT/include/linux/init_task.h~3_FIX	2005-12-17 19:59:45.000000000 +0300
+++ RT/include/linux/init_task.h	2005-12-18 00:27:31.000000000 +0300
@@ -121,7 +121,7 @@ extern struct group_info init_groups;
 	.alloc_lock	= SPIN_LOCK_UNLOCKED(tsk.alloc_lock),		\
 	.proc_lock	= SPIN_LOCK_UNLOCKED(tsk.proc_lock),		\
 	.delayed_put	= LIST_HEAD_INIT(tsk.delayed_put),		\
-	.pi_waiters	= PLIST_INIT(tsk.pi_waiters, MAX_PRIO),		\
+	.pi_waiters	= PL_HEAD_INIT(tsk.pi_waiters),			\
 	.pi_lock	= RAW_SPIN_LOCK_UNLOCKED,			\
 	.journal_info	= NULL,						\
 	.cpu_timers	= INIT_CPU_TIMERS(tsk.cpu_timers),		\
--- RT/kernel/fork.c~3_FIX	2005-12-17 19:59:45.000000000 +0300
+++ RT/kernel/fork.c	2005-12-18 00:55:41.000000000 +0300
@@ -1027,7 +1027,7 @@ static task_t *copy_process(unsigned lon
 #endif
 	INIT_LIST_HEAD(&p->delayed_put);
 	preempt_disable();
-	plist_init(&p->pi_waiters, MAX_PRIO);
+	pl_head_init(&p->pi_waiters);
 	preempt_enable();
 	p->blocked_on = NULL; /* not blocked yet */
 	spin_lock_init(&p->pi_lock);
--- RT/kernel/rt.c~3_FIX	2005-12-17 19:59:45.000000000 +0300
+++ RT/kernel/rt.c	2005-12-18 22:03:25.000000000 +0300
@@ -396,8 +396,8 @@ static void printk_waiter(struct rt_mute
 {
 	printk("-------------------------\n");
 	printk("| waiter struct %p:\n", w);
-	printk("| w->list: [DP:%p/%p|SP:%p/%p|PRI:%d]\n", w->list.dp_node.prev, w->list.dp_node.next, w->list.sp_node.prev, w->list.sp_node.next, w->list.prio);
-	printk("| w->pi_list: [DP:%p/%p|SP:%p/%p|PRI:%d]\n", w->pi_list.dp_node.prev, w->pi_list.dp_node.next, w->pi_list.sp_node.prev, w->pi_list.sp_node.next, w->pi_list.prio);
+	printk("| w->list: [DP:%p/%p|SP:%p/%p|PRI:%d]\n", w->list.plist.prio_list.prev, w->list.plist.prio_list.next, w->list.plist.node_list.prev, w->list.plist.node_list.next, w->list.prio);
+	printk("| w->pi_list: [DP:%p/%p|SP:%p/%p|PRI:%d]\n", w->pi_list.plist.prio_list.prev, w->pi_list.plist.prio_list.next, w->pi_list.plist.node_list.prev, w->pi_list.plist.node_list.next,
w->pi_list.prio);
 	printk("\n| lock:\n");
 	printk_lock(w->lock, 1);
 	printk("| w->ti->task:\n");
@@ -617,7 +617,6 @@ void check_no_held_locks(struct task_str
 {
 	struct thread_info *ti = task->thread_info;
 	struct list_head *curr, *next, *cursor = NULL;
-	struct plist *curr1;
 	struct rt_mutex *lock;
 	struct rt_mutex_waiter *w;
 	struct thread_info *t;
@@ -671,8 +670,7 @@ restart:
 		goto restart;
 	}
 	_raw_spin_lock(&task->pi_lock);
-	plist_for_each(curr1, &task->pi_waiters) {
-		w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
+	plist_for_each_entry(w, &task->pi_waiters, pi_list) {
 		TRACE_OFF();
 		_raw_spin_unlock(&task->pi_lock);
 		trace_unlock_irqrestore(&trace_lock, flags, ti);
@@ -734,13 +732,11 @@ check_pi_list_present(struct rt_mutex *l
 		      struct thread_info *old_owner)
 {
 	struct rt_mutex_waiter *w;
-	struct plist *curr1;
 
 	_raw_spin_lock(&old_owner->task->pi_lock);
-	TRACE_WARN_ON_LOCKED(plist_empty(&waiter->pi_list));
+	TRACE_WARN_ON_LOCKED(plist_unhashed(&waiter->pi_list));
 
-	plist_for_each(curr1, &old_owner->task->pi_waiters) {
-		w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
+	plist_for_each_entry(w, &old_owner->task->pi_waiters, pi_list) {
 		if (w == waiter)
 			goto ok;
 	}
@@ -754,11 +750,9 @@ static void
 check_pi_list_empty(struct rt_mutex *lock, struct thread_info *old_owner)
 {
 	struct rt_mutex_waiter *w;
-	struct plist *curr1;
 
 	_raw_spin_lock(&old_owner->task->pi_lock);
-	plist_for_each(curr1, &old_owner->task->pi_waiters) {
-		w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
+	plist_for_each_entry(w, &old_owner->task->pi_waiters, pi_list) {
 		if (w->lock == lock) {
 			TRACE_OFF();
 			printk("hm, PI interest but no waiter? Old owner:\n");
@@ -793,8 +787,7 @@ static void
 change_owner(struct rt_mutex *lock, struct thread_info *old_owner,
 	     struct thread_info *new_owner)
 {
-	struct plist *next1, *curr1;
-	struct rt_mutex_waiter *w;
+	struct rt_mutex_waiter *w, *tmp;
 	int requeued = 0, sum = 0;
 
 	if (old_owner == new_owner)
@@ -802,12 +795,11 @@ change_owner(struct rt_mutex *lock, stru
 
 	SMP_TRACE_BUG_ON_LOCKED(!spin_is_locked(&old_owner->task->pi_lock));
 	SMP_TRACE_BUG_ON_LOCKED(!spin_is_locked(&new_owner->task->pi_lock));
-	plist_for_each_safe(curr1, next1, &old_owner->task->pi_waiters) {
-		w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
+	plist_for_each_entry_safe(w, tmp, &old_owner->task->pi_waiters, pi_list) {
 		if (w->lock == lock) {
 			trace_special_pid(w->ti->task->pid, w->ti->task->prio, w->ti->task->normal_prio);
-			plist_del(&w->pi_list, &old_owner->task->pi_waiters);
-			plist_init(&w->pi_list, w->ti->task->prio);
+			plist_del(&w->pi_list);
+			w->pi_list.prio = w->ti->task->prio;
 			plist_add(&w->pi_list, &new_owner->task->pi_waiters);
 			requeued++;
 		}
@@ -917,7 +909,7 @@ static void pi_setprio(struct rt_mutex *
 
 		TRACE_BUG_ON_LOCKED(!lock_owner(l));
 
-		if (!plist_empty(&w->pi_list)) {
+		if (!plist_unhashed(&w->pi_list)) {
 			TRACE_BUG_ON_LOCKED(!was_rt && !ALL_TASKS_PI && !rt_task(p));
 			/*
 			 * If the task is blocked on a lock, and we just restored
@@ -927,17 +919,17 @@ static void pi_setprio(struct rt_mutex *
 			 * (TODO: this can be unfair to SCHED_NORMAL tasks if they
 			 *        get PI handled.)
 			 */
-			plist_del(&w->pi_list, &lock_owner(l)->task->pi_waiters);
+			plist_del(&w->pi_list);
 		} else
 			TRACE_BUG_ON_LOCKED((ALL_TASKS_PI || rt_task(p)) && was_rt);
 
 		if (ALL_TASKS_PI || rt_task(p)) {
-			plist_init(&w->pi_list,prio);
+			w->pi_list.prio = prio;
 			plist_add(&w->pi_list, &lock_owner(l)->task->pi_waiters);
 		}
 
-		plist_del(&w->list, &l->wait_list);
-		plist_init(&w->list, prio);
+		plist_del(&w->list);
+		w->list.prio = prio;
 		plist_add(&w->list, &l->wait_list);
 
 		pi_walk++;
@@ -1028,7 +1020,7 @@ task_blocks_on_lock(struct rt_mutex_wait
 	task->blocked_on = waiter;
 	waiter->lock = lock;
 	waiter->ti = ti;
-	plist_init(&waiter->pi_list, task->prio);
+	pl_node_init(&waiter->pi_list, task->prio);
 	/*
 	 * Add SCHED_NORMAL tasks to the end of the waitqueue (FIFO):
 	 */
@@ -1067,7 +1059,7 @@ static void __init_rt_mutex(struct rt_mu
 	lock->owner = NULL;
 	spin_lock_init(&lock->wait_lock);
 	preempt_disable();
-	plist_init(&lock->wait_list, MAX_PRIO);
+	pl_head_init(&lock->wait_list);
 	preempt_enable();
 #ifdef CONFIG_DEBUG_DEADLOCKS
 	lock->save_state = save_state;
@@ -1178,9 +1170,9 @@ pick_new_owner(struct rt_mutex *lock, st
 #endif
 		_raw_spin_lock(&old_owner->task->pi_lock);
 
-	plist_del_init(&waiter->list, &lock->wait_list);
-	plist_del(&waiter->pi_list, &old_owner->task->pi_waiters);
-	plist_init(&waiter->pi_list, waiter->ti->task->prio);
+	plist_del(&waiter->list);
+	plist_del(&waiter->pi_list);
+	waiter->pi_list.prio = waiter->ti->task->prio;
 
 	set_new_owner(lock, old_owner, new_owner __W_EIP__(waiter));
 	/* Don't touch waiter after ->task has been NULLed */
@@ -1203,8 +1195,8 @@ static inline void init_lists(struct rt_
 {
 #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_DEADLOCKS)
 	// we have to do this until the static initializers get fixed:
-	if (unlikely(!lock->wait_list.dp_node.prev)) {
-		plist_init(&lock->wait_list, MAX_PRIO);
+	if (unlikely(!lock->wait_list.prio_list.prev)) {
+		pl_head_init(&lock->wait_list);
 #ifdef CONFIG_DEBUG_DEADLOCKS
 		pi_initialized++;
 #endif
@@ -1334,8 +1326,8 @@ capture_lock(struct rt_mutex_waiter *wai
 			ret = 0;
 		} else {
 			/* Add ourselves back to the list */
-			TRACE_BUG_ON_LOCKED(!plist_empty(&waiter->list));
-			plist_init(&waiter->list, task->prio);
+			TRACE_BUG_ON_LOCKED(!plist_unhashed(&waiter->list));
+			pl_node_init(&waiter->list, task->prio);
 			task_blocks_on_lock(waiter, ti, lock __W_EIP__(waiter));
 			ret = 1;
 		}
@@ -1355,16 +1347,16 @@ static inline void INIT_WAITER(struct rt
 {
 #ifdef CONFIG_DEBUG_DEADLOCKS
 	memset(waiter, 0x11, sizeof(*waiter));
-	plist_init(&waiter->list, MAX_PRIO);
-	plist_init(&waiter->pi_list, MAX_PRIO);
+	pl_node_init(&waiter->list, MAX_PRIO);
+	pl_node_init(&waiter->pi_list, MAX_PRIO);
 #endif
 }
 
 static inline void FREE_WAITER(struct rt_mutex_waiter *waiter)
 {
 #ifdef CONFIG_DEBUG_DEADLOCKS
-	TRACE_WARN_ON(!plist_empty(&waiter->list));
-	TRACE_WARN_ON(!plist_empty(&waiter->pi_list));
+	TRACE_WARN_ON(!plist_unhashed(&waiter->list));
+	TRACE_WARN_ON(!plist_unhashed(&waiter->pi_list));
 	TRACE_WARN_ON(current->blocked_on);
 	memset(waiter, 0x22, sizeof(*waiter));
 #endif
@@ -1409,7 +1401,7 @@ ____down(struct rt_mutex *lock __EIP_DEC
 
 	set_task_state(task, TASK_UNINTERRUPTIBLE);
 
-	plist_init(&waiter.list, task->prio);
+	pl_node_init(&waiter.list, task->prio);
 	task_blocks_on_lock(&waiter, ti, lock __EIP__);
 
 	TRACE_BUG_ON_LOCKED(!raw_irqs_disabled());
@@ -1490,7 +1482,7 @@ ____down_mutex(struct rt_mutex *lock __E
 		return;
 	}
 
-	plist_init(&waiter.list, task->prio);
+	pl_node_init(&waiter.list, task->prio);
 	task_blocks_on_lock(&waiter, ti, lock __EIP__);
 
 	TRACE_BUG_ON_LOCKED(!raw_irqs_disabled());
@@ -1589,7 +1581,7 @@ ____up_mutex(struct rt_mutex *lock, int 
 	trace_lock_irqsave(&trace_lock, flags, ti);
 	TRACE_BUG_ON_LOCKED(!raw_irqs_disabled());
 	_raw_spin_lock(&lock->wait_lock);
-	TRACE_BUG_ON_LOCKED(!lock->wait_list.dp_node.prev && !lock->wait_list.dp_node.next);
+	TRACE_BUG_ON_LOCKED(!lock->wait_list.prio_list.prev && !lock->wait_list.prio_list.next);
 
 #ifdef CONFIG_DEBUG_DEADLOCKS
 	TRACE_WARN_ON_LOCKED(lock_owner(lock) != ti);
@@ -1873,7 +1865,7 @@ static int __sched __down_interruptible(
 
 	set_task_state(task, TASK_INTERRUPTIBLE);
 
-	plist_init(&waiter.list, task->prio);
+	pl_node_init(&waiter.list, task->prio);
 	task_blocks_on_lock(&waiter, ti, lock __EIP__);
 
 	TRACE_BUG_ON_LOCKED(!raw_irqs_disabled());
@@ -1908,7 +1900,7 @@ wait_again:
 			_raw_spin_lock(&task->pi_lock);
 			_raw_spin_lock(&lock->wait_lock);
 			if (waiter.ti || time) {
-				plist_del_init(&waiter.list, &lock->wait_list);
+				plist_del(&waiter.list);
 				/*
 				 * Just remove ourselves from the PI list.
 				 * (No big problem if our PI effect lingers
@@ -1916,8 +1908,8 @@ wait_again:
 				 */
 				TRACE_WARN_ON_LOCKED(waiter.ti != ti);
 				TRACE_WARN_ON_LOCKED(current->blocked_on != &waiter);
-				plist_del(&waiter.pi_list, &task->pi_waiters);
-				plist_init(&waiter.pi_list, task->prio);
+				plist_del(&waiter.pi_list);
+				waiter.pi_list.prio = task->prio;
 				waiter.ti = NULL;
 				current->blocked_on = NULL;
 				if (time) {

Re: [PATCH rc5-rt2 3/3] plist: convert the code to new implementation

[Daniel Walker]

I think firstly, if you want to have success with this patch you'll need
to clean it up a bit. I'm not an authority on clean code , but below
isn't clean to my eyes. However, this is cleaner than your last
attempt .

Hard coding MAX_PRIO isn't really acceptable. If your going to make it
more similar to list_head , why not name it plist_head instead of
pl_head that way it's easy to switch between them. Part of what I wanted
out of plist was to switch between a regular list , and a plist easily.
You seem to add something to that, and take something away. Like you
remove a lot of the API which makes it less similar to a regular list .

Also, making any changes to the internals of the plist structure outside
of plist.c (or similar) isn't acceptable. For instance you set the node
priority in several places, that should be hidden inside another
function or macro. That makes it easier for people to change the
internal structure without treading though tons of code. 

Changing plist_empty() doesn't make any sense to me. Also changing
dp_node to prio_list doesn't make much sense either.

Daniel

On Sun, 2005-12-18 at 21:17 +0300, Oleg Nesterov wrote:
> This patch blindly fixes compilation errors caused by
> a previous patch.
> 
>  include/linux/rt_lock.h   |    8 ++--
>  include/linux/sched.h     |    2 -
>  include/linux/init_task.h |    2 -
>  kernel/fork.c             |    2 -
>  kernel/rt.c               |   78 ++++++++++++++++++++--------------------------
>  5 files changed, 42 insertions(+), 50 deletions(-)
> 
> Signed-off-by: Oleg Nesterov <oleg@tv-sign.ru>
> 
> --- RT/include/linux/rt_lock.h~3_FIX	2005-12-17 19:59:45.000000000 +0300
> +++ RT/include/linux/rt_lock.h	2005-12-18 22:23:40.000000000 +0300
> @@ -24,7 +24,7 @@
>   */
>  struct rt_mutex {
>  	raw_spinlock_t		wait_lock;
> -	struct plist		wait_list;
> +	struct pl_head		wait_list;
>  	struct thread_info	*owner;
>  # ifdef CONFIG_DEBUG_RT_LOCKING_MODE
>  	raw_spinlock_t		debug_slock;
> @@ -49,8 +49,8 @@ struct rt_mutex {
>   */
>  struct rt_mutex_waiter {
>  	struct rt_mutex		*lock;
> -	struct plist		list;
> -	struct plist		pi_list;
> +	struct pl_node		list;
> +	struct pl_node		pi_list;
>  	struct thread_info	*ti;
>  #ifdef CONFIG_DEBUG_DEADLOCKS
>  	unsigned long eip;
> @@ -87,7 +87,7 @@ struct rt_mutex_waiter {
>  # define __PLIST_INIT(lockname)
>  #else
>  # define __PLIST_INIT(lockname) \
> -	, .wait_list = PLIST_INIT((lockname).wait_list, 140 /*MAX_PRIO*/)
> +	, .wait_list = PL_HEAD_INIT((lockname).wait_list)
>  #endif
>  
>  #define __RT_MUTEX_INITIALIZER(lockname) \
> --- RT/include/linux/sched.h~3_FIX	2005-12-17 19:59:45.000000000 +0300
> +++ RT/include/linux/sched.h	2005-12-18 00:21:43.000000000 +0300
> @@ -1026,7 +1026,7 @@ struct task_struct {
>  #endif
>  	/* realtime bits */
>  	struct list_head delayed_put;
> -	struct plist pi_waiters;
> +	struct pl_head pi_waiters;
>  
>  	/* RT deadlock detection and priority inheritance handling */
>  	struct rt_mutex_waiter *blocked_on;
> --- RT/include/linux/init_task.h~3_FIX	2005-12-17 19:59:45.000000000 +0300
> +++ RT/include/linux/init_task.h	2005-12-18 00:27:31.000000000 +0300
> @@ -121,7 +121,7 @@ extern struct group_info init_groups;
>  	.alloc_lock	= SPIN_LOCK_UNLOCKED(tsk.alloc_lock),		\
>  	.proc_lock	= SPIN_LOCK_UNLOCKED(tsk.proc_lock),		\
>  	.delayed_put	= LIST_HEAD_INIT(tsk.delayed_put),		\
> -	.pi_waiters	= PLIST_INIT(tsk.pi_waiters, MAX_PRIO),		\
> +	.pi_waiters	= PL_HEAD_INIT(tsk.pi_waiters),			\
>  	.pi_lock	= RAW_SPIN_LOCK_UNLOCKED,			\
>  	.journal_info	= NULL,						\
>  	.cpu_timers	= INIT_CPU_TIMERS(tsk.cpu_timers),		\
> --- RT/kernel/fork.c~3_FIX	2005-12-17 19:59:45.000000000 +0300
> +++ RT/kernel/fork.c	2005-12-18 00:55:41.000000000 +0300
> @@ -1027,7 +1027,7 @@ static task_t *copy_process(unsigned lon
>  #endif
>  	INIT_LIST_HEAD(&p->delayed_put);
>  	preempt_disable();
> -	plist_init(&p->pi_waiters, MAX_PRIO);
> +	pl_head_init(&p->pi_waiters);
>  	preempt_enable();
>  	p->blocked_on = NULL; /* not blocked yet */
>  	spin_lock_init(&p->pi_lock);
> --- RT/kernel/rt.c~3_FIX	2005-12-17 19:59:45.000000000 +0300
> +++ RT/kernel/rt.c	2005-12-18 22:03:25.000000000 +0300
> @@ -396,8 +396,8 @@ static void printk_waiter(struct rt_mute
>  {
>  	printk("-------------------------\n");
>  	printk("| waiter struct %p:\n", w);
> -	printk("| w->list: [DP:%p/%p|SP:%p/%p|PRI:%d]\n", w->list.dp_node.prev, w->list.dp_node.next, w->list.sp_node.prev, w->list.sp_node.next, w->list.prio);
> -	printk("| w->pi_list: [DP:%p/%p|SP:%p/%p|PRI:%d]\n", w->pi_list.dp_node.prev, w->pi_list.dp_node.next, w->pi_list.sp_node.prev, w->pi_list.sp_node.next, w->pi_list.prio);
> +	printk("| w->list: [DP:%p/%p|SP:%p/%p|PRI:%d]\n", w->list.plist.prio_list.prev, w->list.plist.prio_list.next, w->list.plist.node_list.prev, w->list.plist.node_list.next, w->list.prio);
> +	printk("| w->pi_list: [DP:%p/%p|SP:%p/%p|PRI:%d]\n", w->pi_list.plist.prio_list.prev, w->pi_list.plist.prio_list.next, w->pi_list.plist.node_list.prev, w->pi_list.plist.node_list.next,
> w->pi_list.prio);
>  	printk("\n| lock:\n");
>  	printk_lock(w->lock, 1);
>  	printk("| w->ti->task:\n");
> @@ -617,7 +617,6 @@ void check_no_held_locks(struct task_str
>  {
>  	struct thread_info *ti = task->thread_info;
>  	struct list_head *curr, *next, *cursor = NULL;
> -	struct plist *curr1;
>  	struct rt_mutex *lock;
>  	struct rt_mutex_waiter *w;
>  	struct thread_info *t;
> @@ -671,8 +670,7 @@ restart:
>  		goto restart;
>  	}
>  	_raw_spin_lock(&task->pi_lock);
> -	plist_for_each(curr1, &task->pi_waiters) {
> -		w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
> +	plist_for_each_entry(w, &task->pi_waiters, pi_list) {
>  		TRACE_OFF();
>  		_raw_spin_unlock(&task->pi_lock);
>  		trace_unlock_irqrestore(&trace_lock, flags, ti);
> @@ -734,13 +732,11 @@ check_pi_list_present(struct rt_mutex *l
>  		      struct thread_info *old_owner)
>  {
>  	struct rt_mutex_waiter *w;
> -	struct plist *curr1;
>  
>  	_raw_spin_lock(&old_owner->task->pi_lock);
> -	TRACE_WARN_ON_LOCKED(plist_empty(&waiter->pi_list));
> +	TRACE_WARN_ON_LOCKED(plist_unhashed(&waiter->pi_list));
>  
> -	plist_for_each(curr1, &old_owner->task->pi_waiters) {
> -		w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
> +	plist_for_each_entry(w, &old_owner->task->pi_waiters, pi_list) {
>  		if (w == waiter)
>  			goto ok;
>  	}
> @@ -754,11 +750,9 @@ static void
>  check_pi_list_empty(struct rt_mutex *lock, struct thread_info *old_owner)
>  {
>  	struct rt_mutex_waiter *w;
> -	struct plist *curr1;
>  
>  	_raw_spin_lock(&old_owner->task->pi_lock);
> -	plist_for_each(curr1, &old_owner->task->pi_waiters) {
> -		w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
> +	plist_for_each_entry(w, &old_owner->task->pi_waiters, pi_list) {
>  		if (w->lock == lock) {
>  			TRACE_OFF();
>  			printk("hm, PI interest but no waiter? Old owner:\n");
> @@ -793,8 +787,7 @@ static void
>  change_owner(struct rt_mutex *lock, struct thread_info *old_owner,
>  	     struct thread_info *new_owner)
>  {
> -	struct plist *next1, *curr1;
> -	struct rt_mutex_waiter *w;
> +	struct rt_mutex_waiter *w, *tmp;
>  	int requeued = 0, sum = 0;
>  
>  	if (old_owner == new_owner)
> @@ -802,12 +795,11 @@ change_owner(struct rt_mutex *lock, stru
>  
>  	SMP_TRACE_BUG_ON_LOCKED(!spin_is_locked(&old_owner->task->pi_lock));
>  	SMP_TRACE_BUG_ON_LOCKED(!spin_is_locked(&new_owner->task->pi_lock));
> -	plist_for_each_safe(curr1, next1, &old_owner->task->pi_waiters) {
> -		w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
> +	plist_for_each_entry_safe(w, tmp, &old_owner->task->pi_waiters, pi_list) {
>  		if (w->lock == lock) {
>  			trace_special_pid(w->ti->task->pid, w->ti->task->prio, w->ti->task->normal_prio);
> -			plist_del(&w->pi_list, &old_owner->task->pi_waiters);
> -			plist_init(&w->pi_list, w->ti->task->prio);
> +			plist_del(&w->pi_list);
> +			w->pi_list.prio = w->ti->task->prio;
>  			plist_add(&w->pi_list, &new_owner->task->pi_waiters);
>  			requeued++;
>  		}
> @@ -917,7 +909,7 @@ static void pi_setprio(struct rt_mutex *
>  
>  		TRACE_BUG_ON_LOCKED(!lock_owner(l));
>  
> -		if (!plist_empty(&w->pi_list)) {
> +		if (!plist_unhashed(&w->pi_list)) {
>  			TRACE_BUG_ON_LOCKED(!was_rt && !ALL_TASKS_PI && !rt_task(p));
>  			/*
>  			 * If the task is blocked on a lock, and we just restored
> @@ -927,17 +919,17 @@ static void pi_setprio(struct rt_mutex *
>  			 * (TODO: this can be unfair to SCHED_NORMAL tasks if they
>  			 *        get PI handled.)
>  			 */
> -			plist_del(&w->pi_list, &lock_owner(l)->task->pi_waiters);
> +			plist_del(&w->pi_list);
>  		} else
>  			TRACE_BUG_ON_LOCKED((ALL_TASKS_PI || rt_task(p)) && was_rt);
>  
>  		if (ALL_TASKS_PI || rt_task(p)) {
> -			plist_init(&w->pi_list,prio);
> +			w->pi_list.prio = prio;
>  			plist_add(&w->pi_list, &lock_owner(l)->task->pi_waiters);
>  		}
>  
> -		plist_del(&w->list, &l->wait_list);
> -		plist_init(&w->list, prio);
> +		plist_del(&w->list);
> +		w->list.prio = prio;
>  		plist_add(&w->list, &l->wait_list);
>  
>  		pi_walk++;
> @@ -1028,7 +1020,7 @@ task_blocks_on_lock(struct rt_mutex_wait
>  	task->blocked_on = waiter;
>  	waiter->lock = lock;
>  	waiter->ti = ti;
> -	plist_init(&waiter->pi_list, task->prio);
> +	pl_node_init(&waiter->pi_list, task->prio);
>  	/*
>  	 * Add SCHED_NORMAL tasks to the end of the waitqueue (FIFO):
>  	 */
> @@ -1067,7 +1059,7 @@ static void __init_rt_mutex(struct rt_mu
>  	lock->owner = NULL;
>  	spin_lock_init(&lock->wait_lock);
>  	preempt_disable();
> -	plist_init(&lock->wait_list, MAX_PRIO);
> +	pl_head_init(&lock->wait_list);
>  	preempt_enable();
>  #ifdef CONFIG_DEBUG_DEADLOCKS
>  	lock->save_state = save_state;
> @@ -1178,9 +1170,9 @@ pick_new_owner(struct rt_mutex *lock, st
>  #endif
>  		_raw_spin_lock(&old_owner->task->pi_lock);
>  
> -	plist_del_init(&waiter->list, &lock->wait_list);
> -	plist_del(&waiter->pi_list, &old_owner->task->pi_waiters);
> -	plist_init(&waiter->pi_list, waiter->ti->task->prio);
> +	plist_del(&waiter->list);
> +	plist_del(&waiter->pi_list);
> +	waiter->pi_list.prio = waiter->ti->task->prio;
>  
>  	set_new_owner(lock, old_owner, new_owner __W_EIP__(waiter));
>  	/* Don't touch waiter after ->task has been NULLed */
> @@ -1203,8 +1195,8 @@ static inline void init_lists(struct rt_
>  {
>  #if defined(CONFIG_SMP) || defined(CONFIG_DEBUG_DEADLOCKS)
>  	// we have to do this until the static initializers get fixed:
> -	if (unlikely(!lock->wait_list.dp_node.prev)) {
> -		plist_init(&lock->wait_list, MAX_PRIO);
> +	if (unlikely(!lock->wait_list.prio_list.prev)) {
> +		pl_head_init(&lock->wait_list);
>  #ifdef CONFIG_DEBUG_DEADLOCKS
>  		pi_initialized++;
>  #endif
> @@ -1334,8 +1326,8 @@ capture_lock(struct rt_mutex_waiter *wai
>  			ret = 0;
>  		} else {
>  			/* Add ourselves back to the list */
> -			TRACE_BUG_ON_LOCKED(!plist_empty(&waiter->list));
> -			plist_init(&waiter->list, task->prio);
> +			TRACE_BUG_ON_LOCKED(!plist_unhashed(&waiter->list));
> +			pl_node_init(&waiter->list, task->prio);
>  			task_blocks_on_lock(waiter, ti, lock __W_EIP__(waiter));
>  			ret = 1;
>  		}
> @@ -1355,16 +1347,16 @@ static inline void INIT_WAITER(struct rt
>  {
>  #ifdef CONFIG_DEBUG_DEADLOCKS
>  	memset(waiter, 0x11, sizeof(*waiter));
> -	plist_init(&waiter->list, MAX_PRIO);
> -	plist_init(&waiter->pi_list, MAX_PRIO);
> +	pl_node_init(&waiter->list, MAX_PRIO);
> +	pl_node_init(&waiter->pi_list, MAX_PRIO);
>  #endif
>  }
>  
>  static inline void FREE_WAITER(struct rt_mutex_waiter *waiter)
>  {
>  #ifdef CONFIG_DEBUG_DEADLOCKS
> -	TRACE_WARN_ON(!plist_empty(&waiter->list));
> -	TRACE_WARN_ON(!plist_empty(&waiter->pi_list));
> +	TRACE_WARN_ON(!plist_unhashed(&waiter->list));
> +	TRACE_WARN_ON(!plist_unhashed(&waiter->pi_list));
>  	TRACE_WARN_ON(current->blocked_on);
>  	memset(waiter, 0x22, sizeof(*waiter));
>  #endif
> @@ -1409,7 +1401,7 @@ ____down(struct rt_mutex *lock __EIP_DEC
>  
>  	set_task_state(task, TASK_UNINTERRUPTIBLE);
>  
> -	plist_init(&waiter.list, task->prio);
> +	pl_node_init(&waiter.list, task->prio);
>  	task_blocks_on_lock(&waiter, ti, lock __EIP__);
>  
>  	TRACE_BUG_ON_LOCKED(!raw_irqs_disabled());
> @@ -1490,7 +1482,7 @@ ____down_mutex(struct rt_mutex *lock __E
>  		return;
>  	}
>  
> -	plist_init(&waiter.list, task->prio);
> +	pl_node_init(&waiter.list, task->prio);
>  	task_blocks_on_lock(&waiter, ti, lock __EIP__);
>  
>  	TRACE_BUG_ON_LOCKED(!raw_irqs_disabled());
> @@ -1589,7 +1581,7 @@ ____up_mutex(struct rt_mutex *lock, int 
>  	trace_lock_irqsave(&trace_lock, flags, ti);
>  	TRACE_BUG_ON_LOCKED(!raw_irqs_disabled());
>  	_raw_spin_lock(&lock->wait_lock);
> -	TRACE_BUG_ON_LOCKED(!lock->wait_list.dp_node.prev && !lock->wait_list.dp_node.next);
> +	TRACE_BUG_ON_LOCKED(!lock->wait_list.prio_list.prev && !lock->wait_list.prio_list.next);
>  
>  #ifdef CONFIG_DEBUG_DEADLOCKS
>  	TRACE_WARN_ON_LOCKED(lock_owner(lock) != ti);
> @@ -1873,7 +1865,7 @@ static int __sched __down_interruptible(
>  
>  	set_task_state(task, TASK_INTERRUPTIBLE);
>  
> -	plist_init(&waiter.list, task->prio);
> +	pl_node_init(&waiter.list, task->prio);
>  	task_blocks_on_lock(&waiter, ti, lock __EIP__);
>  
>  	TRACE_BUG_ON_LOCKED(!raw_irqs_disabled());
> @@ -1908,7 +1900,7 @@ wait_again:
>  			_raw_spin_lock(&task->pi_lock);
>  			_raw_spin_lock(&lock->wait_lock);
>  			if (waiter.ti || time) {
> -				plist_del_init(&waiter.list, &lock->wait_list);
> +				plist_del(&waiter.list);
>  				/*
>  				 * Just remove ourselves from the PI list.
>  				 * (No big problem if our PI effect lingers
> @@ -1916,8 +1908,8 @@ wait_again:
>  				 */
>  				TRACE_WARN_ON_LOCKED(waiter.ti != ti);
>  				TRACE_WARN_ON_LOCKED(current->blocked_on != &waiter);
> -				plist_del(&waiter.pi_list, &task->pi_waiters);
> -				plist_init(&waiter.pi_list, task->prio);
> +				plist_del(&waiter.pi_list);
> +				waiter.pi_list.prio = task->prio;
>  				waiter.ti = NULL;
>  				current->blocked_on = NULL;
>  				if (time) {

Re: [PATCH rc5-rt2 3/3] plist: convert the code to newimplementation

[Oleg Nesterov]

Daniel Walker wrote:
> 
> I think firstly, if you want to have success with this patch you'll need
> to clean it up a bit. I'm not an authority on clean code , but below
> isn't clean to my eyes.

Cleanups are always good, I am open to any suggestions.

>                         However, this is cleaner than your last
> attempt .

Thanks, but it was NOT changed from my last attempt. Just rediff.

> Hard coding MAX_PRIO isn't really acceptable.

I don't do that? Could you clarify?

>                                               If your going to make it
> more similar to list_head , why not name it plist_head instead of
> pl_head that way it's easy to switch between them.

I don't mind to rename, probably plist_head is better. I'd like to know
Ingo's opinion first.

>                                                              Like you
> remove a lot of the API which makes it less similar to a regular list .

For example?

> Also, making any changes to the internals of the plist structure outside
> of plist.c (or similar) isn't acceptable. For instance you set the node
> priority in several places, that should be hidden inside another
> function or macro. That makes it easier for people to change the
> internal structure without treading though tons of code.

Agreed, I already thought it makes sense to add plist_add_prio() helper.
Note that ->prio is set directly mostly right before plist_add() call.

> Changing plist_empty() doesn't make any sense to me.

plist_empty(head) means this list empty. plist_unhashed(node) means
this node is not on list. 

>                                                       Also changing
> dp_node to prio_list doesn't make much sense either.

Again, this patch is unchanged. I don't mind to rename, but recall
that it was sent before the current implementation become functional.
And honestly I don't like 'sp_node', this name is misleading, and
reflects first buggy implementation. It should be called 'all_nodes'
or something like this.

Oleg.