Pointers Are More Abstract Than You Might Expect in C

https://stefansf.de/post/pointers-are-more-abstract-than-you-might-expect/

by ognyankulev • 8 years ago

269 257 8 years ago

gilgoomesh2• 8 years ago

This scratches the surface of why I hope C slowly fades away as the default low-level language. C sounds simple when you look through K&R C. C lets you feel like you understand the stack, ALU and memory. A pointer is just an integer and I can manipulate it like an integer.

But the reality is filled with a staggering number of weird special cases that exist because memory doesn't work like a simple flat address space; or the compiler needs to optimise field layouts, loops, functions, allocations, register assignments and local variables; or your CPU doesn't use the lower 4 bits or upper 24 bits when addressing.

C has no way to shield common language constructs from these problems. So everything in the language is a little bit compromised. Program in C for long enough and you'll hit a lot of special special cases – usually in the worst way: runtime misbehavior. Type punning corruption, pointers with equal bit representations that are not equal, values that change mysteriously between lines of code, field offsets that are different at debug and release time.

When using fundamental language constructs, we shouldn't need to worry about these ugly special cases – but C is built around these ideas. The need to specify memory layouts, direct memory access and other low level access should be gated by barriers that ensure the language's representation and the machine representation don't tread on each other's toes.

Rust has a long way to go but is so much more robust at runtime. I think there's room for other languages to occupy a similar space but they're need to focus on no-std-lib no-runtime operation (not always the sexiest target).

mpweiher9• 8 years ago

the compiler needs to optimise ...

wants to. There fixed that for you ;-)

The weird special cases were largely(1) introduced recently by optimizer writers hijacking the standard in order to soften the semantics so that previously illegal optimizations would now be legal, by simply declaring the vast majority of existing C code as "undefined" and up for grabs.

Which is why the Linux kernel, among others, has to set special flags in order to get back to a somewhat sane variant.

(1) Except for those special architectures where the hardware is that weird, but in that case you typically know about it.

zodiac• 8 years ago

What does "softening" the semantics mean? Aren't they pretty unambiguously defined by the standard?

jcranmer3• 8 years ago

What changes are you thinking of? The only change with respect to undefined behavior I can think of off the top of my head is punning via unions, which C99 changed from undefined behavior to well-defined behavior.

xenadu022• 8 years ago

The weird special cases were largely(1) introduced recently by optimizer writers hijacking the standard in order to soften the semantics so that previously illegal optimizations would now be legal, by simply declaring the vast majority of existing C code as "undefined" and up for grabs.

Citation needed.

Signed overflow being undefined behavior was a direct consequence of different hardware representations of numbers. Inserting the instructions required to catch overflow and make it wrapping would be expensive, at least on some systems.

The fact that arrays decay to pointers, C has no dynamic array support, and so on are decisions that go way back and more or less prohibit array bounds checking. After preprocessing, inlining, and various forms of optimization it can be very far from obvious that some random NULL check after the pointer has already been dereferenced is intentional and shouldn't be removed.

Things like overlapping pointers have always had undefined behavior in the sense that inserting the instructions to check for the overlap all over the place would have a large performance impact, no one would use such a compiler, and thus there is no market for one. The standards committee largely documented existing practices rather than inventing new undefined behaviors.

I keep seeing people like you claim we should just "fix" undefined behavior or the standards committee gleefully inserted undefined behaviors because they hate programmers. If you actually sat down and disassembled the C code you write then went through the exercise of inserting instructions to eliminate most types of undefined behavior I suspect it would be a very illuminating experience. I also doubt you'd be so certain of your position.

ChrisSD3• 8 years ago

But as you know, CPU ISAs are designed for C programs and compilers are optimized for C programs. So everything, even new languages like Rust, have to buy into C's model to some extent.

Truly getting out from under C's shadow is going to be very difficult. Maybe better languages are a first step on that path but they are only a small step.

pjmlp17• 8 years ago

Modern CPUs, but it used to be that they were designed for any high level language before C took over the show.

jstimpfle6• 8 years ago

That is said a lot, but what are actual desicions that are made to conform to the C model?

What would be good ideas in CPU design that aren't made since they are not compatible with C?

(I get it that CPUs have to support some common paradigms and use cases. For example, virtual memory / process isolation, maybe branch prediction things, or support for calling conventions. However, I don't think that is specific to C).

_0w8t2• 8 years ago

To get the max performance on modern CPU the code has to be cache-aware. It is painful to program for that in C. One often ends up with very complex macros or writing code generators that writes CPU-specific C code. So modern ISA are not designed for C.

By such arguments one can claim that CPU are designed for Fortran as it's compilers allows to write fast code with less efforts than in C/C++.

nostalgeek• 8 years ago

The following is purely my opinion.

Rust might have gone too far the other way. Yes it strives to be a modern language, with a lot of functional programming features and "OOP" done right (aka no inheritance, simply method polymorphism). To me Rust is more a C++ replacement than a C replacement.

A replacement for C should try to be as simple as possible while fixing C weak typing mess with strong typing for instance, including when it comes to pointers (for instance like in Ada where you can't just take the address of anything you want, you need to declare it as aliased to begin with). In fact Ada tries hard to make pointers redundant which is a great thing. This and range types and bound check arrays( Ada has a lot lot of great ideas, and "C style" Ada is a treat to use).

So a C replacement should keep the procedural nature of C, with closures perhaps, but not go further in terms of paradigm. C aficionados often claim they love C because it's "simple"(it isn't) That's what they mean, they love C because you can't really do OO with it.

On the other hand, Rust macros are exemplary of what a good macro system should be.

pjmlp17• 8 years ago

I think it will only happen the way of Luddites in systems programming.

Even if redo Modula-2 with curly brackets I am not sure it would pick up.

gilgoomesh2• 8 years ago

You don't need to use any polymorphism (generics or traits) in Rust. You can use it as a pure structs and functions language like C (especially if you're not using the standard library).

