Added many comments; some minor style changes

1 files changed, 94 insertions, 38 deletions

diff --git a/litmus/sched_mc.c b/litmus/sched_mc.c
index 0a8464b5aa5c..e2b9fffd72f4 100644
--- a/litmus/sched_mc.c
+++ b/litmus/sched_mc.c
@@ -26,10 +26,6 @@
 
 /* Overview of MC operations.
  *
- * For a detailed explanation of MC have a look at the FMLP paper. This
- * description only covers how the individual operations are implemented in
- * LITMUS.
- *
  * link_task_to_cpu(T, cpu)     - Low-level operation to update the linkage
  *                                structure (NOT the actually scheduled
  *                                task). If there is another linked task To
@@ -118,18 +114,22 @@ cpu_entry_t* mc_cpus[NR_CPUS];
 static struct bheap_node mc_heap_node[NR_CPUS];
 static struct bheap      mc_cpu_heap;
 
-/*static rt_domain_t mc;*/
-DEFINE_PER_CPU(rt_domain_t, crit_b);
-#define remote_b_queue(cpu)     (&per_cpu(crit_b, cpu))
-#define local_b_queue           (&__get_cpu_var(crit_b))
-
+/* Create per-CPU domains for criticality A */
 DEFINE_PER_CPU(rt_domain_t, crit_a);
 #define remote_a_queue(cpu)     (&per_cpu(crit_a, cpu))
 #define local_a_queue           (&__get_cpu_var(crit_a))
 
+/* Create per-CPU domains for criticality B */
+DEFINE_PER_CPU(rt_domain_t, crit_b);
+#define remote_b_queue(cpu)     (&per_cpu(crit_b, cpu))
+#define local_b_queue           (&__get_cpu_var(crit_b))
+
+/* Create global domains for criticalities C and D */
 static rt_domain_t crit_c;
 static rt_domain_t crit_d;
-#define crit_c_lock (crit_c.ready_lock)
+
+/* We use crit_c.ready_lock as a global lock */
+#define global_lock (crit_c.ready_lock)
 
 /* BEGIN clone of edf_common.c to allow shared C/D run queue*/
 
@@ -188,7 +188,8 @@ static void mc_edf_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
 
 /* END clone of edf_common.c*/
 
-static rt_domain_t* proper_domain(struct task_struct* task)
+/* Return the domain of a task */
+static rt_domain_t* domain_of(struct task_struct* task)
 {
         switch (task->rt_param.task_params.crit)
         {
@@ -215,6 +216,9 @@ static rt_domain_t* proper_domain(struct task_struct* task)
 #define WANT_ALL_SCHED_EVENTS
  */
 
+/* Called by update_cpu_position and lowest_prio_cpu in bheap operations
+ *      Callers always have global lock
+*/
 static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b)
 {
         cpu_entry_t *a, *b;
@@ -227,7 +231,10 @@ static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b)
 }
 
 /* update_cpu_position - Move the cpu entry to the correct place to maintain
- *                       order in the cpu queue. Caller must hold mc lock.
+ *                       order in the cpu queue. Caller must hold global lock.
+ * Called from link_task_to_cpu, which holds global lock
+ * link_task_to_cpu is the only way a CPU can get a new task, and hence have its
+ *      priority change.
  */
 static void update_cpu_position(cpu_entry_t *entry)
 {
@@ -236,7 +243,10 @@ static void update_cpu_position(cpu_entry_t *entry)
         bheap_insert(cpu_lower_prio, &mc_cpu_heap, entry->hn);
 }
 
-/* caller must hold mc lock */
+/* caller must hold global lock
+ * Only called when checking for gedf preemptions by check_for_gedf_preemptions,
+ *      which always has global lock
+ */
 static cpu_entry_t* lowest_prio_cpu(void)
 {
         struct bheap_node* hn;
@@ -248,6 +258,8 @@ static cpu_entry_t* lowest_prio_cpu(void)
 /* link_task_to_cpu - Update the link of a CPU.
  *                    Handles the case where the to-be-linked task is already
  *                    scheduled on a different CPU.
+ *      Called from unlink(), prepare_preemption(), and mc_schedule()
+ *      Callers hold global lock
  */
 static noinline void link_task_to_cpu(struct task_struct* linked,
                                       cpu_entry_t *entry)
@@ -313,8 +325,10 @@ static noinline void link_task_to_cpu(struct task_struct* linked,
         update_cpu_position(entry);
 }
 
-/* unlink - Make sure a task is not linked any longer to an entry
- *          where it was linked before. Must hold appropriate lock
+/* unlink - Make sure a task is not linked any longer to a cpu entry
+ *          where it was linked before.
+ *      Called by schedule, task_block, task_exit, and job_completion
+ *      Caller assumed to hold global lock
  */
 static noinline void unlink(struct task_struct* t)
 {
@@ -339,12 +353,13 @@ static noinline void unlink(struct task_struct* t)
                  * case.
                  */
                 TRACE("Weird is_queued situation happened\n");
-                remove(proper_domain(t), t);
+                remove(domain_of(t), t);
         }
 }
 
 
 /* preempt - force a CPU to reschedule
+ * Just sets a Linux scheduler flag.
  */
 static void preempt(cpu_entry_t *entry)
 {
@@ -352,7 +367,8 @@ static void preempt(cpu_entry_t *entry)
 }
 
 /* requeue - Put an unlinked task into the proper domain.
- *           Caller must hold proper lock.
+ *           Caller holds global lock.
+ *           Called by mc_job_arrival() and prepare_preemption().
  */
 static noinline void requeue(struct task_struct* task)
 {
@@ -361,17 +377,17 @@ static noinline void requeue(struct task_struct* task)
         BUG_ON(is_queued(task));
 
         if (is_released(task, litmus_clock()))
-                __add_ready(proper_domain(task), task);
+                __add_ready(domain_of(task), task);
         else {
                 /* it has got to wait */
-                add_release(proper_domain(task), task);
+                add_release(domain_of(task), task);
         }
 }
 
