Add rt_domain_t support

to be merged:
 - arm_release_timer() with no rq locking

4 files changed, 478 insertions, 13 deletions

diff --git a/include/litmus/rt_domain.h b/include/litmus/rt_domain.h
new file mode 100644
index 000000000000..bde1e5a54812
--- /dev/null
+++ b/include/litmus/rt_domain.h
@@ -0,0 +1,158 @@
+/* CLEANUP: Add comments and make it less messy.
+ *
+ */
+
+#ifndef __UNC_RT_DOMAIN_H__
+#define __UNC_RT_DOMAIN_H__
+
+#include <litmus/heap.h>
+
+#define RELEASE_QUEUE_SLOTS 127 /* prime */
+
+struct _rt_domain;
+
+typedef int (*check_resched_needed_t)(struct _rt_domain *rt);
+typedef void (*release_jobs_t)(struct _rt_domain *rt, struct heap* tasks);
+
+struct release_queue {
+        /* each slot maintains a list of release heaps sorted
+         * by release time */
+        struct list_head                slot[RELEASE_QUEUE_SLOTS];
+};
+
+typedef struct _rt_domain {
+        /* runnable rt tasks are in here */
+        spinlock_t                      ready_lock;
+        struct heap                     ready_queue;
+
+        /* real-time tasks waiting for release are in here */
+        spinlock_t                      release_lock;
+        struct release_queue            release_queue;
+
+        /* for moving tasks to the release queue */
+        spinlock_t                      tobe_lock;
+        struct list_head                tobe_released;
+
+        /* how do we check if we need to kick another CPU? */
+        check_resched_needed_t          check_resched;
+
+        /* how do we release jobs? */
+        release_jobs_t                  release_jobs;
+
+        /* how are tasks ordered in the ready queue? */
+        heap_prio_t                     order;
+} rt_domain_t;
+
+struct release_heap {
+        /* list_head for per-time-slot list */
+        struct list_head                list;
+        lt_t                            release_time;
+        /* all tasks to be released at release_time */
+        struct heap                     heap;
+        /* used to trigger the release */
+        struct hrtimer                  timer;
+        /* required for the timer callback */
+        rt_domain_t*                    dom;
+};
+
+
+static inline struct task_struct* __next_ready(rt_domain_t* rt)
+{
+        struct heap_node *hn = heap_peek(rt->order, &rt->ready_queue);
+        if (hn)
+                return heap2task(hn);
+        else
+                return NULL;
+}
+
+void rt_domain_init(rt_domain_t *rt, heap_prio_t order,
+                    check_resched_needed_t check,
+                    release_jobs_t relase);
+
+void __add_ready(rt_domain_t* rt, struct task_struct *new);
+void __merge_ready(rt_domain_t* rt, struct heap *tasks);
+void __add_release(rt_domain_t* rt, struct task_struct *task);
+
+static inline struct task_struct* __take_ready(rt_domain_t* rt)
+{
+        struct heap_node* hn = heap_take(rt->order, &rt->ready_queue);
+        if (hn)
+                return heap2task(hn);
+        else
+                return NULL;
+}
+
+static inline struct task_struct* __peek_ready(rt_domain_t* rt)
+{
+        struct heap_node* hn = heap_peek(rt->order, &rt->ready_queue);
+        if (hn)
+                return heap2task(hn);
+        else
+                return NULL;
+}
+
+static inline int  is_queued(struct task_struct *t)
+{
+        return heap_node_in_heap(tsk_rt(t)->heap_node);
+}
+
+static inline void remove(rt_domain_t* rt, struct task_struct *t)
+{
+        heap_delete(rt->order, &rt->ready_queue, tsk_rt(t)->heap_node);
+}
+
+static inline void add_ready(rt_domain_t* rt, struct task_struct *new)
+{
+        unsigned long flags;
+        /* first we need the write lock for rt_ready_queue */
+        spin_lock_irqsave(&rt->ready_lock, flags);
+        __add_ready(rt, new);
+        spin_unlock_irqrestore(&rt->ready_lock, flags);
+}
+
+static inline void merge_ready(rt_domain_t* rt, struct heap* tasks)
+{
+        unsigned long flags;
+        spin_lock_irqsave(&rt->ready_lock, flags);
+        __merge_ready(rt, tasks);
+        spin_unlock_irqrestore(&rt->ready_lock, flags);
+}
+
+static inline struct task_struct* take_ready(rt_domain_t* rt)
+{
+        unsigned long flags;
+        struct task_struct* ret;
+        /* first we need the write lock for rt_ready_queue */
+        spin_lock_irqsave(&rt->ready_lock, flags);
+        ret = __take_ready(rt);
+        spin_unlock_irqrestore(&rt->ready_lock, flags);
+        return ret;
+}
+
+
+static inline void add_release(rt_domain_t* rt, struct task_struct *task)
+{
+        unsigned long flags;
+        /* first we need the write lock for rt_ready_queue */
+        spin_lock_irqsave(&rt->tobe_lock, flags);
+        __add_release(rt, task);
+        spin_unlock_irqrestore(&rt->tobe_lock, flags);
+}
+
+static inline int __jobs_pending(rt_domain_t* rt)
+{
+        return !heap_empty(&rt->ready_queue);
+}
+
+static inline int jobs_pending(rt_domain_t* rt)
+{
+        unsigned long flags;
+        int ret;
+        /* first we need the write lock for rt_ready_queue */
+        spin_lock_irqsave(&rt->ready_lock, flags);
+        ret = !heap_empty(&rt->ready_queue);
+        spin_unlock_irqrestore(&rt->ready_lock, flags);
+        return ret;
+}
+
+#endif
diff --git a/litmus/Makefile b/litmus/Makefile
index e93f19bb2016..576c1ded20e9 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -5,6 +5,7 @@
 obj-y     = sched_plugin.o litmus.o \
             jobs.o \
             sync.o \
