path: root/ubifs-utils/fsck.ubifs/README.txt

 fsck.ubifs
 ==========
 The fsck.ubifs can check and repair the UBIFS image on a given UBI volume, it
 could fix inconsistent UBIFS image(which is corrupted by hardware exceptions
 or UBIFS realization bugs) and makes filesystem become consistent.


 Manuals
 -------
 There are four modes for fsck.ubifs:
 1. normal mode(no options): Check the filesystem, ask user whether to fix the
    problem as long as inconsistent data is found during fs checking.
 2. safe mode(-a option): Check and automatic safely repair the filesystem, if
    there are any data dropping operations needed by fixing, fsck will fail.
 3. danger mode(-y option): Answer 'yes' to all questions. There are two sub
    modes:
    a) Default submode(no options): Check and automatic repair the filesystem
       according to TNC, data dropping will be reported. If TNC/master/log is
       corrupted, fsck will fail.
    b) rebuild submode(-b option): Check and automatic forcibly repair the
       filesystem, turns to rebuild filesystem if TNC/master/log is corrupted.
       Always make fsck successful.
 4. check mode(-n option): Make no changes to the filesystem, only check the
    filesystem. This mode doesn't check space, because unclean LEBs cannot be
    rewritten in read-only mode.

 The exit code returned by fsck.ubifs is compatible with FSCK(8), which is the
 sum of the following conditions:
 0	- No errors
 1	- File system errors corrected
 2	- System should be rebooted
 4	- File system errors left uncorrected
 8	- Operational error
 16	- Usage or syntax error
 32	- Fsck canceled by user request
 128	- Shared library error


 Designment
 ----------
 There are 2 working modes for fsck: rebuild mode and non-rebuild mode. The main
 idea is that construct all files by scanning the entire filesystem, then check
 the consistency of metadata(file meta information, space statistics, etc.)
 according to the files. The file(xattr is treated as a file) is organized as:
   file tree(rbtree, inum indexed)
            /      \
         file1   file2
         /   \
      file3 file4
 file {
     inode node // each file has 1 inode node
     dentry (sub rb_tree, sqnum indexed)
     // '/' has no dentries, otherwise at least 1 dentry is required.
     trun node // the newest one truncation node
     data (sub rb_tree, block number indexed)
     // Each file may have 0 or many data nodes
     xattrs (sub rb_tree, inum indexed)
     // Each file may have 0 or many xattr files
 }

 Step 0. Both two modes need to read the superblock firstly, fsck fails if
         superblock is corrupted, because fsck has no idea about the location
         of each area(master, log, main, etc.) when the layout is lost.

 A. Rebuild mode:
 Step 1. Scan nodes(inode node/dentry node/data node/truncation node) from all
         LEBs.
         a) Corrupted LEBs(eg. garbage data, corrupted empty space) are dropped
            during scanning.
         b) Corrupted nodes(eg. incorrect crc, bad inode size, bad dentry name
            length, etc.) are dropped during scanning.
         c) Valid inode nodes(nlink > 0) and dentry nodes(inum != 0) are put
            into two valid trees(valid_inos & valid_dents) separately.
         d) Deleted inode nodes (nlink is 0) and deleted dentry nodes(inum is 0)
            are put into two deleted trees(del_inos & del_dents) separately.
         e) Other nodes(data nodes/truncation node) are put into corresponding
            file, if the file doesn't exist, insert a new file into the file
            tree.
 Step 2. Traverse nodes from deleted trees, remove inode nodes and dentry nodes
         with smaller sqnum from valid trees. valid_inos - del_inos = left_inos,
         valid_dents - del_dents = left_dents.
         This step handles the deleting case, for example, file A is deleted,
         deleted inode node and deleted dentry node are written, if we ignore
         the deleted nodes, file A can be recovered after rebuilding because
         undeleted inode node and undeleted dentry node can be scanned. There's
         an exception, if deleted inode node and deleted dentry node are
         reclaimed(by gc) after deletion, file A is recovered. So deleted data
         or files could be recovered by rebuild mode.
 Step 3. Traverse left_inos and left_dents, insert inode node and dentry nodes
         into the corresponding file.
 Step 4. Traverse all files, drop invalid files, move xattr files into the
         corresponding host file's subtree. Invalid files such as:
         a) File has no inode node or inode nlink is zero
         b) Non-consistent file types between inode node and dentry nodes
         c) File has no dentry nodes(excepts '/')
         d) Encrypted file has no xattr information
         e) Non regular file has data nodes
         f) Directory/xattr file has more than one dentries
         g) Xattr file has no host inode, or the host inode is a xattr
         h) Non-xattr file's parent is not a directory
         i) etc.
 Step 5. Extract reachable directory entries tree. Make sure that all files can
         be searched from '/', unreachable file is deleted. Since all xattr
         files are attached to the corresponding host file, only non-xattr
         files should be checked. Luckily, directory file only has one dentry,
         the reachable checking of a dentry becomes easy. Traverse all
         dentries for each file, check whether the dentry is reachable, if not,
         remove dentry from the file. If the file has no dentries, the file is
         unreachable.
 Step 6. Correct the file information. Traverse all files and calculate
         information(nlink, size, xattr_cnt, etc.) for each file just like
         check_leaf(in linux kernel) does, correct the inode node based on the
         calculated information.
 Step 7. Record used LEBs. Traverse all files'(including effective nodes from
         deletion trees in step 2) position, after this step fsck knows which
         LEB is empty.
 Step 8. Re-write data. Read data from LEB and write back data, make sure that
         all LEB is ended with empty data(0xFF). It will prevent failed gc
         scanning in the next mounting.
 Step 9. Build TNC. Construct TNC according to all files' nodes, just like mkfs
         does(refer to add_to_index in mkfs), then write TNC(refer to
         write_index in mkfs) on flash. (If there are no files, create a new
         root dir file.)
 Step 10.Build LPT. Construct LPT according to all nodes' position and length,
         just like mkfs does, then write LPT(refer to write_lpt) on flash.
 Step 11.Clean up log area and orphan area. Log area and orphan area can be
         erased.
 Step 12.Write master node. Since all meta areas are ready, master node can be
         updated.

 B. Non-rebuild mode:
 Step 1. Read master & init lpt.
         a) Scan master nodes failed or master node is invalid (which is not
            caused by invalid space statistics), danger mode with rebuild_fs and
            normal mode with 'yes' answer will turn to rebuild mode, other modes
            will exit. Fsck cannot find the right TNC/LPT if the master node is
            invalid, which affects subsequent steps, so this problem must be
            fixed.
         b) Invalid space statistics in master node, set %FR_LPT_INCORRECT for
            for lpt status and ignore the error.
         c) LPT node is corrupted, set %FR_LPT_CORRUPTED for lpt status and
            ignore the error.
 Step 2. Replay journal.
         I. Scan log LEBs to get all buds.
            a) Nodes in log LEBs are invalid/corrupted, danger mode with
               rebuild_fs and normal mode with 'yes' answer will turn to rebuild
               mode, other modes will exit. Corrupted log LEB could fail
               ubifs_consolidate_log, which may lead to commit failure by out of
	       space in the log area, so this problem must be fixed.
         II. Scan bud LEBs to get all nodes.
             a) Nodes in bud LEBs are invalid/corrupted, danger mode and normal
                mode with 'yes' answer will drop bud LEB and set
                %FR_LPT_INCORRECT for lpt status, other modes will exit.
                Corrupted LEB will make gc failed, so this problem must be
                fixed.
	 III. Record isize into size tree according to data/truncation/inode
              nodes.
         IV. Apply nodes to TNC & LPT, update property for bud LEBs.
             a) Corrupted/Invalid node searched from TNC, skip node and set
                %FR_LPT_INCORRECT in lpt status for danger mode and normal mode
                with 'yes' answer, other modes will exit. The space statistics
                depend on a valid TNC, so this problem must be fixed.
             b) Corrupted/Invalid index node read from TNC, danger mode with
                rebuild_fs and normal mode with 'yes' answer will turn to
                rebuild filesystem, other modes will exit. The space statistics
                depend on a valid TNC, so this problem must be fixed.
             c) Corrupted/Invalid lpt node, Set %FR_LPT_CORRUPTED for lpt status
                and ignore the error.
             d) Incorrect LEB property: Set %FR_LPT_INCORRECT for lpt status and
                ignore the error.
             e) If lpt status is not empty, skip updating lpt, because incorrect
                LEB property could trigger assertion failure in ubifs_change_lp.
 Step 3. Handle orphan nodes.
         I. Scan orphan LEB to get all orphan nodes.
            a) Corrupted/Invalid orphan node: danger mode and normal mode with
               'yes' answer will drop orphan LEB, other modes will exit.
               Corrupted orphan area could lead to mounting/committing failure,
               so this problem must be fixed.
         II. Parse orphan node, find the original inode for each inum.
             a) Corrupted/Invalid node searched from TNC, skip node for danger
                mode and normal mode with 'yes' answer, other modes will exit.
             b) Corrupted/Invalid index node read from TNC, danger mode with
                rebuild_fs and normal mode with 'yes' answer will turn to
                rebuild filesystem, other modes will exit. The space statistics
                depend on a valid TNC, so this problem must be fixed.
         III. Remove inode for each inum, update TNC & LPT.
              a) Corrupted/Invalid node searched from TNC, skip node for danger
                 mode and normal mode with 'yes' answer, other modes will exit.
              b) Corrupted/Invalid index node read from TNC, danger mode with
                 rebuild_fs and normal mode with 'yes' answer will turn to
                 rebuild filesystem, other modes will exit. The space statistics
                 depend on a valid TNC, so this problem must be fixed.
              c) Corrupted/Invalid lpt node, Set %FR_LPT_CORRUPTED for lpt
                 status and ignore the error.
              d) Incorrect LEB property: Set %FR_LPT_INCORRECT for lpt status
                 and ignore the error.
              e) If lpt status is not empty, skip updating lpt, because
                 incorrect LEB property could trigger assertion failure in
                 ubifs_change_lp.
 Step 4. Consolidate log area.
         a) Corrupted data in log LEBs, danger mode with rebuild_fs and normal
            mode with 'yes' answer will turn to rebuild filesystem, other modes
            will exit. It could make commit failed by out of space in log area,
            so this problem must be fixed.
 Step 5. Recover isize.
         I. Traverse size tree, lookup corresponding inode from TNC.
            a) Corrupted/Invalid node searched from TNC, skip node for danger
               mode and normal mode with 'yes' answer, other modes will exit.
            b) Corrupted/Invalid index node read from TNC, danger mode with
               rebuild_fs and normal mode with 'yes' answer will turn to
               rebuild filesystem, other modes will exit. The space statistics
               depend on a valid TNC, so this problem must be fixed.
         II. Update isize for inode. Keep <inum, isize> in size tree for check
             mode, remove <inum, isize> from the size tree and update inode
             node in place for other modes.
 Step 6. Traverse TNC and construct files.
         I. Traverse TNC, check whether the leaf node is valid, remove invalid
            nodes, construct file for valid node and insert the file into the
            file tree.
            a) Corrupted/Invalid node searched from TNC, remove corresponding
               TNC branch for danger mode and normal mode with 'yes' answer,
               other modes will exit. The space statistics depend on a valid
               TNC, so this problem must be fixed.
            b) Corrupted/Invalid index node read from TNC, danger mode with
               rebuild_fs and normal mode with 'yes' answer will turn to
               rebuild filesystem, other modes will exit. The space statistics
               depend on a valid TNC, so this problem must be fixed.
         II. Scan all LEBs(contain TNC) for non check mode(unclean LEBs cannot
             be fixed in read-only mode, so scanning may fail in check mode,
             then space statistics won't be checked in check mode), remove TNC
             branch which points to corrupted LEB.
             a) Corrupted data is found by scanning. If the current node is
                index node, danger mode with rebuild_fs and normal mode with
                'yes' answer will turn to rebuild filesystem, other modes will
                exit; If the current node is non-index node, danger mode and
                normal mode with 'yes' answer will remove all TNC branches which
                point to the corrupted LEB, other modes will exit. The space
                statistics depend on valid LEB scanning, so this problem must
                be fixed.
             b) LEB contains both index and non-index nodes, danger mode with
                rebuild_fs and normal mode with 'yes' answer will turn to
                rebuild filesystem, other modes will exit. Invalid LEB will make
                gc failed, so this problem must be fixed.
 Step 7. Update files' size for check mode. Update files' size according to the
          size tree for check mode.
 Step 8. Check and handle invalid files. Similar to rebuild mode, but the
         methods of handling are different:
         a) Move unattached(file has no dentries) regular file into disconnected
            list for safe mode, danger mode and normal mode with 'yes' answer,
            let subsequent steps to handle them with lost+found. Other modes
            will exit. Disconnected file affects the result of calculated
            information(which will be used in subsequent steps) for its' parent
            file(eg. nlink, size), so this problem must be fixed.
         b) Make file type be consistent between inode, detries and data nodes
            by deleting dentries or data nodes, for danger mode and normal mode
            with 'yes' answer, other modes will exit.
         c) Delete file for other invalid cases(eg. file has no inode) in
            danger mode and normal mode with 'yes' answer, other modes will
            exit.
 Step 9. Extract reachable directory entries tree. Similar to rebuild mode, but
         the methods of handling are different:
         a) Remove unreachable dentry for danger mode and normal mode with 'yes'
            answer, other modes will exit. Unreachable dentry affects the
            calculated information(which will be used in subsequent steps) for
            its' file(eg. nlink), so this problem must be fixed.
         b) Delete unreachable non-regular file for danger mode and normal mode
            with 'yes' answer, other modes will exit. Unreachable file affects
            the calculated information(which will be used in subsequent steps)
            for its' parent file(eg. nlink, size), so this problem must be
            fixed.
         c) Move unreachable regular file into disconnected list for safe mode,
            danger mode and normal mode with 'yes' answer, let subsequent steps
            to handle them with lost+found. Other modes will exit. Disconnected
            file affects the calculated information(which will be used in
            subsequent steps) for its' parent file(eg. nlink, size), so this
            problem must be fixed.
 Step 10.Correct the file information. Similar to rebuild mode, but the methods
         of handling are different:
         a) Correct the file information for safe mode, danger mode and normal
            mode with 'yes' answer, other modes will exit. Incorrect file
            information affects the new creations(which will be used in handling
            lost+found), so this problem must be fixed.
 Step 11.Check whether the TNC is empty. Empty TNC is equal to corrupted TNC,
         which means that zero child count for root znode. If TNC is empty(All
         nodes are invalid and are deleted from TNC), turn to rebuild mode for
         danger mode with rebuild_fs and normal mode with 'yes' answer, other
         modes will exit.
 Step 12.Check and correct the space statistics.
         I. Exit for check mode, if %FR_LPT_CORRUPTED or %FR_LPT_INCORRECT is
            set in lpt status, the exit code should have %FSCK_UNCORRECTED.
         II. Check lpt status, if %FR_LPT_CORRUPTED is set in lpt status, normal
             mode with 'no' answer will exit, other modes will rebuild lpt. New
             creations could be done in subsequent steps, which depends on
             correct space statistics, so this problem must be fixed.
         III. Traverse LPT nodes, check the correctness of nnode and pnode,
              compare LEB scanning result with LEB properties.
              a) LPT node is corrupted, normal mode with 'no' answer will exit,
                 rebuild lpt for other modes. New creations could be done in
                 subsequent steps, which depends on the correct space
                 statistics, so this problem must be fixed.
              b) Incorrect nnode/pnode, normal mode with 'no' answer will exit,
                 other modes will correct the nnode/pnode. New creations could
                 be done in subsequent steps, which depends on correct space
                 statistics, so this problem must be fixed.
              c) Inconsistent comparing result, normal mode with 'no' answer
                 will exit, other modes will correct the space statistics. New
                 creations could be done in subsequent steps, which depends on
                 correct space statistics, so this problem must be fixed.
         IV. Compare LPT area scanning result with lprops table information.
             a) LPT area is corrupted, normal mode with 'no' answer will exit,
                rebuild lpt for other modes. Commit could fail in doing LPT gc
                caused by scanning corrupted data, so this problem must be
                fixed.
             b) Inconsistent comparing result, normal mode with 'no' answer
                will exit, other modes will correct the lprops table
                information. Commit could fail in writing LPT with %ENOSPC
                return code caused by incorrect space statistics in the LPT
                area, so this problem must be fixed.
 Step 13.Do commit, commit problem fixing modifications to disk. The index size
         checking depends on this step.
 Step 14.Check and correct the index size. Check and correct the index size by
         traversing TNC just like dbg_check_idx_size does. This step should be
         executed after first committing, because 'c->calc_idx_sz' can be
         changed in 'ubifs_tnc_start_commit' and the initial value of
         'c->calc_idx_sz' read from the disk is untrusted. Correct the index
         size for safe mode, danger mode and normal mode with 'yes' answer,
         other modes will exit. New creations could be done in subsequent steps,
         which depends on the correct index size, so this problem must be fixed.
 Step 15.Check and create the root dir. Check whether the root dir exists,
         create a new one if it is not found, for safe mode, danger mode and
         normal mode with 'yes' answer, other modes will exit. Mounting depends
         on the root dir, so this problem must be fixed.
 Step 16.Check and create the lost+found.
         I. If the root dir is encrypted, set lost+found as invalid. Because it
            is impossible to check whether the lost+found exists in an encrypted
            directory.
         II. Search the lost+found under root dir.
             a) Found a lost+found, lost+found is a non-encrypted directory, set
                lost+found as valid, otherwise set lost+found as invalid.
             b) Not found the lost+found, create a new one. If creation is
                failed by %ENOSPC, set lost+found as invalid.
 Step 17.Handle each file from the disconnected list.
         I. If lost+found is invalid, delete file for danger mode and normal
            mode with 'yes' answer, other modes will skip and set the exit code
            with %FSCK_UNCORRECTED.
        II. If lost+found is valid, link disconnected file under lost+found
            directory with the name of the corresponding inode number
            (INO_<inum>_<index>, index(starts from 0) is used to handle the
             conflicted names).
             a) Fails in handling conflicted file names, delete file for danger
                mode and normal mode with 'yes' answer, other modes will skip
                and set the exit code with %FSCK_UNCORRECTED.
             b) Fails in linking caused by %ENOSPC, delete file for danger mode
                and normal mode with 'yes' answer, other modes will skip and set
                the exit code with %FSCK_UNCORRECTED.
 Step 18.Do final commit, commit problem fixing modifications to disk and clear
         %UBIFS_MST_DIRTY flag for master node.


 Advantage
 ---------
 1. Can be used for any UBIFS image, fsck has nothing to do with kernel version.
 2. Fsck is tolerant with power-cut, fsck will always succeed in a certain mode
    without changing mode even power-cut happens in checking and repairing. In
    other words, fsck won't let UBIFS image become worse in abnormal situations.
 3. It is compatible with FSCK(8), the exit code returned by fsck.ubifs is same
    as FSCK, the command options used by fsck are supported in fsck.ubifs too.
 4. The UBIFS image can be fixed as long as the super block is not corrupted.
 5. Encrypted UBIFS image is supported, because dentry name and data content of
    file are not necessary for fsck.


 Limitations
 -----------
 1. UBIFS image file is not supported(Not like ext4). The UBIFS image file is
    not equal to UBI volume, empty LEBs are not included in image file, so UBIFS
    cannot allocate empty space when file recovering is needed. Another reason
    is that atomic LEB changing is not supported by image file.
 2. Authenticated UBIFS image is not supported, UBIFS metadata(TNC/LPT) parsing
    depends on the authentication key which is not supported in fsck options.


 Authors
 -------
 Zhihao Cheng <chengzhihao1@huawei.com>
 Zhang Yi <yi.zhang@huawei.com>
 Xiang Yang <xiangyang3@huawei.com>
 Huang Xiaojia <huangxiaojia2@huawei.com>