Rc is unsafe [mostly on 32-bit targets] due to overflow

[nikomatsakis]

So I was thinking about performance costs, particularly for Arc, and I was wondering if this is a good idea:

https://gist.github.com/anonymous/539b3468086b95c03cde

The idea is not to use a single sentinel value for “wrapped around” but rather an entire range. The motivation is that then we don’t need to use a compare-and-swap but rather we can use an atomic increment and just check whether the previous value was in that range of values that are deemed as “too high”. In this particular code, I used an isize and said that the ref count should never go negative (actually, we should never inc the ref when the previous value was already negative). Seems like 2^31 (or 2^63) is high enough, but you could use a usize and just set a threshold wherever you like. Anyway, the idea is that even if we have a ton of CPUs executing in a very unfortunate scheduling, at least one of them is going to observe the increment start from an invalid state.

I haven’t thought super hard about this so possibly there is a very obvious flaw. Certainly the performance is very good when I measure it locally (no difference from a straight addition, basically).

I chose to have the code just abort the process. I generally am against aborting (vs panicing) but:

• this seems like a distributed invariant across many threads, so panicing one thread isn’t clearly enough
• aborting is cheaper because no need for landing pads (right?)

It is probably possible to adapt the setup to leak the value instead, e.g. by setting some boolean flag to true (“count may have wrapped”).

[nikomatsakis]

To clarify something: the reason to use a range, rather than just checking if you added one to USIZE_MAX, is to eliminate the “window of unsafety”. That is, you will abort well before the counter would ever actually overflow. I think you would need 2^31 processors to do otherwise…? In any case, it’s seems vanishingly unlikely (though of course I’d love for someone to point out the flaw in my thinking if there is one).

[Gankro]

Ah, another case of leak amplification I just recalled: My hypothetical Mox type would leak its allocation if it ever was dropped, but it’s intended to be used with a pool allocator which can easily be cleared to “reclaim” all the memory. Generally local allocators are ripe for introducing massive leak amplification sites with bounded memory consumption.

[nikomatsakis]

Here are some benchmarking results for a simple case of spawning a bunch of threads, each of which do increments. (There is more of a slowdown that I saw at first, but still relatively small, certainly compared to CAS.)

https://gist.github.com/nikomatsakis/8ad11f16fd2d24b51b25

“cas” is using compare-and-swap, “inc” is just a plain increment, and “check” is the “danger zone” variant I described.

UPDATE: @alexcrichton saw much better results (check and inc virtually identical) on his machine, so I imagine this will vary by machine somewhat.

[huon]

UPDATE: @alexcrichton saw much better results (check and inc virtually identical) on his machine, so I imagine this will vary by machine somewhat.

I wonder how the various options behave on ARM, since I believe that is quite different to x86 for atomics/memory model.

[rkjnsn]

It is probably possible to adapt the setup to leak the value instead, e.g. by setting some boolean flag to true (“count may have wrapped”).

Given that the situation occurs due to leaking references, leaking the value seems much more intuitive than an abort to me. One way to do this without introducing an extra flag might be to have both inc and dec set the count to the middle of the negative range (-1073741824 for 32-bit) if the previous value was negative. This gives headroom of 2^30, which is plenty.

I think you would need 2^31 processors to do otherwise…?

The real limitation is address space: even if one had 2^31 (or 2^30) processors, there wouldn’t be enough address space for them to all have a distinct Arc on which to operate.

On other note, would this problem also apply to RefCell? It seems that one could get a shared borrow, take and forget enough additional ones to overflow the count, and then take a mutable borrow, yielding both a shared and a mutable borrow to the same memory. What about RWLock?

[llogiq]

Now I just have to put rust on my children’s RasPI.

[stebalien]

I think you would need 2^31 processors to do otherwise…?

Threads not processors so I believe the max headroom needed is the maximum number of threads (2^32/MIN_THREAD_STACK?).

It is probably possible to adapt the setup to leak the value instead, e.g. by setting some boolean flag to true (“count may have wrapped”).

You don’t need to do this, just use the overflow values as a flag. That is, check first then increment. Only MAX_THREADS could possibly increment after checking so all other checks will notice the overflow. (That is, unless this introduces some weird instruction-level memory dependency that slows things down…)

[nikomatsakis]

Given that the situation occurs due to leaking references, leaking the value seems much more intuitive than an abort to me. One way to do this without introducing an extra flag might be to have both inc and dec set the count to the middle of the negative range (-1073741824 for 32-bit) if the previous value was negative. This gives headroom of 2^30, which is plenty.

