Xen devel - Dec 2009 - [PATCH] [RFC] Credit2 scheduler prototype

I''m attaching patches for the rudimentary new credit2 scheduler which
I discussed at the Summit.  It''s definitely still at a developmental
stage, but it''s in a state where people should be able to contribute
now.

I''ve put up a wiki page to help coordinate development here:
 http://wiki.xensource.com/xenwiki/Credit2_Scheduler_Development

Some caveats:
* There is no inter-socket load balancing.  This is one of the work
items to be done.
* It works on my 2-core box, but deadlocks on my 4-core box; cause
still to be determined.

The wiki page lists a number of semi-independent lines of development
that people can take.  Let me know if you''re interested in any of
them, and if you have any questions, and I can elaborate.

Keir (and everyone), I think at this point it would be a good idea to
start a credit2 development branch in ext/ so we can keep a revision
history.  Thoughts?

 -George



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

On 07/12/2009 17:02, "George Dunlap"
<George.Dunlap@eu.citrix.com> wrote:
> Keir (and everyone), I think at this point it would be a good idea to
> start a credit2 development branch in ext/ so we can keep a revision
> history.  Thoughts?
Sounds like a reasonable idea, if you don''t think it suitable just to
check
into mainline as the non-default scheduler.

 -- Keir



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

My main concern is that sharing the runqueue between cores requires
some changes to the core context switch code. The kinks aren''t 100%
worked out yet, so there''s a risk that there will be an impact on the
correctness of the credit1 scheduler.

If you want to go that route, we should probably talk about the
changes we want to the context switch path first, and check that in as
a separate patch, before checking in the core scheduler code.

Or we could just check it in and sort it out as things go, since this
is -unstable. :-)

Thoughts?

Either way I''ll write up an e-mail describing some of the scheduler
path changes I''d like to see.

 -George



On Mon, Dec 7, 2009 at 5:45 PM, Keir Fraser <keir.fraser@eu.citrix.com>
wrote:
> On 07/12/2009 17:02, "George Dunlap"
<George.Dunlap@eu.citrix.com> wrote:
>
>> Keir (and everyone), I think at this point it would be a good idea to
>> start a credit2 development branch in ext/ so we can keep a revision
>> history.  Thoughts?
>
> Sounds like a reasonable idea, if you don''t think it suitable just
to check
> into mainline as the non-default scheduler.
>
>  -- Keir
>
>
>
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com
> http://lists.xensource.com/xen-devel
>
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

On 08/12/2009 14:48, "George Dunlap"
<George.Dunlap@eu.citrix.com> wrote:
> My main concern is that sharing the runqueue between cores requires
> some changes to the core context switch code. The kinks aren''t
100%
> worked out yet, so there''s a risk that there will be an impact on
the
> correctness of the credit1 scheduler.
Ah, if that''s the problem with selecting a vcpu which happens to still
be
''is_running'' then I had some ideas how you could deal with
that within the
credit2 scheduler. If you see such a vcpu when searching the runqueue,
ignore it, but set VPF_migrating. You''ll then get a
''pick_cpu'' callback when
descheduling of the vcpu is completed. That should play nice with the lazy
context switch logic while keeping things work conserving.

 -- Keir



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

Keir,

What do you think of the attached patches?

The first implements something like what you suggest below, but
instead of using a sort of "hack" with VPF_migrate, it makes a proper
"context_saved" SCHED_OP callback.

The second addresses the fact that when sharing runqueues,
v->processor may change quickly without an explicit migrate.

The last two are the credit2 hypervisor and tool patches, which use
these two changes (for reference).

I think these patches should be basically NOOP for the existing
schedulers, so as far as I''m concerned they''re ready to be
merged as
soon as you''re happy with them.

Peace,
 -George

