Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-base

Source of release 0.46.0

0.46.0 / src / support / arena.lucb

#==============================================================================================
#
#   arena - Compiler command storage
#
#   DESCRIPTION:
#       Chunk ownership lives here; allocation mechanics are the standard memory.Allocator
#       interface, on every host.
#
#==============================================================================================

import memory

# mark: The arena =============================================================================

## An arena that acquires additional chunks without moving earlier allocations.
## The parent is retained by value; it must outlive this owner. Borrow the arena
## on one thread, and destroy exactly one owner. Reset reuses its chunks.
pub struct Arena: memory.Allocator:
    ## The allocator the chunks come from.
    pub var parent: memory.Allocator
    var first: ArenaChunk*?
    var last: ArenaChunk*?
    var active: ArenaChunk*?
    var chunk_size: usize

    ## An arena over `parent`, taking chunks of `chunk_size` bytes.
    pub func init(parent: memory.Allocator, chunk_size: usize = 65536):
        self.parent = parent
        self.first = none
        self.last = none
        self.active = none
        self.chunk_size = chunk_size if chunk_size > 0 else 65536

    ## A block of `size` bytes at `alignment`, from the active chunk or a fresh one.
    pub func allocate(size: usize, alignment: usize) -> u8[]?:
        if size == 0:
            return u8[]((u8*)(usize)8, 0)
        let align = alignment if alignment > 0 else 1
        # Reserve enough padding for an arbitrary positive alignment. Refusing
        # overflowing requests leaves both the list and existing data unchanged.
        let minimum = size +? (align - 1) else return none
        var cursor = self.active
        while let chunk = cursor:
            if let start = aligned_offset(chunk.bytes, chunk.used, align):
                if size <= chunk.bytes.length - start:
                    chunk.used = start + size
                    self.active = chunk
                    return chunk.bytes[start..<chunk.used]
            cursor = chunk.next
        let capacity = minimum if minimum > self.chunk_size else self.chunk_size
        let total = capacity +? memory.size_of(ArenaChunk) else return none
        let backing = self.parent.allocate(total, memory.align_of(ArenaChunk)) else return none
        let chunk = (ArenaChunk*)backing.data
        *chunk = ArenaChunk(backing = backing, bytes = backing[memory.size_of(ArenaChunk)..])
        let start = aligned_offset(chunk.bytes, 0, align) else trap("arena chunk alignment")
        chunk.used = start + size
        if let previous = self.last:
            previous.next = chunk
        else:
            self.first = chunk
        self.last = chunk
        self.active = chunk
        return chunk.bytes[start..<chunk.used]

    ## Only the most recent allocation in the active chunk can change in place.
    pub func resize(block: u8[], size: usize) -> bool:
        if size == block.length:
            return true
        if block.length == 0:
            return false
        let chunk = self.active else return false
        let start = (usize)block.data -? (usize)chunk.bytes.data else return false
        if start > chunk.used or block.length != chunk.used - start:
            return false
        if size > chunk.bytes.length - start:
            return false
        chunk.used = start + size
        return true

    ## Reclaim `block` when it is the last allocation in the active chunk; else keep it.
    pub func release(block: u8[]):
        let chunk = self.active else return
        let start = (usize)block.data -? (usize)chunk.bytes.data else return
        if start <= chunk.used and block.length == chunk.used - start:
            chunk.used = start

    ## Reuse every chunk for fresh allocations, releasing none.
    pub func reset():
        var cursor = self.first
        while let chunk = cursor:
            chunk.used = 0
            cursor = chunk.next
        self.active = self.first

    ## Release every chunk back to the parent.
    pub func destroy():
        var cursor = self.first
        self.first = none
        self.last = none
        self.active = none
        while let chunk = cursor:
            let next = chunk.next
            let backing = chunk.backing
            self.parent.release(backing)
            cursor = next

## Chunk metadata shares its parent's allocation, so allocation failure cannot
## strand a separate list node. All links are captured before releasing a chunk.
struct ArenaChunk:
    var backing: u8[]
    var bytes: u8[]
    var next: ArenaChunk*?
    var used: usize

## Align the address inside a bounded span, without rounding an addition past
## usize's range. The remainder works for arbitrary positive byte alignments. The same as
## `memory`'s, which the seed that builds the compiler does not have.
func aligned_offset(storage: u8[], used: usize, alignment: usize) -> usize?:
    if used > storage.length:
        return none
    let address = (usize)storage.data +? used else return none
    let remainder = address % alignment
    let padding = 0 if remainder == 0 else alignment - remainder
    if padding > storage.length - used:
        return none
    return used + padding

# mark: A limited allocator for the tests =====================================================

struct Budget: memory.Allocator:
    var remaining: usize = 2
    var outstanding: usize

    func allocate(size: usize, alignment: usize) -> u8[]?:
        if self.remaining == 0:
            return none
        let block = memory.heap.allocate(size, alignment) else return none
        self.remaining -= 1
        self.outstanding += 1
        return block

    func resize(block: u8[], size: usize) -> bool:
        return false

    func release(block: u8[]):
        memory.heap.release(block)
        self.outstanding -= 1

test "arena growth preserves addresses, handles refusal and reuses released storage":
    var owner = Budget()
    var allocator = Arena(&owner, 64)
    let first = allocator.allocate(17, 7) else trap("first chunk")
    assert((usize)first.data % 7 == 0)
    memory.set(first, 19)
    let large = allocator.allocate(4096, 32) else trap("larger chunk")
    assert((usize)large.data % 32 == 0)
    memory.set(large, 71)
    assert(owner.outstanding == 2)
    assert(allocator.allocate(8192, 16) == none)
    assert(allocator.allocate(18446744073709551615, 16) == none)
    assert(allocator.allocate(1, 18446744073709551615) == none)
    for value in first:
        assert(value == 19)
    for value in large:
        assert(value == 71)
    assert(not allocator.resize(first, 20))
    assert(allocator.resize(large, 1024))
    assert(allocator.resize(large[..<1024], 4096))
    allocator.reset()
    let reused = allocator.allocate(4096, 32) else trap("reset must reuse chunks")
    assert(reused.data == large.data and owner.outstanding == 2)
    allocator.destroy()
    allocator.destroy()
    assert(owner.outstanding == 0)