News for hackers. Stuff that matters.
Re:You Can't Always Hash Pointers in C by forrestthewoods on Tuesday May 31, 2016 @04:50AM (#11805475)
You also can't test if a pointer points to an element in an array without undefined behavior.

C++14 5.6/6, on subtracting pointers: "Unless both pointers point to elements of the same array object or one past the last element of the array object, the behavior is undefined."

http://stackoverflow.com/questions/31774683/is-pointer-compa...

I wish "undefined behavior" wasn't a thing in C/C++. It's not worth it. :(

Re:You Can't Always Hash Pointers in C by _yosefk on Tuesday May 31, 2016 @04:56AM (#11805489)
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.

Re:You Can't Always Hash Pointers in C by peteri on Tuesday May 31, 2016 @07:01AM (#11805827)
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)
Re:You Can't Always Hash Pointers in C by cesarb on Tuesday May 31, 2016 @07:35AM (#11805929)
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.

Re:You Can't Always Hash Pointers in C by userbinator on Tuesday May 31, 2016 @07:12AM (#11805860)
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.
Re:You Can't Always Hash Pointers in C by forrestthewoods on Tuesday May 31, 2016 @05:01AM (#11805508)
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.

Re:You Can't Always Hash Pointers in C by pygy_ on Tuesday May 31, 2016 @05:22AM (#11805567)
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.
Re:You Can't Always Hash Pointers in C by Sacho on Tuesday May 31, 2016 @06:37AM (#11805755)
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.

Re:You Can't Always Hash Pointers in C by pygy_ on Tuesday May 31, 2016 @06:55AM (#11805808)
Whelp... Is there a non undefined way to do bounds checking in C?
Re:You Can't Always Hash Pointers in C by pjc50 on Tuesday May 31, 2016 @10:32AM (#11806716)
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.

Re:You Can't Always Hash Pointers in C by wnoise on Tuesday May 31, 2016 @11:25PM (#11811877)
Unsigned overflow/underflow is defined behavior, unlike signed overflow/underflow. Underflow will be caught by the upper range check.
Re:You Can't Always Hash Pointers in C by tehrei on Tuesday May 31, 2016 @11:04AM (#11806908)
I thought unsigned underflow is defined as wrapping?
Re:You Can't Always Hash Pointers in C by Sacho on Tuesday May 31, 2016 @07:16AM (#11805869)
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.

Re:You Can't Always Hash Pointers in C by nightcracker on Tuesday May 31, 2016 @06:15AM (#11805702)
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.
Re:You Can't Always Hash Pointers in C by arethuza on Tuesday May 31, 2016 @05:27AM (#11805579)
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?
Re:You Can't Always Hash Pointers in C by userbinator on Tuesday May 31, 2016 @06:53AM (#11805804)
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.

Re:You Can't Always Hash Pointers in C by caf on Tuesday May 31, 2016 @07:15AM (#11805866)
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.
Re:You Can't Always Hash Pointers in C by qb45 on Tuesday May 31, 2016 @07:51AM (#11805985)
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 ;)

Re:You Can't Always Hash Pointers in C by tomsmeding on Tuesday May 31, 2016 @07:13AM (#11805861)
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.
Re:You Can't Always Hash Pointers in C by pjmlp on Tuesday May 31, 2016 @07:14AM (#11805864)
> 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.

