linux-kernel - Re: [RFC][PATCH] Logarithmic Timekeeping Accumulation

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20090324141338.GF32043@elte.hu>
Date:	Tue, 24 Mar 2009 15:13:38 +0100
From:	Ingo Molnar <mingo@...e.hu>
To:	John Stultz <johnstul@...ibm.com>
Cc:	Linux-kernel <linux-kernel@...r.kernel.org>,
	Clark Williams <williams@...hat.com>,
	Steven Rostedt <srostedt@...hat.com>,
	Thomas Gleixner <tglx@...utronix.de>,
	Roman Zippel <zippel@...ux-m68k.org>
Subject: Re: [RFC][PATCH] Logarithmic Timekeeping Accumulation


* John Stultz <johnstul@...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@...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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/