I see your logic, but I also think we have a lot of precedent for various “irrecoverable” situations yielding abort: panic in unwind, OOM, stack overflow (sort of a version of OOM), etc. Reference count overflow feels – to me – like it could belong in that category, though I agree it’s claim is weaker, since there is some plausible “recovery” strategy (if leaking can be called recovery). Certainly if I were writing a C program, I’d want it to abort, because it indicates something has gone horribly awry. In truth, either outcome is probably tolerable. It’d be good to measure the perf impact, since this is an exceptional and arguably buggy scenario, so it’d be a shame to penalize normal users of Arc.

On other note, would this problem also apply to RefCell? It seems that one could get a shared borrow, take and forget enough additional ones to overflow the count, and then take a mutable borrow, yielding both a shared and a mutable borrow to the same memory. What about RWLock?

Yes, it applies to RefCell (and there is an issue on this). I think it applies to most reference counting scenarios (at least those where safety is at issue). It does not (currently) apply to RWLock, since that defers I believe to the pthread impl (at least on linux), which appears to have considered this possibility (at least, there is an error for “too many readers”).

[bluss]

What vec::Drain is doing is “ownership by proxy”, for which a &mut borrow is a great tool. To be safe, .drain(start..end) takes ownership by proxy of all elements in the range start.. during its operation. When it’s done, it gives end.. back to the Vec.

This is what the old drain did too, I think, except it didn’t have the complication of putting elements back in drop. This should still be present in HashMap and elsewhere (mayb they are safe though.)

I’m not sure if we have used this kind of pattern outside collections.

[llogiq]

I still think we should be able to abort on debug builds. I doubt it will make much of a performance difference (because it’s on a cold path), but provide very valuable information for a programmer intent on finding the issue.

I’m ok with leaking on release, as long as we get a measurable performance benefit as opposed to abprting.

[comex]

I mean, leaking is recovery in that it correctly simulates the behavior if the refcount were infinitely ranged - since some Rc objects must have been forgotten, it’s impossible for the count to legitimately go back to zero. So I’m not sure there needs to be any special debugging case for this.

edit: except for the mmap case, but I think that’s special enough to not really worry about.

[nikomatsakis]

I mean, leaking is recovery in that it correctly simulates the behavior if the refcount were infinitely ranged

I don’t think that’s necessarily true, if unsafe code is involved. The usual reason to “forget” something is because you have in fact ‘transformed’ it in some other way, and hence you may well “reconstruct” the Rc and drop it later.

[rkjnsn]

Reference count overflow feels – to me – like it could belong in that category

I suppose that depends on how much concession we want to make to the hypothetical larger-than-address-space collection. Without such a collection, getting to this situation requires leaking an Arc, and thus leaking the associated ArcInner and contained object is exactly the same behavior that would occur if the refcount had and infinite range and there were no overflow. Thus it is fully recoverable in a way that makes the externally-visible behavior indistinguishable from the theoretical ideal. With such a collection, however, the user could theoretically create and then destroy more than 2^32 Arc clones, which theoretically wouldn’t leak with an count of infinite range, but would with my solution.

I’ll also note that the possible solution I gave would only have to check for a negative count in dec if such a collection were possible. Otherwise, it would only need to check in inc like your abort solution, as it would be impossible for the user to have 2^30 Arc instances lying around to be destroyed.

I’m a little torn. Using such a collection feels like quite an edge case, but on the other hand, Rusts memcpy move semantics make it feel like such a collection should be completely valid. The fact that Rust’s semantics allow the creation of such a collection with a safe interface seems really cool, and I’d hate to disallow it for the sake of the reference counting of a handful of types.

[bluss]

Vec::drain can be fixed to not amplify by swapping out the Vec completely. So instead of taking ownership by proxy, it simply owns the Vec’s allocation. On drop (if that is reached), it’s switched back.

[Gankro]

@bluss that might be particularly nasty since you might rightly expect vec.ptr/capacity() to not change due to calls to this function. No matter what something truly disgusting is going to happen, though.

[bluss]

I don’t think it’s so bad, and it doesn’t change if the Drain doesn’t leak, which is very simple to make sure for most users.

[pythonesque]

I actually noticed this possibility the other day; I was hoping I was missing some reason that it would still be safe. Personally I would be happy to take the abort solution; code like this is already tricky (so I don’t mind much that this makes it more tricky) and it is hugely unlikely that this limit will ever be reached in the course of normal operations.

[Gankro]

I have a PR open: https://github.com/rust-lang/rust/pull/27174

[system]

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.