diff options
author | Andrea Bastoni <bastoni@cs.unc.edu> | 2009-12-17 21:39:14 -0500 |
---|---|---|
committer | Andrea Bastoni <bastoni@cs.unc.edu> | 2010-05-29 17:17:12 -0400 |
commit | 50ca05ff9cc85176c3ee18bf1363d3d7c34aa355 (patch) | |
tree | 59d0edd28e9e47b9cb48e6cc90d5f6488494795d /litmus/sched_gsn_edf.c | |
parent | 2a94c7bf9869a13e32de7a1fe94596de7b4789a8 (diff) |
[ported from 2008.3] Add GSN-EDF plugin
- insert arm_release_timer() in add_relese() path
- arm_release_timer() uses __hrtimer_start_range_ns() instead of
hrtimer_start() to avoid deadlock on rq->lock.
Diffstat (limited to 'litmus/sched_gsn_edf.c')
-rw-r--r-- | litmus/sched_gsn_edf.c | 816 |
1 files changed, 816 insertions, 0 deletions
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c new file mode 100644 index 000000000000..69990805e16a --- /dev/null +++ b/litmus/sched_gsn_edf.c | |||
@@ -0,0 +1,816 @@ | |||
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 | |||
15 | #include <litmus/litmus.h> | ||
16 | #include <litmus/jobs.h> | ||
17 | #include <litmus/sched_plugin.h> | ||
18 | #include <litmus/edf_common.h> | ||
19 | #include <litmus/sched_trace.h> | ||
20 | |||
21 | #include <litmus/heap.h> | ||
22 | |||
23 | #include <linux/module.h> | ||
24 | |||
25 | /* Overview of GSN-EDF operations. | ||
26 | * | ||
27 | * For a detailed explanation of GSN-EDF have a look at the FMLP paper. This | ||
28 | * description only covers how the individual operations are implemented in | ||
29 | * LITMUS. | ||
30 | * | ||
31 | * link_task_to_cpu(T, cpu) - Low-level operation to update the linkage | ||
32 | * structure (NOT the actually scheduled | ||
33 | * task). If there is another linked task To | ||
34 | * already it will set To->linked_on = NO_CPU | ||
35 | * (thereby removing its association with this | ||
36 | * CPU). However, it will not requeue the | ||
37 | * previously linked task (if any). It will set | ||
38 | * T's state to RT_F_RUNNING and check whether | ||
39 | * it is already running somewhere else. If T | ||
40 | * is scheduled somewhere else it will link | ||
41 | * it to that CPU instead (and pull the linked | ||
42 | * task to cpu). T may be NULL. | ||
43 | * | ||
44 | * unlink(T) - Unlink removes T from all scheduler data | ||
45 | * structures. If it is linked to some CPU it | ||
46 | * will link NULL to that CPU. If it is | ||
47 | * currently queued in the gsnedf queue it will | ||
48 | * be removed from the rt_domain. It is safe to | ||
49 | * call unlink(T) if T is not linked. T may not | ||
50 | * be NULL. | ||
51 | * | ||
52 | * requeue(T) - Requeue will insert T into the appropriate | ||
53 | * queue. If the system is in real-time mode and | ||
54 | * the T is released already, it will go into the | ||
55 | * ready queue. If the system is not in | ||
56 | * real-time mode is T, then T will go into the | ||
57 | * release queue. If T's release time is in the | ||
58 | * future, it will go into the release | ||
59 | * queue. That means that T's release time/job | ||
60 | * no/etc. has to be updated before requeu(T) is | ||
61 | * called. It is not safe to call requeue(T) | ||
62 | * when T is already queued. T may not be NULL. | ||
63 | * | ||
64 | * gsnedf_job_arrival(T) - This is the catch all function when T enters | ||
65 | * the system after either a suspension or at a | ||
66 | * job release. It will queue T (which means it | ||
67 | * is not safe to call gsnedf_job_arrival(T) if | ||
68 | * T is already queued) and then check whether a | ||
69 | * preemption is necessary. If a preemption is | ||
70 | * necessary it will update the linkage | ||
71 | * accordingly and cause scheduled to be called | ||
72 | * (either with an IPI or need_resched). It is | ||
73 | * safe to call gsnedf_job_arrival(T) if T's | ||
74 | * next job has not been actually released yet | ||
75 | * (releast time in the future). T will be put | ||
76 | * on the release queue in that case. | ||
77 | * | ||
78 | * job_completion(T) - Take care of everything that needs to be done | ||
79 | * to prepare T for its next release and place | ||
80 | * it in the right queue with | ||
81 | * gsnedf_job_arrival(). | ||
82 | * | ||
83 | * | ||
84 | * When we now that T is linked to CPU then link_task_to_cpu(NULL, CPU) is | ||
85 | * equivalent to unlink(T). Note that if you unlink a task from a CPU none of | ||
86 | * the functions will automatically propagate pending task from the ready queue | ||
87 | * to a linked task. This is the job of the calling function ( by means of | ||
88 | * __take_ready). | ||
89 | */ | ||
90 | |||
91 | |||
92 | /* cpu_entry_t - maintain the linked and scheduled state | ||
93 | */ | ||
94 | typedef struct { | ||
95 | int cpu; | ||
96 | struct task_struct* linked; /* only RT tasks */ | ||
97 | struct task_struct* scheduled; /* only RT tasks */ | ||
98 | atomic_t will_schedule; /* prevent unneeded IPIs */ | ||
99 | struct heap_node* hn; | ||
100 | } cpu_entry_t; | ||
101 | DEFINE_PER_CPU(cpu_entry_t, gsnedf_cpu_entries); | ||
102 | |||
103 | cpu_entry_t* gsnedf_cpus[NR_CPUS]; | ||
104 | |||
105 | #define set_will_schedule() \ | ||
106 | (atomic_set(&__get_cpu_var(gsnedf_cpu_entries).will_schedule, 1)) | ||
107 | #define clear_will_schedule() \ | ||
108 | (atomic_set(&__get_cpu_var(gsnedf_cpu_entries).will_schedule, 0)) | ||
109 | #define test_will_schedule(cpu) \ | ||
110 | (atomic_read(&per_cpu(gsnedf_cpu_entries, cpu).will_schedule)) | ||
111 | |||
112 | |||
113 | /* the cpus queue themselves according to priority in here */ | ||
114 | static struct heap_node gsnedf_heap_node[NR_CPUS]; | ||
115 | static struct heap gsnedf_cpu_heap; | ||
116 | |||
117 | static rt_domain_t gsnedf; | ||
118 | #define gsnedf_lock (gsnedf.ready_lock) | ||
119 | |||
120 | |||
121 | static int cpu_lower_prio(struct heap_node *_a, struct heap_node *_b) | ||
122 | { | ||
123 | cpu_entry_t *a, *b; | ||
124 | a = _a->value; | ||
125 | b = _b->value; | ||
126 | /* Note that a and b are inverted: we want the lowest-priority CPU at | ||
127 | * the top of the heap. | ||
128 | */ | ||
129 | return edf_higher_prio(b->linked, a->linked); | ||
130 | } | ||
131 | |||
132 | /* update_cpu_position - Move the cpu entry to the correct place to maintain | ||
133 | * order in the cpu queue. Caller must hold gsnedf lock. | ||
134 | */ | ||
135 | static void update_cpu_position(cpu_entry_t *entry) | ||
136 | { | ||
137 | if (likely(heap_node_in_heap(entry->hn))) | ||
138 | heap_delete(cpu_lower_prio, &gsnedf_cpu_heap, entry->hn); | ||
139 | heap_insert(cpu_lower_prio, &gsnedf_cpu_heap, entry->hn); | ||
140 | } | ||
141 | |||
142 | /* caller must hold gsnedf lock */ | ||
143 | static cpu_entry_t* lowest_prio_cpu(void) | ||
144 | { | ||
145 | struct heap_node* hn; | ||
146 | hn = heap_peek(cpu_lower_prio, &gsnedf_cpu_heap); | ||
147 | return hn->value; | ||
148 | } | ||
149 | |||
150 | |||
151 | /* link_task_to_cpu - Update the link of a CPU. | ||
152 | * Handles the case where the to-be-linked task is already | ||
153 | * scheduled on a different CPU. | ||
154 | */ | ||
155 | static noinline void link_task_to_cpu(struct task_struct* linked, | ||
156 | cpu_entry_t *entry) | ||
157 | { | ||
158 | cpu_entry_t *sched; | ||
159 | struct task_struct* tmp; | ||
160 | int on_cpu; | ||
161 | |||
162 | BUG_ON(linked && !is_realtime(linked)); | ||
163 | |||
164 | /* Currently linked task is set to be unlinked. */ | ||
165 | if (entry->linked) { | ||
166 | entry->linked->rt_param.linked_on = NO_CPU; | ||
167 | } | ||
168 | |||
169 | /* Link new task to CPU. */ | ||
170 | if (linked) { | ||
171 | set_rt_flags(linked, RT_F_RUNNING); | ||
172 | /* handle task is already scheduled somewhere! */ | ||
173 | on_cpu = linked->rt_param.scheduled_on; | ||
174 | if (on_cpu != NO_CPU) { | ||
175 | sched = &per_cpu(gsnedf_cpu_entries, on_cpu); | ||
176 | /* this should only happen if not linked already */ | ||
177 | BUG_ON(sched->linked == linked); | ||
178 | |||
179 | /* If we are already scheduled on the CPU to which we | ||
180 | * wanted to link, we don't need to do the swap -- | ||
181 | * we just link ourselves to the CPU and depend on | ||
182 | * the caller to get things right. | ||
183 | */ | ||
184 | if (entry != sched) { | ||
185 | TRACE_TASK(linked, | ||
186 | "already scheduled on %d, updating link.\n", | ||
187 | sched->cpu); | ||
188 | tmp = sched->linked; | ||
189 | linked->rt_param.linked_on = sched->cpu; | ||
190 | sched->linked = linked; | ||
191 | update_cpu_position(sched); | ||
192 | linked = tmp; | ||
193 | } | ||
194 | } | ||
195 | if (linked) /* might be NULL due to swap */ | ||
196 | linked->rt_param.linked_on = entry->cpu; | ||
197 | } | ||
198 | entry->linked = linked; | ||
199 | if (linked) | ||
200 | TRACE_TASK(linked, "linked to %d.\n", entry->cpu); | ||
201 | else | ||
202 | TRACE("NULL linked to %d.\n", entry->cpu); | ||
203 | update_cpu_position(entry); | ||
204 | } | ||
205 | |||
206 | /* unlink - Make sure a task is not linked any longer to an entry | ||
207 | * where it was linked before. Must hold gsnedf_lock. | ||
208 | */ | ||
209 | static noinline void unlink(struct task_struct* t) | ||
210 | { | ||
211 | cpu_entry_t *entry; | ||
212 | |||
213 | if (unlikely(!t)) { | ||
214 | TRACE_BUG_ON(!t); | ||
215 | return; | ||
216 | } | ||
217 | |||
218 | if (t->rt_param.linked_on != NO_CPU) { | ||
219 | /* unlink */ | ||
220 | entry = &per_cpu(gsnedf_cpu_entries, t->rt_param.linked_on); | ||
221 | t->rt_param.linked_on = NO_CPU; | ||
222 | link_task_to_cpu(NULL, entry); | ||
223 | } else if (is_queued(t)) { | ||
224 | /* This is an interesting situation: t is scheduled, | ||
225 | * but was just recently unlinked. It cannot be | ||
226 | * linked anywhere else (because then it would have | ||
227 | * been relinked to this CPU), thus it must be in some | ||
228 | * queue. We must remove it from the list in this | ||
229 | * case. | ||
230 | */ | ||
231 | remove(&gsnedf, t); | ||
232 | } | ||
233 | } | ||
234 | |||
235 | |||
236 | /* preempt - force a CPU to reschedule | ||
237 | */ | ||
238 | static noinline void preempt(cpu_entry_t *entry) | ||
239 | { | ||
240 | /* We cannot make the is_np() decision here if it is a remote CPU | ||
241 | * because requesting exit_np() requires that we currently use the | ||
242 | * address space of the task. Thus, in the remote case we just send | ||
243 | * the IPI and let schedule() handle the problem. | ||
244 | */ | ||
245 | |||
246 | if (smp_processor_id() == entry->cpu) { | ||
247 | if (entry->scheduled && is_np(entry->scheduled)) | ||
248 | request_exit_np(entry->scheduled); | ||
249 | else | ||
250 | set_tsk_need_resched(current); | ||
251 | } else | ||
252 | /* in case that it is a remote CPU we have to defer the | ||
253 | * the decision to the remote CPU | ||
254 | * FIXME: We could save a few IPI's here if we leave the flag | ||
255 | * set when we are waiting for a np_exit(). | ||
256 | */ | ||
257 | if (!test_will_schedule(entry->cpu)) | ||
258 | smp_send_reschedule(entry->cpu); | ||
259 | } | ||
260 | |||
261 | /* requeue - Put an unlinked task into gsn-edf domain. | ||
262 | * Caller must hold gsnedf_lock. | ||
263 | */ | ||
264 | static noinline void requeue(struct task_struct* task) | ||
265 | { | ||
266 | BUG_ON(!task); | ||
267 | /* sanity check before insertion */ | ||
268 | BUG_ON(is_queued(task)); | ||
269 | |||
270 | if (is_released(task, litmus_clock())) | ||
271 | __add_ready(&gsnedf, task); | ||
272 | else { | ||
273 | /* it has got to wait */ | ||
274 | add_release(&gsnedf, task); | ||
275 | } | ||
276 | } | ||
277 | |||
278 | /* check for any necessary preemptions */ | ||
279 | static void check_for_preemptions(void) | ||
280 | { | ||
281 | struct task_struct *task; | ||
282 | cpu_entry_t* last; | ||
283 | |||
284 | for(last = lowest_prio_cpu(); | ||
285 | edf_preemption_needed(&gsnedf, last->linked); | ||
286 | last = lowest_prio_cpu()) { | ||
287 | /* preemption necessary */ | ||
288 | task = __take_ready(&gsnedf); | ||
289 | TRACE("check_for_preemptions: attempting to link task %d to %d\n", | ||
290 | task->pid, last->cpu); | ||
291 | if (last->linked) | ||
292 | requeue(last->linked); | ||
293 | link_task_to_cpu(task, last); | ||
294 | preempt(last); | ||
295 | } | ||
296 | } | ||
297 | |||
298 | /* gsnedf_job_arrival: task is either resumed or released */ | ||
299 | static noinline void gsnedf_job_arrival(struct task_struct* task) | ||
300 | { | ||
301 | BUG_ON(!task); | ||
302 | |||
303 | requeue(task); | ||
304 | check_for_preemptions(); | ||
305 | } | ||
306 | |||
307 | static void gsnedf_release_jobs(rt_domain_t* rt, struct heap* tasks) | ||
308 | { | ||
309 | unsigned long flags; | ||
310 | |||
311 | spin_lock_irqsave(&gsnedf_lock, flags); | ||
312 | |||
313 | __merge_ready(rt, tasks); | ||
314 | check_for_preemptions(); | ||
315 | |||
316 | spin_unlock_irqrestore(&gsnedf_lock, flags); | ||
317 | } | ||
318 | |||
319 | /* caller holds gsnedf_lock */ | ||
320 | static noinline void job_completion(struct task_struct *t, int forced) | ||
321 | { | ||
322 | BUG_ON(!t); | ||
323 | |||
324 | sched_trace_task_completion(t, forced); | ||
325 | |||
326 | TRACE_TASK(t, "job_completion().\n"); | ||
327 | |||
328 | /* set flags */ | ||
329 | set_rt_flags(t, RT_F_SLEEP); | ||
330 | /* prepare for next period */ | ||
331 | prepare_for_next_period(t); | ||
332 | if (is_released(t, litmus_clock())) | ||
333 | sched_trace_task_release(t); | ||
334 | /* unlink */ | ||
335 | unlink(t); | ||
336 | /* requeue | ||
337 | * But don't requeue a blocking task. */ | ||
338 | if (is_running(t)) | ||
339 | gsnedf_job_arrival(t); | ||
340 | } | ||
341 | |||
342 | /* gsnedf_tick - this function is called for every local timer | ||
343 | * interrupt. | ||
344 | * | ||
345 | * checks whether the current task has expired and checks | ||
346 | * whether we need to preempt it if it has not expired | ||
347 | */ | ||
348 | static void gsnedf_tick(struct task_struct* t) | ||
349 | { | ||
350 | if (is_realtime(t) && budget_exhausted(t)) { | ||
351 | if (!is_np(t)) { | ||
352 | /* np tasks will be preempted when they become | ||
353 | * preemptable again | ||
354 | */ | ||
355 | set_tsk_need_resched(t); | ||
356 | set_will_schedule(); | ||
357 | TRACE("gsnedf_scheduler_tick: " | ||
358 | "%d is preemptable " | ||
359 | " => FORCE_RESCHED\n", t->pid); | ||
360 | } else { | ||
361 | TRACE("gsnedf_scheduler_tick: " | ||
362 | "%d is non-preemptable, " | ||
363 | "preemption delayed.\n", t->pid); | ||
364 | request_exit_np(t); | ||
365 | } | ||
366 | } | ||
367 | } | ||
368 | |||
369 | /* Getting schedule() right is a bit tricky. schedule() may not make any | ||
370 | * assumptions on the state of the current task since it may be called for a | ||
371 | * number of reasons. The reasons include a scheduler_tick() determined that it | ||
372 | * was necessary, because sys_exit_np() was called, because some Linux | ||
373 | * subsystem determined so, or even (in the worst case) because there is a bug | ||
374 | * hidden somewhere. Thus, we must take extreme care to determine what the | ||
375 | * current state is. | ||
376 | * | ||
377 | * The CPU could currently be scheduling a task (or not), be linked (or not). | ||
378 | * | ||
379 | * The following assertions for the scheduled task could hold: | ||
380 | * | ||
381 | * - !is_running(scheduled) // the job blocks | ||
382 | * - scheduled->timeslice == 0 // the job completed (forcefully) | ||
383 | * - get_rt_flag() == RT_F_SLEEP // the job completed (by syscall) | ||
384 | * - linked != scheduled // we need to reschedule (for any reason) | ||
385 | * - is_np(scheduled) // rescheduling must be delayed, | ||
386 | * sys_exit_np must be requested | ||
387 | * | ||
388 | * Any of these can occur together. | ||
389 | */ | ||
390 | static struct task_struct* gsnedf_schedule(struct task_struct * prev) | ||
391 | { | ||
392 | cpu_entry_t* entry = &__get_cpu_var(gsnedf_cpu_entries); | ||
393 | int out_of_time, sleep, preempt, np, exists, blocks; | ||
394 | struct task_struct* next = NULL; | ||
395 | |||
396 | spin_lock(&gsnedf_lock); | ||
397 | clear_will_schedule(); | ||
398 | |||
399 | /* sanity checking */ | ||
400 | BUG_ON(entry->scheduled && entry->scheduled != prev); | ||
401 | BUG_ON(entry->scheduled && !is_realtime(prev)); | ||
402 | BUG_ON(is_realtime(prev) && !entry->scheduled); | ||
403 | |||
404 | /* (0) Determine state */ | ||
405 | exists = entry->scheduled != NULL; | ||
406 | blocks = exists && !is_running(entry->scheduled); | ||
407 | out_of_time = exists && budget_exhausted(entry->scheduled); | ||
408 | np = exists && is_np(entry->scheduled); | ||
409 | sleep = exists && get_rt_flags(entry->scheduled) == RT_F_SLEEP; | ||
410 | preempt = entry->scheduled != entry->linked; | ||
411 | |||
412 | TRACE_TASK(prev, "invoked gsnedf_schedule.\n"); | ||
413 | |||
414 | if (exists) | ||
415 | TRACE_TASK(prev, | ||
416 | "blocks:%d out_of_time:%d np:%d sleep:%d preempt:%d " | ||
417 | "state:%d sig:%d\n", | ||
418 | blocks, out_of_time, np, sleep, preempt, | ||
419 | prev->state, signal_pending(prev)); | ||
420 | if (entry->linked && preempt) | ||
421 | TRACE_TASK(prev, "will be preempted by %s/%d\n", | ||
422 | entry->linked->comm, entry->linked->pid); | ||
423 | |||
424 | |||
425 | /* If a task blocks we have no choice but to reschedule. | ||
426 | */ | ||
427 | if (blocks) | ||
428 | unlink(entry->scheduled); | ||
429 | |||
430 | /* Request a sys_exit_np() call if we would like to preempt but cannot. | ||
431 | * We need to make sure to update the link structure anyway in case | ||
432 | * that we are still linked. Multiple calls to request_exit_np() don't | ||
433 | * hurt. | ||
434 | */ | ||
435 | if (np && (out_of_time || preempt || sleep)) { | ||
436 | unlink(entry->scheduled); | ||
437 | request_exit_np(entry->scheduled); | ||
438 | } | ||
439 | |||
440 | /* Any task that is preemptable and either exhausts its execution | ||
441 | * budget or wants to sleep completes. We may have to reschedule after | ||
442 | * this. Don't do a job completion if we block (can't have timers running | ||
443 | * for blocked jobs). Preemption go first for the same reason. | ||
444 | */ | ||
445 | if (!np && (out_of_time || sleep) && !blocks && !preempt) | ||
446 | job_completion(entry->scheduled, !sleep); | ||
447 | |||
448 | /* Link pending task if we became unlinked. | ||
449 | */ | ||
450 | if (!entry->linked) | ||
451 | link_task_to_cpu(__take_ready(&gsnedf), entry); | ||
452 | |||
453 | /* The final scheduling decision. Do we need to switch for some reason? | ||
454 | * If linked is different from scheduled, then select linked as next. | ||
455 | */ | ||
456 | if ((!np || blocks) && | ||
457 | entry->linked != entry->scheduled) { | ||
458 | /* Schedule a linked job? */ | ||
459 | if (entry->linked) { | ||
460 | entry->linked->rt_param.scheduled_on = entry->cpu; | ||
461 | next = entry->linked; | ||
462 | } | ||
463 | if (entry->scheduled) { | ||
464 | /* not gonna be scheduled soon */ | ||
465 | entry->scheduled->rt_param.scheduled_on = NO_CPU; | ||
466 | TRACE_TASK(entry->scheduled, "scheduled_on = NO_CPU\n"); | ||
467 | } | ||
468 | } else | ||
469 | /* Only override Linux scheduler if we have a real-time task | ||
470 | * scheduled that needs to continue. | ||
471 | */ | ||
472 | if (exists) | ||
473 | next = prev; | ||
474 | |||
475 | spin_unlock(&gsnedf_lock); | ||
476 | |||
477 | TRACE("gsnedf_lock released, next=0x%p\n", next); | ||
478 | |||
479 | |||
480 | if (next) | ||
481 | TRACE_TASK(next, "scheduled at %llu\n", litmus_clock()); | ||
482 | else if (exists && !next) | ||
483 | TRACE("becomes idle at %llu.\n", litmus_clock()); | ||
484 | |||
485 | |||
486 | return next; | ||
487 | } | ||
488 | |||
489 | |||
490 | /* _finish_switch - we just finished the switch away from prev | ||
491 | */ | ||
492 | static void gsnedf_finish_switch(struct task_struct *prev) | ||
493 | { | ||
494 | cpu_entry_t* entry = &__get_cpu_var(gsnedf_cpu_entries); | ||
495 | |||
496 | entry->scheduled = is_realtime(current) ? current : NULL; | ||
497 | TRACE_TASK(prev, "switched away from\n"); | ||
498 | } | ||
499 | |||
500 | |||
501 | /* Prepare a task for running in RT mode | ||
502 | */ | ||
503 | static void gsnedf_task_new(struct task_struct * t, int on_rq, int running) | ||
504 | { | ||
505 | unsigned long flags; | ||
506 | cpu_entry_t* entry; | ||
507 | |||
508 | TRACE("gsn edf: task new %d\n", t->pid); | ||
509 | |||
510 | spin_lock_irqsave(&gsnedf_lock, flags); | ||
511 | |||
512 | /* setup job params */ | ||
513 | release_at(t, litmus_clock()); | ||
514 | |||
515 | if (running) { | ||
516 | entry = &per_cpu(gsnedf_cpu_entries, task_cpu(t)); | ||
517 | BUG_ON(entry->scheduled); | ||
518 | entry->scheduled = t; | ||
519 | tsk_rt(t)->scheduled_on = task_cpu(t); | ||
520 | } else { | ||
521 | t->rt_param.scheduled_on = NO_CPU; | ||
522 | } | ||
523 | t->rt_param.linked_on = NO_CPU; | ||
524 | |||
525 | gsnedf_job_arrival(t); | ||
526 | spin_unlock_irqrestore(&gsnedf_lock, flags); | ||
527 | } | ||
528 | |||
529 | static void gsnedf_task_wake_up(struct task_struct *task) | ||
530 | { | ||
531 | unsigned long flags; | ||
532 | lt_t now; | ||
533 | |||
534 | TRACE_TASK(task, "wake_up at %llu\n", litmus_clock()); | ||
535 | |||
536 | spin_lock_irqsave(&gsnedf_lock, flags); | ||
537 | /* We need to take suspensions because of semaphores into | ||
538 | * account! If a job resumes after being suspended due to acquiring | ||
539 | * a semaphore, it should never be treated as a new job release. | ||
540 | */ | ||
541 | if (get_rt_flags(task) == RT_F_EXIT_SEM) { | ||
542 | set_rt_flags(task, RT_F_RUNNING); | ||
543 | } else { | ||
544 | now = litmus_clock(); | ||
545 | if (is_tardy(task, now)) { | ||
546 | /* new sporadic release */ | ||
547 | release_at(task, now); | ||
548 | sched_trace_task_release(task); | ||
549 | } | ||
550 | else { | ||
551 | if (task->rt.time_slice) { | ||
552 | /* came back in time before deadline | ||
553 | */ | ||
554 | set_rt_flags(task, RT_F_RUNNING); | ||
555 | } | ||
556 | } | ||
557 | } | ||
558 | gsnedf_job_arrival(task); | ||
559 | spin_unlock_irqrestore(&gsnedf_lock, flags); | ||
560 | } | ||
561 | |||
562 | static void gsnedf_task_block(struct task_struct *t) | ||
563 | { | ||
564 | unsigned long flags; | ||
565 | |||
566 | TRACE_TASK(t, "block at %llu\n", litmus_clock()); | ||
567 | |||
568 | /* unlink if necessary */ | ||
569 | spin_lock_irqsave(&gsnedf_lock, flags); | ||
570 | unlink(t); | ||
571 | spin_unlock_irqrestore(&gsnedf_lock, flags); | ||
572 | |||
573 | BUG_ON(!is_realtime(t)); | ||
574 | } | ||
575 | |||
576 | |||
577 | static void gsnedf_task_exit(struct task_struct * t) | ||
578 | { | ||
579 | unsigned long flags; | ||
580 | |||
581 | /* unlink if necessary */ | ||
582 | spin_lock_irqsave(&gsnedf_lock, flags); | ||
583 | unlink(t); | ||
584 | if (tsk_rt(t)->scheduled_on != NO_CPU) { | ||
585 | gsnedf_cpus[tsk_rt(t)->scheduled_on]->scheduled = NULL; | ||
586 | tsk_rt(t)->scheduled_on = NO_CPU; | ||
587 | } | ||
588 | spin_unlock_irqrestore(&gsnedf_lock, flags); | ||
589 | |||
590 | BUG_ON(!is_realtime(t)); | ||
591 | TRACE_TASK(t, "RIP\n"); | ||
592 | } | ||
593 | |||
594 | #ifdef CONFIG_FMLP | ||
595 | |||
596 | /* Update the queue position of a task that got it's priority boosted via | ||
597 | * priority inheritance. */ | ||
598 | static void update_queue_position(struct task_struct *holder) | ||
599 | { | ||
600 | /* We don't know whether holder is in the ready queue. It should, but | ||
601 | * on a budget overrun it may already be in a release queue. Hence, | ||
602 | * calling unlink() is not possible since it assumes that the task is | ||
603 | * not in a release queue. However, we can safely check whether | ||
604 | * sem->holder is currently in a queue or scheduled after locking both | ||
605 | * the release and the ready queue lock. */ | ||
606 | |||
607 | /* Assumption: caller holds gsnedf_lock */ | ||
608 | |||
609 | int check_preempt = 0; | ||
610 | |||
611 | if (tsk_rt(holder)->linked_on != NO_CPU) { | ||
612 | TRACE_TASK(holder, "%s: linked on %d\n", | ||
613 | __FUNCTION__, tsk_rt(holder)->linked_on); | ||
614 | /* Holder is scheduled; need to re-order CPUs. | ||
615 | * We can't use heap_decrease() here since | ||
616 | * the cpu_heap is ordered in reverse direction, so | ||
617 | * it is actually an increase. */ | ||
618 | heap_delete(cpu_lower_prio, &gsnedf_cpu_heap, | ||
619 | gsnedf_cpus[tsk_rt(holder)->linked_on]->hn); | ||
620 | heap_insert(cpu_lower_prio, &gsnedf_cpu_heap, | ||
621 | gsnedf_cpus[tsk_rt(holder)->linked_on]->hn); | ||
622 | } else { | ||
623 | /* holder may be queued: first stop queue changes */ | ||
624 | spin_lock(&gsnedf.release_lock); | ||
625 | if (is_queued(holder)) { | ||
626 | TRACE_TASK(holder, "%s: is queued\n", | ||
627 | __FUNCTION__); | ||
628 | /* We need to update the position | ||
629 | * of holder in some heap. Note that this | ||
630 | * may be a release heap. */ | ||
631 | check_preempt = | ||
632 | !heap_decrease(edf_ready_order, | ||
633 | tsk_rt(holder)->heap_node); | ||
634 | } else { | ||
635 | /* Nothing to do: if it is not queued and not linked | ||
636 | * then it is currently being moved by other code | ||
637 | * (e.g., a timer interrupt handler) that will use the | ||
638 | * correct priority when enqueuing the task. */ | ||
639 | TRACE_TASK(holder, "%s: is NOT queued => Done.\n", | ||
640 | __FUNCTION__); | ||
641 | } | ||
642 | spin_unlock(&gsnedf.release_lock); | ||
643 | |||
644 | /* If holder was enqueued in a release heap, then the following | ||
645 | * preemption check is pointless, but we can't easily detect | ||
646 | * that case. If you want to fix this, then consider that | ||
647 | * simply adding a state flag requires O(n) time to update when | ||
648 | * releasing n tasks, which conflicts with the goal to have | ||
649 | * O(log n) merges. */ | ||
650 | if (check_preempt) { | ||
651 | /* heap_decrease() hit the top level of the heap: make | ||
652 | * sure preemption checks get the right task, not the | ||
653 | * potentially stale cache. */ | ||
654 | heap_uncache_min(edf_ready_order, | ||
655 | &gsnedf.ready_queue); | ||
656 | check_for_preemptions(); | ||
657 | } | ||
658 | } | ||
659 | } | ||
660 | |||
661 | static long gsnedf_pi_block(struct pi_semaphore *sem, | ||
662 | struct task_struct *new_waiter) | ||
663 | { | ||
664 | /* This callback has to handle the situation where a new waiter is | ||
665 | * added to the wait queue of the semaphore. | ||
666 | * | ||
667 | * We must check if has a higher priority than the currently | ||
668 | * highest-priority task, and then potentially reschedule. | ||
669 | */ | ||
670 | |||
671 | BUG_ON(!new_waiter); | ||
672 | |||
673 | if (edf_higher_prio(new_waiter, sem->hp.task)) { | ||
674 | TRACE_TASK(new_waiter, " boosts priority via %p\n", sem); | ||
675 | /* called with IRQs disabled */ | ||
676 | spin_lock(&gsnedf_lock); | ||
677 | /* store new highest-priority task */ | ||
678 | sem->hp.task = new_waiter; | ||
679 | if (sem->holder) { | ||
680 | TRACE_TASK(sem->holder, | ||
681 | " holds %p and will inherit from %s/%d\n", | ||
682 | sem, | ||
683 | new_waiter->comm, new_waiter->pid); | ||
684 | /* let holder inherit */ | ||
685 | sem->holder->rt_param.inh_task = new_waiter; | ||
686 | update_queue_position(sem->holder); | ||
687 | } | ||
688 | spin_unlock(&gsnedf_lock); | ||
689 | } | ||
690 | |||
691 | return 0; | ||
692 | } | ||
693 | |||
694 | static long gsnedf_inherit_priority(struct pi_semaphore *sem, | ||
695 | struct task_struct *new_owner) | ||
696 | { | ||
697 | /* We don't need to acquire the gsnedf_lock since at the time of this | ||
698 | * call new_owner isn't actually scheduled yet (it's still sleeping) | ||
699 | * and since the calling function already holds sem->wait.lock, which | ||
700 | * prevents concurrent sem->hp.task changes. | ||
701 | */ | ||
702 | |||
703 | if (sem->hp.task && sem->hp.task != new_owner) { | ||
704 | new_owner->rt_param.inh_task = sem->hp.task; | ||
705 | TRACE_TASK(new_owner, "inherited priority from %s/%d\n", | ||
706 | sem->hp.task->comm, sem->hp.task->pid); | ||
707 | } else | ||
708 | TRACE_TASK(new_owner, | ||
709 | "cannot inherit priority, " | ||
710 | "no higher priority job waits.\n"); | ||
711 | return 0; | ||
712 | } | ||
713 | |||
714 | /* This function is called on a semaphore release, and assumes that | ||
715 | * the current task is also the semaphore holder. | ||
716 | */ | ||
717 | static long gsnedf_return_priority(struct pi_semaphore *sem) | ||
718 | { | ||
719 | struct task_struct* t = current; | ||
720 | int ret = 0; | ||
721 | |||
722 | /* Find new highest-priority semaphore task | ||
723 | * if holder task is the current hp.task. | ||
724 | * | ||
725 | * Calling function holds sem->wait.lock. | ||
726 | */ | ||
727 | if (t == sem->hp.task) | ||
728 | edf_set_hp_task(sem); | ||
729 | |||
730 | TRACE_CUR("gsnedf_return_priority for lock %p\n", sem); | ||
731 | |||
732 | if (t->rt_param.inh_task) { | ||
733 | /* interrupts already disabled by PI code */ | ||
734 | spin_lock(&gsnedf_lock); | ||
735 | |||
736 | /* Reset inh_task to NULL. */ | ||
737 | t->rt_param.inh_task = NULL; | ||
738 | |||
739 | /* Check if rescheduling is necessary */ | ||
740 | unlink(t); | ||
741 | gsnedf_job_arrival(t); | ||
742 | spin_unlock(&gsnedf_lock); | ||
743 | } | ||
744 | |||
745 | return ret; | ||
746 | } | ||
747 | |||
748 | #endif | ||
749 | |||
750 | static long gsnedf_admit_task(struct task_struct* tsk) | ||
751 | { | ||
752 | return 0; | ||
753 | } | ||
754 | |||
755 | static long gsnedf_activate_plugin(void) | ||
756 | { | ||
757 | int cpu; | ||
758 | cpu_entry_t *entry; | ||
759 | |||
760 | heap_init(&gsnedf_cpu_heap); | ||
761 | |||
762 | for_each_online_cpu(cpu) { | ||
763 | entry = &per_cpu(gsnedf_cpu_entries, cpu); | ||
764 | heap_node_init(&entry->hn, entry); | ||
765 | atomic_set(&entry->will_schedule, 0); | ||
766 | entry->linked = NULL; | ||
767 | entry->scheduled = NULL; | ||
768 | TRACE("GSN-EDF: Initializing CPU #%d.\n", cpu); | ||
769 | update_cpu_position(entry); | ||
770 | } | ||
771 | return 0; | ||
772 | } | ||
773 | |||
774 | /* Plugin object */ | ||
775 | static struct sched_plugin gsn_edf_plugin __cacheline_aligned_in_smp = { | ||
776 | .plugin_name = "GSN-EDF", | ||
777 | .finish_switch = gsnedf_finish_switch, | ||
778 | .tick = gsnedf_tick, | ||
779 | .task_new = gsnedf_task_new, | ||
780 | .complete_job = complete_job, | ||
781 | .task_exit = gsnedf_task_exit, | ||
782 | .schedule = gsnedf_schedule, | ||
783 | .task_wake_up = gsnedf_task_wake_up, | ||
784 | .task_block = gsnedf_task_block, | ||
785 | #ifdef CONFIG_FMLP | ||
786 | .fmlp_active = 1, | ||
787 | .pi_block = gsnedf_pi_block, | ||
788 | .inherit_priority = gsnedf_inherit_priority, | ||
789 | .return_priority = gsnedf_return_priority, | ||
790 | #endif | ||
791 | .admit_task = gsnedf_admit_task, | ||
792 | .activate_plugin = gsnedf_activate_plugin, | ||
793 | }; | ||
794 | |||
795 | |||
796 | static int __init init_gsn_edf(void) | ||
797 | { | ||
798 | int cpu; | ||
799 | cpu_entry_t *entry; | ||
800 | |||
801 | heap_init(&gsnedf_cpu_heap); | ||
802 | /* initialize CPU state */ | ||
803 | for (cpu = 0; cpu < NR_CPUS; cpu++) { | ||
804 | entry = &per_cpu(gsnedf_cpu_entries, cpu); | ||
805 | gsnedf_cpus[cpu] = entry; | ||
806 | atomic_set(&entry->will_schedule, 0); | ||
807 | entry->cpu = cpu; | ||
808 | entry->hn = &gsnedf_heap_node[cpu]; | ||
809 | heap_node_init(&entry->hn, entry); | ||
810 | } | ||
811 | edf_domain_init(&gsnedf, NULL, gsnedf_release_jobs); | ||
812 | return register_sched_plugin(&gsn_edf_plugin); | ||
813 | } | ||
814 | |||
815 | |||
816 | module_init(init_gsn_edf); | ||