_Chain_Is_first/last overshoot

[Gedare Bloom]

Attached patch breaks with CVS head, showing that our current
implementation of Chain_Is_first contradicts _Chain_First.

On Thu, Nov 10, 2011 at 3:28 PM, Gedare Bloom <gedare at rtems.org> wrote:
> I don't see any uses of these functions in any test cases. Since they
> are inline routines they probably aren't tripping any of the coverage
> 'uncovered' ranges?
>
> The analysis seems to be correct. Right now these functions return
> true if the passed node is the control block, whereas the intention
> seems to be the functions should return true if the passed node is the
> first node after the head (rsp last node before the tail).
>
> I think this is a bug (and probably an old one) and I doubt the
> functions themselves see much use. Most chain examples iterate through
> by calling _Chain_First and continuing until !_Chain_Is_tail().  A
> simple way to test for the bug and to add a new test case would be to
> write some code that checks if _Chain_Is_first( _Chain_First(
> control_node ) ) ) on a non-empty chain.
>
> On Wed, Nov 9, 2011 at 3:10 PM, Joel Sherrill <joel.sherrill at oarcorp.com> wrote:
>> On 11/9/2011 1:56 PM, Sébastien Bourdeauducq wrote:
>>>
>>> -------- Original Message --------
>>> Subject: [Milkymist-devel] [PATCH, tentative] RTEMS:
>>> _Chain_Is_first/last overshoot
>>> Date: Wed, 9 Nov 2011 16:53:53 -0300
>>> From: Werner Almesberger<werner at almesberger.net>
>>> Reply-To: Milkymist One, Milkymist SoC and Flickernoise developers' list
>>> <devel at lists.milkymist.org>
>>> To: Milkymist One, Milkymist SoC and Flickernoise developers' list
>>> <devel at lists.milkymist.org>
>>>
>>> Doubly-linked lists ("chains") in RTEMS have a "control" block that
>>> looks like the next/prev link pair in an element. The list elements
>>> link both ways to this control block.
>>>
>>> _Chain_Is_first and _Chain_Is_last only probed if the link to the
>>> next element - which would be the control block - is non-NULL.
>>> Telling by the function description and given that there are already
>>> functions called _Chain_Is_head and _Chain_Is_tail (which could be
>>> simplified), this is probably not the intended behaviour.
>>>
>>> This also affects the aliases rtems_chain_is_first and
>>> rtems_chain_is_last.
>>>
>>> These functions are not used a lot and I haven't seen any immediate
>>> effect on M1 after changing them, so I can't say whether this patch
>>> may unearth other problems.
>>
>> This needs a careful, careful review.  And a look at the history.
>>
>> I think by definition your change is right.  This is technically checking
>> that the_node
>> is permanent head or tail -- not checking that it is really the first or
>> last real node
>> on the chain.
>>
>> Can someone pitch in and help review where this is used?
>>
>> --joel
>>>
>>> - Werner
>>>
>>> Index: cpukit/score/inline/rtems/score/chain.inl
>>> ===================================================================
>>> RCS file: /usr1/CVS/rtems/cpukit/score/inline/rtems/score/chain.inl,v
>>> retrieving revision 1.23
>>> diff -U 4 -r1.23 chain.inl
>>> --- cpukit/score/inline/rtems/score/chain.inl   25 Nov 2010 11:48:11
>>> -0000   1.23
>>> +++ cpukit/score/inline/rtems/score/chain.inl   9 Nov 2011 19:42:13 -0000
>>> @@ -296,9 +296,9 @@
>>>   RTEMS_INLINE_ROUTINE bool _Chain_Is_first(
>>>     const Chain_Node *the_node
>>>   )
>>>   {
>>> -  return (the_node->previous == NULL);
>>> +  return the_node->previous->previous == NULL;
>>>   }
>>>
>>>   /** @brief Is this the Last Node on the Chain
>>>    *
>>> @@ -313,9 +313,9 @@
>>>   RTEMS_INLINE_ROUTINE bool _Chain_Is_last(
>>>     const Chain_Node *the_node
>>>   )
>>>   {
>>> -  return (the_node->next == NULL);
>>> +  return the_node->next->next == NULL;
>>>   }
>>>
>>>   /** @brief Does this Chain have only One Node
>>>    *
>>> _______________________________________________
>>> http://lists.milkymist.org/listinfo.cgi/devel-milkymist.org
>>> IRC: #milkymist at Freenode
>>> _______________________________________________
>>> rtems-users mailing list
>>> rtems-users at rtems.org
>>> http://www.rtems.org/mailman/listinfo/rtems-users
>>
>> _______________________________________________
>> rtems-users mailing list
>> rtems-users at rtems.org
>> http://www.rtems.org/mailman/listinfo/rtems-users
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: spchain.diff
Type: text/x-patch
Size: 1163 bytes
Desc: not available
URL: <http://lists.rtems.org/pipermail/users/attachments/20111110/a7613845/attachment.bin>