linux-kernel - Re: Re: [PATCH] optimize ktime

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 for Android: free password hash cracker in your pocket

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

Date:	Thu, 4 Dec 2014 23:30:08 -0500 (EST)
From:	Nicolas Pitre <nicolas.pitre@...aro.org>
To:	pang.xunlei@....com.cn
cc:	Arnd Bergmann <arnd@...db.de>,
	John Stultz <john.stultz@...aro.org>,
	linux-arm-kernel@...ts.infradead.org, linux-kernel@...r.kernel.org,
	linux-kernel-owner@...r.kernel.org,
	Thomas Gleixner <tglx@...utronix.de>
Subject: Re: Re: [PATCH] optimize ktime_divns for constant divisors

On Fri, 5 Dec 2014, pang.xunlei@....com.cn wrote:

> Nicolas,
> 
> On Thursday 04 December 2014 15:23:37: Nicolas Pitre wrote:
> > Nicolas Pitre <nicolas.pitre@...aro.org> 
> > 
> > u64 ktime_to_us(ktime_t kt)
> > {
> >    u64 ns = ktime_to_ns(kt);
> >    u32 x_lo, x_hi, y_lo, y_hi;
> >    u64 res, carry;
> > 
> >    x_hi = ns >> 32;
> >    x_lo = ns;
> >    y_hi = 0x83126e97;
> >    y_lo = 0x8d4fdf3b;
> > 
> >    res = (u64)x_lo * y_lo;
> >    carry = (u64)(u32)res + y_lo;
> >    res = (res >> 32) + (carry >> 32);
> > 
> >    res += (u64)x_lo * y_hi;
> >    carry = (u64)(u32)res + (u64)x_hi * y_lo;
> >    res = (res >> 32) + (carry >> 32);
> > 
> >    res += (u64)x_hi * y_hi;
> >    return res >> 9;
> > }
> 
> What's the first carry operation for?

Hmmm... OK there is a bug.

The code should actually be:

	res = (u64)x_lo * y_lo;
	carry = (u64)(u32)res + y_lo;
	res = (res >> 32) + (carry >> 32) + y_hi;

(the addition of y_hi was missing on the third line of the above block)

The equation is: res = (y + x*y) >> 9

> Moreover, I think the carry operations can be omitted, like below:
> u64 ktime_to_us(ktime_t kt)
> {
>          u64 ns = ktime_to_ns(kt);
>          u32 x_lo, x_hi, y_lo, y_hi;
>          u64 res;
> 
>          x_hi = ns >> 32;
>          x_lo = ns;
>          y_hi = 0x83126e97;
>          y_lo = 0x8d4fdf3b;
> 
>          res = (u64)x_lo * y_lo;
>          res = (res >> 32);

See above. y must be added to res before shifting, and that may cause an 
overflow.

>          res += (u64)x_lo * y_hi + (u64)x_hi * y_lo;

That, too, risk overflowing.

Let's say x_lo = 0xffffffff and x_hi = 0xffffffff.  You get:

	0xffffffff * 0x83126e97 ->  0x83126e967ced9169
	0xffffffff * 0x8d4fdf3b ->  0x8d4fdf3a72b020c5
	                           -------------------
	                           0x110624dd0ef9db22e

Therefore the sum doesn't fit into a u64 variable.

It is possible to skip carry handling but only when the MSB of both 
constants are zero.  Here it is not the case.

>          res = (res >> 32);
> 
>          res += (u64)x_hi * y_hi;
> 
>          return res >> 9;
> }
> 
> Also, I ran this code using ktime "122500000000", and it results as
> 122499999 due to the y_lo deviation,

Please see bug fix above.

> maybe can use 0x8d4fdf3c instead?

No, that won't work with 0xfffffffffffffd97 for example.


Nicolas
--
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/