DIRECTORY
Allocator USING [BlockSizeIndex, bsiEscape, BSIToSizeObj, EHeaderP, ExtendedHeader, FNHeaderP, Header, HeaderP, LastAddress, logPagesPerQuantum, maxSmallBlockSize, minLargeBlockSize, NHeaderP, NormalHeader, pagesPerQuantum, PUZone, QMObject, QuantumCount, QuantumIndex, QuantumMap, RefCount, SizeToBSIObj, UZoneObject, wordsPerQuantum, Zone, ZoneObject],
AllocatorOps USING [CreateMediumSizedHeapObject, DFHeaderP, DoubleFreeHeader, FreeMediumSizedHeapObject, nonNullType, permanentPageZone, REFToNHP, Rover],
Basics USING [BITAND, BITOR, BITXOR, CARD, DoubleShiftLeft, DoubleShiftRight, HighHalf, LongNumber, LowHalf],
DebuggerSwap USING [CallDebugger],
PrincOps USING [SD, StateVector, zRET],
PrincOpsUtils USING [LongZero, MyLocalFrame],
RCMicrocodeOps USING [Allocate, CreateRef, FREEPLEASE, Free, InsertQuanta, rcMicrocodeExists, SoftwareAllocate, SoftwareFree],
RTSD USING [sSystemZone],
SafeStorage USING [GetCanonicalType, NarrowRefFault, nullType, Type],
SafeStoragePrivate USING [],  -- TEMPORARY export of NewObject
StorageAccounting USING [ConsiderCollection, nObjectsCreated, nObjectsReclaimed, nWordsReclaimed],
StorageTraps USING [],
SystemVersion USING [machineType],
TrapSupport USING [BumpPC, GetTrapParam],
UnsafeStorage USING [],
UnsafeStoragePrivate USING[FreeTransientPageObject, InitializeTransientPageZone, NewTransientPageObject],
VM USING [AddressForPageNumber, Allocate, CantAllocate, Free, Interval, logWordsPerPage, PageNumber, PageNumberForAddress, PagesForWords, Pin, SimpleAllocate, SwapIn, Unpin, WordsForPages, wordsPerPage],
ZCT USING [Enter, ExpandZCT];
AllocatorImpl: MONITOR
IMPORTS AllocatorOps, Basics, DebuggerSwap, PrincOpsUtils, RCMicrocodeOps, SafeStorage, StorageAccounting, SystemVersion, TrapSupport, UnsafeStoragePrivate, VM, ZCT
EXPORTS AllocatorOps, SafeStorage, SafeStoragePrivate, StorageTraps, UnsafeStorage
= BEGIN OPEN Allocator, AllocatorOps;

CARD: TYPE = Basics.CARD;
Ptr: TYPE = LONG POINTER;
SmallFreeTable: TYPE = ARRAY Allocator.BlockSizeIndex OF Allocator.FNHeaderP;
Type: TYPE = SafeStorage.Type;
UZone: TYPE = UNCOUNTED ZONE;

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

checking: BOOL _ TRUE;
paranoid: BOOL _ SystemVersion.machineType # dorado;

maxSmallBlockRealSize: NAT = QuantizedSize[maxSmallBlockSize];
minLargeBlockRealSize: NAT = QuantizedSize[minLargeBlockSize];
wordsPerPage: NAT = VM.wordsPerPage;
logWordsPerPage: NAT = VM.logWordsPerPage;
wordsPerQuantum: NAT = Allocator.wordsPerQuantum;
logWordsPerQuantum: NAT = logWordsPerPage+Allocator.logPagesPerQuantum;
nullType: SafeStorage.Type = SafeStorage.nullType;
NormalHeaderInit: Allocator.NormalHeader = [
type: nullType,
blockSizeIndex: 0];
NormalHeaderEscape: Allocator.NormalHeader = [
type: nullType,
blockSizeIndex: Allocator.bsiEscape];
ExtendedHeaderInit: Allocator.ExtendedHeader = [
sizeTag: pages,
extendedSize: 0,
blockSizeIndex: Allocator.bsiEscape,
normalHeader: NormalHeaderEscape];


hackPtr: LONG POINTER _ VM.AddressForPageNumber[VM.SimpleAllocate[1].page];
HackAlloc: PROC [nWords: CARDINAL] RETURNS [ptr: LONG POINTER] = {
ptr _ hackPtr;
PrincOpsUtils.LongZero[ptr, nWords];
hackPtr _ hackPtr + nWords;
};


innerStats: LONG POINTER TO InnerStats _ HackAlloc[SIZE[InnerStats]];
InnerStats: TYPE = RECORD [
countedSmallNewAllocs: INT _ 0,
countedBigNewAllocs: INT _ 0,
uncountedSmallNewAllocs: INT _ 0,
uncountedBigNewAllocs: INT _ 0,
countedSmallNewFrees: INT _ 0,
countedBigNewFrees: INT _ 0,
uncountedSmallNewFrees: INT _ 0,
uncountedBigNewFrees: INT _ 0,
quantaAllocated: INT _ 0,
quantaFreed: INT _ 0
];

rZnHeapSystem: UZoneObject _ [new: NewHeapObject, free: FreeHeapObject];
znHeapSystem: Ptr _ LONG[@rZnHeapSystem];
zhs: UZone _ LOOPHOLE[LONG[@znHeapSystem], UZone];
transientPageUZoneObject: UZoneObject _ [
new: UnsafeStoragePrivate.NewTransientPageObject,
free: UnsafeStoragePrivate.FreeTransientPageObject];
transientPageUZonePointer: Ptr _ LONG[@transientPageUZoneObject];
transientPageUZone: UZone _ LOOPHOLE[LONG[@transientPageUZonePointer], UZone];
bsiToSize: PUBLIC LONG POINTER TO BSIToSizeObj _ permanentPageZone.NEW[BSIToSizeObj _ ALL[0]];
sizeToBSI: PUBLIC LONG POINTER TO SizeToBSIObj _ permanentPageZone.NEW[SizeToBSIObj];

msRover: Rover _ HackAlloc[SIZE[DoubleFreeHeader]];
permRover: Rover _ HackAlloc[SIZE[DoubleFreeHeader]];
quantumMap: PUBLIC QuantumMap _ permanentPageZone.NEW[QMObject];

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

nQMapEntries: INT _ 0;

NewUObject: PUBLIC PROC [size: CARDINAL, zone: UZone] RETURNS [Ptr] = {
RETURN [NewHeapObject[LOOPHOLE[zone, PUZone], size]];
};

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

GetTransientPageUZone: PUBLIC PROC RETURNS [UZone] = {
RETURN [transientPageUZone];
};


NewHeapObject: PROC [self: PUZone, size: CARDINAL] RETURNS [p: Ptr] = {
ENABLE UNWIND => Crash[];
realSize: INT = QuantizedSize[MAX[size, SIZE[ExtendedHeader]]];
nhp: NHeaderP;
IF size > maxSmallBlockRealSize
THEN {
nhp _ AllocateNewStyle[realSize, FALSE, FALSE];
p _ LOOPHOLE[nhp, NHeaderP] + SIZE[NormalHeader];
}
ELSE {
p _ AllocatorOps.CreateMediumSizedHeapObject[realSize];
nhp _ LOOPHOLE[p, NHeaderP] - SIZE[NormalHeader];
};
nhp.type _ nonNullType;
IF UsableWords[nhp] < size THEN Crash[];
};

DoCreateMediumSizedObject: PUBLIC --INTERNAL-- PROC [size: NAT, type: Type, roverP: LONG POINTER TO--VAR-- Rover, counted: BOOL] RETURNS [p: Ptr _ NIL] = {
nhp: NHeaderP _ AllocateNewStyle[size, FALSE, FALSE];
nhp.type _ type;
p _ nhp+SIZE[NormalHeader];  -- here for the conservative scan
IF counted THEN Crash[];
};

