export mod budgets;

use super::budgets;

        budgets::initialize(&mut budgets::STORE);

//! Exclusive half-open CPU intervals and their capability ownership.

use super::abi;

use super::limits;

use super::slots;

use super::capability;

use super::transactions;

use super::domains;

/// Rights on an initial CPU budget.

export constant DEFAULT_RIGHTS: u16 = abi::READ | abi::WRITE | abi::TRANSFER;

/// One retained interval on a physical hart.

export record Window: Copy {

    /// Physical hart on which this interval grants CPU authority.

    hart: u32,

    /// Inclusive first authorized tick.

    start: u64,

    /// Exclusive end of CPU authority.

    end: u64,

    /// Domain holding the sole capability for this interval.

    owner: abi::Ref,

    /// Sole live handle in the owner's table.

    handle: abi::Handle,

    /// Selected execution context, if the interval is bound.

    context: ?abi::Ref,

}

/// Bounded CPU authority derived from one initial interval per hart.

export record Store: Copy {

    /// Budget object generations.

    slots: [slots::Slot; limits::BUDGETS],

    /// Payload for each published interval.

    windows: [Window; limits::BUDGETS],

    /// Harts whose initial interval has already been issued.

    seeded: u64,

}

/// Global exclusive CPU intervals.

export unsafe static STORE: Store = undefined;

/// Initialize fresh budget metadata before boot issues CPU authority.

export fn initialize(store: &mut Store) {

    slots::initialize(&mut store.slots[..]);

    set store.seeded = 0;

}

/// Read a retained budget object after checking its generation.

export fn get(store: &Store, object: abi::Ref) -> Window throws (abi::Error) {

    if not slots::matches(&store.slots[..], object, slots::State::Live) {

        throw abi::Error::BadHandle;

    }

    return store.windows[object.index];

}

/// Validate the unique capability owner and return the budget object reference.

fn owned(store: &Store, table: &capability::Table, handle: abi::Handle, rights: u16) -> abi::Ref throws (abi::Error) {

    let entry = try capability::lookup(table, handle, abi::Kind::Budget, abi::Rights(rights));

    let window = try get(store, entry.object);

    if window.owner <> table.owner or window.handle <> handle {

        throw abi::Error::BadHandle;

    }

    return entry.object;

}

/// Publish a new interval after reserving both object and capability capacity.

fn install(store: &mut Store, table: &mut capability::Table, window: Window, rights: abi::Rights) -> abi::Handle throws (abi::Error) {

    let handleSlot = try slots::reserve(&mut table.slots[..]);

    let budgetSlot = try slots::reserve(&mut store.slots[..]) catch err {

        try! slots::cancel(&mut table.slots[..], handleSlot); throw err;

    };

    let object = slots::reference(&budgetSlot);

    let reference = slots::reference(&handleSlot);

    let handle = try! abi::handle(abi::Kind::Budget, reference);

    set store.windows[object.index] = window;

    set store.windows[object.index].owner = table.owner;

    set store.windows[object.index].handle = handle;

    let live = try! slots::commit(&mut store.slots[..], budgetSlot);

    return capability::publish(table, handleSlot, capability::Entry { kind: abi::Kind::Budget, object: live, rights });

}

/// Issue one initial interval per hart during trusted boot initialization.

/// Only partition, merge, transfer, and consumption can change authority after this call.

export fn seed(store: &mut Store, table: &mut capability::Table, hart: u32, start: u64, end: u64)

    -> abi::Handle throws (abi::Error)

{

    if hart >= limits::HARTS or start >= end {

        throw abi::Error::InvalidArg;

    }

    if (store.seeded & (1 << hart as u64)) <> 0 {

        throw abi::Error::Busy;

    }

    let handle = try install(store, table, Window {

        hart, start, end, owner: table.owner, handle: abi::Handle(0), context: nil,

    }, abi::Rights(DEFAULT_RIGHTS));

    set store.seeded |= 1 << hart as u64;

    return handle;

}

/// Read retained interval metadata through its unique capability.

export fn query(store: &Store, table: &capability::Table, handle: abi::Handle) -> Window throws (abi::Error) {

    let object = try owned(store, table, handle, abi::READ);

    return store.windows[object.index];

}

/// Discard the elapsed prefix and reject fully expired authority.

fn remaining(window: Window, now: u64) -> Window throws (abi::Error) {

    if now >= window.end {

        throw abi::Error::Busy;

    }

    let mut result = window;

    if now > result.start {

        set result.start = now;

    }

    return result;

}

