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

What do we say about the equality of pointers in constants, vtables, and function pointers? #522

Open
RalfJung opened this issue Aug 4, 2024 · 19 comments

Comments

@RalfJung
Copy link
Member

RalfJung commented Aug 4, 2024

Functions, vtables, and consts do not have a unique stable address, leading to interesting problems. We've so far just always said "yeah we don't make any guarantees there", but (a) that could probably be documented better, (b) Miri doesn't actually make this non-deterministic so it can easily miss issues here, and (c) maybe we could/should do better in some cases.

function address equality

vtable equality

const address equality

@Diggsey
Copy link

Diggsey commented Aug 4, 2024

I think the "ideal" case is that only one vtable would exist for a given type/trait pair, but I just don't think that's going to be possible:

  • Solving at the linker level requires support for weak symbols or similar, and I don't believe these are fully supported on all platforms, particularly when dynamic linking is involved... Maybe someone more familiar with linkers could provide a solution though...
  • Solving in the compiler would require runtime machinery (some kind of global vtable index) which I think would go against Rust's design philosophy, and would be difficult to make performant.

The next best thing would be to make wide pointer comparisons useful at least - if we can't make comparisons on vtables useful, then we must not consider vtables as part of any comparison.

IMO a "useful" pointer comparison obeys the following:

  • It must be a "more strict" version of Eq. That is, if pointer comparison returns true and the type implements Eq, then the Eq implementation should return true (Eq is documented as being reflexive, so this just requires our pointer comparison to not return false positives). This means pointer comparison can be used to short-cut Eq evaluation.
  • It should be deterministic based on the abstract machine state (eg. not rely on implementation details such as what codegen unit that value came from, etc.)

