4 ms·

NaN boxing sounds like it would have very significant pointer provenance issues. CHERI would also stick its nose up at it. The tagged pointer type has the adva

NaN boxing sounds like it would have very significant pointer provenance issues. CHERI would also stick its nose up at it. The tagged pointer type has the advantage of holding real pointers, meaning that any machine[0] that sticks extra information onto its pointers transparently just works. And reading the int half of the union to check if the pointer is valid should always be sound, but I'm not 100% sure on that. Architectures that don't enforce alignment are also probably not the sort of thing we care about running on, and I doubt there's a way for an optimizer to legally screw over programs that depend on pointer alignment being there on architectures where it has to be there. But, then again, that's what we said about int-to-pointer casts... [0] Real or virtual. Remember that when you compile your program with an optimizing compiler or JIT, it is executing on two architectures: 1. The compiler's expression/AST interpreter, which enforces ISO C undefined behavior rules 2. The target architecture, where those undefined behaviors become merely unspecified.

klodolph 4y ago
I don't think that pointer provenance rears its ugly head here. You are generally free to convert a pointer to an integer and then back, which is what's happening here, and you get pointer provenance problems because different pointers may be supposed to point to different objects. Basically, casting to an integer and back is supposed to be "safe", but doing math and getting pointers to different objects is not. Note that there are some implementation-dependent factors here which I'm not getting into. > And reading the int half of the union to check if the pointer is valid should always be sound, but I'm not 100% sure on that. After various alias problems a while back (Linux kernel folks had some words), everyone got together and agreed that you can do type punning through a union... you just get the byte representation of one type, reinterpreted as the byte representation of another type. This was codified a few C standards ago and it's fairly explicit in the spec now. I'll also just mention that you don't need an architecture than enforces alignment--you just need an allocator that returns aligned pointers.
- MaulingMonkey 4y ago
  > I don't think that pointer provenance rears its ugly head here. You are generally free to convert a pointer to an integer and then back It's worth noting that Rust is experimenting with making this not so free for one to do: https://doc.rust-lang.org/std/ptr/index.html#pointer-usize-pointer-roundtrips-and-exposed-provenance https://doc.rust-lang.org/std/ptr/index.html#pointer-usize-p...
- wahern 4y ago
  > I don't think that pointer provenance rears its ugly head here. You are generally free to convert a pointer to an integer and then back, which is what's happening here C [optionally] supports converting pointers to intptr_t (or uintptr_t), not to any integer type (even with nominally sufficient width), and certainly not to a floating point type, which is how NaN boxing works. In CHERI intptr_t requires special treatment by the compiler. Plus, the nominal width of both pointers and intptr_t double in size--128-bits on 64-bit architectures. Most environments don't even have a 128-bit floating point type, even when the hardware might support it. (According to Wikipedia, Fortran is an exception, but it's still uncommon in C and other popular language environments.)
  - Dylan16807 4y ago
    > C [optionally] supports converting pointers to intptr_t (or uintptr_t) Yes it's optional, but it's "generally" supported. > (even with nominally sufficient width) C99 says: "Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type." I'm not entirely sure how I'm supposed to parse that, but it sounds like if the result is in range of an integer then it's supposed to work? I guess you could technically say all results have a zillion added to the actual value? Rules lawyering gets annoying pretty fast. > and certainly not to a floating point type, which is how NaN boxing works NaN boxing works by converting to an integer type first. What it does with the bits afterwards is not important to C, as long as it reconstructs the same integer before converting back.
    - lokedhs 4y ago
      The part you quoted seems pretty clear. It's implementation defined. That's why it works done on most modern architectures, but you can't rely on it in portable code, as there are certainly architectures where it doesn't.
      - kazinator 4y ago
