What about: inbounds memory that segfaults on access?

[RalfJung]

It has been a long-established principle that memory which is "inbounds" of a Rust allocation must not cause side-effects for reads and writes (other than the obvious ones) -- in particular, it must not abort execution. This is required because the optimizer will happily reorder accesses and move accesses to "dereferenceable" pointers out of conditionals or loops with no regard for other side-effects. Slightly more precisely, what this means is that when adding an allocation to the Rust AM (e.g. as part of the story for an asm block or FFI call), all memory inside that allocation has to be mapped, or else this operation is UB.

However, last year we had multiple discussions about the possibility of weakening this requirement. The core observation is that the worst thing that can happen with such accesses is that the entire program gets aborted, which is "safe". So it seems plausible to say that when adding an allocation to the AM, it's okay to have some of its pages not mapped, but if you do that then your program may abort at any time without any reason whatsoever, i.e., even if the program ostensibly never accessed the offending memory, execution can still abort "randomly". This caveat is required to account for segfaults caused by reordered or speculated accesses.

This could also be helpful for file-backed mmap which is always at risk of some other process truncating the file and thereby unmapping a bunch of the pages that the current process may consider to be inside a Rust AM allocation.

This came up recently again in the context of SGX where apparently even the pages holding the program text can be unmapped at any time by the untrusted code and somehow that's supposed to not be UB. Program text isn't a concept that exists inside the AM so this would require slightly extending the idea, but the basic principle remains the same.

At the moment I am not aware of anything wrong with that approach, but we should certainly get it blessed by LLVM before officially telling Rust programmers that they can do this. Cc @nikic

[nikic]

I'm not sure I fully understand the semantics being proposed here. It seems like a prerequisite for this would be that loads of non-dereferenceable memory are not UB, otherwise speculation would introduce UB. But if they are not UB, then what are they? Giving such loads the allowance to abort without UB implies that loads are no longer willreturn, which has massive implications for optimizations. That's something we could consider for volatile loads (we already treat volatile stores as non-willreturn, though this was always considered something of a workaround than a desirable model) but I don't think this is at all viable for non-volatile loads.

[theemathas]

I'm not sure I understand what Ralf is proposing, but here's my proposal:

• Reading/writing from memory that causes a segfault isn't UB. Marking a pointer to such memory as dereferenceable is also not UB.
• If a pointer is marked as dereferenceable (or some read/write operation is done through a pointer) but the pointer points to segfault-inducing memory, then the program might or might not segfault, even if the pointer isn't read from.
  • The segfault may occur at any point in time starting from when the memory started being segfault-inducing, even before a dereferenceable pointer is created, or after it is destroyed.
• If the program doesn't segfault, reading from this kind of weird pointer results in reading some nondeterministic byte values.

See also rust-lang/rust#154321 (comment) for my attempt at specifying this for specifically the SGX scenario.

[RalfJung]

I'm not sure I fully understand the semantics being proposed here.

The first step is to say that it's okay for the AM execution to just abort at any time for no reason.
(This is already somewhat true, i.e. any function call can fail because of stack overflow, and LLVM can introduce libcalls, and those might be hoisted out of a maybe-never-taken loop, so there are many points in the program where execution can just abort for no reason.)

With that in place, loads of non-dereferenceable memory are not UB, and they are willreturn. They may also abort execution aprubtly but that's okay, it can already happen on any instruction anyway. The intent is not to restrict at all which optimizations the compiler can do.

(Separately, it'd indeed be nice if volatile accesses were not considered willreturn, as that would simplify using them for non-AM memory. But that's a separate question from whether accessing AM memory can abort the program.)

[nikic]

The first step is to say that it's okay for the AM execution to just abort at any time for no reason.

This seems ... fishy? I understand what you're aiming for here, but this means that transforming if (x) { trap; } into trap; if (x) {} becomes a "legal" optimization right? I assume the intent here is that we're obviously not going to do that as a matter of QoI, but just the fact that it would be allowed means that the operational semantics become insufficient for reasoning about which transforms are "allowed".

With that in place, loads of non-dereferenceable memory are not UB, and they are willreturn. They may also abort execution aprubtly but that's okay, it can already happen on any instruction anyway.

I'm still trying to square what the combination of "can abort" and "is willreturn" means. Can you spell out what this means operationally?

To clarify, the property we want to preserve is that this:

print(x == 0)
load (of potentially non-deref memory)
assume(x == 0)

Can be optimized to:

print(true)
load (of potentially non-deref memory)
assume(x == 0)

How is the load specified such that this property is preserved?

[bjorn3]

How is the load specified such that this property is preserved?

That would be a load of an entirely non-existent allocation, so would be fine to optimize. This issue is specifically about cases where there is a valid allocation, but part or the entirety of it may trap when an actual access is done to it at the assembly level.

[RalfJung]

This seems ... fishy?

Yes. Not aborting "too much" becomes basically a QoI concern.

Multiple people expressed that they have use-cases where "fishy" is better than "UB". Personally I'd prefer if we didn't have to do this, but the question keeps coming up in #t-opsem so I figured it's worth tracking in an issue.

We can make this slightly more refined by saying that such spurious aborts are only allowed of there currently exists AM memory that is unmapped. This makes the trap transformation you mention illegal unless the optimizer can prove that there's unmapped memory somewhere inside the AM at the moment.

but just the fact that it would be allowed means that the operational semantics become insufficient for reasoning about which transforms are "allowed".

I mean, that's already the case. Transformations that make the program slower and bigger are "not allowed".

How is the load specified such that this property is preserved?

load non-deterministically aborts execution or returns the contents of AM memory at that location.

So yes this means that even unmapped memory has to have a "content" in the AM -- I didn't realize this before. We can probably just say that it's uninitialized or poison or so.

[RalfJung]

Regarding willreturn, I agree it sounds odd. But consider this: I assume LLVM treats basic float operations as willreturn. Some of them can be lowered to libcalls. Those libcalls can fail due to a stack overflow. Does that make anything unsound? I don't think so. So it's already allowed for a willreturn operation to just abort the entire execution. What's important is that at least one of the non-deterministically possible executions actually returns (and this non-determinism is not correlated with anything else so the compiler always has the option to choose the returning path). Together with the fact that any operation can spuriously abort, that means we can basically move the abort effect around to wherever we want.

[nikic]

Regarding willreturn, I agree it sounds odd. But consider this: I assume LLVM treats basic float operations as willreturn. Some of them can be lowered to libcalls. Those libcalls can fail due to a stack overflow.

Yes ... but this assumes that we model stack overflows as part of the AM. Is that necessary?

My view on this would be: The AM can always just stop execution at some point. This can be independent of whatever goes on inside the AM, e.g. because the process was killed or there was a power outage. The AM can't observe this, can't rely on it, and it has no impact on permissible optimizations.

Now, I'd say that stack overflow is essentially the same thing, just that the stopping of execution is now correlated with something going on inside the AM (like a recursion depth being exceeded). Once again, this is an external action that is not observed by the AM, it can't rely on it, it has no impact on optimization.

Stopping execution when certain memory is accessed would be just one more example of that.

The distinction I'm trying to draw here is that "AM executed trap" and "AM execution was not continued at some point for whatever reason" are not the same thing. The former is part of the observable effects of the AM, the latter is not.

From that perspective, I'm not sure this even needs any additional guarantees from LLVM? What LLVM ultimately cares about is just that you have provenance to perform the access. If certain accesses can stop execution, but in a way that can't be relied on from within the AM, and that (by design) does not affect allowed optimizations, I don't think LLVM really cares about that?

[RalfJung]

There's IMO a big difference between the execution stopping due to outside influence (power cut, SIGKILL) vs the compiler itself emitting instructions that cause execution to be stopped (function calls that may overflow the stack, memory access that may trap). In any formal model of compiler correctness, those would also typically be treated differently.

[nikic]

Another question I have here is that I'm not sure I understand what use-case this is sufficient to solve. I assume the general idea here is that you want to be able to work with potentially trapping memory using normal accesses on shared references (without this requirement this would be solved by the volatile access provision from #610).

However, what are the use cases where memory becoming potentially trapping is the only thing that can happen, that is, there is no possibility of concurrent writes? You mention mmap file truncation, but in that case you also have to worry about (non-truncation) modifications of the file, right? At which point we get back to the usual discussion of atomic bytewise memcpy (and once you need a special operation, you might as well make it volatile and get guaranteed trapping behavior).

[RalfJung]

Apparently there are situations where the untrusted code can unmap pages but not mutate them -- that's at least my understanding of the situation in SGX.

For other cases like mmaping a file, the idea is to use atomic accesses on maybe-trapping memory. That has multiple advantages over volatile accesses:

• there is no volatile "compare-and-swap" or other RMW operations
• volatile accesses unnecessarily preserve the exact sequence of accesses, while atomics can still be somewhat optimized

OTOH the formal foundation is much weaker for atomics; I don't know a single work that studies the use of atomics across trust boundaries, let alone proves anything about this usecase.