There are four cases to consider:

  1. We are comparing slice pointers.
    The slice length is meaningful, and so there is no problem with including it in the comparison. Not doing so would result in two prefix-sharing slices comparing equal even though they are different.

  2. We are comparing trait object pointers.
    The vtable pointer is not meaningful. We can't just ignore it because one object could be a field within the other, eg.
    struct Foo { bar: Bar } impl Trait for Foo {} impl Trait for Bar {} - we don't want &foo as &dyn Trait == &foo.bar as &dyn Trait, since they are completely different types.

    Clearly the compiler should at least warn about this case (and I believe currently does do so). What should we do if the user ignores the warning? There are two "good" options to me: a) only compare the pointer. b) always return false from the comparison.

  3. We are comparing pointers to an unknown ?Sized type (could be a slice or a trait object, we don't know)
    We have to warn in this case, because we don't know if the comparison is sensible. If the warning is ignored, the behaviour should be the same as (1) or (2) depending on whether it's a slice or a trait object.

  4. We are using ptr_eq on a wide smart pointer (eg. Rc, Arc, etc.) This differs from (2) because the "sub-object" problem cannot occur: the pointer alone is sufficient to determine whether two things are equal. For this reason I think ptr_eq on these types should only look at the pointer, ensuring comparison is always well-defined (this should be clearly spelled out in the documentation though).

@RalfJung
Copy link
Member Author

RalfJung commented Aug 4, 2024 via email

@chorman0773
Copy link
Contributor

Reposting from the miri issue:

TBH, I'd prefer that const items that contain references/pointers have unique address for those items, IE. a const item should always evaluate to an identical expression*, not just an equal one.

I was bitten by the lack of uniqueness when writing a macro producing a (start,end) pair of pointers from a string literal at compile time (the macro itself has been changed, but the original issue was quite annoying).

*Associated consts in traits and generic inherent impl blocks pose an issue for this, but free constants and associated constants in non-generic impl blocks do not.

@chorman0773
Copy link
Contributor

Addressing the note about deduplication, for non generic consts, generating such constants approxiately like the following would work regardless of platform and linkage mode:

pub const FOO: &str = "Hello World!";

// Becomes
pub static FOO_value: str = *"Hello World!"; // psuedo-syntax
pub const FOO: &str = &FOO_value;

@thomcc
Copy link
Member

thomcc commented Aug 6, 2024

I'd prefer that const items that contain references/pointers have unique address for those items.

Wouldn't that mean consts like &["foo", "foo", "foo"] would require 3 copies of foo in the binary?

@chorman0773
Copy link
Contributor

chorman0773 commented Aug 6, 2024

It wouldn't affect string literals directly, and unique here I mean it has one address.

IE.

pub const FOO: &str = "foo";

assert!(core::ptr::eq(FOO, FOO));

holds. I don't think we need to say that the addresses are distinct from all other address, just that there is one address when you evaluate the value of a constant that contains a reference or a pointer.

If you have

pub const FOO: &[&str] = &["foo", "foo", "foo"];

Then the array (and thus necessarily each of its elements) would have a single address, but the literals could all be the same address, as could both arrays if you copied the const initializer to another item.

@VorpalBlade
Copy link

Deduplicating constants is an important optimisation, especially for embedded and other highly constrained environments. Same goes for functions (this can even be done in the linker, mold for example has a flag to do this, I don't know if the other linkers do).

Even outside of embedded this helps reduce the cache pressure, which can help performance.

Relying on separate constants of functions with the same contents not getting merged would be unfortunate, especially since it is quite easy to create these by accident with monomorphization.

It should also be valid to merge the backing data for partially overlapping constant data (e.g. the string constants "foo" and "foobar" could share a prefix, just have different metadata for the slice lengths).

@RalfJung
Copy link
Member Author

RalfJung commented Aug 7, 2024

Addressing the note about deduplication, for non generic consts, generating such constants approxiately like the following would work regardless of platform and linkage mode:

I'm not sure I like having rules that explicitly depend on whether the const is "non-generic". That's a pretty surprising non-continuity in behavior. Generally, the expectation is that if you care about having a unique address, you should use a static. So what I would want is that you can write the following:

pub static FOO: &str = "Hello World!";

// Different crate
pub const FOO_COPY: &str = crate_a::FOO;

assert!(ptr::eq(FOO, FOO_COPY));

However, for annoying and counter-intuitive reasons, that is not currently what happens. FOO will be evaluated once and the result stored with the crate that defines FOO. However that result is just an AllocId referring to memory that stores the bytes of the string. AllocId is a per-crate identifier, it has no meaning "globally". When generating code for crate_a, we notice the static referencing that AllocId, so we also generate some anonymous read-only allocation for the string contents and make FOO point to that. If we now have a constant like FOO_COPY, FOO_COPY's value will be "the same" AllocId but not the same number: since AllocId are per-crate -- as rlibs are loaded, Allocid of other crates are re-mapped into the local crate. When we codegen a value for FOO_COPY we don't know that this AllocId has already been codegen'd somewhere inside crate_a, so we generate another anonymous read-only allocation with the same contents.

@oli-obk made things slightly better in rust-lang/rust#121644, but it doesn't help in all cases and I think it doesn't help for string literals. I wonder if we should entirely revamp how AllocId works to avoid this... that's more of a t-compiler topic though so I'll open a new issue. EDIT: That's rust-lang/rust#128775.


Deduplicating constants is an important optimisation

Yes, but optimizations are off-topic here. We should be doing our best to do this optimization.

But this issue is about whether we guarantee that deduplication occurs, in the sense that unsafe code may rely on it for correctness. There, the answer is currently "no".

It should also be valid to merge the backing data for partially overlapping constant data (e.g. the string constants "foo" and "foobar" could share a prefix, just have different metadata for the slice lengths).

That's a good question -- I agree that for read-only data, this should be considered a valid optimization.

@VorpalBlade
Copy link

Yes, but optimizations are off-topic here

Doesn't what optimisations we want to be able to perform inform what operational semantics we want (as well as other concerns such as lack of footguns etc of course).

As I'm not well versed in the formal methods (but have definite opinions based on working with small embedded microcontrollers, as well as command line tooling) I cannot necessarily express myself in the opsem terms, only in what I as a user need (you often need to compile with size optimisations to even be able to fit the code onto your microcontroller for example).

But this issue is about whether we guarantee that deduplication occurs, in the sense that unsafe code may rely on it for correctness. There, the answer is currently "no".

Indeed, for a debug build it makes sense to not spend the effort to try to deduplicate constants or functions for example, you want something ready to run as quickly as possible there.

I would for size optimised builds also like to see non-generic read only data merged where aggressively where possible (again, the embedded use case). For example if two different panic strings just happen to be the same (e.g. "unreachable") they should be merged. That sort of thing happens more often than you might expect.

So as little guarantees of uniqueness as possible is my preference, unlike what I understand @chorman0773 wants. Again for embedded as well as for cache pressure on non-embedded this is important.

And for the other direction, Rust shouldn't guarantee merging either (as that might slow down the debug/incremental/iterative workflow).

@chorman0773
Copy link
Contributor

Generally, the expectation is that if you care about having a unique address, you should use a static. So what I would want is that you can write the following:

My problem is that I find it unintuive that a const item won't evaluate to exactly the same value every time it is used. I have been tripped by this in unsafe code, and I doubt that I'm the only one. And indeed, in some cases, it isn't possible to create a static item - you can't have a static str for example, or an array you don't know the length of.
I can agree to a weaker guarantee that works for generic const items as well as non-generic consts, but I don't think that "Every Evaluation produces a different pointer to a new AllocId" is good semantics, and I believe that stronger semantics here are possible (even on PE platforms that don't have runtime symbol deduplication between DSOs).

Again for embedded as well as for cache pressure on non-embedded this is important.

To be clear, when I say uniqueness, I mean in the sense that the value of the const is unique, IE. it has exactly one value, regardless of how many times the const item is evaluated. I don't mean that the address is distinct from any other allocation.

To demonstrate

pub const FOO: &str = "Hello World!";

pub const BAR: &str = "Hello World!";

assert!(core::ptr::eq(FOO, FOO)); // Guaranteed to hold, can be relied upon by `unsafe` code

// assert!(!core::ptr::eq(FOO, BAR)); // Not guaranteed  to hold or to fail.

I would like the first assert to hold (and for greater certainty, for the two pointers to be AM-identical, not just identical under eq), but I don't care whether or not the second assert (the one that's commented out) will hold or not.