Re:You Can't Always Hash Pointers in C by Bromskloss on Tuesday May 31, 2016 @06:35AM (#11805752)
> I wish "undefined behavior" wasn't a thing in C/C++. It's not worth it. :(

What do you suggest instead? Run-time checks?

Re:You Can't Always Hash Pointers in C by pjmlp on Tuesday May 31, 2016 @07:13AM (#11805863)
Have a proper defined behavior like most sane languages.

The only reason UB exists was that when ANSI C came to be, the compiler writers and hardware vendors that provided C like compilers didn't want to give up on their semantics.

So in order to please everyone, all the semantics that could not be defined on the standard became UB.

Re:You Can't Always Hash Pointers in C by saynsedit on Tuesday May 31, 2016 @12:29PM (#11807515)
I don't think UB is bad. It's a reasonable thing to do when someone invokes an operation with bad input.

For instance, what should `sqrt(-1)` be? Or `head([])`?

You can define all behavior and say "bad input will throw an exception" or "bad input will abort the entire program" but who really cares what it does since it's a malformed program in the first place? Just say it's undefined and it's up to the programmer to make sure it never happens. Otherwise you're littering your code with countless checks for things that should never happen in a properly coded program.

Programmer error is distinct from operational error. There is no sane thing to do in a program error. Constantly checking for programmer error at runtime is wasteful.

Re:You Can't Always Hash Pointers in C by unlinker on Tuesday May 31, 2016 @07:24AM (#11805889)
That is untrue. UB exists because C is supposed to run on so many platforms there is no way to have a defined behaviour for all of them in that standard.
Re:You Can't Always Hash Pointers in C by scott_s on Tuesday May 31, 2016 @09:53AM (#11806485)
You are confusing undefined behavior with implementation defined behavior.
Re:You Can't Always Hash Pointers in C by wongarsu on Tuesday May 31, 2016 @07:38AM (#11805943)
More importantly, C is not only supposed to run on many platforms (many programming languages do that), but also provide very low-level control on wide variety of platforms.
Re:You Can't Always Hash Pointers in C by pjmlp on Tuesday May 31, 2016 @08:26AM (#11806123)
Which people keep forgetting is only available as implementation defined extensions, as such it is no longer ANSI C and any language compiler is free to have extensions.
Re:You Can't Always Hash Pointers in C by jjnoakes on Tuesday May 31, 2016 @07:51AM (#11805986)
This is why implementation defined behavior exists.

Undefined behavior though?

Re:You Can't Always Hash Pointers in C by pjmlp on Tuesday May 31, 2016 @08:25AM (#11806113)
I was already coding before C had any meaning outside UNIX.
Re:You Can't Always Hash Pointers in C by gpderetta on Tuesday May 31, 2016 @06:39AM (#11805761)
You can do it by converting pointers to integers. No UB, but of course it is implementation defined.
Re:You Can't Always Hash Pointers in C by ArkyBeagle on Wednesday June 01, 2016 @07:19PM (#11819110)
UB is unfortunately inherent in the mission statement of 'C'/C++.
Re:You Can't Always Hash Pointers in C by adrianratnapala on Tuesday May 31, 2016 @04:53AM (#11805481)
Or rather I wish the standard did not bend over backwards to allow every kind of aggressive optimisation that some compiler writer claims will increase speed of unoptimized code by 0.5%.
Re:You Can't Always Hash Pointers in C by qb45 on Tuesday May 31, 2016 @06:00AM (#11805663)
This one is about portability, not optimizations. There are architectures where pointer isn't a simple int, due to things like segmentation, tagging or even possibly something as stupid as lack of sufficiently wide integer type.

Heck, there were even C implementations for 36-bit machines, which had 36-bit registers and could only load/store 36-bit-sized and 36-bit-aligned chunks of memory. They packed 4 chars into such word (leaving 4 bits unused) and I don't know how they implemented char* but it must have been something totally mad and not reasonably castable to int or even int*.

Re:You Can't Always Hash Pointers in C by drfuchs on Tuesday May 31, 2016 @12:12PM (#11807386)
DEC's 36-bit PDP-10 and -20 had hardware support for pointers-to-byte: A pointer had lower 18 bits for the (word) address, while the upper 18 bits had room for the bit-offset within the addressed word, and the bit-length of the "byte" being used. So, if you were using 8-bit characters, a pointer to the beginning of a string would roughly look like (0,8,addr). A special "load and increment" instruction would fetch that first character being pointed to, and increment the pointer to (8,8,addr). So, c=*ptr++ in one instruction! After the fourth fetch, the hardware would know to increment from (24,8,addr) to (0,8,addr+1). And, best of all, if you were using plain old ASCII (and assembly rather than C), as was common in the day, you'd use 7-bit chars, packing 5 into each 36-bit word. Or six 6-bit chars if you were only using upper case, as in file names.

So, casting one of these pointers to int the most natural way (leaving the bits alone) would not give you an easily subtractable representation.

Re:You Can't Always Hash Pointers in C by pklausler on Tuesday May 31, 2016 @12:59PM (#11807817)
I don't know how any 36-bit machine implemented C's char pointers, and I can imagine all kinds of other grief stemming from the ones'-complement arithmetic on the 36-bitters with which I'm familiar, but I can tell you how we implemented char pointers on the 64-bit word-addressable Cray-1, -2, and their descendants. The 3-bit byte offset (big-endian, arbitrarily) of a linear byte address was kept in the most significant bits of a 64-bit word, and the 24-bit or 32-bit regular word address was in the least-significant bits. To do pointer arithmetic, code would have to do circular shifts (more accurately, a shift with fill from the same register) to get a linear address and to put it back into the canonical form that I described.

I don't recall whether a cast to int was raw or converted to linear.

Re:You Can't Always Hash Pointers in C by userbinator on Tuesday May 31, 2016 @07:05AM (#11805837)
but it must have been something totally mad and not reasonably castable to int or even int.*

As long as you can impose an ordering on the elements in memory and thus derive a number for each one, it's possible to define the straightforward representation of a pointer. 4 chars per word is an easy case since you can just let char* be a number with the lowest 2 bits indicating the index within a single word, and the rest of the bits are the word-address. int* can be the same number with the lowest 2 bits always 0. If word addresses are smaller than 36 bits, then values with the higher bits set are invalid, and if they're larger, then use multiple words to hold them.

Working with chars on such a machine is going to involve a lot of shifting and otherwise data movement, but there you go, a way to implement C pointers on such a machine.

Re:You Can't Always Hash Pointers in C by qb45 on Tuesday May 31, 2016 @07:33AM (#11805922)
> int* can be the same number with the lowest 2 bits always 0.

And now you have to right-shift int pointers on every dereference for some dubious benefit. It's easier and more efficient to make pointer arithmetic and casting painful.

Re:You Can't Always Hash Pointers in C by adrianratnapala on Friday June 03, 2016 @05:52PM (#11833550)
No, you left-shift them on every cast.

And is someone type-puns using a union, they get a thing four times samller than they might have expected. Stil it is totally well behaved in a hash.

Re:You Can't Always Hash Pointers in C by thomasahle on Tuesday May 31, 2016 @05:27AM (#11805580)
Isn't that the point of C/C++? "Code should run as fast as the hardware allows" and "We allow you to do crazy things that probably won't be portable, if that's what you want".

I wonder, if somebody created a language with C like semantics, like pointer arithmetic, but with a layer in between to ensure consistency and portability.. Would people want to use that, or would the semantics be considered less interesting, when they don't map directly to hardware?

Re:You Can't Always Hash Pointers in C by lmm on Tuesday May 31, 2016 @05:42AM (#11805615)
Corresponding directly to the hardware makes sense, sure. But what modern GCC (especially) does goes far beyond that. The intent of signed integer overflow being undefined is that it will be twos complement on a twos complement machine, not that I want half my code to not run if I had an overflow somewhere.
Re:You Can't Always Hash Pointers in C by caf on Tuesday May 31, 2016 @07:10AM (#11805849)
If that had been the intent, it would have been specified as implementation-defined, not undefined.

More likely, the intent was to also accomodate implementations that trapped on overflow.

Re:You Can't Always Hash Pointers in C by jjnoakes on Tuesday May 31, 2016 @10:06AM (#11806557)
Implementation-defined includes trapping on overflow.
Re:You Can't Always Hash Pointers in C by lmm on Tuesday May 31, 2016 @10:12AM (#11806590)
"Evaluates to an implementation-defined value" would not include that. I'm not sure if any of the usual definitions in the standard includes trapping and doesn't include arbitrary behaviour.
Re:You Can't Always Hash Pointers in C by caf on Tuesday May 31, 2016 @08:09PM (#11811263)
Well, there's kind of one place: when a value is converted to a signed type and it's out of range for that type, the standard says "either the result is implementation-defined or an implementation-defined signal is raised."

However, integer overflow within an expression is trickier than this to define, because you want to preserve the compiler's ability to reorder sub-expressions that are mathematically equivalent when there's no overflow, without forcing the compiler to prove that there won't be overflow. The same is true of CSE and hoisting expressions out of loops.

For example, if you have a machine that traps on overflow and thus under this hypothetical standard your implementation defined signed overflow to trap, you can't simplify (a + 2 - 1) to (a + 1) because the second might trap when the second does not, and your implementation has said that the trap will happen. It also means that you can't hoist an expression out of a loop if that expression might overflow, because the trap has to happen at the point where it would happen on the C virtual machine, not later after other side-effects have become visible.

This is why trapping implementations imply "undefined behaviour" - it's because defining to trap severely restricts the compiler's freedom under the as-if rule to reorder and simplify expressions.

Re:You Can't Always Hash Pointers in C by jjnoakes on Tuesday May 31, 2016 @10:57AM (#11806865)
Sure, but the standard need not say "Evaluates to an implementation-defined value". There are other wordings which use "implementation-defined" and would support trapping on overflow.
Re:You Can't Always Hash Pointers in C by lmm on Tuesday May 31, 2016 @11:43AM (#11807204)
Can you give an example? I struggle to think of anywhere the standard uses a wording that would fit here.
Re:You Can't Always Hash Pointers in C by jjnoakes on Tuesday May 31, 2016 @12:02PM (#11807327)
Why would it have to be wording already in the standard? Does each phrasing in the standard have to appear more than once?
Re:You Can't Always Hash Pointers in C by lmm on Tuesday May 31, 2016 @12:33PM (#11807549)
Adding a new phrase with a new meaning would add a substantial amount of complexity to what's already a very complex standard.
Re:You Can't Always Hash Pointers in C by jjnoakes on Tuesday May 31, 2016 @12:51PM (#11807737)
I disagree. There's nothing difficult to understand about new phrases with new meanings in general.

Do you have a specific phrase which you can show to be sufficiently difficult to understand by a group of people, and which you don't think could be rewritten to retain the same meaning but be easier to understand?

If you do, let me know, and I will try to simplify it for you and help you understand it.

If you don't, then there isn't much to say. Your current argument ("phrases could be written in a difficult to understand way") is too general to be useful.

Re:You Can't Always Hash Pointers in C by lmm on Tuesday May 31, 2016 @05:26PM (#11810400)
I suppose it's less the phrase itself than the concept. What would be a way to say "integer overflow behaviour may reflect the underlying machine, but must be sensible", rigorously enough for the C standard? We've established that "undefined behaviour" is too broad, and "implementation-defined value" is too narrow.
Re:You Can't Always Hash Pointers in C by jjnoakes on Wednesday June 01, 2016 @02:39PM (#11817007)
Why "must be sensible"? Why not just say "signed integer overflow is implementation-defined" and in a footnote say "for example, it may wrap, trap, saturate, or do anything else documented by your implementation"?

I'm not seeing the big deal here.

Re:You Can't Always Hash Pointers in C by lmm on Wednesday June 08, 2016 @05:07AM (#11860944)
> Why "must be sensible"? Why not just say "signed integer overflow is implementation-defined" and in a footnote say "for example, it may wrap, trap, saturate, or do anything else documented by your implementation"?

I don't think that actually defines anything - I don't think GCC would interpret that as anything other than undefined behaviour.

Re:You Can't Always Hash Pointers in C by Sacho on Tuesday May 31, 2016 @07:04AM (#11805832)
If that was the intent, then overflow should have been classified as enumerated implementation-defined behavior, just like the bit representation of an integer type which already deals with those variations.