Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Guaranteeing Memory Safety and Data-Race Freedo...

Guaranteeing Memory Safety and Data-Race Freedom in Rust

A description of Rust, focusing on ownership and borrowing and how they guarantee memory safety and data-race freedom.

nikomatsakis

October 22, 2014
Tweet

More Decks by nikomatsakis

Other Decks in Programming

Transcript

  1. What is control? void example() { vector<string> vector; … auto&

    elem = vector[0]; … } string [0] … elem vector data length capacity [0] [n] […] … ‘H’ … ‘e’ Stack and inline layout. Lightweight references Deterministic destruction Stack Heap C++
  2. Zero-cost abstraction Ability to define abstractions that optimize away to

    nothing. vector data length cap. [0] […] data cap. ‘H’ ‘e’ […] Not just memory layout: - Static dispatch - Template expansion - … Java safe
  3. What is safety? void example() { vector<string> vector; … auto&

    elem = vector[0]; vector.push_back(some_string); cout << elem; } vector data length capacity [0] … [0] [1] elem Aliasing: more than one pointer to same memory. Dangling pointer: pointer to freed memory. C++ Mutating the vector freed old contents.
  4. What about GC? No control. Requires a runtime. Insufficient to

    prevent related problems: iterator invalidation, data races.
  5. Rust’s Solution Type system understands ownership and borrowing: ! 1.

    All memory has a clear owner. 2. Others can borrow from the owner. 3. Owner cannot free the memory while it is borrowed. ! No segfaults.! No data races.! No runtime.
  6. More to Rust than Safety Explicit control is often correlated

    with painfully verbose. ! Rust offers lots of goodies traditionally associated with garbage- collected runtimes: ! - Closures - Pattern matching - Type inference - Traits
  7. vec data length capacity vec data length capacity 1 2

    fn give() { let mut vec = Vec::new(); vec.push(1); vec.push(2); take(vec); … } fn take(vec: Vec<int>) { // … } ! ! ! Take ownership of a Vec<int>
  8. fn give() { let mut vec = Vec::new(); vec.push(1); vec.push(2);

    take(vec); … } vec.push(2); Compiler enforces moves fn take(vec: Vec<int>) { // … } ! ! ! Error: vec has been moved Prevents: - use after free - double moves - …
  9. fn lender() { let mut vec = Vec::new(); vec.push(1); vec.push(2);

    use(&vec); … } fn use(vec: &Vec<int>) { // … } ! ! ! 1 2 vec data length capacity vec “Shared reference to Vec<int>” Loan out vec
  10. T: Iterator<&int> T: Iterator<(&int,&int)> T: Iterator<int> int fn dot_product(vec1: &Vec<int>,

    vec2: &Vec<int>) -> int { vec1.iter() .zip(vec2.iter()) .map(|(&i, &j)| i * j) .fold(0, |s, p| s + p) } http://is.gd/MXCy9M closure 1 2 3 4 5 6 * vec1 vec2 = 32 pattern matching
  11. Why “shared” reference? fn dot_product(vec1: &Vec<int>, vec2: &Vec<int>) -> int

    {…} ! fn magnitude(vec: &Vec<int>) -> int { sqrt(dot_product(vec, vec)) } two shared references to the same vector — OK!
  12. fn use(vec: &Vec<int>) { vec.push(3); vec[1] += 2; } Shared

    references are immutable: Error: cannot mutate shared reference * Actually: mutation only in controlled circumstances * Aliasing Mutation
  13. fn push_all(from: &Vec<int>, to: &mut Vec<int>) { for elem in

    from.iter() { to.push(*elem); } } Mutable references mutable reference to Vec<int> push() is legal
  14. Efficient Iteration 1 2 3 from to elem 1 …

    fn push_all(from: &Vec<int>, to: &mut Vec<int>) { for elem in from.iter() { to.push(*elem); } }
  15. What if from and to are equal? 1 2 3

    from to elem 1 2 3 … 1 fn push_all(from: &Vec<int>, to: &mut Vec<int>) { for elem in from.iter() { to.push(*elem); } } dangling pointer
  16. fn push_all(from: &Vec<int>, to: &mut Vec<int>) {…} ! fn caller()

    { let mut vec = …; push_all(&vec, &mut vec); } shared reference Error: cannot have both shared and mutable reference at same time A &mut T is the only way to access the memory it points at
  17. { let mut vec = Vec::new(); … for i in

    range(0, vec.len()) { let elem: &int = &vec[i]; … vec.push(…); } … vec.push(…); } Borrows restrict access to the original path for their duration. Error: vec[i] is borrowed, cannot mutate OK. loan expired. & &mut no writes, no moves no access at all
  18. data length capacity data length capacity move || { let

    m = Vec::new(); … tx.send(m); } rx tx tx m fn parent() { let (tx, rx) = channel(); spawn(move || {…}); let m = rx.recv(); }
  19. Arc<Vec<int>> &Vec<int> ref_count data length capacity [0] [1] Shared reference,

    so Vec<int> is immutable. Vec<int> Owned, so no aliases. (ARC = Atomic Reference Count)
  20. fn consult<K,V>(shared: Arc<HashMap<K,V>>, key: &K) { match shared.find(key) { Some(value)

    => { use(value); } None => { // no value } } } Overloaded deref operator allows access to the `find()` method on hash maps Reference directly into the map, naturally. No copying. pattern matching again
  21. fn sync_inc(mutex: &Mutex<int>) { let mut data = mutex.lock(); *data

    += 1; } Destructor releases lock Yields a mutable reference to data Destructor runs here, releasing lock
  22. And beyond… Parallelism is an area of active development. !

    Either already have or have plans for: - Atomic primitives - Non-blocking queues - Concurrent hashtables - Lightweight thread pools - Futures - CILK-style fork-join concurrency - etc. Always data-race free
  23. Parallel! ! adj. occurring or existing at the same time

    https://github.com/nikomatsakis/rayon
  24. fn qsort(vec: &mut [int]) { if vec.len() <= 1 {

    return; } let pivot = vec[random(vec.len())]; let mid = vec.partition(vec, pivot); let (less, greater) = vec.split_at_mut(mid); qsort(less); qsort(greater); } [0] [1] [2] [3] […] [n] let vec: &mut [int] = …; less greater
  25. [0] [1] [2] [3] […] [n] let vec: &mut [int]

    = …; less greater fn parallel_qsort(vec: &mut [int]) { if vec.len() <= 1 { return; } let pivot = vec[random(vec.len())]; let mid = vec.partition(vec, pivot); let (less, greater) = vec.split_at_mut(mid); parallel::do(&mut [ || parallel_qsort(less), || parallel_qsort(greater) ]); }
  26. Safe abstractions unsafe { … } • Useful for: •

    Uninitialized memory • Interfacing with C code • Building parallel abstractions like ARC • Ownership/borrowing permit creating safe abstraction boundaries. Trust me. fn something_safe(…) { ! ! ! ! } Validates input, etc.
  27. Status of Rust “Rapidly stabilizing.”! ! ! Goal to release

    1.0 around end of year: - Stable syntax, core type system - Minimal set of core libraries ! Subsequent releases coming every six weeks or so.
  28. Conclusions • Rust combines high-level features with low-level control. •

    Rust gives strong safety guarantees beyond what GC can offer: • No null pointers • Data race freedom • Iterator invalidation