@RalfJung
Copy link
Member Author

RalfJung commented Aug 7, 2024

My problem is that I find it unintuive that a const item won't evaluate to exactly the same value every time it is used.

This is necessarily the case for consts depending on generics. (The usual problem: it could get instantiated with the same generics in two different downstream crates that know nothing about each other, there's no way they can coordinate to produce the same result.) Carving out a special case for non-generic consts doesn't fundamentally make things any more intuitive, it just makes it harder to notice the strange const semantics, so I don't view that as a good fix. I think it is much easier to teach "if you care about guaranteed unique addresses, use statics" than "you can get guaranteed unique addresses if you make sure your const satisfies the following requirements (and better make sure that does not change in future refactors)".

Seems like you are saying it is better to draw the line between generic and non-generic consts, while I think it is better to draw the line between statics and consts. I can see people prefer either option, this comes down to a fairly subjective judgment call.

@bjorn3
Copy link
Member

bjorn3 commented Aug 7, 2024

Quoting the reference page for constant items: (emphasis mine)

A constant item is an optionally named constant value which is not associated with a specific memory location in the program. Constants are essentially inlined wherever they are used, meaning that they are copied directly into the relevant context when used. This includes usage of constants from external crates, and non-Copy types. References to the same constant are not necessarily guaranteed to refer to the same memory address.

And quoting the reference page for static items: (emphasis mine)

A static item is similar to a constant, except that it represents a precise memory location in the program. All references to the static refer to the same memory location.

The difference between the documented behavior for consts and statics is that the former may produce a result with a different identity (different location of the value and referenced values) but still structurally equivalent, while the latter is guaranteed to produce a result with a fixed identity. Every other difference between the two follows from the different guarantees between consts and statics. The reason statics aren't allowed to be generic is because a fixed identity is not possible to guarantee with generics.

@chorman0773
Copy link
Contributor

chorman0773 commented Aug 7, 2024

I think it is much easier to teach "if you care about guaranteed unique addresses, use statics"

The issue that I brought up is that there are cases you cannot use a static (generics is one of them, but also if you need a reference to an unsized type without knowing the concrete type syntactically) that you may need or want a guaranteed unique address.

I also don't necessarily want to turn off deduplication, which a static would do.

The case which I had needed this was producing a *const u8 to the begin and end of a const str slice. For soundness reasons, they need to be inbounds of each other. One way I was able to do so without violating the static contraints of the language (at the time the macro was written) was evaluating evaluating a const item that contained the string literal multiple times ultimately. As mentioned, I'd be fine with a scope limited guarantee (such as within a given evaluation of a function), but there is and will be code that cannot use a static item and has no option other than to require such a guarantee.

@Diggsey
Copy link

Diggsey commented Aug 7, 2024

The case which I had needed this was producing a *const u8 to the begin and end of a const str slice.

Why doesn't this work?

const fn test() -> &'static str {
    "Hello, world!"
}

