Pointers Are Complicated, or What’s in a Byte? | Hacker News Reader

Pointers Are Complicated, or What’s in a Byte?

ralfj.de

119 pointskibwen61 comments

Note 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), which has managed to find a few bugs in the standard library (https://www.ralfj.de/blog/2017/06/09/mutexguard-sync.html and 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

> 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'?)

One 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)

By 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.

> 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.

This 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`.

> 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.

malloc() is usually implemented in C [0] and to be honest I'm not sure why do you think it wouldn't be? Of course you need OS API calls to actually get some memory (unless you want to operate on statically defined memory buffer) but well it's still C.

[0] https://github.com/lattera/glibc/blob/master/malloc/malloc.c

That linked implementation relies on OS primitives (sysmalloc()), implemented in C, Assembly or whatever was used to write the OS.

Try to implement malloc() on bare metal, without using either Assembly or language extensions.

It's C, but it's not standard C. It uses implementation defined behavior. Every compiler has some implementation defined behavior because they would be much less useful without it.

Hmm. My answer would be “you don’t, unless you are willing to accidentally give stronger guarantees”. I believe that standard C11 permits a function to allocate malloc-style from a big static arena of type array of char. You can even implement free() and reuse the memory. But then all the allocations are really pointers into the arena, and certain operations that should be UB aren’t if you use this type of malloc.

But then you throw something like __attribute__((malloc)) on it, and define that as transforming the return value into a new Pointer that is in a different, fresh allocation. And you declare that access to the range of the arena in use is UB until free() gets called.

I don’t know how well this fits into the formalism, but I think that a complete formal memory model would need to understand that free() is permitted to treat its argument as a pointer into a large array of char, but that free()’s caller is not.

You can't implement malloc in standard C, but there is no actual C compiler that implements only standard C and provides no other guarantees. There is always implementation defined behavior in addition to what the standard defines.

On Linux, compilers will ensure that you can make system calls to the kernel such as brk[1] or mmap[2] which will let you allocate larger chunks of memory that malloc can split up and give out. On Windows, you will have access to Windows APIs which will let you use VirtualAlloc[3] to do the same.

[1] http://man7.org/linux/man-pages/man2/brk.2.html

[2] http://man7.org/linux/man-pages/man2/mmap.2.html

[3] https://msdn.microsoft.com/en-us/library/aa366887(VS.85).asp...

The 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

In fact your idea is not new.

"Efficient Tagged Memory"

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

The problem to most C improvement solutions is mostly human, not technical.

As I have said, I'm sure it's not a new concept. You provided some links to hardware accelerators for somewhat related systems, and they imply software solutions are unworkable performance wise.

But it seems to me that is not the case for what I am proposing. For the most part, working with pointers should generate almost the same assembly, the [alloc_id] part is simply copied around verbatim and [ptr] is used as before. A function that just dereferences pointer parameters will receive alloc_id in the stack frame but it will ignore it and not load it in the registers. If the pointer is duplicated, the alloc_id is copied on, somewhat increasing stack pressure and reducing memory bandwidth, but certainly not 100x slowdown. Modern processors are very good at parallelising these type of loads and stores.

The performance impact should hit when doing pointer arithmetic and advanced casting, depending on the degree of runtime assurance we want to offer. Every address alteration is followed by a sanity check of the pointer against it's allocation segment. An out-of-bounds pointer can be NULLed to trigger a subsequent run-time exception, while keeping with the standard that such pointers mean undefined behavior.

In the case of some frequent operations, like incrementing, these checks can be extremely fast. Not that hardware solutions would not help, but if such a technique works there is certainly a class of programs that would even accept the slowdown of a software solution. So I have to wonder if there is more to this I am not seeing, besides performance.

What you are missing it is the human factor.

At CppCon 2014, if I am not mistaken, too lazy to search the exact year. Herb Sutter asked the audience how many use some kind of analysis tooling. About 1% of the audience say they did.

Joe Duffy has a remark almost at the end of his keynote at Rustconf where he states even with Midori running in front of the Windows team, they weren't accepting it as possible.

At least on Solaris, regardless of its future, those protections are now on for many executables.

https://blogs.oracle.com/solaris/default-memory-allocator-se...

Likewise Google has been locking down what native code is allowed to do on Android, including compiling everything with FORTIFY enabled.

It seems pressure must come from OS vendors for habits to change.

This is a workable approach. One implementation I know of is CCured: https://people.eecs.berkeley.edu/~necula/Papers/ccured_popl0...

They claim 0-150% runtime overhead. It depends a lot on concrete characteristics of the program. For a debugging tool that's certainly acceptable.

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, 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.

> 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.

I meant to only change the reasoning the author is used in terms of optimizations being the ability to ignore loads/stores versus giving more semantical value to a pointer.

You need that semantic information for a pointer to reason about loads and stores to memory blocks. (This semantic information exists only during compiling process.)

The compiler needs semantic data to answer questions like "can an access through pointer A access data visible through pointers B and C?"

If it doesn't know that, it'll need to generate those redundant memory accesses.

Before storing (or loading) through A, it'll need to store temporary values previously written to B and C.

After a store through pointer A, it might need to load B and C values again for more computation, because a store to A might have modified them.

Yes, but giving each pointer metadata for the goal of saying, at compile time, I can ignore or not certain access patterns in this pointer, is conceptually different (but practically the same, it's just a POV) of saying that a pointer is not just a number. Both ways are ok to represent things, but I've the feeling that saying "a pointer is not just a number" in some way allows the ANSI-C culture of UBs to be culturally validated. Moreover, the definition given in the blog post, is also far from the actual nature of machines, where actually a load/store operation for this number will result in the same operation.

The model of "pointers are just a number" likely means that even "obvious" optimizations like

  int i = 0;
  *p = 10;
  return i;

  // becomes

  *p = 10;
  return 0;

aren't valid, because p could "just be a number" pointing to i's stack slot.

Can you explain this more? Surely the compiler can reason about p being able to point to i's address.

p could be

  int *p = rand();

or that code could be in a function

  int f(int *p)

which may be called from completely different compilation units (or even across a dynamic library boundary) meaning there's no way for the compiler to know what p is.

I don't claim that the compiler should avoid any kind of optimizations because pointers are numbers, but that the formal model should be that the compiler can ignore certain loads/stores in certain paths, rather than overloading of semantical value the pointer itself. It's just a different POV that one could use to analyze what happens. Similarly, different statements should be used in order to specify how rigid we want the compiler to be with our loads/stores for a given pointer, so that certain optimizations that are obvious like the one above are the default, and others are performed only if the pointer is specified via keywords and other annotations to have a very special meaning.

How exactly does the model specify which loads/stores are okay to be ignored or reordered (etc.)? I feel like anything that gets close to the essence of the C/C++/Rust model (such as allowing the optimization in my example above), ends up with something pretty similar to the "allocation id" idea.

As a specific example, consider the difference between these two versions of my example above:

  int f() {
    int i = 0;
    *(&i) = 10;
    return i;
  }

and the original:

  int g(int *p) {
    int i = 0;
    *p = 10;
    return i;
  }

If a call like g(rand()) ends up with p == &i, the unoptimized versions of that and of an f() call execute exactly the same sequence of memory accesses, and yet the optimization I mention above only applies to g. In essence, the source of the number "&i" seems to matter.

> others are performed only if the pointer is specified via keywords and other annotations to have a very special meaning.

Some of this already exists, such as 'restrict'.

This 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?

> 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.

> 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/3939a1ccfdb86795e9fd...

That's a good point - if I am following correctly, a memcpy of a byte from an integer can be regarded as an arithmetical operation (in fact, a multiplicative one), while, in general, there is no equivalent interpretation for copying a byte of a pointer.

I guess one could make a similar argument for the bytes of a unicode string.

While writing this, it occurred to me that the difficulties with casting between pointers and integers is in going from integers to pointers, where there is no unique mapping (for pointer to integer, base + offset is meaningful, but it loses information.)

I 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.

I 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?

Rocky and Bullwinkle did the X or Y style thing years before Dr. Strangelove. Everybody loves moose and squirrel?

This 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).

Yep, Strangelove simply utilized the existing trope, just like this article.

Also 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:Twel...

> 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. ;)

Probably 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.

TBH 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.)

I 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.

Pointers 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.

Sure, 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.

The 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.

There should be a different word for that though. A pointer is literally a stored memory address, i.e. an integer.

The thing the compiler manipulates could be called a "C pointer" or something.

> A pointer is literally a stored memory address, i.e. an integer.

Consider:

  int a = 5;
  int* b = &a;

What happens when 'a' is allocated to a CPU register? If 'b' never escapes and no (undefined) pointer arithmetic is used, the compiler can simply consider '*b' as an alias to 'a'.

In this case the 'pointer' never actually points to memory.

> The thing the compiler manipulates could be called a "C pointer" or something.

Perhaps, although when talking about pointers, it's almost always in context of a particular programming language.

Maybe it'd be better to talk about "hardware pointers". Although on hardware level, from CPU point of view, a value or a register generally only becomes a "pointer" when it's used to compute a memory address for an instruction that accesses memory. (Excluding special hardware registers, like instruction pointer, page tables, DMA hardware or interrupt/exception vectors.)

So a "pointer" is always an abstraction in context of general purpose processing.

> A pointer is literally a stored memory address, i.e. an integer.

This is not correct in general. In x86 real mode, addresses consist of a segment and an offset. The linear address is computed as segment * 16 + offset. This is very different from a single integer, and even somewhat different from a pair of integers: Two different segment/offset-pairs can refer to the same linear address, so a pointer comparison has to behave differently than an integer-pair comparison.

You're not wrong, but the segment/offset model is such a farce it's not even worth using as an example

(also you would have had to distinguish between far and near pointers)

At the processor level, pointers are distinguished either by the type of register or by the type of operation used on them (when they're more orthogonal, still there are "pointer only" registers like stack, ip, etc)

> A pointer is literally a stored memory address, i.e. an integer

You’re mixing implementation with definition. A pointer is (usually) implemented in terms of an integer (i.e. its physical representation is a sequence of bytes interpreted as an integer offset in memory). But that isn’t what a pointer is. The C++ standard (or the C standard, or Rust, or any of many other languages) defines pointers as a concept that has all kinds of properties that integers don’t have. The whole point of this blog post is that this distinction is crucial in order to guarantee type safety and allow the compiler to perform basic optimisations.

Unitialized bytes can NOT be considered "ordinary bytes" on x86. This is because of memory paging and copy-on-write. If a memory is untouched, it is allowed to map to a different physical memory on different accesses, so the contents are not only "unknown", they may change under your feet! You must touch the memory page for this not to happen.

TIL, nice detail

(Not that I would've recommended using uninitialized bytes as an RNG anyways ;))

This cannot possibly be correct. A read access to a region without a mapped page in the page table will cause the CPU to trigger a page fault exception. The OS must then decide whether to map memory there a one time operation or abort the program. A second read from the same page must lead to the same mapping then. There is no sane way for an operating system to switch out program heap pages after they have been mapped.

I read "memory is untouched" as no read/write accesses.

Because it'd be pretty odd for the page to change after first read from operating system implementation point of view. Generally I'd expect the default mapping to be to an all-zero physical memory page. (Unless there's a rowhammer attack (or similar) that successfully modifies said all-zero page...)

From C/C++ point of view, it's legal for uninitialized memory to arbitrarily change between (undefined behavior) reads until it is written to.

While I doubt any actual OS would modify the page in this manner after first read access, a C/C++ compiler can still return arbitrary (even random) values when reading from uninitialized memory. It doesn't even need to actually read from the memory proven to be uninitialized.

madvise MADV_DONTNEED

> There is no sane way for an operating system to switch out program heap pages after they have been mapped.

They'll even move the page to the harddisk if necessary. Or am I misunderstanding what you're asking?

The OS can move the content of the pages in physical memory, but it will not make the page table entry point to a page with different content after that point.

This is looking at the wrong level of abstraction though. The compiler will already optimize your code in a way that multiple uses of the same uninitialized value can produce different results.

Arguing about these assembly/CPU-level details (unfortunately?) is besides the point when debating the semantics of languages like C, C++ or Rust.

Grandparent already narrowed discussion down to x86 behaviour and I responded to details on that. This is definitely all outside the scope of language specifications.

I'm not going to take the responsibility whether it's correct or not - here's the talk I learned it from: https://youtu.be/kPR8h4-qZdk?t=22m17s

I haven't watched all of it, but the explanation for the null terminator bug must contain some OS interaction telling the kernel that it is actually safe to discard the page containing the null terminator (e.g. the madvice call mentioned in a sibling post). If you're doing things like that, you're asking for trouble.

auto 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?

> 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.

Reply on news.ycombinator.com