patch] Real-Time Preemption, plist fixes

patch] Real-Time Preemption, plist fixes

[Thomas Gleixner]

The patch fixes a couple of really annoying issues in the PI code of the
Real-Time-Preemption patch

1. Fix the insertion order according to the specified intentions

The desired action was inserting in descending priority and FIFO mode
for matching priority. The resulting action of the code was inserting in
descending priority and inverse FIFO mode for matching priority. 

2. Add the proper list_head initializer in the replacement path.

3. Remove the bogus checks in the delete function for 
 A. !list_empty(&pl->sp_node)
 B. else if (pl->prio == pl_new->prio)

Those checks just covered the dumbest implementation detail of plist at
all. See 4.)

4. Make plist_entry() work as expected by anybody who ever used
list_entry(). Add a plist_first_entry macro for those places where the
provided functionality was accidentaly correct.

Application example:

plist_for_each_safe(curr1, next1, &old_owner->pi_waiters) {
	w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
	.....
}

A moderate experienced Linux programmer would expect, that
plist_entry(curr1,...) returns the first entry of the list
&old_owner->pi_waiters. Looking into the plist_entry macro after
spending hours of witchcrafting reviels that the result is the next
entry of the first entry of the list.

#define plist_entry(ptr, type, member) \
	container_of(plist_first(ptr), type, member)

No further comment necessary.

5. Modify the comments in the header file to explain the real intention
of the implemenation.

Changing fundamental implemtation details and keeping the original
comments is just provoking false assumptions. I apologize hereby for all
maledictions I addressed to the original author.

Signed-off-by: Thomas Gleixner <tglx@linutronix.de>

Index linux/lib/plist.c
===================================================================
--- linux/lib/plist.c	(revision 434)
+++ linux/lib/plist.c	(working copy)
@@ -9,6 +9,10 @@
  * 2001-2005 (c) MontaVista Software, Inc.
  * Daniel Walker <dwalker@mvista.com>
  *
+ * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
+ * Tested and made it functional. I'm still pondering if it is
+ * worth the trouble.
+ *
  * Licensed under the FSF's GNU Public License v2 or later.
  *
  * Based on simple lists (include/linux/list.h).
@@ -17,6 +21,7 @@
 #include <linux/sched.h>
 #include <linux/rt_lock.h>
 
