| /* |
| * Real-Time Scheduling Class (mapped to the SCHED_FIFO and SCHED_RR |
| * policies) |
| */ |
| |
| #include "sched.h" |
| |
| #include <linux/slab.h> |
| |
| int sched_rr_timeslice = RR_TIMESLICE; |
| |
| static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun); |
| |
| struct rt_bandwidth def_rt_bandwidth; |
| |
| static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer) |
| { |
| struct rt_bandwidth *rt_b = |
| container_of(timer, struct rt_bandwidth, rt_period_timer); |
| ktime_t now; |
| int overrun; |
| int idle = 0; |
| |
| for (;;) { |
| now = hrtimer_cb_get_time(timer); |
| overrun = hrtimer_forward(timer, now, rt_b->rt_period); |
| |
| if (!overrun) |
| break; |
| |
| idle = do_sched_rt_period_timer(rt_b, overrun); |
| } |
| |
| return idle ? HRTIMER_NORESTART : HRTIMER_RESTART; |
| } |
| |
| void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime) |
| { |
| rt_b->rt_period = ns_to_ktime(period); |
| rt_b->rt_runtime = runtime; |
| |
| raw_spin_lock_init(&rt_b->rt_runtime_lock); |
| |
| hrtimer_init(&rt_b->rt_period_timer, |
| CLOCK_MONOTONIC, HRTIMER_MODE_REL); |
| rt_b->rt_period_timer.function = sched_rt_period_timer; |
| } |
| |
| static void start_rt_bandwidth(struct rt_bandwidth *rt_b) |
| { |
| if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF) |
| return; |
| |
| if (hrtimer_active(&rt_b->rt_period_timer)) |
| return; |
| |
| raw_spin_lock(&rt_b->rt_runtime_lock); |
| start_bandwidth_timer(&rt_b->rt_period_timer, rt_b->rt_period); |
| raw_spin_unlock(&rt_b->rt_runtime_lock); |
| } |
| |
| 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); |
| |
| #if defined CONFIG_SMP |
| rt_rq->highest_prio.curr = MAX_RT_PRIO; |
| rt_rq->highest_prio.next = MAX_RT_PRIO; |
| rt_rq->rt_nr_migratory = 0; |
| rt_rq->overloaded = 0; |
| plist_head_init(&rt_rq->pushable_tasks); |
| #endif |
| /* We start is dequeued state, because no RT tasks are queued */ |
| rt_rq->rt_queued = 0; |
| |
| rt_rq->rt_time = 0; |
| rt_rq->rt_throttled = 0; |
| rt_rq->rt_runtime = 0; |
| raw_spin_lock_init(&rt_rq->rt_runtime_lock); |
| } |
| |
| #ifdef CONFIG_RT_GROUP_SCHED |
| static void destroy_rt_bandwidth(struct rt_bandwidth *rt_b) |
| { |
| hrtimer_cancel(&rt_b->rt_period_timer); |
| } |
| |
| #define rt_entity_is_task(rt_se) (!(rt_se)->my_q) |
| |
| static inline struct task_struct *rt_task_of(struct sched_rt_entity *rt_se) |
| { |
| #ifdef CONFIG_SCHED_DEBUG |
| WARN_ON_ONCE(!rt_entity_is_task(rt_se)); |
| #endif |
| return container_of(rt_se, struct task_struct, rt); |
| } |
| |
| 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; |
| } |
| |
| static inline struct rq *rq_of_rt_se(struct sched_rt_entity *rt_se) |
| { |
| struct rt_rq *rt_rq = rt_se->rt_rq; |
| |
| return rt_rq->rq; |
| } |
| |
| void free_rt_sched_group(struct task_group *tg) |
| { |
| int i; |
| |
| if (tg->rt_se) |
| destroy_rt_bandwidth(&tg->rt_bandwidth); |
| |
| for_each_possible_cpu(i) { |
| if (tg->rt_rq) |
| kfree(tg->rt_rq[i]); |
| if (tg->rt_se) |
| kfree(tg->rt_se[i]); |
| } |
| |
| kfree(tg->rt_rq); |
| kfree(tg->rt_se); |
| } |
| |
| void init_tg_rt_entry(struct task_group *tg, struct rt_rq *rt_rq, |
| struct sched_rt_entity *rt_se, int cpu, |
| struct sched_rt_entity *parent) |
| { |
| struct rq *rq = cpu_rq(cpu); |
| |
| rt_rq->highest_prio.curr = MAX_RT_PRIO; |
| rt_rq->rt_nr_boosted = 0; |
| rt_rq->rq = rq; |
| rt_rq->tg = tg; |
| |
| tg->rt_rq[cpu] = rt_rq; |
| tg->rt_se[cpu] = rt_se; |
| |
| if (!rt_se) |
| return; |
| |
| if (!parent) |
| rt_se->rt_rq = &rq->rt; |
| else |
| rt_se->rt_rq = parent->my_q; |
| |
| rt_se->my_q = rt_rq; |
| rt_se->parent = parent; |
| INIT_LIST_HEAD(&rt_se->run_list); |
| } |
| |
| int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent) |
| { |
| struct rt_rq *rt_rq; |
| struct sched_rt_entity *rt_se; |
| int i; |
| |
| tg->rt_rq = kzalloc(sizeof(rt_rq) * nr_cpu_ids, GFP_KERNEL); |
| if (!tg->rt_rq) |
| goto err; |
| tg->rt_se = kzalloc(sizeof(rt_se) * nr_cpu_ids, GFP_KERNEL); |
| if (!tg->rt_se) |
| goto err; |
| |
| init_rt_bandwidth(&tg->rt_bandwidth, |
| ktime_to_ns(def_rt_bandwidth.rt_period), 0); |
| |
| for_each_possible_cpu(i) { |
| rt_rq = kzalloc_node(sizeof(struct rt_rq), |
| GFP_KERNEL, cpu_to_node(i)); |
| if (!rt_rq) |
| goto err; |
| |
| rt_se = kzalloc_node(sizeof(struct sched_rt_entity), |
| GFP_KERNEL, cpu_to_node(i)); |
| if (!rt_se) |
| goto err_free_rq; |
| |
| init_rt_rq(rt_rq, cpu_rq(i)); |
| rt_rq->rt_runtime = tg->rt_bandwidth.rt_runtime; |
| init_tg_rt_entry(tg, rt_rq, rt_se, i, parent->rt_se[i]); |
| } |
| |
| return 1; |
| |
| err_free_rq: |
| kfree(rt_rq); |
| err: |
| return 0; |
| } |
| |
| #else /* CONFIG_RT_GROUP_SCHED */ |
| |
| #define rt_entity_is_task(rt_se) (1) |
| |
| 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 struct rq *rq_of_rt_rq(struct rt_rq *rt_rq) |
| { |
| return container_of(rt_rq, struct rq, rt); |
| } |
| |
| static inline struct rq *rq_of_rt_se(struct sched_rt_entity *rt_se) |
| { |
| struct task_struct *p = rt_task_of(rt_se); |
| |
| return task_rq(p); |
| } |
| |
| static inline struct rt_rq *rt_rq_of_se(struct sched_rt_entity *rt_se) |
| { |
| struct rq *rq = rq_of_rt_se(rt_se); |
| |
| return &rq->rt; |
| } |
| |
| void free_rt_sched_group(struct task_group *tg) { } |
| |
| int alloc_rt_sched_group(struct task_group *tg, struct task_group *parent) |
| { |
| return 1; |
| } |
| #endif /* CONFIG_RT_GROUP_SCHED */ |
| |
| #ifdef CONFIG_SMP |
| |
| static int pull_rt_task(struct rq *this_rq); |
| |
| static inline bool need_pull_rt_task(struct rq *rq, struct task_struct *prev) |
| { |
| /* Try to pull RT tasks here if we lower this rq's prio */ |
| return rq->rt.highest_prio.curr > prev->prio; |
| } |
| |
| static inline int rt_overloaded(struct rq *rq) |
| { |
| return atomic_read(&rq->rd->rto_count); |
| } |
| |
| static inline void rt_set_overload(struct rq *rq) |
| { |
| if (!rq->online) |
| return; |
| |
| cpumask_set_cpu(rq->cpu, rq->rd->rto_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. |
| * |
| * Matched by the barrier in pull_rt_task(). |
| */ |
| smp_wmb(); |
| atomic_inc(&rq->rd->rto_count); |
| } |
| |
| static inline void rt_clear_overload(struct rq *rq) |
| { |
| if (!rq->online) |
| return; |
| |
| /* the order here really doesn't matter */ |
| atomic_dec(&rq->rd->rto_count); |
| cpumask_clear_cpu(rq->cpu, rq->rd->rto_mask); |
| } |
| |
| static void update_rt_migration(struct rt_rq *rt_rq) |
| { |
| if (rt_rq->rt_nr_migratory && rt_rq->rt_nr_total > 1) { |
| if (!rt_rq->overloaded) { |
| rt_set_overload(rq_of_rt_rq(rt_rq)); |
| rt_rq->overloaded = 1; |
| } |
| } else if (rt_rq->overloaded) { |
| rt_clear_overload(rq_of_rt_rq(rt_rq)); |
| rt_rq->overloaded = 0; |
| } |
| } |
| |
| static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) |
| { |
| struct task_struct *p; |
| |
| if (!rt_entity_is_task(rt_se)) |
| return; |
| |
| p = rt_task_of(rt_se); |
| rt_rq = &rq_of_rt_rq(rt_rq)->rt; |
| |
| rt_rq->rt_nr_total++; |
| if (p->nr_cpus_allowed > 1) |
| rt_rq->rt_nr_migratory++; |
| |
| update_rt_migration(rt_rq); |
| } |
| |
| static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) |
| { |
| struct task_struct *p; |
| |
| if (!rt_entity_is_task(rt_se)) |
| return; |
| |
| p = rt_task_of(rt_se); |
| rt_rq = &rq_of_rt_rq(rt_rq)->rt; |
| |
| rt_rq->rt_nr_total--; |
| if (p->nr_cpus_allowed > 1) |
| rt_rq->rt_nr_migratory--; |
| |
| update_rt_migration(rt_rq); |
| } |
| |
| static inline int has_pushable_tasks(struct rq *rq) |
| { |
| return !plist_head_empty(&rq->rt.pushable_tasks); |
| } |
| |
| static inline void set_post_schedule(struct rq *rq) |
| { |
| /* |
| * We detect this state here so that we can avoid taking the RQ |
| * lock again later if there is no need to push |
| */ |
| rq->post_schedule = has_pushable_tasks(rq); |
| } |
| |
| static void enqueue_pushable_task(struct rq *rq, struct task_struct *p) |
| { |
| plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks); |
| plist_node_init(&p->pushable_tasks, p->prio); |
| plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks); |
| |
| /* Update the highest prio pushable task */ |
| if (p->prio < rq->rt.highest_prio.next) |
| rq->rt.highest_prio.next = p->prio; |
| } |
| |
| static void dequeue_pushable_task(struct rq *rq, struct task_struct *p) |
| { |
| plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks); |
| |
| /* Update the new highest prio pushable task */ |
| if (has_pushable_tasks(rq)) { |
| p = plist_first_entry(&rq->rt.pushable_tasks, |
| struct task_struct, pushable_tasks); |
| rq->rt.highest_prio.next = p->prio; |
| } else |
| rq->rt.highest_prio.next = MAX_RT_PRIO; |
| } |
| |
| #else |
| |
| static inline void enqueue_pushable_task(struct rq *rq, struct task_struct *p) |
| { |
| } |
| |
| static inline void dequeue_pushable_task(struct rq *rq, struct task_struct *p) |
| { |
| } |
| |
| static inline |
| void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) |
| { |
| } |
| |
| static inline |
| void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) |
| { |
| } |
| |
| static inline bool need_pull_rt_task(struct rq *rq, struct task_struct *prev) |
| { |
| return false; |
| } |
| |
| static inline int pull_rt_task(struct rq *this_rq) |
| { |
| return 0; |
| } |
| |
| static inline void set_post_schedule(struct rq *rq) |
| { |
| } |
| #endif /* CONFIG_SMP */ |
| |
| static void enqueue_top_rt_rq(struct rt_rq *rt_rq); |
| static void dequeue_top_rt_rq(struct rt_rq *rt_rq); |
| |
| static inline int on_rt_rq(struct sched_rt_entity *rt_se) |
| { |
| return !list_empty(&rt_se->run_list); |
| } |
| |
| #ifdef CONFIG_RT_GROUP_SCHED |
| |
| static inline u64 sched_rt_runtime(struct rt_rq *rt_rq) |
| { |
| if (!rt_rq->tg) |
| return RUNTIME_INF; |
| |
| return rt_rq->rt_runtime; |
| } |
| |
| static inline u64 sched_rt_period(struct rt_rq *rt_rq) |
| { |
| return ktime_to_ns(rt_rq->tg->rt_bandwidth.rt_period); |
| } |
| |
| typedef struct task_group *rt_rq_iter_t; |
| |
| static inline struct task_group *next_task_group(struct task_group *tg) |
| { |
| do { |
| tg = list_entry_rcu(tg->list.next, |
| typeof(struct task_group), list); |
| } while (&tg->list != &task_groups && task_group_is_autogroup(tg)); |
| |
| if (&tg->list == &task_groups) |
| tg = NULL; |
| |
| return tg; |
| } |
| |
| #define for_each_rt_rq(rt_rq, iter, rq) \ |
| for (iter = container_of(&task_groups, typeof(*iter), list); \ |
| (iter = next_task_group(iter)) && \ |
| (rt_rq = iter->rt_rq[cpu_of(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, bool head); |
| static void dequeue_rt_entity(struct sched_rt_entity *rt_se); |
| |
| static void sched_rt_rq_enqueue(struct rt_rq *rt_rq) |
| { |
| struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr; |
| struct sched_rt_entity *rt_se; |
| |
| int cpu = cpu_of(rq_of_rt_rq(rt_rq)); |
| |
| rt_se = rt_rq->tg->rt_se[cpu]; |
| |
| if (rt_rq->rt_nr_running) { |
| if (!rt_se) |
| enqueue_top_rt_rq(rt_rq); |
| else if (!on_rt_rq(rt_se)) |
| enqueue_rt_entity(rt_se, false); |
| |
| if (rt_rq->highest_prio.curr < curr->prio) |
| resched_task(curr); |
| } |
| } |
| |
| static void sched_rt_rq_dequeue(struct rt_rq *rt_rq) |
| { |
| struct sched_rt_entity *rt_se; |
| int cpu = cpu_of(rq_of_rt_rq(rt_rq)); |
| |
| rt_se = rt_rq->tg->rt_se[cpu]; |
| |
| if (!rt_se) |
| dequeue_top_rt_rq(rt_rq); |
| else if (on_rt_rq(rt_se)) |
| dequeue_rt_entity(rt_se); |
| } |
| |
| static inline int rt_rq_throttled(struct rt_rq *rt_rq) |
| { |
| return rt_rq->rt_throttled && !rt_rq->rt_nr_boosted; |
| } |
| |
| static int rt_se_boosted(struct sched_rt_entity *rt_se) |
| { |
| struct rt_rq *rt_rq = group_rt_rq(rt_se); |
| struct task_struct *p; |
| |
| if (rt_rq) |
| return !!rt_rq->rt_nr_boosted; |
| |
| p = rt_task_of(rt_se); |
| return p->prio != p->normal_prio; |
| } |
| |
| #ifdef CONFIG_SMP |
| static inline const struct cpumask *sched_rt_period_mask(void) |
| { |
| return this_rq()->rd->span; |
| } |
| #else |
| static inline const struct cpumask *sched_rt_period_mask(void) |
| { |
| return cpu_online_mask; |
| } |
| #endif |
| |
| static inline |
| struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu) |
| { |
| return container_of(rt_b, struct task_group, rt_bandwidth)->rt_rq[cpu]; |
| } |
| |
| static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq) |
| { |
| return &rt_rq->tg->rt_bandwidth; |
| } |
| |
| #else /* !CONFIG_RT_GROUP_SCHED */ |
| |
| static inline u64 sched_rt_runtime(struct rt_rq *rt_rq) |
| { |
| return rt_rq->rt_runtime; |
| } |
| |
| static inline u64 sched_rt_period(struct rt_rq *rt_rq) |
| { |
| return ktime_to_ns(def_rt_bandwidth.rt_period); |
| } |
| |
| typedef struct rt_rq *rt_rq_iter_t; |
| |
| #define for_each_rt_rq(rt_rq, iter, rq) \ |
| for ((void) iter, rt_rq = &rq->rt; rt_rq; rt_rq = NULL) |
| |
| #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_rq_enqueue(struct rt_rq *rt_rq) |
| { |
| struct rq *rq = rq_of_rt_rq(rt_rq); |
| |
| if (!rt_rq->rt_nr_running) |
| return; |
| |
| enqueue_top_rt_rq(rt_rq); |
| resched_task(rq->curr); |
| } |
| |
| static inline void sched_rt_rq_dequeue(struct rt_rq *rt_rq) |
| { |
| dequeue_top_rt_rq(rt_rq); |
| } |
| |
| static inline int rt_rq_throttled(struct rt_rq *rt_rq) |
| { |
| return rt_rq->rt_throttled; |
| } |
| |
| static inline const struct cpumask *sched_rt_period_mask(void) |
| { |
| return cpu_online_mask; |
| } |
| |
| static inline |
| struct rt_rq *sched_rt_period_rt_rq(struct rt_bandwidth *rt_b, int cpu) |
| { |
| return &cpu_rq(cpu)->rt; |
| } |
| |
| static inline struct rt_bandwidth *sched_rt_bandwidth(struct rt_rq *rt_rq) |
| { |
| return &def_rt_bandwidth; |
| } |
| |
| #endif /* CONFIG_RT_GROUP_SCHED */ |
| |
| bool sched_rt_bandwidth_account(struct rt_rq *rt_rq) |
| { |
| struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq); |
| |
| return (hrtimer_active(&rt_b->rt_period_timer) || |
| rt_rq->rt_time < rt_b->rt_runtime); |
| } |
| |
| #ifdef CONFIG_SMP |
| /* |
| * We ran out of runtime, see if we can borrow some from our neighbours. |
| */ |
| static int do_balance_runtime(struct rt_rq *rt_rq) |
| { |
| struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq); |
| struct root_domain *rd = rq_of_rt_rq(rt_rq)->rd; |
| int i, weight, more = 0; |
| u64 rt_period; |
| |
| weight = cpumask_weight(rd->span); |
| |
| raw_spin_lock(&rt_b->rt_runtime_lock); |
| rt_period = ktime_to_ns(rt_b->rt_period); |
| for_each_cpu(i, rd->span) { |
| struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i); |
| s64 diff; |
| |
| if (iter == rt_rq) |
| continue; |
| |
| raw_spin_lock(&iter->rt_runtime_lock); |
| /* |
| * Either all rqs have inf runtime and there's nothing to steal |
| * or __disable_runtime() below sets a specific rq to inf to |
| * indicate its been disabled and disalow stealing. |
| */ |
| if (iter->rt_runtime == RUNTIME_INF) |
| goto next; |
| |
| /* |
| * From runqueues with spare time, take 1/n part of their |
| * spare time, but no more than our period. |
| */ |
| diff = iter->rt_runtime - iter->rt_time; |
| if (diff > 0) { |
| diff = div_u64((u64)diff, weight); |
| if (rt_rq->rt_runtime + diff > rt_period) |
| diff = rt_period - rt_rq->rt_runtime; |
| iter->rt_runtime -= diff; |
| rt_rq->rt_runtime += diff; |
| more = 1; |
| if (rt_rq->rt_runtime == rt_period) { |
| raw_spin_unlock(&iter->rt_runtime_lock); |
| break; |
| } |
| } |
| next: |
| raw_spin_unlock(&iter->rt_runtime_lock); |
| } |
| raw_spin_unlock(&rt_b->rt_runtime_lock); |
| |
| return more; |
| } |
| |
| /* |
| * Ensure this RQ takes back all the runtime it lend to its neighbours. |
| */ |
| static void __disable_runtime(struct rq *rq) |
| { |
| struct root_domain *rd = rq->rd; |
| rt_rq_iter_t iter; |
| struct rt_rq *rt_rq; |
| |
| if (unlikely(!scheduler_running)) |
| return; |
| |
| for_each_rt_rq(rt_rq, iter, rq) { |
| struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq); |
| s64 want; |
| int i; |
| |
| raw_spin_lock(&rt_b->rt_runtime_lock); |
| raw_spin_lock(&rt_rq->rt_runtime_lock); |
| /* |
| * Either we're all inf and nobody needs to borrow, or we're |
| * already disabled and thus have nothing to do, or we have |
| * exactly the right amount of runtime to take out. |
| */ |
| if (rt_rq->rt_runtime == RUNTIME_INF || |
| rt_rq->rt_runtime == rt_b->rt_runtime) |
| goto balanced; |
| raw_spin_unlock(&rt_rq->rt_runtime_lock); |
| |
| /* |
| * Calculate the difference between what we started out with |
| * and what we current have, that's the amount of runtime |
| * we lend and now have to reclaim. |
| */ |
| want = rt_b->rt_runtime - rt_rq->rt_runtime; |
| |
| /* |
| * Greedy reclaim, take back as much as we can. |
| */ |
| for_each_cpu(i, rd->span) { |
| struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i); |
| s64 diff; |
| |
| /* |
| * Can't reclaim from ourselves or disabled runqueues. |
| */ |
| if (iter == rt_rq || iter->rt_runtime == RUNTIME_INF) |
| continue; |
| |
| raw_spin_lock(&iter->rt_runtime_lock); |
| if (want > 0) { |
| diff = min_t(s64, iter->rt_runtime, want); |
| iter->rt_runtime -= diff; |
| want -= diff; |
| } else { |
| iter->rt_runtime -= want; |
| want -= want; |
| } |
| raw_spin_unlock(&iter->rt_runtime_lock); |
| |
| if (!want) |
| break; |
| } |
| |
| raw_spin_lock(&rt_rq->rt_runtime_lock); |
| /* |
| * We cannot be left wanting - that would mean some runtime |
| * leaked out of the system. |
| */ |
| BUG_ON(want); |
| balanced: |
| /* |
| * Disable all the borrow logic by pretending we have inf |
| * runtime - in which case borrowing doesn't make sense. |
| */ |
| rt_rq->rt_runtime = RUNTIME_INF; |
| rt_rq->rt_throttled = 0; |
| raw_spin_unlock(&rt_rq->rt_runtime_lock); |
| raw_spin_unlock(&rt_b->rt_runtime_lock); |
| } |
| } |
| |
| static void __enable_runtime(struct rq *rq) |
| { |
| rt_rq_iter_t iter; |
| struct rt_rq *rt_rq; |
| |
| if (unlikely(!scheduler_running)) |
| return; |
| |
| /* |
| * Reset each runqueue's bandwidth settings |
| */ |
| for_each_rt_rq(rt_rq, iter, rq) { |
| struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq); |
| |
| raw_spin_lock(&rt_b->rt_runtime_lock); |
| raw_spin_lock(&rt_rq->rt_runtime_lock); |
| rt_rq->rt_runtime = rt_b->rt_runtime; |
| rt_rq->rt_time = 0; |
| rt_rq->rt_throttled = 0; |
| raw_spin_unlock(&rt_rq->rt_runtime_lock); |
| raw_spin_unlock(&rt_b->rt_runtime_lock); |
| } |
| } |
| |
| static int balance_runtime(struct rt_rq *rt_rq) |
| { |
| int more = 0; |
| |
| if (!sched_feat(RT_RUNTIME_SHARE)) |
| return more; |
| |
| if (rt_rq->rt_time > rt_rq->rt_runtime) { |
| raw_spin_unlock(&rt_rq->rt_runtime_lock); |
| more = do_balance_runtime(rt_rq); |
| raw_spin_lock(&rt_rq->rt_runtime_lock); |
| } |
| |
| return more; |
| } |
| #else /* !CONFIG_SMP */ |
| static inline int balance_runtime(struct rt_rq *rt_rq) |
| { |
| return 0; |
| } |
| #endif /* CONFIG_SMP */ |
| |
| static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun) |
| { |
| int i, idle = 1, throttled = 0; |
| const struct cpumask *span; |
| |
| span = sched_rt_period_mask(); |
| #ifdef CONFIG_RT_GROUP_SCHED |
| /* |
| * FIXME: isolated CPUs should really leave the root task group, |
| * whether they are isolcpus or were isolated via cpusets, lest |
| * the timer run on a CPU which does not service all runqueues, |
| * potentially leaving other CPUs indefinitely throttled. If |
| * isolation is really required, the user will turn the throttle |
| * off to kill the perturbations it causes anyway. Meanwhile, |
| * this maintains functionality for boot and/or troubleshooting. |
| */ |
| if (rt_b == &root_task_group.rt_bandwidth) |
| span = cpu_online_mask; |
| #endif |
| for_each_cpu(i, span) { |
| int enqueue = 0; |
| struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i); |
| struct rq *rq = rq_of_rt_rq(rt_rq); |
| |
| raw_spin_lock(&rq->lock); |
| if (rt_rq->rt_time) { |
| u64 runtime; |
| |
| raw_spin_lock(&rt_rq->rt_runtime_lock); |
| if (rt_rq->rt_throttled) |
| balance_runtime(rt_rq); |
| runtime = rt_rq->rt_runtime; |
| rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime); |
| if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) { |
| rt_rq->rt_throttled = 0; |
| enqueue = 1; |
| |
| /* |
| * Force a clock update if the CPU was idle, |
| * lest wakeup -> unthrottle time accumulate. |
| */ |
| if (rt_rq->rt_nr_running && rq->curr == rq->idle) |
| rq->skip_clock_update = -1; |
| } |
| if (rt_rq->rt_time || rt_rq->rt_nr_running) |
| idle = 0; |
| raw_spin_unlock(&rt_rq->rt_runtime_lock); |
| } else if (rt_rq->rt_nr_running) { |
| idle = 0; |
| if (!rt_rq_throttled(rt_rq)) |
| enqueue = 1; |
| } |
| if (rt_rq->rt_throttled) |
| throttled = 1; |
| |
| if (enqueue) |
| sched_rt_rq_enqueue(rt_rq); |
| raw_spin_unlock(&rq->lock); |
| } |
| |
| if (!throttled && (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)) |
| return 1; |
| |
| return idle; |
| } |
| |
| static inline int rt_se_prio(struct sched_rt_entity *rt_se) |
| { |
| #ifdef CONFIG_RT_GROUP_SCHED |
| struct rt_rq *rt_rq = group_rt_rq(rt_se); |
| |
| if (rt_rq) |
| return rt_rq->highest_prio.curr; |
| #endif |
| |
| return rt_task_of(rt_se)->prio; |
| } |
| |
| static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq) |
| { |
| u64 runtime = sched_rt_runtime(rt_rq); |
| |
| if (rt_rq->rt_throttled) |
| return rt_rq_throttled(rt_rq); |
| |
| if (runtime >= sched_rt_period(rt_rq)) |
| return 0; |
| |
| balance_runtime(rt_rq); |
| runtime = sched_rt_runtime(rt_rq); |
| if (runtime == RUNTIME_INF) |
| return 0; |
| |
| if (rt_rq->rt_time > runtime) { |
| struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq); |
| |
| /* |
| * Don't actually throttle groups that have no runtime assigned |
| * but accrue some time due to boosting. |
| */ |
| if (likely(rt_b->rt_runtime)) { |
| static bool once = false; |
| |
| rt_rq->rt_throttled = 1; |
| |
| if (!once) { |
| once = true; |
| printk_sched("sched: RT throttling activated\n"); |
| } |
| } else { |
| /* |
| * In case we did anyway, make it go away, |
| * replenishment is a joke, since it will replenish us |
| * with exactly 0 ns. |
| */ |
| rt_rq->rt_time = 0; |
| } |
| |
| if (rt_rq_throttled(rt_rq)) { |
| sched_rt_rq_dequeue(rt_rq); |
| return 1; |
| } |
| } |
| |
| return 0; |
| } |
| |
| /* |
| * Update the current task's runtime statistics. Skip current tasks that |
| * are not in our scheduling class. |
| */ |
| 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 (curr->sched_class != &rt_sched_class) |
| return; |
| |
| delta_exec = rq_clock_task(rq) - curr->se.exec_start; |
| if (unlikely((s64)delta_exec <= 0)) |
| return; |
| |
| schedstat_set(curr->se.statistics.exec_max, |
| max(curr->se.statistics.exec_max, delta_exec)); |
| |
| curr->se.sum_exec_runtime += delta_exec; |
| account_group_exec_runtime(curr, delta_exec); |
| |
| curr->se.exec_start = rq_clock_task(rq); |
| cpuacct_charge(curr, delta_exec); |
| |
| sched_rt_avg_update(rq, delta_exec); |
| |
| if (!rt_bandwidth_enabled()) |
| return; |
| |
| for_each_sched_rt_entity(rt_se) { |
| rt_rq = rt_rq_of_se(rt_se); |
| |
| if (sched_rt_runtime(rt_rq) != RUNTIME_INF) { |
| raw_spin_lock(&rt_rq->rt_runtime_lock); |
| rt_rq->rt_time += delta_exec; |
| if (sched_rt_runtime_exceeded(rt_rq)) |
| resched_task(curr); |
| raw_spin_unlock(&rt_rq->rt_runtime_lock); |
| } |
| } |
| } |
| |
| static void |
| dequeue_top_rt_rq(struct rt_rq *rt_rq) |
| { |
| struct rq *rq = rq_of_rt_rq(rt_rq); |
| |
| BUG_ON(&rq->rt != rt_rq); |
| |
| if (!rt_rq->rt_queued) |
| return; |
| |
| BUG_ON(!rq->nr_running); |
| |
| sub_nr_running(rq, rt_rq->rt_nr_running); |
| rt_rq->rt_queued = 0; |
| } |
| |
| static void |
| enqueue_top_rt_rq(struct rt_rq *rt_rq) |
| { |
| struct rq *rq = rq_of_rt_rq(rt_rq); |
| |
| BUG_ON(&rq->rt != rt_rq); |
| |
| if (rt_rq->rt_queued) |
| return; |
| if (rt_rq_throttled(rt_rq) || !rt_rq->rt_nr_running) |
| return; |
| |
| add_nr_running(rq, rt_rq->rt_nr_running); |
| rt_rq->rt_queued = 1; |
| } |
| |
| #if defined CONFIG_SMP |
| |
| static void |
| inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) |
| { |
| struct rq *rq = rq_of_rt_rq(rt_rq); |
| |
| #ifdef CONFIG_RT_GROUP_SCHED |
| /* |
| * Change rq's cpupri only if rt_rq is the top queue. |
| */ |
| if (&rq->rt != rt_rq) |
| return; |
| #endif |
| if (rq->online && prio < prev_prio) |
| cpupri_set(&rq->rd->cpupri, rq->cpu, prio); |
| } |
| |
| static void |
| dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) |
| { |
| struct rq *rq = rq_of_rt_rq(rt_rq); |
| |
| #ifdef CONFIG_RT_GROUP_SCHED |
| /* |
| * Change rq's cpupri only if rt_rq is the top queue. |
| */ |
| if (&rq->rt != rt_rq) |
| return; |
| #endif |
| if (rq->online && rt_rq->highest_prio.curr != prev_prio) |
| cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr); |
| } |
| |
| #else /* CONFIG_SMP */ |
| |
| static inline |
| void inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {} |
| static inline |
| void dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio) {} |
| |
| #endif /* CONFIG_SMP */ |
| |
| #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED |
| static void |
| inc_rt_prio(struct rt_rq *rt_rq, int prio) |
| { |
| int prev_prio = rt_rq->highest_prio.curr; |
| |
| if (prio < prev_prio) |
| rt_rq->highest_prio.curr = prio; |
| |
| inc_rt_prio_smp(rt_rq, prio, prev_prio); |
| } |
| |
| static void |
| dec_rt_prio(struct rt_rq *rt_rq, int prio) |
| { |
| int prev_prio = rt_rq->highest_prio.curr; |
| |
| if (rt_rq->rt_nr_running) { |
| |
| WARN_ON(prio < prev_prio); |
| |
| /* |
| * This may have been our highest task, and therefore |
| * we may have some recomputation to do |
| */ |
| if (prio == prev_prio) { |
| struct rt_prio_array *array = &rt_rq->active; |
| |
| rt_rq->highest_prio.curr = |
| sched_find_first_bit(array->bitmap); |
| } |
| |
| } else |
| rt_rq->highest_prio.curr = MAX_RT_PRIO; |
| |
| dec_rt_prio_smp(rt_rq, prio, prev_prio); |
| } |
| |
| #else |
| |
| static inline void inc_rt_prio(struct rt_rq *rt_rq, int prio) {} |
| static inline void dec_rt_prio(struct rt_rq *rt_rq, int prio) {} |
| |
| #endif /* CONFIG_SMP || CONFIG_RT_GROUP_SCHED */ |
| |
| #ifdef CONFIG_RT_GROUP_SCHED |
| |
| static void |
| inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) |
| { |
| if (rt_se_boosted(rt_se)) |
| rt_rq->rt_nr_boosted++; |
| |
| if (rt_rq->tg) |
| start_rt_bandwidth(&rt_rq->tg->rt_bandwidth); |
| } |
| |
| static void |
| dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) |
| { |
| if (rt_se_boosted(rt_se)) |
| rt_rq->rt_nr_boosted--; |
| |
| WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted); |
| } |
| |
| #else /* CONFIG_RT_GROUP_SCHED */ |
| |
| static void |
| inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) |
| { |
| start_rt_bandwidth(&def_rt_bandwidth); |
| } |
| |
| static inline |
| void dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) {} |
| |
| #endif /* CONFIG_RT_GROUP_SCHED */ |
| |
| static inline |
| unsigned int rt_se_nr_running(struct sched_rt_entity *rt_se) |
| { |
| struct rt_rq *group_rq = group_rt_rq(rt_se); |
| |
| if (group_rq) |
| return group_rq->rt_nr_running; |
| else |
| return 1; |
| } |
| |
| static inline |
| void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) |
| { |
| int prio = rt_se_prio(rt_se); |
| |
| WARN_ON(!rt_prio(prio)); |
| rt_rq->rt_nr_running += rt_se_nr_running(rt_se); |
| |
| inc_rt_prio(rt_rq, prio); |
| inc_rt_migration(rt_se, rt_rq); |
| inc_rt_group(rt_se, rt_rq); |
| } |
| |
| static inline |
| void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq) |
| { |
| WARN_ON(!rt_prio(rt_se_prio(rt_se))); |
| WARN_ON(!rt_rq->rt_nr_running); |
| rt_rq->rt_nr_running -= rt_se_nr_running(rt_se); |
| |
| dec_rt_prio(rt_rq, rt_se_prio(rt_se)); |
| dec_rt_migration(rt_se, rt_rq); |
| dec_rt_group(rt_se, rt_rq); |
| } |
| |
| static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head) |
| { |
| 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); |
| struct list_head *queue = array->queue + rt_se_prio(rt_se); |
| |
| /* |
| * Don't enqueue the group if its throttled, or when empty. |
| * The latter is a consequence of the former when a child group |
| * get throttled and the current group doesn't have any other |
| * active members. |
| */ |
| if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running)) |
| return; |
| |
| if (head) |
| list_add(&rt_se->run_list, queue); |
| else |
| list_add_tail(&rt_se->run_list, queue); |
| __set_bit(rt_se_prio(rt_se), array->bitmap); |
| |
| 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. |
| */ |
| static void dequeue_rt_stack(struct sched_rt_entity *rt_se) |
| { |
| struct sched_rt_entity *back = NULL; |
| |
| for_each_sched_rt_entity(rt_se) { |
| rt_se->back = back; |
| back = rt_se; |
| } |
| |
| dequeue_top_rt_rq(rt_rq_of_se(back)); |
| |
| for (rt_se = back; rt_se; rt_se = rt_se->back) { |
| if (on_rt_rq(rt_se)) |
| __dequeue_rt_entity(rt_se); |
| } |
| } |
| |
| static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head) |
| { |
| struct rq *rq = rq_of_rt_se(rt_se); |
| |
| dequeue_rt_stack(rt_se); |
| for_each_sched_rt_entity(rt_se) |
| __enqueue_rt_entity(rt_se, head); |
| enqueue_top_rt_rq(&rq->rt); |
| } |
| |
| static void dequeue_rt_entity(struct sched_rt_entity *rt_se) |
| { |
| struct rq *rq = rq_of_rt_se(rt_se); |
| |
| dequeue_rt_stack(rt_se); |
| |
| for_each_sched_rt_entity(rt_se) { |
| struct rt_rq *rt_rq = group_rt_rq(rt_se); |
| |
| if (rt_rq && rt_rq->rt_nr_running) |
| __enqueue_rt_entity(rt_se, false); |
| } |
| enqueue_top_rt_rq(&rq->rt); |
| } |
| |
| /* |
| * Adding/removing a task to/from a priority array: |
| */ |
| static void |
| enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags) |
| { |
| struct sched_rt_entity *rt_se = &p->rt; |
| |
| if (flags & ENQUEUE_WAKEUP) |
| rt_se->timeout = 0; |
| |
| enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD); |
| |
| if (!task_current(rq, p) && p->nr_cpus_allowed > 1) |
| enqueue_pushable_task(rq, p); |
| } |
| |
| static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags) |
| { |
| struct sched_rt_entity *rt_se = &p->rt; |
| |
| update_curr_rt(rq); |
| dequeue_rt_entity(rt_se); |
| |
| dequeue_pushable_task(rq, p); |
| } |
| |
| /* |
| * Put task to the head or 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, int head) |
| { |
| if (on_rt_rq(rt_se)) { |
| struct rt_prio_array *array = &rt_rq->active; |
| struct list_head *queue = array->queue + rt_se_prio(rt_se); |
| |
| if (head) |
| list_move(&rt_se->run_list, queue); |
| else |
| list_move_tail(&rt_se->run_list, queue); |
| } |
| } |
| |
| static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head) |
| { |
| struct sched_rt_entity *rt_se = &p->rt; |
| struct rt_rq *rt_rq; |
| |
| for_each_sched_rt_entity(rt_se) { |
| rt_rq = rt_rq_of_se(rt_se); |
| requeue_rt_entity(rt_rq, rt_se, head); |
| } |
| } |
| |
| static void yield_task_rt(struct rq *rq) |
| { |
| requeue_task_rt(rq, rq->curr, 0); |
| } |
| |
| #ifdef CONFIG_SMP |
| static int find_lowest_rq(struct task_struct *task); |
| |
| static int |
| select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags) |
| { |
| struct task_struct *curr; |
| struct rq *rq; |
| |
| if (p->nr_cpus_allowed == 1) |
| goto out; |
| |
| /* For anything but wake ups, just return the task_cpu */ |
| if (sd_flag != SD_BALANCE_WAKE && sd_flag != SD_BALANCE_FORK) |
| goto out; |
| |
| rq = cpu_rq(cpu); |
| |
| rcu_read_lock(); |
| curr = ACCESS_ONCE(rq->curr); /* unlocked access */ |
| |
| /* |
| * If the current task on @p's runqueue 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. If the woken |
| * task is a higher priority, then it will stay on this CPU |
| * and the lower prio task should be moved to another CPU. |
| * Even though this will probably make the lower prio task |
| * lose its cache, we do not want to bounce a higher task |
| * around just because it gave up its CPU, perhaps for a |
| * lock? |
| * |
| * For equal prio tasks, we just let the scheduler sort it out. |
| * |
| * Otherwise, just let it ride on the affined RQ and the |
| * post-schedule router will push the preempted task away |
| * |
| * This test is optimistic, if we get it wrong the load-balancer |
| * will have to sort it out. |
| */ |
| if (curr && unlikely(rt_task(curr)) && |
| (curr->nr_cpus_allowed < 2 || |
| curr->prio <= p->prio)) { |
| int target = find_lowest_rq(p); |
| |
| if (target != -1) |
| cpu = target; |
| } |
| rcu_read_unlock(); |
| |
| out: |
| return cpu; |
| } |
| |
| static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p) |
| { |
| if (rq->curr->nr_cpus_allowed == 1) |
| return; |
| |
| if (p->nr_cpus_allowed != 1 |
| && cpupri_find(&rq->rd->cpupri, p, NULL)) |
| return; |
| |
| if (!cpupri_find(&rq->rd->cpupri, rq->curr, NULL)) |
| return; |
| |
| /* |
| * There appears to be other cpus that can accept |
| * current and none to run 'p', so lets reschedule |
| * to try and push current away: |
| */ |
| requeue_task_rt(rq, p, 1); |
| resched_task(rq->curr); |
| } |
| |
| #endif /* CONFIG_SMP */ |
| |
| /* |
| * Preempt the current task with a newly woken task if needed: |
| */ |
| static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags) |
| { |
| if (p->prio < rq->curr->prio) { |
| resched_task(rq->curr); |
| return; |
| } |
| |
| #ifdef CONFIG_SMP |
| /* |
| * If: |
| * |
| * - the newly woken task is of equal priority to the current task |
| * - the newly woken task is non-migratable while current is migratable |
| * - current will be preempted on the next reschedule |
| * |
| * we should check to see if current can readily move to a different |
| * cpu. If so, we will reschedule to allow the push logic to try |
| * to move current somewhere else, making room for our non-migratable |
| * task. |
| */ |
| if (p->prio == rq->curr->prio && !test_tsk_need_resched(rq->curr)) |
| check_preempt_equal_prio(rq, p); |
| #endif |
| } |
| |
| static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq, |
| struct rt_rq *rt_rq) |
| { |
| struct rt_prio_array *array = &rt_rq->active; |
| struct sched_rt_entity *next = NULL; |
| struct list_head *queue; |
| int idx; |
| |
| 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); |
| |
| return next; |
| } |
| |
| 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 = &rq->rt; |
| |
| do { |
| rt_se = pick_next_rt_entity(rq, rt_rq); |
| BUG_ON(!rt_se); |
| rt_rq = group_rt_rq(rt_se); |
| } while (rt_rq); |
| |
| p = rt_task_of(rt_se); |
| p->se.exec_start = rq_clock_task(rq); |
| |
| return p; |
| } |
| |
| static struct task_struct * |
| pick_next_task_rt(struct rq *rq, struct task_struct *prev) |
| { |
| struct task_struct *p; |
| struct rt_rq *rt_rq = &rq->rt; |
| |
| if (need_pull_rt_task(rq, prev)) { |
| pull_rt_task(rq); |
| /* |
| * pull_rt_task() can drop (and re-acquire) rq->lock; this |
| * means a dl or stop task can slip in, in which case we need |
| * to re-start task selection. |
| */ |
| if (unlikely((rq->stop && rq->stop->on_rq) || |
| rq->dl.dl_nr_running)) |
| return RETRY_TASK; |
| } |
| |
| /* |
| * We may dequeue prev's rt_rq in put_prev_task(). |
| * So, we update time before rt_nr_running check. |
| */ |
| if (prev->sched_class == &rt_sched_class) |
| update_curr_rt(rq); |
| |
| if (!rt_rq->rt_queued) |
| return NULL; |
| |
| put_prev_task(rq, prev); |
| |
| p = _pick_next_task_rt(rq); |
| |
| /* The running task is never eligible for pushing */ |
| if (p) |
| dequeue_pushable_task(rq, p); |
| |
| set_post_schedule(rq); |
| |
| return p; |
| } |
| |
| static void put_prev_task_rt(struct rq *rq, struct task_struct *p) |
| { |
| update_curr_rt(rq); |
| |
| /* |
| * The previous task needs to be made eligible for pushing |
| * if it is still active |
| */ |
| if (on_rt_rq(&p->rt) && p->nr_cpus_allowed > 1) |
| enqueue_pushable_task(rq, p); |
| } |
| |
| #ifdef CONFIG_SMP |
| |
| /* Only try algorithms three times */ |
| #define RT_MAX_TRIES 3 |
| |
| static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu) |
| { |
| if (!task_running(rq, p) && |
| cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) |
| return 1; |
| return 0; |
| } |
| |
| /* |
| * Return the highest pushable rq's task, which is suitable to be executed |
| * on the cpu, NULL otherwise |
| */ |
| static struct task_struct *pick_highest_pushable_task(struct rq *rq, int cpu) |
| { |
| struct plist_head *head = &rq->rt.pushable_tasks; |
| struct task_struct *p; |
| |
| if (!has_pushable_tasks(rq)) |
| return NULL; |
| |
| plist_for_each_entry(p, head, pushable_tasks) { |
| if (pick_rt_task(rq, p, cpu)) |
| return p; |
| } |
| |
| return NULL; |
| } |
| |
| static DEFINE_PER_CPU(cpumask_var_t, local_cpu_mask); |
| |
| static int find_lowest_rq(struct task_struct *task) |
| { |
| struct sched_domain *sd; |
| struct cpumask *lowest_mask = __get_cpu_var(local_cpu_mask); |
| int this_cpu = smp_processor_id(); |
| int cpu = task_cpu(task); |
| |
| /* Make sure the mask is initialized first */ |
| if (unlikely(!lowest_mask)) |
| return -1; |
| |
| if (task->nr_cpus_allowed == 1) |
| return -1; /* No other targets possible */ |
| |
| if (!cpupri_find(&task_rq(task)->rd->cpupri, task, lowest_mask)) |
| return -1; /* No targets found */ |
| |
| /* |
| * 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 (cpumask_test_cpu(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 (!cpumask_test_cpu(this_cpu, lowest_mask)) |
| this_cpu = -1; /* Skip this_cpu opt if not among lowest */ |
| |
| rcu_read_lock(); |
| for_each_domain(cpu, sd) { |
| if (sd->flags & SD_WAKE_AFFINE) { |
| int best_cpu; |
| |
| /* |
| * "this_cpu" is cheaper to preempt than a |
| * remote processor. |
| */ |
| if (this_cpu != -1 && |
| cpumask_test_cpu(this_cpu, sched_domain_span(sd))) { |
| rcu_read_unlock(); |
| return this_cpu; |
| } |
| |
| best_cpu = cpumask_first_and(lowest_mask, |
| sched_domain_span(sd)); |
| if (best_cpu < nr_cpu_ids) { |
| rcu_read_unlock(); |
| return best_cpu; |
| } |
| } |
| } |
| rcu_read_unlock(); |
| |
| /* |
| * And finally, if there were no matches within the domains |
| * just give the caller *something* to work with from the compatible |
| * locations. |
| */ |
| if (this_cpu != -1) |
| return this_cpu; |
| |
| cpu = cpumask_any(lowest_mask); |
| if (cpu < nr_cpu_ids) |
| return cpu; |
| return -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 tries; |
| int cpu; |
| |
| for (tries = 0; tries < RT_MAX_TRIES; tries++) { |
| cpu = find_lowest_rq(task); |
| |
| if ((cpu == -1) || (cpu == rq->cpu)) |
| break; |
| |
| lowest_rq = cpu_rq(cpu); |
| |
| /* if the prio of this runqueue changed, try again */ |
| 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) != rq || |
| !cpumask_test_cpu(lowest_rq->cpu, |
| tsk_cpus_allowed(task)) || |
| task_running(rq, task) || |
| !task->on_rq)) { |
| |
| double_unlock_balance(rq, lowest_rq); |
| lowest_rq = NULL; |
| break; |
| } |
| } |
| |
| /* If this rq is still suitable use it. */ |
| if (lowest_rq->rt.highest_prio.curr > task->prio) |
| break; |
| |
| /* try again */ |
| double_unlock_balance(rq, lowest_rq); |
| lowest_rq = NULL; |
| } |
| |
| return lowest_rq; |
| } |
| |
| static struct task_struct *pick_next_pushable_task(struct rq *rq) |
| { |
| struct task_struct *p; |
| |
| if (!has_pushable_tasks(rq)) |
| return NULL; |
| |
| p = plist_first_entry(&rq->rt.pushable_tasks, |
| struct task_struct, pushable_tasks); |
| |
| BUG_ON(rq->cpu != task_cpu(p)); |
| BUG_ON(task_current(rq, p)); |
| BUG_ON(p->nr_cpus_allowed <= 1); |
| |
| BUG_ON(!p->on_rq); |
| BUG_ON(!rt_task(p)); |
| |
| return p; |
| } |
| |
| /* |
| * 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 *rq) |
| { |
| struct task_struct *next_task; |
| struct rq *lowest_rq; |
| int ret = 0; |
| |
| if (!rq->rt.overloaded) |
| return 0; |
| |
| next_task = pick_next_pushable_task(rq); |
| if (!next_task) |
| return 0; |
| |
| retry: |
| if (unlikely(next_task == rq->curr)) { |
| WARN_ON(1); |
| 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 < rq->curr->prio)) { |
| resched_task(rq->curr); |
| return 0; |
| } |
| |
| /* 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, rq); |
| if (!lowest_rq) { |
| struct task_struct *task; |
| /* |
| * find_lock_lowest_rq releases rq->lock |
| * so it is possible that next_task has migrated. |
| * |
| * We need to make sure that the task is still on the same |
| * run-queue and is also still the next task eligible for |
| * pushing. |
| */ |
| task = pick_next_pushable_task(rq); |
| if (task_cpu(next_task) == rq->cpu && task == next_task) { |
| /* |
| * The task hasn't migrated, and is still the next |
| * eligible task, but we failed to find a run-queue |
| * to push it to. Do not retry in this case, since |
| * other cpus will pull from us when ready. |
| */ |
| goto out; |
| } |
| |
| if (!task) |
| /* No more tasks, just exit */ |
| goto out; |
| |
| /* |
| * Something has shifted, try again. |
| */ |
| put_task_struct(next_task); |
| next_task = task; |
| goto retry; |
| } |
| |
| deactivate_task(rq, next_task, 0); |
| set_task_cpu(next_task, lowest_rq->cpu); |
| activate_task(lowest_rq, next_task, 0); |
| ret = 1; |
| |
| resched_task(lowest_rq->curr); |
| |
| double_unlock_balance(rq, lowest_rq); |
| |
| out: |
| put_task_struct(next_task); |
| |
| return ret; |
| } |
| |
| 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 int pull_rt_task(struct rq *this_rq) |
| { |
| int this_cpu = this_rq->cpu, ret = 0, cpu; |
| struct task_struct *p; |
| struct rq *src_rq; |
| |
| if (likely(!rt_overloaded(this_rq))) |
| return 0; |
| |
| /* |
| * Match the barrier from rt_set_overloaded; this guarantees that if we |
| * see overloaded we must also see the rto_mask bit. |
| */ |
| smp_rmb(); |
| |
| for_each_cpu(cpu, this_rq->rd->rto_mask) { |
| if (this_cpu == cpu) |
| continue; |
| |
| src_rq = cpu_rq(cpu); |
| |
| /* |
| * Don't bother taking the src_rq->lock if the next highest |
| * task is known to be lower-priority than our current task. |
| * This may look racy, but if this value is about to go |
| * logically higher, the src_rq will push this task away. |
| * And if its going logically lower, we do not care |
| */ |
| if (src_rq->rt.highest_prio.next >= |
| this_rq->rt.highest_prio.curr) |
| continue; |
| |
| /* |
| * We can potentially drop this_rq's lock in |
| * double_lock_balance, and another CPU could |
| * alter this_rq |
| */ |
| double_lock_balance(this_rq, src_rq); |
| |
| /* |
| * We can pull only a task, which is pushable |
| * on its rq, and no others. |
| */ |
| p = pick_highest_pushable_task(src_rq, this_cpu); |
| |
| /* |
| * Do we have an RT task that preempts |
| * the to-be-scheduled task? |
| */ |
| if (p && (p->prio < this_rq->rt.highest_prio.curr)) { |
| WARN_ON(p == src_rq->curr); |
| WARN_ON(!p->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 |
| */ |
| if (p->prio < src_rq->curr->prio) |
| goto skip; |
| |
| 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 likelihood |
| * but possible) |
| */ |
| } |
| skip: |
| double_unlock_balance(this_rq, src_rq); |
| } |
| |
| return ret; |
| } |
| |
| static void post_schedule_rt(struct rq *rq) |
| { |
| push_rt_tasks(rq); |
| } |
| |
| /* |
| * If we are not running and we are not going to reschedule soon, we should |
| * try to push tasks away now |
| */ |
| static void task_woken_rt(struct rq *rq, struct task_struct *p) |
| { |
| if (!task_running(rq, p) && |
| !test_tsk_need_resched(rq->curr) && |
| has_pushable_tasks(rq) && |
| p->nr_cpus_allowed > 1 && |
| (dl_task(rq->curr) || rt_task(rq->curr)) && |
| (rq->curr->nr_cpus_allowed < 2 || |
| rq->curr->prio <= p->prio)) |
| push_rt_tasks(rq); |
| } |
| |
| static void set_cpus_allowed_rt(struct task_struct *p, |
| const struct cpumask *new_mask) |
| { |
| struct rq *rq; |
| int weight; |
| |
| BUG_ON(!rt_task(p)); |
| |
| if (!p->on_rq) |
| return; |
| |
| weight = cpumask_weight(new_mask); |
| |
| /* |
| * Only update if the process changes its state from whether it |
| * can migrate or not. |
| */ |
| if ((p->nr_cpus_allowed > 1) == (weight > 1)) |
| return; |
| |
| rq = task_rq(p); |
| |
| /* |
| * The process used to be able to migrate OR it can now migrate |
| */ |
| if (weight <= 1) { |
| if (!task_current(rq, p)) |
| dequeue_pushable_task(rq, p); |
| BUG_ON(!rq->rt.rt_nr_migratory); |
| rq->rt.rt_nr_migratory--; |
| } else { |
| if (!task_current(rq, p)) |
| enqueue_pushable_task(rq, p); |
| rq->rt.rt_nr_migratory++; |
| } |
| |
| update_rt_migration(&rq->rt); |
| } |
| |
| /* Assumes rq->lock is held */ |
| static void rq_online_rt(struct rq *rq) |
| { |
| if (rq->rt.overloaded) |
| rt_set_overload(rq); |
| |
| __enable_runtime(rq); |
| |
| cpupri_set(&rq->rd->cpupri, rq->cpu, rq->rt.highest_prio.curr); |
| } |
| |
| /* Assumes rq->lock is held */ |
| static void rq_offline_rt(struct rq *rq) |
| { |
| if (rq->rt.overloaded) |
| rt_clear_overload(rq); |
| |
| __disable_runtime(rq); |
| |
| cpupri_set(&rq->rd->cpupri, rq->cpu, CPUPRI_INVALID); |
| } |
| |
| /* |
| * 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) |
| { |
| /* |
| * 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 (!p->on_rq || rq->rt.rt_nr_running) |
| return; |
| |
| if (pull_rt_task(rq)) |
| resched_task(rq->curr); |
| } |
| |
| void __init init_sched_rt_class(void) |
| { |
| unsigned int i; |
| |
| for_each_possible_cpu(i) { |
| zalloc_cpumask_var_node(&per_cpu(local_cpu_mask, i), |
| GFP_KERNEL, cpu_to_node(i)); |
| } |
| } |
| #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 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 (p->on_rq && rq->curr != p) { |
| #ifdef CONFIG_SMP |
| if (p->nr_cpus_allowed > 1 && rq->rt.overloaded && |
| /* Don't resched if we changed runqueues */ |
| push_rt_task(rq) && 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) |
| { |
| if (!p->on_rq) |
| return; |
| |
| if (rq->curr == p) { |
| #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. Note, the above pull_rt_task |
| * can release the rq lock and p could migrate. |
| * Only reschedule if p is still on the same runqueue. |
| */ |
| if (p->prio > rq->rt.highest_prio.curr && rq->curr == p) |
| 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 watchdog(struct rq *rq, struct task_struct *p) |
| { |
| unsigned long soft, hard; |
| |
| /* max may change after cur was read, this will be fixed next tick */ |
| soft = task_rlimit(p, RLIMIT_RTTIME); |
| hard = task_rlimit_max(p, RLIMIT_RTTIME); |
| |
| if (soft != RLIM_INFINITY) { |
| unsigned long next; |
| |
| if (p->rt.watchdog_stamp != jiffies) { |
| p->rt.timeout++; |
| p->rt.watchdog_stamp = jiffies; |
| } |
| |
| next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ); |
| if (p->rt.timeout > next) |
| p->cputime_expires.sched_exp = p->se.sum_exec_runtime; |
| } |
| } |
| |
| static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued) |
| { |
| struct sched_rt_entity *rt_se = &p->rt; |
| |
| update_curr_rt(rq); |
| |
| watchdog(rq, p); |
| |
| /* |
| * RR tasks need a special form of timeslice management. |
| * FIFO tasks have no timeslices. |
| */ |
| if (p->policy != SCHED_RR) |
| return; |
| |
| if (--p->rt.time_slice) |
| return; |
| |
| p->rt.time_slice = sched_rr_timeslice; |
| |
| /* |
| * Requeue to the end of queue if we (and all of our ancestors) are not |
| * the only element on the queue |
| */ |
| for_each_sched_rt_entity(rt_se) { |
| if (rt_se->run_list.prev != rt_se->run_list.next) { |
| requeue_task_rt(rq, p, 0); |
| set_tsk_need_resched(p); |
| return; |
| } |
| } |
| } |
| |
| static void set_curr_task_rt(struct rq *rq) |
| { |
| struct task_struct *p = rq->curr; |
| |
| p->se.exec_start = rq_clock_task(rq); |
| |
| /* The running task is never eligible for pushing */ |
| dequeue_pushable_task(rq, p); |
| } |
| |
| static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task) |
| { |
| /* |
| * Time slice is 0 for SCHED_FIFO tasks |
| */ |
| if (task->policy == SCHED_RR) |
| return sched_rr_timeslice; |
| else |
| return 0; |
| } |
| |
| const struct sched_class rt_sched_class = { |
| .next = &fair_sched_class, |
| .enqueue_task = enqueue_task_rt, |
| .dequeue_task = dequeue_task_rt, |
| .yield_task = yield_task_rt, |
| |
| .check_preempt_curr = check_preempt_curr_rt, |
| |
| .pick_next_task = pick_next_task_rt, |
| .put_prev_task = put_prev_task_rt, |
| |
| #ifdef CONFIG_SMP |
| .select_task_rq = select_task_rq_rt, |
| |
| .set_cpus_allowed = set_cpus_allowed_rt, |
| .rq_online = rq_online_rt, |
| .rq_offline = rq_offline_rt, |
| .post_schedule = post_schedule_rt, |
| .task_woken = task_woken_rt, |
| .switched_from = switched_from_rt, |
| #endif |
| |
| .set_curr_task = set_curr_task_rt, |
| .task_tick = task_tick_rt, |
| |
| .get_rr_interval = get_rr_interval_rt, |
| |
| .prio_changed = prio_changed_rt, |
| .switched_to = switched_to_rt, |
| }; |
| |
| #ifdef CONFIG_SCHED_DEBUG |
| extern void print_rt_rq(struct seq_file *m, int cpu, struct rt_rq *rt_rq); |
| |
| void print_rt_stats(struct seq_file *m, int cpu) |
| { |
| rt_rq_iter_t iter; |
| struct rt_rq *rt_rq; |
| |
| rcu_read_lock(); |
| for_each_rt_rq(rt_rq, iter, cpu_rq(cpu)) |
| print_rt_rq(m, cpu, rt_rq); |
| rcu_read_unlock(); |
| } |
| #endif /* CONFIG_SCHED_DEBUG */ |