Skip to content

Instantly share code, notes, and snippets.

@DmitrySoshnikov
Last active June 8, 2024 01:04
Show Gist options
  • Save DmitrySoshnikov/c8d416624b65ece5ecbb893706d8865b to your computer and use it in GitHub Desktop.
Save DmitrySoshnikov/c8d416624b65ece5ecbb893706d8865b to your computer and use it in GitHub Desktop.
/**
* Educational "Free-list" memory allocator.
*
* Maintains explicit list of free memory blocks, reuses blocks on free.
* Implements "first-fit" strategy. Uses pre-allocated heap of 64 bytes,
* with 32-bit machine word size.
*
* TODO:
*
* - Implement "best-fit" strategy
* - Implement blocks merging on free
* - Implement blocks split on alloc
* - Implement segregated free list (bucket by block sizes).
*
* by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
* MIT License, (C) 2018
*/
/**
* 32-bit machine word.
*/
const WORD_SIZE_BYTES = 4;
/**
* Total heap size.
*/
const HEAP_SIZE_BYTES = 64;
/**
* 16 elements.
*/
const HEAP_ELEMENTS = HEAP_SIZE_BYTES / WORD_SIZE_BYTES;
/**
* 32-bit word aligned heap, 64 bytes of memory.
*/
const heap = new Int32Array(HEAP_ELEMENTS);
/**
* Free-list, contains pointers to free blocks.
*
* Initially the heap is free, so the pointer points to the byte 0, which
* contains the size (object header) of the block.
*/
const freeList = [0];
/**
* Object header size.
*
* In this implementation object header only stores the object size.
*/
const OBJECT_HEADER_SIZE = 4;
const OBJECT_HEADER_ELEM_SIZE = OBJECT_HEADER_SIZE / WORD_SIZE_BYTES;
/**
* Init the heap for the first free block.
*/
heap[0] = HEAP_SIZE_BYTES - OBJECT_HEADER_SIZE;
/**
* Memory blocks alignment by 4 for 32-bits word.
*
* malloc(4) -> 4
* malloc(2) -> 4
* malloc(5) -> 8
* etc.
*/
function align(x) {
return ((((x) - 1) >> 2) << 2) + WORD_SIZE_BYTES;
}
/**
* Allocates amount of byte on the heap, aligning by the word size,
* and reserving the space for the object header (OH).
*
* malloc(n) -> OH + align(n)
*/
function malloc(n) {
// Align by machine word size.
const origN = n;
n = align(n);
console.log(
`malloc(${origN}) = OH(${OBJECT_HEADER_SIZE}) + ${origN} + ` +
`align(${n - origN}) = ${OBJECT_HEADER_SIZE + n}`
);
// Number of heap elements.
const numElements = n / 4;
// Search for the first available block of needed size.
for (let i = 0; i < freeList.length; i++) {
const objectHeader = freeList[i];
// Size is first in the object header, just for readability.
const sizePointer = objectHeader + 0;
const size = heap[sizePointer];
// Got the block of the needed size:
if (size >= n) {
heap[sizePointer] = n;
freeList.splice(i, 1);
// Payload data pointer.
const payload = objectHeader + OBJECT_HEADER_ELEM_SIZE;
// Next free block if still can bump the pointer:
const nextFree = payload + numElements;
if (nextFree <= heap.length - 1) {
heap[nextFree] = size - n - OBJECT_HEADER_SIZE;
freeList.push(nextFree);
}
return payload;
}
}
return null;
}
/**
* Frees a block, adding it back to the free-list.
*/
function free(block) {
freeList.push(block - OBJECT_HEADER_ELEM_SIZE);
}
/**
* Dumps the heap, and free list.
*/
function dump() {
console.log('');
console.log({heap});
console.log({freeList});
console.log('\n--------------------------------------------------------------------------------');
}
// -----------------------------------------------------------------------------
// Tests: allocate
dump();
// Alloc 8 bytes (2 words).
const o1 = malloc(8);
// Write to the words:
heap[o1] = 100;
// Pointer arithmetics works, writing to next byte with
// correct offset of the word size.
heap[o1 + 1] = 200;
dump();
// Alloc 1 word, and write to it:
const o2 = malloc(4);
heap[o2] = 300;
dump();
// Alloc 3 bytes (aligned to 4), and write to it:
const o3 = malloc(3);
heap[o3] = 400;
dump();
// Free first object
free(o1);
dump();
// Allocate 32 bytes, taking the rest of the heap:
let o4 = malloc(32);
heap[o4++] = 5; heap[o4++] = 5;
heap[o4++] = 5; heap[o4++] = 5;
heap[o4++] = 5; heap[o4++] = 5;
heap[o4++] = 5; heap[o4++] = 5;
dump();
// We still can allocate an object in the space freed by o1:
// Alloc 1 byte, aligned to 4:
const o5 = malloc(1);
heap[o5] = 9;
dump();
/*
Exercises:
1. Currently object header only stores the size of the block: {size}.
Implement the following object header structure: {size, free, mark}
2. Use the `free` flag from the new object header to correctly identify
next block (notice the "bug" how allocator kept address 2 in the last
allocation, even though there is no enough space for data).
3. Implement Mark-Sweep garbage collector using the `mark` bit from the
new object header.
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment