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

This is a discussion on (BUG?) round_jiffies() is non-monotonic on SMP - Kernel ; 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 ...

+ Reply to Thread
Results 1 to 7 of 7

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

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

    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?

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

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

    On Sat, 1 Nov 2008 12:14:41 -0400 (EDT)
    Alan Stern 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
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

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

    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

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

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

    On Sat, 1 Nov 2008 15:54:16 -0400 (EDT)
    Alan Stern 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
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

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

    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

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

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

    On Sat, 1 Nov 2008 22:36:30 -0400 (EDT)
    Alan Stern 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
    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

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

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

    > On Sat, 1 Nov 2008 22:36:30 -0400 (EDT)
    > Alan Stern 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

    --
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

+ Reply to Thread