AllocImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Sweet, 19-Aug-81 12:15:12
Satterthwaite, June 10, 1986 3:02:12 pm PDT
Maxwell, August 11, 1983 11:29 am
Rovner, October 12, 1983 10:52 am
Russ Atkinson (RRA) February 19, 1985 6:05:00 pm PST
DIRECTORY
Alloc: TYPE USING [Base, BaseSeq, Index, Notifier, OrderedIndex, Selector, TableInfo, addrSpan],
PrincOpsUtils: TYPE USING [LongCopy],
VM: TYPE USING [AddressForPageNumber, Allocate, Free, Interval, nullInterval, wordsPerPage];
AllocImpl: MONITOR LOCKS h.LOCK USING h: Handle
IMPORTS PrincOpsUtils, VM
EXPORTS Alloc = {
OPEN Alloc;
types
Handle: TYPE = REF InstanceData;
InstanceData: PUBLIC TYPE = MONITORED RECORD[
nTables: CARDINAL,
notifiers: NotifyChainHandle ← NIL,
bases: REF BaseSeq,  -- tag codes subtracted
offsets: REF OffsetSeq,  -- (shifted) tag codes
vm: REF SpaceSeq,
chunks: REF ChunkSeq,
top: REF SizeSeq,  -- tag codes added
limit: REF BoundSeq,  -- tag codes added
vmPages: REF SizeSeq,
maxPages: REF PageSeq];
OffsetSeq: TYPE = RECORD[SEQUENCE length: NAT OF CARD];
SizeSeq: TYPE = RECORD[SEQUENCE length: NAT OF CARD];
Bound: TYPE = CARD;
BoundSeq: TYPE = RECORD[SEQUENCE length: NAT OF Bound];
PageCount: TYPE = CARD;
PageSeq: TYPE = RECORD[SEQUENCE length: NAT OF PageCount];
SpaceSeq: TYPE = RECORD[SEQUENCE length: NAT OF VM.Interval];
ChunkSeq: TYPE = RECORD[SEQUENCE length: NAT OF ChunkHandle];
signals
Failure: PUBLIC ERROR[h: Handle, table: Selector] = CODE;
Overflow: PUBLIC SIGNAL[h: Handle, table: Selector] RETURNS[extra: CARD] = CODE;
stack allocation from subzones
Words: PUBLIC ENTRY PROC[h: Handle, table: Selector, size: CARDINAL]
RETURNS[x: OrderedIndex] = {
ENABLE UNWIND => {NULL};
RETURN[WordsInternal[h, table, size ! Failure => {GO TO Fail}]]
EXITS
Fail => {RETURN WITH ERROR Failure[h, table]}
};
WordsInternal: INTERNAL PROC[h: Handle, table: Selector, size: CARDINAL]
RETURNS[OrderedIndex] = {
index: CARD = h.top[table];
newTop: Bound = index + size;
IF newTop > h.limit[table] THEN {
IF newTop-h.offsets[table] > UnitsForPages[h.maxPages[table]] THEN
ERROR Failure[h, table];
GrowTable[h, table, newTop]};
h.top[table] ← newTop;
RETURN[OrderedIndex.FIRST + index]};
linked list allocation
Chunk: TYPE = MACHINE DEPENDENT RECORD[
free(0: 0..0): BOOL,
size(0: 1..15): NAT,
fLink(1): CIndex,
bLink(3): CIndex];
CIndex: TYPE = Base RELATIVE LONG POINTER TO Chunk; -- tag codes added
ChunkHandle: TYPE = REF ChunkObject;
ChunkObject: TYPE = RECORD[
chunkRover: CIndex,
nullChunkIndex: CIndex,
firstSmall: NAT,
smallLists: SEQUENCE nSmall: NAT OF CIndex];
GetChunk: PUBLIC ENTRY PROC[h: Handle, size: CARDINAL, table: Selector]
RETURNS[Index] = {
ENABLE UNWIND => {NULL};
ch: ChunkHandle = h.chunks[table];
cb: Base = h.bases[table];
q: CIndex;
IF ch = NIL THEN RETURN WITH ERROR Failure[h, table];
size ← MAX[size, Chunk.SIZE];
BEGIN
IF size IN [ch.firstSmall..NAT[ch.firstSmall+ch.nSmall]) THEN {
offset: CARDINAL = size - ch.firstSmall;
q ← ch.smallLists[offset];
IF q # ch.nullChunkIndex THEN {ch.smallLists[offset] ← cb[q].fLink; GO TO found}};
q ← GetRoverChunk[cb, h.top[table], ch, size];
IF q # ch.nullChunkIndex THEN GO TO found;
q ← WordsInternal[h: h, table: table, size: size ! Failure => {GO TO noneAtEnd}];
EXITS
noneAtEnd => {
none the right size, no space at the end, and no big ones to split
FOR s: NAT IN [ch.firstSmall.. ch.firstSmall+ch.nSmall) DO
offset: NAT = s - ch.firstSmall;
r: CIndex ← ch.smallLists[offset];
WHILE r # ch.nullChunkIndex DO
next: CIndex = cb[r].fLink;
FreeRoverChunk[cb, ch, r, s];
r ← next;
ENDLOOP;
ch.smallLists[offset] ← ch.nullChunkIndex;
ENDLOOP;
now all possible merges of free nodes can happen
q ← GetRoverChunk[cb, h.top[table], ch, size];
IF q = ch.nullChunkIndex THEN RETURN WITH ERROR Failure[h, table]};
found => NULL;
END;
h.bases[table][q].free ← FALSE;
RETURN[q]};
GetRoverChunk: INTERNAL PROC[
cb: Base, top: CARDINAL, ch: ChunkHandle, size: CARDINAL]
RETURNS[Index] = {
p, q, next: CIndex;
nodeSize: INTEGER;
n: INTEGER;
BEGIN
IF (p ← ch.chunkRover) = ch.nullChunkIndex THEN GO TO notFound;
search for a chunk to allocate
DO
nodeSize ← cb[p].size;
WHILE (next ← p + nodeSize) - CIndex.FIRST # top AND cb[next].free DO
cb[cb[next].bLink].fLink ← cb[next].fLink;
cb[cb[next].fLink].bLink ← cb[next].bLink;
cb[p].size ← nodeSize ← nodeSize + cb[next].size;
ch.chunkRover ← p; -- in case next = chunkRover
ENDLOOP;
SELECT (n ← nodeSize-size) FROM
= 0 => {
IF cb[p].fLink = p THEN ch.chunkRover ← ch.nullChunkIndex
ELSE {
ch.chunkRover ← cb[cb[p].bLink].fLink ← cb[p].fLink;
cb[cb[p].fLink].bLink ← cb[p].bLink};
q ← p;
GO TO found};
>= Chunk.SIZE => {
cb[p].size ← n; ch.chunkRover ← p; q ← p + n; GO TO found};
ENDCASE;
IF (p ← cb[p].fLink) = ch.chunkRover THEN GO TO notFound;
ENDLOOP;
EXITS
found => NULL;
notFound => q ← ch.nullChunkIndex;
END;
RETURN[q]};
FreeChunk: PUBLIC ENTRY PROC[h: Handle, index: Index, size: CARDINAL, table: Selector] = {
ENABLE UNWIND => {NULL};
ch: ChunkHandle = h.chunks[table];
cb: Base = h.bases[table];
p: CIndex = LOOPHOLE[index];
IF ch = NIL THEN RETURN WITH ERROR Failure[h, table];
cb[p].size ← size ← MAX[size, Chunk.SIZE];
IF size IN [ch.firstSmall..NAT[ch.firstSmall+ch.nSmall]) THEN {
offset: NAT = size - ch.firstSmall;
cb[p].fLink ← ch.smallLists[offset];
ch.smallLists[offset] ← p;
don't set cb[p].free ← TRUE; to avoid coalescing nodes
cb[p].bLink ← ch.nullChunkIndex} -- note, only singly linked
ELSE FreeRoverChunk[cb, ch, index, size]};
FreeRoverChunk: INTERNAL PROC[
cb: Base, ch: ChunkHandle, index: Index, size: CARDINAL] = {
p: CIndex = LOOPHOLE[index];
cb[p].size ← size ← MAX[size, Chunk.SIZE];
IF ch.chunkRover = ch.nullChunkIndex THEN
ch.chunkRover ← cb[p].fLink ← cb[p].bLink ← p
ELSE {
rover: CIndex = ch.chunkRover;
cb[p].fLink ← cb[rover].fLink;
cb[cb[p].fLink].bLink ← p;
cb[p].bLink ← rover;
cb[rover].fLink ← p};
cb[p].free ← TRUE};
queries
Bounds: PUBLIC ENTRY PROC[h: Handle, table: Selector] RETURNS[base: Base, size: CARD] = {
RETURN[h.bases[table], h.top[table]-h.offsets[table]]};
Top: PUBLIC ENTRY PROC[h: Handle, table: Selector] RETURNS[OrderedIndex] = {
RETURN[OrderedIndex.FIRST + h.top[table]]};
Bias: PUBLIC ENTRY PROC[h: Handle, table: Selector] RETURNS[CARD] = {
RETURN[h.offsets[table]]};
VM utilities
unitsPerPage: NAT = VM.wordsPerPage;
UnitsForPages: PROC[pages: PageCount] RETURNS[CARD] = INLINE {
RETURN[pages*unitsPerPage]};
PagesForUnits: PROC[units: CARD] RETURNS[PageCount] = {
RETURN[(units+(unitsPerPage-1))/unitsPerPage]};
stack allocation from subzones
GrowTable: INTERNAL PROC[h: Handle, table: Selector, newTop: Bound] = {
newPages: CARD = PagesForUnits[newTop-h.offsets[table]];
IF newPages > h.vmPages[table] THEN {
extra: CARD = SIGNAL Overflow[h, table];
newVMSize: CARD = MIN[h.maxPages[table], newPages + extra];
newVM: VM.Interval = VM.Allocate[newVMSize];
newVMPointer: LONG POINTER ← VM.AddressForPageNumber[newVM.page];
oldVM: VM.Interval = h.vm[table];
IF oldVM # VM.nullInterval THEN {
oldVMPointer: LONG POINTER ← VM.AddressForPageNumber[oldVM.page];
nWords: CARD ← UnitsForPages[oldVM.count];
copyMax: CARDINAL = (CARDINAL.LAST-unitsPerPage)+1;
WHILE nWords > copyMax DO
PrincOpsUtils.LongCopy[oldVMPointer, copyMax, newVMPointer];
oldVMPointer ← oldVMPointer + copyMax;
newVMPointer ← newVMPointer + copyMax;
nWords ← nWords - copyMax;
ENDLOOP;
PrincOpsUtils.LongCopy[oldVMPointer, nWords, newVMPointer];
VM.Free[oldVM]};
h.vm[table] ← newVM;
h.bases[table] ← LOOPHOLE[newVMPointer-h.offsets[table]];
h.limit[table] ← UnitsForPages[newVMSize]+h.offsets[table];
h.vmPages[table] ← newVMSize;
RunNotifierChain[h]}
};
initialization, expansion and termination
Create: PUBLIC PROC[weights: DESCRIPTOR FOR ARRAY OF TableInfo] RETURNS[h: Handle] = {
cnt: CARDINAL = weights.LENGTH;
h ← NEW[InstanceData ← [
nTables: cnt,
notifiers: NIL,
bases: NEW[BaseSeq[cnt]],
offsets: NEW[OffsetSeq[cnt]],
vm: NEW[SpaceSeq[cnt]],
chunks: NEW[ChunkSeq[cnt]],
top: NEW[SizeSeq[cnt]],
limit: NEW[BoundSeq[cnt]],
vmPages: NEW[PageSeq[cnt]],
maxPages: NEW[PageSeq[cnt]]]];
FOR i: CARDINAL IN [0..cnt) DO InitTable[h, i, weights[i]] ENDLOOP};
InitTable: PROC[h: Handle, table: Selector, info: TableInfo] = {
base: Base;
h.maxPages[table] ← MIN[info.maxPages, PagesForUnits[addrSpan]];
IF info.initialPages > h.maxPages[table] THEN ERROR Failure[h, table];
h.vmPages[table] ← info.initialPages;
IF info.initialPages = 0 THEN {h.vm[table] ← VM.nullInterval; base ← NIL}
ELSE {
h.vm[table] ← VM.Allocate[info.initialPages];
base ← LOOPHOLE[VM.AddressForPageNumber[h.vm[table].page]]};
h.offsets[table] ← info.tag*addrSpan;
h.top[table] ← 0 + h.offsets[table]; h.limit[table] ← 0 + h.offsets[table];
h.bases[table] ← base - h.offsets[table];
h.chunks[table] ← NIL};
ResetTable: PUBLIC ENTRY PROC[h: Handle, table: Selector, info: TableInfo] = {
ENABLE UNWIND => {NULL};
IF h.vm[table] # VM.nullInterval THEN VM.Free[h.vm[table]];
InitTable[h, table, info];
RunNotifierChain[h]};
Destroy: PUBLIC ENTRY PROC[h: Handle] = {
ENABLE UNWIND => {NULL};
FOR i: CARDINAL IN [0..h.nTables) DO h.bases[i] ← Base.NIL-h.offsets[i] ENDLOOP;
RunNotifierChain[h];
FOR i: CARDINAL IN [0..h.nTables) DO
IF h.vm[i] # VM.nullInterval THEN VM.Free[h.vm[i]]
ENDLOOP;
};
Reset: PUBLIC ENTRY PROC[h: Handle] = {
ENABLE UNWIND => {NULL};
FOR i: CARDINAL IN [0..h.nTables) DO
h.top[i] ← 0 + h.offsets[i];
ResetChunkInternal[h, i];
ENDLOOP;
};
Chunkify: PUBLIC ENTRY PROC[h: Handle, table: Selector, firstSmall, nSmall: NAT] = {
ENABLE UNWIND => {NULL};
ch: ChunkHandle ← h.chunks[table];
IF ch # NIL THEN RETURN WITH ERROR Failure[h, table];
ch ← NEW[ChunkObject[nSmall]];
ch.firstSmall ← firstSmall;
ch.nullChunkIndex ← CIndex.FIRST + h.offsets[table]; -- set tag
h.chunks[table] ← ch;
ResetChunkInternal[h, table]};
UnChunkify: PUBLIC ENTRY PROC[h: Handle, table: Selector] = {
ENABLE UNWIND => {NULL};
h.chunks[table] ← NIL};
Trim: PUBLIC ENTRY PROC[h: Handle, table: Selector, size: CARD] = {
ENABLE UNWIND => {NULL};
newTop: CARD = size + h.offsets[table];
IF newTop <= h.top[table] THEN {h.top[table] ← newTop; ResetChunkInternal[h, table]}
ELSE RETURN WITH ERROR Failure[h, table]};
ResetChunk: PUBLIC ENTRY PROC[h: Handle, table: Selector] = {
ResetChunkInternal[h, table ! UNWIND => {NULL}]};
ResetChunkInternal: INTERNAL PROC[h: Handle, table: Selector] = {
ch: ChunkHandle = h.chunks[table];
IF ch # NIL THEN {
ch.chunkRover ← ch.nullChunkIndex;
FOR i: NAT IN [0..ch.nSmall) DO ch.smallLists[i] ← ch.nullChunkIndex ENDLOOP}
};
Notifier stuff
NotifyNode: TYPE = RECORD[notifier: Notifier, link: NotifyChainHandle];
NotifyChainHandle: TYPE = REF NotifyNode;
AddNotify: PUBLIC ENTRY PROC[h: Handle, proc: Notifier] = {
ENABLE UNWIND => {NULL};
p: NotifyChainHandle = NEW[NotifyNode ← [notifier: proc, link: h.notifiers]];
h.notifiers ← p;
proc[h.bases]};
DropNotify: PUBLIC ENTRY PROC[h: Handle, proc: Notifier] = {
ENABLE UNWIND => {NULL};
IF h.notifiers # NIL THEN {
p: NotifyChainHandle ← h.notifiers;
IF p.notifier = proc THEN h.notifiers ← p.link
ELSE {
q: NotifyChainHandle;
DO
q ← p;
p ← p.link;
IF p = NIL THEN RETURN;
IF p.notifier = proc THEN EXIT
ENDLOOP;
q.link ← p.link};
p ← NIL;
};
};
RunNotifierChain: INTERNAL PROC[h: Handle] = {
FOR p: NotifyChainHandle ← h.notifiers, p.link UNTIL p = NIL DO
p.notifier[h.bases] ENDLOOP
};
}.