\begindata{text, 268559100}
\textdsversion{11}
\define{italic
menu:[Font,Italic]
attr:[FontFace Italic Int Set]}
\define{bold
menu:[Font,Bold]
attr:[FontFace Bold Int Set]}
\define{chapter
menu:[Title,Chapter]
attr:[Justification Centered Point 0]
attr:[FontSize PreviousFontSize Point 4]}
\define{section
menu:[Title,Section]
attr:[Justification Centered Point 0]
attr:[FontSize PreviousFontSize Point 4]}
\define{subsection
menu:[Title,Subsection]
attr:[Justification LeftJustified Point 0]
attr:[FontSize PreviousFontSize Point 4]}
\define{paragraph
menu:[Title,Paragraph]
attr:[Justification LeftJustified Point 0]
attr:[FontSize PreviousFontSize Point 4]}
\define{bigger
menu:[Font,Bigger]
attr:[FontSize PreviousFontSize Point 2]}
\define{indent
menu:[Region,Indent]
attr:[LeftMargin LeftMargin Inch 32768]
attr:[RightMargin RightMargin Inch 32768]}
\define{typewriter
menu:[Font,Typewriter]
attr:[FontFace FixedFace Int Set]
attr:[FontFamily AndyType Int 0]}
\define{display
menu:[Region,Display]
attr:[LeftMargin LeftMargin Inch 32768]
attr:[RightMargin RightMargin Inch 32768]
attr:[Justification LeftJustified Point 0]}
\define{example
menu:[Region,Example]
attr:[LeftMargin LeftMargin Inch 32768]
attr:[Justification LeftJustified Point 0]
attr:[FontFace FixedFace Int Set]
attr:[FontFamily AndyType Int 0]}
\define{description
menu:[Region,Description]
attr:[LeftMargin LeftMargin Inch 32768]
attr:[Indent LeftEdge Inch -32768]}
\define{quotation
menu:[Region,Quotation]
attr:[LeftMargin LeftMargin Inch 32768]
attr:[RightMargin RightMargin Inch 32768]
attr:[FontFace Italic Int Set]}
\define{subscript
menu:[Font,Subscript]
attr:[Script PreviousScriptMovement Point 131072]
attr:[FontSize PreviousFontSize Point -2]}
\define{superscript
menu:[Font,Superscript]
attr:[Script PreviousScriptMovement Point -393216]
attr:[FontSize PreviousFontSize Point -2]}
\define{smaller
menu:[Font,Smaller]
attr:[FontSize PreviousFontSize Point -2]}
\define{heading
menu:[Title,Heading]
attr:[LeftMargin LeftMargin Inch -13107]
attr:[Justification LeftJustified Point 0]
attr:[FontFace Bold Int Set]}
\define{majorheading
menu:[Title,MajorHeading]
attr:[Justification Centered Point 0]
attr:[FontSize PreviousFontSize Point 4]}
\define{formatnote
menu:[Region,FormatNote]
attr:[Flags PassThru Int Set]}
\define{subheading
menu:[Title,Subheading]
attr:[Justification LeftJustified Point 0]
attr:[FontFace Bold Int Set]}
\define{center
menu:[Justify,Center]
attr:[Justification Centered Point 0]}
\define{flushleft
menu:[Justify,FlushLeft]
attr:[Justification LeftJustified Point 0]}
\define{flushright
menu:[Justify,FlushRight]
attr:[Justification RightJustified Point 0]}
\define{leftindent
menu:[Region,LeftIndent]
attr:[LeftMargin LeftMargin Inch 32768]}
\define{article
menu:[Title,Article]
attr:[Justification Centered Point 0]
attr:[FontSize ConstantFontSize Point 24]}
\define{subpara
menu:[Title,Subpara]
attr:[Justification LeftJustified Point 0]
attr:[FontFace Bold Int Set]}
\define{subsubpara
menu:[Title,Subsubpara]
attr:[Justification LeftJustified Point 0]
attr:[FontFace Italic Int Set]}

\subsection{Directory package}


\paragraph{Overview}

The directory package implements an efficient mapping from file names into 8 byte partial file identifiers for the Andrew File System.  The Andrew File System uses these 8 bytes of data to store the Vnode and Unique fields of the corresponding file's file identifier.  The Volume field is not stored since, in the Andrew File System, it is the same as the volume of the directory itself.  Directories have a maximum size, 128 2K byte pages, where each page can contain approximately 64 file entries.

The directory system is organized into three major components: an underlying physio package that interfaces to the disk storage system actually holding the directories; a package that handles retrievals and modifications to individual directories, called by users; and a buffer package that connects the physio package with the directory package.  The directory package also provides a salvager that checks directories for internal consistency and rebuilds them when errors are detected.


\paragraph{Description}

