-- DirectoryScavengerImplA.mesa (last edited by Fay on January 22, 1981 4:25 PM)

DIRECTORY

Ascii USING [BEL],

CommonSoftwareFileTypes USING [CommonSoftwareFileType, tDirectory],

Directory USING [Error, ErrorType, fileMaxPermissions, maxDirectoryNameLength, VolumeError],

DirectoryExtras USING [ScavengerContext, ScavengerError, ScavengerErrorType],

DirectoryInternal USING [
DirectoryDescriptor, DirectoryEntryHandle, DirectoryLock, DirectoryPageHandle,
DTNode, emptySize, initDirSize, initDTSize, leaderPageSize, maxDirSize,
nilPagePointer, PagePointer, PDT, pDTnil, PDTNode, swapUnitSize],

DirectoryProps USING [GetPropsInternal, PutPropertyInternal, SetCreateDate],

DirectoryScavenger USING [
BTreeInvalid, ClosePilotLogFile, DoNesting, EquivalentLongStrings, GetWords,
OpenPilotLogFile, ValidateBTree],

DirectoryTrees USING [
BTreeDelete, BTreeFind, BTreeGetNext, BTreeInsert, DTDelete, DTFind, DTFirst,
DTInsert, MoveLongString],

DCSFileTypes USING [tLeaderPage],

Environment USING [wordsPerPage],

File USING [
Capability, Create, Delete, delete, DeleteImmutable, GetAttributes, GetSize,
LimitPermissions, MakePermanent, PageCount, nullCapability, read, Type,
Unknown, write],

Inline USING [LowHalf],

PilotFileTypes USING [tScavengerLog],

PropertyTypes USING [tFileName, tParentDirectory],

Scavenger USING [FileEntry, Header, Problem],

Space USING [
Create, CreateUniformSwapUnits, Delete, ForceOut, GetAttributes, Handle,
LongPointer, Map, PageCount, Unmap, virtualMemory],

String USING [AppendNumber],

System USING [GreenwichMeanTime, VolumeID],

Volume USING [GetAttributes, ID, InsufficientSpace, SetRootFile, Unknown];

DirectoryScavengerImplA: MONITOR LOCKS DirectoryInternal.DirectoryLock

IMPORTS
Directory, DirectoryExtras, DirectoryInternal, DirectoryProps,
DirectoryScavenger, DirectoryTrees, File, Inline, Space, String, Volume

EXPORTS DirectoryExtras

SHARES File =

BEGIN

--Types

DirectoryStatus: TYPE = {ok, invalidBTree, nonexistent, notDirectoryType};

-- Global Variables (initialized by procedure Initialize)

anonCap: File.Capability; -- AnonDir (anonymous directory) file capability

anonFileNumber: CARDINAL;

dirDesc: DirectoryInternal.DirectoryDescriptor;

dirPage: DirectoryInternal.DirectoryPageHandle;

dirSpace: Space.Handle; -- Directory space; used for any directory manipulation

dTreeCap: File.Capability; -- Volume.DirectoryTree file capability

dTreeSpace: Space.Handle; -- Volume.DirectoryTree space

nonDirectoryFileCount: CARDINAL;

nonDirectoryFileCountString: STRING ← [10];

pDirDesc: POINTER TO DirectoryInternal.DirectoryDescriptor = @dirDesc;

pDT: DirectoryInternal.PDT; -- pointer to base of dTreeSpace

pDTNodeAnon: DirectoryInternal.PDTNode; -- relative pointer to Volume.DirectoryTree node for root of AnonDir subdirectories.

rootCap: File.Capability; -- RootDir file capability

sysCap: File.Capability; -- SysDir file capability

theError: DirectoryExtras.ScavengerErrorType;

uniqueAnonName: STRING ← [Directory.maxDirectoryNameLength];

-- Errors

ScavengerError: PUBLIC ERROR [error: DirectoryExtras.ScavengerErrorType] = CODE;

-- Public procedure

-- Scavenge: rebuild (or examine IF ~context.repair) the directory structure on context.volume.

Scavenge: PUBLIC ENTRY PROC [context: DirectoryExtras.ScavengerContext] =
BEGIN
ENABLE {
UNWIND => NULL;
DirectoryExtras.ScavengerError => {theError ← error; GOTO DirectoryError};
Directory.Error, Directory.VolumeError => {theError ← internalFailure; GOTO DirectoryError};
Volume.InsufficientSpace => GOTO VolumeInsufficientSpace};
Initialize[];
-- Create spaces for directory and Volume.DirectoryTree.
dirSpace ← Space.Create[DirectoryInternal.maxDirSize, Space.virtualMemory];
Space.CreateUniformSwapUnits[DirectoryInternal.swapUnitSize, dirSpace];
dirPage ← Space.LongPointer[dirSpace];
dTreeSpace ← Space.Create[DirectoryInternal.maxDirSize, Space.virtualMemory];
Space.CreateUniformSwapUnits[DirectoryInternal.swapUnitSize, dTreeSpace];
pDT ← Space.LongPointer[dTreeSpace];
-- Verify volume has a valid root directory file (create one if not).
ValidateRootDir[context];
-- Create a new Volume.DirectoryTree, and initialize it to contain only RootDir and itself.
CreateDTree[context];
-- Insert each file into its parent directory.

