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

Where to document allocation size upper bound? #465

Closed
joshlf opened this issue Sep 28, 2023 · 46 comments
Closed

Where to document allocation size upper bound? #465

joshlf opened this issue Sep 28, 2023 · 46 comments

Comments

@joshlf
Copy link

joshlf commented Sep 28, 2023

It's common knowledge that a "Rust object" or "Rust allocation" can't have a size which overflows isize. This is relied upon in a lot of APIs such as the raw pointer add method. However, the only place it seems to be documented as a general property is on the reference page for numeric types:

The isize type is a signed integer type with the same number of bits as the platform's pointer type. The theoretical upper bound on object and array size is the maximum isize value. This ensures that isize can be used to calculate differences between pointers into an object or array and can address every byte within an object along with one byte past the end.

I see a few issues with this description:

  • Being on the page for numeric types makes this text not that discoverable for people looking for general guarantees about types and allocations.
  • It uses imprecise language: what are "objects" and "arrays"? Is the latter used in the sense of the type system - a [T; N]?
  • Some allocations are neither native Rust objects nor native Rust arrays. E.g., the allocation backing a Vec doesn't have a type (at least not in its API). If it's guaranteed that &T can't refer to an object of more than isize bytes, then vec.as_slice() can't return a reference which violates this guarantee. However, that doesn't prevent the addresses of vec[0] and vec[N] from being more than isize bytes apart. Various Vec APIs strongly hint that this is impossible, but none actually guarantee it, and the Vec top-level docs make no guarantee about the interactions between various APIs (such as the vec[0]/vec[N] problem).

Based on my understanding of the current state of the language, here's a stab at a more complete set of guarantees; do these sound reasonable?

  • For all T, given t: T, the size of t is guaranteed to fit in an isize
  • For all T, given t: &T, the size of t's referent is guaranteed to fit in an isize
  • With respect to non-builtin types like Vec, I could see a few approaches:
    • Each such type documents its own guarantees
    • We define a formal notion of an "allocation", and document that t: T and t: &T are instances of allocations. Beyond that, we leave it up to non-builtin types to document their own guarantees by making reference to the docs for "allocation".
    • We define a formal notion of an "allocation", and make it clear in the definition itself that it covers non-builtin things like Vec. That seems iffy; I'm not sure how you'd formally specify the set of objects that are covered by a definition like this (e.g., do we want to make guarantees about the memory backing a HashMap?).

cc @jswrenn

@RalfJung
Copy link
Member

Don't have time for a full response right now, but note that this is also documented in slice::from_raw_parts, since that is the most obvious place where someone would violate this guarantee.

@CAD97
Copy link

CAD97 commented Sep 28, 2023

It may not be formalized yet, but in discussing I've been using the concept of a Rust Allocated Object to refer to the thing which exists in the abstract machine, provides memory addresses which can be pointed to, and defines what pointer offsets are "inbounds." The RAO refers just to the chunk of allocated memory; remember that memory is untyped and types only exist for typed copies between memory (as far as the AM is concerned).

The usual way to create a RAO is via std::alloc, and those APIs communicate the size <= isize::MAX requirement, and (mostly) enforce it via Layout1. Memory which is allocated externally to Rust but is still dereferencable requires the FFI code to logically create a RAO; the implementation/# target likely provides some (usually implicit) way to promote a region of read/write system memory to a RAO. The limit is also mentioned in size_of_val_raw (unstable).

What we do need to document though is whether creating a RAO with size > isize::MAX is immediate UB or merely unsound, with UB occurring when doing a layout calculation / field projection of overlarge size. (Allocating such RAO is definitely UB with the std allocation functions, thus only possible via FFI.) For simplicity of the model, I would argue to make it immediate UB, and this might be required for targeting LLVM, which will happily merge two inbounds offsets assuming the combined offset won't overflow isize. Plus, such a large allocation can't even be addressed with 64-bit page tables.

Footnotes

  1. I did this smile and made some of my own layout polyfilling code unsound in the process smile

@joshlf
Copy link
Author

joshlf commented Sep 28, 2023

It may not be formalized yet, but in discussing I've been using the concept of a Rust Allocated Object to refer to the thing which exists in the abstract machine, provides memory addresses which can be pointed to, and defines what pointer offsets are "inbounds." The RAO refers just to the chunk of allocated memory; remember that memory is untyped and types only exist for typed copies between memory (as far as the AM is concerned).

