Blog post: Thoughts on trusting types and unsafe code

[nikomatsakis]

I don’t understand why it is so important to avoid interprocedural analysis

Lots of reasons. First off, you don’t always have all the code available. If you call code from another crate, or through a trait object, I’d like to be able to optimize well without having to know just what code you are calling.

Do C or C++ compilers do these kinds of optimizations without interprocedural analysis?

In the general case, no. But there are ways to enable it. For example, C99 added the restrict keyword precisely for this purpose.

is this an attempt to leapfrog them by exploiting specific properties of Rust?

Both. Consider the case of Fortran vs C. Fortran is generally held to be the faster choice for numerical computing, precisely because of its strong aliasing guarantees:

[Fortran and C] have similar feature-set. The performance difference comes from the fact that Fortran says aliasing is not allowed. Any code that has aliasing is not valid Fortran but it is up to the programmer and not the compiler to detect these errors.

To a large extent what I’ve been advocating for the TPM is that we optimize unsafe code like C compilers, but we do better with safe Rust code. But the pushback is all about doing better than C compilers with unsafe code. Which I am definitely sympathetic to! =)

In fact, it seems to me that it instead just moves the interprocedural analysis step from the compiler to the programmer.

To be clear, this would only be in unsafe code, but yes – this is one thing I am worried about!

Certainly every model has its hazards. In the case of the TPM, the hazard is moving code that used to live inside an unsafe boundary outside of an unsafe boundary. In other models, the hazard might be outlining code into a separate function. I agree it’s important to minimize these hazards – ideally not at the cost of making things complicated everywhere. =)

I would expect that, if such a model were implemented, compiling Rust code with a -fno-tootie-pops flags would become the stated best practice much like -fno-strict-aliasing is recommended today.

I am intrigued by this idea. I cannot understand it. The goal of the Tootsie Pop model, indeed, is to basically emulate the effect of -fno-strict-aliasing. I’m not even sure what “opting out” of it would mean – forgoing optimizations on safe code?

I assume that when you say “optimize Rust code aggressively” you are talking specifically about eliminating or moving loads and stores. Could high-priority optimizations like eliminating unnecessary bounds checks, unnecessary copies during moves, unnecessary zeroing be implemented without doing this?

Actually, nothing in my post talked about eliminating loads or stores. That, indeed, is somewhat easier – if you have two loads, you have some evidence that the pointer is valid between them. What I talked about was code reordering – specifically, moving a load without evidence of another load to come. And I’m not sure how important it is: maybe it’s not. Mostly I’m currently in a mode of trying to push on the boundaries of what the safe type system ought to allow: I focused on this test case because it’s one where, if you only look at the actual loads, you wouldn’t be able to do.

I’m not sure where your list of “high priority” optimizations came from. I don’t know that this particular question (can we move a load later past unknown code) will affect the answers much. But I promise you that, whatever the case, the less we have to know about the surrounding code, the better. =)

As an aside, from conversations I’ve had with people working on the C specification and the like, there is very little data on which instances of UB help the most with optimizing and how. I’d love to see citations and references on this!

[nikomatsakis]

I’m not entirely convinced it’s more subtle than C. My impression is that one of the difficulties with C is that the mental model people use has varied over time as compiler writers have teased optimisations out of implications of the spec (strict aliasing being a popular example)

I am wrestling with two things a bit.

First, the Rust type system is ultimately a static approximation over some more fundamental concepts. You can see this in the discussion about non-lexical lifetimes – if we were to change lifetimes from lexical to non-lexical, a lot of code would now be accepted. And we claim it would still be safe. So clearly there is a more fundamental underlying concept.

To some extent this is what people are referring to when they talk about UB. UB defines the contours of execution traces that are acceptable. The Rust type system guarantees you stay within those contours, but there is a large space of behavior that it can’t accept which would also be valid. So we want unsafe code to be able to explore that area with as few rules and complexity as possible. This was sort of the underlying idea behind the TPM.

But, it’s not that unsafe code is unrelated to the Rust type system. For one thing, a lot of unsafe code relies on other code following the Rust type system in order to be safe. Consider something like this:

fn foo<'a>(&'a mut self) -> &'a u32 { unsafe { ... } }

