FSDirImpl.mesa
Last Edited by: Schroeder, November 15, 1983 1:25 pm
Last Edited by: Levin, September 22, 1983 12:54 pm
DIRECTORY
Ascii USING [Upper],
Basics USING [Comparison],
BasicTime USING [GMT, nullGMT],
BTree USING [DeleteKey, Entry, EntSize, EnumerateEntries, Key, PathStk, ReadEntry, Relation, Tree, UpdateEntry, UpdateType],
File USING [FP, nullFP, Volume],
FS USING [Error, ErrorDesc, maxFNameLength],
FSBackdoor USING [Entry, EntryPtr, EntryType, highestVersion, lowestVersion, MakeFName, TextRep, TextRP, ProduceError, Version],
FSDir USING [VersionMatching],
FSFileOps USING [DeleteFile, LPCreatedTime, OpenFile, VolumeDesc],
FSLock USING [ActiveFile, ReleaseRecord, LockRecord, WaitForRecord],
PrincOpsUtils USING [ByteBlt],
Rope USING [Cat, Length, NewText, ROPE, Text];
FSDirImpl: CEDAR MONITOR
IMPORTS Ascii, BTree, FS, FSBackdoor, FSFileOps, FSLock, PrincOpsUtils, Rope
EXPORTS FSBackdoor, FSDir
= BEGIN
Directory Entry Representation
AppendText: UNSAFE PROC [eP: FSBackdoor.EntryPtr, text: Rope.Text] RETURNS [textRP: FSBackdoor.TextRP] = UNCHECKED
BEGIN
textRep: LONG POINTER TO FSBackdoor.TextRep;
textRP ← LOOPHOLE[eP.size];
textRep ← @eP[textRP];
LOOPHOLE[textRep, LONG POINTER TO CARDINAL]^ ← Rope.Length[text]; -- sets textRep.length
[] ← PrincOpsUtils.ByteBlt [
to: [ BASE[DESCRIPTOR[textRep]], 0, textRep.length ],
from: [ BASE[DESCRIPTOR[text]], 0, textRep.length ]
];
eP.size ← eP.size+SIZE[FSBackdoor.TextRep[textRep.length]];
END;
GetText: UNSAFE PROC [textRep: LONG POINTER TO FSBackdoor.TextRep, text: REF TEXT] = UNCHECKED
BEGIN
text.length ← textRep.length;
[] ← PrincOpsUtils.ByteBlt [
to: [ BASE[DESCRIPTOR[text]], 0, textRep.length ],
from: [ BASE[DESCRIPTOR[textRep]], 0, textRep.length ]
];
END;
EntryNameMatches: UNSAFE PROC [name: Rope.Text, entryPtr: FSBackdoor.EntryPtr] RETURNS[BOOLEAN] = UNCHECKED
BEGIN
entryName: LONG POINTER TO FSBackdoor.TextRep = @entryPtr[entryPtr.nameBody];
nameBody: REF READONLY TEXT = LOOPHOLE[name];
IF entryName.length # nameBody.length THEN RETURN[FALSE];
FOR i: CARDINAL IN [ 0 .. nameBody.length ) DO
IF Ascii.Upper[entryName[i]] # Ascii.Upper[nameBody[i]] THEN RETURN[FALSE];
ENDLOOP;
RETURN[TRUE];
END;
BTree key management
KeyObject: TYPE = RECORD [version: FSBackdoor.Version, nameBody: Rope.Text];
stockKey: REF KeyObject ← NIL;
CheckoutKey: ENTRY PROC [v: FSBackdoor.Version, nB: Rope.Text] RETURNS [k: REF KeyObject] =
BEGIN
IF stockKey = NIL THEN k ← NEW [KeyObject] ELSE { k ← stockKey; stockKey ← NIL };
k^ ← KeyObject[v, nB];
END;
RecycleKey: ENTRY PROC [k: REF KeyObject] =
{ stockKey ← k };
Error generation
NoMoreVersions: PROC [prefix, nameBody: Rope.ROPE, version: FSBackdoor.Version] =
BEGIN
FSBackdoor.ProduceError[noMoreVersions,
Rope.Cat["Next version of \"", FSBackdoor.MakeFName[nameBody, version, prefix], "\" would be too big."]];
END;
BTree access primitives, exported to FSDir
Compare: PUBLIC UNSAFE PROC [key: BTree.Key, entry: BTree.Entry] RETURNS [Basics.Comparison] = UNCHECKED
BEGIN
keyRef: REF KeyObject = NARROW[key];
keyName: REF READONLY TEXT = LOOPHOLE[keyRef.nameBody];
entryPtr: FSBackdoor.EntryPtr = LOOPHOLE[entry];
entryName: LONG POINTER TO FSBackdoor.TextRep = @entryPtr[entryPtr.nameBody];
lenKey, lenEntry: CARDINAL;
IF keyName = NIL THEN RETURN [less];
lenKey ← keyName.length;
lenEntry ← entryName.length;
FOR i: CARDINAL IN [ 0 .. MIN[lenKey, lenEntry] ) DO
cKey: CHAR = Ascii.Upper[keyName[i]];
cEntry: CHAR = Ascii.Upper[entryName[i]];
SELECT cKey FROM
< cEntry => RETURN [less];
> cEntry => RETURN [greater];
ENDCASE;
ENDLOOP;
SELECT lenKey FROM
< lenEntry => RETURN [less];
> lenEntry => RETURN [greater];
ENDCASE =>
SELECT keyRef.version FROM
< entryPtr.version => RETURN [less];
> entryPtr.version => RETURN [greater];
ENDCASE => RETURN [equal];
END;
EntrySize: PUBLIC UNSAFE PROC [entry: BTree.Entry] RETURNS [words: BTree.EntSize] = UNCHECKED
{ RETURN [ LOOPHOLE[entry, FSBackdoor.EntryPtr].size ] };
Exported to FSBackdoor
TextFromTextRep: PUBLIC PROC [textRep: LONG POINTER TO FSBackdoor.TextRep] RETURNS [r: Rope.Text] = TRUSTED
{ r ← Rope.NewText[textRep.length]; GetText[textRep, LOOPHOLE[r]] };
Directory/cache manipulation procedures, exported to FSDir
EnumerateEntries: PUBLIC PROC [ vDesc: FSFileOps.VolumeDesc, start: Rope.Text, versions: FSDir.VersionMatching, matchProc: UNSAFE PROC [entry: FSBackdoor.EntryPtr] RETURNS [accept, stop: BOOLEAN], acceptProc: PROC RETURNS [stop: BOOLEAN] ] = TRUSTED
BEGIN
GetAll: UNSAFE PROC [entry: BTree.Entry] RETURNS [continue: BOOLEAN] =
BEGIN
entryPtr: FSBackdoor.EntryPtr = LOOPHOLE[entry];
[accept, stop] ← matchProc[ entryPtr ];
IF stop
THEN continue ← FALSE
ELSE BEGIN
IF accept
THEN BEGIN -- save nameBody for restarting enumeration
GetText[@entryPtr[entryPtr.nameBody], keyText];
keyRef.version ← entryPtr.version;
continue ← FALSE;
END
ELSE continue ← TRUE;
END;
END;
MatchEntry: UNSAFE PROC [entry: BTree.Entry] =
BEGIN
entryPtr: FSBackdoor.EntryPtr = LOOPHOLE[entry];
IF entryPtr = NIL
THEN stop ← TRUE
ELSE BEGIN
GetText[@entryPtr[entryPtr.nameBody], keyText];
[accept, stop] ← matchProc[ entryPtr ];
END;
END;
FindL: UNSAFE PROC [entry: BTree.Entry] =
BEGIN
entryPtr: FSBackdoor.EntryPtr = LOOPHOLE[entry];
IF entryPtr = NIL
THEN stop ← TRUE
ELSE GetText[@entryPtr[entryPtr.nameBody], keyText];
END;
keyText: REF TEXT = NEW [ TEXT[FS.maxFNameLength] ];
keyRef: REF KeyObject = CheckoutKey[FSBackdoor.lowestVersion, start];
stop, accept: BOOLEAN;
SELECT versions FROM
all => BEGIN
UNTIL BTree.EnumerateEntries[tree: vDesc.tree, relation: greater, key: keyRef, Proc: GetAll] DO
IF stop OR (accept AND acceptProc[]) THEN EXIT;
keyRef.nameBody ← LOOPHOLE[keyText]; -- key from last iteration
ENDLOOP;
END;
bangLOnly => BEGIN
BTree.ReadEntry[tree: vDesc.tree, relation: greater, key: keyRef, Proc: MatchEntry];
keyRef^ ← [FSBackdoor.highestVersion, LOOPHOLE[keyText]]; -- for later interations
UNTIL stop DO
IF accept AND acceptProc[] THEN EXIT;
BTree.ReadEntry[tree: vDesc.tree, relation: greater, key: keyRef, Proc: MatchEntry];
ENDLOOP;
END;
bangHOnly => BEGIN
stop ← FALSE;
BTree.ReadEntry[tree: vDesc.tree, relation: greater, key: keyRef, Proc: FindL];
keyRef^ ← [FSBackdoor.highestVersion, LOOPHOLE[keyText]]; -- for later interations
UNTIL stop DO
BTree.ReadEntry[tree: vDesc.tree, relation: lessEqual, key: keyRef, Proc: MatchEntry];
IF accept AND acceptProc[] THEN EXIT;
BTree.ReadEntry[tree: vDesc.tree, relation: greater, key: keyRef, Proc: FindL];
ENDLOOP;
END;
ENDCASE => ERROR;
RecycleKey[keyRef];
END;
AcquireOldFName: PUBLIC PROC [vDesc: FSFileOps.VolumeDesc, nameBody: Rope.Text, wantedVersion: FSBackdoor.Version, wantedTime: BasicTime.GMT] RETURNS [type: FSBackdoor.EntryType, version: FSBackdoor.Version, keep: CARDINAL, fp: File.FP, time: BasicTime.GMT, attachedTo: Rope.Text, a: FSLock.ActiveFile] = TRUSTED
BEGIN
GetEntry: UNSAFE PROC [entry: BTree.Entry] =
BEGIN
entryPtr: FSBackdoor.EntryPtr = LOOPHOLE[entry];
type ← notFound;
IF entry = NIL OR NOT EntryNameMatches[nameBody, entryPtr]
THEN {outcome ← notFound; RETURN};
version ← entryPtr.version;
IF wantedTime # BasicTime.nullGMT
THEN BEGIN
time ← WITH e: entryPtr^ SELECT FROM
local => FSFileOps.LPCreatedTime[vDesc.vol, e.fp],
attached => e.created,
cached => FSFileOps.LPCreatedTime[vDesc.vol, e.fp],
ENDCASE => ERROR;
IF wantedTime # time THEN {outcome ← wrongTime; RETURN};
END;
type ← entryPtr.type;
[a, lockSet] ← FSLock.LockRecord[vDesc.prefix, nameBody, version];
IF lockSet THEN WITH e: entryPtr^ SELECT FROM
local => BEGIN
keep ← e.keep;
fp ← e.fp;
END;
attached => BEGIN
keep ← e.keep;
time ← e.created;
attachedTo ←TextFromTextRep[@entryPtr[e.attachedTo]];
END;
cached => BEGIN
time ← e.used;
fp ← e.fp;
END;
ENDCASE => ERROR;
outcome ← seeLockSet;
END;
FindAndLock: PROC RETURNS [BOOLEAN] = TRUSTED
BEGIN
DO
errorDesc: FS.ErrorDesc; -- this GetEntry checks the created-time from a leader page sometimes
BTree.ReadEntry[tree: vDesc.tree, relation: search, key: keyRef, Proc: GetEntry
! FS.Error => {errorDesc ← error; CONTINUE} ];
IF errorDesc.group # ok THEN ERROR FS.Error[errorDesc];
SELECT outcome FROM
notFound =>
IF search = equal AND wantedTime # BasicTime.nullGMT
THEN RETURN[TRUE] -- useful to keep looking
ELSE RETURN[FALSE];
wrongTime =>
RETURN[TRUE];
seeLockSet =>
IF lockSet
THEN RETURN[FALSE]
ELSE FSLock.WaitForRecord[a];
ENDCASE =>
ERROR;
ENDLOOP;
END;
outcome: {notFound, wrongTime, seeLockSet};
lockSet, keepLooking: BOOLEAN;
keyRef: REF KeyObject = CheckoutKey [wantedVersion, nameBody];
search: BTree.Relation ← SELECT wantedVersion FROM
FSBackdoor.highestVersion => lessEqual,
FSBackdoor.lowestVersion => greater,
ENDCASE => equal;
IF keepLooking ← FindAndLock[]
THEN BEGIN -- search for version with desired createdTime
IF search = lessEqual
THEN keyRef.version ← [version - 1] -- already found highest version
ELSE { keyRef.version ← FSBackdoor.highestVersion; search ← lessEqual };
WHILE keepLooking DO
keepLooking ← FindAndLock[];
keyRef.version ← [version - 1];
ENDLOOP;
END;
RecycleKey[keyRef];
END;
AcquireNextLName: PUBLIC PROC [vDesc: FSFileOps.VolumeDesc, nameBody: Rope.Text, newKeep: CARDINAL] RETURNS [a: FSLock.ActiveFile, keep: CARDINAL, fp: File.FP] = TRUSTED
BEGIN
GetEntry: UNSAFE PROC [entry: BTree.Entry] =
BEGIN
entryPtr: FSBackdoor.EntryPtr = LOOPHOLE[entry];
type ← notFound;
IF entry # NIL AND EntryNameMatches[nameBody, entryPtr]
THEN BEGIN
keyRef.version ← entryPtr.version;
type ← entryPtr.type;
WITH e: entryPtr^ SELECT FROM
local => BEGIN
IF keep = 0 THEN keep ← e.keep;
entryFP ← e.fp;
END;
attached => BEGIN
IF keep = 0 THEN keep ← e.keep;
END;
ENDCASE => ERROR;
END
ELSE keyRef.version ← FSBackdoor.lowestVersion;
IF count = 0
THEN BEGIN
IF keyRef.version + 1 = FSBackdoor.highestVersion
THEN { noMoreVersions ← TRUE; RETURN }; -- version too big
[a, nextLockSet] ← FSLock.LockRecord[vDesc.prefix, nameBody, [keyRef.version + 1]];
IF NOT nextLockSet OR keyRef.version < keep
THEN RETURN;
END;
IF type # notFound
THEN BEGIN
count ← count + 1;
IF count < keep
THEN entryLockSet ← FALSE
ELSE [entryA, entryLockSet] ← FSLock.LockRecord[vDesc.prefix, nameBody, keyRef.version];
END;
END;
keyRef: REF KeyObject = CheckoutKey[ , nameBody];
entryFP: File.FP;
entryA: FSLock.ActiveFile;
entryLockSet, nextLockSet: BOOLEAN;
noMoreVersions: BOOLEAN ← FALSE;
type: FSBackdoor.EntryType;
count: CARDINAL ← 0;
fp ← File.nullFP;
keep ← newKeep; -- will get reset if =0 and any entries are found
DO -- get a name lock on !N
keyRef.version ← FSBackdoor.highestVersion;
BTree.ReadEntry[tree: vDesc.tree, relation: less, key: keyRef, Proc: GetEntry];
IF noMoreVersions THEN NoMoreVersions[vDesc.prefix, nameBody, FSBackdoor.highestVersion];
IF nextLockSet THEN EXIT ELSE FSLock.WaitForRecord[a];
ENDLOOP;
IF keyRef.version >= keep
THEN UNTIL type = notFound DO -- do keep processing
IF entryLockSet
THEN BEGIN
IF entryA.fileLock = none
THEN BEGIN -- can delete or reuse this file
IF NOT BTree.DeleteKey[tree: vDesc.tree, key: keyRef] THEN ERROR;
IF type = local
THEN BEGIN
IF fp = File.nullFP
THEN fp ← entryFP
ELSE FSFileOps.DeleteFile[ FSFileOps.OpenFile[vDesc.vol, entryFP] ];
END;
END;
FSLock.ReleaseRecord[entryA];
END;
BTree.ReadEntry[tree: vDesc.tree, relation: less, key: keyRef, Proc: GetEntry];
ENDLOOP;
RecycleKey[keyRef];
END;
DoKeeps: PUBLIC PROC [vDesc: FSFileOps.VolumeDesc, nameBody: Rope.Text] = TRUSTED
BEGIN
GetEntry: UNSAFE PROC [entry: BTree.Entry] =
BEGIN
entryPtr: FSBackdoor.EntryPtr = LOOPHOLE[entry];
IF entry = NIL OR NOT EntryNameMatches[nameBody, entryPtr]
THEN {type ← notFound; RETURN};
keyRef.version ← entryPtr.version;
type ← entryPtr.type;
WITH e: entryPtr^ SELECT FROM
local => { IF count = 0 THEN keep ← e.keep; fp ← e.fp };
attached => { IF count = 0 THEN keep ← e.keep };
ENDCASE => ERROR;
count ← count + 1;
IF count <= keep
THEN lockSet ← FALSE
ELSE [a, lockSet] ← FSLock.LockRecord[vDesc.prefix, nameBody, keyRef.version];
END;
keyRef: REF KeyObject = CheckoutKey[FSBackdoor.highestVersion, nameBody];
count: CARDINAL ← 0;
fp: File.FP;
a: FSLock.ActiveFile;
lockSet: BOOLEAN;
type: FSBackdoor.EntryType;
keep: CARDINAL;
BTree.ReadEntry[tree: vDesc.tree, relation: less, key: keyRef, Proc: GetEntry];
IF type # notFound AND keyRef.version > keep
THEN DO -- do keep processing
BTree.ReadEntry[tree: vDesc.tree, relation: less, key: keyRef, Proc: GetEntry];
IF type = notFound THEN EXIT;
IF lockSet
THEN BEGIN
IF a.fileLock = none
THEN BEGIN -- can delete this file
IF NOT BTree.DeleteKey[tree: vDesc.tree, key: keyRef] THEN ERROR;
IF type = local THEN FSFileOps.DeleteFile[ FSFileOps.OpenFile[vDesc.vol, fp] ];
END;
FSLock.ReleaseRecord[a];
END;
ENDLOOP;
RecycleKey[keyRef];
END;
AcquireOldGName: PUBLIC PROC [vDesc: FSFileOps.VolumeDesc, nameBody: Rope.Text, wantedVersion: FSBackdoor.Version] RETURNS [type: FSBackdoor.EntryType, time: BasicTime.GMT, fp: File.FP, a: FSLock.ActiveFile] = TRUSTED
BEGIN
GetEntry: UNSAFE PROC [entry: BTree.Entry] =
BEGIN
entryPtr: FSBackdoor.EntryPtr = LOOPHOLE[entry];
lockSet: BOOLEAN;
IF entry = NIL
THEN type ← notFound
ELSE BEGIN
type ← entryPtr.type;
IF type = cached
THEN BEGIN
[a, lockSet] ← FSLock.LockRecord[vDesc.prefix, nameBody, wantedVersion];
IF lockSet
THEN BEGIN
WITH e: entryPtr^ SELECT FROM
cached => { time ← e.used; fp ← e.fp };
ENDCASE => ERROR;
END
ELSE a ← NIL;
END;
END;
END;
keyRef: REF KeyObject = CheckoutKey[wantedVersion, nameBody];
BTree.ReadEntry[tree: vDesc.tree, key: keyRef, Proc: GetEntry];
RecycleKey[keyRef];
END;
AcquireOldOrNewGName: PUBLIC PROC [vDesc: FSFileOps.VolumeDesc, nameBody: Rope.Text, wantedVersion: FSBackdoor.Version] RETURNS [fp: File.FP, a: FSLock.ActiveFile] = TRUSTED
BEGIN
GetEntry: UNSAFE PROC [entry: BTree.Entry] =
BEGIN
entryPtr: FSBackdoor.EntryPtr = LOOPHOLE[entry];
type ← notFound;
fp ← File.nullFP;
IF entry # NIL
THEN BEGIN
type ← entryPtr.type;
WITH e: entryPtr^ SELECT FROM
cached => fp ← e.fp;
ENDCASE => ERROR;
END;
[a, lockSet] ← FSLock.LockRecord[vDesc.prefix, nameBody, wantedVersion]
END;
keyRef: REF KeyObject = CheckoutKey[wantedVersion, nameBody];
type: FSBackdoor.EntryType;
lockSet: BOOLEAN;
DO
BTree.ReadEntry[tree: vDesc.tree, key: keyRef, Proc: GetEntry];
IF NOT lockSet THEN FSLock.WaitForRecord[a] ELSE EXIT;
ENDLOOP;
RecycleKey[keyRef];
END;
UpdateLocalEntry: PUBLIC PROC [vDesc: FSFileOps.VolumeDesc, nameBody: Rope.Text, version: FSBackdoor.Version, keep: CARDINAL, fp: File.FP, update: BTree.UpdateType] = TRUSTED
BEGIN
WriteEntry: UNSAFE PROCEDURE [entry: BTree.Entry] =
BEGIN
localPtr: LONG POINTER TO FSBackdoor.Entry.local = LOOPHOLE[entry];
localPtr^ ← [ SIZE[FSBackdoor.Entry.local], version, , local [keep, fp] ];
localPtr.nameBody ← AppendText[localPtr, nameBody];
END;
keyRef: REF KeyObject = CheckoutKey[version, nameBody];
BTree.UpdateEntry[tree: vDesc.tree, key: keyRef, words: SIZE[FSBackdoor.Entry.local] + SIZE[FSBackdoor.TextRep[Rope.Length[nameBody]]], Proc: WriteEntry, updateType: update];
RecycleKey[keyRef];
END;
UpdateCachedEntry: PUBLIC PROC [vDesc: FSFileOps.VolumeDesc, nameBody: Rope.Text, version: FSBackdoor.Version, used: BasicTime.GMT, fp: File.FP, update: BTree.UpdateType] = TRUSTED
BEGIN
WriteEntry: UNSAFE PROCEDURE [entry: BTree.Entry] =
BEGIN
cachedPtr: LONG POINTER TO FSBackdoor.Entry.cached = LOOPHOLE[entry];
cachedPtr^ ← [ SIZE[FSBackdoor.Entry.cached], version, , cached [used, fp] ];
cachedPtr.nameBody ← AppendText[cachedPtr, nameBody];
END;
keyRef: REF KeyObject = CheckoutKey[version, nameBody];
BTree.UpdateEntry[tree: vDesc.tree, key: keyRef, words: SIZE[FSBackdoor.Entry.cached] + SIZE[FSBackdoor.TextRep[Rope.Length[nameBody]]], Proc: WriteEntry, updateType: update];
RecycleKey[keyRef];
END;
UpdateAttachedEntry: PUBLIC PROC [vDesc: FSFileOps.VolumeDesc, nameBody: Rope.Text, version: FSBackdoor.Version, keep: CARDINAL, created: BasicTime.GMT, attachedTo: Rope.Text, update: BTree.UpdateType] = TRUSTED
BEGIN
WriteEntry: UNSAFE PROCEDURE [entry: BTree.Entry] =
BEGIN
attachedPtr: LONG POINTER TO FSBackdoor.Entry.attached = LOOPHOLE[entry];
attachedPtr^ ← [ SIZE[FSBackdoor.Entry.attached], version, , attached [keep, created, ] ];
attachedPtr.nameBody ← AppendText[attachedPtr, nameBody];
attachedPtr.attachedTo ← AppendText[attachedPtr, attachedTo];
END;
keyRef: REF KeyObject = CheckoutKey[version, nameBody];
BTree.UpdateEntry[tree: vDesc.tree, key: keyRef, words: SIZE[FSBackdoor.Entry.attached] + SIZE[FSBackdoor.TextRep[Rope.Length[nameBody]]] + SIZE[FSBackdoor.TextRep[Rope.Length[attachedTo]]], Proc: WriteEntry, updateType: update];
RecycleKey[keyRef];
END;
DeleteEntry: PUBLIC PROC [vDesc: FSFileOps.VolumeDesc, nameBody: Rope.Text, version: FSBackdoor.Version] =
BEGIN
keyRef: REF KeyObject = CheckoutKey[version, nameBody];
[] ← BTree.DeleteKey[tree: vDesc.tree, key: keyRef];
RecycleKey[keyRef];
END;
END.