Types as Contracts


#21

Really? I mean, the semantics of noalias when applied to return values are completely opaque to me, but I am not sure how this is supposed to work. Clearly, the noalias has to expire some time:

{ let x1 = v.index_mut(0); }
{ let x2 = v.index_mut(0); }

The two x do alias, after all. So, if it expires, I assume it’d have to expire when the lifetime of the return value ends. But now if I call unknown code between the two blocks, how does noalias guarantee that the vector is not changed?

I can imagine a version on Unique that has an unsafe &mut getter, putting the obligation on the caller to make sure the data is actually valid for the right lifetime. This could then trigger valdiation in my model that enforces uniqueness of this mutable reference, which should – I think – in turn justify putting something like noalias to LLVM. But that is still not enough to get what you are asking for.

You are doing offset_to for pointers between different allocations. That value is not useful for anything. So no, this is not legal in my model, you can’t use pointer arithmetic to move from one allocation to another. (That’s following the memory model implemented in miri, which I think is pretty reasonable.)


#22

Such out of bounds accesses can be UB for much simpler reasons than validation or the semantics of Unique. I think the general consensus is that similar code should be UB even if everything is done with raw pointers (+ whatever else you need to get “the least invariants”), because ptr.offset implies you “stay within the same object”. (With ptr.wrapping_offset on the other hand it would be defined.)

I believe current miri (even without @RalfJung’s validation/contract work) will refuse to run this code because it treats pointer as numeric addresses (offset_of). If it does run, it will still register as an out of bounds access.


#23

Unfortunately, the compiler does not warn about unsafe blocks which are not minimally scoped and you wouldn’t want it to either. But this means that someone can either of the following things:

let p: *mut i32 = std::ptr::null_mut();
let x: &mut i32 = &mut unsafe { *p };
unsafe {
    let p: *mut i32 = std::ptr::null_mut();
    let x: &mut i32 = &mut *p;
}

I think it’s important that both of these generate the same code with the same semantics. It’s difficult to do that if you let the programmer’s choice of where to put the unsafe block impact semantics.

Basically, to put it another way, safe operations inside an unsafe block are still safe operations. The unsafe block does not make code unsafe, it only allows unsafe operations to occur.


#24

I’m not thinking of marking index_mut's return value as noalias. Rather, the Unique pointer itself would be noalias, as all accesses must be “based on” the pointer (in the case of Unique, forever; there shouldn’t be another copy stashed somewhere). index_mut, for its part, would be inlined, so LLVM would just see it as a field access.

Currently, rustc uses the original noalias annotation, which only works for function parameters and return values. It already applies noalias to all parameters and return values of Box type; in theory this could be extended to anything that uses Unique, although it would require some modification.

But it would be better to revamp it to use newer forms of noalias, which allow for arbitrary scopes, not just function boundaries: either scoped metadata, which was added to LLVM a few years ago (relevant rustc issue), or, better, the upcoming intrinsic, which is designed to “[m]ake it practical to use scoped-noalias metadata to model block-level restrict-qualified pointers from Clang.” This should work for both Unique (which, as I said, is noalias ‘forever’) and references (which can’t be aliased for a given lifetime, a.k.a. the “scoped” part of scoped metadata).

Hmm… I guess that’s fine, then.


#25

True – however, really, if a function contains an unsafe block, the extent of that block doesn’t matter. All code in that function is potentially subject to subtle invariants that the compiler does not understand.

How and where would that happen? Can the field of a struct type be marked noalias in LLVM?


#26

Rust and it’s standard library can’t exist without unsafe code somewhere. And if unsafe blocks truly had this property, that would imply that Rust’s safety guarantees are only upheld by luck rather than by the semantics that are prescribed for every operation in the language. I understand that this is hard and complex stuff but the answer that unsafe code does hand-wavy things to code around it just isn’t robust enough.

I’ve proposed this question before, but I suppose I’ll ask again: Each operation which requires an unsafe block has to have a minimum set of guaranteed semantics for that operation to be useful. What are all of the unsafe operations in Rust and what are the minimum semantics of each one?

When I hear “unsafe code guidelines”, I immediately think: Documentation on what unsafe operations exist and what they are guaranteed to do. I don’t think about optimizations or types as contracts or tootsie pops or anything else. If the unsafe code that exists, works, then these semantic guarantees have to exist or we’re building on a house of cards.


