From a13573378cc34327d5af9d2af88e12ccf1ff4fc3 Mon Sep 17 00:00:00 2001 From: Joshua Bakita Date: Sat, 10 Oct 2020 22:52:15 -0400 Subject: Improve portability and fix dynamic CPU entry/exit in gedf_env Dynamic CPU entry/exit changes: - Fix build with CONFIG_RELEASE_MASTER - Migrate gedf_env release timer when a core is suspended - Fix race condition in gedf_env core resume - Add documentation - Allow for gedf_env_suspend() and gedf_env_resume() to be called on CPUs that have already been suspended or resumed. (They do nothing in those cases.) Portability: - Allocate space in `gedf_reservation_environment` using `num_online_cpus()` rather than `NR_CPUS`. Otherwise the stack frame can overflow when `NR_CPUS` is large. - Assign `plugin_state` from the plugin rather than the extended reservations code to support other uses of `plugin_state`. Misc: - Improve robustnesss of `gedf_env_is_np()` - Don't memset with 0 memory already zeroed-out by `kzalloc()` - Use GFP_ATOMIC for allocations when in a scheduling context --- litmus/reservations/gedf_reservation.c | 124 ++++++++++++++++++++++++++------- litmus/rt_domain.c | 6 +- litmus/sched_ext_res.c | 1 + litmus/sched_ext_res_c1.c | 1 + 4 files changed, 104 insertions(+), 28 deletions(-) (limited to 'litmus') diff --git a/litmus/reservations/gedf_reservation.c b/litmus/reservations/gedf_reservation.c index dca51a23386e..2ed16575144e 100644 --- a/litmus/reservations/gedf_reservation.c +++ b/litmus/reservations/gedf_reservation.c @@ -13,6 +13,12 @@ #include #include +// Needed to store context during cross-CPU function calls +struct csd_wrapper { + struct call_single_data csd; + struct gedf_reservation_environment* gedf_env; +}; + /* ******************************************************************************* */ /* returns 1 if res of a has earlier deadline than res of b */ static int edf_ready_order(struct bheap_node* a, struct bheap_node* b) @@ -300,11 +306,9 @@ long alloc_gedf_task_reservation( if (!gedf_task_res) return -ENOMEM; - memset(gedf_task_res, 0, sizeof(struct gedf_task_reservation)); init_ext_reservation(&gedf_task_res->gedf_res.res, task->pid, &gedf_task_ops); gedf_task_res->task = task; - tsk_rt(task)->plugin_state = gedf_task_res; *_res = gedf_task_res; return 0; @@ -322,7 +326,6 @@ long alloc_gedf_container_reservation( if (!gedf_cont_res) return -ENOMEM; - memset(gedf_cont_res, 0, sizeof(struct gedf_container_reservation)); init_ext_reservation(&gedf_cont_res->gedf_res.res, id, &gedf_cont_ops); gedf_cont_res->max_budget = max_budget; @@ -357,7 +360,9 @@ static void gedf_env_shutdown( raw_spin_unlock_irqrestore(&gedf_env->domain.ready_lock, flags); /* free memory */ - kfree(env); + kfree(gedf_env->cpu_entries); + kfree(gedf_env->cpu_node); + kfree(gedf_env); } static int gedf_env_is_np( @@ -366,12 +371,9 @@ static int gedf_env_is_np( { struct gedf_reservation_environment* gedf_env = container_of(env, struct gedf_reservation_environment, env); - struct reservation* res = - &gedf_env->cpu_entries[cpu].scheduled->res; - if (res) - return res->ops->is_np(res, cpu); - else - return 0; + struct gedf_reservation* scheduled = + gedf_env->cpu_entries[cpu].scheduled; + return scheduled && scheduled->res.ops->is_np(&scheduled->res, cpu); } static struct reservation* gedf_find_res_by_id( @@ -452,9 +454,28 @@ static void gedf_env_add_res( raw_spin_unlock_irqrestore(&gedf_env->domain.ready_lock, flags); } -/* TODO: currently does not fully support dynamic cores count in environment - * when a core is suspended, if the release timer is on that core, it will not be - * properly suspended. Only the last core to suspend stops the release timer +/* try_resume_timer: Attempt to resume the release timer locally. + * @param csd_info Pointer to `info` field of struct call_single_data + * @note Used as IPI callback, do not call directly. Lockless. + */ +static void try_resume_timer(void *csd_info) +{ + struct csd_wrapper* csd_wrapper = csd_info; + struct gedf_reservation_environment* gedf_env = csd_wrapper->gedf_env; + int cpu = smp_processor_id(); + struct gedf_cpu_entry* entry = &gedf_env->cpu_entries[cpu]; + // Abort if this CPU was suspended before we could process the IPI + if (!bheap_node_in_heap(entry->hn)) + goto out; + domain_resume_releases(&gedf_env->domain); +out: + kfree(csd_wrapper); +} + +/* gedf_env_suspend: Remove the specified core from scheduling consideration + * @param env Environment to modify + * @param cpu CPU to remove if present. + * @note Safe to call if core already removed. Skips lock in that case. */ static void gedf_env_suspend( struct reservation_environment* env, @@ -468,7 +489,19 @@ static void gedf_env_suspend( gedf_env = container_of(env, struct gedf_reservation_environment, env); entry = &gedf_env->cpu_entries[cpu]; + /* Ignore suspension requests on inactive cores + * This will not errantly fail, as the first thing resume() does is re-add the node + * This will only errantly pass if another core is simultaneously inside + * our critical section. The second check catches that. + * In all cases this will avoid taking the lock if we were never part of the container. + */ + if (!bheap_node_in_heap(entry->hn)) + return; + raw_spin_lock_irqsave(&gedf_env->domain.ready_lock, flags); + // Do not remove! See above comment. + if (!bheap_node_in_heap(entry->hn)) + goto unlock; //TODO: More Graceful way to handle forbidden zone violation? BUG_ON(env->ops->is_np(env, cpu)); @@ -484,19 +517,34 @@ static void gedf_env_suspend( entry->scheduled->res.ops->on_preempt(&entry->scheduled->res, cpu); entry->scheduled = NULL; - BUG_ON(!bheap_node_in_heap(entry->hn)); /* this essentially removes the cpu from scheduling consideration */ bheap_delete(cpu_lower_prio, &gedf_env->cpu_heap, entry->hn); check_for_preemptions(gedf_env); - raw_spin_unlock_irqrestore(&gedf_env->domain.ready_lock, flags); - - /* suspends rt_domain releases when the last core of env is preempted */ + /* suspends rt_domain releases when the last core of env is preempted + * OR re-arm release timer on a different CPU */ if (!gedf_env->num_cpus) domain_suspend_releases(&gedf_env->domain); + else { + struct csd_wrapper* csd_wrapper = + kzalloc(sizeof(struct csd_wrapper), GFP_ATOMIC); + csd_wrapper->gedf_env = gedf_env; + csd_wrapper->csd.func = &try_resume_timer; + csd_wrapper->csd.info = csd_wrapper; + smp_call_function_single_async( + lowest_prio_cpu(&gedf_env->cpu_heap)->id, + &csd_wrapper->csd); + } +unlock: + raw_spin_unlock_irqrestore(&gedf_env->domain.ready_lock, flags); } +/* gedf_env_resume: Add the specified core to scheduling consideration + * @param env Environment to modify + * @param cpu CPU to add if not yet added. + * @note Safe to call if core already added. + */ static void gedf_env_resume( struct reservation_environment* env, int cpu) @@ -504,21 +552,35 @@ static void gedf_env_resume( struct gedf_reservation_environment* gedf_env; struct gedf_cpu_entry* entry; unsigned long flags; + // Needs to be volatile or it may be optimized to gedf_env->num_cpus + volatile int tmp_cpus; gedf_env = container_of(env, struct gedf_reservation_environment, env); entry = &gedf_env->cpu_entries[cpu]; - /* resumes rt_domain releases when the first core of env resumes execution */ - if (!gedf_env->num_cpus) - domain_resume_releases(&gedf_env->domain); + // If we've already been resumed, do nothing + if (bheap_node_in_heap(entry->hn)) + return; raw_spin_lock_irqsave(&gedf_env->domain.ready_lock, flags); - BUG_ON(bheap_node_in_heap(entry->hn)); - gedf_env->num_cpus++; + // Check again. Our earlier check may have raced with this critical section + if (bheap_node_in_heap(entry->hn)) { + raw_spin_unlock_irqrestore(&gedf_env->domain.ready_lock, flags); + return; + } + + // Save how many cpus were resumed before us (if none, we need to restart the timer) + tmp_cpus = gedf_env->num_cpus; + /* adds cpu back to scheduling consideration */ bheap_insert(cpu_lower_prio, &gedf_env->cpu_heap, entry->hn); + gedf_env->num_cpus++; raw_spin_unlock_irqrestore(&gedf_env->domain.ready_lock, flags); + + // Keep this outside the lock. Resuming the timer may have side-effects. + if (!tmp_cpus) + domain_resume_releases(&gedf_env->domain); } static struct task_struct* gedf_env_dispatch( @@ -644,12 +706,24 @@ long alloc_gedf_reservation_environment( { struct gedf_reservation_environment* gedf_env; int i; + int total_cpus = num_online_cpus(); - gedf_env = kzalloc(sizeof(struct gedf_reservation_environment), GFP_KERNEL); + gedf_env = kzalloc(sizeof(struct gedf_reservation_environment), GFP_ATOMIC); if (!gedf_env) return -ENOMEM; - - memset(gedf_env, 0, sizeof(struct gedf_reservation_environment)); + /* We don't know which subset of CPUs we'll run on, so we must keep state + * for all of them */ + gedf_env->cpu_entries = kzalloc(sizeof(struct gedf_cpu_entry)*total_cpus, GFP_ATOMIC); + if (!gedf_env->cpu_entries) { + kfree(gedf_env); + return -ENOMEM; + } + gedf_env->cpu_node = kzalloc(sizeof(struct bheap_node)*total_cpus, GFP_ATOMIC); + if (!gedf_env->cpu_node) { + kfree(gedf_env->cpu_entries); + kfree(gedf_env); + return -ENOMEM; + } /* set environment callback actions */ gedf_env->env.ops = &gedf_env_ops; diff --git a/litmus/rt_domain.c b/litmus/rt_domain.c index 1a15e2491a65..db3a48bff0d0 100644 --- a/litmus/rt_domain.c +++ b/litmus/rt_domain.c @@ -123,6 +123,7 @@ void domain_suspend_releases(rt_domain_t* rt) hrtimer_cancel(&rt->timer); } +// Resume the release timer on the current CPU void domain_resume_releases(rt_domain_t* rt) { release_jobs_before_now(rt); @@ -131,7 +132,6 @@ void domain_resume_releases(rt_domain_t* rt) ns_to_ktime(rt->release_queue.earliest_release), HRTIMER_MODE_ABS_PINNED); } - } /* allocated in litmus.c */ @@ -343,7 +343,7 @@ static void arm_release_timer(rt_domain_t *_rt) * TODO: find some way to combine this with the task version of this fuction */ #ifdef CONFIG_RELEASE_MASTER -#define arm_release_timer_res(t) arm_release_timer_res_on((t), NO_CPU) +#define arm_release_timer_res(t, i) arm_release_timer_res_on((t), (i), NO_CPU) static void arm_release_timer_res_on(rt_domain_t *_rt, int interrupt_release, int target_cpu) #else static void arm_release_timer_res(rt_domain_t *_rt, int interrupt_release) @@ -526,7 +526,7 @@ void __add_release_res_on(rt_domain_t* rt, struct reservation *res, { list_add(&res->ln, &rt->tobe_released); - arm_release_timer_res_on(rt, target_cpu); + arm_release_timer_res_on(rt, 1, target_cpu); } #endif diff --git a/litmus/sched_ext_res.c b/litmus/sched_ext_res.c index 492e2dd8db09..583a2ed9aef0 100644 --- a/litmus/sched_ext_res.c +++ b/litmus/sched_ext_res.c @@ -105,6 +105,7 @@ static long ext_res_admit_task(struct task_struct *tsk) err = alloc_gedf_task_reservation(&gedf_task_res, tsk); if (err) return err; + tsk_rt(tsk)->plugin_state = gedf_task_res; gedf_task_res->gedf_res.res.par_env = mtd_res->res[0].env; diff --git a/litmus/sched_ext_res_c1.c b/litmus/sched_ext_res_c1.c index 63f6d821d2d4..559708c4234f 100644 --- a/litmus/sched_ext_res_c1.c +++ b/litmus/sched_ext_res_c1.c @@ -135,6 +135,7 @@ static long ext_res_admit_task(struct task_struct *tsk) err = alloc_gedf_task_reservation(&gedf_task_res, tsk); if (err) return err; + tsk_rt(tsk)->plugin_state = gedf_task_res; gedf_task_res->gedf_res.res.par_env = &gedf_env->env; -- cgit v1.2.2 From b58595723675d016e7a8e06afcad9be8fd85de3a Mon Sep 17 00:00:00 2001 From: Zelin Tong Date: Tue, 13 Oct 2020 12:11:06 -0400 Subject: Changed how priority is set in gedf_reservations Now set to ULLONG_MAX - deadline(absolute). This fixes logic issues in using higher_res_prio when one parameter is null --- litmus/reservations/gedf_reservation.c | 12 +++++------- 1 file changed, 5 insertions(+), 7 deletions(-) (limited to 'litmus') diff --git a/litmus/reservations/gedf_reservation.c b/litmus/reservations/gedf_reservation.c index 2ed16575144e..157cd16d7ebb 100644 --- a/litmus/reservations/gedf_reservation.c +++ b/litmus/reservations/gedf_reservation.c @@ -23,7 +23,7 @@ struct csd_wrapper { /* returns 1 if res of a has earlier deadline than res of b */ static int edf_ready_order(struct bheap_node* a, struct bheap_node* b) { - return higher_res_prio(bheap2res(b), bheap2res(a)); + return higher_res_prio(bheap2res(a), bheap2res(b)); } /* Functions used to maintain a heap of cpu entries in edf order @@ -38,7 +38,6 @@ static int cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b) struct gedf_cpu_entry *a, *b; a = _a->value; b = _b->value; - /* use higher prio here because prio is deadline value */ return higher_res_prio(&b->linked->res, &a->linked->res); } @@ -72,8 +71,7 @@ static int edf_preemption_needed( * don't know what address space we're currently in. */ - /* reversed */ - return higher_res_prio(&gedf_res->res, __next_ready_res(&gedf_env->domain)); + return higher_res_prio(__next_ready_res(&gedf_env->domain), &gedf_res->res); } /* ******************************************************************************** */ @@ -221,7 +219,7 @@ static void gedf_replenish_budget( res->budget_consumed = 0; res->cur_budget = gedf_cont_res->max_budget; res->replenishment_time += gedf_cont_res->period; - res->priority = res->replenishment_time + gedf_cont_res->relative_deadline; + res->priority = ULLONG_MAX - res->replenishment_time - gedf_cont_res->relative_deadline; } static void gedf_task_replenish_budget( @@ -235,12 +233,12 @@ static void gedf_task_replenish_budget( prepare_for_next_period(t); tsk_rt(t)->completed = 0; sched_trace_task_release(t); - res->priority = get_deadline(t); + res->priority = ULLONG_MAX - get_deadline(t); res->replenishment_time = get_release(t); } else { sched_trace_task_completion(t, 1); res->replenishment_time += get_rt_period(t); - res->priority = res->replenishment_time + get_rt_relative_deadline(t); + res->priority = ULLONG_MAX - res->replenishment_time - get_rt_relative_deadline(t); TRACE_TASK(t, "overrun budget!\n"); } res->budget_consumed = 0; -- cgit v1.2.2