| Message ID | 572A6CDD.10503@av8n.com (mailing list archive) |
|---|---|
| State | Not Applicable |
| Delegated to: | Herbert Xu |
| Headers | show |
On May 4, 2016 2:42:53 PM PDT, John Denker <jsd@av8n.com> wrote: >On 05/04/2016 12:07 PM, tytso@thunk.org wrote: > >> it doesn't hit the >> UB case which Jeffrey was concerned about. > >That should be good enough for present purposes.... > >However, in the interests of long-term maintainability, I >would suggest sticking in a comment or assertion saying >that ror32(,shift) is never called with shift=0. This >can be removed if/when bitops.h is upgraded. > >There is a track record of compilers doing Bad Things in >response to UB code, including some very counterintuitive >Bad Things. > >On Wed, May 04, 2016 at 11:29:57AM -0700, H. Peter Anvin wrote: >>> >>> If bitops.h doesn't do the right thing, we need to >>> fix bitops.h. > >Most of the ror and rol functions in linux/bitops.h >should be considered unsafe, as currently implemented. >http://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/tree/include/linux/bitops.h?id=04974df8049fc4240d22759a91e035082ccd18b4#n103 > >I don't see anything in the file that suggests any limits >on the range of the second argument. So at best it is an >undocumented trap for the unwary. This has demonstrably >been a problem in the past. The explanation in the attached >fix-rol32.diff makes amusing reading. > >Of the eight functions > ror64, rol64, ror32, rol32, ror16, rol16, ror8, and rol8, >only one of them can handle shifting by zero, namely rol32. >It was upgraded on Thu Dec 3 22:04:01 2015; see the attached >fix-rol32.diff. > >I find it very odd that the other seven functions were not >upgraded. I suggest the attached fix-others.diff would make >things more consistent. > >Beware that shifting by an amount >= the number of bits in the >word remains Undefined Behavior. This should be either documented >or fixed. It could be fixed easily enough. This construct has been supported as a rotate since at least gcc2.
On 05/04/2016 02:56 PM, H. Peter Anvin wrote: >> Beware that shifting by an amount >= the number of bits in the >> word remains Undefined Behavior. > This construct has been supported as a rotate since at least gcc2. How then should we understand the story told in commit d7e35dfa? Is the story wrong? At the very least, something inconsistent is going on. There are 8 functions. Why did d7e35dfa change one of them but not the other 7? -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, May 04, 2016 at 03:06:04PM -0700, John Denker wrote: > On 05/04/2016 02:56 PM, H. Peter Anvin wrote: > >> Beware that shifting by an amount >= the number of bits in the > >> word remains Undefined Behavior. > > > This construct has been supported as a rotate since at least gcc2. > > How then should we understand the story told in commit d7e35dfa? > Is the story wrong? I don't think Linux runs on a system where it would make a difference (like a VAX), and also gcc always converts it before it could. Even UBSan should not complain because it runs after the conversion to ROTATE. So it's unlikely to be a pressing issue. -Andi
On 05/04/2016 04:06 PM, Andi Kleen wrote: > gcc always converts it before it could [make a difference]. At the moment, current versions of gcc treat the idiomatic ror/rol code as something they support ... but older versions do not, and future version may not. The gcc guys have made it very clear that they reserve the right to do absolutely anything they want in a UB situation. -- What is true as of today might not be "always" true. -- What is true at one level of optimization might not be true at another. -- The consequences can be highly nonlocal and counterintuitive. For example, in the case of: rslt = word << (32 - N); ... ... if (!N) { ....... } the compiler could assume that N is necessarily nonzero, and many lines later it could optimize out the whole if-block. So, even if the "<<" operator gives the right result, there could be ghastly failures elsewhere. It might work for some people but not others. > So it's unlikely to be a pressing issue. Sometimes issues that are not urgently "pressing" ought to be dealt with in a systematic way. There are serious people who think that avoiding UB is a necessity, if you want the code to be reliable and maintainable. I renew the question: Why did commit d7e35dfa upgrade one of the 8 functions but not the other 7? -- I could understand 0 of 8, or 8 of 8. -- In contrast, I'm having a hard time understanding why 7 of the 8 use the idiomatic expression while the 8th does not. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 05/04/16 15:06, John Denker wrote: > On 05/04/2016 02:56 PM, H. Peter Anvin wrote: >>> Beware that shifting by an amount >= the number of bits in the >>> word remains Undefined Behavior. > >> This construct has been supported as a rotate since at least gcc2. > > How then should we understand the story told in commit d7e35dfa? > Is the story wrong? > > At the very least, something inconsistent is going on. There > are 8 functions. Why did d7e35dfa change one of them but > not the other 7? Yes. d7e35dfa is baloney IMNSHO. All it does is produce worse code, and the description even says so. As I said, gcc has treated the former code as idiomatic since gcc 2, so that support is beyond ancient. -hpa -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, May 4, 2016 at 5:30 PM, H. Peter Anvin <hpa@zytor.com> wrote: > > Yes. d7e35dfa is baloney IMNSHO. All it does is produce worse code, and the > description even says so. > > As I said, gcc has treated the former code as idiomatic since gcc 2, so that > support is beyond ancient. Well, we're *trying* to get clang supported, so the argument that gcc has always supported it and compiles correct code for it is not necessarily the whole story yet. The problem with "32 - shift" is that it really could generate garbage in situations where shift ends up being a constant zero.. That said, the fact that the other cases weren't changed (rol64/ror64/ror32) does make that argument less interesting. Unless there was some particular code that actively ended up using "rol32(..0)" but not the other cases. (And yes, rol32(x,0) is obviously nonsense, but it could easily happen with inline functions or macros that end up generating that). Note that there may be 8 "rol/ror" functions, but the 16-bit and 8-bit ones don't have the undefined semantics. So there are only four that had _that_ problem, although I agree that changing just one out of four is wrong. Linus -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Wed, May 4, 2016 at 7:06 PM, Andi Kleen <andi@firstfloor.org> wrote: > On Wed, May 04, 2016 at 03:06:04PM -0700, John Denker wrote: >> On 05/04/2016 02:56 PM, H. Peter Anvin wrote: >> >> Beware that shifting by an amount >= the number of bits in the >> >> word remains Undefined Behavior. >> >> > This construct has been supported as a rotate since at least gcc2. >> >> How then should we understand the story told in commit d7e35dfa? >> Is the story wrong? > > I don't think Linux runs on a system where it would make a difference > (like a VAX), and also gcc always converts it before it could. > Even UBSan should not complain because it runs after the conversion > to ROTATE. > From what I understand, its a limitation in the barrel shifter and the way the shift bits are handled. Linux runs on a great number of devices, so its conceivable (likely?) a low-cost board would have hardware limitations that not found in modern desktops and servers or VAX. Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On May 4, 2016 6:20:32 PM PDT, Jeffrey Walton <noloader@gmail.com> wrote: >On Wed, May 4, 2016 at 7:06 PM, Andi Kleen <andi@firstfloor.org> wrote: >> On Wed, May 04, 2016 at 03:06:04PM -0700, John Denker wrote: >>> On 05/04/2016 02:56 PM, H. Peter Anvin wrote: >>> >> Beware that shifting by an amount >= the number of bits in the >>> >> word remains Undefined Behavior. >>> >>> > This construct has been supported as a rotate since at least gcc2. >>> >>> How then should we understand the story told in commit d7e35dfa? >>> Is the story wrong? >> >> I don't think Linux runs on a system where it would make a difference >> (like a VAX), and also gcc always converts it before it could. >> Even UBSan should not complain because it runs after the conversion >> to ROTATE. >> >From what I understand, its a limitation in the barrel shifter and the >way the shift bits are handled. > >Linux runs on a great number of devices, so its conceivable (likely?) >a low-cost board would have hardware limitations that not found in >modern desktops and servers or VAX. > >Jeff This is a compiler feature, though. And if icc or clang don't support the idiom they would never have compiled a working kernel.
On 05/04/2016 08:30 PM, H. Peter Anvin wrote: > On 05/04/16 15:06, John Denker wrote: >> On 05/04/2016 02:56 PM, H. Peter Anvin wrote: >>>> Beware that shifting by an amount >= the number of bits in the >>>> word remains Undefined Behavior. >> >>> This construct has been supported as a rotate since at least gcc2. >> >> How then should we understand the story told in commit d7e35dfa? >> Is the story wrong? >> >> At the very least, something inconsistent is going on. There >> are 8 functions. Why did d7e35dfa change one of them but >> not the other 7? > > Yes. d7e35dfa is baloney IMNSHO. All it does is produce worse code, and the description even says so. No, the description says that it produces worse code for *really really* ancient GCC versions. > As I said, gcc has treated the former code as idiomatic since gcc 2, so that support is beyond ancient. Because something works in a specific way on one compiler isn't a reason to ignore this noncompliance with the standard. Thanks, Sasha -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On 05/04/2016 08:48 PM, Linus Torvalds wrote: > That said, the fact that the other cases weren't changed > (rol64/ror64/ror32) does make that argument less interesting. Unless > there was some particular code that actively ended up using > "rol32(..0)" but not the other cases. Right, the others seemed wrong as well but I couldn't find any code that triggers that, and preferred to fix just the one I was hitting. I can go fix the rest if that's something we want to do? Thanks, Sasha -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On May 6, 2016 1:07:13 PM PDT, Sasha Levin <sasha.levin@oracle.com> wrote: >On 05/04/2016 08:30 PM, H. Peter Anvin wrote: >> On 05/04/16 15:06, John Denker wrote: >>> On 05/04/2016 02:56 PM, H. Peter Anvin wrote: >>>>> Beware that shifting by an amount >= the number of bits in the >>>>> word remains Undefined Behavior. >>> >>>> This construct has been supported as a rotate since at least gcc2. >>> >>> How then should we understand the story told in commit d7e35dfa? >>> Is the story wrong? >>> >>> At the very least, something inconsistent is going on. There >>> are 8 functions. Why did d7e35dfa change one of them but >>> not the other 7? >> >> Yes. d7e35dfa is baloney IMNSHO. All it does is produce worse code, >and the description even says so. > >No, the description says that it produces worse code for *really >really* ancient >GCC versions. > >> As I said, gcc has treated the former code as idiomatic since gcc 2, >so that support is beyond ancient. > >Because something works in a specific way on one compiler isn't a >reason to >ignore this noncompliance with the standard. > > >Thanks, >Sasha 4.6.2 is not "really, really ancient."
On May 6, 2016 1:07:13 PM PDT, Sasha Levin <sasha.levin@oracle.com> wrote: >On 05/04/2016 08:30 PM, H. Peter Anvin wrote: >> On 05/04/16 15:06, John Denker wrote: >>> On 05/04/2016 02:56 PM, H. Peter Anvin wrote: >>>>> Beware that shifting by an amount >= the number of bits in the >>>>> word remains Undefined Behavior. >>> >>>> This construct has been supported as a rotate since at least gcc2. >>> >>> How then should we understand the story told in commit d7e35dfa? >>> Is the story wrong? >>> >>> At the very least, something inconsistent is going on. There >>> are 8 functions. Why did d7e35dfa change one of them but >>> not the other 7? >> >> Yes. d7e35dfa is baloney IMNSHO. All it does is produce worse code, >and the description even says so. > >No, the description says that it produces worse code for *really >really* ancient >GCC versions. > >> As I said, gcc has treated the former code as idiomatic since gcc 2, >so that support is beyond ancient. > >Because something works in a specific way on one compiler isn't a >reason to >ignore this noncompliance with the standard. > > >Thanks, >Sasha When the compiler in question is our flagship target and our reference compiler, then yes, it matters.
commit 03b97eeb5401ede1e1d7b6fbf6a9575db8d0efa6
Author: John Denker <jsd@av8n.com>
Date: Wed May 4 13:55:51 2016 -0700
Make ror64, rol64, ror32, ror16, rol16, ror8, and rol8
consistent with rol32 in their handling of shifting by a zero amount.
Same overall rationale as in d7e35dfa, just more consistently applied.
Beware that shifting by an amount >= the number of bits in the
word remains Undefined Behavior. This should be either documented
or fixed. It could be fixed easily enough.
diff --git a/include/linux/bitops.h b/include/linux/bitops.h
index defeaac..97096b4 100644
--- a/include/linux/bitops.h
+++ b/include/linux/bitops.h
@@ -87,7 +87,7 @@ static __always_inline unsigned long hweight_long(unsigned long w)
*/
static inline __u64 rol64(__u64 word, unsigned int shift)
{
- return (word << shift) | (word >> (64 - shift));
+ return (word << shift) | (word >> ((-shift) & 64));
}
/**
@@ -97,7 +97,7 @@ static inline __u64 rol64(__u64 word, unsigned int shift)
*/
static inline __u64 ror64(__u64 word, unsigned int shift)
{
- return (word >> shift) | (word << (64 - shift));
+ return (word >> shift) | (word << ((-shift) & 64));
}
/**
@@ -117,7 +117,7 @@ static inline __u32 rol32(__u32 word, unsigned int shift)
*/
static inline __u32 ror32(__u32 word, unsigned int shift)
{
- return (word >> shift) | (word << (32 - shift));
+ return (word >> shift) | (word << ((-shift) & 31));
}
/**
@@ -127,7 +127,7 @@ static inline __u32 ror32(__u32 word, unsigned int shift)
*/
static inline __u16 rol16(__u16 word, unsigned int shift)
{
- return (word << shift) | (word >> (16 - shift));
+ return (word << shift) | (word >> ((-shift) & 16));
}
/**
@@ -137,7 +137,7 @@ static inline __u16 rol16(__u16 word, unsigned int shift)
*/
static inline __u16 ror16(__u16 word, unsigned int shift)
{
- return (word >> shift) | (word << (16 - shift));
+ return (word >> shift) | (word << ((-shift) & 16));
}
/**
@@ -147,7 +147,7 @@ static inline __u16 ror16(__u16 word, unsigned int shift)
*/
static inline __u8 rol8(__u8 word, unsigned int shift)
{
- return (word << shift) | (word >> (8 - shift));
+ return (word << shift) | (word >> ((-shift) & 8));
}
/**
@@ -157,7 +157,7 @@ static inline __u8 rol8(__u8 word, unsigned int shift)
*/
static inline __u8 ror8(__u8 word, unsigned int shift)
{
- return (word >> shift) | (word << (8 - shift));
+ return (word >> shift) | (word << ((-shift) & 8));
}
/**