C pointers are not hardware pointers

http://kristerw.blogspot.com/2016/03/c-pointers-are-not-hardware-pointers.html

by ingve • 10 years ago

45 36 10 years ago

kristerw.blogspot.com

jepler3• 10 years ago

My "favorite" bit of code that gcc eventually started treating as undefined (after working for probably literally 20 years up to that point): A 3x4 matrix type declared as

    typedef float xform_3d[4][3];

was routinely serialized by (I'm taking liberties here, this certainly not how the 20-year-old code read!)

    float *f = &x[0][0];
    for(int i=0; i<12; i++) write_float(f[i]);

i.e., the code treated the same storage as a 2D-array of floats and then as a 1D-array of floats in different places.

In the "pointers are just CPU registers" world, this worked fine. But more clever compilers know that the code dereferences past the end of the array (e.g., memory at f[4] is always accessed) so the whole loop is undefined behavior.

We fixed it once we started seeing the compiler warning, so I don't know exactly how we would have been punished for the undefined behavior in this case. So hooray for compiler warnings!

dzdt• 10 years ago

Seriously? I have seen this code many places, even written it.

jepler3• 10 years ago

    #include <stdio.h>

    typedef float xform_3d[4][3];

    int main() {
        xform_3d x = {
            {1.f, 0.f, 0.f},
            {0.f, 1.f, 0.f},
            {0.f, 0.f, 1.f},
            {0.f, 0.f, 0.f} };

        for(int i=0; i<12; i++) printf("%f\n", x[0][i]);
    }

with g++ 4.9 (debian jessie -O3 -Wall):

    xf.c: In function ‘int main()’:
    xf.c:12:50: warning: iteration 3u invokes undefined
              behavior [-Waggressive-loop-optimizations]
         for(int i=0; i<12; i++) printf("%f\n", x[0][i]);
                                                      ^
    xf.c:12:5: note: containing loop
         for(int i=0; i<12; i++) printf("%f\n", x[0][i]);
         ^

(yes, this is slightly different than the code I posted first---"laundering" &x[0][0] through an intermediate pointer variable f makes the warning go away in the compiler I tested, but my suspicion is that if one is undefined behavior the other probably is too)

Edited to add: and when built and run, it printed all x[0][i] but x[0][0] as 0.0, so gcc did emit code that doesn't do what the programmer wants.

jibsen2• 10 years ago

Even computing pointers that point outside an array can be undefined behavior, like f - 1 + 1.

It is easy for people who understand the relatively strong correlation between C and the assembly language it generates to assume such things work. Also, compiler vendors did let us get away with them for many years.

bitwize• 10 years ago

I once read about pointer implementations in C compilers for Lisp machines (Zeta-C, I believe). As I recall, they were implemented as a pair consisting of a vector of objects and an index into the vector. Casting between pointer types must have been a royal bitch, if it were implemented at all.

So yeah, major lesson learned: C pointers are not necessarily equal to hardware addresses.

but you should really be using c++ and iterators or smart pointers anyway

Grishnakh• 10 years ago

but you should really be using c++ and iterators or smart pointers anyway

Not if you're writing an OS kernel, or any low-resource embedded code.

asveikau4• 10 years ago

The pointer p has indeterminate value after free(p), so the comparison invokes undefined behavior.

Is there a citation in the standard for this? Obviously all bets are off with being able to dereference p, but it makes no sense that free() could also modify the pointer itself, and I have a hard time justifying how any implementation would reasonably make comparing dangling pointers invalid.

I can even see a legit use case for it being valid.

    void *p, *q;

    p = q = malloc(n);
    /* ... */
    if (foo)
       q = malloc(n);
    /* ... */

    free(p);
    if (p != q)
       free(q);

Here we free q only if it was a different allocation from p... The fact that p was dangling at the free(q) line is immaterial. I guess it's not so bad to move the free(p) to the end of this code, but it's surprising to me that a sane language implementation would consider the above invalid.

dave20003• 10 years ago

I think you're right. I also take issue with the "pointers point at an object, one byte into it or are null" statement. A pointer is a piece of memory/register that contains an address, and an address is just a bit pattern. 0 is an address, as is 1,2,3.... 0xffd9303e. It doesn't even have to be accessible memory; you can get all sorts of exciting effects if you write to or even read from addresses mapped to hardware but the datatype is still a pointer.

dllthomas5• 10 years ago

My vague recollection of the relevant bits of the C standard has it that there are a few differences between how pointers to void, pointers to char, and pointers to anything else are treated in some respects. This might be one of them.

"A pointer is a piece of memory/register that contains an address, and an address is just a bit pattern."

This is true on virtually every modern system, but (if memory serves) not literally every system ever, and the C standard leaves room for some surprising things in some places. It would have been very nice if the author had actually included some references, though.

belovedeagle2• 10 years ago

Seems like you missed the whole point of the article, which was that an abstract "pointer" is not the same thing as the bit field held in some register or memory location, any more than a Java Object is.

nostrademons• 10 years ago

http://blog.llvm.org/2011/05/what-every-c-programmer-should-...

When behavior is undefined, the compiler can legally do anything up to and including formatting your hard drive or making your computer burst into flames. It's counterintuitive, but C compilers follow the C standard and not necessarily programmer's intuitions about C.

asveikau4• 10 years ago

I asked for a citation about why this specifically is undefined, not a condescending lecture about what "undefined behavior" means.

jsnell2• 10 years ago

Consider an extreme segmented CPU architecture where the malloc implementation allocates a new segment for every object, free deallocates the segment, and the architecture has been defined such that any use of a stale segment descriptor is an error.

asveikau4• 10 years ago

and the architecture has been defined such that any use of a stale segment descriptor is an error.

Even trying to imagine such an architecture, it's hard to see that comparing pointers constitutes "use" - it seems more likely that this would just wind up being an integer comparison.

rm445• 10 years ago

Clause 6.2.4 of C11, paragraph 2:

The lifetime of an object is the portion of program execution during which storage is guaranteed to be reserved for it. An object exists, has a constant address,33) and retains its last-stored value throughout its lifetime.34) If an object is referred to outside of its lifetime, the behavior is undefined. The value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime.