FreeHeapObject: PROC [self: PUZone, object: Ptr] = {
ENABLE UNWIND => Crash[];
nhp: NHeaderP = LOOPHOLE[object - SIZE[NormalHeader]];
IF checking AND (CheckAfterAlloc[nhp] # 0 OR nhp.type # nonNullType) THEN
Crash[];
IF nhp.blockSizeIndex = Allocator.bsiEscape
THEN {
FreeNewStyle[object, FALSE];
}
ELSE {
AllocatorOps.FreeMediumSizedHeapObject[object-SIZE[NormalHeader]];
};
};

DoFreeMediumSizedObject: PUBLIC --INTERNAL-- PROC [ptr: DFHeaderP, rover: Rover] = {
bsi: Allocator.BlockSizeIndex _ ptr.eh.blockSizeIndex;
counted: BOOL _ rover = permRover;
IF rover = msRover THEN counted _ TRUE;
IF bsi # Allocator.bsiEscape THEN {
FreeNewStyle[LOOPHOLE[ptr, Ptr] + SIZE[Allocator.NormalHeader], counted];
RETURN;
};
IF ptr.eh.sizeTag = pages THEN {
FreeNewStyle[LOOPHOLE[ptr, Ptr] + SIZE[Allocator.ExtendedHeader], counted];
RETURN;
};
Crash[];
};


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: Type, size: CARDINAL, zone: ZONE _ NIL] RETURNS [ans: REF _ NIL] = {
SELECT zone FROM
NIL, systemZone => ans _ NewSystemObject[NIL, size, type];
permanentZone => ans _ NewPermanentObject[NIL, size, type];
ENDCASE => Crash[];
};

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

IsValidRef: PUBLIC --INTERNAL-- PROC [p: Ptr] RETURNS [BOOL] = {
SELECT TRUE FROM
p = NIL => RETURN [TRUE];
LOOPHOLE[p, CARD] >= LastAddress => RETURN [FALSE];
Basics.LowHalf[LOOPHOLE[p, CARD]] MOD 2 = 1 => RETURN [FALSE];
ENDCASE => {
qi: QuantumIndex _ LPToQI[p];
IF quantumMap[qi] THEN {
hp: HeaderP _ NIL;
UNTIL qi = FIRST[QuantumIndex] OR NOT quantumMap[qi-1] DO
qi _ qi-1;
ENDLOOP;
hp _ QIToLP[qi];
WHILE LOOPHOLE[hp, CARD] < LOOPHOLE[p, CARD] DO
bs: Basics.LongNumber;
nhp: NHeaderP _ LOOPHOLE[hp, NHeaderP];
extended: BOOL _ nhp.blockSizeIndex = bsiEscape;
r: Ptr;
IF extended
THEN {
ehp: EHeaderP _ LOOPHOLE[hp];
nhp _ nhp + (SIZE[ExtendedHeader] - SIZE[NormalHeader]);
SELECT ehp.sizeTag FROM
words => bs.lc _ ehp.extendedSize;
pages => bs.lc _ VM.WordsForPages[ehp.extendedSize];
ENDCASE => Crash[];
r _ hp + SIZE[ExtendedHeader];
}
ELSE {
bs.lc _ bsiToSize[nhp.blockSizeIndex];
r _ hp + SIZE[NormalHeader];
};
SELECT TRUE FROM
bs.lc = 0, bs.lc >= LastAddress, bs.lo MOD 2 = 1 =>
Crash[];
r = p => RETURN [nhp.type # nullType];
ENDCASE;
hp _ hp + bs.lc;
ENDLOOP;
};
RETURN [FALSE];
};
};


PinObject: PUBLIC SAFE PROC [ref: REF] = TRUSTED {
IF ref # NIL THEN {
nhp: HeaderP _ LOOPHOLE[ref, HeaderP] - SIZE[NormalHeader];
hp: HeaderP _ IF IsExtendedBlock[nhp] THEN LOOPHOLE[ref, HeaderP] - SIZE[ExtendedHeader] ELSE nhp;
words: INT _ BlockSize[hp];
low: VM.PageNumber _ VM.PageNumberForAddress[hp];
next: VM.PageNumber _ VM.PageNumberForAddress[hp+(words-1)] + 1;
VM.Pin[[low, next-low]];
};
};

UnpinObject: PUBLIC SAFE PROC [ref: REF] = TRUSTED {
IF ref # NIL THEN {
nhp: HeaderP _ LOOPHOLE[ref, HeaderP] - SIZE[NormalHeader];
hp: HeaderP _ IF IsExtendedBlock[nhp] THEN LOOPHOLE[ref, HeaderP] - SIZE[ExtendedHeader] ELSE nhp;
words: INT _ BlockSize[hp];
low: VM.PageNumber _ VM.PageNumberForAddress[hp];
next: VM.PageNumber _ VM.PageNumberForAddress[hp+(words-1)] + 1;
VM.Unpin[[low, next-low]];
};
};

NewSystemObject: PROC [self: Zone, size: CARDINAL, type: Type] RETURNS [r: REF] = {
nhp: NHeaderP _ NIL;
realSize: INT _ size;
IF type = nullType THEN ERROR;

IF (r _ RCMicrocodeOps.Allocate[size, type]) # NIL
THEN {
nhp _ LOOPHOLE[r, NHeaderP] - SIZE[NormalHeader];
IF checking AND CheckAfterNewRef[nhp, type] # 0 THEN Crash[];
realSize _ bsiToSize[nhp.blockSizeIndex];
IF realSize = 0 THEN Crash[];
}
ELSE {
nhp: NHeaderP _ NIL;
realSize _ QuantizedSize[size];
IF size >= minLargeBlockSize THEN realSize _ LONG[size] + SIZE[ExtendedHeader];
nhp _ AllocateNewStyleEntry[realSize, TRUE, FALSE];
nhp.type _ type;
IF checking AND CheckAfterAlloc[nhp] # 0 THEN Crash[];
r _ LOOPHOLE[nhp+SIZE[NormalHeader]];
RCMicrocodeOps.CreateRef[nhp];
IF paranoid THEN {
IF CheckAfterNewRef[nhp, type] # 0 THEN Crash[];
IF UsableWords[nhp] < size THEN Crash[];
};
};
StorageAccounting.nObjectsCreated _ StorageAccounting.nObjectsCreated + 1;
StorageAccounting.ConsiderCollection[size, realSize];
};

ExpandNormalFreeList: PUBLIC PROC [bsi: BlockSizeIndex] = {
[] _ ExpandAnyFreeList[bsi, TRUE, FALSE];
};

ExpandAnyFreeList: PROC [bsi: BlockSizeIndex, install, permanent: BOOL] RETURNS [first, last, next: FNHeaderP _ NIL] = {
qi: QuantumIndex;
qc: QuantumCount;
incr: NAT = bsiToSize[bsi];
druthers: QuantumCount = WordsToQC[Lcm[incr, wordsPerQuantum]];
[qi, qc] _ GetQuanta[druthers, NOT install];
first _ last _ LOOPHOLE[QIToLP[qi], FNHeaderP];
next _ LOOPHOLE[QIToLP[qi+qc], FNHeaderP];
Clear[first, QCToWords[qc]];
DO
after: FNHeaderP _ last+incr;
last.fnh _ [blockSizeIndex: bsi];
IF after = next THEN EXIT;
last.nextFree _ after;
last _ after;
ENDLOOP;
last.nextFree _ NIL;
IF install THEN
PutQuantaOnNormalFreeList[bsi, first, last, qi, qc];
};