On Tue, Dec 8, 2009 at 6:20 PM, Keir Fraser <keir.fraser@eu.citrix.com>
wrote:
> On 08/12/2009 14:48, "George Dunlap"
<George.Dunlap@eu.citrix.com> wrote:
>
>> My main concern is that sharing the runqueue between cores requires
>> some changes to the core context switch code. The kinks aren''t
100%
>> worked out yet, so there''s a risk that there will be an impact
on the
>> correctness of the credit1 scheduler.
>
> Ah, if that''s the problem with selecting a vcpu which happens to
still be
> ''is_running'' then I had some ideas how you could deal
with that within the
> credit2 scheduler. If you see such a vcpu when searching the runqueue,
> ignore it, but set VPF_migrating. You''ll then get a
''pick_cpu'' callback when
> descheduling of the vcpu is completed. That should play nice with the lazy
> context switch logic while keeping things work conserving.
>
>  -- Keir
>
>
>
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com
> http://lists.xensource.com/xen-devel
>




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

On 13/01/2010 14:48, "George Dunlap"
<George.Dunlap@eu.citrix.com> wrote:
> The first implements something like what you suggest below, but
> instead of using a sort of "hack" with VPF_migrate, it makes a
proper
> "context_saved" SCHED_OP callback.
I thought using the vcpu_migrate() path might work well since you presumably
have logic there to pick a new cpu which is relatively unloaded, making the
cpu which tried to schedule the vcpu but had to idle instead a prime
candidate. So rather than having to implement a new callback hook,
you''d get
to leverage the pick_cpu hook for free?
> The second addresses the fact that when sharing runqueues,
> v->processor may change quickly without an explicit migrate.
I can''t think of a better solution for this one.

 -- Keir



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

On Wed, Jan 13, 2010 at 3:16 PM, Keir Fraser <keir.fraser@eu.citrix.com>
wrote:
> On 13/01/2010 14:48, "George Dunlap"
<George.Dunlap@eu.citrix.com> wrote:
>
>> The first implements something like what you suggest below, but
>> instead of using a sort of "hack" with VPF_migrate, it makes
a proper
>> "context_saved" SCHED_OP callback.
>
> I thought using the vcpu_migrate() path might work well since you
presumably
> have logic there to pick a new cpu which is relatively unloaded, making the
> cpu which tried to schedule the vcpu but had to idle instead a prime
> candidate. So rather than having to implement a new callback hook,
you''d get
> to leverage the pick_cpu hook for free?
Hmm, not sure that actually gives us the leverage we need to solve all
the races.  If you look at sched_credit2.c (in the credit2-hypervisor
patch), you''ll see I added two flags to the private vcpu struct: one
to indicate that the vcpu has (or may have) context somewhere on a
cpu, and thus can''t be added to the runqueue; another to indicate that
when the first flag is cleared, it should be added to the runqueue.
In the current implementation, the first flag is set and cleared every
time a vcpu is scheduled or descheduled, whether it needs to be added
to the runqueue after context_saved() or not.

[NB that the current global lock will eventually be replaced with
per-runqueue locks.]

In particular, one of the races without the first flag looks like this
(brackets indicate physical cpu):
[0] lock cpu0 schedule lock
[0] lock credit2 runqueue lock
[0] Take vX off runqueue; vX->processor == 1
[0] unlock credit2 runqueue lock
[1] vcpu_wake(vX) lock cpu1 schedule lock
[1] finds vX->running false, adds it to the runqueue
[1] unlock cpu1 schedule_lock
[0] vX->running=1
[0] unlock cpu0 schedule lock
[0] lock cpu1 schedule lock (vX->cpu == 1)
[0] vX->cpu = 0
[0] unlock cpu1 schedule lock
[1] takes vX from the runqueue, finds vX->running is true *ERROR*

I guess the real problem here is that vX->running is set even though
the vX->processor schedule lock isn''t held, causing a race with
vcpu_wake().  In the other schedulers this can''t happen, since it
takes an explicit migrate to change processors.  In the attached
patches, csched2 operations serialize on the runqueue lock, fixing
that particular race.

