RISCI_ATOM
/
harvey
mirror of https://github.com/Harvey-OS/harvey.git


			
				
					
						
						
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837
							<html>
<title>
data
</title>
<body BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#330088" ALINK="#FF0044">
<H1>The Plan 9 File Server
</H1>
<DL><DD><I>Ken Thompson<br>
ken@plan9.bell-labs.com<br>
</I></DL>
<DL><DD><H4>ABSTRACT</H4>
This paper describes the structure
and the operation of Plan 9 file servers.
The specifics apply to
our main Plan 9 file server
Emelie,
but
the code is also the basis for
the user level file server
<TT>kfs</TT>.
</DL>
<H4>Introduction
</H4>
<P>
The Plan 9 file server
Emelie
is the oldest piece of system software
still in use on Plan 9.
It evolved from a user-level program that served
serial lines on a Sequent multi-processor.
The current implementation is neither clean nor
portable,
but it has slowly come to terms with
its particular set of cranky computers
and devices.
</P>
<H4>Process Structure
</H4>
<P>
The Plan 9 file system server is made from
an ancient version of the Plan 9 kernel.
The kernel contains process control,
synchronization,
locks,
and some memory
allocation.
The kernel has no user processes or
virtual memory.
</P>
<P>
The structure of the file system server
is a set of kernel processes
synchronizing mostly through message passing.
In Emelie there are 26 processes of 10 types:
<DL><DT><DD><TT><PRE>
number name  function
  15       <TT>srv</TT>   Main file system server processes
   1       <TT>rah</TT>   Block read-ahead processes
  h'w'0'u'1       <TT>scp</TT>   Sync process
  h'w'0'u'1       <TT>wcp</TT>   WORM copy process
  h'w'0'u'1       <TT>con</TT>   Console process
  h'w'0'u'1       <TT>ilo</TT>   IL protocol process
  h'w'0'u'1       <TT>ilt</TT>   IL timer process
  h'w'0'u'2       <TT>ethi</TT>   Ethernet input process
  h'w'0'u'2       <TT>etho</TT>   Ethernet output process
  h'w'0'u'1       <TT>flo</TT>   Floppy disk process
</PRE></TT></DL>
</P>
<H4>The server processes
</H4>
<P>
The main file system algorithm is a set
of identical processes
named
<TT>srv</TT>
that honor the
9P protocol.
Each file system process waits on
a message queue for an incoming request.
The request contains a 9P message and
the address of a reply queue.
A
<TT>srv</TT>
process parses the message,
performs pseudo-disk I/O
to the corresponding file system block device,
formulates a response,
and sends the
response back to the reply queue.
</P>
<P>
The unit of storage is a
block of data on a device:
<DL><DT><DD><TT><PRE>
    enum
    {
        RBUFSIZE = 16*1024
    };

    typedef
    struct
    {
        short   pad;
        short	tag;
        long	path;
    } Tag;

    enum
    {
        BUFSIZE = RBUFSIZE - sizeof(Tag)
    };

    typedef
    struct
    {
        uchar   data[BUFSIZE];
        Tag     tag;
    } Block;
</PRE></TT></DL>
All devices are idealized as a perfect disk
of contiguously numbered blocks each of size
<TT>RBUFSIZE</TT>.
Each block has a tag that identifies what type
of block it is and a unique id of the file or directory
where this block resides.
The remaining data in the block depends on
what type of block it is.
</P>
<P>
The
<TT>srv</TT>
process's main data structure is the directory entry.
This is the equivalent of a UNIX i-node and
defines the set of block addresses that comprise a file or directory.
Unlike the i-node,
the directory entry also has the name of the
file or directory in it:
<DL><DT><DD><TT><PRE>
    enum
    {
        NAMELEN = 28,
        NDBLOCK = 6
    };
</PRE></TT></DL>
<DL><DT><DD><TT><PRE>
    typedef
    struct
    {
        char    name[NAMELEN];
        short   uid;
        short   gid;
        ushort  mode;
        short   wuid;
        Qid     qid;
        long    size;
        long    dblock[NDBLOCK];
        long    iblock;
        long    diblock;
        long    atime;
        long    mtime;
    } Dentry;