PutQuantaOnNormalFreeList: ENTRY PROC [bsi: BlockSizeIndex, first, last: FNHeaderP, qi: QuantumIndex, qc: QuantumCount] = {
ENABLE UNWIND => NULL;
RCMicrocodeOps.InsertQuanta[bsi, first, last];
StuffQMapRange[qi, qc];
};
NewPermanentObject: PROC [self: Zone, size: CARDINAL, type: Type] RETURNS [r: REF _ NIL] = {
realSize: CARD _ LONG[size] + SIZE[NormalHeader];
nhp: NHeaderP _ NIL;
IF type = nullType THEN ERROR;
IF size >= minLargeBlockSize THEN realSize _ LONG[size] + SIZE[ExtendedHeader];
nhp _ AllocateNewStyleEntry[realSize, TRUE, TRUE];
nhp.type _ type;
StorageAccounting.nObjectsCreated _ StorageAccounting.nObjectsCreated + 1;
StorageAccounting.ConsiderCollection[size, realSize];
IF checking AND UsableWords[nhp] < size THEN Crash[];
RCMicrocodeOps.CreateRef[nhp];
IF paranoid THEN {
IF CheckAfterNewRef[nhp, type] # 0 THEN Crash[];
IF UsableWords[nhp] < size THEN Crash[];
};
RETURN [LOOPHOLE[nhp+SIZE[NormalHeader]]];
};

FreeSystemObject: PROC [self: Zone, object: REF ANY] = {
};

FreeObject: PUBLIC PROC [nhp: NHeaderP] = {
realSize: INT _ RealWords[nhp];
IF checking AND (CheckAfterAlloc[nhp] # 0 OR nhp.type = nullType) THEN
Crash[];
BumpWordsReclaimed[realSize];
IF NOT RCMicrocodeOps.Free[nhp].success THEN {
ehp: EHeaderP = NHPToEHP[nhp];
IF nhp.blockSizeIndex # Allocator.bsiEscape THEN Crash[];
SELECT ehp.sizeTag FROM
pages => {
qi: QuantumIndex _ LPToQI[ehp];
qc: QuantumCount _ WordsToQC[realSize];
IF checking THEN {
ln: Basics.LongNumber _ [li[realSize]];
IF ln.lo MOD wordsPerQuantum # 0 THEN Crash[];
IF Basics.LowHalf[LOOPHOLE[ehp, CARD]] MOD wordsPerQuantum # 0
THEN Crash[];
IF NOT IsFullQMapRange[qi, qc] THEN Crash[];
};
ClearQMapRange[qi, qc];
FreeQuanta[qi, qc];
};
ENDCASE => Crash[];
};
};
TAndSFreeObject: PUBLIC --INTERNAL-- PROC [nhp: NHeaderP] = {
realSize: INT _ RealWords[nhp];
IF checking AND CheckAfterAlloc[nhp] # 0 THEN Crash[];
IF nhp.type # nullType THEN {
StorageAccounting.nObjectsReclaimed _ StorageAccounting.nObjectsReclaimed + 1;
StorageAccounting.nWordsReclaimed _ StorageAccounting.nWordsReclaimed + realSize;
};
IF NOT RCMicrocodeOps.FREEPLEASE[nhp].success THEN {
ehp: EHeaderP = NHPToEHP[nhp];
IF nhp.blockSizeIndex # Allocator.bsiEscape THEN Crash[];
SELECT ehp.sizeTag FROM
pages => {
qi: QuantumIndex _ LPToQI[ehp];
qc: QuantumCount _ WordsToQC[realSize];
IF checking THEN {
ln: Basics.LongNumber _ [li[realSize]];
IF ln.lo MOD wordsPerQuantum # 0 THEN Crash[];
IF Basics.LowHalf[LOOPHOLE[ehp, CARD]] MOD wordsPerQuantum # 0
THEN Crash[];
IF NOT IsFullQMapRangeInternal[qi, qc] THEN Crash[];
};
ClearQMapRangeInternal[qi, qc];
FreeQuanta[qi, qc];
};
ENDCASE => Crash[];
};
};

EnterAndCallBack: PUBLIC ENTRY PROC [proc: PROC] = {
ENABLE UNWIND => NULL;
proc[];
};

BumpWordsReclaimed: ENTRY PROC [words: INT] = {
StorageAccounting.nObjectsReclaimed _ StorageAccounting.nObjectsReclaimed + 1;
StorageAccounting.nWordsReclaimed _ StorageAccounting.nWordsReclaimed + words;
};


AllocateTrap: PUBLIC PROC [size: CARDINAL, type: 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];
2 => {
p: PROC [size: CARDINAL, type: Type] = MACHINE CODE{PrincOps.zRET};
ZCT.Enter[];
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state;   -- incantation
p[size, type];
};
4 => {
p: PROC [size: CARDINAL, type: Type] = MACHINE CODE{PrincOps.zRET};
ZCT.ExpandZCT[];
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state;   -- incantation
p[size, type];
};
6 => {
p: PROC [size: CARDINAL, type: Type] = MACHINE CODE{PrincOps.zRET};
ExpandNormalFreeList[sizeToBSI[size]];
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state;   -- incantation
p[size, type];
};
ENDCASE => Crash[];
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 => Crash[];
TrapSupport.BumpPC[2];                -- length of opcode
state.dest _ LOOPHOLE[PrincOpsUtils.MyLocalFrame[]];
TRANSFER WITH state;   -- incantation
};


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

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

GetCanonicalReferentTypeTrap: PUBLIC PROC [ref: REF] RETURNS [type: Type] = {
state: PrincOps.StateVector;
kludge: CARD;
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, type: Type] RETURNS [BOOL] = TRUSTED {
RETURN [SafeStorage.GetCanonicalType[type] = GetCanonicalReferentType[ref]];
};

NarrowRef: PUBLIC SAFE PROC [ref: REF, type: Type] RETURNS [REF] = TRUSTED {
SELECT TRUE FROM
ref = NIL =>
RETURN [NIL];
SafeStorage.GetCanonicalType[type] = GetCanonicalReferentType[ref] =>
RETURN [ref];
ENDCASE =>
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;
};


AllocateNewStyleEntry: ENTRY PROC [size: CARD, counted, permanent: BOOL] RETURNS [nhp: NHeaderP _ NIL] = {
ENABLE UNWIND => Crash[];
RETURN [AllocateNewStyle[size, counted, permanent]];
};

AllocateNewStyle: PROC [size: CARD, counted, permanent: BOOL] RETURNS [nhp: NHeaderP _ NIL] = {
ehp: EHeaderP _ NIL;
SELECT size FROM
<= SIZE[Allocator.NormalHeader] => Crash[];
<= maxSmallBlockRealSize => {
words: CARDINAL _ SELECT Basics.LowHalf[size] FROM
<= 20B => Basics.BITAND[Basics.LowHalf[size]+7, 177777B-7],
<= 100B => Basics.BITAND[Basics.LowHalf[size]+17B, 177777B-17B],
<= 1000B => Basics.BITAND[Basics.LowHalf[size]+177B, 177777B-177B],
ENDCASE => maxSmallBlockRealSize;
bsi: Allocator.BlockSizeIndex _ sizeToBSI[words-SIZE[Allocator.NormalHeader]];
objectWords: CARDINAL _ bsiToSize[bsi];
table: LONG POINTER TO SmallFreeTable _ IF counted THEN countedFreeTable ELSE uncountedFreeTable;
fhp: Allocator.FNHeaderP _ table[bsi];
IF counted
THEN
innerStats.countedSmallNewAllocs _ innerStats.countedSmallNewAllocs + 1
ELSE
innerStats.uncountedSmallNewAllocs _ innerStats.uncountedSmallNewAllocs + 1;
IF fhp = NIL THEN {
first, last, next: FNHeaderP;
[first, last, next] _ ExpandAnyFreeList[bsi, FALSE, permanent];
IF counted THEN
StuffQMapRange[qi: LPToQI[first], qc: LPToQI[next]-LPToQI[first]];
fhp _ table[bsi] _ first;
};
table[bsi] _ fhp.nextFree;
nhp _ LOOPHOLE[fhp];
IF nhp.blockSizeIndex # bsi OR nhp.type # nullType THEN
Crash[];
Clear[nhp+SIZE[Allocator.NormalHeader], objectWords-SIZE[Allocator.NormalHeader]];
nhp^ _ NormalHeaderInit;
nhp.blockSizeIndex _ bsi;
};
ENDCASE => {
qi: QuantumIndex;
qc: QuantumCount _ WordsToQC[size];
np: INT _ QCToPages[qc];
[qi, qc] _ GetQuanta[qc, permanent];
ehp _ QIToLP[qi];
Clear[ehp, VM.WordsForPages[np]];
IF counted
THEN {
StuffQMapRange[qi: LPToQI[ehp], qc: qc];
innerStats.countedBigNewAllocs _ innerStats.countedBigNewAllocs + 1;
}
ELSE {
innerStats.uncountedBigNewAllocs _ innerStats.uncountedBigNewAllocs + 1;
};
ehp^ _ ExtendedHeaderInit;
ehp.extendedSize _ np;
nhp _ @ehp.normalHeader;
};
IF checking AND CheckAfterAlloc[nhp] # 0 THEN Crash[];
};