+
 /* Initialize a pl */
 void plist_init(struct plist *pl, int prio)
 {
@@ -63,7 +68,6 @@
 	struct list_head *itr;
 	struct plist *itr_pl, *itr_pl2;
 
-
 	if (pl->prio < INT_MAX) {
 		list_for_each(itr, &plist->dp_node) {
 			itr_pl = list_entry(itr, struct plist, dp_node);
@@ -82,13 +86,12 @@
 	itr_pl = plist;
 
 new_sp_head:
-	itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
 	list_add_tail(&pl->dp_node, &itr_pl->dp_node);
-	list_add(&pl->sp_node, &itr_pl2->sp_node);
+	list_add_tail(&pl->sp_node, &itr_pl->sp_node);
 	return;
 existing_sp_head:
-	itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
-	list_add(&pl->sp_node, &itr_pl2->sp_node);
+	itr_pl2 = container_of(itr_pl->dp_node.next, struct plist, dp_node);
+	list_add_tail(&pl->sp_node, &itr_pl2->sp_node);
 	return;
 }
 
@@ -107,22 +110,21 @@
 	return 0;
 }
 
-
 /* Grunt to do the real removal work of @pl from the plist. */
 static inline
-void __plist_del(struct plist *pl)
+void  __plist_del(struct plist *pl)
 {
-	if (!list_empty(&pl->sp_node) && !list_empty(&pl->dp_node)) {
-		/* SP list head, not empty */
-		struct plist *pl_new = container_of(pl->sp_node.prev,
-							struct plist, sp_node);
-
-		if (pl->dp_node.prev == &pl_new->dp_node) {
+	if (!list_empty(&pl->dp_node)) {
+		struct plist *pl_new = container_of(pl->sp_node.next,
+						    struct plist, sp_node);
+	
+		if (pl->dp_node.next == &pl_new->dp_node) {
 			/* end of this priorities list */
 			list_del_init(&pl->dp_node);
-		} else if (pl->prio == pl_new->prio) {
+		} else {
 			list_replace_rcu(&pl->dp_node, &pl_new->dp_node);
-		} 
+			INIT_LIST_HEAD(&pl->dp_node);
+		}
 	}
 	list_del_init(&pl->sp_node);
 }
@@ -162,7 +164,7 @@
  */
 unsigned plist_chprio(struct plist *plist, struct plist *pl, int new_prio)
 {
-	if (new_prio == plist->prio)
+	if (new_prio == pl->prio)
 		return 0;
 
 	__plist_chprio(pl, new_prio);

Index linux/include/linux/plist.h
===================================================================
--- linux/include/linux/plist.h	(revision 426)
+++ linux/include/linux/plist.h	(working copy)
@@ -7,6 +7,11 @@
  * 2001-2005 (c) MontaVista Software, Inc.
  * Daniel Walker <dwalker@mvista.com>
  *
+ * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
+ * Tested and made it functional. Removed the bogus O(1)
+ * claim from the comment and put some understandable
+ * explanation in it.
+ *
  * Licensed under the FSF's GNU Public License v2 or later.
  *
  * Based on simple lists (include/linux/list.h).
@@ -17,35 +22,50 @@
  * a priority too (the highest of all the nodes), stored in the head
  * of the list (that is a node itself).
  *
- * Addition is O(1), removal is O(1), change of priority of a node is
- * O(1).
+ * Addition is O(N), removal is O(1), change of priority of a node is
+ * O(N).
  *
- * Addition and change of priority's order is really O(K), where K is
- * a constant being the maximum number of different priorities you
- * will store in the list. Being a constant, it means it is O(1).
- *
  * This list is really a list of lists:
  *
  *  - The tier 1 list is the dp list (Different Priority)
  *
- *  - The tier 2 list is the sp list (Same Priority)
+ *  - The tier 2 list is the sp list (Serialized Priority)
  *
- * All the nodes in a SP list have the same priority, and all the DP
- * lists have different priorities (and are sorted by priority, of
- * course).
+ * Simple ASCII art explanation:
  *
- * Addition means: look for the DP node in the DP list for the
- * priority of the node and append to the SP list corresponding to
- * that node. If it is the first node of that priority, add it to the
- * DP list in the right position and it will be the head of the SP
- * list for his priority.
+ * |HEAD   |
+ * |       |
+ * |dp.prev|<------------------------------------|   
+ * |dp.next|<->|dp|<->|dp|<--------------->|dp|<-|
+ * |10     |   |10|   |21|   |21|   |21|   |40|   (prio)
+ * |       |   |  |   |  |   |  |   |  |   |  |
+ * |       |   |  |   |  |   |  |   |  |   |  |
+ * |sp.next|<->|sp|<->|sp|<->|sp|<->|sp|<->|sp|<-|
+ * |sp.prev|<------------------------------------|   
  *
- * Removal means remove it from the SP list corresponding to its
- * prio. If it is the only one, it means its also the head and thus a
- * DP node, so we remove it from the DP list. If it is the head but
- * there are others in its SP list, then we remove it from both and
- * get the first one of the SP list to be the new head.
+ * The nodes on the dp list are sorted by priority to simplify
+ * the insertion of new nodes. There are no nodes with duplicate 
+ * priorites on the list.
  *
+ * The nodes on the sp list are ordered by priority and can contain
+ * entries which have the same priority. Those entries are ordered
+ * FIFO
+ * 
+ * Addition means: look for the dp node in the dp list for the
+ * priority of the node and insert it before the sp entry of the next 
+ * dp node. If it is the first node of that priority, add it to the
+ * dp list in the right position and insert it into the serialized
+ * sp list
+ *
+ * Removal means remove it from the sp list and remove it from the dp
+ * list if the dp list_head is non empty. In case of removal from the 
+ * dp list it must be checked whether other entries of the same 
+ * priority are on the list or not. If there is another entry of
+ * the same priority then this entry has to replace the
+ * removed entry on the dp list. If the entry which is removed is 
+ * the only entry of this priority then a simple remove from both
+ * list is sufficient.
+ *
  * INT_MIN is the highest priority, 0 is the medium highest, INT_MAX
  * is lowest priority.
  *
@@ -83,7 +103,17 @@
  * @member:     the name of the list_struct within the struct.
  */
 #define plist_entry(ptr, type, member) \
+        container_of(ptr, type, member)
+
+/**
+ * plist_first_entry - get the struct for the first entry
+ * @ptr:        the &struct plist pointer.
+ * @type:       the type of the struct this is embedded in.
+ * @member:     the name of the list_struct within the struct.
+ */
+#define plist_first_entry(ptr, type, member) \
         container_of(plist_first(ptr), type, member)
+
 /**
  * plist_for_each  -       iterate over the plist
  * @pos1:        the type * to use as a loop counter.

Index linux/kernel/rt.c
===================================================================
--- linux/kernel/rt.c	(revision 426)
+++ linux/kernel/rt.c	(working copy)
@@ -773,7 +773,7 @@
 	 *
 	 * (same-prio RT tasks go FIFO)
 	 */
-	waiter = plist_entry(&lock->wait_list, struct rt_mutex_waiter, list);
+	waiter = plist_first_entry(&lock->wait_list, struct rt_mutex_waiter, list);
 
 	trace_special_pid(waiter->task->pid, waiter->task->prio, 0);
 
@@ -1351,7 +1351,7 @@
 	 */
 	prio = mutex_getprio(old_owner);
 	if (!plist_empty(&old_owner->pi_waiters)) {
-		w = plist_entry(&old_owner->pi_waiters, struct rt_mutex_waiter, pi_list);
+		w = plist_first_entry(&old_owner->pi_waiters, struct rt_mutex_waiter, pi_list);
 		if (w->task->prio < prio)
 			prio = w->task->prio;
 	}

Re: patch] Real-Time Preemption, plist fixes

[Daniel Walker]

On Sun, 5 Jun 2005, Thomas Gleixner wrote:

> The patch fixes a couple of really annoying issues in the PI code of the
> Real-Time-Preemption patch

You mean really annoying in the plist code?
 
> 1. Fix the insertion order according to the specified intentions
> 
> The desired action was inserting in descending priority and FIFO mode
> for matching priority. The resulting action of the code was inserting in
> descending priority and inverse FIFO mode for matching priority. 

This is good.
 
> 2. Add the proper list_head initializer in the replacement path.

Not sure what you mean here.
 
> 3. Remove the bogus checks in the delete function for 
>  A. !list_empty(&pl->sp_node)
>  B. else if (pl->prio == pl_new->prio)
> 
> Those checks just covered the dumbest implementation detail of plist at
> all. See 4.)
> 
> 4. Make plist_entry() work as expected by anybody who ever used
> list_entry(). Add a plist_first_entry macro for those places where the
> provided functionality was accidentaly correct.
> 
> Application example:
> 
> plist_for_each_safe(curr1, next1, &old_owner->pi_waiters) {
> 	w = plist_entry(curr1, struct rt_mutex_waiter, pi_list);
> 	.....
> }
> 
> A moderate experienced Linux programmer would expect, that
> plist_entry(curr1,...) returns the first entry of the list
> &old_owner->pi_waiters. Looking into the plist_entry macro after
> spending hours of witchcrafting reviels that the result is the next
> entry of the first entry of the list.
> 
> #define plist_entry(ptr, type, member) \
> 	container_of(plist_first(ptr), type, member)
> 
> No further comment necessary.

I already released a patch to fix this.
 
> 5. Modify the comments in the header file to explain the real intention
> of the implemenation.
> 
> Changing fundamental implemtation details and keeping the original
> comments is just provoking false assumptions. I apologize hereby for all
> maledictions I addressed to the original author.

You should wait till it's stable before you finalize the documentation.

> + * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
> + * Tested and made it functional. I'm still pondering if it is
> + * worth the trouble.
> + *

Gimme a break Thomas..

Daniel

Plist cleanup on RT

[Daniel Walker]

	This includes a change from Thomas Gleixner to make the sp_nodes 
FIFO ordered, plus some other small code changes and some small 
documentation cleanup.

	I fixed plist_entry() to work more like list_entry() , and made 
the proper update to kernel/rt.c .


	Oleg, do you have any correctness concerns with this patch?


Daniel



Index: linux-2.6.11/include/linux/plist.h
===================================================================
--- linux-2.6.11.orig/include/linux/plist.h	2005-06-05 01:32:38.000000000 +0000
+++ linux-2.6.11/include/linux/plist.h	2005-06-05 01:44:50.000000000 +0000
@@ -7,6 +7,8 @@
  * 2001-2005 (c) MontaVista Software, Inc.
  * Daniel Walker <dwalker@mvista.com>
  *
+ * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
+ *
  * Licensed under the FSF's GNU Public License v2 or later.
  *
  * Based on simple lists (include/linux/list.h).
@@ -28,11 +30,14 @@
  *
  *  - The tier 1 list is the dp list (Different Priority)
  *
- *  - The tier 2 list is the sp list (Same Priority)
+ *  - The tier 2 list is the sp list (Serialized Priority)
+ *
+ * The nodes on the sp list are ordered by priority and can contain
+ * entries which have the same priority. Those entries are ordered
+ * FIFO.
  *
- * All the nodes in a SP list have the same priority, and all the DP
- * lists have different priorities (and are sorted by priority, of
- * course).
+ * The DP lists have different priorities (and are sorted by priority, 
+ * of course).
  *
  * Addition means: look for the DP node in the DP list for the
  * priority of the node and append to the SP list corresponding to
@@ -83,7 +88,7 @@ struct plist {
  * @member:     the name of the list_struct within the struct.
  */
 #define plist_entry(ptr, type, member) \
-        container_of(plist_first(ptr), type, member)
+        container_of(ptr, type, member)
 /**
  * plist_for_each  -       iterate over the plist
  * @pos1:        the type * to use as a loop counter.
Index: linux-2.6.11/kernel/rt.c
===================================================================
--- linux-2.6.11.orig/kernel/rt.c	2005-06-05 01:32:38.000000000 +0000
+++ linux-2.6.11/kernel/rt.c	2005-06-05 01:33:20.000000000 +0000
@@ -773,7 +773,7 @@ static inline struct task_struct * pick_
 	 *
 	 * (same-prio RT tasks go FIFO)
 	 */
-	waiter = plist_entry(&lock->wait_list, struct rt_mutex_waiter, list);
+	waiter = plist_entry(plist_first(&lock->wait_list), struct rt_mutex_waiter, list);
 
 	trace_special_pid(waiter->task->pid, waiter->task->prio, 0);
 
@@ -1351,7 +1351,7 @@ static void __up_mutex(struct rt_mutex *
 	 */
 	prio = mutex_getprio(old_owner);
 	if (!plist_empty(&old_owner->pi_waiters)) {
-		w = plist_entry(&old_owner->pi_waiters, struct rt_mutex_waiter, pi_list);
+		w = plist_entry(plist_first(&old_owner->pi_waiters), struct rt_mutex_waiter, pi_list);
 		if (w->task->prio < prio)
 			prio = w->task->prio;
 	}
Index: linux-2.6.11/lib/plist.c
===================================================================
--- linux-2.6.11.orig/lib/plist.c	2005-06-05 01:33:15.000000000 +0000
+++ linux-2.6.11/lib/plist.c	2005-06-05 01:33:34.000000000 +0000
@@ -9,6 +9,8 @@
  * 2001-2005 (c) MontaVista Software, Inc.
  * Daniel Walker <dwalker@mvista.com>
  *
+ * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
+ *
  * Licensed under the FSF's GNU Public License v2 or later.
  *
  * Based on simple lists (include/linux/list.h).
@@ -80,13 +82,12 @@ static inline void __plist_add_sorted(st
 	itr_pl = plist;
 
 new_sp_head:
-	itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
 	list_add_tail(&pl->dp_node, &itr_pl->dp_node);
-	list_add(&pl->sp_node, &itr_pl2->sp_node);
+	list_add_tail(&pl->sp_node, &itr_pl->sp_node);
 	return;
 existing_sp_head:
-	itr_pl2 = container_of(itr_pl->dp_node.prev, struct plist, dp_node);
-	list_add(&pl->sp_node, &itr_pl2->sp_node);
+	itr_pl2 = container_of(itr_pl->dp_node.next, struct plist, dp_node);
+	list_add_tail(&pl->sp_node, &itr_pl2->sp_node);
 	return;
 }
 
@@ -110,16 +111,17 @@ unsigned plist_add(struct plist *pl, str
 static inline
 void __plist_del(struct plist *pl)
 {
-	if (!list_empty(&pl->sp_node) && !list_empty(&pl->dp_node)) {
+	if (!list_empty(&pl->sp_node)) {
 		/* SP list head, not empty */
-		struct plist *pl_new = container_of(pl->sp_node.prev,
+		struct plist *pl_new = container_of(pl->sp_node.next,
 							struct plist, sp_node);
 
-		if (pl->dp_node.prev == &pl_new->dp_node) {
+		if (pl->dp_node.next == &pl_new->dp_node) {
 			/* end of this priorities list */
 			list_del_init(&pl->dp_node);
-		} else if (pl->prio == pl_new->prio) {
+		} else {
 			list_replace_rcu(&pl->dp_node, &pl_new->dp_node);
+			INIT_LIST_HEAD(&pl->dp_node);
 		} 
 	}
 	list_del_init(&pl->sp_node);
@@ -160,7 +162,7 @@ void __plist_chprio(struct plist *pl, in
  */
 unsigned plist_chprio(struct plist *plist, struct plist *pl, int new_prio)
 {
-	if (new_prio == plist->prio)
+	if (new_prio == pl->prio)
 		return 0;
 
 	__plist_chprio(pl, new_prio);

Re: patch] Real-Time Preemption, plist fixes

[Esben Nielsen]

On Sun, 5 Jun 2005, Thomas Gleixner wrote:

> [...] 
>   *
>   * Based on simple lists (include/linux/list.h).
> @@ -17,35 +22,50 @@
>   * a priority too (the highest of all the nodes), stored in the head
>   * of the list (that is a node itself).
>   *
> - * Addition is O(1), removal is O(1), change of priority of a node is
> - * O(1).
> + * Addition is O(N), removal is O(1), change of priority of a node is
> + * O(N).
>   *
> - * Addition and change of priority's order is really O(K), where K is
> - * a constant being the maximum number of different priorities you
> - * will store in the list. Being a constant, it means it is O(1).
> - *

What is N? The number of nodes in the list or the number of different
priorities? If it is the number of nodes in total this exercise is
worthless: You could just as well have a sorted list.

But I hope and also think that the original explanation was correct.

Esben

Re: patch] Real-Time Preemption, plist fixes

[Thomas Gleixner]

On Sun, 2005-06-05 at 09:58 +0200, Esben Nielsen wrote:
> On Sun, 5 Jun 2005, Thomas Gleixner wrote:
> 
> > [...] 
> >   *
> >   * Based on simple lists (include/linux/list.h).
> > @@ -17,35 +22,50 @@
> >   * a priority too (the highest of all the nodes), stored in the head
> >   * of the list (that is a node itself).
> >   *
> > - * Addition is O(1), removal is O(1), change of priority of a node is
> > - * O(1).
> > + * Addition is O(N), removal is O(1), change of priority of a node is
> > + * O(N).
> >   *
> > - * Addition and change of priority's order is really O(K), where K is
> > - * a constant being the maximum number of different priorities you
> > - * will store in the list. Being a constant, it means it is O(1).
> > - *
> 
> What is N? The number of nodes in the list or the number of different
> priorities? If it is the number of nodes in total this exercise is
> worthless: You could just as well have a sorted list.
> 
> But I hope and also think that the original explanation was correct.

Sorry, I meant K the number of different priorities. 

I just find it completely bogus, that O(K) == O(1) for any K != 1. 

tglx

Re: patch] Real-Time Preemption, plist fixes

[Ingo Molnar]

* Thomas Gleixner <tglx@linutronix.de> wrote:

> 5. [...]

#6 looks pretty significant too:

>  unsigned plist_chprio(struct plist *plist, struct plist *pl, int new_prio)
>  {
> -	if (new_prio == plist->prio)
> +	if (new_prio == pl->prio)
>  		return 0;

right?

	Ingo

Re: patch] Real-Time Preemption, plist fixes

[Thomas Gleixner]

On Sun, 2005-06-05 at 10:18 +0200, Ingo Molnar wrote:
> * Thomas Gleixner <tglx@linutronix.de> wrote:
> 
> > 5. [...]
> 
> #6 looks pretty significant too:
> 
> >  unsigned plist_chprio(struct plist *plist, struct plist *pl, int new_prio)
> >  {
> > -	if (new_prio == plist->prio)
> > +	if (new_prio == pl->prio)
> >  		return 0;
> 
> right?
> 

Yes, forgot to rant about that :)

tglx

Re: [patch] Real-Time Preemption, plist fixes

[Ingo Molnar]

* Thomas Gleixner <tglx@linutronix.de> wrote:

> + * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
> + * Tested and made it functional. I'm still pondering if it is
> + * worth the trouble.

you had a long Saturday night debugging session i guess:

> Date: Sun, 05 Jun 2005 02:17:12 +0200

but i think the fundamental question remains even on Sunday mornings -
is the plist overhead worth it? Compared to the simple sorted list we 
exchange O(nr_RT_tasks_running) for O(nr_RT_levels_used) [which is in 
the 1-100 range], is that a significant practical improvement? By 
overhead i dont just mean cycle cost, but also architectural flexibility 
and maintainability.

in any case, i've added most of your fixes and cleanups (changed the
O(N) to O(K) and explained K) and have released the -47-17 patch.
Daniel, do agree with these changes (in particular the __plist_del()
changes?) and is there anything else missing? It looks like we might be
near the end of the tunnel and plists are really stabilizing.

	Ingo

Re: patch] Real-Time Preemption, plist fixes

[Thomas Gleixner]

On Sat, 2005-06-04 at 17:53 -0700, Daniel Walker wrote:

> You mean really annoying in the plist code?

Usually I mean what I write.
 
> > 2. Add the proper list_head initializer in the replacement path.
> 
> Not sure what you mean here.

      list_replace_rcu(&pl->dp_node, &pl_new->dp_node);
+     INIT_LIST_HEAD(&pl->dp_node);

 
> > 4. Make plist_entry() work as expected by anybody who ever used
> > list_entry(). Add a plist_first_entry macro for those places where the
> > provided functionality was accidentaly correct.
> >
> I already released a patch to fix this.

Nice to know. Where ?

> > 5. Modify the comments in the header file to explain the real intention
> > of the implemenation.
>
> You should wait till it's stable before you finalize the documentation.

Thats plain wrong. Having explanations in place which do not match the
code is worse than no explanation at all.

tglx

Re: patch] Real-Time Preemption, plist fixes

[Esben Nielsen]

On Sun, 5 Jun 2005, Thomas Gleixner wrote:

> On Sun, 2005-06-05 at 09:58 +0200, Esben Nielsen wrote:
> > On Sun, 5 Jun 2005, Thomas Gleixner wrote:
> > 
> > > [...] 
> > >   *
> > >   * Based on simple lists (include/linux/list.h).
> > > @@ -17,35 +22,50 @@
> > >   * a priority too (the highest of all the nodes), stored in the head
> > >   * of the list (that is a node itself).
> > >   *
> > > - * Addition is O(1), removal is O(1), change of priority of a node is
> > > - * O(1).
> > > + * Addition is O(N), removal is O(1), change of priority of a node is
> > > + * O(N).
> > >   *
> > > - * Addition and change of priority's order is really O(K), where K is
> > > - * a constant being the maximum number of different priorities you
> > > - * will store in the list. Being a constant, it means it is O(1).
> > > - *
> > 
> > What is N? The number of nodes in the list or the number of different
> > priorities? If it is the number of nodes in total this exercise is
> > worthless: You could just as well have a sorted list.
> > 
> > But I hope and also think that the original explanation was correct.
> 
> Sorry, I meant K the number of different priorities. 
> 
> I just find it completely bogus, that O(K) == O(1) for any K != 1. 
> 
> tglx
> 

When K is a constant or bounded by a constant (140 in this application)
any function which is O(K) is O(1) per definition of O! 

Esben

Re: patch] Real-Time Preemption, plist fixes

[Ingo Molnar]

* Esben Nielsen <simlo@phys.au.dk> wrote:

> When K is a constant or bounded by a constant (140 in this 
> application) any function which is O(K) is O(1) per definition of O!

technically you are right. But the question is - while K is considered a 
constant, and N (nr_running_RT_tasks) is technically not bounded - in 
practice N is bounded just as much. Have you ever seen any hard-RT 
application that has more than 140 threads _running at the same time_ on 
a single CPU? You can even enforce it to be theoretically bounded, via 
ulimits.

in fact, K and N should be pretty close to each other for most 
applications. I'd be interested in real application scenarios where N is 
much (== more than 10 times) larger than K and plists really matter.

	Ingo

Re: [patch] Real-Time Preemption, plist fixes

[Thomas Gleixner]

On Sun, 2005-06-05 at 10:26 +0200, Ingo Molnar wrote:

> > Date: Sun, 05 Jun 2005 02:17:12 +0200

:)

> but i think the fundamental question remains even on Sunday mornings -
> is the plist overhead worth it? Compared to the simple sorted list we 
> exchange O(nr_RT_tasks_running) for O(nr_RT_levels_used) [which is in 
> the 1-100 range], is that a significant practical improvement? By 
> overhead i dont just mean cycle cost, but also architectural flexibility 
> and maintainability.

That was my question too. 

tglx

Re: [patch] Real-Time Preemption, plist fixes

[Esben Nielsen]

On Sun, 5 Jun 2005, Ingo Molnar wrote:

> * Thomas Gleixner <tglx@linutronix.de> wrote:
> 
> > + * (C) 2005 Thomas Gleixner <tglx@linutronix.de>
> > + * Tested and made it functional. I'm still pondering if it is
> > + * worth the trouble.
> 
> you had a long Saturday night debugging session i guess:
> 
> > Date: Sun, 05 Jun 2005 02:17:12 +0200
> 
> but i think the fundamental question remains even on Sunday mornings -
> is the plist overhead worth it? Compared to the simple sorted list we 
> exchange O(nr_RT_tasks_running) for O(nr_RT_levels_used) [which is in 
> the 1-100 range], is that a significant practical improvement? By 
> overhead i dont just mean cycle cost, but also architectural flexibility 
> and maintainability.
>
Sorted lists works deterministicly O(1) on UP if no owner of the lock
blocks while having the lock. On SMP or worse if an owner blocks in the
lock, the wait list can grow very long. Thus insertion of new elements
takes a long time - with preemption disabled :-(

If this is supposed to be used for user-space PI as well I would say it
would have to be completely bounded, i.e. plists are certainly needed.
If it is in the kernel only, you might argue that the code is under
control and thus not make very long wait-lists. Therefore it is
not worth the extra CPU cycles to use them. However, there is no way
to know for sure. In extreme load situations we could end up with a lot of
waiters on mmap_sem forinstance.

Esben

Re: patch] Real-Time Preemption, plist fixes

[Esben Nielsen]

On Sun, 5 Jun 2005, Ingo Molnar wrote:

> 
> * Esben Nielsen <simlo@phys.au.dk> wrote:
> 
> > When K is a constant or bounded by a constant (140 in this 
> > application) any function which is O(K) is O(1) per definition of O!
> 
> technically you are right. But the question is - while K is considered a 
> constant, and N (nr_running_RT_tasks) is technically not bounded - in 
> practice N is bounded just as much. Have you ever seen any hard-RT 
> application that has more than 140 threads _running at the same time_ on 
> a single CPU? You can even enforce it to be theoretically bounded, via 
> ulimits.
> 
> in fact, K and N should be pretty close to each other for most 
> applications. I'd be interested in real application scenarios where N is 
> much (== more than 10 times) larger than K and plists really matter.
> 

I think that would only be the case when an application has an error. The
problem now is: Say you have two RT applications running, one living
in priority 0-49 and one in 50-99. Let us say the second has such an
error, like keep spawning threads whichs blocks on a mutex owned by a task
which is blocked forever. Without plists such an error will kill the high
priority RT task. With plists it will only see a _limited_ effect on it's
latency.

You can say plists is better at isolating applications wrt. timing than
ordinary sorted lists.

> 	Ingo
> 

Re: [patch] Real-Time Preemption, plist fixes

[Ingo Molnar]

* Thomas Gleixner <tglx@linutronix.de> wrote:

> > but i think the fundamental question remains even on Sunday mornings -
> > is the plist overhead worth it? Compared to the simple sorted list we 
> > exchange O(nr_RT_tasks_running) for O(nr_RT_levels_used) [which is in 
> > the 1-100 range], is that a significant practical improvement? By 
> > overhead i dont just mean cycle cost, but also architectural flexibility 
> > and maintainability.
> 
> That was my question too.

i think it would be handy to resurrect ALL_TASKS_PI. It was one of the 
things that stabilized the sorted list approach so quickly. Nothing 
beats the coverage of running a full graphical desktop with all the PI 
code active :-)

	Ingo

Re: patch] Real-Time Preemption, plist fixes