+            rt_domain.o \
             heap.o
 
 obj-$(CONFIG_FEATHER_TRACE) += ft_event.o ftdev.o
diff --git a/litmus/litmus.c b/litmus/litmus.c
index 9254f1621af7..de751a14d77c 100644
--- a/litmus/litmus.c
+++ b/litmus/litmus.c
@@ -19,6 +19,8 @@
 
 #include <litmus/trace.h>
 
+#include <litmus/rt_domain.h>
+
 /* Number of RT tasks that exist in the system */
 atomic_t rt_task_count          = ATOMIC_INIT(0);
 static DEFINE_SPINLOCK(task_transition_lock);
@@ -30,6 +32,7 @@ atomic_t __log_seq_no = ATOMIC_INIT(0);
 atomic_t release_master_cpu = ATOMIC_INIT(NO_CPU);
 
 static struct kmem_cache * heap_node_cache;
+extern struct kmem_cache * release_heap_cache;
 
 struct heap_node* heap_node_alloc(int gfp_flags)
 {
@@ -41,6 +44,9 @@ void heap_node_free(struct heap_node* hn)
         kmem_cache_free(heap_node_cache, hn);
 }
 
+struct release_heap* release_heap_alloc(int gfp_flags);
+void release_heap_free(struct release_heap* rh);
+
 /*
  * sys_set_task_rt_param
  * @pid: Pid of the task which scheduling parameters must be changed
@@ -299,15 +305,16 @@ long litmus_admit_task(struct task_struct* tsk)
             get_exec_cost(tsk) > get_rt_period(tsk)) {
                 TRACE_TASK(tsk, "litmus admit: invalid task parameters "
                            "(%lu, %lu)\n",
-                       get_exec_cost(tsk), get_rt_period(tsk));
-                return -EINVAL;
+                           get_exec_cost(tsk), get_rt_period(tsk));
+                retval = -EINVAL;
+                goto out;
         }
 
-        if (!cpu_online(get_partition(tsk)))
-        {
+        if (!cpu_online(get_partition(tsk))) {
                 TRACE_TASK(tsk, "litmus admit: cpu %d is not online\n",
                            get_partition(tsk));
-                return -EINVAL;
+                retval = -EINVAL;
+                goto out;
         }
 
         INIT_LIST_HEAD(&tsk_rt(tsk)->list);
@@ -316,17 +323,22 @@ long litmus_admit_task(struct task_struct* tsk)
         spin_lock_irqsave(&task_transition_lock, flags);
 
         /* allocate heap node for this task */
