time: Improve documentation of timekeeeping_adjust()
PATCH 1/1 time: Improve documentation of timekeeeping_adjust()
After getting a number of questions in private emails about the math around admittedly very complex timekeeping_adjust() and timekeeping_big_adjust(), I figure the code needs some better comments.
Hopefully the explanations are clear enough and don't muddy the water any worse.
Still needs documentation for ntp_error, but I couldn't recall exactly the full explanation behind the code that's there (although I do recall once working it out when Roman first proposed it). Given a bit more time I can probably work it out, but I don't want to hold back this documentation until then.
--- kernel/time/timekeeping.c | 81 ++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 80 insertions(+), 1 deletions(-)
kernel/time/timekeeping.c +80 -1
@@ -802,14 +802,44 @@ static void timekeeping_adjust(s64 offset)s64 error, interval = timekeeper.cycle_interval;int adj; +/* +* The point of this is to check if the error is greater then half +* an interval. +* +* First we shift it down from NTP_SHIFT to clocksource->shifted nsecs. +* +* Note we subtract one in the shift, so that error is really error*2. +* This "saves" dividing(shifting) intererval twice, but keeps the +* (error > interval) comparision as still measuring if error is +* larger then half an interval. +* +* Note: It does not "save" on aggrivation when reading the code. +*/ error = timekeeper.ntp_error >> (timekeeper.ntp_error_shift -1 );if (error > interval) { +/* +* We now divide error by 4(via shift), which checks if +* the error is greater then twice the interval. +* If it is greater, we need a bigadjust, if its smaller, +* we can adjust by 1. +*/ error >>=2 ; +/* +* XXX - In update_wall_time, we round up to the next +* nanosecond, and store the amount rounded up into +* the error. This causes the likely below to be unlikely. +* +* The properfix is to avoid rounding up by using +* the high precision timekeeper.xtime_nsec instead of +* xtime.tv_nsec everywhere. Fixing this will take some +* time. +*/ if (likely (error <= interval)) adj =1 ;else adj =timekeeping_bigadjust (error, &interval, &offset); }else if (error < -interval) { +/* See comment above, this is just switched for the negative */ error >>=2 ;if (likely (error >= -interval)) { adj =-1 ;
@@ -817,9 +847,58 @@ static void timekeeping_adjust(s64 offset) offset = -offset; }else adj =timekeeping_bigadjust (error, &interval, &offset); - }else + }else /* No adjustment needed */ return ; +/* +* So the following can be confusing. +* +* To keep things simple, lets assume adj == 1 for now. +* +* When adj != 1, remember that the interval and offset values +* have been appropriately scaled so the math is the same. +* +* The basic idea here is that we're increasing the multiplier +* by one, this causes the xtime_interval to be incremented by +* one cycle_interval. This is because: +* xtime_interval = cycle_interval * mult +* So if mult is being incremented by one: +* xtime_interval = cycle_interval * (mult + 1) +* Its the same as: +* xtime_interval = (cycle_interval * mult) + cycle_interval +* Which can be shortened to: +* xtime_interval += cycle_interval +* +* So offset stores the non-accumulated cycles. Thus the current +* time (in shifted nanoseconds) is: +* now = (offset * adj) + xtime_nsec +* Now, even though we're adjusting the clock frequency, we have +* to keep time consistent. In other words, we can't jump back +* in time, and we also want to avoid jumping forward in time. +* +* So given the same offset value, we need the time to be the same +* both before and after the freq adjustment. +* now = (offset * adj_1) + xtime_nsec_1 +* now = (offset * adj_2) + xtime_nsec_2 +* So: +* (offset * adj_1) + xtime_nsec_1 = +* (offset * adj_2) + xtime_nsec_2 +* And we know: +* adj_2 = adj_1 + 1 +* So: +* (offset * adj_1) + xtime_nsec_1 = +* (offset * (adj_1+1)) + xtime_nsec_2 +* (offset * adj_1) + xtime_nsec_1 = +* (offset * adj_1) + offset + xtime_nsec_2 +* Canceling the sides: +* xtime_nsec_1 = offset + xtime_nsec_2 +* Which gives us: +* xtime_nsec_2 = xtime_nsec_1 - offset +* Which simplfies to: +* xtime_nsec -= offset +* +* XXX - TODO: Doc ntp_error calculation. +*/ timekeeper.mult += adj; timekeeper.xtime_interval += interval; timekeeper.xtime_nsec -= offset;
Signature · 1 line
1.7.3.2.146.gca209
Quoted 10 lines · John Stultz
kernel/time/timekeeping.c +2
-0@@ -802,14 +802,44 @@ static void timekeeping_adjust(s64 offset)s64 error, interval = timekeeper.cycle_interval;int adj; +/* +* The point of this is to check if the error is greater then half
kernel/time/timekeeping.c static void timekeeping_adjust(s64 offset) · line 816
Quoted 10 lines
kernel/time/timekeeping.c +10
-0+* an interval. +* +* First we shift it down from NTP_SHIFT to clocksource->shifted nsecs. +* +* Note we subtract one in the shift, so that error is really error*2. +* This "saves" dividing(shifting) intererval twice, but keeps the +* (error > interval) comparision as still measuring if error is +* larger then half an interval. +* +* Note: It does not "save" on aggrivation when reading the code.
... or on "aggravation" either :)
Thanks,
Richard
Quoted 9 lines · Richard Cochran
Quoted 8 lines · John Stultz
kernel/time/timekeeping.c +0
-0@@ -802,14 +802,44 @@ static void timekeeping_adjust(s64 offset)s64 error, interval = timekeeper.cycle_interval;int adj;
Quoted 14 lines
kernel/time/timekeeping.c static void timekeeping_adjust(s64 offset) · line 816
Quoted 12 lines
kernel/time/timekeeping.c +12
-0+/* +* The point of this is to check if the error is greater then half +* an interval. +* +* First we shift it down from NTP_SHIFT to clocksource->shifted nsecs. +* +* Note we subtract one in the shift, so that error is really error*2. +* This "saves" dividing(shifting) intererval twice, but keeps the +* (error > interval) comparision as still measuring if error is +* larger then half an interval. +* +* Note: It does not "save" on aggrivation when reading the code. ... or on "aggravation" either :)
Sigh. I do need to start using an editor with built in spell checking. I'm so poor of a speller (and a typist) its really amazing its not worse.
Thanks for catching that.
-john
Quoted 25 lines · John Stultz
Quoted 9 lines · Richard Cochran
Quoted 8 lines · John Stultz
kernel/time/timekeeping.c +0
-0@@ -802,14 +802,44 @@ static void timekeeping_adjust(s64 offset)s64 error, interval = timekeeper.cycle_interval;int adj;Quoted 14 lines
kernel/time/timekeeping.c static void timekeeping_adjust(s64 offset) · line 816
Quoted 12 lines
kernel/time/timekeeping.c +12
-0+/* +* The point of this is to check if the error is greater then half +* an interval. +* +* First we shift it down from NTP_SHIFT to clocksource->shifted nsecs. +* +* Note we subtract one in the shift, so that error is really error*2. +* This "saves" dividing(shifting) intererval twice, but keeps the +* (error > interval) comparision as still measuring if error is +* larger then half an interval. +* +* Note: It does not "save" on aggrivation when reading the code. ... or on "aggravation" either :)
Quoted 6 lines
Sigh. I do need to start using an editor with built in spell checking. I'm so poor of a speller (and a typist) its really amazing its not worse.
Thanks for catching that.
-john
s/intererval/interval/
AndyM
Ingo Molnar
AppliedQuoted 14 lines · John Stultz
After getting a number of questions in private emails about the math around admittedly very complex
timekeeping_adjust()andtimekeeping_big_adjust(), I figure the code needs some better comments.Hopefully the explanations are clear enough and don't muddy the water any worse.
Still needs documentation for
ntp_error, but I couldn't recall exactly the full explanation behind the code that's there (although I do recall once working it out when Roman first proposed it). Given a bit more time I can probably work it out, but I don't want to hold back this documentation until then.
Quoted 7 lines
CC Chen Jie <[email protected]>CC Steven Rostedt <[email protected]>CC Thomas Gleixner <[email protected]>Signed-off-by John Stultz <[email protected]>--- kernel/time/timekeeping.c | 81 ++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 80 insertions(+), 1 deletions(-)
Applied to tip:timers/core, thanks John.
Ingo
Commit-ID: c2bc11113c50449f23c40b724fe410fc2380a8e9 Gitweb: http://git.kernel.org/tip/c2bc11113c50449f23c40b724fe410fc2380a8e9 Author: John Stultz <[email protected]> AuthorDate: Thu, 27 Oct 2011 18:12:42 -0700 Committer: Ingo Molnar <[email protected]> CommitDate: Fri, 28 Oct 2011 08:57:38 +0200
time: Improve documentation of timekeeeping_adjust()
After getting a number of questions in private emails about the math around admittedly very complex timekeeping_adjust() and timekeeping_big_adjust(), I figure the code needs some better comments.
Hopefully the explanations are clear enough and don't muddy the water any worse.
Still needs documentation for ntp_error, but I couldn't recall exactly the full explanation behind the code that's there (although I do recall once working it out when Roman first proposed it). Given a bit more time I can probably work it out, but I don't want to hold back this documentation until then.
--- kernel/time/timekeeping.c | 81 ++++++++++++++++++++++++++++++++++++++++++++- 1 files changed, 80 insertions(+), 1 deletions(-)
kernel/time/timekeeping.c +80 -1
@@ -802,14 +802,44 @@ static void timekeeping_adjust(s64 offset)s64 error, interval = timekeeper.cycle_interval;int adj; +/* +* The point of this is to check if the error is greater then half +* an interval. +* +* First we shift it down from NTP_SHIFT to clocksource->shifted nsecs. +* +* Note we subtract one in the shift, so that error is really error*2. +* This "saves" dividing(shifting) intererval twice, but keeps the +* (error > interval) comparision as still measuring if error is +* larger then half an interval. +* +* Note: It does not "save" on aggrivation when reading the code. +*/ error = timekeeper.ntp_error >> (timekeeper.ntp_error_shift -1 );if (error > interval) { +/* +* We now divide error by 4(via shift), which checks if +* the error is greater then twice the interval. +* If it is greater, we need a bigadjust, if its smaller, +* we can adjust by 1. +*/ error >>=2 ; +/* +* XXX - In update_wall_time, we round up to the next +* nanosecond, and store the amount rounded up into +* the error. This causes the likely below to be unlikely. +* +* The properfix is to avoid rounding up by using +* the high precision timekeeper.xtime_nsec instead of +* xtime.tv_nsec everywhere. Fixing this will take some +* time. +*/ if (likely (error <= interval)) adj =1 ;else adj =timekeeping_bigadjust (error, &interval, &offset); }else if (error < -interval) { +/* See comment above, this is just switched for the negative */ error >>=2 ;if (likely (error >= -interval)) { adj =-1 ;
@@ -817,9 +847,58 @@ static void timekeeping_adjust(s64 offset) offset = -offset; }else adj =timekeeping_bigadjust (error, &interval, &offset); - }else + }else /* No adjustment needed */ return ; +/* +* So the following can be confusing. +* +* To keep things simple, lets assume adj == 1 for now. +* +* When adj != 1, remember that the interval and offset values +* have been appropriately scaled so the math is the same. +* +* The basic idea here is that we're increasing the multiplier +* by one, this causes the xtime_interval to be incremented by +* one cycle_interval. This is because: +* xtime_interval = cycle_interval * mult +* So if mult is being incremented by one: +* xtime_interval = cycle_interval * (mult + 1) +* Its the same as: +* xtime_interval = (cycle_interval * mult) + cycle_interval +* Which can be shortened to: +* xtime_interval += cycle_interval +* +* So offset stores the non-accumulated cycles. Thus the current +* time (in shifted nanoseconds) is: +* now = (offset * adj) + xtime_nsec +* Now, even though we're adjusting the clock frequency, we have +* to keep time consistent. In other words, we can't jump back +* in time, and we also want to avoid jumping forward in time. +* +* So given the same offset value, we need the time to be the same +* both before and after the freq adjustment. +* now = (offset * adj_1) + xtime_nsec_1 +* now = (offset * adj_2) + xtime_nsec_2 +* So: +* (offset * adj_1) + xtime_nsec_1 = +* (offset * adj_2) + xtime_nsec_2 +* And we know: +* adj_2 = adj_1 + 1 +* So: +* (offset * adj_1) + xtime_nsec_1 = +* (offset * (adj_1+1)) + xtime_nsec_2 +* (offset * adj_1) + xtime_nsec_1 = +* (offset * adj_1) + offset + xtime_nsec_2 +* Canceling the sides: +* xtime_nsec_1 = offset + xtime_nsec_2 +* Which gives us: +* xtime_nsec_2 = xtime_nsec_1 - offset +* Which simplfies to: +* xtime_nsec -= offset +* +* XXX - TODO: Doc ntp_error calculation. +*/ timekeeper.mult += adj; timekeeper.xtime_interval += interval; timekeeper.xtime_nsec -= offset;