diff options
Diffstat (limited to 'ubifs-utils/fsck.ubifs')
| -rw-r--r-- | ubifs-utils/fsck.ubifs/.gitignore | 1 | ||||
| -rw-r--r-- | ubifs-utils/fsck.ubifs/README.txt | 388 | ||||
| -rw-r--r-- | ubifs-utils/fsck.ubifs/check_files.c | 555 | ||||
| -rw-r--r-- | ubifs-utils/fsck.ubifs/check_space.c | 690 | ||||
| -rw-r--r-- | ubifs-utils/fsck.ubifs/extract_files.c | 1574 | ||||
| -rw-r--r-- | ubifs-utils/fsck.ubifs/fsck.ubifs.c | 636 | ||||
| -rw-r--r-- | ubifs-utils/fsck.ubifs/fsck.ubifs.h | 392 | ||||
| -rw-r--r-- | ubifs-utils/fsck.ubifs/handle_disconnected.c | 197 | ||||
| -rw-r--r-- | ubifs-utils/fsck.ubifs/load_fs.c | 261 | ||||
| -rw-r--r-- | ubifs-utils/fsck.ubifs/problem.c | 377 | ||||
| -rw-r--r-- | ubifs-utils/fsck.ubifs/rebuild_fs.c | 1453 |
11 files changed, 6524 insertions, 0 deletions
diff --git a/ubifs-utils/fsck.ubifs/.gitignore b/ubifs-utils/fsck.ubifs/.gitignore new file mode 100644 index 0000000..09d664a --- /dev/null +++ b/ubifs-utils/fsck.ubifs/.gitignore @@ -0,0 +1 @@ +/fsck.ubifs diff --git a/ubifs-utils/fsck.ubifs/README.txt b/ubifs-utils/fsck.ubifs/README.txt new file mode 100644 index 0000000..a4daae7 --- /dev/null +++ b/ubifs-utils/fsck.ubifs/README.txt @@ -0,0 +1,388 @@ + 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> diff --git a/ubifs-utils/fsck.ubifs/check_files.c b/ubifs-utils/fsck.ubifs/check_files.c new file mode 100644 index 0000000..1e1a77b --- /dev/null +++ b/ubifs-utils/fsck.ubifs/check_files.c @@ -0,0 +1,555 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2024, Huawei Technologies Co, Ltd. + * + * Authors: Zhihao Cheng <chengzhihao1@huawei.com> + */ + +#include <stdio.h> +#include <stdlib.h> +#include <sys/stat.h> + +#include "linux_err.h" +#include "bitops.h" +#include "kmem.h" +#include "ubifs.h" +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "fsck.ubifs.h" + +struct invalid_node { + union ubifs_key key; + int lnum; + int offs; + struct list_head list; +}; + +struct iteration_info { + struct list_head invalid_nodes; + unsigned long *corrupted_lebs; +}; + +static int add_invalid_node(struct ubifs_info *c, union ubifs_key *key, + int lnum, int offs, struct iteration_info *iter) +{ + struct invalid_node *in; + + in = kmalloc(sizeof(struct invalid_node), GFP_KERNEL); + if (!in) { + log_err(c, errno, "can not allocate invalid node"); + return -ENOMEM; + } + + key_copy(c, key, &in->key); + in->lnum = lnum; + in->offs = offs; + list_add(&in->list, &iter->invalid_nodes); + + return 0; +} + +static int construct_file(struct ubifs_info *c, union ubifs_key *key, + int lnum, int offs, void *node, + struct iteration_info *iter) +{ + ino_t inum = 0; + struct rb_root *tree = &FSCK(c)->scanned_files; + struct scanned_node *sn = NULL; + struct ubifs_ch *ch = (struct ubifs_ch *)node; + + switch (ch->node_type) { + case UBIFS_INO_NODE: + { + struct scanned_ino_node ino_node; + + if (!parse_ino_node(c, lnum, offs, node, key, &ino_node)) { + if (fix_problem(c, INVALID_INO_NODE, NULL)) + return add_invalid_node(c, key, lnum, offs, iter); + } + inum = key_inum(c, key); + sn = (struct scanned_node *)&ino_node; + break; + } + case UBIFS_DENT_NODE: + case UBIFS_XENT_NODE: + { + struct scanned_dent_node dent_node; + + if (!parse_dent_node(c, lnum, offs, node, key, &dent_node)) { + if (fix_problem(c, INVALID_DENT_NODE, NULL)) + return add_invalid_node(c, key, lnum, offs, iter); + } + inum = dent_node.inum; + sn = (struct scanned_node *)&dent_node; + break; + } + case UBIFS_DATA_NODE: + { + struct scanned_data_node data_node; + + if (!parse_data_node(c, lnum, offs, node, key, &data_node)) { + if (fix_problem(c, INVALID_DATA_NODE, NULL)) + return add_invalid_node(c, key, lnum, offs, iter); + } + inum = key_inum(c, key); + sn = (struct scanned_node *)&data_node; + break; + } + default: + ubifs_assert(c, 0); + } + + dbg_fsck("construct file(%lu) for %s node, TNC location %d:%d, in %s", + inum, ubifs_get_key_name(key_type(c, key)), sn->lnum, sn->offs, + c->dev_name); + return insert_or_update_file(c, tree, sn, key_type(c, key), inum); +} + +static int scan_check_leb(struct ubifs_info *c, int lnum, bool is_idx) +{ + int err = 0; + struct ubifs_scan_leb *sleb; + struct ubifs_scan_node *snod; + + if (FSCK(c)->mode == CHECK_MODE) + /* Skip check mode. */ + return 0; + + ubifs_assert(c, lnum >= c->main_first); + if (test_bit(lnum - c->main_first, FSCK(c)->used_lebs)) + return 0; + + sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0); + if (IS_ERR(sleb)) { + err = PTR_ERR(sleb); + if (test_and_clear_failure_reason_callback(c, FR_DATA_CORRUPTED)) + err = 1; + return err; + } + + list_for_each_entry(snod, &sleb->nodes, list) { + if (is_idx) { + if (snod->type != UBIFS_IDX_NODE) { + err = 1; + goto out; + } + } else { + if (snod->type == UBIFS_IDX_NODE) { + err = 1; + goto out; + } + } + } + + set_bit(lnum - c->main_first, FSCK(c)->used_lebs); + +out: + ubifs_scan_destroy(sleb); + return err; +} + +static int check_leaf(struct ubifs_info *c, struct ubifs_zbranch *zbr, + void *priv) +{ + void *node; + struct iteration_info *iter = (struct iteration_info *)priv; + union ubifs_key *key = &zbr->key; + int lnum = zbr->lnum, offs = zbr->offs, len = zbr->len, err = 0; + + if (len < UBIFS_CH_SZ) { + ubifs_err(c, "bad leaf length %d (LEB %d:%d)", + len, lnum, offs); + set_failure_reason_callback(c, FR_TNC_CORRUPTED); + return -EINVAL; + } + if (key_type(c, key) != UBIFS_INO_KEY && + key_type(c, key) != UBIFS_DATA_KEY && + key_type(c, key) != UBIFS_DENT_KEY && + key_type(c, key) != UBIFS_XENT_KEY) { + ubifs_err(c, "bad key type %d (LEB %d:%d)", + key_type(c, key), lnum, offs); + set_failure_reason_callback(c, FR_TNC_CORRUPTED); + return -EINVAL; + } + + if (test_bit(lnum - c->main_first, iter->corrupted_lebs)) { + if (fix_problem(c, SCAN_CORRUPTED, zbr)) + /* All nodes in corrupted LEB should be removed. */ + return add_invalid_node(c, key, lnum, offs, iter); + return 0; + } + + err = scan_check_leb(c, lnum, false); + if (err < 0) { + return err; + } else if (err) { + set_bit(lnum - c->main_first, iter->corrupted_lebs); + if (fix_problem(c, SCAN_CORRUPTED, zbr)) + return add_invalid_node(c, key, lnum, offs, iter); + return 0; + } + + node = kmalloc(len, GFP_NOFS); + if (!node) + return -ENOMEM; + + err = ubifs_tnc_read_node(c, zbr, node); + if (err) { + if (test_and_clear_failure_reason_callback(c, FR_DATA_CORRUPTED)) { + if (fix_problem(c, TNC_DATA_CORRUPTED, NULL)) + err = add_invalid_node(c, key, lnum, offs, iter); + } + goto out; + } + + err = construct_file(c, key, lnum, offs, node, iter); + +out: + kfree(node); + return err; +} + +static int check_znode(struct ubifs_info *c, struct ubifs_znode *znode, + __unused void *priv) +{ + int err; + const struct ubifs_zbranch *zbr; + + if (znode->parent) + zbr = &znode->parent->zbranch[znode->iip]; + else + zbr = &c->zroot; + + if (zbr->lnum == 0) { + /* The znode has been split up. */ + ubifs_assert(c, zbr->offs == 0 && zbr->len == 0); + return 0; + } + + err = scan_check_leb(c, zbr->lnum, true); + if (err < 0) { + return err; + } else if (err) { + set_failure_reason_callback(c, FR_TNC_CORRUPTED); + return -EINVAL; + } + + return 0; +} + +static int remove_invalid_nodes(struct ubifs_info *c, + struct list_head *invalid_nodes, int error) +{ + int ret = 0;; + struct invalid_node *in; + + while (!list_empty(invalid_nodes)) { + in = list_entry(invalid_nodes->next, struct invalid_node, list); + + if (!error) { + error = ubifs_tnc_remove_node(c, &in->key, in->lnum, in->offs); + if (error) { + /* TNC traversing is finished, any TNC path is accessible */ + ubifs_assert(c, !get_failure_reason_callback(c)); + ret = error; + } + } + + list_del(&in->list); + kfree(in); + } + + return ret; +} + +/** + * traverse_tnc_and_construct_files - traverse TNC and construct all files. + * @c: UBIFS file-system description object + * + * This function does two things by traversing TNC: + * 1. Check all index nodes and non-index nodes, then construct file according + * to scanned non-index nodes and insert file into file tree. + * 2. Make sure that LEB(contains any nodes from TNC) can be scanned by + * ubifs_scan, and the LEB only contains index nodes or non-index nodes. + * Returns zero in case of success, a negative error code in case of failure. + */ +int traverse_tnc_and_construct_files(struct ubifs_info *c) +{ + int err, ret; + struct iteration_info iter; + + FSCK(c)->scanned_files = RB_ROOT; + FSCK(c)->used_lebs = kcalloc(BITS_TO_LONGS(c->main_lebs), + sizeof(unsigned long), GFP_KERNEL); + if (!FSCK(c)->used_lebs) { + err = -ENOMEM; + log_err(c, errno, "can not allocate bitmap of used lebs"); + return err; + } + INIT_LIST_HEAD(&iter.invalid_nodes); + iter.corrupted_lebs = kcalloc(BITS_TO_LONGS(c->main_lebs), + sizeof(unsigned long), GFP_KERNEL); + if (!iter.corrupted_lebs) { + err = -ENOMEM; + log_err(c, errno, "can not allocate bitmap of corrupted lebs"); + goto out; + } + + err = dbg_walk_index(c, check_leaf, check_znode, &iter); + + ret = remove_invalid_nodes(c, &iter.invalid_nodes, err); + if (!err) + err = ret; + + kfree(iter.corrupted_lebs); +out: + if (err) { + kfree(FSCK(c)->used_lebs); + destroy_file_tree(c, &FSCK(c)->scanned_files); + } + return err; +} + +/** + * update_files_size - Update files' size. + * @c: UBIFS file-system description object + * + * This function updates files' size according to @c->size_tree for check mode. + */ +void update_files_size(struct ubifs_info *c) +{ + struct rb_node *this; + + if (FSCK(c)->mode != CHECK_MODE) { + /* Other modes(rw) have updated inode size in place. */ + dbg_fsck("skip updating files' size%s, in %s", + mode_name(c), c->dev_name); + return; + } + + log_out(c, "Update files' size"); + + this = rb_first(&c->size_tree); + while (this) { + struct size_entry *e; + + e = rb_entry(this, struct size_entry, rb); + this = rb_next(this); + + if (e->exists && e->i_size < e->d_size) { + struct scanned_file *file; + + file = lookup_file(&FSCK(c)->scanned_files, e->inum); + if (file && file->ino.header.exist && + file->ino.size < e->d_size) { + dbg_fsck("update file(%lu) size %llu->%llu, in %s", + e->inum, file->ino.size, + (unsigned long long)e->d_size, + c->dev_name); + file->ino.size = e->d_size; + } + } + + rb_erase(&e->rb, &c->size_tree); + kfree(e); + } +} + +/** + * handle_invalid_files - Handle invalid files. + * @c: UBIFS file-system description object + * + * This function checks and handles invalid files, there are three situations: + * 1. Move unattached(file has no dentries, or file's parent file has invalid + * type) regular file into disconnected list, let subsequent steps to handle + * them with lost+found. + * 2. Make file type be consistent between inode, detries and data nodes by + * deleting dentries or data blocks. + * 3. Delete file for other invalid cases(eg. file has no inode). + * + * Returns zero in case of success, a negative error code in case of failure. + */ +int handle_invalid_files(struct ubifs_info *c) +{ + int err; + struct rb_node *node; + struct scanned_file *file; + struct rb_root *tree = &FSCK(c)->scanned_files; + LIST_HEAD(tmp_list); + + /* Add all xattr files into a list. */ + for (node = rb_first(tree); node; node = rb_next(node)) { + file = rb_entry(node, struct scanned_file, rb); + + if (file->ino.is_xattr) + list_add(&file->list, &tmp_list); + } + + /* + * Round 1: Traverse xattr files, check whether the xattr file is + * valid, move valid xattr file into corresponding host file's subtree. + */ + while (!list_empty(&tmp_list)) { + file = list_entry(tmp_list.next, struct scanned_file, list); + + list_del(&file->list); + rb_erase(&file->rb, tree); + err = file_is_valid(c, file, tree, NULL); + if (err < 0) { + destroy_file_content(c, file); + kfree(file); + return err; + } else if (!err) { + err = delete_file(c, file); + kfree(file); + if (err) + return err; + } + } + + /* Round 2: Traverse non-xattr files. */ + for (node = rb_first(tree); node; node = rb_next(node)) { + int is_diconnected = 0; + + file = rb_entry(node, struct scanned_file, rb); + err = file_is_valid(c, file, tree, &is_diconnected); + if (err < 0) { + return err; + } else if (!err) { + if (is_diconnected) + list_add(&file->list, &FSCK(c)->disconnected_files); + else + list_add(&file->list, &tmp_list); + } + } + + /* Delete & remove invalid files. */ + while (!list_empty(&tmp_list)) { + file = list_entry(tmp_list.next, struct scanned_file, list); + + list_del(&file->list); + err = delete_file(c, file); + if (err) + return err; + rb_erase(&file->rb, tree); + kfree(file); + } + + /* Remove disconnected file from the file tree. */ + list_for_each_entry(file, &FSCK(c)->disconnected_files, list) { + rb_erase(&file->rb, tree); + } + + return 0; +} + +/** + * handle_dentry_tree - Handle unreachable dentries and files. + * @c: UBIFS file-system description object + * + * This function iterates all directory entries and remove those unreachable + * ones. If file has no directory entries, it becomes unreachable: + * 1. If the unreachable file has non-regular type, delete it; + * 2. If the unreachable file has regular type, move it into the + * @FSCK(c)->disconnected_files. + * 'Unreachable' means that a directory entry can not be searched from '/'. + * + * Returns zero in case of success, a negative error code in case of failure. + */ +int handle_dentry_tree(struct ubifs_info *c) +{ + struct rb_node *node; + struct scanned_file *file; + struct rb_root *tree = &FSCK(c)->scanned_files; + LIST_HEAD(unreachable); + + for (node = rb_first(tree); node; node = rb_next(node)) { + file = rb_entry(node, struct scanned_file, rb); + + /* + * Since all xattr files are already attached to corresponding + * host file, there are only non-xattr files in the file tree. + */ + ubifs_assert(c, !file->ino.is_xattr); + if (!file_is_reachable(c, file, tree)) + list_add(&file->list, &unreachable); + } + + while (!list_empty(&unreachable)) { + file = list_entry(unreachable.next, struct scanned_file, list); + + list_del(&file->list); + if (S_ISREG(file->ino.mode)) { + /* + * Move regular type unreachable file into the + * @FSCK(c)->disconnected_files. + */ + list_add(&file->list, &FSCK(c)->disconnected_files); + rb_erase(&file->rb, tree); + } else { + /* Delete non-regular type unreachable file. */ + int err = delete_file(c, file); + if (err) + return err; + rb_erase(&file->rb, tree); + kfree(file); + } + } + + return 0; +} + +/** + * tnc_is_empty - Check whether the TNC is empty. + * @c: UBIFS file-system description object + * + * Returns %true if the TNC is empty, otherwise %false is returned. + */ +bool tnc_is_empty(struct ubifs_info *c) +{ + /* + * Check whether the TNC is empty, turn to rebuild_fs if it is empty. + * Can we recreate a new root dir to avoid empty TNC? The answer is no, + * lpt fixing should be done before creating new entry, but lpt fixing + * needs a committing before new dirty data generated to ensure that + * bud data won't be overwritten(bud LEB could become freeable after + * replaying journal, corrected lpt may treat it as a free one to hold + * new data, see details in space checking & correcting step). Then we + * have to create the new root dir after fixing lpt and a committing, + * znode without children(empty TNC) maybe written on disk at the + * moment of committing, which corrupts the UBIFS image. So we choose + * to rebuild the filesystem if the TNC is empty, this case is + * equivalent to corrupted TNC. + */ + return c->zroot.znode->child_cnt == 0; +} + +/** + * check_and_create_root - Check and create root dir. + * @c: UBIFS file-system description object + * + * This function checks whether the root dir is existed, create a new root + * dir if it doesn't exist. Returns zero in case of success, a negative error + * code in case of failure. + */ +int check_and_create_root(struct ubifs_info *c) +{ + int err; + struct ubifs_inode *ui = ubifs_lookup_by_inum(c, UBIFS_ROOT_INO); + + if (!IS_ERR(ui)) { + /* The root dir is found. */ + dbg_fsck("root dir is found, in %s", c->dev_name); + kfree(ui); + return 0; + } + + err = PTR_ERR(ui); + if (err != -ENOENT) + return err; + + fix_problem(c, ROOT_DIR_NOT_FOUND, NULL); + dbg_fsck("root dir is lost, create a new one, in %s", c->dev_name); + return ubifs_create_root(c); +} diff --git a/ubifs-utils/fsck.ubifs/check_space.c b/ubifs-utils/fsck.ubifs/check_space.c new file mode 100644 index 0000000..cff8a7c --- /dev/null +++ b/ubifs-utils/fsck.ubifs/check_space.c @@ -0,0 +1,690 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2024, Huawei Technologies Co, Ltd. + * + * Authors: Zhihao Cheng <chengzhihao1@huawei.com> + */ + +#include <stdio.h> +#include <stdlib.h> + +#include "linux_err.h" +#include "bitops.h" +#include "kmem.h" +#include "ubifs.h" +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "misc.h" +#include "fsck.ubifs.h" + +/** + * get_free_leb - get a free LEB according to @FSCK(c)->used_lebs. + * @c: UBIFS file-system description object + * + * This function tries to find a free LEB, lnum is returned if found, otherwise + * %-ENOSPC is returned. + */ +int get_free_leb(struct ubifs_info *c) +{ + int lnum; + + lnum = find_next_zero_bit(FSCK(c)->used_lebs, c->main_lebs, 0); + if (lnum >= c->main_lebs) { + ubifs_err(c, "No space left."); + return -ENOSPC; + } + set_bit(lnum, FSCK(c)->used_lebs); + lnum += c->main_first; + + return lnum; +} + +/** + * build_lpt - construct LPT and write it into flash. + * @c: UBIFS file-system description object + * @calculate_lp_cb: callback function to calculate the properties for given LEB + * @free_ltab: %true means to release c->ltab after creating lpt + * + * This function builds LPT according to the calculated results by + * @calculate_lp_cb and writes LPT into flash. Returns zero in case of success, + * a negative error code in case of failure. + */ +int build_lpt(struct ubifs_info *c, calculate_lp_callback calculate_lp_cb, + bool free_ltab) +{ + int i, err, lnum, free, dirty; + u8 hash_lpt[UBIFS_HASH_ARR_SZ]; + + memset(&c->lst, 0, sizeof(struct ubifs_lp_stats)); + /* Set gc lnum, equivalent to ubifs_rcvry_gc_commit/take_gc_lnum. */ + lnum = get_free_leb(c); + if (lnum < 0) + return lnum; + c->gc_lnum = lnum; + + /* Update LPT. */ + for (i = 0; i < c->main_lebs; i++) { + err = calculate_lp_cb(c, i, &free, &dirty, NULL); + if (err) + return err; + + FSCK(c)->lpts[i].free = free; + FSCK(c)->lpts[i].dirty = dirty; + c->lst.total_free += free; + c->lst.total_dirty += dirty; + + if (free == c->leb_size) + c->lst.empty_lebs++; + + if (FSCK(c)->lpts[i].flags & LPROPS_INDEX) { + c->lst.idx_lebs += 1; + } else { + int spc; + + spc = free + dirty; + if (spc < c->dead_wm) + c->lst.total_dead += spc; + else + c->lst.total_dark += ubifs_calc_dark(c, spc); + c->lst.total_used += c->leb_size - spc; + } + + dbg_fsck("build properties for LEB %d, free %d dirty %d is_idx %d, in %s", + i + c->main_first, free, dirty, + FSCK(c)->lpts[i].flags & LPROPS_INDEX ? 1 : 0, + c->dev_name); + } + + /* Write LPT. */ + return ubifs_create_lpt(c, FSCK(c)->lpts, c->main_lebs, hash_lpt, free_ltab); +} + +static int scan_get_lp(struct ubifs_info *c, int index, int *free, int *dirty, + int *is_idx) +{ + struct ubifs_scan_leb *sleb; + struct ubifs_scan_node *snod; + int used, idx_leb, lnum = index + c->main_first, err = 0; + bool is_build_lpt = FSCK(c)->lpt_status & FR_LPT_CORRUPTED; + + if (is_build_lpt) { + if (!test_bit(index, FSCK(c)->used_lebs) || c->gc_lnum == lnum) { + *free = c->leb_size; + *dirty = 0; + return 0; + } + } else { + if (!test_bit(index, FSCK(c)->used_lebs)) { + *free = c->leb_size; + *dirty = 0; + return 0; + } + } + + sleb = ubifs_scan(c, lnum, 0, c->sbuf, 0); + if (IS_ERR(sleb)) { + /* All TNC LEBs have passed ubifs_scan in previous steps. */ + ubifs_assert(c, !get_failure_reason_callback(c)); + return PTR_ERR(sleb); + } + + idx_leb = -1; + used = 0; + list_for_each_entry(snod, &sleb->nodes, list) { + int found, level = 0; + + if (idx_leb == -1) + idx_leb = (snod->type == UBIFS_IDX_NODE) ? 1 : 0; + + if (idx_leb) + /* + * Previous steps have ensured that every TNC LEB + * contains only index nodes or non-index nodes. + */ + ubifs_assert(c, snod->type == UBIFS_IDX_NODE); + + if (snod->type == UBIFS_IDX_NODE) { + struct ubifs_idx_node *idx = snod->node; + + key_read(c, ubifs_idx_key(c, idx), &snod->key); + level = le16_to_cpu(idx->level); + } + + found = ubifs_tnc_has_node(c, &snod->key, level, lnum, + snod->offs, idx_leb); + if (found) { + if (found < 0) { + err = found; + /* + * TNC traversing is finished in previous steps, + * any TNC path is accessible. + */ + ubifs_assert(c, !get_failure_reason_callback(c)); + goto out; + } + used += ALIGN(snod->len, 8); + } + } + + if (is_build_lpt && !used) { + *free = c->leb_size; + *dirty = 0; + } else { + *free = c->leb_size - sleb->endpt; + *dirty = sleb->endpt - used; + if (idx_leb == 1) { + if (is_build_lpt) + FSCK(c)->lpts[index].flags = LPROPS_INDEX; + else + *is_idx = 1; + } + } + +out: + ubifs_scan_destroy(sleb); + return err; +} + +static void clear_buds(struct ubifs_info *c) +{ + int i; + + /* + * Since lpt is invalid, space statistics cannot be trusted, the buds + * were used to trace taken LEBs(LPT related), and fsck makes sure that + * there will be no new journal writings(no space allocations) before + * committing, so we should clear buds to prevent wrong lpt updating in + * committing stage(eg. ubifs_return_leb operation for @c->old_buds). + */ + free_buds(c, true); + for (i = 0; i < c->jhead_cnt; i++) { + c->jheads[i].wbuf.lnum = -1; + c->jheads[i].wbuf.offs = -1; + } +} + +static void clear_lp_lists_and_heaps(struct ubifs_info *c) +{ + int i; + + /* + * Since lpt is invalid, clear in-memory fast accessing paths (lp + * lists & heaps). + */ + c->freeable_cnt = 0; + c->in_a_category_cnt = 0; + for (i = 0; i < LPROPS_HEAP_CNT; i++) { + memset(c->lpt_heap[i].arr, 0, LPT_HEAP_SZ * sizeof(void *)); + c->lpt_heap[i].cnt = 0; + c->lpt_heap[i].max_cnt = LPT_HEAP_SZ; + } + memset(c->dirty_idx.arr, 0, LPT_HEAP_SZ * sizeof(void *)); + c->dirty_idx.cnt = 0; + c->dirty_idx.max_cnt = LPT_HEAP_SZ; + INIT_LIST_HEAD(&c->uncat_list); + INIT_LIST_HEAD(&c->empty_list); + INIT_LIST_HEAD(&c->freeable_list); + INIT_LIST_HEAD(&c->frdi_idx_list); +} + +static int retake_ihead(struct ubifs_info *c) +{ + int err = take_ihead(c); + + if (err < 0) { + /* All LPT nodes must be accessible. */ + ubifs_assert(c, !get_failure_reason_callback(c)); + ubifs_assert(c, FSCK(c)->lpt_status == 0); + } else + err = 0; + + return err; +} + +static int rebuild_lpt(struct ubifs_info *c) +{ + int err; + + /* Clear buds. */ + clear_buds(c); + /* Clear stale in-memory lpt data. */ + c->lpt_drty_flgs = 0; + c->dirty_nn_cnt = 0; + c->dirty_pn_cnt = 0; + clear_lp_lists_and_heaps(c); + ubifs_free_lpt_nodes(c); + kfree(c->ltab); + c->ltab = NULL; + + FSCK(c)->lpts = kzalloc(sizeof(struct ubifs_lprops) * c->main_lebs, + GFP_KERNEL); + if (!FSCK(c)->lpts) { + log_err(c, errno, "can not allocate lpts"); + return -ENOMEM; + } + + err = build_lpt(c, scan_get_lp, false); + if (err) + goto out; + + err = retake_ihead(c); + if (err) + goto out; + + FSCK(c)->lpt_status = 0; + +out: + kfree(FSCK(c)->lpts); + return err; +} + +static void check_and_correct_nnode(struct ubifs_info *c, + struct ubifs_nnode *nnode, + struct ubifs_nnode *parent_nnode, + int row, int col, int *corrected) +{ + int num = ubifs_calc_nnode_num(row, col); + + if (nnode->num != num) { + struct nnode_problem nnp = { + .nnode = nnode, + .parent_nnode = parent_nnode, + .num = num, + }; + + /* + * The nnode number is read from disk in big lpt mode, which + * could lead to the wrong nnode number, otherwise, ther nnode + * number cannot be wrong. + */ + ubifs_assert(c, c->big_lpt); + FSCK(c)->lpt_status |= FR_LPT_INCORRECT; + if (fix_problem(c, NNODE_INCORRECT, &nnp)) { + nnode->num = num; + *corrected = 1; + } + } +} + +static int check_and_correct_pnode(struct ubifs_info *c, + struct ubifs_pnode *pnode, int col, + struct ubifs_lp_stats *lst, + int *freeable_cnt, int *corrected) +{ + int i, index, lnum; + const int lp_cnt = UBIFS_LPT_FANOUT; + + if (pnode->num != col) { + struct pnode_problem pnp = { + .pnode = pnode, + .num = col, + }; + + /* + * The pnode number is read from disk in big lpt mode, which + * could lead to the wrong pnode number, otherwise, ther pnode + * number cannot be wrong. + */ + ubifs_assert(c, c->big_lpt); + FSCK(c)->lpt_status |= FR_LPT_INCORRECT; + if (fix_problem(c, PNODE_INCORRECT, &pnp)) { + pnode->num = col; + *corrected = 1; + } + } + + index = pnode->num << UBIFS_LPT_FANOUT_SHIFT; + lnum = index + c->main_first; + for (i = 0; i < lp_cnt && lnum < c->leb_cnt; i++, index++, lnum++) { + int err, cat, free, dirty, is_idx = 0; + struct ubifs_lprops *lp = &pnode->lprops[i]; + + err = scan_get_lp(c, index, &free, &dirty, &is_idx); + if (err) + return err; + + dbg_fsck("calculate properties for LEB %d, free %d dirty %d is_idx %d, in %s", + lnum, free, dirty, is_idx, c->dev_name); + + if (!FSCK(c)->lpt_status && lp->free + lp->dirty == c->leb_size + && !test_bit(index, FSCK(c)->used_lebs)) { + /* + * Some LEBs may become freeable in the following cases: + * a. LEBs become freeable after replaying the journal. + * b. Unclean reboot while doing gc for a freeable + * non-index LEB + * c. Freeable index LEBs in an uncompleted commit due + * to an unclean unmount. + * , which makes that these LEBs won't be accounted into + * the FSCK(c)->used_lebs, but they actually have + * free/dirty space statistics. So we should skip + * checking space for these LEBs. + */ + free = lp->free; + dirty = lp->dirty; + is_idx = (lp->flags & LPROPS_INDEX) ? 1 : 0; + } + if (lnum != lp->lnum || + free != lp->free || dirty != lp->dirty || + (is_idx && !(lp->flags & LPROPS_INDEX)) || + (!is_idx && (lp->flags & LPROPS_INDEX))) { + struct lp_problem lpp = { + .lnum = lnum, + .lp = lp, + .free = free, + .dirty = dirty, + .is_idx = is_idx, + }; + + FSCK(c)->lpt_status |= FR_LPT_INCORRECT; + if (fix_problem(c, LP_INCORRECT, &lpp)) { + lp->lnum = lnum; + lp->free = free; + lp->dirty = dirty; + lp->flags = is_idx ? LPROPS_INDEX : 0; + *corrected = 1; + } + } + + cat = ubifs_categorize_lprops(c, lp); + if (cat != (lp->flags & LPROPS_CAT_MASK)) { + if (FSCK(c)->lpt_status & FR_LPT_INCORRECT) { + lp->flags &= ~LPROPS_CAT_MASK; + lp->flags |= cat; + } else { + /* lp could be in the heap or un-categorized(add heap failed). */ + ubifs_assert(c, (lp->flags & LPROPS_CAT_MASK) == LPROPS_UNCAT); + } + } + if (cat == LPROPS_FREEABLE) + *freeable_cnt = *freeable_cnt + 1; + if ((lp->flags & LPROPS_TAKEN) && free == c->leb_size) + lst->taken_empty_lebs += 1; + + lst->total_free += free; + lst->total_dirty += dirty; + + if (free == c->leb_size) + lst->empty_lebs++; + + if (is_idx) { + lst->idx_lebs += 1; + } else { + int spc; + + spc = free + dirty; + if (spc < c->dead_wm) + lst->total_dead += spc; + else + lst->total_dark += ubifs_calc_dark(c, spc); + lst->total_used += c->leb_size - spc; + } + } + + return 0; +} + +static int check_and_correct_lpt(struct ubifs_info *c, int *lpt_corrected) +{ + int err, i, cnt, iip, row, col, corrected, lnum, max_num, freeable_cnt; + struct ubifs_cnode *cn, *cnode; + struct ubifs_nnode *nnode, *nn; + struct ubifs_pnode *pnode; + struct ubifs_lp_stats lst; + + max_num = 0; + freeable_cnt = 0; + memset(&lst, 0, sizeof(struct ubifs_lp_stats)); + + /* Load the entire LPT tree, check whether there are corrupted nodes. */ + cnt = DIV_ROUND_UP(c->main_lebs, UBIFS_LPT_FANOUT); + for (i = 0; i < cnt; i++) { + pnode = ubifs_pnode_lookup(c, i); + if (IS_ERR(pnode)) + return PTR_ERR(pnode); + if (pnode->num > max_num) + max_num = pnode->num; + } + + /* Check whether there are pnodes exceeding the 'c->main_lebs'. */ + pnode = ubifs_pnode_lookup(c, 0); + if (IS_ERR(pnode)) + return PTR_ERR(pnode); + while (pnode) { + if (pnode->num > max_num) { + ubifs_err(c, "pnode(%d) exceeds max number(%d)", + pnode->num, max_num); + set_failure_reason_callback(c, FR_LPT_CORRUPTED); + return -EINVAL; + } + pnode = ubifs_find_next_pnode(c, pnode); + if (IS_ERR(pnode)) + return PTR_ERR(pnode); + } + + /* Check & correct nnodes and pnodes(including LEB properties). */ + row = col = iip = 0; + cnode = (struct ubifs_cnode *)c->nroot; + while (cnode) { + ubifs_assert(c, row >= 0); + nnode = cnode->parent; + if (cnode->level) { + corrected = 0; + /* cnode is a nnode */ + nn = (struct ubifs_nnode *)cnode; + check_and_correct_nnode(c, nn, nnode, row, col, + &corrected); + if (corrected) + ubifs_make_nnode_dirty(c, nn); + while (iip < UBIFS_LPT_FANOUT) { + cn = nn->nbranch[iip].cnode; + if (cn) { + /* Go down */ + row += 1; + col <<= UBIFS_LPT_FANOUT_SHIFT; + col += iip; + iip = 0; + cnode = cn; + break; + } + /* Go right */ + iip += 1; + } + if (iip < UBIFS_LPT_FANOUT) + continue; + } else { + corrected = 0; + /* cnode is a pnode */ + pnode = (struct ubifs_pnode *)cnode; + err = check_and_correct_pnode(c, pnode, col, &lst, + &freeable_cnt, &corrected); + if (err) + return err; + if (corrected) + ubifs_make_pnode_dirty(c, pnode); + } + /* Go up and to the right */ + row -= 1; + col >>= UBIFS_LPT_FANOUT_SHIFT; + iip = cnode->iip + 1; + cnode = (struct ubifs_cnode *)nnode; + } + + dbg_fsck("empty_lebs %d, idx_lebs %d, total_free %lld, total_dirty %lld," + " total_used %lld, total_dead %lld, total_dark %lld," + " taken_empty_lebs %d, freeable_cnt %d, in %s", + lst.empty_lebs, lst.idx_lebs, lst.total_free, lst.total_dirty, + lst.total_used, lst.total_dead, lst.total_dark, + lst.taken_empty_lebs, freeable_cnt, c->dev_name); + + /* Check & correct the global space statistics. */ + if (lst.empty_lebs != c->lst.empty_lebs || + lst.idx_lebs != c->lst.idx_lebs || + lst.total_free != c->lst.total_free || + lst.total_dirty != c->lst.total_dirty || + lst.total_used != c->lst.total_used || + lst.total_dead != c->lst.total_dead || + lst.total_dark != c->lst.total_dark) { + struct space_stat_problem ssp = { + .lst = &c->lst, + .calc_lst = &lst, + }; + + FSCK(c)->lpt_status |= FR_LPT_INCORRECT; + if (fix_problem(c, SPACE_STAT_INCORRECT, &ssp)) { + c->lst.empty_lebs = lst.empty_lebs; + c->lst.idx_lebs = lst.idx_lebs; + c->lst.total_free = lst.total_free; + c->lst.total_dirty = lst.total_dirty; + c->lst.total_used = lst.total_used; + c->lst.total_dead = lst.total_dead; + c->lst.total_dark = lst.total_dark; + } + } + + /* Check & correct the lprops table information. */ + for (lnum = c->lpt_first; lnum <= c->lpt_last; lnum++) { + err = dbg_check_ltab_lnum(c, lnum); + if (err) + return err; + } + + if (FSCK(c)->lpt_status & FR_LPT_INCORRECT) { + /* Reset the taken_empty_lebs. */ + c->lst.taken_empty_lebs = 0; + /* Clear buds. */ + clear_buds(c); + /* Clear lp lists & heaps. */ + clear_lp_lists_and_heaps(c); + /* + * Build lp lists & heaps, subsequent steps could recover + * disconnected files by allocating free space. + */ + for (lnum = c->main_first; lnum < c->leb_cnt; lnum++) { + int cat; + struct ubifs_lprops *lp = ubifs_lpt_lookup(c, lnum); + if (IS_ERR(lp)) + return PTR_ERR(lp); + + /* Clear %LPROPS_TAKEN flag for all LEBs. */ + lp->flags &= ~LPROPS_TAKEN; + cat = lp->flags & LPROPS_CAT_MASK; + ubifs_add_to_cat(c, lp, cat); + } + /* + * The %LPROPS_TAKEN flag is cleared in LEB properties, just + * remark it for c->ihead_lnum LEB. + */ + err = retake_ihead(c); + if (err) + return err; + + *lpt_corrected = 1; + FSCK(c)->lpt_status &= ~FR_LPT_INCORRECT; + } else { + ubifs_assert(c, c->freeable_cnt == freeable_cnt); + ubifs_assert(c, c->lst.taken_empty_lebs == lst.taken_empty_lebs); + ubifs_assert(c, c->in_a_category_cnt == c->main_lebs); + } + + return 0; +} + +/** + * check_and_correct_space - check & correct the space statistics. + * @c: UBIFS file-system description object + * + * This function does following things: + * 1. Check fsck mode, exit program if current mode is check mode. + * 2. Check space statistics by comparing lpt records with scanning results + * for all main LEBs. There could be following problems: + * a) comparison result is inconsistent: correct the lpt records by LEB + * scanning results. + * b) lpt is corrupted: rebuild lpt. + * 3. Set the gc lnum. + * Returns zero in case of success, a negative error code in case of failure. + */ +int check_and_correct_space(struct ubifs_info *c) +{ + int err, lpt_corrected = 0; + + if (FSCK(c)->mode == CHECK_MODE) { + /* + * The check mode will exit, because unclean LEBs are not + * rewritten for readonly mode in previous steps. + */ + if (FSCK(c)->lpt_status) + exit_code |= FSCK_UNCORRECTED; + dbg_fsck("skip checking & correcting space%s, in %s", + mode_name(c), c->dev_name); + exit(exit_code); + } + + log_out(c, "Check and correct the space statistics"); + + if (FSCK(c)->lpt_status & FR_LPT_CORRUPTED) { +rebuild: + if (fix_problem(c, LPT_CORRUPTED, NULL)) + return rebuild_lpt(c); + } + + err = check_and_correct_lpt(c, &lpt_corrected); + if (err) { + if (test_and_clear_failure_reason_callback(c, FR_LPT_CORRUPTED)) + goto rebuild; + return err; + } + + /* Set gc lnum. */ + if (c->need_recovery || lpt_corrected) { + err = ubifs_rcvry_gc_commit(c); + if (err) { + /* All LPT nodes must be accessible. */ + ubifs_assert(c, !get_failure_reason_callback(c)); + ubifs_assert(c, FSCK(c)->lpt_status == 0); + return err; + } + } else { + err = take_gc_lnum(c); + if (err) { + /* All LPT nodes must be accessible. */ + ubifs_assert(c, !get_failure_reason_callback(c)); + ubifs_assert(c, FSCK(c)->lpt_status == 0); + return err; + } + err = ubifs_leb_unmap(c, c->gc_lnum); + if (err) + return err; + } + + return err; +} + +/** + * check_and_correct_index_size - check & correct the index size. + * @c: UBIFS file-system description object + * + * This function checks and corrects the index size by traversing TNC: Returns + * zero in case of success, a negative error code in case of failure. + */ +int check_and_correct_index_size(struct ubifs_info *c) +{ + int err; + unsigned long long index_size = 0; + + ubifs_assert(c, c->bi.old_idx_sz == c->calc_idx_sz); + err = dbg_walk_index(c, NULL, add_size, &index_size); + if (err) { + /* All TNC nodes must be accessible. */ + ubifs_assert(c, !get_failure_reason_callback(c)); + return err; + } + + dbg_fsck("total index size %llu, in %s", index_size, c->dev_name); + if (index_size != c->calc_idx_sz && + fix_problem(c, INCORRECT_IDX_SZ, &index_size)) + c->bi.old_idx_sz = c->calc_idx_sz = index_size; + + return 0; +} diff --git a/ubifs-utils/fsck.ubifs/extract_files.c b/ubifs-utils/fsck.ubifs/extract_files.c new file mode 100644 index 0000000..c83d377 --- /dev/null +++ b/ubifs-utils/fsck.ubifs/extract_files.c @@ -0,0 +1,1574 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2024, Huawei Technologies Co, Ltd. + * + * Authors: Zhihao Cheng <chengzhihao1@huawei.com> + */ + +#include <stdio.h> +#include <stdlib.h> +#include <getopt.h> +#include <sys/stat.h> + +#include "linux_err.h" +#include "bitops.h" +#include "kmem.h" +#include "crc32.h" +#include "ubifs.h" +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "misc.h" +#include "fsck.ubifs.h" + +static void parse_node_header(int lnum, int offs, int len, + unsigned long long sqnum, + struct scanned_node *header) +{ + header->exist = true; + header->lnum = lnum; + header->offs = offs; + header->len = len; + header->sqnum = sqnum; +} + +static inline bool inode_can_be_encrypted(struct ubifs_info *c, + struct scanned_ino_node *ino_node) +{ + if (!c->encrypted) + return false; + + if (ino_node->is_xattr) + return false; + + /* Only regular files, directories, and symlinks can be encrypted. */ + if (S_ISREG(ino_node->mode) || S_ISDIR(ino_node->mode) || + S_ISLNK(ino_node->mode)) + return true; + + return false; +} + +/** + * parse_ino_node - parse inode node and check it's validity. + * @c: UBIFS file-system description object + * @lnum: logical eraseblock number + * @offs: the offset in LEB of the raw inode node + * @node: raw node + * @key: key of node scanned (if it has one) + * @ino_node: node used to store raw inode information + * + * This function checks the raw inode information, and stores inode + * information into @ino_node. Returns %true if the inode is valid, + * otherwise %false is returned. + */ +bool parse_ino_node(struct ubifs_info *c, int lnum, int offs, void *node, + union ubifs_key *key, struct scanned_ino_node *ino_node) +{ + bool valid = false; + int data_len, node_len; + unsigned int flags; + unsigned long long sqnum; + struct ubifs_ch *ch = (struct ubifs_ch *)node; + struct ubifs_ino_node *ino = (struct ubifs_ino_node *)node; + ino_t inum = key_inum(c, key); + + if (!inum || inum > INUM_WATERMARK) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node(bad inum %lu) at %d:%d, in %s", + inum, lnum, offs, c->dev_name); + else + log_out(c, "bad inode node(bad inum %lu) at %d:%d", + inum, lnum, offs); + goto out; + } + + if (ch->node_type != key_type(c, key)) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(inconsistent node type %d vs key_type %d) at %d:%d, in %s", + inum, ch->node_type, key_type(c, key), + lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(inconsistent node type %d vs key_type %d) at %d:%d", + inum, ch->node_type, key_type(c, key), + lnum, offs); + goto out; + } + + node_len = le32_to_cpu(ch->len); + sqnum = le64_to_cpu(ch->sqnum); + key_copy(c, key, &ino_node->key); + flags = le32_to_cpu(ino->flags); + data_len = le32_to_cpu(ino->data_len); + ino_node->is_xattr = !!(flags & UBIFS_XATTR_FL) ? 1 : 0; + ino_node->is_encrypted = !!(flags & UBIFS_CRYPT_FL) ? 1 : 0; + ino_node->mode = le32_to_cpu(ino->mode); + ino_node->nlink = le32_to_cpu(ino->nlink); + ino_node->xcnt = le32_to_cpu(ino->xattr_cnt); + ino_node->xsz = le32_to_cpu(ino->xattr_size); + ino_node->xnms = le32_to_cpu(ino->xattr_names); + ino_node->size = le64_to_cpu(ino->size); + + if (inum == UBIFS_ROOT_INO && !S_ISDIR(ino_node->mode)) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(root inode is not dir, tyoe %u) at %d:%d, in %s", + inum, ino_node->mode & S_IFMT, lnum, offs, + c->dev_name); + else + log_out(c, "bad inode node %lu(root inode is not dir, tyoe %u) at %d:%d", + inum, ino_node->mode & S_IFMT, lnum, offs); + goto out; + } + + if (ino_node->size > c->max_inode_sz) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(size %llu is too large) at %d:%d, in %s", + inum, ino_node->size, lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(size %llu is too large) at %d:%d", + inum, ino_node->size, lnum, offs); + goto out; + } + + if (le16_to_cpu(ino->compr_type) >= UBIFS_COMPR_TYPES_CNT) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(unknown compression type %d) at %d:%d, in %s", + inum, le16_to_cpu(ino->compr_type), lnum, offs, + c->dev_name); + else + log_out(c, "bad inode node %lu(unknown compression type %d) at %d:%d", + inum, le16_to_cpu(ino->compr_type), lnum, offs); + goto out; + } + + if (ino_node->xnms + ino_node->xcnt > XATTR_LIST_MAX) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(too big xnames %u xcount %u) at %d:%d, in %s", + inum, ino_node->xnms, ino_node->xcnt, + lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(too big xnames %u xcount %u) at %d:%d", + inum, ino_node->xnms, ino_node->xcnt, + lnum, offs); + goto out; + } + + if (data_len < 0 || data_len > UBIFS_MAX_INO_DATA) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(invalid data len %d) at %d:%d, in %s", + inum, data_len, lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(invalid data len %d) at %d:%d", + inum, data_len, lnum, offs); + goto out; + } + + if (UBIFS_INO_NODE_SZ + data_len != node_len) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(inconsistent data len %d vs node len %d) at %d:%d, in %s", + inum, data_len, node_len, lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(inconsistent data len %d vs node len %d) at %d:%d", + inum, data_len, node_len, lnum, offs); + goto out; + } + + if (ino_node->is_xattr) { + if (!S_ISREG(ino_node->mode)) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(bad type %u for xattr) at %d:%d, in %s", + inum, ino_node->mode & S_IFMT, + lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(bad type %u for xattr) at %d:%d", + inum, ino_node->mode & S_IFMT, + lnum, offs); + goto out; + } + if (data_len != ino_node->size) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(inconsistent data_len %d vs size %llu for xattr) at %d:%d, in %s", + inum, data_len, ino_node->size, + lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(inconsistent data_len %d vs size %llu for xattr) at %d:%d", + inum, data_len, ino_node->size, + lnum, offs); + goto out; + } + if (ino_node->xcnt || ino_node->xsz || ino_node->xnms) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(non zero xattr count %u xattr size %u xattr names %u for xattr) at %d:%d, in %s", + inum, ino_node->xcnt, ino_node->xsz, + ino_node->xnms, lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(non zero xattr count %u xattr size %u xattr names %u for xattr) at %d:%d", + inum, ino_node->xcnt, ino_node->xsz, + ino_node->xnms, lnum, offs); + goto out; + } + } + + switch (ino_node->mode & S_IFMT) { + case S_IFREG: + if (!ino_node->is_xattr && data_len != 0) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(bad data len %d for reg file) at %d:%d, in %s", + inum, data_len, lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(bad data len %d for reg file) at %d:%d", + inum, data_len, lnum, offs); + goto out; + } + break; + case S_IFDIR: + if (data_len != 0) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(bad data len %d for dir file) at %d:%d, in %s", + inum, data_len, lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(bad data len %d for dir file) at %d:%d", + inum, data_len, lnum, offs); + goto out; + } + break; + case S_IFLNK: + if (data_len == 0) { + /* + * For encryption enabled or selinux enabled situation, + * uninitialized inode with xattrs could be written + * before ubifs_jnl_update(). If the dent node is + * written successfully but the initialized inode is + * not written, ubifs_iget() will get bad symlink inode + * with 'ui->data_len = 0'. Similar phenomenon can also + * occur for block/char dev creation. + * Just drop the inode node when above class of + * exceptions are found. + */ + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad symlink inode node %lu(bad data len %d) at %d:%d, in %s", + inum, data_len, lnum, offs, c->dev_name); + else + log_out(c, "bad symlink inode node %lu(bad data len %d) at %d:%d", + inum, data_len, lnum, offs); + goto out; + } + break; + case S_IFBLK: + fallthrough; + case S_IFCHR: + { + union ubifs_dev_desc *dev = (union ubifs_dev_desc *)ino->data; + int sz_new = sizeof(dev->new), sz_huge = sizeof(dev->huge); + + if (data_len != sz_new && data_len != sz_huge) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(bad data len %d for char/block file, expect %d or %d) at %d:%d, in %s", + inum, data_len, sz_new, sz_huge, lnum, + offs, c->dev_name); + else + log_out(c, "bad inode node %lu(bad data len %d for char/block file, expect %d or %d) at %d:%d", + inum, data_len, sz_new, sz_huge, lnum, + offs); + goto out; + } + break; + } + case S_IFSOCK: + fallthrough; + case S_IFIFO: + if (data_len != 0) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(bad data len %d for fifo/sock file) at %d:%d, in %s", + inum, data_len, lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(bad data len %d for fifo/sock file) at %d:%d", + inum, data_len, lnum, offs); + goto out; + } + break; + default: + /* invalid file type. */ + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(unknown type %u) at %d:%d, in %s", + inum, ino_node->mode & S_IFMT, lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(unknown type %u) at %d:%d", + inum, ino_node->mode & S_IFMT, lnum, offs); + goto out; + } + + if (ino_node->is_encrypted && !inode_can_be_encrypted(c, ino_node)) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad inode node %lu(encrypted but cannot be encrypted, type %u, is_xattr %d, fs_encrypted %d) at %d:%d, in %s", + inum, ino_node->mode & S_IFMT, ino_node->is_xattr, + c->encrypted, lnum, offs, c->dev_name); + else + log_out(c, "bad inode node %lu(encrypted but cannot be encrypted, type %u, is_xattr %d, fs_encrypted %d) at %d:%d", + inum, ino_node->mode & S_IFMT, ino_node->is_xattr, + c->encrypted, lnum, offs); + goto out; + } + + valid = true; + parse_node_header(lnum, offs, node_len, sqnum, &ino_node->header); + +out: + return valid; +} + +/** + * parse_dent_node - parse dentry node and check it's validity. + * @c: UBIFS file-system description object + * @lnum: logical eraseblock number + * @offs: the offset in LEB of the raw inode node + * @node: raw node + * @key: key of node scanned (if it has one) + * @dent_node: node used to store raw dentry information + * + * This function checks the raw dentry/(xattr entry) information, and + * stores dentry/(xattr entry) information into @dent_node. Returns + * %true if the entry is valid, otherwise %false is returned. + */ +bool parse_dent_node(struct ubifs_info *c, int lnum, int offs, void *node, + union ubifs_key *key, struct scanned_dent_node *dent_node) +{ + bool valid = false; + int node_len, nlen; + unsigned long long sqnum; + struct ubifs_ch *ch = (struct ubifs_ch *)node; + struct ubifs_dent_node *dent = (struct ubifs_dent_node *)node; + int key_type = key_type_flash(c, dent->key); + ino_t inum; + + nlen = le16_to_cpu(dent->nlen); + node_len = le32_to_cpu(ch->len); + sqnum = le64_to_cpu(ch->sqnum); + inum = le64_to_cpu(dent->inum); + + if (node_len != nlen + UBIFS_DENT_NODE_SZ + 1 || + dent->type >= UBIFS_ITYPES_CNT || + nlen > UBIFS_MAX_NLEN || dent->name[nlen] != 0 || + (key_type == UBIFS_XENT_KEY && + strnlen((const char *)dent->name, nlen) != nlen) || + inum > INUM_WATERMARK || key_type != ch->node_type) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad %s node(len %d nlen %d type %d inum %lu key_type %d node_type %d) at %d:%d, in %s", + ch->node_type == UBIFS_XENT_NODE ? "xattr entry" : "directory entry", + node_len, nlen, dent->type, inum, key_type, + ch->node_type, lnum, offs, c->dev_name); + else + log_out(c, "bad %s node(len %d nlen %d type %d inum %lu key_type %d node_type %d) at %d:%d", + ch->node_type == UBIFS_XENT_NODE ? "xattr entry" : "directory entry", + node_len, nlen, dent->type, inum, key_type, + ch->node_type, lnum, offs); + goto out; + } + + key_copy(c, key, &dent_node->key); + dent_node->can_be_found = false; + dent_node->type = dent->type; + dent_node->nlen = nlen; + memcpy(dent_node->name, dent->name, nlen); + dent_node->name[nlen] = '\0'; + dent_node->inum = inum; + + valid = true; + parse_node_header(lnum, offs, node_len, sqnum, &dent_node->header); + +out: + return valid; +} + +/** + * parse_data_node - parse data node and check it's validity. + * @c: UBIFS file-system description object + * @lnum: logical eraseblock number + * @offs: the offset in LEB of the raw data node + * @node: raw node + * @key: key of node scanned (if it has one) + * @ino_node: node used to store raw data information + * + * This function checks the raw data node information, and stores + * data node information into @data_node. Returns %true if the data + * node is valid, otherwise %false is returned. + */ +bool parse_data_node(struct ubifs_info *c, int lnum, int offs, void *node, + union ubifs_key *key, struct scanned_data_node *data_node) +{ + bool valid = false; + int node_len; + unsigned long long sqnum; + struct ubifs_ch *ch = (struct ubifs_ch *)node; + struct ubifs_data_node *dn = (struct ubifs_data_node *)node; + ino_t inum = key_inum(c, key); + + if (ch->node_type != key_type(c, key)) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad data node(inconsistent node type %d vs key_type %d) at %d:%d, in %s", + ch->node_type, key_type(c, key), + lnum, offs, c->dev_name); + else + log_out(c, "bad data node(inconsistent node type %d vs key_type %d) at %d:%d", + ch->node_type, key_type(c, key), lnum, offs); + goto out; + } + + if (!inum || inum > INUM_WATERMARK) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad data node(bad inum %lu) at %d:%d, in %s", + inum, lnum, offs, c->dev_name); + else + log_out(c, "bad data node(bad inum %lu) at %d:%d", + inum, lnum, offs); + goto out; + } + + node_len = le32_to_cpu(ch->len); + sqnum = le64_to_cpu(ch->sqnum); + key_copy(c, key, &data_node->key); + data_node->size = le32_to_cpu(dn->size); + + if (!data_node->size || data_node->size > UBIFS_BLOCK_SIZE) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad data node(invalid size %u) at %d:%d, in %s", + data_node->size, lnum, offs, c->dev_name); + else + log_out(c, "bad data node(invalid size %u) at %d:%d", + data_node->size, lnum, offs); + goto out; + } + + if (le16_to_cpu(dn->compr_type) >= UBIFS_COMPR_TYPES_CNT) { + if (FSCK(c)->mode == REBUILD_MODE) + dbg_fsck("bad data node(invalid compression type %d) at %d:%d, in %s", + le16_to_cpu(dn->compr_type), lnum, offs, c->dev_name); + else + log_out(c, "bad data node(invalid compression type %d) at %d:%d", + le16_to_cpu(dn->compr_type), lnum, offs); + goto out; + } + + valid = true; + parse_node_header(lnum, offs, node_len, sqnum, &data_node->header); + +out: + return valid; +} + +/** + * parse_trun_node - parse truncation node and check it's validity. + * @c: UBIFS file-system description object + * @lnum: logical eraseblock number + * @offs: the offset in LEB of the raw truncation node + * @node: raw node + * @key: key of node scanned (if it has one) + * @trun_node: node used to store raw truncation information + * + * This function checks the raw truncation information, and stores + * truncation information into @trun_node. Returns %true if the + * truncation is valid, otherwise %false is returned. + */ +bool parse_trun_node(struct ubifs_info *c, int lnum, int offs, void *node, + union ubifs_key *key, struct scanned_trun_node *trun_node) +{ + bool valid = false; + int node_len; + unsigned long long sqnum; + struct ubifs_ch *ch = (struct ubifs_ch *)node; + struct ubifs_trun_node *trun = (struct ubifs_trun_node *)node; + loff_t old_size = le64_to_cpu(trun->old_size); + loff_t new_size = le64_to_cpu(trun->new_size); + ino_t inum = le32_to_cpu(trun->inum); + + if (!inum || inum > INUM_WATERMARK) { + dbg_fsck("bad truncation node(bad inum %lu) at %d:%d, in %s", + inum, lnum, offs, c->dev_name); + goto out; + } + + node_len = le32_to_cpu(ch->len); + sqnum = le64_to_cpu(ch->sqnum); + trun_node->new_size = new_size; + + if (old_size < 0 || old_size > c->max_inode_sz || + new_size < 0 || new_size > c->max_inode_sz || + old_size <= new_size) { + dbg_fsck("bad truncation node(new size %ld old size %ld inum %lu) at %d:%d, in %s", + new_size, old_size, inum, lnum, offs, c->dev_name); + goto out; + } + + trun_key_init(c, key, inum); + valid = true; + parse_node_header(lnum, offs, node_len, sqnum, &trun_node->header); + +out: + return valid; +} + +/** + * insert_file_dentry - insert dentry according to scanned dent node. + * @file: file object + * @n_dent: scanned dent node + * + * Insert file dentry information. Returns zero in case of success, a + * negative error code in case of failure. + */ +static int insert_file_dentry(struct scanned_file *file, + struct scanned_dent_node *n_dent) +{ + struct scanned_dent_node *dent; + struct rb_node **p, *parent = NULL; + + p = &file->dent_nodes.rb_node; + while (*p) { + parent = *p; + dent = rb_entry(parent, struct scanned_dent_node, rb); + if (n_dent->header.sqnum < dent->header.sqnum) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + + dent = kmalloc(sizeof(struct scanned_dent_node), GFP_KERNEL); + if (!dent) + return -ENOMEM; + + *dent = *n_dent; + rb_link_node(&dent->rb, parent, p); + rb_insert_color(&dent->rb, &file->dent_nodes); + + return 0; +} + +/** + * update_file_data - insert/update data according to scanned data node. + * @c: UBIFS file-system description object + * @file: file object + * @n_dn: scanned data node + * + * Insert or update file data information. Returns zero in case of success, + * a negative error code in case of failure. + */ +static int update_file_data(struct ubifs_info *c, struct scanned_file *file, + struct scanned_data_node *n_dn) +{ + int cmp; + struct scanned_data_node *dn, *o_dn = NULL; + struct rb_node **p, *parent = NULL; + + p = &file->data_nodes.rb_node; + while (*p) { + parent = *p; + dn = rb_entry(parent, struct scanned_data_node, rb); + cmp = keys_cmp(c, &n_dn->key, &dn->key); + if (cmp < 0) { + p = &(*p)->rb_left; + } else if (cmp > 0) { + p = &(*p)->rb_right; + } else { + o_dn = dn; + break; + } + } + + if (o_dn) { + /* found data node with same block no. */ + if (o_dn->header.sqnum < n_dn->header.sqnum) { + o_dn->header = n_dn->header; + o_dn->size = n_dn->size; + } + + return 0; + } + + dn = kmalloc(sizeof(struct scanned_data_node), GFP_KERNEL); + if (!dn) + return -ENOMEM; + + *dn = *n_dn; + INIT_LIST_HEAD(&dn->list); + rb_link_node(&dn->rb, parent, p); + rb_insert_color(&dn->rb, &file->data_nodes); + + return 0; +} + +/** + * update_file - update file information. + * @c: UBIFS file-system description object + * @file: file object + * @sn: scanned node + * @key_type: type of @sn + * + * Update inode/dent/truncation/data node information of @file. Returns + * zero in case of success, a negative error code in case of failure. + */ +static int update_file(struct ubifs_info *c, struct scanned_file *file, + struct scanned_node *sn, int key_type) +{ + int err = 0; + + switch (key_type) { + case UBIFS_INO_KEY: + { + struct scanned_ino_node *o_ino, *n_ino; + + o_ino = &file->ino; + n_ino = (struct scanned_ino_node *)sn; + if (o_ino->header.exist && o_ino->header.sqnum > sn->sqnum) + goto out; + + *o_ino = *n_ino; + break; + } + case UBIFS_DENT_KEY: + case UBIFS_XENT_KEY: + { + struct scanned_dent_node *dent = (struct scanned_dent_node *)sn; + + dent->file = file; + err = insert_file_dentry(file, dent); + break; + } + case UBIFS_DATA_KEY: + { + struct scanned_data_node *dn = (struct scanned_data_node *)sn; + + err = update_file_data(c, file, dn); + break; + } + case UBIFS_TRUN_KEY: + { + struct scanned_trun_node *o_trun, *n_trun; + + o_trun = &file->trun; + n_trun = (struct scanned_trun_node *)sn; + if (o_trun->header.exist && o_trun->header.sqnum > sn->sqnum) + goto out; + + *o_trun = *n_trun; + break; + } + default: + err = -EINVAL; + log_err(c, 0, "unknown key type %d", key_type); + } + +out: + return err; +} + +/** + * insert_or_update_file - insert or update file according to scanned node. + * @c: UBIFS file-system description object + * @file_tree: tree of all scanned files + * @sn: scanned node + * @key_type: key type of @sn + * @inum: inode number + * + * According to @sn, this function inserts file into the tree, or updates + * file information if it already exists in the tree. Returns zero in case + * of success, a negative error code in case of failure. + */ +int insert_or_update_file(struct ubifs_info *c, struct rb_root *file_tree, + struct scanned_node *sn, int key_type, ino_t inum) +{ + int err; + struct scanned_file *file, *old_file = NULL; + struct rb_node **p, *parent = NULL; + + p = &file_tree->rb_node; + while (*p) { + parent = *p; + file = rb_entry(parent, struct scanned_file, rb); + if (inum < file->inum) { + p = &(*p)->rb_left; + } else if (inum > file->inum) { + p = &(*p)->rb_right; + } else { + old_file = file; + break; + } + } + if (old_file) + return update_file(c, old_file, sn, key_type); + + file = kzalloc(sizeof(struct scanned_file), GFP_KERNEL); + if (!file) + return -ENOMEM; + + file->inum = inum; + file->dent_nodes = RB_ROOT; + file->data_nodes = RB_ROOT; + file->xattr_files = RB_ROOT; + INIT_LIST_HEAD(&file->list); + err = update_file(c, file, sn, key_type); + if (err) { + kfree(file); + return err; + } + rb_link_node(&file->rb, parent, p); + rb_insert_color(&file->rb, file_tree); + + return 0; +} + +/** + * destroy_file_content - destroy scanned data/dentry nodes in give file. + * @c: UBIFS file-system description object + * @file: file object + * + * Destroy all data/dentry nodes and xattrs attached to @file. + */ +void destroy_file_content(struct ubifs_info *c, struct scanned_file *file) +{ + struct scanned_data_node *data_node; + struct scanned_dent_node *dent_node; + struct scanned_file *xattr_file; + struct rb_node *this; + + this = rb_first(&file->data_nodes); + while (this) { + data_node = rb_entry(this, struct scanned_data_node, rb); + this = rb_next(this); + + rb_erase(&data_node->rb, &file->data_nodes); + kfree(data_node); + } + + this = rb_first(&file->dent_nodes); + while (this) { + dent_node = rb_entry(this, struct scanned_dent_node, rb); + this = rb_next(this); + + rb_erase(&dent_node->rb, &file->dent_nodes); + kfree(dent_node); + } + + this = rb_first(&file->xattr_files); + while (this) { + xattr_file = rb_entry(this, struct scanned_file, rb); + this = rb_next(this); + + ubifs_assert(c, !rb_first(&xattr_file->xattr_files)); + destroy_file_content(c, xattr_file); + rb_erase(&xattr_file->rb, &file->xattr_files); + kfree(xattr_file); + } +} + +/** + * destroy_file_tree - destroy files from a given tree. + * @c: UBIFS file-system description object + * @file_tree: tree of all scanned files + * + * Destroy scanned files from a given tree. + */ +void destroy_file_tree(struct ubifs_info *c, struct rb_root *file_tree) +{ + struct scanned_file *file; + struct rb_node *this; + + this = rb_first(file_tree); + while (this) { + file = rb_entry(this, struct scanned_file, rb); + this = rb_next(this); + + destroy_file_content(c, file); + + rb_erase(&file->rb, file_tree); + kfree(file); + } +} + +/** + * destroy_file_list - destroy files from a given list head. + * @c: UBIFS file-system description object + * @file_list: list of the scanned files + * + * Destroy scanned files from a given list. + */ +void destroy_file_list(struct ubifs_info *c, struct list_head *file_list) +{ + struct scanned_file *file; + + while (!list_empty(file_list)) { + file = list_entry(file_list->next, struct scanned_file, list); + + destroy_file_content(c, file); + list_del(&file->list); + kfree(file); + } +} + +/** + * lookup_file - lookup file according to inode number. + * @file_tree: tree of all scanned files + * @inum: inode number + * + * This function lookups target file from @file_tree according to @inum. + */ +struct scanned_file *lookup_file(struct rb_root *file_tree, ino_t inum) +{ + struct scanned_file *file; + struct rb_node *p; + + p = file_tree->rb_node; + while (p) { + file = rb_entry(p, struct scanned_file, rb); + + if (inum < file->inum) + p = p->rb_left; + else if (inum > file->inum) + p = p->rb_right; + else + return file; + } + + return NULL; +} + +static void handle_invalid_file(struct ubifs_info *c, int problem_type, + struct scanned_file *file, void *priv) +{ + struct invalid_file_problem ifp = { + .file = file, + .priv = priv, + }; + + if (FSCK(c)->mode == REBUILD_MODE) + return; + + fix_problem(c, problem_type, &ifp); +} + +static int delete_node(struct ubifs_info *c, const union ubifs_key *key, + int lnum, int offs) +{ + int err; + + err = ubifs_tnc_remove_node(c, key, lnum, offs); + if (err) { + /* TNC traversing is finished, any TNC path is accessible */ + ubifs_assert(c, !get_failure_reason_callback(c)); + } + + return err; +} + +static int delete_dent_nodes(struct ubifs_info *c, struct scanned_file *file, + int err) +{ + int ret = 0; + struct rb_node *this = rb_first(&file->dent_nodes); + struct scanned_dent_node *dent_node; + + while (this) { + dent_node = rb_entry(this, struct scanned_dent_node, rb); + this = rb_next(this); + + if (!err) { + err = delete_node(c, &dent_node->key, + dent_node->header.lnum, dent_node->header.offs); + if (err) + ret = ret ? ret : err; + } + + rb_erase(&dent_node->rb, &file->dent_nodes); + kfree(dent_node); + } + + return ret; +} + +int delete_file(struct ubifs_info *c, struct scanned_file *file) +{ + int err = 0, ret = 0; + struct rb_node *this; + struct scanned_file *xattr_file; + struct scanned_data_node *data_node; + + if (file->ino.header.exist) { + err = delete_node(c, &file->ino.key, file->ino.header.lnum, + file->ino.header.offs); + if (err) + ret = ret ? ret : err; + } + + this = rb_first(&file->data_nodes); + while (this) { + data_node = rb_entry(this, struct scanned_data_node, rb); + this = rb_next(this); + + if (!err) { + err = delete_node(c, &data_node->key, + data_node->header.lnum, data_node->header.offs); + if (err) + ret = ret ? ret : err; + } + + rb_erase(&data_node->rb, &file->data_nodes); + kfree(data_node); + } + + err = delete_dent_nodes(c, file, err); + if (err) + ret = ret ? : err; + + this = rb_first(&file->xattr_files); + while (this) { + xattr_file = rb_entry(this, struct scanned_file, rb); + this = rb_next(this); + + ubifs_assert(c, !rb_first(&xattr_file->xattr_files)); + err = delete_file(c, xattr_file); + if (err) + ret = ret ? ret : err; + rb_erase(&xattr_file->rb, &file->xattr_files); + kfree(xattr_file); + } + + return ret; +} + +/** + * insert_xattr_file - insert xattr file into file's subtree. + * @c: UBIFS file-system description object + * @xattr_file: xattr file + * @host_file: host file + * + * This inserts xattr file into its' host file's subtree. + */ +static void insert_xattr_file(struct ubifs_info *c, + struct scanned_file *xattr_file, + struct scanned_file *host_file) +{ + struct scanned_file *tmp_xattr_file; + struct rb_node **p, *parent = NULL; + + p = &host_file->xattr_files.rb_node; + while (*p) { + parent = *p; + tmp_xattr_file = rb_entry(parent, struct scanned_file, rb); + if (xattr_file->inum < tmp_xattr_file->inum) { + p = &(*p)->rb_left; + } else if (xattr_file->inum > tmp_xattr_file->inum) { + p = &(*p)->rb_right; + } else { + /* Impossible: Same xattr file is inserted twice. */ + ubifs_assert(c, 0); + } + } + + rb_link_node(&xattr_file->rb, parent, p); + rb_insert_color(&xattr_file->rb, &host_file->xattr_files); +} + +/** + * file_is_valid - check whether the file is valid. + * @c: UBIFS file-system description object + * @file: file object + * @file_tree: tree of all scanned files + * @is_diconnected: reason of invalid file, whether the @file is disconnected + * + * This function checks whether given @file is valid, following checks will + * be performed: + * 1. All files have none-zero nlink inode, otherwise they are invalid. + * 2. The file type comes from inode and dentries should be consistent, + * inconsistent dentries will be deleted. + * 3. Directory type or xattr type files only have one dentry. Superfluous + * dentries with lower sequence number will be deleted. + * 4. Non-regular file doesn't have data nodes. Data nodes are deleted for + * non-regular file. + * 5. All files must have at least one dentries, except '/', '/' doesn't + * have dentries. Non '/' file is invalid if it doesn't have dentries. + * 6. Xattr files should have host inode, and host inode cannot be a xattr, + * otherwise they are invalid. + * 7. Encrypted files should have corresponding xattrs, otherwise they are + * invalid. + * Xattr file will be inserted into corresponding host file's subtree. + * + * Returns %1 is @file is valid, %0 if @file is invalid, otherwise a negative + * error code in case of failure. + * Notice: All xattr files should be traversed before non-xattr files, because + * checking item 7 depends on it. + */ +int file_is_valid(struct ubifs_info *c, struct scanned_file *file, + struct rb_root *file_tree, int *is_diconnected) +{ + int type; + struct rb_node *node; + struct scanned_file *parent_file = NULL; + struct scanned_dent_node *dent_node; + struct scanned_data_node *data_node; + LIST_HEAD(drop_list); + + dbg_fsck("check validation of file %lu, in %s", file->inum, c->dev_name); + + if (!file->ino.header.exist) { + handle_invalid_file(c, FILE_HAS_NO_INODE, file, NULL); + return 0; + } + + if (!file->ino.nlink) { + handle_invalid_file(c, FILE_HAS_0_NLINK_INODE, file, NULL); + return 0; + } + + type = ubifs_get_dent_type(file->ino.mode); + + /* Drop dentry nodes with inconsistent type. */ + for (node = rb_first(&file->dent_nodes); node; node = rb_next(node)) { + int is_xattr = 0; + + dent_node = rb_entry(node, struct scanned_dent_node, rb); + + if (key_type(c, &dent_node->key) == UBIFS_XENT_KEY) + is_xattr = 1; + if (is_xattr != file->ino.is_xattr || type != dent_node->type) + list_add(&dent_node->list, &drop_list); + } + + while (!list_empty(&drop_list)) { + dent_node = list_entry(drop_list.next, struct scanned_dent_node, + list); + + handle_invalid_file(c, FILE_HAS_INCONSIST_TYPE, file, dent_node); + if (FSCK(c)->mode != REBUILD_MODE) { + int err = delete_node(c, &dent_node->key, + dent_node->header.lnum, dent_node->header.offs); + if (err) + return err; + } + + list_del(&dent_node->list); + rb_erase(&dent_node->rb, &file->dent_nodes); + kfree(dent_node); + } + + if (type != UBIFS_ITYPE_DIR && !file->ino.is_xattr) + goto check_data_nodes; + + /* Make sure that directory/xattr type files only have one dentry. */ + node = rb_first(&file->dent_nodes); + while (node) { + dent_node = rb_entry(node, struct scanned_dent_node, rb); + node = rb_next(node); + if (!node) + break; + + handle_invalid_file(c, FILE_HAS_TOO_MANY_DENT, file, dent_node); + if (FSCK(c)->mode != REBUILD_MODE) { + int err = delete_node(c, &dent_node->key, + dent_node->header.lnum, dent_node->header.offs); + if (err) + return err; + } + + rb_erase(&dent_node->rb, &file->dent_nodes); + kfree(dent_node); + } + +check_data_nodes: + if (type == UBIFS_ITYPE_REG && !file->ino.is_xattr) + goto check_dent_node; + + /* Make sure that non regular type files not have data/trun nodes. */ + file->trun.header.exist = 0; + node = rb_first(&file->data_nodes); + while (node) { + data_node = rb_entry(node, struct scanned_data_node, rb); + node = rb_next(node); + + handle_invalid_file(c, FILE_SHOULDNT_HAVE_DATA, file, data_node); + if (FSCK(c)->mode != REBUILD_MODE) { + int err = delete_node(c, &data_node->key, + data_node->header.lnum, data_node->header.offs); + if (err) + return err; + } + + rb_erase(&data_node->rb, &file->data_nodes); + kfree(data_node); + } + +check_dent_node: + if (rb_first(&file->dent_nodes)) { + if (file->inum == UBIFS_ROOT_INO) { + /* '/' has no dentries. */ + handle_invalid_file(c, FILE_ROOT_HAS_DENT, file, + rb_entry(rb_first(&file->dent_nodes), + struct scanned_dent_node, rb)); + return 0; + } + + node = rb_first(&file->dent_nodes); + dent_node = rb_entry(node, struct scanned_dent_node, rb); + parent_file = lookup_file(file_tree, key_inum(c, &dent_node->key)); + } else { + /* Non-root files must have dentries. */ + if (file->inum != UBIFS_ROOT_INO) { + if (type == UBIFS_ITYPE_REG && !file->ino.is_xattr) { + handle_invalid_file(c, FILE_IS_DISCONNECTED, + file, NULL); + if (is_diconnected) + *is_diconnected = 1; + } else { + handle_invalid_file(c, FILE_HAS_NO_DENT, + file, NULL); + } + return 0; + } + } + + if (file->ino.is_xattr) { + if (!parent_file) { + /* Host inode is not found. */ + handle_invalid_file(c, XATTR_HAS_NO_HOST, file, NULL); + return 0; + } + if (parent_file->ino.is_xattr) { + /* Host cannot be a xattr file. */ + handle_invalid_file(c, XATTR_HAS_WRONG_HOST, file, parent_file); + return 0; + } + + insert_xattr_file(c, file, parent_file); + if (parent_file->ino.is_encrypted) { + int nlen = min(dent_node->nlen, + strlen(UBIFS_XATTR_NAME_ENCRYPTION_CONTEXT)); + + if (!strncmp(dent_node->name, + UBIFS_XATTR_NAME_ENCRYPTION_CONTEXT, nlen)) + parent_file->has_encrypted_info = true; + } + } else { + if (parent_file && !S_ISDIR(parent_file->ino.mode)) { + /* Parent file should be directory. */ + if (type == UBIFS_ITYPE_REG) { + handle_invalid_file(c, FILE_IS_DISCONNECTED, + file, NULL); + if (FSCK(c)->mode != REBUILD_MODE) { + /* Delete dentries for the disconnected file. */ + int err = delete_dent_nodes(c, file, 0); + if (err) + return err; + } + if (is_diconnected) + *is_diconnected = 1; + } + return 0; + } + + /* + * Since xattr files are checked in first round, so all + * non-xattr files's @has_encrypted_info fields have been + * initialized. + */ + if (file->ino.is_encrypted && !file->has_encrypted_info) { + handle_invalid_file(c, FILE_HAS_NO_ENCRYPT, file, NULL); + return 0; + } + } + + return 1; +} + +static bool dentry_is_reachable(struct ubifs_info *c, + struct scanned_dent_node *dent_node, + struct list_head *path_list, + struct rb_root *file_tree) +{ + struct scanned_file *parent_file = NULL; + struct scanned_dent_node *dn, *parent_dent; + struct rb_node *p; + + /* Check whether the path is cyclical. */ + list_for_each_entry(dn, path_list, list) { + if (dn == dent_node) + return false; + } + + /* Quick path, dentry has already been checked as reachable. */ + if (dent_node->can_be_found) + return true; + + dent_node->can_be_found = true; + list_add(&dent_node->list, path_list); + + parent_file = lookup_file(file_tree, key_inum(c, &dent_node->key)); + /* Parent dentry is not found, unreachable. */ + if (!parent_file) + return false; + + /* Parent dentry is '/', reachable. */ + if (parent_file->inum == UBIFS_ROOT_INO) + return true; + + p = rb_first(&parent_file->dent_nodes); + if (!p) + return false; + parent_dent = rb_entry(p, struct scanned_dent_node, rb); + + return dentry_is_reachable(c, parent_dent, path_list, file_tree); +} + +/** + * file_is_reachable - whether the file can be found from '/'. + * @c: UBIFS file-system description object + * @file: file object + * @file_tree: tree of all scanned files + * + * This function iterates all directory entries in given @file and checks + * whether each dentry is reachable. All unreachable directory entries will + * be removed. + */ +bool file_is_reachable(struct ubifs_info *c, struct scanned_file *file, + struct rb_root *file_tree) +{ + struct rb_node *node; + struct scanned_dent_node *dent_node; + + if (file->inum == UBIFS_ROOT_INO) + goto reachable; + +retry: + for (node = rb_first(&file->dent_nodes); node; node = rb_next(node)) { + LIST_HEAD(path_list); + + dent_node = rb_entry(node, struct scanned_dent_node, rb); + + if (dentry_is_reachable(c, dent_node, &path_list, file_tree)) + continue; + + while (!list_empty(&path_list)) { + dent_node = list_entry(path_list.next, + struct scanned_dent_node, list); + + handle_invalid_file(c, DENTRY_IS_UNREACHABLE, + dent_node->file, dent_node); + if (FSCK(c)->mode != REBUILD_MODE) { + int err = delete_node(c, &dent_node->key, + dent_node->header.lnum, + dent_node->header.offs); + if (err) + return err; + } + dbg_fsck("remove unreachable dentry %s, in %s", + c->encrypted && !file->ino.is_xattr ? + "<encrypted>" : dent_node->name, c->dev_name); + list_del(&dent_node->list); + rb_erase(&dent_node->rb, &dent_node->file->dent_nodes); + kfree(dent_node); + } + + /* Since dentry node is removed from rb-tree, rescan rb-tree. */ + goto retry; + } + + if (!rb_first(&file->dent_nodes)) { + if (S_ISREG(file->ino.mode)) + handle_invalid_file(c, FILE_IS_DISCONNECTED, file, NULL); + else + handle_invalid_file(c, FILE_HAS_NO_DENT, file, NULL); + dbg_fsck("file %lu is unreachable, in %s", file->inum, c->dev_name); + return false; + } + +reachable: + dbg_fsck("file %lu is reachable, in %s", file->inum, c->dev_name); + return true; +} + +/** + * calculate_file_info - calculate the information of file + * @c: UBIFS file-system description object + * @file: file object + * @file_tree: tree of all scanned files + * + * This function calculates file information according to dentry nodes, + * data nodes and truncation node. The calculated informaion will be used + * to correct inode node. + */ +static int calculate_file_info(struct ubifs_info *c, struct scanned_file *file, + struct rb_root *file_tree) +{ + int nlink = 0; + bool corrupted_truncation = false; + unsigned long long ino_sqnum, trun_size = 0, new_size = 0, trun_sqnum = 0; + struct rb_node *node; + struct scanned_file *parent_file, *xattr_file; + struct scanned_dent_node *dent_node; + struct scanned_data_node *data_node; + LIST_HEAD(drop_list); + + for (node = rb_first(&file->xattr_files); node; node = rb_next(node)) { + xattr_file = rb_entry(node, struct scanned_file, rb); + dent_node = rb_entry(rb_first(&xattr_file->dent_nodes), + struct scanned_dent_node, rb); + + ubifs_assert(c, xattr_file->ino.is_xattr); + ubifs_assert(c, !rb_first(&xattr_file->xattr_files)); + xattr_file->calc_nlink = 1; + xattr_file->calc_size = xattr_file->ino.size; + + file->calc_xcnt += 1; + file->calc_xsz += CALC_DENT_SIZE(dent_node->nlen); + file->calc_xsz += CALC_XATTR_BYTES(xattr_file->ino.size); + file->calc_xnms += dent_node->nlen; + } + + if (file->inum == UBIFS_ROOT_INO) { + file->calc_nlink += 2; + file->calc_size += UBIFS_INO_NODE_SZ; + return 0; + } + + if (S_ISDIR(file->ino.mode)) { + file->calc_nlink += 2; + file->calc_size += UBIFS_INO_NODE_SZ; + + dent_node = rb_entry(rb_first(&file->dent_nodes), + struct scanned_dent_node, rb); + parent_file = lookup_file(file_tree, key_inum(c, &dent_node->key)); + if (!parent_file) { + ubifs_assert(c, 0); + return 0; + } + parent_file->calc_nlink += 1; + parent_file->calc_size += CALC_DENT_SIZE(dent_node->nlen); + return 0; + } + + for (node = rb_first(&file->dent_nodes); node; node = rb_next(node)) { + nlink++; + + dent_node = rb_entry(node, struct scanned_dent_node, rb); + + parent_file = lookup_file(file_tree, key_inum(c, &dent_node->key)); + if (!parent_file) { + ubifs_assert(c, 0); + return 0; + } + parent_file->calc_size += CALC_DENT_SIZE(dent_node->nlen); + } + file->calc_nlink = nlink; + + if (!S_ISREG(file->ino.mode)) { + /* No need to verify i_size for symlink/sock/block/char/fifo. */ + file->calc_size = file->ino.size; + return 0; + } + + /* + * Process i_size and data content, following situations should + * be considered: + * 1. Sequential writing or overwriting, i_size should be + * max(i_size, data node size), pick larger sqnum one from + * data nodes with same block index. + * 2. Mixed truncation and writing, i_size depends on the latest + * truncation node or inode node or last data node, pick data + * nodes which are not truncated. + * 3. Setting bigger i_size attr, pick inode size or biggest + * i_size calculated by data nodes. + */ + if (file->trun.header.exist) { + trun_size = file->trun.new_size; + trun_sqnum = file->trun.header.sqnum; + } + ino_sqnum = file->ino.header.sqnum; + for (node = rb_first(&file->data_nodes); node; node = rb_next(node)) { + unsigned long long d_sz, d_sqnum; + unsigned int block_no; + + data_node = rb_entry(node, struct scanned_data_node, rb); + + d_sqnum = data_node->header.sqnum; + block_no = key_block(c, &data_node->key); + d_sz = data_node->size + block_no * UBIFS_BLOCK_SIZE; + if ((trun_sqnum > d_sqnum && trun_size < d_sz) || + (ino_sqnum > d_sqnum && file->ino.size < d_sz)) { + /* + * The truncated data nodes are not gced after + * truncating, just remove them. + */ + list_add(&data_node->list, &drop_list); + } else { + new_size = max_t(unsigned long long, new_size, d_sz); + } + } + /* + * Truncation node is written successful, but inode node is not. It + * won't happen because inode node is written before truncation node + * according to ubifs_jnl_truncate(), unless only inode is corrupted. + * In this case, data nodes could have been removed in history mounting + * recovery, so i_size needs to be updated. + */ + if (trun_sqnum > ino_sqnum && trun_size < file->ino.size) { + if (trun_size < new_size) { + corrupted_truncation = true; + /* + * Appendant writing after truncation and newest inode + * is not fell on disk. + */ + goto update_isize; + } + + /* + * Overwriting happens after truncation and newest inode is + * not fell on disk. + */ + file->calc_size = trun_size; + goto drop_data; + } +update_isize: + /* + * The file cannot use 'new_size' directly when the file may have ever + * been set i_size. For example: + * 1. echo 123 > file # i_size = 4 + * 2. truncate -s 100 file # i_size = 100 + * After scanning, new_size is 4. Apperantly the size of 'file' should + * be 100. So, the calculated new_size according to data nodes should + * only be used for extending i_size, like ubifs_recover_size() does. + */ + if (new_size > file->ino.size || corrupted_truncation) + file->calc_size = new_size; + else + file->calc_size = file->ino.size; + +drop_data: + while (!list_empty(&drop_list)) { + data_node = list_entry(drop_list.next, struct scanned_data_node, + list); + + if (FSCK(c)->mode != REBUILD_MODE) { + /* + * Don't ask, inconsistent file correcting will be + * asked in function correct_file_info(). + */ + int err = delete_node(c, &data_node->key, + data_node->header.lnum, data_node->header.offs); + if (err) + return err; + } + list_del(&data_node->list); + rb_erase(&data_node->rb, &file->data_nodes); + kfree(data_node); + } + + return 0; +} + +/** + * correct_file_info - correct the information of file + * @c: UBIFS file-system description object + * @file: file object + * + * This function corrects file information according to calculated fields, + * eg. 'calc_nlink', 'calc_xcnt', 'calc_xsz', 'calc_xnms' and 'calc_size'. + * Corrected inode node will be re-written. + */ +static int correct_file_info(struct ubifs_info *c, struct scanned_file *file) +{ + uint32_t crc; + int err, lnum, len; + struct rb_node *node; + struct ubifs_ino_node *ino; + struct scanned_file *xattr_file; + + for (node = rb_first(&file->xattr_files); node; node = rb_next(node)) { + xattr_file = rb_entry(node, struct scanned_file, rb); + + err = correct_file_info(c, xattr_file); + if (err) + return err; + } + + if (file->calc_nlink == file->ino.nlink && + file->calc_xcnt == file->ino.xcnt && + file->calc_xsz == file->ino.xsz && + file->calc_xnms == file->ino.xnms && + file->calc_size == file->ino.size) + return 0; + + handle_invalid_file(c, FILE_IS_INCONSISTENT, file, NULL); + lnum = file->ino.header.lnum; + dbg_fsck("correct file(inum:%lu type:%s), nlink %u->%u, xattr cnt %u->%u, xattr size %u->%u, xattr names %u->%u, size %llu->%llu, at %d:%d, in %s", + file->inum, file->ino.is_xattr ? "xattr" : + ubifs_get_type_name(ubifs_get_dent_type(file->ino.mode)), + file->ino.nlink, file->calc_nlink, + file->ino.xcnt, file->calc_xcnt, + file->ino.xsz, file->calc_xsz, + file->ino.xnms, file->calc_xnms, + file->ino.size, file->calc_size, + lnum, file->ino.header.offs, c->dev_name); + + err = ubifs_leb_read(c, lnum, c->sbuf, 0, c->leb_size, 0); + if (err && err != -EBADMSG) + return err; + + ino = c->sbuf + file->ino.header.offs; + ino->nlink = cpu_to_le32(file->calc_nlink); + ino->xattr_cnt = cpu_to_le32(file->calc_xcnt); + ino->xattr_size = cpu_to_le32(file->calc_xsz); + ino->xattr_names = cpu_to_le32(file->calc_xnms); + ino->size = cpu_to_le64(file->calc_size); + len = le32_to_cpu(ino->ch.len); + crc = crc32(UBIFS_CRC32_INIT, (void *)ino + 8, len - 8); + ino->ch.crc = cpu_to_le32(crc); + + /* Atomically write the fixed LEB back again */ + return ubifs_leb_change(c, lnum, c->sbuf, c->leb_size); +} + +/** + * check_and_correct_files - check and correct information of files. + * @c: UBIFS file-system description object + * + * This function does similar things with dbg_check_filesystem(), besides, + * it also corrects file information if the calculated information is not + * consistent with information from flash. + */ +int check_and_correct_files(struct ubifs_info *c) +{ + int err; + struct rb_node *node; + struct scanned_file *file; + struct rb_root *tree = &FSCK(c)->scanned_files; + + for (node = rb_first(tree); node; node = rb_next(node)) { + file = rb_entry(node, struct scanned_file, rb); + + err = calculate_file_info(c, file, tree); + if (err) + return err; + } + + for (node = rb_first(tree); node; node = rb_next(node)) { + file = rb_entry(node, struct scanned_file, rb); + + err = correct_file_info(c, file); + if (err) + return err; + } + + if (list_empty(&FSCK(c)->disconnected_files)) + return 0; + + ubifs_assert(c, FSCK(c)->mode != REBUILD_MODE); + list_for_each_entry(file, &FSCK(c)->disconnected_files, list) { + err = calculate_file_info(c, file, tree); + if (err) + return err; + + /* Reset disconnected file's nlink as one. */ + file->calc_nlink = 1; + err = correct_file_info(c, file); + if (err) + return err; + } + + return 0; +} diff --git a/ubifs-utils/fsck.ubifs/fsck.ubifs.c b/ubifs-utils/fsck.ubifs/fsck.ubifs.c new file mode 100644 index 0000000..6ca0b57 --- /dev/null +++ b/ubifs-utils/fsck.ubifs/fsck.ubifs.c @@ -0,0 +1,636 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2024, Huawei Technologies Co, Ltd. + * + * Authors: Zhihao Cheng <chengzhihao1@huawei.com> + */ + +#include <stdio.h> +#include <stdlib.h> +#include <getopt.h> +#include <signal.h> + +#include "bitops.h" +#include "kmem.h" +#include "ubifs.h" +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "misc.h" +#include "fsck.ubifs.h" + +/* + * Because we copy functions from the kernel, we use a subset of the UBIFS + * file-system description object struct ubifs_info. + */ +struct ubifs_info info_; +static struct ubifs_info *c = &info_; + +int exit_code = FSCK_OK; + +static const char *optstring = "Vrg:abyn"; + +static const struct option longopts[] = { + {"version", 0, NULL, 'V'}, + {"reserve", 1, NULL, 'r'}, + {"debug", 1, NULL, 'g'}, + {"auto", 1, NULL, 'a'}, + {"rebuild", 1, NULL, 'b'}, + {"yes", 1, NULL, 'y'}, + {"nochange", 1, NULL, 'n'}, + {NULL, 0, NULL, 0} +}; + +static const char *helptext = +"Usage: fsck.ubifs [OPTIONS] ubi_volume\n" +"Check & repair UBIFS filesystem on a given UBI volume\n\n" +"Options:\n" +"-V, --version Display version information\n" +"-g, --debug=LEVEL Display debug information (0 - none, 1 - error message,\n" +" 2 - warning message[default], 3 - notice message, 4 - debug message)\n" +"-a, --auto Automatic safely repair without droping data (No questions).\n" +" Can not be specified at the same time as the -y or -n options\n" +"-y, --yes Assume \"yes\" to all questions. Automatic repair and report dropping data (No questions).\n" +" There are two submodes for this working mode:\n" +" a. default - Fail if TNC/master/log is corrupted. Only -y option is specified\n" +" b. rebuild fs - Turn to rebuild fs if TNC/master/log is corrupted. Specify -b option to make effect\n" +" Can not be specified at the same time as the -a or -n options\n" +"-b, --rebuild Forcedly repair the filesystem even by rebuilding filesystem.\n" +" Depends on -y option\n" +"-n, --nochange Make no changes to the filesystem, only check filesystem.\n" +" This mode don't check space, because unclean LEBs are not rewritten in readonly mode.\n" +" Can not be specified at the same time as the -a or -y options\n" +"Examples:\n" +"\t1. Check and repair filesystem from UBI volume /dev/ubi0_0\n" +"\t fsck.ubifs /dev/ubi0_0\n" +"\t2. Only check without modifying filesystem from UBI volume /dev/ubi0_0\n" +"\t fsck.ubifs -n /dev/ubi0_0\n" +"\t3. Check and safely repair filesystem from UBI volume /dev/ubi0_0\n" +"\t fsck.ubifs -a /dev/ubi0_0\n" +"\t4. Check and forcedly repair filesystem from UBI volume /dev/ubi0_0\n" +"\t fsck.ubifs -y -b /dev/ubi0_0\n\n"; + +static inline void usage(void) +{ + printf("%s", helptext); + exit_code |= FSCK_USAGE; + exit(exit_code); +} + +static void get_options(int argc, char *argv[], int *mode) +{ + int opt, i, submode = 0; + char *endp; + + while (1) { + opt = getopt_long(argc, argv, optstring, longopts, &i); + if (opt == -1) + break; + switch (opt) { + case 'V': + common_print_version(); + exit(FSCK_OK); + case 'g': + c->debug_level = strtol(optarg, &endp, 0); + if (*endp != '\0' || endp == optarg || + c->debug_level < 0 || c->debug_level > DEBUG_LEVEL) { + log_err(c, 0, "bad debugging level '%s'", optarg); + usage(); + } + break; + case 'a': + if (*mode != NORMAL_MODE) { +conflict_opt: + log_err(c, 0, "Only one of the options -a, -n or -y may be specified"); + usage(); + } + *mode = SAFE_MODE; + break; + case 'y': + if (*mode != NORMAL_MODE) + goto conflict_opt; + *mode = DANGER_MODE0; + break; + case 'b': + submode = 1; + break; + case 'n': + if (*mode != NORMAL_MODE) + goto conflict_opt; + *mode = CHECK_MODE; + c->ro_mount = 1; + break; + case 'r': + /* Compatible with FSCK(8). */ + break; + default: + usage(); + } + } + + if (submode) { + if (*mode != DANGER_MODE0) { + log_err(c, 0, "Option -y is not specified when -b is used"); + usage(); + } else + *mode = DANGER_MODE1; + } + + if (optind != argc) { + c->dev_name = strdup(argv[optind]); + if (!c->dev_name) { + log_err(c, errno, "can not allocate dev_name"); + exit_code |= FSCK_ERROR; + exit(exit_code); + } + } + + if (!c->dev_name) { + log_err(c, 0, "no ubi_volume specified"); + usage(); + } +} + +static void exit_callback(void) +{ + if (exit_code & FSCK_NONDESTRUCT) + log_out(c, "********** Filesystem was modified **********"); + if (exit_code & FSCK_UNCORRECTED) + log_out(c, "********** WARNING: Filesystem still has errors **********"); + if (exit_code & ~(FSCK_OK|FSCK_NONDESTRUCT)) + log_out(c, "FSCK failed, exit code %d", exit_code); + else + log_out(c, "FSCK success!"); +} + +static void fsck_assert_failed(__unused const struct ubifs_info *c) +{ + exit_code |= FSCK_ERROR; + exit(exit_code); +} + +static void fsck_set_failure_reason(const struct ubifs_info *c, + unsigned int reason) +{ + if (FSCK(c)->mode == REBUILD_MODE) + return; + + FSCK(c)->failure_reason = reason; + if (reason & FR_LPT_CORRUPTED) { + log_out(c, "Found corrupted pnode/nnode, set lpt corrupted"); + FSCK(c)->lpt_status |= FR_LPT_CORRUPTED; + } + if (reason & FR_LPT_INCORRECT) { + log_out(c, "Bad space statistics, set lpt incorrect"); + FSCK(c)->lpt_status |= FR_LPT_INCORRECT; + } +} + +static unsigned int fsck_get_failure_reason(const struct ubifs_info *c) +{ + ubifs_assert(c, FSCK(c)->mode != REBUILD_MODE); + + return FSCK(c)->failure_reason; +} + +static void fsck_clear_failure_reason(const struct ubifs_info *c) +{ + ubifs_assert(c, FSCK(c)->mode != REBUILD_MODE); + + FSCK(c)->failure_reason = 0; +} + +static bool fsck_test_and_clear_failure_reason(const struct ubifs_info *c, + unsigned int reason) +{ + bool res = (FSCK(c)->failure_reason & reason) != 0; + + ubifs_assert(c, FSCK(c)->mode != REBUILD_MODE); + ubifs_assert(c, !(FSCK(c)->failure_reason & (~reason))); + + FSCK(c)->failure_reason = 0; + + return res; +} + +static void fsck_set_lpt_invalid(const struct ubifs_info *c, + unsigned int reason) +{ + ubifs_assert(c, FSCK(c)->mode != REBUILD_MODE); + + if (reason & FR_LPT_CORRUPTED) { + log_out(c, "Found corrupted pnode/nnode, set lpt corrupted"); + FSCK(c)->lpt_status |= FR_LPT_CORRUPTED; + } + if (reason & FR_LPT_INCORRECT) { + log_out(c, "Bad space statistics, set lpt incorrect"); + FSCK(c)->lpt_status |= FR_LPT_INCORRECT; + } +} + +static bool fsck_test_lpt_valid(const struct ubifs_info *c, int lnum, + int old_free, int old_dirty, + int free, int dirty) +{ + ubifs_assert(c, FSCK(c)->mode != REBUILD_MODE); + + if (c->cmt_state != COMMIT_RESTING) + /* Don't skip updating lpt when do commit. */ + goto out; + + if (FSCK(c)->lpt_status) + return false; + + if (c->lst.empty_lebs < 0 || c->lst.empty_lebs > c->main_lebs) { + log_out(c, "Bad empty_lebs %d(main_lebs %d), set lpt incorrect", + c->lst.empty_lebs, c->main_lebs); + goto out_invalid; + } + if (c->freeable_cnt < 0 || c->freeable_cnt > c->main_lebs) { + log_out(c, "Bad freeable_cnt %d(main_lebs %d), set lpt incorrect", + c->freeable_cnt, c->main_lebs); + goto out_invalid; + } + if (c->lst.taken_empty_lebs < 0 || + c->lst.taken_empty_lebs > c->lst.empty_lebs) { + log_out(c, "Bad taken_empty_lebs %d(empty_lebs %d), set lpt incorrect", + c->lst.taken_empty_lebs, c->lst.empty_lebs); + goto out_invalid; + } + if (c->lst.total_free & 7) { + log_out(c, "total_free(%lld) is not 8 bytes aligned, set lpt incorrect", + c->lst.total_free); + goto out_invalid; + } + if (c->lst.total_dirty & 7) { + log_out(c, "total_dirty(%lld) is not 8 bytes aligned, set lpt incorrect", + c->lst.total_dirty); + goto out_invalid; + } + if (c->lst.total_dead & 7) { + log_out(c, "total_dead(%lld) is not 8 bytes aligned, set lpt incorrect", + c->lst.total_dead); + goto out_invalid; + } + if (c->lst.total_dark & 7) { + log_out(c, "total_dark(%lld) is not 8 bytes aligned, set lpt incorrect", + c->lst.total_dark); + goto out_invalid; + } + if (c->lst.total_used & 7) { + log_out(c, "total_used(%lld) is not 8 bytes aligned, set lpt incorrect", + c->lst.total_used); + goto out_invalid; + } + if (old_free != LPROPS_NC && (old_free & 7)) { + log_out(c, "LEB %d old_free(%d) is not 8 bytes aligned, set lpt incorrect", + lnum, old_free); + goto out_invalid; + } + if (old_dirty != LPROPS_NC && (old_dirty & 7)) { + log_out(c, "LEB %d old_dirty(%d) is not 8 bytes aligned, set lpt incorrect", + lnum, old_dirty); + goto out_invalid; + } + if (free != LPROPS_NC && (free < 0 || free > c->leb_size)) { + log_out(c, "LEB %d bad free %d(leb_size %d), set lpt incorrect", + lnum, free, c->leb_size); + goto out_invalid; + } + if (dirty != LPROPS_NC && dirty < 0) { + /* Dirty may be more than c->leb_size before set_bud_lprops. */ + log_out(c, "LEB %d bad dirty %d(leb_size %d), set lpt incorrect", + lnum, dirty, c->leb_size); + goto out_invalid; + } + +out: + return true; + +out_invalid: + FSCK(c)->lpt_status |= FR_LPT_INCORRECT; + return false; +} + +static bool fsck_can_ignore_failure(const struct ubifs_info *c, + unsigned int reason) +{ + ubifs_assert(c, FSCK(c)->mode != REBUILD_MODE); + + if (c->cmt_state != COMMIT_RESTING) + /* Don't ignore failure when do commit. */ + return false; + if (reason & (FR_LPT_CORRUPTED | FR_LPT_INCORRECT)) + return true; + + return false; +} + +static const unsigned int reason_mapping_table[] = { + BUD_CORRUPTED, /* FR_H_BUD_CORRUPTED */ + TNC_DATA_CORRUPTED, /* FR_H_TNC_DATA_CORRUPTED */ + ORPHAN_CORRUPTED, /* FR_H_ORPHAN_CORRUPTED */ + LTAB_INCORRECT, /* FR_H_LTAB_INCORRECT */ +}; + +static bool fsck_handle_failure(const struct ubifs_info *c, unsigned int reason, + void *priv) +{ + ubifs_assert(c, FSCK(c)->mode != REBUILD_MODE); + + return fix_problem(c, reason_mapping_table[reason], priv); +} + +static void signal_cancel(int sig) +{ + ubifs_warn(c, "killed by signo %d", sig); + exit_code |= FSCK_CANCELED; + exit(exit_code); +} + +static int init_fsck_info(struct ubifs_info *c, int argc, char *argv[]) +{ + int err = 0, mode = NORMAL_MODE; + struct sigaction sa; + struct ubifs_fsck_info *fsck = NULL; + + if (atexit(exit_callback)) { + log_err(c, errno, "can not set exit callback"); + return -errno; + } + + init_ubifs_info(c, FSCK_PROGRAM_TYPE); + get_options(argc, argv, &mode); + + fsck = calloc(1, sizeof(struct ubifs_fsck_info)); + if (!fsck) { + err = -errno; + log_err(c, errno, "can not allocate fsck info"); + goto out_err; + } + + c->private = fsck; + FSCK(c)->mode = mode; + INIT_LIST_HEAD(&FSCK(c)->disconnected_files); + c->assert_failed_cb = fsck_assert_failed; + c->set_failure_reason_cb = fsck_set_failure_reason; + c->get_failure_reason_cb = fsck_get_failure_reason; + c->clear_failure_reason_cb = fsck_clear_failure_reason; + c->test_and_clear_failure_reason_cb = fsck_test_and_clear_failure_reason; + c->set_lpt_invalid_cb = fsck_set_lpt_invalid; + c->test_lpt_valid_cb = fsck_test_lpt_valid; + c->can_ignore_failure_cb = fsck_can_ignore_failure; + c->handle_failure_cb = fsck_handle_failure; + + memset(&sa, 0, sizeof(struct sigaction)); + sa.sa_handler = signal_cancel; + if (sigaction(SIGINT, &sa, NULL) || sigaction(SIGTERM, &sa, NULL)) { + err = -errno; + log_err(c, errno, "can not set signal handler"); + goto out_err; + } + + return 0; + +out_err: + free(fsck); + free(c->dev_name); + c->dev_name = NULL; + return err; +} + +static void destroy_fsck_info(struct ubifs_info *c) +{ + free(c->private); + c->private = NULL; + free(c->dev_name); + c->dev_name = NULL; +} + +void handle_error(const struct ubifs_info *c, int reason_set) +{ + bool handled = false; + unsigned int reason = get_failure_reason_callback(c); + + clear_failure_reason_callback(c); + if ((reason_set & HAS_DATA_CORRUPTED) && (reason & FR_DATA_CORRUPTED)) { + handled = true; + reason &= ~FR_DATA_CORRUPTED; + if (fix_problem(c, LOG_CORRUPTED, NULL)) + FSCK(c)->try_rebuild = true; + } + if ((reason_set & HAS_TNC_CORRUPTED) && (reason & FR_TNC_CORRUPTED)) { + ubifs_assert(c, !handled); + handled = true; + reason &= ~FR_TNC_CORRUPTED; + if (fix_problem(c, TNC_CORRUPTED, NULL)) + FSCK(c)->try_rebuild = true; + } + + ubifs_assert(c, reason == 0); + if (!handled) + exit_code |= FSCK_ERROR; +} + +static int commit_fix_modifications(struct ubifs_info *c, bool final_commit) +{ + int err; + + if (final_commit) { + log_out(c, "Final committing"); + c->mst_node->flags &= ~cpu_to_le32(UBIFS_MST_DIRTY); + c->mst_node->gc_lnum = cpu_to_le32(c->gc_lnum); + /* Force UBIFS to do commit by setting @c->mounting. */ + c->mounting = 1; + } else if (exit_code & FSCK_NONDESTRUCT) { + log_out(c, "Commit problem fixing modifications"); + /* Force UBIFS to do commit by setting @c->mounting. */ + c->mounting = 1; + } + + err = ubifs_run_commit(c); + + if (c->mounting) + c->mounting = 0; + + return err; +} + +/* + * do_fsck - Check & repair the filesystem. + */ +static int do_fsck(void) +{ + int err; + + log_out(c, "Traverse TNC and construct files"); + err = traverse_tnc_and_construct_files(c); + if (err) { + handle_error(c, HAS_TNC_CORRUPTED); + return err; + } + + update_files_size(c); + + log_out(c, "Check and handle invalid files"); + err = handle_invalid_files(c); + if (err) { + exit_code |= FSCK_ERROR; + goto free_used_lebs; + } + + log_out(c, "Check and handle unreachable files"); + err = handle_dentry_tree(c); + if (err) { + exit_code |= FSCK_ERROR; + goto free_disconnected_files; + } + + log_out(c, "Check and correct files"); + err = check_and_correct_files(c); + if (err) { + exit_code |= FSCK_ERROR; + goto free_disconnected_files; + } + + log_out(c, "Check whether the TNC is empty"); + if (tnc_is_empty(c) && fix_problem(c, EMPTY_TNC, NULL)) { + err = -EINVAL; + FSCK(c)->try_rebuild = true; + goto free_disconnected_files; + } + + err = check_and_correct_space(c); + kfree(FSCK(c)->used_lebs); + destroy_file_tree(c, &FSCK(c)->scanned_files); + if (err) { + exit_code |= FSCK_ERROR; + goto free_disconnected_files_2; + } + + /* + * Committing is required once before allocating new space(subsequent + * steps may need), because building lpt could mark LEB(which holds + * stale data nodes) as unused, if the LEB is overwritten by new data, + * old data won't be found in the next fsck run(assume that first fsck + * run is interrupted by the powercut), which could affect the + * correctness of LEB properties after replaying journal in the second + * fsck run. + */ + err = commit_fix_modifications(c, false); + if (err) { + exit_code |= FSCK_ERROR; + goto free_disconnected_files_2; + } + + log_out(c, "Check and correct the index size"); + err = check_and_correct_index_size(c); + if (err) { + exit_code |= FSCK_ERROR; + goto free_disconnected_files_2; + } + + log_out(c, "Check and create root dir"); + err = check_and_create_root(c); + if (err) { + exit_code |= FSCK_ERROR; + goto free_disconnected_files_2; + } + + if (list_empty(&FSCK(c)->disconnected_files)) + goto final_commit; + + log_out(c, "Check and create lost+found"); + err = check_and_create_lost_found(c); + if (err) { + exit_code |= FSCK_ERROR; + goto free_disconnected_files_2; + } + + log_out(c, "Handle disconnected files"); + err = handle_disonnected_files(c); + if (err) { + exit_code |= FSCK_ERROR; + goto free_disconnected_files_2; + } + +final_commit: + err = commit_fix_modifications(c, true); + if (err) + exit_code |= FSCK_ERROR; + + return err; + +free_disconnected_files_2: + destroy_file_list(c, &FSCK(c)->disconnected_files); + return err; + +free_disconnected_files: + destroy_file_list(c, &FSCK(c)->disconnected_files); +free_used_lebs: + kfree(FSCK(c)->used_lebs); + destroy_file_tree(c, &FSCK(c)->scanned_files); + return err; +} + +int main(int argc, char *argv[]) +{ + int err; + + err = init_fsck_info(c, argc, argv); + if (err) { + exit_code |= FSCK_ERROR; + goto out_exit; + } + + err = ubifs_open_volume(c, c->dev_name); + if (err) { + exit_code |= FSCK_ERROR; + goto out_destroy_fsck; + } + + /* + * Init: Read superblock + * Step 1: Read master & init lpt + * Step 2: Replay journal + * Step 3: Handle orphan nodes + * Step 4: Consolidate log + * Step 5: Recover isize + */ + err = ubifs_load_filesystem(c); + if (err) { + if (FSCK(c)->try_rebuild) + ubifs_rebuild_filesystem(c); + goto out_close; + } + + /* + * Step 6: Traverse tnc and construct files + * Step 7: Update files' size + * Step 8: Check and handle invalid files + * Step 9: Check and handle unreachable files + * Step 10: Check and correct files + * Step 11: Check whether the TNC is empty + * Step 12: Check and correct the space statistics + * Step 13: Commit problem fixing modifications + * Step 14: Check and correct the index size + * Step 15: Check and create root dir + * Step 16: Check and create lost+found + * Step 17: Handle disconnected files + * Step 18: Do final committing + */ + err = do_fsck(); + if (err && FSCK(c)->try_rebuild) { + ubifs_destroy_filesystem(c); + ubifs_rebuild_filesystem(c); + } else { + ubifs_destroy_filesystem(c); + } + +out_close: + ubifs_close_volume(c); +out_destroy_fsck: + destroy_fsck_info(c); +out_exit: + return exit_code; +} diff --git a/ubifs-utils/fsck.ubifs/fsck.ubifs.h b/ubifs-utils/fsck.ubifs/fsck.ubifs.h new file mode 100644 index 0000000..6529932 --- /dev/null +++ b/ubifs-utils/fsck.ubifs/fsck.ubifs.h @@ -0,0 +1,392 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2024, Huawei Technologies Co, Ltd. + * + * Authors: Zhihao Cheng <chengzhihao1@huawei.com> + */ + +#ifndef __FSCK_UBIFS_H__ +#define __FSCK_UBIFS_H__ + +/* Exit codes used by fsck-type programs */ +#define FSCK_OK 0 /* No errors */ +#define FSCK_NONDESTRUCT 1 /* File system errors corrected */ +#define FSCK_REBOOT 2 /* System should be rebooted */ +#define FSCK_UNCORRECTED 4 /* File system errors left uncorrected */ +#define FSCK_ERROR 8 /* Operational error */ +#define FSCK_USAGE 16 /* Usage or syntax error */ +#define FSCK_CANCELED 32 /* Aborted with a signal or ^C */ +#define FSCK_LIBRARY 128 /* Shared library error */ + +/* + * There are 6 working modes for fsck: + * NORMAL_MODE: Check the filesystem, ask user whether or not to fix the + * problem as long as inconsistent data is found during checking. + * SAFE_MODE: Check and safely repair the filesystem, if there are any + * data dropping operations needed by fixing, fsck will fail. + * DANGER_MODE0:Check and repair the filesystem according to TNC, data dropping + * will be reported. If TNC/master/log is corrupted, fsck will fail. + * DANGER_MODE1:Check and forcedly repair the filesystem according to TNC, + * turns to @REBUILD_MODE mode automatically if TNC/master/log is + * corrupted. + * REBUILD_MODE:Scan entire UBI volume to find all nodes, and rebuild the + * filesystem, always make fsck success. + * CHECK_MODE: Make no changes to the filesystem, only check the filesystem. + */ +enum { NORMAL_MODE = 0, SAFE_MODE, DANGER_MODE0, + DANGER_MODE1, REBUILD_MODE, CHECK_MODE }; + +/* Types of inconsistent problems */ +enum { SB_CORRUPTED = 0, MST_CORRUPTED, LOG_CORRUPTED, BUD_CORRUPTED, + TNC_CORRUPTED, TNC_DATA_CORRUPTED, ORPHAN_CORRUPTED, INVALID_INO_NODE, + INVALID_DENT_NODE, INVALID_DATA_NODE, SCAN_CORRUPTED, FILE_HAS_NO_INODE, + FILE_HAS_0_NLINK_INODE, FILE_HAS_INCONSIST_TYPE, FILE_HAS_TOO_MANY_DENT, + FILE_SHOULDNT_HAVE_DATA, FILE_HAS_NO_DENT, XATTR_HAS_NO_HOST, + XATTR_HAS_WRONG_HOST, FILE_HAS_NO_ENCRYPT, FILE_IS_DISCONNECTED, + FILE_ROOT_HAS_DENT, DENTRY_IS_UNREACHABLE, FILE_IS_INCONSISTENT, + EMPTY_TNC, LPT_CORRUPTED, NNODE_INCORRECT, PNODE_INCORRECT, + LP_INCORRECT, SPACE_STAT_INCORRECT, LTAB_INCORRECT, INCORRECT_IDX_SZ, + ROOT_DIR_NOT_FOUND, DISCONNECTED_FILE_CANNOT_BE_RECOVERED }; + +enum { HAS_DATA_CORRUPTED = 1, HAS_TNC_CORRUPTED = 2 }; + +typedef int (*calculate_lp_callback)(struct ubifs_info *c, + int index, int *free, int *dirty, + int *is_idx); + +struct scanned_file; + +/** + * scanned_node - common header node. + * @exist: whether the node is found by scanning + * @lnum: LEB number of the scanned node + * @offs: scanned node's offset within @lnum + * @len: length of scanned node + * @sqnum: sequence number + */ +struct scanned_node { + bool exist; + int lnum; + int offs; + int len; + unsigned long long sqnum; +}; + +/** + * scanned_ino_node - scanned inode node. + * @header: common header of scanned node + * @key: the key of inode node + * @is_xattr: %1 for xattr inode, otherwise %0 + * @is_encrypted: %1 for encrypted inode, otherwise %0 + * @mode: file mode + * @nlink: number of hard links + * @xcnt: count of extended attributes this inode has + * @xsz: summarized size of all extended attributes in bytes + * @xnms: sum of lengths of all extended attribute names + * @size: inode size in bytes + * @rb: link in the tree of valid inode nodes or deleted inode nodes + */ +struct scanned_ino_node { + struct scanned_node header; + union ubifs_key key; + unsigned int is_xattr:1; + unsigned int is_encrypted:1; + unsigned int mode; + unsigned int nlink; + unsigned int xcnt; + unsigned int xsz; + unsigned int xnms; + unsigned long long size; + struct rb_node rb; +}; + +/** + * scanned_dent_node - scanned dentry node. + * @header: common header of scanned node + * @key: the key of dentry node + * @can_be_found: whether this dentry can be found from '/' + * @type: file type, reg/dir/symlink/block/char/fifo/sock + * @nlen: name length + * @name: dentry name + * @inum: target inode number + * @file: corresponding file + * @rb: link in the trees of: + * 1) valid dentry nodes or deleted dentry node + * 2) all scanned dentry nodes from same file + * @list: link in the list dentries for looking up/deleting + */ +struct scanned_dent_node { + struct scanned_node header; + union ubifs_key key; + bool can_be_found; + unsigned int type; + unsigned int nlen; + char name[UBIFS_MAX_NLEN + 1]; + ino_t inum; + struct scanned_file *file; + struct rb_node rb; + struct list_head list; +}; + +/** + * scanned_data_node - scanned data node. + * @header: common header of scanned node + * @key: the key of data node + * @size: uncompressed data size in bytes + * @rb: link in the tree of all scanned data nodes from same file + * @list: link in the list for deleting + */ +struct scanned_data_node { + struct scanned_node header; + union ubifs_key key; + unsigned int size; + struct rb_node rb; + struct list_head list; +}; + +/** + * scanned_trun_node - scanned truncation node. + * @header: common header of scanned node + * @new_size: size after truncation + */ +struct scanned_trun_node { + struct scanned_node header; + unsigned long long new_size; +}; + +/** + * scanned_file - file info scanned from UBIFS volume. + * + * @calc_nlink: calculated count of directory entries refer this inode + * @calc_xcnt: calculated count of extended attributes + * @calc_xsz: calculated summary size of all extended attributes + * @calc_xnms: calculated sum of lengths of all extended attribute names + * @calc_size: calculated file size + * @has_encrypted_info: whether the file has encryption related xattrs + * + * @inum: inode number + * @ino: inode node + * @trun: truncation node + * + * @rb: link in the tree of all scanned files + * @list: link in the list files for kinds of processing + * @dent_nodes: tree of all scanned dentry nodes + * @data_nodes: tree of all scanned data nodes + * @xattr_files: tree of all scanned xattr files + */ +struct scanned_file { + unsigned int calc_nlink; + unsigned int calc_xcnt; + unsigned int calc_xsz; + unsigned int calc_xnms; + unsigned long long calc_size; + bool has_encrypted_info; + + ino_t inum; + struct scanned_ino_node ino; + struct scanned_trun_node trun; + + struct rb_node rb; + struct list_head list; + struct rb_root dent_nodes; + struct rb_root data_nodes; + struct rb_root xattr_files; +}; + +/** + * invalid_file_problem - problem instance for invalid file. + * @file: invalid file instance + * @priv: invalid instance in @file, could be a dent_node or data_node + */ +struct invalid_file_problem { + struct scanned_file *file; + void *priv; +}; + +/** + * nnode_problem - problem instance for incorrect nnode + * @nnode: incorrect nnode + * @parent_nnode: the parent nnode of @nnode, could be NULL if @nnode is root + * @num: calculated num + */ +struct nnode_problem { + struct ubifs_nnode *nnode; + struct ubifs_nnode *parent_nnode; + int num; +}; + +/** + * pnode_problem - problem instance for incorrect pnode + * @pnode: incorrect pnode + * @num: calculated num + */ +struct pnode_problem { + struct ubifs_pnode *pnode; + int num; +}; + +/** + * lp_problem - problem instance for incorrect LEB proerties + * @lp: incorrect LEB properties + * @lnum: LEB number + * @free: calculated free space in LEB + * @dirty: calculated dirty bytes in LEB + * @is_idx: %true means that the LEB is an index LEB + */ +struct lp_problem { + struct ubifs_lprops *lp; + int lnum; + int free; + int dirty; + int is_idx; +}; + +/** + * space_stat_problem - problem instance for incorrect space statistics + * @lst: current space statistics + * @calc_lst: calculated space statistics + */ +struct space_stat_problem { + struct ubifs_lp_stats *lst; + struct ubifs_lp_stats *calc_lst; +}; + +/** + * ubifs_rebuild_info - UBIFS rebuilding information. + * @write_buf: write buffer for LEB @head_lnum + * @head_lnum: current writing LEB number + * @head_offs: current writing position in LEB @head_lnum + * @need_update_lpt: whether to update lpt while writing index nodes + */ +struct ubifs_rebuild_info { + void *write_buf; + int head_lnum; + int head_offs; + bool need_update_lpt; +}; + +/** + * struct ubifs_fsck_info - UBIFS fsck information. + * @mode: working mode + * @failure_reason: reasons for failed operations + * @lpt_status: the status of lpt, could be: %0(OK), %FR_LPT_CORRUPTED or + * %FR_LPT_INCORRECT + * @scanned_files: tree of all scanned files + * @used_lebs: a bitmap used for recording used lebs + * @disconnected_files: regular files without dentries + * @lpts: lprops table + * @try_rebuild: %true means that try to rebuild fs when fsck failed + * @rebuild: rebuilding-related information + * @lost_and_found: inode number of the lost+found directory, %0 means invalid + */ +struct ubifs_fsck_info { + int mode; + unsigned int failure_reason; + unsigned int lpt_status; + struct rb_root scanned_files; + unsigned long *used_lebs; + struct list_head disconnected_files; + struct ubifs_lprops *lpts; + bool try_rebuild; + struct ubifs_rebuild_info *rebuild; + ino_t lost_and_found; +}; + +#define FSCK(c) ((struct ubifs_fsck_info*)c->private) + +static inline const char *mode_name(const struct ubifs_info *c) +{ + if (!c->private) + return ""; + + switch (FSCK(c)->mode) { + case NORMAL_MODE: + return ",normal mode"; + case SAFE_MODE: + return ",safe mode"; + case DANGER_MODE0: + return ",danger mode"; + case DANGER_MODE1: + return ",danger + rebuild mode"; + case REBUILD_MODE: + return ",rebuild mode"; + case CHECK_MODE: + return ",check mode"; + default: + return ""; + } +} + +#define log_out(c, fmt, ...) \ + printf("%s[%d] (%s%s): " fmt "\n", c->program_name ? : "noprog",\ + getpid(), c->dev_name ? : "-", mode_name(c), \ + ##__VA_ARGS__) + +#define log_err(c, err, fmt, ...) do { \ + printf("%s[%d][ERROR] (%s%s): %s: " fmt, \ + c->program_name ? : "noprog", getpid(), \ + c->dev_name ? : "-", mode_name(c), \ + __FUNCTION__, ##__VA_ARGS__); \ + if (err) \ + printf(" - %s", strerror(err)); \ + printf("\n"); \ +} while (0) + +/* Exit code for fsck program. */ +extern int exit_code; + +/* fsck.ubifs.c */ +void handle_error(const struct ubifs_info *c, int reason_set); + +/* problem.c */ +bool fix_problem(const struct ubifs_info *c, int problem_type, const void *priv); + +/* load_fs.c */ +int ubifs_load_filesystem(struct ubifs_info *c); +void ubifs_destroy_filesystem(struct ubifs_info *c); + +/* extract_files.c */ +bool parse_ino_node(struct ubifs_info *c, int lnum, int offs, void *node, + union ubifs_key *key, struct scanned_ino_node *ino_node); +bool parse_dent_node(struct ubifs_info *c, int lnum, int offs, void *node, + union ubifs_key *key, struct scanned_dent_node *dent_node); +bool parse_data_node(struct ubifs_info *c, int lnum, int offs, void *node, + union ubifs_key *key, struct scanned_data_node *data_node); +bool parse_trun_node(struct ubifs_info *c, int lnum, int offs, void *node, + union ubifs_key *key, struct scanned_trun_node *trun_node); +int insert_or_update_file(struct ubifs_info *c, struct rb_root *file_tree, + struct scanned_node *sn, int key_type, ino_t inum); +void destroy_file_content(struct ubifs_info *c, struct scanned_file *file); +void destroy_file_tree(struct ubifs_info *c, struct rb_root *file_tree); +void destroy_file_list(struct ubifs_info *c, struct list_head *file_list); +struct scanned_file *lookup_file(struct rb_root *file_tree, ino_t inum); +int delete_file(struct ubifs_info *c, struct scanned_file *file); +int file_is_valid(struct ubifs_info *c, struct scanned_file *file, + struct rb_root *file_tree, int *is_diconnected); +bool file_is_reachable(struct ubifs_info *c, struct scanned_file *file, + struct rb_root *file_tree); +int check_and_correct_files(struct ubifs_info *c); + +/* rebuild_fs.c */ +int ubifs_rebuild_filesystem(struct ubifs_info *c); + +/* check_files.c */ +int traverse_tnc_and_construct_files(struct ubifs_info *c); +void update_files_size(struct ubifs_info *c); +int handle_invalid_files(struct ubifs_info *c); +int handle_dentry_tree(struct ubifs_info *c); +bool tnc_is_empty(struct ubifs_info *c); +int check_and_create_root(struct ubifs_info *c); + +/* check_space.c */ +int get_free_leb(struct ubifs_info *c); +int build_lpt(struct ubifs_info *c, calculate_lp_callback calculate_lp_cb, + bool free_ltab); +int check_and_correct_space(struct ubifs_info *c); +int check_and_correct_index_size(struct ubifs_info *c); + +/* handle_disconnected.c */ +int check_and_create_lost_found(struct ubifs_info *c); +int handle_disonnected_files(struct ubifs_info *c); + +#endif diff --git a/ubifs-utils/fsck.ubifs/handle_disconnected.c b/ubifs-utils/fsck.ubifs/handle_disconnected.c new file mode 100644 index 0000000..be62522 --- /dev/null +++ b/ubifs-utils/fsck.ubifs/handle_disconnected.c @@ -0,0 +1,197 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2024, Huawei Technologies Co, Ltd. + * + * Authors: Huang Xiaojia <huangxiaojia2@huawei.com> + * Zhihao Cheng <chengzhihao1@huawei.com> + */ + +#include <stdio.h> +#include <stdlib.h> +#include <sys/stat.h> + +#include "linux_err.h" +#include "kmem.h" +#include "ubifs.h" +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "fsck.ubifs.h" + +#define LOST_FOUND_DIR_NAME "lost+found" +#define MAX_REPEAT_NAME_RETRY_TIMES 10000000 + +/** + * check_and_create_lost_found - Check and create the lost+found directory. + * @c: UBIFS file-system description object + * + * This function checks whether the lost+found directory exists and creates a + * new one if no valid lost+found existing. If there is a valid lost+found + * directory, inode number is stored in @FSCK(c)->lost_and_found. Returns zero + * in case of success, a negative error code in case of failure. + */ +int check_and_create_lost_found(struct ubifs_info *c) +{ + struct ubifs_inode *root_ui, *lost_found_ui; + struct fscrypt_name nm; + int err = 0; + + root_ui = ubifs_lookup_by_inum(c, UBIFS_ROOT_INO); + if (IS_ERR(root_ui)) { + err = PTR_ERR(root_ui); + /* Previous step ensures that the root dir is valid. */ + ubifs_assert(c, err != -ENOENT); + return err; + } + + if (root_ui->flags & UBIFS_CRYPT_FL) { + ubifs_msg(c, "The root dir is encrypted, skip checking lost+found"); + goto free_root; + } + + fname_name(&nm) = LOST_FOUND_DIR_NAME; + fname_len(&nm) = strlen(LOST_FOUND_DIR_NAME); + lost_found_ui = ubifs_lookup(c, root_ui, &nm); + if (IS_ERR(lost_found_ui)) { + err = PTR_ERR(lost_found_ui); + if (err != -ENOENT) + goto free_root; + + /* Not found. Create a new lost+found. */ + err = ubifs_mkdir(c, root_ui, &nm, S_IRUGO | S_IWUSR | S_IXUSR); + if (err < 0) { + if (err == -ENOSPC) { + ubifs_msg(c, "No free space to create lost+found"); + err = 0; + } + goto free_root; + } + lost_found_ui = ubifs_lookup(c, root_ui, &nm); + if (IS_ERR(lost_found_ui)) { + err = PTR_ERR(lost_found_ui); + ubifs_assert(c, err != -ENOENT); + goto free_root; + } + FSCK(c)->lost_and_found = lost_found_ui->vfs_inode.inum; + ubifs_msg(c, "Create the lost+found"); + } else if (!(lost_found_ui->flags & UBIFS_CRYPT_FL) && + S_ISDIR(lost_found_ui->vfs_inode.mode)) { + FSCK(c)->lost_and_found = lost_found_ui->vfs_inode.inum; + } else { + ubifs_msg(c, "The type of lost+found is %s%s", + ubifs_get_type_name(ubifs_get_dent_type(lost_found_ui->vfs_inode.mode)), + lost_found_ui->flags & UBIFS_CRYPT_FL ? ", encrypted" : ""); + } + + kfree(lost_found_ui); +free_root: + kfree(root_ui); + return err; +} + +static int handle_disonnected_file(struct ubifs_info *c, + struct scanned_file *file) +{ + int err = 0; + + if (FSCK(c)->lost_and_found) { + unsigned int index = 0; + char file_name[UBIFS_MAX_NLEN + 1]; + struct fscrypt_name nm; + struct ubifs_inode *ui = NULL, *lost_found_ui = NULL; + + lost_found_ui = ubifs_lookup_by_inum(c, FSCK(c)->lost_and_found); + if (IS_ERR(lost_found_ui)) { + err = PTR_ERR(lost_found_ui); + ubifs_assert(c, err != -ENOENT); + return err; + } + ui = ubifs_lookup_by_inum(c, file->inum); + if (IS_ERR(ui)) { + err = PTR_ERR(ui); + ubifs_assert(c, err != -ENOENT); + goto free_lost_found_ui; + } + + while (index < MAX_REPEAT_NAME_RETRY_TIMES) { + struct ubifs_inode *target_ui; + + err = snprintf(file_name, sizeof(file_name), + "INO_%lu_%u", file->inum, index); + if (err < 0) + goto free_ui; + fname_name(&nm) = file_name; + fname_len(&nm) = strlen(file_name); + target_ui = ubifs_lookup(c, lost_found_ui, &nm); + if (IS_ERR(target_ui)) { + err = PTR_ERR(target_ui); + if (err == -ENOENT) + break; + goto free_ui; + } + kfree(target_ui); + index++; + } + + if (err != -ENOENT) { + err = 0; + kfree(ui); + kfree(lost_found_ui); + log_out(c, "Too many duplicated names(%u) in lost+found for inum %lu", + index, file->inum); + goto delete_file; + } + + /* Try to recover disconnected file into lost+found. */ + err = ubifs_link_recovery(c, lost_found_ui, ui, &nm); + if (err && err == -ENOSPC) { + err = 0; + log_out(c, "No free space to recover disconnected file"); + goto delete_file; + } + dbg_fsck("recover disconnected file %lu, in %s", + file->inum, c->dev_name); + +free_ui: + kfree(ui); +free_lost_found_ui: + kfree(lost_found_ui); + return err; + } + + log_out(c, "No valid lost+found"); + +delete_file: + if (fix_problem(c, DISCONNECTED_FILE_CANNOT_BE_RECOVERED, file)) + err = delete_file(c, file); + return err; +} + +/** + * handle_disonnected_files - Handle disconnected files. + * @c: UBIFS file-system description object + * + * This function tries to recover disonnected files into lost+found directory. + * If there is no free space left to recover the disconnected files, fsck may + * delete the files to make filesystem be consistent. Returns zero in case of + * success, a negative error code in case of failure. + */ +int handle_disonnected_files(struct ubifs_info *c) +{ + int err, ret = 0; + struct scanned_file *file; + + while (!list_empty(&FSCK(c)->disconnected_files)) { + file = list_entry(FSCK(c)->disconnected_files.next, + struct scanned_file, list); + + list_del(&file->list); + err = handle_disonnected_file(c, file); + if (err) + ret = ret ? ret : err; + destroy_file_content(c, file); + kfree(file); + } + + return ret; +} diff --git a/ubifs-utils/fsck.ubifs/load_fs.c b/ubifs-utils/fsck.ubifs/load_fs.c new file mode 100644 index 0000000..04208a1 --- /dev/null +++ b/ubifs-utils/fsck.ubifs/load_fs.c @@ -0,0 +1,261 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2024, Huawei Technologies Co, Ltd. + * + * Authors: Zhihao Cheng <chengzhihao1@huawei.com> + */ + +#include <stdio.h> +#include <stdlib.h> + +#include "bitops.h" +#include "kmem.h" +#include "ubifs.h" +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "misc.h" +#include "fsck.ubifs.h" + +int ubifs_load_filesystem(struct ubifs_info *c) +{ + int err; + size_t sz; + + err = init_constants_early(c); + if (err) { + exit_code |= FSCK_ERROR; + return err; + } + + err = check_volume_empty(c); + if (err <= 0) { + exit_code |= FSCK_ERROR; + log_err(c, 0, "%s UBI volume!", err < 0 ? "bad" : "empty"); + return -EINVAL; + } + + if (c->ro_media && !c->ro_mount) { + exit_code |= FSCK_ERROR; + log_err(c, 0, "cannot read-write on read-only media"); + return -EROFS; + } + + err = -ENOMEM; + c->bottom_up_buf = kmalloc_array(BOTTOM_UP_HEIGHT, sizeof(int), + GFP_KERNEL); + if (!c->bottom_up_buf) { + exit_code |= FSCK_ERROR; + log_err(c, errno, "cannot allocate bottom_up_buf"); + goto out_free; + } + + c->sbuf = vmalloc(c->leb_size); + if (!c->sbuf) { + exit_code |= FSCK_ERROR; + log_err(c, errno, "cannot allocate sbuf"); + goto out_free; + } + + if (!c->ro_mount) { + c->ileb_buf = vmalloc(c->leb_size); + if (!c->ileb_buf) { + exit_code |= FSCK_ERROR; + log_err(c, errno, "cannot allocate ileb_buf"); + goto out_free; + } + } + + c->mounting = 1; + + log_out(c, "Read superblock"); + err = ubifs_read_superblock(c); + if (err) { + if (test_and_clear_failure_reason_callback(c, FR_DATA_CORRUPTED)) + fix_problem(c, SB_CORRUPTED, NULL); + exit_code |= FSCK_ERROR; + goto out_mounting; + } + + err = init_constants_sb(c); + if (err) { + exit_code |= FSCK_ERROR; + goto out_mounting; + } + + sz = ALIGN(c->max_idx_node_sz, c->min_io_size) * 2; + c->cbuf = kmalloc(sz, GFP_NOFS); + if (!c->cbuf) { + err = -ENOMEM; + exit_code |= FSCK_ERROR; + log_err(c, errno, "cannot allocate cbuf"); + goto out_mounting; + } + + err = alloc_wbufs(c); + if (err) { + exit_code |= FSCK_ERROR; + log_err(c, 0, "cannot allocate wbuf"); + goto out_mounting; + } + + log_out(c, "Read master & init lpt"); + err = ubifs_read_master(c); + if (err) { + if (test_and_clear_failure_reason_callback(c, FR_DATA_CORRUPTED)) { + if (fix_problem(c, MST_CORRUPTED, NULL)) + FSCK(c)->try_rebuild = true; + } else + exit_code |= FSCK_ERROR; + goto out_master; + } + + init_constants_master(c); + + if ((c->mst_node->flags & cpu_to_le32(UBIFS_MST_DIRTY)) != 0) { + ubifs_msg(c, "recovery needed"); + c->need_recovery = 1; + } + + if (c->need_recovery && !c->ro_mount) { + err = ubifs_recover_inl_heads(c, c->sbuf); + if (err) { + exit_code |= FSCK_ERROR; + goto out_master; + } + } + + err = ubifs_lpt_init(c, 1, !c->ro_mount); + if (err) { + exit_code |= FSCK_ERROR; + goto out_master; + } + + if (!c->ro_mount && c->space_fixup) { + err = ubifs_fixup_free_space(c); + if (err) { + exit_code |= FSCK_ERROR; + goto out_lpt; + } + } + + if (!c->ro_mount && !c->need_recovery) { + /* + * Set the "dirty" flag so that if we reboot uncleanly we + * will notice this immediately on the next mount. + */ + c->mst_node->flags |= cpu_to_le32(UBIFS_MST_DIRTY); + err = ubifs_write_master(c); + if (err) { + exit_code |= FSCK_ERROR; + goto out_lpt; + } + } + + if (!c->ro_mount && c->superblock_need_write) { + err = ubifs_write_sb_node(c, c->sup_node); + if (err) { + exit_code |= FSCK_ERROR; + goto out_lpt; + } + c->superblock_need_write = 0; + } + + log_out(c, "Replay journal"); + err = ubifs_replay_journal(c); + if (err) { + handle_error(c, HAS_DATA_CORRUPTED | HAS_TNC_CORRUPTED); + goto out_journal; + } + + /* Calculate 'min_idx_lebs' after journal replay */ + c->bi.min_idx_lebs = ubifs_calc_min_idx_lebs(c); + + log_out(c, "Handle orphan nodes"); + err = ubifs_mount_orphans(c, c->need_recovery, c->ro_mount); + if (err) { + handle_error(c, HAS_TNC_CORRUPTED); + goto out_orphans; + } + + if (!c->ro_mount) { + int lnum; + + /* Check for enough log space */ + lnum = c->lhead_lnum + 1; + if (lnum >= UBIFS_LOG_LNUM + c->log_lebs) + lnum = UBIFS_LOG_LNUM; + if (lnum == c->ltail_lnum) { + log_out(c, "Consolidate log"); + err = ubifs_consolidate_log(c); + if (err) { + handle_error(c, HAS_DATA_CORRUPTED); + goto out_orphans; + } + } + + if (c->need_recovery) { + log_out(c, "Recover isize"); + err = ubifs_recover_size(c, true); + if (err) { + handle_error(c, HAS_TNC_CORRUPTED); + goto out_orphans; + } + } + } else if (c->need_recovery) { + log_out(c, "Recover isize"); + err = ubifs_recover_size(c, false); + if (err) { + handle_error(c, HAS_TNC_CORRUPTED); + goto out_orphans; + } + } + + c->mounting = 0; + + return 0; + +out_orphans: + free_orphans(c); +out_journal: + destroy_journal(c); +out_lpt: + ubifs_lpt_free(c, 0); +out_master: + c->max_sqnum = 0; + c->highest_inum = 0; + c->calc_idx_sz = 0; + kfree(c->mst_node); + kfree(c->rcvrd_mst_node); + free_wbufs(c); +out_mounting: + c->mounting = 0; +out_free: + kfree(c->cbuf); + kfree(c->ileb_buf); + kfree(c->sbuf); + kfree(c->bottom_up_buf); + kfree(c->sup_node); + + return err; +} + +void ubifs_destroy_filesystem(struct ubifs_info *c) +{ + destroy_journal(c); + free_wbufs(c); + free_orphans(c); + ubifs_lpt_free(c, 0); + + c->max_sqnum = 0; + c->highest_inum = 0; + c->calc_idx_sz = 0; + + kfree(c->cbuf); + kfree(c->rcvrd_mst_node); + kfree(c->mst_node); + kfree(c->ileb_buf); + kfree(c->sbuf); + kfree(c->bottom_up_buf); + kfree(c->sup_node); +} diff --git a/ubifs-utils/fsck.ubifs/problem.c b/ubifs-utils/fsck.ubifs/problem.c new file mode 100644 index 0000000..916c976 --- /dev/null +++ b/ubifs-utils/fsck.ubifs/problem.c @@ -0,0 +1,377 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2024, Huawei Technologies Co, Ltd. + * + * Authors: Zhihao Cheng <chengzhihao1@huawei.com> + */ + +#include <stdio.h> +#include <stdlib.h> +#include <getopt.h> + +#include "ubifs.h" +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "fsck.ubifs.h" + +/* + * problem flags. + * + * PROBLEM_FIXABLE: problem is fixable, unsolvable problem such as corrupted + * super block will abort the fsck program + * PROBLEM_MUST_FIX: problem must be fixed because it will affect the subsequent + * fsck process, otherwise aborting the fsck program + * PROBLEM_DROP_DATA: user data could be dropped after fixing the problem + * PROBLEM_NEED_REBUILD: rebuilding filesystem is needed to fix the problem + */ +#define PROBLEM_FIXABLE (1<<0) +#define PROBLEM_MUST_FIX (1<<1) +#define PROBLEM_DROP_DATA (1<<2) +#define PROBLEM_NEED_REBUILD (1<<3) + +struct fsck_problem { + unsigned int flags; + const char *desc; +}; + +static const struct fsck_problem problem_table[] = { + {0, "Corrupted superblock"}, // SB_CORRUPTED + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA | PROBLEM_NEED_REBUILD, "Corrupted master node"}, // MST_CORRUPTED + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA | PROBLEM_NEED_REBUILD, "Corrupted log area"}, // LOG_CORRUPTED + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Corrupted bud LEB"}, // BUD_CORRUPTED + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA | PROBLEM_NEED_REBUILD, "Corrupted index node"}, // TNC_CORRUPTED + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Corrupted data searched from TNC"}, // TNC_DATA_CORRUPTED + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Corrupted orphan LEB"}, // ORPHAN_CORRUPTED + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Invalid inode node"}, // INVALID_INO_NODE + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Invalid dentry node"}, // INVALID_DENT_NODE + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Invalid data node"}, // INVALID_DATA_NODE + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Corrupted data is scanned"}, // SCAN_CORRUPTED + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "File has no inode"}, // FILE_HAS_NO_INODE + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "File has zero-nlink inode"}, // FILE_HAS_0_NLINK_INODE + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "File has inconsistent type"}, // FILE_HAS_INCONSIST_TYPE + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "File has too many dentries"}, // FILE_HAS_TOO_MANY_DENT + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "File should not have data"}, // FILE_SHOULDNT_HAVE_DATA + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "File has no dentries"}, // FILE_HAS_NO_DENT + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Xattr file has no host"}, // XATTR_HAS_NO_HOST + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Xattr file has wrong host"}, // XATTR_HAS_WRONG_HOST + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Encrypted file has no encryption information"}, // FILE_HAS_NO_ENCRYPT + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX, "File is disconnected(regular file without dentries)"}, // FILE_IS_DISCONNECTED + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Root dir should not have a dentry"}, // FILE_ROOT_HAS_DENT + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA, "Dentry is unreachable"}, // DENTRY_IS_UNREACHABLE + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX, "File is inconsistent"}, // FILE_IS_INCONSISTENT + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX | PROBLEM_DROP_DATA | PROBLEM_NEED_REBUILD, "TNC is empty"}, // EMPTY_TNC + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX, "Corrupted pnode/nnode"}, // LPT_CORRUPTED + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX, "Inconsistent properties for nnode"}, // NNODE_INCORRECT + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX, "Inconsistent properties for pnode"}, // PNODE_INCORRECT + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX, "Inconsistent properties for LEB"}, // LP_INCORRECT + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX, "Incorrect space statistics"}, // SPACE_STAT_INCORRECT + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX, "Inconsistent properties for lprops table"}, // LTAB_INCORRECT + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX, "Incorrect index size"}, // INCORRECT_IDX_SZ + {PROBLEM_FIXABLE | PROBLEM_MUST_FIX, "Root dir is lost"}, // ROOT_DIR_NOT_FOUND + {PROBLEM_FIXABLE | PROBLEM_DROP_DATA, "Disconnected file cannot be recovered"}, // DISCONNECTED_FILE_CANNOT_BE_RECOVERED +}; + +static const char *get_question(const struct fsck_problem *problem, + int problem_type) +{ + if (problem->flags & PROBLEM_NEED_REBUILD) + return "Rebuild filesystem?"; + + switch (problem_type) { + case BUD_CORRUPTED: + return "Drop bud?"; + case TNC_DATA_CORRUPTED: + case INVALID_INO_NODE: + case INVALID_DENT_NODE: + case INVALID_DATA_NODE: + case SCAN_CORRUPTED: + return "Drop it?"; + case ORPHAN_CORRUPTED: + return "Drop orphans on the LEB?"; + case FILE_HAS_NO_INODE: + case FILE_HAS_0_NLINK_INODE: + case FILE_HAS_NO_DENT: + case XATTR_HAS_NO_HOST: + case XATTR_HAS_WRONG_HOST: + case FILE_HAS_NO_ENCRYPT: + case FILE_ROOT_HAS_DENT: + case DENTRY_IS_UNREACHABLE: + case DISCONNECTED_FILE_CANNOT_BE_RECOVERED: + return "Delete it?"; + case FILE_HAS_INCONSIST_TYPE: + case FILE_HAS_TOO_MANY_DENT: + return "Remove dentry?"; + case FILE_SHOULDNT_HAVE_DATA: + return "Remove data block?"; + case FILE_IS_DISCONNECTED: + return "Put it into disconnected list?"; + case LPT_CORRUPTED: + return "Rebuild LPT?"; + case ROOT_DIR_NOT_FOUND: + return "Create a new one?"; + } + + return "Fix it?"; +} + +static void print_problem(const struct ubifs_info *c, + const struct fsck_problem *problem, int problem_type, + const void *priv) +{ + switch (problem_type) { + case BUD_CORRUPTED: + { + const struct ubifs_bud *bud = (const struct ubifs_bud *)priv; + + log_out(c, "problem: %s %d:%d %s", problem->desc, bud->lnum, + bud->start, dbg_jhead(bud->jhead)); + break; + } + case ORPHAN_CORRUPTED: + { + const int *lnum = (const int *)priv; + + log_out(c, "problem: %s %d", problem->desc, *lnum); + break; + } + case SCAN_CORRUPTED: + { + const struct ubifs_zbranch *zbr = (const struct ubifs_zbranch *)priv; + + log_out(c, "problem: %s in LEB %d, node in %d:%d becomes invalid", + problem->desc, zbr->lnum, zbr->lnum, zbr->offs); + break; + } + case FILE_HAS_NO_INODE: + { + const struct invalid_file_problem *ifp = (const struct invalid_file_problem *)priv; + + log_out(c, "problem: %s, ino %lu", problem->desc, ifp->file->inum); + break; + } + case FILE_HAS_INCONSIST_TYPE: + { + const struct invalid_file_problem *ifp = (const struct invalid_file_problem *)priv; + const struct scanned_dent_node *dent_node = (const struct scanned_dent_node *)ifp->priv; + + log_out(c, "problem: %s, ino %lu, inode type %s%s, dentry %s has type %s%s", + problem->desc, ifp->file->inum, + ubifs_get_type_name(ubifs_get_dent_type(ifp->file->ino.mode)), + ifp->file->ino.is_xattr ? "(xattr)" : "", + c->encrypted && !ifp->file->ino.is_xattr ? "<encrypted>" : dent_node->name, + ubifs_get_type_name(dent_node->type), + key_type(c, &dent_node->key) == UBIFS_XENT_KEY ? "(xattr)" : ""); + break; + } + case FILE_HAS_TOO_MANY_DENT: + case FILE_ROOT_HAS_DENT: + { + const struct invalid_file_problem *ifp = (const struct invalid_file_problem *)priv; + const struct scanned_dent_node *dent_node = (const struct scanned_dent_node *)ifp->priv; + + log_out(c, "problem: %s, ino %lu, type %s%s, dentry %s", + problem->desc, ifp->file->inum, + ubifs_get_type_name(ubifs_get_dent_type(ifp->file->ino.mode)), + ifp->file->ino.is_xattr ? "(xattr)" : "", + c->encrypted && !ifp->file->ino.is_xattr ? "<encrypted>" : dent_node->name); + break; + } + case FILE_SHOULDNT_HAVE_DATA: + { + const struct invalid_file_problem *ifp = (const struct invalid_file_problem *)priv; + const struct scanned_data_node *data_node = (const struct scanned_data_node *)ifp->priv; + + log_out(c, "problem: %s, ino %lu, type %s%s, data block %u", + problem->desc, ifp->file->inum, + ubifs_get_type_name(ubifs_get_dent_type(ifp->file->ino.mode)), + ifp->file->ino.is_xattr ? "(xattr)" : "", + key_block(c, &data_node->key)); + break; + } + case FILE_HAS_0_NLINK_INODE: + case FILE_HAS_NO_DENT: + case XATTR_HAS_NO_HOST: + case FILE_HAS_NO_ENCRYPT: + case FILE_IS_DISCONNECTED: + { + const struct invalid_file_problem *ifp = (const struct invalid_file_problem *)priv; + + log_out(c, "problem: %s, ino %lu type %s%s", problem->desc, + ifp->file->inum, + ubifs_get_type_name(ubifs_get_dent_type(ifp->file->ino.mode)), + ifp->file->ino.is_xattr ? "(xattr)" : ""); + break; + } + case XATTR_HAS_WRONG_HOST: + { + const struct invalid_file_problem *ifp = (const struct invalid_file_problem *)priv; + const struct scanned_file *host = (const struct scanned_file *)ifp->priv; + + log_out(c, "problem: %s, ino %lu type %s%s, host ino %lu type %s%s", + problem->desc, ifp->file->inum, + ubifs_get_type_name(ubifs_get_dent_type(ifp->file->ino.mode)), + ifp->file->ino.is_xattr ? "(xattr)" : "", host->inum, + ubifs_get_type_name(ubifs_get_dent_type(host->ino.mode)), + host->ino.is_xattr ? "(xattr)" : ""); + break; + } + case DENTRY_IS_UNREACHABLE: + { + const struct invalid_file_problem *ifp = (const struct invalid_file_problem *)priv; + const struct scanned_dent_node *dent_node = (const struct scanned_dent_node *)ifp->priv; + + log_out(c, "problem: %s, ino %lu, unreachable dentry %s, type %s%s", + problem->desc, ifp->file->inum, + c->encrypted && !ifp->file->ino.is_xattr ? "<encrypted>" : dent_node->name, + ubifs_get_type_name(dent_node->type), + key_type(c, &dent_node->key) == UBIFS_XENT_KEY ? "(xattr)" : ""); + break; + } + case FILE_IS_INCONSISTENT: + { + const struct invalid_file_problem *ifp = (const struct invalid_file_problem *)priv; + const struct scanned_file *file = ifp->file; + + log_out(c, "problem: %s, ino %lu type %s, nlink %u xcnt %u xsz %u xnms %u size %llu, " + "should be nlink %u xcnt %u xsz %u xnms %u size %llu", + problem->desc, file->inum, + file->ino.is_xattr ? "xattr" : ubifs_get_type_name(ubifs_get_dent_type(file->ino.mode)), + file->ino.nlink, file->ino.xcnt, file->ino.xsz, + file->ino.xnms, file->ino.size, + file->calc_nlink, file->calc_xcnt, file->calc_xsz, + file->calc_xnms, file->calc_size); + break; + } + case NNODE_INCORRECT: + { + const struct nnode_problem *nnp = (const struct nnode_problem *)priv; + + log_out(c, "problem: %s, nnode num %d expected %d parent num %d iip %d", + problem->desc, nnp->nnode->num, nnp->num, + nnp->parent_nnode ? nnp->parent_nnode->num : 0, + nnp->nnode->iip); + break; + } + case PNODE_INCORRECT: + { + const struct pnode_problem *pnp = (const struct pnode_problem *)priv; + + log_out(c, "problem: %s, pnode num %d expected %d parent num %d iip %d", + problem->desc, pnp->pnode->num, pnp->num, + pnp->pnode->parent->num, pnp->pnode->iip); + break; + } + case LP_INCORRECT: + { + const struct lp_problem *lpp = (const struct lp_problem *)priv; + + log_out(c, "problem: %s %d, free %d dirty %d is_idx %d, should be lnum %d free %d dirty %d is_idx %d", + problem->desc, lpp->lp->lnum, lpp->lp->free, + lpp->lp->dirty, lpp->lp->flags & LPROPS_INDEX ? 1 : 0, + lpp->lnum, lpp->free, lpp->dirty, lpp->is_idx); + break; + } + case SPACE_STAT_INCORRECT: + { + const struct space_stat_problem *ssp = (const struct space_stat_problem *)priv; + + log_out(c, "problem: %s, empty_lebs %d idx_lebs %d total_free %lld total_dirty %lld total_used %lld total_dead %lld total_dark %lld, should be empty_lebs %d idx_lebs %d total_free %lld total_dirty %lld total_used %lld total_dead %lld total_dark %lld", + problem->desc, ssp->lst->empty_lebs, ssp->lst->idx_lebs, + ssp->lst->total_free, ssp->lst->total_dirty, + ssp->lst->total_used, ssp->lst->total_dead, + ssp->lst->total_dark, ssp->calc_lst->empty_lebs, + ssp->calc_lst->idx_lebs, ssp->calc_lst->total_free, + ssp->calc_lst->total_dirty, ssp->calc_lst->total_used, + ssp->calc_lst->total_dead, ssp->calc_lst->total_dark); + break; + } + case INCORRECT_IDX_SZ: + { + const unsigned long long *calc_sz = (const unsigned long long *)priv; + + log_out(c, "problem: %s, index size is %llu, should be %llu", + problem->desc, c->calc_idx_sz, *calc_sz); + break; + } + case DISCONNECTED_FILE_CANNOT_BE_RECOVERED: + { + const struct scanned_file *file = (const struct scanned_file *)priv; + + log_out(c, "problem: %s, ino %lu, size %llu", problem->desc, + file->inum, file->ino.size); + break; + } + default: + log_out(c, "problem: %s", problem->desc); + break; + } +} + +static void fatal_error(const struct ubifs_info *c, + const struct fsck_problem *problem) +{ + if (!(problem->flags & PROBLEM_FIXABLE)) + log_out(c, "inconsistent problem cannot be fixed"); + else + log_out(c, "inconsistent problem must be fixed"); + exit(exit_code); +} + +/** + * fix_problem - whether fixing the inconsistent problem + * @c: UBIFS file-system description object + * @problem_type: the type of inconsistent problem + * @priv: private data for problem instance + * + * This function decides to fix/skip the inconsistent problem or abort the + * program according to @problem_type, returns %true if the problem should + * be fixed, returns %false if the problem will be skipped. + */ +bool fix_problem(const struct ubifs_info *c, int problem_type, const void *priv) +{ + bool ans, ask = true, def_y = true; + const struct fsck_problem *problem = &problem_table[problem_type]; + const char *question = get_question(problem, problem_type); + + ubifs_assert(c, FSCK(c)->mode != REBUILD_MODE); + + if (!(problem->flags & PROBLEM_FIXABLE)) { + exit_code |= FSCK_UNCORRECTED; + fatal_error(c, problem); + } + + if (FSCK(c)->mode == CHECK_MODE || + ((problem->flags & PROBLEM_DROP_DATA) && FSCK(c)->mode == SAFE_MODE) || + ((problem->flags & PROBLEM_NEED_REBUILD) && + (FSCK(c)->mode == SAFE_MODE || FSCK(c)->mode == DANGER_MODE0))) + def_y = false; + + if ((problem->flags & PROBLEM_NEED_REBUILD) && + (FSCK(c)->mode == DANGER_MODE0 || FSCK(c)->mode == DANGER_MODE1)) + ask = false; + + print_problem(c, problem, problem_type, priv); + ans = def_y; + if (FSCK(c)->mode == NORMAL_MODE) { + printf("%s[%d] (%s%s)", c->program_name, getpid(), + c->dev_name ? : "-", mode_name(c)); + if (prompt(question, def_y)) + ans = true; + else + ans = false; + } else { + if (ask) + log_out(c, "%s %c\n", question, def_y ? 'y' : 'n'); + } + + if (!ans) { + exit_code |= FSCK_UNCORRECTED; + if (problem->flags & PROBLEM_MUST_FIX) + fatal_error(c, problem); + } else { + exit_code |= FSCK_NONDESTRUCT; + } + + return ans; +} diff --git a/ubifs-utils/fsck.ubifs/rebuild_fs.c b/ubifs-utils/fsck.ubifs/rebuild_fs.c new file mode 100644 index 0000000..b82d728 --- /dev/null +++ b/ubifs-utils/fsck.ubifs/rebuild_fs.c @@ -0,0 +1,1453 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * Copyright (C) 2024, Huawei Technologies Co, Ltd. + * + * Authors: Zhihao Cheng <chengzhihao1@huawei.com> + */ + +#include <stdio.h> +#include <stdlib.h> +#include <getopt.h> +#include <sys/stat.h> + +#include "linux_err.h" +#include "bitops.h" +#include "kmem.h" +#include "ubifs.h" +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "misc.h" +#include "fsck.ubifs.h" + +/** + * scanned_info - nodes and files information from scanning. + * @valid_inos: the tree of scanned inode nodes with 'nlink > 0' + * @del_inos: the tree of scanned inode nodes with 'nlink = 0' + * @valid_dents: the tree of scanned dentry nodes with 'inum > 0' + * @del_dents: the tree of scanned dentry nodes with 'inum = 0' + */ +struct scanned_info { + struct rb_root valid_inos; + struct rb_root del_inos; + struct rb_root valid_dents; + struct rb_root del_dents; +}; + +/** + * struct idx_entry - index entry. + * @list: link in the list index entries for building index tree + * @key: key + * @name: directory entry name used for sorting colliding keys by name + * @lnum: LEB number + * @offs: offset + * @len: length + * + * The index is recorded as a linked list which is sorted and used to create + * the bottom level of the on-flash index tree. The remaining levels of the + * index tree are each built from the level below. + */ +struct idx_entry { + struct list_head list; + union ubifs_key key; + char *name; + int name_len; + int lnum; + int offs; + int len; +}; + +static int init_rebuild_info(struct ubifs_info *c) +{ + int err; + + c->sbuf = vmalloc(c->leb_size); + if (!c->sbuf) { + log_err(c, errno, "can not allocate sbuf"); + return -ENOMEM; + } + FSCK(c)->rebuild = kzalloc(sizeof(struct ubifs_rebuild_info), + GFP_KERNEL); + if (!FSCK(c)->rebuild) { + err = -ENOMEM; + log_err(c, errno, "can not allocate rebuild info"); + goto free_sbuf; + } + FSCK(c)->scanned_files = RB_ROOT; + FSCK(c)->used_lebs = kcalloc(BITS_TO_LONGS(c->main_lebs), + sizeof(unsigned long), GFP_KERNEL); + if (!FSCK(c)->used_lebs) { + err = -ENOMEM; + log_err(c, errno, "can not allocate bitmap of used lebs"); + goto free_rebuild; + } + FSCK(c)->lpts = kzalloc(sizeof(struct ubifs_lprops) * c->main_lebs, + GFP_KERNEL); + if (!FSCK(c)->lpts) { + err = -ENOMEM; + log_err(c, errno, "can not allocate lpts"); + goto free_used_lebs; + } + FSCK(c)->rebuild->write_buf = vmalloc(c->leb_size); + if (!FSCK(c)->rebuild->write_buf) { + err = -ENOMEM; + goto free_lpts; + } + FSCK(c)->rebuild->head_lnum = -1; + + return 0; + +free_lpts: + kfree(FSCK(c)->lpts); +free_used_lebs: + kfree(FSCK(c)->used_lebs); +free_rebuild: + kfree(FSCK(c)->rebuild); +free_sbuf: + vfree(c->sbuf); + return err; +} + +static void destroy_rebuild_info(struct ubifs_info *c) +{ + vfree(FSCK(c)->rebuild->write_buf); + kfree(FSCK(c)->lpts); + kfree(FSCK(c)->used_lebs); + kfree(FSCK(c)->rebuild); + vfree(c->sbuf); +} + +/** + * insert_or_update_ino_node - insert or update inode node. + * @c: UBIFS file-system description object + * @new_ino: new inode node + * @tree: a tree to record valid/deleted inode node info + * + * This function inserts @new_ino into the @tree, or updates inode node + * if it already exists in the tree. Returns zero in case of success, a + * negative error code in case of failure. + */ +static int insert_or_update_ino_node(struct ubifs_info *c, + struct scanned_ino_node *new_ino, + struct rb_root *tree) +{ + int cmp; + struct scanned_ino_node *ino_node, *old_ino_node = NULL; + struct rb_node **p, *parent = NULL; + + p = &tree->rb_node; + while (*p) { + parent = *p; + ino_node = rb_entry(parent, struct scanned_ino_node, rb); + cmp = keys_cmp(c, &new_ino->key, &ino_node->key); + if (cmp < 0) { + p = &(*p)->rb_left; + } else if (cmp > 0) { + p = &(*p)->rb_right; + } else { + old_ino_node = ino_node; + break; + } + } + if (old_ino_node) { + if (old_ino_node->header.sqnum < new_ino->header.sqnum) { + size_t len = offsetof(struct scanned_ino_node, rb); + + memcpy(old_ino_node, new_ino, len); + } + return 0; + } + + ino_node = kmalloc(sizeof(struct scanned_ino_node), GFP_KERNEL); + if (!ino_node) + return -ENOMEM; + + *ino_node = *new_ino; + rb_link_node(&ino_node->rb, parent, p); + rb_insert_color(&ino_node->rb, tree); + + return 0; +} + +static int namecmp(const char *a, int la, const char *b, int lb) +{ + int cmp, len = min(la, lb); + + cmp = memcmp(a, b, len); + if (cmp) + return cmp; + + return la - lb; +} + +/** + * insert_or_update_dent_node - insert or update dentry node. + * @c: UBIFS file-system description object + * @new_dent: new dentry node + * @tree: a tree to record valid/deleted dentry node info + * + * This function inserts @new_dent into the @tree, or updates dent node + * if it already exists in the tree. Returns zero in case of success, a + * negative error code in case of failure. + */ +static int insert_or_update_dent_node(struct ubifs_info *c, + struct scanned_dent_node *new_dent, + struct rb_root *tree) +{ + int cmp; + struct scanned_dent_node *dent_node, *old_dent_node = NULL; + struct rb_node **p, *parent = NULL; + + p = &tree->rb_node; + while (*p) { + parent = *p; + dent_node = rb_entry(parent, struct scanned_dent_node, rb); + cmp = keys_cmp(c, &new_dent->key, &dent_node->key); + if (cmp < 0) { + p = &(*p)->rb_left; + } else if (cmp > 0) { + p = &(*p)->rb_right; + } else { + cmp = namecmp(new_dent->name, new_dent->nlen, + dent_node->name, dent_node->nlen); + if (cmp < 0) { + p = &(*p)->rb_left; + } else if (cmp > 0) { + p = &(*p)->rb_right; + } else { + old_dent_node = dent_node; + break; + } + } + } + if (old_dent_node) { + if (old_dent_node->header.sqnum < new_dent->header.sqnum) { + size_t len = offsetof(struct scanned_dent_node, rb); + + memcpy(old_dent_node, new_dent, len); + } + return 0; + } + + dent_node = kmalloc(sizeof(struct scanned_dent_node), GFP_KERNEL); + if (!dent_node) + return -ENOMEM; + + *dent_node = *new_dent; + rb_link_node(&dent_node->rb, parent, p); + rb_insert_color(&dent_node->rb, tree); + + return 0; +} + +/** + * process_scanned_node - process scanned node. + * @c: UBIFS file-system description object + * @lnum: logical eraseblock number + * @snod: scanned node + * @si: records nodes and files information during scanning + * + * This function parses, checks and records scanned node information. + * Returns zero in case of success, 1% if the scanned LEB doesn't hold file + * data and should be ignored(eg. index LEB), a negative error code in case + * of failure. + */ +static int process_scanned_node(struct ubifs_info *c, int lnum, + struct ubifs_scan_node *snod, + struct scanned_info *si) +{ + ino_t inum; + int offs = snod->offs; + void *node = snod->node; + union ubifs_key *key = &snod->key; + struct rb_root *tree; + struct scanned_node *sn; + struct scanned_ino_node ino_node; + struct scanned_dent_node dent_node; + struct scanned_data_node data_node; + struct scanned_trun_node trun_node; + + switch (snod->type) { + case UBIFS_INO_NODE: + { + if (!parse_ino_node(c, lnum, offs, node, key, &ino_node)) + return 0; + + tree = &si->del_inos; + if (ino_node.nlink) + tree = &si->valid_inos; + return insert_or_update_ino_node(c, &ino_node, tree); + } + case UBIFS_DENT_NODE: + case UBIFS_XENT_NODE: + { + if (!parse_dent_node(c, lnum, offs, node, key, &dent_node)) + return 0; + + tree = &si->del_dents; + if (dent_node.inum) + tree = &si->valid_dents; + return insert_or_update_dent_node(c, &dent_node, tree); + } + case UBIFS_DATA_NODE: + { + if (!parse_data_node(c, lnum, offs, node, key, &data_node)) + return 0; + + inum = key_inum(c, key); + sn = (struct scanned_node *)&data_node; + break; + } + case UBIFS_TRUN_NODE: + { + if (!parse_trun_node(c, lnum, offs, node, key, &trun_node)) + return 0; + + inum = le32_to_cpu(((struct ubifs_trun_node *)node)->inum); + sn = (struct scanned_node *)&trun_node; + break; + } + default: + dbg_fsck("skip node type %d, at %d:%d, in %s", + snod->type, lnum, offs, c->dev_name); + return 1; + } + + tree = &FSCK(c)->scanned_files; + return insert_or_update_file(c, tree, sn, key_type(c, key), inum); +} + +/** + * destroy_scanned_info - destroy scanned nodes. + * @c: UBIFS file-system description object + * @si: records nodes and files information during scanning + * + * Destroy scanned files and all data/dentry nodes attached to file, destroy + * valid/deleted inode/dentry info. + */ +static void destroy_scanned_info(struct ubifs_info *c, struct scanned_info *si) +{ + struct scanned_ino_node *ino_node; + struct scanned_dent_node *dent_node; + struct rb_node *this; + + destroy_file_tree(c, &FSCK(c)->scanned_files); + + this = rb_first(&si->valid_inos); + while (this) { + ino_node = rb_entry(this, struct scanned_ino_node, rb); + this = rb_next(this); + + rb_erase(&ino_node->rb, &si->valid_inos); + kfree(ino_node); + } + + this = rb_first(&si->del_inos); + while (this) { + ino_node = rb_entry(this, struct scanned_ino_node, rb); + this = rb_next(this); + + rb_erase(&ino_node->rb, &si->del_inos); + kfree(ino_node); + } + + this = rb_first(&si->valid_dents); + while (this) { + dent_node = rb_entry(this, struct scanned_dent_node, rb); + this = rb_next(this); + + rb_erase(&dent_node->rb, &si->valid_dents); + kfree(dent_node); + } + + this = rb_first(&si->del_dents); + while (this) { + dent_node = rb_entry(this, struct scanned_dent_node, rb); + this = rb_next(this); + + rb_erase(&dent_node->rb, &si->del_dents); + kfree(dent_node); + } +} + +/** + * scan_nodes - scan node information from flash. + * @c: UBIFS file-system description object + * @si: records nodes and files information during scanning + * + * This function scans nodes from flash, all ino/dent nodes are split + * into valid tree and deleted tree, all trun/data nodes are collected + * into file, the file is inserted into @FSCK(c)->scanned_files. + */ +static int scan_nodes(struct ubifs_info *c, struct scanned_info *si) +{ + int lnum, err = 0; + struct ubifs_scan_leb *sleb; + struct ubifs_scan_node *snod; + + for (lnum = c->main_first; lnum < c->leb_cnt; ++lnum) { + dbg_fsck("scan nodes at LEB %d, in %s", lnum, c->dev_name); + + sleb = ubifs_scan(c, lnum, 0, c->sbuf, 1); + if (IS_ERR(sleb)) { + if (PTR_ERR(sleb) != -EUCLEAN) + return PTR_ERR(sleb); + + sleb = ubifs_recover_leb(c, lnum, 0, c->sbuf, -1); + if (IS_ERR(sleb)) { + if (PTR_ERR(sleb) != -EUCLEAN) + return PTR_ERR(sleb); + + /* This LEB holds corrupted data, abandon it. */ + continue; + } + } + + list_for_each_entry(snod, &sleb->nodes, list) { + if (snod->sqnum > c->max_sqnum) + c->max_sqnum = snod->sqnum; + + err = process_scanned_node(c, lnum, snod, si); + if (err < 0) { + log_err(c, 0, "process node failed at LEB %d, err %d", + lnum, err); + ubifs_scan_destroy(sleb); + goto out; + } else if (err == 1) { + err = 0; + break; + } + } + + ubifs_scan_destroy(sleb); + } + +out: + return err; +} + +static struct scanned_ino_node * +lookup_valid_ino_node(struct ubifs_info *c, struct scanned_info *si, + struct scanned_ino_node *target) +{ + int cmp; + struct scanned_ino_node *ino_node; + struct rb_node *p; + + p = si->valid_inos.rb_node; + while (p) { + ino_node = rb_entry(p, struct scanned_ino_node, rb); + cmp = keys_cmp(c, &target->key, &ino_node->key); + if (cmp < 0) { + p = p->rb_left; + } else if (cmp > 0) { + p = p->rb_right; + } else { + if (target->header.sqnum > ino_node->header.sqnum) + return ino_node; + else + return NULL; + } + } + + return NULL; +} + +static struct scanned_dent_node * +lookup_valid_dent_node(struct ubifs_info *c, struct scanned_info *si, + struct scanned_dent_node *target) +{ + int cmp; + struct scanned_dent_node *dent_node; + struct rb_node *p; + + p = si->valid_dents.rb_node; + while (p) { + dent_node = rb_entry(p, struct scanned_dent_node, rb); + cmp = keys_cmp(c, &target->key, &dent_node->key); + if (cmp < 0) { + p = p->rb_left; + } else if (cmp > 0) { + p = p->rb_right; + } else { + cmp = namecmp(target->name, target->nlen, + dent_node->name, dent_node->nlen); + if (cmp < 0) { + p = p->rb_left; + } else if (cmp > 0) { + p = p->rb_right; + } else { + if (target->header.sqnum > + dent_node->header.sqnum) + return dent_node; + else + return NULL; + } + } + } + + return NULL; +} + +static void update_lpt(struct ubifs_info *c, struct scanned_node *sn, + bool deleted) +{ + int index = sn->lnum - c->main_first; + int pos = sn->offs + ALIGN(sn->len, 8); + + set_bit(index, FSCK(c)->used_lebs); + FSCK(c)->lpts[index].end = max_t(int, FSCK(c)->lpts[index].end, pos); + + if (deleted) + return; + + FSCK(c)->lpts[index].used += ALIGN(sn->len, 8); +} + +/** + * remove_del_nodes - remove deleted nodes from valid node tree. + * @c: UBIFS file-system description object + * @si: records nodes and files information during scanning + * + * This function compares sqnum between deleted node and corresponding valid + * node, removes valid node from tree if the sqnum of deleted node is bigger. + * Deleted ino/dent nodes will be removed from @si->del_inos/@si->del_dents + * after this function finished. + */ +static void remove_del_nodes(struct ubifs_info *c, struct scanned_info *si) +{ + struct scanned_ino_node *del_ino_node, *valid_ino_node; + struct scanned_dent_node *del_dent_node, *valid_dent_node; + struct rb_node *this; + + this = rb_first(&si->del_inos); + while (this) { + del_ino_node = rb_entry(this, struct scanned_ino_node, rb); + this = rb_next(this); + + valid_ino_node = lookup_valid_ino_node(c, si, del_ino_node); + if (valid_ino_node) { + update_lpt(c, &del_ino_node->header, true); + rb_erase(&valid_ino_node->rb, &si->valid_inos); + kfree(valid_ino_node); + } + + rb_erase(&del_ino_node->rb, &si->del_inos); + kfree(del_ino_node); + } + + this = rb_first(&si->del_dents); + while (this) { + del_dent_node = rb_entry(this, struct scanned_dent_node, rb); + this = rb_next(this); + + valid_dent_node = lookup_valid_dent_node(c, si, del_dent_node); + if (valid_dent_node) { + update_lpt(c, &del_dent_node->header, true); + rb_erase(&valid_dent_node->rb, &si->valid_dents); + kfree(valid_dent_node); + } + + rb_erase(&del_dent_node->rb, &si->del_dents); + kfree(del_dent_node); + } +} + +/** + * add_valid_nodes_into_file - add valid nodes into file. + * @c: UBIFS file-system description object + * @si: records nodes and files information during scanning + * + * This function adds valid nodes into corresponding file, all valid ino/dent + * nodes will be removed from @si->valid_inos/@si->valid_dents if the function + * is executed successfully. + */ +static int add_valid_nodes_into_file(struct ubifs_info *c, + struct scanned_info *si) +{ + int err, type; + ino_t inum; + struct scanned_node *sn; + struct scanned_ino_node *ino_node; + struct scanned_dent_node *dent_node; + struct rb_node *this; + struct rb_root *tree = &FSCK(c)->scanned_files; + + this = rb_first(&si->valid_inos); + while (this) { + ino_node = rb_entry(this, struct scanned_ino_node, rb); + this = rb_next(this); + + sn = (struct scanned_node *)ino_node; + type = key_type(c, &ino_node->key); + inum = key_inum(c, &ino_node->key); + err = insert_or_update_file(c, tree, sn, type, inum); + if (err) + return err; + + rb_erase(&ino_node->rb, &si->valid_inos); + kfree(ino_node); + } + + this = rb_first(&si->valid_dents); + while (this) { + dent_node = rb_entry(this, struct scanned_dent_node, rb); + this = rb_next(this); + + sn = (struct scanned_node *)dent_node; + inum = dent_node->inum; + type = key_type(c, &dent_node->key); + err = insert_or_update_file(c, tree, sn, type, inum); + if (err) + return err; + + rb_erase(&dent_node->rb, &si->valid_dents); + kfree(dent_node); + } + + return 0; +} + +/** + * filter_invalid_files - filter out invalid files. + * @c: UBIFS file-system description object + * + * This function filters out invalid files(eg. inconsistent types between + * inode and dentry node, or missing inode/dentry node, or encrypted inode + * has no encryption related xattrs, etc.). + */ +static void filter_invalid_files(struct ubifs_info *c) +{ + struct rb_node *node; + struct scanned_file *file; + struct rb_root *tree = &FSCK(c)->scanned_files; + LIST_HEAD(tmp_list); + + /* Add all xattr files into a list. */ + for (node = rb_first(tree); node; node = rb_next(node)) { + file = rb_entry(node, struct scanned_file, rb); + + if (file->ino.is_xattr) + list_add(&file->list, &tmp_list); + } + + /* + * Round 1: Traverse xattr files, check whether the xattr file is + * valid, move valid xattr file into corresponding host file's subtree. + */ + while (!list_empty(&tmp_list)) { + file = list_entry(tmp_list.next, struct scanned_file, list); + + list_del(&file->list); + rb_erase(&file->rb, tree); + if (!file_is_valid(c, file, tree, NULL)) { + destroy_file_content(c, file); + kfree(file); + } + } + + /* Round 2: Traverse non-xattr files. */ + for (node = rb_first(tree); node; node = rb_next(node)) { + file = rb_entry(node, struct scanned_file, rb); + + if (!file_is_valid(c, file, tree, NULL)) + list_add(&file->list, &tmp_list); + } + + /* Remove invalid files. */ + while (!list_empty(&tmp_list)) { + file = list_entry(tmp_list.next, struct scanned_file, list); + + list_del(&file->list); + destroy_file_content(c, file); + rb_erase(&file->rb, tree); + kfree(file); + } +} + +/** + * extract_dentry_tree - extract reachable directory entries. + * @c: UBIFS file-system description object + * + * This function iterates all directory entries and remove those + * unreachable ones. 'Unreachable' means that a directory entry can + * not be searched from '/'. + */ +static void extract_dentry_tree(struct ubifs_info *c) +{ + struct rb_node *node; + struct scanned_file *file; + struct rb_root *tree = &FSCK(c)->scanned_files; + LIST_HEAD(unreachable); + + for (node = rb_first(tree); node; node = rb_next(node)) { + file = rb_entry(node, struct scanned_file, rb); + + /* + * Since all xattr files are already attached to corresponding + * host file, there are only non-xattr files in the file tree. + */ + ubifs_assert(c, !file->ino.is_xattr); + if (!file_is_reachable(c, file, tree)) + list_add(&file->list, &unreachable); + } + + /* Remove unreachable files. */ + while (!list_empty(&unreachable)) { + file = list_entry(unreachable.next, struct scanned_file, list); + + dbg_fsck("remove unreachable file %lu, in %s", + file->inum, c->dev_name); + list_del(&file->list); + destroy_file_content(c, file); + rb_erase(&file->rb, tree); + kfree(file); + } +} + +static void init_root_ino(struct ubifs_info *c, struct ubifs_ino_node *ino) +{ + __le64 tmp_le64; + + /* Create default root inode */ + ino_key_init_flash(c, &ino->key, UBIFS_ROOT_INO); + ino->ch.node_type = UBIFS_INO_NODE; + ino->creat_sqnum = cpu_to_le64(++c->max_sqnum); + ino->nlink = cpu_to_le32(2); + tmp_le64 = cpu_to_le64(time(NULL)); + ino->atime_sec = tmp_le64; + ino->ctime_sec = tmp_le64; + ino->mtime_sec = tmp_le64; + ino->atime_nsec = 0; + ino->ctime_nsec = 0; + ino->mtime_nsec = 0; + ino->mode = cpu_to_le32(S_IFDIR | S_IRUGO | S_IWUSR | S_IXUGO); + ino->size = cpu_to_le64(UBIFS_INO_NODE_SZ); + /* Set compression enabled by default */ + ino->flags = cpu_to_le32(UBIFS_COMPR_FL); +} + +/** + * flush_write_buf - flush write buffer. + * @c: UBIFS file-system description object + * + * This function flush write buffer to LEB @FSCK(c)->rebuild->head_lnum, then + * set @FSCK(c)->rebuild->head_lnum to '-1'. + */ +static int flush_write_buf(struct ubifs_info *c) +{ + int len, pad, err; + + if (!FSCK(c)->rebuild->head_offs) + return 0; + + len = ALIGN(FSCK(c)->rebuild->head_offs, c->min_io_size); + pad = len - FSCK(c)->rebuild->head_offs; + if (pad) + ubifs_pad(c, FSCK(c)->rebuild->write_buf + + FSCK(c)->rebuild->head_offs, pad); + + err = ubifs_leb_write(c, FSCK(c)->rebuild->head_lnum, + FSCK(c)->rebuild->write_buf, 0, len); + if (err) + return err; + + if (FSCK(c)->rebuild->need_update_lpt) { + int index = FSCK(c)->rebuild->head_lnum - c->main_first; + + FSCK(c)->lpts[index].free = c->leb_size - len; + FSCK(c)->lpts[index].dirty = pad; + FSCK(c)->lpts[index].flags = LPROPS_INDEX; + } + + FSCK(c)->rebuild->head_lnum = -1; + + return 0; +} + +/** + * reserve_space - reserve enough space to write data. + * @c: UBIFS file-system description object + * @len: the length of written data + * @lnum: the write LEB number is returned here + * @offs: the write pos in LEB is returned here + * + * This function finds target position <@lnum, @offs> to write data with + * length of @len. + */ +static int reserve_space(struct ubifs_info *c, int len, int *lnum, int *offs) +{ + int err, new_lnum; + + if (FSCK(c)->rebuild->head_lnum == -1) { +get_new: + new_lnum = get_free_leb(c); + if (new_lnum < 0) + return new_lnum; + + err = ubifs_leb_unmap(c, new_lnum); + if (err) + return err; + + FSCK(c)->rebuild->head_lnum = new_lnum; + FSCK(c)->rebuild->head_offs = 0; + } + + if (len > c->leb_size - FSCK(c)->rebuild->head_offs) { + err = flush_write_buf(c); + if (err) + return err; + + goto get_new; + } + + *lnum = FSCK(c)->rebuild->head_lnum; + *offs = FSCK(c)->rebuild->head_offs; + FSCK(c)->rebuild->head_offs += ALIGN(len, 8); + + return 0; +} + +static void copy_node_data(struct ubifs_info *c, void *node, int offs, int len) +{ + memcpy(FSCK(c)->rebuild->write_buf + offs, node, len); + memset(FSCK(c)->rebuild->write_buf + offs + len, 0xff, ALIGN(len, 8) - len); +} + +/** + * create_root - create root dir. + * @c: UBIFS file-system description object + * + * This function creates root dir. + */ +static int create_root(struct ubifs_info *c) +{ + int err, lnum, offs; + struct ubifs_ino_node *ino; + struct scanned_file *file; + + ino = kzalloc(ALIGN(UBIFS_INO_NODE_SZ, c->min_io_size), GFP_KERNEL); + if (!ino) + return -ENOMEM; + + c->max_sqnum = 0; + c->highest_inum = UBIFS_FIRST_INO; + init_root_ino(c, ino); + err = ubifs_prepare_node_hmac(c, ino, UBIFS_INO_NODE_SZ, -1, 1); + if (err) + goto out; + + err = reserve_space(c, UBIFS_INO_NODE_SZ, &lnum, &offs); + if (err) + goto out; + + copy_node_data(c, ino, offs, UBIFS_INO_NODE_SZ); + + err = flush_write_buf(c); + if (err) + goto out; + + file = kzalloc(sizeof(struct scanned_file), GFP_KERNEL); + if (!file) { + err = -ENOMEM; + goto out; + } + + file->inum = UBIFS_ROOT_INO; + file->dent_nodes = RB_ROOT; + file->data_nodes = RB_ROOT; + INIT_LIST_HEAD(&file->list); + + file->ino.header.exist = true; + file->ino.header.lnum = lnum; + file->ino.header.offs = offs; + file->ino.header.len = UBIFS_INO_NODE_SZ; + file->ino.header.sqnum = le64_to_cpu(ino->ch.sqnum); + ino_key_init(c, &file->ino.key, UBIFS_ROOT_INO); + file->ino.is_xattr = le32_to_cpu(ino->flags) & UBIFS_XATTR_FL; + file->ino.mode = le32_to_cpu(ino->mode); + file->calc_nlink = file->ino.nlink = le32_to_cpu(ino->nlink); + file->calc_xcnt = file->ino.xcnt = le32_to_cpu(ino->xattr_cnt); + file->calc_xsz = file->ino.xsz = le32_to_cpu(ino->xattr_size); + file->calc_xnms = file->ino.xnms = le32_to_cpu(ino->xattr_names); + file->calc_size = file->ino.size = le64_to_cpu(ino->size); + + rb_link_node(&file->rb, NULL, &FSCK(c)->scanned_files.rb_node); + rb_insert_color(&file->rb, &FSCK(c)->scanned_files); + +out: + kfree(ino); + return err; +} + +static const char *get_file_name(struct ubifs_info *c, struct scanned_file *file) +{ + static char name[UBIFS_MAX_NLEN + 1]; + struct rb_node *node; + struct scanned_dent_node *dent_node; + + node = rb_first(&file->dent_nodes); + if (!node) { + ubifs_assert(c, file->inum == UBIFS_ROOT_INO); + return "/"; + } + + if (c->encrypted && !file->ino.is_xattr) + /* Encrypted file name. */ + return "<encrypted>"; + + /* Get name from any one dentry. */ + dent_node = rb_entry(node, struct scanned_dent_node, rb); + memcpy(name, dent_node->name, dent_node->nlen); + /* @dent->name could be non '\0' terminated. */ + name[dent_node->nlen] = '\0'; + return name; +} + +static int parse_node_info(struct ubifs_info *c, struct scanned_node *sn, + union ubifs_key *key, char *name, int name_len, + struct list_head *idx_list, int *idx_cnt) +{ + struct idx_entry *e; + + update_lpt(c, sn, idx_cnt == NULL); + + if (idx_cnt == NULL) + /* Skip truncation node. */ + return 0; + + e = kmalloc(sizeof(struct idx_entry), GFP_KERNEL); + if (!e) + return -ENOMEM; + + key_copy(c, key, &e->key); + e->name = name; + e->name_len = name_len; + e->lnum = sn->lnum; + e->offs = sn->offs; + e->len = sn->len; + list_add_tail(&e->list, idx_list); + *idx_cnt = *idx_cnt + 1; + + return 0; +} + +static int add_idx_node(struct ubifs_info *c, struct ubifs_idx_node *idx, + union ubifs_key *key, int child_cnt, + struct idx_entry *e) +{ + int err, lnum, offs, len; + + len = ubifs_idx_node_sz(c, child_cnt); + ubifs_prepare_node(c, idx, len, 0); + + err = reserve_space(c, len, &lnum, &offs); + if (err) + return err; + + copy_node_data(c, idx, offs, len); + + c->calc_idx_sz += ALIGN(len, 8); + + /* The last index node written will be the root */ + c->zroot.lnum = lnum; + c->zroot.offs = offs; + c->zroot.len = len; + + key_copy(c, key, &e->key); + e->lnum = lnum; + e->offs = offs; + e->len = len; + + return err; +} + +static int cmp_idx(void *priv, const struct list_head *a, + const struct list_head *b) +{ + int cmp; + struct ubifs_info *c = priv; + struct idx_entry *ia, *ib; + + if (a == b) + return 0; + + ia = list_entry(a, struct idx_entry, list); + ib = list_entry(b, struct idx_entry, list); + + cmp = keys_cmp(c, &ia->key, &ib->key); + if (cmp) + return cmp; + + return namecmp(ia->name, ia->name_len, ib->name, ib->name_len); +} + +/** + * build_tnc - construct TNC and write it into flash. + * @c: UBIFS file-system description object + * @lower_idxs: leaf entries of TNC + * @lower_cnt: the count of @lower_idxs + * + * This function builds TNC according to @lower_idxs and writes all index + * nodes into flash. + */ +static int build_tnc(struct ubifs_info *c, struct list_head *lower_idxs, + int lower_cnt) +{ + int i, j, err, upper_cnt, child_cnt, idx_sz, level = 0; + struct idx_entry *pe, *tmp_e, *e = NULL; + struct ubifs_idx_node *idx; + struct ubifs_branch *br; + union ubifs_key key; + LIST_HEAD(upper_idxs); + + idx_sz = ubifs_idx_node_sz(c, c->fanout); + idx = kmalloc(idx_sz, GFP_KERNEL); + if (!idx) + return -ENOMEM; + + list_sort(c, lower_idxs, cmp_idx); + FSCK(c)->rebuild->need_update_lpt = true; + + ubifs_assert(c, lower_cnt != 0); + + do { + upper_cnt = lower_cnt / c->fanout; + if (lower_cnt % c->fanout) + upper_cnt += 1; + e = list_first_entry(lower_idxs, struct idx_entry, list); + + for (i = 0; i < upper_cnt; i++) { + if (i == upper_cnt - 1) { + child_cnt = lower_cnt % c->fanout; + if (child_cnt == 0) + child_cnt = c->fanout; + } else + child_cnt = c->fanout; + + key_copy(c, &e->key, &key); + memset(idx, 0, idx_sz); + idx->ch.node_type = UBIFS_IDX_NODE; + idx->child_cnt = cpu_to_le16(child_cnt); + idx->level = cpu_to_le16(level); + for (j = 0; j < child_cnt; j++) { + ubifs_assert(c, + !list_entry_is_head(e, lower_idxs, list)); + br = ubifs_idx_branch(c, idx, j); + key_write_idx(c, &e->key, &br->key); + br->lnum = cpu_to_le32(e->lnum); + br->offs = cpu_to_le32(e->offs); + br->len = cpu_to_le32(e->len); + e = list_next_entry(e, list); + } + + pe = kmalloc(sizeof(struct idx_entry), GFP_KERNEL); + if (!pe) { + err = -ENOMEM; + goto out; + } + + err = add_idx_node(c, idx, &key, child_cnt, pe); + if (err) { + kfree(pe); + goto out; + } + + list_add_tail(&pe->list, &upper_idxs); + } + + level++; + list_for_each_entry_safe(e, tmp_e, lower_idxs, list) { + list_del(&e->list); + kfree(e); + } + list_splice_init(&upper_idxs, lower_idxs); + lower_cnt = upper_cnt; + } while (lower_cnt > 1); + + /* Set the index head */ + c->ihead_lnum = FSCK(c)->rebuild->head_lnum; + c->ihead_offs = ALIGN(FSCK(c)->rebuild->head_offs, c->min_io_size); + + /* Flush the last index LEB */ + err = flush_write_buf(c); + FSCK(c)->rebuild->need_update_lpt = false; + +out: + list_for_each_entry_safe(e, tmp_e, lower_idxs, list) { + list_del(&e->list); + kfree(e); + } + list_for_each_entry_safe(e, tmp_e, &upper_idxs, list) { + list_del(&e->list); + kfree(e); + } + kfree(idx); + return err; +} + +static int record_file_used_lebs(struct ubifs_info *c, + struct scanned_file *file, + struct list_head *idx_list, int *idx_cnt) +{ + int err; + struct rb_node *node; + struct scanned_file *xattr_file; + struct scanned_dent_node *dent_node; + struct scanned_data_node *data_node; + + dbg_fsck("recovered file(inum:%lu name:%s type:%s), in %s", + file->inum, get_file_name(c, file), + file->ino.is_xattr ? "xattr" : + ubifs_get_type_name(ubifs_get_dent_type(file->ino.mode)), + c->dev_name); + c->highest_inum = max_t(ino_t, c->highest_inum, file->inum); + + err = parse_node_info(c, &file->ino.header, &file->ino.key, + NULL, 0, idx_list, idx_cnt); + if (err) + return err; + + if (file->trun.header.exist) { + err = parse_node_info(c, &file->trun.header, NULL, NULL, + 0, idx_list, NULL); + if (err) + return err; + } + + for (node = rb_first(&file->data_nodes); node; node = rb_next(node)) { + data_node = rb_entry(node, struct scanned_data_node, rb); + + err = parse_node_info(c, &data_node->header, &data_node->key, + NULL, 0, idx_list, idx_cnt); + if (err) + return err; + } + + for (node = rb_first(&file->dent_nodes); node; node = rb_next(node)) { + dent_node = rb_entry(node, struct scanned_dent_node, rb); + + err = parse_node_info(c, &dent_node->header, &dent_node->key, + dent_node->name, dent_node->nlen, + idx_list, idx_cnt); + if (err) + return err; + } + + for (node = rb_first(&file->xattr_files); node; node = rb_next(node)) { + xattr_file = rb_entry(node, struct scanned_file, rb); + + err = record_file_used_lebs(c, xattr_file, idx_list, idx_cnt); + if (err) + return err; + } + + return err; +} + +/** + * traverse_files_and_nodes - traverse all nodes from valid files. + * @c: UBIFS file-system description object + * + * This function traverses all nodes from valid files and does following + * things: + * 1. If there are no scanned files, create default empty filesystem. + * 2. Record all used LEBs which may hold useful nodes, then left unused + * LEBs could be taken for storing new index tree. + * 3. Re-write data to prevent failed gc scanning in the subsequent mounting + * process caused by corrupted data. + * 4. Build TNC. + */ +static int traverse_files_and_nodes(struct ubifs_info *c) +{ + int i, err = 0, idx_cnt = 0; + struct rb_node *node; + struct scanned_file *file; + struct rb_root *tree = &FSCK(c)->scanned_files; + struct idx_entry *ie, *tmp_ie; + LIST_HEAD(idx_list); + + if (rb_first(tree) == NULL) { + /* No scanned files. Create root dir. */ + log_out(c, "No files found, create empty filesystem"); + err = create_root(c); + if (err) + return err; + } + + log_out(c, "Record used LEBs"); + for (node = rb_first(tree); node; node = rb_next(node)) { + file = rb_entry(node, struct scanned_file, rb); + + err = record_file_used_lebs(c, file, &idx_list, &idx_cnt); + if (err) + goto out_idx_list; + } + + /* Re-write data. */ + log_out(c, "Re-write data"); + for (i = 0; i < c->main_lebs; ++i) { + int lnum, len, end; + + if (!test_bit(i, FSCK(c)->used_lebs)) + continue; + + lnum = i + c->main_first; + dbg_fsck("re-write LEB %d, in %s", lnum, c->dev_name); + + end = FSCK(c)->lpts[i].end; + len = ALIGN(end, c->min_io_size); + + err = ubifs_leb_read(c, lnum, c->sbuf, 0, len, 0); + if (err && err != -EBADMSG) + goto out_idx_list; + + if (len > end) + ubifs_pad(c, c->sbuf + end, len - end); + + err = ubifs_leb_change(c, lnum, c->sbuf, len); + if (err) + goto out_idx_list; + } + + /* Build TNC. */ + log_out(c, "Build TNC"); + err = build_tnc(c, &idx_list, idx_cnt); + +out_idx_list: + list_for_each_entry_safe(ie, tmp_ie, &idx_list, list) { + list_del(&ie->list); + kfree(ie); + } + return err; +} + +static int calculate_lp(struct ubifs_info *c, int index, int *free, int *dirty, + __unused int *is_idx) +{ + if (!test_bit(index, FSCK(c)->used_lebs) || + c->gc_lnum == index + c->main_first) { + *free = c->leb_size; + *dirty = 0; + } else if (FSCK(c)->lpts[index].flags & LPROPS_INDEX) { + *free = FSCK(c)->lpts[index].free; + *dirty = FSCK(c)->lpts[index].dirty; + } else { + int len = ALIGN(FSCK(c)->lpts[index].end, c->min_io_size); + + *free = c->leb_size - len; + *dirty = len - FSCK(c)->lpts[index].used; + + if (*dirty == c->leb_size) { + *free = c->leb_size; + *dirty = 0; + } + } + + return 0; +} + +/** + * clean_log - clean up log area. + * @c: UBIFS file-system description object + * + * This function cleans up log area, since there is no need to do recovery + * in next mounting. + */ +static int clean_log(struct ubifs_info *c) +{ + int lnum, err; + struct ubifs_cs_node *cs; + + for (lnum = UBIFS_LOG_LNUM; lnum <= c->log_last; lnum++) { + err = ubifs_leb_unmap(c, lnum); + if (err) + return err; + } + + cs = kzalloc(ALIGN(UBIFS_CS_NODE_SZ, c->min_io_size), GFP_KERNEL); + if (!cs) + return -ENOMEM; + + cs->ch.node_type = UBIFS_CS_NODE; + cs->cmt_no = cpu_to_le64(0); + + err = ubifs_write_node(c, cs, UBIFS_CS_NODE_SZ, UBIFS_LOG_LNUM, 0); + kfree(cs); + if (err) + return err; + + return 0; +} + +/** + * write_master - write master nodes. + * @c: UBIFS file-system description object + * + * This function updates meta information into master node and writes master + * node into master area. + */ +static int write_master(struct ubifs_info *c) +{ + int err, lnum; + struct ubifs_mst_node *mst; + + mst = kzalloc(c->mst_node_alsz, GFP_KERNEL); + if (!mst) + return -ENOMEM; + + mst->ch.node_type = UBIFS_MST_NODE; + mst->log_lnum = cpu_to_le32(UBIFS_LOG_LNUM); + mst->highest_inum = cpu_to_le64(c->highest_inum); + mst->cmt_no = 0; + mst->root_lnum = cpu_to_le32(c->zroot.lnum); + mst->root_offs = cpu_to_le32(c->zroot.offs); + mst->root_len = cpu_to_le32(c->zroot.len); + mst->gc_lnum = cpu_to_le32(c->gc_lnum); + mst->ihead_lnum = cpu_to_le32(c->ihead_lnum); + mst->ihead_offs = cpu_to_le32(c->ihead_offs); + mst->index_size = cpu_to_le64(c->calc_idx_sz); + mst->lpt_lnum = cpu_to_le32(c->lpt_lnum); + mst->lpt_offs = cpu_to_le32(c->lpt_offs); + mst->nhead_lnum = cpu_to_le32(c->nhead_lnum); + mst->nhead_offs = cpu_to_le32(c->nhead_offs); + mst->ltab_lnum = cpu_to_le32(c->ltab_lnum); + mst->ltab_offs = cpu_to_le32(c->ltab_offs); + mst->lsave_lnum = cpu_to_le32(c->lsave_lnum); + mst->lsave_offs = cpu_to_le32(c->lsave_offs); + mst->lscan_lnum = cpu_to_le32(c->main_first); + mst->empty_lebs = cpu_to_le32(c->lst.empty_lebs); + mst->idx_lebs = cpu_to_le32(c->lst.idx_lebs); + mst->leb_cnt = cpu_to_le32(c->leb_cnt); + mst->total_free = cpu_to_le64(c->lst.total_free); + mst->total_dirty = cpu_to_le64(c->lst.total_dirty); + mst->total_used = cpu_to_le64(c->lst.total_used); + mst->total_dead = cpu_to_le64(c->lst.total_dead); + mst->total_dark = cpu_to_le64(c->lst.total_dark); + mst->flags |= cpu_to_le32(UBIFS_MST_NO_ORPHS); + + lnum = UBIFS_MST_LNUM; + err = ubifs_leb_unmap(c, lnum); + if (err) + goto out; + err = ubifs_write_node_hmac(c, mst, UBIFS_MST_NODE_SZ, lnum, 0, + offsetof(struct ubifs_mst_node, hmac)); + if (err) + goto out; + lnum++; + err = ubifs_leb_unmap(c, lnum); + if (err) + goto out; + err = ubifs_write_node_hmac(c, mst, UBIFS_MST_NODE_SZ, lnum, 0, + offsetof(struct ubifs_mst_node, hmac)); + if (err) + goto out; + +out: + kfree(mst); + + return err; +} + +/** + * ubifs_rebuild_filesystem - Rebuild filesystem. + * @c: UBIFS file-system description object + * + * Scanning nodes from UBI volume and rebuild filesystem. Any inconsistent + * problems or corrupted data will be fixed. + */ +int ubifs_rebuild_filesystem(struct ubifs_info *c) +{ + int err = 0; + struct scanned_info si; + + si.valid_inos = si.del_inos = si.valid_dents = si.del_dents = RB_ROOT; + log_out(c, "Start rebuilding filesystem (Notice: dropping data/recovering deleted data can't be awared)"); + FSCK(c)->mode = REBUILD_MODE; + + err = init_rebuild_info(c); + if (err) { + exit_code |= FSCK_ERROR; + return err; + } + + /* Step 1: Scan valid/deleted nodes from volume. */ + log_out(c, "Scan nodes"); + err = scan_nodes(c, &si); + if (err) { + exit_code |= FSCK_ERROR; + goto out; + } + + /* Step 2: Remove deleted nodes from valid node tree. */ + log_out(c, "Remove deleted nodes"); + remove_del_nodes(c, &si); + + /* Step 3: Add valid nodes into file. */ + log_out(c, "Add valid nodes into file"); + err = add_valid_nodes_into_file(c, &si); + if (err) { + exit_code |= FSCK_ERROR; + goto out; + } + + /* Step 4: Drop invalid files. */ + log_out(c, "Filter invalid files"); + filter_invalid_files(c); + + /* Step 5: Extract reachable directory entries. */ + log_out(c, "Extract reachable files"); + extract_dentry_tree(c); + + /* Step 6: Check & correct files' information. */ + log_out(c, "Check & correct file information"); + err = check_and_correct_files(c); + if (err) { + exit_code |= FSCK_ERROR; + goto out; + } + + /* + * Step 7: Record used LEBs. + * Step 8: Re-write data to clean corrupted data. + * Step 9: Build TNC. + */ + err = traverse_files_and_nodes(c); + if (err) { + exit_code |= FSCK_ERROR; + goto out; + } + + /* Step 10. Build LPT. */ + log_out(c, "Build LPT"); + err = build_lpt(c, calculate_lp, true); + if (err) { + exit_code |= FSCK_ERROR; + goto out; + } + + /* Step 11. Clean up log & orphan. */ + log_out(c, "Clean up log & orphan"); + err = clean_log(c); + if (err) { + exit_code |= FSCK_ERROR; + goto out; + } + err = ubifs_clear_orphans(c); + if (err) { + exit_code |= FSCK_ERROR; + goto out; + } + + /* Step 12. Write master node. */ + log_out(c, "Write master"); + err = write_master(c); + if (err) + exit_code |= FSCK_ERROR; + +out: + destroy_scanned_info(c, &si); + destroy_rebuild_info(c); + + return err; +} |