Resolving Rust's forward progress guarantees

Anyone at all can insert their own side effect into their code using Stable Rust:

let x = 0; unsafe { core::ptr::read_volatile(&x) };

So, as an immediate measure that could also be rolled back later once a full fix is applied, we can probably start by warning on loop{} and telling people to add that code into their loop body.

1 Like

If you're going to go through the trouble of detecting loop{} and warning on it (and then expecting the user to insert their own unsafe volatile read), I think it's far better to just have rustc insert sideeffect for loop{}.

I'm personally in favor of the prior suggestion of inserting sideeffect for trivial, easily detectable infinite loops and ignoring nontrivial infinite loops. That strikes a good balance between various trade offs.

17 Likes

Wait, why would LLVM be able to assume that a noreturn function has no side-effect? It could be a function that loops forever while communicating with other threads, meaning it is very effectful.

2 Likes

You are right of course, "function is noreturn => function has no side effects" would be a wrong inference. That is not what I way trying to say, but I was not quite clear. What I meant is that the obvious way to infer "function has no side effects" (classify individual instructions has having side effects or not, then just check if the function contains any instruction that has side effects) leads to considering some functions that do not return to have no side effects -- not because an infinite loop without forward progress was identified but simply because loops did not factor into the analysis at all.

The problem is that LLVM marks functions that don't read/write memory as "readnone" even if they contain potentially infinite loops, and then removes calls to "readnone" functions with unused results (even if they are "noreturn"...).

Obviously this combination of optimizations is broken (without making assumptions about forward progress).

12 Likes

If we look at how forward progress based optimizations can cause problems we have following 3 cases:

  1. Unsoundness: Happens due to a mismatch between the knowledge of rustc and llvm. I.e. it only happens because rustc thinks the normal return of the functions is unreachable while llvm makes it reachable. This should be solvable without to much problems. (E.g. emitting a "side-effect" into known endless loops positioned before a "unreachable section", e.g. a unreachable function return). If we do that it will again become impossible to return from a function which returns a non-constructable type. Also it should not forward progress wrt. recursion doesn't cause additional problems here. (Short: rustc already knows it's a endless loop, so it can make sure it stays one)

  2. Unexpected breakage of safety contract of written unsafe code. Here some unsafe code depends on some code snipped "busy" hanging the current thread for it's safety, but due to the elimination of code this doesn't happen and the unsafe code misbehaves, potentially triggering Compiler or even runtime hardware level UB. The embedded loop {} pattern (for e.g. abort) falls into this category.

  3. Unexpected but (rust)safe behavior due to a situation like in 2. but without it triggering any safety related problems.

Looking at it fixing 1. is from utmost importance (and should be doable without this massive overhead) and fixing 2.,3. is important but the best way to fix isn't as clear to me (I come back to this in a follow up post).

1 Like

Another think we should think about is when does code which does not make forward progress makes sense?

The answer for it is only if you want to busy hang the thread!

So normally it's always reasonable to eliminate code which neither makes forward process nor whichs result is used in code which does make forward progress. That's except if your type system relies on it or you want to hang the thread.

Assuming we handle the first case (we can I belive as we have all info we need to know where it potentially triggers already in rustc) and provide some form of fn thread_busy_hang() function for the second case and also warn on loop {} we probably should be fine for now.

Through we would not be done as programs might still can brake in surprising ways because of it it just would not be unsound.

But this should be hit rarely so rare that it should earn us enough time to find a proper fix.


Side note: I do not think erroring on loop{} (in a new edition) would make sense. There is no good way for rustc to detect all cases of "non returning sections which are potentially eliminated" without doing a lot work LLVM does and keeping it in sync with LLVM while still maintaining constant backward compatibility with code written for different LLVM versions in the same edition.

That's the reasoning behind C++'s forward progress requirement. And they're right; hanging code like this makes no sense in a real application.

But what happens if someone does it by accident? Making it hard to induce UB by accident is, after all, Rust's raison d'être.

5 Likes

So besides the thinks mentioned above I think we might want to find out why -Zinsert-sideeffect caused given compiler and runtime regressions and in context of this what optimizations rely on it.

I originally thought that it will mainly be used to eliminate "useless" code as generated by macros, but then realized that it can potentially yield noticeable performance improvements for other cases like e.g. some use of monomrophisation. I fare for some programs the runtime penalty might be far worse then 7%, but I have to look further into it. Also another situation in which it might be useful is if applied to code after const progragation (in llvm).

