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