Save me from going `unsafe` here?

help
1

I'm working on an (as yet unreleased) document tree structure implementation that uses a vector of nodes, where each node contain indexes to parent, child, sibling nodes. Including memory footprint and access efficiency and ergonomics, the Vector/index approach seems to be working better than an Rc<Node> style tree. Now I have some mutating filter operations to support on the tree which can be modeled nicely using common visitor pattern implementation. However, I can't seem to make this work with the desired interfaces without unsafe-ly "disabling the borrow checker", and while my code "works" Miri certainly doesn't like it, and I'm not sure if I can prove its safe. A minimized example repro is provided below. Any suggestions on how to avoid the unsafe or prove its safe? I think this is the first time I've gotten stuck in the same way.

// Sample code license: Attribution 4.0 International (CC BY 4.0)

#[derive(PartialEq, Eq, Debug, Clone)]
enum Color {
    Green,
    Blue,
    Red,
}

#[derive(Debug)]
pub struct Palette {
    colors: Vec<Color>,
}

impl Palette {
    fn new() -> Palette {
        let mut colors = Vec::with_capacity(100);
        for i in 0..100 {
            colors.push(match i % 3 {
                0 => Color::Green,
                1 => Color::Blue,
                _ => Color::Red,
            })
        }
        Palette { colors }
    }

    fn filter<F>(&mut self, mut f: F) -> bool
        where F: Fn(&Palette, &mut Color) -> bool
    {
        if !self.colors.is_empty() {
            self.filter_at(0, &mut f)
        } else {
            true
        }
    }

    fn filter_at<F>(&mut self, i: usize, f: &mut F) -> bool
        where F: Fn(&Palette, &mut Color) -> bool
    {
        if self.colors.len() > i + 1 && !self.filter_at(i + 1, f) {
            self.colors.remove(i+1);
        }

        // Fails borrow-check:
        // error[E0502]: cannot borrow `self.colors` as mutable because it is
        // also borrowed as immutable
        // f(self, &mut self.colors[i])
        // -------------^^^^^^^^^^^----
        // | |          |
        // | |          mutable borrow occurs here
        // | immutable borrow occurs here
        // immutable borrow later used here

        // Works, but can we proove it to be safe, based on limitations of what
        // F could do in safe code?
        let p = &*self as *const Palette;
        f(unsafe { &*p }, &mut self.colors[i])
        // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        // Miri evaluation error: trying to reborrow for SharedReadOnly, but
        // parent tag <6241> does not have an appropriate item in the borrow
        // stack
    }

    fn len(&self) -> usize {
        self.colors.len()
    }
}

// Example filter
fn adjust_color(p: &Palette, c: &mut Color) -> bool {
    match c {
        Color::Green => p.len() % 2 == 0,
        Color::Blue => p.len() % 2 == 1,
        Color::Red => {
            *c = if p.len() % 3 == 0 {
                Color::Green
            } else {
                Color::Blue
            };
            true
        }
    }
}

fn main() {
    let mut p = Palette::new();
    p.filter(adjust_color);
    println!("result:\n{:#?}", p);
}

(Playground)

Output:

result:
Palette {
    colors: [
        Green,
        Green,
        Blue,
        Blue,
        Green,
        Blue,
        Blue,
        Green,
        Blue,
        Blue,
        Green,
        Blue,
        Blue,
        Green,
        Blue,
        Blue,
        Green,
        Blue,
        Blue,
        Green,
        Blue,
        Blue,
        Green,
        Blue,
        Blue,
        Green,
        Blue,
        Blue,
        Green,
        Blue,
        Blue,
        Green,
        Blue,
        Blue,
        Green,
    ],
}

Errors:

   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 0.51s
     Running `target/debug/playground`
2

One possibility is to move/copy the item being modified out of the Palette, and then move it back in afterwards:

        let mut color = self.colors[i].clone();
        let result = f(self, &mut color);
        self.colors[i] = color;
        result

Or instead of passing the filter predicate a reference to the whole Palette, you could pass it some subset of data that does not include access to the element it's modifying.

2 Likes
3

Thanks much for this suggestion as it helps me narrow in on the nature of the borrow-checker's issue with the interface.

Certainly for the above minimized example, yours is a perfectly valid alternative. For my real tree implementation, with existing benchmarks, if I replace the unsafe with your suggested approach (copy out and back in), it adds ~10% overhead to realistic filtering wall time. That might be acceptable given my stated concerns, but then, the fact that it works as safe code then, gives me more reason to believe that the unsafe version is perfectly safe.

Any suggestions for further reading on this nuance of borrow checking? Is this a common case where people resort to unsafe? If I keep the unsafe impl, do you think its possible to write a filter in safe code that breaks things? If necessary, I guess I could use the unsafe visitor only for the filter impls internal to my library, and then resort to the safe workaround for user-provided filters?

4

How so? They are doing completely different things. The whole point of borrow checking is that having other references to a value while also holding a mutable reference to it is not safe. If the 10% performance penalty is unacceptable, try splitting up the borrows as per @mbrubeck's second suggestion.

No.

1 Like
5

Very much no. This already can be quite clearly used to invoke UB:

fn adjust_color(p: &Palette, c: &mut Color) -> bool {
    *c = Color::Blue;
    let s1 = format!("{:?}", p);
    *c = Color::Red;
    let s2 = format!("{:?}", p);
    
    // The compiler reserves the right to assume
    // that s1 == s2 since p was immutably borrowed,
    // and thus optimize this away.
    assert_eq!(s1, s2, "This should fail!");
    true
}
2 Likes
6

