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

Maybe roll back the safe mem::forget?

1 Like

One can still create a safe mem::forget via Rc cycles, but I guess that case won’t be optimized so well (and is contrived anyway).

I and a couple of other had mentioned that we could keep forget unsafe in a backcompat manner, but I think the consensus was that safe functions should not be marked unsafe because they are a footgun.

I hope that decision is reevaluated. Though perhaps directly fixing the overflow issue should work too.

1 Like

It’s interesting that the problem isn’t safe mem::forget specifically, but a safe mem::forget that doesn’t itself allocate (keep the forgotten object around somewhere in memory). The assumption implicitly relied on here is not that you can’t safely forget, but that the amount of times you can do so is constrained by the available memory to store the forgotten objects. Notably, it’s not clear that either of the main alternative proposals would’ve prevented this: both of which were concerned with narrowing, but not eliminating, the class of types which may be safely leaked. (I.e., I’m not sure whether or not they explicitly had a safe forget<T: Leak> resp. forget<T: 'static> as part of their text, but it would be consistent with their designs, and would give rise to the same issue.)

So one weird but straightforward solution would be to actually just make the safe mem::forget move the forgotten object to the heap (and perhaps add a separate unsafe variation on forget which, like the current one, doesn’t). This is pretty weird and narrowly tailored to closing this particular gap in the soundness of Rc, but we already do a lot of things to accomodate Rc, and pragmatically, it might be preferable to put the burden of suboptimal performance not on Rc but on forget (which no one is really meant to use anyways - it’s just there for display as deterrent against assuming its impossibility). I suppose the language spec would then also change accordingly from “destructors are not guaranteed to run” to “objects are not guaranteed to be deallocated”, or something… (Speaking of which - would it also be possible to trigger this overflow via the destructors-not-run-while-panicking avenue?)

In case it’s not obvious, I’m not sure what I think of this solution.

4 Likes

Basically, the new guarantee would be that rust will never deallocate something (make it unaddressable) before running its destructor (except when the program exits).

Yes, the ideal solution is to introduce a new guarantee: safe rust code will either run the destructor or leak the memory when “forgetting” a value, so that the number of “live” values always fits into usize (except when sizeof(Value) == 0).

But mem::forget is being used by unsafe code that needs to avoid Drop being called (e.g. because ownership of the underlying resource is moved from Rust to C code). Just last week I deleted the unsafe block around one of those calls, since it was producing the “unnecessary unsafe block” warning.

@glaebhoerl: I don’t think silently breaking my code by introducing an artificial memory leak in mem::forget is the solution here – it’s strictly worse than breaking my code by marking mem::forget as unsafe and making me add back the unsafe block.

In fact, grepping for mem::forget in vec.rs is quite instructive in seeing the valid use-cases of mem::forget:

  • Forgetting self in order to suppress the Drop impl and transferring ownership (e.g. Vec::into_iter())
  • Forgetting a value after making an unsafe copy using ptr::read
  • Forgetting zero-sized values in Vec::push, since they can be re-created from thin air later.

We’d need to formulate a guarantee that types like Rc can rely on while still allowing all of those uses in unsafe code.

So I see two main solutions here:

  1. Introduce the new guarantee, and make mem::forget unsafe. This is a breaking change, but how much code would really break? I’d expect most callers to still have the unsafe block around mem::forget calls, since it hasn’t been safe for all that long. On the other hand, a new guarantee means it’s one more thing to check when reviewing unsafe code. Writing unsafe Rust code is already more difficult than writing C code due to the number of (often poorly-documented) invariants you need to uphold. How much more do we want to add to this burden?

  2. Make Rc check for overflows. The expected performance cost on 64-bit platforms is extremely low / often zero – we just have to inhibit some optimizations to prevent overflows from being possible. On 32-bit there’s going to be a real cost, though probably not as bad as I initially thought.

If this were pre-1.0, I’d prefer option 1. Not sure now… this is a safety hole, and we’ve reserved the right to make breaking changes in these cases… but on the other hand, a fix without breaking changes should be the preferred solution in post-1.0 world. I guess we need more data to decide properly: a) How much code is going to break if we make mem::forget unsafe again? b) How big is the impact of overflow checks, both on performance and code-size?

How fascinating. And annoying.

I’m not sure that the right solution in retrospect would have been to keep forget unsafe, because I’m not sure that someone wouldn’t have just discovered some other way to leak without allocating. In other words saying that the safety of Rust depends on not running a value’s destructor implying reserving at least one byte of address space in perpetuity seems awfully shaky to me.

I think checking for overflow is probably a reasonable solution, at least for now. (Maybe you can use saturating arithmetic safely? Hmm.)

5 Likes

Good point. All you have to do is make something unaddressable so a custom “wider than memory” (stores data on disk) vec could do it.

Yes, saturating arith would be safe. All mem::forget does is artificially inflate ref count. Bad stuff only happens if you manage to artificially decrease ref count (which overflow does). To decrement refcount by k still requires k Rcs to exist simultaneously, which this code was already assuming was impossible for k = usize::max.

1 Like

