Lines Matching +full:locality +full:- +full:specific
1 // SPDX-License-Identifier: GPL-2.0
47 #include <linux/memory-tiers.h>
65 * The initial- and re-scaling of tunables is configurable
69 * SCHED_TUNABLESCALING_NONE - unscaled, always *1
70 * SCHED_TUNABLESCALING_LOG - scaled logarithmically, *1+ilog(ncpus)
71 * SCHED_TUNABLESCALING_LINEAR - scaled linear, *ncpus
102 return -cpu;
122 * Amount of runtime to allocate from global (tg) to local (per-cfs_rq) pool
173 lw->weight += inc;
174 lw->inv_weight = 0;
179 lw->weight -= dec;
180 lw->inv_weight = 0;
185 lw->weight = w;
186 lw->inv_weight = 0;
193 * so pick a second-best guess by going with the log2 of the
242 if (likely(lw->inv_weight))
245 w = scale_load_down(lw->weight);
248 lw->inv_weight = 1;
250 lw->inv_weight = WMULT_CONST;
252 lw->inv_weight = WMULT_CONST / w;
258 * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
278 shift -= fs;
282 fact = mul_u32_u32(fact, lw->inv_weight);
287 shift -= fs;
296 return (delta_exec * weight) / lw->weight;
305 if (se->h_load.weight != NICE_0_LOAD)
306 delta = __calc_delta(delta, NICE_0_LOAD, &se->h_load);
321 for (; se; se = se->parent)
328 if (cfs_rq->on_list)
329 return rq->tmp_alone_branch == &rq->leaf_cfs_rq_list;
331 cfs_rq->on_list = 1;
336 * enqueued. The fact that we always enqueue bottom-up
342 if (cfs_rq->tg->parent &&
343 tg_cfs_rq(cfs_rq->tg->parent, cpu)->on_list) {
350 list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
351 &(tg_cfs_rq(cfs_rq->tg->parent, cpu)->leaf_cfs_rq_list));
357 rq->tmp_alone_branch = &rq->leaf_cfs_rq_list;
361 if (!cfs_rq->tg->parent) {
366 list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
367 &rq->leaf_cfs_rq_list);
372 rq->tmp_alone_branch = &rq->leaf_cfs_rq_list;
382 list_add_rcu(&cfs_rq->leaf_cfs_rq_list, rq->tmp_alone_branch);
387 rq->tmp_alone_branch = &cfs_rq->leaf_cfs_rq_list;
393 if (cfs_rq->on_list) {
400 * to the prev element but it will point to rq->leaf_cfs_rq_list
403 if (rq->tmp_alone_branch == &cfs_rq->leaf_cfs_rq_list)
404 rq->tmp_alone_branch = cfs_rq->leaf_cfs_rq_list.prev;
406 list_del_rcu(&cfs_rq->leaf_cfs_rq_list);
407 cfs_rq->on_list = 0;
413 WARN_ON_ONCE(rq->tmp_alone_branch != &rq->leaf_cfs_rq_list);
418 list_for_each_entry_safe(cfs_rq, pos, &rq->leaf_cfs_rq_list, \
425 if (se->cfs_rq == pse->cfs_rq)
426 return se->cfs_rq;
433 return se->parent;
438 return tg->idle > 0;
443 return cfs_rq->idle > 0;
472 for (cfs_rq = &rq->cfs, pos = NULL; cfs_rq; cfs_rq = pos)
511 __res = ((s64)((A)-(B)) < 0); \
513 __res = ((s64)((A)-(B)) <= 0); \
515 __res = ((s64)((A)-(B)) > 0); \
517 __res = ((s64)((A)-(B)) >= 0); \
531 if (!__builtin_strcmp(OP_STR, "-")) { \
532 __res = (s64)((A)-(B)); \
565 return vruntime_cmp(a->deadline, "<", b->deadline);
579 * (disregarding the actual divide-by-weight part makes for the worst case
581 * being the zero-lag point).
585 return vruntime_op(se->vruntime, "-", cfs_rq->zero_vruntime);
592 * Compute virtual time from the per-task service numbers:
600 * lag_i = S - s_i = w_i * (V - v_i)
606 * \Sum w_i * (V - v_i) = 0
607 * \Sum (w_i * V - w_i * v_i) = 0
610 * se->vruntime):
613 * V = -------------- = --------------
620 * virtual time has non-contiguous motion equivalent to:
622 * V +-= lag_i / W
629 * Substitute: v_i == (v_i - v0) + v0
631 * \Sum ((v_i - v0) + v0) * w_i \Sum (v_i - v0) * w_i
632 * V = ---------------------------- = --------------------- + v0
637 * v0 := cfs_rq->zero_vruntime
638 * \Sum (v_i - v0) * w_i := cfs_rq->sum_w_vruntime
639 * \Sum w_i := cfs_rq->sum_weight
641 * Since zero_vruntime closely tracks the per-task service, these
642 * deltas: (v_i - v0), will be in the order of the maximal (virtual) lag
648 if (cfs_rq->sum_shift)
649 w = max(2UL, w >> cfs_rq->sum_shift);
657 unsigned long weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
663 cfs_rq->sum_w_vruntime += w_vruntime;
664 cfs_rq->sum_weight += weight;
674 weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
680 if (check_add_overflow(cfs_rq->sum_w_vruntime, key, &tmp))
683 cfs_rq->sum_w_vruntime = tmp;
684 cfs_rq->sum_weight += weight;
689 * There's gotta be a limit -- if we're still failing at this point
692 BUG_ON(cfs_rq->sum_shift >= 10);
693 cfs_rq->sum_shift++;
698 cfs_rq->sum_w_vruntime = 0;
699 cfs_rq->sum_weight = 0;
701 for (struct rb_node *node = cfs_rq->tasks_timeline.rb_leftmost;
720 unsigned long weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
723 cfs_rq->sum_w_vruntime -= key * weight;
724 cfs_rq->sum_weight -= weight;
731 * v' = v + d ==> sum_w_vruntime' = sum_w_vruntime - d*sum_weight
733 cfs_rq->sum_w_vruntime -= cfs_rq->sum_weight * delta;
734 cfs_rq->zero_vruntime += delta;
742 * - place_entity() -- before enqueue
743 * - update_entity_lag() -- before dequeue
744 * - update_deadline() -- slice expiration
751 struct sched_entity *curr = cfs_rq->curr;
752 long weight = cfs_rq->sum_weight;
755 if (curr && !curr->on_rq)
759 s64 runtime = cfs_rq->sum_w_vruntime;
762 unsigned long w = avg_vruntime_weight(cfs_rq, curr->h_load.weight);
770 runtime -= (weight - 1);
777 delta = curr->vruntime - cfs_rq->zero_vruntime;
782 return cfs_rq->zero_vruntime;
786 * \Sum (v_i - v0)*w_i
787 * V = ------------------- + v0
792 * V = 1/W * {(v_j - v0)*w_j + \Sum_i!=j (v_i - v0)*w_i} + v0
794 * v_j = 1/W * {(v_j - v0)*w_j + \Sum_i!=j (v_i - v0)*w_i} + v0
796 * v_j = 1/W * (v_j - v0)*w_j + 1/W * \Sum_i!=j (v_i - v0)*w_i + v0
798 * v_j - 1/W * (v_j - v0)*w_j = 1/W * \Sum_i!=j (v_i - v0)*w_i + v0
800 * v_j*W - (v_j - v0)*w_j = \Sum_i!=j (v_i - v0)*w_i + v0*W
802 * v_j*(W - w_j) + v0*w_j = \Sum_i!=j (v_i - v0)*w_i + v0*W
804 * v_j*(W - w_j) = \Sum_i!=j (v_i - v0)*w_i + v0*(W - w_j)
806 * \Sum_i!=j (v_i - v0)*w_i
807 * v_j = ------------------------ + v0
808 * W - w_j
810 * When v_j happens to be curr, then '\Sum_i!=j (v_i - v0)*w_i'
811 * is cfs_rq->sum_w_runtime, and 'W - w_j' is cfs_rq->sum_weight, since curr
816 struct sched_entity *curr = cfs_rq->curr;
817 long weight = cfs_rq->sum_weight;
820 if (curr && !curr->on_rq)
830 s64 runtime = cfs_rq->sum_w_vruntime;
833 * Do not add @curr to obtain the effective '- w_j' terms.
838 runtime -= (weight - 1);
843 return cfs_rq->zero_vruntime + delta + 1;
849 * lag_i = S - s_i = w_i * (V - v_i)
852 * is possible -- by addition/removal/reweight to the tree -- to move V around
860 * -r_max < lag < max(r_max, q)
867 vlag = avruntime - se->vruntime;
870 return clamp(vlag, -limit, limit);
882 * se->vlag != avg_vruntime() - se->vruntime
894 if (se->sched_delayed) {
896 vlag = max(vlag, se->vlag);
900 se->vlag = vlag;
902 return avruntime - vlag != se->vruntime;
909 * lag_i = S - s_i = w_i*(V - v_i)
911 * lag_i >= 0 -> V >= v_i
913 * \Sum (v_i - v0)*w_i
914 * V = ------------------- + v0
917 * lag_i >= 0 -> \Sum (v_i - v0)*w_i >= (v_i - v0)*(\Sum w_i)
919 * Note: using 'avg_vruntime() > se->vruntime' is inaccurate due
924 struct sched_entity *curr = cfs_rq->curr;
925 s64 key, avg = cfs_rq->sum_w_vruntime;
926 long load = cfs_rq->sum_weight;
928 if (curr && curr->on_rq) {
929 unsigned long weight = avg_vruntime_weight(cfs_rq, curr->h_load.weight);
935 key = vruntime_op(vruntime, "-", cfs_rq->zero_vruntime);
969 return vruntime_eligible(cfs_rq, se->vruntime);
975 struct sched_entity *curr = cfs_rq->curr;
978 if (curr && curr->on_rq)
979 min_slice = curr->slice;
982 min_slice = min(min_slice, root->min_slice);
990 struct sched_entity *curr = cfs_rq->curr;
993 if (curr && curr->on_rq)
994 max_slice = curr->slice;
997 max_slice = max(max_slice, root->max_slice);
1012 if (vruntime_cmp(se->min_vruntime, ">", rse->min_vruntime))
1013 se->min_vruntime = rse->min_vruntime;
1021 if (rse->min_slice < se->min_slice)
1022 se->min_slice = rse->min_slice;
1030 if (rse->max_slice > se->max_slice)
1031 se->max_slice = rse->max_slice;
1037 new->min_vruntime = old->min_vruntime;
1038 new->min_slice = old->min_slice;
1039 new->max_slice = old->max_slice;
1043 * se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime)
1047 u64 old_min_vruntime = se->min_vruntime;
1048 u64 old_min_slice = se->min_slice;
1049 u64 old_max_slice = se->max_slice;
1050 struct rb_node *node = &se->run_node;
1052 se->min_vruntime = se->vruntime;
1053 __min_vruntime_update(se, node->rb_right);
1054 __min_vruntime_update(se, node->rb_left);
1056 se->min_slice = se->slice;
1057 __min_slice_update(se, node->rb_right);
1058 __min_slice_update(se, node->rb_left);
1060 se->max_slice = se->slice;
1061 __max_slice_update(se, node->rb_right);
1062 __max_slice_update(se, node->rb_left);
1064 return se->min_vruntime == old_min_vruntime &&
1065 se->min_slice == old_min_slice &&
1066 se->max_slice == old_max_slice;
1074 * Enqueue an entity into the rb-tree:
1078 WARN_ON_ONCE(&rq_of(cfs_rq)->cfs != cfs_rq);
1082 se->min_vruntime = se->vruntime;
1083 se->min_slice = se->slice;
1084 se->max_slice = se->slice;
1086 rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
1092 WARN_ON_ONCE(&rq_of(cfs_rq)->cfs != cfs_rq);
1095 rb_erase_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
1102 struct rb_node *root = cfs_rq->tasks_timeline.rb_root.rb_node;
1112 struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
1131 u64 vprot = se->deadline;
1136 slice = min(slice, se->slice);
1139 if (slice != se->slice) {
1143 vprot = min_vruntime(vprot, se->vruntime + calc_delta_fair(slice, se));
1146 se->vprot = vprot;
1152 u64 vruntime = min_vruntime(se->vruntime, avg_vruntime(cfs_rq));
1154 se->vprot = min_vruntime(se->vprot, vruntime + calc_delta_fair(slice, se));
1159 return vruntime_cmp(se->vruntime, "<", se->vprot);
1165 se->vprot = se->vruntime;
1179 * We can do this in O(log n) time due to an augmented RB-tree. The
1183 * se->min_vruntime = min(se->vruntime, se->{left,right}->min_vruntime)
1189 struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
1191 struct sched_entity *curr = cfs_rq->curr;
1198 if (cfs_rq->h_nr_queued == 1)
1199 return curr && curr->on_rq ? curr : se;
1202 * Picking the ->next buddy will affect latency but not fairness.
1205 cfs_rq->next && entity_eligible(cfs_rq, cfs_rq->next)) {
1206 /* ->next will never be delayed */
1207 WARN_ON_ONCE(cfs_rq->next->sched_delayed);
1208 return cfs_rq->next;
1211 if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr)))
1225 struct rb_node *left = node->rb_left;
1232 __node_2_se(left)->min_vruntime)) {
1249 node = node->rb_right;
1260 struct rb_node *last = rb_last(&cfs_rq->tasks_timeline.rb_root);
1291 if (vruntime_cmp(se->vruntime, "<", se->deadline))
1299 if (!se->custom_slice)
1300 se->slice = sysctl_sched_base_slice;
1305 se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
1323 struct sched_avg *sa = &se->avg;
1334 sa->load_avg = scale_load_down(se->load.weight);
1343 * util_avg = cfs_rq->avg.util_avg / (cfs_rq->avg.load_avg + 1)
1353 * util_avg_cap = (cpu_scale - cfs_rq->avg.util_avg) / 2^n
1368 struct sched_entity *se = &p->se;
1370 struct sched_avg *sa = &se->avg;
1372 long cap = (long)(cpu_scale - cfs_rq->avg.util_avg) / 2;
1374 if (p->sched_class != &fair_sched_class) {
1385 se->avg.last_update_time = cfs_rq_clock_pelt(cfs_rq);
1390 if (cfs_rq->avg.util_avg != 0) {
1391 sa->util_avg = cfs_rq->avg.util_avg * se_weight(se);
1392 sa->util_avg /= (cfs_rq->avg.load_avg + 1);
1394 if (sa->util_avg > cap)
1395 sa->util_avg = cap;
1397 sa->util_avg = cap;
1401 sa->runnable_avg = sa->util_avg;
1411 delta_exec = now - se->exec_start;
1415 se->exec_start = now;
1417 struct task_struct *running = rq->curr;
1420 * task, as w/ proxy-exec they may not be the same.
1422 running->se.exec_start = now;
1423 running->se.sum_exec_runtime += delta_exec;
1432 se->sum_exec_runtime += delta_exec;
1439 __schedstat_set(stats->exec_max,
1440 max(delta_exec, stats->exec_max));
1449 * XXX numbers come from a place the sun don't shine -- probably wants to be SD
1463 return -1;
1478 return (1 + (tol - 1) * mul);
1490 sd = rcu_dereference_sched_domain(cpu_rq(cpu)->sd);
1499 llc = sd->llc_bytes;
1500 footprint = READ_ONCE(mm->sc_stat.footprint);
1514 * 784GB = (1 + (99 - 1) * 256) * 32MB
1545 return !fits_capacity((mm->sc_stat.nr_running_avg * cpu_smt_num_threads),
1554 pref_llc = p->preferred_llc;
1559 rq->nr_llc_running++;
1560 rq->nr_pref_llc_running += pref_llc_queued;
1572 * can cause inconsistent values - checking the
1573 * p->pref_llc_queued in account_llc_dequeue() would
1576 p->pref_llc_queued = pref_llc_queued;
1578 sd = rcu_dereference_all(rq->sd);
1579 if (sd && (unsigned int)pref_llc < sd->llc_max)
1580 sd->llc_counts[pref_llc]++;
1588 pref_llc = p->preferred_llc;
1592 rq->nr_llc_running--;
1593 if (p->pref_llc_queued) {
1594 rq->nr_pref_llc_running--;
1600 p->pref_llc_queued = 0;
1603 sd = rcu_dereference_all(rq->sd);
1604 if (sd && (unsigned int)pref_llc < sd->llc_max) {
1610 * and reset statistics to zero(including sd->llc_counts).
1612 * check for such underflow in sd->llc_counts.
1617 if (sd->llc_counts[pref_llc])
1618 sd->llc_counts[pref_llc]--;
1632 pcpu_sched->runtime = 0;
1634 pcpu_sched->epoch = rq->cpu_epoch;
1635 epoch = rq->cpu_epoch;
1638 raw_spin_lock_init(&mm->sc_stat.lock);
1639 mm->sc_stat.epoch = epoch;
1640 mm->sc_stat.cpu = -1;
1641 mm->sc_stat.next_scan = jiffies;
1642 mm->sc_stat.nr_running_avg = 0;
1643 mm->sc_stat.footprint = 0;
1645 * The update to mm->sc_stat should not be reordered
1649 smp_store_release(&mm->sc_stat.pcpu_sched, _pcpu_sched);
1665 lockdep_assert_held(&rq->cpu_epoch_lock);
1669 long delta = now - rq->cpu_epoch_next;
1672 n = (delta + period - 1) / period;
1673 rq->cpu_epoch += n;
1674 rq->cpu_epoch_next += n * period;
1675 __shr_u64(&rq->cpu_runtime, n);
1678 n = rq->cpu_epoch - pcpu_sched->epoch;
1680 pcpu_sched->epoch += n;
1681 __shr_u64(&pcpu_sched->runtime, n);
1688 guard(raw_spinlock_irqsave)(&rq->cpu_epoch_lock);
1697 return div64_u64(NICE_0_LOAD * pcpu_sched->runtime, rq->cpu_runtime + 1);
1702 int mm_sched_llc = -1, mm_sched_cpu;
1705 return -1;
1707 mm_sched_cpu = READ_ONCE(mm->sc_stat.cpu);
1708 if (mm_sched_cpu != -1) {
1718 * called fairly regularly -- at a higher rate
1719 * than sched_setnuma() at least -- and thus the
1723 p->numa_preferred_nid >= 0 &&
1724 cpu_to_node(mm_sched_cpu) != p->numa_preferred_nid)
1725 mm_sched_llc = -1;
1738 struct mm_struct *mm = p->mm;
1739 int mm_sched_llc = -1;
1745 if (p->sched_class != &fair_sched_class)
1751 if (!mm || !mm->sc_stat.pcpu_sched)
1754 pcpu_sched = per_cpu_ptr(mm->sc_stat.pcpu_sched, cpu_of(rq));
1756 scoped_guard (raw_spinlock, &rq->cpu_epoch_lock) {
1758 pcpu_sched->runtime += delta_exec;
1759 rq->cpu_runtime += delta_exec;
1760 epoch = rq->cpu_epoch;
1767 if ((long)(epoch - READ_ONCE(mm->sc_stat.epoch)) > llc_epoch_affinity_timeout ||
1770 if (READ_ONCE(mm->sc_stat.cpu) != -1)
1771 WRITE_ONCE(mm->sc_stat.cpu, -1);
1777 if (task_running_on_cpu(rq->cpu, p) &&
1778 READ_ONCE(p->preferred_llc) != mm_sched_llc) {
1780 WRITE_ONCE(p->preferred_llc, mm_sched_llc);
1787 struct callback_head *work = &p->cache_work;
1788 struct mm_struct *mm = p->mm;
1794 if (!mm || p->flags & PF_KTHREAD ||
1795 !mm->sc_stat.pcpu_sched)
1798 epoch = rq->cpu_epoch;
1800 if (time_after_eq(mm->sc_stat.epoch, epoch))
1803 guard(raw_spinlock)(&mm->sc_stat.lock);
1805 if (work->next == work) {
1807 WRITE_ONCE(mm->sc_stat.epoch, epoch);
1819 cpu = READ_ONCE(p->mm->sc_stat.cpu);
1820 if (cpu != -1)
1826 * preferred node is per-task rather than per-process. It is possible
1828 * nodes; consequently, the process-wide preferred LLC may bounce
1834 pref_nid = p->numa_preferred_nid;
1842 if (cpu != -1 && !cpumask_test_cpu(cpu, cpus) && nid != NUMA_NO_NODE)
1859 s64 diff = sample - *avg;
1876 int cpu, m_a_cpu = -1, nr_running = 0, curr_cpu;
1880 struct mm_struct *mm = p->mm;
1884 WARN_ON_ONCE(work != &p->cache_work);
1886 work->next = work;
1888 if (p->flags & PF_EXITING)
1891 next_scan = READ_ONCE(mm->sc_stat.next_scan);
1896 if (!try_cmpxchg(&mm->sc_stat.next_scan, &next_scan,
1904 if (READ_ONCE(mm->sc_stat.cpu) != -1)
1905 WRITE_ONCE(mm->sc_stat.cpu, -1);
1922 int m_cpu = -1, i;
1929 per_cpu_ptr(mm->sc_stat.pcpu_sched, i));
1936 cur = rcu_dereference_all(cpu_rq(i)->curr);
1937 if (cur && !(cur->flags & (PF_EXITING | PF_KTHREAD)) &&
1938 cur->mm == mm)
1962 if (llc_id(cpu) == llc_id(READ_ONCE(mm->sc_stat.cpu)))
1980 WRITE_ONCE(mm->sc_stat.cpu, m_a_cpu);
1983 update_avg_scale(&mm->sc_stat.nr_running_avg, nr_running);
1989 struct callback_head *work = &p->cache_work;
1992 work->next = work;
1997 p->preferred_llc = -1;
2012 return -1;
2026 return update_se(rq, &rq->donor->se);
2035 * Note: cfs_rq->curr corresponds to the task picked to
2036 * run (ie: rq->donor.se) which due to proxy-exec may
2038 * (rq->curr.se). This is easy to confuse!
2040 struct sched_entity *curr = cfs_rq->h_curr;
2057 cfs_rq = &rq->cfs;
2059 curr->vruntime += calc_delta_fair(delta_exec, curr);
2066 * - If the task is running on behalf of fair_server, we need
2068 * - Fair task that runs outside of fair_server should account
2072 dl_server_update(&rq->fair_server, delta_exec);
2074 if (cfs_rq->h_nr_queued == 1)
2085 struct sched_entity *se = &rq->donor->se;
2121 * maybe already in the runqueue, the se->statistics.wait_start
2125 if (unlikely(!schedstat_val(stats->wait_start)))
2152 * Task is being enqueued - update stats:
2164 if (se != cfs_rq->h_curr)
2182 if (se != cfs_rq->h_curr)
2190 state = READ_ONCE(tsk->__state);
2192 __schedstat_set(tsk->stats.sleep_start,
2195 __schedstat_set(tsk->stats.block_start,
2201 * We are picking a new current task - update its stats:
2209 se->exec_start = rq_clock_task(rq_of(cfs_rq));
2296 * ->numa_group (see struct task_struct for locking rules).
2300 return rcu_dereference_check(p->numa_group, p == current ||
2301 (lockdep_is_held(__rq_lockp(task_rq(p))) && !READ_ONCE(p->on_cpu)));
2306 return rcu_dereference_protected(p->numa_group, p == current);
2318 * Calculations based on RSS as non-present and empty pages are skipped
2323 rss = get_mm_rss(p->mm);
2356 ng = rcu_dereference_all(p->numa_group);
2361 period *= refcount_read(&ng->refcount);
2386 period *= refcount_read(&ng->refcount);
2398 rq->nr_numa_running += (p->numa_preferred_nid != NUMA_NO_NODE);
2399 rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
2404 rq->nr_numa_running -= (p->numa_preferred_nid != NUMA_NO_NODE);
2405 rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
2411 /* Memory and CPU locality */
2423 ng = rcu_dereference_all(p->numa_group);
2425 gid = ng->gid;
2444 if (!p->numa_faults)
2447 return p->numa_faults[task_faults_idx(NUMA_MEM, nid, 0)] +
2448 p->numa_faults[task_faults_idx(NUMA_MEM, nid, 1)];
2458 return ng->faults[task_faults_idx(NUMA_MEM, nid, 0)] +
2459 ng->faults[task_faults_idx(NUMA_MEM, nid, 1)];
2464 return group->faults[task_faults_idx(NUMA_CPU, nid, 0)] +
2465 group->faults[task_faults_idx(NUMA_CPU, nid, 1)];
2474 faults += ng->faults[task_faults_idx(NUMA_MEM, node, 1)];
2486 faults += ng->faults[task_faults_idx(NUMA_MEM, node, 0)];
2494 * considered part of a numa group's pseudo-interleaving set. Migrations
2501 return group_faults_cpu(ng, nid) * ACTIVE_NODE_FRACTION > ng->max_faults_cpu;
2560 faults *= (max_dist - dist);
2561 faults /= (max_dist - LOCAL_DISTANCE);
2581 if (!p->numa_faults)
2584 total_faults = p->total_numa_faults;
2604 total_faults = ng->total_faults;
2640 pgdat->node_present_pages >> 4);
2641 for (z = pgdat->nr_zones - 1; z >= 0; z--) {
2642 struct zone *zone = pgdat->node_zones + z;
2662 * hint page fault latency = hint page fault time - scan time
2674 return (time - last_time) & PAGE_ACCESS_TIME_MASK;
2691 start = pgdat->nbp_rl_start;
2692 if (now - start > MSEC_PER_SEC &&
2693 cmpxchg(&pgdat->nbp_rl_start, start, now) == start)
2694 pgdat->nbp_rl_nr_cand = nr_cand;
2695 if (nr_cand - pgdat->nbp_rl_nr_cand >= rate_limit)
2711 start = pgdat->nbp_th_start;
2712 if (now - start > th_period &&
2713 cmpxchg(&pgdat->nbp_th_start, start, now) == start) {
2717 diff_cand = nr_cand - pgdat->nbp_th_nr_cand;
2719 th = pgdat->nbp_threshold ? : ref_th;
2721 th = max(th - unit_th, unit_th);
2724 pgdat->nbp_th_nr_cand = nr_cand;
2725 pgdat->nbp_threshold = th;
2755 pgdat->nbp_threshold = 0;
2764 th = pgdat->nbp_threshold ? : def_th;
2772 this_cpupid = cpu_pid_to_cpupid(dst_cpu, current->pid);
2782 * two full passes of the "multi-stage node selection" test that is
2785 if ((p->numa_preferred_nid == NUMA_NO_NODE || p->numa_scan_seq <= 4) &&
2790 * Multi-stage node selection is used in conjunction with a periodic
2791 * migration fault to build a temporal task<->page relation. By using
2792 * a two-stage filter we remove short/unlikely relations.
2796 * page (n_t) (in a given time-span) to a probability.
2804 * act on an unlikely task<->page relation.
2814 /* A shared fault, but p->numa_group has not been set up yet. */
2831 * --------------- * - > ---------------
2893 if ((ns->nr_running > ns->weight) &&
2894 (((ns->compute_capacity * 100) < (ns->util * imbalance_pct)) ||
2895 ((ns->compute_capacity * imbalance_pct) < (ns->runnable * 100))))
2898 if ((ns->nr_running < ns->weight) ||
2899 (((ns->compute_capacity * 100) > (ns->util * imbalance_pct)) &&
2900 ((ns->compute_capacity * imbalance_pct) > (ns->runnable * 100))))
2934 int cpu, idle_core = -1;
2937 ns->idle_cpu = -1;
2943 ns->load += cpu_load(rq);
2944 ns->runnable += cpu_runnable(rq);
2945 ns->util += cpu_util_cfs(cpu);
2946 ns->nr_running += rq->cfs.h_nr_runnable;
2947 ns->compute_capacity += capacity_of(cpu);
2949 if (find_idle && idle_core < 0 && !rq->nr_running && idle_cpu(cpu)) {
2950 if (READ_ONCE(rq->numa_migrate_on) ||
2951 !cpumask_test_cpu(cpu, env->p->cpus_ptr))
2954 if (ns->idle_cpu == -1)
2955 ns->idle_cpu = cpu;
2962 ns->weight = cpumask_weight(cpumask_of_node(nid));
2964 ns->node_type = numa_classify(env->imbalance_pct, ns);
2967 ns->idle_cpu = idle_core;
2973 struct rq *rq = cpu_rq(env->dst_cpu);
2975 /* Check if run-queue part of active NUMA balance. */
2976 if (env->best_cpu != env->dst_cpu && xchg(&rq->numa_migrate_on, 1)) {
2978 int start = env->dst_cpu;
2981 for_each_cpu_wrap(cpu, cpumask_of_node(env->dst_nid), start + 1) {
2982 if (cpu == env->best_cpu || !idle_cpu(cpu) ||
2983 !cpumask_test_cpu(cpu, env->p->cpus_ptr)) {
2987 env->dst_cpu = cpu;
2988 rq = cpu_rq(env->dst_cpu);
2989 if (!xchg(&rq->numa_migrate_on, 1))
2999 * Clear previous best_cpu/rq numa-migrate flag, since task now
3002 if (env->best_cpu != -1 && env->best_cpu != env->dst_cpu) {
3003 rq = cpu_rq(env->best_cpu);
3004 WRITE_ONCE(rq->numa_migrate_on, 0);
3007 if (env->best_task)
3008 put_task_struct(env->best_task);
3012 env->best_task = p;
3013 env->best_imp = imp;
3014 env->best_cpu = env->dst_cpu;
3028 * ------------ vs ---------
3031 src_capacity = env->src_stats.compute_capacity;
3032 dst_capacity = env->dst_stats.compute_capacity;
3034 imb = abs(dst_load * src_capacity - src_load * dst_capacity);
3036 orig_src_load = env->src_stats.load;
3037 orig_dst_load = env->dst_stats.load;
3039 old_imb = abs(orig_dst_load * src_capacity - orig_src_load * dst_capacity);
3061 struct numa_group *cur_ng, *p_ng = deref_curr_numa_group(env->p);
3062 struct rq *dst_rq = cpu_rq(env->dst_cpu);
3066 int dist = env->dist;
3071 if (READ_ONCE(dst_rq->numa_migrate_on))
3075 cur = rcu_dereference_all(dst_rq->curr);
3076 if (cur && ((cur->flags & (PF_EXITING | PF_KTHREAD)) ||
3077 !cur->mm))
3082 * end try selecting ourselves (current == env->p) as a swap candidate.
3084 if (cur == env->p) {
3090 if (maymove && moveimp >= env->best_imp)
3097 if (!cpumask_test_cpu(env->src_cpu, cur->cpus_ptr))
3104 if (env->best_task &&
3105 env->best_task->numa_preferred_nid == env->src_nid &&
3106 cur->numa_preferred_nid != env->src_nid) {
3120 cur_ng = rcu_dereference_all(cur->numa_group);
3128 if (env->dst_stats.node_type == node_has_spare)
3131 imp = taskimp + task_weight(cur, env->src_nid, dist) -
3132 task_weight(cur, env->dst_nid, dist);
3138 imp -= imp / 16;
3145 imp += group_weight(cur, env->src_nid, dist) -
3146 group_weight(cur, env->dst_nid, dist);
3148 imp += task_weight(cur, env->src_nid, dist) -
3149 task_weight(cur, env->dst_nid, dist);
3153 if (cur->numa_preferred_nid == env->dst_nid)
3154 imp -= imp / 16;
3162 if (cur->numa_preferred_nid == env->src_nid)
3165 if (maymove && moveimp > imp && moveimp > env->best_imp) {
3175 if (env->best_task && cur->numa_preferred_nid == env->src_nid &&
3176 env->best_task->numa_preferred_nid != env->src_nid) {
3186 if (imp < SMALLIMP || imp <= env->best_imp + SMALLIMP / 2)
3192 load = task_h_load(env->p) - task_h_load(cur);
3196 dst_load = env->dst_stats.load + load;
3197 src_load = env->src_stats.load - load;
3205 int cpu = env->dst_stats.idle_cpu;
3209 cpu = env->dst_cpu;
3215 if (!idle_cpu(cpu) && env->best_cpu >= 0 &&
3216 idle_cpu(env->best_cpu)) {
3217 cpu = env->best_cpu;
3220 env->dst_cpu = cpu;
3230 if (maymove && !cur && env->best_cpu >= 0 && idle_cpu(env->best_cpu))
3237 if (!maymove && env->best_task &&
3238 env->best_task->numa_preferred_nid == env->src_nid) {
3257 if (env->dst_stats.node_type == node_has_spare) {
3267 src_running = env->src_stats.nr_running - 1;
3268 dst_running = env->dst_stats.nr_running + 1;
3269 imbalance = max(0, dst_running - src_running);
3271 env->imb_numa_nr);
3276 if (env->dst_stats.idle_cpu >= 0) {
3277 env->dst_cpu = env->dst_stats.idle_cpu;
3285 * If the improvement from just moving env->p direction is better
3288 load = task_h_load(env->p);
3289 dst_load = env->dst_stats.load + load;
3290 src_load = env->src_stats.load - load;
3295 for_each_cpu_and(cpu, cpumask_of_node(env->dst_nid), env->p->cpus_ptr) {
3296 env->dst_cpu = cpu;
3314 .best_cpu = -1,
3328 * random movement of tasks -- counter the numa conditions we're trying
3334 env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
3335 env.imb_numa_nr = sd->imb_numa_nr;
3347 return -EINVAL;
3350 env.dst_nid = p->numa_preferred_nid;
3355 taskimp = task_weight(p, env.dst_nid, dist) - taskweight;
3356 groupimp = group_weight(p, env.dst_nid, dist) - groupweight;
3364 * - there is no space available on the preferred_nid
3365 * - the task is part of a numa_group that is interleaved across
3370 if (env.best_cpu == -1 || (ng && ng->active_nodes > 1)) {
3372 if (nid == env.src_nid || nid == p->numa_preferred_nid)
3383 taskimp = task_weight(p, nid, dist) - taskweight;
3384 groupimp = group_weight(p, nid, dist) - groupweight;
3404 if (env.best_cpu == -1)
3409 if (nid != p->numa_preferred_nid)
3414 if (env.best_cpu == -1) {
3415 trace_sched_stick_numa(p, env.src_cpu, NULL, -1);
3416 return -EAGAIN;
3422 WRITE_ONCE(best_rq->numa_migrate_on, 0);
3429 WRITE_ONCE(best_rq->numa_migrate_on, 0);
3443 if (unlikely(p->numa_preferred_nid == NUMA_NO_NODE || !p->numa_faults))
3447 interval = min(interval, msecs_to_jiffies(p->numa_scan_period) / 16);
3448 p->numa_migrate_retry = jiffies + interval;
3451 if (task_node(p) == p->numa_preferred_nid)
3481 numa_group->max_faults_cpu = max_faults;
3482 numa_group->active_nodes = active_nodes;
3508 unsigned long remote = p->numa_faults_locality[0];
3509 unsigned long local = p->numa_faults_locality[1];
3518 if (local + shared == 0 || p->numa_faults_locality[2]) {
3519 p->numa_scan_period = min(p->numa_scan_period_max,
3520 p->numa_scan_period << 1);
3522 p->mm->numa_next_scan = jiffies +
3523 msecs_to_jiffies(p->numa_scan_period);
3534 period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
3543 int slot = ps_ratio - NUMA_PERIOD_THRESHOLD;
3553 int slot = lr_ratio - NUMA_PERIOD_THRESHOLD;
3559 * Private memory faults exceed (SLOTS-THRESHOLD)/SLOTS,
3564 diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
3567 p->numa_scan_period = clamp(p->numa_scan_period + diff,
3569 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
3576 * from the dozens-of-seconds NUMA balancing period. Use the scheduler
3583 now = p->se.exec_start;
3584 runtime = p->se.sum_exec_runtime;
3586 if (p->last_task_numa_placement) {
3587 delta = runtime - p->last_sum_exec_runtime;
3588 *period = now - p->last_task_numa_placement;
3594 delta = p->se.avg.load_sum;
3598 p->last_sum_exec_runtime = runtime;
3599 p->last_task_numa_placement = now;
3649 for (dist = sched_max_numa_distance; dist > LOCAL_DISTANCE; dist--) {
3705 * The p->mm->numa_scan_seq field gets updated without
3709 seq = READ_ONCE(p->mm->numa_scan_seq);
3710 if (p->numa_scan_seq == seq)
3712 p->numa_scan_seq = seq;
3713 p->numa_scan_period_max = task_scan_max(p);
3715 total_faults = p->numa_faults_locality[0] +
3716 p->numa_faults_locality[1];
3722 group_lock = &ng->lock;
3742 diff = p->numa_faults[membuf_idx] - p->numa_faults[mem_idx] / 2;
3743 fault_types[priv] += p->numa_faults[membuf_idx];
3744 p->numa_faults[membuf_idx] = 0;
3750 * little over-all impact on throughput, and thus their
3754 f_weight = (f_weight * p->numa_faults[cpubuf_idx]) /
3756 f_diff = f_weight - p->numa_faults[cpu_idx] / 2;
3757 p->numa_faults[cpubuf_idx] = 0;
3759 p->numa_faults[mem_idx] += diff;
3760 p->numa_faults[cpu_idx] += f_diff;
3761 faults += p->numa_faults[mem_idx];
3762 p->total_numa_faults += diff;
3768 * nid and priv in a specific region because it
3771 ng->faults[mem_idx] += diff;
3772 ng->faults[cpu_idx] += f_diff;
3773 ng->total_faults += diff;
3774 group_faults += ng->faults[mem_idx];
3778 * Per task p->numa_faults[mem_idx] converges,
3780 * converges too - Given the number of threads,
3787 * be subtracted from the mm->sc_stat.footprint, otherwise
3788 * the mm->sc_stat.footprint will not converge:
3790 * in mm->sc_stat.footprint. See exit_mm().
3797 new_fp = (long)READ_ONCE(p->mm->sc_stat.footprint) + diff;
3798 WRITE_ONCE(p->mm->sc_stat.footprint,
3814 /* Cannot migrate task to CPU-less node */
3825 if (max_nid != p->numa_preferred_nid)
3834 return refcount_inc_not_zero(&grp->refcount);
3839 if (refcount_dec_and_test(&grp->refcount))
3861 refcount_set(&grp->refcount, 1);
3862 grp->active_nodes = 1;
3863 grp->max_faults_cpu = 0;
3864 spin_lock_init(&grp->lock);
3865 grp->gid = p->pid;
3868 grp->faults[i] = p->numa_faults[i];
3870 grp->total_faults = p->total_numa_faults;
3872 grp->nr_tasks++;
3873 rcu_assign_pointer(p->numa_group, grp);
3877 tsk = READ_ONCE(cpu_rq(cpu)->curr);
3882 grp = rcu_dereference_all(tsk->numa_group);
3894 if (my_grp->nr_tasks > grp->nr_tasks)
3898 * Tie-break on the grp address.
3900 if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)
3904 if (tsk->mm == current->mm)
3923 double_lock_irq(&my_grp->lock, &grp->lock);
3926 my_grp->faults[i] -= p->numa_faults[i];
3927 grp->faults[i] += p->numa_faults[i];
3929 my_grp->total_faults -= p->total_numa_faults;
3930 grp->total_faults += p->total_numa_faults;
3932 my_grp->nr_tasks--;
3933 grp->nr_tasks++;
3935 spin_unlock(&my_grp->lock);
3936 spin_unlock_irq(&grp->lock);
3938 rcu_assign_pointer(p->numa_group, grp);
3953 * reset the data back to default state without freeing ->numa_faults.
3958 struct numa_group *grp = rcu_dereference_raw(p->numa_group);
3959 unsigned long *numa_faults = p->numa_faults;
3967 spin_lock_irqsave(&grp->lock, flags);
3969 grp->faults[i] -= p->numa_faults[i];
3970 grp->total_faults -= p->total_numa_faults;
3972 grp->nr_tasks--;
3973 spin_unlock_irqrestore(&grp->lock, flags);
3974 RCU_INIT_POINTER(p->numa_group, NULL);
3979 p->numa_faults = NULL;
3982 p->total_numa_faults = 0;
4004 if (!p->mm)
4016 /* Allocate buffer to track faults on a per-node basis */
4017 if (unlikely(!p->numa_faults)) {
4018 int size = sizeof(*p->numa_faults) *
4021 p->numa_faults = kzalloc(size, GFP_KERNEL|__GFP_NOWARN);
4022 if (!p->numa_faults)
4025 p->total_numa_faults = 0;
4026 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
4033 if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
4048 if (!priv && !local && ng && ng->active_nodes > 1 &&
4057 if (time_after(jiffies, p->numa_migrate_retry)) {
4063 p->numa_pages_migrated += pages;
4065 p->numa_faults_locality[2] += pages;
4067 p->numa_faults[task_faults_idx(NUMA_MEMBUF, mem_node, priv)] += pages;
4068 p->numa_faults[task_faults_idx(NUMA_CPUBUF, cpu_node, priv)] += pages;
4069 p->numa_faults_locality[local] += pages;
4076 * p->mm->numa_scan_seq is written to without exclusive access
4082 WRITE_ONCE(p->mm->numa_scan_seq, READ_ONCE(p->mm->numa_scan_seq) + 1);
4083 p->mm->numa_scan_offset = 0;
4095 if ((READ_ONCE(current->mm->numa_scan_seq) - vma->numab_state->start_scan_seq) < 2)
4098 pids = vma->numab_state->pids_active[0] | vma->numab_state->pids_active[1];
4099 if (test_bit(hash_32(current->pid, ilog2(BITS_PER_LONG)), &pids))
4104 * some VMAs may never be scanned in multi-threaded applications:
4106 if (mm->numa_scan_offset > vma->vm_start) {
4116 if (READ_ONCE(mm->numa_scan_seq) >
4117 (vma->numab_state->prev_scan_seq + get_nr_threads(current)))
4133 struct mm_struct *mm = p->mm;
4134 u64 runtime = p->se.sum_exec_runtime;
4145 work->next = work;
4149 * NOTE: make sure not to dereference p->mm before this check,
4151 * without p->mm even though we still had it when we enqueued this
4154 if (p->flags & PF_EXITING)
4166 if (!mm->numa_next_scan) {
4167 mm->numa_next_scan = now +
4174 migrate = mm->numa_next_scan;
4178 if (p->numa_scan_period == 0) {
4179 p->numa_scan_period_max = task_scan_max(p);
4180 p->numa_scan_period = task_scan_start(p);
4183 next_scan = now + msecs_to_jiffies(p->numa_scan_period);
4184 if (!try_cmpxchg(&mm->numa_next_scan, &migrate, next_scan))
4191 p->node_stamp += 2 * TICK_NSEC;
4194 pages <<= 20 - PAGE_SHIFT; /* MB in pages */
4211 start = mm->numa_scan_offset;
4223 is_vm_hugetlb_page(vma) || (vma->vm_flags & VM_MIXEDMAP)) {
4231 * hinting faults in read-only file-backed mappings or the vDSO
4234 if (!vma->vm_mm ||
4235 (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ))) {
4249 /* Initialise new per-VMA NUMAB state. */
4250 if (!vma->numab_state) {
4257 if (cmpxchg(&vma->numab_state, NULL, ptr)) {
4262 vma->numab_state->start_scan_seq = mm->numa_scan_seq;
4264 vma->numab_state->next_scan = now +
4268 vma->numab_state->pids_active_reset = vma->numab_state->next_scan +
4276 vma->numab_state->prev_scan_seq = mm->numa_scan_seq - 1;
4283 if (mm->numa_scan_seq && time_before(jiffies,
4284 vma->numab_state->next_scan)) {
4290 if (mm->numa_scan_seq &&
4291 time_after(jiffies, vma->numab_state->pids_active_reset)) {
4292 vma->numab_state->pids_active_reset = vma->numab_state->pids_active_reset +
4294 vma->numab_state->pids_active[0] = READ_ONCE(vma->numab_state->pids_active[1]);
4295 vma->numab_state->pids_active[1] = 0;
4299 if (vma->numab_state->prev_scan_seq == mm->numa_scan_seq) {
4300 mm->numa_scan_offset = vma->vm_end;
4316 start = max(start, vma->vm_start);
4318 end = min(end, vma->vm_end);
4324 * is not already PTE-numa. If the VMA contains
4330 pages -= (end - start) >> PAGE_SHIFT;
4331 virtpages -= (end - start) >> PAGE_SHIFT;
4338 } while (end != vma->vm_end);
4341 vma->numab_state->prev_scan_seq = mm->numa_scan_seq;
4369 mm->numa_scan_offset = start;
4380 if (unlikely(p->se.sum_exec_runtime != runtime)) {
4381 u64 diff = p->se.sum_exec_runtime - runtime;
4382 p->node_stamp += 32 * diff;
4389 struct mm_struct *mm = p->mm;
4392 mm_users = atomic_read(&mm->mm_users);
4394 mm->numa_next_scan = jiffies + msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
4395 mm->numa_scan_seq = 0;
4398 p->node_stamp = 0;
4399 p->numa_scan_seq = mm ? mm->numa_scan_seq : 0;
4400 p->numa_scan_period = sysctl_numa_balancing_scan_delay;
4401 p->numa_migrate_retry = 0;
4403 p->numa_work.next = &p->numa_work;
4404 p->numa_faults = NULL;
4405 p->numa_pages_migrated = 0;
4406 p->total_numa_faults = 0;
4407 RCU_INIT_POINTER(p->numa_group, NULL);
4408 p->last_task_numa_placement = 0;
4409 p->last_sum_exec_runtime = 0;
4411 init_task_work(&p->numa_work, task_numa_work);
4415 p->numa_preferred_nid = NUMA_NO_NODE;
4427 current->numa_scan_period * mm_users * NSEC_PER_MSEC);
4429 p->node_stamp = delay;
4438 struct callback_head *work = &curr->numa_work;
4444 if (!curr->mm || (curr->flags & (PF_EXITING | PF_KTHREAD)) || work->next != work)
4453 now = curr->se.sum_exec_runtime;
4454 period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
4456 if (now > curr->node_stamp + period) {
4457 if (!curr->node_stamp)
4458 curr->numa_scan_period = task_scan_start(curr);
4459 curr->node_stamp += period;
4461 if (!time_before(jiffies, curr->mm->numa_next_scan))
4474 if (!p->mm || !p->numa_faults || (p->flags & PF_EXITING))
4483 * is pulled cross-node due to wakeups or load balancing.
4485 if (p->numa_scan_seq) {
4491 if (dst_nid == p->numa_preferred_nid ||
4492 (p->numa_preferred_nid != NUMA_NO_NODE &&
4493 src_nid != p->numa_preferred_nid))
4497 p->numa_scan_period = task_scan_start(p);
4524 update_load_add(&cfs_rq->load, se->load.weight);
4531 list_add(&se->group_node, &rq->cfs_tasks);
4533 cfs_rq->nr_queued++;
4540 update_load_sub(&cfs_rq->load, se->load.weight);
4547 list_del_init(&se->group_node);
4549 cfs_rq->nr_queued--;
4555 * Explicitly do a load-store to ensure the intermediate value never hits
4575 * A variant of sub_positive(), which does not use explicit load-store
4580 *ptr -= min_t(typeof(*ptr), *ptr, _val); \
4585 * Because of rounding, se->util_sum might ends up being +1 more than
4586 * cfs->util_sum. Although this is not a problem by itself, detaching
4588 * util_avg (~1ms) can make cfs->util_sum becoming null whereas
4597 add_positive(&(sa)->name##_avg, delta_avg); \
4598 add_positive(&(sa)->name##_sum, delta_sum); \
4599 (sa)->name##_sum = max_t(typeof((sa)->name##_sum), \
4600 (sa)->name##_sum, \
4601 (sa)->name##_avg * PELT_MIN_DIVIDER); \
4607 __update_sa(&cfs_rq->avg, load, se->avg.load_avg,
4608 se_weight(se) * se->avg.load_sum);
4614 __update_sa(&cfs_rq->avg, load, -se->avg.load_avg,
4615 se_weight(se) * -se->avg.load_sum);
4621 long old_weight = se->h_load.weight;
4625 * --------
4628 * adjusted if re-weight at !0-lag point.
4631 * re-weight without changing vruntime at !0-lag point.
4633 * Weight VRuntime Avg-VRuntime
4637 * Since lag needs to be preserved through re-weight:
4639 * lag = (V - v)*w = (V'- v')*w', where v = v'
4640 * ==> V' = (V - v)*w/w' + v (1)
4645 * V' = (WV + w'v - wv) / (W + w' - w) (2)
4649 * (WV + w'v - wv) / (W + w' - w) = (V - v)*w/w' + v
4650 * ==> (WV-Wv+Wv+w'v-wv)/(W+w'-w) = (V - v)*w/w' + v
4651 * ==> (WV - Wv)/(W + w' - w) + v = (V - v)*w/w' + v
4652 * ==> (V - v)*W/(W + w' - w) = (V - v)*w/w' (3)
4654 * Since we are doing at !0-lag point which means V != v, we
4657 * ==> W / (W + w' - w) = w / w'
4658 * ==> Ww' = Ww + ww' - ww
4659 * ==> W * (w' - w) = w * (w' - w)
4660 * ==> W = w (re-weight indicates w' != w)
4664 * average vruntime @V, which means we will always re-weight
4665 * at 0-lag point, thus breach assumption. Proof completed.
4668 * COROLLARY #2: Re-weight does NOT affect weighted average
4673 * (V - v)*w = (V' - v')*w'
4674 * ==> v' = V' - (V - v)*w/w' (4)
4678 * V' = (WV - wv + w'v') / (W - w + w')
4679 * = (WV - wv + w'(V' - (V - v)w/w')) / (W - w + w')
4680 * = (WV - wv + w'V' - Vw + wv) / (W - w + w')
4681 * = (WV + w'V' - Vw) / (W - w + w')
4683 * ==> V'*(W - w + w') = WV + w'V' - Vw
4684 * ==> V' * (W - w) = (W - w) * V (5)
4687 * always occurs at 0-lag point, so V won't change. Or else
4692 * So according to corollary #1 & #2, the effect of re-weight
4695 * v' = V' - (V - v) * w / w' (4)
4696 * = V - (V - v) * w / w'
4697 * = V - vl * w / w'
4698 * = V - vl'
4700 se->vlag = div64_long(se->vlag * old_weight, weight);
4704 * --------
4709 * d' = v' + (d - v)*w/w'
4710 * = V' - (V - v)*w/w' + (d - v)*w/w'
4711 * = V - (V - v)*w/w' + (d - v)*w/w'
4712 * = V + (d - V)*w/w'
4714 if (se->rel_deadline)
4715 se->deadline = div64_long(se->deadline * old_weight, weight);
4718 se->vprot = div64_long(se->vprot * old_weight, weight);
4724 bool curr = cfs_rq->curr == se;
4728 if (se->h_load.weight == weight)
4733 se->vlag = entity_lag(cfs_rq, se, avruntime);
4734 se->deadline -= avruntime;
4735 se->rel_deadline = 1;
4737 se->vprot -= avruntime;
4741 cfs_rq->h_nr_queued--;
4748 update_load_set(&se->h_load, weight);
4752 se->vprot += avruntime;
4753 se->deadline += avruntime;
4754 se->rel_deadline = 0;
4755 se->vruntime = avruntime - se->vlag;
4759 cfs_rq->h_nr_queued++;
4766 if (se->load.weight == weight)
4769 if (se->on_rq) {
4771 update_load_sub(&cfs_rq->load, se->load.weight);
4775 update_load_set(&se->load, weight);
4778 u32 divider = get_pelt_divider(&se->avg);
4779 se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
4784 if (se->on_rq)
4785 update_load_add(&cfs_rq->load, se->load.weight);
4797 weight *= se->load.weight;
4799 weight /= cfs_rq->load.weight;
4809 struct sched_entity *se = &p->se;
4812 if (se->on_rq)
4815 reweight_entity(cfs_rq_of(se), se, lw->weight);
4816 se->load.inv_weight = lw->inv_weight;
4818 if (!se->on_rq)
4824 reweight_eevdf(&rq->cfs, &p->se, weight, p->se.on_rq);
4837 * tg->weight * grq->load.weight
4838 * ge->load.weight = ----------------------------- (1)
4839 * \Sum grq->load.weight
4847 * grq->load.weight -> grq->avg.load_avg (2)
4851 * tg->weight * grq->avg.load_avg
4852 * ge->load.weight = ------------------------------ (3)
4853 * tg->load_avg
4855 * Where: tg->load_avg ~= \Sum grq->avg.load_avg
4859 * The problem with it is that because the average is slow -- it was designed
4860 * to be exactly that of course -- this leads to transients in boundary
4861 * conditions. In specific, the case where the group was idle and we start the
4862 * one task. It takes time for our CPU's grq->avg.load_avg to build up,
4867 * tg->weight * grq->load.weight
4868 * ge->load.weight = ----------------------------- = tg->weight (4)
4869 * grp->load.weight
4876 * ge->load.weight =
4878 * tg->weight * grq->load.weight
4879 * --------------------------------------------------- (5)
4880 * tg->load_avg - grq->avg.load_avg + grq->load.weight
4882 * But because grq->load.weight can drop to 0, resulting in a divide by zero,
4883 * we need to use grq->avg.load_avg as its lower bound, which then gives:
4886 * tg->weight * grq->load.weight
4887 * ge->load.weight = ----------------------------- (6)
4892 * tg_load_avg' = tg->load_avg - grq->avg.load_avg +
4893 * max(grq->load.weight, grq->avg.load_avg)
4897 * overestimates the ge->load.weight and therefore:
4899 * \Sum ge->load.weight >= tg->weight
4905 struct task_group *tg = cfs_rq->tg;
4908 load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);
4910 tg_weight = atomic_long_read(&tg->load_avg);
4913 tg_weight -= cfs_rq->tg_load_avg_contrib;
4921 * MIN_SHARES has to be unscaled here to support per-CPU partitioning
4922 * of a group with small tg->shares value. It is a floor value which is
4926 * E.g. on 64-bit for a group with tg->shares of scale_load(15)=15*1024
4927 * on an 8-core system with 8 tasks each runnable on one CPU shares has
4940 struct cgroup *cgrp = tg->css.cgroup;
4955 return max(1, atomic_long_read(&tg->runnable_avg) >> SCHED_CAPACITY_SHIFT);
4959 * Func: fraction(nr_tasks * tg->shares)
4961 * Scale tg->shares by the number of tasks.
4965 struct task_group *tg = cfs_rq->tg;
4967 long tg_shares = READ_ONCE(tg->shares);
4972 * Func: min(fraction(nr_cpus * tg->shares), nice -20)
4974 * Scale tg->shares by the maximal number of CPUs; but clip the max shares at
4975 * nice -20, otherwise a single spinner on a 512 CPU machine would result in
4980 struct task_group *tg = cfs_rq->tg;
4982 long tg_shares = READ_ONCE(tg->shares);
4988 * Func: fraction(nr * tg->shares); nr = min(nr_tasks, nr_cpus)
4995 struct task_group *tg = cfs_rq->tg;
4997 long tg_shares = READ_ONCE(tg->shares);
5002 * Func: fraction(tg->shares)
5008 struct task_group *tg = cfs_rq->tg;
5009 long tg_shares = READ_ONCE(tg->shares);
5018 struct task_group *tg = cfs_rq->tg;
5019 return READ_ONCE(tg->shares);
5061 if (!gcfs_rq || !gcfs_rq->load.weight)
5078 if (&rq->cfs == cfs_rq) {
5088 * As is, the util number is not freq-invariant (we'd have to
5099 if (sa->load_sum)
5102 if (sa->util_sum)
5105 if (sa->runnable_sum)
5113 WARN_ON_ONCE(sa->load_avg ||
5114 sa->util_avg ||
5115 sa->runnable_avg);
5122 return u64_u32_load_copy(cfs_rq->avg.last_update_time,
5123 cfs_rq->last_update_time_copy);
5129 * bottom-up, we only have to test whether the cfs_rq before us on the list
5140 if (cfs_rq->on_list) {
5141 prev = cfs_rq->leaf_cfs_rq_list.prev;
5143 prev = rq->tmp_alone_branch;
5146 if (prev == &rq->leaf_cfs_rq_list)
5151 return (prev_cfs_rq->tg->parent == cfs_rq->tg);
5156 if (cfs_rq->load.weight)
5159 if (!load_avg_is_decayed(&cfs_rq->avg))
5165 if (cfs_rq->tg_load_avg_contrib)
5172 * update_tg_load_avg - update the tg's load avg
5175 * This function 'ensures': tg->load_avg := \Sum tg->cfs_rq[]->avg.load.
5176 * However, because tg->load_avg is a global value there are performance
5193 if (cfs_rq->tg == &root_task_group)
5201 * For migration heavy workloads, access to tg->load_avg can be
5205 if (now - cfs_rq->last_update_tg_load_avg < NSEC_PER_MSEC)
5208 dl = cfs_rq->avg.load_avg - cfs_rq->tg_load_avg_contrib;
5209 dr = cfs_rq->avg.runnable_avg - cfs_rq->tg_runnable_avg_contrib;
5210 if (abs(dl) > cfs_rq->tg_load_avg_contrib / 64 ||
5211 abs(dr) > cfs_rq->tg_runnable_avg_contrib / 64) {
5212 atomic_long_add(dl, &cfs_rq->tg->load_avg);
5213 atomic_long_add(dr, &cfs_rq->tg->runnable_avg);
5214 cfs_rq->tg_load_avg_contrib = cfs_rq->avg.load_avg;
5215 cfs_rq->tg_runnable_avg_contrib = cfs_rq->avg.runnable_avg;
5216 cfs_rq->last_update_tg_load_avg = now;
5228 if (cfs_rq->tg == &root_task_group)
5232 dl = 0 - cfs_rq->tg_load_avg_contrib;
5233 dr = 0 - cfs_rq->tg_runnable_avg_contrib;
5234 atomic_long_add(dl, &cfs_rq->tg->load_avg);
5235 atomic_long_add(dr, &cfs_rq->tg->runnable_avg);
5236 cfs_rq->tg_load_avg_contrib = 0;
5237 cfs_rq->tg_runnable_avg_contrib = 0;
5238 cfs_rq->last_update_tg_load_avg = now;
5268 * caller only guarantees p->pi_lock is held; no other assumptions,
5269 * including the state of rq->lock, should be made.
5283 * getting what current time is, so simply throw away the out-of-date
5287 if (!(se->avg.last_update_time && prev))
5294 se->avg.last_update_time = n_last_update_time;
5302 * ge->avg == grq->avg (1)
5313 * ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg (2)
5318 * grq->avg.load_avg = grq->load.weight * grq->avg.runnable_avg (3)
5322 * ge->avg.runnable_avg == grq->avg.runnable_avg
5326 * ge->load.weight * grq->avg.load_avg
5327 * ge->avg.load_avg = ----------------------------------- (4)
5328 * grq->load.weight
5341 * Another reason this doesn't work is that runnable isn't a 0-sum entity.
5352 * ge->avg.running_sum <= ge->avg.runnable_sum <= LOAD_AVG_MAX
5359 * grq->avg.runnable_sum = grq->avg.load_sum / grq->load.weight
5367 long delta_sum, delta_avg = gcfs_rq->avg.util_avg - se->avg.util_avg;
5375 * cfs_rq->avg.period_contrib can be used for both cfs_rq and se.
5378 divider = get_pelt_divider(&cfs_rq->avg);
5381 se->avg.util_avg = gcfs_rq->avg.util_avg;
5382 new_sum = se->avg.util_avg * divider;
5383 delta_sum = (long)new_sum - (long)se->avg.util_sum;
5384 se->avg.util_sum = new_sum;
5387 __update_sa(&cfs_rq->avg, util, delta_avg, delta_sum);
5393 long delta_sum, delta_avg = gcfs_rq->avg.runnable_avg - se->avg.runnable_avg;
5402 * cfs_rq->avg.period_contrib can be used for both cfs_rq and se.
5405 divider = get_pelt_divider(&cfs_rq->avg);
5408 se->avg.runnable_avg = gcfs_rq->avg.runnable_avg;
5409 new_sum = (u64)se->avg.runnable_avg * divider;
5410 delta_sum = (long)new_sum - (long)se->avg.runnable_sum;
5411 se->avg.runnable_sum = new_sum;
5414 __update_sa(&cfs_rq->avg, runnable, delta_avg, delta_sum);
5420 long delta_avg, running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
5429 gcfs_rq->prop_runnable_sum = 0;
5432 * cfs_rq->avg.period_contrib can be used for both cfs_rq and se.
5435 divider = get_pelt_divider(&cfs_rq->avg);
5442 runnable_sum += se->avg.load_sum;
5449 if (scale_load_down(gcfs_rq->load.weight)) {
5450 load_sum = div_u64(gcfs_rq->avg.load_sum,
5451 scale_load_down(gcfs_rq->load.weight));
5455 runnable_sum = min(se->avg.load_sum, load_sum);
5464 running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT;
5470 delta_avg = load_avg - se->avg.load_avg;
5474 delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
5476 se->avg.load_sum = runnable_sum;
5477 se->avg.load_avg = load_avg;
5478 __update_sa(&cfs_rq->avg, load, delta_avg, delta_sum);
5483 cfs_rq->propagate = 1;
5484 cfs_rq->prop_runnable_sum += runnable_sum;
5496 if (!gcfs_rq->propagate)
5499 gcfs_rq->propagate = 0;
5503 add_tg_cfs_propagate(cfs_rq, gcfs_rq->prop_runnable_sum);
5527 if (se->avg.load_avg || se->avg.util_avg)
5534 if (gcfs_rq->propagate)
5568 if (load_avg_is_decayed(&se->avg))
5575 is_idle = is_idle_task(rcu_dereference_all(rq->curr));
5592 * - cfs->throttled_clock_pelt_time@cfs_rq_idle
5595 * = rq_clock_pelt()@rq_idle - rq_clock_pelt()@cfs_rq_idle
5598 * = sched_clock_cpu() - rq_clock()@rq_idle
5602 * now = rq_clock_pelt()@rq_idle - cfs->throttled_clock_pelt_time +
5603 * sched_clock_cpu() - rq_clock()@rq_idle
5605 * rq_clock_pelt()@rq_idle is rq->clock_pelt_idle
5606 * rq_clock()@rq_idle is rq->clock_idle
5607 * cfs->throttled_clock_pelt_time@cfs_rq_idle
5608 * is cfs_rq->throttled_pelt_idle
5612 throttled = u64_u32_load(cfs_rq->throttled_pelt_idle);
5617 now = u64_u32_load(rq->clock_pelt_idle);
5627 now -= throttled;
5630 * cfs_rq->avg.last_update_time is more recent than our
5635 now += sched_clock_cpu(cpu_of(rq)) - u64_u32_load(rq->clock_idle);
5644 * update_cfs_rq_load_avg - update the cfs_rq's load/util averages
5651 * cfs_rq->avg is used for task_h_load() and update_cfs_group() for example.
5655 * Since both these conditions indicate a changed cfs_rq->avg.load we should
5662 struct sched_avg *sa = &cfs_rq->avg;
5665 if (cfs_rq->removed.nr) {
5667 u32 divider = get_pelt_divider(&cfs_rq->avg);
5669 raw_spin_lock(&cfs_rq->removed.lock);
5670 swap(cfs_rq->removed.util_avg, removed_util);
5671 swap(cfs_rq->removed.load_avg, removed_load);
5672 swap(cfs_rq->removed.runnable_avg, removed_runnable);
5673 cfs_rq->removed.nr = 0;
5674 raw_spin_unlock(&cfs_rq->removed.lock);
5677 __update_sa(sa, load, -r, -r*divider);
5680 __update_sa(sa, util, -r, -r*divider);
5683 __update_sa(sa, runnable, -r, -r*divider);
5690 -(long)(removed_runnable * divider) >> SCHED_CAPACITY_SHIFT);
5696 u64_u32_store_copy(sa->last_update_time,
5697 cfs_rq->last_update_time_copy,
5698 sa->last_update_time);
5703 * attach_entity_load_avg - attach this entity to its cfs_rq load avg
5708 * cfs_rq->avg.last_update_time being current.
5713 * cfs_rq->avg.period_contrib can be used for both cfs_rq and se.
5716 u32 divider = get_pelt_divider(&cfs_rq->avg);
5725 se->avg.last_update_time = cfs_rq->avg.last_update_time;
5726 se->avg.period_contrib = cfs_rq->avg.period_contrib;
5734 se->avg.util_sum = se->avg.util_avg * divider;
5736 se->avg.runnable_sum = se->avg.runnable_avg * divider;
5738 se->avg.load_sum = se->avg.load_avg * divider;
5739 if (se_weight(se) < se->avg.load_sum)
5740 se->avg.load_sum = div_u64(se->avg.load_sum, se_weight(se));
5742 se->avg.load_sum = 1;
5745 cfs_rq->avg.util_avg += se->avg.util_avg;
5746 cfs_rq->avg.util_sum += se->avg.util_sum;
5747 cfs_rq->avg.runnable_avg += se->avg.runnable_avg;
5748 cfs_rq->avg.runnable_sum += se->avg.runnable_sum;
5750 add_tg_cfs_propagate(cfs_rq, se->avg.load_sum);
5758 * detach_entity_load_avg - detach this entity from its cfs_rq load avg
5763 * cfs_rq->avg.last_update_time being current.
5768 __update_sa(&cfs_rq->avg, util, -se->avg.util_avg, -se->avg.util_sum);
5769 __update_sa(&cfs_rq->avg, runnable, -se->avg.runnable_avg, -se->avg.runnable_sum);
5771 add_tg_cfs_propagate(cfs_rq, -se->avg.load_sum);
5788 ewma = READ_ONCE(se->avg.util_est);
5798 dequeued = READ_ONCE(se->avg.util_avg);
5813 last_ewma_diff = ewma - dequeued;
5821 if ((dequeued + UTIL_EST_MARGIN) < READ_ONCE(se->avg.runnable_avg))
5831 * ewma(t) = w * task_util(p) + (1-w) * ewma(t-1)
5832 * = w * task_util(p) + ewma(t-1) - w * ewma(t-1)
5833 * = w * (task_util(p) - ewma(t-1)) + ewma(t-1)
5834 * = w * ( -last_ewma_diff ) + ewma(t-1)
5835 * = w * (-last_ewma_diff + ewma(t-1) / w)
5841 ewma -= last_ewma_diff;
5845 WRITE_ONCE(se->avg.util_est, ewma);
5869 if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD))
5875 if (!se->avg.last_update_time && (flags & DO_ATTACH)) {
5928 * tasks cannot exit without having gone through wake_up_new_task() ->
5935 raw_spin_lock_irqsave(&cfs_rq->removed.lock, flags);
5936 ++cfs_rq->removed.nr;
5937 cfs_rq->removed.util_avg += se->avg.util_avg;
5938 cfs_rq->removed.load_avg += se->avg.load_avg;
5939 cfs_rq->removed.runnable_avg += se->avg.runnable_avg;
5940 raw_spin_unlock_irqrestore(&cfs_rq->removed.lock, flags);
5945 return cfs_rq->avg.runnable_avg;
5950 return cfs_rq->avg.load_avg;
5958 return READ_ONCE(p->se.avg.util_avg);
5963 return READ_ONCE(p->se.avg.util_est) & ~UTIL_AVG_UNCHANGED;
5980 enqueued = cfs_rq->avg.util_est;
5982 WRITE_ONCE(cfs_rq->avg.util_est, enqueued);
5996 enqueued = cfs_rq->avg.util_est;
5997 enqueued -= min_t(unsigned int, enqueued, _task_util_est(p));
5998 WRITE_ONCE(cfs_rq->avg.util_est, enqueued);
6007 capacity -= max(hw_load_avg(cpu_rq(cpu)), cpufreq_get_pressure(cpu));
6065 * +----------------------------------------
6068 * In the above example if a task is capped to a specific performance
6103 * +----------------------------------------
6126 return -1;
6154 if (!p || (p->nr_cpus_allowed == 1) ||
6155 (arch_scale_cpu_capacity(cpu) == p->max_allowed_capacity) ||
6158 rq->misfit_task_load = 0;
6166 rq->misfit_task_load = max_t(unsigned long, task_h_load(p), 1);
6171 struct sched_entity *se = &p->se;
6173 p->static_prio = NICE_TO_PRIO(attr->sched_nice);
6174 if (attr->sched_runtime) {
6175 se->custom_slice = 1;
6176 se->slice = clamp_t(u64, attr->sched_runtime,
6180 se->custom_slice = 0;
6181 se->slice = sysctl_sched_base_slice;
6189 unsigned int nr_queued = cfs_rq->h_nr_queued;
6193 if (!se->custom_slice)
6194 se->slice = sysctl_sched_base_slice;
6195 vslice = calc_delta_fair(se->slice, se);
6198 nr_queued -= 1;
6208 if (sched_feat(PLACE_LAG) && nr_queued && se->vlag) {
6209 struct sched_entity *curr = cfs_rq->curr;
6212 lag = se->vlag;
6222 * lag_i = S - s_i = w_i * (V - v_i)
6227 * vl_i = V - v_i <=> v_i = V - vl_i
6239 * = (W*V + w_i*(V - vl_i)) / (W + w_i)
6240 * = (W*V + w_i*V - w_i*vl_i) / (W + w_i)
6241 * = (V*(W + w_i) - w_i*vl_i) / (W + w_i)
6242 * = V - w_i*vl_i / (W + w_i)
6246 * vl'_i = V' - v_i
6247 * = V - w_i*vl_i / (W + w_i) - (V - vl_i)
6248 * = vl_i - w_i*vl_i / (W + w_i)
6258 * vl'_i = vl_i - w_i*vl_i / (W + w_i)
6259 * = ((W + w_i)*vl_i - w_i*vl_i) / (W + w_i)
6261 * (W + w_i)*vl'_i = (W + w_i)*vl_i - w_i*vl_i
6266 load = cfs_rq->sum_weight;
6267 if (curr && curr->on_rq)
6268 load += avg_vruntime_weight(cfs_rq, curr->h_load.weight);
6270 weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
6284 * sum_w_vruntime = \Sum (v_i - v0) * w_i
6300 se->vruntime = vruntime - lag;
6303 update_zero_vruntime(cfs_rq, -lag);
6305 if (sched_feat(PLACE_REL_DEADLINE) && se->rel_deadline) {
6306 se->deadline += se->vruntime;
6307 se->rel_deadline = 0;
6322 se->deadline = se->vruntime + vslice;
6333 * - Update loads to have both entity and cfs_rq synced with now.
6334 * - For group_entity, update its runnable_weight to reflect the new
6336 * - For group_entity, update its weight to reflect the new share of
6338 * - Add its new weight to cfs_rq->load.weight
6344 * but update_cfs_group() here will re-adjust the weight and have to
6353 se->exec_start = 0;
6357 se->on_rq = 1;
6359 if (cfs_rq->nr_queued == 1) {
6363 if (cfs_rq->pelt_clock_throttled) {
6366 cfs_rq->throttled_clock_pelt_time += rq_clock_pelt(rq) -
6367 cfs_rq->throttled_clock_pelt;
6368 cfs_rq->pelt_clock_throttled = 0;
6376 if (WARN_ON_ONCE(!se->on_rq || se->sched_delayed))
6380 cfs_rq->next = se;
6385 if (cfs_rq->next == se)
6386 cfs_rq->next = NULL;
6393 se->sched_delayed = 1;
6406 cfs_rq->h_nr_runnable--;
6412 se->sched_delayed = 0;
6426 cfs_rq->h_nr_runnable++;
6445 * - Update loads to have both entity and cfs_rq synced with now.
6446 * - For group_entity, update its runnable_weight to reflect the new
6448 * - Subtract its previous weight from cfs_rq->load.weight.
6449 * - For group entity, update its weight to reflect the new share
6457 se->on_rq = 0;
6465 if (cfs_rq->nr_queued == 0) {
6472 cfs_rq->throttled_clock_pelt = rq_clock_pelt(rq);
6473 cfs_rq->pelt_clock_throttled = 1;
6483 if (se->on_rq) {
6494 WARN_ON_ONCE(cfs_rq->h_curr);
6495 cfs_rq->h_curr = se;
6500 * when there are only lesser-weight tasks around):
6503 rq_of(cfs_rq)->cfs.load.weight >= 2*se->load.weight) {
6507 __schedstat_set(stats->slice_max,
6508 max((u64)stats->slice_max,
6509 se->sum_exec_runtime - se->prev_sum_exec_runtime));
6512 se->prev_sum_exec_runtime = se->sum_exec_runtime;
6520 struct cfs_rq *cfs_rq = &rq->cfs;
6524 if (se->sched_delayed) {
6540 if (prev->on_rq)
6543 if (prev->on_rq) {
6548 WARN_ON_ONCE(cfs_rq->h_curr != prev);
6549 cfs_rq->h_curr = NULL;
6556 * Update run-time statistics of the 'current'.
6619 * directly instead of rq->clock to avoid adding additional synchronization
6620 * around rq->lock.
6622 * requires cfs_b->lock
6628 if (unlikely(cfs_b->quota == RUNTIME_INF))
6631 cfs_b->runtime += cfs_b->quota;
6632 runtime = cfs_b->runtime_snap - cfs_b->runtime;
6634 cfs_b->burst_time += runtime;
6635 cfs_b->nr_burst++;
6638 cfs_b->runtime = min(cfs_b->runtime, cfs_b->quota + cfs_b->burst);
6639 cfs_b->runtime_snap = cfs_b->runtime;
6644 return &tg->cfs_bandwidth;
6653 lockdep_assert_held(&cfs_b->lock);
6656 min_amount = target_runtime - cfs_rq->runtime_remaining;
6658 if (cfs_b->quota == RUNTIME_INF)
6663 if (cfs_b->runtime > 0) {
6664 amount = min(cfs_b->runtime, min_amount);
6665 cfs_b->runtime -= amount;
6666 cfs_b->idle = 0;
6670 cfs_rq->runtime_remaining += amount;
6672 return cfs_rq->runtime_remaining > 0;
6680 cfs_rq->runtime_remaining -= delta_exec;
6682 if (likely(cfs_rq->runtime_remaining > 0))
6685 if (cfs_rq->throttled)
6697 if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
6705 return cfs_bandwidth_used() && cfs_rq->throttled;
6710 return cfs_bandwidth_used() && cfs_rq->pelt_clock_throttled;
6716 return cfs_bandwidth_used() && cfs_rq->throttle_count;
6726 return cfs_bandwidth_used() && p->throttled;
6738 p->sched_throttle_work.next = &p->sched_throttle_work;
6744 if ((p->flags & PF_EXITING))
6748 se = &p->se;
6752 if (p->sched_class != &fair_sched_class)
6759 if (!cfs_rq->throttle_count)
6763 WARN_ON_ONCE(p->throttled || !list_empty(&p->throttle_node));
6765 list_add(&p->throttle_node, &cfs_rq->throttled_limbo_list);
6770 p->throttled = true;
6777 init_task_work(&p->sched_throttle_work, throttle_cfs_rq_work);
6779 p->sched_throttle_work.next = &p->sched_throttle_work;
6780 INIT_LIST_HEAD(&p->throttle_node);
6794 WARN_ON_ONCE(p->se.on_rq);
6795 list_del_init(&p->throttle_node);
6799 p->throttled = false;
6813 struct cfs_rq *cfs_rq = cfs_rq_of(&p->se);
6816 WARN_ON_ONCE(!list_empty(&p->throttle_node));
6824 * cause @p's group_node to be incorectly re-insterted in its rq's
6839 * enqueue_task(p) -> p's new cfs_rq
6844 * list_move(&se->group_node, &rq->cfs_tasks); // bug
6854 list_add(&p->throttle_node, &cfs_rq->throttled_limbo_list);
6859 p->throttled = false;
6872 * If cfs_rq->curr is set, the cfs_rq might not have caught up
6880 if (--cfs_rq->throttle_count)
6883 if (cfs_rq->pelt_clock_throttled) {
6884 cfs_rq->throttled_clock_pelt_time += rq_clock_pelt(rq) -
6885 cfs_rq->throttled_clock_pelt;
6886 cfs_rq->pelt_clock_throttled = 0;
6889 if (cfs_rq->throttled_clock_self) {
6890 u64 delta = rq_clock(rq) - cfs_rq->throttled_clock_self;
6892 cfs_rq->throttled_clock_self = 0;
6897 cfs_rq->throttled_clock_self_time += delta;
6903 * see the "throttled_limbo_list" being non-empty in
6906 list_splice_init(&cfs_rq->throttled_limbo_list, &throttled_tasks);
6908 /* Re-enqueue the tasks that have been throttled at this level. */
6915 if (cfs_rq->throttle_count)
6918 list_del_init(&p->throttle_node);
6919 p->throttled = false;
6923 list_splice(&throttled_tasks, &cfs_rq->throttled_limbo_list);
6934 return p->sched_throttle_work.next != &p->sched_throttle_work;
6946 if ((p->flags & (PF_EXITING | PF_KTHREAD)))
6949 task_work_add(p, &p->sched_throttle_work, TWA_RESUME);
6956 if (cfs_rq_throttled(cfs_rq) && !cfs_rq->throttled_clock)
6957 cfs_rq->throttled_clock = rq_clock(rq);
6959 if (!cfs_rq->throttled_clock_self)
6960 cfs_rq->throttled_clock_self = rq_clock(rq);
6968 if (cfs_rq->throttle_count++)
6975 if (!cfs_rq->nr_queued) {
6977 cfs_rq->throttled_clock_pelt = rq_clock_pelt(rq);
6978 cfs_rq->pelt_clock_throttled = 1;
6981 WARN_ON_ONCE(cfs_rq->throttled_clock_self);
6982 WARN_ON_ONCE(!list_empty(&cfs_rq->throttled_limbo_list));
6988 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
6989 struct sched_entity *curr = cfs_rq->h_curr;
6992 scoped_guard(raw_spinlock, &cfs_b->lock) {
6996 * If cfs_rq->h_curr is still runnable, we are here from an
7003 if (curr && curr->on_rq)
7023 list_add_tail_rcu(&cfs_rq->throttled_list,
7024 &cfs_b->throttled_cfs_rq);
7029 walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq);
7033 * throttled-list. rq->lock protects completion.
7035 cfs_rq->throttled = 1;
7036 WARN_ON_ONCE(cfs_rq->throttled_clock);
7040 * current donor. In case of proxy-execution, the execution
7045 if (curr && curr->on_rq)
7046 task_throttle_setup_work(rq->donor);
7054 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
7070 if (cfs_rq->runtime_enabled && cfs_rq->runtime_remaining <= 0)
7073 cfs_rq->throttled = 0;
7075 scoped_guard(raw_spinlock, &cfs_b->lock) {
7076 list_del_rcu(&cfs_rq->throttled_list);
7078 if (!cfs_rq->throttled_clock)
7081 cfs_b->throttled_time += rq_clock(rq) - cfs_rq->throttled_clock;
7082 cfs_rq->throttled_clock = 0;
7086 walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq);
7088 if (!cfs_rq->load.weight) {
7089 if (!cfs_rq->on_list)
7104 if (rq->curr == rq->idle && rq->cfs.h_nr_queued)
7132 list_for_each_entry_safe(cursor, tmp, &rq->cfsb_csd_list,
7134 list_del_init(&cursor->throttled_csd_list);
7155 if (WARN_ON_ONCE(!list_empty(&cfs_rq->throttled_csd_list)))
7158 first = list_empty(&rq->cfsb_csd_list);
7159 list_add_tail(&cfs_rq->throttled_csd_list, &rq->cfsb_csd_list);
7161 smp_call_function_single_async(cpu_of(rq), &rq->cfsb_csd);
7169 cfs_rq->runtime_remaining <= 0))
7185 list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
7200 if (!list_empty(&cfs_rq->throttled_csd_list))
7203 if (cfs_rq->h_curr) {
7209 WARN_ON_ONCE(cfs_rq->runtime_remaining > 0);
7211 scoped_guard(raw_spinlock, &cfs_b->lock) {
7212 runtime = -cfs_rq->runtime_remaining + 1;
7213 if (runtime > cfs_b->runtime)
7214 runtime = cfs_b->runtime;
7215 cfs_b->runtime -= runtime;
7216 remaining = cfs_b->runtime;
7219 cfs_rq->runtime_remaining += runtime;
7225 if (cfs_rq->runtime_remaining <= 0) {
7242 unthrottle_local = list_empty(&rq->cfsb_csd_list);
7243 list_add_tail(&cfs_rq->throttled_csd_list, &rq->cfsb_csd_list);
7261 * period the timer is deactivated until scheduling resumes; cfs_b->idle is
7265 __must_hold(&cfs_b->lock)
7270 if (cfs_b->quota == RUNTIME_INF)
7273 throttled = !list_empty(&cfs_b->throttled_cfs_rq);
7274 cfs_b->nr_periods += overrun;
7276 /* Refill extra burst quota even if cfs_b->idle */
7283 if (cfs_b->idle && !throttled)
7288 cfs_b->idle = 1;
7293 cfs_b->nr_throttled += overrun;
7296 * This check is repeated as we release cfs_b->lock while we unthrottle.
7298 while (throttled && cfs_b->runtime > 0) {
7299 raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
7300 /* we can't nest cfs_b->lock while distributing bandwidth */
7302 raw_spin_lock_irqsave(&cfs_b->lock, flags);
7311 cfs_b->idle = 0;
7329 * Requires cfs_b->lock for hrtimer_expires_remaining to be safe against the
7335 struct hrtimer *refresh_timer = &cfs_b->period_timer;
7338 /* if the call-back is running a quota refresh is already occurring */
7359 if (cfs_b->slack_started)
7361 cfs_b->slack_started = true;
7363 hrtimer_start(&cfs_b->slack_timer,
7371 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
7372 s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime;
7377 guard(raw_spinlock)(&cfs_b->lock);
7379 if (cfs_b->quota != RUNTIME_INF) {
7380 cfs_b->runtime += slack_runtime;
7382 /* we are under rq->lock, defer unthrottling using a timer */
7383 if (cfs_b->runtime > sched_cfs_bandwidth_slice() &&
7384 !list_empty(&cfs_b->throttled_cfs_rq))
7389 cfs_rq->runtime_remaining -= slack_runtime;
7397 if (!cfs_rq->runtime_enabled || cfs_rq->nr_queued)
7405 * it's necessary to juggle rq->locks to unthrottle their respective cfs_rqs.
7410 scoped_guard(raw_spinlock_irqsave, &cfs_b->lock) {
7413 cfs_b->slack_started = false;
7418 if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice)
7419 runtime = cfs_b->runtime;
7431 * runtime as update_curr() throttling can not trigger until it's on-rq.
7439 if (!cfs_rq->runtime_enabled || cfs_rq->h_curr)
7457 if (!tg->parent)
7461 pcfs_rq = tg_cfs_rq(tg->parent, cpu);
7463 cfs_rq->throttle_count = pcfs_rq->throttle_count;
7464 cfs_rq->throttled_clock_pelt = rq_clock_pelt(cpu_rq(cpu));
7473 if (cfs_rq->throttle_count)
7474 cfs_rq->pelt_clock_throttled = 1;
7495 CLASS(raw_spinlock_irqsave, cfsb_guard)(&cfs_b->lock);
7498 overrun = hrtimer_forward_now(timer, cfs_b->period);
7505 u64 new, old = ktime_to_ns(cfs_b->period);
7514 cfs_b->period = ns_to_ktime(new);
7515 cfs_b->quota *= 2;
7516 cfs_b->burst *= 2;
7522 div_u64(cfs_b->quota, NSEC_PER_USEC));
7528 div_u64(cfs_b->quota, NSEC_PER_USEC));
7537 cfs_b->period_active = 0;
7546 raw_spin_lock_init(&cfs_b->lock);
7547 cfs_b->runtime = 0;
7548 cfs_b->quota = RUNTIME_INF;
7549 cfs_b->period = us_to_ktime(default_bw_period_us());
7550 cfs_b->burst = 0;
7551 cfs_b->hierarchical_quota = parent ? parent->hierarchical_quota : RUNTIME_INF;
7553 INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq);
7554 hrtimer_setup(&cfs_b->period_timer, sched_cfs_period_timer, CLOCK_MONOTONIC,
7558 hrtimer_set_expires(&cfs_b->period_timer,
7559 get_random_u32_below(cfs_b->period));
7560 hrtimer_setup(&cfs_b->slack_timer, sched_cfs_slack_timer, CLOCK_MONOTONIC,
7562 cfs_b->slack_started = false;
7567 cfs_rq->runtime_enabled = 0;
7568 INIT_LIST_HEAD(&cfs_rq->throttled_list);
7569 INIT_LIST_HEAD(&cfs_rq->throttled_csd_list);
7570 INIT_LIST_HEAD(&cfs_rq->throttled_limbo_list);
7575 lockdep_assert_held(&cfs_b->lock);
7577 if (cfs_b->period_active)
7580 cfs_b->period_active = 1;
7581 hrtimer_forward_now(&cfs_b->period_timer, cfs_b->period);
7582 hrtimer_start_expires(&cfs_b->period_timer, HRTIMER_MODE_ABS_PINNED);
7590 if (!cfs_b->throttled_cfs_rq.next)
7593 hrtimer_cancel(&cfs_b->period_timer);
7594 hrtimer_cancel(&cfs_b->slack_timer);
7609 if (list_empty(&rq->cfsb_csd_list))
7634 struct cfs_bandwidth *cfs_b = &tg->cfs_bandwidth;
7637 scoped_guard(raw_spinlock, &cfs_b->lock)
7638 cfs_rq->runtime_enabled = cfs_b->quota != RUNTIME_INF;
7665 if (!cfs_rq->runtime_enabled)
7672 cfs_rq->runtime_enabled = 0;
7681 cfs_rq->runtime_remaining = 1;
7695 if (cfs_rq->runtime_enabled ||
7696 tg_cfs_bandwidth(cfs_rq->tg)->hierarchical_quota != RUNTIME_INF)
7714 if (rq->nr_running != 1)
7791 struct sched_entity *se = &p->se;
7799 if (rq->cfs.h_nr_queued <= 1)
7805 vdelta = se->deadline - se->vruntime;
7811 delta = (se->h_load.weight * vdelta) / NICE_0_LOAD;
7819 scale /= (1024 - util);
7830 struct task_struct *donor = rq->donor;
7832 if (!hrtick_enabled_fair(rq) || donor->sched_class != &fair_sched_class)
7869 return !sched_energy_enabled() || READ_ONCE(rd->overutilized);
7877 WRITE_ONCE(rd->overutilized, flag);
7888 if (!is_rd_overutilized(rq->rd) && cpu_overutilized(rq->cpu))
7889 set_rd_overutilized(rq->rd, 1);
7895 return unlikely(rq->nr_running == rq->cfs.h_nr_idle &&
7896 rq->nr_running);
7914 * se->sched_delayed should imply: se->on_rq == 1.
7918 WARN_ON_ONCE(!se->sched_delayed);
7919 WARN_ON_ONCE(!se->on_rq);
7922 cfs_rq->h_nr_queued--;
7923 if (se != cfs_rq->curr)
7926 if (se != cfs_rq->curr)
7928 cfs_rq->h_nr_queued++;
7939 struct sched_entity *se = &p->se;
7943 if (task_new && se->sched_delayed)
7951 if (!se->on_rq) {
7959 cfs_rq->h_nr_runnable += h_nr_runnable;
7960 cfs_rq->h_nr_queued++;
7961 cfs_rq->h_nr_idle += h_nr_idle;
7977 if (!cfs_rq->curr)
7980 update_curr(cfs_rq_of(cfs_rq->curr));
7991 int rq_h_nr_queued = rq->cfs.h_nr_queued;
7993 struct sched_entity *se = &p->se;
7994 struct cfs_rq *cfs_rq = &rq->cfs;
8007 if (!p->se.sched_delayed || (flags & ENQUEUE_DELAYED))
8022 if (p->in_iowait)
8028 curr = (cfs_rq->curr == se);
8032 if (se->on_rq && se->sched_delayed)
8043 if (!rq_h_nr_queued && rq->cfs.h_nr_queued)
8044 dl_server_start(&rq->fair_server);
8073 struct sched_entity *se = &p->se;
8081 if (task_sleep || task_delayed || !se->sched_delayed)
8092 if (cfs_rq->load.weight)
8100 cfs_rq->h_nr_runnable -= h_nr_runnable;
8101 cfs_rq->h_nr_queued--;
8102 cfs_rq->h_nr_idle -= h_nr_idle;
8119 * true - dequeued
8120 * false - delayed
8124 struct sched_entity *se = &p->se;
8125 struct cfs_rq *cfs_rq = &rq->cfs;
8136 WARN_ON_ONCE(!se->sched_delayed);
8146 WARN_ON_ONCE(delay && se->sched_delayed);
8159 se->deadline -= se->vruntime;
8160 se->rel_deadline = 1;
8162 if (se != cfs_rq->curr)
8169 rq->next_balance = jiffies;
8175 WARN_ON_ONCE(p->on_rq != 1);
8178 * Fix-up what block_task() skipped.
8200 if (!p->se.sched_delayed)
8201 util_est_dequeue(&rq->cfs, p);
8214 return (rq->cfs.h_nr_queued - rq->cfs.h_nr_runnable);
8236 return cfs_rq_load_avg(&rq->cfs);
8240 * cpu_load_without - compute CPU load without any contributions from *p
8258 if (cpu_of(rq) != task_cpu(p) || !READ_ONCE(p->se.avg.last_update_time))
8261 cfs_rq = &rq->cfs;
8262 load = READ_ONCE(cfs_rq->avg.load_avg);
8272 return cfs_rq_runnable_avg(&rq->cfs);
8281 if (cpu_of(rq) != task_cpu(p) || !READ_ONCE(p->se.avg.last_update_time))
8284 cfs_rq = &rq->cfs;
8285 runnable = READ_ONCE(cfs_rq->avg.runnable_avg);
8288 lsub_positive(&runnable, p->se.avg.runnable_avg);
8295 return cpu_rq(cpu)->cpu_capacity;
8304 if (time_after(jiffies, current->wakee_flip_decay_ts + HZ)) {
8305 current->wakee_flips >>= 1;
8306 current->wakee_flip_decay_ts = jiffies;
8309 if (current->last_wakee != p) {
8310 current->last_wakee = p;
8311 current->wakee_flips++;
8316 * Detect M:N waker/wakee relationships via a switching-frequency heuristic.
8326 * non-monogamous, with partner count exceeding socket size.
8334 unsigned int master = current->wakee_flips;
8335 unsigned int slave = p->wakee_flips;
8350 * wake_affine_idle() - only considers 'now', it check if the waking CPU is
8351 * cache-affine and is (or will be) idle.
8353 * wake_affine_weight() - considers the weight to reflect the average
8378 if ((rq->nr_running - cfs_h_nr_delayed(rq)) == 1)
8403 this_eff_load -= current_load;
8414 prev_eff_load -= task_load;
8416 prev_eff_load *= 100 + (sd->imbalance_pct - 100) / 2;
8442 schedstat_inc(p->stats.nr_wakeups_affine_attempts);
8446 schedstat_inc(sd->ttwu_move_affine);
8447 schedstat_inc(p->stats.nr_wakeups_affine);
8455 * sched_balance_find_dst_group_cpu - find the idlest CPU among the CPUs in the group.
8464 int shallowest_idle_cpu = -1;
8468 if (group->group_weight == 1)
8472 for_each_cpu_and(i, sched_group_span(group), p->cpus_ptr) {
8483 if (idle && idle->exit_latency < min_exit_latency) {
8489 min_exit_latency = idle->exit_latency;
8490 latest_idle_timestamp = rq->idle_stamp;
8492 } else if ((!idle || idle->exit_latency == min_exit_latency) &&
8493 rq->idle_stamp > latest_idle_timestamp) {
8499 latest_idle_timestamp = rq->idle_stamp;
8502 } else if (shallowest_idle_cpu == -1) {
8511 return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu;
8519 if (!cpumask_intersects(sched_domain_span(sd), p->cpus_ptr))
8527 sync_entity_load_avg(&p->se);
8534 if (!(sd->flags & sd_flag)) {
8535 sd = sd->child;
8541 sd = sd->child;
8548 sd = sd->child;
8554 weight = sd->span_weight;
8557 if (weight <= tmp->span_weight)
8559 if (tmp->flags & sd_flag)
8572 return -1;
8584 WRITE_ONCE(sds->has_idle_cores, val);
8593 return READ_ONCE(sds->has_idle_cores);
8600 * information in sd_balance_shared->has_idle_cores.
8630 * sd_balance_shared->has_idle_cores and enabled through update_idle_core()
8641 if (*idle_cpu == -1) {
8651 if (*idle_cpu == -1 && cpumask_test_cpu(cpu, cpus))
8659 return -1;
8669 for_each_cpu_and(cpu, cpu_smt_mask(target), p->cpus_ptr) {
8682 return -1;
8687 * comparing the average scan cost (tracked in sd->avg_scan_cost) against the
8688 * average idle time for this rq (as found in rq->avg_idle).
8693 int i, cpu, idle_cpu = -1, nr = INT_MAX;
8695 if (sched_feat(SIS_UTIL) && sd->shared) {
8697 * Increment because !--nr is the condition to stop scan.
8700 * caller, it is safe to directly dereference "sd->shared".
8705 nr = READ_ONCE(sd->shared->nr_idle_scan) + 1;
8708 return -1;
8711 if (!cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr))
8712 return -1;
8715 struct sched_group *sg = sd->groups;
8717 if (sg->flags & SD_CLUSTER) {
8727 if (--nr <= 0)
8728 return -1;
8745 if (--nr <= 0)
8746 return -1;
8760 * Idle-capacity scan converts util_fits_cpu() outcomes into preference ranks,
8761 * where lower values indicate a better fit - see select_idle_capacity().
8763 * A CPU that both fits the task and sits on a fully-idle SMT core is returned
8765 * its own "core", so the early return covers all fits-and-idle cases and the
8766 * core-tier ranks below become unreachable.
8769 * ------------------------------ --- ------ ---------------------------
8770 * ASYM_IDLE_UCLAMP_MISFIT -4 core Idle core; capacity fits
8772 * ASYM_IDLE_COMPLETE_MISFIT -3 core Idle core; capacity does
8774 * thread-tier rank: a busy
8778 * ASYM_IDLE_THREAD_FITS -2 thread Busy SMT sibling; capacity
8780 * ASYM_IDLE_THREAD_UCLAMP_MISFIT -1 thread Busy SMT sibling; capacity
8787 * ASYM_IDLE_CORE_BIAS (-3) is an offset, not a state. On an idle core,
8788 * fits += ASYM_IDLE_CORE_BIAS rebases thread-tier ranks into the core tier:
8790 * ASYM_IDLE_THREAD_UCLAMP_MISFIT (-1) + BIAS -> ASYM_IDLE_UCLAMP_MISFIT (-4)
8791 * ASYM_IDLE_THREAD_MISFIT (0) + BIAS -> ASYM_IDLE_COMPLETE_MISFIT (-3)
8793 * ASYM_IDLE_THREAD_FITS (-2) is never rebased because a fully-fitting idle-core
8794 * candidate early-returns from select_idle_capacity().
8797 ASYM_IDLE_UCLAMP_MISFIT = -4,
8804 ASYM_IDLE_CORE_BIAS = -3,
8823 int cpu, best_cpu = -1;
8828 cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
8834 if (sched_feat(SIS_UTIL) && sd->shared) {
8839 nr = READ_ONCE(sd->shared->nr_idle_scan) + 1;
8842 return -1;
8853 if (!has_idle_core && --nr <= 0)
8863 * sits on a fully-idle SMT core, this is a !SMT system, or
8865 * Short-circuit the rank-based selection and return
8881 * ASYM_IDLE_THREAD_MISFIT - does not fit
8882 * ASYM_IDLE_THREAD_UCLAMP_MISFIT - fits with the exception of UCLAMP_MIN
8883 * ASYM_IDLE_THREAD_FITS - fits with the exception of preferred_core
8918 * The asym-capacity wakeup path returns from select_idle_sibling()
8921 * idle-core preference did not win.
8942 * Note: gating on is_core_idle() also makes the early-bailout
8944 * recent_used_cpu) idle-core-aware on ASYM+SMT, which the
8962 int i, recent_used_cpu, prev_aff = -1;
8969 sync_entity_load_avg(&p->se);
8976 * per-cpu select_rq_mask usage
8999 * Allow a per-cpu kthread to stack with the wakee if the
9002 * per-cpu kthread that is now complete and the wakeup is
9009 this_rq()->nr_running <= 1 &&
9015 recent_used_cpu = p->recent_used_cpu;
9016 p->recent_used_cpu = prev;
9021 cpumask_test_cpu(recent_used_cpu, p->cpus_ptr) &&
9029 recent_used_cpu = -1;
9085 * cpu_util() - Estimates the amount of CPU capacity used by CFS tasks.
9088 * @dst_cpu: CPU @p migrates to, -1 if @p moves from @cpu or @p == NULL
9095 * recent utilization of currently non-runnable tasks on that CPU.
9103 * previously-executed tasks, which helps better deduce how busy a CPU will
9104 * be when a long-sleeping task wakes up. The contribution to CPU utilization
9118 * could be seen as over-utilized even though CPU1 has 20% of spare CPU
9121 * after task migrations (scheduler-driven DVFS).
9130 struct cfs_rq *cfs_rq = &cpu_rq(cpu)->cfs;
9131 unsigned long util = READ_ONCE(cfs_rq->avg.util_avg);
9135 * If @dst_cpu is -1 or @p migrates from @cpu to @dst_cpu remove its
9146 runnable = READ_ONCE(cfs_rq->avg.runnable_avg);
9148 runnable += READ_ONCE(p->se.avg.runnable_avg);
9151 READ_ONCE(p->se.avg.runnable_avg));
9158 util_est = READ_ONCE(cfs_rq->avg.util_est);
9161 * During wake-up @p isn't enqueued yet and doesn't contribute
9162 * to any cpu_rq(cpu)->cfs.avg.util_est.
9166 * During exec (@dst_cpu = -1) @p is enqueued and does
9167 * contribute to cpu_rq(cpu)->cfs.util_est.
9176 * p->on_rq = TASK_ON_RQ_MIGRATING;
9177 * -------------------------------- A
9181 * -------------------------------- B
9199 return cpu_util(cpu, NULL, -1, 0);
9204 return cpu_util(cpu, NULL, -1, 1);
9223 if (cpu != task_cpu(p) || !READ_ONCE(p->se.avg.last_update_time))
9226 return cpu_util(cpu, p, -1, 0);
9241 * The cfs,rt,dl utilization are the running times measured with rq->clock_task
9242 * which excludes things like IRQ and steal-time. These latter are then accrued
9260 * because of inaccuracies in how we track these -- see
9275 * - the computed DL bandwidth needed with the IRQ pressure which
9277 * - The minimum performance requirement for CFS and/or RT.
9285 if (!uclamp_is_used() && rt_rq_is_runnable(&rq->rt))
9313 * max - irq
9314 * U' = irq + --------- * U
9329 * energy_env - Utilization landscape for energy estimation.
9335 * @pd_cap: Entire perf domain capacity. (pd->nr_cpus * cpu_cap).
9361 eenv->task_busy_time = busy_time;
9375 * - A stable PD utilization, no matter which CPU of that PD we want to place
9378 * - A fair comparison between CPUs as the task contribution (task_util())
9383 * exceed @eenv->pd_cap.
9393 unsigned long util = cpu_util(cpu, p, -1, 0);
9398 eenv->pd_busy_time = min(eenv->pd_cap, busy_time);
9405 * Returns the maximum utilization among @eenv->cpus. This utilization can't
9406 * exceed @eenv->cpu_cap.
9447 return min(max_util, eenv->cpu_cap);
9460 unsigned long busy_time = eenv->pd_busy_time;
9464 busy_time = min(eenv->pd_cap, busy_time + eenv->task_busy_time);
9466 energy = em_cpu_energy(pd->em_pd, max_util, busy_time, eenv->cpu_cap);
9474 * find_energy_efficient_cpu(): Find most energy-efficient target CPU for the
9478 * out which of the CPU candidates is the most energy-efficient.
9495 * cluster-packing, and spreading inside a cluster. That should at least be
9502 * NOTE: Forkees are not accepted in the energy-aware wake-up path because
9506 * to be energy-inefficient in some use-cases. The alternative would be to
9507 * bias new tasks towards specific types of CPUs first, or to try to infer
9509 * other use-cases too. So, until someone finds a better way to solve this,
9510 * let's keep things simple by re-using the existing slow path.
9518 struct root_domain *rd = this_rq()->rd;
9519 int cpu, best_energy_cpu, target = -1;
9520 int prev_fits = -1, best_fits = -1;
9527 pd = rcu_dereference_all(rd->pd);
9532 * Energy-aware wake-up happens on the lowest sched_domain starting
9537 sd = sd->parent;
9543 sync_entity_load_avg(&p->se);
9549 for (; pd; pd = pd->next) {
9552 long prev_spare_cap = -1, max_spare_cap = -1;
9555 int max_spare_cap_cpu = -1;
9556 int fits, max_fits = -1;
9576 if (!cpumask_test_cpu(cpu, p->cpus_ptr))
9595 * max-aggregated uclamp_{min, max}.
9632 base_energy = compute_energy(&eenv, pd, cpus, p, -1);
9635 if (prev_spare_cap > -1) {
9641 prev_delta -= base_energy;
9665 cur_delta -= base_energy;
9703 int sync = (wake_flags & WF_SYNC) && !(current->flags & PF_EXITING);
9712 * required for stable ->cpus_allowed
9714 lockdep_assert_held(&p->pi_lock);
9719 cpumask_test_cpu(cpu, p->cpus_ptr))
9722 if (!is_rd_overutilized(this_rq()->rd)) {
9729 want_affine = !wake_wide(p) && cpumask_test_cpu(cpu, p->cpus_ptr);
9737 if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
9751 if (tmp->flags & sd_flag)
9771 * previous CPU. The caller guarantees p->pi_lock or task_rq(p)->lock is held.
9775 struct sched_entity *se = &p->se;
9784 * leading to an inflation after wake-up on the new rq.
9794 se->avg.last_update_time = 0;
9801 struct sched_entity *se = &p->se;
9820 if (!cpumask_intersects(p->cpus_ptr, cpumask))
9823 p->max_allowed_capacity = entry->capacity;
9850 if (cfs_rq->next && entity_before(cfs_rq->next, pse))
9859 if (cfs_rq->next && cfs_rq->next->slice < pse->slice)
9884 delta = rq_clock_task(rq) - se->exec_start;
9913 struct task_struct *donor = rq->donor;
9914 struct sched_entity *nse, *se = &donor->se, *pse = &p->se;
9915 struct cfs_rq *cfs_rq = &rq->cfs;
9921 if (p->sched_class != &fair_sched_class ||
9922 donor->sched_class != &fair_sched_class)
9932 * next-buddy nomination below.
9941 * Note: this also catches the edge-case of curr being in a throttled
9947 if (!sched_feat(PREEMPT_SHORT) && test_tsk_need_resched(rq->curr))
9960 * Preempt an idle entity in favor of a non-idle entity (and don't preempt
9974 if (unlikely(!normal_policy(p->policy)))
9981 if (pse->sched_delayed)
9988 if (sched_feat(PREEMPT_SHORT) && (pse->slice < se->slice)) {
10023 if (cfs_rq->h_nr_queued) {
10057 struct cfs_rq *cfs_rq = &rq->cfs;
10063 if (!cfs_rq->h_nr_queued)
10067 if (cfs_rq->curr && cfs_rq->curr->on_rq)
10091 __must_hold(__rq_lockp(dl_se->rq))
10093 return pick_task_fair(dl_se->rq, rf);
10098 struct sched_dl_entity *dl_se = &rq->fair_server;
10110 struct sched_entity *se = &prev->se;
10111 struct cfs_rq *cfs_rq = &rq->cfs;
10115 if (next && next->sched_class == &fair_sched_class)
10116 nse = &next->se;
10121 if (!nse || cfs_rq->h_curr)
10128 int d = nse->depth - se->depth;
10142 cfs_rq = &rq->cfs;
10143 se = &prev->se;
10144 WARN_ON_ONCE(cfs_rq->curr != se);
10145 cfs_rq->curr = NULL;
10146 if (se->on_rq)
10155 struct task_struct *curr = rq->donor;
10156 struct sched_entity *se = &curr->se;
10157 struct cfs_rq *cfs_rq = &rq->cfs;
10162 if (unlikely(rq->nr_running == 1))
10169 * Update run-time statistics of the 'current'.
10188 se->vruntime = se->deadline;
10195 struct sched_entity *se = &p->se;
10197 /* !se->on_rq also covers throttled task */
10198 if (!se->on_rq || se->sched_delayed)
10202 set_next_buddy(&task_rq(p)->cfs, se);
10210 * Fair scheduling class load-balancing methods.
10214 * The purpose of load-balancing is to achieve the same basic fairness the
10215 * per-CPU scheduler provides, namely provide a proportional amount of compute
10220 * Where W_i,n is the n-th weight average for CPU i. The instantaneous weight
10225 * Where w_i,j is the weight of the j-th runnable task on CPU i. This weight
10231 * W'_i,n = (2^n - 1) / 2^n * W_i,n + 1 / 2^n * W_i,0 (3)
10240 * imb_i,j = max{ avg(W/C), W_i/C_i } - min{ avg(W/C), W_j/C_j } (4)
10247 * - infeasible weights;
10248 * - local vs global optima in the discrete case. ]
10258 * of load-balance at each level inversely proportional to the number of CPUs in
10264 * \Sum { --- * --- * 2^i } = O(n) (5)
10266 * `- size of each group
10267 * | | `- number of CPUs doing load-balance
10268 * | `- freq
10269 * `- sum over all levels
10311 * W_i,0 = \Sum_j \Prod_k w_k * ----- (9)
10318 * w_i,j,k is the weight of the j-th runnable task in the k-th cgroup on CPU i.
10368 * There are tasks running on non-preferred LLC, possible to move
10413 /* The set of CPUs under consideration for load-balancing */
10428 * Is this task likely cache-hot:
10434 lockdep_assert_rq_held(env->src_rq);
10436 if (p->sched_class != &fair_sched_class)
10443 if (env->sd->flags & SD_SHARE_CPUCAPACITY)
10449 if (sched_feat(CACHE_HOT_BUDDY) && env->dst_rq->nr_running &&
10450 (&p->se == cfs_rq_of(&p->se)->next))
10453 if (sysctl_sched_migration_cost == -1)
10460 if (!sched_core_cookie_match(cpu_rq(env->dst_cpu), p))
10466 delta = rq_clock_task(env->src_rq) - p->se.exec_start;
10473 * Returns a positive value, if task migration degrades locality.
10474 * Returns 0, if task migration is not affected by locality.
10475 * Returns a negative value, if task migration improves locality i.e migration preferred.
10479 struct numa_group *numa_group = rcu_dereference_all(p->numa_group);
10486 if (!p->numa_faults || !(env->sd->flags & SD_NUMA))
10489 src_nid = cpu_to_node(env->src_cpu);
10490 dst_nid = cpu_to_node(env->dst_cpu);
10496 if (src_nid == p->numa_preferred_nid) {
10497 if (env->src_rq->nr_running > env->src_rq->nr_preferred_running)
10504 if (dst_nid == p->numa_preferred_nid)
10505 return -1;
10507 /* Leaving a core idle is often worse than degrading locality. */
10508 if (env->idle == CPU_IDLE)
10520 return src_weight - dst_weight;
10535 * dst_cfs_rq->nr_queued is greater than 1, if the task
10541 struct cfs_rq *dst_cfs_rq = &cpu_rq(dest_cpu)->cfs;
10543 if (sched_feat(PLACE_LAG) && dst_cfs_rq->h_nr_queued &&
10544 !entity_eligible(&task_rq(p)->cfs, &p->se))
10592 *util = READ_ONCE(sd_share->util_avg);
10593 *cap = READ_ONCE(sd_share->capacity);
10604 * of SMT-2, and it is also a safe cutoff for other SMT-n
10605 * platforms. SMT-1 has higher threshold because it is
10609 * if the preferred LLC is busier than the non-preferred LLC.
10612 * preferred LLC and the non-preferred LLC, and it will
10670 src_util = src_util < tsk_util ? 0 : src_util - tsk_util;
10691 * non-preferred LLC falls within sysctl_aggr_imb percent
10705 * On asymmetric CPU capacity domains, do not let cache-aware
10708 * the destination, trading a cache-locality gain for a capacity
10712 if ((env->sd->flags & SD_ASYM_CPUCAPACITY) && p &&
10713 !task_fits_cpu(p, env->dst_cpu) &&
10714 task_fits_cpu(p, env->src_cpu))
10734 src_cpu = env->src_cpu;
10735 dst_cpu = env->dst_cpu;
10736 mm = p->mm;
10740 cpu = READ_ONCE(mm->sc_stat.cpu);
10747 if (READ_ONCE(mm->sc_stat.cpu) != -1)
10748 WRITE_ONCE(mm->sc_stat.cpu, -1);
10764 * Check if active load balance breaks LLC locality in
10768 * LLC locality outweighs the power efficiency gained from
10777 if (cpus_share_cache(env->src_cpu, env->dst_cpu))
10785 * the cache-aware scheduling policy.
10787 if (env->src_rq->nr_pref_llc_running &&
10788 env->src_rq->nr_pref_llc_running == env->src_rq->cfs.h_nr_runnable) {
10797 if (env->migration_type == migrate_misfit)
10800 if (env->src_rq->nr_running <= 1)
10803 cur = rcu_dereference_all(env->src_rq->curr);
10804 if (cur && cur->sched_class == &fair_sched_class)
10808 can_migrate_llc(env->src_cpu, env->dst_cpu,
10817 * Check if migrating task p from env->src_cpu to
10818 * env->dst_cpu breaks LLC localiy.
10828 * Skip over tasks that would degrade LLC locality;
10836 if (env->sd->nr_balance_failed >= env->sd->cache_nice_tries + 1)
10840 * We know the env->src_cpu has some tasks prefer to
10841 * run on env->dst_cpu, skip the tasks do not prefer
10842 * env->dst_cpu, and find the one that prefers.
10844 if (env->migration_type == migrate_llc_task &&
10845 READ_ONCE(p->preferred_llc) != llc_id(env->dst_cpu))
10874 * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
10881 lockdep_assert_rq_held(env->src_rq);
10882 if (p->sched_task_hot)
10883 p->sched_task_hot = 0;
10891 * 5) are cache-hot on their current CPU, or
10894 if ((p->se.sched_delayed) && (env->migration_type != migrate_load))
10897 if (lb_throttled_hierarchy(p, env->dst_cpu))
10902 * For ineligible tasks we soft-limit them and only allow
10903 * them to migrate when nr_balance_failed is non-zero to
10904 * avoid load-balancing trying very hard to balance the load.
10906 if (!env->sd->nr_balance_failed &&
10907 task_is_ineligible_on_dst_cpu(p, env->dst_cpu))
10917 if (!cpumask_test_cpu(env->dst_cpu, p->cpus_ptr)) {
10920 schedstat_inc(p->stats.nr_failed_migrations_affine);
10922 env->flags |= LBF_SOME_PINNED;
10930 * - for NEWLY_IDLE
10931 * - if we have already computed one in current iteration
10932 * - if it's an active balance
10934 if (env->idle == CPU_NEWLY_IDLE ||
10935 env->flags & (LBF_DST_PINNED | LBF_ACTIVE_LB))
10938 /* Prevent to re-select dst_cpu via env's CPUs: */
10939 cpu = cpumask_first_and_and(env->dst_grpmask, env->cpus, p->cpus_ptr);
10942 env->flags |= LBF_DST_PINNED;
10943 env->new_dst_cpu = cpu;
10950 env->flags &= ~LBF_ALL_PINNED;
10952 if (task_on_cpu(env->src_rq, p) ||
10953 task_current_donor(env->src_rq, p)) {
10954 schedstat_inc(p->stats.nr_failed_migrations_running);
10965 if (env->flags & LBF_ACTIVE_LB)
10971 * If the NUMA locality is not broken,
10973 * LLC locality.
10978 * due to LLC locality, this is expected behavior
10982 if (env->migration_type != migrate_llc_task)
10983 env->flags |= LBF_LLC_PINNED;
10993 if (!hot || env->sd->nr_balance_failed > env->sd->cache_nice_tries) {
10995 p->sched_task_hot = 1;
10999 schedstat_inc(p->stats.nr_failed_migrations_hot);
11004 * detach_task() -- detach the task for the migration specified in env
11008 lockdep_assert_rq_held(env->src_rq);
11010 if (p->sched_task_hot) {
11011 p->sched_task_hot = 0;
11012 schedstat_inc(env->sd->lb_hot_gained[env->idle]);
11013 schedstat_inc(p->stats.nr_forced_migrations);
11016 WARN_ON(task_current(env->src_rq, p));
11017 WARN_ON(task_current_donor(env->src_rq, p));
11019 deactivate_task(env->src_rq, p, DEQUEUE_NOCLOCK);
11020 set_task_cpu(p, env->dst_cpu);
11024 * detach_one_task() -- tries to dequeue exactly one task from env->src_rq, as
11033 lockdep_assert_rq_held(env->src_rq);
11036 &env->src_rq->cfs_tasks, se.group_node) {
11044 * lb_gained[env->idle] is updated (other is detach_tasks)
11048 schedstat_inc(env->sd->lb_gained[env->idle]);
11055 * detach_tasks() -- tries to detach up to imbalance load/util/tasks from
11062 struct list_head *tasks = &env->src_rq->cfs_tasks;
11067 lockdep_assert_rq_held(env->src_rq);
11073 if (env->src_rq->nr_running <= 1) {
11074 env->flags &= ~LBF_ALL_PINNED;
11078 if (env->imbalance <= 0)
11086 if (env->idle && env->src_rq->nr_running <= 1)
11089 env->loop++;
11091 if (env->loop > env->loop_max)
11095 if (env->loop > env->loop_break) {
11096 env->loop_break += SCHED_NR_MIGRATE_BREAK;
11097 env->flags |= LBF_NEED_BREAK;
11106 switch (env->migration_type) {
11111 * value. Make sure that env->imbalance decreases
11118 load < 16 && !env->sd->nr_balance_failed)
11127 if (shr_bound(load, env->sd->nr_balance_failed) > env->imbalance)
11130 env->imbalance -= load;
11136 if (shr_bound(util, env->sd->nr_balance_failed) > env->imbalance)
11139 env->imbalance -= util;
11143 env->imbalance--;
11148 if (task_fits_cpu(p, env->src_cpu))
11151 env->imbalance = 0;
11155 env->imbalance--;
11160 list_add(&p->se.group_node, &env->tasks);
11170 if (env->idle == CPU_NEWLY_IDLE)
11178 if (env->imbalance <= 0)
11183 if (p->sched_task_hot)
11184 schedstat_inc(p->stats.nr_failed_migrations_hot);
11186 list_move(&p->se.group_node, tasks);
11194 schedstat_add(env->sd->lb_gained[env->idle], detached);
11200 * attach_tasks() -- attaches all tasks detached by detach_tasks() to their
11205 struct list_head *tasks = &env->tasks;
11209 rq_lock(env->dst_rq, &rf);
11210 update_rq_clock(env->dst_rq);
11214 list_del_init(&p->se.group_node);
11216 attach_task(env->dst_rq, p);
11219 rq_unlock(env->dst_rq, &rf);
11225 if (cfs_rq->avg.load_avg)
11228 if (cfs_rq->avg.util_avg)
11253 WRITE_ONCE(rq->last_blocked_load_update_tick, jiffies);
11259 rq->has_blocked_load = 0;
11301 if (cfs_rq->nr_queued == 0)
11304 if (cfs_rq == &rq->cfs)
11330 * This needs to be done in a top-down fashion because the load of a child
11339 if (cfs_rq->last_h_load_update == now)
11342 WRITE_ONCE(cfs_rq->h_load_next, NULL);
11345 WRITE_ONCE(cfs_rq->h_load_next, se);
11346 if (cfs_rq->last_h_load_update == now)
11351 cfs_rq->h_load = cfs_rq_load_avg(cfs_rq);
11352 cfs_rq->last_h_load_update = now;
11355 while ((se = READ_ONCE(cfs_rq->h_load_next)) != NULL) {
11356 load = cfs_rq->h_load;
11357 load = div64_ul(load * se->avg.load_avg,
11360 cfs_rq->h_load = load;
11361 cfs_rq->last_h_load_update = now;
11370 return div64_ul(p->se.avg.load_avg * cfs_rq->h_load,
11376 struct cfs_rq *cfs_rq = &rq->cfs;
11388 return p->se.avg.load_avg;
11418 * sg_lb_stats - stats of a sched_group required for load-balancing:
11446 * sd_lb_stats - stats of a sched_domain required for load-balancing:
11503 free = max - used;
11511 struct sched_group *sdg = sd->groups;
11516 cpu_rq(cpu)->cpu_capacity = capacity;
11519 sdg->sgc->capacity = capacity;
11520 sdg->sgc->min_capacity = capacity;
11521 sdg->sgc->max_capacity = capacity;
11526 struct sched_domain *child = sd->child;
11527 struct sched_group *group, *sdg = sd->groups;
11531 interval = msecs_to_jiffies(sd->balance_interval);
11533 sdg->sgc->next_update = jiffies + interval;
11544 if (child->flags & SD_NUMA) {
11563 group = child->groups;
11565 struct sched_group_capacity *sgc = group->sgc;
11567 capacity += sgc->capacity;
11568 min_capacity = min(sgc->min_capacity, min_capacity);
11569 max_capacity = max(sgc->max_capacity, max_capacity);
11570 group = group->next;
11571 } while (group != child->groups);
11574 sdg->sgc->capacity = capacity;
11575 sdg->sgc->min_capacity = min_capacity;
11576 sdg->sgc->max_capacity = max_capacity;
11587 return ((rq->cpu_capacity * sd->imbalance_pct) <
11594 return rq->misfit_task_load;
11599 * groups is inadequate due to ->cpus_ptr constraints.
11608 * If we were to balance group-wise we'd place two tasks in the first group and
11628 return group->sgc->imbalance;
11646 if (sgs->sum_nr_running < sgs->group_weight)
11649 if ((sgs->group_capacity * imbalance_pct) <
11650 (sgs->group_runnable * 100))
11653 if ((sgs->group_capacity * 100) >
11654 (sgs->group_util * imbalance_pct))
11675 if (sched_energy_enabled() && !sgs->group_overutilized)
11678 if (sgs->sum_nr_running <= sgs->group_weight)
11681 if ((sgs->group_capacity * 100) <
11682 (sgs->group_util * imbalance_pct))
11685 if ((sgs->group_capacity * imbalance_pct) <
11686 (sgs->group_runnable * 100))
11700 if (sgs->group_llc_balance)
11706 if (sgs->group_asym_packing)
11709 if (sgs->group_smt_balance)
11712 if (sgs->group_misfit_task_load)
11722 * sched_use_asym_prio - Check whether asym_packing priority must be used
11734 if (!(sd->flags & SD_ASYM_PACKING))
11740 return sd->flags & SD_SHARE_CPUCAPACITY || is_core_idle(cpu);
11754 * sched_group_asym - Check if the destination CPU can do asym_packing balance
11756 * @sgs: Load-balancing statistics of the candidate busiest group
11772 if ((group->flags & SD_SHARE_CPUCAPACITY) &&
11773 (sgs->group_weight - sgs->idle_cpus != 1))
11776 return sched_asym(env->sd, env->dst_cpu, READ_ONCE(group->asym_prefer_cpu));
11786 return (sg1->flags & SD_SHARE_CPUCAPACITY) !=
11787 (sg2->flags & SD_SHARE_CPUCAPACITY);
11793 if (!env->idle)
11802 if (group->flags & SD_SHARE_CPUCAPACITY &&
11803 sgs->sum_h_nr_running > 1)
11817 if (!env->idle || !busiest->sum_nr_running)
11820 ncores_busiest = sds->busiest->cores;
11821 ncores_local = sds->local->cores;
11824 imbalance = busiest->sum_nr_running;
11825 lsub_positive(&imbalance, local->sum_nr_running);
11830 imbalance = ncores_local * busiest->sum_nr_running;
11831 lsub_positive(&imbalance, ncores_busiest * local->sum_nr_running);
11837 if (imbalance <= 1 && local->sum_nr_running == 0 &&
11838 busiest->sum_nr_running > 1)
11851 if (rq->cfs.h_nr_runnable != 1)
11870 if (!sched_cache_enabled() || env->idle == CPU_NEWLY_IDLE)
11874 if (env->sd->child != rcu_dereference_all(per_cpu(sd_llc, env->dst_cpu)))
11881 * Note: sd_share cannot be obtained via sd->child->shared,
11891 if (READ_ONCE(sd_share->util_avg) != sgs->group_util)
11892 WRITE_ONCE(sd_share->util_avg, sgs->group_util);
11894 if (unlikely(READ_ONCE(sd_share->capacity) != sgs->group_capacity))
11895 WRITE_ONCE(sd_share->capacity, sgs->group_capacity);
11908 if (env->sd->flags & SD_SHARE_LLC)
11916 if ((env->sd->flags & SD_ASYM_CPUCAPACITY) &&
11917 sgs->group_misfit_task_load)
11925 if (env->sd->nr_balance_failed >= env->sd->cache_nice_tries + 1)
11928 if (sgs->nr_pref_dst_llc &&
11930 env->dst_cpu, 0, true) == mig_llc)
11943 return sgs->nr_pref_dst_llc > busiest->nr_pref_dst_llc;
11966 * update_sg_lb_stats - Update sched_group's statistics for load balancing.
11968 * @sds: Load-balancing data with statistics of the local group.
11979 int i, nr_running, local_group, sd_flags = env->sd->flags;
11980 bool balancing_at_rd = !env->sd->parent;
11984 local_group = group == sds->local;
11986 for_each_cpu_and(i, sched_group_span(group), env->cpus) {
11990 sgs->group_load += load;
11991 sgs->group_util += cpu_util_cfs(i);
11992 sgs->group_runnable += cpu_runnable(rq);
11993 sgs->sum_h_nr_running += rq->cfs.h_nr_runnable;
11995 nr_running = rq->nr_running;
11996 sgs->sum_nr_running += nr_running;
11999 sgs->group_overutilized = 1;
12006 dst_llc = llc_id(env->dst_cpu);
12008 sd_tmp = rcu_dereference_all(rq->sd);
12009 if (sd_tmp && (unsigned int)dst_llc < sd_tmp->llc_max)
12010 sgs->nr_pref_dst_llc += sd_tmp->llc_counts[dst_llc];
12019 sgs->idle_cpus++;
12031 sgs->nr_numa_running += rq->nr_numa_running;
12032 sgs->nr_preferred_running += rq->nr_preferred_running;
12039 if (rq->misfit_task_load) {
12054 if (capacity_greater(capacity_of(env->dst_cpu),
12055 group->sgc->max_capacity) &&
12056 (sgs->group_misfit_task_load < rq->misfit_task_load))
12057 sgs->group_misfit_task_load = rq->misfit_task_load;
12059 } else if (env->idle && sched_reduced_capacity(rq, env->sd)) {
12061 if (sgs->group_misfit_task_load < load)
12062 sgs->group_misfit_task_load = load;
12066 sgs->group_capacity = group->sgc->capacity;
12068 sgs->group_weight = group->group_weight;
12072 if (env->idle && sgs->sum_h_nr_running &&
12074 sgs->group_asym_packing = 1;
12078 sgs->group_smt_balance = 1;
12082 sgs->group_llc_balance = 1;
12085 sgs->group_type = group_classify(env->sd->imbalance_pct, group, sgs);
12089 if (sgs->group_type == group_overloaded)
12090 sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
12091 sgs->group_capacity;
12095 * update_sd_pick_busiest - return 1 on busiest group
12112 struct sg_lb_stats *busiest = &sds->busiest_stat;
12115 if (!sgs->sum_h_nr_running)
12129 if ((env->sd->flags & SD_ASYM_CPUCAPACITY) &&
12130 (sgs->group_type == group_misfit_task) &&
12131 (!env->dst_core_idle ||
12132 !capacity_greater(capacity_of(env->dst_cpu), sg->sgc->max_capacity) ||
12133 sds->local_stat.group_type != group_has_spare))
12138 * per-CPU capacity. Migrating tasks to less capable CPUs may harm
12142 if ((env->sd->flags & SD_ASYM_CPUCAPACITY) &&
12143 (sgs->group_type <= group_fully_busy) &&
12144 (capacity_greater(sg->sgc->min_capacity, capacity_of(env->dst_cpu))))
12147 if (sgs->group_type > busiest->group_type)
12150 if (sgs->group_type < busiest->group_type)
12158 switch (sgs->group_type) {
12161 return sgs->avg_load > busiest->avg_load;
12176 return sched_asym_prefer(READ_ONCE(sds->busiest->asym_prefer_cpu),
12177 READ_ONCE(sg->asym_prefer_cpu));
12184 return sgs->group_misfit_task_load > busiest->group_misfit_task_load;
12191 if (sgs->idle_cpus != 0 || busiest->idle_cpus != 0)
12209 if (sgs->avg_load < busiest->avg_load)
12212 if (sgs->avg_load == busiest->avg_load) {
12214 * SMT sched groups need more help than non-SMT groups.
12217 if (sds->busiest->flags & SD_SHARE_CPUCAPACITY)
12229 if (smt_vs_nonsmt_groups(sds->busiest, sg)) {
12230 if (sg->flags & SD_SHARE_CPUCAPACITY && sgs->sum_h_nr_running <= 1)
12244 if (sgs->idle_cpus > busiest->idle_cpus)
12246 else if ((sgs->idle_cpus == busiest->idle_cpus) &&
12247 (sgs->sum_nr_running <= busiest->sum_nr_running))
12259 if (sgs->sum_h_nr_running > sgs->nr_numa_running)
12261 if (sgs->sum_h_nr_running > sgs->nr_preferred_running)
12268 if (rq->nr_running > rq->nr_numa_running)
12270 if (rq->nr_running > rq->nr_preferred_running)
12290 * task_running_on_cpu - return 1 if @p is running on @cpu.
12296 if (cpu != task_cpu(p) || !READ_ONCE(p->se.avg.last_update_time))
12306 * idle_cpu_without - would a given CPU be idle without p ?
12316 if (rq->curr != rq->idle && rq->curr != p)
12320 * rq->nr_running can't be used but an updated version without the
12325 if (rq->ttwu_pending)
12332 * update_sg_wakeup_stats - Update sched_group's statistics for wakeup.
12348 if (sd->flags & SD_ASYM_CPUCAPACITY)
12349 sgs->group_misfit_task_load = 1;
12351 for_each_cpu_and(i, sched_group_span(group), p->cpus_ptr) {
12355 sgs->group_load += cpu_load_without(rq, p);
12356 sgs->group_util += cpu_util_without(i, p);
12357 sgs->group_runnable += cpu_runnable_without(rq, p);
12359 sgs->sum_h_nr_running += rq->cfs.h_nr_runnable - local;
12361 nr_running = rq->nr_running - local;
12362 sgs->sum_nr_running += nr_running;
12368 sgs->idle_cpus++;
12371 if (sd->flags & SD_ASYM_CPUCAPACITY &&
12372 sgs->group_misfit_task_load &&
12374 sgs->group_misfit_task_load = 0;
12378 sgs->group_capacity = group->sgc->capacity;
12380 sgs->group_weight = group->group_weight;
12382 sgs->group_type = group_classify(sd->imbalance_pct, group, sgs);
12388 if (sgs->group_type == group_fully_busy ||
12389 sgs->group_type == group_overloaded)
12390 sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
12391 sgs->group_capacity;
12399 if (sgs->group_type < idlest_sgs->group_type)
12402 if (sgs->group_type > idlest_sgs->group_type)
12410 switch (sgs->group_type) {
12414 if (idlest_sgs->avg_load <= sgs->avg_load)
12427 if (idlest->sgc->max_capacity >= group->sgc->max_capacity)
12433 if (idlest_sgs->idle_cpus > sgs->idle_cpus)
12437 if (idlest_sgs->idle_cpus == sgs->idle_cpus &&
12438 idlest_sgs->group_util <= sgs->group_util)
12456 struct sched_group *idlest = NULL, *local = NULL, *group = sd->groups;
12470 p->cpus_ptr))
12494 } while (group = group->next, group != sd->groups);
12525 (sd->imbalance_pct-100) / 100;
12532 * cross-domain, add imbalance to the load on the remote node
12536 if ((sd->flags & SD_NUMA) &&
12547 if (100 * local_sgs.avg_load <= sd->imbalance_pct * idlest_sgs.avg_load)
12560 if (local->sgc->max_capacity >= idlest->sgc->max_capacity)
12566 if (sd->flags & SD_NUMA) {
12567 int imb_numa_nr = sd->imb_numa_nr;
12574 if (cpu_to_node(this_cpu) == p->numa_preferred_nid)
12578 if (cpu_to_node(idlest_cpu) == p->numa_preferred_nid)
12583 * and improve locality if the number of running tasks
12590 if (p->nr_cpus_allowed != NR_CPUS) {
12591 unsigned int w = cpumask_weight_and(p->cpus_ptr,
12593 imb_numa_nr = min(w, sd->imb_numa_nr);
12596 imbalance = abs(local_sgs.idle_cpus - idlest_sgs.idle_cpus);
12623 struct sched_domain *sd = env->sd;
12634 if (!sched_feat(SIS_UTIL) || env->idle == CPU_NEWLY_IDLE)
12637 sd_share = sd->shared;
12647 * let y = SCHED_CAPACITY_SCALE - p * x^2 [1]
12665 * y = SCHED_CAPACITY_SCALE -
12671 llc_weight = sd->span_weight;
12675 pct = sd->imbalance_pct;
12679 y = SCHED_CAPACITY_SCALE - tmp;
12684 if ((int)y != sd_share->nr_idle_scan)
12685 WRITE_ONCE(sd_share->nr_idle_scan, (int)y);
12689 * update_sd_lb_stats - Update sched_domain's statistics for load balancing.
12696 struct sched_group *sg = env->sd->groups;
12697 struct sg_lb_stats *local = &sds->local_stat;
12702 env->dst_core_idle = !sched_smt_active() || is_core_idle(env->dst_cpu);
12708 local_group = cpumask_test_cpu(env->dst_cpu, sched_group_span(sg));
12710 sds->local = sg;
12713 if (env->idle != CPU_NEWLY_IDLE ||
12714 time_after_eq(jiffies, sg->sgc->next_update))
12715 update_group_capacity(env->sd, env->dst_cpu);
12721 sds->busiest = sg;
12722 sds->busiest_stat = *sgs;
12725 sg_overutilized |= sgs->group_overutilized;
12728 sds->total_load += sgs->group_load;
12729 sds->total_capacity += sgs->group_capacity;
12731 sum_util += sgs->group_util;
12732 sg = sg->next;
12733 } while (sg != env->sd->groups);
12740 if (sds->busiest)
12741 sds->prefer_sibling = !!(sds->busiest->flags & SD_PREFER_SIBLING);
12744 if (env->sd->flags & SD_NUMA)
12745 env->fbq_type = fbq_classify_group(&sds->busiest_stat);
12747 if (!env->sd->parent) {
12749 set_rd_overloaded(env->dst_rq->rd, sg_overloaded);
12751 /* Update over-utilization (tipping point, U >= 0) indicator */
12752 set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
12754 set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
12761 * calculate_imbalance - Calculate the amount of imbalance present within the
12770 local = &sds->local_stat;
12771 busiest = &sds->busiest_stat;
12773 if (busiest->group_type == group_misfit_task) {
12774 if (env->sd->flags & SD_ASYM_CPUCAPACITY) {
12776 env->migration_type = migrate_misfit;
12777 env->imbalance = 1;
12783 env->migration_type = migrate_load;
12784 env->imbalance = busiest->group_misfit_task_load;
12789 if (busiest->group_type == group_asym_packing) {
12794 env->migration_type = migrate_task;
12795 env->imbalance = busiest->sum_h_nr_running;
12799 if (busiest->group_type == group_smt_balance) {
12801 env->migration_type = migrate_task;
12802 env->imbalance = 1;
12807 if (busiest->group_type == group_llc_balance) {
12809 env->migration_type = migrate_llc_task;
12810 env->imbalance = 1;
12815 if (busiest->group_type == group_imbalanced) {
12817 * In the group_imb case we cannot rely on group-wide averages
12818 * to ensure CPU-load equilibrium, try to move any task to fix
12822 env->migration_type = migrate_task;
12823 env->imbalance = 1;
12831 if (local->group_type == group_has_spare) {
12832 if ((busiest->group_type > group_fully_busy) &&
12833 !(env->sd->flags & SD_SHARE_LLC)) {
12842 env->migration_type = migrate_util;
12843 env->imbalance = max(local->group_capacity, local->group_util) -
12844 local->group_util;
12853 if (env->idle && env->imbalance == 0) {
12854 env->migration_type = migrate_task;
12855 env->imbalance = 1;
12861 if (busiest->group_weight == 1 || sds->prefer_sibling) {
12866 env->migration_type = migrate_task;
12867 env->imbalance = sibling_imbalance(env, sds, busiest, local);
12874 env->migration_type = migrate_task;
12875 env->imbalance = max_t(long, 0,
12876 (local->idle_cpus - busiest->idle_cpus));
12881 if (env->sd->flags & SD_NUMA) {
12882 env->imbalance = adjust_numa_imbalance(env->imbalance,
12883 local->sum_nr_running + 1,
12884 env->sd->imb_numa_nr);
12889 env->imbalance >>= 1;
12898 if (local->group_type < group_overloaded) {
12904 local->avg_load = (local->group_load * SCHED_CAPACITY_SCALE) /
12905 local->group_capacity;
12911 if (local->avg_load >= busiest->avg_load) {
12912 env->imbalance = 0;
12916 sds->avg_load = (sds->total_load * SCHED_CAPACITY_SCALE) /
12917 sds->total_capacity;
12923 if (local->avg_load >= sds->avg_load) {
12924 env->imbalance = 0;
12938 env->migration_type = migrate_load;
12939 env->imbalance = min(
12940 (busiest->avg_load - sds->avg_load) * busiest->group_capacity,
12941 (sds->avg_load - local->avg_load) * local->group_capacity
12968 * sched_balance_find_src_group - Returns the busiest group within the sched_domain
12975 * Return: - The busiest group if imbalance exists.
12997 if (busiest->group_type == group_misfit_task)
13000 if (!is_rd_overutilized(env->dst_rq->rd) &&
13001 rcu_dereference_all(env->dst_rq->rd->pd))
13005 if (busiest->group_type == group_asym_packing)
13013 if (busiest->group_type == group_imbalanced)
13021 if (local->group_type > busiest->group_type)
13028 if (local->group_type == group_overloaded) {
13033 if (local->avg_load >= busiest->avg_load)
13044 if (local->avg_load >= sds.avg_load)
13051 if (100 * busiest->avg_load <=
13052 env->sd->imbalance_pct * local->avg_load)
13060 if (sds.prefer_sibling && local->group_type == group_has_spare &&
13061 (busiest->group_type == group_llc_balance ||
13065 if (busiest->group_type != group_overloaded) {
13066 if (!env->idle) {
13075 if (busiest->group_type == group_smt_balance &&
13081 if (busiest->group_weight > 1 &&
13082 local->idle_cpus <= (busiest->idle_cpus + 1)) {
13095 if (busiest->sum_h_nr_running == 1) {
13106 return env->imbalance ? sds.busiest : NULL;
13109 env->imbalance = 0;
13114 * sched_balance_find_src_rq - find the busiest runqueue among the CPUs in the group.
13127 for_each_cpu_and(i, sched_group_span(group), env->cpus) {
13137 * - regular: there are !numa tasks
13138 * - remote: there are numa tasks that run on the 'wrong' node
13139 * - all: there is no distinction
13154 if (rt > env->fbq_type)
13157 nr_running = rq->cfs.h_nr_runnable;
13165 * eventually lead to active_balancing high->low capacity.
13166 * Higher per-CPU capacity is considered better than balancing
13169 if (env->sd->flags & SD_ASYM_CPUCAPACITY &&
13172 (get_actual_cpu_capacity(env->dst_cpu) ==
13185 !capacity_greater(capacity_of(env->dst_cpu), capacity))
13196 if (sched_asym(env->sd, i, env->dst_cpu) && nr_running == 1)
13199 switch (env->migration_type) {
13207 if (nr_running == 1 && load > env->imbalance &&
13208 !check_cpu_capacity(rq, env->sd))
13260 if (rq->misfit_task_load > busiest_load) {
13261 busiest_load = rq->misfit_task_load;
13269 sd_tmp = rcu_dereference_all(rq->sd);
13270 dst_llc = llc_id(env->dst_cpu);
13272 if (sd_tmp && (unsigned)dst_llc < sd_tmp->llc_max) {
13274 sd_tmp->llc_counts[dst_llc];
13309 return env->idle && sched_use_asym_prio(env->sd, env->dst_cpu) &&
13310 (sched_asym_prefer(env->dst_cpu, env->src_cpu) ||
13311 !sched_use_asym_prio(env->sd, env->src_cpu));
13317 struct sched_domain *sd = env->sd;
13324 if ((env->migration_type == migrate_task) &&
13325 (sd->nr_balance_failed > sd->cache_nice_tries+2))
13333 struct sched_domain *sd = env->sd;
13350 if (env->idle &&
13351 (env->src_rq->cfs.h_nr_runnable == 1)) {
13352 if ((check_cpu_capacity(env->src_rq, sd)) &&
13353 (capacity_of(env->src_cpu)*sd->imbalance_pct < capacity_of(env->dst_cpu)*100))
13357 if (env->migration_type == migrate_misfit ||
13358 env->migration_type == migrate_llc_task)
13369 struct sched_group *sg = env->sd->groups;
13370 int cpu, idle_smt = -1;
13376 if (!cpumask_test_cpu(env->dst_cpu, env->cpus))
13386 if (env->idle == CPU_NEWLY_IDLE) {
13387 if (env->dst_rq->nr_running > 0 || env->dst_rq->ttwu_pending)
13394 for_each_cpu_and(cpu, swb_cpus, env->cpus) {
13404 !(env->sd->flags & SD_SHARE_CPUCAPACITY) &&
13406 if (idle_smt == -1)
13418 * Are we the first idle core in a non-SMT domain or higher,
13421 return cpu == env->dst_cpu;
13425 if (idle_smt != -1)
13426 return idle_smt == env->dst_cpu;
13429 return group_balance_cpu(sg) == env->dst_cpu;
13438 switch (env->migration_type) {
13440 __schedstat_add(sd->lb_imbalance_load[idle], env->imbalance);
13443 __schedstat_add(sd->lb_imbalance_util[idle], env->imbalance);
13446 __schedstat_add(sd->lb_imbalance_task[idle], env->imbalance);
13449 __schedstat_add(sd->lb_imbalance_misfit[idle], env->imbalance);
13457 * This flag serializes load-balancing passes over large domains
13458 * (above the NODE topology level) - only one load-balancing instance
13462 * - Note that load-balancing passes triggered while another one
13463 * is executing are skipped and not re-tried.
13465 * - Also note that this does not serialize rebalance_domains()
13466 * execution, as non-SD_SERIALIZE domains will still be
13467 * load-balanced in parallel.
13480 struct sched_domain *sd_parent = sd->parent;
13489 .dst_grpmask = group_balance_mask(sd->groups),
13500 schedstat_inc(sd->lb_count[idle]);
13508 if (!need_unlock && (sd->flags & SD_SERIALIZE)) {
13518 schedstat_inc(sd->lb_nobusyg[idle]);
13524 schedstat_inc(sd->lb_nobusyq[idle]);
13532 env.src_cpu = busiest->cpu;
13538 if (busiest->nr_running > 1) {
13541 * an imbalance but busiest->nr_running <= 1, the group is
13545 env.loop_max = min(sysctl_sched_nr_migrate, busiest->nr_running);
13552 * cur_ld_moved - load moved in current iteration
13553 * ld_moved - cumulative load moved across iterations
13560 * unlock busiest->lock, and we are able to be sure
13589 * nohz-idle), we now have balance_cpu in a position to move
13600 /* Prevent to re-select dst_cpu via env's CPUs */
13620 int *group_imbalance = &sd_parent->groups->sgc->imbalance;
13647 sd->nr_balance_failed = 0;
13651 schedstat_inc(sd->lb_failed[idle]);
13663 * migrate task due to LLC locality, it is a expected
13670 sd->nr_balance_failed++;
13681 if (!cpumask_test_cpu(this_cpu, busiest->curr->cpus_ptr))
13688 * ->active_balance synchronizes accesses to
13689 * ->active_balance_work. Once set, it's cleared
13692 if (busiest->active_balance)
13697 * scheduling out its ->curr task (->on_rq := 0), no
13700 if (!busiest->curr->on_rq)
13703 busiest->active_balance = 1;
13704 busiest->push_cpu = this_cpu;
13711 &busiest->active_balance_work);
13717 sd->balance_interval = sd->min_interval;
13727 int *group_imbalance = &sd_parent->groups->sgc->imbalance;
13739 schedstat_inc(sd->lb_balanced[idle]);
13741 sd->nr_balance_failed = 0;
13762 sd->balance_interval < MAX_PINNED_INTERVAL) ||
13763 sd->balance_interval < sd->max_interval)
13764 sd->balance_interval *= 2;
13775 unsigned long interval = sd->balance_interval;
13778 interval *= sd->busy_factor;
13789 interval -= 1;
13803 next = sd->last_balance + interval;
13819 int target_cpu = busiest_rq->push_cpu;
13827 * Between queueing the stop-work and running it is a hole in which
13836 !busiest_rq->active_balance))
13840 if (busiest_rq->nr_running <= 1)
13846 * Bjorn Helgaas on a 128-CPU setup.
13862 .src_cpu = busiest_rq->cpu,
13868 schedstat_inc(sd->alb_count);
13873 schedstat_inc(sd->alb_pushed);
13875 sd->nr_balance_failed = 0;
13877 schedstat_inc(sd->alb_failed);
13882 busiest_rq->active_balance = 0;
13895 * This trades load-balance latency on larger machines for less cross talk.
13904 sd->newidle_call++;
13905 sd->newidle_success += success;
13907 if (sd->newidle_call >= 1024) {
13909 s64 delta = now - sd->newidle_stamp;
13910 sd->newidle_stamp = now;
13920 * 1024 - 4 s - 128 Hz
13921 * 512 - 2 s - 256 Hz
13922 * 256 - 1 s - 512 Hz
13923 * 128 - .5 s - 1024 Hz
13924 * 64 - .25 s - 2048 Hz
13929 ratio += sd->newidle_success;
13931 sd->newidle_ratio = min(1024, ratio);
13932 sd->newidle_call /= 2;
13933 sd->newidle_success /= 2;
13940 unsigned long next_decay = sd->last_decay_max_lb_cost + HZ;
13946 if (cost > sd->max_newidle_lb_cost) {
13951 sd->max_newidle_lb_cost = cost;
13952 sd->last_decay_max_lb_cost = now;
13960 sd->max_newidle_lb_cost = (sd->max_newidle_lb_cost * 253) / 256;
13961 sd->last_decay_max_lb_cost = now;
13977 int cpu = rq->cpu;
13994 max_cost += sd->max_newidle_lb_cost;
14008 if (time_after_eq(jiffies, sd->last_balance + interval)) {
14012 * env->dst_cpu, so we can't know our idle
14018 sd->last_balance = jiffies;
14021 if (time_after(next_balance, sd->last_balance + interval)) {
14022 next_balance = sd->last_balance + interval;
14028 * Ensure the rq-wide value also decays but keep it at a
14029 * reasonable floor to avoid funnies with rq->avg_idle.
14031 rq->max_idle_balance_cost =
14042 rq->next_balance = next_balance;
14048 return unlikely(!rcu_dereference_sched(rq->sd));
14055 * - When one of the busy CPUs notices that there may be an idle rebalancing
14062 int ilb_cpu, fallback = -1;
14067 * Reuse the per-CPU select_rq_mask, which is protected from concurrent
14112 * Kick a CPU to do the NOHZ balancing, if it is time for it, via a cross-CPU
14153 smp_call_function_single_async(ilb_cpu, &cpu_rq(ilb_cpu)->nohz_csd);
14165 int nr_busy, i, cpu = rq->cpu;
14168 if (unlikely(rq->idle_balance))
14200 if (rq->nr_running >= 2) {
14205 sd = rcu_dereference_all(rq->sd);
14211 if (rq->cfs.h_nr_runnable >= 1 && check_cpu_capacity(rq, sd)) {
14258 * increase the overall cache utilization), we need a less-loaded LLC
14262 * the others are - so just get a NOHZ balance going if it looks
14265 nr_busy = atomic_read(&sds->nr_busy_cpus);
14283 * sd->nohz_idle only pairs with nr_busy_cpus on sd->shared; if this
14286 if (!sd || !sd->shared || !sd->nohz_idle)
14288 sd->nohz_idle = 0;
14290 atomic_inc(&sd->shared->nr_busy_cpus);
14297 if (likely(!rq->nohz_tick_stopped))
14300 rq->nohz_tick_stopped = 0;
14301 cpumask_clear_cpu(rq->cpu, nohz.idle_cpus_mask);
14303 set_cpu_sd_state_busy(rq->cpu);
14311 /* See set_cpu_sd_state_busy(): nohz_idle is only used with sd->shared. */
14312 if (!sd || !sd->shared || sd->nohz_idle)
14314 sd->nohz_idle = 1;
14316 atomic_dec(&sd->shared->nr_busy_cpus);
14334 * Can be set safely without rq->lock held
14336 * rq->lock is held during the check and the clear
14338 rq->has_blocked_load = 1;
14346 if (rq->nohz_tick_stopped)
14353 rq->nohz_tick_stopped = 1;
14377 unsigned int cpu = rq->cpu;
14379 if (!rq->has_blocked_load)
14385 if (!time_after(jiffies, READ_ONCE(rq->last_blocked_load_update_tick)))
14390 return rq->has_blocked_load;
14405 int this_cpu = this_rq->cpu;
14462 if (time_after_eq(jiffies, rq->next_balance)) {
14473 if (time_after(next_balance, rq->next_balance)) {
14474 next_balance = rq->next_balance;
14503 unsigned int flags = this_rq->nohz_idle_balance;
14508 this_rq->nohz_idle_balance = 0;
14549 int this_cpu = this_rq->cpu;
14552 if (this_rq->avg_idle < sysctl_sched_migration_cost)
14583 * < 0 - we released the lock and there are !fair tasks present
14584 * 0 - failed, no new tasks
14585 * > 0 - success, new (fair) tasks present
14591 int this_cpu = this_rq->cpu;
14603 if (this_rq->ttwu_pending)
14611 this_rq->idle_stamp = rq_clock(this_rq);
14621 * for load-balance and preemption/IRQs are still disabled avoiding
14623 * re-start the picking loop.
14627 sd = rcu_dereference_sched_domain(this_rq->sd);
14631 if (!get_rd_overloaded(this_rq->rd) ||
14632 this_rq->avg_idle < sd->max_newidle_lb_cost) {
14640 * calculation because it can be quite costly -- this ensures we skip
14654 if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost)
14657 if (sd->flags & SD_BALANCE_NEWIDLE) {
14660 if (sched_feat(NI_RANDOM) && sd->newidle_ratio < 1024) {
14667 weight = 1 + sd->newidle_ratio;
14680 domain_cost = t1 - t0;
14701 if (curr_cost > this_rq->max_idle_balance_cost)
14702 this_rq->max_idle_balance_cost = curr_cost;
14709 if (this_rq->cfs.h_nr_queued && !pulled_task)
14714 pulled_task = -1;
14718 if (time_after(this_rq->next_balance, next_balance))
14719 this_rq->next_balance = next_balance;
14722 this_rq->idle_stamp = 0;
14734 * - directly from the local sched_tick() for periodic load balancing
14736 * - indirectly from a remote sched_tick() for NOHZ idle balancing
14737 * through the SMP cross-call nohz_csd_func()
14742 enum cpu_idle_type idle = this_rq->idle_balance;
14755 sched_balance_update_blocked_averages(this_rq->cpu);
14771 if (time_after_eq(jiffies, rq->next_balance))
14799 u64 rtime = se->sum_exec_runtime - se->prev_sum_exec_runtime;
14800 u64 slice = se->slice;
14822 * MIN_NR_TASKS_DURING_FORCEIDLE - 1 tasks and use that to check
14825 if (rq->core->core_forceidle_count && rq->cfs.h_nr_queued == 1 &&
14826 __entity_slice_used(&curr->se, MIN_NR_TASKS_DURING_FORCEIDLE))
14842 * dt_i = ---------- dt (1)
14848 * s_i = --- d[t]_i (2)
14856 * S = ---------- dt (3)
14861 * lag(i) = S - s_i (4)
14873 * be learned. We can combine (1)-(3) or (4)-(5) and express S in s_i:
14876 * S = -------------- (6)
14881 * is two-fold. Firstly, computing S in that way requires a 64bit division
14883 * the steady-state, it doesn't handle dynamics.
14885 * Anyway, in (6): s_i -> x + (s_i - x), to get:
14887 * \Sum_i w_i (s_i - x)
14888 * S - x = -------------------- (7)
14895 * possible to generalize to multiple runqueues -- however it gets really
14897 * first counter-example.
14899 * Luckily I think we can avoid needing a full multi-queue variant for
14900 * core-scheduling (or load-balancing). The crucial observation is that we
14901 * only actually need this comparison in the presence of forced-idle; only
14907 * answer is only interesting if one of them is forced-idle]
14909 * And (under assumption of SMT2) when there is forced-idle, there is only
14920 * S_k = --- (9)
14926 * S_k+l = --------- (10)
14931 * lag_k+l(i) := S_k+l - s_i (11)
14938 * a) when a runqueue enters force-idle, sync it against it's sibling rq(s)
14939 * using (7); this only requires storing single 'time'-stamps.
14941 * b) when comparing tasks between 2 runqueues of which one is forced-idle,
14946 * boundaries, but I think we can avoid that. The force-idle is for the
14956 * get re-elected. So far so simple, right?
14959 * we sync to 0 and let the idle one build up lag to get re-election. Now
14961 * again would destroy the built-up lag from the queue that was already
14966 * less := !((s64)(s_a - s_b) <= 0)
14968 * (v_a - S_a) - (v_b - S_b) == v_a - v_b - S_a + S_b
14969 * == v_a - (v_b - S_a + S_b)
14971 * IOW, we can recast the (lag) comparison to a one-sided difference.
14978 * and for already idle queues to preserve their build-up lag.
14994 * se_fi_update - Update the cfs_rq->zero_vruntime_fi in a CFS hierarchy if needed.
15003 if (cfs_rq->forceidle_seq == fi_seq)
15005 cfs_rq->forceidle_seq = fi_seq;
15008 cfs_rq->zero_vruntime_fi = cfs_rq->zero_vruntime;
15014 struct sched_entity *se = &p->se;
15016 if (p->sched_class != &fair_sched_class)
15019 se_fi_update(se, rq->core->core_forceidle_seq, in_fi);
15026 const struct sched_entity *sea = &a->se;
15027 const struct sched_entity *seb = &b->se;
15032 WARN_ON_ONCE(task_rq(b)->core != rq->core);
15034 cfs_rqa = &task_rq(a)->cfs;
15035 cfs_rqb = &task_rq(b)->cfs;
15042 delta = vruntime_op(sea->vruntime, "-", seb->vruntime) +
15043 vruntime_op(cfs_rqb->zero_vruntime_fi, "-", cfs_rqa->zero_vruntime_fi);
15055 cfs_rq = &cpu_rq(cpu)->cfs;
15073 struct sched_entity *se = &curr->se;
15075 if (se->on_rq) {
15086 se = &curr->se;
15087 reweight_eevdf(cfs_rq, se, weight, se->on_rq);
15106 * - child not yet on the tasklist
15107 * - preemption disabled
15124 if (p->prio == oldprio)
15127 if (rq->cfs.h_nr_queued == 1)
15136 if (p->prio > oldprio)
15162 se = se->parent;
15185 * - A forked task which hasn't been woken up by wake_up_new_task().
15186 * - A task which has been woken up by try_to_wake_up() but is
15189 if (!se->avg.last_update_time)
15212 struct sched_entity *se = &p->se;
15219 struct sched_entity *se = &p->se;
15226 if (p->se.sched_delayed)
15237 WARN_ON_ONCE(p->se.sched_delayed);
15258 struct sched_entity *se = &p->se;
15260 struct cfs_rq *cfs_rq = &rq->cfs;
15262 bool on_rq = se->on_rq;
15273 !first || !cfs_rq->h_curr)
15286 se = &p->se;
15287 cfs_rq->curr = se;
15290 reweight_eevdf(cfs_rq, se, weight, se->on_rq);
15300 list_move(&se->group_node, &rq->cfs_tasks);
15305 WARN_ON_ONCE(se->sched_delayed);
15316 cfs_rq->tasks_timeline = RB_ROOT_CACHED;
15317 cfs_rq->zero_vruntime = (u64)(-(1LL << 20));
15318 raw_spin_lock_init(&cfs_rq->removed.lock);
15328 if (READ_ONCE(p->__state) == TASK_NEW)
15333 /* Tell se's cfs_rq has been changed -- migrated */
15334 p->se.avg.last_update_time = 0;
15341 free_percpu(tg->cfs_rq);
15355 tg->cfs_rq = &state->cfs_rq;
15356 tg->shares = NICE_0_LOAD;
15411 * check on_list without danger of it being re-added.
15413 if (cfs_rq->on_list) {
15426 cfs_rq->tg = tg;
15427 cfs_rq->rq = rq;
15435 se->cfs_rq = &rq->cfs;
15436 se->depth = 0;
15438 se->cfs_rq = parent->my_q;
15439 se->depth = parent->depth + 1;
15442 se->my_q = cfs_rq;
15444 update_load_set(&se->load, NICE_0_LOAD);
15445 se->parent = parent;
15460 return -EINVAL;
15464 if (tg->shares == shares)
15467 tg->shares = shares;
15492 ret = -EINVAL;
15505 return -EINVAL;
15508 return -EINVAL;
15512 if (tg->idle == idle) {
15517 tg->idle = idle;
15529 grp_cfs_rq->idle = idle;
15533 idle_task_delta = grp_cfs_rq->h_nr_queued -
15534 grp_cfs_rq->h_nr_idle;
15536 idle_task_delta *= -1;
15541 if (!se->on_rq)
15544 cfs_rq->h_nr_idle += idle_task_delta;
15570 struct sched_entity *se = &task->se;
15577 if (rq->cfs.load.weight)
15578 rr_interval = NS_TO_JIFFIES(se->slice);
15651 ng = rcu_dereference_all(p->numa_group);
15653 if (p->numa_faults) {
15654 tsf = p->numa_faults[task_faults_idx(NUMA_MEM, node, 0)];
15655 tpf = p->numa_faults[task_faults_idx(NUMA_MEM, node, 1)];
15658 gsf = ng->faults[task_faults_idx(NUMA_MEM, node, 0)];
15659 gpf = ng->faults[task_faults_idx(NUMA_MEM, node, 1)];
15678 INIT_CSD(&cpu_rq(i)->cfsb_csd, __cfsb_csd_unthrottle, cpu_rq(i));
15679 INIT_LIST_HEAD(&cpu_rq(i)->cfsb_csd_list);