Re: [RFC][PATCH] Logarithmic Timekeeping Accumulation

[Ingo Molnar <mingo@elte.hu>]

* John Stultz <johnstul@us.ibm.com> wrote:

> Accumulating one tick at a time works well unless we're using 
> NOHZ. Then it can be an issue, since we may have to run through 
> the loop a few thousand times, which can increase timer interrupt 
> caused latency.
> 
> The current solution was to accumulate in half-second intervals 
> with NOHZ. This kept the number of loops down, however it did 
> slightly change how we make NTP adjustments. While not an issue 
> with NTPd users, as NTPd makes adjustments over a longer period of 
> time, other adjtimex() users have noticed the half-second 
> granularity with which we can apply frequency changes to the 
> clock.
> 
> For instance, if a application tries to apply a 100ppm frequency 
> correction for 20ms to correct a 2us offset, with NOHZ they either 
> get no correction, or a 50us correction.
> 
> Now, there will always be some granularity error for applying 
> frequency corrections. However with users sensitive to this error 
> have seen a 50-500x increase with NOHZ compared to running without 
> NOHZ.
> 
> So I figured I'd try another approach then just simply increasing 
> the interval. My approach is to consume the time interval 
> logarithmically. This reduces the number of times through the loop 
> needed keeping latency down, while still preserving the original 
> granularity error for adjtimex() changes.
> 
> This has been lightly tested and appears to work correctly, but 
> I'd appreciate any feedback or comments on the idea and code.
> 
> Signed-off-by: John Stultz <johnstul@us.ibm.com>

Hm, we used to have some sort of problem with a similar patch in the 
past. 

>  		/* accumulate error between NTP and clock interval */
> -		clock->error += tick_length;
> -		clock->error -= clock->xtime_interval << (NTP_SCALE_SHIFT - clock->shift);
> +		clock->error += tick_length << shift;
> +		clock->error -= (clock->xtime_interval
> +				<< (NTP_SCALE_SHIFT - clock->shift))
> +					<< shift;

Why not:

		clock->error -= clock->xtime_interval
				<< (NTP_SCALE_SHIFT - clock->shift + shift);

?

> +		if (shift > 0) /*don't roll under!*/
> +			shift--;

(nit: watch out the comment style)

that bit looks a bit messy. We estimated the shift:

+	while (offset > (clock->cycle_interval << shift))
+               shift++;
+	shift--;

can it really ever roll under in this loop:

        while (offset >= clock->cycle_interval) {

        ...
                offset -= clock->cycle_interval << shift;

?

	Ingo