[PATCH] Avoid endless loop for vcpu migration

[PATCH] Avoid endless loop for vcpu migration

[Juergen Gross]

[-- Attachment #1: Type: text/plain, Size: 540 bytes --]

On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
with credit scheduler. Avoid this loop by changing the interface of pick_cpu
to indicate a repeated call in this case.

Signed-off-by: juergen.gross@ts.fujitsu.com


6 files changed, 11 insertions(+), 15 deletions(-)
xen/common/sched_arinc653.c |    2 +-
xen/common/sched_credit.c   |   12 +++---------
xen/common/sched_credit2.c  |    2 +-
xen/common/sched_sedf.c     |    2 +-
xen/common/schedule.c       |    6 ++++--
xen/include/xen/sched-if.h  |    2 +-



[-- Attachment #2: xen-work.patch --]
[-- Type: text/x-patch, Size: 5273 bytes --]

# HG changeset patch
# User Juergen Gross <juergen.gross@ts.fujitsu.com>
# Date 1300113178 -3600
# Node ID 9d164ce877a75cab847b8a6e0114230807d5acd6
# Parent  84bacd800bf88e37434d49547ad8224be46e2a52
Avoid endless loop for vcpu migration

On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
with credit scheduler. Avoid this loop by changing the interface of pick_cpu
to indicate a repeated call in this case.

Signed-off-by: juergen.gross@ts.fujitsu.com

diff -r 84bacd800bf8 -r 9d164ce877a7 xen/common/sched_arinc653.c
--- a/xen/common/sched_arinc653.c	Sat Mar 12 13:20:51 2011 +0000
+++ b/xen/common/sched_arinc653.c	Mon Mar 14 15:32:58 2011 +0100
@@ -612,7 +612,7 @@ a653sched_do_schedule(
  * @return          Number of selected physical CPU
  */
 static int
-a653sched_pick_cpu(const struct scheduler *ops, struct vcpu *vc)
+a653sched_pick_cpu(const struct scheduler *ops, struct vcpu *vc, int proposal)
 {
     /* this implementation only supports one physical CPU */
     return 0;
diff -r 84bacd800bf8 -r 9d164ce877a7 xen/common/sched_credit.c
--- a/xen/common/sched_credit.c	Sat Mar 12 13:20:51 2011 +0000
+++ b/xen/common/sched_credit.c	Mon Mar 14 15:32:58 2011 +0100
@@ -459,7 +459,7 @@ __csched_vcpu_is_migrateable(struct vcpu
 }
 
 static int
-_csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc, bool_t commit)
+csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc, int proposal)
 {
     cpumask_t cpus;
     cpumask_t idlers;
@@ -531,7 +531,7 @@ _csched_cpu_pick(const struct scheduler 
                   && (weight_cpu * migrate_factor < weight_nxt) ) )
         {
             cpu = cycle_cpu(CSCHED_PCPU(nxt)->idle_bias, nxt_idlers);
-            if ( commit )
+            if ( proposal == -1 )
                CSCHED_PCPU(nxt)->idle_bias = cpu;
             cpus_andnot(cpus, cpus, per_cpu(cpu_sibling_map, cpu));
         }
@@ -542,12 +542,6 @@ _csched_cpu_pick(const struct scheduler 
     }
 
     return cpu;
-}
-
-static int
-csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc)
-{
-    return _csched_cpu_pick(ops, vc, 1);
 }
 
 static inline void
@@ -632,7 +626,7 @@ csched_vcpu_acct(struct csched_private *
     {
         __csched_vcpu_acct_start(prv, svc);
     }
-    else if ( _csched_cpu_pick(ops, current, 0) != cpu )
+    else if ( csched_cpu_pick(ops, current, cpu) != cpu )
     {
         CSCHED_VCPU_STAT_CRANK(svc, migrate_r);
         CSCHED_STAT_CRANK(migrate_running);
diff -r 84bacd800bf8 -r 9d164ce877a7 xen/common/sched_credit2.c
--- a/xen/common/sched_credit2.c	Sat Mar 12 13:20:51 2011 +0000
+++ b/xen/common/sched_credit2.c	Mon Mar 14 15:32:58 2011 +0100
@@ -1350,7 +1350,7 @@ out:
 }
 
 static int
-csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc)
+csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc, int proposal)
 {
     struct csched_vcpu * const svc = CSCHED_VCPU(vc);
     int new_cpu;
diff -r 84bacd800bf8 -r 9d164ce877a7 xen/common/sched_sedf.c
--- a/xen/common/sched_sedf.c	Sat Mar 12 13:20:51 2011 +0000
+++ b/xen/common/sched_sedf.c	Mon Mar 14 15:32:58 2011 +0100
@@ -442,7 +442,7 @@ static void sedf_destroy_domain(const st
     sedf_free_domdata(ops, d->sched_priv);
 }
 
-static int sedf_pick_cpu(const struct scheduler *ops, struct vcpu *v)
+static int sedf_pick_cpu(const struct scheduler *ops, struct vcpu *v, int proposal)
 {
     cpumask_t online_affinity;
     cpumask_t *online;
diff -r 84bacd800bf8 -r 9d164ce877a7 xen/common/schedule.c
--- a/xen/common/schedule.c	Sat Mar 12 13:20:51 2011 +0000
+++ b/xen/common/schedule.c	Mon Mar 14 15:32:58 2011 +0100
@@ -393,9 +393,10 @@ static void vcpu_migrate(struct vcpu *v)
 static void vcpu_migrate(struct vcpu *v)
 {
     unsigned long flags;
-    unsigned int old_cpu, new_cpu;
+    unsigned int old_cpu, new_cpu, proposal;
     spinlock_t *old_lock, *new_lock;
 
+    proposal = -1;
     old_cpu = new_cpu = v->processor;
     for ( ; ; )
     {
@@ -430,10 +431,11 @@ static void vcpu_migrate(struct vcpu *v)
         old_cpu = v->processor;
         if ( old_lock == per_cpu(schedule_data, old_cpu).schedule_lock )
         {
-            new_cpu = SCHED_OP(VCPU2OP(v), pick_cpu, v);
+            new_cpu = SCHED_OP(VCPU2OP(v), pick_cpu, v, proposal);
             if ( (new_lock == per_cpu(schedule_data, new_cpu).schedule_lock) &&
                  cpu_isset(new_cpu, v->domain->cpupool->cpu_valid) )
                 break;
+            proposal = new_cpu;
         }
 
         if ( old_lock != new_lock )
diff -r 84bacd800bf8 -r 9d164ce877a7 xen/include/xen/sched-if.h
--- a/xen/include/xen/sched-if.h	Sat Mar 12 13:20:51 2011 +0000
+++ b/xen/include/xen/sched-if.h	Mon Mar 14 15:32:58 2011 +0100
@@ -167,7 +167,7 @@ struct scheduler {
     struct task_slice (*do_schedule) (const struct scheduler *, s_time_t,
                                       bool_t tasklet_work_scheduled);
 
-    int          (*pick_cpu)       (const struct scheduler *, struct vcpu *);
+    int          (*pick_cpu)       (const struct scheduler *, struct vcpu *, int proposal);
     int          (*adjust)         (const struct scheduler *, struct domain *,
                                     struct xen_domctl_scheduler_op *);
     int          (*adjust_global)  (const struct scheduler *,

[-- Attachment #3: Type: text/plain, Size: 138 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Re: [PATCH] Avoid endless loop for vcpu migration

[Jan Beulich]

>>> On 14.03.11 at 15:39, Juergen Gross <juergen.gross@ts.fujitsu.com> wrote:
> On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
> with credit scheduler. Avoid this loop by changing the interface of pick_cpu
> to indicate a repeated call in this case.

But you're not changing in any way the loop that doesn't get
exited - did you perhaps read my original description as the
pick function itself looping (which - afaict - it doesn't)?

Further, the change still isn't consistent with idle_bias - the
updating ought to happen on the last iteration (if you need
to call the function more than once), not the first one, which
creates a chicken-and-egg problem for you as you will know
it's the last one only when it returned.

Jan

Re: [PATCH] Avoid endless loop for vcpu migration

[Keir Fraser]

I'm not versed enough in this aspect of the scheduler to ack or commit this.
It just looks a bit ugly and confusing to me. Needs an Ack from George
therefore.

 -- Keir

On 14/03/2011 14:39, "Juergen Gross" <juergen.gross@ts.fujitsu.com> wrote:

> On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
> with credit scheduler. Avoid this loop by changing the interface of pick_cpu
> to indicate a repeated call in this case.
> 
> Signed-off-by: juergen.gross@ts.fujitsu.com
> 
> 
> 6 files changed, 11 insertions(+), 15 deletions(-)
> xen/common/sched_arinc653.c |    2 +-
> xen/common/sched_credit.c   |   12 +++---------
> xen/common/sched_credit2.c  |    2 +-
> xen/common/sched_sedf.c     |    2 +-
> xen/common/schedule.c       |    6 ++++--
> xen/include/xen/sched-if.h  |    2 +-
> 
> 
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com
> http://lists.xensource.com/xen-devel

Re: [PATCH] Avoid endless loop for vcpu migration

[Tim Deegan]

At 15:03 +0000 on 14 Mar (1300115028), Jan Beulich wrote:
> >>> On 14.03.11 at 15:39, Juergen Gross <juergen.gross@ts.fujitsu.com> wrote:
> > On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
> > with credit scheduler. Avoid this loop by changing the interface of pick_cpu
> > to indicate a repeated call in this case.
> 
> But you're not changing in any way the loop that doesn't get
> exited - did you perhaps read my original description as the
> pick function itself looping (which - afaict - it doesn't)?
> 
> Further, the change still isn't consistent with idle_bias - the
> updating ought to happen on the last iteration (if you need
> to call the function more than once), not the first one, which
> creates a chicken-and-egg problem for you as you will know
> it's the last one only when it returned.

Perhaps you could submit a comment patch that describes exactly what
idle_bias is and how it's supposed to work.  At the moment it's entirely
uncommented.

Tim.

-- 
Tim Deegan <Tim.Deegan@citrix.com>
Principal Software Engineer, Xen Platform Team
Citrix Systems UK Ltd.  (Company #02937203, SL9 0BG)

Re: [PATCH] Avoid endless loop for vcpu migration

[Juergen Gross]

On 03/14/11 16:03, Jan Beulich wrote:
>>>> On 14.03.11 at 15:39, Juergen Gross<juergen.gross@ts.fujitsu.com>  wrote:
>> On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
>> with credit scheduler. Avoid this loop by changing the interface of pick_cpu
>> to indicate a repeated call in this case.
>
> But you're not changing in any way the loop that doesn't get
> exited - did you perhaps read my original description as the
> pick function itself looping (which - afaict - it doesn't)?

I'm changing the way the pick_cpu function is reacting on multiple calls in
a loop. If I've understood the idle_bias correctly, updating it in each
loop iteration did result in returning another cpu for each call.
By updating idle_bias only once, it should return the same cpu in subsequent
calls. This should exit the loop in vcpu_migrate.

> Further, the change still isn't consistent with idle_bias - the
> updating ought to happen on the last iteration (if you need
> to call the function more than once), not the first one, which
> creates a chicken-and-egg problem for you as you will know
> it's the last one only when it returned.

Is it really so important idle_bias is reflecting the last cpu selected?
I was under the impression it should be okay when this is true in most
cases. With my patch idle_bias might be "wrong" if there is a race with
other cpus forcing a selection of a different cpu in the second iteration
of the loop in vcpu_migrate. Is this really critical? I doubt it.


Juergen

-- 
Juergen Gross                 Principal Developer Operating Systems
TSP ES&S SWE OS6                       Telephone: +49 (0) 89 3222 2967
Fujitsu Technology Solutions              e-mail: juergen.gross@ts.fujitsu.com
Domagkstr. 28                           Internet: ts.fujitsu.com
D-80807 Muenchen                 Company details: ts.fujitsu.com/imprint.html

Re: [PATCH] Avoid endless loop for vcpu migration

[Jan Beulich]

>>> On 15.03.11 at 06:50, Juergen Gross <juergen.gross@ts.fujitsu.com> wrote:
> On 03/14/11 16:03, Jan Beulich wrote:
>>>>> On 14.03.11 at 15:39, Juergen Gross<juergen.gross@ts.fujitsu.com>  wrote:
>>> On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
>>> with credit scheduler. Avoid this loop by changing the interface of pick_cpu
>>> to indicate a repeated call in this case.
>>
>> But you're not changing in any way the loop that doesn't get
>> exited - did you perhaps read my original description as the
>> pick function itself looping (which - afaict - it doesn't)?
> 
> I'm changing the way the pick_cpu function is reacting on multiple calls in
> a loop. If I've understood the idle_bias correctly, updating it in each
> loop iteration did result in returning another cpu for each call.
> By updating idle_bias only once, it should return the same cpu in subsequent
> calls. This should exit the loop in vcpu_migrate.

You're only decreasing the likelihood of a live lock, as the return
value of pick_cpu not only depends on idle_bias.

>> Further, the change still isn't consistent with idle_bias - the
>> updating ought to happen on the last iteration (if you need
>> to call the function more than once), not the first one, which
>> creates a chicken-and-egg problem for you as you will know
>> it's the last one only when it returned.
> 
> Is it really so important idle_bias is reflecting the last cpu selected?
> I was under the impression it should be okay when this is true in most
> cases. With my patch idle_bias might be "wrong" if there is a race with
> other cpus forcing a selection of a different cpu in the second iteration
> of the loop in vcpu_migrate. Is this really critical? I doubt it.

It's not critical, and not affecting correctness. But with updating
idle_bias on the first invocation you're (on the right hardware)
basically guaranteeing the second invocation to return a
different CPU. That way, your loop will be run minimally three
times on such systems. I already find it odd to require two
iterations when previously this was a strait code path.

If there's really no way around the iterative approach, one
possibility might be to not take into consideration idle_bias
on non-initial invocations at all.

Jan

Re: [PATCH] Avoid endless loop for vcpu migration

[Juergen Gross]

[-- Attachment #1: Type: text/plain, Size: 3204 bytes --]

On 03/15/11 08:57, Jan Beulich wrote:
>>>> On 15.03.11 at 06:50, Juergen Gross<juergen.gross@ts.fujitsu.com>  wrote:
>> On 03/14/11 16:03, Jan Beulich wrote:
>>>>>> On 14.03.11 at 15:39, Juergen Gross<juergen.gross@ts.fujitsu.com>   wrote:
>>>> On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
>>>> with credit scheduler. Avoid this loop by changing the interface of pick_cpu
>>>> to indicate a repeated call in this case.
>>>
>>> But you're not changing in any way the loop that doesn't get
>>> exited - did you perhaps read my original description as the
>>> pick function itself looping (which - afaict - it doesn't)?
>>
>> I'm changing the way the pick_cpu function is reacting on multiple calls in
>> a loop. If I've understood the idle_bias correctly, updating it in each
>> loop iteration did result in returning another cpu for each call.
>> By updating idle_bias only once, it should return the same cpu in subsequent
>> calls. This should exit the loop in vcpu_migrate.
>
> You're only decreasing the likelihood of a live lock, as the return
> value of pick_cpu not only depends on idle_bias.

Hmm, then another solution would be to let pick_cpu really return the
proposed cpu from the first iteration, if it doesn't contradict the
allowed settings. It could be sub-optimal, but I don't think this is
critical, as vcpu_migrate is called rarely.

Patch attached.

>
>>> Further, the change still isn't consistent with idle_bias - the
>>> updating ought to happen on the last iteration (if you need
>>> to call the function more than once), not the first one, which
>>> creates a chicken-and-egg problem for you as you will know
>>> it's the last one only when it returned.
>>
>> Is it really so important idle_bias is reflecting the last cpu selected?
>> I was under the impression it should be okay when this is true in most
>> cases. With my patch idle_bias might be "wrong" if there is a race with
>> other cpus forcing a selection of a different cpu in the second iteration
>> of the loop in vcpu_migrate. Is this really critical? I doubt it.
>
> It's not critical, and not affecting correctness. But with updating
> idle_bias on the first invocation you're (on the right hardware)
> basically guaranteeing the second invocation to return a
> different CPU. That way, your loop will be run minimally three
> times on such systems. I already find it odd to require two
> iterations when previously this was a strait code path.

This was wrong. It was always required to hold the schedule lock of the
picked cpu as well, otherwise a race with cpu hotplug would be possible.

>
> If there's really no way around the iterative approach, one
> possibility might be to not take into consideration idle_bias
> on non-initial invocations at all.

This would be a side effect of my suggestion.


Juergen

-- 
Juergen Gross                 Principal Developer Operating Systems
TSP ES&S SWE OS6                       Telephone: +49 (0) 89 3222 2967
Fujitsu Technology Solutions              e-mail: juergen.gross@ts.fujitsu.com
Domagkstr. 28                           Internet: ts.fujitsu.com
D-80807 Muenchen                 Company details: ts.fujitsu.com/imprint.html

[-- Attachment #2: vcpu_migrate.patch --]
[-- Type: text/x-patch, Size: 5033 bytes --]

diff -r 9f6dec0d25cd xen/common/sched_arinc653.c
--- a/xen/common/sched_arinc653.c	Mon Mar 14 17:20:11 2011 +0000
+++ b/xen/common/sched_arinc653.c	Tue Mar 15 09:39:10 2011 +0100
@@ -612,7 +612,7 @@ a653sched_do_schedule(
  * @return          Number of selected physical CPU
  */
 static int
-a653sched_pick_cpu(const struct scheduler *ops, struct vcpu *vc)
+a653sched_pick_cpu(const struct scheduler *ops, struct vcpu *vc, int proposal)
 {
     /* this implementation only supports one physical CPU */
     return 0;
diff -r 9f6dec0d25cd xen/common/sched_credit.c
--- a/xen/common/sched_credit.c	Mon Mar 14 17:20:11 2011 +0000
+++ b/xen/common/sched_credit.c	Tue Mar 15 09:39:10 2011 +0100
@@ -459,7 +459,7 @@ __csched_vcpu_is_migrateable(struct vcpu
 }
 
 static int
-_csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc, bool_t commit)
+_csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc, int proposal, bool_t commit)
 {
     cpumask_t cpus;
     cpumask_t idlers;
@@ -473,6 +473,10 @@ _csched_cpu_pick(const struct scheduler 
      */
     online = CSCHED_CPUONLINE(vc->domain->cpupool);
     cpus_and(cpus, *online, vc->cpu_affinity);
+
+    if ( (proposal >= 0) && cpu_isset(proposal, *online) )
+        return proposal;
+
     cpu = cpu_isset(vc->processor, cpus)
             ? vc->processor
             : cycle_cpu(vc->processor, cpus);
@@ -548,9 +552,9 @@ _csched_cpu_pick(const struct scheduler 
 }
 
 static int
-csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc)
+csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc, int proposal)
 {
-    return _csched_cpu_pick(ops, vc, 1);
+    return _csched_cpu_pick(ops, vc, proposal, 1);
 }
 
 static inline void
@@ -635,7 +639,7 @@ csched_vcpu_acct(struct csched_private *
     {
         __csched_vcpu_acct_start(prv, svc);
     }
-    else if ( _csched_cpu_pick(ops, current, 0) != cpu )
+    else if ( _csched_cpu_pick(ops, current, -1, 0) != cpu )
     {
         CSCHED_VCPU_STAT_CRANK(svc, migrate_r);
         CSCHED_STAT_CRANK(migrate_running);
diff -r 9f6dec0d25cd xen/common/sched_credit2.c
--- a/xen/common/sched_credit2.c	Mon Mar 14 17:20:11 2011 +0000
+++ b/xen/common/sched_credit2.c	Tue Mar 15 09:39:10 2011 +0100
@@ -1350,7 +1350,7 @@ out:
 }
 
 static int
-csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc)
+csched_cpu_pick(const struct scheduler *ops, struct vcpu *vc, int proposal)
 {
     struct csched_vcpu * const svc = CSCHED_VCPU(vc);
     int new_cpu;
diff -r 9f6dec0d25cd xen/common/sched_sedf.c
--- a/xen/common/sched_sedf.c	Mon Mar 14 17:20:11 2011 +0000
+++ b/xen/common/sched_sedf.c	Tue Mar 15 09:39:10 2011 +0100
@@ -442,13 +442,15 @@ static void sedf_destroy_domain(const st
     sedf_free_domdata(ops, d->sched_priv);
 }
 
-static int sedf_pick_cpu(const struct scheduler *ops, struct vcpu *v)
+static int sedf_pick_cpu(const struct scheduler *ops, struct vcpu *v, int proposal)
 {
     cpumask_t online_affinity;
     cpumask_t *online;
 
     online = SEDF_CPUONLINE(v->domain->cpupool);
     cpus_and(online_affinity, v->cpu_affinity, *online);
+    if ( (proposal >= 0) && cpu_isset(proposal, online_affinity) )
+        return proposal;
     return first_cpu(online_affinity);
 }
 
diff -r 9f6dec0d25cd xen/common/schedule.c
--- a/xen/common/schedule.c	Mon Mar 14 17:20:11 2011 +0000
+++ b/xen/common/schedule.c	Tue Mar 15 09:39:10 2011 +0100
@@ -393,9 +393,10 @@ static void vcpu_migrate(struct vcpu *v)
 static void vcpu_migrate(struct vcpu *v)
 {
     unsigned long flags;
-    unsigned int old_cpu, new_cpu;
+    unsigned int old_cpu, new_cpu, proposal;
     spinlock_t *old_lock, *new_lock;
 
+    proposal = -1;
     old_cpu = new_cpu = v->processor;
     for ( ; ; )
     {
@@ -430,10 +431,11 @@ static void vcpu_migrate(struct vcpu *v)
         old_cpu = v->processor;
         if ( old_lock == per_cpu(schedule_data, old_cpu).schedule_lock )
         {
-            new_cpu = SCHED_OP(VCPU2OP(v), pick_cpu, v);
+            new_cpu = SCHED_OP(VCPU2OP(v), pick_cpu, v, proposal);
             if ( (new_lock == per_cpu(schedule_data, new_cpu).schedule_lock) &&
                  cpu_isset(new_cpu, v->domain->cpupool->cpu_valid) )
                 break;
+            proposal = new_cpu;
         }
 
         if ( old_lock != new_lock )
diff -r 9f6dec0d25cd xen/include/xen/sched-if.h
--- a/xen/include/xen/sched-if.h	Mon Mar 14 17:20:11 2011 +0000
+++ b/xen/include/xen/sched-if.h	Tue Mar 15 09:39:10 2011 +0100
@@ -167,7 +167,7 @@ struct scheduler {
     struct task_slice (*do_schedule) (const struct scheduler *, s_time_t,
                                       bool_t tasklet_work_scheduled);
 
-    int          (*pick_cpu)       (const struct scheduler *, struct vcpu *);
+    int          (*pick_cpu)       (const struct scheduler *, struct vcpu *, int);
     int          (*adjust)         (const struct scheduler *, struct domain *,
                                     struct xen_domctl_scheduler_op *);
     int          (*adjust_global)  (const struct scheduler *,

[-- Attachment #3: Type: text/plain, Size: 138 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Re: [PATCH] Avoid endless loop for vcpu migration

[Keir Fraser]

On 15/03/2011 08:46, "Juergen Gross" <juergen.gross@ts.fujitsu.com> wrote:

>> It's not critical, and not affecting correctness. But with updating
>> idle_bias on the first invocation you're (on the right hardware)
>> basically guaranteeing the second invocation to return a
>> different CPU. That way, your loop will be run minimally three
>> times on such systems. I already find it odd to require two
>> iterations when previously this was a strait code path.
> 
> This was wrong. It was always required to hold the schedule lock of the
> picked cpu as well, otherwise a race with cpu hotplug would be possible.

What would that race be? CPU offlining is done in stop_machine context.

 -- Keir

Re: [PATCH] Avoid endless loop for vcpu migration

[Juergen Gross]

On 03/15/11 09:50, Keir Fraser wrote:
> On 15/03/2011 08:46, "Juergen Gross"<juergen.gross@ts.fujitsu.com>  wrote:
>
>>> It's not critical, and not affecting correctness. But with updating
>>> idle_bias on the first invocation you're (on the right hardware)
>>> basically guaranteeing the second invocation to return a
>>> different CPU. That way, your loop will be run minimally three
>>> times on such systems. I already find it odd to require two
>>> iterations when previously this was a strait code path.
>>
>> This was wrong. It was always required to hold the schedule lock of the
>> picked cpu as well, otherwise a race with cpu hotplug would be possible.
>
> What would that race be? CPU offlining is done in stop_machine context.

Ahh, okay.


Juergen

-- 
Juergen Gross                 Principal Developer Operating Systems
TSP ES&S SWE OS6                       Telephone: +49 (0) 89 3222 2967
Fujitsu Technology Solutions              e-mail: juergen.gross@ts.fujitsu.com
Domagkstr. 28                           Internet: ts.fujitsu.com
D-80807 Muenchen                 Company details: ts.fujitsu.com/imprint.html

Re: [PATCH] Avoid endless loop for vcpu migration

[Jan Beulich]

>>> On 15.03.11 at 09:46, Juergen Gross <juergen.gross@ts.fujitsu.com> wrote:
> On 03/15/11 08:57, Jan Beulich wrote:
>>>>> On 15.03.11 at 06:50, Juergen Gross<juergen.gross@ts.fujitsu.com>  wrote:
>>> On 03/14/11 16:03, Jan Beulich wrote:
>>>>>>> On 14.03.11 at 15:39, Juergen Gross<juergen.gross@ts.fujitsu.com>   wrote:
>>>>> On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
>>>>> with credit scheduler. Avoid this loop by changing the interface of pick_cpu
>>>>> to indicate a repeated call in this case.
>>>>
>>>> But you're not changing in any way the loop that doesn't get
>>>> exited - did you perhaps read my original description as the
>>>> pick function itself looping (which - afaict - it doesn't)?
>>>
>>> I'm changing the way the pick_cpu function is reacting on multiple calls in
>>> a loop. If I've understood the idle_bias correctly, updating it in each
>>> loop iteration did result in returning another cpu for each call.
>>> By updating idle_bias only once, it should return the same cpu in subsequent
>>> calls. This should exit the loop in vcpu_migrate.
>>
>> You're only decreasing the likelihood of a live lock, as the return
>> value of pick_cpu not only depends on idle_bias.
> 
> Hmm, then another solution would be to let pick_cpu really return the
> proposed cpu from the first iteration, if it doesn't contradict the
> allowed settings. It could be sub-optimal, but I don't think this is
> critical, as vcpu_migrate is called rarely.
> 
> Patch attached.

That candidate-is-valid check seems absolutely independent of the
particular scheduler used, and hence could be done in the (sole)
caller, thus not requiring any change to the scheduler interface.

Which at once would eliminate unnecessary calls into pick_cpu (i.e.
you'd call it a second time only if the previously selected CPU really
is no longer valid to be used for that vCPU).

Jan

Re: [PATCH] Avoid endless loop for vcpu migration

[Juergen Gross]

[-- Attachment #1: Type: text/plain, Size: 2401 bytes --]

On 03/15/11 10:01, Jan Beulich wrote:
>>>> On 15.03.11 at 09:46, Juergen Gross<juergen.gross@ts.fujitsu.com>  wrote:
>> On 03/15/11 08:57, Jan Beulich wrote:
>>>>>> On 15.03.11 at 06:50, Juergen Gross<juergen.gross@ts.fujitsu.com>   wrote:
>>>> On 03/14/11 16:03, Jan Beulich wrote:
>>>>>>>> On 14.03.11 at 15:39, Juergen Gross<juergen.gross@ts.fujitsu.com>    wrote:
>>>>>> On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
>>>>>> with credit scheduler. Avoid this loop by changing the interface of pick_cpu
>>>>>> to indicate a repeated call in this case.
>>>>>
>>>>> But you're not changing in any way the loop that doesn't get
>>>>> exited - did you perhaps read my original description as the
>>>>> pick function itself looping (which - afaict - it doesn't)?
>>>>
>>>> I'm changing the way the pick_cpu function is reacting on multiple calls in
>>>> a loop. If I've understood the idle_bias correctly, updating it in each
>>>> loop iteration did result in returning another cpu for each call.
>>>> By updating idle_bias only once, it should return the same cpu in subsequent
>>>> calls. This should exit the loop in vcpu_migrate.
>>>
>>> You're only decreasing the likelihood of a live lock, as the return
>>> value of pick_cpu not only depends on idle_bias.
>>
>> Hmm, then another solution would be to let pick_cpu really return the
>> proposed cpu from the first iteration, if it doesn't contradict the
>> allowed settings. It could be sub-optimal, but I don't think this is
>> critical, as vcpu_migrate is called rarely.
>>
>> Patch attached.
>
> That candidate-is-valid check seems absolutely independent of the
> particular scheduler used, and hence could be done in the (sole)
> caller, thus not requiring any change to the scheduler interface.
>
> Which at once would eliminate unnecessary calls into pick_cpu (i.e.
> you'd call it a second time only if the previously selected CPU really
> is no longer valid to be used for that vCPU).

True.

The patch seems to become smaller :-)


Juergen

-- 
Juergen Gross                 Principal Developer Operating Systems
TSP ES&S SWE OS6                       Telephone: +49 (0) 89 3222 2967
Fujitsu Technology Solutions              e-mail: juergen.gross@ts.fujitsu.com
Domagkstr. 28                           Internet: ts.fujitsu.com
D-80807 Muenchen                 Company details: ts.fujitsu.com/imprint.html

[-- Attachment #2: vcpu_migrate.patch --]
[-- Type: text/x-patch, Size: 1148 bytes --]

diff -r 9f6dec0d25cd xen/common/schedule.c
--- a/xen/common/schedule.c	Mon Mar 14 17:20:11 2011 +0000
+++ b/xen/common/schedule.c	Tue Mar 15 10:19:15 2011 +0100
@@ -395,6 +395,7 @@ static void vcpu_migrate(struct vcpu *v)
     unsigned long flags;
     unsigned int old_cpu, new_cpu;
     spinlock_t *old_lock, *new_lock;
+    int pick_called = 0;
 
     old_cpu = new_cpu = v->processor;
     for ( ; ; )
@@ -430,11 +431,18 @@ static void vcpu_migrate(struct vcpu *v)
         old_cpu = v->processor;
         if ( old_lock == per_cpu(schedule_data, old_cpu).schedule_lock )
         {
+            if ( pick_called && cpu_isset(new_cpu, v->cpu_affinity) &&
+                 cpu_isset(new_cpu, v->domain->cpupool->cpu_valid) )
+                break;
+
             new_cpu = SCHED_OP(VCPU2OP(v), pick_cpu, v);
             if ( (new_lock == per_cpu(schedule_data, new_cpu).schedule_lock) &&
                  cpu_isset(new_cpu, v->domain->cpupool->cpu_valid) )
                 break;
+            pick_called = 1;
         }
+        else
+            pick_called = 0;
 
         if ( old_lock != new_lock )
             spin_unlock(new_lock);

[-- Attachment #3: Type: text/plain, Size: 138 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Re: [PATCH] Avoid endless loop for vcpu migration

[Jan Beulich]

>>> On 15.03.11 at 10:21, Juergen Gross <juergen.gross@ts.fujitsu.com> wrote:
> On 03/15/11 10:01, Jan Beulich wrote:
>>>>> On 15.03.11 at 09:46, Juergen Gross<juergen.gross@ts.fujitsu.com>  wrote:
>>> On 03/15/11 08:57, Jan Beulich wrote:
>>>>>>> On 15.03.11 at 06:50, Juergen Gross<juergen.gross@ts.fujitsu.com>   wrote:
>>>>> On 03/14/11 16:03, Jan Beulich wrote:
>>>>>>>>> On 14.03.11 at 15:39, Juergen Gross<juergen.gross@ts.fujitsu.com>    wrote:
>>>>>>> On multi-thread multi-core systems an endless loop can occur in vcpu_migrate()
>>>>>>> with credit scheduler. Avoid this loop by changing the interface of pick_cpu
>>>>>>> to indicate a repeated call in this case.
>>>>>>
>>>>>> But you're not changing in any way the loop that doesn't get
>>>>>> exited - did you perhaps read my original description as the
>>>>>> pick function itself looping (which - afaict - it doesn't)?
>>>>>
>>>>> I'm changing the way the pick_cpu function is reacting on multiple calls in
>>>>> a loop. If I've understood the idle_bias correctly, updating it in each
>>>>> loop iteration did result in returning another cpu for each call.
>>>>> By updating idle_bias only once, it should return the same cpu in subsequent
>>>>> calls. This should exit the loop in vcpu_migrate.
>>>>
>>>> You're only decreasing the likelihood of a live lock, as the return
>>>> value of pick_cpu not only depends on idle_bias.
>>>
>>> Hmm, then another solution would be to let pick_cpu really return the
>>> proposed cpu from the first iteration, if it doesn't contradict the
>>> allowed settings. It could be sub-optimal, but I don't think this is
>>> critical, as vcpu_migrate is called rarely.
>>>
>>> Patch attached.
>>
>> That candidate-is-valid check seems absolutely independent of the
>> particular scheduler used, and hence could be done in the (sole)
>> caller, thus not requiring any change to the scheduler interface.
>>
>> Which at once would eliminate unnecessary calls into pick_cpu (i.e.
>> you'd call it a second time only if the previously selected CPU really
>> is no longer valid to be used for that vCPU).
> 
> True.
> 
> The patch seems to become smaller :-)

This looks good to me now, and it makes quite obvious that there
is a likely exit path from the loop (it can only live lock now if
v->cpu_affinity and/or v->domain->cpupool->cpu_valid are
constantly changing, which could only be due to a misbehaving
administrator).

Jan

Re: [PATCH] Avoid endless loop for vcpu migration

[Keir Fraser]

On 15/03/2011 09:21, "Juergen Gross" <juergen.gross@ts.fujitsu.com> wrote:

>> That candidate-is-valid check seems absolutely independent of the
>> particular scheduler used, and hence could be done in the (sole)
>> caller, thus not requiring any change to the scheduler interface.
>> 
>> Which at once would eliminate unnecessary calls into pick_cpu (i.e.
>> you'd call it a second time only if the previously selected CPU really
>> is no longer valid to be used for that vCPU).
> 
> True.
> 
> The patch seems to become smaller :-)

By the way, why is the cpu_isset(new_cpu, v->domain->vcpupool->cpu_valid)
check required (after calling pick_cpu, in the cuirrently checked-in code)?
You already check that pick_cpu was called holding the correct pair of
locks, if it has returned a cpu that is not in the pool's cpu_valid mask,
what would make pick_cpu return anything different on the next invocation
thus avoiding an endless loop?

Looks like this question would remain even if this new patch was applied.

 -- Keir

Re: [PATCH] Avoid endless loop for vcpu migration

[Juergen Gross]

On 03/15/11 10:58, Keir Fraser wrote:
> On 15/03/2011 09:21, "Juergen Gross"<juergen.gross@ts.fujitsu.com>  wrote:
>
>>> That candidate-is-valid check seems absolutely independent of the
>>> particular scheduler used, and hence could be done in the (sole)
>>> caller, thus not requiring any change to the scheduler interface.
>>>
>>> Which at once would eliminate unnecessary calls into pick_cpu (i.e.
>>> you'd call it a second time only if the previously selected CPU really
>>> is no longer valid to be used for that vCPU).
>>
>> True.
>>
>> The patch seems to become smaller :-)
>
> By the way, why is the cpu_isset(new_cpu, v->domain->vcpupool->cpu_valid)
> check required (after calling pick_cpu, in the cuirrently checked-in code)?

Good question. It shouldn't be required, as pick_cpu should check this and
should return only cpus in the current cpupool. With the latest patches from
Jan this seems to be true. :-)
I think I'll send a separate patch to remove the check.

> You already check that pick_cpu was called holding the correct pair of
> locks, if it has returned a cpu that is not in the pool's cpu_valid mask,
> what would make pick_cpu return anything different on the next invocation
> thus avoiding an endless loop?

Nothing. If pick_cpu is returning a cpu outside of it's cpupool, the loop
could be infinite. Inserting a BUG_ON would be a good idea, but this would
require a bit more logic, as a cpu might be removed from the cpupool during
a running vcpu_migrate (this case is handled by the call of
cpu_disable_scheduler() during removing a cpu from a cpupool).


Juergen

-- 
Juergen Gross                 Principal Developer Operating Systems
TSP ES&S SWE OS6                       Telephone: +49 (0) 89 3222 2967
Fujitsu Technology Solutions              e-mail: juergen.gross@ts.fujitsu.com
Domagkstr. 28                           Internet: ts.fujitsu.com
D-80807 Muenchen                 Company details: ts.fujitsu.com/imprint.html