// IFSDirLookup.bcpl -- Lookup names in IFS directory
// Copyright Xerox Corporation 1979, 1980, 1981, 1982
// Last modified July 12, 1982 4:13 PM by Taft
get "Ifs.decl"
get "IfsFiles.decl"
get "IfsDirs.decl"
get "BTree.decl"
external
[
// Outgoing procedures
LookupIFSFile; LookupFD; NextFD; InstallDR
LockDirFD; UnlockDirFD; ModifyDirFD
// Incoming procedures -- IFSDirs
CreateFD; DestroyFD; ParseFD; UpdateFD; IFSAppendVersion
NamesMatch; DirCompareKey
// Incoming procedures -- B-Tree
ReadRecLE; MapTree
// Incoming procedures -- rest of IFS
IFSError; CopyString; FreePointer; MatchKPMTemplate
Lock; Unlock; Block; Yield; LockCell; UnlockCell; NoticeDirectoryChange
// Incoming procedures -- operating system
DefaultArgs; SysAllocate; SysAllocateZero; SysFree; MoveBlock
// Incoming statics
CtxRunning
]
manifest
[
// assumed maximum size of PathStk: existing IFS directory B-Trees
// never exceed 3 levels, so leave room for 4 levels to be ultra-conservative.
lenPathStk = (offset PS.PSE↑5)/16
]
//----------------------------------------------------------------------------
let LookupIFSFile(name, lc, lvErrorCode, fs, dirName; numargs na) = valof
//----------------------------------------------------------------------------
// Combines the operations of CreateFD and LookupFD.
// Returns the fd if successful and zero if unsuccessful.
// The error code is stored in @lvErrorCode; zero is stored upon success.
// The directory should not be locked by the caller and is not locked
// upon return.
[
DefaultArgs(lv na, -2, lv na, 0, 0)
let fd = CreateFD(name, lc, lvErrorCode, fs, dirName)
if fd ne 0 then
[
@lvErrorCode = LookupFD(fd)
if @lvErrorCode ne 0 then fd = DestroyFD(fd)
]
resultis fd
]
//----------------------------------------------------------------------------
and LookupFD(fd, lockMode, requireExists; numargs na) = valof
//----------------------------------------------------------------------------
// Looks up the file described by the FD structure "fd", applying
// the lookup control parameters in the fd as appropriate.
// If the file already exists, the directory record (dr) in the
// fd is replaced by the actual entry that was found.
// If the file does not exist and the lookup control says that
// a new file may be created, a directory record is generated
// which may be used in creating the file (however, the new file
// is not actually created by LookupFD). This procedure should
// ordinarily be called with the directory unlocked, and returns with
// the directory unlocked; however, other lock actions may be specified
// by lockMode (see IfsDirs.decl). Returns zero if successful and
// an error code if unsuccessful. If the lookup is successful,
// the code in fd>>FD.lookupStatus describes the outcome:
// lsNonexistent: the file does not exist and no other version
// exists either. to create the file, directory-default
// properties must be used.
// lsOtherVersion: the specified version doesn't exist, but
// another version does. the FP of that version is stored
// in the dr for use in obtaining its properties.
// lsExists: the specified file exists, and its dr is stored
// in the fd.
// Note that it is ok to call LookupFD multiple times on the same
// fd. This is necessary to "re-validate" an fd that has become
// invalid due to the directory being unlocked.
// If requireExists is true the file is required to exist, regardless of
// the lookup control; if false or omitted, a nonexistent file is
// acceptable if the lookup control permits.
[
if na eq 1 then lockMode = lockNone
// If the fd designates multiple files and this is the first
// lookup, just advance to the first existing file matching
// the template and return it.
if fd>>FD.lookupStatus eq lsNoLookup & fd>>FD.template ne 0 then
resultis (NextFD(fd, lockMode)? 0, ecFileNotFound)
// If a lookup has already been done on this fd and the directory
// has not been modified in the meantime, just return ok.
unless lockMode eq lockAlready do LockDirFD(fd, lockMode eq lockWrite)
let fs = fd>>FD.fs
let vc = fd>>FD.lc.vc
if fd>>FD.lookupStatus ne lsNoLookup then
[
if fd>>FD.dirVersion eq fs>>IFS.dirVersion then
[
unless lockMode ge lockRead do UnlockDirFD(fd)
resultis 0
]
vc = lcVExplicit // force exact match during revalidation
]
// Single file lookup case.
// First, find the best candidate entry in the directory.
// If the version control is vcHighest, vcNext, or vcExplicit,
// this is the greatest entry less than or equal to the key;
// if vcLowest, this is the key's successor (recall that vcHighest
// and vcNext set version to 65535, and vcLowest sets version to 0)
let record = vc eq lcVLowest? DirSuccessor(fs>>IFS.dirBTree, fd),
ReadRecLE(fs>>IFS.dirBTree, fd, 0, 0, fd>>FD.pathStk, true)
if record ne 0 & (record>>DR.header & drHeaderMask) ne 0 then
IFSError(ecBadDR)
// Discover how good a match this was
let version = nil // the real version of the file that was found
let code = (record eq 0? 0, NamesMatch(fd, record, lv version))
// LookupFD (cont'd)
// Branch on the cross product of match code and version control
let ec = 0 // no error yet
switchon 4*vc+code into
[
case 4*lcVHighest+0: case 4*lcVNext+0:
case 4*lcVLowest+0: case 4*lcVExplicit+0:
[ // no such directory
fd>>FD.lookupStatus = lsNonexistent; ec = ecDirNotFound; endcase
]
case 4*lcVHighest+1: case 4*lcVNext+1: case 4*lcVLowest+1:
[ // no such file exists, create version 1
fd>>FD.version = 1 //fall into next case
]
case 4*lcVExplicit+1:
[ // no version of file exists, explicit version requested
fd>>FD.lookupStatus = lsNonexistent; endcase
]
case 4*lcVHighest+2: case 4*lcVHighest+3:
case 4*lcVLowest+2: case 4*lcVExplicit+3:
[ // body matched and highest or lowest requested, or
// exact match and highest or explicit requested,
// return that version
fd>>FD.version = version
fd>>FD.lookupStatus = lsExists
InstallDR(fd, record)
endcase
]
case 4*lcVNext+2:
[ // body matched and next requested, create version+1
fd>>FD.version = version+1 // fall into next case
]
case 4*lcVExplicit+2:
[ // a previous version exists, explicit version requested
fd>>FD.lookupStatus = lsOtherVersion
InstallDR(fd, record)
endcase
]
case 4*lcVNext+3:
[ // exact match and next was requested, version overflow
ec = ecIllegalVersion; endcase
]
default:
IFSError(ecLookupImpossibleCase)
]
FreePointer(lv record)
unless fd>>FD.lookupStatus eq lsExists do FreePointer(lv fd>>FD.pathStk)
if ec eq 0 then
[
IFSAppendVersion(fd) // in case new version number computed
if fd>>FD.dr>>DR.pathName.length gr maxPathNameChars then
ec = ecNameTooLong
if fd>>FD.lookupStatus ne lsExists then
if (na ge 3 & requireExists) % not fd>>FD.lc.create then
ec = ecFileNotFound
]
// Remember directory version for which this fd is valid
fd>>FD.dirVersion = fs>>IFS.dirVersion
unless lockMode ge lockRead do UnlockDirFD(fd)
resultis ec
]
//----------------------------------------------------------------------------
and NextFD(fd, lockMode; numargs na) = valof
//----------------------------------------------------------------------------
// Advances to the next file described by the FD. If successful,
// updates the DR and the auxiliary lookup information (including
// lookupStatus) and returns true. If unsuccessful, returns false.
// lockMode is treated as in LookupFD.
[
if na eq 1 then lockMode = lockNone
let fs = fd>>FD.fs
let vc = fd>>FD.lc.vc
unless lockMode eq lockAlready do LockDirFD(fd, lockMode eq lockWrite)
// scan directory starting at current file.
let result = valof
[ // repeat
if fd>>FD.template eq 0 resultis false // not multiple-file FD
// If version control is "lowest" or "highest", make sure we skip
// over all remaining versions of the current file.
// If we already have a PathStk then use it, else create a new one.
let useExistingPath = false
test vc eq lcVLowest % vc eq lcVHighest
ifso fd>>FD.version = 177777B // and don't use existing path
ifnot test fd>>FD.pathStk eq 0
ifso fd>>FD.pathStk = SysAllocateZero(lenPathStk)
ifnot useExistingPath = true
// following 3 variables must be contiguous and in this order
let param = fd // fd being passed down to MatchFD
let code = 0 // code passed back up from MatchFD
let count = 0 // count of records processed
MapTree(fs>>IFS.dirBTree, fd, MatchFD, lv param, 0, true,
fd>>FD.pathStk, useExistingPath)
//figure out why MapTree terminated
switchon code into
[
case 0: // ran off end of tree or past last possible entry
FreePointer(lv fd>>FD.template, lv fd>>FD.pathStk)
resultis false
case 1: // someone else waiting to use dir, give him a chance
[
let lockedForWriting = fs>>IFS.dirLock.count ls 0
UnlockDirFD(fd)
LockDirFD(fd, lockedForWriting)
UpdateFD(fd)
endcase
]
case 2: // found matching record
// In the case of all version controls besides "highest", we now
// have the desired record. In the case of "highest", we now have
// the lowest version so we have to do a lookup to find the highest.
if vc eq lcVHighest then
[
UpdateFD(fd)
fd>>FD.version = 177777B
// "true" as 4th arg means don't copy -- InstallDR will do it.
// Must be no opportunity to block or fault beween ReadRecLE
// and InstallDR, because ReadRecLE returns unlocked pointer.
InstallDR(fd,
ReadRecLE(fs>>IFS.dirBTree, fd, 0, true, fd>>FD.pathStk))
]
UpdateFD(fd)
resultis true
]
] repeat
// Update the auxiliary lookup information in the fd
fd>>FD.lookupStatus = result? lsExists, lsNonexistent
fd>>FD.dirVersion = fs>>IFS.dirVersion
unless lockMode ge lockRead do UnlockDirFD(fd)
resultis result
]
//----------------------------------------------------------------------------
and MatchFD(record, lvParam, nil) = valof
//----------------------------------------------------------------------------
// This procedure is called by MapTree with the next record for
// consideration. If this record does not match the fd and there
// is no other reason to terminate, returns true, thereby causing
// MapTree to continue scanning the directory. Otherwise, returns
// false, causing MapTree to terminate, after storing a code
// in the parameter vector denoting the reason for termination:
// 0 ran past the last possible entry in the directory
// (note that NextFD initializes the code to 0, so MatchFD
// doesn't have to set it to this value explicitly, and 0 is
// also returned if MapTree returns without having called
// MatchFD at all).
// 1 someone else is waiting to use the directory, give him
// a chance and then resume scanning. stores the current
// record in the fd to use as the starting key.
// 2 found a matching record, which is now stored in the fd.
[
Yield()
// This check is now redundant because MapTree always calls DirEntryLength
// on each record before passing it to us, and DirEntryLength
// performs the same check.
// if (record>>DR.header & drHeaderMask) ne 0 then IFSError(ecBadDR)
let fd = lvParam!0
let i = MatchKPMTemplate(lv record>>DR.pathName, fd>>FD.template)
if i ne 0 then
[
// Doesn't match. If the failing character preceded the first
// "*" in the template then stop now, else continue scan.
test i ls fd>>FD.iFirstStar & DirCompareKey(fd, record) ls 0
ifso resultis false // no further matches possible
ifnot
[
// Terminate scan anyway if we have hogged the directory
// for too long and someone else is waiting.
lvParam!2 = lvParam!2+1 // count entries processed
if fd>>FD.fs>>IFS.dirLockConflict & lvParam!2 gr 25 then
[
InstallDR(fd, record)
lvParam!1 = 1
resultis false
]
resultis true
]
]
// The new record must be "greater than" the current name
unless DirCompareKey(fd, record) ls 0 resultis true
// Ok, pass back this record and terminate scan
InstallDR(fd, record)
lvParam!1 = 2 // signal success
resultis false // stop scan
]
//----------------------------------------------------------------------------
and InstallDR(fd, record) be
//----------------------------------------------------------------------------
// Installs a copy of record as fd's DR.
// Enough extra space is allocated to permit appending a bigger version.
// InstallDR must be in the same overlay as the caller if the supplied
// record is contained in an unlocked B-Tree page. NextFD (above) makes
// this assumption.
[
LockCell(lv record) // protect across Allocate, which might conceivably block
FreePointer(lv fd>>FD.dr)
fd>>FD.dr = SysAllocate(record>>DR.length+3)
MoveBlock(fd>>FD.dr, record, record>>DR.length+3)
UnlockCell(lv record)
]
//----------------------------------------------------------------------------
and DirSuccessor(tree, fd) = valof
//----------------------------------------------------------------------------
// Looks up the FD "fd" in the specified "tree"
// and returns a copy of the directory record for its successor,
// or 0 if no successor exists.
[
let resultRecord = 0 // must immediately follow fd in frame
MapTree(tree, fd, SuccessorFn, lv fd, 0, false, fd>>FD.pathStk, true)
resultis resultRecord
]
//----------------------------------------------------------------------------
and SuccessorFn(record, lvParam, nil) = valof
//----------------------------------------------------------------------------
// This procedure is called by MapTree with the next record for
// consideration. lvParam!0 points to the original key (fd),
// and lvParam!1 is where to put the result when the desired record
// has been reached. Returns false when the correct record has
// been reached, to cause MapTree to stop, and leaves the record
// in lvParam!1. Ordinarily, SuccessorFn is called twice,
// the first time with the original key and the second time with
// that key's successor. However, if the original key is not
// found and is lower than any key in the directory, the record
// we want will be passed on the first call. Hence we can't just
// count calls.
[
// see comment in MatchFD
// if (record>>DR.header & drHeaderMask) ne 0 then IFSError(ecBadDR)
test DirCompareKey(lvParam!0, record) ls 0
ifso // here is the record we want, save it and terminate
[ lvParam!1 = record; resultis false ]
ifnot // not the desired one, turn the crank again
[ SysFree(record); resultis true ]
]
//----------------------------------------------------------------------------
and LockDirFD(fd, write; numargs na) be
//----------------------------------------------------------------------------
// Locks directory given fd. Sets write lock if "write" is true
// and read lock if false or absent. If a lock conflict occurs,
// sets the dirLockConflict flag so that whoever has the lock will
// notice that we are waiting.
[
let fs = fd>>FD.fs
until Lock(lv fs>>IFS.dirLock, na gr 1 & write, true) do
[ fs>>IFS.dirLockConflict = true; Block() ]
]
//----------------------------------------------------------------------------
and UnlockDirFD(fd) be
//----------------------------------------------------------------------------
// Unlocks directory given fd.
[
let fs = fd>>FD.fs
Unlock(lv fs>>IFS.dirLock)
if fs>>IFS.dirLockConflict then
[ fs>>IFS.dirLockConflict = false; Block() ]
]
//----------------------------------------------------------------------------
and ModifyDirFD(fd) be
//----------------------------------------------------------------------------
// Marks directory designated by fd as having been modified,
// by incrementing its version number.
[
let fs = fd>>FD.fs
if fs>>IFS.dirLock.count ge 0 %
fs>>IFS.dirLock.ctx ne CtxRunning then IFSError(ecDirNotLocked)
fs>>IFS.dirVersion = fs>>IFS.dirVersion+1
NoticeDirectoryChange(fd)
]