[Thomas Gleixner]

On Sun, 2005-06-05 at 10:32 +0200, Thomas Gleixner wrote:
> On Sat, 2005-06-04 at 17:53 -0700, Daniel Walker wrote:
> > >
> > I already released a patch to fix this.
> 
> Nice to know. Where ?
> 

Ingo pointed me at the patch. 

Sorry, but I really don't see the release there.

> The first time I saw these latencies I has the PI abstraction applied, and
> the most recent time I had the attached patch applied only. This patch is
> small so I'm not sure if it could have that type of effect on task 
> latency.

It fixes a problem and uncovers others, but your comment is more a
question than an explanation for the urgency of the fix. In fact the
original implementation leads to solid deadlocks in
plist_for_each_safe() loops.


I really can't blame Ingo for ignoring this.

tglx

Re: [patch] Real-Time Preemption, plist fixes

[Ingo Molnar]

* Esben Nielsen <simlo@phys.au.dk> wrote:

> [...] In extreme load situations we could end up with a lot of waiters 
> on mmap_sem forinstance.

what do you mean by extreme load. Extreme number of RT tasks, or extreme 
number of tasks altogether? The sorted-list implementation i had in -RT 
had all non-RT tasks handled in an O(1) way - the O(N) component was for 
adding RT tasks (removal was O(1)).

