Types as Contracts


#12
  • What about weird things like Unique<T>, used for the pointers inside Box, Vec, etc.? Should it be UB to mutate the pointee while the pointer is borrowed by someone else? (Probably; otherwise you’re giving up on significant optimization potential.) If so, there would need to be a way for user code to hook into the contract system, because the pointee may be something other than a single valid instance of T, e.g. for Vec it depends on the len field.

    • I suppose the hook would be a trait that asks a container to walk its contents and somehow indicate types of, and pointers to, all contained values. …That sounds a lot like the same functionality required for tracing GC!
    • But it also seems more intrusive than what should be strictly necessary. With noalias, you can say “if someone loads a pointer from this data structure, it’s UB for someone else to mutate it”, without actually having to know whether there is a pointer or where. But it’s hard to check something like that.
  • It seems like we haven’t gotten any further towards resolving the tension between performance and understandability illustrated in Niko’s original ‘Tootsie Pop’ proposal from last year. Your swap example is similar to Niko’s split-at-mut-via-duplication, which is why you propose making “functions containing unsafe blocks” the boundary for increased permissiveness - and thus reduced performance. But Niko goes on to provide more examples suggesting that the boundary should be the entire module containing unsafe blocks. Yet that, of course, would be a bitter pill for unsafe coders to swallow, since the whole point of unsafe code is usually to increase performance; and in the followup, he provides an example (get_unchecked) where deoptimizing even at the function boundary would feel unfortunate. And then there’s his third post which suggests maybe abandoning the idea of trusting Rust types, but without any real concrete alternative. Well, except the ‘asserting-conflicting-access model’, but your proposal doesn’t go in that direction.

    Not that I need to summarize the issue for you, since you read and responded to those posts :slight_smile: But I wanted to bring it up as context, since your progress makes it more urgent that we make a decision.

    I’m starting to suspect there may not be any truly satisfying resolution, other than picking the least bad option and supplementing it with ugly compiler knobs, like the function attribute you suggested. Which is unfortunate. But then, bad is relative. Whatever the definition of UB, if it can be reliably tested for, that’ll be a heck of a lot better than what you get with C (where people can’t even decide what the standard means)…


#13

For now, there’s nothing special about Unique. And indeed making it special is hard in this framework as it lacks the type information to do so. I am not yet convinced that this is strictly needed for the optimizations I was shown so far, but I also did not look at them in full detail yet.

Well, one possible avenue that my approach opens is having programmers write explicit validation statements. Also, one idea for get_unchecked is to have different “unsafe levels”, and get_unchecked would be marked as “unsafe but doesnt play games with types”; so validation – and optimization – could still happen.

But yes, there are certainly unsolved problems around here. This seems to be pretty much the same as your first point though? Or do you have other optimizations in mind?


#14

I guess it depends what you mean by ‘strictly’? In this code:

let b: Box<SomeStruct> = ...;
foo(b.field);
// intermediate code not using 'b'
bar(b.field);

it would be desirable for the compiler to know b.field couldn’t have changed, assuming it had previously inlined the two calls to Box's Deref impl. Not sure how else you could achieve that, except maybe automatically transforming the code to deref once and reuse the reference? But that transformation might not be safe for arbitrary Deref implementations… am I missing something? :slight_smile:

Not sure what you mean exactly… the points could both be classified as “unsolved problems”, but I see my first point (Unique/containers) as relatively minor, something that could be deferred to a future extension, whereas the second goes to the core of what unsafe code is allowed to do.


#15

It’s not obvious from the post whether you view unsafe code as being unsafe blocks or operations which are only permitted within unsafe blocks. I personally view them as operations which are only permitted within unsafe blocks and the blocks are only syntax which has no impact on code generation. For example, if I have the following code:

let x = 0;

Then changing that to:

let x = unsafe { 0 };

Should have no impact on the semantics of the program.

In the example below:

// Defined elsewhere: unsafe fn ptr::swap_nonoverlapping<T>(x: *mut T, y: *mut T) { ... }

pub fn swap<T>(x: &mut T, y: &mut T) {
    Validate(Acquire, [x, y]);
    let x = x as *mut T;
    let y = y as *mut T;
    unsafe {
        Validate(Release, [x, y]);
        ptr::swap_nonoverlapping(x, y, 1);
    }
}

The Validate(Release, [x, y]); is placed there not because there’s an unsafe block, but because the subsequent operation is unsafe and uses x and y in ways that cannot be validated automatically.

