1 files changed, 201 insertions, 26 deletions

diff --git a/litmus/edf_common.c b/litmus/edf_common.c
index 9b44dc2d8d1e..39ce1816ee04 100644
--- a/litmus/edf_common.c
+++ b/litmus/edf_common.c
@@ -12,40 +12,85 @@
 #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
+#include <litmus/fpmath.h>
+#endif
+
+#ifdef CONFIG_EDF_TIE_BREAK_HASH
+#include <linux/hash.h>
+static inline long edf_hash(struct task_struct *t)
+{
+        /* pid is 32 bits, so normally we would shove that into the
+         * upper 32-bits and and put the job number in the bottom
+         * and hash the 64-bit number with hash_64(). Sadly,
+         * in testing, hash_64() doesn't distribute keys were the
+         * upper bits are close together (as would be the case with
+         * pids) and job numbers are equal (as would be the case with
+         * synchronous task sets with all relative deadlines equal).
+         *
+         * A 2006 Linux patch proposed the following solution
+         * (but for some reason it wasn't accepted...).
+         *
+         * At least this workaround works for 32-bit systems as well.
+         */
+        return hash_32(hash_32((u32)tsk_rt(t)->job_params.job_no, 32) ^ t->pid, 32);
+}
+#endif
+
+
 /* edf_higher_prio -  returns true if first has a higher EDF priority
  *                    than second. Deadline ties are broken by PID.
  *
  * 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
-
-        /* Check for inherited priorities. Change task
+        /* 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.
          */
@@ -53,37 +98,167 @@ 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
 
-
-        return !is_realtime(second_task)  ||
-
-                /* is the deadline of the first task earlier?
-                 * Then it has higher priority.
+        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)) {
+                /* Need to tie break. All methods must set pid_break to 0/1 if
+                 * first_task does not have priority over second_task.
                  */
-                earlier_deadline(first_task, second_task) ||
+                int pid_break;
 
-                /* Do we have a deadline tie?
-                 * Then break by PID.
+#if defined(CONFIG_EDF_TIE_BREAK_LATENESS)
+        /* Tie break by lateness. Jobs with greater lateness get
+                 * priority. This should spread tardiness across all tasks,
+                 * especially in task sets where all tasks have the same
+                 * period and relative deadlines.
                  */
-                (get_deadline(first_task) == get_deadline(second_task) &&
-                (first_task->pid < second_task->pid ||
+                if (get_lateness(first_task) > get_lateness(second_task)) {
+                        return 1;
+                }   
+                pid_break = (get_lateness(first_task) == get_lateness(second_task));
+
 
-                /* If the PIDs are the same then the task with the inherited
-                 * priority wins.
+#elif defined(CONFIG_EDF_TIE_BREAK_LATENESS_NORM)
+                /* Tie break by lateness, normalized by relative deadline. Jobs with
+                 * greater normalized lateness get priority.
+                 *
+                 * Note: Considered using the algebraically equivalent
+                 *      lateness(first)*relative_deadline(second) >
+                                        lateness(second)*relative_deadline(first)
+                 * to avoid fixed-point math, but values are prone to overflow if inputs
+                 * are on the order of several seconds, even in 64-bit.
+                 */
+                fp_t fnorm = _frac(get_lateness(first_task),
+                                                   get_rt_relative_deadline(first_task));
+                fp_t snorm = _frac(get_lateness(second_task),
+                                                   get_rt_relative_deadline(second_task));
+                if (_gt(fnorm, snorm)) {
+                        return 1;
+                }
+                pid_break = _eq(fnorm, snorm);
+                
+                
+#elif defined(CONFIG_EDF_TIE_BREAK_HASH)
+                /* Tie break by comparing hashs of (pid, job#) tuple.  There should be
+                 * a 50% chance that first_task has a higher priority than second_task.
                  */
-                (first_task->pid == second_task->pid &&
-                 !second->rt_param.inh_task)));
+                long fhash = edf_hash(first_task);
+                long shash = edf_hash(second_task);
+                if (fhash < shash) {
+                        return 1;
+                }
+                pid_break = (fhash == shash);
+#else
+                
+                
+                /* CONFIG_EDF_PID_TIE_BREAK */
+                pid_break = 1; // fall through to tie-break by pid;
+#endif
+
+                /* Tie break by pid */
+                if(pid_break) {
+                        if (first_task->pid < second_task->pid) {
+                                return 1;
+                        }
+                        else if (first_task->pid == second_task->pid) {
+#ifdef CONFIG_LITMUS_SOFTIRQD
+                                if (first_task->rt_param.is_proxy_thread < 
+                                        second_task->rt_param.is_proxy_thread) {
+                                        return 1;
+                                }
+#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 (likely(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 with the inherited priority wins. */
+                                        if (!second->rt_param.inh_task) {
+                                                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;
+                                        }
+                                }
+                        }
+                }
+        }
+
+        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));