Here we can rely that we have exclusive access to *self for the entirety of 'a. But what does that really mean? Currently, it means “so long as the return value is in scope” – if we switch to NLL, it means “so long as the return value is in use”. Note that there is a difference there, though I know of no way to write unsafe code that exploits that difference.

But in any case we are relying on our callers to obey the Rust type system’s narrower countours so that we can safely explore this area that lies between. This is precisely why people say that “unsafe code doesn’t compose well”. And of course given that we are using unsafe code to define some basic properties of the Rust language – e.g., unwinding, threading etc – it’s essential for us to set some broader limits on what unsafe code can do that go beyond the core type system.

(For example, I think that longjmp is just fundamentally incompatible with Rust code, since it can cause a local variable’s destructor to be skipped; even though we say that values may be leaked, we still intend for people to be able to rely on RAII if they own the value in question.)

Anyway, add to all this the fact that I think unsafe code authors have enough to think about without burdening them with thinking about the lifetimes of transient references that they create and use. This feels perilously close to C’s TBAA rules. I feel like I’m pretty “in the know” when it comes to aliasing and so forth, but whenever I write low-level code in C I definitely get an itchy, nervous feeling trying to decide if I am properly conforming with TBAA rules. I don’t think Rust’s unsafe rules should feel the same.

[nikomatsakis]

If the rule is to trust types, rustc could have a special unsafe-checking mode that inserted a read at the beginning and end of every reference variable’s life and checked for equality; combine with scribbling over dead variables, malloc scribbling, and maybe valgrind to help with corner cases, and it should be able to catch most errors.

Yes, so this is the direction I’ve been going in a bit (continuing the train of thought from that post). Basically trying to express the “type system guarantees” a bit more concretely – the following properties must hold, at these points.

Another way to think of it would be a kind of “operational semantics” that includes safety checking. e.g., imagine every bit of memory has a version number. When I borrow &foo, I get back a very fat reference that also has the version numbers for all the owned memory (this is just a mathematical construct, obviously, since that could be an arbitrarily large amount of version numbers). Then whenever I load I can check that they still are valid. Or something like that. (Extending this to threading is kind of … fun.)

Not sure if this will lead anywhere productive yet. =)

[nikomatsakis]

Significantly, this can even work across crates due to Rust’s compilation model: the flag could be stored in crate metadata.

Yes, I like this idea. I’ve often thought that we can try to “bubble up” optional information this way. Though I’d prefer to get what we can without needing it. (And – yes, it’d be nice to replace &u32 with just u32.)

[nikomatsakis]

I just think it would be ridiculous to forbid that, and even more ridiculous to make it legal or illegal based on mere existence of unsafe keyword in the same module.

I am intrigued by this. (Edit: I guess this concern is partly what @briansmith was getting at?) Imagine that the declaration were different. For example, imagine that one tagged the module as containing unsafe code:

#![unsafe_scope]
...

In that case, the “scope” of an unsafe block could be the innermost enclosing #[unsafe_scope]. If there is none, then it is the entire crate.

This would mean you could confine the scope of an unsafe block to something within the function, to (maybe?) address the unchecked get use case:

fn do_stuff(x: &[u32]) {
  let mut sum;
  for i in 0 .. x.len() {
    #[unsafe_scope]
    unsafe { 
      sum += *x.unchecked_get(i);
    }
  }
}

I’m not really saying I like this idea, just “tiling the space” a bit.

I have to admit I am still eager to find a way to trust types more, even in unsafe code. I like being able to use Rust reference types to express sharing and uniqueness, since I think that is a super common thing to want to talk about. I just want to find the right balance that gives us a lot of room to optimize without limiting us or making the rules too complex.

[Veedrac]

My view on things looks a bit like an extension of the borrowing rules. If you get a reference, that reference is live. Any unsafe operations derived from this reference means you can’t use the reference again until you stop doing so. A reference derived from non-reference data borrows all of that data; if you want to perform unsafe operations you need to derive it once again from the reference, or wait until the reference is no longer used.

Note that the comment here is not about liveness of references, but of reads and writes. This is because unsafe code is about getting access to the logical model “below” the borrow checker, which is a behavioural thing. (This is my opinion of the “more fundamental underlying concept” mentioned earlier.)

So in this case:

fn patsy(v: &usize) -> usize {
    let l = *v;
    collaborator();
    use(l);
}