context.LogProc["
Directory Scavenger pass one: Insert files back into directories.
"L];

InsertFiles[context];
-- Check for a valid SysDir, and create one if necessary.
ValidateSysDir[context];
-- Walk the directories to delete any invalid entries. Also rebuild Volume.DirectoryTree.

context.LogProc["
Directory Scavenger pass two: Walk directories and delete invalid entries.
"L];

[] ← WalkDirectory[
context, rootCap,
IF context.repair THEN DirectoryTrees.DTFirst[pDT]
ELSE DirectoryInternal.pDTnil, 0];
String.AppendNumber[nonDirectoryFileCountString, nonDirectoryFileCount, 10];
context.LogProc[nonDirectoryFileCountString];

context.LogProc[" files with no leader page were found with valid directory entries
in pass two.
"L];

-- Delete directory space and Volume.DirectoryTree space.
Space.Delete[dirSpace];
Space.Delete[dTreeSpace];
EXITS
DirectoryError => RETURN WITH ERROR DirectoryExtras.ScavengerError[theError];
VolumeInsufficientSpace => RETURN WITH ERROR Volume.InsufficientSpace;
END; -- Scavenge

-- Internal procedures

-- CreateAnonDir: Create a new anonymous subdirectory in parentCap, and insert it in Volume.DirectoryTree.

CreateAnonDir: INTERNAL PROC [
context: DirectoryExtras.ScavengerContext, anonName: LONG STRING,
parentCap: File.Capability, pDTNodeIn: DirectoryInternal.PDTNode]
RETURNS [anonDirCap: File.Capability, pDTNodeOut: DirectoryInternal.PDTNode] =
BEGIN
anonNamePlusBEL: STRING ← [Directory.maxDirectoryNameLength + 1];
dirEntryHandle: DirectoryInternal.DirectoryEntryHandle;
ok, noRoom: BOOLEAN;
DirectoryTrees.MoveLongString[to: anonNamePlusBEL, from: anonName];
anonNamePlusBEL[anonNamePlusBEL.length] ← Ascii.BEL;
anonNamePlusBEL.length ← anonNamePlusBEL.length + 1;
MapDirectory[context, parentCap];
[ok: ok, noRoom: noRoom, ent: dirEntryHandle] ← DirectoryTrees.BTreeInsert[
pDirDesc, anonNamePlusBEL, File.nullCapability];
IF ~ok OR noRoom THEN {
anonDirCap ← File.nullCapability; pDTNodeOut ← DirectoryInternal.pDTnil; }
ELSE {
dirEntryHandle.cap ← anonDirCap ← File.Create[
context.volume, DirectoryInternal.initDirSize,
CommonSoftwareFileTypes.tDirectory];
File.MakePermanent[anonDirCap];
InitializeDirectory[
context: context, dirCap: anonDirCap, parentCap: parentCap,
name: anonName];
IF pDTNodeIn # DirectoryInternal.pDTnil THEN {
IF DirectoryTrees.DTInsert[pDT, pDTNodeIn, anonName, anonDirCap].noRoom
THEN {
context.LogProc[
"Volume.DirectoryTree overflow, too many directories; continuing...
"L];
pDTNodeOut ← DirectoryInternal.pDTnil;
}
ELSE {
Space.ForceOut[dTreeSpace];
pDTNodeOut ← DirectoryTrees.DTFind[pDT, pDTNodeIn, anonName];
};
}
ELSE pDTNodeOut ← DirectoryInternal.pDTnil;
};
END; -- CreateAnonDir

-- CreateDTree: Create a new Volume.DirectoryTree, and initialize it to include just the RootDir and itself.

CreateDTree: INTERNAL PROC [context: DirectoryExtras.ScavengerContext] =
BEGIN
dTreeName: STRING = "Volume.DirectoryTree"L;
IF context.repair THEN {
dTreeCap ← File.Create[
context.volume, DirectoryInternal.initDTSize, DCSFileTypes.tLeaderPage];
MapDirectory[context, rootCap];
[] ← DirectoryTrees.BTreeDelete[pDirDesc, dTreeName, FALSE]; -- can’t check for error here, because
--entry won’t exist if new RootDir had to be created.
IF ~DirectoryTrees.BTreeInsert[
pDirDesc, dTreeName, File.LimitPermissions[dTreeCap, File.read]].ok THEN ERROR
DirectoryExtras.ScavengerError[internalFailure];
Space.ForceOut[dirSpace];
File.MakePermanent[dTreeCap];
IF context.verbose THEN
context.LogProc["New Volume.DirectoryTree created.
"L];
InitializeDTree[context, dTreeName];
DirectoryProps.SetCreateDate[dTreeCap, dTreeName, rootCap];
};
END; -- CreateDTree

-- DeleteDirectoryEntry: Delete the supplied directory entry from its directory if we’re repairing, or else just advance to the next directory entry.

DeleteDirectoryEntry: INTERNAL PROC [
context: DirectoryExtras.ScavengerContext,
pDirDesc: POINTER TO DirectoryInternal.DirectoryDescriptor,
name, nextName: LONG STRING, doSD: BOOLEAN] =
BEGIN
IF context.repair THEN {
IF DirectoryTrees.BTreeDelete[pDirDesc, nextName, doSD].ok THEN {
Space.ForceOut[dirSpace];
context.LogProc["; entry deleted from directory.
"L];
}
ELSE context.LogProc["; attempt to delete entry from directory failed.
"L];
}
ELSE {
context.LogProc[".
"L];
DirectoryTrees.MoveLongString[to: name, from: nextName];
-- advance to next entry
};
END; -- DeleteDirectoryEntry

-- GenerateUniqueName: Generate a unique name for the specified directory using the root name provided.

GenerateUniqueName: INTERNAL PROC [
context: DirectoryExtras.ScavengerContext, dirCap: File.Capability,
rootName: STRING] =
BEGIN
rootNameLength: CARDINAL ← rootName.length;
rootNameNumber: CARDINAL ← 0;
MapDirectory[context, dirCap];
DO
IF ~DirectoryTrees.BTreeFind[pDirDesc, rootName].ok THEN EXIT;
rootName.length ← rootNameLength;
String.AppendNumber[rootName, rootNameNumber, 10];
rootNameNumber ← rootNameNumber + 1;
ENDLOOP;
END; -- GenerateUniqueName

-- Initialize: Reset all the global variables that change during the scavenge.

Initialize: INTERNAL PROC =
BEGIN
anonCap ← File.nullCapability;
anonFileNumber ← 0;
dTreeCap ← File.nullCapability;
nonDirectoryFileCount ← 0;
nonDirectoryFileCountString.length ← 0;
rootCap ← File.nullCapability;
sysCap ← File.nullCapability;
uniqueAnonName.length ← 0;
END; -- Initialize

-- InitializeDirectory: Install an empty BTree in the specified directory, and reset the leader page properties.

InitializeDirectory: INTERNAL PROC [
context: DirectoryExtras.ScavengerContext, dirCap, parentCap: File.Capability,
name: LONG STRING] =
BEGIN
pPage: DirectoryInternal.DirectoryPageHandle ← dirPage;
MapDirectory[context, dirCap];
pPage.parent ← pPage.lastPointer ← DirectoryInternal.nilPagePointer;
pPage.size ← DirectoryInternal.emptySize;
pPage.free ← FALSE;
pPage.filler ← 0;
pPage.top ← FIRST[DirectoryInternal.PagePointer];
pPage ← pPage + Environment.wordsPerPage;
FOR x: File.PageCount ← DirectoryInternal.leaderPageSize + 1, x + 1 UNTIL x =
DirectoryInternal.initDirSize DO
pPage.free ← TRUE; pPage ← pPage + Environment.wordsPerPage; ENDLOOP;
Space.ForceOut[dirSpace];
DirectoryProps.SetCreateDate[dirCap, name, parentCap];
END; -- InitializeDirectory

-- InitializeDTree: Set Volume.DirectoryTree to empty except for entries for RootDir and itself.

InitializeDTree: INTERNAL PROC [
context: DirectoryExtras.ScavengerContext, dTreeName: STRING] =
BEGIN
pDTNode: DirectoryInternal.PDTNode;
Space.Map[dTreeSpace, [dTreeCap, DirectoryInternal.leaderPageSize]];
-- first entry contains pointers to tree, free and full cap of tree
pDTNode ← FIRST[DirectoryInternal.PDTNode];
pDT[pDTNode].name ←
[length: 0, maxlength: Directory.maxDirectoryNameLength, text:];
pDT[pDTNode].cap ← dTreeCap;
pDT[pDTNode].son ← pDTNode + SIZE[DirectoryInternal.DTNode];
pDT[pDTNode].bro ← pDTNode + 2*SIZE[DirectoryInternal.DTNode];
pDT[pDTNode].level ← LAST[CARDINAL];
pDTNode ← pDTNode + SIZE[DirectoryInternal.DTNode];
-- second describes root directory
pDT[pDTNode].name ←
[length: 0, maxlength: Directory.maxDirectoryNameLength, text:];
DirectoryTrees.MoveLongString[to: @pDT[pDTNode].name, from: "RootDir"L];
pDT[pDTNode].son ← pDTNode;
pDT[pDTNode].bro ← pDTNode;
pDT[pDTNode].cap ← rootCap;
pDT[pDTNode].level ← 0;
-- rest are free nodes
-- (third describes the system directory, but it will be inserted during WalkDirectory, not here)
FOR x: CARDINAL ← 2, x + 1 UNTIL x =
(DirectoryInternal.initDTSize -
DirectoryInternal.leaderPageSize)*Environment.wordsPerPage/SIZE[
DirectoryInternal.DTNode] DO
pDTNode ← pDTNode + SIZE[DirectoryInternal.DTNode];
pDT[pDTNode].name ←
[length: 0, maxlength: Directory.maxDirectoryNameLength, text:];
pDT[pDTNode].bro ← pDTNode + SIZE[DirectoryInternal.DTNode];
ENDLOOP;
pDT[pDTNode].bro ← DirectoryInternal.pDTnil;
Space.ForceOut[dTreeSpace];
END; -- InitializeDTree

-- InsertFiles: Enumerate all the files in the Pilot ScavengerLog and try to insert those of the right type into the parent directory indicated in the leader page. Those with invalid parent directory file capabilities will be inserted into anonymous directories. (For now, insert them all in a single "AnonDir" directory. A future improvement would be to put each group of files with the same missing parent in a separate "AnonDirNN" directory, where NN is a number.)

InsertFiles: INTERNAL PROC [context: DirectoryExtras.ScavengerContext] =
BEGIN
bufferPointer: LONG POINTER TO UNSPECIFIED;
fileEntryCopy: Scavenger.FileEntry;
fileEntry: POINTER TO Scavenger.FileEntry ← @fileEntryCopy;
file, fileFound: File.Capability;
header: LONG POINTER TO Scavenger.Header ← NIL;
name: STRING ← [Directory.maxDirectoryNameLength];
namePlusBEL: STRING ← [Directory.maxDirectoryNameLength + 1];
nextWord: CARDINAL ← SIZE[Scavenger.Header];
problemCopy: Scavenger.Problem;
problem: POINTER TO Scavenger.Problem ← @problemCopy;
readDate, writeDate, createDate: System.GreenwichMeanTime;
byteLength, numberOfFiles: LONG CARDINAL;
parent: File.Capability;
type: File.Type;
immutable, temporary, reinserted, found, noRoom, isDirectory: BOOLEAN;
parentStatus: DirectoryStatus;
fileVolume: System.VolumeID;
pilotLogSpace: Space.Handle;
[bufferPointer: bufferPointer, pilotLogSpace: pilotLogSpace] ←
DirectoryScavenger.OpenPilotLogFile[context];
header ← LOOPHOLE[bufferPointer];
IF header.volume # context.volume THEN
ERROR DirectoryExtras.ScavengerError[pilotScavengerLogForWrongVolume];
IF context.repair AND NOT header.repaired THEN
ERROR DirectoryExtras.ScavengerError[pilotFilesNotRepaired];
IF header.incomplete THEN
context.LogProc["Warning: Incomplete Pilot scavenger log; continuing...
"L];
-- Go ahead and scavenge whatever files are in the log. Client probably should rerun the Pilot and directory scavengers after making more disk space available for the Pilot scavenger log.
numberOfFiles ← header.numberOfFiles;
-- save number of files in a safe place (won’t get unmapped if pilotLogSpace WindowOrigin is changed).
header ← NIL;
-- get rid of dangling pointer in case pilotLogSpace WindowOrigin is changed.
FOR counter: LONG CARDINAL ← 1, counter + 1 WHILE counter <= numberOfFiles DO
nextWord ← DirectoryScavenger.GetWords[
fileEntry, bufferPointer, nextWord, SIZE[Scavenger.FileEntry],
pilotLogSpace];
THROUGH [0..fileEntry.numberOfProblems) DO
nextWord ← DirectoryScavenger.GetWords[
problem, bufferPointer, nextWord, SIZE[Scavenger.Problem], pilotLogSpace];
-- For the moment, ignore Problems; in the future, they must be processed at this point.
context.LogProc["Problem entry found in Pilot scavenger log; ignoring and continuing...
"L];
ENDLOOP;
file ←
[fileEntry.file,
IF context.repair THEN Directory.fileMaxPermissions ELSE File.read];
[type: type, immutable: immutable, temporary: temporary, volume: fileVolume]
← File.GetAttributes[
file !
File.Unknown, Volume.Unknown => {
context.LogProc[
"Unknown file ID found in Pilot scavenger log; ignoring and continuing...
"L];
LOOP;
}];
IF temporary THEN {
context.LogProc[
"Temporary file found in Pilot scavenger log; ignoring and continuing...
"L];
LOOP;
};
IF (fileVolume # context.volume) AND ~immutable THEN {
context.LogProc[
"Pilot scavenger log points to non-immutable file found on foreign volume;
ignoring and continuing...
"L];
LOOP;
};
IF (type NOT IN CommonSoftwareFileTypes.CommonSoftwareFileType) AND
(type # DCSFileTypes.tLeaderPage) THEN {
IF context.repair AND (type = PilotFileTypes.tScavengerLog) AND
(file.fID # context.pilotLogFile.fID) THEN {
IF immutable THEN
File.DeleteImmutable[[file.fID, File.delete], context.volume]
ELSE File.Delete[[file.fID, File.delete]];
context.LogProc["Old Pilot scavenger log file deleted.
"L];
}
ELSE nonDirectoryFileCount ← nonDirectoryFileCount + 1;
LOOP;
};
-- file has a file type indicating it is part of a directory (i.e. it has a leader page)
[readDate, writeDate, createDate, byteLength, parent] ←
DirectoryProps.GetPropsInternal[
file, name !
Directory.Error => {
IF type = invalidProperty THEN {
context.LogProc["File with bad leader page found.
"L];
IF context.repair THEN {
parent ← File.nullCapability;
DirectoryTrees.MoveLongString[to: name, from: "AnonFile"L];
String.AppendNumber[name, anonFileNumber, 10];
anonFileNumber ← anonFileNumber + 1;
DirectoryProps.SetCreateDate[file, name, parent];
context.LogProc["File renamed to "L];
context.LogProc[name];
context.LogProc[" and leader page reset.
"L];
CONTINUE;
}
ELSE LOOP;
}
ELSE {ERROR DirectoryExtras.ScavengerError[internalFailure]; };
}];
-- ought to check the validity of the dates here, and log message in ScavengerLog if in error. Same for bytelength and name.
IF (file.fID = rootCap.fID) AND DirectoryScavenger.EquivalentLongStrings[
name, "RootDir"L] THEN LOOP; -- RootDir has no parent.
IF DirectoryScavenger.EquivalentLongStrings[name, "Volume.DirectoryTree"L]

THEN {
IF context.repair THEN {
File.Delete[[file.fID, File.delete]];
IF context.verbose THEN
context.LogProc["Old Volume.DirectoryTree deleted.
"L];
LOOP;
}
ELSE parent ← rootCap;
-- Volume.DirectoryTree’s parent is really RootDir, not SysDir.
};
parentStatus ← ValidateAndMapDirectory[context, parent, pDirDesc];
-- ValidateAndMapDirectory makes sure that the parent directory is a valid BTree, and that it is of type tDirectory; it also sets up the DirectoryDescriptor, including mapping the parent file into dirSpace.
SELECT parentStatus FROM
ok => {
[ok: found, cap: fileFound, isSD: isDirectory] ←
DirectoryTrees.BTreeFind[pDirDesc, name];
IF found THEN {
IF (file.fID = fileFound.fID) THEN {
IF (type = CommonSoftwareFileTypes.tDirectory) = isDirectory THEN {
IF (type = CommonSoftwareFileTypes.tDirectory) AND
(parent.fID = rootCap.fID) AND DirectoryScavenger.EquivalentLongStrings[
name, "SysDir"L] THEN sysCap ← file;
IF context.verbose THEN {
context.LogProc[name]; context.LogProc[" okay.
"L]};
}
ELSE -- directory indicators disagree
{
context.LogProc[name];
IF isDirectory THEN {
context.LogProc[
" is not of directory type but is listed as a subdirectory"L];
IF context.repair THEN {
DirectoryTrees.MoveLongString[to: namePlusBEL, from: name];
namePlusBEL[namePlusBEL.length] ← Ascii.BEL;
namePlusBEL.length ← namePlusBEL.length + 1;
IF ~DirectoryTrees.BTreeDelete[pDirDesc, namePlusBEL, isDirectory].ok OR
~DirectoryTrees.BTreeInsert[pDirDesc, name, file].ok THEN
DirectoryExtras.ScavengerError[internalFailure];
Space.ForceOut[dirSpace];
context.LogProc["; now listed as an ordinary file.
"L];
}
ELSE context.LogProc[".
"L];
}
ELSE -- ~isDirectory (no Ascii.BEL on name in parent directory)
{
context.LogProc[
" has directory type but is not listed as a subdirectory"L];
IF context.repair THEN {
DirectoryTrees.MoveLongString[to: namePlusBEL, from: name];
namePlusBEL[namePlusBEL.length] ← Ascii.BEL;
namePlusBEL.length ← namePlusBEL.length + 1;
IF ~DirectoryTrees.BTreeDelete[pDirDesc, name, isDirectory].ok OR
~DirectoryTrees.BTreeInsert[pDirDesc, namePlusBEL, file].ok THEN ERROR
DirectoryExtras.ScavengerError[internalFailure];
Space.ForceOut[dirSpace];
context.LogProc["; now listed as subdirectory.
"L];
}
ELSE context.LogProc[".
"L];
};
};
}
ELSE -- file.fID # fileFound.fID
{
context.LogProc[name];
context.LogProc[" found in parent directory with wrong FileID.
"L];
InsertInAnonymousDirectory[context, name, file, parent, type];
};
}
ELSE -- not found
{
context.LogProc[name];
IF context.repair THEN {
DirectoryTrees.MoveLongString[to: namePlusBEL, from: name];
IF type = CommonSoftwareFileTypes.tDirectory THEN {
namePlusBEL[namePlusBEL.length] ← Ascii.BEL;
namePlusBEL.length ← namePlusBEL.length + 1;
};
[ok: reinserted, noRoom: noRoom] ← DirectoryTrees.BTreeInsert[
pDirDesc, namePlusBEL, file];
IF reinserted THEN {
Space.ForceOut[dirSpace];
context.LogProc[" had to be reinserted into its directory.
"L];
}
ELSE {
context.LogProc[" couldn’t be reinserted"L];
IF noRoom THEN context.LogProc["; parent directory full.
"L]
ELSE context.LogProc["; unknown problem.
"L];
InsertInAnonymousDirectory[context, name, file, parent, type];
};
}
ELSE context.LogProc[" not found in parent directory.
"L];
};
};
invalidBTree => {
context.LogProc[name];
context.LogProc[" has a parent directory with an invalid B-tree.
"L];
IF context.repair THEN
RepairParentDirectory[context, name, file, parent, type];
};
nonexistent, notDirectoryType => {
context.LogProc[name];
context.LogProc[" has an invalid parent directory file capability.
"L];
InsertInAnonymousDirectory[context, name, file, parent, type];
};
ENDCASE;
ENDLOOP;
DirectoryScavenger.ClosePilotLogFile[pilotLogSpace];
String.AppendNumber[nonDirectoryFileCountString, nonDirectoryFileCount, 10];
context.LogProc[nonDirectoryFileCountString];
context.LogProc[
" files with no leader page were found and ignored in pass one.
"L];
nonDirectoryFileCount ← 0; -- reset for WalkDirectory
nonDirectoryFileCountString.length ← 0; -- reset for WalkDirectory

END; -- InsertFiles

-- InsertInAnonymousDirectory: Insert an orphan file into the Anonymous directory AnonDir (or one of its AnonDir subdirectories in the event of a name conflict). If any pre-existing AnonDirs turn out to be orphan files, rename them to "OldAnonDir" before inserting them to avoid confusion with newly-created AnonDirs.

InsertInAnonymousDirectory: INTERNAL PROC [
context: DirectoryExtras.ScavengerContext, name: LONG STRING,
file, parent: File.Capability, type: File.Type] =
BEGIN
anonName: STRING = "AnonDir"L;
found: BOOLEAN;
namePlusBEL: STRING ← [Directory.maxDirectoryNameLength + 1];
-- "+1" makes room for Ascii.BEL (directory indicator)
newParent, temp: File.Capability;
pNewParent: LONG POINTER TO File.Capability ← @newParent;
pDTNode: DirectoryInternal.PDTNode;
-- relative pointer to Volume.DirectoryTree node for current AnonDir subdirectory.
IF context.repair THEN {
IF DirectoryScavenger.EquivalentLongStrings[name, anonName] THEN {
DirectoryTrees.MoveLongString[to: name, from: "OldAnonDir"L];
-- avoid name conflicts with newly created anonymous directories (can’t use the old ones since they are suspect)
DirectoryProps.PutPropertyInternal[
file, PropertyTypes.tFileName, DESCRIPTOR[
name, SIZE[StringBody [name.length]]]];
context.LogProc["Pre-existing AnonDir renamed "L];
context.LogProc[name];
context.LogProc[
" to avoid potential name conflict with newly-created AnonDir.
"L];
};
DirectoryTrees.MoveLongString[to: namePlusBEL, from: name];
IF type = CommonSoftwareFileTypes.tDirectory THEN {
namePlusBEL[namePlusBEL.length] ← Ascii.BEL;
namePlusBEL.length ← namePlusBEL.length + 1;
};
IF anonCap = File.nullCapability THEN {
DirectoryTrees.MoveLongString[to: uniqueAnonName, from: anonName];
GenerateUniqueName[context, rootCap, uniqueAnonName];
[anonCap, pDTNodeAnon] ← CreateAnonDir[
context, uniqueAnonName, rootCap, DirectoryTrees.DTFirst[pDT]];
};
newParent ← anonCap;
IF newParent = File.nullCapability THEN GOTO noRoomExit;
pDTNode ← pDTNodeAnon;
MapDirectory[context, newParent];
DO
IF pDirDesc.size < DirectoryInternal.maxDirSize THEN
IF DirectoryTrees.BTreeInsert[pDirDesc, namePlusBEL, file].ok THEN EXIT;
[ok: found, cap: temp] ← DirectoryTrees.BTreeFind[pDirDesc, anonName];
IF found THEN {
newParent ← temp;
pDTNode ←
IF pDTNode # DirectoryInternal.pDTnil THEN DirectoryTrees.DTFind[
pDT, pDTNode, anonName] ELSE DirectoryInternal.pDTnil;
MapDirectory[context, newParent];
}
ELSE {
[newParent, pDTNode] ← CreateAnonDir[
context, anonName, newParent, pDTNode];
--does MapDirectory as side effect.
IF newParent = File.nullCapability THEN GOTO noRoomExit;
};
ENDLOOP;
DirectoryProps.PutPropertyInternal[
file, PropertyTypes.tParentDirectory, DESCRIPTOR[
pNewParent, SIZE[File.Capability]]];
Space.ForceOut[dirSpace];
context.LogProc[name];
context.LogProc[" inserted in "L];
context.LogProc[uniqueAnonName];
context.LogProc[" (or one of its AnonDir subdirectories).
"L];
EXITS
noRoomExit =>
context.LogProc["No room to create AnonDir; continuing...
"L];
};
END; -- InsertInAnonymousDirectory

-- MakeRootDir: Create a new RootDir.

MakeRootDir: INTERNAL PROC [context: DirectoryExtras.ScavengerContext] =
BEGIN
rootCap ← File.Create[
context.volume, DirectoryInternal.initDirSize,
CommonSoftwareFileTypes.tDirectory];
InitializeDirectory[
context: context, dirCap: rootCap, parentCap: File.nullCapability,
name: "RootDir"L];
Volume.SetRootFile[context.volume, rootCap];
File.MakePermanent[rootCap];
context.LogProc["Created new RootDir.
"L];
END; -- MakeRootDir

-- MakeSysDir: Create a new SysDir, initialize it, and insert it into Volume.DirectoryTree.

MakeSysDir: INTERNAL PROC [context: DirectoryExtras.ScavengerContext] =
BEGIN
sysDirName: STRING ← "SysDir"L;
sysDirWithBEL: STRING ← [7];
DirectoryTrees.MoveLongString[to: sysDirWithBEL, from: sysDirName];
sysDirWithBEL[sysDirWithBEL.length] ← Ascii.BEL;
sysDirWithBEL.length ← sysDirWithBEL.length + 1;
sysCap ← File.Create[
context.volume, DirectoryInternal.initDirSize,
CommonSoftwareFileTypes.tDirectory];
MapDirectory[context, rootCap];
[] ← DirectoryTrees.BTreeDelete[pDirDesc, sysDirWithBEL, TRUE]; -- don’t check for error; SysDir won’t be there if a new RootDir had to be created.
IF ~DirectoryTrees.BTreeInsert[pDirDesc, sysDirWithBEL, sysCap].ok THEN ERROR
DirectoryExtras.ScavengerError[internalFailure];
File.MakePermanent[sysCap];
InitializeDirectory[
context: context, dirCap: sysCap, parentCap: rootCap, name: sysDirName];
IF DirectoryTrees.DTInsert[
pDT, DirectoryTrees.DTFirst[pDT], sysDirName, sysCap].noRoom THEN
context.LogProc[
"Volume.DirectoryTree overflow, too many entries; continuing...
"L]
ELSE Space.ForceOut[dTreeSpace];
context.LogProc["Created new SysDir.
"L];
END; -- MakeSysDir

-- MapDirectory: Map a directory into dirSpace and set up the DirectoryDescriptor.

MapDirectory: INTERNAL PROC [
context: DirectoryExtras.ScavengerContext, dirCap: File.Capability] =
BEGIN
dirSize: Space.PageCount;
IF Space.GetAttributes[dirSpace].mapped THEN Space.Unmap[dirSpace];
Space.Map[
dirSpace,
[[dirCap.fID, IF context.repair THEN File.read + File.write ELSE File.read],
DirectoryInternal.leaderPageSize]];
dirSize ← Inline.LowHalf[File.GetSize[dirCap]];
pDirDesc↑ ←
[base: dirPage, top: dirPage.top,
size: dirSize - DirectoryInternal.leaderPageSize, space: dirSpace];
END; -- MapDirectory

-- RepairParentDirectory: Repair the parent directory and reinsert the supplied file into it.

RepairParentDirectory: INTERNAL PROC [
context: DirectoryExtras.ScavengerContext, name: LONG STRING,
file, parent: File.Capability, type: File.Type] =
BEGIN
namePlusBEL: STRING ← [Directory.maxDirectoryNameLength + 1];
parentName: STRING ← [Directory.maxDirectoryNameLength];
parentParent: File.Capability ← File.nullCapability;
[parent: parentParent] ← DirectoryProps.GetPropsInternal[
parent, parentName !
Directory.Error => {
IF type = invalidProperty THEN {
context.LogProc["Parent directory has bad leader page.
"L];
DirectoryTrees.MoveLongString[to: parentName, from: "AnonFile"L];
String.AppendNumber[parentName, anonFileNumber, 10];
anonFileNumber ← anonFileNumber + 1;
DirectoryProps.SetCreateDate[parent, parentName, parentParent];
context.LogProc["Directory renamed to "L];
context.LogProc[parentName];
context.LogProc[" and leader page reset.
"L];
CONTINUE;
}
ELSE {ERROR DirectoryExtras.ScavengerError[internalFailure]; };
}];
InitializeDirectory[context, parent, parentParent, parentName];
DirectoryTrees.MoveLongString[to: namePlusBEL, from: name];
IF type = CommonSoftwareFileTypes.tDirectory THEN {
namePlusBEL[namePlusBEL.length] ← Ascii.BEL;
namePlusBEL.length ← namePlusBEL.length + 1;
};
IF ~DirectoryTrees.BTreeInsert[pDirDesc, namePlusBEL, file].ok THEN ERROR
DirectoryExtras.ScavengerError[internalFailure];
Space.ForceOut[dirSpace];
context.LogProc[parentName];
context.LogProc[", (a directory), reset to contain just "L];
context.LogProc[name];
context.LogProc[".
"L];
END; -- RepairParentDirectory

-- ValidateAndMapDirectory: Check that the directory is of type tDirectory, and that it is a valid BTree; also, set up the DirectoryDescriptor, including mapping the directory into dirSpace. (For the future: could check that the directory is in the Pilot scavenger log.)

ValidateAndMapDirectory: INTERNAL PROC [
context: DirectoryExtras.ScavengerContext, dirCap: File.Capability,
pDirDesc: POINTER TO DirectoryInternal.DirectoryDescriptor]
RETURNS [dirStatus: DirectoryStatus] =
BEGIN
type: File.Type;
dirStatus ← ok;
-- for the moment, punt looking parent up in the Pilot scavenger log.
[type: type] ← File.GetAttributes[
dirCap ! File.Unknown, Volume.Unknown => GOTO nonexistentDirectory];
IF type # CommonSoftwareFileTypes.tDirectory THEN dirStatus ← notDirectoryType
ELSE {
MapDirectory[context, dirCap];
DirectoryScavenger.ValidateBTree[
pDirDesc !
DirectoryScavenger.BTreeInvalid =>
IF ~context.repair THEN ERROR
DirectoryExtras.ScavengerError[fatalBTreeErrorInCheckMode]
--continuing risks a later AddressFault or worse trying to search this directory, since it won’t be repaired

ELSE {dirStatus ← invalidBTree; CONTINUE; }];
};
EXITS nonexistentDirectory => dirStatus ← nonexistent;
END; -- ValidateAndMapDirectory

-- ValidateRootDir: Check for a valid root directory file capability in the logical volume root page, and create a new root directory file if necessary (after confirmation).

ValidateRootDir: INTERNAL PROC [context: DirectoryExtras.ScavengerContext] =
BEGIN
parent: File.Capability ← File.nullCapability;
rootDirStatus: DirectoryStatus;
rootDirString: STRING ← "RootDir"L;
rootName: STRING ← [Directory.maxDirectoryNameLength];
[rootFile: rootCap] ← Volume.GetAttributes[
context.volume !
Volume.Unknown => ERROR DirectoryExtras.ScavengerError[volumeUnknown]];
rootDirStatus ← ValidateAndMapDirectory[
context: context, dirCap: rootCap, pDirDesc: pDirDesc];
IF (rootDirStatus = ok) OR (rootDirStatus = invalidBTree) THEN {
[parent: parent] ← DirectoryProps.GetPropsInternal[
rootCap, rootName !
Directory.Error => {
IF type = invalidProperty THEN {
context.LogProc["RootDir’s leader page is invalid.
"L];
IF context.repair THEN {
DirectoryTrees.MoveLongString[to: rootName, from: rootDirString];
DirectoryProps.SetCreateDate[rootCap, rootName, parent];
context.LogProc["RootDir’s leader page repaired.
"L];
};
}
ELSE context.LogProc["Unknown damage to RootDir.
"L];
CONTINUE;
}];
IF parent # File.nullCapability OR
~DirectoryScavenger.EquivalentLongStrings[rootName, rootDirString] THEN
rootDirStatus ← nonexistent;
-- not a valid RootDir if parent or name mismatch.
};
SELECT rootDirStatus FROM
invalidBTree => {
context.LogProc["RootDir’s internal B-tree structure is invalid.
"L];
IF context.repair THEN {
InitializeDirectory[
context: context, dirCap: rootCap, parentCap: File.nullCapability,
name: rootDirString];
context.LogProc["RootDir re-initialized.
"L];
};
};
nonexistent, notDirectoryType => {
context.LogProc["No valid RootDir found.
"L];
IF context.repair THEN MakeRootDir[context];
};
ok => NULL;
ENDCASE;
END; -- ValidateRootDir

-- ValidateSysDir: Check for a valid system directory entry ("SysDir") in the root directory, and create a new system directory file if necessary (after confirmation).

ValidateSysDir: INTERNAL PROC [context: DirectoryExtras.ScavengerContext] =
BEGIN
sysDirStatus: DirectoryStatus;
sysDirStatus ← ValidateAndMapDirectory[
context: context, dirCap: sysCap, pDirDesc: pDirDesc];
SELECT sysDirStatus FROM
invalidBTree => {
context.LogProc["SysDir’s internal B-tree structure is invalid.
"L];
IF context.repair THEN {
InitializeDirectory[
context: context, dirCap: sysCap, parentCap: rootCap,
name: "SysDir"L];
context.LogProc["SysDir re-initialized.
"L];
};
};
nonexistent, notDirectoryType => {
context.LogProc["No valid SysDir found.
"L];
IF context.repair THEN MakeSysDir[context];
};
ok => NULL;
ENDCASE;
END; -- ValidateSysDir

-- WalkDirectory: This is a recursive procedure that traverses the directories in this volume, deleting any entries pointing to non-existent files and any entries which don’t match the leader page information of those target files which have a leader page. It rebuilds Volume.DirectoryTree as it goes. [Future enhancements: it could rename files which were inserted into anonymous directories because of a smashed parent file capability in their leader page, (assuming the natural parent is still alive).] [This procedure is required in addition to InsertFiles because files with no leader page are allowed in the directory. InsertFiles cannot reinsert such files, so it is important not to blow away directories altogether and simply rebuild them with InsertFiles. Instead, InsertFiles reinserts any files with leader pages, and WalkDirectory essentially verifies any directory entries for leader page-less files.]

WalkDirectory: INTERNAL PROC [
context: DirectoryExtras.ScavengerContext, dirCap: File.Capability,
pDTNode: DirectoryInternal.PDTNode, nestingCount: CARDINAL]
RETURNS [dirStatus: DirectoryStatus] =
BEGIN
insertSucceeded, nameMismatch, noRoom, parentMismatch, subdirectory: BOOLEAN;
subdirStatus: DirectoryStatus;
type: File.Type;
fileCap, parentCap: File.Capability;
name: STRING ← [Directory.maxDirectoryNameLength + 1];
-- "+1" for Ascii.BEL tacked onto subdirectory names in parent directory B-tree
nextName: STRING ← [Directory.maxDirectoryNameLength + 1];
-- "+1" for Ascii.BEL tacked onto subdirectory names in parent directory B-tree
nextNameMinusBEL: STRING ← [Directory.maxDirectoryNameLength];
fileName: STRING ← [Directory.maxDirectoryNameLength];
dirStatus ← ValidateAndMapDirectory[context, dirCap, pDirDesc];
IF dirStatus = ok THEN {
DO
fileCap ← DirectoryTrees.BTreeGetNext[pDirDesc, name, nextName];
IF (nextName.length = 0) THEN EXIT;
DirectoryTrees.MoveLongString[to: nextNameMinusBEL, from: nextName];
IF nextNameMinusBEL[nextNameMinusBEL.length - 1] = Ascii.BEL THEN {
nextNameMinusBEL.length ← nextNameMinusBEL.length - 1;
subdirectory ← TRUE;
}
ELSE subdirectory ← FALSE;
IF context.verbose THEN {
DirectoryScavenger.DoNesting[context, nestingCount];
context.LogProc[nextNameMinusBEL];
context.LogProc[" found in directory.
"L];
};
[type: type] ← File.GetAttributes[
fileCap !
File.Unknown, Volume.Unknown => {
context.LogProc[nextNameMinusBEL];
context.LogProc[" associated with unknown file ID in directory"L];
DeleteDirectoryEntry[
context: context, pDirDesc: pDirDesc, name: name,
nextName: nextName, doSD: subdirectory];
LOOP;
}];
--Ought to check for non-immutable file found on foreign volume; delete directory entry in such a case.
IF (type NOT IN CommonSoftwareFileTypes.CommonSoftwareFileType) AND
(type # DCSFileTypes.tLeaderPage) THEN
-- this is a valid entry for a leader page-less file.
{
nonDirectoryFileCount ← nonDirectoryFileCount + 1;
DirectoryTrees.MoveLongString[to: name, from: nextName];
-- advance to next entry
LOOP;
};
[parent: parentCap] ← DirectoryProps.GetPropsInternal[
fileCap, fileName !
Directory.Error => {
context.LogProc[nextNameMinusBEL];
context.LogProc[" has a bad leader page.
"L];
IF (type # invalidProperty) OR context.repair THEN
--should have been repaired already in InsertFiles
ERROR DirectoryExtras.ScavengerError[internalFailure];
DirectoryTrees.MoveLongString[to: name, from: nextName];
-- advance to next entry
LOOP;
}];
IF DirectoryScavenger.EquivalentLongStrings[
fileName, "Volume.DirectoryTree"L] THEN parentCap ← rootCap;
--Volume.DirectoryTree’s parent is really RootDir, not SysDir.
parentMismatch ← parentCap.fID # dirCap.fID;
nameMismatch ← NOT DirectoryScavenger.EquivalentLongStrings[
fileName, nextNameMinusBEL];
IF parentMismatch OR nameMismatch THEN {
context.LogProc[nextNameMinusBEL];
context.LogProc[
" entry in directory does not agree with indicated file’s leader page:
"L];
IF parentMismatch THEN
context.LogProc[" Parent directory mismatch.."L];

IF nameMismatch THEN {
context.LogProc[" File name mismatch..
Name in leader page: "L];
context.LogProc[fileName];
};
DeleteDirectoryEntry[
context: context, pDirDesc: pDirDesc, name: name, nextName: nextName,
doSD: subdirectory];
LOOP;
};
IF subdirectory THEN --it’s a subdirectory, go walk it
{
insertSucceeded ← FALSE;
IF context.repair AND (pDTNode # DirectoryInternal.pDTnil) THEN {
[ok: insertSucceeded, noRoom: noRoom] ← DirectoryTrees.DTInsert[
pDT, pDTNode, nextNameMinusBEL, fileCap];
IF insertSucceeded THEN Space.ForceOut[dTreeSpace]
ELSE
IF noRoom THEN
context.LogProc[
"Volume.DirectoryTree overflow, too many directories; continuing...
"L];
};
subdirStatus ← WalkDirectory[
context, fileCap,
IF context.repair AND (pDTNode # DirectoryInternal.pDTnil) THEN
DirectoryTrees.DTFind[pDT, pDTNode, nextNameMinusBEL]
ELSE DirectoryInternal.pDTnil, nestingCount + 1];
MapDirectory[context, dirCap]; -- map the original directory back in
IF subdirStatus # ok THEN {
context.LogProc[nextNameMinusBEL];
SELECT subdirStatus FROM
invalidBTree => {
context.LogProc[
" is marked as a subdirectory but is not a valid B-tree"L];
IF context.repair THEN {
InitializeDirectory[
context: context, dirCap: fileCap, parentCap: dirCap,
name: nextNameMinusBEL];
context.LogProc["; reset to empty directory.
"L];
MapDirectory[context, dirCap]; -- map the original directory back in
}
ELSE {context.LogProc[".
"L]; };
DirectoryTrees.MoveLongString[to: name, from: nextName];
-- advance to next entry
LOOP;
};
nonexistent => {
context.LogProc[
" is associated with an unknown file ID in its directory"L];
DeleteDirectoryEntry[
context: context, pDirDesc: pDirDesc, name: name,
nextName: nextName, doSD: subdirectory];
};
notDirectoryType => {
context.LogProc[
" is marked as a subdirectory but has the wrong file type"L];
DeleteDirectoryEntry[
context: context, pDirDesc: pDirDesc, name: name,
nextName: nextName, doSD: subdirectory];
};
ENDCASE;
IF insertSucceeded THEN
IF NOT DirectoryTrees.DTDelete[pDT, pDTNode, nextNameMinusBEL].ok
THEN ERROR DirectoryExtras.ScavengerError[internalFailure]
ELSE Space.ForceOut[dTreeSpace];
LOOP;
};
};
DirectoryTrees.MoveLongString[to: name, from: nextName];
-- current entry OK, advance to next entry

ENDLOOP;
};
END; --WalkDirectory

END.

LOG

Time: December 18, 1980 11:11 AMBy: FayAction: Created file.

Time: January 22, 1981 4:25 PMBy: FayAction: AR 7008: assume fixed-size Problem entries.