The borrow checker did what?!

Sep 18, 2022 · 1005 words · 5 minute read

Rust’s borrow checker is often maligned as frustrating and pedantic. An impediment to getting things done. A bureaucrat in the compiler, who demands the following of arcane rules. I don’t agree with this take. There are many valid criticisms of Rust on the internet, but this isn’t one. A serious rebuttal would require far more than a blog post. My intention is to draw attention to valuable and interesting consequences of Rust’s memory model.

The borrow checker is Rust’s most distinguishing feature. It imposes ownership semantics at compile time, which reduces the bug surface of Rust programs substantially. Its security value is well-understood. Memory corruption bugs are a wellspring of vulnerabilities in C/C++ programs. They’re usually not very interesting, although this belies the amount of effort involved to find them in the first place.

On the contrary, optimizations that would be impossible without the borrow checker are very interesting to me.

I really only want to say two things in this post:

Rust’s draconian ownership semantics are not only useful for security, but also for performance.
More research is needed into the optimizations enabled by the borrow checker.

I discovered a neat example of an optimization automatically made by Rust and enabled by the borrow checker.

First, some perspective. 🔗

Before diving into the Rust, let’s take a look at some C.

Consider this toy example:

#include <stdio.h>

struct Thing {
  int val;
};

int abc(struct Thing *a, struct Thing *b) {
  a->val = 99;
  b->val = 100;
  return a->val + 1;
}

int xyz(struct Thing *restrict a, struct Thing *restrict b) {
  a->val = 99;
  b->val = 100;
  return a->val + 1;
}

int main() {
  struct Thing me = {1};
  int res = xyz(&me, &me);
  printf("%d\n", res);
  return res;
}

which when compiled by Clang 15.0 on x86 at -O3 yields

abc: # @abc
  mov dword ptr [rdi], 99
  mov dword ptr [rsi], 100
  mov eax, dword ptr [rdi]
  inc eax
  ret
xyz: # @xyz
  mov dword ptr [rdi], 99
  mov dword ptr [rsi], 100
  mov eax, 100
  ret

In this example, the two functions are identical, except in the second one. I used the restrict keyword to hint to the compiler that a and b can never alias. The compiler rightly elides the load and the increment, because it knows that a and b won’t occupy the same address.

Unless of course, I lie to the compiler, accidentally or otherwise. This is exactly what main does. It passes the same pointer to both arguments in xyz, lying on purpose.

Surely passing aliased pointers to a function compiled to expect non-aliased pointers is undefined behaviour? I don’t actually know.

Let’s see what happens! Will the compiler trust us?

$ gcc prog.c
$ ./a.out
101
$ gcc -O3 prog.c
$ ./a.out
100

Oh no! The compiler trusted us!

GCC 12.2.1 knows we’re up to no good:

$ gcc -Wall prog.c
prog.c: In function ‘main’:
prog.c:21:17: warning: passing argument 1 to ‘restrict’-qualified parameter aliases with argument 2 [-Wrestrict]
   21 |   int res = xyz(&me, &me);
      |

Clang 14.0.5 doesn’t seem to care:

$ clang -Wall prog.c
$ ./a.out
101
$ clang -Wall prog.c -O3
$ ./a.out
100

I don’t understand undefined behaviour very well, so I’m going to ask for help from UBSan:

$ gcc prog.c -fsanitize=undefined -Wall
prog.c: In function ‘main’:
prog.c:21:17: warning: passing argument 1 to ‘restrict’-qualified parameter aliases with argument 2 [-Wrestrict]
   21 |   int res = xyz(&me, &me);
      |                 ^~~  ~~~
$ ./a.out
101
$ gcc prog.c -fsanitize=undefined -Wall -O3
prog.c: In function ‘main’:
prog.c:21:17: warning: passing argument 1 to ‘restrict’-qualified parameter aliases with argument 2 [-Wrestrict]
   21 |   int res = xyz(&me, &me);
      |                 ^~~  ~~~
$ ./a.out
100
$ clang prog.c -fsanitize=undefined -Wall
$ ./a.out
101
$ clang prog.c -fsanitize=undefined -Wall -O3
$ ./a.out
101

Well, now it makes even less sense! There are only two possibilities:

There is a bug in the versions of GCC/Clang that I used.
There is no bug, because the compilers are allowed to produce inconsistent results such as these.

I’m inclined to think this is a compiler problem, but I don’t know for sure.

Regardless, this only happens because C trusts the programmer to manage ownership of resources.

Can I have this optimization for free? 🔗

Yes, you can have this optimization for free, in Rust that is.

Consider the equivalent code in Rust:

pub struct Thing {
    val: i32
}

pub fn abc(a: &mut Thing, b: &mut Thing) -> i32 {
    a.val = 99;
    b.val = 100;
    return a.val + 1;
}

when compiled at opt-level=3 produces:

example::abc:
  mov dword ptr [rdi], 99
  mov dword ptr [rsi], 100
  mov eax, 100
  ret

because the ownership semantics of the language demand that a and b never alias!

I can’t lie to the compiler, even if I wanted to.

This code:

pub fn test() {
    let mut a = Thing {val: 1};
    abc(&mut a, &mut a);
}

results in this error:

error[E0499]: cannot borrow `a` as mutable more than once at a time
  --> <source>:13:17
   |
13 |     abc(&mut a, &mut a);
   |     --- ------  ^^^^^^ second mutable borrow occurs here
   |     |   |
   |     |   first mutable borrow occurs here
   |     first borrow later used by call

error: aborting due to previous error

because it’s not valid Rust. This machine code level optimization happens because the Rust compiler has a rich understanding of alias information.

So what? 🔗

This result extends the reach of the Rust programmer who is oblivious to this optimization because:

It happens automatically.
It is deterministic.
The compiler doesn’t even compile code that would render the optimization incorrect.

The borrow checker is utterly spectacular.

The borrow checker did what?!

First, some perspective. 🔗

Can I have this optimization for free? 🔗

So what? 🔗

See also 🔗