From f80c0017e4bdbb19a6060b97673b09103806a0c5 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 27 Sep 2013 13:03:01 -0400 Subject: Add control page variables for PGM. Currently, PGM token satisfaction is tracked in userspace. However, Litmus needs to be aware of when a PGM task is waiting for tokens in order to avoid unbounded priority inversions. The state of a PGM task is communicated to Litmus via the control page. We should be able to remove control page variables for PGM if/when token tracking is moved from userspace into the kernel. --- include/litmus/rt_param.h | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h index 138799fbaad7..bc074c63c7ad 100644 --- a/include/litmus/rt_param.h +++ b/include/litmus/rt_param.h @@ -121,6 +121,10 @@ struct control_page { uint64_t irq_syscall_start; /* Snapshot of irq_count when the syscall * started. */ + /* Flags from userspace signifying PGM wait states. */ + volatile uint32_t pgm_waiting; /* waiting for tokens */ + volatile uint32_t pgm_satisfied; /* needed tokens acquired */ + /* to be extended */ }; -- cgit v1.2.2 From ee3539ec754976c2303905de2ef87fef3395b518 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 27 Sep 2013 13:13:43 -0400 Subject: Add CONFIG_SCHED_PGM to litmus/Kconfig Conditional compilation of PGM features. Off by default. --- litmus/Kconfig | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/litmus/Kconfig b/litmus/Kconfig index 5d5d6eb29882..11f2801a943f 100644 --- a/litmus/Kconfig +++ b/litmus/Kconfig @@ -58,6 +58,18 @@ config BUG_ON_MIGRATION_DEADLOCK BUG() triggers, the scheduler is broken and turning off this option won't fix it. +config SCHED_PGM + bool "PGM Support" + default n + depends on LITMUS_LOCKING && ALLOW_EARLY_RELEASE + help + Include infrastructure for scheduling PGM graphs. Since PGM token + constraints are not (yet) implemented in the kernel, a job must + tell Litmus when it is waiting for tokens. Litmus boost's the + priority of waiting jobs (which are expected to be well-behaved + and sleep while waiting for tokens) to ensure bounded priority + inversions. Litmus may also change a jobs release/deadline depending + upon when the jobs input tokens are generated. endmenu -- cgit v1.2.2 From 97c8136fe53b81b1b44dc1b9528d2723d9032dcf Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 27 Sep 2013 13:19:57 -0400 Subject: PGM release/deadline adjustment. Adds code that adjusts a jobs release and deadline according to when the job receives the necessary PGM tokens. --- include/litmus/pgm.h | 11 +++++++++++ litmus/Makefile | 1 + litmus/pgm.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 66 insertions(+) create mode 100644 include/litmus/pgm.h create mode 100644 litmus/pgm.c diff --git a/include/litmus/pgm.h b/include/litmus/pgm.h new file mode 100644 index 000000000000..1e87e170e8c3 --- /dev/null +++ b/include/litmus/pgm.h @@ -0,0 +1,11 @@ +#ifndef _LITMUS_PGM_H_ +#define _LITMUS_PGM_H_ + +#include + +#define is_pgm_waiting(t) (tsk_rt(t)->ctrl_page && tsk_rt(t)->ctrl_page->pgm_waiting) +#define is_pgm_satisfied(t) (tsk_rt(t)->ctrl_page && tsk_rt(t)->ctrl_page->pgm_satisfied) + +void setup_pgm_release(struct task_struct* t); + +#endif diff --git a/litmus/Makefile b/litmus/Makefile index 2bddc94a399f..52f407cad77c 100644 --- a/litmus/Makefile +++ b/litmus/Makefile @@ -26,6 +26,7 @@ obj-y = sched_plugin.o litmus.o \ obj-$(CONFIG_PLUGIN_CEDF) += sched_cedf.o obj-$(CONFIG_PLUGIN_PFAIR) += sched_pfair.o obj-$(CONFIG_SCHED_CPU_AFFINITY) += affinity.o +obj-$(CONFIG_SCHED_PGM) += pgm.o obj-$(CONFIG_FEATHER_TRACE) += ft_event.o ftdev.o obj-$(CONFIG_SCHED_TASK_TRACE) += sched_task_trace.o diff --git a/litmus/pgm.c b/litmus/pgm.c new file mode 100644 index 000000000000..f8b857de8118 --- /dev/null +++ b/litmus/pgm.c @@ -0,0 +1,54 @@ +/* litmus/pgm.c - common pgm control code + */ + +#include +#include +#include + +/* Only readjust release/deadline if difference is over a given threshold. + It's a weak method for accounting overheads. Ideally, we'd know the last + time t was woken up by its last predecessor, rather than having to look + at 'now'. */ +#define ADJUSTMENT_THRESH_US 200 + +void setup_pgm_release(struct task_struct* t) +{ + /* approximate time last predecessor gave us tokens */ + lt_t now = litmus_clock(); + + TRACE_TASK(t, "is starting a new PGM job: waiting:%d satisfied:%d\n", + tsk_rt(t)->ctrl_page->pgm_waiting, tsk_rt(t)->ctrl_page->pgm_satisfied); + + BUG_ON(!tsk_rt(t)->ctrl_page->pgm_waiting || !tsk_rt(t)->ctrl_page->pgm_satisfied); + + tsk_rt(t)->ctrl_page->pgm_waiting = 0; + tsk_rt(t)->ctrl_page->pgm_satisfied = 0; + + /* Adjust release time if we got the last tokens after release of this job. + This is possible since PGM jobs are early-released. Don't shift our + deadline if we got the tokens earlier than expected. */ + if (now > tsk_rt(t)->job_params.release) { + long long diff = now - tsk_rt(t)->job_params.release; + if (diff > ADJUSTMENT_THRESH_US) { + lt_t adj_deadline = now + get_rt_relative_deadline(t); + + TRACE_TASK(t, "adjusting PGM release time from (r = %llu, d = %llu) " + "to (r = %llu, d = %llu)\n", + tsk_rt(t)->job_params.release, tsk_rt(t)->job_params.deadline, + now, adj_deadline); + + tsk_rt(t)->job_params.release = now; + tsk_rt(t)->job_params.deadline = adj_deadline; + tsk_rt(t)->job_params.exec_time = 0; /* reset budget */ + } + else { + TRACE_TASK(t, "adjustment falls below threshold. %lld < %lld\n", + diff, ADJUSTMENT_THRESH_US); + } + } + else { + TRACE_TASK(t, "got tokens early--no need to adjust release. " + "cur time = %llu, release time = %llu\n", + now, tsk_rt(t)->job_params.release); + } +} -- cgit v1.2.2 From 727b01be1052e3347b9dbc09692ad6d005fef019 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 27 Sep 2013 13:33:03 -0400 Subject: PGM support in GSN-EDF. Patch enables PGM support by GSN-EDF. GSN-EDF boosts the priority of a job waiting for inbound tokens. Likewise, boosting is removed when inbound tokens have been received. --- litmus/sched_gsn_edf.c | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c index 66ffa3e7a7bd..c5c4d4947c5a 100644 --- a/litmus/sched_gsn_edf.c +++ b/litmus/sched_gsn_edf.c @@ -29,6 +29,10 @@ #include #endif +#ifdef CONFIG_SCHED_PGM +#include +#endif + #include /* Overview of GSN-EDF operations. @@ -458,6 +462,42 @@ static struct task_struct* gsnedf_schedule(struct task_struct * prev) TRACE_TASK(prev, "will be preempted by %s/%d\n", entry->linked->comm, entry->linked->pid); +#ifdef CONFIG_SCHED_PGM + if (exists && is_pgm_waiting(entry->scheduled)) { + if (!is_priority_boosted(entry->scheduled)) { + TRACE_TASK(entry->scheduled, "is waiting for PGM tokens.\n"); + BUG_ON(is_pgm_satisfied(entry->scheduled)); + + /* Boost priority so we'll be scheduled immediately + when needed tokens arrive. */ + tsk_rt(entry->scheduled)->priority_boosted = 1; + tsk_rt(entry->scheduled)->boost_start_time = litmus_clock(); + + if (unlikely(!blocks)) { + /* Task has probably blocked on an inbound token socket, but + if not, re-evaluate scheduling decisions */ + unlink(entry->scheduled); + gsnedf_job_arrival(entry->scheduled); + } + } + else if (is_pgm_satisfied(entry->scheduled)) { + TRACE_TASK(entry->scheduled, "is done waiting for PGM tokens.\n"); + BUG_ON(!is_priority_boosted(entry->scheduled)); + + /* clear any boosting */ + tsk_rt(entry->scheduled)->priority_boosted = 0; + setup_pgm_release(entry->scheduled); + + if (likely(!blocks)) { + /* Task has probably called sched_yield(), so blocking is + unlikely. Re-evaluate scheduling decisions because we + still want to run. */ + unlink(entry->scheduled); + gsnedf_job_arrival(entry->scheduled); + } + } + } +#endif /* If a task blocks we have no choice but to reschedule. */ -- cgit v1.2.2 From e20031840e463ef39e3c845dc3b74567fd6a4b93 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 27 Sep 2013 13:44:08 -0400 Subject: Tracing for PGM release/deadline adjustment. Patch adds tracing of job release/deadline adjustments of PGM tasks. Tracing is separate from regular job tracing so that we many observe the magnitude of adjustments/slippage. --- include/litmus/sched_trace.h | 19 ++++++++++++++++++- include/trace/events/litmus.h | 28 ++++++++++++++++++++++++++++ litmus/pgm.c | 3 +++ litmus/sched_task_trace.c | 12 +++++++++++- 4 files changed, 60 insertions(+), 2 deletions(-) diff --git a/include/litmus/sched_trace.h b/include/litmus/sched_trace.h index 82bde8241298..3d3b06ced797 100644 --- a/include/litmus/sched_trace.h +++ b/include/litmus/sched_trace.h @@ -80,6 +80,11 @@ struct st_sys_release_data { u64 release; }; +struct st_pgm_release_data { + u64 release; /* PGM-adjusted release time */ + u64 deadline; /* PGM-adjusted deadline */ +}; + #define DATA(x) struct st_ ## x ## _data x; typedef enum { @@ -94,7 +99,8 @@ typedef enum { ST_BLOCK, ST_RESUME, ST_ACTION, - ST_SYS_RELEASE + ST_SYS_RELEASE, + ST_PGM_RELEASE } st_event_record_type_t; struct st_event_record { @@ -113,6 +119,7 @@ struct st_event_record { DATA(resume); DATA(action); DATA(sys_release); + DATA(pgm_release); } data; }; @@ -154,6 +161,8 @@ feather_callback void do_sched_trace_action(unsigned long id, unsigned long action); feather_callback void do_sched_trace_sys_release(unsigned long id, lt_t* start); +feather_callback void do_sched_trace_pgm_release(unsigned long id, + struct task_struct* task); #endif @@ -179,6 +188,7 @@ feather_callback void do_sched_trace_sys_release(unsigned long id, #define trace_litmus_task_block(t) #define trace_litmus_task_resume(t) #define trace_litmus_sys_release(start) +#define trace_litmus_pgm_release(t) #endif @@ -252,6 +262,13 @@ feather_callback void do_sched_trace_sys_release(unsigned long id, trace_litmus_sys_release(when); \ } while (0) +#define sched_trace_pgm_release(t) \ + do { \ + SCHED_TRACE(SCHED_TRACE_BASE_ID + 11, \ + do_sched_trace_pgm_release, t); \ + trace_litmus_pgm_release(t); \ + } while (0) + #define sched_trace_quantum_boundary() /* NOT IMPLEMENTED */ #endif /* __KERNEL__ */ diff --git a/include/trace/events/litmus.h b/include/trace/events/litmus.h index 0fffcee02be0..0b4eac386dfe 100644 --- a/include/trace/events/litmus.h +++ b/include/trace/events/litmus.h @@ -225,6 +225,34 @@ TRACE_EVENT(litmus_sys_release, TP_printk("SynRelease(%Lu) at %Lu\n", __entry->rel, __entry->when) ); +/* + * Tracing PGM-adjusted job release + */ +TRACE_EVENT(litmus_pgm_release, + + TP_PROTO(struct task_struct *t), + + TP_ARGS(t), + + TP_STRUCT__entry( + __field( pid_t, pid ) + __field( unsigned int, job ) + __field( lt_t, release ) + __field( lt_t, deadline ) + ), + + TP_fast_assign( + __entry->pid = t ? t->pid : 0; + __entry->job = t ? t->rt_param.job_params.job_no : 0; + __entry->release = get_release(t); + __entry->deadline = get_deadline(t); + ), + + TP_printk("release(job(%u, %u)): %Lu\ndeadline(job(%u, %u)): %Lu\n", + __entry->pid, __entry->job, __entry->release, + __entry->pid, __entry->job, __entry->deadline) +); + #endif /* _SCHED_TASK_TRACEPOINT_H */ /* Must stay outside the protection */ diff --git a/litmus/pgm.c b/litmus/pgm.c index f8b857de8118..2bfa8d0843c1 100644 --- a/litmus/pgm.c +++ b/litmus/pgm.c @@ -4,6 +4,7 @@ #include #include #include +#include /* Only readjust release/deadline if difference is over a given threshold. It's a weak method for accounting overheads. Ideally, we'd know the last @@ -51,4 +52,6 @@ void setup_pgm_release(struct task_struct* t) "cur time = %llu, release time = %llu\n", now, tsk_rt(t)->job_params.release); } + + sched_trace_pgm_release(t); } diff --git a/litmus/sched_task_trace.c b/litmus/sched_task_trace.c index 933e7e4c7094..422314f29a60 100644 --- a/litmus/sched_task_trace.c +++ b/litmus/sched_task_trace.c @@ -231,10 +231,20 @@ feather_callback void do_sched_trace_action(unsigned long id, { struct task_struct *t = (struct task_struct*) _task; struct st_event_record* rec = get_record(ST_ACTION, t); - if (rec) { rec->data.action.when = now(); rec->data.action.action = action; put_record(rec); } } + +feather_callback void do_sched_trace_pgm_release(unsigned long id, unsigned long _task) +{ + struct task_struct *t = (struct task_struct*) _task; + struct st_event_record* rec = get_record(ST_PGM_RELEASE, t); + if (rec) { + rec->data.release.release = get_release(t); + rec->data.release.deadline = get_deadline(t); + put_record(rec); + } +} -- cgit v1.2.2 From a62f9db5b5e183287bffd7f1ece26225f6ed1d61 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 27 Sep 2013 13:47:31 -0400 Subject: Fix: Incorrectly expressed PGM adjustment thresh. PGM release/deadline adjustment is ignored if the difference between an adjusted time and current time falls below a given threshold. This threshold is supposed to be 200us, but was actually 200ns. This patch resolves this--threshold is now propertly 200us. --- litmus/pgm.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/litmus/pgm.c b/litmus/pgm.c index 2bfa8d0843c1..0bc190851718 100644 --- a/litmus/pgm.c +++ b/litmus/pgm.c @@ -9,8 +9,8 @@ /* Only readjust release/deadline if difference is over a given threshold. It's a weak method for accounting overheads. Ideally, we'd know the last time t was woken up by its last predecessor, rather than having to look - at 'now'. */ -#define ADJUSTMENT_THRESH_US 200 + at 'now'. Adjustment threshold currently set to 200us. */ +#define ADJUSTMENT_THRESH_NS (200*1000LL) void setup_pgm_release(struct task_struct* t) { @@ -29,8 +29,8 @@ void setup_pgm_release(struct task_struct* t) This is possible since PGM jobs are early-released. Don't shift our deadline if we got the tokens earlier than expected. */ if (now > tsk_rt(t)->job_params.release) { - long long diff = now - tsk_rt(t)->job_params.release; - if (diff > ADJUSTMENT_THRESH_US) { + long long diff_ns = now - tsk_rt(t)->job_params.release; + if (diff_ns > ADJUSTMENT_THRESH_NS) { lt_t adj_deadline = now + get_rt_relative_deadline(t); TRACE_TASK(t, "adjusting PGM release time from (r = %llu, d = %llu) " @@ -44,7 +44,7 @@ void setup_pgm_release(struct task_struct* t) } else { TRACE_TASK(t, "adjustment falls below threshold. %lld < %lld\n", - diff, ADJUSTMENT_THRESH_US); + diff_ns, ADJUSTMENT_THRESH_NS); } } else { -- cgit v1.2.2 From f5bf97f1f5345f7e8aef2b99ec0d57ddd081c1d2 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 27 Sep 2013 13:53:31 -0400 Subject: Add PGM support to C-EDF. Patch adds PGM priority boosting (and un-boosting) to C-EDF. --- litmus/sched_cedf.c | 40 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 40 insertions(+) diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c index 7cb3cc07ed21..b6bed80133f7 100644 --- a/litmus/sched_cedf.c +++ b/litmus/sched_cedf.c @@ -48,6 +48,10 @@ #include #endif +#ifdef CONFIG_SCHED_PGM +#include +#endif + /* to configure the cluster size */ #include #include @@ -459,6 +463,42 @@ static struct task_struct* cedf_schedule(struct task_struct * prev) TRACE_TASK(prev, "will be preempted by %s/%d\n", entry->linked->comm, entry->linked->pid); +#ifdef CONFIG_SCHED_PGM + if (exists && is_pgm_waiting(entry->scheduled)) { + if (!is_priority_boosted(entry->scheduled)) { + TRACE_TASK(entry->scheduled, "is waiting for PGM tokens.\n"); + BUG_ON(is_pgm_satisfied(entry->scheduled)); + + /* Boost priority so we'll be scheduled immediately + when needed tokens arrive. */ + tsk_rt(entry->scheduled)->priority_boosted = 1; + tsk_rt(entry->scheduled)->boost_start_time = litmus_clock(); + + if (unlikely(!blocks)) { + /* Task has probably blocked on an inbound token socket, but + if not, re-evaluate scheduling decisions */ + unlink(entry->scheduled); + cedf_job_arrival(entry->scheduled); + } + } + else if (is_pgm_satisfied(entry->scheduled)) { + TRACE_TASK(entry->scheduled, "is done waiting for PGM tokens.\n"); + BUG_ON(!is_priority_boosted(entry->scheduled)); + + /* clear any boosting */ + tsk_rt(entry->scheduled)->priority_boosted = 0; + setup_pgm_release(entry->scheduled); + + if (likely(!blocks)) { + /* Task has probably called sched_yield(), so blocking is + unlikely. Re-evaluate scheduling decisions because we + still want to run. */ + unlink(entry->scheduled); + cedf_job_arrival(entry->scheduled); + } + } + } +#endif /* If a task blocks we have no choice but to reschedule. */ -- cgit v1.2.2 From b2b3e869e8d5fee88aabf001c09094b400450bac Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Tue, 19 Nov 2013 14:12:08 -0500 Subject: PGM: Boost priority of producers, not consumers. This patch boosts the priority of PGM producers while they are sending tokens instead of boosting the priority of consumers while they are waiting for tokens. This improves schedulability analysis. --- include/litmus/pgm.h | 3 +- include/litmus/rt_param.h | 5 +-- litmus/pgm.c | 20 +++++++----- litmus/sched_cedf.c | 81 +++++++++++++++++++++++++++++++---------------- 4 files changed, 71 insertions(+), 38 deletions(-) diff --git a/include/litmus/pgm.h b/include/litmus/pgm.h index 1e87e170e8c3..5682a76b3acb 100644 --- a/include/litmus/pgm.h +++ b/include/litmus/pgm.h @@ -4,8 +4,9 @@ #include #define is_pgm_waiting(t) (tsk_rt(t)->ctrl_page && tsk_rt(t)->ctrl_page->pgm_waiting) +#define is_pgm_sending(t) (tsk_rt(t)->ctrl_page && tsk_rt(t)->ctrl_page->pgm_sending) #define is_pgm_satisfied(t) (tsk_rt(t)->ctrl_page && tsk_rt(t)->ctrl_page->pgm_satisfied) -void setup_pgm_release(struct task_struct* t); +int setup_pgm_release(struct task_struct* t); #endif diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h index bc074c63c7ad..fe4b31320ac8 100644 --- a/include/litmus/rt_param.h +++ b/include/litmus/rt_param.h @@ -122,8 +122,9 @@ struct control_page { * started. */ /* Flags from userspace signifying PGM wait states. */ - volatile uint32_t pgm_waiting; /* waiting for tokens */ - volatile uint32_t pgm_satisfied; /* needed tokens acquired */ + volatile uint32_t pgm_waiting; /* waiting for tokens */ + volatile uint32_t pgm_sending; /* sending tokens */ + volatile uint32_t pgm_satisfied; /* done waiting/sending */ /* to be extended */ }; diff --git a/litmus/pgm.c b/litmus/pgm.c index 0bc190851718..db3378ff803d 100644 --- a/litmus/pgm.c +++ b/litmus/pgm.c @@ -12,18 +12,17 @@ at 'now'. Adjustment threshold currently set to 200us. */ #define ADJUSTMENT_THRESH_NS (200*1000LL) -void setup_pgm_release(struct task_struct* t) +int setup_pgm_release(struct task_struct* t) { + int shifted_release = 0; + /* approximate time last predecessor gave us tokens */ lt_t now = litmus_clock(); - TRACE_TASK(t, "is starting a new PGM job: waiting:%d satisfied:%d\n", - tsk_rt(t)->ctrl_page->pgm_waiting, tsk_rt(t)->ctrl_page->pgm_satisfied); - - BUG_ON(!tsk_rt(t)->ctrl_page->pgm_waiting || !tsk_rt(t)->ctrl_page->pgm_satisfied); + TRACE_TASK(t, "is starting a new PGM job: waiting:%d\n", + tsk_rt(t)->ctrl_page->pgm_waiting); - tsk_rt(t)->ctrl_page->pgm_waiting = 0; - tsk_rt(t)->ctrl_page->pgm_satisfied = 0; + BUG_ON(!tsk_rt(t)->ctrl_page->pgm_waiting); /* Adjust release time if we got the last tokens after release of this job. This is possible since PGM jobs are early-released. Don't shift our @@ -40,7 +39,7 @@ void setup_pgm_release(struct task_struct* t) tsk_rt(t)->job_params.release = now; tsk_rt(t)->job_params.deadline = adj_deadline; - tsk_rt(t)->job_params.exec_time = 0; /* reset budget */ + shifted_release = 1; } else { TRACE_TASK(t, "adjustment falls below threshold. %lld < %lld\n", @@ -53,5 +52,10 @@ void setup_pgm_release(struct task_struct* t) now, tsk_rt(t)->job_params.release); } + /* possible that there can be multiple instances of pgm_release logged. + analysis tools should filter out all but the last pgm_release for + a given job release */ sched_trace_pgm_release(t); + + return shifted_release; } diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c index b6bed80133f7..8699f6d9d5b6 100644 --- a/litmus/sched_cedf.c +++ b/litmus/sched_cedf.c @@ -464,39 +464,62 @@ static struct task_struct* cedf_schedule(struct task_struct * prev) entry->linked->comm, entry->linked->pid); #ifdef CONFIG_SCHED_PGM - if (exists && is_pgm_waiting(entry->scheduled)) { - if (!is_priority_boosted(entry->scheduled)) { - TRACE_TASK(entry->scheduled, "is waiting for PGM tokens.\n"); - BUG_ON(is_pgm_satisfied(entry->scheduled)); - - /* Boost priority so we'll be scheduled immediately - when needed tokens arrive. */ - tsk_rt(entry->scheduled)->priority_boosted = 1; - tsk_rt(entry->scheduled)->boost_start_time = litmus_clock(); - - if (unlikely(!blocks)) { - /* Task has probably blocked on an inbound token socket, but - if not, re-evaluate scheduling decisions */ - unlink(entry->scheduled); - cedf_job_arrival(entry->scheduled); + if (exists) { + if (is_pgm_sending(entry->scheduled)) { + if (!is_pgm_satisfied(entry->scheduled)) { + if (!is_priority_boosted(entry->scheduled)) { + TRACE_TASK(entry->scheduled, "is sending PGM tokens and needs boosting.\n"); + BUG_ON(is_pgm_satisfied(entry->scheduled)); + + /* We are either sending tokens or waiting for tokes. + If waiting: Boost priority so we'll be scheduled + immediately when needed tokens arrive. + If sending: Boost priority so no one (specifically, our + consumers) will preempt us while signalling the token + transmission. + */ + tsk_rt(entry->scheduled)->priority_boosted = 1; + tsk_rt(entry->scheduled)->boost_start_time = litmus_clock(); + + if (likely(!blocks)) { + unlink(entry->scheduled); + cedf_job_arrival(entry->scheduled); + } + } + } + else { /* sending is satisfied */ + tsk_rt(entry->scheduled)->ctrl_page->pgm_sending = 0; + tsk_rt(entry->scheduled)->ctrl_page->pgm_satisfied = 0; + + if (is_priority_boosted(entry->scheduled)) { + TRACE_TASK(entry->scheduled, + "is done sending PGM tokens must relinquish boosting.\n"); + /* clear boosting */ + tsk_rt(entry->scheduled)->priority_boosted = 0; + if(likely(!blocks)) { + /* recheck priority */ + unlink(entry->scheduled); + cedf_job_arrival(entry->scheduled); + } + } } } - else if (is_pgm_satisfied(entry->scheduled)) { - TRACE_TASK(entry->scheduled, "is done waiting for PGM tokens.\n"); - BUG_ON(!is_priority_boosted(entry->scheduled)); - - /* clear any boosting */ - tsk_rt(entry->scheduled)->priority_boosted = 0; - setup_pgm_release(entry->scheduled); - - if (likely(!blocks)) { - /* Task has probably called sched_yield(), so blocking is - unlikely. Re-evaluate scheduling decisions because we - still want to run. */ +#if 0 + else if(is_pgm_waiting(entry->scheduled)) { + int shifted_release; + + TRACE_TASK(entry->scheduled, "is waiting for PGM tokens.\n"); + /* release the next job if we have the tokens we need */ + shifted_release = setup_pgm_release(entry->scheduled); + + /* setup_pgm_release() can screw with our priority, + so recheck it */ + if (shifted_release && likely(!blocks)) { unlink(entry->scheduled); cedf_job_arrival(entry->scheduled); } } +#endif } #endif @@ -641,6 +664,10 @@ static void cedf_task_wake_up(struct task_struct *task) release_at(task, now); sched_trace_task_release(task); } + if (is_pgm_waiting(task)) { + /* shift out release/deadline, if needed */ + setup_pgm_release(task); + } cedf_job_arrival(task); raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags); } -- cgit v1.2.2 From dfe59a59caec43172bbf09fe3e2e15e9395e7e6b Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Tue, 26 Nov 2013 14:41:19 -0500 Subject: Add C-FL scheduler plugin. This patch adds a C-FL scheduler plugin. Original work by Jeremy Erikson, port to latest Litmus by Namhoon Kim, and cleanup and commit by Glenn Elliott. --- include/litmus/edf_split_common.h | 25 + include/litmus/litmus.h | 4 + include/litmus/rt_param.h | 6 + litmus/Kconfig | 16 + litmus/Makefile | 1 + litmus/edf_split_common.c | 106 ++++ litmus/sched_cfl_split.c | 1006 +++++++++++++++++++++++++++++++++++++ 7 files changed, 1164 insertions(+) create mode 100644 include/litmus/edf_split_common.h create mode 100644 litmus/edf_split_common.c create mode 100644 litmus/sched_cfl_split.c diff --git a/include/litmus/edf_split_common.h b/include/litmus/edf_split_common.h new file mode 100644 index 000000000000..4e7c0ce23c9d --- /dev/null +++ b/include/litmus/edf_split_common.h @@ -0,0 +1,25 @@ +/* + * EDF common data structures and utility functions shared by all EDF + * based scheduler plugins + */ + +/* CLEANUP: Add comments and make it less messy. + * + */ + +#ifndef __UNC_EDF_SPLIT_COMMON_H__ +#define __UNC_EDF_SPLIT_COMMON_H__ + +#include + +void edf_split_domain_init(rt_domain_t* rt, check_resched_needed_t resched, + release_jobs_t release); + +int edf_split_higher_prio(struct task_struct* first, + struct task_struct* second); + +int edf_split_ready_order(struct bheap_node* a, struct bheap_node* b); + +int edf_split_preemption_needed(rt_domain_t* rt, struct task_struct *t); + +#endif diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h index e35c38c4c0a2..c240d9c07169 100644 --- a/include/litmus/litmus.h +++ b/include/litmus/litmus.h @@ -67,6 +67,7 @@ void litmus_exit_task(struct task_struct *tsk); /* job_param macros */ #define get_exec_time(t) (tsk_rt(t)->job_params.exec_time) #define get_deadline(t) (tsk_rt(t)->job_params.deadline) +#define get_subjob_deadline(t) (tsk_rt(t)->job_params.subjob_deadline) #define get_release(t) (tsk_rt(t)->job_params.release) #define get_lateness(t) (tsk_rt(t)->job_params.lateness) @@ -118,6 +119,9 @@ static inline lt_t litmus_clock(void) #define earlier_release(a, b) (lt_before(\ (a)->rt_param.job_params.release,\ (b)->rt_param.job_params.release)) +#define earlier_subjob_deadline(a, b) (lt_before(\ + (a)->rt_param.job_params.subjob_deadline,\ + (b)->rt_param.job_params.subjob_deadline)) void preempt_if_preemptable(struct task_struct* t, int on_cpu); diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h index fe4b31320ac8..6160a1635227 100644 --- a/include/litmus/rt_param.h +++ b/include/litmus/rt_param.h @@ -76,6 +76,7 @@ struct rt_task { lt_t period; lt_t relative_deadline; lt_t phase; + int split; unsigned int cpu; unsigned int priority; task_class_t cls; @@ -149,6 +150,11 @@ struct rt_job { /* What is the current deadline? */ lt_t deadline; +#ifdef CONFIG_JOB_SPLITTING + /* What is the deadline of the current subjob under splitting? */ + lt_t subjob_deadline; +#endif + /* How much service has this job received so far? */ lt_t exec_time; diff --git a/litmus/Kconfig b/litmus/Kconfig index 11f2801a943f..49017b26d0d3 100644 --- a/litmus/Kconfig +++ b/litmus/Kconfig @@ -12,6 +12,15 @@ config PLUGIN_CEDF On smaller platforms (e.g., ARM PB11MPCore), using C-EDF makes little sense since there aren't any shared caches. +config PLUGIN_CFL + bool "Clustered-Fair-Lateness" + depends on X86 && SYSFS && JOB_SPLITTING + default n + help + Include the Clustered Fair Lateness (C-FL) plugin in the kernel. + This implements Anderson and Erickson's EDF-based scheduler. + Supports job splitting. + config PLUGIN_PFAIR bool "PFAIR" depends on HIGH_RES_TIMERS && HZ_PERIODIC && HZ = "1000" @@ -26,6 +35,13 @@ config PLUGIN_PFAIR If unsure, say Yes. +config JOB_SPLITTING + bool "Job Splitting" + default n + help + Enable job-splitting features for fair-lateness schedulers, such + as C-FL. + config RELEASE_MASTER bool "Release-master Support" depends on ARCH_HAS_SEND_PULL_TIMERS && SMP diff --git a/litmus/Makefile b/litmus/Makefile index 52f407cad77c..6c83cf1734ba 100644 --- a/litmus/Makefile +++ b/litmus/Makefile @@ -25,6 +25,7 @@ obj-y = sched_plugin.o litmus.o \ obj-$(CONFIG_PLUGIN_CEDF) += sched_cedf.o obj-$(CONFIG_PLUGIN_PFAIR) += sched_pfair.o +obj-$(CONFIG_PLUGIN_CFL) += sched_cfl_split.o edf_split_common.o obj-$(CONFIG_SCHED_CPU_AFFINITY) += affinity.o obj-$(CONFIG_SCHED_PGM) += pgm.o diff --git a/litmus/edf_split_common.c b/litmus/edf_split_common.c new file mode 100644 index 000000000000..7d7f5429e4df --- /dev/null +++ b/litmus/edf_split_common.c @@ -0,0 +1,106 @@ +/* + * kernel/edf_split_common.c + * + * Common functions for EDF based scheduler with split jobs. + */ + +#include +#include +#include + +#include +#include +#include + +#include +#include + +/* edf_split_higher_prio - returns true if first has a higher subjob + * EDF priority than second. + * + * both first and second may be NULL + */ +int edf_split_higher_prio(struct task_struct* first, + struct task_struct* second) +{ + struct task_struct *first_task = first; + struct task_struct *second_task = second; + + /* There is no point in comparing a task to itself. */ + if (first && first == second) { + TRACE_TASK(first, + "WARNING: pointless edf priority comparison.\n"); + return 0; + } + + /* check for NULL tasks */ + if (!first || !second) + return first && !second; + +#ifdef CONFIG_LITMUS_LOCKING + + /* Check for inherited priorities. Change task + * used for comparison in such a case. + */ + if (unlikely(first->rt_param.inh_task)) + first_task = first->rt_param.inh_task; + if (unlikely(second->rt_param.inh_task)) + second_task = second->rt_param.inh_task; + + /* Check for priority boosting. Tie-break by start of boosting. + */ + if (unlikely(is_priority_boosted(first_task))) { + /* first_task is boosted, how about second_task? */ + if (!is_priority_boosted(second_task) || + lt_before(get_boost_start(first_task), + get_boost_start(second_task))) + return 1; + else + return 0; + } else if (unlikely(is_priority_boosted(second_task))) + /* second_task is boosted, first is not*/ + return 0; +#endif + + if (earlier_subjob_deadline(first_task, second_task)) { + return 1; + } + else if (get_subjob_deadline(first_task) == get_subjob_deadline(second_task)) { + /* use normal edf to tie-break */ + return edf_higher_prio(first, second); + } + return 0; /* fall-through. prio(second_task) > prio(first_task) */ +} + +int edf_split_ready_order(struct bheap_node* a, struct bheap_node* b) +{ + return edf_split_higher_prio(bheap2task(a), bheap2task(b)); +} + +void edf_split_domain_init(rt_domain_t* rt, check_resched_needed_t resched, + release_jobs_t release) +{ + rt_domain_init(rt, edf_split_ready_order, resched, release); +} + +/* need_to_preempt - check whether the task t needs to be preempted + * call only with irqs disabled and with ready_lock acquired + * THIS DOES NOT TAKE NON-PREEMPTIVE SECTIONS INTO ACCOUNT! + */ +int edf_split_preemption_needed(rt_domain_t* rt, struct task_struct *t) +{ + /* we need the read lock for edf_ready_queue */ + /* no need to preempt if there is nothing pending */ + if (!__jobs_pending(rt)) + return 0; + /* we need to reschedule if t doesn't exist */ + if (!t) + return 1; + + /* NOTE: We cannot check for non-preemptibility since we + * don't know what address space we're currently in. + */ + + /* make sure to get non-rt stuff out of the way */ + return !is_realtime(t) || edf_split_higher_prio(__next_ready(rt), t); +} diff --git a/litmus/sched_cfl_split.c b/litmus/sched_cfl_split.c new file mode 100644 index 000000000000..7d9302eb296b --- /dev/null +++ b/litmus/sched_cfl_split.c @@ -0,0 +1,1006 @@ +/* + * litmus/sched_cfl_split.c + * + * Implementation of a clustered version of the C-FL scheduling algorithm, + * with job splitting. + * + * This implementation is based on C-FL-split: + * - CPUs are clustered around L2 or L3 caches. + * - Clusters topology is automatically detected (this is arch dependent + * and is working only on x86 at the moment --- and only with modern + * cpus that exports cpuid4 information) + * - The plugins _does not_ attempt to put tasks in the right cluster i.e. + * the programmer needs to be aware of the topology to place tasks + * in the desired cluster + * - default clustering is around L2 cache (cache index = 2) + * supported clusters are: L1 (private cache: pedf), L2, L3, ALL (all + * online_cpus are placed in a single cluster). + * + * For details on functions, take a look at sched_gsn_edf.c + * + * Currently, we do not support changes in the number of online cpus. + * If the num_online_cpus() dynamically changes, the plugin is broken. + * + * This version uses the simple approach and serializes all scheduling + * decisions by the use of a queue lock. This is probably not the + * best way to do it, but it should suffice for now. + */ + +#include +#include +#include +#include + +#include + +#include +#include +#include +#include +#include +#include +#include + +#include + +#include + +#ifdef CONFIG_SCHED_CPU_AFFINITY +#include +#endif + +/* to configure the cluster size */ +#include +#include + +/* Reference configuration variable. Determines which cache level is used to + * group CPUs into clusters. GLOBAL_CLUSTER, which is the default, means that + * all CPUs form a single cluster (just like G-FL). + */ +static enum cache_level cluster_config = GLOBAL_CLUSTER; + +struct clusterdomain; + +/* cpu_entry_t - maintain the linked and scheduled state + * + * A cpu also contains a pointer to the cflsplit_domain_t cluster + * that owns it (struct clusterdomain*) + */ +typedef struct { + int cpu; + struct clusterdomain* cluster; /* owning cluster */ + struct task_struct* linked; /* only RT tasks */ + struct task_struct* scheduled; /* only RT tasks */ + atomic_t will_schedule; /* prevent unneeded IPIs */ + struct bheap_node* hn; + struct hrtimer split_timer; + int timer_armed; +} cpu_entry_t; + +/* one cpu_entry_t per CPU */ +DEFINE_PER_CPU(cpu_entry_t, cflsplit_cpu_entries); + +#define set_will_schedule() \ + (atomic_set(&__get_cpu_var(cflsplit_cpu_entries).will_schedule, 1)) +#define clear_will_schedule() \ + (atomic_set(&__get_cpu_var(cflsplit_cpu_entries).will_schedule, 0)) +#define test_will_schedule(cpu) \ + (atomic_read(&per_cpu(cflsplit_cpu_entries, cpu).will_schedule)) + +/* + * In C-FL-split there is a cflsplit domain _per_ cluster + * The number of clusters is dynamically determined accordingly to the + * total cpu number and the cluster size + */ +typedef struct clusterdomain { + /* rt_domain for this cluster */ + rt_domain_t domain; + /* cpus in this cluster */ + cpu_entry_t* *cpus; + /* map of this cluster cpus */ + cpumask_var_t cpu_map; + /* the cpus queue themselves according to priority in here */ + struct bheap_node *heap_node; + struct bheap cpu_heap; + /* lock for this cluster */ +#define cluster_lock domain.ready_lock +} cflsplit_domain_t; + +/* a cflsplit_domain per cluster; allocation is done at init/activation time */ +cflsplit_domain_t *cflsplit; + +#define remote_cluster(cpu) ((cflsplit_domain_t *) per_cpu(cflsplit_cpu_entries, cpu).cluster) +#define task_cpu_cluster(task) remote_cluster(get_partition(task)) + +/* Uncomment WANT_ALL_SCHED_EVENTS if you want to see all scheduling + * decisions in the TRACE() log; uncomment VERBOSE_INIT for verbose + * information during the initialization of the plugin (e.g., topology) +#define WANT_ALL_SCHED_EVENTS + */ +#define VERBOSE_INIT + +inline static int get_slice_num(struct task_struct* t) +{ + int basic = ((t->rt_param.job_params.exec_time * + t->rt_param.task_params.split) / + t->rt_param.task_params.exec_cost) + 1; + if (basic <= t->rt_param.task_params.split){ + return basic; + } + else{ + /*Since we don't police budget, just leave where it's at.*/ + return t->rt_param.task_params.split; + } +} + +/* Returns the appropriate subjob deadline.*/ +inline static lt_t get_proper_deadline(struct task_struct* t) +{ + unsigned int num_cpus = num_online_cpus(); + return t->rt_param.job_params.release + + ((t->rt_param.task_params.period * get_slice_num(t)) + / t->rt_param.task_params.split) + /* G-FL correction */ + - (((num_cpus - 1) * t->rt_param.task_params.exec_cost) + / (num_cpus * t->rt_param.task_params.split)); +} + +/* Tells us if the current deadline is too small.*/ +inline static int needs_deadline_move(struct task_struct* t) +{ + BUG_ON(get_proper_deadline(t) < t->rt_param.job_params.subjob_deadline); + return get_proper_deadline(t) != tsk_rt(t)->job_params.subjob_deadline; +} + +/*Returns execution time until the next deadline move. + * 0 means the task has no more deadline moves + */ +inline static lt_t time_to_next_move(struct task_struct* t) +{ + if (get_slice_num(t) == t->rt_param.task_params.split){ + return 0; + } + /* +1 upper bounds ceiling, since integer division is floor*/ + return ((get_slice_num(t) * t->rt_param.task_params.exec_cost) + / t->rt_param.task_params.split) + 1 + - t->rt_param.job_params.exec_time; +} + +/* Timer stuff - similar to budget.c. */ +static enum hrtimer_restart on_split_timeout(struct hrtimer *timer) +{ + cpu_entry_t* st = container_of(timer, + cpu_entry_t, + split_timer); + + unsigned long flags; + + local_irq_save(flags); + TRACE("split timer fired: %llu\n", litmus_clock()); + st->timer_armed = 0; + /* Activate scheduler */ + litmus_reschedule_local(); + local_irq_restore(flags); + + return HRTIMER_NORESTART; +} + +static void cancel_split_timer(cpu_entry_t* ce) +{ + int ret; + + TRACE("cancelling split time.\n"); + + /* Since interrupts are disabled and et->timer_armed is only + * modified locally, we do not need any locks. + */ + + if (ce->timer_armed) { + ret = hrtimer_try_to_cancel(&ce->split_timer); + /* Should never be inactive. */ + BUG_ON(ret == 0); + /* Should never be running concurrently.*/ + BUG_ON(ret == -1); + + ce->timer_armed = 0; + } +} + +/* assumes called with IRQs off */ +static void arm_split_timer(cpu_entry_t *ce, + struct task_struct* t) +{ + lt_t when_to_fire; + lt_t time_to_move; + lt_t now = litmus_clock(); + + /* __hrtimer_start_range_ns() cancels the timer + * anyway, so we don't have to check whether it is still armed */ + + /*We won't do any new deadline moves if the budget has been exhausted*/ + if (likely(!is_np(t) && (time_to_move = time_to_next_move(t)))) { + when_to_fire = now + time_to_move; + TRACE_TASK(t, "actually arming for %llu into the future\n", + time_to_move); + __hrtimer_start_range_ns(&ce->split_timer, + ns_to_ktime(when_to_fire), + 0 /* delta */, + HRTIMER_MODE_ABS_PINNED, + 0 /* no wakeup */); + ce->timer_armed = 1; + } +} + +static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b) +{ + cpu_entry_t *a, *b; + a = _a->value; + b = _b->value; + /* Note that a and b are inverted: we want the lowest-priority CPU at + * the top of the heap. + */ + return edf_split_higher_prio(b->linked, a->linked); +} + +/* update_cpu_position - Move the cpu entry to the correct place to maintain + * order in the cpu queue. Caller must hold cflsplit lock. + */ +static void update_cpu_position(cpu_entry_t *entry) +{ + cflsplit_domain_t *cluster = entry->cluster; + + if (likely(bheap_node_in_heap(entry->hn))) + bheap_delete(cpu_lower_prio, + &cluster->cpu_heap, + entry->hn); + + bheap_insert(cpu_lower_prio, &cluster->cpu_heap, entry->hn); +} + +/* caller must hold cflsplit lock */ +static cpu_entry_t* lowest_prio_cpu(cflsplit_domain_t *cluster) +{ + struct bheap_node* hn; + hn = bheap_peek(cpu_lower_prio, &cluster->cpu_heap); + return hn->value; +} + + +/* link_task_to_cpu - Update the link of a CPU. + * Handles the case where the to-be-linked task is already + * scheduled on a different CPU. + */ +static noinline void link_task_to_cpu(struct task_struct* linked, + cpu_entry_t *entry) +{ + cpu_entry_t *sched; + struct task_struct* tmp; + int on_cpu; + + BUG_ON(linked && !is_realtime(linked)); + + /* Currently linked task is set to be unlinked. */ + if (entry->linked) { + entry->linked->rt_param.linked_on = NO_CPU; + } + + /* Link new task to CPU. */ + if (linked) { + /* handle task is already scheduled somewhere! */ + on_cpu = linked->rt_param.scheduled_on; + if (on_cpu != NO_CPU) { + sched = &per_cpu(cflsplit_cpu_entries, on_cpu); + /* this should only happen if not linked already */ + BUG_ON(sched->linked == linked); + + /* If we are already scheduled on the CPU to which we + * wanted to link, we don't need to do the swap -- + * we just link ourselves to the CPU and depend on + * the caller to get things right. + */ + if (entry != sched) { + TRACE_TASK(linked, + "already scheduled on %d, updating link.\n", + sched->cpu); + tmp = sched->linked; + linked->rt_param.linked_on = sched->cpu; + sched->linked = linked; + update_cpu_position(sched); + linked = tmp; + } + } + if (linked) /* might be NULL due to swap */ + linked->rt_param.linked_on = entry->cpu; + } + entry->linked = linked; +#ifdef WANT_ALL_SCHED_EVENTS + if (linked) + TRACE_TASK(linked, "linked to %d.\n", entry->cpu); + else + TRACE("NULL linked to %d.\n", entry->cpu); +#endif + update_cpu_position(entry); +} + +/* unlink - Make sure a task is not linked any longer to an entry + * where it was linked before. Must hold cflsplit_lock. + */ +static noinline void unlink(struct task_struct* t) +{ + cpu_entry_t *entry; + + if (t->rt_param.linked_on != NO_CPU) { + /* unlink */ + entry = &per_cpu(cflsplit_cpu_entries, t->rt_param.linked_on); + t->rt_param.linked_on = NO_CPU; + link_task_to_cpu(NULL, entry); + } else if (is_queued(t)) { + /* This is an interesting situation: t is scheduled, + * but was just recently unlinked. It cannot be + * linked anywhere else (because then it would have + * been relinked to this CPU), thus it must be in some + * queue. We must remove it from the list in this + * case. + * + * in C-FL-split case is should be somewhere in the queue for + * its domain, therefore and we can get the domain using + * task_cpu_cluster + */ + remove(&(task_cpu_cluster(t))->domain, t); + } +} + + +/* preempt - force a CPU to reschedule + */ +static void preempt(cpu_entry_t *entry) +{ + preempt_if_preemptable(entry->scheduled, entry->cpu); +} + +/* requeue - Put an unlinked task into gsn-edf domain. + * Caller must hold cflsplit_lock. + */ +static noinline void requeue(struct task_struct* task) +{ + cflsplit_domain_t *cluster = task_cpu_cluster(task); + BUG_ON(!task); + /* sanity check before insertion */ + BUG_ON(is_queued(task)); + + if (is_early_releasing(task) || is_released(task, litmus_clock())) + __add_ready(&cluster->domain, task); + else { + /* it has got to wait */ + add_release(&cluster->domain, task); + } +} + +#ifdef CONFIG_SCHED_CPU_AFFINITY +static cpu_entry_t* cflsplit_get_nearest_available_cpu( + cflsplit_domain_t *cluster, cpu_entry_t *start) +{ + cpu_entry_t *affinity; + + get_nearest_available_cpu(affinity, start, cflsplit_cpu_entries, +#ifdef CONFIG_RELEASE_MASTER + cluster->domain.release_master +#else + NO_CPU +#endif + ); + + /* make sure CPU is in our cluster */ + if (affinity && cpu_isset(affinity->cpu, *cluster->cpu_map)) + return(affinity); + else + return(NULL); +} +#endif + + +/* check for any necessary preemptions */ +static void check_for_preemptions(cflsplit_domain_t *cluster) +{ + struct task_struct *task; + cpu_entry_t *last; + + for(last = lowest_prio_cpu(cluster); + edf_split_preemption_needed(&cluster->domain, last->linked); + last = lowest_prio_cpu(cluster)) { + /* preemption necessary */ + task = __take_ready(&cluster->domain); + TRACE("check_for_preemptions: attempting to link task %d to %d\n", + task->pid, last->cpu); +#ifdef CONFIG_SCHED_CPU_AFFINITY + { + cpu_entry_t *affinity = + cflsplit_get_nearest_available_cpu(cluster, + &per_cpu(cflsplit_cpu_entries, task_cpu(task))); + if(affinity) + last = affinity; + else if(requeue_preempted_job(last->linked)) + requeue(last->linked); + } +#else + if (requeue_preempted_job(last->linked)) + requeue(last->linked); +#endif + link_task_to_cpu(task, last); + preempt(last); + } +} + +/* cflsplit_job_arrival: task is either resumed or released */ +static noinline void cflsplit_job_arrival(struct task_struct* task) +{ + cflsplit_domain_t *cluster = task_cpu_cluster(task); + BUG_ON(!task); + + requeue(task); + check_for_preemptions(cluster); +} + +static void cflsplit_release_jobs(rt_domain_t* rt, struct bheap* tasks) +{ + cflsplit_domain_t* cluster = container_of(rt, cflsplit_domain_t, domain); + unsigned long flags; + + raw_spin_lock_irqsave(&cluster->cluster_lock, flags); + + __merge_ready(&cluster->domain, tasks); + check_for_preemptions(cluster); + + raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags); +} + +/* caller holds cflsplit_lock */ +static noinline void job_completion(struct task_struct *t, int forced) +{ + BUG_ON(!t); + + sched_trace_task_completion(t, forced); + + TRACE_TASK(t, "job_completion().\n"); + + /* set flags */ + tsk_rt(t)->completed = 0; + /* prepare for next period */ + prepare_for_next_period(t); + /* We now also set the subjob deadline to what it should be for + * scheduling priority. + */ + t->rt_param.job_params.subjob_deadline = get_proper_deadline(t); + if (is_early_releasing(t) || is_released(t, litmus_clock())) + sched_trace_task_release(t); + /* unlink */ + unlink(t); + /* requeue + * But don't requeue a blocking task. */ + if (is_running(t)) + cflsplit_job_arrival(t); +} + +static void move_deadline(struct task_struct *t) +{ + tsk_rt(t)->job_params.subjob_deadline = get_proper_deadline(t); + /* Check if rescheduling needed with lower priority. */ + unlink(t); + cflsplit_job_arrival(t); +} + +/* cflsplit_tick - this function is called for every local timer + * interrupt. + * + * checks whether the current task has expired and checks + * whether we need to preempt it if it has not expired + */ +static void cflsplit_tick(struct task_struct* t) +{ + if (is_realtime(t) && budget_enforced(t) && budget_exhausted(t)) { + if (!is_np(t)) { + /* np tasks will be preempted when they become + * preemptable again + */ + litmus_reschedule_local(); + set_will_schedule(); + TRACE("cflsplit_scheduler_tick: " + "%d is preemptable " + " => FORCE_RESCHED\n", t->pid); + } else if (is_user_np(t)) { + TRACE("cflsplit_scheduler_tick: " + "%d is non-preemptable, " + "preemption delayed.\n", t->pid); + request_exit_np(t); + } + } +} + +/* Getting schedule() right is a bit tricky. schedule() may not make any + * assumptions on the state of the current task since it may be called for a + * number of reasons. The reasons include a scheduler_tick() determined that it + * was necessary, because sys_exit_np() was called, because some Linux + * subsystem determined so, or even (in the worst case) because there is a bug + * hidden somewhere. Thus, we must take extreme care to determine what the + * current state is. + * + * The CPU could currently be scheduling a task (or not), be linked (or not). + * + * The following assertions for the scheduled task could hold: + * + * - !is_running(scheduled) // the job blocks + * - scheduled->timeslice == 0 // the job completed (forcefully) + * - is_completed() // the job completed (by syscall) + * - linked != scheduled // we need to reschedule (for any reason) + * - is_np(scheduled) // rescheduling must be delayed, + * sys_exit_np must be requested + * + * Any of these can occur together. + */ +static struct task_struct* cflsplit_schedule(struct task_struct * prev) +{ + cpu_entry_t* entry = &__get_cpu_var(cflsplit_cpu_entries); + cflsplit_domain_t *cluster = entry->cluster; + int out_of_time, sleep, preempt, np, exists, blocks, needs_move; + struct task_struct* next = NULL; + +#ifdef CONFIG_RELEASE_MASTER + /* Bail out early if we are the release master. + * The release master never schedules any real-time tasks. + */ + if (unlikely(cluster->domain.release_master == entry->cpu)) { + sched_state_task_picked(); + return NULL; + } +#endif + + raw_spin_lock(&cluster->cluster_lock); + clear_will_schedule(); + + /* sanity checking */ + BUG_ON(entry->scheduled && entry->scheduled != prev); + BUG_ON(entry->scheduled && !is_realtime(prev)); + BUG_ON(is_realtime(prev) && !entry->scheduled); + + /* (0) Determine state */ + exists = entry->scheduled != NULL; + blocks = exists && !is_running(entry->scheduled); + out_of_time = exists && + budget_enforced(entry->scheduled) && + budget_exhausted(entry->scheduled); + needs_move = exists && needs_deadline_move(entry->scheduled); + np = exists && is_np(entry->scheduled); + sleep = exists && is_completed(entry->scheduled); + preempt = entry->scheduled != entry->linked; + +#ifdef WANT_ALL_SCHED_EVENTS + TRACE_TASK(prev, "invoked cflsplit_schedule.\n"); +#endif + + if (exists) + TRACE_TASK(prev, + "blocks:%d out_of_time:%d needs_move: %d np:%d" + " sleep:%d preempt:%d state:%d sig:%d\n", + blocks, out_of_time, needs_move, np, sleep, preempt, + prev->state, signal_pending(prev)); + if (entry->linked && preempt) + TRACE_TASK(prev, "will be preempted by %s/%d\n", + entry->linked->comm, entry->linked->pid); + + + /* If a task blocks we have no choice but to reschedule. + */ + if (blocks) + unlink(entry->scheduled); + + /* Request a sys_exit_np() call if we would like to preempt but cannot. + * We need to make sure to update the link structure anyway in case + * that we are still linked. Multiple calls to request_exit_np() don't + * hurt. + * + * Job deadline moves handled similarly + */ + if (np && (out_of_time || preempt || sleep)) { + unlink(entry->scheduled); + request_exit_np(entry->scheduled); + } + else if (np && needs_move) { + request_exit_np(entry->scheduled); + } + + /* Any task that is preemptable and either exhausts its execution + * budget or wants to sleep completes. We may have to reschedule after + * this. Don't do a job completion if we block (can't have timers running + * for blocked jobs). Preemption go first for the same reason. + */ + if (!np && (out_of_time || sleep) && !blocks) + job_completion(entry->scheduled, !sleep); + else if (!np && needs_move && !blocks) { + move_deadline(entry->scheduled); + } + + /* Link pending task if we became unlinked. + */ + if (!entry->linked) + link_task_to_cpu(__take_ready(&cluster->domain), entry); + + /* The final scheduling decision. Do we need to switch for some reason? + * If linked is different from scheduled, then select linked as next. + */ + if ((!np || blocks) && + entry->linked != entry->scheduled) { + /* Schedule a linked job? */ + if (entry->linked) { + entry->linked->rt_param.scheduled_on = entry->cpu; + next = entry->linked; + } + if (entry->scheduled) { + /* not gonna be scheduled soon */ + entry->scheduled->rt_param.scheduled_on = NO_CPU; + TRACE_TASK(entry->scheduled, "scheduled_on = NO_CPU\n"); + } + } else + /* Only override Linux scheduler if we have a real-time task + * scheduled that needs to continue. + */ + if (exists) + next = prev; + + sched_state_task_picked(); + raw_spin_unlock(&cluster->cluster_lock); + + if (next) { + arm_split_timer(entry, next); + } + else if (entry->timer_armed) { + cancel_split_timer(entry); + } + +#ifdef WANT_ALL_SCHED_EVENTS + TRACE("cflsplit_lock released, next=0x%p\n", next); + + if (next) + TRACE_TASK(next, "scheduled at %llu\n", litmus_clock()); + else if (exists && !next) + TRACE("becomes idle at %llu.\n", litmus_clock()); +#endif + + + return next; +} + + +/* _finish_switch - we just finished the switch away from prev + */ +static void cflsplit_finish_switch(struct task_struct *prev) +{ + cpu_entry_t* entry = &__get_cpu_var(cflsplit_cpu_entries); + + entry->scheduled = is_realtime(current) ? current : NULL; +#ifdef WANT_ALL_SCHED_EVENTS + TRACE_TASK(prev, "switched away from\n"); +#endif +} + + +static void cflsplit_release_at(struct task_struct *t, lt_t start) +{ + release_at(t, start); + t->rt_param.job_params.subjob_deadline = get_proper_deadline(t); +} + + +/* Prepare a task for running in RT mode + */ +static void cflsplit_task_new(struct task_struct * t, int on_rq, int is_scheduled) +{ + unsigned long flags; + cpu_entry_t* entry; + cflsplit_domain_t* cluster; + + TRACE("gsn edf: task new %d\n", t->pid); + + /* the cluster doesn't change even if t is scheduled */ + cluster = task_cpu_cluster(t); + + raw_spin_lock_irqsave(&cluster->cluster_lock, flags); + + /* setup job params */ + cflsplit_release_at(t, litmus_clock()); + + if (is_scheduled) { + entry = &per_cpu(cflsplit_cpu_entries, task_cpu(t)); + BUG_ON(entry->scheduled); + +#ifdef CONFIG_RELEASE_MASTER + if (entry->cpu != cluster->domain.release_master) { +#endif + entry->scheduled = t; + tsk_rt(t)->scheduled_on = task_cpu(t); +#ifdef CONFIG_RELEASE_MASTER + } else { + /* do not schedule on release master */ + preempt(entry); /* force resched */ + tsk_rt(t)->scheduled_on = NO_CPU; + } +#endif + } else { + t->rt_param.scheduled_on = NO_CPU; + } + t->rt_param.linked_on = NO_CPU; + + if (is_running(t)) + cflsplit_job_arrival(t); + raw_spin_unlock_irqrestore(&(cluster->cluster_lock), flags); +} + +static void cflsplit_task_wake_up(struct task_struct *task) +{ + unsigned long flags; + lt_t now; + cflsplit_domain_t *cluster; + + TRACE_TASK(task, "wake_up at %llu\n", litmus_clock()); + + cluster = task_cpu_cluster(task); + + raw_spin_lock_irqsave(&cluster->cluster_lock, flags); + now = litmus_clock(); + if (is_sporadic(task) && is_tardy(task, now)) { + /* new sporadic release */ + cflsplit_release_at(task, now); + sched_trace_task_release(task); + } + cflsplit_job_arrival(task); + raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags); +} + +static void cflsplit_task_block(struct task_struct *t) +{ + unsigned long flags; + cflsplit_domain_t *cluster; + + TRACE_TASK(t, "block at %llu\n", litmus_clock()); + + cluster = task_cpu_cluster(t); + + /* unlink if necessary */ + raw_spin_lock_irqsave(&cluster->cluster_lock, flags); + unlink(t); + raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags); + + BUG_ON(!is_realtime(t)); +} + + +static void cflsplit_task_exit(struct task_struct * t) +{ + unsigned long flags; + cflsplit_domain_t *cluster = task_cpu_cluster(t); + + /* unlink if necessary */ + raw_spin_lock_irqsave(&cluster->cluster_lock, flags); + unlink(t); + if (tsk_rt(t)->scheduled_on != NO_CPU) { + cpu_entry_t *cpu; + cpu = &per_cpu(cflsplit_cpu_entries, tsk_rt(t)->scheduled_on); + cpu->scheduled = NULL; + tsk_rt(t)->scheduled_on = NO_CPU; + } + raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags); + + BUG_ON(!is_realtime(t)); + TRACE_TASK(t, "RIP\n"); +} + +static long cflsplit_admit_task(struct task_struct* tsk) +{ + return (remote_cluster(task_cpu(tsk)) == task_cpu_cluster(tsk)) ? + 0 : -EINVAL; +} + +/* total number of cluster */ +static int num_clusters; +/* we do not support cluster of different sizes */ +static unsigned int cluster_size; + +#ifdef VERBOSE_INIT +static void print_cluster_topology(cpumask_var_t mask, int cpu) +{ + int chk; + char buf[255]; + + chk = cpulist_scnprintf(buf, 254, mask); + buf[chk] = '\0'; + printk(KERN_INFO "CPU = %d, shared cpu(s) = %s\n", cpu, buf); + +} +#endif + +static int clusters_allocated = 0; + +static void cleanup_cflsplit(void) +{ + int i; + + if (clusters_allocated) { + for (i = 0; i < num_clusters; i++) { + kfree(cflsplit[i].cpus); + kfree(cflsplit[i].heap_node); + free_cpumask_var(cflsplit[i].cpu_map); + } + + kfree(cflsplit); + } +} + +static long cflsplit_activate_plugin(void) +{ + int i, j, cpu, ccpu, cpu_count; + cpu_entry_t *entry; + + cpumask_var_t mask; + int chk = 0; + + /* de-allocate old clusters, if any */ + cleanup_cflsplit(); + + printk(KERN_INFO "C-FL-split: Activate Plugin, cluster configuration = %d\n", + cluster_config); + + /* need to get cluster_size first */ + if(!zalloc_cpumask_var(&mask, GFP_ATOMIC)) + return -ENOMEM; + + if (unlikely(cluster_config == GLOBAL_CLUSTER)) { + cluster_size = num_online_cpus(); + } else { + chk = get_shared_cpu_map(mask, 0, cluster_config); + if (chk) { + /* if chk != 0 then it is the max allowed index */ + printk(KERN_INFO "C-FL-split: Cluster configuration = %d " + "is not supported on this hardware.\n", + cluster_config); + /* User should notice that the configuration failed, so + * let's bail out. */ + return -EINVAL; + } + + cluster_size = cpumask_weight(mask); + } + + if ((num_online_cpus() % cluster_size) != 0) { + /* this can't be right, some cpus are left out */ + printk(KERN_ERR "C-FL-split: Trying to group %d cpus in %d!\n", + num_online_cpus(), cluster_size); + return -1; + } + + num_clusters = num_online_cpus() / cluster_size; + printk(KERN_INFO "C-FL-split: %d cluster(s) of size = %d\n", + num_clusters, cluster_size); + + /* initialize clusters */ + cflsplit = kmalloc(num_clusters * sizeof(cflsplit_domain_t), GFP_ATOMIC); + for (i = 0; i < num_clusters; i++) { + + cflsplit[i].cpus = kmalloc(cluster_size * sizeof(cpu_entry_t), + GFP_ATOMIC); + cflsplit[i].heap_node = kmalloc( + cluster_size * sizeof(struct bheap_node), + GFP_ATOMIC); + bheap_init(&(cflsplit[i].cpu_heap)); + edf_split_domain_init(&(cflsplit[i].domain), NULL, + cflsplit_release_jobs); + + if(!zalloc_cpumask_var(&cflsplit[i].cpu_map, GFP_ATOMIC)) + return -ENOMEM; +#ifdef CONFIG_RELEASE_MASTER + cflsplit[i].domain.release_master = atomic_read(&release_master_cpu); +#endif + } + + /* cycle through cluster and add cpus to them */ + for (i = 0; i < num_clusters; i++) { + + for_each_online_cpu(cpu) { + /* check if the cpu is already in a cluster */ + for (j = 0; j < num_clusters; j++) + if (cpumask_test_cpu(cpu, cflsplit[j].cpu_map)) + break; + /* if it is in a cluster go to next cpu */ + if (j < num_clusters && + cpumask_test_cpu(cpu, cflsplit[j].cpu_map)) + continue; + + /* this cpu isn't in any cluster */ + /* get the shared cpus */ + if (unlikely(cluster_config == GLOBAL_CLUSTER)) + cpumask_copy(mask, cpu_online_mask); + else + get_shared_cpu_map(mask, cpu, cluster_config); + + cpumask_copy(cflsplit[i].cpu_map, mask); +#ifdef VERBOSE_INIT + print_cluster_topology(mask, cpu); +#endif + /* add cpus to current cluster and init cpu_entry_t */ + cpu_count = 0; + for_each_cpu(ccpu, cflsplit[i].cpu_map) { + + entry = &per_cpu(cflsplit_cpu_entries, ccpu); + cflsplit[i].cpus[cpu_count] = entry; + atomic_set(&entry->will_schedule, 0); + entry->cpu = ccpu; + entry->cluster = &cflsplit[i]; + entry->hn = &(cflsplit[i].heap_node[cpu_count]); + hrtimer_init(&entry->split_timer, + CLOCK_MONOTONIC, + HRTIMER_MODE_ABS); + entry->split_timer.function = on_split_timeout; + bheap_node_init(&entry->hn, entry); + + cpu_count++; + + entry->linked = NULL; + entry->scheduled = NULL; +#ifdef CONFIG_RELEASE_MASTER + /* only add CPUs that should schedule jobs */ + if (entry->cpu != entry->cluster->domain.release_master) +#endif + update_cpu_position(entry); + } + /* done with this cluster */ + break; + } + } + + free_cpumask_var(mask); + clusters_allocated = 1; + return 0; +} + +/* Plugin object */ +static struct sched_plugin cflsplit_plugin __cacheline_aligned_in_smp = { + .plugin_name = "C-FL-split", + .finish_switch = cflsplit_finish_switch, + .tick = cflsplit_tick, + .task_new = cflsplit_task_new, + .complete_job = complete_job, + .task_exit = cflsplit_task_exit, + .schedule = cflsplit_schedule, + .release_at = cflsplit_release_at, + .task_wake_up = cflsplit_task_wake_up, + .task_block = cflsplit_task_block, + .admit_task = cflsplit_admit_task, + .activate_plugin = cflsplit_activate_plugin, +}; + +static struct proc_dir_entry *cluster_file = NULL, *cflsplit_dir = NULL; + +static int __init init_cflsplit(void) +{ + int err, fs; + + err = register_sched_plugin(&cflsplit_plugin); + if (!err) { + fs = make_plugin_proc_dir(&cflsplit_plugin, &cflsplit_dir); + if (!fs) + cluster_file = create_cluster_file(cflsplit_dir, &cluster_config); + else + printk(KERN_ERR "Could not allocate C-FL-split procfs dir.\n"); + } + return err; +} + +static void clean_cflsplit(void) +{ + cleanup_cflsplit(); + if (cluster_file) + remove_proc_entry("cluster", cflsplit_dir); + if (cflsplit_dir) + remove_plugin_proc_dir(&cflsplit_plugin); +} + +module_init(init_cflsplit); +module_exit(clean_cflsplit); -- cgit v1.2.2 From efe3e4c46fe86c815ada23a4cfbc89b6e55e14f1 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 6 Dec 2013 13:20:27 -0500 Subject: Add PGM support to C-FL This patch applies the same PGM changes made to C-EDF to C-FL. --- litmus/sched_cedf.c | 3 ++- litmus/sched_cfl_split.c | 54 +++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 55 insertions(+), 2 deletions(-) diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c index 8699f6d9d5b6..a25f2a474263 100644 --- a/litmus/sched_cedf.c +++ b/litmus/sched_cedf.c @@ -566,12 +566,13 @@ static struct task_struct* cedf_schedule(struct task_struct * prev) entry->scheduled->rt_param.scheduled_on = NO_CPU; TRACE_TASK(entry->scheduled, "scheduled_on = NO_CPU\n"); } - } else + } else { /* Only override Linux scheduler if we have a real-time task * scheduled that needs to continue. */ if (exists) next = prev; + } sched_state_task_picked(); raw_spin_unlock(&cluster->cluster_lock); diff --git a/litmus/sched_cfl_split.c b/litmus/sched_cfl_split.c index 7d9302eb296b..af2b28230c72 100644 --- a/litmus/sched_cfl_split.c +++ b/litmus/sched_cfl_split.c @@ -49,6 +49,10 @@ #include #endif +#ifdef CONFIG_SCHED_PGM +#include +#endif + /* to configure the cluster size */ #include #include @@ -587,6 +591,49 @@ static struct task_struct* cflsplit_schedule(struct task_struct * prev) TRACE_TASK(prev, "will be preempted by %s/%d\n", entry->linked->comm, entry->linked->pid); +#ifdef CONFIG_SCHED_PGM + if (exists) { + if (is_pgm_sending(entry->scheduled)) { + if (!is_pgm_satisfied(entry->scheduled)) { + if (!is_priority_boosted(entry->scheduled)) { + TRACE_TASK(entry->scheduled, "is sending PGM tokens and needs boosting.\n"); + BUG_ON(is_pgm_satisfied(entry->scheduled)); + + /* We are either sending tokens or waiting for tokes. + If waiting: Boost priority so we'll be scheduled + immediately when needed tokens arrive. + If sending: Boost priority so no one (specifically, our + consumers) will preempt us while signalling the token + transmission. + */ + tsk_rt(entry->scheduled)->priority_boosted = 1; + tsk_rt(entry->scheduled)->boost_start_time = litmus_clock(); + + if (likely(!blocks)) { + unlink(entry->scheduled); + cflsplit_job_arrival(entry->scheduled); + } + } + } + else { /* sending is satisfied */ + tsk_rt(entry->scheduled)->ctrl_page->pgm_sending = 0; + tsk_rt(entry->scheduled)->ctrl_page->pgm_satisfied = 0; + + if (is_priority_boosted(entry->scheduled)) { + TRACE_TASK(entry->scheduled, + "is done sending PGM tokens must relinquish boosting.\n"); + /* clear boosting */ + tsk_rt(entry->scheduled)->priority_boosted = 0; + if(likely(!blocks)) { + /* recheck priority */ + unlink(entry->scheduled); + cflsplit_job_arrival(entry->scheduled); + } + } + } + } + } +#endif /* If a task blocks we have no choice but to reschedule. */ @@ -639,12 +686,13 @@ static struct task_struct* cflsplit_schedule(struct task_struct * prev) entry->scheduled->rt_param.scheduled_on = NO_CPU; TRACE_TASK(entry->scheduled, "scheduled_on = NO_CPU\n"); } - } else + } else { /* Only override Linux scheduler if we have a real-time task * scheduled that needs to continue. */ if (exists) next = prev; + } sched_state_task_picked(); raw_spin_unlock(&cluster->cluster_lock); @@ -751,6 +799,10 @@ static void cflsplit_task_wake_up(struct task_struct *task) cflsplit_release_at(task, now); sched_trace_task_release(task); } + if (is_pgm_waiting(task)) { + /* shift out release/deadline, if needed */ + setup_pgm_release(task); + } cflsplit_job_arrival(task); raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags); } -- cgit v1.2.2 From 1a4b5f42a5121d960abe215b8f3b55a10614705a Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Thu, 2 Jan 2014 13:03:55 -0500 Subject: Verbose admission test for CFL-split --- litmus/sched_cfl_split.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) diff --git a/litmus/sched_cfl_split.c b/litmus/sched_cfl_split.c index af2b28230c72..ad398470a495 100644 --- a/litmus/sched_cfl_split.c +++ b/litmus/sched_cfl_split.c @@ -847,8 +847,14 @@ static void cflsplit_task_exit(struct task_struct * t) static long cflsplit_admit_task(struct task_struct* tsk) { - return (remote_cluster(task_cpu(tsk)) == task_cpu_cluster(tsk)) ? - 0 : -EINVAL; + if (remote_cluster(task_cpu(tsk)) != task_cpu_cluster(tsk)) { + unsigned int assigned_cpu = get_partition(tsk); + unsigned int cur_cpu = task_cpu(tsk); + TRACE_TASK(tsk, "cluster mismatch: assigned cpu %u but on cpu %u\n", + assigned_cpu, cur_cpu); + return -EINVAL; + } + return 0; } /* total number of cluster */ -- cgit v1.2.2 From 7e1db96d01247ca7a3b23ca8ac40fc195ef4a149 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Tue, 14 Jan 2014 16:51:23 -0500 Subject: sched_trace: Trace PGM node type parameters --- include/litmus/rt_param.h | 8 ++++++++ include/litmus/sched_trace.h | 24 +++++++++++++++++++++--- include/trace/events/litmus.h | 21 +++++++++++++++++++++ litmus/litmus.c | 22 ++++++++++++++++++---- litmus/sched_cfl_split.c | 6 ++++-- litmus/sched_task_trace.c | 15 +++++++++++++-- 6 files changed, 85 insertions(+), 11 deletions(-) diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h index 6160a1635227..0ddc1973b0aa 100644 --- a/include/litmus/rt_param.h +++ b/include/litmus/rt_param.h @@ -51,6 +51,13 @@ typedef enum { TASK_EARLY } release_policy_t; +typedef enum { + PGM_NOT_A_NODE, + PGM_SRC, + PGM_SINK, + PGM_INTERNAL +} pgm_node_type_t; + /* We use the common priority interpretation "lower index == higher priority", * which is commonly used in fixed-priority schedulability analysis papers. * So, a numerically lower priority value implies higher scheduling priority, @@ -82,6 +89,7 @@ struct rt_task { task_class_t cls; budget_policy_t budget_policy; /* ignored by pfair */ release_policy_t release_policy; + pgm_node_type_t pgm_type; }; union np_flag { diff --git a/include/litmus/sched_trace.h b/include/litmus/sched_trace.h index 3d3b06ced797..8e2aefecd1fe 100644 --- a/include/litmus/sched_trace.h +++ b/include/litmus/sched_trace.h @@ -80,6 +80,12 @@ struct st_sys_release_data { u64 release; }; +struct st_pgm_param_data { + u32 node_type; + u16 graph_pid; + u8 __unused[10]; +}; + struct st_pgm_release_data { u64 release; /* PGM-adjusted release time */ u64 deadline; /* PGM-adjusted deadline */ @@ -100,6 +106,7 @@ typedef enum { ST_RESUME, ST_ACTION, ST_SYS_RELEASE, + ST_PGM_PARAM, ST_PGM_RELEASE } st_event_record_type_t; @@ -119,6 +126,7 @@ struct st_event_record { DATA(resume); DATA(action); DATA(sys_release); + DATA(pgm_param); DATA(pgm_release); } data; }; @@ -161,6 +169,8 @@ feather_callback void do_sched_trace_action(unsigned long id, unsigned long action); feather_callback void do_sched_trace_sys_release(unsigned long id, lt_t* start); +feather_callback void do_sched_trace_pgm_param(unsigned long id, + struct task_struct* task); feather_callback void do_sched_trace_pgm_release(unsigned long id, struct task_struct* task); @@ -188,6 +198,7 @@ feather_callback void do_sched_trace_pgm_release(unsigned long id, #define trace_litmus_task_block(t) #define trace_litmus_task_resume(t) #define trace_litmus_sys_release(start) +#define trace_litmus_pgm_param(t) #define trace_litmus_pgm_release(t) #endif @@ -262,10 +273,17 @@ feather_callback void do_sched_trace_pgm_release(unsigned long id, trace_litmus_sys_release(when); \ } while (0) +#define sched_trace_pgm_param(t) \ + do { \ + SCHED_TRACE(SCHED_TRACE_BASE_ID + 11, \ + do_sched_trace_pgm_param, t); \ + trace_litmus_pgm_param(t); \ + } while (0) + #define sched_trace_pgm_release(t) \ - do { \ - SCHED_TRACE(SCHED_TRACE_BASE_ID + 11, \ - do_sched_trace_pgm_release, t); \ + do { \ + SCHED_TRACE(SCHED_TRACE_BASE_ID + 12, \ + do_sched_trace_pgm_release, t); \ trace_litmus_pgm_release(t); \ } while (0) diff --git a/include/trace/events/litmus.h b/include/trace/events/litmus.h index 0b4eac386dfe..0822328144bc 100644 --- a/include/trace/events/litmus.h +++ b/include/trace/events/litmus.h @@ -225,6 +225,27 @@ TRACE_EVENT(litmus_sys_release, TP_printk("SynRelease(%Lu) at %Lu\n", __entry->rel, __entry->when) ); +/* Tracing PGM node parameters */ +TRACE_EVENT(litmus_pgm_param, + + TP_PROTO(struct task_struct *t), + + TP_ARGS(t), + + TP_STRUCT__entry( + __field( pid_t, pid ) + __field( pgm_node_type_t, node_type ) + __field( pid_t, graph_pid ) + ), + + TP_fast_assign( + __entry->pid = t ? t->pid : 0; + __entry->node_type = t ? t->rt_params.task_params.pgm_type : PGM_NOT_A_NODE; + __entry->graph_pid = t ? t->tgid : 0; + ) + + TP_printk("pgm node (%u, node type = %d) in graph (%u)\n", + __entry->pid, __entry->node_type, __entry->graph_pid); /* * Tracing PGM-adjusted job release */ diff --git a/litmus/litmus.c b/litmus/litmus.c index ab0bcac13252..8937f5233b0e 100644 --- a/litmus/litmus.c +++ b/litmus/litmus.c @@ -107,12 +107,19 @@ asmlinkage long sys_set_rt_task_param(pid_t pid, struct rt_task __user * param) if (tp.relative_deadline == 0) tp.relative_deadline = tp.period; - if (tp.exec_cost <= 0) + if (tp.exec_cost <= 0) { + printk(KERN_INFO "litmus: real-time task %d rejected " + "because declared job execution time <= 0.", pid); goto out_unlock; - if (tp.period <= 0) + } + if (tp.period <= 0) { + printk(KERN_INFO "litmus: real-time task %d rejected " + "because declared job period <= 0.", pid); goto out_unlock; - if (!cpu_online(tp.cpu)) + } + if (!cpu_online(tp.cpu)) { goto out_unlock; + } if (min(tp.relative_deadline, tp.period) < tp.exec_cost) /*density check*/ { printk(KERN_INFO "litmus: real-time task %d rejected " @@ -331,9 +338,13 @@ long litmus_admit_task(struct task_struct* tsk) if (get_rt_relative_deadline(tsk) == 0 || get_exec_cost(tsk) > min(get_rt_relative_deadline(tsk), get_rt_period(tsk)) ) { + printk(KERN_INFO "litmus: invalid task parameters " + "(e = %llu, p = %llu, d = %llu)\n", + get_exec_cost(tsk), get_rt_period(tsk), + get_rt_relative_deadline(tsk)); TRACE_TASK(tsk, "litmus admit: invalid task parameters " - "(e = %lu, p = %lu, d = %lu)\n", + "(e = %llu, p = %llu, d = %llu)\n", get_exec_cost(tsk), get_rt_period(tsk), get_rt_relative_deadline(tsk)); retval = -EINVAL; @@ -341,6 +352,8 @@ long litmus_admit_task(struct task_struct* tsk) } if (!cpu_online(get_partition(tsk))) { + printk(KERN_INFO "litmus: cpu %d is not online\n", + get_partition(tsk)); TRACE_TASK(tsk, "litmus admit: cpu %d is not online\n", get_partition(tsk)); retval = -EINVAL; @@ -369,6 +382,7 @@ long litmus_admit_task(struct task_struct* tsk) if (!retval) { sched_trace_task_name(tsk); sched_trace_task_param(tsk); + sched_trace_pgm_param(tsk); atomic_inc(&rt_task_count); } diff --git a/litmus/sched_cfl_split.c b/litmus/sched_cfl_split.c index ad398470a495..b6dde71cdf84 100644 --- a/litmus/sched_cfl_split.c +++ b/litmus/sched_cfl_split.c @@ -850,8 +850,10 @@ static long cflsplit_admit_task(struct task_struct* tsk) if (remote_cluster(task_cpu(tsk)) != task_cpu_cluster(tsk)) { unsigned int assigned_cpu = get_partition(tsk); unsigned int cur_cpu = task_cpu(tsk); - TRACE_TASK(tsk, "cluster mismatch: assigned cpu %u but on cpu %u\n", - assigned_cpu, cur_cpu); + printk(KERN_INFO "cluster mismatch: %u assigned cpu %d but on cpu %d\n", + tsk->pid, assigned_cpu, cur_cpu); + TRACE_TASK(tsk, "cluster mismatch: assigned cpu %d but on cpu %d\n", + assigned_cpu, cur_cpu); return -EINVAL; } return 0; diff --git a/litmus/sched_task_trace.c b/litmus/sched_task_trace.c index 422314f29a60..b9e772c07652 100644 --- a/litmus/sched_task_trace.c +++ b/litmus/sched_task_trace.c @@ -238,13 +238,24 @@ feather_callback void do_sched_trace_action(unsigned long id, } } +feather_callback void do_sched_trace_pgm_param(unsigned long id, unsigned long _task) +{ + struct task_struct *t = (struct task_struct*) _task; + struct st_event_record* rec = get_record(ST_PGM_PARAM, t); + if (rec) { + rec->data.pgm_param.node_type = tsk_rt(t)->task_params.pgm_type; + rec->data.pgm_param.graph_pid = t->tgid; + put_record(rec); + } +} + feather_callback void do_sched_trace_pgm_release(unsigned long id, unsigned long _task) { struct task_struct *t = (struct task_struct*) _task; struct st_event_record* rec = get_record(ST_PGM_RELEASE, t); if (rec) { - rec->data.release.release = get_release(t); - rec->data.release.deadline = get_deadline(t); + rec->data.pgm_release.release = get_release(t); + rec->data.pgm_release.deadline = get_deadline(t); put_record(rec); } } -- cgit v1.2.2 From d7e35a002b94ad52304a4c400d8195e462e0308a Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 17 Jan 2014 00:21:41 -0500 Subject: Don't unlink np tasks that block preemptions. This patch prevents non-preemptive tasks from being unlinked up a blocked preemption. Apparently was leading to lost tasks (they would suspend and never be heard from again). --- litmus/sched_cfl_split.c | 45 +++++++++++++++++++++++++++++++++------------ 1 file changed, 33 insertions(+), 12 deletions(-) diff --git a/litmus/sched_cfl_split.c b/litmus/sched_cfl_split.c index b6dde71cdf84..6fd1591aec5a 100644 --- a/litmus/sched_cfl_split.c +++ b/litmus/sched_cfl_split.c @@ -394,11 +394,16 @@ static cpu_entry_t* cflsplit_get_nearest_available_cpu( #endif ); - /* make sure CPU is in our cluster */ - if (affinity && cpu_isset(affinity->cpu, *cluster->cpu_map)) - return(affinity); - else - return(NULL); + if (affinity) { + /* make sure CPU is in our cluster */ + if(cpu_isset(affinity->cpu, *cluster->cpu_map)) { + return(affinity); + } + else { + TRACE("CPU %d is not in our cluster.\n", affinity->cpu); + } + } + return(NULL); } #endif @@ -414,8 +419,8 @@ static void check_for_preemptions(cflsplit_domain_t *cluster) last = lowest_prio_cpu(cluster)) { /* preemption necessary */ task = __take_ready(&cluster->domain); - TRACE("check_for_preemptions: attempting to link task %d to %d\n", - task->pid, last->cpu); + TRACE("check_for_preemptions: attempting to link task %s/%d to %d\n", + task->comm, task->pid, last->cpu); #ifdef CONFIG_SCHED_CPU_AFFINITY { cpu_entry_t *affinity = @@ -584,9 +589,11 @@ static struct task_struct* cflsplit_schedule(struct task_struct * prev) if (exists) TRACE_TASK(prev, "blocks:%d out_of_time:%d needs_move: %d np:%d" - " sleep:%d preempt:%d state:%d sig:%d\n", + " sleep:%d preempt:%d state:%d sig:%d boosted:%d\n", blocks, out_of_time, needs_move, np, sleep, preempt, - prev->state, signal_pending(prev)); + prev->state, signal_pending(prev), + is_priority_boosted(entry->scheduled)); + if (entry->linked && preempt) TRACE_TASK(prev, "will be preempted by %s/%d\n", entry->linked->comm, entry->linked->pid); @@ -612,6 +619,13 @@ static struct task_struct* cflsplit_schedule(struct task_struct * prev) if (likely(!blocks)) { unlink(entry->scheduled); cflsplit_job_arrival(entry->scheduled); + /* we may regain the processor */ + if (preempt) { + preempt = entry->scheduled != entry->linked; + if (!preempt) { + TRACE_TASK(entry->scheduled, "blocked preemption by lazy boosting.\n"); + } + } } } } @@ -628,6 +642,13 @@ static struct task_struct* cflsplit_schedule(struct task_struct * prev) /* recheck priority */ unlink(entry->scheduled); cflsplit_job_arrival(entry->scheduled); + /* we may lose the processor */ + if (!preempt) { + preempt = entry->scheduled != entry->linked; + if (preempt) { + TRACE_TASK(entry->scheduled, "preempted by lazy unboosting.\n"); + } + } } } } @@ -647,11 +668,12 @@ static struct task_struct* cflsplit_schedule(struct task_struct * prev) * * Job deadline moves handled similarly */ - if (np && (out_of_time || preempt || sleep)) { +// if (np && (out_of_time || preempt || sleep)) { + if (np && (out_of_time || sleep)) { unlink(entry->scheduled); request_exit_np(entry->scheduled); } - else if (np && needs_move) { + else if (np && (needs_move || preempt)) { request_exit_np(entry->scheduled); } @@ -713,7 +735,6 @@ static struct task_struct* cflsplit_schedule(struct task_struct * prev) TRACE("becomes idle at %llu.\n", litmus_clock()); #endif - return next; } -- cgit v1.2.2 From 379f71386ac543baf10d352459405b2d42d7aa21 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 17 Jan 2014 15:53:44 -0500 Subject: Compilation Bug: Fix PGM trace macros. --- include/trace/events/litmus.h | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/include/trace/events/litmus.h b/include/trace/events/litmus.h index 0822328144bc..02b4b54f718c 100644 --- a/include/trace/events/litmus.h +++ b/include/trace/events/litmus.h @@ -39,7 +39,7 @@ TRACE_EVENT(litmus_task_param, __entry->partition = get_partition(t); ), - TP_printk("period(%d, %Lu).\nwcet(%d, %Lu).\n", + TP_printk("period(%u, %Lu).\nwcet(%d, %Lu).\n", __entry->pid, __entry->period, __entry->pid, __entry->wcet) ); @@ -240,12 +240,14 @@ TRACE_EVENT(litmus_pgm_param, TP_fast_assign( __entry->pid = t ? t->pid : 0; - __entry->node_type = t ? t->rt_params.task_params.pgm_type : PGM_NOT_A_NODE; + __entry->node_type = t ? t->rt_param.task_params.pgm_type : PGM_NOT_A_NODE; __entry->graph_pid = t ? t->tgid : 0; - ) + ), TP_printk("pgm node (%u, node type = %d) in graph (%u)\n", - __entry->pid, __entry->node_type, __entry->graph_pid); + __entry->pid, __entry->node_type, __entry->graph_pid) +); + /* * Tracing PGM-adjusted job release */ -- cgit v1.2.2 From e121b41ebcfa1ce83ab77fc93e7fdbb1f522437e Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 17 Jan 2014 15:55:38 -0500 Subject: Add combined PGM_SRC_SINK node type. --- include/litmus/rt_param.h | 1 + litmus/litmus.c | 6 ++++++ 2 files changed, 7 insertions(+) diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h index 0ddc1973b0aa..7b4045069b27 100644 --- a/include/litmus/rt_param.h +++ b/include/litmus/rt_param.h @@ -55,6 +55,7 @@ typedef enum { PGM_NOT_A_NODE, PGM_SRC, PGM_SINK, + PGM_SRC_SINK, PGM_INTERNAL } pgm_node_type_t; diff --git a/litmus/litmus.c b/litmus/litmus.c index 8937f5233b0e..76378ce34c2b 100644 --- a/litmus/litmus.c +++ b/litmus/litmus.c @@ -144,6 +144,12 @@ asmlinkage long sys_set_rt_task_param(pid_t pid, struct rt_task __user * param) pid, tp.budget_policy); goto out_unlock; } + if (tp.pgm_type < PGM_NOT_A_NODE || tp.pgm_type > PGM_INTERNAL) { + printk(KERN_INFO "litmus: real-time task %d rejected " + "because of unknown PGM node type specified (%d)\n", + pid, tp.pgm_type); + goto out_unlock; + } target->rt_param.task_params = tp; -- cgit v1.2.2 From 2b8387eb6535a1ebcfec9224fbf4f3837daf380d Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 17 Jan 2014 16:50:37 -0500 Subject: BUG: Trace IDs don't include ASSIGNED --- include/litmus/sched_trace.h | 24 +++++++++++++----------- 1 file changed, 13 insertions(+), 11 deletions(-) diff --git a/include/litmus/sched_trace.h b/include/litmus/sched_trace.h index 8e2aefecd1fe..c30a80a69333 100644 --- a/include/litmus/sched_trace.h +++ b/include/litmus/sched_trace.h @@ -225,23 +225,25 @@ feather_callback void do_sched_trace_pgm_release(unsigned long id, trace_litmus_task_release(t); \ } while (0) +/* place holder for sched_trace_task_assigned (+4) */ + #define sched_trace_task_switch_to(t) \ do { \ - SCHED_TRACE(SCHED_TRACE_BASE_ID + 4, \ + SCHED_TRACE(SCHED_TRACE_BASE_ID + 5, \ do_sched_trace_task_switch_to, t); \ trace_litmus_switch_to(t); \ } while (0) #define sched_trace_task_switch_away(t) \ do { \ - SCHED_TRACE(SCHED_TRACE_BASE_ID + 5, \ + SCHED_TRACE(SCHED_TRACE_BASE_ID + 6, \ do_sched_trace_task_switch_away, t); \ trace_litmus_switch_away(t); \ } while (0) #define sched_trace_task_completion(t, forced) \ do { \ - SCHED_TRACE2(SCHED_TRACE_BASE_ID + 6, \ + SCHED_TRACE2(SCHED_TRACE_BASE_ID + 7, \ do_sched_trace_task_completion, t, \ (unsigned long) forced); \ trace_litmus_task_completion(t, forced); \ @@ -249,40 +251,40 @@ feather_callback void do_sched_trace_pgm_release(unsigned long id, #define sched_trace_task_block(t) \ do { \ - SCHED_TRACE(SCHED_TRACE_BASE_ID + 7, \ + SCHED_TRACE(SCHED_TRACE_BASE_ID + 8, \ do_sched_trace_task_block, t); \ trace_litmus_task_block(t); \ } while (0) #define sched_trace_task_resume(t) \ do { \ - SCHED_TRACE(SCHED_TRACE_BASE_ID + 8, \ + SCHED_TRACE(SCHED_TRACE_BASE_ID + 9, \ do_sched_trace_task_resume, t); \ trace_litmus_task_resume(t); \ } while (0) #define sched_trace_action(t, action) \ - SCHED_TRACE2(SCHED_TRACE_BASE_ID + 9, \ + SCHED_TRACE2(SCHED_TRACE_BASE_ID + 10, \ do_sched_trace_action, t, (unsigned long) action); /* when is a pointer, it does not need an explicit cast to unsigned long */ #define sched_trace_sys_release(when) \ do { \ - SCHED_TRACE(SCHED_TRACE_BASE_ID + 10, \ + SCHED_TRACE(SCHED_TRACE_BASE_ID + 11, \ do_sched_trace_sys_release, when); \ trace_litmus_sys_release(when); \ } while (0) #define sched_trace_pgm_param(t) \ - do { \ - SCHED_TRACE(SCHED_TRACE_BASE_ID + 11, \ + do { \ + SCHED_TRACE(SCHED_TRACE_BASE_ID + 12, \ do_sched_trace_pgm_param, t); \ trace_litmus_pgm_param(t); \ } while (0) #define sched_trace_pgm_release(t) \ - do { \ - SCHED_TRACE(SCHED_TRACE_BASE_ID + 12, \ + do { \ + SCHED_TRACE(SCHED_TRACE_BASE_ID + 13, \ do_sched_trace_pgm_release, t); \ trace_litmus_pgm_release(t); \ } while (0) -- cgit v1.2.2 From 69b90552b97be30edc7a984d6d1df8a62ca59b98 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Sat, 18 Jan 2014 09:45:28 -0500 Subject: Greatly increase limit on size of sched trace buf. --- litmus/Kconfig | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/litmus/Kconfig b/litmus/Kconfig index 49017b26d0d3..63d35db1cd72 100644 --- a/litmus/Kconfig +++ b/litmus/Kconfig @@ -244,7 +244,7 @@ config SCHED_TASK_TRACE config SCHED_TASK_TRACE_SHIFT int "Buffer size for sched_trace_xxx() events" depends on SCHED_TASK_TRACE - range 8 13 + range 8 28 default 9 help -- cgit v1.2.2 From 9fb66a63b473b338d89893f66aa89811de165469 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Wed, 29 Jan 2014 15:17:27 -0500 Subject: Kludge: Add graph e-to-e period in sched_trace Kludge the expected graph end-to-end response time into record data to make data analysis easier. --- include/litmus/rt_param.h | 1 + include/litmus/sched_trace.h | 3 ++- litmus/sched_task_trace.c | 1 + 3 files changed, 4 insertions(+), 1 deletion(-) diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h index 7b4045069b27..76bb7d55e453 100644 --- a/include/litmus/rt_param.h +++ b/include/litmus/rt_param.h @@ -91,6 +91,7 @@ struct rt_task { budget_policy_t budget_policy; /* ignored by pfair */ release_policy_t release_policy; pgm_node_type_t pgm_type; + lt_t pgm_expected_etoe; }; union np_flag { diff --git a/include/litmus/sched_trace.h b/include/litmus/sched_trace.h index c30a80a69333..8c7dfae1ab24 100644 --- a/include/litmus/sched_trace.h +++ b/include/litmus/sched_trace.h @@ -83,7 +83,8 @@ struct st_sys_release_data { struct st_pgm_param_data { u32 node_type; u16 graph_pid; - u8 __unused[10]; + u16 unused; + u64 expected_graph_etoe; }; struct st_pgm_release_data { diff --git a/litmus/sched_task_trace.c b/litmus/sched_task_trace.c index b9e772c07652..ea9e207a50d5 100644 --- a/litmus/sched_task_trace.c +++ b/litmus/sched_task_trace.c @@ -245,6 +245,7 @@ feather_callback void do_sched_trace_pgm_param(unsigned long id, unsigned long _ if (rec) { rec->data.pgm_param.node_type = tsk_rt(t)->task_params.pgm_type; rec->data.pgm_param.graph_pid = t->tgid; + rec->data.pgm_param.expected_graph_etoe = tsk_rt(t)->task_params.pgm_expected_etoe; put_record(rec); } } -- cgit v1.2.2 From 94b8c497a824e169bc23cd2138464739aaf0a381 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Wed, 19 Feb 2014 14:35:13 -0500 Subject: cleanup --- litmus/sched_cfl_split.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/litmus/sched_cfl_split.c b/litmus/sched_cfl_split.c index 6fd1591aec5a..71c177d24150 100644 --- a/litmus/sched_cfl_split.c +++ b/litmus/sched_cfl_split.c @@ -176,7 +176,7 @@ static enum hrtimer_restart on_split_timeout(struct hrtimer *timer) cpu_entry_t* st = container_of(timer, cpu_entry_t, split_timer); - + unsigned long flags; local_irq_save(flags); @@ -198,7 +198,7 @@ static void cancel_split_timer(cpu_entry_t* ce) /* Since interrupts are disabled and et->timer_armed is only * modified locally, we do not need any locks. */ - + if (ce->timer_armed) { ret = hrtimer_try_to_cancel(&ce->split_timer); /* Should never be inactive. */ @@ -220,7 +220,7 @@ static void arm_split_timer(cpu_entry_t *ce, /* __hrtimer_start_range_ns() cancels the timer * anyway, so we don't have to check whether it is still armed */ - + /*We won't do any new deadline moves if the budget has been exhausted*/ if (likely(!is_np(t) && (time_to_move = time_to_next_move(t)))) { when_to_fire = now + time_to_move; -- cgit v1.2.2 From 57e36bfdbc5f9312979956038e6ef04666834154 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Wed, 19 Feb 2014 15:30:14 -0500 Subject: more cleanup --- litmus/sched_cfl_split.c | 1 - 1 file changed, 1 deletion(-) diff --git a/litmus/sched_cfl_split.c b/litmus/sched_cfl_split.c index 71c177d24150..8dc72c39dcb2 100644 --- a/litmus/sched_cfl_split.c +++ b/litmus/sched_cfl_split.c @@ -668,7 +668,6 @@ static struct task_struct* cflsplit_schedule(struct task_struct * prev) * * Job deadline moves handled similarly */ -// if (np && (out_of_time || preempt || sleep)) { if (np && (out_of_time || sleep)) { unlink(entry->scheduled); request_exit_np(entry->scheduled); -- cgit v1.2.2 From 12ac3ce86bf0c19afe8e55caf93b234e6364175e Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Wed, 19 Feb 2014 15:30:22 -0500 Subject: Port C-FL PGM algorithms to G-EDF. --- litmus/sched_gsn_edf.c | 100 ++++++++++++++++++++++++++++++++----------------- 1 file changed, 65 insertions(+), 35 deletions(-) diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c index c5c4d4947c5a..073f0f4db821 100644 --- a/litmus/sched_gsn_edf.c +++ b/litmus/sched_gsn_edf.c @@ -455,45 +455,67 @@ static struct task_struct* gsnedf_schedule(struct task_struct * prev) if (exists) TRACE_TASK(prev, "blocks:%d out_of_time:%d np:%d sleep:%d preempt:%d " - "state:%d sig:%d\n", + "state:%d sig:%d boosted:%d\n", blocks, out_of_time, np, sleep, preempt, - prev->state, signal_pending(prev)); + prev->state, signal_pending(prev), + is_priority_boosted(entry->scheduled)); if (entry->linked && preempt) TRACE_TASK(prev, "will be preempted by %s/%d\n", entry->linked->comm, entry->linked->pid); #ifdef CONFIG_SCHED_PGM - if (exists && is_pgm_waiting(entry->scheduled)) { - if (!is_priority_boosted(entry->scheduled)) { - TRACE_TASK(entry->scheduled, "is waiting for PGM tokens.\n"); - BUG_ON(is_pgm_satisfied(entry->scheduled)); - - /* Boost priority so we'll be scheduled immediately - when needed tokens arrive. */ - tsk_rt(entry->scheduled)->priority_boosted = 1; - tsk_rt(entry->scheduled)->boost_start_time = litmus_clock(); - - if (unlikely(!blocks)) { - /* Task has probably blocked on an inbound token socket, but - if not, re-evaluate scheduling decisions */ - unlink(entry->scheduled); - gsnedf_job_arrival(entry->scheduled); + if (exists) { + if (is_pgm_sending(entry->scheduled)) { + if (!is_pgm_satisfied(entry->scheduled)) { + if (!is_priority_boosted(entry->scheduled)) { + TRACE_TASK(entry->scheduled, "is sending PGM tokens and needs boosting.\n"); + BUG_ON(is_pgm_satisfied(entry->scheduled)); + + /* We are either sending tokens or waiting for tokes. + If waiting: Boost priority so we'll be scheduled + immediately when needed tokens arrive. + If sending: Boost priority so no one (specifically, our + consumers) will preempt us while signalling the token + transmission. + */ + tsk_rt(entry->scheduled)->priority_boosted = 1; + tsk_rt(entry->scheduled)->boost_start_time = litmus_clock(); + + if (likely(!blocks)) { + unlink(entry->scheduled); + gsnedf_job_arrival(entry->scheduled); + /* we may regain the processor */ + if (preempt) { + preempt = entry->scheduled != entry->linked; + if (!preempt) { + TRACE_TASK(entry->scheduled, "blocked preemption by lazy boosting.\n"); + } + } + } + } } - } - else if (is_pgm_satisfied(entry->scheduled)) { - TRACE_TASK(entry->scheduled, "is done waiting for PGM tokens.\n"); - BUG_ON(!is_priority_boosted(entry->scheduled)); - - /* clear any boosting */ - tsk_rt(entry->scheduled)->priority_boosted = 0; - setup_pgm_release(entry->scheduled); - - if (likely(!blocks)) { - /* Task has probably called sched_yield(), so blocking is - unlikely. Re-evaluate scheduling decisions because we - still want to run. */ - unlink(entry->scheduled); - gsnedf_job_arrival(entry->scheduled); + else { /* sending is satisfied */ + tsk_rt(entry->scheduled)->ctrl_page->pgm_sending = 0; + tsk_rt(entry->scheduled)->ctrl_page->pgm_satisfied = 0; + + if (is_priority_boosted(entry->scheduled)) { + TRACE_TASK(entry->scheduled, + "is done sending PGM tokens must relinquish boosting.\n"); + /* clear boosting */ + tsk_rt(entry->scheduled)->priority_boosted = 0; + if(likely(!blocks)) { + /* recheck priority */ + unlink(entry->scheduled); + gsnedf_job_arrival(entry->scheduled); + /* we may lose the processor */ + if (!preempt) { + preempt = entry->scheduled != entry->linked; + if (preempt) { + TRACE_TASK(entry->scheduled, "preempted by lazy unboosting.\n"); + } + } + } + } } } } @@ -509,10 +531,13 @@ static struct task_struct* gsnedf_schedule(struct task_struct * prev) * that we are still linked. Multiple calls to request_exit_np() don't * hurt. */ - if (np && (out_of_time || preempt || sleep)) { + if (np && (out_of_time || sleep)) { unlink(entry->scheduled); request_exit_np(entry->scheduled); } + else if (np && preempt) { + request_exit_np(entry->scheduled); + } /* Any task that is preemptable and either exhausts its execution * budget or wants to sleep completes. We may have to reschedule after @@ -543,12 +568,14 @@ static struct task_struct* gsnedf_schedule(struct task_struct * prev) entry->scheduled->rt_param.scheduled_on = NO_CPU; TRACE_TASK(entry->scheduled, "scheduled_on = NO_CPU\n"); } - } else + } + else { /* Only override Linux scheduler if we have a real-time task * scheduled that needs to continue. */ if (exists) next = prev; + } sched_state_task_picked(); @@ -563,7 +590,6 @@ static struct task_struct* gsnedf_schedule(struct task_struct * prev) TRACE("becomes idle at %llu.\n", litmus_clock()); #endif - return next; } @@ -635,6 +661,10 @@ static void gsnedf_task_wake_up(struct task_struct *task) release_at(task, now); sched_trace_task_release(task); } + if (is_pgm_waiting(task)) { + /* shift out release/deadline, if needed */ + setup_pgm_release(task); + } gsnedf_job_arrival(task); raw_spin_unlock_irqrestore(&gsnedf_lock, flags); } -- cgit v1.2.2 From 0568a30a1f1895590a35d3487cce7efeaa142989 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Wed, 19 Feb 2014 15:31:18 -0500 Subject: Port C-FL PGM algorithms to C-EDF. --- litmus/sched_cedf.c | 49 +++++++++++++++++++++++++------------------------ 1 file changed, 25 insertions(+), 24 deletions(-) diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c index a25f2a474263..10ada7edadf2 100644 --- a/litmus/sched_cedf.c +++ b/litmus/sched_cedf.c @@ -456,9 +456,10 @@ static struct task_struct* cedf_schedule(struct task_struct * prev) if (exists) TRACE_TASK(prev, "blocks:%d out_of_time:%d np:%d sleep:%d preempt:%d " - "state:%d sig:%d\n", + "state:%d sig:%d boosted:%d\n", blocks, out_of_time, np, sleep, preempt, - prev->state, signal_pending(prev)); + prev->state, signal_pending(prev), + is_priority_boosted(entry->scheduled)); if (entry->linked && preempt) TRACE_TASK(prev, "will be preempted by %s/%d\n", entry->linked->comm, entry->linked->pid); @@ -473,17 +474,24 @@ static struct task_struct* cedf_schedule(struct task_struct * prev) /* We are either sending tokens or waiting for tokes. If waiting: Boost priority so we'll be scheduled - immediately when needed tokens arrive. + immediately when needed tokens arrive. If sending: Boost priority so no one (specifically, our - consumers) will preempt us while signalling the token - transmission. - */ + consumers) will preempt us while signalling the token + transmission. + */ tsk_rt(entry->scheduled)->priority_boosted = 1; tsk_rt(entry->scheduled)->boost_start_time = litmus_clock(); if (likely(!blocks)) { unlink(entry->scheduled); cedf_job_arrival(entry->scheduled); + /* we may regain the processor */ + if (preempt) { + preempt = entry->scheduled != entry->linked; + if (!preempt) { + TRACE_TASK(entry->scheduled, "blocked preemption by lazy boosting.\n"); + } + } } } } @@ -500,26 +508,17 @@ static struct task_struct* cedf_schedule(struct task_struct * prev) /* recheck priority */ unlink(entry->scheduled); cedf_job_arrival(entry->scheduled); + /* we may lose the processor */ + if (!preempt) { + preempt = entry->scheduled != entry->linked; + if (preempt) { + TRACE_TASK(entry->scheduled, "preempted by lazy unboosting.\n"); + } + } } } } } -#if 0 - else if(is_pgm_waiting(entry->scheduled)) { - int shifted_release; - - TRACE_TASK(entry->scheduled, "is waiting for PGM tokens.\n"); - /* release the next job if we have the tokens we need */ - shifted_release = setup_pgm_release(entry->scheduled); - - /* setup_pgm_release() can screw with our priority, - so recheck it */ - if (shifted_release && likely(!blocks)) { - unlink(entry->scheduled); - cedf_job_arrival(entry->scheduled); - } - } -#endif } #endif @@ -533,10 +532,13 @@ static struct task_struct* cedf_schedule(struct task_struct * prev) * that we are still linked. Multiple calls to request_exit_np() don't * hurt. */ - if (np && (out_of_time || preempt || sleep)) { + if (np && (out_of_time || sleep)) { unlink(entry->scheduled); request_exit_np(entry->scheduled); } + else if(np && preempt) { + request_exit_np(entry->scheduled); + } /* Any task that is preemptable and either exhausts its execution * budget or wants to sleep completes. We may have to reschedule after @@ -586,7 +588,6 @@ static struct task_struct* cedf_schedule(struct task_struct * prev) TRACE("becomes idle at %llu.\n", litmus_clock()); #endif - return next; } -- cgit v1.2.2