The reason I mention t: T and t: &T is that in a lot of the unsafe code I write, that's the starting point: I'm trying to do something with pointers that are derived from a T or &T, and I need to be able to say something like "safe Rust can't produce a T or &T larger than isize, so my code is guaranteed that all offsets.... blah blah blah". I don't actually care about the T itself, just the fact that Rust makes certain guarantees about all values or references-to-values.

For more context, the place this has come up for me recently is in this PR. It adds a Ptr<'a, T> type which is somewhere in between a NonNull<T> and a &'a T or &'a mut T in terms of its invariants. One of its invariants is that the referenced memory region has a size which fits in isize. This is required in places such as this one, where it's a prerequisite for the pointer add method. We need guarantees about T and &T in order to ensure that we're satisfying Ptr's invariants when we construct it here.

@CAD97
Copy link

CAD97 commented Sep 28, 2023

It's unquestionably a soundness requirement that values described by a Rust type (including ?Sized ones) have a size <= isize::MAX. Doing size_of_val for an oversized type is documented to be UB.

I don't really know anywhere better to document this soundness requirement other than size_of_val_raw, slice_from_raw_parts, alloc/Layout, and perhaps the various feature(ptr_metadata) APIs. While the precise validity requirement for RAO carefully managed by pointer is technically undecided, the requirement on types/references is reasonably well documented in all the places it could potentially be violated.

If the primary question here is w.r.t. soundness guarantees, it could merit a docs issue, but it's not particularly actionable for UCG let alone T-opsem.

