Litmus core: support tie-breaking in priority queue

We'd like to have consistent deadline tie-breaking
in priority-ordered wait queues, too.

2 files changed, 17 insertions, 2 deletions

diff --git a/include/litmus/wait.h b/include/litmus/wait.h
index ab3770904b1f..ce1347c355f8 100644
--- a/include/litmus/wait.h
+++ b/include/litmus/wait.h
@@ -9,6 +9,8 @@ struct __prio_wait_queue {
 
         /* some priority point */
         lt_t priority;
+        /* break ties in priority by lower tie_breaker */
+        unsigned int tie_breaker;
 };
 
 typedef struct __prio_wait_queue prio_wait_queue_t;
@@ -18,7 +20,18 @@ static inline void init_prio_waitqueue_entry(prio_wait_queue_t *pwq,
                                              lt_t priority)
 {
         init_waitqueue_entry(&pwq->wq, t);
-        pwq->priority = priority;
+        pwq->priority    = priority;
+        pwq->tie_breaker = 0;
+}
+
+static inline void init_prio_waitqueue_entry_tie(prio_wait_queue_t *pwq,
+                                                 struct task_struct* t,
+                                                 lt_t priority,
+                                                 unsigned int tie_breaker)
+{
+        init_waitqueue_entry(&pwq->wq, t);
+        pwq->priority    = priority;
+        pwq->tie_breaker = tie_breaker;
 }
 
 unsigned int __add_wait_queue_prio_exclusive(
diff --git a/litmus/locking.c b/litmus/locking.c
index 6ceaf2e9d0a2..2db2c2813c0b 100644
--- a/litmus/locking.c
+++ b/litmus/locking.c
@@ -152,7 +152,9 @@ unsigned int __add_wait_queue_prio_exclusive(
                 prio_wait_queue_t* queued = list_entry(pos, prio_wait_queue_t,
                                                        wq.task_list);
 
-                if (unlikely(lt_before(new->priority, queued->priority))) {
+                if (unlikely(lt_before(new->priority, queued->priority) ||
+                             (new->priority == queued->priority &&
+                              new->tie_breaker < queued->tie_breaker))) {
                         /* pos is not less than new, thus insert here */
                         __list_add(&new->wq.task_list, pos->prev, pos);
                         goto out;