dymokomi/luce-base
Source of release 0.42.0
0.42.0 / src / std / memory.lucb
#==============================================================================================
#
# memory - Allocators and byte primitives
#
# DESCRIPTION:
# The allocators of §12, the thread's current-allocator convention, the diagnostic
# records of an allocation failure, and the byte copy, move, set, read and write helpers.
#
#==============================================================================================
from windows_abi import SystemInfo
from windows_abi import GetSystemInfo
import platform
extern func malloc(size: usize) -> void*?
extern func c_free as "free"(block: void*)
extern func posix_memalign(memptr: void*?*, alignment: usize, size: usize) -> i32
extern func aligned_malloc as "_aligned_malloc"(size: usize, alignment: usize) -> void*?
extern func aligned_free as "_aligned_free"(block: void*)
extern func memcpy(target: void*, source: const void*, count: usize) -> void*
extern func memmove(target: void*, source: const void*, count: usize) -> void*
extern func memset(target: void*, value: i32, count: usize) -> void*
## What every allocator offers: blocks of bytes at an alignment, optionally
## resized in place, and given back (§12.4). Zero alignment means one. A nonempty
## block must meet the requested alignment; an allocator may refuse an unsupported
## alignment. Bump allocators support every positive alignment, not only powers of two.
pub interface Allocator:
func allocate(size: usize, alignment: usize) -> u8[]?
func resize(block: u8[], size: usize) -> bool
func release(block: u8[])
## A bump allocator over a caller's bytes. Only the last block can be resized or
## released; everything goes away together when the buffer does.
pub struct FixedBuffer: Allocator:
var data: u8[]
var used: usize
## An allocator handing out `buffer`'s bytes; only the last block resizes.
pub static func over(buffer: u8[]) -> FixedBuffer:
return FixedBuffer(data = buffer, used = 0)
## Allocate `size` bytes at `alignment`, or none when it cannot.
pub func allocate(size: usize, alignment: usize) -> u8[]?:
if size == 0:
return self.data[..<0]
let align = alignment if alignment > 0 else 1
let start = aligned_offset(self.data, self.used, align) else return none
if start > self.data.length or size > self.data.length - start:
return none
self.used = start + size
return self.data[start..<self.used]
## Try to resize `block` to `size` in place; whether it worked.
pub func resize(block: u8[], size: usize) -> bool:
if size == block.length:
return true
if block.length == 0:
return false
let start = (usize)block.data -? (usize)self.data.data else return false
if start > self.used or block.length != self.used - start:
return false
if start > self.data.length or size > self.data.length - start:
return false
self.used = start + size
return true
## Free `block`.
pub func release(block: u8[]):
if block.length == 0:
return
if diagnostic:
_ = memset(block.data, 221, block.length) # a fixed buffer releases all at once
let start = (usize)block.data - (usize)self.data.data
if start + block.length == self.used:
self.used = start
## Align the address inside a bounded span, without rounding an addition past
## usize's range. The remainder works for arbitrary positive byte alignments.
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
## The C library's heap.
pub struct CAllocator: Allocator:
var unused: u8
## Allocate `size` bytes at `alignment`, or none when it cannot.
pub func allocate(size: usize, alignment: usize) -> u8[]?:
if size == 0:
return u8[]((u8*)8, 0)
if alignment != 0 and (alignment & (alignment - 1)) != 0:
return none
let align = alignment if alignment > 8 else 8
var p: void*? = none
if platform.windows:
p = aligned_malloc(size, align)
elif posix_memalign(&p, align, size) != 0:
return none
let block = p else return none
return u8[]((u8*)block, size)
## Try to resize `block` to `size` in place; whether it worked.
pub func resize(block: u8[], size: usize) -> bool:
return size <= block.length
## Free `block`.
pub func release(block: u8[]):
if block.length == 0:
return
if not diagnostic:
release_heap(block.data)
return
# the diagnostic profile (§19.4): the block is filled with a pattern and held back, so
# a use after release reads the pattern rather than the next allocation; releasing
# it again, or writing it while it is held, is reported
lock(&records_lock)
if already_held(quarantine, block):
unlock(&records_lock)
trap("double free: a block was released twice")
_ = memset(block.data, (i32)released_fill, block.length)
let slot = quarantine_next % quarantine.length
if let old = quarantine[slot]:
if not still_released(old):
unlock(&records_lock)
trap("use after free: a released block was written after its release")
release_heap(old.data)
quarantine[slot] = block
quarantine_next += 1
unlock(&records_lock)
func release_heap(block: void*):
if platform.windows:
aligned_free(block)
else:
c_free(block)
## Bump allocation over a parent allocator, released all at once by `reset` or `destroy`
## (§12.4, §24.3). One thread at a time.
pub struct Arena: Allocator:
var parent: Allocator
var block: u8[]
var used: usize
## An arena of `capacity` bytes over `parent`, released all at once.
pub static func over(parent: Allocator, capacity: usize) -> Arena!:
let block = parent.allocate(capacity, 16) else error(exhausted, "memory.exhausted")
return Arena(parent = parent, block = block, used = 0)
## Allocate `size` bytes at `alignment`, or none when it cannot.
pub func allocate(size: usize, alignment: usize) -> u8[]?:
if size == 0:
return self.block[..<0]
let align = alignment if alignment > 0 else 1
let start = aligned_offset(self.block, self.used, align) else return none
let end = start +? size else return none
if end > self.block.length:
return none
self.used = end
return self.block[start..<end]
## Try to resize `block` to `size` in place; whether it worked.
pub func resize(block: u8[], size: usize) -> bool:
if size == block.length:
return true
if block.length == 0:
return false
# the last block may grow or shrink in place
let start = (usize)block.data -? (usize)self.block.data else return false
if start > self.used or block.length != self.used - start:
return false
if start > self.block.length or size > self.block.length - start:
return false
self.used = start + size
return true
## Free `block`.
pub func release(block: u8[]):
if diagnostic and block.length > 0:
_ = memset(block.data, 221, block.length) # an arena releases all at once
## What has been handed out since the last reset, and what the arena holds in all.
pub func in_use() -> usize:
return self.used
## The arena's total capacity in bytes.
pub func capacity() -> usize:
return self.block.length
## Forget every allocation; the storage is reused from its start.
pub func reset():
self.used = 0
## Give the storage back to the parent; the arena is empty afterwards.
pub func destroy():
self.parent.release(self.block)
self.block = self.block[..<0]
self.used = 0
## Whole pages from the host, each block its own mapping (§12.4). Safe from several threads.
pub struct PageAllocator: Allocator:
var unused: u8
## Allocate `size` bytes at `alignment`, or none when it cannot.
pub func allocate(size: usize, alignment: usize) -> u8[]?:
if size == 0:
return u8[]((u8*)8, 0)
let page = page_size()
if alignment > page or (alignment != 0 and page % alignment != 0):
return none
let padded = size +? (page - 1) else return none
let rounded = padded // page * page
let mapped = map_pages(rounded) else return none
if (usize)mapped == ~(usize)0:
return none
return u8[]((u8*)mapped, rounded)
## Try to resize `block` to `size` in place; whether it worked.
pub func resize(block: u8[], size: usize) -> bool:
return size <= block.length
## Free `block`.
pub func release(block: u8[]):
if block.length == 0:
return
if not diagnostic:
unmap_pages(block)
return
# the diagnostic profile (§19.4): the mapping is filled and kept for a while, so a
# use after release reads the pattern rather than faulting or reading a new mapping
lock(&records_lock)
if already_held(held_pages, block):
unlock(&records_lock)
trap("double free: pages were released twice")
_ = memset(block.data, (i32)released_fill, block.length)
let slot = held_next % held_pages.length
if let old = held_pages[slot]:
if not still_released(old):
unlock(&records_lock)
trap("use after free: released pages were written after their release")
unmap_pages(old)
held_pages[slot] = block
held_next += 1
unlock(&records_lock)
extern func mmap(address: void*?, length: usize, protection: i32, flags: i32, descriptor: i32, offset: i64) -> void*?
## `MAP_PRIVATE | MAP_ANON`: `MAP_ANON` is 0x1000 on macOS and 0x20 on Linux; the
## protection `PROT_READ | PROT_WRITE` is 3 on both.
let private_anonymous: i32 = 4098 if platform.macos else 34
extern func munmap(address: void*, length: usize) -> i32
extern func getpagesize() -> i32
extern func VirtualAlloc(address: void*?, size: usize, kind: u32, protection: u32) -> void*?
extern func VirtualFree(address: void*, size: usize, kind: u32) -> i32
## The host's memory page size in bytes: the one query `os.page_size` and the threads'
## stack sizes use too.
pub func page_size() -> usize:
if platform.windows:
var info: SystemInfo = ---
GetSystemInfo(&info)
return (usize)info.page_size
return (usize)getpagesize()
func map_pages(size: usize) -> void*?:
if platform.windows:
return VirtualAlloc(none, size, 12288, 4)
return mmap(none, size, 3, private_anonymous, -1, 0)
func unmap_pages(block: u8[]):
if platform.windows:
_ = VirtualFree(block.data, 0, 32768)
else:
_ = munmap(block.data, block.length)
## `--profile diagnostic`: set by the startup shim before `startup` runs.
pub var diagnostic: bool
## An allocation the diagnostic profile recorded (§19.4): the block, its size, and where.
pub struct Site:
## The block's address, or none for a failed request.
pub var address: void*?
## The requested size in bytes.
pub var size: usize
## The function that requested it.
pub var function: str
## The source line of the request.
pub var line: u32
var sites: Site[256]
var site_next: usize
## The diagnostic profile's records are shared by every thread: a short spin lock guards
## each update, on the atomic `@bool` alone, since this module is below `sync`.
var records_lock: @bool
func lock(flag: (@bool)*):
while true:
let (exchanged, observed) = flag.cas(false, true)
_ = observed
if exchanged:
return
func unlock(flag: (@bool)*):
flag.store(false)
## Called by the compiled program after each allocation under `--profile diagnostic`.
## The record keeps the most recent 256 allocations, oldest first: once full, the oldest
## goes and the newest takes the last place.
pub func note_site(address: void*?, size: usize, function: str, line: u32):
lock(&records_lock)
if site_next < sites.length:
sites[site_next] = Site(address = address, size = size, function = function, line = line)
else:
var i: usize = 1
while i < sites.length:
sites[i - 1] = sites[i]
i += 1
sites[sites.length - 1] = Site(address = address, size = size, function = function, line = line)
site_next += 1
unlock(&records_lock)
## The allocations recorded so far, the most recent 256 at most, oldest first. A view of
## the record: read it while no other thread allocates.
pub func allocation_sites() -> const Site[]:
let held = site_next if site_next < sites.length else sites.length
return sites[..<held]
## The released blocks the diagnostic profile still holds, oldest freed first.
var quarantine: (u8[]?)[256]
var quarantine_next: usize
## The released mappings the diagnostic profile still holds, oldest first.
var held_pages: (u8[]?)[8]
var held_next: usize
## The byte a released block is filled with under the diagnostic profile.
let released_fill: u8 = 221
## The byte unwritten storage is filled with under the diagnostic profile: `---` storage,
## `memory.allocate` and `memory.frame`; the compiler writes the same byte, 0xAA.
let unwritten_fill: u8 = 170
## Whether `block` is among the released blocks still `held`: releasing it again is a
## double free.
func already_held(blocks: const (u8[]?)[], block: u8[]) -> bool:
for entry in blocks:
if let kept = entry:
if kept.data == block.data:
return true
return false
## Whether every byte of a held block is still the fill it was given at release: a write
## through a dangling pointer changes one.
func still_released(block: const u8[]) -> bool:
for byte in block:
if byte != released_fill:
return false
return true
## Allocation failed: out of memory.
# mark: Diagnostics and heap ==================================================================
## Allocation failed because memory is exhausted.
pub let exhausted: ErrorCode = ErrorCode.package(1)
## No allocator is current (§12.3).
pub let unset: ErrorCode = ErrorCode.package(2)
var c_allocator: CAllocator
## The current allocator of this thread (§12.3) and the process's initial one.
pub local var allocator: Allocator
## The process's C heap allocator.
pub var heap: Allocator
## Run by the startup shim before `main`, and by `thread.spawn` in a new thread.
pub func startup():
heap = &c_allocator
allocator = heap
## Copy `count` elements from `source` to `target` (no overlap).
# mark: Byte primitives =======================================================================
## Copy `count` elements from `source` into `target`.
pub func copy[T](target: T[], source: const T[], count: usize):
if count > target.length or count > source.length:
trap("index out of bounds")
if count > 0:
_ = memcpy(target.data, source.data, count * size_of(T))
## Copy `count` elements, allowing `source` and `target` to overlap.
pub func move[T](target: T[], source: const T[], count: usize):
if count > target.length or count > source.length:
trap("index out of bounds")
if count > 0:
_ = memmove(target.data, source.data, count * size_of(T))
## Set every byte of `target` to `value`.
pub func set(target: u8[], value: u8):
if target.length > 0:
_ = memset(target.data, (i32)value, target.length)
## Read a `T` from `address`, which may be unaligned.
pub func read[T](address: const void*) -> T:
var value: T = ---
_ = memcpy(&value, address, size_of(T))
return value
## Write `value` to `address`, which may be unaligned.
pub func write[T](address: void*, value: T):
var copy_of = value
_ = memcpy(address, ©_of, size_of(T))
## `count` uninitialised elements of `T` in the frame of the function that calls this, at
## most `most` (a constant; `most * size_of(T)` at most 4096 bytes), freed when that function
## returns (§12.7). The compiler takes the storage at the call, so this body never runs.
pub func frame[T](count: usize, most: usize) -> T[]:
trap("memory.frame is answered where it is called")
## `size` unwritten bytes aligned to `alignment`, from the current allocator: storage a
## structure lays out itself (§12.2), given back with `free`; the diagnostic profile fills
## them with 0xAA (§19.4). Fails with `memory.exhausted`.
pub func allocate(size: usize, alignment: usize) -> u8[]!:
let block = allocator.allocate(size, alignment) else error(exhausted, "memory.exhausted")
if diagnostic:
_ = memset(block.data, (i32)unwritten_fill, block.length)
return block
## `block` with `size` bytes: in place when the current allocator can, else a
## new block with the old bytes copied and the old block released. The bytes past the
## old ones are unwritten, 0xAA under the diagnostic profile.
pub func grow(block: u8[], size: usize) -> u8[]!:
var grown: u8[] = ---
if allocator.resize(block, size):
grown = u8[](block.data, size)
else:
grown = allocator.allocate(size, 8) else error(exhausted, "memory.exhausted")
let keep = block.length if block.length < size else size
if keep > 0:
_ = memcpy(grown.data, block.data, keep)
allocator.release(block)
if diagnostic and size > block.length:
_ = memset(&grown[block.length], (i32)unwritten_fill, size - block.length)
return grown