X-Git-Url: https://git.ralfj.de/rust-101.git/blobdiff_plain/5f6e02d64e3789115ea4327a045b8ad3c39b1808..bc8b6a556edacde1fcdb3bc9c1568373bc31d2d8:/src/part12.rs?ds=inline diff --git a/src/part12.rs b/src/part12.rs index edcb9e0..276ccaf 100644 --- a/src/part12.rs +++ b/src/part12.rs @@ -1,179 +1,194 @@ -// Rust-101, Part 12: Concurrency (WIP) -// ================= - -use std::io::prelude::*; -use std::{io, fs, thread}; -use std::sync::mpsc::{sync_channel, SyncSender, Receiver}; -use std::sync::Arc; - -//@ This part is introducing the concurrency features of Rust. We are going to write our own small version of "grep", -//@ called *rgrep*, and it is going to make use of multiple cores: One thread reads the input files, one thread does -//@ the actual matching, and one thread writes the output. - -// Before we come to the actual code, we define a data-structure `Options` to store all the information we need -// to complete the job: Which files to work on, which pattern to look for, and how to output.
-// Besides just printing all the matching lines, we will also offer to count them, or alternatively to sort them. -#[derive(Clone,Copy)] -enum OutputMode { - Print, - SortAndPrint, - Count, -} -use self::OutputMode::*; - -struct Options { - files: Vec, - pattern: String, - output_mode: OutputMode, +// Rust-101, Part 12: Rc, Interior Mutability, Cell, RefCell +// ========================================================= + +use std::rc::Rc; +use std::cell::{Cell, RefCell}; + +//@ Our generic callback mechanism is already working quite nicely. However, there's one point we +//@ may want to fix: `Callbacks` does not implement `Clone`. The problem is that closures (or +//@ rather, their environment) can never be cloned. +//@ (There's not even an automatic derivation happening for the cases where it would be possible.) +//@ This restriction propagates up to `Callbacks` itself. What could we do about this? + +//@ ## `Rc` +//@ The solution is to find some way of cloning `Callbacks` without cloning the environments. This +//@ can be achieved with `Rc`, a *reference-counted* pointer. This is another example of a +//@ smart pointer. You can `clone` an `Rc` as often as you want, that doesn't affect the data it +//@ contains. It only creates more references to the same data. Once all the references are gone, +//@ the data is deleted. +//@ +//@ Wait a moment, you may say here. Multiple references to the same data? That's aliasing! Indeed: +//@ Once data is stored in an `Rc`, it is read-only and you can only ever get a shared reference to the data again. + +//@ Because of this read-only restriction, we cannot use `FnMut` here: We'd be unable to call the +//@ function with a mutable reference to it's environment! So we have to go with `Fn`. We wrap that +//@ in an `Rc`, and then Rust happily derives `Clone` for us. +#[derive(Clone)] +struct Callbacks { + callbacks: Vec>, } -//@ Now we can write three functions to do the actual job of reading, matching, and printing, respectively. -//@ To get the data from one thread to the next, we will use *message passing*: We will establish communication -//@ channels between the threads, with one thread *sending* data, and the other one receiving it. `SyncSender` -//@ is the type of the sending end of a synchronous channel transmitting data of type `T`. *Synchronous* here -//@ means that the `send` operation could block, waiting for the other side to make progress. We don't want to -//@ end up with the entire files being stored in the buffer of the channels, and the output not being fast enough -//@ to keep up with the speed of input. -//@ -//@ We also need all the threads to have access to the options of the job they are supposed to do. Since it would -//@ be rather unnecessary to actually copy these options around, we will use reference-counting to share them between -//@ all threads. `Arc` is the thread-safe version of `Rc, using atomic operations to keep the reference count up-to-date. -//@ You can also think of this as saying that *all* threads own the `Options` "a bit" - and since there could be other -//@ owners, `Arc` (just like `Rc`) only permits read-only access to its content. That's good enough for the options, though. - -// The first functions reads the files, and sends every line over the `out_channel`. -fn read_files(options: Arc, out_channel: SyncSender) { - for file in options.files.iter() { - // First, we open the file, ignoring any errors. - let file = fs::File::open(file).unwrap(); - // Then we obtain a `BufReader` for it, which provides the `lines` function. - let file = io::BufReader::new(file); - for line in file.lines() { - let line = line.unwrap(); - // Now we send the line over the channel, ignoring the possibility of `send` failing. - out_channel.send(line).unwrap(); - } +impl Callbacks { + pub fn new() -> Self { + Callbacks { callbacks: Vec::new() } } - // When we drop the `out_channel`, it will be closed, which the other end can notice. -} -// The second function filters the lines it receives through `in_channel` with the pattern, and sends -// matches via `out_channel`. -fn filter_lines(options: Arc, in_channel: Receiver, out_channel: SyncSender) { - // We can simply iterate over the channel, which will stop when the channel is closed. - for line in in_channel.iter() { - // `contains` works on lots of types of patterns, but in particular, we can use it to test whether - // one string is contained in another. - if line.contains(&options.pattern) { - out_channel.send(line).unwrap(); /*@*/ - } + // Registration works just like last time, except that we are creating an `Rc` now. + pub fn register(&mut self, callback: F) { + self.callbacks.push(Rc::new(callback)); /*@*/ } -} -// The third function performs the output operations, receiving the relevant lines on its `in_channel`. -fn output_lines(options: Arc, in_channel: Receiver) { - match options.output_mode { - Print => { - // Here, we just print every line we see. - for line in in_channel.iter() { - println!("{}", line); /*@*/ - } - }, - Count => { - // We are supposed to count the number of matching lines. There's a convenient iterator adapter that - // we can use for this job. - let count = in_channel.iter().count(); /*@*/ - println!("{} hits for {}.", count, options.pattern); /*@*/ - }, - SortAndPrint => { - // We are asked to sort the matching lines before printing. So let's collect them all in a local vector... - let data: Vec = in_channel.iter().collect(); - // ...and implement the actual sorting later. - unimplemented!() + pub fn call(&self, val: i32) { + // We only need a shared iterator here. Since `Rc` is a smart pointer, we can directly call the callback. + for callback in self.callbacks.iter() { + callback(val); /*@*/ } } } -// With the operations of the three threads defined, we can now implement a function that performs grepping according -// to some given options. -fn run(options: Options) { - // We move the `options` into an `Arc`, as that's what the thread workers expect. - let options = Arc::new(options); - - // Set up the channels. Use `sync_channel` with buffer-size of 16 to avoid needlessly filling RAM. - let (line_sender, line_receiver) = sync_channel(16); - let (filtered_sender, filtered_receiver) = sync_channel(16); - - // Spawn the read thread: `thread::spawn` takes a closure that is run in a new thread. - //@ The `move` keyword again tells Rust that we want ownership of captured variables to be moved into the - //@ closure. This means we need to do the `clone` *first*, otherwise we would lose our `options` to the - //@ new thread! - let options1 = options.clone(); - let handle1 = thread::spawn(move || read_files(options1, line_sender)); - - // Same with the filter thread. - let options2 = options.clone(); - let handle2 = thread::spawn(move || filter_lines(options2, line_receiver, filtered_sender)); - - // And the output thread. - let options3 = options.clone(); - let handle3 = thread::spawn(move || output_lines(options3, filtered_receiver)); - - // Finally, wait until all three threads did their job. - handle1.join().unwrap(); - handle2.join().unwrap(); - handle3.join().unwrap(); +// Time for a demo! +fn demo(c: &mut Callbacks) { + c.register(|val| println!("Callback 1: {}", val)); + c.call(0); c.clone().call(1); } -// Now we have all the pieces together for testing our `rgrep` with some hard-coded options. -//@ We need to call `to_string` on string literals to convert them to a fully-owned `String`. pub fn main() { - let options = Options { - files: vec!["src/part10.rs".to_string(), "src/part11.rs".to_string(), "src/part12.rs".to_string()], - pattern: "let".to_string(), - output_mode: Print - }; - run(options); + let mut c = Callbacks::new(); + demo(&mut c); } -// **Exercise 12.1**: Change `rgrep` such that it prints now only the matching lines, but also the name of the file -// and the number of the line in the file. You will have to change the type of the channels from `String` to something -// that records this extra information. - -//@ ## Ownership, Borrowing, and Concurrency -//@ The little demo above showed that concurrency in Rust has a fairly simple API. However, considering Rust has closures, -//@ that should not be entirely surprising. However, as I mentioned in the beginning, Rust ensures that well-typed programs -//@ do not have data races. How can that be? A data race is typically defined as having two concurrent, unsynchronized -//@ accesses to the same memory location, at least one of which is a write. In other words, a data race is mutation in -//@ the presence of aliasing, which Rust reliably rules out! It turns out that the same mechanism that makes our single-threaded -//@ programs memory safe, and that prevents us from invalidating iterators, also helps secure our multi-threaded code against -//@ data races. For example, notice how `read_files` sends a `String` to `filter_lines`. At run-time, only the pointer to -//@ the string will actually be moved around (just like when a `String` is passed to a function with full ownership). However, -//@ `read_files` has to *give up* ownership of the string to perform `send`, to it is impossible for an outstanding borrow to -//@ still be around. After it sent the string to the other side, `read_files` has no way to race on the data with someone else. -//@ -//@ However, there is more to this. Remember the `'static` bound we had to add to `register` in the previous part, to make -//@ sure that the callbacks to not reference any pointers that might become invalid? This is just as crucial for spawning -//@ a thread: In general, that thread could last for much longer than the current stack frame. Thus, it must not use -//@ any pointers to data in that stack frame. This is achieved by requiring the `FnOnce` closure passed to `thread::spawn` -//@ to be valid for lifetime `'static`, as you can see in [its documentation](http://doc.rust-lang.org/stable/std/thread/fn.spawn.html). -//@ This avoids another kind of data race, where the thread's access races with the callee deallocating its stack frame. - -//@ ## Send -//@ However, the story goes further. I said above that `Arc` is a thread-safe version of `Rc`, which uses atomic operations -//@ to manipulate the reference count. It is thus crucial that we don't use `Rc` above, or the reference count may become invalid. -//@ And indeed, if you replace `Arc` by `Rc` (and add the appropriate imports), Rust will tell you that something is wrong. -//@ That's great, of course, but how did it do that? +// ## Interior Mutability +//@ Of course, the counting example from last time does not work anymore: It needs to mutate the +//@ environment, which a `Fn` cannot do. The strict borrowing Rules of Rust are getting into our +//@ way. However, when it comes to mutating a mere number (`usize`), there's not really any chance +//@ of problems coming up. Everybody can read and write that variable just as they want. +//@ So it would be rather sad if we were not able to write this program. Lucky enough, Rust's +//@ standard library provides a solution in the form of `Cell`. This type represents a memory +//@ cell of some type `T`, providing the two basic operations `get` and `set`. `get` returns a +//@ *copy* of the content of the cell, so all this works only if `T` is `Copy`. +//@ `set`, which overrides the content, only needs a *shared reference* to the cell. The phenomenon +//@ of a type that permits mutation through shared references (i.e., mutation despite the +//@ possibility of aliasing) is called *interior mutability*. You can think of `set` changing only +//@ the *contents* of the cell, not its *identity*. In contrast, the kind of mutation we saw so far +//@ was about replacing one piece of data by something else of the same type. This is called +//@ *inherited mutability*.
+//@ Notice that it is impossible to *borrow* the contents of the cell, and that is actually the key +//@ to why this is safe. + +// So, let us put our counter in a `Cell`, and replicate the example from the previous part. +fn demo_cell(c: &mut Callbacks) { + { + let count = Cell::new(0); + // Again, we have to move ownership of the `count` into the environment closure. + c.register(move |val| { + // In here, all we have is a shared reference of our environment. But that's good enough + // for the `get` and `set` of the cell! + //@ At run-time, the `Cell` will be almost entirely compiled away, so this becomes + //@ pretty much equivalent to the version we wrote in the previous part. + let new_count = count.get()+1; + count.set(new_count); + println!("Callback 2: {} ({}. time)", val, new_count); + } ); + } + + c.call(2); c.clone().call(3); +} + +//@ It is worth mentioning that `Rc` itself also has to make use of interior mutability: When you +//@ `clone` an `Rc`, all it has available is a shared reference. However, it has to increment the +//@ reference count! Internally, `Rc` uses `Cell` for the count, such that it can be updated during +//@ `clone`. //@ -//@ The answer is already hinted at in the error: It will say something about `Send`. You may have noticed that the closure in -//@ `thread::spawn` does not just have a `'static` bound, but also has to satisfy `Send`. `Send` is a trait, and just like `Copy`, -//@ it's just a marker - there are no functions provided by `Send` What the trait says is that types which are `Send`, can be -//@ safely sent to another thread without causing trouble. Of course, all the primitive data-types are `Send`. So is `Arc`, -//@ which is why Rust accepted our code. But `Rc` is not `Send`, and for a good reason! +//@ Putting it all together, the story around mutation and ownership through references looks as +//@ follows: There are *unique* references, which - because of their exclusivity - are always safe +//@ to mutate through. And there are *shared* references, where the compiler cannot generally +//@ promise that mutation is safe. However, if extra circumstances guarantee that mutation *is* +//@ safe, then it can happen even through a shared reference - as we saw with `Cell`. + +// ## `RefCell` +//@ As the next step in the evolution of `Callbacks`, we could try to solve this problem of +//@ mutability once and for all, by adding `Cell` to `Callbacks` such that clients don't have to +//@ worry about this. However, that won't end up working: Remember that `Cell` only works with +//@ types that are `Copy`, which the environment of a closure will never be. We need a variant of +//@ `Cell` that allows borrowing its contents, such that we can provide a `FnMut` with its +//@ environment. But if `Cell` would allow that, we could write down all those crashing C++ +//@ programs that we wanted to get rid of. //@ -//@ Now, `Send` as a trait is fairly special. It has a so-called *default implementation*. This means that *every type* implements -//@ `Send`, unless it opts out. Opting out is viral: If your type contains a type that opted out, then you don't have `Send`, either. -//@ So if the environment of your closure contains an `Rc`, it won't be `Send`, preventing it from causing trouble. If however every -//@ captured variable *is* `Send`, then so is the entire environment, and you are good. +//@ This is the point where our program got too complex for Rust to guarantee at compile-time that +//@ nothing bad will happen. Since we don't want to give up the safety guarantee, we are going to +//@ need some code that actually checks at run-time that the borrowing rules are not violated. Such +//@ a check is provided by `RefCell`: Unlike `Cell`, this lets us borrow the contents, and it +//@ works for non-`Copy` `T`. But, as we will see, it incurs some run-time overhead. + +// Our final version of `Callbacks` puts the closure environment into a `RefCell`. +#[derive(Clone)] +struct CallbacksMut { + callbacks: Vec>>, +} + +impl CallbacksMut { + pub fn new() -> Self { + CallbacksMut { callbacks: Vec::new() } + } + + pub fn register(&mut self, callback: F) { + let cell = Rc::new(RefCell::new(callback)); /*@*/ + self.callbacks.push(cell); /*@*/ + } + + pub fn call(&mut self, val: i32) { + for callback in self.callbacks.iter() { + // We have to *explicitly* borrow the contents of a `RefCell` by calling `borrow` or + // `borrow_mut`. + //@ At run-time, the cell will keep track of the number of outstanding shared and + //@ mutable references, and panic if the rules are violated.
+ //@ For this check to be performed, `closure` is a *guard*: Rather than a normal + //@ reference, `borrow_mut` returns a smart pointer ([`RefMut`](https://doc.rust- + //@ lang.org/stable/std/cell/struct.RefMut.html), in this case) that waits until is + //@ goes out of scope, and then appropriately updates the number of active references. + //@ + //@ Since `call` is the only place that borrows the environments of the closures, we + //@ should expect that the check will always succeed, as is actually entirely useless. + //@ However, this is not actually true. Several different `CallbacksMut` could share a + //@ callback (as they were created with `clone`), and calling one callback here could + //@ trigger calling all callbacks of the other `CallbacksMut`, which would end up + //@ calling the initial callback again. + //@ This issue of functions accidentally recursively calling themselves is called + //@ *reentrancy*, and it can lead to subtle bugs. Here, it would mean that the closure + //@ runs twice, each time thinking it has a unique, mutable reference to its + //@ environment - so it may end up dereferencing a dangling pointer. Ouch! + //@ Lucky enough, Rust detects this at run-time and panics once we try to borrow the + //@ same environment again. I hope this also makes it clear that there's absolutely no + //@ hope of Rust performing these checks statically, at compile-time: It would have to + //@ detect reentrancy! + let mut closure = callback.borrow_mut(); + // Unfortunately, Rust's auto-dereference of pointers is not clever enough here. We + // thus have to explicitly dereference the smart pointer and obtain a mutable reference + // to the content. + (&mut *closure)(val); + } + } +} + +// Now we can repeat the demo from the previous part - but this time, our `CallbacksMut` type +// can be cloned. +fn demo_mut(c: &mut CallbacksMut) { + c.register(|val| println!("Callback 1: {}", val)); + c.call(0); + + { + let mut count: usize = 0; + c.register(move |val| { + count = count+1; + println!("Callback 2: {} ({}. time)", val, count); + } ); + } + c.call(1); c.clone().call(2); +} + +// **Exercise 12.1**: Write some piece of code using only the available, public interface of +// `CallbacksMut` such that a reentrant call to a closure is happening, and the program panics +// because the `RefCell` refuses to hand out a second mutable borrow of the closure's environment. -//@ [index](main.html) | [previous](part11.html) | [next](main.html) +//@ [index](main.html) | [previous](part11.html) | [raw source](workspace/src/part12.rs) | +//@ [next](part13.html)