Can''t think of a better solution off the top of my head; I''ll
give it
some thought.

 -George

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

On 13/01/2010 16:05, "George Dunlap"
<George.Dunlap@eu.citrix.com> wrote:
> [NB that the current global lock will eventually be replaced with
> per-runqueue locks.]
> 
> In particular, one of the races without the first flag looks like this
> (brackets indicate physical cpu):
> [0] lock cpu0 schedule lock
> [0] lock credit2 runqueue lock
> [0] Take vX off runqueue; vX->processor == 1
> [0] unlock credit2 runqueue lock
> [1] vcpu_wake(vX) lock cpu1 schedule lock
> [1] finds vX->running false, adds it to the runqueue
> [1] unlock cpu1 schedule_lock
Actually, hang on. Doesn''t this issue, and the one that your second
patch
addresses, go away if we change the schedule_lock granularity to match
runqueue granularity? That would seem pretty sensible, and could be
implemented with a schedule_lock(cpu) scheduler hook, returning a
spinlock_t*, and a some easy scheduler code changes.

If we do that, do you then even need separate private per-runqueue locks?
(Just an extra thought).

 -- Keir



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

Keir Fraser wrote:
> On 13/01/2010 16:05, "George Dunlap"
<George.Dunlap@eu.citrix.com> wrote:
>
>   
>> [NB that the current global lock will eventually be replaced with
>> per-runqueue locks.]
>>
>> In particular, one of the races without the first flag looks like this
>> (brackets indicate physical cpu):
>> [0] lock cpu0 schedule lock
>> [0] lock credit2 runqueue lock
>> [0] Take vX off runqueue; vX->processor == 1
>> [0] unlock credit2 runqueue lock
>> [1] vcpu_wake(vX) lock cpu1 schedule lock
>> [1] finds vX->running false, adds it to the runqueue
>> [1] unlock cpu1 schedule_lock
>>     
>
> Actually, hang on. Doesn''t this issue, and the one that your
second patch
> addresses, go away if we change the schedule_lock granularity to match
> runqueue granularity? That would seem pretty sensible, and could be
> implemented with a schedule_lock(cpu) scheduler hook, returning a
> spinlock_t*, and a some easy scheduler code changes.
>
> If we do that, do you then even need separate private per-runqueue locks?
> (Just an extra thought).
>   
Hmm.... can''t see anything wrong with it.  It would make the whole 
locking discipline thing a lot simpler.  It would, AFAICT, remove the 
need for private per-runqueue locks, which make it a lot harder to avoid 
deadlock without these sorts of strange tricks. :-)

I''ll think about it, and probably give it a spin to see how it works
out.

 -George

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

George,

