[Cyan]<Cedar6.0>VM>VMAllocImpl.mesa!3

VMAllocImpl.mesa

Levin on November 15, 1983 2:59 pm

Russ Atkinson (RRA) January 30, 1985 10:01:12 pm PST

Doug Wyatt, February 26, 1985 10:01:32 am PST

DIRECTORY

Basics USING [bitsPerWord],

PrincOps USING [Port, zEXCH, zOR, zPOP, zPUSH, zXOR],

PrincOpsUtils USING [--DBITOR, DBITXOR,-- --D--BITSHIFT, GetReturnLink, SetReturnLink],

VM USING [Free, Interval, LogPageCount, nullInterval, PageCount, PageNumber, VMPartition],

VMInternal USING [AllocationOutcome, allocCounts, Crash, IsFree, logPagesIn64K, MarkAllocated, pagesIn64K, partitions],

VMSideDoor USING [vmPages],

VMStatistics USING [HistogramCounts, HistogramSizes];

VMAllocImpl: MONITOR LOCKS allocationLock

IMPORTS PrincOpsUtils, VM, VMInternal, VMSideDoor

EXPORTS VM, VMInternal, VMStatistics

= BEGIN OPEN VM;

CallerBug: ERROR = CODE;

Global Variables protected by the monitor

rovers: ARRAY VMPartition OF PageNumber;

clump: Interval ← nullInterval;

Exports to VM

CantAllocate: PUBLIC ERROR [bestInterval: Interval] = CODE;

Allocate: PUBLIC SAFE PROC [

count: PageCount, partition: VMPartition ← normalVM, subRange: Interval ← [0, 0],

start: PageNumber ← 0, alignment: LogPageCount ← 0, in64K: BOOL ← FALSE]

