(BUG?) round_jiffies() is non-monotonic on SMP

(BUG?) round_jiffies() is non-monotonic on SMP

[Alan Stern]

Is it generally recognized that round_jiffies() can be non-monotonic on 
SMP systems?  By this, I mean that if cpu-a and cpu-b respectively do:

	ra = round_jiffies(ja);

		and

	rb = round_jiffies(jb);

then the ordering of ra and rb can be opposite the ordering of ja and 
jb.

If this is known, is it regarded as a potential problem?  It certainly
seems likely that some code somewhere depends on timeouts expiring in
the correct order.

Alan Stern

P.S.: As a related matter, it seems very odd that we don't have a 
round_jiffies_up() routine.  Surely there are plenty of places where it 
doesn't matter if an event is a little late but where the event must 
not be early.  (I know two such places offhand.)  Any objection to 
having one added?

Re: (BUG?) round_jiffies() is non-monotonic on SMP

[Arjan van de Ven]

On Sat, 1 Nov 2008 12:14:41 -0400 (EDT)
Alan Stern <stern@rowland.harvard.edu> wrote:

> Is it generally recognized that round_jiffies() can be non-monotonic
> on SMP systems?  By this, I mean that if cpu-a and cpu-b respectively
> do:
> 
> 	ra = round_jiffies(ja);
> 
> 		and
> 
> 	rb = round_jiffies(jb);
> 
> then the ordering of ra and rb can be opposite the ordering of ja and 
> jb.

round_jiffies() tends to be used (and is designed to be used) for cases
where you don't really care when exactly timers will fire... including
the order against other such timers.

 
> If this is known, is it regarded as a potential problem?  It certainly
> seems likely that some code somewhere depends on timeouts expiring in
> the correct order.

I don't think timeouts EVER have that guarantee between different cpus;
even if you don't round the timeouts.
After all, your CPU A can be in some delay loop with irqs off for
longer than the delta was, and boom.. the timers fire in different
order.
If we ever have such ordering requirements in the kernel that
don't handle this... they're a bug...

> 
> Alan Stern
> 
> P.S.: As a related matter, it seems very odd that we don't have a 
> round_jiffies_up() routine.  Surely there are plenty of places where
> it doesn't matter if an event is a little late but where the event
> must not be early.  (I know two such places offhand.)  Any objection
> to having one added?

no objection per se, but I would almost argue we should convert such
places to range timers....
that way the kernel can, rather an aligning them, group them with other
activity.


-- 
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: (BUG?) round_jiffies() is non-monotonic on SMP

[Alan Stern]

On Sat, 1 Nov 2008, Arjan van de Ven wrote:

> > If this is known, is it regarded as a potential problem?  It certainly
> > seems likely that some code somewhere depends on timeouts expiring in
> > the correct order.
> 
> I don't think timeouts EVER have that guarantee between different cpus;
> even if you don't round the timeouts.
> After all, your CPU A can be in some delay loop with irqs off for
> longer than the delta was, and boom.. the timers fire in different
> order.

Why is that?  The fact that CPU A is busy might mean that the timer
routines run on some other CPU... but they should still be called in
the correct order.

Is it possible for timer 1 to expire before timer 2 but the handler
gets interrupted, with the result that timer 2's handler runs to
completion on a different CPU before timer 1's handler has managed to
execute more than a couple of instructions?  If it is then I agree,
timer-ordering requirements between CPUs don't make much sense.

I don't understand all the details of how timers work on SMP systems,
so maybe some subtlety has escaped me.  For instance, there's no
guarantee AFAIK that the system clocks on two different CPUs will be
synchronized with each other.  But wouldn't it be surprising if they
differed by more than a couple of milliseconds?

> If we ever have such ordering requirements in the kernel that
> don't handle this... they're a bug...

I don't know of any examples.

> > P.S.: As a related matter, it seems very odd that we don't have a 
> > round_jiffies_up() routine.  Surely there are plenty of places where
> > it doesn't matter if an event is a little late but where the event
> > must not be early.  (I know two such places offhand.)  Any objection
> > to having one added?
> 
> no objection per se, but I would almost argue we should convert such
> places to range timers....
> that way the kernel can, rather an aligning them, group them with other
> activity.

Come to think of it, is there any good reason why round_jiffies()  
doesn't always round up?  It seems a lot safer.

Alan Stern

Re: (BUG?) round_jiffies() is non-monotonic on SMP

[Arjan van de Ven]

