[PATCH RFC 06/17] ubifs: repair: Extract reachable directory entries tree

[Zhihao Cheng]

This is the 6/13 step of repairing. 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@xxxxxxxxxx>
---
 fs/ubifs/repair.c | 143 ++++++++++++++++++++++++++++++++++++++++++++++
 fs/ubifs/repair.h |   4 ++
 2 files changed, 147 insertions(+)

diff --git a/fs/ubifs/repair.c b/fs/ubifs/repair.c
index 5875268135ff..c9435c9aa148 100644
--- a/fs/ubifs/repair.c
+++ b/fs/ubifs/repair.c
@@ -628,6 +628,7 @@ static int update_file(struct ubifs_info *c, struct scanned_file *file,
 	{
 		struct scanned_dent_node *dent = (struct scanned_dent_node *)sn;
 
+		dent->file = file;
 		err = insert_file_dentry(file, dent);
 		break;
 	}
@@ -1315,6 +1316,144 @@ static void filter_invalid_files(struct ubifs_info *c)
 	}
 }
 
+static bool dentry_is_reachable(struct ubifs_info *c,
+				struct scanned_dent_node *dent_node,
+				struct list_head *path_list)
+{
+	struct scanned_file *parent_file = NULL;
+	struct scanned_dent_node *dn, *parent_dent;
+	struct rb_node *p;
+
+	/* Dentry has already been checked as reachable. */
+	if (dent_node->can_be_found)
+		return true;
+
+	/* Check whether the path is cyclical. */
+	list_for_each_entry(dn, path_list, list) {
+		if (dn == dent_node)
+			return false;
+	}
+	dent_node->can_be_found = true;
+	list_add(&dent_node->list, path_list);
+
+	parent_file = lookup_file(c, 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;
+
+	/*
+	 * There are two situations here:
+	 * 1. @file is non-xattr type. Since directory type file has only
+	 *    one dentry, pick first dentry from @parent_file is okay.
+	 * 2. @file is xattr type. Since non-xattr files are checked in
+	 *    first round, so any directory entries from @parent_file must
+	 *    be reachable.
+	 */
+	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_is_reachable - whether the file can be found from '/'.
+ * @c: UBIFS file-system description object
+ * @file: file object
+ *
+ * This function iterates all directory entries in given @file and checks
+ * whether each dentry is reachable. All unreachable directory entries will
+ * be removed.
+ */
+static bool file_is_reachable(struct ubifs_info *c, struct scanned_file *file)
+{
+	struct rb_node *node;
+	struct scanned_dent_node *dent_node;
+
+	if (file->inum == UBIFS_ROOT_INO)
+		return true;
+
+retry:
+	for (node = rb_first(&file->dent_nodes); node; node = rb_next(node)) {
+		LIST_HEAD(path_list);
+
+		cond_resched();
+		dent_node = rb_entry(node, struct scanned_dent_node, rb);
+
+		if (dentry_is_reachable(c, dent_node, &path_list))
+			continue;
+
+		while (!list_empty(&path_list)) {
+			cond_resched();
+			dent_node = list_entry(path_list.next,
+					       struct scanned_dent_node, list);
+
+			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))
+		return false;
+
+	return true;
+}
+
+/**
+ * check_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 found from '/'.
+ */
+static void extract_dentry_tree(struct ubifs_info *c)
+{
+	struct rb_node *node;
+	struct scanned_file *file;
+	LIST_HEAD(unreachable);
+
+	/* Round 1: Iterate non-xattr files. */
+	for (node = rb_first(&c->repair->scanned_files); node;
+	     node = rb_next(node)) {
+		cond_resched();
+		file = rb_entry(node, struct scanned_file, rb);
+
+		if (!file->ino.is_xattr && !file_is_reachable(c, file))
+			list_add(&file->list, &unreachable);
+	}
+
+	/* Round 2: Iterate xattr files. */
+	for (node = rb_first(&c->repair->scanned_files); node;
+	     node = rb_next(node)) {
+		cond_resched();
+		file = rb_entry(node, struct scanned_file, rb);
+
+		if (file->ino.is_xattr && !file_is_reachable(c, file))
+			list_add(&file->list, &unreachable);
+	}
+
+	/* Remove unreachable files. */
+	while (!list_empty(&unreachable)) {
+		cond_resched();
+		file = list_entry(unreachable.next, struct scanned_file, list);
+
+		list_del(&file->list);
+		destroy_file_content(file);
+		rb_erase(&file->rb, &c->repair->scanned_files);
+		kfree(file);
+	}
+}
+
 static int do_repair(struct ubifs_info *c)
 {
 	int err = 0;
@@ -1342,6 +1481,10 @@ static int do_repair(struct ubifs_info *c)
 	ubifs_msg(c, "Step 5: Filter invalid files");
 	filter_invalid_files(c);
 
+	/* Step 6: Extract reachable directory entries. */
+	ubifs_msg(c, "Step 5: Extract reachable files");
+	extract_dentry_tree(c);
+
 out:
 	destroy_scanned_info(c, &si);
 	return err;
diff --git a/fs/ubifs/repair.h b/fs/ubifs/repair.h
index 242bff2833bd..05bfe9a2189e 100644
--- a/fs/ubifs/repair.h
+++ b/fs/ubifs/repair.h
@@ -14,6 +14,8 @@
 #ifndef __UBIFS_REPAIR_H__
 #define __UBIFS_REPAIR_H__
 
+struct scanned_file;
+
 /**
  * scanned_node - common header node.
  * @exist: whether the node is found by scanning
@@ -67,6 +69,7 @@ struct scanned_ino_node {
  * @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
@@ -80,6 +83,7 @@ struct scanned_dent_node {
 	unsigned int nlen;
 	char name[UBIFS_MAX_NLEN];
 	ino_t inum;
+	struct scanned_file *file;
 	struct rb_node rb;
 	struct list_head list;
 };
-- 
2.31.1