- LoganDark 4y ago
  > You are generally free to convert a pointer to an integer and then back (I'm going to ignore your use of the term "generally" to acknowledge that there are exceptions, because I want to elaborate on a particular exception that highlights an error in reasoning that I believe most programmers make when they manipulate memory addresses and then cast them straight to pointers.) On CHERI, pure integer addressing can be turned off. In that case, pointers cannot necessarily be derived from integers alone. This is because CHERI implements pointer capabilities in hardware. You have to use special capability-preserving instructions to handle them, or else they permanently become invalid. You can still manipulate memory addresses, but you generally cannot use them directly without them being part of a valid pointer. So it's valid to take a memory address, but invalid to try to use it directly. I personally consider it unsound to try to transmute an integer into a pointer. It doesn't make sense, because [pointers are not necessarily memory addresses](https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html). The Rust programming language is also considering taking this stance -- they already have a lint against treating pointers as integers, and with it an option to forbid it, though I'm unsure what the status on that is (it will probably remain optional forever). This doesn't necessarily make it wrong or incorrect if the language allows for it, but I would advise not doing so, unless it's a domain-specific optimization (i.e. there is a fallback for architectures where it does not apply).
armchairhacker 4y ago
Any incompatibility can be resolved by having an explicit “NaN box” type. For OSs where pointers always end in b000 and NaN boxing just works, it compiles to 8 bytes. For weird OSs like CHERI or those which store metadata in pointers, it compiles to an ordinary tagged union.
- Dylan16807 4y ago
  NaN boxing doesn't need pointers to end in b000. You need more than ten bits that don't matter. So you need something like 48 bit pointers, and once you have that you're already done. That's enough to tag 30 different types of pointer and every smaller type.
kazinator 4y ago
NaN boxing can be implemented with pointer-priority. That means that pointers into the heap represent themselves as-is. The upper 12 bits being zero, that bit pattern looks like a valid double. To represent double values that would look like pointers, the 64 image of the double value is altered by adding an offset (as an integer) so no double value is represented with a 0x0000 in the upper bits. So then, that is pretty much just a variation on pointer tagging. When the pointer has certain bits set in certain ways, it represents something else, including a full double. To defend against undefined behaviors not going the way you want, you have tests. Programming language run-times are easily testable. If your language's compiler compiles itself and a sizeable library, and all kinds of tests pass, it's unlikely that there is any hidden time bomb in value tagging scheme due to the undefined behavior of aliasing or pointer/integer conversion. ISO C doesn't guarantee that if some line of code performing some undefined conversion has worked a million times, it will work for the million-and-first time. In practice, there is no reasonable translation scheme from C to machine code which would have that hostile behavior; it would have to be contrived with a hidden counter.

klodolph 4y ago

I don't think that pointer provenance rears its ugly head here. You are generally free to convert a pointer to an integer and then back, which is what's happening here, and you get pointer provenance problems because different pointers may be supposed to point to different objects. Basically, casting to an integer and back is supposed to be "safe", but doing math and getting pointers to different objects is not. Note that there are some implementation-dependent factors here which I'm not getting into. > And reading the int half of the union to check if the pointer is valid should always be sound, but I'm not 100% sure on that. After various alias problems a while back (Linux kernel folks had some words), everyone got together and agreed that you can do type punning through a union... you just get the byte representation of one type, reinterpreted as the byte representation of another type. This was codified a few C standards ago and it's fairly explicit in the spec now. I'll also just mention that you don't need an architecture than enforces alignment--you just need an allocator that returns aligned pointers.

MaulingMonkey 4y ago
> I don't think that pointer provenance rears its ugly head here. You are generally free to convert a pointer to an integer and then back It's worth noting that Rust is experimenting with making this not so free for one to do: https://doc.rust-lang.org/std/ptr/index.html#pointer-usize-pointer-roundtrips-and-exposed-provenance https://doc.rust-lang.org/std/ptr/index.html#pointer-usize-p...
wahern 4y ago
> I don't think that pointer provenance rears its ugly head here. You are generally free to convert a pointer to an integer and then back, which is what's happening here C [optionally] supports converting pointers to intptr_t (or uintptr_t), not to any integer type (even with nominally sufficient width), and certainly not to a floating point type, which is how NaN boxing works. In CHERI intptr_t requires special treatment by the compiler. Plus, the nominal width of both pointers and intptr_t double in size--128-bits on 64-bit architectures. Most environments don't even have a 128-bit floating point type, even when the hardware might support it. (According to Wikipedia, Fortran is an exception, but it's still uncommon in C and other popular language environments.)
- Dylan16807 4y ago
  > C [optionally] supports converting pointers to intptr_t (or uintptr_t) Yes it's optional, but it's "generally" supported. > (even with nominally sufficient width) C99 says: "Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type." I'm not entirely sure how I'm supposed to parse that, but it sounds like if the result is in range of an integer then it's supposed to work? I guess you could technically say all results have a zillion added to the actual value? Rules lawyering gets annoying pretty fast. > and certainly not to a floating point type, which is how NaN boxing works NaN boxing works by converting to an integer type first. What it does with the bits afterwards is not important to C, as long as it reconstructs the same integer before converting back.
  - lokedhs 4y ago
    The part you quoted seems pretty clear. It's implementation defined. That's why it works done on most modern architectures, but you can't rely on it in portable code, as there are certainly architectures where it doesn't.
    - kazinator 4y ago
LoganDark 4y ago
> You are generally free to convert a pointer to an integer and then back (I'm going to ignore your use of the term "generally" to acknowledge that there are exceptions, because I want to elaborate on a particular exception that highlights an error in reasoning that I believe most programmers make when they manipulate memory addresses and then cast them straight to pointers.) On CHERI, pure integer addressing can be turned off. In that case, pointers cannot necessarily be derived from integers alone. This is because CHERI implements pointer capabilities in hardware. You have to use special capability-preserving instructions to handle them, or else they permanently become invalid. You can still manipulate memory addresses, but you generally cannot use them directly without them being part of a valid pointer. So it's valid to take a memory address, but invalid to try to use it directly. I personally consider it unsound to try to transmute an integer into a pointer. It doesn't make sense, because [pointers are not necessarily memory addresses](https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html https://www.ralfj.de/blog/2018/07/24/pointers-and-bytes.html). The Rust programming language is also considering taking this stance -- they already have a lint against treating pointers as integers, and with it an option to forbid it, though I'm unsure what the status on that is (it will probably remain optional forever). This doesn't necessarily make it wrong or incorrect if the language allows for it, but I would advise not doing so, unless it's a domain-specific optimization (i.e. there is a fallback for architectures where it does not apply).

armchairhacker 4y ago

Any incompatibility can be resolved by having an explicit “NaN box” type. For OSs where pointers always end in b000 and NaN boxing just works, it compiles to 8 bytes. For weird OSs like CHERI or those which store metadata in pointers, it compiles to an ordinary tagged union.

Dylan16807 4y ago
NaN boxing doesn't need pointers to end in b000. You need more than ten bits that don't matter. So you need something like 48 bit pointers, and once you have that you're already done. That's enough to tag 30 different types of pointer and every smaller type.

kazinator 4y ago

NaN boxing can be implemented with pointer-priority. That means that pointers into the heap represent themselves as-is. The upper 12 bits being zero, that bit pattern looks like a valid double. To represent double values that would look like pointers, the 64 image of the double value is altered by adding an offset (as an integer) so no double value is represented with a 0x0000 in the upper bits. So then, that is pretty much just a variation on pointer tagging. When the pointer has certain bits set in certain ways, it represents something else, including a full double. To defend against undefined behaviors not going the way you want, you have tests. Programming language run-times are easily testable. If your language's compiler compiles itself and a sizeable library, and all kinds of tests pass, it's unlikely that there is any hidden time bomb in value tagging scheme due to the undefined behavior of aliasing or pointer/integer conversion. ISO C doesn't guarantee that if some line of code performing some undefined conversion has worked a million times, it will work for the million-and-first time. In practice, there is no reasonable translation scheme from C to machine code which would have that hostile behavior; it would have to be contrived with a hidden counter.