tcms.ts

import{BLOCK,BLOCK_OVERHEAD,OBJECT_OVERHEAD,OBJECT_MAXSIZE,TOTAL_OVERHEAD,DEBUG,TRACE,RTRACE}from"./common";
import{onvisit,oncollect}from"./rtrace";
import{E_ALLOCATION_TOO_LARGE,E_ALREADY_PINNED,E_NOT_PINNED}from"../util/error";

// === TCMS: A Two-Color Mark & Sweep garbage collector ===

// ╒═════════════╤══════════════ Colors ═══════════════════════════╕
// │ Color │ Meaning │
// ├─────────────┼─────────────────────────────────────────────────┤
// │ WHITE* │ Unreachable │
// │ BLACK* │ Reachable │
// │ TRANSPARENT │ Manually pinned (always reachable) │
// └─────────────┴─────────────────────────────────────────────────┘
// * flipped between cycles

// @ts-ignore: decorator
@lazyletwhite=0;
// @ts-ignore: decorator
@inlineconsttransparent=3;
// @ts-ignore: decorator
@inlineconstCOLOR_MASK=3;

/** Size in memory of all objects currently managed by the GC. */
// @ts-ignore: decorator
@lazylettotal: usize=0;

// @ts-ignore: decorator
@lazyletfromSpace=initLazy(changetype<Object>(memory.data(offsetof<Object>())));
// @ts-ignore: decorator
@lazylettoSpace=initLazy(changetype<Object>(memory.data(offsetof<Object>())));
// @ts-ignore: decorator
@lazyletpinSpace=initLazy(changetype<Object>(memory.data(offsetof<Object>())));

functioninitLazy(space: Object): Object{
space.nextWithColor=changetype<usize>(space);
space.prev=space;
returnspace;
}

/** Visit cookie indicating scanning of an object. */
// @ts-ignore: decorator
@inlineconstVISIT_SCAN=0;

// ╒═══════════════ Managed object layout (32-bit) ════════════════╕
// 3 2 1
// 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 bits
// ├─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┤
// │ Memory manager block │
// ╞═══════════════════════════════════════════════════════════╤═══╡
// │ next │ C │ = nextWithColor
// ├───────────────────────────────────────────────────────────┴───┤
// │ prev │
// ├───────────────────────────────────────────────────────────────┤
// │ rtId │
// ├───────────────────────────────────────────────────────────────┤
// │ rtSize │
// ╞>ptr═══════════════════════════════════════════════════════════╡
// │ ... │
// C: color

/** Represents a managed object in memory, consisting of a header followed by the object's data. */
@unmanagedclassObjectextendsBLOCK{
/** Pointer to the next object with color flags stored in the alignment bits. */
nextWithColor: usize;// *u32
/** Pointer to the previous object. */
prev: Object;// *u32
/** Runtime id. */
rtId: u32;
/** Runtime size. */
rtSize: u32;

/** Gets the pointer to the next object. */
getnext(): Object{
returnchangetype<Object>(this.nextWithColor&~COLOR_MASK);
}

/** Sets the pointer to the next object. */
setnext(obj: Object){
this.nextWithColor=changetype<usize>(obj)|(this.nextWithColor&COLOR_MASK);
}

/** Gets this object's color. */
getcolor(): i32{
returni32(this.nextWithColor&COLOR_MASK);
}

/** Sets this object's color. */
setcolor(color: i32){
this.nextWithColor=(this.nextWithColor&~COLOR_MASK)|color;
}

/** Gets the size of this object in memory. */
getsize(): usize{
returnBLOCK_OVERHEAD+(this.mmInfo&~3);
}

/** Unlinks this object from its list. */
unlink(): void{
letnext=this.next;
if(next==null){
if(DEBUG)assert(this.prev==null&&changetype<usize>(this)<__heap_base);
return;// static data not yet linked
}
letprev=this.prev;
if(DEBUG)assert(prev);
next.prev=prev;
prev.next=next;
}

/** Links this object to the specified list, with the given color. */
linkTo(list: Object,withColor: i32): void{
letprev=list.prev;
this.nextWithColor=changetype<usize>(list)|withColor;
this.prev=prev;
prev.next=this;
list.prev=this;
}
}

// Garbage collector interface

