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

[llogiq]

I’m not sure if panicking is a good idea

In debug code, it should be a no-brainer – as was noted before, using up 31 bits of refcount is bad news, so we might as well give the coder the headlines. In release / bench code, I’ll concede that just leaking is probably good enough.

Also, it’s worth pointing out that this is only needed on 32-bit systems, if the logic around 64-bit overflow being impractical is accepted.

This hinges on the idea of somehow keeping LLVM from munging all our increments together. Has this already been implemented?

[bluss]

(Also, it’s worth pointing out that this is only needed on 32-bit systems, if the logic around 64-bit overflow being impractical is accepted.

Ah but overflowing 64-bit is practical if llvm realizes it can do it for you without discrete steps. Beautiful, isn’t it?

If you remove the print, LLVM realizes it can skip the loop and segfaults immediately on both 32-bit and (changing the iteration count) 64-bit targets.

[Diggsey]

Something like this x86 code might be faster on architectures without a saturating add instruction:

        add [counter], 1
        jns skip
        dec [counter], 1
skip:

Branch prediction should help reduce overhead.

[nikomatsakis]

@Gankro I’m trying to decide how fundamental this problem is – this “amplification effect” that you achieved with drain, is that specific to the drain API or do you think you could achieve it with other (stable) vec APIs?

[Gankro]

@nikomatsakis

As far as I recall, it’s currently fairly unique to Vec::drain in that it:

• moves data out of the collection without consuming the collection
• via a proxy value
• and the leak doesn’t itself leak the collection’s allocation

However there may be other cases where a collection chooses to handle unwinding-safety like this: mark the collection as empty temporarily so that a panic just leaks all the elements.

e.g. @bluss briefly considered moving forward with such a design if cmp panicked in BinaryHeap: https://github.com/rust-lang/rust/issues/25842

There’s no way to “abuse” that one without catch_panic though, because unlike Drain it doesn’t expose a secondary handler type.

Generally I consider leak amplification to be a necessary evil in a world with uncatchable panics and safe forget.

[bluss]

You make Vec::drain(..) sound so terrible. It’s not a surprise, it came onto the scene in the aftermath of a revolution.

[rkruppe]

Wrong, Vec::drain dates back to at least RFC 509 in December 2014 (I think the idea is even older). The implementation has changed to not be unsafe when the drain iterator is leaked, but the API didn’t. The drain iterator’s destructor would free the remaining values in the vector, so even if leaking was unsafe, leaking the drain iterator would also leak the remaining values in the vector — only it wouldn’t free the objects that were moved either, so it was completely unsafe in addition to amplifying leaks.

Actually Vec::drain was designed unaware of leaks in possible in safe code (remember, those were always possible!) and that the API works nevertheless, although with a slightly different implementation, is a happy accident discovered during the leakpocalypse. The API dates back to a happier, “leak-free” time.

[bluss]

Ah but the new drain’s API did change, it takes a range now. And I did write it with the mem forget issue fresh in memory.

[nikomatsakis]

Generally I consider leak amplification to be a necessary evil in a world with uncatchable panics and safe forget.

Specifically, I was trying to understand whether it would be possible to deprecate safe forget and add the condition that it must consume memory. It seems awfully subtle though and I second the general concern that we’re forgetting things (no pun intended) that could permit leak amplification in other cases.

[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.