We know v guarantees us a borrow of the data. Although collaborator may have pointers to it, those are also conceptually borrowed so it can only perform reads, not writes. collaborator cannot re-derive a mutable pointer because the value is immutably borrowed. The optimisation is thus possible.

And in this case:

fn alloc_free() {
    unsafe {
        let p: *mut i32 = allocate_an_integer();
        let q: &i32 = &*p;
        let r = *q;
        free(p);
        use(r);
    }
}

p is “borrowed” (read: derived) by q, so use of free(p) is only legal with the guarantee that q is never used again. The optimisation is thus not possible.

Now we’re getting to the complicated ones:

fn alloc_free2() {
    unsafe {
        let p: *mut i32 = allocate_an_integer();
        let q: &i32 = &*p;
        let r = *q;
        if condition1() {
            free(p);
        }
        if condition2() {
            use(r);
            if condition3() {
                use_again(*q);
            }
        }
    }
}

When free(p) is called, we have a guarantee that q cannot be used again, because if it was then p would be borrowed and so cannot be mutated. But if condition3(), then q is used again. So the compiler can assume condition1() ⇒ !condition3(). It cannot, however, assume q is live when use(r) is called.

The optimisation is thus not possible, though a better one is (use_again(*q) → use_again(r)).

Note that this means

*(mut_ref as *mut _) = 0;
*mut_ref = 1;
*(mut_ref as *mut _) = 0;

is legal, but

let mut_ptr = mut_ref as *mut _;
*mut_ptr = 0;
*mut_ref = 1;
*mut_ptr = 0;

is not.

[briansmith]

In fact, it seems to me that it instead just moves the interprocedural analysis step from the compiler to the programmer.

To be clear, this would only be in unsafe code, but yes – this is one thing I am worried about!

Thanks for the reply.

I think we need to consider that unsafe itself is shifting some burdens from the compiler to the programmer already. However, I don’t think giving function or module or crate boundaries any special significant w.r.t. unsafe is the right thing to do, because it doesn’t match people’s mental model of how programs work. In particular, I expect “extract function” and its inverse to always work without any semantic change, even across modules (ignoring visibility issues and the need for variable renaming). I think assuming equivalence between a function call and inlining the function’s code is common thinking among programmers.

[quote]

I would expect that, if such a model were implemented, compiling Rust code with a -fno-tootie-pops flags would become the stated best practice much like -fno-strict-aliasing is recommended today.

I am intrigued by this idea. I cannot understand it. The goal of the Tootsie Pop model, indeed, is to basically emulate the effect of -fno-strict-aliasing. I’m not even sure what “opting out” of it would mean – forgoing optimizations on safe code?[/quote]

I mean that I think people would desire to be able to opt out of any optimizations that are done on the basis of extra semantics given to function/module/crate boundaries.

[pcwalton]

Note that Rust is currently generating quite suboptimal code compared to common C++ around moves. It memcpys data around a lot more than code that was written in C++ does, because C++ in practice doesn’t really use move semantics that much. I’ve been working on recovering the performance via compiler optimizations, but a lot of it depends on being able to reason about aliasing, sometimes across function boundaries.

The bottom line is that we do have concrete examples of optimizations that depend on trusting Rust types and that we really want to do in order to reach parity with C++.

[aidanhs]

Anyway, add to all this the fact that I think unsafe code authors have enough to think about without burdening them with thinking about the lifetimes of transient references that they create and use.

To start with, I agree with this. The rules I outlined create a significant amount of mental overhead because, as you say, the code writer has to carefully examine every single lifetime they create.

But, it’s not that unsafe code is unrelated to the Rust type system. For one thing, a lot of unsafe code relies on other code following the Rust type system in order to be safe. Consider something like this:

fn foo<'a>(&'a mut self) -> &'a u32 { unsafe { … } }

Here we can rely that we have exclusive access to *self for the entirety of 'a.

Minor note, I personally wouldn’t want to inhibit optimisations just because (by some unsafe magic) the code could mutate *self just before the end of 'a, so I’d say that we (as people writing rust) cannot rely on exclusive access for the whole of 'a - it’s up to the memory model to draw that line. Which is basically what you’re saying in the rest of the comment, that we need to figure out what properties unsafe code can use.