(But it doesn't hold if you don't point to an actual allocation; it's safe to construct a raw pointer to an oversized slice.)

@joshlf
Copy link
Author

joshlf commented Sep 28, 2023 via email

@RalfJung
Copy link
Member

RalfJung commented Sep 29, 2023

size_of_val seems like the natural place to put the answer to your first two questions. By saying that function will never return a value exceeding isize::MAX, you should have everything you need -- even if you don't physically call that function, you can now rely on the size of any object you hold where you could safely call that function to not exceed isize::MAX.

I'm not sure where to put the answer to the third question.

It may not be formalized yet, but in discussing I've been using the concept of a Rust Allocated Object to refer to the thing which exists in the abstract machine, provides memory addresses which can be pointed to, and defines what pointer offsets are "inbounds."

In #464 we are calling it an "allocation".

What we do need to document though is whether creating a RAO with size > isize::MAX is immediate UB or merely unsound, with UB occurring when doing a layout calculation / field projection of overlarge size.

I think it has to be UB; creating such an allocation (and giving Rust access to it) is a case of mutating the Rust-visible state in a way that is not possible from Rust. The Rust AM has an invariant that all allocations are at most isize::MAX in size; violating such an invariant must be immediate UB.

But of course one could say that when such an allocation is created, really it's just created with size isize::MAX, and the UB occurs on the first access outside that range.

@joshlf
Copy link
Author

joshlf commented Oct 9, 2023

size_of_val seems like the natural place to put the answer to your first two questions. By saying that function will never return a value exceeding isize::MAX, you should have everything you need -- even if you don't physically call that function, you can now rely on the size of any object you hold where you could safely call that function to not exceed isize::MAX.

I don't think that's sufficient because size_of_val can panic. It's not documented on size_of_val itself, but size_of_val_raw's docs say:

an (unstable) extern type, then this function is always safe to call, but may panic or otherwise return the wrong value, as the extern type’s layout is not known. This is the same behavior as size_of_val on a reference to a type with an extern type tail.

I was originally going to put up a PR to add the following to size_of_val's docs:

/// # Safety
///
/// It is guaranteed that `size_of_val` will always return a value which fits in
/// an `isize`. `unsafe` code may rely on this guarantee for its soundness. Note
/// that this amounts to a guarantee that, for all types, `T`, and for all values
/// `t: &T`, `t` references a value whose size can be encoded in an `isize`. This
/// holds because, given a `t: &T`, it is always valid to call `size_of_val(t)`.

However, I realized that this argument is unsound: If size_of_val can panic, then given t: &T, you only know that if size_of_val(t) returns, it will return a value which fits in isize. But you don't know that it will return.

@RalfJung
Copy link
Member

RalfJung commented Oct 10, 2023

However, I realized that this argument is unsound: If size_of_val can panic, then given t: &T, you only know that if size_of_val(t) returns, it will return a value which fits in isize. But you don't know that it will return.

So, we could say

  • When there are (unstable) extern types involved, the function may panic or otherwise return the wrong value.
  • If the function doesn't panic (even if extern types lead to a wrong value), we guarantee that the result fits in an isize.

Until the extern type situation is resolved, this seems the best we can do? Well actually we could do better, we could guarantee that it will panic (probably this has to be a non-unwinding panic) on extern type, and never just return nonsense. IMO that's what we should do, but currently the "panic" part hasn't been implemented yet I think.

@joshlf
Copy link
Author

joshlf commented Oct 11, 2023

Unfortunately I don't think that's sufficient because there are cases where you never actually call size_of_val(t) - you just know that you could. If you actually called size_of_val(t), you could at least argue that your code would diverge rather than misbehaving. But in code that doesn't call it, you can't rely on that argument.

E.g., consider this type:

pub(crate) struct Ptr<'a, T: 'a + ?Sized> {
    // INVARIANTS:
    // - `ptr` addresses a byte range which is not longer than `isize::MAX`
    // (other invariants removed for brevity)
    ptr: NonNull<T>,
    _lifetime: PhantomData<&'a ()>,
}

It has this impl:

impl<'a, T: 'a + ?Sized> From<&'a T> for Ptr<'a, T> {
    fn from(t: &'a T) -> Ptr<'a, T> {
        Ptr { ptr: NonNull::from(t), _lifetime: PhantomData }
    }
}

In order to construct an instance of Ptr which satisfies the field invariant on the ptr field, we need a guarantee that NonNull::from(t) results in a pointer whose referent is a memory region whose length fits in isize. We'd like to say something like "we know t refers to a memory region of no more than isize::MAX bytes because we could call size_of_val(t), which in turn promises to return a size no greater than isize::MAX." However, that argument doesn't work if size_of_val can panic.

Given this limitation, I think we still need a separate location to document the size maximum (unless we can make a stable promise that size_of_val will never panic, in which case this type of reasoning would be sufficient).

@RalfJung
Copy link
Member

RalfJung commented Oct 11, 2023 via email

@joshlf
Copy link
Author

joshlf commented Oct 11, 2023

But where could that be documented? The "alloc" module would make sense but that is really only about heap allocations and we are stating a fact about all allocations...

Yeah so I've been talking this over with @jswrenn, and the conclusion we've come to is that the thing that makes the most sense is to make it a bit validity constraint on &T for all T: ?Sized. Our rationale is that what we're trying to do is the following:

fn foo<T: ?Sized>(t: &T) {
    let ptr = NonNull::from(t);
    // SAFETY: <what do we write here?>
    unsafe { requires_ptr_whose_referent_size_fits_in_isize(ptr) }
}

We need to be able to make an argument whose premise is t: &T and whose conclusion is that t refers to no more than isize::MAX bytes. At first we considered a weaker guarantee like "safe Rust code will never produce a &T which refers to more than isize::MAX bytes", but this on its own isn't sufficient - it doesn't guarantee that unsafe code won't synthesize such a reference. We need to also ban unsafe code from doing this, which is basically what it means to have a bit validity constraint.

We're thinking something like:

For all T: ?Sized, it is unsound to produce a value, t: &T, whose referent is more than isize::MAX bytes in size. Unsafe code may assume that any such t: &T will refer to no more than isize::MAX bytes.

@RalfJung
Copy link
Member

RalfJung commented Oct 11, 2023

"referring to more than isize::MAX bytes" is basically an ill-typed statement. At least if you mean "refer to" in the sense of "there is that much dereferenceable memory behind this pointer". This is independent of whether it's a raw pointer or a reference. There just can't be a contiguous memory range larger than isize::MAX.

A &[u8] with a size of more than isize::MAX is already invalid today because it is dangling, and dangling references are UB. So this doesn't need docs changes.

@joshlf
Copy link
Author

joshlf commented Oct 11, 2023

There just can't be a contiguous memory range larger than isize::MAX.

I agree that this is true in practice, but is it guaranteed anywhere? IIUC that's exactly what we're trying to guarantee here.

A &[u8] with a size of more than isize::MAX is already invalid today because it is dangling, and dangling references are UB. So this doesn't need docs changes.

Oh interesting, I'm not sure where this comes from. How is such a reference dangling?

@RalfJung
Copy link
Member

RalfJung commented Oct 11, 2023

Oh interesting, I'm not sure where this comes from. How is such a reference dangling?

It's dangling because there can't be a memory range large enough for it to point to that would make it non-dangling. :)

I agree that this is true in practice, but is it guaranteed anywhere? IIUC that's exactly what we're trying to guarantee here.

That's what I was asking above -- where should such docs go? This property has nothing to do with references so stating it about references makes no sense. It's a property about what the Rust Abstract Machine considers an "allocated object".

@RalfJung
Copy link
Member

We could add it here maybe? That defines "allocated object". If we say that allocated objects have a maximal size of isize::MAX that should basically cover it?

@joshlf
Copy link
Author

joshlf commented Oct 11, 2023

Oh interesting, I'm not sure where this comes from. How is such a reference dangling?

It's dangling because there can't be a memory range large enough for it to point to that would make it non-dangling. :)

