DIRECTORY Allocator USING [BlockSizeIndex, bsiEscape, FNHeaderP, pagesPerQuantum, QuantumIndex, wordsPerQuantum], AllocatorOps USING [AddressToQuantumIndex, bsiToSize, quantumMap], Basics USING [LongNumber], Commander USING [CommandProc, Register], CommandTool USING [ArgumentVector, Failed, Parse], Convert USING [Error, IntFromRope], IO USING [PutFR1], PrincOps USING [PageCount, PageNumber], Process USING [Detach, Pause, SecondsToTicks], SafeStorage USING [nullType, ReclaimCollectibleObjects, WaitForCollectorDone, WaitForCollectorStart], VM USING [Free, PageCount, PageNumber], ZCT USING [EnterAndCallBack, zct]; ReclaimFreePages: PROGRAM IMPORTS AllocatorOps, Commander, CommandTool, Convert, IO, SafeStorage, Process, VM, ZCT = BEGIN BlockSizeIndex: TYPE = Allocator.BlockSizeIndex; bsiEscape: BlockSizeIndex = Allocator.bsiEscape; CARD: TYPE = LONG CARDINAL; QuantumIndex: TYPE = Allocator.QuantumIndex; FNHeaderP: TYPE = Allocator.FNHeaderP; wordsPerQuantum: CARDINAL = Allocator.wordsPerQuantum; StatsRecord: TYPE = RECORD [ autoForked: BOOL _ FALSE, helpWait: [0..60] _ 0, sortAll: INT _ 0, bsiSorts: INT _ 0, conflicts: INT _ 0, objects: INT _ 0, avgFreeLength: REAL _ 0.0, totalPagesFreed: INT _ 0 ]; checking: BOOL _ TRUE; helpEnabled: BOOL _ TRUE; stats: REF StatsRecord _ NEW[StatsRecord]; ForkHelper: PROC [seconds: [0..60] _ 10] = { Process.Detach[FORK HelperBase[seconds]]; }; HelperBase: PROC [seconds: [0..60] _ 10] = { stats.helpWait _ seconds; WHILE helpEnabled DO Process.Pause[Process.SecondsToTicks[stats.helpWait]]; [] _ SafeStorage.WaitForCollectorStart[]; [] _ SafeStorage.WaitForCollectorDone[]; [] _ SortAll[TRUE]; ENDLOOP; }; Reclaim: PROC [nGCs: NAT _ 1] RETURNS [pagesFreed: INT _ 0] = { THROUGH [0..nGCs) DO SafeStorage.ReclaimCollectibleObjects[]; ENDLOOP; RETURN [SortAll[TRUE]]; }; SortAll: PROC [prune: BOOL _ FALSE] RETURNS [pagesFreed: INT _ 0] = { stats.sortAll _ stats.sortAll + 1; FOR bsi: BlockSizeIndex IN BlockSizeIndex DO pagesFreed _ pagesFreed + SortBsi[bsi, prune]; ENDLOOP; }; SortBsi: PROC [bsi: BlockSizeIndex, prune: BOOL _ FALSE] RETURNS [pagesFreed: INT _ 0] = { inner1: PROC = { head _ CaptureFreeChain[bsi]; }; inner2: PROC = { newHead: FNHeaderP _ CaptureFreeChain[bsi]; IF newHead # NIL THEN { stats.conflicts _ stats.conflicts + 1; newHead _ SortFree[newHead]; head _ MergeFree[head, newHead]; }; ZCT.zct.bsiToFreeList[bsi] _ head; head _ newHead; }; head: FNHeaderP _ ZCT.zct.bsiToFreeList[bsi]; IF head # NIL THEN { stats.bsiSorts _ stats.bsiSorts + 1; ZCT.EnterAndCallBack[inner1]; IF checking THEN CheckValidity[head, bsi]; head _ SortFree[head]; IF prune THEN { IF checking THEN CheckValidity[head, bsi, TRUE]; [head, pagesFreed] _ PruneList[head]; }; CheckValidity[head, bsi, TRUE, TRUE]; ZCT.EnterAndCallBack[inner2]; stats.avgFreeLength _ stats.objects*1.0/stats.bsiSorts; }; stats.totalPagesFreed _ stats.totalPagesFreed + pagesFreed; }; CaptureFreeChain: PROC [bsi: BlockSizeIndex] RETURNS [head: FNHeaderP] = INLINE { head _ ZCT.zct.bsiToFreeList[bsi]; ZCT.zct.bsiToFreeList[bsi] _ NIL; }; CheckValidity: PROC [head: FNHeaderP, bsi: BlockSizeIndex, sorted: BOOL _ FALSE, count: BOOL _ FALSE] = { FOR each: FNHeaderP _ head, each.nextFree WHILE each # NIL DO next: FNHeaderP _ each.nextFree; IF next = head THEN ERROR; IF next = each THEN ERROR; IF each.fnh.blockSizeIndex # bsi THEN ERROR; IF each.fnh.type # SafeStorage.nullType THEN ERROR; IF count THEN stats.objects _ stats.objects + 1; IF sorted THEN IF next # NIL THEN IF LOOPHOLE[each, CARD] >= LOOPHOLE[next, CARD] THEN ERROR; ENDLOOP; }; PruneList: PROC [head: FNHeaderP] RETURNS [new: FNHeaderP _ NIL, pagesFreed: INT _ 0] = { free: FNHeaderP; [new, free] _ SplitList[head]; IF free # NIL THEN { each: FNHeaderP _ free; lastQX: QuantumIndex _ AddressToQuantumIndex[each]; IF NOT OnQuantumBoundary[each] THEN ERROR; WHILE each # NIL DO link: FNHeaderP _ each.nextFree; succ: FNHeaderP _ NextInAddress[each]; SELECT TRUE FROM OnQuantumBoundary[succ] => { succQX: QuantumIndex _ AddressToQuantumIndex[succ]; startPage: VM.PageNumber _ lastQX*Allocator.pagesPerQuantum; pages: VM.PageCount _ (succQX-lastQX)*Allocator.pagesPerQuantum; FOR qi: Allocator.QuantumIndex IN [lastQX..succQX) DO AllocatorOps.quantumMap[qi] _ FALSE; ENDLOOP; VM.Free[[startPage, pages]]; pagesFreed _ pagesFreed + pages; lastQX _ AddressToQuantumIndex[link]; IF NOT OnQuantumBoundary[link] THEN ERROR; }; ENDCASE; each _ link; ENDLOOP; }; }; SplitList: PROC [head: FNHeaderP] RETURNS [new, free: FNHeaderP] = { newTail: FNHeaderP _ new _ NIL; freeTail: FNHeaderP _ free _ NIL; each: FNHeaderP _ head; WHILE each # NIL DO IF OnQuantumBoundary[each] THEN { lag: FNHeaderP _ each; DO scan: FNHeaderP _ NextInAddress[lag]; link: FNHeaderP _ lag.nextFree; SELECT TRUE FROM OnQuantumBoundary[scan] => { IF freeTail = NIL THEN free _ each ELSE freeTail.nextFree _ each; freeTail _ lag; }; scan # link => { IF newTail = NIL THEN new _ each ELSE newTail.nextFree _ each; newTail _ lag; }; ENDCASE => { lag _ scan; LOOP; }; lag.nextFree _ NIL; each _ link; EXIT; ENDLOOP; } ELSE { next: FNHeaderP _ each.nextFree; each.nextFree _ NIL; IF newTail = NIL THEN new _ each ELSE newTail.nextFree _ each; newTail _ each; each _ next; }; ENDLOOP; }; NextInAddress: PROC [fnp: FNHeaderP] RETURNS [FNHeaderP] = INLINE { bsi: BlockSizeIndex _ fnp.fnh.blockSizeIndex; len: CARDINAL _ AllocatorOps.bsiToSize[bsi]; RETURN [fnp+len]; }; OnQuantumBoundary: PROC [head: FNHeaderP] RETURNS [BOOL] = INLINE { ln: Basics.LongNumber _ [lp[head]]; RETURN [(ln.lo MOD wordsPerQuantum) = 0]; }; AddressToQuantumIndex: PROC [fnp: FNHeaderP] RETURNS [QuantumIndex] = INLINE { RETURN [AllocatorOps.AddressToQuantumIndex[LOOPHOLE[fnp]]]; }; SortFree: PROC [list: FNHeaderP] RETURNS [FNHeaderP] = { innerSort: PROC [head: FNHeaderP, max: NAT] RETURNS [new, next: FNHeaderP] = { mid: FNHeaderP _ (new _ head).nextFree; next _ NIL; IF mid = NIL THEN RETURN; next _ mid.nextFree; IF LOOPHOLE[new, CARD] > LOOPHOLE[mid, CARD] THEN { IF new = mid THEN ERROR; mid.nextFree _ new; new _ mid; mid _ head; }; mid.nextFree _ NIL; IF next = NIL THEN RETURN; next _ (mid _ next).nextFree; IF next # NIL THEN { temp: FNHeaderP _ next; next _ temp.nextFree; temp.nextFree _ NIL; IF LOOPHOLE[mid, CARD] > LOOPHOLE[temp, CARD] THEN { IF temp = mid THEN ERROR; mid.nextFree _ NIL; temp.nextFree _ mid; mid _ temp} }; new _ MergeFree[new, mid]; IF next = NIL THEN RETURN; FOR depth: NAT IN [2..max) DO [mid, next] _ innerSort[next, depth]; new _ MergeFree[new, mid]; IF next = NIL THEN RETURN; ENDLOOP; }; IF list = NIL OR list.nextFree = NIL THEN RETURN [list]; RETURN [innerSort[list, 32].new]; }; MergeFree: PROC [x,y: FNHeaderP] RETURNS [new: FNHeaderP] = { tail: FNHeaderP _ NIL; IF x = NIL THEN RETURN [y]; IF y = NIL THEN RETURN [x]; new _ x; IF LOOPHOLE[x, CARD] > LOOPHOLE[y, CARD] THEN {new _ y; y _ x; x _ new}; DO DO tail _ x; x _ x.nextFree; IF x = NIL THEN { IF tail = y THEN ERROR; tail.nextFree _ y; RETURN}; IF LOOPHOLE[x, CARD] > LOOPHOLE[y, CARD] THEN EXIT; ENDLOOP; IF tail = y THEN ERROR; tail.nextFree _ y; DO tail _ y; y _ y.nextFree; IF y = NIL THEN { IF tail = x THEN ERROR; tail.nextFree _ x; RETURN}; IF LOOPHOLE[x, CARD] < LOOPHOLE[y, CARD] THEN EXIT; ENDLOOP; IF tail = x THEN ERROR; tail.nextFree _ x; ENDLOOP; }; AutoReclaim: Commander.CommandProc = TRUSTED { args: CommandTool.ArgumentVector _ CommandTool.Parse[cmd ! CommandTool.Failed => {msg _ errorMsg; GO TO failed}]; seconds: INT _ 64; IF args.argc >= 2 THEN seconds _ Convert.IntFromRope[args[1] ! Convert.Error => {msg _ "illegal number"; GO TO failed}]; SELECT seconds FROM < 0 => seconds _ 0; > 60 => seconds _ 60; ENDCASE; IF stats.autoForked THEN { stats.helpWait _ seconds; msg _ IO.PutFR1["wait reset to %g seconds", [integer[seconds]] ]; } ELSE { stats.autoForked _ TRUE; ForkHelper[seconds]; msg _ IO.PutFR1["forked with wait of %g seconds", [integer[seconds]] ]; }; EXITS failed => result _ $Failure; }; ForceReclaim: Commander.CommandProc = TRUSTED { args: CommandTool.ArgumentVector _ CommandTool.Parse[cmd ! CommandTool.Failed => {msg _ errorMsg; GO TO failed}]; times: INT _ 1; IF args.argc >= 2 THEN times _ Convert.IntFromRope[args[1] ! Convert.Error => {msg _ "illegal number"; GO TO failed}]; SELECT times FROM < 0 => times _ 0; > 100 => times _ 100; ENDCASE; msg _ IO.PutFR1["%g pages reclaimed", [integer[Reclaim[times]]]]; EXITS failed => result _ $Failure; }; Init: PROC = { Commander.Register[key: "AutoReclaimFreePages", proc: AutoReclaim, doc: "forks periodic free page reclaimer (optional argument of minimum seconds to wait)"]; Commander.Register[key: "ForceReclaimFreePages", proc: ForceReclaim, doc: "forces a free page reclamation (optional argument of # of GCs to perform first)"]; }; Init[]; END.  ReclaimFreePages.mesa Copyright c 1985, 1986 by Xerox Corporation. All rights reserved. Russ Atkinson (RRA) January 3, 1986 1:26:39 pm PST ReclaimFreePages.Reclaim[] reclaims freeable quanta from the small object free lists. A freeable quantum is one that only holds free objects. Executing Reclaim[] holds the allocator lock for only small amounts of time, although it must not be allowed to run concurrently with the TraceAndSweep collector. Types, constants, and global variables TRUE if a command was used to call ForkHelper the # of seconds to wait the # of times sortAll was called the # of bsi sorts we needed to perform the # of times that a bsi's free list was added to while we were sorting that bsi the total # of free objects left in lists after the sort (& prune) objects/bsiSorts the total # of pages freed by this module Forks a watching process that calls SortAll[TRUE] after a number of seconds followed by a GC. Causes a number of GCs, then reclaims all freeable quanta. SortAll sorts all of the free lists, optionally reclaiming the freeable quanta. SortBsi sorts the free list for the given block size, then optionally reclaims the freeable quanta. Capture the free list for this bsi. Alterations to this chain have been locked out. Install the sorted free list, merging with any newly freed entries. Alterations to this chain have been locked out. Supposedly few objects have been added to the free list since we last captured it. Sort the free list. Returns the free chain for the given block size. Assumes that the ZCT lock is held. Checks some validity constraints on the free list. We assume that the free list must contain only objects with the given block size. If the list is supposed to be sorted, then we check for the list being in increasing address order. Validity check on the resulting list Check for the list being sorted Takes a free list and prunes it of entries that are on freeable pages, also freeing the pages. Returns the pruned free list and the number of pages freed. We have scanned over a quantum's worth of free objects We must clear these bits or T&S goes down the tubes. Splits the given sorted list into two lists new: the list of free objects that exist in the same quantum as at least one allocated object free: the list of free objects that have no allocated objects in the same quantum We can scan forward within the quantum sequence for adjacent objects. We have found a quantum sequence full of free objects, so put all such objects onto the free chain. The next object in the chain is not adjacent, so splice everything so far onto the new chain. We are still scanning within the quantum sequence This object can be linked onto the new chain. Returns the address just beyond the end of the given free object. Returns TRUE iff the object is on a quantum boundary. Returns the quantum index for the given free object. Sorting functions Sorts a free list into increasing address order. Uses an O(N log N) algorithm that uses O(log N) auxilliary storage (in local frames). Adapted from ListImpl.Sort. First, grab the first pair of elements off the head of the list and make sure that they are sorted. If there is only one element, we return it immediately. If there are only two elements in the list first sort them, then return them. The first two nodes are in the wrong order, so swap them, leaving new pointing at the lesser of the two, and mid pointing at the greater. Second, grab the second pair of elements off the list. We have already checked, and there is at least one. There are two elements for the second pair, so we need to put them in order. The first two nodes are in the wrong order, so swap them. Third, merge the two lead lists. If this exhausts the original list, then return. Finally, build up the tree by progressively building small lists and merging them into larger lists. The size doubles at each level. We start with new holding onto a list of 4 elements, and next holding onto the remainder of the list. Merges two free lists (sorted in increasing address order). Adapted from ListImpl.Merge. Test for empty lists Start from y, which we do by swapping x and y. We first assume that we have just appended from x, but need to advance x to the next element and check for emptiness. Once this is done we try to stay within x as long as the predicate allows. We have just appended from y, so append to the list from y as long as reasonable. Initialization & commands [cmd: Commander.Handle] RETURNS [result: REF ANY _ NIL, msg: ROPE _ NIL] [cmd: Commander.Handle] RETURNS [result: REF ANY _ NIL, msg: ROPE _ NIL] Κ>˜codešœ™Kšœ Οmœ7™BK™2K™Kšœ²™²—˜šΟk ˜ Kšœ žœX˜gKšœ žœ0˜BKšœžœ˜Kšœ žœ˜(Kšœ žœ!˜2Kšœžœ˜#Kšžœžœ ˜Kšœ žœ˜'Kšœžœ!˜.Kšœ žœT˜eKšžœžœ˜'Kšžœžœ˜"——headšœž˜Kšžœ0žœžœž˜XKšœž˜K˜—šœ'™'K˜šœžœ˜0Kšœ0˜0—Kšžœžœžœžœ˜Kšœžœ˜,Kšœ žœ˜&Kšœžœ˜6K˜šœ žœžœ˜šœ žœžœ˜Kšžœ)™-—šœ˜Kšœ™—šœ žœ˜Kšœ!™!—šœ žœ˜Kšœ'™'—šœ žœ˜KšœQ™Q—šœ žœ˜KšœB™B—šœžœ˜Kšœ™—šœžœ˜Kšœ)™)—Kšœ˜K˜—Kšœ žœžœ˜Kšœ žœžœ˜Kšœžœžœ˜*K˜—šΟn œžœ˜,Kšœ,žœ*žœ™]Kšœžœ˜)K˜K˜—šŸ œžœ˜,Kšœ˜šžœ ž˜Kšœ6˜6Kšœ)˜)Kšœ(˜(Kšœ žœ˜Kšžœ˜—K˜K˜—š Ÿœžœžœžœžœ ˜?Kšœ:™:Kšžœ žœ*žœ˜FKšžœ žœ˜K˜K˜—š Ÿœžœ žœžœžœžœ ˜EKšœO™OKšœ"˜"šžœžœž˜,Kšœ.˜.Kšžœ˜—K˜K˜—š Ÿœžœžœžœžœžœ ˜ZKšœc™cšœžœ˜KšœT™TKšœ˜K˜—šœžœ˜K™ΘKšœ+˜+šžœ žœžœ˜Kšœ&˜&Kšœ˜Kšœ ˜ K˜—Kšžœ˜"Kšœ˜K˜—Kšœžœ˜-šžœžœžœ˜Kšœ™Kšœ$˜$Kšžœ˜Kšžœ žœ˜*Kšœ˜šžœžœ˜Kšžœ žœžœ˜0Kšœ%˜%K˜—Kšœžœžœ˜%Kšžœ˜Kšœ7˜7K˜—Kšœ;˜;K˜K˜—šŸœžœžœžœ˜QKšœT™TKšœžœ˜"Kšžœžœ˜!K˜K˜—š Ÿ œžœ0žœžœ žœžœ˜iKšœκ™κšžœ'žœžœž˜=Kšœ$™$Kšœ ˜ Kšžœ žœžœ˜Kšžœ žœžœ˜Kšžœžœžœ˜,Kšžœ&žœžœ˜3Kšžœžœ#˜0šžœž˜Kšœ™šžœžœž˜Kšžœžœžœžœžœžœžœ˜;——Kšžœ˜—K˜K˜—š Ÿ œžœžœžœžœ ˜YKšœ›™›Kšœ˜Kšœ˜šžœžœžœ˜Kšœ˜Kšœ3˜3Kšžœžœžœžœ˜*šžœžœž˜Kšœ ˜ Kšœ&˜&šžœžœž˜šœ˜Kšœ6™6Kšœ3˜3Kšœ žœ/˜Kšœ˜K˜—šžœ˜ Kšœ1™1Kšœ ˜ Kšžœ˜K˜——Kšœžœ˜Kšœ ˜ Kšžœ˜Kšžœ˜—K˜—šžœ˜Kšœ-™-Kšœ ˜ Kšœžœ˜Kšžœ žœžœ žœ˜>Kšœ˜Kšœ ˜ K˜——Kšžœ˜—K˜K˜—šŸ œžœžœžœ˜CKšœA™AKšœ-˜-Kšœžœ˜,Kšžœ ˜K˜K˜—š Ÿœžœžœžœžœ˜CKšœžœ)™5Kšœ#˜#Kšžœ žœ˜)K˜K˜—šŸœžœžœžœ˜NKšœ4™4Kšžœ%žœ˜;K˜K˜—™K˜šŸœžœžœ˜8Kšœ€™€K˜šœ žœžœžœ˜NK˜Kšœλ™λKšœ'˜'Kšœžœ˜ Kšžœžœžœžœ˜Kšœ˜š žœžœžœžœžœžœ˜3Kšœ‰™‰Kšžœ žœžœ˜Kšœ*˜*Kšœ˜—Kšœžœ˜Kšžœžœžœžœ˜K˜Kšœk™kKšœ˜šžœžœžœ˜KšœL™LKšœ˜Kšœ˜Kšœžœ˜š žœžœžœžœžœžœ˜4Kšœ9™9Kšžœ žœžœ˜Kšœžœ"˜4—K˜K˜—K™RKšœ˜Kšžœžœžœžœ˜K˜Kšœμ™μšžœžœžœ ž˜Kšœ%˜%Kšœ˜Kšžœžœžœžœ˜Kšžœ˜—K˜—Kš žœžœžœžœžœžœ˜8Kšžœ˜!K˜K˜—šŸ œžœžœ˜=JšœY™YJ™Jšœžœ˜J˜Jšœ™Jšžœžœžœžœ˜Jšžœžœžœžœ˜J˜J˜š žœžœžœžœžœžœ˜JJšœ.™.J˜—šž˜JšΟcœ2™Αšž˜Jšœ˜šžœžœžœ˜Jšžœ žœžœ˜Jšœžœ˜—Jšžœžœžœžœžœžœžœ˜3Jšžœ˜—Jšžœ žœžœ˜Jšœ˜J˜JšœQ™Qšž˜Jšœ˜šžœžœžœ˜Jšžœ žœžœ˜Jšœžœ˜—Jšžœžœžœžœžœžœžœ˜3Jšžœ˜—Jšžœ žœžœ˜Jšœ˜Jšžœ˜—J˜J˜——šœ™K™•StartOfExpansionL -- [cmd: Commander.Handle] RETURNS [result: REF ANY _ NIL, msg: ROPE _ NIL]šœ%žœ˜.KšΠckH™Hšœ8˜8Kšœ)žœžœ ˜8—Kšœ žœ˜šžœžœ&˜