#27

That’s certainly not the goal. It is fine for the compiler not to understand invariant (in fact, I think it is necessary – there are invariants too complicated to be taught to the compiler). What is important is that in code that handles these invariants, the compiler is cautious with its optimizations.

Writing such a documentation is exactly the goal of the unsafe code guidelines team! The problem is that this is strongly intertwined with optimizations and models like access-based vs. tootsie pop. If the documentation guarantees too much, that inhibits optimizations. If the documentation guarantees too little, lots of already existing code would suddenly be (technically) broken. So we are walking a thin line here, trying hard to come up with a precise model that can clearly tell you whether a piece of code is okay or not. The documentation would then follow from that model.

For example, translating “types as contracts” to such a documentation would say that e.g. when you store into an unsafe pointer, if pointer points to currently valid memory and if there is no read lock and no foreign write lock held on that memory, the store will happen and change memory accordingly. If the conditions are not met, the store is UB.

Notice, however, that it’s not just unsafe operations that need documentation. Unsafe code can call back into safe code in ways that safe code never could (e.g. passing aliasing references); the documentation has to explain what happens in such cases as well.

Does this help?


#28

My point is that the only reason why the compiler needs to be cautious with optimizations is due to the semantics of each operation used by the programmer in the code. Unsafe blocks shouldn’t change the semantics of any operations.

That’s why I’m asking for the minimum guarantees that are required to make each operation useful. For example, *p where p has type *mut i32 is an operation that requires an unsafe block. For that operation to be useful, it has to provide a minimum set of semantics and guarantees. There may be guarantees that current code relies on that aren’t in the minimum set, but that doesn’t prevent specifying the minimum set.

It would seem that you’re attempting to start from the top and go down. I’m attempting to start from the bottom and go up. Currently, unsafe code exists and works. The only reason it works is because the compiler isn’t aggressive about optimizations.

I’m suggesting that there is a lowest common denominator which exists that expresses the bare minimum set of semantics. It would probably make lots of code invalid if the compiler optimized based on the minimum, but knowing what the minimum has to be seems like it would be useful to understand what code is enabled each time the bar is raised to provide additional guarantees.


#29

And I absolutely agree. :slight_smile: However, you other post indicated that you thought “being cautious” was restricted to the immediate operation itself. That is not so. Compiler optimizations typically analyze (at least) the entire function to deduce the properties they are about. So, when I say we have to be cautious around unsafe operations, that really means we have to be cautious (at least) in the entire function if it contains an unsafe operation anywhere. If there is no warning for your code, a function has an unsafe operation anywhere if and only if it has an unsafe block.

Part of the problem here that it is hard to figure out what exactly code relies on. (This is one reason why I want to use miri to test exactly that). Also, “guarantees” do not form a total order: Part of the question here is picking the very framework in which these guarantees should be expressed. Depending on the framework, the question “what do I have to guarantee to make this particular piece of code legal” may have very different answers.


#30

I was writing a longer post about how noalias can be used, but in the meantime, fI think I found a case (for real this time :slight_smile: ) where your semantics don’t justify a current optimization. It’s not important for this optimization to occur, and I think switching to the newer versions of noalias would allow rustc to prevent it without affecting most real-world code (switching would also allow improving optimization potential in many other ways). Nevertheless, I thought it was worth posting, if only as a demonstration that your semantics wouldn’t be 100% compatible with rustc as-is.

Here it is:

#![feature(test)]
fn main() {
    let boks = Box::new(43);
    let raw = &*boks as *const i32 as *mut i32;
    println!("{}", foo(boks, raw));
}

#[inline(never)]
fn foo(mut boks: Box<i32>, raw: *mut i32) -> i32 {
    let a = *boks; // load #1
    m::bar(&mut *boks, raw);
    let b = *boks; // load #2, boks is assumed unchanged
    a - b
}

mod m {
    use std::mem::drop;
    extern crate test;

    #[inline(always)]
    pub fn bar(reff: &mut i32, raw: *mut i32) {
        if reff as *mut i32 != raw {
            // panic without LLVM knowing this must panic
            test::black_box(panic_please as fn())();
        }
        drop({reff}); // get rid of the reference
        unsafe { *raw = 1; }
    }
    fn panic_please() { panic!(); }
}

