Blog post: Thoughts on trusting types and unsafe code

language design Unsafe Code Guidelines
21

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.

22

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 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.

1 Like
23

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++.

4 Likes
24

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.

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.

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).

25

[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.

26

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.

27

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.

28

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.

2 Likes
29

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.

30

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.

31

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.

2 Likes
32

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.

I'm happy we agree that "soundness" (as in, the guarantees expressed by the type system) and the memory model are related :slight_smile:

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...

1 Like
33

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.

34

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?
    }
}
1 Like
35

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.

36

I feel lifetimes don’t offer any optimization potential relative to optimizing “traces” (like @arialb1 mentioned), and make writing unsafe code a lot harder. Plus, this doesn’t solve certain issues of optimization, like the example with collaborator.

My earlier post gives a rule that should be relatively simple to optimize with but doesn’t make the original alloc_free example UB. Perhaps you could give an example your rules could optimize more easily than mine (?).

37

That's a choice we could make, but we could also decide to instrument the execution with further information to decide whether it triggers UB. In other words, just what exact information is recorded in these traces -- and whether they are recorded as traces or whether the "last snapshot" without all the history of how we got there is enough -- is up to us.

Sure, global and thread-local variables are always available. This adds some subtleties to these rules, but doesn't entirely invalidate them. (And those subtleties are the very reason Rust has to be so careful about what it permits functions to do on global variables.) I don't understand what taking the hash of an address has to do with this.

38

I find the notion of an unsafe block deoptimizing nearby safe code distressing, because it goes against my expectations of how unsafe works and how I’ve been using it. In general, I think that if a choice needs to be made between unsafe changing how nearby safe code compiles and unsafe code more subtle than C due to stricter aliasing rules, I would prefer letting unsafe be more subtle than C over letting unsafe have a blast radius affecting how nearby safe code compiles.

As a user of the language, here are some of my expectations (all of these map to actual or, in the case of reinterpreting slices’ pointers as pointers to larger types, near-term planned uses of unsafe in encoding_rs or encoding_rs_compat).

I would expect a transmutation of a u32 to char to have truly zero cost, including in terms of lost optimizations, and I would find it very astonishing and unwanted if this kind of unsafe deoptimized anything nearby. Likewise, I’d I’d expect a transmutation of &[u8] to &str to have truly zero cost, including in terms of lost optimizations. (In fact, before reading the posts here, it didn’t even occur to me that this kind of unsafe might involve lost optimizations nearby!)

I would expect making uninitialized memory available for writing to have a negative cost: I’d expect it to save the cost of zeroing the memory. Again, I would find it astonishing and unwanted if this kind of unsafe deoptimized anything nearby.

The above examples don’t really involve pointer manipulation, so my main point with these examples is that since unsafe in Rust is not qualified with an annotation about what kind of safety is being moved from the responsibility of the compiler to the responsibility of the programmer, it would be particularly bad if the presence of pointer-unrelated unsafe to contaminated the module (or anything nearby) with pessimistic assumptions about pointer aliasing.

Moreover, due to the way unsafe has been characterized in documentation as allowing you to do certain things that are otherwise prohibited, I would find it surprising if marking any pre-existing block (so as not to introduce new scope boundaries) of safe code as unsafe changed the semantics of the code, since such a change wouldn’t introduce any otherwise prohibited actions. If marking an existing safe block unsafe doesn’t change its semantics, having the seemingly no-op annotation deoptimize code behind the scenes would be astonishing and unwanted.

Even with pointers present, if I get a handful of pointers over the FFI and I go ahead and just dereference them (without null-checking), I would expect the generated code to perform as well as it would if those pointers had been references. That is, if I write in the FFI documentation that the pointers must be non-null and must be disjoint and then write dereferences with this assumption, I’m not expecting the compiler to insert pessimism for me.

If I write a function that takes two slices of small integers, say &[u8] and &[u8] or &[u8] and &[u16], and then I decompose those to pointers and lengths and reinterpret the pointers as pointers to larger ALU words or as pointers to even larger SIMD types and read via the pointer that reinterprets one slice and write via the other pointer that reinterprets the other slice, this reinterpreted pointers are still disjoint and I wouldn’t want each write to deoptimize the next read with pessimism about the pointers now may be aliasing.

So my conclusion at this point is that I’d expect unsafe not only to make it the programmer’s responsibility to make sure that Rust’s safety invariants have been restored by the time control exits the unsafe block but also to make it the programmer’s responsibility to uphold Rust’s pointer non-aliasing assumption.

Which would make unsafe even more subtle in terms of UB than C.

Then, going back to the Tootsie Pop examples, I conclude that if an abstraction internally uses unsafe, it may be necessary to introduce additional unsafe in some of the operations that could get messed up under a model where unsafe blocks never affect how safe code is compiled. That is, in the refcell-ref example, I’d rather require copy_drop to use some explicit unsafe operation order forcing mechanism than to have unsafe blocks in a module pessimize safe code.

This means that some internally-unsafe abstractions, such as RefCell, become even harder to write correctly, but hopefully that kind of code will mainly live in the standard library and be written by people who know the subtler-than-C rules. Then, it would probably be appropriate to make other users of Rust aware of unsafe not being just syntactically different C (if the aliasing rules are actually more like those of Fortran) to discourage people from writing large unsafe blocks as if writing inline C.

3 Likes
39

Maybe I'm misunderstanding, but I'm not sure how you're expecting this to be the case. The compiler can make assumptions about fn a(b: &mut T, c: &mut T) that it can't make for fn a(b: *mut T, c: *mut T) unless you

a. allow noalias annotations for pointers b. stop making noalias assumptions about &mut (!) c. make all pointer arguments to functions noalias (!!)

40

I meant c.

I had expected the difference between references and pointers in Rust to be that the latter can be null and aren't tracked by the lifetime system, but I hadn't expected the latter to be less strict about aliasing.