fsck.ubifs: rebuild_fs: Extract reachable directory entries tree

This is the 5/12 step of rebuilding. Extract reachable directory entries
tree. Make sure that all files can be searched from '/', unreachable
file is deleted. So, all files can be accessible in userspace after
reparing.

Signed-off-by: Zhihao Cheng <chengzhihao1@huawei.com>
Signed-off-by: David Oberhollenzer <david.oberhollenzer@sigma-star.at>

1 files changed, 44 insertions, 0 deletions

diff --git a/ubifs-utils/fsck.ubifs/rebuild_fs.c b/ubifs-utils/fsck.ubifs/rebuild_fs.c
index 31f1b3b..669b61d 100644
--- a/ubifs-utils/fsck.ubifs/rebuild_fs.c
+++ b/ubifs-utils/fsck.ubifs/rebuild_fs.c
@@ -588,6 +588,46 @@ static void filter_invalid_files(struct ubifs_info *c)
 }
 
 /**
+ * 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)->rebuild->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);
+	}
+}
+
+/**
  * ubifs_rebuild_filesystem - Rebuild filesystem.
  * @c: UBIFS file-system description object
  *
@@ -633,6 +673,10 @@ int ubifs_rebuild_filesystem(struct ubifs_info *c)
 	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);
+
 out:
 	destroy_scanned_info(c, &si);
 	destroy_rebuild_info(c);