radiance · commit

kernel: Complete preemptible runtime loading

fa787cc52463bb0996aa77aa3441f223fdc8704ff180f76b89ba047c8a9141e4

Alexis Sellier committed 13 days ago 1 parent 5e7ead57

Makefile +7 -1


# Verify the emulator binary exists.
EMU_PATH := $(shell command -v $(EMU) 2>/dev/null)

default: emulator $(RAD_BIN)
test: emulator seed-test std-test bin-test kernel-test module-test package-test native-test shared-test sync-test kernel-boot-test trap-test page-test loader-test dispatch-test smp-test termination-test
test: emulator seed-test std-test bin-test kernel-test module-test package-test native-test shared-test sync-test kernel-boot-test trap-test page-test loader-test dispatch-test smp-test termination-test runtime-test

seed-test:
	@seed/test

module-test: emulator $(RAD_BIN)

# User exit, abort, and CPU faults preserve the surviving parent's execution.
termination-test: emulator $(RAD_BIN) $(BIN_DIR)/kernel.build.rv64
	@RAD_EMULATOR="$(EMU)" sh test/dispatch/run termination

.PHONY: termination-test

# Scheduled compilation, cancellation, retry, and shared executable publication.
runtime-test: emulator $(RAD_BIN) $(BIN_DIR)/kernel.build.rv64
	@RAD_EMULATOR="$(EMU)" sh test/runtime/run

.PHONY: runtime-test

kernel/kernel/frames.rad +68 -14


/// Physical addresses and occupancy of allocatable frames, sorted by address.
export record Pool: Copy {
    /// Physical base address of each eligible frame.
    addresses: [u64; limits::FRAMES],
    /// True when the frame is available for reservation.
    free: [bool; limits::FRAMES],
    /// One set bit per available frame, indexed from the low bit of each word.
    free: [u64; limits::FRAMES / 64],
    /// Number of valid frame-map entries.
    count: u32,
    /// Retired runs whose frames remain unavailable until reclamation.
    retired: [Run; limits::FRAMES],
    /// Index of the next retired run to reclaim.


/// Build a fresh frame map from complete RAM pages with no reserved byte.
/// The pool has zero valid entries if initialization fails.
export unsafe fn initialize(pool: &mut Pool, machine: &platform::Platform) throws (abi::Error) {
    set pool.count = 0;
    set pool.free = [0; limits::FRAMES / 64];
    set pool.retiredHead = 0;
    set pool.retiredCount = 0;
    if machine.ramCount > platform::RAM_BANKS or machine.reservedCount > platform::RESERVATIONS {
        throw abi::Error::InvalidArg;
    }

                set address = (reserved[next].end + limits::FRAME_SIZE - 1) & ~(limits::FRAME_SIZE - 1);
                continue;
            }
            if count == limits::FRAMES { throw abi::Error::Exhausted; }
            set pool.addresses[count] = address;
            set pool.free[count] = true;
            set pool.free[count / 64] |= 1 << (count % 64) as u64;
            set count += 1;
            set address += limits::FRAME_SIZE;
        }
    }
    set pool.count = count;
}

/// Reserve the first physically contiguous free run with a bounded scan.
/// Test one valid frame's availability without exposing unused bitmap bits.
export fn available(pool: &Pool, index: u32) -> bool {
    return index < pool.count and (pool.free[index / 64] & (1 << (index % 64) as u64)) <> 0;
}

/// Low bits selected by a nonzero word-sized span.
fn mask(count: u32) -> u64 {
    assert count > 0 and count <= 64;
    if count == 64 { return 0xffffffffffffffff; }
    return (1 << count as u64) - 1;
}

/// Change a validated run's occupancy one bitmap word at a time.
fn assign(pool: &mut Pool, run: Run, free: bool) {
    let mut first = run.first;
    let end = first + run.count;
    while first < end {
        let offset = first % 64;
        let mut count = 64 - offset;
        if count > end - first { set count = end - first; }
        let bits = mask(count) << offset as u64;
        if free { set pool.free[first / 64] |= bits; }
        else { set pool.free[first / 64] &= ~bits; }
        set first += count;
    }
}

/// Reserve the first contiguous run, scanning uniform bitmap words together.
export fn reserve(pool: &mut Pool, count: u32) -> Reservation throws (abi::Error) {
    if count == 0 { throw abi::Error::InvalidArg; }
    let mut first: u32 = 0;
    let mut found: u32 = 0;
    let mut previous: u64 = 0;
    for i in 0..pool.count {
        if not pool.free[i] { set found = 0; continue; }
        if found == 0 or pool.addresses[i] <> previous + limits::FRAME_SIZE { set first = i; set found = 0; }
        set found += 1;
        set previous = pool.addresses[i];
        if found == count {
            for j in first..first + count { set pool.free[j] = false; }
            return Reservation::Held(Run { first, count });
    for word in 0..(pool.count + 63) / 64 {
        let base = word * 64;
        let mut length = pool.count - base;
        if length > 64 { set length = 64; }
        let full = mask(length);
        let bits = pool.free[word] & full;
        if bits == 0 { set found = 0; continue; }
        let address = pool.addresses[base];
        if bits == full and pool.addresses[base + length - 1] - address == (length - 1) as u64 * limits::FRAME_SIZE {
            if found == 0 or address <> previous + limits::FRAME_SIZE { set first = base; set found = 0; }
            set found += length;
            set previous = pool.addresses[base + length - 1];
        } else {
            for offset in 0..length {
                let i = base + offset;
                if (bits & (1 << offset as u64)) == 0 { set found = 0; continue; }
                if found == 0 or pool.addresses[i] <> previous + limits::FRAME_SIZE { set first = i; set found = 0; }
                set found += 1;
                set previous = pool.addresses[i];
                if found >= count { break; }
            }
        }
        if found >= count {
            let run = Run { first, count };
            assign(pool, run, false);
            return Reservation::Held(run);
        }
    }
    throw abi::Error::OutOfMemory;
}



/// Return a backing allocation's frames after all handles and exposures end.
/// Only the owner of a committed run may release it.
export fn release(pool: &mut Pool, run: Run) throws (abi::Error) {
    let memory = try extent(pool, run);
    for i in run.first..run.first + run.count { if pool.free[i] { throw abi::Error::BadHandle; } }
    for i in run.first..run.first + run.count { set pool.free[i] = true; }
    let mut first = run.first;
    let end = first + run.count;
    while first < end {
        let offset = first % 64;
        let mut count = 64 - offset;
        if count > end - first { set count = end - first; }
        if (pool.free[first / 64] & (mask(count) << offset as u64)) <> 0 { throw abi::Error::BadHandle; }
        set first += count;
    }
    assign(pool, run, true);
}

/// Transfer exclusive ownership of a committed run to bounded reclamation.
/// The caller must not release or retire this run again.
export fn retire(pool: &mut Pool, run: Run) throws (abi::Error) {

kernel/kernel/tests/backing.rad +13 -13

unsafe fn initialize() {
    backing::initialize(&mut STORE);
    try! backing::registerDomain(&mut STORE, abi::Ref { index: 0, generation: 1 });
    try! backing::registerDomain(&mut STORE, abi::Ref { index: 1, generation: 1 });
    set STORE.pool.count = 4;
    for i in 0..4 { set STORE.pool.addresses[i] = 0x80000000 + i as u64 * 4096; set STORE.pool.free[i] = true; }
    for i in 0..4 { set STORE.pool.addresses[i] = 0x80000000 + i as u64 * 4096; set STORE.pool.free[i / 64] |= 1 << (i % 64) as u64; }
}

/// Publish one backing record with its initial page and origin exposure.
unsafe fn allocate() -> abi::Ref {
    let slot = try! slots::reserve(&mut STORE.slots[..]);

    };
    assert invalid and backing::domainLive(&STORE, owner);
    assert not try! backing::endDomainStep(&mut STORE, owner, 1);
    assert not backing::domainLive(&STORE, owner);
    assert STORE.slots[objects[0].index].state == slots::State::Free;
    assert STORE.pool.retiredCount == 1 and not STORE.pool.free[0];
    assert STORE.pool.retiredCount == 1 and not frames::available(&STORE.pool, 0);
    assert STORE.records[objects[1].index].exposed == 2;
    let mut busy = false;
    try backing::registerDomain(&mut STORE, abi::Ref { index: 0, generation: 2 }) catch error {
        assert error == abi::Error::Busy; set busy = true;
    };

    assert STORE.records[objects[1].index].exposed == 1;
    assert STORE.records[objects[2].index].exposed == 1;
    while not try! backing::endDomainStep(&mut STORE, owner, 64) {}
    assert STORE.records[objects[2].index].exposed == 0 and STORE.records[objects[2].index].pages == 1;
    assert STORE.pool.retiredCount == 1;
    assert frames::reclaim(&mut STORE.pool, 1) == 1 and STORE.pool.free[0];
    assert not STORE.pool.free[1] and not STORE.pool.free[2];
    assert frames::reclaim(&mut STORE.pool, 1) == 1 and frames::available(&STORE.pool, 0);
    assert not frames::available(&STORE.pool, 1) and not frames::available(&STORE.pool, 2);
    let next = abi::Ref { index: 0, generation: 2 };
    try! backing::registerDomain(&mut STORE, next);
    assert backing::domainLive(&STORE, next);
    let mut stale = false;
    try backing::endDomainStep(&mut STORE, owner, 64) catch error {
        assert error == abi::Error::BadHandle; set stale = true;
    };
    assert stale and backing::domainLive(&STORE, next);
    try! backing::releasePage(&mut STORE, objects[2]);
    assert STORE.pool.free[2];
    assert frames::available(&STORE.pool, 2);
    while not try! backing::endDomainStep(&mut STORE, receiver, 64) {}
    assert STORE.pool.retiredCount == 1 and not STORE.pool.free[1];
    assert frames::reclaim(&mut STORE.pool, 1) == 1 and STORE.pool.free[1];
    assert STORE.pool.retiredCount == 1 and not frames::available(&STORE.pool, 1);
    assert frames::reclaim(&mut STORE.pool, 1) == 1 and frames::available(&STORE.pool, 1);
}

/// Dropping all page handles preserves capacity while an exposed domain lives.
@test unsafe fn exposures() throws (testing::TestError) {
    initialize();

    try! backing::expose(&mut STORE, object, receiver);
    try! backing::expose(&mut STORE, object, receiver);
    try testing::expect(STORE.records[object.index].exposed == 2);
    try! backing::releasePage(&mut STORE, object);
    try! backing::endDomain(&mut STORE, abi::Ref { index: 0, generation: 1 });
    try testing::expect(not STORE.pool.free[0] and slots::matches(&STORE.slots[..], object, slots::State::Live));
    assert not frames::available(&STORE.pool, 0) and slots::matches(&STORE.slots[..], object, slots::State::Live);
    try! backing::endDomain(&mut STORE, receiver);
    for i in 0..4 { try testing::expect(STORE.pool.free[i]); }
    for i in 0..4 { assert frames::available(&STORE.pool, i); }
    try testing::expect(not slots::matches(&STORE.slots[..], object, slots::State::Live));
}

/// Splits keep their common backing alive until every page object is gone.
@test unsafe fn splitLifetime() throws (testing::TestError) {
    initialize();
    let object = allocate();
    try! backing::retainPage(&mut STORE, object);
    try! backing::endDomain(&mut STORE, abi::Ref { index: 0, generation: 1 });
    try! backing::releasePage(&mut STORE, object);
    try testing::expect(not STORE.pool.free[0] and STORE.records[object.index].pages == 1);
    assert not frames::available(&STORE.pool, 0) and STORE.records[object.index].pages == 1;
    try! backing::releasePage(&mut STORE, object);
    try testing::expect(STORE.pool.free[0]);
    assert frames::available(&STORE.pool, 0);
    let mut stale = false;
    try backing::releasePage(&mut STORE, object) catch err {
        try testing::expect(err == abi::Error::BadHandle); set stale = true;
    };
    try testing::expect(stale);

        try testing::expect(err == abi::Error::BadHandle); set stale = true;
    };
    try testing::expect(stale and STORE.records[object.index].exposed == 1);
    try! backing::releasePage(&mut STORE, object);
    try! backing::endDomain(&mut STORE, abi::Ref { index: 0, generation: 1 });
    try testing::expect(STORE.pool.free[0]);
    assert frames::available(&STORE.pool, 0);
}

/// Retained backing metadata cannot create new page authority after the last page ends.
@test unsafe fn noResurrection() throws (testing::TestError) {
    initialize();

    try backing::expose(&mut STORE, object, abi::Ref { index: 1, generation: 1 }) catch err {
        try testing::expect(err == abi::Error::BadHandle); set failures += 1;
    };
    try testing::expect(failures == 2 and STORE.records[object.index].exposed == 1);
    try! backing::endDomain(&mut STORE, abi::Ref { index: 0, generation: 1 });
    try testing::expect(STORE.pool.free[0]);
    assert frames::available(&STORE.pool, 0);
}

kernel/kernel/tests/calls.rad +2 -1

//! Direct-call scalar results, checked record copies, and architectural replies.

use std::testing;
use kernel::abi;
use kernel::frames;
use kernel::calls;
use kernel::domains;
use kernel::pages;
use kernel::backing;
use kernel::capability;

    let aligned = (base + 4095) & ~4095;
    set OFFSET = ((aligned - base) / 8) as u32;
    set pages::STORE.backings.pool.count = 4;
    for i in 0..4 {
        set pages::STORE.backings.pool.addresses[i] = aligned + i as u64 * 4096;
        set pages::STORE.backings.pool.free[i] = true;
        set pages::STORE.backings.pool.free[i / 64] |= 1 << (i % 64) as u64;
    }
    let pending = try! slots::reserve(&mut domains::STORE.slots[..]);
    let owner = try! slots::commit(&mut domains::STORE.slots[..], pending);
    try! backing::registerDomain(&mut pages::STORE.backings, owner);
    capability::initialize(&mut MEMORY.table, owner);

kernel/kernel/tests/domains.rad +15 -15

    let base = pointer as u64;
    let aligned = (base + 4095) & ~4095;
    set BACKINGS.pool.count = (@sizeOf([u64; 131072]) - (aligned - base) as u32) / 4096;
    for i in 0..BACKINGS.pool.count {
        set BACKINGS.pool.addresses[i] = aligned + i as u64 * 4096;
        set BACKINGS.pool.free[i] = true;
        set BACKINGS.pool.free[i / 64] |= 1 << (i % 64) as u64;
    }
    let pending = try! slots::reserve(&mut DOMAINS.slots[..]);
    let owner = try! slots::commit(&mut DOMAINS.slots[..], pending);
    set DOMAINS.records[owner.index].state = domains::Lifecycle::Active;
    set DOMAINS.records[owner.index].parent = nil;

    set DOMAINS.records[permit.object.index].state = domains::Lifecycle::Dead;
    set DOMAINS.contexts[caller.initial.index].state = domains::ContextState::Stopped;
    set DOMAINS.contexts[caller.initial.index].hart = 1;
    lifecycle::cancelAllocations(&mut CALLS, &mut DOMAINS, &mut PAGES, &mut loader::STATE, &mut registry::STORE);
    assert DOMAINS.contexts[caller.initial.index].reservation;
    assert not PAGES.backings.pool.free[creation.storage.allocation.first];
    assert not frames::available(&PAGES.backings.pool, creation.storage.allocation.first);
    match lease { case lifecycle::Lease::Held(context) => { assert context == caller.initial; }, }
    set DOMAINS.contexts[caller.initial.index].hart = nil;
    lifecycle::cancelAllocations(&mut CALLS, &mut DOMAINS, &mut PAGES, &mut loader::STATE, &mut registry::STORE);
    assert not DOMAINS.contexts[caller.initial.index].reservation;
    assert DOMAINS.slots[creation.domain.index].state == slots::State::Free;

    while PAGES.backings.pool.retiredCount > 0 {
        let reclaimed = frames::reclaim(&mut PAGES.backings.pool, 256);
        assert reclaimed > 0 and reclaimed <= 256;
    }
    for run in [creation.storage.allocation, creation.storage.kernelFrames, creation.storage.graph.frames] {
        for i in run.first..run.first + run.count { assert PAGES.backings.pool.free[i]; }
        for i in run.first..run.first + run.count { assert frames::available(&PAGES.backings.pool, i); }
    }
    set DOMAINS.records[permit.object.index].state = domains::Lifecycle::Active;
    let next = try! domains::reserve(&mut DOMAINS, &mut PAGES.backings, &PACKAGES, &mut caller.memory.table, authority, image);
    let active = lifecycle::holdDomain(&mut CALLS, &mut DOMAINS, caller.initial, next);
    try! lifecycle::prepareDomain(&CALLS, &PACKAGES, &active);

    assert not lifecycle::reapNext(&mut DOMAINS, &mut PAGES, &mut WINDOWS, &mut IRQS);
    while PAGES.backings.pool.retiredCount > 0 {
        let reclaimed = frames::reclaim(&mut PAGES.backings.pool, 256);
        assert reclaimed > 0 and reclaimed <= 256;
    }
    assert not PAGES.backings.pool.free[run.first];
    assert not frames::available(&PAGES.backings.pool, run.first);
    assert PAGES.backings.records[allocation.index].exposed == 1;
    assert (try! pages::get(&PAGES, (try! capability::get(&parent.memory.table, shared)).object)).count == 1;
    assert try! events::flush(&mut DOMAINS.events, receiver, &mut parent.memory.ring) == 1;
    let event = try! events::pop(&mut parent.memory.ring) else panic "missing reaped child event";
    assert event.value == abi::id(target) and event.code == 19;

    assert DOMAINS.slots[receiver.index].state == slots::State::Free;
    while PAGES.backings.pool.retiredCount > 0 {
        let reclaimed = frames::reclaim(&mut PAGES.backings.pool, 256);
        assert reclaimed > 0 and reclaimed <= 256;
    }
    for i in 0..PAGES.backings.pool.count { assert PAGES.backings.pool.free[i]; }
    for i in 0..PAGES.backings.pool.count { assert frames::available(&PAGES.backings.pool, i); }
}