Basically, foo is called with a Box and a raw pointer, both pointing to the same place. However, rustc gives the Box noalias metadata (the old argument version), which has the semantics that load/stores to pointers ‘based on’ it should not alias with stores to pointers not ‘based on’ it, until the function is done executing. Thus, a store to the raw pointer would be UB.

The tricky part is doing a store to the raw pointer without also violating your rules: the reference must not be write locked at that time, and any unsafe code must be separated into its own function, so that any potential deoptimizations that might apply to unsafe functions or modules would not extend to the problematic optimization.

For the former, I reborrow the box when passing it to bar, which should suspend foo's write lock; bar then calls drop, moving the reference, to release its own write lock, before calling baz.

For the latter, the noalias metadata is generated on foo, while only baz contains unsafe code. The if at the beginning is just to make it ‘well-behaved’ as a safe exported function, i.e. safe code shouldn’t be able to cause bad behavior by calling it. That’s only necessary in the first place if baz is required to be exported, i.e. if the presence of unsafe code deoptimizes entire modules. (Note: In this version, it is necessary for LLVM to inline bar in order to perform the problematic optimization. If either unsafe doesn’t deoptimize entire modules, or you drop the requirement that public functions be statically [as opposed to dynamically] well-behaved, then it’s not necessary for unsafe code to be inlined at all.)

Anyway, it should print 0 if you compile it with optimizations and 42 without optimizations. This is because LLVM coalesces the two *boks loads into one.

This could be avoided by switching from old noalias to either scoped noalias metadata or the upcoming noalias intrinsic, both of which assert that loads are non-aliasing only with respect to specified instructions (as opposed to absolutely everything). Where a mutable reference or box (or a load/store of one) is marked noalias, rustc could exclude, from ‘specified instructions’, any call instructions that take place while there’s an active reborrow of that reference which might be visible to that call (i.e. passed as an argument or otherwise escaping).

In practice, that would usually be an argument, and in normal code it wouldn’t be possible anyway to rule out writes to that argument (because normally, functions that take mutable references do so for a reason) - so such a change shouldn’t generally cause performance loss.

(Oh, boy, I hope I didn’t write this up only to be missing an obvious reason the code would be illegal :slight_smile: )


#31

Cool.

By way of example, if I have the following code:

unsafe fn foo(a: i32, b: i32, p: *mut i32) -> i32 {
    if !p.is_null() { *p; }
    a + b
}

a + b is a safe operation and *p is an unsafe operation. My hypothesis is that the semantics of a + b cannot change just because it occurs within an unsafe block. Whether or not the compiler ends up ‘being cautious’, the semantics of safe code within an unsafe block does not change. And the size of the block is irrelevant and so is the keyword unsafe itself. The only thing that matters is the semantics of *p.

Hopefully, that adds clarity to what I mean/meant.

Defining the minimum semantics required for an unsafe operation to be useful purposefully ignores the issue of what real Rust code relies on, because it doesn’t matter when answering the question. So, while this is eventually a problem, it doesn’t prevent answering my question. And the framework for expressing them is the semantics of the code when executed.

As an example, let’s take *p when p is *const i32. The bare minimum semantics would be that the result is an i32 with the value stored at the address pointed to by p, only when p was created from an expression of the form &i where i is of type i32. This would only allow code of the following basic form:

let i: i32 = 0;
let p: *const i32 = &i;
assert_eq!(i, unsafe { *p });

This semantics doesn’t allow interfacing with C code, for example, because it only provides for creating valid pointers from types that are originally declared as Rust types. However, I believe it would allow implementing Rc<i32>, assuming the language provides a way of creating an i32 on the heap.

At this point, someone would point out that there’s real code that requires additional semantics and guarantees. You would extend the semantics to account for values declared in C/asm/etc. You’d have to account for transmutes from u32, etc. Perhaps some real code out there requires semantics that we don’t want to guarantee and those would be rejected.

If I take a step back, I don’t understand why there’s a focus on finding a framework first. A framework may not even exist and it’s been a year and an obvious framework hasn’t occurred. Perhaps trying to find a framework before identifying and documenting a minimum semantics for each unsafe operation is asking too much? Is there even a list of every unsafe operation, even without semantics?


