dymokomi/luce-prism
Source of release 0.6.1
## 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