/// Initial return reports to the current parent and retains its terminal identity.
@test unsafe fn terminalParent() throws (testing::TestError) {
    initialize(abi::CREATE);

    };
    assert overlap;
    let reservedFrames = DOMAINS.contexts[index].kernelFrames;
    domains::contextCancel(&mut DOMAINS, &mut PAGES, reserved);
    assert DOMAINS.contextSlots[index].state == slots::State::Free;
    for i in reservedFrames.first..reservedFrames.first + reservedFrames.count { assert PAGES.backings.pool.free[i]; }
    for i in reservedFrames.first..reservedFrames.first + reservedFrames.count { assert frames::available(&PAGES.backings.pool, i); }
    let pendingContext = try! domains::contextReserve(&mut DOMAINS, &mut PAGES, &PACKAGES, &TABLE, handle, start);
    let stackBase = DOMAINS.contexts[index].kernelStack.start;
    let base = (&RAM[0]) as u64;
    let firstWord = ((stackBase - base) / 8) as u32;
    let lastWord = firstWord + domains::KERNEL_STACK_PAGES * 512 - 1;

    try domains::contextDestroy(&mut DOMAINS, &mut PAGES, &TABLE, handle, context) catch error {
        assert error == abi::Error::Busy; set retained = true;
    };
    assert retained and DOMAINS.contextSlots[context.index].state == slots::State::Live;
    for i in created.kernelFrames.first..created.kernelFrames.first + created.kernelFrames.count {
        assert not PAGES.backings.pool.free[i];
        assert not frames::available(&PAGES.backings.pool, i);
    }
    set DOMAINS.contexts[context.index].pending = nil;
    set DOMAINS.contexts[context.index].reservation = true;
    set retained = false;
    try domains::contextDestroy(&mut DOMAINS, &mut PAGES, &TABLE, handle, context) catch error {

    };
    assert retained and DOMAINS.contextSlots[context.index].state == slots::State::Live;
    set DOMAINS.contexts[context.index].reservation = false;
    try! domains::contextDestroy(&mut DOMAINS, &mut PAGES, &TABLE, handle, context);
    for i in created.kernelFrames.first..created.kernelFrames.first + created.kernelFrames.count {
        try testing::expect(PAGES.backings.pool.free[i]);
        assert frames::available(&PAGES.backings.pool, i);
    }
    try domains::context(&DOMAINS, authority.object, context) catch error {
        try testing::expect(error == abi::Error::BadHandle); set rejected += 1;
    };
    let next = try! domains::contextCreate(&mut DOMAINS, &mut PAGES, &PACKAGES, &TABLE, handle, start);

    let cancelled = try! domains::reserve(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE);
    domains::cancel(&mut DOMAINS, &mut BACKINGS, &mut TABLE, cancelled);
    assert DOMAINS.slots[1].state == slots::State::Free;
    assert DOMAINS.contextSlots[0].state == slots::State::Free;
    assert TABLE.slots[2].state == slots::State::Free;
    for i in 0..BACKINGS.pool.count { assert BACKINGS.pool.free[i]; }
    for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
    set PACKAGES.entries[0].package.relocations = &[shared::Relocation {
        offset: 0, count: 1, target: shared::DataRef { slot: 5, offset: 0 },
    }];
    let mut invalid = false;
    try domains::create(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE) catch error {
        assert error == abi::Error::VerifyFailed; set invalid = true;
    };
    assert invalid and DOMAINS.slots[1].state == slots::State::Free;
    for i in 0..BACKINGS.pool.count { assert BACKINGS.pool.free[i]; }
    for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
    initialize(abi::CREATE);
    let abandoned = try! domains::reserve(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE);
    try! domains::prepare(&PACKAGES, &abandoned);
    try! backing::endDomain(&mut BACKINGS, TABLE.owner);
    let mut dead = false;
    try domains::publish(&mut DOMAINS, &mut BACKINGS, &mut TABLE, abandoned) catch error {
        assert error == abi::Error::BadHandle; set dead = true;
    };
    assert dead and DOMAINS.slots[1].state == slots::State::Free;
    assert TABLE.slots[2].state == slots::State::Free;
    for i in 0..BACKINGS.pool.count { assert BACKINGS.pool.free[i]; }
    for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
}

/// Creation installs only Events in the child and preserves selected authorizing rights.
@test unsafe fn pending() throws (testing::TestError) {
    initialize(abi::CREATE | abi::ALLOCATE);

    let mut rejected = false;
    try domains::create(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE) catch err {
        try testing::expect(err == expected); set rejected = true;
    };
    try testing::expect(rejected);
    for i in 0..BACKINGS.pool.count { try testing::expect(BACKINGS.pool.free[i]); }
    for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
    try testing::expect(DOMAINS.slots[1].state == slots::State::Free);
    try testing::expect(DOMAINS.contextSlots[0].state == slots::State::Free);
    try testing::expect(TABLE.slots[2].state == slots::State::Free);
    try testing::expect(BACKINGS.domains[1] == 0);
}

    try domains::create(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE) catch err {
        try testing::expect(err == abi::Error::Exhausted); set rejected = true;
    };
    try testing::expect(rejected and DOMAINS.slots[1].state == slots::State::Free);
    try testing::expect(TABLE.slots[2].state == slots::State::Free);
    for i in 0..BACKINGS.pool.count { try testing::expect(BACKINGS.pool.free[i]); }
    for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
}

/// A creator can grant Create without Allocate and the next creation preserves that choice.
@test unsafe fn selectiveAuthority() throws (testing::TestError) {
    initialize(abi::CREATE | abi::ALLOCATE);

    let mut failures: u32 = 0;
    try domains::create(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE) catch err {
        try testing::expect(err == abi::Error::Exhausted); set failures += 1;
    };
    try testing::expect(DOMAINS.slots[1].state == slots::State::Free);
    for i in 0..BACKINGS.pool.count { try testing::expect(BACKINGS.pool.free[i]); }
    for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
    initialize(abi::CREATE);
    for i in 1..DOMAINS.slots.len { set DOMAINS.slots[i].state = slots::State::Retired; }
    try domains::create(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE) catch err {
        try testing::expect(err == abi::Error::Exhausted); set failures += 1;
    };
    try testing::expect(failures == 2 and TABLE.slots[2].state == slots::State::Free);
    try testing::expect(DOMAINS.contextSlots[0].state == slots::State::Free);
    for i in 0..BACKINGS.pool.count { try testing::expect(BACKINGS.pool.free[i]); }
    for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
}

kernel/kernel/tests/frames.rad +63 -6

    set machine.reservedCount = 1;
    set machine.reserved[0] = range::Range { start: 0x80003000, end: 0x80005000 };
    try! frames::initialize(&mut POOL, &machine);
}

/// Bitmap allocation agrees with a scalar scan across holes and word boundaries.
@test unsafe fn bitmapRuns() throws (testing::TestError) {
    let mut machine: platform::Platform = undefined;
    set machine.ramCount = 1;
    set machine.ram[0] = range::Range { start: 0x80000000, end: 0x800c2000 };
    set machine.reservedCount = 1;
    set machine.reserved[0] = range::Range { start: 0x8001f000, end: 0x80020000 };
    for pattern in 0..5 {
        for count in [1 as u32, 2, 31, 32, 63, 64, 65, 127, 128, 129, 193, 194] {
            try! frames::initialize(&mut POOL, &machine);
            assert POOL.count == 193;
            for i in 0..POOL.count {
                if pattern > 0 and i % (pattern * 32) == 0 {
                    set POOL.free[i / 64] &= ~(1 << (i % 64) as u64);
                }
            }
            // Padding bits are outside the pool even when their values are set.
            set POOL.free[3] |= 0xfffffffffffffffe;
            let before = [POOL.free[0], POOL.free[1], POOL.free[2], POOL.free[3]];
            let mut expected: ?u32 = nil;
            let mut found: u32 = 0;
            for i in 0..POOL.count {
                if not frames::available(&POOL, i) { set found = 0; continue; }
                if found > 0 and POOL.addresses[i] <> POOL.addresses[i - 1] + 4096 { set found = 0; }
                set found += 1;
                if found == count { set expected = i + 1 - count; break; }
            }
            let reservation = try frames::reserve(&mut POOL, count) catch error {
                assert expected == nil and error == abi::Error::OutOfMemory;
                for i in 0..4 { assert POOL.free[i] == before[i]; }
                continue;
            };
            let first = expected else panic "unexpected frame reservation";
            let run = frames::commit(reservation);
            assert run.first == first and run.count == count;
            for i in 0..POOL.count {
                if i >= first and i - first < count { assert not frames::available(&POOL, i); }
                else { assert frames::available(&POOL, i) == ((before[i / 64] & (1 << (i % 64) as u64)) <> 0); }
            }
            try! frames::release(&mut POOL, run);
            for i in 0..4 { assert POOL.free[i] == before[i]; }
        }
    }
    assert not frames::available(&POOL, POOL.count);
    try! frames::initialize(&mut POOL, &machine);
    let run = frames::commit(try! frames::reserve(&mut POOL, 128));
    assert run.first == 31;
    let before = [POOL.free[0], POOL.free[1], POOL.free[2], POOL.free[3]];
    let mut invalid = false;
    try frames::release(&mut POOL, frames::Run { first: run.first, count: 129 }) catch error {
        assert error == abi::Error::BadHandle; set invalid = true;
    };
    assert invalid;
    for i in 0..4 { assert POOL.free[i] == before[i]; }
    try! frames::release(&mut POOL, run);
}

/// Retired frames stay unavailable until bounded reclamation returns them.
@test unsafe fn retirement() throws (testing::TestError) {
    initialize();
    set POOL.retiredHead = limits::FRAMES - 1;
    let left = frames::commit(try! frames::reserve(&mut POOL, 3));
    let right = frames::commit(try! frames::reserve(&mut POOL, 5));
    try! frames::retire(&mut POOL, left);
    try! frames::retire(&mut POOL, right);
    assert POOL.retiredCount == 2;
    for i in 0..8 { assert not POOL.free[i]; }
    for i in 0..8 { assert not frames::available(&POOL, i); }
    assert frames::reclaim(&mut POOL, 0) == 0;
    assert frames::reclaim(&mut POOL, 2) == 2;
    assert POOL.free[0] and POOL.free[1] and not POOL.free[2];
    assert frames::available(&POOL, 0) and frames::available(&POOL, 1) and not frames::available(&POOL, 2);
    let reused = frames::commit(try! frames::reserve(&mut POOL, 2));
    assert reused.first == 0;
    assert frames::reclaim(&mut POOL, 3) == 3;
    assert POOL.retiredCount == 1 and not POOL.free[5];
    assert not POOL.free[0] and not POOL.free[1];
    assert POOL.retiredCount == 1 and not frames::available(&POOL, 5);
    assert not frames::available(&POOL, 0) and not frames::available(&POOL, 1);
    try! frames::retire(&mut POOL, reused);
    assert frames::reclaim(&mut POOL, 20) == 5;
    assert POOL.retiredCount == 0;
    for i in 0..8 { assert POOL.free[i]; }
    for i in 0..8 { assert frames::available(&POOL, i); }
    assert frames::reclaim(&mut POOL, 20) == 0;
}

/// Adjacent physical frames form runs; a reserved hole cannot be crossed.
@test unsafe fn fragmentation() throws (testing::TestError) {

    try! frames::initialize(&mut POOL, &machine);
    let mut count: u32 = 0;
    for i in 0..96 {
        let start = 0x80000000 + i as u64 * 4096;
        if platform::available(&machine, range::Range { start, end: start + 4096 }) {
            try testing::expect(count < POOL.count and POOL.addresses[count] == start and POOL.free[count]);
            assert count < POOL.count and POOL.addresses[count] == start and frames::available(&POOL, count);
            set count += 1;
        }
    }
    try testing::expect(count == POOL.count);
}

kernel/kernel/tests/instances.rad +4 -4

    let base = pointer as u64;
    let aligned = (base + 4095) & ~4095;
    set POOL.count = (@sizeOf([u64; 131072]) - (aligned - base) as u32) / 4096;
    for i in 0..POOL.count {
        set POOL.addresses[i] = aligned + i as u64 * 4096;
        set POOL.free[i] = true;
        set POOL.free[i / 64] |= 1 << (i % 64) as u64;
    }
    registry::initialize(&mut PACKAGES);
}

/// Publish a package with one private word and optional pointer relocation.

    assert first.frames.first + first.frames.count <= other.frames.first;
    try! frames::release(&mut POOL, first.frames);
    try! frames::release(&mut POOL, other.frames);
    let cancelled = try! instances::reserve(&PACKAGES, &mut POOL, root);
    instances::cancel(&mut POOL, cancelled);
    for i in 0..POOL.count { assert POOL.free[i]; }
    for i in 0..POOL.count { assert frames::available(&POOL, i); }
}

/// A diamond has one dependency instance per domain and independent relocated pointers.
@test unsafe fn diamond() throws (testing::TestError) {
    initialize();

    set *word(first.table[base.index]) = 99;
    try testing::expect(*word(second.table[base.index]) == 7);
    try testing::expect(first.table[4] == 0 and second.table[4] == 0);
    try! frames::release(&mut POOL, first.frames);
    try! frames::release(&mut POOL, second.frames);
    for i in 0..POOL.count { try testing::expect(POOL.free[i]); }
    for i in 0..POOL.count { assert frames::available(&POOL, i); }
}

/// State alignment can exceed a physical frame and zero-fill follows the template.
@test unsafe fn alignment() throws (testing::TestError) {
    initialize();

    };
    try instances::create(&PACKAGES, &mut POOL, abi::Ref { index: root.index, generation: 2 }) catch err {
        try testing::expect(err == abi::Error::BadHandle); set failures += 1;
    };
    try testing::expect(failures == 3);
    for i in 0..POOL.count { try testing::expect(POOL.free[i]); }
    for i in 0..POOL.count { assert frames::available(&POOL, i); }
    let retry = try! instances::create(&PACKAGES, &mut POOL, root);
    try testing::expect(*word(retry.table[root.index]) == 7);
    try! frames::release(&mut POOL, retry.frames);
}

kernel/kernel/tests/lifecycle.rad +11 -11

    });
    let base = ((&RAM[0]) as u64 + 4095) & ~4095;
    set MEMORY.backings.pool.count = 2;
    for i in 0..2 {
        set MEMORY.backings.pool.addresses[i] = base + i as u64 * 4096;
        set MEMORY.backings.pool.free[i] = true;
        set MEMORY.backings.pool.free[i / 64] |= 1 << (i % 64) as u64;
    }
    let reservation = try! pages::reserve(&mut MEMORY, &mut FIRST.table, authority, 2);
    let held = lifecycle::holdPage(&mut CALLS, &mut STORE, owner, reservation);
    assert STORE.contexts[0].reservation;
    lifecycle::clearPage(&CALLS, &held);
    lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
    assert not MEMORY.backings.pool.free[0] and not MEMORY.backings.pool.free[1];
    assert not frames::available(&MEMORY.backings.pool, 0) and not frames::available(&MEMORY.backings.pool, 1);
    set STORE.records[0].state = domains::Lifecycle::Dead;
    set STORE.contexts[0].state = domains::ContextState::Stopped;
    set STORE.contexts[0].hart = 0;
    lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
    assert not MEMORY.backings.pool.free[0];
    assert not frames::available(&MEMORY.backings.pool, 0);
    // Model the end of the stopped continuation before hart release.
    match held { case lifecycle::Lease::Held(context) => { assert context == owner; }, }
    set STORE.contexts[0].hart = nil;
    lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
    assert MEMORY.backings.pool.retiredCount == 1 and not MEMORY.backings.pool.free[0];
    assert MEMORY.backings.pool.retiredCount == 1 and not frames::available(&MEMORY.backings.pool, 0);
    assert frames::reclaim(&mut MEMORY.backings.pool, 256) == 2;
    assert MEMORY.backings.pool.free[0] and MEMORY.backings.pool.free[1];
    assert frames::available(&MEMORY.backings.pool, 0) and frames::available(&MEMORY.backings.pool, 1);
    assert MEMORY.slots[0].state == slots::State::Free;
    assert MEMORY.backings.slots[0].state == slots::State::Free;
    assert FIRST.table.slots[1].state == slots::State::Free and CALLS.active[0] == 0;
    assert not STORE.contexts[0].reservation;
    set STORE.records[0].state = domains::Lifecycle::Active;

    });
    let base = ((&RAM[0]) as u64 + 4095) & ~4095;
    set MEMORY.backings.pool.count = 2;
    for i in 0..2 {
        set MEMORY.backings.pool.addresses[i] = base + i as u64 * 4096;
        set MEMORY.backings.pool.free[i] = true;
        set MEMORY.backings.pool.free[i / 64] |= 1 << (i % 64) as u64;
    }
    let firstPage = try! pages::reserve(&mut MEMORY, &mut FIRST.table, authority, 1);
    let first = lifecycle::holdPage(&mut CALLS, &mut STORE, owner, firstPage);
    let secondPage = try! pages::reserve(&mut MEMORY, &mut FIRST.table, authority, 1);
    let other = lifecycle::holdPage(&mut CALLS, &mut STORE, second, secondPage);

    assert CALLS.active[0] == 2 and MEMORY.backings.pool.retiredCount == 1;
    assert not STORE.contexts[0].reservation and STORE.contexts[1].reservation;
    assert lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
    assert CALLS.active[0] == 0 and MEMORY.backings.pool.retiredCount == 2;
    assert not lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
    assert not MEMORY.backings.pool.free[0] and not MEMORY.backings.pool.free[1];
    assert not frames::available(&MEMORY.backings.pool, 0) and not frames::available(&MEMORY.backings.pool, 1);
    assert frames::reclaim(&mut MEMORY.backings.pool, 1) == 1;
    assert frames::reclaim(&mut MEMORY.backings.pool, 1) == 1;
    assert MEMORY.backings.pool.retiredCount == 0;
}


    let caller = abi::Ref { index: 0, generation: 1 };
    let target = abi::Ref { index: 1, generation: 1 };
    let base = ((&RAM[0]) as u64 + 4095) & ~4095;
    set MEMORY.backings.pool.count = 1;
    set MEMORY.backings.pool.addresses[0] = base;
    set MEMORY.backings.pool.free[0] = true;
    set MEMORY.backings.pool.free[0] |= 1;
    let slot = try! slots::reserve(&mut STORE.contextSlots[..]);
    let object = slots::reference(&slot);
    let run = frames::commit(try! frames::reserve(&mut MEMORY.backings.pool, 1));
    set STORE.contexts[object.index].owner = target;
    set STORE.contexts[object.index].kernelFrames = run;

    });
    let lease = lifecycle::holdContext(&mut CALLS, &mut STORE, caller, pending);
    lifecycle::clearContext(&CALLS, &lease);
    set STORE.records[1].state = domains::Lifecycle::Dead;
    lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
    assert STORE.contexts[0].reservation and not MEMORY.backings.pool.free[0];
    assert STORE.contexts[0].reservation and not frames::available(&MEMORY.backings.pool, 0);
    set STORE.records[0].state = domains::Lifecycle::Dead;
    set STORE.contexts[0].state = domains::ContextState::Stopped;
    set STORE.contexts[0].hart = 1;
    lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
    assert STORE.contextSlots[object.index].state == slots::State::Reserved;
    match lease { case lifecycle::Lease::Held(id) => { assert id == caller; }, }
    set STORE.contexts[0].hart = nil;
    lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
    assert MEMORY.backings.pool.retiredCount == 1 and not MEMORY.backings.pool.free[0];
    assert MEMORY.backings.pool.retiredCount == 1 and not frames::available(&MEMORY.backings.pool, 0);
    assert frames::reclaim(&mut MEMORY.backings.pool, 256) == 1;
    assert MEMORY.backings.pool.free[0];
    assert frames::available(&MEMORY.backings.pool, 0);
    assert STORE.contextSlots[object.index].state == slots::State::Free;
    assert not STORE.contexts[0].reservation and CALLS.active[0] == 0;
}

/// Dead contexts retain requests until hart release and completion of taken work.

