You Can't Always Hash Pointers in C
nullprogram.com
nullprogram.com
If you're porting to that type of system, you will be keenly aware of this. The problem can be solved.
On the Intel 8086, every address has 4096 ways of referring to it by some combination of segment:offset. A segment is 64 kilobytes wide, and the segment: part of the address is "paragraph" (16 byte block) aligned. 65536/16 = 4096. For instance address 0x1234 can be referenced as 0123:0004, or 0122:0014 and so on.
However, there is a unique underlying address.
A pointer value can be normalized (using nonportable code, of course) to use, say, the largest possible segment value and the smallest possible offset. The resulting value can then be hashed.
Another way to deal with it on 8086 might be to use a "far" pointer, and calculate its offset from a "far" null pointer:
(far char *) ptr - (far char *) 0;
So that is to say, the concept of hashing an address is sound; only using "pointer" to mean "address" is not maximally portable. An implementation of pointer hashing can be ported to such architectures by some nonportable code, if necessary.
If you care about such portability, wrap the "pointer to integer address" logic in a function and implement that function as necessary.
Bottom line, the pointer to integer conversion should be specified by your platform ABI. Read it, then either refuse to support your program on platforms with insane ABIs or have a fallback path for them.
The first MacOS used those bits for some things; notably desk accessories. It took them years to kill that practice so that later virtual memory versions of the Mac would work. IBM made a similar mistake in OS/360 (24 bit address space, 32-bit pointer values . . . that was very bad).
And you're right, people absolutely did use it.
On the Amiga I believe that Amiga BASIC (developed by Microsoft) was perhaps the most prominent example of Amiga applications that allegedly did this (only source I've found for this is a comment by a former Commodore employee - Dr Peter Kittel), amongst a massive amount of other problems. People did get it running on 68020+ systems, with a combination of patches and disabling fast ram, but it was pretty much forgotten from AmigaOS 2.x onwards anyway.
Or perhaps not; it depends on whether the tags are immutable attributes. For instance if they indicate type, and type is immutable, then they can perhaps just be mixed into the hash. Under this design, the only way two pointers to the same thing can have a different hash is if you have a use-after-free bug: you're hashing a pointer to something that was de-allocated and re-allocated as a new kind of object. Two objects which occupy the same address at different times don't have to have the same hash, even if it is a pointer hash.
Looked at in another way, those tag bits, if they are immutable, effectively extend the address space. An object with tag 0101 and another one with 0110, all other bits equal, can be considered to be in different spaces (with the constraint that since they collide to the same physical address, they cannot exist simultaneously).
The point is/was that relying on bits that are unused today is risky because it has historically tended to ensure your software breaks when the next CPU generation needs more of the possible address space.
Note specially that a lot of the apps that used the top 8 bits did not use it for type tags that might imply safe usage, but often used it to store unrelated data.
E.g. lets say you had a data structure with a number of pointers and a number of flags. You might very well decide to pack the structure so that the flags overlapped the top 8 bits of the pointers.
Same tricks are used even today. E.g., have a look at Facebook's DiscriminatedPtr from the folly library, which uses the top 16bit of a 64bit pointer (otherwise unused) for type tagging.
The problem is when the architecture lets you get away with explicitly masking out the tag bits (i.e. a tagged pointer is a valid pointer) which makes it hard to evolve the architecture.
Possibly, I wasn't sure so I hedged :).
And yes, I heard that the issue was mostly encountered on the Amiga.
System 7 was the first OS to support 32-bit.
heh, I just published a post on this that I worked on over the weekend: https://nickdesaulniers.github.io/blog/2016/05/30/data-model...
This helps debugging, but it doesn't help future extensions of AMD64. Programs exist that store data in bits 48..63 of a pointer on AMD64, and expect to retrieve a pointer by doing "x << 16 >> 16" on the integer data. Increasing the address space is a pain no matter what.
The old Mac OS did this: https://en.wikipedia.org/wiki/Mac_OS_memory_management#32-bi...
When Stephanov was implementing the STL, he needed a strict weak ordering among all pointers to implement things like std::map.
Instead of wasting time arguing within the committee on wether operator< should have the required semantics, he simply added std::less as a primitive and default comparison for std::map. It is specified to call operator< for every T, except that for pointer it relies on unspecified compiler support for doing the right thing.
On pretty much all implementations it simply calls operator< even for pointers.
I could be misremembering though, but I do know I'd always cast to uintptr_t for this.
Fragments of this mess survive in the Windows API, like Shelley's "vast and trunkless legs of stone": https://blogs.msdn.microsoft.com/oldnewthing/20031125-00/?p=...
http://www.keil.com/support/man/docs/c51/c51_le_ptrs.htm
http://www.keil.com/support/man/docs/c51/c51_le_ptrconversio...
Just like x86, it's likely that everyone interacts daily with a system containing at least 1 8051 core.
The biggest problem with those is, that modern compilers don't support it. Well, that is open-source compilers. IAR will happily sell you a license of their IDE for 2.4k$/seat. There is sdcc, but it's no comparison to a modern gcc or the commercial offerings.
Unfortunately you're right though, 8051 processors are cheap and abundant. Chip makers use it as the go to architecture for any simple embedded processing requirements. It's slowly changing though, but ARM licensing costs are still much higher. Let's hope that in a decade or so they'll use RISC-V instead.
Edit: I am mistaken, it seems that though MIPS is used in all sorts of things that I'd expect wanted the cheapest possible CPU core it has only become free for academic use. I wonder how common that mis-conception is for those not active in the space?
Home routers usually have MIPS CPUs and run Linux on top of it. This wouldn't be possible with the 8051.
"This is usually 0x0000:0x7c00 (CS = 0, offset address 0x7c00). However, some BIOSes load to 0x7c0:0x0000 (CS = 0x07c0, offset address 0) -- which resolves to the same physical address, but can cause problems."
Don't rely on the BIOS' values. You can for example use a far jump to reset CS:IP if you rely on them having specific values.
[Edit: Or, maybe better, just don't rely on them.]
Looking at the standard (no difference between C99/C11), chapter 6.5.6 ("additive operators"), point 9 defines the behavior of pointer subtraction:
When two pointers are subtracted, both shall point to elements of the same array object,
or one past the last element of the array object; the result is the difference of the
subscripts of the two array elements.
The size of the result is implementation-defined,
and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> header.
If the result is not representable in an object of that type, the behavior is undefined.
Still, using pointer difference makes this a lot safer and more portable. Especially on platforms with unusual memory models, where a pointer might not be just a single integer (e.g. segmented memory on x86). Also the operation is Theta(1), so it doesn't impact performance much.
And there are also the platform ABIs, which specify how a pointer is passed between functions. If you're in a platform in which the ABI doesn't allow arbitrarily setting unused bits, even a "security-conscious implementation" will have to leave them alone, since a pointer can be passed to a function written in a different language. This also means that the "map the same object at multiple virtual addresses" trick, in which the implementation flips bits within the pointer knowing there is always a valid alias mapping to it, is broken: suppose two pointers to within the same object are passed (perhaps at separate times) to code written in another language. From the point of view of the other language, they might not be pointing to the same object, even if they should (for instance an array and an element within it, the function might want to compute the offset).
I also wonder how well does the "map the same object at multiple virtual addresses" trick work in architectures with VIVT caches, where both the index and the tag are virtual addresses. In these architectures, if you write through one mapping and want to access the same memory through another mapping, you have to flush the cache, otherwise you will have hard-to-debug problems if both mappings are in the cache at the same time.
Not well at all, unless the OS goes out of the way to do cache coloring. There is a reason that VIVT are today considered suboptimal.
void foo(void *a, void *b) {
char ca[sizeof(void*)];
char cb[sizeof(void*)];
memmove(ca, &a, sizeof(void*));
memmove(cb, &b, sizeof(void*));
assert((a == b) == (memcmp(ca, cb, sizeof(void*)) == 0));
}And this isn't just a historical curiosity. ARM64 can optionally ignore the top eight bits of its 64-bit pointers, for example.
#define ptrToInt(x) ( ((char )x) - ( (char )0 ) );
... and even that may require local tweaking.
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. :(
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.
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.
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.
array_start <= ptr && ptr < array_end // or `<=` if the upper bound is inclusive
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.
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.
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.
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 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 ;)
Which 40 years of experience prove that it doesn't happen as much as it should.
What do you suggest instead? Run-time checks?
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.
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.
Undefined behavior though?
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*.
So, casting one of these pointers to int the most natural way (leaving the bits alone) would not give you an easily subtractable representation.
I don't recall whether a cast to int was raw or converted to linear.
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.
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.
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.
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?
More likely, the intent was to also accomodate implementations that trapped on overflow.
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.
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.
I'm not seeing the big deal here.
I don't think that actually defines anything - I don't think GCC would interpret that as anything other than undefined behaviour.