2
\$\begingroup\$

To get myself used to writing unsafe code, I wrote a collection which allows the user to keep immutable references to the elements of a vector while still being able to add new elements to it.

I would like to know if there is either a security problem with this code, an already implemented better alternative or some possible improvements in general (readability / performance).

pub struct UnsafeHolder<T> {
    items: Vec<Box<(T,String)>> // the vector contains Boxes, due to the fact that
                                // vectors can reallocate when adding elements
                                // which would end up creating dangling pointers
}

impl<T> UnsafeHolder<T> {
    pub fn new() -> Self {
        UnsafeHolder {
            items: vec![],
        }
    }

    // this method pretends to be immutable while actually adding
    // elements to the vector, this allows for continuous reference to
    // previous elements
    pub fn add_element(&self, element: T, key: String) {
        if !(self.items.iter().any( |i| i.1 == key)) {
            let mut items = unsafe {change_mut(&(self.items))};
            items.push(Box::new((element,key)));
        }
    }

    pub fn get_element(&self, key: &str) -> Option<&T> {
        if let Some(return_val) = self.items.iter().find(|i| i.1 == key) {
            Some(&return_val.0)
        }
        else {
            None
        }
    }

    pub fn clear(&mut self) {
        self.items = vec![];
    }
}

// this is used to change '&self' to '&mut self' to avoid the borrow checker
unsafe fn change_mut<T>(x: &T) -> &mut T {
    &mut *(x as *const T as *mut T)
}

This is the whole module, meaning that there should be no other ways than these 4 methods to interact with UnsafeHolder.

There is currently a problem due to the fact that items can be changed by multiple threads at once, resulting in an error.

Here is a link to the most recent version on playground.

\$\endgroup\$
2
\$\begingroup\$

Safety First

Unfortunately, programming in unsafe Rust requires respecting a number of rules; and you have broken at least one here.

Rust memory safety is based on the principle of Aliasing XOR Mutability, which is enforced as much as possible at compile-time for obvious performance reasons. When you wish to shift the responsibility from compile-time to run-time, you need to inform the compiler about it at the type level, lest it infers properties about the code that do not hold.

For interior mutability, use UnsafeCell.

This is the basic block that is used by all abstractions which defer the enforcement of the principle to run-time. For example, here is AtomicBool:

#[cfg(target_has_atomic = "8")]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct AtomicBool {
    v: UnsafeCell<u8>,
}

Thus, your type should be:

pub struct UnsafeHolder<T> {
    items: UnsafeCell<Vec<Box<(T,String)>>>,
}

Clean-up

UnsafeCell comes with a get method: UnsafeCell::get(&self) -> *mut T, and thus your change_mut function is unnecessary:

pub fn add_element(&self, element: T, key: String) {
    if !unsafe { & *self.items.get() }.iter().any(|i| i.1 == key) {
        let items = unsafe { &mut *self.items.get() };
        items.push(Box::new((element, key)));
    }
}

Nits and bits

Your add_element method should indicate when insertion fails; silent failures make programs harder to debug.

It seems strange to me to pass the element before the key; most APIs seem to do the reverse so I would advise following in their steps.

The complexity of your look-up is O(N), so that inserting repeatedly has O(N2) complexity; if you were sorting by key look-up could be O(log N) instead, and repeated insertion O(N log N).

I recommend avoiding unnecessary parentheses (such as in if !(...)); they clutter the code for no obvious gain.


Final Word

If you wish to venture into the world of unsafe, I recommend reading the Nomicon. Until Rust gets official unsafe semantics, it is probably the best reference about the dos and don'ts.

\$\endgroup\$
  • \$\begingroup\$ As it should be save to swap the elements of items, would you recommend to simply use binary_search_by_key as it should decrease the cost to O(log(n)) for both insertion and look-up. I believe that the rust compiler simply removes unused return values when optimizing, so there should be no runtime cost when ignoring the return value. I'm actually kind of unsure about changing !()to ! as it might prevent stupid mistakes like ! false || true instead of !(false || true) (it's probably just a habit from C++) \$\endgroup\$ – lncr Jul 29 '17 at 21:22
  • 1
    \$\begingroup\$ @SleepingPanda: Yes, I recommend the binary search approach for searching: it will give you either the position where the element is, or the position where to insert it. Regarding !, there are so many ways to mess up boolean conditions, I am not sure that adding parentheses really help... but if it helps you, why not! And thanks for the edit :) \$\endgroup\$ – Matthieu M. Jul 30 '17 at 10:26
  • \$\begingroup\$ I ended up including the now improved version of my code in my question, while I'm pretty sure that everything is fine now, it would still be quite reassuring to get the opinion of someone who knows what he is doing, so in case you have the time, please look at my code once more. :) ( I just realized that programming in rust made me insanely afraid of writing code which could have any kind of bug or security issue... I guess that even if someone does not use rust forever, it should still be quite helpful to learn it. :D ) \$\endgroup\$ – lncr Jul 31 '17 at 8:01
  • 1
    \$\begingroup\$ @SleepingPanda: Functionally/Safety-wise, looks good to me. Code wise I would make a few changes: (1) if most of the code is unsafe in a function, I'd just wrap it all in a single unsafe block, (2) I would take a mutable reference to the item within the UnsafeCell at the beginning, rather than type &mut *self.items.get() every time, (3) I would use Vec::clear rather than assign a new vector, so as to preserve capacity. \$\endgroup\$ – Matthieu M. Jul 31 '17 at 8:12
  • \$\begingroup\$ Thank you. I agree with (2) and (3). While (1) was appropriate before decreasing the amount of *self.items.get(), I now think that it is actually cleaner to keep using smaller unsafe scopes here. \$\endgroup\$ – lncr Jul 31 '17 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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