-        tsk_rt(tsk)->heap_node    = heap_node_alloc(GFP_ATOMIC);
-        if (!tsk_rt(tsk)->heap_node ||
-            !tsk_rt(tsk)->rel_heap) {
+        tsk_rt(tsk)->heap_node = heap_node_alloc(GFP_ATOMIC);
+        tsk_rt(tsk)->rel_heap = release_heap_alloc(GFP_ATOMIC);
+
+        if (!tsk_rt(tsk)->heap_node || !tsk_rt(tsk)->rel_heap) {
                 printk(KERN_WARNING "litmus: no more heap node memory!?\n");
-                retval = -ENOMEM;
+
                 heap_node_free(tsk_rt(tsk)->heap_node);
-        } else
+                release_heap_free(tsk_rt(tsk)->rel_heap);
+
+                retval = -ENOMEM;
+                goto out_unlock;
+        } else {
                 heap_node_init(&tsk_rt(tsk)->heap_node, tsk);
+        }
 
-        if (!retval)
-                retval = litmus->admit_task(tsk);
+        retval = litmus->admit_task(tsk);
 
         if (!retval) {
                 sched_trace_task_name(tsk);
@@ -334,8 +346,9 @@ long litmus_admit_task(struct task_struct* tsk)
                 atomic_inc(&rt_task_count);
         }
 
+out_unlock:
         spin_unlock_irqrestore(&task_transition_lock, flags);
-
+out:
         return retval;
 }
 
