Re: Uniprocessor implementation of nested mutex problem of priority inversion.
Hello Saurabh,
I created a ticket to document some requirements for a mutex
implementation. Its not complete and just a starting point:
https://devel.rtems.org/ticket/2412
On 17/08/15 07:45, Saurabh Gadia wrote:
For every mutex held by a thread it is not feasible to have reference
to CORE_mutex_order_list of all mutex that it holds.*I feel that
current solution with CORE_mutex_order_list as argument is the best
choice to have as it is O(1) operation and needs no extra bookkeeping
for the thread.
*
In JPF model we have it as follows:
public List mutexOrderList; //it is a linkedList which stores
acquired mutex objects in LIFO order.
and to extract the index of mutex we call :
public int getMutexIndex(Mutex obj)
{
return mutexOrderList.indexOf(obj);
}
Lets see it through example:
Holder thread: H
Mutex being acquired by executing thread which is acquired by holder
thread(H): M
Executing thread: T
From rtems we have following information:
1. In TCB:
Every thread maintains a list of mutex acquired by it through out its
course in doubly circular linked list fashion :
#ifdef __RTEMS_STRICT_ORDER_MUTEX__
/** This field is the head of queue of priority inheritance mutex
* held by the thread.
*/
Chain_Controllock_mutex;
#endif
thread->lock_mutex
2. In Mutex Control Block:
typedef struct{
/** This field is a chian of locked mutex by a thread,new mutex will
* be added to the head of queue, and the mutex which will be
released
* must be the head of queue.
*/
Chain_Nodelock_queue;
/** This field is the priority of thread before locking this mutex
*
*/
Priority_Control priority_before;
} CORE_mutex_order_list;
Mutex->queue
When a thread acquires a mutex the mutex->queue.lock_queue node is
prepended to the holder's H->lock_mutex.
This way we can traverse through all mutex's acquired by holder thread.
Now when executing thread tries to acquire the mutex M which is
acquired by the holder thread(H) it wants to raise the recorded
priority before of all mutex's acquired by the holder after acquiring
mutex M. So the best way to do it in O(1) operation and without
storing any reference we do it in following manner in new solution:
while(check!=head)
{
queue = RTEMS_CONTAINER_OF(check, CORE_mutex_order_list, lock_queue);
if(!(queue->priority_before > new_priority))
{
return PRIORITY_STATUS_NOT_CHANGED;
}
queue->priority_before = new_priority;
check = check->previous;
}
This is the most efficient way we can do that. We don't need to
change any design for this nor need to do any bookkeeping thing.
Thanks,
Saurabh Gadia
On Sun, Aug 16, 2015 at 6:48 PM, Gedare Bloom > wrote:
We will rely on the linker should not pull the function in if unused.
So if it is only referenced by test code, this solution may be fine.
Gedare
On Sun, Aug 16, 2015 at 7:50 PM, Cyrille Artho
> wrote:
> Hi all,
> As I wrote earlier, I think it makes sense to include validate but
> compile it conditionally. We want to use it for regression
testing but
> not in deployed code.
> Which macros do you use for this purpose?
>
> On Sat, Aug 15, 2015 at 2:50 PM, Cyrille Artho
> wrote:
>> I will look at the code in detail on Monday, but we should keep in
>> mind that validate is only needed for testing. It does not have
to be
>> compiled into the final code otherwise.
>> So we do not have to be overly concerned with its performance but
>> instead we have to make sure that validate itself is not subject to
>> data races.
>>
>> On Sat, Aug 15, 2015 at 5:05 AM, Saurabh Gadia > wrote:
>>> 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 > 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
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
We will rely on the linker should not pull the function in if unused.
So if it is only referenced by test code, this solution may be fine.
Gedare
On Sun, Aug 16, 2015 at 7:50 PM, Cyrille Artho cyrille.ar...@gmail.com wrote:
Hi all,
As I wrote earlier, I think it makes sense to include validate but
compile it conditionally. We want to use it for regression testing but
not in deployed code.
Which macros do you use for this purpose?
On Sat, Aug 15, 2015 at 2:50 PM, Cyrille Artho cyrille.ar...@gmail.com
wrote:
I will look at the code in detail on Monday, but we should keep in
mind that validate is only needed for testing. It does not have to be
compiled into the final code otherwise.
So we do not have to be overly concerned with its performance but
instead we have to make sure that validate itself is not subject to
data races.
On Sat, Aug 15, 2015 at 5:05 AM, Saurabh Gadia ga...@usc.edu wrote:
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 ga...@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 ga...@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 ga...@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
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
For every mutex held by a thread it is not feasible to have reference to
CORE_mutex_order_list of all mutex that it holds.
* I feel that current solution with CORE_mutex_order_list as argument is
the best choice to have as it is O(1) operation and needs no extra
bookkeeping for the thread.*
In JPF model we have it as follows:
public ListMutex mutexOrderList; //it is a linkedList which stores
acquired mutex objects in LIFO order.
and to extract the index of mutex we call :
public int getMutexIndex(Mutex obj)
{
return mutexOrderList.indexOf(obj);
}
Lets see it through example:
Holder thread: H
Mutex being acquired by executing thread which is acquired by holder
thread(H): M
Executing thread: T
From rtems we have following information:
1. In TCB:
Every thread maintains a list of mutex acquired by it through out its
course in doubly circular linked list fashion :
#ifdef __RTEMS_STRICT_ORDER_MUTEX__
/** This field is the head of queue of priority inheritance mutex
* held by the thread.
*/
Chain_Controllock_mutex;
#endif
thread-lock_mutex
2. In Mutex Control Block:
typedef struct{
/** This field is a chian of locked mutex by a thread,new mutex will
* be added to the head of queue, and the mutex which will be released
* must be the head of queue.
*/
Chain_Nodelock_queue;
/** This field is the priority of thread before locking this mutex
*
*/
Priority_Control priority_before;
} CORE_mutex_order_list;
Mutex-queue CORE_mutex_order_list
When a thread acquires a mutex the mutex-queue.lock_queue node is
prepended to the holder's H-lock_mutex.
This way we can traverse through all mutex's acquired by holder thread.
Now when executing thread tries to acquire the mutex M which is acquired by
the holder thread(H) it wants to raise the recorded priority before of all
mutex's acquired by the holder after acquiring mutex M. So the best way to
do it in O(1) operation and without storing any reference we do it in
following manner in new solution:
while(check!=head)
{
queue = RTEMS_CONTAINER_OF(check, CORE_mutex_order_list, lock_queue);
if(!(queue-priority_before new_priority))
{
return PRIORITY_STATUS_NOT_CHANGED;
}
queue-priority_before = new_priority;
check = check-previous;
}
This is the most efficient way we can do that. We don't need to change any
design for this nor need to do any bookkeeping thing.
Thanks,
Saurabh Gadia
On Sun, Aug 16, 2015 at 6:48 PM, Gedare Bloom ged...@rtems.org wrote:
We will rely on the linker should not pull the function in if unused.
So if it is only referenced by test code, this solution may be fine.
Gedare
On Sun, Aug 16, 2015 at 7:50 PM, Cyrille Artho cyrille.ar...@gmail.com
wrote:
Hi all,
As I wrote earlier, I think it makes sense to include validate but
compile it conditionally. We want to use it for regression testing but
not in deployed code.
Which macros do you use for this purpose?
On Sat, Aug 15, 2015 at 2:50 PM, Cyrille Artho cyrille.ar...@gmail.com
wrote:
I will look at the code in detail on Monday, but we should keep in
mind that validate is only needed for testing. It does not have to be
compiled into the final code otherwise.
So we do not have to be overly concerned with its performance but
instead we have to make sure that validate itself is not subject to
data races.
On Sat, Aug 15, 2015 at 5:05 AM, Saurabh Gadia ga...@usc.edu wrote:
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 ga...@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
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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 ga...@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 ga...@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 ga...@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 ged...@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 ga...@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
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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 ga...@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 ga...@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 ged...@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 ga...@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
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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 ga...@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 ged...@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 ga...@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 ga...@usc.edu wrote: Ok. I will mail you back soon. On Thursday, August 13, 2015, Gedare Bloom ged...@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 ga...@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:
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
Can you please print the output from spsem04 without strict-order enabled? (Or, without your patches to fix it?) On Thu, Aug 13, 2015 at 6:31 AM, Saurabh Gadia ga...@usc.edu wrote: Hi, To validate spsem03 test case I created a new test case by modifying spsem02. Below is the description of the new test case: Task: TA01 having priority 36, TA02 having priority 34, TA03 having priority 32. Throughout the course following actions are performed: TA01 acquires S0 TA02 acquires S1 and then S0 TA03 acquires S1 Timeline: TA01 acquires S0 with priority 36. TA01 spawns TA02 having priority 32. TA02 takes over as it has higher priority than TA01. TA02 acquires S1 with priority 34. TA02 tries to acquire S0 but it is locked so promotes TA01 priority to 34. TA01 gains control and now creates TA03 having 32. TA03 takes over and tries to acquire S1. But it is acquired by TA02. TA03 promotes TA02 priority to 32. But it observe that TA02 is also waiting on mutex held by TA01. TA03 promotes TA01 priority to 32 as well. (Indirect reference case). TA01 get control. It releases S0 and now its priority becomes 36 so TA02 takes over, TA02 acquires S0. TA02 releases S0 and S1. And its priority now becomes 34(real priority) TA03 takes over. It acquires S1. Releases S1 and suspends self. Now TA02 gets control. It also suspends self. Now TA01 gets control and exits the test. Following is the output: *** 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 (acquires S0) TA02: started with priority 34 (creates TA02) TA02: priority 34, holding S1 (acquires S1) TA01: priority 34, holding S0 and now creating TA03 TA03: started with priority 32 TA01: priority 32 Releasing s0 (Priority of TA02 and TA01 got promoted to 32). 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 *** [Inferior 1 (process 42000) exited normally] So this is sufficient to prove that spsem03 test passes as we just modelled it above. Thanks, Saurabh Gadia On Thu, Aug 13, 2015 at 2:28 AM, Saurabh Gadia ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia On Thu, Aug 13, 2015 at 9:10 AM, Saurabh Gadia ga...@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 ged...@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 ga...@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 ga...@usc.edu wrote: Ok. I will mail you back soon. On Thursday, August 13, 2015, Gedare Bloom ged...@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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia -- Thanks, Saurabh Gadia ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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. Thanks, Saurabh Gadia On Thu, Aug 13, 2015 at 12:51 PM, Gedare Bloom ged...@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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia On Thu, Aug 13, 2015 at 9:10 AM, Saurabh Gadia ga...@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 ged...@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 ga...@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 ga...@usc.edu wrote: Ok. I will mail you back soon. On Thursday, August 13, 2015, Gedare Bloom ged...@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 ga...@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
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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.ar...@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 ga...@usc.edu wrote: Thanks, Saurabh Gadia -- Forwarded message -- From: Gedare Bloom ged...@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 ga...@usc.edu Cc: devel@rtems.org devel@rtems.org On Thu, Aug 13, 2015 at 6:55 PM, Saurabh Gadia ga...@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 ged...@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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia On Thu, Aug 13, 2015 at 9:10 AM, Saurabh Gadia ga...@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 ged...@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 ga...@usc.edu
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
On Thu, Aug 13, 2015 at 7:31 PM, Cyrille Artho cyrille.ar...@gmail.com wrote: Hi Gedard, The CORE_mutex_order_list in the thread priority update functions is needed to step down the priority in the right way upon unlocking. Currently these functions are only used internally. If you'd like a simpler interface, that list would have to be part of the thread data structure (Thread_Control) itself. However, then we'd add a field to that struct inside an #IFDEF macro. Do you think this is preferable? If they're used internally, can we make them static, or do they need to be shared across multiple subsystems. Internal functions should get extern'ed through the impl.h header file variants. I need to find time (ha!) to look more closely at this. I think the design can be either improved, or made cleaner with respect to information hiding and interface creep. Gedare On Fri, Aug 14, 2015 at 8:01 AM, Saurabh Gadia ga...@usc.edu wrote: Thanks, Saurabh Gadia -- Forwarded message -- From: Gedare Bloom ged...@rtems.org Date: Thu, Aug 13, 2015 at 12:51 PM Subject: Re: Uniprocessor implementation of nested mutex problem of priority inversion. To: Saurabh Gadia ga...@usc.edu Cc: devel@rtems.org devel@rtems.org 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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia On Thu, Aug 13, 2015 at 9:10 AM, Saurabh Gadia ga...@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 ged...@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 ga...@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 ga...@usc.edu wrote: Ok. I
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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 ged...@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.ar...@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 ga...@usc.edu javascript:; wrote: Thanks, Saurabh Gadia -- Forwarded message -- From: Gedare Bloom ged...@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 ga...@usc.edu javascript:; Cc: devel@rtems.org javascript:; devel@rtems.org javascript:; On Thu, Aug 13, 2015 at 6:55 PM, Saurabh Gadia ga...@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 ged...@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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia On Thu, Aug 13, 2015 at 9:10 AM, Saurabh Gadia ga...@usc.edu javascript:; wrote: That is how we were doing in JPF. The validate method was triggered after every release
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
On Thu, Aug 13, 2015 at 6:55 PM, Saurabh Gadia ga...@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 ged...@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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia On Thu, Aug 13, 2015 at 9:10 AM, Saurabh Gadia ga...@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 ged...@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 ga...@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 ga...@usc.edu wrote: Ok. I will mail you back soon. On
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia On Thu, Aug 13, 2015 at 9:10 AM, Saurabh Gadia ga...@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 ged...@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 ga...@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 ga...@usc.edu wrote: Ok. I will mail you back soon. On Thursday, August 13, 2015, Gedare Bloom ged...@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 ga...@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:
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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 ga...@usc.edu wrote: Ok. I will mail you back soon. On Thursday, August 13, 2015, Gedare Bloom ged...@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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia -- Thanks, Saurabh Gadia ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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 ga...@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 ga...@usc.edu wrote: Ok. I will mail you back soon. On Thursday, August 13, 2015, Gedare Bloom ged...@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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia -- Thanks, Saurabh Gadia ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
Re: Uniprocessor implementation of nested mutex problem of priority inversion.
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 ged...@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 ga...@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 ga...@usc.edu wrote: Ok. I will mail you back soon. On Thursday, August 13, 2015, Gedare Bloom ged...@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 ga...@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=0B44HRKVuGCkFfnFDVmxqQzZZUzljNUg4YmVPZmEybEp2Q0NNclpvS2FvemZ4Tm5Xa19nemMusp=sharing Thanks, Saurabh Gadia -- Thanks, Saurabh Gadia ___ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel
