Interest in Gc'ing non-Boxed types?

[mtak-]

If std::marker::Freeze was stabilized, crossbeam could have a AtomicCell-like type where load works with non-Copy data structures. Is this something crossbeam would be interested in? I've called it Inline in the examples below.

It roughly works as follows:

impl<T: Freeze> Inline<T> {
    pub fn load<'g>(&'g self, _: &'g Guard) -> Snapshot<'g, T>;
}

load requires Freeze instead of Copy. It takes in a Guard, and performs a read (in the same memcpy style as AtomicCell), but returns a Snapshot<'g, T> which holds on to the lifetime of both the cell and the guard, provides only immutable access, and does not drop the value read.

impl<T: 'static + Freeze + Send> Inline<T> {
    pub fn store(&self, val: T, guard: &Guard);
}

store requires Freeze and Send. It takes in a Guard. If the type does not need dropping, then it behaves just as AtomicCell. If it does need dropping, then it instead performs an atomic swap (a la AtomicCell), and then defers the drop of the old value: guard.defer(move || drop(old)).

Types like String/Vec<T>/etc. could now be gc'ed without having to be Boxed first.

I have an implementation here which is largely copy-paste from AtomicCell.

[jeehoonkang]

Sorry for my lack of knowledge.. but I couldn't find good documentation of Freeze. May I ask if you could recommend one for me so that I can better understand this PR?

[mtak-]

No worries! AFAIK there is no good documentation of the current version of Freeze. The definition can be found here

/// Compiler-internal trait used to determine whether a type contains
/// any `UnsafeCell` internally, but not through an indirection.
/// This affects, for example, whether a `static` of that type is
/// placed in read-only static memory or writable static memory.
#[lang = "freeze"]
pub(crate) unsafe auto trait Freeze {}

impl<T: ?Sized> !Freeze for UnsafeCell<T> {}
unsafe impl<T: ?Sized> Freeze for PhantomData<T> {}
unsafe impl<T: ?Sized> Freeze for *const T {}
unsafe impl<T: ?Sized> Freeze for *mut T {}
unsafe impl<T: ?Sized> Freeze for &T {}
unsafe impl<T: ?Sized> Freeze for &mut T {}

Freeze forbids any direct interior mutability. Types like AtomicUsize, Mutex, Cell are not Freeze, but most ordinary types are e.g. Vec<T>, Box<T>, String. Interestingly, types like Box<AtomicUsize> are also Freeze since the interior mutability is through a pointer.

Freeze is possibly interesting to crossbeam because it can be used (or so I claim) to perform safe aliasing through memcpy's instead of through pointers. If the memcpy is made using AtomicCell style optimistic reads, then that copy is only valid if the original value is not dropped or mutated. The original value is allowed to be moved, since we have a shallow copy and don't care about it's address. Combining this with EBR means store can move the overwritten value into the garbage collector without interfering with any snapshots that have been read on other threads.

Example usage:

let s = Inline::new("hello".to_owned());
let guard = &epoch::pin();
let hello = s.load(guard);
s.store(" world!".to_owned(), guard);
let hello_world = hello.clone() + &*s.load(guard);
assert_eq!(hello_world, "hello world!");

Hope that helps!

My intention wasn't to make a PR, but to see if there was any interest in it. I would want to make an RFC first, and also make an attempt at a rust-lang RFC to stabilize Freeze.

[jeehoonkang]

It seems Freeze is similar to The D language's "immutable reference" (https://dlang.org/spec/const3.html#const_and_immutable), right?

I like this idea :) One thing I'm wondering is whether we can merge Inline and AtomicCell, because they are so much like each other.

[mtak-]

From what I read (not too familiar with D), references to Freeze types are almost "immutable references". Freeze has no transitivity through pointers.

Freeze:

• String
• Box<Mutex<String>>

Not Freeze:

• Mutex<String>

AtomicCell could probably be implemented in terms of Inline, but unfortunately Inline depends on crossbeam-epoch which depends on crossbeam-utils.

I'm planning on an RFC to make Freeze or some version of Freeze a public API and adding this ticket as a motivation for it.