Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-canvas

Source of release 0.5.1

0.5.1 / src / tiles / governor.lucb

#==============================================================================================
#
#   tiles/governor - Keeping tiles within the GPU's and the machine's memory
#
#   DESCRIPTION:
#       One governor per process. It knows every tile's tier (tiles/residency) and the bytes
#       each tier holds, and keeps them within two budgets: the GPU's, a share (Settings,
#       60% by default) of what the device reports it can hold, and RAM's, the same share of
#       the machine's memory. Derived tiles (pyramid levels, composites) live in TileCaches,
#       which count their bytes here and shrink to `cache_scale` of their budgets when the
#       GPU is short.
#
#       Pins: every tile handed out (`resident`) carries the epoch it was handed out in, and
#       nothing handed out in the current epoch is evicted. An epoch is a frame: a window's
#       frame may draw the document several times (the view, the Navigator, a popup's
#       backdrop), and every draw into it must find what the others recorded still there,
#       since the frame is only submitted when it presents. So the epoch advances, and the
#       governor settles, only at the first draw into a new frame, and never while another
#       frame records around it (`residency_frame`). Evicting then touches only what frames
#       already presented used, which the backends keep alive until the GPU is done.
#
#       Eviction takes the least wanted first:
#         1. tiles no document shows: history's, and jobs' copies (known exactly after the
#            editor marks what its documents hold);
#         2. tiles a document shows that no recent frame drew;
#         3. tiles recent frames drew, least recently first.
#       Evicting moves a tile to RAM (tiles/residency), never drops it: undo, and the view
#       coming back, bring it to the GPU again. Only when the GPU is out of memory and no
#       tile can move does allocating fail.
#
#       RAM has its budget too: past it, warm copies of tiles still on the GPU go first, then
#       the least wanted tiles kept only in RAM (history's first) move to the scratch file
#       (tiles/scratch), from which they come back when wanted. On unified memory (Apple
#       silicon, an integrated GPU) the GPU's tiles are RAM as well, and count against it.
#       The RAM budget is the process's: where the system reports what the process holds
#       (macOS its footprint, Windows its private bytes, Linux its resident pages) that
#       counts when it is more than the tiles alone, since a driver's own copies of GPU memory
#       and everything else the application holds take the same RAM.
#       Not yet: compressed RAM (the design's C tier).
#
#==============================================================================================

## The current epoch: tiles used in it are pinned on the GPU.
var residency_epoch: u64 = 1
## The current marking: tiles marked with it are shown by a document.
var live_generation: u64 = 0
## Bytes held: level-0 tiles on the GPU, their RAM copies, and derived tiles.
var gpu_tile_bytes: usize = 0
var ram_tile_bytes: usize = 0
var derived_tile_bytes: usize = 0
## The budgets, 0 for none (the default until `configure`).
var gpu_budget: usize = 0
var ram_budget: usize = 0
var unified_memory: bool = false
## How much of their budgets derived caches may use now.
var cache_scale_now: f64 = 1.0
## Moves made, for tests and reports.
var residency_promotions: u64 = 0
var residency_demotions: u64 = 0
var residency_transient_uploads: u64 = 0
## Tile allocations a test wants to fail as if the device were out of memory.
var residency_failures: usize = 0

## Epochs a tile counts as recently drawn for.
let recent_epochs: u64 = 2

## The frame the current epoch belongs to.
var epoch_frame: u64 = 0

## What the tiers hold and may hold, in bytes.
pub struct ResidencyReport:
    pub var gpu_tiles: usize
    pub var ram_tiles: usize
    pub var derived: usize
    pub var gpu_budget: usize
    pub var ram_budget: usize
    pub var promotions: u64
    pub var demotions: u64
    pub var transient_uploads: u64
    ## Bytes written into the scratch file (a compressed tile's at its own
    ## length), and moves out to it and back.
    pub var disk_tiles: usize
    pub var spills: u64
    pub var loads: u64
    ## Tiles read back from a document file (tiles/backing).
    pub var fetches: u64
    ## Compressed tiles held in RAM, and tiles compressed (tiles/compressed).
    pub var packed_tiles: usize
    pub var packs: u64
    ## What the system says the process holds; 0 where it cannot tell.
    pub var process: usize

# mark: The governor's controls (one set per process; tiles live on the main thread) ==========

## Budget both tiers as `usage` (0.1..0.95) of what `device` reports it can
## hold and of the machine's memory. On unified memory (Apple silicon) the
## GPU's memory is RAM, so RAM copies of GPU tiles are not kept warm.
pub func residency_configure(device: gpu.Device, usage: f64) -> !:
    if not (usage >= 0.1 and usage <= 0.95):
        error(invalid, "memory usage must be 0.1..0.95 of what the machine has")
    let reported = try device.memory()
    unified_memory = reported.unified
    gpu_budget = (usize)((f64)reported.budget * usage)
    ram_budget = (usize)((f64)physical_memory() * usage)

## Set the budgets directly, in bytes, 0 for none: tests, and forcing a
## small budget to see the governor work. Derived caches start again at their
## full share of the new budgets.
pub func residency_budgets(gpu_bytes: usize, ram_bytes: usize):
    gpu_budget = gpu_bytes
    ram_budget = ram_bytes
    cache_scale_now = 1.0

## Begin a new epoch: what earlier ones pinned may move again. For work
## outside frames (headless steps, tests); a view calls `residency_frame`.
pub func residency_advance():
    residency_epoch += 1

## A draw into frame `serial`: the first draw into a new frame begins a new
## epoch, unless another frame is recording around this one (a texture's frame
## inside a window's), whose draws must keep what they pinned. True when an
## epoch began: the moment to settle.
pub func residency_frame(serial: u64) -> bool:
    if serial == epoch_frame or gpu.open_frames() > 1:
        return false
    epoch_frame = serial
    residency_epoch += 1
    return true

## Whether the GPU tiers hold more than their budget: then the editor marks
## what its documents show and settles.
pub func residency_over_budget() -> bool:
    return (gpu_budget > 0 and gpu_tile_bytes + derived_tile_bytes > gpu_budget) or (ram_budget > 0 and ram_pressure() > ram_budget)

## What counts against the RAM budget: the tiles' RAM (`ram_held`), or what the
## system says the whole process holds when that is more.
func ram_pressure() -> usize:
    let held = ram_held()
    let process = process_memory()
    return process if process > held else held

## What counts against the RAM budget: RAM copies, and on unified memory the
## GPU's tiles too.
func ram_held() -> usize:
    if unified_memory:
        return ram_tile_bytes + packed_tile_bytes + gpu_tile_bytes + derived_tile_bytes
    return ram_tile_bytes + packed_tile_bytes

## Begin marking what documents show: tiles not marked before `settle` are
## the first to leave the GPU.
pub func residency_begin_marking():
    live_generation += 1

## Mark every tile `tiles` holds (on the canvas and past it) as shown.
pub func residency_mark_live(tiles: const Tiles*):
    for cell in tiles.cells:
        if let tile = cell:
            tile.live = live_generation
    if let outside = tiles.outside:
        residency_mark_live(outside)

