Skip to contentSkip to conversation

Priority-based real-time futexes for v2.5.45

PATCH New Inaky Perez-Gonzalez 1 participant 1 message Nov 2, 2002

lore
Share & tools
lore

Inaky Perez-Gonzalez

author
#0 lore raw

PATCH 1/1 Priority-based real-time futexes for v2.5.45

Hi all

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.

[NOTE: I didn't have much time to beat this one, you will probably see some bugs]

How it works is: there is one struct futex_q per futex [before there was one per waiter, don't know if a bug or a feature].

Each futex_q contains a priority array [split from Ingo's code] 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 list 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:

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

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

Remaining caveats:

- Not everybody/task/futex cares about priority based wake-up. 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]. An abstraction of wait queues that would work with both would be the key here.

- Ugly kludge in sched.h to include prioarray.h ...

- vcache callback: as now the futex_q struct is not owned by anybody but 'the futex', the last task in the pqueue (and thus, the last to acquire the lock) will be responsible for freeing. This creates a failure point; when doing the vcache callback, we need to create a new futex_q struct, as the futex is now different, a new futex_q struct has to be allocated - if it fails, we are dead on the water. Kill the process? let it deadlock? let it in the old queue, assume somebody else might wake it up?

- 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 is against 2.5.45.

linux/prioarray.h new file +57 -0
diff -u /dev/null include/linux/prioarray.h:1.1.2.1
@@ -0,0 +1,57 @@
+/*
+ * O(1) priority arrays
+ *
+ * Modified from code (C) 2002 Ingo Molnar <[email protected]> in
+ * sched.c by Iñaky Pérez-González <[email protected]> so
+ * that other parts of the kernel can use the same constructs.
+ */
+
+#ifndef _LINUX_PRIOARRAY_
+#define _LINUX_PRIOARRAY_
+
+        /* This inclusion is kind of recursive ... hmmm */
+
+#include <linux/sched.h>
+
+struct prio_array {
+	int nr_active;
+	unsigned long bitmap[BITMAP_SIZE];
+	struct list_head queue[MAX_PRIO];
+};
+
+typedef struct prio_array prio_array_t;
+
+static inline
+void pa_init (prio_array_t *array)
+{
+        unsigned cnt;
+	array->nr_active = 0;
+        memset (array->bitmap, 0, sizeof (array->bitmap));
+        for (cnt = 0; cnt < MAX_PRIO; cnt++)
+                INIT_LIST_HEAD (&array->queue[cnt]);
+}
+
+/*
+ * Adding/removing a node to/from a priority array:
+ */
+
+static inline
+void pa_dequeue (struct list_head *p, unsigned prio, prio_array_t *array)
+{
+	array->nr_active--;
+	list_del(p);
+	if (list_empty(array->queue + prio))
+		__clear_bit(prio, array->bitmap);
+}
+
+static inline
+void pa_enqueue (struct list_head *p, unsigned prio, prio_array_t *array)
+{
+	list_add_tail(p, array->queue + prio);
+	__set_bit(prio, array->bitmap);
+	array->nr_active++;
+}
+
+
+
+#endif /* #ifndef _LINUX_PRIOARRAY_ */
linux/sched.h renamed from linux/sched.h:1.1.1.4 +3 -1
diff -u include/linux/sched.h:1.1.1.4 include/linux/sched.h:1.1.1.1.2.4
@@ -241,6 +241,9 @@
 #define MAX_RT_PRIO		MAX_USER_RT_PRIO
 
 #define MAX_PRIO		(MAX_RT_PRIO + 40)
+#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
+
+#include <linux/prioarray.h> /* Okay, this is ugly, but needs MAX_PRIO */
  
 /*
  * Some day this will be a full-fledged user tracking system..

@@ -265,7 +268,6 @@
 extern struct user_struct root_user;
 #define INIT_USER (&root_user)
 
-typedef struct prio_array prio_array_t;
 struct backing_dev_info;
 
 struct task_struct {
linux/vcache.h renamed from linux/vcache.h:1.1.1.2 +18 -0
diff -u include/linux/vcache.h:1.1.1.2 include/linux/vcache.h:1.1.1.1.2.3
@@ -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);
futex.c renamed from futex.c:1.1.1.3 +604 -165

962 lines not on this page · raw message

sched.c renamed from sched.c:1.1.1.3 +2 -14
diff -u kernel/sched.c:1.1.1.3 kernel/sched.c:1.1.1.1.2.2
@@ -129,15 +129,8 @@
  * These are the runqueue data structures:
  */
 
-#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
-
 typedef struct runqueue runqueue_t;
 
-struct prio_array {
-	int nr_active;
-	unsigned long bitmap[BITMAP_SIZE];
-	struct list_head queue[MAX_PRIO];
-};
 
 /*
  * This is the main, per-CPU runqueue data structure.

@@ -225,17 +218,12 @@
  */
 static inline void dequeue_task(struct task_struct *p, prio_array_t *array)
 {
-	array->nr_active--;
-	list_del(&p->run_list);
-	if (list_empty(array->queue + p->prio))
-		__clear_bit(p->prio, array->bitmap);
+        pa_dequeue (&p->run_list, p->prio, array);
 }
 
 static inline void enqueue_task(struct task_struct *p, prio_array_t *array)
 {
-	list_add_tail(&p->run_list, array->queue + p->prio);
-	__set_bit(p->prio, array->bitmap);
-	array->nr_active++;
+        pa_enqueue (&p->run_list, p->prio, array);
 	p->array = array;
 }
Signature · 1 line
Inaky Perez-Gonzalez -- Not speaking for Intel - opinions are my own [or my fault]