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

arc::get_mut/Arc::make_unique are racy #24880

Closed
talchas opened this Issue Apr 28, 2015 · 20 comments

Comments

Projects
None yet
7 participants
@talchas

talchas commented Apr 28, 2015

Both of these essentially check that inner().strong == 1 && inner().weak == 1 to check that &mut self is the only reference to the Arc's data. However in between the checks a Weak pointer could be promoted and the Weak pointer dropped, resulting in both checks succeeding. Adding an additional strong check afterwards won't help as the second strong pointer could then be demoted again.

I don't see an obvious way without a two-word atomic read or a generation counter or something of that sort. On 64-bit splitting an atomic64 into two 32-bit sections /might/ be ok, but on 32-bit only allowing 16 bits of refcount seems bad. (There might be something with using a high bit as a lock bit or such?)

@kballard

This comment has been minimized.

Show comment
Hide comment
@kballard

kballard Apr 28, 2015

Contributor

I think you're right.

I'm tempted to say this could be fixed by switching from a strong/weak pair to a num_ptrs/num_weak pair, where every pointer (whether strong or weak) is counted in num_ptrs and then weak pointers are also counted in num_weak. This does lower the number of total pointers (strong + weak) that we can have outstanding, but it's not as restrictive as actually dividing a usize into two halves.

Another alternative might be to use the high bit of the strong pointer as a "there are weak references" marker. I'm not sure how well that would actually work.

And of course we could always just use a spinlock instead.

Contributor

kballard commented Apr 28, 2015

I think you're right.

I'm tempted to say this could be fixed by switching from a strong/weak pair to a num_ptrs/num_weak pair, where every pointer (whether strong or weak) is counted in num_ptrs and then weak pointers are also counted in num_weak. This does lower the number of total pointers (strong + weak) that we can have outstanding, but it's not as restrictive as actually dividing a usize into two halves.

Another alternative might be to use the high bit of the strong pointer as a "there are weak references" marker. I'm not sure how well that would actually work.

And of course we could always just use a spinlock instead.

@sfackler

This comment has been minimized.

Show comment
Hide comment
@sfackler

sfackler Apr 28, 2015

Member

Using num_ptrs + num_weak shouldn't actually lower the total number of pointers since each Arc or Weak is larger than 1 byte so you'd exhaust the address space before overflowing num_ptrs.

Member

sfackler commented Apr 28, 2015

Using num_ptrs + num_weak shouldn't actually lower the total number of pointers since each Arc or Weak is larger than 1 byte so you'd exhaust the address space before overflowing num_ptrs.

@kballard

This comment has been minimized.

Show comment
Hide comment
@kballard

kballard Apr 28, 2015

Contributor

Upon reflection I suspect that num_ptrs + num_weak fails for the same reason that get_mut fails, because the destructor of Arc needs to know how many strong references there are, and the only way to get num_strong is with two loads.

Contributor

kballard commented Apr 28, 2015

Upon reflection I suspect that num_ptrs + num_weak fails for the same reason that get_mut fails, because the destructor of Arc needs to know how many strong references there are, and the only way to get num_strong is with two loads.

@kballard

This comment has been minimized.

Show comment
Hide comment
@kballard

kballard Apr 28, 2015

Contributor

Although it's possible that using num_ptrs + num_strong instead might possibly work.

Contributor

kballard commented Apr 28, 2015

Although it's possible that using num_ptrs + num_strong instead might possibly work.

@talchas

This comment has been minimized.

Show comment
Hide comment
@talchas

talchas Apr 28, 2015

If that works (which sounds plausible) it has the disadvantage of requiring two atomics on clone() (though they're probably the same cacheline, so it's not as horrible as it might be).

talchas commented Apr 28, 2015

If that works (which sounds plausible) it has the disadvantage of requiring two atomics on clone() (though they're probably the same cacheline, so it's not as horrible as it might be).

@kballard

This comment has been minimized.

Show comment
Hide comment
@kballard

kballard Apr 28, 2015

