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

Validity of wide pointer metadata #166

Closed
RalfJung opened this issue Jul 12, 2019 · 37 comments
Closed

Validity of wide pointer metadata #166

RalfJung opened this issue Jul 12, 2019 · 37 comments
Labels
A-validity Topic: Related to validity invariants meeting-proposed Proposed to be discussed at a future t-opsem meeting S-pending-design Status: Resolving this issue requires addressing some open design questions

Comments

@RalfJung
Copy link
Member

RalfJung commented Jul 12, 2019

The discussions at #76 and #77 are about the validity invariant that all references have to maintain in general; this issue here is specifically about the validity invariant of the metadata component of any fat pointer -- which do not have to be references! Rc<[u8]> is also a fat pointer. The expected metadata depends on the type of the "unsized tail".

For slices, it seems clear that the invariant will be the same as that for usize. But for dyn Trait pointers, what should we require about the vtable? My guess would have been at least as much as an &[usize; 3] (a vtable has at least 3 slots: size, alignment and drop function, not necessarily in that order). But in this forum thread, the valid question came up why Weak::new does not work for dyn Trait, and indeed it could if we could "fake" the fat pointer component (though doing that generically seems hard).

And then there is the question how this interacts with eventual custom/user-defined DSTs.

@RalfJung RalfJung added active discussion topic A-validity Topic: Related to validity invariants labels Jul 12, 2019
@gnzlbg
Copy link
Contributor

gnzlbg commented Jul 12, 2019

But for dyn Trait pointers, what should we require about the vtable?

Is there consensus about the validity invariant of the vtable pointer ? E.g. if the vtable pointer can be null, then there doesn't need to be a vtable at all. If the vtable is a reference, then whether there needs to be a valid vtable at all would depend on whether validity of references is transitive. Or do we want to be more strict about vtables ?

@hanna-kruppe
Copy link

Nit: The issue title talks about references, but the text (and Weak::new discussion) about pointers more generally, which is it?

@petertodd
Copy link

Food for thought example: creating a Weak<[T]>.

As long as the nightly-only Weak::as_raw(), Weak::into_raw() etc. exist we have to actually initialize the pointer metadata to something; we can't just "initialize" it with the equivalent of MaybeUninit. So we need some kind of Weak::new_unsized(metadata: <T as Pointee>::Metadata). This would also allow Weak::new() to to work with unsized types if the pointer metadata implements Default:

impl<T: ?Sized> Weak<T> {
    pub fn new() -> Weak<T>
        where <T as Pointee>::Metadata: Default
    {
        unimplemented!()
    }
}

(obvious disadvantage: unnecessary complexity confusing beginners in 99% of use-cases)

Equally, it might be reasonable to eventually (with arbitrary self types) change the slice API so that len() takes a pointer:

impl<T> [T] {
    pub const len(self: *const Self) -> usize {
        unimplemented!()
    }
}

...which in this case could actually be accessed via Weak::as_raw:

let w: Weak<[u8]> = Weak::new_unsized(42);
assert_eq!(w.as_raw().len(), 42);

Heck, you could even imagine a DerefPtr type trait. But I suspect the use-cases of it would be so narrow as to be unnecessary complexity.

As for how this would interact with trait objects, the compiler can probably implement Default for the vtable type automatically. And again, it'd be plausible to allow the calling of trait methods that take pointers.

@RalfJung RalfJung changed the title Validity of references: fat pointer metadata Validity of fat pointer metadata Jul 16, 2019
@RalfJung
Copy link
Member Author

Nit: The issue title talks about references, but the text (and Weak::new discussion) about pointers more generally, which is it?

Good point! That actually explains part of my confusion. I updated text and title.

@RalfJung
Copy link
Member Author

I just realized that with the new title, this discussion would now also apply to fat raw pointers. But IIRC we agreed that fat raw pointers do not have to have valid metadata.

So actually maybe this thread should be about references? Weak internally uses NonNull which is a raw pointer, and IIRC there was agreement that raw pointers do not need to have valid metadata.

@RalfJung
Copy link
Member Author

Similar to #72 (comment), I wonder if it would be worth to write up a (small) RFC that says that fat raw pointers (including NonNull) do not assume validity of their metadata, i.e., the validity invariant of their metadata is the same as that of usize? (It is already the case that a thin raw pointer itself has the same validity invariant as usize, as the two can be cast to each other in safe code.)

@RalfJung RalfJung changed the title Validity of fat pointer metadata Validity of wide pointer metadata Jul 28, 2019
@petertodd
Copy link

@RalfJung So like usize they're assumed to not be undef bits, but beyond that there are no further assumptions?

