EDIT: I meant a code example, not a paragraph. And I would obviously expect to see how the intended goal is achieved without the bug... otherwise it'd be trivial to prevent any bug (just make everything impossible).
fn use_lock(mutex: &Mutex<Vec<i32>>) {
let vec = {
// acquire the lock
let mut guard = lock(mutex);
// attempt to return a borrow of the data
access(&mut guard)
// guard is destroyed here, releasing the lock
};
// attempt to access the data outside of the lock.
vec.push(3);
}
error: `guard` does not live long enough
access(&mut guard)
^~~~~
Yes, when you construct a mutex, you give it ownership of the vector you want it to protect. Due to the way Rust works, once you've given ownership to something else, you can no longer access it yourself.
The only way you can get access to the data again is to "borrow" a reference to it, but this borrow has a "lifetime", which is tied to the period for which you're holding the mutex. This is how the compiler can spot that you've tried to access the vector after the mutex has been released.
As you say, this means that each vector can only have one mutex wrapping it - at least for this implementation of mutex, known as std::sync::Mutex ( https://doc.rust-lang.org/std/sync/struct.Mutex.html).
However, if you're looking for something like a read/write lock, Rust supports that too via std::sync::RwLock - see https://doc.rust-lang.org/std/sync/struct.RwLock.html for more details.
Obviously, the example uses a vector, but Rust has a pretty strong system of generics, so your mutex (or read/write lock) can wrap pretty much any type, e.g. a struct you've defined.
Hope that makes sense - this was one of the areas of Rust that impressed me most!
The mutex owns the vector. Locking it returns a MutexGuard, which is a smart pointer/reference to the data it owns[0]. You can nest mutexes and structures if you need something slightly more flexible than a single big lock.
Having multiple (side-by-side( locks for a single structure sounds like a recipe for concurrency bugs & deadlocks.
> Which seems quite limiting?
If your semantics call for a mutex it makes perfect sense. There are other types of locks if you don't want a 1:1 relationship e.g. RWLock allows multiple readers XOR a single writer.
[0] mutable, so you can replace the structure behind the guard, you just can't keep a reference to it after you release the lock due to Rust's borrow checking semantics
It is, however, often necessary in order to reduce an undesirable level of contention. For example, hash tables often use fine-grained locking (with one lock per bucket) in order to increase actual parallelism and to prevent the hash table from becoming a serialization bottleneck.
Another common example is the implementation of FIFO queues with two locks (one for the head and one for the tail), which allows threads that read from the queue to avoid/reduce contention with threads that write to the queue.
This is both normal and frequently necessary for performance.
I think an approach similar to this (except with multiple sub-hash-tables, each of which is individually locked) is used by https://github.com/veddan/rust-concurrent-hashmap.
For the two-lock FIFO case, you can definitely do this in Rust but you might need to mark it "unsafe". (I'm happy for someone to prove me wrong on this, though!) "Unsafe" tells Rust "look, I know what I'm doing here" and allows you to do things like operate on raw pointers and generally avoiding checks. However, since Rust is no longer checking these assumptions, you need to be very sure of them yourself!
On the plus side, the rest of your code (e.g. the code using your two-lock FIFO) need not know that an implementation is unsafe - the Rust compiler can still check all the assumptions in that code.
That's the problem here: you're on the honor system that everyone knows and follows every rule every time. Maybe you have a really top-notch team, great code review, etc. but can you say for a certainty that this will always be true, or that it's true of every bit of code you use?
Being able to prove that in advance, especially in more complicated scenarios, has a significant value from checking on every build, especially when you think of the many bugs which have been caused by maintenance code breaking some of the assumptions which the original authors had.
Whilst currently the borrow checker is a bit greedy, it's safe to say that most of the time the borrow checker is checking the code is safe the same way I try to reason about memory accesses in C and C++ when dealing with concurrency or freeing memory. The power of the borrow checker shows itself when reasoning about a local function and no longer requires you to reason about the whole application state as the compiler ensures locality to the extent that shared mutable state is not allowed.
template<typename TVectorPointer>
void write_foo(TVectorPointer vec_ptr) {
(*vec_ptr)[3] += 1;
}
template<typename TVectorPointer>
auto read_foo(TVectorPointer vec_ptr) {
return (*vec_ptr)[7];
}
template<typename TVectorAccessRequester>
void use_shared_vector(TVectorAccessRequester vec_ar) {
{
// obtain a non-const pointer to the vector from the "access requester"
// blocking if necessary
auto wl_ptr = vec_ar.writelock_ptr();
write_foo(wl_ptr);
// the pointer owns a lock on the vector so as long as the pointer
// exists it is safe and valid to use
}
// obtaining and using a const pointer to the vector
auto res1 = read_foo(vec_ar.readlock_ptr());
// without a "lock pointer" obtained from an access requester, there is no way
// to access, or even refer to the shared vector, so you can't access it in an
// unsafe manner
}
Rust doesn't allow having two mutable references to the same memory location at the same time, so you would never encounter that.
Wouldn't that make a whole class of efficient algorithms impossible though? Like let's say you have an std::list<T> and you want a sorted "view" of the elements. In C++ you'd create an array of pointers and then sort it, and after that you can just modify whatever each slot points to. In Rust you... can't do that because they'd all need to be read-only? I don't imagine you can turn the read-only to read-write on a whim (otherwise if you do this with two of them how the hell would the compiler figure out if two of them point to the same slot?) so the whole thing is just impossible?
You can only do this in an `unsafe` block. If you get a bug caused by aliased mutation, then you know exactly where it comes from.
Correct. What it does is prevent data races; this is per se nothing new, but was done as early as the 70s [1]. There've been various and sundry approaches to the same problem over the years (the 90s and early aughts produced a lot of research in this area).
In a way, it is frustrating that so few programming languages offer prevention of data races, so I'm grateful that Rust pushes that; but in another way, it is understandable, because all such mechanisms restrict what you can do, often in undesirable ways. Google "benign data races", for example: data races can be purposely exploited for more efficient implementations.
The other problem is that data races are really the easy part to solve about concurrency. The hard parts are general race conditions, non-determinism/causality, liveness properties (such as freedom from deadlocks and starvation), and performance.
Performance is one of the trickier aspects: in a shared memory system, performance is primarily a matter of reducing contention. But virtually any system that relies on some form of mutual exclusion to prevent data races introduces contention, and you have a constant tug of war between the two concerns.
Particularly frustrating is that all of these issues are what software engineers call "cross-cutting concerns" [2], i.e. things that cannot easily be modularized. For example, performance may suffer from a serialization bottleneck in a module's implementation where you cannot avoid that bottleneck without exposing the module's internals.
https://www.eiffel.org/doc/solutions/Concurrent%20programmin...
http://se.ethz.ch/~meyer/publications/acm/eiffel_sigplan.pdf
http://www.eiffel.com/developers/design_by_contract_in_detai...
Since they have strong QA focus, they also have things like test generation from contracts specifying intended behavior. So, safe concurrency was just one benefit of the work that started in the 1980's. Rust takes things further with a simpler and more flexible approach that supports quite a few different styles of concurrency. That's on top of the temporal safety inspired by the Cyclone language for safe, C-like programming.
Rust's real success is it's the first of the safe, system languages to take off with a massive ecosystem due to their great community efforts. That's probably what Ada and Eiffel needed on top of earlier FOSS implementations.
Here's one way to think of it: There's the kind of code that Rust "wants" you to write, and then there's the kind of code that it allows to write.
Rust "wants":
- Lots of immutable data, with relatively sparing use of mutability.
- Clear ownership and borrowing.
Rust allows:
- Pretty much anything you could write in C, with the possible exception of bitfields in structs. You wanna directly access the pic8259 chip from kernel space? Have fun: https://github.com/emk/toyos-rs/blob/fdc5fb8cc8152a63d1b6c85...
The question is, is it worth exercising that full power for "ordinary" Rust code? To use your example, if you have a data structure D and a view V, can you reach "through" V and mutate the underlying D? Of course you can do this, if you really need to. You have lots of choices, including (for example) cells, locks, tricky lifetime annotations and/or unsafe code.
But in practice, it's usually not worth the hassle. What I do in a case like this is step back and ask myself, "How would I solve this problem in a functional language like Clojure, ML or Haskell?" Oftentimes, that will give me a nice, simple solution that Rust likes. But sometimes I actually do need to do things the hard way.
Part of being happy in Rust is learning how to minimize the use of mutable data. For example, if you're writing a video game and you need to update your "world state", do you really need to mutate the existing state? Or can you write a function that takes the old world state and the player's input, and uses them to compute a brand new world state? The latter actually eliminates all kinds of subtle bugs, and it can be done efficiently.
let vec_of_refs = ll.iter_mut().collect();
vec_of_refs.sort_unstable();
A popular approach is to have both views be indices into an underlying vector where the actual, mutable data is stored. If that isn't good for your situation, it's probably time to use `unsafe` to build an appropriate data structure.
Some stuff is impossible without using 'unsafe', although less than you'd think at first glance.
At first glance you'd think "If you have to use unsafe, why bother using rust?" But it's actually awesome. If 0.01% of your code is marked unsafe, that gives you the bandwidth to audit that part of the code very closely.
Or, as Veedrac mentions, you can do it without any tricks if you can give up accessing the list itself while you have the array around.
You are forced by the compiler to implement an explicit exclusion mechanism.
The point is that kind of issue are silent bugs most of the time(up to point) in C, C++. It can work in most cases, and one day, something goes awfully wrong because the thread scheduling is slightly different than usual.
For example this code, which tries to send a reference-counted pointer between threads, which can cause the reference counter to become unsynchronized and random use-after-free:
use std::thread;
use std::rc::Rc;
fn main() {
let rcs = Rc::new("Hello, World!".to_string());
let thread_rcs = rcs.clone();
thread::spawn(move || {
println!("{}", thread_rcs);
});
}
error[E0277]: the trait bound `std::rc::Rc<std::string::String>: std::marker::Send` is not satisfied in `[closure@src/main.rs:8:19: 10:6 thread_rcs:std::rc::Rc<std::string::String>]`
--> src/main.rs:8:5
|
8 | thread::spawn(move || {
| ^^^^^^^^^^^^^ `std::rc::Rc<std::string::String>` cannot be sent between threads safely
|
= help: within `[closure@src/main.rs:8:19: 10:6 thread_rcs:std::rc::Rc<std::string::String>]`, the trait `std::marker::Send` is not implemented for `std::rc::Rc<std::string::String>`
= note: required because it appears within the type `[closure@src/main.rs:8:19: 10:6 thread_rcs:std::rc::Rc<std::string::String>]`
= note: required by `std::thread::spawn`Rust prevents that by having the concepts of "ownership" and "borrowing" built into the language. The Rust book probably explains this better than I ever could, but the basic idea is that you can only have one actor writing to a variable, OR any number of actors reading a variable. But you cannot have multiple actors having write access the same variable at the same time, or one actor writing to it while anyone has read access to it, unless you use some sort of serialization or copy-on-write mechanism.