Sunday, March 6, 2016

C pointers are not hardware pointers

Pointers in the C language are more abstract than pointers in the hardware, and the compiler may surprise developers that think that pointers in C work in the same way as pointers in the CPU.

A C pointer points into what the standard calls an object, points to the byte following the object, or has the value NULL. The concept of "object" here is very different from the C++ object — an object in the C standard is a range of bytes allocated as a unit,1 so x and y are objects in
int x;
struct foo y[10];
and the memory returned by a call to malloc is an object.

Dangling pointers are dangerous, and may invoke undefined behavior even when they are not dereferenced. The reason is that the value of a pointer becomes indeterminate when the object it points to (or just past) reaches the end of its lifetime. That is, a dangling pointer is treated the same way as an uninitialized pointer, and all use of uninitialized values invokes undefined behavior.
void foo(int *p, int *q)
{
    free(p);
    if (p == q)  // Undefined behavior!
        bar();
}
The pointer p has indeterminate value after free(p), so the comparison invokes undefined behavior.

Comparing pointers using the relational operators (<, >, <=, and >=) requires them to point into the same object (or the byte following the object). That is
int *p = malloc(64 * sizeof(int));
int *q = p + i;
if (p < q)
   foo();
is fine (provided that 0 ≤ i ≤ 64), but
int *p = malloc(64 * sizeof(int));
int *q = malloc(64 * sizeof(int));
if (p < q)  // Undefined behavior!
   foo();
invokes undefined behavior. Similarly, subtraction of pointers are only allowed for array objects, and both pointers must point into the same array object (or the byte following the object).

Arithmetic on a pointer cannot make it point outside the object (more than on the byte following the object). In particular, arithmetic on a pointer cannot make it point into another object. This is useful for compilers, as they can use this to track memory accesses and trivially determine that reads and writes through pointers derived from different objects do not conflict. Actually, it would be very hard for the compiler to place variables in registers if writes through pointers could modify arbitrary objects!

There is however one special case where a pointer can point to the address of another object — two objects may be placed next to each other in memory, which is typical for cases such as as
int x, y;
and p and q can now have the same value after
int *p = &x + 1;
int *q = &y;
But the pointer p does not really point to y — it points to the address following x. Dereferencing p invokes undefined behavior, so you cannot really use the fact that p and q have the same value.

GCC has a somewhat aggressive interpretation on the standard, so it compiles p == q to false if it determines that they are derived from different objects (see GCC bug 61502 for details). This has the fun effect that it is possible to get pointers p and q that point at the same memory address, but p == q evaluates to false, as in
#include <stdio.h>

int main(void)
{
    int x, y;
    int *p = &x + 1;
    int *q = &y;
    printf("%p %p %d\n", (void*)p, (void*)q, p == q);
    return 0;
}
that prints
0x7f7fffffdafc 0x7f7fffffdafc 0
on my development machine when compiled with a recent GCC.


1. The C standard's definition of object is a bit more involved, as it also involves the type of the data within the range of bytes, but this does not affect the discussion in this blog post. I'll come back to the type related part in a future blog post on aliasing.

This blog post was updated 2016-05-19:
  • Added casts in last example
  • Changed 256 to 64*sizeof(int) in examples

