8
\$\begingroup\$

For some context, this is inspired by my attempt to solve this SO question.

I have a mutably borrowed slice representing a 2D array, and I want to split the borrow such that I can access all the rows or all the columns at the same time. Splitting into rows is easy, I just have to call split_at_mut repeatedly to obtain a mutable subslice for each row.

But columns are harder because the elements in a column are not contiguous in the slice. My idea is to create a pseudo-slice (Column) that implements Index such that it accesses the elements in a column inside the original slice. The Column struct has a period that is the width of a row (i.e. the number of columns), and an offset that is the index of the column. Columns that have the same period but different offsets are guaranteed to be disjoint, so sharing the same mutable borrow should be safe.

The way to create them is to construct a ColumnIterMut iterator, which will yield all the columns for a specified period.

To construct multiple mutable columns sharing the same slice simultaneously, I had to use raw pointers. I've been writing Safe Rust for a fair amount of time now, but I'm still just learning Unsafe Rust. So, most importantly, I would like you to check if my implementation is actually sound. I'm mainly concerned by aliasing rules and conforming to the Stacked Borrows model. Also, is it correct for me to implement Send and Sync here? The code works and even Miri doesn't complain, but I'm still not 100% sure that it won't cause UB under some circumstances.

A less important aspect is, if my code tirnd out to be correct, what additional traits/methods should I implement on Column to make it more user-friendly?

Here is the code:

use core::ops::{Index, IndexMut};
use std::marker::PhantomData;

pub struct ColumnIterMut<'a, T>{
    data: &'a mut [T],
    period: usize,
    offset: usize
}

impl<'a, T> ColumnIterMut<'a, T> {
    pub fn new(data: &'a mut [T], period: usize) -> Self {
        assert!(period > 0);

        Self { data, period, offset: 0 }
    }
}

impl<'a, T> Iterator for ColumnIterMut<'a, T> {
    type Item = Column<'a, T>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.offset < self.period {
            let col = Column{
                ptr: self.data as *mut [T], 
                _lifetime: PhantomData,
                offset: self.offset,
                period: self.period
            };

            self.offset += 1;

            Some(col)
        } else {
            None
        }
    }
}

//INVARIANT: period > 0
//INVARIANT: offset < period
//INVARIANT: ptr is always non-null, well-aligned and points to a valid instance of [T]
//INVARIANT: all Column structs sharing the same slice of data simultaneously
//           must have equal `period`s and distinct `offset`s
pub struct Column<'a, T>{
    ptr: *mut [T],
    _lifetime: PhantomData<&'a mut [T]>,
    
    period: usize,
    offset: usize,
}

impl<'a, T> Column<'a, T> {
    pub fn len(&self) -> usize {
        unsafe{
            ((*self.ptr).len() + self.period - self.offset - 1) / self.period
        }
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    fn map_index(&self, index: usize) -> usize {
        index * self.period + self.offset
    }
}

impl<'a, T> Index<usize> for Column<'a, T> {
    type Output = T;
    
    fn index(&self, index: usize) -> &Self::Output {
        unsafe{
            //SAFETY: if the invariants are maintained, the indices returned by 
            //        `Self::map_index()` will be exclusive to this instance of the struct
            &(*self.ptr)[self.map_index(index)]
        }
    }
}

impl<'a, T> IndexMut<usize> for Column<'a, T> {    
    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
        unsafe{
            //SAFETY: if the invariants are maintained, the indices returned by 
            //        `Self::map_index()` will be exclusive to this instance of the struct
            &mut (*self.ptr)[self.map_index(index)]
        }
    }
}

unsafe impl<'a, T> Send for Column<'a, T> where [T]: Send {}
unsafe impl<'a, T> Sync for Column<'a, T> where [T]: Sync {}

GitHub

\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Love the idea!

Disclaimer: I am sketchy on the requirements and effects ofPhantomData, so I'll abstain from comments on that.

Differentiate Column and ColumnMut.

I'd advise calling this struct ColumnMut, and reserve Column for the non-mutable version.

Behold NonNull.

Rather than specifying as an invariant that ptr is non-null, you should use the NonNull type.

Apart from a better API and a better guarantee, this will also create a niche within the ColumnMut so that Option<ColumnMut> will have the same size as ColumnMut. Pretty neat.

