"Tootsie Pop" model for unsafe code

[Ericson2314]

@notriddle well, it doesn’t matter that the parameter of the reference type is, but it does matter that it’s the type is &mut _ or & _! It’s TBAA done right!

[comex]

I’m pretty sure Rust doesn’t have TBAA because safe code doesn’t gain anything from it, and unsafe code doesn’t want it. References don’t gain anything from TBAA because they’re already incapable of mutable aliasing; you don’t need to look at the types to determine that.

FWIW, I’ve been under the impression that Rust’s current lack of TBAA is a feature / guarantee, mostly due to this lack of utility. It seems that I’m not the only one - I found two crates on crates.io that try to provide a safe wrapper around transmuting between POD types:

http://arcnmx.github.io/nue/pod/

frozen-tests/rs-lense

I think capnproto-rust does it too, though it’s too complicated for me to figure out what it’s doing at a glance.

Thus, in theory, introducing TBAA to Rust, even limited to safe code, could cause breakage. Though, to be fair, probably not: the only case where TBAA in safe code could be of any use is with Cell-based types, and people probably aren’t using those crates with those.

[notriddle]

but it does matter that it’s the type is &mut _ or & _! It’s TBAA done right!

The difference is a bit more subtle than that. As @comex mentioned, and I overlooked, cell types actually could benefit from TBAA.

But more importantly, Rust’s current aliasing rules for references are neither a superset nor a subset of C’s TBAA.

fn foo(bar: &mut T, baz: &mut T) {
    In Rust, bar and baz cannot point at the same address
    In C, they can point at the same address, and they can be mutably aliased
}

fn foo(bar: &T, baz: &T) {
    In Rust, bar and baz can point at the same address, but they can't mutably alias
    In C, they can mutably alias
}

fn foo(bar: &T, baz: &U) {
    In Rust, bar and baz can point at the same address, but cannot mutably alias
    In C, they cannot point at the same address
}

fn foo(bar: &Cell<T>, baz: &Cell<T>) {
    In Rust, bar and baz can point at the same address, and can mutably alias
    In C, they can also mutably alias
}

fn foo(bar: &Cell<T>, baz: &Cell<U>) {
    In Rust, bar and baz can mutably alias
    In C, they cannot point at the same address at all
}

[nikomatsakis]

FWIW, I’ve been under the impression that Rust’s current lack of TBAA is a feature / guarantee

I agree with this. Not using C-like rules for TBAA, at least, is one of the few things I feel pretty sure about in this whole discussion. =)

Thus, in theory, introducing TBAA to Rust, even limited to safe code, could cause breakage.

This is true, though it’s also true for most restrictions we might add. This is, indeed, one of the points of my blog post, though this concern has not seen a lot of discussion on this thread.

As I wrote in the post, I’m less worried about backwards compatibility as I am about forwards – I expect people will continue writing code very similar to what they write now, whatever we say. But it’s a bit hard to say: right now, there are no clear rules. If we can make rules that are fairly simple, even if they break some existing code, it’s possible that they will be read by enough people that future code won’t break them (or won’t break them much).

Aggressively optimizing would also help, of course, since it would make things stop working faster – or else some way to run your code and give lints or warnings.

[glaebhoerl]

I assume whatever rules we come up with about what is and isn’t defined behavior, MIRI should end up following those rules exactly, and report an error if and only if behavior isn’t defined? That seems like a more reliable way to test than to hope that aggressive optimizations will have immediately obvious symptoms. But that would still only be able to test whether code has defined behavior for one set of inputs at a time, not all possible inputs (you’d need something like symbolic execution to do that?).

I wonder where a Rust interpreter precisely following the memory model would fall on the spectrum between an English-language specification and a fully-formalized specification in something like Coq, in terms of providing confidence that the specification isn’t broken in some way.

[nikomatsakis]

I assume whatever rules we come up with about what is and isn’t defined behavior, MIRI should end up following those rules exactly, and report an error if and only if behavior isn’t defined?

Yes, this has certainly been suggested. How effective it will be as a general purpose mechanism for detecting potential problems remains to be seen, and will depend a bit upon the precise rules, I imagine.

[gnzlbg]

without knowing what the drop function will do.

A different approach could be to mark the variable required to drop a mutex as a volatile so that the compiler can inline drop and reorder before/after droping the mutex, but not across the drop itself. Not that this is much better than the current state of things since it effectively introduces a barrier.

[gnzlbg]

Rust’s type system potentially gives us rich aliasing information – much richer than is possible in a language like C. We can (and to some degree do) feed this aliasing info into the optimizer,