The argument in favour of at least some polymorphism is that it helps to minimise highly repetitive code that would be avoided in C through aliasing, type punning or other pointer conversion.

beojan2• 8 years ago

To me Rust is more a C++ replacement than a C replacement

Precisely. Rust is what C++ would be if it didn't need to be backwards compatible (though I'm not a fan of some of the syntax choices in Rust). Unfortunately, there's a reason C++ needs to retain backwards compatibility and its for that reason that Rust isn't going to replace C++ anytime soon.

That's what they mean, they love C because you can't really do OO with it.

Until they invent GObject or one of the other OO on C libraries. The anti-C++ sentiment is more because compiler support was really quite dire until fairly recently (C++ 11).

TheArcane2• 8 years ago

OOP" done right (aka no inheritance, simply method polymorphism).

Why do you consider inheritance a bad feature of OOP?

icedchai• 8 years ago

I've been programming C on and off for 30 years. Rust feels too complex to be a C replacement. C++, yes...

C's paradigm is really about working with memory. Anything that restricts memory access with bound or type checking is going to feel like "not C"...

bluejekyll6• 8 years ago

To me Rust is more a C++ replacement than a C replacement.

People make this comparison a lot, but it’s not fair. Rust is far simpler, in terms of number of features of the language, to that of C++. It’s fair to say that Rust is far more expressive than C, but this just represents an initial learning curve that is higher than C, but not as high as C++. The type system is fairly simple in Rust, but it can be used to create very complex things. It does take time to be able to read it, but the guarantees you get from it are very powerful.

a C replacement should keep the procedural nature of C, with closures perhaps, but not go further in terms of paradigm

Why leave all of the language development of the last ~50 years on the table? Iterators in Rust are amazing, algebraic data types (enums) allow for simple state machine constructs, lifetimes guarantee memory safety, default immutable memory and single mutable owner mean no more concurrent memory modifications. It’s safer than Java, and as fast and memory constrained as C, what’s not to love?

These are amazing features, that allow for amazingly stable programs. To put it succinctly, you get to code once, and then rely on that code for a long time, to focus on building features, not bugs.

skocznymroczny• 8 years ago

While I am not a fan of it, D's BetterC mode kind of fits what you are looking for.

https://dlang.org/spec/betterc.html

It's kind of a subset of D language, without dependency on GC or runtime. It feels like cleaned up C. Of course without runtime, most of the standard library doesn't work, so you are on your own for the most part, but then, C doesn't really have that much of a standard library to begin with.

Koshkin3• 8 years ago

I have always kind of wondered why Ada did not catch on as a systems programming language (I think it was designed to fill that niche as well).

reza_n2• 8 years ago

C aficionados often claim they love C because it's "simple"(it isn't) That's what they mean, they love C because you can't really do OO with it

I do not think C programmers are anti OO. Infact, a lot of C patterns are modeled on OO (struct + function). I think the appeal of C is that you are able to write the fastest implementation any given algorithm, something that just isn't possible in most other languages.

isaachier3• 8 years ago

Zig again.

marcosdumay2• 8 years ago

"OOP" done right

I wouldn't call the Rust semantics "OOP". But it has a pretty complete implementation of type classes, with class inheritance.

red75prime• 8 years ago

A replacement for C should try to be as simple as possible while fixing C [...]

I have a feeling that such a language will offer too little to offset the costs of switching

pjmlp17• 8 years ago

On top of that C just got here thanks to widespread of UNIX and POSIX, and we had so much better options.

Yes they were languages with helmet, seat belts and airbag bolted on, but just like old technology cars on a motorway crash, the CVE database shows what happens when things go wrong.

tomp• 8 years ago

memory doesn't work like a simple flat address space

Can you expand on that? I thought that modern (non-segmented) memory does work like a simple flat address space, at least from the perspective of userspace programs. Isn't all the weirdness only a result of compiler optimisations?

thechao• 8 years ago

Just to take one example: multisocket x86 is NUMA. There’s HW to paper over that fact, but the power/perf cost is quite high.

bradleyjg• 8 years ago

These architectural bizarrities exist and have to be dealt with by someone. Of course it is better if that someone isn’t you—if some rust maintainer ports the language to the obscure hardware where the CPU ignores the lower four bits when addressing and presents nice, neat, and performance abstractions for you to use.

But who is going to pay for that effort? If the hardware manufacturer cared enough to to invest a lot in developer tooling it probably wouldn’t have picked such a hostile interface to begin with.

sureaboutthis• 8 years ago

Some of your complaints could be said about assembly,too, but are you wanting to get rid of that, too? Some of your other complaints are about how processors and other hardware work, not C. In many ways, you are asking for C to be like other languages but then it wouldn't be C and all the advantages it does have.

