Where to put the interior mutability?


#1

I am working on a Scheme interpreter in Rust, and am having some difficulties with interior mutability.

Specifically: the Scheme heap consists of cells (each 1 word in size). All cells are mutable, and any allocation could change all of them (by causing garbage collection).

The collector is a simple cheney-style stop-and-copy algorithm. Since it is a copying algorithm, all Scheme values must be in areas tracked by the GC whenever an allocation may occur.

Scheme values are defined as

pub struct Value {
    contents: usize,
}

OR (not sure which to choose)

pub struct Value {
    contents: std::cell::Cell<usize>,
}

where the usize can either store a number or a (tagged) pointer into the heap.

The problem is that every Scheme value is aliased by the garbage collector – and by values of distinct types, to boot. In particular, the GC needs to be able to mass-copy Values with functions like ptr::copy_nonoverlapping, which take *mut arguments. And it would be nice to do without having to set each Cell individually – I would much prefer a memcpy. Furthermore, the fromspace and tospace are each of type Vec<Value>, so it would be nice to work with that too.

So the key questions are

  1. Is it valid to use memcpy to copy some memory that contains UnsafeCells?
  2. Where do I put the interior mutability? In the Value type, in the types that contain it, or both?

#2

std::slice::copy_from_slice is a thin wrapper around memcpy; it’s worth considering whether that’s sufficient for your purposes. If you’re not using unsafe code, you don’t have to worry about undefined behavior (whether you’re talking about the detailed rules for UnsafeCells or accidentally screwing up the length of the copy).

If you do need to use raw pointers, you should consider just using raw pointers instead of mixing raw pointer types with reference and Cell types. If you have a Vec<usize>, you can call as_mut_ptr() on it to get a raw pointer; you can use that to read and mutate the Vec’s memory exactly the way you would expect.

I’m intentionally avoiding answering your question about memcpy targeting an &[Cell<usize>] because the answer isn’t completely clear; the interaction between references and raw pointers is complicated. See also https://github.com/rust-lang/rfcs/pull/1643 .


#3

I am writing (actually, have written) a copying garbage collector, so I don’t see a way around unsafe code and raw pointers.


#4

I am writing (actually, have written) a copying garbage collector, so I don’t see a way around unsafe code and raw pointers.


#5

Does my suggestion to use as_mut_ptr() not work for some reason?


#6

It is exactly what I am doing (and the resulting code passes its tests). I just wanted to check that what I am doing had well-defined behavior.


#7

Should be well-defined; the tricky cases essentially all involve mixing raw pointers with variables of reference type.