With your patches and sched=credit2, xen crashes on a failed assertion :
(XEN) ****************************************
(XEN) Panic on CPU 1:
(XEN) Assertion ''_spin_is_locked(&(*({ unsigned long __ptr; __asm__
("" : "=r"(*
(XEN)

Is this version supposed to work (or is it just some reference code) ?

thanks
dulloor


On Wed, Jan 13, 2010 at 11:43 AM, George Dunlap
<george.dunlap@eu.citrix.com> wrote:
> Keir Fraser wrote:
>>
>> On 13/01/2010 16:05, "George Dunlap"
<George.Dunlap@eu.citrix.com> wrote:
>>
>>
>>>
>>> [NB that the current global lock will eventually be replaced with
>>> per-runqueue locks.]
>>>
>>> In particular, one of the races without the first flag looks like
this
>>> (brackets indicate physical cpu):
>>> [0] lock cpu0 schedule lock
>>> [0] lock credit2 runqueue lock
>>> [0] Take vX off runqueue; vX->processor == 1
>>> [0] unlock credit2 runqueue lock
>>> [1] vcpu_wake(vX) lock cpu1 schedule lock
>>> [1] finds vX->running false, adds it to the runqueue
>>> [1] unlock cpu1 schedule_lock
>>>
>>
>> Actually, hang on. Doesn''t this issue, and the one that your
second patch
>> addresses, go away if we change the schedule_lock granularity to match
>> runqueue granularity? That would seem pretty sensible, and could be
>> implemented with a schedule_lock(cpu) scheduler hook, returning a
>> spinlock_t*, and a some easy scheduler code changes.
>>
>> If we do that, do you then even need separate private per-runqueue
locks?
>> (Just an extra thought).
>>
>
> Hmm.... can''t see anything wrong with it.  It would make the whole
locking
> discipline thing a lot simpler.  It would, AFAICT, remove the need for
> private per-runqueue locks, which make it a lot harder to avoid deadlock
> without these sorts of strange tricks. :-)
>
> I''ll think about it, and probably give it a spin to see how it
works out.
>
> -George
>
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com
> http://lists.xensource.com/xen-devel
>
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel

Since it''s an assertion, I assume you ran it with debug=y?

I''m definitely changing some assumptions with this, so it''s
not a
surprise that some assertions trigger.

I''m working on a modified version based on the discussion we had here;
I''ll post a patch (tested with debug=y) when I''m done.

-George

On Thu, Jan 28, 2010 at 11:27 PM, Dulloor <dulloor@gmail.com>
wrote:
> George,
>
> With your patches and sched=credit2, xen crashes on a failed assertion :
> (XEN) ****************************************
> (XEN) Panic on CPU 1:
> (XEN) Assertion ''_spin_is_locked(&(*({ unsigned long __ptr;
__asm__ ("" : "=r"(*
> (XEN)
>
> Is this version supposed to work (or is it just some reference code) ?
>
> thanks
> dulloor
>
>
> On Wed, Jan 13, 2010 at 11:43 AM, George Dunlap
> <george.dunlap@eu.citrix.com> wrote:
>> Keir Fraser wrote:
>>>
>>> On 13/01/2010 16:05, "George Dunlap"
<George.Dunlap@eu.citrix.com> wrote:
>>>
>>>
>>>>
>>>> [NB that the current global lock will eventually be replaced
with
>>>> per-runqueue locks.]
>>>>
>>>> In particular, one of the races without the first flag looks
like this
>>>> (brackets indicate physical cpu):
>>>> [0] lock cpu0 schedule lock
>>>> [0] lock credit2 runqueue lock
>>>> [0] Take vX off runqueue; vX->processor == 1
>>>> [0] unlock credit2 runqueue lock
>>>> [1] vcpu_wake(vX) lock cpu1 schedule lock
>>>> [1] finds vX->running false, adds it to the runqueue
>>>> [1] unlock cpu1 schedule_lock
>>>>
>>>
>>> Actually, hang on. Doesn''t this issue, and the one that
your second patch
>>> addresses, go away if we change the schedule_lock granularity to
match
>>> runqueue granularity? That would seem pretty sensible, and could be
>>> implemented with a schedule_lock(cpu) scheduler hook, returning a
>>> spinlock_t*, and a some easy scheduler code changes.
>>>
>>> If we do that, do you then even need separate private per-runqueue
locks?
>>> (Just an extra thought).
>>>
>>
>> Hmm.... can''t see anything wrong with it.  It would make the
whole locking
>> discipline thing a lot simpler.  It would, AFAICT, remove the need for
>> private per-runqueue locks, which make it a lot harder to avoid
deadlock
>> without these sorts of strange tricks. :-)
>>
>> I''ll think about it, and probably give it a spin to see how it
works out.
>>
>> -George
>>
>> _______________________________________________
>> Xen-devel mailing list
>> Xen-devel@lists.xensource.com
>> http://lists.xensource.com/xen-devel
>>
>
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xensource.com
> http://lists.xensource.com/xen-devel
>
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel