Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

How are virtual function calls specced? #338

Open
JakobDegen opened this issue May 14, 2022 · 63 comments
Open

How are virtual function calls specced? #338

JakobDegen opened this issue May 14, 2022 · 63 comments

Comments

@JakobDegen
Copy link
Contributor

JakobDegen commented May 14, 2022

To make the question more precise, consider this code:

trait A {
    fn foo(&self, u32) -> i32;
}

fn nameless(r: &dyn A, x: u32) -> i32 {
    (&dyn A)::foo(r, x)
}

What does the spec say happens at the (&dyn A)::foo(r, x) call?

Whatever we choose must be strict enough to disallow inserting an extra println!("AAAAA"); that the user did not write, but also permissive enough to not stabilize the layout of vtables.

This is forked off from #328 .

@JakobDegen
Copy link
Contributor Author

I suggest: Abstract machine devirtualization tables. The r: &dyn A, consists of too parts, p: ptr and metadata: ptr. When calling (&dyn A)::foo(r, x), the metadata is separated out and the AM consults an AM devirtualization table that is unique to (&dyn A)::foo. This table maps metadata values to function pointer with signature fn(ptr, u32) -> i32. Once the function pointer has been retrieved for the given metadata, it is called with the parameters that were passed to (&dyn A)::foo.

Importantly, these devirtualization tables are not located anywhere in AM memory. Compilers can implement this pattern via vtables, justified by the as-if rule. This has the advantage of making the behavior of virtual calls completely explicit, while allowing compilers the full flexibility of implementing their vtables using whatever representation they like. The meaning of the metadata pointer remains 100% implementation defined, to the extent that it would even be correct for the pointer to be dangling (assuming the required functionality could still be implemented).

@chorman0773
Copy link
Contributor

chorman0773 commented May 14, 2022

The way I'd define it is

The metadata produced by unsizing to a pointer to a trait object is an unspecified pointer that identifies the dynamic type of the value that was unsized, and is sufficient to determine the properties of the dynamic type, including its size and alignment requirement, and the functions corresponding to each trait method that can be called on the trait object.

with

The result of calling a trait method on a trait object pointer is the same as calling that trait method on the static value as the type of the unsized value. The behaviour is undefined if the metadata of the trait object pointer does not identify any type or if the data pointed to by the trait object pointer does not satisfy the type identified by the metadata.
[Example: given the following trait definition and trait impl, <i32 as Foo>::foo(&x) and (&x as &dyn Foo).foo() shall be equivalent-expressions:

pub trait Foo{
    fn foo(&self);
}
impl Foo for i32{
    fn foo(&self){println!("Foo");}
}

]

@JakobDegen
Copy link
Contributor Author

Yeah, I believe our definitions are functionally equivalent, except that I consider (maybe unreasonably much) the operational-ness of my definition to be a significant benefit that we should try and retain wherever possible

@chorman0773
Copy link
Contributor

chorman0773 commented May 14, 2022

True - mine is a better prose spec, yours is a better description of the operational semantics (w/o exposing impl-details).

@digama0
Copy link

digama0 commented May 14, 2022

Does the metadata pointer have guaranteed static lifetime? Is it guaranteed to be usize large?

Regarding the difference between Jakob's and Connor's specs: Connor's mentions that it is UB to call <&dyn A>::foo((ptr, metadata)) if metadata is not a dyn metadata pointer ("does not identify any type or if the data pointed to by the trait object pointer does not satisfy the type identified by the metadata"). Operationally, how is this tracked? Is there a provenance specific to dyn metadata? How are types distinguished? (Are we going to have a spec-version of rust-lang/rust#10389?)


