Merge branch 'wip-gpu-cleanup' into wip-2012.3-gpu

Conflicts:
	include/litmus/fpmath.h
	include/litmus/litmus.h
	include/litmus/rt_param.h
	include/litmus/trace.h
	kernel/sched.c
	kernel/softirq.c
	litmus/edf_common.c
	litmus/jobs.c
	litmus/litmus.c
	litmus/locking.c
	litmus/preempt.c
	litmus/sched_cedf.c
	litmus/sched_gsn_edf.c
	litmus/sched_litmus.c
	litmus/sync.c

1 files changed, 246 insertions, 18 deletions

diff --git a/litmus/edf_common.c b/litmus/edf_common.c
index 5aca2934a7b5..441fbfddf0c2 100644
--- a/litmus/edf_common.c
+++ b/litmus/edf_common.c
@@ -12,6 +12,10 @@
 #include <litmus/sched_plugin.h>
 #include <litmus/sched_trace.h>
 
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+#include <litmus/locking.h>
+#endif
+
 #include <litmus/edf_common.h>
 
 #ifdef CONFIG_EDF_TIE_BREAK_LATENESS_NORM
@@ -45,33 +49,158 @@ static inline long edf_hash(struct task_struct *t)
  *
  * both first and second may be NULL
  */
-int edf_higher_prio(struct task_struct* first,
-                    struct task_struct* second)
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+int __edf_higher_prio(
+        struct task_struct* first, comparison_mode_t first_mode,
+        struct task_struct* second, comparison_mode_t second_mode)
+#else
+int edf_higher_prio(struct task_struct* first, struct task_struct* second)
+#endif
 {
         struct task_struct *first_task = first;
         struct task_struct *second_task = second;
 
         /* There is no point in comparing a task to itself. */
         if (first && first == second) {
-                TRACE_TASK(first,
-                           "WARNING: pointless edf priority comparison.\n");
+                TRACE_CUR("WARNING: pointless edf priority comparison: %s/%d\n", first->comm, first->pid);
+                WARN_ON(1);
                 return 0;
         }
 
 
         /* check for NULL tasks */
-        if (!first || !second)
+        if (!first || !second) {
                 return first && !second;
+        }
 
-#ifdef CONFIG_LITMUS_LOCKING
+        /* There is some goofy stuff in this code here.  There are three subclasses
+         * within the SCHED_LITMUS scheduling class:
+         * 1) Auxiliary tasks: COTS helper threads from the application level that
+         *      are forced to be real-time.
+         * 2) klmirqd interrupt threads: Litmus threaded interrupt handlers.
+         * 3) Normal Litmus tasks.
+         *
+         * At their base priorities, #3 > #2 > #1.  However, #1 and #2 threads might
+         * inherit a priority from a task of #3.
+         *
+         * The code proceeds in the following manner:
+         * 1) Make aux and klmirqd threads with base-priorities have low priorities.
+         * 2) Determine effective priorities.
+         * 3) Perform priority comparison.  Favor #3 over #1 and #2 in case of tie.
+         */
+
+
+#if defined(CONFIG_REALTIME_AUX_TASK_PRIORITY_BOOSTED)
+        /* run aux tasks at max priority */
+        /* TODO: Actually use prio-boosting. */
+        if (first->rt_param.is_aux_task != second->rt_param.is_aux_task)
+        {
+                return (first->rt_param.is_aux_task > second->rt_param.is_aux_task);
+        }
+        else if(first->rt_param.is_aux_task && second->rt_param.is_aux_task)
+        {
+                if(first->group_leader == second->group_leader) {
+                        TRACE_CUR("aux tie break!\n");  // tie-break by BASE priority of the aux tasks
+                        goto aux_tie_break;
+                }
+                first = first->group_leader;
+                second = second->group_leader;
+        }
+#elif defined(CONFIG_REALTIME_AUX_TASK_PRIORITY_INHERITANCE)
+        {
+                int first_lo_aux = first->rt_param.is_aux_task && !first->rt_param.inh_task;
+                int second_lo_aux = second->rt_param.is_aux_task && !second->rt_param.inh_task;
+
+                /* prioritize aux tasks without inheritance below real-time tasks */
+                if (first_lo_aux || second_lo_aux) {
+                        // one of these is an aux task without inheritance.
+                        if(first_lo_aux && second_lo_aux) {
+                                TRACE_CUR("aux tie break!\n");  // tie-break by BASE priority of the aux tasks
+                                goto aux_tie_break;
+                        }
+                        else {
+
+                                // make the aux thread lowest priority real-time task
+                                int temp = 0;
+                                if (first_lo_aux && is_realtime(second)) {
+//                                      temp = 0;
+                                }
+                                else if(second_lo_aux && is_realtime(first)) {
+                                        temp = 1;
+                                }
+                                TRACE_CUR("%s/%d >> %s/%d --- %d\n", first->comm, first->pid, second->comm, second->pid, temp);
+                                return temp;
+                        }
+                }
+
+                if (first->rt_param.is_aux_task && second->rt_param.is_aux_task &&
+                        first->rt_param.inh_task == second->rt_param.inh_task) {
+                        // inh_task is !NULL for both tasks since neither was a lo_aux task.
+                        // Both aux tasks inherit from the same task, so tie-break
+                        // by base priority of the aux tasks.
+                        TRACE_CUR("aux tie break!\n");
+                        goto aux_tie_break;
+                }
+        }
+#endif
+
+#ifdef CONFIG_LITMUS_SOFTIRQD
+        {
+                int first_lo_klmirqd = first->rt_param.is_interrupt_thread && !first->rt_param.inh_task;
+                int second_lo_klmirqd = second->rt_param.is_interrupt_thread && !second->rt_param.inh_task;
+
+                /* prioritize aux tasks without inheritance below real-time tasks */
+                if (first_lo_klmirqd || second_lo_klmirqd) {
+                        // one of these is an klmirqd thread without inheritance.
+                        if(first_lo_klmirqd && second_lo_klmirqd) {
+                                TRACE_CUR("klmirqd tie break!\n");  // tie-break by BASE priority of the aux tasks
+                                goto klmirqd_tie_break;
+                        }
+                        else {
+                                // make the klmirqd thread the lowest-priority real-time task
+                                // but (above low-prio aux tasks and Linux tasks)
+                                int temp = 0;
+                                if (first_lo_klmirqd && is_realtime(second)) {
+//                                      temp = 0;
+                                }
+                                else if(second_lo_klmirqd && is_realtime(first)) {
+                                        temp = 1;
+                                }
+                                TRACE_CUR("%s/%d >> %s/%d --- %d\n", first->comm, first->pid, second->comm, second->pid, temp);
+                                return temp;
+                        }
+                }
+
+                if (first->rt_param.is_interrupt_thread && second->rt_param.is_interrupt_thread &&
+                        first->rt_param.inh_task == second->rt_param.inh_task) {
+                        // inh_task is !NULL for both tasks since neither was a lo_klmirqd task.
+                        // Both klmirqd tasks inherit from the same task, so tie-break
+                        // by base priority of the klmirqd tasks.
+                        TRACE_CUR("klmirqd tie break!\n");
+                        goto klmirqd_tie_break;
+                }
+        }
+#endif
 
-        /* Check for inherited priorities. Change task
+
+#ifdef CONFIG_LITMUS_LOCKING
+        /* Check for EFFECTIVE priorities. Change task
          * used for comparison in such a case.
          */
-        if (unlikely(first->rt_param.inh_task))
+        if (unlikely(first->rt_param.inh_task)
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+                && (first_mode == EFFECTIVE)
+#endif
+                ) {
                 first_task = first->rt_param.inh_task;
-        if (unlikely(second->rt_param.inh_task))
+        }
+        if (unlikely(second->rt_param.inh_task)
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+                && (second_mode == EFFECTIVE)
+#endif
+                ) {
                 second_task = second->rt_param.inh_task;
+        }
 
         /* Check for priority boosting. Tie-break by start of boosting.
          */
@@ -79,17 +208,31 @@ int edf_higher_prio(struct task_struct* first,
                 /* first_task is boosted, how about second_task? */
                 if (!is_priority_boosted(second_task) ||
                     lt_before(get_boost_start(first_task),
-                              get_boost_start(second_task)))
+                                          get_boost_start(second_task))) {
                         return 1;
-                else
+                }
+                else {
                         return 0;
-        } else if (unlikely(is_priority_boosted(second_task)))
+                }
+        }
+        else if (unlikely(is_priority_boosted(second_task))) {
                 /* second_task is boosted, first is not*/
                 return 0;
+        }
+
+#endif
 
