Lock Permissions

On this page

Spelling
What the reference may do
Borrowing takes the lock
Where the lock is given back
List of Permissions
Mutex
Rwlock
Rwcell
Which regions take which lock
Defining a lock permission

Note: Three lock permissions are implemented: Mutex and Rwlock, the sync package's, on Arc, and Rwcell, core's, on Rc. Not implemented: 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.

Earlier we talked about the static permissions. In addition to these are lock permissions, which can only be used on region-managed references. Unlike static permissions, which are built-in compiler primitives, lock permissions are library-implemented: each is a type, and its value is the lock.

Lock permissions are needed when we want to guarantee that only one reference can change or multiple references can read the object value at-a-time (aliasability xor mutability), while many references, held by many threads, point at it. This is accommodated by having borrowing acquire the lock before the underlying value can be read or changed. When the borrowed reference expires, the lock is automatically released.

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];
imm c = new Counter(0u64);
imm 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 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, Race condition safety).

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, saying that the value is reached only by borrowing.

imm n = c.n;            // refused: a read without the lock
c.n += 1u64;            // refused
imm v = (&*c).n;       // a borrow takes the lock: allowed

Borrowing takes the lock#

To reach the value, one obtains 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 (Concurrency), 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.

imm point = new Arc[Mutex, Point](x: 2, y: 3);
{
  imm 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

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 Tally {
  count Arc[Mutex, Count];
  clock Clock;

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

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 (Borrowed References). 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 forever, as do two threads each holding one lock and borrowing through the other's.

List of Permissions#

Mutex#

The Mutex permission, the sync package's, enables multiple references to one value to 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.

import thread;
import sync use Arc, Mutex;

struct Count { pub n u64; }
alias Counter = Arc[Mutex, Count];

fn add(c Counter) u64 {
  mut i = 0u64;
  while i < 100000u64 {
    (&mut *c).n += 1u64;       // one addition under the lock
    i = i + 1u64;
  }
  i;
}

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

Rwlock#

The Rwlock permission, the sync package's, works very much the same way as Mutex, except that it allows multiple read-only borrowed references to be obtained at the same time, on any threads. However, only one borrow that may write may be obtained at a time, and none beside it. While a writer waits, new readers wait too, so a stream of readers cannot starve it.

Rwcell#

The Rwcell permission, core's, so named in every module, is quite similar to Rwlock, except that all its reference copies are constrained to stay in a single thread: Rc[Rwcell, T]. Its lock is a plain count, and a borrow that conflicts with one still held panics rather than waiting. This is useful when one wishes to serialize at runtime the acquisition of interior references to variant or collection values shared by several owners.

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, So, takes no lock: there is nobody to lock against. Nor does a region counting no owners, nor, yet, a traced region or a virtual reference. Each is refused where the type is written.

Defining a lock permission#

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 (Concurrency).