Lines Matching +full:idlest +full:- +full:shift
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
261 * we're guaranteed shift stays positive because inv_weight is guaranteed to
262 * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
265 * weight/lw.weight <= 1, and therefore our shift will also be positive.
271 int shift = WMULT_SHIFT;
278 shift -= fs;
282 fact = mul_u32_u32(fact, lw->inv_weight);
287 shift -= fs;
291 return mul_u64_u32_shr(delta_exec, fact, shift);
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(grp->footprint);
1514 * 784GB = (1 + (99 - 1) * 256) * 32MB
1545 return !fits_capacity((READ_ONCE(grp->nr_running_avg) * cpu_smt_num_threads),
1556 return p->pref_llc_queued && !p->se.sched_delayed;
1562 rq->nr_pref_llc_running++;
1568 rq->nr_pref_llc_running--;
1576 pref_llc = p->preferred_llc;
1581 rq->nr_llc_running++;
1593 * can cause inconsistent values - checking the
1594 * p->pref_llc_queued in account_llc_dequeue() would
1597 p->pref_llc_queued = pref_llc_queued;
1602 sd = rcu_dereference_all(rq->sd);
1603 if (sd && (unsigned int)pref_llc < sd->llc_max)
1604 sd->llc_counts[pref_llc]++;
1612 pref_llc = p->preferred_llc;
1616 rq->nr_llc_running--;
1617 if (p->pref_llc_queued) {
1621 * from re-adding it.
1629 p->pref_llc_queued = 0;
1632 sd = rcu_dereference_all(rq->sd);
1633 if (sd && (unsigned int)pref_llc < sd->llc_max) {
1639 * and reset statistics to zero(including sd->llc_counts).
1641 * check for such underflow in sd->llc_counts.
1646 if (sd->llc_counts[pref_llc])
1647 sd->llc_counts[pref_llc]--;
1661 mm->sched_cache_grp = NULL;
1662 return -ENOMEM;
1669 pcpu_sched->runtime = 0;
1671 pcpu_sched->epoch = rq->cpu_epoch;
1672 epoch = rq->cpu_epoch;
1675 raw_spin_lock_init(&grp->lock);
1676 grp->epoch = epoch;
1677 grp->cpu = -1;
1678 grp->next_scan = jiffies;
1679 grp->nr_running_avg = 0;
1680 grp->footprint = 0;
1681 refcount_set(&grp->refcnt, 1);
1683 * The update to grp->pcpu_sched should not be reordered
1687 smp_store_release(&grp->pcpu_sched, _pcpu_sched);
1690 * grp->pcpu_sched - can_migrate_llc_task() only checks that the
1691 * pointer is non-NULL before reading grp->footprint and
1692 * grp->nr_running_avg - so a reachable group must already be
1695 smp_store_release(&mm->sched_cache_grp, grp);
1704 free_percpu(grp->pcpu_sched);
1710 if (!grp || !refcount_dec_and_test(&grp->refcnt))
1713 call_rcu(&grp->rcu, sched_cache_group_free_rcu);
1720 rcu_dereference_check((tsk)->sched_cache_grp, (tsk) == current)
1728 rcu_assign_pointer(p->sched_cache_grp, new);
1740 if (grp && !refcount_inc_not_zero(&grp->refcnt))
1749 return sched_cache_group_get(rcu_dereference(p->sched_cache_grp));
1759 RCU_INIT_POINTER(p->sched_cache_grp,
1760 sched_cache_group_get(p->mm->sched_cache_grp));
1770 sched_cache_group_put(rcu_access_pointer(p->sched_cache_grp));
1771 RCU_INIT_POINTER(p->sched_cache_grp, NULL);
1782 old = sched_cache_replace_grp(p, sched_cache_group_get(mm->sched_cache_grp));
1796 if (grp && p->total_numa_faults) {
1797 unsigned long fp = READ_ONCE(grp->footprint);
1798 unsigned long sub = min(fp, p->total_numa_faults);
1800 WRITE_ONCE(grp->footprint, fp - sub);
1808 sched_cache_group_put(mm->sched_cache_grp);
1809 mm->sched_cache_grp = NULL;
1825 lockdep_assert_held(&rq->cpu_epoch_lock);
1829 long delta = now - rq->cpu_epoch_next;
1832 n = (delta + period - 1) / period;
1833 rq->cpu_epoch += n;
1834 rq->cpu_epoch_next += n * period;
1835 __shr_u64(&rq->cpu_runtime, n);
1838 n = rq->cpu_epoch - pcpu_sched->epoch;
1840 pcpu_sched->epoch += n;
1841 __shr_u64(&pcpu_sched->runtime, n);
1848 guard(raw_spinlock_irqsave)(&rq->cpu_epoch_lock);
1857 return div64_u64(NICE_0_LOAD * pcpu_sched->runtime, rq->cpu_runtime + 1);
1862 int mm_sched_llc = -1, mm_sched_cpu;
1865 return -1;
1867 mm_sched_cpu = READ_ONCE(grp->cpu);
1868 if (mm_sched_cpu != -1) {
1878 * called fairly regularly -- at a higher rate
1879 * than sched_setnuma() at least -- and thus the
1883 p->numa_preferred_nid >= 0 &&
1884 cpu_to_node(mm_sched_cpu) != p->numa_preferred_nid)
1885 mm_sched_llc = -1;
1897 struct sched_cache_group *grp = rcu_dereference_all(p->sched_cache_grp);
1899 int mm_sched_llc = -1;
1905 if (p->sched_class != &fair_sched_class)
1912 * invoked for a kernel thread - !grp should gate the
1917 if (p->flags & PF_KTHREAD || !grp || !grp->pcpu_sched)
1920 pcpu_sched = per_cpu_ptr(grp->pcpu_sched, cpu_of(rq));
1922 scoped_guard (raw_spinlock, &rq->cpu_epoch_lock) {
1924 pcpu_sched->runtime += delta_exec;
1925 rq->cpu_runtime += delta_exec;
1926 epoch = rq->cpu_epoch;
1933 if ((long)(epoch - READ_ONCE(grp->epoch)) > llc_epoch_affinity_timeout ||
1936 if (READ_ONCE(grp->cpu) != -1)
1937 WRITE_ONCE(grp->cpu, -1);
1943 if (task_running_on_cpu(rq->cpu, p) &&
1944 READ_ONCE(p->preferred_llc) != mm_sched_llc) {
1946 WRITE_ONCE(p->preferred_llc, mm_sched_llc);
1953 struct sched_cache_group *grp = rcu_dereference_all(p->sched_cache_grp);
1954 struct callback_head *work = &p->cache_work;
1960 if (!grp || p->flags & PF_KTHREAD ||
1961 !grp->pcpu_sched)
1964 epoch = rq->cpu_epoch;
1966 if (time_after_eq(grp->epoch, epoch))
1969 guard(raw_spinlock)(&grp->lock);
1971 if (work->next == work) {
1973 WRITE_ONCE(grp->epoch, epoch);
1986 cpu = READ_ONCE(grp->cpu);
1987 if (cpu != -1)
1993 * preferred node is per-task rather than per-process. It is possible
1995 * nodes; consequently, the process-wide preferred LLC may bounce
2001 pref_nid = p->numa_preferred_nid;
2009 if (cpu != -1 && !cpumask_test_cpu(cpu, cpus) && nid != NUMA_NO_NODE)
2026 s64 diff = sample - *avg;
2045 int cpu, m_a_cpu = -1, nr_running = 0, curr_cpu;
2051 WARN_ON_ONCE(work != &p->cache_work);
2053 work->next = work;
2055 if (p->flags & PF_EXITING)
2067 next_scan = READ_ONCE(grp->next_scan);
2072 if (!try_cmpxchg(&grp->next_scan, &next_scan,
2080 if (READ_ONCE(grp->cpu) != -1)
2081 WRITE_ONCE(grp->cpu, -1);
2098 int m_cpu = -1, i;
2105 per_cpu_ptr(grp->pcpu_sched, i));
2116 cur = rcu_dereference_all(cpu_rq(i)->curr);
2117 if (cur && !(cur->flags & (PF_EXITING | PF_KTHREAD)) &&
2118 rcu_access_pointer(cur->sched_cache_grp) == grp)
2142 if (llc_id(cpu) == llc_id(READ_ONCE(grp->cpu)))
2151 * Avoid switching sched_cache_grp->cpu too fast.
2160 WRITE_ONCE(grp->cpu, m_a_cpu);
2163 update_avg_scale(&grp->nr_running_avg, nr_running);
2168 struct callback_head *work = &p->cache_work;
2171 work->next = work;
2175 * here - before copy_mm() runs - so the child never carries a
2178 RCU_INIT_POINTER(p->sched_cache_grp, NULL);
2183 p->preferred_llc = -1;
2184 p->pref_llc_queued = 0;
2199 return -1;
2217 return update_se(rq, &rq->donor->se);
2226 * Note: cfs_rq->curr corresponds to the task picked to
2227 * run (ie: rq->donor.se) which due to proxy-exec may
2229 * (rq->curr.se). This is easy to confuse!
2231 struct sched_entity *curr = cfs_rq->h_curr;
2248 cfs_rq = &rq->cfs;
2250 curr->vruntime += calc_delta_fair(delta_exec, curr);
2257 * - If the task is running on behalf of fair_server, we need
2259 * - Fair task that runs outside of fair_server should account
2263 dl_server_update(&rq->fair_server, delta_exec);
2265 if (cfs_rq->h_nr_queued == 1)
2276 struct sched_entity *se = &rq->donor->se;
2312 * maybe already in the runqueue, the se->statistics.wait_start
2316 if (unlikely(!schedstat_val(stats->wait_start)))
2343 * Task is being enqueued - update stats:
2355 if (se != cfs_rq->h_curr)
2373 if (se != cfs_rq->h_curr)
2381 state = READ_ONCE(tsk->__state);
2383 __schedstat_set(tsk->stats.sleep_start,
2386 __schedstat_set(tsk->stats.block_start,
2392 * We are picking a new current task - update its stats:
2400 se->exec_start = rq_clock_task(rq_of(cfs_rq));
2487 * ->numa_group (see struct task_struct for locking rules).
2491 return rcu_dereference_check(p->numa_group, p == current ||
2492 (lockdep_is_held(__rq_lockp(task_rq(p))) && !READ_ONCE(p->on_cpu)));
2497 return rcu_dereference_protected(p->numa_group, p == current);
2509 * Calculations based on RSS as non-present and empty pages are skipped
2514 rss = get_mm_rss(p->mm);
2547 ng = rcu_dereference_all(p->numa_group);
2552 period *= refcount_read(&ng->refcount);
2577 period *= refcount_read(&ng->refcount);
2589 rq->nr_numa_running += (p->numa_preferred_nid != NUMA_NO_NODE);
2590 rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
2595 rq->nr_numa_running -= (p->numa_preferred_nid != NUMA_NO_NODE);
2596 rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
2614 ng = rcu_dereference_all(p->numa_group);
2616 gid = ng->gid;
2635 if (!p->numa_faults)
2638 return p->numa_faults[task_faults_idx(NUMA_MEM, nid, 0)] +
2639 p->numa_faults[task_faults_idx(NUMA_MEM, nid, 1)];
2649 return ng->faults[task_faults_idx(NUMA_MEM, nid, 0)] +
2650 ng->faults[task_faults_idx(NUMA_MEM, nid, 1)];
2655 return group->faults[task_faults_idx(NUMA_CPU, nid, 0)] +
2656 group->faults[task_faults_idx(NUMA_CPU, nid, 1)];
2665 faults += ng->faults[task_faults_idx(NUMA_MEM, node, 1)];
2677 faults += ng->faults[task_faults_idx(NUMA_MEM, node, 0)];
2685 * considered part of a numa group's pseudo-interleaving set. Migrations
2692 return group_faults_cpu(ng, nid) * ACTIVE_NODE_FRACTION > ng->max_faults_cpu;
2751 faults *= (max_dist - dist);
2752 faults /= (max_dist - LOCAL_DISTANCE);
2772 if (!p->numa_faults)
2775 total_faults = p->total_numa_faults;
2795 total_faults = ng->total_faults;
2831 pgdat->node_present_pages >> 4);
2832 for (z = pgdat->nr_zones - 1; z >= 0; z--) {
2833 struct zone *zone = pgdat->node_zones + z;
2853 * hint page fault latency = hint page fault time - scan time
2865 return (time - last_time) & PAGE_ACCESS_TIME_MASK;
2882 start = pgdat->nbp_rl_start;
2883 if (now - start > MSEC_PER_SEC &&
2884 cmpxchg(&pgdat->nbp_rl_start, start, now) == start)
2885 pgdat->nbp_rl_nr_cand = nr_cand;
2886 if (nr_cand - pgdat->nbp_rl_nr_cand >= rate_limit)
2902 start = pgdat->nbp_th_start;
2903 if (now - start > th_period &&
2904 cmpxchg(&pgdat->nbp_th_start, start, now) == start) {
2908 diff_cand = nr_cand - pgdat->nbp_th_nr_cand;
2910 th = pgdat->nbp_threshold ? : ref_th;
2912 th = max(th - unit_th, unit_th);
2915 pgdat->nbp_th_nr_cand = nr_cand;
2916 pgdat->nbp_threshold = th;
2946 pgdat->nbp_threshold = 0;
2955 th = pgdat->nbp_threshold ? : def_th;
2963 this_cpupid = cpu_pid_to_cpupid(dst_cpu, current->pid);
2973 * two full passes of the "multi-stage node selection" test that is
2976 if ((p->numa_preferred_nid == NUMA_NO_NODE || p->numa_scan_seq <= 4) &&
2981 * Multi-stage node selection is used in conjunction with a periodic
2982 * migration fault to build a temporal task<->page relation. By using
2983 * a two-stage filter we remove short/unlikely relations.
2987 * page (n_t) (in a given time-span) to a probability.
2995 * act on an unlikely task<->page relation.
3005 /* A shared fault, but p->numa_group has not been set up yet. */
3022 * --------------- * - > ---------------
3084 if ((ns->nr_running > ns->weight) &&
3085 (((ns->compute_capacity * 100) < (ns->util * imbalance_pct)) ||
3086 ((ns->compute_capacity * imbalance_pct) < (ns->runnable * 100))))
3089 if ((ns->nr_running < ns->weight) ||
3090 (((ns->compute_capacity * 100) > (ns->util * imbalance_pct)) &&
3091 ((ns->compute_capacity * imbalance_pct) > (ns->runnable * 100))))
3125 int cpu, idle_core = -1;
3128 ns->idle_cpu = -1;
3134 ns->load += cpu_load(rq);
3135 ns->runnable += cpu_runnable(rq);
3136 ns->util += cpu_util_cfs(cpu);
3137 ns->nr_running += rq->cfs.h_nr_runnable;
3138 ns->compute_capacity += capacity_of(cpu);
3140 if (find_idle && idle_core < 0 && !rq->nr_running && idle_cpu(cpu)) {
3141 if (READ_ONCE(rq->numa_migrate_on) ||
3142 !cpumask_test_cpu(cpu, env->p->cpus_ptr))
3145 if (ns->idle_cpu == -1)
3146 ns->idle_cpu = cpu;
3153 ns->weight = cpumask_weight(cpumask_of_node(nid));
3155 ns->node_type = numa_classify(env->imbalance_pct, ns);
3158 ns->idle_cpu = idle_core;
3164 struct rq *rq = cpu_rq(env->dst_cpu);
3166 /* Check if run-queue part of active NUMA balance. */
3167 if (env->best_cpu != env->dst_cpu && xchg(&rq->numa_migrate_on, 1)) {
3169 int start = env->dst_cpu;
3172 for_each_cpu_wrap(cpu, cpumask_of_node(env->dst_nid), start + 1) {
3173 if (cpu == env->best_cpu || !idle_cpu(cpu) ||
3174 !cpumask_test_cpu(cpu, env->p->cpus_ptr)) {
3178 env->dst_cpu = cpu;
3179 rq = cpu_rq(env->dst_cpu);
3180 if (!xchg(&rq->numa_migrate_on, 1))
3190 * Clear previous best_cpu/rq numa-migrate flag, since task now
3193 if (env->best_cpu != -1 && env->best_cpu != env->dst_cpu) {
3194 rq = cpu_rq(env->best_cpu);
3195 WRITE_ONCE(rq->numa_migrate_on, 0);
3198 if (env->best_task)
3199 put_task_struct(env->best_task);
3203 env->best_task = p;
3204 env->best_imp = imp;
3205 env->best_cpu = env->dst_cpu;
3219 * ------------ vs ---------
3222 src_capacity = env->src_stats.compute_capacity;
3223 dst_capacity = env->dst_stats.compute_capacity;
3225 imb = abs(dst_load * src_capacity - src_load * dst_capacity);
3227 orig_src_load = env->src_stats.load;
3228 orig_dst_load = env->dst_stats.load;
3230 old_imb = abs(orig_dst_load * src_capacity - orig_src_load * dst_capacity);
3252 struct numa_group *cur_ng, *p_ng = deref_curr_numa_group(env->p);
3253 struct rq *dst_rq = cpu_rq(env->dst_cpu);
3257 int dist = env->dist;
3262 if (READ_ONCE(dst_rq->numa_migrate_on))
3266 cur = rcu_dereference_all(dst_rq->curr);
3267 if (cur && ((cur->flags & (PF_EXITING | PF_KTHREAD)) ||
3268 !cur->mm))
3273 * end try selecting ourselves (current == env->p) as a swap candidate.
3275 if (cur == env->p) {
3281 if (maymove && moveimp >= env->best_imp)
3288 if (!cpumask_test_cpu(env->src_cpu, cur->cpus_ptr))
3295 if (env->best_task &&
3296 env->best_task->numa_preferred_nid == env->src_nid &&
3297 cur->numa_preferred_nid != env->src_nid) {
3311 cur_ng = rcu_dereference_all(cur->numa_group);
3319 if (env->dst_stats.node_type == node_has_spare)
3322 imp = taskimp + task_weight(cur, env->src_nid, dist) -
3323 task_weight(cur, env->dst_nid, dist);
3329 imp -= imp / 16;
3336 imp += group_weight(cur, env->src_nid, dist) -
3337 group_weight(cur, env->dst_nid, dist);
3339 imp += task_weight(cur, env->src_nid, dist) -
3340 task_weight(cur, env->dst_nid, dist);
3344 if (cur->numa_preferred_nid == env->dst_nid)
3345 imp -= imp / 16;
3353 if (cur->numa_preferred_nid == env->src_nid)
3356 if (maymove && moveimp > imp && moveimp > env->best_imp) {
3366 if (env->best_task && cur->numa_preferred_nid == env->src_nid &&
3367 env->best_task->numa_preferred_nid != env->src_nid) {
3377 if (imp < SMALLIMP || imp <= env->best_imp + SMALLIMP / 2)
3383 load = task_h_load(env->p) - task_h_load(cur);
3387 dst_load = env->dst_stats.load + load;
3388 src_load = env->src_stats.load - load;
3396 int cpu = env->dst_stats.idle_cpu;
3400 cpu = env->dst_cpu;
3406 if (!idle_cpu(cpu) && env->best_cpu >= 0 &&
3407 idle_cpu(env->best_cpu)) {
3408 cpu = env->best_cpu;
3411 env->dst_cpu = cpu;
3421 if (maymove && !cur && env->best_cpu >= 0 && idle_cpu(env->best_cpu))
3428 if (!maymove && env->best_task &&
3429 env->best_task->numa_preferred_nid == env->src_nid) {
3448 if (env->dst_stats.node_type == node_has_spare) {
3458 src_running = env->src_stats.nr_running - 1;
3459 dst_running = env->dst_stats.nr_running + 1;
3460 imbalance = max(0, dst_running - src_running);
3462 env->imb_numa_nr);
3467 if (env->dst_stats.idle_cpu >= 0) {
3468 env->dst_cpu = env->dst_stats.idle_cpu;
3476 * If the improvement from just moving env->p direction is better
3479 load = task_h_load(env->p);
3480 dst_load = env->dst_stats.load + load;
3481 src_load = env->src_stats.load - load;
3486 for_each_cpu_and(cpu, cpumask_of_node(env->dst_nid), env->p->cpus_ptr) {
3487 env->dst_cpu = cpu;
3505 .best_cpu = -1,
3519 * random movement of tasks -- counter the numa conditions we're trying
3525 env.imbalance_pct = 100 + (sd->imbalance_pct - 100) / 2;
3526 env.imb_numa_nr = sd->imb_numa_nr;
3538 return -EINVAL;
3541 env.dst_nid = p->numa_preferred_nid;
3546 taskimp = task_weight(p, env.dst_nid, dist) - taskweight;
3547 groupimp = group_weight(p, env.dst_nid, dist) - groupweight;
3555 * - there is no space available on the preferred_nid
3556 * - the task is part of a numa_group that is interleaved across
3561 if (env.best_cpu == -1 || (ng && ng->active_nodes > 1)) {
3563 if (nid == env.src_nid || nid == p->numa_preferred_nid)
3574 taskimp = task_weight(p, nid, dist) - taskweight;
3575 groupimp = group_weight(p, nid, dist) - groupweight;
3595 if (env.best_cpu == -1)
3600 if (nid != p->numa_preferred_nid)
3605 if (env.best_cpu == -1) {
3606 trace_sched_stick_numa(p, env.src_cpu, NULL, -1);
3607 return -EAGAIN;
3613 WRITE_ONCE(best_rq->numa_migrate_on, 0);
3620 WRITE_ONCE(best_rq->numa_migrate_on, 0);
3634 if (unlikely(p->numa_preferred_nid == NUMA_NO_NODE || !p->numa_faults))
3638 interval = min(interval, msecs_to_jiffies(p->numa_scan_period) / 16);
3639 p->numa_migrate_retry = jiffies + interval;
3642 if (task_node(p) == p->numa_preferred_nid)
3672 numa_group->max_faults_cpu = max_faults;
3673 numa_group->active_nodes = active_nodes;
3699 unsigned long remote = p->numa_faults_locality[0];
3700 unsigned long local = p->numa_faults_locality[1];
3709 if (local + shared == 0 || p->numa_faults_locality[2]) {
3710 p->numa_scan_period = min(p->numa_scan_period_max,
3711 p->numa_scan_period << 1);
3713 p->mm->numa_next_scan = jiffies +
3714 msecs_to_jiffies(p->numa_scan_period);
3725 period_slot = DIV_ROUND_UP(p->numa_scan_period, NUMA_PERIOD_SLOTS);
3734 int slot = ps_ratio - NUMA_PERIOD_THRESHOLD;
3744 int slot = lr_ratio - NUMA_PERIOD_THRESHOLD;
3750 * Private memory faults exceed (SLOTS-THRESHOLD)/SLOTS,
3755 diff = -(NUMA_PERIOD_THRESHOLD - ratio) * period_slot;
3758 p->numa_scan_period = clamp(p->numa_scan_period + diff,
3760 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
3767 * from the dozens-of-seconds NUMA balancing period. Use the scheduler
3774 now = p->se.exec_start;
3775 runtime = p->se.sum_exec_runtime;
3777 if (p->last_task_numa_placement) {
3778 delta = runtime - p->last_sum_exec_runtime;
3779 *period = now - p->last_task_numa_placement;
3785 delta = p->se.avg.load_sum;
3789 p->last_sum_exec_runtime = runtime;
3790 p->last_task_numa_placement = now;
3840 for (dist = sched_max_numa_distance; dist > LOCAL_DISTANCE; dist--) {
3897 * The p->mm->numa_scan_seq field gets updated without
3901 seq = READ_ONCE(p->mm->numa_scan_seq);
3902 if (p->numa_scan_seq == seq)
3904 p->numa_scan_seq = seq;
3905 p->numa_scan_period_max = task_scan_max(p);
3907 total_faults = p->numa_faults_locality[0] +
3908 p->numa_faults_locality[1];
3914 group_lock = &ng->lock;
3934 diff = p->numa_faults[membuf_idx] - p->numa_faults[mem_idx] / 2;
3935 fault_types[priv] += p->numa_faults[membuf_idx];
3936 p->numa_faults[membuf_idx] = 0;
3942 * little over-all impact on throughput, and thus their
3946 f_weight = (f_weight * p->numa_faults[cpubuf_idx]) /
3948 f_diff = f_weight - p->numa_faults[cpu_idx] / 2;
3949 p->numa_faults[cpubuf_idx] = 0;
3951 p->numa_faults[mem_idx] += diff;
3952 p->numa_faults[cpu_idx] += f_diff;
3953 faults += p->numa_faults[mem_idx];
3954 p->total_numa_faults += diff;
3963 ng->faults[mem_idx] += diff;
3964 ng->faults[cpu_idx] += f_diff;
3965 ng->total_faults += diff;
3966 group_faults += ng->faults[mem_idx];
3970 * Per task p->numa_faults[mem_idx] converges,
3972 * converges too - Given the number of threads,
3979 * be subtracted from p->sched_cache_grp->footprint,
3990 grp = rcu_dereference(p->sched_cache_grp);
3993 new_fp = (long)READ_ONCE(grp->footprint) + diff;
3994 WRITE_ONCE(grp->footprint, max(new_fp, 0L));
4011 /* Cannot migrate task to CPU-less node */
4022 if (max_nid != p->numa_preferred_nid)
4031 return refcount_inc_not_zero(&grp->refcount);
4036 if (refcount_dec_and_test(&grp->refcount))
4058 refcount_set(&grp->refcount, 1);
4059 grp->active_nodes = 1;
4060 grp->max_faults_cpu = 0;
4061 spin_lock_init(&grp->lock);
4062 grp->gid = p->pid;
4065 grp->faults[i] = p->numa_faults[i];
4067 grp->total_faults = p->total_numa_faults;
4069 grp->nr_tasks++;
4070 rcu_assign_pointer(p->numa_group, grp);
4074 tsk = READ_ONCE(cpu_rq(cpu)->curr);
4079 grp = rcu_dereference_all(tsk->numa_group);
4091 if (my_grp->nr_tasks > grp->nr_tasks)
4095 * Tie-break on the grp address.
4097 if (my_grp->nr_tasks == grp->nr_tasks && my_grp > grp)
4101 if (tsk->mm == current->mm)
4120 double_lock_irq(&my_grp->lock, &grp->lock);
4123 my_grp->faults[i] -= p->numa_faults[i];
4124 grp->faults[i] += p->numa_faults[i];
4126 my_grp->total_faults -= p->total_numa_faults;
4127 grp->total_faults += p->total_numa_faults;
4129 my_grp->nr_tasks--;
4130 grp->nr_tasks++;
4132 spin_unlock(&my_grp->lock);
4133 spin_unlock_irq(&grp->lock);
4135 rcu_assign_pointer(p->numa_group, grp);
4150 * reset the data back to default state without freeing ->numa_faults.
4155 struct numa_group *grp = rcu_dereference_raw(p->numa_group);
4156 unsigned long *numa_faults = p->numa_faults;
4164 spin_lock_irqsave(&grp->lock, flags);
4166 grp->faults[i] -= p->numa_faults[i];
4167 grp->total_faults -= p->total_numa_faults;
4169 grp->nr_tasks--;
4170 spin_unlock_irqrestore(&grp->lock, flags);
4171 RCU_INIT_POINTER(p->numa_group, NULL);
4176 p->numa_faults = NULL;
4179 p->total_numa_faults = 0;
4201 if (!p->mm)
4213 /* Allocate buffer to track faults on a per-node basis */
4214 if (unlikely(!p->numa_faults)) {
4215 int size = sizeof(*p->numa_faults) *
4218 p->numa_faults = kzalloc(size, GFP_KERNEL|__GFP_NOWARN);
4219 if (!p->numa_faults)
4222 p->total_numa_faults = 0;
4223 memset(p->numa_faults_locality, 0, sizeof(p->numa_faults_locality));
4230 if (unlikely(last_cpupid == (-1 & LAST_CPUPID_MASK))) {
4245 if (!priv && !local && ng && ng->active_nodes > 1 &&
4254 if (time_after(jiffies, p->numa_migrate_retry)) {
4260 p->numa_pages_migrated += pages;
4262 p->numa_faults_locality[2] += pages;
4264 p->numa_faults[task_faults_idx(NUMA_MEMBUF, mem_node, priv)] += pages;
4265 p->numa_faults[task_faults_idx(NUMA_CPUBUF, cpu_node, priv)] += pages;
4266 p->numa_faults_locality[local] += pages;
4273 * p->mm->numa_scan_seq is written to without exclusive access
4279 WRITE_ONCE(p->mm->numa_scan_seq, READ_ONCE(p->mm->numa_scan_seq) + 1);
4280 p->mm->numa_scan_offset = 0;
4292 if ((READ_ONCE(current->mm->numa_scan_seq) - vma->numab_state->start_scan_seq) < 2)
4295 pids = vma->numab_state->pids_active[0] | vma->numab_state->pids_active[1];
4296 if (test_bit(hash_32(current->pid, ilog2(BITS_PER_LONG)), &pids))
4301 * some VMAs may never be scanned in multi-threaded applications:
4303 if (mm->numa_scan_offset > vma->vm_start) {
4313 if (READ_ONCE(mm->numa_scan_seq) >
4314 (vma->numab_state->prev_scan_seq + get_nr_threads(current)))
4330 struct mm_struct *mm = p->mm;
4331 u64 runtime = p->se.sum_exec_runtime;
4342 work->next = work;
4346 * NOTE: make sure not to dereference p->mm before this check,
4348 * without p->mm even though we still had it when we enqueued this
4351 if (p->flags & PF_EXITING)
4363 if (!mm->numa_next_scan) {
4364 mm->numa_next_scan = now +
4371 migrate = mm->numa_next_scan;
4375 if (p->numa_scan_period == 0) {
4376 p->numa_scan_period_max = task_scan_max(p);
4377 p->numa_scan_period = task_scan_start(p);
4380 next_scan = now + msecs_to_jiffies(p->numa_scan_period);
4381 if (!try_cmpxchg(&mm->numa_next_scan, &migrate, next_scan))
4388 p->node_stamp += 2 * TICK_NSEC;
4391 pages <<= 20 - PAGE_SHIFT; /* MB in pages */
4408 start = mm->numa_scan_offset;
4420 is_vm_hugetlb_page(vma) || (vma->vm_flags & VM_MIXEDMAP)) {
4428 * hinting faults in read-only file-backed mappings or the vDSO
4431 if (!vma->vm_mm ||
4432 (vma->vm_file && (vma->vm_flags & (VM_READ|VM_WRITE)) == (VM_READ))) {
4446 /* Initialise new per-VMA NUMAB state. */
4447 if (!vma->numab_state) {
4454 if (cmpxchg(&vma->numab_state, NULL, ptr)) {
4459 vma->numab_state->start_scan_seq = mm->numa_scan_seq;
4461 vma->numab_state->next_scan = now +
4465 vma->numab_state->pids_active_reset = vma->numab_state->next_scan +
4473 vma->numab_state->prev_scan_seq = mm->numa_scan_seq - 1;
4480 if (mm->numa_scan_seq && time_before(jiffies,
4481 vma->numab_state->next_scan)) {
4487 if (mm->numa_scan_seq &&
4488 time_after(jiffies, vma->numab_state->pids_active_reset)) {
4489 vma->numab_state->pids_active_reset = vma->numab_state->pids_active_reset +
4491 vma->numab_state->pids_active[0] = READ_ONCE(vma->numab_state->pids_active[1]);
4492 vma->numab_state->pids_active[1] = 0;
4496 if (vma->numab_state->prev_scan_seq == mm->numa_scan_seq) {
4497 mm->numa_scan_offset = vma->vm_end;
4513 start = max(start, vma->vm_start);
4515 end = min(end, vma->vm_end);
4521 * is not already PTE-numa. If the VMA contains
4527 pages -= (end - start) >> PAGE_SHIFT;
4528 virtpages -= (end - start) >> PAGE_SHIFT;
4535 } while (end != vma->vm_end);
4538 vma->numab_state->prev_scan_seq = mm->numa_scan_seq;
4566 mm->numa_scan_offset = start;
4577 if (unlikely(p->se.sum_exec_runtime != runtime)) {
4578 u64 diff = p->se.sum_exec_runtime - runtime;
4579 p->node_stamp += 32 * diff;
4586 struct mm_struct *mm = p->mm;
4589 mm_users = atomic_read(&mm->mm_users);
4591 mm->numa_next_scan = jiffies + msecs_to_jiffies(sysctl_numa_balancing_scan_delay);
4592 mm->numa_scan_seq = 0;
4595 p->node_stamp = 0;
4596 p->numa_scan_seq = mm ? mm->numa_scan_seq : 0;
4597 p->numa_scan_period = sysctl_numa_balancing_scan_delay;
4598 p->numa_migrate_retry = 0;
4600 p->numa_work.next = &p->numa_work;
4601 p->numa_faults = NULL;
4602 p->numa_pages_migrated = 0;
4603 p->total_numa_faults = 0;
4604 RCU_INIT_POINTER(p->numa_group, NULL);
4605 p->last_task_numa_placement = 0;
4606 p->last_sum_exec_runtime = 0;
4608 init_task_work(&p->numa_work, task_numa_work);
4612 p->numa_preferred_nid = NUMA_NO_NODE;
4624 current->numa_scan_period * mm_users * NSEC_PER_MSEC);
4626 p->node_stamp = delay;
4635 struct callback_head *work = &curr->numa_work;
4641 if (!curr->mm || (curr->flags & (PF_EXITING | PF_KTHREAD)) || work->next != work)
4650 now = curr->se.sum_exec_runtime;
4651 period = (u64)curr->numa_scan_period * NSEC_PER_MSEC;
4653 if (now > curr->node_stamp + period) {
4654 if (!curr->node_stamp)
4655 curr->numa_scan_period = task_scan_start(curr);
4656 curr->node_stamp += period;
4658 if (!time_before(jiffies, curr->mm->numa_next_scan))
4671 if (!p->mm || !p->numa_faults || (p->flags & PF_EXITING))
4680 * is pulled cross-node due to wakeups or load balancing.
4682 if (p->numa_scan_seq) {
4688 if (dst_nid == p->numa_preferred_nid ||
4689 (p->numa_preferred_nid != NUMA_NO_NODE &&
4690 src_nid != p->numa_preferred_nid))
4694 p->numa_scan_period = task_scan_start(p);
4721 update_load_add(&cfs_rq->load, se->load.weight);
4728 list_add(&se->group_node, &rq->cfs_tasks);
4730 cfs_rq->nr_queued++;
4737 update_load_sub(&cfs_rq->load, se->load.weight);
4744 list_del_init(&se->group_node);
4746 cfs_rq->nr_queued--;
4752 * Explicitly do a load-store to ensure the intermediate value never hits
4772 * A variant of sub_positive(), which does not use explicit load-store
4777 *ptr -= min_t(typeof(*ptr), *ptr, _val); \
4782 * Because of rounding, se->util_sum might ends up being +1 more than
4783 * cfs->util_sum. Although this is not a problem by itself, detaching
4785 * util_avg (~1ms) can make cfs->util_sum becoming null whereas
4794 add_positive(&(sa)->name##_avg, delta_avg); \
4795 add_positive(&(sa)->name##_sum, delta_sum); \
4796 (sa)->name##_sum = max_t(typeof((sa)->name##_sum), \
4797 (sa)->name##_sum, \
4798 (sa)->name##_avg * PELT_MIN_DIVIDER); \
4804 __update_sa(&cfs_rq->avg, load, se->avg.load_avg,
4805 se_weight(se) * se->avg.load_sum);
4811 __update_sa(&cfs_rq->avg, load, -se->avg.load_avg,
4812 se_weight(se) * -se->avg.load_sum);
4818 long old_weight = se->h_load.weight;
4822 * --------
4825 * adjusted if re-weight at !0-lag point.
4828 * re-weight without changing vruntime at !0-lag point.
4830 * Weight VRuntime Avg-VRuntime
4834 * Since lag needs to be preserved through re-weight:
4836 * lag = (V - v)*w = (V'- v')*w', where v = v'
4837 * ==> V' = (V - v)*w/w' + v (1)
4842 * V' = (WV + w'v - wv) / (W + w' - w) (2)
4846 * (WV + w'v - wv) / (W + w' - w) = (V - v)*w/w' + v
4847 * ==> (WV-Wv+Wv+w'v-wv)/(W+w'-w) = (V - v)*w/w' + v
4848 * ==> (WV - Wv)/(W + w' - w) + v = (V - v)*w/w' + v
4849 * ==> (V - v)*W/(W + w' - w) = (V - v)*w/w' (3)
4851 * Since we are doing at !0-lag point which means V != v, we
4854 * ==> W / (W + w' - w) = w / w'
4855 * ==> Ww' = Ww + ww' - ww
4856 * ==> W * (w' - w) = w * (w' - w)
4857 * ==> W = w (re-weight indicates w' != w)
4861 * average vruntime @V, which means we will always re-weight
4862 * at 0-lag point, thus breach assumption. Proof completed.
4865 * COROLLARY #2: Re-weight does NOT affect weighted average
4870 * (V - v)*w = (V' - v')*w'
4871 * ==> v' = V' - (V - v)*w/w' (4)
4875 * V' = (WV - wv + w'v') / (W - w + w')
4876 * = (WV - wv + w'(V' - (V - v)w/w')) / (W - w + w')
4877 * = (WV - wv + w'V' - Vw + wv) / (W - w + w')
4878 * = (WV + w'V' - Vw) / (W - w + w')
4880 * ==> V'*(W - w + w') = WV + w'V' - Vw
4881 * ==> V' * (W - w) = (W - w) * V (5)
4884 * always occurs at 0-lag point, so V won't change. Or else
4889 * So according to corollary #1 & #2, the effect of re-weight
4892 * v' = V' - (V - v) * w / w' (4)
4893 * = V - (V - v) * w / w'
4894 * = V - vl * w / w'
4895 * = V - vl'
4897 se->vlag = div64_long(se->vlag * old_weight, weight);
4901 * --------
4906 * d' = v' + (d - v)*w/w'
4907 * = V' - (V - v)*w/w' + (d - v)*w/w'
4908 * = V - (V - v)*w/w' + (d - v)*w/w'
4909 * = V + (d - V)*w/w'
4911 if (se->rel_deadline)
4912 se->deadline = div64_long(se->deadline * old_weight, weight);
4915 se->vprot = div64_long(se->vprot * old_weight, weight);
4921 bool curr = cfs_rq->curr == se;
4925 if (se->h_load.weight == weight)
4930 se->vlag = entity_lag(cfs_rq, se, avruntime);
4931 se->deadline -= avruntime;
4932 se->rel_deadline = 1;
4934 se->vprot -= avruntime;
4938 cfs_rq->h_nr_queued--;
4945 update_load_set(&se->h_load, weight);
4949 se->vprot += avruntime;
4950 se->deadline += avruntime;
4951 se->rel_deadline = 0;
4952 se->vruntime = avruntime - se->vlag;
4956 cfs_rq->h_nr_queued++;
4963 if (se->load.weight == weight)
4966 if (se->on_rq) {
4968 update_load_sub(&cfs_rq->load, se->load.weight);
4972 update_load_set(&se->load, weight);
4975 u32 divider = get_pelt_divider(&se->avg);
4976 se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
4981 if (se->on_rq)
4982 update_load_add(&cfs_rq->load, se->load.weight);
4994 weight *= se->load.weight;
4996 weight /= cfs_rq->load.weight;
5006 struct sched_entity *se = &p->se;
5009 if (se->on_rq)
5012 reweight_entity(cfs_rq_of(se), se, lw->weight);
5013 se->load.inv_weight = lw->inv_weight;
5015 if (!se->on_rq)
5021 reweight_eevdf(&rq->cfs, &p->se, weight, p->se.on_rq);
5034 * tg->weight * grq->load.weight
5035 * ge->load.weight = ----------------------------- (1)
5036 * \Sum grq->load.weight
5044 * grq->load.weight -> grq->avg.load_avg (2)
5048 * tg->weight * grq->avg.load_avg
5049 * ge->load.weight = ------------------------------ (3)
5050 * tg->load_avg
5052 * Where: tg->load_avg ~= \Sum grq->avg.load_avg
5056 * The problem with it is that because the average is slow -- it was designed
5057 * to be exactly that of course -- this leads to transients in boundary
5059 * one task. It takes time for our CPU's grq->avg.load_avg to build up,
5064 * tg->weight * grq->load.weight
5065 * ge->load.weight = ----------------------------- = tg->weight (4)
5066 * grp->load.weight
5073 * ge->load.weight =
5075 * tg->weight * grq->load.weight
5076 * --------------------------------------------------- (5)
5077 * tg->load_avg - grq->avg.load_avg + grq->load.weight
5079 * But because grq->load.weight can drop to 0, resulting in a divide by zero,
5080 * we need to use grq->avg.load_avg as its lower bound, which then gives:
5083 * tg->weight * grq->load.weight
5084 * ge->load.weight = ----------------------------- (6)
5089 * tg_load_avg' = tg->load_avg - grq->avg.load_avg +
5090 * max(grq->load.weight, grq->avg.load_avg)
5094 * overestimates the ge->load.weight and therefore:
5096 * \Sum ge->load.weight >= tg->weight
5102 struct task_group *tg = cfs_rq->tg;
5105 load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);
5107 tg_weight = atomic_long_read(&tg->load_avg);
5110 tg_weight -= cfs_rq->tg_load_avg_contrib;
5118 * MIN_SHARES has to be unscaled here to support per-CPU partitioning
5119 * of a group with small tg->shares value. It is a floor value which is
5123 * E.g. on 64-bit for a group with tg->shares of scale_load(15)=15*1024
5124 * on an 8-core system with 8 tasks each runnable on one CPU shares has
5137 struct cgroup *cgrp = tg->css.cgroup;
5152 return max(1, atomic_long_read(&tg->runnable_avg) >> SCHED_CAPACITY_SHIFT);
5156 * Func: fraction(nr_tasks * tg->shares)
5158 * Scale tg->shares by the number of tasks.
5162 struct task_group *tg = cfs_rq->tg;
5164 long tg_shares = READ_ONCE(tg->shares);
5169 * Func: min(fraction(nr_cpus * tg->shares), nice -20)
5171 * Scale tg->shares by the maximal number of CPUs; but clip the max shares at
5172 * nice -20, otherwise a single spinner on a 512 CPU machine would result in
5177 struct task_group *tg = cfs_rq->tg;
5179 long tg_shares = READ_ONCE(tg->shares);
5185 * Func: fraction(nr * tg->shares); nr = min(nr_tasks, nr_cpus)
5192 struct task_group *tg = cfs_rq->tg;
5194 long tg_shares = READ_ONCE(tg->shares);
5199 * Func: fraction(tg->shares)
5205 struct task_group *tg = cfs_rq->tg;
5206 long tg_shares = READ_ONCE(tg->shares);
5215 struct task_group *tg = cfs_rq->tg;
5216 return READ_ONCE(tg->shares);
5258 if (!gcfs_rq || !gcfs_rq->load.weight)
5275 if (&rq->cfs == cfs_rq) {
5285 * As is, the util number is not freq-invariant (we'd have to
5296 if (sa->load_sum)
5299 if (sa->util_sum)
5302 if (sa->runnable_sum)
5310 WARN_ON_ONCE(sa->load_avg ||
5311 sa->util_avg ||
5312 sa->runnable_avg);
5319 return u64_u32_load_copy(cfs_rq->avg.last_update_time,
5320 cfs_rq->last_update_time_copy);
5326 * bottom-up, we only have to test whether the cfs_rq before us on the list
5337 if (cfs_rq->on_list) {
5338 prev = cfs_rq->leaf_cfs_rq_list.prev;
5340 prev = rq->tmp_alone_branch;
5343 if (prev == &rq->leaf_cfs_rq_list)
5348 return (prev_cfs_rq->tg->parent == cfs_rq->tg);
5353 if (cfs_rq->load.weight)
5356 if (!load_avg_is_decayed(&cfs_rq->avg))
5362 if (cfs_rq->tg_load_avg_contrib)
5369 * update_tg_load_avg - update the tg's load avg
5372 * This function 'ensures': tg->load_avg := \Sum tg->cfs_rq[]->avg.load.
5373 * However, because tg->load_avg is a global value there are performance
5390 if (cfs_rq->tg == &root_task_group)
5398 * For migration heavy workloads, access to tg->load_avg can be
5402 if (now - cfs_rq->last_update_tg_load_avg < NSEC_PER_MSEC)
5405 dl = cfs_rq->avg.load_avg - cfs_rq->tg_load_avg_contrib;
5406 dr = cfs_rq->avg.runnable_avg - cfs_rq->tg_runnable_avg_contrib;
5407 if (abs(dl) > cfs_rq->tg_load_avg_contrib / 64 ||
5408 abs(dr) > cfs_rq->tg_runnable_avg_contrib / 64) {
5409 atomic_long_add(dl, &cfs_rq->tg->load_avg);
5410 atomic_long_add(dr, &cfs_rq->tg->runnable_avg);
5411 cfs_rq->tg_load_avg_contrib = cfs_rq->avg.load_avg;
5412 cfs_rq->tg_runnable_avg_contrib = cfs_rq->avg.runnable_avg;
5413 cfs_rq->last_update_tg_load_avg = now;
5425 if (cfs_rq->tg == &root_task_group)
5429 dl = 0 - cfs_rq->tg_load_avg_contrib;
5430 dr = 0 - cfs_rq->tg_runnable_avg_contrib;
5431 atomic_long_add(dl, &cfs_rq->tg->load_avg);
5432 atomic_long_add(dr, &cfs_rq->tg->runnable_avg);
5433 cfs_rq->tg_load_avg_contrib = 0;
5434 cfs_rq->tg_runnable_avg_contrib = 0;
5435 cfs_rq->last_update_tg_load_avg = now;
5465 * caller only guarantees p->pi_lock is held; no other assumptions,
5466 * including the state of rq->lock, should be made.
5480 * getting what current time is, so simply throw away the out-of-date
5484 if (!(se->avg.last_update_time && prev))
5491 se->avg.last_update_time = n_last_update_time;
5499 * ge->avg == grq->avg (1)
5510 * ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg (2)
5515 * grq->avg.load_avg = grq->load.weight * grq->avg.runnable_avg (3)
5519 * ge->avg.runnable_avg == grq->avg.runnable_avg
5523 * ge->load.weight * grq->avg.load_avg
5524 * ge->avg.load_avg = ----------------------------------- (4)
5525 * grq->load.weight
5538 * Another reason this doesn't work is that runnable isn't a 0-sum entity.
5549 * ge->avg.running_sum <= ge->avg.runnable_sum <= LOAD_AVG_MAX
5556 * grq->avg.runnable_sum = grq->avg.load_sum / grq->load.weight
5564 long delta_sum, delta_avg = gcfs_rq->avg.util_avg - se->avg.util_avg;
5572 * cfs_rq->avg.period_contrib can be used for both cfs_rq and se.
5575 divider = get_pelt_divider(&cfs_rq->avg);
5578 se->avg.util_avg = gcfs_rq->avg.util_avg;
5579 new_sum = se->avg.util_avg * divider;
5580 delta_sum = (long)new_sum - (long)se->avg.util_sum;
5581 se->avg.util_sum = new_sum;
5584 __update_sa(&cfs_rq->avg, util, delta_avg, delta_sum);
5590 long delta_sum, delta_avg = gcfs_rq->avg.runnable_avg - se->avg.runnable_avg;
5599 * cfs_rq->avg.period_contrib can be used for both cfs_rq and se.
5602 divider = get_pelt_divider(&cfs_rq->avg);
5605 se->avg.runnable_avg = gcfs_rq->avg.runnable_avg;
5606 new_sum = (u64)se->avg.runnable_avg * divider;
5607 delta_sum = (long)new_sum - (long)se->avg.runnable_sum;
5608 se->avg.runnable_sum = new_sum;
5611 __update_sa(&cfs_rq->avg, runnable, delta_avg, delta_sum);
5617 long delta_avg, running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
5626 gcfs_rq->prop_runnable_sum = 0;
5629 * cfs_rq->avg.period_contrib can be used for both cfs_rq and se.
5632 divider = get_pelt_divider(&cfs_rq->avg);
5639 runnable_sum += se->avg.load_sum;
5646 if (scale_load_down(gcfs_rq->load.weight)) {
5647 load_sum = div_u64(gcfs_rq->avg.load_sum,
5648 scale_load_down(gcfs_rq->load.weight));
5652 runnable_sum = min(se->avg.load_sum, load_sum);
5661 running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT;
5667 delta_avg = load_avg - se->avg.load_avg;
5671 delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
5673 se->avg.load_sum = runnable_sum;
5674 se->avg.load_avg = load_avg;
5675 __update_sa(&cfs_rq->avg, load, delta_avg, delta_sum);
5680 cfs_rq->propagate = 1;
5681 cfs_rq->prop_runnable_sum += runnable_sum;
5693 if (!gcfs_rq->propagate)
5696 gcfs_rq->propagate = 0;
5700 add_tg_cfs_propagate(cfs_rq, gcfs_rq->prop_runnable_sum);
5724 if (se->avg.load_avg || se->avg.util_avg)
5731 if (gcfs_rq->propagate)
5765 if (load_avg_is_decayed(&se->avg))
5772 is_idle = is_idle_task(rcu_dereference_all(rq->curr));
5789 * - cfs->throttled_clock_pelt_time@cfs_rq_idle
5792 * = rq_clock_pelt()@rq_idle - rq_clock_pelt()@cfs_rq_idle
5795 * = sched_clock_cpu() - rq_clock()@rq_idle
5799 * now = rq_clock_pelt()@rq_idle - cfs->throttled_clock_pelt_time +
5800 * sched_clock_cpu() - rq_clock()@rq_idle
5802 * rq_clock_pelt()@rq_idle is rq->clock_pelt_idle
5803 * rq_clock()@rq_idle is rq->clock_idle
5804 * cfs->throttled_clock_pelt_time@cfs_rq_idle
5805 * is cfs_rq->throttled_pelt_idle
5809 throttled = u64_u32_load(cfs_rq->throttled_pelt_idle);
5814 now = u64_u32_load(rq->clock_pelt_idle);
5824 now -= throttled;
5827 * cfs_rq->avg.last_update_time is more recent than our
5832 now += sched_clock_cpu(cpu_of(rq)) - u64_u32_load(rq->clock_idle);
5841 * update_cfs_rq_load_avg - update the cfs_rq's load/util averages
5848 * cfs_rq->avg is used for task_h_load() and update_cfs_group() for example.
5852 * Since both these conditions indicate a changed cfs_rq->avg.load we should
5859 struct sched_avg *sa = &cfs_rq->avg;
5862 if (cfs_rq->removed.nr) {
5864 u32 divider = get_pelt_divider(&cfs_rq->avg);
5866 raw_spin_lock(&cfs_rq->removed.lock);
5867 swap(cfs_rq->removed.util_avg, removed_util);
5868 swap(cfs_rq->removed.load_avg, removed_load);
5869 swap(cfs_rq->removed.runnable_avg, removed_runnable);
5870 cfs_rq->removed.nr = 0;
5871 raw_spin_unlock(&cfs_rq->removed.lock);
5874 __update_sa(sa, load, -r, -r*divider);
5877 __update_sa(sa, util, -r, -r*divider);
5880 __update_sa(sa, runnable, -r, -r*divider);
5887 -(long)(removed_runnable * divider) >> SCHED_CAPACITY_SHIFT);
5893 u64_u32_store_copy(sa->last_update_time,
5894 cfs_rq->last_update_time_copy,
5895 sa->last_update_time);
5900 * attach_entity_load_avg - attach this entity to its cfs_rq load avg
5905 * cfs_rq->avg.last_update_time being current.
5910 * cfs_rq->avg.period_contrib can be used for both cfs_rq and se.
5913 u32 divider = get_pelt_divider(&cfs_rq->avg);
5922 se->avg.last_update_time = cfs_rq->avg.last_update_time;
5923 se->avg.period_contrib = cfs_rq->avg.period_contrib;
5931 se->avg.util_sum = se->avg.util_avg * divider;
5933 se->avg.runnable_sum = se->avg.runnable_avg * divider;
5935 se->avg.load_sum = se->avg.load_avg * divider;
5936 if (se_weight(se) < se->avg.load_sum)
5937 se->avg.load_sum = div_u64(se->avg.load_sum, se_weight(se));
5939 se->avg.load_sum = 1;
5942 cfs_rq->avg.util_avg += se->avg.util_avg;
5943 cfs_rq->avg.util_sum += se->avg.util_sum;
5944 cfs_rq->avg.runnable_avg += se->avg.runnable_avg;
5945 cfs_rq->avg.runnable_sum += se->avg.runnable_sum;
5947 add_tg_cfs_propagate(cfs_rq, se->avg.load_sum);
5955 * detach_entity_load_avg - detach this entity from its cfs_rq load avg
5960 * cfs_rq->avg.last_update_time being current.
5965 __update_sa(&cfs_rq->avg, util, -se->avg.util_avg, -se->avg.util_sum);
5966 __update_sa(&cfs_rq->avg, runnable, -se->avg.runnable_avg, -se->avg.runnable_sum);
5968 add_tg_cfs_propagate(cfs_rq, -se->avg.load_sum);
5985 ewma = READ_ONCE(se->avg.util_est);
5995 dequeued = READ_ONCE(se->avg.util_avg);
6010 last_ewma_diff = ewma - dequeued;
6018 if ((dequeued + UTIL_EST_MARGIN) < READ_ONCE(se->avg.runnable_avg))
6028 * ewma(t) = w * task_util(p) + (1-w) * ewma(t-1)
6029 * = w * task_util(p) + ewma(t-1) - w * ewma(t-1)
6030 * = w * (task_util(p) - ewma(t-1)) + ewma(t-1)
6031 * = w * ( -last_ewma_diff ) + ewma(t-1)
6032 * = w * (-last_ewma_diff + ewma(t-1) / w)
6038 ewma -= last_ewma_diff;
6042 WRITE_ONCE(se->avg.util_est, ewma);
6066 if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD))
6072 if (!se->avg.last_update_time && (flags & DO_ATTACH)) {
6125 * tasks cannot exit without having gone through wake_up_new_task() ->
6132 raw_spin_lock_irqsave(&cfs_rq->removed.lock, flags);
6133 ++cfs_rq->removed.nr;
6134 cfs_rq->removed.util_avg += se->avg.util_avg;
6135 cfs_rq->removed.load_avg += se->avg.load_avg;
6136 cfs_rq->removed.runnable_avg += se->avg.runnable_avg;
6137 raw_spin_unlock_irqrestore(&cfs_rq->removed.lock, flags);
6142 return cfs_rq->avg.runnable_avg;
6147 return cfs_rq->avg.load_avg;
6155 return READ_ONCE(p->se.avg.util_avg);
6160 return READ_ONCE(p->se.avg.util_est) & ~UTIL_AVG_UNCHANGED;
6177 enqueued = cfs_rq->avg.util_est;
6179 WRITE_ONCE(cfs_rq->avg.util_est, enqueued);
6193 enqueued = cfs_rq->avg.util_est;
6194 enqueued -= min_t(unsigned int, enqueued, _task_util_est(p));
6195 WRITE_ONCE(cfs_rq->avg.util_est, enqueued);
6204 capacity -= max(hw_load_avg(cpu_rq(cpu)), cpufreq_get_pressure(cpu));
6262 * +----------------------------------------
6300 * +----------------------------------------
6323 return -1;
6351 if (!p || (p->nr_cpus_allowed == 1) ||
6352 (arch_scale_cpu_capacity(cpu) == p->max_allowed_capacity) ||
6355 rq->misfit_task_load = 0;
6363 rq->misfit_task_load = max_t(unsigned long, task_h_load(p), 1);
6368 struct sched_entity *se = &p->se;
6370 p->static_prio = NICE_TO_PRIO(attr->sched_nice);
6371 if (attr->sched_runtime) {
6372 se->custom_slice = 1;
6373 se->slice = clamp_t(u64, attr->sched_runtime,
6377 se->custom_slice = 0;
6378 se->slice = sysctl_sched_base_slice;
6386 unsigned int nr_queued = cfs_rq->h_nr_queued;
6390 if (!se->custom_slice)
6391 se->slice = sysctl_sched_base_slice;
6392 vslice = calc_delta_fair(se->slice, se);
6395 nr_queued -= 1;
6405 if (sched_feat(PLACE_LAG) && nr_queued && se->vlag) {
6406 struct sched_entity *curr = cfs_rq->curr;
6409 lag = se->vlag;
6419 * lag_i = S - s_i = w_i * (V - v_i)
6424 * vl_i = V - v_i <=> v_i = V - vl_i
6436 * = (W*V + w_i*(V - vl_i)) / (W + w_i)
6437 * = (W*V + w_i*V - w_i*vl_i) / (W + w_i)
6438 * = (V*(W + w_i) - w_i*vl_i) / (W + w_i)
6439 * = V - w_i*vl_i / (W + w_i)
6443 * vl'_i = V' - v_i
6444 * = V - w_i*vl_i / (W + w_i) - (V - vl_i)
6445 * = vl_i - w_i*vl_i / (W + w_i)
6455 * vl'_i = vl_i - w_i*vl_i / (W + w_i)
6456 * = ((W + w_i)*vl_i - w_i*vl_i) / (W + w_i)
6458 * (W + w_i)*vl'_i = (W + w_i)*vl_i - w_i*vl_i
6463 load = cfs_rq->sum_weight;
6464 if (curr && curr->on_rq)
6465 load += avg_vruntime_weight(cfs_rq, curr->h_load.weight);
6469 weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
6489 * sum_w_vruntime = \Sum (v_i - v0) * w_i
6505 se->vruntime = vruntime - lag;
6508 update_zero_vruntime(cfs_rq, -lag);
6510 if (sched_feat(PLACE_REL_DEADLINE) && se->rel_deadline) {
6511 se->deadline += se->vruntime;
6512 se->rel_deadline = 0;
6527 se->deadline = se->vruntime + vslice;
6538 * - Update loads to have both entity and cfs_rq synced with now.
6539 * - For group_entity, update its runnable_weight to reflect the new
6541 * - For group_entity, update its weight to reflect the new share of
6543 * - Add its new weight to cfs_rq->load.weight
6549 * but update_cfs_group() here will re-adjust the weight and have to
6558 se->exec_start = 0;
6562 se->on_rq = 1;
6564 if (cfs_rq->nr_queued == 1) {
6568 if (cfs_rq->pelt_clock_throttled) {
6571 cfs_rq->throttled_clock_pelt_time += rq_clock_pelt(rq) -
6572 cfs_rq->throttled_clock_pelt;
6573 cfs_rq->pelt_clock_throttled = 0;
6581 if (WARN_ON_ONCE(!se->on_rq || se->sched_delayed))
6585 cfs_rq->next = se;
6590 if (cfs_rq->next == se)
6591 cfs_rq->next = NULL;
6608 se->sched_delayed = 1;
6618 se->sched_delayed = 1;
6623 cfs_rq->h_nr_runnable--;
6629 se->sched_delayed = 0;
6641 * Re-add on wake, after sched_delayed is cleared. On a final delayed
6650 cfs_rq->h_nr_runnable++;
6669 * - Update loads to have both entity and cfs_rq synced with now.
6670 * - For group_entity, update its runnable_weight to reflect the new
6672 * - Subtract its previous weight from cfs_rq->load.weight.
6673 * - For group entity, update its weight to reflect the new share
6681 se->on_rq = 0;
6689 if (cfs_rq->nr_queued == 0) {
6696 cfs_rq->throttled_clock_pelt = rq_clock_pelt(rq);
6697 cfs_rq->pelt_clock_throttled = 1;
6707 if (se->on_rq) {
6718 WARN_ON_ONCE(cfs_rq->h_curr);
6719 cfs_rq->h_curr = se;
6724 * when there are only lesser-weight tasks around):
6727 rq_of(cfs_rq)->cfs.load.weight >= 2*se->load.weight) {
6731 __schedstat_set(stats->slice_max,
6732 max((u64)stats->slice_max,
6733 se->sum_exec_runtime - se->prev_sum_exec_runtime));
6736 se->prev_sum_exec_runtime = se->sum_exec_runtime;
6744 struct cfs_rq *cfs_rq = &rq->cfs;
6748 if (se->sched_delayed) {
6764 if (prev->on_rq)
6767 if (prev->on_rq) {
6772 WARN_ON_ONCE(cfs_rq->h_curr != prev);
6773 cfs_rq->h_curr = NULL;
6780 * Update run-time statistics of the 'current'.
6843 * directly instead of rq->clock to avoid adding additional synchronization
6844 * around rq->lock.
6846 * requires cfs_b->lock
6852 if (unlikely(cfs_b->quota == RUNTIME_INF))
6855 cfs_b->runtime += cfs_b->quota;
6856 runtime = cfs_b->runtime_snap - cfs_b->runtime;
6858 cfs_b->burst_time += runtime;
6859 cfs_b->nr_burst++;
6862 cfs_b->runtime = min(cfs_b->runtime, cfs_b->quota + cfs_b->burst);
6863 cfs_b->runtime_snap = cfs_b->runtime;
6868 return &tg->cfs_bandwidth;
6877 lockdep_assert_held(&cfs_b->lock);
6880 min_amount = target_runtime - cfs_rq->runtime_remaining;
6882 if (cfs_b->quota == RUNTIME_INF)
6887 if (cfs_b->runtime > 0) {
6888 amount = min(cfs_b->runtime, min_amount);
6889 cfs_b->runtime -= amount;
6890 cfs_b->idle = 0;
6894 cfs_rq->runtime_remaining += amount;
6896 return cfs_rq->runtime_remaining > 0;
6904 cfs_rq->runtime_remaining -= delta_exec;
6906 if (likely(cfs_rq->runtime_remaining > 0))
6909 if (cfs_rq->throttled)
6921 if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
6929 return cfs_bandwidth_used() && cfs_rq->throttled;
6934 return cfs_bandwidth_used() && cfs_rq->pelt_clock_throttled;
6940 return cfs_bandwidth_used() && cfs_rq->throttle_count;
6950 return cfs_bandwidth_used() && p->throttled;
6962 p->sched_throttle_work.next = &p->sched_throttle_work;
6968 if ((p->flags & PF_EXITING))
6972 se = &p->se;
6976 if (p->sched_class != &fair_sched_class)
6983 if (!cfs_rq->throttle_count)
6987 WARN_ON_ONCE(p->throttled || !list_empty(&p->throttle_node));
6989 list_add(&p->throttle_node, &cfs_rq->throttled_limbo_list);
6994 p->throttled = true;
7001 init_task_work(&p->sched_throttle_work, throttle_cfs_rq_work);
7003 p->sched_throttle_work.next = &p->sched_throttle_work;
7004 INIT_LIST_HEAD(&p->throttle_node);
7018 WARN_ON_ONCE(p->se.on_rq);
7019 list_del_init(&p->throttle_node);
7023 p->throttled = false;
7037 struct cfs_rq *cfs_rq = cfs_rq_of(&p->se);
7040 WARN_ON_ONCE(!list_empty(&p->throttle_node));
7048 * cause @p's group_node to be incorectly re-insterted in its rq's
7063 * enqueue_task(p) -> p's new cfs_rq
7068 * list_move(&se->group_node, &rq->cfs_tasks); // bug
7078 list_add(&p->throttle_node, &cfs_rq->throttled_limbo_list);
7083 p->throttled = false;
7096 * If cfs_rq->curr is set, the cfs_rq might not have caught up
7104 if (--cfs_rq->throttle_count)
7107 if (cfs_rq->pelt_clock_throttled) {
7108 cfs_rq->throttled_clock_pelt_time += rq_clock_pelt(rq) -
7109 cfs_rq->throttled_clock_pelt;
7110 cfs_rq->pelt_clock_throttled = 0;
7113 if (cfs_rq->throttled_clock_self) {
7114 u64 delta = rq_clock(rq) - cfs_rq->throttled_clock_self;
7116 cfs_rq->throttled_clock_self = 0;
7121 cfs_rq->throttled_clock_self_time += delta;
7127 * see the "throttled_limbo_list" being non-empty in
7130 list_splice_init(&cfs_rq->throttled_limbo_list, &throttled_tasks);
7132 /* Re-enqueue the tasks that have been throttled at this level. */
7139 if (cfs_rq->throttle_count)
7142 list_del_init(&p->throttle_node);
7143 p->throttled = false;
7147 list_splice(&throttled_tasks, &cfs_rq->throttled_limbo_list);
7158 return p->sched_throttle_work.next != &p->sched_throttle_work;
7170 if ((p->flags & (PF_EXITING | PF_KTHREAD)))
7173 task_work_add(p, &p->sched_throttle_work, TWA_RESUME);
7180 if (cfs_rq_throttled(cfs_rq) && !cfs_rq->throttled_clock)
7181 cfs_rq->throttled_clock = rq_clock(rq);
7183 if (!cfs_rq->throttled_clock_self)
7184 cfs_rq->throttled_clock_self = rq_clock(rq);
7192 if (cfs_rq->throttle_count++)
7199 if (!cfs_rq->nr_queued) {
7201 cfs_rq->throttled_clock_pelt = rq_clock_pelt(rq);
7202 cfs_rq->pelt_clock_throttled = 1;
7205 WARN_ON_ONCE(cfs_rq->throttled_clock_self);
7206 WARN_ON_ONCE(!list_empty(&cfs_rq->throttled_limbo_list));
7212 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
7213 struct sched_entity *curr = cfs_rq->h_curr;
7216 scoped_guard(raw_spinlock, &cfs_b->lock) {
7220 * If cfs_rq->h_curr is still runnable, we are here from an
7227 if (curr && curr->on_rq)
7247 list_add_tail_rcu(&cfs_rq->throttled_list,
7248 &cfs_b->throttled_cfs_rq);
7253 walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq);
7257 * throttled-list. rq->lock protects completion.
7259 cfs_rq->throttled = 1;
7260 WARN_ON_ONCE(cfs_rq->throttled_clock);
7264 * current donor. In case of proxy-execution, the execution
7269 if (curr && curr->on_rq)
7270 task_throttle_setup_work(rq->donor);
7278 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
7294 if (cfs_rq->runtime_enabled && cfs_rq->runtime_remaining <= 0)
7297 cfs_rq->throttled = 0;
7299 scoped_guard(raw_spinlock, &cfs_b->lock) {
7300 list_del_rcu(&cfs_rq->throttled_list);
7302 if (!cfs_rq->throttled_clock)
7305 cfs_b->throttled_time += rq_clock(rq) - cfs_rq->throttled_clock;
7306 cfs_rq->throttled_clock = 0;
7310 walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq);
7312 if (!cfs_rq->load.weight) {
7313 if (!cfs_rq->on_list)
7328 if (rq->curr == rq->idle && rq->cfs.h_nr_queued)
7356 list_for_each_entry_safe(cursor, tmp, &rq->cfsb_csd_list,
7358 list_del_init(&cursor->throttled_csd_list);
7379 if (WARN_ON_ONCE(!list_empty(&cfs_rq->throttled_csd_list)))
7382 first = list_empty(&rq->cfsb_csd_list);
7383 list_add_tail(&cfs_rq->throttled_csd_list, &rq->cfsb_csd_list);
7385 smp_call_function_single_async(cpu_of(rq), &rq->cfsb_csd);
7393 cfs_rq->runtime_remaining <= 0))
7409 list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
7424 if (!list_empty(&cfs_rq->throttled_csd_list))
7427 if (cfs_rq->h_curr) {
7433 WARN_ON_ONCE(cfs_rq->runtime_remaining > 0);
7435 scoped_guard(raw_spinlock, &cfs_b->lock) {
7436 runtime = -cfs_rq->runtime_remaining + 1;
7437 if (runtime > cfs_b->runtime)
7438 runtime = cfs_b->runtime;
7439 cfs_b->runtime -= runtime;
7440 remaining = cfs_b->runtime;
7443 cfs_rq->runtime_remaining += runtime;
7449 if (cfs_rq->runtime_remaining <= 0) {
7466 unthrottle_local = list_empty(&rq->cfsb_csd_list);
7467 list_add_tail(&cfs_rq->throttled_csd_list, &rq->cfsb_csd_list);
7485 * period the timer is deactivated until scheduling resumes; cfs_b->idle is
7489 __must_hold(&cfs_b->lock)
7494 if (cfs_b->quota == RUNTIME_INF)
7497 throttled = !list_empty(&cfs_b->throttled_cfs_rq);
7498 cfs_b->nr_periods += overrun;
7500 /* Refill extra burst quota even if cfs_b->idle */
7507 if (cfs_b->idle && !throttled)
7512 cfs_b->idle = 1;
7517 cfs_b->nr_throttled += overrun;
7520 * This check is repeated as we release cfs_b->lock while we unthrottle.
7522 while (throttled && cfs_b->runtime > 0) {
7523 raw_spin_unlock_irqrestore(&cfs_b->lock, flags);
7524 /* we can't nest cfs_b->lock while distributing bandwidth */
7526 raw_spin_lock_irqsave(&cfs_b->lock, flags);
7535 cfs_b->idle = 0;
7553 * Requires cfs_b->lock for hrtimer_expires_remaining to be safe against the
7559 struct hrtimer *refresh_timer = &cfs_b->period_timer;
7562 /* if the call-back is running a quota refresh is already occurring */
7583 if (cfs_b->slack_started)
7585 cfs_b->slack_started = true;
7587 hrtimer_start(&cfs_b->slack_timer,
7595 struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
7596 s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime;
7601 guard(raw_spinlock)(&cfs_b->lock);
7603 if (cfs_b->quota != RUNTIME_INF) {
7604 cfs_b->runtime += slack_runtime;
7606 /* we are under rq->lock, defer unthrottling using a timer */
7607 if (cfs_b->runtime > sched_cfs_bandwidth_slice() &&
7608 !list_empty(&cfs_b->throttled_cfs_rq))
7613 cfs_rq->runtime_remaining -= slack_runtime;
7621 if (!cfs_rq->runtime_enabled || cfs_rq->nr_queued)
7629 * it's necessary to juggle rq->locks to unthrottle their respective cfs_rqs.
7634 scoped_guard(raw_spinlock_irqsave, &cfs_b->lock) {
7637 cfs_b->slack_started = false;
7642 if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice)
7643 runtime = cfs_b->runtime;
7655 * runtime as update_curr() throttling can not trigger until it's on-rq.
7663 if (!cfs_rq->runtime_enabled || cfs_rq->h_curr)
7681 if (!tg->parent)
7685 pcfs_rq = tg_cfs_rq(tg->parent, cpu);
7687 cfs_rq->throttle_count = pcfs_rq->throttle_count;
7688 cfs_rq->throttled_clock_pelt = rq_clock_pelt(cpu_rq(cpu));
7697 if (cfs_rq->throttle_count)
7698 cfs_rq->pelt_clock_throttled = 1;
7719 CLASS(raw_spinlock_irqsave, cfsb_guard)(&cfs_b->lock);
7722 overrun = hrtimer_forward_now(timer, cfs_b->period);
7729 u64 new, old = ktime_to_ns(cfs_b->period);
7738 cfs_b->period = ns_to_ktime(new);
7739 cfs_b->quota *= 2;
7740 cfs_b->burst *= 2;
7746 div_u64(cfs_b->quota, NSEC_PER_USEC));
7752 div_u64(cfs_b->quota, NSEC_PER_USEC));
7761 cfs_b->period_active = 0;
7770 raw_spin_lock_init(&cfs_b->lock);
7771 cfs_b->runtime = 0;
7772 cfs_b->quota = RUNTIME_INF;
7773 cfs_b->period = us_to_ktime(default_bw_period_us());
7774 cfs_b->burst = 0;
7775 cfs_b->hierarchical_quota = parent ? parent->hierarchical_quota : RUNTIME_INF;
7777 INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq);
7778 hrtimer_setup(&cfs_b->period_timer, sched_cfs_period_timer, CLOCK_MONOTONIC,
7782 hrtimer_set_expires(&cfs_b->period_timer,
7783 get_random_u32_below(cfs_b->period));
7784 hrtimer_setup(&cfs_b->slack_timer, sched_cfs_slack_timer, CLOCK_MONOTONIC,
7786 cfs_b->slack_started = false;
7791 cfs_rq->runtime_enabled = 0;
7792 INIT_LIST_HEAD(&cfs_rq->throttled_list);
7793 INIT_LIST_HEAD(&cfs_rq->throttled_csd_list);
7794 INIT_LIST_HEAD(&cfs_rq->throttled_limbo_list);
7799 lockdep_assert_held(&cfs_b->lock);
7801 if (cfs_b->period_active)
7804 cfs_b->period_active = 1;
7805 hrtimer_forward_now(&cfs_b->period_timer, cfs_b->period);
7806 hrtimer_start_expires(&cfs_b->period_timer, HRTIMER_MODE_ABS_PINNED);
7814 if (!cfs_b->throttled_cfs_rq.next)
7817 hrtimer_cancel(&cfs_b->period_timer);
7818 hrtimer_cancel(&cfs_b->slack_timer);
7833 if (list_empty(&rq->cfsb_csd_list))
7858 struct cfs_bandwidth *cfs_b = &tg->cfs_bandwidth;
7861 scoped_guard(raw_spinlock, &cfs_b->lock)
7862 cfs_rq->runtime_enabled = cfs_b->quota != RUNTIME_INF;
7889 if (!cfs_rq->runtime_enabled)
7896 cfs_rq->runtime_enabled = 0;
7905 cfs_rq->runtime_remaining = 1;
7919 if (cfs_rq->runtime_enabled ||
7920 tg_cfs_bandwidth(cfs_rq->tg)->hierarchical_quota != RUNTIME_INF)
7938 if (rq->nr_running != 1)
8015 struct sched_entity *se = &p->se;
8023 if (rq->cfs.h_nr_queued <= 1)
8029 vdelta = se->deadline - se->vruntime;
8035 delta = (se->h_load.weight * vdelta) / NICE_0_LOAD;
8043 scale /= (1024 - util);
8054 struct task_struct *donor = rq->donor;
8056 if (!hrtick_enabled_fair(rq) || donor->sched_class != &fair_sched_class)
8093 return !sched_energy_enabled() || READ_ONCE(rd->overutilized);
8101 WRITE_ONCE(rd->overutilized, flag);
8112 if (!is_rd_overutilized(rq->rd) && cpu_overutilized(rq->cpu))
8113 set_rd_overutilized(rq->rd, 1);
8119 return unlikely(rq->nr_running == rq->cfs.h_nr_idle &&
8120 rq->nr_running);
8138 * se->sched_delayed should imply: se->on_rq == 1.
8142 WARN_ON_ONCE(!se->sched_delayed);
8143 WARN_ON_ONCE(!se->on_rq);
8146 cfs_rq->h_nr_queued--;
8147 if (se != cfs_rq->curr)
8150 if (se != cfs_rq->curr)
8152 cfs_rq->h_nr_queued++;
8163 struct sched_entity *se = &p->se;
8167 if (task_new && se->sched_delayed)
8175 if (!se->on_rq) {
8183 cfs_rq->h_nr_runnable += h_nr_runnable;
8184 cfs_rq->h_nr_queued++;
8185 cfs_rq->h_nr_idle += h_nr_idle;
8201 if (!cfs_rq->curr)
8204 update_curr(cfs_rq_of(cfs_rq->curr));
8215 int rq_h_nr_queued = rq->cfs.h_nr_queued;
8217 struct sched_entity *se = &p->se;
8218 struct cfs_rq *cfs_rq = &rq->cfs;
8231 if (!p->se.sched_delayed || (flags & ENQUEUE_DELAYED))
8246 if (p->in_iowait)
8252 curr = (cfs_rq->curr == se);
8256 if (se->on_rq && se->sched_delayed)
8267 if (!rq_h_nr_queued && rq->cfs.h_nr_queued)
8268 dl_server_start(&rq->fair_server);
8297 struct sched_entity *se = &p->se;
8305 if (task_sleep || task_delayed || !se->sched_delayed)
8316 if (cfs_rq->load.weight)
8324 cfs_rq->h_nr_runnable -= h_nr_runnable;
8325 cfs_rq->h_nr_queued--;
8326 cfs_rq->h_nr_idle -= h_nr_idle;
8343 * true - dequeued
8344 * false - delayed
8348 struct sched_entity *se = &p->se;
8349 struct cfs_rq *cfs_rq = &rq->cfs;
8360 WARN_ON_ONCE(!se->sched_delayed);
8370 WARN_ON_ONCE(delay && se->sched_delayed);
8383 se->deadline -= se->vruntime;
8384 se->rel_deadline = 1;
8386 if (se != cfs_rq->curr)
8393 rq->next_balance = jiffies;
8399 WARN_ON_ONCE(p->on_rq != 1);
8402 * Fix-up what block_task() skipped.
8424 if (!p->se.sched_delayed)
8425 util_est_dequeue(&rq->cfs, p);
8438 return (rq->cfs.h_nr_queued - rq->cfs.h_nr_runnable);
8460 return cfs_rq_load_avg(&rq->cfs);
8464 * cpu_load_without - compute CPU load without any contributions from *p
8482 if (cpu_of(rq) != task_cpu(p) || !READ_ONCE(p->se.avg.last_update_time))
8485 cfs_rq = &rq->cfs;
8486 load = READ_ONCE(cfs_rq->avg.load_avg);
8496 return cfs_rq_runnable_avg(&rq->cfs);
8505 if (cpu_of(rq) != task_cpu(p) || !READ_ONCE(p->se.avg.last_update_time))
8508 cfs_rq = &rq->cfs;
8509 runnable = READ_ONCE(cfs_rq->avg.runnable_avg);
8512 lsub_positive(&runnable, p->se.avg.runnable_avg);
8519 return cpu_rq(cpu)->cpu_capacity;
8528 if (time_after(jiffies, current->wakee_flip_decay_ts + HZ)) {
8529 current->wakee_flips >>= 1;
8530 current->wakee_flip_decay_ts = jiffies;
8533 if (current->last_wakee != p) {
8534 current->last_wakee = p;
8535 current->wakee_flips++;
8540 * Detect M:N waker/wakee relationships via a switching-frequency heuristic.
8550 * non-monogamous, with partner count exceeding socket size.
8558 unsigned int master = current->wakee_flips;
8559 unsigned int slave = p->wakee_flips;
8574 * wake_affine_idle() - only considers 'now', it check if the waking CPU is
8575 * cache-affine and is (or will be) idle.
8577 * wake_affine_weight() - considers the weight to reflect the average
8602 if ((rq->nr_running - cfs_h_nr_delayed(rq)) == 1)
8627 this_eff_load -= current_load;
8638 prev_eff_load -= task_load;
8640 prev_eff_load *= 100 + (sd->imbalance_pct - 100) / 2;
8666 schedstat_inc(p->stats.nr_wakeups_affine_attempts);
8670 schedstat_inc(sd->ttwu_move_affine);
8671 schedstat_inc(p->stats.nr_wakeups_affine);
8679 * sched_balance_find_dst_group_cpu - find the idlest CPU among the CPUs in the group.
8688 int shallowest_idle_cpu = -1;
8692 if (group->group_weight == 1)
8696 for_each_cpu_and(i, sched_group_span(group), p->cpus_ptr) {
8707 if (idle && idle->exit_latency < min_exit_latency) {
8713 min_exit_latency = idle->exit_latency;
8714 latest_idle_timestamp = rq->idle_stamp;
8716 } else if ((!idle || idle->exit_latency == min_exit_latency) &&
8717 rq->idle_stamp > latest_idle_timestamp) {
8723 latest_idle_timestamp = rq->idle_stamp;
8726 } else if (shallowest_idle_cpu == -1) {
8735 return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu;
8743 if (!cpumask_intersects(sched_domain_span(sd), p->cpus_ptr))
8751 sync_entity_load_avg(&p->se);
8758 if (!(sd->flags & sd_flag)) {
8759 sd = sd->child;
8765 sd = sd->child;
8772 sd = sd->child;
8778 weight = sd->span_weight;
8781 if (weight <= tmp->span_weight)
8783 if (tmp->flags & sd_flag)
8796 return -1;
8808 WRITE_ONCE(sds->has_idle_cores, val);
8817 return READ_ONCE(sds->has_idle_cores);
8824 * information in sd_balance_shared->has_idle_cores.
8854 * sd_balance_shared->has_idle_cores and enabled through update_idle_core()
8865 if (*idle_cpu == -1) {
8875 if (*idle_cpu == -1 && cpumask_test_cpu(cpu, cpus))
8883 return -1;
8893 for_each_cpu_and(cpu, cpu_smt_mask(target), p->cpus_ptr) {
8906 return -1;
8911 * comparing the average scan cost (tracked in sd->avg_scan_cost) against the
8912 * average idle time for this rq (as found in rq->avg_idle).
8917 int i, cpu, idle_cpu = -1, nr = INT_MAX;
8919 if (sched_feat(SIS_UTIL) && sd->shared) {
8921 * Increment because !--nr is the condition to stop scan.
8924 * caller, it is safe to directly dereference "sd->shared".
8929 nr = READ_ONCE(sd->shared->nr_idle_scan) + 1;
8932 return -1;
8935 if (!cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr))
8936 return -1;
8939 struct sched_group *sg = sd->groups;
8941 if (sg->flags & SD_CLUSTER) {
8951 if (--nr <= 0)
8952 return -1;
8969 if (--nr <= 0)
8970 return -1;
8984 * Idle-capacity scan converts util_fits_cpu() outcomes into preference ranks,
8985 * where lower values indicate a better fit - see select_idle_capacity().
8987 * A CPU that both fits the task and sits on a fully-idle SMT core is returned
8989 * its own "core", so the early return covers all fits-and-idle cases and the
8990 * core-tier ranks below become unreachable.
8993 * ------------------------------ --- ------ ---------------------------
8994 * ASYM_IDLE_UCLAMP_MISFIT -4 core Idle core; capacity fits
8996 * ASYM_IDLE_COMPLETE_MISFIT -3 core Idle core; capacity does
8998 * thread-tier rank: a busy
9002 * ASYM_IDLE_THREAD_FITS -2 thread Busy SMT sibling; capacity
9004 * ASYM_IDLE_THREAD_UCLAMP_MISFIT -1 thread Busy SMT sibling; capacity
9011 * ASYM_IDLE_CORE_BIAS (-3) is an offset, not a state. On an idle core,
9012 * fits += ASYM_IDLE_CORE_BIAS rebases thread-tier ranks into the core tier:
9014 * ASYM_IDLE_THREAD_UCLAMP_MISFIT (-1) + BIAS -> ASYM_IDLE_UCLAMP_MISFIT (-4)
9015 * ASYM_IDLE_THREAD_MISFIT (0) + BIAS -> ASYM_IDLE_COMPLETE_MISFIT (-3)
9017 * ASYM_IDLE_THREAD_FITS (-2) is never rebased because a fully-fitting idle-core
9018 * candidate early-returns from select_idle_capacity().
9021 ASYM_IDLE_UCLAMP_MISFIT = -4,
9028 ASYM_IDLE_CORE_BIAS = -3,
9047 int cpu, best_cpu = -1;
9052 cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr);
9058 if (sched_feat(SIS_UTIL) && sd->shared) {
9063 nr = READ_ONCE(sd->shared->nr_idle_scan) + 1;
9066 return -1;
9077 if (!has_idle_core && --nr <= 0)
9087 * sits on a fully-idle SMT core, this is a !SMT system, or
9089 * Short-circuit the rank-based selection and return
9105 * ASYM_IDLE_THREAD_MISFIT - does not fit
9106 * ASYM_IDLE_THREAD_UCLAMP_MISFIT - fits with the exception of UCLAMP_MIN
9107 * ASYM_IDLE_THREAD_FITS - fits with the exception of preferred_core
9142 * The asym-capacity wakeup path returns from select_idle_sibling()
9145 * idle-core preference did not win.
9166 * Note: gating on is_core_idle() also makes the early-bailout
9168 * recent_used_cpu) idle-core-aware on ASYM+SMT, which the
9186 int i, recent_used_cpu, prev_aff = -1;
9193 sync_entity_load_avg(&p->se);
9200 * per-cpu select_rq_mask usage
9223 * Allow a per-cpu kthread to stack with the wakee if the
9226 * per-cpu kthread that is now complete and the wakeup is
9233 this_rq()->nr_running <= 1 &&
9239 recent_used_cpu = p->recent_used_cpu;
9240 p->recent_used_cpu = prev;
9245 cpumask_test_cpu(recent_used_cpu, p->cpus_ptr) &&
9253 recent_used_cpu = -1;
9309 * cpu_util() - Estimates the amount of CPU capacity used by CFS tasks.
9312 * @dst_cpu: CPU @p migrates to, -1 if @p moves from @cpu or @p == NULL
9319 * recent utilization of currently non-runnable tasks on that CPU.
9327 * previously-executed tasks, which helps better deduce how busy a CPU will
9328 * be when a long-sleeping task wakes up. The contribution to CPU utilization
9342 * could be seen as over-utilized even though CPU1 has 20% of spare CPU
9345 * after task migrations (scheduler-driven DVFS).
9354 struct cfs_rq *cfs_rq = &cpu_rq(cpu)->cfs;
9355 unsigned long util = READ_ONCE(cfs_rq->avg.util_avg);
9359 * If @dst_cpu is -1 or @p migrates from @cpu to @dst_cpu remove its
9370 runnable = READ_ONCE(cfs_rq->avg.runnable_avg);
9372 runnable += READ_ONCE(p->se.avg.runnable_avg);
9375 READ_ONCE(p->se.avg.runnable_avg));
9382 util_est = READ_ONCE(cfs_rq->avg.util_est);
9385 * During wake-up @p isn't enqueued yet and doesn't contribute
9386 * to any cpu_rq(cpu)->cfs.avg.util_est.
9390 * During exec (@dst_cpu = -1) @p is enqueued and does
9391 * contribute to cpu_rq(cpu)->cfs.util_est.
9400 * p->on_rq = TASK_ON_RQ_MIGRATING;
9401 * -------------------------------- A
9405 * -------------------------------- B
9423 return cpu_util(cpu, NULL, -1, 0);
9428 return cpu_util(cpu, NULL, -1, 1);
9447 if (cpu != task_cpu(p) || !READ_ONCE(p->se.avg.last_update_time))
9450 return cpu_util(cpu, p, -1, 0);
9465 * The cfs,rt,dl utilization are the running times measured with rq->clock_task
9466 * which excludes things like IRQ and steal-time. These latter are then accrued
9484 * because of inaccuracies in how we track these -- see
9499 * - the computed DL bandwidth needed with the IRQ pressure which
9501 * - The minimum performance requirement for CFS and/or RT.
9509 if (!uclamp_is_used() && rt_rq_is_runnable(&rq->rt))
9537 * max - irq
9538 * U' = irq + --------- * U
9553 * energy_env - Utilization landscape for energy estimation.
9559 * @pd_cap: Entire perf domain capacity. (pd->nr_cpus * cpu_cap).
9585 eenv->task_busy_time = busy_time;
9599 * - A stable PD utilization, no matter which CPU of that PD we want to place
9602 * - A fair comparison between CPUs as the task contribution (task_util())
9607 * exceed @eenv->pd_cap.
9617 unsigned long util = cpu_util(cpu, p, -1, 0);
9622 eenv->pd_busy_time = min(eenv->pd_cap, busy_time);
9629 * Returns the maximum utilization among @eenv->cpus. This utilization can't
9630 * exceed @eenv->cpu_cap.
9671 return min(max_util, eenv->cpu_cap);
9684 unsigned long busy_time = eenv->pd_busy_time;
9688 busy_time = min(eenv->pd_cap, busy_time + eenv->task_busy_time);
9690 energy = em_cpu_energy(pd->em_pd, max_util, busy_time, eenv->cpu_cap);
9698 * find_energy_efficient_cpu(): Find most energy-efficient target CPU for the
9702 * out which of the CPU candidates is the most energy-efficient.
9719 * cluster-packing, and spreading inside a cluster. That should at least be
9726 * NOTE: Forkees are not accepted in the energy-aware wake-up path because
9730 * to be energy-inefficient in some use-cases. The alternative would be to
9733 * other use-cases too. So, until someone finds a better way to solve this,
9734 * let's keep things simple by re-using the existing slow path.
9742 struct root_domain *rd = this_rq()->rd;
9743 int cpu, best_energy_cpu, target = -1;
9744 int prev_fits = -1, best_fits = -1;
9751 pd = rcu_dereference_all(rd->pd);
9756 * Energy-aware wake-up happens on the lowest sched_domain starting
9761 sd = sd->parent;
9767 sync_entity_load_avg(&p->se);
9773 for (; pd; pd = pd->next) {
9776 long prev_spare_cap = -1, max_spare_cap = -1;
9779 int max_spare_cap_cpu = -1;
9780 int fits, max_fits = -1;
9800 if (!cpumask_test_cpu(cpu, p->cpus_ptr))
9819 * max-aggregated uclamp_{min, max}.
9856 base_energy = compute_energy(&eenv, pd, cpus, p, -1);
9859 if (prev_spare_cap > -1) {
9865 prev_delta -= base_energy;
9889 cur_delta -= base_energy;
9919 * Balances load by selecting the idlest CPU in the idlest group, or under
9927 int sync = (wake_flags & WF_SYNC) && !(current->flags & PF_EXITING);
9936 * required for stable ->cpus_allowed
9938 lockdep_assert_held(&p->pi_lock);
9943 cpumask_test_cpu(cpu, p->cpus_ptr))
9946 if (!is_rd_overutilized(this_rq()->rd)) {
9953 want_affine = !wake_wide(p) && cpumask_test_cpu(cpu, p->cpus_ptr);
9961 if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
9975 if (tmp->flags & sd_flag)
9995 * previous CPU. The caller guarantees p->pi_lock or task_rq(p)->lock is held.
9999 struct sched_entity *se = &p->se;
10008 * leading to an inflation after wake-up on the new rq.
10018 se->avg.last_update_time = 0;
10025 struct sched_entity *se = &p->se;
10044 if (!cpumask_intersects(p->cpus_ptr, cpumask))
10047 p->max_allowed_capacity = entry->capacity;
10074 if (cfs_rq->next && entity_before(cfs_rq->next, pse))
10083 if (cfs_rq->next && cfs_rq->next->slice < pse->slice)
10108 delta = rq_clock_task(rq) - se->exec_start;
10137 struct task_struct *donor = rq->donor;
10138 struct sched_entity *nse, *se = &donor->se, *pse = &p->se;
10139 struct cfs_rq *cfs_rq = &rq->cfs;
10145 if (p->sched_class != &fair_sched_class ||
10146 donor->sched_class != &fair_sched_class)
10156 * next-buddy nomination below.
10165 * Note: this also catches the edge-case of curr being in a throttled
10171 if (!sched_feat(PREEMPT_SHORT) && test_tsk_need_resched(rq->curr))
10184 * Preempt an idle entity in favor of a non-idle entity (and don't preempt
10198 if (unlikely(!normal_policy(p->policy)))
10205 if (pse->sched_delayed)
10212 if (sched_feat(PREEMPT_SHORT) && (pse->slice < se->slice)) {
10247 if (cfs_rq->h_nr_queued) {
10281 struct cfs_rq *cfs_rq = &rq->cfs;
10287 if (!cfs_rq->h_nr_queued)
10291 if (cfs_rq->curr && cfs_rq->curr->on_rq)
10315 __must_hold(__rq_lockp(dl_se->rq))
10317 return pick_task_fair(dl_se->rq, rf);
10322 struct sched_dl_entity *dl_se = &rq->fair_server;
10334 struct sched_entity *se = &prev->se;
10335 struct cfs_rq *cfs_rq = &rq->cfs;
10339 if (next && next->sched_class == &fair_sched_class)
10340 nse = &next->se;
10345 if (!nse || cfs_rq->h_curr)
10352 int d = nse->depth - se->depth;
10366 cfs_rq = &rq->cfs;
10367 se = &prev->se;
10368 WARN_ON_ONCE(cfs_rq->curr != se);
10369 cfs_rq->curr = NULL;
10370 if (se->on_rq)
10379 struct task_struct *curr = rq->donor;
10380 struct sched_entity *se = &curr->se;
10381 struct cfs_rq *cfs_rq = &rq->cfs;
10386 if (unlikely(rq->nr_running == 1))
10393 * Update run-time statistics of the 'current'.
10412 se->vruntime = se->deadline;
10419 struct sched_entity *se = &p->se;
10421 /* !se->on_rq also covers throttled task */
10422 if (!se->on_rq || se->sched_delayed)
10426 set_next_buddy(&task_rq(p)->cfs, se);
10434 * Fair scheduling class load-balancing methods.
10438 * The purpose of load-balancing is to achieve the same basic fairness the
10439 * per-CPU scheduler provides, namely provide a proportional amount of compute
10444 * Where W_i,n is the n-th weight average for CPU i. The instantaneous weight
10449 * Where w_i,j is the weight of the j-th runnable task on CPU i. This weight
10455 * W'_i,n = (2^n - 1) / 2^n * W_i,n + 1 / 2^n * W_i,0 (3)
10464 * imb_i,j = max{ avg(W/C), W_i/C_i } - min{ avg(W/C), W_j/C_j } (4)
10471 * - infeasible weights;
10472 * - local vs global optima in the discrete case. ]
10482 * of load-balance at each level inversely proportional to the number of CPUs in
10488 * \Sum { --- * --- * 2^i } = O(n) (5)
10490 * `- size of each group
10491 * | | `- number of CPUs doing load-balance
10492 * | `- freq
10493 * `- sum over all levels
10535 * W_i,0 = \Sum_j \Prod_k w_k * ----- (9)
10542 * w_i,j,k is the weight of the j-th runnable task in the k-th cgroup on CPU i.
10592 * There are tasks running on non-preferred LLC, possible to move
10638 /* The set of CPUs under consideration for load-balancing */
10653 * Is this task likely cache-hot:
10659 lockdep_assert_rq_held(env->src_rq);
10661 if (p->sched_class != &fair_sched_class)
10668 if (env->sd->flags & SD_SHARE_CPUCAPACITY)
10674 if (sched_feat(CACHE_HOT_BUDDY) && env->dst_rq->nr_running &&
10675 (&p->se == cfs_rq_of(&p->se)->next))
10678 if (sysctl_sched_migration_cost == -1)
10685 if (!sched_core_cookie_match(cpu_rq(env->dst_cpu), p))
10691 delta = rq_clock_task(env->src_rq) - p->se.exec_start;
10704 struct numa_group *numa_group = rcu_dereference_all(p->numa_group);
10711 if (!p->numa_faults || !(env->sd->flags & SD_NUMA))
10714 src_nid = cpu_to_node(env->src_cpu);
10715 dst_nid = cpu_to_node(env->dst_cpu);
10721 if (src_nid == p->numa_preferred_nid) {
10722 if (env->src_rq->nr_running > env->src_rq->nr_preferred_running)
10729 if (dst_nid == p->numa_preferred_nid)
10730 return -1;
10733 if (env->idle == CPU_IDLE)
10745 return src_weight - dst_weight;
10760 * dst_cfs_rq->nr_queued is greater than 1, if the task
10766 struct cfs_rq *dst_cfs_rq = &cpu_rq(dest_cpu)->cfs;
10768 if (sched_feat(PLACE_LAG) && dst_cfs_rq->h_nr_queued &&
10769 !entity_eligible(&task_rq(p)->cfs, &p->se))
10817 *util = READ_ONCE(sd_share->util_avg);
10818 *cap = READ_ONCE(sd_share->capacity);
10829 * of SMT-2, and it is also a safe cutoff for other SMT-n
10830 * platforms. SMT-1 has higher threshold because it is
10834 * if the preferred LLC is busier than the non-preferred LLC.
10837 * preferred LLC and the non-preferred LLC, and it will
10895 src_util = src_util < tsk_util ? 0 : src_util - tsk_util;
10916 * non-preferred LLC falls within sysctl_aggr_imb percent
10930 * On asymmetric CPU capacity domains, do not let cache-aware
10933 * the destination, trading a cache-locality gain for a capacity
10937 if ((env->sd->flags & SD_ASYM_CPUCAPACITY) && p &&
10938 !task_fits_cpu(p, env->dst_cpu) &&
10939 task_fits_cpu(p, env->src_cpu))
10959 src_cpu = env->src_cpu;
10960 dst_cpu = env->dst_cpu;
10961 grp = rcu_dereference_all(p->sched_cache_grp);
10965 cpu = READ_ONCE(grp->cpu);
10972 if (READ_ONCE(grp->cpu) != -1)
10973 WRITE_ONCE(grp->cpu, -1);
11002 if (cpus_share_cache(env->src_cpu, env->dst_cpu))
11010 * the cache-aware scheduling policy.
11012 if (env->src_rq->nr_pref_llc_running &&
11013 env->src_rq->nr_pref_llc_running == env->src_rq->cfs.h_nr_runnable) {
11022 if (env->migration_type == migrate_misfit)
11025 if (env->src_rq->nr_running <= 1)
11028 cur = rcu_dereference_all(env->src_rq->curr);
11029 if (cur && cur->sched_class == &fair_sched_class)
11033 can_migrate_llc(env->src_cpu, env->dst_cpu,
11044 * in env->migration_type, while active LB carries LBF_ACTIVE_LB_LLC in
11045 * env->flags to avoid overwriting env->migration_type.
11051 (env->migration_type == migrate_llc_task ||
11052 env->flags & LBF_ACTIVE_LB_LLC) &&
11053 READ_ONCE(p->preferred_llc) != llc_id(env->dst_cpu);
11057 * Check if migrating task p from env->src_cpu to
11058 * env->dst_cpu breaks LLC localiy.
11076 if (env->sd->nr_balance_failed >= env->sd->cache_nice_tries + 1)
11080 * We know the env->src_cpu has some tasks prefer to
11081 * run on env->dst_cpu, skip the tasks do not prefer
11082 * env->dst_cpu, and find the one that prefers.
11119 * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
11126 lockdep_assert_rq_held(env->src_rq);
11127 if (p->sched_task_hot)
11128 p->sched_task_hot = 0;
11136 * 5) are cache-hot on their current CPU, or
11139 if ((p->se.sched_delayed) && (env->migration_type != migrate_load))
11142 if (lb_throttled_hierarchy(p, env->dst_cpu))
11147 * For ineligible tasks we soft-limit them and only allow
11148 * them to migrate when nr_balance_failed is non-zero to
11149 * avoid load-balancing trying very hard to balance the load.
11151 if (!env->sd->nr_balance_failed &&
11152 task_is_ineligible_on_dst_cpu(p, env->dst_cpu))
11162 if (!cpumask_test_cpu(env->dst_cpu, p->cpus_ptr)) {
11165 schedstat_inc(p->stats.nr_failed_migrations_affine);
11167 env->flags |= LBF_SOME_PINNED;
11175 * - for NEWLY_IDLE
11176 * - if we have already computed one in current iteration
11177 * - if it's an active balance
11179 if (env->idle == CPU_NEWLY_IDLE ||
11180 env->flags & (LBF_DST_PINNED | LBF_ACTIVE_LB))
11183 /* Prevent to re-select dst_cpu via env's CPUs: */
11184 cpu = cpumask_first_and_and(env->dst_grpmask, env->cpus, p->cpus_ptr);
11187 env->flags |= LBF_DST_PINNED;
11188 env->new_dst_cpu = cpu;
11195 env->flags &= ~LBF_ALL_PINNED;
11197 if (task_on_cpu(env->src_rq, p) ||
11198 task_current_donor(env->src_rq, p)) {
11199 schedstat_inc(p->stats.nr_failed_migrations_running);
11210 if (env->flags & LBF_ACTIVE_LB)
11227 if (env->migration_type != migrate_llc_task)
11228 env->flags |= LBF_LLC_PINNED;
11238 if (!hot || env->sd->nr_balance_failed > env->sd->cache_nice_tries) {
11240 p->sched_task_hot = 1;
11244 schedstat_inc(p->stats.nr_failed_migrations_hot);
11249 * detach_task() -- detach the task for the migration specified in env
11253 lockdep_assert_rq_held(env->src_rq);
11255 if (p->sched_task_hot) {
11256 p->sched_task_hot = 0;
11257 schedstat_inc(env->sd->lb_hot_gained[env->idle]);
11258 schedstat_inc(p->stats.nr_forced_migrations);
11261 WARN_ON(task_current(env->src_rq, p));
11262 WARN_ON(task_current_donor(env->src_rq, p));
11264 deactivate_task(env->src_rq, p, DEQUEUE_NOCLOCK);
11265 set_task_cpu(p, env->dst_cpu);
11269 * detach_one_task() -- tries to dequeue exactly one task from env->src_rq, as
11278 lockdep_assert_rq_held(env->src_rq);
11281 &env->src_rq->cfs_tasks, se.group_node) {
11289 * lb_gained[env->idle] is updated (other is detach_tasks)
11293 schedstat_inc(env->sd->lb_gained[env->idle]);
11300 * detach_tasks() -- tries to detach up to imbalance load/util/tasks from
11307 struct list_head *tasks = &env->src_rq->cfs_tasks;
11312 lockdep_assert_rq_held(env->src_rq);
11318 if (env->src_rq->nr_running <= 1) {
11319 env->flags &= ~LBF_ALL_PINNED;
11323 if (env->imbalance <= 0)
11331 if (env->idle && env->src_rq->nr_running <= 1)
11334 env->loop++;
11336 if (env->loop > env->loop_max)
11340 if (env->loop > env->loop_break) {
11341 env->loop_break += SCHED_NR_MIGRATE_BREAK;
11342 env->flags |= LBF_NEED_BREAK;
11351 switch (env->migration_type) {
11356 * value. Make sure that env->imbalance decreases
11363 load < 16 && !env->sd->nr_balance_failed)
11372 if (shr_bound(load, env->sd->nr_balance_failed) > env->imbalance)
11375 env->imbalance -= load;
11381 if (shr_bound(util, env->sd->nr_balance_failed) > env->imbalance)
11384 env->imbalance -= util;
11388 env->imbalance--;
11393 if (task_fits_cpu(p, env->src_cpu))
11396 env->imbalance = 0;
11400 env->imbalance--;
11405 list_add(&p->se.group_node, &env->tasks);
11415 if (env->idle == CPU_NEWLY_IDLE)
11423 if (env->imbalance <= 0)
11428 if (p->sched_task_hot)
11429 schedstat_inc(p->stats.nr_failed_migrations_hot);
11431 list_move(&p->se.group_node, tasks);
11439 schedstat_add(env->sd->lb_gained[env->idle], detached);
11445 * attach_tasks() -- attaches all tasks detached by detach_tasks() to their
11450 struct list_head *tasks = &env->tasks;
11454 rq_lock(env->dst_rq, &rf);
11455 update_rq_clock(env->dst_rq);
11459 list_del_init(&p->se.group_node);
11461 attach_task(env->dst_rq, p);
11464 rq_unlock(env->dst_rq, &rf);
11470 if (cfs_rq->avg.load_avg)
11473 if (cfs_rq->avg.util_avg)
11498 WRITE_ONCE(rq->last_blocked_load_update_tick, jiffies);
11504 rq->has_blocked_load = 0;
11546 if (cfs_rq->nr_queued == 0)
11549 if (cfs_rq == &rq->cfs)
11575 * This needs to be done in a top-down fashion because the load of a child
11584 if (cfs_rq->last_h_load_update == now)
11587 WRITE_ONCE(cfs_rq->h_load_next, NULL);
11590 WRITE_ONCE(cfs_rq->h_load_next, se);
11591 if (cfs_rq->last_h_load_update == now)
11596 cfs_rq->h_load = cfs_rq_load_avg(cfs_rq);
11597 cfs_rq->last_h_load_update = now;
11600 while ((se = READ_ONCE(cfs_rq->h_load_next)) != NULL) {
11601 load = cfs_rq->h_load;
11602 load = div64_ul(load * se->avg.load_avg,
11605 cfs_rq->h_load = load;
11606 cfs_rq->last_h_load_update = now;
11615 return div64_ul(p->se.avg.load_avg * cfs_rq->h_load,
11621 struct cfs_rq *cfs_rq = &rq->cfs;
11633 return p->se.avg.load_avg;
11663 * sg_lb_stats - stats of a sched_group required for load-balancing:
11691 * sd_lb_stats - stats of a sched_domain required for load-balancing:
11748 free = max - used;
11756 struct sched_group *sdg = sd->groups;
11761 cpu_rq(cpu)->cpu_capacity = capacity;
11764 sdg->sgc->capacity = capacity;
11765 sdg->sgc->min_capacity = capacity;
11766 sdg->sgc->max_capacity = capacity;
11771 struct sched_domain *child = sd->child;
11772 struct sched_group *group, *sdg = sd->groups;
11776 interval = msecs_to_jiffies(sd->balance_interval);
11778 sdg->sgc->next_update = jiffies + interval;
11789 if (child->flags & SD_NUMA) {
11808 group = child->groups;
11810 struct sched_group_capacity *sgc = group->sgc;
11812 capacity += sgc->capacity;
11813 min_capacity = min(sgc->min_capacity, min_capacity);
11814 max_capacity = max(sgc->max_capacity, max_capacity);
11815 group = group->next;
11816 } while (group != child->groups);
11819 sdg->sgc->capacity = capacity;
11820 sdg->sgc->min_capacity = min_capacity;
11821 sdg->sgc->max_capacity = max_capacity;
11832 return ((rq->cpu_capacity * sd->imbalance_pct) <
11839 return rq->misfit_task_load;
11844 * groups is inadequate due to ->cpus_ptr constraints.
11853 * If we were to balance group-wise we'd place two tasks in the first group and
11873 return group->sgc->imbalance;
11891 if (sgs->sum_nr_running < sgs->group_weight)
11894 if ((sgs->group_capacity * imbalance_pct) <
11895 (sgs->group_runnable * 100))
11898 if ((sgs->group_capacity * 100) >
11899 (sgs->group_util * imbalance_pct))
11920 if (sched_energy_enabled() && !sgs->group_overutilized)
11923 if (sgs->sum_nr_running <= sgs->group_weight)
11926 if ((sgs->group_capacity * 100) <
11927 (sgs->group_util * imbalance_pct))
11930 if ((sgs->group_capacity * imbalance_pct) <
11931 (sgs->group_runnable * 100))
11945 if (sgs->group_llc_balance)
11951 if (sgs->group_asym_packing)
11954 if (sgs->group_smt_balance)
11957 if (sgs->group_misfit_task_load)
11967 * sched_use_asym_prio - Check whether asym_packing priority must be used
11979 if (!(sd->flags & SD_ASYM_PACKING))
11985 return sd->flags & SD_SHARE_CPUCAPACITY || is_core_idle(cpu);
11999 * sched_group_asym - Check if the destination CPU can do asym_packing balance
12001 * @sgs: Load-balancing statistics of the candidate busiest group
12017 if ((group->flags & SD_SHARE_CPUCAPACITY) &&
12018 (sgs->group_weight - sgs->idle_cpus != 1))
12021 return sched_asym(env->sd, env->dst_cpu, READ_ONCE(group->asym_prefer_cpu));
12031 return (sg1->flags & SD_SHARE_CPUCAPACITY) !=
12032 (sg2->flags & SD_SHARE_CPUCAPACITY);
12038 if (!env->idle)
12047 if (group->flags & SD_SHARE_CPUCAPACITY &&
12048 sgs->sum_h_nr_running > 1)
12062 if (!env->idle || !busiest->sum_nr_running)
12065 ncores_busiest = sds->busiest->cores;
12066 ncores_local = sds->local->cores;
12069 imbalance = busiest->sum_nr_running;
12070 lsub_positive(&imbalance, local->sum_nr_running);
12075 imbalance = ncores_local * busiest->sum_nr_running;
12076 lsub_positive(&imbalance, ncores_busiest * local->sum_nr_running);
12082 if (imbalance <= 1 && local->sum_nr_running == 0 &&
12083 busiest->sum_nr_running > 1)
12096 if (rq->cfs.h_nr_runnable != 1)
12115 if (!sched_cache_enabled() || env->idle == CPU_NEWLY_IDLE)
12119 if (env->sd->child != rcu_dereference_all(per_cpu(sd_llc, env->dst_cpu)))
12126 * Note: sd_share cannot be obtained via sd->child->shared,
12136 if (READ_ONCE(sd_share->util_avg) != sgs->group_util)
12137 WRITE_ONCE(sd_share->util_avg, sgs->group_util);
12139 if (unlikely(READ_ONCE(sd_share->capacity) != sgs->group_capacity))
12140 WRITE_ONCE(sd_share->capacity, sgs->group_capacity);
12153 if (env->sd->flags & SD_SHARE_LLC)
12161 if ((env->sd->flags & SD_ASYM_CPUCAPACITY) &&
12162 sgs->group_misfit_task_load)
12170 if (env->sd->nr_balance_failed >= env->sd->cache_nice_tries + 1)
12173 if (sgs->nr_pref_dst_llc &&
12175 env->dst_cpu, 0, true) == mig_llc)
12188 return sgs->nr_pref_dst_llc > busiest->nr_pref_dst_llc;
12211 * update_sg_lb_stats - Update sched_group's statistics for load balancing.
12213 * @sds: Load-balancing data with statistics of the local group.
12224 int i, nr_running, local_group, sd_flags = env->sd->flags;
12225 bool balancing_at_rd = !env->sd->parent;
12229 local_group = group == sds->local;
12231 for_each_cpu_and(i, sched_group_span(group), env->cpus) {
12235 sgs->group_load += load;
12236 sgs->group_util += cpu_util_cfs(i);
12237 sgs->group_runnable += cpu_runnable(rq);
12238 sgs->sum_h_nr_running += rq->cfs.h_nr_runnable;
12240 nr_running = rq->nr_running;
12241 sgs->sum_nr_running += nr_running;
12244 sgs->group_overutilized = 1;
12251 dst_llc = llc_id(env->dst_cpu);
12253 sd_tmp = rcu_dereference_all(rq->sd);
12254 if (sd_tmp && (unsigned int)dst_llc < sd_tmp->llc_max)
12255 sgs->nr_pref_dst_llc += sd_tmp->llc_counts[dst_llc];
12264 sgs->idle_cpus++;
12276 sgs->nr_numa_running += rq->nr_numa_running;
12277 sgs->nr_preferred_running += rq->nr_preferred_running;
12284 if (rq->misfit_task_load) {
12299 if (capacity_greater(capacity_of(env->dst_cpu),
12300 group->sgc->max_capacity) &&
12301 (sgs->group_misfit_task_load < rq->misfit_task_load))
12302 sgs->group_misfit_task_load = rq->misfit_task_load;
12304 } else if (env->idle && sched_reduced_capacity(rq, env->sd)) {
12306 if (sgs->group_misfit_task_load < load)
12307 sgs->group_misfit_task_load = load;
12311 sgs->group_capacity = group->sgc->capacity;
12313 sgs->group_weight = group->group_weight;
12317 if (env->idle && sgs->sum_h_nr_running &&
12319 sgs->group_asym_packing = 1;
12323 sgs->group_smt_balance = 1;
12327 sgs->group_llc_balance = 1;
12330 sgs->group_type = group_classify(env->sd->imbalance_pct, group, sgs);
12334 if (sgs->group_type == group_overloaded)
12335 sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
12336 sgs->group_capacity;
12340 * update_sd_pick_busiest - return 1 on busiest group
12357 struct sg_lb_stats *busiest = &sds->busiest_stat;
12360 if (!sgs->sum_h_nr_running)
12374 if ((env->sd->flags & SD_ASYM_CPUCAPACITY) &&
12375 (sgs->group_type == group_misfit_task) &&
12376 (!env->dst_core_idle ||
12377 !capacity_greater(capacity_of(env->dst_cpu), sg->sgc->max_capacity) ||
12378 sds->local_stat.group_type != group_has_spare))
12383 * per-CPU capacity. Migrating tasks to less capable CPUs may harm
12387 if ((env->sd->flags & SD_ASYM_CPUCAPACITY) &&
12388 (sgs->group_type <= group_fully_busy) &&
12389 (capacity_greater(sg->sgc->min_capacity, capacity_of(env->dst_cpu))))
12392 if (sgs->group_type > busiest->group_type)
12395 if (sgs->group_type < busiest->group_type)
12403 switch (sgs->group_type) {
12406 return sgs->avg_load > busiest->avg_load;
12421 return sched_asym_prefer(READ_ONCE(sds->busiest->asym_prefer_cpu),
12422 READ_ONCE(sg->asym_prefer_cpu));
12429 return sgs->group_misfit_task_load > busiest->group_misfit_task_load;
12436 if (sgs->idle_cpus != 0 || busiest->idle_cpus != 0)
12454 if (sgs->avg_load < busiest->avg_load)
12457 if (sgs->avg_load == busiest->avg_load) {
12459 * SMT sched groups need more help than non-SMT groups.
12462 if (sds->busiest->flags & SD_SHARE_CPUCAPACITY)
12474 if (smt_vs_nonsmt_groups(sds->busiest, sg)) {
12475 if (sg->flags & SD_SHARE_CPUCAPACITY && sgs->sum_h_nr_running <= 1)
12489 if (sgs->idle_cpus > busiest->idle_cpus)
12491 else if ((sgs->idle_cpus == busiest->idle_cpus) &&
12492 (sgs->sum_nr_running <= busiest->sum_nr_running))
12504 if (sgs->sum_h_nr_running > sgs->nr_numa_running)
12506 if (sgs->sum_h_nr_running > sgs->nr_preferred_running)
12513 if (rq->nr_running > rq->nr_numa_running)
12515 if (rq->nr_running > rq->nr_preferred_running)
12535 * task_running_on_cpu - return 1 if @p is running on @cpu.
12541 if (cpu != task_cpu(p) || !READ_ONCE(p->se.avg.last_update_time))
12551 * idle_cpu_without - would a given CPU be idle without p ?
12561 if (rq->curr != rq->idle && rq->curr != p)
12565 * rq->nr_running can't be used but an updated version without the
12570 if (rq->ttwu_pending)
12577 * update_sg_wakeup_stats - Update sched_group's statistics for wakeup.
12578 * @sd: The sched_domain level to look for idlest group.
12581 * @p: The task for which we look for the idlest group/CPU.
12593 if (sd->flags & SD_ASYM_CPUCAPACITY)
12594 sgs->group_misfit_task_load = 1;
12596 for_each_cpu_and(i, sched_group_span(group), p->cpus_ptr) {
12600 sgs->group_load += cpu_load_without(rq, p);
12601 sgs->group_util += cpu_util_without(i, p);
12602 sgs->group_runnable += cpu_runnable_without(rq, p);
12604 sgs->sum_h_nr_running += rq->cfs.h_nr_runnable - local;
12606 nr_running = rq->nr_running - local;
12607 sgs->sum_nr_running += nr_running;
12613 sgs->idle_cpus++;
12616 if (sd->flags & SD_ASYM_CPUCAPACITY &&
12617 sgs->group_misfit_task_load &&
12619 sgs->group_misfit_task_load = 0;
12623 sgs->group_capacity = group->sgc->capacity;
12625 sgs->group_weight = group->group_weight;
12627 sgs->group_type = group_classify(sd->imbalance_pct, group, sgs);
12633 if (sgs->group_type == group_fully_busy ||
12634 sgs->group_type == group_overloaded)
12635 sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
12636 sgs->group_capacity;
12639 static bool update_pick_idlest(struct sched_group *idlest,
12644 if (sgs->group_type < idlest_sgs->group_type)
12647 if (sgs->group_type > idlest_sgs->group_type)
12651 * The candidate and the current idlest group are the same type of
12652 * group. Let check which one is the idlest according to the type.
12655 switch (sgs->group_type) {
12659 if (idlest_sgs->avg_load <= sgs->avg_load)
12672 if (idlest->sgc->max_capacity >= group->sgc->max_capacity)
12678 if (idlest_sgs->idle_cpus > sgs->idle_cpus)
12682 if (idlest_sgs->idle_cpus == sgs->idle_cpus &&
12683 idlest_sgs->group_util <= sgs->group_util)
12701 struct sched_group *idlest = NULL, *local = NULL, *group = sd->groups;
12715 p->cpus_ptr))
12734 if (!local_group && update_pick_idlest(idlest, &idlest_sgs, group, sgs)) {
12735 idlest = group;
12739 } while (group = group->next, group != sd->groups);
12742 /* There is no idlest group to push tasks to */
12743 if (!idlest)
12748 return idlest;
12751 * If the local group is idler than the selected idlest group
12758 * If the local group is busier than the selected idlest group
12762 return idlest;
12770 (sd->imbalance_pct-100) / 100;
12777 * cross-domain, add imbalance to the load on the remote node
12781 if ((sd->flags & SD_NUMA) &&
12787 * idlest group don't try and push any tasks.
12792 if (100 * local_sgs.avg_load <= sd->imbalance_pct * idlest_sgs.avg_load)
12805 if (local->sgc->max_capacity >= idlest->sgc->max_capacity)
12811 if (sd->flags & SD_NUMA) {
12812 int imb_numa_nr = sd->imb_numa_nr;
12819 if (cpu_to_node(this_cpu) == p->numa_preferred_nid)
12822 idlest_cpu = cpumask_first(sched_group_span(idlest));
12823 if (cpu_to_node(idlest_cpu) == p->numa_preferred_nid)
12824 return idlest;
12835 if (p->nr_cpus_allowed != NR_CPUS) {
12836 unsigned int w = cpumask_weight_and(p->cpus_ptr,
12838 imb_numa_nr = min(w, sd->imb_numa_nr);
12841 imbalance = abs(local_sgs.idle_cpus - idlest_sgs.idle_cpus);
12861 return idlest;
12868 struct sched_domain *sd = env->sd;
12879 if (!sched_feat(SIS_UTIL) || env->idle == CPU_NEWLY_IDLE)
12882 sd_share = sd->shared;
12892 * let y = SCHED_CAPACITY_SCALE - p * x^2 [1]
12910 * y = SCHED_CAPACITY_SCALE -
12916 llc_weight = sd->span_weight;
12920 pct = sd->imbalance_pct;
12924 y = SCHED_CAPACITY_SCALE - tmp;
12929 if ((int)y != sd_share->nr_idle_scan)
12930 WRITE_ONCE(sd_share->nr_idle_scan, (int)y);
12934 * update_sd_lb_stats - Update sched_domain's statistics for load balancing.
12941 struct sched_group *sg = env->sd->groups;
12942 struct sg_lb_stats *local = &sds->local_stat;
12947 env->dst_core_idle = !sched_smt_active() || is_core_idle(env->dst_cpu);
12953 local_group = cpumask_test_cpu(env->dst_cpu, sched_group_span(sg));
12955 sds->local = sg;
12958 if (env->idle != CPU_NEWLY_IDLE ||
12959 time_after_eq(jiffies, sg->sgc->next_update))
12960 update_group_capacity(env->sd, env->dst_cpu);
12966 sds->busiest = sg;
12967 sds->busiest_stat = *sgs;
12970 sg_overutilized |= sgs->group_overutilized;
12973 sds->total_load += sgs->group_load;
12974 sds->total_capacity += sgs->group_capacity;
12976 sum_util += sgs->group_util;
12977 sg = sg->next;
12978 } while (sg != env->sd->groups);
12985 if (sds->busiest)
12986 sds->prefer_sibling = !!(sds->busiest->flags & SD_PREFER_SIBLING);
12989 if (env->sd->flags & SD_NUMA)
12990 env->fbq_type = fbq_classify_group(&sds->busiest_stat);
12992 if (!env->sd->parent) {
12994 set_rd_overloaded(env->dst_rq->rd, sg_overloaded);
12996 /* Update over-utilization (tipping point, U >= 0) indicator */
12997 set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
12999 set_rd_overutilized(env->dst_rq->rd, sg_overutilized);
13006 * calculate_imbalance - Calculate the amount of imbalance present within the
13015 local = &sds->local_stat;
13016 busiest = &sds->busiest_stat;
13018 if (busiest->group_type == group_misfit_task) {
13019 if (env->sd->flags & SD_ASYM_CPUCAPACITY) {
13021 env->migration_type = migrate_misfit;
13022 env->imbalance = 1;
13028 env->migration_type = migrate_load;
13029 env->imbalance = busiest->group_misfit_task_load;
13034 if (busiest->group_type == group_asym_packing) {
13039 env->migration_type = migrate_task;
13040 env->imbalance = busiest->sum_h_nr_running;
13044 if (busiest->group_type == group_smt_balance) {
13046 env->migration_type = migrate_task;
13047 env->imbalance = 1;
13052 if (busiest->group_type == group_llc_balance) {
13054 env->migration_type = migrate_llc_task;
13055 env->imbalance = 1;
13060 if (busiest->group_type == group_imbalanced) {
13062 * In the group_imb case we cannot rely on group-wide averages
13063 * to ensure CPU-load equilibrium, try to move any task to fix
13067 env->migration_type = migrate_task;
13068 env->imbalance = 1;
13076 if (local->group_type == group_has_spare) {
13077 if ((busiest->group_type > group_fully_busy) &&
13078 !(env->sd->flags & SD_SHARE_LLC)) {
13087 env->migration_type = migrate_util;
13088 env->imbalance = max(local->group_capacity, local->group_util) -
13089 local->group_util;
13098 if (env->idle && env->imbalance == 0) {
13099 env->migration_type = migrate_task;
13100 env->imbalance = 1;
13106 if (busiest->group_weight == 1 || sds->prefer_sibling) {
13111 env->migration_type = migrate_task;
13112 env->imbalance = sibling_imbalance(env, sds, busiest, local);
13119 env->migration_type = migrate_task;
13120 env->imbalance = max_t(long, 0,
13121 (local->idle_cpus - busiest->idle_cpus));
13126 if (env->sd->flags & SD_NUMA) {
13127 env->imbalance = adjust_numa_imbalance(env->imbalance,
13128 local->sum_nr_running + 1,
13129 env->sd->imb_numa_nr);
13134 env->imbalance >>= 1;
13143 if (local->group_type < group_overloaded) {
13149 local->avg_load = (local->group_load * SCHED_CAPACITY_SCALE) /
13150 local->group_capacity;
13156 if (local->avg_load >= busiest->avg_load) {
13157 env->imbalance = 0;
13161 sds->avg_load = (sds->total_load * SCHED_CAPACITY_SCALE) /
13162 sds->total_capacity;
13168 if (local->avg_load >= sds->avg_load) {
13169 env->imbalance = 0;
13183 env->migration_type = migrate_load;
13184 env->imbalance = min(
13185 (busiest->avg_load - sds->avg_load) * busiest->group_capacity,
13186 (sds->avg_load - local->avg_load) * local->group_capacity
13213 * sched_balance_find_src_group - Returns the busiest group within the sched_domain
13220 * Return: - The busiest group if imbalance exists.
13242 if (busiest->group_type == group_misfit_task)
13245 if (!is_rd_overutilized(env->dst_rq->rd) &&
13246 rcu_dereference_all(env->dst_rq->rd->pd))
13250 if (busiest->group_type == group_asym_packing)
13258 if (busiest->group_type == group_imbalanced)
13266 if (local->group_type > busiest->group_type)
13273 if (local->group_type == group_overloaded) {
13278 if (local->avg_load >= busiest->avg_load)
13289 if (local->avg_load >= sds.avg_load)
13296 if (100 * busiest->avg_load <=
13297 env->sd->imbalance_pct * local->avg_load)
13305 if (sds.prefer_sibling && local->group_type == group_has_spare &&
13306 (busiest->group_type == group_llc_balance ||
13310 if (busiest->group_type != group_overloaded) {
13311 if (!env->idle) {
13320 if (busiest->group_type == group_smt_balance &&
13326 if (busiest->group_weight > 1 &&
13327 local->idle_cpus <= (busiest->idle_cpus + 1)) {
13340 if (busiest->sum_h_nr_running == 1) {
13351 return env->imbalance ? sds.busiest : NULL;
13354 env->imbalance = 0;
13359 * sched_balance_find_src_rq - find the busiest runqueue among the CPUs in the group.
13372 for_each_cpu_and(i, sched_group_span(group), env->cpus) {
13382 * - regular: there are !numa tasks
13383 * - remote: there are numa tasks that run on the 'wrong' node
13384 * - all: there is no distinction
13399 if (rt > env->fbq_type)
13402 nr_running = rq->cfs.h_nr_runnable;
13410 * eventually lead to active_balancing high->low capacity.
13411 * Higher per-CPU capacity is considered better than balancing
13414 if (env->sd->flags & SD_ASYM_CPUCAPACITY &&
13417 (get_actual_cpu_capacity(env->dst_cpu) ==
13430 !capacity_greater(capacity_of(env->dst_cpu), capacity))
13441 if (sched_asym(env->sd, i, env->dst_cpu) && nr_running == 1)
13444 switch (env->migration_type) {
13452 if (nr_running == 1 && load > env->imbalance &&
13453 !check_cpu_capacity(rq, env->sd))
13505 if (rq->misfit_task_load > busiest_load) {
13506 busiest_load = rq->misfit_task_load;
13514 sd_tmp = rcu_dereference_all(rq->sd);
13515 dst_llc = llc_id(env->dst_cpu);
13517 if (sd_tmp && (unsigned)dst_llc < sd_tmp->llc_max) {
13519 sd_tmp->llc_counts[dst_llc];
13554 return env->idle && sched_use_asym_prio(env->sd, env->dst_cpu) &&
13555 (sched_asym_prefer(env->dst_cpu, env->src_cpu) ||
13556 !sched_use_asym_prio(env->sd, env->src_cpu));
13562 struct sched_domain *sd = env->sd;
13569 if ((env->migration_type == migrate_task) &&
13570 (sd->nr_balance_failed > sd->cache_nice_tries+2))
13578 struct sched_domain *sd = env->sd;
13595 if (env->idle &&
13596 (env->src_rq->cfs.h_nr_runnable == 1)) {
13597 if ((check_cpu_capacity(env->src_rq, sd)) &&
13598 (capacity_of(env->src_cpu)*sd->imbalance_pct < capacity_of(env->dst_cpu)*100))
13602 if (env->migration_type == migrate_misfit ||
13603 env->migration_type == migrate_llc_task)
13614 * it shouldn't be repurposed just to flag an LLC-directed active
13619 if (env->migration_type == migrate_llc_task)
13628 struct sched_group *sg = env->sd->groups;
13629 int cpu, idle_smt = -1;
13635 if (!cpumask_test_cpu(env->dst_cpu, env->cpus))
13645 if (env->idle == CPU_NEWLY_IDLE) {
13646 if (env->dst_rq->nr_running > 0 || env->dst_rq->ttwu_pending)
13653 for_each_cpu_and(cpu, swb_cpus, env->cpus) {
13663 !(env->sd->flags & SD_SHARE_CPUCAPACITY) &&
13665 if (idle_smt == -1)
13677 * Are we the first idle core in a non-SMT domain or higher,
13680 return cpu == env->dst_cpu;
13684 if (idle_smt != -1)
13685 return idle_smt == env->dst_cpu;
13688 return group_balance_cpu(sg) == env->dst_cpu;
13697 switch (env->migration_type) {
13699 __schedstat_add(sd->lb_imbalance_load[idle], env->imbalance);
13702 __schedstat_add(sd->lb_imbalance_util[idle], env->imbalance);
13705 __schedstat_add(sd->lb_imbalance_task[idle], env->imbalance);
13708 __schedstat_add(sd->lb_imbalance_misfit[idle], env->imbalance);
13716 * This flag serializes load-balancing passes over large domains
13717 * (above the NODE topology level) - only one load-balancing instance
13721 * - Note that load-balancing passes triggered while another one
13722 * is executing are skipped and not re-tried.
13724 * - Also note that this does not serialize rebalance_domains()
13725 * execution, as non-SD_SERIALIZE domains will still be
13726 * load-balanced in parallel.
13739 struct sched_domain *sd_parent = sd->parent;
13748 .dst_grpmask = group_balance_mask(sd->groups),
13759 schedstat_inc(sd->lb_count[idle]);
13767 if (!need_unlock && (sd->flags & SD_SERIALIZE)) {
13777 schedstat_inc(sd->lb_nobusyg[idle]);
13783 schedstat_inc(sd->lb_nobusyq[idle]);
13791 env.src_cpu = busiest->cpu;
13797 if (busiest->nr_running > 1) {
13800 * an imbalance but busiest->nr_running <= 1, the group is
13804 env.loop_max = min(sysctl_sched_nr_migrate, busiest->nr_running);
13811 * cur_ld_moved - load moved in current iteration
13812 * ld_moved - cumulative load moved across iterations
13819 * unlock busiest->lock, and we are able to be sure
13848 * nohz-idle), we now have balance_cpu in a position to move
13859 /* Prevent to re-select dst_cpu via env's CPUs */
13879 int *group_imbalance = &sd_parent->groups->sgc->imbalance;
13906 sd->nr_balance_failed = 0;
13910 schedstat_inc(sd->lb_failed[idle]);
13929 sd->nr_balance_failed++;
13940 if (!cpumask_test_cpu(this_cpu, busiest->curr->cpus_ptr))
13947 * ->active_balance synchronizes accesses to
13948 * ->active_balance_work. Once set, it's cleared
13951 if (busiest->active_balance)
13956 * scheduling out its ->curr task (->on_rq := 0), no
13959 if (!busiest->curr->on_rq)
13962 busiest->active_balance = 1;
13963 busiest->push_cpu = this_cpu;
13970 &busiest->active_balance_work);
13976 sd->balance_interval = sd->min_interval;
13986 int *group_imbalance = &sd_parent->groups->sgc->imbalance;
13998 schedstat_inc(sd->lb_balanced[idle]);
14000 sd->nr_balance_failed = 0;
14021 sd->balance_interval < MAX_PINNED_INTERVAL) ||
14022 sd->balance_interval < sd->max_interval)
14023 sd->balance_interval *= 2;
14034 unsigned long interval = sd->balance_interval;
14037 interval *= sd->busy_factor;
14048 interval -= 1;
14062 next = sd->last_balance + interval;
14078 int target_cpu = busiest_rq->push_cpu;
14086 * Between queueing the stop-work and running it is a hole in which
14095 !busiest_rq->active_balance))
14099 if (busiest_rq->nr_running <= 1)
14105 * Bjorn Helgaas on a 128-CPU setup.
14121 .src_cpu = busiest_rq->cpu,
14127 schedstat_inc(sd->alb_count);
14132 schedstat_inc(sd->alb_pushed);
14134 sd->nr_balance_failed = 0;
14136 schedstat_inc(sd->alb_failed);
14141 busiest_rq->active_balance = 0;
14164 * This trades load-balance latency on larger machines for less cross talk.
14173 sd->newidle_call++;
14174 sd->newidle_success += success;
14176 if (sd->newidle_call >= 1024) {
14178 s64 delta = now - sd->newidle_stamp;
14179 sd->newidle_stamp = now;
14189 * 1024 - 4 s - 128 Hz
14190 * 512 - 2 s - 256 Hz
14191 * 256 - 1 s - 512 Hz
14192 * 128 - .5 s - 1024 Hz
14193 * 64 - .25 s - 2048 Hz
14198 ratio += sd->newidle_success;
14200 sd->newidle_ratio = min(1024, ratio);
14201 sd->newidle_call /= 2;
14202 sd->newidle_success /= 2;
14209 unsigned long next_decay = sd->last_decay_max_lb_cost + HZ;
14215 if (cost > sd->max_newidle_lb_cost) {
14220 sd->max_newidle_lb_cost = cost;
14221 sd->last_decay_max_lb_cost = now;
14229 sd->max_newidle_lb_cost = (sd->max_newidle_lb_cost * 253) / 256;
14230 sd->last_decay_max_lb_cost = now;
14246 int cpu = rq->cpu;
14263 max_cost += sd->max_newidle_lb_cost;
14277 if (time_after_eq(jiffies, sd->last_balance + interval)) {
14281 * env->dst_cpu, so we can't know our idle
14287 sd->last_balance = jiffies;
14290 if (time_after(next_balance, sd->last_balance + interval)) {
14291 next_balance = sd->last_balance + interval;
14297 * Ensure the rq-wide value also decays but keep it at a
14298 * reasonable floor to avoid funnies with rq->avg_idle.
14300 rq->max_idle_balance_cost =
14311 rq->next_balance = next_balance;
14317 return unlikely(!rcu_dereference_sched(rq->sd));
14324 * - When one of the busy CPUs notices that there may be an idle rebalancing
14331 int ilb_cpu, fallback = -1;
14336 * Reuse the per-CPU select_rq_mask, which is protected from concurrent
14381 * Kick a CPU to do the NOHZ balancing, if it is time for it, via a cross-CPU
14422 smp_call_function_single_async(ilb_cpu, &cpu_rq(ilb_cpu)->nohz_csd);
14434 int nr_busy, i, cpu = rq->cpu;
14437 if (unlikely(rq->idle_balance))
14469 if (rq->nr_running >= 2) {
14474 sd = rcu_dereference_all(rq->sd);
14480 if (rq->cfs.h_nr_runnable >= 1 && check_cpu_capacity(rq, sd)) {
14527 * increase the overall cache utilization), we need a less-loaded LLC
14531 * the others are - so just get a NOHZ balance going if it looks
14534 nr_busy = atomic_read(&sds->nr_busy_cpus);
14552 * sd->nohz_idle only pairs with nr_busy_cpus on sd->shared; if this
14555 if (!sd || !sd->shared || !sd->nohz_idle)
14557 sd->nohz_idle = 0;
14559 atomic_inc(&sd->shared->nr_busy_cpus);
14566 if (likely(!rq->nohz_tick_stopped))
14569 rq->nohz_tick_stopped = 0;
14570 cpumask_clear_cpu(rq->cpu, nohz.idle_cpus_mask);
14572 set_cpu_sd_state_busy(rq->cpu);
14580 /* See set_cpu_sd_state_busy(): nohz_idle is only used with sd->shared. */
14581 if (!sd || !sd->shared || sd->nohz_idle)
14583 sd->nohz_idle = 1;
14585 atomic_dec(&sd->shared->nr_busy_cpus);
14603 * Can be set safely without rq->lock held
14605 * rq->lock is held during the check and the clear
14607 rq->has_blocked_load = 1;
14615 if (rq->nohz_tick_stopped)
14622 rq->nohz_tick_stopped = 1;
14646 unsigned int cpu = rq->cpu;
14648 if (!rq->has_blocked_load)
14654 if (!time_after(jiffies, READ_ONCE(rq->last_blocked_load_update_tick)))
14659 return rq->has_blocked_load;
14674 int this_cpu = this_rq->cpu;
14731 if (time_after_eq(jiffies, rq->next_balance)) {
14742 if (time_after(next_balance, rq->next_balance)) {
14743 next_balance = rq->next_balance;
14772 unsigned int flags = this_rq->nohz_idle_balance;
14777 this_rq->nohz_idle_balance = 0;
14818 int this_cpu = this_rq->cpu;
14821 if (this_rq->avg_idle < sysctl_sched_migration_cost)
14852 * < 0 - we released the lock and there are !fair tasks present
14853 * 0 - failed, no new tasks
14854 * > 0 - success, new (fair) tasks present
14860 int this_cpu = this_rq->cpu;
14872 if (this_rq->ttwu_pending)
14880 this_rq->idle_stamp = rq_clock(this_rq);
14890 * for load-balance and preemption/IRQs are still disabled avoiding
14892 * re-start the picking loop.
14896 sd = rcu_dereference_sched_domain(this_rq->sd);
14900 if (!get_rd_overloaded(this_rq->rd) ||
14901 this_rq->avg_idle < sd->max_newidle_lb_cost) {
14909 * calculation because it can be quite costly -- this ensures we skip
14923 if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost)
14926 if (sd->flags & SD_BALANCE_NEWIDLE) {
14929 if (sched_feat(NI_RANDOM) && sd->newidle_ratio < 1024) {
14936 weight = 1 + sd->newidle_ratio;
14949 domain_cost = t1 - t0;
14970 if (curr_cost > this_rq->max_idle_balance_cost)
14971 this_rq->max_idle_balance_cost = curr_cost;
14978 if (this_rq->cfs.h_nr_queued && !pulled_task)
14983 pulled_task = -1;
14987 if (time_after(this_rq->next_balance, next_balance))
14988 this_rq->next_balance = next_balance;
14991 this_rq->idle_stamp = 0;
15003 * - directly from the local sched_tick() for periodic load balancing
15005 * - indirectly from a remote sched_tick() for NOHZ idle balancing
15006 * through the SMP cross-call nohz_csd_func()
15011 enum cpu_idle_type idle = this_rq->idle_balance;
15024 sched_balance_update_blocked_averages(this_rq->cpu);
15040 if (time_after_eq(jiffies, rq->next_balance))
15068 u64 rtime = se->sum_exec_runtime - se->prev_sum_exec_runtime;
15069 u64 slice = se->slice;
15091 * MIN_NR_TASKS_DURING_FORCEIDLE - 1 tasks and use that to check
15094 if (rq->core->core_forceidle_count && rq->cfs.h_nr_queued == 1 &&
15095 __entity_slice_used(&curr->se, MIN_NR_TASKS_DURING_FORCEIDLE))
15111 * dt_i = ---------- dt (1)
15117 * s_i = --- d[t]_i (2)
15125 * S = ---------- dt (3)
15130 * lag(i) = S - s_i (4)
15142 * be learned. We can combine (1)-(3) or (4)-(5) and express S in s_i:
15145 * S = -------------- (6)
15150 * is two-fold. Firstly, computing S in that way requires a 64bit division
15152 * the steady-state, it doesn't handle dynamics.
15154 * Anyway, in (6): s_i -> x + (s_i - x), to get:
15156 * \Sum_i w_i (s_i - x)
15157 * S - x = -------------------- (7)
15164 * possible to generalize to multiple runqueues -- however it gets really
15166 * first counter-example.
15168 * Luckily I think we can avoid needing a full multi-queue variant for
15169 * core-scheduling (or load-balancing). The crucial observation is that we
15170 * only actually need this comparison in the presence of forced-idle; only
15176 * answer is only interesting if one of them is forced-idle]
15178 * And (under assumption of SMT2) when there is forced-idle, there is only
15189 * S_k = --- (9)
15195 * S_k+l = --------- (10)
15200 * lag_k+l(i) := S_k+l - s_i (11)
15207 * a) when a runqueue enters force-idle, sync it against it's sibling rq(s)
15208 * using (7); this only requires storing single 'time'-stamps.
15210 * b) when comparing tasks between 2 runqueues of which one is forced-idle,
15215 * boundaries, but I think we can avoid that. The force-idle is for the
15225 * get re-elected. So far so simple, right?
15228 * we sync to 0 and let the idle one build up lag to get re-election. Now
15230 * again would destroy the built-up lag from the queue that was already
15235 * less := !((s64)(s_a - s_b) <= 0)
15237 * (v_a - S_a) - (v_b - S_b) == v_a - v_b - S_a + S_b
15238 * == v_a - (v_b - S_a + S_b)
15240 * IOW, we can recast the (lag) comparison to a one-sided difference.
15247 * and for already idle queues to preserve their build-up lag.
15263 * se_fi_update - Update the cfs_rq->zero_vruntime_fi in a CFS hierarchy if needed.
15272 if (cfs_rq->forceidle_seq == fi_seq)
15274 cfs_rq->forceidle_seq = fi_seq;
15277 cfs_rq->zero_vruntime_fi = cfs_rq->zero_vruntime;
15283 struct sched_entity *se = &p->se;
15285 if (p->sched_class != &fair_sched_class)
15288 se_fi_update(se, rq->core->core_forceidle_seq, in_fi);
15295 const struct sched_entity *sea = &a->se;
15296 const struct sched_entity *seb = &b->se;
15301 WARN_ON_ONCE(task_rq(b)->core != rq->core);
15303 cfs_rqa = &task_rq(a)->cfs;
15304 cfs_rqb = &task_rq(b)->cfs;
15311 delta = vruntime_op(sea->vruntime, "-", seb->vruntime) +
15312 vruntime_op(cfs_rqb->zero_vruntime_fi, "-", cfs_rqa->zero_vruntime_fi);
15324 cfs_rq = &cpu_rq(cpu)->cfs;
15342 struct sched_entity *se = &curr->se;
15344 if (se->on_rq) {
15355 se = &curr->se;
15356 reweight_eevdf(cfs_rq, se, weight, se->on_rq);
15375 * - child not yet on the tasklist
15376 * - preemption disabled
15393 if (p->prio == oldprio)
15396 if (rq->cfs.h_nr_queued == 1)
15405 if (p->prio > oldprio)
15431 se = se->parent;
15454 * - A forked task which hasn't been woken up by wake_up_new_task().
15455 * - A task which has been woken up by try_to_wake_up() but is
15458 if (!se->avg.last_update_time)
15481 struct sched_entity *se = &p->se;
15488 struct sched_entity *se = &p->se;
15495 if (p->se.sched_delayed)
15506 WARN_ON_ONCE(p->se.sched_delayed);
15527 struct sched_entity *se = &p->se;
15529 struct cfs_rq *cfs_rq = &rq->cfs;
15531 bool on_rq = se->on_rq;
15542 !first || !cfs_rq->h_curr)
15555 se = &p->se;
15556 cfs_rq->curr = se;
15559 reweight_eevdf(cfs_rq, se, weight, se->on_rq);
15569 list_move(&se->group_node, &rq->cfs_tasks);
15574 WARN_ON_ONCE(se->sched_delayed);
15585 cfs_rq->tasks_timeline = RB_ROOT_CACHED;
15586 cfs_rq->zero_vruntime = (u64)(-(1LL << 20));
15587 raw_spin_lock_init(&cfs_rq->removed.lock);
15597 if (READ_ONCE(p->__state) == TASK_NEW)
15602 /* Tell se's cfs_rq has been changed -- migrated */
15603 p->se.avg.last_update_time = 0;
15610 free_percpu(tg->cfs_rq);
15624 tg->cfs_rq = &state->cfs_rq;
15625 tg->shares = NICE_0_LOAD;
15680 * check on_list without danger of it being re-added.
15682 if (cfs_rq->on_list) {
15695 cfs_rq->tg = tg;
15696 cfs_rq->rq = rq;
15704 se->cfs_rq = &rq->cfs;
15705 se->depth = 0;
15707 se->cfs_rq = parent->my_q;
15708 se->depth = parent->depth + 1;
15711 se->my_q = cfs_rq;
15713 update_load_set(&se->load, NICE_0_LOAD);
15714 se->parent = parent;
15729 return -EINVAL;
15733 if (tg->shares == shares)
15736 tg->shares = shares;
15761 ret = -EINVAL;
15774 return -EINVAL;
15777 return -EINVAL;
15781 if (tg->idle == idle) {
15786 tg->idle = idle;
15798 grp_cfs_rq->idle = idle;
15802 idle_task_delta = grp_cfs_rq->h_nr_queued -
15803 grp_cfs_rq->h_nr_idle;
15805 idle_task_delta *= -1;
15810 if (!se->on_rq)
15813 cfs_rq->h_nr_idle += idle_task_delta;
15839 struct sched_entity *se = &task->se;
15846 if (rq->cfs.load.weight)
15847 rr_interval = NS_TO_JIFFIES(se->slice);
15920 ng = rcu_dereference_all(p->numa_group);
15922 if (p->numa_faults) {
15923 tsf = p->numa_faults[task_faults_idx(NUMA_MEM, node, 0)];
15924 tpf = p->numa_faults[task_faults_idx(NUMA_MEM, node, 1)];
15927 gsf = ng->faults[task_faults_idx(NUMA_MEM, node, 0)];
15928 gpf = ng->faults[task_faults_idx(NUMA_MEM, node, 1)];
15947 INIT_CSD(&cpu_rq(i)->cfsb_csd, __cfsb_csd_unthrottle, cpu_rq(i));
15948 INIT_LIST_HEAD(&cpu_rq(i)->cfsb_csd_list);