Hacker News Reader

Hacker News

Comment by Animats | Hacker News Reader

Full thread

Animats

The three big questions:

1. How big is it?

2. Who owns it?

3. Who locks it?

Most undefined behavior in C/C++ involves those three questions.

#1 is historically the most troublesome. And the most inexcusable. Pascal, which predates C, didn't have that problem, because arrays carried size info. Nor did Algol, Modula I, Modula II, and Modula III. Modula I was a very low level language - device registers were a language concept.

Something I wrote on this back in 2012.[1] There was some consensus at the time that this would work and would be backwards compatible with C. But it would be a tough sell, and I didn't want to spend my life selling it.

[1] http://animats.com/papers/languages/safearraysforc43.pdf

View on HN

-fbounds-safety

https://discourse.llvm.org/t/rfc-enforcing-bounds-safety-in-...

Part of the proposal is to make fat pointers. Has ABI implications, but there are many pressure relief valves.

I read most of that proposal and I really like it! I hope they get it into the next standard.

In a way, it’s kind of a very narrow form of dependent types. It solves this one issue very cleanly.

I think a C implementation with overhead instead of UB is implementable. I'd like to know what the fundamental performance delta we get from UB is. Likewise not sure it's the right choice for my life's work.

The MINIMUM baseline is probably somewhere around ASAN/UBSAN/etc. and those aren't exactly cheap... and they don't even promise to catch all the problems. The problem is that almost every single little thing you can do in C has potential for UB, even just the + operator.

So it would absolutely come at a HUGE performance cost, unfortunately.

More esoteric stuff is: If you do pointer arithmetic that technically goes out of bounds and then in bounds again... that's technically UB (can't remember if this is C++ only or both), so you can't rely on knowing where everything is + bounds checks.

I'd say that those are not actually the minimum. You don't need to detect undefined behavior, you just need to "make it implementation defined", so integers could just wrap around without needing to check for overflow, unitialized memory would just be random bytes, and so on. At least that would be one way to do it. Of course the checks would ensure the program shuts down more cleanly.

The nice thing about integer overflow being UB is that UBsan (or even compiler flags without it) can make it throw, so it's easy to catch. Defining it as wrapping means you still have bugs, they're just harder to catch.

Define it as wrapping, and there will be programs relying on it (that are currently using unsigned).

Aliasing is a real problem. If any pointer of any type can write though to any value of any other type with some defined behavior, many key optimizations—moving a value into a register!—become impossible.

In general I don't know how you make currently-UB aliasing safe. But in that specific case you can just say that the value not showing up through the bad alias is a possible defined behavior.

But whether it shows up or not is a function of the optimization decision, which might have gone the other way for any number of hard-to-define reasons.

Is that a problem, though?

I would have thought the best case scenario for a bad alias is that you safely corrupt some other piece of data. (Assuming you let those writes go through.) So "it might not do that" seems like an improvement to me.

If you don't let those writes go through, then we're in a different happier situation, and the register optimization causes no change in behavior.

I guess I'm not sure which definition you're proposing:

a) Writes through "bad" aliases never take effect.

b) Writes through "bad" aliases take effect sometimes, no guarantees.

I don't think either makes the point you're hoping to.

b) is just bog standard undefined behavior. I guess you could be intending to constrain the range of what effects compiler-emitted code can have in bad-aliasing situations (no nasal daemons!) but it's not clear how much additional optimization latitude constraining only nasal daemons provides. Compilers often save local stack space by reusing stack entries for multiple local variables. A bad alias to one could corrupt an unrelated value, and you've got nasal daemons again.

a) requires massive compile-time and run-time effort to dynamically distinguish "bad" aliases from "good" ones. This is along the lines of what valgrind does at great cost.

I thought the premise was that Someone Else already took care of those nasal demons somehow, and we're just worried about putting the register optimization back into place. So the range of effects has already been constrained to something safe. We're just adding in "sometimes it doesn't have those bad effects" to enable some optimizations, and that should have very little downside.

Options a and b are just the different ways Someone Else could have implemented their solution. I'm not suggesting how they did that, I'm taking it as the premise. The problem of "how do we make bad aliasing safe" is much much much harder than "how do we still enable normal optimizations like this after we make bad aliasing safe".

That's the general consensus.

However, much the same key optimisations are useful when both pointers have the same type. Given multiple float* pointers, you still want to know whether they alias for load/store forwarding and the like.

Once you've written the analysis to partition values of the same type into separate alias sets, that same analysis runs fine on values of different types.

Distinct types implying distinct alias sets does tolerate separate compilation well and is cheap to compute. The belief that it is the only way to achieve said key optimisations is worth some scepticism now that link time optimisation and interprocedural analysis are fairly common.

You can have the most sophisticated analysis imaginable, but then I cast rand() to a pointer and …

