aboutsummaryrefslogtreecommitdiffstats
path: root/include
diff options
context:
space:
mode:
authorGlenn Elliott <gelliott@cs.unc.edu>2013-10-30 18:30:58 -0400
committerGlenn Elliott <gelliott@cs.unc.edu>2014-03-03 10:07:32 -0500
commit39b8d26fb9bba4984d4d912cb8a31e04d99fb3d5 (patch)
tree7f5f9b25967d5dfae72cbf2f83c751126fb9736b /include
parentd377bc02d8b79f89a28e39c70a934c499f6c2347 (diff)
Add ikglp.
Adds an implementation of the ikglp. Supports both affinity and nesting of other locks within the ikglp (the ikglp itself must be an outer-most lock).
Diffstat (limited to 'include')
-rw-r--r--include/litmus/ikglp_lock.h233
-rw-r--r--include/litmus/rt_param.h12
2 files changed, 245 insertions, 0 deletions
diff --git a/include/litmus/ikglp_lock.h b/include/litmus/ikglp_lock.h
new file mode 100644
index 000000000000..c85c8c280299
--- /dev/null
+++ b/include/litmus/ikglp_lock.h
@@ -0,0 +1,233 @@
1#ifndef LITMUS_IKGLP_H
2#define LITMUS_IKGLP_H
3
4#include <litmus/litmus.h>
5#include <litmus/binheap.h>
6#include <litmus/locking.h>
7
8#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
9#include <litmus/kexclu_affinity.h>
10struct ikglp_affinity;
11#endif
12
13typedef struct ikglp_heap_node
14{
15 struct task_struct *task;
16 struct binheap_node node;
17} ikglp_heap_node_t;
18
19struct fifo_queue;
20struct ikglp_wait_state;
21struct fifo_queue;
22
23typedef struct ikglp_donee_heap_node
24{
25 struct task_struct *task;
26 struct fifo_queue *fq;
27
28 /* cross-linked with ikglp_wait_state_t of donor */
29 struct ikglp_wait_state *donor_info;
30
31 struct binheap_node node;
32} ikglp_donee_heap_node_t;
33
34typedef enum ikglp_states
35{
36 IKGLP_INVL = 0,
37 IKGLP_FQ,
38 IKGLP_PQ,
39 IKGLP_DONOR
40} ikglp_states_t;
41
42/*
43 Maintains the state of a request as it goes through the IKGLP.
44 There are three exclusive wait states:
45 (1) as a donor
46 (2) in the PQ
47 (3) in the FQ
48*/
49typedef struct ikglp_wait_state {
50 struct task_struct *task; /* pointer back to the requesting task */
51
52 ikglp_states_t cur_q;
53 /* data for x-highest-prio tasks */
54 ikglp_heap_node_t global_heap_node;
55
56 /* TODO: put these fields in an appropriate union since wait
57 states are exclusive. */
58
59 /** Data for whilst in FIFO Queue **/
60 wait_queue_t fq_node;
61 struct fifo_queue *fq;
62 ikglp_donee_heap_node_t donee_heap_node;
63
64 /** Data for whilst in PQ **/
65 ikglp_heap_node_t pq_node;
66
67 /** Data for whilst a donor **/
68 /* cross-linked with donee's ikglp_donee_heap_node_t */
69 ikglp_donee_heap_node_t *donee_info;
70 struct nested_info prio_donation;
71 struct binheap_node node;
72} ikglp_wait_state_t;
73
74/* struct for FIFO mutex with priority inheritance */
75struct fifo_queue
76{
77 wait_queue_head_t wait;
78 struct task_struct* owner;
79
80 /* used for bookkeepping */
81 ikglp_heap_node_t global_heap_node;
82 ikglp_donee_heap_node_t donee_heap_node;
83
84 struct task_struct* hp_waiter;
85 unsigned int count; /* number of waiters + holder */
86
87 struct nested_info nest;
88
89 /* Asserted if owner has 'virtually' unlocked the FIFO's replica.
90 * See rule B2 in Brandenburg's "Virtually Exclusive Resources"
91 * tech report MPI_SWS-2012-005.
92 *
93 * In this implementation, allows the FIFO queue to temporarily
94 * grow by one past it's maximum size.
95 */
96 unsigned int is_vunlocked:1;
97};
98
99/* Main IKGLP data structure. */
100struct ikglp_semaphore
101{
102 struct litmus_lock litmus_lock;
103
104 raw_spinlock_t lock;
105 raw_spinlock_t real_lock;
106
107 unsigned int nr_replicas; /* AKA k */
108 unsigned int max_fifo_len; /* max len of a fifo queue */
109
110 unsigned int max_in_fifos;
111 unsigned int nr_in_fifos;
112
113 struct binheap top_m; /* min heap, base prio */
114 unsigned int top_m_size; /* number of nodes in top_m */
115
116 struct binheap not_top_m; /* max heap, ordered by base priority */
117
118 struct binheap donees; /* min-heap, ordered by base priority */
119
120 /* cached value - pointer to shortest fifo queue */
121 struct fifo_queue *shortest_fifo_queue;
122
123 /* data structures for holding requests */
124 struct fifo_queue *fifo_queues; /* array nr_replicas in length */
125 struct binheap priority_queue; /* max-heap, ordered by base priority */
126 struct binheap donors; /* max-heap, ordered by base priority */
127
128#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
129 struct ikglp_affinity *aff_obs; /* pointer to affinity observer */
130#endif
131};
132
133static inline struct ikglp_semaphore* ikglp_from_lock(struct litmus_lock* lock)
134{
135 return container_of(lock, struct ikglp_semaphore, litmus_lock);
136}
137
138int ikglp_lock(struct litmus_lock* l);
139int ikglp_unlock(struct litmus_lock* l);
140void ikglp_virtual_unlock(struct litmus_lock* l, struct task_struct* t);
141void ikglp_budget_exhausted(struct litmus_lock* l, struct task_struct* t);
142
143int ikglp_close(struct litmus_lock* l);
144void ikglp_free(struct litmus_lock* l);
145struct litmus_lock* ikglp_new(unsigned int m, struct litmus_lock_ops*,
146 void* __user arg);
147
148#ifdef CONFIG_LITMUS_AFFINITY_LOCKING
149struct ikglp_queue_info
150{
151 struct fifo_queue* q;
152 lt_t estimated_len;
153 unsigned int *nr_cur_users;
154 unsigned int *nr_aff_users;
155};
156
157/* routines for IKGLP to call to get advice on queueing operations */
158typedef struct fifo_queue* (*advise_enqueue_t)(struct ikglp_affinity* aff,
159 struct task_struct* t);
160typedef ikglp_wait_state_t* (*advise_steal_t)(struct ikglp_affinity* aff,
161 struct fifo_queue* dst);
162typedef ikglp_donee_heap_node_t* (*advise_donee_t)(struct ikglp_affinity* aff,
163 struct task_struct* t);
164typedef ikglp_wait_state_t* (*advise_donor_t)(struct ikglp_affinity* aff,
165 struct fifo_queue* dst);
166
167/* routines for IKGLP to notify the affinity observer about changes in mutex state */
168typedef void (*notify_enqueue_t)(struct ikglp_affinity* aff,
169 struct fifo_queue* fq, struct task_struct* t);
170typedef void (*notify_dequeue_t)(struct ikglp_affinity* aff,
171 struct fifo_queue* fq, struct task_struct* t);
172typedef void (*notify_acquire_t)(struct ikglp_affinity* aff,
173 struct fifo_queue* fq, struct task_struct* t);
174typedef void (*notify_free_t)(struct ikglp_affinity* aff,
175 struct fifo_queue* fq, struct task_struct* t);
176typedef int (*notify_exit_t)(struct ikglp_affinity* aff,
177 struct task_struct* t);
178
179/* convert a replica # to a GPU (includes offsets & simult user folding) */
180typedef int (*replica_to_resource_t)(struct ikglp_affinity* aff,
181 struct fifo_queue* fq);
182
183struct ikglp_affinity_ops
184{
185 advise_enqueue_t advise_enqueue;
186 advise_steal_t advise_steal;
187 advise_donee_t advise_donee_selection;
188 advise_donor_t advise_donor_to_fq;
189
190 notify_enqueue_t notify_enqueue;
191 notify_dequeue_t notify_dequeue;
192 notify_acquire_t notify_acquired;
193 notify_free_t notify_freed;
194 notify_exit_t notify_exit;
195
196 replica_to_resource_t replica_to_resource;
197};
198
199struct ikglp_affinity
200{
201 struct affinity_observer obs;
202 struct ikglp_affinity_ops *ops;
203 struct ikglp_queue_info *q_info;
204 unsigned int *nr_cur_users_on_rsrc;
205 unsigned int *nr_aff_on_rsrc;
206 unsigned int offset;
207 unsigned int nr_simult;
208 unsigned int nr_rsrc;
209
210 unsigned int relax_max_fifo_len:1;
211};
212
213static inline struct ikglp_affinity* ikglp_aff_obs_from_aff_obs(
214 struct affinity_observer* aff_obs)
215{
216 return container_of(aff_obs, struct ikglp_affinity, obs);
217}
218
219int ikglp_aff_obs_close(struct affinity_observer*);
220void ikglp_aff_obs_free(struct affinity_observer*);
221
222#ifdef CONFIG_LITMUS_NVIDIA
223struct affinity_observer* ikglp_gpu_aff_obs_new(
224 struct affinity_observer_ops* aff,
225 void* __user arg);
226struct affinity_observer* ikglp_simple_gpu_aff_obs_new(
227 struct affinity_observer_ops* aff,
228 void* __user arg);
229#endif /* end LITMUS_NVIDIA */
230
231#endif /* end LITMUS_AFFINITY_LOCKING */
232
233#endif
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 966f197041dc..9a1193383f56 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -98,6 +98,18 @@ struct affinity_observer_args
98 int lock_od; 98 int lock_od;
99}; 99};
100 100
101#define IKGLP_M_IN_FIFOS (0u)
102#define IKGLP_UNLIMITED_IN_FIFOS (~0u)
103#define IKGLP_OPTIMAL_FIFO_LEN (0u)
104#define IKGLP_UNLIMITED_FIFO_LEN (~0u)
105
106struct ikglp_args
107{
108 unsigned int nr_replicas;
109 unsigned int max_in_fifos;
110 unsigned int max_fifo_len;
111};
112
101/* The definition of the data that is shared between the kernel and real-time 113/* The definition of the data that is shared between the kernel and real-time
102 * tasks via a shared page (see litmus/ctrldev.c). 114 * tasks via a shared page (see litmus/ctrldev.c).
103 * 115 *
generated by cgit v1.2.2 (git 2.25.0) at 2025-09-06 15:20:09 -0400