If you get rid of C, you get rid of most of the software your operating system runs on and that begs the question you need to ask yourself: if C is so bad, why is everyone using it?

bluejekyll6• 8 years ago

if C is so bad, why is everyone using it?

Don't confuse success for correctness, survivorship bias is something to consider here. As others will surely point out, when C was written, there were other languages available at the time that were as fast, but much safer.

In many ways C won, because Unix won, to talk about them separately ignores how important both were to each others success. (Yes, other operating systems adopted C as well, but Unix is it's foundation)

pjmlp17• 8 years ago

Some mainframes like Unisys ClearPath don't have Assembly support at all, zero, nada, all necessary low level primitives are exposed as compiler intrisics.

jcranmer3• 8 years ago

C sort of has this mindset built around it that you're writing portable assembly, except for messy bits like stack frame layout or register allocation. But that doesn't really hold true anymore, and arguably hasn't for decades.

The first obvious issue is that C is specified by an abstract machine that doesn't really correspond to actual hardware. There's no concept of segmented memory, or multiple address spaces in C. Traps don't quite work the way you'd want in C [1]; there's no way to catch a trap that occurs in a specific region of code. Worse, the abstract machine leans on a definition of undefined behavior in such a way that it's painful for programmers but not useful enough to make automatic security permissible. (Unsigned overflow, which is going to be a more common cause of overflows that lead to security vulnerabilities, is well-defined).

However, the more real problem with C is that it is outright missing hardware features that you'd like access to. Things like rotate instructions or wide multiply are easy enough to pattern match, so their lack isn't so devastating. But flag bits--particularly add with carry or checked overflow operations--aren't figured into at all. SIMD vectors have no conception. Returning multiple values via registers. Traps [1]. Coroutines. Multiple address spaces (especially important for GPUs).

[1] Admittedly, the OS is also to blame here: POSIX signals are a really atrocious way to handle machine-generated faults.

nwmcsween• 8 years ago

flag bits

That's sort of a processor specific implementation detail, IIRC you can access them via GNU extensions.

SIMD vectors

Not having SIMD IMO is a feature as doing useful things will expose processor specific details, you can use SWAR to do some of SIMD.

trentnelson• 8 years ago

Traps don't quite work the way you'd want in C [1]; there's no way to catch a trap that occurs in a specific region of code.

Ah, unless you're in NT land, which makes lexical scoping of traps very easy: https://github.com/tpn/tracer/blob/0224d94b8d17fe74c39cec285...

        //
        // Verify the guard page is working properly by wrapping an attempt to
        // write to it in a structured exception handler that will catch the
        // access violation trap.
        //
        // N.B. We only do this if we're not actively being debugged, as the
        //      traps get dispatched to the debugger engine first as part of
        //      the "first-pass" handling logic of the kernel.
        //

        if (!IsDebuggerPresent()) {

            CaughtException = FALSE;

            TRY_PROBE_MEMORY{

                *Unusable = 1;

            } CATCH_EXCEPTION_ACCESS_VIOLATION{

                CaughtException = TRUE;

            }

            ASSERT(CaughtException);
        }

The helper #defines: https://github.com/tpn/tracer/blob/0224d94b8d17fe74c39cec285..., e.g.

    #define TRY_TSX __try
    #define TRY_AVX __try
    #define TRY_AVX512 __try
    #define TRY_AVX_ALIGNED __try
    #define TRY_AVX_UNALIGNED __try
    
    #define TRY_SSE42 __try
    #define TRY_SSE42_ALIGNED __try
    #define TRY_SSE42_UNALIGNED __try
    
    #define TRY_PROBE_MEMORY __try
    #define TRY_MAPPED_MEMORY_OP __try
    
    #define CATCH_EXCEPTION_ILLEGAL_INSTRUCTION __except(     \
        GetExceptionCode() == EXCEPTION_ILLEGAL_INSTRUCTION ? \
            EXCEPTION_EXECUTE_HANDLER :                       \
            EXCEPTION_CONTINUE_SEARCH                         \
        )
    
    #define CATCH_EXCEPTION_ACCESS_VIOLATION __except(     \
        GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ? \
            EXCEPTION_EXECUTE_HANDLER :                    \
            EXCEPTION_CONTINUE_SEARCH                      \
        )
    
    #define CATCH_STATUS_IN_PAGE_ERROR __except(     \
        GetExceptionCode() == STATUS_IN_PAGE_ERROR ? \
            EXCEPTION_EXECUTE_HANDLER :              \
            EXCEPTION_CONTINUE_SEARCH                \
        )
    
    #define CATCH_STATUS_IN_PAGE_ERROR_OR_ACCESS_VIOLATION __except( \
        GetExceptionCode() == STATUS_IN_PAGE_ERROR ||                \
        GetExceptionCode() == EXCEPTION_ACCESS_VIOLATION ?           \
            EXCEPTION_EXECUTE_HANDLER :                              \
            EXCEPTION_CONTINUE_SEARCH                                \
        )

