Xen devel - May 2005 - ac_timer: time to say goodbye?

It appears that the ac_timer code is not used very much
anymore.  (Not that it''s not used at all, just not very
much... grep for ac_timer.)  It''s kind of a heavyweight
mechanism for a hypervisor... I wonder if it might be
possible to dispense with it entirely?

The reason I ask now is that, as part of the ia64 CONFIG_VTI
checkin, some new timer code got added that makes use
of ac_timer and I''m concerned that this might be a step in the
wrong direction.

As domains more completely manage their own timer interrupts,
the only use for time in Xen itself is for time-slicing
domains, correct?

Should ac_timer be removed and replaced by a lighter weight
mechanism, or at least its use deprecated?

Comments welcome.

Dan


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

On 23 May 2005, at 20:59, Magenheimer, Dan (HP Labs Fort Collins) wrote:
> Should ac_timer be removed and replaced by a lighter weight
> mechanism, or at least its use deprecated?
What''s heavyweight about it? We can maybe slim down the interface a 
little, but we need a mechanism for managing at least an alarm timeout 
per vcpu. I don''t imagine anyhting much simpler than ac_timer would 
really fit the bill.

  -- Keir


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

> It appears that the ac_timer code is not used very much 
> anymore.  (Not that it''s not used at all, just not very 
> much... grep for ac_timer.)  It''s kind of a heavyweight 
> mechanism for a hypervisor... I wonder if it might be 
> possible to dispense with it entirely?
> 
> The reason I ask now is that, as part of the ia64 CONFIG_VTI 
> checkin, some new timer code got added that makes use of 
> ac_timer and I''m concerned that this might be a step in the 
> wrong direction.
> 
> As domains more completely manage their own timer interrupts, 
> the only use for time in Xen itself is for time-slicing 
> domains, correct?
> 
> Should ac_timer be removed and replaced by a lighter weight 
> mechanism, or at least its use deprecated?
Heavy weight? It''s a basic heap (priority queue) implementation. 
Seems to me like a perfectly sensible thing to have in a hypervisor, and
its used extensively by all the schedulers.

Thanks,
Ian


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

> What''s heavyweight about it? We can maybe slim down the interface
a
> little, but we need a mechanism for managing at least an 
> alarm timeout 
> per vcpu. I don''t imagine anyhting much simpler than ac_timer
would
> really fit the bill.
> 
>   -- Keir
>
> Heavy weight? It''s a basic heap (priority queue) implementation. 
> Seems to me like a perfectly sensible thing to have in a 
> hypervisor, and
> its used extensively by all the schedulers.
> 
> Thanks,
> Ian
I can''t say I fully understand the code and usage, so I may
be missing something, but...

Is there ever any more than one or two elements in the queue?
What is the total set of functions called by the queue?
> its used extensively by all the schedulers.
Try ''grep -r ac_timer'' and see.

I suspect that the whole functionality of it can be replaced
with a couple of time variables that are checked and
manipulated in the timer interrupt code and a single
scheduler/timer routine in the generic scheduler.

The queueing mechanism is nice if there are a lot of uses,
but confusing (and IMHO heavyweight) if not.  I suspect
the generalized mechanism was good when there was more
functionality in Xen itself but as more and more migrates
to domain0, if the remaining usage could be replaced by
a couple variables, perhaps it should.

Not urgent, but if this is the right direction, we shouldn''t
be layering more code on top of it (thus the suggestion of
deprecating it).

Dan

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

On 23/5/05 9:28 pm, "Magenheimer, Dan (HP Labs Fort Collins)"
<dan.magenheimer@hp.com> wrote:
>> What''s heavyweight about it? We can maybe slim down the
interface a
>> little, but we need a mechanism for managing at least an
>> alarm timeout 
>> per vcpu. I don''t imagine anyhting much simpler than ac_timer
would
>> really fit the bill.
>> 
>>   -- Keir
>> 
>> Heavy weight? It''s a basic heap (priority queue)
implementation.
>> Seems to me like a perfectly sensible thing to have in a
>> hypervisor, and
>> its used extensively by all the schedulers.
>> 
>> Thanks,
>> Ian
> 
> I can''t say I fully understand the code and usage, so I may
> be missing something, but...
> 
> Is there ever any more than one or two elements in the queue?
> What is the total set of functions called by the queue?
Of the top of my head:
Each domain has a timer to schedule timeout values. So depending on how many
domains are blocking the number of timers varies.
Then there is one timer per vcpu to generate a ticker for the currently
running VM.
> 
>> its used extensively by all the schedulers.
> 
> Try ''grep -r ac_timer'' and see.
As said above every domain has a timer. With grep that probably shows up as
one ;)
> 
> I suspect that the whole functionality of it can be replaced
> with a couple of time variables that are checked and
> manipulated in the timer interrupt code and a single
> scheduler/timer routine in the generic scheduler.
> 
> The queueing mechanism is nice if there are a lot of uses,
> but confusing (and IMHO heavyweight) if not.  I suspect
> the generalized mechanism was good when there was more
> functionality in Xen itself but as more and more migrates
> to domain0, if the remaining usage could be replaced by
> a couple variables, perhaps it should.
What''s confusing about the interface? You set a timeout and a function
to be
called at that timeout. Then there are  functions to modify and remove a
timer. Pretty straightforward.

