RE: [PATCH 2/4] rt_mutex: add new plist implementation

RE: [PATCH 2/4] rt_mutex: add new plist implementation

[Perez-Gonzalez, Inaky]

>From: Oleg Nesterov
>"Perez-Gonzalez, Inaky" wrote:
>>
>> >From: Oleg Nesterov
>>
>> >+extern void plist_add(struct pl_node *node, struct pl_head *head);
>> >+extern void plist_del(struct pl_node *node);
>>
>> At least I'd add return codes for this if the head's priority=20
>> changes (or in this case, because head's have no prio, if the=20
>> first node's  prio change).
>
>I am not sure I understand you. Why should we track ->prio=20 changes?
>plist should be generic, I think.

Errr....shut, that was my or your email program screwing
things up...that =20, I mean, that's MIME for line break.

>This could be:
>	int plist_add_and_check_min_prio_changed(node, head)
>	{
>		plist_add(node, head);
>		return plist_next(head) == node;
>	}
>
>Or plist_add() could be easily changed to return -1,0,+1 to indicate
>min/max prio changed/unchanged.

The -1/0/+1 sounds pretty good. 

>Currently these functions are used in void context only. I think
>it is better to add return codes when callers need them.
>
>What do you think?

I guess I am still very biased by my implementation, where returning
that was almost free because of how the functions where implemented
(which steamed from the fact that they had to always compute the
new priority to store it in the head).

So as you say, the best way is wrapping your primitives around. I'd
suggest a shorter postfix, something like _prio() or _chkprio().

Thanks,

-- Inaky

Re: [PATCH 2/4] rt_mutex: add new plist implementation

[Valdis.Kletnieks]

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

On Tue, 10 May 2005 11:39:45 PDT, "Perez-Gonzalez, Inaky" said:

> >> At least I'd add return codes for this if the head's priority=20
> >> changes (or in this case, because head's have no prio, if the=20
> >> first node's  prio change).
> >
> >I am not sure I understand you. Why should we track ->prio=20 changes?
> >plist should be generic, I think.
> 
> Errr....shut, that was my or your email program screwing
> things up...that =20, I mean, that's MIME for line break.

Actually, it's the MIME encoding for "blank".  It's usually seen with trailing
blanks, so systems that trim trailing blanks won't molest the one you left on
the end of the line.....


[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

Re: [PATCH 2/4] rt_mutex: add new plist implementation

[Valdis.Kletnieks]

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

On Tue, 10 May 2005 11:39:45 PDT, "Perez-Gonzalez, Inaky" said:
> >From: Oleg Nesterov
> >"Perez-Gonzalez, Inaky" wrote:

> Errr....shut, that was my or your email program screwing
> things up...that =20, I mean, that's MIME for line break.

Dug a bit further...

There was a trailing blank in Inaky's note as it arrived here, but it was
traveling with a Content-Type-Encoding: 8bit.  My guess is that some mail
software between vger and Oleg's inbox down-converted to 7bit.  Either that
mailer failed to insert a 'Content-Type-Encoding: quoted-printable' header when
it applied the quoted-printable )changing a trailing blank to =20) when
down-converting, or Oleg's mail reader (apparently Mozilla?) failed to heed the
C-T-E and convert the =20 back to the trailing blank it should have been.

I was there when all this MIME stuff was designed, and we covered all the
failure modes of stupid designers of mail software that we could think of.
We never considered the sorts of whitespace screw-ups we actually see today -
I think there was a "No designer could be THAT daft" blind-spot....

[-- Attachment #2: Type: application/pgp-signature, Size: 226 bytes --]

RE: [PATCH 2/4] rt_mutex: add new plist implementation

[Daniel Walker]

On Tue, 2005-05-10 at 11:39, Perez-Gonzalez, Inaky wrote:

> 
> I guess I am still very biased by my implementation, where returning
> that was almost free because of how the functions where implemented
> (which steamed from the fact that they had to always compute the
> new priority to store it in the head).
> 
> So as you say, the best way is wrapping your primitives around. I'd
> suggest a shorter postfix, something like _prio() or _chkprio().

I still say re-implementation of plist is a waste .. Why re-make the
wheel when you have a perfectly good starting point .

Daniel

Re: [PATCH 2/4] rt_mutex: add new plist implementation

[Oleg Nesterov]

Daniel Walker wrote:
> 
> I still say re-implementation of plist is a waste .. Why re-make the
> wheel when you have a perfectly good starting point .

Because it does not work? I think you have missed my first message on
this topic: http://marc.theaimsgroup.com/?l=linux-kernel&m=111536999732736

I had no intent to re-implement plists, it was you who told me:
>
> Make a patch .

Oleg.

RE: [PATCH 2/4] rt_mutex: add new plist implementation

[Perez-Gonzalez, Inaky]

>From: Daniel Walker [mailto:dwalker@mvista.com]
>>
>> So as you say, the best way is wrapping your primitives around. I'd
>> suggest a shorter postfix, something like _prio() or _chkprio().
>
>I still say re-implementation of plist is a waste .. Why re-make the
>wheel when you have a perfectly good starting point .

I don't know *shrug* 

In this case, Oleg's wheel looks simpler than mine and does the
same thing, so why not use it? Simpler is beautiful.

I share the concern, though, of it being fully debugged and stuff,
but being simpler it should be easier to prove it correct.

-- Inaky

RE: [PATCH 2/4] rt_mutex: add new plist implementation

[Perez-Gonzalez, Inaky]

>From: Valdis.Kletnieks@vt.edu [mailto:Valdis.Kletnieks@vt.edu]
>On Tue, 10 May 2005 11:39:45 PDT, "Perez-Gonzalez, Inaky" said:
>
>> >I am not sure I understand you. Why should we track ->prio=20
changes?
>> >plist should be generic, I think.
>>
>> Errr....shut, that was my or your email program screwing
>> things up...that =20, I mean, that's MIME for line break.
>
>Actually, it's the MIME encoding for "blank".  It's usually seen with
trailing
>blanks, so systems that trim trailing blanks won't molest the one you
left on
>the end of the line.....

Tomatoe, tomato :)

Thanks,

-- Inaky

RE: [PATCH 2/4] rt_mutex: add new plist implementation

[Perez-Gonzalez, Inaky]

Hi Oleg

>From: Oleg Nesterov

>+extern void plist_add(struct pl_node *node, struct pl_head *head);
>+extern void plist_del(struct pl_node *node);

At least I'd add return codes for this if the head's priority 
changes (or in this case, because head's have no prio, if the 
first node's  prio change). Both function's  logic should make
it easy to test and it'd save a lot of code in the caller.

-- Inaky

Re: [PATCH 2/4] rt_mutex: add new plist implementation

[Oleg Nesterov]

"Perez-Gonzalez, Inaky" wrote:
>
> >From: Oleg Nesterov
>
> >+extern void plist_add(struct pl_node *node, struct pl_head *head);
> >+extern void plist_del(struct pl_node *node);
>
> At least I'd add return codes for this if the head's priority=20
> changes (or in this case, because head's have no prio, if the=20
> first node's  prio change).

I am not sure I understand you. Why should we track ->prio=20 changes?
plist should be generic, I think.

Original code:
	unsigned plist_add (struct plist *pl, struct plist *plist)
	{
		__plist_add_sorted (plist, pl);
		if (pl->prio < plist->prio) {
			plist->prio = pl->prio;
			return !0;
		}
		return 0;
	}

This could be:
	int plist_add_and_check_min_prio_changed(node, head)
	{
		plist_add(node, head);
		return plist_next(head) == node;
	}

Or plist_add() could be easily changed to return -1,0,+1 to indicate
min/max prio changed/unchanged.

But may be it is better to return 'iter' from plist_add(). This way
we can avoid scanning ->prio_list when we add the node with the same
->prio next time. I am not sure.

And please note that pl_head "has" prio:

	plist_empty(head) ? INT_MAX			// -1 ?
			  : plist_next(head)->prio

> Both function's  logic should make it easy to test and it'd save
> a lot of code in the caller.

Currently these functions are used in void context only. I think
it is better to add return codes when callers need them.

What do you think?

Oleg.

[PATCH 2/4] rt_mutex: add new plist implementation

[Oleg Nesterov]

This patch adds new plist implementation, see
http://marc.theaimsgroup.com/?l=linux-kernel&m=111547290706136

Changes:

	added plist_next_entry() helper (was plist_entry)

	added plist_unhashed() helper, see PATCH 4/4

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

--- V0.7.47-01/include/linux/plist.h~1_PLIST	2005-05-09 17:06:05.000000000 +0400
+++ V0.7.47-01/include/linux/plist.h	2005-05-09 20:11:26.000000000 +0400
@@ -0,0 +1,97 @@
+#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_next_entry(head, type, member)	\
+	container_of(plist_next(head), type, member)
+
+#define plist_prev_entry(head, type, member)	\
+	container_of(plist_prev(head), type, member)
+
+#define __pl_head_node(head, list, dir)	\
+	list_entry((head)->list.dir, struct pl_node, plist.list)
+
+static inline struct pl_node* plist_next(const struct pl_head *head)
+{
+	return __pl_head_node(head, node_list, next);
+}
+
+static inline struct pl_node* plist_prev(const struct pl_head *head)
+{
+	return __pl_head_node(head, node_list, prev);
+}
+
+static inline struct pl_node* plist_prio_next(const struct pl_head *head)
+{
+	return __pl_head_node(head, prio_list, next);
+}
+
+static inline struct pl_node* plist_prio_prev(const struct pl_head *head)
+{
+	return __pl_head_node(head, prio_list, prev);
+}
+
+#undef	__pl_head_node
+#endif
--- V0.7.47-01/lib/plist.c~1_PLIST	2005-05-09 17:06:05.000000000 +0400
+++ V0.7.47-01/lib/plist.c	2005-05-09 19:55:31.000000000 +0400
@@ -0,0 +1,36 @@
+/*
+ * 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 = plist_prio_next(&iter->plist);
+			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_next(&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);
+}
--- V0.7.47-01/lib/Makefile~1_PLIST	2005-05-09 16:46:06.000000000 +0400
+++ V0.7.47-01/lib/Makefile	2005-05-09 17:12:48.000000000 +0400
@@ -15,6 +15,8 @@ CFLAGS_kobject.o += -DDEBUG
 CFLAGS_kobject_uevent.o += -DDEBUG
 endif
 
+obj-$(CONFIG_PREEMPT_RT) += plist.o
+
 obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
 lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
 lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o

Re: [PATCH 2/4] rt_mutex: add new plist implementation

[Daniel Walker]

On Mon, 9 May 2005, Oleg Nesterov wrote:

> This patch adds new plist implementation, see
> http://marc.theaimsgroup.com/?l=linux-kernel&m=111547290706136
> 
> Changes:
> 
> 	added plist_next_entry() helper (was plist_entry)
> 
> 	added plist_unhashed() helper, see PATCH 4/4
> 


	Naw , stick with Inaky's API .. Your stuff looks nothing like 
list.h ..

Daniel

Re: [PATCH 2/4] rt_mutex: add new plist implementation

[Oleg Nesterov]

Daniel Walker wrote:
>
> On Mon, 9 May 2005, Oleg Nesterov wrote:
>
> > This patch adds new plist implementation, see
> > http://marc.theaimsgroup.com/?l=linux-kernel&m=111547290706136
> >
> > Changes:
> >
> > 	added plist_next_entry() helper (was plist_entry)
> >
> > 	added plist_unhashed() helper, see PATCH 4/4
> >
>
> 	Naw , stick with Inaky's API ..

This patch breaks Inaky's API anyway, plist_del() now has only one
argument, and I think this is good.

I don't mind doing s/plist_next_entry/plist_entry/ if you wish,
but I think this is consistent with plist_next/plist_prev helpers.

And original plist_empty() is confusing. When used on plist's head
it is ok, but it is wrong to use plist_empty(&plist_node).

> Your stuff looks nothing like list.h ..

Is it bad?

Yes, plist_empty/plist_unhashed mimics hlist_empty/hlist_unhashed.

Oleg.