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; rovers: ARRAY VMPartition OF PageNumber; clump: Interval _ nullInterval; 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 { 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[ count: pagesIn64K, alignment: logPagesIn64K, in64K: TRUE]).outcome = $ok THEN { 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; }; 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] = { 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; }; 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; }; FOR i: NAT IN [0..counts.LENGTH) DO counts[i] _ 0; ENDLOOP; DO runStart: PageNumber; UNTIL page >= limit DO 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; }; 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]; 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[]; DO count: PageCount; partition: VMPartition; subRange: Interval; start: PageNumber; alignment: LogPageCount; in64K: BOOL; [count, partition, subRange, start, alignment, in64K] _ AwaitAllocate[outcome, interval]; PrincOpsUtils.SetReturnLink[LOOPHOLE[AwaitAllocate, PrincOps.Port].dest]; BEGIN 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 { FindNextHole: PROC [ count: PageCount, scanRange: Interval, alignPages: PageCount, in64K: BOOL] RETURNS [bestSeen: Interval _ [page: , count: 0]] = INLINE { Crosses64KBoundary: PROC [start, end: PageNumber] RETURNS [BOOL] = INLINE { DBITXOR: PROC [a, b: INT] RETURNS [INT] = MACHINE CODE { PrincOps.zPOP; PrincOps.zEXCH; PrincOps.zPUSH; PrincOps.zXOR; PrincOps.zEXCH; 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 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}; base _ RoundUp[page + 1, alignPages]; exBase _ MAX[top + 1, base]; EXIT }; REPEAT FINISHED => RETURN [[base, count]]; ENDLOOP; 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; }; 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; DO remainingRange: Interval _ [page: bestFound.page + bestFound.count, count: range.count - (bestFound.page + bestFound.count - range.page)]; 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 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 { DBITOR: PROC [a, b: INT] RETURNS [INT] = MACHINE CODE { PrincOps.zPOP; PrincOps.zEXCH; PrincOps.zPUSH; PrincOps.zOR; PrincOps.zEXCH; 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] = { 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; }; FOR partition: VMPartition IN VMPartition DO rovers[partition] _ VMInternal.partitions[partition].page; ENDLOOP; [] _ InitializeAllocateVirtualMemoryInternal[]; END. FVMAllocImpl.mesa last edited by Levin on November 15, 1983 2:59 pm Global Variables protected by the monitor Exports to VM Since we have acquired the allocation lock, we must not trigger any frame allocation, since a frame fault would then cause a deadlock. Exports to VMStatistics Binary search Validate parameters. Build histogram. skip over in-use run Exports to VMInternal Internal procedures The following is to permit the debugger to trace the stack. This block is the body of the actual allocation algorithm. This code was adapted from IFS's DiskFindHole.bcpl. 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. When Trinity/Klamath comes, use PrincOpsUtils.DBITXOR directly Invariants: exBase >= base [base..exBase) have been searched exhaustively and are known to be free Try now for a new hole starting at page+1. (page..top] are known to be free. 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.) 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. Assert: newBest.count = bestFound.count + 1 Find out how many pages immediately following newBest are also unallocated. "count" must be a power of two. When Trinity/Klamath comes, use PrincOpsUtils.DBITOR directly Since we have acquired the allocation lock, we must not trigger any frame allocation, since a frame fault would then cause a deadlock. Initialization Ê¦– "Cedar" style˜Jšœ™Jšœ1™1J˜šÏk ˜ Jšœœ˜Jšœ œ'˜5JšœœÏcœžœ ˜WJšœœR˜Zšœœ˜Jšœe˜e—Jšœœ˜Jšœ œ#˜5J˜J˜—šœ œœ˜)Jšœœ˜1Jšœœ˜&J˜—Jš˜J˜Jšœœ˜J˜Jšœœœ˜J˜J™J™)J˜Jšœœ œ˜(J˜J˜J™J™Jšœ ™ J˜J˜Jšœœœœ˜;J˜šÏnœœœœ˜JšœQ˜QJšœ;œœ˜HJšœœ˜)Jšœ.˜.Jšœ4˜4Jšœ"˜"šŸ œœœ+œ˜TJšœ†™†šœœ˜Jšœœœ˜Ošœœœœ˜HJšœ˜JšœS˜SšœIœ˜QJšœ/˜/Jšœ6˜6Jšœ,˜,Jšœ˜Jšœ˜—šœ˜J˜+Jšœž3˜Fšœ4˜6Jšœ4œœ˜OJ˜,J˜+J˜,Jšœ!ž˜>Jšœ˜J˜—Jšœ˜J˜—J˜—J˜—šœ˜JšœS˜S—J˜—Jšœ8˜8Jšœœ˜+šœ ˜Jšœœ˜Jšœ œ&˜8Jšœœ˜"Jšœ˜—J˜—J˜J˜J™J˜J™šŸœœœ˜!Jšœ#˜#Jšœ%œ+˜SJšœœ-˜6J˜-J˜Jšœ œœ œœœ ˜TšŸœœ˜(Jšœœœ œœ˜HJšœœœœœœ˜BJ˜—šŸœœ˜'Jšœ ™ Jšœœ˜ Jšœœ œœ˜Jšœœ˜šœ˜Jšœ˜šœ˜Jšœ œ˜Jšœ œœœœœ˜8Jšœ œœ œœ œ ˜LJšœ˜—š˜Jšœ˜—Jšœ˜—Jšœœ˜#J˜—Jšœ™Jšœ œœœœœ˜;šœ œœ˜Jšœœœœ˜;Jšœœœ˜%š œœœœ˜"Jšœœœ˜/Jšœ˜—J˜—Jšœ™Jšœœœœœœ˜;š˜J˜šœ˜Jšœ™Jšœœœ˜%Jšœœ˜š˜Jšœœ˜—Jšœ˜—Jšœ˜Jšœœ˜šœ˜Jšœœœ˜&Jšœœ˜Jšœ˜—Jšœ˜Jšœ˜—J˜—J™J™J™J˜Jšœœœ˜#J˜šŸœœœ˜,JšœR˜RJšœ;œœ˜Hšœ>˜EJšœ˜——J˜J™J™J˜šœœ<˜OJšœ?˜FJšœ3œ˜9J˜—šŸ'œ˜-Jšœ@˜GJšœD˜Lš˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœœ˜JšœY˜YJšœ;™;Jšœœ%˜IJš˜Jšœ:™:Jšœ4˜4šž˜šœ,˜,Jšœ+œ˜0——šœœ˜!šœœ*˜Ašœœ*˜OJšœœ˜!——J˜J˜—Jšœœ˜+šœœ œ*˜@Jšœœ˜!—J˜<šœœ˜ šœœ/˜HJ˜Jšœ˜—J˜Jšœ7˜7šž˜šœ5˜5Jšœ4œ˜9—šœ2˜2Jšœ9˜9——J˜—Jšœ˜Jšœ˜Jšœ˜—J˜—J˜šŸœœ˜JšœVœ˜[Jšœœ˜(Jšœ3™3šŸœœ˜JšœEœ˜JJšœ-œ˜™>JšœM˜MJšœM˜MJ˜—Jšœžœ&˜FJ˜—šœœ˜"Jšœ?˜?Jšœ@˜@šœ˜šœ™Jšœ™JšœG™G—J˜#šœœ˜/Jšœ4˜4—š˜šœ œœ˜3šœœ˜"šœœ˜%Jšœ7˜7—JšœL™LJ˜%Jšœ œ˜Jš˜J˜—š˜Jšœœ˜#—Jšœ˜——Jšœ˜—J˜—J˜—Jšœ4˜4Jšœ5˜5Jšœ`˜`Jšœœœ˜'šœœ˜šœ˜Jšœœ?˜V—Jšœœœ˜'J˜—Jšœû™ûšœ˜šœœ(˜AJšœœ.œ˜Sš˜Jšœœž"˜7—Jšœ˜——šœ&™&Jšœ5™5JšœÑ™Ñ—J™ëš˜šœ˜Jšœ(˜(JšœF˜F—JšœIœ˜PJšœ6˜6Jšœ"œœž˜>Jšœ+™+J™Kšœœ˜5J˜Jšœ˜—Jšœ=˜=Jšœ˜—J˜J˜—šŸœœ&œœ˜RJšœ™šœœœœœœ˜7Jšœ=™=JšœL˜LJšœL˜LJ˜—Jšœžœ˜3J˜—J˜šŸœœœœ˜PJšœœœ œœ œ˜<šœž:˜Cšœ!˜'Jšœ"œ%˜W—Jšœœœ˜/J˜—J˜J˜—š Ÿ œœœœ œ˜:Jšœœ˜6Jšœ˜JšœW˜WJ˜—J™J™š Ÿ œœœœœ˜˜>——Jš˜J˜—Jšœ˜—J˜J˜—J™J˜šœœ ˜,J˜:Jšœ˜—J˜/J˜Jšœ˜J™J™—…—(²Až