[PATCH V1 0/4] sched: Predict load based on conditional probability

[PATCH V1 0/4] sched: Predict load based on conditional probability

[zihan zhou]

The work of this patch is to predict the load after a period of time in
the future based on the conditional probability, so as to optimize the
load balancing, wake-up preemption, cpu frequency adjustment or other
tasks. PATCH 4/4 is a simple example of optimizing wake-up preemption,
which can improve the performance of the hackbench a little.

I am optimistic about the potential of this patch, but my ability and my
time are limited. I sincerely hope that more kind people can join in and
help me...

In the kernel, pelt works very well, but I think it is not perfect. For
example, there is a task 1 that sleeps for 10s, and then runs for 10s. In
this scenario, it is likely to make the wrong choice in load balancing.

Suppose we currently have two cpus (or said rqs). The load of cpu 0 is 0,
and the load of cpu 1 is 512 with a task 2:

cpu 0 (0)       cpu 1 (512)
                task 2 (512)

After task 1 wakes up, it will select cpu 0 because of the lower load,
while task 1 has a load of 0 due to long sleep, so the next time, the load
of cpus will still be like this:

cpu 0 (0)       cpu 1 (512)
task 1 (0)      task 2 (512)

At this time, there is a task 3 that wants select a cpu. Since the load of
cpu 0 is lower than cpu 1, it will choose cpu 0 to compete with a high
load task 1:

cpu 0 (128)       cpu 1 (512)
task 1 (0)      task 2 (512)
task 3 (128)

After a while, the load of two cpus is unbalanced, and the task can only be
migrated again:

cpu 0 (1152)       cpu 1 (512)
task 1 (1024)      task 2 (512)
task 3 (128)

This scenario is a fantasy of mine, there may be some wrong guesses. I
just want to illustrate my point through this example: if we can accurately
predict the future load of the task, then we can optimize many things on
the scheduler.

My idea is to predict the load when dequeue based on the load when enqueue.
This algorithm is based on conditional probability:
p(A|B) = p(AB) / p(B)

To do it, we need to count the load of tasks when they enter or leave the
rq, if we need detailed statistics, we need to use a two-dimensional array
to record:

  record_load_array[load_when_enqueue][load_when_dequeue] = count;

When enqueue, the most likely load2 when dequeue can be predicted through
the load1, where

  record_load_array[load1][load2] == max(record_load_array[load1])

Regardless of special circumstances, the maximum load is 1024, which
requires 1024*1024*8b = 1MB,

Considering that every se will maintain such a two-dimensional array, the
cost is unacceptable, and given the complexity of the actual scene, the
probability of accurately predicting the load with this array is probably
small.

So I made two optimizations:
The first optimization is to normalize the load to 0~1024 (the maximum
value of se->avg.load_avg is related to its weight), and then offset it to
the right LOAD_GRAN_SHIFT (4), so that it represents a range of 16.

For example, if the load is 893, then 893 >> 4 = 55, 55 << 4 = 880, so it
means the load from 880 to 896 (880 + (1<<4)).
For a normal process, se_weight=1024, the load change per 1ms is about
1024*1000 / 47742 = 21 < 16. Theoretically, the statistical error will not
exceed 1ms.

The second optimization is use Boyer–Moore majority vote algorithm, to
record the maximum possible dequeue load. For details, refer to the
implementation of record_predict_load_data().

Through these two optimizations, each record_load_array only needs 128B of
memory. With some other data structures included, a total of 176B of memory
is needed. My machine uses about 3MB memory:

[root@test tip]# cat /proc/slabinfo | grep predict_load_data
predict_load_data  14652  18584    176   ...

According to the experiment, the accuracy of load prediction is about
50%~70%, which is not so good, but we can already try to do something with
it!

zihan zhou (4):
  kconfig: Add kconfig of predict load.
  sched: do predict load.
  sched/debug: add debug for predict load.
  sched/fair: add sched feature PREDICT_NO_PREEMPT.

---
 fs/proc/base.c              |  39 ++++++
 include/linux/sched.h       |  46 +++++++
 include/linux/sched/debug.h |   5 +
 include/linux/sched/task.h  |   2 +-
 init/Kconfig                |  10 ++
 init/init_task.c            |   3 +
 kernel/fork.c               |   6 +-
 kernel/sched/core.c         |  15 ++-
 kernel/sched/debug.c        |  39 ++++++
 kernel/sched/fair.c         | 240 +++++++++++++++++++++++++++++++++++-
 kernel/sched/features.h     |   4 +
 kernel/sched/sched.h        |   2 +
 lib/Kconfig.debug           |  12 ++
 13 files changed, 414 insertions(+), 9 deletions(-)

-- 
2.33.0

[PATCH V1 1/4] sched: Add kconfig of predict load.

[zihan zhou]

Using predict load will make the scheduler logic more complex and take
up more resources. When we are not sure whether to use it, we should be
able to close it.

Signed-off-by: zihan zhou <15645113830zzh@gmail.com>
---
 init/Kconfig      | 10 ++++++++++
 lib/Kconfig.debug | 12 ++++++++++++
 2 files changed, 22 insertions(+)

diff --git a/init/Kconfig b/init/Kconfig
index d0d021b3fa3b..83cff5d63ce2 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -573,6 +573,16 @@ config HAVE_SCHED_AVG_IRQ
 	depends on IRQ_TIME_ACCOUNTING || PARAVIRT_TIME_ACCOUNTING
 	depends on SMP
 
+config SCHED_PREDICT_LOAD
+	bool "Predict the load of se"
+	depends on SMP
+	help
+	  Select this option to enable the load prediction, the load at the
+	  time of dequeue will be predicted according the load at the time
+	  of enqueue.
+
+	  Say N if unsure.
+
 config SCHED_HW_PRESSURE
 	bool
 	default y if ARM && ARM_CPU_TOPOLOGY
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 1af972a92d06..01b23677d003 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1310,6 +1310,18 @@ config SCHED_DEBUG
 	  that can help debug the scheduler. The runtime overhead of this
 	  option is minimal.
 
+config SCHED_PREDICT_LOAD_DEBUG
+	bool "Debug for SCHED_PREDICT_LOAD"
+	depends on SMP && SCHED_PREDICT_LOAD && SCHED_DEBUG
+	default y
+	help
+	  If you say Y here, the /proc/$pid/predict_load file will be provided
+	  the information of task se that can help debug the SCHED_PREDICT_LOAD.
+	  The /sys/kernel/debug/sched/debug file can also see the information
+	  of group se, but compared with task se, there is less information.
+
+	  Say N if unsure.
+
 config SCHED_INFO
 	bool
 	default n
-- 
2.33.0

[PATCH V1 2/4] sched: Do predict load

[zihan zhou]

Patch 2/4 is the core content of this submission.

The main struct is predict_load_data, which every se has one except
init_task. Both group se and task se has it.

Predict load is mainly realized by functions record_predict_load_data
and se_do_predict_load, they run when dequeue and enqueue.

when enqueue, se_do_predict_load record load_normalized_when_enqueue,
and try get predict_load_normalized. when dequeue, record_predict_load_data
use record_load_array to record correspondence between enqueue load and
dequeue load.

Here we use Boyer–Moore majority vote algorithm, I think prediction is
considered reliable only when the confidence is greater than
CONFIDENCE_THRESHOLD(4), this is an experimental value.

It has also been explained in patch 0/4 that the load will be normalized to
0~1024. From the perspective of machine learning, normalization is better,
and it also helps to deal with some special cases.

All operation time complexity is O(1), and predict load will not affect
performance, at least when I test.

TODO:
There are still many shortcomings here. I hope to have the opportunity
to establish a mapping of exec_filename to predict_load_data and add
exec statistics, which helps the kernel distinguish whether the executable
file is sysbench or cyclictest.

Signed-off-by: zihan zhou <15645113830zzh@gmail.com>
---
 include/linux/sched.h      |  46 ++++++++++++
 include/linux/sched/task.h |   2 +-
 init/init_task.c           |   3 +
 kernel/fork.c              |   6 +-
 kernel/sched/core.c        |  15 +++-
 kernel/sched/fair.c        | 148 ++++++++++++++++++++++++++++++++++++-
 kernel/sched/sched.h       |   2 +
 7 files changed, 217 insertions(+), 5 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 9632e3318e0d..b8576bca5a5d 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -491,6 +491,42 @@ struct sched_avg {
 	unsigned int			util_est;
 } ____cacheline_aligned;
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+
+#define NO_PREDICT_LOAD ULONG_MAX
+#define CONFIDENCE_THRESHOLD 4
+
+#define PREDICT_LOAD_MAX 1024
+#define LOAD_GRAN_SHIFT 4
+#define LOAD_GRAN (1 << LOAD_GRAN_SHIFT)
+
+struct record_load {
+	u8 load_after_offset;
+	u8 confidence;
+};
+
+extern struct kmem_cache *predict_load_data_cachep;
+
+#endif
+
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+
+	struct predict_load_data {
+		//1024 Special processing, index does not need +1.
+		struct record_load record_load_array[PREDICT_LOAD_MAX >> LOAD_GRAN_SHIFT];
+		unsigned long		load_normalized_when_enqueue;
+		unsigned long		predict_load_normalized;
+
+#ifdef CONFIG_SCHED_PREDICT_LOAD_DEBUG
+		unsigned long predict_count;
+		unsigned long predict_correct_count;
+		unsigned long no_predict_count;
+#endif
+		bool in_predict_no_preempt;
+	};
+
+#endif
+
 /*
  * The UTIL_AVG_UNCHANGED flag is used to synchronize util_est with util_avg
  * updates. When a task is dequeued, its util_est should not be updated if its
@@ -587,9 +623,19 @@ struct sched_entity {
 	 * collide with read-mostly values above.
 	 */
 	struct sched_avg		avg;
+
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	struct predict_load_data *pldp;
+#endif
 #endif
 };
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+unsigned long get_predict_load(struct sched_entity *se);
+void set_in_predict_no_preempt(struct sched_entity *se, bool in_predict_no_preempt);
+bool predict_error_should_resched(struct sched_entity *se);
+#endif
+
 struct sched_rt_entity {
 	struct list_head		run_list;
 	unsigned long			timeout;
diff --git a/include/linux/sched/task.h b/include/linux/sched/task.h
index 0f2aeb37bbb0..c5d435b9fce9 100644
--- a/include/linux/sched/task.h
+++ b/include/linux/sched/task.h
@@ -62,7 +62,7 @@ extern int lockdep_tasklist_lock_is_held(void);
 extern asmlinkage void schedule_tail(struct task_struct *prev);
 extern void init_idle(struct task_struct *idle, int cpu);
 
-extern int sched_fork(unsigned long clone_flags, struct task_struct *p);
+extern int sched_fork(unsigned long clone_flags, struct task_struct *p, int node);
 extern int sched_cgroup_fork(struct task_struct *p, struct kernel_clone_args *kargs);
 extern void sched_cancel_fork(struct task_struct *p);
 extern void sched_post_fork(struct task_struct *p);
diff --git a/init/init_task.c b/init/init_task.c
index e557f622bd90..c0ea11adfdab 100644
--- a/init/init_task.c
+++ b/init/init_task.c
@@ -89,6 +89,9 @@ struct task_struct init_task __aligned(L1_CACHE_BYTES) = {
 	},
 	.se		= {
 		.group_node 	= LIST_HEAD_INIT(init_task.se.group_node),
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+		.pldp			= NULL,
+#endif
 	},
 	.rt		= {
 		.run_list	= LIST_HEAD_INIT(init_task.rt.run_list),
diff --git a/kernel/fork.c b/kernel/fork.c
index 735405a9c5f3..b8ba621d2a87 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -182,6 +182,10 @@ static inline struct task_struct *alloc_task_struct_node(int node)
 
 static inline void free_task_struct(struct task_struct *tsk)
 {
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	if (tsk->se.pldp != NULL && predict_load_data_cachep != NULL)
+		kmem_cache_free(predict_load_data_cachep, tsk->se.pldp);
+#endif
 	kmem_cache_free(task_struct_cachep, tsk);
 }
 
@@ -2370,7 +2374,7 @@ __latent_entropy struct task_struct *copy_process(
 #endif
 
 	/* Perform scheduler related setup. Assign this task to a CPU. */
-	retval = sched_fork(clone_flags, p);
+	retval = sched_fork(clone_flags, p, node);
 	if (retval)
 		goto bad_fork_cleanup_policy;
 
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 165c90ba64ea..905d53503a35 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -4712,7 +4712,7 @@ late_initcall(sched_core_sysctl_init);
 /*
  * fork()/clone()-time setup:
  */
-int sched_fork(unsigned long clone_flags, struct task_struct *p)
+int sched_fork(unsigned long clone_flags, struct task_struct *p, int node)
 {
 	__sched_fork(clone_flags, p);
 	/*
@@ -4768,7 +4768,9 @@ int sched_fork(unsigned long clone_flags, struct task_struct *p)
 	}
 
 	init_entity_runnable_average(&p->se);
-
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	init_entity_predict_load_data(&p->se, node);
+#endif
 
 #ifdef CONFIG_SCHED_INFO
 	if (likely(sched_info_on()))
@@ -8472,11 +8474,20 @@ LIST_HEAD(task_groups);
 static struct kmem_cache *task_group_cache __ro_after_init;
 #endif
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+struct kmem_cache *predict_load_data_cachep;
+#endif
+
 void __init sched_init(void)
 {
 	unsigned long ptr = 0;
 	int i;
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	predict_load_data_cachep = kmem_cache_create("predict_load_data",
+		sizeof(struct predict_load_data), 0, SLAB_PANIC|SLAB_ACCOUNT, NULL);
+#endif
+
 	/* Make sure the linker didn't screw up */
 #ifdef CONFIG_SMP
 	BUG_ON(!sched_class_above(&stop_sched_class, &dl_sched_class));
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 857808da23d8..d22d47419f79 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1068,6 +1068,23 @@ void init_entity_runnable_average(struct sched_entity *se)
 	/* when this task is enqueued, it will contribute to its cfs_rq's load_avg */
 }
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+void init_entity_predict_load_data(struct sched_entity *se, int node)
+{
+	if (predict_load_data_cachep == NULL) {
+		se->pldp = NULL;
+		return;
+	}
+
+	struct predict_load_data *pldp = kmem_cache_alloc_node(predict_load_data_cachep,
+										 GFP_KERNEL, node);
+
+	memset(pldp, 0, sizeof(*(pldp)));
+	pldp->predict_load_normalized = NO_PREDICT_LOAD;
+	se->pldp = pldp;
+}
+#endif
+
 /*
  * With new tasks being created, their initial util_avgs are extrapolated
  * based on the cfs_rq's current util_avg:
@@ -4701,6 +4718,114 @@ static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *s
 	trace_pelt_cfs_tp(cfs_rq);
 }
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+
+static unsigned long get_load_after_offset(unsigned long load)
+{
+	if (load >= PREDICT_LOAD_MAX)
+		load = PREDICT_LOAD_MAX - 1;
+	return load >> LOAD_GRAN_SHIFT;
+}
+
+/*
+ * Here I don't want the weight of se to affect the load, because
+ * the predict_load_data is designed to record load form 0 to 1024,
+ * so normalized it, we can restore it as needed by restore_normalized_load.
+ */
+static unsigned long get_normalized_load(struct sched_entity *se)
+{
+	unsigned long normalized_load, load = se->avg.load_avg;
+
+	//Prevent arithmetic overflow
+	WARN_ON_ONCE(load > 4000000);
+	if (se_weight(se) == PREDICT_LOAD_MAX)
+		return load;
+	normalized_load = div_u64(load * PREDICT_LOAD_MAX, se_weight(se));
+	return min(normalized_load, PREDICT_LOAD_MAX);
+}
+
+static unsigned long restore_normalized_load(unsigned long normalized_load, unsigned long weight)
+{
+	unsigned long load;
+
+	//Prevent arithmetic overflow
+	WARN_ON_ONCE(normalized_load > 4000000);
+	if (weight == PREDICT_LOAD_MAX)
+		return normalized_load;
+	load = div_u64(load * weight, PREDICT_LOAD_MAX);
+	return load;
+}
+
+//This is a useful API.
+unsigned long get_predict_load(struct sched_entity *se)
+{
+	if (se->pldp == NULL)
+		return NO_PREDICT_LOAD;
+	struct predict_load_data *pldp = se->pldp;
+	unsigned long predict_load_normalized = pldp->predict_load_normalized;
+	unsigned long predict_load;
+
+	if (predict_load_normalized == NO_PREDICT_LOAD)
+		return NO_PREDICT_LOAD;
+
+	predict_load = restore_normalized_load(predict_load_normalized + LOAD_GRAN, se_weight(se));
+	return predict_load;
+}
+
+
+static void record_predict_load_data(struct sched_entity *se)
+{
+	if (se->pldp == NULL)
+		return;
+	struct predict_load_data *pldp = se->pldp;
+	struct record_load *rla = pldp->record_load_array;
+	unsigned long load_normalized_when_dequeue = get_normalized_load(se);
+	unsigned long load_normalized_when_enqueue = se->pldp->load_normalized_when_enqueue;
+	unsigned long index = get_load_after_offset(load_normalized_when_enqueue);
+	unsigned long val = get_load_after_offset(load_normalized_when_dequeue);
+
+#ifdef CONFIG_SCHED_PREDICT_LOAD_DEBUG
+	if (pldp->predict_load_normalized != NO_PREDICT_LOAD) {
+		pldp->predict_count++;
+		if (load_normalized_when_dequeue >= pldp->predict_load_normalized
+		&& load_normalized_when_dequeue <= pldp->predict_load_normalized + LOAD_GRAN)
+			pldp->predict_correct_count++;
+	} else {
+		pldp->no_predict_count++;
+	}
+#endif
+
+	if (rla[index].load_after_offset == val) {
+		if (rla[index].confidence < 255)
+			rla[index].confidence++;
+	} else {
+		if (rla[index].confidence <= 1) {
+			rla[index].load_after_offset = val;
+			rla[index].confidence = 1;
+		} else {
+			rla[index].confidence--;
+		}
+	}
+}
+
+static void se_do_predict_load(struct sched_entity *se)
+{
+	if (se->pldp == NULL)
+		return;
+	unsigned long index, predict_load_normalized = NO_PREDICT_LOAD;
+	struct predict_load_data *pldp = se->pldp;
+	struct record_load *rla = pldp->record_load_array;
+
+	pldp->load_normalized_when_enqueue = get_normalized_load(se);
+	index = get_load_after_offset(pldp->load_normalized_when_enqueue);
+
+	if (rla[index].confidence >= CONFIDENCE_THRESHOLD)
+		predict_load_normalized = rla[index].load_after_offset << LOAD_GRAN_SHIFT;
+	pldp->predict_load_normalized = predict_load_normalized;
+}
+
+#endif
+
 /**
  * detach_entity_load_avg - detach this entity from its cfs_rq load avg
  * @cfs_rq: cfs_rq to detach from
@@ -5336,6 +5461,11 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 	 */
 	update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
 	se_update_runnable(se);
+
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	se_do_predict_load(se);
+#endif
+
 	/*
 	 * XXX update_load_avg() above will have attached us to the pelt sum;
 	 * but update_cfs_group() here will re-adjust the weight and have to
@@ -5493,6 +5623,11 @@ dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 	update_load_avg(cfs_rq, se, action);
 	se_update_runnable(se);
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	record_predict_load_data(se);
+	set_in_predict_no_preempt(se, false);
+#endif
+
 	update_stats_dequeue_fair(cfs_rq, se, flags);
 
 	update_entity_lag(cfs_rq, se);
@@ -5628,6 +5763,9 @@ static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
 	}
 	SCHED_WARN_ON(cfs_rq->curr != prev);
 	cfs_rq->curr = NULL;
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	set_in_predict_no_preempt(prev, false);
+#endif
 }
 
 static void
@@ -13345,8 +13483,13 @@ void free_fair_sched_group(struct task_group *tg)
 	for_each_possible_cpu(i) {
 		if (tg->cfs_rq)
 			kfree(tg->cfs_rq[i]);
-		if (tg->se)
+		if (tg->se) {
 			kfree(tg->se[i]);
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+			if (tg->se[i]->pldp != NULL && predict_load_data_cachep != NULL)
+				kmem_cache_free(predict_load_data_cachep, tg->se[i]->pldp);
+#endif
+		}
 	}
 
 	kfree(tg->cfs_rq);
@@ -13384,6 +13527,9 @@ int alloc_fair_sched_group(struct task_group *tg, struct task_group *parent)
 		init_cfs_rq(cfs_rq);
 		init_tg_cfs_entry(tg, cfs_rq, se, i, parent->se[i]);
 		init_entity_runnable_average(se);
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+		init_entity_predict_load_data(se, cpu_to_node(i));
+#endif
 	}
 
 	return 1;
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index ab16d3d0e51c..cf1e98bf83d3 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -2733,6 +2733,8 @@ extern void init_dl_entity(struct sched_dl_entity *dl_se);
 extern unsigned long to_ratio(u64 period, u64 runtime);
 
 extern void init_entity_runnable_average(struct sched_entity *se);
+extern void init_entity_predict_load_data(struct sched_entity *se, int node);
+
 extern void post_init_entity_util_avg(struct task_struct *p);
 
 #ifdef CONFIG_NO_HZ_FULL
-- 
2.33.0

Re: [PATCH V1 2/4] sched: Do predict load

[kernel test robot]

Hi zihan,

kernel test robot noticed the following build warnings:

[auto build test WARNING on tip/sched/core]
[also build test WARNING on akpm-mm/mm-nonmm-unstable brauner-vfs/vfs.all peterz-queue/sched/core linus/master v6.14-rc4 next-20250227]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/zihan-zhou/sched-Add-kconfig-of-predict-load/20250221-165850
base:   tip/sched/core
patch link:    https://lore.kernel.org/r/20250221085051.32468-1-15645113830zzh%40gmail.com
patch subject: [PATCH V1 2/4] sched: Do predict load
config: hexagon-allyesconfig (https://download.01.org/0day-ci/archive/20250228/202502281647.5vhdZuZE-lkp@intel.com/config)
compiler: clang version 18.1.8 (https://github.com/llvm/llvm-project 3b5b5c1ec4a3095ab096dd780e84d7ab81f3d7ff)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250228/202502281647.5vhdZuZE-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202502281647.5vhdZuZE-lkp@intel.com/

All warnings (new ones prefixed by >>):

>> kernel/sched/fair.c:4755:17: warning: variable 'load' is uninitialized when used here [-Wuninitialized]
    4755 |         load = div_u64(load * weight, PREDICT_LOAD_MAX);
         |                        ^~~~
   kernel/sched/fair.c:4749:20: note: initialize the variable 'load' to silence this warning
    4749 |         unsigned long load;
         |                           ^
         |                            = 0
   1 warning generated.


vim +/load +4755 kernel/sched/fair.c

  4746	
  4747	static unsigned long restore_normalized_load(unsigned long normalized_load, unsigned long weight)
  4748	{
  4749		unsigned long load;
  4750	
  4751		//Prevent arithmetic overflow
  4752		WARN_ON_ONCE(normalized_load > 4000000);
  4753		if (weight == PREDICT_LOAD_MAX)
  4754			return normalized_load;
> 4755		load = div_u64(load * weight, PREDICT_LOAD_MAX);
  4756		return load;
  4757	}
  4758	

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

Re: [PATCH V1 2/4] sched: Do predict load

[kernel test robot]

Hi zihan,

kernel test robot noticed the following build errors:

[auto build test ERROR on tip/sched/core]
[also build test ERROR on akpm-mm/mm-nonmm-unstable brauner-vfs/vfs.all peterz-queue/sched/core linus/master v6.14-rc4 next-20250228]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/zihan-zhou/sched-Add-kconfig-of-predict-load/20250221-165850
base:   tip/sched/core
patch link:    https://lore.kernel.org/r/20250221085051.32468-1-15645113830zzh%40gmail.com
patch subject: [PATCH V1 2/4] sched: Do predict load
config: x86_64-randconfig-076-20250301 (https://download.01.org/0day-ci/archive/20250302/202503020410.hBcraNw8-lkp@intel.com/config)
compiler: clang version 19.1.7 (https://github.com/llvm/llvm-project cd708029e0b2869e80abe31ddb175f7c35361f90)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250302/202503020410.hBcraNw8-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202503020410.hBcraNw8-lkp@intel.com/

All errors (new ones prefixed by >>):

>> ld.lld: error: undefined symbol: set_in_predict_no_preempt
   >>> referenced by fair.c:5628 (kernel/sched/fair.c:5628)
   >>>               vmlinux.o:(dequeue_entity)
   >>> referenced by fair.c:5767 (kernel/sched/fair.c:5767)
   >>>               vmlinux.o:(put_prev_entity)

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

[PATCH V1 3/4] sched: add debug for predict load

[zihan zhou]

We can see the debugging information about load prediction from
/proc/$pid/predict_load (task se) and /sys/kernel/debug/sched/debug
(group se)

An example:
[root@test sched]# cat /proc/1/predict_load 
se.pldp->predict_correct_count               :                 7699 
se.pldp->predict_count                       :                 7820
se.pldp->no_predict_count                    :                  263
enqueue_load_normalized: 0, dequeue_load_normalized: 0, confidence:255
enqueue_load_normalized: 16, dequeue_load_normalized: 16, confidence:42
enqueue_load_normalized: 32, dequeue_load_normalized: 32, confidence:14
enqueue_load_normalized: 48, dequeue_load_normalized: 48, confidence:5 
enqueue_load_normalized: 64, dequeue_load_normalized: 64, confidence:8 
enqueue_load_normalized: 80, dequeue_load_normalized: 80, confidence:9 
enqueue_load_normalized: 96, dequeue_load_normalized: 96, confidence:3 
enqueue_load_normalized: 112, dequeue_load_normalized: 128, confidence:2 

/sys/kernel/debug/sched/debug only have predict_count.

Signed-off-by: zihan zhou <15645113830zzh@gmail.com>
---
 fs/proc/base.c              | 39 +++++++++++++++++++++++++++++++++++++
 include/linux/sched/debug.h |  5 +++++
 kernel/sched/debug.c        | 39 +++++++++++++++++++++++++++++++++++++
 3 files changed, 83 insertions(+)

diff --git a/fs/proc/base.c b/fs/proc/base.c
index cd89e956c322..e66173ce941b 100644
--- a/fs/proc/base.c
+++ b/fs/proc/base.c
@@ -1541,6 +1541,39 @@ static const struct file_operations proc_pid_sched_operations = {
 
 #endif
 
+
+#ifdef CONFIG_SCHED_PREDICT_LOAD_DEBUG
+
+static int predict_load_show(struct seq_file *m, void *v)
+{
+	struct inode *inode = m->private;
+	struct pid_namespace *ns = proc_pid_ns(inode->i_sb);
+	struct task_struct *p;
+
+	p = get_proc_task(inode);
+	if (!p)
+		return -ESRCH;
+	proc_predict_load_show_task(p, ns, m);
+
+	put_task_struct(p);
+
+	return 0;
+}
+
+static int predict_load_open(struct inode *inode, struct file *filp)
+{
+	return single_open(filp, predict_load_show, inode);
+}
+
+static const struct file_operations proc_pid_predict_load_operations = {
+	.open		= predict_load_open,
+	.read		= seq_read,
+	.llseek		= seq_lseek,
+	.release	= single_release,
+};
+
+#endif
+
 #ifdef CONFIG_SCHED_AUTOGROUP
 /*
  * Print out autogroup related information:
@@ -3334,6 +3367,9 @@ static const struct pid_entry tgid_base_stuff[] = {
 #ifdef CONFIG_SCHED_DEBUG
 	REG("sched",      S_IRUGO|S_IWUSR, proc_pid_sched_operations),
 #endif
+#ifdef CONFIG_SCHED_PREDICT_LOAD_DEBUG
+	REG("predict_load",      S_IRUGO, proc_pid_predict_load_operations),
+#endif
 #ifdef CONFIG_SCHED_AUTOGROUP
 	REG("autogroup",  S_IRUGO|S_IWUSR, proc_pid_sched_autogroup_operations),
 #endif
@@ -3684,6 +3720,9 @@ static const struct pid_entry tid_base_stuff[] = {
 	ONE("limits",	 S_IRUGO, proc_pid_limits),
 #ifdef CONFIG_SCHED_DEBUG
 	REG("sched",     S_IRUGO|S_IWUSR, proc_pid_sched_operations),
+#endif
+#ifdef CONFIG_SCHED_PREDICT_LOAD_DEBUG
+	REG("predict_load",      S_IRUGO, proc_pid_predict_load_operations),
 #endif
 	NOD("comm",      S_IFREG|S_IRUGO|S_IWUSR,
 			 &proc_tid_comm_inode_operations,
diff --git a/include/linux/sched/debug.h b/include/linux/sched/debug.h
index b5035afa2396..5b2bab60afae 100644
--- a/include/linux/sched/debug.h
+++ b/include/linux/sched/debug.h
@@ -40,6 +40,11 @@ struct seq_file;
 extern void proc_sched_show_task(struct task_struct *p,
 				 struct pid_namespace *ns, struct seq_file *m);
 extern void proc_sched_set_task(struct task_struct *p);
+
+#ifdef CONFIG_SCHED_PREDICT_LOAD_DEBUG
+extern void proc_predict_load_show_task(struct task_struct *p,
+					struct pid_namespace *ns, struct seq_file *m);
+#endif
 #endif
 
 /* Attach to any functions which should be ignored in wchan output. */
diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
index ef047add7f9e..619b96333f6a 100644
--- a/kernel/sched/debug.c
+++ b/kernel/sched/debug.c
@@ -690,6 +690,12 @@ static void print_cfs_group_stats(struct seq_file *m, int cpu, struct task_group
 	P(se->avg.runnable_avg);
 #endif
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD_DEBUG
+	P(se->pldp->predict_correct_count);
+	P(se->pldp->predict_count);
+	P(se->pldp->no_predict_count);
+#endif
+
 #undef PN_SCHEDSTAT
 #undef PN
 #undef P_SCHEDSTAT
@@ -1160,6 +1166,39 @@ static void sched_show_numa(struct task_struct *p, struct seq_file *m)
 #endif
 }
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD_DEBUG
+
+void proc_predict_load_show_task(struct task_struct *p, struct pid_namespace *ns,
+						  struct seq_file *m)
+{
+	struct predict_load_data *pldp = p->se.pldp;
+
+	if (pldp == NULL)
+		return;
+	struct record_load *rla = pldp->record_load_array;
+
+	unsigned long index, enqueue_load_normalized, dequeue_load_normalized, confidence;
+
+	P(se.pldp->predict_correct_count);
+	P(se.pldp->predict_count);
+	P(se.pldp->no_predict_count);
+
+
+	for (index = 0; index < (PREDICT_LOAD_MAX >> LOAD_GRAN_SHIFT); index++) {
+		enqueue_load_normalized = index << LOAD_GRAN_SHIFT;
+		dequeue_load_normalized = rla[index].load_after_offset << LOAD_GRAN_SHIFT;
+		confidence = rla[index].confidence;
+		if (confidence) {
+			SEQ_printf(m, "enqueue_load_normalized: %ld, ", enqueue_load_normalized);
+			SEQ_printf(m, "dequeue_load_normalized: %ld, ", dequeue_load_normalized);
+			SEQ_printf(m, "confidence:%ld\n", confidence);
+		}
+	}
+
+}
+
+#endif
+
 void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns,
 						  struct seq_file *m)
 {
-- 
2.33.0

[PATCH V1 4/4] sched: add feature PREDICT_NO_PREEMPT

[zihan zhou]

Patch 4/4 is independent. It is an attempt to use the predict load.

I observed that some tasks were almost finished, but they were preempted
and had to spend more time running.

This task can be identified by load prediction, that is, the load when
enqueue is basically equal to the load when dequeue.

If the se to be preempted is such a task and the pse should have
preempted the se, PREDICT_NO_PREEMPT prevents pse from preempting and
compensates pse (set_next_buddy).

This is a protection for tasks that are executed immediately. If we find
that our prediction fails later, we will resched the se.

It can be said that this is a way to automatically adjust to
SCHED_BATCH, The performance of hackbench has improved a little.

./hackbench -g 8 -l 10000
orig: 2.063s   with PREDICT_NO_PREEMPT: 1.833s
./hackbench -g 16 -l 10000                                        
orig: 3.658s   with PREDICT_NO_PREEMPT: 3.479s

The average latency of cyclictest (with hackbench) has increased, but the
maximum latency is no different.

orig:
I:1000 C: 181852 Min:      4 Act:   59 Avg:  212 Max:   21838
with PREDICT_NO_PREEMPT:
I:1000 C: 181564 Min:      8 Act:   80 Avg:  457 Max:   22989

I think this kind of scheduling protection can't increase the scheduling
delay over 1ms (every tick will check whether the prediction is correct).
And it can improve the overall throughput, which seems acceptable.
Of course, this patch is still experimental, and welcome to put forward
suggestions.

(Seems to predict util better?)

In addition, I found that even if a high load hackbench was hung in
the background, the terminal operation was still very smooth.

Signed-off-by: zihan zhou <15645113830zzh@gmail.com>
---
 kernel/sched/fair.c     | 92 +++++++++++++++++++++++++++++++++++++++--
 kernel/sched/features.h |  4 ++
 2 files changed, 92 insertions(+), 4 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index d22d47419f79..21bf58a494ba 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -1258,6 +1258,9 @@ static void update_curr(struct cfs_rq *cfs_rq)
 
 	curr->vruntime += calc_delta_fair(delta_exec, curr);
 	resched = update_deadline(cfs_rq, curr);
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	resched |= predict_error_should_resched(curr);
+#endif
 	update_min_vruntime(cfs_rq);
 
 	if (entity_is_task(curr)) {
@@ -8884,6 +8887,60 @@ static void set_next_buddy(struct sched_entity *se)
 	}
 }
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+static bool predict_se_will_end_soon(struct sched_entity *se)
+{
+	struct predict_load_data *pldp = se->pldp;
+
+	if (pldp == NULL)
+		return false;
+	if (pldp->predict_load_normalized == NO_PREDICT_LOAD)
+		return false;
+	if (pldp->predict_load_normalized > pldp->load_normalized_when_enqueue)
+		return false;
+	if (se->avg.load_avg >= get_predict_load(se))
+		return false;
+	return true;
+}
+
+void set_in_predict_no_preempt(struct sched_entity *se, bool in_predict_no_preempt)
+{
+	struct predict_load_data *pldp = se->pldp;
+
+	if (pldp == NULL)
+		return;
+	pldp->in_predict_no_preempt = in_predict_no_preempt;
+}
+
+static bool get_in_predict_no_preempt(struct sched_entity *se)
+{
+	struct predict_load_data *pldp = se->pldp;
+
+	if (pldp == NULL)
+		return false;
+	return pldp->in_predict_no_preempt;
+}
+
+static bool predict_right(struct sched_entity *se)
+{
+	struct predict_load_data *pldp = se->pldp;
+
+	if (pldp == NULL)
+		return false;
+	if (pldp->predict_load_normalized == NO_PREDICT_LOAD)
+		return false;
+	if (se->avg.load_avg <= get_predict_load(se))
+		return true;
+	return false;
+}
+
+bool predict_error_should_resched(struct sched_entity *se)
+{
+	return get_in_predict_no_preempt(se) && !predict_right(se);
+}
+
+#endif
+
 /*
  * Preempt the current task with a newly woken task if needed:
  */
@@ -8893,6 +8950,10 @@ static void check_preempt_wakeup_fair(struct rq *rq, struct task_struct *p, int
 	struct sched_entity *se = &donor->se, *pse = &p->se;
 	struct cfs_rq *cfs_rq = task_cfs_rq(donor);
 	int cse_is_idle, pse_is_idle;
+	bool if_best_se;
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	bool predict_no_preempt = false;
+#endif
 
 	if (unlikely(se == pse))
 		return;
@@ -8954,6 +9015,21 @@ static void check_preempt_wakeup_fair(struct rq *rq, struct task_struct *p, int
 	if (unlikely(!normal_policy(p->policy)))
 		return;
 
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	/*
+	 * If If we predict that se will end soon, it's better not to preempt it,
+	 * but wait for it to exit by itself. This is undoubtedly a grievance for
+	 * pse, so if pse should preempt se, we will give it some compensation.
+	 */
+	if (sched_feat(PREDICT_NO_PREEMPT)) {
+		if (predict_error_should_resched(se))
+			goto preempt;
+
+		if (predict_se_will_end_soon(se))
+			predict_no_preempt = true;
+	}
+#endif
+
 	cfs_rq = cfs_rq_of(se);
 	update_curr(cfs_rq);
 	/*
@@ -8966,10 +9042,18 @@ static void check_preempt_wakeup_fair(struct rq *rq, struct task_struct *p, int
 	if (do_preempt_short(cfs_rq, pse, se))
 		cancel_protect_slice(se);
 
-	/*
-	 * If @p has become the most eligible task, force preemption.
-	 */
-	if (pick_eevdf(cfs_rq) == pse)
+	if_best_se = (pick_eevdf(cfs_rq) == pse);
+
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+	if (predict_no_preempt) {
+		if (if_best_se && !pse->sched_delayed) {
+			set_next_buddy(pse);
+			set_in_predict_no_preempt(se, true);
+			return;
+		}
+	}
+#endif
+	if (if_best_se)
 		goto preempt;
 
 	return;
diff --git a/kernel/sched/features.h b/kernel/sched/features.h
index 3c12d9f93331..8a78108af835 100644
--- a/kernel/sched/features.h
+++ b/kernel/sched/features.h
@@ -121,3 +121,7 @@ SCHED_FEAT(WA_BIAS, true)
 SCHED_FEAT(UTIL_EST, true)
 
 SCHED_FEAT(LATENCY_WARN, false)
+
+#ifdef CONFIG_SCHED_PREDICT_LOAD
+SCHED_FEAT(PREDICT_NO_PREEMPT, true)
+#endif
-- 
2.33.0