1 files changed, 97 insertions, 0 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