DIRECTORY
Allocator USING[BlockSizeIndex, bsiEscape, BSIToSizeObj, EHeaderP, ExtendedHeader, FNHeaderP, Header, HeaderP, LastAddress, logPagesPerQuantum, maxSmallBlockSize, minLargeBlockSize, NHeaderP, NormalHeader, pagesPerQuantum, PUZone, QMObject, QuantumCount, QuantumIndex, QuantumMap, SizeToBSIObj, UZoneObject, wordsPerQuantum, Zone, ZoneObject],
AllocatorOps USING[REFToNHP, permanentPageZone, CreateMediumSizedHeapObject, FreeMediumSizedHeapObject, DFHeaderP, DoubleFreeHeader, Rover, nonNullType],
Basics USING[LowHalf, BITAND],
Collector USING[InternalReclaim],
PrincOps USING[SD, wordsPerPage, StateVector, zRET],
PrincOpsUtils USING[ZERO, MyLocalFrame],
RCMicrocodeOps USING[CreateRef, Allocate, Free, rcMicrocodeExists, InsertQuanta, DoFREE, SoftwareAllocate, SoftwareFree, FREEPLEASE],
RTSD USING[sSystemZone],
SafeStorage USING[nullType, GetCanonicalType, NarrowRefFault, Type],
SafeStoragePrivate USING[],  -- TEMPORARY export of NewObject
StorageAccounting USING[nObjectsCreated, ConsiderCollection, nObjectsReclaimed, nWordsReclaimed],
StorageTraps USING[],
TrapSupport USING[BumpPC, GetTrapParam],
UnsafeStorage USING[],
VM USING[PageNumberForAddress, PagesForWords, Free, CantAllocate, Allocate, wordsPerPage],
ZCT USING[Enter, ExpandZCT, zct];

AllocatorImpl: MONITOR
IMPORTS
AllocatorOps, Basics, Collector, PrincOpsUtils, RCMicrocodeOps, SafeStorage, StorageAccounting, TrapSupport, VM, ZCT
EXPORTS
AllocatorOps, SafeStorage, SafeStoragePrivate, StorageTraps, UnsafeStorage

= BEGIN OPEN Allocator, AllocatorOps;

InsufficientVM: ERROR = CODE;
InvalidRef: PUBLIC ERROR[ref: REF ANY] = CODE;

checking: BOOL = TRUE;
takingStatistics: BOOL = TRUE;

maxSmallBlockRealSize: NAT = QuantizedSize[maxSmallBlockSize];
minLargeBlockRealSize: NAT = QuantizedSize[minLargeBlockSize];

rZnHeapSystem: UZoneObject _ [new: NewHeapObject, free: FreeHeapObject];
znHeapSystem: LONG POINTER _ LONG[@rZnHeapSystem];
zhs: UNCOUNTED ZONE _ LOOPHOLE[LONG[@znHeapSystem], UNCOUNTED ZONE];


bsiToSize: PUBLIC LONG POINTER TO BSIToSizeObj
			_ permanentPageZone.NEW[BSIToSizeObj _ ALL[0]];
sizeToBSI: PUBLIC LONG POINTER TO SizeToBSIObj _ permanentPageZone.NEW[SizeToBSIObj];

msRoot: DoubleFreeHeader _ [
eh: [extendedSize: 0, normalHeader: [blockSizeIndex: bsiEscape]],
nextFree: @msRoot,
prevFree: @msRoot
];
msRover: Rover _ @msRoot;
permRoot: DoubleFreeHeader _ [
eh: [extendedSize: 0, normalHeader: [blockSizeIndex: bsiEscape]],
nextFree: @permRoot,
prevFree: @permRoot
];
permRover: Rover _ @permRoot;
quantumMap: PUBLIC QuantumMap _ permanentPageZone.NEW[QMObject];

systemZone: ZONE _ NIL;
permanentZone: ZONE _ NIL;

nQMapEntries: INT _ 0;


NewUObject: PUBLIC PROC[size: CARDINAL--words--, zone: UNCOUNTED ZONE]
RETURNS [LONG POINTER] ={
RETURN[NewHeapObject[LOOPHOLE[zone, PUZone], size]];
};

GetSystemUZone: PUBLIC PROC RETURNS[UNCOUNTED ZONE] =
{RETURN[zhs]};

TrimUZone: PUBLIC PROC[zone: UNCOUNTED ZONE] = {
NULL;
};


NewHeapObject: PROC[self: PUZone, size: CARDINAL]
RETURNS[p: LONG POINTER] = {
realSize: INT = MAX[QuantizedSize[size], SIZE[DoubleFreeHeader]];
IF IsLargeRealSize[realSize]
THEN p _ CreateLargeObject
		   [type: nonNullType, size: realSize, permanent: FALSE, counted: FALSE]
ELSE
WHILE (p _ AllocatorOps.CreateMediumSizedHeapObject[size: realSize]) = NIL
DO ExpandDoubleFreeList
	[realSize: realSize, permanent: TRUE, varRover: NIL, counted: FALSE];
ENDLOOP;
IF checking THEN {
nhp: NHeaderP = p-SIZE[NormalHeader];
IF nhp.inZCT
OR nhp.f
OR nhp.rcOverflowed
OR nhp.refCount # 0
OR nhp.type # nonNullType
OR UsableWords[nhp] < size
THEN ERROR;
};
RETURN[p];
};  -- end NewHeapObject

