Cone Language Reference

What may cross a thread: Sendable and Shareable

On this page

Note: Not yet checked: a global's type must be Shareable (a plain var global, which several threads could reach, is not yet refused), and a value's own methods that change it through a &. Not built yet: concurrent data structures other than channels and atomic values. The sync package runs on Windows and Linux (x86-64), not yet on macOS.

Every tool in this part does one of two things with a value: hands it to another thread, as a message to an actor does, or lets several threads read it at once, as the passes of a parallel each do. Get either wrong and two threads race on the same memory. Cone decides both questions with two built-in markers, Sendable and Shareable, which the compiler works out from what a type holds, with nothing for you to write. This page says what each allows and why, so that you can read a refusal and fix it. Here one price list is read on every core and sent to an actor:

mod prices;

import stdio use *;
import collections use *;
import actors;
import sync use Arc;

struct Prices {
  pub loaf i32;
  pub bun i32;
}

actor Till {
  // Every parameter of a behaviour must be Sendable
  pub async do sell(self, prices Arc[imm, Prices], loaves i32, buns i32) {
    print <- "The till charges $", loaves * prices.loaf + buns * prices.bun, "\n";
  }
}

fn main() {
  // An Arc's count is atomic, so its owners may live on any thread
  let prices = new Arc[imm, Prices](loaf: 3, bun: 1);

  // Every pass of a parallel each may read it at once: it is Shareable
  let orders = new List[i32] <- 1, 2, 3, 4;
  let costs = new List[i32] <- parallel each n in orders yield *n * prices.loaf;
  print <- "Ten loaves cost $", costs.parallel().sum(), "\n";

  // And it may be sent to an actor: it is Sendable
  let till = new Till();
  till.sell(prices, 2, 5);
}

It prints:

Ten loaves cost $30
The till charges $11

Now make the price list an Rc[imm, Prices], the counted owner for one thread, and the behaviour is refused where it is declared:

Error 1194: Actor Till's behaviour sell takes prices, a Rc[imm, Prices], which is not Sendable: it is an owner
that may be copied, and Rc does not declare ThreadSafe: its copies could not be made and dropped on several
threads at once. It may cross as a uni owner, which moves it, or as an owner of a region declaring ThreadSafe,
such as Arc. A message carries its arguments to the thread the actor runs on, so each must be Sendable.

Nothing in the price list changes, yet it may not cross. The danger is in the owner, not the value: every copy of an Rc adds one to its count, and two threads adding at the same moment can lose one, so the list is freed while a thread still reads it. An Arc counts with atomic operations, so its copies may be made and dropped anywhere.

Race safety: what the compiler promises#

A data race is two threads reaching the same memory at once, at least one of them writing, with nothing to order them. Its symptoms are the worst kind: a total that is occasionally wrong, an object freed twice once a week. Cone refuses a data race when the program is compiled, with two layers of rules.

The first layer is the one Memory taught: permissions. A reference's permission says what its holder may do and what others may do meanwhile, so a value that may be changed through one reference is never read through another unchecked, on any thread. Lock permissions (Lock permissions) make the same promise for a value that several threads change, taking a lock as a borrow begins. This part does not repeat those rules.

The second layer is this page's: a value reaches another thread only if its type says it may. Together they promise that every way a program has to share a value between threads is safe: a message, a thread's start, a channel, a parallel loop's body. What the compiler does not promise is just as important. It does not prevent a deadlock (two threads each waiting for what the other holds), nor a race condition in the wider sense, where the result depends on which thread got there first, as in the Guide's bakery, where which customer went short could change from run to run, though the loaves were always counted right. And it trusts the program in a few named places, each said where it arises: a raw pointer; a type that declares a marker for itself (below); a GPU kernel's buffers (The GPU); the runtime's low-level parallel loop (How the runtime works); a function the compiler cannot read, such as an extern one, that writes a global from a parallel loop; and, until it is checked, a plain var global.

Sendable: what may be handed to another thread#

Sendable says a value may be handed to another thread. It is asked wherever a value crosses:

  • of every parameter of an actor's behaviour and initializer, and of a behaviour's answer (The declaration). An actor's state is not asked, since it never crosses as a value: it may hold an Rc, and its methods may borrow freely;
  • of the value thread.start and thread.startWith hand a new thread, and of what the thread returns;
  • of the values a channel carries: Channel[T], Sender[T], SoloSender[T] and Receiver[T] ask it of T, as the one-shot channel does;
  • by any generic that asks it of a type parameter, as a constraint, which is how library code marks what crosses threads.

The compiler grants Sendable to a type unless it holds, directly or in a field, an array element, a tuple element or an enum's variant, one of these:

  • a borrowed reference, of any permission, &imm included: a borrow's lifetime is checked in one thread alone (but for a borrow that lasts the whole program, below);
  • an owner that may be copied whose permission is not race-safe: Rc[mut, T], Arc[mut, T], and the lock permission for one thread, Rc[Rwcell, T]. The lock permissions for threads cross, Arc[Mutex, T] and Arc[Rwlock, T], where T may (Lock permissions);
  • an owner that may be copied in a region that does not declare ThreadSafe, whatever its permission: Rc[imm, T], whose count is not atomic. Arc[imm, T] and Arc[opaq, T] cross;
  • a traced reference, Gc or an actor's ActorGc, whatever its permission: the first's collector is single-threaded, and the second stays in the actor whose collector moves it (The actor's own garbage-collected region);
  • a raw pointer, whose target nothing checks.

An owner that moves takes its value with it: a uni owner of any region, and any owner of Uni, crosses when what it points at may. So does an Arc[imm, T] owner: an Arc of a value holding a mut reference is refused. A reference to a function crosses, and so does an actor's handle, whatever its state holds. A type holding raw pointers it shares safely declares is Sendable, which the compiler takes on trust, as a channel's ends, ThreadRef, and the collections package's List and Dict do; an instance of a generic type declaring it is Sendable only where its type arguments are.

What is checked is the type of the value, not how a variable was declared: a local declared var x = 5 holds a number, which is Sendable, while &mut x is a borrow, which is not. A refusal names the part of the type that binds it to its thread:

struct Counter { pub n i64; }
struct Job { pub data &mut Counter; }

fn work(j Job) i64 { j.data.n; }

var c = new Counter(1i64);
let t = thread.start(new Job(&mut c), &work);    // refused

Error 1194: start requires A is Sendable, and Job is not Sendable: Job.data is &mut Counter, a borrowed
reference of permission mut, and a borrow crosses threads only if it lives for the whole program and is let or
opaq (any number of threads may read what it reaches, and none writes) or uni (it moves, so one holder has it).
This permission lets a holder write while others may read. What is checked is the types of the references a
value holds, not how a variable was declared: a local declared 'var x = 5' holds a number, which is Sendable.

Shareable: what several threads may read at once#

Sending is one question; sharing is another. Shareable says a borrow of a value may be held by several threads at once, so each reads it while the others do: the passes of a parallel each naming a value from outside the loop (What the body may do), the threads that hold an Arc, the closures of a parallel reduction. The compiler grants it from what a type holds, never from names, to every type that does not hold, directly or in a field, an element, a variant, a type argument or behind a borrow or an owner, one of these:

  • an owner that may be copied in a region that does not declare ThreadSafe (an Rc): two threads copying it write its count at once without an atomic operation;
  • a traced reference, Gc, whose copies are roots in a collector that is single-threaded. A read-only ActorGc[imm, T] is the exception, in the passes of a parallel each in its own actor's behaviour (In an actor's behaviour);
  • a reference that writes through a path others share: a &mut (Cone's &mut may be shared, so what holds one writes through a & of it), or an Arc[mut, T]. A closure that names a &mut variable is not Shareable, whatever its () takes, nor is a struct with a &mut field;
  • a reference to a trait or a callable that does not say what is behind it (&<Shape, &<fn(i32) i32, Uni[Shape]): the implementers are not known, so nothing says a borrow of the value may be shared. + Shareable, or + Sendable, vouches for it (below).

Raw pointers in a struct that is not generic are trusted, as the parallel-body check has always trusted them (nothing is followed behind one); a type holding ones it shares safely declares is Shareable; and an instance of a generic type is Shareable only where its type arguments are (List[Rc[T]], Dict[K, Rc[V]] and Option[Rc[T]] are not), whatever the collection keeps its items behind. A plain borrow, an Arc[imm, T] and an Arc[Mutex, T] of a Shareable T, an atomic and a number are Shareable. What the compiler grants Sendable it also grants Shareable, so an Arc[imm, T] of one may be read by several threads at once; a type declaring Sendable over raw pointers promises that of them, and declares Shareable as well where its borrows may be shared. A generic asks it of its argument as it asks Sendable: [F fn() + Shareable].

Saying what is behind a reference: Sendable, Shareable and ShapeKeeping#

A reference to a trait or a callable hides the type of the value behind it, so it is not Sendable or Shareable unless it says so. The markers follow the signature or the trait with a +, in either order:

fn work(f Uni[fn(x i32) i32 + Sendable]) i32 { f(1); }
fn read(f &<fn(x i32) i32 + Shareable, x i32) i32 { f(x); }
Uni[Shape + Sendable + Shareable]

The marker is a requirement on the closure or value put behind the reference: a value is made such a reference only if its type is each marker, and one that is not is refused where the reference is made, naming the variable it borrows or the owner it holds. An owner of a closure sent to a thread lists what it uses, so it has its own copy:

let k = 3;
let c = new Uni[fn(x i32) i32 + Sendable](fn(x i32) [k] i32 { x * k; });   // k is listed: its own copy
let th = thread.start(c, &work);                                          // th.join() is 3

A closure that holds an Rc is refused, and told what to hold instead:

let hf = new Rc[imm, Grid](h: 0.5);
let flock = new Uni[fn(x f32, z f32) f32 + Sendable](fn(x f32, z f32) [hf] f32 { x + z + hf.h; });

Error 1194: `Uni[fn(f32, f32) f32 + Sendable]` says the closure behind it is Sendable, and this closure is
not: it holds 'hf' (Rc[imm, Grid]), which is an owner that may be copied, and Rc does not declare ThreadSafe:
its copies could not be made and dropped on several threads at once. It may cross as a uni owner, which moves
it, or as an owner of a region declaring ThreadSafe, such as Arc. Its list holds 'hf' as its own: give it
something that can go there (an Arc where it is an Rc, a value copied where it is a borrow).

With hf an Arc[imm, Grid], the same closure goes to a thread. A reference with markers is a reference with fewer, never the other way: a Uni[fn() + Sendable] goes where a Uni[fn()] is wanted. A parallel each body may name a reference to a trait or a callable from outside the loop only if it carries one of the two markers.

A third marker, ShapeKeeping, says that a call through the reference reshapes nothing the caller holds a borrow into, so the caller's borrows of the elements of a collection survive the call (Shape changes). Unlike the other two, it is a fact of the methods the reference calls rather than of the type behind it: a closure or a struct whose method pushes to a list it reaches through a &mut is refused, naming the push:

fn visit(w &mut World, f &<fn(x &mut World) + ShapeKeeping) i64 { f(w); w.score; }

let n = visit(&mut w, fn (x &mut World) { x.score = x.score + 1; });   // Ok: writes a field
let m = visit(&mut w, fn (x &mut World) { x.items.push(5); });         // refused

Error 1500: `&<fn(&mut World) + ShapeKeeping` says a call through it keeps the shape of what the caller has
borrowed, and this closure calls `push` (line 26) on a `List` that it reaches through a shared mutable path (a
`&mut` parameter, a variable it borrows or holds by reference, or a global), which could be a collection the
caller holds a borrow into. Leave '+ ShapeKeeping' off, which ends the caller's borrows into a collection at the
call, or don't reshape it there.

Only Sendable, Shareable and ShapeKeeping may follow the +. A reference to a known type takes no marker (ask the type, T is Sendable), and joining two traits with their methods, &<Shape + Named, is not built.

A borrow that lasts the whole program#

A borrow of a local is refused everywhere Sendable is asked, because the local may be gone while the other thread still holds the borrow. A borrow that lasts the whole program, 'static (Lifetimes), has no such end: it is checked in no thread's scope, so it may cross threads and actors in either of two cases, and in no other:

  • it is imm or opaq, and what it reaches is safe for two threads to read at once, as the value of an Arc[imm, T] must be: no Rc and no Gc in it, no raw pointer, no borrow that is itself refused;
  • it is uni, and what it reaches is safe to move. A uni borrow moves, so one holder only has it.

An ro borrow never crosses, even of a global: ro only stops this holder from writing, and another holder (mut) may still change what it reads (Permissions). Nor does a mut one. Nor does a borrow of an invariant lifetime (&'=a T, a key): the lifetime is an arena's brand, and the arena dies when its owner drops it. A uni borrow of a named global is refused where it is made ("cannot obtain this permission"): any code reaches a global by name, so it is not unique. A uni borrow of an owner that nothing else can reach would be unique, and crosses; an owner leaked for the rest of the program, which would make one, is not built yet, but a signature may already take one: fn f(p &'static uni T).

A generic says that a type parameter may be such a borrow by bounding it, [A Sendable + 'static], as thread.start does, and each call is then checked to hand it only borrows of the whole program (Lifetime bounds); without the bound, Sendable refuses every borrow. An actor's initializer or behaviour takes one by writing it 'static, and what it reaches is asked the same way. So is a behaviour's answer: it may be &'static imm T, &'static opaq T or &'static uni T, or a struct holding one, under the same rule.

let table Array[u64, 3] = [1u64, 2u64, 3u64];
fn sum(t &imm Array[u64, 3]) u64 { (*t)[0] + (*t)[1] + (*t)[2]; }
fn peek(t &Array[u64, 3]) u64 { (*t)[0]; }

actor Reader {
  total u64;
  pub async do addTable(self, t &'static imm Array[u64, 3]) { total = total + (*t)[0]; }
}

let t = thread.start(&imm table, &sum);    // Ok: an imm borrow of a global; t.join() is 6
reader.addTable(&imm table);               // Ok: the same, to an actor

thread.start(&table, &peek);               // refused: an ro borrow
thread.start(&imm onTheStack, &sum);       // refused: a borrow of a local

Error 1194: start requires A is Sendable, and &ro Array[u64, 3] is not Sendable: it is a borrowed reference of
permission ro, and a borrow crosses threads only if it lives for the whole program and is let or opaq (any
number of threads may read what it reaches, and none writes) or uni (it moves, so one holder has it). 'ro' only
stops this holder writing: another holder could still change what it reaches. ...
Error 1249: The type parameter A is bounded by ''static' ('A + 'static'), so the borrow handed in for it must be
global: this one lives only as long as a value of this function.

Sharing immutable data: Arc#

Most data that several threads need is data nobody changes: a price list, a mesh, a table of settings. It is shared through the sync package's Arc region (import sync use Arc), whose count is atomic, as the program at the top shows: Arc[imm, T] owners may be copied and dropped on any thread, and the value is freed once, after the last (the Arc region). An Rc owner's count is not atomic, and it must stay on one thread.

Sharing what changes#

Threads that change one value together pay for it twice: in the synchronization each change needs (a lock, or an atomic instruction), and in the caches of every other core, which lose their copy whenever one core writes. Shared, changing data is also where deadlocks come from. So the fastest and safest design shares as little that changes as it can: it sends small messages, moves a uniquely owned value from one thread to the next rather than sharing it, and shares freely what nobody changes. The static permissions check all of that when the program is compiled, at no cost when it runs.

When threads truly must change one value, there are four ways, from the most used:

  • Give the value to an actor, and send it what to do, as the Guide's bakery gives the loaves to the stock room. One message at a time reaches it, so it needs no lock at all.
  • Guard it with a lock permission, Arc[Mutex, T] or Arc[Rwlock, T]: a borrow takes the lock, and its last use gives it back, so nothing reaches the value unlocked (Lock permissions, in Memory).
  • Make it an atomic value, a number, flag or pointer whose every change is indivisible (Atomic values).
  • Pass values between plain threads through a channel, a queue that any number of threads put into and one takes from (Channels).

Concurrent data structures beyond those, such as dictionaries that many threads change at once without a lock, are not built yet.

You can now tell whether a value may be sent or shared, read the refusal when it may not, and choose how threads share what changes. The Guide's actors waited for each other's answers with await; the next page says exactly what happens at that pause, and what a future is.