Why not borrow check raw pointers’ pointee places?

language design Unsafe Code Guidelines
1

Consider the following function (derived from this URLO question) (playground):

unsafe fn use_a_raw_pointer(ptr: *mut i32) {
    unsafe {
        let ref1 = &mut *ptr;
        let ref2 = &mut *ptr;
        dbg!(*ref1); // miri error: Undefined Behavior: attempting a read access using <1566> at alloc767[0x0], but that tag does not exist in the borrow stack for this location
    }
}

This program is unsound, because ref2 is created between the time ref1 is created and ref1 is used, therefore ref1 is invalid to use. It seems to me that this problem could be detected at compile time, using the following rules:

  1. Borrows of the place *ptr shall be tracked by the borrow checker, in the exact same way that it would track a variable in safe code:

    fn currently_disallowed(mut value: i32) {
    let ref1 = &mut value;
    let ref2 = &mut value;
    dbg!(*ref1); // rustc error[E0499]: cannot borrow `value` as mutable more than once at a time
}

  2. If and when ptr is mutated, then occurrences of *ptr afterward count as accessing a new, separately tracked place. Borrows from the previous value of *ptr are not invalidated.

It seems to me that this would reject some unsound code while still accepting all currently-accepted sound code, so it would help catch bugs without interfering with any valid uses of unsafe code. Am I missing a case where rejecting this type of usage would be a false positive? Could we compatibly (or across an edition) add this check to the compiler?

7 Likes
2

At a minimum, a deny-by-default lint seems like it should be doable. That leaves an escape hatch for people that really want UB for whatever reason, or if they find an edge case where it isn't.

3

That's not necessarily simple, because it would mean giving the borrow checker an additional mode that tracks whether the borrow conflict it's reporting came from a raw pointee place or not. What I'm proposing here is not a separately implemented lint for raw pointers, but giving the borrow checker more things to check.

What I'd particularly like to hear is whether there are in fact any cases where this check would reject a sound program.

1 Like
4

With unions, the borrow checker prevents you from borrowing parts of different fields, but doing the same with a raw pointer should be sound as long as the actual borrows are disjoint:

#[repr(C)]
union Foo { a: (u32, u32), b: (u32, u32) }

let ptr: *mut Foo = ...
unsafe {
    let ref1 = &mut ptr.a.0;
    // error[E0499]: cannot borrow `*ptr` (via `ptr.b.1`) as mutable more than once at a time
    let ref2 = &mut ptr.b.1;
    dbg!(*ref1);
}

The equivalent code with a raw pointer passes Miri:

let ptr: *mut Foo = ptr;
unsafe {
    let ref1 = &mut (*ptr).a.0;
    let ref2 = &mut (*ptr).b.1;
    dbg!(*ref1);
}

playground

4 Likes
5

AFAICT only with stacked borrows, not with tree borrows. So do we really want to reject it?

3 Likes
6

Perhaps my example was too simple, then. If ref1 and ref2 are actually used — in particular, if they are both written and read after they are created — then the code would definitely violate &mut exclusiveness. Here’s a definitely-UB example:

struct Foo<'a> {
    r: &'a mut i32,
}
impl<'a> Foo<'a> {
    pub fn new(r: &'a mut i32) -> Self {
        *r += 1;
        Self { r }
    }
}
impl<'a> Drop for Foo<'a> {
    fn drop(&mut self) {
        *self.r -= 1;
    }
}

unsafe fn use_a_raw_pointer(ptr: *mut i32) {
    unsafe {
        let ref1 = Foo::new(&mut *ptr);
        let ref2 = Foo::new(&mut *ptr);
    }
}

The target of the reference ref1 owns is mutated, and not by ref1.

I take your point, though, that we would not want to reject the simple case, if TB allows it and UCG/opsem decides on TB or something else that allows that.

1 Like
7

Thanks for the clarification. Yes, I think we shouldn't reject sound programs in unsafe code, since that's the escape hatch.

