Mutation - part 2: To mut or not to mut

Prelude

From the previous post:

A (runtime) variable is a (static) binding to some place in memory, and is used to read/write from/into that place in memory

Let’s illustrate it again with an example.

The following code

fn foo ()
{
    let x = 42;
    let y = i32::wrapping_add(x, 27) as u8;
}

unsugars to¹:

fn foo ()
{
    // allocate 4 bytes in the stack frame & bind at_x to its address
    let x: i32;  // type inferred
    // allocate 1 byte in the stack frame & bind at_y to its address
    let y:  u8;  // type inferred
    *at_x = 42;
    *at_y = i32::wrapping_add(*at_x, 27) as u8;
}

So, whenever there is a variable var, the actual binding is from at_var to some address in memory, and var is just sugar for *at_var².

To mut or not to mut

What does the keyword mut really mean?

1) mut bindings

When used with a variable binding, it expresses to the compiler the programmer’s intent of potentially mutating the data owned by that variable (i.e., mutating either the very contents of that variable, or the data recursively owned by that content (e.g., a Box)).

• For local variables, this is more of a lint, to warn against accidental mutations; local memory is always mutable! (since it is in the stack, which is writeable).

  • This means that transmuting an immutable reference to stack data into a mutable reference should never cause a memory violation (neither does it in C).

    Test, for instance, the following code:

    fn main ()
    {
        let x: i32 = 42; // immutable?
        let at_x_mut: &mut i32 = unsafe {
            &mut *(&x as *const i32 as *mut i32)
        };
        *at_x_mut += 27;
        assert!(x != 42);
        dbg!(x);
    }
    

    However, this is still Undefined Behavior³, so do not do this at home (nor at work)!

• But for global variables, a mut binding can make the compiler choose to place a static in the writeable part of the global memory (.data/.bss segment) instead of⁴ the readonly part (.rodata).

  • This means that transmuting an immutable reference to static data into a mutable reference can cause a memory violation.

    Test, for instance, the following code:

    fn main ()
    {
        static x: i32 = 42; // immutable!
        let at_x_mut: &mut i32 = unsafe {
            &mut *(&x as *const i32 as *mut i32)
        };
        *at_x_mut += 27; // Segmentation Fault
        unreachable!("Previous line segfaulted");
    }
    

  See Appendix 2 - readonly vs writeable statics.

As said before, the “compiler deny mutation lint” applies transitively to data pointed to in an owning manner, such as through a Box.

• For instance, rustc will refuse to compile the following code:

  30fn main ()
  31{
  32    // immutable?
  33    let at_thing = Box::<Thing>::default();
  34    print!("Before:\n  {:?}\nAfter:\n  ", *at_thing);
  35    mutate(&mut *at_thing); // cannot borrow as mutable
  36}
  37

• But by adding a couple of braces it compiles (without any unsafe whatsoever!):

  30fn main ()
  31{
  32    // immutable?
  33    let at_thing = Box::<Thing>::default();
  34    print!("Before:\n  {:?}\nAfter:\n  ", *at_thing);
  35    mutate(&mut *{at_thing}); // notice the braces
  36}
  37

  • displaying:

    Before:
      Thing at 0x559f5e50ea40 { mutated: false }
    After:
      Thing at 0x559f5e50ea40 { mutated: true }
    

You may then ask:

Why? How?

Mainly because:

the mut modifier applies to the binding itself, not the memory it binds to!

This is actually one of the main non obvious points that I wanted to talk about within this blog post series.

Let’s simplify the previous example into the following:

let ptr1 = Box::new(42_u8);
/****** Error, cannot borrow as mutable *******/
// *ptr1 += 27;        // mutation of the data in the heap
// ptr1 = Box::new(0); // mutation of the pointer itself

let mut ptr2 = ptr1;
*ptr2 += 27;        // mutation of the data in the heap
ptr2 = Box::new(0); // mutation of the pointer itself

