Dangers of Shared State
If you're a functional programmer, you're probably used to a language in which nested data structures are allocated in several heap cells, each of which is garbage-collected, so multiple users can freely alias into the same data, implicitly copy to make changes, and so on.
Rust's approach is somewhat different: it focuses on stack-allocation, avoiding expensive implicit copies, and predictable performance. In fact, heap-allocation only occurs when you write the @ or ~ sigil; and, absent @-pointers, Rust's representation semantics don't involve garbage collection at all. Instead:
- Data types are representated with interior types, meaning data types are embedded directly within one another rather than using pointer indirection. You can, of course, create borrowed pointers to such types and pass them between functions.
- Stack-allocated and ~-allocated values are owned data, which get eagerly freed/deinitialised immediately upon going out of scope or being overwritten.
- Rustic data structures can have in-place mutability, indicated with the mut keyword. While also supported by many other functional languages, in Rust it presents new difficulties with aliasing pointers because of point #2 above.
With such a C/C++-like representation model, the prospect of sharing mutable state among multiple actors is a lot more dangerous. To show why, let's say we added a data-race-enabling function to ARC's interface:
fn get_mut<T: Const Send>(arc: &a/ARC<T>) -> &a/mut T
Then we can commit badness like:
let arc: ARC<Option<~int>> = ARC(Some(~31337));
let arc2 = clone(&arc);
do task::spawn |move arc2| {
// Might print "Some(~31337)". Might print "None". Might segfault.
io::println(fmt!("%?", *get(&arc2)));
}
// Frees and deinitialises the owned pointer inside the ARC.
*get_mut(&arc) = None;
// (But what if this runs after the other task determines the data
// is Some, but before it dereferences the contained pointer??)
With sufficient cleverness, this can even be harnessed to implement arbitrary type coercion. (See my solution here.)
Reader-Writer ARCs
The ARC already existed when I arrived at Mozilla, but there was no similar (and safe) solution for the state being mutable. I created the RWARC, with a reader-writer lock inside, to fill this gap.
You create them just like you create ARCs:
fn RWARC<T: Const Send>(data: T) -> RWARC<T>
fn clone<T: Const Send>(arc: &RWARC<T>) -> RWARC<T>
But when using them, instead of getting an unlimited-use reference to the data inside, you give the interface a closure to run on the data, and it runs the closure for you with the rwlock held in the correct mode.
fn read <T: Const Send>(arc: &RWARC<T>, blk: fn(&T))
fn write<T: Const Send>(arc: &RWARC<T>, blk: fn(&mut T))
The key difference is that the region associated with the data pointer is the region of the closure, rather than some arbitrary region defined by the caller. This allows read() and write() to enforce that the contained reader-writer lock is always held in the correct mode when references to the data exist.
Now we can fix the example from before.
let arc = RWARC(Some(~31337));
for 5.times {
let arc2 = clone(&arc);
do task::spawn |move arc2| {
do read(&arc2) |state: &Option<~int>| {
// Long-running reads on state still happen in parallel.
io::println(fmt!("%?", *state));
}
}
}
do write(&arc) |state: &mut Option<~int>| {
// Exclusive write access. No other aliases to state can exist concurrently.
*state = None;
}
Note that while data races are no longer possible, race conditions in general still are. (I mentioned earlier that shared mutable state introduces nondeterminism.) Here, anywhere between zero and five "None"s will be printed.
The compiler will, of course, reject code that tries to cheat the interface:
let escaped_state;
do write(&arc) |state| {
escaped_state = state; // ERROR: reference not valid outside of its lifetime
}
A brief informal justification of safety:
- The Const restriction still enforces that readers only see deeply immutable state. Also, even with mutable state, it still prevents cycles from being created, because the RWARC itself does not have the Const kind.
- References to the shared state cannot escape the closure called by read() or write(). In effect, the region system statically enforces that the lock must be held in order to access the state.
The Concurrency Primitives You Know and Love
Condition Variables
The RWARC also comes with some other features to remind you of home (if "home" to you means old C-style concurrency primitives you fought off race conditions with back in the day). We have condition variables:
fn write_cond<T: Const Send>(arc: &RWARC<T>, blk: fn(&mut T, &Condvar))
fn wait(cond: &Condvar)
fn signal(cond: &Condvar) -> bool
fn broadcast(cond: &Condvar) -> uint
These work as you might expect. Like the &mut T reference, the Condvar reference can only be used inside the closure (i.e., while the lock is held).
let arc = RWARC(~[]);
let arc2 = clone(&arc);
do task::spawn |move arc2| {
do write_cond(&arc2) |state,cond| {
// Poor man's message-passing. Of course, pipes are much
// faster; rwarcs and condvars are built on top of pipes.
vec::push(state, ~"hello there!");
signal(cond);
}
}
do write_cond(&arc) |state,cond| {
while state.len() == 0 {
wait(cond);
}
io::println(vec::pop(state));
}
(The more seasoned concurrency hackers among you might now be wondering what if you wanted to associate multiple conditions with the same state? That can be done too -- gritty details are in the docs.)
Downgrade (or, Now You're Just Showing Off with the Region System)
(Do feel free to zone out for this section.)
If you're used to being able to atomically "downgrade" write access into read access without letting other writers through in the meantime, you can do that here too. (I'm presenting this feature mostly just to show off more stuff you can do by combining the region system with noncopyable types.)
// Calls a closure which will write, then downgrade, then read.
fn write_downgrade<T: Const Send>(arc: &RWARC<T>, blk: fn(RWWriteMode/&a<T>))
// Converts a "write permission" token to a "read permission" token.
fn downgrade<T: Const Send>(token: RWWriteMode/&a<T>) -> RWReadMode/&a<T>
fn write<T: Const Send>(token: &RWWriteMode<T>, blk: fn(&mut T))
fn read <T: Const Send>(token: &RWReadMode <T>, blk: fn(&T))
Here, the RWWriteMode and RWReadMode are noncopyable "permission tokens" that allow the user to write or read, and downgrade() is a function that consumes the write token and wakes up any readers waiting on the rwlock. Since the tokens are noncopyable, the caller cannot still have write permissions after calling downgrade() (which would, of course, result in data races).
The "RWWriteMode/&a" syntax indicates an opaque data structure with region pointers inside. While the write mode token is passed by ownership (so that it can in turn be surrendered to downgrade()), its scope is still constrained by the associated region, which means it can't escape from the closure passed to write_downgrade(). And downgrade() converts a write mode token to a read mode token with the same region, so the latter can't escape either.
Complex as the above functions may seem, using the interface simply looks like this:
do write_downgrade(&arc) |token| {
do write(&token) |mutable_state| {
...
}
let token = downgrade(move token);
do read(&token) |immutable_state| {
...
}
}
Unwrap
Finally, RWARCs (ARCs too) also now have a mechanism to get your data back out again.
fn unwrap<T: Const Send>(arc: RWARC<T>) -> T
Of course, it wouldn't be valid to reclaim ownership of the data while other tasks might still have aliases to it. Instead, unwrap() blocks the calling task until its reference is the only reference alive, and then takes ownership of the data instead of freeing it. (To avoid deadlock, subsequent callers to unwrap() on the same ARC immediately fail.)
This adds expressivity in two ways: it relieves you from having to deeply-copy the shared data if you need to own it (which would be extra problematic if it had noncopyables inside), and it automatically synchronises with the ARC's other users. You could use this to implement a fork-join pattern, like so:
let arc = RWARC(some_data);
for num_cpus().times {
let arc2 = clone(&arc);
do task::spawn |move arc2| {
process_data(arc2); // might read, write, whatever
}
}
let modified_data = unwrap(move arc); // blocks on all child tasks at once
// do more of the algorithm, etc.
All this without ever once copying the data.
This about wraps up the contributions I made this summer at Mozilla. In my next post I'll conclude the series with a summary of why I like Rust so much.
No comments:
Post a Comment