Manual does not define "data reached through a shared reference".

[mahkoh]

The manual uses the expression "data reached through a shared reference" but does not define it. In the following code, is x reached through a shared reference?

pub unsafe fn a() -> u8 {
    let mut x = 11;
    b(&x as *const u8 as *mut u8);
    x
}

unsafe fn b(x: *mut u8) {
    *x = 22;
}

[steveklabnik]

/cc @rust-lang/lang

[arielb1]

Wow. This looks like a big issue in my model of aliasing, but maybe it is not so scary.

The problem here is that we want locals to be essentially "always borrowed by the containing function", and IIRC we already perform optimizations that use that (so your code should probably be UB). On the other hand, we do need to have some way of converting mutable references to raw pointers and back again.

I think that is the reason why @thestinger wanted an access-based, rather than an instant-death-based, aliasing model. An access-based aliasing model basically says that a valid reference that is dereferenced and used must not be incompatibly accessed - by raw pointers, other mutable references, modification of the page table, DMA by random peripherals, etc. - for its entire live lifetime. An instant-death-based model is similar but does not include the "that is dereferenced and used" part.

LLVM also has some fancy rules on pointer comparisons, but we can't feasibly support them as we allow taking the addresses of arbitrary things in safe code.

The problem with the access-based model is that it is problematic with "spurious" accesses (e.g. lifting accesses out of a loop), so we probably need some synthesis of the models - maybe using instant-death in functions without unsafe blocks and access-based in functions with, or maybe having some "undefined value" sort of semantics (related question: if I have a &mut reference laying around, am I allowed to munmap a hole within it?).

A few examples for the mutable-references-to-raw-pointers-and-back-again issue, for exposition::

fn f(&self) -> &Self { self }
fn f_mut_unsure<'s>(&'s mut self) -> &'s mut Self {
    let ret = unsafe { transmute::<&Self, &'s mut Self>(self.f()) };
    ret // β-expansion should have no effect
}
fn f_mut_should_work<'s>(&'s mut self) -> &'s mut Self {
    let ret = unsafe { &mut *(self.f() as *const Self as *mut Self) };
    ret // β-expansion should have no effect
}

There are basically 2 aliasing issues there:

• In both cases, self is only borrowed within the unsafe block, as there is nothing that would make the borrow any longer. Therefore, on the second line both ret and self are live mutable pointers to the same place.
• In the first case only, the reborrow of self would be another alias, alive just after the return from transmute. This is what is linted against.

Under "instant death" rules, both are UB, so we can't have that. Under the access-based rules, both are fine. We had a proposal flying around that &-references use instant death and &mut use some variant of access-based, which would make the first UB and the second safe.

[arielb1]

Of course the reason we want some kind of softer rules for &mut is because unsafe code can "hand-reborrow" these sorts of references, and then we are have to guess about the lifetime of the intended hand-reborrow.

[arielb1]

Technically, a more explicit version of the above would be

fn f_mut_pedantic<'s>(&'s mut self) -> &'s mut Self {
    let captured_self = self as *mut Self;
    unsafe { &mut *((*captured_self).f() as *const Self as *mut Self) }
}

which inactivates self, but I would hate to make it necessary (you can use a transmute to replace some of the cast dance).

[aturon]

cc @RalfJung

[RalfJung]

The problem here is that we want locals to be essentially "always borrowed by the containing function", and IIRC we already perform optimizations that use that (so your code should probably be UB).

Which optimizations would/could that be?

I don't think I'm entirely understanding the significance of choosing an "aliasing model", or actually what an "aliasing model" is. I suppose it is related to UnsafeCell being the only defined way to convert a shared borrow to a mutable one? At least, the part of the language reference this issue is about also mentions UnsafeCell.

Disclaimer: So far, the LLVM noalias annotation and the special case of UnsafeCell are out of scope of my formal development. I did not give much thought to how to formally model "UB through interior mutability outside of UnsafeCell", and what it would take to prove absence of that UB. The fact that noalias is as poorly understood as C's restrict (right now, I don't know of anybody who has a real idea what it could formally mean) doesn't help.

[arielb1]

@RalfJung

The aliasing rules basically say that the compiler can assume that nobody is modifying its memory behind its back (this also includes calls to external functions and the compiler's own pointer writes). This is important for optimizations like copy elimination and store-to-load forwarding. For example, if we have

#[derive(Debug,Copy,Clone)]
struct Foo {
    bar: Bar
}
#[derive(Debug,Copy,Clone)]
struct Bar {
    // lots of data
}
fn doit() -> u32 {
    let foo = Foo { bar: make_bar() };
    debug!("{}", &foo);
    match foo {
        Foo { bar } => frobnicate(&mut bar)
    };
}

In a case like this, we would like to make foo.bar and bar point to the same place (rather than physically moving foo to bar). However, if debug!(...) ends up storing the address of foo in a global variable, this would be problematic because frobnicate could access the original foo along with the bar.

[RalfJung]

Thanks for the example! I suppose at some point I will have to mask for more examples of copy elimination and store-to-load forwarding, just to get an idea what it would take to formally justify these transformations.

In this case however, I am puzzle. Please excuse me being so slow ;-) .
If debug stored the &foo anywhere, how would that in any way help frobnicate, considering that the lifetime of this reference ends on the semicolon after debug!?