#32

If we are to follow this type of model, I would prefer for clarity, explicitness, predictability, and avoidance of unnecessary pessimizations, that we trust types anywhere outside of an unsafe block. That is, I would prefer that rather than releasing at the beginning of the function immediately after acquisition, we instead release before the unsafe block and acquire again afterward.

In the swap example, this would mean the now-shadowed x and y arguments would be released before entering the unsafe block, making this example no longer UB.


#33

unsafe { *p } is a block expression and therefore a vexpr, so this creates a reference to a temporary with the value of *p, rather than a reference to *p.


#34

Does that mean that I have the following pairs of code that are equivalent:

let p: *mut i32 = std::ptr::null_mut();
let x: &mut i32 = &mut unsafe { *p };
unsafe {
    let p: *mut i32 = std::ptr::null_mut();
    let x: &mut i32 = &mut { *p };
}
let p: *mut i32 = std::ptr::null_mut();
let x: &mut i32 = unsafe { &mut *p };
unsafe {
    let p: *mut i32 = std::ptr::null_mut();
    let x: &mut i32 = { &mut *p };
}

#35

This is indeed very interesting, thanks for sharing! I am still trying to understand what is going on. In particular, I do not understand why it needs inlining and what you said about under which conditions it would not need inlining. What do you mean by “statically [as opposed to dynamically] well-behaved”? We do want UB to be testable, so if a particular execution calls a buggy safe function (like bar without the inequality test), but doesn’t happen to hit the bad case, that program is well-behaved. E.g., the following program is fine:

mod m {
  pub fn bar(do_sth: bool, raw: *mut i32) {
    if do_sth { unsafe { *raw = 0; }}
  }
}

fn main() {
  bar(false, 0 as *mut i32);
}

bar is not actually a safe function, but the program happens to not exhibit the bad case.

Still, it’s great that you made bar a truly safe function, as that makes the entire argument much more interesting.

Inlining is somewhat more subtle than usual in my model because of the memory locks being acquired by a function, and locks being released when the function terminates; so arguing that inlining doesn’t change behavior becomes tricky. I am sure inlining can be made to work, but it may need some further instruction to do the auto-lock-release on the inlined return edge.

I am trying to find one, but the code seems fine under my model. :wink: bar checks that it actually has the permission to write to raw, so it doesn’t violate its interface.

I assume if we want this to be UB and have the optimization, we’d have to say that bar is actually lying about being a safe function? That’s a little funny, because the unsafety is only possibly exposed by inlining. Interesting indeed.


The hard question is not what this operation does when we allow it. The hard question is, when should it be allowed? As a simple example, your suggestions would also allow things like

let i = Box::new(0);
let p : *const i32 = &*i; // *i is of type i32
drop(i);
assert_eq!(0, unsafe { *p });

miri’s memory implementation handles all the questions around not using dangling pointers, and not doing out-of-bounds pointer arithmetic (check out Rc::from_raw, you need pointer arithmetic even to handle Rc<i32>). However, it still allows too many things to do the optimizations we want to do.

I don’t think you really can acquire again afterwards. The hard question is what to acquire, and at which type. Most of this information could in principle be acquired from the borrow checker, but when it comes to borrowing elements of a slice, the borrow checker only has approximate information – so we just would not know what to acquire.


#36

The reason it needs inlining is that in:

m::bar(&mut *boks, raw);

…if LLVM couldn’t inline (or at least inspect) m::bar, it would have to assume that m::bar might just directly mutate through the reference parameter.

Why does bar have to take the reference parameter? Well, we should pass a reborrowed reference to some function to release the lock (just a block could work too, but with NLL it’s less clear how the lifetimes work out). But also, for bar to be truly safe, we have to pass an &mut to it or to some other trusted (same module as bar) function, so bar knows the raw pointer it’s writing to isn’t locked.

But if we ignore all that and allow “not actually a safe function”, the reference-taking (ergo must-be-inlined) function doesn’t have to be unsafe or trusted. It can be an intermediate, fully-safe function:

#[inline(always)]
fn bar(reff: &mut i32, raw: *mut i32) {
    drop({reff}); // get rid of the reference
    m::baz(raw);
}

…which calls a “not actually safe” function that need not be inlined, because it doesn’t take the reference:

