9 ms·

Since it hasn't been mentioned yet, I'll point out that the article is about how hardware processors react to assembly level shifts with greater than register s

by nkurz 3y ago

Since it hasn't been mentioned yet, I'll point out that the article is about how hardware processors react to assembly level shifts with greater than register size. Unless you are programming directly in assembly, the most important take-home from the article is probably the "Bonus chatter" at the end: shifts equal to or greater than register size are undefined in C and C++. How the CPU would handle the theoretical assembly instruction is usually of little importance when demons are flying out of your nose. Here's Regehr on some of the standard ways to protect yourself from a malicious or overzealous compiler when you need to have a function that does variable sized rotations: https://blog.regehr.org/archives/1063 https://blog.regehr.org/archives/1063

fao_ 3y ago
I mean, I feel a sane reading of the C Standard means reading "undefined" as "unspecified by the standard, but dependent on the trust and common sense of the compiler authors" -- which, you know, I don't know that that's any worse than "dependent on the trust and common sense of the npm package author" or "dependent on the trust and common sense of the rust cargo maintainer". Like, yes theoretically the compiler can do anything, but tangibly, coherently, most compilers deal with most UB in a sane way.
- loup-vaillant 3y ago
  > but tangibly, coherently, most compilers deal with most UB in a sane way. It depends. In some cases, really, no they do not. Compilers have been caught deleting security checks when they noticed that the only way to reach the error case was to trigger UB… and since "UB doesn't exist", the error case is considered dead, and the whole test is deleted. Sometimes this leads to remote code execution vulnerabilities, that if exploited could actually result in your hard drive being encrypted, or a keylogger being installed. UB is really, really scary.
  - bippihippi1 3y ago
    cite source?
    - dzaima 3y ago
      Here's one case: https://godbolt.org/z/aM89Eqs3v https://godbolt.org/z/aM89Eqs3v - the 'p == NULL' check is gone. Not directly harmful if the null page is inaccessible (which it's gonna be for most user-space stuff), but if it's accessible, it's quite bad. (and, fwiw, there's -fno-delete-null-pointer-checks to stop the compilers from doing this) And another commonly mentioned one: https://godbolt.org/z/6bf17W1Ee https://godbolt.org/z/6bf17W1Ee
  - maccard 3y ago
    > Sometimes this leads to remote code execution vulnerabilities, that if exploited could actually result in your hard drive being encrypted, or a keylogger being installed. Have you got a link to a CVE of an RCE that was caused by UB being exploited by an optimizer? Im with you that UB is dangerous, but let's be honest in 98% of situations it's correct to assume that integer overflow can't happen, and that if you pass a pointer into a function and don't check it that the call site has checked it.
    - loup-vaillant 3y ago
      No link, but I do recall a CVE talking about a buffer overflow vulnerability that could be traced back to a bounds check being removed by the compiler because the only way to go out of bounds was to overflow a signed integer. (Signed integer overflow is UB, and "UB does not exist", so the check was "dead".)
    - tedunangst 3y ago
      The Linux kernel used to have lots of deref then null check bugs, but you could map memory at address zero, controlling what should have been kernel memory.
  - fao_ 3y ago
    Right, and that's a breach of the social contract vis a vis compiler authors and the language users, which is a social problem. The lack of safety here is because the GNU programmers detect the UB and decide to cowboy it. If you take the time to actually read Annex J of the C language you'll see that most of what is intended by "UB" is just "The language or platform could be buggy or the spec could be weird".
- fanf2 3y ago
  This is not true in fact or in practice. For example, a compiler can assume that a variable sized shift is in range, then use value range propagation to eliminate tests, which can be very confusing if you expect the shift to be implicitly & 63.
- kibwen 3y ago
  > I don't know that that's any worse than "dependent on the trust and common sense of the npm package author" or "dependent on the trust and common sense of the rust cargo maintainer" You don't need to rely on the trust and common sense of anyone in those cases, because oversized shifts aren't undefined behavior in Javascript or Rust. If C (or C++, or any other language) wants the same benefit, they can just say that it's not undefined behavior, and thereby require implementations to define the behavior somehow. And "backwards compatibility" isn't an excuse here: UB means that, currently, anything can happen, so having the standard specify that one particular thing happens is an entirely backwards-compatible change.
- userbinator 3y ago
  but tangibly, coherently, most compilers deal with most UB in a sane way. They used to, but unfortunately increasingly not so much now. (Since the most popular ones are open-source, we should theoretically have the power to change that.)
- taway1237 3y ago
  >Like, yes theoretically the compiler can do anything, but tangibly, coherently, most compilers deal with most UB in a sane way. I have to disagree - I do a lot of hacky low-level stuff, and C/C++ compilers love to "break" my code. I mean they have a right to, because I know it's technically UB, but I end up playing a game with the compiler where I "trick" it so it doesn't notice the UB and delete my whole function silently.
somat 3y ago
See this is where undefined got lost somewhere. As a layman undefined appears to mean a specific thing here. "undefined by the specification because it does whatever the hardware does" in this context it should never mean "can not happen because it is undefined by the specification". Heck, I don't think it should mean that in any context. whenever a thing is undefined, it is almost always because there is varying hardware that the specification is trying to accommodate.
- inetknght 3y ago
  > As a layman undefined appears to mean a specific thing here. "undefined by the specification because it does whatever the hardware does" in this context it should never mean "can not happen because it is undefined by the specification". Actually, undefined means "undefined by the specification". It doesn't matter what the hardware does. The specification allows the hardware to do whatever it wants. It's perfectly valid to wipe your hard drive if you trigger undefined behavior.
  - deleted 3y ago
    [deleted]
  - dunham 3y ago
    I also wouldn't expect "undefined" to be consistent within a single compiler implementation. The optimizer is free to make different instances behave differently.
    - Someone 3y ago
      A single compiler can even seem inconsistent. A conforming compiler is allowed to completely remove undefined behavior like this: if((n << 64) == 0) { println("Hi!\n"); } if((n << 64) != 0) { println("Hi!\n"); } If it were implementation-defined, it would have to compile it to the equivalent of println("Hi!\n");
      - deleted 3y ago
        [deleted]
zX41ZdbW 3y ago
There is an undefined behavior in the compiler and an undefined behavior in the CPU. For example, bsr/bsf instructions (count leading or trailing bits) have undefined behavior if the argument is zero. What I observed is that the CPU leaves the destination register unchanged in this case (but it can do something else according to the spec, for example - set it to zero). The compiler exposes these instructions for convenience as intrinsics __builtin_clz/__builtin_ctz, which consequently, have undefined behavior if the argument is zero. But you can use them directly as an optimization if you know in advance that the argument is non-zero: https://github.com/ClickHouse/ClickHouse/blob/c0a43df749c827ce13abb015faca4ad8ab524685/src/Common/BitHelpers.h#L35 https://github.com/ClickHouse/ClickHouse/blob/c0a43df749c827...
- Findecanor 3y ago
  `bsr` and `bsf` have "undefined" results on a zero argument in Intel's documentation. In AMD's documentation however, the destination is supposed to be "unchanged". What is unusual is that the 32-bit flavours of these instructions leave the upper 32 bits unchanged, whereas other 32-bit integer instructions write zeroes there even if the lower bits in the destination are unchanged. Perhaps Intel intends to make these instructions zero-extend in the future ... or does there exist some processor (from Intel or someone else) that zero-extends?
  - userbinator 3y ago
    In at least the early days of x86, it was common for AMD to document what Intel left undefined: https://news.ycombinator.com/item?id=25320603 https://news.ycombinator.com/item?id=25320603
almostnormal 3y ago
> Unless you are programming directly in assembly, the most important take-home from the article is probably the "Bonus chatter" at the end: shifts equal to or greater than register size are undefined in C and C++. The article claims UB only at greater but not at equal: > Bonus chatter: The wide variety of behavior when shifting by more than the register size is one of the reasons why the C and C++ languages leave undefined what happens when you shift by more than the bit width of the shifted type. If think your "equal to or greater" is correct, and the article is wrong. The reason might be that the instructions are defined up to including equal for many hardware. I remember checking one case that included equal as valid for only one of left/right shift and invalid for the other (left/right encoded in 5 bit signed).

by nkurz 3y ago

fao_ 3y ago

I mean, I feel a sane reading of the C Standard means reading "undefined" as "unspecified by the standard, but dependent on the trust and common sense of the compiler authors" -- which, you know, I don't know that that's any worse than "dependent on the trust and common sense of the npm package author" or "dependent on the trust and common sense of the rust cargo maintainer". Like, yes theoretically the compiler can do anything, but tangibly, coherently, most compilers deal with most UB in a sane way.

loup-vaillant 3y ago
> but tangibly, coherently, most compilers deal with most UB in a sane way. It depends. In some cases, really, no they do not. Compilers have been caught deleting security checks when they noticed that the only way to reach the error case was to trigger UB… and since "UB doesn't exist", the error case is considered dead, and the whole test is deleted. Sometimes this leads to remote code execution vulnerabilities, that if exploited could actually result in your hard drive being encrypted, or a keylogger being installed. UB is really, really scary.
- bippihippi1 3y ago
  cite source?
  - dzaima 3y ago
    Here's one case: https://godbolt.org/z/aM89Eqs3v https://godbolt.org/z/aM89Eqs3v - the 'p == NULL' check is gone. Not directly harmful if the null page is inaccessible (which it's gonna be for most user-space stuff), but if it's accessible, it's quite bad. (and, fwiw, there's -fno-delete-null-pointer-checks to stop the compilers from doing this) And another commonly mentioned one: https://godbolt.org/z/6bf17W1Ee https://godbolt.org/z/6bf17W1Ee
- maccard 3y ago
  > Sometimes this leads to remote code execution vulnerabilities, that if exploited could actually result in your hard drive being encrypted, or a keylogger being installed. Have you got a link to a CVE of an RCE that was caused by UB being exploited by an optimizer? Im with you that UB is dangerous, but let's be honest in 98% of situations it's correct to assume that integer overflow can't happen, and that if you pass a pointer into a function and don't check it that the call site has checked it.
  - loup-vaillant 3y ago
    No link, but I do recall a CVE talking about a buffer overflow vulnerability that could be traced back to a bounds check being removed by the compiler because the only way to go out of bounds was to overflow a signed integer. (Signed integer overflow is UB, and "UB does not exist", so the check was "dead".)
  - tedunangst 3y ago
    The Linux kernel used to have lots of deref then null check bugs, but you could map memory at address zero, controlling what should have been kernel memory.
- fao_ 3y ago
  Right, and that's a breach of the social contract vis a vis compiler authors and the language users, which is a social problem. The lack of safety here is because the GNU programmers detect the UB and decide to cowboy it. If you take the time to actually read Annex J of the C language you'll see that most of what is intended by "UB" is just "The language or platform could be buggy or the spec could be weird".
fanf2 3y ago
This is not true in fact or in practice. For example, a compiler can assume that a variable sized shift is in range, then use value range propagation to eliminate tests, which can be very confusing if you expect the shift to be implicitly & 63.
kibwen 3y ago
> I don't know that that's any worse than "dependent on the trust and common sense of the npm package author" or "dependent on the trust and common sense of the rust cargo maintainer" You don't need to rely on the trust and common sense of anyone in those cases, because oversized shifts aren't undefined behavior in Javascript or Rust. If C (or C++, or any other language) wants the same benefit, they can just say that it's not undefined behavior, and thereby require implementations to define the behavior somehow. And "backwards compatibility" isn't an excuse here: UB means that, currently, anything can happen, so having the standard specify that one particular thing happens is an entirely backwards-compatible change.
userbinator 3y ago
but tangibly, coherently, most compilers deal with most UB in a sane way. They used to, but unfortunately increasingly not so much now. (Since the most popular ones are open-source, we should theoretically have the power to change that.)
taway1237 3y ago
>Like, yes theoretically the compiler can do anything, but tangibly, coherently, most compilers deal with most UB in a sane way. I have to disagree - I do a lot of hacky low-level stuff, and C/C++ compilers love to "break" my code. I mean they have a right to, because I know it's technically UB, but I end up playing a game with the compiler where I "trick" it so it doesn't notice the UB and delete my whole function silently.

somat 3y ago

See this is where undefined got lost somewhere. As a layman undefined appears to mean a specific thing here. "undefined by the specification because it does whatever the hardware does" in this context it should never mean "can not happen because it is undefined by the specification". Heck, I don't think it should mean that in any context. whenever a thing is undefined, it is almost always because there is varying hardware that the specification is trying to accommodate.

inetknght 3y ago
> As a layman undefined appears to mean a specific thing here. "undefined by the specification because it does whatever the hardware does" in this context it should never mean "can not happen because it is undefined by the specification". Actually, undefined means "undefined by the specification". It doesn't matter what the hardware does. The specification allows the hardware to do whatever it wants. It's perfectly valid to wipe your hard drive if you trigger undefined behavior.
- deleted 3y ago
  [deleted]
- dunham 3y ago
  I also wouldn't expect "undefined" to be consistent within a single compiler implementation. The optimizer is free to make different instances behave differently.
  - Someone 3y ago
    A single compiler can even seem inconsistent. A conforming compiler is allowed to completely remove undefined behavior like this: if((n << 64) == 0) { println("Hi!\n"); } if((n << 64) != 0) { println("Hi!\n"); } If it were implementation-defined, it would have to compile it to the equivalent of println("Hi!\n");
    - deleted 3y ago
      [deleted]

zX41ZdbW 3y ago

There is an undefined behavior in the compiler and an undefined behavior in the CPU. For example, bsr/bsf instructions (count leading or trailing bits) have undefined behavior if the argument is zero. What I observed is that the CPU leaves the destination register unchanged in this case (but it can do something else according to the spec, for example - set it to zero). The compiler exposes these instructions for convenience as intrinsics __builtin_clz/__builtin_ctz, which consequently, have undefined behavior if the argument is zero. But you can use them directly as an optimization if you know in advance that the argument is non-zero: https://github.com/ClickHouse/ClickHouse/blob/c0a43df749c827ce13abb015faca4ad8ab524685/src/Common/BitHelpers.h#L35 https://github.com/ClickHouse/ClickHouse/blob/c0a43df749c827...

Findecanor 3y ago
`bsr` and `bsf` have "undefined" results on a zero argument in Intel's documentation. In AMD's documentation however, the destination is supposed to be "unchanged". What is unusual is that the 32-bit flavours of these instructions leave the upper 32 bits unchanged, whereas other 32-bit integer instructions write zeroes there even if the lower bits in the destination are unchanged. Perhaps Intel intends to make these instructions zero-extend in the future ... or does there exist some processor (from Intel or someone else) that zero-extends?
- userbinator 3y ago
  In at least the early days of x86, it was common for AMD to document what Intel left undefined: https://news.ycombinator.com/item?id=25320603 https://news.ycombinator.com/item?id=25320603

almostnormal 3y ago

> Unless you are programming directly in assembly, the most important take-home from the article is probably the "Bonus chatter" at the end: shifts equal to or greater than register size are undefined in C and C++. The article claims UB only at greater but not at equal: > Bonus chatter: The wide variety of behavior when shifting by more than the register size is one of the reasons why the C and C++ languages leave undefined what happens when you shift by more than the bit width of the shifted type. If think your "equal to or greater" is correct, and the article is wrong. The reason might be that the instructions are defined up to including equal for many hardware. I remember checking one case that included equal as valid for only one of left/right shift and invalid for the other (left/right encoded in 5 bit signed).