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