Contributor

I still haven't thought it entirely all the way through, but I think that num_ptrs + num_strong will work (as long as num_strong is always modified before num_ptrs). As you say, this will require two atomics on clone().

The other alternative that I think would work is using the low bit of the strong counter as a "has weak" flag that, when set, is never un-set. Once it's set, a spinlock is then used around all relevant accesses to the strong and weak counters. This is more complicated than num_ptrs + num_strong, but has the benefit of meaning that Arcs that don't use Weak won't have to pay any cost (and in fact they'll be slightly cheaper than today, because no atomic load of weak is necessary if the flag is 0).

Incidentally, it appears we do not have a spinlock construct in our stdlib. That's rather unfortunate, as ad-hoc simple spinlocks are not generally ideal. Preferably we'd have a construct that spins some number of times (it looks like pthread on OS X defines that number as 1000) on multi-processor machines before yielding the thread, and yields immediately on single-processor machines.

Contributor

kballard commented Apr 28, 2015

I still haven't thought it entirely all the way through, but I think that num_ptrs + num_strong will work (as long as num_strong is always modified before num_ptrs). As you say, this will require two atomics on clone().

The other alternative that I think would work is using the low bit of the strong counter as a "has weak" flag that, when set, is never un-set. Once it's set, a spinlock is then used around all relevant accesses to the strong and weak counters. This is more complicated than num_ptrs + num_strong, but has the benefit of meaning that Arcs that don't use Weak won't have to pay any cost (and in fact they'll be slightly cheaper than today, because no atomic load of weak is necessary if the flag is 0).

Incidentally, it appears we do not have a spinlock construct in our stdlib. That's rather unfortunate, as ad-hoc simple spinlocks are not generally ideal. Preferably we'd have a construct that spins some number of times (it looks like pthread on OS X defines that number as 1000) on multi-processor machines before yielding the thread, and yields immediately on single-processor machines.

@bluss

This comment has been minimized.

Show comment
Hide comment
@bluss

bluss Apr 28, 2015

Contributor

Split the Arc struct in two: Give Arc another marker type parameter that decides statically if the type should support weak pointers or not. Use default type parameters to make Arc<T> equivalent Arc<T, NoWeak>

Only the NoWeak Arc will permit get_mut and make_unique. Since the Arc source references boost a lot, I tried to find any indication of how this is solved in the boost sphere, and I can't find any solution when weak pointers are involved.

Default type parameters make this seamless for users that don't need weak pointers.

Note: boost shared_ptr has a member function bool unique() but it only considers stong references.

Contributor

bluss commented Apr 28, 2015

Split the Arc struct in two: Give Arc another marker type parameter that decides statically if the type should support weak pointers or not. Use default type parameters to make Arc<T> equivalent Arc<T, NoWeak>

Only the NoWeak Arc will permit get_mut and make_unique. Since the Arc source references boost a lot, I tried to find any indication of how this is solved in the boost sphere, and I can't find any solution when weak pointers are involved.

Default type parameters make this seamless for users that don't need weak pointers.

Note: boost shared_ptr has a member function bool unique() but it only considers stong references.

@kballard

This comment has been minimized.

Show comment
Hide comment
@kballard

kballard Apr 28, 2015

Contributor

@bluss That seems like a very heavy-handed approach. The creator of the Arc instance may not know ahead of time whether any code is going to want to create a Weak instance. And at such time as that decision is made, all code that touches the Arc would have to be updated even though that code doesn't really care whether there's a Weak reference.

As for Boost, I glanced at it yesterday and it didn't appear to me that it supported weak pointers.

Contributor

kballard commented Apr 28, 2015

@bluss That seems like a very heavy-handed approach. The creator of the Arc instance may not know ahead of time whether any code is going to want to create a Weak instance. And at such time as that decision is made, all code that touches the Arc would have to be updated even though that code doesn't really care whether there's a Weak reference.

As for Boost, I glanced at it yesterday and it didn't appear to me that it supported weak pointers.

@bluss

