[PATCH rc5-rt2 0/3] plist: alternative implementation

[PATCH rc5-rt2 0/3] plist: alternative implementation

[Oleg Nesterov]

Rediff against patch-2.6.15-rc5-rt2.

Nothing was changed except s/plist_next_entry/plist_first_entry/
to match the current naming.

These patches were only compile tested. This is beacuse I can't
even compile 2.6.15-rc5-rt2, I had to comment out this line

	lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o

in lib/Makefile. I think CONFIG_RWSEM_GENERIC_SPINLOCK means that
lib/rwsem.c should be ignored.

After that the kernel panics at boot time, the call trace shows

	set_workqueue_thread_prio
	wake_up_process
	set_workqueue_prio
	init_workqueues

will try to look further on Tuesday.

Just to make it clear, these problems were _without_ these patches.

Oleg.

Re: [PATCH rc5-rt2 0/3] plist: alternative implementation

[Steven Rostedt]

On Sun, 18 Dec 2005, Oleg Nesterov wrote:

> Rediff against patch-2.6.15-rc5-rt2.
>
> Nothing was changed except s/plist_next_entry/plist_first_entry/
> to match the current naming.
>
> These patches were only compile tested. This is beacuse I can't
> even compile 2.6.15-rc5-rt2, I had to comment out this line
>
> 	lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
>
> in lib/Makefile. I think CONFIG_RWSEM_GENERIC_SPINLOCK means that
> lib/rwsem.c should be ignored.
>

I've already submitted patches to Ingo to fix this.

-- Steve

Re: [PATCH rc5-rt2 0/3] plist: alternative implementation

[Steven Rostedt]

On Sun, 18 Dec 2005, Steven Rostedt wrote:

>
> On Sun, 18 Dec 2005, Oleg Nesterov wrote:
>
> > Rediff against patch-2.6.15-rc5-rt2.
> >
> > Nothing was changed except s/plist_next_entry/plist_first_entry/
> > to match the current naming.
> >
> > These patches were only compile tested. This is beacuse I can't
> > even compile 2.6.15-rc5-rt2, I had to comment out this line
> >
> > 	lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
> >
> > in lib/Makefile. I think CONFIG_RWSEM_GENERIC_SPINLOCK means that
> > lib/rwsem.c should be ignored.
> >
>
> I've already submitted patches to Ingo to fix this.
>

Oh, and here's the link to that post.

http://marc.theaimsgroup.com/?l=linux-kernel&m=113448476303030&w=2

-- Steve

Re: [PATCH rc5-rt2 0/3] plist: alternative implementation

[Ingo Molnar]

* Oleg Nesterov <oleg@tv-sign.ru> wrote:

> Rediff against patch-2.6.15-rc5-rt2.
> 
> Nothing was changed except s/plist_next_entry/plist_first_entry/ to 
> match the current naming.

thanks Oleg, your patches look good to me, and it's a worthwile cleanup 
to make plist.h ops behave more like normal list.h ops. The new ops 
should be documented, but otherwise it looks OK.

(the resulting kernel doesnt build in PREEMPT_RT mode though, it's 
lib/plist.c not being converted yet?)

> These patches were only compile tested. This is beacuse I can't even 
> compile 2.6.15-rc5-rt2, I had to comment out this line
> 
> 	lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
> 
> in lib/Makefile. I think CONFIG_RWSEM_GENERIC_SPINLOCK means that 
> lib/rwsem.c should be ignored.
> 
> After that the kernel panics at boot time, the call trace shows
> 
> 	set_workqueue_thread_prio
> 	wake_up_process
> 	set_workqueue_prio
> 	init_workqueues
> 
> will try to look further on Tuesday.
> 
> Just to make it clear, these problems were _without_ these patches.

please try the -rt3 kernel, does it work any better?

	Ingo

Re: [PATCH rc5-rt2 0/3] plist: alternative implementation

[Oleg Nesterov]

Ingo Molnar wrote:
> 
> * Oleg Nesterov <oleg@tv-sign.ru> wrote:
> 
> > Rediff against patch-2.6.15-rc5-rt2.
> >
> > Nothing was changed except s/plist_next_entry/plist_first_entry/ to
> > match the current naming.
> 
> (the resulting kernel doesnt build in PREEMPT_RT mode though, it's
> lib/plist.c not being converted yet?)

Ingo, sorry, I sent you a wrong plist.c !!!
plist.c should also do this rename, but I sent you an old file.

This is updated patch:

[PATCH rc5-rt2 2/3] plist: add new implementation

New implementation. It is smaller, and in my opinion cleaner.
User-space test: http://www.tv-sign.ru/oleg/plist.tgz

Like hlist, it has different types for head and node: pl_head/pl_node.

pl_head does not have ->prio field. This saves sizeof(int), and we
don't need to have it in plist_del's parameter list. This is also good
for typechecking.

Like list_add(), plist_add() does not require initialization on pl_node,
except ->prio.

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