+#ifdef CONFIG_REALTIME_AUX_TASKS
+aux_tie_break:
+#endif
+#ifdef CONFIG_LITMUS_SOFTIRQD
+klmirqd_tie_break:
 #endif
 
-        if (earlier_deadline(first_task, second_task)) {
+        if (!is_realtime(second_task)) {
+                return 1;
+        }
+        else if (earlier_deadline(first_task, second_task)) {
                 return 1;
         }
         else if (get_deadline(first_task) == get_deadline(second_task)) {
@@ -98,7 +241,6 @@ int edf_higher_prio(struct task_struct* first,
                  */
                 int pid_break;
 
-
 #if defined(CONFIG_EDF_TIE_BREAK_LATENESS)
                 /* Tie break by lateness. Jobs with greater lateness get
                  * priority. This should spread tardiness across all tasks,
@@ -154,18 +296,104 @@ int edf_higher_prio(struct task_struct* first,
                                 return 1;
                         }
                         else if (first_task->pid == second_task->pid) {
-                                /* If the PIDs are the same then the task with the
-                                 * inherited priority wins.
-                                 */
-                                if (!second->rt_param.inh_task) {
+#ifdef CONFIG_LITMUS_SOFTIRQD
+                                if (first_task->rt_param.is_interrupt_thread < second_task->rt_param.is_interrupt_thread) {
+                                        return 1;
+                                }
+                                else if (first_task->rt_param.is_interrupt_thread == second_task->rt_param.is_interrupt_thread) {
+#endif
+
+#if defined(CONFIG_REALTIME_AUX_TASK_PRIORITY_INHERITANCE)
+                                if (tsk_rt(first)->is_aux_task < tsk_rt(second)->is_aux_task) {
                                         return 1;
                                 }
+                                else if (tsk_rt(first)->is_aux_task == tsk_rt(second)->is_aux_task) {
+#endif
+
+                                /* Something could be wrong if you get this far. */
+                                if (unlikely(first->rt_param.inh_task == second->rt_param.inh_task)) {
+                                        /* Both tasks have the same inherited priority.
+                                         * Likely in a bug-condition.
+                                     */
+                                        if (first->pid < second->pid) {
+                                                return 1;
+                                        }
+                                        else if (first->pid == second->pid) {
+                                                //WARN_ON(1);
+                                        }
+                                }
+                                else {
+                                        /* At least one task must inherit */
+                                        BUG_ON(!first->rt_param.inh_task &&
+                                                   !second->rt_param.inh_task);
+
+                                        /* The task withOUT the inherited priority wins. */
+                                        if (second->rt_param.inh_task) {
+                                                /*
+                                                 * common with aux tasks.
+                                                TRACE_CUR("unusual comparison: "
+                                                        "first = %s/%d  first_task = %s/%d  "
+                                                        "second = %s/%d  second_task = %s/%d\n",
+                                                        first->comm, first->pid,
+                                                        (first->rt_param.inh_task) ? first->rt_param.inh_task->comm : "(nil)",
+                                                        (first->rt_param.inh_task) ? first->rt_param.inh_task->pid : 0,
+                                                        second->comm, second->pid,
+                                                        (second->rt_param.inh_task) ? second->rt_param.inh_task->comm : "(nil)",
+                                                        (second->rt_param.inh_task) ? second->rt_param.inh_task->pid : 0);
+                                                 */
+                                                return 1;
+                                        }
+                                }
+#if defined(CONFIG_REALTIME_AUX_TASK_PRIORITY_INHERITANCE)
+                                }
+#endif
+
+#ifdef CONFIG_LITMUS_SOFTIRQD
+                                }
+#endif
+
                         }
                 }
         }
+
         return 0; /* fall-through. prio(second_task) > prio(first_task) */
 }
 