/// Split unconsumed authority, retaining the left handle and returning the right.

export fn split(store: &mut Store, table: &mut capability::Table, handle: abi::Handle, at: u64, now: u64)

    -> abi::Handle throws (abi::Error)

{

    let object = try owned(store, table, handle, abi::WRITE);

    let window = try remaining(store.windows[object.index], now);

    if at <= window.start or at >= window.end {

        throw abi::Error::InvalidArg;

    }

    let entry = try! capability::get(table, handle);

    let mut right = window;

    set right.start = at;

    let result = try install(store, table, right, entry.rights);

    set store.windows[object.index].start = window.start;

    set store.windows[object.index].end = at;

    return result;

}

/// Combine adjacent intervals on the same hart with the same context binding.

/// The first handle survives with the intersection of both capability rights.

export fn merge(store: &mut Store, table: &mut capability::Table, first: abi::Handle, second: abi::Handle, now: u64)

    -> abi::Handle throws (abi::Error)

{

    if first == second {

        throw abi::Error::InvalidArg;

    }

    let a = try owned(store, table, first, abi::WRITE);

    let b = try owned(store, table, second, abi::WRITE);

    let left = try remaining(store.windows[a.index], now);

    let right = try remaining(store.windows[b.index], now);

    if left.hart <> right.hart or left.context <> right.context {

        throw abi::Error::InvalidArg;

    }

    let mut start = left.start;

    let mut end = right.end;

    if left.end <> right.start {

        if right.end <> left.start {

            throw abi::Error::InvalidArg;

        }

        set start = right.start; set end = left.end;

    }

    let firstEntry = try! capability::get(table, first);

    let secondEntry = try! capability::get(table, second);

    let firstSlot = try! abi::decode(first);

    set table.entries[firstSlot.object.index].rights = abi::Rights(*firstEntry.rights & *secondEntry.rights);

    set store.windows[a.index].start = start;

    set store.windows[a.index].end = end;

    let removed = try! capability::invalidate(table, second);

    try! slots::release(&mut store.slots[..], b);

    return first;

}

/// Retire an expired interval and its sole handle.

export fn expire(store: &mut Store, table: &mut capability::Table, handle: abi::Handle, now: u64) -> bool throws (abi::Error) {

    let object = try owned(store, table, handle, 0);

    if now < store.windows[object.index].end {

        return false;

    }

    let removed = try! capability::invalidate(table, handle);

    try! slots::release(&mut store.slots[..], object);

    return true;

}

/// Transfer unconsumed authority, clear its context binding, and attenuate rights.

/// The caller keeps both domains alive and serializes both capability tables.

export fn transfer(store: &mut Store, source: &mut capability::Table, target: &mut capability::Table,

    handle: abi::Handle, rights: u64, now: u64) -> abi::Handle throws (abi::Error)

{

    let object = try owned(store, source, handle, abi::TRANSFER);

    let mut window = try remaining(store.windows[object.index], now);

    let entry = try! capability::get(source, handle);

    let owner = source.owner;

    let pending = try transactions::reserve(target, owner, handle, entry, rights, true);

    let result = transactions::transfer(source, target, pending);

    set window.owner = target.owner;

    set window.handle = result;

    set window.context = nil;

    set store.windows[object.index] = window;

    return result;

}

/// Capability and context selected by a budget-binding request.

export record Binding: Copy {

    /// Exclusive CPU authority to bind or transfer.

    budget: abi::Handle,

    /// Domain capability carrying Wake authority for the receiver.

    domain: abi::Handle,

    /// Live execution context owned by the receiver.

    context: abi::Ref,

}

/// Reject overlapping execution authority for one context across all harts.

fn available(store: &Store, object: abi::Ref, candidate: Window, context: abi::Ref) -> bool {

    for i in 0..limits::BUDGETS {

        if i == object.index or store.slots[i].state <> slots::State::Live {

            continue;

        }

        let other = store.windows[i];

        if other.context == context and candidate.start < other.end and other.start < candidate.end {

            return false;

        }

    }

    return true;

}

/// Select a context and transfer the unique capability when its domain differs.

/// The caller serializes the budget, domain lifetimes, and both capability tables.

export unsafe fn bind(store: &mut Store, domainStore: &domains::Store, table: &mut capability::Table,

    request: Binding, now: u64) -> abi::Handle throws (abi::Error)