FreeNewStyle: PROC [ptr: Ptr, counted: BOOL] = {
IF Basics.HighHalf[LOOPHOLE[ptr]] # 0 AND Basics.LowHalf[LOOPHOLE[ptr]] MOD 2 = 0 THEN {
nhp: NHeaderP _ LOOPHOLE[ptr, NHeaderP]-SIZE[Allocator.NormalHeader];
IF nhp.type = nullType THEN Crash[];
SELECT TRUE FROM
nhp.blockSizeIndex = Allocator.bsiEscape => {
ehp: EHeaderP _ LOOPHOLE[ptr, EHeaderP]-SIZE[Allocator.ExtendedHeader];
SELECT ehp.sizeTag FROM
pages => {
np: CARDINAL _ ehp.extendedSize;
qi: QuantumIndex _ LPToQI[ehp];
qc: QuantumCount _ PagesToQC[np];
ehp.extendedSize _ 0;
IF np = 0 THEN Crash[];
IF Basics.BITAND[wordsPerQuantum-1, Basics.LowHalf[LOOPHOLE[ehp]] ] # 0 THEN Crash[];
IF counted
THEN {
ClearQMapRangeInternal[qi, qc];
innerStats.countedBigNewFrees _ innerStats.countedBigNewFrees + 1
}
ELSE
innerStats.uncountedBigNewFrees _ innerStats.uncountedBigNewFrees + 1;
FreeQuanta[qi, qc];
RETURN;
};
ENDCASE;
};
ENDCASE => {
bsi: Allocator.BlockSizeIndex _ nhp.blockSizeIndex;
table: LONG POINTER TO SmallFreeTable _ IF counted THEN countedFreeTable ELSE uncountedFreeTable;
fhp: Allocator.FNHeaderP _ LOOPHOLE[nhp, Allocator.FNHeaderP];
IF counted
THEN
innerStats.countedSmallNewFrees _ innerStats.countedSmallNewFrees + 1
ELSE
innerStats.uncountedSmallNewFrees _ innerStats.uncountedSmallNewFrees + 1;
fhp.fnh _ NormalHeaderInit;
fhp.fnh.blockSizeIndex _ bsi;
fhp.nextFree _ table[bsi];
table[bsi] _ fhp;
RETURN;
};
};
IF ptr # NIL THEN Crash[];
};

countedFreeTable: LONG POINTER TO SmallFreeTable _ InitSmallAllocator[];
uncountedFreeTable: LONG POINTER TO SmallFreeTable _ InitSmallAllocator[];

InitSmallAllocator: PROC RETURNS [ptr: LONG POINTER TO SmallFreeTable] = {
pages: NAT _ VM.PagesForWords[SIZE[SmallFreeTable]];
interval: VM.Interval _ VM.Allocate[count: pages, in64K: TRUE];
VM.SwapIn[interval];
ptr _ LOOPHOLE[VM.AddressForPageNumber[interval.page]];
Clear[ptr, SIZE[SmallFreeTable]];
};

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

RETURN [VM.WordsForPages[VM.PagesForWords[LONG[size]+e]]];
};

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] = INLINE {
RETURN [LOOPHOLE[hp, NHeaderP].blockSizeIndex = bsiEscape];
};

ExtendedBlockSize: PROC [ehp: EHeaderP] RETURNS [words: INT _ 0] = INLINE {
SELECT ehp.sizeTag FROM
words =>  words _ ehp.extendedSize;
pages => words _ VM.WordsForPages[ehp.extendedSize];
ENDCASE => Crash[];
};

RealWords: PROC [nhp: NHeaderP] RETURNS [words: INT] = INLINE {
IF nhp.blockSizeIndex # bsiEscape
THEN RETURN [bsiToSize[nhp.blockSizeIndex]]
ELSE {
ehp: EHeaderP _ NHPToEHP[nhp];
SELECT ehp.sizeTag FROM
words => words _ ehp.extendedSize;
pages => words _ VM.WordsForPages[ehp.extendedSize];
ENDCASE => Crash[];
RETURN [words];
};
};

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

QIToLP: PROC [qi: QuantumIndex] RETURNS [Ptr] = INLINE {
RETURN [Basics.DoubleShiftLeft[[lc[qi]], logWordsPerQuantum].lp];
};

LPToQI: PROC [ptr: Ptr] RETURNS [QuantumIndex] = INLINE {
RETURN [Basics.DoubleShiftRight[[lp[ptr]], logWordsPerQuantum].lo];
};

QCToWords: PROC [qc: QuantumCount] RETURNS [INT] = INLINE {
RETURN [Basics.DoubleShiftLeft[[lc[qc]], logWordsPerQuantum].li];
};

WordsToQC: PROC [words: INT] RETURNS [QuantumCount] = INLINE {
RETURN [Basics.DoubleShiftRight[[li[words+(wordsPerQuantum-1)]], logWordsPerQuantum].lo];
};

PagesToQC: PROC [pages: INT] RETURNS [qc: QuantumCount] = INLINE {
IF Allocator.logPagesPerQuantum = 0 THEN RETURN [pages];
pages _ pages + (pagesPerQuantum-1);
RETURN [Basics.DoubleShiftRight[[li[pages]], Allocator.logPagesPerQuantum].lo];
};

QCToPages: PROC [qc: QuantumCount] RETURNS [pages: INT] = INLINE {
IF Allocator.logPagesPerQuantum = 0
THEN RETURN [qc]
ELSE RETURN [Basics.DoubleShiftLeft[[lc[qc]], Allocator.logPagesPerQuantum].li];
};

EHPToNHP: PROC [ehp: EHeaderP] RETURNS [NHeaderP] = INLINE {
RETURN [@ehp.normalHeader];
};

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

DFHPToNHP: PROC [dfhp: DFHeaderP] RETURNS [NHeaderP] = INLINE {
RETURN [@dfhp.eh.normalHeader];
};

FunnyHeaderPtr: TYPE = LONG POINTER TO FunnyHeader;
FunnyHeader: TYPE = MACHINE DEPENDENT RECORD [
preType (0): WORD,
type (1): WORD];

CheckAfterAlloc: PROC [nhp: NHeaderP] RETURNS [WORD] = INLINE {
RETURN [Basics.BITAND[LOOPHOLE[nhp, FunnyHeaderPtr].preType, maskWord1]];
};

maskWord1: WORD = LOOPHOLE[Allocator.NormalHeader[
inZCT: TRUE, f: TRUE, rcOverflowed: TRUE, refCount: LAST[Allocator.RefCount],
blockSizeIndex: 0], FunnyHeader].preType;

CheckAfterNewRef: PROC [nhp: NHeaderP, type: Type] RETURNS [WORD] = INLINE {
RETURN [Basics.BITOR[
Basics.BITAND[LOOPHOLE[nhp, FunnyHeaderPtr].preType, maskWord2],
Basics.BITXOR[LOOPHOLE[nhp, FunnyHeaderPtr].type, type] 
]];
};

maskWord2: WORD = LOOPHOLE[Allocator.NormalHeader[
f: TRUE, rcOverflowed: TRUE, refCount: LAST[Allocator.RefCount],
blockSizeIndex: 0], FunnyHeader].preType;