Ah gotcha :)

I agree that this is true in practice, but is it guaranteed anywhere? IIUC that's exactly what we're trying to guarantee here.

That's what I was asking above -- where should such docs go? This property has nothing to do with references so stating it about references makes no sense.

Yeah so I think we're actually on the same page here. I definitely agree that what we're really talking about is a property of "allocations" or "memory regions" or some similar concept. However, The Reference doesn't currently define these concepts, while it already defines the concept of a reference. Our thinking behind making this a bit validity invariant on &T is just that it'd require a much smaller change to The Reference as compared to introducing and defining an entirely new concept.

We could add it here maybe? That defines "allocated object". If we say that allocated objects have a maximal size of isize::MAX that should basically cover it?

Ah interesting, yeah that's a good start! I'll be honest it feels weird that that's in ptr rather than in the Reference since it's documenting a property that applies to all of Rust rather than just to things in the ptr module, but that's roughly what we need. In terms of content, do you think it'd be appropriate to just beef up that section by adding something like the following?

It is guaranteed that an allocated object never spans more than isize::MAX bytes. For all types, T: ?Sized, and for all t: &T, it is guaranteed that t refers to a subset of a single allocated object.

Obviously let me know if you think there are better words/phrases to use for concepts like "spans" and "refers to", etc.

@RalfJung
Copy link
Member

We have many things in the lib docs that probably should also be in the reference -- but my general assumption is that hardly anyone reads the reference, so libs docs is usually where improvements go. Ongoing examples of that are rust-lang/rust#115476 and rust-lang/rust#115577.

@joshlf
Copy link
Author

joshlf commented Oct 12, 2023

We have many things in the lib docs that probably should also be in the reference -- but my general assumption is that hardly anyone reads the reference, so libs docs is usually where improvements go. Ongoing examples of that are rust-lang/rust#115476 and rust-lang/rust#115577.

Yeah that makes sense. Obviously completely orthogonal to the present discussion, but I wonder whether it'd be reasonable to put things in the Reference but then refer to them in the obvious places so they're just as discoverable.

It is guaranteed that an allocated object never spans more than isize::MAX bytes. For all types, T: ?Sized, and for all t: &T, it is guaranteed that t refers to a subset of a single allocated object.

Does this seem like reasonable language for the ptr module docs section on allocated objects? I can put up a PR.

@RalfJung
Copy link
Member

RalfJung commented Oct 12, 2023

The first sentence sounds like something we could add there, yes.