@Gankra: good point, we only need saturating arith when incrementing the counter: once the counter reaches the maximum, it’s impossible for safe code to bring it back down to zero. This means the decrementing code can stay unchanged (no need to special-case the “counter is saturated” case).

This also suggests a cheap fix for Arc: If I see it correctly, it would be sufficient to replace

self.inner().strong.fetch_add(1, Relaxed);

with

if self.inner().strong.fetch_add(1, Relaxed) >= isize::MAX as usize {
     // poor man's racy saturating counter
     self.inner().strong.store(isize::MAX as usize, SeqCst);
     // sequential consistency is overkill,
     // but I don't trust myself to pick the correct ordering
}

Since Rc takes more than 2 bytes of memory, keeping the counter saturated around isize::MAX should be as safe as saturating at usize::MAX. While there is a race that allows the counter to temporarily exceed isize::MAX, this should be unproblematic: we can’t hit an overflow because that would require usize::MAX - isize::MAX threads, which can’t fit into memory. Losing some increment calls to race is harmless, they don’t have any effect on a saturated counter anyways. Losing some decrement calls to the race is also harmless, because we know the count can never reach zero again.

As for overhead, at least on x86 the comparison could use the sign flag that already gets set by the lock xadd instruction, so something similar to this change would only add a single assembler instruction to the hot path. There’s a good chance this costs zero cycles if branch prediction works properly.

4 Likes

Exactly my suggestion. Also see http://shipilev.net/blog/2014/on-the-fence-with-dependencies/ for a thorough discussion of load/store atomicity - in short, x86 32bit-systems usually don’t reorder instructions anyway.

Saturating math seems a bad solution due to the performance implications (the cost of it and the fact that it might prevent LLVM from eliding reference count operations).

This seems a very good reason to make mem::forget unsafe again.

Also in general I think that leaking Rc cycles cannot be disallowed by the language, but the API should reserve the right (and should do so in debug mode) to output an error on task (for Rc) or program (for Arc) termination and thus correct programs should not leak memory (this is easily done by keeping a list of all rc boxes and checking that it’s empty at termination).

Note that we don’t need saturating math on 64 bit architectures, only on 32 bit (ARM and x86). For the former, triggering unsafety would take a looong time while the latter makes it simple enough using a branch on the sign bit to implement a workaround to avoid it.

It occurred to me that the fundamental problem with Rc isn’t cycles, per se, it’s that it provides shared ownership in a system heavily designed for a single-owner multiple-borrow model.

While we might be able to use this to design a safer yet more performant approximation to shared ownership, I suspect there isn’t any way to use this to fix the current problem at hand :confused:

I’m finding these proclamations that this means mem::forget should be unsafe quite frankly crazy. If you can do it in safe code, it’s safe. Full stop. There’s no “oh well this is kinda of nasty, and it’s hard to do in safe code…”. If Rc can make cycles, then mem::forget is safe. These have been the semantics for over a year (though many of us forgot them because mem::forget was marked unsafe erroneously), and are the semantics we have stabilized on in 1.0.

And it’s all for a theoretical perf hit in one method that no one has benched? (thanks to @dgrunwald for bringing at least some numbers into this). Also this is very easy to fix now (do a checked or saturating add) with an eye to fixing any perf fallout later.

4 Likes

FWIW many people are of the opinion that footgunny things should be unsafe too, but that's debatable and should be decided elsewhere (I believe the current consensus is that unsafe means unsafe and nothing else)

Yeah, I find the saturating add method to be the best way to fix this now.

I could have misunderstood something, but isn't the key difference here that forgetting by Rc cycles actually leaks memory (in the sense that unreachable memory has not been free'd), but mem::forget doesn't?

I think @pcwalton is right that it seems too likely that it is possible by some means with the declared safe abstractions in std to completely free memory without running Drop for this to be a safety commitment that Rust makes, but I also think you're rather badly misrepresenting the other side of this.

Leak amplification is a thing you have to deal with when you start mixing mem::forget and collections. In particular the ever tricky Vec::drain guarded against forget by marking all of its memory uninitialized to start, so that if you leak it, all the happens is the dtors get leaked. As such it’s quite trivial to blow up an allocating leak into a much-less-allocating leak.

e.g.

let mut vec = vec![];
for i in 0..1000000 { vec.push(make_thing_to_leak()); }
forget_that_wastes_memory(vec.drain(..)); 
// wastes one Vec::Drain worth of memory, but we leaked 1000000 thing_to_leaks.

Note that you can re-use the same Vec over and over since it’s not freeing or leaking its actual buffer.

1 Like

But if it wastes even 1 byte of memory, an OOM error will occur rather than Rc overflowing using the code in the first post. Doesn't your code still do that?

1 Like

You can e.g. destroy thousands of Rc-s each time leaking a few bytes of memory.

Seems like its efficient collections, efficient Rc, memory safety - pick two.

That only holds if one byte per Rc is wasted. The code I provided wastes about 1 byte per 100000 Rc’s. This would overflow the Rc count after only ~40k of leaked memory (on 32-bit).