## Keep the tiers within their budgets: shrink derived caches and move the
## least wanted GPU tiles to RAM until the GPU holds 85% of its budget, and
## drop RAM copies of tiles still on the GPU while RAM holds too much.
pub func residency_settle(device: gpu.Device) -> !:
    if gpu_budget > 0:
        let held = gpu_tile_bytes + derived_tile_bytes
        if held > gpu_budget:
            let target = gpu_budget // 100 * 85
            let wanted = held - target
            # Derived caches shrink only when layer tiles moving to RAM is not enough.
            if (try evict(device, wanted)) < wanted:
                cache_scale_now = max_f64(0.25, cache_scale_now * 0.5)
        elif held < gpu_budget // 10 * 6 and derived_tile_bytes < gpu_budget // 4:
            cache_scale_now = min_f64(1.0, cache_scale_now * 1.25)
        # Derived caches keep at most half the budget, so the layer tiles a frame or a job
        # draws with have the rest. Tiles a document file backs leave for nothing, so moving
        # layer tiles out alone would always suffice and hand the caches all of it.
        if derived_tile_bytes > gpu_budget // 2:
            cache_scale_now = max_f64(0.1, cache_scale_now * 0.5)
    if ram_budget > 0:
        let pressure = ram_pressure()
        if pressure > ram_budget:
            # Past the budget by the tiles' own count, settle to 85% of it; by what
            # the process holds beyond the tiles, only back to the budget: memory
            # freed may stay with the allocator a while, and asking the process
            # figure for more each time would move every tile out.
            let held = ram_held()
            let target = ram_budget // 100 * 85 if held > ram_budget else ram_budget // 100 * 95
            var wanted = pressure - target
            let dropped = drop_warm_copies(wanted)
            wanted = wanted - dropped if dropped < wanted else 0
            if wanted > 0:
                _ = try spill_ram(wanted)

## The share of their budgets derived caches may keep now.
pub func residency_cache_scale() -> f64:
    return cache_scale_now

## A derived cache now holds `bytes` more (`added`) or fewer.
pub func residency_derived(bytes: usize, added: bool):
    if added:
        derived_tile_bytes += bytes
    else:
        derived_tile_bytes -= bytes if bytes <= derived_tile_bytes else derived_tile_bytes

## The next `count` tile allocations fail as if the device were out of memory.
pub func residency_fail_allocations(count: usize):
    residency_failures = count

pub func residency_report() -> ResidencyReport:
    return ResidencyReport(gpu_tiles = gpu_tile_bytes, ram_tiles = ram_tile_bytes, derived = derived_tile_bytes, gpu_budget = gpu_budget, ram_budget = ram_budget,
                           promotions = residency_promotions, demotions = residency_demotions, transient_uploads = residency_transient_uploads,
                           disk_tiles = disk_tile_bytes, spills = residency_spills, loads = residency_loads, fetches = residency_fetches,
                           packed_tiles = packed_tile_bytes, packs = residency_packs, process = process_memory())

## The device is out of memory: shrink derived caches and move unpinned tiles
## to RAM, `wanted` bytes' worth, least wanted first. Bytes freed.
func relieve(device: gpu.Device, wanted: usize) -> usize!:
    let freed = try evict(device, wanted)
    if freed < wanted:
        cache_scale_now = max_f64(0.25, cache_scale_now * 0.5)
    return freed

## Whether a tile read back anyway may keep a RAM copy: not on unified memory,
## and while warm copies take under half the RAM budget.
func warm_room() -> bool:
    if unified_memory or ram_budget == 0:
        return false
    return ram_tile_bytes + tile_bytes <= ram_budget // 2

# mark: Choosing what leaves ==================================================================

## A GPU tile that may leave, and its order: class in the top byte, then
## the epoch it was last used in (older first).
struct Candidate:
    var tile: Tile*
    var key: u64

