DIRECTORY Allocator USING[bsiEscape, EHeaderP, ExtendedHeader, PUZone], AllocatorOps USING[DoubleFreeHeader, Rover, DFHeaderP, DoCreateMediumSizedObject, DoFreeMediumSizedObject, nonNullType], Process USING [Pause], UnsafeStoragePrivate USING[], VMInternal USING[partitions], -- move this to VMSideDoor VM USING[AddressForPageNumber, Allocate, CantAllocate, Free, Interval, MakeUnchanged, nullInterval, PageCount, PagesForWords, PageNumber, PageNumberForAddress, wordsPerPage]; UnsafeAllocatorImpl: MONITOR IMPORTS AllocatorOps, Process, VM, VMInternal EXPORTS AllocatorOps, UnsafeStoragePrivate = BEGIN OPEN AllocatorOps; InsufficientVM: ERROR = CODE; UZHandle: TYPE = LONG POINTER TO UZObject; UZObject: TYPE = MACHINE DEPENDENT RECORD [ procs(0:0..31): LONG POINTER TO UZProcs ]; UZProcs: TYPE = MACHINE DEPENDENT RECORD [ new(0): PROC[self: UZHandle, size: CARDINAL] RETURNS[LONG POINTER], free(1): PROC[self: UZHandle, object: LONG POINTER] ]; ppzProcs: UZProcs _ [new: PPZNew, free: NIL]; ppzObject: UZObject _ [procs: @ppzProcs]; permanentPageZone: PUBLIC UNCOUNTED ZONE _ LOOPHOLE[LONG[@ppzObject]]; heapRoot: DoubleFreeHeader _ [ eh: [extendedSize: 0, normalHeader: [blockSizeIndex: Allocator.bsiEscape]], nextFree: @heapRoot, prevFree: @heapRoot ]; heapRover: Rover _ @heapRoot; skipHeader: CARDINAL = SIZE[Allocator.ExtendedHeader]; skipToHeader: CARDINAL = VM.wordsPerPage - skipHeader; MaxTransientPageSize: INT = 8; -- Maximum size kept in the cache transientPageAllocCount: INT _ 0 ; transientPageAllocRover: VM.PageNumber _ 0; MaxTransientPageIntervalInRec: INT = 10; TransientPageListRec: TYPE = RECORD [ prev: REF TransientPageListRec, next: REF TransientPageListRec _ NIL, putIndex: CARDINAL _ 1, intervalStarts: ARRAY [1..MaxTransientPageIntervalInRec] OF VM.PageNumber _ ALL[0] ]; TransientPageList: PUBLIC ARRAY [1..MaxTransientPageSize] OF REF TransientPageListRec _ ALL[NIL]; PPZNew: PROC[self: UZHandle, size: CARDINAL] RETURNS[lp: LONG POINTER] = { nPages: INT = VM.PagesForWords[size]; lp _ VM.AddressForPageNumber [VM.Allocate[count: nPages, in64K: TRUE ! VM.CantAllocate => GOTO noVM].page]; EXITS noVM => ERROR InsufficientVM; }; CreateMediumSizedHeapObject: PUBLIC ENTRY PROC[size: NAT] RETURNS[LONG POINTER] = { ENABLE UNWIND => NULL; RETURN[ AllocatorOps.DoCreateMediumSizedObject[size, nonNullType, @heapRover, FALSE]]; }; FreeMediumSizedHeapObject: PUBLIC ENTRY PROC[ptr: DFHeaderP] = { ENABLE UNWIND => NULL; AllocatorOps.DoFreeMediumSizedObject[ptr, heapRover]; }; NewTransientPageObject: PUBLIC PROC[self: Allocator.PUZone, size: CARDINAL] RETURNS[p: LONG POINTER] = { nPages: VM.PageCount = MAX[2, VM.PagesForWords[size]+1]; -- both PagesForWords and MAX calls are inlines interval: VM.Interval _ VM.nullInterval; ehp: Allocator.EHeaderP; IF nPages > MaxTransientPageSize THEN { DO interval _ VM.Allocate[count: nPages ! VM.CantAllocate => CONTINUE;]; IF interval.page # 0 THEN EXIT; Process.Pause[1]; ENDLOOP; p _ VM.AddressForPageNumber[interval.page]; -- an inline } ELSE { found: BOOL; [found, p] _ getFromTransientCache[nPages]; -- an inline ENTRY IF ~found THEN { IF transientPageAllocCount > 10 THEN transientPageAllocCount _ 0; IF transientPageAllocCount = 0 THEN transientPageAllocRover _ VMInternal.partitions[normalVM].page; transientPageAllocCount _ transientPageAllocCount + 1; DO interval _ VM.Allocate[count: nPages, start: transientPageAllocRover ! VM.CantAllocate => CONTINUE;]; IF interval.page # 0 THEN { p _ VM.AddressForPageNumber[interval.page]; EXIT}; Process.Pause[1]; ENDLOOP; transientPageAllocRover _ interval.page; }; }; p _ p + skipToHeader; ehp _ LOOPHOLE[p, Allocator.EHeaderP]; ehp^ _ [ sizeTag: pages, extendedSize: nPages - 1, normalHeader: [blockSizeIndex: Allocator.bsiEscape, type: AllocatorOps.nonNullType] ]; p _ p + skipHeader; }; FreeTransientPageObject: PUBLIC PROC [self: Allocator.PUZone, object: LONG POINTER] = { IF LOOPHOLE[object, INT] # 0 THEN { objectHdr: Allocator.EHeaderP = LOOPHOLE[object - skipHeader]; nPages: VM.PageCount = objectHdr.extendedSize+1; interval: VM.Interval _ [page: VM.PageNumberForAddress[objectHdr], count: nPages]; IF nPages > MaxTransientPageSize THEN { VM.Free[interval]; -- does procedure call RETURN; } ELSE { putIntoTransientCache[interval]; -- this calls an inline, but it does a procedure call to VM.MakeUnchanged }; }; }; getFromTransientCache: ENTRY PROC [nPages: VM.PageCount] RETURNS [found: BOOL, address: LONG POINTER TO WORD] = INLINE { putIndex: INT _ TransientPageList[nPages].putIndex; IF putIndex > 1 THEN { putIndex_ putIndex - 1; address _ VM.AddressForPageNumber[TransientPageList[nPages].intervalStarts[putIndex]]; TransientPageList[nPages].putIndex _ putIndex; found _ TRUE; } ELSE { IF TransientPageList[nPages].prev = NIL THEN found _ FALSE ELSE { TransientPageList[nPages] _ TransientPageList[nPages].prev; address _ VM.AddressForPageNumber[ TransientPageList[nPages].intervalStarts[MaxTransientPageIntervalInRec]]; TransientPageList[nPages].putIndex _ MaxTransientPageIntervalInRec; found _ TRUE; }; }; }; putIntoTransientCache: ENTRY PROC [interval: VM.Interval] = INLINE { count: INT = interval.count; putIndex: INT _ TransientPageList[count].putIndex; VM.MakeUnchanged[interval]; -- by making the pages "unchanged", we retain the physical memory associated with this interval (decreases page faults); however we also make the page "clean" in that if it is reclaimed it will not be written to the backing file IF putIndex > MaxTransientPageIntervalInRec THEN { putIndex _ 1; IF TransientPageList[count].next = NIL THEN { TransientPageList[count].next _ NEW [TransientPageListRec _ [prev: TransientPageList[count]]]; TransientPageList[count].next.prev _ TransientPageList[count]; }; TransientPageList[count] _ TransientPageList[count].next; TransientPageList[count].putIndex _ 1; }; TransientPageList[count].intervalStarts[putIndex] _ interval.page; TransientPageList[count].putIndex _ putIndex + 1; }; InitializeTransientPageZone: PUBLIC PROC[] = { FOR i: INT IN [1..MaxTransientPageSize] DO TransientPageList[i] _ NEW[TransientPageListRec _ [prev: NIL]]; ENDLOOP; }; END. UnsafeAllocatorImpl.Mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Paul Rovner, November 9, 1983 8:33 am Russ Atkinson (RRA) February 1, 1985 2:17:34 pm PST Bob Hagmann February 19, 1985 4:26:22 pm PST protects the systemUZone free list and rover. Procs herein are simply entry procs that call back into AllocatorImpl. ERRORS TYPES UNCOUNTED ZONES and their data the permanentPageZone permanentPageZone requires no ENTRY procs permanentPageZone is ready for use the systemUZone free list and rover dummy entry; the "uncountedHeap" free list never has NIL ptrs the TransientPageZone data IMPLEMENTATION of permanentPageZone Referenced only from permanentPageZone (its NEW proc) IMPLEMENTATION support for the systemUZone; here because these need their own monitor Called only from AllocatorImpl.NewHeapObject. size includes overhead, has been quantized and is >= SIZE[DoubleFreeHeader]. This proc may return an object of a larger size than requested. Returns NIL if free list needs expansion. Called only from ExpandDoubleFreeList and FreeHeapObject in AllocatorImpl. Assume header is made IMPLEMENTATION of TransientPageZone Allocate an object that is page aligned, and as big as needed. fall back on VM allocator for really big objects No pages available of correct size. Get a new interval from VM. We maintain our oun rover so as to use up the small free chunks of VM in low memory. p now points to the start of the allocated page interval. Skip over extra words at the start of the page, and write a header. This header may not be needed, but the normal unsafe allocator writes them, so we do it here too. Read header to find out how big the object is. Then free the object using either VM or our oun internal cache. Internal Procedures Initialization Called from AllocatorImpl once collectable storage is up. Nothing works until this is called. Bob Hagmann February 19, 1985 1:26:32 pm PST added Transient Page Zone, DIRECTORY Bob Hagmann February 19, 1985 4:26:22 pm PST changes to: UnsafeAllocatorImpl สS˜codešœ™Kšœ ฯmœ1™—š กœž œžœžœžœžœ˜hJš œžœ žœžœŸœ ŸžŸ˜hJšœ žœ žœ˜(Jšœ˜šžœžœ˜'Jšœ0™0šž˜Jšœ žœžœžœ˜EJšžœžœžœ˜J˜Jšžœ˜—Jšœžœ&Ÿ ˜8J˜—šœžœ˜Jšœžœ˜ Jšœ,Ÿ˜>šžœžœ˜J™–Jšžœžœ˜AJšžœžœ@˜cJšœ6˜6šž˜Jšœ žœ:žœžœ˜eJšžœžœ/žœ˜NJ˜Jšžœ˜—Jšœ(˜(J˜—J˜—Jšœ:Ÿzœ,™เJšœ˜Jšœžœ˜&šœ˜Jšœ˜Jšœ˜JšœS˜SJšœ˜—Jšœ˜Jšœ˜J˜—š กœžœžœ"žœžœ˜Wšžœžœ žœžœ˜#J™oJšœ žœ˜>Jšœžœ&˜0Jšœ žœžœ1˜Ršžœžœ˜'JšžœŸ˜*Jšžœ˜J˜—šœžœ˜Jšœ"ŸI˜kJ˜—J˜—Jšœ˜J˜šœ™J˜š œžœžœ žœ žœ žœ žœžœžœžœžœ˜zJšœ žœ&˜3šžœžœ˜Jšœ˜Jšœ žœJ˜VJšœ.˜.Jšœžœ˜ J˜—šœžœ˜Jšžœ"žœžœ ž˜:šœžœ˜Jšœ;˜;Jšœ žœ`˜lJšœC˜CJšœžœ˜ J˜—J˜—J˜—J˜š  œžœžœ žœ žœ˜DJšœžœ˜Jšœ žœ%˜2JšžœŸไ˜€šžœ*žœ˜2Jšœ ˜ šžœ!žœžœ˜-Jšœ žœ;˜^Jšœ>˜>J˜—Jšœ9˜9Jšœ&˜&J˜—JšœB˜BJšœ1˜1J˜———K˜—head™Jšœ^™^šกœž œž˜.šžœžœžœž˜*Jšœžœžœ˜?Jšžœ˜—J˜——K˜Kšžœ˜K˜™,Kšœฯr ™$—K™™,Kšœ ข™—K™—…—(U