Do we assume the metadata for all wide pointers is always safely castable to usize? Eg could there be a future wide pointer type where the metadata has a subset of valid bit representations, like, say, bool?

@gnzlbg
Copy link
Contributor

gnzlbg commented Aug 5, 2019

Eg could there be a future wide pointer type where the metadata has a subset of valid bit representations, like, say, bool?

Do you have a concrete application in mind?

@RalfJung
Copy link
Member Author

RalfJung commented Aug 5, 2019

So like usize they're assumed to not be undef bits, but beyond that there are no further assumptions?

Exactly. And if we decide we are fine with uninitialized integers, then so would be wide raw pointer metadata.
This also matches *const T/*mut T, which have the exact same validity invariant as usize -- after all, they can be safely converted back and forth.

Do we assume the metadata for all wide pointers is always safely castable to usize? Eg could there be a future wide pointer type where the metadata has a subset of valid bit representations, like, say, bool?

I guess we should clarify that everything we are saying right now is only for wide pointer types that already exist (slices and trait objects). I do not want to unnecessarily constrain custom DST designs.

@petertodd
Copy link

Eg could there be a future wide pointer type where the metadata has a subset of valid bit representations, like, say, bool?

Do you have a concrete application in mind?

Having a hard time coming up with one, other than trait objects where it's plausible you'd want to call a method on the trait for a potentially invalid pointer. Basically, that'd allow a call like this to work: fn foo(self: *const dyn Foo)

@RalfJung
Copy link
Member Author

Dereferencing the raw pointer will require the vtable to be valid. The question here is about invariants that are maintained even when the pointer is just "passed around".

@petertodd
Copy link

Dereferencing the raw pointer will require the vtable to be valid. The question here is about invariants that are maintained even when the pointer is just "passed around".

Note the "dyn Foo" - I'm not talking about an example where we're dereferencing the pointer itself. Rather, I'm talking about a potential new feature.

@RalfJung
Copy link
Member Author

It seems reasonable to say that a pointer/reference to dyn Trait gets dereferenced when you access its vtable.

Note that by dereference I mean the * operator, so &*x does dereference x, even though no memory access happens.

@RalfJung
Copy link
Member Author

It seems like rustc actually marks the vtable in wide raw pointers as non-null. That is quite surprising to me. Is that really what we want?

@RalfJung
Copy link
Member Author

RalfJung commented Aug 26, 2019

Turns out for slices however, safe code can create raw slices with invalid metadata:

123456789 as *const [(); usize::max_value()] as *const [()] as *const [u64]

What a mess.

Maybe the size condition is just pat of the safety invariant for slices? Then at least we'd uniformly say that metadata has to be valid for raw pointers.

@hanna-kruppe
Copy link

I'm surprised by mere suggestion of any restriction on the size part of a raw slice (apart from things that apply to all usizes, like being initialized). After all, as raw pointers they don't have to refer to any allocation, so there's really no harm in permitting them to be dangling and hold addresses and lengths that wouldn't be possible to create an actual allocation for. Was anyone really trying to get a niche out of *[T] depending on the size of T?

I don't even see why it would have to be part of the safety invariant. offset and related functions are themselves unsafe because of the isize::MAX restriction. That restriction is part of the safety invariant for references, Boxes, etc. to slices since lots of safe functions will want to (indirectly) call offset on them with offsets that are only bounds-checked against the size of the allocation. But there's no such operations on raw slices.

@gnzlbg
Copy link
Contributor

gnzlbg commented Aug 26, 2019

What a mess.

Maybe we can consider the metadata as part of the pointee instead of as part of the pointer ?

That is, the validity of [T] could require [T]::len valid elements. A *[T] does not necessarily need to point to a [T] so len can be anything. When one dereferences a *[T] the validity of the [T] is asserted, imposing constraints on valid [T]::len.

What a &[T] requires would depend on what we require for the validity of references. If reference validity is not transitive, the pointer needs to be aligned, non-null, etc. but creating a &[T] with an incorrect len would be ok - dereferencing that &[T] would assert the validity of [T] which could fail. If we make validity of references transitive, then the validity of &[T] requires [T] to be valid and depends on [T]::len.

@nico-abram
Copy link

nico-abram commented Aug 26, 2019

but creating a &[T] with an incorrect len would be ok - dereferencing that &[T] would assert the validity of [T] which could fail.

Aren't references always assumed dereferenceable

@gnzlbg
Copy link
Contributor

gnzlbg commented Aug 26, 2019

Aren't references always assumed dereferenceable

That would depend on what the validity of references requires (#77 ) (EDIT: and/or the aliasing model). It could require that, and that would allow us to emit dereferenceable in many cases, e.g., for all thin references (&i32).

For wide pointers, we cannot, in general, emit dereferenceable. Consider:

fn foo(x: &[T]) { ... }

How would we emit dereferenceable(n) for the pointer in x ? n must be a compile-time constant representing the number of bytes for which the reference is dereferenceable, but for slices that's a dynamic value in the [T]::len field and can be zero.

In cases like:

static X: [i32; 4] = [0, 1, 2, 3];
pub unsafe fn foo() -> /* dereferenceable(16) */ &'static [i32] { &X }

