    FILE SYSTEM(V)                2/9/75               FILE SYSTEM(V)

    NAME
         fs - format of file system volume

    DESCRIPTION
         Every  file system storage volume (e.g. RF disk, RK disk, RP
         disk, DECtape reel) has a common format  for  certain  vital
         information.   Every  such  volume is divided into a certain
         number of 256 word (512 byte) blocks.  Block 0 is unused and
         is  available to contain a bootstrap program, pack label, or
         other information.

         Block 1 is the super block.  Starting from its  first  word,
         the format of a super-block is

         struct {
              int  isize;
              int  fsize;
              int  nfree;
              int  free[100];
              int  ninode;
              int  inode[100];
              char flock;
              char ilock;
              char fmod;
              int  time[2];
         };

         Isize  is  the number of blocks devoted to the i-list, which
         starts just after the super-block, in block 2.  Fsize is the
         first  block  not  potentially available for allocation to a
         file.  These numbers are used by the system to check for bad
         block numbers; if an ``impossible'' block number is allocat-
         ed from the free list or is freed, a diagnostic  is  written
         on  the  on-line  console.   Moreover,  the  free  array  is
         cleared, so as to prevent further allocation from a  presum-
         ably corrupted free list.

         The free list for each volume is maintained as follows.  The
         free array contains, in free[1], ... , free[nfree-1], up  to
         99  numbers  of free blocks.  Free[0] is the block number of
         the head of a chain of blocks constituting  the  free  list.
         The first word in each free-chain block is the number (up to
         100) of free-block numbers listed in the next 100  words  of
         this  chain  member.   The  first of these 100 blocks is the
         link to the next member of the chain.  To allocate a  block:
         decrement  nfree,  and the new block is free[nfree].  If the
         new block number is 0, there are no blocks left, so give  an
         error.   If  nfree  became 0, read in the block named by the
         new block number, replace nfree by its first word, and  copy
         the block numbers in the next 100 words into the free array.
         To free a block, check if nfree is 100; if  so,  copy  nfree
         and  the  free array into it, write it out, and set nfree to
         0.  In any event set free[nfree] to the freed block's number
         and increment nfree.

                                  - 1 -

    FILE SYSTEM(V)                2/9/75               FILE SYSTEM(V)

         Ninode  is  the number of free i-numbers in the inode array.
         To allocate an i-node: if ninode is greater than  0,  decre-
         ment  it and return inode[ninode].  If it was 0, read the i-
         list and place the numbers of all free inodes  (up  to  100)
         into  the  inode  array, then try again.  To free an i-node,
         provided ninode is less than 100, place its number into  in-
         ode[ninode] and increment ninode.  If ninode is already 100,
         don't bother to enter the freed i-node into any table.  This
         list  of i-nodes is only to speed up the allocation process;
         the information as to whether the inode is  really  free  or
         not is maintained in the inode itself.

         Flock and ilock are flags maintained in the core copy of the
         file system while it is mounted and their values on disk are
         immaterial.  The value of fmod on disk is likewise immateri-
         al; it is used as a flag to indicate  that  the  super-block
         has changed and should be copied to the disk during the next
         periodic update of file system information.

         Time is the last time the super-block of the file system was
         changed,  and  is  a  double-precision representation of the
         number of seconds that have elapsed since 0000 Jan.  1  1970
         (GMT).  During a reboot, the time of the super-block for the
         root file system is used to set the  system's  idea  of  the
         time.

         I-numbers  begin at 1, and the storage for i-nodes begins in
         block 2.  Also, i-nodes are 32 bytes long, so 16 of them fit
         into  a  block.   Therefore,  i-node  i  is located in block
         (i + 31) / 16, and begins 32.((i + 31) (mod 16)  bytes  from
         its  start.   I-node 1 is reserved for the root directory of
         the file system, but no other i-number has a built-in  mean-
         ing.   Each i-node represents one file.  The format of an i-
         node is as follows.

         struct {
              int  flags;    /* +0: see below */
              char nlinks;   /* +2: number of links to file */
              char uid; /* +3: user ID of owner */
              char gid; /* +4: group ID of owner */
              char size0;    /* +5: high byte of 24-bit size */
              int  size1;    /* +6: low word of 24-bit size */
              int  addr[8];  /* +8: block numbers or device number */
              int  actime[2];     /* +24: time of last access */
              int  modtime[2];    /* +28: time of last modification */
         };

         The flags are as follows:

          100000   i-node is allocated
          060000   2-bit file type:
               000000   plain file
               040000   directory
               020000   character-type special file
               060000   block-type special file.
          010000   large file

                                  - 2 -

    FILE SYSTEM(V)                2/9/75               FILE SYSTEM(V)

          004000   set user-ID on execution
          002000   set group-ID on execution
          000400   read (owner)
          000200   write (owner)
          000100   execute (owner)
          000070   read, write, execute (group)
          000007   read, write, execute (others)

         Special files are recognized by their flags and  not  by  i-
         number.   A  block-type  special file is basically one which
         can potentially be mounted as a file  system;  a  character-
         type special file cannot, though it is not necessarily char-
         acter-oriented.  For special files  the  high  byte  of  the
         first  address  word  specifies  the type of device; the low
         byte specifies one of several devices of that type.  The de-
         vice type numbers of block and character special files over-
         lap.

         The address words of ordinary files and directories  contain
         the  numbers  of  the blocks in the file (if it is small) or
         the numbers of indirect blocks (if the file is large).  Byte
         number  n of a file is accessed as follows.  N is divided by
         512 to find its logical block number (say b ) in  the  file.
         If the file is small (flag 010000 is 0), then b must be less
         than 8, and the physical block number is addr[b].

         If the file is large, b is divided by 256 to yield i.  If  i
         is less than 7, then addr[i] is the physical block number of
         the indirect block.  The remainder from the division  yields
         the  word in the indirect block which contains the number of
         the block for the sought-for byte.

         If i is equal to 7, then the  file  has  become  extra-large
         (huge),  and  addr[7]  is  the  address  of a first indirect
         block.  Each word in this block is the number of  a  second-
         level indirect block; each word in the second-level indirect
         blocks points to a  data  block.   Notice  that  extra-large
         files are not marked by any mode bit, but only by having ad-
         dr[7] non-zero; and that although  this  scheme  allows  for
         more  than  256X256X512  =  33,554,432  bytes  per file, the
         length of files is stored in 24 bits so in practice  a  file
         can be at most 16,777,216 bytes long.

         For block b in a file to exist, it is not necessary that all
         blocks less than b exist.  A zero block number either in the
         address  words  of  the i-node or in an indirect block indi-
         cates that the corresponding block has never been allocated.
         Such  a  missing  block  reads  as  if it contained all zero
         words.

    SEE ALSO
         icheck, dcheck(VIII)

                                  - 3 -