Real-time futexes (priority inheritance/protection/robust support) take 5

Hi all

More fixes for the real-time futexes. Priority inheritance has now some more fixes (some of them more or less ugly tweaks) and it should work better now (some bugs and deadlocks fixed). Still work-in-progress.

This is my second try into implementing real-time futex support. The patch below encloses a proposal on a way to do real-time futexes that support priority-inheritance, priority-protection, dead-owner recovery (more flexible than Sun's Robust Mutex Extension) and dead lock detection, a sample implementation (sans priority-protection) and a set of test programs along with a very simple thread library to test it.

Note this is NOT a replacement for futexes. rtfutexes cannot do things that normal futexes can do because of the constraints that "real-time-ness" impose. It is intended as a complementary interface.

I have been working on this for a while, and got input from many different people in different companies who are interested in these features (eg: Intel, Cisco, Montavista, OSDL ...) We are also working on a way to blend this into NPTL so it can do real-time.

Version 5

- Ported to 2.5.66 - this fixed the timing problems found; according to George Anzinger, it was a problem in the timer code.

- Fix allocation of rtfutex_q: when we drop the spin lock, we need to claim again, as somebody else might have preempted and modified it. This makes the code much more stable.

- General cleanups (debug, doc) and optimizations (moving not-common code paths out of the way - it makes it kind of uglier though).

- Fix deadlock caused when rtfutex_do_recycle() runs while the same CPU was running with the rtfutex_lock held (I keep stomping into this one) - right now just do a trylock and abort if not possible.

- Fail when trying to lock a futex in non recoverable state.

- Fix different aspects in PI (stop the propagation when a non-PI/PP futex is hit and fall back to deadlock detection). Make it cleaner when we set the priority of a task because of inheritance. Force a boosted task to yield when the boosting task stops waiting (still needs some work).

- Optimize rtfutex_sign_task() a wee bit for the "all clear" case.

- Allow any kind of task to use rtfutex, even if it is not realtime. However, PI/PP requires SCHED_FIFO or SCHED_RR. Use static_prio for non-realtime tasks instead of prio.

- Is slow as hell ... I mean, it is expected to be slower than normal futexes because they are more complex, but currently it sucks. Working on that - mainly removing any usage of kmap_atomic(); the TLB flush is a killer.

- Funny behavior on PI with test-11.c; sometimes the thread TL overpowers lower-prio TP from the very start.

Version 4

- Currently on 2.5.64

- Does not modify original futexes - a new interface is added

Caveats:

- Priority protection not yet implemented.

- Many fixmes here and there that require answers

- Hook for properly acting when the priority of a waiting task is changed not implemented yet.

- The tweak in timer.c is kind of ugly, and needs to be done much more generic; maybe even moved into wake_up_process().

Check out kernel/rtfutex.c for a quick roadmap; Documentation/rtfutex.txt for a longer series of rants and a something more like a design reference. Documentation/rtfutex-api.txt describes how to call the functions (in the test library, test/src/include/rtfutex.h is more up-to-date).

Patch at: http://sost.net/pub/linux/rtfutex-5.patch
Test pkg at: http://sost.net/pub/linux/rtfutex-test-5.tar.gz

Build with:

./configure --with-headers=RTFUTEX-PATCHED-LINUX-TREE/include make

Inaky Perez-Gonzalez -- Not speaking for Intel - opinions are my own [or my fault]