it is always correct to emit dereferenceable independently of what the validity of references requires. We currently do not (https://rust.godbolt.org/z/pQRqsO), but that looks like a missed optimization.

EDIT: Arguably, LLVM could add a new attribute that allowed expressing this, similar to how the allocsize function attribute works.

@RalfJung
Copy link
Member Author

I'm surprised by mere suggestion of any restriction on the size part of a raw slice (apart from things that apply to all usizes, like being initialized). After all, as raw pointers they don't have to refer to any allocation, so there's really no harm in permitting them to be dangling and hold addresses and lengths that wouldn't be possible to create an actual allocation for. Was anyone really trying to get a niche out of *[T] depending on the size of T?

This is probably my mistake. I learned about the size restriction for slices and was like "sounds like a validity invariant to me". And then when metadata validity was expanded to raw pointers I naturally also expanded this.

But you are right, the more natural way to treat this is to fold this into the requirement that &[T] must be dereferencable, which is already defined as "everything must be within the same allocation". Together with isize::MAX being the maximal allocation size, that gives us the desired specification.

I don't even see why it would have to be part of the safety invariant.

I meant that for safe slices only. We agree it is part of the safety invariant for &[T], right?

For wide pointers, we cannot, in general, emit dereferenceable

At least for now, I'd like to be as strict as we can, and demand them to be dereferencable for size_of_val many bytes. We can always relax that later.

@hanna-kruppe
Copy link

@RalfJung Ok, I see.

I meant that for safe slices only. We agree it is part of the safety invariant for &[T], right?

Yes.

@elichai
Copy link

elichai commented Nov 11, 2019

It seems like rustc actually marks the vtable in wide raw pointers as non-null. That is quite surprising to me. Is that really what we want?

I must say I'm really surprised by this discussion.
I think raw pointers should be left raw pointers, they should have no safety guarantees.
most of the rust ecosystem got used to the fact that pointers are a mess but it's fine as long as you make sure it's valid when dereferenced.
I don't think fat pointers should be treated any different.

there's no good reason I can think of why this shouldn't be valid: https://play.rust-lang.org/?gist=50e814066bcb1f4e9f7fc8c2ca71c6c0
And I think that any Minor optimization (i.e. size_of::<*const dyn Trait>() == size_of::<Option<*const dyn Trait>()) is worth the brain heavy weighting that we need to do because there's no way to reason about raw pointers without knowing the exact type.

I really hope that unsafe raw pointers will stay that way, if we start requiring validity then what makes them raw pointers?

@RalfJung
Copy link
Member Author

RalfJung commented Nov 12, 2019

I think raw pointers should be left raw pointers, they should have no safety guarantees.

Notice that wide raw pointers never were "raw" in that sense. Since Rust 1.0, the compiler assumed that vtables are non-null. So, there's nothing to "leave as-is" here. But we might suggest in an RFC to change them to be "fully raw".

most of the rust ecosystem got used to the fact that pointers are a mess but it's fine as long as you make sure it's valid when dereferenced.

That's not really an accurate summary. By "pointers", do you mean everything that has a pointer value or just specifically raw pointers? I am assuming the latter but it is not clear. And even then, you need to make sure that there are no references anywhere that are in conflict with what you are doing with your raw pointers. That is more than just making sure they are "valid" -- "valid" is a technical term in these discussions (also see our glossary).

I really hope that unsafe raw pointers will stay that way, if we start requiring validity then what makes them raw pointers?

Just to make sure we are talking about the same thing, the validity requirement is for the metadata of a wide raw pointer only. And (repeating myself) that metadata never was "raw", so it cannot stay that way either. We started requiring validity for that before Rust 1.0. What you are suggesting is to change them to be that way.

there's no good reason I can think of

The good reason that has been raised in this thread is using raw pointers as method receivers in object-safe traits.

@elichai
Copy link

elichai commented Nov 12, 2019

I'm sorry if I wasn't clear enough (wrote it in the middle of the night).

Notice that wide raw pointers never were "raw" in that sense. Since Rust 1.0, the compiler assumed that vtables are non-null. So, there's nothing to "leave as-is" here. But we might suggest in an RFC to change them to be "fully raw".

Yes, I understand that. But I still think a lot of the ecosystem(and the FFI/unsafe one) doesn't know/understand this.

That's not really an accurate summary. By "pointers", do you mean everything that has a pointer value or just specifically raw pointers? I am assuming the latter but it is not clear. And even then, you need to make sure that there are no references anywhere that are in conflict with what you are doing with your raw pointers.

Yes, I talked about just raw pointers. and again everything "you need to make sure" is only at dereference time.

Just to make sure we are talking about the same thing, the validity requirement is for the metadata of a wide raw pointer only. And (repeating myself) that metadata never was "raw", so it cannot stay that way either. We started requiring validity for that before Rust 1.0. What you are suggesting is to change them to be that way.

You're right, I shouldn't have said "stay this way" I was more thinking about letting my brain model of unsafe stay the way it is :P

The good reason that has been raised in this thread is using raw pointers as method receivers in object-safe traits.

Can these even be useful without dereferencing the raw pointer?
I think making them unsafe is fine IMHO.

You keep saying "only the metadata need to be valid". so how can I create a null/dangling pointer with a valid metadata? :)