so the question is - can we have an extreme (larger than 140) number of 
RT tasks? If yes, why are they all RT - they can have no expectation of 
good latencies with a possible load factor of 140!

	Ingo

Re: [patch] Real-Time Preemption, plist fixes

[Esben Nielsen]

On Sun, 5 Jun 2005, Ingo Molnar wrote:

> 
> * Esben Nielsen <simlo@phys.au.dk> wrote:
> 
> > [...] In extreme load situations we could end up with a lot of waiters 
> > on mmap_sem forinstance.
> 
> what do you mean by extreme load. Extreme number of RT tasks, or extreme 
> number of tasks altogether? The sorted-list implementation i had in -RT 
> had all non-RT tasks handled in an O(1) way - the O(N) component was for 
> adding RT tasks (removal was O(1)).
> 
> so the question is - can we have an extreme (larger than 140) number of 
> RT tasks? If yes, why are they all RT - they can have no expectation of 
> good latencies with a possible load factor of 140!

I can't really imagine a properly working application having more than 140
RT tasks pounding on the same lock - except maybe if someone tries to run
an RT application on one of those Altrix thingies (#CPUS>140 :-).

But as I said I could imagine a situation where you have some really
important RT tasks you would like to survive even if your low priority RT
tasks does something bad - like keep spawning RT tasks which all waits on
the same lock. 

Actually this test would make the difference:

thread1:
 lock(&badlock);
 block_on_some_event_which_might_never_arrive();
 unlock(&badlock);

func:
 lock(&badlock);
 unlock(&badlock);
 done=1;

thread2:
 while(!done) {
   create_thread(func,RTprio=50);
   create_thread(func,RTprio=51);
   if(done) break;
   sleep(1);
 }   

If you have enough memory for all the tasks, this kind of code would not
be a problem with plists - it will only take a lot of memory. On the other
hand with sorted lists each thread will take longer time inside raw
spinlocks. At some point it will take the whole 1 sec and basicly nothing
else can run.

Ofcourse you can prevent this with ulimits...

What I would do in this discussion is to abstract the interface:
The rt_mutex code should not care if plists, sorted lists or what ever are
used. It should just have a prio_queue structure and prio_queue_add(),
prio_queue_first(), a prio_queue_for_each macro etc. Then Daniel can play
along with his plists and have it as a config-option for now. Someone who
doesn't care about the memory consumption, could even choose to use the
prio_array from the scheduler!
 
> 
> 	Ingo

Esben

Re: [patch] Real-Time Preemption, plist fixes

[Daniel Walker]

On Sun, 5 Jun 2005, Ingo Molnar wrote:
> 
> in any case, i've added most of your fixes and cleanups (changed the
> O(N) to O(K) and explained K) and have released the -47-17 patch.
> Daniel, do agree with these changes (in particular the __plist_del()
> changes?) and is there anything else missing? It looks like we might be
> near the end of the tunnel and plists are really stabilizing.


__plist_del was a good fix. I attached a patch on "Plist cleanup on RT" to
lkml with what was acceptable to me. A good 60% of Thomas's changes are
unacceptable to me.

Daniel

Re: [patch] Real-Time Preemption, plist fixes

[Daniel Walker]

On Sun, 5 Jun 2005, Ingo Molnar wrote:

> but i think the fundamental question remains even on Sunday mornings -
> is the plist overhead worth it? Compared to the simple sorted list we 
> exchange O(nr_RT_tasks_running) for O(nr_RT_levels_used) [which is in 
> the 1-100 range], is that a significant practical improvement? By 
> overhead i dont just mean cycle cost, but also architectural flexibility 
> and maintainability.

We use it for all tasks . So for instance all priority levels get sorted ,
not just RT tasks. Most systems aren't going to have many RT tasks, just
interrupts and they don't share many locks. However, there are tons of
userspace tasks that do get sorted.

I think using plist on the wait_list is worth it. Since there aren't
many RT tasks usually . It may be a waste to use it on the pi_waiters.

Daniel

Re: [patch] Real-Time Preemption, plist fixes

[Daniel Walker]

On Sun, 5 Jun 2005, Ingo Molnar wrote:

> i think it would be handy to resurrect ALL_TASKS_PI. It was one of the 
> things that stabilized the sorted list approach so quickly. Nothing 
> beats the coverage of running a full graphical desktop with all the PI 
> code active :-)