Clear: PROC [ptr: Ptr, size: INT] = {
delta: CARDINAL = 20000B;
WHILE size > delta DO
PrincOpsUtils.LongZero[ptr, delta];
size _ size - delta;
ptr _ ptr + delta;
ENDLOOP;
PrincOpsUtils.LongZero[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;
};

GetQuanta: PROC [needed: QuantumCount, permanent: BOOL _ FALSE] RETURNS [qi: QuantumIndex, qc: QuantumCount] = {
np: INT _ QCToPages[qc _ needed];
interval: VM.Interval _ VM.Allocate[
count: np, alignment: logPagesPerQuantum, in64K: permanent
! VM.CantAllocate => GO TO noVM
];
VM.SwapIn[interval];
qi _ PagesToQC[interval.page];
innerStats.quantaAllocated _ innerStats.quantaAllocated + qc;
EXITS noVM => ERROR InsufficientVM;
};

FreeQuanta: PROC [qi: QuantumIndex, qc: QuantumCount] = {
VM.Free[[page: QCToPages[qi], count: QCToPages[qc]]];
innerStats.quantaFreed _ innerStats.quantaFreed + qc;
};
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 Ptr]^
_ LOOPHOLE[systemZone, Ptr];
permanentZone
_ LOOPHOLE[NEW[ZoneObject _ [new: NewPermanentObject, free: FreeSystemObject]]];
UnsafeStoragePrivate.InitializeTransientPageZone[];
};

Reset: PUBLIC PROC = {
countedFreeTable^ _ ALL[NIL];
uncountedFreeTable^ _ ALL[NIL];
};

Crash: PROC = {
DebuggerSwap.CallDebugger["Kosher it's not!"L];
};


{
oldQS: NAT _ 0;
nextBSI: BlockSizeIndex _ 0;

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

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

};

END.

 ΊAllocatorImpl.Mesa
Copyright c 1984, 1985, 1986 by Xerox Corporation.  All rights reserved.
designed by Paul Rovner
Bob Hagmann, February 19, 1985 5:45:56 pm PST
Russ Atkinson (RRA) April 15, 1986 2:26:17 pm PST
the LOCK protects the quantumMap and the countedFreeTable
ERRORS

Options

We don't trust any new code!
Extra checks when distrusting microcode.
CONSTANTS

VARIABLES and their INITIALIZATION
Inner Statistics
NOTE: the declaration sequence below is EXTREMELY DELICATE.  Order of the declarations and their initialization is important.

Support for the systemUZone


Support for the TransientPageUZone


Support for both uncounted and counted storage (exported to AllocatorOps)

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
msRoot: DoubleFreeHeader _ [
eh: [extendedSize: 0, normalHeader: [blockSizeIndex: bsiEscape]],
nextFree: @msRoot,
prevFree: @msRoot
];
(Obsolete, but necessary as a place holder)

the "permanent" free list (permRover): a doubly-linked ring
permRoot: DoubleFreeHeader _ [
eh: [extendedSize: 0, normalHeader: [blockSizeIndex: bsiEscape]],
nextFree: @permRoot,
prevFree: @permRoot
];
(Obsolete, but necessary as a place holder)

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

Statistics

PROCEDURES
Support for uncounted storage

Public access to uncounted storage

UNCOUNTED ZONE procs

Unfortunately, these cannot be ENTRY procs here, since the uncounted system zone gets used during TraceAndSweep, and should not have any connection with the counted allocator.  Of course, it does, but we will be careful about this.  For historical reasons, the "medium" allocator is assumed in the interfaces, even though there is no longer any such thing.  The monitor lock in UnsafeAllocatorImpl is used to protect our uncounted data structures.
Referenced only via zhs, The "systemUZone"
We don't need a monitor lock for large allocation
We need the monitor lock for small allocation (to protect the table)
(this is a monitored call to DoCreateMediumSizedObject)
Called from UnsafeAllocatorImpl.CreateMediumSizedHeapObject
size includes overhead (for extended header), has been quantized and is >= SIZE[DoubleFreeHeader].
This proc may return an object of a larger size than requested.
Referenced only via zhs, The "systemUZone"
For large objects we do not need the monitor
For small objects we need the monitor (to protect the table)
(this is a monitored call to DoFreeMediumSizedObject)
Called from UnsafeAllocatorImpl.FreeMediumSizedObject
ptr may refer to a small object or a large one
This is a real crock, but such is life
Can we ever have rover = msRover?
This is a small-size object allocated by the new allocator
This is a large-size object that we can handle in the new style.
Support for counted storage

Public access to counted storage
There is nothing to do here, although there could be some day
Start parsing at the beginning of the first quantum in this run.  Note that we depend on the quantumMap not changing during this operation!
hp points to an extended header
hp points to a normal header
The size of the object must never be too small, too large, or odd.  If it is then we crash, since it means that the heap has been violated.
We have found the REF, so the ref is valid for non-free objects.
Pinning & unpinning objects
... pins the object & its header in memory
... unpins the object & its header (provided it was already pinned)
ZONE procs

Referenced from systemZone and called from NewObject and Initialize
size DOES NOT INCLUDE overhead
This should NOT happen!
The microcode allocation was successful, so just use the object returned.  This is the fastest path for allocation.
medium-sized or large object
We are getting pretty suspicious here!
Called from Allocate and AllocateTrap.
Called from ExpandNormalFreeList (install = TRUE) and AllocateNewStyle (install = FALSE).  This proc must not call monitored procedures if NOT install!
Using the LCM enables us to not have any leftovers, which helps zone scanning in the future.
Run through the zone, chaining the free blocks together in increasing order until we hit next, which is the next object after our allocated storage.  Every free block is initialized with the blockSizeIndex.
This is for the normal free list, so we install it
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

Referenced from permanentZone and called from NewObject
size DOES NOT INCLUDE overhead
This should NOT happen!
We are getting pretty suspicious here!
Referenced from systemZone and permanentZone
We always rely on GC, except from within GC for collectible objects
Procs called by the reclaimer and TraceAndSweepImpl

Monitored to keep the stats reasonably consistent
This is a large block

It is possible to free an already free object during T&S, since we rebuild the free lists from scratch, but that should NOT count in the statistics.
large or medium-sized object or extended header for some other reason
Called from TraceAndSweepImpl.
Trap handlers
no microcode
uCode is disabled; someone is inside this monitor
zctFull
expandNormalFreeList
Support for NARROW; referent types

QuantumMap
New uncounted allocator
This must be called under the allocator lock for counted allocations!
words INCLUDES overhead, has been quantized and is >= SIZE[DoubleFreeHeader].
This proc may return an object of a larger size than requested (of course).
This proc can be called only for uncounted objects or for counted permanent zone objects.  System zone objects are handled differently (see NewSystemObject).
Allocate from quantized table
RRA: to reduce breakage here, get all small objects up to a multiple of 2^n.
8, 16
32, 48, 64 
128, 256, 384, 512
576
This slot needs some words added to it
Call to expand the free list for the given size.  Note that we should never get here for the system zone, only for the permanent zone or the uncounted zone, so it is quite proper to NOT ask for installation.
These quanta need to be shown as in the counted heap
We have a nasty error here, since these are set when we initialize, and are not changed by anything except a bad bug!
Allocate from VM
These quanta need to be shown as in the counted heap
Just count this one
This must be called under the allocator lock (unless for an uncounted large block)!
If AllocateNewStyle allocated this object, then it has ehp.sizeTag = pages.  Otherwise, we did not have anything to do with it.
We probably did allocate this object, so we can return it to our pool.
This is protected (after init) by the monitor in AllocatorImpl (this module)
This is protected (after init) by the monitor in UnsafeAllocatorImpl

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 > maxSmallBlockSize require extended headers.  It is not true that the difference between any two quantized sizes is a valid quantized size.
sizes: 1200B, 1400B, 1600B, 2000B, 2200B
steps of wordsPerPage for requested size
nhp.inZCT OR nhp.f OR nhp.rcOverflowed OR nhp.refCount # 0
Called from ExpandNormalFreeList, AllocateNewStyle
Called from ExpandNormalFreeList, AllocateNewStyle

