GCC and pointer overflows

Posted Apr 24, 2008 20:39 UTC (Thu) by nix (subscriber, #2304) [Link]

You can't (yet) attach attributes to arbitrary expressions, though.

Posted Apr 16, 2008 19:50 UTC (Wed) by MathFox (guest, #6104) [Link]

Posted Apr 16, 2008 20:54 UTC (Wed) by JoeBuck (subscriber, #2330) [Link]

Posted Apr 17, 2008 14:06 UTC (Thu) by iabervon (subscriber, #722) [Link]

How so? I was only suggesting that the expression "pointer1 + offset >= pointer2" be treated
differently (that is, the magic does away if you store the LHS in a variable and use the
variable). (And, of course, the change would only apply to cases where the LHS overflows the
address space, which is clearly undefined, so having odd things matter isn't a problem.)

If you do something with "pointer + offset" other than comparing it with something else, I
wouldn't have anything change (what would it do, anyway, without a test and branch in the
code?); and in the case where you're doing the comparison, processors generally have a status
bit that gets updated in the multiply/shift and add and is pretty much free to have an
unlikely jump based on. Except on architectures where the instruction decode significantly
limits the pipeline, it should be at most one cycle to test so long as you do each test right
after the ALU operation.

C, in general, doesn't make good use of the fact that processors make it trivial to test for
overflow, but that doesn't mean that C compilers can't do extra-clever things with this
ability in cases where there's undefined behavior associated with it.

Posted Apr 16, 2008 23:31 UTC (Wed) by wahern (subscriber, #37304) [Link]

I should be more clear. Because there's no "one before" rule, then "buffer + len < buffer"
will always be false in a correct program. A correct program would not attempt to derive an
invalid pointer (let alone access an object through such a pointer).

It's worth noting that "buffer" is the actual object, not merely a pointer. This is an
instance where we can't forget that arrays and pointers in C really are distinct, even though
we can so often treat an array like a pointer. And the compiler in this instance has
sufficient information about the object to make the optimization, whereas in many other
instances it would not be able to do this (and so people get the wrong impression). This is a
good thing.

Posted Apr 17, 2008 16:01 UTC (Thu) by wahern (subscriber, #37304) [Link]

if (~sizeof buf < len) {
    die();
}

This only works with unsigned values, and there are probably some caveats with width and
promotion rules (portable, nonetheless).

Also, assuming your environment uses linear addressing, and there's no other funny stuff going
on with pointer bits (like the effectively 16 free bits on AMD64--using 48-bit addressing).

if (~(uintptr_t)buf < len)  {
    die();
}

I believe this should work on Windows and all Unix systems (guaranteed by additional SUSv3
constraints), but I'm not positive.

Posted Apr 17, 2008 17:14 UTC (Thu) by jzbiciak (✭ supporter ✭, #5246) [Link]

No, I meant 32 bit system. If you do the pointer arithmetic first on an array of structs whose size is 65536, then any length > 32767 will give a byte offset that's >= 2³¹ away. A length of 65535 will give you a pointer that's one element before the base.

I guess it's an oversimplification to say 32767 specifically. Clearly, any len > 65535 will wrap back around and start to look "legal" again if the element size is 65536. Any len <= 65535 but greater than some number determined by how far the base pointer is from the end of the 32-bit memory map will wrap to give you a pointer that is less than the base. So, the threshold isn't really 32767, but something larger than the length of the array.

That was my main point: When you factor in the size of the indexed type, the threshold at which an index causes the pointer to wrap around the end of the address space and the potential number of wrapping scenarios gets you in trouble. Thus, the only safe way is to compare indices, not pointers.

For example, suppose the compiler didn't do this particular optimization, and you had written the following code on a machine for which sizeof(int)==4:

extern void foo(int*);

void b0rken(unsigned int len)
{
    int mybuf[BUFLEN];
    int *mybuf_end = mybuf + BUFLEN;
    int i;

    if (mybuf + len < mybuf_end && mybuf + len >= mybuf)
    {
        for (i = 0; i < len; i++)
            mybuf[i] = 42;
    }

    foo(mybuf);  /* prevent dead code elimination */
}

What happens when you pass in 0x40000001 in for len? The computed pointer for mybuf + len will be equal to &mybuf[1], because under the hood, the compiler multiplies len by sizeof(int), giving 0x00000004 after truncating to 32 bits. How many times does the loop iterate, though?

This happens regardless of whether the compiler optimizes away the second test.

Now, there is a chance a different optimization saves your butt here. If the compiler does common subexpression elimination and some amount of forward substitution, it may rewrite that if statement's first test as follows. (Oversimplified, but hopefully it gives you an idea of what the compiler can do to/for you.)

Step 0: Represent pointer arithmetic as bare arithmetic (internally)

    mybuf + 4*len >= mybuf_end

Step 1: Forward substitution.

    mybuf + 4*len >= mybuf + 4*BUFLEN

Step 2: Remove common terms from both sides. (Assumes no integer overflow with pointer arithmetic--what started this conversation to begin with.)

    4*len >= 4*BUFLEN

Step 3: Strength reduction. (Again, assumes no integer overflow with pointer arithmetic.)

    len >= BUFLEN

That gets us back to what the test should have been to begin with. There's no guarantee that the compiler will do all of this though. For example, GCC 4.2.0 doesn't seem to optimize the test in this way. I just tried the Code Composer Studio compiler for C64x (v6.0.18), and it seems to do up through step 2 if the array is on the local stack, thereby changing, but not eliminating the bug.

It turns out GCC does yet a different optimization that changes the way in which the bug might manifest. It eliminates the original loop counter entirely, and instead transforms the loop effectively into:

    int *ptr;

    for (ptr = mybuf; ptr != mybuf + len; ptr++)
        *ptr++ = 42;

This actually has even different safety characteristics.

Moral of the story? Compare indices, not computed pointers to avoid buffer overflows.

Posted Apr 17, 2008 17:24 UTC (Thu) by clugstj (subscriber, #4020) [Link]

OK, how about this: if you don't trust the code, don't use the latest whiz bang optimizations!

The documentation for GCC should specifically warn about optimizations that can do bad things
with questionable code.  As an example, here is a quote from the "Sun Workshop 6 update 2" man
page:

            -xO3 In addition to optimizations performed at the
                    -xO2 level, also optimizes references and
                    definitions for external variables.  This
                    level does not trace the effects of pointer
                    assignments.  When compiling either device
                    drivers that are not properly protected by
                    volatile, or programs that modify external
                    variables from within signal handlers, use
                    -xO2

Let's not penalize GCC because of how some people will use/abuse it.

Posted Apr 17, 2008 20:39 UTC (Thu) by brouhaha (subscriber, #1698) [Link]

That would be a fine optimization to use when you choose some high level of optimization that includes unsafe optimizations, but it shouldn't happen at -O1.

Posted Apr 18, 2008 21:22 UTC (Fri) by mikov (subscriber, #33179) [Link]

Exactly my point. It is not easy to imagine a case where this is a _desirable_ optimization.
It is either a bug, which should be warned, or it is deliberate. Either way the compiler
should not remove the code!

I imagine however that the general assumption "int + positive_value is always greater than
int" may be useful for complex loop optimizations and the like. It probably allows to
completely ignore integer overflow in cases like this "for (int i = 0; i < x; ++i ) {...}". 

Posted Apr 18, 2008 22:03 UTC (Fri) by giraffedata (subscriber, #1954) [Link]

I would prefer a warning only if there's an easy way to disable the warning. And Gcc almost never provides a way to say, "don't warn me about this particular piece of code; I've already verified it's supposed to be that way." The things I have to do to stop warning messages often make the code harder to read or slower to execute. But because the warnings are so often valid, I won't accept any code that generates any warnings.

I've used other compilers that at least have the ability to turn off warnings for a certain stretch of source code. And others have fine-grained selection of types of warnings.

I prefer the compiler to warn about it, not to silently optimize the code.

I really don't think of what the compiler is doing as "optimizing away" my code. It's not throwing away code I wrote, it's simply implementing it with zero instructions, because that's an efficient way to implement what I wrote. The warning isn't, "I didn't generate any instructions for this." It's, "you wrote something that a programmer normally wouldn't write intentionally, so maybe you meant to write something else."