"Tootsie Pop" model for unsafe code

language design
61

Except that I don't care whether the compiler can see the non-aliasing. I only care that the user writing the unsafe code can prove that there won't be conflicting memory actions. Although indexing is a function call, it is a completely predictable function call that unsafe code writers understand completely, and so it isn't a burden to ask people to understand that it doesn't involve actually reading from the slice being sliced.

However, I think the "Tootsie Pop" proposal will only make this situation worse - by making it safer to change safe code in a module with unsafe invariants, the proposal only encourages this misunderstanding without really mitigating its effects. This proposal lulls people into a false sense of security.

Unfortunately, I believe that concurrent code does assume this already - there are many cases where AtomicUsize is used instead of AtomicPtr, including the fact that pointers need to be aligned, so when tagging pointers people indirect through usize.

I think this is assuming the main point of contention here, whether the boundary of unsafety is a module. I would argue that even when you use unsafe code, Rust can still prove that pointers don't alias, because you are responsible for leaving pointers nonaliasing when you exit an unsafe block (where I consider the boundary to be). If, in contrast, you assume the boundary to be the module, then what you said is correct, but only with that highly contentious assumption.

Except that no type system is ever sufficient. The beauty of privacy and unsafety is that you can make arbitrarily complex invariants that will never be included into the language, where you internally prove that your code is correct and expose the correct interface to ensure that. Arguing that we shouldn't pay attention to those uses of unsafety because the language will eventually patch the deficiencies is wrong because there are an infinite number of deficiencies.

Except that this is exactly the point being argued. If the unsafe boundary ends at the end of an unsafe block (which I think it should), then the compiler can assume that the assembly code does not stash the pointer somewhere, because otherwise the unsafe block would extend until that problematic behavior ended.

