1-- Threads: tasks a routine starts as a group and waits for before it goes
2-- on, each on a thread of its own (D494). It is `core/fibre`'s group
3-- over threads: made over a `hosted/system` handle, a backing the caller
4-- lends and a count; `admit` copies a task's state onto a free stack and
5-- starts a thread that calls an ordinary routine with the copy; and
6-- `join`, which the routine making the group defers, waits for every one
7-- and fails with the first failure any had. Threads are no provider of
8-- `core/fibre`'s concepts (D446): a thread runs in parallel with the one
9-- that started it, so state they share is the atomic wrapper's or a
10-- lock's.
11--
12-- Each stack is cut from the backing and prepared with
13-- `compiler.stack_prepare`, so every routine of the task checks its frame
14-- against the thread's own limit and a task past its stack traps
15-- `stack_exhausted` (D495). The thread starts on a small area at the
16-- stack's top, the system's least, where the C library, when it starts
17-- the thread, keeps its own frames, and switches from there to the
18-- prepared stack; when the task ends it switches back and the thread
19-- ends (D517). Nothing here allocates and no guard page is mapped: the
20-- records, the states and the ledger are the backing's, behind
21-- integer-made pointers that stay inside this module [0810].
22
23import core/atomic
24import core/failure
25import core/mem
26import hosted/system
27import hosted/thread/lock
28import platform/posix
29
30-- What a thread runs: one entry, as `core/fibre`'s task, with no error
31-- set, since a thread's first frame has no caller to fail to.
32job: type = concept (job_type: type)
33 -- Run the task to its end.
34 run: (self: ptr mut job_type) -> none
35end job
36
37-- The record at a stack's base: the system's record of the thread, the
38-- start area's saved stack pointer while the task runs and the prepared
39-- stack's, the task, whether it has ended, which the thread writes, and
40-- whether a thread was started and not yet joined, and when, which only
41-- the group's owner reads and writes.
42slot: type = struct
43 thread: posix.thread
44 home: usize
45 prepared: usize
46 work: any job
47 ended: atomic.cell(u32)
48 running: u32
49 order: usize
50end slot
51
52-- The group's state shared with its threads, at the front of its backing
53-- so a task finds it wherever the group's handle has been copied to: the
54-- claim the first failure takes, that failure, and how many tasks the
55-- group has admitted, which orders its stacks by when each was started.
56ledger: type = struct
57 claimed: atomic.cell(u32)
58 failed: bool
59 problem: failure.reason
60 admitted: usize
61end ledger
62
63-- The alignment every stack and record is cut to, and the room kept at
64-- the backing's front for the ledger and at each stack's base for its
65-- record.
66alignment: usize = 16
67ledger_room: usize = (sizeof ledger + 15) / 16 * 16
68record_room: usize = (sizeof slot + 15) / 16 * 16
69
70-- The least a task's stack keeps below its state: room for the first
71-- frame `compiler.stack_prepare` lays, the limit's margin above the
72-- stack's base (D472) and a few calls of the task's own. A stack this
73-- small is a test's; a real one is as deep as the task's calls.
74least_task: usize = 4096
75
76group_value: type = struct
77 host: system.host
78 backing: []mut u8
79 front: usize
80 first: usize
81 size: usize
82 count: usize
83 area: usize
84end group_value
85
86--- Threads a routine starts and waits for: `count` equal stacks cut from
87--- a backing the caller lends, each with its record at its base and the
88--- area its thread starts on at its top. Made by `group_over`, given
89--- tasks by `admit`, and waited for by `join`, which the routine making
90--- the group defers as it would a region's release: a group must be
91--- joined before its backing goes, and nothing else makes sure it is.
92public group: type = group_value
93
94-- A value rounded down to `unit`.
95round_down: (value: usize, unit: usize) -> (result: usize) =
96 result = value - value % unit
97end round_down
98
99-- How far `value` is below the next multiple of `unit`.
100skip_to: (value: usize, unit: usize) -> (result: usize) =
101 result = (unit - value % unit) % unit
102end skip_to
103
104record_of: (g: group, index: usize) -> (record: ptr mut slot) =
105 -- [0810]: a record is the base of its stack, in the group's backing.
106 record = ptr(g.first + index * g.size)
107end record_of
108
109--- The least bytes one stack of a group takes on this system: its
110--- record, 4 KiB for the task's own stack and the area the thread starts
111--- on, the system's least: 2 KiB and the thread's storage on a static
112--- Linux program, glibc's PTHREAD_STACK_MIN, 16 KiB on x86-64 and RV64 and
113--- 128 KiB on arm64, under --link=libc, and 16 KiB on Darwin and FreeBSD,
114--- where Darwin cuts every stack in whole 16 KiB pages (D519).
115public least_stack: () -> (bytes: usize) =
116 unit: usize = posix.thread_start_alignment()
117 bytes = record_room + least_task + posix.thread_start_bytes()
118 bytes += skip_to(bytes, unit)
119end least_stack
120
121--- A group of threads over `host`, whose last-error cell keeps the errno
122--- of a start the system refused. It cuts `backing` into `count` equal
123--- stacks and fails `mem.out_of_memory` when they would be smaller than
124--- `least_stack()`, before any thread starts. The group borrows the
125--- handle and the backing for as long as it is used [0790].
126public group_over: (host: system.host, backing: []mut u8, count: usize)
127 -> (g: group from host, backing) ! mem.out_of_memory =
128 fail mem.out_of_memory when count == 0 or lenof backing == 0
129 unit: usize = posix.thread_start_alignment()
130 lowest: usize = usize(addr backing[0])
131 front: usize = lowest + skip_to(lowest, alignment)
132 first: usize = front + ledger_room + skip_to(front + ledger_room, unit)
133 fail mem.out_of_memory when first >= lowest + lenof backing
134 size: usize = round_down((lowest + lenof backing - first) / count, unit)
135 fail mem.out_of_memory when size < least_stack()
136 -- [0810]: the ledger and the records are the backing's bytes.
137 kept: ptr mut ledger = ptr(front)
138 kept.val = (claimed: atomic.new(u32(0)), failed: false,
139 problem: mem.out_of_memory, admitted: 0)
140 g = (host: host, backing: backing, front: front, first: first,
141 size: size, count: count, area: posix.thread_start_bytes())
142 mut index: usize = 0
143 while index < count do
144 record: ptr mut slot = record_of(g, index)
145 record.val.running = 0
146 record.val.ended = atomic.new(u32(0))
147 record.val.order = 0
148 inc index
149 end while
150end group_over
151
152-- What a task's stack holds at its top, below the area its thread starts
153-- on: the routine, the address of its group's ledger and the state the
154-- routine is called with.
155launch: type (state_type: type) = struct
156 work: (inout state: state_type) -> none ! failure.reason
157 kept: usize
158 state: state_type
159end launch
160
161-- Run the task; the first failure of the group's tasks takes the claim,
162-- and only it writes the failure, beside the count `admit` writes, whose
163-- bytes it never touches. The failure is read only after `join` has
164-- waited for every thread, whose end orders the write.
165launch_run: (state_type: type, self: ptr mut launch(state_type)) -> none =
166 self.val.work(self.val.state) else (problem)
167 kept: ptr mut ledger = ptr(self.val.kept)
168 if atomic.compare_exchange(addr kept.val.claimed, u32(0), u32(1))
169 == 0
170 then
171 kept.val.problem = problem
172 kept.val.failed = true
173 end if
174 end
175end launch_run
176
177(state_type: type) launch(state_type) is job (run: launch_run)
178
179-- The prepared stack's first frame: run the task, then go back to the
180-- area the thread started on, which ends the thread. Nothing resumes
181-- this frame again.
182first_frame: (argument: usize) -> noreturn =
183 -- [0810]: the argument is the address of the stack's record.
184 record: ptr mut slot = ptr(argument)
185 record.val.work.run()
186 compiler.stack_switch(addr record.val.prepared, record.val.home)
187 compiler.unreachable()
188end first_frame
189
190-- Written once by every thread `begin_thread` runs, on its start area.
191-- Darwin makes an image's thread storage at a thread's first access to
192-- any of it, in dyld's slow path, on whatever stack that access runs on,
193-- which no check or depth report counts; this write makes it on the C
194-- library's area before the prepared stack runs (D517).
195link(thread) mut begun: u8
196
197-- The thread's routine, on the area at its stack's top: make the thread's
198-- storage, switch to the prepared stack, and once the task has ended
199-- there and switched back, say so and end. Its prologue checks nothing a
200-- new thread has set: a thread's limit holds zero until the switch
201-- installs the prepared stack's (D497).
202extern(c) begin_thread: (argument: usize) -> (result: usize) =
203 -- [0810]: the argument is the address of the stack's record.
204 record: ptr mut slot = ptr(argument)
205 begun = 1
206 compiler.stack_switch(addr record.val.home, record.val.prepared)
207 atomic.store(addr record.val.ended, u32(1))
208 result = 0
209end begin_thread
210
211-- Wait for the thread on stack `index` to end, and mark the stack free.
212-- A join the system refuses is a defect of this module, since only a
213-- thread it started is joined, and once.
214finish: (g: group, index: usize) -> none =
215 record: ptr mut slot = record_of(g, index)
216 posix.join_thread(addr record.val.thread) else (problem)
217 _ = problem
218 compiler.unreachable()
219 end
220 record.val.running = 0
221end finish
222
223-- The index of a stack no thread runs on: a free one, or else one whose
224-- task has ended, or else the one whose thread started first, waited
225-- for until it ends.
226free_stack: (g: group) -> (index: usize) =
227 index = 0
228 while index < g.count do
229 free: ptr mut slot = record_of(g, index)
230 return when free.val.running == 0
231 inc index
232 end while
233 mut oldest: usize = 0
234 index = 0
235 while index < g.count do
236 record: ptr mut slot = record_of(g, index)
237 if atomic.load(addr record.val.ended) <> 0 then
238 finish(g, index)
239 return
240 end if
241 first: ptr mut slot = record_of(g, oldest)
242 if record.val.order < first.val.order then
243 oldest = index
244 end if
245 inc index
246 end while
247 finish(g, oldest)
248 index = oldest
249end free_stack
250
251--- Start a task: wait until one of the group's stacks is free, joining a
252--- thread whose task has ended, or else the one that started first;
253--- copy `state` onto the top of that stack's own part, as a call passes
254--- an argument; prepare the stack; and start a thread whose first frame
255--- calls `work` with the copy. The thread begins with every
256--- asynchronous signal blocked, and only a fault's own unblocked (D521). Because each task's state lives on its own stack, one group
257--- holds tasks of different state types. The thread runs in parallel with
258--- the caller: everything sequenced before `admit` happens before the
259--- task's first action, and nothing after it does unless the two
260--- synchronize themselves (D227).
261---
262--- `work`'s failure is kept by the group, the first one only, and `join`
263--- fails with it. A task with atoms of its own maps them to
264--- `failure.reason` before returning. `state` is kept in the group until
265--- the task ends, so what it refers to must outlive the group (D445).
266--- It fails `mem.out_of_memory` when the state leaves the stack less than
267--- 4 KiB for the task's own calls, and when the system refuses the thread,
268--- whose errno the group's handle then keeps for `system.last_errno`; a
269--- failed start starts nothing and leaves the stack free.
270public admit: (state_type: type, inout g: group,
271 work: (inout state: state_type) -> none ! failure.reason,
272 escaping into g state: state_type)
273 -> none ! mem.out_of_memory =
274 index: usize = free_stack(g)
275 record: ptr mut slot = record_of(g, index)
276 low: usize = usize(record) + record_room
277 area: usize = usize(record) + g.size - g.area
278 extent: usize = sizeof launch(state_type)
279 fail mem.out_of_memory when extent > area - low - least_task
280 mut place: usize = round_down(area - extent, alignment)
281 place -= place % alignof launch(state_type)
282 fail mem.out_of_memory when place < low + least_task
283 -- [0810]: the launch is the top bytes of the stack's own part, kept
284 -- until the task ends; the task's stack is the bytes below it, and
285 -- the thread's start area the bytes above.
286 copy: ptr mut launch(state_type) = ptr(place)
287 copy.val = (work: work, kept: g.front, state: state)
288 bottom: ptr mut [1]u8 = ptr(low)
289 mut stack: []mut u8 = bottom.val[0..<1]
290 top: ptr mut [1]u8 = ptr(area)
291 mut start: []mut u8 = top.val[0..<1]
292 unchecked begin
293 -- The bytes from `low` to the launch, and from the area to the
294 -- stack's end, are the backing's.
295 stack = stack[0..<place - low]
296 start = start[0..<g.area]
297 end unchecked
298 record.val.work = any(copy)
299 atomic.store_relaxed(addr record.val.ended, u32(0))
300 record.val.prepared = compiler.stack_prepare(stack, first_frame,
301 usize(record))
302 lock.note_start()
303 system.clear_errno(g.host)
304 posix.start_thread(start, addr record.val.thread, begin_thread,
305 usize(record)) else (problem)
306 system.record_errno(g.host, problem)
307 fail mem.out_of_memory
308 end
309 kept: ptr mut ledger = ptr(g.front)
310 kept.val.admitted += 1
311 record.val.order = kept.val.admitted
312 record.val.running = 1
313end admit
314
315--- Wait until every task admitted to `g` has ended, blocking the calling
316--- thread, whatever provider of fibres it runs under: a fibre that joins
317--- holds its round. Every thread's end happens before `join` returns
318--- (D227). The first failure any task had is `join`'s, handed on once;
319--- the rest ran to their own ends regardless, since nothing cancels a
320--- thread. A group may be joined again, and given more tasks after it is.
321public join: (inout g: group) -> none ! failure.reason =
322 mut index: usize = 0
323 while index < g.count do
324 record: ptr mut slot = record_of(g, index)
325 if record.val.running <> 0 then
326 finish(g, index)
327 end if
328 inc index
329 end while
330 kept: ptr mut ledger = ptr(g.front)
331 if kept.val.failed then
332 kept.val.failed = false
333 atomic.store_relaxed(addr kept.val.claimed, u32(0))
334 fail kept.val.problem
335 end if
336end join