apache
Priority Inheritance fails to restore base priority
Reproduce
CONFIG_PRIORITY_INHERITANCE is enabled CONFIG_SEM_PREALLOCHOLDERS is either 0 (use the array of holder) or N use the pre allocated holder list, CONFIG_SEM_NNESTPRIO at 32.
Three tasks all waiting on one Semaphore
Three tasks (name:priority) A:200, B:210, C:220 A takes semaphore. A:200 B waits semaphore. A:210 C waits semaphore A:220 A posts semaphore A:210 <- it is removed as a holder and C takes semaphore A:210 not resotred. C posts semaphore A:210 B takes semaphore A:210 B posts semaphore A:210
OStest PR coming...
This may have been resolved on master after https://github.com/apache/incubator-nuttx/pull/5171 came in. But the test was not detecting the issue. - I will re-test with master and report back
It is still broken. Tested with NuttX master f2bc4555bb0a4386ecc10ac04eb2de34864835e4 NuttX Apps f2bc4555bb0a4386ecc10ac04eb2de34864835e4
priority_inheritance: Restoration Test:
priority_inheritance: Task0 initial priority is:200
priority_inheritance: Task1 initial priority is:210
priority_inheritance: Task2 initial priority is:220
priority_inheritance: Waiting for Task-0 to complete
priority_inheritance: Task0 Started, waiting 0 uS to take count
priority_inheritance: Task1 Started, waiting 10000 uS to take count
priority_inheritance: Task0 priority was:200 is:210
priority_inheritance: Task2 Started, waiting 20000 uS to take count
priority_inheritance: Task0 priority was:210 is:220
priority_inheritance: Task0 Posted
priority_inheritance: Task0 priority was:220 is:210
priority_inheritance: Task-0 Priority is 210, and was not restored to 200
priority_inheritance: Waiting for Task-1 to complete
priority_inheritance: Task2 Posted
priority_inheritance: Task2 priority was:220 is:220
priority_inheritance: Task1 Posted
priority_inheritance: Task1 priority was:210 is:210
priority_inheritance: Waiting for Task-2 to complete
priority_inheritance: ERROR: FAIL Priorities were not correctly restored.
priority_inheritance: Finished
Few questions on this test:
- What is the value of
SEM_NNESTPRIO? - What is the value of
SEM_PREALLOCHOLDERS?
Few questions on this test:
- What is the value of
SEM_NNESTPRIO?- What is the value of
SEM_PREALLOCHOLDERS?
SEM_NNESTPRIO=32 SEM_PREALLOCHOLDERS=64
@pkarashchenko master has diverged from 10.1.0+ when https://github.com/apache/incubator-nuttx/pull/5171 came in.
Here is what I have to resolve the issues for 10.1.0+
@davids5 I've looked into the 10.1.0+ changes to cover described test case and made some drawings on the paper of other possible test cases. My conclusion is that your changes as well as some changes that I prototyped locally can cover only particular corner cases and will only overcomplicate logic and not cover all the possible cases.
The case is that task pend_reprios does not cover the source of re-prioritisation (I mean if task holds 2 semaphores and first time it was reprioritised due to holding semaphore 1 and second time due to semaphore 2) so correct restoring to base priority is not possible.
I see as a robust solution a way that we need to equip each semaphore with a list of tasks waiting for that semaphore (in case of priority inheritance only of course) and when task release a semaphore it iterates the tasks wait list for all semaphores that it holds and find the highest priority from that lists. If that priority is higher than task base prio then priority should be dropped to the highest priority of the waiting task otherwise base priority should be set.
I try to explore some design descriptions for current implementation to ensure that I understand all design points of the current implementation correctly.
@pkarashchenko
Thanks for looking into this. It can be complex with multi counts, multi semaphores being held.
The case is that task pend_reprios does not cover the source of re-prioritisation (I mean if task holds 2 semaphores and first time it was reprioritised due to holding semaphore 1 and second time due to semaphore 2) so correct restoring to base priority is not possible.
Would you walk me through the fail with a little more detail?
We have tested our 10.1.0+ uses cases: single thread with multi count, multi semaphores and the issues is resolved. There is an artificial case if the lowest priority holder holds a second semaphore and never releases it.
I agree the design needs to be rethought out in upstream (with https://github.com/apache/incubator-nuttx/pull/5171) I am happy to work through that with you, but have not looked at how what https://github.com/apache/incubator-nuttx/pull/5171 changed it.
I modified your test and added "task0.5" with priority 209 (in between of task0 and task1) and one additional semaphore (lets call it also "sem0.5"). So now task0 takes sem0.5 and g_sem at start and hold both for a fair amount of time. Them task0.5 tries to take sem0.5 and task0 prio is boosted to 209. Then your scenario is "played":
- task2 tries to take g_sem an task0 priority is boosted to 210
- task3 tries to take g_sem an task0 priority is boosted to 220
- task0 post a g_sem and task0 prio is set to 210. Here with your 10.1.0+ fix
htcb->nsem_heldis still!= 0because of task0.5 - then task0 runs at 210 priority while task0.5 with 209 is preempted, so neither 209 nor base prio can be set for task0
- then task0 posts sem0.5 and task0 prio still remains at 209. Here your 10.1.0+ fix could help to get back to base prio, but if we add task1.5 with with prio 219 that tries to get sem0.5 or add one more mutex then we can build a cascade, so priorities will be restored to wrong values. Of course 10.1.0+ fix could help at the end when task0 does not hold any semaphore to restore to base prio, but still as I wrote this is only a fix for the corner case.
So one of the possible solutions could be moving pend_reprios from struct tcb_s to a struct semholder_s, but that would grow memory consumption a lot. I tried to prototype changes where I save only the prio of highest priority task waiting on semaphore in struct semholder_s, but that fails in case if we are having multiple tasks with the same priority. So we definitely need to track both the origin of reprio and reprio priority. That is why I wrote that one of the possible solutions could be to "equip each semaphore with a list of tasks waiting for that semaphore and when task release a semaphore it iterates the tasks wait list for all semaphores that it holds and find the highest priority from that lists" so we will can rely on the actual data when task release the semaphore.
The other method could be to iterate g_waitingforsemaphore the n times where n is a number of currently held semaphores. But the complexity of such operation might be quite high. So we can pick all the tasks that are waiting for each semaphore, then get the maximum priority across those tasks and adjust current task priority based on that.
@pkarashchenko - I am looking into the behavior if the pthread_barrier, and I am wondering if the init should be excluding the _barrier's semaphore from being involved in priority Inheritance. The threads all start as waiters then all end up of as holders. The pthread_barrier_destroy then destroys the semaphore with all the holders holding counts. This will debug assert in nxsem_destroyholder
@davids5 I think you are still looking into 10.1.0+ code. The bug with pthread_barrier was identified and fixed by adding sem_setprotocol(&barrier->sem, SEM_PRIO_NONE);, so it should be safe to use on mainline
I drafted some changes in https://github.com/apache/incubator-nuttx/pull/6318 The test described in this issue pass, but I didn't tried all the other OS tests related to priority inheritance. Will do it tomorrow. @davids5 you can take a look if you have time
P.S. I think there definitely is some error in my logic, but still this is just a POC
UDP: I fixed few bugs, so my 4 task test also pass, but again iterating g_waitingforsemaphore might be too heavy, so maybe it is good to have such list per-semaphore and the upper loop can iterate htcb->holdsem while inner will iterate only a relevant tasks. But anyway that is an optimization mostly.
The ostest seems to pass, but it contains really few tests related to priority inheritance.
@pkarashchenko - I have to get a few things off my plate and then I can circle back to test this.
@pkarashchenko I had a go at trying to fix this as well here: https://github.com/apache/incubator-nuttx/pull/6341. Could be fairly memory intensive though.
@ThomasDebrunner I did the same during some of my experiments, but issued a https://github.com/apache/incubator-nuttx/pull/6318 because considered memory consumption increase tradeoff as too much and considered logic to track tuples to be quite complicated (possibly missing some other corner cases). Thats very good that you are looking into this as well!
I've been thinking about this issue on the background and I think I know how to solve it by keeping code efficiency. Will try to work on this next week and come with some drafted solution.
@davids5 my new idea didn't work as expected, but I did a significant performance improvements (compared to my original one) in https://github.com/apache/incubator-nuttx/pull/6318
The kwork_inherit functionality is a bit blurred to me. For now I implemented an option for a single priority boost for kwork. I'm not sure if multi-boost is required. Currently only NuttX asynchronous I/O logic uses this dynamic prioritization, so I can add a boost stacking support under a config option (but it is not there for now).
@pkarashchenko - Sorry for the late response I was traveling. Are the performance improvements pushed to https://github.com/apache/incubator-nuttx/pull/6318 ? Why would kwork_inherit be any different in the context of the running thread: While kwork is running a thread that is holding a resource and it's priority is < waiter?
@davids5 yes. The changes are pushed. Regarding the kwork_inherit I do not fully understand your question. I will double check, but I think that kwork_inherit works exactly as before. There is a way to boost priority of lpwork externally via lpwork_boostpriority. If kwork is running a thread and is holding any resource that other higher priority thread is waiting, then the priority of kwork will rise above boosted priority and will go back after resource is released. Maybe you can expand description of a situation that you are writing about.
@pkarashchenko - Sorry for being unclear.
kwork will rise above boosted priority and will go back after resource is released
Sounds correct.
he kwork_inherit functionality is a bit blurred to me.
What is blurred for you? The external interface boosting and the priority inheritance bosting?
@pkarashchenko - Sorry for being unclear.
kwork will rise above boosted priority and will go back after resource is released
Sounds correct.
he kwork_inherit functionality is a bit blurred to me.
What is blurred for you? The external interface boosting and the priority inheritance bosting?
When I was writing the original message the blurred part was do we need to support nested boosting. For example we have two subsystems that use LP work and each call lpwork_boostpriority() with a different priority value. The original code supports it, but after my rework I added /* REVISIT: Priority multi-boost is not supported */ comment and DEBUGASSERT() since currently there is only one user for kwork priority boost. Also I'm not sure why do we need to boost priority for kwork at all when priority inheritance is enabled since the priority will be boosted (inherited) automatically as soon as there will be a waiter for a resource hold by kwork. Maybe I'm missing some part of a bigger picture.