Like you it seems a bit odd to me - perhaps to make the standard prepared for architectures, existing or otherwise, where pointer values have to be loaded in specific registers, and then trap if they contain values pointing to unallocated pages? (Without being dereferenced).

skissane2• 10 years ago

Imagine the following possible architecture: every pointer contains a valid bit (V), which is initially set to 1. The V bit is checked on every pointer dereference, and dereferencing a pointer with V=0 traps. free(p) as well as freeing the memory pointed to by p, also sets p.V=0. Now, if you copied p earlier, the copy would still have V=1, and hence would now != the original pointer, even though the actual address stored inside the pointer is the same. So your sample code would end up doing a double free on p when foo is false.

We can question whether the design choices of such a CPU architecture are sensible or not, but I can certainly imagine such a design decision being made at some point in the last few decades. Indeed, if you look at the history of tagged memory architectures (e.g. Burroughs large systems, IBM System/38, Intel iAPX 432) - their tagged pointers are in the same spirit as what I've described here, except they used multiple bits instead of just one, and the tag bits were often stored in a distinct memory area from the actual pointer addresses (I don't know how C implementations on those platforms - if they existed - actually handled free() or pointer comparison though.) I guess, the possibility of such a design decision motivates making this undefined behaviour in the C standard.

dllthomas5• 10 years ago

Except that free is defined to be a function, so it can't really make changes to arguments passed by value.

maxhou• 10 years ago

http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm

dwarman3• 10 years ago

One problem is, in C at least, the compiler has no way to know that the contents pointed to by p have reached their end of life. All these examples use malloc() and free(), but these two names are purely convention, and any names and memory management methods can be used with different names. And implications for the contents.

But there is another problem too - the free() might (should:) use a mutex while it does its work, but another thread could be woken up during the free() postamble, after the mutex has been released but before the caller resumes execution - or even between the == comparison and the second free() - call malloc(), and the implementation might be one that re-uses the most recent free(). Which would mess up the other thread wonderfully.

Neither of the above rely on any kind of mapping between the C variable p and the underlying hardware. This is deliberate. C is defined as an abstract grammar and semantics set, primarily because by that era it was painfully recognised that inventing new HLL's for each new hardware architecture was a losing proposition. There were so many of them, and those languages were not transportable. The essence beauty of C was it is simple enough to be implemented on any level from direct hardware out to as many layers of VM as one could wish for. And really only required the execution machine model to be Turing complete. Its early use was all done to the metal, hence the inherited impression that C pointers are hardware pointers, but really only when used at the metal is this likely to be true. And typically, these days, one finds architectural specific extensions, such as intrinsics, that allow metal access from C to the custom parts of the hardware.

The still painful part of C though is where its architectural independence intrudes. Such as, sizeof(int) being the native hardware size of an integer. 8, 16, 24, 32, 36, 48, 64, I've suffered from them all. Similarly, sizeof(enum) is undefined. The language only stats it must be large enough to represent all its values. I have found the compiler definition differences of bool to also be very frustrating. I grew into software from a hardware design background, and to me

a & true == a

is always true. Or should be. The language defines boolean values as 0 for false and any other value for true. Most compilers choose 1 for true - enum style. So then

((a & true) == a) && ((a == 0) || (a == 1))

Useless when trying to deal with metal and bitflag registers (clearly not the literal true, rather when somewhere else a variable has been set to true and later is used as a mask).

Some compilers have compile command options or #pragmas for forcing the issue, but there is no standard for these. Still. These indefinites can cause serious and sometimes difficult to debug problems when the binary structures containing these things have to be shared between different architectures. Not to mention endian-ness.

All told though, C is still easier than ASM, which usually _is_ specific to the hardware architecture.

dllthomas5• 10 years ago

"One problem is, in C at least, the compiler has no way to know that the contents pointed to by p have reached their end of life. All these examples use malloc() and free(), but these two names are purely convention, and any names and memory management methods can be used with different names."

This seams wrong, unless by "purely convention" you mean in some sense that the entire standard is "purely convention". The clearly defines the lifetime of an allocated object to be from allocation to deallocation, and clearly labels free (and realloc, in some circumstances) as deallocating. I am not sure whether a conforming implementation can introduce new functions that also, in the sense of the standard, deallocate, but in either case the provided code is still technically incorrect per the standard.

"Such as, sizeof(int) being the native hardware size of an integer. 8, 16, 24, 32, 36, 48, 64, I've suffered from them all."

Nit, and I'm sure you're aware, but perhaps worth noting for others: the values you're listing are (I infer) number of bits, which is not the same as what's returned by sizeof. sizeof gives number of chars, which on some architectures has actually been other than 8 bits!

dwarman3• 10 years ago

But does not define them in terms of hardware.

My numbers referred to the native widths of the hardware words. sizeof(int) would of course return those numbers divided by 8, but machines are almost universally referred to by bit width, not byte width. Intel 64 bit chips, not Intel 8 byte chips, for example. So sizeof(int) is still a function of hardware width, and hardware width is defined in terms of bits.

Perhaps I should have been a bit more specific, instead of leaping over fully internalized transforms without explanation? Here? In a discussion about hardware? And note that 36 bits is not a multiple of 8, which actually breaks sizeof() anyway.

C pointers are not hardware pointers

Related Stories