Add LITMUS^RT core implementation

This patch adds the core of LITMUS^RT:

 - library functionality (heaps, rt_domain, prioritization, etc.)
 - budget enforcement logic
 - job management
 - system call backends
 - virtual devices (control page, etc.)
 - scheduler plugin API (and dummy plugin)

This code compiles, but is not yet integrated with the rest of Linux.

21 files changed, 1717 insertions, 6 deletions

diff --git a/include/litmus/affinity.h b/include/litmus/affinity.h
new file mode 100644
index 000000000000..ca2e442eb547
--- /dev/null
+++ b/include/litmus/affinity.h
@@ -0,0 +1,80 @@
+#ifndef __LITMUS_AFFINITY_H
+#define __LITMUS_AFFINITY_H
+
+#include <linux/cpumask.h>
+
+/*
+  L1 (instr) = depth 0
+  L1 (data)  = depth 1
+  L2 = depth 2
+  L3 = depth 3
+ */
+#define NUM_CACHE_LEVELS 4
+
+struct neighborhood
+{
+        unsigned int size[NUM_CACHE_LEVELS];
+        cpumask_var_t neighbors[NUM_CACHE_LEVELS];
+};
+
+/* topology info is stored redundently in a big array for fast lookups */
+extern struct neighborhood neigh_info[NR_CPUS];
+
+void init_topology(void); /* called by Litmus module's _init_litmus() */
+
+/* Works like:
+void get_nearest_available_cpu(
+        cpu_entry_t **nearest,
+        cpu_entry_t *start,
+        cpu_entry_t *entries,
+        int release_master)
+
+Set release_master = NO_CPU for no Release Master.
+
+We use a macro here to exploit the fact that C-EDF and G-EDF
+have similar structures for their cpu_entry_t structs, even though
+they do not share a common base-struct.  The macro allows us to
+avoid code duplication.
+
+TODO: Factor out the job-to-processor linking from C/G-EDF into
+a reusable "processor mapping".  (See B.B.'s RTSS'09 paper &
+dissertation.)
+ */
+#define get_nearest_available_cpu(nearest, start, entries, release_master) \
+{ \
+        (nearest) = NULL; \
+        if (!(start)->linked) { \
+                (nearest) = (start); \
+        } else { \
+                int __level; \
+                int __cpu; \
+                int __release_master = ((release_master) == NO_CPU) ? -1 : (release_master); \
+                struct neighborhood *__neighbors = &neigh_info[(start)->cpu]; \
+                \
+                for (__level = 0; (__level < NUM_CACHE_LEVELS) && !(nearest); ++__level) { \
+                        if (__neighbors->size[__level] > 1) { \
+                                for_each_cpu(__cpu, __neighbors->neighbors[__level]) { \
+                                        if (__cpu != __release_master) { \
+                                                cpu_entry_t *__entry = &per_cpu((entries), __cpu); \
+                                                if (!__entry->linked) { \
+                                                        (nearest) = __entry; \
+                                                        break; \
+                                                } \
+                                        } \
+                                } \
+                        } else if (__neighbors->size[__level] == 0) { \
+                                break; \
+                        } \
+                } \
+        } \
+        \
+        if ((nearest)) { \
+                TRACE("P%d is closest available CPU to P%d\n", \
+                                (nearest)->cpu, (start)->cpu); \
+        } else { \
+                TRACE("Could not find an available CPU close to P%d\n", \
+                                (start)->cpu); \
+        } \
+}
+
+#endif
diff --git a/include/litmus/bheap.h b/include/litmus/bheap.h
new file mode 100644
index 000000000000..cf4864a498d8
--- /dev/null
+++ b/include/litmus/bheap.h
@@ -0,0 +1,77 @@
+/* bheaps.h -- Binomial Heaps
+ *
+ * (c) 2008, 2009 Bjoern Brandenburg
+ */
+
+#ifndef BHEAP_H
+#define BHEAP_H
+
+#define NOT_IN_HEAP UINT_MAX
+
+struct bheap_node {
+        struct bheap_node*      parent;
+        struct bheap_node*      next;
+        struct bheap_node*      child;
+
+        unsigned int            degree;
+        void*                   value;
+        struct bheap_node**     ref;
+};
+
+struct bheap {
+        struct bheap_node*      head;
+        /* We cache the minimum of the heap.
+         * This speeds up repeated peek operations.
+         */
+        struct bheap_node*      min;
+};
+
+typedef int (*bheap_prio_t)(struct bheap_node* a, struct bheap_node* b);
+
+void bheap_init(struct bheap* heap);
+void bheap_node_init(struct bheap_node** ref_to_bheap_node_ptr, void* value);
+
+static inline int bheap_node_in_heap(struct bheap_node* h)
+{
+        return h->degree != NOT_IN_HEAP;
+}
+
+static inline int bheap_empty(struct bheap* heap)
+{
+        return heap->head == NULL && heap->min == NULL;
+}
+
+/* insert (and reinitialize) a node into the heap */
+void bheap_insert(bheap_prio_t higher_prio,
+                 struct bheap* heap,
+                 struct bheap_node* node);
+
+/* merge addition into target */
+void bheap_union(bheap_prio_t higher_prio,
+                struct bheap* target,
+                struct bheap* addition);
+
+struct bheap_node* bheap_peek(bheap_prio_t higher_prio,
+                            struct bheap* heap);
+
+struct bheap_node* bheap_take(bheap_prio_t higher_prio,
+                            struct bheap* heap);
+
+void bheap_uncache_min(bheap_prio_t higher_prio, struct bheap* heap);
+int  bheap_decrease(bheap_prio_t higher_prio, struct bheap_node* node);
+
+void bheap_delete(bheap_prio_t higher_prio,
+                 struct bheap* heap,
+                 struct bheap_node* node);
+
+/* allocate from memcache */
+struct bheap_node* bheap_node_alloc(int gfp_flags);
+void bheap_node_free(struct bheap_node* hn);
+
+/* allocate a heap node for value and insert into the heap */
+int bheap_add(bheap_prio_t higher_prio, struct bheap* heap,
+             void* value, int gfp_flags);
+
+void* bheap_take_del(bheap_prio_t higher_prio,
+                    struct bheap* heap);
+#endif
diff --git a/include/litmus/binheap.h b/include/litmus/binheap.h
new file mode 100644
index 000000000000..1cf364701da8
--- /dev/null
+++ b/include/litmus/binheap.h
@@ -0,0 +1,205 @@
+#ifndef LITMUS_BINARY_HEAP_H
+#define LITMUS_BINARY_HEAP_H
+
+#include <linux/kernel.h>
+
+/**
+ * Simple binary heap with add, arbitrary delete, delete_root, and top
+ * operations.
+ *
+ * Style meant to conform with list.h.
+ *
+ * Motivation: Linux's prio_heap.h is of fixed size. Litmus's binomial
+ * heap may be overkill (and perhaps not general enough) for some applications.
+ *
+ * Note: In order to make node swaps fast, a node inserted with a data pointer
+ * may not always hold said data pointer. This is similar to the binomial heap
+ * implementation. This does make node deletion tricky since we have to
+ * (1) locate the node that holds the data pointer to delete, and (2) the
+ * node that was originally inserted with said data pointer. These have to be
+ * coalesced into a single node before removal (see usage of
+ * __binheap_safe_swap()). We have to track node references to accomplish this.
+ */
+
+struct binheap_node {
+        void    *data;
+        struct binheap_node *parent;
+        struct binheap_node *left;
+        struct binheap_node *right;
+
+        /* pointer to binheap_node that holds *data for which this binheap_node
+         * was originally inserted.  (*data "owns" this node)
+         */
+        struct binheap_node *ref;
+        struct binheap_node **ref_ptr;
+};
+
+/**
+ * Signature of compator function.  Assumed 'less-than' (min-heap).
+ * Pass in 'greater-than' for max-heap.
+ *
+ * TODO: Consider macro-based implementation that allows comparator to be
+ * inlined (similar to Linux red/black tree) for greater efficiency.
+ */
+typedef int (*binheap_order_t)(struct binheap_node *a,
+                                struct binheap_node *b);
+
+
+struct binheap {
+        struct binheap_node *root;
+
+        /* pointer to node to take next inserted child */
+        struct binheap_node *next;
+
+        /* pointer to last node in complete binary tree */
+        struct binheap_node *last;
+
+        /* comparator function pointer */
+        binheap_order_t compare;
+};
+
+
+/* Initialized heap nodes not in a heap have parent
+ * set to BINHEAP_POISON.
+ */
+#define BINHEAP_POISON  ((void*)(0xdeadbeef))
+
+
+/**
+ * binheap_entry - get the struct for this heap node.
+ *  Only valid when called upon heap nodes other than the root handle.
+ * @ptr:        the heap node.
+ * @type:       the type of struct pointed to by binheap_node::data.
+ * @member:     unused.
+ */
+#define binheap_entry(ptr, type, member) \
+((type *)((ptr)->data))
+
+/**
+ * binheap_node_container - get the struct that contains this node.
+ *  Only valid when called upon heap nodes other than the root handle.
+ * @ptr:        the heap node.
+ * @type:       the type of struct the node is embedded in.
+ * @member:     the name of the binheap_struct within the (type) struct.
+ */
+#define binheap_node_container(ptr, type, member) \
+container_of((ptr), type, member)
+
+/**
+ * binheap_top_entry - get the struct for the node at the top of the heap.
+ *  Only valid when called upon the heap handle node.
+ * @ptr:    the special heap-handle node.
+ * @type:   the type of the struct the head is embedded in.
+ * @member:     the name of the binheap_struct within the (type) struct.
+ */
+#define binheap_top_entry(ptr, type, member) \
+binheap_entry((ptr)->root, type, member)
+
+/**
+ * binheap_delete_root - remove the root element from the heap.
+ * @handle:      handle to the heap.
+ * @type:    the type of the struct the head is embedded in.
+ * @member:      the name of the binheap_struct within the (type) struct.
+ */
+#define binheap_delete_root(handle, type, member) \
+__binheap_delete_root((handle), &((type *)((handle)->root->data))->member)
+
+/**
+ * binheap_delete - remove an arbitrary element from the heap.
+ * @to_delete:  pointer to node to be removed.
+ * @handle:      handle to the heap.
+ */
+#define binheap_delete(to_delete, handle) \
+__binheap_delete((to_delete), (handle))
+
+/**
+ * binheap_add - insert an element to the heap
+ * new_node: node to add.
+ * @handle:      handle to the heap.
+ * @type:    the type of the struct the head is embedded in.
+ * @member:      the name of the binheap_struct within the (type) struct.
+ */
+#define binheap_add(new_node, handle, type, member) \
+__binheap_add((new_node), (handle), container_of((new_node), type, member))
+
+/**
+ * binheap_decrease - re-eval the position of a node (based upon its
+ * original data pointer).
+ * @handle: handle to the heap.
+ * @orig_node: node that was associated with the data pointer
+ *             (whose value has changed) when said pointer was
+ *             added to the heap.
+ */
+#define binheap_decrease(orig_node, handle) \
+__binheap_decrease((orig_node), (handle))
+
+#define BINHEAP_NODE_INIT() { NULL, BINHEAP_POISON, NULL, NULL , NULL, NULL}
+
+#define BINHEAP_NODE(name) \
+        struct binheap_node name = BINHEAP_NODE_INIT()
+
+
+static inline void INIT_BINHEAP_NODE(struct binheap_node *n)
+{
+        n->data = NULL;
+        n->parent = BINHEAP_POISON;
+        n->left = NULL;
+        n->right = NULL;
+        n->ref = NULL;
+        n->ref_ptr = NULL;
+}
+
+static inline void INIT_BINHEAP_HANDLE(struct binheap *handle,
+                                binheap_order_t compare)
+{
+        handle->root = NULL;
+        handle->next = NULL;
+        handle->last = NULL;
+        handle->compare = compare;
+}
+
+/* Returns true if binheap is empty. */
+static inline int binheap_empty(struct binheap *handle)
+{
+        return(handle->root == NULL);
+}
+
+/* Returns true if binheap node is in a heap. */
+static inline int binheap_is_in_heap(struct binheap_node *node)
+{
+        return (node->parent != BINHEAP_POISON);
+}
+
+/* Returns true if binheap node is in given heap. */
+int binheap_is_in_this_heap(struct binheap_node *node, struct binheap* heap);
+
+/* Add a node to a heap */
+void __binheap_add(struct binheap_node *new_node,
+                                struct binheap *handle,
+                                void *data);
+
+/**
+ * Removes the root node from the heap. The node is removed after coalescing
+ * the binheap_node with its original data pointer at the root of the tree.
+ *
+ * The 'last' node in the tree is then swapped up to the root and bubbled
+ * down.
+ */
+void __binheap_delete_root(struct binheap *handle,
+                                struct binheap_node *container);
+
+/**
+ * Delete an arbitrary node.  Bubble node to delete up to the root,
+ * and then delete to root.
+ */
+void __binheap_delete(struct binheap_node *node_to_delete,
+                                struct binheap *handle);
+
+/**
+ * Bubble up a node whose pointer has decreased in value.
+ */
+void __binheap_decrease(struct binheap_node *orig_node,
+                                                struct binheap *handle);
+
+
+#endif
diff --git a/include/litmus/budget.h b/include/litmus/budget.h
new file mode 100644
index 000000000000..a766781b87d4
--- /dev/null
+++ b/include/litmus/budget.h
@@ -0,0 +1,36 @@
+#ifndef _LITMUS_BUDGET_H_
+#define _LITMUS_BUDGET_H_
+
+/* Update the per-processor enforcement timer (arm/reproram/cancel) for
+ * the next task. */
+void update_enforcement_timer(struct task_struct* t);
+
+inline static int budget_exhausted(struct task_struct* t)
+{
+        return get_exec_time(t) >= get_exec_cost(t);
+}
+
+inline static lt_t budget_remaining(struct task_struct* t)
+{
+        if (!budget_exhausted(t))
+                return get_exec_cost(t) - get_exec_time(t);
+        else
+                /* avoid overflow */
+                return 0;
+}
+
+#define budget_enforced(t) (tsk_rt(t)->task_params.budget_policy != NO_ENFORCEMENT)
+
+#define budget_precisely_enforced(t) (tsk_rt(t)->task_params.budget_policy \
+                                      == PRECISE_ENFORCEMENT)
+
+static inline int requeue_preempted_job(struct task_struct* t)
+{
+        /* Add task to ready queue only if not subject to budget enforcement or
+         * if the job has budget remaining. t may be NULL.
+         */
+        return t && !is_completed(t) && !tsk_rt(t)->dont_requeue
+                && (!budget_exhausted(t) || !budget_enforced(t));
+}
+
+#endif
diff --git a/include/litmus/clustered.h b/include/litmus/clustered.h
new file mode 100644
index 000000000000..0c18dcb15e6c
--- /dev/null
+++ b/include/litmus/clustered.h
@@ -0,0 +1,44 @@
+#ifndef CLUSTERED_H
+#define CLUSTERED_H
+
+/* Which cache level should be used to group CPUs into clusters?
+ * GLOBAL_CLUSTER means that all CPUs form a single cluster (just like under
+ * global scheduling).
+ */
+enum cache_level {
+        GLOBAL_CLUSTER = 0,
+        L1_CLUSTER     = 1,
+        L2_CLUSTER     = 2,
+        L3_CLUSTER     = 3
+};
+
+int parse_cache_level(const char *str, enum cache_level *level);
+const char* cache_level_name(enum cache_level level);
+
+/* expose a cache level in a /proc dir */
+struct proc_dir_entry* create_cluster_file(struct proc_dir_entry* parent,
+                                           enum cache_level* level);
+
+
+
+struct scheduling_cluster {
+        unsigned int id;
+        /* list of CPUs that are part of this cluster */
+        struct list_head cpus;
+};
+
+struct cluster_cpu {
+        unsigned int id; /* which CPU is this? */
+        struct list_head cluster_list; /* List of the CPUs in this cluster. */
+        struct scheduling_cluster* cluster; /* The cluster that this CPU belongs to. */
+};
+
+int get_cluster_size(enum cache_level level);
+
+int assign_cpus_to_clusters(enum cache_level level,
+                            struct scheduling_cluster* clusters[],
+                            unsigned int num_clusters,
+                            struct cluster_cpu* cpus[],
+                            unsigned int num_cpus);
+
+#endif
diff --git a/include/litmus/edf_common.h b/include/litmus/edf_common.h
new file mode 100644
index 000000000000..bbaf22ea7f12
--- /dev/null
+++ b/include/litmus/edf_common.h
@@ -0,0 +1,25 @@
+/*
+ * EDF common data structures and utility functions shared by all EDF
+ * based scheduler plugins
+ */
+
+/* CLEANUP: Add comments and make it less messy.
+ *
+ */
+
+#ifndef __UNC_EDF_COMMON_H__
+#define __UNC_EDF_COMMON_H__
+
+#include <litmus/rt_domain.h>
+
+void edf_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
+                     release_jobs_t release);
+
+int edf_higher_prio(struct task_struct* first,
+                    struct task_struct* second);
+
+int edf_ready_order(struct bheap_node* a, struct bheap_node* b);
+
+int edf_preemption_needed(rt_domain_t* rt, struct task_struct *t);
+
+#endif
diff --git a/include/litmus/fdso.h b/include/litmus/fdso.h
new file mode 100644
index 000000000000..f2115b83f1e4
--- /dev/null
+++ b/include/litmus/fdso.h
@@ -0,0 +1,77 @@
+/* fdso.h - file descriptor attached shared objects
+ *
+ * (c) 2007 B. Brandenburg, LITMUS^RT project
+ */
+
+#ifndef _LINUX_FDSO_H_
+#define _LINUX_FDSO_H_
+
+#include <linux/list.h>
+#include <asm/atomic.h>
+
+#include <linux/fs.h>
+#include <linux/slab.h>
+
+#define MAX_OBJECT_DESCRIPTORS 85
+
+typedef enum  {
+        MIN_OBJ_TYPE    = 0,
+
+        FMLP_SEM        = 0,
+        SRP_SEM         = 1,
+
+        MPCP_SEM        = 2,
+        MPCP_VS_SEM     = 3,
+        DPCP_SEM        = 4,
+
+        PCP_SEM         = 5,
+
+        MAX_OBJ_TYPE    = 5
+} obj_type_t;
+
+struct inode_obj_id {
+        struct list_head        list;
+        atomic_t                count;
+        struct inode*           inode;
+
+        obj_type_t              type;
+        void*                   obj;
+        unsigned int            id;
+};
+
+struct fdso_ops;
+
+struct od_table_entry {
+        unsigned int            used;
+
+        struct inode_obj_id*    obj;
+        const struct fdso_ops*  class;
+};
+
+struct fdso_ops {
+        int   (*create)(void** obj_ref, obj_type_t type, void* __user);
+        void  (*destroy)(obj_type_t type, void*);
+        int   (*open)   (struct od_table_entry*, void* __user);
+        int   (*close)  (struct od_table_entry*);
+};
+
+/* translate a userspace supplied od into the raw table entry
+ * returns NULL if od is invalid
+ */
+struct od_table_entry* get_entry_for_od(int od);
+
+/* translate a userspace supplied od into the associated object
+ * returns NULL if od is invalid
+ */
+static inline void* od_lookup(int od, obj_type_t type)
+{
+        struct od_table_entry* e = get_entry_for_od(od);
+        return e && e->obj->type == type ? e->obj->obj : NULL;
+}
+
+#define lookup_fmlp_sem(od)((struct pi_semaphore*)  od_lookup(od, FMLP_SEM))
+#define lookup_srp_sem(od) ((struct srp_semaphore*) od_lookup(od, SRP_SEM))
+#define lookup_ics(od)     ((struct ics*)           od_lookup(od, ICS_ID))
+
+
+#endif
diff --git a/include/litmus/fp_common.h b/include/litmus/fp_common.h
new file mode 100644
index 000000000000..19356c0fa6c1
--- /dev/null
+++ b/include/litmus/fp_common.h
@@ -0,0 +1,105 @@
+/* Fixed-priority scheduler support.
+ */
+
+#ifndef __FP_COMMON_H__
+#define __FP_COMMON_H__
+
+#include <litmus/rt_domain.h>
+
+#include <asm/bitops.h>
+
+
+void fp_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
+                    release_jobs_t release);
+
+int fp_higher_prio(struct task_struct* first,
+                   struct task_struct* second);
+
+int fp_ready_order(struct bheap_node* a, struct bheap_node* b);
+
+#define FP_PRIO_BIT_WORDS (LITMUS_MAX_PRIORITY / BITS_PER_LONG)
+
+#if (LITMUS_MAX_PRIORITY % BITS_PER_LONG)
+#error LITMUS_MAX_PRIORITY must be a multiple of BITS_PER_LONG
+#endif
+
+/* bitmask-inexed priority queue */
+struct fp_prio_queue {
+        unsigned long   bitmask[FP_PRIO_BIT_WORDS];
+        struct bheap    queue[LITMUS_MAX_PRIORITY];
+};
+
+void fp_prio_queue_init(struct fp_prio_queue* q);
+
+static inline void fpq_set(struct fp_prio_queue* q, unsigned int index)
+{
+        unsigned long *word = q->bitmask + (index / BITS_PER_LONG);
+        __set_bit(index % BITS_PER_LONG, word);
+}
+
+static inline void fpq_clear(struct fp_prio_queue* q, unsigned int index)
+{
+        unsigned long *word = q->bitmask + (index / BITS_PER_LONG);
+        __clear_bit(index % BITS_PER_LONG, word);
+}
+
+static inline unsigned int fpq_find(struct fp_prio_queue* q)
+{
+        int i;
+
+        /* loop optimizer should unroll this */
+        for (i = 0; i < FP_PRIO_BIT_WORDS; i++)
+                if (q->bitmask[i])
+                        return __ffs(q->bitmask[i]) + i * BITS_PER_LONG;
+
+        return LITMUS_MAX_PRIORITY; /* nothing found */
+}
+
+static inline void fp_prio_add(struct fp_prio_queue* q, struct task_struct* t, unsigned int index)
+{
+        BUG_ON(index >= LITMUS_MAX_PRIORITY);
+        BUG_ON(bheap_node_in_heap(tsk_rt(t)->heap_node));
+
+        fpq_set(q, index);
+        bheap_insert(fp_ready_order, &q->queue[index], tsk_rt(t)->heap_node);
+}
+
+static inline void fp_prio_remove(struct fp_prio_queue* q, struct task_struct* t, unsigned int index)
+{
+        BUG_ON(!is_queued(t));
+
+        bheap_delete(fp_ready_order, &q->queue[index], tsk_rt(t)->heap_node);
+        if (likely(bheap_empty(&q->queue[index])))
+                fpq_clear(q, index);
+}
+
+static inline struct task_struct* fp_prio_peek(struct fp_prio_queue* q)
+{
+        unsigned int idx = fpq_find(q);
+        struct bheap_node* hn;
+
+        if (idx < LITMUS_MAX_PRIORITY) {
+                hn = bheap_peek(fp_ready_order, &q->queue[idx]);
+                return bheap2task(hn);
+        } else
+                return NULL;
+}
+
+static inline struct task_struct* fp_prio_take(struct fp_prio_queue* q)
+{
+        unsigned int idx = fpq_find(q);
+        struct bheap_node* hn;
+
+        if (idx < LITMUS_MAX_PRIORITY) {
+                hn = bheap_take(fp_ready_order, &q->queue[idx]);
+                if (likely(bheap_empty(&q->queue[idx])))
+                        fpq_clear(q, idx);
+                return bheap2task(hn);
+        } else
+                return NULL;
+}
+
+int fp_preemption_needed(struct fp_prio_queue*  q, struct task_struct *t);
+
+
+#endif
diff --git a/include/litmus/fpmath.h b/include/litmus/fpmath.h
new file mode 100644
index 000000000000..642de98542c8
--- /dev/null
+++ b/include/litmus/fpmath.h
@@ -0,0 +1,147 @@
+#ifndef __FP_MATH_H__
+#define __FP_MATH_H__
+
+#include <linux/math64.h>
+
+#ifndef __KERNEL__
+#include <stdint.h>
+#define abs(x) (((x) < 0) ? -(x) : x)
+#endif
+
+// Use 64-bit because we want to track things at the nanosecond scale.
+// This can lead to very large numbers.
+typedef int64_t fpbuf_t;
+typedef struct
+{
+        fpbuf_t val;
+} fp_t;
+
+#define FP_SHIFT 10
+#define ROUND_BIT (FP_SHIFT - 1)
+
+#define _fp(x) ((fp_t) {x})
+
+#ifdef __KERNEL__
+static const fp_t LITMUS_FP_ZERO = {.val = 0};
+static const fp_t LITMUS_FP_ONE = {.val = (1 << FP_SHIFT)};
+#endif
+
+static inline fp_t FP(fpbuf_t x)
+{
+        return _fp(((fpbuf_t) x) << FP_SHIFT);
+}
+
+/* divide two integers to obtain a fixed point value  */
+static inline fp_t _frac(fpbuf_t a, fpbuf_t b)
+{
+        return _fp(div64_s64(FP(a).val, (b)));
+}
+
+static inline fpbuf_t _point(fp_t x)
+{
+        return (x.val % (1 << FP_SHIFT));
+
+}
+
+#define fp2str(x) x.val
+/*(x.val >> FP_SHIFT), (x.val % (1 << FP_SHIFT)) */
+#define _FP_  "%ld/1024"
+
+static inline fpbuf_t _floor(fp_t x)
+{
+        return x.val >> FP_SHIFT;
+}
+
+/* FIXME: negative rounding */
+static inline fpbuf_t _round(fp_t x)
+{
+        return _floor(x) + ((x.val >> ROUND_BIT) & 1);
+}
+
+/* multiply two fixed point values */
+static inline fp_t _mul(fp_t a, fp_t b)
+{
+        return _fp((a.val * b.val) >> FP_SHIFT);
+}
+
+static inline fp_t _div(fp_t a, fp_t b)
+{
+#if !defined(__KERNEL__) && !defined(unlikely)
+#define unlikely(x) (x)
+#define DO_UNDEF_UNLIKELY
+#endif
+        /* try not to overflow */
+        if (unlikely(  a.val > (2l << ((sizeof(fpbuf_t)*8) - FP_SHIFT)) ))
+                return _fp((a.val / b.val) << FP_SHIFT);
+        else
+                return _fp((a.val << FP_SHIFT) / b.val);
+#ifdef DO_UNDEF_UNLIKELY
+#undef unlikely
+#undef DO_UNDEF_UNLIKELY
+#endif
+}
+
+static inline fp_t _add(fp_t a, fp_t b)
+{
+        return _fp(a.val + b.val);
+}
+
+static inline fp_t _sub(fp_t a, fp_t b)
+{
+        return _fp(a.val - b.val);
+}
+
+static inline fp_t _neg(fp_t x)
+{
+        return _fp(-x.val);
+}
+
+static inline fp_t _abs(fp_t x)
+{
+        return _fp(abs(x.val));
+}
+
+/* works the same as casting float/double to integer */
+static inline fpbuf_t _fp_to_integer(fp_t x)
+{
+        return _floor(_abs(x)) * ((x.val > 0) ? 1 : -1);
+}
+
+static inline fp_t _integer_to_fp(fpbuf_t x)
+{
+        return _frac(x,1);
+}
+
+static inline int _leq(fp_t a, fp_t b)
+{
+        return a.val <= b.val;
+}
+
+static inline int _geq(fp_t a, fp_t b)
+{
+        return a.val >= b.val;
+}
+
+static inline int _lt(fp_t a, fp_t b)
+{
+        return a.val < b.val;
+}
+
+static inline int _gt(fp_t a, fp_t b)
+{
+        return a.val > b.val;
+}
+
+static inline int _eq(fp_t a, fp_t b)
+{
+        return a.val == b.val;
+}
+
+static inline fp_t _max(fp_t a, fp_t b)
+{
+        if (a.val < b.val)
+                return b;
+        else
+                return a;
+}
+#endif
diff --git a/include/litmus/jobs.h b/include/litmus/jobs.h
new file mode 100644
index 000000000000..e1507d4314b8
--- /dev/null
+++ b/include/litmus/jobs.h
@@ -0,0 +1,8 @@
+#ifndef __LITMUS_JOBS_H__
+#define __LITMUS_JOBS_H__
+
+void prepare_for_next_period(struct task_struct *t);
+void release_at(struct task_struct *t, lt_t start);
+long complete_job(void);
+
+#endif
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index c87863c9b231..e35c38c4c0a2 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -6,7 +6,41 @@
 #ifndef _LINUX_LITMUS_H_
 #define _LINUX_LITMUS_H_
 
+#include <litmus/debug_trace.h>
+
+#ifdef CONFIG_RELEASE_MASTER
+extern atomic_t release_master_cpu;
+#endif
+
+/* in_list - is a given list_head queued on some list?
+ */
+static inline int in_list(struct list_head* list)
+{
+        return !(  /* case 1: deleted */
+                   (list->next == LIST_POISON1 &&
+                    list->prev == LIST_POISON2)
+                 ||
+                   /* case 2: initialized */
+                   (list->next == list &&
+                    list->prev == list)
+                );
+}
+
+struct task_struct* __waitqueue_remove_first(wait_queue_head_t *wq);
+
+#define NO_CPU                  0xffffffff
+
+void litmus_fork(struct task_struct *tsk);
+void litmus_exec(void);
+/* clean up real-time state of a task */
+void exit_litmus(struct task_struct *dead_tsk);
+
+long litmus_admit_task(struct task_struct *tsk);
+void litmus_exit_task(struct task_struct *tsk);
+
 #define is_realtime(t)          ((t)->policy == SCHED_LITMUS)
+#define rt_transition_pending(t) \
+        ((t)->rt_param.transition_pending)
 
 #define tsk_rt(t)               (&(t)->rt_param)
 
@@ -28,6 +62,7 @@
 #define get_partition(t)        (tsk_rt(t)->task_params.cpu)
 #define get_priority(t)         (tsk_rt(t)->task_params.priority)
 #define get_class(t)        (tsk_rt(t)->task_params.cls)
