Save me from going `unsafe` here?

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?

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

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

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

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.

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

1 Like

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

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

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

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

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

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

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.

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

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

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

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

1 Like

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

Regarding Copy: the real Node (unlike Color) has references to heap allocated Vec and buffer types, so it can't be Copy. I should have added something like that to the minimized example to make it more clear.

I've ended up staying with @mbrubeck's first recommended solution for this, with a few optimizations that bring the "performance cost of safety" down to 7.4% (wall time) in the normal case. One optimization was just to limit the move to a smaller inner struct that is really the desired target for mutations. This is a good direction in any case because it avoids any further possibility of mutations that could invalidate the tree walk. I looked at a bunch other options, including the use of Cell's, but they all appear to have other drawbacks.

The workaround requires a bit of documentation, but I suppose its better than having to explain the potential problems with the unsafe version. See excerpt from the real (as yet unreleased) library below:

/// Perform a depth-first (e.g. children before parent nodes) walk from the
/// specified node ID, applying the provided function.
///
/// The `Fn` can be a closure or free-function in the form:
///
/// ```norun
/// fn a_filter_fn(pos: NodeRef<'_>, data: &mut NodeData) -> Action;
/// ```
///
/// Where `data` provides read-write access to the the `NodeData` of the
/// current node being visited, and `pos` gives a read-only view to the
/// remainder of the `Document`, e.g. parent, children, and siblings of the
/// current node. Note that to avoid aliasing issues, the `NodeData` is
/// actually moved out of the `Document` and replaced with a
/// `NodeData::Hole` value which could be observed via `pos`. The
/// potentially modified `NodeData` is moved back to the `Document` if the
/// function returns `Action::Continue`. The function may also modify the
/// `Document` by returning other [`Action`] values.
pub fn filter_at<F>(&mut self, id: NodeId, mut f: F)
    where F: Fn(NodeRef<'_>, &mut NodeData) -> Action;

I learned some things about the borrow checker due to this scenario, but I think we are still friends. Thanks everyone for your suggestions!

1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.