Arc::drop has a (potentially) dangling shared ref

[RalfJung]

Discovered by @Amanieu on IRLO. Quoting their report:

Arc::drop contains this code:

if self.inner().strong.fetch_sub(1, Release) != 1 {
    return;
}

Once the current thread (Thread A) has decremented the reference count, Thread B could come in and free the ArcInner.

The problem becomes apparent when you look at the implementation of fetch_sub:

pub fn fetch_sub(&self, val: $int_type, order: Ordering) -> $int_type {
    unsafe { atomic_sub(self.v.get(), val, order) }
    // HERE
}

Note the point marked HERE: at this point we have released our claim to the Arc (as in, decremented the count), which means that Thread B might have freed the ArcInner. However the &self still points to the strong reference count in the ArcInner -- so &self dangles.

Other instances of this:

• Soundness of std::sync::Once #65796

[RalfJung]

Potential fixes:

• Provide a version of fetch_sub that takes a raw pointer, and use that.
• Provide a version of UnsafeCell that opts-out of the dereferenceable attribute, maybe even make that the default behavior for UnsafeCell. Also see What about: volatile accesses and memory-mapped IO unsafe-code-guidelines#33 for another use-case for a non-dereferenceable shared ref.

[RalfJung]

Turns out Clang has a similar issue, it uses dereferenceable for C++ references and that's not correct because the pointee might get deallocated during the course of the function. Hence another possible fix might be to use dereferenceable_on_entry instead of dereferenceable for &UnsafeCell<T> once that attribute exists.

[jClaireCodesStuff]

It's a little spooky to see a situation where a region of code could do something undefined without an unsafe block. However, as the 'Nomocon notes, this is to be expected when working around unsafe code. A soundly designed library will encapsulate this potential unsafety, but it's not possible or even desirable to protect closely neighboring safe code from the potential of UB.

Anyway, in this twilight zone dangling pointers are not prohibited. Dereferencing dangling pointers is. Exposing somebody else's unsuspecting code to a dangling pointer is also very forbidden. But it's fine for dangling pointers to exist as long as they are dead.

Remember: "dead" means "will not be accessed by anything below this point." Other languages don't even have a concept of reference lifetimes.

Once the current thread (Thread A) has decremented the reference count, Thread B could come in and free the ArcInner.

That can happen. But if it does, Thread A is guaranteed to fetch a reference count greater than 1, which then causes Arc::drop to return early. self dangles but it isn't dereferenced while dangling, so no problem.

It would be undefined behavior for any method to be called after drop. But we also know that this won't happen, because "drop is the last method call" is one of the invariants.

Honestly, I think you're a little too attached to the "Stacked Borrows" model - this is a situation where it doesn't work and rather than trying to understand why the model should be changed, you're arguing that the source code of stdlib should be declared unsound. If Rust continues in the tradition of LLVM, the uniqueness of &mut really means something like "I solemnly swear that the addresses derived from this reference will not be derived by any other means until after the last use of this reference."

[hanna-kruppe]