However in that particular case, we could probably argue that the program can be rewritten with only raw pointers, producing a mutable reference only when needed. In that sense, additional borrow checking rules, even if conservative (rejecting sound code), could be added, since it doesn't reduce the expressivity of the language (a different but similar program would type check).

Am I understanding correctly your argument?

8

No, I was hoping that we’d hook this into the borrow checker and nobody would have to rewrite any unsafe code that isn’t unsound. @quaternic and you have given examples where this wouldn’t be true, or might not be true, respectively.

My point with the second example with Foo<'a> was only to demonstrate a case which definitely does have UB, by contrast with the original one which creates an aliasing &mut but doesn’t actually use it.

9

What if the mutation writes the same (runtime-determined, so you don't know it at compile time) value to ptr? Or there is an intermediate sequence of mutations which end up returning ptr to the same value? What if instead of two borrows of ptr, we have ptr1 and ptr2, and they just happen to point to the same place?

You suggestion doesn't make sense as a compile error, since it can't be really checked in any complete way. Sounds more like a very situational Clippy lint, and even then it's debatable (e.g. there is nothing definitely forbidding this pattern, Tree Borrows allow it, and the model may change yet again in the future).

10

The goal of this would be to catch unsoundness that can be caught, not to be complete. The compiler already does this kind of thing.

11

If it doesn't have simple, strong rules, I strongly believe it needs to be a lint and not hard error.

12

Well, we don't agree whether it is necessarily unsound in the first place. Even then, having this kind of vague rule built into the compiler would imho do more harm than good. It would confuse the users about the rules which must be followed. Nowadays the boundary is clear: with safe code (or at least references and variables) the rules are checked by the compiler, and when dealing with pointers you're on your own. Having ad-hoc rules for specific cases makes this into a very fuzzy boundary. There are no errors, does that mean the code is okay? How much can I rely on what the compiler complains about?

Not to mention that turning this into a compilation error would be a breaking change, and wouldn't be fixing actual unsoundness in the compiler. It may be UB in user code, yes. But UB is a runtime property. What if the relevant code path isn't actually ever executed? This means it can't be anything but a lint.

Is it a common error? How hard would it be to fix?

13

I take your point that, since this is a “might catch a problem” diagnostic, it should be a lint and not a hard error (like e.g. deref_nullptr). This means that implementing it would require the borrow checker to track which information it got from these pointer accesses, so that it can refrain from producing hard errors. I imagine that would make it much more difficult.

As to the rest of your questions, please note that I posted this question to gather input on how feasible this idea might be and what I haven’t thought of. I am not, currently, making a complete RFC, Pre-RFC, compiler MCP, or any other form of change proposal.

1 Like
14

I don't see why it should be infeasible to implement as a Clippy lint. I don't think the borrow checker should bother with such low-quality checks at all, and since we don't expect the check to be 100% correct (it can't be, due to runtime conditions), we could restrict it to a warning based on mostly-syntactic considerations.

  • If we have a pointer variable ptr...
  • And a mutable borrow of its pointee let b = &mut *ptr;, which is stored in a variable...
  • Check that the control-flow graph doesn't contain any other borrows of the pointee until the last use of b.

This sounds easily checkable. It is debatable how common this kind of error is, outside of trivial examples (where it is easy to catch with Miri anyway). We can't really do any more complex borrow checking, since that may depend on runtime conditions. Maybe we could extend it to applying f(b) and using its result after a second borrow of *ptr, but it will have false positives, so I'm not sure it's justified.

15

That's still a mutation, from the perspective of the aliasing model, so it has no bearing on this discussion. More specifically, the aliasing model is only considered with "read accesses" and "write accesses", not with the actual data being read/written.

16

Is this not what the borrow checker does? It seems to me that duplicating the logic in Clippy would lead to inconsistencies and increased maintenance costs. I hoped that this check would be implementable in a way which is consistent with the rest of the language by using existing borrow checking, rather than being a more ad-hoc system. In particular, my experience with seeing people react to lints is that users are quick to hypothesize “I changed the code and the lint went away, so the new code must be good”. That is, of course, an argument against doing raw pointer borrow checking at all too, but in particular a novel lint algorithm would be worse than integrating with the borrow checker, because it would be less robust — it would be likely to have more false positives and more false negatives.

I think @afetisov meant writing to the place ptr, not *ptr. This is in reference to the rule I stated in the original post:

  1. If and when ptr is mutated, then occurrences of *ptr afterward count as accessing a new, separately tracked place. Borrows from the previous value of *ptr are not invalidated.

This is how this check would avoid falsely rejecting code like the following:

while todo!("some condition") {
    vec_of_borrows.push(&mut *ptr); // or something else that requires a borrow outliving the loop
    ptr = ptr.add(1);
}

Because ptr was reassigned, the check must, to avoid rejecting this correct code, consider *ptr to be a new place in each iteration of the loop, so that it doesn’t incorrectly see a borrow conflict. But because we’re not attempting to check the correctness of pointer arithmetic, this means the lint can be falsely suppressed just by writing ptr = ptr; or something obfuscatedly equivalent to that, which is the fundamental “““soundness hole””” in it.

2 Likes
17

Kind of, but it's much more complex than this simple rule.

I'll preface with a caveat that I haven't studied the specific implementation, and speak from a general understanding, which can be wrong. That said, the borrow checker is part of the type system. This means the algorithms and implementations are likely intertwined, making it hard and dangerous to "just add a small exception". Given the unreliability of the proposed analysis, I don't think using it for anything semantics-relevant in the compiler is a good idea. But given the integration of borrow checker, it may be difficult to keep these "educated guesses" from actual facts in the compiler.

It's also debatable whether it's prudent to waste extra compilation time on an unreliable check, which shouldn't even apply in safe code (which is most code).

The borrow checker must find an actual set of regions in code which satisfy all defined lifetime constraints. This is obviously more complex than a simple "is this place reborrowed" check. Regions may be shrunk or expanded depending on provided constraints. It also propagates through function calls via relations of input and output lifetimes, and I propose to do no such thing. API lifetime constraints are often more conservative than possible, either for reasons of ergonomics or specifiability (i.e. more complex constraints may not be soundly definable in the type system). Unsafe code is often used specifically to side-step the limitations imposed by the borrow checker. It would make no sense to add a lint which prohibits this kind of formally wrong (as defined in the API), but operationally correct code.

18

I am not proposing to add any exceptions to the borrow checker. Rather: the borrow checker checks relationships between places, borrows (carried through types), and dereferences of borrows. What I was initially proposing is that certain places (raw pointer pointees) which the borrow checker currently ignores would now be considered; that is, the borrow checker gets more input for it to check than it previously did, but its algorithm is unchanged.

Given the premise that this should be a lint and not a hard error, that might be implemented by running the borrow checker a second time, to check the relationships between references already checked and raw pointee places not already checked, so that any failures resulting from that information can be isolated into the lint rather than ordinary borrow checking errors — but the algorithm itself would not be altered, and ideally it would be able to reuse all already-computed types and lifetime relationships. This might be infeasible, but whether it is feasible is a matter of the compiler architecture, not the language design.

It should do nothing in safe code, because it only applies to raw pointer dereferences, which cannot appear in safe code.

Yes, I agree with this statement. The purpose of this lint would be to reject code which is unsound. If, in fact, it would reject code that is sound — perhaps because the opsem/UCG/spec is nailed down to say that merely taking two aliasing &mut (which the borrow checker rejects) is not UB in itself — then it should not be added in the form I proposed in the original post.

1 Like
19

That's an interesting suggestion. Perhaps it would be feasible. At least I'm reasonably sure that it wouldn't affect the type system, even though I'm not so sure about the burden on the compiler, or the compile-time cost of doing a second borrow checker pass.

It would be interesting to do a search of crates.io, to determine whether this kind of error is actually common in the wild. But I don't know how to do it, without either Crater or a full local mirror, which I can do neither of,