diff options
author | Bjoern Brandenburg <bbb@mpi-sws.org> | 2013-02-12 13:16:03 -0500 |
---|---|---|
committer | Namhoon Kim <namhoonk@cs.unc.edu> | 2014-10-21 10:08:27 -0400 |
commit | 8fcdf62f4db13de12ae638c8e7e3535858fb8d95 (patch) | |
tree | 670c600a64b7a8c44688d65a045cd82838a307f4 | |
parent | ad5164aa251591c954a084a51aaa866c1380e7b3 (diff) |
Add GSN-EDF scheduler plugin
-rw-r--r-- | litmus/Makefile | 1 | ||||
-rw-r--r-- | litmus/sched_gsn_edf.c | 1069 |
2 files changed, 1070 insertions, 0 deletions
diff --git a/litmus/Makefile b/litmus/Makefile index 0db695e35201..c01ce3e7a101 100644 --- a/litmus/Makefile +++ b/litmus/Makefile | |||
@@ -19,6 +19,7 @@ obj-y = sched_plugin.o litmus.o \ | |||
19 | binheap.o \ | 19 | binheap.o \ |
20 | ctrldev.o \ | 20 | ctrldev.o \ |
21 | uncachedev.o \ | 21 | uncachedev.o \ |
22 | sched_gsn_edf.o \ | ||
22 | sched_psn_edf.o | 23 | sched_psn_edf.o |
23 | 24 | ||
24 | 25 | ||
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c new file mode 100644 index 000000000000..9307d0b76404 --- /dev/null +++ b/litmus/sched_gsn_edf.c | |||
@@ -0,0 +1,1069 @@ | |||
1 | /* | ||
2 | * litmus/sched_gsn_edf.c | ||
3 | * | ||
4 | * Implementation of the GSN-EDF scheduling algorithm. | ||
5 | * | ||
6 | * This version uses the simple approach and serializes all scheduling | ||
7 | * decisions by the use of a queue lock. This is probably not the | ||
8 | * best way to do it, but it should suffice for now. | ||
9 | */ | ||
10 | |||
11 | #include <linux/spinlock.h> | ||
12 | #include <linux/percpu.h> | ||
13 | #include <linux/sched.h> | ||
14 | #include <linux/slab.h> | ||
15 | |||
16 | #include <litmus/litmus.h> | ||
17 | #include <litmus/jobs.h> | ||
18 | #include <litmus/sched_plugin.h> | ||
19 | #include <litmus/edf_common.h> | ||
20 | #include <litmus/sched_trace.h> | ||
21 | #include <litmus/trace.h> | ||
22 | |||
23 | #include <litmus/preempt.h> | ||
24 | #include <litmus/budget.h> | ||
25 | |||
26 | #include <litmus/bheap.h> | ||
27 | |||
28 | #ifdef CONFIG_SCHED_CPU_AFFINITY | ||
29 | #include <litmus/affinity.h> | ||
30 | #endif | ||
31 | |||
32 | /* to set up domain/cpu mappings */ | ||
33 | #include <litmus/litmus_proc.h> | ||
34 | |||
35 | #include <linux/module.h> | ||
36 | |||
37 | /* Overview of GSN-EDF operations. | ||
38 | * | ||
39 | * For a detailed explanation of GSN-EDF have a look at the FMLP paper. This | ||
40 | * description only covers how the individual operations are implemented in | ||
41 | * LITMUS. | ||
42 | * | ||
43 | * link_task_to_cpu(T, cpu) - Low-level operation to update the linkage | ||
44 | * structure (NOT the actually scheduled | ||
45 | * task). If there is another linked task To | ||
46 | * already it will set To->linked_on = NO_CPU | ||
47 | * (thereby removing its association with this | ||
48 | * CPU). However, it will not requeue the | ||
49 | * previously linked task (if any). It will set | ||
50 | * T's state to not completed and check whether | ||
51 | * it is already running somewhere else. If T | ||
52 | * is scheduled somewhere else it will link | ||
53 | * it to that CPU instead (and pull the linked | ||
54 | * task to cpu). T may be NULL. | ||
55 | * | ||
56 | * unlink(T) - Unlink removes T from all scheduler data | ||
57 | * structures. If it is linked to some CPU it | ||
58 | * will link NULL to that CPU. If it is | ||
59 | * currently queued in the gsnedf queue it will | ||
60 | * be removed from the rt_domain. It is safe to | ||
61 | * call unlink(T) if T is not linked. T may not | ||
62 | * be NULL. | ||
63 | * | ||
64 | * requeue(T) - Requeue will insert T into the appropriate | ||
65 | * queue. If the system is in real-time mode and | ||
66 | * the T is released already, it will go into the | ||
67 | * ready queue. If the system is not in | ||
68 | * real-time mode is T, then T will go into the | ||
69 | * release queue. If T's release time is in the | ||
70 | * future, it will go into the release | ||
71 | * queue. That means that T's release time/job | ||
72 | * no/etc. has to be updated before requeu(T) is | ||
73 | * called. It is not safe to call requeue(T) | ||
74 | * when T is already queued. T may not be NULL. | ||
75 | * | ||
76 | * gsnedf_job_arrival(T) - This is the catch all function when T enters | ||
77 | * the system after either a suspension or at a | ||
78 | * job release. It will queue T (which means it | ||
79 | * is not safe to call gsnedf_job_arrival(T) if | ||
80 | * T is already queued) and then check whether a | ||
81 | * preemption is necessary. If a preemption is | ||
82 | * necessary it will update the linkage | ||
83 | * accordingly and cause scheduled to be called | ||
84 | * (either with an IPI or need_resched). It is | ||
85 | * safe to call gsnedf_job_arrival(T) if T's | ||
86 | * next job has not been actually released yet | ||
87 | * (releast time in the future). T will be put | ||
88 | * on the release queue in that case. | ||
89 | * | ||
90 | * job_completion(T) - Take care of everything that needs to be done | ||
91 | * to prepare T for its next release and place | ||
92 | * it in the right queue with | ||
93 | * gsnedf_job_arrival(). | ||
94 | * | ||
95 | * | ||
96 | * When we now that T is linked to CPU then link_task_to_cpu(NULL, CPU) is | ||
97 | * equivalent to unlink(T). Note that if you unlink a task from a CPU none of | ||
98 | * the functions will automatically propagate pending task from the ready queue | ||
99 | * to a linked task. This is the job of the calling function ( by means of | ||
100 | * __take_ready). | ||
101 | */ | ||
102 | |||
103 | |||
104 | /* cpu_entry_t - maintain the linked and scheduled state | ||
105 | */ | ||
106 | typedef struct { | ||
107 | int cpu; | ||
108 | struct task_struct* linked; /* only RT tasks */ | ||
109 | struct task_struct* scheduled; /* only RT tasks */ | ||
110 | struct bheap_node* hn; | ||
111 | } cpu_entry_t; | ||
112 | DEFINE_PER_CPU(cpu_entry_t, gsnedf_cpu_entries); | ||
113 | |||
114 | cpu_entry_t* gsnedf_cpus[NR_CPUS]; | ||
115 | |||
116 | /* the cpus queue themselves according to priority in here */ | ||
117 | static struct bheap_node gsnedf_heap_node[NR_CPUS]; | ||
118 | static struct bheap gsnedf_cpu_heap; | ||
119 | |||
120 | static rt_domain_t gsnedf; | ||
121 | #define gsnedf_lock (gsnedf.ready_lock) | ||
122 | |||
123 | |||
124 | /* Uncomment this if you want to see all scheduling decisions in the | ||
125 | * TRACE() log. | ||
126 | #define WANT_ALL_SCHED_EVENTS | ||
127 | */ | ||
128 | |||
129 | static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b) | ||
130 | { | ||
131 | cpu_entry_t *a, *b; | ||
132 | a = _a->value; | ||
133 | b = _b->value; | ||
134 | /* Note that a and b are inverted: we want the lowest-priority CPU at | ||
135 | * the top of the heap. | ||
136 | */ | ||
137 | return edf_higher_prio(b->linked, a->linked); | ||
138 | } | ||
139 | |||
140 | /* update_cpu_position - Move the cpu entry to the correct place to maintain | ||
141 | * order in the cpu queue. Caller must hold gsnedf lock. | ||
142 | */ | ||
143 | static void update_cpu_position(cpu_entry_t *entry) | ||
144 | { | ||
145 | if (likely(bheap_node_in_heap(entry->hn))) | ||
146 | bheap_delete(cpu_lower_prio, &gsnedf_cpu_heap, entry->hn); | ||
147 | bheap_insert(cpu_lower_prio, &gsnedf_cpu_heap, entry->hn); | ||
148 | } | ||
149 | |||
150 | /* caller must hold gsnedf lock */ | ||
151 | static cpu_entry_t* lowest_prio_cpu(void) | ||
152 | { | ||
153 | struct bheap_node* hn; | ||
154 | hn = bheap_peek(cpu_lower_prio, &gsnedf_cpu_heap); | ||
155 | return hn->value; | ||
156 | } | ||
157 | |||
158 | |||
159 | /* link_task_to_cpu - Update the link of a CPU. | ||
160 | * Handles the case where the to-be-linked task is already | ||
161 | * scheduled on a different CPU. | ||
162 | */ | ||
163 | static noinline void link_task_to_cpu(struct task_struct* linked, | ||
164 | cpu_entry_t *entry) | ||
165 | { | ||
166 | cpu_entry_t *sched; | ||
167 | struct task_struct* tmp; | ||
168 | int on_cpu; | ||
169 | |||
170 | BUG_ON(linked && !is_realtime(linked)); | ||
171 | |||
172 | /* Currently linked task is set to be unlinked. */ | ||
173 | if (entry->linked) { | ||
174 | entry->linked->rt_param.linked_on = NO_CPU; | ||
175 | } | ||
176 | |||
177 | /* Link new task to CPU. */ | ||
178 | if (linked) { | ||
179 | /* handle task is already scheduled somewhere! */ | ||
180 | on_cpu = linked->rt_param.scheduled_on; | ||
181 | if (on_cpu != NO_CPU) { | ||
182 | sched = &per_cpu(gsnedf_cpu_entries, on_cpu); | ||
183 | /* this should only happen if not linked already */ | ||
184 | BUG_ON(sched->linked == linked); | ||
185 | |||
186 | /* If we are already scheduled on the CPU to which we | ||
187 | * wanted to link, we don't need to do the swap -- | ||
188 | * we just link ourselves to the CPU and depend on | ||
189 | * the caller to get things right. | ||
190 | */ | ||
191 | if (entry != sched) { | ||
192 | TRACE_TASK(linked, | ||
193 | "already scheduled on %d, updating link.\n", | ||
194 | sched->cpu); | ||
195 | tmp = sched->linked; | ||
196 | linked->rt_param.linked_on = sched->cpu; | ||
197 | sched->linked = linked; | ||
198 | update_cpu_position(sched); | ||
199 | linked = tmp; | ||
200 | } | ||
201 | } | ||
202 | if (linked) /* might be NULL due to swap */ | ||
203 | linked->rt_param.linked_on = entry->cpu; | ||
204 | } | ||
205 | entry->linked = linked; | ||
206 | #ifdef WANT_ALL_SCHED_EVENTS | ||
207 | if (linked) | ||
208 | TRACE_TASK(linked, "linked to %d.\n", entry->cpu); | ||
209 | else | ||
210 | TRACE("NULL linked to %d.\n", entry->cpu); | ||
211 | #endif | ||
212 | update_cpu_position(entry); | ||
213 | } | ||
214 | |||
215 | /* unlink - Make sure a task is not linked any longer to an entry | ||
216 | * where it was linked before. Must hold gsnedf_lock. | ||
217 | */ | ||
218 | static noinline void unlink(struct task_struct* t) | ||
219 | { | ||
220 | cpu_entry_t *entry; | ||
221 | |||
222 | if (t->rt_param.linked_on != NO_CPU) { | ||
223 | /* unlink */ | ||
224 | entry = &per_cpu(gsnedf_cpu_entries, t->rt_param.linked_on); | ||
225 | t->rt_param.linked_on = NO_CPU; | ||
226 | link_task_to_cpu(NULL, entry); | ||
227 | } else if (is_queued(t)) { | ||
228 | /* This is an interesting situation: t is scheduled, | ||
229 | * but was just recently unlinked. It cannot be | ||
230 | * linked anywhere else (because then it would have | ||
231 | * been relinked to this CPU), thus it must be in some | ||
232 | * queue. We must remove it from the list in this | ||
233 | * case. | ||
234 | */ | ||
235 | remove(&gsnedf, t); | ||
236 | } | ||
237 | } | ||
238 | |||
239 | |||
240 | /* preempt - force a CPU to reschedule | ||
241 | */ | ||
242 | static void preempt(cpu_entry_t *entry) | ||
243 | { | ||
244 | preempt_if_preemptable(entry->scheduled, entry->cpu); | ||
245 | } | ||
246 | |||
247 | /* requeue - Put an unlinked task into gsn-edf domain. | ||
248 | * Caller must hold gsnedf_lock. | ||
249 | */ | ||
250 | static noinline void requeue(struct task_struct* task) | ||
251 | { | ||
252 | BUG_ON(!task); | ||
253 | /* sanity check before insertion */ | ||
254 | BUG_ON(is_queued(task)); | ||
255 | |||
256 | if (is_early_releasing(task) || is_released(task, litmus_clock())) | ||
257 | __add_ready(&gsnedf, task); | ||
258 | else { | ||
259 | /* it has got to wait */ | ||
260 | add_release(&gsnedf, task); | ||
261 | } | ||
262 | } | ||
263 | |||
264 | #ifdef CONFIG_SCHED_CPU_AFFINITY | ||
265 | static cpu_entry_t* gsnedf_get_nearest_available_cpu(cpu_entry_t *start) | ||
266 | { | ||
267 | cpu_entry_t *affinity; | ||
268 | |||
269 | get_nearest_available_cpu(affinity, start, gsnedf_cpu_entries, | ||
270 | #ifdef CONFIG_RELEASE_MASTER | ||
271 | gsnedf.release_master | ||
272 | #else | ||
273 | NO_CPU | ||
274 | #endif | ||
275 | ); | ||
276 | |||
277 | return(affinity); | ||
278 | } | ||
279 | #endif | ||
280 | |||
281 | /* check for any necessary preemptions */ | ||
282 | static void check_for_preemptions(void) | ||
283 | { | ||
284 | struct task_struct *task; | ||
285 | cpu_entry_t *last; | ||
286 | |||
287 | |||
288 | #ifdef CONFIG_PREFER_LOCAL_LINKING | ||
289 | cpu_entry_t *local; | ||
290 | |||
291 | /* Before linking to other CPUs, check first whether the local CPU is | ||
292 | * idle. */ | ||
293 | local = &__get_cpu_var(gsnedf_cpu_entries); | ||
294 | task = __peek_ready(&gsnedf); | ||
295 | |||
296 | if (task && !local->linked | ||
297 | #ifdef CONFIG_RELEASE_MASTER | ||
298 | && likely(local->cpu != gsnedf.release_master) | ||
299 | #endif | ||
300 | ) { | ||
301 | task = __take_ready(&gsnedf); | ||
302 | TRACE_TASK(task, "linking to local CPU %d to avoid IPI\n", local->cpu); | ||
303 | link_task_to_cpu(task, local); | ||
304 | preempt(local); | ||
305 | } | ||
306 | #endif | ||
307 | |||
308 | for (last = lowest_prio_cpu(); | ||
309 | edf_preemption_needed(&gsnedf, last->linked); | ||
310 | last = lowest_prio_cpu()) { | ||
311 | /* preemption necessary */ | ||
312 | task = __take_ready(&gsnedf); | ||
313 | TRACE("check_for_preemptions: attempting to link task %d to %d\n", | ||
314 | task->pid, last->cpu); | ||
315 | |||
316 | #ifdef CONFIG_SCHED_CPU_AFFINITY | ||
317 | { | ||
318 | cpu_entry_t *affinity = | ||
319 | gsnedf_get_nearest_available_cpu( | ||
320 | &per_cpu(gsnedf_cpu_entries, task_cpu(task))); | ||
321 | if (affinity) | ||
322 | last = affinity; | ||
323 | else if (requeue_preempted_job(last->linked)) | ||
324 | requeue(last->linked); | ||
325 | } | ||
326 | #else | ||
327 | if (requeue_preempted_job(last->linked)) | ||
328 | requeue(last->linked); | ||
329 | #endif | ||
330 | |||
331 | link_task_to_cpu(task, last); | ||
332 | preempt(last); | ||
333 | } | ||
334 | } | ||
335 | |||
336 | /* gsnedf_job_arrival: task is either resumed or released */ | ||
337 | static noinline void gsnedf_job_arrival(struct task_struct* task) | ||
338 | { | ||
339 | BUG_ON(!task); | ||
340 | |||
341 | requeue(task); | ||
342 | check_for_preemptions(); | ||
343 | } | ||
344 | |||
345 | static void gsnedf_release_jobs(rt_domain_t* rt, struct bheap* tasks) | ||
346 | { | ||
347 | unsigned long flags; | ||
348 | |||
349 | raw_spin_lock_irqsave(&gsnedf_lock, flags); | ||
350 | |||
351 | __merge_ready(rt, tasks); | ||
352 | check_for_preemptions(); | ||
353 | |||
354 | raw_spin_unlock_irqrestore(&gsnedf_lock, flags); | ||
355 | } | ||
356 | |||
357 | /* caller holds gsnedf_lock */ | ||
358 | static noinline void job_completion(struct task_struct *t, int forced) | ||
359 | { | ||
360 | BUG_ON(!t); | ||
361 | |||
362 | sched_trace_task_completion(t, forced); | ||
363 | |||
364 | TRACE_TASK(t, "job_completion().\n"); | ||
365 | |||
366 | /* set flags */ | ||
367 | tsk_rt(t)->completed = 0; | ||
368 | /* prepare for next period */ | ||
369 | prepare_for_next_period(t); | ||
370 | if (is_early_releasing(t) || is_released(t, litmus_clock())) | ||
371 | sched_trace_task_release(t); | ||
372 | /* unlink */ | ||
373 | unlink(t); | ||
374 | /* requeue | ||
375 | * But don't requeue a blocking task. */ | ||
376 | if (is_running(t)) | ||
377 | gsnedf_job_arrival(t); | ||
378 | } | ||
379 | |||
380 | /* Getting schedule() right is a bit tricky. schedule() may not make any | ||
381 | * assumptions on the state of the current task since it may be called for a | ||
382 | * number of reasons. The reasons include a scheduler_tick() determined that it | ||
383 | * was necessary, because sys_exit_np() was called, because some Linux | ||
384 | * subsystem determined so, or even (in the worst case) because there is a bug | ||
385 | * hidden somewhere. Thus, we must take extreme care to determine what the | ||
386 | * current state is. | ||
387 | * | ||
388 | * The CPU could currently be scheduling a task (or not), be linked (or not). | ||
389 | * | ||
390 | * The following assertions for the scheduled task could hold: | ||
391 | * | ||
392 | * - !is_running(scheduled) // the job blocks | ||
393 | * - scheduled->timeslice == 0 // the job completed (forcefully) | ||
394 | * - is_completed() // the job completed (by syscall) | ||
395 | * - linked != scheduled // we need to reschedule (for any reason) | ||
396 | * - is_np(scheduled) // rescheduling must be delayed, | ||
397 | * sys_exit_np must be requested | ||
398 | * | ||
399 | * Any of these can occur together. | ||
400 | */ | ||
401 | static struct task_struct* gsnedf_schedule(struct task_struct * prev) | ||
402 | { | ||
403 | cpu_entry_t* entry = &__get_cpu_var(gsnedf_cpu_entries); | ||
404 | int out_of_time, sleep, preempt, np, exists, blocks; | ||
405 | struct task_struct* next = NULL; | ||
406 | |||
407 | #ifdef CONFIG_RELEASE_MASTER | ||
408 | /* Bail out early if we are the release master. | ||
409 | * The release master never schedules any real-time tasks. | ||
410 | */ | ||
411 | if (unlikely(gsnedf.release_master == entry->cpu)) { | ||
412 | sched_state_task_picked(); | ||
413 | return NULL; | ||
414 | } | ||
415 | #endif | ||
416 | |||
417 | raw_spin_lock(&gsnedf_lock); | ||
418 | |||
419 | /* sanity checking */ | ||
420 | BUG_ON(entry->scheduled && entry->scheduled != prev); | ||
421 | BUG_ON(entry->scheduled && !is_realtime(prev)); | ||
422 | BUG_ON(is_realtime(prev) && !entry->scheduled); | ||
423 | |||
424 | /* (0) Determine state */ | ||
425 | exists = entry->scheduled != NULL; | ||
426 | blocks = exists && !is_running(entry->scheduled); | ||
427 | out_of_time = exists && budget_enforced(entry->scheduled) | ||
428 | && budget_exhausted(entry->scheduled); | ||
429 | np = exists && is_np(entry->scheduled); | ||
430 | sleep = exists && is_completed(entry->scheduled); | ||
431 | preempt = entry->scheduled != entry->linked; | ||
432 | |||
433 | #ifdef WANT_ALL_SCHED_EVENTS | ||
434 | TRACE_TASK(prev, "invoked gsnedf_schedule.\n"); | ||
435 | #endif | ||
436 | |||
437 | if (exists) | ||
438 | TRACE_TASK(prev, | ||
439 | "blocks:%d out_of_time:%d np:%d sleep:%d preempt:%d " | ||
440 | "state:%d sig:%d\n", | ||
441 | blocks, out_of_time, np, sleep, preempt, | ||
442 | prev->state, signal_pending(prev)); | ||
443 | if (entry->linked && preempt) | ||
444 | TRACE_TASK(prev, "will be preempted by %s/%d\n", | ||
445 | entry->linked->comm, entry->linked->pid); | ||
446 | |||
447 | |||
448 | /* If a task blocks we have no choice but to reschedule. | ||
449 | */ | ||
450 | if (blocks) | ||
451 | unlink(entry->scheduled); | ||
452 | |||
453 | /* Request a sys_exit_np() call if we would like to preempt but cannot. | ||
454 | * We need to make sure to update the link structure anyway in case | ||
455 | * that we are still linked. Multiple calls to request_exit_np() don't | ||
456 | * hurt. | ||
457 | */ | ||
458 | if (np && (out_of_time || preempt || sleep)) { | ||
459 | unlink(entry->scheduled); | ||
460 | request_exit_np(entry->scheduled); | ||
461 | } | ||
462 | |||
463 | /* Any task that is preemptable and either exhausts its execution | ||
464 | * budget or wants to sleep completes. We may have to reschedule after | ||
465 | * this. Don't do a job completion if we block (can't have timers running | ||
466 | * for blocked jobs). | ||
467 | */ | ||
468 | if (!np && (out_of_time || sleep) && !blocks) | ||
469 | job_completion(entry->scheduled, !sleep); | ||
470 | |||
471 | /* Link pending task if we became unlinked. | ||
472 | */ | ||
473 | if (!entry->linked) | ||
474 | link_task_to_cpu(__take_ready(&gsnedf), entry); | ||
475 | |||
476 | /* The final scheduling decision. Do we need to switch for some reason? | ||
477 | * If linked is different from scheduled, then select linked as next. | ||
478 | */ | ||
479 | if ((!np || blocks) && | ||
480 | entry->linked != entry->scheduled) { | ||
481 | /* Schedule a linked job? */ | ||
482 | if (entry->linked) { | ||
483 | entry->linked->rt_param.scheduled_on = entry->cpu; | ||
484 | next = entry->linked; | ||
485 | TRACE_TASK(next, "scheduled_on = P%d\n", smp_processor_id()); | ||
486 | } | ||
487 | if (entry->scheduled) { | ||
488 | /* not gonna be scheduled soon */ | ||
489 | entry->scheduled->rt_param.scheduled_on = NO_CPU; | ||
490 | TRACE_TASK(entry->scheduled, "scheduled_on = NO_CPU\n"); | ||
491 | } | ||
492 | } else | ||
493 | /* Only override Linux scheduler if we have a real-time task | ||
494 | * scheduled that needs to continue. | ||
495 | */ | ||
496 | if (exists) | ||
497 | next = prev; | ||
498 | |||
499 | sched_state_task_picked(); | ||
500 | |||
501 | raw_spin_unlock(&gsnedf_lock); | ||
502 | |||
503 | #ifdef WANT_ALL_SCHED_EVENTS | ||
504 | TRACE("gsnedf_lock released, next=0x%p\n", next); | ||
505 | |||
506 | if (next) | ||
507 | TRACE_TASK(next, "scheduled at %llu\n", litmus_clock()); | ||
508 | else if (exists && !next) | ||
509 | TRACE("becomes idle at %llu.\n", litmus_clock()); | ||
510 | #endif | ||
511 | |||
512 | |||
513 | return next; | ||
514 | } | ||
515 | |||
516 | |||
517 | /* _finish_switch - we just finished the switch away from prev | ||
518 | */ | ||
519 | static void gsnedf_finish_switch(struct task_struct *prev) | ||
520 | { | ||
521 | cpu_entry_t* entry = &__get_cpu_var(gsnedf_cpu_entries); | ||
522 | |||
523 | entry->scheduled = is_realtime(current) ? current : NULL; | ||
524 | #ifdef WANT_ALL_SCHED_EVENTS | ||
525 | TRACE_TASK(prev, "switched away from\n"); | ||
526 | #endif | ||
527 | } | ||
528 | |||
529 | |||
530 | /* Prepare a task for running in RT mode | ||
531 | */ | ||
532 | static void gsnedf_task_new(struct task_struct * t, int on_rq, int is_scheduled) | ||
533 | { | ||
534 | unsigned long flags; | ||
535 | cpu_entry_t* entry; | ||
536 | |||
537 | TRACE("gsn edf: task new %d\n", t->pid); | ||
538 | |||
539 | raw_spin_lock_irqsave(&gsnedf_lock, flags); | ||
540 | |||
541 | /* setup job params */ | ||
542 | release_at(t, litmus_clock()); | ||
543 | |||
544 | if (is_scheduled) { | ||
545 | entry = &per_cpu(gsnedf_cpu_entries, task_cpu(t)); | ||
546 | BUG_ON(entry->scheduled); | ||
547 | |||
548 | #ifdef CONFIG_RELEASE_MASTER | ||
549 | if (entry->cpu != gsnedf.release_master) { | ||
550 | #endif | ||
551 | entry->scheduled = t; | ||
552 | tsk_rt(t)->scheduled_on = task_cpu(t); | ||
553 | #ifdef CONFIG_RELEASE_MASTER | ||
554 | } else { | ||
555 | /* do not schedule on release master */ | ||
556 | preempt(entry); /* force resched */ | ||
557 | tsk_rt(t)->scheduled_on = NO_CPU; | ||
558 | } | ||
559 | #endif | ||
560 | } else { | ||
561 | t->rt_param.scheduled_on = NO_CPU; | ||
562 | } | ||
563 | t->rt_param.linked_on = NO_CPU; | ||
564 | |||
565 | if (is_running(t)) | ||
566 | gsnedf_job_arrival(t); | ||
567 | raw_spin_unlock_irqrestore(&gsnedf_lock, flags); | ||
568 | } | ||
569 | |||
570 | static void gsnedf_task_wake_up(struct task_struct *task) | ||
571 | { | ||
572 | unsigned long flags; | ||
573 | lt_t now; | ||
574 | |||
575 | TRACE_TASK(task, "wake_up at %llu\n", litmus_clock()); | ||
576 | |||
577 | raw_spin_lock_irqsave(&gsnedf_lock, flags); | ||
578 | now = litmus_clock(); | ||
579 | if (is_sporadic(task) && is_tardy(task, now)) { | ||
580 | /* new sporadic release */ | ||
581 | release_at(task, now); | ||
582 | sched_trace_task_release(task); | ||
583 | } | ||
584 | gsnedf_job_arrival(task); | ||
585 | raw_spin_unlock_irqrestore(&gsnedf_lock, flags); | ||
586 | } | ||
587 | |||
588 | static void gsnedf_task_block(struct task_struct *t) | ||
589 | { | ||
590 | unsigned long flags; | ||
591 | |||
592 | TRACE_TASK(t, "block at %llu\n", litmus_clock()); | ||
593 | |||
594 | /* unlink if necessary */ | ||
595 | raw_spin_lock_irqsave(&gsnedf_lock, flags); | ||
596 | unlink(t); | ||
597 | raw_spin_unlock_irqrestore(&gsnedf_lock, flags); | ||
598 | |||
599 | BUG_ON(!is_realtime(t)); | ||
600 | } | ||
601 | |||
602 | |||
603 | static void gsnedf_task_exit(struct task_struct * t) | ||
604 | { | ||
605 | unsigned long flags; | ||
606 | |||
607 | /* unlink if necessary */ | ||
608 | raw_spin_lock_irqsave(&gsnedf_lock, flags); | ||
609 | unlink(t); | ||
610 | if (tsk_rt(t)->scheduled_on != NO_CPU) { | ||
611 | gsnedf_cpus[tsk_rt(t)->scheduled_on]->scheduled = NULL; | ||
612 | tsk_rt(t)->scheduled_on = NO_CPU; | ||
613 | } | ||
614 | raw_spin_unlock_irqrestore(&gsnedf_lock, flags); | ||
615 | |||
616 | BUG_ON(!is_realtime(t)); | ||
617 | TRACE_TASK(t, "RIP\n"); | ||
618 | } | ||
619 | |||
620 | |||
621 | static long gsnedf_admit_task(struct task_struct* tsk) | ||
622 | { | ||
623 | return 0; | ||
624 | } | ||
625 | |||
626 | #ifdef CONFIG_LITMUS_LOCKING | ||
627 | |||
628 | #include <litmus/fdso.h> | ||
629 | |||
630 | /* called with IRQs off */ | ||
631 | static void set_priority_inheritance(struct task_struct* t, struct task_struct* prio_inh) | ||
632 | { | ||
633 | int linked_on; | ||
634 | int check_preempt = 0; | ||
635 | |||
636 | raw_spin_lock(&gsnedf_lock); | ||
637 | |||
638 | TRACE_TASK(t, "inherits priority from %s/%d\n", prio_inh->comm, prio_inh->pid); | ||
639 | tsk_rt(t)->inh_task = prio_inh; | ||
640 | |||
641 | linked_on = tsk_rt(t)->linked_on; | ||
642 | |||
643 | /* If it is scheduled, then we need to reorder the CPU heap. */ | ||
644 | if (linked_on != NO_CPU) { | ||
645 | TRACE_TASK(t, "%s: linked on %d\n", | ||
646 | __FUNCTION__, linked_on); | ||
647 | /* Holder is scheduled; need to re-order CPUs. | ||
648 | * We can't use heap_decrease() here since | ||
649 | * the cpu_heap is ordered in reverse direction, so | ||
650 | * it is actually an increase. */ | ||
651 | bheap_delete(cpu_lower_prio, &gsnedf_cpu_heap, | ||
652 | gsnedf_cpus[linked_on]->hn); | ||
653 | bheap_insert(cpu_lower_prio, &gsnedf_cpu_heap, | ||
654 | gsnedf_cpus[linked_on]->hn); | ||
655 | } else { | ||
656 | /* holder may be queued: first stop queue changes */ | ||
657 | raw_spin_lock(&gsnedf.release_lock); | ||
658 | if (is_queued(t)) { | ||
659 | TRACE_TASK(t, "%s: is queued\n", | ||
660 | __FUNCTION__); | ||
661 | /* We need to update the position of holder in some | ||
662 | * heap. Note that this could be a release heap if we | ||
663 | * budget enforcement is used and this job overran. */ | ||
664 | check_preempt = | ||
665 | !bheap_decrease(edf_ready_order, | ||
666 | tsk_rt(t)->heap_node); | ||
667 | } else { | ||
668 | /* Nothing to do: if it is not queued and not linked | ||
669 | * then it is either sleeping or currently being moved | ||
670 | * by other code (e.g., a timer interrupt handler) that | ||
671 | * will use the correct priority when enqueuing the | ||
672 | * task. */ | ||
673 | TRACE_TASK(t, "%s: is NOT queued => Done.\n", | ||
674 | __FUNCTION__); | ||
675 | } | ||
676 | raw_spin_unlock(&gsnedf.release_lock); | ||
677 | |||
678 | /* If holder was enqueued in a release heap, then the following | ||
679 | * preemption check is pointless, but we can't easily detect | ||
680 | * that case. If you want to fix this, then consider that | ||
681 | * simply adding a state flag requires O(n) time to update when | ||
682 | * releasing n tasks, which conflicts with the goal to have | ||
683 | * O(log n) merges. */ | ||
684 | if (check_preempt) { | ||
685 | /* heap_decrease() hit the top level of the heap: make | ||
686 | * sure preemption checks get the right task, not the | ||
687 | * potentially stale cache. */ | ||
688 | bheap_uncache_min(edf_ready_order, | ||
689 | &gsnedf.ready_queue); | ||
690 | check_for_preemptions(); | ||
691 | } | ||
692 | } | ||
693 | |||
694 | raw_spin_unlock(&gsnedf_lock); | ||
695 | } | ||
696 | |||
697 | /* called with IRQs off */ | ||
698 | static void clear_priority_inheritance(struct task_struct* t) | ||
699 | { | ||
700 | raw_spin_lock(&gsnedf_lock); | ||
701 | |||
702 | /* A job only stops inheriting a priority when it releases a | ||
703 | * resource. Thus we can make the following assumption.*/ | ||
704 | BUG_ON(tsk_rt(t)->scheduled_on == NO_CPU); | ||
705 | |||
706 | TRACE_TASK(t, "priority restored\n"); | ||
707 | tsk_rt(t)->inh_task = NULL; | ||
708 | |||
709 | /* Check if rescheduling is necessary. We can't use heap_decrease() | ||
710 | * since the priority was effectively lowered. */ | ||
711 | unlink(t); | ||
712 | gsnedf_job_arrival(t); | ||
713 | |||
714 | raw_spin_unlock(&gsnedf_lock); | ||
715 | } | ||
716 | |||
717 | |||
718 | /* ******************** FMLP support ********************** */ | ||
719 | |||
720 | /* struct for semaphore with priority inheritance */ | ||
721 | struct fmlp_semaphore { | ||
722 | struct litmus_lock litmus_lock; | ||
723 | |||
724 | /* current resource holder */ | ||
725 | struct task_struct *owner; | ||
726 | |||
727 | /* highest-priority waiter */ | ||
728 | struct task_struct *hp_waiter; | ||
729 | |||
730 | /* FIFO queue of waiting tasks */ | ||
731 | wait_queue_head_t wait; | ||
732 | }; | ||
733 | |||
734 | static inline struct fmlp_semaphore* fmlp_from_lock(struct litmus_lock* lock) | ||
735 | { | ||
736 | return container_of(lock, struct fmlp_semaphore, litmus_lock); | ||
737 | } | ||
738 | |||
739 | /* caller is responsible for locking */ | ||
740 | struct task_struct* find_hp_waiter(struct fmlp_semaphore *sem, | ||
741 | struct task_struct* skip) | ||
742 | { | ||
743 | struct list_head *pos; | ||
744 | struct task_struct *queued, *found = NULL; | ||
745 | |||
746 | list_for_each(pos, &sem->wait.task_list) { | ||
747 | queued = (struct task_struct*) list_entry(pos, wait_queue_t, | ||
748 | task_list)->private; | ||
749 | |||
750 | /* Compare task prios, find high prio task. */ | ||
751 | if (queued != skip && edf_higher_prio(queued, found)) | ||
752 | found = queued; | ||
753 | } | ||
754 | return found; | ||
755 | } | ||
756 | |||
757 | int gsnedf_fmlp_lock(struct litmus_lock* l) | ||
758 | { | ||
759 | struct task_struct* t = current; | ||
760 | struct fmlp_semaphore *sem = fmlp_from_lock(l); | ||
761 | wait_queue_t wait; | ||
762 | unsigned long flags; | ||
763 | |||
764 | if (!is_realtime(t)) | ||
765 | return -EPERM; | ||
766 | |||
767 | /* prevent nested lock acquisition --- not supported by FMLP */ | ||
768 | if (tsk_rt(t)->num_locks_held) | ||
769 | return -EBUSY; | ||
770 | |||
771 | spin_lock_irqsave(&sem->wait.lock, flags); | ||
772 | |||
773 | if (sem->owner) { | ||
774 | /* resource is not free => must suspend and wait */ | ||
775 | |||
776 | init_waitqueue_entry(&wait, t); | ||
777 | |||
778 | /* FIXME: interruptible would be nice some day */ | ||
779 | set_task_state(t, TASK_UNINTERRUPTIBLE); | ||
780 | |||
781 | __add_wait_queue_tail_exclusive(&sem->wait, &wait); | ||
782 | |||
783 | /* check if we need to activate priority inheritance */ | ||
784 | if (edf_higher_prio(t, sem->hp_waiter)) { | ||
785 | sem->hp_waiter = t; | ||
786 | if (edf_higher_prio(t, sem->owner)) | ||
787 | set_priority_inheritance(sem->owner, sem->hp_waiter); | ||
788 | } | ||
789 | |||
790 | TS_LOCK_SUSPEND; | ||
791 | |||
792 | /* release lock before sleeping */ | ||
793 | spin_unlock_irqrestore(&sem->wait.lock, flags); | ||
794 | |||
795 | /* We depend on the FIFO order. Thus, we don't need to recheck | ||
796 | * when we wake up; we are guaranteed to have the lock since | ||
797 | * there is only one wake up per release. | ||
798 | */ | ||
799 | |||
800 | schedule(); | ||
801 | |||
802 | TS_LOCK_RESUME; | ||
803 | |||
804 | /* Since we hold the lock, no other task will change | ||
805 | * ->owner. We can thus check it without acquiring the spin | ||
806 | * lock. */ | ||
807 | BUG_ON(sem->owner != t); | ||
808 | } else { | ||
809 | /* it's ours now */ | ||
810 | sem->owner = t; | ||
811 | |||
812 | spin_unlock_irqrestore(&sem->wait.lock, flags); | ||
813 | } | ||
814 | |||
815 | tsk_rt(t)->num_locks_held++; | ||
816 | |||
817 | return 0; | ||
818 | } | ||
819 | |||
820 | int gsnedf_fmlp_unlock(struct litmus_lock* l) | ||
821 | { | ||
822 | struct task_struct *t = current, *next; | ||
823 | struct fmlp_semaphore *sem = fmlp_from_lock(l); | ||
824 | unsigned long flags; | ||
825 | int err = 0; | ||
826 | |||
827 | spin_lock_irqsave(&sem->wait.lock, flags); | ||
828 | |||
829 | if (sem->owner != t) { | ||
830 | err = -EINVAL; | ||
831 | goto out; | ||
832 | } | ||
833 | |||
834 | tsk_rt(t)->num_locks_held--; | ||
835 | |||
836 | /* check if there are jobs waiting for this resource */ | ||
837 | next = __waitqueue_remove_first(&sem->wait); | ||
838 | if (next) { | ||
839 | /* next becomes the resouce holder */ | ||
840 | sem->owner = next; | ||
841 | TRACE_CUR("lock ownership passed to %s/%d\n", next->comm, next->pid); | ||
842 | |||
843 | /* determine new hp_waiter if necessary */ | ||
844 | if (next == sem->hp_waiter) { | ||
845 | TRACE_TASK(next, "was highest-prio waiter\n"); | ||
846 | /* next has the highest priority --- it doesn't need to | ||
847 | * inherit. However, we need to make sure that the | ||
848 | * next-highest priority in the queue is reflected in | ||
849 | * hp_waiter. */ | ||
850 | sem->hp_waiter = find_hp_waiter(sem, next); | ||
851 | if (sem->hp_waiter) | ||
852 | TRACE_TASK(sem->hp_waiter, "is new highest-prio waiter\n"); | ||
853 | else | ||
854 | TRACE("no further waiters\n"); | ||
855 | } else { | ||
856 | /* Well, if next is not the highest-priority waiter, | ||
857 | * then it ought to inherit the highest-priority | ||
858 | * waiter's priority. */ | ||
859 | set_priority_inheritance(next, sem->hp_waiter); | ||
860 | } | ||
861 | |||
862 | /* wake up next */ | ||
863 | wake_up_process(next); | ||
864 | } else | ||
865 | /* becomes available */ | ||
866 | sem->owner = NULL; | ||
867 | |||
868 | /* we lose the benefit of priority inheritance (if any) */ | ||
869 | if (tsk_rt(t)->inh_task) | ||
870 | clear_priority_inheritance(t); | ||
871 | |||
872 | out: | ||
873 | spin_unlock_irqrestore(&sem->wait.lock, flags); | ||
874 | |||
875 | return err; | ||
876 | } | ||
877 | |||
878 | int gsnedf_fmlp_close(struct litmus_lock* l) | ||
879 | { | ||
880 | struct task_struct *t = current; | ||
881 | struct fmlp_semaphore *sem = fmlp_from_lock(l); | ||
882 | unsigned long flags; | ||
883 | |||
884 | int owner; | ||
885 | |||
886 | spin_lock_irqsave(&sem->wait.lock, flags); | ||
887 | |||
888 | owner = sem->owner == t; | ||
889 | |||
890 | spin_unlock_irqrestore(&sem->wait.lock, flags); | ||
891 | |||
892 | if (owner) | ||
893 | gsnedf_fmlp_unlock(l); | ||
894 | |||
895 | return 0; | ||
896 | } | ||
897 | |||
898 | void gsnedf_fmlp_free(struct litmus_lock* lock) | ||
899 | { | ||
900 | kfree(fmlp_from_lock(lock)); | ||
901 | } | ||
902 | |||
903 | static struct litmus_lock_ops gsnedf_fmlp_lock_ops = { | ||
904 | .close = gsnedf_fmlp_close, | ||
905 | .lock = gsnedf_fmlp_lock, | ||
906 | .unlock = gsnedf_fmlp_unlock, | ||
907 | .deallocate = gsnedf_fmlp_free, | ||
908 | }; | ||
909 | |||
910 | static struct litmus_lock* gsnedf_new_fmlp(void) | ||
911 | { | ||
912 | struct fmlp_semaphore* sem; | ||
913 | |||
914 | sem = kmalloc(sizeof(*sem), GFP_KERNEL); | ||
915 | if (!sem) | ||
916 | return NULL; | ||
917 | |||
918 | sem->owner = NULL; | ||
919 | sem->hp_waiter = NULL; | ||
920 | init_waitqueue_head(&sem->wait); | ||
921 | sem->litmus_lock.ops = &gsnedf_fmlp_lock_ops; | ||
922 | |||
923 | return &sem->litmus_lock; | ||
924 | } | ||
925 | |||
926 | /* **** lock constructor **** */ | ||
927 | |||
928 | |||
929 | static long gsnedf_allocate_lock(struct litmus_lock **lock, int type, | ||
930 | void* __user unused) | ||
931 | { | ||
932 | int err = -ENXIO; | ||
933 | |||
934 | /* GSN-EDF currently only supports the FMLP for global resources. */ | ||
935 | switch (type) { | ||
936 | |||
937 | case FMLP_SEM: | ||
938 | /* Flexible Multiprocessor Locking Protocol */ | ||
939 | *lock = gsnedf_new_fmlp(); | ||
940 | if (*lock) | ||
941 | err = 0; | ||
942 | else | ||
943 | err = -ENOMEM; | ||
944 | break; | ||
945 | |||
946 | }; | ||
947 | |||
948 | return err; | ||
949 | } | ||
950 | |||
951 | #endif | ||
952 | |||
953 | static struct domain_proc_info gsnedf_domain_proc_info; | ||
954 | static long gsnedf_get_domain_proc_info(struct domain_proc_info **ret) | ||
955 | { | ||
956 | *ret = &gsnedf_domain_proc_info; | ||
957 | return 0; | ||
958 | } | ||
959 | |||
960 | static void gsnedf_setup_domain_proc(void) | ||
961 | { | ||
962 | int i, cpu; | ||
963 | int release_master = | ||
964 | #ifdef CONFIG_RELEASE_MASTER | ||
965 | atomic_read(&release_master_cpu); | ||
966 | #else | ||
967 | NO_CPU; | ||
968 | #endif | ||
969 | int num_rt_cpus = num_online_cpus() - (release_master != NO_CPU); | ||
970 | struct cd_mapping *map; | ||
971 | |||
972 | memset(&gsnedf_domain_proc_info, sizeof(gsnedf_domain_proc_info), 0); | ||
973 | init_domain_proc_info(&gsnedf_domain_proc_info, num_rt_cpus, 1); | ||
974 | gsnedf_domain_proc_info.num_cpus = num_rt_cpus; | ||
975 | gsnedf_domain_proc_info.num_domains = 1; | ||
976 | |||
977 | gsnedf_domain_proc_info.domain_to_cpus[0].id = 0; | ||
978 | for (cpu = 0, i = 0; cpu < num_online_cpus(); ++cpu) { | ||
979 | if (cpu == release_master) | ||
980 | continue; | ||
981 | map = &gsnedf_domain_proc_info.cpu_to_domains[i]; | ||
982 | map->id = cpu; | ||
983 | cpumask_set_cpu(0, map->mask); | ||
984 | ++i; | ||
985 | |||
986 | /* add cpu to the domain */ | ||
987 | cpumask_set_cpu(cpu, | ||
988 | gsnedf_domain_proc_info.domain_to_cpus[0].mask); | ||
989 | } | ||
990 | } | ||
991 | |||
992 | static long gsnedf_activate_plugin(void) | ||
993 | { | ||
994 | int cpu; | ||
995 | cpu_entry_t *entry; | ||
996 | |||
997 | bheap_init(&gsnedf_cpu_heap); | ||
998 | #ifdef CONFIG_RELEASE_MASTER | ||
999 | gsnedf.release_master = atomic_read(&release_master_cpu); | ||
1000 | #endif | ||
1001 | |||
1002 | for_each_online_cpu(cpu) { | ||
1003 | entry = &per_cpu(gsnedf_cpu_entries, cpu); | ||
1004 | bheap_node_init(&entry->hn, entry); | ||
1005 | entry->linked = NULL; | ||
1006 | entry->scheduled = NULL; | ||
1007 | #ifdef CONFIG_RELEASE_MASTER | ||
1008 | if (cpu != gsnedf.release_master) { | ||
1009 | #endif | ||
1010 | TRACE("GSN-EDF: Initializing CPU #%d.\n", cpu); | ||
1011 | update_cpu_position(entry); | ||
1012 | #ifdef CONFIG_RELEASE_MASTER | ||
1013 | } else { | ||
1014 | TRACE("GSN-EDF: CPU %d is release master.\n", cpu); | ||
1015 | } | ||
1016 | #endif | ||
1017 | } | ||
1018 | |||
1019 | gsnedf_setup_domain_proc(); | ||
1020 | |||
1021 | return 0; | ||
1022 | } | ||
1023 | |||
1024 | static long gsnedf_deactivate_plugin(void) | ||
1025 | { | ||
1026 | destroy_domain_proc_info(&gsnedf_domain_proc_info); | ||
1027 | return 0; | ||
1028 | } | ||
1029 | |||
1030 | /* Plugin object */ | ||
1031 | static struct sched_plugin gsn_edf_plugin __cacheline_aligned_in_smp = { | ||
1032 | .plugin_name = "GSN-EDF", | ||
1033 | .finish_switch = gsnedf_finish_switch, | ||
1034 | .task_new = gsnedf_task_new, | ||
1035 | .complete_job = complete_job, | ||
1036 | .task_exit = gsnedf_task_exit, | ||
1037 | .schedule = gsnedf_schedule, | ||
1038 | .task_wake_up = gsnedf_task_wake_up, | ||
1039 | .task_block = gsnedf_task_block, | ||
1040 | .admit_task = gsnedf_admit_task, | ||
1041 | .activate_plugin = gsnedf_activate_plugin, | ||
1042 | .deactivate_plugin = gsnedf_deactivate_plugin, | ||
1043 | .get_domain_proc_info = gsnedf_get_domain_proc_info, | ||
1044 | #ifdef CONFIG_LITMUS_LOCKING | ||
1045 | .allocate_lock = gsnedf_allocate_lock, | ||
1046 | #endif | ||
1047 | }; | ||
1048 | |||
1049 | |||
1050 | static int __init init_gsn_edf(void) | ||
1051 | { | ||
1052 | int cpu; | ||
1053 | cpu_entry_t *entry; | ||
1054 | |||
1055 | bheap_init(&gsnedf_cpu_heap); | ||
1056 | /* initialize CPU state */ | ||
1057 | for (cpu = 0; cpu < NR_CPUS; cpu++) { | ||
1058 | entry = &per_cpu(gsnedf_cpu_entries, cpu); | ||
1059 | gsnedf_cpus[cpu] = entry; | ||
1060 | entry->cpu = cpu; | ||
1061 | entry->hn = &gsnedf_heap_node[cpu]; | ||
1062 | bheap_node_init(&entry->hn, entry); | ||
1063 | } | ||
1064 | edf_domain_init(&gsnedf, NULL, gsnedf_release_jobs); | ||
1065 | return register_sched_plugin(&gsn_edf_plugin); | ||
1066 | } | ||
1067 | |||
1068 | |||
1069 | module_init(init_gsn_edf); | ||