kernel: enforce finite hart-bound execution budgets

8c203f662b025354f44836ade50f40aa92c3c802f443bb393cd484aa228a9692
Verified: make -C kernel check with the machine-capable emulator; all pass.
Alexis Sellier committed ago 1 parent e9333d80
kernel/Makefile +5 -3
3 3
HOST_EMU ?= $(EMU)
4 4
COMPILER := ../bin/radiance.rv64.dev
5 5
COMPILE := $(HOST_EMU) -memory-size=385024 -data-size=348160 -stack-size=512 -run $(COMPILER)
6 6
MODULES := core/fdt.rad core/platform.rad core/frames.rad core/abi.rad core/handles.rad \
7 7
	core/events.rad core/domains.rad core/resources.rad core/capabilities.rad \
8 -
	core/memory.rad core/state.rad core/pages.rad core/atomic.rad core/cpu.rad
9 -
CORE_ASM := arch/atomic.ras arch/context.ras
8 +
	core/memory.rad core/state.rad core/pages.rad core/atomic.rad core/cpu.rad \
9 +
	core/budgets.rad core/contexts.rad core/clock.rad core/budget_caps.rad
10 +
CORE_ASM := arch/atomic.ras arch/context.ras arch/clock.ras
10 11
CORE := -pkg core -mod core.rad $(addprefix -mod ,$(MODULES) $(CORE_ASM))
11 12
CHECK_MODULES := check/boot.rad check/fixture.rad check/frames.rad check/handles.rad \
12 -
	check/domains.rad check/capabilities.rad check/pages.rad check/events.rad
13 +
	check/domains.rad check/capabilities.rad check/pages.rad check/events.rad \
14 +
	check/budgets.rad check/budget_caps.rad
13 15
14 16
.PHONY: all check clean compiler-check
15 17
all: kernel.rv64
16 18
17 19
compiler-check:
kernel/NOTES.md +23 -3
1 1
# Kernel implementation decisions
2 2
3 3
The specification at https://radiant.computer/system/kernel takes precedence
4 4
for fixed call numbers, handle layout, rights, and object behavior. These notes
5 -
record the contracts established through step 11 of the 22-step plan.
5 +
record the contracts established through step 12 of the 22-step plan.
6 6
7 7
## Source and trust boundary
8 8
9 9
- Kernel mechanisms use freestanding Radiance; RAS owns machine entry, register
10 10
  state, atomics, and MMIO. Hosted checks exercise the same mechanism modules.
139 139
140 140
- On-demand layout resolution prepares imports in the nominal type's defining
141 141
  module, independent of sibling declaration order. By-value record and union
142 142
  cycles fail resolution; recursion through pointers is supported.
143 143
144 +
## Finite budgets and context identities
145 +
146 +
- Time is monotonic CLINT ticks at the FDT timebase frequency. A Budget retains
147 +
  a hardware hart, remaining ticks, and at most one bound context. Only boot
148 +
  provisions quantities; splitting and charging cannot increase their sum.
149 +
- Split requires Write, an unbound source, and available handle/object slots.
150 +
  It retains source rights and hart; a bound source returns Busy. A scheduler's
151 +
  unbound reserve must be distinct from its running budget.
152 +
- Bind requires Execute on both Budget and Domain, an Active domain, and a
153 +
  quiescent context. First binding fixes the context's hart. A binding retains
154 +
  its Budget object even when all handles to that object disappear.
155 +
- Context identities pack a nonzero u32 incarnation above a u32 table index.
156 +
  There are at most 512 contexts. Zero is invalid and exhausted incarnations
157 +
  never wrap. Possession of an identity alone grants no authority.
158 +
- Start creates a linear Running obligation and checked deadline; program the
159 +
  timer before U-mode entry. Architectural return consumes the obligation and
160 +
  charges the monotonic interval once, including transition overhead, saturating
161 +
  at zero. Empty, wrong-hart, incorrectly bound, or non-ready contexts cannot run.
162 +
- Creating a context or publishing an event supplies no ticks. Checks exercise
163 +
  conservation, failed operations, retained bindings, and actual CLINT preemption.
164 +
144 165
## Validation
145 166
146 167
Use the current machine-capable sibling emulator. Set `RAD_EMULATOR`, pass
147 168
`EMU` to the kernel Make invocation, or put `emulator` on PATH. The kernel build
148 169
checks compiler dependencies. From the repository root, run:
149 170
150 171
```sh
151 172
make -C kernel check
152 -
make std-test bin-test
153 173
```
154 174
155 -
Exercise defining-module imports, record/union cycle rejection, and pointer-recursive layout.
175 +
Exercise budget conservation and failed split/bind operations; preempt finite computation through CLINT and reject execution after exhaustion.
156 176
157 177
Run the context reservation probe with an emulator that retains LR/SC
158 178
reservations across traps. This checks the kernel's reservation invalidation.
kernel/arch/clock.ras added +21 -0
1 +
// Validated RV64 CLINT windows use native, naturally aligned 64-bit accesses.
2 +
.text;
3 +
.export @"core::clock::read";
4 +
@"core::clock::read"
5 +
	li     %t0    0xbff8;
6 +
	add    %a0    %a0    %t0;
7 +
	ld     %a0    0(%a0);
8 +
	ret;
9 +
.export @"core::clock::arm";
10 +
@"core::clock::arm"
11 +
	slli   %a1    %a1    3;
12 +
	add    %a0    %a0    %a1;
13 +
	li     %t0    0x4000;
14 +
	add    %a0    %a0    %t0;
15 +
	fence;
16 +
	sd     %a2    0(%a0);
17 +
	ret;
18 +
.export @"core::clock::interrupts";
19 +
@"core::clock::interrupts"
20 +
	csrw   mie    %a0;
21 +
	ret;
kernel/check.rad +4 -0
6 6
mod handles;
7 7
mod domains;
8 8
mod capabilities;
9 9
mod pages;
10 10
mod events;
11 +
mod budgets;
12 +
mod budget_caps;
11 13
12 14
/// Run the available kernel mechanism checks.
13 15
@default fn main() -> u32 {
14 16
    frames::run();
15 17
    boot::run();
16 18
    handles::run();
17 19
    domains::run();
18 20
    capabilities::run();
19 21
    pages::run();
20 22
    events::run();
23 +
    budgets::run();
24 +
    budget_caps::run();
21 25
    return 0;
22 26
}
kernel/check/budget_caps.rad added +90 -0
1 +
//! Budget authority conservation across binding, handle drop, and resource reuse.
2 +
3 +
use core::abi;
4 +
use core::budget_caps;
5 +
use core::budgets;
6 +
use core::capabilities;
7 +
use core::contexts;
8 +
use core::domains;
9 +
use core::frames;
10 +
use core::handles;
11 +
use core::memory;
12 +
use core::platform;
13 +
use core::resources;
14 +
use core::state;
15 +
16 +
/// Two independent protection domains for authority checks.
17 +
static DOMAINS: [domains::Domain; 2] = undefined;
18 +
/// Exactly enough resource slots for a reserve, a loan, and its replacement.
19 +
static OBJECTS: [resources::Slot; 3] = undefined;
20 +
/// One context that retains execution authority independently of handles.
21 +
static CONTEXTS: [contexts::Context; 1] = undefined;
22 +
/// Valid empty physical-memory accounting for this capability-only fixture.
23 +
static POOL: frames::Pool = undefined;
24 +
/// Empty-pool pin storage.
25 +
static PINS: [u16; 1] = undefined;
26 +
/// Empty-pool object claims.
27 +
static ASSIGNED: [bool; 1] = undefined;
28 +
/// Empty-pool persistent domain grants.
29 +
static GRANTS: [u64; 2] = undefined;
30 +
/// Shared kernel mechanism storage.
31 +
static KERNEL: state::State = undefined;
32 +
33 +
/// Reject a split without consuming any authority from the source.
34 +
fn reject(source: abi::Handle, expected: abi::Error) {
35 +
    let _handle = try budget_caps::split(&mut KERNEL, 0, source, 1) catch error {
36 +
        assert error == expected;
37 +
        return;
38 +
    };
39 +
    panic "reject: invalid budget split succeeded";
40 +
}
41 +
42 +
/// Reject binding authority to a context owned by a different target domain.
43 +
fn wrongTarget(source: abi::Handle, target: abi::Handle, context: u64) {
44 +
    try budget_caps::bind(&mut KERNEL, 0, source, target, context) catch error {
45 +
        assert error == abi::Error::Denied;
46 +
        return;
47 +
    };
48 +
    panic "wrongTarget: another domain context accepted authority";
49 +
}
50 +
51 +
/// Preserve charged execution after handles vanish and reclaim only after unbinding.
52 +
export fn run() {
53 +
    domains::init(&mut DOMAINS[..]);
54 +
    contexts::init(&mut CONTEXTS[0], 0);
55 +
    resources::init(&mut OBJECTS[..]);
56 +
    let mut machine: platform::Platform = undefined;
57 +
    set machine.memoryCount = 0;
58 +
    set machine.reservedCount = 0;
59 +
    try! frames::init(&mut POOL, &machine);
60 +
    let mut ram: memory::Memory = undefined;
61 +
    memory::init(&mut ram, &mut POOL, &mut PINS[..], &mut ASSIGNED[..], &mut GRANTS[..], 2);
62 +
    set KERNEL = state::State { domains: &mut DOMAINS[..], resources: &mut OBJECTS[..], contexts: &mut CONTEXTS[..], memory: ram };
63 +
    let rootHandle = domains::root(&mut DOMAINS[..], 0);
64 +
    let root = try! domains::resolve(&DOMAINS[..], 0, rootHandle, abi::CREATE);
65 +
    let child = try! domains::create(&mut DOMAINS[..], root, 0);
66 +
    let target = handles::install(&mut DOMAINS[0].handles, 2, child, abi::DOMAIN_RIGHTS);
67 +
    set DOMAINS[0].state = domains::Lifecycle::Active;
68 +
    set DOMAINS[child.index].state = domains::Lifecycle::Active;
69 +
    try! contexts::prepare(&mut CONTEXTS[0], child, 0, 0, DOMAINS[child.index].env);
70 +
    let id = contexts::identity(&CONTEXTS[0]);
71 +
    let reserve = try! resources::create(&mut OBJECTS[..], resources::Value::Budget(try! budgets::init(0, 1000)));
72 +
    resources::retain(&mut OBJECTS[..], reserve);
73 +
    let source = handles::install(&mut DOMAINS[0].handles, 3, reserve, abi::READ | abi::WRITE | abi::EXECUTE | abi::GRANT | abi::TRANSFER);
74 +
    let loan = try! budget_caps::split(&mut KERNEL, 0, source, 400);
75 +
    wrongTarget(loan, rootHandle, id);
76 +
    try! budget_caps::bind(&mut KERNEL, 0, loan, target, id);
77 +
    reject(loan, abi::Error::Busy);
78 +
    let received = try! capabilities::grant(&mut KERNEL, 0, loan, target, abi::EXECUTE as u64);
79 +
    try! capabilities::drop(&mut KERNEL, 0, loan);
80 +
    try! capabilities::drop(&mut KERNEL, child.index, received);
81 +
    let retained = budget_caps::value(&mut KERNEL, CONTEXTS[0].budget);
82 +
    let running = try! contexts::begin(&mut CONTEXTS[0], retained, 1, 0);
83 +
    assert contexts::finish(&mut CONTEXTS[0], retained, running, 101) == 300;
84 +
    let replacement = try! budget_caps::split(&mut KERNEL, 0, source, 100);
85 +
    reject(source, abi::Error::Exhausted);
86 +
    assert budget_caps::value(&mut KERNEL, reserve).remaining == 500;
87 +
    try! budget_caps::bind(&mut KERNEL, 0, replacement, target, id);
88 +
    let _reused = try! budget_caps::split(&mut KERNEL, 0, source, 1);
89 +
    assert budget_caps::value(&mut KERNEL, reserve).remaining == 499;
90 +
}
kernel/check/budgets.rad added +91 -0
1 +
//! Conservation, execution binding, exhaustion, and non-wrapping deadline checks.
2 +
3 +
use core::abi;
4 +
use core::budgets;
5 +
use core::platform;
6 +
7 +
/// Observe provisioning failures without accepting an unexpected success.
8 +
fn initError(hart: u32, ticks: u64) -> abi::Error {
9 +
    let _budget = try budgets::init(hart, ticks) catch error { return error; };
10 +
    return abi::Error::Ok;
11 +
}
12 +
13 +
/// Observe split failures while retaining the source for subsequent execution.
14 +
fn splitError(source: *mut budgets::Budget, ticks: u64) -> abi::Error {
15 +
    let _budget = try budgets::split(source, ticks) catch error { return error; };
16 +
    return abi::Error::Ok;
17 +
}
18 +
19 +
/// Observe binding failures while retaining the previous execution authority.
20 +
fn bindError(budget: *mut budgets::Budget, context: u64, hart: u32) -> abi::Error {
21 +
    try budgets::bind(budget, context, hart) catch error { return error; };
22 +
    return abi::Error::Ok;
23 +
}
24 +
25 +
/// Observe deadline failures without modifying the budget.
26 +
fn deadlineError(budget: *budgets::Budget, now: u64) -> abi::Error {
27 +
    let _deadline = try budgets::deadline(budget, now) catch error { return error; };
28 +
    return abi::Error::Ok;
29 +
}
30 +
31 +
/// Check that splitting, failed mutation, and context reuse cannot mint ticks.
32 +
export fn run() {
33 +
    let first: u64 = 0x100000007;
34 +
    let next: u64 = 0x200000007;
35 +
    assert initError(platform::MAX_HARTS, 1) == abi::Error::InvalidArg;
36 +
    assert initError(0, 0) == abi::Error::InvalidArg;
37 +
38 +
    let mut source = try! budgets::init(0, 1000);
39 +
    let mut child = try! budgets::split(&mut source, 400);
40 +
    assert splitError(&mut source, 0) == abi::Error::InvalidArg;
41 +
    assert splitError(&mut source, 601) == abi::Error::Exhausted;
42 +
    assert bindError(&mut source, 0, 0) == abi::Error::InvalidArg;
43 +
    assert bindError(&mut source, first, platform::MAX_HARTS) == abi::Error::InvalidArg;
44 +
    assert bindError(&mut source, first, 1) == abi::Error::Denied;
45 +
    assert bindError(&mut child, next, 1) == abi::Error::Denied;
46 +
    try! budgets::bind(&mut source, first, 0);
47 +
    try! budgets::bind(&mut child, next, 0);
48 +
    assert try! budgets::deadline(&source, 100) == 700;
49 +
    assert try! budgets::deadline(&child, 100) == 500;
50 +
51 +
    assert splitError(&mut source, 1) == abi::Error::Busy;
52 +
    assert bindError(&mut source, first, 0) == abi::Error::Busy;
53 +
    assert bindError(&mut source, next, 0) == abi::Error::Busy;
54 +
    assert bindError(&mut source, next, 1) == abi::Error::Denied;
55 +
    assert budgets::charge(&mut source, first, 150) == 450;
56 +
    budgets::unbind(&mut source, first);
57 +
    try! budgets::bind(&mut source, next, 0);
58 +
    assert budgets::charge(&mut source, next, 200) == 250;
59 +
    assert budgets::charge(&mut child, next, 399) == 1;
60 +
    assert source.remaining + child.remaining + 150 + 200 + 399 == 1000;
61 +
    assert budgets::charge(&mut source, next, 0) == 250;
62 +
    assert budgets::charge(&mut source, next, 250) == 0;
63 +
    assert deadlineError(&source, 0) == abi::Error::Exhausted;
64 +
    assert budgets::charge(&mut source, next, 1) == 0;
65 +
    budgets::unbind(&mut source, next);
66 +
    assert bindError(&mut source, first, 0) == abi::Error::Exhausted;
67 +
    assert splitError(&mut source, 1) == abi::Error::Exhausted;
68 +
    assert budgets::charge(&mut child, next, 0xffffffffffffffff) == 0;
69 +
    budgets::unbind(&mut child, next);
70 +
    assert bindError(&mut child, first, 0) == abi::Error::Exhausted;
71 +
72 +
    // Moving the complete balance leaves execution authority only in the child.
73 +
    let mut reserve = try! budgets::init(1, 50);
74 +
    let mut entire = try! budgets::split(&mut reserve, 50);
75 +
    assert bindError(&mut reserve, first, 1) == abi::Error::Exhausted;
76 +
    assert bindError(&mut entire, first, 0) == abi::Error::Denied;
77 +
    try! budgets::bind(&mut entire, first, 1);
78 +
    assert budgets::charge(&mut entire, first, 50) == 0;
79 +
    budgets::unbind(&mut entire, first);
80 +
81 +
    // Exact maximum deadlines are valid; an overflow failure cannot consume ticks.
82 +
    let mut limit = try! budgets::init(0, 0xffffffffffffffff);
83 +
    assert try! budgets::deadline(&limit, 0) == 0xffffffffffffffff;
84 +
    assert deadlineError(&limit, 1) == abi::Error::InvalidArg;
85 +
    try! budgets::bind(&mut limit, first, 0);
86 +
    assert budgets::charge(&mut limit, first, 1) == 0xfffffffffffffffe;
87 +
    assert try! budgets::deadline(&limit, 1) == 0xffffffffffffffff;
88 +
    assert deadlineError(&limit, 2) == abi::Error::InvalidArg;
89 +
    assert budgets::charge(&mut limit, first, 0xfffffffffffffffe) == 0;
90 +
    budgets::unbind(&mut limit, first);
91 +
}
kernel/check/capabilities.rad +5 -1
1 1
//! Capability mutation contracts across independent domain tables.
2 2
3 3
use core::abi;
4 4
use core::capabilities;
5 +
use core::contexts;
5 6
use core::domains;
6 7
use core::fdt;
7 8
use core::handles;
8 9
use core::resources;
9 10
use core::frames;
13 14
14 15
/// Domain storage for capability transactions.
15 16
static DOMAINS: [domains::Domain; 3] = undefined;
16 17
/// Physical resources used by the transactions.
17 18
static OBJECTS: [resources::Slot; 4] = undefined;
19 +
/// Context storage for the shared kernel state.
20 +
static CONTEXTS: [contexts::Context; 1] = undefined;
18 21
/// Empty RAM pool for device-only capability transactions.
19 22
static POOL: frames::Pool = undefined;
20 23
/// Frame pin backing storage.
21 24
static PINS: [u16; 1] = undefined;
22 25
/// Frame object backing storage.
36 39
37 40
/// Check attenuation, non-delegable queues, unique IRQs, and failed moves.
38 41
export fn run() {
39 42
    domains::init(&mut DOMAINS[..]);
40 43
    resources::init(&mut OBJECTS[..]);
44 +
    contexts::init(&mut CONTEXTS[0], 0);
41 45
    let mut machine: platform::Platform = undefined;
42 46
    set machine.memoryCount = 0;
43 47
    set machine.reservedCount = 0;
44 48
    try! frames::init(&mut POOL, &machine);
45 49
    let mut ram: memory::Memory = undefined;
46 50
    memory::init(&mut ram, &mut POOL, &mut PINS[..], &mut ASSIGNED[..], &mut GRANTS[..], 3);
47 -
    set KERNEL = state::State { domains: &mut DOMAINS[..], resources: &mut OBJECTS[..], memory: ram };
51 +
    set KERNEL = state::State { domains: &mut DOMAINS[..], resources: &mut OBJECTS[..], contexts: &mut CONTEXTS[..], memory: ram };
48 52
    let rootHandle = domains::root(&mut DOMAINS[..], 0);
49 53
    let root = try! domains::resolve(&DOMAINS[..], 0, rootHandle, abi::CREATE);
50 54
    let child = try! domains::create(&mut DOMAINS[..], root, 1);
51 55
    let childHandle = handles::install(&mut DOMAINS[0].handles, 2, child, abi::DOMAIN_RIGHTS);
52 56
    let device = try! resources::create(&mut OBJECTS[..], resources::Value::Device(fdt::Range { base: 0x10000000, size: 256 }));
kernel/check/context.ras +7 -0
64 64
	csrr   %a0    mstatus;
65 65
	ld     %a0    1(%zero);
66 66
	li     %t0    0x40000000;
67 67
	sd     %zero  0(%t0);
68 68
	ebreak;
69 +
.export @"context::loopEntry";
70 +
@"context::loopEntry"
71 +
	la     %a0    @loop;
72 +
	ret;
73 +
@loop
74 +
	addi   %a0    %a0    1;
75 +
	j      @loop;
69 76
70 77
// Return the two user entries; Frame initialization supplies shared memory in a0.
71 78
.export @"context::reservationEntry";
72 79
@"context::reservationEntry"
73 80
	la     %a0    @reservation;
kernel/check/pages.rad +5 -1
1 1
//! Page authority, split exclusivity, and persistent recipient lifetime checks.
2 2
3 3
use core::abi;
4 4
use core::capabilities;
5 +
use core::contexts;
5 6
use core::domains;
6 7
use core::fdt;
7 8
use core::frames;
8 9
use core::handles;
9 10
use core::memory;
16 17
static RAM: [u8; 16 * frames::PAGE_SIZE] = undefined;
17 18
/// Domain storage for allocator and recipient authority.
18 19
static DOMAINS: [domains::Domain; 3] = undefined;
19 20
/// Physical Page object slots.
20 21
static OBJECTS: [resources::Slot; 8] = undefined;
22 +
/// Context storage for the shared kernel state.
23 +
static CONTEXTS: [contexts::Context; 1] = undefined;
21 24
/// Frame availability metadata.
22 25
static POOL: frames::Pool = undefined;
23 26
/// Recipient pin counts.
24 27
static PINS: [u16; 16] = undefined;
25 28
/// Live Page claims on each frame.
44 47
    try! frames::init(&mut POOL, &machine);
45 48
    let mut ram: memory::Memory = undefined;
46 49
    memory::init(&mut ram, &mut POOL, &mut PINS[..], &mut ASSIGNED[..], &mut GRANTS[..], 3);
47 50
    domains::init(&mut DOMAINS[..]);
48 51
    resources::init(&mut OBJECTS[..]);
49 -
    set KERNEL = state::State { domains: &mut DOMAINS[..], resources: &mut OBJECTS[..], memory: ram };
52 +
    contexts::init(&mut CONTEXTS[0], 0);
53 +
    set KERNEL = state::State { domains: &mut DOMAINS[..], resources: &mut OBJECTS[..], contexts: &mut CONTEXTS[..], memory: ram };
50 54
    let rootHandle = domains::root(&mut DOMAINS[..], 0);
51 55
    let root = try! domains::resolve(&DOMAINS[..], 0, rootHandle, abi::CREATE);
52 56
    let child = try! domains::create(&mut DOMAINS[..], root, 1);
53 57
    let childHandle = handles::install(&mut DOMAINS[0].handles, 2, child, abi::DOMAIN_RIGHTS);
54 58
    let left = try! pages::allocate(&mut KERNEL, 0, abi::Handle { bits: 0 }, 4, clear);
kernel/context.rad +34 -0
1 1
//! Machine-mode regression for real user traps and protected kernel resumption.
2 2
3 3
use core::abi;
4 4
use core::atomic;
5 5
use core::cpu;
6 +
use core::budgets;
7 +
use core::clock;
8 +
use core::contexts;
6 9
7 10
/// Address of the fixed user register and fault probe.
8 11
fn entry() -> u64;
9 12
/// Instruction address of the first user ecall.
10 13
fn checkpoint() -> u64;
11 14
/// Arm hart zero's machine timer for the idle-path check.
12 15
unsafe fn alarm();
13 16
/// Disable the machine timer after its interrupt.
14 17
unsafe fn cancel();
18 +
/// Address of a user computation that can stop only through preemption.
19 +
fn loopEntry() -> u64;
15 20
/// Address of the user probe that attempts SC after another frame runs.
16 21
fn reservationEntry() -> u64;
17 22
/// Address of the user probe that replaces the hart's LR reservation.
18 23
fn reservationPeerEntry() -> u64;
19 24
36 41
    assert first.cause == 8 and (first.status & 0x1800) == 0;
37 42
    assert first.registers[12] <> 0;
38 43
    assert shared == 1;
39 44
}
40 45
46 +
/// Refuse user entry when the retained authority has no ticks left.
47 +
fn exhausted(context: *mut contexts::Context, budget: *mut budgets::Budget, now: u64) {
48 +
    let running = try contexts::begin(context, budget, now, 0) catch error {
49 +
        assert error == abi::Error::Exhausted;
50 +
        return;
51 +
    };
52 +
    let _remaining = contexts::finish(context, budget, running, now);
53 +
    panic "exhausted: execution began without budget";
54 +
}
55 +
41 56
/// Check saved user state even when user sp, gp, tp, and ra are unusable.
42 57
@default unsafe fn main() -> u32 {
43 58
    let mut word: u32 = 0xffffffff;
44 59
    assert atomic::exchange(&mut word, 123) == 0xffffffff;
45 60
    assert atomic::exchange(&mut word, 0) == 123;
81 96
    alarm();
82 97
    cpu::idle(&mut frame);
83 98
    cancel();
84 99
    assert frame.cause == 0x8000000000000007;
85 100
    assert (frame.status & 0x1800) == 0x1800;
101 +
102 +
    let mut context: contexts::Context = undefined;
103 +
    contexts::init(&mut context, 0);
104 +
    try! contexts::prepare(&mut context, abi::Object { kind: abi::Kind::Domain, index: 0, epoch: 1 }, loopEntry(), 0, context.env);
105 +
    set context.frame.registers[10] = 0;
106 +
    let mut budget = try! budgets::init(0, 1000);
107 +
    try! budgets::bind(&mut budget, contexts::identity(&context), 0);
108 +
    set context.hart = 0;
109 +
    let running = try! contexts::begin(&mut context, &budget, clock::read(0x02000000), 0);
110 +
    clock::arm(0x02000000, 0, context.deadline);
111 +
    clock::interrupts(128);
112 +
    cpu::enter(&mut context.frame);
113 +
    let stopped = clock::read(0x02000000);
114 +
    clock::interrupts(0);
115 +
    clock::arm(0x02000000, 0, 0xffffffffffffffff);
116 +
    assert contexts::finish(&mut context, &mut budget, running, stopped) == 0;
117 +
    assert context.frame.cause == 0x8000000000000007;
118 +
    assert context.frame.registers[10] > 0 and context.frame.registers[10] <= 500;
119 +
    exhausted(&mut context, &mut budget, stopped);
86 120
    return 0;
87 121
}
kernel/core.rad +4 -0
12 12
export mod memory;
13 13
export mod state;
14 14
export mod pages;
15 15
export mod atomic;
16 16
export mod cpu;
17 +
export mod budgets;
18 +
export mod contexts;
19 +
export mod clock;
20 +
export mod budget_caps;
kernel/core/budget_caps.rad added +72 -0
1 +
//! Capability-mediated budget splitting and exclusive context binding.
2 +
3 +
use core::abi;
4 +
use core::budgets;
5 +
use core::capabilities;
6 +
use core::contexts;
7 +
use core::domains;
8 +
use core::handles;
9 +
use core::resources;
10 +
use core::state;
11 +
12 +
/// Borrow the accounting value of a retained, live Budget resource.
13 +
export fn value(kernel: *mut state::State, object: abi::Object) -> *mut budgets::Budget {
14 +
    assert object.kind == abi::Kind::Budget;
15 +
    let slot = &mut kernel.resources[object.index];
16 +
    assert slot.epoch == object.epoch and slot.references > 0;
17 +
    match &mut slot.value {
18 +
        case resources::Value::Budget(budget) => return budget,
19 +
        else => panic "value: budget identity does not name accounting state",
20 +
    }
21 +
}
22 +
23 +
/// Move a finite quantity into a fresh handle after all slot-capacity checks.
24 +
export fn split(kernel: *mut state::State, caller: u32, source: abi::Handle, ticks: u64) -> abi::Handle throws (abi::Error) {
25 +
    let entry = try capabilities::lookup(kernel, caller, source);
26 +
    if entry.object.kind <> abi::Kind::Budget { throw abi::Error::BadHandle; }
27 +
    if entry.rights & abi::WRITE == 0 { throw abi::Error::Denied; }
28 +
    let handleSlot = try handles::vacant(&kernel.domains[caller].handles);
29 +
    let objectSlot = try resources::vacant(kernel.resources);
30 +
    let child = try budgets::split(value(kernel, entry.object), ticks);
31 +
    let object = resources::install(kernel.resources, objectSlot, resources::Value::Budget(child));
32 +
    resources::retain(kernel.resources, object);
33 +
    return handles::install(&mut kernel.domains[caller].handles, handleSlot, object, entry.rights);
34 +
}
35 +
36 +
/// Bind execution authority to an authorized, quiescent context on the same hart.
37 +
/// A binding retains the Budget even if its last user handle is dropped.
38 +
export fn bind(kernel: *mut state::State, caller: u32, source: abi::Handle, target: abi::Handle, id: u64) throws (abi::Error) {
39 +
    let entry = try capabilities::lookup(kernel, caller, source);
40 +
    if entry.object.kind <> abi::Kind::Budget { throw abi::Error::BadHandle; }
41 +
    if entry.rights & abi::EXECUTE == 0 { throw abi::Error::Denied; }
42 +
    let domain = try domains::resolve(kernel.domains, caller, target, abi::EXECUTE);
43 +
    let index = try contexts::resolve(kernel.contexts, id);
44 +
    let context = &mut kernel.contexts[index];
45 +
    if context.owner.index <> domain.index or context.owner.epoch <> domain.epoch {
46 +
        throw abi::Error::Denied;
47 +
    }
48 +
    if kernel.domains[domain.index].state <> domains::Lifecycle::Active {
49 +
        throw abi::Error::InvalidArg;
50 +
    }
51 +
    if context.status == contexts::Status::Running { throw abi::Error::Busy; }
52 +
    let budget = value(kernel, entry.object);
53 +
    if context.hart <> contexts::NO_HART and context.hart <> budget.hart { throw abi::Error::Denied; }
54 +
    try budgets::bind(budget, id, budget.hart);
55 +
    if context.budget.kind == abi::Kind::Budget {
56 +
        budgets::unbind(value(kernel, context.budget), id);
57 +
        let _released = resources::release(kernel.resources, context.budget);
58 +
    }
59 +
    resources::retain(kernel.resources, entry.object);
60 +
    set context.budget = entry.object;
61 +
    set context.hart = budget.hart;
62 +
}
63 +
64 +
/// Release a quiescent context's retained binding after its last interval is charged.
65 +
export fn unbind(kernel: *mut state::State, context: *mut contexts::Context) {
66 +
    assert context.status <> contexts::Status::Running;
67 +
    if context.budget.kind == abi::Kind::Budget {
68 +
        budgets::unbind(value(kernel, context.budget), contexts::identity(context));
69 +
        let _released = resources::release(kernel.resources, context.budget);
70 +
        set context.budget = domains::none();
71 +
    }
72 +
}
kernel/core/budgets.rad added +71 -0
1 +
//! Finite, hart-local execution authority measured in monotonic CLINT ticks.
2 +
3 +
use core::abi;
4 +
use core::platform;
5 +
6 +
/// Kernel-owned accounting value; copies must not create independent authority.
7 +
/// Callers serialize access and validate live, generation-qualified identities.
8 +
export record Budget: Copy {
9 +
    /// Hardware hart on which this authority can execute.
10 +
    hart: u32,
11 +
    /// Unconsumed CLINT ticks; only splitting and charging can reduce them.
12 +
    remaining: u64,
13 +
    /// Bound context incarnation, or zero while available for binding or split.
14 +
    context: u64,
15 +
}
16 +
17 +
/// Create boot-provisioned authority; reject unsupported harts and zero ticks.
18 +
/// The caller also verifies that the hart is present in the boot topology.
19 +
export fn init(hart: u32, ticks: u64) -> Budget throws (abi::Error) {
20 +
    if hart >= platform::MAX_HARTS or ticks == 0 { throw abi::Error::InvalidArg; }
21 +
    return Budget { hart, remaining: ticks, context: 0 };
22 +
}
23 +
24 +
/// Move ticks into an unbound child on the same hart without replenishment.
25 +
/// Busy forbids changing in-flight accounting; every failure preserves source.
26 +
export fn split(source: *mut Budget, ticks: u64) -> Budget throws (abi::Error) {
27 +
    if source.context <> 0 { throw abi::Error::Busy; }
28 +
    if ticks == 0 { throw abi::Error::InvalidArg; }
29 +
    if ticks > source.remaining { throw abi::Error::Exhausted; }
30 +
    set source.remaining -= ticks;
31 +
    return Budget { hart: source.hart, remaining: ticks, context: 0 };
32 +
}
33 +
34 +
/// Bind one nonzero context incarnation to nonempty authority on its own hart.
35 +
/// InvalidArg rejects malformed input, Denied a different hart, Busy an existing
36 +
/// binding, and Exhausted an empty balance. Failures preserve execution authority.
37 +
export fn bind(budget: *mut Budget, context: u64, hart: u32) throws (abi::Error) {
38 +
    if context == 0 or hart >= platform::MAX_HARTS { throw abi::Error::InvalidArg; }
39 +
    if hart <> budget.hart { throw abi::Error::Denied; }
40 +
    if budget.context <> 0 { throw abi::Error::Busy; }
41 +
    if budget.remaining == 0 { throw abi::Error::Exhausted; }
42 +
    set budget.context = context;
43 +
}
44 +
45 +
/// Release the exact bound incarnation without restoring any consumed ticks.
46 +
/// Matching a nonzero identity is a kernel invariant, not user input validation.
47 +
export fn unbind(budget: *mut Budget, context: u64) {
48 +
    assert context <> 0 and budget.context == context;
49 +
    set budget.context = 0;
50 +
}
51 +
52 +
/// Debit elapsed monotonic CLINT ticks and return the remaining balance.
53 +
/// The caller charges each execution interval once, before releasing its binding.
54 +
/// A matching nonzero identity is required even after saturation at zero.
55 +
export fn charge(budget: *mut Budget, context: u64, elapsed: u64) -> u64 {
56 +
    assert context <> 0 and budget.context == context;
57 +
    if elapsed >= budget.remaining {
58 +
        set budget.remaining = 0;
59 +
    } else {
60 +
        set budget.remaining -= elapsed;
61 +
    }
62 +
    return budget.remaining;
63 +
}
64 +
65 +
/// Compute a timer deadline, including before binding, without changing authority.
66 +
/// Exhausted rejects zero balance; InvalidArg rejects overflow instead of wrapping.
67 +
export fn deadline(budget: *Budget, now: u64) -> u64 throws (abi::Error) {
68 +
    if budget.remaining == 0 { throw abi::Error::Exhausted; }
69 +
    if now > 0xffffffffffffffff - budget.remaining { throw abi::Error::InvalidArg; }
70 +
    return now + budget.remaining;
71 +
}
kernel/core/clock.rad added +10 -0
1 +
//! Machine-only CLINT access using validated physical platform addresses.
2 +
3 +
/// Read monotonic ticks from a validated CLINT register window.
4 +
export unsafe fn read(clint: u64) -> u64;
5 +
6 +
/// Program one validated CLINT bank's timer compare, with ordered MMIO access.
7 +
export unsafe fn arm(clint: u64, bank: u32, deadline: u64);
8 +
9 +
/// Select enabled machine interrupt sources while global M-mode interrupts are off.
10 +
export unsafe fn interrupts(mask: u64);
kernel/core/contexts.rad added +142 -0
1 +
//! Bounded execution identities and linear obligations for charged user intervals.
2 +
3 +
use core::abi;
4 +
use core::budgets;
5 +
use core::cpu;
6 +
use core::domains;
7 +
use core::frames;
8 +
use core::platform;
9 +
10 +
/// Maximum execution contexts shared by all domains.
11 +
export constant CAPACITY: u32 = 512;
12 +
/// Hart value before an execution context has been bound.
13 +
export constant NO_HART: u32 = 0xffffffff;
14 +
15 +
/// Execution state independent of the owning domain's lifecycle.
16 +
export union Status: Copy {
17 +
    /// Slot available for a new incarnation.
18 +
    Vacant,
19 +
    /// Can be dispatched when its bound budget permits execution.
20 +
    Ready,
21 +
    /// One hart owns a live accounting interval and architectural frame.
22 +
    Running,
23 +
    /// Waiting for an unread domain event.
24 +
    Waiting,
25 +
    /// Explicitly stopped; dispatch requires a new request.
26 +
    Stopped,
27 +
}
28 +
29 +
/// Private state for one execution context; all mutation is kernel serialized.
30 +
export record Context: Copy {
31 +
    /// Complete architectural user state.
32 +
    frame: cpu::Frame,
33 +
    /// Immutable environment addressed by this context's tp.
34 +
    env: domains::Env,
35 +
    /// Owning protection-domain incarnation.
36 +
    owner: abi::Object,
37 +
    /// Resource identity retained by this context's budget binding.
38 +
    budget: abi::Object,
39 +
    /// Private stack allocation; count zero means not provisioned.
40 +
    private: frames::Run,
41 +
    /// Stable table index.
42 +
    index: u32,
43 +
    /// Nonzero live incarnation; exhausted slots are not reused.
44 +
    epoch: u32,
45 +
    /// Execution transition state.
46 +
    status: Status,
47 +
    /// Bound hardware hart, or NO_HART before binding.
48 +
    hart: u32,
49 +
    /// Explicit caller to resume when this context relinquishes execution.
50 +
    continuation: u64,
51 +
    /// Deadline of the current charged interval.
52 +
    deadline: u64,
53 +
}
54 +
55 +
/// A started interval that must be charged exactly once after architectural return.
56 +
export union Running: Once {
57 +
    /// Context identity and monotonic start time of the interval.
58 +
    Interval { identity: u64, started: u64 },
59 +
}
60 +
61 +
/// Initialize one table slot before it can receive a context incarnation.
62 +
export fn init(context: *mut Context, index: u32) {
63 +
    assert index < CAPACITY;
64 +
    set context.index = index;
65 +
    set context.epoch = 0;
66 +
    set context.status = Status::Vacant;
67 +
    set context.owner = domains::none();
68 +
    set context.budget = domains::none();
69 +
    set context.private = frames::Run { first: 0, count: 0 };
70 +
    set context.hart = NO_HART;
71 +
    set context.continuation = 0;
72 +
    set context.deadline = 0;
73 +
    set context.env = domains::Env {
74 +
        argsPointer: 0, argsSize: 0, eventsHandle: 0, eventsPointer: 0,
75 +
        stateBase: 0, stackBase: 0, stackTop: 0, context: 0,
76 +
        privateStackBase: 0, privateStackTop: 0,
77 +
    };
78 +
    cpu::init(&mut context.frame, 0, 0, 0, 0);
79 +
}
80 +
81 +
/// Get the nonzero incarnation-qualified identity of an initialized context.
82 +
export fn identity(context: *Context) -> u64 {
83 +
    if context.epoch == 0 { return 0; }
84 +
    return (context.epoch as u64 << 32) | context.index as u64;
85 +
}
86 +
87 +
/// Resolve a current context incarnation without treating an integer as authority.
88 +
export fn resolve(table: *[Context], id: u64) -> u32 throws (abi::Error) {
89 +
    let index = id as u32;
90 +
    let epoch = id >> 32;
91 +
    if epoch == 0 or index >= table.len { throw abi::Error::InvalidArg; }
92 +
    let context = &table[index];
93 +
    if context.epoch as u64 <> epoch or context.status == Status::Vacant {
94 +
        throw abi::Error::InvalidArg;
95 +
    }
96 +
    return index;
97 +
}
98 +
99 +
/// Install checked image and startup state in a vacant slot, without granting budget.
100 +
export fn prepare(context: *mut Context, owner: abi::Object, entry: u64, stack: u64, env: domains::Env) throws (abi::Error) {
101 +
    if context.status <> Status::Vacant { throw abi::Error::Busy; }
102 +
    if context.epoch == 0xffffffff { throw abi::Error::Exhausted; }
103 +
    assert owner.kind == abi::Kind::Domain and owner.epoch <> 0;
104 +
    set context.epoch += 1;
105 +
    set context.owner = owner;
106 +
    set context.budget = domains::none();
107 +
    set context.hart = NO_HART;
108 +
    set context.continuation = 0;
109 +
    set context.deadline = 0;
110 +
    set context.env = env;
111 +
    set context.env.context = identity(context);
112 +
    cpu::init(&mut context.frame, entry, stack, &context.env as u64, env.stateBase);
113 +
    set context.status = Status::Ready;
114 +
}
115 +
116 +
/// Start authorized execution after the caller has checked the owning domain is active.
117 +
/// The caller programs deadline before user entry and owns the frame until finish.
118 +
export fn begin(context: *mut Context, budget: *budgets::Budget, now: u64, hart: u32) -> Running throws (abi::Error) {
119 +
    if context.status <> Status::Ready { throw abi::Error::Busy; }
120 +
    if hart >= platform::MAX_HARTS or context.hart <> hart or budget.hart <> hart {
121 +
        throw abi::Error::Denied;
122 +
    }
123 +
    let id = identity(context);
124 +
    if id == 0 or budget.context <> id { throw abi::Error::Denied; }
125 +
    let deadline = try budgets::deadline(budget, now);
126 +
    set context.deadline = deadline;
127 +
    set context.status = Status::Running;
128 +
    return Running::Interval { identity: id, started: now };
129 +
}
130 +
131 +
/// Charge one completed interval before any binding, wait, or lifecycle mutation.
132 +
export fn finish(context: *mut Context, budget: *mut budgets::Budget, running: Running, now: u64) -> u64 {
133 +
    match running {
134 +
        case Running::Interval { identity: id, started } => {
135 +
            assert context.status == Status::Running and identity(context) == id;
136 +
            assert now >= started;
137 +
            let remaining = budgets::charge(budget, id, now - started);
138 +
            set context.status = Status::Ready;
139 +
            return remaining;
140 +
        },
141 +
    }
142 +
}
kernel/core/resources.rad +7 -0
1 1
//! Physical object identities shared by capability entries.
2 2
3 3
use core::abi;
4 +
use core::budgets;
4 5
use core::domains;
5 6
use core::fdt;
6 7
use core::frames;
7 8
8 9
/// One contiguous physical Page object.
29 30
    Page(Page),
30 31
    /// User-visible MMIO register range.
31 32
    Device(fdt::Range),
32 33
    /// Exclusively held external interrupt source.
33 34
    Interrupt(Interrupt),
35 +
    /// Finite execution authority with one context binding.
36 +
    Budget(budgets::Budget),
34 37
}
35 38
36 39
/// One resource slot and its live handle count.
37 40
export record Slot: Copy {
38 41
    /// Type-specific physical resource state.
48 51
    match value {
49 52
        case Value::Free => return abi::Kind::Empty,
50 53
        case Value::Page(_) => return abi::Kind::Page,
51 54
        case Value::Device(_) => return abi::Kind::Device,
52 55
        case Value::Interrupt(_) => return abi::Kind::Interrupt,
56 +
        case Value::Budget(_) => return abi::Kind::Budget,
53 57
    }
54 58
}
55 59
56 60
/// Initialize caller-owned physical resource storage once at boot.
57 61
export fn init(slots: *mut [Slot]) {
117 121
    set slot.references -= 1;
118 122
    if let case Value::Page(page) = slot.value; slot.references == 0 {
119 123
        set slot.value = Value::Free;
120 124
        return page.run;
121 125
    }
126 +
    if object.kind == abi::Kind::Budget and slot.references == 0 {
127 +
        set slot.value = Value::Free;
128 +
    }
122 129
    if let case Value::Interrupt(irq) = &mut slot.value {
123 130
        assert slot.references == 0;
124 131
        set irq.target = domains::none();
125 132
    }
126 133
    return nil;
kernel/core/state.rad +3 -0
1 1
//! Bounded storage shared by kernel control-plane mechanisms.
2 2
3 3
use core::domains;
4 +
use core::contexts;
4 5
use core::memory;
5 6
use core::resources;
6 7
7 8
/// Kernel-owned state accessed while the machine critical section is held.
8 9
export record State: Copy {
9 10
    /// Protection-domain slots and their capability tables.
10 11
    domains: *mut [domains::Domain],
11 12
    /// Physical resource identities and live handle counts.
12 13
    resources: *mut [resources::Slot],
14 +
    /// Execution identities and protected architectural frames.
15 +
    contexts: *mut [contexts::Context],
13 16
    /// Physical allocations and persistent domain-lifetime pins.
14 17
    memory: memory::Memory,
15 18
}