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

     fs - format of file system volume

     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

     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-

     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

     icheck, dcheck(VIII)

                              - 3 -