AllocatorOps.mesa
Paul Rovner, December 6, 1983 3:29 pm
Russ Atkinson (RRA) February 27, 1985 10:48:57 pm PST
Beach, February 23, 1985 9:26:54 am PST
Doug Wyatt, February 24, 1985 9:04:33 pm PST
Definitions for the Cedar allocator: object prefix formats, ZONE formats
DIRECTORY
Allocator USING [bsiEscape, ExtendedHeader, HeaderP, LastAddress, NHeaderP, NormalHeader, QuantumMap, QuantumIndex, wordsPerQuantum, BSIToSizeObj, SizeToBSIObj, BlockSizeIndex],
Basics USING [BITAND, HighHalf, LongDiv, LowHalf],
SafeStorage USING [nullType, Type, TypeIndex];
AllocatorOps: DEFINITIONS
IMPORTS Basics
= BEGIN OPEN Allocator;
doubly-linked free lists
DFHeaderP: TYPE = LONG POINTER TO DoubleFreeHeader;
Rover: TYPE = DFHeaderP;
DoubleFreeHeader:
TYPE =
RECORD[
eh: ExtendedHeader,
nextFree: DFHeaderP,
prevFree: DFHeaderP
];
nonNullType: SafeStorage.Type = [LAST[SafeStorage.TypeIndex]];
permanentPageZone: UNCOUNTED ZONE;
bsiToSize: LONG POINTER TO BSIToSizeObj;
sizeToBSI: LONG POINTER TO SizeToBSIObj;
quantumMap: QuantumMap;
NewObject:
PROC[type: SafeStorage.Type, size:
CARDINAL, zone:
ZONE ←
NIL]
RETURNS[
REF
ANY];
-- CLEARED
PlausibleRef:
PROC[lc:
LONG
CARDINAL]
RETURNS[
BOOL] =
INLINE {
RETURN[
Basics.HighHalf[lc] IN [1..Basics.HighHalf[LastAddress]]
AND Basics.BITAND[Basics.LowHalf[lc], 1] = 0
AND quantumMap[AddressToQuantumIndex[lc]]
];
};
AddressToQuantumIndex:
PROC[addr:
LONG
CARDINAL]
RETURNS[QuantumIndex] =
INLINE {
RETURN [Basics.LongDiv[addr, wordsPerQuantum]];
This is the fastest and smallest method for performing this calculation. It assumes that QuantumIndex is one 16-bit word. We even use the overflow error for division to check for a bogus address (which should not be passed to this routine!).
};
ReferentType:
PROC[ref:
REF
ANY]
RETURNS[SafeStorage.Type] =
INLINE {
RETURN[
IF ref =
NIL
THEN SafeStorage.nullType
ELSE (LOOPHOLE[ref, LONG POINTER TO SafeStorage.Type]-1)^
];
};
BlockSize:
PROC[hp: HeaderP]
RETURNS[
INT];
REFToHP:
PROC[ref:
REF
ANY]
RETURNS[HeaderP] =
INLINE {
nhp: NHeaderP = LOOPHOLE[ref, NHeaderP] - SIZE[NormalHeader];
IF nhp.blockSizeIndex # bsiEscape
THEN RETURN[LOOPHOLE[nhp]]
ELSE RETURN[LOOPHOLE[ref, HeaderP] - SIZE[ExtendedHeader]];
};
REFToNHP:
PROC[ref:
REF
ANY]
RETURNS[NHeaderP] =
INLINE {
RETURN[LOOPHOLE[ref, NHeaderP] - SIZE[NormalHeader]]};
NHPToREF:
PROC[nhp: NHeaderP]
RETURNS[
REF
ANY] =
INLINE {
RETURN[LOOPHOLE[nhp + SIZE[NormalHeader], REF ANY]]};
HPToREF:
PROC[hp: HeaderP]
RETURNS[
REF
ANY] =
INLINE {
nhp: NHeaderP = LOOPHOLE[hp];
IF nhp.blockSizeIndex # bsiEscape
THEN RETURN[LOOPHOLE[hp + SIZE[NormalHeader]]]
ELSE RETURN[LOOPHOLE[hp + SIZE[ExtendedHeader]]];
};
FreeObject:
PROC[nhp: NHeaderP];
TAndSFreeObject:
PROC[nhp: NHeaderP];
ExpandNormalFreeList:
PROC[bsi: BlockSizeIndex];
Initialize: PROC; -- initializes the safe allocator.
Reset: PROC; -- called by the TAndS.
Stuff used by the TAndS
EnterAndCallBack: PROC[proc: PROC];
IsValidRef: PROC[p: LONG POINTER] RETURNS[BOOL]; -- NIL => TRUE
Stuff for UnsafeAllocatorImpl
Defined in AllocatorImpl
Procs that actually do the work of manipulating and modifying DoubleFree lists
DoCreateMediumSizedObject: PROC [size: NAT, type: SafeStorage.Type,
roverP: LONG POINTER TO--VAR-- Rover, counted: BOOL]
RETURNS[p: LONG POINTER ← NIL];
DoFreeMediumSizedObject: PROC[ptr: DFHeaderP, rover: Rover];
Defined in UnsafeAllocatorImpl
Procs called via NewHeapObject and FreeHeapObject to enter its monitor and then call the above guys to actually do the work
CreateMediumSizedHeapObject: PROC [size: NAT] RETURNS[p: LONG POINTER ← NIL];
FreeMediumSizedHeapObject: PROC [ptr: DFHeaderP];
END.