1-- The switch, and the one provider of turns the library carries over it
2-- (D444, D450). `prepare` and `switch` are for whoever writes a provider
3-- that runs fibres on stacks of their own; `round` is one: a round of
4-- fixed turns over records the caller keeps, with the wait when nobody
5-- can run supplied by whoever builds on it. It is a module of its own,
6-- beneath core/fibre, so that a program that never switches a stack,
7-- one over `fibre.whole` or the blocking host, carries no switch and is
8-- admitted on every target, the switch's own included or not (D463).
9-- Priorities, timers and preemption are not here: an operating system's
10-- or an RTOS's scheduler is another provider of the same concepts.
11
12import core/fibre
13import core/mem
14
15-- What a prepared stack holds at its top: the record the fibre runs on,
16-- the record it resumes when its task has ended, and the task.
17starting: type = struct
18 record: usize
19 after: usize
20 work: any fibre.task
21end starting
22
23-- The least a prepared stack holds below its `starting`, in words: what
24-- `compiler.stack_prepare` lays at its top and the margin it keeps above
25-- its base for a failed check (D472), on every target, which is at most
26-- 976 bytes on a 64-bit one and 432 on a 32-bit one. A smaller stack
27-- is then out of memory here rather than a trap in the builtin. Every
28-- routine checks its own frame against the limit in its prologue
29-- (D471), so how deep a task may go is the stack's business, not this
30-- module's.
31least_prepared_words: usize = 128
32
33-- A fibre's first frame: run the task, mark the record ended, and resume
34-- the record the provider named. Nothing resumes it again.
35first_frame: (argument: usize) -> noreturn =
36 -- [0810]: the argument is the address of the stack's `starting`.
37 start: ptr mut starting = ptr(argument)
38 start.val.work.run()
39 record: ptr mut fibre.space = ptr(start.val.record)
40 after: ptr mut fibre.space = ptr(start.val.after)
41 record.val.status = 0
42 switch(record, after)
43 compiler.unreachable()
44end first_frame
45
46--- Lay out a first frame on `stack` that, when a switch resumes `record`,
47--- runs `work` to its end, makes the record's status zero and switches to
48--- `after`, which the provider keeps unfinished for as long as a fibre
49--- can end into it. A routine of the task, or of anything it calls, whose
50--- frame would go below the stack's limit traps `stack_exhausted` in its
51--- prologue (D451, D471), before it has written there. It fails
52--- `mem.out_of_memory` when `stack` is smaller than 128 words and the few
53--- words the first frame keeps at its top.
54public prepare: (escaping record: ptr mut fibre.space,
55 escaping stack: []mut u8, escaping work: any fibre.task,
56 escaping after: ptr mut fibre.space)
57 -> none ! mem.out_of_memory =
58 fail mem.out_of_memory when lenof stack == 0
59 low: usize = usize(addr stack[0])
60 high: usize = low + lenof stack
61 extent: usize = sizeof starting
62 least: usize = least_prepared_words * sizeof usize
63 fail mem.out_of_memory
64 when lenof stack < extent + alignof starting + least
65 mut place: usize = high - extent
66 place -= place % alignof starting
67 -- [0810]: the `starting` is the stack's top bytes; the first frame
68 -- is laid out below it.
69 start: ptr mut starting = ptr(place)
70 start.val = (record: usize(record), after: usize(after), work: work)
71 record.val.status = 1
72 record.val.saved = compiler.stack_prepare(stack[0..<place - low],
73 first_frame, place)
74end prepare
75
76--- Save the callee-saved registers, the frame pointer and the leaving
77--- stack's limit on the leaving stack, keep its stack pointer in
78--- `leaving`, and resume `entering`, returning when something switches
79--- back to `leaving` (D472). A switch is a full compiler memory boundary
80--- (D446). Pointers rather than two `inout` records, because both
81--- commonly sit in one table.
82public switch: (leaving: ptr mut fibre.space, entering: ptr mut fibre.space)
83 -> none =
84 compiler.stack_switch(addr leaving.val.saved, entering.val.saved)
85end switch
86
87--- What a round does when every fibre has yielded since anything last
88--- started or ended: wait for something to change. A device waits for an
89--- interrupt; an event-driven Io waits for its events; `spin` returns at
90--- once.
91public idler: type = concept (provider: type)
92 --- Wait until something a fibre waits for may have changed.
93 idle: (self: provider) -> none
94end idler
95
96--- An idler that returns at once, for a round whose fibres yield only
97--- while they have work to do, as a test's do. Make one `zeroed`.
98public spin: type = struct
99 reserved: u32
100end spin
101
102spin_idle: (self: spin) -> none =
103 _ = self
104end spin_idle
105
106spin is idler (idle: spin_idle)
107
108round_state: type = struct
109 home: fibre.space
110 current: usize
111 count: usize
112 quiet: usize
113 ended: usize
114end round_state
115
116--- Caller-owned state of a round: the record of the stack the round was
117--- made on, which entry runs, and its counts. Declare it `zeroed` and
118--- give it to `round_over`, which fills it; it must outlive the round.
119public round_space: type = round_state
120
121round_value: type = struct
122 state: ptr mut round_state
123 entries: []mut usize
124 when_idle: any idler
125end round_value
126
127--- A round of fixed turns, as a handle: copies share one round. Entry 0 is
128--- the stack the round was made on; the others are the fibres `start`
129--- prepared, each the record it was given, in the order they were
130--- started. `start` prepares and returns, and the fibre runs at its first
131--- turn. `yield` moves to the next unfinished entry after the current
132--- one, round the table, and after a whole round in which every
133--- unfinished entry yielded and nothing started or ended it calls the
134--- idler first. A provider of `fibre.turns`. Every entry may switch
135--- except `finished`.
136public round: type = round_value
137
138--- Fill `state` for a round over `entries`, the caller's table of the
139--- records it runs, and return its handle. The table holds entry 0 and
140--- one entry for each fibre that may be unfinished at once, so a group of
141--- `count` stacks needs `count + 1`; `start` fails `mem.out_of_memory`
142--- when it is full. It fails `mem.out_of_memory` when `entries` holds
143--- fewer than two. Keep `state`, `entries` and `when_idle` alive while the
144--- round is used.
145public round_over: (inout state: round_space, entries: []mut usize,
146 when_idle: any idler)
147 -> (handle: round from state, entries, when_idle)
148 ! mem.out_of_memory =
149 fail mem.out_of_memory when lenof entries < 2
150 state = (home: (saved: 0, status: 1), current: 0, count: 1,
151 quiet: 0, ended: 0)
152 entries[0] = usize(addr state.home)
153 handle = (state: addr state, entries: entries, when_idle: when_idle)
154end round_over
155
156-- The record entry `index` names.
157entry_record: (self: round, index: usize) -> (record: ptr mut fibre.space) =
158 -- [0810]: an entry is the address of a record the round was given.
159 record = ptr(self.entries[index])
160end entry_record
161
162-- Whether entry `index` holds a fibre that has not ended; entry 0, the
163-- stack the round was made on, never ends.
164running: (self: round, index: usize) -> (yes: bool) =
165 yes = false
166 return when self.entries[index] == 0
167 record: ptr mut fibre.space = entry_record(self, index)
168 yes = record.val.status <> 0
169end running
170
171-- Empty every entry whose fibre has ended since the last sweep, counting
172-- each, so a later start may take its place.
173sweep: (self: round) -> none =
174 state: ptr mut round_state = self.state
175 mut index: usize = 1
176 while index < state.val.count do
177 if self.entries[index] <> 0 and not running(self, index) then
178 self.entries[index] = 0
179 inc state.val.ended
180 state.val.quiet = 0
181 end if
182 inc index
183 end while
184end sweep
185
186-- How many entries hold a fibre that has not ended, entry 0 among them.
187unfinished: (self: round) -> (count: usize) =
188 state: ptr mut round_state = self.state
189 count = 0
190 mut index: usize = 0
191 while index < state.val.count do
192 if index == 0 or running(self, index) then
193 inc count
194 end if
195 inc index
196 end while
197end unfinished
198
199round_start: (self: round, escaping record: ptr mut fibre.space,
200 escaping stack: []mut u8, escaping work: any fibre.task)
201 -> none ! mem.out_of_memory =
202 state: ptr mut round_state = self.state
203 sweep(self)
204 mut index: usize = 1
205 while index < state.val.count and self.entries[index] <> 0 do
206 inc index
207 end while
208 if index == state.val.count then
209 fail mem.out_of_memory when index == lenof self.entries
210 inc state.val.count
211 end if
212 home: ptr mut fibre.space = entry_record(self, 0)
213 try prepare(record, stack, work, home)
214 self.entries[index] = usize(record)
215 state.val.quiet = 0
216end round_start
217
218round_finished: (self: round, record: fibre.space) -> (yes: bool) =
219 _ = self
220 yes = record.status == 0
221end round_finished
222
223round_yield: (self: round) -> none =
224 state: ptr mut round_state = self.state
225 sweep(self)
226 inc state.val.quiet
227 if state.val.quiet >= unfinished(self) then
228 state.val.quiet = 0
229 self.when_idle.idle()
230 end if
231 was: usize = state.val.current
232 mut next: usize = was
233 loop do
234 next = (next + 1) % state.val.count
235 break when next == was or next == 0 or running(self, next)
236 end loop
237 return when next == was
238 state.val.current = next
239 switch(entry_record(self, was), entry_record(self, next))
240 -- Whoever switched back here, a turn or a fibre that ended, this
241 -- entry runs again.
242 state.val.current = was
243end round_yield
244
245round_wait: (self: round) -> none =
246 state: ptr mut round_state = self.state
247 sweep(self)
248 loop do
249 mut others: usize = unfinished(self) - 1
250 if state.val.current <> 0 then
251 others -= 1
252 end if
253 break when others == 0
254 before: usize = state.val.ended
255 round_yield(self)
256 sweep(self)
257 break when state.val.ended <> before
258 end loop
259end round_wait
260
261round_value is fibre.scheduler (start: round_start, finished: round_finished,
262 wait: round_wait)
263round_value is fibre.turns (yield: round_yield)