P-FP: port P-FP plugin used in B. Brandenburg's

      dissertation (branch bbb-diss) to current
      version of litmus

This is needed for ongoing projects

I took the unchanged code but removed some leftovers
of OMLP which is not implemented

5 files changed, 172 insertions, 2 deletions

diff --git a/include/litmus/fdso.h b/include/litmus/fdso.h
index caf2a1e6918c..2b0537ce7260 100644
--- a/include/litmus/fdso.h
+++ b/include/litmus/fdso.h
@@ -12,7 +12,7 @@
 #include <linux/fs.h>
 #include <linux/slab.h>
 
-#define MAX_OBJECT_DESCRIPTORS 32
+#define MAX_OBJECT_DESCRIPTORS 85
 
 typedef enum  {
         MIN_OBJ_TYPE    = 0,
@@ -20,7 +20,11 @@ typedef enum  {
         FMLP_SEM        = 0,
         SRP_SEM         = 1,
 
-        MAX_OBJ_TYPE    = 1
+        MPCP_SEM        = 2,
+        MPCP_VS_SEM     = 3,
+        DPCP_SEM        = 4,
+
+        MAX_OBJ_TYPE    = 4
 } obj_type_t;
 
 struct inode_obj_id {
diff --git a/include/litmus/fp_common.h b/include/litmus/fp_common.h
new file mode 100644
index 000000000000..dd1f7bf1e347
--- /dev/null
+++ b/include/litmus/fp_common.h
@@ -0,0 +1,105 @@
+/* Fixed-priority scheduler support.
+ */
+
+#ifndef __FP_COMMON_H__
+#define __FP_COMMON_H__
+
+#include <litmus/rt_domain.h>
+
+#include <asm/bitops.h>
+
+
+void fp_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
+                    release_jobs_t release);
+
+int fp_higher_prio(struct task_struct* first,
+                   struct task_struct* second);
+
+int fp_ready_order(struct bheap_node* a, struct bheap_node* b);
+
+#define FP_PRIO_BIT_WORDS (LITMUS_MAX_PRIORITY / BITS_PER_LONG)
+
+#if (LITMUS_MAX_PRIORITY % BITS_PER_LONG)
+#error LITMUS_MAX_PRIORITY must be a multiple of BITS_PER_LONG
+#endif
+
+/* bitmask-inexed priority queue */
+struct fp_prio_queue {
+        unsigned long   bitmask[FP_PRIO_BIT_WORDS];
+        struct bheap    queue[LITMUS_MAX_PRIORITY];
+};
+
+void fp_prio_queue_init(struct fp_prio_queue* q);
+
+static inline void fpq_set(struct fp_prio_queue* q, unsigned int index)
+{
+        unsigned long *word = q->bitmask + (index / BITS_PER_LONG);
+        __set_bit(index % BITS_PER_LONG, word);
+}
+
+static inline void fpq_clear(struct fp_prio_queue* q, unsigned int index)
+{
+        unsigned long *word = q->bitmask + (index / BITS_PER_LONG);
+        __clear_bit(index % BITS_PER_LONG, word);
+}
+
+static inline unsigned int fpq_find(struct fp_prio_queue* q)
+{
+        int i;
+
+        /* loop optimizer should unroll this */
+        for (i = 0; i < FP_PRIO_BIT_WORDS; i++)
+                if (q->bitmask[i])
+                        return __ffs(q->bitmask[i]) + i * BITS_PER_LONG;
+
+        return LITMUS_MAX_PRIORITY; /* nothing found */
+}
+
+static inline void fp_prio_add(struct fp_prio_queue* q, struct task_struct* t, unsigned int index)
+{
+
+        BUG_ON(bheap_node_in_heap(tsk_rt(t)->heap_node));
+
+        fpq_set(q, index);
+        bheap_insert(fp_ready_order, &q->queue[index], tsk_rt(t)->heap_node);
+}
+
+static inline void fp_prio_remove(struct fp_prio_queue* q, struct task_struct* t, unsigned int index)
+{
+        BUG_ON(!is_queued(t));
+
+        bheap_delete(fp_ready_order, &q->queue[index], tsk_rt(t)->heap_node);
+        if (likely(bheap_empty(&q->queue[index])))
+                fpq_clear(q, index);
+}
+
+static inline struct task_struct* fp_prio_peek(struct fp_prio_queue* q)
+{
+        unsigned int idx = fpq_find(q);
+        struct bheap_node* hn;
+
+        if (idx < LITMUS_MAX_PRIORITY) {
+                hn = bheap_peek(fp_ready_order, &q->queue[idx]);
+                return bheap2task(hn);
+        } else
+                return NULL;
+}
+
+static inline struct task_struct* fp_prio_take(struct fp_prio_queue* q)
+{
+        unsigned int idx = fpq_find(q);
+        struct bheap_node* hn;
+
+        if (idx < LITMUS_MAX_PRIORITY) {
+                hn = bheap_take(fp_ready_order, &q->queue[idx]);
+                if (likely(bheap_empty(&q->queue[idx])))
+                        fpq_clear(q, idx);
+                return bheap2task(hn);
+        } else
+                return NULL;
+}
+
+int fp_preemption_needed(struct fp_prio_queue*  q, struct task_struct *t);
+
+
+#endif
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index 160119abfe30..aa56eeef7e7d 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -52,6 +52,7 @@ void litmus_exit_task(struct task_struct *tsk);
 #define get_rt_period(t)        (tsk_rt(t)->task_params.period)
 #define get_rt_phase(t)         (tsk_rt(t)->task_params.phase)
 #define get_partition(t)        (tsk_rt(t)->task_params.cpu)
+#define get_priority(t)         (tsk_rt(t)->task_params.priority)
 #define get_deadline(t)         (tsk_rt(t)->job_params.deadline)
 #define get_release(t)          (tsk_rt(t)->job_params.release)
 #define get_class(t)            (tsk_rt(t)->task_params.cls)
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index d6d799174160..1ce96af51287 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -33,11 +33,14 @@ typedef enum {
         PRECISE_ENFORCEMENT  /* budgets are enforced with hrtimers */
 } budget_policy_t;
 
+#define LITMUS_MAX_PRIORITY 512
+
 struct rt_task {
         lt_t            exec_cost;
         lt_t            period;
         lt_t            phase;
         unsigned int    cpu;
+        unsigned int    priority;
         task_class_t    cls;
         budget_policy_t budget_policy; /* ignored by pfair */
 };
diff --git a/include/litmus/wait.h b/include/litmus/wait.h
new file mode 100644
index 000000000000..ce1347c355f8
--- /dev/null
+++ b/include/litmus/wait.h
@@ -0,0 +1,57 @@
+#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;
+        /* break ties in priority by lower tie_breaker */
+        unsigned int tie_breaker;
+};
+
+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;
+        pwq->tie_breaker = 0;
+}
+
+static inline void init_prio_waitqueue_entry_tie(prio_wait_queue_t *pwq,
+                                                 struct task_struct* t,
+                                                 lt_t priority,
+                                                 unsigned int tie_breaker)
+{
+        init_waitqueue_entry(&pwq->wq, t);
+        pwq->priority    = priority;
+        pwq->tie_breaker = tie_breaker;
+}
+
+unsigned int __add_wait_queue_prio_exclusive(
+        wait_queue_head_t* head,
+        prio_wait_queue_t *new);
+
+static inline unsigned int add_wait_queue_prio_exclusive(
+        wait_queue_head_t* head,
+        prio_wait_queue_t *new)
+{
+        unsigned long flags;
+        unsigned int passed;
+
+        spin_lock_irqsave(&head->lock, flags);
+        passed = __add_wait_queue_prio_exclusive(head, new);
+
+        spin_unlock_irqrestore(&head->lock, flags);
+
+        return passed;
+}
+
+
+#endif