The part about references is a consequence of that. That seems to be better located here (but that page doesn't seem to talk about validity requirements at all currently) and/or here. (And of course it should be generalized to also apply to &mut.)

Yeah that makes sense. Obviously completely orthogonal to the present discussion, but I wonder whether it'd be reasonable to put things in the Reference but then refer to them in the obvious places so they're just as discoverable.

Reasonable, yes. That's just less convenient to do.^^ It needs a reference PR, waiting for the submodule to be updated, and then a libs PR... and often it's also not at all clear where in the reference something would go. The standard library has these nice keyword and primitive type documentation pages, do we really want to duplicate all that in the reference? E.g. for unsafe we currently have some stuff in the reference and some in the keyword docs and they are covering the same material to a large extent and it's all rather messy...

@joshlf
Copy link
Author

joshlf commented Oct 12, 2023

The first sentence sounds like something we could add there, yes.

Sounds good; put up a PR: rust-lang/rust#116675

The part about references is a consequence of that. That seems to be better located here (but that page doesn't seem to talk about validity requirements at all currently) and/or here. (And of course it should be generalized to also apply to &mut.)

Sounds good; put up a PR: rust-lang/rust#116677

Yeah that makes sense. Obviously completely orthogonal to the present discussion, but I wonder whether it'd be reasonable to put things in the Reference but then refer to them in the obvious places so they're just as discoverable.

Reasonable, yes. That's just less convenient to do.^^ It needs a reference PR, waiting for the submodule to be updated, and then a libs PR... and often it's also not at all clear where in the reference something would go. The standard library has these nice keyword and primitive type documentation pages, do we really want to duplicate all that in the reference? E.g. for unsafe we currently have some stuff in the reference and some in the keyword docs and they are covering the same material to a large extent and it's all rather messy...

Yeah, that's very understandable. I think my general worry is that, with concepts spread out across a lot of documentation, we risk losing track of what we've technically promised and thus breaking promises made in the past. The more that code authors have to language lawyer as opposed to just cite a straightforward guarantee made by documentation, the more likely that a guarantee is technically implied by the docs but not in a way that's obvious to editors of those docs or language/compiler authors. It'd be ideal if terms were formally defined where possible (where "formally" just means "a definition exists at a place that can be linked to") and uses of those terms were always linked so that broken links could be caught automatically. It sounds like we're far away from that state, though.

@RalfJung
Copy link
Member

Yeah, that's very understandable. I think my general worry is that, with concepts spread out across a lot of documentation, we risk losing track of what we've technically promised and thus breaking promises made in the past.

Fully agreed, I wasn't claiming that what we are doing is good.

@workingjubilee
Copy link
Member

Documenting the keywords in std's API docs was a fairly arbitrary choice. They could just as easily be documented in the reference.

@joshlf
Copy link
Author

joshlf commented Oct 27, 2023

Follow-up question that's related to this discussion: do we intend to guarantee that, for a slice DST, an instance with 0 elements always has a size which fits in isize::MAX? This came up today in rust-lang/rust#69835 (comment)

If we intend to guarantee this, where would be a good place to document it? I can put up a PR.

@LegionMammal978
Copy link

As a note, I was performing some tests to ensure that the status quo is that 0-length slice ZSTs are always within isize::MAX bytes (i.e., both the header and the trailing padding are counted in the compiler's maximum-type-size check), but I unexpectedly ran into rust-lang/rust#117265, finding that padding isn't counted even for regular types.

@RalfJung
Copy link
Member

I don't know if we currently guarantee that (the layout computation code is largely a black box to me), but it does sound like a sensible thing to guarantee.

@joshlf
Copy link
Author

joshlf commented Oct 27, 2023

I don't know if we currently guarantee that (the layout computation code is largely a black box to me), but it does sound like a sensible thing to guarantee.

Do you have opinions on where such a thing should be documented?

@RalfJung
Copy link
Member

The [T] type maybe? After all it's about types that have that as their tail.

jhpratt added a commit to jhpratt/rust that referenced this issue May 14, 2024
jhpratt added a commit to jhpratt/rust that referenced this issue May 14, 2024
rust-timer added a commit to rust-lang-ci/rust that referenced this issue May 14, 2024
Rollup merge of rust-lang#116675 - joshlf:patch-10, r=scottmcm

[ptr] Document maximum allocation size

Partially addresses rust-lang/unsafe-code-guidelines#465
@RalfJung
Copy link
Member

@joshlf https://doc.rust-lang.org/nightly/std/ptr/index.html now documents that an allocation is at most isize::MAX bytes. Could you remind me again what the motivation is for further documenting in rust-lang/reference#1482 that the "minimal size" of all types is at most isize::MAX? That guarantee seems to be hard to write down precisely (since it depends on what exactly we monomorphize), so I am trying to figure out why that even is a question we have to make a guarantee about.

@LegionMammal978
Copy link

LegionMammal978 commented May 29, 2024

Could you remind me again what the motivation is for further documenting in rust-lang/reference#1482 that the "minimal size" of all types is at most isize::MAX?

To lay it out explicitly: suppose you have a custom slice DST, and you want to find the byte offset of the unsized tail from the beginning of the struct.

Unfortunately, offset_of!() does not support DST tails: it only supports fields within the static prefix. Therefore, you must form a value of the DST somewhere in memory (of any length), take a pointer to the unsized tail, and manually compute the byte offset.

However, you cannot simply do this with a null DST pointer, since taking an invalid addr_of!() is forbidden. Therefore, you must create a valid allocation with the proper size.

However, you can't stably obtain a large-enough allocation without already having an instance, since that requires size_of_val(). Therefore, you must wait for size_of_val_raw() to stabilize, then use that on a null DST pointer to obtain the allocation size.

However, calling size_of_val_raw() is UB if the size of the entire value is greater than isize::MAX. Therefore, you must hope that if you make your null DST pointer as small as possible (length 0), it will be small enough to pass into size_of_val_raw(). Then you can use that to create an actual allocation, take the addr_of!() the unsized tail, and compute its byte offset.

(Note that this guarantee still isn't sufficient for dynamically constructing repr(Rust) slice DSTs of length greater than 0, since they can have an unbounded amount of padding!)

@RalfJung
Copy link
Member

Wow, what a rabbit hole.^^

To lay it out explicitly: suppose you have a custom slice DST, and you want to find the byte offset of the unsized tail from the beginning of the struct.

What exactly is a "custom slice DST"? We don't have custom DST. Do you mean an unsized type whose unsized tail is a slice?

Unfortunately, offset_of!() does not support DST tails: it only supports fields within the static prefix.

Since the alignment is statically known for slices, it should be fairly easy to add support for unsized fields with slice tail to offset_of!. If that avoids the need for rust-lang/reference#1482 then that honestly seems worth it.^^

However, calling size_of_val_raw() is UB if the size of the entire value is greater than isize::MAX. Therefore, you must hope that if you make your null DST pointer as small as possible (length 0), it will be small enough to pass into size_of_val_raw(). Then you can use that to create an actual allocation, take the addr_of!() the unsized tail, and compute its byte offset.

Ah, so the entire point of rust-lang/reference#1482 is to ensure that the precondition for size_of_val_raw holds?

That is easier to guarantee than rust-lang/reference#1482. For instance we could just say that if the slice metadata is 0, then size_of_val_raw is safe to call -- either the call will be optimized out entirely or the compiler guarantees that the total size fits in isize::MAX.

@workingjubilee
Copy link
Member

agreed that "I want to do something that should be obvious with the standard library but I can't because (stuff)" seems like a request for a library enhancement first and a justification for that enhancement second.

@LegionMammal978
Copy link

LegionMammal978 commented May 31, 2024

What exactly is a "custom slice DST"? We don't have custom DST. Do you mean an unsized type whose unsized tail is a slice?

Whatever you want to call it. I mean a user-defined type that is a DST with a (possibly wrapped) slice tail, not a type that is a DST with user-defined metadata. If such a type is repr(Rust), or if it is repr(C) and you do not know all of its fields, you end up with this dilemma, where you must know the layout beforehand to learn anything about the layout soundly. (Except that fields before the tail can now be queried with offset_of!().)

Ah, so the entire point of rust-lang/reference#1482 is to ensure that the precondition for size_of_val_raw holds?

That is the primary purpose, from my understanding of the zerocopy use case.

That is easier to guarantee than rust-lang/reference#1482. For instance we could just say that if the slice metadata is 0, then size_of_val_raw is safe to call -- either the call will be optimized out entirely or the compiler guarantees that the total size fits in isize::MAX.

Regardless of the wording, this only fixes the narrow case of determining the offset of the slice tail. With such a guarantee, one still can't soundly create repr(Rust) DSTs with slice tails of length greater than 0, except via unsizing coercions. To allow this, either the additional padding following the tail of a repr(Rust) DST could be determined by a specified algorithm (i.e., pad to the alignment of the prefix), or a fallible version of size_of_val_raw could be added (as I initially suggested in rust-lang/rust#69835 (comment)).

@RalfJung
Copy link
Member

Whatever you want to call it. I mean a user-defined type that is a DST with a (possibly wrapped) slice tail, not a type that is a DST with user-defined metadata.

I see, thanks. I usually call them something like "slice-tail DST" or "unsized type with a slice tail" or so. I don't know of short standard terminology for them.

Regardless of the wording, this only fixes the narrow case of determining the offset of the slice tail. With such a guarantee, one still can't soundly create repr(Rust) DSTs with slice tails of length greater than 0, except via unsizing coercions.

To create one without unsizing coercions, you need to make layout assumptions anyway, don't you?
If you are willing and able to do that, then you can compute the total size of the type as the size with length 0, plus N * the element size of the slice tail. Or does that not work because of things being rounded up to alignment somewhere?

With the length=0 guarantee, you can implement offset_of! in userland. I don't see how rust-lang/reference#1482 gives you any more than that. So if that's not sufficient, how would rust-lang/reference#1482 be sufficient?

@LegionMammal978
Copy link

If you are willing and able to do that, then you can compute the total size of the type as the size with length 0, plus N * the element size of the slice tail. Or does that not work because of things being rounded up to alignment somewhere?

Indeed, padding is the problem, as I demonstrated at rust-lang/rust#69835 (comment). The layout for a DST with a slice tail looks like:

  1. The fields of the static prefix, with possible padding before and between them.
  2. At least enough padding to match the alignment of the slice tail.
  3. The consecutive elements of the slice tail, with no padding between.
  4. At least enough padding to match the alignment of the entire DST.

If the DST is repr(C), then the padding is as small as possible, so you can compute the overall size for any given length. However, if the DST is repr(Rust), then you obtain as few guarantees as possible.

Before offset_of!() was added, this technically meant that you don't know whether the tail appears before or after the prefix, since the layout could vary for each length. However, the stabilization of a constant offset_of!() for fields in the prefix implies that the tail is always at the end, even for repr(Rust) DSTs.

The bigger issue is the final padding after the slice tail. Since repr(Rust) has few guarantees, there is no guarantee on how little or much padding might appear in this position. The amount of padding also varies dynamically, depending on the slice length. Therefore, a malicious repr(Rust) layout algorithm could make every slice length past 1 require so much padding that the overall size would become greater than isize::MAX.

Thus, one solution would be to say that the padding after the slice tail (or perhaps any DST tail) is the minimum necessary to reach the alignment of the entire DST, even if it is repr(Rust). Combined with the ability to take the offset_of!() the tail, this would be sufficient to calculate the proper layout.

@RalfJung
Copy link
Member

Given that you're worried about trailing padding for the non-empty-slice case, how would rust-lang/reference#1482 help?

@CAD97
Copy link

CAD97 commented May 31, 2024

(Using struct WithTail<T: ?Sized> { /* fields */, pub tail: T })

Unsizing coercions already require WithTail<[T; N]> and WithTail<[T]> to have identical layout, so forwarding that guarantee makes sense. Although I suppose that alone still doesn't preclude extra padding after the tail slice that monotonically increases1 with slice length.

Existence of after-tail padding also raises an interesting follow-up question of if/when it is valid to split &mut WithTail<[T]> into (&mut WithTail<[T]>, &mut [T]) — if WithTail<[T]> has trailing padding that aliases the following T, that's a problem for the aliasing requirements.

For manipulation of user defined slice-tailed struct to be in any way reasonable, I think it would be a good idea to guarantee that the layout of WithTail<[T]> is exactly Layout::from_size_align(offset_of!(WithTail<[T; 0]>, tail), align_of::<WithTail<[T; 0]>>())?.extend(Layout::array::<T>(len))?.pad_to_align(), also extending that same guarantee to non-generic slice-tailed structures.

Where/how to communicate that guarantee I'm not sure, but that's effectively the exact guarantee needed to make manual manipulation of slice-tailed types possible.

Footnotes

  1. Monotonicity is desirable to be able to slice &WithTail<[T; {N+M}]> to &WithTail<[T; N]>.

@RalfJung
Copy link
Member

RalfJung commented Jun 1, 2024

For manipulation of user defined slice-tailed struct to be in any way reasonable, I think it would be a good idea to guarantee that the layout of WithTail<[T]> is exactly Layout::from_size_align(offset_of!(WithTail<[T; 0]>, tail), align_of::<WithTail<[T; 0]>>())?.extend(Layout::array::(len))?.pad_to_align(), also extending that same guarantee to non-generic slice-tailed structures.

I don't think that property is even true. Consider (on x86-64)

#[repr(C)]
struct MyDST(u64, u8, [u8]);

This has alignment 8, and the last field is at offset 9. With length 0, the total size is 16. With length 7, the total size is still 16.

@CAD97
Copy link

CAD97 commented Jun 1, 2024

I don't see any contradiction there. Note that I specifically built the prefix layout with size set as the offset of the tail field, not the size of the type with zero-sized tail. A zero length tail ends up as Layout(9, 8).extend(Layout(0, 1)).pad_to_align() == Layout(16, 8) and a 7 length tail Layout(9, 8).extend(Layout(7, 1)).pad_to_align() == Layout(16, 8).

@RalfJung
Copy link
Member

RalfJung commented Jun 1, 2024 via email

@LegionMammal978
Copy link

LegionMammal978 commented Jun 1, 2024

Given that you're worried about trailing padding for the non-empty-slice case, how would rust-lang/reference#1482 help?

It is necessary to determine the alignment of the entire DST. With repr(Rust), a struct can be arbitrarily more-aligned than its fields. (Or we might be writing a macro that isn't aware of all the fields in the prefix.) Therefore, to determine the alignment of the DST, align_of_val_raw() is needed. But that function has the same isize::MAX restriction that size_of_val_raw() does, so we need the guarantee that it's safe to probe the layout at length 0.

From there, the alignment of the entire DST, the byte offset of the tail, and the layout of the tail's elements are sufficient to compute the size of the entire DST for any length, assuming that trailing padding is minimized.

@RalfJung
Copy link
Member

RalfJung commented Jun 2, 2024

Okay so there's still an assumption here that the alignment doesn't change as the length goes up?
That looks like the "size_of_val_raw is fine for length 0" approach would suffice, though? Above you seemed to say that is not the case. But then I still don't see how rust-lang/reference#1482 helps if "size_of_val_raw is fine for length 0" is not enough.

Honestly I'd rather spend all this time and effort on the proper solution(s) -- offset_of! for slice tail fields, and a checked layout computation method that takes <T as Pointee>::Metadata. (But adding "size_of_val_raw is fine for length 0" is relatively cheap so I am not opposed to that either.)

@LegionMammal978
Copy link

LegionMammal978 commented Jun 3, 2024

That looks like the "size_of_val_raw is fine for length 0" approach would suffice, though? Above you seemed to say that is not the case. But then I still don't see how rust-lang/reference#1482 helps if "size_of_val_raw is fine for length 0" is not enough.

Sorry if I've been unclear. For the offset of slice tail fields (the zerocopy use case), either "proper offset_of!() support", "out-of-bounds addr_of!()", or "length-0 size_of_val_raw()" is sufficient. For constructing DSTs with not-completely-known layout, "fallible Layout::for_value_raw()" (i.e., your Metadata computation) is sufficient, and "length-0 align_of_val_raw()" + "minimal trailing padding" is also sufficient.

@RalfJung
Copy link
Member

RalfJung commented Jun 5, 2024

Okay, so I propose someone prepare a PR for length-0 size_of_val_raw. offset_of on slice tail fields and fallible layout computation are reasonable feature requests; it may be worth filing issues for them.

@RalfJung
Copy link
Member

RalfJung commented Jun 8, 2024

I have opened two PRs for these steps:

I will close the issue now, since the original question in the issue title has been answered and the issue description is quite outdated at this point. Please open a new issue if there is still an open question to resolve/track.

@RalfJung RalfJung closed this as completed Jun 8, 2024
matthiaskrgr added a commit to matthiaskrgr/rust that referenced this issue Jul 24, 2024
size_of_val_raw: for length 0 this is safe to call

For motivation, see rust-lang/unsafe-code-guidelines#465, specifically around [here](rust-lang/unsafe-code-guidelines#465 (comment)).
Cc `@rust-lang/opsem`
rust-timer added a commit to rust-lang-ci/rust that referenced this issue Jul 24, 2024
Rollup merge of rust-lang#126152 - RalfJung:size_of_val_raw, r=saethlin

size_of_val_raw: for length 0 this is safe to call

For motivation, see rust-lang/unsafe-code-guidelines#465, specifically around [here](rust-lang/unsafe-code-guidelines#465 (comment)).
Cc `@rust-lang/opsem`
github-actions bot pushed a commit to rust-lang/miri that referenced this issue Jul 25, 2024
size_of_val_raw: for length 0 this is safe to call

For motivation, see rust-lang/unsafe-code-guidelines#465, specifically around [here](rust-lang/unsafe-code-guidelines#465 (comment)).
Cc `@rust-lang/opsem`
joshlf added a commit to google/zerocopy that referenced this issue Aug 6, 2024
Previously, we needed to rely on the fact that the instance of any valid
Rust type with 0 elements has a size (in number of bytes) which is not
greater than `isize::MAX`. Providing this as a guarantee turned out to
be controversial. [1]

This was made possible by rust-lang/rust#126152.

[1] rust-lang/unsafe-code-guidelines#465 (comment)
joshlf added a commit to google/zerocopy that referenced this issue Aug 6, 2024
Previously, we needed to rely on the fact that the instance of any valid
Rust type with 0 elements has a size (in number of bytes) which is not
greater than `isize::MAX`. Providing this as a guarantee turned out to
be controversial. [1]

This was made possible by rust-lang/rust#126152.

[1] rust-lang/unsafe-code-guidelines#465 (comment)
github-merge-queue bot pushed a commit to google/zerocopy that referenced this issue Aug 6, 2024
Previously, we needed to rely on the fact that the instance of any valid
Rust type with 0 elements has a size (in number of bytes) which is not
greater than `isize::MAX`. Providing this as a guarantee turned out to
be controversial. [1]

This was made possible by rust-lang/rust#126152.

[1] rust-lang/unsafe-code-guidelines#465 (comment)
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

5 participants