At a higher level, one of the concerns I see is limiting optimizations too broadly because ‘we’ collectively let unsafe code ‘poison’ other code too liberally. I suspect that thinking about unsafe code as operations and not as blocks will make that eventuality less likely.


#16

First of all, Boxes are special in that they incur a write lock just like mutable references do.

However, for your example, that wouldn’t even be needed… if the code doesn’t use b, then of course b is not modified. What am I missing? The interesting case IMHO is calling a function and not passing b to it. That is handled just like mutable references: If you do not pass a box to a function, you keep the write lock, so the box cannot be accessed by the other function.

From my understanding, Unique is what unsafe code authors (want to) use to get the optimizations that they otherwise couldn’t because raw pointer types are too weak. That’s why your two questions seem closely related to me.

Good point! My plan was to go for unsafe blocks, just because that’s simpler. But everything should work just as well if “unnecessary” unsafe blocks do not matter. However, notice that the compiler already warns about unnecessary unsafe blocks.


#17

I don’t like it; it feels too much like tootsie pop, and imo, tootsie pop is not a good way to go forward. I want types to have the exact same guarantees no matter where they are.

At least for the aliasing stuff, I prefer an access model based on a preorder (initial draft):


#18

By “intermediate code not using ‘b’” I meant potentially including function calls, or anything else the compiler can’t analyze, like writes through raw pointers that (if not for special casing) could potentially alias the pointer in the Box. (Anyway, in my example, foo() is executed between the reads.)

First of all, Boxes are special in that they incur a write lock just like mutable references do.

Okay, sounds like a good idea (I didn’t know because it’s not mentioned in your post). Of course, there are other types which could take advantage of the same optimizations, such as Vec, Rc, Arc, etc., and in general it’s best to avoid special-casing standard library types - so eventually it would be good to have a way to customize locking behavior in ‘userland’.


#19

You are right. :slight_smile: I should probably mention this.

My model permits the current function to write to this memory, no matter which pointer is used. So the compiler would still have to prove that all writes that happen inside this function do not alias b. For safe writes that is easy; for raw pointers it is not – my model is conservative here in the sense that &mut and *mut could actually alias if used in the same function.

So you are saying that multiple accesses to a (v: &Vec)[0] should be known to return the same thing even when unknown functions are called in the mean time? That’s tough, it requires teaching the compiler about the fact that Vec “owns” the heap-allocated buffer, so it can remain locked even when we don’t hold any reference into it. This goes beyond controlling when validation intrinsics are added, and into actually controlling validation – in some declarative way so that the optimizer can make use of this.


#20

Yep, and I acknowledge it’s tough. Well, tough to implement in a way that’s coherent between validation and actual optimization. On the optimization side, the pointer field in a Vec<T> is already a Unique<T>; if loads through Unique pointers are given LLVM noalias metadata, I think that’s enough to let LLVM make the optimization in question. (Which AFAIK was part of the original motivation for Unique, given the comment about aliasing guarantees, but isn’t currently implemented, as Unique isn’t a lang item.) But it seems like validation would have to use a totally separate mechanism to indicate the range of addresses to lock, given that that depends on the separate len field.

Also, I guess there are weird semantic corner cases. Consider this code:

let vec: Vec<i32> = vec![1, 2, 3];
let mut foo: i32 = 1;
let out_of_range_index = vec.as_ptr().offset_to(&mut foo as *const i32).unwrap() as usize;
let read1 = *vec.get_unchecked(out_of_range_index); // this reads `foo`
foo = 2;
let read2 = *vec.get_unchecked(out_of_range_index); // ditto

As far as I can tell, under your model, this code is perfectly legal - at least if the Vec contents happen to be located before foo in memory, so that vec.get_unchecked(out_of_range_index) doesn’t wrap around the address space. Even if the Vec contents were write locked, that wouldn’t cause any conflict with accesses to a different memory region. But if LLVM optimized multiple accesses to the same index, it could coalesce read1 and read2 into one read, even though the value changed in between.

Then again, that isn’t just an issue for Vec, but any kind of array, including fixed-length arrays, which I’d assume your proposal already covers. Yet it would be highly desirable for Rust’s semantics to allow taking advantage of LLVM’s existing noalias functionality. Perhaps that code would have aliasing assumptions disabled due to using unsafe? Or perhaps it should just be independently considered UB to index a slice out of bounds (even using get_unchecked), regardless of aliasing?


#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?