diff options
48 files changed, 1521 insertions, 332 deletions
diff --git a/Documentation/admin-guide/sysctl/kernel.rst b/Documentation/admin-guide/sysctl/kernel.rst index 83acf5025488..55bf6b4de4ec 100644 --- a/Documentation/admin-guide/sysctl/kernel.rst +++ b/Documentation/admin-guide/sysctl/kernel.rst @@ -1062,6 +1062,60 @@ Enables/disables scheduler statistics. Enabling this feature incurs a small amount of overhead in the scheduler but is useful for debugging and performance tuning. +sched_util_clamp_min: +===================== + +Max allowed *minimum* utilization. + +Default value is 1024, which is the maximum possible value. + +It means that any requested uclamp.min value cannot be greater than +sched_util_clamp_min, i.e., it is restricted to the range +[0:sched_util_clamp_min]. + +sched_util_clamp_max: +===================== + +Max allowed *maximum* utilization. + +Default value is 1024, which is the maximum possible value. + +It means that any requested uclamp.max value cannot be greater than +sched_util_clamp_max, i.e., it is restricted to the range +[0:sched_util_clamp_max]. + +sched_util_clamp_min_rt_default: +================================ + +By default Linux is tuned for performance. Which means that RT tasks always run +at the highest frequency and most capable (highest capacity) CPU (in +heterogeneous systems). + +Uclamp achieves this by setting the requested uclamp.min of all RT tasks to +1024 by default, which effectively boosts the tasks to run at the highest +frequency and biases them to run on the biggest CPU. + +This knob allows admins to change the default behavior when uclamp is being +used. In battery powered devices particularly, running at the maximum +capacity and frequency will increase energy consumption and shorten the battery +life. + +This knob is only effective for RT tasks which the user hasn't modified their +requested uclamp.min value via sched_setattr() syscall. + +This knob will not escape the range constraint imposed by sched_util_clamp_min +defined above. + +For example if + + sched_util_clamp_min_rt_default = 800 + sched_util_clamp_min = 600 + +Then the boost will be clamped to 600 because 800 is outside of the permissible +range of [0:600]. This could happen for instance if a powersave mode will +restrict all boosts temporarily by modifying sched_util_clamp_min. As soon as +this restriction is lifted, the requested sched_util_clamp_min_rt_default +will take effect. seccomp ======= diff --git a/Documentation/scheduler/index.rst b/Documentation/scheduler/index.rst index 69074e5de9c4..88900aabdbf7 100644 --- a/Documentation/scheduler/index.rst +++ b/Documentation/scheduler/index.rst @@ -12,6 +12,7 @@ Linux Scheduler sched-deadline sched-design-CFS sched-domains + sched-capacity sched-energy sched-nice-design sched-rt-group diff --git a/Documentation/scheduler/sched-capacity.rst b/Documentation/scheduler/sched-capacity.rst new file mode 100644 index 000000000000..00bf0d011e2a --- /dev/null +++ b/Documentation/scheduler/sched-capacity.rst @@ -0,0 +1,439 @@ +========================= +Capacity Aware Scheduling +========================= + +1. CPU Capacity +=============== + +1.1 Introduction +---------------- + +Conventional, homogeneous SMP platforms are composed of purely identical +CPUs. Heterogeneous platforms on the other hand are composed of CPUs with +different performance characteristics - on such platforms, not all CPUs can be +considered equal. + +CPU capacity is a measure of the performance a CPU can reach, normalized against +the most performant CPU in the system. Heterogeneous systems are also called +asymmetric CPU capacity systems, as they contain CPUs of different capacities. + +Disparity in maximum attainable performance (IOW in maximum CPU capacity) stems +from two factors: + +- not all CPUs may have the same microarchitecture (µarch). +- with Dynamic Voltage and Frequency Scaling (DVFS), not all CPUs may be + physically able to attain the higher Operating Performance Points (OPP). + +Arm big.LITTLE systems are an example of both. The big CPUs are more +performance-oriented than the LITTLE ones (more pipeline stages, bigger caches, +smarter predictors, etc), and can usually reach higher OPPs than the LITTLE ones +can. + +CPU performance is usually expressed in Millions of Instructions Per Second +(MIPS), which can also be expressed as a given amount of instructions attainable +per Hz, leading to:: + + capacity(cpu) = work_per_hz(cpu) * max_freq(cpu) + +1.2 Scheduler terms +------------------- + +Two different capacity values are used within the scheduler. A CPU's +``capacity_orig`` is its maximum attainable capacity, i.e. its maximum +attainable performance level. A CPU's ``capacity`` is its ``capacity_orig`` to +which some loss of available performance (e.g. time spent handling IRQs) is +subtracted. + +Note that a CPU's ``capacity`` is solely intended to be used by the CFS class, +while ``capacity_orig`` is class-agnostic. The rest of this document will use +the term ``capacity`` interchangeably with ``capacity_orig`` for the sake of +brevity. + +1.3 Platform examples +--------------------- + +1.3.1 Identical OPPs +~~~~~~~~~~~~~~~~~~~~ + +Consider an hypothetical dual-core asymmetric CPU capacity system where + +- work_per_hz(CPU0) = W +- work_per_hz(CPU1) = W/2 +- all CPUs are running at the same fixed frequency + +By the above definition of capacity: + +- capacity(CPU0) = C +- capacity(CPU1) = C/2 + +To draw the parallel with Arm big.LITTLE, CPU0 would be a big while CPU1 would +be a LITTLE. + +With a workload that periodically does a fixed amount of work, you will get an +execution trace like so:: + + CPU0 work ^ + | ____ ____ ____ + | | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + + CPU1 work ^ + | _________ _________ ____ + | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + +CPU0 has the highest capacity in the system (C), and completes a fixed amount of +work W in T units of time. On the other hand, CPU1 has half the capacity of +CPU0, and thus only completes W/2 in T. + +1.3.2 Different max OPPs +~~~~~~~~~~~~~~~~~~~~~~~~ + +Usually, CPUs of different capacity values also have different maximum +OPPs. Consider the same CPUs as above (i.e. same work_per_hz()) with: + +- max_freq(CPU0) = F +- max_freq(CPU1) = 2/3 * F + +This yields: + +- capacity(CPU0) = C +- capacity(CPU1) = C/3 + +Executing the same workload as described in 1.3.1, which each CPU running at its +maximum frequency results in:: + + CPU0 work ^ + | ____ ____ ____ + | | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + + workload on CPU1 + CPU1 work ^ + | ______________ ______________ ____ + | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + +1.4 Representation caveat +------------------------- + +It should be noted that having a *single* value to represent differences in CPU +performance is somewhat of a contentious point. The relative performance +difference between two different µarchs could be X% on integer operations, Y% on +floating point operations, Z% on branches, and so on. Still, results using this +simple approach have been satisfactory for now. + +2. Task utilization +=================== + +2.1 Introduction +---------------- + +Capacity aware scheduling requires an expression of a task's requirements with +regards to CPU capacity. Each scheduler class can express this differently, and +while task utilization is specific to CFS, it is convenient to describe it here +in order to introduce more generic concepts. + +Task utilization is a percentage meant to represent the throughput requirements +of a task. A simple approximation of it is the task's duty cycle, i.e.:: + + task_util(p) = duty_cycle(p) + +On an SMP system with fixed frequencies, 100% utilization suggests the task is a +busy loop. Conversely, 10% utilization hints it is a small periodic task that +spends more time sleeping than executing. Variable CPU frequencies and +asymmetric CPU capacities complexify this somewhat; the following sections will +expand on these. + +2.2 Frequency invariance +------------------------ + +One issue that needs to be taken into account is that a workload's duty cycle is +directly impacted by the current OPP the CPU is running at. Consider running a +periodic workload at a given frequency F:: + + CPU work ^ + | ____ ____ ____ + | | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + +This yields duty_cycle(p) == 25%. + +Now, consider running the *same* workload at frequency F/2:: + + CPU work ^ + | _________ _________ ____ + | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + +This yields duty_cycle(p) == 50%, despite the task having the exact same +behaviour (i.e. executing the same amount of work) in both executions. + +The task utilization signal can be made frequency invariant using the following +formula:: + + task_util_freq_inv(p) = duty_cycle(p) * (curr_frequency(cpu) / max_frequency(cpu)) + +Applying this formula to the two examples above yields a frequency invariant +task utilization of 25%. + +2.3 CPU invariance +------------------ + +CPU capacity has a similar effect on task utilization in that running an +identical workload on CPUs of different capacity values will yield different +duty cycles. + +Consider the system described in 1.3.2., i.e.:: + +- capacity(CPU0) = C +- capacity(CPU1) = C/3 + +Executing a given periodic workload on each CPU at their maximum frequency would +result in:: + + CPU0 work ^ + | ____ ____ ____ + | | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + + CPU1 work ^ + | ______________ ______________ ____ + | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + +IOW, + +- duty_cycle(p) == 25% if p runs on CPU0 at its maximum frequency +- duty_cycle(p) == 75% if p runs on CPU1 at its maximum frequency + +The task utilization signal can be made CPU invariant using the following +formula:: + + task_util_cpu_inv(p) = duty_cycle(p) * (capacity(cpu) / max_capacity) + +with ``max_capacity`` being the highest CPU capacity value in the +system. Applying this formula to the above example above yields a CPU +invariant task utilization of 25%. + +2.4 Invariant task utilization +------------------------------ + +Both frequency and CPU invariance need to be applied to task utilization in +order to obtain a truly invariant signal. The pseudo-formula for a task +utilization that is both CPU and frequency invariant is thus, for a given +task p:: + + curr_frequency(cpu) capacity(cpu) + task_util_inv(p) = duty_cycle(p) * ------------------- * ------------- + max_frequency(cpu) max_capacity + +In other words, invariant task utilization describes the behaviour of a task as +if it were running on the highest-capacity CPU in the system, running at its +maximum frequency. + +Any mention of task utilization in the following sections will imply its +invariant form. + +2.5 Utilization estimation +-------------------------- + +Without a crystal ball, task behaviour (and thus task utilization) cannot +accurately be predicted the moment a task first becomes runnable. The CFS class +maintains a handful of CPU and task signals based on the Per-Entity Load +Tracking (PELT) mechanism, one of those yielding an *average* utilization (as +opposed to instantaneous). + +This means that while the capacity aware scheduling criteria will be written +considering a "true" task utilization (using a crystal ball), the implementation +will only ever be able to use an estimator thereof. + +3. Capacity aware scheduling requirements +========================================= + +3.1 CPU capacity +---------------- + +Linux cannot currently figure out CPU capacity on its own, this information thus +needs to be handed to it. Architectures must define arch_scale_cpu_capacity() +for that purpose. + +The arm and arm64 architectures directly map this to the arch_topology driver +CPU scaling data, which is derived from the capacity-dmips-mhz CPU binding; see +Documentation/devicetree/bindings/arm/cpu-capacity.txt. + +3.2 Frequency invariance +------------------------ + +As stated in 2.2, capacity-aware scheduling requires a frequency-invariant task +utilization. Architectures must define arch_scale_freq_capacity(cpu) for that +purpose. + +Implementing this function requires figuring out at which frequency each CPU +have been running at. One way to implement this is to leverage hardware counters +whose increment rate scale with a CPU's current frequency (APERF/MPERF on x86, +AMU on arm64). Another is to directly hook into cpufreq frequency transitions, +when the kernel is aware of the switched-to frequency (also employed by +arm/arm64). + +4. Scheduler topology +===================== + +During the construction of the sched domains, the scheduler will figure out +whether the system exhibits asymmetric CPU capacities. Should that be the +case: + +- The sched_asym_cpucapacity static key will be enabled. +- The SD_ASYM_CPUCAPACITY flag will be set at the lowest sched_domain level that + spans all unique CPU capacity values. + +The sched_asym_cpucapacity static key is intended to guard sections of code that +cater to asymmetric CPU capacity systems. Do note however that said key is +*system-wide*. Imagine the following setup using cpusets:: + + capacity C/2 C + ________ ________ + / \ / \ + CPUs 0 1 2 3 4 5 6 7 + \__/ \______________/ + cpusets cs0 cs1 + +Which could be created via: + +.. code-block:: sh + + mkdir /sys/fs/cgroup/cpuset/cs0 + echo 0-1 > /sys/fs/cgroup/cpuset/cs0/cpuset.cpus + echo 0 > /sys/fs/cgroup/cpuset/cs0/cpuset.mems + + mkdir /sys/fs/cgroup/cpuset/cs1 + echo 2-7 > /sys/fs/cgroup/cpuset/cs1/cpuset.cpus + echo 0 > /sys/fs/cgroup/cpuset/cs1/cpuset.mems + + echo 0 > /sys/fs/cgroup/cpuset/cpuset.sched_load_balance + +Since there *is* CPU capacity asymmetry in the system, the +sched_asym_cpucapacity static key will be enabled. However, the sched_domain +hierarchy of CPUs 0-1 spans a single capacity value: SD_ASYM_CPUCAPACITY isn't +set in that hierarchy, it describes an SMP island and should be treated as such. + +Therefore, the 'canonical' pattern for protecting codepaths that cater to +asymmetric CPU capacities is to: + +- Check the sched_asym_cpucapacity static key +- If it is enabled, then also check for the presence of SD_ASYM_CPUCAPACITY in + the sched_domain hierarchy (if relevant, i.e. the codepath targets a specific + CPU or group thereof) + +5. Capacity aware scheduling implementation +=========================================== + +5.1 CFS +------- + +5.1.1 Capacity fitness +~~~~~~~~~~~~~~~~~~~~~~ + +The main capacity scheduling criterion of CFS is:: + + task_util(p) < capacity(task_cpu(p)) + +This is commonly called the capacity fitness criterion, i.e. CFS must ensure a +task "fits" on its CPU. If it is violated, the task will need to achieve more +work than what its CPU can provide: it will be CPU-bound. + +Furthermore, uclamp lets userspace specify a minimum and a maximum utilization +value for a task, either via sched_setattr() or via the cgroup interface (see +Documentation/admin-guide/cgroup-v2.rst). As its name imply, this can be used to +clamp task_util() in the previous criterion. + +5.1.2 Wakeup CPU selection +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +CFS task wakeup CPU selection follows the capacity fitness criterion described +above. On top of that, uclamp is used to clamp the task utilization values, +which lets userspace have more leverage over the CPU selection of CFS +tasks. IOW, CFS wakeup CPU selection searches for a CPU that satisfies:: + + clamp(task_util(p), task_uclamp_min(p), task_uclamp_max(p)) < capacity(cpu) + +By using uclamp, userspace can e.g. allow a busy loop (100% utilization) to run +on any CPU by giving it a low uclamp.max value. Conversely, it can force a small +periodic task (e.g. 10% utilization) to run on the highest-performance CPUs by +giving it a high uclamp.min value. + +.. note:: + + Wakeup CPU selection in CFS can be eclipsed by Energy Aware Scheduling + (EAS), which is described in Documentation/scheduling/sched-energy.rst. + +5.1.3 Load balancing +~~~~~~~~~~~~~~~~~~~~ + +A pathological case in the wakeup CPU selection occurs when a task rarely +sleeps, if at all - it thus rarely wakes up, if at all. Consider:: + + w == wakeup event + + capacity(CPU0) = C + capacity(CPU1) = C / 3 + + workload on CPU0 + CPU work ^ + | _________ _________ ____ + | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + w w w + + workload on CPU1 + CPU work ^ + | ____________________________________________ + | | + +----+----+----+----+----+----+----+----+----+----+-> + w + +This workload should run on CPU0, but if the task either: + +- was improperly scheduled from the start (inaccurate initial + utilization estimation) +- was properly scheduled from the start, but suddenly needs more + processing power + +then it might become CPU-bound, IOW ``task_util(p) > capacity(task_cpu(p))``; +the CPU capacity scheduling criterion is violated, and there may not be any more +wakeup event to fix this up via wakeup CPU selection. + +Tasks that are in this situation are dubbed "misfit" tasks, and the mechanism +put in place to handle this shares the same name. Misfit task migration +leverages the CFS load balancer, more specifically the active load balance part +(which caters to migrating currently running tasks). When load balance happens, +a misfit active load balance will be triggered if a misfit task can be migrated +to a CPU with more capacity than its current one. + +5.2 RT +------ + +5.2.1 Wakeup CPU selection +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +RT task wakeup CPU selection searches for a CPU that satisfies:: + + task_uclamp_min(p) <= capacity(task_cpu(cpu)) + +while still following the usual priority constraints. If none of the candidate +CPUs can satisfy this capacity criterion, then strict priority based scheduling +is followed and CPU capacities are ignored. + +5.3 DL +------ + +5.3.1 Wakeup CPU selection +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +DL task wakeup CPU selection searches for a CPU that satisfies:: + + task_bandwidth(p) < capacity(task_cpu(p)) + +while still respecting the usual bandwidth and deadline constraints. If +none of the candidate CPUs can satisfy this capacity criterion, then the +task will remain on its current CPU. diff --git a/Documentation/scheduler/sched-energy.rst b/Documentation/scheduler/sched-energy.rst index 9580c57a52bc..78f850778982 100644 --- a/Documentation/scheduler/sched-energy.rst +++ b/Documentation/scheduler/sched-energy.rst @@ -331,16 +331,8 @@ asymmetric CPU topologies for now. This requirement is checked at run-time by looking for the presence of the SD_ASYM_CPUCAPACITY flag when the scheduling domains are built. -The flag is set/cleared automatically by the scheduler topology code whenever -there are CPUs with different capacities in a root domain. The capacities of -CPUs are provided by arch-specific code through the arch_scale_cpu_capacity() -callback. As an example, arm and arm64 share an implementation of this callback -which uses a combination of CPUFreq data and device-tree bindings to compute the -capacity of CPUs (see drivers/base/arch_topology.c for more details). - -So, in order to use EAS on your platform your architecture must implement the -arch_scale_cpu_capacity() callback, and some of the CPUs must have a lower -capacity than others. +See Documentation/sched/sched-capacity.rst for requirements to be met for this +flag to be set in the sched_domain hierarchy. Please note that EAS is not fundamentally incompatible with SMP, but no significant savings on SMP platforms have been observed yet. This restriction diff --git a/arch/arm/include/asm/topology.h b/arch/arm/include/asm/topology.h index 435aba289fc5..e0593cf095d0 100644 --- a/arch/arm/include/asm/topology.h +++ b/arch/arm/include/asm/topology.h @@ -16,8 +16,9 @@ /* Enable topology flag updates */ #define arch_update_cpu_topology topology_update_cpu_topology -/* Replace task scheduler's default thermal pressure retrieve API */ +/* Replace task scheduler's default thermal pressure API */ #define arch_scale_thermal_pressure topology_get_thermal_pressure +#define arch_set_thermal_pressure topology_set_thermal_pressure #else diff --git a/arch/arm64/include/asm/topology.h b/arch/arm64/include/asm/topology.h index 0cc835ddfcd1..e042f6527981 100644 --- a/arch/arm64/include/asm/topology.h +++ b/arch/arm64/include/asm/topology.h @@ -34,8 +34,9 @@ void topology_scale_freq_tick(void); /* Enable topology flag updates */ #define arch_update_cpu_topology topology_update_cpu_topology -/* Replace task scheduler's default thermal pressure retrieve API */ +/* Replace task scheduler's default thermal pressure API */ #define arch_scale_thermal_pressure topology_get_thermal_pressure +#define arch_set_thermal_pressure topology_set_thermal_pressure #include <asm-generic/topology.h> diff --git a/arch/x86/include/asm/div64.h b/arch/x86/include/asm/div64.h index 9b8cb50768c2..b8f1dc0761e4 100644 --- a/arch/x86/include/asm/div64.h +++ b/arch/x86/include/asm/div64.h @@ -74,16 +74,26 @@ static inline u64 mul_u32_u32(u32 a, u32 b) #else # include <asm-generic/div64.h> -static inline u64 mul_u64_u32_div(u64 a, u32 mul, u32 div) +/* + * Will generate an #DE when the result doesn't fit u64, could fix with an + * __ex_table[] entry when it becomes an issue. + */ +static inline u64 mul_u64_u64_div_u64(u64 a, u64 mul, u64 div) { u64 q; asm ("mulq %2; divq %3" : "=a" (q) - : "a" (a), "rm" ((u64)mul), "rm" ((u64)div) + : "a" (a), "rm" (mul), "rm" (div) : "rdx"); return q; } +#define mul_u64_u64_div_u64 mul_u64_u64_div_u64 + +static inline u64 mul_u64_u32_div(u64 a, u32 mul, u32 div) +{ + return mul_u64_u64_div_u64(a, mul, div); +} #define mul_u64_u32_div mul_u64_u32_div #endif /* CONFIG_X86_32 */ diff --git a/arch/x86/include/asm/topology.h b/arch/x86/include/asm/topology.h index 79d8d5496330..f4234575f3fd 100644 --- a/arch/x86/include/asm/topology.h +++ b/arch/x86/include/asm/topology.h @@ -193,7 +193,7 @@ static inline void sched_clear_itmt_support(void) } #endif /* CONFIG_SCHED_MC_PRIO */ -#ifdef CONFIG_SMP +#if defined(CONFIG_SMP) && defined(CONFIG_X86_64) #include <asm/cpufeature.h> DECLARE_STATIC_KEY_FALSE(arch_scale_freq_key); diff --git a/arch/x86/kernel/smpboot.c b/arch/x86/kernel/smpboot.c index ffbd9a3d78d8..518ac6bf752e 100644 --- a/arch/x86/kernel/smpboot.c +++ b/arch/x86/kernel/smpboot.c @@ -56,6 +56,7 @@ #include <linux/cpuidle.h> #include <linux/numa.h> #include <linux/pgtable.h> +#include <linux/overflow.h> #include <asm/acpi.h> #include <asm/desc.h> @@ -1777,6 +1778,7 @@ void native_play_dead(void) #endif +#ifdef CONFIG_X86_64 /* * APERF/MPERF frequency ratio computation. * @@ -1975,6 +1977,7 @@ static bool core_set_max_freq_ratio(u64 *base_freq, u64 *turbo_freq) static bool intel_set_max_freq_ratio(void) { u64 base_freq, turbo_freq; + u64 turbo_ratio; if (slv_set_max_freq_ratio(&base_freq, &turbo_freq)) goto out; @@ -2000,15 +2003,23 @@ out: /* * Some hypervisors advertise X86_FEATURE_APERFMPERF * but then fill all MSR's with zeroes. + * Some CPUs have turbo boost but don't declare any turbo ratio + * in MSR_TURBO_RATIO_LIMIT. */ - if (!base_freq) { - pr_debug("Couldn't determine cpu base frequency, necessary for scale-invariant accounting.\n"); + if (!base_freq || !turbo_freq) { + pr_debug("Couldn't determine cpu base or turbo frequency, necessary for scale-invariant accounting.\n"); return false; } - arch_turbo_freq_ratio = div_u64(turbo_freq * SCHED_CAPACITY_SCALE, - base_freq); + turbo_ratio = div_u64(turbo_freq * SCHED_CAPACITY_SCALE, base_freq); + if (!turbo_ratio) { + pr_debug("Non-zero turbo and base frequencies led to a 0 ratio.\n"); + return false; + } + + arch_turbo_freq_ratio = turbo_ratio; arch_set_max_freq_ratio(turbo_disabled()); + return true; } @@ -2048,11 +2059,19 @@ static void init_freq_invariance(bool secondary) } } +static void d |