From d990b018b1eb12eb52713d553e5d61a3cdd1249b Mon Sep 17 00:00:00 2001 From: Christopher Kenna Date: Sun, 25 Sep 2011 16:05:50 -0400 Subject: Untested merge of CE and MC plugins --- litmus/sched_mc.c | 79 ++++++++++++++++++++++++++----------------------------- 1 file changed, 37 insertions(+), 42 deletions(-) (limited to 'litmus/sched_mc.c') diff --git a/litmus/sched_mc.c b/litmus/sched_mc.c index 577e7d36faf5..bce25bc8822e 100644 --- a/litmus/sched_mc.c +++ b/litmus/sched_mc.c @@ -24,25 +24,7 @@ #include #include - -/** - * crit_entry_t - State of a CPU within each criticality level system. - * @level Criticality level of this entry - * @linked Logically running task, ghost or regular - * @domain Domain from which to draw tasks - * @usable False if a higher criticality task is running - * @timer For ghost task budget enforcement - * @node Used to sort crit_entries by preemptability in global domains - */ -typedef struct { - enum crit_level level; - struct task_struct* linked; - domain_t* domain; - int usable; - struct hrtimer timer; - struct bheap_node* node; - atomic_t dirty; -} crit_entry_t; +#include /** * cpu_entry_t - State of a CPU for the entire MC system @@ -64,18 +46,6 @@ typedef struct { #endif } cpu_entry_t; -/** - * domain_data_t - Wrap domains with related CPU state - * @domain A domain for a criticality level - * @heap The preemptable heap of crit entries (for global domains) - * @crit_entry The crit entry for this domain (for partitioned domains) - */ -typedef struct { - domain_t domain; - struct bheap* heap; - crit_entry_t* crit_entry; -} domain_data_t; - static cpu_entry_t* cpus[NR_CPUS]; #ifdef CONFIG_RELEASE_MASTER static int interrupt_cpu; @@ -213,10 +183,14 @@ static void link_task_to_crit(crit_entry_t *ce, ce->linked = task; if (task) { task->rt_param.linked_on = crit_cpu(ce)->cpu; - if (is_ghost(task)) { + if (is_ghost(task) && CRIT_LEVEL_A != tsk_mc_crit(task)) { + /* There is a level-A timer that will force a + * preemption, so we don't set this for level-A + * tasks. + */ /* Reset budget timer */ task->se.exec_start = litmus_clock(); - when_to_fire = litmus_clock() + + when_to_fire = task->se.exec_start + tsk_mc_data(task)->mc_job.ghost_budget; __hrtimer_start_range_ns(&ce->timer, ns_to_ktime(when_to_fire), @@ -659,6 +633,9 @@ static void mc_task_exit(struct task_struct *task) tsk_rt(task)->scheduled_on = NO_CPU; } + if (CRIT_LEVEL_A == tsk_mc_crit(task)) + ce_task_exit(get_task_domain(task), task); + local_irq_restore(flags); } @@ -797,7 +774,22 @@ static long mc_activate_plugin(void) if (interrupt_cpu == NO_CPU) interrupt_cpu = 0; #endif - return 0; + return ce_activate_plugin(); +} + +/* + * This is the plugin's release at function, called by the release task-set + * system call. Other places in the file use the generic LITMUS release_at(), + * which is not this. + */ +void mc_release_at(struct task_struct *ts, lt_t start) +{ + ce_start(ts, start); +} + +long mc_deactivate_plugin(void) +{ + return ce_deactivate_plugin(); } /* ************************************************************************** @@ -820,11 +812,6 @@ static rt_domain_t _mc_crit_c_rt; struct bheap _mc_heap_c; struct bheap_node _mc_nodes_c[NR_CPUS]; -/* - * XXX commented out because I think this was an obvious typo - */ -/* release_at)_ */ - static struct sched_plugin mc_plugin __cacheline_aligned_in_smp = { .plugin_name = "MC", .task_new = mc_task_new, @@ -835,6 +822,8 @@ static struct sched_plugin mc_plugin __cacheline_aligned_in_smp = { .task_block = mc_task_block, .admit_task = mc_admit_task, .activate_plugin = mc_activate_plugin, + .release_at = mc_release_at, + .deactivate_plugin = mc_deactivate_plugin, }; static void init_crit_entry(crit_entry_t *ce, enum crit_level level, @@ -888,12 +877,14 @@ static inline void init_edf_domain(domain_t *dom, rt_domain_t *rt) edf_higher_prio); } +domain_data_t *ce_domain_for(int); static int __init init_mc(void) { int cpu; cpu_entry_t *entry; rt_domain_t *rt; domain_data_t *dom_data; + domain_t *dom; raw_spinlock_t *a_dom, *b_dom, *c_dom; /* For lock debugger */ for_each_online_cpu(cpu) { @@ -911,13 +902,17 @@ static int __init init_mc(void) #endif /* CRIT_LEVEL_A */ - dom_data = &per_cpu(_mc_crit_a, cpu); - rt = &per_cpu(_mc_crit_a_rt, cpu); + dom_data = ce_domain_for(cpu); init_local_domain(entry, dom_data, CRIT_LEVEL_A); - init_edf_domain(&dom_data->domain, rt); a_dom = dom_data->domain.lock; raw_spin_lock_init(a_dom); dom_data->domain.name = "LVL-A"; + /* Hook up the level A functions */ + dom = &dom_data->domain; + dom->requeue = ce_requeue; + dom->peek_ready = dom->take_ready = ce_peek_and_take_ready; + dom->higher_prio = ce_higher_prio; + dom->preempt_needed = mc_preempt_needed; /* CRIT_LEVEL_B */ dom_data = &per_cpu(_mc_crit_b, cpu); -- cgit v1.2.2 From d9e964752ce668f8a9540e9511e0cb73cd21d480 Mon Sep 17 00:00:00 2001 From: Christopher Kenna Date: Mon, 26 Sep 2011 14:14:41 -0400 Subject: checkpoint before refactor --- litmus/sched_mc.c | 72 ++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 53 insertions(+), 19 deletions(-) (limited to 'litmus/sched_mc.c') diff --git a/litmus/sched_mc.c b/litmus/sched_mc.c index bce25bc8822e..3b98a93511ab 100644 --- a/litmus/sched_mc.c +++ b/litmus/sched_mc.c @@ -104,7 +104,7 @@ static int cpu_lower_prio(struct bheap_node *a, struct bheap_node *b) * Return true if the domain has a higher priority ready task. The curr * task must belong to the domain. */ -static noinline int mc_preempt_needed(domain_t *dom, struct task_struct* curr) +noinline int mc_preempt_needed(domain_t *dom, struct task_struct* curr) { struct task_struct *next = dom->peek_ready(dom); if (!next || !curr) { @@ -208,7 +208,7 @@ static void link_task_to_crit(crit_entry_t *ce, } } -static void check_for_preempt(domain_t*); +void mc_check_for_preempt(domain_t*); /** * job_arrival() - Called when a task re-enters the system. * Caller must hold no locks. @@ -222,7 +222,7 @@ static void job_arrival(struct task_struct *task) if (can_requeue(task)) { raw_spin_lock(dom->lock); dom->requeue(dom, task); - check_for_preempt(dom); + mc_check_for_preempt(dom); raw_spin_unlock(dom->lock); } else { /* If a global task is scheduled on one cpu, it CANNOT @@ -374,18 +374,19 @@ static void update_crit_levels(cpu_entry_t *entry) } /** - * check_for_preempt() - Causes a preemption if higher-priority tasks are ready. + * mc_check_for_preempt() - Causes a preemption if higher-priority tasks are ready. * Caller must hold domain lock. * Makes gigantic nasty assumption that there is 1 global criticality level, * and it is the last one in each list, so it doesn't call update_crit.. */ -static void check_for_preempt(domain_t *dom) +void mc_check_for_preempt(domain_t *dom) { int preempted = 1; cpu_entry_t *entry; crit_entry_t *ce; if (is_global(dom)) { + TRACE("domain: %s is global\n", dom->name); /* Loop until we find a non-preemptable CPU */ while ((ce = lowest_prio_cpu(dom)) && preempted) { entry = crit_cpu(ce); @@ -398,6 +399,7 @@ static void check_for_preempt(domain_t *dom) raw_spin_unlock(&entry->lock); } } else /* Partitioned */ { + TRACE("domain: %s is partitioned\n", dom->name); ce = domain_data(dom)->crit_entry; entry = crit_cpu(ce); raw_spin_lock(&entry->lock); @@ -476,6 +478,7 @@ static void job_completion(struct task_struct *task, int forced) /* If it's not a ghost job, do ghost job conversion */ if (!is_ghost(task)) { + TRACE_TASK(task, "is not a ghost task\n"); tsk_mc_data(task)->mc_job.ghost_budget = budget_remaining(task); tsk_mc_data(task)->mc_job.is_ghost = 1; } @@ -485,6 +488,7 @@ static void job_completion(struct task_struct *task, int forced) * conversion. Revert back to a normal task and complete the period. */ if (tsk_mc_data(task)->mc_job.ghost_budget == 0) { + TRACE_TASK(task, "has zero ghost budget\n"); tsk_mc_data(task)->mc_job.is_ghost = 0; prepare_for_next_period(task); if (is_released(task, litmus_clock())) @@ -530,6 +534,26 @@ static enum hrtimer_restart mc_ghost_exhausted(struct hrtimer *timer) return HRTIMER_NORESTART; } +void __mc_ce_timer_callback(struct hrtimer *timer); +domain_data_t *ce_domain_for(int); +static enum hrtimer_restart ce_timer_function(struct hrtimer *timer) +{ + struct ce_dom_data *ce_data; + domain_data_t *dom_data; + unsigned long flags; + + TRACE("timer callback\n"); + + ce_data = container_of(timer, struct ce_dom_data, timer); + dom_data = ce_domain_for(ce_data->cpu); + raw_spin_lock_irqsave(dom_data->domain.lock, flags); + __mc_ce_timer_callback(timer); + mc_check_for_preempt(&dom_data->domain); + raw_spin_unlock_irqrestore(dom_data->domain.lock, flags); + return HRTIMER_RESTART; +} + + /** * mc_release_jobs() - Add heap of tasks to the system, check for preemptions. */ @@ -542,7 +566,7 @@ static void mc_release_jobs(rt_domain_t* rt, struct bheap* tasks) raw_spin_lock_irqsave(dom->lock, flags); TRACE_TASK(first, "Jobs released"); __merge_ready(rt, tasks); - check_for_preempt(dom); + mc_check_for_preempt(dom); raw_spin_unlock_irqrestore(dom->lock, flags); } @@ -639,25 +663,37 @@ static void mc_task_exit(struct task_struct *task) local_irq_restore(flags); } +long __mc_ce_admit_task(struct task_struct*); /** * mc_admit_task() - Return true if the task is valid. * Assumes there are no partitioned levels after level B. */ static long mc_admit_task(struct task_struct* task) { + const enum crit_level crit = tsk_mc_crit(task); + long ret; if (!tsk_mc_data(task)) { printk(KERN_WARNING "Tried to admit task with no criticality " "level\n"); - return -EINVAL; + ret = -EINVAL; + goto out; } - if (tsk_mc_crit(task) < CRIT_LEVEL_C && get_partition(task) == NO_CPU) { + if (crit < CRIT_LEVEL_C && get_partition(task) == NO_CPU) { printk(KERN_WARNING "Tried to admit partitioned task with no " "partition\n"); - return -EINVAL; + ret = -EINVAL; + goto out; + } + if (crit == CRIT_LEVEL_A) { + ret = __mc_ce_admit_task(task); + if (ret) + goto out; } printk(KERN_INFO "Admitted task with criticality level %d\n", tsk_mc_crit(task)); - return 0; + ret = 0; +out: + return ret; } /** @@ -746,6 +782,7 @@ static struct task_struct* mc_schedule(struct task_struct * prev) raw_spin_unlock(dom->lock); update_crit_levels(entry); raw_spin_lock(&entry->lock); + continue; } } raw_spin_unlock(dom->lock); @@ -784,7 +821,11 @@ static long mc_activate_plugin(void) */ void mc_release_at(struct task_struct *ts, lt_t start) { - ce_start(ts, start); + /* hack so that we can have CE timers start at the right time */ + if (CRIT_LEVEL_A == tsk_mc_crit(ts)) + ce_start(ts, start); + else + release_at(ts, start); } long mc_deactivate_plugin(void) @@ -884,7 +925,6 @@ static int __init init_mc(void) cpu_entry_t *entry; rt_domain_t *rt; domain_data_t *dom_data; - domain_t *dom; raw_spinlock_t *a_dom, *b_dom, *c_dom; /* For lock debugger */ for_each_online_cpu(cpu) { @@ -903,16 +943,10 @@ static int __init init_mc(void) /* CRIT_LEVEL_A */ dom_data = ce_domain_for(cpu); + ce_domain_init(/* TODO */); init_local_domain(entry, dom_data, CRIT_LEVEL_A); a_dom = dom_data->domain.lock; - raw_spin_lock_init(a_dom); dom_data->domain.name = "LVL-A"; - /* Hook up the level A functions */ - dom = &dom_data->domain; - dom->requeue = ce_requeue; - dom->peek_ready = dom->take_ready = ce_peek_and_take_ready; - dom->higher_prio = ce_higher_prio; - dom->preempt_needed = mc_preempt_needed; /* CRIT_LEVEL_B */ dom_data = &per_cpu(_mc_crit_b, cpu); -- cgit v1.2.2 From 46bb1ecb861729ebc3ac1631b6a7f7b131db86ac Mon Sep 17 00:00:00 2001 From: Christopher Kenna Date: Mon, 26 Sep 2011 23:55:48 -0400 Subject: Checkpoint commit. Testing begins. --- litmus/sched_mc.c | 87 ++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 64 insertions(+), 23 deletions(-) (limited to 'litmus/sched_mc.c') diff --git a/litmus/sched_mc.c b/litmus/sched_mc.c index 3b98a93511ab..11ba10a54f4d 100644 --- a/litmus/sched_mc.c +++ b/litmus/sched_mc.c @@ -507,7 +507,7 @@ static enum hrtimer_restart mc_ghost_exhausted(struct hrtimer *timer) { unsigned long flags; struct task_struct *tmp = NULL; - crit_entry_t *ce = container_of(timer, crit_entry_t, timer);; + crit_entry_t *ce = container_of(timer, crit_entry_t, timer); local_irq_save(flags); TRACE_CRIT_ENTRY(ce, "Ghost exhausted firing"); @@ -534,22 +534,38 @@ static enum hrtimer_restart mc_ghost_exhausted(struct hrtimer *timer) return HRTIMER_NORESTART; } -void __mc_ce_timer_callback(struct hrtimer *timer); -domain_data_t *ce_domain_for(int); static enum hrtimer_restart ce_timer_function(struct hrtimer *timer) { - struct ce_dom_data *ce_data; - domain_data_t *dom_data; + struct ce_dom_data *ce_data = + container_of(timer, struct ce_dom_data, timer); + crit_entry_t *ce = &cpus[ce_data->cpu]->crit_entries[CRIT_LEVEL_A]; + domain_t *dom = ce->domain; + struct task_struct *old_link = NULL; unsigned long flags; - TRACE("timer callback\n"); + TRACE("MC level-A timer callback for CPU %d\n", ce_data->cpu); + + raw_spin_lock_irqsave(dom->lock, flags); + + raw_spin_lock(&crit_cpu(ce)->lock); + if (ce->linked && + ce->linked == ce_data->should_schedule && + is_ghost(ce->linked)) + { + update_ghost_time(ce->linked); + if (tsk_mc_data(ce->linked)->mc_job.ghost_budget == 0) { + old_link = ce->linked; + link_task_to_crit(ce, NULL); + } + } + raw_spin_unlock(&crit_cpu(ce)->lock); + + if (NULL != old_link) + job_completion(old_link, 0); - ce_data = container_of(timer, struct ce_dom_data, timer); - dom_data = ce_domain_for(ce_data->cpu); - raw_spin_lock_irqsave(dom_data->domain.lock, flags); - __mc_ce_timer_callback(timer); - mc_check_for_preempt(&dom_data->domain); - raw_spin_unlock_irqrestore(dom_data->domain.lock, flags); + mc_ce_timer_callback_common(dom, timer); + mc_check_for_preempt(dom); + raw_spin_unlock_irqrestore(dom->lock, flags); return HRTIMER_RESTART; } @@ -658,12 +674,11 @@ static void mc_task_exit(struct task_struct *task) } if (CRIT_LEVEL_A == tsk_mc_crit(task)) - ce_task_exit(get_task_domain(task), task); + mc_ce_task_exit_common(task); local_irq_restore(flags); } -long __mc_ce_admit_task(struct task_struct*); /** * mc_admit_task() - Return true if the task is valid. * Assumes there are no partitioned levels after level B. @@ -685,7 +700,7 @@ static long mc_admit_task(struct task_struct* task) goto out; } if (crit == CRIT_LEVEL_A) { - ret = __mc_ce_admit_task(task); + ret = mc_ce_admit_task_common(task); if (ret) goto out; } @@ -806,12 +821,30 @@ static struct task_struct* mc_schedule(struct task_struct * prev) static long mc_activate_plugin(void) { + domain_data_t *dom_data; + domain_t *dom; + domain_data_t *our_domains[NR_CPUS]; + int cpu, n = 0; + long ret; + #ifdef CONFIG_RELEASE_MASTER interrupt_cpu = atomic_read(&release_master_cpu); if (interrupt_cpu == NO_CPU) interrupt_cpu = 0; #endif - return ce_activate_plugin(); + for_each_online_cpu(cpu) { + BUG_ON(NR_CPUS <= n); + dom = cpus[cpu]->crit_entries[CRIT_LEVEL_A].domain; + dom_data = domain_data(dom); + our_domains[cpu] = dom_data; + n++; + } + ret = mc_ce_set_domains(n, our_domains); + if (ret) + goto out; + ret = mc_ce_activate_plugin_common(); +out: + return ret; } /* @@ -823,14 +856,14 @@ void mc_release_at(struct task_struct *ts, lt_t start) { /* hack so that we can have CE timers start at the right time */ if (CRIT_LEVEL_A == tsk_mc_crit(ts)) - ce_start(ts, start); + mc_ce_release_at_common(ts, start); else release_at(ts, start); } long mc_deactivate_plugin(void) { - return ce_deactivate_plugin(); + return mc_ce_deactivate_plugin_common(); } /* ************************************************************************** @@ -843,7 +876,8 @@ long mc_deactivate_plugin(void) DEFINE_PER_CPU(cpu_entry_t, _mc_cpus); /* LVL-A */ DEFINE_PER_CPU(domain_data_t, _mc_crit_a); -DEFINE_PER_CPU(rt_domain_t, _mc_crit_a_rt); +DEFINE_PER_CPU(raw_spinlock_t, _mc_crit_a_lock); +DEFINE_PER_CPU(struct ce_dom_data, _mc_crit_a_ce_data); /* LVL-B */ DEFINE_PER_CPU(domain_data_t, _mc_crit_b); DEFINE_PER_CPU(rt_domain_t, _mc_crit_b_rt); @@ -925,7 +959,8 @@ static int __init init_mc(void) cpu_entry_t *entry; rt_domain_t *rt; domain_data_t *dom_data; - raw_spinlock_t *a_dom, *b_dom, *c_dom; /* For lock debugger */ + raw_spinlock_t *a_dom_lock, *b_dom, *c_dom; /* For lock debugger */ + struct ce_dom_data *ce_data; for_each_online_cpu(cpu) { entry = &per_cpu(_mc_cpus, cpu); @@ -942,10 +977,16 @@ static int __init init_mc(void) #endif /* CRIT_LEVEL_A */ - dom_data = ce_domain_for(cpu); - ce_domain_init(/* TODO */); + dom_data = &per_cpu(_mc_crit_a, cpu); + ce_data = &per_cpu(_mc_crit_a_ce_data, cpu); + a_dom_lock = &per_cpu(_mc_crit_a_lock, cpu); + raw_spin_lock_init(a_dom_lock); + ce_domain_init(&dom_data->domain, + a_dom_lock, ce_requeue, ce_peek_and_take_ready, + ce_peek_and_take_ready, mc_preempt_needed, + ce_higher_prio, ce_data, cpu, + ce_timer_function); init_local_domain(entry, dom_data, CRIT_LEVEL_A); - a_dom = dom_data->domain.lock; dom_data->domain.name = "LVL-A"; /* CRIT_LEVEL_B */ -- cgit v1.2.2 From 609c45f71b7a2405230fd2f8436837d6389ec599 Mon Sep 17 00:00:00 2001 From: Christopher Kenna Date: Tue, 27 Sep 2011 14:07:52 -0400 Subject: Debugged ghosts in the MC scheduler for CE tasks. --- litmus/sched_mc.c | 35 +++++++++++++++++++++++------------ 1 file changed, 23 insertions(+), 12 deletions(-) (limited to 'litmus/sched_mc.c') diff --git a/litmus/sched_mc.c b/litmus/sched_mc.c index 11ba10a54f4d..afba6e44716f 100644 --- a/litmus/sched_mc.c +++ b/litmus/sched_mc.c @@ -407,6 +407,7 @@ void mc_check_for_preempt(domain_t *dom) preempt(dom, ce); update_crit_levels(entry); } else { + TRACE("domain: %s NOT preempting\n", dom->name); raw_spin_unlock(&entry->lock); } } @@ -545,27 +546,37 @@ static enum hrtimer_restart ce_timer_function(struct hrtimer *timer) TRACE("MC level-A timer callback for CPU %d\n", ce_data->cpu); - raw_spin_lock_irqsave(dom->lock, flags); + local_irq_save(flags); + + raw_spin_lock(dom->lock); raw_spin_lock(&crit_cpu(ce)->lock); if (ce->linked && - ce->linked == ce_data->should_schedule && - is_ghost(ce->linked)) + ce->linked == ce_data->should_schedule && + is_ghost(ce->linked)) { - update_ghost_time(ce->linked); - if (tsk_mc_data(ce->linked)->mc_job.ghost_budget == 0) { - old_link = ce->linked; - link_task_to_crit(ce, NULL); - } + old_link = ce->linked; + tsk_mc_data(ce->linked)->mc_job.ghost_budget = 0; + link_task_to_crit(ce, NULL); } raw_spin_unlock(&crit_cpu(ce)->lock); - if (NULL != old_link) + mc_ce_timer_callback_common(dom, timer); + + /* job completion will check for preemptions by means of calling job + * arrival if the task is not blocked */ + if (NULL != old_link) { + TRACE(" old_link " TS " so will call job completion\n", TA(old_link)); + raw_spin_unlock(dom->lock); job_completion(old_link, 0); + } else { + TRACE(" old_link was null, so will call check for preempt\n"); + raw_spin_unlock(dom->lock); + mc_check_for_preempt(dom); + } + + local_irq_restore(flags); - mc_ce_timer_callback_common(dom, timer); - mc_check_for_preempt(dom); - raw_spin_unlock_irqrestore(dom->lock, flags); return HRTIMER_RESTART; } -- cgit v1.2.2