I think that this should be the behavior of plain unsafe blocks. If there is a need for aliasing unsafe blocks (which I don't think there is, given the right definition of alias), then those should be the specially distinguished ones, since those cause widespread, extra unsafe unsafety.

I like your distinction between the three zones. I would argue that 1 and 3 should be bounded by unsafe blocks (with 3 possibly even smaller) and 2 should not be constrained, stretching possibly to the whole crate, though authors should be encouraged to keep it much smaller.

Essentially, library authors are required to make sure that no code will break the type system/language invariants. Since they cannot know what usage code will be, zone 2 has to be bounded by the crate boundary. However, they are free to let unsafety bleed into however much or however little of their library as they wish, as long as the fastidiously avoid doing anything problematic.

As an example, in the implementation of BTreeMap, the node module uses lots of unsafety for speed. Various functions have preconditions that, if violated, cause memory safety. These are checked by debug_asserts, meaning that in a debug build, zone 2 is contained within the node module, but in a release build, it technically reaches into the main BTree map module. This seems very reasonable to me - functions are called with their preconditions satisfied, and, to ease development, this is double checked. However, the region in which someone could do something bad on a release build is larger to cut down on overhead, even larger than a single module.

The issue is that the BorrowRef is being dropped, and that doesn't touch the acual data stored in the RefCell. It does act somewhat barrier-like because it writes to the borrow tracking state, but that memory is distinct from the read in question, of the actual data stores beside the borrow tracking state.

2 Likes
62

Hm, whereas I feel that making (3) smaller than (2) is potentially very dangerous, as then the compiler may violate those more nuanced invariants - and I use that terminology carefully: The invariants of (2) are neither a superset of Rust's, nor a subset. Until and unless the optimizer can understand those invariants, violating them may cause safe Rust code to have unsafe effects.

63

The key property of an optimizer is that it doesn't change the behavior of code. The only way that it can is if the programmer lies to the compiler, promising something that isn't true. If, as I suggest, the programmer is responsible for fixing invariants at the end of an unsafe block, the programming will never be promising something false, and the optimizer can never break anything.

As an example, consider the split-at-mut-via-duplication case:

let copy: &mut [T] = unsafe { &mut *(self as *mut _) };
let left = &mut self[0..mid];
let right = &mut copy[mid..];
(left, right)

Using my definition of alias, I claim that there is nothing in this code in zone 3. copy and self do not alias, as there are no future writes or reads to copy or self that conflict. However, after line 1, the code is all in zone 2, as, e.g., a stray copy[0] = self[0] would invalidate the aliasing assumption, causing unsafe behavior.

I may be misunderstanding you, but I don't see how making zone 2 larger than zone 3 causes a problem with optimization.

64

This is what I was trying to get at in "Tootsie Pop" model for unsafe code - #11 by Ericson2314, but I think I can do better now. The "opposite" you mention is actually quite useful. The Vec fields are unsafe to construct, while the improper &muts are unsafe to eliminate. We could have a "variance" on unsafe fields which controls in which direction(s) (introduction or elimination) the unsafety matters.

Conversely, I think this bolsters the argument that unsafe-to-introduce for fields is better style than unsafe-to-eliminate. The latter is better suited for "unsafe variables" or data flow within an unsafe block like in the split-at-mut-via-duplication example.

65

This is an interesting point. Because it isn't really the manipulation of the capacity and len members that are the problem. The problem is that they have invariants that are trusted by unsafe code. Maybe the suggestion of unsafe structures or members should be considered as suggested by others. In the Vec case writing to len is effectively considered unsafe in the code as all writes go through the unsafe set_len() function.

But yes you are correct. Currently there are invariants that can't be expressed by the type system (or at least not currently) that can be relied on by unsafe code. Maybe this is a rabbit hole of other examples but in this case at least it seems reasonable to fix this problem.

I think I am trying to do this on purpose. I don't see the strength of a strong type system if it doesn't hold. So I want to restrict all of these to small sections of the code. Maybe this is unreasonable but to me it seems like it would be ideal to keep these the same.

In fact I think that 1 and 3 are intrinsically linked, because being able to rely on the type system is essential to many optimizations. So I suspect unless you want to get very fine grained with disabling specific optimizations in given scopes that these should remain the same.

For 2 I think that we should attempt to tie this to the same scopes for programmer effectiveness and maintaining high reliability. I see what you are trying to say that privacy was the tool previously used but I think it is worth changing this to be unsafety (and still offering privacy to be manipulated as desired).

1 Like
66

I'm not sure how you mean to do that. If unsafe code relies on values set by safe code, then the only way to prevent the unsafe code from going awry is restricting what can modify those values - and the only way to do that currently, which as a result is used everywhere, is privacy.

This could be done with unsafe values, but we can't narrow (2) when we introduce them: that would break existing code that had not yet been updated. Back-compat is not something we can cut here.

In addition, I am unconvinced that (3) can be narrower than (2) without opening a can of worms.

67

I think unsafe also restricts access because it requires access to be done in an unsafe block. It's a different sort of restriction because you can get by it just by saying "I promise to be careful" but it is still a restriction IMHO. In fact I think that this is a more relevant restriction then privacy as I see privacy as an orthogonal issue to bypassing the type system. And when you are doing things that mess with the type system declaring that you are aware of constraints beyond the type system (by typing unsafe).

This seems really elegant to me. Enhance the type system so that you can prevent access to structures that have additional invariants related to unsafe code, then when you type unsafe you acknowledge that the type system can't help you at this point and you promise that you are aware of the invariants whether language prescribed or application-specific.

You might be right about this as it is a really tricky subject. From what I understand this area is largely undefined currently. So if it becomes well-defined then future optimizations might change the behavior of existing code. I however think that this is somewhat inevitable because no matter how the restrictions to unsafe code get applied there will still be some, whether they are at module boundaries or someplace else.

I think you are right. It will be hard to perform many optimizations in an "unstable" state (where invariants are not guaranteed).

1 Like
68

I think this is already argued by others, like @kevincox, but I want to reply to clarify: I think that by introducing unsafe fields, the unsafe boundary can be restricted to be the size of the unsafe blocks, from perspective of the state the unsafe code relies on. (Migration is a problem, however, like pointed out by @eternaleye.) Then, from perspective of other type system violations, like aliasing &mut, I think that the unsafe boundary should be defined to be the unsafe blocks – that is, it should be considered UB to allow aliasing &mut to escape an unsafe block. (However, I think that it’s a sensible definition of aliasing to make only actual dereferences count.)

This has the downside that it’s easier to cause UB, which is something that is against the spirit of Niko’s post…

But this has also the benefit that it’s very easy to understand where the boundary is. Can’t have two aliasing &muts in safe Rust? Then don’t let them escape to safe code, plain and simple.

I think that it should be also possible to some extent prevent (although maybe not exhaustively) “silent” UB by inserting automatically debug_asserts before uses of values that have been “touched” inside the unsafe blocks. (I’m thinking testing for aliasing of self and copy of the split_at_mut example here.) Preventing silent UB is the point, right?

1 Like
69

Why can’t we disallow aliasing &mut everywhere, and ask developers to do their pointer arithmetic with *mut pointers? Isn’t that what they’re for?

1 Like
70

Perhaps posting this blog post just before a 3-day weekend (in the US, at least) wasn’t the best idea on my part. I spent most of the morning reading through this thread (and reddit too). I’m still pondering a lot of what I read and will try to write up a comprehensive thing later. I just wanted to clarify one point right now.

About the Ref example and re-ordering with respect to drop

There were some questions as to whether one ought to be able to re-order with respect to drop, and whether the Ref example that I gave could cause a problem in practice. The key point is that the compiler ought to be able to do the code motion I described without knowing what the drop function will do. I definitely want the compiler, in safe code at least, to feel free to reorder reads past function calls, relying on the fact that in Rust we have a pretty good idea what bits of memory a function might access (and what bits of memory are immutable, as well).

To put it another way, the following two functions ought to be “observationally equivalent” (that is, they will print the same value, guaranteed), and the compiler should be able to optimize on that basis:

fn foo0(x: &u32, y: &mut u32) {
    let v0 = *x;
    bar(y);
    println!("{:?}", v0);
}

fn foo1(x: &u32, y: &mut u32) {
    bar(y);
    let v1 = *x;
    println!("{:?}", v1);
}

So this pattern, if permitted, is very much a problem.

Abstraction boundaries vs barriers

I want to drill in a bit more on the previous point. This is sort of a random response to no-one, just clarifying something that may not be obvious.

The way I see it, an unsafe block is very different from something like an asm statement. Those tend to have unpredictable effects that cause the compiler to treat them as a barrier, where code motion around the block is not allowed. In contrast, code motion around unsafe blocks – or, at least, unsafe blocks contained in fns you call – is essential in Rust. This is what ensures that (e.g.) a call to vec.push() in safe code doesn’t serve as an optimization boundary.

71

It looks like most of what I want to say has already been articulated pretty clearly by @gereeter, so I just want to add a brief +1 to a couple of points.

  • I think that the current implementation of Ref is wrong: the struct is lying about the valid lifetime of the reference, and should be using a raw pointer (or a wrapper like Shared), instead. Trying to make this legal should be a non-goal.
  • Inhibition of optimization should only occur within an unsafe block or function, not in surrounding code. Any unsafe block should make sure that type-level invariants are restored before the end of the block.
73

I'm late to the party here, but there's an important point that I think is not getting enough attention:

What's proposed here is emphatically not "deoptimizing". It's a much, much smaller thing.

Rust's type system potentially gives us rich aliasing information -- much richer than is possible in a language like C. We can (and to some degree do) feed this aliasing info into the optimizer, and see some wins. These wins are above and beyond optimization that you get for C code.

What's at play here, AIUI, is just whether these extra, Rust-only optimizations are performed. At worst, your code is optimized as if it were C. The proposal just makes it possible to violate some of the usual typing assumptions -- for example, using an &mut and *mut pointer to the same data in unsafe code.

There is zero question in my mind that people writing unsafe code will violate these assumptions in practice. We've done so plenty of times within the standard library. Indeed, this is a big part of the reason Rust exists in the first place: people get these things wrong. But we have an opportunity here to do better than C, not only by limiting potentially-unsafe code to very small internals within abstraction boundaries, but to also avoid making that unsafe code a minefield of UB.

I also think it's worth spending some time fleshing out the proposal in more detail before getting too concerned about effects at the level of an entire file. In particular, there are two very vague ideas that could be made more clear and could have an impact here:

  • The idea of having an explicitly-marked abstraction boundary of some kind. In that case, unsafe code might by default use a very coarse-grained abstraction boundary, conservatively falling back to "merely" the C level of optimization. But if your abstraction boundary is more narrow, you could explicitly mark it as such, restoring optimizations that rely on Rust aliasing properties.

  • The idea of having aliasing opt-ins. That is, normally Rust types like &mut automatically provide aliasing assumptions. We can turn off those assumptions within the "gooey interior" of unsafe abstractions, but then provide you a way to opt back in to those assumptions in targeted cases where you can verify their correctness.

In all, this presents a scenario where unsafe code is optimized like C code by default, and has relatively easy to follow rules when it comes to Rust's types. And, where it's most critical, you're able to go above and beyond C optimizations through more explicit annotations.

2 Likes
74

Except that C has TBAA and Rust doesn't, which makes this statements wrong.
(It would be very nice to benchmark effects of TBAA and Rust aliasing guarantees on some non-trivial code, I haven't found such benchmarks with quick googling.)

Also, I haven't found any mentions of macros in this thread. Suppose an innocent user tries to use lazy_static! inside of a large module, he doesn't even use unsafe himself, but.. boom! all his code is suddenly deoptimized because lazy_static! contains unsafe code after expansion. And making aliasing rules depend on macro expansion by introducing some kind of "unsafety hygiene" would be even greater insanity.

75

I agree, ouch. I definitely do appreciate that there must be some boundary somewhere, and that code can ruin invariants in safe code when unsafe code depends on those fields. But I'll use some code I've written as an example.

httparse is a HTTP/1 parser. The rules the spec places on several fields, such as reason-phrase, header-name, and method, etc, are subsets of UTF-8. So, after parsing a header-name, and reaching b':', I have proved that all the bytes leading up to it are UTF-8. So I use unsafe to call str::from_utf8_unchecked, since I've already checked it.

In fact, throughout the main module, the only usage of unsafe is this case exactly. In order to make sure httparse receives all the optimizations it can from rustc, I would most likely create a new module, unchecked.rs. It'd contain 1 function, that houses the unsafe block. Then my code ends up looking like this:

// no unsafe
header.name = unchecked::from_utf8(bytes);

I can't decide if that is horrible, or what I'm "supposed" to do with this model.

1 Like
76

That sounds more like a reason to implement Undefined Behavior Sanitizer. Unsafe code is always going to have the possibility of invoking undefined behavior, so we need it anyways.

I wouldn't be opposed to a crate-level #![disable(strict_aliasing)].

77

My conclusion based on this thread is unsafe fields (and maybe ?) + crate-level #![unsafe_block_is_unsafe_boundary] for backwards comparability is all we need. Might be simplest to just do no optimizations within rustc without that annotation–that will incentivize people :).

78

I want to highlight this part of @aturon's comment and add some thoughts of my own:

Basically, C is an elegant and simple language -- until you learn about undefined behavior. Then you find out that most of the C code you have ever written is actually wrong in some way or another. I would like to see if we can find a scheme that ensures that unsafe Rust does not share this property. The "Tootsie Pop" scheme is aiming in that direction, but I don't think it's the only way to get there.

More generally, I'd like to see a "gradually escalating scale of danger":

  1. Safe code: guaranteed no memory faults or undefined behavior
  2. Simple unsafe code: easy to validate for correctness relying only on a working knowledge of the stack, heap, and how Rust types work
  3. Complex unsafe code: leverage annotations and types to get better optimization, but you have to understand more details to check it.

I worry a lot about the cliff between safe and unsafe code. Small amounts of unsafe code are common in practice -- if for no other reason than FFI code. Most of it doesn't have to be optimized "to the nines". It'd be great if we can find ways to minimize the risks of using unsafe code.

As an example, I would very much like it if, when doing simple unsafe code, one was able to think in isolation about individual pointers (and references) -- what does this pointer point at? If it's something on my stack frame, has it been popped? Was it declared as mut? If so, I know it is safe for me to access it. The Tootsie Pop model tries to deliver on this simple reasoning, but I don't think it's the only way to achieve it (and maybe not the best way!).

Of course there are cases where it is worth going "all out" for performance, and so I think we need some simple ways to opt in to that level of reasoning. But I'd be happier if it's not mandatory. Even some form of "strict types" declaration, for example, serves the purpose of giving people something to google for and encounter documentation.

1 Like
79

This is true, but not the whole truth. For one thing, a lot of C projects in practice disable TBAA =) -- and I've been told that many game engines do too, because it makes it too hard to write the sorts of low-level code they want to write (and hence ultimately costs them performance, since they'd have to be more conservative). But I'm not a game developer, so others might have to verify that statement.