I keep wondering why I'm dragging ALL_TASKS_PI around in all my patches,
since it doesn't work. Why not have it on all the time?

Daniel 

Re: [patch] Real-Time Preemption, plist fixes

[Thomas Gleixner]

On Sun, 2005-06-05 at 07:51 -0700, Daniel Walker wrote:

> __plist_del was a good fix. I attached a patch on "Plist cleanup on RT" to
> lkml with what was acceptable to me. A good 60% of Thomas's changes are
> unacceptable to me.

Would you be so kind to explain that a bit ? Your patch contains _all_
my proposed changes except the additional plist_first_entry macro and
the comment cleanup.

So what are the 60% which are unacceptable. Comments ? I'm amused.

tglx

Re: [patch] Real-Time Preemption, plist fixes

[Daniel Walker]

On Sun, 5 Jun 2005, Thomas Gleixner wrote:

> On Sun, 2005-06-05 at 07:51 -0700, Daniel Walker wrote:
> 
> > __plist_del was a good fix. I attached a patch on "Plist cleanup on RT" to
> > lkml with what was acceptable to me. A good 60% of Thomas's changes are
> > unacceptable to me.
> 
> Would you be so kind to explain that a bit ? Your patch contains _all_
> my proposed changes except the additional plist_first_entry macro and
> the comment cleanup.
> 
> So what are the 60% which are unacceptable. Comments ? I'm amused.