And of course given that we are using unsafe code to define some basic properties of the Rust language – e.g., unwinding, threading etc – it’s essential for us to set some broader limits on what unsafe code can do that go beyond the core type system.

(For example, I think that longjmp is just fundamentally incompatible with Rust code, since it can cause a local variable’s destructor to be skipped; even though we say that values may be leaked, we still intend for people to be able to rely on RAII if they own the value in question.)

Interesting, would you see this kind of thing going in the memory model or elsewhere?

---

On the subject of trusting types, some invariants seem necessary even in unsafe code - lack of trust may not be absolute. In particular, not being able to use the nonzero optimisation on references is probably a non-starter. The issue on invalid references has a useful comment outlining some possible restrictions. nonzero seems clearly important all the time. dereferencable also feels important, but could disallow the “refcell-ref” example depending on implementation (though I’m starting to feel less sympathetic towards it anyway).

[briansmith]

[quote=“pcwalton, post:23, topic:4059”] I’ve been working on recovering the performance via compiler optimizations, but a lot of it depends on being able to reason about aliasing, sometimes across function boundaries.[/quote]

Awesome to hear that this is being improved!

To clarify, I’m not arguing against interprocedural optimization. I just think it makes sense for the compiler to do the interprocedural analysis too.

FYI, here’s a very common pattern in my code:

