Arc::ptr_eq does not always return "true if the two Arcs point to the same allocation" as documented

[rib]

Edited: to account for an initial misunderstanding about how dyn Trait wide pointers are compared

TL;DR
The implementation of Arc::ptr_eq is implemented based on comparing pointers to the inner value (not something that the documentation suggests/requires), which may involve comparing wide pointer meta data that is not relevant to it's stated function - and could lead to false negatives

How Arc::ptr_eq is documented, and current expectations:

For reference here this is the (I think concise) documentation for Arc::ptr_eq:

Returns true if the two Arcs point to the same allocation (in a vein similar to ptr::eq).

My expectation from this is rather simple: the implementation will get the pointer for the Box/"allocation" that is allocated as the backing storage for two arcs (holding the reference count and inner value) and it will compare those pointers with ptr::eq.

Notably: the wrapped type should have no bearing on the implementation / semantics here, since it's the pointer of the "allocation" that is supposed (documented) to be compared.

This way you can create any number of references for a single Arc that wraps some inner value and cheaply determine whether two Arcs point back to the same state allocation.

I've been relying on those semantics for Arc::ptr_eq across a number of projects for exactly that purpose.

For a few projects I should also note that I have generalized how I wrap state in an Arc as an aid for also exposing that state across FFI boundaries. I note this just to highlight the separation of concerns that I have relied on - namely that I assume I can use Arc::ptr_eq to check whether two Arcs point to the same state without having to worry about what kind of type is wrapped by the Arc.

Actual implementation of Arc::ptr_eq:

Instead of comparing the pointers of the backing "allocation", the current implementation of Arc::ptr_eq instead figures out the offset pointer to the inner value and does a comparison of those value pointers with semantics that could vary depending on what is wrapped by the Arc.

I.e. it does Arc::as_ptr(&a) == Arc::as_ptr(&b)

edited, to address an initial misunderstanding:
In particular if an Arc contains a dyn Trait then the pointers would be wide/fat pointers and the comparison will compare the vtable pointer for those trait objects which could be equal even though the two Arcs are otherwise unrelated, not referencing the same "allocation". (I.e. it could return true for two Arcs that don't point to the same allocation)

In particular if an Arc contains a dyn Trait then the pointers would be wide/fat pointers and the comparison will
check that target_a == target_b && vtable_a == vtable_b which makes it possible for the comparison to return false for two Arcs that have the same allocations but differing vtables.

Example

Based on #80505 (comment)

use std::{sync::Arc, mem};

struct A(u8);
#[repr(transparent)]
struct B(A);

trait T {
    fn f(&self);
}
impl T for A {
    fn f(&self) { println!("A") }
}
impl T for B {
    fn f(&self) { println!("B") }
}


fn main() {
    let b = Arc::new(B(A(92)));
    let a = unsafe {
        mem::transmute::<Arc<B>, Arc<A>>(b.clone())
    };
    
    let a: Arc<dyn T> = a;
    let b: Arc<dyn T> = b;
    println!("{}", Arc::ptr_eq(&a, &b));
}

Discussion

I'm not sure what safety rules have been established for transmuting Arcs in such a way as to hit this but the more general consideration here is that Rust supports the notion of wide pointers with meta data whereby that meta data may affect pointer comparisons in various ways depending on the types involved.

The Arc::ptr_eq API is specifically documented to compare whether the "allocation" of two Arcs are the same and so I don't believe that the semantics for comparing any form of wide pointer to the inner value should be relevant here.

Additionally comparing meta data associated with the inner value poses a rather open-ended risk that this function may deviate from its documented function - something that might change further if new types of wide pointers + meta data are added to Rust in the future.

Especially in the context of state that's being shared over unsafe FFI boundaries I think the potential for deviation from the documentation could be rather dangerous.

Even unrelated to FFI this breaks the basic notion that you can rely on this API compare whether two Arcs reference the same state which may easily break logical invariants that code relies on, for example to implement the Eq trait of a higher level type.

As it happens I discovered this in a project for Json Web Tokens after I introduced Clippy to the project's CI. There was some validation state that was wrapped in an Arc (closures that the application could add for validating a token) and discovering that the logic for comparing this validation state is broken by this was particularly concerning for me.

Duplicate issue

This issue has been discussed before as #80505 but I think it was, perhaps, a mistake that the discussion focused on the question of consistency between ptr::eq and Arc::ptr_eq in terms of how wide pointers should be compared.

The documentation for Arc::ptr_eq gives no suggestion that it is comparing pointers to the wrapped type and so (imho) there is no cause for concern regarding the consistent handling of wide pointer comparisons.

Even considering the mention of ptr::eq in the documentation where it says:

(in a vein similar to ptr::eq)

there is no implication that the inner type of the Arc affects what pointers are being compared.

ptr::eq should conceptually be used to compare the pointers to the Arcs inner allocation, which should just be the raw (non-wide) pointer for the Box that encompasses the Arcs reference count. In this way the comparison is done "in a vein similar to ptr::eq" (it may literally use ptr::eq internally).

Previous agreement that this is a bug

The discussion for #80505 seemed to go around in circles but it seems important to highlight that the libraries team did discuss the issue and actually agreed that it was a bug #80505 (comment)

With that agreement it's hard to understand why #80505 was closed. (It looks like it was essentially closed since it was a pull request not an issue, and there had been some questions raised about the patch that maybe weren't addressed.)

