diff options
Diffstat (limited to 'kernel/sched/fair.c')
| -rw-r--r-- | kernel/sched/fair.c | 2215 |
1 files changed, 1681 insertions, 534 deletions
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 3ebec186f982..d78467ec6ee1 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -334,7 +334,7 @@ static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq) * to a tree or when we reach the top of the tree */ if (cfs_rq->tg->parent && - cfs_rq->tg->parent->cfs_rq[cpu]->on_list) { + tg_cfs_rq(cfs_rq->tg->parent, cpu)->on_list) { /* * If parent is already on the list, we add the child * just before. Thanks to circular linked property of @@ -342,7 +342,7 @@ static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq) * of the list that starts by parent. */ list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list, - &(cfs_rq->tg->parent->cfs_rq[cpu]->leaf_cfs_rq_list)); + &(tg_cfs_rq(cfs_rq->tg->parent, cpu)->leaf_cfs_rq_list)); /* * The branch is now connected to its tree so we can * reset tmp_alone_branch to the beginning of the @@ -525,7 +525,7 @@ static int se_is_idle(struct sched_entity *se) #endif /* !CONFIG_FAIR_GROUP_SCHED */ static __always_inline -void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec); +bool account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec); /************************************************************** * Scheduling class tree data structure manipulation methods: @@ -1350,6 +1350,8 @@ void post_init_entity_util_avg(struct task_struct *p) sa->runnable_avg = sa->util_avg; } +static inline void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec); + static s64 update_se(struct rq *rq, struct sched_entity *se) { u64 now = rq_clock_task(rq); @@ -1372,6 +1374,7 @@ static s64 update_se(struct rq *rq, struct sched_entity *se) trace_sched_stat_runtime(running, delta_exec); account_group_exec_runtime(running, delta_exec); + account_mm_sched(rq, running, delta_exec); /* cgroup time is always accounted against the donor */ cgroup_account_cputime(donor, delta_exec); @@ -1393,6 +1396,581 @@ static s64 update_se(struct rq *rq, struct sched_entity *se) static void set_next_buddy(struct sched_entity *se); +#ifdef CONFIG_SCHED_CACHE + +/* + * XXX numbers come from a place the sun don't shine -- probably wants to be SD + * tunable or so. + */ +#define EPOCH_PERIOD (HZ / 100) /* 10 ms */ +#define EPOCH_LLC_AFFINITY_TIMEOUT 5 /* 50 ms */ +__read_mostly unsigned int llc_aggr_tolerance = 1; +__read_mostly unsigned int llc_epoch_period = EPOCH_PERIOD; +__read_mostly unsigned int llc_epoch_affinity_timeout = EPOCH_LLC_AFFINITY_TIMEOUT; +__read_mostly unsigned int llc_imb_pct = 20; +__read_mostly unsigned int llc_overaggr_pct = 50; + +static int llc_id(int cpu) +{ + if (cpu < 0) + return -1; + + return per_cpu(sd_llc_id, cpu); +} + +static inline int get_sched_cache_scale(int mul) +{ + unsigned int tol = READ_ONCE(llc_aggr_tolerance); + + if (!tol) + return 0; + + if (tol >= 100) + return INT_MAX; + + return (1 + (tol - 1) * mul); +} + +static bool exceed_llc_capacity(struct mm_struct *mm, int cpu) +{ +#ifdef CONFIG_NUMA_BALANCING + unsigned long llc, footprint; + struct sched_domain *sd; + int scale; + + guard(rcu)(); + + sd = rcu_dereference_sched_domain(cpu_rq(cpu)->sd); + if (!sd) + return true; + + if (static_branch_likely(&sched_numa_balancing)) { + /* + * TBD: RDT exclusive LLC ways reserved should be + * excluded. + */ + llc = sd->llc_bytes; + footprint = READ_ONCE(mm->sc_stat.footprint); + + /* + * Scale the LLC size by 256*llc_aggr_tolerance + * and compare it to the task's footprint. + * + * Suppose the L3 size is 32MB. If the + * llc_aggr_tolerance is 1: + * When the footprint is larger than 32MB, the + * process is regarded as exceeding the LLC + * capacity. If the llc_aggr_tolerance is 99: + * When the footprint is larger than 784GB, the + * process is regarded as exceeding the LLC + * capacity: + * 784GB = (1 + (99 - 1) * 256) * 32MB + * If the llc_aggr_tolerance is 100: + * ignore the footprint and do the aggregation + * anyway. + */ + scale = get_sched_cache_scale(256); + if (scale == INT_MAX) + return false; + + return ((llc * (u64)scale) < (footprint * PAGE_SIZE)); + } +#endif + return false; +} + +static bool invalid_llc_nr(struct mm_struct *mm, struct task_struct *p, + int cpu) +{ + int scale; + + if (get_nr_threads(p) <= 1) + return true; + + /* + * Scale the number of 'cores' in a LLC by llc_aggr_tolerance + * and compare it to the task's active threads. + */ + scale = get_sched_cache_scale(1); + if (scale == INT_MAX) + return false; + + return !fits_capacity((mm->sc_stat.nr_running_avg * cpu_smt_num_threads), + (scale * per_cpu(sd_llc_size, cpu))); +} + +static void account_llc_enqueue(struct rq *rq, struct task_struct *p) +{ + int pref_llc, pref_llc_queued; + struct sched_domain *sd; + + pref_llc = p->preferred_llc; + if (pref_llc < 0) + return; + + pref_llc_queued = (pref_llc == task_llc(p)); + rq->nr_llc_running++; + rq->nr_pref_llc_running += pref_llc_queued; + + /* + * Record whether p is enqueued on its preferred + * LLC, in order to pair with account_llc_dequeue() + * to maintain a consistent nr_pref_llc_running per + * runqueue. + * This is necessary because a race condition exists: + * after a task is enqueued on a runqueue, task_llc(p) + * may change due to CPU hotplug. Therefore, checking + * task_llc(p) to determine whether the task is being + * dequeued from its preferred LLC is unreliable and + * can cause inconsistent values - checking the + * p->pref_llc_queued in account_llc_dequeue() would + * be reliable. + */ + p->pref_llc_queued = pref_llc_queued; + + sd = rcu_dereference_all(rq->sd); + if (sd && (unsigned int)pref_llc < sd->llc_max) + sd->llc_counts[pref_llc]++; +} + +static void account_llc_dequeue(struct rq *rq, struct task_struct *p) +{ + struct sched_domain *sd; + int pref_llc; + + pref_llc = p->preferred_llc; + if (pref_llc < 0) + return; + + rq->nr_llc_running--; + if (p->pref_llc_queued) { + rq->nr_pref_llc_running--; + /* + * Update the status in case + * other logic might query + * this. + */ + p->pref_llc_queued = 0; + } + + sd = rcu_dereference_all(rq->sd); + if (sd && (unsigned int)pref_llc < sd->llc_max) { + /* + * There is a race condition between dequeue + * and CPU hotplug. After a task has been enqueued + * on CPUx, a CPU hotplug event occurs, and all online + * CPUs (including CPUx) rebuild their sched_domains + * and reset statistics to zero(including sd->llc_counts). + * This can cause temporary undercount and we have to + * check for such underflow in sd->llc_counts. + * + * This undercount is temporary and accurate accounting + * will resume once the rq has a chance to be idle. + */ + if (sd->llc_counts[pref_llc]) + sd->llc_counts[pref_llc]--; + } +} + +void mm_init_sched(struct mm_struct *mm, + struct sched_cache_time __percpu *_pcpu_sched) +{ + unsigned long epoch = 0; + int i; + + for_each_possible_cpu(i) { + struct sched_cache_time *pcpu_sched = per_cpu_ptr(_pcpu_sched, i); + struct rq *rq = cpu_rq(i); + + pcpu_sched->runtime = 0; + /* a slightly stale cpu epoch is acceptible */ + pcpu_sched->epoch = rq->cpu_epoch; + epoch = rq->cpu_epoch; + } + + raw_spin_lock_init(&mm->sc_stat.lock); + mm->sc_stat.epoch = epoch; + mm->sc_stat.cpu = -1; + mm->sc_stat.next_scan = jiffies; + mm->sc_stat.nr_running_avg = 0; + mm->sc_stat.footprint = 0; + /* + * The update to mm->sc_stat should not be reordered + * before initialization to mm's other fields, in case + * the readers may get invalid mm_sched_epoch, etc. + */ + smp_store_release(&mm->sc_stat.pcpu_sched, _pcpu_sched); +} + +/* because why would C be fully specified */ +static __always_inline void __shr_u64(u64 *val, unsigned int n) +{ + if (n >= 64) { + *val = 0; + return; + } + *val >>= n; +} + +static inline void __update_mm_sched(struct rq *rq, + struct sched_cache_time *pcpu_sched) +{ + lockdep_assert_held(&rq->cpu_epoch_lock); + + unsigned int period = max(READ_ONCE(llc_epoch_period), 1U); + unsigned long n, now = jiffies; + long delta = now - rq->cpu_epoch_next; + + if (delta > 0) { + n = (delta + period - 1) / period; + rq->cpu_epoch += n; + rq->cpu_epoch_next += n * period; + __shr_u64(&rq->cpu_runtime, n); + } + + n = rq->cpu_epoch - pcpu_sched->epoch; + if (n) { + pcpu_sched->epoch += n; + __shr_u64(&pcpu_sched->runtime, n); + } +} + +static unsigned long fraction_mm_sched(struct rq *rq, + struct sched_cache_time *pcpu_sched) +{ + guard(raw_spinlock_irqsave)(&rq->cpu_epoch_lock); + + __update_mm_sched(rq, pcpu_sched); + + /* + * Runtime is a geometric series (r=0.5) and as such will sum to twice + * the accumulation period, this means the multiplcation here should + * not overflow. + */ + return div64_u64(NICE_0_LOAD * pcpu_sched->runtime, rq->cpu_runtime + 1); +} + +static int get_pref_llc(struct task_struct *p, struct mm_struct *mm) +{ + int mm_sched_llc = -1, mm_sched_cpu; + + if (!mm) + return -1; + + mm_sched_cpu = READ_ONCE(mm->sc_stat.cpu); + if (mm_sched_cpu != -1) { + mm_sched_llc = llc_id(mm_sched_cpu); + +#ifdef CONFIG_NUMA_BALANCING + /* + * Don't assign preferred LLC if it + * conflicts with NUMA balancing. + * This can happen when sched_setnuma() gets + * called, however it is not much of an issue + * because we expect account_mm_sched() to get + * called fairly regularly -- at a higher rate + * than sched_setnuma() at least -- and thus the + * conflict only exists for a short period of time. + */ + if (static_branch_likely(&sched_numa_balancing) && + p->numa_preferred_nid >= 0 && + cpu_to_node(mm_sched_cpu) != p->numa_preferred_nid) + mm_sched_llc = -1; +#endif + } + + return mm_sched_llc; +} + +static unsigned int task_running_on_cpu(int cpu, struct task_struct *p); + +static inline +void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec) +{ + struct sched_cache_time *pcpu_sched; + struct mm_struct *mm = p->mm; + int mm_sched_llc = -1; + unsigned long epoch; + + if (!sched_cache_enabled()) + return; + + if (p->sched_class != &fair_sched_class) + return; + /* + * init_task, kthreads and user thread created + * by user_mode_thread() don't have mm. + */ + if (!mm || !mm->sc_stat.pcpu_sched) + return; + + pcpu_sched = per_cpu_ptr(mm->sc_stat.pcpu_sched, cpu_of(rq)); + + scoped_guard (raw_spinlock, &rq->cpu_epoch_lock) { + __update_mm_sched(rq, pcpu_sched); + pcpu_sched->runtime += delta_exec; + rq->cpu_runtime += delta_exec; + epoch = rq->cpu_epoch; + } + + /* + * If this process hasn't hit task_cache_work() for a while invalidate + * its preferred state. + */ + if ((long)(epoch - READ_ONCE(mm->sc_stat.epoch)) > llc_epoch_affinity_timeout || + invalid_llc_nr(mm, p, cpu_of(rq)) || + exceed_llc_capacity(mm, cpu_of(rq))) { + if (READ_ONCE(mm->sc_stat.cpu) != -1) + WRITE_ONCE(mm->sc_stat.cpu, -1); + } + + mm_sched_llc = get_pref_llc(p, mm); + + /* task not on rq accounted later in account_entity_enqueue() */ + if (task_running_on_cpu(rq->cpu, p) && + READ_ONCE(p->preferred_llc) != mm_sched_llc) { + account_llc_dequeue(rq, p); + WRITE_ONCE(p->preferred_llc, mm_sched_llc); + account_llc_enqueue(rq, p); + } +} + +static void task_tick_cache(struct rq *rq, struct task_struct *p) +{ + struct callback_head *work = &p->cache_work; + struct mm_struct *mm = p->mm; + unsigned long epoch; + + if (!sched_cache_enabled()) + return; + + if (!mm || p->flags & PF_KTHREAD || + !mm->sc_stat.pcpu_sched) + return; + + epoch = rq->cpu_epoch; + /* avoid moving backwards */ + if (time_after_eq(mm->sc_stat.epoch, epoch)) + return; + + guard(raw_spinlock)(&mm->sc_stat.lock); + + if (work->next == work) { + task_work_add(p, work, TWA_RESUME); + WRITE_ONCE(mm->sc_stat.epoch, epoch); + } +} + +static void get_scan_cpumasks(cpumask_var_t cpus, struct task_struct *p) +{ +#ifdef CONFIG_NUMA_BALANCING + int cpu, curr_cpu, nid, pref_nid; + + if (!static_branch_likely(&sched_numa_balancing)) + goto out; + + cpu = READ_ONCE(p->mm->sc_stat.cpu); + if (cpu != -1) + nid = cpu_to_node(cpu); + curr_cpu = task_cpu(p); + + /* + * Scanning in the preferred NUMA node is ideal. However, the NUMA + * preferred node is per-task rather than per-process. It is possible + * for different threads of the process to have distinct preferred + * nodes; consequently, the process-wide preferred LLC may bounce + * between different nodes. As a workaround, maintain the scan + * CPU mask to also cover the process's current preferred LLC and the + * current running node to mitigate the bouncing risk. + * TBD: numa_group should be considered during task aggregation. + */ + pref_nid = p->numa_preferred_nid; + /* honor the task's preferred node */ + if (pref_nid == NUMA_NO_NODE) + goto out; + + cpumask_or(cpus, cpus, cpumask_of_node(pref_nid)); + + /* honor the task's preferred LLC CPU */ + if (cpu != -1 && !cpumask_test_cpu(cpu, cpus) && nid != NUMA_NO_NODE) + cpumask_or(cpus, cpus, cpumask_of_node(nid)); + + /* make sure the task's current running node is included */ + if (!cpumask_test_cpu(curr_cpu, cpus)) + cpumask_or(cpus, cpus, cpumask_of_node(cpu_to_node(curr_cpu))); + + return; + +out: +#endif + cpumask_copy(cpus, cpu_online_mask); +} + +static inline void update_avg_scale(u64 *avg, u64 sample) +{ + int factor = per_cpu(sd_llc_size, raw_smp_processor_id()); + s64 diff = sample - *avg; + u32 divisor; + + /* + * Scale the divisor based on the number of CPUs contained + * in the LLC. This scaling ensures smaller LLC domains use + * a smaller divisor to achieve more precise sensitivity to + * changes in nr_running, while larger LLC domains are capped + * at a maximum divisor of 8 which is the default smoothing + * factor of EWMA in update_avg(). + */ + divisor = clamp_t(u32, (factor >> 2), 2, 8); + *avg += div64_s64(diff, divisor); +} + +static void task_cache_work(struct callback_head *work) +{ + int cpu, m_a_cpu = -1, nr_running = 0, curr_cpu; + unsigned long next_scan, now = jiffies; + struct task_struct *p = current, *cur; + unsigned long curr_m_a_occ = 0; + struct mm_struct *mm = p->mm; + unsigned long m_a_occ = 0; + cpumask_var_t cpus; + + WARN_ON_ONCE(work != &p->cache_work); + + work->next = work; + + if (p->flags & PF_EXITING) + return; + + next_scan = READ_ONCE(mm->sc_stat.next_scan); + if (time_before(now, next_scan)) + return; + + /* only 1 thread is allowed to scan */ + if (!try_cmpxchg(&mm->sc_stat.next_scan, &next_scan, + now + max_t(unsigned long, + READ_ONCE(llc_epoch_period), 1))) + return; + + curr_cpu = task_cpu(p); + if (invalid_llc_nr(mm, p, curr_cpu) || + exceed_llc_capacity(mm, curr_cpu)) { + if (READ_ONCE(mm->sc_stat.cpu) != -1) + WRITE_ONCE(mm->sc_stat.cpu, -1); + + return; + } + + if (!zalloc_cpumask_var(&cpus, GFP_KERNEL)) + return; + + scoped_guard (cpus_read_lock) { + guard(rcu)(); + + get_scan_cpumasks(cpus, p); + + for_each_cpu(cpu, cpus) { + /* XXX sched_cluster_active */ + struct sched_domain *sd = rcu_dereference_all(per_cpu(sd_llc, cpu)); + unsigned long occ, m_occ = 0, a_occ = 0; + int m_cpu = -1, i; + + if (!sd) + continue; + + for_each_cpu(i, sched_domain_span(sd)) { + occ = fraction_mm_sched(cpu_rq(i), + per_cpu_ptr(mm->sc_stat.pcpu_sched, i)); + a_occ += occ; + if (occ > m_occ) { + m_occ = occ; + m_cpu = i; + } + + cur = rcu_dereference_all(cpu_rq(i)->curr); + if (cur && !(cur->flags & (PF_EXITING | PF_KTHREAD)) && + cur->mm == mm) + nr_running++; + } + + /* + * Compare the accumulated occupancy of each LLC. The + * reason for using accumulated occupancy rather than average + * per CPU occupancy is that it works better in asymmetric LLC + * scenarios. + * For example, if there are 2 threads in a 4CPU LLC and 3 + * threads in an 8CPU LLC, it might be better to choose the one + * with 3 threads. However, this would not be the case if the + * occupancy is divided by the number of CPUs in an LLC (i.e., + * if average per CPU occupancy is used). + * Besides, NUMA balancing fault statistics behave similarly: + * the total number of faults per node is compared rather than + * the average number of faults per CPU. This strategy is also + * followed here. + */ + if (a_occ > m_a_occ) { + m_a_occ = a_occ; + m_a_cpu = m_cpu; + } + + if (llc_id(cpu) == llc_id(READ_ONCE(mm->sc_stat.cpu))) + curr_m_a_occ = a_occ; + + cpumask_andnot(cpus, cpus, sched_domain_span(sd)); + } + } + + if (m_a_occ > (2 * curr_m_a_occ)) { + /* + * Avoid switching sc_stat.cpu too fast. + * The reason to choose 2X is because: + * 1. It is better to keep the preferred LLC stable, + * rather than changing it frequently and cause migrations + * 2. 2X means the new preferred LLC has at least 1 more + * busy CPU than the old one(200% vs 100%, eg) + * 3. 2X is chosen based on test results, as it delivers + * the optimal performance gain so far. + */ + WRITE_ONCE(mm->sc_stat.cpu, m_a_cpu); + } + + update_avg_scale(&mm->sc_stat.nr_running_avg, nr_running); + free_cpumask_var(cpus); +} + +void init_sched_mm(struct task_struct *p) +{ + struct callback_head *work = &p->cache_work; + + init_task_work(work, task_cache_work); + work->next = work; + /* + * Reset new task's preference to avoid + * polluting account_llc_enqueue(). + */ + p->preferred_llc = -1; +} + +#else /* CONFIG_SCHED_CACHE */ + +static inline void account_mm_sched(struct rq *rq, struct task_struct *p, + s64 delta_exec) { } + +void init_sched_mm(struct task_struct *p) { } + +static void task_tick_cache(struct rq *rq, struct task_struct *p) { } + +static inline int get_pref_llc(struct task_struct *p, + struct mm_struct *mm) +{ + return -1; +} + +static void account_llc_enqueue(struct rq *rq, struct task_struct *p) {} + +static void account_llc_dequeue(struct rq *rq, struct task_struct *p) {} + +#endif /* CONFIG_SCHED_CACHE */ + /* * Used by other classes to account runtime. */ @@ -1578,13 +2156,9 @@ update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se) se->exec_start = rq_clock_task(rq_of(cfs_rq)); } -/************************************************** - * Scheduling class queueing methods: - */ - +/* Check sched_smt_active before calling this to avoid overheads in fastpaths */ static inline bool is_core_idle(int cpu) { -#ifdef CONFIG_SCHED_SMT int sibling; for_each_cpu(sibling, cpu_smt_mask(cpu)) { @@ -1594,7 +2168,6 @@ static inline bool is_core_idle(int cpu) if (!idle_cpu(sibling)) return false; } -#endif return true; } @@ -2277,12 +2850,11 @@ numa_type numa_classify(unsigned int imbalance_pct, return node_fully_busy; } -#ifdef CONFIG_SCHED_SMT /* Forward declarations of select_idle_sibling helpers */ static inline bool test_idle_cores(int cpu); static inline int numa_idle_core(int idle_core, int cpu) { - if (!static_branch_likely(&sched_smt_present) || + if (!sched_smt_active() || idle_core >= 0 || !test_idle_cores(cpu)) return idle_core; @@ -2295,12 +2867,6 @@ static inline int numa_idle_core(int idle_core, int cpu) return idle_core; } -#else /* !CONFIG_SCHED_SMT: */ -static inline int numa_idle_core(int idle_core, int cpu) -{ - return idle_core; -} -#endif /* !CONFIG_SCHED_SMT */ /* * Gather all necessary information to make NUMA balancing placement @@ -3079,6 +3645,7 @@ static void task_numa_placement(struct task_struct *p) unsigned long total_faults; u64 runtime, period; spinlock_t *group_lock = NULL; + long __maybe_unused new_fp; struct numa_group *ng; /* @@ -3153,6 +3720,31 @@ static void task_numa_placement(struct task_struct *p) ng->total_faults += diff; group_faults += ng->faults[mem_idx]; } +#ifdef CONFIG_SCHED_CACHE + /* + * Per task p->numa_faults[mem_idx] converges, + * so the accumulation of each task's faults + * converges too - Given the number of threads, + * it cannot overflow an unsigned long. + * Racy with concurrent updates from other threads + * sharing this mm. Acceptable since footprint is a + * heuristic and occasional lost updates are tolerable. + * + * If a task exits, its corresponding footprint must + * be subtracted from the mm->sc_stat.footprint, otherwise + * the mm->sc_stat.footprint will not converge: + * the exiting thread's footprint remains unchanged/undecayed + * in mm->sc_stat.footprint. See exit_mm(). + * + * Lost updates and unsynchronized subtraction + * in exit_mm() can cause footprint + diff to + * go negative. Clamp to zero to prevent the + * unsigned footprint from wrapping. + */ + new_fp = (long)READ_ONCE(p->mm->sc_stat.footprint) + diff; + WRITE_ONCE(p->mm->sc_stat.footprint, + max(new_fp, 0L)); +#endif } if (!ng) { @@ -3877,9 +4469,11 @@ account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se) { update_load_add(&cfs_rq->load, se->load.weight); if (entity_is_task(se)) { + struct task_struct *p = task_of(se); struct rq *rq = rq_of(cfs_rq); - account_numa_enqueue(rq, task_of(se)); + account_numa_enqueue(rq, p); + account_llc_enqueue(rq, p); list_add(&se->group_node, &rq->cfs_tasks); } cfs_rq->nr_queued++; @@ -3890,7 +4484,11 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se) { update_load_sub(&cfs_rq->load, se->load.weight); if (entity_is_task(se)) { - account_numa_dequeue(rq_of(cfs_rq), task_of(se)); + struct task_struct *p = task_of(se); + struct rq *rq = rq_of(cfs_rq); + + account_numa_dequeue(rq, p); + account_llc_dequeue(rq, p); list_del_init(&se->group_node); } cfs_rq->nr_queued--; @@ -4393,7 +4991,7 @@ static inline void update_tg_load_avg(struct cfs_rq *cfs_rq) * For migration heavy workloads, access to tg->load_avg can be * unbound. Limit the update rate to at most once per ms. */ - now = sched_clock_cpu(cpu_of(rq_of(cfs_rq))); + now = rq_clock(rq_of(cfs_rq)); if (now - cfs_rq->last_update_tg_load_avg < NSEC_PER_MSEC) return; @@ -4416,7 +5014,7 @@ static inline void clear_tg_load_avg(struct cfs_rq *cfs_rq) if (cfs_rq->tg == &root_task_group) return; - now = sched_clock_cpu(cpu_of(rq_of(cfs_rq))); + now = rq_clock(rq_of(cfs_rq)); delta = 0 - cfs_rq->tg_load_avg_contrib; atomic_long_add(delta, &cfs_rq->tg->load_avg); cfs_rq->tg_load_avg_contrib = 0; @@ -4437,13 +5035,13 @@ static void __maybe_unused clear_tg_offline_cfs_rqs(struct rq *rq) */ rq_clock_start_loop_update(rq); - rcu_read_lock(); + guard(rcu)(); + list_for_each_entry_rcu(tg, &task_groups, list) { - struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)]; + struct cfs_rq *cfs_rq = tg_cfs_rq(tg, cpu_of(rq)); clear_tg_load_avg(cfs_rq); } - rcu_read_unlock(); rq_clock_stop_loop_update(rq); } @@ -4959,13 +5557,86 @@ static void detach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *s trace_pelt_cfs_tp(cfs_rq); } +#define UTIL_EST_MARGIN (SCHED_CAPACITY_SCALE / 100) + +static inline void util_est_update(struct sched_entity *se) +{ + unsigned int ewma, dequeued, last_ewma_diff; + + if (!sched_feat(UTIL_EST)) + return; + + /* Get current estimate of utilization */ + ewma = READ_ONCE(se->avg.util_est); + + /* + * If the PELT values haven't changed since enqueue time, + * skip the util_est update. + */ + if (ewma & UTIL_AVG_UNCHANGED) + return; + + /* Get utilization at dequeue */ + dequeued = READ_ONCE(se->avg.util_avg); + + /* + * Reset EWMA on utilization increases, the moving average is used only + * to smooth utilization decreases. + */ + if (ewma <= dequeued) { + ewma = dequeued; + goto done; + } + + /* + * Skip update of task's estimated utilization when its members are + * already ~1% close to its last activation value. + */ + last_ewma_diff = ewma - dequeued; + if (last_ewma_diff < UTIL_EST_MARGIN) + goto done; + + /* + * To avoid underestimate of task utilization, skip updates of EWMA if + * we cannot grant that thread got all CPU time it wanted. + */ + if ((dequeued + UTIL_EST_MARGIN) < READ_ONCE(se->avg.runnable_avg)) + goto done; + + /* + * Update Task's estimated utilization + * + * When *p completes an activation we can consolidate another sample + * of the task size. This is done by using this value to update the + * Exponential Weighted Moving Average (EWMA): + * + * ewma(t) = w * task_util(p) + (1-w) * ewma(t-1) + * = w * task_util(p) + ewma(t-1) - w * ewma(t-1) + * = w * (task_util(p) - ewma(t-1)) + ewma(t-1) + * = w * ( -last_ewma_diff ) + ewma(t-1) + * = w * (-last_ewma_diff + ewma(t-1) / w) + * + * Where 'w' is the weight of new samples, which is configured to be + * 0.25, thus making w=1/4 ( >>= UTIL_EST_WEIGHT_SHIFT) + */ + ewma <<= UTIL_EST_WEIGHT_SHIFT; + ewma -= last_ewma_diff; + ewma >>= UTIL_EST_WEIGHT_SHIFT; +done: + ewma |= UTIL_AVG_UNCHANGED; + WRITE_ONCE(se->avg.util_est, ewma); + + trace_sched_util_est_se_tp(se); +} + /* * Optional action to be done while updating the load average */ -#define UPDATE_TG 0x1 -#define SKIP_AGE_LOAD 0x2 -#define DO_ATTACH 0x4 -#define DO_DETACH 0x8 +#define UPDATE_TG 0x01 +#define SKIP_AGE_LOAD 0x02 +#define DO_ATTACH 0x04 +#define DO_DETACH 0x08 +#define UPDATE_UTIL_EST 0x10 /* Update task and its cfs_rq load average */ static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) @@ -5008,6 +5679,9 @@ static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *s if (flags & UPDATE_TG) update_tg_load_avg(cfs_rq); } + + if (flags & UPDATE_UTIL_EST) + util_est_update(se); } /* @@ -5066,11 +5740,6 @@ static inline unsigned long task_util(struct task_struct *p) return READ_ONCE(p->se.avg.util_avg); } -static inline unsigned long task_runnable(struct task_struct *p) -{ - return READ_ONCE(p->se.avg.runnable_avg); -} - static inline unsigned long _task_util_est(struct task_struct *p) { return READ_ONCE(p->se.avg.util_est) & ~UTIL_AVG_UNCHANGED; @@ -5113,88 +5782,6 @@ static inline void util_est_dequeue(struct cfs_rq *cfs_rq, trace_sched_util_est_cfs_tp(cfs_rq); } -#define UTIL_EST_MARGIN (SCHED_CAPACITY_SCALE / 100) - -static inline void util_est_update(struct cfs_rq *cfs_rq, - struct task_struct *p, - bool task_sleep) -{ - unsigned int ewma, dequeued, last_ewma_diff; - - if (!sched_feat(UTIL_EST)) - return; - - /* - * Skip update of task's estimated utilization when the task has not - * yet completed an activation, e.g. being migrated. - */ - if (!task_sleep) - return; - - /* Get current estimate of utilization */ - ewma = READ_ONCE(p->se.avg.util_est); - - /* - * If the PELT values haven't changed since enqueue time, - * skip the util_est update. - */ - if (ewma & UTIL_AVG_UNCHANGED) - return; - - /* Get utilization at dequeue */ - dequeued = task_util(p); - - /* - * Reset EWMA on utilization increases, the moving average is used only - * to smooth utilization decreases. - */ - if (ewma <= dequeued) { - ewma = dequeued; - goto done; - } - - /* - * Skip update of task's estimated utilization when its members are - * already ~1% close to its last activation value. - */ - last_ewma_diff = ewma - dequeued; - if (last_ewma_diff < UTIL_EST_MARGIN) - goto done; - - /* - * To avoid underestimate of task utilization, skip updates of EWMA if - * we cannot grant that thread got all CPU time it wanted. - */ - if ((dequeued + UTIL_EST_MARGIN) < task_runnable(p)) - goto done; - - - /* - * Update Task's estimated utilization - * - * When *p completes an activation we can consolidate another sample - * of the task size. This is done by using this value to update the - * Exponential Weighted Moving Average (EWMA): - * - * ewma(t) = w * task_util(p) + (1-w) * ewma(t-1) - * = w * task_util(p) + ewma(t-1) - w * ewma(t-1) - * = w * (task_util(p) - ewma(t-1)) + ewma(t-1) - * = w * ( -last_ewma_diff ) + ewma(t-1) - * = w * (-last_ewma_diff + ewma(t-1) / w) - * - * Where 'w' is the weight of new samples, which is configured to be - * 0.25, thus making w=1/4 ( >>= UTIL_EST_WEIGHT_SHIFT) - */ - ewma <<= UTIL_EST_WEIGHT_SHIFT; - ewma -= last_ewma_diff; - ewma >>= UTIL_EST_WEIGHT_SHIFT; -done: - ewma |= UTIL_AVG_UNCHANGED; - WRITE_ONCE(p->se.avg.util_est, ewma); - - trace_sched_util_est_se_tp(&p->se); -} - static inline unsigned long get_actual_cpu_capacity(int cpu) { unsigned long capacity = arch_scale_cpu_capacity(cpu); @@ -5647,7 +6234,7 @@ static bool dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { bool sleep = flags & DEQUEUE_SLEEP; - int action = UPDATE_TG; + int action = 0; update_curr(cfs_rq); clear_buddies(cfs_rq, se); @@ -5667,15 +6254,23 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) if (sched_feat(DELAY_DEQUEUE) && delay && !entity_eligible(cfs_rq, se)) { - update_load_avg(cfs_rq, se, 0); + if (entity_is_task(se)) + action |= UPDATE_UTIL_EST; + update_load_avg(cfs_rq, se, action); update_entity_lag(cfs_rq, se); set_delayed(se); return false; } } - if (entity_is_task(se) && task_on_rq_migrating(task_of(se))) - action |= DO_DETACH; + action = UPDATE_TG; + if (entity_is_task(se)) { + if (task_on_rq_migrating(task_of(se))) + action |= DO_DETACH; + + if (sleep && !(flags & DEQUEUE_DELAYED)) + action |= UPDATE_UTIL_EST; + } /* * When dequeuing a sched_entity, we must: @@ -5793,8 +6388,6 @@ pick_next_entity(struct rq *rq, struct cfs_rq *cfs_rq, bool protect) return se; } -static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq); - static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev) { /* @@ -5804,9 +6397,6 @@ static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev) if (prev->on_rq) update_curr(cfs_rq); - /* throttle cfs_rqs exceeding runtime */ - check_cfs_rq_runtime(cfs_rq); - if (prev->on_rq) { update_stats_wait_start_fair(cfs_rq, prev); /* Put 'current' back into the tree. */ @@ -5941,44 +6531,32 @@ static int __assign_cfs_rq_runtime(struct cfs_bandwidth *cfs_b, return cfs_rq->runtime_remaining > 0; } -/* returns 0 on failure to allocate runtime */ -static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq) -{ - struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); - int ret; +static bool throttle_cfs_rq(struct cfs_rq *cfs_rq); - raw_spin_lock(&cfs_b->lock); - ret = __assign_cfs_rq_runtime(cfs_b, cfs_rq, sched_cfs_bandwidth_slice()); - raw_spin_unlock(&cfs_b->lock); - - return ret; -} - -static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) +static bool __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) { /* dock delta_exec before expiring quota (as it could span periods) */ cfs_rq->runtime_remaining -= delta_exec; if (likely(cfs_rq->runtime_remaining > 0)) - return; + return false; if (cfs_rq->throttled) - return; + return true; /* - * if we're unable to extend our runtime we resched so that the active - * hierarchy can be throttled + * throttle_cfs_rq() will try to extend the runtime first + * before throttling the hierarchy. */ - if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr)) - resched_curr(rq_of(cfs_rq)); + return throttle_cfs_rq(cfs_rq); } static __always_inline -void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) +bool account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) { if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled) - return; + return false; - __account_cfs_rq_runtime(cfs_rq, delta_exec); + return __account_cfs_rq_runtime(cfs_rq, delta_exec); } static inline int cfs_rq_throttled(struct cfs_rq *cfs_rq) @@ -5999,7 +6577,7 @@ static inline int throttled_hierarchy(struct cfs_rq *cfs_rq) static inline int lb_throttled_hierarchy(struct task_struct *p, int dst_cpu) { - return throttled_hierarchy(task_group(p)->cfs_rq[dst_cpu]); + return throttled_hierarchy(tg_cfs_rq(task_group(p), dst_cpu)); } static inline bool task_is_throttled(struct task_struct *p) @@ -6145,8 +6723,18 @@ static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags); static int tg_unthrottle_up(struct task_group *tg, void *data) { struct rq *rq = data; - struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)]; + struct cfs_rq *cfs_rq = tg_cfs_rq(tg, cpu_of(rq)); struct task_struct *p, *tmp; + LIST_HEAD(throttled_tasks); + + /* + * If cfs_rq->curr is set, the cfs_rq might not have caught up + * since the last clock update. Do it now before we begin + * queueing task onto it to save the need for unnecessarily + * unthrottle the hierarchy for this cfs_rq to be throttled + * right back again. + */ + update_curr(cfs_rq); if (--cfs_rq->throttle_count) return 0; @@ -6168,13 +6756,31 @@ static int tg_unthrottle_up(struct task_group *tg, void *data) cfs_rq->throttled_clock_self_time += delta; } + /* + * Move the tasks to a local list since an update_curr() during + * enqueue_task_fair() can throttle a higher cfs_rq, and it can + * see the "throttled_limbo_list" being non-empty in + * tg_throttle_down() if throttle_count turned 0 above. + */ + list_splice_init(&cfs_rq->throttled_limbo_list, &throttled_tasks); + /* Re-enqueue the tasks that have been throttled at this level. */ - list_for_each_entry_safe(p, tmp, &cfs_rq->throttled_limbo_list, throttle_node) { + list_for_each_entry_safe(p, tmp, &throttled_tasks, throttle_node) { + /* + * Back to being throttled! Break out and put the remaining + * tasks back onto the limbo_list to prevent running them + * unnecessarily. + */ + if (cfs_rq->throttle_count) + break; + list_del_init(&p->throttle_node); p->throttled = false; - enqueue_task_fair(rq_of(cfs_rq), p, ENQUEUE_WAKEUP); + enqueue_task_fair(rq, p, ENQUEUE_WAKEUP); } + list_splice(&throttled_tasks, &cfs_rq->throttled_limbo_list); + /* Add cfs_rq with load or one or more already running entities to the list */ if (!cfs_rq_is_decayed(cfs_rq)) list_add_leaf_cfs_rq(cfs_rq); @@ -6216,7 +6822,7 @@ static void record_throttle_clock(struct cfs_rq *cfs_rq) static int tg_throttle_down(struct task_group *tg, void *data) { struct rq *rq = data; - struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)]; + struct cfs_rq *cfs_rq = tg_cfs_rq(tg, cpu_of(rq)); if (cfs_rq->throttle_count++) return 0; @@ -6238,35 +6844,48 @@ static int tg_throttle_down(struct task_group *tg, void *data) static bool throttle_cfs_rq(struct cfs_rq *cfs_rq) { - struct rq *rq = rq_of(cfs_rq); struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); - int dequeue = 1; + struct sched_entity *curr = cfs_rq->curr; + struct rq *rq = rq_of(cfs_rq); + + scoped_guard(raw_spinlock, &cfs_b->lock) { + u64 target_runtime = 1; - raw_spin_lock(&cfs_b->lock); - /* This will start the period timer if necessary */ - if (__assign_cfs_rq_runtime(cfs_b, cfs_rq, 1)) { /* - * We have raced with bandwidth becoming available, and if we - * actually throttled the timer might not unthrottle us for an - * entire period. We additionally needed to make sure that any - * subsequent check_cfs_rq_runtime calls agree not to throttle - * us, as we may commit to do cfs put_prev+pick_next, so we ask - * for 1ns of runtime rather than just check cfs_b. + * If cfs_rq->curr is still runnable, we are here from an + * update_curr(). Request sysctl_sched_cfs_bandwidth_slice + * worth of bandwidth to continue running. + * + * If the curr is not runnable, just request enough bandwidth + * to be runnable next time the pick selects this cfs_rq. + */ + if (curr && curr->on_rq) + target_runtime = sched_cfs_bandwidth_slice(); + + /* + * Check if We have raced with bandwidth becoming available. If + * we actually throttled the timer might not unthrottle us for + * an entire period. We additionally needed to make sure that + * any subsequent check_cfs_rq_runtime calls agree not to + * throttle us, as we may commit to do cfs put_prev+pick_next, + * so we ask for 1ns of runtime rather than just check cfs_b. + * + * This will start the period timer if necessary. + */ + if (__assign_cfs_rq_runtime(cfs_b, cfs_rq, target_runtime)) + return false; + + /* + * No bandwidth available; Add ourselves on the list to be + * unthrottled later. */ - dequeue = 0; - } else { list_add_tail_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq); } - raw_spin_unlock(&cfs_b->lock); - - if (!dequeue) - return false; /* Throttle no longer required. */ /* freeze hierarchy runnable averages while throttled */ - rcu_read_lock(); - walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq); - rcu_read_unlock(); + scoped_guard(rcu) + walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq); /* * Note: distribution will already see us throttled via the @@ -6274,6 +6893,17 @@ static bool throttle_cfs_rq(struct cfs_rq *cfs_rq) */ cfs_rq->throttled = 1; WARN_ON_ONCE(cfs_rq->throttled_clock); + + /* + * If current hierarchy was throttled, add throttle work to the + * current donor. In case of proxy-execution, the execution + * context cannot exit to the userspace while holding a mutex + * and the rule of throttle deferral to only throttle the + * throttled context at exit to userspace is still preserved. + */ + if (curr && curr->on_rq) + task_throttle_setup_work(rq->donor); + return true; } @@ -6281,7 +6911,7 @@ void unthrottle_cfs_rq(struct cfs_rq *cfs_rq) { struct rq *rq = rq_of(cfs_rq); struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg); - struct sched_entity *se = cfs_rq->tg->se[cpu_of(rq)]; + struct sched_entity *se = cfs_rq_se(cfs_rq); /* * It's possible we are called with runtime_remaining < 0 due to things @@ -6291,21 +6921,25 @@ void unthrottle_cfs_rq(struct cfs_rq *cfs_rq) * We can't unthrottle this cfs_rq without any runtime remaining because * any enqueue in tg_unthrottle_up() will immediately trigger a throttle, * which is not supposed to happen on unthrottle path. + * + * Catch up on the remaining runtime since last clock update before + * checking runtime remaining. */ + update_curr(cfs_rq); if (cfs_rq->runtime_enabled && cfs_rq->runtime_remaining <= 0) return; cfs_rq->throttled = 0; - update_rq_clock(rq); + scoped_guard(raw_spinlock, &cfs_b->lock) { + list_del_rcu(&cfs_rq->throttled_list); + + if (!cfs_rq->throttled_clock) + break; - raw_spin_lock(&cfs_b->lock); - if (cfs_rq->throttled_clock) { cfs_b->throttled_time += rq_clock(rq) - cfs_rq->throttled_clock; cfs_rq->throttled_clock = 0; } - list_del_rcu(&cfs_rq->throttled_list); - raw_spin_unlock(&cfs_b->lock); /* update hierarchical throttle state */ walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq); @@ -6334,9 +6968,8 @@ static void __cfsb_csd_unthrottle(void *arg) { struct cfs_rq *cursor, *tmp; struct rq *rq = arg; - struct rq_flags rf; - rq_lock(rq, &rf); + guard(rq_lock)(rq); /* * Iterating over the list can trigger several call to @@ -6353,7 +6986,7 @@ static void __cfsb_csd_unthrottle(void *arg) * race with group being freed in the window between removing it * from the list and advancing to the next entry in the list. */ - rcu_read_lock(); + guard(rcu)(); list_for_each_entry_safe(cursor, tmp, &rq->cfsb_csd_list, throttled_csd_list) { @@ -6363,10 +6996,7 @@ static void __cfsb_csd_unthrottle(void *arg) unthrottle_cfs_rq(cursor); } - rcu_read_unlock(); - rq_clock_stop_loop_update(rq); - rq_unlock(rq, &rf); } static inline void __unthrottle_cfs_rq_async(struct cfs_rq *cfs_rq) @@ -6375,6 +7005,7 @@ static inline void __unthrottle_cfs_rq_async(struct cfs_rq *cfs_rq) bool first; if (rq == this_rq()) { + update_rq_clock(rq); unthrottle_cfs_rq(cfs_rq); return; } @@ -6402,15 +7033,14 @@ static void unthrottle_cfs_rq_async(struct cfs_rq *cfs_rq) static bool distribute_cfs_runtime(struct cfs_bandwidth *cfs_b) { + bool throttled = false, unthrottle_local = false; int this_cpu = smp_processor_id(); u64 runtime, remaining = 1; - bool throttled = false; - struct cfs_rq *cfs_rq, *tmp; - struct rq_flags rf; + struct cfs_rq *cfs_rq; struct rq *rq; - LIST_HEAD(local_unthrottle); - rcu_read_lock(); + guard(rcu)(); + list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq, throttled_list) { rq = rq_of(cfs_rq); @@ -6420,64 +7050,66 @@ static bool distribute_cfs_runtime(struct cfs_bandwidth *cfs_b) break; } - rq_lock_irqsave(rq, &rf); + guard(rq_lock_irqsave)(rq); + if (!cfs_rq_throttled(cfs_rq)) - goto next; + continue; /* Already queued for async unthrottle */ if (!list_empty(&cfs_rq->throttled_csd_list)) - goto next; + continue; + + if (cfs_rq->curr) { + update_rq_clock(rq); + update_curr(cfs_rq); + } /* By the above checks, this should never be true */ WARN_ON_ONCE(cfs_rq->runtime_remaining > 0); - raw_spin_lock(&cfs_b->lock); - runtime = -cfs_rq->runtime_remaining + 1; - if (runtime > cfs_b->runtime) - runtime = cfs_b->runtime; - cfs_b->runtime -= runtime; - remaining = cfs_b->runtime; - raw_spin_unlock(&cfs_b->lock); + scoped_guard(raw_spinlock, &cfs_b->lock) { + runtime = -cfs_rq->runtime_remaining + 1; + if (runtime > cfs_b->runtime) + runtime = cfs_b->runtime; + cfs_b->runtime -= runtime; + remaining = cfs_b->runtime; + } cfs_rq->runtime_remaining += runtime; - /* we check whether we're throttled above */ - if (cfs_rq->runtime_remaining > 0) { - if (cpu_of(rq) != this_cpu) { - unthrottle_cfs_rq_async(cfs_rq); - } else { - /* - * We currently only expect to be unthrottling - * a single cfs_rq locally. - */ - WARN_ON_ONCE(!list_empty(&local_unthrottle)); - list_add_tail(&cfs_rq->throttled_csd_list, - &local_unthrottle); - } - } else { + /* + * Ran out of bandwidth during distribution! + * Indicate throttled entities and break early. + */ + if (cfs_rq->runtime_remaining <= 0) { throttled = true; + break; } -next: - rq_unlock_irqrestore(rq, &rf); - } - - list_for_each_entry_safe(cfs_rq, tmp, &local_unthrottle, - throttled_csd_list) { - struct rq *rq = rq_of(cfs_rq); - - rq_lock_irqsave(rq, &rf); - - list_del_init(&cfs_rq->throttled_csd_list); - - if (cfs_rq_throttled(cfs_rq)) - unthrottle_cfs_rq(cfs_rq); + /* we check whether we're throttled above */ + if (cpu_of(rq) != this_cpu) { + unthrottle_cfs_rq_async(cfs_rq); + continue; + } - rq_unlock_irqrestore(rq, &rf); + /* + * Allow a parallel async unthrottle to unthrottle + * this cfs_rq too via __cfsb_csd_unthrottle(). + * If we are first, do it ourselves at the end and + * save on an IPI from remote CPUs. + */ + unthrottle_local = list_empty(&rq->cfsb_csd_list); + list_add_tail(&cfs_rq->throttled_csd_list, &rq->cfsb_csd_list); } - WARN_ON_ONCE(!list_empty(&local_unthrottle)); - rcu_read_unlock(); + if (unthrottle_local) { + /* + * Protect against an IPI that is also trying to flush + * the unthrottled cfs_rq(s) from this CPU's csd_list. + */ + scoped_guard(irqsave) + __cfsb_csd_unthrottle(cpu_rq(this_cpu)); + } return throttled; } @@ -6601,7 +7233,8 @@ static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq) if (slack_runtime <= 0) return; - raw_spin_lock(&cfs_b->lock); + guard(raw_spinlock)(&cfs_b->lock); + if (cfs_b->quota != RUNTIME_INF) { cfs_b->runtime += slack_runtime; @@ -6610,7 +7243,6 @@ static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq) !list_empty(&cfs_b->throttled_cfs_rq)) start_cfs_slack_bandwidth(cfs_b); } - raw_spin_unlock(&cfs_b->lock); /* even if it's not valid for return we don't want to try again */ cfs_rq->runtime_remaining -= slack_runtime; @@ -6633,25 +7265,21 @@ static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) */ static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b) { - u64 runtime = 0, slice = sched_cfs_bandwidth_slice(); - unsigned long flags; - /* confirm we're still not at a refresh boundary */ - raw_spin_lock_irqsave(&cfs_b->lock, flags); - cfs_b->slack_started = false; + scoped_guard(raw_spinlock_irqsave, &cfs_b->lock) { + u64 runtime = 0, slice = sched_cfs_bandwidth_slice(); - if (runtime_refresh_within(cfs_b, min_bandwidth_expiration)) { - raw_spin_unlock_irqrestore(&cfs_b->lock, flags); - return; - } + cfs_b->slack_started = false; - if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice) - runtime = cfs_b->runtime; + if (runtime_refresh_within(cfs_b, min_bandwidth_expiration)) + return; - raw_spin_unlock_irqrestore(&cfs_b->lock, flags); + if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice) + runtime = cfs_b->runtime; - if (!runtime) - return; + if (!runtime) + return; + } distribute_cfs_runtime(cfs_b); } @@ -6666,7 +7294,7 @@ static void check_enqueue_throttle(struct cfs_rq *cfs_rq) if (!cfs_bandwidth_used()) return; - /* an active group must be handled by the update_curr()->put() path */ + /* an active group must be handled by the update_curr() path */ if (!cfs_rq->runtime_enabled || cfs_rq->curr) return; @@ -6676,8 +7304,6 @@ static void check_enqueue_throttle(struct cfs_rq *cfs_rq) /* update runtime allocation */ account_cfs_rq_runtime(cfs_rq, 0); - if (cfs_rq->runtime_remaining <= 0) - throttle_cfs_rq(cfs_rq); } static void sync_throttle(struct task_group *tg, int cpu) @@ -6690,8 +7316,8 @@ static void sync_throttle(struct task_group *tg, int cpu) if (!tg->parent) return; - cfs_rq = tg->cfs_rq[cpu]; - pcfs_rq = tg->parent->cfs_rq[cpu]; + cfs_rq = tg_cfs_rq(tg, cpu); + pcfs_rq = tg_cfs_rq(tg->parent, cpu); cfs_rq->throttle_count = pcfs_rq->throttle_count; cfs_rq->throttled_clock_pelt = rq_clock_pelt(cpu_rq(cpu)); @@ -6707,25 +7333,6 @@ static void sync_throttle(struct task_group *tg, int cpu) cfs_rq->pelt_clock_throttled = 1; } -/* conditionally throttle active cfs_rq's from put_prev_entity() */ -static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq) -{ - if (!cfs_bandwidth_used()) - return false; - - if (likely(!cfs_rq->runtime_enabled || cfs_rq->runtime_remaining > 0)) - return false; - - /* - * it's possible for a throttled entity to be forced into a running - * state (e.g. set_curr_task), in this case we're finished. - */ - if (cfs_rq_throttled(cfs_rq)) - return true; - - return throttle_cfs_rq(cfs_rq); -} - static enum hrtimer_restart sched_cfs_slack_timer(struct hrtimer *timer) { struct cfs_bandwidth *cfs_b = @@ -6740,18 +7347,18 @@ static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer) { struct cfs_bandwidth *cfs_b = container_of(timer, struct cfs_bandwidth, period_timer); - unsigned long flags; int overrun; int idle = 0; int count = 0; - raw_spin_lock_irqsave(&cfs_b->lock, flags); + CLASS(raw_spinlock_irqsave, cfsb_guard)(&cfs_b->lock); + for (;;) { overrun = hrtimer_forward_now(timer, cfs_b->period); if (!overrun) break; - idle = do_sched_cfs_period_timer(cfs_b, overrun, flags); + idle = do_sched_cfs_period_timer(cfs_b, overrun, cfsb_guard.flags); if (++count > 3) { u64 new, old = ktime_to_ns(cfs_b->period); @@ -6784,11 +7391,13 @@ static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer) count = 0; } } - if (idle) + + if (idle) { cfs_b->period_active = 0; - raw_spin_unlock_irqrestore(&cfs_b->lock, flags); + return HRTIMER_NORESTART; + } - return idle ? HRTIMER_NORESTART : HRTIMER_RESTART; + return HRTIMER_RESTART; } void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b, struct cfs_bandwidth *parent) @@ -6855,14 +7464,12 @@ static void destroy_cfs_bandwidth(struct cfs_bandwidth *cfs_b) */ for_each_possible_cpu(i) { struct rq *rq = cpu_rq(i); - unsigned long flags; if (list_empty(&rq->cfsb_csd_list)) continue; - local_irq_save(flags); - __cfsb_csd_unthrottle(rq); - local_irq_restore(flags); + scoped_guard(irqsave) + __cfsb_csd_unthrottle(rq); } } @@ -6880,16 +7487,15 @@ static void __maybe_unused update_runtime_enabled(struct rq *rq) lockdep_assert_rq_held(rq); - rcu_read_lock(); + guard(rcu)(); + list_for_each_entry_rcu(tg, &task_groups, list) { struct cfs_bandwidth *cfs_b = &tg->cfs_bandwidth; - struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)]; + struct cfs_rq *cfs_rq = tg_cfs_rq(tg, cpu_of(rq)); - raw_spin_lock(&cfs_b->lock); - cfs_rq->runtime_enabled = cfs_b->quota != RUNTIME_INF; - raw_spin_unlock(&cfs_b->lock); + scoped_guard(raw_spinlock, &cfs_b->lock) + cfs_rq->runtime_enabled = cfs_b->quota != RUNTIME_INF; } - rcu_read_unlock(); } /* cpu offline callback */ @@ -6910,9 +7516,10 @@ static void __maybe_unused unthrottle_offline_cfs_rqs(struct rq *rq) */ rq_clock_start_loop_update(rq); - rcu_read_lock(); + guard(rcu)(); + list_for_each_entry_rcu(tg, &task_groups, list) { - struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)]; + struct cfs_rq *cfs_rq = tg_cfs_rq(tg, cpu_of(rq)); if (!cfs_rq->runtime_enabled) continue; @@ -6933,7 +7540,6 @@ static void __maybe_unused unthrottle_offline_cfs_rqs(struct rq *rq) cfs_rq->runtime_remaining = 1; unthrottle_cfs_rq(cfs_rq); } - rcu_read_unlock(); rq_clock_stop_loop_update(rq); } @@ -6980,8 +7586,7 @@ static void sched_fair_update_stop_tick(struct rq *rq, struct task_struct *p) #else /* !CONFIG_CFS_BANDWIDTH: */ -static void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) {} -static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq) { return false; } +static bool account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec) { return false; } static void check_enqueue_throttle(struct cfs_rq *cfs_rq) {} static inline void sync_throttle(struct task_group *tg, int cpu) {} static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq) {} @@ -7438,7 +8043,6 @@ static bool dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags) if (!p->se.sched_delayed) util_est_dequeue(&rq->cfs, p); - util_est_update(&rq->cfs, p, flags & DEQUEUE_SLEEP); if (dequeue_entities(rq, &p->se, flags) < 0) return false; @@ -7811,7 +8415,6 @@ static inline int __select_idle_cpu(int cpu, struct task_struct *p) return -1; } -#ifdef CONFIG_SCHED_SMT DEFINE_STATIC_KEY_FALSE(sched_smt_present); EXPORT_SYMBOL_GPL(sched_smt_present); @@ -7819,7 +8422,7 @@ static inline void set_idle_cores(int cpu, int val) { struct sched_domain_shared *sds; - sds = rcu_dereference_all(per_cpu(sd_llc_shared, cpu)); + sds = rcu_dereference_all(per_cpu(sd_balance_shared, cpu)); if (sds) WRITE_ONCE(sds->has_idle_cores, val); } @@ -7828,7 +8431,7 @@ static inline bool test_idle_cores(int cpu) { struct sched_domain_shared *sds; - sds = rcu_dereference_all(per_cpu(sd_llc_shared, cpu)); + sds = rcu_dereference_all(per_cpu(sd_balance_shared, cpu)); if (sds) return READ_ONCE(sds->has_idle_cores); @@ -7837,7 +8440,7 @@ static inline bool test_idle_cores(int cpu) /* * Scans the local SMT mask to see if the entire core is idle, and records this - * information in sd_llc_shared->has_idle_cores. + * information in sd_balance_shared->has_idle_cores. * * Since SMT siblings share all cache levels, inspecting this limited remote * state should be fairly cheap. @@ -7867,7 +8470,8 @@ unlock: /* * Scan the entire LLC domain for idle cores; this dynamically switches off if * there are no idle cores left in the system; tracked through - * sd_llc->shared->has_idle_cores and enabled through update_idle_core() above. + * sd_balance_shared->has_idle_cores and enabled through update_idle_core() + * above. */ static int select_idle_core(struct task_struct *p, int core, struct cpumask *cpus, int *idle_cpu) { @@ -7921,29 +8525,6 @@ static int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int t return -1; } -#else /* !CONFIG_SCHED_SMT: */ - -static inline void set_idle_cores(int cpu, int val) -{ -} - -static inline bool test_idle_cores(int cpu) -{ - return false; -} - -static inline int select_idle_core(struct task_struct *p, int core, struct cpumask *cpus, int *idle_cpu) -{ - return __select_idle_cpu(core, p); -} - -static inline int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int target) -{ - return -1; -} - -#endif /* !CONFIG_SCHED_SMT */ - /* * Scan the LLC domain for idle CPUs; this is dynamically regulated by * comparing the average scan cost (tracked in sd->avg_scan_cost) against the @@ -7954,7 +8535,7 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool struct cpumask *cpus = this_cpu_cpumask_var_ptr(select_rq_mask); int i, cpu, idle_cpu = -1, nr = INT_MAX; - if (sched_feat(SIS_UTIL)) { + if (sched_feat(SIS_UTIL) && sd->shared) { /* * Increment because !--nr is the condition to stop scan. * @@ -8019,6 +8600,54 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool } /* + * Idle-capacity scan converts util_fits_cpu() outcomes into preference ranks, + * where lower values indicate a better fit - see select_idle_capacity(). + * + * A CPU that both fits the task and sits on a fully-idle SMT core is returned + * immediately and is never assigned one of these ranks. On !SMT every CPU is + * its own "core", so the early return covers all fits-and-idle cases and the + * core-tier ranks below become unreachable. + * + * Rank Val Tier Meaning + * ------------------------------ --- ------ --------------------------- + * ASYM_IDLE_UCLAMP_MISFIT -4 core Idle core; capacity fits + * util but uclamp_min misses. + * ASYM_IDLE_COMPLETE_MISFIT -3 core Idle core; capacity does + * not fit. Still beats every + * thread-tier rank: a busy + * sibling cuts effective + * capacity more than a + * misfit hurts a quiet core. + * ASYM_IDLE_THREAD_FITS -2 thread Busy SMT sibling; capacity + * fits util + uclamp. + * ASYM_IDLE_THREAD_UCLAMP_MISFIT -1 thread Busy SMT sibling; capacity + * fits but uclamp_min misses + * (native util_fits_cpu() + * return value). + * ASYM_IDLE_THREAD_MISFIT 0 thread Busy SMT sibling; capacity + * does not fit. + * + * ASYM_IDLE_CORE_BIAS (-3) is an offset, not a state. On an idle core, + * fits += ASYM_IDLE_CORE_BIAS rebases thread-tier ranks into the core tier: + * + * ASYM_IDLE_THREAD_UCLAMP_MISFIT (-1) + BIAS -> ASYM_IDLE_UCLAMP_MISFIT (-4) + * ASYM_IDLE_THREAD_MISFIT (0) + BIAS -> ASYM_IDLE_COMPLETE_MISFIT (-3) + * + * ASYM_IDLE_THREAD_FITS (-2) is never rebased because a fully-fitting idle-core + * candidate early-returns from select_idle_capacity(). + */ +enum asym_fits_state { + ASYM_IDLE_UCLAMP_MISFIT = -4, + ASYM_IDLE_COMPLETE_MISFIT, + ASYM_IDLE_THREAD_FITS, + ASYM_IDLE_THREAD_UCLAMP_MISFIT, + ASYM_IDLE_THREAD_MISFIT, + + /* util_fits_cpu() bias for idle core */ + ASYM_IDLE_CORE_BIAS = -3, +}; + +/* * Scan the asym_capacity domain for idle CPUs; pick the first idle one on which * the task fits. If no CPU is big enough, but there are idle ones, try to * maximize capacity. @@ -8026,10 +8655,17 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool static int select_idle_capacity(struct task_struct *p, struct sched_domain *sd, int target) { + /* + * On !SMT systems, has_idle_core is always false and preferred_core + * is always true (CPU == core), so the SMT preference logic below + * collapses to the plain capacity scan. + */ + bool has_idle_core = sched_smt_active() && test_idle_cores(target); unsigned long task_util, util_min, util_max, best_cap = 0; - int fits, best_fits = 0; + int fits, best_fits = ASYM_IDLE_THREAD_MISFIT; int cpu, best_cpu = -1; struct cpumask *cpus; + int nr = INT_MAX; cpus = this_cpu_cpumask_var_ptr(select_rq_mask); cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr); @@ -8038,16 +8674,41 @@ select_idle_capacity(struct task_struct *p, struct sched_domain *sd, int target) util_min = uclamp_eff_value(p, UCLAMP_MIN); util_max = uclamp_eff_value(p, UCLAMP_MAX); + if (sched_feat(SIS_UTIL) && sd->shared) { + /* + * Same nr_idle_scan hint as select_idle_cpu(), nr only limits + * the scan when not preferring an idle core. + */ + nr = READ_ONCE(sd->shared->nr_idle_scan) + 1; + /* overloaded domain is unlikely to have idle cpu/core */ + if (nr == 1) + return -1; + } + for_each_cpu_wrap(cpu, cpus, target) { + bool preferred_core = !has_idle_core || is_core_idle(cpu); unsigned long cpu_cap = capacity_of(cpu); + /* + * Stop when the nr_idle_scan is exhausted (mirrors + * select_idle_cpu() logic). + */ + if (!has_idle_core && --nr <= 0) + return best_cpu; + if (!choose_idle_cpu(cpu, p)) continue; fits = util_fits_cpu(task_util, util_min, util_max, cpu); - /* This CPU fits with all requirements */ - if (fits > 0) + /* + * Perfect fit: capacity satisfies util + uclamp and the CPU + * sits on a fully-idle SMT core, this is a !SMT system, or + * there is no idle core to find. + * Short-circuit the rank-based selection and return + * immediately. + */ + if (fits > 0 && preferred_core) return cpu; /* * Only the min performance hint (i.e. uclamp_min) doesn't fit. @@ -8055,9 +8716,33 @@ select_idle_capacity(struct task_struct *p, struct sched_domain *sd, int target) */ else if (fits < 0) cpu_cap = get_actual_cpu_capacity(cpu); + /* + * fits > 0 implies we are not on a preferred core, but the util + * fits CPU capacity. Set fits to ASYM_IDLE_THREAD_FITS + * so the effective range becomes + * [ASYM_IDLE_THREAD_FITS, ASYM_IDLE_THREAD_MISFIT], where: + * ASYM_IDLE_THREAD_MISFIT - does not fit + * ASYM_IDLE_THREAD_UCLAMP_MISFIT - fits with the exception of UCLAMP_MIN + * ASYM_IDLE_THREAD_FITS - fits with the exception of preferred_core + */ + else if (fits > 0) + fits = ASYM_IDLE_THREAD_FITS; /* - * First, select CPU which fits better (-1 being better than 0). + * If we are on a preferred core, translate the range of fits + * of [ASYM_IDLE_THREAD_UCLAMP_MISFIT, ASYM_IDLE_THREAD_MISFIT] to + * [ASYM_IDLE_UCLAMP_MISFIT, ASYM_IDLE_COMPLETE_MISFIT]. + * This ensures that an idle core is always given priority over + * (partially) busy core. + * + * A fully fitting idle core would have returned early and hence + * fits > 0 for preferred_core need not be dealt with. + */ + if (preferred_core) + fits += ASYM_IDLE_CORE_BIAS; + + /* + * First, select CPU which fits better (lower is more preferred). * Then, select the one with best capacity at same level. */ if ((fits < best_fits) || @@ -8068,6 +8753,19 @@ select_idle_capacity(struct task_struct *p, struct sched_domain *sd, int target) } } + /* + * A value in the [ASYM_IDLE_UCLAMP_MISFIT, ASYM_IDLE_COMPLETE_MISFIT] + * range means the chosen CPU is in a fully idle SMT core. Values above + * ASYM_IDLE_COMPLETE_MISFIT mean we never ranked such a CPU best. + * + * The asym-capacity wakeup path returns from select_idle_sibling() + * after this function and never runs select_idle_cpu(), so the usual + * select_idle_cpu() tail that clears idle cores must live here when the + * idle-core preference did not win. + */ + if (has_idle_core && best_fits > ASYM_IDLE_COMPLETE_MISFIT) + set_idle_cores(target, false); + return best_cpu; } @@ -8076,12 +8774,22 @@ static inline bool asym_fits_cpu(unsigned long util, unsigned long util_max, int cpu) { - if (sched_asym_cpucap_active()) + if (sched_asym_cpucap_active()) { /* * Return true only if the cpu fully fits the task requirements * which include the utilization and the performance hints. + * + * When SMT is active, also require that the core has no busy + * siblings. + * + * Note: gating on is_core_idle() also makes the early-bailout + * candidates in select_idle_sibling() (target, prev, + * recent_used_cpu) idle-core-aware on ASYM+SMT, which the + * NO_ASYM path does not do. */ - return (util_fits_cpu(util, util_min, util_max, cpu) > 0); + return (!sched_smt_active() || is_core_idle(cpu)) && + (util_fits_cpu(util, util_min, util_max, cpu) > 0); + } return true; } @@ -8260,25 +8968,32 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target) static unsigned long cpu_util(int cpu, struct task_struct *p, int dst_cpu, int boost) { + bool add_task = p && task_cpu(p) != cpu && dst_cpu == cpu; + bool sub_task = p && task_cpu(p) == cpu && dst_cpu != cpu; struct cfs_rq *cfs_rq = &cpu_rq(cpu)->cfs; unsigned long util = READ_ONCE(cfs_rq->avg.util_avg); unsigned long runnable; - if (boost) { - runnable = READ_ONCE(cfs_rq->avg.runnable_avg); - util = max(util, runnable); - } - /* * If @dst_cpu is -1 or @p migrates from @cpu to @dst_cpu remove its * contribution. If @p migrates from another CPU to @cpu add its * contribution. In all the other cases @cpu is not impacted by the * migration so its util_avg is already correct. */ - if (p && task_cpu(p) == cpu && dst_cpu != cpu) - lsub_positive(&util, task_util(p)); - else if (p && task_cpu(p) != cpu && dst_cpu == cpu) + if (add_task) util += task_util(p); + else if (sub_task) + lsub_positive(&util, task_util(p)); + + if (boost) { + runnable = READ_ONCE(cfs_rq->avg.runnable_avg); + if (add_task) + runnable += READ_ONCE(p->se.avg.runnable_avg); + else if (sub_task) + lsub_positive(&runnable, + READ_ONCE(p->se.avg.runnable_avg)); + util = max(util, runnable); + } if (sched_feat(UTIL_EST)) { unsigned long util_est; @@ -9194,17 +9909,19 @@ preempt: resched_curr_lazy(rq); } -static struct task_struct *pick_task_fair(struct rq *rq, struct rq_flags *rf) +struct task_struct *pick_task_fair(struct rq *rq, struct rq_flags *rf) + __must_hold(__rq_lockp(rq)) { struct sched_entity *se; struct cfs_rq *cfs_rq; struct task_struct *p; bool throttled; + int new_tasks; again: cfs_rq = &rq->cfs; if (!cfs_rq->nr_queued) - return NULL; + goto idle; throttled = false; @@ -9213,8 +9930,6 @@ again: if (cfs_rq->curr && cfs_rq->curr->on_rq) update_curr(cfs_rq); - throttled |= check_cfs_rq_runtime(cfs_rq); - se = pick_next_entity(rq, cfs_rq, true); if (!se) goto again; @@ -9225,95 +9940,22 @@ again: if (unlikely(throttled)) task_throttle_setup_work(p); return p; -} - -static void __set_next_task_fair(struct rq *rq, struct task_struct *p, bool first); -static void set_next_task_fair(struct rq *rq, struct task_struct *p, bool first); - -struct task_struct * -pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) - __must_hold(__rq_lockp(rq)) -{ - struct sched_entity *se; - struct task_struct *p; - int new_tasks; - -again: - p = pick_task_fair(rq, rf); - if (!p) - goto idle; - se = &p->se; - -#ifdef CONFIG_FAIR_GROUP_SCHED - if (prev->sched_class != &fair_sched_class) - goto simple; - - __put_prev_set_next_dl_server(rq, prev, p); - - /* - * Because of the set_next_buddy() in dequeue_task_fair() it is rather - * likely that a next task is from the same cgroup as the current. - * - * Therefore attempt to avoid putting and setting the entire cgroup - * hierarchy, only change the part that actually changes. - * - * Since we haven't yet done put_prev_entity and if the selected task - * is a different task than we started out with, try and touch the - * least amount of cfs_rqs. - */ - if (prev != p) { - struct sched_entity *pse = &prev->se; - struct cfs_rq *cfs_rq; - - while (!(cfs_rq = is_same_group(se, pse))) { - int se_depth = se->depth; - int pse_depth = pse->depth; - - if (se_depth <= pse_depth) { - put_prev_entity(cfs_rq_of(pse), pse); - pse = parent_entity(pse); - } - if (se_depth >= pse_depth) { - set_next_entity(cfs_rq_of(se), se, true); - se = parent_entity(se); - } - } - - put_prev_entity(cfs_rq, pse); - set_next_entity(cfs_rq, se, true); - - __set_next_task_fair(rq, p, true); - } - - return p; - -simple: -#endif /* CONFIG_FAIR_GROUP_SCHED */ - put_prev_set_next_task(rq, prev, p); - return p; idle: - if (rf) { - new_tasks = sched_balance_newidle(rq, rf); - - /* - * Because sched_balance_newidle() releases (and re-acquires) - * rq->lock, it is possible for any higher priority task to - * appear. In that case we must re-start the pick_next_entity() - * loop. - */ - if (new_tasks < 0) - return RETRY_TASK; - - if (new_tasks > 0) - goto again; - } + if (sched_core_enabled(rq)) + return NULL; + new_tasks = sched_balance_newidle(rq, rf); + if (new_tasks < 0) + return RETRY_TASK; + if (new_tasks > 0) + goto again; return NULL; } static struct task_struct * fair_server_pick_task(struct sched_dl_entity *dl_se, struct rq_flags *rf) + __must_hold(__rq_lockp(dl_se->rq)) { return pick_task_fair(dl_se->rq, rf); } @@ -9334,10 +9976,33 @@ static void put_prev_task_fair(struct rq *rq, struct task_struct *prev, struct t { struct sched_entity *se = &prev->se; struct cfs_rq *cfs_rq; + struct sched_entity *nse = NULL; - for_each_sched_entity(se) { +#ifdef CONFIG_FAIR_GROUP_SCHED + if (next && next->sched_class == &fair_sched_class) + nse = &next->se; +#endif + + while (se) { cfs_rq = cfs_rq_of(se); - put_prev_entity(cfs_rq, se); + if (!nse || cfs_rq->curr) + put_prev_entity(cfs_rq, se); +#ifdef CONFIG_FAIR_GROUP_SCHED + if (nse) { + if (is_same_group(se, nse)) + break; + + int d = nse->depth - se->depth; + if (d >= 0) { + /* nse has equal or greater depth, ascend */ + nse = parent_entity(nse); + /* if nse is the deeper, do not ascend se */ + if (d > 0) + continue; + } + } +#endif + se = parent_entity(se); } } @@ -9559,6 +10224,16 @@ enum group_type { */ group_imbalanced, /* + * There are tasks running on non-preferred LLC, possible to move + * them to their preferred LLC without creating too much imbalance. + * The priority of group_llc_balance is lower than that of + * group_overloaded and higher than that of all other group types. + * This is because group_llc_balance may exacerbate load imbalance. + * If the LLC balancing attempt fails, the nr_balance_failed + * mechanism will trigger other group types to rebalance the load. + */ + group_llc_balance, + /* * The CPU is overloaded and can't provide expected CPU cycles to all * tasks. */ @@ -9569,7 +10244,8 @@ enum migration_type { migrate_load = 0, migrate_util, migrate_task, - migrate_misfit + migrate_misfit, + migrate_llc_task }; #define LBF_ALL_PINNED 0x01 @@ -9577,6 +10253,7 @@ enum migration_type { #define LBF_DST_PINNED 0x04 #define LBF_SOME_PINNED 0x08 #define LBF_ACTIVE_LB 0x10 +#define LBF_LLC_PINNED 0x20 struct lb_env { struct sched_domain *sd; @@ -9586,6 +10263,7 @@ struct lb_env { int dst_cpu; struct rq *dst_rq; + bool dst_core_idle; struct cpumask *dst_grpmask; int new_dst_cpu; @@ -9722,7 +10400,7 @@ static inline int task_is_ineligible_on_dst_cpu(struct task_struct *p, int dest_ struct cfs_rq *dst_cfs_rq; #ifdef CONFIG_FAIR_GROUP_SCHED - dst_cfs_rq = task_group(p)->cfs_rq[dest_cpu]; + dst_cfs_rq = tg_cfs_rq(task_group(p), dest_cpu); #else dst_cfs_rq = &cpu_rq(dest_cpu)->cfs; #endif @@ -9733,6 +10411,298 @@ static inline int task_is_ineligible_on_dst_cpu(struct task_struct *p, int dest_ return 0; } +#ifdef CONFIG_SCHED_CACHE +/* + * The margin used when comparing LLC utilization with CPU capacity. + * It determines the LLC load level where active LLC aggregation is + * done. + * Derived from fits_capacity(). + * + * (default: ~50%, tunable via debugfs) + */ +static bool fits_llc_capacity(unsigned long util, unsigned long max) +{ + u32 aggr_pct = llc_overaggr_pct; + + /* + * For single core systems, raise the aggregation + * threshold to accommodate more tasks. + */ + if (cpu_smt_num_threads == 1) + aggr_pct = (aggr_pct * 3 / 2); + + return util * 100 < max * aggr_pct; +} + +/* + * The margin used when comparing utilization. + * is 'util1' noticeably greater than 'util2' + * Derived from capacity_greater(). + * Bias is in perentage. + */ +/* Allows dst util to be bigger than src util by up to bias percent */ +#define util_greater(util1, util2) \ + ((util1) * 100 > (util2) * (100 + llc_imb_pct)) + +static __maybe_unused bool get_llc_stats(int cpu, unsigned long *util, + unsigned long *cap) +{ + struct sched_domain_shared *sd_share; + + sd_share = rcu_dereference_all(per_cpu(sd_llc_shared, cpu)); + if (!sd_share) + return false; + + *util = READ_ONCE(sd_share->util_avg); + *cap = READ_ONCE(sd_share->capacity); + + return true; +} + +/* + * Decision matrix according to the LLC utilization. To + * decide whether we can do task aggregation across LLC. + * + * By default, 50% is the threshold for treating the LLC + * as busy. The reason for choosing 50% is to avoid saturation + * of SMT-2, and it is also a safe cutoff for other SMT-n + * platforms. SMT-1 has higher threshold because it is + * supposed to accommodate more tasks, see fits_llc_capacity(). + * + * 20% is the utilization imbalance percentage to decide + * if the preferred LLC is busier than the non-preferred LLC. + * 20 is a little higher than the LLC domain's imbalance_pct + * 17. The hysteresis is used to avoid task bouncing between the + * preferred LLC and the non-preferred LLC, and it will + * be turned into tunable debugfs. + * + * 1. moving towards the preferred LLC, dst is the preferred + * LLC, src is not. + * + * src \ dst 30% 40% 50% 60% + * 30% Y Y Y N + * 40% Y Y Y Y + * 50% Y Y G G + * 60% Y Y G G + * + * 2. moving out of the preferred LLC, src is the preferred + * LLC, dst is not: + * + * src \ dst 30% 40% 50% 60% + * 30% N N N N + * 40% N N N N + * 50% N N G G + * 60% Y N G G + * + * src : src_util + * dst : dst_util + * Y : Yes, migrate + * N : No, do not migrate + * G : let the Generic load balance to even the load. + * + * The intention is that if both LLCs are quite busy, cache aware + * load balance should not be performed, and generic load balance + * should take effect. However, if one is busy and the other is not, + * the preferred LLC capacity(50%) and imbalance criteria(20%) should + * be considered to determine whether LLC aggregation should be + * performed to bias the load towards the preferred LLC. + */ + +/* migration decision, 3 states are orthogonal. */ +enum llc_mig { + mig_forbid = 0, /* N: Don't migrate task, respect LLC preference */ + mig_llc, /* Y: Do LLC preference based migration */ + mig_unrestricted /* G: Don't restrict generic load balance migration */ +}; + +/* + * Check if task can be moved from the source LLC to the + * destination LLC without breaking cache aware preferrence. + * src_cpu and dst_cpu are arbitrary CPUs within the source + * and destination LLCs, respectively. + */ +static enum llc_mig can_migrate_llc(int src_cpu, int dst_cpu, + unsigned long tsk_util, + bool to_pref) +{ + unsigned long src_util, dst_util, src_cap, dst_cap; + + if (!get_llc_stats(src_cpu, &src_util, &src_cap) || + !get_llc_stats(dst_cpu, &dst_util, &dst_cap)) + return mig_unrestricted; + + src_util = src_util < tsk_util ? 0 : src_util - tsk_util; + dst_util = dst_util + tsk_util; + + if (!fits_llc_capacity(dst_util, dst_cap) && + !fits_llc_capacity(src_util, src_cap)) + return mig_unrestricted; + + if (to_pref) { + /* + * Don't migrate if we will get preferred LLC too + * heavily loaded and if the dest is much busier + * than the src, in which case migration will + * increase the imbalance too much. + */ + if (!fits_llc_capacity(dst_util, dst_cap) && + util_greater(dst_util, src_util)) + return mig_forbid; + } else { + /* + * Don't migrate if we will leave preferred LLC + * too idle, or if this migration leads to the + * non-preferred LLC falls within sysctl_aggr_imb percent + * of preferred LLC, leading to migration again + * back to preferred LLC. + */ + if (fits_llc_capacity(src_util, src_cap) || + !util_greater(src_util, dst_util)) + return mig_forbid; + } + return mig_llc; +} + +/* + * Check if task p can migrate from source LLC to + * destination LLC in terms of cache aware load balance. + */ +static enum llc_mig can_migrate_llc_task(int src_cpu, int dst_cpu, + struct task_struct *p) +{ + struct mm_struct *mm; + bool to_pref; + int cpu; + + mm = p->mm; + if (!mm) + return mig_unrestricted; + + cpu = READ_ONCE(mm->sc_stat.cpu); + if (cpu < 0 || cpus_share_cache(src_cpu, dst_cpu)) + return mig_unrestricted; + + /* skip cache aware load balance for too many threads */ + if (invalid_llc_nr(mm, p, dst_cpu) || + exceed_llc_capacity(mm, dst_cpu)) { + if (READ_ONCE(mm->sc_stat.cpu) != -1) + WRITE_ONCE(mm->sc_stat.cpu, -1); + return mig_unrestricted; + } + + if (cpus_share_cache(dst_cpu, cpu)) + to_pref = true; + else if (cpus_share_cache(src_cpu, cpu)) + to_pref = false; + else + return mig_unrestricted; + + return can_migrate_llc(src_cpu, dst_cpu, + task_util(p), to_pref); +} + +/* + * Check if active load balance breaks LLC locality in + * terms of cache aware load balance. The load level and + * imbalance do not warrant breaking LLC preference per + * the can_migrate_llc() policy. Here, the benefit of + * LLC locality outweighs the power efficiency gained from + * migrating the only runnable task away. + */ +static inline bool +alb_break_llc(struct lb_env *env) +{ + if (!sched_cache_enabled()) + return false; + + if (cpus_share_cache(env->src_cpu, env->dst_cpu)) + return false; + /* + * All tasks prefer to stay on their current CPU. + * Do not pull a task from its preferred CPU if: + * 1. It is the only task running and does not exceed + * imbalance allowance; OR + * 2. Migrating it away from its preferred LLC would violate + * the cache-aware scheduling policy. + */ + if (env->src_rq->nr_pref_llc_running && + env->src_rq->nr_pref_llc_running == env->src_rq->cfs.h_nr_runnable) { + unsigned long util = 0; + struct task_struct *cur; + + if (env->src_rq->nr_running <= 1) + return true; + + cur = rcu_dereference_all(env->src_rq->curr); + if (cur && cur->sched_class == &fair_sched_class) + util = task_util(cur); + + if (can_migrate_llc(env->src_cpu, env->dst_cpu, + util, false) == mig_forbid) + return true; + } + + return false; +} + +/* + * Check if migrating task p from env->src_cpu to + * env->dst_cpu breaks LLC localiy. + */ +static bool migrate_degrades_llc(struct task_struct *p, struct lb_env *env) +{ + if (!sched_cache_enabled()) + return false; + + if (task_has_sched_core(p)) + return false; + /* + * Skip over tasks that would degrade LLC locality; + * only when nr_balanced_failed is sufficiently high do we + * ignore this constraint. + * + * Threshold of cache_nice_tries is set to 1 higher + * than nr_balance_failed to avoid excessive task + * migration at the same time. + */ + if (env->sd->nr_balance_failed >= env->sd->cache_nice_tries + 1) + return false; + + /* + * We know the env->src_cpu has some tasks prefer to + * run on env->dst_cpu, skip the tasks do not prefer + * env->dst_cpu, and find the one that prefers. + */ + if (env->migration_type == migrate_llc_task && + READ_ONCE(p->preferred_llc) != llc_id(env->dst_cpu)) + return true; + + if (can_migrate_llc_task(env->src_cpu, + env->dst_cpu, p) != mig_forbid) + return false; + + return true; +} + +#else +static inline bool get_llc_stats(int cpu, unsigned long *util, + unsigned long *cap) +{ + return false; +} + +static inline bool +alb_break_llc(struct lb_env *env) +{ + return false; +} + +static inline bool +migrate_degrades_llc(struct task_struct *p, struct lb_env *env) +{ + return false; +} +#endif /* * can_migrate_task - may task p from runqueue rq be migrated to this_cpu? */ @@ -9829,10 +10799,29 @@ int can_migrate_task(struct task_struct *p, struct lb_env *env) return 1; degrades = migrate_degrades_locality(p, env); - if (!degrades) + if (!degrades) { + /* + * If the NUMA locality is not broken, + * further check if migration would hurt + * LLC locality. + */ + if (migrate_degrades_llc(p, env)) { + /* + * If regular load balancing fails to pull a task + * due to LLC locality, this is expected behavior + * and we set LBF_LLC_PINNED so we don't increase + * nr_balance_failed unecessarily. + */ + if (env->migration_type != migrate_llc_task) + env->flags |= LBF_LLC_PINNED; + + return 0; + } + hot = task_hot(p, env); - else + } else { hot = degrades > 0; + } if (!hot || env->sd->nr_balance_failed > env->sd->cache_nice_tries) { if (hot) @@ -9994,6 +10983,10 @@ static int detach_tasks(struct lb_env *env) env->imbalance = 0; break; + + case migrate_llc_task: + env->imbalance--; + break; } detach_task(p, env); @@ -10127,7 +11120,6 @@ static bool __update_blocked_fair(struct rq *rq, bool *done) { struct cfs_rq *cfs_rq, *pos; bool decayed = false; - int cpu = cpu_of(rq); /* * Iterates the task_group tree in a bottom up fashion, see @@ -10147,7 +11139,7 @@ static bool __update_blocked_fair(struct rq *rq, bool *done) } /* Propagate pending load changes to the parent, if any: */ - se = cfs_rq->tg->se[cpu]; + se = cfs_rq_se(cfs_rq); if (se && !skip_blocked_update(se)) update_load_avg(cfs_rq_of(se), se, UPDATE_TG); @@ -10173,8 +11165,7 @@ static bool __update_blocked_fair(struct rq *rq, bool *done) */ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) { - struct rq *rq = rq_of(cfs_rq); - struct sched_entity *se = cfs_rq->tg->se[cpu_of(rq)]; + struct sched_entity *se = cfs_rq_se(cfs_rq); unsigned long now = jiffies; unsigned long load; @@ -10272,12 +11263,16 @@ struct sg_lb_stats { enum group_type group_type; unsigned int group_asym_packing; /* Tasks should be moved to preferred CPU */ unsigned int group_smt_balance; /* Task on busy SMT be moved */ + unsigned int group_llc_balance; /* Tasks should be moved to preferred LLC */ unsigned long group_misfit_task_load; /* A CPU has a task too big for its capacity */ unsigned int group_overutilized; /* At least one CPU is overutilized in the group */ #ifdef CONFIG_NUMA_BALANCING unsigned int nr_numa_running; unsigned int nr_preferred_running; #endif +#ifdef CONFIG_SCHED_CACHE + unsigned int nr_pref_dst_llc; +#endif }; /* @@ -10535,6 +11530,9 @@ group_type group_classify(unsigned int imbalance_pct, if (group_is_overloaded(imbalance_pct, sgs)) return group_overloaded; + if (sgs->group_llc_balance) + return group_llc_balance; + if (sg_imbalanced(group)) return group_imbalanced; @@ -10689,6 +11687,105 @@ sched_reduced_capacity(struct rq *rq, struct sched_domain *sd) return check_cpu_capacity(rq, sd); } +#ifdef CONFIG_SCHED_CACHE +/* + * Record the statistics for this scheduler group for later + * use. These values guide load balancing on aggregating tasks + * to a LLC. + */ +static void record_sg_llc_stats(struct lb_env *env, + struct sg_lb_stats *sgs, + struct sched_group *group) +{ + struct sched_domain_shared *sd_share; + int cpu; + + if (!sched_cache_enabled() || env->idle == CPU_NEWLY_IDLE) + return; + + /* Only care about sched domain spanning multiple LLCs */ + if (env->sd->child != rcu_dereference_all(per_cpu(sd_llc, env->dst_cpu))) + return; + + /* + * At this point we know this group spans a LLC domain. + * Record the statistic of this group in its corresponding + * shared LLC domain. + * Note: sd_share cannot be obtained via sd->child->shared, + * because the latter refers to the domain that covers the + * local group. Instead, sd_share should be located using + * the first CPU of the LLC group. + */ + cpu = cpumask_first(sched_group_span(group)); + sd_share = rcu_dereference_all(per_cpu(sd_llc_shared, cpu)); + if (!sd_share) + return; + + if (READ_ONCE(sd_share->util_avg) != sgs->group_util) + WRITE_ONCE(sd_share->util_avg, sgs->group_util); + + if (unlikely(READ_ONCE(sd_share->capacity) != sgs->group_capacity)) + WRITE_ONCE(sd_share->capacity, sgs->group_capacity); +} + +/* + * Do LLC balance on sched group that contains LLC, and have tasks preferring + * to run on LLC in idle dst_cpu. + */ +static inline bool llc_balance(struct lb_env *env, struct sg_lb_stats *sgs, + struct sched_group *group) +{ + if (!sched_cache_enabled()) + return false; + + if (env->sd->flags & SD_SHARE_LLC) + return false; + + /* + * Skip cache aware tagging if nr_balanced_failed is sufficiently high. + * Threshold of cache_nice_tries is set to 1 higher than nr_balance_failed + * to avoid excessive task migration at the same time. + */ + if (env->sd->nr_balance_failed >= env->sd->cache_nice_tries + 1) + return false; + + if (sgs->nr_pref_dst_llc && + can_migrate_llc(cpumask_first(sched_group_span(group)), + env->dst_cpu, 0, true) == mig_llc) + return true; + + return false; +} + +static bool update_llc_busiest(struct lb_env *env, + struct sg_lb_stats *busiest, + struct sg_lb_stats *sgs) +{ + /* + * There are more tasks that want to run on dst_cpu's LLC. + */ + return sgs->nr_pref_dst_llc > busiest->nr_pref_dst_llc; +} +#else +static inline void record_sg_llc_stats(struct lb_env *env, struct sg_lb_stats *sgs, + struct sched_group *group) +{ +} + +static inline bool llc_balance(struct lb_env *env, struct sg_lb_stats *sgs, + struct sched_group *group) +{ + return false; +} + +static bool update_llc_busiest(struct lb_env *env, + struct sg_lb_stats *busiest, + struct sg_lb_stats *sgs) +{ + return false; +} +#endif + /** * update_sg_lb_stats - Update sched_group's statistics for load balancing. * @env: The load balancing environment. @@ -10725,6 +11822,20 @@ static inline void update_sg_lb_stats(struct lb_env *env, if (cpu_overutilized(i)) sgs->group_overutilized = 1; +#ifdef CONFIG_SCHED_CACHE + if (sched_cache_enabled()) { + struct sched_domain *sd_tmp; + int dst_llc; + + dst_llc = llc_id(env->dst_cpu); + if (llc_id(i) != dst_llc) { + sd_tmp = rcu_dereference_all(rq->sd); + if (sd_tmp && (unsigned int)dst_llc < sd_tmp->llc_max) + sgs->nr_pref_dst_llc += sd_tmp->llc_counts[dst_llc]; + } + } +#endif + /* * No need to call idle_cpu() if nr_running is not 0 */ @@ -10765,17 +11876,24 @@ static inline void update_sg_lb_stats(struct lb_env *env, sgs->group_weight = group->group_weight; - /* Check if dst CPU is idle and preferred to this group */ - if (!local_group && env->idle && sgs->sum_h_nr_running && - sched_group_asym(env, sgs, group)) - sgs->group_asym_packing = 1; + if (!local_group) { + /* Check if dst CPU is idle and preferred to this group */ + if (env->idle && sgs->sum_h_nr_running && + sched_group_asym(env, sgs, group)) + sgs->group_asym_packing = 1; + + /* Check for loaded SMT group to be balanced to dst CPU */ + if (smt_balance(env, sgs, group)) + sgs->group_smt_balance = 1; - /* Check for loaded SMT group to be balanced to dst CPU */ - if (!local_group && smt_balance(env, sgs, group)) - sgs->group_smt_balance = 1; + /* Check for tasks in this group can be moved to their preferred LLC */ + if (llc_balance(env, sgs, group)) + sgs->group_llc_balance = 1; + } sgs->group_type = group_classify(env->sd->imbalance_pct, group, sgs); + record_sg_llc_stats(env, sgs, group); /* Computing avg_load makes sense only when group is overloaded */ if (sgs->group_type == group_overloaded) sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) / @@ -10811,10 +11929,16 @@ static bool update_sd_pick_busiest(struct lb_env *env, * We can use max_capacity here as reduction in capacity on some * CPUs in the group should either be possible to resolve * internally or be covered by avg_load imbalance (eventually). + * + * When SMT is active, only pull a misfit to dst_cpu if it is on a + * fully idle core; otherwise the effective capacity of the core is + * reduced and we may not actually provide more capacity than the + * source. */ if ((env->sd->flags & SD_ASYM_CPUCAPACITY) && (sgs->group_type == group_misfit_task) && - (!capacity_greater(capacity_of(env->dst_cpu), sg->sgc->max_capacity) || + (!env->dst_core_idle || + !capacity_greater(capacity_of(env->dst_cpu), sg->sgc->max_capacity) || sds->local_stat.group_type != group_has_spare)) return false; @@ -10834,6 +11958,10 @@ static bool update_sd_pick_busiest(struct lb_env *env, /* Select the overloaded group with highest avg_load. */ return sgs->avg_load > busiest->avg_load; + case group_llc_balance: + /* Select the group with most tasks preferring dst LLC */ + return update_llc_busiest(env, busiest, sgs); + case group_imbalanced: /* * Select the 1st imbalanced group as we don't have any way to @@ -11096,6 +12224,7 @@ static bool update_pick_idlest(struct sched_group *idlest, return false; break; + case group_llc_balance: case group_imbalanced: case group_asym_packing: case group_smt_balance: @@ -11228,6 +12357,7 @@ sched_balance_find_dst_group(struct sched_domain *sd, struct task_struct *p, int return NULL; break; + case group_llc_balance: case group_imbalanced: case group_asym_packing: case group_smt_balance: @@ -11378,6 +12508,8 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd unsigned long sum_util = 0; bool sg_overloaded = 0, sg_overutilized = 0; + env->dst_core_idle = !sched_smt_active() || is_core_idle(env->dst_cpu); + do { struct sg_lb_stats *sgs = &tmp_sgs; int local_group; @@ -11480,6 +12612,15 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s return; } +#ifdef CONFIG_SCHED_CACHE + if (busiest->group_type == group_llc_balance) { + /* Move a task that prefer local LLC */ + env->migration_type = migrate_llc_task; + env->imbalance = 1; + return; + } +#endif + if (busiest->group_type == group_imbalanced) { /* * In the group_imb case we cannot rely on group-wide averages @@ -11726,7 +12867,8 @@ static struct sched_group *sched_balance_find_src_group(struct lb_env *env) * group's child domain. */ if (sds.prefer_sibling && local->group_type == group_has_spare && - sibling_imbalance(env, &sds, busiest, local) > 1) + (busiest->group_type == group_llc_balance || + sibling_imbalance(env, &sds, busiest, local) > 1)) goto force_balance; if (busiest->group_type != group_overloaded) { @@ -11785,7 +12927,10 @@ static struct rq *sched_balance_find_src_rq(struct lb_env *env, { struct rq *busiest = NULL, *rq; unsigned long busiest_util = 0, busiest_load = 0, busiest_capacity = 1; + unsigned int __maybe_unused busiest_pref_llc = 0; + struct sched_domain __maybe_unused *sd_tmp; unsigned int busiest_nr = 0; + int __maybe_unused dst_llc; int i; for_each_cpu_and(i, sched_group_span(group), env->cpus) { @@ -11913,6 +13058,23 @@ static struct rq *sched_balance_find_src_rq(struct lb_env *env, break; + case migrate_llc_task: +#ifdef CONFIG_SCHED_CACHE + sd_tmp = rcu_dereference_all(rq->sd); + dst_llc = llc_id(env->dst_cpu); + + if (sd_tmp && (unsigned)dst_llc < sd_tmp->llc_max) { + unsigned int this_pref_llc = + sd_tmp->llc_counts[dst_llc]; + + if (busiest_pref_llc < this_pref_llc) { + busiest_pref_llc = this_pref_llc; + busiest = rq; + } + } +#endif + break; + } } @@ -11964,6 +13126,9 @@ static int need_active_balance(struct lb_env *env) { struct sched_domain *sd = env->sd; + if (alb_break_llc(env)) + return 0; + if (asym_active_balance(env)) return 1; @@ -11983,7 +13148,8 @@ static int need_active_balance(struct lb_env *env) return 1; } - if (env->migration_type == migrate_misfit) + if (env->migration_type == migrate_misfit || + env->migration_type == migrate_llc_task) return 1; return 0; @@ -12028,7 +13194,9 @@ static int should_we_balance(struct lb_env *env) * balancing cores, but remember the first idle SMT CPU for * later consideration. Find CPU on an idle core first. */ - if (!(env->sd->flags & SD_SHARE_CPUCAPACITY) && !is_core_idle(cpu)) { + if (sched_smt_active() && + !(env->sd->flags & SD_SHARE_CPUCAPACITY) && + !is_core_idle(cpu)) { if (idle_smt == -1) idle_smt = cpu; /* @@ -12036,9 +13204,7 @@ static int should_we_balance(struct lb_env *env) * idle has been found, then its not needed to check other * SMT siblings for idleness: */ -#ifdef CONFIG_SCHED_SMT cpumask_andnot(swb_cpus, swb_cpus, cpu_smt_mask(cpu)); -#endif continue; } @@ -12076,6 +13242,8 @@ static void update_lb_imbalance_stat(struct lb_env *env, struct sched_domain *sd case migrate_misfit: __schedstat_add(sd->lb_imbalance_misfit[idle], env->imbalance); break; + case migrate_llc_task: + break; } } @@ -12279,9 +13447,16 @@ more_balance: * * Similarly for migration_misfit which is not related to * load/util migration, don't pollute nr_balance_failed. + * + * The same for cache aware scheduling's allowance for + * load imbalance. If regular load balance does not + * migrate task due to LLC locality, it is a expected + * behavior and don't pollute nr_balance_failed. + * See can_migrate_task(). */ if (idle != CPU_NEWLY_IDLE && - env.migration_type != migrate_misfit) + env.migration_type != migrate_misfit && + !(env.flags & LBF_LLC_PINNED)) sd->nr_balance_failed++; if (need_active_balance(&env)) { @@ -12785,8 +13960,6 @@ static void nohz_balancer_kick(struct rq *rq) goto out; } - rcu_read_lock(); - sd = rcu_dereference_all(rq->sd); if (sd) { /* @@ -12794,8 +13967,8 @@ static void nohz_balancer_kick(struct rq *rq) * capacity, kick the ILB to see if there's a better CPU to run on: */ if (rq->cfs.h_nr_runnable >= 1 && check_cpu_capacity(rq, sd)) { - flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK; - goto unlock; + flags |= NOHZ_STATS_KICK | NOHZ_BALANCE_KICK; + goto out; } } @@ -12811,8 +13984,8 @@ static void nohz_balancer_kick(struct rq *rq) */ for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) { if (sched_asym(sd, i, cpu)) { - flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK; - goto unlock; + flags |= NOHZ_STATS_KICK | NOHZ_BALANCE_KICK; + goto out; } } } @@ -12823,10 +13996,8 @@ static void nohz_balancer_kick(struct rq *rq) * When ASYM_CPUCAPACITY; see if there's a higher capacity CPU * to run the misfit task on. */ - if (check_misfit_status(rq)) { - flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK; - goto unlock; - } + if (check_misfit_status(rq)) + flags |= NOHZ_STATS_KICK | NOHZ_BALANCE_KICK; /* * For asymmetric systems, we do not want to nicely balance @@ -12835,10 +14006,10 @@ static void nohz_balancer_kick(struct rq *rq) * * Skip the LLC logic because it's not relevant in that case. */ - goto unlock; + goto out; } - sds = rcu_dereference_all(per_cpu(sd_llc_shared, cpu)); + sds = rcu_dereference_all(per_cpu(sd_balance_shared, cpu)); if (sds) { /* * If there is an imbalance between LLC domains (IOW we could @@ -12850,13 +14021,9 @@ static void nohz_balancer_kick(struct rq *rq) * like this LLC domain has tasks we could move. */ nr_busy = atomic_read(&sds->nr_busy_cpus); - if (nr_busy > 1) { - flags = NOHZ_STATS_KICK | NOHZ_BALANCE_KICK; - goto unlock; - } + if (nr_busy > 1) + flags |= NOHZ_STATS_KICK | NOHZ_BALANCE_KICK; } -unlock: - rcu_read_unlock(); out: if (READ_ONCE(nohz.needs_update)) flags |= NOHZ_NEXT_KICK; @@ -12868,17 +14035,17 @@ out: static void set_cpu_sd_state_busy(int cpu) { struct sched_domain *sd; - - rcu_read_lock(); sd = rcu_dereference_all(per_cpu(sd_llc, cpu)); - if (!sd || !sd->nohz_idle) - goto unlock; + /* + * sd->nohz_idle only pairs with nr_busy_cpus on sd->shared; if this + * domain has no shared object there is nothing to clear or account. + */ + if (!sd || !sd->shared || !sd->nohz_idle) + return; sd->nohz_idle = 0; atomic_inc(&sd->shared->nr_busy_cpus); -unlock: - rcu_read_unlock(); } void nohz_balance_exit_idle(struct rq *rq) @@ -12897,17 +14064,14 @@ void nohz_balance_exit_idle(struct rq *rq) static void set_cpu_sd_state_idle(int cpu) { struct sched_domain *sd; - - rcu_read_lock(); sd = rcu_dereference_all(per_cpu(sd_llc, cpu)); - if (!sd || sd->nohz_idle) - goto unlock; + /* See set_cpu_sd_state_busy(): nohz_idle is only used with sd->shared. */ + if (!sd || !sd->shared || sd->nohz_idle) + return; sd->nohz_idle = 1; atomic_dec(&sd->shared->nr_busy_cpus); -unlock: - rcu_read_unlock(); } /* @@ -13666,7 +14830,7 @@ static int task_is_throttled_fair(struct task_struct *p, int cpu) struct cfs_rq *cfs_rq; #ifdef CONFIG_FAIR_GROUP_SCHED - cfs_rq = task_group(p)->cfs_rq[cpu]; + cfs_rq = tg_cfs_rq(task_group(p), cpu); #else cfs_rq = &cpu_rq(cpu)->cfs; #endif @@ -13686,8 +14850,8 @@ static inline void task_tick_core(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; + struct cfs_rq *cfs_rq; for_each_sched_entity(se) { cfs_rq = cfs_rq_of(se); @@ -13700,6 +14864,8 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) if (static_branch_unlikely(&sched_numa_balancing)) task_tick_numa(rq, curr); + task_tick_cache(rq, curr); + update_misfit_status(curr, rq); check_update_overutilized_status(task_rq(curr)); @@ -13858,9 +15024,33 @@ static void switched_to_fair(struct rq *rq, struct task_struct *p) } } -static void __set_next_task_fair(struct rq *rq, struct task_struct *p, bool first) +/* + * Account for a task changing its policy or group. + * + * This routine is mostly called to set cfs_rq->curr field when a task + * migrates between groups/classes. + */ +static void set_next_task_fair(struct rq *rq, struct task_struct *p, bool first) { struct sched_entity *se = &p->se; + bool throttled = false; + + for_each_sched_entity(se) { + struct cfs_rq *cfs_rq = cfs_rq_of(se); + + if (IS_ENABLED(CONFIG_FAIR_GROUP_SCHED) && + first && cfs_rq->curr) + break; + + set_next_entity(cfs_rq, se, first); + /* ensure bandwidth has been allocated on our new cfs_rq */ + throttled |= account_cfs_rq_runtime(cfs_rq, 0); + } + + if (throttled) + task_throttle_setup_work(p); + + se = &p->se; if (task_on_rq_queued(p)) { /* @@ -13881,27 +15071,6 @@ static void __set_next_task_fair(struct rq *rq, struct task_struct *p, bool firs sched_fair_update_stop_tick(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 - * migrates between groups/classes. - */ -static void set_next_task_fair(struct rq *rq, struct task_struct *p, bool first) -{ - struct sched_entity *se = &p->se; - - for_each_sched_entity(se) { - struct cfs_rq *cfs_rq = cfs_rq_of(se); - - set_next_entity(cfs_rq, se, first); - /* ensure bandwidth has been allocated on our new cfs_rq */ - account_cfs_rq_runtime(cfs_rq, 0); - } - - __set_next_task_fair(rq, p, first); -} - void init_cfs_rq(struct cfs_rq *cfs_rq) { cfs_rq->tasks_timeline = RB_ROOT_CACHED; @@ -13929,56 +15098,38 @@ static void task_change_group_fair(struct task_struct *p) void free_fair_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]); - } - - kfree(tg->cfs_rq); - kfree(tg->se); + free_percpu(tg->cfs_rq); } int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent) { + struct cfs_tg_state __percpu *state; struct sched_entity *se; struct cfs_rq *cfs_rq; int i; - tg->cfs_rq = kzalloc_objs(cfs_rq, nr_cpu_ids); - if (!tg->cfs_rq) - goto err; - tg->se = kzalloc_objs(se, nr_cpu_ids); - if (!tg->se) + state = alloc_percpu_gfp(struct cfs_tg_state, GFP_KERNEL); + if (!state) goto err; + tg->cfs_rq = &state->cfs_rq; tg->shares = NICE_0_LOAD; init_cfs_bandwidth(tg_cfs_bandwidth(tg), tg_cfs_bandwidth(parent)); for_each_possible_cpu(i) { - cfs_rq = kzalloc_node(sizeof(struct cfs_rq), - GFP_KERNEL, cpu_to_node(i)); + cfs_rq = tg_cfs_rq(tg, i); if (!cfs_rq) goto err; - se = kzalloc_node(sizeof(struct sched_entity_stats), - GFP_KERNEL, cpu_to_node(i)); - if (!se) - goto err_free_rq; - + se = tg_se(tg, i); init_cfs_rq(cfs_rq); - init_tg_cfs_entry(tg, cfs_rq, se, i, parent->se[i]); + init_tg_cfs_entry(tg, cfs_rq, se, i, tg_se(parent, i)); init_entity_runnable_average(se); } return 1; -err_free_rq: - kfree(cfs_rq); err: return 0; } @@ -13992,7 +15143,7 @@ void online_fair_sched_group(struct task_group *tg) for_each_possible_cpu(i) { rq = cpu_rq(i); - se = tg->se[i]; + se = tg_se(tg, i); rq_lock_irq(rq, &rf); update_rq_clock(rq); attach_entity_cfs_rq(se); @@ -14008,8 +15159,8 @@ void unregister_fair_sched_group(struct task_group *tg) destroy_cfs_bandwidth(tg_cfs_bandwidth(tg)); for_each_possible_cpu(cpu) { - struct cfs_rq *cfs_rq = tg->cfs_rq[cpu]; - struct sched_entity *se = tg->se[cpu]; + struct cfs_rq *cfs_rq = tg_cfs_rq(tg, cpu); + struct sched_entity *se = tg_se(tg, cpu); struct rq *rq = cpu_rq(cpu); if (se) { @@ -14045,9 +15196,6 @@ void init_tg_cfs_entry(struct task_group *tg, struct cfs_rq *cfs_rq, cfs_rq->rq = rq; init_cfs_rq_runtime(cfs_rq); - tg->cfs_rq[cpu] = cfs_rq; - tg->se[cpu] = se; - /* se could be NULL for root_task_group */ if (!se) return; @@ -14077,7 +15225,7 @@ static int __sched_group_set_shares(struct task_group *tg, unsigned long shares) /* * We can't change the weight of the root cgroup. */ - if (!tg->se[0]) + if (is_root_task_group(tg)) return -EINVAL; shares = clamp(shares, scale_load(MIN_SHARES), scale_load(MAX_SHARES)); @@ -14088,7 +15236,7 @@ static int __sched_group_set_shares(struct task_group *tg, unsigned long shares) tg->shares = shares; for_each_possible_cpu(i) { struct rq *rq = cpu_rq(i); - struct sched_entity *se = tg->se[i]; + struct sched_entity *se = tg_se(tg, i); struct rq_flags rf; /* Propagate contribution to hierarchy */ @@ -14139,8 +15287,8 @@ int sched_group_set_idle(struct task_group *tg, long idle) for_each_possible_cpu(i) { struct rq *rq = cpu_rq(i); - struct sched_entity *se = tg->se[i]; - struct cfs_rq *grp_cfs_rq = tg->cfs_rq[i]; + struct sched_entity *se = tg_se(tg, i); + struct cfs_rq *grp_cfs_rq = tg_cfs_rq(tg, i); bool was_idle = cfs_rq_is_idle(grp_cfs_rq); long idle_task_delta; struct rq_flags rf; @@ -14213,7 +15361,6 @@ DEFINE_SCHED_CLASS(fair) = { .wakeup_preempt = wakeup_preempt_fair, .pick_task = pick_task_fair, - .pick_next_task = pick_next_task_fair, .put_prev_task = put_prev_task_fair, .set_next_task = set_next_task_fair, |