Also allows you to do fun things like this for testing if you can do an AVX512 op (although this is not the supported way of doing things):

    #pragma optimize("", off)
    static
    NOINLINE
    VOID
    CanWeUseAvx512(PBOOLEAN UseAvx512Pointer)
    {
        BOOLEAN UseAvx512 = TRUE;
        TRY_AVX512 {
            ZMMWORD Test1 = _mm512_set1_epi64(1);
            ZMMWORD Test2 = _mm512_add_epi64(Test1, Test1);
            UNREFERENCED_PARAMETER(Test2);
        } CATCH_EXCEPTION_ILLEGAL_INSTRUCTION{
            UseAvx512 = FALSE;
        }
        *UseAvx512Pointer = UseAvx512;
    }
    #pragma optimize("", on)

https://github.com/tpn/tracer/blob/0224d94b8d17fe74c39cec285...

The structured exception handling protocol used by NT is really quite elegant.

MaxBarraclough5• 8 years ago

I think there's room for other languages to occupy a similar space but they're need to focus on no-std-lib no-runtime operation (not always the sexiest target).

You're describing the Zig language!

It aims to be as fast as C, and unlike most languages that say this is a goal, it means it. There's no "almost as fast as C if you ignore the garbage-collector and the array-bounds-checking", it's actually as fast as C.

Its author values the minimalism of C, but wants to create a far better language for doing that sort of work. [0]

They're doing surprisingly well. They even managed to make a faster-than-C (faster even than hand-tuned assembly) SHA-2 [1]

[0] https://andrewkelley.me/post/intro-to-zig.html , https://github.com/ziglang/zig/wiki/Why-Zig-When-There-is-Al...

[1] https://ziglang.org/download/0.2.0/release-notes.html , it's also mentioned somewhere in this talk https://youtu.be/Z4oYSByyRak

kbenson4• 8 years ago

faster even than hand-tuned assembly

I think you and I are working off different definitions of what that means, as my definition doesn't really allow for a faster implementation (unless there's some really spooky stuff going on in the compiler). I suspect you mean faster than a popular hand tuned implementation.

AnIdiotOnTheNet• 8 years ago

It should be noted that 0.2.0 is significantly different than master in regards to pointer syntax due to pointer reform [0]. There are a lot of other changes too, but that one's the most noticeable.

[0] https://github.com/ziglang/zig/issues/770

mcguire4• 8 years ago

Does Zig have a memory management story other than C's? Anything like Rust's borrow checker?

CyberDildonics4• 8 years ago

I feel like C++11 and Rust have shown a way forward and the C standard should focus on a design that takes into account ownership and protected arrays in a simple way, hopefully as backwards compatible as possible.

Maybe the solution is for the major compilers to default to strong static analysis.

Even though there are safe languages, the enormous integration and compatibility of C means that it isn't going anywhere soon, so I think even imperfect solutions can offer a lot if they are low hanging fruit.

pjmlp17• 8 years ago

It is a matter of mindset, multiple safe C variants have been attempted throughout the years.

Even lint was already available in 1979, yet hardly anyone used static analysis tools on C codebases.

bitwize5• 8 years ago

A pointer is just an integer and I can manipulate it like an integer.

Except it's not. Not unless you cast it to uintptr_t. Doy. :) Understanding the underlying asm can give you context for what a pointer is, but you can't assume that a pointer is an integer, any more than you can assume 'int' is a machine word in length.

There are reasons why C seems so abstruse and abstract. It has to exist on a huge variety of architectures and environments, from supercomputers to tiny embedded microcontrollers. Fun fact: The Lisp Machine had a C compiler! In Lisp Machine C, pointers were fat: they consisted of a machine pointer to an allocated chunk of memory and an offset within that chunk. And of course it was invalid to have a pointer outside an allocated object; the machine would throw an exception if you even tried. Hence why C pointers are only well-defined over valid references to objects and arrays, one past the end of an array, and NULL. And lest you say, "well no modern cpu works like that anymore", there are programs out there written for the Burroughs architecture that are still running. Are you going to cut off the maintainers of those programs because the architecture they're coding for doesn't resemble an x86?

This is part of why I disdain the call for modernity in programming. "Modern" means "limited". "Modern" means "I have no intention of testing this on anything but my laptop, so I will make assumptions that suit my use case and fuck you if yours differs".

C is a pain in the ass, but it becomes more approachable if you take into account its history. And it still fits in your head more easily than Rust.

hexane3602• 8 years ago

The obvious flipside of this is that those C programs written for Burroughs never had any chance of running on anything but Burroughs. The only difference is that C offloads the effort of portability onto the user, whereas other languages at least attempt to make it portable in the compiler.

tropo2• 8 years ago

Burroughs does not have a modern C compiler. As far as modern C standards go, the Burroughs architecture does not exist.

The same is true for the rest of the oddball stuff. It's dead now. Nobody is even trying. There is no longer any reason to make the C standard nasty in order to support these systems. The plug should have been pulled on them long ago, when they were well under 1% of the market and declining, but now they are nothing. No standards-conforming compiler supports that old stuff.

Even back at 1%, hurting everybody to support that stuff was not worthwhile. It was a terrible trade-off to make.

Koshkin3• 8 years ago

Road to Rust is paved with good intentions. (Same is true about C++.)

andrewmcwatters• 8 years ago

Is there a site or book out there that talks about these common pitfalls? I work in C89 so K&R C does seem pretty simple to me. I clearly haven't worked with it long enough to spot these things, or I have code in the wild that unknowingly is victim to these issues and I've yet to stumble on it.

oppositelock• 8 years ago

I've been writing C on and off since 1990, across embedded systems, game consoles, massive SGI supercomputers, and modern kernels.

