1-- Fibres: tasks a routine starts as a group and waits for before it goes
2-- on (D444). Three layers, of which an application uses the last. The
3-- switch, `core/fibre/stacks`, is for whoever writes a provider that runs
4-- fibres on stacks of their own; the concepts `scheduler` and `turns` say
5-- what a provider is; and the group, here, is all an application calls.
6-- Fibres are cooperative: a fibre gives the core away only inside a call
7-- to an entry of the provider that runs it (D446). Nothing here
8-- allocates: the stacks are a backing the caller lends, and the records
9-- and states are kept on them, behind integer-made pointers that stay
10-- inside this module [0810].
11
12import core/failure
13import core/mem
14
15--- The caller's record of one fibre: where its stack pointer was saved,
16--- and whether a task runs on it. A group keeps these at the base of the
17--- stacks it cuts, so an application never declares one. `status` is zero
18--- when no task runs on the record, before the first start and after a
19--- task has ended; a provider makes it nonzero while one does. Where the
20--- stack ends is in the frames the switch saves, not here (D472).
21public space: type = struct
22 saved: usize
23 status: u8
24end space
25
26--- What a provider starts: one entry, no error set, since a fibre's first
27--- frame has no caller to fail to. An application does not write one; a
28--- group makes it from a routine and a state.
29public task: type = concept (task_type: type)
30 --- Run the task to its end.
31 run: (self: ptr mut task_type) -> none
32end task
33
34--- What runs fibres. A `scheduler` may run a task to its end inside
35--- `start`, before returning, and a program written against it must be
36--- right when every task does. `start` fails `mem.out_of_memory` when
37--- `stack` cannot hold the task's first frame. `finished` says whether
38--- the task last started on `record` has ended. `wait` returns once one
39--- of the provider's fibres has finished, or at once when none is running,
40--- which is how a group waits for a free stack. The provider runs at most
41--- one of its fibres at a time, and its fibres are one execution context
42--- (D446).
43public scheduler: type = concept (provider: type)
44 --- Start `work` on `record` and `stack`, or run it to its end.
45 start: (self: provider, escaping record: ptr mut space,
46 escaping stack: []mut u8, escaping work: any task)
47 -> none ! mem.out_of_memory
48 --- Whether the task last started on `record` has ended.
49 finished: (self: provider, record: space) -> (yes: bool)
50 --- Wait until one of the provider's fibres has finished.
51 wait: (self: provider) -> none
52end scheduler
53
54--- A `scheduler` whose fibres take turns. `yield` gives the core to
55--- another fibre of the provider that can run, and its contract is the
56--- promise: a fibre that yields lets every other unfinished fibre of the
57--- provider run before it resumes. A provider that runs every task to its
58--- end has nothing to yield to, and so does not provide `turns`; a program
59--- that needs turns asks for them with `turns_over`, and is refused there.
60public turns: type = concept (provider: type) is scheduler
61 --- Let every other unfinished fibre run, then go on.
62 yield: (self: provider) -> none
63end turns
64
65--- Give the core to the provider's other fibres, through `turns`
66--- evidence, for a provider the program holds as itself.
67public yield: (provider: type is turns, host: provider) -> none =
68 provider.yield(host)
69end yield
70
71--- A provider that has no second stack to give: it runs every task to its
72--- end, on the caller's stack, before `start` returns, and ignores the
73--- stack it is given. The blocking host, `system.host`, is another; a
74--- device that wants no switching is a third. Make one `zeroed`.
75public whole: type = struct
76 reserved: u32
77end whole
78
79whole_start: (self: whole, escaping record: ptr mut space,
80 escaping stack: []mut u8, escaping work: any task)
81 -> none ! mem.out_of_memory =
82 _ = self
83 _ = stack
84 record.val.status = 1
85 work.run()
86 record.val.status = 0
87end whole_start
88
89whole_finished: (self: whole, record: space) -> (yes: bool) =
90 _ = self
91 yes = record.status == 0
92end whole_finished
93
94-- Nothing is ever running when `start` has returned.
95whole_wait: (self: whole) -> none =
96 _ = self
97end whole_wait
98
99whole is scheduler (start: whole_start, finished: whole_finished,
100 wait: whole_wait)
101
102-- The group's one cell of shared state, kept at the front of its backing
103-- so a task finds it wherever the group's handle has been copied to.
104ledger: type = struct
105 failed: bool
106 problem: failure.reason
107end ledger
108
109-- `any turns` does not convert to `any scheduler`, so a group holds one
110-- of each and says which it runs on; the other is one of these, which
111-- runs nothing and is never called.
112unused: type = struct
113 reserved: u32
114end unused
115
116unused_start: (self: unused, escaping record: ptr mut space,
117 escaping stack: []mut u8, escaping work: any task)
118 -> none ! mem.out_of_memory =
119 _ = self
120 _ = record
121 _ = stack
122 _ = work
123end unused_start
124
125unused_finished: (self: unused, record: space) -> (yes: bool) =
126 _ = self
127 _ = record
128 yes = true
129end unused_finished
130
131unused_wait: (self: unused) -> none =
132 _ = self
133end unused_wait
134
135unused is scheduler (start: unused_start, finished: unused_finished,
136 wait: unused_wait)
137unused is turns (yield: unused_wait)
138
139nobody: unused = zeroed
140
141-- The alignment every stack and record is cut to, and the room kept at
142-- the backing's front for the ledger and at each stack's base for its
143-- record.
144alignment: usize = 16
145ledger_room: usize = 32
146record_room: usize = 32
147
148-- The least a stack keeps below a task's state for the task's own calls:
149-- room for the provider's first frame and a few calls. A stack this
150-- small is a test's; a real one is as deep as the routine's calls.
151least_stack: usize = 512
152
153group_value: type = struct
154 runs: any scheduler
155 turning: any turns
156 takes_turns: bool
157 backing: []mut u8
158 front: usize
159 size: usize
160 count: usize
161end group_value
162
163--- Fibres a routine starts and waits for: `count` equal stacks cut from
164--- a backing the caller lends, each with its record at its base, and the
165--- provider that runs them. Made by `group_over` or `turns_over`, given
166--- tasks by `admit`, and waited for by `join`, which the routine making
167--- the group defers as it would a region's release: a group must be
168--- joined before its backing goes, and nothing else makes sure it is.
169public group: type = group_value
170
171-- A value rounded down to the alignment stacks are cut to.
172round_down: (value: usize) -> (result: usize) =
173 result = value - value % alignment
174end round_down
175
176-- Where the ledger goes, the backing's first aligned byte, and the size
177-- of each of `count` stacks after it; it fails when they would be
178-- smaller than a stack's least.
179cut: (backing: []mut u8, count: usize)
180 -> (front: usize, size: usize) ! mem.out_of_memory =
181 fail mem.out_of_memory when count == 0 or lenof backing == 0
182 start: usize = usize(addr backing[0])
183 skip: usize = (alignment - start % alignment) % alignment
184 fail mem.out_of_memory when lenof backing < skip + ledger_room
185 front = start + skip
186 size = round_down((lenof backing - skip - ledger_room) / count)
187 fail mem.out_of_memory when size < record_room + least_stack
188 -- [0810]: the ledger and the records are the backing's bytes.
189 kept: ptr mut ledger = ptr(front)
190 kept.val = (failed: false, problem: mem.out_of_memory)
191 mut index: usize = 0
192 while index < count do
193 record: ptr mut space = ptr(front + ledger_room + index * size)
194 record.val = (saved: 0, status: 0)
195 inc index
196 end while
197end cut
198
199--- A group over a `scheduler`, which may run each task to its end as it
200--- is admitted. It cuts `backing` into `count` equal stacks and fails
201--- `mem.out_of_memory` when they would be smaller than a stack's least,
202--- 512 bytes after its record. The group borrows the provider and the
203--- backing for as long as it is used [0790].
204public group_over: (runs: any scheduler, backing: []mut u8, count: usize)
205 -> (g: group from runs, backing) ! mem.out_of_memory =
206 (front, size) := try cut(backing, count)
207 g = (runs: runs, turning: any(addr nobody), takes_turns: false,
208 backing: backing, front: front, size: size, count: count)
209end group_over
210
211--- A group over a provider of `turns`, whose tasks take turns: a task
212--- that yields, or waits in a call to the provider, lets the others run.
213--- A provider that cannot promise that is refused here, where the group
214--- is made, rather than when a task waits for ever.
215public turns_over: (runs: any turns, backing: []mut u8, count: usize)
216 -> (g: group from runs, backing) ! mem.out_of_memory =
217 (front, size) := try cut(backing, count)
218 g = (runs: any(addr nobody), turning: runs, takes_turns: true,
219 backing: backing, front: front, size: size, count: count)
220end turns_over
221
222-- The group's provider's three `scheduler` entries, through whichever
223-- of its two it runs on.
224start_on: (g: group, escaping record: ptr mut space,
225 escaping stack: []mut u8, escaping work: any task)
226 -> none ! mem.out_of_memory =
227 if g.takes_turns then
228 try g.turning.start(record, stack, work)
229 else
230 try g.runs.start(record, stack, work)
231 end if
232end start_on
233
234wait_on: (g: group) -> none =
235 if g.takes_turns then
236 g.turning.wait()
237 else
238 g.runs.wait()
239 end if
240end wait_on
241
242-- Whether the task last started on the group's stack `index` has ended.
243ended: (g: group, index: usize) -> (yes: bool) =
244 record: ptr mut space = record_of(g, index)
245 if g.takes_turns then
246 yes = g.turning.finished(record.val)
247 else
248 yes = g.runs.finished(record.val)
249 end if
250end ended
251
252-- What a task's stack holds at its top: the routine, the address of its
253-- group's ledger and the state the routine is called with.
254launch: type (state_type: type) = struct
255 work: (inout state: state_type) -> none ! failure.reason
256 kept: usize
257 state: state_type
258end launch
259
260launch_run: (state_type: type, self: ptr mut launch(state_type)) -> none =
261 self.val.work(self.val.state) else (problem)
262 kept: ptr mut ledger = ptr(self.val.kept)
263 if not kept.val.failed then
264 kept.val = (failed: true, problem: problem)
265 end if
266 end
267end launch_run
268
269(state_type: type) launch(state_type) is task (run: launch_run)
270
271record_of: (g: group, index: usize) -> (record: ptr mut space) =
272 -- [0810]: a record is the base of its stack, in the group's backing.
273 record = ptr(g.front + ledger_room + index * g.size)
274end record_of
275
276-- The index of a stack whose task has ended, waiting through the
277-- provider until one has.
278free_stack: (g: group) -> (index: usize) =
279 loop do
280 index = 0
281 while index < g.count do
282 return when ended(g, index)
283 inc index
284 end while
285 wait_on(g)
286 end loop
287end free_stack
288
289--- Start a task: wait, through the provider, until one of the group's
290--- stacks is free; copy `state` onto the top of that stack, as a call
291--- passes an argument; and start a fibre whose first frame calls `work`
292--- with the copy. Because each task's state lives on its own stack, one
293--- group holds tasks of different state types.
294---
295--- `work`'s failure is kept by the group, the first one only, and `join`
296--- fails with it. A task with atoms of its own maps them to
297--- `failure.reason` before returning. `state` is kept in the group until
298--- the task ends, so what it refers to must outlive the group (D445): a
299--- parameter of the routine making the group does, and so does a local
300--- declared before the group. It fails `mem.out_of_memory` when the state
301--- leaves the stack less than its least, 512 bytes, for its own calls.
302public admit: (state_type: type, inout g: group,
303 work: (inout state: state_type) -> none ! failure.reason,
304 escaping into g state: state_type)
305 -> none ! mem.out_of_memory =
306 index: usize = free_stack(g)
307 record: ptr mut space = record_of(g, index)
308 low: usize = usize(record) + record_room
309 high: usize = usize(record) + g.size
310 extent: usize = sizeof launch(state_type)
311 fail mem.out_of_memory when extent > high - low - least_stack
312 mut place: usize = round_down(high - extent)
313 place -= place % alignof launch(state_type)
314 fail mem.out_of_memory when place < low + least_stack
315 -- [0810]: the launch is the stack's top bytes, kept until the task
316 -- ends; its stack is the bytes below it.
317 copy: ptr mut launch(state_type) = ptr(place)
318 copy.val = (work: work, kept: g.front, state: state)
319 bottom: ptr mut [1]u8 = ptr(low)
320 mut stack: []mut u8 = bottom.val[0..<1]
321 unchecked begin
322 -- The bytes from `low` to the launch are the backing's.
323 stack = stack[0..<place - low]
324 end unchecked
325 try start_on(g, record, stack, any(copy))
326end admit
327
328--- Wait until every task admitted to `g` has ended. The first failure any
329--- of them had is `join`'s, handed on once; the rest ran to their own
330--- ends regardless, since nothing cancels a fibre (D449). A group may be
331--- joined again, and given more tasks after it is.
332public join: (inout g: group) -> none ! failure.reason =
333 mut index: usize = 0
334 while index < g.count do
335 if ended(g, index) then
336 inc index
337 else
338 wait_on(g)
339 end if
340 end while
341 kept: ptr mut ledger = ptr(g.front)
342 if kept.val.failed then
343 kept.val.failed = false
344 fail kept.val.problem
345 end if
346end join