mod m {
    #[inline(never)]
    pub fn baz(raw: *mut i32) {
        unsafe { *raw = 1; }
    }
}

(It takes raw, which is the same pointer, but from foo's perspective isn’t “based on” boks, so supposedly can’t be the source of aliasing writes.)


#37

I’ve been thinking a little more about your example @comex. I first thought that this is about having raw pointers in the function type (so one possible fix would be to not emit noalias for functions taking raw pointers), but actually I am not sure about this. I assume LLVM also treats bitcasts as “derived from”, so passing a usize would work just as well as passing a raw ptr?

mod m {
    use std::mem::drop;
    extern crate test;

    #[inline(always)]
    pub fn bar(reff: &mut i32, raw: usize) {
        let raw = raw as *mut i32;
        if reff as *mut i32 != raw {
            // panic without LLVM knowing this must panic
            test::black_box(panic_please as fn())();
        }
        drop({reff}); // get rid of the reference
        unsafe { *raw = 1; }
    }
    fn panic_please() { panic!(); }
}

This is also a function that I would think is safe, but that would actually be misoptimized by LLVM in the context you gave above, right? And it’s type doesn’t involve any “strange” types such as raw pointers.


#38

@RalfJung, thanks for writing this up! Great post. I’m currently on vacation in Greece, and what time I have I have just spent catching up on this thread. I just wanted to leave some scattered thoughts, since I don’t have time to write a comprehensive post.

Some thoughts on dynamic checking, frame rules, and open worlds =)

To my mind, the most important part of this design is that each function is responsible for “protecting” its own assumptions. So, as a simple example, if I call foo(x, y), then I retain the locks on my other variables (e.g., z), and hence if foo should try to mutate z, an error arises. What’s nice about this setup is that I do not have to know about all data that exists: I only protect the values reachable from my local variables (in a transitive sort of way).

I think this is a key property for having things be dynamically testable, and in particular for doing dynamic testing when interfacing with random C libraries and other unsafe code. Ultimately I envision that when running cargo test on a project with unsafe code, we will be using a sanitizer – perhaps running in some environment like valgrind. This means that the Rust code can’t expect “full” understanding of what’s going on – i.e., what memory is allocated and how. But it can expect that if it has a local variable z of type &mut T, and it invokes a safe function without giving it access to z, then *z is not accessed.

Why I think locks make sense

As for the decision to use locks, I was initially opposed to this – I wanted to use a model where, when you dereferenced a pointer, we checked at that point if the reference had been invalidated. But after talking with @arielb1 at the compiler design sprint I changed my opinion. In particular, @arielb1 pointed out if that you have some code like this:

let x: &mut usize;
*x += 1; // A
foo();
*x += 1; // B

Ideally, we would remove statement B and replace statement A with *x += 2. This is possible in the locking based model – we retain the lock when calling foo(), and hence we know that if anyone were to try and read *x (and hence observe our optimization), that would be UB.

However, in the validating model, we can’t do the optimization. The idea of a validating model would be that we would check at statement B that foo() had not accessed *x in any way. That might seem equivalent to holding a lock, but it’s not if foo() never terminates, or if foo() were to panic. That is, imagine foo() were to (illegally, through some alias) access *x, and then abort. It would in that case observe that we had added 2 instead of 1, invalidating our optimization. Locks avoid this problem.

As Ralf’s post stated, this locking model is currently really only intended to capture the patterns that safe code uses. This implies something kind of like the “tootsie pop” model; however, it’s certainly possible to imagine applying Ralf’s proposal to unsafe code, though I think it will invalidate a lot of the extant code.

Sachertorte: Three-layer tootsie pops

That said, I still think the basic idea of “tootsie pop” makes sense as a way for us to get the best of both worlds: highly optimized safe code and correct unsafe code. I would like to have more discussions around this point, but I feel like any kind of “one size fits all” rules will have to give on some of those points (i.e., optimize less, or invalidate a lot).