pub struct ColumnMut<'a, T> {
    ptr: NonNull<[T]>,
    ...
}

Consider zero-sized structs.

Slices of zero-sized structs are particular, as they reference a zero-sized array, and may have nigh arbitrary length.

You could either disable support for them outright -- panicking in the constructor for example -- or else you'll need to double check your implementation.

I'd advise creating a test with the largest Vec<()> you can get, getting a slice from that, and then testing operations on the two edge cases that are single row and single column (min/maxing length and period).

Consider implementing Default for ColumnMut.

You can use a dangling pointer and a length of 0.

(Performance) Consider a different representation.

The problem of the current representation is that len() uses / self.period. A division by a (large) integer is the slowest arithmetic operations possible: between 30 and 90 CPU cycles, when an addition/subtraction is 1 cycle and a multiplication 3 cycles. This is because it's implemented by trial division, primary school style.

It's all the more problematic here that you use len repeatedly, it's the basis of pretty much all other implementations. The cost is going to add up quickly.

Rather than storing the length of the slice (as part of [T]) you could instead directly store the length of the column (number of rows).

Similarly, you store the offset, requiring you to add it at every turn. Addition is fast (1 cycle) but that's an extra 8 bytes (+33%). Instead, you could just offset the pointer once and for all when creating the ColumnMut, and you'd be good to go.

pub struct ColumnMut<'a, T> {
    ptr: NonNull<T>,
    length: usize,
    period: usize,
    _lifetime: PhantomData<&'a mut [T]>,
}

impl ColumnMut<'a, T> {
    /// Creates an instance of the given length, based on the given number
    /// of rows and the column index.
    ///
    /// # Safety
    ///
    /// - The slice must be alive and must NOT be aliased for `'a`.
    /// - All instances of `ColumnMut` referencing this slice MUST be defined
    ///   with the same number of rows and a distinct column index.
    /// - `number_rows * number_columns` must be equal to `slice.len()`.
    /// - `column_index` must be strictly less than `number_columns`.
    pub unsafe fn new(
        slice: NonNull<[T]>,
        number_rows: usize,
        number_columns: usize,
        column_index: usize,
    ) -> ColumnMut<'a T> {
        //  Any safety invariant which CAN be verified SHOULD be verified in
        //  Debug mode.
        debug_assert_eq!(number_rows * number_columns, slice.len());
        debug_assert!(column_index < number_columns);

        let length = number_rows;
        let period = number_columns;
        let _lifetime = PhantomData;

        if length == 0 {
            let ptr = slice.as_non_null_ptr();

            return Self { ptr, length, period, _lifetime, };
        }

        //  SAFETY:
        //  - `column_index` is within bounds of the original slice, since
        //      * `column_index < number_columns`,
        //      * `number_rows * number_columns == slice.len()`,
        //      * and `number_rows > 0`.
        //  - `column_index` does not overflow an `isize`, since it's within
        //    bounds of the slice and a slice size does not overflow an `isize`.
        let ptr = unsafe { slice.as_non_null_ptr().add(column_index) };

        Self { ptr, length, period, _lifetime, }
    }   

You may even consider using u32, instead of usize, as having more than 4 billions of columns, or 4 billions of rows, is fairly unlikely in the first place -- it requires 4 GB of memory for the smallest 1 byte struct.

(Safety) Use the unsafe_ops_in_unsafe_fn lint.

It requires using unsafe for unsafe operations even in unsafe functions, making them stand out, and ensuring you don't forget the matching SAFETY comment.

//  In lib.rs or main.rs
#![deny(unsafe_ops_in_unsafe_fn)]

(Safety) Don't be greedy.

It's tempting to pack as much as possible in a single unsafe statement, but the problem is that it makes it hard to properly document why each individual operation is valid.

Instead, prefer splitting each operation in a separate block, unless the same justification can made for multiple operations at once.

(Safety) Don't repeat yourself.

It's not an advice specific to safety, but it's all the more important when safety's at stake.

Part of the reason for being "greedy" (packing statements, skimping on the SAFETY comment, ...) is that you're repeating yourself. And it'd be worse if you had the appropriate get and get_mut fallible implementation, as you'd have 4 implementations of getting an element.

