From 58e2d4ca581167c2a079f4ee02be2f0bc52e8729 Mon Sep 17 00:00:00 2001 From: Srivatsa Vaddagiri Date: Fri, 25 Jan 2008 21:08:00 +0100 Subject: sched: group scheduling, change how cpu load is calculated This patch changes how the cpu load exerted by fair_sched_class tasks is calculated. Load exerted by fair_sched_class tasks on a cpu is now a summation of the group weights, rather than summation of task weights. Weight exerted by a group on a cpu is dependent on the shares allocated to it. This version of patch has a minor impact on code size, but should have no runtime/functional impact for !CONFIG_FAIR_GROUP_SCHED. Signed-off-by: Srivatsa Vaddagiri Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 2 ++ 1 file changed, 2 insertions(+) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 9ba3daa03475..cefcd5105146 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -32,6 +32,7 @@ static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup) list_add_tail(&p->run_list, array->queue + p->prio); __set_bit(p->prio, array->bitmap); + inc_cpu_load(rq, p->se.load.weight); } /* @@ -46,6 +47,7 @@ static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep) list_del(&p->run_list); if (list_empty(array->queue + p->prio)) __clear_bit(p->prio, array->bitmap); + dec_cpu_load(rq, p->se.load.weight); } /* -- cgit v1.2.3-59-g8ed1b From 63489e45e265f64c368882be1f01c42dec5d984c Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:03 +0100 Subject: sched: count # of queued RT tasks This patch adds accounting to keep track of the number of RT tasks running on a runqueue. This information will be used in later patches. Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched.c | 1 + kernel/sched_rt.c | 17 +++++++++++++++++ 2 files changed, 18 insertions(+) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched.c b/kernel/sched.c index 5b3d46574eeb..9dd8d121eea6 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -342,6 +342,7 @@ struct rt_rq { struct rt_prio_array active; int rt_load_balance_idx; struct list_head *rt_load_balance_head, *rt_load_balance_curr; + unsigned long rt_nr_running; }; /* diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index cefcd5105146..e3d2ca8832af 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -26,6 +26,19 @@ static void update_curr_rt(struct rq *rq) cpuacct_charge(curr, delta_exec); } +static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq) +{ + WARN_ON(!rt_task(p)); + rq->rt.rt_nr_running++; +} + +static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq) +{ + WARN_ON(!rt_task(p)); + WARN_ON(!rq->rt.rt_nr_running); + rq->rt.rt_nr_running--; +} + static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup) { struct rt_prio_array *array = &rq->rt.active; @@ -33,6 +46,8 @@ static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup) list_add_tail(&p->run_list, array->queue + p->prio); __set_bit(p->prio, array->bitmap); inc_cpu_load(rq, p->se.load.weight); + + inc_rt_tasks(p, rq); } /* @@ -48,6 +63,8 @@ static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep) if (list_empty(array->queue + p->prio)) __clear_bit(p->prio, array->bitmap); dec_cpu_load(rq, p->se.load.weight); + + dec_rt_tasks(p, rq); } /* -- cgit v1.2.3-59-g8ed1b From 764a9d6fe4b52995c8aba277e3634385699354f4 Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:04 +0100 Subject: sched: track highest prio task queued This patch adds accounting to each runqueue to keep track of the highest prio task queued on the run queue. We only care about RT tasks, so if the run queue does not contain any active RT tasks its priority will be considered MAX_RT_PRIO. This information will be used for later patches. Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched.c | 3 +++ kernel/sched_rt.c | 18 ++++++++++++++++++ 2 files changed, 21 insertions(+) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched.c b/kernel/sched.c index 9dd8d121eea6..6185fa080ec8 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -343,6 +343,8 @@ struct rt_rq { int rt_load_balance_idx; struct list_head *rt_load_balance_head, *rt_load_balance_curr; unsigned long rt_nr_running; + /* highest queued rt task prio */ + int highest_prio; }; /* @@ -6864,6 +6866,7 @@ void __init sched_init(void) rq->cpu = i; rq->migration_thread = NULL; INIT_LIST_HEAD(&rq->migration_queue); + rq->rt.highest_prio = MAX_RT_PRIO; #endif atomic_set(&rq->nr_iowait, 0); diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index e3d2ca8832af..136c2857a049 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -30,6 +30,10 @@ static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq) { WARN_ON(!rt_task(p)); rq->rt.rt_nr_running++; +#ifdef CONFIG_SMP + if (p->prio < rq->rt.highest_prio) + rq->rt.highest_prio = p->prio; +#endif /* CONFIG_SMP */ } static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq) @@ -37,6 +41,20 @@ static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq) WARN_ON(!rt_task(p)); WARN_ON(!rq->rt.rt_nr_running); rq->rt.rt_nr_running--; +#ifdef CONFIG_SMP + if (rq->rt.rt_nr_running) { + struct rt_prio_array *array; + + WARN_ON(p->prio < rq->rt.highest_prio); + if (p->prio == rq->rt.highest_prio) { + /* recalculate */ + array = &rq->rt.active; + rq->rt.highest_prio = + sched_find_first_bit(array->bitmap); + } /* otherwise leave rq->highest prio alone */ + } else + rq->rt.highest_prio = MAX_RT_PRIO; +#endif /* CONFIG_SMP */ } static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup) -- cgit v1.2.3-59-g8ed1b From e8fa136262e1121288bb93befe2295928ffd240d Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:05 +0100 Subject: sched: add RT task pushing This patch adds an algorithm to push extra RT tasks off a run queue to other CPU runqueues. When more than one RT task is added to a run queue, this algorithm takes an assertive approach to push the RT tasks that are not running onto other run queues that have lower priority. The way this works is that the highest RT task that is not running is looked at and we examine the runqueues on the CPUS for that tasks affinity mask. We find the runqueue with the lowest prio in the CPU affinity of the picked task, and if it is lower in prio than the picked task, we push the task onto that CPU runqueue. We continue pushing RT tasks off the current runqueue until we don't push any more. The algorithm stops when the next highest RT task can't preempt any other processes on other CPUS. TODO: The algorithm may stop when there are still RT tasks that can be migrated. Specifically, if the highest non running RT task CPU affinity is restricted to CPUs that are running higher priority tasks, there may be a lower priority task queued that has an affinity with a CPU that is running a lower priority task that it could be migrated to. This patch set does not address this issue. Note: checkpatch reveals two over 80 character instances. I'm not sure that breaking them up will help visually, so I left them as is. Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched.c | 8 +- kernel/sched_rt.c | 225 +++++++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 231 insertions(+), 2 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched.c b/kernel/sched.c index 6185fa080ec8..97cab609fc31 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -1952,6 +1952,8 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev) prev_state = prev->state; finish_arch_switch(prev); finish_lock_switch(rq, prev); + schedule_tail_balance_rt(rq); + fire_sched_in_preempt_notifiers(current); if (mm) mmdrop(mm); @@ -2185,11 +2187,13 @@ static void double_rq_unlock(struct rq *rq1, struct rq *rq2) /* * double_lock_balance - lock the busiest runqueue, this_rq is locked already. */ -static void double_lock_balance(struct rq *this_rq, struct rq *busiest) +static int double_lock_balance(struct rq *this_rq, struct rq *busiest) __releases(this_rq->lock) __acquires(busiest->lock) __acquires(this_rq->lock) { + int ret = 0; + if (unlikely(!irqs_disabled())) { /* printk() doesn't work good under rq->lock */ spin_unlock(&this_rq->lock); @@ -2200,9 +2204,11 @@ static void double_lock_balance(struct rq *this_rq, struct rq *busiest) spin_unlock(&this_rq->lock); spin_lock(&busiest->lock); spin_lock(&this_rq->lock); + ret = 1; } else spin_lock(&busiest->lock); } + return ret; } /* diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 136c2857a049..7815e90b1147 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -137,6 +137,227 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p) } #ifdef CONFIG_SMP +/* Only try algorithms three times */ +#define RT_MAX_TRIES 3 + +static int double_lock_balance(struct rq *this_rq, struct rq *busiest); +static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep); + +/* Return the second highest RT task, NULL otherwise */ +static struct task_struct *pick_next_highest_task_rt(struct rq *rq) +{ + struct rt_prio_array *array = &rq->rt.active; + struct task_struct *next; + struct list_head *queue; + int idx; + + assert_spin_locked(&rq->lock); + + if (likely(rq->rt.rt_nr_running < 2)) + return NULL; + + idx = sched_find_first_bit(array->bitmap); + if (unlikely(idx >= MAX_RT_PRIO)) { + WARN_ON(1); /* rt_nr_running is bad */ + return NULL; + } + + queue = array->queue + idx; + next = list_entry(queue->next, struct task_struct, run_list); + if (unlikely(next != rq->curr)) + return next; + + if (queue->next->next != queue) { + /* same prio task */ + next = list_entry(queue->next->next, struct task_struct, run_list); + return next; + } + + /* slower, but more flexible */ + idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); + if (unlikely(idx >= MAX_RT_PRIO)) { + WARN_ON(1); /* rt_nr_running was 2 and above! */ + return NULL; + } + + queue = array->queue + idx; + next = list_entry(queue->next, struct task_struct, run_list); + + return next; +} + +static DEFINE_PER_CPU(cpumask_t, local_cpu_mask); + +/* Will lock the rq it finds */ +static struct rq *find_lock_lowest_rq(struct task_struct *task, + struct rq *this_rq) +{ + struct rq *lowest_rq = NULL; + int cpu; + int tries; + cpumask_t *cpu_mask = &__get_cpu_var(local_cpu_mask); + + cpus_and(*cpu_mask, cpu_online_map, task->cpus_allowed); + + for (tries = 0; tries < RT_MAX_TRIES; tries++) { + /* + * Scan each rq for the lowest prio. + */ + for_each_cpu_mask(cpu, *cpu_mask) { + struct rq *rq = &per_cpu(runqueues, cpu); + + if (cpu == this_rq->cpu) + continue; + + /* We look for lowest RT prio or non-rt CPU */ + if (rq->rt.highest_prio >= MAX_RT_PRIO) { + lowest_rq = rq; + break; + } + + /* no locking for now */ + if (rq->rt.highest_prio > task->prio && + (!lowest_rq || rq->rt.highest_prio > lowest_rq->rt.highest_prio)) { + lowest_rq = rq; + } + } + + if (!lowest_rq) + break; + + /* if the prio of this runqueue changed, try again */ + if (double_lock_balance(this_rq, lowest_rq)) { + /* + * We had to unlock the run queue. In + * the mean time, task could have + * migrated already or had its affinity changed. + * Also make sure that it wasn't scheduled on its rq. + */ + if (unlikely(task_rq(task) != this_rq || + !cpu_isset(lowest_rq->cpu, task->cpus_allowed) || + task_running(this_rq, task) || + !task->se.on_rq)) { + spin_unlock(&lowest_rq->lock); + lowest_rq = NULL; + break; + } + } + + /* If this rq is still suitable use it. */ + if (lowest_rq->rt.highest_prio > task->prio) + break; + + /* try again */ + spin_unlock(&lowest_rq->lock); + lowest_rq = NULL; + } + + return lowest_rq; +} + +/* + * If the current CPU has more than one RT task, see if the non + * running task can migrate over to a CPU that is running a task + * of lesser priority. + */ +static int push_rt_task(struct rq *this_rq) +{ + struct task_struct *next_task; + struct rq *lowest_rq; + int ret = 0; + int paranoid = RT_MAX_TRIES; + + assert_spin_locked(&this_rq->lock); + + next_task = pick_next_highest_task_rt(this_rq); + if (!next_task) + return 0; + + retry: + if (unlikely(next_task == this_rq->curr)) + return 0; + + /* + * It's possible that the next_task slipped in of + * higher priority than current. If that's the case + * just reschedule current. + */ + if (unlikely(next_task->prio < this_rq->curr->prio)) { + resched_task(this_rq->curr); + return 0; + } + + /* We might release this_rq lock */ + get_task_struct(next_task); + + /* find_lock_lowest_rq locks the rq if found */ + lowest_rq = find_lock_lowest_rq(next_task, this_rq); + if (!lowest_rq) { + struct task_struct *task; + /* + * find lock_lowest_rq releases this_rq->lock + * so it is possible that next_task has changed. + * If it has, then try again. + */ + task = pick_next_highest_task_rt(this_rq); + if (unlikely(task != next_task) && task && paranoid--) { + put_task_struct(next_task); + next_task = task; + goto retry; + } + goto out; + } + + assert_spin_locked(&lowest_rq->lock); + + deactivate_task(this_rq, next_task, 0); + set_task_cpu(next_task, lowest_rq->cpu); + activate_task(lowest_rq, next_task, 0); + + resched_task(lowest_rq->curr); + + spin_unlock(&lowest_rq->lock); + + ret = 1; +out: + put_task_struct(next_task); + + return ret; +} + +/* + * TODO: Currently we just use the second highest prio task on + * the queue, and stop when it can't migrate (or there's + * no more RT tasks). There may be a case where a lower + * priority RT task has a different affinity than the + * higher RT task. In this case the lower RT task could + * possibly be able to migrate where as the higher priority + * RT task could not. We currently ignore this issue. + * Enhancements are welcome! + */ +static void push_rt_tasks(struct rq *rq) +{ + /* push_rt_task will return true if it moved an RT */ + while (push_rt_task(rq)) + ; +} + +static void schedule_tail_balance_rt(struct rq *rq) +{ + /* + * If we have more than one rt_task queued, then + * see if we can push the other rt_tasks off to other CPUS. + * Note we may release the rq lock, and since + * the lock was owned by prev, we need to release it + * first via finish_lock_switch and then reaquire it here. + */ + if (unlikely(rq->rt.rt_nr_running > 1)) { + spin_lock_irq(&rq->lock); + push_rt_tasks(rq); + spin_unlock_irq(&rq->lock); + } +} + /* * Load-balancing iterator. Note: while the runqueue stays locked * during the whole iteration, the current task might be @@ -241,7 +462,9 @@ move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest, return iter_move_one_task(this_rq, this_cpu, busiest, sd, idle, &rt_rq_iterator); } -#endif +#else /* CONFIG_SMP */ +# define schedule_tail_balance_rt(rq) do { } while (0) +#endif /* CONFIG_SMP */ static void task_tick_rt(struct rq *rq, struct task_struct *p) { -- cgit v1.2.3-59-g8ed1b From 4fd29176b7cd24909f8ceba2105cb3ae2857b90c Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:06 +0100 Subject: sched: add rt-overload tracking This patch adds an RT overload accounting system. When a runqueue has more than one RT task queued, it is marked as overloaded. That is that it is a candidate to have RT tasks pulled from it. Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 7815e90b1147..547f858b0752 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -3,6 +3,38 @@ * policies) */ +#ifdef CONFIG_SMP +static cpumask_t rt_overload_mask; +static atomic_t rto_count; +static inline int rt_overloaded(void) +{ + return atomic_read(&rto_count); +} +static inline cpumask_t *rt_overload(void) +{ + return &rt_overload_mask; +} +static inline void rt_set_overload(struct rq *rq) +{ + cpu_set(rq->cpu, rt_overload_mask); + /* + * Make sure the mask is visible before we set + * the overload count. That is checked to determine + * if we should look at the mask. It would be a shame + * if we looked at the mask, but the mask was not + * updated yet. + */ + wmb(); + atomic_inc(&rto_count); +} +static inline void rt_clear_overload(struct rq *rq) +{ + /* the order here really doesn't matter */ + atomic_dec(&rto_count); + cpu_clear(rq->cpu, rt_overload_mask); +} +#endif /* CONFIG_SMP */ + /* * Update the current task's runtime statistics. Skip current tasks that * are not in our scheduling class. @@ -33,6 +65,8 @@ static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq) #ifdef CONFIG_SMP if (p->prio < rq->rt.highest_prio) rq->rt.highest_prio = p->prio; + if (rq->rt.rt_nr_running > 1) + rt_set_overload(rq); #endif /* CONFIG_SMP */ } @@ -54,6 +88,8 @@ static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq) } /* otherwise leave rq->highest prio alone */ } else rq->rt.highest_prio = MAX_RT_PRIO; + if (rq->rt.rt_nr_running < 2) + rt_clear_overload(rq); #endif /* CONFIG_SMP */ } -- cgit v1.2.3-59-g8ed1b From f65eda4f789168ba5ff3fa75546c29efeed19f58 Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:07 +0100 Subject: sched: pull RT tasks from overloaded runqueues This patch adds the algorithm to pull tasks from RT overloaded runqueues. When a pull RT is initiated, all overloaded runqueues are examined for a RT task that is higher in prio than the highest prio task queued on the target runqueue. If another runqueue holds a RT task that is of higher prio than the highest prio task on the target runqueue is found it is pulled to the target runqueue. Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched.c | 2 + kernel/sched_rt.c | 187 ++++++++++++++++++++++++++++++++++++++++++++++++++---- 2 files changed, 178 insertions(+), 11 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched.c b/kernel/sched.c index 97cab609fc31..c91797107913 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -3721,6 +3721,8 @@ need_resched_nonpreemptible: switch_count = &prev->nvcsw; } + schedule_balance_rt(rq, prev); + if (unlikely(!rq->nr_running)) idle_balance(cpu, rq); diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 547f858b0752..bacb32039e95 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -179,8 +179,17 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p) static int double_lock_balance(struct rq *this_rq, struct rq *busiest); static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep); +static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) +{ + if (!task_running(rq, p) && + (cpu < 0 || cpu_isset(cpu, p->cpus_allowed))) + return 1; + return 0; +} + /* Return the second highest RT task, NULL otherwise */ -static struct task_struct *pick_next_highest_task_rt(struct rq *rq) +static struct task_struct *pick_next_highest_task_rt(struct rq *rq, + int cpu) { struct rt_prio_array *array = &rq->rt.active; struct task_struct *next; @@ -199,26 +208,36 @@ static struct task_struct *pick_next_highest_task_rt(struct rq *rq) } queue = array->queue + idx; + BUG_ON(list_empty(queue)); + next = list_entry(queue->next, struct task_struct, run_list); - if (unlikely(next != rq->curr)) - return next; + if (unlikely(pick_rt_task(rq, next, cpu))) + goto out; if (queue->next->next != queue) { /* same prio task */ next = list_entry(queue->next->next, struct task_struct, run_list); - return next; + if (pick_rt_task(rq, next, cpu)) + goto out; } + retry: /* slower, but more flexible */ idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); - if (unlikely(idx >= MAX_RT_PRIO)) { - WARN_ON(1); /* rt_nr_running was 2 and above! */ + if (unlikely(idx >= MAX_RT_PRIO)) return NULL; - } queue = array->queue + idx; - next = list_entry(queue->next, struct task_struct, run_list); + BUG_ON(list_empty(queue)); + + list_for_each_entry(next, queue, run_list) { + if (pick_rt_task(rq, next, cpu)) + goto out; + } + + goto retry; + out: return next; } @@ -305,13 +324,15 @@ static int push_rt_task(struct rq *this_rq) assert_spin_locked(&this_rq->lock); - next_task = pick_next_highest_task_rt(this_rq); + next_task = pick_next_highest_task_rt(this_rq, -1); if (!next_task) return 0; retry: - if (unlikely(next_task == this_rq->curr)) + if (unlikely(next_task == this_rq->curr)) { + WARN_ON(1); return 0; + } /* * It's possible that the next_task slipped in of @@ -335,7 +356,7 @@ static int push_rt_task(struct rq *this_rq) * so it is possible that next_task has changed. * If it has, then try again. */ - task = pick_next_highest_task_rt(this_rq); + task = pick_next_highest_task_rt(this_rq, -1); if (unlikely(task != next_task) && task && paranoid--) { put_task_struct(next_task); next_task = task; @@ -378,6 +399,149 @@ static void push_rt_tasks(struct rq *rq) ; } +static int pull_rt_task(struct rq *this_rq) +{ + struct task_struct *next; + struct task_struct *p; + struct rq *src_rq; + cpumask_t *rto_cpumask; + int this_cpu = this_rq->cpu; + int cpu; + int ret = 0; + + assert_spin_locked(&this_rq->lock); + + /* + * If cpusets are used, and we have overlapping + * run queue cpusets, then this algorithm may not catch all. + * This is just the price you pay on trying to keep + * dirtying caches down on large SMP machines. + */ + if (likely(!rt_overloaded())) + return 0; + + next = pick_next_task_rt(this_rq); + + rto_cpumask = rt_overload(); + + for_each_cpu_mask(cpu, *rto_cpumask) { + if (this_cpu == cpu) + continue; + + src_rq = cpu_rq(cpu); + if (unlikely(src_rq->rt.rt_nr_running <= 1)) { + /* + * It is possible that overlapping cpusets + * will miss clearing a non overloaded runqueue. + * Clear it now. + */ + if (double_lock_balance(this_rq, src_rq)) { + /* unlocked our runqueue lock */ + struct task_struct *old_next = next; + next = pick_next_task_rt(this_rq); + if (next != old_next) + ret = 1; + } + if (likely(src_rq->rt.rt_nr_running <= 1)) + /* + * Small chance that this_rq->curr changed + * but it's really harmless here. + */ + rt_clear_overload(this_rq); + else + /* + * Heh, the src_rq is now overloaded, since + * we already have the src_rq lock, go straight + * to pulling tasks from it. + */ + goto try_pulling; + spin_unlock(&src_rq->lock); + continue; + } + + /* + * We can potentially drop this_rq's lock in + * double_lock_balance, and another CPU could + * steal our next task - hence we must cause + * the caller to recalculate the next task + * in that case: + */ + if (double_lock_balance(this_rq, src_rq)) { + struct task_struct *old_next = next; + next = pick_next_task_rt(this_rq); + if (next != old_next) + ret = 1; + } + + /* + * Are there still pullable RT tasks? + */ + if (src_rq->rt.rt_nr_running <= 1) { + spin_unlock(&src_rq->lock); + continue; + } + + try_pulling: + p = pick_next_highest_task_rt(src_rq, this_cpu); + + /* + * Do we have an RT task that preempts + * the to-be-scheduled task? + */ + if (p && (!next || (p->prio < next->prio))) { + WARN_ON(p == src_rq->curr); + WARN_ON(!p->se.on_rq); + + /* + * There's a chance that p is higher in priority + * than what's currently running on its cpu. + * This is just that p is wakeing up and hasn't + * had a chance to schedule. We only pull + * p if it is lower in priority than the + * current task on the run queue or + * this_rq next task is lower in prio than + * the current task on that rq. + */ + if (p->prio < src_rq->curr->prio || + (next && next->prio < src_rq->curr->prio)) + goto bail; + + ret = 1; + + deactivate_task(src_rq, p, 0); + set_task_cpu(p, this_cpu); + activate_task(this_rq, p, 0); + /* + * We continue with the search, just in + * case there's an even higher prio task + * in another runqueue. (low likelyhood + * but possible) + */ + + /* + * Update next so that we won't pick a task + * on another cpu with a priority lower (or equal) + * than the one we just picked. + */ + next = p; + + } + bail: + spin_unlock(&src_rq->lock); + } + + return ret; +} + +static void schedule_balance_rt(struct rq *rq, + struct task_struct *prev) +{ + /* Try to pull RT tasks here if we lower this rq's prio */ + if (unlikely(rt_task(prev)) && + rq->rt.highest_prio > prev->prio) + pull_rt_task(rq); +} + static void schedule_tail_balance_rt(struct rq *rq) { /* @@ -500,6 +664,7 @@ move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest, } #else /* CONFIG_SMP */ # define schedule_tail_balance_rt(rq) do { } while (0) +# define schedule_balance_rt(rq, prev) do { } while (0) #endif /* CONFIG_SMP */ static void task_tick_rt(struct rq *rq, struct task_struct *p) -- cgit v1.2.3-59-g8ed1b From 4642dafdf93dc7d66ee33437b93a5e6b8cea20d2 Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:07 +0100 Subject: sched: push RT tasks from overloaded CPUs This patch adds pushing of overloaded RT tasks from a runqueue that is having tasks (most likely RT tasks) added to the run queue. TODO: We don't cover the case of waking of new RT tasks (yet). Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched.c | 1 + kernel/sched_rt.c | 10 ++++++++++ 2 files changed, 11 insertions(+) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched.c b/kernel/sched.c index c91797107913..357d3a084de8 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -1710,6 +1710,7 @@ out_activate: out_running: p->state = TASK_RUNNING; + wakeup_balance_rt(rq, p); out: task_rq_unlock(rq, &flags); diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index bacb32039e95..d38a8a559aa5 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -558,6 +558,15 @@ static void schedule_tail_balance_rt(struct rq *rq) } } + +static void wakeup_balance_rt(struct rq *rq, struct task_struct *p) +{ + if (unlikely(rt_task(p)) && + !task_running(rq, p) && + (p->prio >= rq->curr->prio)) + push_rt_tasks(rq); +} + /* * Load-balancing iterator. Note: while the runqueue stays locked * during the whole iteration, the current task might be @@ -665,6 +674,7 @@ move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest, #else /* CONFIG_SMP */ # define schedule_tail_balance_rt(rq) do { } while (0) # define schedule_balance_rt(rq, prev) do { } while (0) +# define wakeup_balance_rt(rq, p) do { } while (0) #endif /* CONFIG_SMP */ static void task_tick_rt(struct rq *rq, struct task_struct *p) -- cgit v1.2.3-59-g8ed1b From c7a1e46aa9782a947cf2ed506245d43396dbf991 Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:07 +0100 Subject: sched: disable standard balancer for RT tasks Since we now take an active approach to load balancing, we don't need to balance RT tasks via the normal task balancer. In fact, this code was found to pull RT tasks away from CPUS that the active movement performed, resulting in large latencies. Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 95 +++---------------------------------------------------- 1 file changed, 4 insertions(+), 91 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index d38a8a559aa5..c492fd2b2eec 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -567,109 +567,22 @@ static void wakeup_balance_rt(struct rq *rq, struct task_struct *p) push_rt_tasks(rq); } -/* - * Load-balancing iterator. Note: while the runqueue stays locked - * during the whole iteration, the current task might be - * dequeued so the iterator has to be dequeue-safe. Here we - * achieve that by always pre-iterating before returning - * the current task: - */ -static struct task_struct *load_balance_start_rt(void *arg) -{ - struct rq *rq = arg; - struct rt_prio_array *array = &rq->rt.active; - struct list_head *head, *curr; - struct task_struct *p; - int idx; - - idx = sched_find_first_bit(array->bitmap); - if (idx >= MAX_RT_PRIO) - return NULL; - - head = array->queue + idx; - curr = head->prev; - - p = list_entry(curr, struct task_struct, run_list); - - curr = curr->prev; - - rq->rt.rt_load_balance_idx = idx; - rq->rt.rt_load_balance_head = head; - rq->rt.rt_load_balance_curr = curr; - - return p; -} - -static struct task_struct *load_balance_next_rt(void *arg) -{ - struct rq *rq = arg; - struct rt_prio_array *array = &rq->rt.active; - struct list_head *head, *curr; - struct task_struct *p; - int idx; - - idx = rq->rt.rt_load_balance_idx; - head = rq->rt.rt_load_balance_head; - curr = rq->rt.rt_load_balance_curr; - - /* - * If we arrived back to the head again then - * iterate to the next queue (if any): - */ - if (unlikely(head == curr)) { - int next_idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); - - if (next_idx >= MAX_RT_PRIO) - return NULL; - - idx = next_idx; - head = array->queue + idx; - curr = head->prev; - - rq->rt.rt_load_balance_idx = idx; - rq->rt.rt_load_balance_head = head; - } - - p = list_entry(curr, struct task_struct, run_list); - - curr = curr->prev; - - rq->rt.rt_load_balance_curr = curr; - - return p; -} - static unsigned long load_balance_rt(struct rq *this_rq, int this_cpu, struct rq *busiest, unsigned long max_load_move, struct sched_domain *sd, enum cpu_idle_type idle, int *all_pinned, int *this_best_prio) { - struct rq_iterator rt_rq_iterator; - - rt_rq_iterator.start = load_balance_start_rt; - rt_rq_iterator.next = load_balance_next_rt; - /* pass 'busiest' rq argument into - * load_balance_[start|next]_rt iterators - */ - rt_rq_iterator.arg = busiest; - - return balance_tasks(this_rq, this_cpu, busiest, max_load_move, sd, - idle, all_pinned, this_best_prio, &rt_rq_iterator); + /* don't touch RT tasks */ + return 0; } static int move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest, struct sched_domain *sd, enum cpu_idle_type idle) { - struct rq_iterator rt_rq_iterator; - - rt_rq_iterator.start = load_balance_start_rt; - rt_rq_iterator.next = load_balance_next_rt; - rt_rq_iterator.arg = busiest; - - return iter_move_one_task(this_rq, this_cpu, busiest, sd, idle, - &rt_rq_iterator); + /* don't touch RT tasks */ + return 0; } #else /* CONFIG_SMP */ # define schedule_tail_balance_rt(rq) do { } while (0) -- cgit v1.2.3-59-g8ed1b From 73fe6aae84400e2b475e2a1dc4e8592cd3ed6e69 Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:07 +0100 Subject: sched: add RT-balance cpu-weight Some RT tasks (particularly kthreads) are bound to one specific CPU. It is fairly common for two or more bound tasks to get queued up at the same time. Consider, for instance, softirq_timer and softirq_sched. A timer goes off in an ISR which schedules softirq_thread to run at RT50. Then the timer handler determines that it's time to smp-rebalance the system so it schedules softirq_sched to run. So we are in a situation where we have two RT50 tasks queued, and the system will go into rt-overload condition to request other CPUs for help. This causes two problems in the current code: 1) If a high-priority bound task and a low-priority unbounded task queue up behind the running task, we will fail to ever relocate the unbounded task because we terminate the search on the first unmovable task. 2) We spend precious futile cycles in the fast-path trying to pull overloaded tasks over. It is therefore optimial to strive to avoid the overhead all together if we can cheaply detect the condition before overload even occurs. This patch tries to achieve this optimization by utilizing the hamming weight of the task->cpus_allowed mask. A weight of 1 indicates that the task cannot be migrated. We will then utilize this information to skip non-migratable tasks and to eliminate uncessary rebalance attempts. We introduce a per-rq variable to count the number of migratable tasks that are currently running. We only go into overload if we have more than one rt task, AND at least one of them is migratable. In addition, we introduce a per-task variable to cache the cpus_allowed weight, since the hamming calculation is probably relatively expensive. We only update the cached value when the mask is updated which should be relatively infrequent, especially compared to scheduling frequency in the fast path. Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- include/linux/init_task.h | 1 + include/linux/sched.h | 2 ++ kernel/fork.c | 1 + kernel/sched.c | 9 ++++++++- kernel/sched_rt.c | 50 ++++++++++++++++++++++++++++++++++++++++++----- 5 files changed, 57 insertions(+), 6 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/include/linux/init_task.h b/include/linux/init_task.h index cae35b6b9aec..572c65bcc80f 100644 --- a/include/linux/init_task.h +++ b/include/linux/init_task.h @@ -130,6 +130,7 @@ extern struct group_info init_groups; .normal_prio = MAX_PRIO-20, \ .policy = SCHED_NORMAL, \ .cpus_allowed = CPU_MASK_ALL, \ + .nr_cpus_allowed = NR_CPUS, \ .mm = NULL, \ .active_mm = &init_mm, \ .run_list = LIST_HEAD_INIT(tsk.run_list), \ diff --git a/include/linux/sched.h b/include/linux/sched.h index 0846f1f9e196..b07a2cf76401 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -847,6 +847,7 @@ struct sched_class { void (*set_curr_task) (struct rq *rq); void (*task_tick) (struct rq *rq, struct task_struct *p); void (*task_new) (struct rq *rq, struct task_struct *p); + void (*set_cpus_allowed)(struct task_struct *p, cpumask_t *newmask); }; struct load_weight { @@ -956,6 +957,7 @@ struct task_struct { unsigned int policy; cpumask_t cpus_allowed; + int nr_cpus_allowed; unsigned int time_slice; #if defined(CONFIG_SCHEDSTATS) || defined(CONFIG_TASK_DELAY_ACCT) diff --git a/kernel/fork.c b/kernel/fork.c index 09c0b90a69cc..930c51865ab4 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -1242,6 +1242,7 @@ static struct task_struct *copy_process(unsigned long clone_flags, * parent's CPU). This avoids alot of nasty races. */ p->cpus_allowed = current->cpus_allowed; + p->nr_cpus_allowed = current->nr_cpus_allowed; if (unlikely(!cpu_isset(task_cpu(p), p->cpus_allowed) || !cpu_online(task_cpu(p)))) set_task_cpu(p, smp_processor_id()); diff --git a/kernel/sched.c b/kernel/sched.c index 357d3a084de8..66e99b419b31 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -343,6 +343,7 @@ struct rt_rq { int rt_load_balance_idx; struct list_head *rt_load_balance_head, *rt_load_balance_curr; unsigned long rt_nr_running; + unsigned long rt_nr_migratory; /* highest queued rt task prio */ int highest_prio; }; @@ -5144,7 +5145,13 @@ int set_cpus_allowed(struct task_struct *p, cpumask_t new_mask) goto out; } - p->cpus_allowed = new_mask; + if (p->sched_class->set_cpus_allowed) + p->sched_class->set_cpus_allowed(p, &new_mask); + else { + p->cpus_allowed = new_mask; + p->nr_cpus_allowed = cpus_weight(new_mask); + } + /* Can the task run on the task's current CPU? If so, we're done */ if (cpu_isset(task_cpu(p), new_mask)) goto out; diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index c492fd2b2eec..ae4995c09aac 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -33,6 +33,14 @@ static inline void rt_clear_overload(struct rq *rq) atomic_dec(&rto_count); cpu_clear(rq->cpu, rt_overload_mask); } + +static void update_rt_migration(struct rq *rq) +{ + if (rq->rt.rt_nr_migratory && (rq->rt.rt_nr_running > 1)) + rt_set_overload(rq); + else + rt_clear_overload(rq); +} #endif /* CONFIG_SMP */ /* @@ -65,8 +73,10 @@ static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq) #ifdef CONFIG_SMP if (p->prio < rq->rt.highest_prio) rq->rt.highest_prio = p->prio; - if (rq->rt.rt_nr_running > 1) - rt_set_overload(rq); + if (p->nr_cpus_allowed > 1) + rq->rt.rt_nr_migratory++; + + update_rt_migration(rq); #endif /* CONFIG_SMP */ } @@ -88,8 +98,10 @@ static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq) } /* otherwise leave rq->highest prio alone */ } else rq->rt.highest_prio = MAX_RT_PRIO; - if (rq->rt.rt_nr_running < 2) - rt_clear_overload(rq); + if (p->nr_cpus_allowed > 1) + rq->rt.rt_nr_migratory--; + + update_rt_migration(rq); #endif /* CONFIG_SMP */ } @@ -182,7 +194,8 @@ static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep); static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) { if (!task_running(rq, p) && - (cpu < 0 || cpu_isset(cpu, p->cpus_allowed))) + (cpu < 0 || cpu_isset(cpu, p->cpus_allowed)) && + (p->nr_cpus_allowed > 1)) return 1; return 0; } @@ -584,6 +597,32 @@ move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest, /* don't touch RT tasks */ return 0; } +static void set_cpus_allowed_rt(struct task_struct *p, cpumask_t *new_mask) +{ + int weight = cpus_weight(*new_mask); + + BUG_ON(!rt_task(p)); + + /* + * Update the migration status of the RQ if we have an RT task + * which is running AND changing its weight value. + */ + if (p->se.on_rq && (weight != p->nr_cpus_allowed)) { + struct rq *rq = task_rq(p); + + if ((p->nr_cpus_allowed <= 1) && (weight > 1)) + rq->rt.rt_nr_migratory++; + else if((p->nr_cpus_allowed > 1) && (weight <= 1)) { + BUG_ON(!rq->rt.rt_nr_migratory); + rq->rt.rt_nr_migratory--; + } + + update_rt_migration(rq); + } + + p->cpus_allowed = *new_mask; + p->nr_cpus_allowed = weight; +} #else /* CONFIG_SMP */ # define schedule_tail_balance_rt(rq) do { } while (0) # define schedule_balance_rt(rq, prev) do { } while (0) @@ -637,6 +676,7 @@ const struct sched_class rt_sched_class = { #ifdef CONFIG_SMP .load_balance = load_balance_rt, .move_one_task = move_one_task_rt, + .set_cpus_allowed = set_cpus_allowed_rt, #endif .set_curr_task = set_curr_task_rt, -- cgit v1.2.3-59-g8ed1b From 697f0a487f294e634a342764472b79375bb3158a Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:09 +0100 Subject: sched: clean up this_rq use in kernel/sched_rt.c "this_rq" is normally used to denote the RQ on the current cpu (i.e. "cpu_rq(this_cpu)"). So clean up the usage of this_rq to be more consistent with the rest of the code. Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 22 +++++++++++----------- 1 file changed, 11 insertions(+), 11 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index ae4995c09aac..b788e35ffd3f 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -328,21 +328,21 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, * running task can migrate over to a CPU that is running a task * of lesser priority. */ -static int push_rt_task(struct rq *this_rq) +static int push_rt_task(struct rq *rq) { struct task_struct *next_task; struct rq *lowest_rq; int ret = 0; int paranoid = RT_MAX_TRIES; - assert_spin_locked(&this_rq->lock); + assert_spin_locked(&rq->lock); - next_task = pick_next_highest_task_rt(this_rq, -1); + next_task = pick_next_highest_task_rt(rq, -1); if (!next_task) return 0; retry: - if (unlikely(next_task == this_rq->curr)) { + if (unlikely(next_task == rq->curr)) { WARN_ON(1); return 0; } @@ -352,24 +352,24 @@ static int push_rt_task(struct rq *this_rq) * higher priority than current. If that's the case * just reschedule current. */ - if (unlikely(next_task->prio < this_rq->curr->prio)) { - resched_task(this_rq->curr); + if (unlikely(next_task->prio < rq->curr->prio)) { + resched_task(rq->curr); return 0; } - /* We might release this_rq lock */ + /* We might release rq lock */ get_task_struct(next_task); /* find_lock_lowest_rq locks the rq if found */ - lowest_rq = find_lock_lowest_rq(next_task, this_rq); + lowest_rq = find_lock_lowest_rq(next_task, rq); if (!lowest_rq) { struct task_struct *task; /* - * find lock_lowest_rq releases this_rq->lock + * find lock_lowest_rq releases rq->lock * so it is possible that next_task has changed. * If it has, then try again. */ - task = pick_next_highest_task_rt(this_rq, -1); + task = pick_next_highest_task_rt(rq, -1); if (unlikely(task != next_task) && task && paranoid--) { put_task_struct(next_task); next_task = task; @@ -380,7 +380,7 @@ static int push_rt_task(struct rq *this_rq) assert_spin_locked(&lowest_rq->lock); - deactivate_task(this_rq, next_task, 0); + deactivate_task(rq, next_task, 0); set_task_cpu(next_task, lowest_rq->cpu); activate_task(lowest_rq, next_task, 0); -- cgit v1.2.3-59-g8ed1b From e7693a362ec84bb5b6fd441d8a8b4b9d568a7a0c Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:09 +0100 Subject: sched: de-SCHED_OTHER-ize the RT path The current wake-up code path tries to determine if it can optimize the wake-up to "this_cpu" by computing load calculations. The problem is that these calculations are only relevant to SCHED_OTHER tasks where load is king. For RT tasks, priority is king. So the load calculation is completely wasted bandwidth. Therefore, we create a new sched_class interface to help with pre-wakeup routing decisions and move the load calculation as a function of CFS task's class. Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- include/linux/sched.h | 1 + kernel/sched.c | 167 ++++++++---------------------------------------- kernel/sched_fair.c | 148 ++++++++++++++++++++++++++++++++++++++++++ kernel/sched_idletask.c | 9 +++ kernel/sched_rt.c | 10 +++ 5 files changed, 195 insertions(+), 140 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/include/linux/sched.h b/include/linux/sched.h index b07a2cf76401..6fbbf38555ac 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -827,6 +827,7 @@ struct sched_class { void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup); void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep); void (*yield_task) (struct rq *rq); + int (*select_task_rq)(struct task_struct *p, int sync); void (*check_preempt_curr) (struct rq *rq, struct task_struct *p); diff --git a/kernel/sched.c b/kernel/sched.c index 66e99b419b31..3344ba776b97 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -960,6 +960,13 @@ static inline void dec_cpu_load(struct rq *rq, unsigned long load) update_load_sub(&rq->load, load); } +#ifdef CONFIG_SMP +static unsigned long source_load(int cpu, int type); +static unsigned long target_load(int cpu, int type); +static unsigned long cpu_avg_load_per_task(int cpu); +static int task_hot(struct task_struct *p, u64 now, struct sched_domain *sd); +#endif /* CONFIG_SMP */ + #include "sched_stats.h" #include "sched_idletask.c" #include "sched_fair.c" @@ -1118,7 +1125,7 @@ static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu) /* * Is this task likely cache-hot: */ -static inline int +static int task_hot(struct task_struct *p, u64 now, struct sched_domain *sd) { s64 delta; @@ -1343,7 +1350,7 @@ static unsigned long target_load(int cpu, int type) /* * Return the average load per task on the cpu's run queue */ -static inline unsigned long cpu_avg_load_per_task(int cpu) +static unsigned long cpu_avg_load_per_task(int cpu) { struct rq *rq = cpu_rq(cpu); unsigned long total = weighted_cpuload(cpu); @@ -1500,58 +1507,6 @@ static int sched_balance_self(int cpu, int flag) #endif /* CONFIG_SMP */ -/* - * wake_idle() will wake a task on an idle cpu if task->cpu is - * not idle and an idle cpu is available. The span of cpus to - * search starts with cpus closest then further out as needed, - * so we always favor a closer, idle cpu. - * - * Returns the CPU we should wake onto. - */ -#if defined(ARCH_HAS_SCHED_WAKE_IDLE) -static int wake_idle(int cpu, struct task_struct *p) -{ - cpumask_t tmp; - struct sched_domain *sd; - int i; - - /* - * If it is idle, then it is the best cpu to run this task. - * - * This cpu is also the best, if it has more than one task already. - * Siblings must be also busy(in most cases) as they didn't already - * pickup the extra load from this cpu and hence we need not check - * sibling runqueue info. This will avoid the checks and cache miss - * penalities associated with that. - */ - if (idle_cpu(cpu) || cpu_rq(cpu)->nr_running > 1) - return cpu; - - for_each_domain(cpu, sd) { - if (sd->flags & SD_WAKE_IDLE) { - cpus_and(tmp, sd->span, p->cpus_allowed); - for_each_cpu_mask(i, tmp) { - if (idle_cpu(i)) { - if (i != task_cpu(p)) { - schedstat_inc(p, - se.nr_wakeups_idle); - } - return i; - } - } - } else { - break; - } - } - return cpu; -} -#else -static inline int wake_idle(int cpu, struct task_struct *p) -{ - return cpu; -} -#endif - /*** * try_to_wake_up - wake up a thread * @p: the to-be-woken-up thread @@ -1573,8 +1528,6 @@ static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync) long old_state; struct rq *rq; #ifdef CONFIG_SMP - struct sched_domain *sd, *this_sd = NULL; - unsigned long load, this_load; int new_cpu; #endif @@ -1594,90 +1547,7 @@ static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync) if (unlikely(task_running(rq, p))) goto out_activate; - new_cpu = cpu; - - schedstat_inc(rq, ttwu_count); - if (cpu == this_cpu) { - schedstat_inc(rq, ttwu_local); - goto out_set_cpu; - } - - for_each_domain(this_cpu, sd) { - if (cpu_isset(cpu, sd->span)) { - schedstat_inc(sd, ttwu_wake_remote); - this_sd = sd; - break; - } - } - - if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed))) - goto out_set_cpu; - - /* - * Check for affine wakeup and passive balancing possibilities. - */ - if (this_sd) { - int idx = this_sd->wake_idx; - unsigned int imbalance; - - imbalance = 100 + (this_sd->imbalance_pct - 100) / 2; - - load = source_load(cpu, idx); - this_load = target_load(this_cpu, idx); - - new_cpu = this_cpu; /* Wake to this CPU if we can */ - - if (this_sd->flags & SD_WAKE_AFFINE) { - unsigned long tl = this_load; - unsigned long tl_per_task; - - /* - * Attract cache-cold tasks on sync wakeups: - */ - if (sync && !task_hot(p, rq->clock, this_sd)) - goto out_set_cpu; - - schedstat_inc(p, se.nr_wakeups_affine_attempts); - tl_per_task = cpu_avg_load_per_task(this_cpu); - - /* - * If sync wakeup then subtract the (maximum possible) - * effect of the currently running task from the load - * of the current CPU: - */ - if (sync) - tl -= current->se.load.weight; - - if ((tl <= load && - tl + target_load(cpu, idx) <= tl_per_task) || - 100*(tl + p->se.load.weight) <= imbalance*load) { - /* - * This domain has SD_WAKE_AFFINE and - * p is cache cold in this domain, and - * there is no bad imbalance. - */ - schedstat_inc(this_sd, ttwu_move_affine); - schedstat_inc(p, se.nr_wakeups_affine); - goto out_set_cpu; - } - } - - /* - * Start passive balancing when half the imbalance_pct - * limit is reached. - */ - if (this_sd->flags & SD_WAKE_BALANCE) { - if (imbalance*this_load <= 100*load) { - schedstat_inc(this_sd, ttwu_move_balance); - schedstat_inc(p, se.nr_wakeups_passive); - goto out_set_cpu; - } - } - } - - new_cpu = cpu; /* Could not wake to this_cpu. Wake to cpu instead */ -out_set_cpu: - new_cpu = wake_idle(new_cpu, p); + new_cpu = p->sched_class->select_task_rq(p, sync); if (new_cpu != cpu) { set_task_cpu(p, new_cpu); task_rq_unlock(rq, &flags); @@ -1693,6 +1563,23 @@ out_set_cpu: cpu = task_cpu(p); } +#ifdef CONFIG_SCHEDSTATS + schedstat_inc(rq, ttwu_count); + if (cpu == this_cpu) + schedstat_inc(rq, ttwu_local); + else { + struct sched_domain *sd; + for_each_domain(this_cpu, sd) { + if (cpu_isset(cpu, sd->span)) { + schedstat_inc(sd, ttwu_wake_remote); + break; + } + } + } + +#endif + + out_activate: #endif /* CONFIG_SMP */ schedstat_inc(p, se.nr_wakeups); diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c index 5c208e090ae4..f881fc5e035c 100644 --- a/kernel/sched_fair.c +++ b/kernel/sched_fair.c @@ -860,6 +860,151 @@ static void yield_task_fair(struct rq *rq) se->vruntime = rightmost->vruntime + 1; } +/* + * wake_idle() will wake a task on an idle cpu if task->cpu is + * not idle and an idle cpu is available. The span of cpus to + * search starts with cpus closest then further out as needed, + * so we always favor a closer, idle cpu. + * + * Returns the CPU we should wake onto. + */ +#if defined(ARCH_HAS_SCHED_WAKE_IDLE) +static int wake_idle(int cpu, struct task_struct *p) +{ + cpumask_t tmp; + struct sched_domain *sd; + int i; + + /* + * If it is idle, then it is the best cpu to run this task. + * + * This cpu is also the best, if it has more than one task already. + * Siblings must be also busy(in most cases) as they didn't already + * pickup the extra load from this cpu and hence we need not check + * sibling runqueue info. This will avoid the checks and cache miss + * penalities associated with that. + */ + if (idle_cpu(cpu) || cpu_rq(cpu)->nr_running > 1) + return cpu; + + for_each_domain(cpu, sd) { + if (sd->flags & SD_WAKE_IDLE) { + cpus_and(tmp, sd->span, p->cpus_allowed); + for_each_cpu_mask(i, tmp) { + if (idle_cpu(i)) { + if (i != task_cpu(p)) { + schedstat_inc(p, + se.nr_wakeups_idle); + } + return i; + } + } + } else { + break; + } + } + return cpu; +} +#else +static inline int wake_idle(int cpu, struct task_struct *p) +{ + return cpu; +} +#endif + +#ifdef CONFIG_SMP +static int select_task_rq_fair(struct task_struct *p, int sync) +{ + int cpu, this_cpu; + struct rq *rq; + struct sched_domain *sd, *this_sd = NULL; + int new_cpu; + + cpu = task_cpu(p); + rq = task_rq(p); + this_cpu = smp_processor_id(); + new_cpu = cpu; + + for_each_domain(this_cpu, sd) { + if (cpu_isset(cpu, sd->span)) { + this_sd = sd; + break; + } + } + + if (unlikely(!cpu_isset(this_cpu, p->cpus_allowed))) + goto out_set_cpu; + + /* + * Check for affine wakeup and passive balancing possibilities. + */ + if (this_sd) { + int idx = this_sd->wake_idx; + unsigned int imbalance; + unsigned long load, this_load; + + imbalance = 100 + (this_sd->imbalance_pct - 100) / 2; + + load = source_load(cpu, idx); + this_load = target_load(this_cpu, idx); + + new_cpu = this_cpu; /* Wake to this CPU if we can */ + + if (this_sd->flags & SD_WAKE_AFFINE) { + unsigned long tl = this_load; + unsigned long tl_per_task; + + /* + * Attract cache-cold tasks on sync wakeups: + */ + if (sync && !task_hot(p, rq->clock, this_sd)) + goto out_set_cpu; + + schedstat_inc(p, se.nr_wakeups_affine_attempts); + tl_per_task = cpu_avg_load_per_task(this_cpu); + + /* + * If sync wakeup then subtract the (maximum possible) + * effect of the currently running task from the load + * of the current CPU: + */ + if (sync) + tl -= current->se.load.weight; + + if ((tl <= load && + tl + target_load(cpu, idx) <= tl_per_task) || + 100*(tl + p->se.load.weight) <= imbalance*load) { + /* + * This domain has SD_WAKE_AFFINE and + * p is cache cold in this domain, and + * there is no bad imbalance. + */ + schedstat_inc(this_sd, ttwu_move_affine); + schedstat_inc(p, se.nr_wakeups_affine); + goto out_set_cpu; + } + } + + /* + * Start passive balancing when half the imbalance_pct + * limit is reached. + */ + if (this_sd->flags & SD_WAKE_BALANCE) { + if (imbalance*this_load <= 100*load) { + schedstat_inc(this_sd, ttwu_move_balance); + schedstat_inc(p, se.nr_wakeups_passive); + goto out_set_cpu; + } + } + } + + new_cpu = cpu; /* Could not wake to this_cpu. Wake to cpu instead */ +out_set_cpu: + return wake_idle(new_cpu, p); +} +#endif /* CONFIG_SMP */ + + /* * Preempt the current task with a newly woken task if needed: */ @@ -1153,6 +1298,9 @@ static const struct sched_class fair_sched_class = { .enqueue_task = enqueue_task_fair, .dequeue_task = dequeue_task_fair, .yield_task = yield_task_fair, +#ifdef CONFIG_SMP + .select_task_rq = select_task_rq_fair, +#endif /* CONFIG_SMP */ .check_preempt_curr = check_preempt_wakeup, diff --git a/kernel/sched_idletask.c b/kernel/sched_idletask.c index bf9c25c15b8b..ca5374860aef 100644 --- a/kernel/sched_idletask.c +++ b/kernel/sched_idletask.c @@ -5,6 +5,12 @@ * handled in sched_fair.c) */ +#ifdef CONFIG_SMP +static int select_task_rq_idle(struct task_struct *p, int sync) +{ + return task_cpu(p); /* IDLE tasks as never migrated */ +} +#endif /* CONFIG_SMP */ /* * Idle tasks are unconditionally rescheduled: */ @@ -72,6 +78,9 @@ const struct sched_class idle_sched_class = { /* dequeue is not valid, we print a debug message there: */ .dequeue_task = dequeue_task_idle, +#ifdef CONFIG_SMP + .select_task_rq = select_task_rq_idle, +#endif /* CONFIG_SMP */ .check_preempt_curr = check_preempt_curr_idle, diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index b788e35ffd3f..5de1aebdbd1b 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -150,6 +150,13 @@ yield_task_rt(struct rq *rq) requeue_task_rt(rq, rq->curr); } +#ifdef CONFIG_SMP +static int select_task_rq_rt(struct task_struct *p, int sync) +{ + return task_cpu(p); +} +#endif /* CONFIG_SMP */ + /* * Preempt the current task with a newly woken task if needed: */ @@ -667,6 +674,9 @@ const struct sched_class rt_sched_class = { .enqueue_task = enqueue_task_rt, .dequeue_task = dequeue_task_rt, .yield_task = yield_task_rt, +#ifdef CONFIG_SMP + .select_task_rq = select_task_rq_rt, +#endif /* CONFIG_SMP */ .check_preempt_curr = check_preempt_curr_rt, -- cgit v1.2.3-59-g8ed1b From 07b4032c9e505e2a1fbe7703aff64a153c3249be Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:10 +0100 Subject: sched: break out search for RT tasks Isolate the search logic into a function so that it can be used later in places other than find_locked_lowest_rq(). Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 66 ++++++++++++++++++++++++++++++++----------------------- 1 file changed, 39 insertions(+), 27 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 5de1aebdbd1b..ffd02720b58f 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -263,54 +263,66 @@ static struct task_struct *pick_next_highest_task_rt(struct rq *rq, static DEFINE_PER_CPU(cpumask_t, local_cpu_mask); -/* Will lock the rq it finds */ -static struct rq *find_lock_lowest_rq(struct task_struct *task, - struct rq *this_rq) +static int find_lowest_rq(struct task_struct *task) { - struct rq *lowest_rq = NULL; int cpu; - int tries; cpumask_t *cpu_mask = &__get_cpu_var(local_cpu_mask); + struct rq *lowest_rq = NULL; cpus_and(*cpu_mask, cpu_online_map, task->cpus_allowed); - for (tries = 0; tries < RT_MAX_TRIES; tries++) { - /* - * Scan each rq for the lowest prio. - */ - for_each_cpu_mask(cpu, *cpu_mask) { - struct rq *rq = &per_cpu(runqueues, cpu); + /* + * Scan each rq for the lowest prio. + */ + for_each_cpu_mask(cpu, *cpu_mask) { + struct rq *rq = cpu_rq(cpu); - if (cpu == this_rq->cpu) - continue; + if (cpu == rq->cpu) + continue; - /* We look for lowest RT prio or non-rt CPU */ - if (rq->rt.highest_prio >= MAX_RT_PRIO) { - lowest_rq = rq; - break; - } + /* We look for lowest RT prio or non-rt CPU */ + if (rq->rt.highest_prio >= MAX_RT_PRIO) { + lowest_rq = rq; + break; + } - /* no locking for now */ - if (rq->rt.highest_prio > task->prio && - (!lowest_rq || rq->rt.highest_prio > lowest_rq->rt.highest_prio)) { - lowest_rq = rq; - } + /* no locking for now */ + if (rq->rt.highest_prio > task->prio && + (!lowest_rq || rq->rt.highest_prio > lowest_rq->rt.highest_prio)) { + lowest_rq = rq; } + } + + return lowest_rq ? lowest_rq->cpu : -1; +} + +/* Will lock the rq it finds */ +static struct rq *find_lock_lowest_rq(struct task_struct *task, + struct rq *rq) +{ + struct rq *lowest_rq = NULL; + int cpu; + int tries; - if (!lowest_rq) + for (tries = 0; tries < RT_MAX_TRIES; tries++) { + cpu = find_lowest_rq(task); + + if (cpu == -1) break; + lowest_rq = cpu_rq(cpu); + /* if the prio of this runqueue changed, try again */ - if (double_lock_balance(this_rq, lowest_rq)) { + if (double_lock_balance(rq, lowest_rq)) { /* * We had to unlock the run queue. In * the mean time, task could have * migrated already or had its affinity changed. * Also make sure that it wasn't scheduled on its rq. */ - if (unlikely(task_rq(task) != this_rq || + if (unlikely(task_rq(task) != rq || !cpu_isset(lowest_rq->cpu, task->cpus_allowed) || - task_running(this_rq, task) || + task_running(rq, task) || !task->se.on_rq)) { spin_unlock(&lowest_rq->lock); lowest_rq = NULL; -- cgit v1.2.3-59-g8ed1b From 2de0b4639f4b1b6bfe31f795e5855f041f177170 Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:10 +0100 Subject: sched: RT balancing: include current CPU It doesn't hurt if we allow the current CPU to be included in the search. We will just simply skip it later if the current CPU turns out to be the lowest. We will use this later in the series Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index ffd02720b58f..95f36f61ae1d 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -277,9 +277,6 @@ static int find_lowest_rq(struct task_struct *task) for_each_cpu_mask(cpu, *cpu_mask) { struct rq *rq = cpu_rq(cpu); - if (cpu == rq->cpu) - continue; - /* We look for lowest RT prio or non-rt CPU */ if (rq->rt.highest_prio >= MAX_RT_PRIO) { lowest_rq = rq; @@ -307,7 +304,7 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, for (tries = 0; tries < RT_MAX_TRIES; tries++) { cpu = find_lowest_rq(task); - if (cpu == -1) + if ((cpu == -1) || (cpu == rq->cpu)) break; lowest_rq = cpu_rq(cpu); -- cgit v1.2.3-59-g8ed1b From 318e0893ce3f524ca045f9fd9dfd567c0a6f9446 Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:10 +0100 Subject: sched: pre-route RT tasks on wakeup In the original patch series that Steven Rostedt and I worked on together, we both took different approaches to low-priority wakeup path. I utilized "pre-routing" (push the task away to a less important RQ before activating) approach, while Steve utilized a "post-routing" approach. The advantage of my approach is that you avoid the overhead of a wasted activate/deactivate cycle and peripherally related burdens. The advantage of Steve's method is that it neatly solves an issue preventing a "pull" optimization from being deployed. In the end, we ended up deploying Steve's idea. But it later dawned on me that we could get the best of both worlds by deploying both ideas together, albeit slightly modified. The idea is simple: Use a "light-weight" lookup for pre-routing, since we only need to approximate a good home for the task. And we also retain the post-routing push logic to clean up any inaccuracies caused by a condition of "priority mistargeting" caused by the lightweight lookup. Most of the time, the pre-routing should work and yield lower overhead. In the cases where it doesnt, the post-router will bat cleanup. Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 95f36f61ae1d..ac7d06786454 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -151,8 +151,27 @@ yield_task_rt(struct rq *rq) } #ifdef CONFIG_SMP +static int find_lowest_rq(struct task_struct *task); + static int select_task_rq_rt(struct task_struct *p, int sync) { + struct rq *rq = task_rq(p); + + /* + * If the task will not preempt the RQ, try to find a better RQ + * before we even activate the task + */ + if ((p->prio >= rq->rt.highest_prio) + && (p->nr_cpus_allowed > 1)) { + int cpu = find_lowest_rq(p); + + return (cpu == -1) ? task_cpu(p) : cpu; + } + + /* + * Otherwise, just let it ride on the affined RQ and the + * post-schedule router will push the preempted task away + */ return task_cpu(p); } #endif /* CONFIG_SMP */ -- cgit v1.2.3-59-g8ed1b From 6e1254d2c41215da27025add8900ed187bca121d Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:11 +0100 Subject: sched: optimize RT affinity The current code base assumes a relatively flat CPU/core topology and will route RT tasks to any CPU fairly equally. In the real world, there are various toplogies and affinities that govern where a task is best suited to run with the smallest amount of overhead. NUMA and multi-core CPUs are prime examples of topologies that can impact cache performance. Fortunately, linux is already structured to represent these topologies via the sched_domains interface. So we change our RT router to consult a combination of topology and affinity policy to best place tasks during migration. Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 100 +++++++++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 88 insertions(+), 12 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index ac7d06786454..a9d7d4408160 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -281,35 +281,111 @@ static struct task_struct *pick_next_highest_task_rt(struct rq *rq, } static DEFINE_PER_CPU(cpumask_t, local_cpu_mask); +static DEFINE_PER_CPU(cpumask_t, valid_cpu_mask); -static int find_lowest_rq(struct task_struct *task) +static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask) { - int cpu; - cpumask_t *cpu_mask = &__get_cpu_var(local_cpu_mask); - struct rq *lowest_rq = NULL; + int cpu; + cpumask_t *valid_mask = &__get_cpu_var(valid_cpu_mask); + int lowest_prio = -1; + int ret = 0; - cpus_and(*cpu_mask, cpu_online_map, task->cpus_allowed); + cpus_clear(*lowest_mask); + cpus_and(*valid_mask, cpu_online_map, task->cpus_allowed); /* * Scan each rq for the lowest prio. */ - for_each_cpu_mask(cpu, *cpu_mask) { + for_each_cpu_mask(cpu, *valid_mask) { struct rq *rq = cpu_rq(cpu); /* We look for lowest RT prio or non-rt CPU */ if (rq->rt.highest_prio >= MAX_RT_PRIO) { - lowest_rq = rq; - break; + if (ret) + cpus_clear(*lowest_mask); + cpu_set(rq->cpu, *lowest_mask); + return 1; } /* no locking for now */ - if (rq->rt.highest_prio > task->prio && - (!lowest_rq || rq->rt.highest_prio > lowest_rq->rt.highest_prio)) { - lowest_rq = rq; + if ((rq->rt.highest_prio > task->prio) + && (rq->rt.highest_prio >= lowest_prio)) { + if (rq->rt.highest_prio > lowest_prio) { + /* new low - clear old data */ + lowest_prio = rq->rt.highest_prio; + cpus_clear(*lowest_mask); + } + cpu_set(rq->cpu, *lowest_mask); + ret = 1; + } + } + + return ret; +} + +static inline int pick_optimal_cpu(int this_cpu, cpumask_t *mask) +{ + int first; + + /* "this_cpu" is cheaper to preempt than a remote processor */ + if ((this_cpu != -1) && cpu_isset(this_cpu, *mask)) + return this_cpu; + + first = first_cpu(*mask); + if (first != NR_CPUS) + return first; + + return -1; +} + +static int find_lowest_rq(struct task_struct *task) +{ + struct sched_domain *sd; + cpumask_t *lowest_mask = &__get_cpu_var(local_cpu_mask); + int this_cpu = smp_processor_id(); + int cpu = task_cpu(task); + + if (!find_lowest_cpus(task, lowest_mask)) + return -1; + + /* + * At this point we have built a mask of cpus representing the + * lowest priority tasks in the system. Now we want to elect + * the best one based on our affinity and topology. + * + * We prioritize the last cpu that the task executed on since + * it is most likely cache-hot in that location. + */ + if (cpu_isset(cpu, *lowest_mask)) + return cpu; + + /* + * Otherwise, we consult the sched_domains span maps to figure + * out which cpu is logically closest to our hot cache data. + */ + if (this_cpu == cpu) + this_cpu = -1; /* Skip this_cpu opt if the same */ + + for_each_domain(cpu, sd) { + if (sd->flags & SD_WAKE_AFFINE) { + cpumask_t domain_mask; + int best_cpu; + + cpus_and(domain_mask, sd->span, *lowest_mask); + + best_cpu = pick_optimal_cpu(this_cpu, + &domain_mask); + if (best_cpu != -1) + return best_cpu; } } - return lowest_rq ? lowest_rq->cpu : -1; + /* + * And finally, if there were no matches within the domains + * just give the caller *something* to work with from the compatible + * locations. + */ + return pick_optimal_cpu(this_cpu, lowest_mask); } /* Will lock the rq it finds */ -- cgit v1.2.3-59-g8ed1b From a22d7fc187ed996b66d8439db27b2303f79a8e7b Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:12 +0100 Subject: sched: wake-balance fixes We have logic to detect whether the system has migratable tasks, but we are not using it when deciding whether to push tasks away. So we add support for considering this new information. Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched.c | 2 ++ kernel/sched_rt.c | 10 ++++++++-- 2 files changed, 10 insertions(+), 2 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched.c b/kernel/sched.c index 3344ba776b97..c591abd9ca38 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -346,6 +346,7 @@ struct rt_rq { unsigned long rt_nr_migratory; /* highest queued rt task prio */ int highest_prio; + int overloaded; }; /* @@ -6770,6 +6771,7 @@ void __init sched_init(void) rq->migration_thread = NULL; INIT_LIST_HEAD(&rq->migration_queue); rq->rt.highest_prio = MAX_RT_PRIO; + rq->rt.overloaded = 0; #endif atomic_set(&rq->nr_iowait, 0); diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index a9d7d4408160..87d7b3ff3861 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -16,6 +16,7 @@ static inline cpumask_t *rt_overload(void) } static inline void rt_set_overload(struct rq *rq) { + rq->rt.overloaded = 1; cpu_set(rq->cpu, rt_overload_mask); /* * Make sure the mask is visible before we set @@ -32,6 +33,7 @@ static inline void rt_clear_overload(struct rq *rq) /* the order here really doesn't matter */ atomic_dec(&rto_count); cpu_clear(rq->cpu, rt_overload_mask); + rq->rt.overloaded = 0; } static void update_rt_migration(struct rq *rq) @@ -448,6 +450,9 @@ static int push_rt_task(struct rq *rq) assert_spin_locked(&rq->lock); + if (!rq->rt.overloaded) + return 0; + next_task = pick_next_highest_task_rt(rq, -1); if (!next_task) return 0; @@ -675,7 +680,7 @@ static void schedule_tail_balance_rt(struct rq *rq) * the lock was owned by prev, we need to release it * first via finish_lock_switch and then reaquire it here. */ - if (unlikely(rq->rt.rt_nr_running > 1)) { + if (unlikely(rq->rt.overloaded)) { spin_lock_irq(&rq->lock); push_rt_tasks(rq); spin_unlock_irq(&rq->lock); @@ -687,7 +692,8 @@ static void wakeup_balance_rt(struct rq *rq, struct task_struct *p) { if (unlikely(rt_task(p)) && !task_running(rq, p) && - (p->prio >= rq->curr->prio)) + (p->prio >= rq->rt.highest_prio) && + rq->rt.overloaded) push_rt_tasks(rq); } -- cgit v1.2.3-59-g8ed1b From e1f47d891c0f00769d6d40ac5740f943e998d089 Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:12 +0100 Subject: sched: RT-balance, avoid overloading This patch changes the searching for a run queue by a waking RT task to try to pick another runqueue if the currently running task is an RT task. The reason is that RT tasks behave different than normal tasks. Preempting a normal task to run a RT task to keep its cache hot is fine, because the preempted non-RT task may wait on that same runqueue to run again unless the migration thread comes along and pulls it off. RT tasks behave differently. If one is preempted, it makes an active effort to continue to run. So by having a high priority task preempt a lower priority RT task, that lower RT task will then quickly try to run on another runqueue. This will cause that lower RT task to replace its nice hot cache (and TLB) with a completely cold one. This is for the hope that the new high priority RT task will keep its cache hot. Remeber that this high priority RT task was just woken up. So it may likely have been sleeping for several milliseconds, and will end up with a cold cache anyway. RT tasks run till they voluntarily stop, or are preempted by a higher priority task. This means that it is unlikely that the woken RT task will have a hot cache to wake up to. So pushing off a lower RT task is just killing its cache for no good reason. Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 87d7b3ff3861..9becc3710b60 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -160,11 +160,23 @@ static int select_task_rq_rt(struct task_struct *p, int sync) struct rq *rq = task_rq(p); /* - * If the task will not preempt the RQ, try to find a better RQ - * before we even activate the task + * If the current task is an RT task, then + * try to see if we can wake this RT task up on another + * runqueue. Otherwise simply start this RT task + * on its current runqueue. + * + * We want to avoid overloading runqueues. Even if + * the RT task is of higher priority than the current RT task. + * RT tasks behave differently than other tasks. If + * one gets preempted, we try to push it off to another queue. + * So trying to keep a preempting RT task on the same + * cache hot CPU will force the running RT task to + * a cold CPU. So we waste all the cache for the lower + * RT task in hopes of saving some of a RT task + * that is just being woken and probably will have + * cold cache anyway. */ - if ((p->prio >= rq->rt.highest_prio) - && (p->nr_cpus_allowed > 1)) { + if (unlikely(rt_task(rq->curr))) { int cpu = find_lowest_rq(p); return (cpu == -1) ? task_cpu(p) : cpu; -- cgit v1.2.3-59-g8ed1b From 17b3279b48835eb522d842eae16f541da3729c8a Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:13 +0100 Subject: sched: break out early if RT task cannot be migrated We don't need to bother searching if the task cannot be migrated Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 9becc3710b60..72c81322fb9a 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -176,7 +176,8 @@ static int select_task_rq_rt(struct task_struct *p, int sync) * that is just being woken and probably will have * cold cache anyway. */ - if (unlikely(rt_task(rq->curr))) { + if (unlikely(rt_task(rq->curr)) && + (p->nr_cpus_allowed > 1)) { int cpu = find_lowest_rq(p); return (cpu == -1) ? task_cpu(p) : cpu; -- cgit v1.2.3-59-g8ed1b From 06f90dbd7610d51549004ea9c2ada337831eb292 Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:13 +0100 Subject: sched: RT-balance, optimize We can cheaply track the number of bits set in the cpumask for the lowest priority CPUs. Therefore, compute the mask's weight and use it to skip the optimal domain search logic when there is only one CPU available. Signed-off-by: Gregory Haskins Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 25 ++++++++++++++++++------- 1 file changed, 18 insertions(+), 7 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 72c81322fb9a..52d88f193afc 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -303,7 +303,7 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask) int cpu; cpumask_t *valid_mask = &__get_cpu_var(valid_cpu_mask); int lowest_prio = -1; - int ret = 0; + int count = 0; cpus_clear(*lowest_mask); cpus_and(*valid_mask, cpu_online_map, task->cpus_allowed); @@ -316,7 +316,7 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask) /* We look for lowest RT prio or non-rt CPU */ if (rq->rt.highest_prio >= MAX_RT_PRIO) { - if (ret) + if (count) cpus_clear(*lowest_mask); cpu_set(rq->cpu, *lowest_mask); return 1; @@ -328,14 +328,17 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask) if (rq->rt.highest_prio > lowest_prio) { /* new low - clear old data */ lowest_prio = rq->rt.highest_prio; - cpus_clear(*lowest_mask); + if (count) { + cpus_clear(*lowest_mask); + count = 0; + } } cpu_set(rq->cpu, *lowest_mask); - ret = 1; + count++; } } - return ret; + return count; } static inline int pick_optimal_cpu(int this_cpu, cpumask_t *mask) @@ -359,9 +362,17 @@ static int find_lowest_rq(struct task_struct *task) cpumask_t *lowest_mask = &__get_cpu_var(local_cpu_mask); int this_cpu = smp_processor_id(); int cpu = task_cpu(task); + int count = find_lowest_cpus(task, lowest_mask); - if (!find_lowest_cpus(task, lowest_mask)) - return -1; + if (!count) + return -1; /* No targets found */ + + /* + * There is no sense in performing an optimal search if only one + * target is found. + */ + if (count == 1) + return first_cpu(*lowest_mask); /* * At this point we have built a mask of cpus representing the -- cgit v1.2.3-59-g8ed1b From 610bf05645a7ac6ea104a474e328eeaaea148870 Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:13 +0100 Subject: sched: RT-balance, optimize cpu search This patch removes several cpumask operations by keeping track of the first of the CPUS that is of the lowest priority. When the search for the lowest priority runqueue is completed, all the bits up to the first CPU with the lowest priority runqueue is cleared. Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 49 ++++++++++++++++++++++++++++++++++++------------- 1 file changed, 36 insertions(+), 13 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 52d88f193afc..61d198845f00 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -296,29 +296,36 @@ static struct task_struct *pick_next_highest_task_rt(struct rq *rq, } static DEFINE_PER_CPU(cpumask_t, local_cpu_mask); -static DEFINE_PER_CPU(cpumask_t, valid_cpu_mask); static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask) { - int cpu; - cpumask_t *valid_mask = &__get_cpu_var(valid_cpu_mask); int lowest_prio = -1; + int lowest_cpu = -1; int count = 0; + int cpu; - cpus_clear(*lowest_mask); - cpus_and(*valid_mask, cpu_online_map, task->cpus_allowed); + cpus_and(*lowest_mask, cpu_online_map, task->cpus_allowed); /* * Scan each rq for the lowest prio. */ - for_each_cpu_mask(cpu, *valid_mask) { + for_each_cpu_mask(cpu, *lowest_mask) { struct rq *rq = cpu_rq(cpu); /* We look for lowest RT prio or non-rt CPU */ if (rq->rt.highest_prio >= MAX_RT_PRIO) { - if (count) + /* + * if we already found a low RT queue + * and now we found this non-rt queue + * clear the mask and set our bit. + * Otherwise just return the queue as is + * and the count==1 will cause the algorithm + * to use the first bit found. + */ + if (lowest_cpu != -1) { cpus_clear(*lowest_mask); - cpu_set(rq->cpu, *lowest_mask); + cpu_set(rq->cpu, *lowest_mask); + } return 1; } @@ -328,13 +335,29 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask) if (rq->rt.highest_prio > lowest_prio) { /* new low - clear old data */ lowest_prio = rq->rt.highest_prio; - if (count) { - cpus_clear(*lowest_mask); - count = 0; - } + lowest_cpu = cpu; + count = 0; } - cpu_set(rq->cpu, *lowest_mask); count++; + } else + cpu_clear(cpu, *lowest_mask); + } + + /* + * Clear out all the set bits that represent + * runqueues that were of higher prio than + * the lowest_prio. + */ + if (lowest_cpu > 0) { + /* + * Perhaps we could add another cpumask op to + * zero out bits. Like cpu_zero_bits(cpumask, nrbits); + * Then that could be optimized to use memset and such. + */ + for_each_cpu_mask(cpu, *lowest_mask) { + if (cpu >= lowest_cpu) + break; + cpu_clear(cpu, *lowest_mask); } } -- cgit v1.2.3-59-g8ed1b From 79064fbf75796c4c6a53e40729dbe52f789a91fd Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Fri, 25 Jan 2008 21:08:14 +0100 Subject: sched: clean up pick_next_highest_task_rt() clean up pick_next_highest_task_rt(). Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 61d198845f00..b8435fd47f78 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -242,8 +242,7 @@ static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) } /* Return the second highest RT task, NULL otherwise */ -static struct task_struct *pick_next_highest_task_rt(struct rq *rq, - int cpu) +static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu) { struct rt_prio_array *array = &rq->rt.active; struct task_struct *next; @@ -270,7 +269,8 @@ static struct task_struct *pick_next_highest_task_rt(struct rq *rq, if (queue->next->next != queue) { /* same prio task */ - next = list_entry(queue->next->next, struct task_struct, run_list); + next = list_entry(queue->next->next, struct task_struct, + run_list); if (pick_rt_task(rq, next, cpu)) goto out; } -- cgit v1.2.3-59-g8ed1b From 4df64c0bfb7e0e260d10ebc005f7d0ba1308eed7 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Fri, 25 Jan 2008 21:08:15 +0100 Subject: sched: clean up find_lock_lowest_rq() clean up find_lock_lowest_rq(). Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index b8435fd47f78..0749c1837b10 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -438,12 +438,11 @@ static int find_lowest_rq(struct task_struct *task) } /* Will lock the rq it finds */ -static struct rq *find_lock_lowest_rq(struct task_struct *task, - struct rq *rq) +static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq) { struct rq *lowest_rq = NULL; - int cpu; int tries; + int cpu; for (tries = 0; tries < RT_MAX_TRIES; tries++) { cpu = find_lowest_rq(task); @@ -462,9 +461,11 @@ static struct rq *find_lock_lowest_rq(struct task_struct *task, * Also make sure that it wasn't scheduled on its rq. */ if (unlikely(task_rq(task) != rq || - !cpu_isset(lowest_rq->cpu, task->cpus_allowed) || + !cpu_isset(lowest_rq->cpu, + task->cpus_allowed) || task_running(rq, task) || !task->se.on_rq)) { + spin_unlock(&lowest_rq->lock); lowest_rq = NULL; break; -- cgit v1.2.3-59-g8ed1b From deeeccd41bd94a9db133d7b923f9a7479a47305d Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Fri, 25 Jan 2008 21:08:15 +0100 Subject: sched: clean up overlong line in kernel/sched_debug.c clean up overlong line in kernel/sched_debug.c. Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 0749c1837b10..b591b89710a4 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -762,6 +762,7 @@ move_one_task_rt(struct rq *this_rq, int this_cpu, struct rq *busiest, /* don't touch RT tasks */ return 0; } + static void set_cpus_allowed_rt(struct task_struct *p, cpumask_t *new_mask) { int weight = cpus_weight(*new_mask); @@ -775,9 +776,9 @@ static void set_cpus_allowed_rt(struct task_struct *p, cpumask_t *new_mask) if (p->se.on_rq && (weight != p->nr_cpus_allowed)) { struct rq *rq = task_rq(p); - if ((p->nr_cpus_allowed <= 1) && (weight > 1)) + if ((p->nr_cpus_allowed <= 1) && (weight > 1)) { rq->rt.rt_nr_migratory++; - else if((p->nr_cpus_allowed > 1) && (weight <= 1)) { + } else if ((p->nr_cpus_allowed > 1) && (weight <= 1)) { BUG_ON(!rq->rt.rt_nr_migratory); rq->rt.rt_nr_migratory--; } @@ -788,6 +789,7 @@ static void set_cpus_allowed_rt(struct task_struct *p, cpumask_t *new_mask) p->cpus_allowed = *new_mask; p->nr_cpus_allowed = weight; } + #else /* CONFIG_SMP */ # define schedule_tail_balance_rt(rq) do { } while (0) # define schedule_balance_rt(rq, prev) do { } while (0) -- cgit v1.2.3-59-g8ed1b From 84de4274893691aa8c471a1f7336d51e555d23a0 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Fri, 25 Jan 2008 21:08:15 +0100 Subject: sched: clean up kernel/sched_rt.c clean up whitespace damage and missing comments in kernel/sched_rt.c. Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 9 +++++++++ 1 file changed, 9 insertions(+) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index b591b89710a4..1a2d8f0aa659 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -4,16 +4,24 @@ */ #ifdef CONFIG_SMP + +/* + * The "RT overload" flag: it gets set if a CPU has more than + * one runnable RT task. + */ static cpumask_t rt_overload_mask; static atomic_t rto_count; + static inline int rt_overloaded(void) { return atomic_read(&rto_count); } + static inline cpumask_t *rt_overload(void) { return &rt_overload_mask; } + static inline void rt_set_overload(struct rq *rq) { rq->rt.overloaded = 1; @@ -28,6 +36,7 @@ static inline void rt_set_overload(struct rq *rq) wmb(); atomic_inc(&rto_count); } + static inline void rt_clear_overload(struct rq *rq) { /* the order here really doesn't matter */ -- cgit v1.2.3-59-g8ed1b From 6e1938d3ad58c940ec4119d387dd92a787cb238c Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Fri, 25 Jan 2008 21:08:16 +0100 Subject: sched: remove rt_overload() remove rt_overload() - it's an unnecessary indirection. Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 10 +--------- 1 file changed, 1 insertion(+), 9 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 1a2d8f0aa659..deff0c77d705 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -17,11 +17,6 @@ static inline int rt_overloaded(void) return atomic_read(&rto_count); } -static inline cpumask_t *rt_overload(void) -{ - return &rt_overload_mask; -} - static inline void rt_set_overload(struct rq *rq) { rq->rt.overloaded = 1; @@ -590,7 +585,6 @@ static int pull_rt_task(struct rq *this_rq) struct task_struct *next; struct task_struct *p; struct rq *src_rq; - cpumask_t *rto_cpumask; int this_cpu = this_rq->cpu; int cpu; int ret = 0; @@ -608,9 +602,7 @@ static int pull_rt_task(struct rq *this_rq) next = pick_next_task_rt(this_rq); - rto_cpumask = rt_overload(); - - for_each_cpu_mask(cpu, *rto_cpumask) { + for_each_cpu_mask(cpu, rt_overload_mask) { if (this_cpu == cpu) continue; -- cgit v1.2.3-59-g8ed1b From 00597c3ed78e424bdafff123565c078d8b6088cf Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Fri, 25 Jan 2008 21:08:16 +0100 Subject: sched: remove leftover debugging remove leftover debugging. Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 8 -------- 1 file changed, 8 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index deff0c77d705..cc38521c5723 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -253,8 +253,6 @@ static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu) struct list_head *queue; int idx; - assert_spin_locked(&rq->lock); - if (likely(rq->rt.rt_nr_running < 2)) return NULL; @@ -500,8 +498,6 @@ static int push_rt_task(struct rq *rq) int ret = 0; int paranoid = RT_MAX_TRIES; - assert_spin_locked(&rq->lock); - if (!rq->rt.overloaded) return 0; @@ -546,8 +542,6 @@ static int push_rt_task(struct rq *rq) goto out; } - assert_spin_locked(&lowest_rq->lock); - deactivate_task(rq, next_task, 0); set_task_cpu(next_task, lowest_rq->cpu); activate_task(lowest_rq, next_task, 0); @@ -589,8 +583,6 @@ static int pull_rt_task(struct rq *this_rq) int cpu; int ret = 0; - assert_spin_locked(&this_rq->lock); - /* * If cpusets are used, and we have overlapping * run queue cpusets, then this algorithm may not catch all. -- cgit v1.2.3-59-g8ed1b From 80bf3171dcdf0f5d236e2e48afe2a95c7ce23879 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Fri, 25 Jan 2008 21:08:17 +0100 Subject: sched: clean up pull_rt_task() clean up pull_rt_task(). Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 22 ++++++++++------------ 1 file changed, 10 insertions(+), 12 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index cc38521c5723..05ada7d44800 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -576,12 +576,9 @@ static void push_rt_tasks(struct rq *rq) static int pull_rt_task(struct rq *this_rq) { - struct task_struct *next; - struct task_struct *p; + int this_cpu = this_rq->cpu, ret = 0, cpu; + struct task_struct *p, *next; struct rq *src_rq; - int this_cpu = this_rq->cpu; - int cpu; - int ret = 0; /* * If cpusets are used, and we have overlapping @@ -608,23 +605,25 @@ static int pull_rt_task(struct rq *this_rq) if (double_lock_balance(this_rq, src_rq)) { /* unlocked our runqueue lock */ struct task_struct *old_next = next; + next = pick_next_task_rt(this_rq); if (next != old_next) ret = 1; } - if (likely(src_rq->rt.rt_nr_running <= 1)) + if (likely(src_rq->rt.rt_nr_running <= 1)) { /* * Small chance that this_rq->curr changed * but it's really harmless here. */ rt_clear_overload(this_rq); - else + } else { /* * Heh, the src_rq is now overloaded, since * we already have the src_rq lock, go straight * to pulling tasks from it. */ goto try_pulling; + } spin_unlock(&src_rq->lock); continue; } @@ -638,6 +637,7 @@ static int pull_rt_task(struct rq *this_rq) */ if (double_lock_balance(this_rq, src_rq)) { struct task_struct *old_next = next; + next = pick_next_task_rt(this_rq); if (next != old_next) ret = 1; @@ -674,7 +674,7 @@ static int pull_rt_task(struct rq *this_rq) */ if (p->prio < src_rq->curr->prio || (next && next->prio < src_rq->curr->prio)) - goto bail; + goto out; ret = 1; @@ -686,9 +686,7 @@ static int pull_rt_task(struct rq *this_rq) * case there's an even higher prio task * in another runqueue. (low likelyhood * but possible) - */ - - /* + * * Update next so that we won't pick a task * on another cpu with a priority lower (or equal) * than the one we just picked. @@ -696,7 +694,7 @@ static int pull_rt_task(struct rq *this_rq) next = p; } - bail: + out: spin_unlock(&src_rq->lock); } -- cgit v1.2.3-59-g8ed1b From 7f51f298204ec0528422cd9b23feac12612c5665 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Fri, 25 Jan 2008 21:08:17 +0100 Subject: sched: clean up schedule_balance_rt() clean up schedule_balance_rt(). Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 05ada7d44800..4d0a60e47dfa 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -701,12 +701,10 @@ static int pull_rt_task(struct rq *this_rq) return ret; } -static void schedule_balance_rt(struct rq *rq, - struct task_struct *prev) +static void schedule_balance_rt(struct rq *rq, struct task_struct *prev) { /* Try to pull RT tasks here if we lower this rq's prio */ - if (unlikely(rt_task(prev)) && - rq->rt.highest_prio > prev->prio) + if (unlikely(rt_task(prev)) && rq->rt.highest_prio > prev->prio) pull_rt_task(rq); } -- cgit v1.2.3-59-g8ed1b From 637f50851b57a32f7ec67c50fc16f1601ab1a87a Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:18 +0100 Subject: sched: only balance our RT tasks within our domain We move the rt-overload data as the first global to per-domain reclassification. This limits the scope of overload related cache-line bouncing to stay with a specified partition instead of affecting all cpus in the system. Finally, we limit the scope of find_lowest_cpu searches to the domain instead of the entire system. Note that we would always respect domain boundaries even without this patch, but we first would scan potentially all cpus before whittling the list down. Now we can avoid looking at RQs that are out of scope, again reducing cache-line hits. Note: In some cases, task->cpus_allowed will effectively reduce our search to within our domain. However, I believe there are cases where the cpus_allowed mask may be all ones and therefore we err on the side of caution. If it can be optimized later, so be it. Signed-off-by: Gregory Haskins CC: Christoph Lameter Signed-off-by: Ingo Molnar --- kernel/sched.c | 7 +++++++ kernel/sched_rt.c | 57 ++++++++++++++++++++++++++++++------------------------- 2 files changed, 38 insertions(+), 26 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched.c b/kernel/sched.c index 34b7d721d735..35ef06c99214 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -365,6 +365,13 @@ struct root_domain { atomic_t refcount; cpumask_t span; cpumask_t online; + + /* + * The "RT overload" flag: it gets set if a CPU has more than + * one runnable RT task. + */ + cpumask_t rto_mask; + atomic_t rto_count; }; static struct root_domain def_root_domain; diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 4d0a60e47dfa..b049e5110eea 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -5,22 +5,14 @@ #ifdef CONFIG_SMP -/* - * The "RT overload" flag: it gets set if a CPU has more than - * one runnable RT task. - */ -static cpumask_t rt_overload_mask; -static atomic_t rto_count; - -static inline int rt_overloaded(void) +static inline int rt_overloaded(struct rq *rq) { - return atomic_read(&rto_count); + return atomic_read(&rq->rd->rto_count); } static inline void rt_set_overload(struct rq *rq) { - rq->rt.overloaded = 1; - cpu_set(rq->cpu, rt_overload_mask); + cpu_set(rq->cpu, rq->rd->rto_mask); /* * Make sure the mask is visible before we set * the overload count. That is checked to determine @@ -29,23 +21,25 @@ static inline void rt_set_overload(struct rq *rq) * updated yet. */ wmb(); - atomic_inc(&rto_count); + atomic_inc(&rq->rd->rto_count); } static inline void rt_clear_overload(struct rq *rq) { /* the order here really doesn't matter */ - atomic_dec(&rto_count); - cpu_clear(rq->cpu, rt_overload_mask); - rq->rt.overloaded = 0; + atomic_dec(&rq->rd->rto_count); + cpu_clear(rq->cpu, rq->rd->rto_mask); } static void update_rt_migration(struct rq *rq) { - if (rq->rt.rt_nr_migratory && (rq->rt.rt_nr_running > 1)) + if (rq->rt.rt_nr_migratory && (rq->rt.rt_nr_running > 1)) { rt_set_overload(rq); - else + rq->rt.overloaded = 1; + } else { rt_clear_overload(rq); + rq->rt.overloaded = 0; + } } #endif /* CONFIG_SMP */ @@ -306,7 +300,7 @@ static int find_lowest_cpus(struct task_struct *task, cpumask_t *lowest_mask) int count = 0; int cpu; - cpus_and(*lowest_mask, cpu_online_map, task->cpus_allowed); + cpus_and(*lowest_mask, task_rq(task)->rd->online, task->cpus_allowed); /* * Scan each rq for the lowest prio. @@ -580,18 +574,12 @@ static int pull_rt_task(struct rq *this_rq) struct task_struct *p, *next; struct rq *src_rq; - /* - * If cpusets are used, and we have overlapping - * run queue cpusets, then this algorithm may not catch all. - * This is just the price you pay on trying to keep - * dirtying caches down on large SMP machines. - */ - if (likely(!rt_overloaded())) + if (likely(!rt_overloaded(this_rq))) return 0; next = pick_next_task_rt(this_rq); - for_each_cpu_mask(cpu, rt_overload_mask) { + for_each_cpu_mask(cpu, this_rq->rd->rto_mask) { if (this_cpu == cpu) continue; @@ -811,6 +799,20 @@ static void task_tick_rt(struct rq *rq, struct task_struct *p) } } +/* Assumes rq->lock is held */ +static void join_domain_rt(struct rq *rq) +{ + if (rq->rt.overloaded) + rt_set_overload(rq); +} + +/* Assumes rq->lock is held */ +static void leave_domain_rt(struct rq *rq) +{ + if (rq->rt.overloaded) + rt_clear_overload(rq); +} + static void set_curr_task_rt(struct rq *rq) { struct task_struct *p = rq->curr; @@ -840,4 +842,7 @@ const struct sched_class rt_sched_class = { .set_curr_task = set_curr_task_rt, .task_tick = task_tick_rt, + + .join_domain = join_domain_rt, + .leave_domain = leave_domain_rt, }; -- cgit v1.2.3-59-g8ed1b From bdd7c81b4973e72b670eff6b5725bab189b723d6 Mon Sep 17 00:00:00 2001 From: Ingo Molnar Date: Fri, 25 Jan 2008 21:08:18 +0100 Subject: sched: fix sched_rt.c:join/leave_domain fix build bug in sched_rt.c:join/leave_domain and make them only be included on SMP builds. Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 33 ++++++++++++++++----------------- 1 file changed, 16 insertions(+), 17 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index b049e5110eea..3ea0cae513d2 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -767,6 +767,20 @@ static void set_cpus_allowed_rt(struct task_struct *p, cpumask_t *new_mask) p->nr_cpus_allowed = weight; } +/* Assumes rq->lock is held */ +static void join_domain_rt(struct rq *rq) +{ + if (rq->rt.overloaded) + rt_set_overload(rq); +} + +/* Assumes rq->lock is held */ +static void leave_domain_rt(struct rq *rq) +{ + if (rq->rt.overloaded) + rt_clear_overload(rq); +} + #else /* CONFIG_SMP */ # define schedule_tail_balance_rt(rq) do { } while (0) # define schedule_balance_rt(rq, prev) do { } while (0) @@ -799,20 +813,6 @@ static void task_tick_rt(struct rq *rq, struct task_struct *p) } } -/* Assumes rq->lock is held */ -static void join_domain_rt(struct rq *rq) -{ - if (rq->rt.overloaded) - rt_set_overload(rq); -} - -/* Assumes rq->lock is held */ -static void leave_domain_rt(struct rq *rq) -{ - if (rq->rt.overloaded) - rt_clear_overload(rq); -} - static void set_curr_task_rt(struct rq *rq) { struct task_struct *p = rq->curr; @@ -838,11 +838,10 @@ const struct sched_class rt_sched_class = { .load_balance = load_balance_rt, .move_one_task = move_one_task_rt, .set_cpus_allowed = set_cpus_allowed_rt, + .join_domain = join_domain_rt, + .leave_domain = leave_domain_rt, #endif .set_curr_task = set_curr_task_rt, .task_tick = task_tick_rt, - - .join_domain = join_domain_rt, - .leave_domain = leave_domain_rt, }; -- cgit v1.2.3-59-g8ed1b From 9a897c5a6701bcb6f099f7ca20194999102729fd Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:22 +0100 Subject: sched: RT-balance, replace hooks with pre/post schedule and wakeup methods To make the main sched.c code more agnostic to the schedule classes. Instead of having specific hooks in the schedule code for the RT class balancing. They are replaced with a pre_schedule, post_schedule and task_wake_up methods. These methods may be used by any of the classes but currently, only the sched_rt class implements them. Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- include/linux/sched.h | 3 +++ kernel/sched.c | 20 ++++++++++++++++---- kernel/sched_rt.c | 17 +++++++---------- 3 files changed, 26 insertions(+), 14 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/include/linux/sched.h b/include/linux/sched.h index 2e69f19369e4..c67d2c2f0111 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -843,6 +843,9 @@ struct sched_class { int (*move_one_task) (struct rq *this_rq, int this_cpu, struct rq *busiest, struct sched_domain *sd, enum cpu_idle_type idle); + void (*pre_schedule) (struct rq *this_rq, struct task_struct *task); + void (*post_schedule) (struct rq *this_rq); + void (*task_wake_up) (struct rq *this_rq, struct task_struct *task); #endif void (*set_curr_task) (struct rq *rq); diff --git a/kernel/sched.c b/kernel/sched.c index 9d6fb731559b..2368a0d882e3 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -1625,7 +1625,10 @@ out_activate: out_running: p->state = TASK_RUNNING; - wakeup_balance_rt(rq, p); +#ifdef CONFIG_SMP + if (p->sched_class->task_wake_up) + p->sched_class->task_wake_up(rq, p); +#endif out: task_rq_unlock(rq, &flags); @@ -1748,7 +1751,10 @@ void fastcall wake_up_new_task(struct task_struct *p, unsigned long clone_flags) inc_nr_running(p, rq); } check_preempt_curr(rq, p); - wakeup_balance_rt(rq, p); +#ifdef CONFIG_SMP + if (p->sched_class->task_wake_up) + p->sched_class->task_wake_up(rq, p); +#endif task_rq_unlock(rq, &flags); } @@ -1869,7 +1875,10 @@ static void finish_task_switch(struct rq *rq, struct task_struct *prev) prev_state = prev->state; finish_arch_switch(prev); finish_lock_switch(rq, prev); - schedule_tail_balance_rt(rq); +#ifdef CONFIG_SMP + if (current->sched_class->post_schedule) + current->sched_class->post_schedule(rq); +#endif fire_sched_in_preempt_notifiers(current); if (mm) @@ -3638,7 +3647,10 @@ need_resched_nonpreemptible: switch_count = &prev->nvcsw; } - schedule_balance_rt(rq, prev); +#ifdef CONFIG_SMP + if (prev->sched_class->pre_schedule) + prev->sched_class->pre_schedule(rq, prev); +#endif if (unlikely(!rq->nr_running)) idle_balance(cpu, rq); diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 3ea0cae513d2..a5a45104603a 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -689,14 +689,14 @@ static int pull_rt_task(struct rq *this_rq) return ret; } -static void schedule_balance_rt(struct rq *rq, struct task_struct *prev) +static void pre_schedule_rt(struct rq *rq, struct task_struct *prev) { /* Try to pull RT tasks here if we lower this rq's prio */ if (unlikely(rt_task(prev)) && rq->rt.highest_prio > prev->prio) pull_rt_task(rq); } -static void schedule_tail_balance_rt(struct rq *rq) +static void post_schedule_rt(struct rq *rq) { /* * If we have more than one rt_task queued, then @@ -713,10 +713,9 @@ static void schedule_tail_balance_rt(struct rq *rq) } -static void wakeup_balance_rt(struct rq *rq, struct task_struct *p) +static void task_wake_up_rt(struct rq *rq, struct task_struct *p) { - if (unlikely(rt_task(p)) && - !task_running(rq, p) && + if (!task_running(rq, p) && (p->prio >= rq->rt.highest_prio) && rq->rt.overloaded) push_rt_tasks(rq); @@ -780,11 +779,6 @@ static void leave_domain_rt(struct rq *rq) if (rq->rt.overloaded) rt_clear_overload(rq); } - -#else /* CONFIG_SMP */ -# define schedule_tail_balance_rt(rq) do { } while (0) -# define schedule_balance_rt(rq, prev) do { } while (0) -# define wakeup_balance_rt(rq, p) do { } while (0) #endif /* CONFIG_SMP */ static void task_tick_rt(struct rq *rq, struct task_struct *p) @@ -840,6 +834,9 @@ const struct sched_class rt_sched_class = { .set_cpus_allowed = set_cpus_allowed_rt, .join_domain = join_domain_rt, .leave_domain = leave_domain_rt, + .pre_schedule = pre_schedule_rt, + .post_schedule = post_schedule_rt, + .task_wake_up = task_wake_up_rt, #endif .set_curr_task = set_curr_task_rt, -- cgit v1.2.3-59-g8ed1b From cb46984504048db946cd551c261df4e70d59a8ea Mon Sep 17 00:00:00 2001 From: Steven Rostedt Date: Fri, 25 Jan 2008 21:08:22 +0100 Subject: sched: RT-balance, add new methods to sched_class Dmitry Adamushko found that the current implementation of the RT balancing code left out changes to the sched_setscheduler and rt_mutex_setprio. This patch addresses this issue by adding methods to the schedule classes to handle being switched out of (switched_from) and being switched into (switched_to) a sched_class. Also a method for changing of priorities is also added (prio_changed). This patch also removes some duplicate logic between rt_mutex_setprio and sched_setscheduler. Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- include/linux/sched.h | 7 ++++ kernel/sched.c | 42 +++++++++++------------ kernel/sched_fair.c | 39 ++++++++++++++++++++++ kernel/sched_idletask.c | 31 +++++++++++++++++ kernel/sched_rt.c | 89 +++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 186 insertions(+), 22 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/include/linux/sched.h b/include/linux/sched.h index c67d2c2f0111..f2044e707004 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -855,6 +855,13 @@ struct sched_class { void (*join_domain)(struct rq *rq); void (*leave_domain)(struct rq *rq); + + void (*switched_from) (struct rq *this_rq, struct task_struct *task, + int running); + void (*switched_to) (struct rq *this_rq, struct task_struct *task, + int running); + void (*prio_changed) (struct rq *this_rq, struct task_struct *task, + int oldprio, int running); }; struct load_weight { diff --git a/kernel/sched.c b/kernel/sched.c index 2368a0d882e3..5834c7fb79a5 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -1152,6 +1152,18 @@ static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu) #endif } +static inline void check_class_changed(struct rq *rq, struct task_struct *p, + const struct sched_class *prev_class, + int oldprio, int running) +{ + if (prev_class != p->sched_class) { + if (prev_class->switched_from) + prev_class->switched_from(rq, p, running); + p->sched_class->switched_to(rq, p, running); + } else + p->sched_class->prio_changed(rq, p, oldprio, running); +} + #ifdef CONFIG_SMP /* @@ -4017,6 +4029,7 @@ void rt_mutex_setprio(struct task_struct *p, int prio) unsigned long flags; int oldprio, on_rq, running; struct rq *rq; + const struct sched_class *prev_class = p->sched_class; BUG_ON(prio < 0 || prio > MAX_PRIO); @@ -4042,18 +4055,10 @@ void rt_mutex_setprio(struct task_struct *p, int prio) if (on_rq) { if (running) p->sched_class->set_curr_task(rq); + enqueue_task(rq, p, 0); - /* - * Reschedule if we are currently running on this runqueue and - * our priority decreased, or if we are not currently running on - * this runqueue and our priority is higher than the current's - */ - if (running) { - if (p->prio > oldprio) - resched_task(rq->curr); - } else { - check_preempt_curr(rq, p); - } + + check_class_changed(rq, p, prev_class, oldprio, running); } task_rq_unlock(rq, &flags); } @@ -4253,6 +4258,7 @@ int sched_setscheduler(struct task_struct *p, int policy, { int retval, oldprio, oldpolicy = -1, on_rq, running; unsigned long flags; + const struct sched_class *prev_class = p->sched_class; struct rq *rq; /* may grab non-irq protected spin_locks */ @@ -4346,18 +4352,10 @@ recheck: if (on_rq) { if (running) p->sched_class->set_curr_task(rq); + activate_task(rq, p, 0); - /* - * Reschedule if we are currently running on this runqueue and - * our priority decreased, or if we are not currently running on - * this runqueue and our priority is higher than the current's - */ - if (running) { - if (p->prio > oldprio) - resched_task(rq->curr); - } else { - check_preempt_curr(rq, p); - } + + check_class_changed(rq, p, prev_class, oldprio, running); } __task_rq_unlock(rq); spin_unlock_irqrestore(&p->pi_lock, flags); diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c index 10aa6e1ae3dd..dfa18d55561d 100644 --- a/kernel/sched_fair.c +++ b/kernel/sched_fair.c @@ -1280,6 +1280,42 @@ static void task_new_fair(struct rq *rq, struct task_struct *p) resched_task(rq->curr); } +/* + * Priority of the task has changed. Check to see if we preempt + * the current task. + */ +static void prio_changed_fair(struct rq *rq, struct task_struct *p, + int oldprio, int running) +{ + /* + * Reschedule if we are currently running on this runqueue and + * our priority decreased, or if we are not currently running on + * this runqueue and our priority is higher than the current's + */ + if (running) { + if (p->prio > oldprio) + resched_task(rq->curr); + } else + check_preempt_curr(rq, p); +} + +/* + * We switched to the sched_fair class. + */ +static void switched_to_fair(struct rq *rq, struct task_struct *p, + int running) +{ + /* + * We were most likely switched from sched_rt, so + * kick off the schedule if running, otherwise just see + * if we can still preempt the current task. + */ + if (running) + resched_task(rq->curr); + else + check_preempt_curr(rq, p); +} + /* Account for a task changing its policy or group. * * This routine is mostly called to set cfs_rq->curr field when a task @@ -1318,6 +1354,9 @@ static const struct sched_class fair_sched_class = { .set_curr_task = set_curr_task_fair, .task_tick = task_tick_fair, .task_new = task_new_fair, + + .prio_changed = prio_changed_fair, + .switched_to = switched_to_fair, }; #ifdef CONFIG_SCHED_DEBUG diff --git a/kernel/sched_idletask.c b/kernel/sched_idletask.c index ca5374860aef..ef7a2661fa10 100644 --- a/kernel/sched_idletask.c +++ b/kernel/sched_idletask.c @@ -69,6 +69,33 @@ static void set_curr_task_idle(struct rq *rq) { } +static void switched_to_idle(struct rq *rq, struct task_struct *p, + int running) +{ + /* Can this actually happen?? */ + if (running) + resched_task(rq->curr); + else + check_preempt_curr(rq, p); +} + +static void prio_changed_idle(struct rq *rq, struct task_struct *p, + int oldprio, int running) +{ + /* This can happen for hot plug CPUS */ + + /* + * Reschedule if we are currently running on this runqueue and + * our priority decreased, or if we are not currently running on + * this runqueue and our priority is higher than the current's + */ + if (running) { + if (p->prio > oldprio) + resched_task(rq->curr); + } else + check_preempt_curr(rq, p); +} + /* * Simple, special scheduling class for the per-CPU idle tasks: */ @@ -94,5 +121,9 @@ const struct sched_class idle_sched_class = { .set_curr_task = set_curr_task_idle, .task_tick = task_tick_idle, + + .prio_changed = prio_changed_idle, + .switched_to = switched_to_idle, + /* no .task_new for idle tasks */ }; diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index a5a45104603a..57fa3d96847b 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -779,7 +779,92 @@ static void leave_domain_rt(struct rq *rq) if (rq->rt.overloaded) rt_clear_overload(rq); } + +/* + * When switch from the rt queue, we bring ourselves to a position + * that we might want to pull RT tasks from other runqueues. + */ +static void switched_from_rt(struct rq *rq, struct task_struct *p, + int running) +{ + /* + * If there are other RT tasks then we will reschedule + * and the scheduling of the other RT tasks will handle + * the balancing. But if we are the last RT task + * we may need to handle the pulling of RT tasks + * now. + */ + if (!rq->rt.rt_nr_running) + pull_rt_task(rq); +} +#endif /* CONFIG_SMP */ + +/* + * When switching a task to RT, we may overload the runqueue + * with RT tasks. In this case we try to push them off to + * other runqueues. + */ +static void switched_to_rt(struct rq *rq, struct task_struct *p, + int running) +{ + int check_resched = 1; + + /* + * If we are already running, then there's nothing + * that needs to be done. But if we are not running + * we may need to preempt the current running task. + * If that current running task is also an RT task + * then see if we can move to another run queue. + */ + if (!running) { +#ifdef CONFIG_SMP + if (rq->rt.overloaded && push_rt_task(rq) && + /* Don't resched if we changed runqueues */ + rq != task_rq(p)) + check_resched = 0; +#endif /* CONFIG_SMP */ + if (check_resched && p->prio < rq->curr->prio) + resched_task(rq->curr); + } +} + +/* + * Priority of the task has changed. This may cause + * us to initiate a push or pull. + */ +static void prio_changed_rt(struct rq *rq, struct task_struct *p, + int oldprio, int running) +{ + if (running) { +#ifdef CONFIG_SMP + /* + * If our priority decreases while running, we + * may need to pull tasks to this runqueue. + */ + if (oldprio < p->prio) + pull_rt_task(rq); + /* + * If there's a higher priority task waiting to run + * then reschedule. + */ + if (p->prio > rq->rt.highest_prio) + resched_task(p); +#else + /* For UP simply resched on drop of prio */ + if (oldprio < p->prio) + resched_task(p); #endif /* CONFIG_SMP */ + } else { + /* + * This task is not running, but if it is + * greater than the current running task + * then reschedule. + */ + if (p->prio < rq->curr->prio) + resched_task(rq->curr); + } +} + static void task_tick_rt(struct rq *rq, struct task_struct *p) { @@ -837,8 +922,12 @@ const struct sched_class rt_sched_class = { .pre_schedule = pre_schedule_rt, .post_schedule = post_schedule_rt, .task_wake_up = task_wake_up_rt, + .switched_from = switched_from_rt, #endif .set_curr_task = set_curr_task_rt, .task_tick = task_tick_rt, + + .prio_changed = prio_changed_rt, + .switched_to = switched_to_rt, }; -- cgit v1.2.3-59-g8ed1b From cdc8eb984ce47a7c90a049f45229f7b0d59ba781 Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:23 +0100 Subject: sched: RT-balance, only adjust overload state when changing The overload set/clears were originally idempotent when this logic was first implemented. But that is no longer true due to the addition of the atomic counter and this logic was never updated to work properly with that change. So only adjust the overload state if it is actually changing to avoid getting out of sync. Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 57fa3d96847b..a386758ffebb 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -34,9 +34,11 @@ static inline void rt_clear_overload(struct rq *rq) static void update_rt_migration(struct rq *rq) { if (rq->rt.rt_nr_migratory && (rq->rt.rt_nr_running > 1)) { - rt_set_overload(rq); - rq->rt.overloaded = 1; - } else { + if (!rq->rt.overloaded) { + rt_set_overload(rq); + rq->rt.overloaded = 1; + } + } else if (rq->rt.overloaded) { rt_clear_overload(rq); rq->rt.overloaded = 0; } -- cgit v1.2.3-59-g8ed1b From c49443c538c1bbf50eda27e4a3711e9fc15176b0 Mon Sep 17 00:00:00 2001 From: Gregory Haskins Date: Fri, 25 Jan 2008 21:08:23 +0100 Subject: sched: remove some old cpuset logic We had support for overlapping cpuset based rto logic in early prototypes that is no longer used, so remove it. Signed-off-by: Gregory Haskins Signed-off-by: Steven Rostedt Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 33 --------------------------------- 1 file changed, 33 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index a386758ffebb..9affb3c9d3db 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -586,38 +586,6 @@ static int pull_rt_task(struct rq *this_rq) continue; src_rq = cpu_rq(cpu); - if (unlikely(src_rq->rt.rt_nr_running <= 1)) { - /* - * It is possible that overlapping cpusets - * will miss clearing a non overloaded runqueue. - * Clear it now. - */ - if (double_lock_balance(this_rq, src_rq)) { - /* unlocked our runqueue lock */ - struct task_struct *old_next = next; - - next = pick_next_task_rt(this_rq); - if (next != old_next) - ret = 1; - } - if (likely(src_rq->rt.rt_nr_running <= 1)) { - /* - * Small chance that this_rq->curr changed - * but it's really harmless here. - */ - rt_clear_overload(this_rq); - } else { - /* - * Heh, the src_rq is now overloaded, since - * we already have the src_rq lock, go straight - * to pulling tasks from it. - */ - goto try_pulling; - } - spin_unlock(&src_rq->lock); - continue; - } - /* * We can potentially drop this_rq's lock in * double_lock_balance, and another CPU could @@ -641,7 +609,6 @@ static int pull_rt_task(struct rq *this_rq) continue; } - try_pulling: p = pick_next_highest_task_rt(src_rq, this_cpu); /* -- cgit v1.2.3-59-g8ed1b From fa717060f1ab7eb6570f2fb49136f838fc9195a9 Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Fri, 25 Jan 2008 21:08:27 +0100 Subject: sched: sched_rt_entity Move the task_struct members specific to rt scheduling together. A future optimization could be to put sched_entity and sched_rt_entity into a union. Signed-off-by: Peter Zijlstra CC: Srivatsa Vaddagiri Signed-off-by: Ingo Molnar --- include/linux/init_task.h | 5 +++-- include/linux/sched.h | 8 ++++++-- kernel/sched.c | 2 +- kernel/sched_rt.c | 20 ++++++++++---------- mm/oom_kill.c | 2 +- 5 files changed, 21 insertions(+), 16 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/include/linux/init_task.h b/include/linux/init_task.h index 572c65bcc80f..ee65d87bedb7 100644 --- a/include/linux/init_task.h +++ b/include/linux/init_task.h @@ -133,9 +133,10 @@ extern struct group_info init_groups; .nr_cpus_allowed = NR_CPUS, \ .mm = NULL, \ .active_mm = &init_mm, \ - .run_list = LIST_HEAD_INIT(tsk.run_list), \ + .rt = { \ + .run_list = LIST_HEAD_INIT(tsk.rt.run_list), \ + .time_slice = HZ, }, \ .ioprio = 0, \ - .time_slice = HZ, \ .tasks = LIST_HEAD_INIT(tsk.tasks), \ .ptrace_children= LIST_HEAD_INIT(tsk.ptrace_children), \ .ptrace_list = LIST_HEAD_INIT(tsk.ptrace_list), \ diff --git a/include/linux/sched.h b/include/linux/sched.h index 72e1b8ecfbe1..a06d09ebd5c6 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -929,6 +929,11 @@ struct sched_entity { #endif }; +struct sched_rt_entity { + struct list_head run_list; + unsigned int time_slice; +}; + struct task_struct { volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */ void *stack; @@ -945,9 +950,9 @@ struct task_struct { #endif int prio, static_prio, normal_prio; - struct list_head run_list; const struct sched_class *sched_class; struct sched_entity se; + struct sched_rt_entity rt; #ifdef CONFIG_PREEMPT_NOTIFIERS /* list of struct preempt_notifier: */ @@ -972,7 +977,6 @@ struct task_struct { unsigned int policy; cpumask_t cpus_allowed; int nr_cpus_allowed; - unsigned int time_slice; #ifdef CONFIG_PREEMPT_RCU int rcu_read_lock_nesting; diff --git a/kernel/sched.c b/kernel/sched.c index 02d468844a91..c2cedd09d895 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -1685,7 +1685,7 @@ static void __sched_fork(struct task_struct *p) p->se.wait_max = 0; #endif - INIT_LIST_HEAD(&p->run_list); + INIT_LIST_HEAD(&p->rt.run_list); p->se.on_rq = 0; #ifdef CONFIG_PREEMPT_NOTIFIERS diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 9affb3c9d3db..29963af782ae 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -111,7 +111,7 @@ static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup) { struct rt_prio_array *array = &rq->rt.active; - list_add_tail(&p->run_list, array->queue + p->prio); + list_add_tail(&p->rt.run_list, array->queue + p->prio); __set_bit(p->prio, array->bitmap); inc_cpu_load(rq, p->se.load.weight); @@ -127,7 +127,7 @@ static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep) update_curr_rt(rq); - list_del(&p->run_list); + list_del(&p->rt.run_list); if (list_empty(array->queue + p->prio)) __clear_bit(p->prio, array->bitmap); dec_cpu_load(rq, p->se.load.weight); @@ -143,7 +143,7 @@ static void requeue_task_rt(struct rq *rq, struct task_struct *p) { struct rt_prio_array *array = &rq->rt.active; - list_move_tail(&p->run_list, array->queue + p->prio); + list_move_tail(&p->rt.run_list, array->queue + p->prio); } static void @@ -212,7 +212,7 @@ static struct task_struct *pick_next_task_rt(struct rq *rq) return NULL; queue = array->queue + idx; - next = list_entry(queue->next, struct task_struct, run_list); + next = list_entry(queue->next, struct task_struct, rt.run_list); next->se.exec_start = rq->clock; @@ -261,14 +261,14 @@ static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu) queue = array->queue + idx; BUG_ON(list_empty(queue)); - next = list_entry(queue->next, struct task_struct, run_list); + next = list_entry(queue->next, struct task_struct, rt.run_list); if (unlikely(pick_rt_task(rq, next, cpu))) goto out; if (queue->next->next != queue) { /* same prio task */ next = list_entry(queue->next->next, struct task_struct, - run_list); + rt.run_list); if (pick_rt_task(rq, next, cpu)) goto out; } @@ -282,7 +282,7 @@ static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu) queue = array->queue + idx; BUG_ON(list_empty(queue)); - list_for_each_entry(next, queue, run_list) { + list_for_each_entry(next, queue, rt.run_list) { if (pick_rt_task(rq, next, cpu)) goto out; } @@ -846,16 +846,16 @@ static void task_tick_rt(struct rq *rq, struct task_struct *p) if (p->policy != SCHED_RR) return; - if (--p->time_slice) + if (--p->rt.time_slice) return; - p->time_slice = DEF_TIMESLICE; + p->rt.time_slice = DEF_TIMESLICE; /* * Requeue to the end of queue if we are not the only element * on the queue: */ - if (p->run_list.prev != p->run_list.next) { + if (p->rt.run_list.prev != p->rt.run_list.next) { requeue_task_rt(rq, p); set_tsk_need_resched(p); } diff --git a/mm/oom_kill.c b/mm/oom_kill.c index 91a081a82f55..96473b482099 100644 --- a/mm/oom_kill.c +++ b/mm/oom_kill.c @@ -286,7 +286,7 @@ static void __oom_kill_task(struct task_struct *p, int verbose) * all the memory it needs. That way it should be able to * exit() and clear out its resources quickly... */ - p->time_slice = HZ; + p->rt.time_slice = HZ; set_tsk_thread_flag(p, TIF_MEMDIE); force_sig(SIGKILL, p); -- cgit v1.2.3-59-g8ed1b From 78f2c7db6068fd6ef75b8c120f04a388848eacb5 Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Fri, 25 Jan 2008 21:08:27 +0100 Subject: sched: SCHED_FIFO/SCHED_RR watchdog timer Introduce a new rlimit that allows the user to set a runtime timeout on real-time tasks their slice. Once this limit is exceeded the task will receive SIGXCPU. So it measures runtime since the last sleep. Input and ideas by Thomas Gleixner and Lennart Poettering. Signed-off-by: Peter Zijlstra CC: Lennart Poettering CC: Michael Kerrisk CC: Ulrich Drepper Signed-off-by: Ingo Molnar --- include/asm-generic/resource.h | 5 +++-- include/linux/sched.h | 1 + kernel/posix-cpu-timers.c | 29 +++++++++++++++++++++++++++++ kernel/sched_rt.c | 30 ++++++++++++++++++++++++++++++ 4 files changed, 63 insertions(+), 2 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/include/asm-generic/resource.h b/include/asm-generic/resource.h index a4a22cc35898..587566f95f6c 100644 --- a/include/asm-generic/resource.h +++ b/include/asm-generic/resource.h @@ -44,8 +44,8 @@ #define RLIMIT_NICE 13 /* max nice prio allowed to raise to 0-39 for nice level 19 .. -20 */ #define RLIMIT_RTPRIO 14 /* maximum realtime priority */ - -#define RLIM_NLIMITS 15 +#define RLIMIT_RTTIME 15 /* timeout for RT tasks in us */ +#define RLIM_NLIMITS 16 /* * SuS says limits have to be unsigned. @@ -86,6 +86,7 @@ [RLIMIT_MSGQUEUE] = { MQ_BYTES_MAX, MQ_BYTES_MAX }, \ [RLIMIT_NICE] = { 0, 0 }, \ [RLIMIT_RTPRIO] = { 0, 0 }, \ + [RLIMIT_RTTIME] = { RLIM_INFINITY, RLIM_INFINITY }, \ } #endif /* __KERNEL__ */ diff --git a/include/linux/sched.h b/include/linux/sched.h index a06d09ebd5c6..fe3f8fbc614e 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -932,6 +932,7 @@ struct sched_entity { struct sched_rt_entity { struct list_head run_list; unsigned int time_slice; + unsigned long timeout; }; struct task_struct { diff --git a/kernel/posix-cpu-timers.c b/kernel/posix-cpu-timers.c index 68c96376e84a..2c076b36c4f6 100644 --- a/kernel/posix-cpu-timers.c +++ b/kernel/posix-cpu-timers.c @@ -967,6 +967,7 @@ static void check_thread_timers(struct task_struct *tsk, { int maxfire; struct list_head *timers = tsk->cpu_timers; + struct signal_struct *const sig = tsk->signal; maxfire = 20; tsk->it_prof_expires = cputime_zero; @@ -1011,6 +1012,34 @@ static void check_thread_timers(struct task_struct *tsk, t->firing = 1; list_move_tail(&t->entry, firing); } + + /* + * Check for the special case thread timers. + */ + if (sig->rlim[RLIMIT_RTTIME].rlim_cur != RLIM_INFINITY) { + unsigned long hard = sig->rlim[RLIMIT_RTTIME].rlim_max; + unsigned long *soft = &sig->rlim[RLIMIT_RTTIME].rlim_cur; + + if (tsk->rt.timeout > DIV_ROUND_UP(hard, USEC_PER_SEC/HZ)) { + /* + * At the hard limit, we just die. + * No need to calculate anything else now. + */ + __group_send_sig_info(SIGKILL, SEND_SIG_PRIV, tsk); + return; + } + if (tsk->rt.timeout > DIV_ROUND_UP(*soft, USEC_PER_SEC/HZ)) { + /* + * At the soft limit, send a SIGXCPU every second. + */ + if (sig->rlim[RLIMIT_RTTIME].rlim_cur + < sig->rlim[RLIMIT_RTTIME].rlim_max) { + sig->rlim[RLIMIT_RTTIME].rlim_cur += + USEC_PER_SEC; + } + __group_send_sig_info(SIGXCPU, SEND_SIG_PRIV, tsk); + } + } } /* diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 29963af782ae..f350f7b15158 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -116,6 +116,9 @@ static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup) inc_cpu_load(rq, p->se.load.weight); inc_rt_tasks(p, rq); + + if (wakeup) + p->rt.timeout = 0; } /* @@ -834,11 +837,38 @@ static void prio_changed_rt(struct rq *rq, struct task_struct *p, } } +static void watchdog(struct rq *rq, struct task_struct *p) +{ + unsigned long soft, hard; + + if (!p->signal) + return; + + soft = p->signal->rlim[RLIMIT_RTTIME].rlim_cur; + hard = p->signal->rlim[RLIMIT_RTTIME].rlim_max; + + if (soft != RLIM_INFINITY) { + unsigned long next; + + p->rt.timeout++; + next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ); + if (next > p->rt.timeout) { + u64 next_time = p->se.sum_exec_runtime; + + next_time += next * (NSEC_PER_SEC/HZ); + if (p->it_sched_expires > next_time) + p->it_sched_expires = next_time; + } else + p->it_sched_expires = p->se.sum_exec_runtime; + } +} static void task_tick_rt(struct rq *rq, struct task_struct *p) { update_curr_rt(rq); + watchdog(rq, p); + /* * RR tasks need a special form of timeslice management. * FIFO tasks have no timeslices. -- cgit v1.2.3-59-g8ed1b From 8f4d37ec073c17e2d4aa8851df5837d798606d6f Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Fri, 25 Jan 2008 21:08:29 +0100 Subject: sched: high-res preemption tick Use HR-timers (when available) to deliver an accurate preemption tick. The regular scheduler tick that runs at 1/HZ can be too coarse when nice level are used. The fairness system will still keep the cpu utilisation 'fair' by then delaying the task that got an excessive amount of CPU time but try to minimize this by delivering preemption points spot-on. The average frequency of this extra interrupt is sched_latency / nr_latency. Which need not be higher than 1/HZ, its just that the distribution within the sched_latency period is important. Signed-off-by: Peter Zijlstra Signed-off-by: Ingo Molnar --- arch/x86/kernel/entry_64.S | 6 +- arch/x86/kernel/signal_32.c | 3 + arch/x86/kernel/signal_64.c | 3 + include/asm-x86/thread_info_32.h | 2 + include/asm-x86/thread_info_64.h | 5 + include/linux/hrtimer.h | 9 ++ include/linux/sched.h | 3 +- kernel/Kconfig.hz | 2 + kernel/sched.c | 210 +++++++++++++++++++++++++++++++++++++-- kernel/sched_fair.c | 69 ++++++++++++- kernel/sched_idletask.c | 2 +- kernel/sched_rt.c | 2 +- 12 files changed, 295 insertions(+), 21 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/arch/x86/kernel/entry_64.S b/arch/x86/kernel/entry_64.S index 3a058bb16409..e70f3881d7e4 100644 --- a/arch/x86/kernel/entry_64.S +++ b/arch/x86/kernel/entry_64.S @@ -283,7 +283,7 @@ sysret_careful: sysret_signal: TRACE_IRQS_ON sti - testl $(_TIF_SIGPENDING|_TIF_SINGLESTEP|_TIF_MCE_NOTIFY),%edx + testl $_TIF_DO_NOTIFY_MASK,%edx jz 1f /* Really a signal */ @@ -377,7 +377,7 @@ int_very_careful: jmp int_restore_rest int_signal: - testl $(_TIF_SIGPENDING|_TIF_SINGLESTEP|_TIF_MCE_NOTIFY),%edx + testl $_TIF_DO_NOTIFY_MASK,%edx jz 1f movq %rsp,%rdi # &ptregs -> arg1 xorl %esi,%esi # oldset -> arg2 @@ -603,7 +603,7 @@ retint_careful: jmp retint_check retint_signal: - testl $(_TIF_SIGPENDING|_TIF_SINGLESTEP|_TIF_MCE_NOTIFY),%edx + testl $_TIF_DO_NOTIFY_MASK,%edx jz retint_swapgs TRACE_IRQS_ON sti diff --git a/arch/x86/kernel/signal_32.c b/arch/x86/kernel/signal_32.c index 9bdd83022f5f..20f29e4c1d33 100644 --- a/arch/x86/kernel/signal_32.c +++ b/arch/x86/kernel/signal_32.c @@ -658,6 +658,9 @@ void do_notify_resume(struct pt_regs *regs, void *_unused, /* deal with pending signal delivery */ if (thread_info_flags & (_TIF_SIGPENDING | _TIF_RESTORE_SIGMASK)) do_signal(regs); + + if (thread_info_flags & _TIF_HRTICK_RESCHED) + hrtick_resched(); clear_thread_flag(TIF_IRET); } diff --git a/arch/x86/kernel/signal_64.c b/arch/x86/kernel/signal_64.c index ab086b0357fc..38d806467c0f 100644 --- a/arch/x86/kernel/signal_64.c +++ b/arch/x86/kernel/signal_64.c @@ -480,6 +480,9 @@ do_notify_resume(struct pt_regs *regs, void *unused, __u32 thread_info_flags) /* deal with pending signal delivery */ if (thread_info_flags & (_TIF_SIGPENDING|_TIF_RESTORE_SIGMASK)) do_signal(regs); + + if (thread_info_flags & _TIF_HRTICK_RESCHED) + hrtick_resched(); } void signal_fault(struct pt_regs *regs, void __user *frame, char *where) diff --git a/include/asm-x86/thread_info_32.h b/include/asm-x86/thread_info_32.h index 22a8cbcd35e2..ef58fd2a6eb0 100644 --- a/include/asm-x86/thread_info_32.h +++ b/include/asm-x86/thread_info_32.h @@ -132,6 +132,7 @@ static inline struct thread_info *current_thread_info(void) #define TIF_SYSCALL_AUDIT 6 /* syscall auditing active */ #define TIF_SECCOMP 7 /* secure computing */ #define TIF_RESTORE_SIGMASK 8 /* restore signal mask in do_signal() */ +#define TIF_HRTICK_RESCHED 9 /* reprogram hrtick timer */ #define TIF_MEMDIE 16 #define TIF_DEBUG 17 /* uses debug registers */ #define TIF_IO_BITMAP 18 /* uses I/O bitmap */ @@ -147,6 +148,7 @@ static inline struct thread_info *current_thread_info(void) #define _TIF_SYSCALL_AUDIT (1<base->get_time(); } +static inline int hrtimer_is_hres_active(struct hrtimer *timer) +{ + return timer->base->cpu_base->hres_active; +} + /* * The resolution of the clocks. The resolution value is returned in * the clock_getres() system call to give application programmers an @@ -248,6 +253,10 @@ static inline ktime_t hrtimer_cb_get_time(struct hrtimer *timer) return timer->base->softirq_time; } +static inline int hrtimer_is_hres_active(struct hrtimer *timer) +{ + return 0; +} #endif extern ktime_t ktime_get(void); diff --git a/include/linux/sched.h b/include/linux/sched.h index 7907845c2348..43e0339d65fc 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -257,6 +257,7 @@ extern void trap_init(void); extern void account_process_tick(struct task_struct *task, int user); extern void update_process_times(int user); extern void scheduler_tick(void); +extern void hrtick_resched(void); extern void sched_show_task(struct task_struct *p); @@ -849,7 +850,7 @@ struct sched_class { #endif void (*set_curr_task) (struct rq *rq); - void (*task_tick) (struct rq *rq, struct task_struct *p); + void (*task_tick) (struct rq *rq, struct task_struct *p, int queued); void (*task_new) (struct rq *rq, struct task_struct *p); void (*set_cpus_allowed)(struct task_struct *p, cpumask_t *newmask); diff --git a/kernel/Kconfig.hz b/kernel/Kconfig.hz index 4af15802ccd4..526128a2e622 100644 --- a/kernel/Kconfig.hz +++ b/kernel/Kconfig.hz @@ -54,3 +54,5 @@ config HZ default 300 if HZ_300 default 1000 if HZ_1000 +config SCHED_HRTICK + def_bool HIGH_RES_TIMERS && X86 diff --git a/kernel/sched.c b/kernel/sched.c index 6ee37602a6d8..17f93d3eda91 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -65,6 +65,7 @@ #include #include #include +#include #include #include @@ -451,6 +452,12 @@ struct rq { struct list_head migration_queue; #endif +#ifdef CONFIG_SCHED_HRTICK + unsigned long hrtick_flags; + ktime_t hrtick_expire; + struct hrtimer hrtick_timer; +#endif + #ifdef CONFIG_SCHEDSTATS /* latency stats */ struct sched_info rq_sched_info; @@ -572,6 +579,8 @@ enum { SCHED_FEAT_START_DEBIT = 4, SCHED_FEAT_TREE_AVG = 8, SCHED_FEAT_APPROX_AVG = 16, + SCHED_FEAT_HRTICK = 32, + SCHED_FEAT_DOUBLE_TICK = 64, }; const_debug unsigned int sysctl_sched_features = @@ -579,7 +588,9 @@ const_debug unsigned int sysctl_sched_features = SCHED_FEAT_WAKEUP_PREEMPT * 1 | SCHED_FEAT_START_DEBIT * 1 | SCHED_FEAT_TREE_AVG * 0 | - SCHED_FEAT_APPROX_AVG * 0; + SCHED_FEAT_APPROX_AVG * 0 | + SCHED_FEAT_HRTICK * 1 | + SCHED_FEAT_DOUBLE_TICK * 0; #define sched_feat(x) (sysctl_sched_features & SCHED_FEAT_##x) @@ -796,6 +807,173 @@ void sched_clock_idle_wakeup_event(u64 delta_ns) } EXPORT_SYMBOL_GPL(sched_clock_idle_wakeup_event); +static void __resched_task(struct task_struct *p, int tif_bit); + +static inline void resched_task(struct task_struct *p) +{ + __resched_task(p, TIF_NEED_RESCHED); +} + +#ifdef CONFIG_SCHED_HRTICK +/* + * Use HR-timers to deliver accurate preemption points. + * + * Its all a bit involved since we cannot program an hrt while holding the + * rq->lock. So what we do is store a state in in rq->hrtick_* and ask for a + * reschedule event. + * + * When we get rescheduled we reprogram the hrtick_timer outside of the + * rq->lock. + */ +static inline void resched_hrt(struct task_struct *p) +{ + __resched_task(p, TIF_HRTICK_RESCHED); +} + +static inline void resched_rq(struct rq *rq) +{ + unsigned long flags; + + spin_lock_irqsave(&rq->lock, flags); + resched_task(rq->curr); + spin_unlock_irqrestore(&rq->lock, flags); +} + +enum { + HRTICK_SET, /* re-programm hrtick_timer */ + HRTICK_RESET, /* not a new slice */ +}; + +/* + * Use hrtick when: + * - enabled by features + * - hrtimer is actually high res + */ +static inline int hrtick_enabled(struct rq *rq) +{ + if (!sched_feat(HRTICK)) + return 0; + return hrtimer_is_hres_active(&rq->hrtick_timer); +} + +/* + * Called to set the hrtick timer state. + * + * called with rq->lock held and irqs disabled + */ +static void hrtick_start(struct rq *rq, u64 delay, int reset) +{ + assert_spin_locked(&rq->lock); + + /* + * preempt at: now + delay + */ + rq->hrtick_expire = + ktime_add_ns(rq->hrtick_timer.base->get_time(), delay); + /* + * indicate we need to program the timer + */ + __set_bit(HRTICK_SET, &rq->hrtick_flags); + if (reset) + __set_bit(HRTICK_RESET, &rq->hrtick_flags); + + /* + * New slices are called from the schedule path and don't need a + * forced reschedule. + */ + if (reset) + resched_hrt(rq->curr); +} + +static void hrtick_clear(struct rq *rq) +{ + if (hrtimer_active(&rq->hrtick_timer)) + hrtimer_cancel(&rq->hrtick_timer); +} + +/* + * Update the timer from the possible pending state. + */ +static void hrtick_set(struct rq *rq) +{ + ktime_t time; + int set, reset; + unsigned long flags; + + WARN_ON_ONCE(cpu_of(rq) != smp_processor_id()); + + spin_lock_irqsave(&rq->lock, flags); + set = __test_and_clear_bit(HRTICK_SET, &rq->hrtick_flags); + reset = __test_and_clear_bit(HRTICK_RESET, &rq->hrtick_flags); + time = rq->hrtick_expire; + clear_thread_flag(TIF_HRTICK_RESCHED); + spin_unlock_irqrestore(&rq->lock, flags); + + if (set) { + hrtimer_start(&rq->hrtick_timer, time, HRTIMER_MODE_ABS); + if (reset && !hrtimer_active(&rq->hrtick_timer)) + resched_rq(rq); + } else + hrtick_clear(rq); +} + +/* + * High-resolution timer tick. + * Runs from hardirq context with interrupts disabled. + */ +static enum hrtimer_restart hrtick(struct hrtimer *timer) +{ + struct rq *rq = container_of(timer, struct rq, hrtick_timer); + + WARN_ON_ONCE(cpu_of(rq) != smp_processor_id()); + + spin_lock(&rq->lock); + __update_rq_clock(rq); + rq->curr->sched_class->task_tick(rq, rq->curr, 1); + spin_unlock(&rq->lock); + + return HRTIMER_NORESTART; +} + +static inline void init_rq_hrtick(struct rq *rq) +{ + rq->hrtick_flags = 0; + hrtimer_init(&rq->hrtick_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL); + rq->hrtick_timer.function = hrtick; + rq->hrtick_timer.cb_mode = HRTIMER_CB_IRQSAFE_NO_SOFTIRQ; +} + +void hrtick_resched(void) +{ + struct rq *rq; + unsigned long flags; + + if (!test_thread_flag(TIF_HRTICK_RESCHED)) + return; + + local_irq_save(flags); + rq = cpu_rq(smp_processor_id()); + hrtick_set(rq); + local_irq_restore(flags); +} +#else +static inline void hrtick_clear(struct rq *rq) +{ +} + +static inline void hrtick_set(struct rq *rq) +{ +} + +static inline void init_rq_hrtick(struct rq *rq) +{ +} + +void hrtick_resched(void) +{ +} +#endif + /* * resched_task - mark a task 'to be rescheduled now'. * @@ -809,16 +987,16 @@ EXPORT_SYMBOL_GPL(sched_clock_idle_wakeup_event); #define tsk_is_polling(t) test_tsk_thread_flag(t, TIF_POLLING_NRFLAG) #endif -static void resched_task(struct task_struct *p) +static void __resched_task(struct task_struct *p, int tif_bit) { int cpu; assert_spin_locked(&task_rq(p)->lock); - if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED))) + if (unlikely(test_tsk_thread_flag(p, tif_bit))) return; - set_tsk_thread_flag(p, TIF_NEED_RESCHED); + set_tsk_thread_flag(p, tif_bit); cpu = task_cpu(p); if (cpu == smp_processor_id()) @@ -841,10 +1019,10 @@ static void resched_cpu(int cpu) spin_unlock_irqrestore(&rq->lock, flags); } #else -static inline void resched_task(struct task_struct *p) +static void __resched_task(struct task_struct *p, int tif_bit) { assert_spin_locked(&task_rq(p)->lock); - set_tsk_need_resched(p); + set_tsk_thread_flag(p, tif_bit); } #endif @@ -3497,7 +3675,7 @@ void scheduler_tick(void) rq->tick_timestamp = rq->clock; update_cpu_load(rq); if (curr != rq->idle) /* FIXME: needed? */ - curr->sched_class->task_tick(rq, curr); + curr->sched_class->task_tick(rq, curr, 0); spin_unlock(&rq->lock); #ifdef CONFIG_SMP @@ -3643,6 +3821,8 @@ need_resched_nonpreemptible: schedule_debug(prev); + hrtick_clear(rq); + /* * Do the rq-clock update outside the rq lock: */ @@ -3680,14 +3860,20 @@ need_resched_nonpreemptible: ++*switch_count; context_switch(rq, prev, next); /* unlocks the rq */ + /* + * the context switch might have flipped the stack from under + * us, hence refresh the local variables. + */ + cpu = smp_processor_id(); + rq = cpu_rq(cpu); } else spin_unlock_irq(&rq->lock); - if (unlikely(reacquire_kernel_lock(current) < 0)) { - cpu = smp_processor_id(); - rq = cpu_rq(cpu); + hrtick_set(rq); + + if (unlikely(reacquire_kernel_lock(current) < 0)) goto need_resched_nonpreemptible; - } + preempt_enable_no_resched(); if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) goto need_resched; @@ -6913,6 +7099,8 @@ void __init sched_init(void) rq->rt.overloaded = 0; rq_attach_root(rq, &def_root_domain); #endif + init_rq_hrtick(rq); + atomic_set(&rq->nr_iowait, 0); array = &rq->rt.active; diff --git a/kernel/sched_fair.c b/kernel/sched_fair.c index dfa18d55561d..3dab1ff83c4f 100644 --- a/kernel/sched_fair.c +++ b/kernel/sched_fair.c @@ -642,13 +642,29 @@ static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev) cfs_rq->curr = NULL; } -static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) +static void +entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued) { /* * Update run-time statistics of the 'current'. */ update_curr(cfs_rq); +#ifdef CONFIG_SCHED_HRTICK + /* + * queued ticks are scheduled to match the slice, so don't bother + * validating it and just reschedule. + */ + if (queued) + return resched_task(rq_of(cfs_rq)->curr); + /* + * don't let the period tick interfere with the hrtick preemption + */ + if (!sched_feat(DOUBLE_TICK) && + hrtimer_active(&rq_of(cfs_rq)->hrtick_timer)) + return; +#endif + if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT)) check_preempt_tick(cfs_rq, curr); } @@ -754,6 +770,43 @@ static inline struct sched_entity *parent_entity(struct sched_entity *se) #endif /* CONFIG_FAIR_GROUP_SCHED */ +#ifdef CONFIG_SCHED_HRTICK +static void hrtick_start_fair(struct rq *rq, struct task_struct *p) +{ + int requeue = rq->curr == p; + struct sched_entity *se = &p->se; + struct cfs_rq *cfs_rq = cfs_rq_of(se); + + WARN_ON(task_rq(p) != rq); + + if (hrtick_enabled(rq) && cfs_rq->nr_running > 1) { + u64 slice = sched_slice(cfs_rq, se); + u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime; + s64 delta = slice - ran; + + if (delta < 0) { + if (rq->curr == p) + resched_task(p); + return; + } + + /* + * Don't schedule slices shorter than 10000ns, that just + * doesn't make sense. Rely on vruntime for fairness. + */ + if (!requeue) + delta = max(10000LL, delta); + + hrtick_start(rq, delta, requeue); + } +} +#else +static inline void +hrtick_start_fair(struct rq *rq, struct task_struct *p) +{ +} +#endif + /* * The enqueue_task method is called before nr_running is * increased. Here we update the fair scheduling stats and @@ -782,6 +835,8 @@ static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup) */ if (incload) inc_cpu_load(rq, topse->load.weight); + + hrtick_start_fair(rq, rq->curr); } /* @@ -814,6 +869,8 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep) */ if (decload) dec_cpu_load(rq, topse->load.weight); + + hrtick_start_fair(rq, rq->curr); } /* @@ -1049,6 +1106,7 @@ static void check_preempt_wakeup(struct rq *rq, struct task_struct *p) static struct task_struct *pick_next_task_fair(struct rq *rq) { + struct task_struct *p; struct cfs_rq *cfs_rq = &rq->cfs; struct sched_entity *se; @@ -1060,7 +1118,10 @@ static struct task_struct *pick_next_task_fair(struct rq *rq) cfs_rq = group_cfs_rq(se); } while (cfs_rq); - return task_of(se); + p = task_of(se); + hrtick_start_fair(rq, p); + + return p; } /* @@ -1235,14 +1296,14 @@ move_one_task_fair(struct rq *this_rq, int this_cpu, struct rq *busiest, /* * scheduler tick hitting a task of our scheduling class: */ -static void task_tick_fair(struct rq *rq, struct task_struct *curr) +static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) { struct cfs_rq *cfs_rq; struct sched_entity *se = &curr->se; for_each_sched_entity(se) { cfs_rq = cfs_rq_of(se); - entity_tick(cfs_rq, se); + entity_tick(cfs_rq, se, queued); } } diff --git a/kernel/sched_idletask.c b/kernel/sched_idletask.c index ef7a2661fa10..2bcafa375633 100644 --- a/kernel/sched_idletask.c +++ b/kernel/sched_idletask.c @@ -61,7 +61,7 @@ move_one_task_idle(struct rq *this_rq, int this_cpu, struct rq *busiest, } #endif -static void task_tick_idle(struct rq *rq, struct task_struct *curr) +static void task_tick_idle(struct rq *rq, struct task_struct *curr, int queued) { } diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index f350f7b15158..83fbbcb8019e 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -863,7 +863,7 @@ static void watchdog(struct rq *rq, struct task_struct *p) } } -static void task_tick_rt(struct rq *rq, struct task_struct *p) +static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued) { update_curr_rt(rq); -- cgit v1.2.3-59-g8ed1b From fa85ae2418e6843953107cd6a06f645752829bc0 Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Fri, 25 Jan 2008 21:08:29 +0100 Subject: sched: rt time limit Very simple time limit on the realtime scheduling classes. Allow the rq's realtime class to consume sched_rt_ratio of every sched_rt_period slice. If the class exceeds this quota the fair class will preempt the realtime class. Signed-off-by: Peter Zijlstra Signed-off-by: Ingo Molnar --- include/linux/sched.h | 2 ++ kernel/sched.c | 70 ++++++++++++++++++++++++++++++++++++--------------- kernel/sched_rt.c | 53 ++++++++++++++++++++++++++++++++++++++ kernel/sysctl.c | 18 ++++++++++++- 4 files changed, 122 insertions(+), 21 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/include/linux/sched.h b/include/linux/sched.h index 43e0339d65fc..d5ea144df836 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1490,6 +1490,8 @@ extern unsigned int sysctl_sched_child_runs_first; extern unsigned int sysctl_sched_features; extern unsigned int sysctl_sched_migration_cost; extern unsigned int sysctl_sched_nr_migrate; +extern unsigned int sysctl_sched_rt_period; +extern unsigned int sysctl_sched_rt_ratio; #if defined(CONFIG_FAIR_GROUP_SCHED) && defined(CONFIG_SMP) extern unsigned int sysctl_sched_min_bal_int_shares; extern unsigned int sysctl_sched_max_bal_int_shares; diff --git a/kernel/sched.c b/kernel/sched.c index 17f93d3eda91..e9a7beee9b79 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -342,13 +342,14 @@ struct cfs_rq { /* Real-Time classes' related field in a runqueue: */ struct rt_rq { struct rt_prio_array active; - int rt_load_balance_idx; - struct list_head *rt_load_balance_head, *rt_load_balance_curr; unsigned long rt_nr_running; +#ifdef CONFIG_SMP unsigned long rt_nr_migratory; - /* highest queued rt task prio */ - int highest_prio; + int highest_prio; /* highest queued rt task prio */ int overloaded; +#endif + u64 rt_time; + u64 rt_throttled; }; #ifdef CONFIG_SMP @@ -415,6 +416,7 @@ struct rq { struct list_head leaf_cfs_rq_list; #endif struct rt_rq rt; + u64 rt_period_expire; /* * This is part of a global counter where only the total sum @@ -600,6 +602,21 @@ const_debug unsigned int sysctl_sched_features = */ const_debug unsigned int sysctl_sched_nr_migrate = 32; +/* + * period over which we measure -rt task cpu usage in ms. + * default: 1s + */ +const_debug unsigned int sysctl_sched_rt_period = 1000; + +#define SCHED_RT_FRAC_SHIFT 16 +#define SCHED_RT_FRAC (1UL << SCHED_RT_FRAC_SHIFT) + +/* + * ratio of time -rt tasks may consume. + * default: 100% + */ +const_debug unsigned int sysctl_sched_rt_ratio = SCHED_RT_FRAC; + /* * For kernel-internal use: high-speed (but slightly incorrect) per-cpu * clock constructed from sched_clock(): @@ -3674,8 +3691,8 @@ void scheduler_tick(void) rq->clock = next_tick; rq->tick_timestamp = rq->clock; update_cpu_load(rq); - if (curr != rq->idle) /* FIXME: needed? */ - curr->sched_class->task_tick(rq, curr, 0); + curr->sched_class->task_tick(rq, curr, 0); + update_sched_rt_period(rq); spin_unlock(&rq->lock); #ifdef CONFIG_SMP @@ -7041,6 +7058,29 @@ static void init_cfs_rq(struct cfs_rq *cfs_rq, struct rq *rq) cfs_rq->min_vruntime = (u64)(-(1LL << 20)); } +static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq) +{ + struct rt_prio_array *array; + int i; + + array = &rt_rq->active; + for (i = 0; i < MAX_RT_PRIO; i++) { + INIT_LIST_HEAD(array->queue + i); + __clear_bit(i, array->bitmap); + } + /* delimiter for bitsearch: */ + __set_bit(MAX_RT_PRIO, array->bitmap); + +#ifdef CONFIG_SMP + rt_rq->rt_nr_migratory = 0; + rt_rq->highest_prio = MAX_RT_PRIO; + rt_rq->overloaded = 0; +#endif + + rt_rq->rt_time = 0; + rt_rq->rt_throttled = 0; +} + void __init sched_init(void) { int highest_cpu = 0; @@ -7051,7 +7091,6 @@ void __init sched_init(void) #endif for_each_possible_cpu(i) { - struct rt_prio_array *array; struct rq *rq; rq = cpu_rq(i); @@ -7083,6 +7122,8 @@ void __init sched_init(void) } init_task_group.shares = init_task_group_load; #endif + init_rt_rq(&rq->rt, rq); + rq->rt_period_expire = 0; for (j = 0; j < CPU_LOAD_IDX_MAX; j++) rq->cpu_load[j] = 0; @@ -7095,22 +7136,11 @@ void __init sched_init(void) rq->cpu = i; rq->migration_thread = NULL; INIT_LIST_HEAD(&rq->migration_queue); - rq->rt.highest_prio = MAX_RT_PRIO; - rq->rt.overloaded = 0; rq_attach_root(rq, &def_root_domain); #endif init_rq_hrtick(rq); - atomic_set(&rq->nr_iowait, 0); - - array = &rq->rt.active; - for (j = 0; j < MAX_RT_PRIO; j++) { - INIT_LIST_HEAD(array->queue + j); - __clear_bit(j, array->bitmap); - } highest_cpu = i; - /* delimiter for bitsearch: */ - __set_bit(MAX_RT_PRIO, array->bitmap); } set_load_weight(&init_task); @@ -7282,7 +7312,7 @@ void set_curr_task(int cpu, struct task_struct *p) #ifdef CONFIG_SMP /* * distribute shares of all task groups among their schedulable entities, - * to reflect load distrbution across cpus. + * to reflect load distribution across cpus. */ static int rebalance_shares(struct sched_domain *sd, int this_cpu) { @@ -7349,7 +7379,7 @@ static int rebalance_shares(struct sched_domain *sd, int this_cpu) * sysctl_sched_max_bal_int_shares represents the maximum interval between * consecutive calls to rebalance_shares() in the same sched domain. * - * These settings allows for the appropriate tradeoff between accuracy of + * These settings allows for the appropriate trade-off between accuracy of * fairness and the associated overhead. * */ diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 83fbbcb8019e..fd10d965aa06 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -45,6 +45,50 @@ static void update_rt_migration(struct rq *rq) } #endif /* CONFIG_SMP */ +static int sched_rt_ratio_exceeded(struct rq *rq, struct rt_rq *rt_rq) +{ + u64 period, ratio; + + if (sysctl_sched_rt_ratio == SCHED_RT_FRAC) + return 0; + + if (rt_rq->rt_throttled) + return 1; + + period = (u64)sysctl_sched_rt_period * NSEC_PER_MSEC; + ratio = (period * sysctl_sched_rt_ratio) >> SCHED_RT_FRAC_SHIFT; + + if (rt_rq->rt_time > ratio) { + rt_rq->rt_throttled = rq->clock + period - rt_rq->rt_time; + return 1; + } + + return 0; +} + +static void update_sched_rt_period(struct rq *rq) +{ + while (rq->clock > rq->rt_period_expire) { + u64 period, ratio; + + period = (u64)sysctl_sched_rt_period * NSEC_PER_MSEC; + ratio = (period * sysctl_sched_rt_ratio) >> SCHED_RT_FRAC_SHIFT; + + rq->rt.rt_time -= min(rq->rt.rt_time, ratio); + rq->rt_period_expire += period; + } + + /* + * When the rt throttle is expired, let them rip. + * (XXX: use hrtick when available) + */ + if (rq->rt.rt_throttled && rq->clock > rq->rt.rt_throttled) { + rq->rt.rt_throttled = 0; + if (!sched_rt_ratio_exceeded(rq, &rq->rt)) + resched_task(rq->curr); + } +} + /* * Update the current task's runtime statistics. Skip current tasks that * are not in our scheduling class. @@ -66,6 +110,11 @@ static void update_curr_rt(struct rq *rq) curr->se.sum_exec_runtime += delta_exec; curr->se.exec_start = rq->clock; cpuacct_charge(curr, delta_exec); + + rq->rt.rt_time += delta_exec; + update_sched_rt_period(rq); + if (sched_rt_ratio_exceeded(rq, &rq->rt)) + resched_task(curr); } static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq) @@ -208,8 +257,12 @@ static struct task_struct *pick_next_task_rt(struct rq *rq) struct rt_prio_array *array = &rq->rt.active; struct task_struct *next; struct list_head *queue; + struct rt_rq *rt_rq = &rq->rt; int idx; + if (sched_rt_ratio_exceeded(rq, rt_rq)) + return NULL; + idx = sched_find_first_bit(array->bitmap); if (idx >= MAX_RT_PRIO) return NULL; diff --git a/kernel/sysctl.c b/kernel/sysctl.c index 96f31c1bc4f0..3afbd25f43eb 100644 --- a/kernel/sysctl.c +++ b/kernel/sysctl.c @@ -306,7 +306,23 @@ static struct ctl_table kern_table[] = { .procname = "sched_nr_migrate", .data = &sysctl_sched_nr_migrate, .maxlen = sizeof(unsigned int), - .mode = 644, + .mode = 0644, + .proc_handler = &proc_dointvec, + }, + { + .ctl_name = CTL_UNNUMBERED, + .procname = "sched_rt_period_ms", + .data = &sysctl_sched_rt_period, + .maxlen = sizeof(unsigned int), + .mode = 0644, + .proc_handler = &proc_dointvec, + }, + { + .ctl_name = CTL_UNNUMBERED, + .procname = "sched_rt_ratio", + .data = &sysctl_sched_rt_ratio, + .maxlen = sizeof(unsigned int), + .mode = 0644, .proc_handler = &proc_dointvec, }, #if defined(CONFIG_FAIR_GROUP_SCHED) && defined(CONFIG_SMP) -- cgit v1.2.3-59-g8ed1b From 6f505b16425a51270058e4a93441fe64de3dd435 Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Fri, 25 Jan 2008 21:08:30 +0100 Subject: sched: rt group scheduling Extend group scheduling to also cover the realtime classes. It uses the time limiting introduced by the previous patch to allow multiple realtime groups. The hard time limit is required to keep behaviour deterministic. The algorithms used make the realtime scheduler O(tg), linear scaling wrt the number of task groups. This is the worst case behaviour I can't seem to get out of, the avg. case of the algorithms can be improved, I focused on correctness and worst case. [ akpm@linux-foundation.org: move side-effects out of BUG_ON(). ] Signed-off-by: Peter Zijlstra Signed-off-by: Ingo Molnar --- include/linux/init_task.h | 5 +- include/linux/sched.h | 10 +- kernel/fork.c | 2 +- kernel/sched.c | 283 +++++++++++++++++++--------- kernel/sched_rt.c | 455 ++++++++++++++++++++++++++++++++++------------ 5 files changed, 549 insertions(+), 206 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/include/linux/init_task.h b/include/linux/init_task.h index ee65d87bedb7..796019b22b6f 100644 --- a/include/linux/init_task.h +++ b/include/linux/init_task.h @@ -130,12 +130,13 @@ extern struct group_info init_groups; .normal_prio = MAX_PRIO-20, \ .policy = SCHED_NORMAL, \ .cpus_allowed = CPU_MASK_ALL, \ - .nr_cpus_allowed = NR_CPUS, \ .mm = NULL, \ .active_mm = &init_mm, \ .rt = { \ .run_list = LIST_HEAD_INIT(tsk.rt.run_list), \ - .time_slice = HZ, }, \ + .time_slice = HZ, \ + .nr_cpus_allowed = NR_CPUS, \ + }, \ .ioprio = 0, \ .tasks = LIST_HEAD_INIT(tsk.tasks), \ .ptrace_children= LIST_HEAD_INIT(tsk.ptrace_children), \ diff --git a/include/linux/sched.h b/include/linux/sched.h index d5ea144df836..04eecbf0241e 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -934,6 +934,15 @@ struct sched_rt_entity { struct list_head run_list; unsigned int time_slice; unsigned long timeout; + int nr_cpus_allowed; + +#ifdef CONFIG_FAIR_GROUP_SCHED + struct sched_rt_entity *parent; + /* rq on which this entity is (to be) queued: */ + struct rt_rq *rt_rq; + /* rq "owned" by this entity/group: */ + struct rt_rq *my_q; +#endif }; struct task_struct { @@ -978,7 +987,6 @@ struct task_struct { unsigned int policy; cpumask_t cpus_allowed; - int nr_cpus_allowed; #ifdef CONFIG_PREEMPT_RCU int rcu_read_lock_nesting; diff --git a/kernel/fork.c b/kernel/fork.c index 9f8ef32cbc7a..0c969f4fade0 100644 --- a/kernel/fork.c +++ b/kernel/fork.c @@ -1246,7 +1246,7 @@ static struct task_struct *copy_process(unsigned long clone_flags, * parent's CPU). This avoids alot of nasty races. */ p->cpus_allowed = current->cpus_allowed; - p->nr_cpus_allowed = current->nr_cpus_allowed; + p->rt.nr_cpus_allowed = current->rt.nr_cpus_allowed; if (unlikely(!cpu_isset(task_cpu(p), p->cpus_allowed) || !cpu_online(task_cpu(p)))) set_task_cpu(p, smp_processor_id()); diff --git a/kernel/sched.c b/kernel/sched.c index e9a7beee9b79..5ea2c533b432 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -161,6 +161,8 @@ struct rt_prio_array { struct cfs_rq; +static LIST_HEAD(task_groups); + /* task group related information */ struct task_group { #ifdef CONFIG_FAIR_CGROUP_SCHED @@ -171,6 +173,11 @@ struct task_group { /* runqueue "owned" by this group on each cpu */ struct cfs_rq **cfs_rq; + struct sched_rt_entity **rt_se; + struct rt_rq **rt_rq; + + unsigned int rt_ratio; + /* * shares assigned to a task group governs how much of cpu bandwidth * is allocated to the group. The more shares a group has, the more is @@ -208,6 +215,7 @@ struct task_group { unsigned long shares; struct rcu_head rcu; + struct list_head list; }; /* Default task group's sched entity on each cpu */ @@ -215,9 +223,15 @@ static DEFINE_PER_CPU(struct sched_entity, init_sched_entity); /* Default task group's cfs_rq on each cpu */ static DEFINE_PER_CPU(struct cfs_rq, init_cfs_rq) ____cacheline_aligned_in_smp; +static DEFINE_PER_CPU(struct sched_rt_entity, init_sched_rt_entity); +static DEFINE_PER_CPU(struct rt_rq, init_rt_rq) ____cacheline_aligned_in_smp; + static struct sched_entity *init_sched_entity_p[NR_CPUS]; static struct cfs_rq *init_cfs_rq_p[NR_CPUS]; +static struct sched_rt_entity *init_sched_rt_entity_p[NR_CPUS]; +static struct rt_rq *init_rt_rq_p[NR_CPUS]; + /* task_group_mutex serializes add/remove of task groups and also changes to * a task group's cpu shares. */ @@ -240,6 +254,9 @@ static void set_se_shares(struct sched_entity *se, unsigned long shares); struct task_group init_task_group = { .se = init_sched_entity_p, .cfs_rq = init_cfs_rq_p, + + .rt_se = init_sched_rt_entity_p, + .rt_rq = init_rt_rq_p, }; #ifdef CONFIG_FAIR_USER_SCHED @@ -269,10 +286,13 @@ static inline struct task_group *task_group(struct task_struct *p) } /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */ -static inline void set_task_cfs_rq(struct task_struct *p, unsigned int cpu) +static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { p->se.cfs_rq = task_group(p)->cfs_rq[cpu]; p->se.parent = task_group(p)->se[cpu]; + + p->rt.rt_rq = task_group(p)->rt_rq[cpu]; + p->rt.parent = task_group(p)->rt_se[cpu]; } static inline void lock_task_group_list(void) @@ -297,7 +317,7 @@ static inline void unlock_doms_cur(void) #else -static inline void set_task_cfs_rq(struct task_struct *p, unsigned int cpu) { } +static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { } static inline void lock_task_group_list(void) { } static inline void unlock_task_group_list(void) { } static inline void lock_doms_cur(void) { } @@ -343,13 +363,22 @@ struct cfs_rq { struct rt_rq { struct rt_prio_array active; unsigned long rt_nr_running; +#if defined CONFIG_SMP || defined CONFIG_FAIR_GROUP_SCHED + int highest_prio; /* highest queued rt task prio */ +#endif #ifdef CONFIG_SMP unsigned long rt_nr_migratory; - int highest_prio; /* highest queued rt task prio */ int overloaded; #endif + int rt_throttled; u64 rt_time; - u64 rt_throttled; + +#ifdef CONFIG_FAIR_GROUP_SCHED + struct rq *rq; + struct list_head leaf_rt_rq_list; + struct task_group *tg; + struct sched_rt_entity *rt_se; +#endif }; #ifdef CONFIG_SMP @@ -411,12 +440,14 @@ struct rq { u64 nr_switches; struct cfs_rq cfs; + struct rt_rq rt; + u64 rt_period_expire; + #ifdef CONFIG_FAIR_GROUP_SCHED /* list of leaf cfs_rq on this cpu: */ struct list_head leaf_cfs_rq_list; + struct list_head leaf_rt_rq_list; #endif - struct rt_rq rt; - u64 rt_period_expire; /* * This is part of a global counter where only the total sum @@ -613,9 +644,9 @@ const_debug unsigned int sysctl_sched_rt_period = 1000; /* * ratio of time -rt tasks may consume. - * default: 100% + * default: 95% */ -const_debug unsigned int sysctl_sched_rt_ratio = SCHED_RT_FRAC; +const_debug unsigned int sysctl_sched_rt_ratio = 62259; /* * For kernel-internal use: high-speed (but slightly incorrect) per-cpu @@ -1337,7 +1368,7 @@ unsigned long weighted_cpuload(const int cpu) static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu) { - set_task_cfs_rq(p, cpu); + set_task_rq(p, cpu); #ifdef CONFIG_SMP /* * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be @@ -5281,7 +5312,7 @@ int set_cpus_allowed(struct task_struct *p, cpumask_t new_mask) p->sched_class->set_cpus_allowed(p, &new_mask); else { p->cpus_allowed = new_mask; - p->nr_cpus_allowed = cpus_weight(new_mask); + p->rt.nr_cpus_allowed = cpus_weight(new_mask); } /* Can the task run on the task's current CPU? If so, we're done */ @@ -7079,8 +7110,50 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq) rt_rq->rt_time = 0; rt_rq->rt_throttled = 0; + +#ifdef CONFIG_FAIR_GROUP_SCHED + rt_rq->rq = rq; +#endif } +#ifdef CONFIG_FAIR_GROUP_SCHED +static void init_tg_cfs_entry(struct rq *rq, struct task_group *tg, + struct cfs_rq *cfs_rq, struct sched_entity *se, + int cpu, int add) +{ + tg->cfs_rq[cpu] = cfs_rq; + init_cfs_rq(cfs_rq, rq); + cfs_rq->tg = tg; + if (add) + list_add(&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list); + + tg->se[cpu] = se; + se->cfs_rq = &rq->cfs; + se->my_q = cfs_rq; + se->load.weight = tg->shares; + se->load.inv_weight = div64_64(1ULL<<32, se->load.weight); + se->parent = NULL; +} + +static void init_tg_rt_entry(struct rq *rq, struct task_group *tg, + struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, + int cpu, int add) +{ + tg->rt_rq[cpu] = rt_rq; + init_rt_rq(rt_rq, rq); + rt_rq->tg = tg; + rt_rq->rt_se = rt_se; + if (add) + list_add(&rt_rq->leaf_rt_rq_list, &rq->leaf_rt_rq_list); + + tg->rt_se[cpu] = rt_se; + rt_se->rt_rq = &rq->rt; + rt_se->my_q = rt_rq; + rt_se->parent = NULL; + INIT_LIST_HEAD(&rt_se->run_list); +} +#endif + void __init sched_init(void) { int highest_cpu = 0; @@ -7090,6 +7163,10 @@ void __init sched_init(void) init_defrootdomain(); #endif +#ifdef CONFIG_FAIR_GROUP_SCHED + list_add(&init_task_group.list, &task_groups); +#endif + for_each_possible_cpu(i) { struct rq *rq; @@ -7099,30 +7176,20 @@ void __init sched_init(void) rq->nr_running = 0; rq->clock = 1; init_cfs_rq(&rq->cfs, rq); + init_rt_rq(&rq->rt, rq); #ifdef CONFIG_FAIR_GROUP_SCHED - INIT_LIST_HEAD(&rq->leaf_cfs_rq_list); - { - struct cfs_rq *cfs_rq = &per_cpu(init_cfs_rq, i); - struct sched_entity *se = - &per_cpu(init_sched_entity, i); - - init_cfs_rq_p[i] = cfs_rq; - init_cfs_rq(cfs_rq, rq); - cfs_rq->tg = &init_task_group; - list_add(&cfs_rq->leaf_cfs_rq_list, - &rq->leaf_cfs_rq_list); - - init_sched_entity_p[i] = se; - se->cfs_rq = &rq->cfs; - se->my_q = cfs_rq; - se->load.weight = init_task_group_load; - se->load.inv_weight = - div64_64(1ULL<<32, init_task_group_load); - se->parent = NULL; - } init_task_group.shares = init_task_group_load; + INIT_LIST_HEAD(&rq->leaf_cfs_rq_list); + init_tg_cfs_entry(rq, &init_task_group, + &per_cpu(init_cfs_rq, i), + &per_cpu(init_sched_entity, i), i, 1); + + init_task_group.rt_ratio = sysctl_sched_rt_ratio; /* XXX */ + INIT_LIST_HEAD(&rq->leaf_rt_rq_list); + init_tg_rt_entry(rq, &init_task_group, + &per_cpu(init_rt_rq, i), + &per_cpu(init_sched_rt_entity, i), i, 1); #endif - init_rt_rq(&rq->rt, rq); rq->rt_period_expire = 0; for (j = 0; j < CPU_LOAD_IDX_MAX; j++) @@ -7460,12 +7527,36 @@ static int load_balance_monitor(void *unused) } #endif /* CONFIG_SMP */ +static void free_sched_group(struct task_group *tg) +{ + int i; + + for_each_possible_cpu(i) { + if (tg->cfs_rq) + kfree(tg->cfs_rq[i]); + if (tg->se) + kfree(tg->se[i]); + if (tg->rt_rq) + kfree(tg->rt_rq[i]); + if (tg->rt_se) + kfree(tg->rt_se[i]); + } + + kfree(tg->cfs_rq); + kfree(tg->se); + kfree(tg->rt_rq); + kfree(tg->rt_se); + kfree(tg); +} + /* allocate runqueue etc for a new task group */ struct task_group *sched_create_group(void) { struct task_group *tg; struct cfs_rq *cfs_rq; struct sched_entity *se; + struct rt_rq *rt_rq; + struct sched_rt_entity *rt_se; struct rq *rq; int i; @@ -7479,100 +7570,89 @@ struct task_group *sched_create_group(void) tg->se = kzalloc(sizeof(se) * NR_CPUS, GFP_KERNEL); if (!tg->se) goto err; + tg->rt_rq = kzalloc(sizeof(rt_rq) * NR_CPUS, GFP_KERNEL); + if (!tg->rt_rq) + goto err; + tg->rt_se = kzalloc(sizeof(rt_se) * NR_CPUS, GFP_KERNEL); + if (!tg->rt_se) + goto err; + + tg->shares = NICE_0_LOAD; + tg->rt_ratio = 0; /* XXX */ for_each_possible_cpu(i) { rq = cpu_rq(i); - cfs_rq = kmalloc_node(sizeof(struct cfs_rq), GFP_KERNEL, - cpu_to_node(i)); + cfs_rq = kmalloc_node(sizeof(struct cfs_rq), + GFP_KERNEL|__GFP_ZERO, cpu_to_node(i)); if (!cfs_rq) goto err; - se = kmalloc_node(sizeof(struct sched_entity), GFP_KERNEL, - cpu_to_node(i)); + se = kmalloc_node(sizeof(struct sched_entity), + GFP_KERNEL|__GFP_ZERO, cpu_to_node(i)); if (!se) goto err; - memset(cfs_rq, 0, sizeof(struct cfs_rq)); - memset(se, 0, sizeof(struct sched_entity)); + rt_rq = kmalloc_node(sizeof(struct rt_rq), + GFP_KERNEL|__GFP_ZERO, cpu_to_node(i)); + if (!rt_rq) + goto err; - tg->cfs_rq[i] = cfs_rq; - init_cfs_rq(cfs_rq, rq); - cfs_rq->tg = tg; + rt_se = kmalloc_node(sizeof(struct sched_rt_entity), + GFP_KERNEL|__GFP_ZERO, cpu_to_node(i)); + if (!rt_se) + goto err; - tg->se[i] = se; - se->cfs_rq = &rq->cfs; - se->my_q = cfs_rq; - se->load.weight = NICE_0_LOAD; - se->load.inv_weight = div64_64(1ULL<<32, NICE_0_LOAD); - se->parent = NULL; + init_tg_cfs_entry(rq, tg, cfs_rq, se, i, 0); + init_tg_rt_entry(rq, tg, rt_rq, rt_se, i, 0); } - tg->shares = NICE_0_LOAD; - lock_task_group_list(); for_each_possible_cpu(i) { rq = cpu_rq(i); cfs_rq = tg->cfs_rq[i]; list_add_rcu(&cfs_rq->leaf_cfs_rq_list, &rq->leaf_cfs_rq_list); + rt_rq = tg->rt_rq[i]; + list_add_rcu(&rt_rq->leaf_rt_rq_list, &rq->leaf_rt_rq_list); } + list_add_rcu(&tg->list, &task_groups); unlock_task_group_list(); return tg; err: - for_each_possible_cpu(i) { - if (tg->cfs_rq) - kfree(tg->cfs_rq[i]); - if (tg->se) - kfree(tg->se[i]); - } - kfree(tg->cfs_rq); - kfree(tg->se); - kfree(tg); - + free_sched_group(tg); return ERR_PTR(-ENOMEM); } /* rcu callback to free various structures associated with a task group */ -static void free_sched_group(struct rcu_head *rhp) +static void free_sched_group_rcu(struct rcu_head *rhp) { - struct task_group *tg = container_of(rhp, struct task_group, rcu); - struct cfs_rq *cfs_rq; - struct sched_entity *se; - int i; - /* now it should be safe to free those cfs_rqs */ - for_each_possible_cpu(i) { - cfs_rq = tg->cfs_rq[i]; - kfree(cfs_rq); - - se = tg->se[i]; - kfree(se); - } - - kfree(tg->cfs_rq); - kfree(tg->se); - kfree(tg); + free_sched_group(container_of(rhp, struct task_group, rcu)); } /* Destroy runqueue etc associated with a task group */ void sched_destroy_group(struct task_group *tg) { struct cfs_rq *cfs_rq = NULL; + struct rt_rq *rt_rq = NULL; int i; lock_task_group_list(); for_each_possible_cpu(i) { cfs_rq = tg->cfs_rq[i]; list_del_rcu(&cfs_rq->leaf_cfs_rq_list); + rt_rq = tg->rt_rq[i]; + list_del_rcu(&rt_rq->leaf_rt_rq_list); } + list_del_rcu(&tg->list); unlock_task_group_list(); BUG_ON(!cfs_rq); /* wait for possible concurrent references to cfs_rqs complete */ - call_rcu(&tg->rcu, free_sched_group); + call_rcu(&tg->rcu, free_sched_group_rcu); } /* change task's runqueue when it moves between groups. @@ -7588,11 +7668,6 @@ void sched_move_task(struct task_struct *tsk) rq = task_rq_lock(tsk, &flags); - if (tsk->sched_class != &fair_sched_class) { - set_task_cfs_rq(tsk, task_cpu(tsk)); - goto done; - } - update_rq_clock(rq); running = task_current(rq, tsk); @@ -7604,7 +7679,7 @@ void sched_move_task(struct task_struct *tsk) tsk->sched_class->put_prev_task(rq, tsk); } - set_task_cfs_rq(tsk, task_cpu(tsk)); + set_task_rq(tsk, task_cpu(tsk)); if (on_rq) { if (unlikely(running)) @@ -7612,7 +7687,6 @@ void sched_move_task(struct task_struct *tsk) enqueue_task(rq, tsk, 0); } -done: task_rq_unlock(rq, &flags); } @@ -7697,6 +7771,31 @@ unsigned long sched_group_shares(struct task_group *tg) return tg->shares; } +/* + * Ensure the total rt_ratio <= sysctl_sched_rt_ratio + */ +int sched_group_set_rt_ratio(struct task_group *tg, unsigned long rt_ratio) +{ + struct task_group *tgi; + unsigned long total = 0; + + rcu_read_lock(); + list_for_each_entry_rcu(tgi, &task_groups, list) + total += tgi->rt_ratio; + rcu_read_unlock(); + + if (total + rt_ratio - tg->rt_ratio > sysctl_sched_rt_ratio) + return -EINVAL; + + tg->rt_ratio = rt_ratio; + return 0; +} + +unsigned long sched_group_rt_ratio(struct task_group *tg) +{ + return tg->rt_ratio; +} + #endif /* CONFIG_FAIR_GROUP_SCHED */ #ifdef CONFIG_FAIR_CGROUP_SCHED @@ -7772,12 +7871,30 @@ static u64 cpu_shares_read_uint(struct cgroup *cgrp, struct cftype *cft) return (u64) tg->shares; } +static int cpu_rt_ratio_write_uint(struct cgroup *cgrp, struct cftype *cftype, + u64 rt_ratio_val) +{ + return sched_group_set_rt_ratio(cgroup_tg(cgrp), rt_ratio_val); +} + +static u64 cpu_rt_ratio_read_uint(struct cgroup *cgrp, struct cftype *cft) +{ + struct task_group *tg = cgroup_tg(cgrp); + + return (u64) tg->rt_ratio; +} + static struct cftype cpu_files[] = { { .name = "shares", .read_uint = cpu_shares_read_uint, .write_uint = cpu_shares_write_uint, }, + { + .name = "rt_ratio", + .read_uint = cpu_rt_ratio_read_uint, + .write_uint = cpu_rt_ratio_write_uint, + }, }; static int cpu_cgroup_populate(struct cgroup_subsys *ss, struct cgroup *cont) diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index fd10d965aa06..1178257613ad 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -45,47 +45,167 @@ static void update_rt_migration(struct rq *rq) } #endif /* CONFIG_SMP */ -static int sched_rt_ratio_exceeded(struct rq *rq, struct rt_rq *rt_rq) +static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se) { + return container_of(rt_se, struct task_struct, rt); +} + +static inline int on_rt_rq(struct sched_rt_entity *rt_se) +{ + return !list_empty(&rt_se->run_list); +} + +#ifdef CONFIG_FAIR_GROUP_SCHED + +static inline unsigned int sched_rt_ratio(struct rt_rq *rt_rq) +{ + if (!rt_rq->tg) + return SCHED_RT_FRAC; + + return rt_rq->tg->rt_ratio; +} + +#define for_each_leaf_rt_rq(rt_rq, rq) \ + list_for_each_entry(rt_rq, &rq->leaf_rt_rq_list, leaf_rt_rq_list) + +static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq) +{ + return rt_rq->rq; +} + +static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se) +{ + return rt_se->rt_rq; +} + +#define for_each_sched_rt_entity(rt_se) \ + for (; rt_se; rt_se = rt_se->parent) + +static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se) +{ + return rt_se->my_q; +} + +static void enqueue_rt_entity(struct sched_rt_entity *rt_se); +static void dequeue_rt_entity(struct sched_rt_entity *rt_se); + +static void sched_rt_ratio_enqueue(struct rt_rq *rt_rq) +{ + struct sched_rt_entity *rt_se = rt_rq->rt_se; + + if (rt_se && !on_rt_rq(rt_se) && rt_rq->rt_nr_running) { + enqueue_rt_entity(rt_se); + resched_task(rq_of_rt_rq(rt_rq)->curr); + } +} + +static void sched_rt_ratio_dequeue(struct rt_rq *rt_rq) +{ + struct sched_rt_entity *rt_se = rt_rq->rt_se; + + if (rt_se && on_rt_rq(rt_se)) + dequeue_rt_entity(rt_se); +} + +#else + +static inline unsigned int sched_rt_ratio(struct rt_rq *rt_rq) +{ + return sysctl_sched_rt_ratio; +} + +#define for_each_leaf_rt_rq(rt_rq, rq) \ + for (rt_rq = &rq->rt; rt_rq; rt_rq = NULL) + +static inline struct rq *rq_of_rt_rq(struct rt_rq *rt_rq) +{ + return container_of(rt_rq, struct rq, rt); +} + +static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se) +{ + struct task_struct *p = rt_task_of(rt_se); + struct rq *rq = task_rq(p); + + return &rq->rt; +} + +#define for_each_sched_rt_entity(rt_se) \ + for (; rt_se; rt_se = NULL) + +static inline struct rt_rq *group_rt_rq(struct sched_rt_entity *rt_se) +{ + return NULL; +} + +static inline void sched_rt_ratio_enqueue(struct rt_rq *rt_rq) +{ +} + +static inline void sched_rt_ratio_dequeue(struct rt_rq *rt_rq) +{ +} + +#endif + +static inline int rt_se_prio(struct sched_rt_entity *rt_se) +{ +#ifdef CONFIG_FAIR_GROUP_SCHED + struct rt_rq *rt_rq = group_rt_rq(rt_se); + + if (rt_rq) + return rt_rq->highest_prio; +#endif + + return rt_task_of(rt_se)->prio; +} + +static int sched_rt_ratio_exceeded(struct rt_rq *rt_rq) +{ + unsigned int rt_ratio = sched_rt_ratio(rt_rq); u64 period, ratio; - if (sysctl_sched_rt_ratio == SCHED_RT_FRAC) + if (rt_ratio == SCHED_RT_FRAC) return 0; if (rt_rq->rt_throttled) return 1; period = (u64)sysctl_sched_rt_period * NSEC_PER_MSEC; - ratio = (period * sysctl_sched_rt_ratio) >> SCHED_RT_FRAC_SHIFT; + ratio = (period * rt_ratio) >> SCHED_RT_FRAC_SHIFT; if (rt_rq->rt_time > ratio) { - rt_rq->rt_throttled = rq->clock + period - rt_rq->rt_time; + rt_rq->rt_throttled = 1; + sched_rt_ratio_dequeue(rt_rq); return 1; } return 0; } +static void __update_sched_rt_period(struct rt_rq *rt_rq, u64 period) +{ + unsigned long rt_ratio = sched_rt_ratio(rt_rq); + u64 ratio = (period * rt_ratio) >> SCHED_RT_FRAC_SHIFT; + + rt_rq->rt_time -= min(rt_rq->rt_time, ratio); + if (rt_rq->rt_throttled) { + rt_rq->rt_throttled = 0; + sched_rt_ratio_enqueue(rt_rq); + } +} + static void update_sched_rt_period(struct rq *rq) { - while (rq->clock > rq->rt_period_expire) { - u64 period, ratio; + struct rt_rq *rt_rq; + u64 period; + while (rq->clock > rq->rt_period_expire) { period = (u64)sysctl_sched_rt_period * NSEC_PER_MSEC; - ratio = (period * sysctl_sched_rt_ratio) >> SCHED_RT_FRAC_SHIFT; - - rq->rt.rt_time -= min(rq->rt.rt_time, ratio); rq->rt_period_expire += period; - } - /* - * When the rt throttle is expired, let them rip. - * (XXX: use hrtick when available) - */ - if (rq->rt.rt_throttled && rq->clock > rq->rt.rt_throttled) { - rq->rt.rt_throttled = 0; - if (!sched_rt_ratio_exceeded(rq, &rq->rt)) - resched_task(rq->curr); + for_each_leaf_rt_rq(rt_rq, rq) + __update_sched_rt_period(rt_rq, period); } } @@ -96,6 +216,8 @@ static void update_sched_rt_period(struct rq *rq) static void update_curr_rt(struct rq *rq) { struct task_struct *curr = rq->curr; + struct sched_rt_entity *rt_se = &curr->rt; + struct rt_rq *rt_rq = rt_rq_of_se(rt_se); u64 delta_exec; if (!task_has_rt_policy(curr)) @@ -111,95 +233,184 @@ static void update_curr_rt(struct rq *rq) curr->se.exec_start = rq->clock; cpuacct_charge(curr, delta_exec); - rq->rt.rt_time += delta_exec; - update_sched_rt_period(rq); - if (sched_rt_ratio_exceeded(rq, &rq->rt)) + rt_rq->rt_time += delta_exec; + /* + * might make it a tad more accurate: + * + * update_sched_rt_period(rq); + */ + if (sched_rt_ratio_exceeded(rt_rq)) resched_task(curr); } -static inline void inc_rt_tasks(struct task_struct *p, struct rq *rq) +static inline +void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) { - WARN_ON(!rt_task(p)); - rq->rt.rt_nr_running++; + WARN_ON(!rt_prio(rt_se_prio(rt_se))); + rt_rq->rt_nr_running++; +#if defined CONFIG_SMP || defined CONFIG_FAIR_GROUP_SCHED + if (rt_se_prio(rt_se) < rt_rq->highest_prio) + rt_rq->highest_prio = rt_se_prio(rt_se); +#endif #ifdef CONFIG_SMP - if (p->prio < rq->rt.highest_prio) - rq->rt.highest_prio = p->prio; - if (p->nr_cpus_allowed > 1) + if (rt_se->nr_cpus_allowed > 1) { + struct rq *rq = rq_of_rt_rq(rt_rq); rq->rt.rt_nr_migratory++; + } - update_rt_migration(rq); -#endif /* CONFIG_SMP */ + update_rt_migration(rq_of_rt_rq(rt_rq)); +#endif } -static inline void dec_rt_tasks(struct task_struct *p, struct rq *rq) +static inline +void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) { - WARN_ON(!rt_task(p)); - WARN_ON(!rq->rt.rt_nr_running); - rq->rt.rt_nr_running--; -#ifdef CONFIG_SMP - if (rq->rt.rt_nr_running) { + WARN_ON(!rt_prio(rt_se_prio(rt_se))); + WARN_ON(!rt_rq->rt_nr_running); + rt_rq->rt_nr_running--; +#if defined CONFIG_SMP || defined CONFIG_FAIR_GROUP_SCHED + if (rt_rq->rt_nr_running) { struct rt_prio_array *array; - WARN_ON(p->prio < rq->rt.highest_prio); - if (p->prio == rq->rt.highest_prio) { + WARN_ON(rt_se_prio(rt_se) < rt_rq->highest_prio); + if (rt_se_prio(rt_se) == rt_rq->highest_prio) { /* recalculate */ - array = &rq->rt.active; - rq->rt.highest_prio = + array = &rt_rq->active; + rt_rq->highest_prio = sched_find_first_bit(array->bitmap); } /* otherwise leave rq->highest prio alone */ } else - rq->rt.highest_prio = MAX_RT_PRIO; - if (p->nr_cpus_allowed > 1) + rt_rq->highest_prio = MAX_RT_PRIO; +#endif +#ifdef CONFIG_SMP + if (rt_se->nr_cpus_allowed > 1) { + struct rq *rq = rq_of_rt_rq(rt_rq); rq->rt.rt_nr_migratory--; + } - update_rt_migration(rq); + update_rt_migration(rq_of_rt_rq(rt_rq)); #endif /* CONFIG_SMP */ } -static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup) +static void enqueue_rt_entity(struct sched_rt_entity *rt_se) { - struct rt_prio_array *array = &rq->rt.active; + struct rt_rq *rt_rq = rt_rq_of_se(rt_se); + struct rt_prio_array *array = &rt_rq->active; + struct rt_rq *group_rq = group_rt_rq(rt_se); - list_add_tail(&p->rt.run_list, array->queue + p->prio); - __set_bit(p->prio, array->bitmap); - inc_cpu_load(rq, p->se.load.weight); + if (group_rq && group_rq->rt_throttled) + return; - inc_rt_tasks(p, rq); + list_add_tail(&rt_se->run_list, array->queue + rt_se_prio(rt_se)); + __set_bit(rt_se_prio(rt_se), array->bitmap); - if (wakeup) - p->rt.timeout = 0; + inc_rt_tasks(rt_se, rt_rq); +} + +static void dequeue_rt_entity(struct sched_rt_entity *rt_se) +{ + struct rt_rq *rt_rq = rt_rq_of_se(rt_se); + struct rt_prio_array *array = &rt_rq->active; + + list_del_init(&rt_se->run_list); + if (list_empty(array->queue + rt_se_prio(rt_se))) + __clear_bit(rt_se_prio(rt_se), array->bitmap); + + dec_rt_tasks(rt_se, rt_rq); +} + +/* + * Because the prio of an upper entry depends on the lower + * entries, we must remove entries top - down. + * + * XXX: O(1/2 h^2) because we can only walk up, not down the chain. + * doesn't matter much for now, as h=2 for GROUP_SCHED. + */ +static void dequeue_rt_stack(struct task_struct *p) +{ + struct sched_rt_entity *rt_se, *top_se; + + /* + * dequeue all, top - down. + */ + do { + rt_se = &p->rt; + top_se = NULL; + for_each_sched_rt_entity(rt_se) { + if (on_rt_rq(rt_se)) + top_se = rt_se; + } + if (top_se) + dequeue_rt_entity(top_se); + } while (top_se); } /* * Adding/removing a task to/from a priority array: */ +static void enqueue_task_rt(struct rq *rq, struct task_struct *p, int wakeup) +{ + struct sched_rt_entity *rt_se = &p->rt; + + if (wakeup) + rt_se->timeout = 0; + + dequeue_rt_stack(p); + + /* + * enqueue everybody, bottom - up. + */ + for_each_sched_rt_entity(rt_se) + enqueue_rt_entity(rt_se); + + inc_cpu_load(rq, p->se.load.weight); +} + static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep) { - struct rt_prio_array *array = &rq->rt.active; + struct sched_rt_entity *rt_se = &p->rt; + struct rt_rq *rt_rq; update_curr_rt(rq); - list_del(&p->rt.run_list); - if (list_empty(array->queue + p->prio)) - __clear_bit(p->prio, array->bitmap); - dec_cpu_load(rq, p->se.load.weight); + dequeue_rt_stack(p); + + /* + * re-enqueue all non-empty rt_rq entities. + */ + for_each_sched_rt_entity(rt_se) { + rt_rq = group_rt_rq(rt_se); + if (rt_rq && rt_rq->rt_nr_running) + enqueue_rt_entity(rt_se); + } - dec_rt_tasks(p, rq); + dec_cpu_load(rq, p->se.load.weight); } /* * Put task to the end of the run list without the overhead of dequeue * followed by enqueue. */ +static +void requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se) +{ + struct rt_prio_array *array = &rt_rq->active; + + list_move_tail(&rt_se->run_list, array->queue + rt_se_prio(rt_se)); +} + static void requeue_task_rt(struct rq *rq, struct task_struct *p) { - struct rt_prio_array *array = &rq->rt.active; + struct sched_rt_entity *rt_se = &p->rt; + struct rt_rq *rt_rq; - list_move_tail(&p->rt.run_list, array->queue + p->prio); + for_each_sched_rt_entity(rt_se) { + rt_rq = rt_rq_of_se(rt_se); + requeue_rt_entity(rt_rq, rt_se); + } } -static void -yield_task_rt(struct rq *rq) +static void yield_task_rt(struct rq *rq) { requeue_task_rt(rq, rq->curr); } @@ -229,7 +440,7 @@ static int select_task_rq_rt(struct task_struct *p, int sync) * cold cache anyway. */ if (unlikely(rt_task(rq->curr)) && - (p->nr_cpus_allowed > 1)) { + (p->rt.nr_cpus_allowed > 1)) { int cpu = find_lowest_rq(p); return (cpu == -1) ? task_cpu(p) : cpu; @@ -252,27 +463,51 @@ static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p) resched_task(rq->curr); } -static struct task_struct *pick_next_task_rt(struct rq *rq) +static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq, + struct rt_rq *rt_rq) { - struct rt_prio_array *array = &rq->rt.active; - struct task_struct *next; + struct rt_prio_array *array = &rt_rq->active; + struct sched_rt_entity *next = NULL; struct list_head *queue; - struct rt_rq *rt_rq = &rq->rt; int idx; - if (sched_rt_ratio_exceeded(rq, rt_rq)) - return NULL; + if (sched_rt_ratio_exceeded(rt_rq)) + goto out; idx = sched_find_first_bit(array->bitmap); - if (idx >= MAX_RT_PRIO) - return NULL; + BUG_ON(idx >= MAX_RT_PRIO); queue = array->queue + idx; - next = list_entry(queue->next, struct task_struct, rt.run_list); + next = list_entry(queue->next, struct sched_rt_entity, run_list); + out: + return next; +} - next->se.exec_start = rq->clock; +static struct task_struct *pick_next_task_rt(struct rq *rq) +{ + struct sched_rt_entity *rt_se; + struct task_struct *p; + struct rt_rq *rt_rq; - return next; + retry: + rt_rq = &rq->rt; + + if (unlikely(!rt_rq->rt_nr_running)) + return NULL; + + if (sched_rt_ratio_exceeded(rt_rq)) + return NULL; + + do { + rt_se = pick_next_rt_entity(rq, rt_rq); + if (unlikely(!rt_se)) + goto retry; + rt_rq = group_rt_rq(rt_se); + } while (rt_rq); + + p = rt_task_of(rt_se); + p->se.exec_start = rq->clock; + return p; } static void put_prev_task_rt(struct rq *rq, struct task_struct *p) @@ -282,6 +517,7 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p) } #ifdef CONFIG_SMP + /* Only try algorithms three times */ #define RT_MAX_TRIES 3 @@ -292,7 +528,7 @@ static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) { if (!task_running(rq, p) && (cpu < 0 || cpu_isset(cpu, p->cpus_allowed)) && - (p->nr_cpus_allowed > 1)) + (p->rt.nr_cpus_allowed > 1)) return 1; return 0; } @@ -300,52 +536,33 @@ static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) /* Return the second highest RT task, NULL otherwise */ static struct task_struct *pick_next_highest_task_rt(struct rq *rq, int cpu) { - struct rt_prio_array *array = &rq->rt.active; - struct task_struct *next; - struct list_head *queue; + struct task_struct *next = NULL; + struct sched_rt_entity *rt_se; + struct rt_prio_array *array; + struct rt_rq *rt_rq; int idx; - if (likely(rq->rt.rt_nr_running < 2)) - return NULL; - - idx = sched_find_first_bit(array->bitmap); - if (unlikely(idx >= MAX_RT_PRIO)) { - WARN_ON(1); /* rt_nr_running is bad */ - return NULL; - } - - queue = array->queue + idx; - BUG_ON(list_empty(queue)); - - next = list_entry(queue->next, struct task_struct, rt.run_list); - if (unlikely(pick_rt_task(rq, next, cpu))) - goto out; - - if (queue->next->next != queue) { - /* same prio task */ - next = list_entry(queue->next->next, struct task_struct, - rt.run_list); - if (pick_rt_task(rq, next, cpu)) - goto out; - } - - retry: - /* slower, but more flexible */ - idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); - if (unlikely(idx >= MAX_RT_PRIO)) - return NULL; - - queue = array->queue + idx; - BUG_ON(list_empty(queue)); - - list_for_each_entry(next, queue, rt.run_list) { - if (pick_rt_task(rq, next, cpu)) - goto out; + for_each_leaf_rt_rq(rt_rq, rq) { + array = &rt_rq->active; + idx = sched_find_first_bit(array->bitmap); + next_idx: + if (idx >= MAX_RT_PRIO) + continue; + if (next && next->prio < idx) + continue; + list_for_each_entry(rt_se, array->queue + idx, run_list) { + struct task_struct *p = rt_task_of(rt_se); + if (pick_rt_task(rq, p, cpu)) { + next = p; + break; + } + } + if (!next) { + idx = find_next_bit(array->bitmap, MAX_RT_PRIO, idx+1); + goto next_idx; + } } - goto retry; - - out: return next; } @@ -774,12 +991,12 @@ static void set_cpus_allowed_rt(struct task_struct *p, cpumask_t *new_mask) * Update the migration status of the RQ if we have an RT task * which is running AND changing its weight value. */ - if (p->se.on_rq && (weight != p->nr_cpus_allowed)) { + if (p->se.on_rq && (weight != p->rt.nr_cpus_allowed)) { struct rq *rq = task_rq(p); - if ((p->nr_cpus_allowed <= 1) && (weight > 1)) { + if ((p->rt.nr_cpus_allowed <= 1) && (weight > 1)) { rq->rt.rt_nr_migratory++; - } else if ((p->nr_cpus_allowed > 1) && (weight <= 1)) { + } else if ((p->rt.nr_cpus_allowed > 1) && (weight <= 1)) { BUG_ON(!rq->rt.rt_nr_migratory); rq->rt.rt_nr_migratory--; } @@ -788,7 +1005,7 @@ static void set_cpus_allowed_rt(struct task_struct *p, cpumask_t *new_mask) } p->cpus_allowed = *new_mask; - p->nr_cpus_allowed = weight; + p->rt.nr_cpus_allowed = weight; } /* Assumes rq->lock is held */ -- cgit v1.2.3-59-g8ed1b From 614ee1f61f667b02165c1ae0c1357048dc6d94a0 Mon Sep 17 00:00:00 2001 From: Mike Galbraith Date: Fri, 25 Jan 2008 21:08:30 +0100 Subject: sched: pull_rt_task() cleanup "goto out" is an odd way to spell "skip". Signed-off-by: Mike Galbraith Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 10 ++++------ 1 file changed, 4 insertions(+), 6 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 1178257613ad..1144bf55669d 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -877,10 +877,8 @@ static int pull_rt_task(struct rq *this_rq) /* * Are there still pullable RT tasks? */ - if (src_rq->rt.rt_nr_running <= 1) { - spin_unlock(&src_rq->lock); - continue; - } + if (src_rq->rt.rt_nr_running <= 1) + goto skip; p = pick_next_highest_task_rt(src_rq, this_cpu); @@ -904,7 +902,7 @@ static int pull_rt_task(struct rq *this_rq) */ if (p->prio < src_rq->curr->prio || (next && next->prio < src_rq->curr->prio)) - goto out; + goto skip; ret = 1; @@ -924,7 +922,7 @@ static int pull_rt_task(struct rq *this_rq) next = p; } - out: + skip: spin_unlock(&src_rq->lock); } -- cgit v1.2.3-59-g8ed1b From 48d5e258216f1c7713633439beb98a38c7290649 Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Fri, 25 Jan 2008 21:08:31 +0100 Subject: sched: rt throttling vs no_hz We need to teach no_hz about the rt throttling because its tick driven. Signed-off-by: Peter Zijlstra Signed-off-by: Ingo Molnar --- include/linux/sched.h | 2 ++ kernel/sched.c | 23 ++++++++++++++++++++++- kernel/sched_rt.c | 30 ++++++++++++++++-------------- kernel/time/tick-sched.c | 5 +++++ 4 files changed, 45 insertions(+), 15 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/include/linux/sched.h b/include/linux/sched.h index 04eecbf0241e..acadcab89ef9 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -230,6 +230,8 @@ static inline int select_nohz_load_balancer(int cpu) } #endif +extern unsigned long rt_needs_cpu(int cpu); + /* * Only dump TASK_* tasks. (0 for all tasks) */ diff --git a/kernel/sched.c b/kernel/sched.c index 5ea2c533b432..22712b2e058a 100644 --- a/kernel/sched.c +++ b/kernel/sched.c @@ -442,6 +442,7 @@ struct rq { struct cfs_rq cfs; struct rt_rq rt; u64 rt_period_expire; + int rt_throttled; #ifdef CONFIG_FAIR_GROUP_SCHED /* list of leaf cfs_rq on this cpu: */ @@ -594,6 +595,23 @@ static void update_rq_clock(struct rq *rq) #define task_rq(p) cpu_rq(task_cpu(p)) #define cpu_curr(cpu) (cpu_rq(cpu)->curr) +unsigned long rt_needs_cpu(int cpu) +{ + struct rq *rq = cpu_rq(cpu); + u64 delta; + + if (!rq->rt_throttled) + return 0; + + if (rq->clock > rq->rt_period_expire) + return 1; + + delta = rq->rt_period_expire - rq->clock; + do_div(delta, NSEC_PER_SEC / HZ); + + return (unsigned long)delta; +} + /* * Tunables that become constants when CONFIG_SCHED_DEBUG is off: */ @@ -7102,9 +7120,11 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq) /* delimiter for bitsearch: */ __set_bit(MAX_RT_PRIO, array->bitmap); +#if defined CONFIG_SMP || defined CONFIG_FAIR_GROUP_SCHED + rt_rq->highest_prio = MAX_RT_PRIO; +#endif #ifdef CONFIG_SMP rt_rq->rt_nr_migratory = 0; - rt_rq->highest_prio = MAX_RT_PRIO; rt_rq->overloaded = 0; #endif @@ -7191,6 +7211,7 @@ void __init sched_init(void) &per_cpu(init_sched_rt_entity, i), i, 1); #endif rq->rt_period_expire = 0; + rq->rt_throttled = 0; for (j = 0; j < CPU_LOAD_IDX_MAX; j++) rq->cpu_load[j] = 0; diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 1144bf55669d..8bfdb3f8a52d 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -175,7 +175,11 @@ static int sched_rt_ratio_exceeded(struct rt_rq *rt_rq) ratio = (period * rt_ratio) >> SCHED_RT_FRAC_SHIFT; if (rt_rq->rt_time > ratio) { + struct rq *rq = rq_of_rt_rq(rt_rq); + + rq->rt_throttled = 1; rt_rq->rt_throttled = 1; + sched_rt_ratio_dequeue(rt_rq); return 1; } @@ -183,18 +187,6 @@ static int sched_rt_ratio_exceeded(struct rt_rq *rt_rq) return 0; } -static void __update_sched_rt_period(struct rt_rq *rt_rq, u64 period) -{ - unsigned long rt_ratio = sched_rt_ratio(rt_rq); - u64 ratio = (period * rt_ratio) >> SCHED_RT_FRAC_SHIFT; - - rt_rq->rt_time -= min(rt_rq->rt_time, ratio); - if (rt_rq->rt_throttled) { - rt_rq->rt_throttled = 0; - sched_rt_ratio_enqueue(rt_rq); - } -} - static void update_sched_rt_period(struct rq *rq) { struct rt_rq *rt_rq; @@ -204,8 +196,18 @@ static void update_sched_rt_period(struct rq *rq) period = (u64)sysctl_sched_rt_period * NSEC_PER_MSEC; rq->rt_period_expire += period; - for_each_leaf_rt_rq(rt_rq, rq) - __update_sched_rt_period(rt_rq, period); + for_each_leaf_rt_rq(rt_rq, rq) { + unsigned long rt_ratio = sched_rt_ratio(rt_rq); + u64 ratio = (period * rt_ratio) >> SCHED_RT_FRAC_SHIFT; + + rt_rq->rt_time -= min(rt_rq->rt_time, ratio); + if (rt_rq->rt_throttled) { + rt_rq->rt_throttled = 0; + sched_rt_ratio_enqueue(rt_rq); + } + } + + rq->rt_throttled = 0; } } diff --git a/kernel/time/tick-sched.c b/kernel/time/tick-sched.c index cb89fa8db110..5f9fb645b725 100644 --- a/kernel/time/tick-sched.c +++ b/kernel/time/tick-sched.c @@ -153,6 +153,7 @@ void tick_nohz_update_jiffies(void) void tick_nohz_stop_sched_tick(void) { unsigned long seq, last_jiffies, next_jiffies, delta_jiffies, flags; + unsigned long rt_jiffies; struct tick_sched *ts; ktime_t last_update, expires, now, delta; struct clock_event_device *dev = __get_cpu_var(tick_cpu_device).evtdev; @@ -216,6 +217,10 @@ void tick_nohz_stop_sched_tick(void) next_jiffies = get_next_timer_interrupt(last_jiffies); delta_jiffies = next_jiffies - last_jiffies; + rt_jiffies = rt_needs_cpu(cpu); + if (rt_jiffies && rt_jiffies < delta_jiffies) + delta_jiffies = rt_jiffies; + if (rcu_needs_cpu(cpu)) delta_jiffies = 1; /* -- cgit v1.2.3-59-g8ed1b From 1020387f5f3b52929b387103cf976321981f8e26 Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Fri, 25 Jan 2008 21:08:32 +0100 Subject: sched: rt-group: reduce rescheduling Only reschedule if the new group has a higher prio task. Signed-off-by: Peter Zijlstra Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 8bfdb3f8a52d..f1f215db3bd0 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -94,8 +94,11 @@ static void sched_rt_ratio_enqueue(struct rt_rq *rt_rq) struct sched_rt_entity *rt_se = rt_rq->rt_se; if (rt_se && !on_rt_rq(rt_se) && rt_rq->rt_nr_running) { + struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr; + enqueue_rt_entity(rt_se); - resched_task(rq_of_rt_rq(rt_rq)->curr); + if (rt_rq->highest_prio < curr->prio) + resched_task(curr); } } -- cgit v1.2.3-59-g8ed1b From 5a52dd50091b6a6e710a1293db741028f8cc5aac Mon Sep 17 00:00:00 2001 From: Peter Zijlstra Date: Fri, 25 Jan 2008 21:08:32 +0100 Subject: sched: rt-watchdog: fix .rlim_max = RLIM_INFINITY Remove the curious logic to set it_sched_expires in the future. It useless because rt.timeout wouldn't be incremented anyway. Explicity check for RLIM_INFINITY as a test programm that had a 1s soft limit and a inf hard limit would SIGKILL at 1s. This is because RLIM_INFINITY+d-1 is d-2. Signed-off-by: Peter Zijlsta CC: Michal Schmidt Signed-off-by: Ingo Molnar --- kernel/posix-cpu-timers.c | 3 ++- kernel/sched_rt.c | 8 +------- 2 files changed, 3 insertions(+), 8 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/posix-cpu-timers.c b/kernel/posix-cpu-timers.c index 2c076b36c4f6..0b7c82ac467e 100644 --- a/kernel/posix-cpu-timers.c +++ b/kernel/posix-cpu-timers.c @@ -1020,7 +1020,8 @@ static void check_thread_timers(struct task_struct *tsk, unsigned long hard = sig->rlim[RLIMIT_RTTIME].rlim_max; unsigned long *soft = &sig->rlim[RLIMIT_RTTIME].rlim_cur; - if (tsk->rt.timeout > DIV_ROUND_UP(hard, USEC_PER_SEC/HZ)) { + if (hard != RLIM_INFINITY && + tsk->rt.timeout > DIV_ROUND_UP(hard, USEC_PER_SEC/HZ)) { /* * At the hard limit, we just die. * No need to calculate anything else now. diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index f1f215db3bd0..2dac5ebb8bcb 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -1125,13 +1125,7 @@ static void watchdog(struct rq *rq, struct task_struct *p) p->rt.timeout++; next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ); - if (next > p->rt.timeout) { - u64 next_time = p->se.sum_exec_runtime; - - next_time += next * (NSEC_PER_SEC/HZ); - if (p->it_sched_expires > next_time) - p->it_sched_expires = next_time; - } else + if (p->rt.timeout > next) p->it_sched_expires = p->se.sum_exec_runtime; } } -- cgit v1.2.3-59-g8ed1b From 326587b840785c60f5dc18557235a23bafefd620 Mon Sep 17 00:00:00 2001 From: Dmitry Adamushko Date: Fri, 25 Jan 2008 21:08:34 +0100 Subject: sched: fix goto retry in pick_next_task_rt() looking at it one more time: (1) it looks to me that there is no need to call sched_rt_ratio_exceeded() from pick_next_rt_entity() - [ for CONFIG_FAIR_GROUP_SCHED ] queues with rt_rq->rt_throttled are not within this 'tree-like hierarchy' (or whatever we should call it :-) - there is also no need to re-check 'rt_rq->rt_time > ratio' at this point as 'rt_rq->rt_time' couldn't have been increased since the last call to update_curr_rt() (which obviously calls sched_rt_ratio_esceeded()) well, it might be that 'ratio' for this rt_rq has been re-configured (and the period over which this rt_rq was active has not yet been finished)... but I don't think we should really take this into account. (2) now pick_next_rt_entity() must never return NULL, so let's change pick_next_task_rt() accordingly. Signed-off-by: Dmitry Adamushko Signed-off-by: Ingo Molnar --- kernel/sched_rt.c | 9 ++------- 1 file changed, 2 insertions(+), 7 deletions(-) (limited to 'kernel/sched_rt.c') diff --git a/kernel/sched_rt.c b/kernel/sched_rt.c index 2dac5ebb8bcb..274b40d7bef2 100644 --- a/kernel/sched_rt.c +++ b/kernel/sched_rt.c @@ -476,15 +476,12 @@ static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq, struct list_head *queue; int idx; - if (sched_rt_ratio_exceeded(rt_rq)) - goto out; - idx = sched_find_first_bit(array->bitmap); BUG_ON(idx >= MAX_RT_PRIO); queue = array->queue + idx; next = list_entry(queue->next, struct sched_rt_entity, run_list); - out: + return next; } @@ -494,7 +491,6 @@ static struct task_struct *pick_next_task_rt(struct rq *rq) struct task_struct *p; struct rt_rq *rt_rq; - retry: rt_rq = &rq->rt; if (unlikely(!rt_rq->rt_nr_running)) @@ -505,8 +501,7 @@ static struct task_struct *pick_next_task_rt(struct rq *rq) do { rt_se = pick_next_rt_entity(rq, rt_rq); - if (unlikely(!rt_se)) - goto retry; + BUG_ON(!rt_se); rt_rq = group_rt_rq(rt_se); } while (rt_rq); -- cgit v1.2.3-59-g8ed1b