[lkml]   [2013]   [Nov]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: Clock control algorithms (Re: [RFC][PATCH 5/7] x86: Use latch data structure for cyc2ns)
There is a huge difference between something that breaks after 2^32 and 2^64 events.  Very few computers will ever be able to have 2^64 events of any kind in their lifetime, never mind a single boot.  

Andy Lutomirski <> wrote:
>[Subject changed because this isn't relevant to the patches in
>question any more.]
>On Sat, Nov 30, 2013 at 1:18 AM, Peter Zijlstra <>
>> On Fri, Nov 29, 2013 at 03:22:45PM -0800, Andy Lutomirski wrote:
>>> On Fri, Nov 29, 2013 at 9:37 AM, Peter Zijlstra
><> wrote:
>>> > Use the 'latch' data structure for cyc2ns.
>>> >
>>> > This is a data structure first proposed by me and later named by
>>> > Mathieu. If anybody's got a better name; do holler.
>>> That structure must exist in the literature, but I have no idea what
>>> it's called. It's a multi-word lock-free atomic (I think -- maybe
>>> it's just regular) register. I even published a considerably
>>> version of much the same thing a few years ago. :)
>> Yeah, its a fairly straight fwd thing it has to be named someplace
>The trouble is that this data structure (like seqlocks, refcounts, and
>lots of real-world synchronization things) fails if the reader falls
>asleep for a multiple of 2^32 (or 2^64) writes. The literature
>generally doesn't like such things. (As a thoroughly irrelevant
>aside, TSX, and maybe even LL/SC, can be used to work around that
>issue in case anyone cares.)
>>> I've occasionally wondered whether it would be possible to make a
>>> monotonicity-preserving version of this and use it for
>>> One approach: have the writer set the time for the update to be a
>>> in the future and have the reader compare the current raw time to
>>> cutoff to see which set of frequency/offset to use. (This requires
>>> having some kind of bound on how long it takes to update the data
>>> structures.)
>>> The advantage: clock_gettime would never block.
>>> The disadvantage: complicated, potentially nasty to implement, and
>>> would get complicated if anyone tried to allow multiple updates in
>>> rapid succession.
>> Yes, that way you can chain a number of linear segments in various
>> slots, but you're indeed right in that it will limit the update
>> frequency. More slots will give you more room, but eventually you're
>> limited.
>> I suppose NTP is the primary updater in that case, does that have a
>> limit on the updates? All the other updates we can artificially
>> that shouldn't really matter.
>> But yeah in my case we pretty much assume the TSC is complete crap
>and a
>> little more crap simply doesn't matter.
>> For the 'stable' tsc on modern machines we never set the frequency
>> it doesn't matter anyway.
>I assume that NTP works by filddling with the frequency and offset on
>a regular basis to preserve monotonicity while still controlling the
>TBH, I've never understood why the NTP code is so integrated into the
>kernel's timing infrastucture or, for that matter, lives in the kernel
>at all. Shouldn't the core interface be something more like "starting
>at time t_1, change the frequency to f_1, then at time t_2, change the
>frequency to f_2"? That would give the ability to manage a control
>loop in userspace (or some kernel thread) and to reliably slew the
>clock by a small, fixed amount. I suppose this could be elaborated to
>allow more than two adjustments to be scheduled in advance, but I
>really don't see the need for anything much fancier.
> - Comprehensible without reading the entire NTP spec and all the
>various addenda.
> - No need for any timing code at all in the tick handler -- the whole
>thing could presumably be done with hrtimers and a bit fancier data
>structure that lets clock_gettime figure out when to update*.
> - Things like PTP don't need to pretend to be NTP.
>Disadvantages: No clue, since I don't know why NTP works the way it
>does right now.
>* vclock_gettime on x86_64 already has a branch that depends on the
>time. I think that good implementation could do all of this fancy
>stuff with exactly one branch, resulting in the fast path being just
>as fast.

Sent from my mobile phone. Please pardon brevity and lack of formatting.

 \ /
  Last update: 2013-11-30 19:01    [W:0.070 / U:0.144 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site