@RalfJung
Copy link
Member Author

RalfJung commented Nov 12, 2019

You keep saying "only the metadata need to be valid". so how can I create a null/dangling pointer with a valid metadata? :)

You can't. ;)

But the reason I said that is that thin raw pointers are unaffected. I doubt there is a "lot of ecosystem" that has to handle wide raw pointers -- and in FFI they should never occur as their representation is unstable. Right now a raw trait object pointer consists of a data pointer and a vtable pointer but that is not a stable guarantee. Code relying on the data layout of wide pointers (or references) is just as incorrect as code relying on the data layout of struct without repr(C).

So what I am saying is, the code you are talking about has some more fundamental problems than NULL vtables. Someone needs to push through an RFC that stabilizes the representation of wide pointers; before that happens I think there is very little motivation for talking about their validity requirements.

I was more thinking about letting my brain model of unsafe stay the way it is :P

That's fair. ;) But sometimes models are wrong and need to be adjusted to reality... that said, I had a similar reaction to you first, which is why I am generally in favor of not making any validity requirements for raw pointers. But that would make calling a method on a raw dyn Trait pointer unsafe, even though that operation does not actually dereference the pointer.

@elichai
Copy link

elichai commented Nov 12, 2019

You can't. ;)

So let's remove the possiblity of raw pointers to dyn traits. Why do we need them in the language? if you can't construct "invalid" pointers and you can't do pointer arithmetic(which also makes no sense in a pointer pointing to a trait and not a struct) on them then let's leave references only :).

But the reason I said that is that thin raw pointers are unaffected. I doubt there is a "lot of ecosystem" that has to handle wide raw pointers -- and in FFI they should never occur as their representation is unstable. Right now a raw trait object pointer consists of a data pointer and a vtable pointer but that is not a stable guarantee. Code relying on the data layout of wide pointers (or references) is just as incorrect as code relying on the data layout of struct without repr(C).

IIRC wide pointers as in slices do have a stable memory layout, (struct Slice {ptr: *const T, len: usize}).
Am I wrong? this representation is both useful and makes sense in safe and unsafe code (i.e. in transmuting and manipulating the length).

That's fair. ;) But sometimes models are wrong and need to be adjusted to reality... that said, I had a similar reaction to you first, which is why I am generally in favor of not making any validity requirements for raw pointers. But that would make calling a method on a raw dyn Trait pointer unsafe, even though that operation does not actually dereference the pointer.

My only question now is what is the usefullness of raw dyn Trait? in a raw slice there's a lot of usefulness(And I might be for exposing the length for safe code). but if there's already some amount of required validity let's lint it/ remove it from the language. people should use references in that case (and if they're doing some black magic they should transmute the reference to &'static one, because there's 0 amount of checks that can be done "before dereferencing" if the vtable has to stay valid forever).

in summary:
There are 2 use cases I know of for raw pointers:

  1. FFI - this isn't a thing in wide/fat pointers.
  2. Defeating the borrow checker (i.e. Box::into_raw, etc.) and that is very misleading in dyn trait pointers right now, because you can't just put a bunch of checks and logic to make sure you don't dereference if the pointers become invalid, because the vtable isn't allowed to be invalid.

Now I might be overstating it and the vtable always points to a static location which means it has no life time to it etc, but it still feels wrong to me.