</PRE></TT></DL>
Each directory entry holds the file or directory
name, protection mode, access times, user-id, group-id, and addressing
information.
The entry
<TT>wuid</TT>
is the user-id of the last writer of the file
and
<TT>size</TT>
is the size of the file in bytes.
The first 6
blocks of the file are held in the
<TT>dblock</TT>
array.
If the file is larger than that,
an indirect block is allocated that holds
the next
<TT>BUFSIZE/sizeof(long)</TT>
blocks of the file.
The indirect block address is held in the structure member
<TT>iblock</TT>.
If the file is larger yet,
then there is a double indirect block that points
at indirect blocks.
The double indirect address is held in
<TT>diblock</TT>
and can point at another
<TT>(BUFSIZE/sizeof(long))<sup>2</sup></TT>
blocks of data.
The maximum addressable size of a file is
therefore 275 Gbytes.
There is a tighter restriction of
2<sup>32</sup>
bytes because the length of a file is maintained in
a long.
Even so,
sloppy use of long arithmetic restricts the length to
2<sup>31</sup>
bytes.
These numbers are based on Emelie
which has a block size of 16K and
<TT>sizeof(long)</TT>
is 4.
It would be different if the size of a block
changed.
</P>
<P>
The declarations of the indirect and double indirect blocks
are as follows.
<DL><DT><DD><TT><PRE>
    enum
    {
        INDPERBUF = BUFSIZE/sizeof(long),
    };
</PRE></TT></DL>
<DL><DT><DD><TT><PRE>
    typedef
    {
        long    dblock[INDPERBUF];
        Tag     ibtag;
    } Iblock;
</PRE></TT></DL>
<DL><DT><DD><TT><PRE>
    typedef
    {
        long    iblock[INDPERBUF];
        Tag     dibtag;
    } Diblock;