The immediate problem is not about Rust, safe or unsafe, or any proposed formal semantics for it. rustc emits IR that has technically undefined behavior, because there is a pointer that is claimed to be dereferenceable for the duration of a function but points to memory that is (potentially) deallocated during the execution of the function. That this is not a Rust-specific problem can also be seen by the fact that Clang ('s C++ mode) is affected by it too, as linked earlier. This specific instance is not terribly likely to cause miscompilations, but others are, and in any case "UB that's unlikely to cause problems in practice" is not a good way to build a reliable language implementation.

Aside from that, there is the task of justifying the LLVM IR that rustc emits with Rust-level rules -- at minimum, in every case where emitted LLVM IR has UB, the input Rust code also needs to have UB to be able to claim rustc is correct. This issue points out a case where previous attempts at justifying the dereferenceable attribute that rustc emits are not sufficient. There are multiple possible remedies for that, none of which are about stacked borrows and most of which modify how rustc emits IR (emitting the attribute in fewer cases, or emitting a weaker attribute instead in some cases) to make the existing code well-defined without modification.

[vertexclique]

Option one:

• Provide a version of fetch_sub that takes a raw pointer, and use that.

for resolving this bug was tried in here: #58611

[nikomatsakis]

I'm nominating this issue -- and tagging it for @rust-lang/lang -- in response to some comments by @jamesmunns in today's Project Leadership Sync meeting. In particular, @jamesmunns pointed out that this issue around the deferenceable attribute has potentially large repercussions in the embedded space, and cited @japaric's RFC as well as a number of issues around the embedded space (see the minutes).

I've got to dig a bit deeper here but it seems like it'd be good to check-in on the current thinking here. I will try to catch up on the RFC and some of the proposed changes and see if I can post any notes.

Without having done so, I would say that, as far as I know, we still want to keep the dereferenceable attribute, so I expect some form of these changes will be required.

(I suppose omething like the [dereferencable on entry proposal(https://lists.llvm.org/pipermail/llvm-dev/2018-July/124555.html) might also be good, does anyone know if that's made progress? I'm going to assume not.)

[vertexclique]

@nikomatsakis I have done some work around this. But actually that extended visible API surface by one method. It resolves the problem at a cost of that.

[64]

I could be wrong, but it seems like LLVM now supports nofree and nosync function attributes, which would solve the issue. https://lists.llvm.org/pipermail/llvm-dev/2018-July/124555.html

[hanna-kruppe]

nofree and nosync exist now, but as far as I can tell the switch from

dereferenceable applies through the entire function

to

dereferenceable applies on function entry (use nofree and nosync information to recover analysis power)

has not yet happened.

[RalfJung]

Ah so the tentative plan in LLVM now is to weaken dereferencable semantics instead of adding another attribute?

That seems bad though. Quoting:

I'd like to propose adding a nofree function attribute to indicate that
a function does not, directly or indirectly, call a memory-deallocation
function (e.g., free, C++'s operator delete).

So, e.g., a function that takes a reference and also drops an unrelated Box could not express, with its attributes, that the reference will not get deallocated.

Maybe some from the Rust side should chime in an raise this as a concern?

[hanna-kruppe]

I forgot about this before but there's a (not yet committed) patch introducing a new attribute for "dereferencable forever" at https://reviews.llvm.org/D61652

[RalfJung]

See #65796 for another instance: there's a call to AtomicBool::store there signalling another thread that it can remove this memory; that deallocation might happen while AtomicBool::store still runs with its &self argument.

[RalfJung]

Unfortunately I have no idea what you mean by this rather vague proposal. Please describe your changes via concrete code / a diff that applies to the current code.

[SoniEx2]

Again, we don't know if it's possible to do it that way.

The basic idea is we'd allocate a struct on the stack, and place a pointer to it in the ArcInner. we'd then check the ArcInner to see if it was modified and attempt to clear it. if it was modified, we wait for a signal and... ah, we guess this would only shift the problem to AtomicPtr...

Hmm...

... yeah nvm, we guess the only real solution is to tell the abstract machine to just accept it as-is somehow.

[RalfJung]

#98498 is another instance of this -- or rather, after doing the easiest fix, it becomes an interesting instance of this -- except that this time, not the entire memory &self points to is inside UnsafeCell, so the proposed solutions do not suffice to allow that code. We'd have to also move the main_thread field into an UnsafeCell.

[Coder-256]

#98017 seems like a potentially large change to fix a relatively smaller issue. Would the following change not be sufficient?:

-        if self.inner().strong.fetch_sub(1, Release) != 1 {
-            return;
-        }
+        let strong_ptr = self.inner().strong.as_mut_ptr();
+        unsafe {
+            if core::intrinsics::atomic_xsub_rel(strong_ptr, 1) != 1 {
+                return;
+            }
+        };

In this case, the current thread would have no references to inner() by the time the strong count is decremented, and therefore there couldn't exist any dereferenceable references when the ArcInner is dropped, correct?

I know I have commented this before and I don't mean to distract from the conversation, just a bit confused why a change to rustc itself would be required here. I worry that limiting the use of dereferenceable could possibly prevent some optimizations, today or in the future, which may be undesirable if this issue can be solved without it.

[ghost]

Given that approximately the same issue has come up in rayon, crossbeam, and at least three separate instances in std, it seems like this is a pattern that Rust experts expected to work. IMO that is a sign a language change like the one @RalfJung has proposed is necessary.

If we went that route of not allowing references in this pattern, I think we should consider expanding the API of atomics. Creating functions explicitly designed to be safe for this "may signal that self can be deallocated" pattern would greatly help guide people in the right direction.

[saethlin]

I do not think that reasoning is very good. Numerous crates including rayon and the compiler have expected to be able to do out-of-bounds indexing with slice::get_unchecked.

We should not attempt to codify and bless existing practice, because that is largely based on whatever appears to work with the current implementation of the language, and may not lend itself to a coherent set of rules. It seems clear at this point that we cannot have a simple set of rules which permit both the applications and optimizations we would like Rust to have and also accept all existing code, or even all code written by "experts". There will be give on both the language and the use of the language.

I don't have a strong opinion on the right way to resolve this situation, but I will point out that losing dereferenceable from &UnsafeCell isn't particularly surprising; the type already exists to lift one form of pointer/reference optimization. But the fact that this change doesn't resolve #98498 makes me wonder how many codebases which contain the pattern that losing dereferenceable on &UnsafeCell is intended to permit will require soundness fixes anyway, because the root problem isn't that the rules aren't usable at all before or after this change, it's something else. Perhaps that authors aren't used to reasoning about dereferenceable, or Miri wasn't good enough at exposing this bug until recently, or that Miri isn't used/is hard to use on the kind of codebases that would run into this.

[RalfJung]

I don't have a strong opinion on the right way to resolve this situation, but I will point out that losing dereferenceable from &UnsafeCell isn't particularly surprising; the type already exists to lift one form of pointer/reference optimization. But the fact that this change doesn't resolve #98498 makes me wonder how many codebases which contain the pattern that losing dereferenceable on &UnsafeCell is intended to permit will require soundness fixes anyway,

My personal preference to resolve the situation is to also say that when a shared ref points to a !Freeze type, we treat the entire pointee as not-frozen (as opposed to attempting to precisely track which bytes are inside an UnsafeCell and which are not). Doing so makes the approach in #98504 sound, and greatly simplifies the specification and its implementation because now a given tag always has the same permission everywhere it is used. We lose some optimizations, but what we currently tell LLVM is still correct. So I think overall that is a nice corner of the design space. This is basically the discussion in rust-lang/unsafe-code-guidelines#236.

[AngelicosPhosphoros]

@RalfJung Can we solve this by changing Drop trait API?

Something like this:

trait Drop{
   fn drop(&mut self);
   
   fn drop_ptr(mut self: NonNull<Self>){
        unsafe{
            // Only case when direct call to `Drop::drop` is allowed.
            Drop::drop(self.as_mut());
        }
   }
}

All existing code would just work because it delegates to old methods that accept the reference.
For cases like discussed ITT, user can implement it like this:

impl Drop for MyTypeWithPtr{
   fn drop(&mut self){ unreachable!("We use only pointer based deallocation") }
   
   fn drop_ptr(mut self: NonNull<Self>){
        // Since we created references inside function, they are not dereferencable.
        // And we can check all our conditions using pointer based API
        // to avoid having living references to data freed in separate thread.
   }
}

This way we would solve issues caused by dropping code like this without giving up dereferencable on &UnsafeCell<X> arguments.

[RalfJung]

It's not the reference in drop that caused the trouble. It's the &self reference in this AtomucIsize method:

pub fn fetch_sub(&self, val: $int_type, order: Ordering) -> $int_type {
    unsafe { atomic_sub(self.v.get(), val, order) }
    // HERE
}

Anyway, with #98017 having landed, I think we can finally close this issue. :) We barely managed to do it in less than 4 years. :D