C is not fading away because of it's portability and low overhead. It has some nasty behaviors, as the original post shows, but you hit those once in a blue moon. The language is not unsound because of it, it just has some warts like any other language.

I don't particularly enjoy writing C, as it's too low level for my liking and I have to write too much code to do basic things (slist_* makes me shudder), but the reason that I have used it is due to its tremendous portability and direct compilation to machine code. That still matters in some places.

In places where memory is precious, or realtime performance precludes things like memory managers, C will continue to thrive, beside languages like Rust which are great for different goals. There's room for both.

C, in my opinion, has stood the test of time on its simplicity, portability, and the ubiquity of the C standard library, tiny as it may be.

joosteto• 8 years ago

When I compile the example, i get:

  0x7ffd0b57ebd0 0x7ffd0b57ebd8 0

OK, so gcc reordered a & b; I'll fix this by chaning the initialisation of p and q to:

  int *p = &a + 1;
  int *q = &b;

But when I now run the example, I get:

  gcc -o c c.c && ./c
  0x7ffe55eb0aa4 0x7ffe55eb0aa4 1

  gcc -O -o c c.c && ./c
  0x7ffcfeffd914 0x7ffcfeffd914 0

So, p==q only evaluates to 1 if optimisation is enabled.

  $ gcc --version
  gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0

psyklic• 8 years ago

It shows the exact options the author used if you click on GCC:

Version: 8.1.1 Options: -std=c11 -O1 Target: x86_64-redhat-linux

mpweiher9• 8 years ago

clang is a bit more sane:

   > cc pointereq.c 
   > ./a.out 
   0x7ffee83163b8 0x7ffee83163b8 1
   > cc -O pointereq.c 
   > ./a.out 
   0x7ffeeeb8b3b8 0x7ffeeeb8b3c0 0

So without optimization, the pointers are the same and compare as equal. With optimization, the pointers compare as not equal. At first that seemed horrible, until I saw the pointers actually are not the same. Since I don't recall any guarantees about stack layout, that seems perfectly fine.

   > cat pointereq.c 
   
   #include <stdio.h>
   
   int main(void) {
     int a, b;
     int *p = &a;
     int *q = &b + 1;
     printf("%p %p %d\n", (void *)p, (void *)q, p == q);
     return 0;
   }

andyjohnson03• 8 years ago

Just a datapoint: VS2017 on Win10 x64 gives me 00AFF89C 00AFF894 0, which is what I naively expect.

JdeBP9• 8 years ago

Actually, you should not expect that, because you don't have a guarantee of ordering of the addresses of a and b on the stack.