FreeHeapObject: PROC[self: PUZone, object: LONG POINTER] = {
nhp: NHeaderP = LOOPHOLE[object - SIZE[NormalHeader]];
IF checking THEN
IF nhp.inZCT
OR nhp.f
OR nhp.rcOverflowed
OR nhp.refCount # 0
OR nhp.type # nonNullType
THEN ERROR;
IF nhp.blockSizeIndex = bsiEscape
THEN {  -- large or medium-sized object or extended header for some other reason
ehp: EHeaderP = NHPToEHP[nhp];
realSize: INT _ ExtendedBlockSize[ehp];
IF IsLargeRealSize[realSize]
THEN {
IF checking
AND (realSize MOD wordsPerQuantum # 0)
AND (LOOPHOLE[ehp, INT] MOD wordsPerQuantum # 0)
AND NOT IsClearQMapRange[qi: LPToQI[ehp], qc: WordsToQC[realSize]]
THEN ERROR;
VM.Free[
[page: VM.PageNumberForAddress[ehp],
 count: VM.PagesForWords[realSize]
]];
}
ELSE AllocatorOps.FreeMediumSizedHeapObject[LOOPHOLE[ehp, DFHeaderP]];
}
ELSE {  -- small normal object
LOOPHOLE[nhp, EHeaderP]^
_ [extendedSize: bsiToSize[nhp.blockSizeIndex],
normalHeader: [blockSizeIndex: bsiEscape]];
AllocatorOps.FreeMediumSizedHeapObject[LOOPHOLE[nhp, DFHeaderP]];
};
};  -- end FreeHeapObject


GetSystemZone: PUBLIC SAFE PROC RETURNS[ZONE] =
TRUSTED{RETURN[systemZone]};

GetPermanentZone: PUBLIC SAFE PROC RETURNS[ZONE] =
TRUSTED{RETURN[permanentZone]};

TrimSystemZone: PUBLIC SAFE PROC = TRUSTED{NULL};

NewObject: PUBLIC PROC[type: SafeStorage.Type, size: CARDINAL, zone: ZONE _ NIL]
RETURNS[ans: REF _ NIL] = {
IF zone = NIL THEN zone _ systemZone;
IF zone = systemZone THEN ans _ NewSystemObject[NIL, size, type]
ELSE IF zone = permanentZone THEN ans _ NewPermanentObject[NIL, size, type]
ELSE ERROR;
};

ValidateRef: PUBLIC ENTRY PROC[ref: REF] = {
ENABLE UNWIND => NULL;
IF NOT IsValidRef[LOOPHOLE[ref, LONG POINTER]]
THEN RETURN WITH ERROR InvalidRef[ref];
};

IsValidRef: PUBLIC --INTERNAL-- PROC[p: LONG POINTER] RETURNS[BOOL] = {
qi: QuantumIndex;
IF p = NIL THEN RETURN[TRUE];
IF LOOPHOLE[p, LONG CARDINAL] > LastAddress
OR NOT quantumMap[qi _ LPToQI[p]] THEN RETURN[FALSE];
UNTIL qi = FIRST[QuantumIndex] OR NOT quantumMap[qi-1] DO qi _ qi-1 ENDLOOP;
FOR hp: HeaderP _ QIToLP[qi], hp + BlockSize[hp]
UNTIL LOOPHOLE[hp, LONG CARDINAL] > LOOPHOLE[p, LONG CARDINAL]
DO
r: LONG POINTER
= IF IsExtendedBlock[hp]
THEN hp + SIZE[ExtendedHeader] ELSE hp + SIZE[NormalHeader];
IF p = r THEN {
nhp: NHeaderP _ REFToNHP[LOOPHOLE[r, REF]];
IF nhp.type # SafeStorage.nullType THEN RETURN[TRUE] ELSE RETURN[FALSE];
};
ENDLOOP;
RETURN[FALSE];
};

NewSystemObject:
--PUBLIC--PROC[self: Zone, size: CARDINAL, type: SafeStorage.Type]
RETURNS[r: REF] = {
realSize: INT _ size;
IF (r _ RCMicrocodeOps.Allocate[size, type]) = NIL 
THEN {  -- medium-sized or large object
realSize _ QuantizedSize[size];
IF IsLargeRealSize[realSize]
THEN r _ LOOPHOLE
			[CreateLargeObject
				[type: type, size: realSize, permanent: FALSE, counted: TRUE],
			 REF]
ELSE   -- medium-sized object.
WHILE (r _ LOOPHOLE[CreateMediumSizedObject
							[size: realSize, type: type,
							 roverP: @msRover], REF]) = NIL
DO ExpandDoubleFreeList
	[realSize: realSize, permanent: TRUE,
	 varRover: @msRover, counted: TRUE];
ENDLOOP;
};
StorageAccounting.nObjectsCreated _ StorageAccounting.nObjectsCreated + 1;
StorageAccounting.ConsiderCollection[size, IF takingStatistics THEN realSize ELSE size];
IF checking THEN {
nhp: NHeaderP = REFToNHP[r];
IF NOT nhp.inZCT
OR nhp.f
OR nhp.rcOverflowed
OR nhp.refCount # 0
OR nhp.type # type
OR UsableWords[nhp] < size
THEN ERROR;
};
};  -- end NewSystemObject

ExpandNormalFreeList: PUBLIC PROC[bsi: BlockSizeIndex] = {
qi: QuantumIndex;
qc: QuantumCount;
druthers: QuantumCount = WordsToQC[Lcm[bsiToSize[bsi], wordsPerQuantum]];
first: FNHeaderP _ NIL;
last: FNHeaderP;
next: FNHeaderP;
incr: NAT = bsiToSize[bsi];
[qi, qc]
_ GetQuanta[
desired: druthers,
needed: druthers,  -- (bsiToSize[bsi]-1)/wordsPerQuantum + 1
permanent: TRUE
];
last _ LOOPHOLE[QIToLP[qi], FNHeaderP];
next _ LOOPHOLE[QIToLP[qi+qc], FNHeaderP];
Clear[last, QCToWords[qc]];
FOR fnhp: FNHeaderP _ last, fnhp + incr UNTIL fnhp = next
DO
fnhp.fnh _ [blockSizeIndex: bsi];
fnhp.nextFree _ first;
first _ fnhp;
ENDLOOP;
PutQuantaOnNormalFreeList[bsi, qi, qc, first, last];
};

PutQuantaOnNormalFreeList:  
ENTRY PROC[
bsi: BlockSizeIndex, qi: QuantumIndex,
qc: QuantumCount, first, last: FNHeaderP] = {
ENABLE UNWIND => NULL;
IF checking
AND Basics.BITAND[Basics.LowHalf[LOOPHOLE[first, LONG CARDINAL]], 1] # 0
THEN ERROR;
RCMicrocodeOps.InsertQuanta[bsi, first, last];
StuffQMapRange[qi, qc];
};


NewPermanentObject:
--PUBLIC--PROC[self: Zone, size: CARDINAL, type: SafeStorage.Type]
RETURNS[r: REF] = {
realSize: INT;
IF IsSmallRequestedSize[size]
THEN {  -- small object
bsi: BlockSizeIndex = sizeToBSI[size];
realSize _ bsiToSize[bsi];
WHILE (r _ LOOPHOLE[CreateMediumSizedObject
							[size: realSize, type: type,
							 roverP: @permRover], REF]) = NIL
DO ExpandDoubleFreeList
	[realSize: realSize, permanent: TRUE,
	 varRover: @permRover, counted: TRUE];
ENDLOOP;
}
ELSE {  -- medium-sized or large object
realSize _ QuantizedSize[size];
IF IsLargeRealSize[realSize]
THEN r _ LOOPHOLE
			[CreateLargeObject
				[type: type, size: realSize, permanent: TRUE, counted: TRUE],
			 REF]
ELSE   -- medium-sized object.
WHILE (r _ LOOPHOLE[CreateMediumSizedObject
							[size: realSize, type: type,
							 roverP: @permRover], REF])
= NIL
DO ExpandDoubleFreeList
	[realSize: realSize, permanent: TRUE,
	 varRover: @permRover, counted: TRUE];
ENDLOOP;
};
StorageAccounting.nObjectsCreated _ StorageAccounting.nObjectsCreated + 1;
StorageAccounting.ConsiderCollection
[size, IF takingStatistics THEN realSize ELSE size];
IF checking THEN {
nhp: NHeaderP = REFToNHP[r];
IF NOT nhp.inZCT
OR nhp.f
OR nhp.rcOverflowed
OR nhp.refCount # 0
OR nhp.type # type
OR UsableWords[nhp] < size
THEN ERROR;
};
RETURN[r];
};

FreeSystemObject: PROC[self: Zone, object: REF ANY] = {
NULL;  -- XXX RCMapWalkerImpl.FreeCollectibleObject[object];
};

CreateMediumSizedObject:
ENTRY PROC
[size: NAT, type: SafeStorage.Type, roverP: LONG POINTER TO--VAR-- Rover]
RETURNS[p: LONG POINTER _ NIL] = {ENABLE UNWIND => NULL;
p _ DoCreateMediumSizedObject[size, type, roverP, TRUE];
};

DoCreateMediumSizedObject:
PUBLIC --INTERNAL-- PROC
[size: NAT, type: SafeStorage.Type, roverP: LONG POINTER TO--VAR-- Rover, counted: BOOL]
RETURNS[p: LONG POINTER _ NIL] = {
rover: Rover _ roverP^;
first: DFHeaderP _ rover;
freeBlockLength, excess: INT;
nhp: NHeaderP _ NIL;

UNTIL (freeBlockLength _ ExtendedBlockSize[@rover.eh]) >= size
DO
roverP^ _ rover _ rover.nextFree;
IF rover = first THEN RETURN  -- no free block is large enough
ENDLOOP;
IF (excess _ freeBlockLength - size) >= size
OR IsLargeRealSize[freeBlockLength]
THEN {  -- split the block
IF checking AND excess < SIZE[normal free Header] THEN ERROR;
IF counted AND IsSmallRealSize[excess] THEN {
frag: DFHeaderP = rover;
roverP^ _ frag.nextFree;
frag.nextFree.prevFree _ frag.prevFree;
frag.prevFree.nextFree _ frag.nextFree;
DoFreeNormalFragment[frag, excess];
}
ELSE --change the size of the free block--
IF rover.eh.sizeTag = pages
THEN {
IF excess < LAST[CARDINAL]
THEN {
rover.eh.sizeTag _ words;
rover.eh.extendedSize _ excess;
}
ELSE {  -- excess is large
IF excess MOD PrincOps.wordsPerPage # 0 THEN {
ERROR;  -- XXX not implemented yet (I'm getting sick of this)
};
rover.eh.extendedSize _ excess/PrincOps.wordsPerPage;
};
}
ELSE {rover.eh.extendedSize _ excess; rover.eh.sizeTag _ words};
rover _ LOOPHOLE[rover + excess];
LOOPHOLE[rover, EHeaderP]^
_ [extendedSize: size, normalHeader: [blockSizeIndex: bsiEscape]];
}  --end case of excess >= size OR IsLargeRealSize[freeBlockLength]
ELSE { -- remove the block from the free list without splitting it
rover.nextFree.prevFree _ rover.prevFree;
roverP^ _ rover.prevFree.nextFree _ rover.nextFree;
rover.nextFree _ rover.prevFree _ NIL;  -- CLEAR IT
size _ freeBlockLength;
};
nhp _ IF IsSmallRealSize[size]
THEN LOOPHOLE[MakeNormalFragment[rover, size].fnhp, NHeaderP]
ELSE DFHPToNHP[rover];
nhp.type _ type;
p _ nhp+SIZE[NormalHeader];  -- here for the conservative scan
IF counted THEN RCMicrocodeOps.CreateRef[nhp];
};  -- end DoCreateMediumSizedObject

CreateLargeObject:
PROC[type: SafeStorage.Type, size: INT, permanent: BOOL, counted: BOOL]
RETURNS[p: LONG POINTER _ NIL] = {
qi: QuantumIndex;
qc: QuantumCount;
druthers: QuantumCount = WordsToQC[size];
ehp: EHeaderP;
IF checking AND size MOD wordsPerQuantum # 0 THEN ERROR;
[qi, qc] _ GetQuanta[desired: druthers, needed: druthers, permanent: permanent];
ehp _ LOOPHOLE[QIToLP[qi], EHeaderP];
IF counted THEN Clear[ptr: ehp, size: QCToWords[qc]];
ehp^ _ [
sizeTag: pages,
extendedSize: QCToPages[qc],
normalHeader: [blockSizeIndex: bsiEscape, type: type]
];
p _ ehp + SIZE[ExtendedHeader];  -- here for the conservative scan
IF counted THEN DoCreateLargeObject[qi, qc, ehp, type];
};

DoCreateLargeObject: ENTRY PROC[--belongs in the quantumMap monitor
qi: QuantumIndex, qc: QuantumCount, ehp: EHeaderP, type: SafeStorage.Type] = {
ENABLE UNWIND => NULL;
RCMicrocodeOps.CreateRef[EHPToNHP[ehp]];
StuffQMapRange[qi, qc];
};

FreeObject: PUBLIC PROC[nhp: NHeaderP] = {
realSize: INT;
IF checking THEN
IF nhp.inZCT
OR nhp.f
OR nhp.rcOverflowed
OR nhp.refCount # 0
OR nhp.type = SafeStorage.nullType
THEN ERROR;
StorageAccounting.nObjectsReclaimed _ StorageAccounting.nObjectsReclaimed + 1;
IF RCMicrocodeOps.Free[nhp].success
THEN realSize _ bsiToSize[nhp.blockSizeIndex]
ELSE {  -- large or medium-sized object or extended header for some other reason
ehp: EHeaderP = NHPToEHP[nhp];
realSize _ ExtendedBlockSize[ehp];
IF IsLargeRealSize[realSize]
THEN {
IF checking
AND (realSize MOD wordsPerQuantum # 0)
AND (LOOPHOLE[ehp, INT] MOD wordsPerQuantum # 0)
AND NOT IsFullQMapRange[qi: LPToQI[ehp], qc: WordsToQC[realSize]]
THEN ERROR;
ClearQMapRange[qi: LPToQI[ehp], qc: WordsToQC[realSize]];
VM.Free[
[page: VM.PageNumberForAddress[ehp],
 count: VM.PagesForWords[realSize]
]];
}
ELSE IF IsMediumRealSize[realSize] THEN {  -- medium-sized object.
[] _ PrincOpsUtils.ZERO[ehp + SIZE[ExtendedHeader],
						  realSize - SIZE[ExtendedHeader]];
FreeMediumSizedObject[LOOPHOLE[ehp, DFHeaderP]];
}
ELSE FreeNormalFragment[ehp, realSize];
};
StorageAccounting.nWordsReclaimed
_ StorageAccounting.nWordsReclaimed + realSize;
};  -- end FreeObject
TAndSFreeObject: PUBLIC --INTERNAL-- PROC[nhp: NHeaderP] = {
StorageAccounting.nObjectsReclaimed _ StorageAccounting.nObjectsReclaimed + 1;
IF NOT RCMicrocodeOps.FREEPLEASE[nhp].success
THEN {-- large or medium-sized object or extended header for some other reason
ehp: EHeaderP = NHPToEHP[nhp];
realSize: INT _ ExtendedBlockSize[ehp];
StorageAccounting.nWordsReclaimed
_ StorageAccounting.nWordsReclaimed + realSize;
IF IsLargeRealSize[realSize]
THEN {
IF checking
AND (realSize MOD wordsPerQuantum # 0)
AND (LOOPHOLE[ehp, INT] MOD wordsPerQuantum # 0)
AND NOT IsFullQMapRangeInternal[qi: LPToQI[ehp],
										qc: WordsToQC[realSize]]
THEN ERROR;
ClearQMapRangeInternal[qi: LPToQI[ehp], qc: WordsToQC[realSize]];
VM.Free[
[page: VM.PageNumberForAddress[ehp],
 count: VM.PagesForWords[realSize]
]];
}
ELSE IF IsMediumRealSize[realSize] THEN {  -- medium-sized object.
[] _ PrincOpsUtils.ZERO[ehp + SIZE[ExtendedHeader],
						  realSize - SIZE[ExtendedHeader]];
DoFreeMediumSizedObject[LOOPHOLE[ehp, DFHeaderP], msRover];
}
ELSE TAndSDoFreeNormalFragment[ehp, realSize];
};
};  -- end TAndSFreeObject

FreeNormalFragment: ENTRY PROC[p: LONG POINTER, realSize: NAT] = {
ENABLE UNWIND => NULL;
DoFreeNormalFragment[p, realSize];
};


DoFreeNormalFragment: --INTERNAL--PROC[p: LONG POINTER, realSize: NAT] = {
bsi: BlockSizeIndex;
fnhp: FNHeaderP;
[fnhp, bsi] _ MakeNormalFragment[p, realSize];
RCMicrocodeOps.DoFREE[fnhp, bsi];
};

TAndSDoFreeNormalFragment:
--INTERNAL--PROC[p: LONG POINTER, realSize: NAT] = {
bsi: BlockSizeIndex;
fnhp: FNHeaderP;
[fnhp, bsi] _ MakeNormalFragment[p, realSize];
--********
fnhp.fnh.type _ SafeStorage.nullType;  -- mark the object as free
fnhp.nextFree _ ZCT.zct.bsiToFreeList[bsi];
ZCT.zct.bsiToFreeList[bsi] _ fnhp;
--********
};

MakeNormalFragment:
--INTERNAL-- PROC[p: LONG POINTER, realSize: NAT]
RETURNS[fnhp: FNHeaderP _ NIL, rbsi: BlockSizeIndex _ 0] = {
bsi: BlockSizeIndex _ sizeToBSI[realSize - SIZE[NormalHeader]];
IF checking AND bsiToSize[bsi] < realSize THEN ERROR;
PrincOpsUtils.ZERO[p, realSize];
IF bsiToSize[bsi] = realSize
THEN {  -- make it a small block with a normal header
nhp: NHeaderP _ LOOPHOLE[p, NHeaderP];
nhp^ _ [blockSizeIndex: bsi];
fnhp _ LOOPHOLE[nhp, FNHeaderP];
rbsi _ bsi;
}
ELSE { -- bsiToSize[bsi] > realSize
ehp: EHeaderP = LOOPHOLE[p, EHeaderP];
ehp^ _ [extendedSize: realSize, normalHeader: [blockSizeIndex: bsiEscape]];
IF checking
AND (bsi = FIRST[BlockSizeIndex] OR bsiToSize[bsi-1] > realSize)
THEN ERROR;
fnhp _ LOOPHOLE[@ehp.normalHeader, FNHeaderP];
rbsi _ bsi - 1;
};
};

FreeMediumSizedObject: ENTRY PROC[ptr: DFHeaderP] = {
ENABLE UNWIND => NULL;
DoFreeMediumSizedObject[ptr, msRover];
};

FreeNewMediumSizedObject: ENTRY PROC
[ptr: DFHeaderP,
 varRover: LONG POINTER TO Rover,
 qi: QuantumIndex,
 qc: QuantumCount] = {
ENABLE UNWIND => NULL;
DoFreeMediumSizedObject[ptr, varRover^];
StuffQMapRange[qi, qc];  -- stuff the quantum map
};

DoFreeMediumSizedObject:
PUBLIC --INTERNAL-- PROC[ptr: DFHeaderP, rover: Rover] = {
ptr.eh.normalHeader.type _ SafeStorage.nullType;
ptr.nextFree _ rover.nextFree;
ptr.prevFree _ rover;
rover.nextFree.prevFree _ ptr;
rover.nextFree _ ptr;
};
EnterAndCallBack: PUBLIC ENTRY PROC[proc: PROC] = {
ENABLE UNWIND => NULL;
proc[];
};


AllocateTrap: PUBLIC PROC[size: CARDINAL, type: SafeStorage.Type]
RETURNS[r: REF] = {
state: PrincOps.StateVector;
state _ STATE;   -- incantation
SELECT (IF RCMicrocodeOps.rcMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0)
FROM
0 => r _ RCMicrocodeOps.SoftwareAllocate[size, type];   -- no microcode
2 => { -- uCode is disabled; someone is inside this monitor
p: PROC[size: CARDINAL, type: SafeStorage.Type] =
MACHINE CODE{PrincOps.zRET};
ZCT.Enter[];
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state;   -- incantation
p[size, type];
};
4 => { -- zctFull
p: PROC[size: CARDINAL, type: SafeStorage.Type] =
MACHINE CODE{PrincOps.zRET};
ZCT.ExpandZCT[];
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state;   -- incantation
p[size, type];
};
6 => { -- expandNormalFreeList
p: PROC[size: CARDINAL, type: SafeStorage.Type] =
MACHINE CODE{PrincOps.zRET};
ExpandNormalFreeList[sizeToBSI[size]];
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state;   -- incantation
p[size, type];
};
ENDCASE => ERROR;
TrapSupport.BumpPC[2];                -- length of opcode
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state;   -- incantation
};

FreeTrap: PUBLIC PROC[nhp: NHeaderP] RETURNS[success: BOOL] = {
state: PrincOps.StateVector;
state _ STATE;   -- incantation
SELECT (IF RCMicrocodeOps.rcMicrocodeExists THEN TrapSupport.GetTrapParam[] ELSE 0)
FROM
0 => success _ RCMicrocodeOps.SoftwareFree[nhp];   -- no microcode
2 => { -- uCode is disabled; someone is inside this monitor
p: PROC[nhp: NHeaderP] = MACHINE CODE{PrincOps.zRET};
ZCT.Enter[];
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state;   -- incantation
p[nhp];
};
ENDCASE => ERROR;
TrapSupport.BumpPC[2];                -- length of opcode
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state;   -- incantation
};



GetReferentType: PUBLIC SAFE PROC[ref: REF ANY]
RETURNS[type: SafeStorage.Type] = TRUSTED{
RETURN[GetCanonicalReferentType[ref]]
};

GetCanonicalReferentType: PUBLIC SAFE PROC[ref: REF ANY]
RETURNS[type: SafeStorage.Type] = TRUSTED{
IF ref = NIL
THEN RETURN[SafeStorage.nullType]
ELSE RETURN[REFToNHP[ref].type]
};

GetCanonicalReferentTypeTrap: PUBLIC PROC[ref: REF ANY]
RETURNS[type: SafeStorage.Type] = {
state: PrincOps.StateVector;
kludge: LONG CARDINAL;
state _ STATE;   -- incantation
kludge _ 0;
type _ GetCanonicalReferentType[ref];
TrapSupport.BumpPC[2];
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state   -- incantation
};

IsReferentType: PUBLIC SAFE PROC[ref: REF ANY, type: SafeStorage.Type]
RETURNS[BOOL] = TRUSTED {
RETURN[SafeStorage.GetCanonicalType[type] = GetCanonicalReferentType[ref]];
};

NarrowRef: PUBLIC SAFE PROC[ref: REF, type: SafeStorage.Type]
RETURNS[REF] = TRUSTED {
IF ref = NIL THEN RETURN[NIL]
ELSE IF SafeStorage.GetCanonicalType[type] = GetCanonicalReferentType[ref]
THEN RETURN[ref]
ELSE ERROR SafeStorage.NarrowRefFault[ref, type];
};

StuffQMapRange: INTERNAL PROC[qi: QuantumIndex, qc: QuantumCount] = {
nQMapEntries _ nQMapEntries + qc;
FOR i: QuantumIndex _ qi, i+1 UNTIL i = qi + qc
DO quantumMap[i] _ TRUE ENDLOOP;
};

ClearQMapRange: ENTRY PROC[qi: QuantumIndex, qc: QuantumCount] = {
ENABLE UNWIND => NULL;
ClearQMapRangeInternal[qi, qc];
};

ClearQMapRangeInternal: --INTERNAL--PROC[qi: QuantumIndex, qc: QuantumCount] = {
nQMapEntries _ nQMapEntries - qc;
FOR i: QuantumIndex _ qi, i+1 UNTIL i = qi + qc
DO quantumMap[i] _ FALSE ENDLOOP;
};

IsFullQMapRange: ENTRY PROC[qi: QuantumIndex, qc: QuantumCount]
RETURNS[ans: BOOL _ TRUE] = {
ENABLE UNWIND => NULL;
RETURN[IsFullQMapRangeInternal[qi, qc]]};

IsFullQMapRangeInternal: --INTERNAL--PROC[qi: QuantumIndex, qc: QuantumCount]
RETURNS[ans: BOOL _ TRUE] = {
FOR i: QuantumIndex _ qi, i+1 UNTIL i = qi + qc
DO IF NOT quantumMap[i] THEN RETURN[FALSE] ENDLOOP;
};

IsClearQMapRange: ENTRY PROC[qi: QuantumIndex, qc: QuantumCount]
RETURNS[ans: BOOL _ TRUE] = {
ENABLE UNWIND => NULL;
FOR i: QuantumIndex _ qi, i+1 UNTIL i = qi + qc
DO IF quantumMap[i] THEN RETURN[FALSE] ENDLOOP;
};

NQMapEntries: ENTRY PROC RETURNS[ans: INT _ 0] = {
ENABLE UNWIND => NULL;
FOR i: QuantumIndex IN QuantumIndex
DO IF quantumMap[i] THEN ans _ ans + 1 ENDLOOP;
};


QuantizedSize: PROC[size: CARDINAL] RETURNS[INT] = {
n: NAT = SIZE[NormalHeader];  -- minimum overhead
e: NAT = SIZE[ExtendedHeader] - n;  -- additional overhead for extended headers
IF checking AND size = 0 THEN ERROR;
RETURN[
SELECT size FROM
<= 22B => ((size-1+n)/2 + 1)*2,  -- 4, 6, 10B, 12B, 14B, 16B, 20B, 22B, 24B
<= 42B => ((size-1+n)/4B + 1)*4B,  -- 30B, 34B, 40B, 44B
<= 106B => ((size-1+n)/10B + 1)*10B,  -- 50B, 60B, 70B, 100B, 110B
<= 216B => ((size-1+n)/20B + 1)*20B,  -- 120B, 140B, 160B, 200B, 220B 
<= 436B => ((size-1+n)/40B + 1)*40B,  -- 240B, 300B, 340B, 400B, 440B
<= 1076B => ((size-1+n)/100B + 1)*100B,  -- 500B, 600B, 700B, 1000B, 1100B
<= 2174B => ((size-1+n+e)/200B + 1)*200B,  -- 1200B, 1400B, 1600B, 2000B, 2200B
ENDCASE => ((LONG[size]-1+n+e)/400B + 1)*400B
];
};

BlockSize: PUBLIC PROC[hp: HeaderP] RETURNS[INT] = {
nhp: NHeaderP = LOOPHOLE[hp, NHeaderP];
IF nhp.blockSizeIndex = bsiEscape
THEN RETURN[ExtendedBlockSize[LOOPHOLE[hp, EHeaderP]]]
ELSE RETURN[bsiToSize[nhp.blockSizeIndex]];
};

IsExtendedBlock: PROC[hp: HeaderP] RETURNS[BOOL] = {
RETURN[LOOPHOLE[hp, NHeaderP].blockSizeIndex = bsiEscape];
};

ExtendedBlockSize: PROC[ehp: EHeaderP] RETURNS[INT] = {
RETURN[
SELECT ehp.sizeTag FROM
words => LONG[ehp.extendedSize],
pages => LONG[ehp.extendedSize] * VM.wordsPerPage,
bsi => LONG[bsiToSize[ehp.extendedSize]],
ENDCASE => ERROR];
};

UsableWords: PROC[nhp: NHeaderP] RETURNS[INT] = {
IF nhp.blockSizeIndex # bsiEscape
THEN RETURN[bsiToSize[nhp.blockSizeIndex] - SIZE[NormalHeader]]
ELSE RETURN[ExtendedBlockSize[NHPToEHP[nhp]] - SIZE[ExtendedHeader]];
};

IsLargeRealSize: PROC[size: INT] RETURNS[BOOL] = {
RETURN[size >= minLargeBlockRealSize];
};

IsMediumRealSize: PROC[size: INT] RETURNS[BOOL] = {
RETURN[maxSmallBlockRealSize < size AND size< minLargeBlockRealSize];
};

IsSmallRealSize: PROC[size: INT] RETURNS[BOOL] = {
RETURN[size <= maxSmallBlockRealSize];
};

IsSmallRequestedSize: PROC[size: CARDINAL] RETURNS[BOOL] = {
RETURN[size <= maxSmallBlockSize];
};

QIToLP: PROC[qi: QuantumIndex] RETURNS[LONG POINTER] = {
RETURN[LOOPHOLE[LONG[qi]*wordsPerQuantum, LONG POINTER]];
};

LPToQI: PROC[ptr: LONG POINTER] RETURNS[QuantumIndex] = {
RETURN[LOOPHOLE[ptr, LONG CARDINAL] / wordsPerQuantum];
};

QCToWords: PROC[qc: QuantumCount] RETURNS[INT] = {
RETURN[LONG[qc]*wordsPerQuantum];
};

WordsToQC: PROC[words: INT] RETURNS[QuantumCount] = {
RETURN[words/wordsPerQuantum];
};

QCToPages: PROC[qc: QuantumCount] RETURNS[INT] = {
RETURN[LONG[qc]*pagesPerQuantum];
};

EHPToNHP: PROC[ehp: EHeaderP] RETURNS[NHeaderP] = {
RETURN[LOOPHOLE[ehp + SIZE[ExtendedHeader] - SIZE[NormalHeader], NHeaderP]];
};

NHPToEHP: PROC[nhp: NHeaderP] RETURNS[EHeaderP] = {
RETURN[LOOPHOLE[nhp + SIZE[NormalHeader] - SIZE[ExtendedHeader], EHeaderP]];
};

DFHPToNHP: PROC[dfhp: DFHeaderP] RETURNS[NHeaderP] = {
RETURN[LOOPHOLE[dfhp + SIZE[ExtendedHeader] - SIZE[NormalHeader], NHeaderP]];
};

Clear: PROC[ptr: LONG POINTER, size: INT] = {
WHILE size > LAST[CARDINAL]
DO [] _ PrincOpsUtils.ZERO[ptr, LAST[CARDINAL]];
 size _ size - LAST[CARDINAL];
 ptr _ ptr + LAST[CARDINAL];
ENDLOOP;
[] _ PrincOpsUtils.ZERO[ptr, Basics.LowHalf[size]];
};

Lcm: PROC[m,n: INT] RETURNS[INT] = {RETURN[(m*n)/Gcd[m,n]]};

Gcd: PROC[m,n: INT] RETURNS[INT] = {
DO
r: INT = m MOD n;
IF r = 0 THEN RETURN[n];
m _ n;
n _ r;
ENDLOOP;
};

ExpandDoubleFreeList:
PROC[realSize: INT, permanent: BOOL, varRover: LONG POINTER TO Rover, counted: BOOL] = {
qi: QuantumIndex;
qc: QuantumCount;
ehp: EHeaderP;
desired: QuantumCount = WordsToQC[Lcm[realSize, wordsPerQuantum]];
[qi, qc] _ GetQuanta[desired: desired, needed: desired, permanent: permanent];
realSize _ QCToWords[qc];
ehp _ LOOPHOLE[QIToLP[qi], EHeaderP];
Clear[ehp, realSize];
ehp^ _ [extendedSize: realSize, normalHeader: [blockSizeIndex: bsiEscape]];
IF counted
THEN FreeNewMediumSizedObject[LOOPHOLE[ehp, DFHeaderP], varRover, qi, qc]
ELSE AllocatorOps.FreeMediumSizedHeapObject[LOOPHOLE[ehp, DFHeaderP]];
};

GetQuanta: PROC[desired, needed: QuantumCount, permanent: BOOL _ FALSE]
RETURNS[qi: QuantumIndex, qc: QuantumCount] = {
qc _ desired;
DO {
qi _ VM.Allocate
[count: qc * pagesPerQuantum, alignment: logPagesPerQuantum, in64K: permanent
! VM.CantAllocate =>
{IF bestInterval.count >= needed * pagesPerQuantum
THEN {qc _ needed; RETRY}
ELSE GOTO noVM}
].page/pagesPerQuantum;
EXIT;
EXITS noVM => ERROR InsufficientVM;
};
ENDLOOP;
};
Initialize: PUBLIC PROC = {
systemZone _ LOOPHOLE[NewSystemObject[NIL, SIZE[ZoneObject], CODE[ZoneObject]], ZONE];
LOOPHOLE[systemZone, Zone]^ _ [new: NewSystemObject, free: FreeSystemObject];
LOOPHOLE[@PrincOps.SD[RTSD.sSystemZone], POINTER TO LONG POINTER]^
_ LOOPHOLE[systemZone, LONG POINTER];
permanentZone
_ LOOPHOLE[NEW[ZoneObject _ [new: NewPermanentObject, free: FreeSystemObject]]];
};

Reset: PUBLIC PROC = {
msRover _ @msRoot;
msRover.nextFree _ @msRoot;
msRover.prevFree _ @msRoot;
permRover _ @permRoot;
permRover.nextFree _ @permRoot;
permRover.prevFree _ @permRoot;
};


FOR i: QuantumIndex IN QuantumIndex DO quantumMap[i] _ FALSE ENDLOOP;

{ --Initialize bsiToSize and sizeToBSI
oldQS: NAT _ 0;
nextBSI: BlockSizeIndex _ 0;
FOR size: --requested-- [0..maxSmallBlockSize] IN [0..maxSmallBlockSize]
DO
qs: NAT = QuantizedSize[IF size = 0 THEN 1 ELSE size];
IF qs # oldQS THEN {  -- new size and bsi
IF nextBSI = bsiEscape THEN ERROR;
oldQS _ qs;
bsiToSize[nextBSI] _ qs;
nextBSI _ nextBSI + 1;
};
sizeToBSI[size] _ nextBSI - 1;
ENDLOOP;
};


END.

JAllocatorImpl.Mesa
last edited November 9, 1983 8:34 am by Paul Rovner
protects the "medium-sized" free list and rover, the "permanent" free list and rover and the quantumMap
ERRORS
CONSTANTS
VARIABLES and their INITIALIZATION

NOTE: the declaration sequence below is EXTREMELY DELICATE.  Order of the declarations and their initilization is important.

Support for the systemUZone
Support for both uncounted and counted storage

bsiToSize maps a bsi to a quantized size (including overhead) for small block sizes

sizeToBSI maps a requested size <= maxSmallBlockSize (not including overhead) to a bsi
Support for counted storage only

the "medium-sized" free list (msRover): a doubly-linked ring
dummy entry; the "medium-sized" free list never has NIL ptrs

the "permanent" free list (permRover): a doubly-linked ring
dummy entry; the "permanent" free list never has NIL ptrs

This has a flag for each page in VM, TRUE iff the page is assigned to a counted ZONE.

Statistics

END: VARIABLES and their INITIALIZATION

PROCEDURES
Support for uncounted storage

Public access to uncounted storage

UNCOUNTED ZONE procs
Referenced only via zhs, The "systemUZone"
Referenced only via zhs, The "systemUZone"
medium-sized or small object.
Support for counted storage

Public access to counted storage
Start parsing at the beginning of the first quantum in this run
ZONE procs

Referenced from systemZone and called from NewObject and Initialize
size DOES NOT INCLUDE overhead
Called from Allocate and AllocateTrap.
smallest x s.t. bsiToSize[bsi] divides QCToWords[x]
smallest x s.t. (QCToWords[x]) >= bsiToSize[bsi]
 WAS fnhp^ _ [fnh: [blockSizeIndex: bsi], nextFree: first];  ??
Called only from ExpandNormalFreeList
atomic: stuffing the quantum map and expansion of the free list.  Should be in the quantumMap monitor
now stuff the QMap

Called only from NewSystemObject.
CreateNormalObject: ENTRY PROC[bsi: BlockSizeIndex, type: SafeStorage.Type]
RETURNS[r: REF _ NIL] = {ENABLE UNWIND => NULL;
fnhp: FNHeaderP;
IF (fnhp _ bsiToFreeList[bsi]) = NIL THEN RETURN;	
IF checking
AND Basics.BITAND
		[Basics.LowHalf[LOOPHOLE[fnhp.nextFree, LONG CARDINAL]], 1] # 0
THEN ERROR;
bsiToFreeList[bsi] _ fnhp.nextFree;
fnhp.nextFree _ NIL;  -- CLEAR IT
IF checking THEN {
nhp: NHeaderP = @fnhp.fnh;
IF nhp.inZCT
OR nhp.maybeOnStack
OR nhp.f
OR nhp.rcOverflowed
OR nhp.refCount # 0
OR nhp.type # SafeStorage.nullType
THEN ERROR;
};
fnhp.fnh.type _ type;
r _ NHPToREF[@fnhp.fnh];  -- gotta have a ref on the stack
RCMicrocodeOps.CreateRef[@fnhp.fnh];
};
Referenced from permanentZone and called from NewObject
size DOES NOT INCLUDE overhead
Referenced from systemZone and permanentZone
Procs called from ZONE procs and UNCOUNTED ZONE procs

Called from NewSystemObject and NewPermanentObject
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 from CreateMediumSizedObject and UnsafeAllocatorImpl.CreateMediumSizedHeapObject
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.
Here with a large enough free block; rover points to it
this OR clause is here in case the new object gets reclaimed to avoid thinking it a LargeObject and therefore assuming it page-aligned and a page-size multiple, hence VM.Free-able.  Large objects are allocated above this level.
get the new object from the end of the free block
says here that this can't happen
change the size of the free block 
move the excess block to a normal free list
can't be equal 'cause excess is even
done dealing with the fragment
Called from NewHeapObject, NewSystemObject and NewPermanentObject
Called only from CreateLargeObject
Procs called by the reclaimer and TraceAndSweepImpl



Called only by FreeObject
stick this block (which may be extended) on the specified (small-sized) free list
FreeNormalSizedObject: ENTRY PROC[fnhp: FNHeaderP, bsi: BlockSizeIndex] = {
ENABLE UNWIND => NULL;
DoFreeNormalSizedObject[fnhp, bsi];
};
Called only by FreeObject
called by DoFreeNormalFragment
DoFreeNormalSizedObject:
INTERNAL PROC[fnhp: FNHeaderP, bsi: BlockSizeIndex] = {
IF checking
AND Basics.BITAND[Basics.LowHalf[LOOPHOLE[fnhp, LONG CARDINAL]], 1] # 0
THEN ERROR;
fnhp.fnh.type _ SafeStorage.nullType;  -- mark the object as free
fnhp.nextFree _ bsiToFreeList[bsi];
bsiToFreeList[bsi] _ fnhp;
};
called by FreeNormalFragment and by CreateMediumSizedObject
RCMicrocodeOps.DoFREE[fnhp, bsi];
called by DoFreeNormalFragment, CreateMediumSizedObject
Returns the bsi s.t. bsiToSize[bsi] <= realSize
Yields bsi s.t. bsiToSize[bsi] >= realSize
unusual size: make an extended block
Called from FreeObject.
Assume header is made
Assume block is cleared
Called only from ExpandDoubleFreeList.
Assume header is made
Assume block is cleared
Called from FreeNewMediumSizedObject, FreeMediumSizedObject, FreeMediumSizedHeapObject, TAndSFreeObject.

Called from TraceAndSweepImpl.
Trap handlers
Support for NARROW; referent types

QuantumMap

Utilities
This is called very early in the (delicate) initialization sequence. It calls nothing.
arg is a requested block size NOT INCLUDING overhead; result is an even, quantized size that INCLUDES OVERHEAD.  Requested sizes > (1100B - SIZE[NormalHeader]) require extended headers. It is not true that the difference between any two quantized sizes is a valid quantized size.
requested sizes > maxSmallBlockSize (1076B) require extended headers
steps of 400B for requested size > (2200B - SIZE[ExtendedHeader]), starting at 2400B
Called from NewHeapObject, NewSystemObject and NewPermanentObject
desired: smallest x s.t. realSize divides QCToWords[x]
needed: (realSize-1)/wordsPerQuantum + 1
OR smallest x s.t. (QCToWords[x]) >= realSize
Called from CreateLargeObject, ExpandNormalFreeList, ExpandDoubleFreeList

END: PROCEDURES

This is called long after this module is started; CODE[mumble] isn't meaningful until then
This is called by the TAndS
START CODE

Initialize the quantum map: needed here because ALL has a bug

The systemUZone (zhs) is now ready for use
Κ) ˜Jš
œ™Jš
œ3™3J˜š
Οk	˜	Jšœ
œΘ˜ΧJšœ
œ‡
˜™
Jšœœ
œ˜Jšœ
œ˜!Jšœ	œ
œ#˜4Jšœœ
œ˜(Jšœœq˜…
Jšœ
œ˜Jšœœ3˜DJšœœΟc ˜=JšœœJ˜aJšœ
œ˜Jšœœ˜(Jšœœ˜Jšœ
œR˜ZJšœ
œ˜!—J˜šœ˜Jš
œg™g—š
˜Jšœk	˜t—š
˜Jš
œJ˜J—J˜Jšœœ
œ˜%˜š
œ™Jšœœœ
˜Jšœœ
œœ
œœ
˜.—J˜™	Jšœ
œœ
˜Jšœœœ
˜J˜Jšœœ$˜>Jšœœ$˜>—J˜™"J™Jšœ$	œ
œB™|J™
procš
œ™š
œH˜HJšœœ
œœ˜2—JšΟbœ	œ
œœ
œ	œ
œ˜DJ˜K˜—™.™Jš
œS™S—šœœ
œ
œ
˜.Jšœœœ˜2J™Jš
œV™V—Jš	œœ
œ
œ"œ˜UJ˜—™ ™Jš
œ<™<š
œ˜Jš
œ<™<Jš
œA˜AJš
œ˜Jš
œ˜Jš
œ˜——š
œ˜J™Jš
œ;™;š
œ˜Jš
œ9™9Jš
œA˜AJš
œ˜Jš
œ˜Jš
œ˜——Jš
œ˜™J™U—Jšœœ œ˜@J˜Jšœœœ
˜Jšœœœ
˜—K™™
K˜Kšœœ˜J™—J˜J™'—K™™
K˜™K™™"J™š
Οn
œœ
œž	œ	œ
œ
˜FJšœœ
œ˜Jšœœ˜4Jš
œ˜J˜—š œœ
œ
œ
	œ
œ˜5Jšœ
œ˜J˜—š
 	œœ
œ	œ
œ˜0Jšœ
˜Jš
œ˜J˜——™˜Kš
œ*™*—š 
œœœ
˜1Jšœœ
œ˜Jšœ
œœœ˜Ašœ˜šœ˜Jšœ4œœ
˜J—š
˜šœB˜Jšœ˜Jšœ!œœ˜F—Jšœ
˜———šœ
œ˜Jšœœ˜%šœ
˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ
œ
˜—J˜—Jšœ˜
Jšœž˜J˜Kš
œ*™*—š œœœ
œ˜<Jšœœ
œ˜6šœ
˜šœ
˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ
œ
˜——šœ˜!šœžH˜PJš
œ˜Jšœ
œ˜'šœ˜šœ˜šœ	˜Jšœœ˜&Jšœœœœ˜0Jšœ
œ;˜BJšœ
œ
˜—šœ˜Jšœœ˜$Jšœœ˜"Jš
œ˜—Jš
œ
˜
—šœ(œ˜FJš
œ™——Jš
œ
˜
—šœž˜šœ˜š
œ/˜/Jš
œ+˜+——Jšœ'œ˜AJ˜——Jšœž˜——J˜—™K™™ J˜š 
œœ
œ
œ
œ
œ˜/Jšœ
œ˜J˜—š œœ
œ
œ
œ
œ˜2Jšœ
œ˜J˜—Jš œœ
œ
œœ
œ˜1J˜š 	œœ
œœœœ
˜PJšœœœ˜Jšœœ
œ˜%Jšœœœ
˜@Jšœ
œœœ
˜KJšœ
œ
˜J˜—J˜š œœ

œœ˜,Jšœ
œœ
˜š
œ
œœœ
œ˜.Jšœ
œ˜'—J˜J˜—š 
œœ
žœ
œœ
œœ
œ˜GJš
œ˜Jš
œœ
œ
œ
œ˜šœ
œœ
œ˜+Jš
œ
œœ
œ
œ˜5—Jšœœœ
œœœ
˜LJš
œ?™?šœ-˜0Jšœ
œœ
œœœ
œ
˜>š
˜šœœ
˜šœœ˜Jšœœœœ˜<——šœœ˜Jšœœœ˜+Jšœ!œ
œ
œœ
œ
œ˜HJ˜——Jšœ
˜—Jšœ
œ˜J˜—J˜—™
™Jš
œC™CJš
œ™—š œ
˜Jšž
œœ˜BJšœœ˜Jšœ
œ˜Jšœ-œ
˜3šœž˜'Jš
œ˜šœ˜šœ˜Jš
œ˜Jšœ,œœœ
˜K—šœž˜šœœ˜+Jš
œ#˜#Jšœœ˜&šœ˜Jšœ!œ
˜&Jšœœ˜%—Jšœ
˜———J˜—Jš
œJ˜JJšœ+œœ
œ˜Xšœ
œ˜Jš
œ˜šœ
œ
˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ
œ
˜—J˜—Jšœž˜˜Jš
œ&™&—š œœ˜:Jš
œ˜Jš
œ˜Jš
œI˜IJšœœ
˜Jš
œ˜Jš
œ˜Jšœœ˜š
œ˜š
œ˜š
œ˜Jš
œ3™3—šœž)˜<Jš
œ0™0—Jš
œ˜Jš
œ˜——Jšœœ˜'Jšœœ˜*Jš
œ˜šœ%œ˜9š
˜Jš
œ!˜!Jš
œ˜Jš
œ?™?Jš
œ
˜
—Jšœ
˜—Jš
œ4˜4Jš
œ˜˜Jš
œ%™%—š œ˜šœ
œ
˜Jš
œe™eJš
œ&˜&Jš
œ-˜-—Jšœ
œœ
˜šœ	˜Jš
œœœœ
œ
˜HJšœ
œ
˜—Jš
œ.˜.Jš
œ™Jš
œ˜Jš
œ˜J˜—J™Jš
œ!™!—š œœ
œ-™KJšœœœœ
œœ
™/Jš
œ™Jšœœ
œ
œ™2šœ	™šœ™Jšœœœ
œ
™A—Jšœ
œ
™—Jš
œ#™#Jšœœž™!šœ
œ™Jš
œ™šœ
™Jšœ™Jšœ™Jšœ™Jšœ™Jšœ ™"Jšœ
œ
™—J™—Jš
œ™Jšœž ™:Jš
œ$™$Jš
œ™—J˜Jš
œ7™7Jš
œ™—š œ
˜Jšž
œœ˜BJšœœ˜Jšœ
œ
˜šœ˜šœž˜Jš
œ&˜&Jš
œ˜šœœ˜+Jš
œ#˜#Jšœœ˜(šœ˜Jšœ!œ
˜&Jšœ!œ˜'—Jšœ
˜—J˜
—šœž˜'Jš
œ˜šœ˜šœ˜Jš
œ˜Jšœ,œœœ
˜J—šœž˜šœœ˜+Jš
œ#˜#šœœ˜"Jšœ˜—šœ˜Jšœ!œ
˜&Jšœ!œ˜'—Jšœ
˜———J˜——Jš
œJ˜Jš
œ$˜$Jšœœœ
œ˜4—šœ
œ˜Jš
œ˜šœ
œ
˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ˜Jšœ
œ
˜—J˜—Jšœ˜
Jš
œ˜—˜Jš
œ,™,—š œœœ
œ˜7Jšœž5˜<Jš
œ˜—J˜—™5™Jš
œ2™2Jšœ5œ™LJš
œ?™?Jš
œ)™)—š œ
˜šœ
˜
Jš
œœ"œ
œ
žœ˜I—Jšœœ
œœœ
œœ
˜8Jšœ2œ˜8J˜—˜Jš
œW™WJšœ5œ™LJš
œ?™?Jš
œ)™)—š œ
˜šœ
žœ
˜Jšœœ"œ
œ
žœœ
˜X—Jšœœ
œœ˜"Jš
œ˜Jš
œ˜Jšœœ
˜Jšœœ
˜J˜šœ9˜>š
˜Jš
œ!˜!Jšœœ
œž ˜>—Jšœ
˜—Jš
œ7™7šœ*˜,šœ!˜#Jš
œγ
™γ
—šœž˜Jš
œ1™1š
œ
œ
œœ
œ
˜=J™ —Jš
œ"™"šœ	œœ˜-Jš
œ+™+Jš
œ˜Jš
œ˜Jš
œ'˜'Jš
œ'˜'Jš
œ#˜#Jš
œ
˜
—šœ
ž%˜*Jšœ˜šœ˜šœ
œ
œ
˜šœ˜Jš
œ$™$Jš
œ˜Jš
œ˜Jš
œ
˜
—šœž˜šœœœ˜.Jšœž5˜=Jš
œ˜—Jš
œ5˜5J˜——Jš
œ
˜
—Jšœ<˜@—Jš
œ™Jšœœ˜!šœ˜Jš
œB˜B—Jšœž@˜C—šœž;˜BJš
œ)˜)Jš
œ3˜3Jšœ"œž˜3Jš
œ˜Jš
œ˜——šœœ˜Jšœ
œ0˜=Jšœ˜—Jš
œ˜Jšœœž!˜>Jšœ	œ˜.Jšœž ˜$J˜Jš
œA™A—šŸœ
˜Jšœœ
œœ
˜GJšœœ
œœ˜"Jš
œ˜Jš
œ˜Jš
œ)˜)Jš
œ˜Jš
œ
œœœ
œ
˜8Jš
œP˜PJšœœ˜%Jšœ	œ&˜5š
œ˜Jš
œ˜Jš
œ˜Jš
œ5˜5Jš
œ˜—Jšœ
œž!˜BJšœ	œ(˜7Jš
œ˜˜Jš
œ"™"—š œœ
œ
ž#˜CJš
œN˜NJšœ
œœ
˜Jš
œ(˜(Jš
œ˜Jš
œ˜——J˜—™3J™š 
œœ
œ˜*Jšœ
œ
˜šœ
˜šœ
˜Jšœ˜Jšœ˜Jšœ˜Jšœ ˜"Jšœ
œ
˜——Jš
œN˜Nšœ!˜#Jšœ)˜-šœžH˜PJš
œ˜Jš
œ"˜"šœ˜šœ˜šœ	˜Jšœœ˜&Jšœœœœ˜0Jšœ
œ:˜AJšœ
œ
˜—Jš
œ9˜9šœ˜Jšœœ˜$Jšœœ˜"Jš
œ˜—Jš
œ
˜
—šœ
œœž˜Bšœœœ˜3Jšœœ˜)—Jšœœ˜0Jš
œ
˜
—Jšœ#˜'—Jš
œ˜——š
œ!˜!Jš
œ/˜/—Jšœž˜J™š œœ
žœ
œ˜<Jš
œN˜Nšœ
œ
œ
˜-šœžH˜NJš
œ˜Jšœ
œ˜'š
œ!˜!Jš
œ/˜/—šœ˜šœ˜šœ	˜Jšœœ˜&Jšœœœœ˜0šœ
œ)˜0Jš
œ"˜"—Jšœ
œ
˜—Jš
œA˜Ašœ˜Jšœœ˜$Jšœœ˜"Jš
œ˜—Jš
œ
˜
—šœ
œœž˜Bšœœœ˜3Jšœœ˜)—Jšœœ˜;Jš
œ
˜
—Jšœ*˜.—Jš
œ˜——Jšœž˜J™Jš
œ™Jš
œQ™Q—š œœ
œ*™KJšœ
œœ
™Jš
œ#™#Jš
œ™—˜Jš
œ™—š œœ
œœ
œœ˜BJšœ
œœ
˜Jš
œ"˜"Jš
œ˜—˜Jš
œ™—š œ
™Jšœ
œ*™7šœ	™Jš
œœœœ
œ
™GJšœ
œ
™—Jšœ'ž™AJš
œ#™#Jš
œ™Jš
œ™—˜Jš
œ;™;—š œžœœ
œœ˜JJš
œ˜Jš
œ˜Jš
œ.˜.Jš
œ!˜!Jš
œ˜—J˜š œ
˜Jš	žœœ
œœ˜4Jš
œ˜Jš
œ˜Jš
œ.˜.Jš
œ
˜
Jš
œ!™!Jšœ'ž˜AJš
œ+˜+Jš
œ"˜"Jš
œ
˜
Jš
œ˜J˜Jšœ ž™7Jš
œ/™/—š œ
˜Jš
žœ
œœ
œœ
˜1Jšœœ˜<šœ+œ˜?Jš
œ*™*—Jšœ
œœ
œ
˜5Jšœœ˜ šœ˜šœž-˜5Jšœœ˜&Jš
œ˜Jšœœ˜ Jš
œ˜J˜
—šœž˜#Jšœžœ™$Jšœœ˜&Jš
œK˜Kšœ	˜Jšœœœ˜@Jšœ
œ
˜—Jšœœ˜.Jš
œ˜J˜——Jš
œ˜˜Jš
œ™Jš
œ™Jš
œ™——š œœ
œ˜5Jšœ
œœ
˜Jš
œ&˜&Jš
œ˜—˜Jš
œ&™&Jš
œ™Jš
œ™—š œœ
˜$Jš
œ˜Jšœœ
œ
œ˜!Jš
œ˜Jš
œ˜Jšœ
œœ
˜Jš
œ(˜(Jšœž˜1Jš
œ˜—˜Jš
œh™h—š œ
˜Jšœ
žœ
œ"˜:Jš
œ0˜0Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜J™Jš
œ™—š
 œœ
œ
œœ˜3Jšœ
œœ
˜Jš
œ˜Jš
œ˜——J˜—™
J˜š œœ
œœ˜AJšœœ˜Jš
œ˜Jšœœž˜šœœ"œœ˜Sš
˜Jšœ8ž˜Gšœž4˜;šœœœ˜1Jšœ
œ˜—J˜Jšœ
œ˜4Jšœ
œ
ž˜%Jš
œ˜J˜—šœž
˜šœœœ˜1Jšœ
œ˜—Jš
œ˜Jšœ
œ˜4Jšœ
œ
ž˜%Jš
œ˜J˜—šœž˜šœœœ˜1Jšœ
œ˜—Jš
œ&˜&Jšœ
œ˜4Jšœ
œ
ž˜%Jš
œ˜J˜—Jšœœ
˜——Jšœ&ž˜9Jšœ
œ˜4Jšœ
œ
ž˜%Jš
œ˜J˜—š
 œœ
œœ
œ˜?Jš
œ˜Jšœœž˜šœœ"œœ˜Sš
˜Jšœ3ž˜Bšœž4˜;Jšœœœ
œ˜5J˜Jšœ
œ˜4Jšœ
œ
ž˜%Jš
œ˜J˜—Jšœœ
˜——Jšœ&ž˜9Jšœ
œ˜4Jšœ
œ
ž˜%Jš
œ˜—J˜—J˜—™"J˜š œœ
œ
œœ
œ
˜/Jšœœ
˜*Jšœ˜%Jš
œ˜J˜—š
 œœ
	œœ
œ
˜8Jšœœ
˜*šœ˜Jšœ
œ˜!Jšœ
œ˜—Jš
œ˜J˜—š
 œœ
œœ
œ
˜7Jšœ˜#Jš
œ˜Jšœœ
œ
˜Jšœœž˜Jš
œ˜Jš
œ%˜%Jš
œ˜Jšœ
œ˜4Jšœ
œ	ž˜$Jš
œ˜—J˜š œœ
œ
œœ
œ˜FJšœ
œœ˜JšœE˜KJš
œ˜J˜—š
 	œœ
œ
œœ˜=Jšœ
œœ˜Jš
œœ
œ
œ
œ
˜Jšœ
œC˜JJšœ
œ˜Jšœ
œ'˜1Jš
œ˜—K™—™
J˜š œœ
œ(˜EJš
œ!˜!šœœ˜/Jšœœ
˜ —Jš
œ˜J˜—š œœ
œ(˜BJšœ
œœ
˜Jš
œ˜Jš
œ˜J˜—š œœ(˜PJš
œ!˜!šœœ˜/Jšœœ
œ
˜!—Jš
œ˜J˜—š œœ
œ$˜?Jšœœœ˜Jšœ
œœ
˜Jšœ#˜)J˜—š œœ$˜MJšœœœ˜šœœ˜/Jšœ
œ
œœ
œ
œœ
˜3—Jš
œ˜J˜—š œœ
œ$˜@Jšœœœ˜Jšœ
œœ
˜šœœ˜/Jšœ
œœ
œ
œœ
˜/—Jš
œ˜J˜—š
 œœ
œ
œœ	˜2Jšœ
œœ
˜šœœ
˜#Jšœ
œœœ
˜/—Jš
œ˜J˜—K™—™	˜J™VJš
œ—™——š
 
œœœœ
œ˜4Jšœœœž˜1Jšœœœž+˜OJšœ
œ
œ
œ
˜$šœ
˜šœ˜Jšœ!ž*˜KJšœ#ž˜8Jšœ&ž˜BJšœ&ž ˜FJšœ&ž˜EJšœ)ž!˜JJš
œD™DJšœ+ž$˜Ošœœ˜-Jš
œT™T——J˜—Jš
œ˜—J˜š 	œœœ
œ˜4Jšœœ˜'šœ˜!Jšœ
œœ˜6Jšœ
œ ˜+—Jš
œ˜J˜—š œœœ
œ˜4Jšœ
œ+˜:Jš
œ˜J˜—š œœœ
œ˜7šœ
˜šœ
˜Jšœ	œ˜ Jšœ	œœ˜2Jšœœ˜)—Jšœœ˜—Jš
œ˜—J˜šΠbnœœœ
œ˜1šœ˜!Jšœ
œ!œ˜?Jšœ
œ$œ˜E—Jš
œ˜J˜—š
 œœœœ
œ˜2Jšœ ˜&J˜J˜—š
 œœœœ
œ˜3Jšœœ˜EJ˜J˜—š
 œœœœ
œ˜2Jšœ ˜&J˜J˜—š
 œœœœ
œ˜<Jšœ˜"J˜—J˜š
 œœœ
œ
œ˜8Jš
œ
œ
œœ
œ˜9J˜J˜—š
 œœœ
œœ˜9Jšœ
œœ
œ˜7J˜J˜—š 	œœœ
œ˜2Jšœ
œ˜!J˜J˜—š 	œœœœ˜5Jšœ˜J˜J˜—š 	œœœ
œ˜2Jšœ
œ˜!J˜—J˜š œœœ˜3Jšœ
œœœ˜LJ˜J˜—š œœœ˜3Jšœ
œœœ˜LJ˜J˜—š 	œœœ˜6Jšœ
œœœ˜MJ˜—J˜š
 œœœ
œœ˜-šœœ
œ
˜šœœœ
œ˜0Jšœœ
œ˜Jšœ
œ
œ˜—Jšœ
˜—Jšœœ˜3Jš
œ˜—J˜š œœœœ
œœ˜<J˜—š
 œœœœ
œ˜$š
˜Jšœœœ˜Jšœœ
œ˜J˜J˜—Jšœ
˜J˜—˜Jš
œA™A—š œ
˜Jšœœ
œœ
œ
œœ˜XJš
œ˜Jš
œ˜Jš
œ˜š
œB˜BJš
œ6™6—š
œN˜Nš
œ(™(Jš
œ-™-——Jš
œ˜Jšœœ˜%Jš
œ˜Jš
œK˜Kšœ˜
Jšœœ#˜IJšœ(œ˜F—Jš
œ˜J˜Jš
œI™I—š 	œœ+œœ
˜GKšœ(˜/Kš
œ
˜
šœ˜šœœ	˜š
œM˜Mšœœ˜šœ
œ/˜2Kšœœ
˜Kšœ
œ˜———Kš
œ˜—Jšœ
˜Kšœ	œ˜#Jš
œ˜—Jšœ
˜Kš
œ˜——K™K™—™Kš
œZ™Z—š 
œœ
œ˜Jšœ
œœœœœ˜VJšœE˜Mšœœ
œœ
œ
œ
œ˜BJšœœ
œ
œ˜%—š
œ
˜
Jšœœ
œB˜P—J˜J˜Kš
œ™—š œœ
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ˜J˜J˜—š
œ
™
˜J™J™=—Jš
œœœœ
œ
˜E—˜šœž$˜&Kšœœ˜Jš
œ˜šœž
œœ˜Hš
˜Jš	œœœ
œœ˜6šœœž˜)Jšœœ
œ
˜"Jš
œ˜Jš
œ˜Jš
œ˜J˜—Jš
œ˜—Jšœ
˜——Jš
œ˜J™Jš
œ*™*J˜—J˜—Jšœ
˜J˜—…—hΘͺ²