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.
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
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
* Oleg Nesterov <[email protected]> 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
Ingo Molnar wrote:
>
> * Oleg Nesterov <[email protected]> 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 <[email protected]>
--- /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);
+}
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.
* Oleg Nesterov <[email protected]> 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
On Tue, 2005-12-20 at 15:38 +0100, Ingo Molnar wrote:
> * Oleg Nesterov <[email protected]> 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
Daniel Walker wrote:
>
> On Tue, 2005-12-20 at 15:38 +0100, Ingo Molnar wrote:
> > * Oleg Nesterov <[email protected]> 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.
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 <[email protected]> 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