It would be more confusing if the timer interrupt code would check a bunch
of variables and then figure out the next timeout value.

Given the use, a priority queue seems the best solution. The implementation
is a bit more complicated as due to the use of the softirq (to avoid the
handler being executed in an interrupt context), the timer slop stuff to
avoid unnecessary races and timer interrupts, and the hack to make this work
if no local apic is available. But all that is hidden behind the interface.
> 
> Not urgent, but if this is the right direction, we shouldn''t
> be layering more code on top of it (thus the suggestion of
> deprecating it).
I don''t think this will be deprecated, as Keir said we need at least
one
implementation of a programmable timer.

rolf
> 
> Dan
> 
> _______________________________________________
> 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 23 May 2005, at 21:28, Magenheimer, Dan (HP Labs Fort Collins) wrote:
> I suspect that the whole functionality of it can be replaced
> with a couple of time variables that are checked and
> manipulated in the timer interrupt code and a single
> scheduler/timer routine in the generic scheduler.
We are going to strip out the periodic ticker entirely (at least in 
arch/x86) and have just a programmable one-shot timer. We need to keep 
track of what is the nearest event we care about so we know what to 
program into the one-shot timer.

I think the interface could be simplified a little (fold 
mod_ac_timer/add_ac_timer into a single function, for example), but the 
implementation is already very pared down. I image it would hardly save 
100 lines, or bytes of hypervisor code, to replace the heap with a 
list, for example.

  -- Keir


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

> Of the top of my head:
> Each domain has a timer to schedule timeout values. So 
> depending on how many
> domains are blocking the number of timers varies.
> Then there is one timer per vcpu to generate a ticker for the 
> currently
> running VM.
Every domain or every *active* domain?

For inactive domains, determining when the next ticker
should be delivered could be part of the domain context,
with next tick scheduled when it is made active.


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

> We are going to strip out the periodic ticker entirely (at least in 
> arch/x86) and have just a programmable one-shot timer. We 
> need to keep 
> track of what is the nearest event we care about so we know what to 
> program into the one-shot timer.
Yes, this is exactly what Xen/ia64 does today.
 
> I think the interface could be simplified a little (fold 
> mod_ac_timer/add_ac_timer into a single function, for 
> example), but the 
> implementation is already very pared down. I image it would 
> hardly save 
> 100 lines, or bytes of hypervisor code, to replace the heap with a 
> list, for example.
With the periodic ticker gone, all that''s really left for
ac_timer is a Xen scheduler interrupt (I think).

Is the Xen scheduler interrupt per-cpu or is there a "monarch"?
If the latter, the usage of ac_timer keeps a''dwindling.

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

> Is there ever any more than one or two elements in the queue?
> What is the total set of functions called by the queue?
You could potentially have two, and in future possibly even three,
timeouts per domain.
> I suspect that the whole functionality of it can be replaced 
> with a couple of time variables that are checked and 
> manipulated in the timer interrupt code and a single 
> scheduler/timer routine in the generic scheduler.
What would you propose instead of an array heap? A linked list? 
Sounds daft to me.
> Not urgent, but if this is the right direction, we shouldn''t 
> be layering more code on top of it (thus the suggestion of 
> deprecating it).
ac_timer seems like a perfrectly good abstraction, and I can think of no
reason to deprecate it.

Ian


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

> > I suspect that the whole functionality of it can be replaced 
> > with a couple of time variables that are checked and 
> > manipulated in the timer interrupt code and a single 
> > scheduler/timer routine in the generic scheduler.
> 
> What would you propose instead of an array heap? A linked list? 
> Sounds daft to me.
You misunderstand.  I''m not proposing a different abstraction,
I''m questioning whether an abstraction is necessary at all.
> You could potentially have two, and in future possibly even three,
> timeouts per domain.
I agree that if there are three or more unique uses for
the abstraction (or will be in the future), an abstraction
is goodness.  If there are two, it''s probably borderline.
If there is one, an abstraction seems like overkill; just
use a (possibly per-domain or per-vcpu) variable and if statements.