#[derive(Debug)]
struct RawPtr(*const u8);
unsafe impl Sync for RawPtr {}

static FOO: &str = test();
static BAR: RawPtr = RawPtr(FOO as *const str as *const u8);
static BAR2: RawPtr = RawPtr(unsafe {BAR.0.offset(FOO.len() as isize)});

fn main() {
    println!("{FOO:?} {BAR:?} {BAR2:?}");
}

@chorman0773
Copy link
Contributor

This was in the context of a macro that could be expanded in any number of const contexts, with ideally arbitrary const expression inputs.

@CAD97
Copy link

CAD97 commented Aug 7, 2024

At a bare minimum, I hope we can guarantee that multiple copies of a single reference within a single constant evaluation could be guaranteed identical to each other, e.g.

const _: () = {
    let a = &0;
    // with 1.82 nightly (2024-08-06 60d146580c10036ce89e)
    assert!(matches!(<*const _>::guaranteed_eq(a, a), None));
};

Carving out a special case for non-generic consts doesn't fundamentally make things any more intuitive, it just makes it harder to notice the strange const semantics,

Generic context const are already separately different in that they're evaluated post-mono, whereas free const are pre-mono, making that bit of odd behavior harder to notice. (E.g. for a nongeneric trait implementation's associated consts.) Yes I'd still prefer this to be fixed and have the const evaluation happen if the type/impl is checked WF, but it does bear mentioning as a related symptom.

But rather than tie constant address stability guarantees to captured generics, I think it's easier to assign to top level versus associated constant items. It's the same thing determining if unnamed const items are allowed. Yeah, it's far from ideal to lose that property if refactoring to an associated name, but maybe it's livable?

Although, otoh, #![feature(generic_const_items)]

Seems like [Connor is] saying it is better to draw the line between generic and non-generic consts, while I think it is better to draw the line between statics and consts.

The annoying thing is that we have to choose one or the other — either a consistent address or const compatibility. At least, not without #![feature(const_refs_to_static)], which I didn't actually realize was a thing. Combine that with inline static blocks to avoid needing to name the type (obviously can't capture generics) and this seems absolutely reasonable.

@Diggsey
Copy link

Diggsey commented Aug 7, 2024

@CAD97 I don't see how your example relates to the others here - let a = ... is not a constant, it's just evaluated in a const context, so guaranteed_eq(a, a) doesn't involve any inlining of constants - you're just comparing a variable against itself.

@CAD97
Copy link

CAD97 commented Aug 7, 2024

you're just comparing a variable against itself

All the more reason that it should be. I originally wrote the example instead as

const C: (&i32, &i32) = { let x = &0; (x, x) };
const _: () = {
    let (a, b) = C;
    // with 1.82 nightly (2024-08-06 60d146580c10036ce89e)
    assert!(matches!(<*const _>::guaranteed_eq(a, b), None));
};

but then I changed it when I checked and guaranteed_eq(a, a) still produced None.

Also, &0 is eligible for constant promotion, though I don't know for sure whether it gets promoted. After checking, it does still return None when const promotion is prevented, though. (Or Some(true) at runtime.)

@RalfJung
Copy link
Member Author

With rust-lang/rust#126660, vtables get yet another fun kind of pointer equality behavior: casting from &dyn Trait+Send to &dyn Send (or otherwise doing a cast that removes the "principal" trait) will preserve the original vtable at runtime, but logically (and in Miri) this creates a new vtable for the original type without a "principal". So in Miri these will never compare equal but at runtime they will.

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

No branches or pull requests

7 participants