kernel/kernel/tests/loader.rad +2 -2

    let aligned = (base + 4095) & ~4095;
    set OFFSET = (aligned - base) as u32;
    set PAGES.backings.pool.count = (@sizeOf([u64; 18874368]) - OFFSET) / 4096;
    for i in 0..PAGES.backings.pool.count {
        set PAGES.backings.pool.addresses[i] = aligned + i as u64 * 4096;
        set PAGES.backings.pool.free[i] = true;
        set PAGES.backings.pool.free[i / 64] |= 1 << (i % 64) as u64;
    }
    let owner = abi::Ref { index: 0, generation: 1 };
    capability::initialize(&mut TABLE, owner);
    try! backing::registerDomain(&mut PAGES.backings, owner);
    let authority = try! capability::install(&mut TABLE, capability::Entry {

}

/// Count available frames to detect leaked temporary or unpublished output storage.
unsafe fn free() -> u32 {
    let mut count: u32 = 0;
    for i in 0..PAGES.backings.pool.count { if PAGES.backings.pool.free[i] { set count += 1; } }
    for i in 0..PAGES.backings.pool.count { if frames::available(&PAGES.backings.pool, i) { set count += 1; } }
    return count;
}

/// Dead loaders retain private resources until hart release, then permit a retry.
@test unsafe fn cancelledCall() throws (testing::TestError) {

kernel/kernel/tests/pages.rad +16 -15

//! Page allocation, zeroing, split atomicity, and retained-pointer lifetimes.

use std::testing;
use kernel::abi;
use kernel::frames;
use kernel::capability;
use kernel::pages;
use kernel::backing;
use kernel::slots;
use kernel::limits;

    let aligned = (address + 4095) & ~4095;
    set OFFSET = (aligned - address) as u32;
    slots::initialize(&mut STORE.slots[..]);
    backing::initialize(&mut STORE.backings);
    set STORE.backings.pool.count = 8;
    for i in 0..8 { set STORE.backings.pool.addresses[i] = aligned + i as u64 * 4096; set STORE.backings.pool.free[i] = true; }
    for i in 0..8 { set STORE.backings.pool.addresses[i] = aligned + i as u64 * 4096; set STORE.backings.pool.free[i / 64] |= 1 << (i % 64) as u64; }
    let owner = abi::Ref { index: 0, generation: 1 };
    capability::initialize(&mut TABLE, owner);
    try! backing::registerDomain(&mut STORE.backings, owner);
    let authority = try! capability::install(&mut TABLE, capability::Entry {
        kind: abi::Kind::Domain, object: owner, rights: abi::Rights(abi::ALLOCATE),

@test unsafe fn stagedAllocation() throws (testing::TestError) {
    initialize();
    let pending = try! pages::reserve(&mut STORE, &mut TABLE, abi::Handle(0), 2);
    assert STORE.slots[0].state == slots::State::Reserved;
    assert TABLE.slots[1].state == slots::State::Reserved;
    assert not STORE.backings.pool.free[0] and not STORE.backings.pool.free[1];
    assert not frames::available(&STORE.backings.pool, 0) and not frames::available(&STORE.backings.pool, 1);
    assert RAM[OFFSET] == 0xa5;
    let other = try! pages::allocate(&mut STORE, &mut TABLE, abi::Handle(0), 6);
    set RAM[OFFSET + 8192] = 0x7b;
    pages::clear(&pending);
    for i in OFFSET..OFFSET + 8192 { assert RAM[i] == 0; }

    let entry = try! capability::get(&TABLE, handle);
    let page = try! pages::get(&STORE, entry.object);
    assert page.count == 2 and page.origin == TABLE.owner;
    drop(handle); drop(other);
    try! backing::endDomain(&mut STORE.backings, TABLE.owner);
    for i in 0..8 { assert STORE.backings.pool.free[i]; }
    for i in 0..8 { assert frames::available(&STORE.backings.pool, i); }
}

/// Cancelling unpublished storage returns all capacity without exposing its bytes.
@test unsafe fn cancelAllocation() throws (testing::TestError) {
    initialize();
    let pending = try! pages::reserve(&mut STORE, &mut TABLE, abi::Handle(0), 8);
    pages::cancel(&mut STORE, &mut TABLE, pending);
    assert STORE.slots[0].state == slots::State::Free;
    assert STORE.backings.slots[0].state == slots::State::Free;
    assert TABLE.slots[1].state == slots::State::Free;
    for i in 0..8 { assert STORE.backings.pool.free[i]; }
    for i in 0..8 { assert frames::available(&STORE.backings.pool, i); }
    assert RAM[OFFSET] == 0xa5;
    let full = try! pages::allocate(&mut STORE, &mut TABLE, abi::Handle(0), 8);
    let entry = try! capability::get(&TABLE, full);
    assert (try! pages::get(&STORE, entry.object)).count == 8;
}

    try testing::expect(page.handles == 1 and STORE.backings.records[page.backing.index].exposed == 2);
    let actual = try! capability::get(&TARGET, moved);
    try testing::expect(*actual.rights == abi::READ);
    try! pages::drop(&mut STORE, &mut TARGET, moved);
    try! backing::endDomain(&mut STORE.backings, receiver);
    try testing::expect(not STORE.backings.pool.free[0]);
    assert not frames::available(&STORE.backings.pool, 0);
    try! backing::endDomain(&mut STORE.backings, TABLE.owner);
    try testing::expect(STORE.backings.pool.free[0]);
    assert frames::available(&STORE.backings.pool, 0);
}

/// Grants acquire references only after capacity and receiver checks succeed.
@test unsafe fn grantRollback() throws (testing::TestError) {
    initialize();

    try testing::expect(STORE.records[entry.object.index].handles == 2);
    try testing::expect(STORE.backings.records[page.backing.index].exposed == 2);
    drop(original);
    try! pages::drop(&mut STORE, &mut TARGET, granted);
    try! backing::endDomain(&mut STORE.backings, TABLE.owner);
    try testing::expect(not STORE.backings.pool.free[0]);
    assert not frames::available(&STORE.backings.pool, 0);
    try! backing::endDomain(&mut STORE.backings, receiver);
    try testing::expect(STORE.backings.pool.free[0]);
    assert frames::available(&STORE.backings.pool, 0);
}

/// Self-attenuation adds one reference, preserves authority, and prevents splitting.
@test unsafe fn selfAttenuation() throws (testing::TestError) {
    initialize();

    try testing::expect(*none.rights == 0);
    drop(narrowed); drop(copy);
    let right = try! pages::split(&mut STORE, &mut TABLE, original, 1);
    drop(original); drop(right);
    try! backing::endDomain(&mut STORE.backings, TABLE.owner);
    try testing::expect(STORE.backings.pool.free[0] and STORE.backings.pool.free[1]);
    assert frames::available(&STORE.backings.pool, 0) and frames::available(&STORE.backings.pool, 1);
}

/// New allocations are zeroed completely and carry the documented default rights.
@test unsafe fn allocation() throws (testing::TestError) {
    initialize();

    for count in &[65537 as u64, 0xffffffffffffffff] {
        let mut exhausted = false;
        try pages::allocate(&mut STORE, &mut TABLE, abi::Handle(0), count) catch err {
            try testing::expect(err == abi::Error::OutOfMemory); set exhausted = true;
        };
        try testing::expect(exhausted and STORE.backings.pool.free[2]);
        assert exhausted and frames::available(&STORE.backings.pool, 2);
    }
}

/// Splitting preserves contents and backing identity while changing only page extents.
@test unsafe fn split() throws (testing::TestError) {

    try! pages::retain(&mut STORE, entry.object, receiver);
    set RAM[OFFSET] = 99;
    drop(handle);
    try! pages::release(&mut STORE, entry.object);
    try! backing::endDomain(&mut STORE.backings, TABLE.owner);
    try testing::expect(not STORE.backings.pool.free[0] and RAM[OFFSET] == 99);
    assert not frames::available(&STORE.backings.pool, 0) and RAM[OFFSET] == 99;
    try! backing::endDomain(&mut STORE.backings, receiver);
    try testing::expect(STORE.backings.pool.free[0]);
    assert frames::available(&STORE.backings.pool, 0);
    let owner = abi::Ref { index: 0, generation: 2 };
    capability::initialize(&mut TABLE, owner);
    try! backing::registerDomain(&mut STORE.backings, owner);
    let authority = try! capability::install(&mut TABLE, capability::Entry {
        kind: abi::Kind::Domain, object: owner, rights: abi::Rights(abi::ALLOCATE),

    };
    try pages::split(&mut STORE, &mut TABLE, handle, 2) catch err {
        try testing::expect(err == abi::Error::Exhausted); set failed += 1;
    };
    let page = try! pages::get(&STORE, entry.object);
    try testing::expect(failed == 2 and page.count == 4 and STORE.backings.pool.free[4]);
    assert failed == 2 and page.count == 4 and frames::available(&STORE.backings.pool, 4);
}

/// Failure at each storage stage releases all earlier reservations.
@test unsafe fn rollback() throws (testing::TestError) {
    initialize();

        }
        let mut exhausted = false;
        try pages::allocate(&mut STORE, &mut TABLE, abi::Handle(0), 1) catch err {
            try testing::expect(err == abi::Error::Exhausted); set exhausted = true;
        };
        try testing::expect(exhausted and TABLE.slots[1].state == slots::State::Free and STORE.backings.pool.free[0]);
        assert exhausted and TABLE.slots[1].state == slots::State::Free and frames::available(&STORE.backings.pool, 0);
        if stage == 0 { try testing::expect(STORE.slots[0].state == slots::State::Free); }
    }
}

/// A Domain handle with Allocate rights must name the caller to allocate RAM.

    });
    let mut denied = false;
    try pages::allocate(&mut STORE, &mut TABLE, other, 1) catch err {
        try testing::expect(err == abi::Error::Denied); set denied = true;
    };
    try testing::expect(denied and STORE.backings.pool.free[0] and TABLE.slots[2].state == slots::State::Free);
    assert denied and frames::available(&STORE.backings.pool, 0) and TABLE.slots[2].state == slots::State::Free;
}

