-- Swapper>ResidentHeapImpl.mesa (last edited by Jose on January 13, 1981 1:47 PM)

DIRECTORY

Environment: FROM "Environment" USING [Base, Long, wordsPerPage],

Inline: FROM "Inline" USING [BITAND],

MiscPrograms: FROM "MiscPrograms",

ResidentHeap: FROM "ResidentHeap" USING [first64K],

ResidentMemory: FROM "ResidentMemory" USING [Allocate, Free, Location],

RuntimeInternal: FROM "RuntimeInternal" USING [WorryCallDebugger],

Zone: FROM "Zone" USING [AddSegment, Alignment, BlockSize, Create, FreeNode, Handle, MakeNode, SplitNode, Status],

ZoneInternal: FROM "ZoneInternal" USING [NodeHeader];

ResidentHeapImpl: MONITOR
IMPORTS Inline, ResidentMemory, RuntimeInternal, Zone
EXPORTS ResidentHeap, MiscPrograms =

BEGIN

--Global types

InuseNodePointer: TYPE = Environment.Base RELATIVE POINTER TO inuse ZoneInternal.NodeHeader;

--Global constants for the resident heap (these should be adjusted to best reflect the demands of Pilot)

--Warning: The next two constants must be one as some of the clients of this module on some processors can not have an object crossing a page boundary. (For instance, IOCB’s can not cross a page boundary on the Dandelion.)

initialHeapSize: CARDINAL ← 1; --pages (this is what pilot currently needs initially)

heapSizeIncrement: CARDINAL ← 1; --pages

maxExtraSegments: CARDINAL ← 18; --increments; testPackage>rs232C needs these

inuseNodeHeaderSize: CARDINAL = SIZE [inuse ZoneInternal.NodeHeader];

largeObjectThreshold: Zone.BlockSize = Environment.wordsPerPage/2; -- any objects this size or larger will be allocated as separate pages and not in residentZone.

largeNodeThreshold: Zone.BlockSize = largeObjectThreshold+inuseNodeHeaderSize;

--Global variables for the resident heap

residentZone: PUBLIC Zone.Handle;

status: Zone.Status;

base: Environment.Base = ResidentHeap.first64K;--to save typing!

numberOfExtraSegments: CARDINAL ← 0;

--Statistical counters

allocates, frees, splits: CARDINAL ← 0;

alignmentDistribution: ARRAY Zone.Alignment OF CARDINAL ← ALL [0];

sizeDistribution: ARRAY [0..nSizes] OF CARDINAL ← ALL [0];

nSizes: CARDINAL = 11;

sizes: ARRAY [0..nSizes) OF Zone.BlockSize = [4, 8, 12, 16, 24, 32, 48, 64, 128, 256, 512];

InitializeResidentHeap: PUBLIC PROCEDURE =

BEGIN

[residentZone, status] ← Zone.Create[

storage: ResidentMemory.Allocate[first64K, initialHeapSize],

length: Environment.wordsPerPage * initialHeapSize,

zoneBase: base];

IF status~=okay THEN DO RuntimeInternal.WorryCallDebugger["Can’t init resident heap"] ENDLOOP;

END;

--Implementation of the heap operations

FreeNode: PUBLIC ENTRY PROCEDURE [p: Environment.Base RELATIVE POINTER] RETURNS [s: Zone.Status] =

BEGIN

nodeP: InuseNodePointer = LOOPHOLE [p-inuseNodeHeaderSize];

frees ← frees+1;

IF base[nodeP].length >= largeNodeThreshold THEN

BEGIN -- Assumption: alignments are at no greater than single page boundaries. Otherwise, WordsToPages is not returning the actual number of pages allocated

ResidentMemory.Free[first64K, WordsToPages [base[nodeP].length], @base[p]];

RETURN [okay];

END

ELSE RETURN[Zone.FreeNode[zH: residentZone, p: @base[p]]];

END;

Increment: PRIVATE ENTRY PROCEDURE [count: POINTER TO CARDINAL] =

INLINE BEGIN count↑ ← count↑+1; END;

MakeNode: PUBLIC ENTRY PROCEDURE [n: Zone.BlockSize, alignment: Zone.Alignment] RETURNS [node: Environment.Base RELATIVE POINTER, s: Zone.Status] =

BEGIN

UpdateCounts: PROCEDURE =

BEGIN

i: [0..nSizes);

allocates ← allocates + 1;

alignmentDistribution[alignment] ← alignmentDistribution[alignment]+1;

FOR i IN [0..nSizes) DO

IF n < sizes[i] THEN BEGIN sizeDistribution[i] ← sizeDistribution[i]+1; EXIT; END;

REPEAT FINISHED => sizeDistribution[nSizes] ← sizeDistribution[nSizes]+1;

ENDLOOP;

END;

IF n >= largeObjectThreshold THEN

BEGIN

