What can I assume about VTable pointers?

help
1

I am experimenting with pointer metadata and want to make sure, that assumptions I make are correct. Consider following example:

#![feature(ptr_metadata)]

use std::ptr::metadata;

trait Foo {}

impl Foo for i32 {}
impl Foo for u32 {}

fn main() {
    let x: &dyn Foo = &42i32;
    let y: &dyn Foo = &42u32;
    let z: &dyn Foo = &42u32;
    
    let x_metadata = metadata(x);
    let y_metadata = metadata(y);
    let z_metadata = metadata(z);
    
    // This actually fails even in normal execution,
    // because compiler is smart enough to unify the same vtables.
    // assert_ne!(x_metadata, y_metadata);
    
    // This works in normal execution, but fails under miri.
    assert_eq!(y_metadata, z_metadata);
}

I thought that following logic clause was true:

For all a, b: dyn Foo where their concrete types are A and B respectively: A == B => vtable(a) == vtable(b).

So if two vtables are the same, then trait object may originate from the same type. But if they do originate from the same type, then they vtable pointers must be the same.

However when I run above code under Miri, then assertion assert_eq!(y_metadata, z_metadata) fails! Does this mean that my assumptions about vtables are wrong? Or does Miri do some additional safety checks, that are irrelevant to actual generated code? And if so, can they be turned of with some flag?

1 Like
2

Conjecture: perhaps vtables are instantiated once per codegen unit? That would mean that the same type may have several different vtables.

3

It's not true. The compiler may duplicate a vtable.

3 Likes
4

When could this happen? And can I somehow force the compiler/miri to not do this?

I am trying to crate a collection, where I can store trait objects as a list of data pointers (thin part of *const dyn Foo) and list of vtable pointers. Point being that if multiple trait objects with the same vtable are added, then vtable pointer is only stored once.

If I cannot rely on vtables being the same for the same concrete types, this would somehow limit the usefulness of such collection. In that case I would like to at least force Miri to comply, because without it I cannot reliably run tests under Miri, which would be sad (since implementation involves a modest amount of unsafe).

5

In practice, it mostly happens when multiple crates are involved. The vtable gets duplicated once for each compilation unit that needs the vtable. No, you can't force the compiler to not do it. Miri intentionally duplicates them more often to help discover code that is incorrect because it relies on duplication not happening.

8 Likes
6

You cannot rely on the address of a vtable, in the same way and for the same reasons that you cannot rely on the address of a function or a const. To the compiler, vtables are just pieces of static data to be allocated when needed.

3 Likes
7

Ah. I think I've found place where documentation indeed states that I cannot make those assumptions. Documentation of std::ptr::DynMetadata contains following section:

Note that while this type implements PartialEq, comparing vtable pointers is unreliable: pointers to vtables of the same type for the same trait can compare inequal (because vtables are duplicated in multiple codegen units), and pointers to vtables of different types/traits can compare equal (since identical vtables can be deduplicated within a codegen unit).

4 Likes
8

I don't think, however, that this necessarily breaks your design as described; it stops you knowing whether or not two things have the same type just based on their DynMetadata (since two DynMetadata<T> can be equal for different types, or not equal for the same type), but it does allow for a possible storage saving if you're storing a BTreeSet<*const dyn T> as a BTreeMap<DynMetadata<T>, BTreeSet<*const ()>>.

9

My original intent was to represent Vec<*mut dyn T> as:

pub struct Container<T, const N: usize>
where
    T: Pointee<Metadata = DynMetadata<T>> + ?Sized,
{
    tags: ArrayVec<DynMetadata<T>, N>,
    data: Vec<*mut ()>,
    _phantom: PhantomData<Box<T>>,
}

Where tags is a stack allocated array with N slots for holding vtable metadata.

I think that this design will still work, but now when caller chooses N = 8, they cannot be sure that 8 different types can be represented, because vtables can be duplicated. I could resign from allocating statically number of slots for DynMetadata, but that would mean that memory usage guarantees were much weaker.

10

Even if vtables were identical for the same type, I see a big problem with your design; how do I reliably know which tags entry goes with a given data entry? You don't save any storage if you put an index (even a u8 index) in data, since padding will make each entry in the Vec still the size of 2 pointers.

1 Like
11

Pointers stored in self.data can be tagged with index of metadata in self.tags. To do this I align trait objects to N bytes (hence N slots in self.tags).

12

The documentation for std::ptr::eq also mentions something similar.

There's also Rc::ptr_eq and Arc::ptr_eq that were added for this reason, though their documentation don't seem to mention this.

1 Like
13

It says

Returns true if the two Rcs point to the same allocation

And that allocation is never empty because of the reference counts, so it's reliable.

So it's more like addr_eq in std::ptr - Rust than like eq in std::ptr - Rust

14

That's not why they were added; they've only ignored metadata since 1.72.

1 Like
15

I have one more question. If I know that two trait objects originate from the same underlying type, can I safely swap their vtable pointers? vtables may be duplicated, but surely they are identical, and it should not matter which one is used, should it?

Miri does not warn that following code is wrong. Is this enough?

#![feature(ptr_metadata)]

use std::ptr::{from_raw_parts, from_ref};

trait Foo {}

impl Foo for i32 {}

fn main() {
    let x: &dyn Foo = &42; 
    let y: &dyn Foo = &42; 
    
    let (x_ptr, x_metadata) = from_ref(x).to_raw_parts();
    let (y_ptr, y_metadata) = from_ref(x).to_raw_parts();

    // assume that we **kown** that `x` and `y` originate
    // from the same original type. Is this safe?
    let z: &dyn Foo = unsafe {
        // constructs trait object from thin pointer to `y` and vtable of `x`
        let z: *const dyn Foo = from_raw_parts(y_ptr, x_metadata);
        &*z
    };
}
16

Well, the documentation says:

For trait objects, the metadata must come from a pointer to the same underlying erased type.

So, it should be sound. However, note that “from the same underlying erased type” is not implied by “the data pointer is the same”. For example:

let a = [42, 0];
let x: &dyn Debug = &a; 
let y: &dyn Debug = &a[0];
let z: &dyn Debug = std::array::from_ref(&a[0]);

x and y have identical data pointers, and vtables for the same trait, but they have different behaviors, and y has a smaller size and provenance. y and z have identical size but still different behaviors.

9 Likes
17

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.