Uniprocessor implementation of nested mutex problem of priority inversion.

Thu Aug 13 23:32:19 UTC 2015

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