Sophie: coda-doc-5.2.0-4mdk noarch

coda-doc-5.2.0-4mdk.noarch.rpm

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<HTML>
<HEAD>
 <META NAME="GENERATOR" CONTENT="SGML-Tools 1.0.9">
 <TITLE> The Coda Dir Package: Introduction</TITLE>
 <LINK HREF="codadir-2.html" REL=next>

 <LINK HREF="codadir.html#toc1" REL=contents>
</HEAD>
<BODY>
<A HREF="codadir-2.html">Next</A>
Previous
<A HREF="codadir.html#toc1">Contents</A>
<HR>
<H2><A NAME="s1">1. Introduction</A></H2>

<P>
<P>
<H2><A NAME="ss1.1">1.1 <B>Directory Entries</B></A>
</H2>

<P>
<P>Unix directories are files containing lists of filenames and file
identifiers. In Coda the directory entries consist of a name and a
DirFed, a pair of a vnode number and uniqifier. The volume to which a
directory belongs can be found back through its vnode.
<P>Directories are transported over the net, hence the storage format of
all data is in network order. Therefore two variants of the Dir Fid
structure exist, DirFid's for use on the host,and Dir NFid's which
hold the identifiers innetwork order.
<P>The size of a directory entry is always a multiple of 32 bytes. The
first entry contains the fid, the blob number of the next entry on the
hash chain and a tag indicating it is the first entry. Subsequent
entries contain the remainder of a potentially long name.
<P>
<H2><A NAME="ss1.2">1.2 <B>Directory Format</B></A>
</H2>

<P>
<P>The Coda directory format is inherited from AFS 2 and is somewhat
elaborate. Directories have sizes equal to an integral multiple of the
directory page size (2048 bytes). They are always continguously
allocated (this was changed in 1998). Pages are then subdivided in 64
blobs. Each page in the directory has a PageHeader and a directory has
a DirHeader.
<P>The first blob contains the PageHeader, the next 12 blobs in the first
page contain the directory header and the remaining blobs are for
directory entries. The pageheader contains a bitmap to manage the
allocation of blobs, and a free count to indicate how many blobs are
still free. The DirHeader contains an allocation map (allomap), which
also indicates for each possible page in the direcotry how many blobs
are available. It also contains a hastable. Has values are coputed for
names and indicate the first blob used by entries of that name.
<P>
<H2><A NAME="ss1.3">1.3 Persistent Storage for Directories</A>
</H2>

<P>
<P>Ultimately, clients and servers hold directory data in RVM. 
<P>
<H3>Directories on the client </H3>

<P>
<P>Venus will store directory data as a contiguous blob of memory and
expand such a region when a directory needs to grow. A Venus fso
object contains a field of type VenusData, which is a union of file,
directory and symlink data.  
<P>
<PRE>
union VenusData {
    int havedata;       /* generic test for null pointer (pretty gross, eh) */
    CacheFile *file;    /* VnodeType == File */
    VenusDirData *dir;  /* VnodeType == Directory */
    char *symlink;      /* VnodeType == SymbolicLink */
};
</PRE>
<P>
<P>For a directory Venus has:
<P>
<PRE>
struct VenusDirData {
        struct DirHandle dh; /* contains pointer to Coda format directory */
        unsigned udcfvalid : 1; /*T*/   /* Unix format directory in UFS. */
        CacheFile *udcf;   /*T*/
        int padding;       /*T*/
};
</PRE>
<P>Venus will at appropriate times write a Unix style directory into a
container file, so that the kernel can perform its readdir operations
directly on the container.
<P>
<H3>Server directory storage </H3>