{

    let object = try owned(store, table, request.budget, abi::TRANSFER);

    let candidate = try remaining(store.windows[object.index], now);

    let permission = try capability::lookup(table, request.domain, abi::Kind::Domain, abi::Rights(abi::WAKE));

    let mut target = try domains::get(domainStore, permission.object);

    if target.state == domains::Lifecycle::Dead {

        throw abi::Error::BadHandle;

    }

    if not slots::matches(&domainStore.contextSlots[..], request.context, slots::State::Live)

        or domainStore.contexts[request.context.index].owner <> permission.object {

            throw abi::Error::BadHandle;

        }

    if not available(store, object, candidate, request.context) {

        throw abi::Error::Busy;

    }

    let mut result = request.budget;

    if permission.object <> table.owner {

        let entry = try! capability::get(table, request.budget);

        set result = try transfer(store, table, &mut target.memory.table, request.budget, *entry.rights as u64, now);

    }

    set store.windows[object.index].start = candidate.start;

    set store.windows[object.index].context = request.context;

    return result;

}

/// Test half-open execution authority on the selected hart at the current tick.

export fn active(store: &Store, object: abi::Ref, hart: u32, now: u64) -> bool throws (abi::Error) {

    let window = try get(store, object);

    return window.context <> nil and window.hart == hart and window.start <= now and now < window.end;

}

export mod budgets;

//! Conservation and expiration of exclusive CPU windows.

use std::testing;

use kernel::abi;

use kernel::capability;

use kernel::budgets;

use kernel::slots;

use kernel::domains;

use kernel::frames;

use kernel::instances;

use kernel::trap;

/// Exclusive CPU-window metadata.

unsafe static STORE: budgets::Store = undefined;

/// Capability owner for the test windows.

unsafe static TABLE: capability::Table = undefined;

/// Receiving domain's capability table.

unsafe static TARGET: capability::Table = undefined;

/// Domain and context lifetimes used for binding admission.

unsafe static DOMAINS: domains::Store = undefined;

/// Capability storage for a pending receiver domain.

unsafe static MEMORY: domains::Memory = undefined;

/// Start with one live owner and no issued hart intervals.

unsafe fn initialize() {

    budgets::initialize(&mut STORE);

    capability::initialize(&mut TABLE, abi::Ref { index: 0, generation: 1 });

    capability::initialize(&mut TARGET, abi::Ref { index: 1, generation: 1 });

}

/// Split and merge conserve the unconsumed half-open interval.

@test unsafe fn conservation() throws (testing::TestError) {

    initialize();

    let left = try! budgets::seed(&mut STORE, &mut TABLE, 0, 10, 100);

    let right = try! budgets::split(&mut STORE, &mut TABLE, left, 60, 20);

    let a = try! budgets::query(&STORE, &TABLE, left);

    let b = try! budgets::query(&STORE, &TABLE, right);

    try testing::expect(a.start == 20 and a.end == 60 and b.start == 60 and b.end == 100);

    let joined = try! budgets::merge(&mut STORE, &mut TABLE, right, left, 30);

    let result = try! budgets::query(&STORE, &TABLE, joined);

    try testing::expect(joined == right and result.start == 30 and result.end == 100);

    let mut stale = false;

    try budgets::query(&STORE, &TABLE, left) catch err {

        try testing::expect(err == abi::Error::BadHandle); set stale = true;

    };

    try testing::expect(stale);

}

/// Expiration cannot recreate consumed time or issue a second initial interval.

@test unsafe fn expiration() throws (testing::TestError) {

    initialize();

    let handle = try! budgets::seed(&mut STORE, &mut TABLE, 0, 10, 100);

    let mut failures: u32 = 0;

    try budgets::split(&mut STORE, &mut TABLE, handle, 50, 50) catch err {

        try testing::expect(err == abi::Error::InvalidArg); set failures += 1;

    };

    try budgets::split(&mut STORE, &mut TABLE, handle, 90, 100) catch err {

        try testing::expect(err == abi::Error::Busy); set failures += 1;

    };

    try testing::expect(not try! budgets::expire(&mut STORE, &mut TABLE, handle, 99));

    try testing::expect(try! budgets::expire(&mut STORE, &mut TABLE, handle, 100));

    try budgets::query(&STORE, &TABLE, handle) catch err {

        try testing::expect(err == abi::Error::BadHandle); set failures += 1;

    };

    try budgets::seed(&mut STORE, &mut TABLE, 0, 100, 200) catch err {

        try testing::expect(err == abi::Error::Busy); set failures += 1;

    };

    try testing::expect(failures == 4);

}