It sounds/looks like the number is getting smaller, especially
with the periodic ticker going away.

No offense intended to the designer/coder of ac_timer, I''m
just noticing a trend.

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

On 23/5/05 10:07 pm, "Magenheimer, Dan (HP Labs Fort Collins)"
<dan.magenheimer@hp.com> wrote:
>> Of the top of my head:
>> Each domain has a timer to schedule timeout values. So
>> depending on how many
>> domains are blocking the number of timers varies.
>> Then there is one timer per vcpu to generate a ticker for the
>> currently
>> running VM.
> 
> Every domain or every *active* domain?
> 
> For inactive domains, determining when the next ticker
> should be delivered could be part of the domain context,
> with next tick scheduled when it is made active.
> 
It''s for every "inactive" domain, ie domain which is blocked.
Under Linux we
set a timeout value in the the idle loop to the next timer event the guest
cares about and then block. This is translated into a ac_timer for that
domain.

I don''t understand how making this part of the domain context makes
this
simpler. Basically, instead of looking up the head of a generic timer queue
for the next timeout value, as we do now, you seem to propose that we should
look up the timeout value for a domain in the list of blocked domain when
reprogramming the timer (and maybe a couple of other places).

The order of domains on the schedulers "blocked" list is best left up
to the
scheduler. In the *best* case it is ordered by timeout value so this would
be functionally equiv to what we have now (except that we might have to
check for some other variables containing timeout values as well). In the
worst case we''d have to scan all inactive domains'' contexts
for the lowest
timeout value. Actually, we would have to do that anyway if we want to keep
the ability of having different schedulers. Then, we certainly don''t
want to
dictate a way what types of queues a given scheduler *has* to use and which
order domains should be placed on it. This seems strictly more complicated,
*and* less generic than what we have now (even if just used for scheduling).

BTW.: ac_timers are per physical CPU as they are scheduled off the local
APIC. There is priority queue per local APIC.

Rolf







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

OK, that answers my question.  I was unaware that wakeup
of inactive domains was queued (and ordered) as ac_timer entries.

Thanks,
Dan 
> -----Original Message-----
> From: Rolf Neugebauer [mailto:rolf.neugebauer@intel.com] 
> Sent: Monday, May 23, 2005 5:37 PM
> To: Magenheimer, Dan (HP Labs Fort Collins)
> Cc: xen-devel@lists.xensource.com
> Subject: Re: [Xen-devel] ac_timer: time to say goodbye?
> 
> 
> 
> 
> On 23/5/05 10:07 pm, "Magenheimer, Dan (HP Labs Fort Collins)"
> <dan.magenheimer@hp.com> wrote:
> 
> >> Of the top of my head:
> >> Each domain has a timer to schedule timeout values. So
> >> depending on how many
> >> domains are blocking the number of timers varies.
> >> Then there is one timer per vcpu to generate a ticker for the
> >> currently
> >> running VM.
> > 
> > Every domain or every *active* domain?
> > 
> > For inactive domains, determining when the next ticker
> > should be delivered could be part of the domain context,
> > with next tick scheduled when it is made active.
> > 
> 
> It''s for every "inactive" domain, ie domain which is
blocked.
> Under Linux we
> set a timeout value in the the idle loop to the next timer 
> event the guest
> cares about and then block. This is translated into a 
> ac_timer for that
> domain.
> 
> I don''t understand how making this part of the domain context 
> makes this
> simpler. Basically, instead of looking up the head of a 
> generic timer queue
> for the next timeout value, as we do now, you seem to propose 
> that we should
> look up the timeout value for a domain in the list of blocked 
> domain when
> reprogramming the timer (and maybe a couple of other places).
> 
> The order of domains on the schedulers "blocked" list is best 
> left up to the
> scheduler. In the *best* case it is ordered by timeout value 
> so this would
> be functionally equiv to what we have now (except that we 
> might have to
> check for some other variables containing timeout values as 
> well). In the
> worst case we''d have to scan all inactive domains''
contexts
> for the lowest
> timeout value. Actually, we would have to do that anyway if 
> we want to keep
> the ability of having different schedulers. Then, we 
> certainly don''t want to
> dictate a way what types of queues a given scheduler *has* to 
> use and which
> order domains should be placed on it. This seems strictly 
> more complicated,
> *and* less generic than what we have now (even if just used 
> for scheduling).
> 
> BTW.: ac_timers are per physical CPU as they are scheduled 
> off the local
> APIC. There is priority queue per local APIC.
> 
> Rolf
> 
> 
> 
> 
> 
> 
> 
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel