malloc.js

/**
 * 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.

*/