impl Something {
    fn new() -> Self {
        let mut x = Something { field: [0; FIELD_LEN] };
        unsafe { c_function(x.field.as_mut_ptr(), x.len()); }
        x
    }

Ideally, I’d like to write this as:

impl Something {
    fn new() -> Self {
        Something {
            field: unsafe { c_function() }
        }
    }
}

However, while the compiler accepts extern { fn c_function() -> [u8; FIELD_LEN] }, the way to write a C function that works for that signature is not documented and nobody knows.

This example shows that the solution to some of these problems may be to change the language to reduce the use of harder-to-optimize things like moves and pointers.

[comex]

Isn’t that just a C gotcha? It’s impossible to return (or pass) an array by value directly in C. If you wrap it in a struct it would work, but if anything it would probably be less efficient, not more. On the other hand, in the first example, the compiler should be able to optimize x to live on the caller’s stack frame (NRVO) even if you take a pointer to it, though I don’t know whether it currently does so.

[briansmith]

Isn’t that just a C gotcha? It’s impossible to return (or pass) an array by value directly in C. If you wrap it in a struct it would work, but if anything it would probably be less efficient, not more. On the other hand, in the first example, the compiler should be able to optimize x to live on the caller’s stack frame (NRVO) even if you take a pointer to it, though I don’t know whether it currently does so.

Right. The question I have is, how do programmers, the language design, and the compiler optimizer work together to optimize such code? I think it’s too limiting to only consider changing the optimizer to solve this kind of problem. As the programmer, I would be willing to add all kinds of annotations or whatever to help the compiler, and I would prefer to do that work instead of dealing with any tricky semantics regarding unsafe and function boundaries.

[comex]

Well, I don’t know about FFI in particular, which is always something of a special case, but I suppose one fundamental conflict related to your example - you may know this, but to lay it out - is that Rust really likes to pass and return structs by value, yet actually memcpying large structs by value is almost never desirable or necessary. If we don’t want to rely on the optimizer, then there would need to be an explicit representation of out pointers (as you often see in C):

let x: BigStruct;
foo(&out x);

By the way, this could also mostly subsume the special placement-new syntax:

// fn append_ptr(&mut self) -> &out T
*my_vec.append_ptr() = BigStruct { ... };
// or
foo(my_vec.append_ptr());

The big problems are of course that this (a) is usually uglier and less readable than passing by value and (b) has some issues in connection with panicking (although I don’t think they’re fundamental).

But it would sure be convenient as a way to guarantee that the generated code is Doing the Right Thing.

…A wilder alternative: a way to mark types as non-moveable by default (maybe except for generics), perhaps requiring the move keyword to do so. But this would only apply to physical moves: there would be fairly broad conditions under which semantic moves would be guaranteed to not actually require a memcpy, and no keyword would be required in those cases. Kind of like how in other languages, guaranteed tail call optimization allows a completely different style of programming (that the mere existence of TCO as a typical best-effort optimization doesn’t), this would be ‘guaranteed RVO’ (except it wouldn’t just be for returns).

Okay, probably a bad idea.

[briansmith]

If we don’t want to rely on the optimizer, then there would need to be an explicit representation of out pointers (as you often see in C):

I believe the Rust calling convention for large return values already does this implicitly. However, sometimes (often?) the compiler doesn’t optimize away the memcpy like it should.

[comex]

All calling conventions do; there’s not really any other way to do it. But if you want a more reliable way to avoid optimizer gotchas, which I interpreted your post as suggesting, the most obvious one would be representing the pointers explicitly. For the reasons I said (and others), perhaps not the best way…

edit: though the problem also applies to passing arguments by value, not just returning them, where things are more varied.

[gnzlbg]

I am still missing the answer to what is for me the most important fundamental question: why should that unsafe code be legal? If it shouldn’t, the rest of the discussion is moot. In the previous post, you argued:

It does allow us to assign blame to the unsafe code that took actions it wasn’t supposed to take. But at the end of the day we’re still causing crashes, so that’s bad. […] So we had better be sure that reasonable code works by default.

But I think this is a very weak argument: writing correct unsafe code is hard and users know it, users need to go out of their way to write unsafe code, the unsafe code you show introduces “aliasing + mutation” that is observable in safe code (which I don’t think qualifies as “reasonable code”).

I agree that making it easier to write correct unsafe code is a noble goal, but I don’t think that it is worth to sacrifice one of Rust’s pilars (zero-cost abstractions) for it. In particular, introducing “regions of safe code tainted by unsafe code” introduces a complexity into the language that writers of safe code need to be aware about. And in my opinion, for little benefit, since there are many ways to crash rust binaries by writing unsafe code, and such regions don’t catch most of them .

So… I guess my stand on the whole topic is that I am fine with undefined behavior in unsafe code, and I am fine with broken unsafe code producing crashes in safe code, which is the situation we have today.

I think a better way to help users to write correct user code would be either static analysis, which is hard, or run-time instrumentation in the spirit of clang’s undefined behavior sanitizer, which I think it is feasible to make detect, and trace back to the faulty unsafe code, not only these issue, but many others (data races, reads to uninitialized memory, and so on).

I like how the blog post flows in the direction at the end that maybe functions should be unsafe abstraction boundaries, but we already have the unsafe keyword which marks unsafe code, so I would really like these unsafe boundaries to be delimited by this keyword only.

[RalfJung]

Thanks for this post! I can very much relate to the idea of “trusting types”. When I first started thinking about a Rust memory model way back then, my inclination was “types should always be trusted, period”. I’ve since been convinced that this is not practical, but I very much sympathize with making “trusting types (sometimes, somewhere)” a cornerstone of the model. This is, of course, hoping that we can find nice and intuitive explanations of what exactly a type promises, so we know what it is we’re trusting. But that’s necessary anyway, in order to establish soundness of the type system.

Yes, so this is the direction I’ve been going in a bit (continuing the train of thought from that post). Basically trying to express the “type system guarantees” a bit more concretely – the following properties must hold, at these points

I’m happy we agree that “soundness” (as in, the guarantees expressed by the type system) and the memory model are related

Imagine that the declaration were different. For example, imagine that one tagged the module as containing unsafe code:

#![unsafe_scope] …

In that case, the “scope” of an unsafe block could be the innermost enclosing #[unsafe_scope]. If there is none, then it is the entire crate.

Why is the crate the default here? Is there any scenario where unsafety should leak further than visibility? After all, the rest of the crate has the same kind of access as foreign crates. If anything could go wrong there, then this doesn’t stop at the crate boundary - it leaks to the entire binary.

---

There is another dimension to trusting types that I’ve not seen come up here in this discussion, but I think it is closely related. It was recently raised on GitHub: When and how far can we trust function types? We can re-phrase the question raised in that issue as follows: Given a value of type for<'a> fn(&'a i32), what do we trust this function to (not) do when called? I would say, we should rely on the function to potentially access its argument (as in, just the 4 bytes covered by the i32) and global variables, and nothing else. Just like we can think of the type &i32 to give us the permission to read from that location, and the guarantee that noone else will be mutating the location; we can think of the type for<'a> fn(&'a i32) as the permission to jump to the code at the given location, and the guarantee that the function will be running just fine if we pass it an &i32, and that it will not touch (not even read) anything else.

