Fsck - The UNIX|- File System Check Program

                   Revised July 16, 1985


                   Marshall Kirk McKusick

              Computer Systems Research Group
                 Computer Science Division
 Department of Electrical Engineering and Computer Science
             University of California, Berkeley
                    Berkeley, CA  94720


                       T. J. Kowalski

                     Bell Laboratories
               Murray Hill, New Jersey 07974


                          _A_B_S_T_R_A_C_T

          This document reflects the use of  _f_s_c_k  with
     the  4.2BSD  and  4.3BSD file system organization.
     This is a revision of the original  paper  written
     by T. J. Kowalski.

          File  System  Check  Program  (_f_s_c_k)  is   an
     interactive  file system check and repair program.
     _F_s_c_k uses the redundant structural information  in
     the  UNIX  file  system  to  perform  several con-
     sistency checks.  If an inconsistency is detected,
     it  is  reported to the operator, who may elect to
     fix or ignore each  inconsistency.   These  incon-
     sistencies  result from the permanent interruption
     of the file system updates,  which  are  performed
     every  time  a file is modified.  Unless there has
     been a hardware failure, _f_s_c_k is  able  to  repair
     corrupted file systems using procedures based upon
     the order in which UNIX honors these  file  system
     update requests.

          The purpose of this document is  to  describe
_________________________
|-UNIX is a trademark of Bell Laboratories.
This work was done under grants from the National  Sci-
ence  Foundation  under  grant MCS80-05144, and the De-
fense Advance Research Projects Agency (DoD) under Arpa
Order  No.  4031  monitored  by Naval Electronic System
Command under Contract No. N00039-82-C-0235.










                           - 2 -


     the normal updating of the file system, to discuss
     the possible causes of file system corruption, and
     to  present  the corrective actions implemented by
     _f_s_c_k.   Both  the  program  and  the   interaction
     between   the   program   and   the  operator  are
     described.

























































Fsck                       - i -                    Contents


                     _T_A_B_L_E _O_F _C_O_N_T_E_N_T_S


_1.  _I_n_t_r_o_d_u_c_t_i_o_n

9_2.  _O_v_e_r_v_i_e_w _o_f _t_h_e _f_i_l_e _s_y_s_t_e_m
 .1.    Superblock
 .2.    Summary Information
 .3.    Cylinder groups
 .4.    Fragments
 .5.    Updates to the file system

9_3.  _F_i_x_i_n_g _c_o_r_r_u_p_t_e_d _f_i_l_e _s_y_s_t_e_m_s
 .1.    Detecting and correcting corruption
 .2.    Super block checking
 .3.    Free block checking
 .4.    Checking the inode state
 .5.    Inode links
 .6.    Inode data size
 .7.    Checking the data associated with an inode
 .8.    File system connectivity

9_A_c_k_n_o_w_l_e_d_g_e_m_e_n_t_s

9_R_e_f_e_r_e_n_c_e_s

9_4.  _A_p_p_e_n_d_i_x _A
 .1.     Conventions
 .2.     Initialization
 .3.     Phase 1 - Check Blocks and Sizes
 .4.     Phase 1b - Rescan for more Dups
 .5.     Phase 2 - Check Pathnames
 .6.     Phase 3 - Check Connectivity
 .7.     Phase 4 - Check Reference Counts
 .8.     Phase 5 - Check Cyl groups
 .9.     Cleanup















9








Fsck                       - 1 -                Introduction


_1.  _I_n_t_r_o_d_u_c_t_i_o_n

     This document reflects the use of _f_s_c_k with the  4.2BSD
and  4.3BSD file system organization.  This is a revision of
the original paper written by T. J. Kowalski.

     When a UNIX operating system  is  brought  up,  a  con-
sistency  check  of  the  file systems should always be per-
formed.  This precautionary measure helps to insure a  reli-
able  environment  for  file  storage on disk.  If an incon-
sistency is discovered, corrective  action  must  be  taken.
_F_s_c_k   runs   in   two  modes.   Normally  it  is  run  non-
interactively by the system after a normal boot.  When  run-
ning  in  this  mode,  it will only make changes to the file
system that are known to always be  correct.   If  an  unex-
pected inconsistency is found _f_s_c_k will exit with a non-zero
exit status, leaving the system running single-user.   Typi-
cally  the operator then runs _f_s_c_k interactively.  When run-
ning in this mode, each problem is listed followed by a sug-
gested  corrective action.  The operator must decide whether
or not the suggested correction should be made.

     The purpose of this memo is to dispel the mystique sur-
rounding  file  system  inconsistencies.  It first describes
the updating of the file system (the calm before the  storm)
and  then  describes  file  system  corruption  (the storm).
Finally, the set of deterministic corrective actions used by
_f_s_c_k (the Coast Guard to the rescue) is presented.

_2.  _O_v_e_r_v_i_e_w _o_f _t_h_e _f_i_l_e _s_y_s_t_e_m

     The file system is discussed in detail in [Mckusick84];
this section gives a brief overview.

_2._1.  _S_u_p_e_r_b_l_o_c_k

     A file system is described  by  its  _s_u_p_e_r-_b_l_o_c_k.   The
super-block  is  built  when  the  file  system  is  created
(_n_e_w_f_s(8)) and never changes.  The super-block contains  the
basic  parameters  of the file system, such as the number of
data blocks it contains and a count of the maximum number of
files.   Because  the  super-block  contains  critical data,
_n_e_w_f_s replicates it to protect  against  catastrophic  loss.
The  _d_e_f_a_u_l_t  _s_u_p_e_r  _b_l_o_c_k  always resides at a fixed offset
from the beginning of the file system's disk partition.  The
_r_e_d_u_n_d_a_n_t  _s_u_p_e_r  _b_l_o_c_k_s  are  not  referenced unless a head
crash or other hard disk error  causes  the  default  super-
block  to  be  unusable.  The redundant blocks are sprinkled
throughout the disk partition.

     Within the file system are files.   Certain  files  are
distinguished  as  directories  and  contain  collections of
pointers to files that may themselves be directories.  Every
file  has  a  descriptor associated with it called an _i_n_o_d_e.









Fsck                       - 2 - Overview of the file system


The inode contains information describing ownership  of  the
file,  time  stamps indicating modification and access times
for the file, and an array of indices pointing to  the  data
blocks  for  the  file.  In this section, we assume that the
first 12 blocks of  the  file  are  directly  referenced  by
values stored in the inode  structure  itself|-.   The  inode
structure  may  also  contain  references to indirect blocks
containing further data block indices.   In  a  file  system
with  a  4096  byte block size, a singly indirect block con-
tains 1024 further block addresses, a doubly indirect  block
contains  1024  addresses of further single indirect blocks,
and a triply  indirect  block  contains  1024  addresses  of
further doubly indirect blocks.

     In order to create files with up to 2|^32  bytes,  using
only  two  levels of indirection, the minimum size of a file
system block is 4096 bytes.  The size of file system  blocks
can  be any power of two greater than or equal to 4096.  The
block size of the file system is maintained  in  the  super-
block, so it is possible for file systems of different block
sizes to be accessible simultaneously on  the  same  system.
The  block  size must be decided when _n_e_w_f_s creates the file
system;  the  block  size  cannot  be  subsequently  changed
without rebuilding the file system.

_2._2.  _S_u_m_m_a_r_y _i_n_f_o_r_m_a_t_i_o_n

     Associated with the super block is non replicated  _s_u_m_-
_m_a_r_y  _i_n_f_o_r_m_a_t_i_o_n.   The  summary information changes as the
file system is modified.  The summary  information  contains
the  number