Whatever was missing was unacceptable. 

Daniel

Re: [patch] Real-Time Preemption, plist fixes

[Daniel Walker]

On Sun, 5 Jun 2005, Ingo Molnar wrote:
> 
> but i think the fundamental question remains even on Sunday mornings -
> is the plist overhead worth it? Compared to the simple sorted list we 
> exchange O(nr_RT_tasks_running) for O(nr_RT_levels_used) [which is in 
> the 1-100 range], is that a significant practical improvement? By 
> overhead i dont just mean cycle cost, but also architectural flexibility 
> and maintainability.


	You'll have to explain the "architectural flexibility and 
maintainability" costs . Questioning if plist works correctly isn't 
a long term maintainability problem, in my mind. I don't see any 
architectural costs considering the plist API, which is why I saw a clear 
path to integrate plist in the first place. 

	For me it's strictly a speed question. I was reviewing V0.7.40-04 
and it looks like apples and oranges to me. It's more a question of where 
do you perfer the latency , in up() or in down() .. plist is slower for 
non-RT tasks, but non-RT tasks also get the benefit of priority ordering.

Daniel

Re: [patch] Real-Time Preemption, plist fixes

[Ingo Molnar]

* Esben Nielsen <simlo@phys.au.dk> wrote:

> Sorted lists works deterministicly O(1) on UP if no owner of the lock 
> blocks while having the lock. On SMP or worse if an owner blocks in 
> the lock, the wait list can grow very long. Thus insertion of new 
> elements takes a long time - with preemption disabled :-(

the wait list can grow only as long as the max # of RT tasks is. Sorted 
lists become 'O(1)' if we added some code that globally limits the 
number of RT tasks to say 50. E.g. /proc/sys/kernel/max_nr_RT_tasks. A 
user can override it if he needs more RT tasks. There can be an 
arbitrary number of SCHED_OTHER tasks.

(note that on Linux there is a RAM-dependent 'max # of tasks' ulimit 
which is never 'infinity', so theoretically the sorted lists are "O(1)" 
too. But this is nitpicking.)

> If this is supposed to be used for user-space PI as well I would say 
> it would have to be completely bounded, i.e. plists are certainly 
> needed. [...]

yes, it's supposed to be used for user-space PI too. What do you mean by 
'completely bounded'. Do you consider the current worst-case O(100) 
property of plists a 'completely bounded' solution?

i dont think fusyn's should be made available to non-RT tasks. If this 
restriction is preserved then fusyn's would become O(max_nr_RT_tasks) 
too.

	Ingo

Re: [patch] Real-Time Preemption, plist fixes

[Ingo Molnar]

* Daniel Walker <dwalker@mvista.com> wrote:

> 	For me it's strictly a speed question. I was reviewing 
> V0.7.40-04 and it looks like apples and oranges to me. It's more a 
> question of where do you perfer the latency , in up() or in down() .. 
> plist is slower for non-RT tasks, but non-RT tasks also get the 
> benefit of priority ordering.

what benefit do non-RT tasks get from plists, compared to the ordered 
list? Non-RT tasks are not PI handled in any way.

	Ingo

Re: [patch] Real-Time Preemption, plist fixes

[Esben Nielsen]

On Mon, 6 Jun 2005, Ingo Molnar wrote:

> 
> * Esben Nielsen <simlo@phys.au.dk> wrote:
> 
> > Sorted lists works deterministicly O(1) on UP if no owner of the lock 
> > blocks while having the lock. On SMP or worse if an owner blocks in 
> > the lock, the wait list can grow very long. Thus insertion of new 
> > elements takes a long time - with preemption disabled :-(
> 
> the wait list can grow only as long as the max # of RT tasks is. Sorted 
> lists become 'O(1)' if we added some code that globally limits the 
> number of RT tasks to say 50. E.g. /proc/sys/kernel/max_nr_RT_tasks. A 
> user can override it if he needs more RT tasks. There can be an 
> arbitrary number of SCHED_OTHER tasks.
> 
> (note that on Linux there is a RAM-dependent 'max # of tasks' ulimit 
> which is never 'infinity', so theoretically the sorted lists are "O(1)" 
> too. But this is nitpicking.)
> 
> > If this is supposed to be used for user-space PI as well I would say 
> > it would have to be completely bounded, i.e. plists are certainly 
> > needed. [...]
> 
> yes, it's supposed to be used for user-space PI too. What do you mean by 
> 'completely bounded'. Do you consider the current worst-case O(100) 
> property of plists a 'completely bounded' solution?
> 
> i dont think fusyn's should be made available to non-RT tasks. If this 
> restriction is preserved then fusyn's would become O(max_nr_RT_tasks) 
> too.
> 

My pragmatic side agrees with you. My sense of beauty does not. I think
you make 2 small hacks here:
1) Adding a limit like above smells wrong.
2) Making PI only apply to RT tasks isn't beautifull either.

