blah

6 files changed, 412 insertions, 13 deletions

diff --git a/include/litmus/fdso.h b/include/litmus/fdso.h
index caf2a1e6918c..4b4ae7796788 100644
--- a/include/litmus/fdso.h
+++ b/include/litmus/fdso.h
@@ -19,8 +19,10 @@ typedef enum  {
 
         FMLP_SEM        = 0,
         SRP_SEM         = 1,
+        
+        RSM_MUTEX       = 2,
 
-        MAX_OBJ_TYPE    = 1
+        MAX_OBJ_TYPE    = 2
 } obj_type_t;
 
 struct inode_obj_id {
@@ -67,5 +69,7 @@ static inline void* od_lookup(int od, obj_type_t type)
 #define lookup_srp_sem(od) ((struct srp_semaphore*) od_lookup(od, SRP_SEM))
 #define lookup_ics(od)     ((struct ics*)           od_lookup(od, ICS_ID))
 
+#define lookup_rsm_mutex(od)((struct litmus_lock*)  od_lookup(od, FMLP_SEM))
+
 
 #endif
diff --git a/include/litmus/locking.h b/include/litmus/locking.h
index 27eafd002556..a01890153fa1 100644
--- a/include/litmus/locking.h
+++ b/include/litmus/locking.h
@@ -17,6 +17,10 @@ struct litmus_lock {
 #endif
 };
 
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+void nest_lock(struct litmus_lock *l, struct task_struct *t);
+#endif
+
 struct litmus_lock_ops {
         /* Current task tries to obtain / drop a reference to a lock.
          * Optional methods, allowed by default. */
@@ -29,6 +33,11 @@ struct litmus_lock_ops {
 
         /* The lock is no longer being referenced (mandatory method). */
         void (*deallocate)(struct litmus_lock*);
+        
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+        void (*propagate_increase_inheritance)(struct litmus_lock* l, struct task_struct* t);
+        void (*propagate_decrease_inheritance)(struct litmus_lock* l, struct task_struct* t);
+#endif
 };
 
 #endif
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 3a054db8ee07..5239d4a6f508 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -141,6 +141,9 @@ struct rt_param {
     
     /* pointer to the last lock acquired */
     struct litmus_lock* last_lock;
+        
+        /* pointer to lock upon which is currently blocked */
+        struct litmus_lock* blocked_lock;
 #endif
     
     
diff --git a/litmus/fdso.c b/litmus/fdso.c
index aa7b384264e3..f192787b577d 100644
--- a/litmus/fdso.c
+++ b/litmus/fdso.c
@@ -23,6 +23,7 @@ extern struct fdso_ops generic_lock_ops;
 static const struct fdso_ops* fdso_ops[] = {
         &generic_lock_ops, /* FMLP_SEM */
         &generic_lock_ops, /* SRP_SEM */
+        &generic_lock_ops, /* RSM_MUTEX */
 };
 
 static int fdso_create(void** obj_ref, obj_type_t type, void* __user config)
diff --git a/litmus/locking.c b/litmus/locking.c
index 5897beb941cf..f3fa273314fb 100644
--- a/litmus/locking.c
+++ b/litmus/locking.c
@@ -4,6 +4,7 @@
 
 #include <litmus/sched_plugin.h>
 #include <litmus/trace.h>
+#include <litmus/litmus.h>
 
 static int create_generic_lock(void** obj_ref, obj_type_t type, void* __user arg);
 static int open_generic_lock(struct od_table_entry* entry, void* __user arg);
@@ -124,6 +125,27 @@ struct task_struct* __waitqueue_remove_first(wait_queue_head_t *wq)
 }
 
 
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+/* not "lock_nest" ... get it? */
+void nest_lock(struct litmus_lock *l, struct task_struct *t)
+{
+        if(tsk_rt(t)->last_lock) {
+                /* push new lock to front of old lock */
+                struct litmus_lock *old = tsk_rt(t)->last_lock;
+                
+                list_add(&l->lock_chain, &old->lock_chain);
+        }
+        
+        tsk_rt(t)->last_lock = l;
+        
+        // local inh now becomes transitive inh
+        tsk_rt(t)->trans_prio = tsk_rt(t)->local_prio;  // what about old transitive prio???
+        tsk_rt(t)->local_prio = NULL;
+}
+#endif
+
+
+
 #else
 
 struct fdso_ops generic_lock_ops = {};
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index 677a932e08be..91c38bbf695c 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -718,13 +718,13 @@ static void decrease_priority_inheritance(struct task_struct* t, struct task_str
 
         /* 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);
+        //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(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()
@@ -736,6 +736,350 @@ 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)
+{
+        increase_priority_inheritance(t, prio_inh);  // increase our prio.
+        
+        // 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);
+        }
+}
+
+/* called with IRQs off */
+static void nested_decrease_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh)
+{
+        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);
+        }       
+}
+
+
+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;
+        
+        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(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);
+                }
+        }
+        
+EXIT:
+        
+        spin_unlock_irqrestore(&mutex->wait.lock, flags);
+}
+
+void gsnedf_rsm_mutex_propagate_decrease_inheritance(struct litmus_lock* l,
+                                                                                                         struct task_struct* t)
+{
+        struct rsm_mutex *mutex = rsm_mutex_from_lock(l);
+        unsigned long flags;
+        
+        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) {
+                        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);
+                        
+                        
+                        // lower eff_prio of owner to new hp if needed.
+                        if(t == mutex->owner->eff_prio)
+                        {
+                                
+                        }
+                        
+
+                        nested_increase_priority_inheritance(mutex->owner, prio);                       
+                }
+        }
+        
+        spin_unlock_irqrestore(&mutex->wait.lock, flags);
+}
+
+
+
+
+
+
+/* ******************** RSM MUTEX ********************** */
+
+/* struct for semaphore with priority inheritance */
+struct rsm_mutex {
+        struct litmus_lock litmus_lock;
+    
+        /* current resource holder */
+        struct task_struct *owner;
+    
+        /* highest-priority waiter */
+        struct task_struct *hp_waiter;
+    
+        /* FIFO queue of waiting tasks -- for now.  time stamp in the future. */
+        wait_queue_head_t wait;
+};
+
+static inline struct rsm_mutex* rsm_mutex_from_lock(struct litmus_lock* lock)
+{
+        return container_of(lock, struct rsm_mutex, litmus_lock);
+}
+
+/* caller is responsible for locking */
+struct task_struct* rsm_mutex_find_hp_waiter(struct rsm_mutex *mutex,
+                                             struct task_struct* skip)
+{
+        struct list_head        *pos;
+        struct task_struct      *queued, *found = NULL;
+    
+        list_for_each(pos, &mutex->wait.task_list) {
+                queued  = (struct task_struct*) list_entry(pos, wait_queue_t,
+                                                   task_list)->private;
+        
+                /* Compare task prios, find high prio task. */
+                if (queued != skip && edf_higher_prio(queued, found))
+                        found = queued;
+        }
+        return found;
+}
+
+
+
+
+int gsnedf_rsm_mutex_lock(struct litmus_lock* l)
+{
+        struct task_struct* t = current;
+        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);
+    
+        if (mutex->owner) {
+                /* resource is not free => must suspend and wait */
+        
+                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();
+                
+                /* FIXME: interruptible would be nice some day */
+                set_task_state(t, TASK_UNINTERRUPTIBLE);
+        
+                __add_wait_queue_tail_exclusive(&mutex->wait, &wait);
+        
+                /* check if we need to activate priority inheritance */
+                if (edf_higher_prio(t, mutex->hp_waiter)) {
+                        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);
+                        }
+                }
+                
+                TS_LOCK_SUSPEND;
+        
+                /* release lock before sleeping */
+                spin_unlock_irqrestore(&mutex->wait.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
+                 * there is only one wake up per release.
+                 */
+        
+                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);
+        } else {
+                /* it's ours now */
+                mutex->owner = t;
+        
+                nest_lock(l, t);
+                
+                spin_unlock_irqrestore(&mutex->wait.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;
+        int err = 0;
+    
+        spin_lock_irqsave(&mutex->wait.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);  
+        }
+        
+    
+        /* check if there are jobs waiting for this resource */
+        next = __waitqueue_remove_first(&mutex->wait);
+        if (next) {
+                /* next becomes the resouce holder */
+                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);
+                        if (mutex->hp_waiter)
+                                TRACE_TASK(mutex->hp_waiter, "is new highest-prio waiter\n");
+                        else
+                                TRACE("no further waiters\n");
+                } else {
+                        /* Well, if next is not the highest-priority waiter,
+                         * then it ought to inherit the highest-priority
+                         * waiter's priority. */
+                        increase_priority_inheritance(next, mutex->hp_waiter);
+                }
+                
+                /* wake up next */
+                wake_up_process(next);
+        }
+        else {
+    /* becomes available */
+                mutex->owner = NULL;
+        }
+
+out:
+        spin_unlock_irqrestore(&mutex->wait.lock, flags);
+    
+        return err;
+}
+
+int gsnedf_rsm_mutex_close(struct litmus_lock* l)
+{
+        struct task_struct *t = current;
+        struct rsm_mutex *mutex = rsm_mutex_from_lock(l);
+        unsigned long flags;
+    
+        int owner;
+    
+        spin_lock_irqsave(&mutex->wait.lock, flags);
+    
+        owner = (mutex->owner == t);
+    
+        spin_unlock_irqrestore(&mutex->wait.lock, flags);
+    
+        if (owner)
+                gsnedf_rsm_mutex_unlock(l);
+    
+        return 0;
+}
+
+void gsnedf_rsm_mutex_free(struct litmus_lock* lock)
+{
+        kfree(rsm_mutex_from_lock(lock));
+}
+
+static struct litmus_lock_ops gsnedf_rsm_mutex_lock_ops = {
+        .close  = gsnedf_rsm_mutex_close,
+        .lock   = gsnedf_rsm_mutex_lock,
+        .unlock = gsnedf_rsm_mutex_unlock,
+        .deallocate = gsnedf_rsm_mutex_free,
+        .propagate_increase_inheritance = gsnedf_rsm_mutex_propagate_increase_inheritance,
+        .propagate_decrease_inheritance = gsnedf_rsm_mutex_propagate_decrease_inheritance       
+};
+
+static struct litmus_lock* gsnedf_new_rsm_mutex(void)
+{
+        struct rsm_mutex* mutex;
+    
+        mutex = kmalloc(sizeof(*mutex), GFP_KERNEL);
+        if (!mutex)
+                return NULL;
+    
+        mutex->owner   = NULL;
+        mutex->hp_waiter = NULL;
+        init_waitqueue_head(&mutex->wait);
+        mutex->litmus_lock.ops = &gsnedf_rsm_mutex_lock_ops;
+    
+        return &mutex->litmus_lock;
+}
+
+/* **** lock constructor **** */
+
+#endif
+
+
+
+
+
+
+
+
+
+
+
 /* ******************** FMLP support ********************** */
 
 /* struct for semaphore with priority inheritance */
@@ -918,6 +1262,11 @@ static struct litmus_lock_ops gsnedf_fmlp_lock_ops = {
         .lock   = gsnedf_fmlp_lock,
         .unlock = gsnedf_fmlp_unlock,
         .deallocate = gsnedf_fmlp_free,
+        
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+        .propagate_increase_inheritance = NULL,
+        .propagate_decrease_inheritance = NULL
+#endif
 };
 
 static struct litmus_lock* gsnedf_new_fmlp(void)
@@ -942,7 +1291,7 @@ static struct litmus_lock* gsnedf_new_fmlp(void)
 static long gsnedf_allocate_lock(struct litmus_lock **lock, int type,
                                  void* __user unused)
 {
-        int err = -ENXIO;
+        int err;
 
         /* GSN-EDF currently only supports the FMLP for global resources. */
         switch (type) {
@@ -950,14 +1299,25 @@ static long gsnedf_allocate_lock(struct litmus_lock **lock, int type,
         case FMLP_SEM:
                 /* Flexible Multiprocessor Locking Protocol */
                 *lock = gsnedf_new_fmlp();
-                if (*lock)
-                        err = 0;
-                else
-                        err = -ENOMEM;
                 break;
-
+            
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+    case RSM_MUTEX:
+                *lock = gsnedf_new_rsm_mutex();
+                break;
+#endif
+        
+        default:
+                err = -ENXIO;
+                goto UNSUPPORTED_LOCK;
         };
 
+        if (*lock)
+                err = 0;
+        else
+                err = -ENOMEM;
+
+UNSUPPORTED_LOCK:
         return err;
 }