--- /dev/null	2000-01-01 03:00:00.000000000 +0300
+++ RT/include/linux/plist.h	2005-12-20 21:45:05.000000000 +0300
@@ -0,0 +1,75 @@
+#ifndef _LINUX_PLIST_H_
+#define _LINUX_PLIST_H_
+
+#include <linux/list.h>
+
+struct pl_head {
+	struct list_head prio_list;
+	struct list_head node_list;
+};
+
+struct pl_node {
+	int		prio;
+	struct pl_head	plist;
+};
+
+#define PL_HEAD_INIT(head)	\
+{							\
+	.prio_list = LIST_HEAD_INIT((head).prio_list),	\
+	.node_list = LIST_HEAD_INIT((head).node_list),	\
+}
+
+#define PL_NODE_INIT(node, __prio)	\
+{							\
+	.prio  = (__prio),				\
+	.plist = PL_HEAD_INIT((node).plist),		\
+}
+
+static inline void pl_head_init(struct pl_head *head)
+{
+	INIT_LIST_HEAD(&head->prio_list);
+	INIT_LIST_HEAD(&head->node_list);
+}
+
+static inline void pl_node_init(struct pl_node *node, int prio)
+{
+	node->prio = prio;
+	pl_head_init(&node->plist);
+}
+
+extern void plist_add(struct pl_node *node, struct pl_head *head);
+extern void plist_del(struct pl_node *node);
+
+#define plist_for_each(pos, head)	\
+	 list_for_each_entry(pos, &(head)->node_list, plist.node_list)
+
+#define plist_for_each_safe(pos, n, head)	\
+	 list_for_each_entry_safe(pos, n, &(head)->node_list, plist.node_list)
+
+#define plist_for_each_entry(pos, head, mem)	\
+	 list_for_each_entry(pos, &(head)->node_list, mem.plist.node_list)
+
+#define plist_for_each_entry_safe(pos, n, head, mem)	\
+	 list_for_each_entry_safe(pos, n, &(head)->node_list, mem.plist.node_list)
+
+static inline int plist_empty(const struct pl_head *head)
+{
+	return list_empty(&head->node_list);
+}
+
+static inline int plist_unhashed(const struct pl_node *node)
+{
+	return list_empty(&node->plist.node_list);
+}
+
+/* All functions below assume the pl_head is not empty. */
+
+#define plist_first_entry(head, type, member)	\
+	container_of(plist_first(head), type, member)
+
+static inline struct pl_node* plist_first(const struct pl_head *head)
+{
+	return list_entry(head->node_list.next, struct pl_node, plist.node_list);
+}
+
+#endif
--- /dev/null	2000-01-01 03:00:00.000000000 +0300
+++ RT/lib/plist.c	2005-12-20 21:43:43.000000000 +0300
@@ -0,0 +1,37 @@
+/*
+ * lib/plist.c - Priority List implementation.
+ */
+
+#include <linux/plist.h>
+
+void plist_add(struct pl_node *node, struct pl_head *head)
+{
+	struct pl_node *iter;
+
+	INIT_LIST_HEAD(&node->plist.prio_list);
+
+	list_for_each_entry(iter, &head->prio_list, plist.prio_list)
+		if (node->prio < iter->prio)
+			goto lt_prio;
+		else if (node->prio == iter->prio) {
+			iter = list_entry(iter->plist.prio_list.next,
+					struct pl_node, plist.prio_list);
+			goto eq_prio;
+		}
+
+lt_prio:
+	list_add_tail(&node->plist.prio_list, &iter->plist.prio_list);
+eq_prio:
+	list_add_tail(&node->plist.node_list, &iter->plist.node_list);
+}
+
+void plist_del(struct pl_node *node)
+{
+	if (!list_empty(&node->plist.prio_list)) {
+		struct pl_node *next = plist_first(&node->plist);
+		list_move_tail(&next->plist.prio_list, &node->plist.prio_list);
+		list_del_init(&node->plist.prio_list);
+	}
+
+	list_del_init(&node->plist.node_list);
+}

Re: [PATCH rc5-rt2 0/3] plist: alternative implementation

[Ingo Molnar]

* Oleg Nesterov <oleg@tv-sign.ru> wrote:

> > (the resulting kernel doesnt build in PREEMPT_RT mode though, it's
> > lib/plist.c not being converted yet?)
> 
> Ingo, sorry, I sent you a wrong plist.c !!! plist.c should also do 
> this rename, but I sent you an old file.
> 
> This is updated patch:

thanks, this one builds fine and boots fine on a dual-core X2 box, in 
full PREEMPT_RT mode. I cannot see anything obviously wrong going on, so 
i've released this as -rt4.

could you send the doc fixups against -rt4? Please also add back the 
credits to plist.h (and add your own name for these improvements).  
Thanks,

	Ingo

Re: [PATCH rc5-rt2 0/3] plist: alternative implementation

[Oleg Nesterov]

Ingo Molnar wrote:
> 
> 
> thanks Oleg, your patches look good to me, and it's a worthwile cleanup
> to make plist.h ops behave more like normal list.h ops. The new ops
> should be documented, but otherwise it looks OK.
> 
> please try the -rt3 kernel, does it work any better?

I'll try to do some testing on my side and send comments update on Friday.

Oleg.

Re: [PATCH rc5-rt2 0/3] plist: alternative implementation

[Daniel Walker]

On Tue, 2005-12-20 at 15:38 +0100, Ingo Molnar wrote:
> * Oleg Nesterov <oleg@tv-sign.ru> wrote:
> 
> > Rediff against patch-2.6.15-rc5-rt2.
> > 
> > Nothing was changed except s/plist_next_entry/plist_first_entry/ to 
> > match the current naming.
> 
> thanks Oleg, your patches look good to me, and it's a worthwile cleanup 
> to make plist.h ops behave more like normal list.h ops. The new ops 
> should be documented, but otherwise it looks OK.

I think there is a bug in the new plist_add() , which was in the
original code. It doesn't properly handle the new maximum node scenario,
or INT_MAX . 

If the list is 1 2 3 4

and you insert 5 , you'll end up with the list 1 2 3 5 4 . Or something
like that .


Daniel

Re: [PATCH rc5-rt2 0/3] plist: alternative implementation

[Oleg Nesterov]

Daniel Walker wrote:
> 
> On Tue, 2005-12-20 at 15:38 +0100, Ingo Molnar wrote:
> > * Oleg Nesterov <oleg@tv-sign.ru> wrote:
> >
> I think there is a bug in the new plist_add() , which was in the
> original code. It doesn't properly handle the new maximum node scenario,
> or INT_MAX .
> 
> If the list is 1 2 3 4
> 
> and you insert 5 , you'll end up with the list 1 2 3 5 4 . Or something
> like that .

I think you are not right, please look at the code.

The code under list_for_each_entry() can break the loop only
when node->prio <= iter->prio.

void plist_add(struct pl_node *node, struct pl_head *head)
{
	struct pl_node *iter;

	list_for_each_entry(iter, &head->prio_list, plist.prio_list)
		if (node->prio < iter->prio)
			goto lt_prio;
		else if (node->prio == iter->prio)
			...

	// So, node->prio is a new maximum, or the list was empty.

	// &iter.plist == head. We don't touch iter->prio, so it
	// is ok that this pl_node is fake, it is really pl_head.

	// We are doing list_add_tail(), this means that new node
	// will stay _after_ all other nodes.

	// In this case the code below is equal to:
	//
	//	list_add_tail(&node->plist.prio_list, &head->prio_list);
	//	list_add_tail(&node->plist.prio_list, &head->node_list);

lt_prio:
	list_add_tail(&node->plist.prio_list, &iter->plist.prio_list);
eq_prio:
	list_add_tail(&node->plist.node_list, &iter->plist.node_list);
}

Note that this also garantees FIFO ordering, which was documented
in plist.h, but was not true for plist_for_each().

Daniel, do you agree ?

Oleg.

Re: [PATCH rc5-rt2 0/3] plist: alternative implementation

[Daniel Walker]

On Tue, 2005-12-20 at 21:31 +0300, Oleg Nesterov wrote:
> Daniel Walker wrote:
> > 
> > On Tue, 2005-12-20 at 15:38 +0100, Ingo Molnar wrote:
> > > * Oleg Nesterov <oleg@tv-sign.ru> wrote:
> > >
> > I think there is a bug in the new plist_add() , which was in the
> > original code. It doesn't properly handle the new maximum node scenario,
> > or INT_MAX .
> > 
> > If the list is 1 2 3 4
> > 
> > and you insert 5 , you'll end up with the list 1 2 3 5 4 . Or something
> > like that .
> 
> I think you are not right, please look at the code.
> 
> The code under list_for_each_entry() can break the loop only
> when node->prio <= iter->prio.
> 
> void plist_add(struct pl_node *node, struct pl_head *head)
> {
> 	struct pl_node *iter;
> 
> 	list_for_each_entry(iter, &head->prio_list, plist.prio_list)
> 		if (node->prio < iter->prio)
> 			goto lt_prio;
> 		else if (node->prio == iter->prio)
> 			...
> 
> 	// So, node->prio is a new maximum, or the list was empty.
> 
> 	// &iter.plist == head. We don't touch iter->prio, so it
> 	// is ok that this pl_node is fake, it is really pl_head.
> 
> 	// We are doing list_add_tail(), this means that new node
> 	// will stay _after_ all other nodes.
> 
> 	// In this case the code below is equal to:
> 	//
> 	//	list_add_tail(&node->plist.prio_list, &head->prio_list);
> 	//	list_add_tail(&node->plist.prio_list, &head->node_list);
> 
> lt_prio:
> 	list_add_tail(&node->plist.prio_list, &iter->plist.prio_list);
> eq_prio:
> 	list_add_tail(&node->plist.node_list, &iter->plist.node_list);
> }
> 
> Note that this also garantees FIFO ordering, which was documented
> in plist.h, but was not true for plist_for_each().
> 
> Daniel, do you agree ?

It seems correct, however Inaky's code had special cases for this .
Since the two iteration implementation are near identical, it's a bit
suspect. Maybe Inaky can shed some light on it .

Daniel