On Sat, 1 Nov 2008 15:54:16 -0400 (EDT)
Alan Stern <stern@rowland.harvard.edu> wrote:

> On Sat, 1 Nov 2008, Arjan van de Ven wrote:
> 
> > > If this is known, is it regarded as a potential problem?  It
> > > certainly seems likely that some code somewhere depends on
> > > timeouts expiring in the correct order.
> > 
> > I don't think timeouts EVER have that guarantee between different
> > cpus; even if you don't round the timeouts.
> > After all, your CPU A can be in some delay loop with irqs off for
> > longer than the delta was, and boom.. the timers fire in different
> > order.
> 
> Why is that?  The fact that CPU A is busy might mean that the timer
> routines run on some other CPU... but they should still be called in
> the correct order.

Hi,

I think you misunderstand how timers work right now ;)

timers are a per cpu list, and each cpu has its own interrupt to
service this per cpu list.

now... if one cpu disables interrupts for a while, that cpus interrupts
get blocked, including that cpus timer handling irq (whichever method
is used for that)... and only that cpus timers will get delayed, the
other cpus will just keep rolling...


> 
> Is it possible for timer 1 to expire before timer 2 but the handler
> gets interrupted, with the result that timer 2's handler runs to
> completion on a different CPU before timer 1's handler has managed to
> execute more than a couple of instructions?  If it is then I agree,
> timer-ordering requirements between CPUs don't make much sense.

yes
> 
> 
> Come to think of it, is there any good reason why round_jiffies()  
> doesn't always round up?  It seems a lot safer.

at the time folks had concerns about making a big error in that
direction...


-- 
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: (BUG?) round_jiffies() is non-monotonic on SMP

[Alan Stern]

On Sat, 1 Nov 2008, Arjan van de Ven wrote:

> > Come to think of it, is there any good reason why round_jiffies()  
> > doesn't always round up?  It seems a lot safer.
> 
> at the time folks had concerns about making a big error in that
> direction...

All right then.  Would it be preferable to add a new round_jiffies_up() 
routine, or to change round_jiffies() so that it never rounds down?

Alan Stern

Re: (BUG?) round_jiffies() is non-monotonic on SMP

[Arjan van de Ven]

On Sat, 1 Nov 2008 22:36:30 -0400 (EDT)
Alan Stern <stern@rowland.harvard.edu> wrote:

> On Sat, 1 Nov 2008, Arjan van de Ven wrote:
> 
> > > Come to think of it, is there any good reason why
> > > round_jiffies() doesn't always round up?  It seems a lot safer.
> > 
> > at the time folks had concerns about making a big error in that
> > direction...
> 
> All right then.  Would it be preferable to add a new
> round_jiffies_up() routine, or to change round_jiffies() so that it
> never rounds down?

I'd prefer the former.
But to be honest.. I would even more prefer the use of range timers ;)
They're in 2.6.28-rc now ... and more power friendly than rounded timers
(although I will readily admit that rounding is just easier)



-- 
Arjan van de Ven 	Intel Open Source Technology Centre
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org

Re: (BUG?) round_jiffies() is non-monotonic on SMP

[Alan Stern]

On Sat, 1 Nov 2008, Arjan van de Ven wrote:

> On Sat, 1 Nov 2008 22:36:30 -0400 (EDT)
> Alan Stern <stern@rowland.harvard.edu> wrote:
> 
> > On Sat, 1 Nov 2008, Arjan van de Ven wrote:
> > 
> > > > Come to think of it, is there any good reason why
> > > > round_jiffies() doesn't always round up?  It seems a lot safer.
> > > 
> > > at the time folks had concerns about making a big error in that
> > > direction...
> > 
> > All right then.  Would it be preferable to add a new
> > round_jiffies_up() routine, or to change round_jiffies() so that it
> > never rounds down?
> 
> I'd prefer the former.
> But to be honest.. I would even more prefer the use of range timers ;)
> They're in 2.6.28-rc now ... and more power friendly than rounded timers
> (although I will readily admit that rounding is just easier)

I don't know. One of the cases I know about is the timer embedded in a 
delayed_work -- it's hard to see how that could be converted.

The other could be converted.  But it falls in the category of
"timeouts", as described in Documentation/timers/hrtimers.txt.  As
such, it is best suited to an old-style timer rather than a
high-precision timer (according to hrtimers.txt, at least).  
Furthermore, there doesn't seem to be any documentation describing how
to use the range timer programming interface.

Under the circumstances, I'm not inclined to do any conversions.

Alan Stern