4 files changed, 225 insertions, 34 deletions

diff --git a/include/litmus/ikglp_lock.h b/include/litmus/ikglp_lock.h
new file mode 100644
index 000000000000..c0cc04db1bc6
--- /dev/null
+++ b/include/litmus/ikglp_lock.h
@@ -0,0 +1,97 @@
+#ifndef LITMUS_IKGLP_H
+#define LITMUS_IKGLP_H
+
+#include <litmus/litmus.h>
+#include <litmus/binheap.h>
+#include <litmus/locking.h>
+
+typedef struct ikglp_heap_node
+{
+        struct task_struct *task;
+        struct binheap_node node;
+} ikglp_heap_node_t;
+
+struct fifo_queue;
+struct ikglp_wait_state;
+
+typedef struct ikglp_donee_heap_node
+{
+        struct task_struct *task;
+        struct fifo_queue *fq;
+        struct ikglp_wait_state *donor_info;  // cross-linked with ikglp_wait_state_t of donor
+
+        struct binheap_node node;
+} ikglp_donee_heap_node_t;
+
+// Maintains the state of a request as it goes through the IKGLP
+typedef struct ikglp_wait_state {
+        struct task_struct *task;  // pointer back to the requesting task
+
+        // Data for while waiting in FIFO Queue
+        wait_queue_t fq_node;
+        ikglp_heap_node_t global_heap_node;
+        ikglp_donee_heap_node_t donee_heap_node;
+
+        // Data for while waiting in PQ
+        ikglp_heap_node_t pq_node;
+
+        // Data for while waiting as a donor
+        ikglp_donee_heap_node_t *donee_info;  // cross-linked with donee's ikglp_donee_heap_node_t
+        struct nested_info prio_donation;
+        struct binheap_node node;
+} ikglp_wait_state_t;
+
+/* struct for semaphore with priority inheritance */
+struct fifo_queue
+{
+        wait_queue_head_t wait;
+        struct task_struct* owner;
+
+        // used for bookkeepping
+        ikglp_heap_node_t global_heap_node;
+        ikglp_donee_heap_node_t donee_heap_node;
+
+        struct task_struct* hp_waiter;
+        int count; /* number of waiters + holder */
+
+        struct nested_info nest;
+};
+
+struct ikglp_semaphore
+{
+        struct litmus_lock litmus_lock;
+
+        raw_spinlock_t  lock;
+        raw_spinlock_t  real_lock;
+
+        int nr_replicas; // AKA k
+        int m;
+
+        int max_fifo_len; // max len of a fifo queue
+
+        struct binheap_handle top_m;  // min heap, base prio
+        int top_m_size;  // number of nodes in top_m
+
+        struct binheap_handle not_top_m; // max heap, base prio
+
+        struct binheap_handle donees;   // min-heap, base prio
+        struct fifo_queue *shortest_fifo_queue; // pointer to shortest fifo queue
+
+        /* data structures for holding requests */
+        struct fifo_queue *fifo_queues; // array nr_replicas in length
+        struct binheap_handle priority_queue;   // max-heap, base prio
+        struct binheap_handle donors;   // max-heap, base prio
+};
+
+static inline struct ikglp_semaphore* ikglp_from_lock(struct litmus_lock* lock)
+{
+        return container_of(lock, struct ikglp_semaphore, litmus_lock);
+}
+
+int ikglp_lock(struct litmus_lock* l);
+int ikglp_unlock(struct litmus_lock* l);
+int ikglp_close(struct litmus_lock* l);
+void ikglp_free(struct litmus_lock* l);
+struct litmus_lock* ikglp_new(int m, struct litmus_lock_ops*, void* __user arg);
+
+#endif
diff --git a/include/litmus/locking.h b/include/litmus/locking.h
index 972cbdb7fdd5..c2324c4ccb8a 100644
--- a/include/litmus/locking.h
+++ b/include/litmus/locking.h
@@ -13,6 +13,15 @@ struct nested_info
         struct task_struct **hp_waiter_ptr;
     struct binheap_node hp_binheap_node;        
 };
+
+static inline struct task_struct* top_priority(struct binheap_handle* handle) {
+        if(!binheap_empty(handle)) {
+                return (struct task_struct*)(binheap_top_entry(handle, struct nested_info, hp_binheap_node)->hp_waiter_eff_prio);
+        }
+        return NULL;
+}
+
+void print_hp_waiters(struct binheap_node* n, int depth);
 #endif
 
 
@@ -23,16 +32,14 @@ struct litmus_lock {
         struct litmus_lock_ops *ops;
         int type;
     
-#ifdef CONFIG_LITMUS_NESTED_LOCKING
         int ident;
         
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
         struct nested_info nest;
-
 //#ifdef CONFIG_DEBUG_SPINLOCK  
         char cheat_lockdep[2];
         struct lock_class_key key;
 //#endif
-
 #endif
 };
 
@@ -41,36 +48,42 @@ struct litmus_lock {
 #define MAX_DGL_SIZE CONFIG_LITMUS_MAX_DGL_SIZE
 
 typedef struct dgl_wait_state {
-        struct task_struct *task;
-        struct litmus_lock *locks[MAX_DGL_SIZE];
-        int size;
-        int nr_remaining;
-        
-        int last_primary;
-        
+        struct task_struct *task;       /* task waiting on DGL */
+        struct litmus_lock *locks[MAX_DGL_SIZE];        /* requested locks in DGL */
+        int size;                       /* size of the DGL */
+        int nr_remaining;       /* nr locks remainging before DGL is complete */
+        int last_primary;       /* index lock in locks[] that has active priority */
         wait_queue_t wq_nodes[MAX_DGL_SIZE];
 } dgl_wait_state_t;
 
 void wake_or_wait_on_next_lock(dgl_wait_state_t *dgl_wait);
-void select_next_lock(dgl_wait_state_t* dgl_wait, struct litmus_lock* prev_lock);
+void select_next_lock(dgl_wait_state_t* dgl_wait /*, struct litmus_lock* prev_lock*/);
 
 void init_dgl_waitqueue_entry(wait_queue_t *wq_node, dgl_wait_state_t* dgl_wait);
 int dgl_wake_up(wait_queue_t *wq_node, unsigned mode, int sync, void *key);
 void __waitqueue_dgl_remove_first(wait_queue_head_t *wq, dgl_wait_state_t** dgl_wait, struct task_struct **task);
 #endif
 
+typedef int (*lock_op_t)(struct litmus_lock *l);
+typedef lock_op_t lock_close_t;
+typedef lock_op_t lock_lock_t;
+typedef lock_op_t lock_unlock_t;
+
+typedef int (*lock_open_t)(struct litmus_lock *l, void* __user arg);
+typedef void (*lock_free_t)(struct litmus_lock *l);
+
 struct litmus_lock_ops {
         /* Current task tries to obtain / drop a reference to a lock.
          * Optional methods, allowed by default. */
-        int (*open)(struct litmus_lock*, void* __user);
-        int (*close)(struct litmus_lock*);
+        lock_open_t open;
+        lock_close_t close;
 
         /* Current tries to lock/unlock this lock (mandatory methods). */
-        int (*lock)(struct litmus_lock*);
-        int (*unlock)(struct litmus_lock*);
+        lock_lock_t lock;
+        lock_unlock_t unlock;
         
         /* The lock is no longer being referenced (mandatory method). */
-        void (*deallocate)(struct litmus_lock*);
+        lock_free_t deallocate;
         
 #ifdef CONFIG_LITMUS_NESTED_LOCKING
         void (*propagate_increase_inheritance)(struct litmus_lock* l, struct task_struct* t, raw_spinlock_t* to_unlock, unsigned long irqflags);
@@ -86,7 +99,36 @@ struct litmus_lock_ops {
 };
 
 
-#ifdef CONFIG_LITMUS_DGL_SUPPORT
+/*
+ Nested inheritance can be achieved with fine-grain locking when there is
+ no need for DGL support, presuming locks are acquired in a partial order
+ (no cycles!).  However, DGLs allow locks to be acquired in any order.  This
+ makes nested inheritance very difficult (we don't yet know a solution) to
+ realize with fine-grain locks, so we use a big lock instead.
+ 
+ Code contains both fine-grain and coarse-grain methods together, side-by-side.
+ Each lock operation *IS NOT* surrounded by ifdef/endif to help make code more
+ readable.  However, this leads to the odd situation where both code paths
+ appear together in code as if they were both active together.
+ 
+ THIS IS NOT REALLY THE CASE!  ONLY ONE CODE PATH IS ACTUALLY ACTIVE!
+ 
+ Example:
+        lock_global_irqsave(coarseLock, flags);
+        lock_fine_irqsave(fineLock, flags);
+ 
+ Reality (coarse):
+        lock_global_irqsave(coarseLock, flags);
+        //lock_fine_irqsave(fineLock, flags);   
+ 
+ Reality (fine):
+        //lock_global_irqsave(coarseLock, flags);
+        lock_fine_irqsave(fineLock, flags);      
+ 
+ Be careful when you read code involving nested inheritance.
+ */
+#if defined(CONFIG_LITMUS_DGL_SUPPORT)
+/* DGL requires a big lock to implement nested inheritance */
 #define lock_global_irqsave(lock, flags)                raw_spin_lock_irqsave((lock), (flags))
 #define lock_global(lock)                                               raw_spin_lock((lock))
 #define unlock_global_irqrestore(lock, flags)   raw_spin_unlock_irqrestore((lock), (flags))
@@ -98,8 +140,8 @@ struct litmus_lock_ops {
 #define unlock_fine_irqrestore(lock, flags)
 #define unlock_fine(lock)
 
-#elif CONFIG_LITMUS_NESTED_LOCKING
-
+#elif defined(CONFIG_LITMUS_NESTED_LOCKING)
+/* Use fine-grain locking when DGLs are disabled. */
 /* global locking are no-ops without DGL support */
 #define lock_global_irqsave(lock, flags)
 #define lock_global(lock)
@@ -116,17 +158,3 @@ struct litmus_lock_ops {
 
 #endif
 
-
-
-
-
-
-
-
-
-
-
-
-
-
-
diff --git a/include/litmus/rsm_lock.h b/include/litmus/rsm_lock.h
new file mode 100644
index 000000000000..a15189683de4
--- /dev/null
+++ b/include/litmus/rsm_lock.h
@@ -0,0 +1,54 @@
+#ifndef LITMUS_RSM_H
+#define LITMUS_RSM_H
+
+#include <litmus/litmus.h>
+#include <litmus/binheap.h>
+#include <litmus/locking.h>
+
+/* 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;
+
+        /* 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)
+{
+        return container_of(lock, struct rsm_mutex, litmus_lock);
+}
+
+#ifdef CONFIG_LITMUS_DGL_SUPPORT
+int rsm_mutex_is_owner(struct litmus_lock *l, struct task_struct *t);
+int rsm_mutex_dgl_lock(struct litmus_lock *l, dgl_wait_state_t* dgl_wait, wait_queue_t* wq_node);
+void rsm_mutex_enable_priority(struct litmus_lock *l, dgl_wait_state_t* dgl_wait);
+#endif
+
+void rsm_mutex_propagate_increase_inheritance(struct litmus_lock* l,
+                                                                                          struct task_struct* t,
+                                                                                          raw_spinlock_t* to_unlock,
+                                                                                          unsigned long irqflags);
+
+void rsm_mutex_propagate_decrease_inheritance(struct litmus_lock* l,
+                                                                                          struct task_struct* t,
+                                                                                          raw_spinlock_t* to_unlock,
+                                                                                          unsigned long irqflags);
+
+int rsm_mutex_lock(struct litmus_lock* l);
+int rsm_mutex_unlock(struct litmus_lock* l);
+int rsm_mutex_close(struct litmus_lock* l);
+void rsm_mutex_free(struct litmus_lock* l);
+struct litmus_lock* rsm_mutex_new(struct litmus_lock_ops*);
+
+
+#endif
\ No newline at end of file
diff --git a/include/litmus/sched_plugin.h b/include/litmus/sched_plugin.h
index ae11e3ac9266..8e5167970340 100644
--- a/include/litmus/sched_plugin.h
+++ b/include/litmus/sched_plugin.h
@@ -58,6 +58,13 @@ typedef void (*task_exit_t)    (struct task_struct *);
 typedef long (*allocate_lock_t) (struct litmus_lock **lock, int type,
                                  void* __user config);
 
+typedef void (*increase_prio_t)(struct task_struct* t, struct task_struct* prio_inh);
+typedef void (*decrease_prio_t)(struct task_struct* t, struct task_struct* prio_inh);
+typedef void (*nested_increase_prio_t)(struct task_struct* t, struct task_struct* prio_inh,
+                                                                          raw_spinlock_t *to_unlock, unsigned long irqflags);
+typedef void (*nested_decrease_prio_t)(struct task_struct* t, struct task_struct* prio_inh,
+                                                                          raw_spinlock_t *to_unlock, unsigned long irqflags);
+
 typedef raw_spinlock_t* (*get_dgl_spinlock_t) (struct task_struct *t);
 
 /********************* sys call backends  ********************/
@@ -97,8 +104,13 @@ struct sched_plugin {
 #ifdef CONFIG_LITMUS_LOCKING
         /*      locking protocols       */
         allocate_lock_t         allocate_lock;
+        increase_prio_t         increase_prio;
+        decrease_prio_t         decrease_prio;
+#endif
+#ifdef CONFIG_LITMUS_NESTED_LOCKING
+        nested_increase_prio_t nested_increase_prio;
+        nested_decrease_prio_t nested_decrease_prio;
 #endif
-        
 #ifdef CONFIG_LITMUS_DGL_SUPPORT
         get_dgl_spinlock_t      get_dgl_spinlock;
 #endif