Re: linux/bitops.h
On May 6, 2016 1:07:13 PM PDT, Sasha Levin 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. -- Sent from my Android device with K-9 Mail. Please excuse brevity and formatting. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: linux/bitops.h
On May 6, 2016 1:07:13 PM PDT, Sasha Levin 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." -- Sent from my Android device with K-9 Mail. Please excuse brevity and formatting. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: linux/bitops.h
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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: linux/bitops.h
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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: UB in general ... and linux/bitops.h in particular
>-- Perhaps the compiler guys could be persuaded to support > the needed features explicitly, perhaps via a command-line > option: -std=vanilla > This should be a no-cost option as things stand today, but > it helps to prevent nasty surprises in the future. It looks LLVM has the -rainbow option; see http://blog.llvm.org/2016/04/undefined-behavior-is-magic.html :) Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On 05/05/2016 03:18 PM, ty...@mit.edu wrote: > > So this is why I tend to take a much more pragmatic viewpoint on > things. Sure, it makes sense to pay attention to what the C standard > writers are trying to do to us; but if we need to suppress certain > optimizations to write sane kernel code --- I'm ok with that. And > this is why using a trust-but-verify on a specific set of compilers > and ranges of compiler versions is a really good idea > For the record, the "portable" construct has apparently only been supported since gcc 4.6.3. -hpa -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On May 5, 2016 3:18:09 PM PDT, ty...@mit.edu wrote: >On Thu, May 05, 2016 at 05:34:50PM -0400, Sandy Harris wrote: >> >> I completely fail to see why tests or compiler versions should be >> part of the discussion. The C standard says the behaviour in >> certain cases is undefined, so a standard-compliant compiler >> can generate more-or-less any code there. >> > >> As long as any of portability, reliability or security are among our >> goals, any code that can give undefined behaviour should be >> considered problematic. > >Because compilers have been known not necessarily to obey the specs, >and/or interpret the specs in way that not everyone agrees with. It's >also the case that we are *already* disabling certain C optimizations >which are technically allowed by the spec, but which kernel >programmers consider insane (e.g., strict aliasing). > >And of course, memzero_explicit() which crypto people understand is >necessary, is something that technically compilers are allowed to >optimize according to the spec. So trying to write secure kernel code >which will work on arbitrary compilers may well be impossible. > >And which is also why people have said (mostly in jest), "A >sufficiently advanced compiler is indistinguishable from an >adversary." (I assume people will agree that optimizing away a memset >needed to clear secrets from memory would be considered adversarial, >at the very least!) > >So this is why I tend to take a much more pragmatic viewpoint on >things. Sure, it makes sense to pay attention to what the C standard >writers are trying to do to us; but if we need to suppress certain >optimizations to write sane kernel code --- I'm ok with that. And >this is why using a trust-but-verify on a specific set of compilers >and ranges of compiler versions is a really good idea > >- Ted I have filed a gcc bug to have the preexisting rotate idiom officially documented as a GNU C extension. https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70967 -- Sent from my Android device with K-9 Mail. Please excuse brevity and formatting. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On 05/05/2016 03:18 PM, ty...@mit.edu wrote: > On Thu, May 05, 2016 at 05:34:50PM -0400, Sandy Harris wrote: >> >> I completely fail to see why tests or compiler versions should be >> part of the discussion. The C standard says the behaviour in >> certain cases is undefined, so a standard-compliant compiler >> can generate more-or-less any code there. >> > >> As long as any of portability, reliability or security are among our >> goals, any code that can give undefined behaviour should be >> considered problematic. > > Because compilers have been known not necessarily to obey the specs, > and/or interpret the specs in way that not everyone agrees with. It's > also the case that we are *already* disabling certain C optimizations > which are technically allowed by the spec, but which kernel > programmers consider insane (e.g., strict aliasing). > > And of course, memzero_explicit() which crypto people understand is > necessary, is something that technically compilers are allowed to > optimize according to the spec. So trying to write secure kernel code > which will work on arbitrary compilers may well be impossible. > > And which is also why people have said (mostly in jest), "A > sufficiently advanced compiler is indistinguishable from an > adversary." (I assume people will agree that optimizing away a memset > needed to clear secrets from memory would be considered adversarial, > at the very least!) > > So this is why I tend to take a much more pragmatic viewpoint on > things. Sure, it makes sense to pay attention to what the C standard > writers are trying to do to us; but if we need to suppress certain > optimizations to write sane kernel code --- I'm ok with that. And > this is why using a trust-but-verify on a specific set of compilers > and ranges of compiler versions is a really good idea > In theory, theory and practice should agree, but in practice, practice is what counts. I fully agree we should get rid of UD behavior where doing so is practical, but not at the cost of breaking real-life compilers, expecially not gcc, and to a lesser but still very real extent icc and clang. I would also agree that we should push the gcc developers to add to the manual C-standard-UD behavior which are well-defined under the gnu89/gnu99/gnu11 C dialects. -hpa -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On Thu, May 05, 2016 at 05:34:50PM -0400, Sandy Harris wrote: > > I completely fail to see why tests or compiler versions should be > part of the discussion. The C standard says the behaviour in > certain cases is undefined, so a standard-compliant compiler > can generate more-or-less any code there. > > As long as any of portability, reliability or security are among our > goals, any code that can give undefined behaviour should be > considered problematic. Because compilers have been known not necessarily to obey the specs, and/or interpret the specs in way that not everyone agrees with. It's also the case that we are *already* disabling certain C optimizations which are technically allowed by the spec, but which kernel programmers consider insane (e.g., strict aliasing). And of course, memzero_explicit() which crypto people understand is necessary, is something that technically compilers are allowed to optimize according to the spec. So trying to write secure kernel code which will work on arbitrary compilers may well be impossible. And which is also why people have said (mostly in jest), "A sufficiently advanced compiler is indistinguishable from an adversary." (I assume people will agree that optimizing away a memset needed to clear secrets from memory would be considered adversarial, at the very least!) So this is why I tend to take a much more pragmatic viewpoint on things. Sure, it makes sense to pay attention to what the C standard writers are trying to do to us; but if we need to suppress certain optimizations to write sane kernel code --- I'm ok with that. And this is why using a trust-but-verify on a specific set of compilers and ranges of compiler versions is a really good idea - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On Wed, May 4, 2016 at 11:50 PM, Theodore Ts'o wrote: > Instead of arguing over who's "sane" or "insane", can we come up with > a agreed upon set of tests, and a set of compiler and compiler > versions ... I completely fail to see why tests or compiler versions should be part of the discussion. The C standard says the behaviour in certain cases is undefined, so a standard-compliant compiler can generate more-or-less any code there. As long as any of portability, reliability or security are among our goals, any code that can give undefined behaviour should be considered problematic. > But instead of arguing over what works and doesn't, let's just create > the the test set and just try it on a wide range of compilers and > architectures, hmmm? No. Let's just fix the code so that undefined behaviour cannot occur. Creating test cases for a fix and trying them on a range of systems would be useful, perhaps essential, work. Doing tests without a fix would be a complete waste of time. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: UB in general ... and linux/bitops.h in particular
> Suggestions: > > a) Going forward, I suggest that UB should not be invoked > unless there is a good solid reason. Good luck rewriting most of the kernel source. This discussion is insane! -Andi -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: UB in general ... and linux/bitops.h in particular
On 05/04/2016 11:35 PM, H. Peter Anvin wrote: > The disagreement here is the priority between these points. Yes. As usual, all the extremes are wrong. Tradeoffs must be made. Perspective and judgment are required. > In my very strong opinion, "no undefined behavior" per the C standard > is way less important than the others; what matters is what gcc and > the other compilers we care about do. But we don't control what the compilers do. The gcc guys have a track record of assuming that UB gives them a license to do whatever they want. At any moment they can change their mind and do something new. > The kernel relies on various versions of C-standard-undefined > behavior *all over the place*;> One should be careful with that argument. Not all types of UB are created equal. There is a world of difference between -- UB_type_1 used "all over the place" by necessity, and -- UB_type_2 used here-and-there for convenience. UB_type_1 defines a de_facto dialect of the language. Ideally there would be a formal specification of the dialect, but that's not super-urgent, because the compiler guys are probably not crazy enough to break something if it really is used "all over the place". Formalized or not, UB_type_1 does not make it OK for programmers to invoke *other* types of UB. I'll say it again: the gcc guys have a track record of assuming UB gives them a license to do whatever they want. The results can be very counterintuitive. UB is a nightmare from the point of view of reliability, security, and maintainability. The fact that your favorite compiler does what you want as of today is *not* a guarantee that it will do so in the future. === As for the suggestion that the UB code is somehow more efficient or in any way better, I'm not buying it. Using gcc 5.2.1 I observe that [1] and [2] (given below) generate the exact same code at any optimization level from -O1 on up. My kernel is compiled with -O2. (They generate different code with -O0 but that doesn't seem like an important consideration.) The relevant code is (word >> shift) | (word >> ((-shift) & 31)); /* [1] */ (word >> shift) | (word << (32 - shift)); /* [2] */ > for one thing sizeof(void *) == sizeof(size_t) == sizeof(unsigned long)!! I assume that comes up in the context of type punning. I am not a language lawyer, but it is my understanding that type punning *is* permitted by the C language specification. (C++ is another story entirely, but not relevant here.) There is a world of difference between -- loosely specified options (LSO), and -- undefined behavior (UB) The sizeof() example is LSO not UB. One could easily check the sizes at compile time, so that no looseness remains. The result is perfectly reasonable, efficient, reliable code. Similarly, the kernel assumes two's complement arithmetic "all over the place" but this is LSO not UB. This is relevant to linux/bitops.h because [2] is UB when shift==0. In contrast [1] is a very mild example of LSO because it assumes two's complement. I consider it a step in the right direction to get rid of UB when it can be done at zero cost. UB is dangerous. == Suggestions: a) Going forward, I suggest that UB should not be invoked unless there is a good solid reason. b) In cases where a this-or-that UB really is needed, it should be carefully documented. -- Perhaps there could be a file linux_kernel_dialect.c that gives examples of all the constructs that the kernel needs but are not in the basic C specification. One would hope this would be very, very short. -- Perhaps the compiler guys could be persuaded to support the needed features explicitly, perhaps via a command-line option: -std=vanilla This should be a no-cost option as things stand today, but it helps to prevent nasty surprises in the future. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On 05/04/16 21:03, Jeffrey Walton wrote: On Wed, May 4, 2016 at 11:50 PM, Theodore Ts'o wrote: ... But instead of arguing over what works and doesn't, let's just create the the test set and just try it on a wide range of compilers and architectures, hmmm? What are the requirements? Here's a short list: * No undefined behavior - important because the compiler writers use the C standard * Compiles to native "rotate IMMEDIATE" if the rotate amount is a "constant expression" and the machine provides it - translates to a native rotate instruction if available - "rotate IMM" can be 3 times faster than "rotate REG" - do any architectures *not* provide a rotate? * Compiles to native "rotate REGISTER" if the rotate is variable and the machine provides it - do any architectures *not* provide a rotate? * Constant time - important to high-integrity code - Non-security code paths probably don't care Maybe the first thing to do is provide a different rotates for the constant-time requirement when its in effect? The disagreement here is the priority between these points. In my very strong opinion, "no undefined behavior" per the C standard is way less important than the others; what matters is what gcc and the other compilers we care about do. The kernel relies on various versions of C-standard-undefined behavior *all over the place*; for one thing sizeof(void *) == sizeof(size_t) == sizeof(unsigned long)!! but they are well-defined in the subcontext we care about. (And no, not all architectures provide a rotate instruction.) -hpa -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On Wed, May 4, 2016 at 11:50 PM, Theodore Ts'o wrote: > ... > But instead of arguing over what works and doesn't, let's just create > the the test set and just try it on a wide range of compilers and > architectures, hmmm? What are the requirements? Here's a short list: * No undefined behavior - important because the compiler writers use the C standard * Compiles to native "rotate IMMEDIATE" if the rotate amount is a "constant expression" and the machine provides it - translates to a native rotate instruction if available - "rotate IMM" can be 3 times faster than "rotate REG" - do any architectures *not* provide a rotate? * Compiles to native "rotate REGISTER" if the rotate is variable and the machine provides it - do any architectures *not* provide a rotate? * Constant time - important to high-integrity code - Non-security code paths probably don't care Maybe the first thing to do is provide a different rotates for the constant-time requirement when its in effect? Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
Instead of arguing over who's "sane" or "insane", can we come up with a agreed upon set of tests, and a set of compiler and compiler versions for which these tests must achieve at least *working* code? Bonus points if they achieve optimal code, but what's important is that for a wide range of GCC versions (from ancient RHEL distributions to bleeding edge gcc 5.x compilers) this *must* work. >From my perspective, clang and ICC producing corret code is a very nice to have, but most shops I know of don't yet assume that clang produces code that is trustworthy for production systems, although it *is* great for as far as generating compiler warnings to find potential bugs. But instead of arguing over what works and doesn't, let's just create the the test set and just try it on a wide range of compilers and architectures, hmmm? - Ted -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
>>> So you are actually saying outright that we should sacrifice *actual* >>portability in favor of *theoretical* portability? What kind of >>twilight zone did we just step into?! >> >>I'm not sure what you mean. It will be well defined on all platforms. >>Clang may not recognize the pattern, which means they could run >>slower. GCC and ICC will be fine. >> >>Slower but correct code is what you have to live with until the Clang >>dev's fix their compiler. >> >>Its kind of like what Dr. Jon Bentley said: "If it doesn't have to be >>correct, I can make it as fast as you'd like it to be". > > The current code works on all compilers we care about. The code you propose > does not; it doesn't work on anything but very recent versions of our > flagship target compiler, and pretty your own admission might even cause > security hazards in the kernel if compiled on clang. I'm not sure how you're arriving at the conclusion the code does not work. > That qualifies as insane in my book. OK, thanks. I see the kernel is providing IPSec, SSL/TLS, etc. You can make SSL/TLS run faster by using aNULL and eNULL. Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On May 4, 2016 7:54:12 PM PDT, Jeffrey Walton wrote: >On Wed, May 4, 2016 at 10:41 PM, H. Peter Anvin wrote: >> On May 4, 2016 6:35:44 PM PDT, Jeffrey Walton >wrote: >>>On Wed, May 4, 2016 at 5:52 PM, John Denker wrote: On 05/04/2016 02:42 PM, I wrote: > 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. Here's a replacement patch. ... >>> >>>+1, commit it. >>> >>>Its good for three additional reasons. First, this change means the >>>kernel is teaching the next generation the correct way to do things. >>>Many developers aspire to be kernel hackers, and they sometimes use >>>the code from bitops.h. I've actually run across the code in >>>production during an audit where the developers cited bitops.h. >>> >>>Second, it preserves a "silent and dark" cockpit during analysis. >That >>>is, when analysis is run, no findings are generated. Auditors and >>>security folks like quiet tools, much like the way pilots like their >>>cockpits (flashing lights and sounding buzzers usually means >something >>>is wrong). >>> >>>Third, the pattern is recognized by the major compilers, so the >kernel >>>should not have any trouble when porting any of the compilers. I >often >>>use multiple compiler to tease out implementation defined behavior in >>>a effort to achieve greater portability. Here are the citations to >>>ensure the kernel is safe with the pattern: >>> >>> * GCC: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157 >>> * ICC: http://software.intel.com/en-us/forums/topic/580884 >>> >>>However, Clang may cause trouble because they don't want the >>>responsibility of recognizing the pattern: >>> >>> * https://llvm.org/bugs/show_bug.cgi?id=24226#c8 >>> >>>Instead, they provide a defective rotate. The "defect" here is its >>>non-constant time due to the branch, so it may not be suitable for >>>high-integrity or high-assurance code like linux-crypto: >>> >>> * https://llvm.org/bugs/show_bug.cgi?id=24226#c5 >>> >>>Jeff >> >> So you are actually saying outright that we should sacrifice *actual* >portability in favor of *theoretical* portability? What kind of >twilight zone did we just step into?! > >I'm not sure what you mean. It will be well defined on all platforms. >Clang may not recognize the pattern, which means they could run >slower. GCC and ICC will be fine. > >Slower but correct code is what you have to live with until the Clang >dev's fix their compiler. > >Its kind of like what Dr. Jon Bentley said: "If it doesn't have to be >correct, I can make it as fast as you'd like it to be". > >Jeff The current code works on all compilers we care about. The code you propose does not; it doesn't work on anything but very recent versions of our flagship target compiler, and pretty your own admission might even cause security hazards in the kernel if compiled on clang. That qualifies as insane in my book. The church code is de facto portable with the intended outcome, the one you propose is not. -- Sent from my Android device with K-9 Mail. Please excuse brevity and formatting. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On Wed, May 4, 2016 at 10:41 PM, H. Peter Anvin wrote: > On May 4, 2016 6:35:44 PM PDT, Jeffrey Walton wrote: >>On Wed, May 4, 2016 at 5:52 PM, John Denker wrote: >>> On 05/04/2016 02:42 PM, I wrote: >>> 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. >>> >>> Here's a replacement patch. >>> ... >> >>+1, commit it. >> >>Its good for three additional reasons. First, this change means the >>kernel is teaching the next generation the correct way to do things. >>Many developers aspire to be kernel hackers, and they sometimes use >>the code from bitops.h. I've actually run across the code in >>production during an audit where the developers cited bitops.h. >> >>Second, it preserves a "silent and dark" cockpit during analysis. That >>is, when analysis is run, no findings are generated. Auditors and >>security folks like quiet tools, much like the way pilots like their >>cockpits (flashing lights and sounding buzzers usually means something >>is wrong). >> >>Third, the pattern is recognized by the major compilers, so the kernel >>should not have any trouble when porting any of the compilers. I often >>use multiple compiler to tease out implementation defined behavior in >>a effort to achieve greater portability. Here are the citations to >>ensure the kernel is safe with the pattern: >> >> * GCC: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157 >> * ICC: http://software.intel.com/en-us/forums/topic/580884 >> >>However, Clang may cause trouble because they don't want the >>responsibility of recognizing the pattern: >> >> * https://llvm.org/bugs/show_bug.cgi?id=24226#c8 >> >>Instead, they provide a defective rotate. The "defect" here is its >>non-constant time due to the branch, so it may not be suitable for >>high-integrity or high-assurance code like linux-crypto: >> >> * https://llvm.org/bugs/show_bug.cgi?id=24226#c5 >> >>Jeff > > So you are actually saying outright that we should sacrifice *actual* > portability in favor of *theoretical* portability? What kind of twilight > zone did we just step into?! I'm not sure what you mean. It will be well defined on all platforms. Clang may not recognize the pattern, which means they could run slower. GCC and ICC will be fine. Slower but correct code is what you have to live with until the Clang dev's fix their compiler. Its kind of like what Dr. Jon Bentley said: "If it doesn't have to be correct, I can make it as fast as you'd like it to be". Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On May 4, 2016 6:35:44 PM PDT, Jeffrey Walton wrote: >On Wed, May 4, 2016 at 5:52 PM, John Denker wrote: >> On 05/04/2016 02:42 PM, I wrote: >> >>> 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. >> >> Here's a replacement patch. >> ... > >+1, commit it. > >Its good for three additional reasons. First, this change means the >kernel is teaching the next generation the correct way to do things. >Many developers aspire to be kernel hackers, and they sometimes use >the code from bitops.h. I've actually run across the code in >production during an audit where the developers cited bitops.h. > >Second, it preserves a "silent and dark" cockpit during analysis. That >is, when analysis is run, no findings are generated. Auditors and >security folks like quiet tools, much like the way pilots like their >cockpits (flashing lights and sounding buzzers usually means something >is wrong). > >Third, the pattern is recognized by the major compilers, so the kernel >should not have any trouble when porting any of the compilers. I often >use multiple compiler to tease out implementation defined behavior in >a effort to achieve greater portability. Here are the citations to >ensure the kernel is safe with the pattern: > > * GCC: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157 > * ICC: http://software.intel.com/en-us/forums/topic/580884 > >However, Clang may cause trouble because they don't want the >responsibility of recognizing the pattern: > > * https://llvm.org/bugs/show_bug.cgi?id=24226#c8 > >Instead, they provide a defective rotate. The "defect" here is its >non-constant time due to the branch, so it may not be suitable for >high-integrity or high-assurance code like linux-crypto: > > * https://llvm.org/bugs/show_bug.cgi?id=24226#c5 > >Jeff So you are actually saying outright that we should sacrifice *actual* portability in favor of *theoretical* portability? What kind of twilight zone did we just step into?! -- Sent from my Android device with K-9 Mail. Please excuse brevity and formatting. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On Wed, May 4, 2016 at 5:52 PM, John Denker wrote: > On 05/04/2016 02:42 PM, I wrote: > >> 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. > > Here's a replacement patch. > ... +1, commit it. Its good for three additional reasons. First, this change means the kernel is teaching the next generation the correct way to do things. Many developers aspire to be kernel hackers, and they sometimes use the code from bitops.h. I've actually run across the code in production during an audit where the developers cited bitops.h. Second, it preserves a "silent and dark" cockpit during analysis. That is, when analysis is run, no findings are generated. Auditors and security folks like quiet tools, much like the way pilots like their cockpits (flashing lights and sounding buzzers usually means something is wrong). Third, the pattern is recognized by the major compilers, so the kernel should not have any trouble when porting any of the compilers. I often use multiple compiler to tease out implementation defined behavior in a effort to achieve greater portability. Here are the citations to ensure the kernel is safe with the pattern: * GCC: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57157 * ICC: http://software.intel.com/en-us/forums/topic/580884 However, Clang may cause trouble because they don't want the responsibility of recognizing the pattern: * https://llvm.org/bugs/show_bug.cgi?id=24226#c8 Instead, they provide a defective rotate. The "defect" here is its non-constant time due to the branch, so it may not be suitable for high-integrity or high-assurance code like linux-crypto: * https://llvm.org/bugs/show_bug.cgi?id=24226#c5 Jeff -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: linux/bitops.h
On May 4, 2016 6:20:32 PM PDT, Jeffrey Walton wrote: >On Wed, May 4, 2016 at 7:06 PM, Andi Kleen 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. -- Sent from my Android device with K-9 Mail. Please excuse brevity and formatting. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: linux/bitops.h
On Wed, May 4, 2016 at 7:06 PM, Andi Kleen 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: linux/bitops.h
On Wed, May 4, 2016 at 5:30 PM, H. Peter Anvin 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: linux/bitops.h
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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: linux/bitops.h
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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: linux/bitops.h
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 -- a...@linux.intel.com -- Speaking for myself only. -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: linux/bitops.h
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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: better patch for linux/bitops.h
On 05/04/2016 02:42 PM, I wrote: > 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. Here's a replacement patch. Same idea, less brain damage. Sorry for the confusion. commit ba83b16d8430ee6104aa1feeed4ff7a82b02747a Author: John Denker 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..90f389b 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) & 63)); } /** @@ -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) & 63)); } /** @@ -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) & 15)); } /** @@ -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) & 15)); } /** @@ -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) & 7)); } /** @@ -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) & 7)); } /**