RETURNS [interval: Interval] = TRUSTED {

pagesIn64K: PageCount = VMInternal.pagesIn64K;

logPagesIn64K: PageCount = VMInternal.logPagesIn64K;

oldClump: Interval ← nullInterval;

AllocateEntry: ENTRY PROC RETURNS [outcome: VMInternal.AllocationOutcome] = INLINE {

Since we have acquired the allocation lock, we must not trigger any frame allocation, since a frame fault would then cause a deadlock.

IF in64K THEN {

IF count > pagesIn64K OR alignment > logPagesIn64K THEN RETURN[$badParameters];

IF partition = $normalVM AND subRange.count < count AND start = 0 THEN {

breakage: PageCount;

interval ← [page: RoundUp[clump.page, PagesForAlignment[alignment]], count: count];

IF clump.count >= interval.count + (breakage ← interval.page - clump.page) THEN {

oldClump ← [page: clump.page, count: breakage];

clump.count ← clump.count - breakage - interval.count;

clump.page ← interval.page + interval.count;

RETURN[$ok]

}

ELSE {

savedRover: PageNumber = rovers[$normalVM];

oldClump ← clump; -- can't call Free here, since the monitor is held.

IF ([interval: clump] ← AllocateVirtualMemoryInternal[

interval ← [page: clump.page, count: count];

clump.count ← clump.count - interval.count;

clump.page ← interval.page + interval.count;

rovers[$normalVM] ← savedRover; -- try to avoid fragmentation

RETURN[$ok]

}

ELSE clump ← nullInterval;

};

[outcome, interval] ←

AllocateVirtualMemoryInternal[count, partition, subRange, start, alignment, in64K];

};

outcome: VMInternal.AllocationOutcome = AllocateEntry[];

IF oldClump.count ~= 0 THEN Free[oldClump];

SELECT outcome FROM

$ok => NULL;

$notFound => ERROR CantAllocate[bestInterval: interval];

$badParameters => ERROR CallerBug;

ENDCASE;

};

SimpleAllocate: PUBLIC SAFE PROC[count: PageCount] RETURNS[interval: Interval] = CHECKED {

RETURN[Allocate[count: count]];

};

Exports to VMStatistics

FreeSpaceHistogram: PUBLIC PROC [

partition: VMPartition ← $normalVM,

sizes: VMStatistics.HistogramSizes ← NIL, counts: VMStatistics.HistogramCounts] = {

range: VM.Interval = VMInternal.partitions[partition];

limit: PageNumber = range.page + range.count;

page: PageNumber ← range.page;

runProc: PROC [size: PageCount] ← IF sizes = NIL THEN DefaultSizes ELSE ClientSizes;

DefaultSizes: PROC [size: PageCount] = {

IF size <= counts.LENGTH THEN counts[size.PRED] ← counts[size.PRED].SUCC

ELSE counts[counts.LENGTH.PRED] ← counts[counts.LENGTH.PRED].SUCC;

};

ClientSizes: PROC [size: PageCount] = {

Binary search

low: NAT ← 0;

high: NAT ← sizes.LENGTH.PRED;

probe: NAT;

UNTIL low > high DO

probe ← (low + high) / 2;

SELECT sizes[probe] FROM

= size => EXIT;

> size => IF probe = 0 THEN EXIT ELSE high ← probe.PRED;

< size => IF (probe ← probe.SUCC) = sizes.LENGTH THEN EXIT ELSE low ← probe;

ENDCASE;

REPEAT

FINISHED => probe ← low;

ENDLOOP;

counts[probe] ← counts[probe].SUCC;

};

Validate parameters.

IF counts = NIL OR counts.LENGTH <= 1 THEN ERROR CallerBug;

IF sizes ~= NIL THEN {

IF sizes.LENGTH ~= counts.LENGTH.PRED THEN ERROR CallerBug;

IF sizes[0] = 0 THEN ERROR CallerBug;

FOR i: NAT IN [1..sizes.LENGTH) DO

IF sizes[i-1] >= sizes[i] THEN ERROR CallerBug;

ENDLOOP;

};

Build histogram.

FOR i: NAT IN [0..counts.LENGTH) DO counts[i] ← 0; ENDLOOP;

runStart: PageNumber;

UNTIL page >= limit DO

skip over in-use run

IF VMInternal.IsFree[page] THEN EXIT;

page ← page.SUCC;

REPEAT

FINISHED => EXIT;

ENDLOOP;

runStart ← page;

page ← page.SUCC;

UNTIL page >= limit DO

IF ~VMInternal.IsFree[page] THEN EXIT;

page ← page.SUCC;

ENDLOOP;

runProc[page - runStart];

ENDLOOP;

};

Exports to VMInternal

allocationLock: PUBLIC MONITORLOCK;

AllocateVirtualMemoryInternal: PUBLIC PROC [

count: PageCount, partition: VMPartition ← $normalVM, subRange: Interval ← [0, 0],

start: PageNumber ← 0, alignment: LogPageCount ← 0, in64K: BOOL ← FALSE]

RETURNS [outcome: VMInternal.AllocationOutcome, interval: Interval] ←

LOOPHOLE[@AwaitAllocate];

Internal procedures

AwaitAllocate: PORT [outcome: VMInternal.AllocationOutcome, interval: Interval]

RETURNS [count: PageCount, partition: VMPartition, subRange: Interval,

start: PageNumber, alignment: LogPageCount, in64K: BOOL];

InitializeAllocateVirtualMemoryInternal: PROC

RETURNS [outcome: VMInternal.AllocationOutcome, interval: Interval] = {

LOOPHOLE[AwaitAllocate, PrincOps.Port].dest ← PrincOpsUtils.GetReturnLink[];

partition: VMPartition;

subRange: Interval;

start: PageNumber;

alignment: LogPageCount;

in64K: BOOL;

[count, partition, subRange, start, alignment, in64K] ← AwaitAllocate[outcome, interval];

The following is to permit the debugger to trace the stack.

PrincOpsUtils.SetReturnLink[LOOPHOLE[AwaitAllocate, PrincOps.Port].dest];

BEGIN

This block is the body of the actual allocation algorithm.

within: Interval ← VMInternal.partitions[partition];

--*stats*--

VMInternal.allocCounts[partition].requests ←

VMInternal.allocCounts[partition].requests.SUCC;

IF subRange.count >= count THEN {

IF ~(subRange.page IN [within.page..within.page+within.count)) OR

~(subRange.page+subRange.count IN (within.page..within.page+within.count]) THEN

{outcome ← $badParameters; LOOP};

within ← subRange;

};

IF start = 0 THEN start ← rovers[partition]

ELSE IF ~(start IN [within.page..within.page+within.count)) THEN

{outcome ← $badParameters; LOOP};

interval ← FindHole[count, within, start, alignment, in64K];

IF interval.count = count THEN {

FOR page: PageNumber IN [interval.page..interval.page+interval.count) DO

VMInternal.MarkAllocated[page];

ENDLOOP;

outcome ← $ok;

rovers[partition] ← interval.page + interval.count - 1;

--*stats*--

VMInternal.allocCounts[partition].requestsSatisfied ←

VMInternal.allocCounts[partition].requestsSatisfied.SUCC;

VMInternal.allocCounts[partition].pagesAllocated ←

VMInternal.allocCounts[partition].pagesAllocated + count;

}

ELSE outcome ← $notFound;

END;

ENDLOOP;

};

FindHole: PROC [

count: PageCount, range: Interval, start: PageNumber, alignment: LogPageCount, in64K: BOOL]

RETURNS [bestFound: Interval] = INLINE {

This code was adapted from IFS's DiskFindHole.bcpl.

FindNextHole: PROC [

RETURNS [bestSeen: Interval ← [page: , count: 0]] = INLINE {

This procedure searches the interval "scanRange" looking for a contiguous hole of "count" pages beginning at a page "base" such that base MOD alignPages = 0. If such a hole exists, the base of the hole is returned in "bestSeen.page" and "bestSeen.count" will equal "count". Furthermore, this procedure guarantees to return the "leftmost" such hole, that is, bestSeen.page will be minimal (within "scanRange"). If no such hole exists, "bestSeen" will describe the largest hole actually encountered during the scan (which, however, may not be the largest hole present in "scanRange"). This hole will generally not satisfy the alignment constraint.

Crosses64KBoundary: PROC [start, end: PageNumber] RETURNS [BOOL] = INLINE {

DBITXOR: PROC [a, b: INT] RETURNS [INT] = MACHINE CODE {

When Trinity/Klamath comes, use PrincOpsUtils.DBITXOR directly

PrincOps.zPOP; PrincOps.zEXCH; PrincOps.zPUSH; PrincOps.zXOR; PrincOps.zEXCH;

};

RETURN[--PrincOpsUtils.--DBITXOR[start, end] >= VMInternal.pagesIn64K]

};

IF count <= scanRange.count THEN {

base, exBase: PageNumber ← RoundUp[scanRange.page, alignPages];

lastPage: PageNumber ← scanRange.page + scanRange.count - count;

UNTIL base > lastPage DO

Invariants:

exBase >= base

[base..exBase) have been searched exhaustively and are known to be free

top: PageNumber = base + count - 1;

IF in64K AND Crosses64KBoundary[base, top] THEN

base ← exBase ← RoundUp[base, VMInternal.pagesIn64K]

ELSE

FOR page: PageNumber DECREASING IN [exBase..top] DO

IF ~VMInternal.IsFree[page] THEN {

IF top - page > bestSeen.count THEN {

bestSeen.count ← top - page; bestSeen.page ← page + 1};

Try now for a new hole starting at page+1. (page..top] are known to be free.

base ← RoundUp[page + 1, alignPages];

exBase ← MAX[top + 1, base];

EXIT

};

REPEAT

FINISHED => RETURN [[base, count]];

ENDLOOP;

};

endRange: PageNumber = range.page + range.count - 1;

alignPages: PageCount = PagesForAlignment[alignment];

bestFound ← FindNextHole[count, [start, range.count - (start - range.page)], alignPages, in64K];

IF bestFound.count = count THEN RETURN;

IF start ~= range.page THEN {

bestFound ← FindNextHole[

count, [range.page, MIN[start - range.page + count, range.count]], alignPages, in64K];

IF bestFound.count = count THEN RETURN;

};

There is no hole of the requested size and alignment. "bestFound" is some smaller hole, probably misaligned. The code that follows sets "bestFound" to the leftmost, largest free interval less than "count" plages in length, but does not guarantee that this interval satisfies the alignment constraint. (Implementation note for future reference: to do this would seem to require iterating on FindNextHole with decreasing counts until an interval is found that satisfies the alignment constraint. Unfortunately, this is much more expensive, since the trick used below to limit the search to a single pass of the VM map doesn't work.)

IF bestFound.count = 0 THEN

FOR page: PageNumber IN [range.page..range.page + range.count) DO

IF VMInternal.IsFree[page] THEN {bestFound.page ← page; bestFound.count ← 1; EXIT};

REPEAT

FINISHED => RETURN; -- "range" is completely allocated

ENDLOOP;

The following two conditions now hold:

"bestFound" describes a non-empty hole within "range"

For any range q with range.page <= q.page < bestFound.page and q.count = bestFound.count, q contains at least one allocated page. That is, bestFound.page describes the "leftmost" hole of size bestFound.count.

The following loop increases bestFound.count holding the above conditions invariant. When it terminates, bestFound describes the leftmost, largest interval of fewer than "count" pages that is unallocated. Note that "remainingRange.page" increases monotonically throughout this loop, thus at worst a single pass over the VM map is required to find the best hole.

remainingRange: Interval ←

[page: bestFound.page + bestFound.count,

newBest: Interval ← FindNextHole[bestFound.count + 1, remainingRange, 1, FALSE];

page: PageNumber ← newBest.page + bestFound.count + 1;

IF newBest.count <= bestFound.count THEN EXIT; -- no progress

Assert: newBest.count = bestFound.count + 1

Find out how many pages immediately following newBest are also unallocated.

WHILE page <= endRange AND VMInternal.IsFree[page] DO

page ← page + 1;

ENDLOOP;

bestFound ← [page: newBest.page, count: page - newBest.page];

ENDLOOP;

};

RoundUp: PROC [page: PageNumber, count: PageCount] RETURNS [PageNumber] = INLINE {

"count" must be a power of two.

DBITOR: PROC [a, b: INT] RETURNS [INT] = MACHINE CODE {

When Trinity/Klamath comes, use PrincOpsUtils.DBITOR directly

PrincOps.zPOP; PrincOps.zEXCH; PrincOps.zPUSH; PrincOps.zOR; PrincOps.zEXCH;

};

RETURN[--PrincOpsUtils.--DBITOR[page-1, count-1]+1]

};

PagesForAlignment: PROC [alignment: LogPageCount] RETURNS [PageCount] = INLINE {

Hack: TYPE = MACHINE DEPENDENT RECORD [low, high: CARDINAL];

RETURN[ -- Trinity/Klamath: PrincOpsUtils.DBITSHIFT[1, alignment]

IF alignment >= Basics.bitsPerWord THEN

LOOPHOLE[Hack[low: 0, high: PrincOpsUtils.BITSHIFT[1, alignment - Basics.bitsPerWord]]]

ELSE LONG[PrincOpsUtils.BITSHIFT[1, alignment]]

]

};

UpdateVMLimit: PUBLIC ENTRY PROC [pages: VM.PageCount] = {

IF pages < VMSideDoor.vmPages THEN VMInternal.Crash[];

VMSideDoor.vmPages ← pages;

VMInternal.partitions[$normalVM].count ← pages - VMInternal.partitions[$normalVM].page;

};

NoteFreePages: PUBLIC ENTRY PROC [interval: VM.Interval] = {

Since we have acquired the allocation lock, we must not trigger any frame allocation, since a frame fault would then cause a deadlock.

FOR partition: VMPartition IN VMPartition DO

pi: VM.Interval = VMInternal.partitions[partition];

IF interval.page IN [pi.page..pi.page+pi.count) THEN {

IF rovers[partition] > interval.page THEN rovers[partition] ← interval.page;

--*stats*--

VMInternal.allocCounts[partition].pagesFreed ←

VMInternal.allocCounts[partition].pagesFreed + interval.count;

EXIT

}

ENDLOOP;

};

Initialization

FOR partition: VMPartition IN VMPartition DO

rovers[partition] ← VMInternal.partitions[partition].page;

ENDLOOP;

[] ← InitializeAllocateVirtualMemoryInternal[];

END.