-- SpaceWatch.mesa
-- last edited by John Maxwell on February 8, 1983 11:16 am
-- last edited by Paul Rovner on February 10, 1983 10:14 am
DIRECTORY
CachedSpace USING [Desc],
CommonSoftwareFileTypes,
ConvertUnsafe USING [ToRope],
DCSFileTypes,
Directory USING [GetProperty, Lookup],
File USING [
Capability, GetAttributes, ID, nullCapability, nullID, PageNumber, Unknown, Type],
FileCacheImpl USING [GetPageGroup],
FileInternal USING [PageGroup],
Hierarchy USING [GetDescriptor],
IO USING [card, char, CR, CreateViewerStreams, int, STREAM, Put, PutF, rope, SP],
KernelFile USING [GetNextFile],
PageMap USING [GetF, flagsVacant],
PilotFileTypes,
Projection USING [Get],
PropertyTypes USING [tFileName],
Rope USING [Concat, Equal, Find, Length, ROPE, Substr],
Space USING [
defaultWindow, GetAttributes, GetWindow, Handle, nullHandle,
PageCount, PageNumber, virtualMemory, VMPageNumber, WindowOrigin],
SpaceImplInternal USING [EnterSpace],
System USING [UniversalID],
UserExec USING [CommandProc, RegisterCommand],
Volume USING [ID, systemID];
SpaceWatch: PROGRAM
IMPORTS
ConvertUnsafe, Directory, File, FileCacheImpl, Hierarchy, IO,
KernelFile, PageMap, Projection, Rope, Space, SpaceImplInternal, UserExec, Volume
SHARES File, PageMap =
BEGIN
OPEN IO;
ROPE: TYPE = Rope.ROPE;
cedarVM: File.ID;
bootFile: File.ID ← File.nullID;
pages: RECORD[cedar, pilot, code, unmapped, unknown, anon, vm, resident, other: INT ← 0];
printIn: BOOL ← FALSE;
-- printLargest: BOOL ← FALSE; see PDR
ExecPrintSpaces: UserExec.CommandProc = TRUSTED {DoIt[]};
DoIt: PROC[summaryOnly: BOOL ← FALSE] =
BEGIN
indent: ROPE;
count: INT ← 0;
stream: IO.STREAM;
last: Space.PageNumber ← 0; -- the first page number following the space most recently seen
page: Space.PageNumber;
vmPages: Space.PageNumber;
free: Space.PageCount ← 0;
largest: Space.PageCount ← 0;
pinned: Space.PageCount ← 0;
swappedIn: Space.PageCount ← 0;
PrintBackingFiles: PROC[space: Space.Handle, depth: INTEGER] = {
default: BOOL;
mapped: BOOL;
child: Space.Handle;
size: Space.PageCount;
window: Space.WindowOrigin;
in: CARDINAL ← 0;
[lowestChild: child, size: size, mapped: mapped] ← Space.GetAttributes[space];
page ← Space.VMPageNumber[space];
-- indicate free regions
IF depth = 1 THEN {
count ← count + 1;
IF NOT summaryOnly AND page > last
THEN stream.Put[rope["****** "], int[page - last], rope[" free pages *****\n"]];
free ← free + page - last;
largest ← MAX[largest, page - last];
last ← page + size};
-- print line for space
IF NOT summaryOnly AND indent.Length # 0 THEN stream.Put[rope[indent]];
IF NOT summaryOnly THEN stream.PutF["page: %5d size: %4d", int[page], int[size]];
-- if unmapped then print any subspaces
IF ~mapped THEN { -- indicate subspaces by indentations
IF depth = 1 THEN pages.unmapped ← pages.unmapped + size;
IF child = Space.nullHandle THEN { -- no subspaces
IF NOT summaryOnly THEN stream.Put[rope[" (unmapped)"], char[CR]];
RETURN};
IF NOT summaryOnly THEN stream.Put[char[CR]];
indent ← Rope.Concat[" ", indent];
EnumerateChildren[space, PrintBackingFiles, depth];
indent ← Rope.Substr[indent, 0, indent.Length[]-3];
RETURN};
-- if mapped then print backing file
IF depth # 1 THEN pages.unmapped ← pages.unmapped - size;
default ← FALSE;
window ← Space.GetWindow[space];
IF window = Space.defaultWindow THEN {
FindBackingFile: PROC = {
desc: CachedSpace.Desc;
validSpace, validSwapUnit: BOOL;
[validSpace, validSwapUnit] ← Hierarchy.GetDescriptor[@desc, LOOPHOLE[space]];
IF ~(validSpace OR validSwapUnit) OR desc.dataOrFile ~= data THEN ERROR;
window ← desc.window};
default ← TRUE;
SpaceImplInternal.EnterSpace[FindBackingFile]};
IF NOT summaryOnly THEN stream.Put[rope[" file: "]];
PrintFile[(IF NOT summaryOnly THEN stream ELSE NIL),
window.file, window.base, size, default];
IF Projection.Get[page].state = inPinned THEN {
IF NOT summaryOnly THEN stream.Put[rope[" (pinned)"]];
swappedIn ← swappedIn + size;
pinned ← pinned + size;
IF NOT summaryOnly THEN stream.Put[char[CR]];
RETURN};
IF NOT summaryOnly AND child # Space.nullHandle THEN
IF Projection.Get[page].hasSwapUnits
THEN stream.Put[rope[", swapUnitSize: "], card[Space.GetAttributes[child].size]]
ELSE stream.Put[rope[", firstChild: "], card[Space.GetAttributes[child].size]];
FOR i: CARDINAL IN [0..size) DO
IF PageMap.GetF[page+i].valueOld.flags # PageMap.flagsVacant THEN in ← in + 1;
ENDLOOP;
IF NOT summaryOnly AND printIn AND in # 0
THEN stream.Put[rope[", pagesIn: "], card[in]];
swappedIn ← swappedIn + in;
IF NOT summaryOnly THEN stream.Put[char[CR]];
-- IF printLargest AND size > 20 AND child # Space.nullHandle THEN {
-- indent ← Rope.Concat[" ", indent];
-- EnumerateChildren[space, PrintLargeSpaces, depth];
-- indent ← Rope.Substr[indent, 0, indent.Length[]-3]}
}; -- end PrintBackingFiles
PrintLargeSpaces: PROC[space: Space.Handle, depth: INTEGER] = {
child: Space.Handle;
size: Space.PageCount;
[lowestChild: child, size: size] ← Space.GetAttributes[space];
IF size < 20 THEN RETURN;
IF child # Space.nullHandle
THEN EnumerateChildren[space, PrintLargeSpaces, depth]
ELSE IF NOT summaryOnly
THEN stream.PutF["%gpage: %5d size: %4d (swap unit)\n",
rope[indent], int[Space.VMPageNumber[space]], int[size]]};
-- START DoIt HERE --
pages ← [];
vmPages ← Space.GetAttributes[Space.virtualMemory].size;
stream ← IO.CreateViewerStreams["VM Space Log"].out;
stream.Put[rope["SpaceWatch.DoIt["]];
IF summaryOnly THEN stream.Put[rope["summaryOnly: TRUE"]];
stream.Put[rope["]\n"]];
IF NOT summaryOnly
THEN stream.Put[rope["'#' indicates a space mapped to Space.defaultWindow.\n\n"]];
cedarVM ← Directory.Lookup["CedarVM.DontDeleteMe"].fID;
-- do the work
EnumerateChildren[Space.virtualMemory, PrintBackingFiles, 0];
IF NOT summaryOnly
THEN stream.Put[rope["****** "], int[vmPages - last], rope[" free pages *****\n"]];
free ← free + vmPages - last;
largest ← MAX[largest, vmPages - last];
stream.Put[char[CR]];
stream.Put[rope["General Statistics ...\n"]];
stream.Put[rope[" Total pages in VM = "], int[vmPages], rope[".\n"]];
stream.Put[rope[" Total top level spaces = "], int[count], rope[".\n"]];
stream.Put[rope[" Total pages swapped in = "], int[swappedIn], rope[".\n"]];
stream.Put[rope[" Total pages pinned = "], int[pinned], rope[".\n"]];
stream.Put[rope[" Largest run of free pages = "], int[largest], rope[".\n"]];
stream.Put[rope[" Total free pages = "], int[free], rope[".\n\n"]];
stream.Put[rope["VM allocation breakdown ...\n"]];
stream.Put[rope[" Pilot pages (total never changes) = "], int[pages.pilot], rope[".\n"]];
stream.Put[rope[" Permanently pinned pages with no backing file = "],
int[pages.resident], rope[".\n"]];
stream.Put[rope[" Bootfile and .bcd file pages (code, BCD headers, symbols) = "],
int[pages.code], rope[".\n"]];
stream.Put[rope[" Pages from other mapped files = "], int[pages.other], rope[".\n"]];
stream.Put[rope[" Pages from files with unknown file types = "],
int[pages.unknown], rope[".\n"]];
stream.Put[rope[" Anonymous backing store mapped to VMBackingFile = "],
int[pages.vm], rope[".\n"]];
stream.Put[rope[" Anonymous backing store mapped to anonymous files = "],
int[pages.anon], rope[".\n"]];
stream.Put[rope[" CedarVMFile pages = "], int[pages.cedar], rope[".\n"]];
stream.Put[rope[" Unmapped pages = "], int[pages.unmapped], rope[".\n\n"]];
stream.Put[rope[" TOTAL = "],
int[pages.pilot+pages.resident+pages.code
+pages.other+pages.unknown+pages.vm
+pages.anon+pages.cedar+pages.unmapped],
rope[".\n"]];
END;
EnumerateChildren: PROC [space: Space.Handle, proc: PROC [Space.Handle, INTEGER],
depth: INTEGER] =
BEGIN
FOR child: Space.Handle ←
Space.GetAttributes[space].lowestChild,
Space.GetAttributes[child].nextSibling
UNTIL child = Space.nullHandle DO proc[child, depth + 1]; ENDLOOP;
END;
PrintFile: PROC[stream: IO.STREAM,
cap: File.Capability,
page: File.PageNumber,
size: Space.PageCount,
default: BOOL] =
BEGIN
OPEN DCSFileTypes, PilotFileTypes;
type: File.Type;
fileName: STRING ← [130];
temporary, fileError: BOOL ← FALSE;
IF cap.fID = File.nullID THEN {
IF stream # NIL THEN stream.Put[rope["resident"]];
pages.resident ← pages.resident + size; RETURN};
IF cap.fID = cedarVM THEN {
IF stream # NIL THEN stream.Put[rope["CedarVM"]];
pages.cedar ← pages.cedar + size; RETURN};
[type, , temporary, ] ← File.GetAttributes[cap
! File.Unknown => {fileError ← TRUE; CONTINUE}];
IF fileError THEN {
PrintID[cap.fID, stream];
IF stream # NIL THEN stream.Put[rope[" (File.Unknown)"]];
pages.unknown ← pages.unknown + size; RETURN};
SELECT type FROM
tLeaderPage => {
name: Rope.ROPE;
fileName.length ← 0;
Directory.GetProperty[cap, PropertyTypes.tFileName,
DESCRIPTOR[fileName, 66]];
name ← ConvertUnsafe.ToRope[fileName];
IF name.Length[] = 0 THEN {
Directory.GetProperty[cap, LOOPHOLE[213B], -- tRemoteFileName
DESCRIPTOR[fileName, 66]];
name ← ConvertUnsafe.ToRope[fileName]};
IF stream # NIL THEN
IF name.Length[] = 0
THEN {PrintID[cap.fID, stream]; stream.Put[rope[" (unnamed)"]]}
ELSE stream.Put[rope[name]];
SELECT TRUE FROM
name.Find[".bcd", 0, FALSE] > 0 => pages.code ← pages.code + size;
name.Equal["Volume.DirectoryTree"] => pages.pilot ← pages.pilot + size;
ENDCASE => pages.other ← pages.other + size};
tTempFileList => {
IF stream # NIL THEN stream.Put[rope["tTempFileList"]];
pages.pilot ← pages.pilot + size};
tVolumeAllocationMap => {
IF stream # NIL THEN stream.Put[rope["VAM"]];
pages.pilot ← pages.pilot + size};
tVolumeFileMap => {
IF stream # NIL THEN stream.Put[rope["VFM"]];
pages.pilot ← pages.pilot + size};
CommonSoftwareFileTypes.tDirectory => {
IF stream # NIL THEN stream.Put[rope["Pilot Directory File"]];
pages.pilot ← pages.pilot + size};
tTransactionStateFile => {
IF stream # NIL THEN stream.Put[rope["TransactionStateFile"]];
pages.pilot ← pages.pilot + size};
tLogicalVolumeRootPage => {
IF stream # NIL THEN stream.Put[rope["LogicalVolumeRootPage"]];
pages.pilot ← pages.pilot + size};
tAnonymousFile => {
PrintID[cap.fID, stream];
IF stream # NIL THEN stream.Put[rope[" (anon.)"]];
pages.anon ← pages.anon + size};
tVMBackingFile => SELECT page FROM
IN [0..40) => {IF stream # NIL THEN stream.Put[rope["MapLog"]];
pages.pilot ← pages.pilot + size};
IN [40..150) => {IF stream # NIL THEN stream.Put[rope["SystemBTrees"]];
pages.pilot ← pages.pilot + size};
ENDCASE => {IF stream # NIL THEN stream.Put[rope["VMBackingFile"]];
pages.vm ← pages.vm + size};
ENDCASE => {
IF bootFile = File.nullID THEN bootFile ← cap.fID; -- always the first one
IF cap.fID = bootFile
THEN {IF stream # NIL THEN stream.Put[rope["BootFile"]];
pages.code ← pages.code + size}
ELSE {PrintID[cap.fID, stream];
IF stream # NIL THEN stream.Put[rope[" (unknown type)"]];
pages.unknown ← pages.unknown + size}};
IF default AND stream # NIL THEN stream.Put[rope["#"]];
IF temporary AND stream # NIL THEN stream.Put[rope[" (temp.)"]];
END;
PrintID: PROC[id: System.UniversalID, stream: IO.STREAM] =
BEGIN
idRep: RECORD[a, b, c, d, e: CARDINAL] ← LOOPHOLE[id];
IF stream = NIL THEN RETURN;
stream.Put[char[SP], card[idRep.a]];
stream.Put[char[SP], card[idRep.b]];
stream.Put[char[SP], card[idRep.c]];
stream.Put[char[SP], card[idRep.d]];
stream.Put[char[SP], card[idRep.e]];
END;
PrintFileMap: PROC =
BEGIN
success: BOOL;
page: File.PageNumber;
stream: IO.STREAM;
length: LONG CARDINAL;
group: FileInternal.PageGroup;
volume: Volume.ID ← Volume.systemID;
file: File.Capability ← File.nullCapability;
stream ← IO.CreateViewerStreams["FileMap.log"].out;
stream.Put[rope["SpaceWatch.PrintFileMap[]\n"]];
WHILE (file←KernelFile.GetNextFile[volume,file])#File.nullCapability DO
stream.Put[rope["file: "]];
PrintFile[stream, file, 200, 0, FALSE];
stream.Put[rope[" = "]];
page ← 0;
DO -- until we run out of page groups --
[success, group] ← FileCacheImpl.GetPageGroup[file.fID, page];
IF ~success THEN EXIT;
length ← group.nextFilePage - group.filePage;
page ← group.nextFilePage;
IF length=0 THEN EXIT;
stream.Put[rope["("], card[length], rope[")"]];
ENDLOOP;
stream.Put[char[CR]];
ENDLOOP;
END;
UserExec.RegisterCommand["SpaceWatch", ExecPrintSpaces, "prints the current VM."];
END . .
DisplayVAM:PROC = {
width:CARDINAL = 200;
context:Graphics.Context ← Graphics.NewContext[];
volume:Volume.ID ← Volume.systemID;
page,volSize:LONG CARDINAL ← 0;
point:Graphics.Box;
x,y:LONG CARDINAL ← 0;
busy:BOOL←FALSE;
getVolSize:LogicalVolume.VolumeAccessProc = {
updateMarkers ← FALSE;
volSize ← volume.volumeSize};
getVAM:LogicalVolume.VolumeAccessProc = {
updateMarkers ← FALSE;
busy ← VolAllocMapImpl.AccessVAM[volume, page, FALSE, FALSE]};
[] ← Graphics.SetFat[context, TRUE];
[] ← VolumeImpl.VolumeAccess[@volume, getVolSize, FALSE];
point ← [0,0,width*4,4*(volSize+width-1)/width];
Graphics.SetColor[context, Graphics.white];
Graphics.DrawBox[context, point];
Graphics.SetColor[context, Graphics.black];
FOR page IN [0..volSize) DO
[] ← VolumeImpl.VolumeAccess[@volume, getVAM, FALSE];
IF ~busy THEN LOOP;
x ← (page MOD width)*4;
y ← (page/width)*4;
point ← [x,y,x+3,y+3];
Graphics.MoveTo[context, x, y];
Graphics.DrawBox[context, point];
ENDLOOP};
Error:SIGNAL = CODE;
GetFileCacheInfo:PROC RETURNS[pinned,notPinned:LONG CARDINAL] = {
OPEN FileCacheImpl;
file:FileCEptr;
pg:PageGroupCEptr;
length:LONG CARDINAL;
pinned ← notPinned ← 0;
FOR file ← LOOPHOLE[FCache.mru], LOOPHOLE[base[file].next] DO
IF file=nilCEptr THEN EXIT;
FOR pg ← base[file].pgList, LOOPHOLE[base[pg].next] DO
IF pg=nilCEptr THEN EXIT;
length ← base[pg].group.nextFilePage - base[pg].group.filePage;
IF base[pg].pinned AND length>10000 THEN LOOP; -- skip VAM, VFM
IF base[pg].pinned
THEN pinned ← pinned + length
ELSE notPinned ← notPinned + length;
ENDLOOP;
ENDLOOP};
MeasureFileCache:PROC[init,pinned:BOOL] = {
OPEN FileCacheImpl;
file:FileCEptr;
pg:PageGroupCEptr;
length:LONG INTEGER;
IF init THEN hist ← ALL[[0,0,0,FALSE]];
boundary ← distribution1;
FOR file ← LOOPHOLE[FCache.mru], LOOPHOLE[base[file].next] DO
IF file=nilCEptr THEN EXIT;
FOR pg ← base[file].pgList, LOOPHOLE[base[pg].next] DO
IF pg=nilCEptr THEN EXIT;
length ← base[pg].group.nextFilePage - base[pg].group.filePage;
IF base[pg].pinned AND length>10000 THEN LOOP; -- skip VAM, VFM
IF pinned=base[pg].pinned THEN AddToHistogram[length];
ENDLOOP;
ENDLOOP};
MeasureFileMap:PROC = {
volume:Volume.ID ← Volume.systemID;
success:BOOL;
file:File.Capability ← File.nullCapability;
group:FileInternal.PageGroup;
page:File.PageNumber;
length:LONG INTEGER;
hist ← ALL[[0,0,0,FALSE]];
boundary ← distribution1;
WHILE (file←KernelFile.GetNextFile[volume,file])#File.nullCapability DO
page ← 0;
DO -- until we run out of page groups --
[success, group] ← GetPageGroup[file, page];
IF ~success THEN EXIT;
length ← group.nextFilePage - group.filePage;
page ← group.nextFilePage;
IF length=0 THEN EXIT;
AddToHistogram[length];
ENDLOOP;
ENDLOOP};
GetPageGroup:PROC[file:File.Capability,page:File.PageNumber]
RETURNS[success:BOOL, group:FileInternal.PageGroup] = {
volume:Volume.ID ← Volume.systemID;
fileD:FileInternal.Descriptor;
getPageGroup:LogicalVolume.VolumeAccessProc = {
updateMarkers ← FALSE;
[success, group] ← VolFileMapImpl.GetPageGroup[volume, @fileD, page]};
IF ~FileImpl.GetFileDescriptor[@file, @fileD, @volume] THEN ERROR;
[success, group] ← FileCacheImpl.GetPageGroup[File.ShowCapability[file].fID, page];
IF success THEN RETURN;
[] ← VolumeImpl.VolumeAccess[@volume, getPageGroup, FALSE]};
GetMap:PROC[handle:CachedSpace.Handle] RETURNS[
file:File.Capability,base:File.PageNumber,mapped:BOOL] = {
spaceDesc:CachedSpace.Desc;
file ← File.nullCapability;
base ← 0;
[] ← HierarchyImpl.GetDescriptor[@spaceDesc, handle];
mapped ← spaceDesc.state IN [mapped..beingRemapped];
IF ~mapped THEN Error;
[file,base] ← spaceDesc.window};
break1:ARRAY [0..10) OF Number;
break2:ARRAY [0..10) OF Number;
nil:RECORD[descs,pages:INTEGER];
MeasureSwapUnits:PROC = {
OPEN Space;
file:File.Capability ← File.nullCapability;
desc:CachedRegion.Desc;
spaceDesc:CachedSpace.Desc;
size,count,countMapped:CARDINAL;
mapped,nilFile:BOOL;
group:FileInternal.PageGroup;
base,filePage:File.PageNumber;
VMpage,start:Space.PageNumber𡤀
VMMax:Space.PageNumber ← GetAttributes[virtualMemory].size;
success:BOOL;
hist ← ALL[[0,0,0,FALSE]];
break1 ← break2 ← ALL[0];
nil ← [0,0];
boundary ← distribution2;
FOR VMpage IN [0..VMMax) DO
IF VMpage>=start THEN {
desc ← ProjectionImpl.Get[VMpage];
IF desc.state IN [missing..checkedOut] THEN Error;
IF ~(desc.state IN CachedRegion.Mapped) THEN LOOP;
[] ← HierarchyImpl.GetDescriptor[@spaceDesc, [desc.levelMapped, VMpage]];
IF VMpage >= spaceDesc.interval.page + spaceDesc.countMapped THEN LOOP;
[file, base, mapped] ← GetMap[[desc.levelMapped, VMpage]];
base ← base + (VMpage - spaceDesc.interval.page);
countMapped ← spaceDesc.countMapped;
[] ← HierarchyImpl.GetDescriptor[@spaceDesc, [desc.level, VMpage]];
IF ~desc.hasSwapUnits
THEN size ← MIN[desc.interval.count, countMapped]
ELSE size ← spaceDesc.sizeSwapUnit;
start ← VMpage + size;
nilFile ← File.ShowCapability[file].fID = File.nullID;
IF nilFile THEN {nil.descs←nil.descs+1; nil.pages←nil.pages+1; LOOP};
AddToHistogram[size];
count ← 0;
filePage ← base;
DO -- over the page groups in a desc
IF filePage>= base+size THEN EXIT;
[success, group] ← GetPageGroup[file, filePage];
IF ~success THEN EXIT;
IF group.nextFilePage=group.filePage THEN EXIT;
filePage ← group.nextFilePage;
count ← count+1;
ENDLOOP;
SELECT count FROM
0 => {break1[count] ← break1[count]+1; Error};
IN [1..8] => break1[count] ← break1[count]+1;
ENDCASE => break1[9] ← break1[9]+1};
IF ~mapped THEN LOOP;
-- conditional probabilities
IF nilFile THEN {nil.pages←nil.pages+1; LOOP};
AddToBucket[size,histLength];
SELECT count FROM
0 => {break2[count] ← break2[count]+1; Error};
IN [1..8] => break2[count] ← break2[count]+1;
ENDCASE => break2[9] ← break2[9]+1;
ENDLOOP};
--********************************************************************
--histogram manipulation
--********************************************************************
Number:TYPE = LONG INTEGER;
extra:CARDINAL = 1;
Histogram:TYPE = ARRAY [0..histLength+extra) OF RECORD[
count:Number,
total:Number,
average:Number,
overflow:BOOL];
-- the first bucket is used for totals
-- the second bucket is used for underflow
-- histLength-1 is used for overflow
-- the rest are for the client's use
hist:Histogram;
histLength:CARDINAL = 21;
boundary:ARRAY [0..histLength) OF Number;
distribution1:ARRAY [0..histLength) OF Number
← [0,0,1,2,3,4,5,10,15,20,30,40,50,100,150,200,250,300,500,1000,5000];
distribution2:ARRAY [0..histLength) OF Number
← [0,0,1,2,3,4,5,10,15,20,30,40,50,100,150,200,250,300,500,1000,5000];
AddToHistogram:PROC[entry:Number] =
INLINE BEGIN
AddToBucket[entry,0]; -- totals
FOR i:CARDINAL DECREASING IN [2..histLength) DO
IF entry<boundary[i] THEN LOOP; -- histLength-1 = overflow
AddToBucket[entry,i];
RETURN; ENDLOOP;
AddToBucket[entry,1]; -- underflow
END;
AddToBucket:PROC[entry:LONG INTEGER,i:CARDINAL] =
INLINE BEGIN
IF hist[i].overflow THEN RETURN;
IF hist[i].count+1<0 THEN {hist[i].overflow ← TRUE; RETURN};
hist[i].count ← hist[i].count + 1;
hist[i].total ← hist[i].total +entry;
IF hist[i].total >= entry THEN RETURN;
hist[i].overflow ← TRUE;
hist[i].total ← hist[i].total -entry; -- undo
END;
ComputeAverages:PROC =
BEGIN
FOR i:CARDINAL IN [0..histLength+extra) DO
IF hist[i].count = 0 THEN LOOP;
hist[i].average ← hist[i].total/hist[i].count;
ENDLOOP;
END;