[arielb1]

@RalfJung

Because we want to treat pointers as "just integers", they don't have a lifetime associated with them if you do things like convert them to a raw pointer and back. This is required for f_mut to work.

[RalfJung]

What is f_mut?

The pointer passed to debug! had a lifetime associated with it.
This means debug has the permission to use that pointer for the duration of that lifetime. Of course it can convert it to a raw pointer, but it cannot convert it back to a shared reference with a larger lifetime. That piece of unsafe code would be severely wrong, because the caller may long since have handed a mutable reference to someone else (after the end of the lifetime of the shared reference).

My approach to checking validity of unsafe code is not at all about aliasing, so I don't have to think about how pointers are represented here. (Also, I am pretty sure that unsafe Rust cannot pretend pointers are just integers, because that's not what LLVM does. See https://internals.rust-lang.org/t/comparing-dangling-pointers/3019.)
Instead, I think about the permissions a piece of code has, and whether these permissions justify the actions taken by the code. For example, a shared reference with lifetime 'a (to something that is Copy) carries with it the permission to read from that pointer as long as lifetime 'a lasts. After the end of 'a, that permission is entirely useless and does not grant the right to perform any action. Converting a shared reference to a raw pointer does not actually do anything, so there's no permission required to do that, but converting it back to a shared reference requires the code to somehow cough up the permissions that back a shared reference - and debug! cannot possibly have that permission.

There is some relation to aliasing, of course. In particular, permissions are passed around in a linear way, i.e., they cannot be duplicated. The permission associated with a mutable reference is such that it is impossible for anyone else to have the same permission (or the "shared reference" permission) for the same location. From having the "mutable reference" permission for pointer p it follows that no pointer q for which someone else has any "reference" permission can alias p. But this is a consequence of permissions held by separate parties being disjoint, it is not the fundamental building block of how I think about references. I'd like to understand how the "aliasing-based" approach works, in particular how the compiler uses it to justify certain transformations, to make sure that these assumptions are actually backed by the permissions I associated with various types.

[arielb1]

@RalfJung

I was quite convinced that all raw pointers to the same address are pretty much equivalent.

[arielb1]

Maybe a model with equal raw pointers being equivalent does not allow desirable optimizations so we need a different one.

[arielb1]

What is f_mut?

One of the functions from the previous example, say:

fn f_mut_pedantic<'s>(&'s mut self) -> &'s mut Self {
    let captured_self = self as *mut Self;
    unsafe { &mut *(Self::f(&*captured_self) as *const Self as *mut Self) }
}

We basically want them to be defined. This means we can't "precisely" track borrows, at least in functions with unsafe blocks (e.g. in the latter function, self is not borrowed at all).

My approach to checking validity of unsafe code is not at all about aliasing, so I don't have to think about how pointers are represented here.

We must be using different definitions of "aliasing". The definition I (and I think LLVM) uses is that accessed addresses in an object pointed to by a noalias pointers can't be incompatibly accessed during their noalias scope except by pointers derived from that pointer, with "derived from" being rather conservative.

Rust's definition is pretty similar - an accessed field of a reference can't be incompatibly accessed while the reference is active (that's it, live and not-incompatibly-borrowed).

The problem with only having noalias is that it does not allow misoptimizing cases like the OP (in C lingo, a variable read via a scanf can now be aliased by everything). LLVM uses nocapture to account for that, which makes the relevant argument become indeterminate after the call. Rust can't afford to emit that because that would require having integers become indeterminate.

Instead, in Rust I think we should say that locals are basically implicitly borrowed by the owning function (they are already treated as such by the borrow checker/safety proof) which would also allow for this kind of reasoning.

Of course it can convert it to a raw pointer, but it cannot convert it back to a shared reference with a larger lifetime. That piece of unsafe code would be severely wrong, because the caller may long since have handed a mutable reference to someone else (after the end of the lifetime of the shared reference).

Instead, I think about the permissions a piece of code has, and whether these permissions justify the actions taken by the code.

That is not the way we decided to go about with unsafe Rust. We try not to have a hardcoded notion of "permissions" - people come up with pretty exotic ways to split array indices. There is some system of permissions that gives safe Rust its safety proof, but unsafe code is free to use a different system without risking UB. And even if that system is incompatible with the real one (e.g. an unrestricted "write-what-where" primitive, or a safe transmute_lifetime) that would only be unsafe (be a bad practice), but not UB unless it is actually used to break some rules.

[RalfJung]

I was quite convinced that all raw pointers to the same address are pretty much equivalent.

I am not sure what you mean by "equivalent" here. Permissions are entirely independent of the actual values processed on the machine, so one function could work on a raw pointer with some permissions, and another function could work on the same raw pointer and have no or different permissions. Permissions are associated with types, and the raw pointer type carries no permission. Of course, unsafe functions can always declare that they want more (or less, or different) permissions than what the types promise.
I also don't understand how this relates to my post. Sorry I'm so slow on this here, we seem to have very different trains of thought.

That is not the way we decided to go about with unsafe Rust. We try not to have a hardcoded notion of "permissions" - people come up with pretty exotic ways to split array indices. There is some system of permissions that gives safe Rust its safety proof, but unsafe code is free to use a different system without risking UB. And even if that system is incompatible with the real one (e.g. an unrestricted "write-what-where" primitive, or a safe transmute_lifetime) that would only be unsafe (be a bad practice), but not UB unless it is actually used to break some rules.

There has to be some coherent notion of permissions associated with the basic Rust types that is common to all code. This is a necessary condition for soundness. After all, we'd like to take all of these safely encapsulated, but unsafely implemented pieces of Rust and use them in the same program. This is only possible if they all agree on what the basic types mean, which permissions they grant.
Unsafe code, on the other hand, is free to do whatever it wants. It doesn't have to follow any existing permission scheme, if there is no interest in a safe abstraction.

Of course, the permission associated with shared borrows will be a very flexible one, mirroring the fact that programs have lots of flexibility what they do with their shared borrows - just think of RefCell.
What exactly are you referring to when you refer to "splitting array indices"? The permission associated with an array will consist of all the individual permissions for its elements. And of course, it is possible to partition this array arbitrarily, and split the array permission accordingly - as long as those individual partitions are all pairwise disjoint. This is something that separation logic does automatically for us.

fn f_mut_pedantic<'s>(&'s mut self) -> &'s mut Self {
    let captured_self = self as *mut Self;
    unsafe { &mut *((*captured_self).f() as *const Self as *mut Self) }
}