That fact that it works as safe code means that LLVM was constrained by Rust's semantics for the safe code to NOT mis-optimize your program logic. You remove that constraint on LLVM the moment that you introduce UB, which occurs when you use unsafe to code a mut ref concurrent with immutable refs to the same object. Once you have UB you should assume that LLVM will miscompile your program, potentially differently each time your code changes, or the code in an included library changes, or the code in rustc changes.

3 Likes
7

Thanks all for the comments, and I hope this doesn't sound unthankful. Really, I did ask for and greatly appreciate the feedback!

For me the unsafe dark side was tempting enough at least to leave in place while I prototyped other aspects of my library. But I can't actually replicate @ExpHP's expected UB: playground v2, nor does valgrind suggest any problems. To interpret you literally would seem to suggest that other people, even more reasonable than me, wouldn't also be tempted by unsafe for this same case!

I'm going to see if I can change the real interface to be safe in different way (moving the mutations out of the filter Fn), and hopefully without introducing a 10% perf penalty. I'll followup here.

8

Try running it with miri. You can find it under the tools on the playground. It will detect the UB.

1 Like
9

Here's an example of UB in safe code (playground):

fn adjust_color(p: &Palette, c: &mut Color) -> bool {
    let c1 = &p.colors[0];
    let c2 = c1.clone();
    
    *c = Color::Blue;
    
    assert_eq!(c1, &c2);
    
    true
}

c and c1 clearly violate the aliasing rules, and the value behind c1 gets mutated even though it is borrowed immutably.

You can prevent this from happening in code outside your module, if there is no public way to access the Color values from a &Palette. Even then you might still need some UnsafeCell involved for it to be sound.

3 Likes
10

Thanks @mbrubeck, I can repro that UB, and not just as a Miri warning. While I think it would be an unusual implementation (didn't appear in the 7 filters I wrote in real library) I certainly don't want to inflict such a possibility on myself or others!

1 Like
11

It doesn't matter whether you can "reproduce" it; if it's UB, it's UB. In the case of my example, the compiler simply isn't smart enough yet to make this optimization. That doesn't mean it couldn't become smarter in the future.

It was unclear to me what the public API was (since nothing is marked pub) and whether the colors are directly exposed in any way, so I went with the one thing that (indirectly) accessed them in your original main function, which was the Debug impl.

4 Likes
12

To reiterate the point: Undefined behaviour means that although the compiler is allowed to do what you wanted, it also has permission to do something else. Sometimes you just get lucky.

13 Likes
13

And to take it just a bit further, aside from inter-thread send and sync stuff, the major real hazards in Rust involve mut ref and unsafe_cell. Rust's annotations on unsafe_cell suppress many (most?) of LLVM's code-movement optimizations, whereas for mut ref Rust tells LLVM to maximize its optimizations because there are guaranteed to be no other accesses to the ref'd object.

2 Likes
14

Why don't you make it Fn(&mut Palette, usize) -> bool with the usize passing an index to that color? This would be a common Rust like solution.

Alternatively, instead of passing a palette reference, pass the data that makes up the palette: Fn(palette_size: usize, color: &mut Color) -> bool

1 Like
15

Fair enough. I did find your first example illustrative of what to be worried about. Thanks!

@alice @TomP @H2CO3 @ExpHP Thanks for your patient efforts to educate/dissuade me from using unsafe here. Initially I thought this might just be some borrow limitation of a more complex kind than what we regularly encountered before the NLL checker. I needed a fresh reminder of the implications of the aliasing that still applies when coming from "both ends" of a somewhat complex data structure.

@johannesvollmer Thanks but keep in mind above (Palette) is a minimized example. Somewhat counter to my entertaining of unsafe, I don't want to pass a &mut Palette (or in my real code a &mut Document) here because certain modifications would violate invariants of the in-progress visitor (tree walker) implementation. In the real case, the Fn needs read-only access to parents, siblings and children to decide how to mutate the current Node, but is not allowed to mutate other nodes. And its not possible to just pass a single summary value like the length.

As @mbrubeck demonstrates, an easy resolution with the same interface is to clone/replace the Node (here Color) to avoid the aliasing. I'm now (still) trying to find a better performing and safe alternative interface.

16

It may not solve your entire problem, but have you considered deriving Copy for Color? Unless the real type is more complex, it looks simple enough, and would remove some of the friction from what you're trying to do.

1 Like
17

few suggestions:

  1. Presuming f will not access self.colors (which seems... likely?), one option would be to swap self.colors with a empty vector. You can guarantee that self.colors can't be accessed using a non exported struct field.
  2. I would also suggest writing an imperative loop here. You can keep track of the read index and write index separately, "shifting" the elements up one by one, and then leaving a tail & a count of things to delete.
  3. Pass i to f -- if f has access to colors directly or via an updating function it's not that much worse to have a helper which mutates based on i. You can even wrap the index sent to an opaque type. But then you need to make the whole palette mutable, or use a mutex on the vector
18

If a type is copyable, even if not explicitly implementing Copy, a clone operation will not be more expensive than a copy, right?

19

I think so? My suggestion was more of an ergonomic one than a performance fix.

1 Like
20

The Clone implementation is separate from the Copy implementation. The latter is a strict copy of the memory and you cannot influence that behavior. Clone, on the other hand, leaves the implementation details to the user. You can do whatever you want inside that method as long as you satisfy the return type. However, if you implement Copy for a type then the Clone implementation really should not behave differently from what Copy does, otherwise you will probably cause unexpected behavior and unnecessary headaches.

3 Likes