// IfsNameInstall.bcpl - Name lookup server -- directory installation
// Copyright Xerox Corporation 1979, 1980, 1981
// Last modified December 5, 1981 2:47 PM by Taft
get Port, lenPort from "Pup0.decl"
get "Ifs.decl"
get "IfsFiles.decl"
get "IfsNameServ.decl"
get "IFSDirs.decl"
get wordItem from "Streams.d"
get jobTypeNameUpdate from "IfsRs.decl"
get "BTree.decl"
external
[
// outgoing procedures
InstallNetworkDirectory
// incoming procedures
NetDirEntryLength; NameCompareKey; AddressCompareKey
HeapSort; CheckNetDirChecksum
IFSOpenFile; LookupIFSFile; IFSDeleteFile; IFSDeleteOldVersions; DestroyFD
GetBufferForFD; StreamsFD; EmptiestFreePages; PositionPage
ReadBlock; Gets; SetFilePos; Closes; ReadLeaderPage; WriteLeaderPage
OpenIFSTree; CloseBTree; UpdateRecord; ReadBTreePage; WriteBTreePage
Lock; Unlock; Min; IFSError; Yield; Dismiss; JobOK; PurgeVMem
SysErr; SysAllocate; SysFree; MoveBlock; Usc
// incoming statics
@ns; primaryIFS; haltFlag; numOvXMPages
]
manifest
[
lenNameTable = 50 // number of names processed per pass
]
structure NB: // Name buffer (pointed to from nameTable)
[
pointer word // File pointer to entry or address block
namePointer word // File pointer to name block
// 0 => not primary name for entry
string @String
]
structure NameTS: // Extension to TS (Tree State) structure
[
blank word lTS
blank word 128-lTS
version word // Net dir version of this tree
]
//----------------------------------------------------------------------------
let InstallNetworkDirectory() = valof
//----------------------------------------------------------------------------
// Rebuilds the network directory B-tree from the highest version of
// the file <System>Pup-network.directory. Returns true iff successful.
// Does not rebuild the tree if the one that is there is the correct
// version already.
// Converting the standard Pup network directory structure, with its rat's
// nest of pointers, into a collection of self-contained B-tree entries
// is hairy if you don't have enough buffer space to hold the entire
// network directory, which we don't. Doing it in the obvious way, using
// disk streams, would require on the order of 2*n random positioning
// operations, where n is the number of names in the directory. (The factor
// of 2 comes from the fact that you have to indirect through the entry block
// to reach the address block). Also, the cost of each positioning operation
// itself would be related to n, since the length of the file is dependent
// on n, so the process would in fact be order n squared.
// A virtually-accessed file would make things linear in n, but that wouldn't
// be much better since the references don't have any locality.
// Instead what we do is to use a process that approaches being n squared,
// but with a much smaller multiplier on n (and, in particular, with
// linear dependence on n for number of disk transfers, with small fractional
// multiplier). We process the network directory
// by making multiple passes over the file and building part of the
// B-tree on each pass, using an auxiliary table and a limited amount
// of allocated storage.
// 1. Read through the name block portion of the directory. For each name,
// allocate a block in core with room for the name plus two overhead words,
// and add a pointer to this block in the table. In the extra words,
// put the entry block file pointer gotten from the name block, and also the
// file pointer to this name block (needed in step 3).
// Continue until you run out of storage or table space.
// 2. Sort the table by entry block file pointer value.
// 3. Read all the entry blocks in the order in which the corresponding
// name blocks now appear in the table (i.e., sequentially through the file)
// and replace the entry block pointers by address block pointers gotten
// from the entry blocks. (Also remember whether or not the name block
// was the head of the entry's name block chain, i.e., the primary name.)
// 4. Sort the table by address block file pointer value.
// 5. Read all the address blocks in the order in which the corresponding
// name blocks now appear in the table (i.e., sequentially through the file),
// and create and insert a name entry and an address entry into the B-tree
// for each one. (Complication: some entries point to a chain consisting of
// more than one address. Since there are relatively few of these, however,
// it doesn't cost much to simply follow the pointers on the fly. Second
// complication: we must only insert address entries for primary names.)
// 6. Go back to step 1 if there are more names to do.
[
// If not already open, open existing tree if there is one.
let treeName = "Pup-Network.tree"
let treeFP = vec lFP
let fd = LookupIFSFile(treeName, lcVHighest)
if fd ne 0 then
[
MoveBlock(treeFP, lv fd>>FD.dr>>DR.fp, lFP)
if ns>>NS.tree eq 0 then
[
Lock(lv ns>>NS.treeLock, true) // write lock
ns>>NS.tree = OpenIFSTree(treeFP, primaryIFS, SysErr,
NetDirEntryLength, false, nameTreePages)
ns>>NS.version = ReadBTreePage(ns>>NS.tree, 0)>>NameTS.version
if ns>>NS.version eq 0 then ns>>NS.tree = CloseBTree(ns>>NS.tree)
Unlock(lv ns>>NS.treeLock)
]
DestroyFD(fd)
]
// Open network directory file and process header
let stream = IFSOpenFile("Pup-Network.directory", 0, modeRead, wordItem)
if stream eq 0 resultis false
let hdr = vec lenHdr
ReadBlock(stream, hdr, lenHdr)
// Check the file's checksum before installing it.
unless CheckNetDirChecksum(stream) do
[ Closes(stream); resultis false ]
// See if tree is same version as directory file
if ns>>NS.version eq hdr>>Hdr.version then
[ Closes(stream); resultis true ]
// Versions do not match; prepare to rebuild tree.
// If this is a non-XM IFS or the file system is too full, close the
// existing tree and rebuild it in place; otherwise create a new tree file,
// build the tree in that file, switch the pointers, and destroy the old tree.
// The latter strategy permits the name server to continue to operate using
// the old tree while the new tree is being built.
test ns>>NS.tree ne 0 &
(numOvXMPages eq 0 % EmptiestFreePages(primaryIFS) uls nameTreePages+100)
ifso
[ // prepare to rebuild tree in place
Lock(lv ns>>NS.treeLock, true)
WriteBTreePage(ns>>NS.tree, 0)>>NameTS.version = 0 // invalidate version
ns>>NS.tree = CloseBTree(ns>>NS.tree)
Unlock(lv ns>>NS.treeLock)
]
ifnot unless fd ne 0 & ns>>NS.tree eq 0 do
[ // make new tree file (unless tree file exists but is not open)
let treeStream = IFSOpenFile(treeName, 0, modeWrite)
if treeStream eq 0 then IFSError(ecCreateEssentialFile)
let ld = GetBufferForFD(StreamsFD(treeStream))
ReadLeaderPage(treeStream, ld)
ld>>ILD.type = ftBinary
ld>>ILD.byteSize = 8
ld>>ILD.noBackup = true
ld>>ILD.undeletable = true
WriteLeaderPage(treeStream, ld)
SysFree(ld)
PositionPage(treeStream, nameTreePages)
MoveBlock(treeFP, lv StreamsFD(treeStream)>>FD.dr>>DR.fp, lFP)
Closes(treeStream)
]
let newTree = OpenIFSTree(treeFP, primaryIFS, SysErr,
NetDirEntryLength, true, nameTreePages)
// InstallNetworkDirectory (cont'd)
let nameTable = SysAllocate(lenNameTable)
let curNameIndex = 0
while curNameIndex ls hdr>>Hdr.numNames do
[
if haltFlag break // stop if system is shutting down
// Don't proceed if the system is too busy, else we risk getting
// into deadlocks
unless JobOK(jobTypeNameUpdate) do [ Dismiss(100); loop ]
// First, fill name table with file pointers of next batch of names
let numNamesInTable = Min(lenNameTable, hdr>>Hdr.numNames-curNameIndex)
SetDirPos(stream, hdr>>Hdr.firstName+curNameIndex)
ReadBlock(stream, nameTable, numNamesInTable)
// Read the names and build name table
for i = 0 to numNamesInTable-1 do
[
SetDirPos(stream, nameTable!i + offset Name.entry/16)
let entry = Gets(stream) // file pointer to entry
let string0 = Gets(stream) // first word of name string
let lenString = (string0<<String.length rshift 1)+1
let nb = SysAllocate(offset NB.string/16 + lenString)
nb>>NB.pointer = entry
nb>>NB.namePointer = nameTable!i
let string = lv nb>>NB.string
string!0 = string0
for j = 1 to lenString-1 do string!j = Gets(stream)
nameTable!i = nb
]
// Sort table by entry block file pointer value
HeapSort(nameTable, numNamesInTable, PointerCompare)
// Read pointers to address blocks from the entry blocks
for i = 0 to numNamesInTable-1 do
[
let nb = nameTable!i
SetDirPos(stream, nb>>NB.pointer)
// Remember whether the entry points back to the name we came from
if Gets(stream) ne nb>>NB.namePointer then nb>>NB.namePointer = 0
nb>>NB.pointer = Gets(stream) // file pointer to address block
]
// Sort table by address block file pointer value
HeapSort(nameTable, numNamesInTable, PointerCompare)
// InstallNetworkDirectory (cont'd)
// Now read address blocks and do B-tree insertions
for i = 0 to numNamesInTable-1 do
[
// Chase down address block chain (usually only one block)
// and build up array of ports
let portVec = vec maxNPorts*lenPort
let lenPorts = 0
let nb = nameTable!i
let pAddr = nb>>NB.pointer
[ // repeat
SetDirPos(stream, pAddr)
pAddr = Gets(stream)
Gets(stream)
for j = 0 to lenPort-1 do (portVec+lenPorts)!j = Gets(stream)
lenPorts = lenPorts+lenPort
] repeatwhile pAddr ne 0 & lenPorts ls maxNPorts*lenPort
// Wait here if the system is too busy...
until JobOK(jobTypeNameUpdate) % haltFlag do Dismiss(100)
// Insert NDTE for name
let lenString = (nb>>NB.string.length rshift 1)+1
let lenNDTE = offset NDTE.name.string/16+lenString+lenPorts
let ndte = SysAllocate(lenNDTE)
ndte>>NDTE.type = ndteTypeName
ndte>>NDTE.length = lenNDTE
let string = lv ndte>>NDTE.name.string
MoveBlock(string, lv nb>>NB.string, lenString)
MoveBlock(string+lenString, portVec, lenPorts)
UpdateRecord(newTree, string, RecordGenerator, ndte, NameCompareKey)
// If name is primary, insert NDTE for each address
if nb>>NB.namePointer ne 0 then
[
let iPort = 0
lenNDTE = offset NDTE.address.string/16 + lenString
[ // repeat
ndte = SysAllocate(lenNDTE)
ndte>>NDTE.type = ndteTypeAddress
ndte>>NDTE.length = lenNDTE
MoveBlock(lv ndte>>NDTE.address.string, lv nb>>NB.string, lenString)
MoveBlock(lv ndte>>NDTE.address.port, portVec+iPort, lenPort)
UpdateRecord(newTree, portVec+iPort, RecordGenerator, ndte,
AddressCompareKey)
iPort = iPort+lenPort
] repeatwhile iPort ls lenPorts
]
SysFree(nb)
]
curNameIndex = curNameIndex+numNamesInTable
]
// InstallNetworkDirectory (cont'd)
// Done building the tree
SysFree(nameTable)
Closes(stream)
if haltFlag then
[ // Stopped before new tree was completely built.
CloseBTree(newTree)
IFSDeleteFile(treeName, 0, lcVHighest, 0, true)
resultis false
]
// Force the tree out to the disk, then put the version number into the
// tree state, and finally make this tree known to the name server.
PurgeVMem(newTree>>TREE.vmd)
WriteBTreePage(newTree, 0)>>NameTS.version = hdr>>Hdr.version
Lock(lv ns>>NS.treeLock, true)
if ns>>NS.tree ne 0 then CloseBTree(ns>>NS.tree)
ns>>NS.tree = newTree
ns>>NS.version = hdr>>Hdr.version
Unlock(lv ns>>NS.treeLock)
IFSDeleteOldVersions(treeName, 0, 0, 0, true) // deleteUndeletable
resultis true
]
//----------------------------------------------------------------------------
and SetDirPos(stream, wordPointer) be
//----------------------------------------------------------------------------
[
Yield()
SetFilePos(stream, wordPointer rshift 15, wordPointer lshift 1)
]
//----------------------------------------------------------------------------
and PointerCompare(nb1, nb2) = Usc(nb1>>NB.pointer, nb2>>NB.pointer)
//----------------------------------------------------------------------------
//----------------------------------------------------------------------------
and RecordGenerator(oldRecord, newRecord) = valof
//----------------------------------------------------------------------------
[
if oldRecord ne 0 then IFSError(ecNameDuplicateRecord)
resultis newRecord
]