.de SE
.sp 1
.sh \\$1 "\\$2 \\$3 \\$4 \\$5 \\$6 \\$7 \\$8 \\$9"
..
.ba 4
.ll 7i
.m2 2
.m3 2
.he ''The Operation of Fbackup''
.fo ''%''
.SE 1 "Background"
.pp
Fbackup is an application designed to do both full and incremental
backups of files (primarily) to magnetic tape drives, though it will also
output to stdout or disc files.
Fbackup is a multiprocessed program.  Each fbackup session will always have
one 'main' process, one 'writer' process, and one or more 'reader' process(es).
The main process controls most of the activities during backups including
initiating most actions in the writer process and reader process(es).
These processes communicate with each other primarily by using a shared memory
segment, but a semaphore, 'reliable' signals and a pipe are also employed.
.pp
At the most fundamental level, the main and reader processes fill the shared
memory segment with data, and the writer process writes it to the output media.
.pp
Another useful document may be found with the frecover source code.  The file
is named 'tape.fmt', and is in troff source format.
It contains a description of the output files generated by fbackup,
which are, of course, the input files for frecover.
.SE 2 "Three Executable Files and Their Location"
.pp
Since fbackup is a multiprocessed application, it must do forks.  The main,
reader and writer processes have essentially no common functionality, and the
main process (in particular) is very large.
It seemed rather a waste to have only one executable file which behaved
differently depending on whether it was invoked as a main, reader or writer
process.
This lead to having three different executable files, fbackup, fbackuprdr,
and fbackupwrtr.  After each fork, fbackup execs either fbackuprdr or
fbackupwrtr.
This means that fbackuprdr and fbackupwrtr must either be somewhere in the
search path of the user, or they must be in a know location.
Since we could not rely on the search path approach, we chose to put them
in a fixed know location, /etc.  (READER is defined to be "/etc/fbackuprdr"
and WRITER is defined to be "/etc/fbackupwrtr" in the file head.h)
This has the unfortunate side-effect that a user cannot, say, copy the three
executables to his home directory and then run his local copy of fbackup.
Actually, he would be running the local fbackup, but he would still be running
the fbackuprdr and fbackupwrtr in /etc.  This was the best solution we could
think of; if you, dear reader, know of something better, please implement it.
.SE 2 "The Shared Memory Segment"
.pp
Most of the inter-process (and some intra-process) communication is done via
the shared memory segment.  There are four logical divisions of this shared
memory segment: A) the 'ring', B) the 'pad' area,
C) the 'rdr' (reader) area, and D) the 'rec' (record) area.
Actually, the rdr and rec sections are defined (and contained) within the
pad structure, but they are logically independent.
.SE 3 "The 'ring' section"
.pp
The shared memory 'ring' is really just a region of shared memory that is used
in a manner such that byte 0 is the address following byte B-1, in an B byte
area.  The ring is divided into one or more 'records'.  Records are, in turn,
divided into one or more 512 byte 'blocks'.  It is possible to specify the
number of blocks per record and (independently) the number of records.  Hence,
it is possible to specify the size of the ring.  For example, if the user
specifies a ring containing 8 records of 16 (512 byte) blocks, the size of the
ring will be 8 x 16 x 0.5k = 64k bytes.  Fbackup will first attempt to fill
record 0 with data.  When this is complete, it fills record 1.  In the example
above, when record 7 is filled, it again uses record 0, and so on.  The
variable 'char *segment' is used to reference the first byte of the ring.
.SE 3 "The 'pad' section"
.pp
The 'pad' section of shared memory is used to hold all the variables which
are needed by more than one process.
The only exceptions to this are the values which the writer process and the
reader process(es) require in order to begin their operation.  These values
are passed as command line arguments.  (See the main() functions in reader.c
and writer.c, and the execl/execv calls in main.c.)
For a description of each variable in the pad section, see
the PADTYPE data structure in head.h.
The variable 'PADTYPE *pad' is used to reference this data structure.
.SE 3 "The 'rdr' section"
.pp
The rdr section of shared memory (which is actually contained in the PADTYPE
data structure) is used to indicate the status of each reader process.  It
is an array of structures of type RDRTYPE.  Only the main process and the
reader process(es) have reason to access this area; the writer process has
no need to know the status of the reader(s).
The variable 'RDRTYPE *rdr' is used to reference this data structure, however
this is really a shortcut way of accessing pad->rdr (one less level of
indirection).
.SE 3 "The 'rec' section"
.pp
The rec section of shared memory (which is actually contained in the PADTYPE
data structure) is used to indicate the status of each ring record.  It
is an array of structures of type RECTYPE.  All processes access this region
of shared memory.
The variable 'RECTYPE *rec' is used to reference this data structure, however
this is really a shortcut way of accessing pad->rec.
.SE 1 "Operation"
.pp
A normal fbackup session has three phases, 1) initialization,
2) building the file list (the 'flist'),
and 3) backing up the data onto the output media.  
.pp
Note: Throughout the following description, the word 'file' is used to
indicate a link to any kind of a file as long as it has an i-node which
describes it which is accessible by the system being backed up.
Hence, a 'file' may be a 'regular' data file, a hard link, a symbolic link,
a directory, a (block or character) special file, a named pipe, etc.
.SE 2 "Phase 1 - Initialization"
.pp
The initialization of the main process, writer process, and reader process(es)
is relatively straight-forward, and described fairly completely in the code.
Perhaps the most important thing to note is 
the order in which values are assigned in the pad shared memory area.
For certain variables, their values are required by the writer process and
reader process(es) very soon after they are invoked.
Hence, the main process first
gets the shared memory segment, then attaches it,
then assigns values to some appropriate pad values,
and then forks and execs the writer process and the reader process(es)
(and then builds the flist, which is incidental to this discussion).
As soon as these processes attach the shared memory segment,
these values are immediately usable by the child processes.
.SE 2 "Phase 2 - Building the 'flist'"
.pp
The essential points of building the flist under 'normal' operation are
described in this section.
Most of the code to build the flist is found in the files search.c and flist.c.
In the 'normal' case, the functions search() and expanddir() are used to do
ordinary recursive tree expansion of a pathname.
Fbackup uses readdir() to read the names of the files contained within a
directory; unfortunately, these files are not in 'sorted' order.
There is an automatic array
with NUMCHILDREN elements which is used to hold the child file names.  If there
are too many files to fit in this array, a new array of double the size of the
previous one is allocated.  This doubling continues until there is enough array
space.
After the files are read into the array, qsort() is used to sort them.
The sorting of the directory entries is described in the expanddir() code.
.pp
After this sort, fbackup sequences through all these files and each one is
checked to see if it should be excluded from the session
because it is in one of the two exclude tables.
These tables are described below.
In the normal case (when a file is not excluded), add_flistnode() is called
to selectively add the file to the flist.
The selectivity depends on when the file was last modified (both its mtime
and ctime values are used to determine this).
.pp
There are two exclude tables, one for directory entries, and the other for
non-directory (everything else) entries.  (This could have been done
with only one table, but it was thought that two would be faster, as a simple
linear search is used for each table.
It is expected that the non-directory table should be empty most of the time
in 'typical' operation.)
Files get into these tables (and omitted from the session)
by being explicitly excluded (eg, with the -e option).
These two tables are built during the initialization phase (phase 1).
Each time a directory is encountered, it is checked
to see if it has been specifically excluded in the directory exclude table.
If it has, this directory is skipped.  If not, it is processed normally.
Non-directories are handled in an exactly analogous fashion.
.SE 3 "Adding Leading Directories"
.pp
The function make_flist() in the file inex.c is responsible for taking the
pathnames (files) in the include list and calling search() to expand them.
However, if the pathname selected has more than one part, each component of
the name is stripped off one at a time and added (in proper sorted order) to
the flist.  See the comments in make_flist().  This may result in something
other than what the user desires if, for example, s/he specifies
./../thisdir as a pathname to be included in a session.
.pp
.SE 3 "Exceptions while Building the 'flist'"
.pp
The essential points of building the flist under abnormal or unusual operation
are described in this section.
All of these cases only apply to directories; non-directories do not cause
any peculiar problems because they are never the origin of links.
Most of the complications in the function expanddir() are due to one of the
following 'exception' cases.
.SE 3 "Sibling Links ('siblinks')"
.pp
What I have called 'siblinks' are multiple links with different names that
link the same inode (eg, inode A) to the same other inode (eg, inode B).
For example, if there is a directory named Parent and it contains two links,
named link1 and link2, where both links point to the same object.  Under these
conditions, only one of the links should be expanded; the other one should be
handled as a link to the (already expanded) inode.  There is code which looks
through all the previous directory files (contained within the directory
which is expanddir()'s current working directory) to see if any of them are
siblinks with the one presently being examined.
It is described more completely below.
.SE 3 "Weird Directories: When Dotdot ('..') is not the 'Parent' Directory"
.pp
Weird directories can occur when there is more than one hard link to the same
directory.  Generally, the directory is created by calling mkdir.
Let's assume we have a directory named 'dad' with a child directory
named 'son'.  This is a link to inode I ('dad/son').
Also, assume there is another link to inode I called 'stepdad'
(from a directory which is not the same inode as 'dad';
this would be a siblink).
Since the directory inode called 'son' can have only one dotdot (..) link,
it cannot have both 'dad' and 'stepdad' as parent directories.  Yet both 'dad'
and 'stepdad' have 'son' as a child.  (Note that the link from 'stepdad'
the the inode represented by 'son' may be named anything; it need not
be called 'son'.)  I have called any directory, C, with one or more hard links
to it where C's dotdot pointer does not point to the directory from which the
link(s) to C originated, a 'weird' node.
.SE 4 "Forward Links"
.pp
Weird nodes may be, for example like the example above, with 'dad', 'son',
and 'stepdad'.  That is, the dotdot pointer only points to one of the
multiple 'parents'.
If the 'true parent' (the one pointed to by the dotdot pointer)
comes before any 'surrogate parent' (in the sorted order of the flist),
the 'surrogate parent' can simply be handled as a hard link to
the 'true parent'.
However, any of the 'surrogate parents' which precede the 'true parent' must
be marked as being 'forward links'.
(Frecover should produce an exact
reproduction of the original file system, it is important to know which is the
true and which is/are the surrogate parent directory/ies.)
When such a 'surrogate parent' is found (before the 'true parent'), it is know
that it should be a link to something, but since we haven't got to that thing
yet, we don't know what is should be.  These cases have their fwdlinkflag
set to TRUE, and they are handled by the function doweirds() after all the 
non-weird inodes have been handled.
.SE 4 "Excessively Weird Directories"
.pp
In the case where there is NO 'true parent' directory, (only 'surrogate parent'
directory/ies, we have an excessively weird file system.  Such inodes cannot
be linked to one 'true parent' either through forward or backward links,
because there isn't one.  As a result, such a directory is added to the
weird list (as any other weird node would be), but since non of the links
to this inode is the 'true parent' it would never have been expanded.
(The main reason for determining the one 'true parent' is so that directory
subtree gets expanded (properly) exactly once.)
When doweirds() discovers such a directory, it finds the appropriate
place in the flist, and expands the subtree so that the new flist elements
are inserted at their proper (sorted) place in the flist.
.pp
One interesting thing to note: even though these weird file trees (really
acyclic graphs) are legal as far a UNIX is concerned, fsck may well think
that some of them are bogus.  Nevertheless, fbackup and frecover should
faithfully and accurately restore these weird graphs to their original state.
.SE 2 "Phase 3 - Backing up the Data"
.pp
After the flist has been built, the main process begins sequencing through
it and selecting each file successively.
(Recall that the flist is in 'sorted' order.)
As each filename is selected, it is tested to see if it
exists and if it is accessible by the user.  If both of these conditions are
OK, the data required to recover that file is copied into the ring.  If the
file is a 'regular' disc file, the main process assigns a reader process to
read in either, A) the entire contents of the file - if it will fit, or,
B) however much of the file that will fit, into the available ring shared
memory.
This process is repeated, if necessary, until the entire file has been read in.
If the file is a
directory, the main process reads all the names of the children files contained
within that directory into shared memory (separated by null characters).
In the case of any other kind of file (ie, a symbolic link, a special file,
named pipe, etc.),
no (additional) data is required to recover the file, so none is put in the
ring.
.SE 3 "Headers and Trailers"
.pp
Warning, this section is even more poorly written than the other sections, but
I didn't have time to fix it up.  Sorry about that, dear reader - you'll just
have to try and figure it out.
.pp
Obviously, something must be put into the ring if symbolic links and special
files are to be recovered.  For each file backed up, (all files
which exist and are accessible), a 'header' is constructed in the ring before
the data (data is present only for 'regular' files and directory files)
and a 'trailer' is constructed in the ring after the data.  One header and
one trailer are ALWAYS present for each file,
even if there is no data between them.
The data contained in trailers is described by the structure FTRLTYPE, in the
file /usr/include/fbackup.h.  Trailers are ALWAYS one block in length.
The data contained in headers is described by the structure FHDRTYPE, in the
file /usr/include/fbackup.h   Headers may be one or more blocks in length.
.pp
Both headers and trailers have fixed parts and variable parts.  The variable
parts consist of a label, a colon (':'), and then the value associated with
that label.  These triplets are null terminated.  Values may be arbitrarily
long, with the exception that no information kept in the trailer must cause
the trailer to be more than one block long.
.pp
The most critical piece of data in the trailer is the status byte.  This is
the byte which indicates that the file has or has not changed (either its
contents or its i-node data has been modified).  It cannot be determined
whether or not a file was active during the interval when it was being backed
up until after it has been completely copied into the ring.
Hence, a trailer is required for each file.
.pp
The shared memory ring is filled by both the main process and the reader
process(es).  Readers are only called to read some or all of a 'regular'
file into a specific location of the ring.  There are four important parameters
which a reader requires in order to accomplish its task: A) which file, B) the
offset (how much of the file to skip if this is not the first read), C) the
number of bytes to read, and D) the location in the ring to put the data.
Headers, trailers, and directory contents are all handled by the main process.
.SE 3 "Record Status"
.pp
The coordination of what each reader is doing and the status of each record of
the ring is handled by signal handlers in the main process.
As each file is sequentially selected
from the flist, the main process determines how much ring space the file will
occupy, and in the case of a regular file, it assigns a free reader process to
read the data into the ring.  The status of each record can have one of the
following four values: FREE, PARTIAL, ALLOCATED, or COMPLETE.
A FREE record is one that is just that.  PARTIAL means that a record has had
the first block(s) of it allocated (but perhaps not filled with data yet), but
there is at least one of the last block(s) which the main process has not yet
set aside as the location where data will be put (at least one block in this
record must not be 'allocated' to any file yet).  A PARTIAL record may have
none, some, or all, of its 'allocated' block(s) filled with data.
An ALLOCATED record is one where all block(s) of the record have
been 'allocated'.
ALLOCATED records may have none or some of its block(s) filled with data.
When all of these blocks fill with data, the record's status changes from
ALLOCATED to COMPLETE.  That is,
a record is COMPLETE when an all the block(s) of an ALLOCATED record get
filled with data.  COMPLETE records are ready for the writer process to write
to the output file.
All records are initialized to be FREE,
and the transition diagram looks as follows.
.(b
.hl

.ce
Ring Record State Diagram


.nf
                                      ----
                                      |  |(M)
         (initial st.)    (M)         |  v
              FREE -----------+----> PARTIAL
                ^             |         |         (M) - Main process
                |(W)          |(M)      |(M)      (W) - Writer process
                |             +------+  |
                |                    |  |
                |          (M)       v  v
              COMPLETE <---------- ALLOCATED
.fi

.hl
.)b
.pp
In the above diagram, it is evident that the writer process is responsible for
the transition from COMPLETE to FREE.  The main process is responsible for all
the other transitions.  (Note: exception cases such as the last file and active
files are not shown.)
.SE 3 "markempty() and markfull()"
.pp
These are the functions of the main process which actually cause the rec data
structure (the status of the ring records) to be changed.  Whenever the main
process grabs a chunk of ring memory (either to fill itself or to assign to a
reader process to fill it), it calls markempty().  Likewise, whenever the main
process learns that a chunk of ring memory has been filled (either by filling
itself or discovering that a reader process has completed filling it),
markfull() is called.  Together, these functions are responsible for causing
most of the state transitions of ring records.
.SE 3 "Reader Process Operation"
.pp
Reader process(es) also 
sequence through several states in the course of normal operation.
The legal states are: READY, START, BUSY, and DONE.
READY indicates that a reader is free to be assigned to read (some or all of)
a file into the ring.  Initially, the main process sets the status of any
the reader process(es) to BUSY.  After each reader process completes
initialization, it changes its status (rdr->[reader].status) to READY.
(This initialization is not shown in the state diagram below.)
The normal cycle is now ready to begin (shown in the diagram below).
After it has allocated the needed space in the ring, the main process provides
the reader process with all the requisite information for it to proceed.
The main process then sets that reader's status to START, and sends that
(most likely sleeping) reader process a signal to get it to begin reading.
Reader processes indicate that they are working by changing their status from
START to BUSY; that is the very first thing they do whenever they are told to
start reading.  After the reading is complete, reader processes set their
status to DONE, and then send a signal to the main process to indicate this.
The main process has a signal handler which checks to see if there are any
readers which have completed their task.  If such a reader is found, the status
of any appropriate ring records are adjusted, and the status of this reader is
set to READY, so the cycle may begin again.
.(b
.hl

.ce
Reader Process State Diagram


.nf
                           (M)
              READY -----------------> START
                ^                       |         (M) - Main process
                |(M)                    |(R)      (R) - Reader process
                |          (R)          v
              DONE <------------------- BUSY
.fi

.hl
.)b
.SE 3 "Writer Process Operation"
.pp
The writer process also sequences through several states.
The legal states during normal operation are:
BUSY, READY, DONE, and EXIT.  Whenever there is an active file or a tape write
error, the additional states RESET and RESUME may occur.
The main process initializes the writer status (pad->wrtrstatus) to be BUSY,
and then the writer
process sets it to READY when it has completed initialization.  The
writer remains in this state until either the flist is exhausted, or there is
an active file or a tape write error.  In the former case,
the writer goes first to DONE and then to EXIT states.  In the latter case,
the writer process changes the status to RESET.
This causes the main process to suspend its activities, prepare to
restart at a previous file, and then changes the writer's status to RESUME.
When the writer process discovers that it is in RESUME state, it does the
necessary tasks to prepare to resume writing, and then changes its status
back to READY.  Normal operation resumes after this (hopefully).
.(b
.hl

.ce
Writer Process State Diagram


.nf
   (initial st.) (W)              (M)
        BUSY ----------> READY ---------> DONE
                         ^  |               |     (M) - Main process
            +------------|  |(W)            |(W)  (W) - Writer process
            |(W)            |               |
            |      (M)      v               v
        RESUME <-------- RESET            EXIT
.fi

.hl
.)b
.SE 2 "Non-deterministic Operation"
.pp
Assuming normal operation (eg, there are no inaccessible or active files),
space for headers, contents (when required), and trailers are assigned in a
predictable and reproducible order.
However, when there are two or more reader processes, the order in which the
data portions are filled in by the reader processes is non-deterministic.
In the general case, there is no guarantee that fbackup will ever run precisely
the same way twice.  However, given identical file systems, the output file
produced should be the same in all cases, irrespective of the number of reader
processes.
.SE 1 "Output to Tape Drives"
.SE 2 "EOT Conditions"
.pp
Fbackup does not attempt to determine how much data will fit on a tape volume
in advance (eg, by knowing the length of the tape and the bit density).
Instead, after each write to the tape, the status of the drive is checked to
see if the EOT mark has been detected.  If it has been, and there has not been
a write error, fbackup assumes that there is enough tape left after the EOT
mark to write two EOF marks (a valid assumption), which signifies the end of
this volume.  This scenario is slightly complicated by tape drives operating
in 'immediate report mode'.  In this mode, drives often report the
success of a write() call when it has been accepted by the driver's buffer (but
not yet written to the tape).  However, standard magnetic tapes should always
have enough good tape after the EOT mark to handle the all the data in the
drive's buffer.  So, unless a tape write error occurs, this should cause no
problems.
.SE 2 "Magnetic Tape Drive Write Errors and Checkpointing"
.pp
Fbackup has the ability to recover from some tape write errors.  It does this
by 'checkpointing' magnetic tape output files and then using this
information (when possible) to prevent the session from having to be
restarted from the beginning.
.pp
Checkpoint records are placed every R records (where R can be configured by the
user).  They contain information pertaining to the tape record immediately
following the checkpoint record.
Note: in this discussion, 'tape record' numbers only refer to those records
holding 'data' being backed up for the session.  None of the other 'records'
(eg, tape labels, volume headers, EOF marks, checkpoint records, etc.) are
counted.
For example, assume that R is 200.  Before tape record
0, there is a checkpoint record indicating that tape record 0 immediately
follows.  This checkpoint record also indicates to which file the first data in
the following tape record belongs (indicated by an flist index number),
how many blocks into the file it is, and some other relevant information.
Since R is 200, tape records 0 through 199 follow the first checkpoint record.
Then there is another checkpoint record before tape record 200, which contains
information pertaining to tape record 200.  Each checkpoint record is
immediately preceded by an EOF mark, so that they may be found quickly.
For more detail on the format of magnetic tape output files, refer to the
tape format specification (kept with the frecover source code).
.pp
In addition to producing 'checkpoint records' on magnetic tape output files,
fbackup also maintains 'internal' checkpoint data structures.
Two internal checkpoints are kept, one for the beginning of the current volume
and one for the most recent checkpoint record successfully written to tape.
.pp
Whenever a write error is discovered on a magnetic tape output file, fbackup
attempts to back the tape up and read the previous 'tape checkpoint record'.
If it cannot do this or the 'tape checkpoint record' does not match
the internal record checkpoint structure,
the user is forced to toss this volume and rewrite
it from the beginning.
.pp
If the 'tape checkpoint record' and the internal record checkpoint structure
match,
fbackup cleans up the end of the tape so that it looks like a normal end of
volume.  The user is then given the option of keeping the good part of the data
on this (partially bad) volume and beginning from 'this point' forward on the
next volume, or tossing this volume and rewriting it from the beginning.
The one exception is when a write error occurs between the first and second
checkpoints on any volume;
the user is not given the option of keeping the partially bad volume.
In this case, the volume is automatically rejected.
.SE 1 "Output to Non-magnetic Tape Drive Output files"
.pp
Whenever the output file is not a magnetic tape drive, write errors are fatal.
For example, if the output file is an ordinary disc file or the standard output,
any time fbackup discovers the failure of a write() call, it causes the
termination of the session.  There is no checkpointing for non-tape drive
output files.
.SE 1 "Active Files"
.pp
Fbackup attempts to handle 'active files' (files which have either their ctime
or mtime values changed during the time fbackup was placing their information
into the ring) by repeatedly attempting to back them up until A) an inactive
copy is transferred to the ring, or B) some user defined limits are exceeded -
in which case fbackup gives up and continues with the next file.
Because only 'regular' files and directories will have
any 'contents' (between the header and trailer),
these are the only types of files
which may be active.  The following discussion applies to both magnetic tape
and non-magnetic tape output files.
.pp
The main process is the only one capable of detecting that a file is active.
Unfortunately, by the time this discovery has been made, the writer process
may have already started writing the data for this file to the output file.
In fact, it is even possible to have a volume change in the middle of an active
file, though this is unlikely unless the active file is very large.  Because of
these possibilities, it was decided that it was better to have a trailer
following every file indicating its status.  Thus, active files
are always completely written to the output file, but their status will be
marked active, and hence, will be ignored by frecover.
There is one byte in the trailer which is used to indicate
the status of a file: active, (ASCIIBAD) or an inactive, (ASCIIGOOD).
.pp
In the course of backing up a 'regular' file, the main process first allocates
space in the ring for the header, and then fills it with header information.
Next, the space for file's data is allocated, and the reader process(es) are
assigned the task of filling this space with the file's contents (this happens
asynchronously).  Finally, the
main process allocates the trailer space and then fills it.  If by this time
the last reader process has completed,
the status is set accordingly (ASCIIBAD for an active file, otherwise
ASCIIGOOD).
.pp
If the last reader process was not finished when the trailer was being built
and the file had not been modified (up to that time),
the status is set to ASCIIGOOD, as least temporarily.
If the main process discovers that the file had been active,
it sets the status to ASCIIBAD.
.SE 2 "The Pending File Table"
.pp
The pending file table is an array of structures designed to hold all the
information necessary to process a file.
For each file which has not been processed completely (each 'pending' file),
an entry is maintained in the pending file table.
For a session running with P reader
processes, only P+1 entries are required in the table.  This is because the
worst case would be when each of the reader processes was working on a
different file, while the main process was looking for a free entry in the
pending file table.  It is not possible for the main process to be looking for
another FREE entry in the table before one of the P+1 entries became FREE.
.pp
Part of the data maintained in the pending file table is the location of the
status byte for each pending file (the index in the ring).
This enables the main process to change
the status of a file from ASCIIGOOD to ASCIIBAD even after the trailer has
been built, but before the file gets written out by the writer process.
This condition is indicated when the status of this pending file is set to
TRLINMEM (trailer in memory).
.pp
There are two counter variables kept in this table which enable the main
process to determine when a 'regular' file has been completely read in by
the reader process(es).
The 'chunks' counter indicates the number of sections of the file that have been
assigned to be read into the ring.  The 'chunksfull' variable indicates the
number of these sections which have been filled.  Note that the particular
reader process(es) which did the reading are irrelevant.  All the chunks could
have been assigned to the same reader process, or any combination of the
reader(s) could have been (non-deterministically) scheduled.
The only matter of concern is the values of chunks and chunksfull.  When these
values are equal, and when the trailer has been completed (indicated by the
status being TRLINMEM), the entire file has been copied into
the ring.
.SE 2 "What Happens When an Active File is Discovered"
.pp
When an active file is detected by the writer process, it writes out everything
up to and including the trailer block for that file, but not any part of the
next file (even portions of both files are contained in the same record).
The writer process then stops any further writing and changes its status to
RESET, and hence, informs the main process that there is a problem.
The main process stops assigning any new tasks
and then waits for the reader process(es) to finish any work they are
currently doing.  When all this main and reader activity finishes, the main
process informs the writer process that it is ready to resume (by a 'goto
resume:') by setting the writer status to RESUME.  The main process determines
which file to resume at by calling the function reset().
.SE 1 "Signal Handlers"
.pp
Most of the communication between processes is initiated by signals.  The
writer process and reader process(es) sleep whenever they have nothing to
do.  The main process sleeps whenever it runs out of resources (ie, reader
process(es), ring space, or files to back up).  All of the processes have
signal handlers.  It is fairly clear in the code what happens when
an 'abnormal' signal is received, such as an interrupt.  However, in the normal
course of backing up files, lots of signals are sent.  Whenever the main
process wants to start a reader process, it sets up all the relevant data in
the rdr shared memory section and then sends a signal (SIGUSR2) to the
appropriate reader.
Likewise, when a reader is finished with it's task, it sends a signal (SIGUSR2)
to the main process to indicate this.
Whenever a ring record is ready to be written, the main process sends a signal
(SIGUSR1) to the writer process.
When the writer process has finished processing a ring record, it sends a signal
(SIGUSR1) to the main process to indicate this.
.pp
There are other circumstances when the writer sends a SIGUSR1 to the main
process; basically, it sends a SIGUSR1 whenever the writer requires the
attention of the main process.
.pp
When the main process wants to kill its children processes, it sends the
reader process(es) a SIGUSR1 and the writer process a SIGUSR2.  Note that
these are 'crossed' signals from those used in normal operation.
.pp
Signal handlers exist in all of these processes to catch these signals.
Whenever the main process receives a signal from a reader process, it must
take any appropriate actions to update the status of the reader process(es),
the state of the ring records, and its own internal state.
Whenever the main process receives a signal from the writer process,
it's only task is to see if any index actions are required.
.SE 1 "Indices and the Pipe"
.pp
Fbackup produces an 'index' of what it thinks will be on each volume (see the
manual page). 
As the flist is being built (phase 2), a count of the number of bytes required
to hold the index is updated as the flist grows.  When hard links are
discovered, this count is also increased - since hard links are also shown in
the index.  This means that at any point during an fbackup session, the size of
the index is know.
.pp
Fbackup writes its best guess of what the index should be at the beginning of
every volume.  (Note that these indices are only correct for previous volumes.)
However, the data which is used to build the index (the flist)
is kept by the main process.
Unfortunately, the writer process is the one that writes it to the output file.
Hence, a pipe is used to transfer the data from one to the other.
To do this, the writer first sets pad->idxcmd to SENDIDX, and then
sends a signal to the main process.  The main process then sends the index over
the pipe to the writer.  As the data comes in, the writer buffers it up and
writes it out in recsize byte records.  When the entire index has been sent, a
null byte is sent to indicate to the writer that the transfer is complete.
This is the first use of the pipe.
.pp
This same pipe is used for a a second purpose.  After each volume finishes, the
flist must be updated to the revise the guess of where each file will
reside.  Again, the flist is kept by the main process, so the writer
sets the variable pad->updateafter to a value (update from file N+1 on, if this
value is set to N), sets pad->idxcmd to UPDATEIDX, and then signals
the main process.  This causes the main process to do the update and then
send a null byte over the pipe.
.SE 1 "Stopping and Restarting a Session"
.pp
If fbackup is in phase 3 (backing up files), it is possible to stop the session
and save its present state.
(If fbackup gets an interrupt during phase 1 or 2, the session is
terminated immediately; the state cannot be saved.)
Recall that the flist was completely built during
phase 2.  When the main process receives an interrupt signal during phase 3,
fbackup asks if the user wishes to save the state.  If s/he does, some
data pertinent to the session and also a record for each element in the flist
is saved in a file specified by the user.
.pp
When backup receives the interrupt, it finishes the file it is currently
working on, but does not proceed to the next one.  Hence, it is probably
not a good idea to wait until volume change time to interrupt the program.
This approach will work, but it (most likely) has the unfortunate result of
producing a very short volume.
If an interruption is necessary, it would be
better to wait until near the end of a volume, if possible.
This way, you get a nearly full volume.
.pp
If fbackup is then run with the -R option, the reverse of this procedure
occurs, and fbackup continues from where it left off before.
When fbackup is running in this mode, the session may be interrupted again
as usual, because after files start being backed up again, the
session is no different from one which was started without using the -R
option.
.SE 1 "The Semaphore and pad->avail"
.pp
Only one semaphore is used by fbackup.  Its sole purpose is to provide
exclusive access to one variable, pad->avail.  This variable is used by both
the main and writer processes, but not any reader process(es).  It indicates
the amount of available ring shared memory.  Whenever the main process wants
a section of the ring, it checks this variable to see if there is enough
available.  If there isn't, it goes to sleep until there is enough.  When
sufficient ring memory is available, exclusive access is obtained by doing a GET
operation on the binary semaphore.  pad->avail is then decremented by the
appropriate amount, and a RELEASE operation is done on the semaphore.
Analogously, whenever the writer process finishes writing a record, it gets
exclusive access to pad->avail, increments its value by recsize, and then
releases the semaphore.
.SE 1 "RESET, 'reset:', RESUME, and Restart"
.pp
These four terms require some explanation primarily because of the -R
(restart) option.  The other three terms have nothing to do with this
command line option.  They are used when an active file has been discovered or
when there has been a tape write error.
Notice that there is a 'resume:' label in the function work()
in the file main.c.
There are two ways to reach this label: 1) by entering the top of the loop
which sequences through the flist (either with or without using the -R option),
or 2) by discovering an active file or a tape write error.
.SE 1 "Login and Group Names"
.pp
For security reasons, the ASCII login and group names are used in addition to
the user-id and group-id numbers.  The file pwgr.c consists of routines which
build two hash tables.  Fbackup searches through the password file and then the
group file to gather the necessary data.  There are also two lookup routines
which search the hashed table of linked lists.  The linked lists are searched
linearly if there is more than one element.  It is hoped that this technique
will prove to be sufficiently fast.
.SE 1 "The Consumption of Virtual Memory by the 'flist'"
.pp
Fbackup was originally written so the flist was kept in a disc file.  This
can cause a problem, however, when the file system is completely full and the
user wishes to back it up so s/he can remove some files.  If there is no room
left on the disc to put this temporary file, the backup cannot be
(conveniently) done.  This prompted the decision to keep the flist in virtual
memory.  Unfortunately, this introduced the problem that fbackup can fill up
VM if it is run on extremely large file trees.  In particular, if the user
puts the entire file system on one session (-i /), fbackup can run out
of memory.  Fbackup was never designed to be used in this manner, and it is
recommended that users split large disk farms up into more than one session.
Fbackup provides lots of functionality to allow users to do this easily.
However, if a user does back up all of a very large system on only one session,
s/he may hit this limitation.  When this happens, the session terminates.
.SE 1 "Recommendations"
.pp
I think that one source of slow operation may be the way
hard links to non-directories are handled.  Each one is put on the same linked
list, so the list can grow very long.  In retrospect, I think a hash table
of linked lists (similar to the user and group names) would have been a much
better solution, but I ran out of time.  I think this should at least be
investigated to see if such an approach is warranted.
