Sunday, March 20, 2016

Pointer casts in C

The C standard has more restrictions on pointers than what was discussed in the previous blog post. This post covers pointer casts.

Pointer casts and alignment

Casting a pointer invokes undefined behavior if the resulting pointer is not correctly aligned. The standard is written in this way in order to support architectures that use different formats for different kinds of pointers, and such architectures do exist — see for example this mail to the GCC development list about a mainframe architecture that was recently commercially supported with a GCC 4.3 port.

The compiler may use this to optimize memory accesses for processors with strict alignment requirements (such as old ARM processors). Consider for example
void foo(void *p)
    memset(p, 0, 4);
that clears 32 bits of data. This could be generated as a 32-bit store, but the alignment of p is unknown, so the compiler must generate this as four byte operations if it want to inline the memset
mov     r3, #0
strb    r3, [r0, #0]
strb    r3, [r0, #1]
strb    r3, [r0, #2]
strb    r3, [r0, #3]
Consider now
void bar(int *);

void foo(void *p)
    memset(p, 0, 4);
The call to bar will convert p to an int* pointer, and this invokes undefined behavior if p is not 32-bit aligned. So the compiler may assume p is aligned, and the memset can now be generated as a 32-bit store
mov     r3, #0
str     r3, [r0, #0]
This example illustrates two things that often cause confusion with regard to undefined behavior
  • The effect of undefined behavior may go back in time — the undefined behavior is invoked when calling bar, but the compiler may use this to optimize code executed before bar in a way that would make it misbehave if p was not correctly aligned.
  • The compiler just use the undefined behavior of misaligned conversion to determine that p must be aligned, which then affects each use of p in the same way as if the alignment had been known by some other means — i.e. the compiler developers do not go out of their way implementing evil algorithms doing obscure transformations back in time based on undefined behavior.

Function pointers

It is not allowed to cast between a function pointer and a pointer to object type (i.e. a "normal" pointer). The reason is that they may be very different on a hardware level, and it may be impossible to represent data pointers as function pointers, or vice versa. One trivial example is when function pointers and data pointers have different width, such as the MS-DOS "medium" memory model that use 32-bit pointers for code but only 16-bit pointers for data.

Casting between integers and pointers

Casting between integers and pointers are implementation defined, so the compiler may choose to handle this in any way it want (although the standard has a footnote saying that the intention is that the mapping between pointers and integers should "be consistent with the addressing structure of the execution environment").

The only thing that is guaranteed to work on any implementation is casting between the integer value 0 and pointers:
An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.
I have read far too many confused discussions about if the value of NULL is guaranteed to be 0. In some sense it is, as (void*)0 == NULL evaluates to true, but the value of (void*)NULL does not need to be 0 when stored in memory — the implementation may for example choose to implement the cast operator as flipping the most significant bit,1 which means that the code
union {
    uintptr_t u;
    void *p;
} u;
u.p = 0;
printf("0x%" PRIxPTR "\n", u.u);
prints 0x80000000 on a 32-bit machine.

One other thing to note is that NULL is defined as being a "null pointer constant", which does not need to be of a pointer type per the quoted text above! This may cause problems when passing NULL to a va_arg function.

1. This is not a completely stupid example. Consider a small embedded processor that has some hardware mapped at address 0. The platform does not have much memory, so 0x80000000 is guaranteed not to be a valid address, and the implementation use this for NULL. There are in general better ways of handling this, but I have seen this done for real hardware...

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)
    if (p == q)  // Undefined behavior!
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)
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!
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