*-----------------------------------------------------------
Title[DMesaAlloc.mc...March 11, 1983 1:33 PM...WSH];
*-----------------------------------------------------------
** version for PILOT only
*-----------------------------------------------------------
** allocating Quantized Node
rme[mAsz, rcv];
rme[hcode, residue];
rme[SzSize, entry];
rme[szfl, oiPrev0];
** freeing Quantized Node
rme[zoneIndex, entry];
rme[szflLo, onStack];
rme[szflHi, oiPrev1];
** allocating Prefixed Node
rme[pLengthLo, rcv];
rme[pLengthHi, residue];
rme[pSize, entry];
rme[pfnFirstLo, onStack];
rme[pfnFirstHi, oiPrev1];
rme[znpfn, oiPrev0];
** freeing Prefixed Node
rme[pfnPrevLo, rcv];
rme[pfnPrevHi, residue];
rme[pfnLo, entry];
rme[pfnHi, oiPrev0];
rme[pfnNextLo, onStack];
rme[pfnNextHi, oiPrev1];
top level;
*-----------------------------------------------------------
*
* GetReferentType[ref: REF ANY] RETURNS[Type]
*-----------------------------------------------------------
GetRefType: MiscTable[71];
Stack&-2, call[getRef]; * T has Stack-1
Stack-1← T, IFUNext0;
*-----------------------------------------------------------
*
* GetCanonicalReferentType[ref: REF ANY] RETURNS[Type]
*-----------------------------------------------------------
* GetCRefType: MiscTable[72],
* Stack&-2;
* call[getRef]; * T has Stack-1
** returns from call with pd← T test
* branch[.+2, alu#0], membase← gcStateBR;
* IFUNext0, Stack-1← T; * nullType
* knowrbase[gcTemp];
* gcTemp← T + T + 1;
* T← (fetch← MapTiTdOffset) + 1, call[loadLPtr];
* fetch← 0s, T← Stack, call[checkSize];
** MapTiTd is a SEQUENCE of LONG POINTERs
* T← (fetch← gcTemp) + 1, call[loadLPtr];
* fetch← eqvTypeSc;
* pd← Md;
* branch[.+2, alu#0];
* branch[agcTrap], T← 1C; * not canonicalized yet
* Stack-1← Md, IFUNext0;
*-----------------------------------------------------------
*
* GetCanonicalReferentType[ref: REF ANY] RETURNS[Type]
* canonical referenttype is now kept in (ref-1)↑
*-----------------------------------------------------------
KnowRBase[rTemp0];
GetCRefType: MiscTable[72],
Stack&-2;
membase← LPtr, pd← (Stack) OR T;
branch[.+2, alu#0], pd← Stack; * Stack is refLo
Stack← T, IFUNext0; * ref was NIL => type 0
rTemp0← (Stack) - 1, branch[.+2, alu#0];
T← T - 1; * T is refHi
BrLo← rTemp0;
BrHi← T;
fetch← 0s;
rTemp0← Md;
branch[.+2, R<0], T← (rTemp0) AND (37777C); * mask for type field
Stack← T, IFUNext0;
branch[cats], T← 10C; * referent on free list
*-----------------------------------------------------------
subroutine;
getRef:
rbase← rbase[rcv]; * T has Stack-1
pd← (Stack) OR (Q← T); * Q has hi part of Pointer
branch[.+2, alu#0], membase← GCStateBR, T← Stack&+1;
T← T - T, return; * Pointer was NIL => type=nullType=0
glink← Link;
top level;
gcTemp2← T; * save ptrLo
T← (fetch← MapPtrMzOffset) + 1, call[loadLPtr];
T← Q;
T← RCY[T, gctemp2, qiShift]; * quantumIndex
gctemp← T, fetch← 0s, call[checkSize];
** size was OK
** MapPtrMz is a SEQUENCE of one-word items
T← (gcTemp) + 1;
fetch← T, T← Q;
probe← pd← Md;
branch[subzone, alu<0], pd← gcTemp2;
*-----------------------------------------------------------
* RealZone => RETURN[(ptr-SIZE[Type])↑] where SIZE[Type]=1
* ptr is in T,,gcTemp2
*-----------------------------------------------------------
gcTemp2← (gcTemp2) - 1, branch[.+2, alu#0]; * pd← gcTemp2
T← T - 1; * decrement hi part of ptr if low part = 0
BrLo← gcTemp2;
BrHi← T, branch[endGRT];
*-----------------------------------------------------------
* SubZone => RETURN[GetSzType[mz.szi]]
* which is MapSziSz[SzSize lshift 1 + 1]↑
*-----------------------------------------------------------
subzone:
membase← gcStateBR, SzSize← Md;
SzSize← (SzSize) and (77777C); * mask off hi bit so size check will work
T← (fetch← MapSziSzOffset) + 1, call[loadLPtr];
fetch← 0s, T← SzSize, call[checkSize];
** MapSziSz is a SEQUENCE of LONG POINTERs
T← (SzSize) + (SzSize) + 1;
T← (fetch← T) + 1, call[loadLPtr];
endGRT: fetch← 0s;
link← gLink;
subroutine;
gcTemp← Md;
branch[.+2, R<0], T← (gcTemp) AND (37777C); * mask for type field
pd← T, return;
branch[cats], T← 10C; * referent on free list
top level;
*-----------------------------------------------------------
*
* AllocateQuantizedNode[zn:PRealZone, size: CARDINAL, t: Type]
* RETURNS[ptr: Pointer]
*-----------------------------------------------------------
AllocQNode: MiscTable[73], Stack&-3;
membase← ScratchBR;
T← zn.LOCK, call[checkMLock];
**----------- returns with gcTemp holding the Monitor lock
knowrbase[gcTemp];
branch[.+2, R even], gcTemp, T← zn.mAsz;
branch[agcTrap], T← 2C; * lock was set
** we have the zone
fetch← T, Stack&+2;
mAsz← (Md) + (Md);
mAsz← ((mAsz) + Md) lsh 1; * hi end of SubZoneArray
T← (Stack) AND Md; * forming hash code
hcode← T + T; * 2*T
hcode← ((hcode) + T) lsh 1; * 6*T --SubZoneRec is 6 words long
T← zn.pAsz;
T← (fetch← T) + 1, call[loadBaseReg]; * overwrite current BR
** arrive here with StkP pointing to size parameter
aqLoop:
T← (sz.vacant) + (hcode);
* ScratchBR has pointer to SubZoneArray
fetch← T, Stack&+1;
pd← Md;
branch[.+2, alu#0], T← (fetch← hcode) + 1; * fetch← ((sz.type)+(hcode))
T← 3C, Stack&+1, branch[agcTrap]; * vacant
pd← (Stack&-1) XOR Md;
branch[.+2, alu=0], szfl← (fetch← T) + 1; * fetch← ((sz.size)+(hcode))
pd← hcode, branch[aqNext]; * types didn't match
pd← (Stack) XOR Md;
branch[aqNext, alu#0], pd← hcode;
**------- we have a ptr to allocate, maybe
T← (fetch← szfl) + 1; * fetch← ((sz.fl)+(hcode))
Fetch← T, T← Q← Md;
pd← T OR (Md), membase← LPtr;
branch[.+2, alu#0], BrLo← T, gcTemp2← Md; * branch if FreeList#NIL
T← 3C, branch[agcTrap]; * vacant
BrHi← gcTemp2;
** LPtr (gcTemp2,,Q) contains the Pointer to allocate
T← (fetch← obj.FreeList1) - 1;
fetch← T, gcTemp← Md;
** store 0's on top of the old free list
T← (store← T) + 1, dbuf← 0C;
T← (store← T) - 1, dbuf← 0C;
** update sz.fl ** gcTemp(Hi),,Md(Lo) is new FreeList
membase← ScratchBR, Stack&-1;
T← (store← szfl) + 1, dbuf← Md;
store← T, dbuf← gcTemp;
T← gcTemp2;
Stack&-1← T;
Stack&+1← Q, IFUNext0;
aqNext: T← (Hcode) - (6C), branch[.+2, alu#0];
T← mAsz;
hcode← T, b← Md, branch[aqLoop];
*-----------------------------------------------------------
*
* AllocatePrefixedNode[zn:PRealZone, size: CARDINAL, t: Type]
* RETURNS[ptr: Pointer]
*-----------------------------------------------------------
AllocPNode: MiscTable[74], Stack&-3;
membase← ScratchBR;
T← zn.LOCK, call[checkMLock];
**----------- returns with gcTemp holding the Monitor lock
branch[.+2, R even], gcTemp, T← MinBlockSize;
branch[agcTrap], T← 2C; * lock was set
Stack&+2;
branch[apn0, R EVEN], pd← (Stack) - T;
Stack← (Stack) + 1;
branch[.+3, alu#0];
Stack← (Stack) - 1;
branch[agcTrap], T← 5C; * size too big
pd← (Stack) - T;
apn0: branch[.+2, carry], T← (Stack&+1) + (pNodeOverhead);
pSize← FreeNodeSize, branch[doneSize];
branch[.+2, carry'], pSize← T;
branch[agcTrap], T← 5C; * size too big
doneSize: * pSize has node size, ScratchBR has zn
T← znpfn← zn.pfn;
T← (fetch← T) + 1;
gcTemp← 100C;
Cnt← gcTemp;
fetch← T, pfnFirstLo← Md;
membase← LPtr, T← Md;
BrLo← pfnFirstLo;
pfnFirstHi← BrHi← T;
* LPtr has PFreeNode
apLoop:
T← (fetch← pnode.sizeHi) - 1;
pLengthHi← Md, fetch← T;
apL2: pLengthHi← (pLengthHi) AND (377C), branch[.+2, R <0];
branch[cats], T← 5C; * node on free list is not free
pd← pLengthHi, T← Md;
branch[sizeOK, alu#0], T← T - (pSize); * branch if pLengthHi # 0
branch[.+2, carry']; * skip if pSize > pLengthLo
pLengthLo← T, branch[szOK1];
** this node is too small, check interrupts, count and then try another
** undate rover pointer in zone
T← (fetch← pnode.pfnNextHi) - 1;
pLengthHi← Md, fetch← T;
membase← ScratchBR, T← (znpfn) + 1;
T← (store← T) - 1, dbuf← pLengthHi;
store← T, dbuf← Md, T← Md, branch[.+2, Cnt#0&-1];
branch[agcTrap], T← 4C; * looked at 20B nodes
** check if have gone all the way around a short list
branch[.+2, ReSchedule'], membase← LPtr;
branch[MesaReschedTrap]; * priority interrupt
pd← (BrLo← T) XOR (pfnFirstLo);
branch[apLoop, alu#0], T← BrHi← pLengthHi;
pd← T xor (pfnFirstHi);
branch[.+2, alu=0], T← (fetch← pnode.sizeHi) - 1;
branch[apL2], pLengthHi← Md, fetch← T;
branch[agcTrap], T← 3C; * all the way around
*-----------------------------------------------------------
sizeOK:
pLengthLo← T, branch[.+2, carry'];
branch[splitBlock]; * know plengthHi > 0 => split
pLengthHi← (pLengthHi) - 1; * borrow
branch[splitblock, alu>0];
** pLengthHi,,pLengthLo has length of leftover node
szOK1:
pd← (pLengthLo) - (4MinBlockSize);
branch[.+2, carry'];
branch[splitBlock]; * need to split the block
* take the whole block off the free list - don't need to change the size
** need to access both next and previous block in linked list before
** taking this node off the chain (page faults)
T← (fetch← pnode.pfnNext) + 1;
T← Md, fetch← T;
membase← BBSrcBR; * use BitBlt's 2 base registers
pfnFirstLo← BrLo← T, T← Md;
pfnFirstHi← BrHi← T;
T← (fetch← pnode.pfnPrev) + 1;
T← Md, fetch← T;
membase← LPtr, b← Md;
T← (fetch← pnode.pfnPrev) + 1;
T← Md, fetch← T;
membase← BBDstBR;
gcTemp← BrLo← T, T← Md;
gcTemp2← BrHi← T;
T← (fetch← pnode.pfnNext) + 1;
b← Md;
T← (store← T) - 1, dbuf← pfnFirstHi;
store← T, dbuf← pfnFirstLo, flipmembase;
T← (store← pnode.pfnPrev) + 1, dbuf← gcTemp;
store← T, dbuf← gcTemp2;
*-------- update zn.pfn
membase← ScratchBR, T← pfnFirstLo;
T← (store← znpfn) + 1, dbuf← T;
store← T, dbuf← pfnFirstHi;
*-------- mark the node as inuse by storing the type into pnode.SizeHi field
membase← LPtr;
store← pnode.type, dbuf← Stack&-3;
endPAlloc:
*-------- clear the freeList pointers (can't cause page fault)
T← A0;
store← pnode.pfnPrevHi, dbuf← T;
store← pnode.pfnPrev, dbuf← T;
store← pnode.pfnNextHi, dbuf← T;
store← pnode.ref, dbuf← T; * same as pnode.pfnNext
gcTemp← Md, T← 377C; ** get memory in good state
Stack&+1← VaLo;
Stack← T AND (VaHi), IFUNext0;
*--------- split the block - pLengthHi,,pLengthLo has length of leftover node
* need to access the part of pnode that will be returned as the new node
** this is to take care of page faults
** LPtr has the node to allocate from, scratchBR is not needed
splitBlock:
fetch← pnode.SizeLo;
T← VaLo;
Q← T;
T← VaHi;
fetch← pnode.ref; * page fault insurance
gcTemp← (pLengthLo) + Q;
T← T + (pLengthHi), XORSavedCarry;
pfnFirstHi← T AND (377C);
membase← ScratchBR;
BrLo← gcTemp;
BrHi← pfnFirstHi;
T← (store← pnode.sizeLo) + 1, dbuf← pSize;
store← T, dbuf← Stack&-3; * store type
* must change size of original node
membase← LPtr;
store← pnode.sizeLo, dbuf← pLengthLo;
pLengthHi← (pLengthHi) OR (100000C); * mark as free
store← pnode.sizeHi, dbuf← pLengthHi;
membase← ScratchBR, branch[endPAlloc];
*-----------------------------------------------------------
*
* DoFreeObject[ptr: Pointer]
*-----------------------------------------------------------
FreeObject: MiscTable[75], Stack&-2;
call[getRef];
knowrbase[gcTemp]; * membase unknown, probe has MapQMz entry
branch[freePN, R>=0], probe;
** subzone => quantized node to be freed, and membase is LPtr
* LPtr points to the subZone, ptr is in Stack-1,,Stack
** need to get the zone and check the monitor lock (sigh)
freeQN: fetch← sz.zi;
zoneIndex← Md, membase← gcstateBR;
T← (fetch← MapZiZnOffset) + 1;
T← Md, fetch← T;
membase← BBSrcBR, zoneIndex← (zoneIndex) + (zoneIndex) + 1;
BrLo← T, T← Md;
BrHi← T;
T← (fetch← zoneIndex) + 1, call[loadBaseReg];
freeQN1: fetch← zn.MLOCK;
gcTemp← Md;
branch[.+2, R even], gcTemp, membase← LPtr;
branch[agcTrap], T← 2C; * lock was set, so take trap
* LOOPHOLE[ptr, FreeList]↑← sz.fl;
* sz.fl← ptr;
T← (fetch← sz.fl) + 1;
szflLo← Md, fetch← T;
szflHi← Md, membase← ScratchBR;
BrHi← Stack&-1;
BrLo← Stack;
T← (fetch← obj.FreeList) + 1;
T← (store← T) - 1, dbuf← szflHi;
store← T, dbuf← szflLo;
membase← LPtr;
T← (store← sz.fl) + 1, dbuf← Stack&+1;
store← T, dbuf← Stack&-2, IFUNext0CF;
* probe has zn.zi
* pfn, pfnPrev: PFreeNode;
* pfnNext: PFreeNode← pfnPrev.pfnNext;
* pfn.body← free[pfnPrev: pfnPrev, pfnNext: pfnNext];
* pfnNext.pfnPrev← pfn;
* pfnPrev.pfnNext← pfn
freePN: membase← GCstateBR, Stack&-1;
T← (fetch← MapZiZnOffset) + 1, call[loadLPtr];
fetch← 0s, T← probe, call[checkSize];
T← (probe) + (probe) + 1;
T← (fetch← T) + 1, call[loadBaseReg];
* LPtr now holds the zone, StkP points to ptrLo
T← pNodeOverhead; * node+type overhead
freePN1: T← (Stack&+1) - T; * need to subtract overhead
pfnLo← pd← T, branch[.+2, carry];
T← (Stack) - 1, branch[.+2];
T← Stack;
pfnHi← T;
* StkP points to ptrHi, membase is LPtr
fetch← zn.MLock, Stack&-2; * don't need StkP anymore
gcTemp← Md;
branch[.+2, R even], gcTemp, T← zn.fnd;
branch[agcTrap], T← 2C; * zone is locked
* must reference pfnPrev and pfnNext before any stores
* can do stores into pfn, since its neither free nor used
DummyRef← T, b← Md;
T← VaLo;
BrLo← T;
T← VaHi;
T← T AND (377C);
BrHi← T;
* LPtr holds pfnPrev
T← (fetch← pnode.pfnNext) + 1;
pfnNextLo← Md, fetch← T;
pfnNextHi← Md, membase← BBDstBR;
BrLo← pfnNextLo;
BrHi← pfnNextHi;
T← (fetch← pnode.pfnPrev) + 1;
pfnPrevLo← Md, fetch← T;
pfnPrevHi← Md, membase← scratchBR;
** fix up the new free node to be inserted
BrHi← pfnHi;
BrLo← pfnLo;
fetch← pnode.sizeHi;
pd← Md;
branch[.+2, alu>=0], T← 6C;
branch[cats]; * node already on free list
T← (store← pnode.pfnNext) + 1, dbuf← pfnNextLo;
store← T, dbuf← pfnNextHi;
T← (store← pnode.pfnPrev) + 1, dbuf← pfnPrevLo;
store← T, dbuf← pfnPrevHi;
T← 100000C; * mark node as free
store← pnode.sizeHi, dbuf← T;
membase← BBDstBR;
T← (store← pnode.pfnPrev) + 1, dbuf← pfnLo;
store← T, dbuf← pfnHi;
membase← LPtr;
T← (store← pnode.pfnNext) + 1, dbuf← pfnLo;
store← T, dbuf← pfnHi, IFUNext0CF;
*** debugging
* membase← scratchBR;
* fetch← pnode.sizeHi;
* gcTemp← Md;
* branch[.+2, r ODD], gcTemp; * check if inserted node is marked free
* branch[cats];
* IFUNext0;
*** debugging
*-----------------------------------------------------------
*
* FreeQuantizedNode[ptr: Pointer, zn:PRealZone]
*-----------------------------------------------------------
FreeQNode: MiscTable[76], Stack&-3;
call[getRef], T← Stack&-1;
knowrbase[gcTemp]; * membase unknown
Stack&+2, membase← BBSrcBR;
BrHi← Stack&-1;
BrLo← Stack&-1, branch[freeQN1];
*-----------------------------------------------------------
*
* FreePrefixedNode[ptr: Pointer, zn:PRealZone]
*-----------------------------------------------------------
FreePNode: MiscTable[77], Stack&-3;
call[getRef], T← Stack&-1;
knowrbase[gcTemp]; * membase unknown
Stack&+2, membase← LPtr;
BrHi← Stack&-1;
BrLo← Stack&-2; *Lptr holds zone, StkP -> ptrLo
T← pNodeOverhead, branch[freePN1]; * node overhead
*-----------------------------------------------------------
subroutine;
* T← (fetch← xx) + 1, call[loadLPtr]
*-----------------------------------------------------------
loadLPtr:
T← Md, fetch← T;
membase← LPtr;
llpt1: BrLo← T, T← Md;
BrHi← T, return;
*-----------------------------------------------------------
* T← (fetch← xx) + 1, call[loadBaseReg]
*-----------------------------------------------------------
loadBaseReg:
T← Md, fetch← T, branch[llpt1];
*-----------------------------------------------------------
*
* fetch← 0s, T← xx, call[checkSize]
*-----------------------------------------------------------
checkSize:
pd← T - Md;
branch[.+2, alu<0];
T← 7C, branch[cats]; * bounds fault
return;
*-----------------------------------------------------------
* T has offset of word in zone/record to fetch
* ptr (zone/record) is on top of stack
* sets rbase to Allocator/Collector region
*
* membase← xx, T← yy, call[checkMLock]
*-----------------------------------------------------------
checkMLock:
BrHi← Stack&-1;
BrLo← Stack;
fetch← T;
rbase← rbase[rcv];
gcTemp← Md, return;
*-----------------------------------------------------------
top level;
agcTrap: rbase← rbase[RTemp0], global;
TrapParam← T, branch[MiscOpCodeTrap];