gcc/clang pointer equality bug demo

README.md

I believe I've found a bug in the implementation of the "==" operator for pointers in both gcc and clang.

pointer_equality_bug.c is a demonstration of the bug.

Quoting N1570 6.5.9p6:

Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function, both are pointers to one past the last element of the same array object, or one is a pointer to one past the end of one array object and the other is a pointer to the start of a different array object that happens to immediately follow the first array object in the address space.

with a footnote:

Two objects may be adjacent in memory because they are adjacent elements of a larger array or adjacent members of a structure with no padding between them, or because the implementation chose to place them so, even though they are unrelated. If prior invalid pointer operations (such as accesses outside array bounds) produced undefined behavior, subsequent comparisons also produce undefined behavior.

I posted the initial version of the demo program to comp.lang.c on Sun 2014-10-19, Message-ID: <[email protected]>. A Google Groups link to the original article is here.

Thomas Richter pointed out that the quoted clause applies only to array objects, and the original version of the test program uses non-array int objects. The standard says, in 6.5.9p7, that:

For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.

But to avoid any ambiguity, I've updated the program to use explicit array objects, and the problem still exists.

Compiling with -S to generate an assembly listing shows that no code is generated for the puts("ok") call, implying that this is an optimization bug that occurs even with no optimization specified (equivalent to -O0).

If my interpretation is correct, and this is a compiler bug, I don't think it's likely to affect real-world code. There's not much reason to compare a pointer to one object vs. a pointer just past the end of another object for equality. The relevant clause in the standard is, I think, intended to make == behave consistently in all cases, even ones that are not particularly useful.

Tue 2014-10-21 I've submitted bug reports against gcc:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63611
and clang:
http://llvm.org/bugs/show_bug.cgi?id=21327

Mon 2014-10-27 Tim Rentsch points out that N807, submitted by Clive D.W. Feather on 1997-12-27, discusses this. It refers to DR 172; I'll track that down and update this later.

pointer_equality_bug.c

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    typedef struct {
        int arr[32];
    } element;
    element x[1];
    element y[1];
    element *const x0 = x;
    element *const x1 = x0 + 1;
    element *const y0 = y;
    element *const y1 = y0 + 1;

    /*
     * x and y will typically be adjacent in memory.
     * x0 points to x; x1 points just past it.
     * y0 points to y; y1 points just past it.
     * We should have x1 == y0 if and only if y immediately follows x.
     * We should have y1 == x0 if and only if x immediately follows y.
     */

    printf("x  = %p\nx0 = %p\nx1 = %p\ny  = %p\ny0 = %p\ny1 = %p\n",
           (void*)x, (void*)x0, (void*)x1,
           (void*)y, (void*)y0, (void*)y1);

    if (x1 == y0) {
        puts("y immediately follows x");
        if (x + 1 == y) {
            puts("ok");
        }
        else if (x + 1 != y) {
            printf("inconsistent behavior:\n"
                   "    %p !=\n"
                   "    %p\n",
                   (void*)(x + 1),
                   (void*)y);
            exit(EXIT_FAILURE);
        }
        else {
            printf("inconsistent behavior:\n"
                   "    %p !=\n"
                   "    %p\n",
                   (void*)(x + 1),
                   (void*)y);
            exit(EXIT_FAILURE);
        }
    }
    else if (y1 == x0) {
        puts("x immediately follows y");
        if (y + 1 == x) {
            puts("ok");
        }
        else if (y + 1 != x) {
            printf("inconsistent behavior:\n"
                   "    %p !=\n"
                   "    %p\n",
                   (void*)(y + 1),
                   (void*)x);
            exit(EXIT_FAILURE);
        }
        else {
            printf("inconsistent behavior:\n"
                   "    %p !=\n"
                   "    %p\n",
                   (void*)(y + 1),
                   (void*)x);
            exit(EXIT_FAILURE);
        }
    }
    else {
        puts("x and y are not adjacent");
    }
}

pointer_equality_bug.clang.out

$ uname -a
Linux m5 3.13.0-24-generic #47-Ubuntu SMP Fri May 2 23:30:00 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux
$ clang --version
Ubuntu clang version 3.4-1ubuntu3 (tags/RELEASE_34/final) (based on LLVM 3.4)
Target: x86_64-pc-linux-gnu
Thread model: posix
$ clang -std=c11 -pedantic -Wall -Wextra pointer_equality_bug.c -o pointer_equality_bug && ./pointer_equality_bug
x  = 0x7fff92486cd0
x0 = 0x7fff92486cd0
x1 = 0x7fff92486d50
y  = 0x7fff92486c50
y0 = 0x7fff92486c50
y1 = 0x7fff92486cd0
x immediately follows y
inconsistent behavior:
    0x7fff92486cd0 !=
    0x7fff92486cd0
$ 

pointer_equality_bug.gcc.out

$ uname -a
Linux m5 3.13.0-24-generic #47-Ubuntu SMP Fri May 2 23:30:00 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ gcc -std=c11 -pedantic -Wall -Wextra pointer_equality_bug.c -o pointer_equality_bug && ./pointer_equality_bug
x  = 0x7fff40da7f90
x0 = 0x7fff40da7f90
x1 = 0x7fff40da8010
y  = 0x7fff40da8010
y0 = 0x7fff40da8010
y1 = 0x7fff40da8090
y immediately follows x
inconsistent behavior:
    0x7fff40da8010 !=
    0x7fff40da8010
$