1. At least one byte is heap-allocated and initialised with the value 42.

2. The pointer to the allocated byte is then stored in a local variable ptr1, immutably bound (no mut qualifier in the binding declaration);

3. This makes mutation through the ptr1 binding “impossible” (refused by the compiler), even through one level of indirection, because that indirection owns its data.

4. By moving the pointer into another⁵ local variable, we have the chance to declare a new binding, this time mut-able. The data in the heap has not moved.

5. Mutation is now possible, both to the pointee (value in the heap) and the pointer (value in the stack).

Now you can understand why the code with the braces compiled and worked:

• {var} is a very short way of writing down the following code:

  {
      let inner_var = var;  // var is moved *into* the scope
      inner_var
  } // the whole braced expr. evaluates to the moved value of `var`
  // but has no (explicit) binding: it is anonymously bound.
  

  i.e., {var} can be a trick to extract the value of var without the binding

  but if the mut-ability of a variable is defined when bound, quid of anonymous expressions?

• an anonymous binding is always mut!

  • This is what allows you to write, for instance, things such as:

     1use ::std::process::Command;
     2
     3fn run (
     4    command: &mut Command,
     5) -> String
     6{
     7    String::from_utf8(
     8        command
     9            .output()
    10            .expect("Failed to execute process")
    11            .stdout
    12    ).expect("Invalid UTF8 output")
    13}
    14
    15
    16fn main ()
    17{
    18    print!("{}", run(
    19        Command::new("sh")  // anonymous `Command`
    20            .arg("-c")      // takes a `&mut Command`
    21            .arg("echo Hello, World!")
    22    ));
    23}
    24

    If you look at the main function, lines 19 and 20, you will notice that the anonymously bound Command::new("sh") is fed to the .arg() method, which takes a &mut Command. This means Rust does allow taking a &mut reference of an anonymously bound expression.

2) &mut _ references

There is a very short definition for this:

A &mut T reference is a valid pointer to a T that is statically guaranteed to be unique.

That’s it. No more… no less! &mut _ is all about the uniqueness of the pointer! In other words, it is guaranteed by design that during the existence of a &mut reference p, the only way to access *p (the data pointed to) is through p. I will often call such reference &unique instead of &mut to emphasize this point.

But isn’t &mut _ a mutable reference?

No. &mut _ is a unique (and valid) reference! It just so happens that uniqueness is such a strong guarantee, that Rust allows mutation through such a reference “for free”.

To see how this is granted, look at the following safe function, one of the core features of the language:

// core::mem {
    /// Swaps the values at two uniquely referenced locations,
    /// without deinitializing either one.
    pub fn swap <T> (p1: &unique T, p2: &unique T);
        // note: Rust `&mut _` semantics guarantee that `p1 != p2`
// }

This means that whenever a type T is inhabited with at least⁶ 2 different values, it is then possible to use a &unique reference to mutate a value of type T and observe the difference.

Hence the mut in &mut _.

But &unique is not the only “mutable” reference in Rust. There are infinitely more. For instance, the relation “unique-reference-to” is transitive⁷, thus making a unique reference to a unique reference to some x effectively a unique reference to that x:

fn swap<T> (at_p1: &mut &mut T, at_p2: &mut &mut T)
{
    core::mem::swap(&mut *(*at_p1), &mut *(*at_p2))
}

Which means that &unique &unique T is also a mutable “reference” to some T.

On the other hand, it is easy to break the uniqueness of a nested reference; when the inner reference is not unique (e.g. & _ reference, or Rc<_>), then a unique reference to such (potentially) non-unique reference is (potentially) non-unique:

fn swap<T> (at_p1: &mut &T, at_p2: &mut &T)
{
    // although at_p1 != at_p2, it is possible that *at_p1 == *at_p2
    core::mem::swap(&mut *(*at_p1), &mut *(*at_p2))
}