The directory package contains four code modules.  At the top are the \bold{directory module}, presenting a directory abstraction, and the \bold{salvager module}, which repairs damaged directories.  The directory and salvager modules are implemented on top of the \bold{buffer module}, which provides the abstraction of a set of buffers and a manager.  Finally, the buffer module accesses the disk storage holding the directories via the \bold{physio module}.  The directory, salvager and buffer modules are provided by the directory package, along with an interface specification for the physio module.  The user of the directory package is responsible for providing a physio module.

The directory package contains 3 interfaces of interest.  These are the interface between the client programmer and the directory module, essentially the client programmer's interface; the interface between the directory module and the buffer module (primarily an internal interface); and the interface between the buffer module and the physio module.


\paragraph{Interface specification}

The buffer module provides the caching essential to the high performance of the directory package.  The following routines are provided:

\bold{DInit}(nbuffers)
long nbuffers;

This call must be performed before any other calls to the directory package are made.  This procedure initializes the directory package with \italic{nbuffers} directory buffers (of 2K bytes each).  At least three pages per active light-weight process must be provided in order to guarantee freedom from deadlock.

char *\bold{DRead}(fid, page)
long *fid;
long page;

This is an internal routine only used by the directory package.  This routine reads from the file described by \italic{fid} the page specified by \italic{page}.  The manner in which fid specifies the directory to use is described in the previous section.  The page number specifies which 2K byte page to read; the first page is numbered 0.  A pointer is returned to the first byte in the requested page.  A null pointer is returned if an error occurred while performing the read.  \italic{DRead} read-locks the page until \italic{DRelease} is called to unlock the page from the buffer pool.  This prevents the page frame from being re-used by the LRU algorithm while the directory package is still reading a directory's data.  Each new call to \italic{DRead} increments a count of readers for this page and thus requires a call to \italic{DRelease} when the caller finishes with the data.

\bold{DRelease}(buffer, rwflag)
char *buffer;
long flag;

This is an internal routine only used by the directory package.  This routine unlocks the buffer into which buffer points.  \italic{Buffer} may point at any byte within the buffer; it need not point at the first byte of the buffer.  If \italic{rwflag} is 1, the buffer package assumes that the data in the buffer has changed and will mark the buffer as modified.  The buffer package will not re-use a modified buffer without writing it out to the disk first.  If \italic{rwflag} is 0, no such assumption is made about the buffer.

\bold{DVOffset}(ptr)
char *ptr

This is an internal routine only used by the directory package.  It takes a pointer to a character in a disk buffer and returns the offset in the corresponding disk file of this same byte.  It returns -1 if an error occurs during the translation process.

\bold{DZap}(fid)
long *fid;

This is an exported routine.  It tells the buffer module to discard all blocks associated with the fid \italic{fid}.  The blocks are not written out, even if they were modified (according to \italic{DRelease}).

\bold{DFlushEntry}(fid)
long *fid;

This is an exported routine.  It directs the buffer module to write out to disk all of the modified buffers associated with the file named by \italic{fid}.

\bold{DFlush}()

This is an exported routine.  It directs the buffer module to write out all modified disk buffers.

\bold{DNew}(fid, page)
long *fid
long page;

This is an internal routine called only by the directory module.  It works exactly like \italic{DRead}, only no data is read at all, under the assumption that the particular page of the dir does not exist.  It is used to add pages to a directory.

The next set of routines make up the physio module.  This module is provided by the user of the buffer package, not by the buffer package itself.  As part of providing the physio module, the programmer must provide routines dealing with file identifiers (\bold{fids}), with each fid stored in a long[5] array.  The programmer provides assignment, comparison and invalidation routines that are called by the buffer package.  The programmer also provides routines that, given a fid, read or write pages of the corresponding file.  Your representation for a fid must fit within 5 long words.

For example, the file identifiers that the Andrew Cache Manager uses for represnting files within its cache are simply the files' inode numbers within the cache partition.  These fids require only one long word to hold, and the remaining 4 words reserved by the buffer module are unused.  Equality testing and copying simply test or copy the first word of the 5 word array.  Reading and writing are provided via a new system call added that allows files to be opened by inode number.

In the following, parameters referring to files by fid contain \italic{fid} as part of their name and are declared as \italic{long *}.  These file identifiers are unrelated to \italic{ViceFids}, the unique 96 bit name for a file in the Andrew File System.

\bold{FidEq}(afid, bfid)
long *afid;
long *bfid;

This routine must be supplied by the user.  It should return true if the two fids are equal, and false otherwise.

\bold{FidCpy}(dfid, sfid)
long *dfid;
long *sfid;

This routine must be supplied by the user.  It should copy the source fid \italic{sfid} to the destination fid \italic{dfid}.

\bold{FidZap}(dfid)
long *dfid;

This routine must be supplied by the user.  It should set the fid \italic{dfid} to a value that never occurs in normal files.

\bold{Die}(msg)
char *msg;

This routine must be supplied by the user.  It is called on a fatal error and should display the message \italic{msg}.  It should exit when finished.

\bold{ReallyRead}(fid, block, data)
long *fid;
long block;
char *data;

