From 4e28e863475df7c27c2e9ecba4e2cdd409bf044e Mon Sep 17 00:00:00 2001 From: Glenn Elliott Date: Fri, 22 Mar 2013 15:13:17 -0400 Subject: work in progress. --- include/litmus/bheap.h | 7 +++ include/litmus/budget.h | 7 +++ include/litmus/rt_param.h | 2 + litmus/bheap.c | 12 +++++ litmus/budget.c | 24 +++++++++ litmus/sched_cedf.c | 126 ++++++++++++++++++++++++++++++++++------------ litmus/sched_gsn_edf.c | 3 ++ litmus/sched_pfp.c | 3 ++ litmus/sched_psn_edf.c | 3 ++ 9 files changed, 156 insertions(+), 31 deletions(-) diff --git a/include/litmus/bheap.h b/include/litmus/bheap.h index cf4864a498d8..49f7e44bc0a5 100644 --- a/include/litmus/bheap.h +++ b/include/litmus/bheap.h @@ -24,6 +24,8 @@ struct bheap { * This speeds up repeated peek operations. */ struct bheap_node* min; + +// unsigned int size; }; typedef int (*bheap_prio_t)(struct bheap_node* a, struct bheap_node* b); @@ -41,6 +43,11 @@ static inline int bheap_empty(struct bheap* heap) return heap->head == NULL && heap->min == NULL; } +//static inline unsigned int bheap_size(struct bheap* heap) +//{ +// return heap->size; +//} + /* insert (and reinitialize) a node into the heap */ void bheap_insert(bheap_prio_t higher_prio, struct bheap* heap, diff --git a/include/litmus/budget.h b/include/litmus/budget.h index 72f04777e0b0..4f1bdd101a9e 100644 --- a/include/litmus/budget.h +++ b/include/litmus/budget.h @@ -58,6 +58,8 @@ typedef void (*preempt_t)(struct task_struct* t); typedef void (*sleep_t)(struct task_struct* t); typedef enum hrtimer_restart (*exhausted_t)(struct task_struct* t); typedef void (*exit_t)(struct task_struct* t); +typedef void (*inherit_t)(struct task_struct* t, struct task_struct* prio_inh); +typedef void (*disinherit_t)(struct task_struct* t, struct task_struct* prio_inh); struct budget_tracker_ops { @@ -69,6 +71,9 @@ struct budget_tracker_ops exit_t on_exit; /* task exiting rt mode */ exhausted_t on_exhausted; /* called by plugin::tick() or timer interrupt */ + + inherit_t on_inherit; + disinherit_t on_disinherit; }; struct budget_tracker @@ -108,6 +113,8 @@ void sobliv_on_sleep(struct task_struct* t); /* Use the DRAIN_SIMPLE implementations */ #define sobliv_on_preempt simple_on_preempt #define sobliv_on_exit simple_on_exit +void sobliv_on_inherit(struct task_struct* t, struct task_struct* prio_inh); +void sobliv_on_disinherit(struct task_struct* t, struct task_struct* prio_inh); void init_budget_tracker(struct budget_tracker* bt, diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h index 499ecd899fcd..40bdb26faebe 100644 --- a/include/litmus/rt_param.h +++ b/include/litmus/rt_param.h @@ -422,6 +422,8 @@ struct rt_param { */ struct task_struct* inh_task; + struct task_struct* inh_task_linkback; + #ifdef CONFIG_REALTIME_AUX_TASKS unsigned int is_aux_task:1; unsigned int aux_ready:1; diff --git a/litmus/bheap.c b/litmus/bheap.c index 528af97f18a6..45e1db36fa36 100644 --- a/litmus/bheap.c +++ b/litmus/bheap.c @@ -5,6 +5,8 @@ void bheap_init(struct bheap* heap) { heap->head = NULL; heap->min = NULL; + +// heap->size = 0; } void bheap_node_init(struct bheap_node** _h, void* value) @@ -173,6 +175,8 @@ void bheap_insert(bheap_prio_t higher_prio, struct bheap* heap, heap->min = node; } else __bheap_union(higher_prio, heap, node); + +// ++heap->size; } void bheap_uncache_min(bheap_prio_t higher_prio, struct bheap* heap) @@ -195,6 +199,8 @@ void bheap_union(bheap_prio_t higher_prio, __bheap_union(higher_prio, target, addition->head); /* this is a destructive merge */ addition->head = NULL; + +// target->size += addition->size; } struct bheap_node* bheap_peek(bheap_prio_t higher_prio, @@ -215,6 +221,9 @@ struct bheap_node* bheap_take(bheap_prio_t higher_prio, heap->min = NULL; if (node) node->degree = NOT_IN_HEAP; + +// --heap->size; + return node; } @@ -286,7 +295,10 @@ void bheap_delete(bheap_prio_t higher_prio, struct bheap* heap, __bheap_union(higher_prio, heap, __bheap_reverse(node->child)); } else heap->min = NULL; + node->degree = NOT_IN_HEAP; + +// --heap->size; } /* allocate a heap node for value and insert into the heap */ diff --git a/litmus/budget.c b/litmus/budget.c index 15de83bc584e..91755cf2787c 100644 --- a/litmus/budget.c +++ b/litmus/budget.c @@ -171,6 +171,11 @@ void sobliv_on_scheduled(struct task_struct* t) arm_enforcement_timer(t); } } + + if (tsk_rt(t)->inh_task) { + BUG_ON(is_running(tsk_rt(t)->inh_task)); + tsk_rt(tsk_rt(t)->inh_task)->inh_task_linkback = t; + } } void sobliv_on_blocked(struct task_struct* t) @@ -196,6 +201,25 @@ void sobliv_on_sleep(struct task_struct* t) } } +void sobliv_on_inherit(struct task_struct* t, struct task_struct* prio_inh) +{ + BUG_ON(!prio_inh); + + if (budget_precisely_tracked(t)) { + TRACE_TASK(t, "inheriting from %s/%d. stop draining own budget.\n", + prio_inh->comm, prio_inh->pid); + cancel_enforcement_timer(t); + } +} + +void sobliv_on_disinherit(struct task_struct* t, struct task_struct* prio_inh) +{ + if (!prio_inh && budget_precisely_tracked(t)) { + TRACE_TASK(t, "assuming base priority. start draining own budget.\n"); + arm_enforcement_timer(t); + } +} + static enum hrtimer_restart __on_timeout(struct hrtimer *timer) { diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c index fd1b80ac6090..64e04405dd32 100644 --- a/litmus/sched_cedf.c +++ b/litmus/sched_cedf.c @@ -440,6 +440,7 @@ static noinline void job_completion(struct task_struct *t, int forced) ++get_backlog(t); TRACE_TASK(t, "adding backlogged job\n"); } + do_backlogged_job = has_backlog(t); TRACE_TASK(t, "number of backlogged jobs: %u\n", get_backlog(t)); @@ -457,15 +458,20 @@ static noinline void job_completion(struct task_struct *t, int forced) tsk_rt(t)->completed = 1; if (!forced && do_backlogged_job) { - /* don't advance deadline/refresh budget. use the remaining budget for - * the backlogged job. */ + /* Don't advance deadline/refresh budget. Use the remaining budget for + * the backlogged job. + * + * NOTE: Allowing backlogged jobs comsume remaining budget may affet + * blocking bound analysis. + */ } else { + prepare_for_next_period(t); + if (do_backlogged_job) { - TRACE_TASK(t, "refreshing budget with early release for backlogged job.\n"); + TRACE_TASK(t, "refreshing budget with early " + "release for backlogged job.\n"); } - - prepare_for_next_period(t); } do_release = (is_early_releasing(t) || is_released(t, now)); @@ -570,35 +576,76 @@ static enum hrtimer_restart cedf_sobliv_on_exhausted(struct task_struct *t) litmus_reschedule(cpu); } else { - BUG_ON(cpu != NO_CPU); -#ifdef CONFIG_LITMUS_LOCKING - if (holds_locks(t)) { - /* TODO: Integration with Litmus locking protocols */ - TRACE_TASK(t, "prevented lock holder from postponing deadline.\n"); - } - else { -#endif - /* force job completion */ - cedf_domain_t* cluster = task_cpu_cluster(t); - unsigned long flags; - lt_t remaining; + cedf_domain_t* cluster = task_cpu_cluster(t); + unsigned long flags; + lt_t remaining; - TRACE_TASK(t, "blocked, postponing deadline\n"); - raw_spin_lock_irqsave(&cluster->cluster_lock, flags); - job_completion(t, 1); /* refreshes budget */ - - hrtimer_forward_now(&get_budget_timer(t).timer.timer, - ns_to_ktime(budget_remaining(t))); - remaining = hrtimer_get_expires_ns(&get_budget_timer(t).timer.timer); - - raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags); + BUG_ON(cpu != NO_CPU); - TRACE_TASK(t, "rearmed timer to %ld\n", remaining); - restart = HRTIMER_RESTART; -#ifdef CONFIG_LITMUS_LOCKING - } -#endif + // 1) refresh budget through job completion + // 2) if holds locks, tell the locking protocol to re-eval priority + // 3) -- the LP must undo any inheritance relations if appropriate + + + /* force job completion */ + TRACE_TASK(t, "blocked, postponing deadline\n"); + + raw_spin_lock_irqsave(&cluster->cluster_lock, flags); + job_completion(t, 1); /* refreshes budget */ + + +//#ifdef CONFIG_LITMUS_LOCKING +// if (tsk_rt(t))->inh_task) { +// /* change in base-priority is masked */ +// } +// else { +//#ifdef CONFIG_LITMUS_NESTED_LOCKING +// struct litmus_lock *blocked_lock; +// +// raw_spin_lock(&tsk_rt(t)->hp_blocked_tasks_lock); +// if (holds_locks(t)) { +// struct task_struct* hp_blocked = top_priority(&tsk_rt(t)->hp_blocked_tasks); +// if (litmus->compare(hp_blocked, t)) +// __increase_priority_inheritance(t, effective_priority(hp_blocked)); +// } +// +// blocked_lock = tsk_rt(t)->blocked_lock; +// if(blocked_lock) { +// if(blocked_lock->ops->supports_nesting) { +// TRACE_TASK(t, "Inheritor is blocked (...perhaps). Checking lock %d.\n", +// blocked_lock->ident); +// +// // beware: recursion +// blocked_lock->ops->propagate_decrease_inheritance(blocked_lock, t, +// to_unlock, +// irqflags); +// } +// else { +// TRACE_TASK(t, "Inheritor is blocked on lock (%p) that does not support nesting!\n", +// blocked_lock); +// unlock_fine_irqrestore(to_unlock, irqflags); +// } +// } +// else { +// TRACE_TASK(t, "is not blocked. No propagation.\n"); +// unlock_fine_irqrestore(to_unlock, irqflags); +// } +//#endif +// } +//#endif + + hrtimer_forward_now(&get_budget_timer(t).timer.timer, + ns_to_ktime(budget_remaining(t))); + remaining = hrtimer_get_expires_ns(&get_budget_timer(t).timer.timer); + + raw_spin_unlock_irqrestore(&cluster->cluster_lock, flags); + + + + + TRACE_TASK(t, "rearmed timer to %ld\n", remaining); + restart = HRTIMER_RESTART; } } } @@ -1297,6 +1344,9 @@ static struct budget_tracker_ops cedf_drain_simple_ops = .on_exit = simple_on_exit, .on_exhausted = cedf_simple_on_exhausted, + + .on_inherit = NULL, + .on_disinherit = NULL, }; static struct budget_tracker_ops cedf_drain_sobliv_ops = @@ -1308,6 +1358,9 @@ static struct budget_tracker_ops cedf_drain_sobliv_ops = .on_exit = sobliv_on_exit, .on_exhausted = cedf_sobliv_on_exhausted, + + .on_inherit = sobliv_on_inherit, + .on_disinherit = sobliv_on_disinherit, }; static long cedf_admit_task(struct task_struct* tsk) @@ -1411,6 +1464,11 @@ static int __increase_priority_inheritance(struct task_struct* t, #endif sched_trace_eff_prio_change(t, prio_inh); + if (NULL != get_budget_timer(t).ops->on_inherit && + NULL != get_budget_timer(prio_inh).ops->on_inherit) { + get_budget_timer(t).ops->on_inherit(t, prio_inh); + } + TRACE_TASK(t, "inherits priority from %s/%d\n", prio_inh->comm, prio_inh->pid); tsk_rt(t)->inh_task = prio_inh; @@ -1575,6 +1633,12 @@ static int __decrease_priority_inheritance(struct task_struct* t, } #endif + if (NULL != tsk_rt(t)->inh_task && + NULL != get_budget_timer(t).ops->on_disinherit && + NULL != get_budget_timer(tsk_rt(t)->inh_task).ops->on_disinherit) { + get_budget_timer(t).ops->on_disinherit(t, tsk_rt(t)->inh_task); + } + #ifdef CONFIG_LITMUS_NESTED_LOCKING if(__edf_higher_prio(t, EFFECTIVE, prio_inh, BASE)) { #endif diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c index 2950e39b054e..821e96cd4ec9 100644 --- a/litmus/sched_gsn_edf.c +++ b/litmus/sched_gsn_edf.c @@ -1131,6 +1131,9 @@ static struct budget_tracker_ops gsnedf_drain_simple_ops = .on_exit = simple_on_exit, .on_exhausted = gsnedf_simple_on_exhausted, + + .on_inherit = NULL, + .on_disinherit = NULL, }; static long gsnedf_admit_task(struct task_struct* tsk) diff --git a/litmus/sched_pfp.c b/litmus/sched_pfp.c index 33f861ab0056..3ff131e58553 100644 --- a/litmus/sched_pfp.c +++ b/litmus/sched_pfp.c @@ -1722,6 +1722,9 @@ static struct budget_tracker_ops pfp_drain_simple_ops = .on_exit = simple_on_exit, .on_exhausted = pfp_simple_on_exhausted, + + .on_inherit = NULL, + .on_disinherit = NULL, }; static long pfp_admit_task(struct task_struct* tsk) diff --git a/litmus/sched_psn_edf.c b/litmus/sched_psn_edf.c index c06db8b434cd..720a733aff9e 100644 --- a/litmus/sched_psn_edf.c +++ b/litmus/sched_psn_edf.c @@ -656,6 +656,9 @@ static struct budget_tracker_ops psnedf_drain_simple_ops = .on_exit = simple_on_exit, .on_exhausted = psnedf_simple_on_exhausted, + + .on_inherit = NULL, + .on_disinherit = NULL, }; static long psnedf_admit_task(struct task_struct* tsk) -- cgit v1.2.2