Merge branch 'prop/robust-tie-break' into wip-gpu-rtas12

Conflicts:
	include/litmus/binheap.h
	include/litmus/fdso.h
	include/litmus/litmus.h
	litmus/Makefile
	litmus/binheap.c
	litmus/edf_common.c
	litmus/fdso.c
	litmus/jobs.c
	litmus/locking.c

1 files changed, 94 insertions, 38 deletions

diff --git a/litmus/edf_common.c b/litmus/edf_common.c
index b346bdd65b3b..a1cdc10ea6f1 100644
--- a/litmus/edf_common.c
+++ b/litmus/edf_common.c
@@ -18,6 +18,30 @@
 
 #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
@@ -88,58 +112,90 @@ int edf_higher_prio(struct task_struct* first, struct task_struct* second)
 
 #endif
 
-//      // rate-monotonic for testing
-//      if (!is_realtime(second_task)) {
-//              return true;
-//      }
-//
-//      if (shorter_period(first_task, second_task)) {
-//              return true;
-//      }
-//
-//      if (get_period(first_task) == get_period(second_task)) {
-//              if (first_task->pid < second_task->pid) {
-//                      return true;
-//              }
-//              else if (first_task->pid == second_task->pid) {
-//                      return !second->rt_param.inh_task;
-//              }
-//      }
-
         if (!is_realtime(second_task)) {
-                return true;
+                return 1;
         }
-
-        if (earlier_deadline(first_task, second_task)) {
-                return true;
+        else if (earlier_deadline(first_task, second_task)) {
+                return 1;
         }
-        if (get_deadline(first_task) == get_deadline(second_task)) {
-
-                if (shorter_period(first_task, second_task)) {
-                        return true;
+        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.
+                 */
+                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,
+                 * especially in task sets where all tasks have the same
+                 * period and relative deadlines.
+                 */
+                if (get_lateness(first_task) > get_lateness(second_task)) {
+                        return 1;
+                }   
+                pid_break = (get_lateness(first_task) == get_lateness(second_task));
+
+
+#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.
+                 */
+                long fhash = edf_hash(first_task);
+                long shash = edf_hash(second_task);
+                if (fhash < shash) {
+                        return 1;
                 }
-                if (get_rt_period(first_task) == get_rt_period(second_task)) {
+                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 true;
+                                return 1;
                         }
-                        if (first_task->pid == second_task->pid) {
+                        else if (first_task->pid == second_task->pid) {
 #ifdef CONFIG_LITMUS_SOFTIRQD
-                                if (first_task->rt_param.is_proxy_thread <
+                                if (first_task->rt_param.is_proxy_thread < 
                                         second_task->rt_param.is_proxy_thread) {
-                                        return true;
-                                }
-                                if(first_task->rt_param.is_proxy_thread == second_task->rt_param.is_proxy_thread) {
-                                        return !second->rt_param.inh_task;
+                                        return 1;
                                 }
-#else
-                                return !second->rt_param.inh_task;
 #endif
+                                /* If the PIDs are the same then the task with the
+                                 * inherited priority wins.
+                                 */
+                                if (!second_task->rt_param.inh_task) {
+                                        return 1;
+                                }
                         }
-
                 }
         }
 
-        return false;
+        return 0; /* fall-through. prio(second_task) > prio(first_task) */
 }