Landin library reference discuss source

core/fibre/stacks

Shared: available on every enabled target.

The switch between stacks, and a round of fixed turns built on it.

Call What it does
stacks.round_over Fill the caller's stacks.round_space and return a stacks.round, a provider of fibre.turns over the caller's table of records.
stacks.prepare Lay out a fibre's first frame on a stack, for a provider of its own.
stacks.switch Save the leaving fibre's registers and resume another's.

A round's entry 0 is the stack it was made on; its other entries are the fibres it started, in the order they were started. start prepares and returns, and the fibre runs at its first turn. The table holds one entry more than the fibres that may be unfinished at once.

When every unfinished fibre has yielded since anything last started or ended, the round calls its stacks.idler before it goes on: a device waits for an interrupt there, and stacks.spin returns at once.

In a program that prepares a stack, every routine checks its frame against the stack it runs on before it reserves the frame, and traps stack_exhausted at its own site when the frame would go below the stack's limit, so a task that goes too deep stops at the call that would have overflowed, between switches as at them. The limit stands a margin above the stack's lowest byte, room for a failed check's handler: 640 bytes on x86-64 and arm64, 768 on RV64 and 384 on Cortex-M0, which --stack-report gives as margin_bytes. A switch carries each stack's limit with the registers it saves. A prepared stack is at least 128 words, beside the few words its first frame keeps at its top; size it from the report's depth of the task's routine and the margin.

Every target with a native backend admits this module, and synthetic-32 does not; a program over fibre.whole or the blocking host does not import it, and runs on every target.

Items

Concepts 1

Also on this page

idler

concept core/fibre/stacks/stacks.ldn:91 ↑ index 
public idler: type = concept (provider: type)

Wait until something a fibre waits for may have changed.

    idle: (self: provider) -> none
end idler

What a round does when every fibre has yielded since anything last started or ended: wait for something to change. A device waits for an interrupt; an event-driven Io waits for its events; spin returns at once.

round

type core/fibre/stacks/stacks.ldn:136 ↑ index 
public round: type = round_value

A round of fixed turns, as a handle: copies share one round. Entry 0 is the stack the round was made on; the others are the fibres start prepared, each the record it was given, in the order they were started. start prepares and returns, and the fibre runs at its first turn. yield moves to the next unfinished entry after the current one, round the table, and after a whole round in which every unfinished entry yielded and nothing started or ended it calls the idler first. A provider of fibre.turns. Every entry may switch except finished.

round_space

type core/fibre/stacks/stacks.ldn:119 ↑ index 
public round_space: type = round_state

Caller-owned state of a round: the record of the stack the round was made on, which entry runs, and its counts. Declare it zeroed and give it to round_over, which fills it; it must outlive the round.

spin

type core/fibre/stacks/stacks.ldn:98 ↑ index 
public spin: type = struct
    reserved: u32
end spin

An idler that returns at once, for a round whose fibres yield only while they have work to do, as a test's do. Make one zeroed.

prepare

function core/fibre/stacks/stacks.ldn:54 ↑ index 
public prepare: (escaping record: ptr mut fibre.space,
                 escaping stack: []mut u8, escaping work: any fibre.task,
                 escaping after: ptr mut fibre.space)
                -> none ! mem.out_of_memory

Lay out a first frame on stack that, when a switch resumes record, runs work to its end, makes the record's status zero and switches to after, which the provider keeps unfinished for as long as a fibre can end into it. A routine of the task, or of anything it calls, whose frame would go below the stack's limit traps stack_exhausted in its prologue (D451, D471), before it has written there. It fails mem.out_of_memory when stack is smaller than 128 words and the few words the first frame keeps at its top.

round_over

function core/fibre/stacks/stacks.ldn:145 ↑ index 
public round_over: (inout state: round_space, entries: []mut usize,
                    when_idle: any idler)
                   -> (handle: round from state, entries, when_idle)
                   ! mem.out_of_memory

Fill state for a round over entries, the caller's table of the records it runs, and return its handle. The table holds entry 0 and one entry for each fibre that may be unfinished at once, so a group of count stacks needs count + 1; start fails mem.out_of_memory when it is full. It fails mem.out_of_memory when entries holds fewer than two. Keep state, entries and when_idle alive while the round is used.

switch

function core/fibre/stacks/stacks.ldn:82 ↑ index 
public switch: (leaving: ptr mut fibre.space, entering: ptr mut fibre.space)
               -> none

Save the callee-saved registers, the frame pointer and the leaving stack's limit on the leaving stack, keep its stack pointer in leaving, and resume entering, returning when something switches back to leaving (D472). A switch is a full compiler memory boundary (D446). Pointers rather than two inout records, because both commonly sit in one table.

Example program

This complete program is one of the compiler's runtime tests. View source.

compiler/tests/fixtures/runtime/fibre-turns-interleave/main.ldn71 lines
--  D444: a group over a round of turns runs two tasks that yield in turn,
--  each letting the other run before it resumes, so their letters
--  interleave.  The round's home stack makes the group and goes on past
--  both admissions before either task has run, and its join takes turns
--  until both have ended.
import core/failure
import core/fibre
import core/fibre/stacks
import core/io
import hosted/system

mut order: [16]u8 = zeroed
mut steps: usize = 0

note: type = struct
    runs: any fibre.turns
    letter: u8
end note

note_of: (runs: any fibre.turns, letter: u8) -> (made: note from runs) =
    made = (runs: runs, letter: letter)
end note_of

mark: (letter: u8) -> none =
    order[steps] = letter
    steps += 1
end mark

--  Three letters, with a turn after each of the first two.
thrice: (inout state: note) -> none ! failure.reason =
    mark(state.letter)
    state.runs.yield()
    mark(state.letter)
    state.runs.yield()
    mark(state.letter)
end thrice

both: (runs: any fibre.turns) -> none ! failure.reason =
    mut stacks: [2 * 8192]u8 = zeroed
    mut tasks := try fibre.turns_over(runs, stacks, 2)
    defer fibre.join(tasks) else none
    a := note_of(runs, u8('a'))
    try fibre.admit(tasks, thrice, a)
    b := note_of(runs, u8('b'))
    try fibre.admit(tasks, thrice, b)
    mark(u8('h'))
    try fibre.join(tasks)
    mark(u8('j'))
end both

public main: () -> (code: i32) =
    code = 1
    host := system.new()
    mut state: stacks.round_space = zeroed
    mut entries: [3]usize = zeroed
    idler: stacks.spin = zeroed
    round := stacks.round_over(state, entries, any(addr idler)) else (problem)
        _ = problem
        return
    end
    both(any(addr round)) else (problem)
        _ = problem
        return
    end
    mut storage: [64]u8 = zeroed
    mut out := io.buffered_over(host, io.out(host), storage)
    io.put(out, order[0..<steps]) else none
    io.put(out, "\n") else none
    io.flush(out) else none
    code = 0
end main
in a terminalprints on standard output
$ refine compile main.ldn -o fibre-turns-interleave && ./fibre-turns-interleave
habababj