I do however think my initial proposal had a lot of flaws. The way I now think of it is that there are three layers to consider. I’m going to call this model the Sachertorte model, since Sachertorte has three layers (well, three kinds of layers, anyway):

  • Safe actions – do not need any additional permissions to execute correctly beyond the ones implied by their operands.
  • Unchecked actions – in Ralf’s terms, these functions do not require additional locks to execute correctly, but may require other conditions be met. An example of an unchecked action is calling String::from_utf8_unchecked – as far as the types are concerned, this could be a safe function, but we do require the additional condition that the buffer is valid UTF-8. At present, there are no “built-in” unchecked actions, but users could declare some by labeling a function as unchecke (indeed, we already have this naming convention).
  • Unsafe actions – require additional locks to execute beyond those implies by the types of its operands. The primary example of an unsafe action is dereferencing a raw pointer (*p) – the operand here is p, and its type (*const T or *mut T) implies no locks at all, so clearly we must have some other reason to think we hold the locks. There are other built-in intrinsics which are unsafe actions – transmute, ptr::offset(), etc. And of course users can declare unsafe functions of their own, and calling such a function is considered an unsafe action.

Currently, we conflate unchecked and unsafe in the language with a single keyword. I think this is the root of why the unchecked_get example caused problems.

To be clear, in this Sachertorte model, we would make unchecked be a part of the language (e.g., with an unchecked keyword). You could then write unchecked fn get_unchecked(&self, u: usize) -> &T as the proper declaration for get_unchecked. To call such a function, you would write an unchecked { .. } block – such a block would be allowed to do unchecked things, but not unsafe things (i.e., no raw pointer deref, or calling unsafe functions).

Accordingly, functions that contained only unchecked actions would retain all the normal locking rules of safe code (and hence be optimizable in the same way). Functions that take unsafe actions (but declare a safe interface) would be handled as @RalfJung described (releasing their locks on entry). Functions declared as unsafe in their interface would neither take nor acquire locks.

Grumble grumble problems

I don’t think the Sachertorte model is perfect. I’d like to dig a bit more into its flaws. Here are two that come to mind (leaving aside the basic philosophical objection to distinguishing “safe” and “unsafe” code to begin with, which is of course also important):

Limitations on optimizing unsafe code. One flaw with this proposal is that an unsafe fn – i.e., with an unsafe interface – is allowed to access all of its caller’s state (subject to other rules that prohibit locals from being accessed). It’d be nice to have the ability to give more limits there. This may not be such a big problem, though, since unsafe functions tend to be private, and hence in the same codegen-unit – this makes them amenable to more global compiler analyses.

Module boundaries? I like this idea of unchecked, but there is still some uncertainty in my mind in terms of how to deal with the scoping. In the original post, I talked about the need to sometimes extend “unsafety” to the surrounding module. This makes sense, in some sense, because unsafety and privacy are highly aligned, but also feels uncomfortable. The main reason to need this is that people sometimes write private functions (e.g., fn deref(x: *const u32) { unsafe { *x } }) that in fact have an unsafe interface, in the sense of requiring add’l locks, but are declared as safe. It’d be interesting to drill more into such examples and see how they play out. It may be that if we had dynamic checking, we could render such cases UB (and detect them reliably), and sidestep this problem.

Other ideas

So yeah, I have to go. I’m not satisfied with this post, in particular I’d like to make a more affirmative case why I think that having layers is important to being able to have all the optimizations we want. But I wanted to toss these ideas out there anyway. =) More later!


#39

But… that’s because they are the same thing. For example, here is a simple implementation of ptr::write using nothing but unchecked operations (playground):

unsafe fn write<T>(ptr: *mut T, value: T) {
    let mut vec = vec![value];
    let base_ptr = &mut vec[0] as *mut T;
    let value_again = vec.pop().unwrap();
    let offset = (ptr as usize).wrapping_sub(base_ptr as usize);
    let old_val = mem::replace(vec.get_unchecked_mut(offset / mem::size_of::<T>()), value_again);
    mem::forget(old_val);
}

Unchecked operations are marked as unsafe because they are unsafe. Enforcing a meaningless distinction doesn’t make sense.


#40

I just tested it, and oddly enough, switching to usize seems to inhibit the misoptimization, but only when the store is inlined. In the modified version from my last post, where the store is moved to a non-inlined baz, the misoptimization occurs even after switching to usize.

The fact that it inhibits the misoptimization at all is probably a LLVM bug: the pointer aliasing rules make it clear that inttoptr and bitcast are included in the definition of “based on”, so it shouldn’t make a difference.