</PRE></TT></DL>
</P>
<P>
The root of a file system is a single directory entry
at a known block address.
A directory is a file that consists of a list of
directory entries.
To make access easier,
a directory entry cannot cross blocks.
In Emelie there are 233 directory entries per block.
</P>
<P>
The device on which the blocks reside is implicit
and ultimately comes from the 9P
<TT>attach</TT>
message that specifies the name of the
device containing the root.
</P>
<H4>Buffer Cache
</H4>
<P>
When the file server is
booted,
all of the unused memory is allocated to
a block buffer pool.
There are two major operations on the buffer
pool.
<TT>Getbuf</TT>
will find the buffer associated with a
particular block on a particular device.
The returned buffer is locked so that the
caller has exclusive use.
If the requested buffer is not in the pool,
some other buffer will be relabeled and
the data will be read from the requested device.
<TT>Putbuf</TT>
will unlock a buffer and
if the contents are marked as modified,
the buffer will be written to the device before
the buffer is relabeled.
If there is some special mapping
or CPU cache flushing
that must occur in order for the physical I/O
device to access the buffers,
this is done between
<TT>getbuf</TT>
and
<TT>putbuf</TT>.
The contents of a buffer is never touched
except while it is locked between
<TT>getbuf</TT>
and
<TT>putbuf</TT>
calls.
</P>
<P>
The
file system server processes
prevent deadlock in the buffers by
always locking parent and child
directory entries in that order.
Since the entire directory structure
is a hierarchy,
this makes the locking well-ordered,
preventing deadlock.
The major problem in the locking strategy is
that locks are at a block level and there are many
directory entries in a single block.
There are unnecessary lock conflicts
in the directory blocks.
When one of these directory blocks is tied up
accessing the very slow WORM,
then all I/O to dozens of unrelated directories
is blocked.
</P>
<H4>Block Devices
</H4>
<P>
The block device I/O system is like a
protocol stack of filters.
There are a set of pseudo-devices that call
recursively to other pseudo-devices and real devices.
The protocol stack is compiled from a configuration
string that specifies the order of pseudo-devices and devices.
Each pseudo-device and device has a set of entry points
that corresponds to the operations that the file system
requires of a device.
The most notable operations are
<TT>read</TT>,
<TT>write</TT>,
and
<TT>size</TT>.
</P>
<P>
The device stack can best be described by
describing the syntax of the configuration string
that specifies the stack.
Configuration strings are used
during the setup of the file system.
For a description see
<A href="/magic/man2html/8/fsconfig"><I>fsconfig</I>(8).
</A>In the following recursive definition,
<I>D</I>
represents a
string that specifies a block device.
</P>
<DL COMPACT>
<DT><I>D</I> = (<I>DD</I>...)<DD>
<br>
This is a set of devices that
are concatenated to form a single device.
The size of the catenated device is the
sum of the sizes of each sub-device.
<DT><I>D</I> = [<I>DD</I>...]<DD>
<br>
This is the interleaving of the
individual devices.
If there are N devices in the list,
then the pseudo-device is the N-way block
interleaving of the sub-devices.
The size of the interleaved device is
N times the size of the smallest sub-device.
<DT><I>D</I> = <TT>p</TT><I>DN1.N2</I><DD>
<br>
This is a partition of a sub-device.
The sub-device is partitioned into 100 equal pieces.
If the size of the sub-device is not divisible by 100,
then there will be some slop thrown away at the top.
The pseudo-device starts at the N1-th piece and
continues for N2 pieces. Thus
<TT>p<I>D</I>67.33</TT>
will be the
last third of the device
<I>D</I>.
<DT><I>D</I> = <TT>f</TT><I>D</I><DD>
<br>
This is a fake write-once-read-many device simulated by a
second read-write device.
This second device is partitioned
into a set of block flags and a set of blocks.
The flags are used to generate errors if a
block is ever written twice or read without being written first.
<DT><I>D</I> = <TT>c</TT><I>DD</I><DD>
<br>
This is the cache/WORM device made up of a cache (read-write)
device and a WORM (write-once-read-many) device.
More on this later.
<DT><I>D</I> = <TT>o</TT><DD>
<br>
This is the dump file system that is the
two-level hierarchy of all dumps ever taken on a cache/WORM.
The read-only root of the cache/WORM file system
(on the dump taken Feb 18, 1995) can
be referenced as
<TT>/1995/0218</TT>
in this pseudo device.
The second dump taken that day will be
<TT>/1995/02181</TT>.
<DT><I>D</I> = <TT>w</TT><I>N1.N2</I><DD>
<br>
This is a SCSI disk on controller N1 and target N2.
<DT><I>D</I> = <TT>l</TT><I>N1.N2</I><DD>
<br>
This is the same as
<TT>w</TT>,
but one block from the SCSI disk is removed for labeling.
<DT><I>D</I> = <TT>j(</TT><I>D<sub>1</sub></I><I>D<sub>2</sub></I><TT>*)</TT><I>D<sub>3</sub></I><DD>
<br>
<I>D<sub>1</sub></I>
is the juke box SCSI interface.
The
<I>D<sub>2</sub></I>'s
are the SCSI drives in the juke box
and  the
<I>D<sub>3</sub></I>'s
are the demountable platters in the juke box.
<I>D<sub>1</sub></I>
and
<I>D<sub>2</sub></I>
must be
<TT>w</TT>.
<I>D<sub>3</sub></I>
must be pseudo devices of
<TT>w</TT>
or
<TT>l</TT>
devices.
</dl>
<P>
For both
<TT>w</TT>
and
<TT>r</TT>
devices any of the configuration numbers
can be replaced by an iterator of the form
<TT><<I>N1-N2</I>></TT>.
Thus
<DL><DT><DD><TT><PRE>
    [w0.&#60;2-6&#62;]
</PRE></TT></DL>
is the interleaved SCSI disks on SCSI targets
2 through 6 of SCSI controller 0.
The main file system on
Emelie
is defined by the configuration string
<DL><DT><DD><TT><PRE>
    c[w1.&#60;0-5&#62;.0]j(w6w5w4w3w2)l(&#60;0-236&#62;l&#60;238-474&#62;)
</PRE></TT></DL>
This is a cache/WORM driver.
The cache is three interleaved disks on SCSI controller 1
targets 0, 1, 2, 3, 4, and 5.
The WORM half of the cache/WORM
is 474 jukebox disks.
</P>
<H4>The read-ahead processes
</H4>
<P>
There are a set of file system processes,
<TT>rah</TT>,
that wait for messages consisting of a device and block
address.
When a message comes in,
the process reads the specified block from the device.
This is done by calling
<TT>getbuf</TT>
and
<TT>putbuf</TT>.
The purpose of this is the hope that these blocks
will be used later and that they will reside in the
buffer cache long enough not to be discarded before
they are used.
</P>
<P>
The messages to the read-ahead processes are
generated by the server processes.
The server processes maintain a relative block mark in every
open file.
Whenever an open file reads that relative block,
the next 110 block addresses of the file are sent
to the read-ahead processes and
the relative block mark is advanced by 100.
The initial relative block is set to 1.
If the file is opened and
only a few bytes are read,
then no anticipating reads are performed
since the relative block mark is set to 1
and only block offset 0 is read.
This is to prevent some
fairly common action such as
<DL><DT><DD><TT><PRE>
    file *
</PRE></TT></DL>
from swamping the file system with read-ahead
requests that will never be used.
</P>
<H4>Cache/WORM Driver
</H4>
<P>
The cache/WORM (cw) driver is by far the
largest and most complicated device driver in the file server.
There are four devices involved in the cw driver.
It implements a read/write pseudo-device (the cw-device)
and a read-only pseudo-device (the dump device)
by performing operations on its two constituent devices
the read-write c-device and the write-once-read-many
w-device.
The block numbers on the four devices are distinct,
although the cw addresses,
dump addresses,
and the w addresses are
highly correlated.
</P>
<P>
The cw-driver uses the w-device as the
stable storage of the file system at the time of the
last dump.
All newly written and a large number of recently used
exact copies of blocks of the w-device are kept on the c-device.
The c-device is much smaller than the w-device and
so the subset of w-blocks that are kept on the c-device are
mapped through a hash table kept on a partition of the c-device.
</P>
<P>
The map portion of the c-device consists of blocks of buckets of entries.
The declarations follow.
<DL><DT><DD><TT><PRE>
    enum
    {
        BKPERBLK = 10,
        CEPERBK  = (BUFSIZE - BKPERBLK*sizeof(long)) /
                   (sizeof(Centry)*BKPERBLK),
    };
</PRE></TT></DL>
<DL><DT><DD><TT><PRE>
    typedef
    struct
    {
        ushort   age;
        short    state;
        long     waddr;
    } Centry;
</PRE></TT></DL>
<DL><DT><DD><TT><PRE>
    typedef
    struct
    {
        long     agegen;
        Centry   entry[CEPERBK];
    } Bucket;
</PRE></TT></DL>
<DL><DT><DD><TT><PRE>
    Bucket   bucket[BKPERBLK];
</PRE></TT></DL>
There is exactly one entry structure for each block in the
data partition of the c-device.
A bucket contains all of the w-addresses that have
the same hash code.
There are as many buckets as will fit
in a block and enough blocks to have the required
number of entries.
The entries in the bucket are maintained
in FIFO order with an age variable and an incrementing age generator.
When the age generator is about to overflow,
all of the ages in the bucket are rescaled
from zero.
</P>
<P>
The following steps go into converting a w-address into a c-address.
The bucket is found by
<DL><DT><DD><TT><PRE>
    bucket_number = w-address % total_buckets
    getbuf(c-device, bucket_offset + bucket_number/BKPERBLK);
</PRE></TT></DL>
After the desired bucket is found,
the desired entry is found by a linear search within the bucket for the
entry with the desired
<TT>waddr</TT>.
</P>
<P>
The state variable in the entry is
one of the following.
<DL><DT><DD><TT><PRE>
    enum
    {
        Cnone    = 0,
        Cdirty,
        Cdump,
        Cread,
        Cwrite,
        Cdump1,
    };
</PRE></TT></DL>
Every w-address has a state.
Blocks that are not in the
c-device have the implied
state
<TT>Cnone</TT>.
The
<TT>Cread</TT>
state is for blocks that have the
same data as the corresponding block in
the w-device.
Since the c-device is much faster than the
w-device,
<TT>Cread</TT>
blocks are kept as long as possible and
used in preference to reading the w-device.
<TT>Cread</TT>
blocks may be discarded from the c-device
when the space is needed for newer data.
The
<TT>Cwrite</TT>
state is when the c-device contains newer data
than the corresponding block on the w-device.
This happens when a
<TT>Cnone</TT>,
<TT>Cread</TT>,
or
<TT>Cwrite</TT>
block is written.
The
<TT>Cdirty</TT>
state
is when the c-device contains
new data and the corresponding block
on the w-device has never been written.
This happens when a new block has been
allocated from the free space on the w-device.
</P>
<P>
The
<TT>Cwrite</TT>
and
<TT>Cdirty</TT>
blocks are created and never removed.
Unless something is done to
convert these blocks,
the c-device will gradually
fill up and stop functioning.
Once a day,
or by command,
a
<I>dump</I>
of the cw-device
is taken.
The purpose of
a dump is to queue the writes that
have been shunted to the c-device
to be written to the w-device.
Since the w-device is a WORM,
blocks cannot be rewritten.
Blocks that have already been written to the WORM must be
relocated to the unused portion of the w-device.
These are precisely the
blocks with
<TT>Cwrite</TT>
state.
</P>
<P>
The dump algorithm is as follows:
a) The tree on the cw-device is walked
as long as the blocks visited have been
modified since the last dump.
These are the blocks with state
<TT>Cwrite</TT>
and
<TT>Cdirty</TT>.
It is possible to restrict the search
to within these blocks
since the directory containing a modified
file must have been accessed to modify the
file and accessing a directory will set its
modified time thus causing the block containing it
to be written.
The directory containing that directory must be
modified for the same reason.
The tree walk is thus drastically restrained and the
tree walk does not take much time.
b) All
<TT>Cwrite</TT>
blocks found in the tree search
are relocated to new blank blocks on the w-device
and converted to
<TT>Cdump</TT>
state.
All
<TT>Cdirty</TT>
blocks are converted to
<TT>Cdump</TT>
state without relocation.
At this point,
all modified blocks in the cw-device
have w-addresses that point to unwritten
WORM blocks.
These blocks are marked for later
writing to the w-device
with the state
<TT>Cdump</TT>.
c) All open files that were pointing to modified
blocks are reopened to point at the corresponding
reallocated blocks.
This causes the directories leading to the
open files to be modified.
Thus the invariant discussed in a) is maintained.
d) The background dumping process will slowly
go through the map of the c-device and write out
all blocks with
<TT>Cdump</TT>
state.
</P>
<P>
The dump takes a few minutes to walk the tree
and mark the blocks.
It can take hours to write the marked blocks
to the WORM.
If a marked block is rewritten before the old
copy has been written to the WORM,
it must be forced to the WORM before it is rewritten.
There is no problem if another dump is taken before the first one
is finished.
The newly marked blocks are just added to the marked blocks
left from the first dump.
</P>
<P>
If there is an error writing a marked block
to the WORM
then the
<TT>dump</TT>
state is converted to
<TT>Cdump1</TT>
and manual intervention is needed.
(See the
<TT>cwcmd</TT>
<TT>mvstate</TT>
command in
<A href="/magic/man2html/8/fs"><I>fs</I>(8)).
</A>These blocks can be disposed of by converting
their state back to
<TT>Cdump</TT>
so that they will be written again.
They can also be converted to
<TT>Cwrite</TT>
state so that they will be allocated new
addresses at the next dump.
In most other respects,
a
<TT>Cdump1</TT>
block behaves like a
<TT>Cwrite</TT>
block.
</P>
<H4>Sync Copy and WORM Copy Processes
</H4>
<P>
The
<TT>scp</TT>
process
wakes up every ten seconds and
issues writes to blocks in the buffer cache
that have been modified.
This is done automatically on important
console commands such as
<TT>halt</TT>
and
<TT>dump</TT>.
</P>
<P>
The
<TT>wcp</TT>
process also wakes up every ten seconds
and tries to copy a
<TT>dump</TT>
block from the cache to the WORM.
As long as there are
<TT>dump</TT>
blocks to copy and there is no competition for
the WORM device,
the copy will continue at full speed.
Whenever there is competition for the WORM
or there are no more blocks to
copy,
then the process will sleep ten seconds
before looking again.
</P>
<P>
The HP WORM jukebox consists of
238 disks divided into 476 sides
or platters.
Platter 0 is the
<I>A</I>
side of disk 0.
Platter 1 is the
<I>A</I>
side of the disk 1.
Platter 238 is the
<I>B</I>
side of disk 0.
On Emelie,
the main file system is configured
on both sides of the first 237 disks,
platters 0-236 and 238-474.
</P>
<H4>9P Protocol Drivers
</H4>
<P>
The file server described so far
waits for 9P protocol messages to
appear in its input queue.
It processes each message and
sends the reply back to the originator.
There are groups of processes that
perform protocol I/O on some network or
device and the resulting messages
are sent to the file system queue.
</P>
<P>
There are two sets of processes
<TT>ethi</TT>
and
<TT>etho</TT>
that perform Ethernet input and output on two different networks.
These processes send Ethernet messages
to/from two more processes
<TT>ilo</TT>
and
<TT>ilt</TT>
that do the IL reliable datagram protocol
on top of IP packets.
</P>
<P>
The last process in Emelie,
<TT>con</TT>,
reads the console
and calls internal subroutines to
executes commands typed.
Since there is only one process,
only one command can be executing at a
time.
See
<A href="/magic/man2html/8/fs"><I>fs</I>(8)
</A>for a description of the
commands available at the console.

</P>
<br>&#32;<br>
<A href=http://www.lucent.com/copyright.html>
Copyright</A> &#169; 2000 Lucent Technologies Inc.  All rights reserved.
</body></html>