I guess the keyword here is potentially but which aliasing information are we feeding to LLVM? We used to pass noalias metadata to LLVM which is “equivalent” to C’s restrict annotation which is where the wins are, but we are not passing this metadata to LLVM anymore. Is there any other type of aliasing information we are passing to LLVM or are we just inlining as much as possible and hoping that LLVM optimizer is able to recognize Rust patterns?

[gnzlbg]

That sounds more like a reason to implement Undefined Behavior Sanitizer.

While it would be awesome to catch some forms of undefined behavior in unsafe code at run-time this is a titanic task.

There are easy problems like catching out-of-bounds memory accesses that are solved in C++ with the AddressSanitizer. When you go into reading uninitialized memory the current solution is to use the MemorySanitizer. This requires you to recompile the whole world with instrumentation down until libc, and link against an instrumented libc and memory allocator (basically this means recompile everything down to the OS kernel). For being able to instrument code that links dynamic libraries MemorySanitizer users run-time valgrind like instrumentation for dynamic libraries and exchanges the information at the interface at run-time. This gives an idea of the scope of the problem: just to sanitize reading uninitialized memory you need to instrument everything. And we haven’t really reached the hard spots of undefined behavior like accessing an inactive member of an union which currently have no known solution. And if you add data-races (ThreadSanitizer) and some other easier forms of undefined behavior (UBSan) you end up with 4-5 run-time instrumentation stacks that each makes the whole program “only” factor 2-5x slower but that cannot work together at the same time (you have to basically sanitize your program for each of the possible types of UB independently from the others). Doing so for multiple types of UB in general is not yet a solved problem and we are very far from doing so for most types of UB in C/C++.

With this I don’t want to discourage anybody out of trying to implement sanitizers for undefined behavior but rather put in perspective that sanitizers are not the ultimate solution to this problem yet and won’t be for the forseeable future. A lot of projects use ASan, UBSan and TSan in C/C++ to detect undefined behavior at run-time but very few projects use MSan to detect reads to uninitialized memory due to their inhability to recompile the world (and resort to best-effort slow tools like valgrind as much as they can).

[notriddle]

That’s fair enough, but not really applicable to the reference aliasing rules, which are the only form of UB that anyone is discussing right now. Most other forms of UB we’re either stuck with (reading uninitialized memory or the wrong variant of a union) or we just made them defined (arithmetic overflow).

I think we can handle sanitizing the aliasing rules, if we do a decent job of defining what they are, so making them schizophrenic seems unnecessary and would probably make writing a sanitizer harder.

[rkjnsn]

Although I originally thought otherwise, I agree that this code should be safe. As a stronger example, in the current implementation of BTreeMap's iterators, all the mutable iterators store two mutable pointers into the tree, gradually moving one towards the other.

Doesn’t the BTreeMap iterator use raw pointers for the root and node? Even if the rule were that “no &mut reference can alias any other reference once one leaves the unsafe block”, I don’t see how that would affect BTreeMap. Indeed, I think that like in the Ref case, raw pointers are the correct solution when one wants to keep a pointer that does not meet the type-system requirements for & or &mut.

The more I think about this problem, the more I like the solution of “type-system invariants must hold outside of an unsafe block. Code within an unsafe block is free to break these invariants, but they must be restored before leaving the block.” The easiest way to do this is to have any variables that violate type invariants scoped within the unsafe block. To me, this seems like a simple rule that is easy to remember, and the boundaries are simple and obvious (the unsafe block, itself). Indeed, it is what I would intuitively expect and try to uphold in my own code. It’s true that the unsafe block would have to be careful not to expose broken invariants to any safe functions it might call (e.g., it couldn’t pass two aliasing &muts to a safe function), but not exposing invariants to code outside the boundary is necessary for any boundary.

The split-at-mut-via-duplication example can trivially be made to follow this rule by expanding the unsafe block:

impl [T] {
    pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
        unsafe {
            let copy: &mut [T] = &mut *(self as *mut _);
            let left = &mut self[0..mid];
            let right = &mut copy[mid..];
            (left, right)
        }
    }
}

Note that due to scoping, even in the event of a panic, no code outside of the unsafe block can observe aliasing.

The Ref/RefMut case seems like clear-cut UB, and should be handled as such.

If the authors of std can’t write code that’s free of UB, then nobody can.
The authors of std can’t write code that’s free of UB.
------------------------------------------------------------------------------
Nobody can write code that’s free of UB.

That’s not a world I want to live in.

I don’t think an author failing to follow a rule that was not thought out at the time, and which we are just now trying to formulate, is a sign of doom. I agree with @arielb1 that this code appears to be pretty obviously invalid, as the lifetime on the reference is just plain wrong. As I have mentioned before, I think trying to make this case valid should be a non-goal. Further, I think that once we have the rules regarding type-system invariants and unsafe written down, including examples such as invalid lifetimes and aliasing &muts, it will be very unlikely that such code with be written or pass code review.

[Ericson2314]

I think the idea would be that its miri-based (the MIR interpreter in progress). Miri’s virtual heap does most of the work for us. As to libc, I’m relying on the assumption that functions we use will not malloc internally (as to allocation itself, miri special-cases it), and passing pointers to miri-allocated locations should preserve the properties of the virtual heap, provided the ffi function doesn’t do something ridiculous.

[nikomatsakis]

The more I think about this problem, the more I like the solution of “type-system invariants must hold outside of an unsafe block. Code within an unsafe block is free to break these invariants, but they must be restored before leaving the block.”

I’ve been wondering about this. I think the suitability hinges very much on what you call a type-system invariant.

I’ve been trying to write up some thoughts in response to this thread, and one of the insights I came to is that I was conflating various definitions of “abstraction boundary”. For example, one definition is:

• the scope where you find the justification for why things are safe

This lends itself to “bigger” boundaries. For example, in a function like this one:

fn foo() {
    let mut x: i32 = 22;
    let p: *mut T = &mut x;
    let q = unsafe { *p };
}

Here, the unsafe block itself is not a boundary in this “logical” sense. Rather, the entire function is, since it is only based on the function body that I can prove that p is a valid pointer for me to dereference here.

But the words you used were different. They were:

• the scope within which the compiler cannot trust types

In that version, the code I wrote above is fine.

This to some extent comes back to the age-old debate about whether you should make “big” or “small” unsafe blocks. The “big” unsafe blocks people often argue for are more the “justification” style, and the smaller blocks correspond to “the points where I need to prove something” – which somewhat aligns with the “where we can’t trust”. At minimum, it actually seems to me to act more like a traditional barrier (that is, code can’t be moved around it), but one that is scoped to the enclosing “justification boundary”.

Put another way, I think that the unsafe keyword was designed to act as the “justification boundary” – but that’s not the boundary that the compielr cares about when optimizing, really. I mean, we can align the two – which is basically what my proposal was saying – but it will result in less optimization than what we would otherwise get.

Hope that this makes sense, I’m trying to write this in a more structured way, but these are my off-the-cuff current thoughts.

[nikomatsakis]

Put another way, I think that the unsafe keyword was designed to act as the “justification boundary” – but that’s not the boundary that the compielr cares about when optimizing, really

Ah, this is not quite right. I think what I should say is that the compiler cares about both boundaries, potentially.

[rkjnsn]

I think the suitability hinges very much on what you call a type-system invariant.

To attempt to clarify, I mean invariants such as "& and &mut references are guaranteed to be non-null and point to valid data", “a live &mut reference cannot be aliased”, "the data behind a & reference won’t change unless it contains an UnsafeCell", and "A reference &'a is valid for all of 'a". I believe these should always hold when outside an unsafe block. (Some have argued that these should always hold, period, but I think this can make writing correct unsafe code too subtle, and leads to questions such as “can I operate on a *mut if the &mut from which it was obtained is still live?”).

I explicitly do not mean invariants of a given type such as “this raw pointer is always dereferenceable if capacity is more than zero”, “the first N elements of this memory are initialized, where N is the value of the length field”, “the raw pointers in this iterator point to valid nodes within the same data structure”, et cetera. As you and others have noted, upholding these invariants currently requires a wider boundary relying on privacy boundaries, and furthermore seem unrelated to optimizing based on type-system invariants.

[nikomatsakis]

To attempt to clarify, …

Actually, I think what I wrote was wrong. I probably should have said “I think the suitability depends on how you view the role of an unsafe block” or something like that.

[dobenour]

I wrote a part of a memory allocator, and found myself struggling with aliasing issues and indeterminate lifetimes. This forced me to use a bunch of raw pointers.

[notriddle]

If you’re trying to get memory from the operating system yourself, and thus are also responsible for giving it back, I don’t see why that’s a problem.

[ahmedcharles]

My largest issue with unsafe rust is that there isn’t a clear set of semantics for operations which require unsafe blocks. Trying to define a model for a boundary between safe and unsafe code for optimization purposes doesn’t make sense without understanding the semantic guarantees of the operations on one side of the boundary, does it? For example, the C++ standard doesn’t define ‘boundaries’ where the behavior of the optimizer changes, it just defines the guaranteed semantics of operations given the state of the program when the operation takes place.

At a higher level, I’m not sure it’s reasonable to try to make unsafe code easy to write at the cost of performance. If someone types the unsafe keyword, they should ‘know’ what they are doing or accept the consequences. The goal of the rust team should be to provide the knowledge and guarantees required to write code that works as expected. If someone wants training wheels, that’s what safe code is for.

[nikomatsakis]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.