This routine must be supplied by the user.  It is called by the buffer package to read a block of data from the file named by \italic{fid}.  In particular, it should read 2048 bytes from the file named by \italic{fid} into the buffer pointed to by \italic{data}.  It should simply return if insufficient data is available to perform the entire read.  The data read should be the block named by \italic{block} (in 2048 byte blocks, starting with block 0 as the name for the first block in the file).

\bold{ReallyWrite}(fid, block, data)
long *fid;
long block;
char *data;

This routine must be supplied by the user.  It is called by the buffer package to write a block of data to the file named by fid.  In particular, it should write 2048 bytes to the file named by fid, obtaining the data from the pointer named \italic{data}.  The data written should be the block named by \italic{block} (in 2048 byte blocks, starting with block 0 as the name for the first block in the file).

The next set of routines make up the directory module.

\bold{Create}(fid, name, vfid)
long *fid;
char *name;
ViceFid *vfid;

This routine creates an entry in the directory named by \italic{fid}.  The name of the new entry is \italic{name}, and the associated ViceFid's Vnode and Unique fields are copied from vfid->Vnode and vfid->Unique.  It returns 0 if successful or a Unix error code (from error.h) if an error occurred.  \bold{Note that fid and vfid are completely different types: fid is of the type implicitly defined by the physio module, while vfid is of type ViceFid (a structure of three long integers: a Volume, a Vnode and a Unique field)}.

\bold{Length}(fid)
long *fid;

This routine returns the length, in bytes, that the specified directory requires.  It returns 0, which is never a correct value, if an error occurs during the computation.

\bold{Delete}(fid, name)

This routine deletes the file named \italic{name} from the specified directory.  It retuns 0 if successful; otherwise it returns a Unix error code from the file error.h.

\bold{MakeDir}(fid, myViceFid, parentViceFid)
long *fid;
ViceFid *myViceFid;
ViceFid *parentViceFid;

This routine formats a new directory.  It creates a hash table, allocation map, and other internal structures.  It also creates "." and ".." entries for itself and its parent directory.  In order to do this, it must have the ViceFids corresponding to these entries in the Andrew File System.  \bold{Note that fid is of the type defined by the physio module, while myViceFid and parentViceFid are ViceFids.}

\bold{Lookup}(fid, entry, viceFid)
long *fid;
char *entry;
ViceFid *viceFid;

This routine looks up the entry named by \italic{entry} in the directory specified by \italic{fid}.  It returns, in viceFid.Vnode and viceFid.Unique, the 8 bytes of location information associated with names by the directory package.  The function returns 0 if it succeeds and ENOENT (see error.h) if it can not find the name in the directory.

\bold{EnumerateDir}(dir, hookproc, hook)
long *dirFid;
long hook;
int (*hookproc)();

This routine is used for enumerating a directory's contents.  \italic{DirFid} specifies the directory whose contents are to be enumerated.  \italic{Hookproc} is the address of a procedure to be called once for every entry in the directory.  \italic{Hook} is a parameter passed through to the hookproc procedure.

The hook procedure is called with four parameters.  The first is the \italic{hook} parameter to EnumerateDir.  The second is a \italic{char *} parameter giving the name of the current entry.  The next two parameters are the \italic{Vnode} and \italic{Unique} fields from the directory; both are \italic{long} and both are in host by order (these items are stored in network byte order in the directory and are translated for the programmer).

\bold{IsEmpty}(dir)
long *dirFid;

\bold{Warning: this routine is very poorly named.}  It returns 0 (false) if the directory is empty and 1 (true) if the directory is not empty.  The directory is specified by the \italic{dir} parameter.

The next two routines make up the salvager module.  They are used to check and repair directories in the file system.

\bold{DirOK}(dirFid)
long *dirFid;

This routine makes up a significant part of the salvager module.  It takes one parameter, a directory to check for consistency.  It does the check, writing occasional diagnostics to \italic{stdout}.  It also returns 0 if the directory is bad and 1 if the directory passes all of its checks.

\bold{DirSalvage}(fromDirFid, toDirFid)
long *fromDirFid;
long *toDirFid;

This routine is used to repair damaged directories.  It takes two file parameters: \italic{fromDirFid}, the damaged directory, and \italic{toDirFid}, a newly-created empty file.  DirSalvage leaves \italic{fromDirFid} unchanged and writes new data to \italic{toDirFid}, making it into a copy of \italic{fromDirFid} with all the damage repaired.  DirSalvage writes diagnostic output to \italic{stdout}.  Note that \italic{DirSalvage} may discard directory entries that it cannot decipher.


\paragraph{Module hierarchy}

The module hierarchy for the directory package is quite simple.  Both the directory and salvager modules are built atop of the buffer module, which in turn is built atop of the physio module.

The physio module provides the definition of the basic file type, declared as a \italic{long *} throughout the buffer and directory modules.  The buffer module manages a pool of 2048 byte buffers containing 2048 byte pages from these files.  The directory module provides routines for manipulating the contents of directories.  The salvager module provides routines for checking directories and repairing damaged directories.
\formatnote{.bp}
\enddata{text,268559100}