On the other hand the plists are "beautifull". It would sadden me if they
are thrown away.

As I said in an earlier mail, I think you should agree on an interface
between the rt_mutex code and list structure. Then Daniel can implement
and test his plist in user space, somebody else can implement and test
the sorted list in userspace and the transition can happen with a switch
of a macro and a recompilation.

I hope I will get some time to help out from next weekend. I am taking
exams right now.

> 	Ingo
> 

Esben

Re: [patch] Real-Time Preemption, plist fixes

[Ingo Molnar]

* Esben Nielsen <simlo@phys.au.dk> wrote:

> > i dont think fusyn's should be made available to non-RT tasks. If this 
> > restriction is preserved then fusyn's would become O(max_nr_RT_tasks) 
> > too.
> 
> My pragmatic side agrees with you. My sense of beauty does not. I think
> you make 2 small hacks here:
>
> 1) Adding a limit like above smells wrong.
> 2) Making PI only apply to RT tasks isn't beautifull either.

Enabling PI for all tasks would certainly make plists the only viable 
choice. To achieve that we'd have to do quite careful coding, as the 
priorities of SCHED_OTHER tasks can change quite frequently, and the PI 
code doesnt follow priority changes that well currently.

	Ingo

Re: [patch] Real-Time Preemption, plist fixes

[Daniel Walker]

On Mon, 6 Jun 2005, Ingo Molnar wrote:

> 
> * Daniel Walker <dwalker@mvista.com> wrote:
> 
> > 	For me it's strictly a speed question. I was reviewing 
> > V0.7.40-04 and it looks like apples and oranges to me. It's more a 
> > question of where do you perfer the latency , in up() or in down() .. 
> > plist is slower for non-RT tasks, but non-RT tasks also get the 
> > benefit of priority ordering.
> 
> what benefit do non-RT tasks get from plists, compared to the ordered 
> list? Non-RT tasks are not PI handled in any way.

The original wait list was partial ordered, wasn't it? RT tasks on the 
front, non-RT at the back. Now the whole list is sorted (including non RT 
tasks) . So non-RT task will get the lock in priority sorted order, as 
opposed to just random. Like you said, there is no PI done.


Daniel

Re: [patch] Real-Time Preemption, plist fixes

[Daniel Walker]

On Mon, 6 Jun 2005, Ingo Molnar wrote:
> 
> yes, it's supposed to be used for user-space PI too. What do you mean by 
> 'completely bounded'. Do you consider the current worst-case O(100) 
> property of plists a 'completely bounded' solution?
> 
> i dont think fusyn's should be made available to non-RT tasks. If this 
> restriction is preserved then fusyn's would become O(max_nr_RT_tasks) 
> too.

	I think making fusyn RT tasks only would be asking a lot. Fusyn 
replaces Futex, and they are both used in pthreads. So non-RT tasks 
wouldn't be able to use pthreads in userspace, or a big chunk of pthread 
..

Daniel

Re: [patch] Real-Time Preemption, plist fixes

[Daniel Walker]

On Mon, 6 Jun 2005, Ingo Molnar wrote:
> But indeed it could improve interactivity (but this has not been proven 
> yet) - and also for testing purposes it would sure be useful, so we 
> should perhaps make ALL_TASKS_PI default-on, as Daniel suggests. If that 
> is done then plists are indeed a superior solution. But if in the end we 
> decide to only include RT tasks in the PI mechanism (which could easily 
> happen) then there seems to be little practical difference between 
> sorted lists and plists.

The biggest reason that I suggest this is because when I wrote the 
abstracted PI I gave the user of the API the choice to do RT tasks only or 
all tasks. In the case of fusyn or futex , they will do all tasks .. Once 
you throw in one structure that does all tasks , they may as well all be 
doing it. Or that's how I feel.

Daniel

Re: [patch] Real-Time Preemption, plist fixes

[Ingo Molnar]

* Perez-Gonzalez, Inaky <inaky.perez-gonzalez@intel.com> wrote:

> >From: Ingo Molnar [mailto:mingo@elte.hu]
> >
> >so the question is - can we have an extreme (larger than 140) number of
> >RT tasks? If yes, why are they all RT - they can have no expectation of
> >good latencies with a possible load factor of 140!
> 
> In practice, didn't we want most tasks to behave like RT? (for 
> interactivity purposes) -- I recall hearing that's basically what good 
> interactivity meant; short reponse times to events.

that's not what the current code does (and it's not what the non-plist 
code did either). We dont do PI handling for non-RT tasks. They 
basically have no RT expectations at all, and including them in the PI 
mechanism would only slow them down, and would increase the latencies of 
the RT tasks as well.

But indeed it could improve interactivity (but this has not been proven 
yet) - and also for testing purposes it would sure be useful, so we 
should perhaps make ALL_TASKS_PI default-on, as Daniel suggests. If that 
is done then plists are indeed a superior solution. But if in the end we 
decide to only include RT tasks in the PI mechanism (which could easily 
happen) then there seems to be little practical difference between 
sorted lists and plists.

	Ingo

RE: [patch] Real-Time Preemption, plist fixes

[Perez-Gonzalez, Inaky]

>From: Ingo Molnar [mailto:mingo@elte.hu]
>
>so the question is - can we have an extreme (larger than 140) number of
>RT tasks? If yes, why are they all RT - they can have no expectation of
>good latencies with a possible load factor of 140!

In practice, didn't we want most tasks to behave like RT?
(for interactivity purposes) -- I recall hearing that's basically
what good interactivity meant; short reponse times to events.

So then, taking await batch/bacground data-munching jobs, we fold 
back to needing a good RT-like behaviour. And then we can reach > 140.

-- Inaky