8 ms·
Pointers Are Complicated, or What’s in a Byte?
- kibwen 8y agoNote that this is the same author who worked on formally verifying Rust's type system via RustBelt (https://www.ralfj.de/blog/2017/07/08/rustbelt.html https://www.ralfj.de/blog/2017/07/08/rustbelt.html), which has managed to find a few bugs in the standard library (https://www.ralfj.de/blog/2017/06/09/mutexguard-sync.html https://www.ralfj.de/blog/2017/06/09/mutexguard-sync.html and https://www.ralfj.de/blog/2018/07/13/arc-synchronization.html https://www.ralfj.de/blog/2018/07/13/arc-synchronization.htm...), and also hopefully provides (by the nature of formal proofs) some small comfort regarding the quantity of other latent bugs. :P
- throwaway0255 8y agoI know meta comments are frowned upon here, but why is the “or:” in headlines (borrowed from Dr. Strangelove I presume) so popular among programmers? I see it done again at least once a week. Is it just because the movie is popular among programmers, or is there something more to it?
- toast0 8y agoRocky and Bullwinkle did the X or Y style thing years before Dr. Strangelove. Everybody loves moose and squirrel?
- chrismorgan 8y agoThis form of subtitle spans back a long way. I don’t know just how far, but I do know that twelve of the fourteen major works by Gilbert & Sullivan had such form, beginning with “Thespis; or, The Gods Grown Old” in 1871. Many of us have a fondness for comparatively old-fashioned approaches to various things; double titles like that are one such example, using em dashes despite space-separated en dashes being more popular is another (though that one varies by locale), and writing “&c.” for “et cetera” is another (there’s lots of fun history around the ampersand ligature).
- Sharlin 8y agoYep, Strangelove simply utilized the existing trope, just like this article.
- irishsultan 8y agoAlso for example "Frankenstein; or, The Modern Prometheus" by Mary Shelley, which was published in 1818. But actually it goes back even further, at least to the 17th century, https://en.wikipedia.org/wiki/Twelfth_Night#/media/File:Twelfth_Night_F1.jpg https://en.wikipedia.org/wiki/Twelfth_Night#/media/File:Twel...
- ralfjung 8y ago> using em dashes despite space-separated en dashes being more popular is another (though that one varies by locale) Okay so I was told in my English writing class that in US English one uses the longer em dashes without spaces. But I just can't get over how they look, and in German we use en dashes with spaces (AFAIK), so I usually do that when writing English except if it is a paper where my advisor will complain if I do. ;)
- panic 8y agoProbably for the same reason you're referencing the famous quote, "Dr. Livingstone, I presume" -- it's natural to imitate other text in various ways when you're writing.
- ralfjung 8y agoTBH I just wanted to mention both of these things in the title so I stuffed them both in.^^ (I'm also not a native speaker so I kind of borrow what I see. And Dr. Strangelove was probably where I was this kind of title for the first time.)
- iforgotpassword 8y agoI know what the post is trying to say and all the examples are fine and learning C(++) you should be aware of this and everything, but I think the conclusion of saying that this shows pointers aren't integers is an odd choice. They still are in memory. It's all about the interpretation of these integers, and the shortcuts compilers can take because the standard allows them to do so, as the author points out. If you turn off all optimizations or go ahead and write a really simple compiler yourself, you probably end up getting exactly the results you'd "expect" from those examples, at least on any platform that is not totally exotic. Also uninitialized bytes are still ordinary bytes, you just get a free rand() run. :) Yeah maybe it's just me being weird.
- vardump 8y agoPointers are not integers in abstract model C++ compilers use for reasoning about code. This is all about the abstract model used for optimization according to the language specification.
- iforgotpassword 8y agoSure, I thought I made that clear in my post. Also I didn't want to imply that this is good code or code anyone should write. However I still think when learning C or explaining the language it is vastly helpful to go with the analogy of pointers being integers, since it is so much easier to grasp. Which doesn't mean that shouldn't come with a big warning not to write weird unsafe code and everything; but even if the standard would actually mandate that any form if crazy pointer arithmetic would be defined behavior I wouldn't exactly encourage anyone to write code like that.
- ralfjung 8y agoThe sad truth is that I have seen, several times, people justifying real code doing questionable things with pointers in C(-like languages) by saying "well but pointers are just integers". I am not sure what the best way to teach C is. Maybe it is a good idea to start with a "lie" and explain pointers as integers. But most C books/tutorials never go to the part where they explain that this is a lie, and that is a problem. The problem will only get worse as compilers get smarter and hence better at exploiting the UB that lurks in so many programs due to a naive treatment of pointers.
- rwallace 8y ago> it is not clear what else to do – in our abstract machine, there is no single coherent “address space” that all allocations live in, that we could use to map every pointer to a distinct integer. Every allocation is just identified by an (unobservable) ID. That's all very well if you assume malloc is a primitive. But in this model, how can you implement malloc? (And have it be definitely correct, rather than just 'works for the moment because the compiler hasn't yet got around to calling it undefined behavior and optimizing it out of existence'?)
- andrewaylett 8y agoBy having malloc take an allocation from a lower-level allocator and hand out pieces of that. The lower-level allocator (mmap or -- historically -- brk) is a primitive, implemented as a syscall.
- yoklov 8y agoOne option: Just go further up the chain. Malloc is going to be implemented (probably) using mmap/VirtualAlloc/whatever, just teach the system about those native calls as allocations. (This probably is not a satisfying resolution there, since it's likely impossible to enumerate all the primitive memory allocation functions)
- vardump 8y ago> But in this model, how can you implement malloc? This is not about runtime implementation, it's about how the compiler reasons about pointers to allocated memory on a symbolic level. It just means the compiler would consider all memory accessed through the pointer (and other pointers computed from it) other than the pointed (allocated) memory block to be undefined. Even if this was about runtime behavior, a basic malloc would fulfill this requirement with no changes. It returns a pointer to the allocated block and this pointer itself is the "memory block ID". So absolutely no change, with a reasonable assumption that successive allocations (without freeing in between) always return a different pointer. The compiler could simply generate fat pointers with allocation base address + offset to actual location.
- ralfjung 8y agoThis is an extremely good question, and I do not have a satisfying answer. Note that `malloc` is special in the C standard as well, and AFAIK it is not possible to implement `malloc` in standard C at all. Heck, there are several models of C out there where you cannot implement `memcpy`.
- bumholio 8y agoThe idea of redefining pointers from an {address} to an {offset,allocation_id} tuple seems to me a very powerful solution to the problems discussed recently in "C's biggest mistake: conflating pointers with arrays" [1] Instead of redefining arrays and introduce a new incompatible syntax, we are redefining the compiler representation of what a pointer is and get run-time guarantees of correctness without modifying the source code of existing C and C++ programs. For example, on a 64 bit machine a pointer can become an 128 bit long concatenation of two address: [ptr][alloc_id] The [ptr] part is binary equivalent of existing C pointers (the memory address of the pointed object), while the alloc_id is another 64 bit address of the allocation structure from which the object is part of. Here is a "fat" pointer that indexes the 4th element of an array, previously allocated by malloc(8 * sizeof(object)) : [ ][ ][ ][ ][ ][ ][ ][ ][malloc_data] ^______ ___^ | | [ptr][alloc_id] = "fat pointer" Defining the allocation_ID as the address of the malloc data structure and placing that at the end of the array earns us a very efficient way to make sure pointer increment (a very frequent operation and source of memory bugs) still points inside of the array, in a single assembly instruction: just CMP the new [ptr] with the [alloc_id] (for other operations, like pointer arithmetic with negative ints where [ptr] can go down, you would of course need to deference [alloc_id] and obtain the lower limit of the array stored somewhere in the malloc_data structure) This solves a slew of problems: - pointer arithmetic can now be performed only when it makes sense (identical alloc_id) - binary equality of pointers is a guarantee that they point to the same object - the compiler can easily implement some or more memory protection checks, based on the desired performance-safety trade-off - the cost in memory or stack space of doubling pointer size should not have a significant impact on most real programs - no syntax changes should be required Since this cannot be a new ideea, I would like someone more knowledgeable to poke some holes in it. [1] https://news.ycombinator.com/item?id=17585357 https://news.ycombinator.com/item?id=17585357
- pjmlp 8y agoIn fact your idea is not new. "Efficient Tagged Memory" http://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/201711-iccd2017-efficient-tags.pdf http://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/201711-... "SPARC M7 Application Data Integrity" https://swisdev.oracle.com/_files/What-Is-ADI.html https://swisdev.oracle.com/_files/What-Is-ADI.html The problem to most C improvement solutions is mostly human, not technical.
- antirez 8y agoHere the author is constructing a theory based all on true statements, but the mental model he builds, which is philosophically valid, is IMHO not the best choice in order to really address and simplify those concepts, for the scope of further reasoning upon that aspects of languages. My POV is that the interpretation of what a pointer is, should be more bound to the low level load/store instructions, and the address space of the process. In this declination a pointer is just a number, the problem is that certain programming statements in C/C++ that the programmer believes will result into a load/store operation, will be disregarded by the compiler, in name of a set of rules that violate what should be a normal behavior. So I think that a better mental model is to think at a program as a set of load/store operations (from the POV of memory), and how the compiler may decide to disregard such operations depending on the context. I think that reasoning like that also makes us pointing the finger in the right direction, which is the ANSI C committee.
- vardump 8y ago> Here the author is constructing a theory based all on true statements, but the mental model he builds, which is philosophically valid, is IMHO not the best choice in order to really address and simplify those concepts On the contrary, I feel those concepts are great for reasoning about code on a symbolic level. Which is what a compiler is all about. > In this declination a pointer is just a number, the problem is that certain programming statements in C/C++ that... Wouldn't this mean the compiler will need to generate a more memory loads and stores that could otherwise be proven redundant? It'll need to assume a store through a pointer 'a' at index unknown at compilation time can modify data at pointer 'b', even though it could otherwise deduce there's no aliasing.
- mannykannot 8y agoThis is an interesting discussion, but I get the impression that the author is trying to reconcile two fundamentally irreconcilable ways of looking at memory: on the one hand, the machine view of a single address space, and on the other, the program view of distinct variables. I am not at all convinced that there is a unifying viewpoint, at least if you want to cast pointers in both models to and from integers. One can, of course, map {base, offset} pointers to the natural numbers (though not necessarily Rust integer types? I don't know Rust) by considering the base to be the most significant bits of the number and the offset the least, but arithmetic on these numbers is not the same as pointer arithmetic in the address-space model. I do not follow the part, in the "what's in a byte" section, about a byte-by-byte memcpy. Is the question "what is the first byte?" any more or less problematical for a {base, offset} pointer than it is for a multi-byte integer, where place value matters?
- ralfjung 8y ago> the author is trying to reconcile two fundamentally irreconcilable ways of looking at memory: on the one hand, the machine view of a single address space, and on the other, the program view of distinct variables That's not incorrect. However, the reason I am doing that is because this is what C is all about (nowadays, at least): Compilers doing high-level optimizations based on alias analysis and other sources, and programmers expecting to have a low-level picture of memory. Our choice is to either give up and declare C broken beyond repair, or try to find some way to reconcile these two worlds as best as possible.
- tom_mellior 8y ago> Is the question "what is the first byte?" any more or less problematical for a {base, offset} pointer than it is for a multi-byte integer, where place value matters? Shifting and bit-masking integers are operations that make sense. Storing an int in memory and loading back only one of its bytes is equivalent to loading it all, then shifting and masking. It's meaningful, thus you do need to model the bits faithfully. In contrast, shifting and masking pointers is (with some exceptions) not meaningful. Neither is it meaningful to store one of these in memory and to load back only part of it. It makes sense to use a more abstract, symbolic model for bytes of such values. For whatever it's worth, the author's solution for bytes is the same as CompCert's: https://github.com/AbsInt/CompCert/blob/3939a1ccfdb86795e9fdf5953489ddfee238152c/common/Memdata.v#L155 https://github.com/AbsInt/CompCert/blob/3939a1ccfdb86795e9fd...
- kulu2002 8y agoI am extremely convinced with all points in article apart from the model that author proposes, which I am not sure I quite get it. I think the definition of pointer becomes more and more abstract as you move from hardware level to more high-level languages. In languages like C/C++ (Not aware of Rust) which lie in middle (higher than assembly where pointer is just a hw register and lower than say Java having no pointers per se) the definition of pointer is not so clear. The other source of confusion is syntax of pointer in C/C++ and fact that they can be used interchangeably with arrays and arithmetically manipulated. Pointers are indeed complicated and thats why standards like MISRA C / autospice restricts use of pointers to great extent. In highest level languages like MATLAB for model based development, the inputs outputs are treated in form of Arrays at user level. When autocode is generated from these models compilers internally transform array operations into pointer operations, essentially making the array-based source code into object code that's as efficient as the pointer version. The advantage is that the pointer-oriented compiler-generated code is created in a controlled fashion.
- miket94 8y agoauto x = new int[8]; auto y = new int[8]; However, given how low-level a language C++ is, we can actually break this assumption by setting i to y-x. Since &x[i] is the same as x+i, this means we are actually writing 23 to &y[0]. This assumes that the address space of y starts at the end of the address space of x? In other words x+8==y? Could these two allocated blocks of memory ever not be continuous?
- vardump 8y ago> However, given how low-level a language C++ is, we can actually break this assumption by setting i to y-x. Since &x[i] is the same as x+i, this means we are actually writing 23 to &y[0]. > This assumes that the address space of y starts at the end of the address space of x? No it does not. Any value of x or y should "work", because y-x computes a difference between pointers. > Could these two allocated blocks of memory ever not be continuous? Probability they're not continuous is high and only gets higher as the heap gets more fragmented over time.