Histogram:
TYPE = RECORD[
counts: ARRAY LogRunLenght OF INT,
freeSpace: ARRAY LogRunLenght OF INT,
mixEndsAlloc: INT,
mixEndsFree: INT,
mixAdjMix: INT
] ← [ALL[0], ALL[0], 0, 0, 0];
computeHistogram:
PROCEDURE[volume: File.Volume]
RETURNS[ histogram: Histogram ] =
TRUSTED
BEGIN
vamFile: File.Handle = File.Open[volume, FileBackdoor.GetRoot[volume, VAM].fp];
filePages: INT = File.Info[vamFile].size;
fileWords: INT = File.wordsPerPage * filePages;
limit: INT = FileBackdoor.GetVolumePages[volume].size;
interval: VM.Interval = VM.Allocate[VM.PagesForWords[fileWords]];
buffer: LONG POINTER TO bufferObject ← VM.AddressForPageNumber[interval.page];
bufferObject: TYPE = RECORD[ SEQUENCE COMPUTED CARDINAL OF WORD ];
state: {alloc, free, mixed} ← alloc;
all0: WORD = 000000B;
all1: WORD = 177777B;
updateHistogram:
SAFE
PROCEDURE =
CHECKED BEGIN
OPEN histogram;
logRun ← MIN[ Real.Fix[RealFns.Log[4, runCount]], 6 ];
counts[logRun] ← counts[logRun]+1;
freeSpace[logRun] ← freeSpace[logRun]+runCount;
END;
runCount: INT ← 0; -- Length of the current free run
logRun: LogRunLenght;
File.Read[file: vamFile, from: [0], to: LOOPHOLE[buffer], nPages: filePages];
BEGIN OPEN histogram;
Proceed with an FSM analysis of the VAM. Sixteen bit blocks containing both 0s and 1s are counted as "Mixed", and are distinguished as to whether they follow a free block, an allocated block or a mixed block. As a result, the computed lenght of any particular run may be up to 30 blocks shorter than it really is.
FOR i:
INT ← 0, i+1
WHILE i < limit/16
DO
SELECT state
FROM
alloc => {
SELECT buffer[i]
FROM
all1 => NULL;
all0 => {
state ← free;
runCount ← 16;
};
ENDCASE => {
state ← mixed;
mixEndsAlloc ← mixEndsAlloc+1;
};
};
free => {
SELECT buffer[i]
FROM
all1 => {
updateHistogram;
state ← alloc;
};
all0 => {
runCount ← runCount+16;
};
ENDCASE => {
updateHistogram;
state ← mixed;
mixEndsFree ← mixEndsFree+1;
};
};
mixed => {
SELECT buffer[i]
FROM
all1 => {
state ← alloc;
};
all0 => {
state ← free;
runCount ← 16;
};
ENDCASE => {
mixAdjMix ← mixAdjMix+1;
};
};
ENDCASE;
ENDLOOP;
IF state=free
THEN {
updateHistogram;
};
VM.Free[interval];
END;
END;
HistoVAMProc: Commander.CommandProc = {
[cmd: Commander.Handle] RETURNS [result: REF ANY ← NIL, msg: ROPE ← NIL]
argv: CommandTool.ArgumentVector;
volume: File.Volume;
volumeName: Rope.ROPE;
histogram: Histogram;
argv ← CommandTool.Parse[cmd: cmd
! CommandTool.Failed => { msg ← errorMsg; CONTINUE; }];
IF argv = NIL THEN GOTO Failed;
IF argv.argc = 1
THEN {
volume ← File.SystemVolume[];
volumeName ← File.GetVolumeName[volume];
}
ELSE {
IF argv.argc # 2 THEN GOTO Usage;
volume ← File.FindVolumeFromName[argv[1]];
volumeName ← argv[1];
};
IF volume = NIL THEN GOTO NoVolume;
histogram ← computeHistogram[volume];
cmd.out.PutF[ "Distribution of free page run sizes on Volume: %g:\n", IO.rope[volumeName] ];
cmd.out.PutF[ "\tSizes\t\tnRuns\t\tSpace\n" ];
cmd.out.PutF[ "\t1..15\t\t\t%g\t\t~8*%g\n", IO.int[histogram.mixEndsAlloc+histogram.mixEndsFree+histogram.mixAdjMix], IO.int[histogram.mixEndsAlloc+histogram.mixEndsFree+histogram.mixAdjMix] ];
cmd.out.PutF[ "\t16..63\t\t\t%g\t\t%g\n", IO.int[histogram.counts[2]], IO.int[histogram.freeSpace[2]] ];
cmd.out.PutF[ "\t64..255\t\t%g\t\t%g\n", IO.int[histogram.counts[3]], IO.int[histogram.freeSpace[3]] ];
cmd.out.PutF[ "\t256..1023\t\t%g\t\t%g\n", IO.int[histogram.counts[4]], IO.int[histogram.freeSpace[4]] ];
cmd.out.PutF[ "\t1024..4095\t\t%g\t\t%g\n", IO.int[histogram.counts[5]], IO.int[histogram.freeSpace[5]] ];
cmd.out.PutF[ "\t4096...\t\t\t%g\t\t%g\n", IO.int[histogram.counts[6]], IO.int[histogram.freeSpace[6]] ];
EXITS
Failed => RETURN[$Failure, msg];
Usage => RETURN[$Failure, " Usage: ShowVAM volumename\n"];
NoVolume => RETURN[$Failure, " No such volume\n"];
};
Commander.Register[key: "HistoVAM", proc: HistoVAMProc, doc: "Show a histogram of free run lenghts in the VAM (volume allocation map) of the given logical volume (SystemVolume if omitted)"];