// IfsScav2-3.bcpl - Pass 2 Phase 3 // Copyright Xerox Corporation 1980, 1981, 1982, 1983, 1984 // Last modified August 10, 1984 5:51 PM by Fiala // Last modified February 16, 1984 3:46 PM by Boggs get "IfsScavenger.decl" get "IfsDirs.decl" get "BTree.decl" get "Disks.d" external [ // outgoing procedures Pass2Phase3 // incoming procedures Gets; Puts; Closes; Resets OpenFile; CreateDiskStream; CreateDiskFile FileLength; GetCurrentFa; WriteBlock; ExtendFile Allocate; Free; IFSError; MoveBlock; Zero; ReadCalendar DoubleDifference; DoubleIncrement; MultEq; Usc InitializeContext; Block; Enqueue; Unqueue CreateStringStream; CopyString; StringCompare ReadLPTE; WriteLPTE; GetLptLpte OpenLPT; EnumerateLPT; CloseLPT GetLpteIfsName; GetLpteIfp; GetLpteFa; GetLpteDIFRec SetLpteIfsName; SetLpteIfp; GetLpteFlags; GetLpteType DirEntryLength; CompareRecords; Password MapTree; UpdateRecord; DeleteKey OpenFPTree; CloseIFSTree; FlushBuffers Ws; Wss; PutTemplate; PrintTime // incoming statics keys; dsp; sysZone; ifsCtxQ scavDisk; scratchDisk; tree; phase; lpt initTreeFlag; debugFlag ] static [ treeDR; lptDR; difDR; dupLpt giveMeATreeDR; leftoverLPTE; treeChanged ] manifest [ // error codes ecMalformedLPTE = 508 ecUpdateRecord = 509 ] //----------------------------------------------------------------------------------------- let Pass2Phase3() = valof //----------------------------------------------------------------------------------------- // This phase enumerates the directory and the leader page table in parallel. // The LPT is the truth about what should be in the directory, so any // disagreements are resolved by changing the tree. // The algorithm is: // lptDR > treeDR: delete treeDR, read next treeDR // lptDR = treeDR: read next lptDR, read next treeDR // lptDR < treeDR: insert lptDR, read next lptDR [ phase = 3 Ws("*N[2-3]"); if debugFlag then Gets(keys) if initTreeFlag & not debugFlag then Ws("*N[2-3] Initializing the directory B-Tree; only DIFs will be mentioned") // open the tree and set up its reader process let fpIfsDir = vec lFP; Zero(fpIfsDir, lFP) let ifsDir = OpenFile("Ifs.dir", 0, 0, 0, fpIfsDir, 0, 0, 0, scavDisk) if ifsDir eq 0 then IFSError(ecScavengeeFile, "Ifs.dir") Closes(ifsDir) tree = OpenFPTree(fpIfsDir, scavDisk, CompareRecords, DirEntryLength, false, 3000) let treeMapper = InitializeContext(Allocate(sysZone, 1024), 1024, TreeMapper) Enqueue(ifsCtxQ, treeMapper) giveMeATreeDR, treeChanged = false, false Resets(lpt) dupLpt = 0 leftoverLPTE = false lptDR = Allocate(sysZone, maxDRLength); Zero(lptDR, maxDRLength) difDR = Allocate(sysZone, maxDRLength); Zero(difDR, maxDRLength) treeDR = Allocate(sysZone, maxDRLength); Zero(treeDR, maxDRLength) CopyString(lv treeDR>>DR.pathName, "!1") // Pass2Phase3 (cont'd) let startTime = vec 1; ReadCalendar(startTime) ReadNextLPTDR() ReadNextTreeDR() [ switchon valof [ if treeDR>>DR.type eq 0 & lptDR>>DR.type eq 0 break //all done if lptDR>>DR.type eq 0 resultis -1 //lpt ran out if treeDR>>DR.type eq 0 resultis 1 //tree ran out resultis CompareRecords(treeDR, lptDR) ] into [ case -1: //treeDR < lptDR [ PutTemplate(dsp, "*N[2-3] Deleting tree entry *"$S*"", lv treeDR>>DR.pathName) DeleteKey(tree, treeDR) treeChanged = true ReadNextTreeDR() endcase ] case 0: //treeDR = lptDR [ let update = false test lptDR>>DR.type eq drTypeDIF ifso update = true ifnot [ @lv treeDR>>DR.fp.unit = treeDR>>DR.fp.unit @lv lptDR>>DR.fp.unit = lptDR>>DR.fp.unit unless MultEq(lv treeDR>>DR.fp,lv lptDR>>DR.fp,lFP) do [ PutTemplate(dsp, "*N[2-3] Updating tree entry *"$S*"", lv lptDR>>DR.pathName) update = true ] ] if update then UpdateRecord(tree, lptDR, UpdateRecGen, lptDR) ReadNextTreeDR() ReadNextLPTDR() endcase ] case 1: //treeDR > lptDR [ if not initTreeFlag % lptDR>>DR.type eq drTypeDIF % debugFlag do PutTemplate(dsp, "*N[2-3] Inserting tree entry *"$S*"", lv lptDR>>DR.pathName) UpdateRecord(tree, lptDR, InsertRecGen, lptDR) ReadNextLPTDR() endcase ] ] ] repeat // Pass2Phase3 (cont'd) UpdateRecord(tree, difDR, UpdateRecGen, difDR) //updates last dif PrintTime(startTime) if dupLpt ne 0 then [ EnumerateLPT(dupLpt, AddDuplicates) dupLpt = CloseLPT(dupLpt, true) ] // If the tree is more than 90% full, extend it by 50% if there is room. let greatestPage = tree>>TREE.GreatestPage tree = CloseIFSTree(tree) let st = CreateDiskStream(fpIfsDir, 0, 0, 0, 0, 0, 0, scavDisk) let fa = vec lFA; FileLength(st); GetCurrentFa(st, fa) Closes(st) if (fa>>FA.pageNumber/10)*9 ls greatestPage then ExtendFile("IFS.Dir", (fa>>FA.pageNumber/2)*3, 0) // clean up and go away Unqueue(ifsCtxQ, treeMapper) Free(sysZone, treeMapper) treeDR = Free(sysZone, treeDR) lptDR = Free(sysZone, lptDR) difDR = Free(sysZone, difDR) FlushBuffers() resultis true ] //----------------------------------------------------------------------------------------- and AddDuplicates(lpt, lpte, nil) be //----------------------------------------------------------------------------------------- [ let drName = lv lptDR>>DR.pathName let ss = CreateStringStream(drName, maxPathNameChars) let ifp = GetLpteIfp(lpte) PutTemplate(ss, "Duplicate>VDA$EUO", lv ifp>>IFP.da) let ifsName = GetLpteIfsName(lpte) for i = 1 to ifsName>>String.length do [ if drName>>String.length ge maxPathNameChars break // turn directory punctuation into harmless dashes let char = ifsName>>String.char^i if char eq $> % char eq $< then char = $- Puts(ss, char) ] Closes(ss) PutTemplate(dsp, "*N[2-3] Inserting duplicate file *"$S*"", drName) MoveBlock(lv lptDR>>DR.fp, ifp, lFP) lptDR>>DR.type = drTypeNormal lptDR>>DR.length = lenDRHeader + lptDR>>DR.pathName.length rshift 1 +1 UpdateRecord(tree, lptDR, InsertRecGen, lptDR) ] //----------------------------------------------------------------------------------------- and InsertRecGen(dr, newDR) = valof //----------------------------------------------------------------------------------------- // This record generator is passed to UpdateRecord when inserting a record [ treeChanged = true test dr ne 0 //two files with the same name? ifso [ if dupLpt eq 0 then dupLpt = OpenLPT("IfsScavenger.dupLpt", true) let lpte = GetLptLpte(dupLpt, true) SetLpteIfsName(lpte, lv newDR>>DR.pathName) SetLpteIfp(lpte, lv newDR>>DR.fp) WriteLPTE(dupLpt) ] ifnot [ dr = Allocate(sysZone, newDR>>DR.length) MoveBlock(dr, newDR, newDR>>DR.length) ] resultis dr ] //----------------------------------------------------------------------------------------- and UpdateRecGen(dr, newDR) = valof //----------------------------------------------------------------------------------------- // This record generator is passed to UpdateRecord when updating a record [ treeChanged = true if dr eq 0 then IFSError(ecUpdateRecord) Free(sysZone,dr) dr = Allocate(sysZone, newDR>>DR.length) MoveBlock(dr, newDR, newDR>>DR.length) resultis dr ] //----------------------------------------------------------------------------------------- and TreeMapper() be //a context used as a coroutine //----------------------------------------------------------------------------------------- [ Block() repeatuntil giveMeATreeDR //wait for a request if MapTree(tree, treeDR, MapTreeFunction, 0, 0, true) then [ //ran off the end of the tree treeDR>>DR.type = 0 giveMeATreeDR = false //request satisfied Block() repeatuntil giveMeATreeDR //wait for a request ] repeat ] repeat //----------------------------------------------------------------------------------------- and MapTreeFunction(dr, nil, nil) = valof //----------------------------------------------------------------------------------------- [ if treeChanged then if CompareRecords(dr, treeDR) le 0 resultis true //we want the next one treeChanged = false MoveBlock(treeDR, dr, dr>>DR.length) giveMeATreeDR = false //request satisfied Block() repeatuntil giveMeATreeDR //wait for a request resultis not treeChanged //return true unless our partner modifed tree ] //----------------------------------------------------------------------------------------- and ReadNextTreeDR() be //----------------------------------------------------------------------------------------- // Pokes the B-Tree process for the next record. [ giveMeATreeDR = true //make a request Block() repeatwhile giveMeATreeDR //wait for it to be satisfied ] //----------------------------------------------------------------------------------------- and ReadNextLPTDR() be //----------------------------------------------------------------------------------------- // Manufactures a directory record from the next leader page table entry. [ let lpte = GetLptLpte(lpt) [ unless leftoverLPTE do unless ReadLPTE(lpt) do [ lptDR>>DR.type = 0; return ] //no more LPTEs if GetLpteType(lpte) eq dvTypeFile break ] repeat let dirEnd = 1 let ifsName = GetLpteIfsName(lpte) for i = 1 to ifsName>>String.length do if ifsName>>String.char^i eq $> then [ dirEnd = i; break ] if dirEnd eq 1 then IFSError(ecMalformedLPTE) test StringCompare(ifsName, lv difDR>>DR.pathName, 1, dirEnd) eq -2 ifso //This file is in the same directory as the last file [ CopyString(lv lptDR>>DR.pathName, ifsName) MoveBlock(lv lptDR>>DR.fp, GetLpteIfp(lpte), lFP) lptDR>>DR.type = drTypeNormal lptDR>>DR.length = lenDRHeader + lptDR>>DR.pathName.length rshift 1 +1 DoubleIncrement(lv (DIFRecFromDR(difDR)>>DIFRec.diskPageUsage), GetLpteFa(lpte)>>FA.pageNumber +1) leftoverLPTE = false ] ifnot //New directory [ if difDR>>DR.type eq drTypeDIF then //every time except the first UpdateRecord(tree, difDR, UpdateRecGen, difDR) let difRec = difDR + lenDRHeader let pathName = lv difDR>>DR.pathName Zero(difDR, maxDRLength) test (GetLpteFlags(lpte) & lfDIF) ne 0 ifso //This is the new directory's DIF. [ CopyString(pathName, ifsName) MoveBlock(lv difDR>>DR.fp, GetLpteIfp(lpte), lFP) difRec = difRec + pathName>>String.length rshift 1 +1 MoveBlock(difRec, GetLpteDIFRec(lpte), lenDIFRec) Zero(lv difRec>>DIFRec.diskPageUsage, 2) leftoverLPTE = false ] // ReadNextLPTDR (cont'd) ifnot //New directory's DIF seems to be missing. [ // manufacture the DIF filename let s = CreateStringStream(pathName, maxPathNameChars) for i = 1 to dirEnd do Puts(s, ifsName>>String.char^i) Wss(s, "!1") Closes(s) // create the Directory Information File PutTemplate(dsp, "*N[2-3] Creating *"$S*"", pathName) let pageLength = 1 lshift scavDisk>>DSK.lnPageSize let ld = Allocate(sysZone, pageLength); Zero(ld, pageLength) CopyString(lv ld>>ILD.pathName, pathName) CopyString(lv ld>>ILD.author, "System") ld>>ILD.readProt.owner = true ld>>ILD.type = ftBinary ld>>ILD.byteSize = 8 ld>>ILD.undeletable = true CreateDiskFile(scavDisk, pathName, lv difDR>>DR.fp, 0, 0, 0, ld) Free(sysZone, ld) difDR>>DR.fp.unit = 0 // fill the dif with vanilla things let dif = vec lenDIF; Zero(dif, lenDIF) Password("ifs", lv dif>>DIF.password, true) dif>>DIF.diskPageLimit^1 = 1000 dif>>DIF.createProt.owner = true dif>>DIF.connectProt.owner = true dif>>DIF.readProt.owner = true dif>>DIF.readProt.world = true dif>>DIF.writeProt.owner = true dif>>DIF.appendProt.owner = true let s = CreateDiskStream(lv difDR>>DR.fp, 0, 0, 0, 0, 0, 0, scavDisk) if s eq 0 then IFSError(ecCreateDiskStream, pathName) WriteBlock(s, dif, lenDIF) Closes(s) difRec = difRec + pathName>>String.length rshift 1 +1 MoveBlock(difRec, dif, lenDIFRec) leftoverLPTE = true ] difDR>>DR.type = drTypeDIF difDR>>DR.length = lenDRHeader + lenDIFRec + difDR>>DR.pathName.length rshift 1 +1 difRec>>DIFRec.diskPageUsage^1 = 2 MoveBlock(lptDR, difDR, difDR>>DR.length) ] ] //----------------------------------------------------------------------------------------- and DIFRecFromDR(dr) = valof //----------------------------------------------------------------------------------------- [ // returns pointer to the DIFRec portion of a directory entry if dr>>DR.type ne drTypeDIF then IFSError(ecNotDIFRec) resultis dr + dr>>DR.length - lenDIFRec ]