dymokomi/luce-js
Source of release 0.6.0
0.6.0 / src / engine / malloc.lucb
#==============================================================================================
#
# malloc - The JS malloc small-block allocator: arenas of 31 size classes
#
# DESCRIPTION:
# Port of quickjs.c "JS malloc" (lines 1416-1778). Every block the engine allocates
# is preceded by an 8-byte MallocBlockHeader, which also holds the reference count
# and GC bits of GC objects and strings (`js_rc`). Blocks up to 512 bytes, header
# included, come from 4 KiB arenas of equally sized blocks; larger ones come from
# the host allocator with a header of their own. JS_MALLOC_USE_ITER (off upstream)
# and its js_malloc_iter are not ported; JS_MALLOC_LARGE_BLOCKS_ONLY is 0.
#
#==============================================================================================
# mark: Block sizes and headers =================================================================
# max overhead for size >= 64: 12.5%
let js_malloc_block_sizes: u16[31] = [
16,
24,
32,
40,
48,
56,
64,
72,
80,
88,
96,
104,
112,
120,
128,
144,
160,
176,
192,
208,
224,
240,
256,
288,
320,
352,
384,
416,
448,
480,
512,
]
## The size class of a small block of `size` bytes, header included, or
## `js_malloc_block_size_count` when it is too large for the arenas.
func get_block_size_index(size: usize) -> i32:
if size <= 16:
return 0
elif size <= 128:
return (i32)((size + 7) // 8) - 2
elif size <= 256:
return (i32)((size + 15) // 16) + 6
elif size <= 512:
return (i32)((size + 31) // 32) + 14
else:
return (i32)js_malloc_block_size_count
## The header of the one block that answers zero-sized requests.
func get_zero_size_block(s: MallocContext*) -> MallocBlockHeader*:
return &s.zero_size_block
## The user data of a block: the bytes just after its header (JSMallocBlockHeader.user_data).
func block_user_data(b: MallocBlockHeader*) -> void*:
return (u8*)b + memory.size_of(MallocBlockHeader)
## The header before a js_malloc'ed block (js_rc): it holds the reference count of GC
## objects and strings.
func js_rc(ptr: const void*) -> MallocBlockHeader*:
return (MallocBlockHeader*)((const u8*)ptr - memory.size_of(MallocBlockHeader))
func js_malloc_init(s: MallocContext*):
_ = cutils.memset(s, 0, memory.size_of(MallocContext))
get_zero_size_block(s).block_idx = free_nil
for i in 0..<js_malloc_block_size_count:
cutils.init_list_head(&s.arena_list[i])
cutils.init_list_head(&s.free_arena_list[i])
## The header of block `idx` of an arena; the blocks follow the arena header.
func get_arena_block(ar: MallocArena*, idx: u32, block_size: u32) -> MallocBlockHeader*:
return (MallocBlockHeader*)((u8*)ar + memory.size_of(MallocArena) + (usize)idx * (usize)block_size)
# mark: Allocation ==============================================================================
func js_malloc_new_arena(s: MallocContext*, block_size_idx: i32) -> MallocArena*?:
let block_size = (i32)js_malloc_block_sizes[block_size_idx]
let n_blocks = (i32)((js_malloc_arena_size - memory.size_of(MallocArena)) // (usize)block_size)
let host_malloc = s.mf.js_malloc
let p = host_malloc(&s.malloc_state, memory.size_of(MallocArena) + (usize)(n_blocks * block_size)) else return none
let ar = (MallocArena*)p
ar.block_size_idx = (u8)block_size_idx
ar.n_blocks = (u16)n_blocks
ar.n_used_blocks = 0
ar.first_free_block = 0
# chain every block on the free list; block_idx is free_next while a block is free
for i in 0..<n_blocks - 1:
let b = get_arena_block(ar, (u32)i, (u32)block_size)
b.block_idx = (u16)(i + 1)
b.block_size_idx = (u8)block_size_idx
let last = get_arena_block(ar, (u32)(n_blocks - 1), (u32)block_size)
last.block_idx = free_nil
last.block_size_idx = (u8)block_size_idx
# add to the head
cutils.list_add(&ar.link, &s.arena_list[block_size_idx])
cutils.list_add(&ar.free_link, &s.free_arena_list[block_size_idx])
return ar
func js_malloc_large(s: MallocContext*, size: usize) -> void*?:
# a size so large that the header overflows cannot be allocated (C would wrap)
let total_size = memory.size_of(MallocLargeBlockHeader) +? size else return none
let host_malloc = s.mf.js_malloc
let p = host_malloc(&s.malloc_state, total_size) else return none
let b = (MallocLargeBlockHeader*)p
b.header.block_idx = free_nil
b.header.block_size_idx = 0xff # fail safe
return block_user_data(&b.header)
## The size of a small block holding `size` user bytes, header included, or none when
## the rounding overflows (C would wrap).
func small_block_total_size(size: usize) -> usize?:
# the overflow tests spelled out: `+?` lowers to a call of the runtime's generic
# checked addition, on every allocation
let largest: usize = ~(usize)0
if size > largest - (js_malloc_align - 1):
return none
let rounded = (size + (js_malloc_align - 1)) & ~(js_malloc_align - 1)
if rounded > largest - memory.size_of(MallocBlockHeader):
return none
return rounded + memory.size_of(MallocBlockHeader)
## Allocate `size` bytes (__js_malloc); none if the host allocator fails.
func js_malloc_raw(s: MallocContext*, size: usize) -> void*?:
if size == 0:
return block_user_data(get_zero_size_block(s))
let total_size = small_block_total_size(size) else return none
if total_size > js_malloc_max_small_size:
return js_malloc_large(s, size)
let block_size_idx = get_block_size_index(total_size)
let block_size = (u32)js_malloc_block_sizes[block_size_idx]
let head = &s.free_arena_list[block_size_idx]
let el = head.next else trap("js_malloc: unlinked free arena list")
var found: MallocArena*? = none
if el == head:
found = js_malloc_new_arena(s, block_size_idx)
else:
found = (MallocArena*)((u8*)el - memory.offset_of(MallocArena, free_link))
let ar = found else return none
let block_idx = ar.first_free_block
let b = get_arena_block(ar, (u32)block_idx, block_size)
ar.first_free_block = b.block_idx # free_next
b.block_idx = block_idx
ar.n_used_blocks += 1
if ar.n_used_blocks == ar.n_blocks:
cutils.list_del(&ar.free_link)
return block_user_data(b)
## Free a block (__js_free); none is ignored.
func js_free_raw(s: MallocContext*, ptr: void*?):
let p = ptr else return
let b = js_rc(p)
if b.block_idx == free_nil:
# large or zero size block
if b == get_zero_size_block(s):
return # nothing to do
# the large block header is the block header (container_of header.user_data)
let lb = (MallocLargeBlockHeader*)b
let host_free = s.mf.js_free
host_free(&s.malloc_state, lb)
else:
let block_idx = (usize)b.block_idx
let block_size_idx = (usize)b.block_size_idx
let block_size = (usize)js_malloc_block_sizes[block_size_idx]
let ar = (MallocArena*)((u8*)b - block_size * block_idx - memory.size_of(MallocArena))
b.block_idx = ar.first_free_block # free_next
ar.first_free_block = (u16)block_idx
# add back to the free list if needed
if ar.n_used_blocks == ar.n_blocks:
cutils.list_add(&ar.free_link, &s.free_arena_list[block_size_idx])
ar.n_used_blocks -= 1
if ar.n_used_blocks == 0:
cutils.list_del(&ar.link)
cutils.list_del(&ar.free_link)
let host_free = s.mf.js_free
host_free(&s.malloc_state, ar)
## Resize a block (__js_realloc). A null `ptr` allocates; a zero `size` frees and
## answers none. The GC bits and reference count move with the block.
func js_realloc_raw(s: MallocContext*, ptr: void*?, size: usize) -> void*?:
let p = ptr else return js_malloc_raw(s, size)
if size == 0:
js_free_raw(s, p)
return none
let b = js_rc(p)
if b.block_idx == free_nil:
if b == get_zero_size_block(s):
return js_malloc_raw(s, size)
let lb = (MallocLargeBlockHeader*)b
let total_size = memory.size_of(MallocLargeBlockHeader) +? size else return none
let host_realloc = s.mf.js_realloc
let q = host_realloc(&s.malloc_state, lb, total_size) else return none
let new_lb = (MallocLargeBlockHeader*)q
new_lb.header.block_idx = free_nil
new_lb.header.block_size_idx = 0xff # fail safe
return block_user_data(&new_lb.header)
let block_size = (usize)js_malloc_block_sizes[b.block_size_idx]
let total_size = small_block_total_size(size) else return none
if total_size <= block_size:
return p
let new_ptr = js_malloc_raw(s, size) else return none
let new_b = js_rc(new_ptr)
# copy the GC data (gc_obj_type and mark)
new_b.gc_bits = b.gc_bits
new_b.ref_count = b.ref_count
# copy the data
let old_size = block_size - memory.size_of(MallocBlockHeader)
let copy_size = old_size if size > old_size else size
_ = cutils.memcpy(new_ptr, p, copy_size)
js_free_raw(s, p)
return new_ptr
## The usable size of a block (__js_malloc_usable_size); 0 for none, the zero-size
## block, and large blocks when the host cannot tell.
func js_malloc_usable_size_raw(s: MallocContext*, ptr: const void*?) -> usize:
let p = ptr else return 0
let b = js_rc(p)
if b.block_idx == free_nil:
if b == get_zero_size_block(s):
return 0
let lb = (const MallocLargeBlockHeader*)b
if let usable_size = s.mf.js_malloc_usable_size:
var size = usable_size(lb)
if size != 0:
size -= memory.size_of(MallocLargeBlockHeader)
return size
return 0
let block_size = (usize)js_malloc_block_sizes[b.block_size_idx]
return block_size - memory.size_of(MallocBlockHeader)