@cuviper
Copy link
Member

cuviper commented Nov 12, 2019

You can create a null trait object by first creating a null pointer to a sized type, then casting or coercing to the unsized pointer.

@RalfJung
Copy link
Member Author

RalfJung commented Nov 12, 2019

if you can't construct "invalid" pointers and you can't do pointer arithmetic

You can have "invalid" pointers as far as the data ptr is concerned; just the vtable has to be valid. There's still plenty of use-cases for that. In particular this means a general &mut T with T: ?Sized can be turned into *mut T and used without any aliasing restrictions. The vtable is in immutable memory, there are no aliasing problems with that.

So, "defeating the borrow checker" as you called it, works fine with raw trait object pointers.

IIRC wide pointers as in slices do have a stable memory layout, (struct Slice {ptr: *const T, len: usize}).
Am I wrong?

You are wrong. slice::from_raw_parts(_mut) as well as slice::as(_mut)_ptr and slice::len are the only supported ways to (de)construct slice references and raw pointers. transmuteing wide slice pointers/references is not supported.

Generally, in terms of data layout, the only things you can rely on are things that are explicitly documented. There is no implicit stabilization of layout.

@Lokathor
Copy link
Contributor

Lokathor commented Nov 12, 2019

the UCG docs currently document that such a layout is the real layout, but that is an unstable implementation detail and subject to change etc etc.

@comex
Copy link

comex commented Nov 12, 2019

You can create a null trait object by first creating a null pointer to a sized type, then casting or coercing to the unsized pointer.

In this case the vtable pointer would be valid and non-null, though.

@cuviper
Copy link
Member

cuviper commented Nov 12, 2019

You can create a null trait object by first creating a null pointer to a sized type, then casting or coercing to the unsized pointer.

In this case the vtable pointer would be valid and non-null, though.

Yes, I meant that in reply to "how can I create a null/dangling pointer with a valid metadata?"

@gnzlbg
Copy link
Contributor

gnzlbg commented Nov 13, 2019

the UCG docs currently document that such a layout is the real layout, but that is an unstable implementation detail and subject to chamge etc etc.

When the UCGs get RFC'ed, this layout becomes guaranteed for the cases mentioned in the document at least (e.g. no multi-trait objects).

@CAD97
Copy link

CAD97 commented Mar 12, 2021

Accepted RFC#2580 Pointer Metadata is currently written such that all *const dyn Trait must have a valid usable vtable pointer (at least for getting layout) as a safety invariant. (Pointers having a safety invariant is... weird, but I suppose acceptable?)

Specifically, it provides the API

pub fn metadata<T: ?Sized>(ptr: *const T) -> <T as Pointee>::Metadata;
pub struct DynMetadata<DynTrait: ?Sized> { ... }
impl<DynTrait> DynMetadata<DynTrait> {
    pub fn size(self) -> usize;
    pub fn align(self) -> usize;
    pub fn layout(self) -> alloc::Layout;
}

This API does only mandate a safety invariant on pointer metadata, but it is at least interesting in the context of this discussion to note that it applies to raw pointers.

@RalfJung
Copy link
Member Author

That sounds like it could still make a bunch of existing code unsound since "raw pointers do not have a safety invariant" seems like a reasonable assumption people would make.

@RalfJung
Copy link
Member Author

RalfJung commented Aug 8, 2023

Status update: the safety invariant (not validity invariant) for wide raw pointer metadata are pretty much fixed at this point:

  • slices: can be any usize (we have safe ptr::slice_from_raw_parts but unsafe size_of_val_raw)
  • dyn: must be a valid vtable (so that we can have safe dyn trait upcasting)

However the validity invariants can of course be more liberal than that.

@RalfJung
Copy link
Member Author

With rust-lang/rust#124220, Miri now enforces the validity invariant on dyn trait pointers and references as: must point to a vtable for the right trait.

My current inclination is that we should use very liberal validity invariants for metadata of wide raw pointers, which matches the pointer itself: it has to be initialized, and that's it. This means we have to get rid of the niche in wide raw ptr vtable pointers.

Meanwhile, for references we should go as strong as possible: for dyn Trait, require the vtable to be for the right trait; for slices, require the full size of the type (unsized slice tail plus the statically sized prefix) to fit into isize::MAX.

@RalfJung
Copy link
Member Author

I have opened #516 to track the remaining question here, which is about vtable pointers.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-validity Topic: Related to validity invariants meeting-proposed Proposed to be discussed at a future t-opsem meeting S-pending-design Status: Resolving this issue requires addressing some open design questions
Projects
None yet
Development

No branches or pull requests