alignmentModulii: ARRAY Zone.Alignment OF CARDINAL = [1, 2, 4, 8, 16]; -- entry for alignment "ai" is i

masks: ARRAY Zone.Alignment OF CARDINAL = [177777B, 177776B, 177774B, 177770B, 177760B]; -- entry for alignment "ai" is 177777B left shifted by log2i-1. Thus i must be a power of 2.

alignmentModulus: CARDINAL; -- Cardinal’ized version of alignment

mask: CARDINAL; -- used to turn a pointer into a pointer to aligned storage

nodeOffset: CARDINAL; -- Offset of the allocated node

size: CARDINAL; -- size of the allocated node (in words)

longNodeP: Environment.Long;

nodeP: InuseNodePointer;

alignmentModulus ← alignmentModulii [alignment];

mask ← masks [alignment];

nodeOffset ← Inline.BITAND [inuseNodeHeaderSize+alignmentModulus-1, mask]-inuseNodeHeaderSize; -- align the node so that the data area is properly aligned as per alignment

size ← nodeOffset+inuseNodeHeaderSize+n;

longNodeP.lp ← ResidentMemory.Allocate [first64K, WordsToPages [size]];

nodeP ← LOOPHOLE [LOOPHOLE [longNodeP.lp-base, Environment.Long].lowbits+nodeOffset];

base[nodeP] ← ZoneInternal.NodeHeader [length: size, extension: inuse[]];

UpdateCounts[];

RETURN [LOOPHOLE [nodeP+inuseNodeHeaderSize], okay];

END

ELSE -- Else it is a small object so use residentZone

BEGIN

[node, s] ← Zone.MakeNode[zH: residentZone, n: n, alignment: alignment];

IF s=noRoomInZone THEN

IF numberOfExtraSegments < maxExtraSegments THEN

BEGIN

status ← Zone.AddSegment[zH: residentZone, storage: ResidentMemory.Allocate [first64K, heapSizeIncrement], length: Environment.wordsPerPage * heapSizeIncrement].s;

IF status=okay THEN numberOfExtraSegments ← numberOfExtraSegments+1

ELSE RuntimeInternal.WorryCallDebugger["Resident heap extension error."];

[node, s] ← Zone.MakeNode[zH: residentZone, n: n, alignment: alignment];

IF s=noRoomInZone THEN RuntimeInternal.WorryCallDebugger["Node too large for Resident Heap"];

END;

IF s=okay THEN UpdateCounts[];

END;

END;

SplitNode: PUBLIC PROCEDURE [p: Environment.Base RELATIVE POINTER, n: Zone.BlockSize] RETURNS [s: Zone.Status] =

-- Splitting of large object nodes is not supported due the percieved needs of the clients of large nodes

BEGIN

nodeP: InuseNodePointer = LOOPHOLE [p-inuseNodeHeaderSize];

Increment[@splits];

IF base[nodeP].length >= largeNodeThreshold THEN RETURN [okay]

ELSE RETURN[Zone.SplitNode[zH: residentZone, p: @base[p], n: n]];

END;

WordsToPages: PRIVATE PROCEDURE [n: CARDINAL] RETURNS [CARDINAL] =

BEGIN

RETURN [(n+Environment.wordsPerPage-1)/Environment.wordsPerPage];

END;

END.

LOG

Time: April 30, 1979 9:18 PMBy: LauerAction: Created file

Time: June 2, 1979 10:47 PMBy: LauerAction: Replaced the stub in this file with the real implementation of the resident heap

Time: July 18, 1979 2:57 PMBy: KnutsenAction: Merged contents of obsolete ZoneExtension into Zone and Environment.

Time: August 17, 1979 4:28 PMBy: LauerAction: Changed initialHeapSize, heapSizeIncrement, maxExtraSegments to variables; improved statistics gathering in sizeDistribution

Time: September 13, 1979 10:48 AMBy: SchwartzAction: Allowed nodes slightly larger than one page (for Gateway communication with Xerox 850), and corrected diagnosis of attempts to allocate nodes larger than maxNodeSize.

Time: November 16, 1979 9:56 AMBy: ForrestAction: Fixed max number of increment’s logic. Made MakeNode an entry procedure, since the test for extending the node has to be "atomic".

Time: November 20, 1979 6:54 PMBy: ForrestAction: Raised number of increments to 5, since this is what TestPackage>Exercise RS232C needs to run. Also incresed initial allocation to 3

Time: April 10, 1980 2:55 PMBy: LuniewskiAction: Allocate large objects in the first 64K but not in the actual resident zone in order to avoid fragmentation problems in the zone. Also, modify so that small objects do not cross page boundaries.

Time: April 14, 1980 9:12 AMBy: KnutsenAction: Now STARTed by InitializeResidentHeap.

Time: January 13, 1981 1:47 PMBy: JoseAction: Eliminated conversions of relative pointers to short pointers; deleted RelativePointerToPointer, NodeSize, LargeNode.