This is called long after this module is started; CODE[mumble] isn't meaningful until then
This is called by the TAndS (with the monitor lock held); the intent is to make us drop all of the free lists so they can be reconstructed
START CODE
Initialize bsiToSize and sizeToBSI
Initialize the quantum map: needed here because ALL has a bug
new size and bsi
The systemUZone (zhs) is now ready for use
Bob Hagmann February 19, 1985 2:49:15 pm PST
changes to: DIRECTORY, AllocatorImpl, GetSystemUZone, GetTransientPageUZone, Initialize

Bob Hagmann February 19, 1985 5:44:59 pm PST
changes to: NewHeapObject, DoCreateMediumSizedObject
Russ Atkinson (RRA) February 3, 1986 2:13:31 pm PST
Beefed up checking in IsValidRef, made NewPermanentObject call AllocateNewStyleEntry instead of AllocateNewStyle.


Κ(L˜
codeš
œ™Kšœ
Οm
œ=™HK™Kš
œ-™-K™1K˜š
Οk	˜	Kšœ
žœΣ˜βKšœ
žœˆ
˜š
KšœžœžœžœžœžœD˜mKšœ
žœ˜"Kšœ	žœžœ˜'Kšœžœ˜-Kšœžœž
œI˜~Kšžœ
žœ˜Kšœžœ4˜EKšœžœΟc ˜>KšœžœK˜bKšœ
žœ˜Kšœžœ˜"Kšœžœ˜)Kšœžœ˜KšœžœO˜iKšžœ
žœΓ
˜Λ
Kšžœ
žœ˜——
headšœž˜Kš
œ9™9Kšžœ–
žœž˜€
KšžœK˜RKšœžœ
žœ˜%K˜Kšžœžœ
žœ
˜Kšœžœžœ
žœ
˜Kšœžœžœžœ˜MKšœžœ˜Kšœžœž	œ
žœ
˜—˜š
œ™K™Kšœžœžœ
˜Kšœžœ
žœžœ
žœžœ
˜.—K˜™K™šœ
žœžœ
˜Kš
œ™—šœ
žœ&˜4K™(—K˜—™	K™Kšœžœ$˜>Kšœžœ$˜>šœžœžœ˜$Kšœžœžœ˜*—šœžœ˜1Kšœžœ0˜G—Kš
œ2˜2˜,K˜K˜—š
œ.˜.K˜Kš
œ%˜%—š
œ0˜0Kš
œ˜K˜Kš
œ$˜$Kš
œ"˜"——K˜™"K˜Kš	œ	žœ
žœžœžœ˜KšΟn	œžœ
žœžœžœ
žœ˜BKš
œ˜Kš
œ$˜$Kš
œ˜K˜K˜—™K˜Kš	œžœ
žœ
žœžœ˜Ešœžœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ˜!Kšœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ˜ Kšœžœ˜Kšœžœ˜Kšœ
žœ˜K˜K˜——Kšžœ$ž	œ
žœC™}K™š
œ™K™š
œH˜HKšœžœ˜)—KšΟbœ
žœ
žœ˜2—K™š
œ"™"K™š
œ)˜)Kš
œ1˜1Kš
œ4˜4—Kšœ!žœ˜AKš‘œ
žœ
žœ%˜N—K™™IK™š
œžœ
žœ
žœ
žœ"žœžœ˜^Kš
œS™SK™—šœžœ
žœ
žœ
žœ"žœ˜UKš
œV™V—K˜—™ K™š
œ<™<š
œ™Kš
œA™AKš
œ™Kš
œ™Kš
œ™——šœžœ˜3K™+K™—š
œ;™;š
œ™Kš
œA™AKš
œ™Kš
œ™Kš
œ™——šœžœ˜5K™+—K™šœžœ žœ˜@Kš
œd™d—K˜Kšœžœžœ
˜Kšœžœžœ
˜—K™™
K˜Kšœžœ˜K™——™
K˜™K™™"K™š
 
œžœ
žœžœžœ
˜GKšžœžœ˜5Kš
œ˜K˜—š
 œžœ
žœ
žœ
ž
œ
˜/Kšžœ˜
Kš
œ˜—K˜š œžœ
žœ
žœ˜6Kšžœ˜Kš
œ˜K˜——K™™KšŸϊœŸ2™ΏK˜š 
œžœžœžœ
˜GKš
œ*™*Kšžœ
žœ˜Kšœ
žœžœžœ˜?Kš
œ˜šžœ˜šžœ˜Kš
œ1™1Kšœ!žœžœ˜/Kšœžœžœ˜1K˜
—šžœ˜Kš
œD™Dš
œ7˜7Kš
œ7™7—Kšœžœžœ˜1K˜——Kš
œ˜Kšžœžœ	˜(Kš
œ˜K˜—šΠbnœžœ
Ÿœ
žœžœžœ
žœ
žŸœžœžœžœ˜›
Kš
œ;™;KšœKžœ™bKš
œ?™?Kšœ'žœžœ˜5Kš
œ˜KšœžœŸ!˜>Kšžœ	žœ	˜Kš
œ˜K˜—š œžœ ˜4Kš
œ*™*Kšžœ
žœ˜Kšœžœ
žœ˜6šžœ
žœžœž˜IKš
œ˜—šžœ)˜+šžœ˜Kš
œ,™,Kšœžœ˜K˜
—šžœ˜Kš
œ<™<šœ.žœ˜BKš
œ5™5—K˜——Kš
œ˜K˜—š œžœ
Ÿœ
žœ#˜Tš
œ5™5K™.—Kš
œ6˜6šœ	žœ˜"Kš
œ&™&—šžœžœžœ
˜'Kš
œ!™!—šžœžœ˜#Kš
œ:™:Kšœ
žœ
žœ#˜IKšžœ
˜K˜—šžœžœ˜ Kš
œ@™@Kšœ
žœ
žœ%˜KKšžœ
˜K˜—Kš
œ˜Kš
œ˜——K˜—™K™™ K˜š 
œžœ
žœ
žœ
žœžœžœ
˜9Kšžœ˜Kš
œ˜K˜—š œžœ
žœ
žœ
žœžœžœ
˜<Kšžœ˜Kš
œ˜K˜—š
 œžœ
žœ
žœžœ˜,Kš
œ=™=Kšžœ
˜Kš
œ˜—K˜š 	œžœ
žœžœžœžœžœžœžœ˜bšžœž˜Kšžœ&žœ˜:Kšœ*žœ˜;Kšžœ˜—K˜—K˜š œžœ
ž
œžœ˜-Kšžœ
žœžœ
˜šžœ
žœžœž˜*Kšžœ˜"—K˜K˜—š 
œžœ
Ÿœ
žœ
žœžœ˜@šžœ
žœ
ž˜Kšœžœžœžœ˜Kšžœžœžœžœ˜3Kšœžœžœžœ
žœžœ˜>šžœ˜Kš
œ‹
™‹
Kš
œ˜šžœžœ˜Kšœžœ
˜š	žœžœžœ
žœž˜9Kš
œ
˜
Kšžœ
˜—Kš
œ˜šžœ
žœžœžœžœž˜/Kš
œ˜Kšœžœ˜'Kšœ
žœ"˜0Kš
œ˜šžœ	˜šžœ˜Kš
œ™Kšœžœ˜Kšœ
žœžœ˜8šžœ
ž˜Kš
œ"˜"Kšœžœ!˜4Kšžœ˜—Kšœ	žœ˜K˜
—šžœ˜Kš
œ™Kš
œ&˜&Kšœ	žœ˜K˜——šžœ
žœ
ž˜šœ'žœ	˜3Kš
œ‹
™‹
Kš
œ˜—šœ	žœ˜&Kšœžœ+™@—Kšžœ
˜—Kš
œ˜Kšžœ
˜—K˜—Kšžœžœ˜Kš
œ˜——K˜—K˜—™K˜š 	œžœ
žœ
žœžœž	œ
˜2Kš
œ*™*šžœžœ
žœ˜Kšœžœžœ˜;Kšœžœžœ
žœžœžœ˜bKšœžœ˜Kšœžœžœ˜1Kšœžœžœ(˜@Kšžœ˜K˜—Kš
œ˜K˜—š
 œžœ
ž
œžœžœ
˜4Kš
œC™Cšžœžœ
žœ˜Kšœžœžœ˜;Kšœžœžœ
žœžœžœ˜bKšœžœ˜Kšœžœžœ˜1Kšœžœžœ(˜@Kšžœ˜K˜—K˜K˜——™
K™š
 œžœžœžœžœ˜Sš
œC™CKš
œ™—Kšœžœ
˜Kšœ
žœ˜šžœžœ
žœ
˜Kš
œ™—K˜šžœ-ž˜2šžœ˜Kš
œs™sKšœžœžœ˜1Kšžœ
žœ!žœ	˜=Kš
œ)˜)Kšžœžœ	˜K˜
—šžœ˜Kš
œ™Kšœžœ
˜Kš
œ˜Kšžœžœžœ	žœ˜OKšœ&žœžœ˜3Kš
œ˜Kšžœ
žœžœ	˜6Kšœžœžœ˜%Kš
œ˜šžœ
žœ˜Kš
œ&™&Kšžœ!žœ	˜0Kšžœžœ	˜(K˜—K˜——Kš
œJ˜JKš
œ5˜5Kš
œ˜K˜—š œžœ˜;Kš
œ&™&Kšœžœžœ˜)Kš
œ˜K˜—š
 œžœ+žœžœ!žœ˜xKšœ,žœ"žœ4žœ	™—