So far we have seen that any kind of unique reference is a mutable reference, i.e., a reference that allows mutation through it.

Is it the sole⁸ form of mutable reference?

If that were the case, there would be programming idioms that would not be expressable in Rust, such as any form of multi-threaded mutation; which would be a pity since by paying a runtime cost (e.g., locks) it is a safe and acceptable programming construct.

Well, that’s what unsafe is for, isn’t it? To use constructs the compiler cannot prove to be safe, and force it to trust the code within the unsafe block. Then I could simply transmute an immutable reference into a mutable one, which should be safe as long as the code is guarded by sound runtime checks, right?

Let me show a picture of yourself and your program after such unsafe transmute:

What? But I told you I have this awesome safety checks and super sound invariants that cannot be broken!!

It. Doesn’t. Even. Matter. Hell, even the following transmute⁹ is UB:

#![allow(
    mutable_transmutes, // let MIRI spot the Undefined Behavior
    non_snake_case,
)]

fn swap_UB<T> (at_x: &mut T, at_y: &mut T)
{
    // for fun, let us temporarily downgrade our `&mut T` into a `&T`
    let at_x: &T = & *at_x;
    // now, let's upgrade it back:
    let at_x: &mut T = unsafe {
        core::mem::transmute::<&T, &mut T>(at_x)
    };
    core::mem::swap(at_x, at_y);
}

fn main () { swap_UB(&mut 42, &mut 0) }

Why transmuting & to &mut is UB

Because for any type T:

1. The only¹⁰ way to mutate a T is through a unique handle on that value; i.e., a straight-owned T, a &unique T, a &unique &unique T, etc.

2. This implies that it is not possible mutate a T through a &shared T reference.

3. Actually, the very existence of a &shared T reference prevents the existence of any other &unique T or straight-owned T handle that would allow us to mutate that data!!

4. In other words, whenever a &shared _ exists, the pointee is guaranteed to be immutable for the lifetime of the reference.

5. This is a very interesting invariant that the compiler can use and (does use!) to aggressively optimize your code.

6. So if the data turned out not to be immutable, these assumptions would be invalidated making the optimized code wrong. Such contract violation is the very definition of Undefined Behavior.

TL,DR

Once a reference reaches the “potentially shared” state (&_), Rust asserts that the pointee is immutable (during the lifetime of the reference).

• Now we can see why the previous code:

   1//! Run with MIRI to spot the Undefined Behavior
   2
   3#[allow(non_snake_case)]
   4fn swap_UB<T> (at_x: &mut T, at_y: &mut T)
   5{
   6    // let us temporarily downgrade our `&mut T` into a `&T`
   7    let at_x: &T = & *at_x;
   8    // now, let's upgrade it back:
   9    let at_x: &mut T = unsafe {
  10        &mut *(at_x as *const T as *mut T)
  11    };
  12    core::mem::swap(at_x, at_y);
  13}
  14
  15fn main () { swap_UB(&mut 42, &mut 0) }
  16

  is Undefined Behavior; at line 7 we have created a &shared T reference to the data pointed to by at_x, thus asserting to the compiler that that data is immutable for the duration of the function (the scope of the reference). And yet at line 12 that data is mutated.

Hmmm, isn’t there then a way to exceptionally turn down that invariant? To tell it that some data can never be truly immutable since it’s kind of … volatile maybe?

Ok, let’s imagine that it can be done.

Hypothetical Volatile

How should that “volatility property” be expressed?

Definitely not with a let volatile lang construct, since that would be a binding-dependant modifier instead of a memory-dependant one (c.f. all that was said about mut bindings).

But it could be a struct (field) attribute:

struct Foo {
    #[volatile]
    bar: Box<i32>,

    baz: i32,
}

But then what would be volatile? The pointer, the pointee, both ? The semantics are not clear.

