Nested inheritance with fine-grained locking.

Minor hack to lockdep was required too allow
the inheritance propagation locking logic to
work.

1 files changed, 565 insertions, 176 deletions

diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index 6edcc339ea5e..99c93ae65e06 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -638,11 +638,17 @@ static void gsnedf_task_exit(struct task_struct * t)
 
 static long gsnedf_admit_task(struct task_struct* tsk)
 {
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+        INIT_BINHEAP_HANDLE(&tsk_rt(tsk)->hp_blocked_tasks, edf_max_heap_base_priority_order);
+#endif
+        
         return 0;
 }
 
 #ifdef CONFIG_LITMUS_LOCKING
 
+extern raw_spinlock_t rsm_global_lock;
+
 #include <litmus/fdso.h>
 
 /* called with IRQs off */
@@ -653,60 +659,71 @@ static void increase_priority_inheritance(struct task_struct* t, struct task_str
 
         raw_spin_lock(&gsnedf_lock);
 
-        TRACE_TASK(t, "inherits priority from %s/%d\n", prio_inh->comm, prio_inh->pid);
-        tsk_rt(t)->eff_prio = prio_inh;
-
-        linked_on  = tsk_rt(t)->linked_on;
-
-        /* If it is scheduled, then we need to reorder the CPU heap. */
-        if (linked_on != NO_CPU) {
-                TRACE_TASK(t, "%s: linked  on %d\n",
-                           __FUNCTION__, linked_on);
-                /* Holder is scheduled; need to re-order CPUs.
-                 * We can't use heap_decrease() here since
-                 * the cpu_heap is ordered in reverse direction, so
-                 * it is actually an increase. */
-                binheap_delete(&gsnedf_cpus[linked_on]->hn, &gsnedf_cpu_heap);
-                binheap_add(&gsnedf_cpus[linked_on]->hn,
-                                &gsnedf_cpu_heap, cpu_entry_t, hn);
-        } else {
-                /* holder may be queued: first stop queue changes */
-                raw_spin_lock(&gsnedf.release_lock);
-                if (is_queued(t)) {
-                        TRACE_TASK(t, "%s: is queued\n",
-                                   __FUNCTION__);
-                        /* We need to update the position of holder in some
-                         * heap. Note that this could be a release heap if we
-                         * budget enforcement is used and this job overran. */
-                        check_preempt =
-                                !bheap_decrease(edf_ready_order,
-                                               tsk_rt(t)->heap_node);
+        /* this sanity check allows for weaker locking in protocols */
+        if(__edf_higher_prio(prio_inh, BASE, t, INHERITED)) {
+                TRACE_TASK(t, "inherits priority from %s/%d\n", prio_inh->comm, prio_inh->pid);
+                tsk_rt(t)->inh_task = prio_inh;
+
+                linked_on  = tsk_rt(t)->linked_on;
+
+                /* If it is scheduled, then we need to reorder the CPU heap. */
+                if (linked_on != NO_CPU) {
+                        TRACE_TASK(t, "%s: linked  on %d\n",
+                                   __FUNCTION__, linked_on);
+                        /* Holder is scheduled; need to re-order CPUs.
+                         * We can't use heap_decrease() here since
+                         * the cpu_heap is ordered in reverse direction, so
+                         * it is actually an increase. */
+                        binheap_delete(&gsnedf_cpus[linked_on]->hn, &gsnedf_cpu_heap);
+                        binheap_add(&gsnedf_cpus[linked_on]->hn,
+                                        &gsnedf_cpu_heap, cpu_entry_t, hn);
                 } else {
-                        /* Nothing to do: if it is not queued and not linked
-                         * then it is either sleeping or currently being moved
-                         * by other code (e.g., a timer interrupt handler) that
-                         * will use the correct priority when enqueuing the
-                         * task. */
-                        TRACE_TASK(t, "%s: is NOT queued => Done.\n",
-                                   __FUNCTION__);
-                }
-                raw_spin_unlock(&gsnedf.release_lock);
-
-                /* If holder was enqueued in a release heap, then the following
-                 * preemption check is pointless, but we can't easily detect
-                 * that case. If you want to fix this, then consider that
-                 * simply adding a state flag requires O(n) time to update when
-                 * releasing n tasks, which conflicts with the goal to have
-                 * O(log n) merges. */
-                if (check_preempt) {
-                        /* heap_decrease() hit the top level of the heap: make
-                         * sure preemption checks get the right task, not the
-                         * potentially stale cache. */
-                        bheap_uncache_min(edf_ready_order,
-                                         &gsnedf.ready_queue);
-                        check_for_preemptions();
+                        /* holder may be queued: first stop queue changes */
+                        raw_spin_lock(&gsnedf.release_lock);
+                        if (is_queued(t)) {
+                                TRACE_TASK(t, "%s: is queued\n",
+                                           __FUNCTION__);
+                                /* We need to update the position of holder in some
+                                 * heap. Note that this could be a release heap if we
+                                 * budget enforcement is used and this job overran. */
+                                check_preempt =
+                                        !bheap_decrease(edf_ready_order,
+                                                           tsk_rt(t)->heap_node);
+                        } else {
+                                /* Nothing to do: if it is not queued and not linked
+                                 * then it is either sleeping or currently being moved
+                                 * by other code (e.g., a timer interrupt handler) that
+                                 * will use the correct priority when enqueuing the
+                                 * task. */
+                                TRACE_TASK(t, "%s: is NOT queued => Done.\n",
+                                           __FUNCTION__);
+                        }
+                        raw_spin_unlock(&gsnedf.release_lock);
+
+                        /* If holder was enqueued in a release heap, then the following
+                         * preemption check is pointless, but we can't easily detect
+                         * that case. If you want to fix this, then consider that
+                         * simply adding a state flag requires O(n) time to update when
+                         * releasing n tasks, which conflicts with the goal to have
+                         * O(log n) merges. */
+                        if (check_preempt) {
+                                /* heap_decrease() hit the top level of the heap: make
+                                 * sure preemption checks get the right task, not the
+                                 * potentially stale cache. */
+                                bheap_uncache_min(edf_ready_order,
+                                                 &gsnedf.ready_queue);
+                                check_for_preemptions();
+                        }
                 }
         }
+        else {
+                TRACE_TASK(t, "Spurious invalid priority increase. "
+                                      "Inheritance request: %s/%d [eff_prio = %s/%d] to inherit from %s/%d\n"
+                                          "Occurance is likely okay: probably due to (hopefully safe) concurrent priority updates.\n",
+                                   t->comm, t->pid,
+                                   effective_priority(t)->comm, effective_priority(t)->pid,
+                                   prio_inh->comm, prio_inh->pid);
+        }
 
         raw_spin_unlock(&gsnedf_lock);
 }
@@ -715,23 +732,52 @@ static void increase_priority_inheritance(struct task_struct* t, struct task_str
 static void decrease_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh)
 {
         raw_spin_lock(&gsnedf_lock);
-
-        /* A job only stops inheriting a priority when it releases a
-         * resource. Thus we can make the following assumption.*/
-        //BUG_ON(tsk_rt(t)->scheduled_on == NO_CPU);
-
-        if(prio_inh)
-                TRACE_TASK(t, "inherited priority decreased to %s/%d\n", prio_inh->comm, prio_inh->pid);
-        else
-                TRACE_TASK(t, "base priority restored.\n");
+        
+        if(__edf_higher_prio(t, INHERITED, prio_inh, BASE)) {
+                /* A job only stops inheriting a priority when it releases a
+                 * resource. Thus we can make the following assumption.*/
+                if(prio_inh)
+                        TRACE_TASK(t, "inherited priority decreased to %s/%d\n", prio_inh->comm, prio_inh->pid);
+                else
+                        TRACE_TASK(t, "base priority restored.\n");     
                 
-        tsk_rt(t)->eff_prio = prio_inh;
-
-        /* Check if rescheduling is necessary. We can't use heap_decrease()
-         * since the priority was effectively lowered. */
-        unlink(t);
-        gsnedf_job_arrival(t);
+                tsk_rt(t)->inh_task = prio_inh;
+                
+                if(tsk_rt(t)->scheduled_on != NO_CPU) {
+                        TRACE_TASK(t, "is scheduled.\n");       
+                        
+                        /* Check if rescheduling is necessary. We can't use heap_decrease()
+                         * since the priority was effectively lowered. */
+                        unlink(t);
+                        gsnedf_job_arrival(t);
+                }
+                else {
+                        /* task is queued */
+                        raw_spin_lock(&gsnedf.release_lock);
+                        if (is_queued(t)) {
+                                TRACE_TASK(t, "is queued.\n");
+                                
+                                /* decrease in priority, so we have to re-add to binomial heap */
+                                unlink(t);
+                                gsnedf_job_arrival(t);
+                        }
+                        else {
+                                TRACE_TASK(t, "is not in scheduler. Probably on wait queue somewhere.\n");
+                        }
+                        raw_spin_unlock(&gsnedf.release_lock);
+                }
+        }
+        else {
+                TRACE_TASK(t, "Spurious invalid priority decrease. "
+                                   "Inheritance request: %s/%d [eff_prio = %s/%d] to inherit from %s/%d\n"
+                                   "Occurance is likely okay: probably due to (hopefully safe) concurrent priority updates.\n",
+                                   t->comm, t->pid,
+                                   effective_priority(t)->comm, effective_priority(t)->pid,
+                                   (prio_inh) ? prio_inh->comm : "nil",
+                                   (prio_inh) ? prio_inh->pid : -1);
+        }
 
+                
         raw_spin_unlock(&gsnedf_lock);
 }
 
@@ -741,110 +787,113 @@ static void decrease_priority_inheritance(struct task_struct* t, struct task_str
 #ifdef CONFIG_LITMUS_NESTED_LOCKING
 
 
-
-/* called with IRQs off */
-static void nested_increase_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh)
+void print_hp_waiters(struct binheap_node* n, int depth)
 {
-        increase_priority_inheritance(t, prio_inh);  // increase our prio.
+        struct litmus_lock* l;
+        char padding[81] = "                                                                                ";
+        struct task_struct *hp = NULL;
+        struct task_struct *hp_eff = NULL;
+        struct task_struct *node_prio = NULL;
+        
         
-        // beware: recursion
-        if(tsk_rt(t)->blocked_lock &&
-           tsk_rt(t)->blocked_lock->ops->propagate_increase_inheritance) {
-                TRACE_TASK(mutex->hp_waiter, "Inheritor is blocked.  Checking lock %p.", l);
-                tsk_rt(t)->blocked_lock->ops->propagate_increase_inheritance(tsk_rt(t)->blocked_lock, t);
+        if(n == NULL) {
+                TRACE("+-> %p\n", NULL);
+                return;
         }
+        
+        l = binheap_entry(n, struct litmus_lock, hp_binheap_node);
+        
+        if(depth*2 <= 80)
+                padding[depth*2] = '\0';
+        
+        if(*(l->hp_waiter_ptr)) {
+                hp = *(l->hp_waiter_ptr);
+                
+                if(tsk_rt(hp)->inh_task) {
+                        hp_eff = tsk_rt(hp)->inh_task;
+                }
+        }
+        
+        node_prio = l->hp_waiter_eff_prio;
+        
+        TRACE("%s+-> %s/%d [waiter = %s/%d] [waiter's inh = %s/%d] (lock = %d)\n",
+                  padding,
+                  (node_prio) ? node_prio->comm : "nil",
+                  (node_prio) ? node_prio->pid : -1,
+                  (hp) ? hp->comm : "nil",
+                  (hp) ? hp->pid : -1,
+                  (hp_eff) ? hp_eff->comm : "nil",
+                  (hp_eff) ? hp_eff->pid : -1,                    
+                  l->ident);    
+        
+    if(n->left) print_hp_waiters(n->left, depth+1);
+    if(n->right) print_hp_waiters(n->right, depth+1);
 }
 
+
 /* called with IRQs off */
-static void nested_decrease_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh)
+/* preconditions:
+ (1) The 'hp_blocked_tasks_lock' of task 't' is held.
+ (2) The lock 'to_unlock' is held.
+ */
+static void nested_increase_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh, raw_spinlock_t *to_unlock, unsigned long irqflags)
 {
-        decrease_priority_inheritance(t, prio_inh);
-        
-        // beware: recursion
-        if(tsk_rt(t)->blocked_lock && tsk_rt(t)->blocked_lock->ops->propagate_decrease_inheritance) {
-                TRACE_TASK(mutex->hp_waiter, "Inheritor is blocked.  Checking lock %p.", l);
-                tsk_rt(t)->blocked_lock->ops->propagate_decrease_inheritance(tsk_rt(t)->blocked_lock, t);
-        }       
-}
+        struct litmus_lock *blocked_lock = tsk_rt(t)->blocked_lock;
 
+        increase_priority_inheritance(t, prio_inh);  // increase our prio.
 
-void gsnedf_rsm_mutex_propagate_increase_inheritance(struct litmus_lock* l,
-                                                                                                         struct task_struct* t)
-{
-        struct rsm_mutex *mutex = rsm_mutex_from_lock(l);
-        unsigned long flags;
+        raw_spin_unlock(&tsk_rt(t)->hp_blocked_tasks_lock);  // unlock the t's heap.
         
-        spin_lock_irqsave(&mutex->wait.lock, flags);
         
-        if(tsk_rt(t)->blocked_lock == l) {  // prevent race on tsk_rt(t)->blocked
-                if(t != mutex->hp_waiter) {
-                        if(edf_higher_prio(t, mutex->hp_waiter)) {
-                                mutex->hp_waiter = t;
-                                
-                                TRACE_TASK(mutex->hp_waiter, "is new highest-prio waiter by propagation.\n");
-                        }
-                        else {
-                                goto EXIT;  // HP waiter has greater prio than us.  bail out.
-                        }
-                }
+        if(blocked_lock) {
+                if(blocked_lock->ops->propagate_increase_inheritance) {
+                        TRACE_TASK(t, "Inheritor is blocked (...perhaps).  Checking lock %d.\n", blocked_lock->ident);
                 
-                if(edf_higher_prio(mutex->hp_waiter, mutex->owner)) {
-                        struct task_struct* prio = (tsk_rt(t)->eff_prio) ? tsk_rt(t)->eff_prio : t;
-                        
-                        TRACE_TASK(mutex->hp_waiter, "Propagating inheritance to holder of %p.\n", l);
-                        
-                        nested_increase_priority_inheritance(mutex->owner, prio);
+                        // beware: recursion                    
+                        blocked_lock->ops->propagate_increase_inheritance(blocked_lock, t, to_unlock, irqflags);
+                }
+                else {
+                        TRACE_TASK(t, "Inheritor is blocked on lock (%d) that does not support nesting!\n", blocked_lock->ident);
+                        raw_spin_unlock_irqrestore(to_unlock, irqflags);
                 }
         }
-        
-EXIT:
-        
-        spin_unlock_irqrestore(&mutex->wait.lock, flags);
+        else {
+                TRACE_TASK(t, "is not blocked.  No propagation.\n");
+                raw_spin_unlock_irqrestore(to_unlock, irqflags);
+        }
 }
 
-void gsnedf_rsm_mutex_propagate_decrease_inheritance(struct litmus_lock* l,
-                                                                                                         struct task_struct* t)
+/* called with IRQs off */
+/* preconditions:
+ (1) The 'hp_blocked_tasks_lock' of task 't' is held.
+ (2) The lock 'to_unlock' is held.
+ */
+static void nested_decrease_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh, raw_spinlock_t *to_unlock, unsigned long irqflags)
 {
-        struct rsm_mutex *mutex = rsm_mutex_from_lock(l);
-        unsigned long flags;
+        struct litmus_lock *blocked_lock = tsk_rt(t)->blocked_lock;
+        decrease_priority_inheritance(t, prio_inh);
         
-        spin_lock_irqsave(&mutex->wait.lock, flags);
+        raw_spin_unlock(&tsk_rt(t)->hp_blocked_tasks_lock);  // unlock the t's heap.
         
-        if(tsk_rt(t)->blocked_lock == l) {  // prevent race on tsk_rt(t)->blocked
-                if(t == mutex->hp_waiter) {
-                        struct task_struct* prio;
-                        
-                        TRACE_TASK(t, "was highest-prio waiter\n");
-                        /* next has the highest priority --- it doesn't need to
-                         * inherit.  However, we need to make sure that the
-                         * next-highest priority in the queue is reflected in
-                         * hp_waiter. */
-                        mutex->hp_waiter = rsm_mutex_find_hp_waiter(mutex, NULL);
-                        
-                        TRACE_TASK(mutex->hp_waiter, "is new highest-prio waiter\n");
-                        
-                        TRACE_TASK(mutex->hp_waiter, "Propagating inheritance to holder of %p.\n", l);
+        if(blocked_lock) {
+                if(blocked_lock->ops->propagate_decrease_inheritance) { 
+                        TRACE_TASK(t, "Inheritor is blocked (...perhaps).  Checking lock %d.\n", blocked_lock->ident);
                         
-                        
-                        // lower eff_prio of owner to new hp if needed.
-                        if(t == mutex->owner->eff_prio)
-                        {
-                                
-                        }
-                        
-
-                        nested_increase_priority_inheritance(mutex->owner, prio);                       
+                        // beware: recursion
+                        blocked_lock->ops->propagate_decrease_inheritance(blocked_lock, t, to_unlock, irqflags);
+                }       
+                else {
+                        TRACE_TASK(t, "Inheritor is blocked on lock (%p) that does not support nesting!\n", blocked_lock);
+                        raw_spin_unlock_irqrestore(to_unlock, irqflags);
                 }
         }
-        
-        spin_unlock_irqrestore(&mutex->wait.lock, flags);
+        else {
+                TRACE_TASK(t, "is not blocked.  No propagation.\n");
+                raw_spin_unlock_irqrestore(to_unlock, irqflags);
+        }
 }
 
 
-
-
-
-
 /* ******************** RSM MUTEX ********************** */
 
 /* struct for semaphore with priority inheritance */
@@ -858,7 +907,11 @@ struct rsm_mutex {
         struct task_struct *hp_waiter;
     
         /* FIFO queue of waiting tasks -- for now.  time stamp in the future. */
-        wait_queue_head_t wait;
+        wait_queue_head_t       wait;
+        
+        /* we do some nesting within spinlocks, so we can't use the normal
+           sleeplocks found in wait_queue_head_t. */
+        raw_spinlock_t          lock;
 };
 
 static inline struct rsm_mutex* rsm_mutex_from_lock(struct litmus_lock* lock)
@@ -884,30 +937,38 @@ struct task_struct* rsm_mutex_find_hp_waiter(struct rsm_mutex *mutex,
         return found;
 }
 
-
-
+static inline struct task_struct* top_priority(struct binheap_handle* handle) {
+        if(!binheap_empty(handle)) {
+                return (struct task_struct*)(binheap_top_entry(handle, struct litmus_lock, hp_binheap_node)->hp_waiter_eff_prio);
+        }
+        return NULL;
+}
 
 int gsnedf_rsm_mutex_lock(struct litmus_lock* l)
 {
-        struct task_struct* t = current;
+        struct task_struct *t = current;
+        struct task_struct *owner;
         struct rsm_mutex *mutex = rsm_mutex_from_lock(l);
         wait_queue_t wait;
         unsigned long flags;
     
         if (!is_realtime(t))
                 return -EPERM;
-    
-        spin_lock_irqsave(&mutex->wait.lock, flags);
-    
+
+        raw_spin_lock_irqsave(&mutex->lock, flags);
+        //raw_spin_lock_irqsave(&rsm_global_lock, flags);
+        
         if (mutex->owner) {
+                TRACE_TASK(t, "Blocking on lock %d.\n", l->ident);
+                
                 /* resource is not free => must suspend and wait */
+                
+                owner = mutex->owner;
         
                 init_waitqueue_entry(&wait, t);
         
-                // TODO: inheritance propagation from another thread may not finish
-                // before I check local inheritance...
                 tsk_rt(t)->blocked_lock = l;  /* record where we are blocked */
-                mb();
+                mb();  // needed?
                 
                 /* FIXME: interruptible would be nice some day */
                 set_task_state(t, TASK_UNINTERRUPTIBLE);
@@ -916,17 +977,67 @@ int gsnedf_rsm_mutex_lock(struct litmus_lock* l)
         
                 /* check if we need to activate priority inheritance */
                 if (edf_higher_prio(t, mutex->hp_waiter)) {
+                        
+                        struct task_struct *old_max_eff_prio;
+                        struct task_struct *new_max_eff_prio;
+                        struct task_struct *new_prio = NULL;
+                        
+                        if(mutex->hp_waiter)
+                                TRACE_TASK(t, "has higher prio than hp_waiter (%s/%d).\n", mutex->hp_waiter->comm, mutex->hp_waiter->pid);
+                        else
+                                TRACE_TASK(t, "has higher prio than hp_waiter (NIL).\n");
+                        
+                        raw_spin_lock(&tsk_rt(owner)->hp_blocked_tasks_lock);
+                        
+                        //TRACE_TASK(owner, "Heap Before:\n");
+                        //print_hp_waiters(tsk_rt(owner)->hp_blocked_tasks.root, 0);
+                        
+                        old_max_eff_prio = top_priority(&tsk_rt(owner)->hp_blocked_tasks);
+                        
                         mutex->hp_waiter = t;
-                        if (edf_higher_prio(t, mutex->owner)) {
-                                struct task_struct* prio = (tsk_rt(t)->eff_prio) ? tsk_rt(t)->eff_prio : t;
-                                nested_increase_priority_inheritance(mutex->owner, prio);
+                        l->hp_waiter_eff_prio = effective_priority(mutex->hp_waiter);
+                        
+                        binheap_decrease(&l->hp_binheap_node, &tsk_rt(owner)->hp_blocked_tasks);
+                        
+                        //TRACE_TASK(owner, "Heap After:\n");
+                        //print_hp_waiters(tsk_rt(owner)->hp_blocked_tasks.root, 0);                    
+                        
+                        new_max_eff_prio = top_priority(&tsk_rt(owner)->hp_blocked_tasks);
+                        
+                        if(new_max_eff_prio != old_max_eff_prio) {
+                                TRACE_TASK(t, "is new hp_waiter.\n");
+                                
+                                if ((effective_priority(owner) == old_max_eff_prio) ||
+                                        (__edf_higher_prio(new_max_eff_prio, BASE, owner, INHERITED))){
+                                        new_prio = new_max_eff_prio;
+                                }
+                        }
+                        else {
+                                TRACE_TASK(t, "no change in max_eff_prio of heap.\n");
+                        }
+                        
+                        //raw_spin_unlock(&tsk_rt(owner)->hp_blocked_tasks_lock);
+                        
+                        if(new_prio) {
+                                nested_increase_priority_inheritance(owner, new_prio, &mutex->lock, flags);  // unlocks lock.
                         }
+                        else {
+                                raw_spin_unlock(&tsk_rt(owner)->hp_blocked_tasks_lock);
+                                raw_spin_unlock_irqrestore(&mutex->lock, flags);
+                        }
+
+                }
+                else {
+                        TRACE_TASK(t, "no change in hp_waiter.\n");
+                        raw_spin_unlock_irqrestore(&mutex->lock, flags);
                 }
                 
+
                 TS_LOCK_SUSPEND;
         
                 /* release lock before sleeping */
-                spin_unlock_irqrestore(&mutex->wait.lock, flags);
+                //raw_spin_unlock_irqrestore(&rsm_global_lock, flags);          
+                //raw_spin_unlock_irqrestore(&mutex->lock, flags);
         
                 /* We depend on the FIFO order.  Thus, we don't need to recheck
                  * when we wake up; we are guaranteed to have the lock since
@@ -934,44 +1045,99 @@ int gsnedf_rsm_mutex_lock(struct litmus_lock* l)
                  */
         
                 schedule();
-        
+                
                 TS_LOCK_RESUME;
         
                 /* Since we hold the lock, no other task will change
                  * ->owner. We can thus check it without acquiring the spin
                  * lock. */
                 BUG_ON(mutex->owner != t);
+                
+                TRACE_TASK(t, "Acquired lock %d.\n", l->ident);
+                
         } else {
+                TRACE_TASK(t, "Acquired lock %d with no blocking.\n", l->ident);
+                
                 /* it's ours now */
                 mutex->owner = t;
-        
-                nest_lock(l, t);
                 
-                spin_unlock_irqrestore(&mutex->wait.lock, flags);
+                raw_spin_lock(&tsk_rt(mutex->owner)->hp_blocked_tasks_lock);
+                binheap_add(&l->hp_binheap_node, &tsk_rt(t)->hp_blocked_tasks, struct litmus_lock, hp_binheap_node);
+                raw_spin_unlock(&tsk_rt(mutex->owner)->hp_blocked_tasks_lock);
+                
+                raw_spin_unlock_irqrestore(&mutex->lock, flags);
+                //raw_spin_unlock_irqrestore(&rsm_global_lock, flags);
         }
     
         return 0;
 }
 
+
 int gsnedf_rsm_mutex_unlock(struct litmus_lock* l)
 {
         struct task_struct *t = current, *next;
         struct rsm_mutex *mutex = rsm_mutex_from_lock(l);
         unsigned long flags;
+        
+        struct task_struct *old_max_eff_prio;
+        
+        
         int err = 0;
     
-        spin_lock_irqsave(&mutex->wait.lock, flags);
+        raw_spin_lock_irqsave(&mutex->lock, flags);
+        //raw_spin_lock_irqsave(&rsm_global_lock, flags);
+        
     
         if (mutex->owner != t) {
                 err = -EINVAL;
                 goto out;
         }
         
-        /* we lose the benefit of priority inheritance (if any) */
-        if (tsk_rt(t)->local_prio) {
-                nested_decrease_priority_inheritance(t, NULL);  
+        
+        raw_spin_lock(&tsk_rt(t)->hp_blocked_tasks_lock);
+        
+        TRACE_TASK(t, "Freeing lock %d\n", l->ident);
+        //TRACE_TASK(t, "Heap Before:\n");
+        //print_hp_waiters(tsk_rt(t)->hp_blocked_tasks.root, 0);                
+        
+        //old_max_hp_waiter = *(binheap_top_entry(&tsk_rt(t)->hp_blocked_tasks, struct litmus_lock, hp_binheap_node)->hp_waiter_ptr);
+        old_max_eff_prio = top_priority(&tsk_rt(t)->hp_blocked_tasks);  
+        binheap_delete(&l->hp_binheap_node, &tsk_rt(t)->hp_blocked_tasks);
+        
+        //raw_spin_unlock(&tsk_rt(t)->hp_blocked_tasks_lock);
+        
+        //TRACE_TASK(t, "Heap After:\n");
+        //print_hp_waiters(tsk_rt(t)->hp_blocked_tasks.root, 0);                
+        
+        if(tsk_rt(t)->inh_task){
+                struct task_struct *new_max_eff_prio = top_priority(&tsk_rt(t)->hp_blocked_tasks);
+                
+                if((new_max_eff_prio == NULL) ||
+                   (  (new_max_eff_prio != old_max_eff_prio) /* there was a change in eff prio */ &&
+                          (effective_priority(t) == old_max_eff_prio) /* and owner had the old eff prio */)  )
+                {
+                        // old_max_eff_prio > new_max_eff_prio
+                        
+                        if(__edf_higher_prio(new_max_eff_prio, BASE, t, INHERITED)) {
+                                TRACE_TASK(t, "new_max_eff_prio > task's eff_prio-- new_max_eff_prio: %s/%d   task: %s/%d [%s/%d]\n",
+                                                   new_max_eff_prio->comm, new_max_eff_prio->pid,
+                                                   t->comm, t->pid, tsk_rt(t)->inh_task->comm, tsk_rt(t)->inh_task->pid);
+                                WARN_ON(1);
+                        }
+                        
+                        decrease_priority_inheritance(t, new_max_eff_prio);
+                }
         }
         
+        if(binheap_empty(&tsk_rt(t)->hp_blocked_tasks) && tsk_rt(t)->inh_task != NULL)
+        {
+                WARN_ON(tsk_rt(t)->inh_task != NULL);
+                TRACE_TASK(t, "No more locks are held, but eff_prio = %s/%d\n",
+                                   tsk_rt(t)->inh_task->comm, tsk_rt(t)->inh_task->pid);
+        }       
+        
+        raw_spin_unlock(&tsk_rt(t)->hp_blocked_tasks_lock);
+        
     
         /* check if there are jobs waiting for this resource */
         next = __waitqueue_remove_first(&mutex->wait);
@@ -980,28 +1146,70 @@ int gsnedf_rsm_mutex_unlock(struct litmus_lock* l)
                 mutex->owner = next;
                 TRACE_CUR("lock ownership passed to %s/%d\n", next->comm, next->pid);
         
+                
                 tsk_rt(next)->blocked_lock = NULL;
-                nest_lock(l, next);  // moves local_prio to trans_prio
+        
                 
                 /* determine new hp_waiter if necessary */
                 if (next == mutex->hp_waiter) {
+                        
                         TRACE_TASK(next, "was highest-prio waiter\n");
                         /* next has the highest priority --- it doesn't need to
                          * inherit.  However, we need to make sure that the
                          * next-highest priority in the queue is reflected in
                          * hp_waiter. */
                         mutex->hp_waiter = rsm_mutex_find_hp_waiter(mutex, next);
+                        l->hp_waiter_eff_prio = (mutex->hp_waiter) ? effective_priority(mutex->hp_waiter) : NULL;
+                        
                         if (mutex->hp_waiter)
                                 TRACE_TASK(mutex->hp_waiter, "is new highest-prio waiter\n");
                         else
                                 TRACE("no further waiters\n");
+                        
+                        raw_spin_lock(&tsk_rt(next)->hp_blocked_tasks_lock);
+                        
+                        //TRACE_TASK(next, "Heap Before:\n");
+                        //print_hp_waiters(tsk_rt(next)->hp_blocked_tasks.root, 0);                     
+                        
+                        binheap_add(&l->hp_binheap_node, &tsk_rt(next)->hp_blocked_tasks, struct litmus_lock, hp_binheap_node);
+                        
+                        //TRACE_TASK(next, "Heap After:\n");
+                        //print_hp_waiters(tsk_rt(next)->hp_blocked_tasks.root, 0);                     
+                        
+                        raw_spin_unlock(&tsk_rt(next)->hp_blocked_tasks_lock);
                 } else {
-                        /* Well, if next is not the highest-priority waiter,
-                         * then it ought to inherit the highest-priority
+                        /* Well, if 'next' is not the highest-priority waiter,
+                         * then it (probably) ought to inherit the highest-priority
                          * waiter's priority. */
-                        increase_priority_inheritance(next, mutex->hp_waiter);
+                        TRACE_TASK(next, "is not hp_waiter of lock %d.\n", l->ident);
+                        
+                        raw_spin_lock(&tsk_rt(next)->hp_blocked_tasks_lock);
+                        
+                        //TRACE_TASK(next, "Heap Before:\n");
+                        //print_hp_waiters(tsk_rt(next)->hp_blocked_tasks.root, 0);                                     
+                        
+                        binheap_add(&l->hp_binheap_node, &tsk_rt(next)->hp_blocked_tasks,
+                                                struct litmus_lock, hp_binheap_node);
+                        
+                        //TRACE_TASK(next, "Heap After:\n");
+                        //print_hp_waiters(tsk_rt(next)->hp_blocked_tasks.root, 0);                             
+                        
+                        /* It is possible that 'next' *should* be the hp_waiter, but isn't
+                     * because that update hasn't yet executed (update operation is
+                         * probably blocked on mutex->lock). So only inherit if the top of
+                         * 'next's top heap node is indeed the effective prio. of hp_waiter. 
+                         * (We use l->hp_waiter_eff_prio instead of effective_priority(hp_waiter)
+                         * since the effective priority of hp_waiter can change (and the
+                         * update has not made it to this lock).)
+                         */
+                        if(likely(top_priority(&tsk_rt(next)->hp_blocked_tasks) == l->hp_waiter_eff_prio))
+                        {
+                                increase_priority_inheritance(next, l->hp_waiter_eff_prio);
+                        }
+                        
+                        raw_spin_unlock(&tsk_rt(next)->hp_blocked_tasks_lock);
                 }
-                
+
                 /* wake up next */
                 wake_up_process(next);
         }
@@ -1011,11 +1219,178 @@ int gsnedf_rsm_mutex_unlock(struct litmus_lock* l)
         }
 
 out:
-        spin_unlock_irqrestore(&mutex->wait.lock, flags);
+        raw_spin_unlock_irqrestore(&mutex->lock, flags);
+        //raw_spin_unlock_irqrestore(&rsm_global_lock, flags);
     
         return err;
 }
 
+
+void gsnedf_rsm_mutex_propagate_increase_inheritance(struct litmus_lock* l,
+                                                                                                         struct task_struct* t,
+                                                                                                         raw_spinlock_t* to_unlock,
+                                                                                                         unsigned long irqflags)
+{
+        struct rsm_mutex *mutex = rsm_mutex_from_lock(l);
+        
+        // relay-style locking
+        raw_spin_lock(&mutex->lock);
+        raw_spin_unlock(to_unlock);
+        
+        if(tsk_rt(t)->blocked_lock == l) {  // prevent race on tsk_rt(t)->blocked
+                struct task_struct *owner = mutex->owner;                       
+                
+                struct task_struct *old_max_eff_prio;
+                struct task_struct *new_max_eff_prio;
+                
+                raw_spin_lock(&tsk_rt(owner)->hp_blocked_tasks_lock);
+                
+                old_max_eff_prio = top_priority(&tsk_rt(owner)->hp_blocked_tasks);
+                
+                if((t != mutex->hp_waiter) && edf_higher_prio(t, mutex->hp_waiter)) {
+                        TRACE_TASK(t, "is new highest-prio waiter by propagation.\n");                  
+                        mutex->hp_waiter = t;
+                }
+                if(t == mutex->hp_waiter) {
+                        // reflect the decreased priority in the heap node.
+                        l->hp_waiter_eff_prio = effective_priority(mutex->hp_waiter);
+                        binheap_decrease(&l->hp_binheap_node, &tsk_rt(owner)->hp_blocked_tasks);
+                }
+                
+                new_max_eff_prio = top_priority(&tsk_rt(owner)->hp_blocked_tasks);
+                
+                
+                if(new_max_eff_prio != old_max_eff_prio) {
+                        // new_max_eff_prio > old_max_eff_prio holds.
+                        if ((effective_priority(owner) == old_max_eff_prio) ||
+                                (__edf_higher_prio(new_max_eff_prio, BASE, owner, INHERITED))) {
+                                
+                                TRACE_TASK(new_max_eff_prio, "Propagating inheritance to holder of lock %d.\n", l->ident);
+                                
+                                // beware: recursion
+                                nested_increase_priority_inheritance(owner, new_max_eff_prio, &mutex->lock, irqflags);  // unlocks mutex->lock
+                        }
+                        else {
+                                TRACE_TASK(new_max_eff_prio, "Lower priority than holder %s/%d.  No propagation.\n", owner->comm, owner->pid);
+                                raw_spin_unlock(&tsk_rt(owner)->hp_blocked_tasks_lock);
+                                raw_spin_unlock_irqrestore(&mutex->lock, irqflags);
+                        }
+                }
+                else {
+                        TRACE_TASK(mutex->owner, "No change in maxiumum effective priority.\n");                        
+                        raw_spin_unlock(&tsk_rt(owner)->hp_blocked_tasks_lock);
+                        raw_spin_unlock_irqrestore(&mutex->lock, irqflags);
+                }
+        }
+        else {
+                struct litmus_lock *still_blocked = tsk_rt(t)->blocked_lock;
+
+                TRACE_TASK(t, "is not blocked on lock %d.\n", l->ident);
+                if(still_blocked) {
+                        TRACE_TASK(t, "is still blocked on a lock though (lock %d).\n", still_blocked->ident);
+                        if(still_blocked->ops->propagate_increase_inheritance) {
+                                /* due to relay-style nesting of spinlocks (acq. A, acq. B, free A, free B)
+                                   we know that task 't' has not released any locks behind us in this
+                                   chain.  Propagation just needs to catch up with task 't'. */
+                                still_blocked->ops->propagate_increase_inheritance(still_blocked, t, &mutex->lock, irqflags);
+                        }
+                        else {
+                                TRACE_TASK(t, "Inheritor is blocked on lock (%p) that does not support nesting!\n", still_blocked);
+                                raw_spin_unlock_irqrestore(&mutex->lock, irqflags);
+                        }
+                }
+                else {
+                        raw_spin_unlock_irqrestore(&mutex->lock, irqflags);
+                }
+        }
+}
+
+
+void gsnedf_rsm_mutex_propagate_decrease_inheritance(struct litmus_lock* l,
+                                                                                                         struct task_struct* t,
+                                                                                                         raw_spinlock_t* to_unlock,
+                                                                                                         unsigned long irqflags)
+{
+        struct rsm_mutex *mutex = rsm_mutex_from_lock(l);
+        
+        // relay-style locking
+        raw_spin_lock(&mutex->lock);
+        raw_spin_unlock(to_unlock);
+        
+        if(tsk_rt(t)->blocked_lock == l) {  // prevent race on tsk_rt(t)->blocked
+                if(t == mutex->hp_waiter) {
+                        struct task_struct *owner = mutex->owner;
+                        
+                        struct task_struct *old_max_eff_prio;
+                        struct task_struct *new_max_eff_prio;                   
+                        
+                        raw_spin_lock(&tsk_rt(owner)->hp_blocked_tasks_lock);
+                        
+                        old_max_eff_prio = top_priority(&tsk_rt(owner)->hp_blocked_tasks);
+                        
+                        binheap_delete(&l->hp_binheap_node, &tsk_rt(owner)->hp_blocked_tasks);
+                        mutex->hp_waiter = rsm_mutex_find_hp_waiter(mutex, NULL);
+                        l->hp_waiter_eff_prio = (mutex->hp_waiter) ? effective_priority(mutex->hp_waiter) : NULL;
+                        binheap_add(&l->hp_binheap_node, &tsk_rt(owner)->hp_blocked_tasks, struct litmus_lock, hp_binheap_node);
+                        
+                        new_max_eff_prio = top_priority(&tsk_rt(owner)->hp_blocked_tasks);
+                        
+                        if((old_max_eff_prio != new_max_eff_prio) &&
+                           (effective_priority(owner) == old_max_eff_prio))
+                        {
+                                // Need to set new effective_priority for owner
+                                
+                                struct task_struct *decreased_prio;
+
+                                TRACE_TASK(new_max_eff_prio, "Propagating decreased inheritance to holder of lock %d.\n", l->ident);
+                                
+                                if(__edf_higher_prio(new_max_eff_prio, BASE, owner, BASE)) {
+                                        TRACE_TASK(new_max_eff_prio, "has greater base priority than base priority of owner of lock %d.\n", l->ident);
+                                        decreased_prio = new_max_eff_prio;
+                                }
+                                else {
+                                        TRACE_TASK(new_max_eff_prio, "has lesser base priority than base priority of owner of lock %d.\n", l->ident);
+                                        decreased_prio = NULL;
+                                }
+
+                                // beware: recursion
+                                nested_decrease_priority_inheritance(owner, decreased_prio, &mutex->lock, irqflags);    // will unlock mutex->lock
+                        }
+                        else {
+                                raw_spin_unlock(&tsk_rt(owner)->hp_blocked_tasks_lock);
+                                raw_spin_unlock_irqrestore(&mutex->lock, irqflags);
+                        }
+                }
+                else {
+                        TRACE_TASK(t, "is not hp_waiter.  No propagation.\n");
+                        raw_spin_unlock_irqrestore(&mutex->lock, irqflags);
+                }
+        }
+        else {
+                struct litmus_lock *still_blocked = tsk_rt(t)->blocked_lock;
+
+                TRACE_TASK(t, "is not blocked on lock %d.\n", l->ident);
+                if(still_blocked) {
+                        TRACE_TASK(t, "is still blocked on a lock though (lock %d).\n", still_blocked->ident);
+                        if(still_blocked->ops->propagate_decrease_inheritance) {
+                                /* due to linked nesting of spinlocks (acq. A, acq. B, free A, free B)
+                                   we know that task 't' has not released any locks behind us in this
+                                   chain.  propagation just needs to catch up with task 't' */
+                                still_blocked->ops->propagate_decrease_inheritance(still_blocked, t, &mutex->lock, irqflags);
+                        }
+                        else {
+                                TRACE_TASK(t, "Inheritor is blocked on lock (%p) that does not support nesting!\n", still_blocked);
+                                raw_spin_unlock_irqrestore(&mutex->lock, irqflags);
+                        }
+                }
+                else {
+                        raw_spin_unlock_irqrestore(&mutex->lock, irqflags);
+                }
+        }
+}
+
+
+
 int gsnedf_rsm_mutex_close(struct litmus_lock* l)
 {
         struct task_struct *t = current;
@@ -1024,11 +1399,13 @@ int gsnedf_rsm_mutex_close(struct litmus_lock* l)
     
         int owner;
     
-        spin_lock_irqsave(&mutex->wait.lock, flags);
+        raw_spin_lock_irqsave(&mutex->lock, flags);
+        //raw_spin_lock_irqsave(&rsm_global_lock, flags);
     
         owner = (mutex->owner == t);
     
-        spin_unlock_irqrestore(&mutex->wait.lock, flags);
+        raw_spin_unlock_irqrestore(&mutex->lock, flags);
+        //raw_spin_unlock_irqrestore(&rsm_global_lock, flags);
     
         if (owner)
                 gsnedf_rsm_mutex_unlock(l);
@@ -1061,7 +1438,19 @@ static struct litmus_lock* gsnedf_new_rsm_mutex(void)
         mutex->owner   = NULL;
         mutex->hp_waiter = NULL;
         init_waitqueue_head(&mutex->wait);
+
+
+#ifdef CONFIG_DEBUG_SPINLOCK
+        {
+                __raw_spin_lock_init(&mutex->lock, ((struct litmus_lock*)mutex)->cheat_lockdep, &((struct litmus_lock*)mutex)->key);
+        }
+#else
+        raw_spin_lock_init(&mutex->lock);
+#endif
+        
         mutex->litmus_lock.ops = &gsnedf_rsm_mutex_lock_ops;
+        
+        ((struct litmus_lock*)mutex)->hp_waiter_ptr = &mutex->hp_waiter;
     
         return &mutex->litmus_lock;
 }
@@ -1223,7 +1612,7 @@ int gsnedf_fmlp_unlock(struct litmus_lock* l)
                 sem->owner = NULL;
 
         /* we lose the benefit of priority inheritance (if any) */
-        if (tsk_rt(t)->eff_prio)
+        if (tsk_rt(t)->inh_task)
                 decrease_priority_inheritance(t, NULL);
 
 out: