// 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) ]