Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-prism

Source of release 0.6.1

0.6.1 / src / pool.lucb

## LRU of unpinned published payloads and compositor pins. Evict/fault I/O lives in store.
## Entries are found through a hash index: every bake and every open touches each
## property once, so a linear search made them quadratic in the property count.
import memory
from path import is_descendant
from storage import Buffer, List, close_names, text_copy

## Payloads smaller than this stay resident and out of the LRU: an extent and an entry
## cost more than paging them out could free. They still count toward the limit.
pub let min_paged: usize = 4096

pub struct Entry:
    pub var identity: Buffer
    pub var path: Buffer
    pub var name: Buffer
    pub var size: usize
    pub var tick: u64

    pub func init():
        return

    pub func close():
        self.identity.close()
        self.path.close()
        self.name.close()

pub struct Pin:
    pub var identity: Buffer
    pub var path: Buffer
    pub var refs: u64

    pub func init():
        return

    pub func close():
        self.identity.close()
        self.path.close()

pub struct Pool:
    pub var entries: List[Entry]
    ## Open addressing over `entries`: 0 is empty, otherwise an entry index plus one.
    ## The capacity is a power of two, at least twice the entry count.
    var slots: usize[]
    pub var pins: List[Pin]
    pub var clock: u64
    pub var evictions: u64
    pub var faults: u64

    pub func init():
        return

pub func close_pool(pool: Pool*):
    for i in 0..<pool.entries.count:
        pool.entries.items[i].close()
    pool.entries.close()
    if pool.slots.length > 0: free(pool.slots) in memory.heap
    for i in 0..<pool.pins.count:
        pool.pins.items[i].close()
    pool.pins.close()

pub func pinned(pool: const Pool*, identity: str, path: str) -> bool:
    for held in pool.pins.span():
        if held.identity.view() == identity and (path == held.path.view() or is_descendant(path, held.path.view())):
            return true
    return false

pub func pin(pool: Pool*, identity: str, path: str) -> !:
    for i in 0..<pool.pins.count:
        if pool.pins.items[i].identity.view() == identity and pool.pins.items[i].path.view() == path:
            pool.pins.items[i].refs += 1
            return
    var item = Pin()
    item.refs = 1
    item.identity = try text_copy(identity)
    item.path = text_copy(path) catch failure:
        item.close()
        error(failure.code, failure.message)
    pool.pins.push(item) catch failure:
        item.close()
        error(failure.code, failure.message)

pub func unpin(pool: Pool*, identity: str, path: str):
    for i in 0..<pool.pins.count:
        if pool.pins.items[i].identity.view() == identity and pool.pins.items[i].path.view() == path:
            if pool.pins.items[i].refs > 1:
                pool.pins.items[i].refs -= 1
                return
            pool.pins.items[i].close()
            pool.pins.remove(i)
            return

func key_hash(identity: str, path: str, name: str) -> usize:
    var value: u64 = 14695981039346656037
    for part in [identity, path, name]:
        for byte in part.bytes:
            value = (value ^ (u64)byte) *% 1099511628211
        value = (value ^ 0xff) *% 1099511628211
    return (usize)value

func matches(item: const Entry*, identity: str, path: str, name: str) -> bool:
    return item.identity.view() == identity and item.path.view() == path and item.name.view() == name

## The slot holding the entry for this key, or the empty slot where it would go.
func slot_for(pool: const Pool*, identity: str, path: str, name: str) -> usize:
    let mask = pool.slots.length - 1
    var at = key_hash(identity, path, name) & mask
    while pool.slots[at] != 0 and not matches(&pool.entries.items[pool.slots[at] - 1], identity, path, name):
        at = (at + 1) & mask
    return at

func find(pool: const Pool*, identity: str, path: str, name: str) -> usize?:
    if pool.slots.length == 0: return none
    let index = pool.slots[slot_for(pool, identity, path, name)]
    if index == 0: return none
    return index - 1

## Rebuild the index for the current entries, at least twice their count.
func reindex(pool: Pool*, minimum: usize) -> !:
    var capacity: usize = 16
    while capacity < minimum * 2: capacity *= 2
    let slots = try new usize[capacity] --- in memory.heap
    for i in 0..<capacity: slots[i] = 0
    if pool.slots.length > 0: free(pool.slots) in memory.heap
    pool.slots = slots
    for i in 0..<pool.entries.count:
        let item = &pool.entries.items[i]
        pool.slots[slot_for(pool, item.identity.view(), item.path.view(), item.name.view())] = i + 1

pub func touch(pool: Pool*, identity: str, path: str, name: str, size: usize) -> !:
    pool.clock += 1
    if let index = find(pool, identity, path, name):
        pool.entries.items[index].tick = pool.clock
        pool.entries.items[index].size = size
        return
    if (pool.entries.count + 1) * 2 > pool.slots.length: try reindex(pool, pool.entries.count + 1)
    var item = Entry()
    item.size = size
    item.tick = pool.clock
    item.identity = try text_copy(identity)
    item.path = text_copy(path) catch failure:
        item.close()
        error(failure.code, failure.message)
    item.name = text_copy(name) catch failure:
        item.close()
        error(failure.code, failure.message)
    pool.entries.push(item) catch failure:
        item.close()
        error(failure.code, failure.message)
    pool.slots[slot_for(pool, identity, path, name)] = pool.entries.count

## Remove an entry: the last entry moves into its place, and the index is rebuilt
## around the hole so probing stays correct (backward-shift deletion).
pub func drop_entry(pool: Pool*, identity: str, path: str, name: str):
    let index = find(pool, identity, path, name) else return
    let mask = pool.slots.length - 1
    var hole = slot_for(pool, identity, path, name)
    pool.slots[hole] = 0
    var next = (hole + 1) & mask
    while pool.slots[next] != 0:
        let item = &pool.entries.items[pool.slots[next] - 1]
        let home = key_hash(item.identity.view(), item.path.view(), item.name.view()) & mask
        # Move it into the hole unless its home lies cyclically in (hole, next].
        let stays = (home > hole and home <= next) if hole <= next else (home > hole or home <= next)
        if not stays:
            pool.slots[hole] = pool.slots[next]
            pool.slots[next] = 0
            hole = next
        next = (next + 1) & mask
    pool.entries.items[index].close()
    let last = pool.entries.count - 1
    if index != last:
        pool.entries.items[index] = pool.entries.items[last]
        let moved = &pool.entries.items[index]
        pool.slots[slot_for(pool, moved.identity.view(), moved.path.view(), moved.name.view())] = index + 1
    pool.entries.count = last

pub func coldest(pool: const Pool*) -> usize?:
    var best: usize? = none
    var tick: u64 = 0
    var found = false
    for i in 0..<pool.entries.count:
        let item = &pool.entries.items[i]
        if pinned(pool, item.identity.view(), item.path.view()):
            continue
        if not found or item.tick < tick:
            found = true
            tick = item.tick
            best = i
    return best

pub func pinned_bytes(pool: const Pool*) -> usize:
    var total: usize = 0
    for item in pool.entries.span():
        if pinned(pool, item.identity.view(), item.path.view()):
            total += item.size
    return total