We basically want them to be defined. This means we can't "precisely" track borrows, at least in functions with unsafe blocks (e.g. in the latter function, self is not borrowed at all).

This function looks fairly harmless to me. All these pointer casts do not actually do anything, in the end, all that happens here is that f is called. f_mut_pedantic takes something of type &mut Self as argument, so it can do anything you can do with a mutable borrow - including re-borrowing it as a shorter shared borrow, passing that shared borrow to f. We know that f just returns its argument, so we know it returns the shared-borrow-permission for s, and we can end the re-borrow, re-obtain our mutable borrow, and be happy.
Or did you say that this function should be safe for any f? That would be rather surprising... I think we'd need some kind of parametricity argument saying that f has to return its argument. And I don't think that would survive specialization...

Of course, the proof sketch above entirely ignores the fact that Rust adds noalias annotations to arguments. Until someone formally understands what noalias is, there's not much we can do there. We probably would not like to make Rust's semantics depend on the precise nuances of noalias anyway, since (I assume) it's something of a beast.
So far it was my understanding that what Rust actually wants to enforce is something like "there is no interior mutability outside of UnsafeCell". From this it should then follow that the noalias annotation is correct. In f_mut_pedantic above, we actually start with a mutable borrow, so we do have the right to mutate it. We know the function body of f, so we can prove manually that whatever permissions we have are good enough for f, so we should be fine.

In particular, I noticed that f_mut_pedantic actually does contain a & <something>, a shared borrow starts - it's the implicit borrowing happening when f is called. Slightly de-sugared, the function looks as follows:

fn f_mut_pedantic<'s>(&'s mut self) -> &'s mut Self {
    let captured_self = self as *mut Self;
    unsafe { &mut *((&*captured_self).f() as *const Self as *mut Self) }
}