> More esoteric stuff is: If you do pointer arithmetic that technically goes out of bounds and then in bounds again... that's technically UB (can't remember if this is C++ only or both), so you can't rely on knowing where everything is + bounds checks.

When the goal is preventing UB, you can simply define things like that as not-UB. At least on the vast majority of architectures where the numbers work fine at runtime, and only the compiler sees it as invalid behavior.

Not really. Address Sanitizer must work with the existing ABI, which means it has a lot of overhead for an imperfect result.

What could be done better if it could break the ABI?

You could pass around fat pointers everywhere. This is more efficient than probabilistically setting up redzones.

True, but that doesn't address (heh) the briefly-goes-out-of-bounds-and-then-in-bounds scenario. Again, I'm not 100% that that's technically UB, but I think so?

(It would have be to be for very esoteric addressing modes, maybe relevant on ancient pre-linear address space architectures?)

That would be a check on each arithmetic operation.

...and Ada, too. I like the idea of attributes of data objects, to access the size of x simple write x'Size (also for types e.g. Natural'Size).

The Wirth languages (from which Ada is also a descendant) were so much more readable than C, yet relatively capable for systems programming, as demonstrated by systems like TeX, MacOS, Wirth's Modula compilers and the OS for the Lilith workstation he co-designed from scratch.

Never used Ada but I think you can define range types so int range 0...11. Which I feel is something that you really want in embedded and applications level programming.

>> Never used Ada but I think you can define range types so int range 0...11.

Yes. Ada supports integral types with custom ranges:

https://learn.adacore.com/courses/intro-to-ada/chapters/stro...

In the medium-long term I want to do this for Rust as "Pattern types" because the thing I actually want (custom types with niches) is gated on Pattern types, as the way to explain to the type system where the niche goes is a Pattern. I was persuaded that we can't/ shouldn't just say we'll half ass it, we must do it properly if we're doing it.

e.g. I don't necessarily have a use for an integer from 0 to 11, but I do see a use for BalancedI8, a one byte type with values -127 to +127 via 0, thus omitting -128. I reckon lots of people don't need -128, whereas a niche is very useful. Rust provides NonZeroI8, which has -128 through +127 but no zero, but I find that's less often what you want, and it's not today possible to make your own in stable Rust (and in nightly Rust you need a not-for-mortals perma-unstable attribute today).

You can make it on stable Rust by using an enum with a missing variant. The compiler will give you a niche automatically.

Of course that doesn't scale to larger types as even with a macro the compile speed will be horrible.

Yeah, "enum with a missing variant" is like, awful but maybe viable for BalancedI8, but it's clearly insane for BalancedI32 let alone BalancedI64 and those seem at least as useful.

Today, in practice, if you want BalancedI32 what you'd do is swizzle NonZeroI32, so that a trivial CPU operation converts between the two types and you can deliver almost the same optimisations in practice. But, I think that's also pretty ugly, and Rust clearly could do the nicer thing here, indeed it does in my crate that only builds on nightly and is using not-for-public-use compiler internal attributes. So that's what I want, just apparently not enough to spend my vacation time last month working on it. Maybe next month.

From a tutorial at https://www.modula2.org/tutor/chapter11.php:

> The ALLOCATE procedure requires 2 arguments, the first of which is a pointer which will be used to point to the desired new block of dynamically allocated menory, and the second which gives the size of the block in bytes. The supplied function TSIZE will return the size of the block of data required by the TYPE supplied to it as an argument. Be sure to use the TYPE of the data and not the TYPE of the pointer to the data for the argument.

So what happens if you pass the wrong value as the second argument to ALLOCATE? Does the compiler throw an error, or are you now risking a buffer overflow?

C has arrays. Arrays carry size. The problems in C are much more nuanced than people seem to suggest, and people exaggerate the extent to which other languages do better in this regard, though to be sure C has significant deficiencies.

Hm, the proposal is rather sensible but... didn't C99 introduce static-dimensions in array-typed function parameters? I'm pretty sure

    void copybyref(size_t n, int a[static n], const int b[static n]) {
        for (int i = 0; i < n; i++) {
            a[i] = b[i];
        }
    }

is valid C and has exactly the same semantics as the example from the proposal — except that in this case, "no diagnostic is required" to ensure that there are indeed (at least) n elements in both a and b arrays.

Checking this in general has ABI considerations. It allows the compiler to do some things at compile-time but beyond that it doesn't really work.

> Checking this in general has ABI considerations

Does it? Inserting a sanity check at every call site of e.g. memcpy (that neither of dst/src are NULL) is already kinda required for correctness even if people skip it and boldly go.

#4 which is partly #2 - what thread is this callback being invoked in? The calling thread? A thread pool in the library?

Mostly a problem I have in java libraries, though.

Reply on news.ycombinator.com