1-- The lock threads share state behind, and the process's one record of
2-- whether a thread has been started (D501, D502). It is a module of its
3-- own, beneath hosted/thread, so that the heap can take a lock without
4-- importing the thread facility that allocates its own stacks from the
5-- caller: hosted/heap imports this module, hosted/thread imports this
6-- module, and hosted/thread never imports the heap.
7--
8-- A lock is one u32 cell of core/atomic: free, taken, or taken with a
9-- thread waiting. Taking a free lock and giving one nobody waits for are
10-- one read-modify-write each; a thread that finds it taken sleeps in the
11-- system's wait on the cell's address, platform/posix's `wait_on`, and
12-- the thread that gives it wakes one waiter. This is the three-state
13-- lock of Drepper's "Futexes Are Tricky", on every hosted system alike.
14--
15-- On Cortex-M0 there is no lock: a context there excludes the interrupt
16-- handlers that share its state with platform/cortex_m's critical
17-- section, `disable_interrupts` to `restore_interrupts`, and that is its
18-- lock (D501). This module is hosted only.
19
20import core/atomic
21import platform/posix
22
23-- What a lock's cell holds.
24free: u32 = 0
25taken: u32 = 1
26contended: u32 = 2
27
28lock_value: type = struct
29 word: atomic.cell(u32)
30end lock_value
31
32--- A lock: one thread at a time holds it, between `take` and `give`. A
33--- zeroed lock is free, so module storage starts one `zeroed` and `new`
34--- makes one for a local or a field. It is not reentrant: a thread that
35--- takes a lock it holds waits for itself forever. It keeps no owner, so
36--- nothing stops a thread giving a lock another holds; do not. Waiting
37--- blocks the thread, so a fibre that holds a lock across a switch can
38--- hold every other fibre of its round that wants it. Share it by
39--- pointer, never by copy.
40public lock: type = lock_value
41
42--- A free lock.
43public new: () -> (made: lock) =
44 made = (word: atomic.new(free))
45end new
46
47--- Take `held`, waiting while another thread holds it. What the thread
48--- that gave it last did before giving it is visible after this returns.
49public take: (held: ptr mut lock) -> none =
50 word: ptr mut atomic.cell(u32) = addr held.val.word
51 mut seen: u32 = atomic.compare_exchange(word, free, taken)
52 return when seen == free
53 -- Say that someone waits, then sleep while that is still so: whoever
54 -- gives the lock sees `contended` and wakes a sleeper, and the one it
55 -- wakes takes the lock as contended, since it cannot know it was the
56 -- last.
57 if seen <> contended then
58 seen = atomic.exchange(word, contended)
59 end if
60 while seen <> free do
61 posix.wait_on(word, contended)
62 seen = atomic.exchange(word, contended)
63 end while
64end take
65
66--- Take `held` if no thread holds it, and say whether it did, without
67--- waiting.
68public take_if_free: (held: ptr mut lock) -> (took: bool) =
69 took = atomic.compare_exchange(addr held.val.word, free, taken) == free
70end take_if_free
71
72--- Give `held`, which this thread took, back, and wake one thread waiting
73--- for it, if any is. What this thread did while it held the lock is
74--- visible to the thread that takes it next.
75public give: (held: ptr mut lock) -> none =
76 word: ptr mut atomic.cell(u32) = addr held.val.word
77 if atomic.exchange(word, free) == contended then
78 posix.wake_one(word)
79 end if
80end give
81
82-- Whether the program has started a thread: zero until `note_start`, and
83-- one for the rest of the process. Relaxed, since the thread's creation
84-- orders what the program did before it, and nothing is ever unwritten.
85mut started: atomic.cell(u32) = zeroed
86
87--- Record that the program is about to start a thread. The thread
88--- facility calls it before it starts its first thread, on the thread that
89--- starts it, and the creation's happens-before edge gives the new thread
90--- the record. State that is shared only once there are threads, the
91--- heap's among it, then takes its lock; until then it skips it.
92public note_start: () -> none =
93 atomic.store_relaxed(addr started, 1)
94end note_start
95
96--- Whether `note_start` has been called: whether a thread other than the
97--- one the program started on may be running. A C thread calling into
98--- Landin under `--link=libc` is none of the program's and is not
99--- counted.
100public threads_started: () -> (yes: bool) =
101 yes = atomic.load_relaxed(addr started) <> 0
102end threads_started