Now with fine grained locking

6 files changed, 311 insertions, 250 deletions

diff --git a/include/litmus/rt_domain.h b/include/litmus/rt_domain.h
index b5cf95ffd488..0e4e75cd1e67 100644
--- a/include/litmus/rt_domain.h
+++ b/include/litmus/rt_domain.h
@@ -80,14 +80,13 @@ void rt_domain_init(rt_domain_t *rt, bheap_prio_t order,
                     release_jobs_t release);
 
 void pd_domain_init(domain_t *dom,
+                    rt_domain_t *rt,
                     bheap_prio_t order,
                     check_resched_needed_t check,
                     release_jobs_t release,
                     preempt_needed_t preempt_needed,
                     task_prio_t priority);
 
-void pd_domain_free(domain_t *dom);
-
 void __add_ready(rt_domain_t* rt, struct task_struct *new);
 void __merge_ready(rt_domain_t* rt, struct bheap *tasks);
 void __add_release(rt_domain_t* rt, struct task_struct *task);
diff --git a/include/litmus/sched_mc.h b/include/litmus/sched_mc.h
index 32ef68150c81..d29796298701 100644
--- a/include/litmus/sched_mc.h
+++ b/include/litmus/sched_mc.h
@@ -9,8 +9,7 @@ enum crit_level {
         CRIT_LEVEL_A = 0,
         CRIT_LEVEL_B = 1,
         CRIT_LEVEL_C = 2,
-        CRIT_LEVEL_D = 3,
-        NUM_CRIT_LEVELS = 4,
+        NUM_CRIT_LEVELS = 3,
 };
 
 struct mc_task {
diff --git a/litmus/litmus.c b/litmus/litmus.c
index 7db9fdadc7db..437cdfa215ce 100644
--- a/litmus/litmus.c
+++ b/litmus/litmus.c
@@ -315,7 +315,7 @@ asmlinkage long sys_set_rt_task_mc_param(pid_t pid, struct mc_task __user *param
         }
 
         /* check parameters passed in are valid */
-        if (mc.crit < CRIT_LEVEL_A || mc.crit > CRIT_LEVEL_D)
+        if (mc.crit < CRIT_LEVEL_A || mc.crit >= NUM_CRIT_LEVELS)
         {
                 printk(KERN_WARNING "litmus: real-time task %d rejected because "
                         "of invalid criticality level\n", pid);
@@ -562,10 +562,10 @@ void exit_litmus(struct task_struct *dead_tsk)
         }
 
 #ifdef CONFIG_PLUGIN_MC
-        /* The MC-setup syscall might succeed and allocate mc_data, but the
-           task may not exit in real-time mode, and that memory will leak.
-           Check and free it here.
-        */
+        /* The MC-setup syscall might succeed and allocate mc_data, but the
+         * task may not exit in real-time mode, and that memory will leak.
+         *  Check and free it here.
+         */
         if (tsk_rt(dead_tsk)->mc_data)
                 kfree(tsk_rt(dead_tsk)->mc_data);
 #endif
diff --git a/litmus/rt_domain.c b/litmus/rt_domain.c
index 65c6e5c02f1e..3e419d7c9ae7 100644
--- a/litmus/rt_domain.c
+++ b/litmus/rt_domain.c
@@ -20,7 +20,7 @@
 
 
 /* Uncomment when debugging timer races... */
-#if 1
+#if 0
 #define VTRACE_TASK TRACE_TASK
 #define VTRACE TRACE
 #else
@@ -371,8 +371,12 @@ static void pd_requeue(domain_t *dom, struct task_struct *task)
 
         if (is_released(task, litmus_clock())) {
                 __add_ready(domain, task);
+                TRACE("rt: adding %s/%d (%llu, %llu) rel=%llu to ready queue at %llu\n",
+                      task->comm, task->pid, get_exec_cost(task), get_rt_period(task),
+                      get_release(task), litmus_clock());
         } else {
                 /* task has to wait for next release */
+                TRACE_TASK(task, "add release(), rel=%llu\n", get_release(task));
                 add_release(domain, task);
         }
 }
@@ -398,22 +402,16 @@ static struct task_struct* pd_peek_ready(domain_t *dom)
 /* pd_domain_init - create a generic domain wrapper for an rt_domain
  */
 void pd_domain_init(domain_t *dom,
+                    rt_domain_t *domain,
                     bheap_prio_t order,
                     check_resched_needed_t check,
                     release_jobs_t release,
                     preempt_needed_t preempt_needed,
                     task_prio_t priority)
 {
-        rt_domain_t *domain = kmalloc(sizeof(rt_domain_t), GFP_ATOMIC);
-
         rt_domain_init(domain, order, check, release);
         domain_init(dom, &domain->ready_lock,
                     pd_requeue, pd_peek_ready, pd_take_ready,
                     preempt_needed, priority);
         dom->data = domain;
 }
-
-void pd_domain_free(domain_t *dom)
-{
-        kfree(dom->data);
-}
diff --git a/litmus/sched_mc.c b/litmus/sched_mc.c
index 0f6c052aad20..1f2b13c6a219 100644
--- a/litmus/sched_mc.c
+++ b/litmus/sched_mc.c
@@ -16,6 +16,7 @@
 #include <linux/hrtimer.h>
 #include <linux/slab.h>
 #include <linux/module.h>
+#include <linux/poison.h>
 
 #include <litmus/litmus.h>
 #include <litmus/jobs.h>
@@ -27,30 +28,50 @@
 
 #include <litmus/sched_mc.h>
 
-/* Per CPU per criticality level state */
+/**
+ * crit_entry_t - State of a CPU within each criticality level system.
+ * @level       Criticality level of this entry
+ * @linked      Logically running task, ghost or regular
+ * @domain      Domain from which to draw tasks
+ * @usable      False if a higher criticality task is running
+ * @timer       For ghost task budget enforcement
+ * @node        Used to sort crit_entries by preemptability in global domains
+ */
 typedef struct {
         enum crit_level         level;
-        struct task_struct*     linked; /* Logically running task */
+        struct task_struct*     linked;
         domain_t*               domain;
+        int                     usable;
+        struct hrtimer          timer;
+        struct bheap_node*      node;
+} crit_entry_t;
 
-        struct hrtimer          timer;  /* For ghost task budget enforcement */
-        struct bheap_node*      node;   /* For membership in global domains  */
-} crit_cpu_entry_t;
-
-/* Per CPU state */
+/**
+ * cpu_entry_t - State of a CPU for the entire MC system
+ * @cpu           CPU id
+ * @scheduled     Task that is physically running
+ * @linked        Task that should be running / is logically running
+ * @lock          For serialization
+ * @crit_entries  Array of CPU state per criticality level
+ */
 typedef struct {
         int                     cpu;
-        struct task_struct*     scheduled; /* Task that is physically running */
-        struct task_struct*     linked;    /* Task that is logically running  */
-
-        crit_cpu_entry_t        crit_entries[NUM_CRIT_LEVELS];
+        struct task_struct*     scheduled;
+        struct task_struct*     linked;
+        raw_spinlock_t          lock;
+        crit_entry_t            crit_entries[NUM_CRIT_LEVELS];
 } cpu_entry_t;
 
