mirror of
https://github.com/fluencelabs/assemblyscript
synced 2025-04-26 15:32:16 +00:00
238 lines
9.7 KiB
HTML
238 lines
9.7 KiB
HTML
<script>
|
|
// Configuration - must match actual implementation
|
|
const AL_BITS = 4;
|
|
const SL_BITS = 4;
|
|
const OVERHEAD = 16;
|
|
|
|
const SL_SIZE = 1 << SL_BITS;
|
|
const SB_BITS = AL_BITS + SL_BITS;
|
|
const FL_BITS = 31 - SB_BITS;
|
|
const HL_SIZE = FL_BITS * SL_SIZE;
|
|
|
|
var exports;
|
|
var ROOT;
|
|
var U32;
|
|
fetch("untouched.wasm").then(result =>
|
|
result.arrayBuffer()
|
|
).then(buffer =>
|
|
WebAssembly.instantiate(buffer, {
|
|
env: {
|
|
abort: function(msg, file, line, column) {
|
|
console.log("abort: " + getString(msg) + " at " + getString(file) + ":" + line + ":" + column);
|
|
},
|
|
trace: function(msg, n, ...args) {
|
|
console.log("trace: " + getString(msg) + " " + args.slice(0, n).join(" "));
|
|
}
|
|
}
|
|
})
|
|
).then(result => {
|
|
exports = result.instance.exports;
|
|
if (exports.__start) exports.__start();
|
|
U32 = new Uint32Array(exports.memory.buffer);
|
|
var first = exports.__alloc(255);
|
|
exports.__free(first);
|
|
ROOT = first - 17;
|
|
while (!U32[ROOT >> 2]) --ROOT; // find tail
|
|
ROOT -= (1 + FL_BITS + HL_SIZE) << 2;
|
|
init();
|
|
update();
|
|
});
|
|
|
|
function getString(ptr) {
|
|
if (!ptr) return "null";
|
|
var U32 = new Uint32Array(exports.memory.buffer);
|
|
var U16 = new Uint16Array(exports.memory.buffer);
|
|
var len16 = U32[(ptr - 12) >>> 2] >>> 1; // TODO: old header
|
|
var ptr16 = ptr >>> 1;
|
|
return String.fromCharCode.apply(String, U16.subarray(ptr16, ptr16 + len16));
|
|
}
|
|
|
|
var fl = [];
|
|
var sl = [];
|
|
var hl = [];
|
|
|
|
var flValue;
|
|
var slValue;
|
|
var hlValue;
|
|
var tailValue;
|
|
|
|
function toBits(n, l, radix = 2) {
|
|
var s = n.toString(radix);
|
|
while (s.length < l) s = "0" + s;
|
|
return s;
|
|
}
|
|
|
|
function init() {
|
|
document.getElementById("albits").innerText = AL_BITS;
|
|
document.getElementById("flbits").innerText = FL_BITS;
|
|
document.getElementById("slbits").innerText = SL_BITS;
|
|
document.getElementById("overhead").innerText = OVERHEAD;
|
|
|
|
var fls = document.getElementById("fl");
|
|
var sls = document.getElementById("sl");
|
|
var hls = document.getElementById("hl");
|
|
|
|
for (let i = 0; i < FL_BITS; ++i) {
|
|
let el = document.createElement("span");
|
|
el.className = "fl";
|
|
el.innerText = i;
|
|
fls.appendChild(el);
|
|
fl[i] = el;
|
|
el.title = "< " + (1 << (8 + i));
|
|
el = document.createElement("span");
|
|
el.className = "sl";
|
|
el.innerHTML = '<span class="num">' + i + '</span>' + " " + toBits(0, HL_SIZE / FL_BITS);
|
|
sls.appendChild(el);
|
|
sl[i] = el;
|
|
}
|
|
for (let i = 0; i <= HL_SIZE; ++i) { // sic: last is tail
|
|
let el = document.createElement("span");
|
|
el.className = "hl";
|
|
el.innerHTML = '<span class="num">' + i + '</span> -';
|
|
hl[i] = el;
|
|
hls.appendChild(el);
|
|
}
|
|
}
|
|
|
|
function update() {
|
|
if (U32.buffer !== exports.memory.buffer) U32 = new Uint32Array(exports.memory.buffer);
|
|
var flv = U32[ROOT >> 2];
|
|
fl.forEach((el, i) => {
|
|
var isset = (flv >>> i) & 1;
|
|
el.className = isset ? "fl set" : "fl";
|
|
});
|
|
sl.forEach((el, i) => {
|
|
var map = U32[(ROOT + 4 + i * 4) >> 2];
|
|
el.className = map ? "sl set" : "sl";
|
|
el.innerHTML = '<span class="num">' + i + '</span>' + " " + toBits(map, (hl.length - 1) / fl.length);
|
|
});
|
|
hl.forEach((el, i) => {
|
|
var ptr = U32[(ROOT + 4 + fl.length * 4 + i * 4) >> 2];
|
|
el.className = ptr ? "hl set" : "hl";
|
|
el.innerHTML = '<span class="num">' + (i == hl.length - 1 ? "tail" : i) + '</span>' + " " + toBits(ptr, 6, 16);
|
|
});
|
|
}
|
|
|
|
function allocate(size) {
|
|
var ptr = exports.__alloc(size);
|
|
if (!ptr) {
|
|
alert("should not happen");
|
|
return;
|
|
}
|
|
var el = document.createElement("div");
|
|
el.className = "seg";
|
|
var es = document.createElement("input");
|
|
es.size = 10;
|
|
es.value = size;
|
|
el.appendChild(es);
|
|
var er = document.createElement("button");
|
|
er.innerText = "realloc";
|
|
er.onclick = function() {
|
|
ptr = exports.__realloc(ptr, es.value >>> 0);
|
|
update();
|
|
};
|
|
el.appendChild(er);
|
|
var ef = document.createElement("button");
|
|
ef.innerText = "free";
|
|
ef.className = "free";
|
|
el.appendChild(ef);
|
|
ef.onclick = function() {
|
|
exports.__free(ptr);
|
|
document.getElementById("segs").removeChild(el);
|
|
update();
|
|
};
|
|
document.getElementById("segs").appendChild(el);
|
|
}
|
|
</script>
|
|
|
|
<style>
|
|
/* General */
|
|
body { font-family: sans-serif; font-size: 0.8em; margin: 0; padding: 1em; }
|
|
h1 { font-size: 1em; margin: -1em -1em 0 -1em; padding: 1em; background: #7f7; }
|
|
h2 { background: #333; color: #ddd; font-size: 1em; padding: 0.5em; border-radius: 5px; }
|
|
input, button { border: 1px solid #999; border-radius: 0.2em; padding: 0.5em; }
|
|
button { cursor: pointer; background: #ddd; }
|
|
button:hover { background: #bbb; }
|
|
.clear { clear: both; }
|
|
/* Lists */
|
|
.fl, .sl, .hl, .seg { float: left; padding: 0.4em; margin: 0.2em; border: 1px solid #ddd; border-radius: 3px; }
|
|
.fl { min-width: 1.3em; text-align: center; }
|
|
.sl { min-width: 12em; }
|
|
.hl { min-width: 7em; font-size: 0.8em; }
|
|
.num { color: #fff; background: rgba(0, 0, 0, 0.3); padding: 0.4em; margin-left: -0.4em; border-radius: 0.2em; }
|
|
.set { background: #7f7; }
|
|
.seg { border-top: 0.3em solid #333; }
|
|
.seg button { margin-left: 0.5em; }
|
|
.sub { vertical-align: sub; font-size: 0.8em; }
|
|
.free { background: #f77; border-color: #c33; }
|
|
.free:hover { background: #c33; color: #fff; }
|
|
</style>
|
|
|
|
<h1>AssemblyScript Runtime Visualizer / TLSF</h1>
|
|
<p>
|
|
<strong>Notes:</strong>
|
|
<ul>
|
|
<li>It is expected that there is exactly one block on initialization. This is the remaining space (< 64K) within the last page after static data.</li>
|
|
<li>It is expected that if two adjacent blocks of size K are freed, the merged block doesn't go into the first level list for K*2 because its size is actually larger than that (K + OVERHEAD + K).</li>
|
|
<li>It is expected that if memory grows beyond 1GB, that even if all blocks are free'd there are at least two (or even three if the largest block is in the middle) remaining blocks, because a single block must not be larger than 1GB.</li>
|
|
<li>It is expected that after other operations have already been performed, being able to allocate 1GB can't be guaranteed anymore, even if there should be enough space left in absolute terms, if prior subdivision prevents it.</li>
|
|
<li>It is expected that the second level 0 in first level 0 isn't ever used due to alignment guarantees. Smallest block is 32 bytes (16 bytes overhead + 16 bytes payload if used, respectively linking information if free) in this implementation.</li>
|
|
</ul>
|
|
</p>
|
|
<p><strong>Implementation constants:</strong> <span id="albits">?</span> bits alignment, <span id="flbits">?</span> bits first level, <span id="slbits">?</span> bits second level, <span id="overhead">?</span> B overhead</p>
|
|
|
|
<h2>First level bitmap</h2>
|
|
<p>The first level map is a bitmap determining whether free blocks exist in at least one of its respective second levels. In this implementation, the first bit indicates whether a small block (< 256B) exists. Each bit doubles the size.</p>
|
|
<div id="fl"></div>
|
|
<div class="clear"></div>
|
|
|
|
<h2>Second level maps</h2>
|
|
<p>Second level maps subdivide each first level into multiple lists of subsizes. Each one works similar to the first level bitmap.</p>
|
|
<div id="sl"></div>
|
|
<div class="clear"></div>
|
|
|
|
<h2>Heads</h2>
|
|
<p>The heads of the actual free lists, one per second level per first level. Values here are pointers into memory. Last item is the address of the special zero-size "used" tail block, which is usually the end of WASM memory minus block overhead.</p>
|
|
<div id="hl"></div>
|
|
<div class="clear"></div>
|
|
|
|
<h2>Allocator</h2>
|
|
<p>Chose a size to allocate. Annotated list indexes depend on implementation constants but match those of this implementation.</p>
|
|
<p>
|
|
<input type="text" value="1" size="10" id="size" /> <button onclick="allocate(document.getElementById('size').value); update()">B</button>
|
|
</p>
|
|
<p>
|
|
Small blocks:
|
|
<button onclick="allocate(0); update()">0 B</button>
|
|
<button onclick="allocate(16); update()">16 B <span class="sub">fl=0 sl=1</span></button>
|
|
<button onclick="allocate(32); update()">32 B <span class="sub">fl=0 sl=2</span></button>
|
|
<button onclick="allocate(48); update()">48 B <span class="sub">fl=0 sl=3</span></button>
|
|
<button onclick="allocate(64); update()">64 B <span class="sub">fl=0 sl=4</span></button>
|
|
...
|
|
<button onclick="allocate(256-OVERHEAD); update()">256 B - δ <span class="sub">fl=0 sl=MSB</span></button>
|
|
(δ ≙ block overhead)
|
|
</p>
|
|
<p>
|
|
Common blocks:
|
|
<button onclick="allocate(256); update()">256 B <span class="sub">fl=1 sl=0</span></button>
|
|
<button onclick="allocate(512-OVERHEAD); update()">512 B - δ <span class="sub">fl=1 sl=MSB</span></button>
|
|
<button onclick="allocate(1024-OVERHEAD); update()">1 KB - δ <span class="sub">fl=2 sl=MSB</span></button>
|
|
<button onclick="allocate(2048-OVERHEAD); update()">2 KB - δ <span class="sub">fl=3 sl=MSB</span></button>
|
|
<button onclick="allocate(4096-OVERHEAD); update()">4 KB - δ <span class="sub">fl=4 sl=MSB</span></button>
|
|
(e.g. allocate 3, free middle, check second level)
|
|
</p>
|
|
<p>
|
|
Large blocks:
|
|
<button onclick="allocate(67108864-OVERHEAD); update()">64 MB - δ <span class="sub">fl=MSB-4 sl=MSB</span></button>
|
|
<button onclick="allocate(134217728-OVERHEAD); update()">128 MB - δ <span class="sub">fl=MSB-3 sl=MSB</span></button>
|
|
<button onclick="allocate(268435456-OVERHEAD); update()">256 MB - δ <span class="sub">fl=MSB-2 sl=MSB</span></button>
|
|
<button onclick="allocate(536870912-OVERHEAD); update()">512 MB - δ <span class="sub">fl=MSB-1 sl=MSB</span></button>
|
|
<button onclick="allocate(1073741824-OVERHEAD); update()">1 GB - δ <span class="sub">fl=MSB sl=MSB</span></button>
|
|
</p>
|
|
</p>
|
|
|
|
<h2>Segments</h2>
|
|
<p>Allocations performed above are tracked here so you can free them again. Note that TLSF alone does not keep track of used blocks (unless free'd and put in a free list again). It is expected that adjacent free blocks become merged automatically.</p>
|
|
<div id="segs"></div>
|
|
<div class="clear"></div>
|