YggNamingImpl.mesa
Copyright Ó 1988, 1989 by Xerox Corporation. All rights reserved.
Bob Hagmann March 21, 1989 1:48:55 pm PST
Top level naming ``interface'' for Yggdrasil.
Things to think about:
1) Is the directory caching reasonable?
2) Does locking work OK?
DIRECTORY
Ascii,
Basics USING [charsPerWord, Comparison, UnsafeBlock],
BTree,
BTreeVM,
Convert,
IO,
Process,
RefTab,
Rope USING [Equal, Flatten, FromRefText, Index, InlineFetch, Length, ROPE, Substr, Text, UnsafeMoveChars],
PBasics USING [ByteBlt, LowHalf],
YggDID USING [DID, EqualDIDs, StabilizeDID, VolatilizeDID],
YggDIDMap USING [AddComponentFile, GetComponentFiles, OpenDocumentFromDID, RemoveComponentFile],
YggDIDPrivate USING [DIDRep],
YggEnvironment USING [nullDID, nullTransID, Outcome, TransID],
YggFile USING [BytesForPages, Create, Delete, FileFromComponentFiles, FileHandle, PageCount, PagesForBytes, SetByteSize],
YggFileStream USING [StreamFromComponentFilesAndTid],
YggFixedNames USING [],
YggIndex USING [],
YggInline USING [BytesForWords, WordsForBytes],
YggInternal USING [Document, FileHandle],
YggLock USING [LockID, MakeLockID, Release, Set],
YggNaming USING [EnumProc, ErrorDesc, Version],
YggRep USING [DocType],
YggTransaction USING [CreateTrans, EqualTrans, Finish, IsNullTrans];
YggNamingImpl: CEDAR MONITOR
IMPORTS Ascii, BTree, BTreeVM, Convert, IO, PBasics, Process, RefTab, Rope, YggDID, YggDIDMap, YggFile, YggFileStream, YggInline, YggLock, YggTransaction
EXPORTS YggDID, YggNaming
~ BEGIN
Types, variables, and constants
ROPE: TYPE = Rope.ROPE;
Error: PUBLIC ERROR [error: YggNaming.ErrorDesc] = CODE;
DID: PUBLIC TYPE ~ REF DIDRep;
DIDRep: PUBLIC TYPE ~ YggDIDPrivate.DIDRep;
EntryPtr: TYPE = LONG BASE POINTER TO Entry;
nameOffset: INT = 2+ UNITS[DIDRep];
Entry: TYPE = MACHINE DEPENDENT RECORD [
size(0): CARDINAL, -- size in words of entire entry (16 bit PrincOps words and 32 bit Mimosa words)
version(1): YggNaming.Version, -- version part of name
didNamed(2): DIDRep, -- DID that is named
name(nameOffset): PACKED ARRAY [0..0) OF CHAR -- name of object, extra nulls added if needed
];
Key: TYPE = REF KeyRep;
KeyRep: TYPE = RECORD [
name: ROPE,
version: YggNaming.Version
];
AllNulls: PACKED ARRAY [0..Basics.charsPerWord) OF CHAR ← ALL[0C];
StandardCacheSize: INT ← 8;
bytesPerPage: INT ← 1024;
DirectoryCache: RefTab.Ref ← NIL;
desiredSizeOfDirectoryCache: INT ← 50;
DirectoryCacheEntry: TYPE = RECORD [
did: YggDID.DID,
isADirectory: BOOL ← FALSE,
treeStream: IO.STREAM,
btreevmHandle: BTreeVM.Handle,
tree: BTree.Tree,
unused: BOOL ← FALSE,
users: INT ← 0 -- -1 means in the process of being opened
];
scratchDirectoryCacheKey: REF DirectoryCacheEntry ← NIL;
DirectoryContentsAtom: ATOM ← $directoryContents;
DeferredList: LIST OF DeferredItem ← NIL;
DeferredItem: TYPE = RECORD[
trans: YggEnvironment.TransID,
deferredUpdate: LIST OF DeferredTransItem
];
DeferredTransItem: TYPE = RECORD[
directoryDid: YggDID.DID,
update: LIST OF DUpdateItem
];
arcode: TYPE = {update, remove, invalidate};
DUpdateItem: TYPE = RECORD[
addOrRemove: arcode,
name: ROPE,
version: ROPE,
itemDID: YggDID.DID,
updateType: BTree.UpdateType
];
DefaultDirectorySizeInPages: INT ← 7;
MyCondition: CONDITION;
oops: INT ← 0;
Transactions
PreCommit: PUBLIC PROC[tid: YggEnvironment.TransID] ~ {
deferredUpdate: LIST OF DeferredTransItem ← NIL;
deferredUpdate ← FindItemOnDeferredList[tid, FALSE];
FOR lodti: LIST OF DeferredTransItem ← deferredUpdate, lodti.rest UNTIL lodti = NIL DO
ENDLOOP;
};
Commit: PUBLIC PROC[tid: YggEnvironment.TransID] ~ {
[] ← FindItemOnDeferredList[tid, TRUE];
};
Abort: PUBLIC PROC[tid: YggEnvironment.TransID] ~ {
deferredUpdate: LIST OF DeferredTransItem ← NIL;
deferredUpdate ← FindItemOnDeferredList[tid, TRUE];
FOR lodti: LIST OF DeferredTransItem ← deferredUpdate, lodti.rest UNTIL lodti = NIL DO
RemoveDirectoryFromCache[lodti.first.directoryDid];
ENDLOOP;
};
FindItemOnDeferredList: ENTRY PROC [tid: YggEnvironment.TransID, removeIt: BOOL] RETURNS [deferredUpdate: LIST OF DeferredTransItem ← NIL] ~ {
prev: LIST OF DeferredItem ← NIL;
FOR oldi: LIST OF DeferredItem ← DeferredList, oldi.rest UNTIL oldi = NIL DO
IF YggTransaction.EqualTrans[tid, oldi.first.trans] THEN {
deferredUpdate ← oldi.first.deferredUpdate;
IF removeIt THEN {
IF prev = NIL THEN DeferredList ← oldi.rest
ELSE prev.rest ← oldi.rest;
};
EXIT;
};
prev ← oldi;
ENDLOOP;
};
RememberDeferredUpdate: ENTRY PROC [trans: YggEnvironment.TransID, directoryDid: YggDID.DID, addOrRemove: arcode, name: ROPE, version: ROPE, itemDID: YggDID.DID, updateType: BTree.UpdateType]~ {
dupdate: DUpdateItem ← [addOrRemove, name, version, itemDID, updateType];
FOR oldi: LIST OF DeferredItem ← DeferredList, oldi.rest UNTIL oldi = NIL DO
IF YggTransaction.EqualTrans[trans, oldi.first.trans] THEN {
deferredUpdate: LIST OF DeferredTransItem;
FOR deferredUpdate ← oldi.first.deferredUpdate, deferredUpdate.rest UNTIL deferredUpdate.rest = NIL DO
ENDLOOP;
deferredUpdate.rest ← CONS[[directoryDid, LIST[dupdate]], NIL];
EXIT;
};
REPEAT FINISHED => DeferredList ← CONS [[trans, LIST[[directoryDid, LIST[dupdate]]]], DeferredList];
ENDLOOP;
};
Directories
MkDir: PUBLIC PROC [trans: YggEnvironment.TransID, did: YggDID.DID] RETURNS [directoryAlreadyExists: BOOL ← TRUE] ~ {
Make a new directory.
effectiveTrans: YggEnvironment.TransID;
doc: YggInternal.Document ← NIL;
granted: BOOL ← FALSE;
released: BOOL ← FALSE;
pageSize: YggFile.PageCount;
didLockID: YggLock.LockID;
componentFiles: LIST OF YggInternal.FileHandle;
newFile: YggInternal.FileHandle ← NIL;
didLockID ← YggLock.MakeLockID[did];
effectiveTrans ← IF YggTransaction.IsNullTrans[trans] THEN YggTransaction.CreateTrans[YggEnvironment.nullTransID] ELSE trans;
granted ← YggLock.Set[trans: effectiveTrans, lock: didLockID, mode: directoryWrite, wait: FALSE];
IF ~granted THEN RETURN[TRUE];
doc ← YggDIDMap.OpenDocumentFromDID[did, effectiveTrans];
componentFiles ← YggDIDMap.GetComponentFiles[doc];
IF YggFile.FileFromComponentFiles [componentFiles: componentFiles, fileUse: DirectoryContentsAtom] # NIL THEN {
released ← YggLock.Release[trans: effectiveTrans, lock: didLockID, mode: directoryWrite];
IF YggTransaction.IsNullTrans[trans] THEN [] ← YggTransaction.Finish[transID: effectiveTrans, requestedOutcome: abort];
RETURN[TRUE];
};
pageSize ← DefaultDirectorySizeInPages * YggFile.PagesForBytes[bytesPerPage];
newFile ← YggFile.Create[size: pageSize, did: did, fileUse: DirectoryContentsAtom, nearToDid: did, tid: effectiveTrans];
YggFile.SetByteSize[newFile, YggFile.BytesForPages[pageSize], effectiveTrans];
YggDIDMap.AddComponentFile[doc: doc, componentFile: newFile, tid: effectiveTrans];
[] ← OpenDir[did: did, fileUse: DirectoryContentsAtom, cacheSize: StandardCacheSize, initialize: TRUE, trans: trans];
DoneWithDirectory[did];
IF YggTransaction.IsNullTrans[trans] THEN {
outcome: YggEnvironment.Outcome;
outcome ← YggTransaction.Finish[transID: effectiveTrans, requestedOutcome: commit];
IF outcome # commit THEN ERROR Error[[$commitFailed, "bug: commit failed in MkDir in Naming, but it really should succeed"]];
};
RememberDeferredUpdate[trans, did, invalidate, NIL, NIL, YggEnvironment.nullDID, insert];
RETURN[FALSE];
};
RmDir: PUBLIC PROC [trans: YggEnvironment.TransID, did: YggDID.DID] RETURNS [directoryDoesNotExist: BOOL ← FALSE] ~ {
Destroy a directory.
doc: YggInternal.Document ← NIL;
granted: BOOL ← FALSE;
released: BOOL ← FALSE;
didLockID: YggLock.LockID;
componentFiles: LIST OF YggInternal.FileHandle;
oldFile: YggInternal.FileHandle ← NIL;
IF YggTransaction.IsNullTrans[trans] THEN ERROR Error[[$nullTransaction, "RmDir in Naming needs a transaction"]];
didLockID ← YggLock.MakeLockID[did];
granted ← YggLock.Set[trans: trans, lock: didLockID, mode: directoryWrite, wait: FALSE];
IF ~granted THEN ERROR Error[[$cantGetDirectoryLock, "RmDir in Naming could not get a write lock; a retry might work."]];
doc ← YggDIDMap.OpenDocumentFromDID[did, trans];
componentFiles ← YggDIDMap.GetComponentFiles[doc];
IF (oldFile ← YggFile.FileFromComponentFiles[componentFiles: componentFiles, fileUse: DirectoryContentsAtom]) = NIL THEN RETURN[FALSE];
YggDIDMap.RemoveComponentFile[doc: doc, componentFile: oldFile, tid: trans];
YggFile.Delete[file: oldFile, tid: trans];
RemoveDirectoryFromCache[did];
};
Files
Lookup: PUBLIC PROC [trans: YggEnvironment.TransID, directoryDid: YggDID.DID, namePattern: ROPE, version: ROPE] RETURNS [nameFound: BOOL ← FALSE, moreThanOneMatch: BOOL ← FALSE, didFound: YggDID.DID ← YggEnvironment.nullDID, nameMatched: ROPE ← NIL, versionMatched: ROPE ← NIL] ~ {
Look up the name/version in the directory property of the directoryDid. The namePattern may include "*" characters. The version is either NIL (highest version), "h" (highest version), "l" (lowest version), or the ASCII string for a number (base 10). If nameFound is TRUE, then the name/version specifies a single file and it's did is returned in didFound while its name/version is returned in nameMatched and versionMatched. If nameFound is FALSE but moreThanOneMatch is TRUE, then the name/version specifies more than one file. didFound is not interesting. If both nameFound and moreThanOneMatch are FALSE, then no names match the name/version and didFound is not interesting.
foundProc: YggNaming.EnumProc ~ {
nameFound ← TRUE;
IF numberFound > 0 THEN {
moreThanOneMatch ← TRUE;
didFound ← YggEnvironment.nullDID;
RETURN[stop: TRUE];
};
numberFound ← numberFound + 1;
moreThanOneMatch ← FALSE;
didFound ← did;
nameMatched ← Rope.FromRefText[name];
versionMatched ← Convert.RopeFromInt[version];
};
numberFound: INT ← 0;
[] ← EnumerateEntries[trans, directoryDid, namePattern, version, NIL, NIL, foundProc];
};
VersionMatching: TYPE = {all, bangHOnly, bangLOnly, numberMatch};
EnumerateEntries: PUBLIC PROC [trans: YggEnvironment.TransID, directoryDid: YggDID.DID, namePattern: ROPE, version: ROPE, nameToStart: ROPE, nameToStartVersion: ROPE, proc: YggNaming.EnumProc] RETURNS [notADirectory: BOOL ← TRUE, completedEnumerate: BOOL ← TRUE] ~ {
Calls `proc' for each entry in the specified matching key values. The enumeration is halted when either the matching of entries is exhausted or `proc' returns FALSE
enumProc: UNSAFE PROC [entry: BTree.Entry] RETURNS [continue: BOOL ← TRUE] = TRUSTED {
maxEntryChars: INT;
entryPtr: EntryPtr = LOOPHOLE[entry];
maxEntryChars ← YggInline.BytesForWords[entryPtr.size - WORDS[Entry]];
IF matching = numberMatch THEN {
countSinceLastClashTest ← countSinceLastClashTest + 1;
IF countSinceLastClashTest < 10 AND keyRef.version # entryPtr.version THEN RETURN[TRUE]; -- wrong version
countSinceLastClashTest ← 0;
};
SELECT Match[@entryPtr.name, maxEntryChars, flatNamePattern] FROM
fit => {
makeRefTextName: UNSAFE PROC [charArray: LONG POINTER TO PACKED ARRAY [0..0) OF CHAR, maxSize: INT] RETURNS [textName: REF TEXT] ~ {
GetText: UNSAFE PROC [textRep: LONG POINTER TO PACKED ARRAY [0..0) OF CHAR, text: REF TEXT] = UNCHECKED {
text.length ← nameSize;
[] ← PBasics.ByteBlt [
to: [ BASE[DESCRIPTOR[text]], 0, nameSize ],
from: [ charArray, 0, nameSize ]
];
};
nameSize: INT ← maxSize;
WHILE nameSize > 0 DO
IF charArray^[nameSize-1] # 0C THEN EXIT;
nameSize ← nameSize-1;
ENDLOOP;
textName ← NEW[TEXT[nameSize]];
GetText[charArray, LOOPHOLE[textName]];
};
name: REF TEXT ← NIL;
IF matching = numberMatch AND (keyRef.version # entryPtr.version) THEN RETURN[TRUE]; -- wrong version
name ← makeRefTextName[@entryPtr.name, maxEntryChars];
continue ← ~proc[name, entryPtr.version, YggDID.VolatilizeDID[buffer: @entryPtr.didNamed]];
RETURN;
};
compatible => RETURN[TRUE];
clash => RETURN[FALSE];
ENDCASE => ERROR;
};
granted: BOOL ← FALSE;
tree: BTree.Tree;
didLockID: YggLock.LockID;
countSinceLastClashTest: INT ← 0;
matching: VersionMatching ← all;
flatNamePattern: Rope.Text = Rope.Flatten[namePattern];
keyRef: Key ← NIL;
start: Rope.Text = Rope.Flatten[Rope.Substr[namePattern, 0, Rope.Index[namePattern, 0, "*"]]];
keyRef ← CheckoutKey[];
keyRef.name ← start;
didLockID ← YggLock.MakeLockID[directoryDid];
granted ← YggLock.Set[trans: trans, lock: didLockID, mode: directoryRead, wait: FALSE];
IF ~granted THEN ERROR Error[[$cantGetDirectoryLock, "EnumerateEntries in Naming could not get a read lock; a retry might work."]];
[tree: tree] ← GetTreeForDID[directoryDid];
IF tree = NIL THEN RETURN[TRUE, TRUE];
notADirectory ← FALSE;
SELECT TRUE FROM
Rope.Equal[version, "*"], Rope.Equal[version, ""] => {
keyRef.version ← [0];
matching ← all;
};
Rope.Equal[version, "h", FALSE]=> {
keyRef.version ← [0];
matching ← bangHOnly;
};
Rope.Equal[version, "l", FALSE]=> {
keyRef.version ← [0];
matching ← bangLOnly;
};
ENDCASE => {
notInt: BOOL ← FALSE;
matching ← numberMatch;
keyRef.version ← [Convert.CardFromRope[version ! Convert.Error => {notInt ← TRUE; CONTINUE}]];
IF notInt THEN {
DoneWithDirectory[directoryDid];
ERROR Error[[$badVersionSpec, "The version specification is bogus"]];
};
};
TRUSTED {[] ← BTree.EnumerateEntries[tree: tree, relation: greater, key: keyRef, pathStk: NIL, useExistingPath: FALSE, Proc: enumProc];};
DoneWithDirectory[directoryDid];
IF ~YggLock.Release[trans: trans, lock: didLockID, mode: directoryRead] THEN ERROR;
RecycleKey[keyRef];
};
MatchResult: TYPE = {fit, compatible, clash};
The match result is computed on the assumtion that name is always GE the pattern prefix (characters up to the first star). In this case, "compatible" means that it is sensible to present another name GE the current one, and "clash" means that such a name cannot "fit".
Match: UNSAFE PROC [name: LONG POINTER TO PACKED ARRAY [0..0) OF CHAR, maxNameSize: INT, pattern: Rope.Text] RETURNS [MatchResult] = UNCHECKED {
SubMatch: PROC [i1: INT, len1: INT, i2: INT, len2: INT] RETURNS [MatchResult] = TRUSTED {
"1" is the pattern, "2" is the name
WHILE len1 > 0 DO
c1: CHAR = pText[i1];
IF c1 = '*
THEN { -- quick kill for * at end of pattern
IF len1 = 1 THEN RETURN [fit];
else must take all combinations
{ -- first, accept the *
j1: INT = i1 + 1;
nlen1: INT = len1 - 1;
j2: INT ← i2;
nlen2: INT ← len2;
WHILE nlen2 >= 0 DO
IF SubMatch[j1, nlen1, j2, nlen2] = fit THEN RETURN [fit];
j2 ← j2 + 1;
nlen2 ← nlen2 - 1;
ENDLOOP;
};
RETURN [compatible];
};
IF len2 = 0 THEN RETURN [compatible];
at this point demand an exact match in both strings
IF Ascii.Upper[c1] # Ascii.Upper[name[i2]] THEN RETURN [clash];
i1 ← i1 + 1;
len1 ← len1 - 1;
i2 ← i2 + 1;
len2 ← len2 - 1;
ENDLOOP;
RETURN [IF len2 = 0 THEN fit ELSE clash];
};
pText: REF TEXT = LOOPHOLE[pattern];
nameSize: INT ← maxNameSize;
WHILE nameSize > 0 DO
IF name^[nameSize-1] # 0C THEN EXIT;
nameSize ← nameSize-1;
ENDLOOP;
RETURN [SubMatch [0, pText.length, 0, nameSize]];
};
Directroy manipulation
SimpleEntryProc: YggNaming.EnumProc = { -- for debugging purposes
[name: REF TEXT, version: Version, did: YggDID.DID] RETURNS [continue: BOOL]
cont: BOOLEAN ← TRUE;
set breakpoint here to look at entry
RETURN[cont];
};
UpdateItem: PUBLIC PROC [trans: YggEnvironment.TransID, directoryDid: YggDID.DID, name: ROPE, version: ROPE, did: YggDID.DID, updateType: BTree.UpdateType ← insertOrReplace] RETURNS [notADirectory: BOOL ← FALSE, nameFound: BOOL ← FALSE] ~ {
Adds a new entry to the index.
writeEntryInner: UNSAFE PROCEDURE [entry: BTree.Entry] = UNCHECKED {
nBytes: INT;
nullsToMove: INT;
entryPtr: EntryPtr = LOOPHOLE[entry];
entryPtr.version ← keyRef.version;
entryPtr.size ← entSize;
YggDID.StabilizeDID[did: did, buffer: @entryPtr.didNamed];
TRUSTED {nBytes ← Rope.UnsafeMoveChars[block: [LOOPHOLE[@entryPtr.name], 0, nameSize], rope: name, start: 0];};
nullsToMove ← YggInline.BytesForWords[YggInline.WordsForBytes[nameSize]] - nameSize;
IF nullsToMove < 0 THEN ERROR;
TRUSTED {nBytes ← PBasics.ByteBlt[
from: [blockPointer: @AllNulls, startIndex: 0, stopIndexPlusOne: nullsToMove],
to: [blockPointer: @entryPtr.name, startIndex: nameSize, stopIndexPlusOne: nameSize+nullsToMove]];
};
IF nBytes # nullsToMove THEN ERROR;
};
granted: BOOL ← FALSE;
didLockID: YggLock.LockID;
nameSize: INT;
keyRef: Key ← NIL;
entSize: INT;
tree: BTree.Tree;
notInt: BOOL ← FALSE;
treeStream: IO.STREAM;
IF YggTransaction.IsNullTrans[trans] THEN ERROR Error[[$nullTransaction, "UpdateItem in Naming needs a transaction"]];
nameSize ← Rope.Length[name];
entSize ← YggInline.WordsForBytes[nameSize] + WORDS[Entry];
keyRef ← CheckoutKey[];
keyRef.name ← name;
keyRef.version ← [Convert.CardFromRope[version ! Convert.Error => {notInt ← TRUE; CONTINUE}]];
IF notInt AND ~(Rope.Equal[version, "h", FALSE]) THEN ERROR Error[[$badVersionSpec, "The version specification is bogus"]];
didLockID ← YggLock.MakeLockID[directoryDid];
granted ← YggLock.Set[trans: trans, lock: didLockID, mode: directoryWrite, wait: FALSE];
IF ~granted THEN ERROR Error[[$cantGetDirectoryLock, "UpdateItem in Naming could not get a write lock; a retry might work."]];
[tree, treeStream] ← GetTreeForDID[directoryDid];
NewTransForStream[trans, treeStream];
IF notInt THEN { -- highest or lowest version has to be found
notADirectory: BOOL ← TRUE;
completedEnumerate: BOOL ← TRUE;
foundSomething: BOOL ← FALSE;
versionFound: YggNaming.Version;
enumProc: YggNaming.EnumProc ~ {
PROC [name: REF TEXT, version: Version, did: YggDID.DID] RETURNS [stop: BOOL ← FALSE];
foundSomething ← TRUE;
versionFound ← version;
RETURN[TRUE];
};
[notADirectory: notADirectory, completedEnumerate: completedEnumerate] ← EnumerateEntries[trans: trans, directoryDid: directoryDid, namePattern: name, version: version, nameToStart: name, nameToStartVersion: version, proc: enumProc];
IF notADirectory THEN {
DoneWithDirectory[directoryDid];
RETURN[TRUE, FALSE];
};
SELECT TRUE FROM
foundSomething AND updateType = insert => {
keyRef.version ← [versionFound+1];
};
foundSomething AND (updateType = replace OR updateType = insertOrReplace) => {
keyRef.version ← versionFound;
};
~foundSomething AND (updateType = insert OR updateType = insertOrReplace) => {
keyRef.version ← [1];
};
~foundSomething AND updateType = replace => {
DoneWithDirectory[directoryDid];
IF ~YggLock.Release[trans: trans, lock: didLockID, mode: directoryWrite] THEN ERROR;
RETURN[FALSE, FALSE]
};
ENDCASE => ERROR;
};
TRUSTED {BTree.UpdateEntry[tree: tree, key: keyRef, pathStk: NIL, useExistingPath: FALSE, words: entSize, Proc: writeEntryInner, updateType: updateType ! BTree.Error => {
SELECT reason FROM
wrongUpdateType => {nameFound ← TRUE; CONTINUE;};
ENDCASE ;
};
];};
RememberDeferredUpdate[trans, directoryDid, invalidate, NIL, NIL, YggEnvironment.nullDID, insert];
DoneWithDirectory[directoryDid];
RecycleKey[keyRef];
};
DeleteItem: PUBLIC PROC [trans: YggEnvironment.TransID, directoryDid: YggDID.DID, name: ROPE, version: ROPE] RETURNS [found: BOOLEAN] ~ {
Deletes the entry that contains the given attribute value for the given key.
keyRef: Key ← NIL;
tree: BTree.Tree;
granted: BOOL ← FALSE;
didLockID: YggLock.LockID;
notInt: BOOL ← FALSE;
treeStream: IO.STREAM;
IF YggTransaction.IsNullTrans[trans] THEN ERROR Error[[$nullTransaction, "UpdateItem in Naming needs a transaction"]];
keyRef ← CheckoutKey[];
keyRef.name ← name;
keyRef.version ← [Convert.CardFromRope[version ! Convert.Error => {notInt ← TRUE; CONTINUE}]];
IF notInt THEN {
ERROR Error[[$badVersionSpec, "The version specification is bogus"]];
};
didLockID ← YggLock.MakeLockID[directoryDid];
granted ← YggLock.Set[trans: trans, lock: didLockID, mode: directoryWrite, wait: FALSE];
IF ~granted THEN ERROR Error[[$cantGetDirectoryLock, "DeleteItem in Naming could not get a write lock; a retry might work."]];
[tree, treeStream] ← GetTreeForDID[directoryDid];
NewTransForStream[trans, treeStream];
found ← BTree.DeleteKey[tree: tree, key: keyRef, pathStk: NIL, useExistingPath: FALSE];
RememberDeferredUpdate[trans, directoryDid, invalidate, NIL, NIL, YggEnvironment.nullDID, insert];
DoneWithDirectory[directoryDid];
RecycleKey[keyRef];
};
HasDirectory: PUBLIC PROC [trans: YggEnvironment.TransID, directoryDid: YggDID.DID] RETURNS [isDirectory: BOOL] ~ {
Returns TRUE iff there is a directory contents
tree: BTree.Tree;
[tree: tree] ← GetTreeForDID[directoryDid];
IF tree = NIL THEN RETURN [FALSE] ELSE {
DoneWithDirectory[directoryDid];
RETURN [TRUE];
};
};
BTreeVM related procedures
GetTreeForDID: PROC [directoryDid: YggDID.DID] RETURNS [tree: BTree.Tree, treeStream: IO.STREAM ← NIL] ~ {
Must call DoneWithDirectory[treeStream] when done!!
[tree, treeStream] ← OpenDir[directoryDid, DirectoryContentsAtom, StandardCacheSize, FALSE];
};
OpenDir: PROC [did: YggDID.DID, fileUse: ATOM, cacheSize: BTreeVM.CacheSize, initialize: BOOL, trans: YggEnvironment.TransID ← YggEnvironment.nullTransID] RETURNS [tree: BTree.Tree ← NIL, treeStream: IO.STREAM ← NIL] ~ {
Initiates directory activity. This can be called any number of times to get a new directory handle or reopen a directory that has been closed.
btreevmHandle: BTreeVM.Handle ← NIL;
ce: REF DirectoryCacheEntry;
found: BOOL;
innerOpen: ENTRY PROC = {
val: RefTab.Val;
scratchDirectoryCacheKey.did ← did;
[found, val] ← RefTab.Fetch[x: DirectoryCache, key: scratchDirectoryCacheKey];
IF found THEN {
ce ← NARROW[val];
WHILE ce.users = -1 DO WAIT MyCondition; ENDLOOP;
IF ce.isADirectory THEN {
ce.users ← ce.users + 1;
IF ce.unused THEN {
ce.unused ← FALSE;
};
};
}
ELSE {
ce ← NEW[DirectoryCacheEntry ← [did, TRUE, treeStream, NIL, NIL, FALSE, -1]];
IF ~RefTab.Insert[x: DirectoryCache, key: ce, val: ce] THEN ERROR;
scratchDirectoryCacheKey ← NEW[DirectoryCacheEntry]; -- used to use scratchDirectoryCacheKey as a key
};
};
innerOpen[];
IF found THEN {
IF ~ce.isADirectory THEN RETURN[NIL, NIL];
treeStream ← ce.treeStream;
tree ← ce.tree;
IF ~YggTransaction.IsNullTrans[trans] THEN {
NewTransForStream[trans, treeStream];
};
}
ELSE {
opened: ENTRY PROC = {
ce.users ← 1;
BROADCAST MyCondition;
};
letGo: ENTRY PROC = {
ce.users ← 0;
BROADCAST MyCondition;
};
doc: YggInternal.Document ← NIL;
componentFiles: LIST OF YggFile.FileHandle;
doc ← YggDIDMap.OpenDocumentFromDID[did, trans];
componentFiles ← YggDIDMap.GetComponentFiles[doc];
IF YggFile.FileFromComponentFiles[componentFiles, DirectoryContentsAtom] = NIL THEN {
ce.isADirectory ← FALSE;
letGo[];
RETURN[NIL, NIL];
};
treeStream ← NewStreamForBTreeVM[componentFiles, trans];
NewTransForStream[trans, treeStream];
NewReadStreamForStream [trans: trans, stream: treeStream]; -- use this trans for read while doing init
IF treeStream = NIL THEN RETURN[NIL, NIL];
btreevmHandle ← BTreeVM.Open[treeStream, bytesPerPage, cacheSize, 0];
ce.btreevmHandle ← btreevmHandle;
ce.treeStream ← treeStream;
tree ← BTree.New[
repPrim: [compare: Compare, entrySize: EntrySize],
storPrim: [referencePage: BTreeVM.ReferencePage, releasePage: BTreeVM.ReleasePage],
minEntrySize: SIZE[YggRep.DocType] + SIZE[CARD],
initialState: suspended
];
BTree.Open[
tree: tree,
storage: btreevmHandle,
pageSize: bytesPerPage,
initialize: initialize,
maintainRecomputableState: TRUE
];
ce.tree ← tree;
NullReadStreamForStream [stream: treeStream]; -- use null trans next time
opened[];
SafeStorage.EnableFinalization[h];
};
};
DoneWithDirectory: ENTRY PROC [ directoryDid: YggDID.DID ] = {
Done with the current use of the BTree.
ce: REF DirectoryCacheEntry;
found: BOOL;
val: RefTab.Val;
scratchDirectoryCacheKey.did ← directoryDid;
[found, val] ← RefTab.Fetch[x: DirectoryCache, key: scratchDirectoryCacheKey];
IF found THEN {
ce ← NARROW[val];
ce.users ← ce.users - 1;
}
ELSE oops ← oops + 1; -- debugging
};
RemoveDirectoryFromCache: ENTRY PROC [ directoryDid: YggDID.DID ] = {
RmDir has removed it.
scratchDirectoryCacheKey.did ← directoryDid;
[] ← RefTab.Delete[x: DirectoryCache, key: scratchDirectoryCacheKey];
};
Compare: UNSAFE PROC [key: BTree.Key, entry: BTree.Entry] RETURNS [result: Basics.Comparison ← equal] = UNCHECKED {
keyRef: Key = NARROW[key];
entryPtr: EntryPtr = LOOPHOLE[entry];
maxEntryChars: INT;
keySize: INT;
maxEntryChars ← YggInline.BytesForWords[entryPtr.size - WORDS[Entry]];
keySize ← Rope.Length[keyRef.name];
FOR inx: INT IN [0..MIN[maxEntryChars, keySize]) DO
entryChar: CHAR;
keyChar: CHAR;
IF (entryChar ← entryPtr.name[inx]) = 0C THEN RETURN[greater];
keyChar ← Rope.InlineFetch[keyRef.name, inx];
IF entryChar = keyChar THEN LOOP;
IF keyChar < entryChar THEN RETURN [less] ELSE RETURN [greater];
ENDLOOP;
IF maxEntryChars < keySize THEN RETURN [greater];
IF maxEntryChars > keySize THEN {
IF entryPtr.name[keySize] # 0C THEN RETURN [less];
};
SELECT keyRef.version FROM
> entryPtr.version => RETURN[greater];
< entryPtr.version => RETURN[less];
ENDCASE => RETURN[equal];
};
EntrySize: UNSAFE PROC [entry: BTree.Entry] RETURNS [words: BTree.EntSize ← 4] = UNCHECKED {
entryPtr: EntryPtr = LOOPHOLE[entry];
RETURN[entryPtr.size];
};
My streams
myStreamProcs: REF IO.StreamProcs ← IO.CreateStreamProcs[variety: inputOutput, class: $YggdrasilDirectory, unsafeGetBlock: myUnsafeGetBlock, unsafePutBlock: myUnsafePutBlock, flush: myFlush, getLength: myGetLength, setIndex: mySetIndex];
MyStream: TYPE = REF MyStreamRep;
MyStreamRep: TYPE = RECORD [
tid: YggEnvironment.TransID,
componentFiles: LIST OF YggInternal.FileHandle,
readStream: IO.STREAM,
readStreamTid: YggEnvironment.TransID,
currentWriteStream: IO.STREAM,
writeStreamPos: INT ← -1
];
NewStreamForBTreeVM: PROC [componentFiles: LIST OF YggInternal.FileHandle, trans: YggEnvironment.TransID] RETURNS [stream: IO.STREAM] = {
stream ← IO.CreateStream[streamProcs: myStreamProcs, streamData: NEW[MyStreamRep ← [tid: trans, componentFiles: componentFiles, readStream: NIL, readStreamTid: YggEnvironment.nullTransID, currentWriteStream: NIL]], backingStream: NIL];
};
NewTransForStream: PROC [trans: YggEnvironment.TransID, newStream: IO.STREAM] = {
myStream: MyStream = NARROW[newStream.streamData];
IF ~YggTransaction.EqualTrans[trans, myStream.tid] THEN {
myStream.tid ← trans;
myStream.currentWriteStream ← NIL;
myStream.writeStreamPos ← -1;
};
};
NullReadStreamForStream: PROC [stream: IO.STREAM] = {
myStream: MyStream = NARROW[stream.streamData];
myStream.readStream ← NIL;
myStream.readStreamTid ← YggEnvironment.nullTransID;
};
NewReadStreamForStream: PROC [trans: YggEnvironment.TransID, stream: IO.STREAM] = {
myStream: MyStream = NARROW[stream.streamData];
myStream.readStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: myStream.componentFiles, fileUse: DirectoryContentsAtom, tid: trans, readOnly: TRUE];
myStream.readStreamTid ← trans;
};
myUnsafeGetBlock: UNSAFE PROC [self: IO.STREAM, block: Basics.UnsafeBlock] RETURNS [nBytesRead: INT] ~ TRUSTED {
myStream: MyStream = NARROW[self.streamData];
IF myStream.readStream = NIL OR (~YggTransaction.IsNullTrans[myStream.readStreamTid] AND ~YggTransaction.EqualTrans[myStream.tid, myStream.readStreamTid]) THEN {
myStream.readStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: myStream.componentFiles, fileUse: DirectoryContentsAtom, tid: YggEnvironment.nullTransID, readOnly: TRUE];
myStream.readStreamTid ← YggEnvironment.nullTransID;
};
nBytesRead ← IO.UnsafeGetBlock[myStream.readStream, block];
};
myUnsafePutBlock: PROC [self: IO.STREAM, block: Basics.UnsafeBlock] ~ {
myStream: MyStream = NARROW[self.streamData];
IF myStream.currentWriteStream = NIL THEN {
myStream.currentWriteStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: myStream.componentFiles, fileUse: DirectoryContentsAtom, tid: myStream.tid];
};
IF myStream.writeStreamPos # -1 THEN {
IO.SetIndex[self: myStream.currentWriteStream, index: myStream.writeStreamPos] ;
myStream.writeStreamPos ← -1;
};
IO.UnsafePutBlock[myStream.currentWriteStream, block];
};
myFlush: PROC [self: IO.STREAM] ~ {
myStream: MyStream = NARROW[self.streamData];
IF myStream.currentWriteStream = NIL THEN {
myStream.currentWriteStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: myStream.componentFiles, fileUse: DirectoryContentsAtom, tid: myStream.tid];
};
IF myStream.writeStreamPos # -1 THEN {
IO.SetIndex[self: myStream.currentWriteStream, index: myStream.writeStreamPos] ;
myStream.writeStreamPos ← -1;
};
IO.Flush[myStream.currentWriteStream];
};
myGetLength: PROC [self: IO.STREAM] RETURNS [length: INT] ~ {
myStream: MyStream = NARROW[self.streamData];
IF myStream.readStream = NIL OR (~YggTransaction.IsNullTrans[myStream.readStreamTid] AND ~YggTransaction.EqualTrans[myStream.tid, myStream.readStreamTid]) THEN {
myStream.readStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: myStream.componentFiles, fileUse: DirectoryContentsAtom, tid: YggEnvironment.nullTransID, readOnly: TRUE];
myStream.readStreamTid ← YggEnvironment.nullTransID;
};
length ← IO.GetLength[myStream.readStream];
};
mySetIndex: PROC [self: IO.STREAM, index: INT] ~ {
myStream: MyStream = NARROW[self.streamData];
IF myStream.readStream = NIL OR (~YggTransaction.IsNullTrans[myStream.readStreamTid] AND ~YggTransaction.EqualTrans[myStream.tid, myStream.readStreamTid]) THEN {
myStream.readStream ← YggFileStream.StreamFromComponentFilesAndTid[componentFiles: myStream.componentFiles, fileUse: DirectoryContentsAtom, tid: YggEnvironment.nullTransID, readOnly: TRUE];
myStream.readStreamTid ← YggEnvironment.nullTransID;
};
IO.SetIndex[self: myStream.readStream, index: index ! IO.EndOfStream => CONTINUE];
IF myStream.currentWriteStream # NIL THEN {
IO.SetIndex[self: myStream.currentWriteStream, index: index] ;
myStream.writeStreamPos ← -1;
}
ELSE myStream.writeStreamPos ← index;
};
Utilities
stockKeys: ARRAY [0..numberOfStockKeys] OF Key ← ALL[NIL];
numberOfStockKeys: INT = 10;
stockKeyIndex: INT ← 0;
CheckoutKey: ENTRY PROC RETURNS [k: Key] = {
IF stockKeyIndex = 0 THEN k ← NEW [KeyRep]
ELSE {
stockKeyIndex ← stockKeyIndex - 1;
k ← stockKeys[stockKeyIndex];
};
};
RecycleKey: ENTRY PROC [k: Key] = {
IF stockKeyIndex < numberOfStockKeys THEN {
stockKeys[stockKeyIndex] ← k;
stockKeyIndex ← stockKeyIndex + 1;
};
};
Equals and hash
equalProc: RefTab.EqualProc = {
PROC [key1, key2: Key] RETURNS [BOOL];
k1: REF DirectoryCacheEntry;
k2: REF DirectoryCacheEntry;
k1 ← NARROW[key1];
k2 ← NARROW[key2];
RETURN [YggDID.EqualDIDs[k1.did, k2.did]];
};
hashProc: RefTab.HashProc = {
PROC PROC [key: Key] RETURNS [CARDINAL];
keyRef: REF DirectoryCacheEntry;
keyRef ← NARROW[key];
RETURN [PBasics.LowHalf[keyRef.did.didLow]];
};
Initialization, cache trim, and finalization
NamingCacheTrimProcess: PROC = {
ticksToWait: Process.Ticks;
ticksToWait ← Process.MsecToTicks[1315];
DO
innerTrim: ENTRY PROC = {
eachPairAction: RefTab.EachPairAction = {
PROC [key: Key, val: Val] RETURNS [quit: BOOL ← FALSE];
ce: REF DirectoryCacheEntry;
ce ← NARROW[val];
IF ce.unused THEN {
[] ← RefTab.Delete[x: DirectoryCache, key: ce];
size ← size - 1;
IF size <= desiredSizeOfDirectoryCache THEN quit ← TRUE;
}
ELSE ce.unused ← TRUE;
};
size: INT;
size ← RefTab.GetSize[DirectoryCache];
[] ← RefTab.Pairs[x: DirectoryCache, action: eachPairAction];
};
Process.Pause[ticksToWait];
IF RefTab.GetSize[DirectoryCache] > desiredSizeOfDirectoryCache THEN innerTrim[];
ENDLOOP;
};
Initialization
TRUSTED {
Process.Detach[FORK NamingCacheTrimProcess];
Process.SetTimeout[condition: @MyCondition, ticks: Process.MsecToTicks[171]];
};
DirectoryCache ← RefTab.Create[mod: 47, equal: equalProc, hash: hashProc];
scratchDirectoryCacheKey ← NEW[DirectoryCacheEntry];
END.