[PATCH] xen/sched: Fix the sorted insertion in sched_domain_insert_unit()

[PATCH] xen/sched: Fix the sorted insertion in sched_domain_insert_unit()

[Stefano Stabellini]

The loop links the new unit in front of the unit whose successor has a
higher unit_id, rather than after it: inserting 1 into {0, 2} gives
{1, 0, 2}. Stop at the first unit with a higher unit_id instead.

I think it usually works because guest vCPUs are typically inserted in
order.

Signed-off-by: Stefano Stabellini <stefano.stabellini@amd.com>
---
 xen/common/sched/core.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/xen/common/sched/core.c b/xen/common/sched/core.c
index 0b072bdee6..a95d6752df 100644
--- a/xen/common/sched/core.c
+++ b/xen/common/sched/core.c
@@ -489,8 +489,7 @@ static void sched_domain_insert_unit(struct sched_unit *unit, struct domain *d)
 
     for ( prev_unit = &d->sched_unit_list; *prev_unit;
           prev_unit = &(*prev_unit)->next_in_list )
-        if ( (*prev_unit)->next_in_list &&
-             (*prev_unit)->next_in_list->unit_id > unit->unit_id )
+        if ( (*prev_unit)->unit_id > unit->unit_id )
             break;
 
     unit->next_in_list = *prev_unit;
-- 
2.43.0

Re: [PATCH] xen/sched: Fix the sorted insertion in sched_domain_insert_unit()

[Jan Beulich]

On 21.10.2026 00:35, Stefano Stabellini wrote:
> The loop links the new unit in front of the unit whose successor has a
> higher unit_id, rather than after it: inserting 1 into {0, 2} gives
> {1, 0, 2}. Stop at the first unit with a higher unit_id instead.
> 
> I think it usually works because guest vCPUs are typically inserted in
> order.

Plus I can't seem to be able to spot anything which depends on any
particular ordering (except for sched_domain_insert_unit() itself).

> --- a/xen/common/sched/core.c
> +++ b/xen/common/sched/core.c
> @@ -489,8 +489,7 @@ static void sched_domain_insert_unit(struct sched_unit *unit, struct domain *d)
>  
>      for ( prev_unit = &d->sched_unit_list; *prev_unit;
>            prev_unit = &(*prev_unit)->next_in_list )
> -        if ( (*prev_unit)->next_in_list &&
> -             (*prev_unit)->next_in_list->unit_id > unit->unit_id )
> +        if ( (*prev_unit)->unit_id > unit->unit_id )
>              break;
>  
>      unit->next_in_list = *prev_unit;

Part of the problem may also be that "prev_unit" doesn't look to
properly describe the purpose of the variable: We insert before
prev_unit, when the name (to me at least) suggests we mean to
insert after it. IOW I think a rename (together with the correction
of the condition) may help here.

Jan

Re: [PATCH] xen/sched: Fix the sorted insertion in sched_domain_insert_unit()

[Jürgen Groß]

