Lock permissions: Mutex, Rwlock and Rwcell

On this page

Static and dynamic permissions
Spelling
What the reference may do
Borrowing takes the lock
Where the lock is given back
The lock permissions
Mutex
Rwlock
Rwcell
Which regions take which lock
Defining a lock permission

The static permissions let a shared value be read by many, or changed by one owner at a time, but not both: an Arc[imm, T] crosses threads and never changes, and an Arc[mut, T] may not cross at all. A counter that every thread adds to needs both. A lock permission gives it: many owners, on many threads, may change one value, and the compiler makes sure every change happens while a lock is held. This page covers the three lock permissions, how a borrow takes and gives back the lock, and which regions take which. Afterwards you can share a changing value between threads with no way to touch it unlocked:

mod counter;

import stdio use *;
import thread;
import sync use Arc, Mutex;

struct Count { pub n u64; }
alias Counter = Arc[Mutex, Count];   // many owners, on many threads, one lock

fn add(c Counter) u64 {
  var i = 0u64;
  while i < 100000u64 {
    (&mut *c).n += 1u64;             // the borrow takes the lock, for this statement
    i = i + 1u64;
  }
  i;
}

fn main() {
  let c = new Counter(0u64);
  let a = thread.start(c, &add);     // each start copies the owner
  let b = thread.start(c, &add);
  a.join();
  b.join();
  let total = (&*c).n;
  print <- "total: ", total, "\n";   // 200000, every time
}

It prints:

total: 200000

Try this: write the addition as c.n += 1u64;. The compiler refuses it: Error 1248: May not borrow implicitly through a reference whose permission is the lock Mutex: its value is reached only by borrowing through it, which takes the lock until the borrow ends ('&mut *r', or '&*r' to read).

Static and dynamic permissions#

The static permissions are compiler primitives, checked entirely before the program runs. A lock permission is checked partly while it runs, which is why it is also called a dynamic permission: it is a library type, and its value is the lock. It guarantees that at any moment either one reference changes the value or several read it, never both, while many references, held by many threads, point at it. It does that by having every borrow through it take the lock before the value can be read or changed, and give it back when the borrow ends. Only an owning reference in a region can carry one. Concurrency's roadmap sends you here for them, since they are permissions first.

Spelling#

A static permission is a keyword, written in lower case: mut, imm. A lock permission is a type, named as types are, its first letter alone capitalized: Mutex, Rwlock, Rwcell. It stands where a managed reference's permission does, and the allocation's arguments go to the value's initializer, as for any allocation:

import sync use Arc, Mutex;

alias Counter = Arc[Mutex, Count];
let c = new Counter(0u64);
let point = new Arc[Mutex, Point](x: 2, y: 3);

An allocation runs in one order: the region allocates the memory, the region's part of the header is initialized (the owner count), then the lock (unlocked), then the value (The order of an allocation). The lock lives in the allocation's header, between the region's part and the value, so a lock-managed reference is one pointer, as any managed reference is.

What the reference may do#

A lock-managed reference may be copied: each copy is another owner, counted as the region counts. An Arc[Mutex, T] or Arc[Rwlock, T] may be handed to another thread, as an Arc[imm, T] may, wherever T may cross (it is Sendable, What may cross a thread).

The reference gives no direct access to its value. Through it, no field is read or written, the value is not read whole, no method is called on the value, it is not lent where a borrowed reference is wanted, and no operator changes a field in place. Each is refused with Error 1248, saying that the value is reached only by borrowing:

let n = c.n;            // Error 1248: May not read through a reference whose permission is the lock Mutex
c.n += 1u64;            // Error 1248: May not borrow implicitly through a reference whose permission is ...
let m = c.get();        // Error 1248: May not call a method on the value through ...
show(c);                // Error 1248: May not lend the value through ...
let v = (&*c).n;       // a borrow takes the lock: allowed

Borrowing takes the lock#

To reach the value, obtain a borrowed reference through the lock-managed reference: &mut *p, &*p, or a borrow of a part, &mut p.x, &mut p[i]. Obtaining the borrow acquires the lock first:

A borrow that may write (&mut, &uni) takes the lock for writing, which nobody else holds at the same time.
A read-only borrow (&, &imm) takes the lock for reading, where the lock has a read lock, which other readers may hold at the same time; where it has none (Mutex), it takes the one lock.
On a lock for threads (Mutex, Rwlock), a borrow that finds the lock held waits until it is given back. On Rwcell, whose owners are all on one thread, the holder could only be that thread itself, so a conflicting borrow panics instead, naming the line of the borrow.

Once granted, a borrow never waits: the lock is held for as long as the borrow lasts, and no wait happens inside it. A Condvar waits only on a Mutex held as a value (Roll your own), never on a lock permission's, whose lock sits in a header no program can name.

Where the lock is given back#

The lock is given back at the borrow's last use, as any borrow ends at its last use. The borrow is the only way to the value the lock guards, so a borrow that is never used again protects nothing. Two kinds of borrow differ in how far the last use can be from where the borrow was made:

A borrow a local's initializer makes holds the lock until the last use of the local, or of anything that holds the borrow on: a part of it borrowed in turn and kept, a copy of it, a struct it was put in. On each path the lock goes back after the statement holding that path's last use. A branch of an if that does not use the borrow gives the lock back as it begins, if nothing after the if uses it either; a loop whose body uses the borrow gives it back after the loop. A borrow made in a loop's body is its own on each pass. Every way out gives the lock back too, if it was still held there: the end of the block, a return (whose value may use the borrow), a break, a continue, or, in an actor's behaviour, an await.
Any other borrow, an argument, a field read or written through it, an operator applied to a part of it, holds the lock to the end of its statement, or to an await within the statement.

let point = new Arc[Mutex, Point](x: 2, y: 3);
{
  let pointref = &mut *point;  // takes the lock
  pointref.x += pointref.y;     // the point is reached only while it is held: the last use
  show(point);                  // the lock was given back after that statement, so a
}                               // borrow in show does not wait for this block's end
bump(&mut *point);              // taken and given back within the statement
(&mut *point).y = 7;           // and again

Because a borrow that is not a local's holds its lock to the end of its statement, two borrows through one Mutex in one statement wait on each other for ever: print <- (&*point).x, " ", (&*point).y; prints the first value and hangs. Take one borrow into a local, let p = &*point;, and read both fields through it.

To keep a lock held over a stretch of code, use the borrow in it (or in the statement that ends it). A Mutex or Rwlock held as a value, locked and unlocked by explicit calls, is not a lock permission, and is held until it is unlocked.

An await ends every borrow the behaviour holds, so that no lock is held while the behaviour waits for its reply and its actor handles other messages (Awaiting a reply). A lock borrow used after the await is refused, as any borrow used after its end is; to reach the value again, the behaviour borrows it again:

struct Count { pub n u64; }

actor Clock {
  ticks u64;
  fn init(self &new) { *self = new Self(ticks: 100u64); }
  pub async do now(self) u64 { ticks += 1u64; ticks; }
}

actor Tally {
  count Arc[Mutex, Count];
  clock Clock;

  fn init(self &new, count Arc[Mutex, Count], clock Clock) {
    *self = new Self(count: count, clock: clock);
  }

  pub async do bump(self) u64 {
    let c = &mut *count;                  // takes the lock
    c.n += 1u64;
    let t = await clock.now();            // gives it back
    (&mut *count).n += t;                 // takes it again, for the statement
    (&*count).n;
  }
}

Using c again after the await is refused: Error 1168: The borrow 'c' holds through the lock ... ends at this 'await', where the method returns to its actor's dispatcher to wait, and 'c' is used again.

Copies of the borrow live no longer than the lock: a borrow is not returned from the function, nor stored where it would outlive its block, nor used after the statement whose lock it holds has ended (How long a borrow may live). So nothing reaches the value unlocked. The borrow also keeps the value alive while it lasts, whatever becomes of the reference it was made from.

A panic does not unwind: it ends the whole program, so a lock held when a panic happens is never given back, and nothing runs that could wait for it (Panics).

Cone does not prevent deadlock. A thread borrowing through a Mutex it already holds through another borrow waits for ever, as above, and so do two threads each holding one lock and borrowing through the other's.

The lock permissions#

Mutex#

The sync package's Mutex lets many references to one value be shared across threads, Arc[Mutex, T]. Every borrow through it, read-only or not, takes its one lock, so one borrow at a time, on any thread, reaches the value, as in the counter above.

Rwlock#

The sync package's Rwlock works the same way, except that several read-only borrows may be held at the same time, on any threads. Only one borrow that may write may be held at a time, and none beside it. While a writer waits, new readers wait too, so a stream of readers cannot starve it.

Rwcell#

Core's Rwcell, named so in every module, is like Rwlock except that all its owners stay on one thread: Rc[Rwcell, T]. Its lock is a plain count, and a borrow that conflicts with one still held panics rather than waiting. It suits a value shared by several owners on one thread, where the order of borrows is settled only at run time, such as interior references to a variant or a collection several owners hold:

struct Count { pub n i64; }

let c = new Rc[Rwcell, Count](1);
let d = c;                       // a second owner, on the same thread
let r = &*c;                     // a read borrow: the cell counts one reader
let w = &mut *d;                 // a write borrow while the read is still to be used:
w.n = 2;                         //   "panic at (file):(line): Rwcell: a borrow that may
print <- r.n, "\n";              //   write, while another borrow holds the lock"

Which regions take which lock#

Mutex and Rwlock are locks for threads (each declares ThreadSafe), and fit only a region whose owners may be on several threads, one declaring ThreadSafe: Arc.
Rwcell fits only a region whose owners stay on one thread: Rc.
A region of one owner, Uni, takes no lock: there is nobody to lock against. Nor does a region counting no owners. Each is refused where the type is written.

Not built yet: a borrow that tries the lock and gives up rather than waiting, a time limit on the wait, taking the locks of several values at once, a lock on a traced region (Gc) or behind a virtual reference, and anything preventing a deadlock, which Cone does not do.

Defining a lock permission#

Rarely needed: a lock permission is a struct declaring the built-in trait LockPermission, whose methods the compiler calls with the lock in the header as self:

acquireMut, as a borrow that may write begins, and releaseMut, as it ends; both required.
acquireRead and releaseRead, for a read-only borrow; both, or neither, when a read-only borrow takes the mutable lock.
Each takes only self and returns nothing, except that an acquiring method may also take file &Array[u8], line u32, and is then handed where the borrow is, which Rwcell's panic names.
init, taking only self &new, fills the lock in a new allocation's header.
Declaring ThreadSafe beside it says the lock is for owners on several threads.

The sync package's Mutex and Rwlock are the same types as its plain locks, which a program may also hold as values, with explicit, unchecked lock and unlock (Roll your own).

You can now let many owners, on many threads, change one value, and know exactly how long each borrow holds its lock. Counting and locking cover shared values; the next strategies trade sharing for speed, starting with the fastest allocation there is, the arena.