So, there actually is a clear point where "freezing" starts. (I think of there being explicit machine instructions to freeze and unfreeze a block of memory. They would be called whenever a shared borrow starts or ends, which should be statically known. Then whenever we write to a location, we can trigger UB if it is frozen. This explains why you can't just transmute a shared borrow to a mutable one, even in unsafe code. This freezing would of course not happen for UnsafeCell.)
The freezing would end when the lifetime of the shared borrow ends, which is right after the call to ´f`. So, I think this function is fine in my view of the world.

An interesting question here may be - and maybe that's what some of your other examples are about - is what would happen if there is no explicit &, if the shared borrow starts with some casts instead of an actual borrow with a proper lifetime. Then there would be no "freeze" instruction emitted, and we may wonder whether f is safe to call, since it may assume that its argument is frozen. No sure if anyone cal follow me here... I'll have to think more about this, but right now I am struggling with more fundamental problems in my formal development ;-)

We must be using different definitions of "aliasing". The definition I (and I think LLVM) uses is that accessed addresses in an object pointed to by a noalias pointers can't be incompatibly accessed during their noalias scope except by pointers derived from that pointer, with "derived from" being rather conservative.

Rust's definition is pretty similar - an accessed field of a reference can't be incompatibly accessed while the reference is active (that's it, live and not-incompatibly-borrowed).

Well, unfortunately I have no idea how to formally capture the notion of aliasing you are using here. As far as I know, nobody has figure out what noalias actually means in an operational semantics. So while these intuitions are nice, they don't really help me.
By "aliasing" above, I meant "the pointers are equal". That's why this question is related to how pointers are represented as bits.

The problem with only having noalias is that it does not allow misoptimizing cases like the OP (in C lingo, a variable read via a scanf can now be aliased by everything). LLVM uses nocapture to account for that, which makes the relevant argument become indeterminate after the call. Rust can't afford to emit that because that would require having integers become indeterminate.

Instead, in Rust I think we should say that locals are basically implicitly borrowed by the owning function (they are already treated as such by the borrow checker/safety proof) which would also allow for this kind of reasoning.

How does the OP's code relate to scanf? And which arguments of scanf become indeterminate? Also, in unsafe Rust, pretty much anything already can become indeterminate. Or are you saying taht this could come up in safe Rust? Sorry, you entirely lost me here.

Also, regarding scanf, does this mean that if an LLVM program writes a pointer value to a file, then reads it back, and then uses the pointer it read (under the guarantee that it did not change), that this would not be a valid pointer to be used? Is that what nocapture makes happen?

[RalfJung]

Ah yes, now that I realized you may be talking about interior mutability and how to allow it only within UnafeCell - how to coherently make mutation through a pointer derived from a shared borrow UB - I think I can follow your code examples much better ;-) . All the talking about "aliasing" somehow didn't do it for me.
Btw, I heard people saying that "Transmuting a shared borrow to a mutable borrow is UB". Is it really the cast that you consider UB, or is it using the resulting pointer to perform mutation? I can't see how UB could arise just from the cast itself, no matter which annotations you emit to LLVM.

So, coming to your other two examples:

fn f_mut_unsure<'s>(&'s mut self) -> &'s mut Self {
    let ret = unsafe { transmute::<&Self, &'s mut Self>(self.f()) };
    ret // β-expansion should have no effect
}
fn f_mut_should_work<'s>(&'s mut self) -> &'s mut Self {
    let ret = unsafe { &mut *(self.f() as *const Self as *mut Self) };
    ret // β-expansion should have no effect
}

Putting my "freeze/unfreeze" glasses on (I have no idea if they make any sense, but it's the only operational take I was able to get on this so far), my question is where these (virtual) freeze and unfreeze instructions are emitted. I think both functions are kind of the same here. In both functions, the self argument to f is obtained by casting the self: &mut Self to &Self (and this is a regular cast, the Rust compiler sees this happen - it's not a transmute). Now the crucial question is, which lifetime does the borrow passed to f have.

• If we really just have a downcast of the mutability here, then the argument to f has the same lifetime as the argument to f_mut. That would be rather bad, because we want to up-cast to a mutable borrow again later.
• So we better make sure that the compiler actually determines a new lifetime for the cast-down self. If it does, then that lifetime should turn out to be just the call to f, so that self is unfrozen immediately. Then both functions would be safe.

This one, however, would not:

fn f_mut_bad<'s>(&'s mut self) -> &'s mut Self {
    let ret = unsafe { transmute::<&'s Self, &'s mut Self>(self.f()) };
    ret // β-expansion should have no effect
}

Notice that this forces the lifetime of f's argument to be 's, which means that self has to be frozen for the rest of 's - which is not even something we can make happen, because 's may be much longer than the call to f_mut_bad.

And then there is the functions that use casts to obtain the argument of f...

fn unsafe cast_mut_away<T>(x: &mut T) -> &T { transmute(x) } // make sure transmute does not change the lifetime
fn f_mut_dunno<'s>(&'s mut self) -> &'s mut Self {
    let local = &mut *self; // just to get a local re-borrow with a lifetime shorter than the function body
    unsafe { &mut *(cast_mut_away(local).f() as *const Self as *mut Self) }
}

The argument to f should have a short lifetime, so that's fine, but there's not actually a shared borrow starting anywhere, so the memory never got frozen. Is that bad? f assumes the memory is frozen, so it won't do anything that could mutate, so it should not care that memory is not frozen. The only guarantee we ever need is that if we have a &mut (or if we own something), then it is not frozen. Maybe. I am not sure.
Of course, then fn f_mut_bad could also be entirely fine, if there are not actually any "freeze" instructions emitted. It's not like I have any idea what the concrete rules for emitting these instructions would be...

@arielb1, how do these functions look to you?

Coming back to the OP,

pub unsafe fn a() -> u8 {
    let mut x = 11;
    b(&x as *const u8 as *mut u8);
    x
}

unsafe fn b(x: *mut u8) {
    *x = 22;
}

My central question here would be, what is the lifetime of the borrow created at &x? It is entirely unconstrained, so it could last for no time at all. Then memory would be unfrozen before b is called, and this code should be fine.
Which optimizations did you envision that could make above code UB?

[arielb1]

@RalfJung

There has to be some coherent notion of permissions associated with the basic Rust types that is common to all code. This is a necessary condition for soundness.
Of course, the permission associated with shared borrows will be a very flexible one, mirroring the fact that programs have lots of flexibility what they do with their shared borrows - just think of RefCell.

I think that you are missing the point about the difference between UB and the Safety Proof. These are quite different things.

UB is the set of things that rustc/LLVM is allowed to assume not to happen. Invoking UB, even in unsafe code, gives rustc/LLVM a Carte Blanche to rewrite your code - just the same as C.

Unlike C, Rust (at least in theory) has a safety proof. The safety proof says that as long as all unsafe code in the program behaves according to some rules, then any additional safe code can't cause UB. It is perfectly fine to have a program that plays loose with the safety proof - for example, if you wrap a buggy C library with a safe interface, then calling it with the appropriate arguments will cause it to execute some rather arbitrary code, which is obviously UB. However, if, at run-time, the library is not called with these malformed arguments, no UB is involved.

The rules the Safety Proof demands on unsafe code are purely behavioural, which means that unsafe code may rely on arbitrarily complex predicates in order to satisfy them (including the body of some "trusted" safe functions).

The rules of UB are basically "syntax-directed", but are evaluated at run-time. The question of whether a program execution-trace invokes UB should be easily decidable (and require no proof or "ghost" permissions not apparent in the code).

Also, regarding scanf, does this mean that if an LLVM program writes a pointer value to a file, then reads it back, and then uses the pointer it read (under the guarantee that it did not change), that this would not be a valid pointer to be used? Is that what nocapture makes happen?

That is basically correct, but I am quite sure that LLVM does not emit nocapture on the real scanf (basically for this reason).

[arielb1]

@RalfJung

Now the crucial question is, which lifetime does the borrow passed to f have.

Rust's lifetime inference always infers the minimum lifetime possible (of course, the semantics only "run" on fully elaborated code) so we should be fine. We agree on f_mut_bad.

The problem with f_mut_should_work etc. is that an active &mut self pointer can also be basically treated as freezing the pointee except for direct modifications (f_mut_pedantic ensures that the pointer is disposed of properly) - that should not be a problem in these cases because the pointers are not dereferenced while they are simultaneously active.

fn a is unsafe under the "parent-function-has-borrow" rules (which we do rely on) because it does not do anything about the parent's active borrow of the local x (if it was an &mut, it could be argued that the borrow's duration should be extended to not annoy unsafe code, but a &-borrow does not affect the immutable part of the parent's borrow).

About f_mut_pedantic: we must have had different versions of the "pointer permission bits" model: I (and @mahkoh) was quite sure that taking a short borrow limits the permission bits to the duration of that borrow.

[RalfJung]

I think that you are missing the point about the difference between UB and the Safety Proof. These are quite different things.
[snip]
The rules of UB are basically "syntax-directed", but are evaluated at run-time.

I see. There is of course a relation between the two, since the safety proof has to show that there is no UB. But I was probably too focused on how to prove absence of UB - indeed for the "no mutation through a shared reference" part, even defining UB is an open problem. (The same goes for "mutable references and pointers derived from them do not alias", btw.)

Btw, you mentioned the LLVM notion of a "derived pointer" above. I tried to find a definition of that for LLVM, but could not find anything like it. Does a pointer loaded from memory through another pointer count as "derived"? The LLVM docs http://llvm.org/docs/LangRef.html#noalias-and-alias-scope-metadata only explain noalias in relation to an alias.scope, as metadata on an expression. Rust uses noalias as annotation on the type, which I can't even find mentioned in the LLVM language reference.

The question of whether a program execution-trace invokes UB should be easily decidable (and require no proof or "ghost" permissions not apparent in the code).

I don't think this can be done without adding any ghost state - though that ghost state would be somewhat different from the kind of permissions I mentioned earlier. For example, some the C rules concerning address arithmetic also apply in unsafe Rust; to explain them, our model of the memory cannot be just "mapping numbers to bytes". And I think the same goes for "no mutation through a shared reference, except for UnsafeCell" - there has to be some tracking somewhere whether a particular piece of memory is allowed to be mutated right now, so that we can assign UB if we do not want to allow mutation.

That's what I had in mind with my "freezing" proposal: Imagine every location in memory has an additional bit, "frozen", such that writing to a frozen location is UB. We could then imagine having explicit operations that freeze and unfreeze memory, which are called whenever a shared borrow starts or ends. When a function has arguments that are shared references, it would start by asserting that they are frozen - again invoking UB if they are not. This would then justify re-ordering reads from that location.
Unfortunately, this would not be good enough to justify re-ordering reads around a function call - since the function we call could unfreeze memory, change it, and freeze it again. Some extra tracking could be added to compensate for this, like counting the total number of freezes of a location (sth. like a version number), and checking (within a function) that this does not change.

I think ultimately we will need a model that actually uses some state in the memory to track things like this. The trouble with the aliasing-based models I saw so far is that they involve somehow looking at all the pointers that exist in all functions, and that are not borrowed away. (Notice that this, too, requires some "operational effect" associated with borrows starting and ending, visible on the machine that detects UB.) I don't like looking at other functions' state, or somehow having a global register of "all pointers that exist", and I think that would be rather hard to formally define. You mention "access-based" vs. "instant-death based" models above; I definitely think that access-based should be preferred. Having UB just from certain unused pointer values lying around is fairly surprising - and an access-based model lends itself much more natural to some extra tracking happening in the global memory, for every location, with checks being performed on every access. More checks could be easily added if we want certain guarantees even for unused pointers, like the "assert this memory is frozen" I suggested above.

The problem with f_mut_should_work etc. is that an active &mut self pointer can also be basically treated as freezing the pointee except for direct modifications (f_mut_pedantic ensures that the pointer is disposed of properly) - that should not be a problem in these cases because the pointers are not dereferenced while they are simultaneously active.

You mean, having a &mut guarantees that if we don't write through this pointer, then nobody can change that memory? Yes, that's also something that somehow needs to be encoded operationally. I don't have any bright ideas for this yet. But in all the examples you brought up, the &mut self is given up before f is called (transmute consumes its argument), so its not only that the pointer is not used, it cannot be used.
Or are you talking about the return value? In both cases, the lifetime used for f is unconstrained, so it could be said to end before the cast to &mut happens.

More in general though... maybe the "freezing with a version number" can help. We could check, when a function starts, that &mut arguments are frozen, and record the version numbers. When we perform a mutation, we check the version number and unfreeze, mutate, and freeze again with the next version number. Before the function returns, we check the version number. This way, we could detect if anybody else modifies the memory.
Thinking about it, we wouldn't even need a "freeze" flag, just a write counter. We record the write counter at the beginning of every function, and check it at the end, to verify that no unexpected writes have happened. Does this make any sense?

Btw, I noticed that Rust only emits noalias for function arguments, but not for borrows created locally. For example, in

static zz: i32 = 13;
fn foo(x: &i32, y: &i32) -> i32 { let z = &zz; *z + *x + *y }

I could not find any annotation for z. That's why I only talked about beginning and end of functions above, but of course, the same check should happen immediately after a local (re-borrow) and when that (re-)borrow ends.

[arielb1]

I don't think this can be done without adding any ghost state - though that ghost state would be somewhat different from the kind of permissions I mentioned earlier.

Permissions on pointers are not really going to work with FFI, so they are a non-starter. I suppose that the "freezing" of & can be treated as ghost states on memory, but I am used to think of it as universally-quantified relations on memory accesses (but that should be mostly equivalent).

But in all the examples you brought up, the &mut self is given up before f is called (transmute consumes its argument)

self will reborrow itself rather than be consumed, so this won't work.

Anyway, in my view, an active (I need to decide on terminology: live vs. active) &mut is also basically a freeze, except that
a) the memory can be accessed via the relevant active &mut, ignoring the freeze.
b) the memory can't be read from via any other pointer (of course, control flow effects, incl. unwinding, can unexpectedly terminate your borrow and expose that memory, but that is another issue).
c) the memory is not frozen if the &mut is inactive (mutably borrowed or dropped). This is slightly complicated that it is in fact possible for an &mut borrow to be active except for some subobjects (1). Note that an &mut can also be borrowed immutably and frozen.

One useful consequence of this, is that if some &mut is inactive, but you know an active &mut pointer to some subobject of it, you can be sure that the subobject is not poked with except through that pointer, even if the parent is inactive.

Maybe this can be modeled as &mut references freezing the relevant memory using a capability, and being able to use that capability to safely access it.

(1)
For example, you can have

fn traverse(l: &mut MyList)
{
    let mut cur = l;
    loop {
        if let &mut MyList::Cons(42, _) = cur {
            break;
        }
        cur = match {cur} {
            &mut MyList::Nil => return,
            &mut MyList::Cons(_, ref mut l) => &mut *l
        }
    }
    // here `l` is active, except for some unknown child of `cur`
    if let &mut MyList::Cons(ref mut a, _) = cur {
        *a += 1;
    }
}

[pnkfelix]

cc rust-lang/rfcs#1447

[RalfJung]

But in all the examples you brought up, the &mut self is given up before f is called (transmute consumes its argument)

self will reborrow itself rather than be consumed, so this won't work.

For what lifetime will it be considered reborrowed, when it is transmuted?
I assume that casting to a *mut does consume the reference. Usually reborrows occur because the compiler can reasonably infer a shorter and still non-surprising lifetime for a function argument, i.e. in

fn bar(x: &mut i32) { ... }
fn foo(x: &mut i32) { bar(x); bar(x); }

it infers the lifetime of the calls to bar for the argument type that's actually used when bar is called. If the same happens to transmute, the compiler could literally pick any shorter lifetime, so using transmute to turn a &mut into a *mut would actually be very different from using a cast.

// here l is active, except for some unknown child of cur

Why should l be active there? l has been moved out of in the first line, so it should be inactive. Only cur remains active.

[arielb1]

Why should l be active there? l has been moved out of in the first line, so it should be inactive. Only cur remains active.

l has been reborrowed, not moved (apparently, rustc even reborrows on raw pointer casts, which would make even my pedantic version not work). rustc reborrows at pretty much every opportunity - apparently even on raw pointer casts, breaking my pedantic example - unless you force it to move using a block {cur}.

We probably need some way to make rustc not reborrow like that.

[nikomatsakis]

I think that whatever rules we settle on when it comes to & to * casting cannot, probably, be based on the lifetime of the & pointer being cast. This is partly because of reborrows but also because in general when we go from & to *, we lose track of the pointer, and hence can't really have a prayer of inference coming up with a long enough lifetime (in fact, it's often very handy that the lifetime is so short). It might be that they can be based on the "upper bound" of the lifetime of that & pointer though.

[arielb1]

@nikomatsakis

The problem is that one of the points of &mut is that you can, in fact, suspend your ownership of them only for a short period of time.

[RalfJung]

l has been reborrowed, not moved (apparently, rustc even reborrows on raw pointer casts, which would make even my pedantic version not work).

But cur is alive until after the line where you had your comment, so even if it has been reborrowed, it is dead until the reborrow ends. Which will be when the function ends.

@nikomatsakis I am not entirely following you... but if I understand it correctly that the compiler assigns minimal lifetimes and always reborrows, then this should be sound (and rustc says it is... which leaves me slightly shocked^^):

fn foo(x: &mut T) {
  let y = x as *mut _; // reborrows x for the shortest possible lifetime, which is this single statement
  let z = x as *mut _; // does the same again
}

In other words, the compiler would actually not see any ownership transfer happening when casting to a raw pointer. This is somewhat consistent (after all, the compiler assigns no ownrship to mutable borrows), but I think it is also dangerous and usually not what people "mean". Above, you'd have to be very careful what you do with x, even in safe code. If the cast would consume x, the compiler would tell you that you cannot use it any more. I think this is desirable. The old behavior can still be encoded, if people want it...

fn foo(x: &mut T) {
  let y = { let x' = x; x' as *mut _ };
  let z = { let x' = x; x' as *mut _ }
}

Now the reborrow happens in the assignment to x', so this is slightly more explicit.

However, I think there's not just "linting" problems with the current behavior:
Right now, you can write

fn foo(x: &mut i32) {
  let y = x as *mut _;
  unsafe { *y = 42; }
}

and I assume this code is intended to have defined behavior. But a model that actually ensures that mutable borrows are the only way to write to the data they point to, would assign UB to the program above: At the beginning of the unsafe block, x is an active mutable borrow, and we do not use x for the rest of this function. Hence we can assert that whatever x points to does not change. But that's not the case...

This code is probably okay for LLVM because it will consider y to be derived from x. But it certainly violates the idea of in-scope active mutable pointers always being unique.

[nikomatsakis]

@arielb1 @RalfJung

My point is that I believe it should, in some cases, be legal to transmute/cast an &'a mut T to a *mut T and then use the pointer for a span of time longer than 'a. I don't mean arbitrarily long, either, but I think we need some rules that govern how far a *mut can escape and I don't think those rules can be strictly tied to the lifetime of the source pointer (though they are also not independent from that lifetime). I think they should probably be tied to bigger, coarser scopes that are more easily defined.

Put another way, I don't want the results of what is legal to have anything to do with what is inferred by the compiler within a fn definition. I want them to be based on the formal types of the arguments (which are explicitly written) and some kind of "common sense" reasoning. This may require the compiler to be more conservative than it would otherwise be in functions whose bodies contain coercions from &mut to *mut (hopefully, though, we can contain the effects of those coercions to the fn itself, so that callers don't have to care if their callees define coercions -- in fact, I think that this is the primary challenge of the memory model: determining when, exactly, callers should care about the callees do).

For example, in this snippet from @RalfJung:

fn foo(x: &mut T) {
  let y = x as *mut _; // reborrows x for the shortest possible lifetime, which is this single statement
  let z = x as *mut _; // does the same again
}

And another related example that @alexcrichton and I discussed a long time back:

fn caller(x: &mut T) {
    caller(x, y); // what lifetime is inferred for the (implicit) coercion? does it cover the call?
}
fn callee(x: *mut T, y: *mut T) {
}

In both these cases, as @RalfJung observed, the compiler will infer an awfully (and unrealistically) short borrow. But clearly the user expects to use the pointers y and z and I think we ought to make that OK.

One can imagine then a rule that says something like this: if the fn body contains a coercion or cast to *mut or an unsafe block, then the compiler must assume that all references are potentially aliased within the fns. This will impair its ability to optimize and reorder code. It does not mean the user is free to do whatever they want: memory still gets freed and so forth in the usual way. But it does mean that the user can use unsafe pointers to "go beyond" borrows, but those uses are on them in terms of avoiding UB.

Anyway, I have to run, so I have no time to cleanup this text just now, and I know that is not a "memory model". It's also coming from a mildly different perspective (what the compiler will do), which in principle ought to be "derived from" the memory model. But of course in practice most memory models are aimed at formalizing what the compiler just does. Hopefully this comment nonetheless helps to elucidate my thinking a bit.

[arielb1]

@nikomatsakis

Luckily, the &mut-not-being-properly-disposed-of problem is function-local in its effect - you can always manually dispose of the reference, so we can fudge the rules in functions that contain unsafe code.

[RalfJung]

I am slightly worried about the part where it seems like we have to detect whether a function perform a borrow-to-ptr-coercion, and then let the entire function behave differently. I think this should be more local to the pointer, like - the moment you coerce a mutable borrow to a raw pointer, until , all aliasing for that particular pointer is fine. But I do agree that this is probably the behavior most people would expect.

Semantically speaking, I don't think "until the end of the function" would be a good boundary. I would prefer something that is more tied to, e.g., the scope of the variable that has been coerced. Incidentally, if the variable is consumed by the coercion, this would pretty much match the "infer the maximal lifetime when coercing".

EDIT: Hm, but you were worried about inferred lifetimes having effect on the validity of code, which I agree Bad (TM). It's just, the function boundary is pretty arbitrary and entirely blurred away by inlining. Plus, there may be mutable borrows that I cast to a raw pointer that genuinely do not live until the end of the function. "aliasing is now legal" would have to be communicated to whoever obtains the borrow when its lifetime ends. As in

fn foobar(x: &mut i32) {
  let zz : *mut _;
  { let y = x; // reborrow for the scope of y
    let z = y as *mut _;
    *z = 15;
    zz = *z;
   }
   // How is the compiler supposed to know that `x` can now alias? Or is thus UB?
   *x = 14;
   *zz = 13;
   *x
}

(Update: fixed typo)
Of course, the data flow from x to y could be arbitrarily complicated and involve code in other crates.

[arielb1]

@RalfJung

Of course, only the mutable reference immediately being cast would stay "semi-active" - if it was a reborrow of some other thing, its parent would return to being active as soon as the reborrow will go out. This also preserves meaning in the presence of inlining.

Though the SEME rules would make it hard to reborrow anything that is not just a parameter. Maybe just take a function being unsafe to fudge the activity of mutable pointers in it, and preserve that kind of fudging during inlining.

I am not sure what is zz in your code above ^ and you seem to have an extra deref (also: unsafe block) but as extract-functioning the block would be obvious UB, this code would also be UB under the first rules and valid if we fudge things.

[RalfJung]

Sorry, I had a typo around the zz, I fixed that.

Of course, only the mutable reference immediately being cast would stay "semi-active" - if it was a reborrow of some other thing, its parent would return to being active as soon as the reborrow will go out. This also preserves meaning in the presence of inlining.

In other words, the cast would completely consume its origin and be a valid pointer - with arbitrary aliasing - for the lifetime of the origin?

Though the SEME rules would make it hard to reborrow anything that is not just a parameter. Maybe just take a function being unsafe to fudge the activity of mutable pointers in it, and preserve that kind of fudging during inlining.

Hu? SEME?
Again, I think doing this based on whether the containing function is unsafe or not (what does that even mean?) is a semantic dead-end. Explaining what is and what is not allowed after inlining is about as hard as just doing it in a modular, local way from the start.

also: unsafe block

Sorry for that^^. I think about this stuff in terms of entirely untyped code that doesn't even want to type-check (because we will eventually prove that it behaves semantically well-typed), and then translate it back to Rust, and sometimes I forget that in Rust I have to explicitly mark some pieces of this ;-)

[nikomatsakis]

On Fri, Jan 15, 2016 at 01:30:15AM -0800, Ralf Jung wrote:

I am slightly worried about the part where it seems like we have to detect whether a function perform a borrow-to-ptr-coercion, and then let the entire function behave differently. I think this should be more local to the pointer, like - the moment you coerce a mutable borrow to a raw pointer, until , all aliasing for that particular pointer is fine. But I do agree that this is probably the behavior most people would expect.

I am open to more restrictive definitions, but I definitely want to find something that is relatively easy for people to grok. I also want to avoid TBAA and other sensitive definitions. I think people should be able to cast freely around between types.

Semantically speaking, I don't think "until the end of the function" would be a good boundary. I would prefer something that is more tied to, e.g., the scope of the variable that has been coerced. Incidentally, if the variable is consumed by the coercion, this would pretty much match the "infer the maximal lifetime when coercing".

Seems plausible. The bottom line for me is that it should be some clear, syntactic boundary -- not the results of lifetime inference!

[arielb1]

SEME

Currently, region inference is can only pick out fairly coarse-grained regions. SEME is an RFC for more finely-grained regions which will make the destroying a mutable pointer more annoying.

In other words, the cast would completely consume its origin and be a valid pointer - with arbitrary aliasing - for the lifetime of the origin?

That sounds like a good solution. It will be a little problematic when as_mut_ptr is used instead of arbitrary casts - maybe just ban these kinds of methods, or have some kind of attribute annotation + lint.

Explaining what is and what is not allowed after inlining is about as hard as just doing it in a modular, local way from the start.

Not really. The "dead areas" of mutable pointers are inferred once, before inlining, and then preserved during inlining. This is no more difficult than preserving type inference.

[steveklabnik]

Interestingly enough, if we run this code in MIRI: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0d8479bc8e9eeb656f08f3b763e80989

error[E0080]: constant evaluation error: borrow being accessed (Alias(None)) does not exist on the borrow stack
 --> src/main.rs:8:5
  |
8 |     *x = 22;
  |     ^^^^^^^ borrow being accessed (Alias(None)) does not exist on the borrow stack
  |
note: inside call to `b` at src/main.rs:3:5
 --> src/main.rs:3:5
  |
3 |     b(&x as *const u8 as *mut u8);
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside call to `a` at src/main.rs:13:21
 --> src/main.rs:13:21
  |
13|         let mut a = a();
  |                     ^^^
  = note: inside call to `main` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:64:34
  = note: inside call to closure at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:53
  = note: inside call to closure at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:293:40
  = note: inside call to `std::panicking::try::do_call::<[closure@DefId(1/1:1780 ~ std[82ff]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panicking.rs:289:5
  = note: inside call to `std::panicking::try::<i32, [closure@DefId(1/1:1780 ~ std[82ff]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe]>` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/panic.rs:388:9
  = note: inside call to `std::panic::catch_unwind::<[closure@DefId(1/1:1780 ~ std[82ff]::rt[0]::lang_start_internal[0]::{{closure}}[0]) 0:&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe], i32>` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:52:25
  = note: inside call to `std::rt::lang_start_internal` at /root/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/src/libstd/rt.rs:64:5
  = note: inside call to `std::rt::lang_start::<()>`

So, there's one answer at least. I'm not going to close this issue just yet, in case someone finds this discussion useful, but I imagine this thread is obsoleted by the unsafe code guidelines, or at least this question should be raised over there.