[-- Attachment #1.1.1: Type: text/plain, Size: 1598 bytes --]

On 26.10.26 13:46, Jan Beulich wrote:
> On 21.10.2026 00:35, Stefano Stabellini wrote:
>> The loop links the new unit in front of the unit whose successor has a
>> higher unit_id, rather than after it: inserting 1 into {0, 2} gives
>> {1, 0, 2}. Stop at the first unit with a higher unit_id instead.
>>
>> I think it usually works because guest vCPUs are typically inserted in
>> order.
> 
> Plus I can't seem to be able to spot anything which depends on any
> particular ordering (except for sched_domain_insert_unit() itself).

sched_move_domain() relies on the sequence in a subtle way:

   if ( unit->unit_id + gran == v->vcpu_id )
       unit = unit->next_in_list;

> 
>> --- a/xen/common/sched/core.c
>> +++ b/xen/common/sched/core.c
>> @@ -489,8 +489,7 @@ static void sched_domain_insert_unit(struct sched_unit *unit, struct domain *d)
>>   
>>       for ( prev_unit = &d->sched_unit_list; *prev_unit;
>>             prev_unit = &(*prev_unit)->next_in_list )
>> -        if ( (*prev_unit)->next_in_list &&
>> -             (*prev_unit)->next_in_list->unit_id > unit->unit_id )
>> +        if ( (*prev_unit)->unit_id > unit->unit_id )
>>               break;
>>   
>>       unit->next_in_list = *prev_unit;
> 
> Part of the problem may also be that "prev_unit" doesn't look to
> properly describe the purpose of the variable: We insert before
> prev_unit, when the name (to me at least) suggests we mean to
> insert after it. IOW I think a rename (together with the correction
> of the condition) may help here.

I agree. Maybe "next_unit"?


Juergen

[-- Attachment #1.1.2: OpenPGP public key --]
[-- Type: application/pgp-keys, Size: 3743 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 495 bytes --]

[PATCH v2] xen/sched: Fix the sorted insertion in sched_domain_insert_unit()

[Stefano Stabellini]

The loop links the new unit in front of the unit whose successor has a
higher unit_id, rather than after it: inserting 1 into {0, 2} gives
{1, 0, 2}. Stop at the first unit with a higher unit_id instead.

This goes unnoticed as long as units are inserted in unit_id order, as
guest vCPUs typically are.

Also rename prev_unit to next_unit: the new unit is linked in front of
*next_unit, not after it.

Fixes: 141db7fd4d2d ("xen/sched: build a linked list of struct sched_unit")
Signed-off-by: Stefano Stabellini <stefano.stabellini@amd.com>
---
Changes in v2:
- rename prev_unit to next_unit
- add a Fixes tag
- reword the second paragraph of the commit message

 xen/common/sched/core.c | 13 ++++++-------
 1 file changed, 6 insertions(+), 7 deletions(-)

diff --git a/xen/common/sched/core.c b/xen/common/sched/core.c
index 0b072bdee6..88ae40f954 100644
--- a/xen/common/sched/core.c
+++ b/xen/common/sched/core.c
@@ -483,18 +483,17 @@ static struct sched_unit *sched_alloc_unit_mem(void)
 
 static void sched_domain_insert_unit(struct sched_unit *unit, struct domain *d)
 {
-    struct sched_unit **prev_unit;
+    struct sched_unit **next_unit;
 
     unit->domain = d;
 
-    for ( prev_unit = &d->sched_unit_list; *prev_unit;
-          prev_unit = &(*prev_unit)->next_in_list )
-        if ( (*prev_unit)->next_in_list &&
-             (*prev_unit)->next_in_list->unit_id > unit->unit_id )
+    for ( next_unit = &d->sched_unit_list; *next_unit;
+          next_unit = &(*next_unit)->next_in_list )
+        if ( (*next_unit)->unit_id > unit->unit_id )
             break;
 
-    unit->next_in_list = *prev_unit;
-    *prev_unit = unit;
+    unit->next_in_list = *next_unit;
+    *next_unit = unit;
 }
 
 static struct sched_unit *sched_alloc_unit(struct vcpu *v)
-- 
2.47.3

Re: [PATCH v2] xen/sched: Fix the sorted insertion in sched_domain_insert_unit()

[Juergen Gross]

[-- Attachment #1.1.1: Type: text/plain, Size: 684 bytes --]

On 27.10.26 00:39, Stefano Stabellini wrote:
> The loop links the new unit in front of the unit whose successor has a
> higher unit_id, rather than after it: inserting 1 into {0, 2} gives
> {1, 0, 2}. Stop at the first unit with a higher unit_id instead.
> 
> This goes unnoticed as long as units are inserted in unit_id order, as
> guest vCPUs typically are.
> 
> Also rename prev_unit to next_unit: the new unit is linked in front of
> *next_unit, not after it.
> 
> Fixes: 141db7fd4d2d ("xen/sched: build a linked list of struct sched_unit")
> Signed-off-by: Stefano Stabellini <stefano.stabellini@amd.com>

Reviewed-by: Juergen Gross <jgross@suse.com>


Juergen

[-- Attachment #1.1.2: OpenPGP public key --]
[-- Type: application/pgp-keys, Size: 3743 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 495 bytes --]