// @ts-ignore: decorator
@global @unsafe
exportfunction__new(size: usize,id: i32): usize{
if(size>OBJECT_MAXSIZE)thrownewError(E_ALLOCATION_TOO_LARGE);
letobj=changetype<Object>(__alloc(OBJECT_OVERHEAD+size)-BLOCK_OVERHEAD);
obj.rtId=id;
obj.rtSize=<u32>size;
obj.linkTo(fromSpace,white);
total+=obj.size;
returnchangetype<usize>(obj)+TOTAL_OVERHEAD;
}

// @ts-ignore: decorator
@global @unsafe
exportfunction__renew(oldPtr: usize,size: usize): usize{
letoldObj=changetype<Object>(oldPtr-TOTAL_OVERHEAD);
if(oldPtr<__heap_base){// move to heap for simplicity
letnewPtr=__new(size,oldObj.rtId);
memory.copy(newPtr,oldPtr,min(size,oldObj.rtSize));
returnnewPtr;
}
if(size>OBJECT_MAXSIZE)thrownewError(E_ALLOCATION_TOO_LARGE);
total-=oldObj.size;
letnewPtr=__realloc(oldPtr-OBJECT_OVERHEAD,OBJECT_OVERHEAD+size)+OBJECT_OVERHEAD;
letnewObj=changetype<Object>(newPtr-TOTAL_OVERHEAD);
newObj.rtSize=<u32>size;

// Replace with new object
newObj.next.prev=newObj;
newObj.prev.next=newObj;

total+=newObj.size;
returnnewPtr;
}

// @ts-ignore: decorator
@global @unsafe
exportfunction__link(parentPtr: usize,childPtr: usize,expectMultiple: bool): void{
// nop
}

// @ts-ignore: decorator
@global @unsafe
exportfunction__visit(ptr: usize,cookie: i32): void{
if(!ptr)return;
letobj=changetype<Object>(ptr-TOTAL_OVERHEAD);
if(RTRACE)if(!onvisit(obj))return;
if(obj.color==white){
obj.unlink();// from fromSpace
obj.linkTo(toSpace,i32(!white));
}
}

// @ts-ignore: decorator
@global @unsafe
exportfunction__pin(ptr: usize): usize{
if(ptr){
letobj=changetype<Object>(ptr-TOTAL_OVERHEAD);
if(obj.color==transparent){
thrownewError(E_ALREADY_PINNED);
}
obj.unlink();// from fromSpace
obj.linkTo(pinSpace,transparent);
}
returnptr;
}

// @ts-ignore: decorator
@global @unsafe
exportfunction__unpin(ptr: usize): void{
if(!ptr)return;
letobj=changetype<Object>(ptr-TOTAL_OVERHEAD);
if(obj.color!=transparent){
thrownewError(E_NOT_PINNED);
}
obj.unlink();// from pinSpace
obj.linkTo(fromSpace,white);
}

// @ts-ignore: decorator
@global @unsafe
exportfunction__collect(): void{
if(TRACE)trace("GC at",1,total);

// Mark roots (add to toSpace)
__visit_globals(VISIT_SCAN);

// Mark direct members of pinned objects (add to toSpace)
letpn=pinSpace;
letiter=pn.next;
while(iter!=pn){
if(DEBUG)assert(iter.color==transparent);
__visit_members(changetype<usize>(iter)+TOTAL_OVERHEAD,VISIT_SCAN);
iter=iter.next;
}

// Mark what's reachable from toSpace
letblack=i32(!white);
letto=toSpace;
iter=to.next;
while(iter!=to){
if(DEBUG)assert(iter.color==black);
__visit_members(changetype<usize>(iter)+TOTAL_OVERHEAD,VISIT_SCAN);
iter=iter.next;
}

// Sweep what's left in fromSpace
letfrom=fromSpace;
iter=from.next;
while(iter!=from){
if(DEBUG)assert(iter.color==white);
letnewNext=iter.next;
if(changetype<usize>(iter)<__heap_base){
iter.nextWithColor=0;// may become linked again
iter.prev=changetype<Object>(0);
}else{
total-=iter.size;
if(isDefined(__finalize))__finalize(changetype<usize>(iter)+TOTAL_OVERHEAD);
__free(changetype<usize>(iter)+BLOCK_OVERHEAD);
}
iter=newNext;
}
from.nextWithColor=changetype<usize>(from);
from.prev=from;

// Flip spaces and colors
fromSpace=to;
toSpace=from;
white=black;

if(TRACE)trace("GC done at",1,total);
if(RTRACE)oncollect(total);
}