Uniprocessor implementation of nested mutex problem of priority inversion.

Fri Aug 14 00:08:18 UTC 2015

I see, it is the "list" being passed, not the mutex_control. I misread
something earlier.

It may be acceptable to store a pointer to this list into the
Thread_Control somewhere if that will simplify the interface and not
complicate the implementation by too much. But I haven't given this
too much thought. Saurabh can continue to fix the other issues and we
can discuss these new functions a bit more yet.

Gedare

On Thu, Aug 13, 2015 at 7:39 PM, Cyrille Artho <cyrille.artho at gmail.com> wrote:
> The Wait_queue maintains a queue of threads that try to obtain a lock,
> but the CORE_mutex_order_list is a list of locks currently held by a
> given thread. The former decides who gets the lock next (once it is
> released), and the latter is needed to step down the priority of the
> former lock holder on release.
> One data structure contains threads, the other one locks; it is not
> possible to eliminate one of them (at least not without a major
> redesign of all the other code).
>
> On Fri, Aug 14, 2015 at 8:34 AM, Saurabh Gadia <gadia at usc.edu> wrote:
>>
>> Thanks,
>>
>> Saurabh Gadia
>>
>> ---------- Forwarded message ----------
>> From: Gedare Bloom <gedare at rtems.org>
>> Date: Thu, Aug 13, 2015 at 4:32 PM
>> Subject: Re: Uniprocessor implementation of nested mutex problem of priority
>> inversion.
>> To: Saurabh Gadia <gadia at usc.edu>
>> Cc: "devel at rtems.org" <devel at rtems.org>
>>
>>
>> On Thu, Aug 13, 2015 at 6:55 PM, Saurabh Gadia <gadia at usc.edu> wrote:
>>> How can we get mutex->queue.priority_before data structure without having
>>> the mutex structure. We need that to change the priority_before for every
>>> acquired mutex by a thread to ensure that there is proper stepdown of
>>> priority. We just need to have mutex to get the start point of the
>>> chain_control and then we traverse upto the head of the chain to
>>> manipulate
>>> the priority_before if required
>>
>> From what I see, you're approximately using container_of(holder,
>> queue) to get the thread queue, from that you can get the Wait_queue
>> in the mutex_control, and find the priority_before. So you don't need
>> to pass the pointer to the mutex_control if you can recover it from
>> the holder thread_control, right?
>>
>> Just add some conditional code (based on RTEMS_SMP and/or
>> STRICT_ORDER) in the existing functions that follows the pointer from
>> the thread to the threadq to the mutex to find the priority_before.
>> Unless I missed something.
>>
>> Gedare
>>
>>> Thanks,
>>>
>>> Saurabh Gadia
>>>
>>> On Thu, Aug 13, 2015 at 12:51 PM, Gedare Bloom <gedare at rtems.org> wrote:
>>>>
>>>> Saurabh,
>>>>
>>>> Remove the commit "Updated the motivation for creating the new
>>>> branch", don't add the .tags files, and don't add the .m4 changes that
>>>> are not related to your project.
>>>>
>>>> Switch to using RTEMS_CONTAINER_OF macro and remove the typeaddr one.
>>>>
>>>> coremutexseize.c : remove the modification where you deleted a blank
>>>> space randomly.
>>>>
>>>> threadimpl.h : follow the score naming conventions (
>>>> https://devel.rtems.org/wiki/Developer/Coding/NamingRules ) for the
>>>> new functions you introduce. Can you explain clearly why new functions
>>>> are needed? Also, I'm not particularly satisfied with the use of the
>>>> CORE_mutex_order_list type in these Thread functions. I don't see why
>>>> the mutex should be "baked in" to the Thread functions interface.
>>>> Tracking through the code, I can't even tell if it is necessary to
>>>> pass this argument around. Can you say whether or not you need to keep
>>>> this argument?
>>>>
>>>> Read the coding conventions for the style guidelines with respect to
>>>> block scoping. Also watch out for line lengths > 80 characters. Add
>>>> doxygen for new functions you introduce if they are kept around.
>>>>
>>>> For changes where the UP function invoked differs from the SMP, can
>>>> you please add a comment to justify the difference. I want to
>>>> understand why a particular code-path is followed for UP but not SMP.
>>>>
>>>> That's all for now, thanks!
>>>> Gedare
>>
>>>>
>>>>
>>>> On Thu, Aug 13, 2015 at 1:55 PM, Saurabh Gadia <gadia at usc.edu> wrote:
>>>> > Hi,
>>>> >
>>>> > I have created a new branch for uniprocessor solution of priority
>>>> > inversion
>>>> > problem caused by nested mutex behavior.
>>>> >
>>>> > link: https://github.com/saurabhgadia4/rtems/tree/nested-mutex
>>>> > test case results:
>>>> >
>>>> >
>>>> > https://drive.google.com/folderview?id=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemM&usp=sharing
>>>> >
>>>> > Thanks,
>>>> >
>>>> > Saurabh Gadia
>>>> >
>>>> > On Thu, Aug 13, 2015 at 9:10 AM, Saurabh Gadia <gadia at usc.edu> wrote:
>>>> >>
>>>> >> That is how we were doing in JPF. The validate method was triggered
>>>> >> after
>>>> >> every release of mutex by any thread and we would check for all the
>>>> >> waiting
>>>> >> threads on mutex's held by the holder. And if it finds a thread with
>>>> >> higher
>>>> >> priority blocked then it would panic or give assertion failure.
>>>> >>
>>>> >> Thanks,
>>>> >>
>>>> >> Saurabh Gadia
>>>> >>
>>>> >> On Thu, Aug 13, 2015 at 9:08 AM, Gedare Bloom <gedare at rtems.org>
>>>> >> wrote:
>>>> >>>
>>>> >>> Thanks. Would it be possible for you to turn the failure cases into
>>>> >>> real test failures? In other words, add some logic to detect the
>>>> >>> priority inversion and abort the test?
>>>> >>>
>>>> >>> Gedare
>>>> >>>
>>>> >>> On Thu, Aug 13, 2015 at 12:05 PM, Saurabh Gadia <gadia at usc.edu>
>>>> >>> wrote:
>>>> >>> > Hi,
>>>> >>> >
>>>> >>> > Following is the result of spsem04 test without the patch:
>>>> >>> >
>>>> >>> > *** BEGIN OF TEST SPSEM 4 ***
>>>> >>> >
>>>> >>> > init: S0 created
>>>> >>> >
>>>> >>> > init: S1 created
>>>> >>> >
>>>> >>> > init: TA01 created with priority 36
>>>> >>> >
>>>> >>> > init: TA02 created with priority 34
>>>> >>> >
>>>> >>> > init: TA03 created with priority 32
>>>> >>> >
>>>> >>> > TA01: started with priority 36
>>>> >>> >
>>>> >>> > TA01: priority 36, holding S0
>>>> >>> >
>>>> >>> > TA02: started with priority 34
>>>> >>> >
>>>> >>> > TA02: priority 34, holding S1
>>>> >>> >
>>>> >>> > TA01: priority 34, holding S0 and now creating TA03
>>>> >>> >
>>>> >>> > TA03: started with priority 32
>>>> >>> >
>>>> >>> > TA01: priority 34 Releasing s0 (This is priority inheritance
>>>> >>> > problem
>>>> >>> > as
>>>> >>> > TA02
>>>> >>> > waits on mutex held by TA01 and has higher priority than TA01. TA03
>>>> >>> > just
>>>> >>> > promotes the priority TA02.)
>>>> >>> >
>>>> >>> > TA02: priority 32, holding S1,S0
>>>> >>> >
>>>> >>> > TA02: priority 32 before releasing S0
>>>> >>> >
>>>> >>> > TA02: priority 32 after releasing S0
>>>> >>> >
>>>> >>> > TA02: priority 32 before releasing S1
>>>> >>> >
>>>> >>> > TA03: priority 32, holding S1
>>>> >>> >
>>>> >>> > TA03: priority 32
>>>> >>> >
>>>> >>> > TA03: suspending
>>>> >>> >
>>>> >>> > TA02: priority 34 after releasing S1
>>>> >>> >
>>>> >>> > TA02: suspending
>>>> >>> >
>>>> >>> > TA01: priority 36
>>>> >>> >
>>>> >>> > TA01: exiting
>>>> >>> >
>>>> >>> > *** END OF TEST SPSEM 4 ***
>>>> >>> >
>>>> >>> > You can see the difference in highlighted portions of both outputs.
>>>> >>> >
>>>> >>> > Thanks,
>>>> >>> >
>>>> >>> > Saurabh Gadia
>>>> >>> >
>>>> >>> > On Thu, Aug 13, 2015 at 8:17 AM, Saurabh Gadia <gadia at usc.edu>
>>>> >>> > wrote:
>>>> >>> >>
>>>> >>> >> Ok. I will mail you back soon.
>>>> >>> >>
>>>> >>> >>
>>>> >>> >> On Thursday, August 13, 2015, Gedare Bloom <gedare at rtems.org>
>>>> >>> >> wrote:
>>>> >>> >>>
>>>> >>> >>> Saurabh,
>>>> >>> >>>
>>>> >>> >>> Please pull from rtems.git again, create a new branch from
>>>> >>> >>> 'master',
>>>> >>> >>> and apply your changes to the branch. It's too hard to review
>>>> >>> >>> code
>>>> >>> >>> that is not all by itself on a branch.
>>>> >>> >>>
>>>> >>> >>> Gedare
>>>> >>> >>>
>>>> >>> >>> On Thu, Aug 13, 2015 at 5:28 AM, Saurabh Gadia <gadia at usc.edu>
>>>> >>> >>> wrote:
>>>> >>> >>> > Hi,
>>>> >>> >>> >
>>>> >>> >>> > I have implemented uniprocessor model of nested mutex problem
>>>> >>> >>> > in
>>>> >>> >>> > rtems.
>>>> >>> >>> > its
>>>> >>> >>> > still in basic form. I tried to multiplex it with the existing
>>>> >>> >>> > solution
>>>> >>> >>> > but
>>>> >>> >>> > was finding hard time. To push ahead, I decided to have
>>>> >>> >>> > separate
>>>> >>> >>> > functions
>>>> >>> >>> > for uniprocessor and SMP(kept default behavior) and with your
>>>> >>> >>> > review
>>>> >>> >>> > comments will know what to do. Following is the link for the
>>>> >>> >>> > git
>>>> >>> >>> > repo:
>>>> >>> >>> > https://github.com/saurabhgadia4/rtems/commits/master and its
>>>> >>> >>> > JPF
>>>> >>> >>> > branch:
>>>> >>> >>> >
>>>> >>> >>> >
>>>> >>> >>> >
>>>> >>> >>> >
>>>> >>> >>> > https://github.com/saurabhgadia4/lock-model/blob/uniproc-new1/rtems/Mutex.java
>>>> >>> >>> >
>>>> >>> >>> > I have also tested spsem01, 02, 03 test cases. Following are
>>>> >>> >>> > the
>>>> >>> >>> > links
>>>> >>> >>> > for
>>>> >>> >>> > the test case results which states output before solution and
>>>> >>> >>> > after
>>>> >>> >>> > applying
>>>> >>> >>> > the solution. I am still not getting whether my code is passing
>>>> >>> >>> > spsem03
>>>> >>> >>> > test
>>>> >>> >>> > or not. How can I verify that?
>>>> >>> >>> >
>>>> >>> >>> > Test Case Link:
>>>> >>> >>> >
>>>> >>> >>> >
>>>> >>> >>> >
>>>> >>> >>> >
>>>> >>> >>> > https://drive.google.com/folderview?id=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemM&usp=sharing
>>>> >>> >>> >
>>>> >>> >>> > Thanks,
>>>> >>> >>> >
>>>> >>> >>> > Saurabh Gadia
>>>> >>> >>
>>>> >>> >>
>>>> >>> >>
>>>> >>> >> --
>>>> >>> >> Thanks,
>>>> >>> >>
>>>> >>> >> Saurabh Gadia
>>>> >>> >>
>>>> >>> >
>>>> >>
>>>> >>
>>>> >
>>>
>>>
>>
>
>
>
> --
> Regards,
> Cyrille Artho