Skip to content

Instantly share code, notes, and snippets.

@DmitrySoshnikov

DmitrySoshnikov/heap.js Secret

Last active Feb 10, 2019
Embed
What would you like to do?
Virtual heap in JavaScript
/**
* 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');
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.