This comment has been minimized.

Show comment
Hide comment
@bluss

bluss Apr 28, 2015

Contributor

It is heavy-handed, but it is also flexible, and allows users to only pay for what they use. Didn't we already want to make Weak pointers optional? (What other reason are they unstable for?)

See boost Smart Pointers doc, it has weak_ptr

Contributor

bluss commented Apr 28, 2015

It is heavy-handed, but it is also flexible, and allows users to only pay for what they use. Didn't we already want to make Weak pointers optional? (What other reason are they unstable for?)

See boost Smart Pointers doc, it has weak_ptr

@kballard

This comment has been minimized.

Show comment
Hide comment
@kballard

kballard Apr 28, 2015

Contributor

@bluss I'm not really sure why they're unstable, the message just says "Weak pointers may not belong in this module".

And you're right, Boost does have weak_ptr, the link I followed before (from the comments of Arc) didn't show it. Looking through Boost's weak_ptr and shared_ptr it appears that shared_ptr::unique() ignores weak pointers entirely and returns true even if there are existing weak pointers (it appears that shared_ptr works the same way our Arc does, with a shared counter (i.e. our strong) and a weak counter (that includes an extra +1 count as long as shared is non-zero).

So the difference here is our Arc's unique-testing needs to care about weak pointers (in order to meet the memory safety guarantees of Rust) but Boost doesn't enforce that.

Contributor

kballard commented Apr 28, 2015

@bluss I'm not really sure why they're unstable, the message just says "Weak pointers may not belong in this module".

And you're right, Boost does have weak_ptr, the link I followed before (from the comments of Arc) didn't show it. Looking through Boost's weak_ptr and shared_ptr it appears that shared_ptr::unique() ignores weak pointers entirely and returns true even if there are existing weak pointers (it appears that shared_ptr works the same way our Arc does, with a shared counter (i.e. our strong) and a weak counter (that includes an extra +1 count as long as shared is non-zero).

So the difference here is our Arc's unique-testing needs to care about weak pointers (in order to meet the memory safety guarantees of Rust) but Boost doesn't enforce that.

@kballard

This comment has been minimized.

Show comment
Hide comment
@kballard

kballard Apr 28, 2015

Contributor

I think what we should do today is remove Arc::make_unique and alloc::arc::get_mut. They're both marked as #[unstable] so this is acceptable. Without those two functions, our existing reference-counting implementation works fine. Then we can explore ways to re-add that functionality in the future. It appears that there are zero clients of Arc::make_unique in rust-lang/rust, although checking for get_mut is not so trivial as that name is not unique.

Contributor

kballard commented Apr 28, 2015

I think what we should do today is remove Arc::make_unique and alloc::arc::get_mut. They're both marked as #[unstable] so this is acceptable. Without those two functions, our existing reference-counting implementation works fine. Then we can explore ways to re-add that functionality in the future. It appears that there are zero clients of Arc::make_unique in rust-lang/rust, although checking for get_mut is not so trivial as that name is not unique.

@kballard

This comment has been minimized.

Show comment
Hide comment
@kballard

kballard Apr 28, 2015

Contributor

@alexcrichton You added Arc::make_unique in the first place, and @aturon you updated it to check weak refs. Any thoughts?

Contributor

kballard commented Apr 28, 2015

@alexcrichton You added Arc::make_unique in the first place, and @aturon you updated it to check weak refs. Any thoughts?

@kvark

This comment has been minimized.

Show comment
Hide comment
@kvark

kvark Apr 28, 2015

Contributor

@kballard I added arc::get_mut() in order to use it for parallel ECS proof of concept. I don't know if any real projects use it at the moment, so it should be safe to kill, but I'm going to miss it anyways.

Contributor

kvark commented Apr 28, 2015

@kballard I added arc::get_mut() in order to use it for parallel ECS proof of concept. I don't know if any real projects use it at the moment, so it should be safe to kill, but I'm going to miss it anyways.

@kballard

This comment has been minimized.

Show comment
Hide comment
@kballard

kballard Apr 28, 2015

Contributor

@kvark I would really like to have Arc::get_mut(), I think it's potentially useful, but as long as there's no clients in rust-lang/rust that depend on it right now, I think we should just kill it for 1.0 and investigate ways to safely re-add it in the future.

Contributor

kballard commented Apr 28, 2015

@kvark I would really like to have Arc::get_mut(), I think it's potentially useful, but as long as there's no clients in rust-lang/rust that depend on it right now, I think we should just kill it for 1.0 and investigate ways to safely re-add it in the future.

@bluss

This comment has been minimized.

Show comment
Hide comment
@bluss

bluss Apr 28, 2015

Contributor

Since weak_count and strong_count are public, get_mut can be implemented as it is today, outside of the crate too. At least I think you can, you would be effectively converting &T to &mut T, but isn't that legal if you go through raw pointers? Of course you'll only use this unsafe-marked get_mut if you know no Weak pointers are used in your application.

Removing unsound unstable API sounds fine.

Contributor

bluss commented Apr 28, 2015

Since weak_count and strong_count are public, get_mut can be implemented as it is today, outside of the crate too. At least I think you can, you would be effectively converting &T to &mut T, but isn't that legal if you go through raw pointers? Of course you'll only use this unsafe-marked get_mut if you know no Weak pointers are used in your application.

Removing unsound unstable API sounds fine.

@kballard

This comment has been minimized.

Show comment
Hide comment
@kballard

kballard Apr 28, 2015

Contributor

@bluss True, you could reimplement the current logic of get_mut, but since that logic is broken I don't think it's something we should be telling people to do.

At least I think you can, you would be effectively converting &T to &mut T, but isn't that legal if you go through raw pointers?.

Well no, that doesn't make it legal. If you construct a &mut T, you need to guarantee it's not aliased by anything else. This means you need to guarantee that there are no &T references to the same value (and that you can't construct one). That said, I'm not 100% positive about the actual hard requirements here; I think it's just the aliasing requirement, which means if you can guarantee that there are no (accessible) &T references extant, then your constructed &mut T is valid.

Based on that, I believe that it would be legal to construct this third-party fn arc_get_mut<T>(ptr: &mut Arc<T>) -> Option<&mut T> even though the implementation would have to transmute a &T into a &mut T. The implementation of the function can ensure that it doesn't construct any other &T reference after creating the &mut T (or more generally, that it doesn't touch the ptr again), and the API of the function means that the resulting &mut T borrows the Arc.


All that said, given that the current scheme of separate atomic strong and weak counts does not allow you to do this unique-test safely, none of this really matters. get_mut() can't be implemented safely without changing the implementation details of Arc.

Contributor

kballard commented Apr 28, 2015

@bluss True, you could reimplement the current logic of get_mut, but since that logic is broken I don't think it's something we should be telling people to do.

At least I think you can, you would be effectively converting &T to &mut T, but isn't that legal if you go through raw pointers?.

Well no, that doesn't make it legal. If you construct a &mut T, you need to guarantee it's not aliased by anything else. This means you need to guarantee that there are no &T references to the same value (and that you can't construct one). That said, I'm not 100% positive about the actual hard requirements here; I think it's just the aliasing requirement, which means if you can guarantee that there are no (accessible) &T references extant, then your constructed &mut T is valid.

Based on that, I believe that it would be legal to construct this third-party fn arc_get_mut<T>(ptr: &mut Arc<T>) -> Option<&mut T> even though the implementation would have to transmute a &T into a &mut T. The implementation of the function can ensure that it doesn't construct any other &T reference after creating the &mut T (or more generally, that it doesn't touch the ptr again), and the API of the function means that the resulting &mut T borrows the Arc.


All that said, given that the current scheme of separate atomic strong and weak counts does not allow you to do this unique-test safely, none of this really matters. get_mut() can't be implemented safely without changing the implementation details of Arc.

@huonw

This comment has been minimized.

