Add priority-ordered wait_queue_t implementation

Will be used by MPCP implementation.

5 files changed, 57 insertions, 2 deletions

diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index a2a694e20be8..b5d8abb4aea5 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -26,8 +26,6 @@ static inline int in_list(struct list_head* list)
                 );
 }
 
-struct task_struct* __waitqueue_remove_first(wait_queue_head_t *wq);
-
 #define NO_CPU                  0xffffffff
 
 void litmus_fork(struct task_struct *tsk);
diff --git a/include/litmus/wait.h b/include/litmus/wait.h
new file mode 100644
index 000000000000..62884f5eb9c8
--- /dev/null
+++ b/include/litmus/wait.h
@@ -0,0 +1,54 @@
+#ifndef _LITMUS_WAIT_H_
+#define _LITMUS_WAIT_H_
+
+struct task_struct* __waitqueue_remove_first(wait_queue_head_t *wq);
+
+/* wrap regular wait_queue_t head */
+struct __prio_wait_queue {
+        wait_queue_t wq;
+
+        /* some priority point */
+        lt_t priority;
+};
+
+typedef struct __prio_wait_queue prio_wait_queue_t;
+
+static inline void init_prio_waitqueue_entry(prio_wait_queue_t *pwq,
+                                             struct task_struct* t,
+                                             lt_t priority)
+{
+        init_waitqueue_entry(&pwq->wq, t);
+        pwq->priority = priority;
+}
+
+static inline unsigned int __add_wait_queue_prio_exclusive(
+        wait_queue_head_t* head,
+        prio_wait_queue_t *new)
+{
+        struct list_head *pos;
+        unsigned int passed = 0;
+
+        new->wq.flags |= WQ_FLAG_EXCLUSIVE;
+
+        /* find a spot where the new entry is less than the next */
+        list_for_each(pos, &head->task_list) {
+                prio_wait_queue_t* queued = list_entry(pos, prio_wait_queue_t,
+                                                       wq.task_list);
+
+                if (unlikely(lt_before(new->priority, queued->priority))) {
+                        /* pos is not less than new, thus insert here */
+                        __list_add(&new->wq.task_list, pos->prev, pos);
+                        goto out;
+                }
+                passed++;
+        }
+
+        /* if we get to this point either the list is empty or every entry
+         * queued element is less than new.
+         * Let's add new to the end. */
+        list_add_tail(&new->wq.task_list, &head->task_list);
+out:
+        return passed;
+}
+
+#endif
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index dfec80e351aa..a0f3ba54ed8f 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -14,6 +14,7 @@
 #include <linux/slab.h>
 
 #include <litmus/litmus.h>
+#include <litmus/wait.h>
 #include <litmus/jobs.h>
 #include <litmus/sched_plugin.h>
 #include <litmus/edf_common.h>
diff --git a/litmus/sched_pfp.c b/litmus/sched_pfp.c
index 45c838f1413e..af60bab563ca 100644
--- a/litmus/sched_pfp.c
+++ b/litmus/sched_pfp.c
@@ -12,6 +12,7 @@
 #include <linux/module.h>
 
 #include <litmus/litmus.h>
+#include <litmus/wait.h>
 #include <litmus/jobs.h>
 #include <litmus/preempt.h>
 #include <litmus/fp_common.h>
diff --git a/litmus/sched_psn_edf.c b/litmus/sched_psn_edf.c
index 8e4a22dd8d6a..178ca0b33b04 100644
--- a/litmus/sched_psn_edf.c
+++ b/litmus/sched_psn_edf.c
@@ -15,6 +15,7 @@
 #include <linux/module.h>
 
 #include <litmus/litmus.h>
+#include <litmus/wait.h>
 #include <litmus/jobs.h>
 #include <litmus/preempt.h>
 #include <litmus/sched_plugin.h>