Cache aware scheduling
Subsystems (5)
Re: [PATCH v2 20/23] sched/cache: Add user control to adjust the parameters of cache-aware scheduling
In reply to Jianyong WuHello Jianyong,
Quoted 28 lines · Jianyong Wu
Hello Tim, Chen Yu,
Quoted 26 lines
static bool
exceed_llc_capacity(struct mm_struct *mm, int cpu){
+ unsigned int llc, scale;
struct cacheinfo *ci;
unsigned long rss;
- unsigned int llc;
/*
*get_cpu_cacheinfo_level()can not be used(quoted diff) +0
-0@@ -1252,19 +1266,54 @@ static bool exceed_llc_capacity(struct mm_struct *mm, int cpu)rss =
get_mm_counter(mm, MM_ANONPAGES)+get_mm_counter(mm, MM_SHMEMPAGES);
- return (llc <= (rss *PAGE_SIZE));
+ /*
+ * Scale the LLC size by 256*llc_aggr_tolerance + * and compare it to the task's RSS size.
+ *
+ * Suppose the L3 size is 32MB. If the
+ *llc_aggr_toleranceis 1:
+ * When the RSS is larger than 32MB, the process + * is regarded as exceeding the LLC capacity. If + * thellc_aggr_toleranceis 99:
+ * When the RSS is larger than 784GB, the process + * is regarded as exceeding the LLC capacity because:
+ * 784GB = (1 + (99 - 1) * 256) * 32MB
Quoted 9 lines
Quoted 7 lines
+ */
+ scale =get_sched_cache_scale(256);
+ if (scale ==INT_MAX)
+ return false;
+
+ return ((llc * scale) <= (rss *PAGE_SIZE));
}Suppose the LLC is 16 MB (which is 16777216 bytes). If we set
llc_aggr_toleranceto 99, thescalevalue will be 25089. When calculating16777216 * 25089, the result is 420923572224, which exceeds 2^32 and thus causes an integer overflow.
[resend might be due to smtp issue]
Good catch! Let me switch it to u64, it should be big enough for llc size(max to about (2^64 -1)/2589 bytes)
thanks,
Chenyu
Re: [PATCH v2 01/23] sched/cache: Introduce infrastructure for cache-aware load balancing
In reply to Vern HaoQuoted 103 lines · Vern Hao
Quoted 97 lines · Yu C
Quoted 91 lines · Vern Hao
Hi, Peter, Chen Yu and Tim:
Quoted 76 lines · Tim Chen
From: "Peter Zijlstra (Intel)" <[email protected]>
Adds infrastructure to enable cache-aware load balancing, which improves cache locality by grouping tasks that share resources within the same cache domain. This reduces cache misses and improves overall data access efficiency.
In this initial implementation, threads belonging to the same process are treated as entities that likely share working sets. The mechanism tracks per-process CPU occupancy across cache domains and attempts to migrate threads toward cache-hot domains where their process already has active threads, thereby enhancing locality.
This provides a basic model for cache affinity. While the current code targets the last-level cache (LLC), the approach could be extended to other domain types such as clusters (L2) or node-internal groupings.
At present, the mechanism selects the CPU within an LLC that has the highest recent runtime. Subsequent patches in this series will use this information in the load-balancing path to guide task placement toward preferred LLCs.
In the future, more advanced policies could be integrated through NUMA balancing-for example, migrating a task to its preferred LLC when spare capacity exists, or swapping tasks across LLCs to improve cache affinity.
Grouping of tasks could also be generalized from that of a process to be that of a NUMA group, or be user configurable.Originally-by Peter Zijlstra (Intel) <[email protected]>Signed-off-by Chen Yu <[email protected]>Signed-off-by Tim Chen <[email protected]>---
Notes:
v1->v2:
Restore the original CPU scan to cover all online CPUs, rather than scanning within the preferred NUMA node. (Peter Zijlstra)
Userq->currinstead ofrq->donor. (K Prateek Nayak) Minor fix intask_tick_cache()to use
if (mm->mm_sched_epoch>=rq->cpu_epoch)
to avoidmm_sched_epochgoing backwards.
include/linux/mm_types.h| 44 +++++++
include/linux/sched.h | 11 ++
init/Kconfig | 11 ++
kernel/fork.c | 6 +
kernel/sched/core.c | 6 +
kernel/sched/fair.c | 258
+++++++++++++++++++++++++++++++++++++++
kernel/sched/sched.h | 8 ++7 files changed, 344 insertions(+)include/linux/mm_types.h +8
-0@@ -939,6 +939,11 @@ typedef struct { DECLARE_BITMAP(__mm_flags, NUM_MM_FLAG_BITS); } __private mm_flags_t; +struct mm_sched { + u64 runtime; + unsigned long epoch; +}; + struct kioctx_table; struct iommu_mm_data; struct mm_struct {@@ -1029,6 +1034,17 @@ struct mm_struct {*/ raw_spinlock_t cpus_allowed_lock; #endif +#ifdef CONFIG_SCHED_CACHE + /* +* Track per-cpu-per-process occupancy as a proxy for cache Quoted 7 lines
residency.
+ * Seeaccount_mm_sched()and ...
+ */
+ structmm_sched__percpu*pcpu_sched;
+raw_spinlock_tmm_sched_lock;
+ unsigned longmm_sched_epoch;
+ intmm_sched_cpu;As we discussed earlier,I continue to believe that dedicating '
mm_sched_cpu' to handle the aggregated hotspots of all threads is inappropriate, as the multiple threads lack a necessary correlation in our real application.Quoted 4 lines
So, I was wondering if we could put this variable into struct
task_struct, That allows us to better monitor the hotspot CPU of each thread, despite some details needing consideration.Quoted 4 lines
I suppose you are suggesting a fine-grained control for a set of tasks. Process-scope aggregation could be a start as the default strategy( conservative, benefit multi-thread workloads that share data per process, not introduce regression).
Quoted 6 lines
Yes, in our real-world business scenarios at Tencent, I have indeed encountered this issue where multiple threads are divided into several categories to handle different transactions, so they are not share the hot data, the 'mm_sched_cpu' does not represent all of their task, so add a control interface such as cgroup or others will be a good idea.
Yes, the grouping and aggregating of tasks by process will not cover your usage scenario. Chen Yu and I had quite a bit of discussions among us and here're our thoughts.
In the initial version of cache aware scheduling, process based aggregation is a sensible default. Once this basic option is merged in mainline we will consider adding other options for task grouping. For example, setting a flag in a cgroup cpu controller to indicate that tasks in a cgroup could benefit from being consolidated in a LLC.
We think that you can put your threads in each category in each of its own cgroup. Will that meet your need?
Things like mm_sched_cpu ... etc will be abstracted out, where the grouping structure in mm is abstracted as cache_group. So we will have something like cache_group_sched_cpu instead of mm_sched_cpu.
Tim
Quoted 17 lines
Quoted 5 lines
On top of that, I wonder if we could provide task-scope control like
sched_setattr(), similar to core-scheduling cookie mechanism, for users that want aggressive aggregation. But before doing that, we need a mechanism that that leverages a monitor system(like PMU) to figure outThere will maybe a trouble, If the environment is running on a VM, We could use tags to differentiate these tasks and do some tests to verify the performance difference between unifying the |mm_sched_cpu| and not unifying.
Quoted 8 lines
if putting these tasks together would bring benefit(if I understand Steven's suggestion correctly on LPC), or detection tasks that share resource, then maybe leverage QOS interfaces to enable the cache-aware aggregation(something Qias mentioned on the LPC).
thanks,
Chenyu
Re: [PATCH v2 20/23] sched/cache: Add user control to adjust the parameters of cache-aware scheduling
In reply to Tim ChenQuoted 212 lines · Tim Chen
From: Chen Yu <[email protected]>
Introduce a set of debugfs knobs to control the enabling of and parameters for cache-aware load balancing.
(1)
llc_enabledllc_enabledacts as the primary switch - users can toggle it to enable or disable cache aware load balancing.(2)
llc_aggr_tolerance
Withsched_cacheenabled, the scheduler uses a process's RSS as a proxy for its LLC footprint to determine if aggregating tasks on the preferred LLC could cause cache contention. If RSS exceeds the LLC size, aggregation is skipped. Some workloads with large RSS but small actual memory footprints may still benefit from aggregation. Since the kernel cannot efficiently track per-task cache usage (resctrl is user-space only), userspace can provide a more accurate hint.Introduce
/sys/kernel/debug/sched/llc_aggr_toleranceto let users control how strictly RSS limits aggregation. Values range from 0 to 100:- 0: Cache-aware scheduling is disabled.
- 1: Strict; tasks with RSS larger than LLC size are skipped.
- 100: Aggressive; tasks are aggregated regardless of RSS.For example, with a 32MB L3 cache:
- llc_aggr_tolerance=1 -> tasks with RSS > 32MB are skipped.
- llc_aggr_tolerance=99 -> tasks with RSS > 784GB are skipped(784GB = (1 + (99 - 1) * 256) * 32MB).Similarly,
/sys/kernel/debug/sched/llc_aggr_tolerancealso controls how strictly the number of active threads is considered when doing cache aware load balance. The number of SMTs is also considered. High SMT counts reduce the aggregation capacity, preventing excessive task aggregation on SMT-heavy systems like Power10/Power11.For example, with 8 Cores/16 CPUs in a L3:
- llc_aggr_tolerance=1 -> tasks with
nr_running> 8 are skipped.
- llc_aggr_tolerance=99 -> tasks withnr_running> 785 are skipped785 = (1 + (99 - 1) * 8).(3) llc_epoch_period/llc_epoch_affinity_timeout
Besides,llc_epoch_periodandllc_epoch_affinity_timeoutare also turned into tunable.Suggested-by K Prateek Nayak <[email protected]>Suggested-by Madadi Vineeth Reddy <[email protected]>Suggested-by Shrikanth Hegde <[email protected]>Suggested-by Tingyin Duan <[email protected]>Co-developed-by Tim Chen <[email protected]>Signed-off-by Tim Chen <[email protected]>Signed-off-by Chen Yu <[email protected]>---
Notes:
v1->v2: Remove the smt_nr check in fits_llc_capacity(). (Aaron Lu)include/linux/sched.h | 4 ++- kernel/sched/debug.c | 62 ++++++++++++++++++++++++++++++++++++++++ kernel/sched/fair.c | 63 ++++++++++++++++++++++++++++++++++++----- kernel/sched/sched.h | 5 ++++ kernel/sched/topology.c | 54 +++++++++++++++++++++++++++++++++-- 5 files changed, 178 insertions(+), 10 deletions(-)include/linux/sched.h +3
-1@@ -2436,9 +2436,11 @@ extern void migrate_enable(void); DEFINE_LOCK_GUARD_0(migrate, migrate_disable(), migrate_enable())#ifdef CONFIG_SCHED_CACHE +DECLARE_STATIC_KEY_FALSE (sched_cache_on); +static inline bool sched_cache_enabled (void ) { -return false; +return static_branch_unlikely (&sched_cache_on); }#endif kernel/sched/debug.c +62
-0@@ -169,6 +169,53 @@ static const struct file_operations sched_feat_fops = { .release = single_release, }; +#ifdef CONFIG_SCHED_CACHE +#define SCHED_CACHE_CREATE_CONTROL (name, max) \ +static ssize_t sched_cache_write_##name(struct file *filp, \ + const char __user *ubuf, \ + size_t cnt, loff_t *ppos) \ +{ \ + char buf[16]; \ + unsigned int val; \ + if (cnt > 15) \ + cnt = 15; \ + if (copy_from_user(&buf, ubuf, cnt)) \ + return -EFAULT; \ + buf[cnt] = '\0'; \ + if (kstrtouint(buf, 10, &val)) \ + return -EINVAL; \ + if (val > (max)) \ + return -EINVAL; \ + llc_##name = val; \ + if (!strcmp(#name, "enabled")) \ + sched_cache_set(false); \ + *ppos += cnt; \ + return cnt; \ +} \ +static int sched_cache_show_##name(struct seq_file *m, void *v) \ +{ \ + seq_printf(m, "%d\n", llc_##name); \ + return 0; \ +} \ +static int sched_cache_open_##name(struct inode *inode, \ + struct file *filp) \ +{ \ + return single_open(filp, sched_cache_show_##name, NULL); \ +} \ +static const struct file_operations sched_cache_fops_##name = { \ + .open = sched_cache_open_##name, \ + .write = sched_cache_write_##name, \ + .read = seq_read, \ + .llseek = seq_lseek, \ + .release = single_release, \ +} + +SCHED_CACHE_CREATE_CONTROL (overload_pct,100 ); +SCHED_CACHE_CREATE_CONTROL (imb_pct,100 ); +SCHED_CACHE_CREATE_CONTROL (aggr_tolerance,100 ); +SCHED_CACHE_CREATE_CONTROL (enabled,1 ); +#endif /* SCHED_CACHE */ +static ssize_t sched_scaling_write (struct file *filp,const char __user *ubuf,size_t cnt,loff_t *ppos) {@@ -523,6 +570,21 @@ static __init int sched_init_debug(void)debugfs_create_u32 ("hot_threshold_ms" ,0644 , numa, &sysctl_numa_balancing_hot_threshold);#endif /* CONFIG_NUMA_BALANCING */ +#ifdef CONFIG_SCHED_CACHE +debugfs_create_file ("llc_overload_pct" ,0644 , debugfs_sched,NULL , + &sched_cache_fops_overload_pct); +debugfs_create_file ("llc_imb_pct" ,0644 , debugfs_sched,NULL , + &sched_cache_fops_imb_pct); +debugfs_create_file ("llc_aggr_tolerance" ,0644 , debugfs_sched,NULL , + &sched_cache_fops_aggr_tolerance); +debugfs_create_file ("llc_enabled" ,0644 , debugfs_sched,NULL , + &sched_cache_fops_enabled); +debugfs_create_u32 ("llc_epoch_period" ,0644 , debugfs_sched, + &llc_epoch_period); +debugfs_create_u32 ("llc_epoch_affinity_timeout" ,0644 , debugfs_sched, + &llc_epoch_affinity_timeout); +#endif +debugfs_create_file ("debug" ,0444 , debugfs_sched,NULL , &sched_debug_fops);debugfs_fair_server_init ();kernel/sched/fair.c +19
-2@@ -1207,6 +1207,9 @@ static s64 update_se(struct rq *rq, struct sched_entity *se)__read_mostly unsigned int llc_overload_pct =50 ;__read_mostly unsigned int llc_imb_pct =20 ; +__read_mostly unsigned int llc_aggr_tolerance =1 ; +__read_mostly unsigned int llc_epoch_period =EPOCH_PERIOD ; +__read_mostly unsigned int llc_epoch_affinity_timeout =EPOCH_LLC_AFFINITY_TIMEOUT ;static int llc_id (int cpu) {@@ -1223,11 +1226,22 @@ static int llc_id(int cpu)return llc; } +static inline int get_sched_cache_scale (int mul) +{ +if (!llc_aggr_tolerance) +return 0 ; + +if (llc_aggr_tolerance ==100 ) +return INT_MAX ; + +return (1 + (llc_aggr_tolerance -1 ) * mul); +} +static bool exceed_llc_capacity (struct mm_struct *mm,int cpu) { +unsigned int llc, scale;struct cacheinfo *ci;unsigned long rss; -unsigned int llc;/* * get_cpu_cacheinfo_level() can not be used @@ -1252,19 +1266,54 @@ static bool exceed_llc_capacity(struct mm_struct *mm, int cpu) rss =get_mm_counter (mm,MM_ANONPAGES ) +get_mm_counter (mm,MM_SHMEMPAGES ); -return (llc <= (rss *PAGE_SIZE )); +/* +* Scale the LLC size by 256*llc_aggr_tolerance +* and compare it to the task's RSS size. +*
kernel/sched/fair.c static bool exceed_llc_capacity(struct mm_struct *mm, int cpu) · line 1282
Quoted 10 lines
kernel/sched/fair.c +10
-0+* Suppose the L3 size is 32MB. If the +* llc_aggr_tolerance is 1: +* When the RSS is larger than 32MB, the process +* is regarded as exceeding the LLC capacity. If +* the llc_aggr_tolerance is 99: +* When the RSS is larger than 784GB, the process +* is regarded as exceeding the LLC capacity because: +* 784GB = (1 + (99 - 1) * 256) * 32MB +*/ + scale =get_sched_cache_scale (256 );
Hi Tim Chen and Chen Yu,
There's an integer overflow here. Since the unit of LLC size is bytes, you have a 256-scale unit. For a typical LLC size of 32M, you calculate 32M multiplied by 256, which equals 8GB. This value exceeds the maximum integer value (2GB, INT_MAX), resulting in an integer overflow.
I think such function should be use u64. Below is my patch:
kernel/sched/fair.c +6 -6
@@ -1226,20 +1226,20 @@ static int llc_id(int cpu)return llc; } -static inline int get_sched_cache_scale (int mul) +static inline u64 get_sched_cache_scale (int mul) {if (!llc_aggr_tolerance)return 0 ;if (llc_aggr_tolerance ==100 ) -return INT_MAX ; +return ULLONG_MAX ;return (1 + (llc_aggr_tolerance -1 ) * mul); }static bool exceed_llc_capacity (struct mm_struct *mm,int cpu) { -unsigned int llc, scale; +unsigned long long llc, scale;struct cacheinfo *ci;unsigned long rss;
@@ -1280,7 +1280,7 @@ static bool exceed_llc_capacity(struct mm_struct *mm, int cpu)* 784GB = (1 + (99 - 1) * 256) * 32MB */ scale =get_sched_cache_scale (256 ); -if (scale ==INT_MAX ) +if (scale ==ULLONG_MAX )return false;return ((llc * scale) <= (rss *PAGE_SIZE ));
@@ -1288,7 +1288,7 @@ static bool exceed_llc_capacity(struct mm_struct *mm, int cpu)static bool exceed_llc_nr (struct mm_struct *mm,int cpu) { -int smt_nr =1 , scale; +unsigned long long smt_nr =1 , scale;#ifdef CONFIG_SCHED_SMT if (sched_smt_active ())
@@ -1310,7 +1310,7 @@ static bool exceed_llc_nr(struct mm_struct *mm, int cpu)* 785 = 1 + (99 - 1) * 8 */ scale =get_sched_cache_scale (1 ); -if (scale ==INT_MAX ) +if (scale ==ULLONG_MAX )return false; return ((mm->nr_running_avg * smt_nr) > (scale * per_cpu(sd_llc_size,
cpu)));
Thanks,
Yangyu Chen
Quoted 162 lines
kernel/sched/fair.c +27
-5+if (scale ==INT_MAX ) +return false; + +return ((llc * scale) <= (rss *PAGE_SIZE )); }static bool exceed_llc_nr (struct mm_struct *mm,int cpu) { -int smt_nr =1 ; +int smt_nr =1 , scale;#ifdef CONFIG_SCHED_SMT if (sched_smt_active ()) smt_nr =cpumask_weight (cpu_smt_mask (cpu));#endif +/* +* Scale the Core number in a LLC by llc_aggr_tolerance +* and compare it to the task's active threads. +* +* Suppose the number of Cores in LLC is 8. +* Every core has 2 SMTs. +* If the llc_aggr_tolerance is 1: When the +* nr_running is larger than 8, the process +* is regarded as exceeding the LLC capacity. +* If the llc_aggr_tolerance is 99: +* When the nr_running is larger than 785, +* the process is regarded as exceeding +* the LLC capacity: +* 785 = 1 + (99 - 1) * 8 +*/ + scale =get_sched_cache_scale (1 ); +if (scale ==INT_MAX ) +return false; -return ((mm->nr_running_avg * smt_nr) >per_cpu (sd_llc_size, cpu)); +return ((mm->nr_running_avg * smt_nr) > (scale *per_cpu (sd_llc_size, cpu))); }static void account_llc_enqueue (struct rq *rq,struct task_struct *p)@@ -1350,9 +1399,9 @@ static inline void __update_mm_sched(struct rq *rq, struct mm_sched *pcpu_sched)long delta = now - rq->cpu_epoch_next;if (delta >0 ) { - n = (delta +EPOCH_PERIOD -1 ) /EPOCH_PERIOD ; + n = (delta + llc_epoch_period -1 ) / llc_epoch_period; rq->cpu_epoch += n; - rq->cpu_epoch_next += n *EPOCH_PERIOD ; + rq->cpu_epoch_next += n * llc_epoch_period;__shr_u64 (&rq->cpu_runtime, n); }@@ -1412,7 +1461,7 @@ void account_mm_sched(struct rq *rq, struct task_struct *p, s64 delta_exec)* has only 1 thread, or has too many active threads, invalidate * its preferred state. */ -if (epoch -READ_ONCE (mm->mm_sched_epoch) >EPOCH_LLC_AFFINITY_TIMEOUT || +if (epoch -READ_ONCE (mm->mm_sched_epoch) > llc_epoch_affinity_timeout ||get_nr_threads (p) <=1 ||exceed_llc_nr (mm,cpu_of (rq)) ||exceed_llc_capacity (mm,cpu_of (rq))) {kernel/sched/sched.h +5
-0@@ -2852,6 +2852,11 @@ extern unsigned int sysctl_numa_balancing_hot_threshold;#ifdef CONFIG_SCHED_CACHE extern unsigned int llc_overload_pct;extern unsigned int llc_imb_pct; +extern unsigned int llc_aggr_tolerance; +extern unsigned int llc_epoch_period; +extern unsigned int llc_epoch_affinity_timeout; +extern unsigned int llc_enabled; +void sched_cache_set (bool locked);#endif #ifdef CONFIG_SCHED_HRTICK kernel/sched/topology.c +52
-2@@ -26,6 +26,49 @@ int max_llcs;static bool sched_cache_present; +unsigned int llc_enabled =1 ; +DEFINE_STATIC_KEY_FALSE (sched_cache_on); + +/* +* Enable/disable cache aware scheduling according to +* user input and the presence of hardware support. +*/ +static void _sched_cache_set (bool enable,bool locked) +{ +if (enable) { +if (locked) +static_branch_enable_cpuslocked (&sched_cache_on); +else +static_branch_enable (&sched_cache_on); + }else { +if (locked) +static_branch_disable_cpuslocked (&sched_cache_on); +else +static_branch_disable (&sched_cache_on); + } +} + +void sched_cache_set (bool locked) +{ +/* hardware does not support */ +if (!sched_cache_present) { +if (static_branch_likely (&sched_cache_on)) +_sched_cache_set (false, locked); + +return ; + } + +/* user wants it or not ?*/ +if (llc_enabled) { +if (!static_branch_likely (&sched_cache_on)) +_sched_cache_set (true, locked); + + }else { +if (static_branch_likely (&sched_cache_on)) +_sched_cache_set (false, locked); + } +} +static unsigned int *alloc_new_pref_llcs (unsigned int *old,unsigned int **gc) {unsigned int *new =NULL ;@@ -70,8 +113,12 @@ static int resize_llc_pref(bool has_multi_llcs)* new buffer. */ tmp_llc_pref = alloc_percpu_noprof(unsigned int *); -if (!tmp_llc_pref) -return -ENOMEM ; +if (!tmp_llc_pref) { + sched_cache_present = false; + ret = -ENOMEM ; + + goto out; + }for_each_present_cpu (i) *per_cpu_ptr (tmp_llc_pref, i) =NULL ;@@ -89,6 +136,7 @@ static int resize_llc_pref(bool has_multi_llcs) new =alloc_new_pref_llcs (rq->nr_pref_llc,per_cpu_ptr (tmp_llc_pref, i));if (!new) { ret = -ENOMEM ; + sched_cache_present = false; goto release_old; }@@ -126,6 +174,8 @@ static int resize_llc_pref(bool has_multi_llcs)if (!ret) max_llcs = new_max_llcs; +out: +sched_cache_set (true);return ret; }
Re: [PATCH v2 20/23] sched/cache: Add user control to adjust the parameters of cache-aware scheduling
Hi Yangyu,
Quoted 3 lines · Yangyu Chen
On 4/12/2025 07:07, Tim Chen wrote:
[ ... ]
Quoted 8 lines
Quoted 1 line
+ scale =
get_sched_cache_scale(256);Hi Tim Chen and Chen Yu,
There's an integer overflow here. Since the unit of LLC size is bytes, you have a 256-scale unit. For a typical LLC size of 32M, you calculate 32M multiplied by 256, which equals 8GB. This value exceeds the maximum integer value (2GB,
INT_MAX), resulting in an integer overflow.I think such function should be use u64. Below is my patch:
Thanks very much for the investigation, Jianyong previously also mentioned this issue
https://lore.kernel.org/all/SI2PR04MB49317BA503E9C8A381956D6AE38CA@SI2PR04MB4931.apcprd04.prod.outlook.com/
we will fix the issue accordingly.
Quoted 15 lines
kernel/sched/fair.c +1
-1@@ -1226,20 +1226,20 @@ static int llc_id(int cpu) return llc; } -static inline int get_sched_cache_scale (int mul) +static inline u64 get_sched_cache_scale (int mul) { if (!llc_aggr_tolerance) return 0; if (llc_aggr_tolerance == 100)
kernel/sched/fair.c static int llc_id(int cpu) · line 1242
Quoted 10 lines
kernel/sched/fair.c +2
-2- return INT_MAX; + return ULLONG_MAX; return (1 + (llc_aggr_tolerance - 1) * mul); } static bool exceed_llc_capacity(struct mm_struct *mm, int cpu) { - unsigned int llc, scale; + unsigned long long llc, scale;
I suppose we only need to change llc to u64, and not change scale, because (llc * scale) would be converted to u64 anyway.
thanks,
Chenyu
Re: [PATCH v2 03/23] sched/cache: Introduce helper functions to enforce LLC migration policy
In reply to Tim ChenQuoted 8 lines · Tim Chen
From: Chen Yu <[email protected]>
Cache-aware scheduling aggregates threads onto their preferred LLC, mainly through load balancing. When the preferred LLC becomes saturated, more threads are still placed there, increasing latency. A mechanism is needed to limit aggregation so that the preferred LLC does not become overloaded.
Quoted 5 lines
Introduce helper functions
can_migrate_llc()andcan_migrate_llc_task()to enforce the LLC migration policy:1. Aggregate a task to its preferred LLC if both source and destination LLCs are not too busy (<50% utilization),
Hi Chen Yu and Tim Chen,
I would like to ask why here chooses 50% for LLC busy. For example, a common AMD Zen 3-5 has 8 cores per LLC. When these servers turned SMT off, an 8-thread process can not be scheduled within 1 LLC. I think here can be 100% by default.
Thanks,
Yangyu Chen
Quoted 226 lines
or if doing so will not leave the preferred LLC much more imbalanced than the non-preferred one (>20% utilization difference, similar to
imbalance_pctof the LLC domain).
2. Allow moving a task from overloaded preferred LLC to a non preferred LLC if this will not cause the non preferred LLC to become too imbalanced to cause a later migration back.
3. If both LLCs are too busy, let the generic load balance to spread the tasks.Further (hysteresis)action could be taken in the future to prevent tasks from being migrated into and out of the preferred LLC frequently (back and forth): the threshold for migrating a task out of its preferred LLC should be higher than that for migrating it into the LLC.
Since aggregation tends to make the preferred LLC busier than others, the imbalance tolerance is controlled by
llc_imb_pct. If set to 0, tasks may still aggregate to the preferred LLC as long as it is not more utilized than the source LLC, preserving the preference.Co-developed-by Tim Chen <[email protected]>Signed-off-by Chen Yu <[email protected]>Signed-off-by Tim Chen <[email protected]>---
Notes:
v1->v2: No change.kernel/sched/fair.c | 153 +++++++++++++++++++++++++++++++++++++++++++ kernel/sched/sched.h | 5 ++ 2 files changed, 158 insertions(+)kernel/sched/fair.c +153
-0@@ -1205,6 +1205,9 @@ static s64 update_se(struct rq *rq, struct sched_entity *se)#define EPOCH_PERIOD (HZ / 100)/* 10 ms */ #define EPOCH_LLC_AFFINITY_TIMEOUT 5/* 50 ms */ +__read_mostly unsigned int llc_overload_pct =50 ; +__read_mostly unsigned int llc_imb_pct =20 ; +static int llc_id (int cpu) {if (cpu <0 )@@ -9623,6 +9626,27 @@ static inline int task_is_ineligible_on_dst_cpu(struct task_struct *p, int dest_ }#ifdef CONFIG_SCHED_CACHE +/* +* The margin used when comparing LLC utilization with CPU capacity. +* Parameter llc_overload_pct determines the LLC load level where +* active LLC aggregation is done. +* Derived from fits_capacity(). +* +* (default: ~50%) +*/ +#define fits_llc_capacity (util, max) \ + ((util) * 100 < (max) * llc_overload_pct) + +/* +* The margin used when comparing utilization. +* is 'util1' noticeably greater than 'util2' +* Derived from capacity_greater(). +* Bias is in perentage. +*/ +/* Allows dst util to be bigger than src util by up to bias percent */ +#define util_greater (util1, util2) \ + ((util1) * 100 > (util2) * (100 + llc_imb_pct)) +/* Called from load balancing paths with rcu_read_lock held */ static __maybe_unused bool get_llc_stats (int cpu,unsigned long *util,unsigned long *cap)@@ -9638,6 +9662,135 @@ static __maybe_unused bool get_llc_stats(int cpu, unsigned long *util, return true; } + +/* +* Decision matrix according to the LLC utilization. To +* decide whether we can do task aggregation across LLC. +* +* By default, 50% is the threshold to treat the LLC as busy, +* and 20% is the utilization imbalance percentage to decide +* if the preferred LLC is busier than the non-preferred LLC. +* The hysteresis is used to avoid task bouncing between the +* preferred LLC and the non-preferred LLC. +* +* 1. moving towards the preferred LLC, dst is the preferred +* LLC, src is not. +* +* src \ dst 30% 40% 50% 60% +* 30% Y Y Y N +* 40% Y Y Y Y +* 50% Y Y G G +* 60% Y Y G G +* +* 2. moving out of the preferred LLC, src is the preferred +* LLC, dst is not: +* +* src \ dst 30% 40% 50% 60% +* 30% N N N N +* 40% N N N N +* 50% N N G G +* 60% Y N G G +* +* src : src_util +* dst : dst_util +* Y : Yes, migrate +* N : No, do not migrate +* G : let the Generic load balance to even the load. +* +* The intention is that if both LLCs are quite busy, cache aware +* load balance should not be performed, and generic load balance +* should take effect. However, if one is busy and the other is not, +* the preferred LLC capacity(50%) and imbalance criteria(20%) should +* be considered to determine whether LLC aggregation should be +* performed to bias the load towards the preferred LLC. +*/ + +/* migration decision, 3 states are orthogonal. */ +enum llc_mig { + mig_forbid =0 ,/* N: Don't migrate task, respect LLC preference */ + mig_llc,/* Y: Do LLC preference based migration */ + mig_unrestricted/* G: Don't restrict generic load balance migration */ +}; + +/* +* Check if task can be moved from the source LLC to the +* destination LLC without breaking cache aware preferrence. +* src_cpu and dst_cpu are arbitrary CPUs within the source +* and destination LLCs, respectively. +*/ +static enum llc_mig can_migrate_llc (int src_cpu,int dst_cpu, +unsigned long tsk_util, +bool to_pref) +{ +unsigned long src_util, dst_util, src_cap, dst_cap; + +if (!get_llc_stats (src_cpu, &src_util, &src_cap) || + !get_llc_stats (dst_cpu, &dst_util, &dst_cap)) +return mig_unrestricted; + +if (!fits_llc_capacity (dst_util, dst_cap) && + !fits_llc_capacity (src_util, src_cap)) +return mig_unrestricted; + + src_util = src_util < tsk_util ?0 : src_util - tsk_util; + dst_util = dst_util + tsk_util; +if (to_pref) { +/* +* llc_imb_pct is the imbalance allowed between +* preferred LLC and non-preferred LLC. +* Don't migrate if we will get preferred LLC too +* heavily loaded and if the dest is much busier +* than the src, in which case migration will +* increase the imbalance too much. +*/ +if (!fits_llc_capacity (dst_util, dst_cap) && +util_greater (dst_util, src_util)) +return mig_forbid; + }else { +/* +* Don't migrate if we will leave preferred LLC +* too idle, or if this migration leads to the +* non-preferred LLC falls within sysctl_aggr_imb percent +* of preferred LLC, leading to migration again +* back to preferred LLC. +*/ +if (fits_llc_capacity (src_util, src_cap) || + !util_greater (src_util, dst_util)) +return mig_forbid; + } +return mig_llc; +} + +/* +* Check if task p can migrate from source LLC to +* destination LLC in terms of cache aware load balance. +*/ +static __maybe_unused enum llc_mig can_migrate_llc_task (int src_cpu,int dst_cpu, +struct task_struct *p) +{ +struct mm_struct *mm; +bool to_pref; +int cpu; + + mm = p->mm; +if (!mm) +return mig_unrestricted; + + cpu = mm->mm_sched_cpu; +if (cpu <0 ||cpus_share_cache (src_cpu, dst_cpu)) +return mig_unrestricted; + +if (cpus_share_cache (dst_cpu, cpu)) + to_pref = true; +else if (cpus_share_cache (src_cpu, cpu)) + to_pref = false; +else +return mig_unrestricted; + +return can_migrate_llc (src_cpu, dst_cpu, +task_util (p), to_pref); +} +#else static inline bool get_llc_stats (int cpu,unsigned long *util,unsigned long *cap)kernel/sched/sched.h +5
-0@@ -2828,6 +2828,11 @@ extern unsigned int sysctl_numa_balancing_scan_period_max;extern unsigned int sysctl_numa_balancing_scan_size;extern unsigned int sysctl_numa_balancing_hot_threshold; +#ifdef CONFIG_SCHED_CACHE +extern unsigned int llc_overload_pct; +extern unsigned int llc_imb_pct; +#endif +#ifdef CONFIG_SCHED_HRTICK /*
Re: [PATCH v2 03/23] sched/cache: Introduce helper functions to enforce LLC migration policy
Quoted 16 lines · Yangyu Chen
Quoted 8 lines · Tim Chen
From: Chen Yu <[email protected]>
Cache-aware scheduling aggregates threads onto their preferred LLC, mainly through load balancing. When the preferred LLC becomes saturated, more threads are still placed there, increasing latency. A mechanism is needed to limit aggregation so that the preferred LLC does not become overloaded.
Quoted 5 lines
Introduce helper functions
can_migrate_llc()andcan_migrate_llc_task()to enforce the LLC migration policy:1. Aggregate a task to its preferred LLC if both source and destination LLCs are not too busy (<50% utilization),
Quoted 6 lines
Hi Chen Yu and Tim Chen,
I would like to ask why here chooses 50% for LLC busy. For example, a common AMD Zen 3-5 has 8 cores per LLC. When these servers turned SMT off, an 8-thread process can not be scheduled within 1 LLC. I think here can be 100% by default.
For 100% you would be likely have over aggregation and contention on the LLC by aggregating everything there. We tested some workload that has hot working set footprint that's a significant fraction of the LLC and found that 100% would cause significant
degradation to performance. 50% is what we found to be a reasonable
default value. This is a tunnable so it could be changed by admin if
desired.
Tim
Quoted 231 lines
Thanks,
Yangyu ChenQuoted 226 lines
or if doing so will not leave the preferred LLC much more imbalanced than the non-preferred one (>20% utilization difference, similar to
imbalance_pctof the LLC domain).
2. Allow moving a task from overloaded preferred LLC to a non preferred LLC if this will not cause the non preferred LLC to become too imbalanced to cause a later migration back.
3. If both LLCs are too busy, let the generic load balance to spread the tasks.Further (hysteresis)action could be taken in the future to prevent tasks from being migrated into and out of the preferred LLC frequently (back and forth): the threshold for migrating a task out of its preferred LLC should be higher than that for migrating it into the LLC.
Since aggregation tends to make the preferred LLC busier than others, the imbalance tolerance is controlled by
llc_imb_pct. If set to 0, tasks may still aggregate to the preferred LLC as long as it is not more utilized than the source LLC, preserving the preference.Co-developed-by Tim Chen <[email protected]>Signed-off-by Chen Yu <[email protected]>Signed-off-by Tim Chen <[email protected]>---
Notes:
v1->v2: No change.kernel/sched/fair.c | 153 +++++++++++++++++++++++++++++++++++++++++++ kernel/sched/sched.h | 5 ++ 2 files changed, 158 insertions(+)kernel/sched/fair.c +153
-0@@ -1205,6 +1205,9 @@ static s64 update_se(struct rq *rq, struct sched_entity *se)#define EPOCH_PERIOD (HZ / 100)/* 10 ms */ #define EPOCH_LLC_AFFINITY_TIMEOUT 5/* 50 ms */ +__read_mostly unsigned int llc_overload_pct =50 ; +__read_mostly unsigned int llc_imb_pct =20 ; +static int llc_id (int cpu) {if (cpu <0 )@@ -9623,6 +9626,27 @@ static inline int task_is_ineligible_on_dst_cpu(struct task_struct *p, int dest_ }#ifdef CONFIG_SCHED_CACHE +/* +* The margin used when comparing LLC utilization with CPU capacity. +* Parameter llc_overload_pct determines the LLC load level where +* active LLC aggregation is done. +* Derived from fits_capacity(). +* +* (default: ~50%) +*/ +#define fits_llc_capacity (util, max) \ + ((util) * 100 < (max) * llc_overload_pct) + +/* +* The margin used when comparing utilization. +* is 'util1' noticeably greater than 'util2' +* Derived from capacity_greater(). +* Bias is in perentage. +*/ +/* Allows dst util to be bigger than src util by up to bias percent */ +#define util_greater (util1, util2) \ + ((util1) * 100 > (util2) * (100 + llc_imb_pct)) +/* Called from load balancing paths with rcu_read_lock held */ static __maybe_unused bool get_llc_stats (int cpu,unsigned long *util,unsigned long *cap)@@ -9638,6 +9662,135 @@ static __maybe_unused bool get_llc_stats(int cpu, unsigned long *util, return true; } + +/* +* Decision matrix according to the LLC utilization. To +* decide whether we can do task aggregation across LLC. +* +* By default, 50% is the threshold to treat the LLC as busy, +* and 20% is the utilization imbalance percentage to decide +* if the preferred LLC is busier than the non-preferred LLC. +* The hysteresis is used to avoid task bouncing between the +* preferred LLC and the non-preferred LLC. +* +* 1. moving towards the preferred LLC, dst is the preferred +* LLC, src is not. +* +* src \ dst 30% 40% 50% 60% +* 30% Y Y Y N +* 40% Y Y Y Y +* 50% Y Y G G +* 60% Y Y G G +* +* 2. moving out of the preferred LLC, src is the preferred +* LLC, dst is not: +* +* src \ dst 30% 40% 50% 60% +* 30% N N N N +* 40% N N N N +* 50% N N G G +* 60% Y N G G +* +* src : src_util +* dst : dst_util +* Y : Yes, migrate +* N : No, do not migrate +* G : let the Generic load balance to even the load. +* +* The intention is that if both LLCs are quite busy, cache aware +* load balance should not be performed, and generic load balance +* should take effect. However, if one is busy and the other is not, +* the preferred LLC capacity(50%) and imbalance criteria(20%) should +* be considered to determine whether LLC aggregation should be +* performed to bias the load towards the preferred LLC. +*/ + +/* migration decision, 3 states are orthogonal. */ +enum llc_mig { + mig_forbid =0 ,/* N: Don't migrate task, respect LLC preference */ + mig_llc,/* Y: Do LLC preference based migration */ + mig_unrestricted/* G: Don't restrict generic load balance migration */ +}; + +/* +* Check if task can be moved from the source LLC to the +* destination LLC without breaking cache aware preferrence. +* src_cpu and dst_cpu are arbitrary CPUs within the source +* and destination LLCs, respectively. +*/ +static enum llc_mig can_migrate_llc (int src_cpu,int dst_cpu, +unsigned long tsk_util, +bool to_pref) +{ +unsigned long src_util, dst_util, src_cap, dst_cap; + +if (!get_llc_stats (src_cpu, &src_util, &src_cap) || + !get_llc_stats (dst_cpu, &dst_util, &dst_cap)) +return mig_unrestricted; + +if (!fits_llc_capacity (dst_util, dst_cap) && + !fits_llc_capacity (src_util, src_cap)) +return mig_unrestricted; + + src_util = src_util < tsk_util ?0 : src_util - tsk_util; + dst_util = dst_util + tsk_util; +if (to_pref) { +/* +* llc_imb_pct is the imbalance allowed between +* preferred LLC and non-preferred LLC. +* Don't migrate if we will get preferred LLC too +* heavily loaded and if the dest is much busier +* than the src, in which case migration will +* increase the imbalance too much. +*/ +if (!fits_llc_capacity (dst_util, dst_cap) && +util_greater (dst_util, src_util)) +return mig_forbid; + }else { +/* +* Don't migrate if we will leave preferred LLC +* too idle, or if this migration leads to the +* non-preferred LLC falls within sysctl_aggr_imb percent +* of preferred LLC, leading to migration again +* back to preferred LLC. +*/ +if (fits_llc_capacity (src_util, src_cap) || + !util_greater (src_util, dst_util)) +return mig_forbid; + } +return mig_llc; +} + +/* +* Check if task p can migrate from source LLC to +* destination LLC in terms of cache aware load balance. +*/ +static __maybe_unused enum llc_mig can_migrate_llc_task (int src_cpu,int dst_cpu, +struct task_struct *p) +{ +struct mm_struct *mm; +bool to_pref; +int cpu; + + mm = p->mm; +if (!mm) +return mig_unrestricted; + + cpu = mm->mm_sched_cpu; +if (cpu <0 ||cpus_share_cache (src_cpu, dst_cpu)) +return mig_unrestricted; + +if (cpus_share_cache (dst_cpu, cpu)) + to_pref = true; +else if (cpus_share_cache (src_cpu, cpu)) + to_pref = false; +else +return mig_unrestricted; + +return can_migrate_llc (src_cpu, dst_cpu, +task_util (p), to_pref); +} +#else static inline bool get_llc_stats (int cpu,unsigned long *util,unsigned long *cap)kernel/sched/sched.h +5
-0@@ -2828,6 +2828,11 @@ extern unsigned int sysctl_numa_balancing_scan_period_max;extern unsigned int sysctl_numa_balancing_scan_size;extern unsigned int sysctl_numa_balancing_hot_threshold; +#ifdef CONFIG_SCHED_CACHE +extern unsigned int llc_overload_pct; +extern unsigned int llc_imb_pct; +#endif +#ifdef CONFIG_SCHED_HRTICK /*