Show comment
Hide comment
@huonw
Member

huonw commented Apr 28, 2015

cc #24564

@bluss

This comment has been minimized.

Show comment
Hide comment
@bluss

bluss Apr 29, 2015

Contributor

since that logic is broken I don't think it's something we should be telling people to do.

It's a systems language, we don't tell them what to do. We tell them what's possible and where the boundaries lie. We give them unsafe blocks for when they feel they can take over the reins themselves.

Well no, that doesn't make it legal. If you construct a &mut T, you need to guarantee it's not aliased by anything else.

Obviously. I didn't say it was a sufficient criterium. Anyway, let's not do this kind of thing where we out-nitpick each other.. All I suggested was if wouldn't it be possible to implement outside of crate.

Contributor

bluss commented Apr 29, 2015

since that logic is broken I don't think it's something we should be telling people to do.

It's a systems language, we don't tell them what to do. We tell them what's possible and where the boundaries lie. We give them unsafe blocks for when they feel they can take over the reins themselves.

Well no, that doesn't make it legal. If you construct a &mut T, you need to guarantee it's not aliased by anything else.

Obviously. I didn't say it was a sufficient criterium. Anyway, let's not do this kind of thing where we out-nitpick each other.. All I suggested was if wouldn't it be possible to implement outside of crate.

@bluss

This comment has been minimized.

Show comment
Hide comment
@bluss

bluss May 10, 2015

Contributor

The racy functions still exist. We should document that or remove them.

Contributor

bluss commented May 10, 2015

The racy functions still exist. We should document that or remove them.

bluss pushed a commit to bluss/rust that referenced this issue May 30, 2015

Ulrik Sverdrup
Mark Arc function get_mut and method make_unique unsafe
This is a temporary mitigation for issue #24880 which points out that
these functions are racy in a particular situation where weak pointers
exist.

To mitigate this, mark the functions unsafe until this can be fixed or
another decision is made.

bluss pushed a commit to bluss/rust that referenced this issue May 30, 2015

Ulrik Sverdrup
Mark Arc function get_mut and method make_unique unsafe
This is a temporary mitigation for issue #24880 which points out that
these functions are racy in a particular situation where weak pointers
exist.

To mitigate this, mark the functions unsafe until this can be fixed or
another decision is made.

This is a breaking change to unstable API, because the new version
requires an `unsafe` block. Review carefully if weak pointers may race
for any uses of this API and consider abandoning it.

[breaking-change]

bors added a commit that referenced this issue May 31, 2015

Auto merge of #25908 - bluss:arc-mark-unsafe, r=sfackler
Mark Arc function get_mut and method make_unique unsafe

This is a temporary mitigation for issue #24880 which points out that
these functions are racy in a particular situation where weak pointers
exist.

To mitigate this, mark the functions unsafe until this can be fixed or
another decision is made.
@aturon

This comment has been minimized.

Show comment
Hide comment
@aturon

aturon Jun 26, 2015

Member

For reference, these functions, together with weak pointers, are used heavily in Servo. I've made a PR to fix this problem more directly: #26610

Member

aturon commented Jun 26, 2015

For reference, these functions, together with weak pointers, are used heavily in Servo. I've made a PR to fix this problem more directly: #26610

bors added a commit that referenced this issue Jul 3, 2015

Auto merge of #26610 - aturon:fix_make_unique, r=alexcrichton
This commit resolves the race condition in the `get_mut` and
`make_unique` functions, which arose through interaction with weak
pointers. The basic strategy is to "lock" the weak pointer count when
trying to establish uniqueness, by reusing the field as a simple
spinlock. The overhead for normal use of `Arc` is expected to be minimal
-- it will be *none* when only strong pointers are used, and only
requires a move from atomic increment to CAS for usage of weak pointers.

The commit also removes the `unsafe` and deprecated status of these functions.

Closes #24880

r? @alexcrichton 

cc @metajack @SimonSapin @Ms2ger

@bors bors closed this in #26610 Jul 3, 2015

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment