How are virtual function calls specced?

[JakobDegen]

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]

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]

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]

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]

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

[digama0]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

I'd assume same way as C++, modified slightly: volatile access and I/O.

On Wed, May 18, 2022 at 17:20 Jakob Degen @.***> wrote:

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)

— Reply to this email directly, view it on GitHub https://github.com/rust-lang/unsafe-code-guidelines/issues/338#issuecomment-1130563207, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABGLD22L5YEMEYNSMIZSQQLVKVNKBANCNFSM5V6EAHEA . You are receiving this because you commented.Message ID: @.***>

[JakobDegen]

Heh, sorry, sniped you with the edit

[chorman0773]

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]

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

[digama0]

...or it could just write to the data pointer that was passed to it. Or not even call the right function or do nothing.

I think what is needed here is to say that it is observationally equivalent to the appropriate devirtualized function call, which is pretty much what Jakob's original model was doing.

[RalfJung]

These are all good questions, but they are also solved problems in program language formalization and reasoning. :)

In first approximation, we can say the function must be read-only, i.e., leave the machine state exactly as it found it. It is also possible to formalize the idea of "observably read-only", but that requires a class in PL theory to explain (keyword: "logical relation"). Unfortunately I don't know a good book explaining this material, these lecture notes might be a start. But if you believe me that we can formalize the idea of "contextual equivalence", aka " equivalent to every observer inside the AM", then we can state "observably read-only" as "equivalent to some syntactically read-only function".

[RalfJung]

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.

Agreed; I'd be fine with landing such a change.

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.

[JakobDegen]

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)

Do we? Why can't we forever keep the "AM vtable" as a ZST alloc, and then lower those to real vtables and force the implementation to prove that this has no observable distinction?

[RalfJung]

For example, the AM would have had t change when trait upcasting was implemented, by adjusting the AM vtable to account for the new unsizing entries.

[digama0]

Well yeah, if Rust literally gains new features then the AM will have to support them... I see no way around that since the spec would have to change in any case: &dyn SubTrait -> &dyn SuperTrait is not legal today and would be with the new feature.

[RalfJung]

Yes of course. But this means we still have to be careful to only change the AM in ways that would not make previously well-defined programs UB.

I think both approaches achieve that; I am just saying that even with entirely interpreter-controlled vtables we still have to be a bit careful.

[RalfJung]

I have implemented the "symbolic vtable" scheme in Miri (where a vtable is a special kind of allocation that does not exist as regular Abstract Machine memory), and ran into an issue: the (unstable) DynMetadata type provides access to the size and alignment stored in the vtable. This code has UB under the proposed scheme where Abstract Machine code cannot access the data in the vtable -- including Abstract Machine code in the standard library. (The standard library may exploit implementation-specific behavior, but the entire idea here is to make inspecting vtable layout Undefined Behavior and not even the standard library may do that.)

These APIs are actually used e.g. by Rc, so I doubt we can just drop them. I think we'd have to implement them via an intrinsic to keep this working.

[RalfJung]

Ah no, turns out Rc does not need those functions, it just needs the DynMetadata type.

[Diggsey]

What was the motivation for making vtable access UB, rather than leaving it to be implementation defined? There is a middle ground between stabilizing something and making it UB...

[RalfJung]

For datatype layouts we have to make them implementation-specific (not implementation-defined!) to make things like offset_of! work. But for vtables there is no need to do that, and 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. It means we might not need -Z randomize-vtable.

The entire notion of "is this a valid vtable (for a given type/trait)" does not even make any sense on the Abstract Machine level without this kind of "symbolic vtable".

[chorman0773]

On Sun, 17 Jul 2022 at 17:01, Ralf Jung @.***> wrote:

For datatype layouts we have to make them implementation-specific (not implementation-defined!)

Do you mean unspecified?

to make things like offset_of! work. But for vtables there is no need to do that, and 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.

The entire notion of "is a valid vtable (for a given type/trait)" does not even make any sense on the Abstract Machine level without this kind of "symbolic vtable".

— Reply to this email directly, view it on GitHub https://github.com/rust-lang/unsafe-code-guidelines/issues/338#issuecomment-1186606273, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABGLD25UD2YK4XE6GMJOS2TVURYBFANCNFSM5V6EAHEA . You are receiving this because you commented.Message ID: @.***>

[RalfJung]

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]

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]

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]

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]

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]

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]

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]

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.