Hacker News Reader

Comment by _yosefk | Hacker News Reader

I think you can do that test by comparing pointers, you just can't subtract them. (The SO answer you link to also points out that comparing and subtracting are different, but I'm not sure that what I said follows.)

In practice, almost all C and C++ programs depend on both implementation-defined and undefined behavior, and, modulo security implications, that's fine as long as you test the program properly after compiling with a new compiler.

View on HN

I'd guess that PAE on x86 systems might really hurt with this. Basically any system where the memory model is one of segment + offset will run into trouble with pointer comparisons. Ever since the 8086 I've assumed that pointer math is tricky and non portable (see http://catb.org/jargon/html/V/vaxocentrism.html for the 80s version of the same problem)

PAE means pointers that need to hold at least 36 bits, but in practice I don't think anyone, OS developers included, would ever treat the whole PAE address space as one entity and represent addresses with a single pointer.

PAE means you have longer physical addresses, but pointers are always virtual addresses. That is, the difference is only visible in the layout of the page tables.

Segment+offset is something else, but even on 32-bit x86 the segments were almost always set to base 0, and AMD64 dropped most of the segment mechanism. The exception on both is using segments to access thread-local data, but even then it's used just as an offset into the same flat address space.

You can test equality with a given element. But if you want to test "does this pointer to any element of that array" you can't. As this test would be:

bool b = ptr - array_start < array_end - array_start

But that first subtraction is undefined if ptr does not point to an element between start and end.

Not that this is exactly a common operation or anything. But the fact that a seemingly simple and obvious test is undefined behavior is crazy imo.

What about

    array_start <= ptr && ptr < array_end // or `<=` if the upper bound is inclusive

Edit: well, for one it may not be thread safe, since it's not atomic, but neither is your example AFAIK.

Your edit is pretty much irrelevant - it could be applied to literally any example code anywhere. Unless mentioned otherwise you should assume that all variables are thread-local.

Evaluating that expression is undefined behavior if ptr is outside the +1 bounds of the array. Check out the enumerated defined behavior in the (old C99, working draft) standard - http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf

6.5.8 Relational operators

...and pointers to array elements with larger subscript values compare greater than pointers to elements of the same array with lower subscript values...

... If the expression P points to an element of an array object and the expression Q points to the last element of the same array object, the pointer expression Q+1 compares greater than P.

In all other cases, the behavior is undefined.

Whelp... Is there a non undefined way to do bounds checking in C?

I'm just a C newbie, so I can't give you a definitive answer. Here's two I came up with:

If you know the bounds of the array, then you could enumerate it and check if the pointers to any of its elements are equal to your pointer.

Alternatively you could store references to array elements as a structure of a start pointer + offset, and arrays as a pair of start and end pointers. Then checking if a reference points to part of the array would be a two-step operation - check that the starts match and that your offset is within the end - start bounds.

Avoid maintaining pointers into arrays and instead maintain indices. If you maintain them as unsigned then you only need one range check (although you then have to avoid underflow if you want to stay in the realm of defined behaviour).

One of the downsides to C is that K&R and most source code out there will encourage you to do pointer arithmetic freely, but the standard points out all kinds of surprises where it is undefined. So you get technically non-conformant code in widespread use.

I thought unsigned underflow is defined as wrapping?

Unsigned overflow/underflow is defined behavior, unlike signed overflow/underflow. Underflow will be caught by the upper range check.

It's been a long time since I wrote C for a living, but what would you expect sensible behaviour to be for the expression ptr - array_start if ptr isn't in the array?

Do the subtraction and divide by the size of the pointed-to type, like the expression says? Why would you expect the calculation to be any different if ptr was inside, one element past, two elements past, or 1000 elements away from the ends of the array?

I can understand it possibly being a problem if the two pointers being subtracted denote completely different address spaces (which is definitely possible on some architectures, particularly Harvard MCUs; the one that comes to mind immediately is the 8051 which has IRAM, XRAM, and PMEM), and even there you can "linearise" address spaces so one comes after another and subtraction still works despite possibly giving a meaningless result, but on any architecture where all pointers are in the same address space, the sensible behaviour is the most consistent and straightforward one.

The idea here is that if you have segment:offset pointers, like x86 real mode, then you (as a compiler writer) don't have to worry about the segment part at all - you can just subtract the offsets and shift, because pointers within the same object will have the same segment part.

Just nitpicking, but in real mode it is at least conceivable to implement arbitrary pointer arithmetic (at some significant performance hit) because segments are spaced evenly every 16 bytes.

The real killer is arbitrary segmentation, where software can say this segment start here and that segment starts there, like, say, the x86 protected mode. Is the OS going to expose absolute segment addresses to the C language to allow some "defensive programming" like checking if a pointer really points to the array you think it does? Hell no, you write your damn code correctly ;)

You expect a pointer to represent a location in linear memory, so you expect ptr - array_start to be a negative number if ptr is before the array, and a number larger than the array size if it's after the array.

> that's fine as long as you test the program properly after compiling with a new compiler.

Which 40 years of experience prove that it doesn't happen as much as it should.

Reply on news.ycombinator.com