`UnsafeCell` and slices, and discrete `RwLock`s

help
1

Background

I am trying to implement a flat list which contains sublists of the same size where each sublist is guarded by its own RwLock.

So, something like this:

use std::cell::UnsafeCell;
use crossbeam::utils::CachePadded;
use parking_lot::RwLock;

struct Layers {
    data: Box<[UnsafeCell<u32>]>, // I may have say N "virtual array" of size 16.
    rwlocks: Box<[CachePadded<RwLock<()>>]>, // Then, I will have an RwLock for each "virtual array", so a total of N here.
}

First Question

Which type should be used for data?

  • Box<UnsafeCell<[u32]>>: It's quite unintuitive to create a value of this type, one has to go through Vec::into_boxed_slice, Box::into_raw, pointer casting, Box::from_raw, etc. But I think this has the "most correct" provenance for the pointers obtained from UnsafeCell in the sense that they have write permission over the whole region of the slice.
  • Box<[UnsafeCell<u32>]>: For my use case, I will need to mutate other elements through a pointer to some element. In my understanding, the pointer may have the correct spatial permission as it inherited that from the slice but may not have the correct mutation permission (due to the requirement to use UnsafeCell::get and UnsafeCell::raw_get). In Does UnsafeCell::raw_get preserve pointer provenance? · Issue #474 · rust-lang/unsafe-code-guidelines · GitHub, RalfJung mentioned that:
    1. ... However we reserve the right to have something more strict in the future where if you do not go through raw_get, you are not allowed to perform mutation of the cell's contents ...
    2. UnsafeCell::raw_get does not do any "narrowing" of provenance to the type -- the entire memory range of the original provenance is preserved ...
  • UnsafeCell<Box<[u32]>: This feels even more wrong, to me the UnsafeCell is not enabling interior mutability to the memory region but the Box itself instead.

Second Question

Is it sound to use separated RwLocks that doesn't wrap the values (i.e., RwLock<()>)?

For one, although I believe RwLock does provide the required semantics for MT-safe access, UnsafeCell only mentioned atomics for synchronizing conflicting access: ... conflicting non-synchronized accesses must be done via the APIs in core::sync::atomic..

I'm not even sure if my reasoning is correct. Please correct me if there is any inaccurate description of the semantics. Help appreciated!

FYR: Read/Write guard for sublists 
impl Layers {
    ...

    /// Read-lock layer `layer` and return a guard for immutable access.
    fn layer_read(&self, layer: usize) -> LayerReadGuard<'_> {
        // TODO: Check `layer` range?

        let _guard = self.rwlocks[layer].read();

        let offset = self.layer_offset(layer);

        // SAFETY: We derive `data_ptr` from `self.data.as_ptr()` (provenance
        // over the whole allocation) via `UnsafeCell::raw_get`, rather than
        // indexing a single element (which shrinks the spatial permission),
        // so later pointer arithmetic that walks past this one cell stays
        // within the pointer's provenance.
        let base: *const UnsafeCell<u32> = self.data.as_ptr();
        let data_ptr = UnsafeCell::raw_get(unsafe { base.add(offset) }).cast_const();

        LayerReadGuard { _guard, data_ptr }
    }

    /// Write-lock layer `layer` and return a guard for mutable access.
    fn layer_write(&self, layer: usize) -> LayerWriteGuard<'_> {
        // TODO: Check `layer` range?

        let _guard = self.rwlocks[layer].write();

        let offset = self.layer_offset(layer);

        // SAFETY: We derive `data_ptr` from `self.data.as_ptr()` (provenance
        // over the whole allocation) via `UnsafeCell::raw_get`, rather than
        // indexing a single element (which shrinks the spatial permission),
        // so later pointer arithmetic that walks past this one cell stays
        // within the pointer's provenance.
        let base: *const UnsafeCell<u32> = self.data.as_ptr();
        let data_ptr = UnsafeCell::raw_get(unsafe { base.add(offset) });

        let cap = self.layer_cap(layer);

        LayerWriteGuard {
            _guard,
            data_ptr,
            cap,
        }
    }
}

struct LayerReadGuard<'a> {
    _guard: parking_lot::RwLockReadGuard<'a, ()>,
    data_ptr: *const u32,
}

struct LayerWriteGuard<'a> {
    _guard: parking_lot::RwLockWriteGuard<'a, ()>,
    data_ptr: *mut u32,
    cap: usize,
}
2

First, if the sublist length is constant, you can do it fully safely as Box<[RwLock<[u32; N]>]>.

Now to your questions:

Both UnsafeCell<[u32]> as [UnsafeCell<u32>] are fine, and you can transmute between them. For [UnsafeCell<u32>], you can do it via raw_get() but you can also not: the quote from Ralf Jung is not up to date: in Can a pointer obtained by casting `&UnsafeCell<T>` to `*mut T` be written to? · Issue #281 · rust-lang/unsafe-code-guidelines · GitHub it was decided that you can read/write to a pointer casted from &UnsafeCell without get(), although the docs aren't updated yet.

UnsafeCell<Box<[u32]>> is indeed not correct, except for one thing: you might not need UnsafeCell at all. Since you have an indirection, if you store a *mut [u32] you can do writes without any problems. But with Box this is more complicated since this type might have aliasing requirements (What are the uniqueness guarantees of Box and Vec? · Issue #326 · rust-lang/unsafe-code-guidelines · GitHub).

As for the second question, this is fine. While std does not document that RwLock creates a happens-before relationship, too much code in the wild relies on this (even for RwLock<()>).

3

The sublist length is indeed not constant, so I can't do the RwLock sized slice thing.

The GH issue you quoted is quite interesting, although it seems to be still an FCP only.

However, I don't think that casting between &UnsafeCell<T> from/to *mut T being sound makes my provenance concern go away. You can say that when I create the pointer to the first element, that pointer has spatial permission to the whole slice as it is one allocation as a whole. However, I'm not sure if I crossed the boundary of the UnsafeCell with pointer arithmetics, it has the mutation permission or even the permission to read the second or later elements.

From an application point of view, am I allowed to create a subslice &[T] from a raw pointer to one of the elements (assuming [UnsafeCell<u32>] is used)?

4

FYI: I have started a topic on Rust Zulip (#t-opsem > Clarification on &UnsafeCell<T> to/from *mut T).

6

might help to know how it's determined then, feels odd for sublist lenght to come from anywhere other than the struct initialization in which case it might be possible to integrate it better into the type structure

7

It is not constant in the sense that it's determined in runtime. I am actually implementing HNSW (a multi-layer graph structure), so depending on the M parameter (number of neighbors a node can have), my sublists will have different lengths.

8

After the discussion over in #t-opsem > Clarification on &UnsafeCell<T> to/from *mut T, my personal conclusion for this is:

  • Both types Box<UnsafeCell<[T]>> and Box<[UnsafeCell<T>]> are fine.
  • Whether subslicing/indexing is sound depends on whether the intermediate pointer/reference has provenance over the whole memory region or not, i.e.:
    • For Box<UnsafeCell<[T]>>, you can do box.get().cast() (Box<UnsafeCell<[T]>> -> *mut [T] -> *mut T), a &UnsafeCell<[T]> is created by .get() but it has provenance over the whole region so it's fine).
    • For Box<[UnsafeCell<T>]>, you can do UnsafeCell::raw_get(box.as_ptr()) (Box<[UnsafeCell<T>]> -> *UnsafeCell<T> -> *mut T), no intermediate reference created so provenance is inherited all the way.
    • But for Box<[UnsafeCell<T>]>, you cannot do (&box[i]).get() (Box<[UnsafeCell<T>]> -> &UnsafeCell<T> -> *mut T) then create a slice from it because the intermediate reference to the some element (&UnsafeCell<T>) MAY have a shrank provenance (not well specified as of now). There is an active open discussion over in #t-opsem > Vibes on subobject provenance whether a reference to a subobject has provenance over the greater object (the whole memory region in this case).

For RwLock, I don't have much to add.