@@ -343,9 +356,13 @@ void litmus_exit_task(struct task_struct* tsk)
 {
         if (is_realtime(tsk)) {
                 sched_trace_task_completion(tsk, 1);
+
                 litmus->task_exit(tsk);
+
                 BUG_ON(heap_node_in_heap(tsk_rt(tsk)->heap_node));
                 heap_node_free(tsk_rt(tsk)->heap_node);
+                release_heap_free(tsk_rt(tsk)->rel_heap);
+
                 atomic_dec(&rt_task_count);
                 reinit_litmus_state(tsk, 1);
         }
@@ -632,6 +649,7 @@ static int __init _init_litmus(void)
         register_sched_plugin(&linux_sched_plugin);
 
         heap_node_cache    = KMEM_CACHE(heap_node, SLAB_PANIC);
+        release_heap_cache = KMEM_CACHE(release_heap, SLAB_PANIC);
 
 #ifdef CONFIG_MAGIC_SYSRQ
         /* offer some debugging help */
@@ -650,6 +668,7 @@ static void _exit_litmus(void)
 {
         exit_litmus_proc();
         kmem_cache_destroy(heap_node_cache);
+        kmem_cache_destroy(release_heap_cache);
 }
 
 module_init(_init_litmus);
diff --git a/litmus/rt_domain.c b/litmus/rt_domain.c
new file mode 100644
index 000000000000..4fa834018efa
--- /dev/null
+++ b/litmus/rt_domain.c
@@ -0,0 +1,287 @@
+/*
+ * litmus/rt_domain.c
+ *
+ * LITMUS real-time infrastructure. This file contains the
+ * functions that manipulate RT domains. RT domains are an abstraction
+ * of a ready queue and a release queue.
+ */
+
+#include <linux/percpu.h>
+#include <linux/sched.h>
+#include <linux/list.h>
+#include <linux/slab.h>
+
+#include <litmus/litmus.h>
+#include <litmus/sched_plugin.h>
+#include <litmus/sched_trace.h>
+
+#include <litmus/rt_domain.h>
+
+#include <litmus/trace.h>
+
+#include <litmus/heap.h>
+
+static int dummy_resched(rt_domain_t *rt)
+{
+        return 0;
+}
+
+static int dummy_order(struct heap_node* a, struct heap_node* b)
+{
+        return 0;
+}
+
+/* default implementation: use default lock */
+static void default_release_jobs(rt_domain_t* rt, struct heap* tasks)
+{
+        merge_ready(rt, tasks);
+}
+
+static unsigned int time2slot(lt_t time)
+{
+        return (unsigned int) time2quanta(time, FLOOR) % RELEASE_QUEUE_SLOTS;
+}
+
+static enum hrtimer_restart on_release_timer(struct hrtimer *timer)
+{
+        unsigned long flags;
+        struct release_heap* rh;
+
+        TRACE("on_release_timer(0x%p) starts.\n", timer);
+
+        TS_RELEASE_START;
+
+        rh = container_of(timer, struct release_heap, timer);
+
+        spin_lock_irqsave(&rh->dom->release_lock, flags);
+        TRACE("CB has the release_lock 0x%p\n", &rh->dom->release_lock);
+        /* remove from release queue */
+        list_del(&rh->list);
+        spin_unlock_irqrestore(&rh->dom->release_lock, flags);
+        TRACE("CB returned release_lock 0x%p\n", &rh->dom->release_lock);
+
+        /* call release callback */
+        rh->dom->release_jobs(rh->dom, &rh->heap);
+        /* WARNING: rh can be referenced from other CPUs from now on. */
+
+        TS_RELEASE_END;
+
+        TRACE("on_release_timer(0x%p) ends.\n", timer);
+
+        return  HRTIMER_NORESTART;
+}
+
+/* allocated in litmus.c */
+struct kmem_cache * release_heap_cache;
+
+struct release_heap* release_heap_alloc(int gfp_flags)
+{
+        struct release_heap* rh;
+        rh= kmem_cache_alloc(release_heap_cache, gfp_flags);
+        if (rh) {
+                /* initialize timer */
+                hrtimer_init(&rh->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
+                rh->timer.function = on_release_timer;
+        }
+        return rh;
+}
+
+void release_heap_free(struct release_heap* rh)
+{
+        /* make sure timer is no longer in use */
+        hrtimer_cancel(&rh->timer);
+        kmem_cache_free(release_heap_cache, rh);
+}
+
+/* Caller must hold release lock.
+ * Will return heap for given time. If no such heap exists prior to
+ * the invocation it will be created.
+ */
+static struct release_heap* get_release_heap(rt_domain_t *rt,
+                                             struct task_struct* t,
+                                             int use_task_heap)
+{
+        struct list_head* pos;
+        struct release_heap* heap = NULL;
+        struct release_heap* rh;
+        lt_t release_time = get_release(t);
+        unsigned int slot = time2slot(release_time);
+
+        /* initialize pos for the case that the list is empty */
+        pos = rt->release_queue.slot[slot].next;
+        list_for_each(pos, &rt->release_queue.slot[slot]) {
+                rh = list_entry(pos, struct release_heap, list);
+                if (release_time == rh->release_time) {
+                        /* perfect match -- this happens on hyperperiod
+                         * boundaries
+                         */
+                        heap = rh;
+                        break;
+                } else if (lt_before(release_time, rh->release_time)) {
+                        /* we need to insert a new node since rh is
+                         * already in the future
+                         */
+                        break;
+                }
+        }
+        if (!heap && use_task_heap) {
+                /* use pre-allocated release heap */
+                rh = tsk_rt(t)->rel_heap;
+
+                rh->dom = rt;
+                rh->release_time = release_time;
+
+                /* add to release queue */
+                list_add(&rh->list, pos->prev);
+                heap = rh;
+        }
+        return heap;
+}
+
+static void reinit_release_heap(struct task_struct* t)
+{
+        struct release_heap* rh;
+
+        /* use pre-allocated release heap */
+        rh = tsk_rt(t)->rel_heap;
+
+        /* Make sure it is safe to use.  The timer callback could still
+         * be executing on another CPU; hrtimer_cancel() will wait
+         * until the timer callback has completed.  However, under no
+         * circumstances should the timer be active (= yet to be
+         * triggered).
+         *
+         * WARNING: If the CPU still holds the release_lock at this point,
+         *          deadlock may occur!
+         */
+        BUG_ON(hrtimer_cancel(&rh->timer));
+
+        /* initialize */
+        heap_init(&rh->heap);
+}
+
+static void arm_release_timer(unsigned long _rt)
+{
+        rt_domain_t *rt = (rt_domain_t*) _rt;
+        unsigned long flags;
+        struct list_head list;
+        struct list_head *pos, *safe;
+        struct task_struct* t;
+        struct release_heap* rh;
+
+        /* We only have to defend against the ISR since norq callbacks
+         * are serialized.
+         */
+        TRACE("arm_release_timer() at %llu\n", litmus_clock());
+        spin_lock_irqsave(&rt->tobe_lock, flags);
+        list_replace_init(&rt->tobe_released, &list);
+        spin_unlock_irqrestore(&rt->tobe_lock, flags);
+
+        list_for_each_safe(pos, safe, &list) {
+                /* pick task of work list */
+                t = list_entry(pos, struct task_struct, rt_param.list);
+                sched_trace_task_release(t);
+                list_del(pos);
+
+                /* put into release heap while holding release_lock */
+                spin_lock_irqsave(&rt->release_lock, flags);
+                TRACE_TASK(t, "I have the release_lock 0x%p\n", &rt->release_lock);
+                rh = get_release_heap(rt, t, 0);
+                if (!rh) {
+                        /* need to use our own, but drop lock first */
+                        spin_unlock(&rt->release_lock);
+                        TRACE_TASK(t, "Dropped release_lock 0x%p\n",
+                                   &rt->release_lock);
+                        reinit_release_heap(t);
+                        TRACE_TASK(t, "release_heap ready\n");
+                        spin_lock(&rt->release_lock);
+                        TRACE_TASK(t, "Re-acquired release_lock 0x%p\n",
+                                   &rt->release_lock);
+                        rh = get_release_heap(rt, t, 1);
+                }
+                heap_insert(rt->order, &rh->heap, tsk_rt(t)->heap_node);
+                TRACE_TASK(t, "arm_release_timer(): added to release heap\n");
+                spin_unlock_irqrestore(&rt->release_lock, flags);
+                TRACE_TASK(t, "Returned the release_lock 0x%p\n", &rt->release_lock);
+
+                /* To avoid arming the timer multiple times, we only let the
+                 * owner do the arming (which is the "first" task to reference
+                 * this release_heap anyway).
+                 */
+                if (rh == tsk_rt(t)->rel_heap) {
+                        TRACE_TASK(t, "arming timer 0x%p\n", &rh->timer);
+                        hrtimer_start(&rh->timer,
+                                      ns_to_ktime(rh->release_time),
+                                      HRTIMER_MODE_ABS);
+                } else
+                        TRACE_TASK(t, "0x%p is not my timer\n", &rh->timer);
+        }
+}
+
+void rt_domain_init(rt_domain_t *rt,
+                    heap_prio_t order,
+                    check_resched_needed_t check,
+                    release_jobs_t release
+                   )
+{
+        int i;
+
+        BUG_ON(!rt);
+        if (!check)
+                check = dummy_resched;
+        if (!release)
+                release = default_release_jobs;
+        if (!order)
+                order = dummy_order;
+
+        heap_init(&rt->ready_queue);
+        INIT_LIST_HEAD(&rt->tobe_released);
+        for (i = 0; i < RELEASE_QUEUE_SLOTS; i++)
+                INIT_LIST_HEAD(&rt->release_queue.slot[i]);
+
+        spin_lock_init(&rt->ready_lock);
+        spin_lock_init(&rt->release_lock);
+        spin_lock_init(&rt->tobe_lock);
+
+        rt->check_resched       = check;
+        rt->release_jobs        = release;
+        rt->order               = order;
+}
+
+/* add_ready - add a real-time task to the rt ready queue. It must be runnable.
+ * @new:       the newly released task
+ */
+void __add_ready(rt_domain_t* rt, struct task_struct *new)
+{
+        TRACE("rt: adding %s/%d (%llu, %llu) rel=%llu to ready queue at %llu\n",
+              new->comm, new->pid, get_exec_cost(new), get_rt_period(new),
+              get_release(new), litmus_clock());
+
+        BUG_ON(heap_node_in_heap(tsk_rt(new)->heap_node));
+
+        heap_insert(rt->order, &rt->ready_queue, tsk_rt(new)->heap_node);
+        rt->check_resched(rt);
+}
+
+/* merge_ready - Add a sorted set of tasks to the rt ready queue. They must be runnable.
+ * @tasks      - the newly released tasks
+ */
+void __merge_ready(rt_domain_t* rt, struct heap* tasks)
+{
+        heap_union(rt->order, &rt->ready_queue, tasks);
+        rt->check_resched(rt);
+}
+
+/* add_release - add a real-time task to the rt release queue.
+ * @task:        the sleeping task
+ */
+void __add_release(rt_domain_t* rt, struct task_struct *task)
+{
+        TRACE_TASK(task, "add_release(), rel=%llu\n", get_release(task));
+        list_add(&tsk_rt(task)->list, &rt->tobe_released);
+        task->rt_param.domain = rt;
+        /* XXX arm_release_timer() used to be activated here
+         *     such that it would be called with the runqueue lock dropped.
+         */
+}
+