/// A full receiver preserves source authority; successful transfer leaves one owner.

@test unsafe fn transfer() throws (testing::TestError) {

    initialize();

    let handle = try! budgets::seed(&mut STORE, &mut TABLE, 0, 10, 100);

    for i in 0..TARGET.slots.len {

        set TARGET.slots[i].state = slots::State::Retired;

    }

    let mut failed = false;

    try budgets::transfer(&mut STORE, &mut TABLE, &mut TARGET, handle, abi::READ as u64, 20) catch err {

        try testing::expect(err == abi::Error::InvalidArg); set failed = true;

    };

    let unchanged = try! budgets::query(&STORE, &TABLE, handle);

    try testing::expect(failed and unchanged.start == 10 and unchanged.end == 100);

    set TARGET.slots[0].state = slots::State::Free;

    let received = try! budgets::transfer(&mut STORE, &mut TABLE, &mut TARGET, handle, abi::READ as u64, 20);

    let window = try! budgets::query(&STORE, &TARGET, received);

    try testing::expect(window.owner == TARGET.owner and window.start == 20 and window.end == 100);

    let entry = try! capability::get(&TARGET, received);

    try testing::expect(*entry.rights == abi::READ and window.context == nil);

    let mut stale = false;

    try budgets::query(&STORE, &TABLE, handle) catch err {

        try testing::expect(err == abi::Error::BadHandle); set stale = true;

    };

    try testing::expect(stale);

}

/// Split exhaustion leaves the original interval intact and merge requires adjacency.

@test unsafe fn rejection() throws (testing::TestError) {

    initialize();

    let first = try! budgets::seed(&mut STORE, &mut TABLE, 0, 10, 100);

    for i in 1..STORE.slots.len {

        set STORE.slots[i].state = slots::State::Retired;

    }

    let mut failures: u32 = 0;

    try budgets::split(&mut STORE, &mut TABLE, first, 50, 20) catch err {

        try testing::expect(err == abi::Error::Exhausted); set failures += 1;

    };

    let unchanged = try! budgets::query(&STORE, &TABLE, first);

    try testing::expect(unchanged.start == 10 and unchanged.end == 100 and TABLE.slots[1].state == slots::State::Free);

    for i in 1..STORE.slots.len {

        set STORE.slots[i].state = slots::State::Free;

    }

    let middle = try! budgets::split(&mut STORE, &mut TABLE, first, 40, 20);

    let last = try! budgets::split(&mut STORE, &mut TABLE, middle, 70, 20);

    try budgets::merge(&mut STORE, &mut TABLE, first, last, 20) catch err {

        try testing::expect(err == abi::Error::InvalidArg); set failures += 1;

    };

    let otherHart = try! budgets::seed(&mut STORE, &mut TABLE, 1, 40, 70);

    try budgets::merge(&mut STORE, &mut TABLE, first, otherHart, 20) catch err {

        try testing::expect(err == abi::Error::InvalidArg); set failures += 1;

    };

    try testing::expect(failures == 3);

}

/// Install a pending receiver and one live context for budget admission tests.

unsafe fn receiver() -> abi::Handle {

    domains::initialize(&mut DOMAINS);

    let rootSlot = try! slots::reserve(&mut DOMAINS.slots[..]);

    let root = try! slots::commit(&mut DOMAINS.slots[..], rootSlot);

    let childSlot = try! slots::reserve(&mut DOMAINS.slots[..]);

    let child = slots::reference(&childSlot);

    capability::initialize(&mut MEMORY.table, child);

    let contextSlot = try! slots::reserve(&mut DOMAINS.contextSlots[..]);

    let context = slots::reference(&contextSlot);

    set DOMAINS.contexts[context.index] = domains::Context {

        owner: child, frame: trap::Frame { registers: [0; 32], pc: 4, status: 0x80, cause: 0, value: 0 },

    };

    set DOMAINS.records[child.index] = domains::Domain {

        state: domains::Lifecycle::Pending, creator: root, parent: root,

        image: abi::Ref { index: 0, generation: 1 }, initial: context,

        allocation: frames::Run { first: 0, count: 0 }, memory: &mut MEMORY,

        graph: instances::Instance { frames: frames::Run { first: 0, count: 0 }, table: &[] },

        events: abi::Handle(0),

    };

    let liveContext = try! slots::commit(&mut DOMAINS.contextSlots[..], contextSlot);

    let liveDomain = try! slots::commit(&mut DOMAINS.slots[..], childSlot);

    return try! capability::install(&mut TABLE, capability::Entry {

        kind: abi::Kind::Domain, object: child, rights: abi::Rights(abi::WAKE),

    });

}

/// One context cannot hold overlapping windows on separate harts.

@test unsafe fn binding() throws (testing::TestError) {

    initialize();

    let domain = receiver();

    let context = abi::Ref { index: 0, generation: 1 };

    let first = try! budgets::seed(&mut STORE, &mut TABLE, 0, 10, 100);

    let other = try! budgets::seed(&mut STORE, &mut TABLE, 1, 10, 200);

    let future = try! budgets::split(&mut STORE, &mut TABLE, other, 100, 10);

    let received = try! budgets::bind(&mut STORE, &DOMAINS, &mut TABLE,

        budgets::Binding { budget: first, domain, context }, 10);

    let entry = try! capability::get(&MEMORY.table, received);

    try testing::expect(not try! budgets::active(&STORE, entry.object, 0, 9));

    try testing::expect(try! budgets::active(&STORE, entry.object, 0, 10));

    try testing::expect(not try! budgets::active(&STORE, entry.object, 1, 10));

    try testing::expect(not try! budgets::active(&STORE, entry.object, 0, 100));

    let mut overlap = false;

    try budgets::bind(&mut STORE, &DOMAINS, &mut TABLE,

        budgets::Binding { budget: other, domain, context }, 10) catch err {

        try testing::expect(err == abi::Error::Busy); set overlap = true;

    };

    let unchanged = try! budgets::query(&STORE, &TABLE, other);

    try testing::expect(overlap and unchanged.context == nil and unchanged.start == 10);

    let next = try! budgets::bind(&mut STORE, &DOMAINS, &mut TABLE,

        budgets::Binding { budget: future, domain, context }, 10);

    let following = try! capability::get(&MEMORY.table, next);

    try testing::expect(try! budgets::active(&STORE, following.object, 1, 100));

    let self = try! capability::install(&mut MEMORY.table, capability::Entry {

        kind: abi::Kind::Domain, object: MEMORY.table.owner, rights: abi::Rights(abi::WAKE),

    });

    let same = try! budgets::bind(&mut STORE, &DOMAINS, &mut MEMORY.table,

        budgets::Binding { budget: received, domain: self, context }, 20);

    let rebound = try! budgets::query(&STORE, &MEMORY.table, same);

    try testing::expect(same == received and rebound.start == 20 and rebound.end == 100);

}

/// Binding validates context generations, receiver capacity, and expiration atomically.

@test unsafe fn bindingRejection() throws (testing::TestError) {

    initialize();

    let domain = receiver();

    let handle = try! budgets::seed(&mut STORE, &mut TABLE, 0, 10, 100);

    let mut request = budgets::Binding { budget: handle, domain, context: abi::Ref { index: 0, generation: 2 } };

    let mut failures: u32 = 0;

    try budgets::bind(&mut STORE, &DOMAINS, &mut TABLE, request, 20) catch err {

        try testing::expect(err == abi::Error::BadHandle); set failures += 1;

    };

    set request.context.generation = 1;

    for i in 0..MEMORY.table.slots.len {

        set MEMORY.table.slots[i].state = slots::State::Retired;

    }

    try budgets::bind(&mut STORE, &DOMAINS, &mut TABLE, request, 20) catch err {

        try testing::expect(err == abi::Error::InvalidArg); set failures += 1;

    };

    let untouched = try! budgets::query(&STORE, &TABLE, handle);

    try testing::expect(untouched.start == 10 and untouched.context == nil);

    try budgets::bind(&mut STORE, &DOMAINS, &mut TABLE, request, 100) catch err {

        try testing::expect(err == abi::Error::Busy); set failures += 1;

    };

    set MEMORY.table.slots[0].state = slots::State::Free;

    let domainSlot = try! abi::decode(domain);

    set TABLE.entries[domainSlot.object.index].rights = abi::Rights(0);

    try budgets::bind(&mut STORE, &DOMAINS, &mut TABLE, request, 20) catch err {

        try testing::expect(err == abi::Error::Denied); set failures += 1;

    };

    try testing::expect(failures == 4);

}