Virtual heap in JavaScript

heap.js

/**
 * Virtual heap.
 *
 * by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
 * MIT Style License, 2019
 */

const assert = require('assert');

/**
 * Word size, bytes.
 */
const WORD_SIZE = 8;

/**
 * Header size: size, used, next.
 */
const HEADER_SIZE = 3;

/**
 * Heap size, 4 MB.
 */
const HEAP_SIZE = 4 * 1024 ** 2;

/**
 * Heap, 4 MB.
 */
const heap = new ArrayBuffer(HEAP_SIZE);

/**
 * Byte view.
 */
const hByte = new Int8Array(heap);

/**
 * Word view.
 */
const hWord = new Float64Array(heap);

/**
 * Block structure.
 */
const SIZE_OFFSET = 0;
const USED_OFFSET = 1;
const NEXT_OFFSET = 2;
const DATA_OFFSET = 3;

/**
 * Heap start.
 */
let heapStart = null;

/**
 * Current top block.
 */
let top = heapStart;

/**
 * Program break.
 */
let _brk = 0;

/**
 * Search modes.
 */
const SearchMode = {
  FirstFit: 0,
  NextFit: 1,
  BestFit: 2,
  FreeList: 3,
  SegregatedList: 4,
};

/**
 * Current search mode.
 */
let searchMode = SearchMode.FirstFit;

/**
 * Sets the break to the passed address.
 */
function brk(address) {
  _brk = address;
}

/**
 * Increases the brk on passed amount.
 */
function sbrk(increment) {
  if (increment === 0) {
    return _brk;
  }

  const newBrk = _brk + increment;

  if (newBrk > HEAP_SIZE) {
    return -1;
  }

  brk(newBrk);
}

/**
 * Requests a block of the passed size.
 */
function requestFromOS(size) {
  const block = sbrk(0);

  if (sbrk(allocSize(size)) == -1) {
    return null;
  }

  return block * WORD_SIZE;
}

/**
 * Allocates a block.
 */
function malloc(size) {
  size = align(size);

  // Try finding the block:
  let block = findBlock(size);
  if (block !== null) {
    return getDataPointer(block);
  }

  // Block wasn't found, request from OS:
  block = requestFromOS(size);

  if (heapStart === null) {
    heapStart = block;
  }

  setSize(block, size);
  setUsed(block, true);

  if (top !== null) {
    setNext(top, block);
  }

  top = block;

  return getDataPointer(block);
}

/**
 * Tries finding the block.
 */
function findBlock(size) {
  switch (searchMode) {
    case SearchMode.FirstFit:
      return firstFit(size);
  }
}

/**
 * First-fit search.
 */
function firstFit(size) {
  let foundBlock = null;
  traverse(block => {
    if (getUsed(block) || getSize(block) < size) {
      return;
    }
    foundBlock = listAllocate(block, size);
    return STOP_ITER;
  });
  return foundBlock;
}

/**
 * Allocates a block, splitting if needed.
 */
function listAllocate(block, size) {
  setSize(block, size);
  setUsed(block, true);
  return block;
}

/**
 * Frees the object.
 */
function free(data) {
  const block = getHeader(data);
  setUsed(block, false);
}

/**
 * Sets size.
 */
function setSize(block, size) {
  hWord[block + SIZE_OFFSET] = size;
}


/**
 * Gets sizes.
 */
function getSize(block) {
  return hWord[block + SIZE_OFFSET];
}

/**
 * Sets used.
 */
function setUsed(block, used) {
  hWord[block + USED_OFFSET] = used;
}

/**
 * Gets used.
 */
function getUsed(block) {
  return hWord[block + USED_OFFSET];
}

/**
 * Sets next.
 */
function setNext(block, next) {
  hWord[block + NEXT_OFFSET] = next;
}

/**
 * Gets next.
 */
function getNext(block) {
  return hWord[block + NEXT_OFFSET];
}

/**
 * Gets data.
 */
function getDataPointer(block) {
  return block + HEADER_SIZE;
}

/**
 * Gets next.
 */
function getNext(block) {
  return hWord[block + NEXT_OFFSET];
}

/**
 * Aligns the size by the machine word.
 */
function align(n) {
  return (n + WORD_SIZE - 1) & ~(WORD_SIZE - 1);
}

/**
 * Writes a word.
 */
function writeWord(data, value) {
  hWord[data / WORD_SIZE] = value;
}

/**
 * Returns total allocation size considering
 * object header and padding.
 */
function allocSize(size) {
  return size + HEADER_SIZE * WORD_SIZE;
}

/**
 * Returns headers.
 */
function getHeader(data) {
  return data - HEADER_SIZE;
}

/**
 * Value used to stop iteration.
 */
const STOP_ITER = {};

/**
 * Traverses the blocks.
 */
function traverse(callback) {
  let block = heapStart;
  callback(block);
  block = getNext(block);
  while (block !== 0) {
    let result = callback(block);
    if (result == STOP_ITER) {
      break;
    }
    block = getNext(block);
  }
}

/**
 * Prints blocks.
 */
function printBlocks() {
  let info = [];
  traverse(block => {
    info.push(`[${getSize(block)}, ${getUsed(block)}]`);
  });
  console.log(info.join(' '));
}

// -----------------------------------------------------------------------------

const p1 = malloc(3);
const p1b = getHeader(p1);
assert.equal(getSize(p1b), WORD_SIZE);
writeWord(p1, 255);
printBlocks();

const p2 = malloc(8);
const p2b = getHeader(p2);
assert.equal(getSize(p2b), 8);
printBlocks();

free(p2);
assert.equal(getUsed(p2b), false);
printBlocks();

const p3 = malloc(8);
const p3b = getHeader(p3);
assert.equal(getSize(p3b), 8);
assert.equal(p3b, p2b);
printBlocks();

console.log('\nAll assertions passed.\n');