/// Buffer authority covers complete ranges and rejects overflow and stale objects.
@test unsafe fn bufferAuthority() throws (testing::TestError) {
    initialize();

test/runtime/kernel/dispatchcheck.rad added +216 -0

1	+	//! Runtime compiler ownership across scheduled windows and domain destruction.
2	+	use std::mem;
3	+	use kernel::abi;
4	+	use kernel::frames;
5	+	use kernel::slots;
6	+	use kernel::backing;
7	+	use kernel::pages;
8	+	use kernel::capability;
9	+	use kernel::registry;
10	+	use kernel::loader;
11	+	use kernel::domains;
12	+	use kernel::budgets;
13	+	use kernel::dispatch;
14	+	use kernel::boot;
15	+	use kernel::sync;
16	+	use kernel::calls;
17	+	use kernel::lifecycle;
18	+	use kernel::remote;
19	+	use kernel::dispatchinput;
20	+
21	+	/// Bootstrap resource capabilities.
22	+	unsafe static TABLE: capability::Table = undefined;
23	+	/// First loader, retry loader, witness, and controller domain handles.
24	+	unsafe static HANDLES: [abi::Handle; 4] = undefined;
25	+	/// Generation-bearing domain identities for each actor.
26	+	unsafe static ACTORS: [abi::Ref; 4] = undefined;
27	+	/// Initial context identities for each actor.
28	+	unsafe static CONTEXTS: [abi::Ref; 4] = undefined;
29	+	/// Controller capability for the first loader.
30	+	unsafe static VICTIM: abi::Handle = undefined;
31	+	/// Controller capability for the binary input page.
32	+	unsafe static SOURCE: abi::Handle = undefined;
33	+	/// Shared user progress and published package identity.
34	+	unsafe static PROGRESS: *mut u64 = undefined;
35	+	/// Start of the controller's final execution window.
36	+	static FINAL: u64 = 0;
37	+	/// Write one diagnostic byte to the fixture UART.
38	+	fn put(byte: u8);
39	+	/// Write a fixed-width hexadecimal diagnostic value.
40	+	fn number(value: u64) {
41	+	let digits = "0123456789abcdef";
42	+	for i in 0..16 { put(digits[((value >> ((15 - i) as u64 * 4)) & 15) as u32]); }
43	+	}
44	+
45	+	/// Map a validated physical page.
46	+	fn memory(address: u64) -> *mut u8;
47	+	/// Current kernel package-state base.
48	+	fn kernelGp() -> u64;
49	+	/// Native controller entry address.
50	+	fn completion() -> u64;
51	+	/// Execute published code with one private package-state table.
52	+	fn invoke(address: u64, table: u64) -> i64;
53	+	/// Signal native fixture completion.
54	+	fn finish();
55	+
56	+	/// Copy trusted package bytes into a bootstrap-owned page allocation.
57	+	unsafe fn input(authority: abi::Handle, bytes: &[u8]) -> abi::Handle {
58	+	let handle = try! pages::allocate(&mut pages::STORE, &mut TABLE, authority, (bytes.len as u64 + 4095) / 4096);
59	+	let page = try! pages::get(&pages::STORE, (try! capability::get(&TABLE, handle)).object);
60	+	let copied = try! mem::copy(@sliceOf(memory(page.base), page.count * 4096), bytes);
61	+	assert copied == bytes.len;
62	+	return handle;
63	+	}
64	+
65	+	/// Install user actors and disjoint windows that interrupt two compiler calls.
66	+	export unsafe fn setup() {
67	+	let pending = try! slots::reserve(&mut domains::STORE.slots[..]);
68	+	let owner = try! slots::commit(&mut domains::STORE.slots[..], pending);
69	+	capability::initialize(&mut TABLE, owner);
70	+	try! backing::registerDomain(&mut pages::STORE.backings, owner);
71	+	let authority = try! capability::install(&mut TABLE, capability::Entry {
72	+	kind: abi::Kind::Domain, object: owner, rights: abi::Rights(abi::CREATE \| abi::ALLOCATE),
73	+	});
74	+	let source = input(authority, &dispatchinput::INPUT[..]);
75	+	let image = try! loader::load(&mut loader::STATE, &mut pages::STORE, &mut registry::STORE, &mut TABLE,
76	+	loader::Request { authority, source, offset: 0, length: dispatchinput::INPUT.len as u64 });
77	+	let payload = input(authority, &dispatchinput::PAYLOAD[..]);
78	+	let progress = try! pages::allocate(&mut pages::STORE, &mut TABLE, authority, 1);
79	+	let shared = try! pages::get(&pages::STORE, (try! capability::get(&TABLE, progress)).object);
80	+	set PROGRESS = memory(shared.base) as *mut u64;
81	+	for i in 0..4 {
82	+	let handle = try! domains::create(&mut domains::STORE, &mut pages::STORE.backings, &registry::STORE, &mut TABLE, authority, image);
83	+	let object = (try! capability::get(&TABLE, handle)).object;
84	+	let mut child = try! domains::get(&domains::STORE, object);
85	+	let mut rights = abi::ALLOCATE;
86	+	if i == 3 { set rights \|= abi::CREATE; }
87	+	let self = try! capability::install(&mut child.memory.table, capability::Entry {
88	+	kind: abi::Kind::Domain, object, rights: abi::Rights(rights),
89	+	});
90	+	set HANDLES[i] = handle; set ACTORS[i] = object; set CONTEXTS[i] = child.initial;
91	+	let readable = try! pages::grant(&mut pages::STORE, &TABLE, &mut child.memory.table, payload, abi::READ as u64);
92	+	let writable = try! pages::grant(&mut pages::STORE, &TABLE, &mut child.memory.table, progress, (abi::READ \| abi::WRITE) as u64);
93	+	if i == 3 {
94	+	set SOURCE = readable;
95	+	set VICTIM = try! capability::install(&mut child.memory.table, capability::Entry {
96	+	kind: abi::Kind::Domain, object: ACTORS[0], rights: abi::Rights(abi::DESTROY),
97	+	});
98	+	set domains::STORE.records[object.index].state = domains::Lifecycle::Active;
99	+	let frame = &mut domains::STORE.contexts[child.initial.index].frame;
100	+	set frame.pc = completion(); set frame.status = 0x1880;
101	+	set frame.registers[2] = domains::STORE.contexts[child.initial.index].kernelStack.end;
102	+	set frame.registers[3] = kernelGp();
103	+	continue;
104	+	}
105	+	let stack = try! pages::allocate(&mut pages::STORE, &mut TABLE, authority, 1);
106	+	let granted = try! pages::grant(&mut pages::STORE, &TABLE, &mut child.memory.table, stack, (abi::READ \| abi::WRITE) as u64);
107	+	let storage = try! pages::get(&pages::STORE, (try! capability::get(&TABLE, stack)).object);
108	+	let args = @sliceOf(memory(storage.base) as *mut u64, 3);
109	+	set args[0] = *readable; set args[1] = dispatchinput::PAYLOAD.len as u64; set args[2] = shared.base;
110	+	try! domains::activate(&mut domains::STORE, &pages::STORE, &TABLE, handle, storage.base + 4096, storage.base, i as u64);
111	+	}
112	+	for byte in "runtime actors ready\n" { put(byte); }
113	+	let now = dispatch::clock();
114	+	let start = now + 1000000;
115	+	set FINAL = start + 300000000;
116	+	let mut remaining = try! budgets::seed(&mut budgets::STORE, &mut TABLE, 0, start, FINAL + 10000000);
117	+	let actors = [0 as u32, 3, 1, 2, 1];
118	+	let ends = [10000000 as u64, 50000000, 60000000, 62000000, 300000000];
119	+	for i in 0..5 {
120	+	let next = try! budgets::split(&mut budgets::STORE, &mut TABLE, remaining, start + ends[i], now);
121	+	let actor = actors[i];
122	+	let bound = try! budgets::bind(&mut budgets::STORE, &domains::STORE, &mut TABLE,
123	+	budgets::Binding { budget: remaining, domain: HANDLES[actor], context: CONTEXTS[actor] }, now);
124	+	set remaining = next;
125	+	}
126	+	let bound = try! budgets::bind(&mut budgets::STORE, &domains::STORE, &mut TABLE,
127	+	budgets::Binding { budget: remaining, domain: HANDLES[3], context: CONTEXTS[3] }, now);
128	+	}
129	+
130	+	/// Verify cancellation, competing admission, progress, and resident code reuse.
131	+	export unsafe fn verify() {
132	+	for byte in "runtime admission metadata instructions: " { put(byte); }
133	+	number(sync::maximum()); put(10);
134	+	let progress = @sliceOf(PROGRESS, 4);
135	+	let guard = sync::enter();
136	+	let first = CONTEXTS[0];
137	+	for byte in "runtime first progress and owner: " { put(byte); }
138	+	number(progress[0]); put(32); number(abi::id(loader::STATE.owner)); put(10);
139	+	assert progress[0] == 1 and loader::STATE.busy and loader::STATE.owner == ACTORS[0];
140	+	assert domains::STORE.contexts[first.index].reservation;
141	+	assert (domains::STORE.contexts[first.index].frame.status & 0x1800) == 0x1800;
142	+	let allocation = lifecycle::CALLS.records[first.index].allocation;
143	+	let mut loading: lifecycle::Loading = undefined;
144	+	match allocation {
145	+	case lifecycle::Allocation::Load(value) => { set loading = value; },
146	+	else => panic "loader reservation required",
147	+	}
148	+	let output = loading.output else panic "compilation output required";
149	+	sync::leave(guard);
150	+	let mut busy = false;
151	+	try calls::synchronized(ACTORS[3], 51, &[0, *SOURCE, 0, dispatchinput::PAYLOAD.len as u64], dispatch::clock()) catch error {
152	+	assert error == abi::Error::Busy; set busy = true;
153	+	};
154	+	assert busy;
155	+	for byte in "runtime competing load rejected\n" { put(byte); }
156	+	let destroyed = try! calls::synchronized(ACTORS[3], 22, &[*VICTIM, 0, 0, 0], dispatch::clock());
157	+	assert destroyed == 0;
158	+	let checking = sync::enter();
159	+	let request = try! dispatch::request(0, remote::Action::Reschedule);
160	+	sync::leave(checking);
161	+	let result = try! dispatch::awaitRequest(0, request);
162	+	assert result == 0;
163	+	let cancelled = sync::enter();
164	+	assert not loader::STATE.busy;
165	+	assert (lifecycle::CALLS.active[first.index / 32] & (1 << (first.index % 32))) == 0;
166	+	assert registry::STORE.slots[output.object.index].state == slots::State::Free;
167	+	sync::leave(cancelled);
168	+	let mut reclaimed = false;
169	+	for attempt in 0..10000 {
170	+	let guard = sync::enter();
171	+	set reclaimed = pages::STORE.backings.pool.retiredCount == 0;
172	+	if reclaimed { sync::leave(guard); break; }
173	+	let request = try! dispatch::request(0, remote::Action::Reschedule);
174	+	sync::leave(guard);
175	+	let result = try! dispatch::awaitRequest(0, request);
176	+	assert result == 0;
177	+	}
178	+	assert reclaimed;
179	+	for run in [loading.input.frames, output.code, output.metadata] {
180	+	let mut offset: u32 = 0;
181	+	while offset < run.count {
182	+	let mut count = run.count - offset;
183	+	if count > 256 { set count = 256; }
184	+	let recovered = sync::enter();
185	+	for i in run.first + offset..run.first + offset + count { assert frames::available(&pages::STORE.backings.pool, i); }
186	+	sync::leave(recovered);
187	+	set offset += count;
188	+	}
189	+	}
190	+	for byte in "runtime cancellation passed\n" { put(byte); }
191	+	while dispatch::clock() < FINAL {}
192	+	let complete = sync::enter();
193	+	for byte in "runtime final progress: " { put(byte); }
194	+	for i in 0..4 { number(progress[i]); put(32); }
195	+	put(10);
196	+	assert progress[0] == 1 and progress[1] == 2 and progress[2] == 1;
197	+	assert not loader::STATE.busy;
198	+	let package = try! registry::get(&registry::STORE, abi::reference(progress[3]));
199	+	let entry = package.entry else panic "published entry required";
200	+	let mut controller = try! domains::get(&domains::STORE, ACTORS[3]);
201	+	let image = try! registry::install(&registry::STORE, &mut controller.memory.table, abi::reference(progress[3]));
202	+	sync::leave(complete);
203	+	let handle = abi::Handle(try! calls::synchronized(ACTORS[3], 20, &[0, *image, 0, 0], dispatch::clock()));
204	+	let created = sync::enter();
205	+	let object = (try! capability::get(&controller.memory.table, handle)).object;
206	+	let domain = try! domains::get(&domains::STORE, object);
207	+	sync::leave(created);
208	+	assert invoke(entry, domain.graph.table.ptr as u64) == 43;
209	+	assert invoke(entry, domain.graph.table.ptr as u64) == 85;
210	+	for byte in "runtime retry published executable code\n" { put(byte); }
211	+	let maximum = sync::maximum();
212	+	for byte in "runtime metadata instructions: " { put(byte); }
213	+	number(maximum); put(10);
214	+	assert maximum > 0 and maximum < 1000000;
215	+	finish();
216	+	}

test/runtime/machine.ras added +44 -0

1	+	//! Boot one hart and check user termination through production dispatch.
2	+	.text;
3	+	call @kernel::boot::initialize;
4	+	call @kernel::dispatchcheck::setup;
5	+	call @kernel::boot::run;
6	+	.export @kernel::dispatchcheck::memory;
7	+	.export @kernel::dispatchcheck::kernelGp;
8	+	.export @kernel::dispatchcheck::completion;
9	+	.export @kernel::dispatchcheck::finish;
10	+	@kernel::dispatchcheck::memory
11	+	ret;
12	+	@kernel::dispatchcheck::kernelGp
13	+	mv %a0 %gp;
14	+	ret;
15	+	@kernel::dispatchcheck::completion
16	+	la %a0 @complete;
17	+	ret;
18	+	@complete
19	+	call @kernel::dispatchcheck::verify;
20	+	ebreak;
21	+	@kernel::dispatchcheck::finish
22	+	li %t0 0x10001000;
23	+	li %t1 0x5555;
24	+	sw %t1 0(%t0);
25	+	ebreak;
26	+
27	+	.export @kernel::dispatchcheck::put;
28	+	@kernel::dispatchcheck::put
29	+	li %t0 0x10000000;
30	+	sb %a0 0(%t0);
31	+	ret;
32	+
33	+	.export @kernel::dispatchcheck::invoke;
34	+	// Preserve kernel state while calling one private instance of shared code.
35	+	@kernel::dispatchcheck::invoke
36	+	addi %sp %sp -16;
37	+	sd %ra 8(%sp);
38	+	sd %gp 0(%sp);
39	+	mv %gp %a1;
40	+	jalr %ra %a0 0;
41	+	ld %gp 0(%sp);
42	+	ld %ra 8(%sp);
43	+	addi %sp %sp 16;
44	+	ret;

test/runtime/run added +39 -0

1	+	#!/bin/sh
2	+	# Compile, cancel, and retry a package through scheduled user calls.
3	+	set -eu
4	+	emulator=${RAD_EMULATOR:-emulator}
5	+	fixture=runtime
6	+	work=$(mktemp -d)
7	+	trap 'rm -rf "$work"' EXIT HUP INT TERM
8	+	mkdir "$work/spin"
9	+	cp "test/$fixture/spin.rad" "$work/spin.rad"
10	+	cp kernel/kernel/abi.rad kernel/kernel/sys.rad "$work/spin/"
11	+	"$emulator" -memory-size=385024 -data-size=348160 -stack-size=512 -run bin/radiance.rv64.dev \
12	+	-pkg spin -mod "$work/spin.rad" -mod "$work/spin/abi.rad" -mod "$work/spin/sys.rad" -entry spin -ril "$work"
13	+	cp test/loader/loaded.rad "$work/loaded.rad"
14	+	index=0
15	+	while [ "$index" -lt 128 ]; do
16	+	printf '\n/// Compute a distinct exported value.\nexport fn value%s(input: u64) -> u64 { return input + %s; }\n' "$index" "$index" >> "$work/loaded.rad"
17	+	index=$((index + 1))
18	+	done
19	+	"$emulator" -memory-size=385024 -data-size=348160 -stack-size=512 -run bin/radiance.rv64.dev \
20	+	-pkg loaded -mod "$work/loaded.rad" -entry loaded -ril "$work"
21	+	cp kernel/kernel.rad "$work/kernel.rad"
22	+	printf '\nexport mod dispatchinput;\nexport mod dispatchcheck;\n' >> "$work/kernel.rad"
23	+	mkdir "$work/kernel"
24	+	cp kernel/kernel/*.rad "$work/kernel/"
25	+	cp "test/$fixture/kernel/dispatchcheck.rad" "$work/kernel/"
26	+	length=$(wc -c < "$work/spin.ril")
27	+	printf '//! Binary user loop.\n/// Complete trusted input package.\nexport static INPUT: [u8; %s] = [\n' "$length" > "$work/kernel/dispatchinput.rad"
28	+	od -An -v -tu1 "$work/spin.ril" \| awk '{ for (i = 1; i <= NF; i++) printf "%s,", $i; print "" }' >> "$work/kernel/dispatchinput.rad"
29	+	printf '];\n' >> "$work/kernel/dispatchinput.rad"
30	+	length=$(wc -c < "$work/loaded.ril")
31	+	printf '\n/// Package compiled by scheduled user calls.\nexport static PAYLOAD: [u8; %s] = [\n' "$length" >> "$work/kernel/dispatchinput.rad"
32	+	od -An -v -tu1 "$work/loaded.ril" \| awk '{ for (i = 1; i <= NF; i++) printf "%s,", $i; print "" }' >> "$work/kernel/dispatchinput.rad"
33	+	printf '];\n' >> "$work/kernel/dispatchinput.rad"
34	+	sh test/acceptance/compile "$emulator" "$work"
35	+	cat "test/$fixture/machine.ras" kernel/kernel/*.ras > "$work/dispatch.ras"
36	+	"$emulator" -memory-size=385024 -data-size=348160 -stack-size=512 -run bin/kernel.build.rv64 \
37	+	-- "$work/std.ril" "$work/kernel.ril" "$work/dispatch.ras" "$work/dispatch.rv64"
38	+	"$emulator" -machine -harts=1 -memory-size=262144 -max-steps=2000000000 -run "$work/dispatch.rv64"
39	+	printf 'runtime: scheduled cancellation, retry, and publication passed\n'

test/runtime/spin.rad added +53 -0

1	+	//! Scheduled runtime compilation and an independent window witness.
2	+	export mod abi;
3	+	export mod sys;
4	+
5	+	/// Startup fields used by the scheduled fixture.
6	+	record Request: Copy {
7	+	/// Readable binary package capability.
8	+	source: u64,
9	+	/// Complete binary package byte count.
10	+	length: u64,
11	+	/// Shared progress counters.
12	+	progress: *unsafe mut u64,
13	+	}
14	+
15	+	/// Values supplied at domain activation.
16	+	record Env: Copy {
17	+	/// Input handle, byte count, and shared progress address.
18	+	argsPointer: *Request,
19	+	/// Actor index selected by the parent.
20	+	argsSize: u64,
21	+	/// Event capability installed at creation.
22	+	eventsHandle: u64,
23	+	/// Shared event queue address.
24	+	eventsPointer: u64,
25	+	}
26	+
27	+	/// Compile a package twice or record progress during another domain's load.
28	+	@default unsafe fn main(env: *Env) {
29	+	let args = env.argsPointer;
30	+	let progress = @sliceOf(args.progress, 4);
31	+	let actor = env.argsSize as u32;
32	+	if actor == 2 {
33	+	assert progress[1] == 1;
34	+	let mut busy = false;
35	+	try sys::imageLoad(abi::Handle(0), abi::Handle(args.source), 0, args.length) catch error {
36	+	assert error == abi::Error::Busy; set busy = true;
37	+	};
38	+	assert busy;
39	+	set progress[2] = 1;
40	+	return;
41	+	}
42	+	set progress[actor] = 1;
43	+	let image = try sys::imageLoad(abi::Handle(0), abi::Handle(args.source), 0, args.length) catch error {
44	+	set progress[actor] = 100 + error as u64; return;
45	+	};
46	+	let info = try! sys::queryImage(image);
47	+	let repeated = try sys::imageLoad(abi::Handle(0), abi::Handle(args.source), 0, args.length) catch error {
48	+	set progress[actor] = 200 + error as u64; return;
49	+	};
50	+	assert (try! sys::queryImage(repeated)).id == info.id;
51	+	set progress[3] = info.id;
52	+	set progress[actor] = 2;
53	+	}

test/smp/kernel/dispatchcheck.rad +2 -1

//! One domain executing separate user contexts on every online hart.
use std::mem;
use std::arch::rv64::shared;
use kernel::abi;
use kernel::frames;
use kernel::slots;
use kernel::backing;
use kernel::pages;
use kernel::capability;
use kernel::registry;

    let guard = sync::enter();
    assert (lifecycle::CALLS.active[IDLE_CONTEXT.index / 32] & (1 << (IDLE_CONTEXT.index % 32))) == 0;
    assert pages::STORE.slots[allocation.page.index].state == slots::State::Free;
    assert pages::STORE.backings.slots[allocation.backing.index].state == slots::State::Free;
    for i in allocation.run.first..allocation.run.first + allocation.run.count {
        assert pages::STORE.backings.pool.free[i];
        assert frames::available(&pages::STORE.backings.pool, i);
    }
    sync::leave(guard);
    for byte in "smp cancelled preempted page allocation\n" { put(byte); }
}


220	220		# User exit, abort, and CPU faults preserve the surviving parent's execution.
221	221		termination-test: emulator $(RAD_BIN) $(BIN_DIR)/kernel.build.rv64
222	222		@RAD_EMULATOR="$(EMU)" sh test/dispatch/run termination
223	223
224	224		.PHONY: termination-test
	225	+
	226	+	# Scheduled compilation, cancellation, retry, and shared executable publication.
	227	+	runtime-test: emulator $(RAD_BIN) $(BIN_DIR)/kernel.build.rv64
	228	+	@RAD_EMULATOR="$(EMU)" sh test/runtime/run
	229	+
	230	+	.PHONY: runtime-test

296	297		let aligned = (base + 4095) & ~4095;
297	298		set OFFSET = ((aligned - base) / 8) as u32;
298	299		set pages::STORE.backings.pool.count = 4;
299	300		for i in 0..4 {
300	301		set pages::STORE.backings.pool.addresses[i] = aligned + i as u64 * 4096;
301		-	set pages::STORE.backings.pool.free[i] = true;
	302	+	set pages::STORE.backings.pool.free[i / 64] \|= 1 << (i % 64) as u64;
302	303		}
303	304		let pending = try! slots::reserve(&mut domains::STORE.slots[..]);
304	305		let owner = try! slots::commit(&mut domains::STORE.slots[..], pending);
305	306		try! backing::registerDomain(&mut pages::STORE.backings, owner);
306	307		capability::initialize(&mut MEMORY.table, owner);

264	264		assert not lifecycle::reapNext(&mut DOMAINS, &mut PAGES, &mut WINDOWS, &mut IRQS);
265	265		while PAGES.backings.pool.retiredCount > 0 {
266	266		let reclaimed = frames::reclaim(&mut PAGES.backings.pool, 256);
267	267		assert reclaimed > 0 and reclaimed <= 256;
268	268		}
269		-	assert not PAGES.backings.pool.free[run.first];
	269	+	assert not frames::available(&PAGES.backings.pool, run.first);
270	270		assert PAGES.backings.records[allocation.index].exposed == 1;
271	271		assert (try! pages::get(&PAGES, (try! capability::get(&parent.memory.table, shared)).object)).count == 1;
272	272		assert try! events::flush(&mut DOMAINS.events, receiver, &mut parent.memory.ring) == 1;
273	273		let event = try! events::pop(&mut parent.memory.ring) else panic "missing reaped child event";
274	274		assert event.value == abi::id(target) and event.code == 19;

283	283		assert DOMAINS.slots[receiver.index].state == slots::State::Free;
284	284		while PAGES.backings.pool.retiredCount > 0 {
285	285		let reclaimed = frames::reclaim(&mut PAGES.backings.pool, 256);
286	286		assert reclaimed > 0 and reclaimed <= 256;
287	287		}
288		-	for i in 0..PAGES.backings.pool.count { assert PAGES.backings.pool.free[i]; }
	288	+	for i in 0..PAGES.backings.pool.count { assert frames::available(&PAGES.backings.pool, i); }
289	289		}
290	290
291	291		/// Initial return reports to the current parent and retains its terminal identity.
292	292		@test unsafe fn terminalParent() throws (testing::TestError) {
293	293		initialize(abi::CREATE);

478	478		};
479	479		assert overlap;
480	480		let reservedFrames = DOMAINS.contexts[index].kernelFrames;
481	481		domains::contextCancel(&mut DOMAINS, &mut PAGES, reserved);
482	482		assert DOMAINS.contextSlots[index].state == slots::State::Free;
483		-	for i in reservedFrames.first..reservedFrames.first + reservedFrames.count { assert PAGES.backings.pool.free[i]; }
	483	+	for i in reservedFrames.first..reservedFrames.first + reservedFrames.count { assert frames::available(&PAGES.backings.pool, i); }
484	484		let pendingContext = try! domains::contextReserve(&mut DOMAINS, &mut PAGES, &PACKAGES, &TABLE, handle, start);
485	485		let stackBase = DOMAINS.contexts[index].kernelStack.start;
486	486		let base = (&RAM[0]) as u64;
487	487		let firstWord = ((stackBase - base) / 8) as u32;
488	488		let lastWord = firstWord + domains::KERNEL_STACK_PAGES * 512 - 1;

21	21
22	22		# Verify the emulator binary exists.
23	23		EMU_PATH := $(shell command -v $(EMU) 2>/dev/null)
24	24
25	25		default: emulator $(RAD_BIN)
26		-	test: emulator seed-test std-test bin-test kernel-test module-test package-test native-test shared-test sync-test kernel-boot-test trap-test page-test loader-test dispatch-test smp-test termination-test
	26	+	test: emulator seed-test std-test bin-test kernel-test module-test package-test native-test shared-test sync-test kernel-boot-test trap-test page-test loader-test dispatch-test smp-test termination-test runtime-test
27	27
28	28		seed-test:
29	29		@seed/test
30	30
31	31		module-test: emulator $(RAD_BIN)

21	21
22	22		/// Physical addresses and occupancy of allocatable frames, sorted by address.
23	23		export record Pool: Copy {
24	24		/// Physical base address of each eligible frame.
25	25		addresses: [u64; limits::FRAMES],
26		-	/// True when the frame is available for reservation.
27		-	free: [bool; limits::FRAMES],
	26	+	/// One set bit per available frame, indexed from the low bit of each word.
	27	+	free: [u64; limits::FRAMES / 64],
28	28		/// Number of valid frame-map entries.
29	29		count: u32,
30	30		/// Retired runs whose frames remain unavailable until reclamation.
31	31		retired: [Run; limits::FRAMES],
32	32		/// Index of the next retired run to reclaim.

46	46
47	47		/// Build a fresh frame map from complete RAM pages with no reserved byte.
48	48		/// The pool has zero valid entries if initialization fails.
49	49		export unsafe fn initialize(pool: &mut Pool, machine: &platform::Platform) throws (abi::Error) {
50	50		set pool.count = 0;
	51	+	set pool.free = [0; limits::FRAMES / 64];
51	52		set pool.retiredHead = 0;
52	53		set pool.retiredCount = 0;
53	54		if machine.ramCount > platform::RAM_BANKS or machine.reservedCount > platform::RESERVATIONS {
54	55		throw abi::Error::InvalidArg;
55	56		}

81	82		set address = (reserved[next].end + limits::FRAME_SIZE - 1) & ~(limits::FRAME_SIZE - 1);
82	83		continue;
83	84		}
84	85		if count == limits::FRAMES { throw abi::Error::Exhausted; }
85	86		set pool.addresses[count] = address;
86		-	set pool.free[count] = true;
	87	+	set pool.free[count / 64] \|= 1 << (count % 64) as u64;
87	88		set count += 1;
88	89		set address += limits::FRAME_SIZE;
89	90		}
90	91		}
91	92		set pool.count = count;
92	93		}
93	94
94		-	/// Reserve the first physically contiguous free run with a bounded scan.
	95	+	/// Test one valid frame's availability without exposing unused bitmap bits.
	96	+	export fn available(pool: &Pool, index: u32) -> bool {
	97	+	return index < pool.count and (pool.free[index / 64] & (1 << (index % 64) as u64)) <> 0;
	98	+	}
	99	+
	100	+	/// Low bits selected by a nonzero word-sized span.
	101	+	fn mask(count: u32) -> u64 {
	102	+	assert count > 0 and count <= 64;
	103	+	if count == 64 { return 0xffffffffffffffff; }
	104	+	return (1 << count as u64) - 1;
	105	+	}
	106	+
	107	+	/// Change a validated run's occupancy one bitmap word at a time.
	108	+	fn assign(pool: &mut Pool, run: Run, free: bool) {
	109	+	let mut first = run.first;
	110	+	let end = first + run.count;
	111	+	while first < end {
	112	+	let offset = first % 64;
	113	+	let mut count = 64 - offset;
	114	+	if count > end - first { set count = end - first; }
	115	+	let bits = mask(count) << offset as u64;
	116	+	if free { set pool.free[first / 64] \|= bits; }
	117	+	else { set pool.free[first / 64] &= ~bits; }
	118	+	set first += count;
	119	+	}
	120	+	}
	121	+
	122	+	/// Reserve the first contiguous run, scanning uniform bitmap words together.
95	123		export fn reserve(pool: &mut Pool, count: u32) -> Reservation throws (abi::Error) {
96	124		if count == 0 { throw abi::Error::InvalidArg; }
97	125		let mut first: u32 = 0;
98	126		let mut found: u32 = 0;
99	127		let mut previous: u64 = 0;
100		-	for i in 0..pool.count {
101		-	if not pool.free[i] { set found = 0; continue; }
102		-	if found == 0 or pool.addresses[i] <> previous + limits::FRAME_SIZE { set first = i; set found = 0; }
103		-	set found += 1;
104		-	set previous = pool.addresses[i];
105		-	if found == count {
106		-	for j in first..first + count { set pool.free[j] = false; }
107		-	return Reservation::Held(Run { first, count });
	128	+	for word in 0..(pool.count + 63) / 64 {
	129	+	let base = word * 64;
	130	+	let mut length = pool.count - base;
	131	+	if length > 64 { set length = 64; }
	132	+	let full = mask(length);
	133	+	let bits = pool.free[word] & full;
	134	+	if bits == 0 { set found = 0; continue; }
	135	+	let address = pool.addresses[base];
	136	+	if bits == full and pool.addresses[base + length - 1] - address == (length - 1) as u64 * limits::FRAME_SIZE {
	137	+	if found == 0 or address <> previous + limits::FRAME_SIZE { set first = base; set found = 0; }
	138	+	set found += length;
	139	+	set previous = pool.addresses[base + length - 1];
	140	+	} else {
	141	+	for offset in 0..length {
	142	+	let i = base + offset;
	143	+	if (bits & (1 << offset as u64)) == 0 { set found = 0; continue; }
	144	+	if found == 0 or pool.addresses[i] <> previous + limits::FRAME_SIZE { set first = i; set found = 0; }
	145	+	set found += 1;
	146	+	set previous = pool.addresses[i];
	147	+	if found >= count { break; }
	148	+	}
	149	+	}
	150	+	if found >= count {
	151	+	let run = Run { first, count };
	152	+	assign(pool, run, false);
	153	+	return Reservation::Held(run);
108	154		}
109	155		}
110	156		throw abi::Error::OutOfMemory;
111	157		}
112	158

127	173
128	174		/// Return a backing allocation's frames after all handles and exposures end.
129	175		/// Only the owner of a committed run may release it.
130	176		export fn release(pool: &mut Pool, run: Run) throws (abi::Error) {
131	177		let memory = try extent(pool, run);
132		-	for i in run.first..run.first + run.count { if pool.free[i] { throw abi::Error::BadHandle; } }
133		-	for i in run.first..run.first + run.count { set pool.free[i] = true; }
	178	+	let mut first = run.first;
	179	+	let end = first + run.count;
	180	+	while first < end {
	181	+	let offset = first % 64;
	182	+	let mut count = 64 - offset;
	183	+	if count > end - first { set count = end - first; }
	184	+	if (pool.free[first / 64] & (mask(count) << offset as u64)) <> 0 { throw abi::Error::BadHandle; }
	185	+	set first += count;
	186	+	}
	187	+	assign(pool, run, true);
134	188		}
135	189
136	190		/// Transfer exclusive ownership of a committed run to bounded reclamation.
137	191		/// The caller must not release or retire this run again.
138	192		export fn retire(pool: &mut Pool, run: Run) throws (abi::Error) {

13	13		unsafe fn initialize() {
14	14		backing::initialize(&mut STORE);
15	15		try! backing::registerDomain(&mut STORE, abi::Ref { index: 0, generation: 1 });
16	16		try! backing::registerDomain(&mut STORE, abi::Ref { index: 1, generation: 1 });
17	17		set STORE.pool.count = 4;
18		-	for i in 0..4 { set STORE.pool.addresses[i] = 0x80000000 + i as u64 * 4096; set STORE.pool.free[i] = true; }
	18	+	for i in 0..4 { set STORE.pool.addresses[i] = 0x80000000 + i as u64 * 4096; set STORE.pool.free[i / 64] \|= 1 << (i % 64) as u64; }
19	19		}
20	20
21	21		/// Publish one backing record with its initial page and origin exposure.
22	22		unsafe fn allocate() -> abi::Ref {
23	23		let slot = try! slots::reserve(&mut STORE.slots[..]);

47	47		};
48	48		assert invalid and backing::domainLive(&STORE, owner);
49	49		assert not try! backing::endDomainStep(&mut STORE, owner, 1);
50	50		assert not backing::domainLive(&STORE, owner);
51	51		assert STORE.slots[objects[0].index].state == slots::State::Free;
52		-	assert STORE.pool.retiredCount == 1 and not STORE.pool.free[0];
	52	+	assert STORE.pool.retiredCount == 1 and not frames::available(&STORE.pool, 0);
53	53		assert STORE.records[objects[1].index].exposed == 2;
54	54		let mut busy = false;
55	55		try backing::registerDomain(&mut STORE, abi::Ref { index: 0, generation: 2 }) catch error {
56	56		assert error == abi::Error::Busy; set busy = true;
57	57		};

65	65		assert STORE.records[objects[1].index].exposed == 1;
66	66		assert STORE.records[objects[2].index].exposed == 1;
67	67		while not try! backing::endDomainStep(&mut STORE, owner, 64) {}
68	68		assert STORE.records[objects[2].index].exposed == 0 and STORE.records[objects[2].index].pages == 1;
69	69		assert STORE.pool.retiredCount == 1;
70		-	assert frames::reclaim(&mut STORE.pool, 1) == 1 and STORE.pool.free[0];
71		-	assert not STORE.pool.free[1] and not STORE.pool.free[2];
	70	+	assert frames::reclaim(&mut STORE.pool, 1) == 1 and frames::available(&STORE.pool, 0);
	71	+	assert not frames::available(&STORE.pool, 1) and not frames::available(&STORE.pool, 2);
72	72		let next = abi::Ref { index: 0, generation: 2 };
73	73		try! backing::registerDomain(&mut STORE, next);
74	74		assert backing::domainLive(&STORE, next);
75	75		let mut stale = false;
76	76		try backing::endDomainStep(&mut STORE, owner, 64) catch error {
77	77		assert error == abi::Error::BadHandle; set stale = true;
78	78		};
79	79		assert stale and backing::domainLive(&STORE, next);
80	80		try! backing::releasePage(&mut STORE, objects[2]);
81		-	assert STORE.pool.free[2];
	81	+	assert frames::available(&STORE.pool, 2);
82	82		while not try! backing::endDomainStep(&mut STORE, receiver, 64) {}
83		-	assert STORE.pool.retiredCount == 1 and not STORE.pool.free[1];
84		-	assert frames::reclaim(&mut STORE.pool, 1) == 1 and STORE.pool.free[1];
	83	+	assert STORE.pool.retiredCount == 1 and not frames::available(&STORE.pool, 1);
	84	+	assert frames::reclaim(&mut STORE.pool, 1) == 1 and frames::available(&STORE.pool, 1);
85	85		}
86	86
87	87		/// Dropping all page handles preserves capacity while an exposed domain lives.
88	88		@test unsafe fn exposures() throws (testing::TestError) {
89	89		initialize();

92	92		try! backing::expose(&mut STORE, object, receiver);
93	93		try! backing::expose(&mut STORE, object, receiver);
94	94		try testing::expect(STORE.records[object.index].exposed == 2);
95	95		try! backing::releasePage(&mut STORE, object);
96	96		try! backing::endDomain(&mut STORE, abi::Ref { index: 0, generation: 1 });
97		-	try testing::expect(not STORE.pool.free[0] and slots::matches(&STORE.slots[..], object, slots::State::Live));
	97	+	assert not frames::available(&STORE.pool, 0) and slots::matches(&STORE.slots[..], object, slots::State::Live);
98	98		try! backing::endDomain(&mut STORE, receiver);
99		-	for i in 0..4 { try testing::expect(STORE.pool.free[i]); }
	99	+	for i in 0..4 { assert frames::available(&STORE.pool, i); }
100	100		try testing::expect(not slots::matches(&STORE.slots[..], object, slots::State::Live));
101	101		}
102	102
103	103		/// Splits keep their common backing alive until every page object is gone.
104	104		@test unsafe fn splitLifetime() throws (testing::TestError) {
105	105		initialize();
106	106		let object = allocate();
107	107		try! backing::retainPage(&mut STORE, object);
108	108		try! backing::endDomain(&mut STORE, abi::Ref { index: 0, generation: 1 });
109	109		try! backing::releasePage(&mut STORE, object);
110		-	try testing::expect(not STORE.pool.free[0] and STORE.records[object.index].pages == 1);
	110	+	assert not frames::available(&STORE.pool, 0) and STORE.records[object.index].pages == 1;
111	111		try! backing::releasePage(&mut STORE, object);
112		-	try testing::expect(STORE.pool.free[0]);
	112	+	assert frames::available(&STORE.pool, 0);
113	113		let mut stale = false;
114	114		try backing::releasePage(&mut STORE, object) catch err {
115	115		try testing::expect(err == abi::Error::BadHandle); set stale = true;
116	116		};
117	117		try testing::expect(stale);

130	130		try testing::expect(err == abi::Error::BadHandle); set stale = true;
131	131		};
132	132		try testing::expect(stale and STORE.records[object.index].exposed == 1);
133	133		try! backing::releasePage(&mut STORE, object);
134	134		try! backing::endDomain(&mut STORE, abi::Ref { index: 0, generation: 1 });
135		-	try testing::expect(STORE.pool.free[0]);
	135	+	assert frames::available(&STORE.pool, 0);
136	136		}
137	137
138	138		/// Retained backing metadata cannot create new page authority after the last page ends.
139	139		@test unsafe fn noResurrection() throws (testing::TestError) {
140	140		initialize();

147	147		try backing::expose(&mut STORE, object, abi::Ref { index: 1, generation: 1 }) catch err {
148	148		try testing::expect(err == abi::Error::BadHandle); set failures += 1;
149	149		};
150	150		try testing::expect(failures == 2 and STORE.records[object.index].exposed == 1);
151	151		try! backing::endDomain(&mut STORE, abi::Ref { index: 0, generation: 1 });
152		-	try testing::expect(STORE.pool.free[0]);
	152	+	assert frames::available(&STORE.pool, 0);
153	153		}

1	1		//! Direct-call scalar results, checked record copies, and architectural replies.
2	2
3	3		use std::testing;
4	4		use kernel::abi;
	5	+	use kernel::frames;
5	6		use kernel::calls;
6	7		use kernel::domains;
7	8		use kernel::pages;
8	9		use kernel::backing;
9	10		use kernel::capability;

49	49		let base = pointer as u64;
50	50		let aligned = (base + 4095) & ~4095;
51	51		set BACKINGS.pool.count = (@sizeOf([u64; 131072]) - (aligned - base) as u32) / 4096;
52	52		for i in 0..BACKINGS.pool.count {
53	53		set BACKINGS.pool.addresses[i] = aligned + i as u64 * 4096;
54		-	set BACKINGS.pool.free[i] = true;
	54	+	set BACKINGS.pool.free[i / 64] \|= 1 << (i % 64) as u64;
55	55		}
56	56		let pending = try! slots::reserve(&mut DOMAINS.slots[..]);
57	57		let owner = try! slots::commit(&mut DOMAINS.slots[..], pending);
58	58		set DOMAINS.records[owner.index].state = domains::Lifecycle::Active;
59	59		set DOMAINS.records[owner.index].parent = nil;

98	98		set DOMAINS.records[permit.object.index].state = domains::Lifecycle::Dead;
99	99		set DOMAINS.contexts[caller.initial.index].state = domains::ContextState::Stopped;
100	100		set DOMAINS.contexts[caller.initial.index].hart = 1;
101	101		lifecycle::cancelAllocations(&mut CALLS, &mut DOMAINS, &mut PAGES, &mut loader::STATE, &mut registry::STORE);
102	102		assert DOMAINS.contexts[caller.initial.index].reservation;
103		-	assert not PAGES.backings.pool.free[creation.storage.allocation.first];
	103	+	assert not frames::available(&PAGES.backings.pool, creation.storage.allocation.first);
104	104		match lease { case lifecycle::Lease::Held(context) => { assert context == caller.initial; }, }
105	105		set DOMAINS.contexts[caller.initial.index].hart = nil;
106	106		lifecycle::cancelAllocations(&mut CALLS, &mut DOMAINS, &mut PAGES, &mut loader::STATE, &mut registry::STORE);
107	107		assert not DOMAINS.contexts[caller.initial.index].reservation;
108	108		assert DOMAINS.slots[creation.domain.index].state == slots::State::Free;

561	561		try domains::contextDestroy(&mut DOMAINS, &mut PAGES, &TABLE, handle, context) catch error {
562	562		assert error == abi::Error::Busy; set retained = true;
563	563		};
564	564		assert retained and DOMAINS.contextSlots[context.index].state == slots::State::Live;
565	565		for i in created.kernelFrames.first..created.kernelFrames.first + created.kernelFrames.count {
566		-	assert not PAGES.backings.pool.free[i];
	566	+	assert not frames::available(&PAGES.backings.pool, i);
567	567		}
568	568		set DOMAINS.contexts[context.index].pending = nil;
569	569		set DOMAINS.contexts[context.index].reservation = true;
570	570		set retained = false;
571	571		try domains::contextDestroy(&mut DOMAINS, &mut PAGES, &TABLE, handle, context) catch error {

573	573		};
574	574		assert retained and DOMAINS.contextSlots[context.index].state == slots::State::Live;
575	575		set DOMAINS.contexts[context.index].reservation = false;
576	576		try! domains::contextDestroy(&mut DOMAINS, &mut PAGES, &TABLE, handle, context);
577	577		for i in created.kernelFrames.first..created.kernelFrames.first + created.kernelFrames.count {
578		-	try testing::expect(PAGES.backings.pool.free[i]);
	578	+	assert frames::available(&PAGES.backings.pool, i);
579	579		}
580	580		try domains::context(&DOMAINS, authority.object, context) catch error {
581	581		try testing::expect(error == abi::Error::BadHandle); set rejected += 1;
582	582		};
583	583		let next = try! domains::contextCreate(&mut DOMAINS, &mut PAGES, &PACKAGES, &TABLE, handle, start);

651	651		let cancelled = try! domains::reserve(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE);
652	652		domains::cancel(&mut DOMAINS, &mut BACKINGS, &mut TABLE, cancelled);
653	653		assert DOMAINS.slots[1].state == slots::State::Free;
654	654		assert DOMAINS.contextSlots[0].state == slots::State::Free;
655	655		assert TABLE.slots[2].state == slots::State::Free;
656		-	for i in 0..BACKINGS.pool.count { assert BACKINGS.pool.free[i]; }
	656	+	for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
657	657		set PACKAGES.entries[0].package.relocations = &[shared::Relocation {
658	658		offset: 0, count: 1, target: shared::DataRef { slot: 5, offset: 0 },
659	659		}];
660	660		let mut invalid = false;
661	661		try domains::create(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE) catch error {
662	662		assert error == abi::Error::VerifyFailed; set invalid = true;
663	663		};
664	664		assert invalid and DOMAINS.slots[1].state == slots::State::Free;
665		-	for i in 0..BACKINGS.pool.count { assert BACKINGS.pool.free[i]; }
	665	+	for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
666	666		initialize(abi::CREATE);
667	667		let abandoned = try! domains::reserve(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE);
668	668		try! domains::prepare(&PACKAGES, &abandoned);
669	669		try! backing::endDomain(&mut BACKINGS, TABLE.owner);
670	670		let mut dead = false;
671	671		try domains::publish(&mut DOMAINS, &mut BACKINGS, &mut TABLE, abandoned) catch error {
672	672		assert error == abi::Error::BadHandle; set dead = true;
673	673		};
674	674		assert dead and DOMAINS.slots[1].state == slots::State::Free;
675	675		assert TABLE.slots[2].state == slots::State::Free;
676		-	for i in 0..BACKINGS.pool.count { assert BACKINGS.pool.free[i]; }
	676	+	for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
677	677		}
678	678
679	679		/// Creation installs only Events in the child and preserves selected authorizing rights.
680	680		@test unsafe fn pending() throws (testing::TestError) {
681	681		initialize(abi::CREATE \| abi::ALLOCATE);

706	706		let mut rejected = false;
707	707		try domains::create(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE) catch err {
708	708		try testing::expect(err == expected); set rejected = true;
709	709		};
710	710		try testing::expect(rejected);
711		-	for i in 0..BACKINGS.pool.count { try testing::expect(BACKINGS.pool.free[i]); }
	711	+	for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
712	712		try testing::expect(DOMAINS.slots[1].state == slots::State::Free);
713	713		try testing::expect(DOMAINS.contextSlots[0].state == slots::State::Free);
714	714		try testing::expect(TABLE.slots[2].state == slots::State::Free);
715	715		try testing::expect(BACKINGS.domains[1] == 0);
716	716		}

743	743		try domains::create(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE) catch err {
744	744		try testing::expect(err == abi::Error::Exhausted); set rejected = true;
745	745		};
746	746		try testing::expect(rejected and DOMAINS.slots[1].state == slots::State::Free);
747	747		try testing::expect(TABLE.slots[2].state == slots::State::Free);
748		-	for i in 0..BACKINGS.pool.count { try testing::expect(BACKINGS.pool.free[i]); }
	748	+	for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
749	749		}
750	750
751	751		/// A creator can grant Create without Allocate and the next creation preserves that choice.
752	752		@test unsafe fn selectiveAuthority() throws (testing::TestError) {
753	753		initialize(abi::CREATE \| abi::ALLOCATE);

795	795		let mut failures: u32 = 0;
796	796		try domains::create(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE) catch err {
797	797		try testing::expect(err == abi::Error::Exhausted); set failures += 1;
798	798		};
799	799		try testing::expect(DOMAINS.slots[1].state == slots::State::Free);
800		-	for i in 0..BACKINGS.pool.count { try testing::expect(BACKINGS.pool.free[i]); }
	800	+	for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
801	801		initialize(abi::CREATE);
802	802		for i in 1..DOMAINS.slots.len { set DOMAINS.slots[i].state = slots::State::Retired; }
803	803		try domains::create(&mut DOMAINS, &mut BACKINGS, &PACKAGES, &mut TABLE, abi::Handle(0), IMAGE) catch err {
804	804		try testing::expect(err == abi::Error::Exhausted); set failures += 1;
805	805		};
806	806		try testing::expect(failures == 2 and TABLE.slots[2].state == slots::State::Free);
807	807		try testing::expect(DOMAINS.contextSlots[0].state == slots::State::Free);
808		-	for i in 0..BACKINGS.pool.count { try testing::expect(BACKINGS.pool.free[i]); }
	808	+	for i in 0..BACKINGS.pool.count { assert frames::available(&BACKINGS.pool, i); }
809	809		}

18	18		set machine.reservedCount = 1;
19	19		set machine.reserved[0] = range::Range { start: 0x80003000, end: 0x80005000 };
20	20		try! frames::initialize(&mut POOL, &machine);
21	21		}
22	22
	23	+	/// Bitmap allocation agrees with a scalar scan across holes and word boundaries.
	24	+	@test unsafe fn bitmapRuns() throws (testing::TestError) {
	25	+	let mut machine: platform::Platform = undefined;
	26	+	set machine.ramCount = 1;
	27	+	set machine.ram[0] = range::Range { start: 0x80000000, end: 0x800c2000 };
	28	+	set machine.reservedCount = 1;
	29	+	set machine.reserved[0] = range::Range { start: 0x8001f000, end: 0x80020000 };
	30	+	for pattern in 0..5 {
	31	+	for count in [1 as u32, 2, 31, 32, 63, 64, 65, 127, 128, 129, 193, 194] {
	32	+	try! frames::initialize(&mut POOL, &machine);
	33	+	assert POOL.count == 193;
	34	+	for i in 0..POOL.count {
	35	+	if pattern > 0 and i % (pattern * 32) == 0 {
	36	+	set POOL.free[i / 64] &= ~(1 << (i % 64) as u64);
	37	+	}
	38	+	}
	39	+	// Padding bits are outside the pool even when their values are set.
	40	+	set POOL.free[3] \|= 0xfffffffffffffffe;
	41	+	let before = [POOL.free[0], POOL.free[1], POOL.free[2], POOL.free[3]];
	42	+	let mut expected: ?u32 = nil;
	43	+	let mut found: u32 = 0;
	44	+	for i in 0..POOL.count {
	45	+	if not frames::available(&POOL, i) { set found = 0; continue; }
	46	+	if found > 0 and POOL.addresses[i] <> POOL.addresses[i - 1] + 4096 { set found = 0; }
	47	+	set found += 1;
	48	+	if found == count { set expected = i + 1 - count; break; }
	49	+	}
	50	+	let reservation = try frames::reserve(&mut POOL, count) catch error {
	51	+	assert expected == nil and error == abi::Error::OutOfMemory;
	52	+	for i in 0..4 { assert POOL.free[i] == before[i]; }
	53	+	continue;
	54	+	};
	55	+	let first = expected else panic "unexpected frame reservation";
	56	+	let run = frames::commit(reservation);
	57	+	assert run.first == first and run.count == count;
	58	+	for i in 0..POOL.count {
	59	+	if i >= first and i - first < count { assert not frames::available(&POOL, i); }
	60	+	else { assert frames::available(&POOL, i) == ((before[i / 64] & (1 << (i % 64) as u64)) <> 0); }
	61	+	}
	62	+	try! frames::release(&mut POOL, run);
	63	+	for i in 0..4 { assert POOL.free[i] == before[i]; }
	64	+	}
	65	+	}
	66	+	assert not frames::available(&POOL, POOL.count);
	67	+	try! frames::initialize(&mut POOL, &machine);
	68	+	let run = frames::commit(try! frames::reserve(&mut POOL, 128));
	69	+	assert run.first == 31;
	70	+	let before = [POOL.free[0], POOL.free[1], POOL.free[2], POOL.free[3]];
	71	+	let mut invalid = false;
	72	+	try frames::release(&mut POOL, frames::Run { first: run.first, count: 129 }) catch error {
	73	+	assert error == abi::Error::BadHandle; set invalid = true;
	74	+	};
	75	+	assert invalid;
	76	+	for i in 0..4 { assert POOL.free[i] == before[i]; }
	77	+	try! frames::release(&mut POOL, run);
	78	+	}
	79	+
23	80		/// Retired frames stay unavailable until bounded reclamation returns them.
24	81		@test unsafe fn retirement() throws (testing::TestError) {
25	82		initialize();
26	83		set POOL.retiredHead = limits::FRAMES - 1;
27	84		let left = frames::commit(try! frames::reserve(&mut POOL, 3));
28	85		let right = frames::commit(try! frames::reserve(&mut POOL, 5));
29	86		try! frames::retire(&mut POOL, left);
30	87		try! frames::retire(&mut POOL, right);
31	88		assert POOL.retiredCount == 2;
32		-	for i in 0..8 { assert not POOL.free[i]; }
	89	+	for i in 0..8 { assert not frames::available(&POOL, i); }
33	90		assert frames::reclaim(&mut POOL, 0) == 0;
34	91		assert frames::reclaim(&mut POOL, 2) == 2;
35		-	assert POOL.free[0] and POOL.free[1] and not POOL.free[2];
	92	+	assert frames::available(&POOL, 0) and frames::available(&POOL, 1) and not frames::available(&POOL, 2);
36	93		let reused = frames::commit(try! frames::reserve(&mut POOL, 2));
37	94		assert reused.first == 0;
38	95		assert frames::reclaim(&mut POOL, 3) == 3;
39		-	assert POOL.retiredCount == 1 and not POOL.free[5];
40		-	assert not POOL.free[0] and not POOL.free[1];
	96	+	assert POOL.retiredCount == 1 and not frames::available(&POOL, 5);
	97	+	assert not frames::available(&POOL, 0) and not frames::available(&POOL, 1);
41	98		try! frames::retire(&mut POOL, reused);
42	99		assert frames::reclaim(&mut POOL, 20) == 5;
43	100		assert POOL.retiredCount == 0;
44		-	for i in 0..8 { assert POOL.free[i]; }
	101	+	for i in 0..8 { assert frames::available(&POOL, i); }
45	102		assert frames::reclaim(&mut POOL, 20) == 0;
46	103		}
47	104
48	105		/// Adjacent physical frames form runs; a reserved hole cannot be crossed.
49	106		@test unsafe fn fragmentation() throws (testing::TestError) {

187	244		try! frames::initialize(&mut POOL, &machine);
188	245		let mut count: u32 = 0;
189	246		for i in 0..96 {
190	247		let start = 0x80000000 + i as u64 * 4096;
191	248		if platform::available(&machine, range::Range { start, end: start + 4096 }) {
192		-	try testing::expect(count < POOL.count and POOL.addresses[count] == start and POOL.free[count]);
	249	+	assert count < POOL.count and POOL.addresses[count] == start and frames::available(&POOL, count);
193	250		set count += 1;
194	251		}
195	252		}
196	253		try testing::expect(count == POOL.count);
197	254		}

21	21		let base = pointer as u64;
22	22		let aligned = (base + 4095) & ~4095;
23	23		set POOL.count = (@sizeOf([u64; 131072]) - (aligned - base) as u32) / 4096;
24	24		for i in 0..POOL.count {
25	25		set POOL.addresses[i] = aligned + i as u64 * 4096;
26		-	set POOL.free[i] = true;
	26	+	set POOL.free[i / 64] \|= 1 << (i % 64) as u64;
27	27		}
28	28		registry::initialize(&mut PACKAGES);
29	29		}
30	30
31	31		/// Publish a package with one private word and optional pointer relocation.

66	66		assert first.frames.first + first.frames.count <= other.frames.first;
67	67		try! frames::release(&mut POOL, first.frames);
68	68		try! frames::release(&mut POOL, other.frames);
69	69		let cancelled = try! instances::reserve(&PACKAGES, &mut POOL, root);
70	70		instances::cancel(&mut POOL, cancelled);
71		-	for i in 0..POOL.count { assert POOL.free[i]; }
	71	+	for i in 0..POOL.count { assert frames::available(&POOL, i); }
72	72		}
73	73
74	74		/// A diamond has one dependency instance per domain and independent relocated pointers.
75	75		@test unsafe fn diamond() throws (testing::TestError) {
76	76		initialize();

90	90		set *word(first.table[base.index]) = 99;
91	91		try testing::expect(*word(second.table[base.index]) == 7);
92	92		try testing::expect(first.table[4] == 0 and second.table[4] == 0);
93	93		try! frames::release(&mut POOL, first.frames);
94	94		try! frames::release(&mut POOL, second.frames);
95		-	for i in 0..POOL.count { try testing::expect(POOL.free[i]); }
	95	+	for i in 0..POOL.count { assert frames::available(&POOL, i); }
96	96		}
97	97
98	98		/// State alignment can exceed a physical frame and zero-fill follows the template.
99	99		@test unsafe fn alignment() throws (testing::TestError) {
100	100		initialize();

125	125		};
126	126		try instances::create(&PACKAGES, &mut POOL, abi::Ref { index: root.index, generation: 2 }) catch err {
127	127		try testing::expect(err == abi::Error::BadHandle); set failures += 1;
128	128		};
129	129		try testing::expect(failures == 3);
130		-	for i in 0..POOL.count { try testing::expect(POOL.free[i]); }
	130	+	for i in 0..POOL.count { assert frames::available(&POOL, i); }
131	131		let retry = try! instances::create(&PACKAGES, &mut POOL, root);
132	132		try testing::expect(*word(retry.table[root.index]) == 7);
133	133		try! frames::release(&mut POOL, retry.frames);
134	134		}

80	80		});
81	81		let base = ((&RAM[0]) as u64 + 4095) & ~4095;
82	82		set MEMORY.backings.pool.count = 2;
83	83		for i in 0..2 {
84	84		set MEMORY.backings.pool.addresses[i] = base + i as u64 * 4096;
85		-	set MEMORY.backings.pool.free[i] = true;
	85	+	set MEMORY.backings.pool.free[i / 64] \|= 1 << (i % 64) as u64;
86	86		}
87	87		let reservation = try! pages::reserve(&mut MEMORY, &mut FIRST.table, authority, 2);
88	88		let held = lifecycle::holdPage(&mut CALLS, &mut STORE, owner, reservation);
89	89		assert STORE.contexts[0].reservation;
90	90		lifecycle::clearPage(&CALLS, &held);
91	91		lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
92		-	assert not MEMORY.backings.pool.free[0] and not MEMORY.backings.pool.free[1];
	92	+	assert not frames::available(&MEMORY.backings.pool, 0) and not frames::available(&MEMORY.backings.pool, 1);
93	93		set STORE.records[0].state = domains::Lifecycle::Dead;
94	94		set STORE.contexts[0].state = domains::ContextState::Stopped;
95	95		set STORE.contexts[0].hart = 0;
96	96		lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
97		-	assert not MEMORY.backings.pool.free[0];
	97	+	assert not frames::available(&MEMORY.backings.pool, 0);
98	98		// Model the end of the stopped continuation before hart release.
99	99		match held { case lifecycle::Lease::Held(context) => { assert context == owner; }, }
100	100		set STORE.contexts[0].hart = nil;
101	101		lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
102		-	assert MEMORY.backings.pool.retiredCount == 1 and not MEMORY.backings.pool.free[0];
	102	+	assert MEMORY.backings.pool.retiredCount == 1 and not frames::available(&MEMORY.backings.pool, 0);
103	103		assert frames::reclaim(&mut MEMORY.backings.pool, 256) == 2;
104		-	assert MEMORY.backings.pool.free[0] and MEMORY.backings.pool.free[1];
	104	+	assert frames::available(&MEMORY.backings.pool, 0) and frames::available(&MEMORY.backings.pool, 1);
105	105		assert MEMORY.slots[0].state == slots::State::Free;
106	106		assert MEMORY.backings.slots[0].state == slots::State::Free;
107	107		assert FIRST.table.slots[1].state == slots::State::Free and CALLS.active[0] == 0;
108	108		assert not STORE.contexts[0].reservation;
109	109		set STORE.records[0].state = domains::Lifecycle::Active;

150	150		assert CALLS.active[0] == 2 and MEMORY.backings.pool.retiredCount == 1;
151	151		assert not STORE.contexts[0].reservation and STORE.contexts[1].reservation;
152	152		assert lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
153	153		assert CALLS.active[0] == 0 and MEMORY.backings.pool.retiredCount == 2;
154	154		assert not lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
155		-	assert not MEMORY.backings.pool.free[0] and not MEMORY.backings.pool.free[1];
	155	+	assert not frames::available(&MEMORY.backings.pool, 0) and not frames::available(&MEMORY.backings.pool, 1);
156	156		assert frames::reclaim(&mut MEMORY.backings.pool, 1) == 1;
157	157		assert frames::reclaim(&mut MEMORY.backings.pool, 1) == 1;
158	158		assert MEMORY.backings.pool.retiredCount == 0;
159	159		}
160	160

166	166		let caller = abi::Ref { index: 0, generation: 1 };
167	167		let target = abi::Ref { index: 1, generation: 1 };
168	168		let base = ((&RAM[0]) as u64 + 4095) & ~4095;
169	169		set MEMORY.backings.pool.count = 1;
170	170		set MEMORY.backings.pool.addresses[0] = base;
171		-	set MEMORY.backings.pool.free[0] = true;
	171	+	set MEMORY.backings.pool.free[0] \|= 1;
172	172		let slot = try! slots::reserve(&mut STORE.contextSlots[..]);
173	173		let object = slots::reference(&slot);
174	174		let run = frames::commit(try! frames::reserve(&mut MEMORY.backings.pool, 1));
175	175		set STORE.contexts[object.index].owner = target;
176	176		set STORE.contexts[object.index].kernelFrames = run;

181	181		});
182	182		let lease = lifecycle::holdContext(&mut CALLS, &mut STORE, caller, pending);
183	183		lifecycle::clearContext(&CALLS, &lease);
184	184		set STORE.records[1].state = domains::Lifecycle::Dead;
185	185		lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
186		-	assert STORE.contexts[0].reservation and not MEMORY.backings.pool.free[0];
	186	+	assert STORE.contexts[0].reservation and not frames::available(&MEMORY.backings.pool, 0);
187	187		set STORE.records[0].state = domains::Lifecycle::Dead;
188	188		set STORE.contexts[0].state = domains::ContextState::Stopped;
189	189		set STORE.contexts[0].hart = 1;
190	190		lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
191	191		assert STORE.contextSlots[object.index].state == slots::State::Reserved;
192	192		match lease { case lifecycle::Lease::Held(id) => { assert id == caller; }, }
193	193		set STORE.contexts[0].hart = nil;
194	194		lifecycle::cancelAllocations(&mut CALLS, &mut STORE, &mut MEMORY, &mut loader::STATE, &mut registry::STORE);
195		-	assert MEMORY.backings.pool.retiredCount == 1 and not MEMORY.backings.pool.free[0];
	195	+	assert MEMORY.backings.pool.retiredCount == 1 and not frames::available(&MEMORY.backings.pool, 0);
196	196		assert frames::reclaim(&mut MEMORY.backings.pool, 256) == 1;
197		-	assert MEMORY.backings.pool.free[0];
	197	+	assert frames::available(&MEMORY.backings.pool, 0);
198	198		assert STORE.contextSlots[object.index].state == slots::State::Free;
199	199		assert not STORE.contexts[0].reservation and CALLS.active[0] == 0;
200	200		}
201	201
202	202		/// Dead contexts retain requests until hart release and completion of taken work.