From c0667dc4894e913048cf8904f0ce9a79b481b556 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 13 Apr 2012 16:18:03 -0400 Subject: Move RSM and IKGLP imp. to own .c files Also reformated code to be slightly more standard coding practice compliant. --- include/litmus/ikglp_lock.h | 97 +++++++++++++++++++++++++++++++++++++++++++ include/litmus/locking.h | 94 ++++++++++++++++++++++++++--------------- include/litmus/rsm_lock.h | 54 ++++++++++++++++++++++++ include/litmus/sched_plugin.h | 14 ++++++- 4 files changed, 225 insertions(+), 34 deletions(-) create mode 100644 include/litmus/ikglp_lock.h create mode 100644 include/litmus/rsm_lock.h (limited to 'include') 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 +#include +#include + +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 +#include +#include + +/* 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 -- cgit v1.2.2