Kš
œ˜Kš
œ˜Kšœžœ˜š
œ?˜?Kš
œ\™\—Kšœžœ
˜,Kšœžœ˜/Kšœžœ˜*Kš
œ˜Kš
œΞ
™Ξ
š
ž˜Kš
œ˜Kš
œ!˜!Kšžœžœ
žœ
˜Kš
œ˜Kš
œ
˜
Kšžœ
˜—Kšœžœ
˜šžœ	ž˜Kš
œ2™2Kš
œ4˜4—K˜K˜—š œžœ
žœV˜{Kš
œ%™%Kš
œe™eKšžœ
žœžœ
˜Kš
œ.˜.Kš
œ™Kš
œ˜Kš
œ˜K™—š œžœžœžœžœžœ˜\š
œ7™7Kš
œ™—Kšœ
žœžœ	žœ˜1Kšœžœ
˜šžœžœ
žœ
˜Kš
œ™—Kšžœžœžœ	žœ˜OKšœ&žœžœ˜2Kš
œ˜Kš
œJ˜JKš
œ5˜5Kšžœ
žœžœ	˜5Kš
œ˜šžœ
žœ˜Kš
œ&™&Kšžœ!žœ	˜0Kšžœžœ	˜(K˜—Kšžœžœžœ˜*Kš
œ˜—K˜š œžœžœ
žœ˜8š
œ,™,Kš
œC™C—Kš
œ˜—K˜—™3K™š 
œžœ
žœ˜+Kšœ
žœ˜šžœ
žœžœž˜FKš
œ˜—š
œ˜Kš
œ1™1—šžœ
žœ"žœ˜.Kš
œ™Kš
œ˜Kšžœ*žœ	˜9šžœ
ž˜˜
Kš
œ˜Kš
œ'˜'šžœ
žœ˜Kš
œ'˜'Kšžœžœžœ	˜.šžœžœžœžœ˜>Kšžœ	˜
—Kšžœ
žœžœ	˜,K˜—Kš
œ˜Kš
œ˜K˜—Kšžœ˜—Kš
œ˜—Kš
œ˜K™—š œžœ
Ÿœ
žœ˜=Kšœ
žœ˜Kšžœ
žœžœ	˜6šžœžœ˜Kšœxžœ™”
Kš
œN˜NKš
œQ˜QK˜—šžœ
žœž
œžœ˜4Kš
œE™EKš
œ˜Kšžœ*žœ	˜9šžœ
ž˜˜
Kš
œ˜Kš
œ'˜'šžœ
žœ˜Kš
œ'˜'Kšžœžœžœ	˜.šžœžœžœžœ˜>Kšžœ	˜
—Kšžœ
žœ!žœ	˜4K˜—Kš
œ˜Kš
œ˜K˜—Kšžœ˜—Kš
œ˜—Kš
œ˜K˜—š
 œžœ
žœ
žœžœ˜4Kš
œ™Kšžœ
žœžœ
˜Kš
œ˜Kš
œ˜K˜—š œžœ
žœ	žœ˜/Kš
œN˜NKš
œN˜NK˜—K˜—™
K˜š œžœ
žœžœ
žœžœ˜KKš
œ˜KšœžœŸ˜šžœžœ"žœžœ˜Sš
ž˜š
œ˜Kš
œ™Kš
œ0˜0—š
œ˜Kš
œ1™1Kš	œžœžœžœ
žœ˜CK˜Kšœ
žœ˜4Kšžœ
žœ
Ÿ˜%Kš
œ˜K˜—š
œ˜Kš
œ™Kš	œžœžœžœ
žœ˜CKš
œ˜Kšœ
žœ˜4Kšžœ
žœ
Ÿ˜%Kš
œ˜K˜—š
œ˜Kš
œ™Kš	œžœžœžœ
žœ˜CKš
œ&˜&Kšœ
žœ˜4Kšžœ
žœ
Ÿ˜%Kš
œ˜K˜—Kšžœ˜——Kšœ&Ÿ˜9Kšœ
žœ˜4Kšžœ
žœ
Ÿ˜%Kš
œ˜K˜—š
 œžœ
žœžœžœ˜AKš
œ˜KšœžœŸ˜šžœžœ"žœžœ˜Sš
ž˜Kšœ3Ÿ˜BšœŸ4˜;Kšœžœžœ
žœ˜6K˜Kšœ
žœ˜4Kšžœ
žœ
Ÿ˜%Kš
œ˜K˜—Kšžœ˜——Kšœ&Ÿ˜9Kšœ
žœ˜4Kšžœ
žœ
Ÿ˜%Kš
œ˜——K˜—™"K˜š œžœ
žœ
žœžœžœžœ˜MKšžœ ˜&Kš
œ˜K˜—š œžœ
žœ
žœžœžœžœ˜Všžœž˜Kšžœ
žœ˜Kšžœ
žœ˜ —Kš
œ˜K˜—š
 œžœ
žœžœ
žœ˜MKš
œ˜Kšœžœ
˜
KšœžœŸ˜Kš
œ˜Kš
œ%˜%Kš
œ˜Kšœ
žœ˜4Kšžœ
žœ	Ÿ˜$Kš
œ˜—K˜š œžœ
žœ
žœžœžœžœžœ˜RKšžœF˜LKš
œ˜K˜—š 	œžœ
žœ
žœžœ
žœžœžœ˜Lšžœ
žœ
ž˜šœžœ˜Kšžœžœ˜
—š
œE˜EKšžœ˜
—šžœ˜
Kšžœ'˜,——Kš
œ˜—K™—™
K˜š œŸ
žœ
žœ)˜JKš
œ!˜!šžœžœ
ž˜2Kšœžœ
˜Kšžœ
˜—Kš
œ˜K˜—š œžœ
žœ)˜CKšžœ
žœžœ
˜Kš
œ˜Kš
œ˜K˜—š œŸœ
žœ)˜RKš
œ!˜!šžœžœ
ž˜2Kšœžœ
˜Kšžœ
˜—Kš
œ˜K˜—š œžœ
žœ%žœžœžœ˜_Kšžœ
žœžœ
˜Kšžœ#˜)Kš
œ˜K˜—š œŸœ
žœ&žœžœžœ˜nšžœžœ
ž˜2Kš
žœ
žœžœ
žœžœ˜)Kšžœ
˜—Kš
œ˜K˜———š
œ™K˜š œžœ
žœžœžœžœžœ˜jKšžœ
žœ˜Kšžœ.˜4K˜K˜—š œžœžœžœžœžœ˜_Kš
œE™EKšœ6žœ™MKš
œK™KKš
œ
™
Kšœžœ
˜šžœž˜Kšœžœ$˜+š
œ˜Kš
œ™šœžœžœž˜2KšžœI™Lšœžœ$˜;K™—šœžœ(˜@Kš
œ™—šœžœ*˜CK™—šžœ˜!K™——Kšœ0žœ˜NKšœ
žœ˜'Kš
œžœ
žœ
žœžœ	žœžœ˜aKš
œ&˜&šžœ˜
š
ž˜Kš
œG˜G—š
ž˜Kš
œL˜L——šžœžœ
žœ˜Kš
œ&™&Kš
œ˜šœ-žœ
˜?KšœΆ
žœ™Ο
—šžœ	ž˜Kš
œ4™4Kš
œB˜B—Kš
œ˜K˜—Kš
œ˜Kšœžœ˜šžœžœž˜7Kš
œu™uKš
œ˜—Kšœ
žœ&žœ˜RKš
œ˜Kš
œ˜K˜—šžœ˜Kšœž™Kš
œ˜Kš
œ#˜#Kšœžœ˜Kš
œ$˜$Kš
œ˜Kšœžœ˜!šžœ˜
šžœ˜Kš
œ4™4Kš
œ(˜(Kš
œD˜DK˜
—šžœ˜K™Kš
œH˜HK˜——Kš
œ˜Kš
œ˜Kš
œ˜K˜——Kšžœ
žœžœ	˜6K˜K˜—š œžœžœ˜0Kš
œS™Sšžœžœžœžœžœžœ˜XKšœžœžœ˜EKšžœžœ	˜$šžœ
žœ
ž˜š
œ-˜-Kš
œ™Kšœžœžœ˜Gšžœ
ž˜˜
Kšœžœ˜ Kš
œ˜Kš
œ!˜!Kš
œ˜Kšžœžœ	˜Kšžœžœ#žœ
žœ	˜Ušžœ˜
šžœ˜Kš
œ˜Kš
œA˜AK˜
—š
ž˜Kš
œF˜F——Kš
œ˜Kšžœ
˜K˜—Kšžœ
˜—K˜—šžœ˜Kš
œF™FKš
œ3˜3Kš
œžœ
žœ
žœžœ	žœžœ˜aKšœžœ˜>šžœ˜
š
ž˜Kš
œE˜E—š
ž˜Kš
œJ˜J——Kš
œ˜Kš
œ˜Kš
œ˜Kš
œ˜Kšžœ
˜K˜——K˜—Kšžœžœ
žœ	˜K˜K˜—šœžœ
žœ
žœ'˜HKš
œL™L—šœžœ
žœ
žœ'˜JKš
œD™D—K˜š œžœ
žœžœ
žœ
žœ˜JKšœžœžœžœ˜4Kšœ
žœžœžœ˜?Kšžœ˜Kšœžœ
žœ&˜7Kšœžœ˜!K˜—K™—™	K˜š
 
œžœžœžœžœ˜;Kš
œζ™ζKšœžœžœŸ˜1KšœžœžœŸ+˜KKšžœ
žœ
žœ	˜&šžœ%žœ˜-Kšœžœ˜šžœž˜Kšœ Ÿ*˜JKšœ"Ÿ˜7Kšœ%Ÿ˜AKšœ%Ÿ ˜EKšœ%Ÿ˜DKšžœ Ÿ!˜H—Kš
ž˜K˜—šžœ'ž˜-Kš
œ(™(Kšžœ˜$K˜—Kš
œ(™(Kšžœžœžœžœ˜:Kš
œ˜—K˜š 	œžœžœžœ˜6Kšœžœ˜'šžœ˜!Kšžœ
žœžœ˜7Kšžœ
žœ!˜,—Kš
œ˜K˜—š
 œžœžœžœžœ˜=Kšžœžœ+˜;Kš
œ˜K˜—š
 œžœžœ	žœžœ˜Kšžœ
ž˜Kš
œ#˜#Kšœžœ!˜4Kšžœ˜—Kš
œ˜—K˜š
’	œžœžœ	žœžœ˜?šžœ˜!Kšžœ
žœ ˜+šžœ˜Kš
œ˜šžœ
ž˜Kš
œ"˜"Kšœžœ!˜4Kšžœ˜—Kšžœ	˜K˜——Kš
œ˜K˜—š
’œžœžœžœžœ˜:šžœ˜!Kšžœ
žœ"žœ˜@Kšžœ
žœ%žœ˜F—Kš
œ˜K˜—š œžœžœ	žœ˜8Kšžœ;˜AK˜K˜—š œžœžœžœ˜9Kšžœ=˜CK˜K˜—š
 	œžœžœžœžœ˜;Kšžœ;˜AK˜K˜—š
 	œžœ	žœžœžœ˜>KšžœS˜YK˜K˜—š
 	œžœ	žœžœžœ˜BKšžœ"žœ
žœ	˜8Kš
œ$˜$KšžœI˜OK˜K˜—š
 	œžœžœ	žœžœ˜Bšžœ!˜#Kšžœ
žœ˜Kšžœ
žœE˜P—K˜—K˜š œžœžœžœ˜<Kšžœ˜K˜K˜—š œžœžœžœ˜<Kšžœžœžœžœ˜OK˜K˜—š 	œžœžœžœ˜?Kšžœ˜K˜K˜—Kš	œžœžœ
žœ
žœ
˜3š	œ
žœžœ
ž	œ
žœ˜.Kšœ
žœ
˜Kšœ
žœ˜K˜—š
 œžœžœžœžœ˜?šžœ	žœ
žœ+˜IKšœ
žœžœžœ™:—K˜K˜—šœžœžœ˜2Kš	œžœžœžœžœ˜MKš
œ)˜)—K˜š
 œžœžœžœžœ˜Lšžœ	žœ
˜Kšœžœ
žœ*˜@Kšœžœ
žœ"˜8Kš
œ˜—K˜K˜—šœžœžœ˜2Kšœžœžœžœ˜@Kš
œ)˜)—K˜š œžœžœ˜%Kšœžœ
˜šžœž˜Kš
œ#˜#Kš
œ˜Kš
œ˜Kšžœ
˜—Kš
œ2˜2Kš
œ˜K˜—š
 œžœžœžœžœ˜&Kšžœ˜Kš
œ˜K˜—š
 œžœžœžœžœ˜&š
ž˜Kšœžœžœ˜Kšžœžœ
žœ˜K˜K˜Kšžœ
˜—K˜—K˜š
 	œžœ#žœžœžœ)˜pKš
œ2™2Kšœžœ˜!šœ
žœžœ
˜$Kš
œ:˜:Kšœžœžœ
žœ˜Kš
œ˜—Kšžœ˜Kš
œ˜Kš
œ=˜=Kšžœ	žœ˜#Kš
œ˜K˜—š 
œžœ)˜9Kš
œ2™2Kšžœ3˜5Kš
œ5˜5Kš
œ˜—K™š 
œžœ
žœ˜Kš
œZ™ZKšœ
žœžœžœžœžœ˜VKšžœE˜Mš
žœžœ
žœžœ
žœ˜9Kšœžœ˜—š
œ
˜
Kšœžœ
žœB˜P—K˜3K˜K˜—š œžœ
žœ˜Kš
œŠ
™Š
Kšœžœ
žœ˜Kšœžœ
žœ˜K˜K˜—š œžœ˜Kš
œ/˜/K˜K˜——š
œ
™
K˜š
œ
˜
Kš
œ"™"Kšœžœ˜Kš
œ˜K˜K™=Kš
žœžœžœžœ
žœ
˜EK˜šžœŸ
œžœž˜KKš	œžœžœ
žœžœ˜6šžœžœ˜Kš
œ™Kšžœžœ	˜$Kš
œ˜Kš
œ˜Kš
œ˜K˜—Kš
œ˜Kšžœ
˜K˜—Kš
œ*™*Kš
œ˜——K˜—Kšžœ
˜K˜™,KšœΟrK™W—K™™,Kšœ£(™4—™3Kš
œq™q—K™K™—…—k΄΄Ί