My answers to these questions:

  • Yes, the metadata pointer produced by unsizing has static lifetime. Metadata pointers in general are not required to have static lifetime, and calling a dyn function works as long as the metadata pointer is valid (which, like Jake said, does not necessarily entail that the pointer is pointing at allocated memory)

  • The metadata is guaranteed to have the same size as *const () (which is the same as usize; the uptr stuff might rewrite this line later).

  • Each dyn metadata pointer is in its own address domain which has access to zero bytes (so you are not allowed to read directly through it). The pointer tags are stored in the AM devirtualization table as described by Jakob, which also maps the tag to the address of that pointer (the base of the allocation). Calling <&dyn A>::foo((value, metadata), arg) checks that the metadata tag exists in the table and has the correct pointer value (else UB), and then it calls the foo: fn(ptr, u32) -> i32 function pointer stored in the table as foo(value, arg), which can subsequently cause UB if value has the incorrect type.

  • It is not otherwise UB to call a pointer with the incorrect metadata type, unless one of the above mechanisms signals UB. In particular, unsizing, which creates dyn metadata, uses the lifetime-erased type to create the metadata, so punning the lifetimes is explicitly allowed. (Type equality questions don't really appear here because unsizing is not guaranteed to produce the same dyn metadata value even if used on the same type. It simply has to produce some dyn metadata value which is valid to subsequently call with a value of that type.)

@chorman0773
Copy link
Contributor

Operationally, how is this tracked? Is there a provenance specific to dyn metadata?

Presumaby. though it's fun. Mostly it would just spec-in that if you call a &i32 trait method on a &dyn Any, the actual pointee of the dyn Any can't be a u8 because there isn't a full i32 in that u8.

@chorman0773
Copy link
Contributor

Yes, the metadata pointer produced by unsizing has static lifetime. Metadata pointers in general are not required to have static lifetime, and calling a dyn function works as long as the metadata pointer is valid (which, like Jake said, does not necessarily entail that the pointer is pointing at allocated memory)

I'd wonder if there is a benefit to specifying that calls don't care about the dynamic lifetime if, for the purposes of the spec, all operations that can validly produce the metadata pointer produce something with a 'static dynamic lifetime. Of course, with compiler specific knowledge, you could magic up a vtable with less than static lifetime but as you need to know the implementation, that could merely require the compiler "OK"ing the metadata.

@digama0
Copy link

digama0 commented May 14, 2022

That's a fair point. Given that we want to be able to use "anything Rust code could do" as a way to spec unknown functions and FFI, I think we need to add an intrinsic for creating non-static dyn metadata even if there isn't anything in the surface language to invoke it, if only to say "FFI or other unknown calls, or compiler intrinsics, can maybe do this".

@digama0
Copy link

digama0 commented May 14, 2022

Operationally, how is this tracked? Is there a provenance specific to dyn metadata?

Presumaby. though it's fun. Mostly it would just spec-in that if you call a &i32 trait method on a &dyn Any, the actual pointee of the dyn Any can't be a u8 because there isn't a full i32 in that u8.

To be more concrete, let's consider some cases with the following code:

trait Foo {
  fn foo(&self);
}
impl Foo for i32 {
  fn foo(&self) {}
}
impl Foo for u8 {
  fn foo(&self) {}
}

(I will use <A as dyn Trait>::metadata to mean the dyn metadata you obtain by unsizing some value of type A as a &dyn Trait.)

  • Calling <dyn Foo>::foo((&0u8, <i32 as dyn Foo>::metadata)) results in a call to <i32 as dyn Foo>::foo(&0u8), which implicitly transmutes the &0u8 to a &i32. This is immediate UB if the reference is not aligned, but otherwise it is not UB unless the value is read in the function (this one doesn't use the value). This is UB because of retagging, as Jake points out.

  • Calling <dyn Foo>::foo((&0i16, <u8 as dyn Foo>::metadata)) results in a call to <i32 as dyn Foo>::foo(&0i16), again implicitly transmuting the type, which here would be fine and would read the low 8 bits on a little endian system.

  • Calling <dyn Foo>::foo((&0u8, <u8 as dyn Any>::metadata)) is UB, because the devirtualization table for <u8 as dyn Any>::metadata does not contain an entry for <dyn Foo>::foo.


Here's another fun thing: is it legal for the compiler to not create any dyn metadata for ! and consider <! as dyn Any>::metadata to be uninhabited? The only way to make calls into the vtable is using a trait object, which needs a &! or &mut ! even though some things like the size and align don't actually need this data, so it seems like it would be valid to just never create such things. Personally I'm leaning toward requiring that <! as dyn Any>::metadata exists in the same way as non-static dyn metadata: a thing that could possibly exist but for which there is no mechanism in the language to construct them other than implementation-defined things.

@JakobDegen
Copy link
Contributor Author

This is immediate UB if the reference is not aligned, but otherwise it is not UB unless the value is read in the function (this one doesn't use the value).

It is immediate UB anyway, because the &self argument is retagged on function entry. Because of this, I don't think we should be inserting any additional rules regarding the validity requirements; <dyn A>::foo((value, metadata), arg) should have the same exact validity requirements (modulo metadata) as <ActualType>::foo(value, arg).

@JakobDegen
Copy link
Contributor Author

JakobDegen commented May 15, 2022

Regarding the remaining questions: Generally, I agree with Mario. That being said, I would like to clarify something though: I believe that the devirtualization tables should map pointer values to function pointer values. Importantly, this means that the domain is (allocation_id, sb_tag, address) triples. Otherwise we run the risk of allowing code like this:

let d: &dyn A = something();
let (val, metadata): (_, *const ()) = d;
let metadata_new = &mut *(metadata as *mut ()) as *const (); // Reborrow the `metadata` through a `&mut ()`
let d = (val, metadata_new);
d.foo(5);

As soon as we lower virtual function calls to an IR in which there are vtable pointers instead of devirtualization tables, this will read outside of metadata_new's provenance. That seems like a mess. It forces all relevant IRs to choose between having explicit versions of virtual function calls, or having SB information.

With that worked out, specifying the behavior of dyn upcasting is easy: Create a metadata = alloca(0);, which yields a new pointer with the desired uniqueness properties (address is not unique, alloc id and tag is). This metadata is then inserted into the global devirtualization table (never to be removed) and the function pointer it maps to is the appropriate one from the concrete type impl. The obvious value is returned from the expression.

@digama0
Copy link

digama0 commented May 15, 2022

Regarding the remaining questions: I think they can all be answered simultaneously by specifying the behavior of (val: &Concrete) as &dyn A. Before I do that, I would like to clarify something about my previous proposal though. I believe that the devirtualization tables should map pointer values to function pointer values. Importantly, this means that the domain is (allocation_id, sb_tag, address) triples.

  • Are allocation_id and sb_tag not the same thing? I thought we can make one tag do both jobs.
  • In my variation, the table is just taking the allocation_id/sb_tag and asserting the address, instead of taking both. I think there is not much difference, since presumably each tag is only going to have an entry in the table for exactly one address, but if you have some reason to allow for multiple pointer values at the same tag to work please speak up.

Otherwise we run the risk of allowing code like this:

I don't see the issue: Reborrowing creates a new tag, so it would be rejected as a legal metadata value. Or do you want to accept that code?

With that worked out, specifying the behavior of dyn upcasting is easy: Create a metadata = alloca(0);, which yields a new pointer with the desired uniqueness properties (address is not unique, alloc id and tag is). This metadata is then inserted into the global devirtualization table (never to be removed) and the function pointer it maps to is the appropriate one from the concrete type impl. The obvious value is returned from the expression.

Ah, I don't think this one is quite right. I don't think we want to promise that metadata acquired through unsizing is unique or a fresh id, and in fact we might want to promise the opposite. It also looks like another interesting application of NB. I would say that the compiler is allowed to return nondeterministically any metadata value valid for the type and trait (which was already in the map beforehand). It's not entirely clear to me whether the "allocation" of a new entry in the map would be observable, but it seems like a safe bet to not allow such a thing.

Put another way, I think that metadata values should already exist at program start in the same way as function pointer values. (Dyn unsizing has a lot in common with casting fn() {foo} to fn()).

@JakobDegen
Copy link
Contributor Author

Are allocation_id and sb_tag not the same thing? I thought we can make one tag do both jobs.

Ralf had mentioned at some point that they might not be. It seems possible to make them the same thing, but that's off-topic here, so just for safety I'm including both.

Besides that, I think I had misread your original proposal. Re-reading it now, I agree that ours are actually the same, and both correctly disallow the code I posted above

@RalfJung
Copy link
Member

What's wrong with saying that basically what Miri does is the spec? I assume it is the concern I raised about wanting to change vtable layout in the future?

Seeing all this extra complication here, I wonder if we cannot carefully delineate some part of this as being a part of the spec that might change in the future -- like how exactly the fn ptr is determined given the vtable ptr and trait?

@digama0
Copy link

digama0 commented May 15, 2022

I believe the purpose of the complication here is precisely to allow the compiler freedom to do other things, in particular devirtualization. I think it is right that even beyond simply assuming that a vtable pointer is in unspecified layout like a repr(Rust) struct, it can also simply not be at the address it purports to live at - this is an observable property since you could hand-code an offset pointer access to get at the function pointer, and this apparatus allows us to say that accessing vtable data yourself is UB, which is necessary if the table isn't actually there because it was devirtualized but you've hacked together another access of the function manually to fool the compiler's devirtualization analysis.

Seeing all this extra complication here, I wonder if we cannot carefully delineate some part of this as being a part of the spec that might change in the future -- like how exactly the fn ptr is determined given the vtable ptr and trait?

I think the operative question is: is the determination of fn ptr from vtable ptr and trait something that well-defined rust code could do? Assuming it knew the compiler's layout. The thing the Jakob's (and Connor's) models allow you to do is say "no this function is magic and you cannot fake it with rust code" which seems like the maximally conservative choice if we want to consider the possibility of compilers being clever and reading a lot into the structure of virtual calls.

Another thing: you say determination of the "fn ptr" from the vtable ptr, but AFAIK the fn ptr itself is not something you have access to with non-weird rust code: you can only call the function, not observe its location. An explicit (but unspecified) repr for vtables would presumably imply that this fn ptr is accessible, which might limit what a compiler can do with inlining and deleting the function.

What's wrong with saying that basically what Miri does is the spec?

What exactly does Miri do? I assume it just has a concrete vtable layout. One issue with this is that the vtable layout has to match rustc's or else it could miss UB in user code. With this abstract approach, you can "naturally" model vtables directly (i.e. in actual data structures instead of in simulated memory) in Miri and you only need to know spec stuff to write it, which seems like a plus.

@JakobDegen
Copy link
Contributor Author

I actually initially wanted to do something like what Ralf said, where we essentially claim that the AM is parametrized by a vtable shim which accepts the metadata and outputs the function pointer. The problem is that you also have to address the question of what this shim may be - clearly it may not println!("AAAAA");. This requires us to start getting into some details (may access immutable global memory, may not access mutable global memory), and unless there's some trick here that we can use to ensure the function does what its supposed to, I don't know that we're actually reducing complexity.

@digama0
Copy link

digama0 commented May 15, 2022

I wonder whether the talk about dynx Trait affects any of this, since IIUC it basically lets users write the shim code in a library.

@JakobDegen
Copy link
Contributor Author

Ah, I don't think this one is quite right. I don't think we want to promise that metadata acquired through unsizing is unique or a fresh id, and in fact we might want to promise the opposite. It also looks like another interesting application of NB. I would say that the compiler is allowed to return nondeterministically any metadata value valid for the type and trait (which was already in the map beforehand). It's not entirely clear to me whether the "allocation" of a new entry in the map would be observable, but it seems like a safe bet to not allow such a thing.

Yeah, I'm not sure what I was thinking. Completely agreed though, unsizing should attach an existing metadata to the pointer, not create a new one

@RalfJung
Copy link
Member

I believe the purpose of the complication here is precisely to allow the compiler freedom to do other things, in particular devirtualization. I think it is right that even beyond simply assuming that a vtable pointer is in unspecified layout like a repr(Rust) struct, it can also simply not be at the address it purports to live at - this is an observable property since you could hand-code an offset pointer access to get at the function pointer, and this apparatus allows us to say that accessing vtable data yourself is UB, which is necessary if the table isn't actually there because it was devirtualized but you've hacked together another access of the function manually to fool the compiler's devirtualization analysis.

Could you give an example?
My understanding of devirtualization is that it will replace vtable-loaded fn ptrs with constants since it can predict the callee. However if code mucks about with the vtable, that would also interfere with the compiler's ability to figure out which virtual instance a call dispatches to, and thus should be fine. Specifically, vtables are read-only, so the only thing code can do is forge a wide pointer with an "artifical" vtable that it created itself (possibly by copying and modifying a "real" vtable). Devirtualization would never happen for such a pointer, or would it?

What exactly does Miri do? I assume it just has a concrete vtable layout. One issue with this is that the vtable layout has to match rustc's or else it could miss UB in user code.

Yes. In fact the code that generates vtables is shared between Miri and the codegen backends.

@digama0
Copy link

digama0 commented May 17, 2022

I believe the purpose of the complication here is precisely to allow the compiler freedom to do other things, in particular devirtualization. I think it is right that even beyond simply assuming that a vtable pointer is in unspecified layout like a repr(Rust) struct, it can also simply not be at the address it purports to live at - this is an observable property since you could hand-code an offset pointer access to get at the function pointer, and this apparatus allows us to say that accessing vtable data yourself is UB, which is necessary if the table isn't actually there because it was devirtualized but you've hacked together another access of the function manually to fool the compiler's devirtualization analysis.

Could you give an example?

trait Foo {
  fn foo(&self);
}

#[repr(C)]
struct FooVTable<T> {
  drop: unsafe fn(&mut T),
  size: usize,
  align: usize,
  foo_ptr: fn(&T),
}

#[repr(C)]
struct DynFoo<'a, T> {
  data: &'a T,
  vtable: &'a FooVTable<T>,
}

// Safety: I looked at rustc layout stuff and this is totally okay, pinky promise
// (as long as `dynptr` is in fact pointing to a `T`)
unsafe fn undyn<T: Foo>(dynptr: &dyn Foo) -> DynFoo<'_, T> {
  std::mem::transmute(dynptr)
}

impl Foo for i32 {
  fn foo(&self) {
    println!("called i32::foo({self})")
  }
}

fn main() {
  let dynptr: &dyn Foo = &0i32;
  let undyned = unsafe { undyn::<i32>(dynptr) };
  // equivalent to: dynptr.foo()
  (undyned.vtable.foo_ptr)(undyned.data);
}

This is some "perfectly normal" code that takes advantage of unstable (but not UB) layout details in order to call dynptr.foo(). Under your model, this would be defined behavior, and under Jakob's model it would be UB.

The way this interacts with devirtualization is that I would like the compiler to be able to reason:

  • Since dynptr.foo() is never called here (that is, the shim function <dyn Foo as Foo>::foo was definitely never called, which remains true even with the shenanigans), we are licensed to omit it. (This should not be a surprise)
  • Since no function on dyn Foo is called (it is a private trait so we have full visibility into all uses here), in fact we do not need the vtable at all and can stuff the vtable with uninit. (This is false because of the shenanigans: in fact foo_ptr is accessed, and such an optimization will cause a segfault.)
  • We can go one step further and remove the vtable allocation entirely, and replace the vtable pointer with dangling(). This is true even though the undyn function exists and is making use of a &dyn Foo, because it doesn't "do anything" with the value.
  • Even if undyn called foo() we would still be allowed to devirtualize by "constant propagation" since unsizing only occurs for one type so we could forward any method or alignment accesses to the values for i32, and having done that there would be no accesses to the vtable and we could make it dangle as before.

These optimizations are valid in Jakob's model because the *undyned.vtable access is UB. It is true that you can still do some devirtualization in your model, you just have to ensure no shenanigans like this; but I think this is difficult since the transmute could happen somewhere very unobviously related, for example behind some more pointer indirections or across an FFI parameter conversion. Basically you would have to be very conservative and I would guess there are quite a few situations that are devirtualizable with Jakob's model but can't be proven to be devirtualizable with yours.

What exactly does Miri do? I assume it just has a concrete vtable layout.

Yes. In fact the code that generates vtables is shared between Miri and the codegen backends.

I assume you realize that this is problematic re: making a specification which is independent of rustc so that alternate rust implementations can exist.

@bjorn3
Copy link
Member

bjorn3 commented May 17, 2022

I assume you realize that this is problematic re: making a specification which is independent of rustc so that alternate rust implementations can exist.

An alternative rust compiler may choose a different vtable layout and different versions of rustc may choose different vtable layouts. It is just whatever you do miri and the codegen backends need to agree on a single vtable layout for any specific rustc version and thus having miri generate vtables is the best option we have.

@JakobDegen
Copy link
Contributor Author

An alternative rust compiler may choose a different vtable layout and different versions of rustc may choose different vtable layouts. It is just whatever you do miri and the codegen backends need to agree on a single vtable layout for any specific rustc version and thus having miri generate vtables is the best option we have.

Right, clearly for rustc's miri this is the right choice, but the issue of "how do we spec this" still remains. If we allow other implementations to do it differently, what are the rules governing what they may do? Is it really just the layout of the vtable that is allowed to be changed? That seems unnecessarily restrictive, an implementation should be able to add an extra indirection in there if it feels like it.

@RalfJung
Copy link
Member

RalfJung commented May 18, 2022

I assume you realize that this is problematic re: making a specification which is independent of rustc so that alternate rust implementations can exist.

Yeah, same as with repr(Rust) data layouts.

The way this interacts with devirtualization is that I would like the compiler to be able to reason:

That is not what I expected devirtualization to do -- I thought it would be about replacing virtual calls by direct calls, but what you describe sounds quite different?

I had indeed expected your code to be defined if one guessed vtable layout correctly, similar to repr(Rust) types. I was more concerned with people forging fake vtables than people peeking at the (read-only) "real" vtables.

That seems unnecessarily restrictive, an implementation should be able to add an extra indirection in there if it feels like it.

Oh definitely, I would see that as part of the layout.

Basically: to create a vtable, the compiler will return a pointer to some data, backed up by a set of allocations. Mutating any of that is UB (i.e., this is all read-only memory). The compiler also has procedures that, given a vtable, can look up the size and alignment, drop function, or virtual trait function of the type; it guarantees that when generating a vtable for a impl Trait for T, those procedures on the created vtable will produce the expected result.

If you fake your own vtable, you get 0 guarantees for what these procedures will do when you run them on that vtable.


To be clear, I am not set against something like @JakobDegen's proposal (assuming it can be implemented in Miri). I just would like to better understand the motivation.
Would that proposal be equivalent to having a new "kind" of allocation in Miri (like we don't just have regular allocations but also function allocations, to implement function pointers), and storing somewhere a map from AllocId to type+trait infos, and then making the vtable a pointer to that AllocId, and making vtable lookup consult this special map directly? That also seems quite elegant; it would entirely replace the current vtable lookup code I think.

@JakobDegen
Copy link
Contributor Author

In terms of motivation, two comments:

I had indeed expected your code to be defined if one guessed vtable layout correctly, similar to repr(Rust) types

This is definitely an option, but there's a distinction that I think is worth noting: For #[repr(Rust)] types, it is possible for users to check their guess within the code, and so we must make this well-defined anyway. With vtables, the only way to make sure that your guess is correct is to go read the compiler's source code. Of course, that's not an argument that we need to try and forbid it either.

The compiler also has procedures that, given a vtable, can look up the size and alignment, drop function, or virtual trait function of the type; it guarantees that when generating a vtable for a impl Trait for T, those procedures on the created vtable will produce the expected result.

As written, this rule does not prevent the compiler from including a println!("AAA"); in that function. On the one hand, this is of course a bit of a silly complaint. On the other hand though, it seems non-trivial to me to nail down what set of operations the compiler should be permitted to perform and what set it shouldn't be. Furthermore, once we did figure that out, it's not clear to me that the complexity of this suggestion won't be greater than the complexity of mine.

Would that proposal be equivalent to having a new "kind" of allocation in Miri (like we don't just have regular allocations but also function allocations, to implement function pointers), and storing somewhere a map from AllocId to type+trait infos, and then making the vtable a pointer to that AllocId, and making vtable lookup consult this special map directly

I had not considered that, but I do think this is equivalent, and that does indeed seem quite elegant. Especially if we already do this with function pointers, this kind of direction seems worth pursuing to me.

@RalfJung
Copy link
Member

For #[repr(Rust)] types, it is possible for users to check their guess within the code, and so we must make this well-defined anyway.

"must" is too strong, we could make it ill-defined. C does that (standard C, but of course people use those patterns anyway). https://robbertkrebbers.nl/thesis.html has a proposed formalization of that. But for Rust I don't think we should do that -- it's just worth mentioning that the same design decision we have for vtables here, absolutely also exists for repr(Rust).

As written, this rule does not prevent the compiler from including a println!("AAA"); in that function. On the one hand, this is of course a bit of a silly complaint. On the other hand though, it seems non-trivial to me to nail down what set of operations the compiler should be permitted to perform and what set it shouldn't be.

It is fairly easy to say that these operations cannot have any observable side-effects. So I see no problem here.

@JakobDegen
Copy link
Contributor Author

JakobDegen commented May 18, 2022

these operations cannot have any observable side-effects

How are we defining "observable side-effects" here? (To be clear, I'm not trying to be pedantic/annoying, I ask because I tried to do this and failed)

Specifically, it seems insufficient to restrict to "real" side-effects (IO and such), since functions without real side-effects could still be impure by eg writing to a static mut, and so devirtualization is unsound

@chorman0773
Copy link
Contributor

chorman0773 commented May 18, 2022 via email

@JakobDegen
Copy link
Contributor Author

Heh, sorry, sniped you with the edit

@chorman0773
Copy link
Contributor

Specifically, it seems insufficient to restrict to "real" side-effects (IO and such), since functions without real side-effects could still be impure by eg writing to a static mut, and so devirtualization is unsound

I can add as many side effects to a pure function as I want as long as the observable behaviour is preserved - if a tree falls in a forest, and the user isn't arround to hear it, it does not make a sound.

@JakobDegen
Copy link
Contributor Author

JakobDegen commented May 18, 2022

But you can't show that the observable behavior is preserved:

trait A {
    fn foo(&self);
}

struct S;
impl Foo for S { /* snip */ }

static mut V: i32 = 0;

(&S as &dyn A).foo();
dbg!(V);

Requiring that the compiler shim not do observable side-effects does not prevent it from doing V = 1;. And even if you add a rule that says "also it can't write to globals," you still need to prove that that is enough to make devirtualization sound

@RalfJung
Copy link
Member

The original motivation that spawned this thread, though, was that it is very hard to say what a virtual function call does on the Abstract Machine if we keep the vtable observable. Quoting from above:

Is it really just the layout of the vtable that is allowed to be changed? That seems unnecessarily restrictive, an implementation should be able to add an extra indirection in there if it feels like it.

Also see the discussion starting around here.

Do you mean unspecified?

Ah right that's the C/C++ term for it.

@Diggsey
Copy link

Diggsey commented Jul 17, 2022

a more abstract model gives us stronger guarantees that we can keep evolving the vtable layout (or other things we might want to do with vtables) in the future.

How does it "give us stronger guarantees"? There are only two things that would affect if we can change it in future:

  1. Whether we said it was stable.
  2. Whether people end up writing code that depends on it anyway.

Unless we get to a point where everyone is running all their code through MIRI, then it doesn't seem like this decision affects either (1) or (2).

the entire idea here is to make inspecting vtable layout Undefined Behavior and not even the standard library may do that

This concerns me because IMO, unsafe code should be able to do low-level memory reads of basically any appropriately mapped memory (into MaybeUninit) without immediately invoking UB (and outside of MIRI the vtable is in readable memory for the time being, so it should not be UB to read it).

I'm onboard with the idea of not making any stability guarantees about what lives in the vtable, or even where the vtable is stored, or if we even use a vtable at all, but these seem like things that should be implementation-specific, not UB.

I think maybe part of the issue lies with the notion of backwards compatibility for the AM:

That said, this does not entirely solve the problem: we still want to be able to evolve this part of the AM by changing the structure of the vtable (that is now an internal part of the AM). So we have to prove or at least convince ourselves that such a change cannot change the behavior of any existing program, in particular cannot introduce UB to existing UB-free programs.

It's not necessary for the AM to be backwards compatible in the first place. Only the stable parts of the Rust language need to be backwards compatible, so it would be perfectly fine to have vtable access be well-defined in one version of the AM (but have no related stability guarantees in the language) and then for vtable access to be UB in a later version (if say, the vtable really didn't live in memory in that version).

@RalfJung
Copy link
Member

RalfJung commented Jul 17, 2022

Here's a summary of the problem: to say something is "unspecified", we have to say what the set of possible choices is that the implementation can pick from. This is required so that programmers can argue their code is correct with every possible choice, and hence with every possible implementation.

For struct layout, that is easy: the entire struct gets an arbitrary size, each field gets an arbitrary offset, all subject to the constraint that all fields fit into the size, fields do not overlap, and alignment is respected.

For vtables, this is much harder. I sketched it above, but it quickly derailed into a discussion of how to make all the things I was talking about actually precise. Please read the discussion if you want to know the details, I won't repeat it all here. I think it can be done, but it's complicated and requires some fairly advanced PL techniques. Making vtable accesses UB is a lot easier.

So unless you have a good reason for wanting the program to directly access the vtable, and a good proposal for describing the set of all possible choices for what happens on a virtual call, I think we should stick with making vtable access UB. Note that just saying the layout of the vtable is unspecified is insufficient, since we probably want to allow introducing indirections, and then everything becomes a lot more complicated.

This concerns me because IMO, unsafe code should be able to do low-level memory reads of basically any appropriately mapped memory (into MaybeUninit) without immediately invoking UB (and outside of MIRI the vtable is in readable memory for the time being, so it should not be UB to read it).

Unsafe code is not allowed to read from function pointers either. This is similar.

It's not necessary for the AM to be backwards compatible in the first place. Only the stable parts of the Rust language need to be backwards compatible, so it would be perfectly fine to have vtable access be well-defined in one version of the AM (but have no related stability guarantees in the language) and then for vtable access to be UB in a later version (if say, the vtable really didn't live in memory in that version).

No, that would not be fine. If we have a spec, and some piece of code is correct for all possible choices of unspecified behavior, then we must ensure that this piece of code remains correct as we evolve the spec. If we don't do this, it becomes impossible to write unsafe code that will keep working with future versions of Rust.

@Diggsey
Copy link

Diggsey commented Jul 18, 2022

No, that would not be fine. If we have a spec, and some piece of code is correct for all possible choices of unspecified behavior, then we must ensure that this piece of code remains correct as we evolve the spec. If we don't do this, it becomes impossible to write unsafe code that will keep working with future versions of Rust.

Let's imagine we have an unstable intrinsic do_thing() in the AM, which is implementation-specific. It's perfectly valid for a future version of rust to remove the intrinsic entirely, change what it does, or even make it UB to call. Everything that is not stable is subject to change.

If we don't do this, it becomes impossible to write unsafe code that will keep working with future versions of Rust.

It's perfectly possible: just don't use unstable features.

Unsafe code is not allowed to read from function pointers either. This is similar.

Hmmm. It seems like there are a lot of things that should not be expected to work in general, but where it needs to work in specific instances (ie. specific versions of Rust, on specific platforms). Like, there exist low-level usecases for reading from a function pointer or a vtable. Which of the following is your view:

  1. This is never possible with Rust
  2. This is UB in Rust, but if you target a specific version and platform and follow some rules, then it should be expected to work

@chorman0773
Copy link
Contributor

chorman0773 commented Jul 18, 2022

Let's imagine we have an unstable intrinsic do_thing() in the AM, which is implementation-specific. It's perfectly valid for a future version of rust to remove the intrinsic entirely, change what it does, or even make it UB to call. Everything that is not stable is subject to change.

To put what Ralf has said a different way, the AM does not spec what a particular implementation of rust does, but the base-line for all implementations (which is then parameterized by choices for implementation-defined behaviour, and affected by nondeterministic choices for unspecified behaviour). Thus anything that the AM does specify (outside of definitions for actually unstable features) is by definition stable. Within those constraints it is possible to reason about what the behaviour of the program is on the abstract machine, independant of what implementation of the abstract machine is in use, if you can rule it as stable under all possible parameters and non-deterministic choices. Such code is portable between implementations of rust (whether they be different targets, different versions of the same compiler, or even entirely different compilers).

It's perfectly possible: just don't use unstable features.

This isn't the same as #![feature(specialization)]. As Ralf has said, it's more akin to relying on the fact that if you write a #[repr(Rust)] structure that has a field, that the field is present in the structure for as-if purposes.

Hmmm. It seems like there are a lot of things that should not be expected to work in general, but where it needs to work in specific instances (ie. specific versions of Rust, on specific platforms). Like, there exist low-level usecases for reading from a function pointer or a vtable. Which of the following is your view:

(1) and (2) are exactly the same, in my opinion. In rust, you can't do either of these things, it's UB. Full stop. That being said, if you write code for a particular implementation of rust, then you can rely on both explicit or implicit promises it makes refining the rules of rust (for example, it's particular documented choices for implementation-defined behaviour, or promises for layout of certain types with otherwise unstable layout). At that point, your target is not the rust abstract machine, but a particular implementation, and you lose the portability guarantee.

@RalfJung
Copy link
Member

RalfJung commented Jul 18, 2022

It's perfectly possible: just don't use unstable features.

Calling a virtual function is not an unstable feature. We have to say what it does, on the AM level, and guarantee that this specification will not change in the future (other than permitting clients to do more things -- but every previously correct client must remain correct).

@RalfJung
Copy link
Member

Like, there exist low-level usecases for reading from a function pointer or a vtable.

I can imagine that, though it seems extremely niche. Maybe one day someone suggests a way to make these operations not UB in the Abstract Machine while also still providing useful reasoning principles. I could imagine something like "for each function and vtable, there is an unspecified number of bytes starting at the given address that may be read. writing to any of them is immediate UB. copying those bytes elsewhere does not make a functional copy of the original function/vtable, it results in a regular boring data allocation". Miri then chooses to set that number of readable bytes to 0, but other implementations could choose differently.

This is very different from the status quo in Miri, where you can cobble together a fn ptr, size, and alignment, and this will actually pass as a vtable. I think that is a promise we cannot hold.

@RalfJung
Copy link
Member

RalfJung commented Jul 18, 2022

affected by nondeterministic choices for unspecified behaviour

Unspecified behavior and nondet choice are two very different things, btw. Nondet is what I call pick in MiniRust. Unspecified behavior is a parameter that affects the translation of surface Rust to MiniRust (it might also be a parameter of the MiniRust AM itself, though so far that does not seem necessary). Nondet has some very specific interactions with the notion of correct compilation ("refinement") that unspecified behavior does not have.

@chorman0773
Copy link
Contributor

Unspecified behavior and nondet choice are two very different things, btw.

In C++, unspecified behaviour is defined as the nondeterministic aspects of the abstract machine, so unless rust is somehow different in this regard, I'd consider the two synonymous.

Nondet has some very specific interactions with the notion of correct compilation ("refinement") that unspecified behavior does not have.

Would you be able to share some examples, please?

@Diggsey
Copy link

Diggsey commented Jul 18, 2022

That being said, if you write code for a particular implementation of rust, then you can rely on both explicit or implicit promises it makes refining the rules of rust

Then why can't the standard library rely on the fact that the implementation makes these promises (at least for now) in order to implement DynMetadata?

Calling a virtual function is not an unstable feature.

No, but reading from a vtable within the AM could be an unstable feature (which is then used by std).

I would like it if we could make "your code may become UB in the future" (ie. you are relying on an unstable feature) and "your code is UB today" two distinct results rather than conflating them.

@RalfJung
Copy link
Member

RalfJung commented Jul 18, 2022

In C++, unspecified behaviour is defined as the nondeterministic aspects of the abstract machine, so unless rust is somehow different in this regard, I'd consider the two synonymous.

I guess Rust is different then.

Nondeterminism is a runtime thing. It is an action taken by the program as it runs on the Abstract Machine. The compiler is allowed to "refine" non-determinism by reducing the set from which the choice is taken from during compilation, and even completely resolve the choice to a concrete value. The most canonical example for this in Rust is the address of a freshly created allocation.

If we said that struct layout was non-deterministic, that would mean that each time you start a Rust program, it would be allowed to pick fresh offsets then and there. (Or even each time a struct value is created? Non-determinism is an effect, you have to say when it happens. "Struct layout is non-deterministic" is not a well-defined statement.) That is not the specification we want.

Maybe you mean that compilation is non-deterministic, but then you have to be more precise and distinguish between non-determinism during compilation and non-determinism during execution of the Abstract Machine program.

Then why can't the standard library rely on the fact that the implementation makes these promises (at least for now) in order to implement DynMetadata?

We have not decided to make any such promises for rustc yet. Also note that I said "I could imagine" and "maybe one day". I didn't say I think any of these are good ideas or reflect how we think of Rust today.

Also we care about running this code in Miri which aims to be a faithful implementation of the Rust Abstract Machine.

I don't think the notion of an "unstable AM feature" makes much sense. The purpose of the AM is to specify which programs you can write. Either the AM says my program is fine, then it must stay fine, or it says the program is not fine, then I need to fix it. We could of course have multiple different AMs but that would be a mistake IMO, that's basically forking the language (akin to -fno-strict-aliasing in C).

The standard library runs on the same AM as everyone else. It it okay to exploit layout assumptions there since those are compile-time decisions, but it in my opinion is not okay to have UB in the standard library, no matter how much you know about the compiler. (I know authors of some other compilers disagree, but in rustc this is the policy we follow, AFAIK.)

@chorman0773
Copy link
Contributor

chorman0773 commented Jul 18, 2022 via email

@Diggsey
Copy link

Diggsey commented Jul 18, 2022

The purpose of the AM is to specify which programs you can write. Either the AM says my program is fine, then it must stay fine, or it says the program is not fine, then I need to fix it.

Well that's kindof my issue. If the choice is so binary then there is no room for implementation-specific programs to exist at all, and that is a problem because I believe a lot, if not most, useful programs rely on some behaviour that is implementation-specific.

There is a class of programs which will never work on MIRI but which we should not consider to be "wrong". What do we do for inline assembly here? Surely we say that such programs are simply "out of scope" of the abstract machine, without saying they definitely have UB?

@RalfJung
Copy link
Member

RalfJung commented Jul 18, 2022

there is no room for implementation-specific programs to exist at all

That's not true. As I keep saying, struct layout is implementation-specific (unspecified, whatever you want to call it). I also disagree with your thesis that most useful programs rely on implementation-specific behavior, unless you mean rely on it transitively through the standard library. Outside the standard library me and many others generally consider relying on implementation-specific behavior a soundness bug.

But I don't think vtables and vtable access should be implementation-specific, at least not in the form of allowing programs to read from the vtable. Instead what I do in rust-lang/rust#99420 is add some implementation-specific intrinsics that can be specified on the AM in a coherent way. This avoids the need for "implementation-specific UB" or anything like that. Now Miri can fully enforce opaque vtables and run stdlib code that needs to fetch the size from a vtable.

@RalfJung
Copy link
Member

RalfJung commented Jul 18, 2022

There is a class of programs which will never work on MIRI but which we should not consider to be "wrong". What do we do for inline assembly here? Surely we say that such programs are simply "out of scope" of the abstract machine, without saying they definitely have UB?

I don't think this is the right thread for fundamental discussions about the limits of Abstract Machine specifications, but there is a coherent way to integrate inline assembly and C FFI into this picture. (Basically, the author of the code has to "axiomatize" what transition on the AM state is implemented by this "gap in the code". That transition needs to be one that could also have been taken by regular Rust code, to ensure correctness of compiler analyses.) Indeed Miri will not be able to run such code.

So yes we could probably have implemented those parts of the stdlib via inline assembly (though the "must be possible in regular Rust code" part could become tricky, if a compiler analysis wants to actually rely on the fact that regular Rust code can never read the size field -- but now that we have an intrinsic for this, that is an operation the optimizer has to take into account anyway). I think an intrinsic is much cleaner though.

bors added a commit to rust-lang-ci/rust that referenced this issue Jul 22, 2022
make vtable pointers entirely opaque

This implements the scheme discussed in rust-lang/unsafe-code-guidelines#338: vtable pointers should be considered entirely opaque and not even readable by Rust code, similar to function pointers.

- We have a new kind of `GlobalAlloc` that symbolically refers to a vtable.
- Miri uses that kind of allocation when generating a vtable.
- The codegen backends, upon encountering such an allocation, call `vtable_allocation` to obtain an actually dataful allocation for this vtable.
- We need new intrinsics to obtain the size and align from a vtable (for some `ptr::metadata` APIs), since direct accesses are UB now.

I had to touch quite a bit of code that I am not very familiar with, so some of this might not make much sense...
r? `@oli-obk`
antoyo pushed a commit to rust-lang/rustc_codegen_gcc that referenced this issue Aug 26, 2022
make vtable pointers entirely opaque

This implements the scheme discussed in rust-lang/unsafe-code-guidelines#338: vtable pointers should be considered entirely opaque and not even readable by Rust code, similar to function pointers.

- We have a new kind of `GlobalAlloc` that symbolically refers to a vtable.
- Miri uses that kind of allocation when generating a vtable.
- The codegen backends, upon encountering such an allocation, call `vtable_allocation` to obtain an actually dataful allocation for this vtable.
- We need new intrinsics to obtain the size and align from a vtable (for some `ptr::metadata` APIs), since direct accesses are UB now.

I had to touch quite a bit of code that I am not very familiar with, so some of this might not make much sense...
r? `@oli-obk`
workingjubilee pushed a commit to tcdi/postgrestd that referenced this issue Sep 15, 2022
make vtable pointers entirely opaque

This implements the scheme discussed in rust-lang/unsafe-code-guidelines#338: vtable pointers should be considered entirely opaque and not even readable by Rust code, similar to function pointers.

- We have a new kind of `GlobalAlloc` that symbolically refers to a vtable.
- Miri uses that kind of allocation when generating a vtable.
- The codegen backends, upon encountering such an allocation, call `vtable_allocation` to obtain an actually dataful allocation for this vtable.
- We need new intrinsics to obtain the size and align from a vtable (for some `ptr::metadata` APIs), since direct accesses are UB now.

I had to touch quite a bit of code that I am not very familiar with, so some of this might not make much sense...
r? `@oli-obk`
@dimpolo
Copy link

dimpolo commented Oct 7, 2022

I have a weird question, hopefully it's alright to ask here.
I have a use case where I want to perform something similar to upcasting a ThinBox.
Since the ThinBox stores the vtable pointer inline, normal upcasting can not work.
However I was hoping that for some combinations of traits where it is known, that upcasting does not change the vtable pointer, a transmute would be fine.

So my question would be:
Is it possible to include the notion of a trivial upcast into the spec (and the implementation of MIRI) so that code like the following is both sound and deterministic?

#![feature(ptr_metadata)]
#![feature(thin_box)]
#![feature(trait_upcasting)]

use std::boxed::ThinBox;
use std::ops::Deref;

trait A {
    fn a(&self);
}

trait B: A {
    fn b(&self);
}

impl A for i32 {
    fn a(&self) {
        println!("a");
    }
}


impl B for i32 {
    fn b(&self) {
        println!("b");
    }
}


fn main() {
    let x: ThinBox<dyn B> = ThinBox::new_unsize(5);

    x.b();
    if let Some(x) = try_upcast(x) { // MIRI returns None :(
        x.a()
    }
}

fn try_upcast(x: ThinBox<dyn B>) -> Option<ThinBox<dyn A>> {
    // somehow check that dyn A vtable is a subset of the dyn B vtable
    // would be nice to have this as an intrinsic
    let fat_ptr: &dyn B = x.deref();
    let meta_1 = core::ptr::metadata(fat_ptr);
    let meta_2 = core::ptr::metadata(fat_ptr as &dyn A);
    let upcast_is_trivial = format!("{meta_1:?}") == format!("{meta_2:?}");

    if upcast_is_trivial {
        // manual "upcast"
        Some(unsafe { core::mem::transmute(x) })
    } else { None }
}

@bjorn3
Copy link
Member

bjorn3 commented Oct 7, 2022

We don't guarantee any encoding of vtables. The fact that the vtable of B contains a valid vtable of A is just an optimization and should not be visible to end users. As such checking that it is a subset should remain UB IMHO.

@dimpolo
Copy link

dimpolo commented Oct 7, 2022

As such checking that it is a subset should remain UB IMHO.

I was hoping we could say that the result of checking is unspecified but consistent for one particular implementation.

Something along the lines of how TypeId works:

While TypeId implements Hash, PartialOrd, and Ord, it is worth noting that the hashes and ordering will vary between Rust releases. Beware of relying on them inside of your code!

@RalfJung
Copy link
Member

RalfJung commented Oct 7, 2022

No, currently vtables are deliberately unobservable in the program -- any attempt to even read from a vtable using a regular load is UB.

I have no idea what the debug printer of metadata shows -- but it is definitely not okay to rely on it for anything.

If there is a usecase for directly accessing the vtable from the program, that needs to be carefully specified and RFC'd first.

@dimpolo
Copy link

dimpolo commented Oct 7, 2022

any attempt to even read from a vtable using a regular load is UB.

I understand, but this is a little different.

No access to the vtable is happing, just a comparison of the address of the vtable.

The debug printer just prints the vtable address.
In real code I would transmute the metadatas to opaque pointers and compare them.
(I just tried to limit the unsafe blocks for the example)

Here's another way of phrasing the question:

Is it ok to observe the address of a vtable and if yes is it safe to transmute a DynMetadata<dyn B> to a DynMetadata<dyn A> if they point to the same vtable?

@RalfJung
Copy link
Member

RalfJung commented Oct 7, 2022

No, that's not safe either. vtables can be deduplicated, so if two types have the same size and alignment and a NOP drop, they might share the vtable.

In real code I would transmute the metadatas to opaque pointers and compare them.

That's incorrect, too -- the transmute might fail in the future if the size of the metadata changes.

(In the future please open a new issue unless you are sure it is the same question as another issue. Now we have two completely independent discussions mixed in this overly long thread.)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

7 participants