Meta

rustc --version --verbose:

rustc 1.64.0 (a55dd71d5 2022-09-19)
binary: rustc
commit-hash: a55dd71d5fb0ec5a6a3a9e8c27b2127ba491ce52
commit-date: 2022-09-19
host: x86_64-pc-windows-msvc
release: 1.64.0
LLVM version: 14.0.6

[SNCPlay42]

In particular if an Arc contains a dyn Trait then the pointers would be wide/fat pointers and the comparison will compare the vtable pointer for those trait objects which could be equal even though the two Arcs are otherwise unrelated, not referencing the same "allocation". (I.e. it could return true for two Arcs that don't point to the same allocation)

Can you provide a code sample where this happens?

I certainly accept that two Arcs that reference the same allocation but have a different vtable would compare unequal as discussed in #80505, but you are suggesting that Arc comparison is based on the vtable exclusively, which does not sound correct to me.

e.g. when comparing two fat pointers (target_a, vtable_a) and (target_b, vtable_b), I believe the current logic is target_a == target_b && vtable_a == vtable_b and #80505 would have changed it to target_a == target_b, but you claim it is vtable_a == table_b.

[rib]

In particular if an Arc contains a dyn Trait then the pointers would be wide/fat pointers and the comparison will compare the vtable pointer for those trait objects which could be equal even though the two Arcs are otherwise unrelated, not referencing the same "allocation". (I.e. it could return true for two Arcs that don't point to the same allocation)

Can you provide a code sample where this happens?

I certainly accept that two Arcs that reference the same allocation but have a different vtable would compare unequal as discussed in #80505, but you are suggesting that Arc comparison is based on the vtable exclusively, which does not sound correct to me.

e.g. when comparing two fat pointers (target_a, vtable_a) and (target_b, vtable_b), I believe the current logic is target_a == target_b && vtable_a == vtable_b and #80505 would have changed it to target_a == target_b, but you claim it is vtable_a == table_b.

Ah, right, I had got the wrong impression that it was going to do vtable_a == vtable_b only. I tried testing this and as you say it's not so simple as just comparing the vtable.

In my case I never witnessed a specific error condition but I did get a big surprise when running Clippy and got warned that Arc::ptr_eq was doing a vtable comparison which firstly led me to this issue:

rust-lang/rust-clippy#6524

and then #80505 - which I was very surprised to see had been closed.

The Clippy warning is phrased as: "error: comparing trait object pointers compares a non-unique vtable address"

and so I probably took my over-simplified understanding of how dyn Trait wide pointers would be compared from that.

I can strike out / edit this part of my issue description to address my misunderstanding here but I think the core of the issue still stands.

Thanks for the clarification.

[RalfJung]

I think this has been fixed by #103567? The docs now clarify the semantics of dyn Trait comparisons.

[rib]

From the Arc::ptr_eq docs I don't believe that the ptr::eq semantics regarding dyn Trait comparisons (or any wide pointers) are related to this issue because Arc::ptr_eq is not supposed to be comparing pointers to the wrapped values of each Arc.

So I think the clarification for how ptr::eq handles dyn Trait pointer comparisons is orthogonal to this issue.

It's only the current implementation of Arc::ptr_eq that will potentially lead to using ptr::eq to compare dyn Trait wide pointers (or other wide pointers for dynamically sized types).

The documentation for Arc::ptr_eq essentially says that it will compare the (implied thin) pointers to the backing "allocation" of two Arcs which is not something that's affected by the type being wrapped by the Arc. This should simplify things because that means the semantics of wide pointer comparisons doesn't come in to it.

The docs don't say anything about comparing pointers to the wrapped values of an Arc. If someone needs to do that then they could call Arc::as_ptr for each Arc and compare those manually in case they e.g. want the meta data associated with each value to also affect the comparison.

I believe the currently documented semantics are precisely what users of the API are expecting, for being able to determine if separate references point back to common state. (At least for the multiple projects I have using this API I had never imagined the implementation might also compare meta data for the wrapped value and never considered what unexpected implications that could have).

This issue is suggesting that the implementation should probably be changed to effectively compare the "allocation" pointers - which is not the same thing as comparing (potentially wide) pointers to the wrapped values.

I think one possible solution could be to compare the pointers to the values after stripping away any meta data. Another solution could be to compare the heap pointers to the inner Box instead of the offset value pointers (which would be a more literal interpretation of the documentation).

[RalfJung]

So I think the clarification for how ptr::eq handles dyn Trait pointer comparisons is orthogonal to this issue.

That PR also changes the Arc::ptr_eq docs to explicitly mention "caveats when comparing dyn Trait pointers", making it clear that those are (currently) relevant when calling Arc::ptr_eq.

The documentation for Arc::ptr_eq essentially says that it will compare the (implied thin) pointers to the backing "allocation" of two Arcs which is not something that's affected by the type being wrapped by the Arc. This should simplify things because that means the semantics of wide pointer comparisons doesn't come in to it.

That is your interpretation of the docs, but the docs also say that it works like ptr::eq, so it is very reasonable to assume that Arc::ptr_eq(x, y) is the exact same as ptr::eq(Arc::as_ptr(x), Arc::as_ptr(y)). In fact given the use of eq that would be reasonable to assume even if the docs did not explicitly mention ptr::eq.

I believe the currently documented semantics are precisely what users of the API are expecting

This comment has already gotten a reply almost 2 years ago:

• Documentation is not an immutable source of absolute truth. This one was changed in Rc: value -> allocation #65505 from "same value", which in turn was added in Add pub fn ptr_eq(this: &Self, other: &Self) -> bool to Rc and Arc #35992 without considering DSTs at all.
  (Source: I wrote that, mentioning a project that uses Rc<Node> where Node: Sized.)
  So I don’t think this precise choice of phrasing should be an argument for changing the behavior.

You are just repeating what has already been said many times. This is not helping.

Don't try to interpret the scripture that is comments and argue that your interpretation is better than someone else's. It's not going to end well for anyone. Instead make an independent argument for why the behavior should be the way you want it, why that is better than the current behavior, also taking into account

• the confusion caused by inconsistency between APIs (Arc::ptr_eq not working like ptr::eq)
• the alternative of having a separate method that performs the comparison you want

I'll nominate this for discussion by @rust-lang/libs-api and will see myself out since I don't actually have any skin in this game, all I care about is having clearly documented.

Last time, it looks like the team was torn -- @m-ou-se said the team preferred the 'thin ptr only' semantics but @SimonSapin had concerns.

[rib]

Right, my interpretation has always been that it does a thin pointer comparison for the backing storage allocation and so I was surprised to see a Clippy warning showing that that's not what the current implementation does and then worried about the implications of other interpretations on the correctness of my code.

I (personally) saw no inconsistency / conflict with the docs saying that the function works "(in a vein similar to ptr::eq)" because I believe that a valid comparison of the allocation pointers could be literally done using ptr::eq.

I see nothing to imply that pointers to the wrapped values will be compared which is what introduces all this ambiguity about how wide pointers / meta data should be handled.

Sorry that you see that I'm repeating things that were discussed before. The previous pull request that raised this was closed and so there was nothing to track the the issue. Also regarding scripture / re-interpretation of comments this is feeling somewhat more heated than I expected. I'm not trying to just disregard other opinions / comments. I tried to lay out a considered break down above of how I see this issue. I didn't simply assert that I disagree with someone's interpretation and that my interpretation is right, but sorry that it came across like that for you.

My impression from #80505 was that it was previously agreed that Arc::ptr_eq should only compare the thin pointers (re: #80505 (comment)) but the pull request got closed because the patch to fix the issue wasn't updated to match feedback given re: #80505 (comment))

[rib]

That PR also changes the Arc::ptr_eq docs to explicitly mention "caveats when comparing dyn Trait pointers", making it clear that those are (currently) relevant when calling Arc::ptr_eq.

This is interesting for sure.

(Personally) I find that the updated documentation from #103567 is more confusing for me. To me the initial statement of what Arc::ptr_eq does implies that no clarification about how ptr::eq handles wide pointers etc is necessary - so then it's extra confusing that there is now an added warning. It raises doubt over what "allocation" refers to.

I think it would be good for the docs to be much more explicit either way about the semantics here.

I feel like the docs should either:

1. state the the implementation is equivalent to doing Arc::as_ptr(&a) == Arc::as_ptr(&b) so that you know in no uncertain terms that the API compares the pointers to the wrapped values - including any meta data associated with those value pointers.
2. or else it should clarify that the "allocation" pointer has a private type and the semantics of the comparison is unaffected by the type that's being wrapped by the Arc.

If going with the former it would be interesting to understand when/why someone would want to compare Arcs and take into account meta data for the wrapped value. Any use case I have had for Arc::ptr_eq has always simply been to determine whether different references point back to the same original state and would have assumed that's the typical use case.

[Amanieu]

We discussed this in the libs-api meeting and think this might be better solved at the language level by making dyn trait pointer comparisons ignore the vtable pointer entirely. It seems to be very fragile in general (#103567) since the compiler is free to instantiate multiple copies of the same vtable (#46139).

It seems like the current behavior comes from rust-lang/rfcs#1135 (comment) which was a decision made when pointer equality for fat pointers was initially added to the language.

[rib]

Thanks for discussing the topic in the libs team.

I think there's a risk we're conflating two distinct issues/questions here and it could be good to find a way of tracking them both:

1. What does "allocation" conceptually refer to in the docs for Arc::ptr_eq? Is it the address of the Box allocation that holds the counters or is it the offset address of the value that's wrapped by the Arc? Conceptually the former definition may imply simpler semantics for Arc::ptr_eq because you wouldn't need to consider how wide pointers with meta data for value pointers get compared. This doesn't seem to be just about how dyn Trait wide pointers are compared because Rust can theoretically always introduce new wide pointer types with meta data (with as-yet unknown comparison semantics) for types that an Arc can wrap.
2. Should dyn Trait wide pointer comparisons just compare the address or the address and vtable? If it's hard to trust/know whether the compiler could duplicate equivalent vtables maybe it was the wrong design choice to have dyn Trait pointer comparisons check the vtable pointer. Whether this affects the implementation of Arc::ptr_eq depends on the answer to the first question though I think.

When opening this issue I think I was hoping we'd be able to focus on the first question - deciding what address Arc::ptr_eq is conceptually comparing. Deciding this would then determine whether the second question is orthogonal to this or not.

@Amanieu would it perhaps be possible to, more specifically, raise the first question with the libs team?

It seems hard to see how the Arc::ptr_eq semantics / docs can be really clarified without pinning that first decision down one way or the other.

Previously from #80505 (comment) it looked like the libs team agreed that it should refer to the allocation that holds the counters. If that still holds then that may imply that the semantics for dyn Trait pointer comparisons would be orthogonal to this issue?

Answering the first question should enable developers to know whether they need to manually strip the meta data from wide pointers if they know they want to disregard meta data associated with the value wrapped by the Arc (which is effectively what Clippy warns about currently re: rust-lang/rust-clippy#6524).

I.e. even if the semantics for dyn Trait pointer comparisons were changed/simplified to disregard the vtable then depending on the answer to the first question it may still make sense for developers to avoid Arc::ptr_eq and instead use Arc::as_ptr so they can unconditionally strip wide pointer meta data if they know they want to effectively compare the address associated with the ref counters and aren't trying to compare the pointers to the values.

[pnkfelix]

@Amanieu wrote:

We discussed this in the libs-api meeting and think this might be better solved at the language level by making dyn trait pointer comparisons ignore the vtable pointer entirely. It seems to be very fragile in general (#103567) since the compiler is free to instantiate multiple copies of the same vtable (#46139).

It seems like the current behavior comes from rust-lang/rfcs#1135 (comment) which was a decision made when pointer equality for fat pointers was initially added to the language.

This was discussed in T-lang triage meeting yesterday.

I do not agree that this is better solved by making dyn trait comparisons via == always ignore the vtable pointer entirely.

The team does agree that you cannot rely on two dyn trait pointer comparisons to reliably tell you that the two objects denote the same thing, due to implementation artifacts such as having multiple copies of the vtable embedded in the object binary.

However, it would be a mistake to address this by making == always ignore the vtable pointer and rely solely on the data pointer.

My own intuition about how == should generally behave¹ is that you have a == b only if a and b are observationally equivalent. In other words, given any two a and b, if you have a == b, then you would not expect to be construct a program context that would observe distinct behavior from a vs b.

I believe the Rust languages tries to follow the above intuition today². Thus, one's business logic can use == as the basis for caching the result returned by a call to a method on a *const dyn Trait; i.e. I can cache the result of calling a.m(), and later, if I'm given b such that a == b, then I can return the cached result instead of invoking b.m().

The change to == that is proposed here could easily break the above intuition: One can construct instances of dyn Trait with matching data addresses but also distinct vtables that collect differing methods. The two cases we discussed in the language team meeting:

• unsafe code constructing two *const dyn Trait.³
• aliased data pointers with distinct types (which can occur with zero sized types)

As a concrete example of the latter, I submit the following example code (playground):

trait Trait { fn msg(&self) -> String; }

fn pair(a: *const dyn Trait, b: *const dyn Trait) {
    let a_msg; let b_msg;
    unsafe {
        a_msg = a.as_ref().unwrap().msg();
        b_msg = b.as_ref().unwrap().msg();
    }
    
    let a_data_addr = a as *const ();
    let b_data_addr = b as *const ();
    
    // The Question: for non-null a, b,
    // if `a_data_addr == b_data_addr`,
    // can you ever have `a_msg != b_msg` ... ?
    
    if a_msg != b_msg && a_data_addr == b_data_addr {
        println!("Found one!");
        dbg!(a_data_addr);
        dbg!(b_data_addr);
        dbg!(a);
        dbg!(b);
        dbg!(a_msg);
        dbg!(b_msg);
    }
}

// ... and the answer is, yes you can:

fn main() {
    let zm = (Zst, Msg("good gravy"));
    let zm: (&dyn Trait, &dyn Trait) = (&zm.0, &zm.1);
    pair(zm.0, zm.1);
}

Thus, I do not think just comparing the data addresses of a *const dyn Trait should be considered an appropriate implementation of the == operator. If one finds two things are ==, in principle one should be able to conclude that they will behave the same. (If one finds they are not equal according to ==, one might still find that they otherwise behave the same; this is our sad lot as software engineers.)

Footnotes

1. "behave" in terms of user expectations w.r.t. their business logic for well-behaved values, not in terms of safety guarantees nor compiler optimizations nor operation in the face of adversarial code. ↩

2. modulo users providing implementations of PartialEq+Eq that break the aforementioned intuition, which is why I am specifically not including safety guarantees nor compiler optimizations as within scope of the implications presented here. ↩

3. I admit I do not find unsafe code to be an entirely satsifactory counter-example. Unsafe code can do lots of things that would be counter to typical business logic. Also, perhaps the lang design team, or an operational semantics team, may decide in the future that unsafe code is in fact not allowed to construct such *const dyn Trait objects with differing vtables for the same concrete data address with a single fixed type. ↩

[pnkfelix]

@rustbot label: -I-lang-nominated

[m-ou-se]

In the example on top of this thread, if you change both T::f impls to be identical (e.g. make both print "A"), the program will print false in debug mode, but true in release mode. The vtables get merged, as their contents are identical (because the f implementations get merged).

[m-ou-se]

FCP for fixing the issue for Arc::ptr_eq by ignoring the pointer metadata (so, only comparing the pointer address), such that the example above returns true rather than false, regardless of whether ptr::eq gets 'fixed' too:

@rfcbot merge

See the first comment in this thread for details and rationale.

[rfcbot]

Team member @m-ou-se has proposed to merge this. The next step is review by the rest of the tagged team members:

• @Amanieu
• @BurntSushi
• @dtolnay
• @joshtriplett
• @m-ou-se
• @yaahc

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

This will be merged soon.

[Amanieu]

I opened #106447 to discuss a language change to pointer equality.

In the meantime the discussion on this issue seems to be done, we just need a PR to change the behavior of ptr_eq to ignore the vtable.

[albertlarsan68]

@rustbot claim

[albertlarsan68]

Does the FCP also covers the Rc and {rc,sync}::Weak case ?

[Amanieu]

Does the FCP also covers the Rc and {rc,sync}::Weak case ?

Yes.