Re: [PATCH] sched/fair: Fix overflow in vruntime_eligible() causing NULL return

Re: [PATCH] sched/fair: Fix overflow in vruntime_eligible() causing NULL return

[quzicheng]

> May I ask which specific version of the 6.6 LTS branch are you using?
Hi, based on 6.6.31

[PATCH] sched/fair: Fix overflow in vruntime_eligible() causing NULL return

[Fang Xiang]

In the vruntime_eligible() function, the original comparison:
	return avg >= (s64)(vruntime - cfs_rq->min_vruntime) * load;
could produce incorrect results due to integer overflow in the 'avg' or
s64 part.

This overflow causes the comparison to return false even when the
mathematical result should be true, leading all tasks to be falsely
deemed ineligible. Consequently, pick_eevdf() returns NULL, triggering a
kernel crash. This issue was discovered on kernel 6.6.76, it may be incorrect
to simply spot a potentially overflowing integer type and directly use
the >= sign for comparison.

The following are the relevant attributes that cause the return of NULL:
cfs_rq:
my_q = 0xFFFFFF8019BF2600 -> (
      load = (weight = 3609742336, inv_weight = 0),
      nr_running = 647,
      h_nr_running = 647,
      idle_nr_running = 0,
      idle_h_nr_running = 0,
      avg_vruntime = -13338730231239499,
      avg_load = 3525139,
      exec_clock = 598416298647,
      min_vruntime = 1918334512120,
      tasks_timeline = (
        rb_root = (rb_node = 0xFFFFFF811B63A850),
        rb_leftmost = 0xFFFFFF810C5B2850),
      )
)

root node:
 (struct sched_entity *)(0xFFFFFF811B63A850- 0x10) = 0xFFFFFF811B63A840 -> (
    load = (weight = 2561024, inv_weight = 1717300),
    run_node = (__rb_parent_color = 1, rb_right = 0xFFFFFF8054864FD0, rb_left = 0xFFFFFF8104916390),
    deadline = 1918337366679,
    min_vruntime = 18446741380279378713,
    on_rq = 1,
    sum_exec_runtime = 349968442385,
    prev_sum_exec_runtime = 349967120379,
    vruntime = 1918336679648,
 )

leftmost node:
(struct sched_entity *)(0xFFFFFF810C5B2850- 0x10) = 0xFFFFFF810C5B2840 -> (
    load = (weight = 1048576, inv_weight = 4194304),
    deadline = 18446741380282378713,
    min_vruntime = 18446741380279378713,
    on_rq = 1,
    sum_exec_runtime = 17431358323,
    prev_sum_exec_runtime = 307584686,
    vruntime = 18446741380279378713,
    vlag = 4607980805462,
 )

Signed-off-by: Fang Xiang <fangxiang3@xiaomi.com>
---
 kernel/sched/fair.c | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 726fa69c4d88..f597f8869b37 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -746,6 +746,8 @@ int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
 	struct sched_entity *curr = cfs_rq->curr;
 	s64 avg = cfs_rq->avg_vruntime;
 	long load = cfs_rq->avg_load;
+	s64 a = entity_key(cfs_rq, se);
+	s64 b, d;
 
 	if (curr && curr->on_rq) {
 		unsigned long weight = scale_load_down(curr->load.weight);
@@ -754,7 +756,11 @@ int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
 		load += weight;
 	}
 
-	return avg >= entity_key(cfs_rq, se) * load;
+	b = (s64)load;
+	if (check_mul_overflow(a, b, &d))
+		return 1;
+
+	return avg - d >= 0;
 }
 
 static u64 __update_min_vruntime(struct cfs_rq *cfs_rq, u64 vruntime)
-- 
2.34.1

[PATCH] sched/fair: Fix overflow in vruntime_eligible() causing NULL return

[Zicheng Qu]

In the vruntime_eligible() function, the original comparison:
	return avg >= (s64)(vruntime - cfs_rq->min_vruntime) * load;
could produce incorrect results due to integer overflow in the 'avg' or
s64 part.

This overflow causes the comparison to return false even when the
mathematical result should be true, leading all tasks to be falsely
deemed ineligible. Consequently, pick_eevdf() returns NULL, triggering a
kernel crash.

The best approach should be to dig deep into why overflow occurs, which
attributes lead to the overflow, whether it is normal, and how to avoid
it. Not pretty sure if this part of the modification will introduce new
issues, but it may be incorrect to simply spot a potentially
overflowing integer type and directly use the >= sign for comparison.
Therefore, drawing on the enqueue method in the rb tree, to avoid the
impact of overflow, the method of first performing subtraction and then
comparing with 0 is also adopted.

The following are the relevant attributes that cause the return of NULL:
crash> struct cfs_rq.avg_vruntime,avg_load,min_vruntime
ffff9ea77ecb4280
  avg_vruntime = -4392414779907141680,
  avg_load = 28644,
  min_vruntime = 239776551994501,

sched_entity: curr
crash> struct sched_entity.deadline,min_vruntime,vruntime,load,vlag
0xffff9ea74510d800
  deadline = 86432035728535,
  min_vruntime = 86431486021988,
  vruntime = 86431531134184,
  load = {
    weight = 6066,
    inv_weight = 0
  },
  vlag = 86431823023195,

the sched_entity mapping to the root node in the cfs_rq
crash> struct sched_entity.deadline,min_vruntime,vruntime,load,vlag -l
sched_entity.run_node 0xffff9ea849fbc350
  deadline = 18446615868453340281,
  min_vruntime = 18446615868452621390,
  vruntime = 18446615868453018539,
  load = {
    weight = 9777152,
    inv_weight = 449829
  },
  vlag = -5599,

the sched_entity mapping to the leftmost node in the csf_rq, also the
left child of root node.
crash> struct sched_entity.deadline,min_vruntime,vruntime,load,vlag -l
sched_entity.run_node 0xffff9ea78d0280d0
  deadline = 18446615868452943132,
  min_vruntime = 18446615868452621390,
  vruntime = 18446615868452621390,
  load = {
    weight = 9777152,
    inv_weight = 449829
  },
  vlag = 444143,

the sched_entity mapping to the rightmost node in the csf_rq, also the
right child of root node.
crash> struct sched_entity.deadline,min_vruntime,vruntime,load,vlag -l
sched_entity.run_node 0xffff9ea783144350
  deadline = 515705106937888,
  min_vruntime = 515705106616146,
  vruntime = 515705106616146,
  load = {
    weight = 9777152,
    inv_weight = 449829
  },
  vlag = -260493,

Fixes: 147f3efaa241 ("sched/fair: Implement an EEVDF-like scheduling policy")
Signed-off-by: Zicheng Qu <quzicheng@huawei.com>
---
 kernel/sched/fair.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 7a14da5396fb..bfa4090cef93 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -734,7 +734,7 @@ static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
 		load += weight;
 	}
 
-	return avg >= (s64)(vruntime - cfs_rq->min_vruntime) * load;
+	return avg - (s64)(vruntime - cfs_rq->min_vruntime) * load >= 0;
 }
 
 int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
-- 
2.34.1

Re: [PATCH] sched/fair: Fix overflow in vruntime_eligible() causing NULL return

[Peter Zijlstra]

On Wed, Jul 09, 2025 at 09:38:29AM +0000, Zicheng Qu wrote:

> The best approach should be to dig deep into why overflow occurs, which
> attributes lead to the overflow, whether it is normal, and how to avoid
> it.

What kernel version are you seeing this on?

Re: [PATCH] sched/fair: Fix overflow in vruntime_eligible() causing NULL return

[Zicheng Qu]

Hi,

Based on LTS 6.6. I also looked at the code logic around 
vruntime_eligible() in the mainline. It seems that if 
vruntime_eligible() consistently returned false, this could lead to null 
pointer dereferences.

I'm wondering if it's feasible to adjust the handling of integer 
overflows within vruntime_eligible() the way shown in my patch, or if 
there's a specific design rationale behind directly comparing integers 
that are susceptible to overflow in the current implementation?

Thanks

On 7/9/2025 7:53 PM, Peter Zijlstra wrote:
> On Wed, Jul 09, 2025 at 09:38:29AM +0000, Zicheng Qu wrote:
>
>> The best approach should be to dig deep into why overflow occurs, which
>> attributes lead to the overflow, whether it is normal, and how to avoid
>> it.
> What kernel version are you seeing this on?
>

Re: [PATCH] sched/fair: Fix overflow in vruntime_eligible() causing NULL return

[Peter Zijlstra]

On Thu, Jul 10, 2025 at 10:01:15AM +0800, Zicheng Qu wrote:
> Hi,
> 
> Based on LTS 6.6. I also looked at the code logic around vruntime_eligible()
> in the mainline. It seems that if vruntime_eligible() consistently returned
> false, this could lead to null pointer dereferences.

That is a truly ancient kernel.  Please verify the issue is reproducible
on something recent.

Specifically, commit bbce3de72be5 ("sched/eevdf: Fix se->slice being set
to U64_MAX and resulting crash") cured something very similar to this.

Re: [PATCH] sched/fair: Fix overflow in vruntime_eligible() causing NULL return

[Fang Xiang]

On Wed, Jul 09, 2025 at 09:38:29AM +0000, Zicheng Qu wrote:
> In the vruntime_eligible() function, the original comparison:
> 	return avg >= (s64)(vruntime - cfs_rq->min_vruntime) * load;
> could produce incorrect results due to integer overflow in the 'avg' or
> s64 part.
> 
> This overflow causes the comparison to return false even when the
> mathematical result should be true, leading all tasks to be falsely
> deemed ineligible. Consequently, pick_eevdf() returns NULL, triggering a
> kernel crash.
> 
> The best approach should be to dig deep into why overflow occurs, which
> attributes lead to the overflow, whether it is normal, and how to avoid
> it. Not pretty sure if this part of the modification will introduce new
> issues, but it may be incorrect to simply spot a potentially
> overflowing integer type and directly use the >= sign for comparison.
> Therefore, drawing on the enqueue method in the rb tree, to avoid the
> impact of overflow, the method of first performing subtraction and then
> comparing with 0 is also adopted.
> 
> The following are the relevant attributes that cause the return of NULL:
> crash> struct cfs_rq.avg_vruntime,avg_load,min_vruntime
> ffff9ea77ecb4280
>   avg_vruntime = -4392414779907141680,
>   avg_load = 28644,
>   min_vruntime = 239776551994501,
> 
> sched_entity: curr
> crash> struct sched_entity.deadline,min_vruntime,vruntime,load,vlag
> 0xffff9ea74510d800
>   deadline = 86432035728535,
>   min_vruntime = 86431486021988,
>   vruntime = 86431531134184,
>   load = {
>     weight = 6066,
>     inv_weight = 0
>   },
>   vlag = 86431823023195,
> 
> the sched_entity mapping to the root node in the cfs_rq
> crash> struct sched_entity.deadline,min_vruntime,vruntime,load,vlag -l
> sched_entity.run_node 0xffff9ea849fbc350
>   deadline = 18446615868453340281,
>   min_vruntime = 18446615868452621390,
>   vruntime = 18446615868453018539,
>   load = {
>     weight = 9777152,
>     inv_weight = 449829
>   },
>   vlag = -5599,
> 
> the sched_entity mapping to the leftmost node in the csf_rq, also the
> left child of root node.
> crash> struct sched_entity.deadline,min_vruntime,vruntime,load,vlag -l
> sched_entity.run_node 0xffff9ea78d0280d0
>   deadline = 18446615868452943132,
>   min_vruntime = 18446615868452621390,
>   vruntime = 18446615868452621390,
>   load = {
>     weight = 9777152,
>     inv_weight = 449829
>   },
>   vlag = 444143,
> 
> the sched_entity mapping to the rightmost node in the csf_rq, also the
> right child of root node.
> crash> struct sched_entity.deadline,min_vruntime,vruntime,load,vlag -l
> sched_entity.run_node 0xffff9ea783144350
>   deadline = 515705106937888,
>   min_vruntime = 515705106616146,
>   vruntime = 515705106616146,
>   load = {
>     weight = 9777152,
>     inv_weight = 449829
>   },
>   vlag = -260493,
> 
> Fixes: 147f3efaa241 ("sched/fair: Implement an EEVDF-like scheduling policy")
> Signed-off-by: Zicheng Qu <quzicheng@huawei.com>
> ---
>  kernel/sched/fair.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 7a14da5396fb..bfa4090cef93 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -734,7 +734,7 @@ static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
>  		load += weight;
>  	}
>  
> -	return avg >= (s64)(vruntime - cfs_rq->min_vruntime) * load;
> +	return avg - (s64)(vruntime - cfs_rq->min_vruntime) * load >= 0;
>  }
>  
>  int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
> -- 
> 2.34.1
> 
May I ask which specific version of the 6.6 LTS branch are you using? 
On the 6.6.54 kernel version, I've also encountered the same issue in my device.
The following are the relevant attributes that cause the return of NULL in pick_eevdf():
cfs_rq:
  avg_vruntime = -34534164181975319,
  avg_load = 1531079,
  min_vruntime = 26052230711305,
  nr_running = 245,
  h_nr_running = 245,

sched_entity: curr is NULL

the sched_entity mapping to the root node in the cfs_rq
  deadline = 26052232578140,
  min_vruntime = 17382361763776,
  vruntime = 26052229578140,
  load = {
    weight = 1048576,
    inv_weight = 4194304
  },
  vlag = 656101,

the sched_entity mapping to the leftmost node in the csf_rq
  deadline = 17382364763776,
  min_vruntime = 17382361763776,
  vruntime = 17382361763776,
  load = {
    weight = 1048576,
    inv_weight = 4194304
  },
  vlag = 8648818863863,