Now try with /O2 . (-:

andyjohnson03• 8 years ago

Maybe I'm misunderstanding you, but it's precisely because I have no knowledge of the stack frame's layout that I didn't expect the pointers to be equal.

With /O2 optimisation I get:

00B1F99C 00B1F9A4 0

nuriaion2• 8 years ago

Basically you have no guarantee where the pointer q is pointing to. Some compiler/static code analyzer will yell at you with this code.

jerrre• 8 years ago

isn't it guaranteed that is points sizeof(int) bytes higher than the address of b?

Whether something useful is behind that address is another question

ChrisSD3• 8 years ago

From reading the spec it seems that is undefined behaviour for anything other than `&b + 1`. That is one past the end of b is fine but not `&b + 2` etc.

JdeBP9• 8 years ago

There's a guarantee relative to the address of b. But there's no guarantee about the relative addresses of a and b themselves, i.e. where they are placed in automatic storage. So even setting aside the idea of optimizing the test away at compile time, there's no guarantee that the comparison result will be a specific value. a could be above or below b, and they are not necessarily adjacent objects.

golergka4• 8 years ago

I don't think that address of anything even has to be a positive number, according to the C standard.

nuriaion2• 8 years ago

Depending on your architecture and compiler it could be that everything is 128 bit aligned, so you would had "empty holes" in your memory layout. (For example some dsp's)

foxhill2• 8 years ago

the comparison at the start is nonsense - there is no specification for the ordering or location of stack variables. by taking the address of these variables, you could see that they actually are the same value, and so intuitively you’d think they might be the same, but a different compiler might put them in different locations. or they may be elided entirely through optimisation. it’s far safer to fail the equality test in this case - this is what the model specifies.

this is not even the first example of this counter-initiative behaviour. imagine two floating point values with exactly the same bit-representation. it is possible, without any trickery for them to fail an equality check - i.e, they are both NaN.

this is what IEE754 demands of a compliant floating point implementation. and indeed, it’s a sane choice when you understand why it was made.

similarly, it’s perfectly reasonable for this example to fail.

jameshart• 8 years ago

Surely the point of writing an if-block testing the equality of the pointers is precisely because the code isn’t assuming that they are the same - but maybe it has something it wants to do if it finds itself running somewhere where they are.

Writing code which assumed those pointers were equivalent would be bad, but this code doesn’t do that. Instead, it looks like the compiler assumes that the pointers won’t be the same and refuses to let you entertain the possibility at all.

maxxxxx• 8 years ago

What's the point of even trying to compare these two pointers?

cozzyd• 8 years ago

I haven't tested it but I imagine casting to uint64_t will make it work as you want.

foxhill2• 8 years ago

Instead, it looks like the compiler assumes that the pointers won’t be the same and refuses to let you entertain the possibility at all.

and indeed it should - it’s sane to use the address of a stack variable for the purposes of writing something into it, but assuming that it forms some sort of array in memory is sure to cause pain if you rely on that assumption.

mehh• 8 years ago

I agree, when I can see the addresses match it would do my head in if the compiler says false, its unexpected, its surprising. If i write bad code, fine I'm used to that and I can debug it, if there are these new 'gotchas' thats less transparent. I've not used c11 yet, and don't likes the sound of it!

bluecalm2• 8 years ago

I like the behavior of the compiler here. There is no guarantee that a and b are next to each other in memory. That's why the comparison fails, the alternative makes is runtime/compiler/optimization level dependent which would be a total mess.

As usual with those C bashing articles you won't run into trouble if you don't try very hard to write contrived code. I mean, the moment you see:

     int *q = &b + 1;

on your screen alarm bells should go off. Doing pointer arithmetic on something that is not an array is asking for trouble. If the standard should be amended in any way it should be undefined behavior right away you do pointer arithmetic on non-array objects.

jstimpfle6• 8 years ago

That would require making a distinction between array-pointers and non-array pointers. There, another can of worms. Probably not worth the additional complexity.

mpweiher9• 8 years ago

Agree on the alarm bells with the pointer arithmetic.

Disagree that gcc is doing the right thing here. The clang behavior (different comment in this thread) is much more sane: if the pointers happen to be the same, they compare as equal. If the pointers happen to not be the same, they compare as not equal.

shakna2• 8 years ago

Except clang's behaviour changes depending on the optimisation level. If you use -O1, then you get a different result.

Koshkin3• 8 years ago

C is useful in part because it allows for the freedom unimaginable in other languages.

pjmlp17• 8 years ago

That freedom does exist in Ada, Modula-2 among others, the big difference being that one needs to be explicit about what is going on.

tzs3• 8 years ago

I like the behavior of the compiler here. There is no guarantee that a and b are next to each other in memory. That's why the comparison fails, the alternative makes is runtime/compiler/optimization level dependent which would be a total mess

Yes, there is no guarantee that they are next to each other, but in this case they happen to be next to each other, and according to the spec as quoted in the article, two pointers are equal if:

[...] 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

Note that it says "happens to" immediately follow, not "is guaranteed to" immediately follow.

This are pointers to ints, not arrays of ints, but that should not matter because as quoted in the article:

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.

I don't see any way to read these as not requiring the pointers to compare as equal if the compiler happens to put a and b adjacent in memory in the right order and with no padding between them, other than resorting to something ridiculous like claiming that "follow" or "immediately" follow are not defined in the spec and so one object occupying that very next available address after another does not necessarily "immediately follow". This seems to be what the gcc developers went with to declare this is not a bug.

Also, note that if you move the "int a, b" to outside main, so a and b are on the heap instead of on the stack, then gcc does find that the pointers are equal.

clarry2• 8 years ago

> 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.
I don't see any way to read these as not requiring the pointers to compare as equal if the compiler happens to put a and b adjacent in memory in the right order and with no padding between them, other than resorting to something ridiculous like claiming that "follow" or "immediately" follow are not defined in the spec and so one object occupying that very next available address after another does not necessarily "immediately follow". This seems to be what the gcc developers went with to declare this is not a bug.

"These operators" in the spec refer to the (additive) pointer arithmetic operators, not the equality operator. So incrementing a pointer to int behaves as if the pointee were in an array of length one, but that does not mean any subsequent equality operator should consider the objects as arrays.

It's totally fine for the equality comparison to return false when the objects in question are actually not arrays.

slrz2• 8 years ago

Note that it says "happens to" immediately follow, not "is guaranteed to" immediately follow.

I read that more as "happens to be placed" by the programmer (as a conscious decision), not including mere happenstance. In other words, this refers to arrays and struct fields.

kabdib• 8 years ago

Also, note that if you move the "int a, b" to outside main, so a and b are on the heap instead of on the stack, then gcc does find that the pointers are equal.

This is also an utter accident, since it depends a great deal on the toolchain. I've worked on compilers and linkers that will put the variables in totally separate parts of the binary (e.g., based on name hash).

tzahola3• 8 years ago

There's nothing surprising in the first example. Comparing the addresses of stack variables is undefined behaviour.

The second one is more interesting:

    extern int _start[];
    extern int _end[];
    
    void foo(void) {
        for (int *i = _start; i != _end; ++i) { /* ... */ }
    }

GCC optimized "i != _end" into "true". The kernel guys fixed this by turning "_start" and "_end" into "extern int*". I always thought [] was just syntactic sugar over a regular pointer, but seems like I was wrong.

JdeBP9• 8 years ago

Actually, the headline article tells us that it optimized it to true.

That affected some of my code from years ago, too; and another fix is to keep _start and instead of having another array called _end have an external size_t giving the number of elements of start and loop while i!=_start+count .

In fairness to the compiler people there shouldn't really be anything surprising in the second example, either. There are x86 memory models (compact and large) where that loop never terminates in the general case, because the two arrays are not in the same data segment and no amount of incrementing a (far but not huge) pointer will get from one to the other. So it's not the case that this is a new pitfall. It was a pitfall decades ago.

People just thought that it didn't exist with modern tiny (a.k.a. flat) memory models, because the old explanation wasn't applicable. It does, but with a different explanation.

tzahola3• 8 years ago

Yup, I've mistyped "true" as "false".

If you set "_start" and "_end" to addresses of different objects, then you're invoking undefined behaviour and all bets are off. But this should be perfectly valid IMO:

    extern char* _start;
    extern char* _end;

    void foo() {
        for (char* c = start; c != end; c++) ...
    }

    int main(int, char**) {
        char buf[128];
        _start = &buf[0];
        _end = &buf[128];
        foo();
    }

Right?

kbp2• 8 years ago

I always thought [] was just syntactic sugar over a regular pointer, but seems like I was wrong.

For another example showing their differences, if a.c has:

    int n[] = { 1 };

And b.c has:

    extern int *n;
    printf("%d\n", *n);

Then running b.c will segfault, whereas if it said extern int n[], it would work as expected (hint: extern int n and printf("%d\n", n) would also work). Arrays degrade to pointers at the drop of a hat, but they're distinct from them.

jcelerier2• 8 years ago

Then running b.c will segfault

why would it not ? On one side you declare an int array of size 1, on the other side you declare a pointer. Think about what's going on with the bytes :

    int n[] = { 1 };

will look exactly the same in memory than

    int n = 1;

which is of course not compatible with

    int* n = 1;

Arrays by themselves have no indirection in C.

=> https://godbolt.org/g/xwT7uW

mwkaufma• 8 years ago

The confusion in the example is the choice of names "start" and "end". If we rename them "some_array" and "some_totally_different_array" the undefined behavior is clear.

jcelerier2• 8 years ago

I always thought [] was just syntactic sugar over a regular pointer, but seems like I was wrong.

It depends on the context. When used in function arguments, yes, it's the same. When used during the declaration of a variable, it's entirely different.

jjnoakes3• 8 years ago

Comparing the addresses of stack variables is undefined behaviour

Can you elaborate? I don't think this is true.

Rusky5• 8 years ago

They're from different objects, so it's not meaningful (according to the standard) to compare them. That's what makes it UB.

tzs3• 8 years ago

Note that if the two pointers are passed to a function, and the comparison is done in the function, the results are different:

  #include <stdio.h>

  void pcmp(int *p, int *q)
  {
      printf("%p %p %d\n", (void *)p, (void *)q, p == q);
  }

  int main(void) {
    int a, b;
    int *p = &a;
    int *q = &b + 1;
    printf("%p %p %d\n", (void *)p, (void *)q, p == q);
    pcmp(p, q);
    return 0;
  }

That is giving me:

  0x7ffebac1483c 0x7ffebac1483c 0
  0x7ffebac1483c 0x7ffebac1483c 1

That's compiled with '-std=c11 -O1' as in the article. The result is the same of pcmp is moved into a separate file so that when compiling it the compiler has no knowledge of the origins of the two pointers.

I don't like this at all. It bugs me that I can get different results comparing two pointers depending on where I happen to do the comparison.

JoeAltmaier• 8 years ago

Yes, I agree. It makes far more sense to make guarantees in a language, that two values are compared using a metric that is invariant. Especially in a language like C, where we expect it to be a very thin abstraction over the machine.

ash_gti• 8 years ago

Did you use gcc or clang or...?

When I ran this locally I get:

    0x7ffeee2a4808 0x7ffeee2a4810 0
    0x7ffeee2a4808 0x7ffeee2a4810 0

With -O0 I get 1/1 instead of 0/0 so this appears to be a compiler optimization.

quelltext• 8 years ago

Yup, what is described in the article looks like a bugged optimization to me were the runtime behavior differs from the static model used for the optimization. I am sure the actual runtime semantics is in fact to compare addresses but the optimization claims to know (falsely) enough about the pointers to determine they must be not equal.

I don't understand the people in this comment section defending this. The cited spec gives no evidence that this should happen (I fail to see the undefined behavior here). It specifies when pointers are equal, and both pointers ended up pointing to the same object, so they should be equal. Just because the compiler doesn't know, shouldn't mean it can replace an equality check with false.

The spec didn't say "also, they are not equal in case the conpiler thinks that they proooobably aren't pointing to the same object".

I do agree that one should avoid this type of pointer arithmetic, but that doesn't excuse the confusing behavior of this primitive operstion.

One should at least argue for the behavior to be consistent.

0x417572656c• 8 years ago

You're right, unless pcmp is declared as static (then the compiler inline the function)

   #include <stdio.h>
   #include <stdint.h>

   static void pcmp(void *p, void *q)
   {
       printf("%p %p %d %d(sub) %d(cast)\n", p, q, p == q, !(p - q),
                                             (uintptr_t)p == (uintptr_t)q);
   }

   int main(void)
   {
       int a, b;
       void *p = &a;
       void *q = &b + 1;

       printf("%p %p %d %d(sub) %d(cast)\n", p, q, p == q, !(p - q),
                                             (uintptr_t)p == (uintptr_t)q);
       pcmp(p, q);
       return 0; 
   }

Results:

   $ gcc -std=gnu11 -O1 pq.c
   $ ./a.out
   0x7fffde6612ec 0x7fffde6612ec 0 1(sub) 1(cast)
   0x7fffde6612ec 0x7fffde6612ec 0 1(sub) 1(cast)

Same result with '-std=gnu11' as with '-std=c11' (GNU C allow void pointer arithmetic for the test !(p - q))

_RPM• 8 years ago

if you're adding 1 to a pointer, why would you expect it to be equal? I would not expect it to be equal.

armitron• 8 years ago

He's adding "1" to the pointer that points to the variable "b" which in this case is allocated immediately below "a" in the stack. Thus adding one will make the two pointers equal.

saagarjha6• 8 years ago

The layout of things on the stack is completely implementation-defined.

crehn• 8 years ago

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.

Can someone explain to me the rationale behind this? Why not just "two pointers compare equal if they point to the same address"?

isaachier3• 8 years ago

My guess is type based alias analysis. The classic example is casting an int to a float like so may crash your program due to undefined behavior:

float my_bad_function(void) { int x = 5; float* y = (float) &x; return y; }

JdeBP9• 8 years ago

Because (a) pointers do not point to addresses, and (b) now you have to define the concept of addresses being equal in the language standard and haven't actually reached the goal. (-:

Sharlin3• 8 years ago

Indeed; pointers intentionally abstract away memory addresses and addressing, which, as the article states, can be much nastier business than the benign flat address space of i386 protected mode.

thatcks• 8 years ago

The C standard was (and is) written so that it allowed for machines that didn't have simple pointers; a highly relevant example for the time was x86 machines in real or protected mode using segment registers. Even when such environments have accessible linear address spaces under the hood, comparing the absolute address of two pointers requires some extra work (you have to reassemble the absolute address from the segment + offset pair). In the grand tradition of allowing the most efficient implementation possible, the C standard says that implementations don't have to do this work; they can simply compare pointer values directly, provided that they insure that pointers to the same object work (eg use the same segment + offset pair, which they normally naturally will).

The standard was also written to allow for C interpreters, where you may not have an underlying linear memory model at all and all pointers are represented internally in some complex way (for example 'object ID + offset inside object'). Here you don't have any particular idea of 'an address' as a distinct thing and so you can't naturally compare two pointers to different objects in any meaningful way.

Sharlin3• 8 years ago

...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.

I was not aware of this special case. What's the rationale? Is there even a way in standard C to guarantee that two array objects are laid out in memory like that, with no padding?

mcguire4• 8 years ago

Start with one large array and subdivide it into two segments.

saagarjha6• 8 years ago

A two-dimensional array?

Sharlin3• 8 years ago

Yeah, good point.

oconnor6632• 8 years ago

If we step back from the standard and ask our self does it make sense to compare two pointers which are derived from two completely unrelated objects? The answer is probably always no.

The one big counterexample I can think of is the difference between memcpy and memmove. The latter is supposed to be able to do arithmetic on memory regions, to see if they overlap. Is this article saying that the standard C implementation of memmove is relying on unspecified behavior?

coldnose• 8 years ago

Another example of arbitrary pointer comparison I'm familiar with is for resolving lock ordering problems. If I have a big set of locks that I need to take to complete a particular operation, a simple way to prevent deadlocking is to acquire those locks in the order of their pointers.

E.g. if I have three locks I need to take,

  lock_t *a = (lock_t *)0x100;
  lock_t *b = (lock_t *)0x300;
  lock_t *c = (lock_t *)0x200;

then I'll take them in order a, c, b;

bluecalm2• 8 years ago

If order of locks is important maybe it's worth considering putting them in an array.

slrz2• 8 years ago

Memmove is frequently cited as an example of a standard library function that can't be implemented using only standard C. It's incorrect, though: the way to do memmove using standard C is to use malloc to allocate a temporary buffer.

But the whole question is not terribly relevant. When memmove is provided as part of the C implementation it can rely on non-portable platform behaviour just fine. There's no rule that you have to implement libc using only standard C facilities.

pjmlp17• 8 years ago

And how do you implement malloc() in standard C?

mabynogy• 8 years ago

Not related to the content but I find the colored links in the nav a simple and very good idea.

bsder2• 8 years ago

Ummm, when I run this on gcc 7.3.0 on OS X I actually get:

0x7fff5dbd89fc 0x7fff5dbd89fc 1

Which kind of shoots the whole article in the foot ...

zubyak3• 8 years ago

Did you compile it using '-std=c11 -O1' ?

bsder2• 8 years ago

No, but that just makes me assume that this is an optimization bug. Especially since -O4 actually coughs up different pointers:

  gcc-7 -std=c11 -O4 -o test test.c
  $ ./test
  0x7fff5b5f5a08 0x7fff5b5f5a10 0

The following code works as expected even with your flags and the pointers are clearly not related to one another:

  #include <stdio.h>
  #include <stdint.h>
  
  int main(void) {
      uint32_t *p = ((uint32_t *)0x7fffffffffff3eac)+1;
      uint32_t *q = (uint32_t *)0x7fffffffffff3eb0;
      printf("%p %p %d\n", (void *)p, (void *)q, p == q);
      return 0;
  }

So, I would either chalk this up to either 1) "compiler optimization bug" unless a gcc maintainer explicitly gave me a reason to believe to the contrary or 2) getting your underwear eaten by weasels because you optimized after invoking undefined behavior (attempting to probe stack layouts qualifies as undefined behavior in a big way).

My assumption would be that the compiler had to do something screwball that it got wrong because you actually asked for a pointer to a stack object that it had optimized to always be in registers.

Pointers Are More Abstract Than You Might Expect in C

Related Stories