Uniprocessor implementation of nested mutex problem of priority inversion.

Fri Aug 14 00:22:15 UTC 2015

Yeah. I am working now on developing a validate method to point out bad and
good results. And documentation seems to be super important for now because
I feel that logic is correct just some semantics based on above discussion
will change.

On Thursday, August 13, 2015, Gedare Bloom <gedare at rtems.org> wrote:

> 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
> <javascript:;>> 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
> <javascript:;>> wrote:
> >>
> >> Thanks,
> >>
> >> Saurabh Gadia
> >>
> >> ---------- Forwarded message ----------
> >> From: Gedare Bloom <gedare at rtems.org <javascript:;>>
> >> 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 <javascript:;>>
> >> Cc: "devel at rtems.org <javascript:;>" <devel at rtems.org <javascript:;>>
> >>
> >>
> >> On Thu, Aug 13, 2015 at 6:55 PM, Saurabh Gadia <gadia at usc.edu
> <javascript:;>> 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
> <javascript:;>> 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
> <javascript:;>> 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
> <javascript:;>> 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
> <javascript:;>>
> >>>> >> 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
> <javascript:;>>
> >>>> >>> 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
> <javascript:;>>
> >>>> >>> > wrote:
> >>>> >>> >>
> >>>> >>> >> Ok. I will mail you back soon.
> >>>> >>> >>
> >>>> >>> >>
> >>>> >>> >> On Thursday, August 13, 2015, Gedare Bloom <gedare at rtems.org
> <javascript:;>>
> >>>> >>> >> 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
> <javascript:;>>
> >>>> >>> >>> 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
>

-- 
Thanks,

Saurabh Gadia
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20150813/1245a780/attachment-0002.html>