-static void do_preemption_on_cpu(rt_domain_t *dom, cpu_entry_t *cpu) {
+static void prepare_preemption(rt_domain_t *dom, cpu_entry_t *cpu) {
         struct task_struct* task;
         task = __take_ready(dom);
-        TRACE("do_preemption_on_cpu: attempting to link task %d to %d\n",
+        TRACE("prepare_preemption: attempting to link task %d to %d\n",
                 task->pid, cpu->cpu);
         if (cpu->linked)
                 requeue(cpu->linked);
@@ -379,22 +395,27 @@ static void do_preemption_on_cpu(rt_domain_t *dom, cpu_entry_t *cpu) {
         preempt(cpu);
 }
 
+/* Callers always have global lock */
 static void check_for_gedf_preemptions(rt_domain_t *dom){
         cpu_entry_t* last;
         for (last = lowest_prio_cpu();
                         mc_edf_preemption_needed(dom, last->linked);
                         last = lowest_prio_cpu()) {
-                do_preemption_on_cpu(dom, last);
+                prepare_preemption(dom, last);
         }
 }
 
 static void check_for_pedf_preemption(rt_domain_t *dom, cpu_entry_t *cpu) {
         if (mc_edf_preemption_needed(dom, cpu->linked)) {
-                do_preemption_on_cpu(dom, cpu);
+                prepare_preemption(dom, cpu);
         }
 }
 
-/* mc_job_arrival: task is either resumed or released */
+/* mc_job_arrival: task is either resumed or released
+ * Called from job_completion(), mc_task_new(), and mc_task_wake_up(), all
+ *      of which have the global lock
+ * Requeues task and checks for/triggers preemptions
+ */
 static noinline void mc_job_arrival(struct task_struct* task)
 {
         BUG_ON(!task);
@@ -417,12 +438,16 @@ static noinline void mc_job_arrival(struct task_struct* task)
         }
 }
 
+/* Called by the domain
+ * Obtains global lock, merges ready tasks, checks for/triggers preemptions,
+ *      and releases global lock
+*/
 static void mc_release_jobs(rt_domain_t* rt, struct bheap* tasks)
 {
         unsigned long flags;
         int i;
 
-        raw_spin_lock_irqsave(&crit_c_lock, flags);
+        raw_spin_lock_irqsave(&global_lock, flags);
         TRACE("mc_release_jobs triggered\n");
 
         __merge_ready(rt, tasks);
@@ -439,10 +464,13 @@ static void mc_release_jobs(rt_domain_t* rt, struct bheap* tasks)
                 check_for_gedf_preemptions(rt);
         }
 
-        raw_spin_unlock_irqrestore(&crit_c_lock, flags);
+        raw_spin_unlock_irqrestore(&global_lock, flags);
 }
 
-/* caller holds crit_c_lock */
+/* caller holds global_lock
+ * Called only by mc_schedule() which holds global lock
+ * Prepares task for next period, unlinks it, and calls mc_job_arrival
+*/
 static noinline void job_completion(struct task_struct *t, int forced)
 {
         BUG_ON(!t);
@@ -470,6 +498,9 @@ static noinline void job_completion(struct task_struct *t, int forced)
  *
  *                   checks whether the current task has expired and checks
  *                   whether we need to preempt it if it has not expired
+ * Called from LITMUS core
+ * Does not use locks
+ * Just sets reschedule flags on task and CPU and request_exit_np flag on task
  */
 static void mc_tick(struct task_struct* t)
 {
@@ -512,6 +543,14 @@ static void mc_tick(struct task_struct* t)
  *                                         sys_exit_np must be requested
  *
  * Any of these can occur together.
+ *
+ *
+ * Called by LITMUS core
+ * No lock required by caller
+ * Obtains global lock
+ * can call unlink(), request_exit_np(), job_completion(), __take_ready()
+ * modifies next, scheduled->scheduled_on, linked->scheduled_on
+ * Releases global lock
  */
 static struct task_struct* mc_schedule(struct task_struct * prev)
 {
@@ -528,7 +567,7 @@ static struct task_struct* mc_schedule(struct task_struct * prev)
                 return NULL;
 #endif
 
-        raw_spin_lock(&crit_c_lock);
+        raw_spin_lock(&global_lock);
         clear_will_schedule();
 
         /* sanity checking */
@@ -622,10 +661,10 @@ static struct task_struct* mc_schedule(struct task_struct * prev)
                         next = prev;
 
         /*TODO: Update name of locking, reflect that we're locking all queues*/
-        raw_spin_unlock(&crit_c_lock);
+        raw_spin_unlock(&global_lock);
 
 #ifdef WANT_ALL_SCHED_EVENTS
-        TRACE("crit_c_lock released, next=0x%p\n", next);
+        TRACE("global_lock released, next=0x%p\n", next);
 
         if (next)
                 TRACE_TASK(next, "scheduled at %llu\n", litmus_clock());
@@ -639,6 +678,8 @@ static struct task_struct* mc_schedule(struct task_struct * prev)
 
 
 /* _finish_switch - we just finished the switch away from prev
+ * Called by LITMUS core
+ * No locks
  */
 static void mc_finish_switch(struct task_struct *prev)
 {
@@ -652,6 +693,9 @@ static void mc_finish_switch(struct task_struct *prev)
 
 
 /*      Prepare a task for running in RT mode
+ *      Called by LITMUS core
+ *      No lock required by caller
+ *      Obtains lock and calls mc_job_arrival before releasing lock
  */
 static void mc_task_new(struct task_struct * t, int on_rq, int running)
 {
@@ -660,7 +704,7 @@ static void mc_task_new(struct task_struct * t, int on_rq, int running)
 
         TRACE("mixed crit: task new %d\n", t->pid);
 
-        raw_spin_lock_irqsave(&crit_c_lock, flags);
+        raw_spin_lock_irqsave(&global_lock, flags);
 
         /* setup job params */
         release_at(t, litmus_clock());
@@ -687,9 +731,13 @@ static void mc_task_new(struct task_struct * t, int on_rq, int running)
         t->rt_param.linked_on          = NO_CPU;
 
         mc_job_arrival(t);
-        raw_spin_unlock_irqrestore(&crit_c_lock, flags);
+        raw_spin_unlock_irqrestore(&global_lock, flags);
 }
 
+/* Called by LITMUS core
+ * No lock required by caller
+ * Obtains lock and calls mc_job_arrival before releasing lock
+ */
 static void mc_task_wake_up(struct task_struct *task)
 {
         unsigned long flags;
@@ -697,7 +745,7 @@ static void mc_task_wake_up(struct task_struct *task)
 
         TRACE_TASK(task, "wake_up at %llu\n", litmus_clock());
 
-        raw_spin_lock_irqsave(&crit_c_lock, flags);
+        raw_spin_lock_irqsave(&global_lock, flags);
         /* We need to take suspensions because of semaphores into
          * account! If a job resumes after being suspended due to acquiring
          * a semaphore, it should never be treated as a new job release.
@@ -720,9 +768,13 @@ static void mc_task_wake_up(struct task_struct *task)
                 }
         }
         mc_job_arrival(task);
-        raw_spin_unlock_irqrestore(&crit_c_lock, flags);
+        raw_spin_unlock_irqrestore(&global_lock, flags);
 }
 
+/* Called by LITMUS core
+ * No lock required by caller
+ * Obtains and releases global lock
+ */
 static void mc_task_block(struct task_struct *t)
 {
         unsigned long flags;
@@ -730,26 +782,30 @@ static void mc_task_block(struct task_struct *t)
         TRACE_TASK(t, "block at %llu\n", litmus_clock());
 
         /* unlink if necessary */
-        raw_spin_lock_irqsave(&crit_c_lock, flags);
+        raw_spin_lock_irqsave(&global_lock, flags);
         unlink(t);
-        raw_spin_unlock_irqrestore(&crit_c_lock, flags);
+        raw_spin_unlock_irqrestore(&global_lock, flags);
 
         BUG_ON(!is_realtime(t));
 }
 
 
+/* Called by LITMUS core
+ * No lock required by caller
+ * Obtains and releases global lock
+ */
 static void mc_task_exit(struct task_struct * t)
 {
         unsigned long flags;
 
         /* unlink if necessary */
-        raw_spin_lock_irqsave(&crit_c_lock, flags);
+        raw_spin_lock_irqsave(&global_lock, flags);
         unlink(t);
         if (tsk_rt(t)->scheduled_on != NO_CPU) {
                 mc_cpus[tsk_rt(t)->scheduled_on]->scheduled = NULL;
                 tsk_rt(t)->scheduled_on = NO_CPU;
         }
-        raw_spin_unlock_irqrestore(&crit_c_lock, flags);
+        raw_spin_unlock_irqrestore(&global_lock, flags);
 
         BUG_ON(!is_realtime(t));
         TRACE_TASK(t, "RIP\n");