Re: [TECH TOPIC] Rust for Linux

[Wedson Almeida Filho <wedsonaf@google.com>]

On Wed, Jul 07, 2021 at 10:38:27PM +0200, Jan Kara wrote:
> On Wed 07-07-21 20:19:19, Wedson Almeida Filho wrote:
> > Where would a lock be needed in the examples above?
> 
> So I think Greg speaks about a situation where you have multiple threads
> and the refcounted object can be looked up through some structure all the
> threads see. And the problem is that the shared data structure cannot hold
> ref to the object it points to because you want to detect the situation
> where the data structure is the only place pointing to the object and
> reclaim the object in that case. Currently I don't see how to model this
> idiom with Rust refs.

The normal idiom in Rust for this is "weak" pointers. With it, each
reference-counted object has two counts: strong and weak refs. Objects are
"destroyed" when the strong count goes to zero and "freed" when the weak count
goes to zero.

Weak references need to upgraded to strong references before the underlying
objects can be accessed; upgrading may fail if the strong count has gone to
zero. It is, naturally, implemented as an increment that avoids going from 0 to
1. It is safe to try to do it because the memory is kept alive while there are
weak references.

For the case you mention, the list would be based on weak references. If the
object's destructor also removes the object from the list, both counts will go
to zero and the object will be freed as well. (If it fails to do so, the
*memory* will linger allocated until someone removes the object from the list,
but all attempts to upgrade the weak reference to a strong one will fail.)

The obvious cost is that we need an extra 32-bit number per reference-counted
allocation. But if we have specialized cases, like the underlying object always
being in some data structure until the ref count goes to zero, then we can build
a zero-cost abstraction for such a scenario.

We can also build specialised zero-cost abstractions for the case when we want
to avoid the 1 -> 0 transition unless we're holding some lock to prevent others
observing the object-with-zero-ref. For this I'd have to spend more time to see
if we can do safely (i.e., with compile-time guarantees that the object was
actually removed from the data structure).