In other words, when we start to talk about “permissions granted by types” and in how far we can trust types, we have to consider not just pointer types, but also function types (and really any type). So here’s some rambling (probably more and more incomprehensible) about how I arrived here: In the literature on the semantics of types, there is a standard way to “raise” the “meaning” of types from the base types to function types: A function fn(A) -> B can be trusted to execute safely if you pass it something that it can trust to be an A. (Notice the “negative polarity” here, the function relies on the argument being an A as a precondition for it to be well-behaved.) The function will then return something that you can trust to be a B. (This is the core idea of “logical relations”.) Now, with the Rust type system being about ownership, it would be very natural (at least, from a theory standpoint) to phrase this guarantee in terms of Separation Logic (which really could also be called “Ownership Logic”). In this framework, such a function type makes an additional guarantee: A is really all the function needs; if the caller owns anything else beyond A, he can trust the function to to touch this. (This is called “Framing”.)

I hope at least some of this makes sense to you…

[arielb1]

UB is only defined on traces. Therefore, trusting types can only mean trusting properties that can be discovered from these traces.

And a Rust for<'a> fn(&'a u32) can always access global variables and/or use the hash of the address passed to it as a sort key.

[ahmedcharles]

I haven’t had the time to completely read the thread, but here’s my initial thought upon viewing this code example:

fn alloc_free() {
    unsafe {
        // allocates and initializes an integer
        let p: *mut i32 = allocate_an_integer();

        // create a safe reference to `*p` and read from it
        let q: &i32 = &*p;
        let r = *q;

        // free `p`
        free(p);

        // use the value we loaded
        use(r); // but could we move the load down to here?
    }
}

The call to free would invoke undefined behavior because it’s freeing memory that can still be accessed through q. For example, this code is similar, yet avoids the issue by limiting the lifetime of the potential copy propagation:

fn alloc_free() {
    unsafe {
        // allocates and initializes an integer
        let p: *mut i32 = allocate_an_integer();

        // create a safe reference to `*p` and read from it
        use_value(&*p);

        // free `p`
        free(p);

        // use the value we loaded
        fn use_value(q: &i32) {
            let r = *q;
            use(r); // but could we move the load down to here?
        }
    }
}

Basically, free is an unsafe function and should only be called after all safe references to the function are no longer in scope. I suppose an alternative would be:

fn alloc_free() {
    unsafe {
        // allocates and initializes an integer
        let p: *mut i32 = allocate_an_integer();

        // create a safe reference to `*p` and read from it
        let r;
        {
            let q: &i32 = &*p;
            r = *q;
        } // The lifetime of q ends here, therefore, copy propagation isn't allowed past this point.

        // free `p`
        free(p);

        // use the value we loaded
        use(r); // but could we move the load down to here?
    }
}

[ahmedcharles]

I should probably state that my high level perspective on unsafe Rust is that two things should hold:

1. The optimizer should take maximal advantage of the properties of the ‘safe’ type system.
2. The semantics of operations requiring an unsafe block should be well defined.

I.e. If you don’t understand what’s going on, don’t type unsafe, ever.

Given that I don’t see a good reference for the semantics of unsafe operations, I don’t understand why discussing expanding the scope of unsafe blocks using the TPM or any other model is under consideration. I’d rather have the semantics defined and then see if there are examples of code that cannot be written under those semantics.

Edit:

The blog mentions:

Another takeaway is that we have to be very careful trusting lifetimes around unsafe code. Lifetimes of references are a tool designed for use by the borrow checker: we should not use them to limit the clever things that unsafe code authors can do.

I don’t quite get the reasoning. The primary motivation for limiting what unsafe code authors can do is optimizations and allowing the compiler to apply more optimizations to make all of the code faster (or at least, that’s the goal of the optimizations). The only reason to type unsafe as a Rust programmer is to get additional performance. So, why would a performance focused programmer want to inhibit potential compiler optimizations by virtue of the fact that they are trying to make their code faster by using unsafe code?

Any potential clever thing I can do with lifetimes of safe references is something I can equally do with unsafe pointers, without the compiler having to decide whether to optimize my safe code or not.