Instead, do it ONCE and do it WELL.

(Safety) Avoid materializing the reference to the underlying slice.

I am surprised that MIRI isn't complaining -- maybe a gap in the tests?

When materializing &mut ... from raw pointers, I recommend never materializing intermediate references. There's too much of a chance of accidentally materializing an overlap: even if afterwards you only take one field or one element, if there's a moment in time where overlap exists, who knows what the compiler/optimizer might do.

Thus, I'd recommend sticking with pointer arithmetic until you have a pointer to a guaranteed not-to-overlap piece of memory, in your case, a T.

(Safety) Putting all those remarks together.

Focusing on the new stuff:

impl<'a, T> ColumnMut<'a, T> {
    /// Returns a reference to the element at the specified `index`, if within bounds.
    pub fn get(&self, index: usize) -> Option<&T> {
        let pointer = self.get_pointer(index)?;

        //  SAFETY:
        //  - `pointer` is within bounds, as per `self.get_pointer`.
        //  - `pointer` is correctly aligned, and points to readable memory.
        //  - `self` has exclusive access to `*pointer`, guaranteeing the
        //    absence of mutable borrow from outside `self` for the lifetime
        //    of `&*pointer`.
        //  - `&*pointer` borrows `&self`, guaranteeing the absence of mutable
        //    borrow from `self` for its lifetime.
        Some(unsafe { &*pointer })
    }

    /// Returns a reference to the element at the specified `index`, if within bounds.
    pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
        let pointer = self.get_pointer(index)?;

        //  SAFETY:
        //  - `pointer` is within bounds, as per `self.get_pointer`.
        //  - `pointer` is correctly aligned, and points to readable memory.
        //  - `self` has exclusive access to `&mut *pointer`, guaranteeing the
        //    absence of borrow from outside `self` for the lifetime of 
        //    `&mut *pointer`.
        //  - `&mut *pointer` borrows `&self` mutably, guaranteeing the absence
        //    of borrow from `self` for its lifetime.
        Some(unsafe { &mut *pointer })
    }

    //  Returns a pointer to the element at the specified `index`, if within bounds.
    fn get_pointer(&self, index: usize) -> Option<NonNull<T>> {
        if index >= self.length {
            return None;
        }

        if mem::size_of::<T>() == 0 {
            return Some(self.ptr);
        }

        //  SAFETY:
        //  - `index * self.period` is within bounds of the original slice.
        //  - `index * self.period` does not overflow an `isize`, since it's
        //    within bounds of the original slice and a slice size does not
        //    overflow an `isize`.
        let pointer = unsafe { self.ptr.as_ptr().add(index * self.period) };

        NonNull::new(pointer)
     }

Having written the fallible versions, the infallible ones are dead easy:

impl<'a, T> Index<usize> for ColumnMut<'a, T> {
    type Output = T;

    fn index(&self, index: usize) -> &Self::Output {
        let Some(element) = self.get(index) else {
            panic!("{index} is out of bounds (>= {})", self.length);
        };

        element
    }
}

impl<'a, T> IndexMut<usize> for ColumnMut<'a, T> {
    fn index_mut(&self, index: usize) -> &mut Self::Output {
        let Some(element) = self.get_mut(index) else {
            panic!("{index} is out of bounds (>= {})", self.length);
        };

        element
    }
}

Use a better named argument for ColumnIterMut::new

That period is fairly confusing. This is the number of columns, just name it so.

(Safety) What about ColumnIterMut?

I am uneasy, once again, due to the presence of the mutable slice.

After obtaining a ColumnMut from the iterator, you have both:

  • A mutable slice within ColumnIterMut.
  • A ColumnMut instance allowing to materialize a mutable reference to elements of this mutable slice.

This is a recipe for disaster, in my view, and I'd feel better if ColumnIterMut instead embedded a NonNull<[T]> so that if anyone wants elements out of that, they'll have to first do a safety assessment.

Put together:

pub struct ColumnMutIter<'a, T> {
    slice: NonNull<[T]>,
    length: usize,
    period: usize,
    offset: usize,
    _lifetime: PhantomData<&'a mut [T]>,
}

