IKGLP virtual unlock and MAJOR BUG FIX

Fixed a major bug where a scheduled task with
and exhausted budget does not recheck its priority
inheritance upon deadline postponement. Postponment
may enable priority inheritance relations, as the
priority of the lock holder decreases.

4 files changed, 287 insertions, 123 deletions

diff --git a/include/litmus/ikglp_lock.h b/include/litmus/ikglp_lock.h
index d81b755b9039..954597fc927d 100644
--- a/include/litmus/ikglp_lock.h
+++ b/include/litmus/ikglp_lock.h
@@ -73,6 +73,15 @@ struct fifo_queue
         unsigned int count; /* number of waiters + holder */
 
         struct nested_info nest;
+
+        /* Asserted if owner has 'virtually' unlocked the FIFO's replica.
+         * See rule B2 in Brandenburg's "Virtually Exclusive Resources"
+         * tech report MPI_SWS-2012-005.
+         *
+         * In this implementation, allows the FIFO queue to temporarily
+         * grow by one past it's maximum size.
+         */
+        unsigned int is_vunlocked:1;
 };
 
 struct ikglp_semaphore
diff --git a/litmus/budget.c b/litmus/budget.c
index aa254349a85e..f7d690c77226 100644
--- a/litmus/budget.c
+++ b/litmus/budget.c
@@ -183,7 +183,8 @@ void sobliv_on_blocked(struct task_struct* t)
                          * trigger another exhaustion signal since signals are controled by
                          * BTF_SIG_BUDGET_SENT. */
                         int exhausted = bt_flag_test_and_clear(t, BTF_BUDGET_EXHAUSTED);
-                        BUG_ON(!exhausted);
+                        //BUG_ON(!exhausted);
+                        WARN_ON(!exhausted);
 
                         TRACE_TASK(t, "budget timer not armed. "
                                            "Raced with exhaustion-resched? Re-arming.\n");
@@ -317,12 +318,6 @@ void sobliv_revaluate_task(struct task_struct* t)
                            "on Litmus lock without "
                            "CONFIG_LITMUS_NESTED_LOCKING enabled.\n");
 #endif
-
-        /* Move a waiter onto a FIFO queue to simulate an unlock call. */
-        if (tsk_rt(t)->outermost_lock &&
-                tsk_rt(t)->outermost_lock->ops->is_omlp_family) {
-                tsk_rt(t)->outermost_lock->ops->omlp_virtual_unlock(tsk_rt(t)->outermost_lock, t);
-        }
 }
 
 
diff --git a/litmus/ikglp_lock.c b/litmus/ikglp_lock.c
index 3058aa8fb2fe..d9c263eee34a 100644
--- a/litmus/ikglp_lock.c
+++ b/litmus/ikglp_lock.c
@@ -77,6 +77,10 @@ int ikglp_min_heap_donee_order(struct binheap_node *a,
 }
 
 
+static inline unsigned int nominal_fq_len(struct fifo_queue *fq)
+{
+        return (fq->count - fq->is_vunlocked);
+}
 
 static inline int ikglp_get_idx(struct ikglp_semaphore *sem,
                                                                 struct fifo_queue *queue)
@@ -122,8 +126,9 @@ static struct fifo_queue* ikglp_find_shortest(struct ikglp_semaphore *sem,
 
         do {
                 step = (step+1 != &sem->fifo_queues[sem->nr_replicas]) ?
-                step+1 : &sem->fifo_queues[0];
+                        step+1 : &sem->fifo_queues[0];
 
+                /* consider actual lengths, not nominal lengths */
                 if(step->count < shortest->count) {
                         shortest = step;
                         if(step->count == 0)
@@ -195,10 +200,11 @@ static void __ikglp_dump_donors(struct binheap_node *n, int depth)
 
 static void __ikglp_dump_fifoq(int i, struct fifo_queue* fq)
 {
-        TRACE("    FIFO %d: Owner = %s/%d, HP Waiter = %s/%d, # Waiters = %u\n",
+        TRACE("    FIFO %d: Owner = %s/%d (Virtually Unlocked = %u),  HP Waiter = %s/%d,  Length = %u\n",
                   i,
                   (fq->owner) ? fq->owner->comm : "null",
                   (fq->owner) ? fq->owner->pid : 0,
+                  fq->is_vunlocked,
                   (fq->hp_waiter) ? fq->hp_waiter->comm : "null",
                   (fq->hp_waiter) ? fq->hp_waiter->pid : 0,
                   fq->count);
@@ -1395,11 +1401,16 @@ void ikglp_grant_replica_to_next(struct ikglp_semaphore *sem, struct fifo_queue
 }
 
 
+#define ALLOW_STEALING                          1
+#define ALWAYS_TERMINATE_DONATION       1
+
 void ikglp_move_next_to_fq(struct ikglp_semaphore *sem,
                                                    struct fifo_queue *fq,
                                                    struct task_struct *t,
                                                    ikglp_donee_heap_node_t *donee_node,
-                                                   int allow_stealing)
+                                                   unsigned long *flags,
+                                                   int allow_stealing,
+                                                   int always_terminate_donation)
 {
         struct task_struct *donee = NULL;
         struct task_struct *new_on_fq = NULL;
@@ -1408,7 +1419,6 @@ void ikglp_move_next_to_fq(struct ikglp_semaphore *sem,
         ikglp_wait_state_t *other_donor_info = NULL;
         struct fifo_queue *to_steal = NULL;
         int need_steal_prio_reeval = 0;
-        unsigned long flags = 0;
 
         if (donee_node->donor_info) {
                 ikglp_wait_state_t *donor_info = donee_node->donor_info;
@@ -1421,7 +1431,7 @@ void ikglp_move_next_to_fq(struct ikglp_semaphore *sem,
 #ifdef CONFIG_LITMUS_AFFINITY_LOCKING
                 if(sem->aff_obs) {
                         fq_of_new_on_fq = sem->aff_obs->ops->advise_enqueue(sem->aff_obs, new_on_fq);
-                        if((fq_of_new_on_fq->count >= sem->max_fifo_len) && !sem->aff_obs->relax_max_fifo_len) {
+                        if((nominal_fq_len(fq_of_new_on_fq) >= sem->max_fifo_len) && !sem->aff_obs->relax_max_fifo_len) {
                                 WARN_ON(1);
                                 fq_of_new_on_fq = fq;
                         }
@@ -1438,6 +1448,11 @@ void ikglp_move_next_to_fq(struct ikglp_semaphore *sem,
                                    ikglp_get_idx(sem, fq));
 
                 ikglp_move_donor_to_fq(sem, fq_of_new_on_fq, donor_info);
+
+                /* treat donor as if it had donated to a task other than 't'.
+                 * this triggers the termination of the donation relationship. */
+                if (always_terminate_donation)
+                        other_donor_info = donor_info;
         }
         else if(!binheap_empty(&sem->donors)) {  // No donor, so move any donor to FQ
                                                                                          // Select a donor
@@ -1459,7 +1474,7 @@ void ikglp_move_next_to_fq(struct ikglp_semaphore *sem,
 #ifdef CONFIG_LITMUS_AFFINITY_LOCKING
                 if(sem->aff_obs) {
                         fq_of_new_on_fq = sem->aff_obs->ops->advise_enqueue(sem->aff_obs, new_on_fq);
-                        if((fq_of_new_on_fq->count >= sem->max_fifo_len) && !sem->aff_obs->relax_max_fifo_len) {
+                        if((nominal_fq_len(fq_of_new_on_fq) >= sem->max_fifo_len) && !sem->aff_obs->relax_max_fifo_len) {
                                 WARN_ON(1);
                                 fq_of_new_on_fq = fq;
                         }
@@ -1488,7 +1503,7 @@ void ikglp_move_next_to_fq(struct ikglp_semaphore *sem,
 #ifdef CONFIG_LITMUS_AFFINITY_LOCKING
                 if(sem->aff_obs) {
                         fq_of_new_on_fq = sem->aff_obs->ops->advise_enqueue(sem->aff_obs, new_on_fq);
-                        if((fq_of_new_on_fq->count >= sem->max_fifo_len) && !sem->aff_obs->relax_max_fifo_len) {
+                        if((nominal_fq_len(fq_of_new_on_fq) >= sem->max_fifo_len) && !sem->aff_obs->relax_max_fifo_len) {
                                 WARN_ON(1);
                                 fq_of_new_on_fq = fq;
                         }
@@ -1556,7 +1571,7 @@ void ikglp_move_next_to_fq(struct ikglp_semaphore *sem,
                 struct fifo_queue *other_fq = other_donor_info->donee_info->fq;
 
                 BUG_ON(!donee);
-                BUG_ON(donee == t);
+                BUG_ON(!always_terminate_donation && donee == t);
 
                 TRACE_TASK(t, "Terminating donation relation of donor %s/%d to donee %s/%d!\n",
                                    other_donor_info->task->comm, other_donor_info->task->pid,
@@ -1568,8 +1583,8 @@ void ikglp_move_next_to_fq(struct ikglp_semaphore *sem,
                                            donee->comm, donee->pid,
                                            ikglp_get_idx(sem, other_fq));
 
-                        ikglp_remove_donation_from_owner(&other_donor_info->prio_donation.hp_binheap_node, other_fq, sem, flags);
-                        lock_fine_irqsave(&sem->lock, flags);  // there should be no contention!!!!
+                        ikglp_remove_donation_from_owner(&other_donor_info->prio_donation.hp_binheap_node, other_fq, sem, *flags);
+                        lock_fine_irqsave(&sem->lock, *flags);  // there should be no contention!!!!
                 }
                 else {
                         TRACE_TASK(t, "Donee %s/%d is blocked in of fq %d.\n",
@@ -1588,8 +1603,8 @@ void ikglp_move_next_to_fq(struct ikglp_semaphore *sem,
                                                    (other_fq->hp_waiter) ? other_fq->hp_waiter->comm : "null",
                                                    (other_fq->hp_waiter) ? other_fq->hp_waiter->pid : 0);
 
-                                ikglp_refresh_owners_prio_decrease(other_fq, sem, flags, 0); // unlocks sem->lock.  reacquire it.
-                                lock_fine_irqsave(&sem->lock, flags);  // there should be no contention!!!!
+                                ikglp_refresh_owners_prio_decrease(other_fq, sem, *flags, 0); // unlocks sem->lock.  reacquire it.
+                                lock_fine_irqsave(&sem->lock, *flags);  // there should be no contention!!!!
                         }
                 }
         }
@@ -1598,15 +1613,15 @@ void ikglp_move_next_to_fq(struct ikglp_semaphore *sem,
                                    ikglp_get_idx(sem, to_steal));
 
                 if(need_steal_prio_reeval) {
-                        ikglp_refresh_owners_prio_decrease(to_steal, sem, flags, 0); // unlocks sem->lock.  reacquire it.
-                        lock_fine_irqsave(&sem->lock, flags);  // there should be no contention!!!!
+                        ikglp_refresh_owners_prio_decrease(to_steal, sem, *flags, 0); // unlocks sem->lock.  reacquire it.
+                        lock_fine_irqsave(&sem->lock, *flags);  // there should be no contention!!!!
                 }
         }
 
         // check for new HP waiter.
         if(new_on_fq) {
-                ikglp_refresh_owners_prio_increase(new_on_fq, fq_of_new_on_fq, sem, flags); // unlocks sem->lock.  reacquire it.
-                lock_fine_irqsave(&sem->lock, flags);  // there should be no contention!!!!
+                ikglp_refresh_owners_prio_increase(new_on_fq, fq_of_new_on_fq, sem, *flags); // unlocks sem->lock.  reacquire it.
+                lock_fine_irqsave(&sem->lock, *flags);  // there should be no contention!!!!
         }
 
         /* we moved a request to an empty FQ. wake it up */
@@ -1656,7 +1671,11 @@ int ikglp_unlock(struct litmus_lock* l)
         if(fq->count < sem->shortest_fifo_queue->count) {
                 sem->shortest_fifo_queue = fq;
         }
-        --(sem->nr_in_fifos);
+
+        if (likely(!fq->is_vunlocked))
+                --(sem->nr_in_fifos);
+        else
+                TRACE_TASK(t, "virtually unlocked. handing off replica only.\n");
 
 #ifdef CONFIG_LITMUS_AFFINITY_LOCKING
         if(sem->aff_obs) {
@@ -1687,9 +1706,14 @@ int ikglp_unlock(struct litmus_lock* l)
         }
         raw_spin_unlock(&tsk_rt(t)->hp_blocked_tasks_lock);
 
-        // Move the next request into the FQ and update heaps as needed.
-        // We defer re-evaluation of priorities to later in the function.
-        ikglp_move_next_to_fq(sem, fq, t, &fq->donee_heap_node, 1);
+        if (likely(!fq->is_vunlocked)) {
+                // Move the next request into the FQ and update heaps as needed.
+                // Skip this step we already did this during the virtual unlock.
+                ikglp_move_next_to_fq(sem, fq, t, &fq->donee_heap_node, &flags,
+                                                ALLOW_STEALING, !ALWAYS_TERMINATE_DONATION);
+        }
+        else
+                fq->is_vunlocked = 0; /* reset vunlock flag */
 
         if (waitqueue_active(&fq->wait))
                 ikglp_grant_replica_to_next(sem, fq);
@@ -1755,7 +1779,8 @@ void ikglp_abort_request(struct ikglp_semaphore *sem, struct task_struct *t, uns
 
                         ikglp_refresh_owners_prio_decrease(wait->donee_heap_node.fq, sem, flags, 1); // unlocks sem->lock.  reacquire it.
                         lock_fine_irqsave(&sem->lock, flags);  // there should be no contention!!!!
-                        ikglp_move_next_to_fq(sem, fq, t, &wait->donee_heap_node, 1);
+                        ikglp_move_next_to_fq(sem, fq, t, &wait->donee_heap_node, &flags,
+                                                        ALLOW_STEALING, !ALWAYS_TERMINATE_DONATION);
                         break;
 
 
@@ -1900,7 +1925,51 @@ void ikglp_budget_exhausted(struct litmus_lock* l, struct task_struct* t)
 
 void ikglp_virtual_unlock(struct litmus_lock* l, struct task_struct* t)
 {
-        TRACE_TASK(t, "TODO!\n");
+        /* PRE: DGL lock already held if DGLs are supported */
+
+        struct ikglp_semaphore *sem = ikglp_from_lock(l);
+        struct fifo_queue *fq = ikglp_get_queue(sem, t);
+        unsigned long flags = 0, more_flags;
+
+        TRACE_TASK(t, "virtual unlock!\n");
+
+        if (!fq)
+                return;
+
+        if (fq->is_vunlocked) {
+                TRACE_TASK(t, "Lock %d already virtually unlocked.\n", l->ident);
+                return;
+        }
+
+        raw_spin_lock_irqsave(&sem->real_lock, more_flags);
+        lock_fine_irqsave(&sem->lock, flags);
+
+        if (unlikely(fq->owner != t)) {
+                TRACE_TASK(t, "no longer holds lock %d.\n", l->ident);
+                goto out;
+        }
+
+        TRACE_TASK(t, "IKGLP before virtual unlock:\n");
+        __ikglp_dump_state(sem);
+
+        /* Move a request from donor heap or PQ to fq. don't steal from
+         * other FQs.  Also, terminate donation relationship if we move
+         * a donor to 't' to the FQ (we'll pick inheritance back up via
+         * the FQ, if needed). */
+        ikglp_move_next_to_fq(sem, fq, t, &fq->donee_heap_node, &flags,
+                                        !ALLOW_STEALING, ALWAYS_TERMINATE_DONATION);
+
+        /* decrement fifo count to simulate unlock. individual fifo
+         * length counts remain unchanged. */
+        --(sem->nr_in_fifos);
+        fq->is_vunlocked = 1;
+
+        TRACE_TASK(t, "IKGLP after virtual unlock:\n");
+        __ikglp_dump_state(sem);
+
+out:
+        unlock_fine_irqrestore(&sem->lock, flags);
+        raw_spin_unlock_irqrestore(&sem->real_lock, more_flags);
 }
 
 
@@ -2030,6 +2099,7 @@ struct litmus_lock* ikglp_new(unsigned int m,
                 q->hp_waiter = NULL;
                 init_waitqueue_head(&q->wait);
                 q->count = 0;
+                q->is_vunlocked = 0;
 
                 q->global_heap_node.task = NULL;
                 INIT_BINHEAP_NODE(&q->global_heap_node.node);
@@ -2316,7 +2386,8 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
 
         for(i = 0; i < sem->nr_replicas; ++i) {
                 if(&aff->q_info[i] != shortest) {
-                        if(aff->q_info[i].q->count < max_fifo_len) {
+                        /* is there room on this q? */
+                        if(nominal_fq_len(aff->q_info[i].q) < max_fifo_len) {
                                 int want = 0;
 
                                 lt_t migration =
@@ -2335,7 +2406,7 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
                                 // queues "close enough" in length to be considered equal.
 
                                 /* NOTE: 'shortest' starts out with affinity GPU */
-                                if(unlikely(shortest->q->count >= max_fifo_len)) {                                              /* 'shortest' is full and i-th queue is not */
+                                if(unlikely(nominal_fq_len(shortest->q) >= max_fifo_len)) {                     /* 'shortest' is full and i-th queue is not */
                                         want = 1;
                                 }
                                 else if(est_len < min_len) {
@@ -2363,7 +2434,7 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
                                         min_nr_aff_users = *(aff->q_info[i].nr_aff_users);
                                 }
 
-                                TRACE_CUR("cs is %llu on queue %d (count = %d): est len = %llu\n",
+                                TRACE_CUR("cs is %llu on queue %d (count = %u): est len = %llu\n",
                                                   get_gpu_estimate(t,
                                                                 gpu_migration_distance(tsk_rt(t)->last_gpu,
                                                                                                            replica_to_gpu(aff, i))),
@@ -2378,13 +2449,13 @@ struct fifo_queue* gpu_ikglp_advise_enqueue(struct ikglp_affinity* aff, struct t
                 }
         }
 
-        if(shortest->q->count >= max_fifo_len) {
+        if(nominal_fq_len(shortest->q) >= max_fifo_len) {
                 TRACE_CUR("selected fq %d is too long, but returning it anyway.\n",
                                   ikglp_get_idx(sem, shortest->q));
         }
 
         to_enqueue = shortest->q;
-        TRACE_CUR("enqueue on fq %d (count = %d) (non-aff wanted fq %d)\n",
+        TRACE_CUR("enqueue on fq %d (count = %u) (non-aff wanted fq %d)\n",
                           ikglp_get_idx(sem, to_enqueue),
                           to_enqueue->count,
                           ikglp_get_idx(sem, sem->shortest_fifo_queue));
diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c
index 7178b6cd3ba1..879f781cf1aa 100644
--- a/litmus/sched_cedf.c
+++ b/litmus/sched_cedf.c
@@ -703,6 +703,35 @@ static enum hrtimer_restart cedf_simple_on_exhausted(struct task_struct *t)
         return HRTIMER_NORESTART;
 }
 
+
+#ifdef CONFIG_LITMUS_LOCKING
+static void __cedf_trigger_vunlock(struct task_struct *t)
+{
+        TRACE_TASK(t, "triggering virtual unlock of lock %d\n",
+                                        tsk_rt(t)->outermost_lock->ident);
+        tsk_rt(t)->outermost_lock->ops->omlp_virtual_unlock(tsk_rt(t)->outermost_lock, t);
+}
+
+static void cedf_trigger_vunlock(struct task_struct *t)
+{
+        cedf_domain_t *cluster = task_cpu_cluster(t);
+#ifdef CONFIG_LITMUS_DGL_SUPPORT
+        unsigned long flags;
+
+        /* Unfortunately, we _might_ need to grab the DGL lock, so we
+         * must grab it every time since it must be take before the
+         * cluster lock. */
+        raw_spin_lock_irqsave(&cluster->dgl_lock, flags);
+#endif
+
+        __cedf_trigger_vunlock(t);
+
+#ifdef CONFIG_LITMUS_DGL_SUPPORT
+        raw_spin_unlock_irqrestore(&cluster->dgl_lock, flags);
+#endif
+}
+#endif
+
 static enum hrtimer_restart cedf_sobliv_on_exhausted(struct task_struct *t)
 {
         enum hrtimer_restart restart = HRTIMER_NORESTART;
@@ -719,126 +748,136 @@ static enum hrtimer_restart cedf_sobliv_on_exhausted(struct task_struct *t)
         }
 
         if (budget_enforced(t) && !bt_flag_is_set(t, BTF_BUDGET_EXHAUSTED)) {
+                int cpu = (tsk_rt(t)->linked_on != NO_CPU) ?
+                                tsk_rt(t)->linked_on : tsk_rt(t)->scheduled_on;
+
+#ifdef CONFIG_LITMUS_LOCKING
+                /* if 't' running, trigger a virtual unlock of outermost held lock
+                 * if supported. Case where 't' not running handled later in function.
+                 */
+                if (cpu != NO_CPU &&
+                        tsk_rt(t)->outermost_lock &&
+                        tsk_rt(t)->outermost_lock->ops->is_omlp_family)
+                                cedf_trigger_vunlock(t);
+#endif
+
                 if (is_np(t) && is_user_np(t)) {
                         TRACE_TASK(t, "is non-preemptable, preemption delayed.\n");
                         bt_flag_set(t, BTF_BUDGET_EXHAUSTED);
                         request_exit_np(t);
                 }
+                /* where do we need to call resched? */
+                else if (cpu == smp_processor_id()) {
+                        TRACE_TASK(t, "is preemptable => FORCE_RESCHED\n");
+                        bt_flag_set(t, BTF_BUDGET_EXHAUSTED);
+                        litmus_reschedule_local();
+                        set_will_schedule();
+                }
+                else if (cpu != NO_CPU) {
+                        TRACE_TASK(t, "is preemptable on remote cpu (%d) => FORCE_RESCHED\n", cpu);
+                        bt_flag_set(t, BTF_BUDGET_EXHAUSTED);
+                        litmus_reschedule(cpu);
+                }
                 else {
-                        /* where do we need to call resched? */
-                        int cpu = (tsk_rt(t)->linked_on != NO_CPU) ?
-                                tsk_rt(t)->linked_on : tsk_rt(t)->scheduled_on;
-                        if (cpu == smp_processor_id()) {
-                                TRACE_TASK(t, "is preemptable => FORCE_RESCHED\n");
+                        lt_t remaining;
+                        cedf_domain_t *cluster;
+                        unsigned long flags;
 
-                                bt_flag_set(t, BTF_BUDGET_EXHAUSTED);
-                                litmus_reschedule_local();
-                                set_will_schedule();
-                        }
-                        else if (cpu != NO_CPU) {
-                                TRACE_TASK(t, "is preemptable on remote cpu (%d) => FORCE_RESCHED\n", cpu);
+                        cluster = task_cpu_cluster(t);
 
-                                bt_flag_set(t, BTF_BUDGET_EXHAUSTED);
-                                litmus_reschedule(cpu);
-                        }
-                        else {
-                                lt_t remaining;
-                                cedf_domain_t* cluster = task_cpu_cluster(t);
-                                unsigned long flags;
-
-                                BUG_ON(cpu != NO_CPU);
-
-                                // 1) refresh budget through job completion
-                                // 2) if holds locks, tell the locking protocol to re-eval priority
-                                // 3) -- the LP must undo any inheritance relations if appropriate
+                        // 1) refresh budget through job completion
+                        // 2) if holds locks, tell the locking protocol to re-eval priority
+                        // 3) -- the LP must undo any inheritance relations if appropriate
 
-                                /* force job completion */
-                                TRACE_TASK(t, "blocked, postponing deadline\n");
+                        /* force job completion */
+                        TRACE_TASK(t, "blocked, postponing deadline\n");
 
-                                /* Outermost lock of the cluster. Recursive lock calls are
-                                 * possible on this code path. This should be the _ONLY_
-                                 * scenario where recursive calls are made. */
+                        /* Outermost lock of the cluster. Recursive lock calls are
+                         * possible on this code path. This should be the _ONLY_
+                         * scenario where recursive calls are made. */
 #ifdef CONFIG_LITMUS_DGL_SUPPORT
-                                /* Unfortunately, we _might_ need to grab the DGL lock, so we
-                                 * must grab it every time since it must be take before the
-                                 * cluster lock. */
-                                raw_spin_lock_irqsave(&cluster->dgl_lock, flags);
-                                raw_readyq_lock(&cluster->cluster_lock);
+                        /* Unfortunately, we _might_ need to grab the DGL lock, so we
+                         * must grab it every time since it must be take before the
+                         * cluster lock. */
+                        raw_spin_lock_irqsave(&cluster->dgl_lock, flags);
+                        raw_readyq_lock(&cluster->cluster_lock);
 #else
-                                raw_readyq_lock_irqsave(&cluster->cluster_lock, flags);
+                        raw_readyq_lock_irqsave(&cluster->cluster_lock, flags);
 #endif
 
-                                job_completion(t, 1); /* refreshes budget and pushes out deadline */
+                        job_completion(t, 1); /* refreshes budget and pushes out deadline */
 
 #ifdef CONFIG_LITMUS_LOCKING
+                        {
+                                int i;
+                                /* any linked task that inherits from 't' needs to have their
+                                 * cpu-position re-evaluated. we have to do this in two passes.
+                                 * pass 1: remove nodes from heap s.t. heap is in known good state.
+                                 * pass 2: re-add nodes.
+                                 *
+                                 */
+                                for (i = find_first_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots));
+                                         i < BITS_PER_LONG;
+                                         i = find_next_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots), i+1))
                                 {
-                                        int i;
-                                        /* any linked task that inherits from 't' needs to have their
-                                         * cpu-position re-evaluated. we have to do this in two passes.
-                                         * pass 1: remove nodes from heap s.t. heap is in known good state.
-                                         * pass 2: re-add nodes.
-                                         *
-                                         */
-                                        for (i = find_first_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots));
-                                                 i < BITS_PER_LONG;
-                                                 i = find_next_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots), i+1))
-                                        {
-                                                struct task_struct *to_update = tsk_rt(t)->inh_task_linkbacks[i];
-                                                BUG_ON(!to_update);
-                                                if (tsk_rt(to_update)->linked_on != NO_CPU) {
-                                                        cpu_entry_t *entry = &per_cpu(cedf_cpu_entries, tsk_rt(to_update)->linked_on);
-                                                        BUG_ON(!binheap_is_in_heap(&entry->hn));
-                                                        binheap_delete(&entry->hn, &cluster->cpu_heap);
-                                                }
+                                        struct task_struct *to_update = tsk_rt(t)->inh_task_linkbacks[i];
+                                        BUG_ON(!to_update);
+                                        if (tsk_rt(to_update)->linked_on != NO_CPU) {
+                                                cpu_entry_t *entry = &per_cpu(cedf_cpu_entries, tsk_rt(to_update)->linked_on);
+                                                BUG_ON(!binheap_is_in_heap(&entry->hn));
+                                                binheap_delete(&entry->hn, &cluster->cpu_heap);
                                         }
-                                        for (i = find_first_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots));
-                                                 i < BITS_PER_LONG;
-                                                 i = find_next_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots), i+1))
-                                        {
-                                                struct task_struct *to_update = tsk_rt(t)->inh_task_linkbacks[i];
-                                                BUG_ON(!to_update);
-                                                if (tsk_rt(to_update)->linked_on != NO_CPU) {
-                                                        cpu_entry_t *entry = &per_cpu(cedf_cpu_entries, tsk_rt(to_update)->linked_on);
-                                                        binheap_add(&entry->hn, &cluster->cpu_heap, cpu_entry_t, hn);
-                                                }
+                                }
+                                for (i = find_first_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots));
+                                         i < BITS_PER_LONG;
+                                         i = find_next_bit(&tsk_rt(t)->used_linkback_slots, BITS_PER_BYTE*sizeof(&tsk_rt(t)->used_linkback_slots), i+1))
+                                {
+                                        struct task_struct *to_update = tsk_rt(t)->inh_task_linkbacks[i];
+                                        BUG_ON(!to_update);
+                                        if (tsk_rt(to_update)->linked_on != NO_CPU) {
+                                                cpu_entry_t *entry = &per_cpu(cedf_cpu_entries, tsk_rt(to_update)->linked_on);
+                                                binheap_add(&entry->hn, &cluster->cpu_heap, cpu_entry_t, hn);
                                         }
                                 }
+                        }
 
-                                /* Check our inheritance and propagate any changes forward. */
-                                sobliv_revaluate_task(t);
+                        /* Check our inheritance and propagate any changes forward. */
+                        sobliv_revaluate_task(t);
+
+                        if (tsk_rt(t)->outermost_lock && tsk_rt(t)->outermost_lock->ops->is_omlp_family)
+                                __cedf_trigger_vunlock(t);
 #endif
-                                /* No need to recheck priority of AUX tasks. They will always
-                                 * inherit from 't' if they are enabled. Their prio change was
-                                 * captured by the cpu-heap operations above. */
+                        /* No need to recheck priority of AUX tasks. They will always
+                         * inherit from 't' if they are enabled. Their prio change was
+                         * captured by the cpu-heap operations above. */
 
 #ifdef CONFIG_LITMUS_NVIDIA
-                                /* Re-eval priority of GPU interrupt threads. */
-                                if(tsk_rt(t)->held_gpus && !tsk_rt(t)->hide_from_gpu)
-                                        recheck_gpu_owner(t);
+                        /* Re-eval priority of GPU interrupt threads. */
+                        if(tsk_rt(t)->held_gpus && !tsk_rt(t)->hide_from_gpu)
+                                recheck_gpu_owner(t);
 #endif
 
 #ifdef CONFIG_LITMUS_LOCKING
-                                /* double-check that everything is okay */
-                                check_for_preemptions(cluster);
+                        /* double-check that everything is okay */
+                        check_for_preemptions(cluster);
 #endif
 
-                                /* should be the outermost unlock call */
+                        /* should be the outermost unlock call */
 #ifdef CONFIG_LITMUS_DGL_SUPPORT
-                                raw_readyq_unlock(&cluster->cluster_lock);
-                                raw_spin_unlock_irqrestore(&cluster->dgl_lock, flags);
+                        raw_readyq_unlock(&cluster->cluster_lock);
+                        raw_spin_unlock_irqrestore(&cluster->dgl_lock, flags);
 #else
-                                raw_readyq_unlock_irqrestore(&cluster->cluster_lock, flags);
+                        raw_readyq_unlock_irqrestore(&cluster->cluster_lock, flags);
 #endif
 
-                                /* we need to set up the budget timer since we're within the callback. */
-                                if (bt_flag_is_set(t, BTF_IS_TOP_M)) {
-                                        hrtimer_forward_now(&get_budget_timer(t).timer.timer,
-                                                                                ns_to_ktime(budget_remaining(t)));
-                                        remaining = hrtimer_get_expires_ns(&get_budget_timer(t).timer.timer);
+                        /* we need to set up the budget timer since we're within the callback. */
+                        if (bt_flag_is_set(t, BTF_IS_TOP_M)) {
+                                hrtimer_forward_now(&get_budget_timer(t).timer.timer,
+                                                                        ns_to_ktime(budget_remaining(t)));
+                                remaining = hrtimer_get_expires_ns(&get_budget_timer(t).timer.timer);
 
-                                        TRACE_TASK(t, "rearmed timer to %ld\n", remaining);
-                                        restart = HRTIMER_RESTART;
-                                }
+                                TRACE_TASK(t, "rearmed timer to %ld\n", remaining);
+                                restart = HRTIMER_RESTART;
                         }
                 }
         }
@@ -1160,6 +1199,9 @@ static void cedf_change_prio_pai_tasklet(struct task_struct *old_prio,
 
 #endif  // PAI
 
+#ifdef CONFIG_LITMUS_LOCKING
+static int __increase_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh);
+#endif
 
 /* Getting schedule() right is a bit tricky. schedule() may not make any
  * assumptions on the state of the current task since it may be called for a
@@ -1189,6 +1231,10 @@ static struct task_struct* cedf_schedule(struct task_struct * prev)
         int out_of_time, sleep, preempt, np, exists, blocks;
         struct task_struct* next = NULL;
 
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+        int recheck_inheritance;
+#endif
+
 #ifdef CONFIG_RELEASE_MASTER
         /* Bail out early if we are the release master.
          * The release master never schedules any real-time tasks.
@@ -1199,6 +1245,27 @@ static struct task_struct* cedf_schedule(struct task_struct * prev)
         }
 #endif
 
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+        /* prevent updates to inheritance relations while we work with 'prev' */
+        /* recheck inheritance if the task holds locks, is running, and will
+         * have its deadline pushed out by job_completion() */
+        recheck_inheritance =
+                        (prev != NULL) &&
+                        is_realtime(prev) &&
+                        holds_locks(prev) &&
+                        !is_np(prev) &&
+                        !is_completed(prev) &&
+                        is_running(prev) &&
+                        budget_enforced(prev) &&
+                        bt_flag_is_set(prev, BTF_BUDGET_EXHAUSTED);
+        if (recheck_inheritance) {
+#ifdef CONFIG_LITMUS_DGL_SUPPORT
+                raw_spin_lock(&cluster->dgl_lock);
+#endif
+                raw_spin_lock(&tsk_rt(prev)->hp_blocked_tasks_lock);
+        }
+#endif
+
         raw_readyq_lock(&cluster->cluster_lock);
         clear_will_schedule();
 
@@ -1223,7 +1290,7 @@ static struct task_struct* cedf_schedule(struct task_struct * prev)
 
         if (exists) {
                 TRACE_TASK(prev,
-                           "blocks:%d out_of_time:%d np:%d sleep:%d preempt:%d "
+                           "blocks:%d out_of_time:%d np:%d completed:%d preempt:%d "
                            "state:%d sig:%d\n",
                            blocks, out_of_time, np, sleep, preempt,
                            prev->state, signal_pending(prev));
@@ -1284,8 +1351,22 @@ static struct task_struct* cedf_schedule(struct task_struct * prev)
          * this. Don't do a job completion if we block (can't have timers running
          * for blocked jobs).
          */
-        if (!np && (out_of_time || sleep) && !blocks)
+        if (!np && (out_of_time || sleep) && !blocks) {
                 job_completion(entry->scheduled, !sleep);
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+                /* check if job completion enables an inheritance relation. no need to
+                 * recheck if task already inherits a priority since job_completion()
+                 * will not enable a higher-prio relation */
+                if (unlikely(recheck_inheritance && !tsk_rt(entry->scheduled)->inh_task)) {
+                        struct task_struct *hp_blocked;
+                        TRACE_TASK(entry->scheduled, "rechecking inheritance.\n");
+                        hp_blocked = top_priority(&tsk_rt(entry->scheduled)->hp_blocked_tasks);
+                        /* hp_blocked_tasks_lock is held */
+                        if (edf_higher_prio(hp_blocked, entry->scheduled))
+                                __increase_priority_inheritance(entry->scheduled, effective_priority(hp_blocked));
+                }
+#endif
+        }
 
         /* Link pending task if we became unlinked.
          */
@@ -1317,7 +1398,6 @@ static struct task_struct* cedf_schedule(struct task_struct * prev)
                 }
         }
 
-
 #ifdef CONFIG_REALTIME_AUX_TASKS
 out_set_state:
 #endif
@@ -1325,6 +1405,15 @@ out_set_state:
         sched_state_task_picked();
         raw_readyq_unlock(&cluster->cluster_lock);
 
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+        if (recheck_inheritance) {
+                raw_spin_unlock(&tsk_rt(prev)->hp_blocked_tasks_lock);
+#ifdef CONFIG_LITMUS_DGL_SUPPORT
+                raw_spin_unlock(&cluster->dgl_lock);
+#endif
+        }
+#endif
+
 #ifdef WANT_ALL_SCHED_EVENTS
         TRACE("cluster_lock released, next=0x%p\n", next);