+
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+int edf_higher_prio(struct task_struct* first, struct task_struct* second)
+{
+        return __edf_higher_prio(first, EFFECTIVE, second, EFFECTIVE);
+}
+
+int edf_max_heap_order(struct binheap_node *a, struct binheap_node *b)
+{
+        struct nested_info *l_a = (struct nested_info *)binheap_entry(a, struct nested_info, hp_binheap_node);
+        struct nested_info *l_b = (struct nested_info *)binheap_entry(b, struct nested_info, hp_binheap_node);
+
+        return __edf_higher_prio(l_a->hp_waiter_eff_prio, EFFECTIVE, l_b->hp_waiter_eff_prio, EFFECTIVE);
+}
+
+int edf_min_heap_order(struct binheap_node *a, struct binheap_node *b)
+{
+        return edf_max_heap_order(b, a);  // swap comparison
+}
+
+int edf_max_heap_base_priority_order(struct binheap_node *a, struct binheap_node *b)
+{
+        struct nested_info *l_a = (struct nested_info *)binheap_entry(a, struct nested_info, hp_binheap_node);
+        struct nested_info *l_b = (struct nested_info *)binheap_entry(b, struct nested_info, hp_binheap_node);
+
+        return __edf_higher_prio(l_a->hp_waiter_eff_prio, BASE, l_b->hp_waiter_eff_prio, BASE);
+}
+
+int edf_min_heap_base_priority_order(struct binheap_node *a, struct binheap_node *b)
+{
+        return edf_max_heap_base_priority_order(b, a);  // swap comparison
+}
+#endif
+
+
 int edf_ready_order(struct bheap_node* a, struct bheap_node* b)
 {
         return edf_higher_prio(bheap2task(a), bheap2task(b));