pfutex-1.2: Priority-based/real-time futexes

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) except futex_q_find() [and callers], that are O(N / 2^FUTEX_HASHBITS).

Changelog since last patch:

v1.2

- Updated documentation

- Enhanced allocation of struct 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.

The slab allocator reduces the pressure on the VM and to avoid the lengthy pa_init() call. There is also a recycle list that will keep a futex_q allocated for ten seconds before returning it to the slab - in the event it is needed again, it is used, or if a new futex_q is required, it will be taken from the recycle list if there is any. Asides, each time we allocate without GFP_ATOMIC, we have to release the lock and then, when reacquired, check that nobody added a futex_q for our futex; that takes time and this alleviates it.

- Added the priority to the struct futex_w, so we do proper house-keeping in the pa_*() functions if the task changes priority when queued. This will require more work.

- Tried to simplify locking a wee bit ... not much though.

Older changelog:

v1.1

- 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.

- NGPT's test program 'test_str03 -b 5 -d 5' using futexes as spinlocks now works, before it deadlocked. I think I was hitting the deadlock in futex_wait(), that was kind of ugly.

v1.0

- 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.

- 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 thinking that I could split the queue implementation from the actual futex_q; when the first waiter comes in, depending on the priority, a priority based or normal one will be used depending on it being real-time or not. If it is a normal one, whenever a new waiter comes in it is transformed to a real-time one if the waiter is real-time ... sounds too complex, though
...

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

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.59 prioarray-1.0

diff -u linux/include/linux/vcache.h:1.1.1.1 linux/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]