## Move at least `wanted` bytes of unpinned GPU tiles to RAM, least wanted
## first. Bytes freed.
func evict(device: gpu.Device, wanted: usize) -> usize!:
    if wanted == 0:
        return 0
    var count: usize = 0
    var cursor = first_tile
    while let tile = cursor:
        if tile.on_gpu and tile.used != residency_epoch:
            count += 1
        cursor = tile.next
    if count == 0:
        return 0
    let candidates = try new Candidate[count] --- in memory.heap
    defer free(candidates) in memory.heap
    var at: usize = 0
    cursor = first_tile
    while let tile = cursor:
        if tile.on_gpu and tile.used != residency_epoch and at < count:
            candidates[at] = Candidate(tile = tile, key = eviction_key(tile))
            at += 1
        cursor = tile.next
    sort_candidates(candidates[..<at])
    let taking = min_usize(at, (wanted + tile_bytes - 1) // tile_bytes)
    let chosen = try new Tile*[taking] --- in memory.heap
    defer free(chosen) in memory.heap
    for index in 0..<taking:
        chosen[index] = candidates[index].tile
    return try demote(device, chosen)

func eviction_key(tile: const Tile*) -> u64:
    var class: u64 = 2
    if tile.live != live_generation:
        class = 1
    elif tile.used + recent_epochs >= residency_epoch:
        class = 3
    let used = tile.used if tile.used < (1u64 << 56) else (1u64 << 56) - 1
    return (class << 56) | used

## Heap sort by key, smallest first: no recursion, no allocation.
func sort_candidates(items: Candidate[]):
    let count = items.length
    if count < 2:
        return
    var start = count // 2
    while start > 0:
        start -= 1
        sift_down(items, start, count)
    var end = count
    while end > 1:
        end -= 1
        let top = items[0]
        items[0] = items[end]
        items[end] = top
        sift_down(items, 0, end)

func sift_down(items: Candidate[], first: usize, count: usize):
    var root = first
    while root * 2 + 1 < count:
        var child = root * 2 + 1
        if child + 1 < count and items[child + 1].key > items[child].key:
            child += 1
        if items[root].key >= items[child].key:
            return
        let swapped = items[root]
        items[root] = items[child]
        items[child] = swapped
        root = child

## Free RAM held by tiles only there, the least wanted first (history's before a
## document's, then the least recently used), until `wanted` bytes are free or
## none is left: first by compressing them in RAM (tiles/compressed), then by
## moving them to the scratch file, compressed when they are. Bytes freed.
func spill_ram(wanted: usize) -> usize!:
    var count: usize = 0
    var cursor = first_tile
    while let tile = cursor:
        if spillable(tile):
            count += 1
        cursor = tile.next
    if count == 0:
        return 0
    let candidates = try new Candidate[count] --- in memory.heap
    defer free(candidates) in memory.heap
    var at: usize = 0
    cursor = first_tile
    while let tile = cursor:
        if spillable(tile) and at < count:
            candidates[at] = Candidate(tile = tile, key = eviction_key(tile))
            at += 1
        cursor = tile.next
    sort_candidates(candidates[..<at])
    var freed = try pack_candidates(candidates[..<at], wanted)
    for index in 0..<at:
        if freed >= wanted:
            break
        let tile = candidates[index].tile
        if tile.ram.length > 0 and (tile.packed.length > 0 or tile.disk >= 0 or backed(tile)):
            # Another copy holds it: the whole one in RAM just goes.
            drop_ram_copy(tile)
            freed += tile_bytes
        elif tile.packed.length > 0:
            let length = tile.packed.length
            try spill_packed(tile)
            freed += length
        elif tile.ram.length > 0:
            try spill(tile)
            freed += tile_bytes
    return freed

## Whether `tile` holds RAM the governor may free: off the GPU, not pinned.
func spillable(tile: const Tile*) -> bool:
    return not tile.on_gpu and (tile.ram.length > 0 or tile.packed.length > 0) and tile.used != residency_epoch

## The compressed tier's part of `spill_ram`: whole RAM copies with another
## copy just go; the others are compressed a batch at a time, the least
## wanted first, until `wanted` bytes are free. Bytes freed.
func pack_candidates(candidates: Candidate[], wanted: usize) -> usize!:
    if not has_codec():
        return 0
    var freed: usize = 0
    var batch: Tile*[64] = ---
    var count: usize = 0
    for index in 0..<candidates.length:
        if freed >= wanted:
            break
        let tile = candidates[index].tile
        if tile.ram.length == 0:
            continue
        if tile.packed.length > 0 or tile.disk >= 0 or backed(tile):
            drop_ram_copy(tile)
            freed += tile_bytes
            continue
        if tile.raw_only:
            continue
        batch[count] = tile
        count += 1
        if count == 64:
            freed += try pack_many(batch[..<count])
            count = 0
    if count > 0 and freed < wanted:
        freed += try pack_many(batch[..<count])
    return freed

## Free RAM copies of tiles that are also on the GPU, the least recently used
## first, until `wanted` bytes are gone or none is left.
func drop_warm_copies(wanted: usize) -> usize:
    var freed: usize = 0
    var cursor = first_tile
    while let tile = cursor:
        if freed >= wanted:
            return freed
        cursor = tile.next
        if tile.on_gpu and tile.ram.length > 0:
            drop_ram_copy(tile)
            freed += tile_bytes
    return freed

# mark: The machine's memory ==================================================================

extern func sysctlbyname(name: c.str, value: void*, length: usize*, new_value: void*?, new_length: usize) -> i32
extern func sysconf(name: i32) -> i64
extern func GlobalMemoryStatusEx(status: void*) -> i32
extern func proc_pid_rusage(pid: i32, flavor: i32, buffer: void*) -> i32
extern func getpid() -> i32
extern func GetCurrentProcess() -> void*
extern func K32GetProcessMemoryInfo(process: void*, counters: void*, size: u32) -> i32

## What the system says this process holds in bytes; 0 when it cannot tell.
## macOS: the physical footprint (what Activity Monitor shows); Windows: private
## bytes; Linux: resident pages.
pub func process_memory() -> usize:
    if platform.macos:
        # rusage_info_v2: a 16-byte UUID, then u64s; ri_phys_footprint is the 8th.
        var info: u64[32]
        memory.set(u8[]((u8*)&info[0], 256), 0)
        if proc_pid_rusage(getpid(), 2, (void*)&info[0]) != 0:
            return 0
        return (usize)info[9]
    elif platform.windows:
        # PROCESS_MEMORY_COUNTERS_EX: cb, PageFaultCount, then SIZE_Ts; PrivateUsage at byte 72.
        var counters: u64[10]
        memory.set(u8[]((u8*)&counters[0], 80), 0)
        counters[0] = 80
        if K32GetProcessMemoryInfo(GetCurrentProcess(), (void*)&counters[0], 80) == 0:
            return 0
        return (usize)counters[9]
    else:
        return linux_resident()

## Linux: the resident pages /proc/self/statm gives second, as bytes.
func linux_resident() -> usize:
    var opened = files.File.open((c.str)"/proc/self/statm", files.OpenMode.read) catch failure:
        _ = failure
        return 0
    defer opened.destroy()
    var text: u8[128]
    let count = opened.read(text) catch failure:
        _ = failure
        return 0
    var field: usize = 0
    var value: usize = 0
    for index in 0..<count:
        let character = text[index]
        if character == ' ':
            if field == 1:
                break
            field += 1
            value = 0
        elif character >= '0' and character <= '9' and field == 1:
            value = value * 10 + (usize)(character - '0')
    let size = sysconf(30)
    return value * (usize)size if size > 0 else 0

## The machine's physical memory in bytes; 0 when it cannot be told.
func physical_memory() -> u64:
    if platform.macos:
        var value: u64 = 0
        var length: usize = 8
        if sysctlbyname((c.str)"hw.memsize", (void*)&value, &length, none, 0) != 0:
            return 0
        return value
    elif platform.windows:
        # MEMORYSTATUSEX: dwLength first, ullTotalPhys at byte 8.
        var status: u8[64]
        memory.set(status, 0)
        status[0] = 64
        if GlobalMemoryStatusEx((void*)&status[0]) == 0:
            return 0
        var total: u64 = 0
        for index in 0..<(usize)8:
            total |= (u64)status[8 + index] << (u64)(index * 8)
        return total
    else:
        # _SC_PHYS_PAGES and _SC_PAGESIZE on Linux.
        let pages = sysconf(85)
        let size = sysconf(30)
        return (u64)pages * (u64)size if pages > 0 and size > 0 else 0

func min_f64(a: f64, b: f64) -> f64:
    return a if a < b else b

func max_f64(a: f64, b: f64) -> f64:
    return a if a > b else b