Uniprocessor implementation of nested mutex problem of priority inversion.

Fri Aug 14 20:05:03 UTC 2015

Hi,

I have implemented the validate method. following are the links for it:
github: https://github.com/saurabhgadia4/rtems/tree/nested-mutex
commit:
https://github.com/saurabhgadia4/rtems/commit/e7f0f169c056076c46ef5ea17b0c38efe33fe576

I am waiting on the decision of how to integrate call to this
_Thread_Validate_Priority.

Thanks,

Saurabh Gadia

On Fri, Aug 14, 2015 at 10:06 AM, Saurabh Gadia <gadia at usc.edu> wrote:

> And in respect of efficiency, we have to traverse through all the mutex
> held my the thread and do the checking. There is no other way to confirm
> that priority inversion has occurred or not. One way we can do is have
> default argument variable for core_mutex_surrender but then there is change
> in API call semantics. So kind of stuck between which way to take.
>
> One way is that we can do lazy evaluation. following should be the calling
> pair:
> task1()
> {
> ...
> ...
> rtems_semaphore_release()
> validate()
> }
> these pairs should be intact so even if the task1 thread gets preempted
> after calling rtems_semaphore_release(), then other thread will get control
> of processor. When this task1 thread get the control back then next call it
> will do is validate() which is no harm to us as only task 1 thread can
> release rest of its resources of we have owner release binding. But there
> can be one problem that is Till the task 1 thread get the control back its
> priority may be promoted by other task thread. So it won't be 100% accurate
> validate test.
>
> Main problem still exists is: For uniprocessor(for this project scope)
> implementation how can we make sure that only after validate method task1
> can be preempted ( To acheive this behavior I guess we will need to make
> change to core_mutex_surrender).
>
> Thanks,
>
> Saurabh Gadia
>
> On Fri, Aug 14, 2015 at 9:43 AM, Saurabh Gadia <gadia at usc.edu> wrote:
>
>> When a thread releases a semaphore/mutex we call this validate method to
>> make sure that there does not exists any priority inversion. Following is
>> the course of action that needs to be performed:
>>
>> 1. Validate method needs to be called within mutex_surrender method
>> because after releasing a mutex a new holder thread can get scheduled and
>> then we can't call validate method. We need to do call validate before we
>> enable interrupts in uniprocessor or dispatching of threads.
>>
>> 2. Functioning of validate method: input param -  executing thread
>> (thread which releases the mutex)
>>
>> 2.a) Go through the list of Mutex Chain i.e( Chain_Control lock_mutex;)
>> in TCB.
>> 2.b) Extract mutex from the chain node linked list. This gives us
>> (the_mutex->queue.lock_queue) from which we will extract mutex by using
>> CONTAINER_OF() method.
>>
>> 2.c) Now access the thread wait queue of this mutex
>> i.e(the_mutex->Wait_queue) to get the information about the first waiting
>> thread in this waitqueue by calling
>> _Thread_queue_First_locked(&the_mutex->Wait_queue)
>>
>> 2.d) Now check whether
>> assert(releasingThread.current_priority<=first_locked_thread.currentPriority).
>> If assertion fails then there is priority inversion problem and we can
>> break out of loop and return error status.
>>
>> 2.e) Repeat from 2.a till all acquired resources are visited present in
>> Chain_Control of releasing thread.
>>
>> So I am sceptical about how can I include this validate method in the
>> _CORE_mutex_Surrender(). We can have it as a separate call from user level
>> but then we need to make sure that the thread dispatch mechanism is
>> disabled. If not then whether including this validate method in
>> _CORE_mutex_Surrender for only strict_order_mutex and Priority inheritance
>> attribute is feasible or not.
>>
>> Please guide me on this.
>>
>>
>> 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
>>>> >>
>>>> >
>>>>
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20150814/50249178/attachment-0002.html>