From 983773f990053cb0ced72afb4b69594e5d32c779 Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Thu, 6 Dec 2012 20:37:20 -0500 Subject: AUX_FUTURE and revised inh-based aux tie break --- include/litmus/aux_tasks.h | 2 + include/litmus/litmus.h | 1 + include/litmus/rt_param.h | 7 ++ kernel/fork.c | 6 +- litmus/aux_tasks.c | 198 +++++++++++++++++++++++++++++++-------------- litmus/edf_common.c | 78 ++++++++---------- litmus/litmus.c | 8 ++ 7 files changed, 192 insertions(+), 108 deletions(-) mode change 100644 => 100755 include/litmus/aux_tasks.h mode change 100644 => 100755 include/litmus/litmus.h mode change 100644 => 100755 include/litmus/rt_param.h mode change 100644 => 100755 litmus/litmus.c diff --git a/include/litmus/aux_tasks.h b/include/litmus/aux_tasks.h old mode 100644 new mode 100755 index 3bb6b26fef09..87745c1c0df0 --- a/include/litmus/aux_tasks.h +++ b/include/litmus/aux_tasks.h @@ -6,6 +6,8 @@ struct task_struct; /* admit an aux task with default parameters */ //int admit_aux_task(struct task_struct *t); +int make_aux_task_if_required(struct task_struct *t); + /* call on an aux task when it exits real-time */ int exit_aux_task(struct task_struct *t); diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h old mode 100644 new mode 100755 index db2987a24686..711b88e2b3d1 --- a/include/litmus/litmus.h +++ b/include/litmus/litmus.h @@ -32,6 +32,7 @@ struct task_struct* __waitqueue_remove_first(wait_queue_head_t *wq); #define NO_CPU 0xffffffff void litmus_fork(struct task_struct *tsk); +void litmus_post_fork_thread(struct task_struct *tsk); void litmus_exec(void); /* clean up real-time state of a task */ void exit_litmus(struct task_struct *dead_tsk); diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h old mode 100644 new mode 100755 index cb7c3ac64339..aca78a835529 --- a/include/litmus/rt_param.h +++ b/include/litmus/rt_param.h @@ -41,6 +41,12 @@ typedef enum { PRECISE_SIGNALS, /* budget signals are triggered with hrtimers */ } budget_signal_policy_t; +typedef enum { + AUX_ENABLE = 0x1, + AUX_CURRENT = (AUX_ENABLE<<1), + AUX_FUTURE = (AUX_CURRENT<<2) +} aux_flags_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, @@ -370,6 +376,7 @@ struct aux_data struct list_head aux_tasks; struct binheap aux_task_owners; unsigned int initialized:1; + unsigned int aux_future:1; }; #endif diff --git a/kernel/fork.c b/kernel/fork.c index 25c6111fe3a6..7491c4f5e78c 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -1370,8 +1370,12 @@ static struct task_struct *copy_process(unsigned long clone_flags, write_unlock_irq(&tasklist_lock); proc_fork_connector(p); cgroup_post_fork(p); - if (clone_flags & CLONE_THREAD) + if (clone_flags & CLONE_THREAD) { threadgroup_fork_read_unlock(current); +#ifdef CONFIG_REALTIME_AUX_TASKS + litmus_post_fork_thread(p); +#endif + } perf_event_fork(p); return p; diff --git a/litmus/aux_tasks.c b/litmus/aux_tasks.c index bd7bcbed58fe..e5f3c82d32e9 100755 --- a/litmus/aux_tasks.c +++ b/litmus/aux_tasks.c @@ -25,7 +25,7 @@ static int admit_aux_task(struct task_struct *t) struct rt_task tp = { .period = 1000000, /* 1ms */ .relative_deadline = 1000000, - .exec_cost = 1000000, /* allow full utilization */ + .exec_cost = 1000000, /* allow full utilization with buget tracking */ .phase = 0, .cpu = task_cpu(leader), /* take CPU of group leader */ .budget_policy = QUANTUM_ENFORCEMENT, @@ -44,17 +44,15 @@ static int admit_aux_task(struct task_struct *t) int exit_aux_task(struct task_struct *t) { int retval = 0; - struct task_struct *leader = t->group_leader; BUG_ON(!tsk_rt(t)->is_aux_task); - TRACE_CUR("Aux task %s/%d is exiting from %s/%d.\n", t->comm, t->pid, leader->comm, leader->pid); + TRACE_CUR("Aux task %s/%d is exiting from %s/%d.\n", t->comm, t->pid, t->group_leader->comm, t->group_leader->pid); + tsk_rt(t)->is_aux_task = 0; + #ifdef CONFIG_REALTIME_AUX_TASK_PRIORITY_INHERITANCE list_del(&tsk_rt(t)->aux_task_node); - - tsk_rt(t)->is_aux_task = 0; - if (tsk_rt(t)->inh_task) { litmus->__decrease_prio(t, NULL); } @@ -80,10 +78,14 @@ static int aux_tasks_increase_priority(struct task_struct *leader, struct task_s if (!is_realtime(aux)) { TRACE_CUR("skipping non-real-time aux task %s/%d\n", aux->comm, aux->pid); } - - // aux tasks don't touch rt locks, so no nested call needed. - TRACE_CUR("increasing %s/%d.\n", aux->comm, aux->pid); - retval = litmus->__increase_prio(aux, hp); + else if(tsk_rt(aux)->inh_task == hp) { + TRACE_CUR("skipping real-time aux task %s/%d that already inherits from %s/%d\n", aux->comm, aux->pid, hp->comm, hp->pid); + } + else { + // aux tasks don't touch rt locks, so no nested call needed. + TRACE_CUR("increasing %s/%d.\n", aux->comm, aux->pid); + retval = litmus->__increase_prio(aux, hp); + } } #endif @@ -208,6 +210,54 @@ out: return retval; } +int make_aux_task_if_required(struct task_struct *t) +{ + struct task_struct *leader; + int retval = 0; + + read_lock_irq(&tasklist_lock); + + leader = t->group_leader; + + if(!tsk_aux(leader)->initialized || !tsk_aux(leader)->aux_future) { + goto out; + } + + TRACE_CUR("Making %s/%d in %s/%d an aux thread.\n", t->comm, t->pid, leader->comm, leader->pid); + + INIT_LIST_HEAD(&tsk_rt(t)->aux_task_node); + INIT_BINHEAP_NODE(&tsk_rt(t)->aux_task_owner_node); + + retval = admit_aux_task(t); + if (retval == 0) { + tsk_rt(t)->is_aux_task = 1; + +#ifdef CONFIG_REALTIME_AUX_TASK_PRIORITY_INHERITANCE + list_add_tail(&tsk_rt(t)->aux_task_node, &tsk_aux(leader)->aux_tasks); + + if (!binheap_empty(&tsk_aux(leader)->aux_task_owners)) { + struct task_struct *hp = + container_of(binheap_top_entry(&tsk_aux(leader)->aux_task_owners, struct rt_param, aux_task_owner_node), + struct task_struct, rt_param); + + TRACE_CUR("hp in group: %s/%d\n", hp->comm, hp->pid); + + retval = litmus->__increase_prio(t, (tsk_rt(hp)->inh_task)? tsk_rt(hp)->inh_task : hp); + + if (retval != 0) { + /* don't know how to recover from bugs with prio inheritance. better just crash. */ + read_unlock_irq(&tasklist_lock); + BUG(); + } + } +#endif + } + +out: + read_unlock_irq(&tasklist_lock); + + return retval; +} long enable_aux_task_owner(struct task_struct *t) @@ -313,11 +363,12 @@ static int aux_task_owner_max_priority_order(struct binheap_node *a, } -static long __do_enable_aux_tasks(void) +static long __do_enable_aux_tasks(int flags) { long retval = 0; struct task_struct *leader; struct task_struct *t; + int aux_tasks_added = 0; leader = current->group_leader; @@ -327,34 +378,52 @@ static long __do_enable_aux_tasks(void) tsk_aux(leader)->initialized = 1; } + if (flags & AUX_FUTURE) { + tsk_aux(leader)->aux_future = 1; + } + t = leader; do { - /* doesn't hurt to initialize them both */ - INIT_LIST_HEAD(&tsk_rt(t)->aux_task_node); - INIT_BINHEAP_NODE(&tsk_rt(t)->aux_task_owner_node); + if (!tsk_rt(t)->has_aux_tasks && !tsk_rt(t)->is_aux_task) { + /* This may harmlessly reinit unused nodes. TODO: Don't reinit already init nodes. */ + /* doesn't hurt to initialize both nodes */ + INIT_LIST_HEAD(&tsk_rt(t)->aux_task_node); + INIT_BINHEAP_NODE(&tsk_rt(t)->aux_task_owner_node); + } TRACE_CUR("Checking task in %s/%d: %s/%d = (p = %llu):\n", leader->comm, leader->pid, t->comm, t->pid, tsk_rt(t)->task_params.period); - - /* inspect heap_node to see if it is an rt task */ + + /* inspect period to see if it is an rt task */ if (tsk_rt(t)->task_params.period == 0) { - if (!tsk_rt(t)->is_aux_task) { - TRACE_CUR("AUX task in %s/%d: %s/%d:\n", leader->comm, leader->pid, t->comm, t->pid); - /* hasn't been aux_tasks_increase_priorityted into rt. make it a aux. */ - tsk_rt(t)->is_aux_task = 1; - + if (flags && AUX_CURRENT) { + if (!tsk_rt(t)->is_aux_task) { + int admit_ret; + + TRACE_CUR("AUX task in %s/%d: %s/%d:\n", leader->comm, leader->pid, t->comm, t->pid); + + admit_ret = admit_aux_task(t); + + if (admit_ret == 0) { + /* hasn't been aux_tasks_increase_priorityted into rt. make it a aux. */ + tsk_rt(t)->is_aux_task = 1; + aux_tasks_added = 1; + #ifdef CONFIG_REALTIME_AUX_TASK_PRIORITY_INHERITANCE - list_add_tail(&tsk_rt(t)->aux_task_node, &tsk_aux(leader)->aux_tasks); + list_add_tail(&tsk_rt(t)->aux_task_node, &tsk_aux(leader)->aux_tasks); #endif - - (void)admit_aux_task(t); + } + } + else { + TRACE_CUR("AUX task in %s/%d is already set up: %s/%d\n", leader->comm, leader->pid, t->comm, t->pid); + } } else { - TRACE_CUR("AUX task in %s/%d is already set up: %s/%d\n", leader->comm, leader->pid, t->comm, t->pid); + TRACE_CUR("Not changing thread in %s/%d to AUX task: %s/%d\n", leader->comm, leader->pid, t->comm, t->pid); } } - else { + else if (!tsk_rt(t)->is_aux_task) { /* don't let aux tasks get aux tasks of their own */ if (!tsk_rt(t)->has_aux_tasks) { TRACE_CUR("task in %s/%d: %s/%d:\n", leader->comm, leader->pid, t->comm, t->pid); tsk_rt(t)->has_aux_tasks = 1; @@ -369,19 +438,18 @@ static long __do_enable_aux_tasks(void) #ifdef CONFIG_REALTIME_AUX_TASK_PRIORITY_INHERITANCE - if (!binheap_empty(&tsk_aux(leader)->aux_task_owners)) { + if (aux_tasks_added && !binheap_empty(&tsk_aux(leader)->aux_task_owners)) { struct task_struct *hp = container_of(binheap_top_entry(&tsk_aux(leader)->aux_task_owners, struct rt_param, aux_task_owner_node), struct task_struct, rt_param); - TRACE_CUR("found hp in group: %s/%d\n", hp->comm, hp->pid); - retval = aux_tasks_increase_priority(leader, - (tsk_rt(hp)->inh_task)? tsk_rt(hp)->inh_task : hp); + TRACE_CUR("hp in group: %s/%d\n", hp->comm, hp->pid); + retval = aux_tasks_increase_priority(leader, (tsk_rt(hp)->inh_task)? tsk_rt(hp)->inh_task : hp); } #endif return retval; } -static long __do_disable_aux_tasks(void) +static long __do_disable_aux_tasks(int flags) { long retval = 0; struct task_struct *leader; @@ -389,50 +457,56 @@ static long __do_disable_aux_tasks(void) leader = current->group_leader; - t = leader; - do { - if (tsk_rt(t)->is_aux_task) { - - TRACE_CUR("%s/%d is an aux task.\n", t->comm, t->pid); - - if (is_realtime(t)) { - long temp_retval; - struct sched_param param = { .sched_priority = 0}; - - TRACE_CUR("%s/%d is real-time. Changing policy to SCHED_NORMAL.\n", t->comm, t->pid); - - temp_retval = sched_setscheduler_nocheck(t, SCHED_NORMAL, ¶m); - - if (temp_retval != 0) { - TRACE_CUR("error changing policy of %s/%d to SCHED_NORMAL\n", t->comm, t->pid); - if (retval == 0) { - retval = temp_retval; - } - else { - TRACE_CUR("prior error (%d) masks new error (%d)\n", retval, temp_retval); + if (flags & AUX_FUTURE) { + tsk_aux(leader)->aux_future = 0; + } + + if (flags & AUX_CURRENT) { + t = leader; + do { + if (tsk_rt(t)->is_aux_task) { + + TRACE_CUR("%s/%d is an aux task.\n", t->comm, t->pid); + + if (is_realtime(t)) { + long temp_retval; + struct sched_param param = { .sched_priority = 0}; + + TRACE_CUR("%s/%d is real-time. Changing policy to SCHED_NORMAL.\n", t->comm, t->pid); + + temp_retval = sched_setscheduler_nocheck(t, SCHED_NORMAL, ¶m); + + if (temp_retval != 0) { + TRACE_CUR("error changing policy of %s/%d to SCHED_NORMAL\n", t->comm, t->pid); + if (retval == 0) { + retval = temp_retval; + } + else { + TRACE_CUR("prior error (%d) masks new error (%d)\n", retval, temp_retval); + } } } - } - tsk_rt(t)->is_aux_task = 0; - } - t = next_thread(t); - } while(t != leader); + tsk_rt(t)->is_aux_task = 0; + } + t = next_thread(t); + } while(t != leader); + } return retval; } -asmlinkage long sys_set_aux_tasks(int enable) +asmlinkage long sys_set_aux_tasks(int flags) { long retval; read_lock_irq(&tasklist_lock); - if (enable) { - retval = __do_enable_aux_tasks(); + if (flags & AUX_ENABLE) { + retval = __do_enable_aux_tasks(flags); } else { - retval = __do_disable_aux_tasks(); + retval = __do_disable_aux_tasks(flags); } read_unlock_irq(&tasklist_lock); @@ -442,7 +516,7 @@ asmlinkage long sys_set_aux_tasks(int enable) #else -asmlinkage long sys_set_aux_tasks(int enable) +asmlinkage long sys_set_aux_tasks(int flags) { printk("Unsupported. Recompile with CONFIG_REALTIME_AUX_TASKS.\n"); return -EINVAL; diff --git a/litmus/edf_common.c b/litmus/edf_common.c index 5a3f5b417f73..c279bf12a7f5 100755 --- a/litmus/edf_common.c +++ b/litmus/edf_common.c @@ -22,7 +22,7 @@ #include #endif -#if defined(CONFIG_EDF_TIE_BREAK_HASH) || defined(CONFIG_REALTIME_AUX_TASKS) +#if defined(CONFIG_EDF_TIE_BREAK_HASH) #include static inline long edf_hash(struct task_struct *t) { @@ -43,23 +43,6 @@ static inline long edf_hash(struct task_struct *t) } #endif -#ifdef CONFIG_REALTIME_AUX_TASK_PRIORITY_INHERITANCE -int aux_tie_break(struct task_struct *first, struct task_struct *second) -{ - long fhash = edf_hash(first); - long shash = edf_hash(second); - if (fhash < shash) { - TRACE_CUR("%s/%d >> %s/%d --- %d\n", first->comm, first->pid, second->comm, second->pid, 1); - return 1; - } - else if(fhash == shash) { - TRACE_CUR("%s/%d >> %s/%d --- %d\n", first->comm, first->pid, second->comm, second->pid, (first->pid < second->pid)); - return first->pid < second->pid; - } - return 0; -} -#endif - /* edf_higher_prio - returns true if first has a higher EDF priority * than second. Deadline ties are broken by PID. @@ -93,44 +76,47 @@ int edf_higher_prio(struct task_struct* first, struct task_struct* second) #if defined(CONFIG_REALTIME_AUX_TASK_PRIORITY_BOOSTED) /* run aux tasks at max priority */ + /* TODO: Actually use prio-boosting. */ if (first->rt_param.is_aux_task != second->rt_param.is_aux_task) { return (first->rt_param.is_aux_task > second->rt_param.is_aux_task); } else if(first->rt_param.is_aux_task && second->rt_param.is_aux_task) { + if(first->group_leader == second->group_leader) { + TRACE_CUR("aux tie break!\n"); // tie-break by BASE priority of the aux tasks + goto aux_tie_break; + } first = first->group_leader; second = second->group_leader; } #elif defined(CONFIG_REALTIME_AUX_TASK_PRIORITY_INHERITANCE) { - int first_lo_aux, second_lo_aux; - int first_hi_aux, second_hi_aux; - first_lo_aux = first->rt_param.is_aux_task && !first->rt_param.inh_task; - second_lo_aux = second->rt_param.is_aux_task && !second->rt_param.inh_task; - - if (first_lo_aux && !second_lo_aux) { - TRACE_CUR("%s/%d >> %s/%d --- 0\n", first->comm, first->pid, second->comm, second->pid); - return 0; - } - else if (second_lo_aux && !first_lo_aux) { - TRACE_CUR("%s/%d >> %s/%d --- 1\n", first->comm, first->pid, second->comm, second->pid); - return 1; - } - else if (first_lo_aux && second_lo_aux) { - int aux_lo_tie_break = aux_tie_break(first, second); - TRACE_CUR("low aux tie break: %s/%d >> %s/%d --- %d\n", first->comm, first->pid, second->comm, second->pid, aux_lo_tie_break); - return aux_lo_tie_break; - } - - first_hi_aux = first->rt_param.is_aux_task && first->rt_param.inh_task; - second_hi_aux = second->rt_param.is_aux_task && second->rt_param.inh_task; - - if (first_hi_aux && second_hi_aux && first->rt_param.inh_task == second->rt_param.inh_task) { - int aux_hi_tie_break = aux_tie_break(first, second); - TRACE_CUR("hi aux tie break: %s/%d >> %s/%d --- %d\n", first->comm, first->pid, second->comm, second->pid, aux_hi_tie_break); - return aux_hi_tie_break; - } + int first_lo_aux = first->rt_param.is_aux_task && !first->rt_param.inh_task; + int second_lo_aux = second->rt_param.is_aux_task && !second->rt_param.inh_task; + + /* prioritize aux tasks without inheritance below real-time tasks */ + if (first_lo_aux || second_lo_aux) { + // one of these is an aux task without inheritance. + if(first_lo_aux && second_lo_aux) { + TRACE_CUR("aux tie break!\n"); // tie-break by BASE priority of the aux tasks + goto aux_tie_break; + } + else { + // make the aux thread lowest priority real-time task + int temp = (first_lo_aux) ? !is_realtime(second) : !is_realtime(first); + TRACE_CUR("%s/%d >> %s/%d --- %d\n", first->comm, first->pid, second->comm, second->pid, temp); + return temp; + } + } + + if (first->rt_param.is_aux_task && second->rt_param.is_aux_task && + first->rt_param.inh_task == second->rt_param.inh_task) { // inh_task is !NULL for both tasks since neither was a lo_aux task + // Both aux tasks inherit from the same task, so tie-break + // by base priority of the aux tasks. + TRACE_CUR("aux tie break!\n"); + goto aux_tie_break; + } } #endif @@ -174,6 +160,8 @@ int edf_higher_prio(struct task_struct* first, struct task_struct* second) #endif +aux_tie_break: + if (!is_realtime(second_task)) { return 1; } diff --git a/litmus/litmus.c b/litmus/litmus.c old mode 100644 new mode 100755 index cfd14852502b..8bc159b2fcce --- a/litmus/litmus.c +++ b/litmus/litmus.c @@ -634,6 +634,14 @@ void litmus_fork(struct task_struct* p) p->od_table = NULL; } +/* Called right before copy_process() returns a forked thread. */ +void litmus_post_fork_thread(struct task_struct* p) +{ +#ifdef CONFIG_REALTIME_AUX_TASKS + make_aux_task_if_required(p); +#endif +} + /* Called upon execve(). * current is doing the exec. * Don't let address space specific stuff leak. -- cgit v1.2.2