In any case, I think ultimately there is a basic empirical question to be answered here. We don't use TBAA today. We do add some amount of LLVM annotations that would probably be removed by the Tootsie Pop model. It'd be nice to get some measurement of the impact of that, and -- if there is impact -- examine the causes.

80

Two things:

  1. I would love all my Rust code to be optimized to the same level as, say, GCC 6 or clang 3.9 optimize C code. Right now, I believe it is far from the case that "at worst, your code is optimized as if it were C," as C compiler front-ends do quite a few optimizations that LLVM doesn't do, and/or they seem to often do a better job of helping LLVM optimize the code, compared to rustc (in my experience).

  2. My understanding of the proposal was that if you don't have any unsafe code in a module, then it would be fully optimized with all those Rust-specific optimizations. But, if you then insert an unsafe block, all the Rust-specific optimizations are undone; i.e. This undoing of optimizations due to the addition of an unsafe block are what I (and others, I think) meant by "deoptimizing."

3 Likes
81

Generally speaking, TBAA is a big deal. Around 2010, LLVM didn’t have TBAA and as a result lost to GCC in benchmarks, sometimes as much as 20%. See this bug in LLVM bugzilla which is about initial implementation of TBAA: https://llvm.org/bugs/show_bug.cgi?id=2547.

Anecdotally, the most useful fact is that integer arrays and floating point arrays do not alias. So FP heavy codes tend to benefit. My impression is that FP heavy Rust code is rare at the moment.