So I'm not sure if rust can go without forward progress without losing performance competitiveness.

The fact that it also means the compiler has to do much more work on loops and recursion code to detect if it can eliminate some of it driving up compiler times is another problem.

So I wondered how can rust have forward progress optimizations without UB?

While this definitely needs more research into it I believe it's possible defining forward progress rules which do not trigger UB but explicitly allow certain kinds of optimizations.

E.g. something like "writing code which doesn't cause forward progress does not trigger UB but the compiler is allowed to eliminate it" (just more formal).

If such a rule is paired with a fn busy_hang_thread() -> ! function and the type system soundness hole is closed this could be a viable (but irksome) solution.

Through if we find a way to do without forward progress at all, that would be even better.

If loop {} isn't going to spin forever, and isn't going to trigger UB, then what is it going to do?

4 Likes

Like I says the compiler is allowed to eliminate it. (I.e. loop {} does nothing.)

In C/C++ they often go through UB to allow optimizations, but this isn't necessary if it's clear which optimization you want to allow and you want to allow no other optimizations you can directly specify this without UB.

The problem with UB is that the compiler can do basically anything and you can't really know nor relay on it acting in some ways. With that you could know and relay on it only eliminating "useless" code. Which can at most affect your program by not hanging a thread (but as it's in sync with rustc doesn't open a type system soundes bug as it was e.g. shown in the above linked playground example).

Sure it's not the most intuitive behavior but it would well cover the case where anyone runs into this by accident and by adding warnings people wouldn't be surprised.

Edit: In case of loop {} we can always proper warn or "magically" replace it with the thread hang function, but there are other cases where we can't as they are to complex for rustc to detect with reasonable performance.

How would it be made sound without being a seriously breaking change?

Right now, I can cast loop {} to any type I want. Like this:

let x: i32 = loop {};
println!("{}", x);

Lots of code relies on this "! can coerce to anything else" behaviour.

If loop {} gets eliminated, then what will the println print?

9 Likes

This is not actually true -- I am told that loop {} is a common construct e.g. in embedded panic handlers, where you want to be able to attach a debugger and get the stacktrace, for example (and e.g. resetting the device would lose all the stack state).

8 Likes

As I mentioned above the type system bug can be solved this can only cause problems when the type system knows about unreachability and as such allows such thinks. In which case we can make sure the "non returningness" is not eliminated at all. The "compiler can eliminate it part is for cases where the type system doesn't know that a part of code is "non return".

1 Like

You're right, but in a scenario like that you can use @naicode's idea of having a lang item function core::intrinsic::hang_forever() function.

Through I want to make clear that I don't like the solution I proposed.

If we somehow can get way without any forward progress rules this would be much better. And to know if we can more research needs to be put into the actual benefits of it.

1 Like

No, it matters even in cases where the type system doesn't know that the function loops forever.

Take a function like this:

fn infinite_function() -> i32 {
    let x;
    loop {
        if function_that_always_returns_false() {
            x = 1;
            break;
        }
    }
    x
}

If the loop is completely removed, then we're again returning an uninitialized variable, which will quickly lead to UB. How could this loop be removed without doing that?

Edit: Here's a playground link to prove that the compiler actually does accept this code.

1 Like

Oh, dang. Yup I overlooked that possibility.

1 Like

Yeah, in general pretty much any form of "the compiler might ignore a meaningful thing that you wrote" immediately implies UB in some code that we wouldn't expect/want to be UB, even if it takes some effort to "weaponize" it.

AFAIK there's no design discussion for us to work through until after someone's managed to figure out why the fix had such significant regressions, and what the options are for mitigating them.

9 Likes

I mean we could extend it from triggering on "potential reached unreachable code" to also cover potentially uninitialized variables.

But it's probably not enough, no longer as easy to detect and might be costly on compiler time (don't know the rustc internal good enough).

Maybe instead we can inject the "magic side effect marker" into loop {..} statements of any kind but not for and while loops. But that would probably not enough either.

Also it might no longer be that helpful.

No they are to different thinks, one is well defined by surprising and not-so-deterministic behavior (can change between compiler version). The other is "the compiler can do basically anything it likes including wiping your OS if run as admin".

Through I won't deny that in practice close together and can be abused to potentially hide security vulnerabilities. At least if combined with unsafe code.