-/* Wrapper necessary until cpu linking code is moved into header file */
-typedef struct domain_data {
-        domain_t                domain;
-        struct bheap*           heap;       /* For global domains      */
-        crit_cpu_entry_t*       crit_entry; /* For partitioned domains */
+/**
+ * domain_data_t - Wrap domains with related CPU state
+ * @domain      A domain for a criticality level
+ * @heap        The preemptable heap of crit entries (for global domains)
+ * @crit_entry  The crit entry for this domain (for partitioned domains)
+ */
+typedef struct {
+        domain_t        domain;
+        struct bheap*   heap;
+        crit_entry_t*   crit_entry;
 } domain_data_t;
 
 static cpu_entry_t* cpus[NR_CPUS];
@@ -59,9 +80,14 @@ static raw_spinlock_t global_lock;
 #define domain_data(dom)  (container_of(dom, domain_data_t, domain))
 #define is_global(dom)    (domain_data(dom)->heap)
 #define is_global_task(t) (is_global(get_task_domain(t)))
+#define can_requeue(t)                                  \
+        (!is_global_task(t) || (t)->rt_param.scheduled_on == NO_CPU)
+#define entry_level(e) \
+        (((e)->linked) ? tsk_mc_crit((e)->linked) : NUM_CRIT_LEVELS - 1)
 #define crit_cpu(ce) \
-        (container_of((void*)(ce - ce->level), cpu_entry_t, crit_entries))
+        (container_of((void*)((ce) - (ce)->level), cpu_entry_t, crit_entries))
 
+/* useful debug macros */
 #define TS "(%s/%d:%d:%s)"
 #define TA(t) (t) ? (is_ghost(t)) ? "ghost" : t->comm : "NULL", (t) ? t->pid : 1, \
               (t) ? t->rt_param.job_params.job_no : 1,                  \
@@ -71,7 +97,8 @@ static raw_spinlock_t global_lock;
               e->cpu, TA(e->linked), ##args)
 #define TRACE_CRIT_ENTRY(ce, fmt, args...)                      \
         TRACE("%s P%d, linked=" TS " " fmt "\n",                \
-              ce->domain->name, crit_cpu(ce)->cpu, TA(ce->linked), ##args)
+              (ce)->domain->name, crit_cpu(ce)->cpu, TA((ce)->linked), ##args)
+#undef  TRACE_TASK
 #define TRACE_TASK(t, fmt, args...)                             \
         TRACE(TS " " fmt "\n", TA(t), ##args)
 
@@ -81,7 +108,7 @@ static raw_spinlock_t global_lock;
 static int cpu_lower_prio(struct bheap_node *a, struct bheap_node *b)
 {
         domain_t *domain;
-        crit_cpu_entry_t *first, *second;
+        crit_entry_t *first, *second;
         struct task_struct *first_link, *second_link;
 
         first  = a->value;
@@ -89,7 +116,9 @@ static int cpu_lower_prio(struct bheap_node *a, struct bheap_node *b)
         first_link  = first->linked;
         second_link = second->linked;
 
-        if (!first_link || !second_link) {
+        if (!first->usable || !second->usable) {
+                return second->usable && first->usable;
+        } else if (!first_link || !second_link) {
                 return second_link && !first_link;
         } else {
                 domain = get_task_domain(first_link);
@@ -99,10 +128,26 @@ static int cpu_lower_prio(struct bheap_node *a, struct bheap_node *b)
 }
 
 /*
+ * Return true if the domain has a higher priority ready task. The curr
+ * task must belong to the domain.
+ */
+static noinline int mc_preempt_needed(domain_t *dom, struct task_struct* curr)
+{
+        struct task_struct *next = dom->peek_ready(dom);
+
+        if (!next || !curr) {
+                return next && !curr;
+        } else {
+                BUG_ON(tsk_mc_crit(next) != tsk_mc_crit(curr));
+                return get_task_domain(next)->higher_prio(next, curr);
+        }
+}
+
+/*
  * Return next CPU which should preempted or NULL if the domain has no
  * preemptable CPUs.
  */
-static inline crit_cpu_entry_t* lowest_prio_cpu(domain_t *dom)
+static inline crit_entry_t* lowest_prio_cpu(domain_t *dom)
 {
         struct bheap *heap = domain_data(dom)->heap;
         struct bheap_node* hn;
@@ -110,8 +155,9 @@ static inline crit_cpu_entry_t* lowest_prio_cpu(domain_t *dom)
         return (hn) ? hn->value : NULL;
 }
 
-/*
- * Time accounting for ghost tasks. Called during ticks and linking.
+/**
+ * update_ghost_time() - Time accounting for ghost tasks.
+ * Must be called before a decision is made involving the task's budget.
  */
 static void update_ghost_time(struct task_struct *p)
 {
@@ -135,16 +181,18 @@ static void update_ghost_time(struct task_struct *p)
         }
 }
 
-/*
- * Logically set running task for a domain on a CPU.
+/**
+ * link_task_to_crit() - Logically run a task at a criticality level.
+ * Caller must hold @ce's domain's lock.
  */
-static void link_task_to_crit(crit_cpu_entry_t *ce,
+static void link_task_to_crit(crit_entry_t *ce,
                               struct task_struct *task)
 {
         lt_t when_to_fire;
         struct bheap *heap;
 
-        TRACE_TASK(task, "Linking to P%d", crit_cpu(ce)->cpu);
+        TRACE_CRIT_ENTRY(ce, "Linking " TS, TA(task));
+        BUG_ON(!ce->usable && task);
         BUG_ON(task && tsk_rt(task)->linked_on != NO_CPU);
         BUG_ON(task && is_global(ce->domain) &&
                !bheap_node_in_heap(ce->node));
@@ -180,7 +228,7 @@ static void link_task_to_crit(crit_cpu_entry_t *ce,
         }
 
         /* Update global heap node position */
-        if (is_global(ce->domain) && bheap_node_in_heap(ce->node)) {
+        if (is_global(ce->domain)) {
                 heap = domain_data(ce->domain)->heap;
                 bheap_delete(cpu_lower_prio, heap, ce->node);
                 bheap_insert(cpu_lower_prio, heap, ce->node);
@@ -189,18 +237,19 @@ static void link_task_to_crit(crit_cpu_entry_t *ce,
 
 static void check_for_preempt(domain_t*);
 
-/*
- * Catch all function for when a task enters the system after a suspension
- * or a release. Requeues the task and causes a preemption, if necessary.
+/**
+ * job_arrival() - Called when a task re-enters the system.
+ * Caller must hold no locks.
  */
-static void job_arrival(struct task_struct* task)
+static void job_arrival(struct task_struct *task)
 {
         domain_t *dom = get_task_domain(task);
 
         TRACE_TASK(task, "Job arriving");
         BUG_ON(!task);
 
-        if (!is_global(dom) || tsk_rt(task)->scheduled_on == NO_CPU) {
+        raw_spin_lock(dom->lock);
+        if (can_requeue(task)) {
                 dom->requeue(dom, task);
                 check_for_preempt(dom);
         } else {
@@ -212,86 +261,51 @@ static void job_arrival(struct task_struct* task)
                  */
                 TRACE_TASK(task, "Delayed arrival of scheduled task");
         }
+        raw_spin_unlock(dom->lock);
 }
 
-/*
- * Logically run a task on a CPU. The task must first have been linked
- * to one of the criticalities running on this CPU.
+/**
+ * link_task_to_cpu() - Logically run a task on a CPU.
+ * The task must first have been linked to one of the CPU's crit_entries.
+ * Caller must hold the entry lock.
  */
 static void link_task_to_cpu(cpu_entry_t *entry, struct task_struct *task)
 {
-        int i, in_heap;
-        crit_cpu_entry_t *ce;
-        struct bheap *heap;
-        struct task_struct *tmp;
-        enum crit_level last, next;
-
-        next = (task) ? tsk_mc_crit(task) : NUM_CRIT_LEVELS - 1;
-        last = (entry->linked) ? tsk_mc_crit(entry->linked) :
-                NUM_CRIT_LEVELS - 1;
-
+        int i;
         TRACE_TASK(task, "Linking to P%d", entry->cpu);
         BUG_ON(task && tsk_rt(task)->linked_on != entry->cpu);
         BUG_ON(task && is_ghost(task));
-        BUG_ON(entry->linked && task && tsk_mc_crit(entry->linked) < next);
 
-        /* Actually link task */
-        if (task && !is_ghost(task)) {
+        i = entry_level(entry);
+        if (task){
                 set_rt_flags(task, RT_F_RUNNING);
-                entry->linked = task;
-        } else {
-                entry->linked = NULL;
         }
-
-        /* Update CPU states */
-        for (i  = ((next < last) ? next : last);
-             i <= ((next > last) ? next : last); i++) {
-                ce = &entry->crit_entries[i];
-
-                /* Put CPU only in heaps which can preempt the linked task */
-                if (is_global(ce->domain)) {
-                        heap = domain_data(ce->domain)->heap;
-                        in_heap = bheap_node_in_heap(ce->node);
-                        if (ce->level > next && in_heap) {
-                                bheap_delete(cpu_lower_prio, heap, ce->node);
-                        } else if ((ce->level < next || !task) && !in_heap) {
-                                bheap_insert(cpu_lower_prio, heap, ce->node);
-                        }
-                }
-
-                /* Remove and requeue lower priority tasks on this CPU */
-                if (ce->linked && ce->level > next) {
-                        TRACE_TASK(ce->linked, "Removed by higher priority");
-                        tmp = ce->linked;
-                        link_task_to_crit(ce, NULL);
-                        if (is_global(ce->domain)) {
-                                /* Need to check for a preemption.
-                                 * We know this CPU is no longer in the heap
-                                 * so it cannot get re-preempted here.
-                                 */
-                                job_arrival(tmp);
-                        } else {
-                                ce->domain->requeue(ce->domain, tmp);
-                        }
-                }
+        entry->linked = task;
+        for (; i < entry_level(entry) + 1; i++) {
+                TRACE_CRIT_ENTRY(&entry->crit_entries[i], "now usable");
+                entry->crit_entries[i].usable = 1;
         }
 }
 
-/*
- * Preempt logically running task in a domain. If the preempting task should be
- * running on the domain's CPU, also links the task to the CPU and causes
- * a physical preemption.
+/**
+ * preempt() - Preempt a logically running task with a higher priority one.
+ * @dom Domain from which to draw higher priority task
+ * @ce  CPU criticality level to preempt
+ *
+ * Caller must hold the lock for @dom and @ce's CPU lock. Returns 1 if
+ * a physically preemption occurred.
  */
-static void preempt(domain_t *dom, crit_cpu_entry_t *ce)
+static int preempt(domain_t *dom, crit_entry_t *ce)
 {
+        int rv = 0;
         struct task_struct *task = dom->take_ready(dom);
         cpu_entry_t *entry = crit_cpu(ce);
 
-        TRACE_CRIT_ENTRY(ce, "Preempted by " TS, TA(task));
         BUG_ON(!task);
+        TRACE_CRIT_ENTRY(ce, "Preempted by " TS, TA(task));
 
         /* Per-domain preemption */
-        if (ce->linked) {
+        if (ce->linked && can_requeue(ce->linked)) {
                 dom->requeue(dom, ce->linked);
         }
         link_task_to_crit(ce, task);
@@ -300,65 +314,119 @@ static void preempt(domain_t *dom, crit_cpu_entry_t *ce)
         if (!is_ghost(task)) {
                 link_task_to_cpu(entry, task);
                 preempt_if_preemptable(entry->scheduled, entry->cpu);
+                rv = 1;
         }
+        return rv;
 }
 
-/*
- * Causes a logical preemption if the domain has a higher-priority ready task.
+/**
+ * update_crit_levels() - Update criticality entries for the new cpu state.
+ * This should be called after a new task has been linked to @entry.
+ * Assumes the caller holds @entry->lock, but this method will release it.
+ */
+static void update_crit_levels(cpu_entry_t *entry)
+{
+        int i;
+        crit_entry_t *ce;
+        struct task_struct *tasks[NUM_CRIT_LEVELS];
+        enum crit_level level = entry_level(entry);
+
+        /* Remove tasks from entries */
+        for (i = level + 1; i < NUM_CRIT_LEVELS; i++) {
+                ce = &entry->crit_entries[i];
+                tasks[i] = ce->linked;
+                TRACE_CRIT_ENTRY(ce, "not usable");
+                ce->usable = 0;
+                if (ce->linked) {
+                        link_task_to_crit(ce, NULL);
+                }
+        }
+
+        raw_spin_unlock(&entry->lock);
+
+        /* Put tasks back into system */
+        for (i = level + 1; i < NUM_CRIT_LEVELS; i++) {
+                ce = &entry->crit_entries[i];
+                if (tasks[i]) {
+                        job_arrival(tasks[i]);
+                }
+        }
+}
+
+/**
+ * check_for_preempt() - Causes a preemption if higher-priority tasks are ready.
+ * Caller must hold domain lock.
+ * Makes gigantic nasty assumption that there is 1 global criticality level,
+ * and it is the last one in each list, so it doesn't call update_crit..
  */
 static void check_for_preempt(domain_t *dom)
 {
-        int lower_prio;
+        int preempted = 1;
         cpu_entry_t *entry;
-        crit_cpu_entry_t *ce;
+        crit_entry_t *ce;
 
         if (is_global(dom)) {
-                /* If a higher priority task is running on a CPU,
-                 * it will not be present in the domain heap.
-                 */
-                for (ce = lowest_prio_cpu(dom);
-                     ce && dom->preempt_needed(dom, ce->linked);
-                     ce = lowest_prio_cpu(dom)) {
-
-                        preempt(dom, ce);
+                /* Loop until we find a non-preemptable CPU */
+                while ((ce = lowest_prio_cpu(dom)) && preempted) {
+                        entry = crit_cpu(ce);
+                        preempted = 0;
+                        raw_spin_lock(&entry->lock);
+                        if (ce->usable && dom->preempt_needed(dom, ce->linked)){
+                                preempted = 1;
+                                preempt(dom, ce);
+                        }
+                        raw_spin_unlock(&entry->lock);
                 }
         } else /* Partitioned */ {
                 ce = domain_data(dom)->crit_entry;
                 entry = crit_cpu(ce);
-                /* A higher priority task might be running, in which case
-                 * this level cannot link any task.
-                 */
-                lower_prio = entry->linked &&
-                        tsk_mc_crit(entry->linked) < ce->level;
-                if (!lower_prio && dom->preempt_needed(dom, ce->linked)) {
+
+                raw_spin_lock(&entry->lock);
+                if (ce->usable && dom->preempt_needed(dom, ce->linked)) {
                         preempt(dom, ce);
+                        update_crit_levels(entry);
+                } else {
+                        raw_spin_unlock(&entry->lock);
                 }
         }
 }
 
-/*
- * Remove a running task from all structures.
+/**
+ * remove_from_all() - Logically remove a task from all structures.
+ * Caller must hold no locks.
  */
 static void remove_from_all(struct task_struct* task)
 {
-        int cpu, level;
+        int update = 0;
         cpu_entry_t *entry;
-        crit_cpu_entry_t *ce;
+        crit_entry_t *ce;
+        domain_t *dom = get_task_domain(task);
 
         TRACE_TASK(task, "Removing from everything");
         BUG_ON(!task);
 
-        cpu = task->rt_param.linked_on;
-        level = tsk_mc_crit(task);
-        if (cpu != NO_CPU) {
-                /* Unlink */
-                entry = cpus[cpu];
-                ce = &entry->crit_entries[level];
-                link_task_to_crit(ce, NULL);
-                if (!is_ghost(task)) {
-                        link_task_to_cpu(entry, NULL);
+        raw_spin_lock(dom->lock);
+        if (task->rt_param.linked_on != NO_CPU) {
+                entry = cpus[task->rt_param.linked_on];
+
+                raw_spin_lock(&entry->lock);
+                /* Unlink if task is still linked post lock */
+                ce = &entry->crit_entries[tsk_mc_crit(task)];
+                if (task->rt_param.linked_on != NO_CPU) {
+                        BUG_ON(entry->linked != task);
+                        link_task_to_crit(ce, NULL);
+                        if (!is_ghost(task)) {
+                                update = 1;
+                                link_task_to_cpu(entry, NULL);
+                        }
                 }
                 BUG_ON(is_queued(task));
+
+                if (update) {
+                        update_crit_levels(entry);
+                } else {
+                        raw_spin_unlock(&entry->lock);
+                }
         } else if (is_queued(task)) {
                 /* This is an interesting situation: t is scheduled,
                  * but was just recently unlinked. It cannot be
@@ -367,14 +435,15 @@ static void remove_from_all(struct task_struct* task)
                  * queue. We must remove it from the list in this
                  * case.
                  */
-                TRACE_TASK(task, "Weird is_queued situation happened");
                 remove((rt_domain_t*)get_task_domain(task)->data, task);
         }
+        raw_spin_unlock(dom->lock);
 }
 
-/*
- * Prepares a task for its next period and causes a preemption, if necessary.
- * Converts tasks which completed their execution early into ghost tasks.
+/**
+ * job_completion() - Update task state and re-enter it into the system.
+ * Converts tasks which have completed their execution early into ghost jobs.
+ * Caller must hold no locks.
  */
 static void job_completion(struct task_struct *task, int forced)
 {
@@ -409,88 +478,63 @@ static void job_completion(struct task_struct *task, int forced)
                 job_arrival(task);
 }
 
-/*
- * Return true if the domain has a higher priority ready task. The curr
- * task must belong to the domain.
- */
-static noinline int mc_preempt_needed(domain_t *dom, struct task_struct* curr)
-{
-        struct task_struct *next = dom->peek_ready(dom);
-
-        if (!next || !curr) {
-                return next && !curr;
-        } else {
-                BUG_ON(tsk_mc_crit(next) != tsk_mc_crit(curr));
-                return get_task_domain(next)->higher_prio(next, curr);
-        }
-}
-
-/*
- * Completes a logically (but not physically) running ghost task.
+/**
+ * mc_ghost_exhausted() - Complete logically running ghost task.
  */
 static enum hrtimer_restart mc_ghost_exhausted(struct hrtimer *timer)
 {
         unsigned long flags;
-        crit_cpu_entry_t *ce;
+        crit_entry_t *ce;
+        struct task_struct *tmp = NULL;
 
-        raw_spin_lock_irqsave(&global_lock, flags);
+        local_irq_save(flags);
 
-        ce = container_of(timer, crit_cpu_entry_t, timer);
+        ce = container_of(timer, crit_entry_t, timer);
         TRACE_CRIT_ENTRY(ce, "Ghost exhausted firing");
 
         /* Due to race conditions, we cannot just set the linked
          * task's budget to 0 as it may no longer be the task
-         * for which this timer was armed.
+         * for which this timer was armed. Instead, update the running
+         * task time
          */
+        raw_spin_lock(&crit_cpu(ce)->lock);
         if (ce->linked && is_ghost(ce->linked)) {
                 update_ghost_time(ce->linked);
                 if (tsk_mc_data(ce->linked)->mc_job.ghost_budget == 0) {
-                        job_completion(ce->linked, 0);
-                        goto out;
+                        tmp = ce->linked;
+                        link_task_to_crit(ce, NULL);
                 }
         }
+        raw_spin_unlock(&crit_cpu(ce)->lock);
 
-        TRACE_TASK(ce->linked, "Was not exhausted");
- out:
-        raw_spin_unlock_irqrestore(&global_lock, flags);
+        if (tmp)
+                job_completion(tmp, 0);
+
+        local_irq_restore(flags);
         return HRTIMER_NORESTART;
 }
 
-/*
- * Adds released jobs to a domain and causes a preemption, if necessary.
+/**
+ * mc_release_jobs() - Add heap of tasks to the system, check for preemptions.
  */
 static void mc_release_jobs(rt_domain_t* rt, struct bheap* tasks)
 {
         unsigned long flags;
-        struct task_struct *first;
+        struct task_struct *first = bheap_peek(rt->order, tasks)->value;
+        domain_t *dom = get_task_domain(first);
 
-        raw_spin_lock_irqsave(&global_lock, flags);
+        raw_spin_lock_irqsave(dom->lock, flags);
 
-        first = bheap_peek(rt->order, tasks)->value;
         TRACE_TASK(first, "Jobs released");
-
         __merge_ready(rt, tasks);
-        check_for_preempt(get_task_domain(first));
-
-        raw_spin_unlock_irqrestore(&global_lock, flags);
-}
+        check_for_preempt(dom);
 
-/*
- * Ghost time accounting.
- * TODO: remove
- */
-static void mc_tick(struct task_struct* t)
-{
-        unsigned long flags;
-        if (is_realtime(t) && is_ghost(t)) {
-                raw_spin_lock_irqsave(&global_lock, flags);
-                update_ghost_time(t);
-                raw_spin_unlock_irqrestore(&global_lock, flags);
-        }
+        raw_spin_unlock_irqrestore(dom->lock, flags);
 }
 
-/*
- * Setup new mixed-criticality task.
+/**
+ * ms_task_new() - Setup new mixed-criticality task.
+ * Assumes that there are no partitioned domains after level B.
  */
 static void mc_task_new(struct task_struct *t, int on_rq, int running)
 {
@@ -500,7 +544,7 @@ static void mc_task_new(struct task_struct *t, int on_rq, int running)
 
         TRACE("New mixed criticality task %d\n", t->pid);
 
-        raw_spin_lock_irqsave(&global_lock, flags);
+        local_irq_save(flags);
 
         /* Assign domain */
         level = tsk_mc_crit(t);
@@ -509,14 +553,12 @@ static void mc_task_new(struct task_struct *t, int on_rq, int running)
         } else {
                 entry = cpus[task_cpu(t)];
         }
-        level = tsk_mc_crit(t);
         t->rt_param._domain = entry->crit_entries[level].domain;
 
         /* Setup job params */
         release_at(t, litmus_clock());
         tsk_mc_data(t)->mc_job.ghost_budget = 0;
         tsk_mc_data(t)->mc_job.is_ghost = 0;
-
         if (running) {
                 BUG_ON(entry->scheduled);
                 entry->scheduled = t;
@@ -528,18 +570,18 @@ static void mc_task_new(struct task_struct *t, int on_rq, int running)
 
         job_arrival(t);
 
-        raw_spin_unlock_irqrestore(&global_lock, flags);
+        local_irq_restore(flags);
 }
 
-/*
- * Add task back into its domain and cause any necessary preemptions.
+/**
+ * mc_task_new() - Add task back into its domain check for preemptions.
  */
 static void mc_task_wake_up(struct task_struct *task)
 {
         unsigned long flags;
         lt_t now;
 
-        raw_spin_lock_irqsave(&global_lock, flags);
+        local_irq_save(flags);
         TRACE_TASK(task, "Wakes up");
 
         now = litmus_clock();
@@ -548,49 +590,46 @@ static void mc_task_wake_up(struct task_struct *task)
                 release_at(task, now);
                 sched_trace_task_release(task);
         }
-
         if (!is_ghost(task))
                 job_arrival(task);
 
-        raw_spin_unlock_irqrestore(&global_lock, flags);
+        local_irq_restore(flags);
 }
 
-/*
- * Remove task from global state to prevent it from being linked / run
- * on any CPU.
+/**
+ * mc_task_block() - Remove task from state to prevent it being run anywhere.
  */
 static void mc_task_block(struct task_struct *task)
 {
         unsigned long flags;
-        raw_spin_lock_irqsave(&global_lock, flags);
+        local_irq_save(flags);
         TRACE_TASK(task, "Block at %llu", litmus_clock());
-
         remove_from_all(task);
-
-        raw_spin_unlock_irqrestore(&global_lock, flags);
+        local_irq_restore(flags);
 }
 
-/*
- * Remove task from the system.
+/**
+ * mc_task_exit() - Remove task from the system.
  */
 static void mc_task_exit(struct task_struct *task)
 {
         unsigned long flags;
-
+        local_irq_save(flags);
         BUG_ON(!is_realtime(task));
         TRACE_TASK(task, "RIP");
 
-        raw_spin_lock_irqsave(&global_lock, flags);
         remove_from_all(task);
         if (tsk_rt(task)->scheduled_on != NO_CPU) {
                 cpus[tsk_rt(task)->scheduled_on]->scheduled = NULL;
                 tsk_rt(task)->scheduled_on = NO_CPU;
         }
-        raw_spin_unlock_irqrestore(&global_lock, flags);
+
+        local_irq_restore(flags);
 }
 
-/*
- * Return true if the task is a valid mixed-criticality task.
+/**
+ * mc_admit_task() - Return true if the task is valid.
+ * Assumes there are no partitioned levels after level B.
  */
 static long mc_admit_task(struct task_struct* task)
 {
@@ -614,13 +653,14 @@ static long mc_admit_task(struct task_struct* task)
  */
 static struct task_struct* mc_schedule(struct task_struct * prev)
 {
+        unsigned long flags;
         domain_t *dom;
-        crit_cpu_entry_t *ce;
+        crit_entry_t *ce;
         cpu_entry_t* entry = cpus[smp_processor_id()];
         int i, out_of_time, sleep, preempt, exists, blocks, global;
         struct task_struct *dtask = NULL, *ready_task = NULL, *next = NULL;
 
-        raw_spin_lock(&global_lock);
+        local_irq_save(flags);
 
         /* Sanity checking */
         BUG_ON(entry->scheduled && entry->scheduled != prev);
@@ -660,19 +700,29 @@ static struct task_struct* mc_schedule(struct task_struct * prev)
                 job_arrival(entry->scheduled);
 
         /* Pick next task if none is linked */
-        if (!entry->linked) {
-                for (i = 0; i < NUM_CRIT_LEVELS && !ready_task; i++) {
-                        ce = &entry->crit_entries[i];
-                        dom = ce->domain;
-                        dtask = dom->peek_ready(dom);
-                        if (!ce->linked && dtask) {
-                                dom->take_ready(dom);
-                                link_task_to_crit(ce, dtask);
-                                ready_task = (is_ghost(dtask)) ? NULL : dtask;
+        raw_spin_lock(&entry->lock);
+        for (i = 0; i < NUM_CRIT_LEVELS && !entry->linked; i++) {
+                ce = &entry->crit_entries[i];
+                dom = ce->domain;
+
+                raw_spin_unlock(&entry->lock);
+                raw_spin_lock(dom->lock);
+                raw_spin_lock(&entry->lock);
+
+                dtask = dom->peek_ready(dom);
+                if (!entry->linked && ce->usable && !ce->linked && dtask) {
+                        dom->take_ready(dom);
+                        link_task_to_crit(ce, dtask);
+                        ready_task = (is_ghost(dtask)) ? NULL : dtask;
+                        if (ready_task) {
+                                link_task_to_cpu(entry, ready_task);
+                                raw_spin_unlock(dom->lock);
+                                update_crit_levels(entry);
+                                raw_spin_lock(&entry->lock);
+                                continue;
                         }
                 }
-                if (ready_task)
-                        link_task_to_cpu(entry, ready_task);
+                raw_spin_unlock(dom->lock);
         }
 
         /* Schedule next task */
@@ -683,7 +733,8 @@ static struct task_struct* mc_schedule(struct task_struct * prev)
 
         sched_state_task_picked();
 
-        raw_spin_unlock(&global_lock);
+        raw_spin_unlock(&entry->lock);
+        local_irq_restore(flags);
 
         if (next)
                 TRACE_TASK(next, "Scheduled at %llu", litmus_clock());
@@ -699,7 +750,6 @@ static struct task_struct* mc_schedule(struct task_struct * prev)
 
 static struct sched_plugin mc_plugin __cacheline_aligned_in_smp = {
         .plugin_name            = "MC",
-        .tick                   = mc_tick,
         .task_new               = mc_task_new,
         .complete_job           = complete_job,
         .task_exit              = mc_task_exit,
@@ -713,13 +763,19 @@ static struct sched_plugin mc_plugin __cacheline_aligned_in_smp = {
  * and destroyed when the module is unloaded.
  */
 DEFINE_PER_CPU(cpu_entry_t, _mc_cpus);
+/* LVL-A */
 DEFINE_PER_CPU(domain_data_t, _mc_crit_a);
+DEFINE_PER_CPU(rt_domain_t, _mc_crit_a_rt);
+/* LVL-B */
 DEFINE_PER_CPU(domain_data_t, _mc_crit_b);
-static domain_data_t _mc_crit_c, _mc_crit_d;
-struct bheap _mc_heap_c, _mc_heap_d;
-struct bheap_node _mc_nodes_c[NR_CPUS], _mc_nodes_d[NR_CPUS];
-
-static void init_crit_entry(crit_cpu_entry_t *ce, enum crit_level level,
+DEFINE_PER_CPU(rt_domain_t, _mc_crit_b_rt);
+/* LVL-C */
+static domain_data_t _mc_crit_c;
+static rt_domain_t _mc_crit_c_rt;
+struct bheap _mc_heap_c;
+struct bheap_node _mc_nodes_c[NR_CPUS];
+
+static void init_crit_entry(crit_entry_t *ce, enum crit_level level,
                             domain_data_t *dom_data,
                             struct bheap_node *node)
 {
@@ -727,6 +783,7 @@ static void init_crit_entry(crit_cpu_entry_t *ce, enum crit_level level,
         ce->linked = NULL;
         ce->node   = node;
         ce->domain = &dom_data->domain;
+        ce->usable = 1;
 
         hrtimer_init(&ce->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
         ce->timer.function = mc_ghost_exhausted;
@@ -745,7 +802,7 @@ static void init_global_domain(domain_data_t *dom_data, enum crit_level level,
 {
         int cpu;
         cpu_entry_t *entry;
-        crit_cpu_entry_t *ce;
+        crit_entry_t *ce;
         struct bheap_node *node;
 
         dom_data->crit_entry = NULL;
@@ -764,9 +821,9 @@ static void init_global_domain(domain_data_t *dom_data, enum crit_level level,
         }
 }
 
-static inline void init_edf_domain(domain_t *dom)
+static inline void init_edf_domain(domain_t *dom, rt_domain_t *rt)
 {
-        pd_domain_init(dom, edf_ready_order, NULL,
+        pd_domain_init(dom, rt, edf_ready_order, NULL,
                        mc_release_jobs, mc_preempt_needed,
                        edf_higher_prio);
 }
@@ -775,7 +832,9 @@ static int __init init_mc(void)
 {
         int cpu;
         cpu_entry_t *entry;
+        rt_domain_t *rt;
         domain_data_t *dom_data;
+        raw_spinlock_t *a_dom, *b_dom, *c_dom; /* For lock debugger */
 
         raw_spin_lock_init(&global_lock);
 
@@ -786,32 +845,35 @@ static int __init init_mc(void)
                 entry->cpu = cpu;
                 entry->scheduled = NULL;
                 entry->linked = NULL;
+                raw_spin_lock_init(&entry->lock);
 
                 /* CRIT_LEVEL_A */
                 dom_data = &per_cpu(_mc_crit_a, cpu);
+                rt = &per_cpu(_mc_crit_a_rt, cpu);
                 init_local_domain(entry, dom_data, CRIT_LEVEL_A);
-                init_edf_domain(&dom_data->domain);
+                init_edf_domain(&dom_data->domain, rt);
+                a_dom = dom_data->domain.lock;
+                raw_spin_lock_init(a_dom);
                 dom_data->domain.name = "LVL-A";
 
                 /* CRIT_LEVEL_B */
                 dom_data = &per_cpu(_mc_crit_b, cpu);
+                rt = &per_cpu(_mc_crit_b_rt, cpu);
                 init_local_domain(entry, dom_data, CRIT_LEVEL_B);
-                init_edf_domain(&dom_data->domain);
+                init_edf_domain(&dom_data->domain, rt);
+                b_dom = dom_data->domain.lock;
+                raw_spin_lock_init(b_dom);
                 dom_data->domain.name = "LVL-B";
         }
 
         /* CRIT_LEVEL_C */
         init_global_domain(&_mc_crit_c, CRIT_LEVEL_C,
                            &_mc_heap_c, _mc_nodes_c);
-        init_edf_domain(&_mc_crit_c.domain);
+        init_edf_domain(&_mc_crit_c.domain, &_mc_crit_c_rt);
+        c_dom = _mc_crit_c.domain.lock;
+        raw_spin_lock_init(c_dom);
         _mc_crit_c.domain.name = "LVL-C";
 
-        /* CRIT_LEVEL_D */
-        init_global_domain(&_mc_crit_d, CRIT_LEVEL_D,
-                           &_mc_heap_d, _mc_nodes_d);
-        init_edf_domain(&_mc_crit_d.domain);
-        _mc_crit_d.domain.name = "LVL-D";
-
         return register_sched_plugin(&mc_plugin);
 }
 
diff --git a/litmus/sched_mc_ce.c b/litmus/sched_mc_ce.c
index 1fdca7a7d3aa..0a5a18dc54ff 100644
--- a/litmus/sched_mc_ce.c
+++ b/litmus/sched_mc_ce.c
@@ -61,6 +61,7 @@ struct ce_dom_data {
 };
 
 DEFINE_PER_CPU(domain_t, mc_ce_doms);
+DEFINE_PER_CPU(rt_domain_t, mc_ce_rts);
 DEFINE_PER_CPU(struct ce_dom_data, _mc_ce_dom_data);
 
 /*
@@ -511,12 +512,14 @@ static int __init init_sched_mc_ce(void)
 {
         struct ce_dom_data *ce_data;
         domain_t *dom;
+        rt_domain_t *rt;
         int cpu, err;
 
         clear_pid_entries();
         for_each_online_cpu(cpu) {
                 dom = &per_cpu(mc_ce_doms, cpu);
-                pd_domain_init(dom, NULL, NULL, NULL, NULL, NULL);
+                rt = &per_cpu(mc_ce_rts, cpu);
+                pd_domain_init(dom, rt, NULL, NULL, NULL, NULL, NULL);
                 dom->data = &per_cpu(_mc_ce_dom_data, cpu);
                 ce_data = dom->data;
                 hrtimer_init(&ce_data->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);