InternalAllocImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Sweet, 19-Aug-81 12:15:12
Satterthwaite, October 11, 1985 4:58:16 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, Limit, maxForBits, Notifier, OrderedIndex, pagesForBits, Selector, TableInfo],
PrincOpsUtils: TYPE USING [LongCopy],
VM: TYPE USING [AddressForPageNumber, Allocate, Free, Interval, nullInterval, PagesForWords, WordsForPages];
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,
tileSize: CARDINAL,
notifiers: NotifyChainHandle ← NIL,
bases: REF BaseSeq,
vm: REF SpaceSeq,
chunks: REF ChunkSeq,
top: REF SizeSeq,
indexBits: REF SizeSeq,
limit: REF BoundSeq,
vmPages: REF SizeSeq];
SizeSeq: TYPE = RECORD[SEQUENCE length: NAT OF CARDINAL];
Bound: TYPE = LONG CARDINAL;
BoundSeq: TYPE = RECORD[SEQUENCE length: NAT OF Bound];
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: CARDINAL] = CODE;
stack allocation from subzones
Words: PUBLIC ENTRY PROC[h: Handle, table: Selector, size: CARDINAL]
RETURNS[x: OrderedIndex] = {
ENABLE UNWIND => {NULL};
ok: BOOL ← TRUE;
x ← WordsInternal[h, table, size ! Failure => {ok ← FALSE; CONTINUE}];
IF NOT ok THEN RETURN WITH ERROR Failure[h, table]};
WordsInternal: INTERNAL PROC[h: Handle, table: Selector, size: CARDINAL] RETURNS[OrderedIndex] = {
index: CARDINAL = h.top[table];
newTop: Bound = index.LONG + size; -- could overflow CARDINAL for 16 bit pointers
IF newTop > h.limit[table] THEN {
IF newTop > maxForBits[h.indexBits[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): [0..maxForBits[15]],
fLink(1): CIndex,
bLink(2): CIndex];
CIndex: TYPE = Base RELATIVE POINTER [0..Limit) TO Chunk;
nullChunkIndex: CIndex = CIndex.FIRST;
ChunkHandle: TYPE = REF ChunkObject;
ChunkObject: TYPE = RECORD[
chunkRover: CIndex,
firstSmall: CARDINAL,
smallLists: SEQUENCE nSmall: CARDINAL 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..ch.firstSmall+ch.nSmall) THEN {
offset: CARDINAL = size - ch.firstSmall;
q ← ch.smallLists[offset];
IF q # nullChunkIndex THEN {ch.smallLists[offset] ← cb[q].fLink; GO TO found}};
q ← GetRoverChunk[cb, h.top[table], ch, size];
IF q # 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: CARDINAL IN [ch.firstSmall.. ch.firstSmall+ch.nSmall) DO
offset: CARDINAL = s - ch.firstSmall;
r: CIndex ← ch.smallLists[offset];
WHILE r # nullChunkIndex DO
next: CIndex = cb[r].fLink;
FreeRoverChunk[cb, ch, r, s];
r ← next;
ENDLOOP;
ch.smallLists[offset] ← nullChunkIndex;
ENDLOOP;
now all possible merges of free nodes can happen
q ← GetRoverChunk[cb, h.top[table], ch, size];
IF q = 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) = 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 ← 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 ← 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..ch.firstSmall+ch.nSmall) THEN {
offset: CARDINAL = 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 ← 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 = 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: CARDINAL] = {RETURN[h.bases[table], h.top[table]]};
stack allocation from subzones
fileTileSize: CARDINAL = 32; -- must be >= tileSize;
GrowTable: INTERNAL PROC[h: Handle, table: Selector, newTop: Bound] = {
newPages: CARDINAL = VM.PagesForWords[newTop];
IF newPages > h.vmPages[table] THEN {
extra: CARDINAL = SIGNAL Overflow[h, table];
newVMSize: CARDINAL = MIN[maxForBits[h.indexBits[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: CARDINAL = VM.WordsForPages[oldVM.count];
PrincOpsUtils.LongCopy[oldVMPointer, nwords, newVMPointer];
VM.Free[oldVM]};
h.vm[table] ← newVM;
h.bases[table] ← LOOPHOLE[newVMPointer];
h.vmPages[table] ← newVMSize;
RunNotifierChain[h]}
};
initialization, expansion and termination
Create: PUBLIC PROC[weights: DESCRIPTOR FOR ARRAY OF TableInfo, tileSize: CARDINAL]
RETURNS[h: Handle] = {
cnt: CARDINAL = weights.LENGTH;
h ← NEW[InstanceData ← [
nTables: cnt,
tileSize: tileSize, notifiers: NIL,
bases: NEW[BaseSeq[cnt]],
vm: NEW[SpaceSeq[cnt]],
chunks: NEW[ChunkSeq[cnt]],
top: NEW[SizeSeq[cnt]],
limit: NEW[BoundSeq[cnt]],
indexBits: NEW[SizeSeq[cnt]],
vmPages: NEW[SizeSeq[cnt]]]];
IF tileSize >= fileTileSize THEN ERROR;
FOR i: CARDINAL IN [0..cnt) DO InitTable[h, i, weights[i]] ENDLOOP};
InitTable: PROC[h: Handle, table: Selector, info: TableInfo] = {
max: CARDINAL = WITH w: info SELECT FROM
TRUE => pagesForBits[w.indexBits],
FALSE => w.initialVMemPages,
ENDCASE => ERROR;
iPages: CARDINAL ← info.initialPages;
IF iPages > max OR max > pagesForBits[info.indexBits] THEN
ERROR Failure[h, table];
h.indexBits[table] ← info.indexBits;
h.vmPages[table] ← max;
h.top[table] ← 0; h.limit[table] ← 0;
h.chunks[table] ← NIL;
IF iPages = 0 THEN {h.vm[table] ← VM.nullInterval; h.bases[table] ← NIL}
ELSE {
h.vm[table] ← VM.Allocate[max];
h.bases[table] ← LOOPHOLE[VM.AddressForPageNumber[h.vm[table].page]]}
};
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] ← NIL 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;
ResetChunkInternal[h, i];
ENDLOOP;
};
Chunkify: PUBLIC ENTRY PROC[h: Handle, table: Selector, firstSmall, nSmall: CARDINAL] = {
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;
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: CARDINAL] = {
ENABLE UNWIND => {NULL};
IF size <= h.top[table] THEN {h.top[table] ← size; 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 ← nullChunkIndex;
FOR i: CARDINAL IN [0..ch.nSmall) DO ch.smallLists[i] ← 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
};
}.