Heap Allocator

C0 Heap Allocator

Implemented in ./utility/memory.ts

interface C0HeapAllocator {
    // Basic Operations
    malloc(size: number): C0Pointer
    free(ptr: C0Pointer): void
    // Clear the whole heap memory, called when C0VM restarts
    clear(): void

    // Return the memory pool as ArrayBuffer - used for debug only
    // Should not change the memory by altering the ArrayBuffer here
    debug_getMemPool(): ArrayBuffer | undefined
    // Operations on Heap Memory
    cmstore(ptr: C0Pointer, value: DataView): void
    cmload(ptr: C0Pointer): DataView

    imstore(ptr: C0Pointer, value: DataView): void
    imload(ptr: C0Pointer): DataView

    amstore(ptr: C0Pointer, stored_ptr: C0Pointer): void
    amload(ptr: C0Pointer): DataView

    deref(ptr: C0Pointer, block_size: number): DataView
}

// Factory Function for HeapAllocator
export function createHeap(
    allocator: C0HeapAllocatorConstructor,
    size ?: number
): C0HeapAllocator

In C0VM.ts, we use a ArrayBuffer to simulate the heap memory of a C program.

Since we are following the C's convention (0x0000000000000000 is a NULLpointer), the memory address at 0x00 is reserved and never touched.

malloc & free Functions

A C0HeapAllocator is able to manage its own memory pool and encapsulate the details with malloc and free interface.

malloc will allocate a block of memory and return a C0Pointer that referes to the starting position of the allocated memory segment.

free will free/release a block of memory. When the pointer given to free does not points to the start of memory segment, c0_memory_error should be throw to caller. (since free a memory with result of pointer arithmetic will lead to undefined behavior in C)

deref Function

The deref function is a simulation of the * operator in C.

Given a C0Pointer, the deref function will return a DataView that is an alias of the ArrayBuffer of the memory block that pointer is pointing to.

Example

For some pointer 0x0000_0000_0070_00FF, passing it to deref will return you a DataView of the segment [0x0000_0070, 0x0000_00FF).

0x0000_0000                            0x0000_00FF
|=====================^================|
^- addr = 0x0000_0000 ^- offset = 0x0070

It is always recommended to use this function to access heap memory.

Naïve Implementation of C0HeapAllocator

A naïve implementation of C0HeapAllocator is the VM_Memory class. Defined as follow:

export class VM_Memory implements C0HeapAllocator {
    private memory_pool: ArrayBuffer;
    private heap_top_address: number;
    private memory_size: number;

    constructor(size?: number);

    malloc(size: number): C0Pointer;
    free(ptr: C0Pointer): void;
    clear(): void;

    debug_getMemPool(): ArrayBuffer;

    cmstore(ptr: C0Pointer, value: DataView): void;
    cmload(ptr: C0Pointer): DataView;
    imstore(ptr: C0Pointer, value: DataView): void;
    imload(ptr: C0Pointer): DataView;
    amstore(ptr: C0Pointer, stored_ptr: DataView): void;
    amload(ptr: C0Pointer): DataView;

    deref(ptr: DataView, block_size: number): DataView
}

Written in ./utility/memory.ts, the VM_Memory class is a naïve implementation to the C0HeapAllocator interface.

The private property heap_top_address will keep track of the boundary between allocated and unallocated parts of the memory pool. Whenever a malloc is called to allocate n bytes of heap memory, the allocator will give the memory segment [heap_top, heap_top + n) to the caller and make heap_top += n.

Since 0x00 is reserved for NULL, allocator will start to allocate memory from 0x01.

free is not implemented in this naive implementation! Currently, calling the free will only write zero to the memory block the pointer is pointing at. Memory will NOT be re-claimed or re-allocated anyway.

In the future, we may implement a fancy allocator which will re-claim the freed memory.