lkml.org 
[lkml]   [2005]   [Dec]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [PATCH rc5-rt2 0/3] plist: alternative implementation
From
Date
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

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-12-20 18:31    [W:0.805 / U:0.056 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site