+#define get_release_policy(t) (tsk_rt(t)->task_params.release_policy)
 
 /* job_param macros */
 #define get_exec_time(t)    (tsk_rt(t)->job_params.exec_time)
@@ -35,6 +70,15 @@
 #define get_release(t)          (tsk_rt(t)->job_params.release)
 #define get_lateness(t)         (tsk_rt(t)->job_params.lateness)
 
+/* release policy macros */
+#define is_periodic(t)          (get_release_policy(t) == TASK_PERIODIC)
+#define is_sporadic(t)          (get_release_policy(t) == TASK_SPORADIC)
+#ifdef CONFIG_ALLOW_EARLY_RELEASE
+#define is_early_releasing(t)   (get_release_policy(t) == TASK_EARLY)
+#else
+#define is_early_releasing(t)   (0)
+#endif
+
 #define is_hrt(t)               \
         (tsk_rt(t)->task_params.cls == RT_CLASS_HARD)
 #define is_srt(t)               \
@@ -48,6 +92,192 @@ static inline lt_t litmus_clock(void)
         return ktime_to_ns(ktime_get());
 }
 
+/* A macro to convert from nanoseconds to ktime_t. */
+#define ns_to_ktime(t)          ktime_add_ns(ktime_set(0, 0), t)
+
+#define get_domain(t) (tsk_rt(t)->domain)
+
+/* Honor the flag in the preempt_count variable that is set
+ * when scheduling is in progress.
+ */
+#define is_running(t)                   \
+        ((t)->state == TASK_RUNNING ||  \
+         task_thread_info(t)->preempt_count & PREEMPT_ACTIVE)
+
+#define is_blocked(t)       \
+        (!is_running(t))
+#define is_released(t, now)     \
+        (lt_before_eq(get_release(t), now))
+#define is_tardy(t, now)    \
+        (lt_before_eq(tsk_rt(t)->job_params.deadline, now))
+
+/* real-time comparison macros */
+#define earlier_deadline(a, b) (lt_before(\
+        (a)->rt_param.job_params.deadline,\
+        (b)->rt_param.job_params.deadline))
+#define earlier_release(a, b)  (lt_before(\
+        (a)->rt_param.job_params.release,\
+        (b)->rt_param.job_params.release))
+
+void preempt_if_preemptable(struct task_struct* t, int on_cpu);
+
+#ifdef CONFIG_LITMUS_LOCKING
+void srp_ceiling_block(void);
+#else
+#define srp_ceiling_block() /* nothing */
+#endif
+
+#define bheap2task(hn) ((struct task_struct*) hn->value)
+
+#ifdef CONFIG_NP_SECTION
+
+static inline int is_kernel_np(struct task_struct *t)
+{
+        return tsk_rt(t)->kernel_np;
+}
+
+static inline int is_user_np(struct task_struct *t)
+{
+        return tsk_rt(t)->ctrl_page ? tsk_rt(t)->ctrl_page->sched.np.flag : 0;
+}
+
+static inline void request_exit_np(struct task_struct *t)
+{
+        if (is_user_np(t)) {
+                /* Set the flag that tells user space to call
+                 * into the kernel at the end of a critical section. */
+                if (likely(tsk_rt(t)->ctrl_page)) {
+                        TRACE_TASK(t, "setting delayed_preemption flag\n");
+                        tsk_rt(t)->ctrl_page->sched.np.preempt = 1;
+                }
+        }
+}
+
+static inline void make_np(struct task_struct *t)
+{
+        tsk_rt(t)->kernel_np++;
+}
+
+/* Caller should check if preemption is necessary when
+ * the function return 0.
+ */
+static inline int take_np(struct task_struct *t)
+{
+        return --tsk_rt(t)->kernel_np;
+}
+
+/* returns 0 if remote CPU needs an IPI to preempt, 1 if no IPI is required */
+static inline int request_exit_np_atomic(struct task_struct *t)
+{
+        union np_flag old, new;
+
+        if (tsk_rt(t)->ctrl_page) {
+                old.raw = tsk_rt(t)->ctrl_page->sched.raw;
+                if (old.np.flag == 0) {
+                        /* no longer non-preemptive */
+                        return 0;
+                } else if (old.np.preempt) {
+                        /* already set, nothing for us to do */
+                        return 1;
+                } else {
+                        /* non preemptive and flag not set */
+                        new.raw = old.raw;
+                        new.np.preempt = 1;
+                        /* if we get old back, then we atomically set the flag */
+                        return cmpxchg(&tsk_rt(t)->ctrl_page->sched.raw, old.raw, new.raw) == old.raw;
+                        /* If we raced with a concurrent change, then so be
+                         * it. Deliver it by IPI.  We don't want an unbounded
+                         * retry loop here since tasks might exploit that to
+                         * keep the kernel busy indefinitely. */
+                }
+        } else
+                return 0;
+}
+
+#else
+
+static inline int is_kernel_np(struct task_struct* t)
+{
+        return 0;
+}
+
+static inline int is_user_np(struct task_struct* t)
+{
+        return 0;
+}
+
+static inline void request_exit_np(struct task_struct *t)
+{
+        /* request_exit_np() shouldn't be called if !CONFIG_NP_SECTION */
+        BUG();
+}
+
+static inline int request_exit_np_atomic(struct task_struct *t)
+{
+        return 0;
+}
+
+#endif
+
+static inline void clear_exit_np(struct task_struct *t)
+{
+        if (likely(tsk_rt(t)->ctrl_page))
+                tsk_rt(t)->ctrl_page->sched.np.preempt = 0;
+}
+
+static inline int is_np(struct task_struct *t)
+{
+#ifdef CONFIG_SCHED_DEBUG_TRACE
+        int kernel, user;
+        kernel = is_kernel_np(t);
+        user   = is_user_np(t);
+        if (kernel || user)
+                TRACE_TASK(t, " is non-preemptive: kernel=%d user=%d\n",
+
+                           kernel, user);
+        return kernel || user;
+#else
+        return unlikely(is_kernel_np(t) || is_user_np(t));
+#endif
+}
+
+static inline int is_present(struct task_struct* t)
+{
+        return t && tsk_rt(t)->present;
+}
+
+static inline int is_completed(struct task_struct* t)
+{
+        return t && tsk_rt(t)->completed;
+}
+
+
+/* make the unit explicit */
+typedef unsigned long quanta_t;
+
+enum round {
+        FLOOR,
+        CEIL
+};
+
+
+/* Tick period is used to convert ns-specified execution
+ * costs and periods into tick-based equivalents.
+ */
+extern ktime_t tick_period;
+
+static inline quanta_t time2quanta(lt_t time, enum round round)
+{
+        s64  quantum_length = ktime_to_ns(tick_period);
+
+        if (do_div(time, quantum_length) && round == CEIL)
+                time++;
+        return (quanta_t) time;
+}
+
+/* By how much is cpu staggered behind CPU 0? */
+u64 cpu_stagger_offset(int cpu);
+
 static inline struct control_page* get_control_page(struct task_struct *t)
 {
         return tsk_rt(t)->ctrl_page;
@@ -58,4 +288,29 @@ static inline int has_control_page(struct task_struct* t)
         return tsk_rt(t)->ctrl_page != NULL;
 }
 