23 comments:

  1. Technically, your last example can invoke undefined behavior because the %p format specifier requires a pointer-to-void, and there's no implicit conversion from pointer-to-object to pointer-to-void when the former is passed through a variadic function.

    Also, are you sure that the one-past-end rule is formulated in terms of "bytes"? The standard doesn't say that. When int a[10]; int *p = a + 10; p doesn't "point to the byte following a" – it is said to point "one past the last element of the array object" (C99 6.5.6.8).

    ReplyDelete
    Replies
    1. Thanks! I have updated the example to cast the pointers.

      Delete
  2. @H2CO3 You are right that the standard does not really talk about bytes. My intention was to write in an informal way that does not get lost in the legalese, and "one past the last element" and the "byte following" are the same thing on real computers. BTW, the C99 rationale use a similar explanation: "This stipulation merely requires that every object be followed by one byte whose address is representable."

    ReplyDelete
  3. C pointers are not required to point anywhere. For example, `int i[1]; &i[1]` is a valid pointer that points nowhere. Furthermore, the term *object* is defined as “region of data storage in the execution environment, the content of which can represent a value.” I don't see the word *type* mentioned anywhere.

    ReplyDelete
  4. If you want to work around the pointer comparison with different objects, cast the pointers to an intptr_t and compare those. That should work.

    ReplyDelete
  5. @Robert The C11 standard says in 6.5.6 "the expression (P)+1 points one past the last element of the array object", so I think my usage of "point to" is sufficiently correct. :-)

    You are right about the definition of object in 3.15 (but the NOTE actually mention that types are involved when referencing the object), but part of the rest of the standard does not make sense unless types are involved in the concept of object (as they need the object to be an array object etc.), and the type system is described using "object types (types that describe objects)" etc.

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

    *p may change in your example, but what should change p?

    ReplyDelete
  7. The concept of "object" here is very different from the C++ object ...

    Actually the C and C++ standards have very similar definitions for the word "object".

    jak:

    If you want to work around the pointer comparison with different objects, cast the pointers to an intptr_t and compare those. That should work.

    Not necessarily. You can convert a pointer to the integer type intptr_t, but the result is not guaranteed to be meaningful.

    Sorcire:

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

    *p may change in your example, but what should change p?

    free(p) doesn't change the value of p (or at least doesn't change its representation), but the value of p does become indeterminate.

    ReplyDelete
  8. In the last example, since x and y are allocated on the stack, and since the stack grows upwards, I have to do it this way to get the addresses to match:

    int x, y;
    int *p = &x;
    int *q = &y+1;
    printf("%p %p %d\n", p, q, p == q);


    And I actually get this output:

    C:\Users\Keith>gcc test.c
    C:\Users\Keith>a.exe
    0028FF34 0028FF34 1

    ReplyDelete
  9. Have you seen the AAP project? (http://www.embecosm.com/appnotes/ean13/ean13.html)

    It is designed to be the CPU architecture from hell. The background for this is that compilers make a lot of assumption about pointer sizes, datawidths and int sizes, that aren't necessarily true, something that you also demonstrate in this blog post.

    We actually have a GSoC project under the FOSSi Foundation umbrella this year to turn the AAP into a real CPU to be run on an FPGA fossi-foundation.org/gsoc16-ideas.html

    ReplyDelete
  10. I am with @Keith Thompson on the free(p) topic. The value of p (i.e. the address that p points to) will not change as a result of free as function parameters are sent by value. The contents of the memory at that address, that's what's indeterminate after free.

    Btw, on your last example I get the following with gcc 5.2.1 on Ubuntu:
    0x7ffc7085e5f4 0x7ffc7085e5f4 1

    However, my gut tells me not to rely on the fact that two consecutively-defined variables will have consecutive addresses (with respect to the type size). What if you don't have ints and alignment becomes an issue?

    ReplyDelete
  11. @Andrei Yes, you cannot rely on two consecutively-defined variables having consecutive addresses. And the example is in some sense just an amusing example of problem you can get if you would try to exploit the fact that they are consecutive on a particular platform.

    ReplyDelete
  12. @Sorcire As Keith said, p does not change, but all usages of it becomes undefined.

    The C99 rationale has an example of where usage of p may fail:
    "Consider a hypothetical segmented architecture on which pointers comprise a segment descriptor and an offset. Suppose that segments are relatively small so that large arrays are allocated in multiple segments. While the segments are valid (allocated, mapped to real memory), the hardware, operating system, or C implementation can make these multiple segments behave like a single object: pointer arithmetic and relational operators use the defined mapping to impose the proper order on the elements of the array. Once the memory is deallocated, the mapping is no longer guaranteed to exist. Use of the segment descriptor might now cause an exception, or the hardware addressing logic might return meaningless data."

    ReplyDelete
    Replies
    1. When the authors of the Standard say that some action invokes Undefined Behavior, that is an invitation for compiler writers to do whatever would best suit the compiler's intended purpose. If a compiler's purpose is to run code which doesn't need to do anything "interesting" with pointers, on hardware which handles pointers in "unusual" fashion, that purpose may be best accomplished by allowing weird things to happen if code uses pointers in unusual ways. That in no way implies that compilers intended for other purposes (e.g. supporting a wide range of common application fields on commonplace hardware) shouldn't support predictable behaviors beyond those mandated by the Standard.

      Delete
  13. @Olof Thanks! Handling evil CPUs are one of my interests, so I'll definitely take a look at AAP!

    ReplyDelete
  14. I'm not at my machine, but what happens if you change it to:

    int x, dummy, y;

    Any effect?

    ReplyDelete
  15. The first example makes no sense whatsoever:
    void foo(int *p, int *q)
    {
    free(p);
    if (p == q) // Undefined behavior!
    bar();
    }

    ...why would (p == q) be undefined behavior? Does this imply that the compiler has some knowledge of what free() does? What if free() is a local function that does nothing but returns?

    ReplyDelete
  16. Continuing along the same lines:
    In free(p), 'p' is passed by value, so it is guaranteed not to be modified...so, why would behavior be undefined? Makes no sense.
    int *p = malloc(256);
    int *q = malloc(256);
    if (p < q) // Undefined behavior!
    foo();
    ...same here -- why would you assume that there's undefined behavior? It is perfectly well-defined. I think you need to take another run at your examples to make your point. As it stands now, your point is...well, undefined

    ReplyDelete
  17. Ilya: My point is that the standard has more restrictions than what you may think is reasonable by looking at normal hardware.

    Annex J in the standard lists all undefined behavior (with references to the section specifying the restriction), and the two cases you are asking about are covered by:
    * An object is referred to outside of its lifetime (6.2.4).
    * Pointers that do not point to the same aggregate or union (nor just beyond the same array object) are compared using relational operators (6.5.8).
    So it does not need to make sense -- it is undefined because the standard says so! :-)

    But there is a reason why the standard has these restrictions. I gave one example in a previous comment (with text from the C99 rationale document): "Consider a hypothetical segmented architecture on which pointers comprise a segment descriptor and an offset. Suppose that segments are relatively small so that large arrays are allocated in multiple segments. While the segments are valid (allocated, mapped to real memory), the hardware, operating system, or C implementation can make these multiple segments behave like a single object: pointer arithmetic and relational operators use the defined mapping to impose the proper order on the elements of the array. Once the memory is deallocated, the mapping is no longer guaranteed to exist. Use of the segment descriptor might now cause an exception, or the hardware addressing logic might return meaningless data."

    ReplyDelete
  18. Krister: I agree that C compilers can make some unexpected assumptions. However, your first example does not demonstrate referring to an object outside of its lifetime. Perhaps, something like this would qualify:

    void foobar()
    {
    int *p, *q;

    {
    int x;
    p = &x;
    q = &x;

    }

    if( p == q ) { // 'x' is out of scope and the compiler knows it

    ...so, I can certainly see the compiler doing something unexpected here. However, using free() does nothing to inform the compiler of anything that it can optimize or make a decision on -- not in your example anyway. So, once again, I disagree that your first code segment would lead to undefined behavior.

    Same here:
    int *p = malloc(256);
    int *q = malloc(256);
    if (p < q) // Undefined behavior!
    foo();

    ...let's imagine that...

    static unsigned i=0;
    static char buf[BIG_NUMBER];
    void *malloc(unsigned size)
    {

    i += size;
    return &buf[i-size];
    }

    We're pointing to the same aggregate object, so I would think relational pointer comparison would make perfect sense.

    And your last example does make sense, as the pointer p and q point to two disparate objects whose addresses cannot be compared.

    ReplyDelete
    Replies
    1. Comparing (p < q) when from different malloc() calls is technically unspecified (technically not the same as undefined as the standard treats those terms differently). Sometimes p will be < q and sometimes q will be < p. There is no guarantee based on the order of calling malloc how they will be allocated.

      Delete
  19. Your example:
    int *p = malloc(256);
    int *q = p + i;
    if (p < q)
    foo();

    and then state it is fine (provided that 0 ≤ i ≤ 64). However, that is only true if sizeof(int)==4. You can not assume that, as it could be 8 or 2 or plenty of other valid but less common values.



    ReplyDelete