<P>
<P>Server directory vnodes point to directory inodes.  Such inodes
contain the pages of the directories.  Since directories and directory
inodes are copy-on-write objects with respect to cloning volumes,
several vnodes (in different volumes) can point to a single directory
inode.
<P>The <B>VnodeDiskObjectStruct</B> in RVM contains a pointer <B>Inode</B> to
a directory inode structure:
<P>
<PRE>
struct DirInode {
        void *di_pages[DIR_MAXPAGES];
        int  di_refcount;             /* for copy on write */
};
</PRE>
<P>The server stores the directory in pages in RVM, but never does
directory operations on the RVM pages.  A directory inode contains the
page map <CODE>di_pages</CODE> for the directory. The array contains pointers
to RVM storage for the individual pages of the directory.  When
concatenated into a single buffer they are the objects Venus fetches
from the server.
<P>The server makes a copy of the directory data in VM, operates on that
copy and copies the entire directory back to RVM when finished. 
<P>Since directory contents on the server are copy on write, a directory
handle is needed to count the references to the directory while it is
in use.  These handles are held in a hash table in the server.
<P>
<P>These arrange for RVM storage of directories.  
<P>While the server is running vnodes are hashed in VM and the <B>Vnode</B>
structure contains a pointer <B>dh</B> to a directory handle.  The
directory handles themselves sit in a hashtable:
<P>
<PRE>
struct dllist_head dcache[DCSIZE];
struct dllist_head dfreelist; 

struct DCHashEntry {
        struct dllist_head    dc_listhead;
        int                   dc_count;  /*how many vnodes are referencing us */
        struct DirHandle      dc_dh;
        PDirInode             dc_pdi;
};
</PRE>
 
<P>
<P>
<H2><A NAME="ss1.4">1.4 <B>C Structures Describing the Directory Format</B></A>
</H2>

<P>
<P>The following structures describe the directory format:
<P>
<PRE>
struct PageHeader {
    log tag;
    char freecount;   /* duplicated info: also in allomap */
    char freebitmap [EPP/81];
    char padding[PH_PADSIZE];
};

struct DirHeader {
    struct PageHeader dirh_ph;
    char dirth_allomap[MAXPAGES];  /* one byte per 2K page */  
    short dirh_hashTable[NHASH];
};

/* A file identifier in host order */
struct DirFid {
    long dnf_vnode;   /* file vnode */
    long dnf_unique;  /* file uniguifier */
};

/* File identifier in network order */
struct DirNFid {
    long dng_vnode; /* file vnode */
    long dnf_unique;  /* file uniguifier */
};

struct DirEntry {
    char flag;
    char length;  /* currently unused */
    short next;
    struct DirNFid fid;
    char name[16];
};

struct DirXEntry {
    char name[32];
};
</PRE>
<P>
<P>
<P>
<H2><A NAME="ss1.5">1.5 <B>Example of the Directory Layout:</B></A>
</H2>

<P>
<P>The dirtest program shows a simple directorylayout below:
<P>
<PRE>
DIR: 0x501121c, LENGTH: 2048

HASH TABLE:
(1 19) (46 13) (68 14) (104 20)

ALLOMAP:
(0 41)

PAGEHEADERS;
page 0, tag 1234, freecount 41, st 23, bitmap:
1111111101111111111111100000000100000000000000000000000000000000

CHAINS:
Chain: 1
thisblob: 19 next: 18, flag 1 fid: (8.8) 27
thisblob: 18 next: 17, flag 1 fid: (8.8) 50
thisblob: 17 next: 0, flag 1 fid: (8.8) 225
Chain: 46
thisblob: 13 next: 0, flag 1 fid: (9.9) .
Chain: 68
thisblob: 14 next: 0, flag 1 fid: (9.9) ..
Chain: 104
thisblob: 20 next: 0, flag 1 fid: (4.5) this is a veryveryveryverylongname
</PRE>
<P>Careful investigation will show that more than a single blob is ocupied by the very long entry.
<P>
<P>
<P>
<HR>
<A HREF="codadir-2.html">Next</A>
Previous
<A HREF="codadir.html#toc1">Contents</A>
</BODY>
</HTML>