Priority-based real-time futexes v1.1 for 2.5.52

This is the priority-based futex support; tasks/fds that are sleeping on a futex get woken up by priority order. This is useful for real-time locking, with most benefits being for the NGPT and NPTL thread libraries. Checkout the CAVEATS section for a PRIORITY INVERSION problem that needs sollution.

How it works is: there is one struct futex_q per futex; each futex_q contains a priority array [it requires the prioarray-1.0 patch] where the waiters are attached [the waiter, struct futex_w, describes the task and fd if any). The last waiter takes care of freeing the futex_q.

When a wake up is selected, the prioarray is walked in priority order to wake up as many waiters as specified. All list operations are O(1). The only one operation that is O(N) is sys_poll() [on the number of fds being waited for, as always].

Changelog since last patch:

- vcache callback: having to create a new futex_q struct in the callback creates a failure point if there is no more GFP_ATOMIC space; the corresponding waiter would be deattached from any futex_q and thus, lay there sleeping for ever.

The only sollution I can think of is wake it up, so it goes up to user space, sees the count is still -1 [or whatever] and if required, go back down to the kernel and sleep there.

- Added futex_wait_utime() split by Luca Barbieri.

- Define futex_w_is_queued() so we don't test manually q->NULL [in case it changes IANF].

- Some silly pretty print and cosmetic changes.

Older changelog:

- Updated docs here and there, add explanation of the model and a short roadmap.

- Don't depend so much in GFP_ATOMIC - this forces us to lookup with __get_futex_q() twice when there is no futex_q, and that is ugly. Need to improve it (CR caveats).

- Fixed a bunch of embarrasing error paths [let's see how many did I introduce]

Remaining CAVEATS:

- Priority inversion problem: in the current futex model, when we wake up, in userspace, we set the futex count to 1 and then go down to the kernel to ask it to wake up so many waiters. Between setting the futex count to 1 and the kernel waking up the highest priority waiter(s), some lower priority process could acquire the futex and cause a priority inversion.

To fix this, I can only thing of improving the current FUTEX_PASS mechanism to work inside the kernel, so that the futex does not need to be set to 1 when there are waiters.

- Not everybody/task/futex cares about priority based wake-up, and they consume some space (140 * 2 * 4 bytes each futex_q for the prioarray index plus associated stuff) [more than 1K in total].

I am planning that I could have the first locker specify how it should behave, and then, dynamically select either a normal queue or a pqueue, with that selection in effect for the lifetime of the futex in kernel space [ie: while it is locked].

- I took special care not to miss anything allocated when it should, but I could have screwed up ...

- Optimize lookup and possible creation of a new futex_q

- Use an slab allocator for the futex_q. On applications with a low contention rate, we don't want to be allocating and deallocating an struct futex_q every time just because the futex is locked by nobody, one or two people in a random distribution. If the slab is there, the futex_q will remain allocated, so acquisition will be faster and fragmentation lower. When memory is tight, and it is not used, it will be released.

I used a combination of code that I borrowed from NGPT, Rusty's user space sample library + some of my own to test it. It is basically a shared area and futex_down and futex_up programs that can be called from the shell. I gave it a few hard times and it resisted pretty well - however, I probably missed many cases. Find it at:

http://sost.net/pub/linux/pfutex-test.tar.gz

Enjoy

This patch requires the following patches and kernel version:

linux-2.5.52 prioarray-1.0

diff -u include/linux/vcache.h:1.1.1.1 include/linux/vcache.h:1.1.1.1.4.1
@@ -17,8 +17,26 @@
 		unsigned long address,
 		struct mm_struct *mm,
 		void (*callback)(struct vcache_s *data, struct page *new_page));
+static inline
+void attach_vcache (vcache_t *vcache,
+		unsigned long address,
+		struct mm_struct *mm,
+                    void (*callback)(struct vcache_s *data, struct page *new_page))
+{
+  spin_lock (&vcache_lock);
+  __attach_vcache (vcache, address, mm, callback);
+  spin_unlock (&vcache_lock);
+}
 
 extern void __detach_vcache(vcache_t *vcache);
+
+static inline
+void detach_vcache (vcache_t *vcache)
+{
+  spin_lock (&vcache_lock);
+  __detach_vcache (vcache);
+  spin_unlock (&vcache_lock);
+}
 
 extern void invalidate_vcache(unsigned long address, struct mm_struct *mm,
 				struct page *new_page);

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