impl<'a, T> ColumnMutIter<'a, T> {
    pub fn new(slice: &'a mut [T], number_columns: usize) -> Self {
        assert!(number_columns > 0);

        //  Consider this case, silent failure seems odd.
        debug_assert!(number_columns <= slice.len());

        let slice = NonNull::from(slice);
        let length = slice.len() / number_columns;
        let period = number_columns;
        let offset = 0;
        let _lifetime = PhantomData;

        Self { slice, period, offset, _lifetime }
    }
}

impl<'a, T> Iterator for ColumnMutIter<'a, T> {
    type Item = ColumnMut<'a, T>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.offset < self.period {
            let result = ColumnMut::new(self.slice, self.length, self.period, self.offset);

            self.offset += 1;

            Some(result)
        } else {
            None
        }
    }
}

The length in my implementation is "overkill". You could do without if you removed the matching debug statement in ColumnMut::new. But it doesn't cost much to keep it, so why not?

(Safety) Your Send and Sync look odd.

A ColumnMut is a reference to a slice, not a slice itself, so I'd change the where clauses to &'a mut [T]: Send (or Sync) to match. Probably inconsequential, but it'd match exactly, rather than closely, and who knows what differences lurk there?

Where are the tests?

You didn't show any test.

It's important to have good test coverage for unsafe code, because the only analysis tools that you have (MIRI, Sanitizers, Valgrind, ...) only check that the code that is running looks OK.

So, first things first, write tests as you would normally. You want to verify that each function, in isolation, works as expected, including in edge cases:

  • This means checking zero-sized elements.
  • This means using cargo tarpaulin (or equivalent) to check code coverage and verifying that you exercise all code-paths.

It's unsafe code, be thorough.

On top, you also need some specific testing techniques for unsafe code.

You want to check that borrow-checking works, or that Send and Sync are not implemented when they should not be. It seems silly, but when you write unsafe code and materialize references manually, you could have a fn get(&self) -> &'static T and it would compile... and because the lifetimes differ, it would not borrow self. Or you could accidentally delete that where clause on impl Send. Time to be paranoid.

You should (ab)use documentations tests, as they can test that compilation fails for a snippet:

#[cfg(test)]
#[doc(hidden)]
pub mod compiletests {
    /// ```compile_fail:Exxx
    /// let mut array = [1, 2, 3];
    /// let column = ColumnMut::from_slice(&mut array, 3, 0);
    ///
    /// let first = column.get(0);
    /// std::mem::drop(column);  // first should borrow until next line.
    /// std::mem::drop(first);
    /// ```
    pub fn column_mut_get_borrow() {}
}

And finally, you want to write tests specifically exercising overlapping borrows:

  • Between ColumnMutIter and ColumnMut: create a column, use it to access an element, create another column, use the element from the first.
  • Between ColumnMut instances: create two columns, grab an element (mutably) from each, use swap between them.

It's those tests that'll really validate whether the Stacked Borrow model is okay with what you're doing, or not.

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Miri doesn't complain about the references because they are valid according to Stacked Borrows, but there is still a problem: if somebody, concurrently, executes the code that materializes references, they will get two mutable references to the whole slice existing at the same time, which is UB. \$\endgroup\$ Jan 21, 2023 at 18:28
  • 1
    \$\begingroup\$ Oh, wow, that's a lot to take in. It's interesting that several of the mentioned issues originated from me not being "brave" enough to use pointer arithmetic and resorting to a pointer to the slice... Also, I did consider using NonNull, but I didn't feel qualified enough (the docs say "but is ultimately more dangerous to use because of its additional properties. If you’re not sure if you should use NonNull<T>, just use *mut T!"). And finally, I have to get into the habit of writing a lot of tests. I did write a basic one, but it was not at all comprehensive. \$\endgroup\$
    – FZs
    Jan 21, 2023 at 19:17
  • \$\begingroup\$ @ChayimRefaelFriedman Is that issue also present in Matthieu's version that uses pointer arithmetic instead? \$\endgroup\$
    – FZs
    Jan 21, 2023 at 19:21
  • 2
    \$\begingroup\$ @FZs No, it is fine because it never uses references to overlapping memory. \$\endgroup\$ Jan 21, 2023 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.