_Chain_Is_first/last overshoot

[Joel Sherrill]

On 11/10/2011 02:57 PM, Gedare Bloom wrote:
> Attached patch breaks with CVS head, showing that our current
> implementation of Chain_Is_first contradicts _Chain_First.
Thanks Gedare.  I think this needs a PR and both
this change and the test diff you have need to be
applied.

--joel
> 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
>>>


-- 
Joel Sherrill, Ph.D.             Director of Research&  Development
joel.sherrill at OARcorp.com        On-Line Applications Research
Ask me about RTEMS: a free RTOS  Huntsville AL 35805
    Support Available             (256) 722-9985