The best way to express semantics is through an API, clarifying what can be done and what cannot. Thus, let’s use a new type pattern to encapsulate the dangerous #[volatile] attribute:

struct Volatile<T> {
    #[volatile] // Attribute directly used here only!
    volatile_data: T,
}

The semantics will be the following:

The transitivity of the immutability property deduced from a &shared _ reference stops at a Volatile<_> wrapper boundary.

This means that if we have:

• struct Person {
      name: String,
      age: Volatile< Box<i32> >,
  }
  
  let john = Person {
      name: "Duh",
      age: Volatile { volatile_data: Box::new(42) },
  }
  

• and a reference at_john of type &shared Person

{
    let at_john: &Person = &john;
    // is `john` immutable ?
}

then within the lifetime of the at_john reference,

• john.name is immutable because referred by a potentially shared &shared reference;

• but john.age.volatile_data is not, because it’s inside a Volatile wrapper (who knows, maybe john’s birthday happens right within that scope and his age increments).

• Note that all the data wrapped in a Volatile is considered non-immutable. So this includes both the actual age value and the pointer to the age value;

  • However, john.age itself (the wrapper) is considered immutable, since the wrapper boundary has not been crossed!

This sounds exactly like what we’d want for, for instance, concurrency (imagine another thread is busy checking whether his birthday happens to then increment his age).

This is all nice and pretty, but what would the actual aforementioned API be? Having something “volatile” but not being actually able to mutate it sounds dumb.

impl<T> Volatile<T> {

So let’s thing about what we’d want for impl<T> Volatile<T>:

1. to be able to mutate its data through a &unique _ reference obviously;

   • fn get_mut (self: &mut Volatile<T>) -> &mut T

2. but above all, we want to be able to mutate its data through a &shared _ reference:

   • fn get (self: &Volatile<T>) -> &mut T?

     Well, hopefully the previous line looks wrong to you too; remember that a &mut T means &unique T, i.e., a valid and unique reference to the pointee. Such output cannot¹¹ be guaranteed from a &shared input!

     1let at_john_1 = &john; // shared, so valid
     2let at_john_2 = &john; // shared, so valid
     3let at_age_1_mut: &mut _ =
     4    Volatile::get(&at_john_1.age);
     5// The following line is UB
     6let at_age_2_mut: &mut _ =
     7    Volatile::get(&at_john_2.age);
     8core::mem::swap(at_age_1_mut, at_age_2_mut);
     9

   • Okay, the guarantees/semantics of a &unique T are too strong to express the return value of our function. We want to return a raw handle to mutable data, without guaranteeing that the handle/reference is unique.

     Somebody said raw handle to mutable data?

     asks *mut T as it slams (⌐■_■) the door open;

     (you may realize that *mut T is actually the closest thing to a “mutable reference”¹² in other languages. Note the difference with a &mut T)

   • So, the method’s prototype should be the following:

     fn get (self: &Volatile<T>) -> *mut T

Let’s try to implement it:

impl<T> Volatile<T> {
    fn get (self: &Self) -> *mut T
    {
        (&self.volatile_data) as *const T as *mut T
    }
}

Yes, we did it!!

Did we?

Oh, what now!!?

Nothing, just some…

What!? How??

&self.volatile_data.

After all this trouble, we just went and created (even if only for an instant) a &shared _ to the volatile_data, thus asserting its immutability.

Ok, what about the following:

impl<T> Volatile<T> {
    fn get (self: &Self) -> *mut T
    {
        (&mut self.volatile_data) as *mut T
    }
}

This does not even compile! cannot borrow as mutable, as it is behind a '&' reference

Ok, fixed:

fn get (self: &Self) -> *mut T
{ unsafe {
    &mut (self as *const Self as *mut Self).volatile_data
}}

unsafe is not the way to go to avoid UB:

• you transmuted a &Self to a *mut Self which is UB if you dereference it, and which you just did when accessing volatile_data;

• and then you got a &mut volatile_data, even if only for an instant, which was the problem of the very first get.

Right, right, I should have known better than to use unsafe.

Okay, this is my last idea:

impl<T> Volatile<T> {
    fn get (self: &Self) -> *mut T
    {
        self as *const Self as *const T as *mut T
    }
}

let me guess, UB again?

Well, yes and no:

1. it’s UB, because you are assuming that a pointer to a Volatile<T> can be casted as / transmuted to a pointer to a T,

   Ha! I knew it!

2. It’s nevertheless the right way, since it dodged all the mutability-related UB

   Oh, I was right then?

Pretty much, yes. We just get rid of 1., by adding the #[repr(transparent)] attribute to the Volatile wrapper:

#[repr(transparent)]
struct Volatile <T> {
    #[volatile]
    volatile_data: T,
}

#[repr(transparent)] guarantees that the wrapper and the wrappee(?) have exactly the same memory layout, thus making the pointer conversion not UB. Hooray!!

So, now we have some kind of wrapper, package, box, cell (you name it) that yields, through (potentially) shared references, *mut T pointers, which are unsafe to “promote to uniqueness” (&mut T)

Wait a mome…

• Plot twist!!

  Volatile was UnsafeCell all along!!!

  • Instead of our imagined #[volatile] field attribute, Rust’s core uses #[lang = "unsafe_cell"] struct attribute (and they also get rid of the implicit Sized bound with : ?Sized, so as to be able to wrap DSTs with it):

    1435#[lang = "unsafe_cell"]
    1436#[stable(feature = "rust1", since = "1.0.0")]
    1437#[repr(transparent)]
    1438pub struct UnsafeCell<T: ?Sized> {
    1439    value: T,
    1440}
    1441

Perfect, now we can talk about Interior Mutability, on the

Appendix

1 - Annotated MIR

 1fn foo ()
 2{
 3/////// LOCALS METADATA (e.g. sizes) ///////
 4//      _0: ()      // return value
 5//      _1: i32     // `x`
 6//      _2: u8      // `y`
 7//      _3: i32     // `x + 27` (before `as u8`)
 8//      _4: i32     // copy of `x` (function arg)
 9
10/////// let x = 42; ///////
11    // let x: i32;
12    StorageLive!(_1);
13
14    // x = 42;
15    _1 = 42i32;
16
17/////// let y = i32::wrapping_add(x, 27); ///////
18    // let y: u8;
19    StorageLive!(_2);
20
21    // COMPUTE i32::wrapping_add(x, 27)
22        // let _3: i32;  // (will store the result of wrapping_add)
23        StorageLive!(_3);
24
25        // let _4: i32 = x; // (first argument of wrapping add)
26        StorageLive!(_4);
27        _4 = _1;  // read value stored at _1, and write it into _4
28
29        // call i32::wrapping_add
30        _3 = i32::wrapping_add(move _4, 27i32)
31
32        // FREE ARGS
33        StorageDead!(_4);
34
35    // y = COMPUTE_RESULT as u8;
36    _2 = _3 as u8;  // read 1 byte stored at _3, and write it into _2
37
38/////// DROP DROP DROP ///////
39    StorageDead!(_3);
40    StorageDead!(_2);
41    StorageDead!(_1);
42
43/////// END => RETURN ///////
44    return;
45}
46

2 -readonly vs writeable statics

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

use ::std::sync::atomic::AtomicIsize;

/// neither `mut` nor interior mutability => .rodata (R)
#[no_mangle] pub
static      W: isize = 42;

/// `mut` => .data (D)
#[no_mangle] pub
static mut  X: isize = 421

/// interior mutability => .data (D)
#[no_mangle] pub
static      Y: AtomicIsize = AtomicIsize::new(42);

/// mutable & 0-init => .bss (B)
#[no_mangle] pub
static mut Zero: isize = 0;

Proof

3 - Transmuting int const * to int * in C: