Aliasing, Capabilities, and Ownership in Rust

What is Rust?

New programming language

• (... and ecosystem, and development community)

Emphasizing control, safety, and speed

• (... especially when it comes to concurrency)

Low-level hacking without fear of segfaults nor data races

• or more simply: "Hack without Fear"

Why ...?

Algebraic Data Types

enum BinaryTree { Leaf(i32), Node(Box<BinaryTree>, i32, Box<BinaryTree>) }
fn sample_tree() -> BinaryTree {
    let l1 = Box::new(BinaryTree::Leaf(1));
    let l3 = Box::new(BinaryTree::Leaf(3));
    let n2 = Box::new(BinaryTree::Node(l1, 2, l3));
    let l5 = Box::new(BinaryTree::Leaf(5));
    BinaryTree::Node(n2, 4, l5) }

Ownership

enum BinaryTree { Leaf(i32), Node(Box<BinaryTree>, i32, Box<BinaryTree>) }

• match moves input to Leaf(n) or Node(l, n, r) as appropriate
• *expr dereferences; here, moves tree out of box to local stack slot
• fn signature: pass-by-value + move semantics = args consumed

fn tree_weight(t: BinaryTree) -> i32 {
    match t {
        BinaryTree::Leaf(payload) => payload,
        BinaryTree::Node(left, payload, right) => {
            tree_weight(*left) + payload + tree_weight(*right)
        }
    }
}

Arguments Consumed

fn tree_weight(t: BinaryTree) -> i32 { ... }

fn consume_semantics() {
    let t = sample_tree();
    let w1 = tree_weight(t);
    let w2 = tree_weight(t);
    println!("w1: {} w2: {}", w1, w2);
}

error[E0382]: use of moved value: `t`
  --> src/a00.rs:67:17
   |
66 |     tree_weight(t);
   |                 - value moved here
67 |     tree_weight(t);
   |                 ^ value used here after move
   |
   = note: move occurs because `t` has type `BinaryTree`,
           which does not implement the `Copy` trait

Sending resources (std::thread)

let (tx, rx) = channel(); // create transmitter/receiver pair
thread::spawn(move || match rx.recv() { // spawn A1, taking ownership of `rx`
                          Ok(v_end) => {
                              println!("A1 received {:?}", v_end)
                          } // (end of scope for `v_end`; automatic clean up.)
                          Err(err) => println!("A1 receive failure {:?}", err),
                   });
let t1 = tx.clone();
thread::spawn(move || { // spawn A2, taking ownership of `t1`
                       let mut v = Vec::new(); v.push('a'); v.push('b'); v.push('c');
                       t1.send(v).expect("A2 send failure");
                   });
thread::spawn(move || { // spawn A3, taking ownership of `tx`
                       let v = vec!['1', '2', '3'];
                       tx.send(v).expect("A3 send failure");
                   });

• Syntax: |arg, ...| expr (incl. || { expr; ... }) are closures
• move |arg, ...| expr captures by ownership xfer ("moving")
• println! and vec! are macros (typesafe printf; Vec building sugar)
• Destruction 1: at scope end for v_end, buffer + contents reclaimed
• Destruction 2: at scope end for rx, t1 + tx, channel reclaimed

Sending between threads

• rx, t1, tx, and each v are all moved from one thread to another
• t1 cloned from tx; (if tx moved to middle subthread, would not be available for left one)

Not everything can be sent

fn demo_sendable() {
    let (tx, rx) = channel();
    let r1 = Rc::new(vec!['a', 'b', 'c', '1', '2', '3']);
    tx.send(r1.clone()).unwrap();
    let _r2 = rx.recv().unwrap();
    println!("r1: {:?}", r1);
}

Not everything can be sent (really)

fn demo_unsendable() {
    let (tx, rx) = channel();
    let r1 = Rc::new(vec!['a', 'b', 'c', '1', '2', '3']);
    thread::spawn(move || { let r2 = rx.recv().unwrap();
                            println!("received: {:?}", r2); });
    tx.send(r1.clone()).unwrap();
    println!("r1: {:?}", r1);
}

error[E0277]: the trait bound `Rc<Vec<char>>: Send` is not satisfied
   --> src/a00.rs:405:5
    |
405 |     thread::spawn(move || {
    |     ^^^^^^^^^^^^^ `Rc<Vec<char>>` cannot be sent between threads safely
    |
    = help: the trait `Send` is not implemented for `Rc<Vec<char>>`
    = note: required because of the requirements on the impl of `Send`
            for `Receiver<Rc<Vec<char>>>`
    = note: required because it appears within the type
            `[closure@src/a00.rs:405:19: 410:6 Receiver<Rc<Vec<char>>>]`
    = note: required by `std::thread::spawn`

Move semantics alone: insufficient

We are computer scientists

Importance of Ownership

Sharing Data

Pointers: Perhaps the Pandora's Box of Computer Science

• &mut T, &T
• (plus library reference types: Box<T>, Cow<T>, Rc<T>, ...)
• T above ranges over both so-called "sized" and "unsized" types
• Sized: &char, &mut Vec<u8>, &[i32; 16]
• Unsized: &str, &mut [u8], &Fn() -> i32

Menagerie: &T, Box<T>, Rc<T> etc

• T: owned instance of T, stored inline (e.g. in stack frame or record)
• Box<T>: owned instance of T, stored on heap (so Box<T> itself is just a pointer)
• &T: pointer to T, but not owned. Extent is limited to some static scope (possibly a scope known only to function's caller).
• Rc<T>: ref-counted pointer to T; shared ownership. (At end of scope for our Rc<T>, we might be responsible for resource cleanup.)

References and Slices

fn demo_references() {
    let v = vec!['a', 'b', 'c', '1', '2', '3'];
    let ref1 = &v[0..3];
    let ref2 = &v[3..6];
    let f1 = |i| println!("ref1[{}]: {:?}", i, ref1[i]);
    let f2 = |i| println!("ref2[{}]: {:?}", i, ref2[i]);
    f1(1);
    f2(2);
}

Rc<T> (shared ownership)

fn demo_refcounts() {
    let r1 = Rc::new(vec!['a', 'b', 'c', '1', '2', '3']);
    let r2 = r1.clone();
    let f1 = |i| println!("v[{}]: {:?}", i, r1[i]);
    let f2 = |i| println!("v[{}]: {:?}", i, r2[i]);
    f1(1);
    f2(2);
}

Is &mut only way to encode mutation via reference?

Interior Mutability: Cell + RefCell

• Both types have mutator methods that take &self (not &mut self)
• Cell<T>: move values in+out (via swapping, or other methods that ensure cell remains sound, e.g. get/set if T: Copy)
• RefCell<T> provides refs to the T it holds, but dynamically enforces the rules.
• RefCell::borrow() returns read-only Ref (many-readers), and panic!'s on outstanding mut-borrow (∴ no previous writers)
• RefCell::borrow_mut() returns read/write RefMut (unique), and panic!'s on any outstanding borrow (∴ no previous readers or writers).

Sharing resources (rayon)

let temp_data = vec!['a', 'b', 'c', '1', '2', '3'];
rayon::scope(|s| {
    let (tx, rx) = channel(); // create transmitter/receiver pair
    s.spawn(move |_s| { // spawn A1, taking ownership of `rx`
        match rx.recv() {
            Ok(v) => println!("A1 received {:?}", v),
            Err(err) => println!("A1 receive failure {:?}", err),
        }
    });
    let data: &[char] = &temp_data; // (N.B. assigned type is *not* `&Vec`)
    let t1 = tx.clone();

    // spawn A2, taking ownership of `t1` (and a copy of `data`)
    s.spawn(move |_s| t1.send(&data[0..4]).expect("A2 send failure"));

    // spawn A3, taking ownership of `tx` (and a copy of `data`)
    s.spawn(move |_s| tx.send(&data[2..6]).expect("A3 send failure"));

}); // (`rayon::scope` waits here until all `s.spawn`'ed threads finish)

Sharing resources between threads

• rx, t1, tx still moved from one thread to another.
• data is shared reference to character slice: freely copyable
• s's are subslices &data[0..4] + &data[2..6] (overlap is safe!)

Sending and sharing intertwine

Can send &-references and &mut-references

• &-refs copy (as usual).
• &mut-refs obey move semantics when sent (as usual)

Examples

fn send_ref_i32(arg: &i32) {
    rayon::scope(move |s| {
        s.spawn(move |_s| println!("arg: {:?}", arg));
    });
}

fn send_ref_vec(arg: &Vec<i32>) {
    rayon::scope(move |s| {
        s.spawn(move |_s| println!("arg: {:?}", arg));
    });
}

fn send_mut_vec(arg: &mut Vec<i32>) {
    rayon::scope(move |s| {
        s.spawn(move |_s| println!("arg: {:?}", arg));
    });
}

So far so good

"Can't always get what you want ..."

Can send &-references and &mut-references ... if data synchronized!

fn send_ref_to_cell(arg: &Cell<i32>) {
    rayon::scope(move |s| {
        s.spawn(move |_s| println!("arg: {:?}", arg));
    });
}

error[E0277]: the trait bound `Cell<i32>: Sync` is not satisfied
   --> src/a00.rs:547:5
    |
547 |     rayon::scope(move |s| {
    |     ^^^^^^^^^^^^ `Cell<i32>` cannot be shared between threads safely
    |
    = help: the trait `Sync` is not implemented for `Cell<i32>`
    = note: required because of the requirements on the impl of `Send` for `&Cell<i32>`
    = note: required because it appears within the type `[closure@src/a00.rs:547:18: 549:6 arg:&Cell<i32>]`
    = note: required by `rayon::scope`

The Send traits

Send: focused on ownership transfer

The Send and Sync traits

• Send and Sync control cross-thread capabilities
• T: Send implies ownership of T can be tranferred across threads
• T: Sync implies a reference to T (e.g. &T, Arc<T>) can be shared across threads
• Send enables Message Passing style concurrency, via channels
• Sync enables Shared State style concurrency; only T with synchronized access is allowed
• Rust compiler automatically marks types as Send or Sync, based on a recursive analysis of their structure.
• Data-structure designer can opt out of above analysis. (If doing unsafe stuff, they may need to do so for soundness!)

See also: https://www.ralfj.de/blog/2017/06/09/mutexguard-sync.html

Thanks

www.rust-lang.org

Hack Without Fear