+
+#ifdef CONFIG_SCHED_OVERHEAD_TRACE
+
+#define TS_SYSCALL_IN_START                                             \
+        if (has_control_page(current)) {                                \
+                __TS_SYSCALL_IN_START(&get_control_page(current)->ts_syscall_start); \
+        }
+
+#define TS_SYSCALL_IN_END                                               \
+        if (has_control_page(current)) {                                \
+                uint64_t irqs;                                          \
+                local_irq_disable();                                    \
+                irqs = get_control_page(current)->irq_count -           \
+                        get_control_page(current)->irq_syscall_start;   \
+                __TS_SYSCALL_IN_END(&irqs);                             \
+                local_irq_enable();                                     \
+        }
+
+#else
+
+#define TS_SYSCALL_IN_START
+#define TS_SYSCALL_IN_END
+
+#endif
+
 #endif
diff --git a/include/litmus/litmus_proc.h b/include/litmus/litmus_proc.h
new file mode 100644
index 000000000000..6800e725d48c
--- /dev/null
+++ b/include/litmus/litmus_proc.h
@@ -0,0 +1,25 @@
+#include <litmus/sched_plugin.h>
+#include <linux/proc_fs.h>
+
+int __init init_litmus_proc(void);
+void exit_litmus_proc(void);
+
+/*
+ * On success, returns 0 and sets the pointer to the location of the new
+ * proc dir entry, otherwise returns an error code and sets pde to NULL.
+ */
+long make_plugin_proc_dir(struct sched_plugin* plugin,
+                struct proc_dir_entry** pde);
+
+/*
+ * Plugins should deallocate all child proc directory entries before
+ * calling this, to avoid memory leaks.
+ */
+void remove_plugin_proc_dir(struct sched_plugin* plugin);
+
+
+/* Copy at most size-1 bytes from ubuf into kbuf, null-terminate buf, and
+ * remove a '\n' if present. Returns the number of bytes that were read or
+ * -EFAULT. */
+int copy_and_chomp(char *kbuf, unsigned long ksize,
+                   __user const char* ubuf, unsigned long ulength);
diff --git a/include/litmus/locking.h b/include/litmus/locking.h
new file mode 100644
index 000000000000..4d7b870cb443
--- /dev/null
+++ b/include/litmus/locking.h
@@ -0,0 +1,28 @@
+#ifndef LITMUS_LOCKING_H
+#define LITMUS_LOCKING_H
+
+struct litmus_lock_ops;
+
+/* Generic base struct for LITMUS^RT userspace semaphores.
+ * This structure should be embedded in protocol-specific semaphores.
+ */
+struct litmus_lock {
+        struct litmus_lock_ops *ops;
+        int type;
+};
+
+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*);
+
+        /* Current tries to lock/unlock this lock (mandatory methods). */
+        int (*lock)(struct litmus_lock*);
+        int (*unlock)(struct litmus_lock*);
+
+        /* The lock is no longer being referenced (mandatory method). */
+        void (*deallocate)(struct litmus_lock*);
+};
+
+#endif
diff --git a/include/litmus/preempt.h b/include/litmus/preempt.h
new file mode 100644
index 000000000000..4fd108a45333
--- /dev/null
+++ b/include/litmus/preempt.h
@@ -0,0 +1,164 @@
+#ifndef LITMUS_PREEMPT_H
+#define LITMUS_PREEMPT_H
+
+#include <linux/types.h>
+#include <linux/cache.h>
+#include <linux/percpu.h>
+#include <asm/atomic.h>
+
+#include <litmus/debug_trace.h>
+
+DECLARE_PER_CPU_SHARED_ALIGNED(atomic_t, resched_state);
+
+#ifdef CONFIG_PREEMPT_STATE_TRACE
+const char* sched_state_name(int s);
+#define TRACE_STATE(fmt, args...) TRACE("SCHED_STATE " fmt, args)
+#else
+#define TRACE_STATE(fmt, args...) /* ignore */
+#endif
+
+#define VERIFY_SCHED_STATE(x)                                           \
+        do { int __s = get_sched_state();                               \
+                if ((__s & (x)) == 0)                                   \
+                        TRACE_STATE("INVALID s=0x%x (%s) not "          \
+                                    "in 0x%x (%s) [%s]\n",              \
+                                    __s, sched_state_name(__s),         \
+                                    (x), #x, __FUNCTION__);             \
+        } while (0);
+
+#define TRACE_SCHED_STATE_CHANGE(x, y, cpu)                             \
+        TRACE_STATE("[P%d] 0x%x (%s) -> 0x%x (%s)\n",                   \
+                    cpu,  (x), sched_state_name(x),                     \
+                    (y), sched_state_name(y))
+
+
+typedef enum scheduling_state {
+        TASK_SCHEDULED    = (1 << 0),  /* The currently scheduled task is the one that
+                                        * should be scheduled, and the processor does not
+                                        * plan to invoke schedule(). */
+        SHOULD_SCHEDULE   = (1 << 1),  /* A remote processor has determined that the
+                                        * processor should reschedule, but this has not
+                                        * been communicated yet (IPI still pending). */
+        WILL_SCHEDULE     = (1 << 2),  /* The processor has noticed that it has to
+                                        * reschedule and will do so shortly. */
+        TASK_PICKED       = (1 << 3),  /* The processor is currently executing schedule(),
+                                        * has selected a new task to schedule, but has not
+                                        * yet performed the actual context switch. */
+        PICKED_WRONG_TASK = (1 << 4),  /* The processor has not yet performed the context
+                                        * switch, but a remote processor has already
+                                        * determined that a higher-priority task became
+                                        * eligible after the task was picked. */
+} sched_state_t;
+
+static inline sched_state_t get_sched_state_on(int cpu)
+{
+        return atomic_read(&per_cpu(resched_state, cpu));
+}
+
+static inline sched_state_t get_sched_state(void)
+{
+        return atomic_read(&__get_cpu_var(resched_state));
+}
+
+static inline int is_in_sched_state(int possible_states)
+{
+        return get_sched_state() & possible_states;
+}
+
+static inline int cpu_is_in_sched_state(int cpu, int possible_states)
+{
+        return get_sched_state_on(cpu) & possible_states;
+}
+
+static inline void set_sched_state(sched_state_t s)
+{
+        TRACE_SCHED_STATE_CHANGE(get_sched_state(), s, smp_processor_id());
+        atomic_set(&__get_cpu_var(resched_state), s);
+}
+
+static inline int sched_state_transition(sched_state_t from, sched_state_t to)
+{
+        sched_state_t old_state;
+
+        old_state = atomic_cmpxchg(&__get_cpu_var(resched_state), from, to);
+        if (old_state == from) {
+                TRACE_SCHED_STATE_CHANGE(from, to, smp_processor_id());
+                return 1;
+        } else
+                return 0;
+}
+
+static inline int sched_state_transition_on(int cpu,
+                                            sched_state_t from,
+                                            sched_state_t to)
+{
+        sched_state_t old_state;
+
+        old_state = atomic_cmpxchg(&per_cpu(resched_state, cpu), from, to);
+        if (old_state == from) {
+                TRACE_SCHED_STATE_CHANGE(from, to, cpu);
+                return 1;
+        } else
+                return 0;
+}
+
+/* Plugins must call this function after they have decided which job to
+ * schedule next.  IMPORTANT: this function must be called while still holding
+ * the lock that is used to serialize scheduling decisions.
+ *
+ * (Ideally, we would like to use runqueue locks for this purpose, but that
+ * would lead to deadlocks with the migration code.)
+ */
+static inline void sched_state_task_picked(void)
+{
+        VERIFY_SCHED_STATE(WILL_SCHEDULE);
+
+        /* WILL_SCHEDULE has only a local tansition => simple store is ok */
+        set_sched_state(TASK_PICKED);
+}
+
+static inline void sched_state_entered_schedule(void)
+{
+        /* Update state for the case that we entered schedule() not due to
+         * set_tsk_need_resched() */
+        set_sched_state(WILL_SCHEDULE);
+}
+
+/* Called by schedule() to check if the scheduling decision is still valid
+ * after a context switch. Returns 1 if the CPU needs to reschdule. */
+static inline int sched_state_validate_switch(void)
+{
+        int left_state_ok = 0;
+
+        VERIFY_SCHED_STATE(PICKED_WRONG_TASK | TASK_PICKED);
+
+        if (is_in_sched_state(TASK_PICKED)) {
+                /* Might be good; let's try to transition out of this
+                 * state. This must be done atomically since remote processors
+                 * may try to change the state, too. */
+                left_state_ok = sched_state_transition(TASK_PICKED, TASK_SCHEDULED);
+        }
+
+        if (!left_state_ok) {
+                /* We raced with a higher-priority task arrival => not
+                 * valid. The CPU needs to reschedule. */
+                set_sched_state(WILL_SCHEDULE);
+                return 1;
+        } else
+                return 0;
+}
+
+/* State transition events. See litmus/preempt.c for details. */
+void sched_state_will_schedule(struct task_struct* tsk);
+void sched_state_ipi(void);
+/* Cause a CPU (remote or local) to reschedule. */
+void litmus_reschedule(int cpu);
+void litmus_reschedule_local(void);
+
+#ifdef CONFIG_DEBUG_KERNEL
+void sched_state_plugin_check(void);
+#else
+#define sched_state_plugin_check() /* no check */
+#endif
+
+#endif
diff --git a/include/litmus/rt_domain.h b/include/litmus/rt_domain.h
new file mode 100644
index 000000000000..ac249292e866
--- /dev/null
+++ b/include/litmus/rt_domain.h
@@ -0,0 +1,182 @@
+/* CLEANUP: Add comments and make it less messy.
+ *
+ */
+
+#ifndef __UNC_RT_DOMAIN_H__
+#define __UNC_RT_DOMAIN_H__
+
+#include <litmus/bheap.h>
+
+#define RELEASE_QUEUE_SLOTS 127 /* prime */
+
+struct _rt_domain;
+
+typedef int (*check_resched_needed_t)(struct _rt_domain *rt);
+typedef void (*release_jobs_t)(struct _rt_domain *rt, struct bheap* tasks);
+
+struct release_queue {
+        /* each slot maintains a list of release heaps sorted
+         * by release time */
+        struct list_head                slot[RELEASE_QUEUE_SLOTS];
+};
+
+typedef struct _rt_domain {
+        /* runnable rt tasks are in here */
+        raw_spinlock_t                  ready_lock;
+        struct bheap                    ready_queue;
+
+        /* real-time tasks waiting for release are in here */
+        raw_spinlock_t                  release_lock;
+        struct release_queue            release_queue;
+
+#ifdef CONFIG_RELEASE_MASTER
+        int                             release_master;
+#endif
+
+        /* for moving tasks to the release queue */
+        raw_spinlock_t                  tobe_lock;
+        struct list_head                tobe_released;
+
+        /* how do we check if we need to kick another CPU? */
+        check_resched_needed_t          check_resched;
+
+        /* how do we release jobs? */
+        release_jobs_t                  release_jobs;
+
+        /* how are tasks ordered in the ready queue? */
+        bheap_prio_t                    order;
+} rt_domain_t;
+
+struct release_heap {
+        /* list_head for per-time-slot list */
+        struct list_head                list;
+        lt_t                            release_time;
+        /* all tasks to be released at release_time */
+        struct bheap                    heap;
+        /* used to trigger the release */
+        struct hrtimer                  timer;
+
+#ifdef CONFIG_RELEASE_MASTER
+        /* used to delegate releases */
+        struct hrtimer_start_on_info    info;
+#endif
+        /* required for the timer callback */
+        rt_domain_t*                    dom;
+};
+
+
+static inline struct task_struct* __next_ready(rt_domain_t* rt)
+{
+        struct bheap_node *hn = bheap_peek(rt->order, &rt->ready_queue);
+        if (hn)
+                return bheap2task(hn);
+        else
+                return NULL;
+}
+
+void rt_domain_init(rt_domain_t *rt, bheap_prio_t order,
+                    check_resched_needed_t check,
+                    release_jobs_t relase);
+
+void __add_ready(rt_domain_t* rt, struct task_struct *new);
+void __merge_ready(rt_domain_t* rt, struct bheap *tasks);
+void __add_release(rt_domain_t* rt, struct task_struct *task);
+
+static inline struct task_struct* __take_ready(rt_domain_t* rt)
+{
+        struct bheap_node* hn = bheap_take(rt->order, &rt->ready_queue);
+        if (hn)
+                return bheap2task(hn);
+        else
+                return NULL;
+}
+
+static inline struct task_struct* __peek_ready(rt_domain_t* rt)
+{
+        struct bheap_node* hn = bheap_peek(rt->order, &rt->ready_queue);
+        if (hn)
+                return bheap2task(hn);
+        else
+                return NULL;
+}
+
+static inline int  is_queued(struct task_struct *t)
+{
+        BUG_ON(!tsk_rt(t)->heap_node);
+        return bheap_node_in_heap(tsk_rt(t)->heap_node);
+}
+
+static inline void remove(rt_domain_t* rt, struct task_struct *t)
+{
+        bheap_delete(rt->order, &rt->ready_queue, tsk_rt(t)->heap_node);
+}
+
+static inline void add_ready(rt_domain_t* rt, struct task_struct *new)
+{
+        unsigned long flags;
+        /* first we need the write lock for rt_ready_queue */
+        raw_spin_lock_irqsave(&rt->ready_lock, flags);
+        __add_ready(rt, new);
+        raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
+}
+
+static inline void merge_ready(rt_domain_t* rt, struct bheap* tasks)
+{
+        unsigned long flags;
+        raw_spin_lock_irqsave(&rt->ready_lock, flags);
+        __merge_ready(rt, tasks);
+        raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
+}
+
+static inline struct task_struct* take_ready(rt_domain_t* rt)
+{
+        unsigned long flags;
+        struct task_struct* ret;
+        /* first we need the write lock for rt_ready_queue */
+        raw_spin_lock_irqsave(&rt->ready_lock, flags);
+        ret = __take_ready(rt);
+        raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
+        return ret;
+}
+
+
+static inline void add_release(rt_domain_t* rt, struct task_struct *task)
+{
+        unsigned long flags;
+        raw_spin_lock_irqsave(&rt->tobe_lock, flags);
+        __add_release(rt, task);
+        raw_spin_unlock_irqrestore(&rt->tobe_lock, flags);
+}
+
+#ifdef CONFIG_RELEASE_MASTER
+void __add_release_on(rt_domain_t* rt, struct task_struct *task,
+                      int target_cpu);
+
+static inline void add_release_on(rt_domain_t* rt,
+                                  struct task_struct *task,
+                                  int target_cpu)
+{
+        unsigned long flags;
+        raw_spin_lock_irqsave(&rt->tobe_lock, flags);
+        __add_release_on(rt, task, target_cpu);
+        raw_spin_unlock_irqrestore(&rt->tobe_lock, flags);
+}
+#endif
+
+static inline int __jobs_pending(rt_domain_t* rt)
+{
+        return !bheap_empty(&rt->ready_queue);
+}
+
+static inline int jobs_pending(rt_domain_t* rt)
+{
+        unsigned long flags;
+        int ret;
+        /* first we need the write lock for rt_ready_queue */
+        raw_spin_lock_irqsave(&rt->ready_lock, flags);
+        ret = !bheap_empty(&rt->ready_queue);
+        raw_spin_unlock_irqrestore(&rt->ready_lock, flags);
+        return ret;
+}
+
+#endif
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index a1fed7653377..138799fbaad7 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -84,12 +84,12 @@ struct rt_task {
 };
 
 union np_flag {
-        uint64_t raw;
+        uint32_t raw;
         struct {
                 /* Is the task currently in a non-preemptive section? */
-                uint64_t flag:31;
+                uint32_t flag:31;
                 /* Should the task call into the scheduler? */
-                uint64_t preempt:1;
+                uint32_t preempt:1;
         } np;
 };
 
@@ -110,10 +110,10 @@ union np_flag {
 struct control_page {
         /* This flag is used by userspace to communicate non-preempive
          * sections. */
-        volatile union np_flag sched;
+        volatile __attribute__ ((aligned (8))) union np_flag sched;
 
-        volatile uint64_t irq_count; /* Incremented by the kernel each time an IRQ is
-                                      * handled. */
+        /* Incremented by the kernel each time an IRQ is handled. */
+        volatile __attribute__ ((aligned (8))) uint64_t irq_count;
 
         /* Locking overhead tracing: userspace records here the time stamp
          * and IRQ counter prior to starting the system call. */
diff --git a/include/litmus/sched_plugin.h b/include/litmus/sched_plugin.h
new file mode 100644
index 000000000000..0f2fe90123db
--- /dev/null
+++ b/include/litmus/sched_plugin.h
@@ -0,0 +1,114 @@
+/*
+ * Definition of the scheduler plugin interface.
+ *
+ */
+#ifndef _LINUX_SCHED_PLUGIN_H_
+#define _LINUX_SCHED_PLUGIN_H_
+
+#include <linux/sched.h>
+
+#ifdef CONFIG_LITMUS_LOCKING
+#include <litmus/locking.h>
+#endif
+
+/************************ setup/tear down ********************/
+
+typedef long (*activate_plugin_t) (void);
+typedef long (*deactivate_plugin_t) (void);
+
+
+
+/********************* scheduler invocation ******************/
+
+/*  Plugin-specific realtime tick handler */
+typedef void (*scheduler_tick_t) (struct task_struct *cur);
+/* Novell make sched decision function */
+typedef struct task_struct* (*schedule_t)(struct task_struct * prev);
+/* Clean up after the task switch has occured.
+ * This function is called after every (even non-rt) task switch.
+ */
+typedef void (*finish_switch_t)(struct task_struct *prev);
+
+
+/********************* task state changes ********************/
+
+/* Called to setup a new real-time task.
+ * Release the first job, enqueue, etc.
+ * Task may already be running.
+ */
+typedef void (*task_new_t) (struct task_struct *task,
+                            int on_rq,
+                            int running);
+
+/* Called to re-introduce a task after blocking.
+ * Can potentially be called multiple times.
+ */
+typedef void (*task_wake_up_t) (struct task_struct *task);
+/* called to notify the plugin of a blocking real-time task
+ * it will only be called for real-time tasks and before schedule is called */
+typedef void (*task_block_t)  (struct task_struct *task);
+/* Called when a real-time task exits or changes to a different scheduling
+ * class.
+ * Free any allocated resources
+ */
+typedef void (*task_exit_t)    (struct task_struct *);
+
+#ifdef CONFIG_LITMUS_LOCKING
+/* Called when the current task attempts to create a new lock of a given
+ * protocol type. */
+typedef long (*allocate_lock_t) (struct litmus_lock **lock, int type,
+                                 void* __user config);
+#endif
+
+
+/********************* sys call backends  ********************/
+/* This function causes the caller to sleep until the next release */
+typedef long (*complete_job_t) (void);
+
+typedef long (*admit_task_t)(struct task_struct* tsk);
+
+typedef void (*release_at_t)(struct task_struct *t, lt_t start);
+
+struct sched_plugin {
+        struct list_head        list;
+        /*      basic info              */
+        char                    *plugin_name;
+
+        /*      setup                   */
+        activate_plugin_t       activate_plugin;
+        deactivate_plugin_t     deactivate_plugin;
+
+        /*      scheduler invocation    */
+        scheduler_tick_t        tick;
+        schedule_t              schedule;
+        finish_switch_t         finish_switch;
+
+        /*      syscall backend         */
+        complete_job_t          complete_job;
+        release_at_t            release_at;
+
+        /*      task state changes      */
+        admit_task_t            admit_task;
+
+        task_new_t              task_new;
+        task_wake_up_t          task_wake_up;
+        task_block_t            task_block;
+        task_exit_t             task_exit;
+
+#ifdef CONFIG_LITMUS_LOCKING
+        /*      locking protocols       */
+        allocate_lock_t         allocate_lock;
+#endif
+} __attribute__ ((__aligned__(SMP_CACHE_BYTES)));
+
+
+extern struct sched_plugin *litmus;
+
+int register_sched_plugin(struct sched_plugin* plugin);
+struct sched_plugin* find_sched_plugin(const char* name);
+void print_sched_plugins(struct seq_file *m);
+
+
+extern struct sched_plugin linux_sched_plugin;
+
+#endif
diff --git a/include/litmus/srp.h b/include/litmus/srp.h
new file mode 100644
index 000000000000..c9a4552b2bf3
--- /dev/null
+++ b/include/litmus/srp.h
@@ -0,0 +1,28 @@
+#ifndef LITMUS_SRP_H
+#define LITMUS_SRP_H
+
+struct srp_semaphore;
+
+struct srp_priority {
+        struct list_head        list;
+        unsigned int            priority;
+        pid_t                   pid;
+};
+#define list2prio(l) list_entry(l, struct srp_priority, list)
+
+/* struct for uniprocessor SRP "semaphore" */
+struct srp_semaphore {
+        struct litmus_lock litmus_lock;
+        struct srp_priority ceiling;
+        struct task_struct* owner;
+        int cpu; /* cpu associated with this "semaphore" and resource */
+};
+
+/* map a task to its SRP preemption level priority */
+typedef unsigned int (*srp_prioritization_t)(struct task_struct* t);
+/* Must be updated by each plugin that uses SRP.*/
+extern srp_prioritization_t get_srp_prio;
+
+struct srp_semaphore* allocate_srp_semaphore(void);
+
+#endif
diff --git a/include/litmus/unistd_32.h b/include/litmus/unistd_32.h
new file mode 100644
index 000000000000..94264c27d9ac
--- /dev/null
+++ b/include/litmus/unistd_32.h
@@ -0,0 +1,21 @@
+/*
+ * included from arch/x86/include/asm/unistd_32.h
+ *
+ * LITMUS^RT syscalls with "relative" numbers
+ */
+#define __LSC(x) (__NR_LITMUS + x)
+
+#define __NR_set_rt_task_param  __LSC(0)
+#define __NR_get_rt_task_param  __LSC(1)
+#define __NR_complete_job       __LSC(2)
+#define __NR_od_open            __LSC(3)
+#define __NR_od_close           __LSC(4)
+#define __NR_litmus_lock        __LSC(5)
+#define __NR_litmus_unlock      __LSC(6)
+#define __NR_query_job_no       __LSC(7)
+#define __NR_wait_for_job_release __LSC(8)
+#define __NR_wait_for_ts_release __LSC(9)
+#define __NR_release_ts         __LSC(10)
+#define __NR_null_call          __LSC(11)
+
+#define NR_litmus_syscalls 12
diff --git a/include/litmus/unistd_64.h b/include/litmus/unistd_64.h
new file mode 100644
index 000000000000..d5ced0d2642c
--- /dev/null
+++ b/include/litmus/unistd_64.h
@@ -0,0 +1,33 @@
+/*
+ * included from arch/x86/include/asm/unistd_64.h
+ *
+ * LITMUS^RT syscalls with "relative" numbers
+ */
+#define __LSC(x) (__NR_LITMUS + x)
+
+#define __NR_set_rt_task_param                  __LSC(0)
+__SYSCALL(__NR_set_rt_task_param, sys_set_rt_task_param)
+#define __NR_get_rt_task_param                  __LSC(1)
+__SYSCALL(__NR_get_rt_task_param, sys_get_rt_task_param)
+#define __NR_complete_job                       __LSC(2)
+__SYSCALL(__NR_complete_job, sys_complete_job)
+#define __NR_od_open                            __LSC(3)
+__SYSCALL(__NR_od_open, sys_od_open)
+#define __NR_od_close                           __LSC(4)
+__SYSCALL(__NR_od_close, sys_od_close)
+#define __NR_litmus_lock                        __LSC(5)
+__SYSCALL(__NR_litmus_lock, sys_litmus_lock)
+#define __NR_litmus_unlock                      __LSC(6)
+__SYSCALL(__NR_litmus_unlock, sys_litmus_unlock)
+#define __NR_query_job_no                       __LSC(7)
+__SYSCALL(__NR_query_job_no, sys_query_job_no)
+#define __NR_wait_for_job_release               __LSC(8)
+__SYSCALL(__NR_wait_for_job_release, sys_wait_for_job_release)
+#define __NR_wait_for_ts_release                __LSC(9)
+__SYSCALL(__NR_wait_for_ts_release, sys_wait_for_ts_release)
+#define __NR_release_ts                         __LSC(10)
+__SYSCALL(__NR_release_ts, sys_release_ts)
+#define __NR_null_call                          __LSC(11)
+__SYSCALL(__NR_null_call, sys_null_call)
+
+#define NR_litmus_syscalls 12
diff --git a/include/litmus/wait.h b/include/litmus/wait.h
new file mode 100644
index 000000000000..ce1347c355f8
--- /dev/null
+++ b/include/litmus/wait.h
@@ -0,0 +1,57 @@
+#ifndef _LITMUS_WAIT_H_
+#define _LITMUS_WAIT_H_
+
+struct task_struct* __waitqueue_remove_first(wait_queue_head_t *wq);
+
+/* wrap regular wait_queue_t head */
+struct __prio_wait_queue {
+        wait_queue_t wq;
+
+        /* some priority point */
+        lt_t priority;
+        /* break ties in priority by lower tie_breaker */
+        unsigned int tie_breaker;
+};
+
+typedef struct __prio_wait_queue prio_wait_queue_t;
+
+static inline void init_prio_waitqueue_entry(prio_wait_queue_t *pwq,
+                                             struct task_struct* t,
+                                             lt_t priority)
+{
+        init_waitqueue_entry(&pwq->wq, t);
+        pwq->priority    = priority;
+        pwq->tie_breaker = 0;
+}
+
+static inline void init_prio_waitqueue_entry_tie(prio_wait_queue_t *pwq,
+                                                 struct task_struct* t,
+                                                 lt_t priority,
+                                                 unsigned int tie_breaker)
+{
+        init_waitqueue_entry(&pwq->wq, t);
+        pwq->priority    = priority;
+        pwq->tie_breaker = tie_breaker;
+}
+
+unsigned int __add_wait_queue_prio_exclusive(
+        wait_queue_head_t* head,
+        prio_wait_queue_t *new);
+
+static inline unsigned int add_wait_queue_prio_exclusive(
+        wait_queue_head_t* head,
+        prio_wait_queue_t *new)
+{
+        unsigned long flags;
+        unsigned int passed;
+
+        spin_lock_irqsave(&head->lock, flags);
+        passed = __add_wait_queue_prio_exclusive(head, new);
+
+        spin_unlock_irqrestore(&head->lock, flags);
+
+        return passed;
+}
+
+
+#endif