commit 18076aac0276719f1476f5371d942328a6483a1b (HEAD -> master)
Author: Luke Dashjr <luke-jr+git@utopios.org>
Date:   Sat Aug 25 02:25:31 2018 +0000

    rebase rebuild-root.diff

diff --git a/fsck/fsck.c b/fsck/fsck.c
index 05a6301..08b117b 100644
--- a/fsck/fsck.c
+++ b/fsck/fsck.c
@@ -391,6 +391,8 @@ static int sanity_check_nid(struct f2fs_sb_info *sbi, u32 nid,
 		ASSERT_MSG("nid[0x%x] ino is 0", nid);
 		return -EINVAL;
 	}
+	if (nid == 3)
+		printf("DEBUG: %s: root inode blk_addr %#x\n", __func__, ni->blk_addr);
 
 	if (ni->blk_addr == NEW_ADDR) {
 		ASSERT_MSG("nid is NEW_ADDR. [0x%x]", nid);
@@ -563,6 +565,457 @@ err:
 	return -EINVAL;
 }
 
+struct wrapper {
+	union {
+		/*
+		 * direct/indirect/double-indirect and xattr
+		 * offs in node_footer->flags is used to sort nodes
+		 */
+		struct f2fs_node *node;
+		/* FIXME: data block should be all dentries */
+		struct data {
+			struct f2fs_dentry_block *dentry;
+			/* sum_entry->ofs_in_node is used to sort data */
+			struct f2fs_summary *sum;
+		} data;
+	};
+	block_t blk_addr;
+	struct wrapper *next;
+};
+struct wrapper *node_head = NULL, *data_head = NULL, *xattr_head = NULL;
+/*
+ * if nat entry of root inode is corrupted, we may find correct root inode
+ * block during scanning. So we save them
+ */
+struct wrapper *root_head = NULL;
+
+static void add_wrapper(struct wrapper **head, struct wrapper *new)
+{
+	if (*head == NULL) {
+		*head = new;
+	} else {
+		new->next = *head;
+		*head = new;
+	}
+}
+
+static int get_all_wrappers(struct f2fs_sb_info *sbi)
+{
+	struct seg_entry *se;
+	struct f2fs_dentry_block *dentry_blk;
+	struct f2fs_node *node_blk;
+	struct f2fs_summary_block *sum_blk;
+	struct f2fs_summary *sum_entry;
+	u32 seg_idx, sum_idx;
+	int sum_type, ret;
+	nid_t root_ino = F2FS_ROOT_INO(sbi);
+	struct wrapper *new;
+
+	for (seg_idx = 0; seg_idx < TOTAL_SEGS(sbi); seg_idx++) {
+		se = get_seg_entry(sbi, seg_idx);
+		if (!se->valid_blocks)
+			/* skip unused segment */
+			continue;
+
+		sum_blk = get_sum_block(sbi, seg_idx, &sum_type);
+		if (!sum_blk)
+			return -ENOMEM;
+
+		for (sum_idx = 0; sum_idx < ENTRIES_IN_SUM; sum_idx++) {
+			block_t blkaddr = SM_I(sbi)->main_blkaddr +
+					  seg_idx * sbi->blocks_per_seg +
+					  sum_idx;
+
+			if (!f2fs_test_sit_bitmap(sbi, blkaddr))
+				/* skip unused block */
+				continue;
+
+			sum_entry = &sum_blk->entries[sum_idx];
+			if (le32_to_cpu(sum_entry->nid) != root_ino)
+				/* skip block whose parent nid is not root ino */
+				continue;
+
+			new = (struct wrapper *)calloc(sizeof(struct wrapper), 1);
+			ASSERT(new);
+
+			if (sum_type == SEG_TYPE_NODE || sum_type == SEG_TYPE_CUR_NODE) {
+				node_blk = (struct f2fs_node *)calloc(BLOCK_SZ, 1);
+				ASSERT(node_blk);
+
+				ret = dev_read_block(node_blk, blkaddr);
+				ASSERT(ret >= 0);
+				if (le32_to_cpu(node_blk->footer.ino) == le32_to_cpu(node_blk->footer.nid)) {
+					/* skip the root inode itself */
+					if (le32_to_cpu(node_blk->footer.ino) == root_ino) {
+						DBG(1, "add block %#x to root_head\n", blkaddr);
+						new->node = node_blk;
+						new->blk_addr = blkaddr;
+						new->next = NULL;
+						add_wrapper(&root_head, new);
+						continue;
+					}
+				}
+				/* FIXME: shall we do some check here? if it
+				 * does not pass, we should drop the data
+				 * block.
+				 * Or, we don't need to check this, fsck
+				 * will do this later
+				 */
+				new->node = node_blk;
+				new->blk_addr = blkaddr;
+				new->next = NULL;
+				if (ofs_of_node(node_blk) == XATTR_NODE_OFFSET)
+					add_wrapper(&xattr_head, new);
+				else
+					add_wrapper(&node_head, new);
+			} else if (sum_type == SEG_TYPE_DATA || sum_type == SEG_TYPE_CUR_DATA) {
+				dentry_blk = (struct f2fs_dentry_block *)calloc(BLOCK_SZ, 1);
+				ASSERT(dentry_blk);
+
+				ret = dev_read_block(dentry_blk, blkaddr);
+				ASSERT(ret >= 0);
+				/* FIXME: shall we do some check here? if it
+				 * does not pass, we should drop the data
+				 * block.
+				 * Or, we don't need to check this, fsck
+				 * will do this later
+				 */
+				new->data.dentry = dentry_blk;
+				new->data.sum = calloc(sizeof(struct f2fs_summary), 1);
+				memcpy(new->data.sum, sum_entry, sizeof(struct f2fs_summary));
+				new->blk_addr = blkaddr;
+				new->next = NULL;
+				add_wrapper(&data_head, new);
+			} else {
+				ASSERT_MSG("segment 0x%x: unknown summary type %d\n",
+					seg_idx, sum_type);
+				break;
+			}
+		}
+		if (sum_type == SEG_TYPE_NODE ||
+		    sum_type == SEG_TYPE_DATA ||
+		    sum_type == SEG_TYPE_MAX)
+			free(sum_blk);
+	}
+	return 0;
+}
+
+static int update_nat_entry(struct f2fs_sb_info *sbi, u32 nid, block_t newblk)
+{
+	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
+	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
+	struct f2fs_summary_block *sum = curseg->sum_blk;
+	struct f2fs_nm_info *nm_i = NM_I(sbi);
+	struct f2fs_nat_block *nat_block;
+	struct f2fs_nat_entry *ne;
+	pgoff_t block_off;
+	pgoff_t nat_blk_addr;
+	block_t wrong_addr;
+	int seg_off, entry_off;
+	int i, ret;
+
+	/* look up nat entry in journal */
+	for (i = 0; i < nats_in_cursum((&sum->journal)); i++) {
+		if (le32_to_cpu(nid_in_journal((&sum->journal), i)) == nid) {
+			ne = &nat_in_journal((&sum->journal), i);
+			wrong_addr = le32_to_cpu(ne->block_addr);
+			ne->block_addr = cpu_to_le32(newblk);
+			goto out;
+		}
+	}
+
+	/* look up nat entry in NAT area */
+	nat_block = (struct f2fs_nat_block *)calloc(BLOCK_SZ, 1);
+	ASSERT(nat_block);
+
+        block_off = nid / NAT_ENTRY_PER_BLOCK;
+        entry_off = nid % NAT_ENTRY_PER_BLOCK;
+
+        seg_off = block_off >> sbi->log_blocks_per_seg;
+        nat_blk_addr = (pgoff_t)(nm_i->nat_blkaddr +
+                        (seg_off << sbi->log_blocks_per_seg << 1) +
+                        (block_off & ((1 << sbi->log_blocks_per_seg) - 1)));
+
+        if (f2fs_test_bit(block_off, nm_i->nat_bitmap))
+                nat_blk_addr += sbi->blocks_per_seg;
+
+        ret = dev_read_block(nat_block, nat_blk_addr);
+        ASSERT(ret >= 0);
+
+	ne = &nat_block->entries[entry_off];
+	wrong_addr = le32_to_cpu(ne->block_addr);
+	ne->block_addr = cpu_to_le32(newblk);
+
+	dev_write_block(nat_block, nat_blk_addr);
+
+out:
+	f2fs_set_bit(nid, fsck->nat_area_bitmap);
+	FIX_MSG("nat entry [%d] block_addr [0x%x] -> [0x%x]\n",
+		i, wrong_addr, newblk);
+	return 0;
+}
+
+static int update_sit_entry(struct f2fs_sb_info *sbi, block_t blk_addr)
+{
+	struct f2fs_fsck *fsck = F2FS_FSCK(sbi);
+	struct seg_entry *se;
+
+	if (f2fs_test_sit_bitmap(sbi, blk_addr)) {
+		se = get_seg_entry(sbi, GET_SEGNO(sbi, blk_addr));
+		se->valid_blocks += 1;
+		f2fs_set_bit(OFFSET_IN_SEG(sbi, blk_addr), (char *)se->cur_valid_map);
+		f2fs_test_bit(BLKOFF_FROM_MAIN(sbi, blk_addr), fsck->sit_area_bitmap);
+	}
+
+	return 0;
+}
+
+static int do_fix_root_inode(struct f2fs_sb_info *sbi,
+			     struct f2fs_node *root_node)
+{
+	struct node_info ni;
+	u32 noffset;
+	u64 cnt;
+	struct wrapper *new, *ptr = NULL;
+	struct f2fs_inode *root_inode;
+	block_t blkaddr;
+	/* shall we truct that the inode block really is root inode block */
+	int weight = 0, pre_weight = 0;
+	int fixed = 0;
+	nid_t root_ino = F2FS_ROOT_INO(sbi);
+	int ret;
+
+	/* get inode block */
+	ASSERT(root_node);
+	new = (struct wrapper *)calloc(sizeof(struct wrapper), 1);
+	get_node_info(sbi, root_ino, &ni);
+	new->node = root_node;
+	new->blk_addr = ni.blk_addr;
+	new->next = NULL;
+	add_wrapper(&root_head, new);
+
+	/*
+	 * check if the inode block is really the root inode block, choose
+	 * the node block which has the largest weight
+	 */
+	while (root_head) {
+		if (le32_to_cpu(root_head->node->footer.ino) == root_ino)
+			weight++;
+		if (le32_to_cpu(root_head->node->footer.nid) == root_ino)
+			weight++;
+		if (S_ISDIR(le16_to_cpu(root_head->node->i.i_mode)))
+			weight++;
+		/* FIXME: more weight? */
+
+		if (weight > pre_weight) {
+			/* FIXME: then how about >=? */
+			new = root_head;
+			pre_weight = weight;
+			DBG(1, "find new root_node block %#x\n", new->blk_addr);
+			root_head = root_head->next;
+			continue;
+		}
+		ptr = root_head;
+		root_head = root_head->next;
+		free(ptr->node);
+		free(ptr);
+	}
+	if (pre_weight < 2) {
+		/*
+		 * nat entry may be corrupted, we should not trust what we
+		 * read. We should select a new place to write it back
+		 */
+		blkaddr = 0; //FIXME: find a new position
+	} else {
+		blkaddr = new->blk_addr;
+		root_node = new->node;	
+	}
+	if (new->blk_addr != ni.blk_addr || root_node != new->node) {
+		ret = update_nat_entry(sbi, root_ino, new->blk_addr);
+		ASSERT(ret == 0);
+		ret = update_sit_entry(sbi, new->blk_addr);
+		ASSERT(ret == 0);
+	}
+
+	root_inode = &root_node->i;
+	/* recover i_addr[] */
+	cnt = 0;
+	while (data_head) {
+		ASSERT(cnt < DEF_ADDRS_PER_INODE);
+		noffset = le32_to_cpu(data_head->data.sum->ofs_in_node);
+		if (le32_to_cpu(root_inode->i_addr[noffset]) != data_head->blk_addr) {
+			ASSERT_MSG("root inode: i_addr[%u] = 0x%x, 0x%x\n",
+				noffset, le32_to_cpu(root_inode->i_addr[noffset]),
+				data_head->blk_addr);
+			root_inode->i_addr[noffset] = cpu_to_le32(data_head->blk_addr);
+			FIX_MSG("set i_addr[%u] = 0x%x\n", noffset, data_head->blk_addr);
+			fixed = 1;
+		}
+		ptr = data_head;
+		data_head = data_head->next;
+		free(ptr->data.dentry);
+		free(ptr->data.sum);
+		free(ptr);
+		cnt++;
+	}
+	DBG(1, "root inode: data blocks %lu\n", cnt);
+
+	/* recover i_nid[] */
+	cnt = 0;
+	while (node_head) {
+		ASSERT(cnt < 5);
+		noffset = ofs_of_node(node_head->node);
+		/* check if noffset is valid */
+		if (noffset == 1 || noffset == 2 || noffset == 3) {
+			/* noffset is valid, calc the index in i_nid */
+			noffset = noffset - 1;
+		} else if (noffset == 4 + ADDRS_PER_BLOCK) {
+			/* i_nid[3] */
+			noffset = 3;
+		} else if (noffset == 4 + ADDRS_PER_BLOCK + NIDS_PER_BLOCK) {
+			/* i_nid[4] */
+			noffset = 4;
+		} else {
+			/* noffset = 0, node is in i_addr, this must be wrong.
+			 * noffset = other value, node is in indirect/didirect
+			 * node. We drop these nodes.
+			 */
+			ASSERT_MSG("root inode: offset of node 0x%x\n", noffset);
+			FIX_MSG(" drop node block 0x%x\n", node_head->blk_addr);
+			fixed = 1;
+			break;
+		}
+		if (root_inode->i_nid[noffset] != node_head->node->footer.nid) {
+			ASSERT_MSG("root inode: i_nid[%u] = 0x%x, 0x%x\n",
+				noffset, le32_to_cpu(root_inode->i_nid[noffset]),
+				le32_to_cpu(node_head->node->footer.nid));
+			root_inode->i_nid[noffset] = node_head->node->footer.nid;
+			FIX_MSG("set i_nid[%u] = 0x%x\n", noffset,
+				le32_to_cpu(node_head->node->footer.nid));
+			fixed = 1;
+		}
+		ptr = node_head;
+		node_head = node_head->next;
+		free(ptr->node);
+		free(ptr);
+		cnt++;
+	}
+	DBG(1, "root inode: node blocks %lu\n", cnt);
+
+	/* recover i_xattr_nid */
+	cnt = 0;
+	while (xattr_head) {
+		ASSERT(cnt < 1);
+		if (root_inode->i_xattr_nid != xattr_head->node->footer.nid) {
+			root_inode->i_xattr_nid = xattr_head->node->footer.nid;
+			FIX_MSG("set i_xattr_nid = 0x%x\n",
+				le32_to_cpu(xattr_head->node->footer.nid));
+			fixed = 1;
+		}
+		ptr = xattr_head;
+		xattr_head = xattr_head->next;
+		free(ptr->node);
+		free(ptr);
+		cnt++;
+	}
+	DBG(1, "root inode: xattr blocks %lu\n", cnt);
+
+	/* recover other meta of root inode */
+	if (le16_to_cpu(root_inode->i_mode) != 0x41ed) {
+		root_inode->i_mode = cpu_to_le16(0x41ed); // from f2fs_write_root_inode
+		FIX_MSG("set i_mode = 0x41ed\n");
+		fixed = 1;
+	}
+	/* FIXME: how to set appropriate values to these 2 level */
+	if (le32_to_cpu(root_inode->i_current_depth) > MAX_DIR_HASH_DEPTH) {
+		root_inode->i_current_depth = cpu_to_le32(MAX_DIR_HASH_DEPTH);
+		FIX_MSG("set i_current_depth = %u\n", MAX_DIR_HASH_DEPTH);
+		fixed = 1;
+	}
+	if (le32_to_cpu(root_inode->i_dir_level) > MAX_DIR_HASH_DEPTH) {
+		root_inode->i_dir_level = cpu_to_le32(DEF_DIR_LEVEL);
+		FIX_MSG("set i_dir_level = %u\n", DEF_DIR_LEVEL);
+		fixed = 1;
+	}
+	/* FIXME: is root_inode->i_pino 3? why I get 0 in my case? */
+//	if (le32_to_cpu(root_inode->i_pino) != root_ino) {
+//		root_inode->i_pino = cpu_to_le32(root_ino);
+//		FIX_MSG("set i_pino = %u\n", root_ino);
+//		fixed = 1;
+//	}
+	/*
+	 * XXX: i_advise, i_inline, i_uid, i_gid, i_*time, i_*time_nsec,
+	 * i_generation, i_flagsi_flags, i_namelen, i_name
+	 *
+	 * XXX: the later fsck -f will fix: i_links, i_blocks, i_ext
+	 */
+
+	if (fixed && !c.ro) {
+		ret = dev_write_block(root_node, blkaddr);
+		ASSERT(ret >= 0);
+	}
+
+	return fixed;
+}
+
+/*
+ * we can only recover root inode by scanning SSA. Because inode may
+ * contains data, only SSA saves which nid the block belonging to
+ */
+static int fix_root_inode(struct f2fs_sb_info *sbi, struct f2fs_node *root_node)
+{
+	int ret;
+
+	/* 1. get all node/data blocks of root inode */
+	ret = get_all_wrappers(sbi);
+	if (ret)
+		return ret;
+
+	/* 2. recover root inode and write it back */
+	ret = do_fix_root_inode(sbi, root_node);
+	if (ret)
+		FIX_MSG("fixed root inode\n");
+
+	return 0;
+}
+
+int fsck_chk_fs(struct f2fs_sb_info *sbi, u32 *blk_cnt)
+{
+	struct node_info ni;
+	struct f2fs_node *node_blk = NULL;
+	struct f2fs_inode *root_inode;
+	enum FILE_TYPE ftype = F2FS_FT_DIR;
+	enum NODE_TYPE ntype = TYPE_INODE;
+	u32 ino = F2FS_ROOT_INO(sbi);
+	int retries = 0, ret;
+
+	node_blk = (struct f2fs_node *)calloc(BLOCK_SZ, 1);
+	ASSERT(node_blk != NULL);
+
+retry:
+	/* check if F2FS_ROOT_INO is a correct inode */
+	ret = sanity_check_nid(sbi, ino, node_blk, ftype, ntype, &ni);
+	if (ret)
+		goto fix;
+
+	root_inode = &node_blk->i;
+
+	/* check if F2FS_ROOT_INO is a directory */
+	if (!S_ISDIR(le16_to_cpu(root_inode->i_mode))) {
+		ASSERT_MSG("Root inode is not a directory\n");
+		goto fix;
+	}
+
+	fsck_chk_inode_blk(sbi, ino, ftype, node_blk, blk_cnt, &ni, NULL);
+	return 0;
+fix:
+	ret = fix_root_inode(sbi, node_blk);
+	retries++;
+	ASSERT(ret == 0);
+	ASSERT(retries < 2); // FIXME: how many times to retry?
+	goto retry;
+}
+
 static inline void get_extent_info(struct extent_info *ext,
 					struct f2fs_extent *i_ext)
 {
@@ -1410,6 +1863,8 @@ static int __chk_dentries(struct f2fs_sb_info *sbi, struct child_info *child,
 				}
 
 				i++;
+				print_dentry(fsck->dentry_depth, name, bitmap,
+					dentry, max, i, last_blk, enc_name);
 				free(name);
 				continue;
 			}
diff --git a/fsck/fsck.h b/fsck/fsck.h
index 8e133fa..2267492 100644
--- a/fsck/fsck.h
+++ b/fsck/fsck.h
@@ -125,6 +125,7 @@ struct selabel_handle;
 extern int fsck_chk_orphan_node(struct f2fs_sb_info *);
 extern int fsck_chk_quota_node(struct f2fs_sb_info *);
 extern int fsck_chk_quota_files(struct f2fs_sb_info *);
+extern int fsck_chk_fs(struct f2fs_sb_info *sbi, u32 *blk_cnt);
 extern int fsck_chk_node_blk(struct f2fs_sb_info *, struct f2fs_inode *, u32,
 		enum FILE_TYPE, enum NODE_TYPE, u32 *,
 		struct child_info *);
diff --git a/fsck/main.c b/fsck/main.c
index bbf82c3..97a0d9d 100644
--- a/fsck/main.c
+++ b/fsck/main.c
@@ -562,8 +562,7 @@ static void do_fsck(struct f2fs_sb_info *sbi)
 		}
 	}
 	fsck_chk_orphan_node(sbi);
-	fsck_chk_node_blk(sbi, NULL, sbi->root_ino_num,
-			F2FS_FT_DIR, TYPE_INODE, &blk_cnt, NULL);
+	fsck_chk_fs(sbi, &blk_cnt);
 	fsck_chk_quota_files(sbi);
 
 	fsck_verify(sbi);
diff --git a/fsck/mount.c b/fsck/mount.c
index 4a14320..dd874e5 100644
--- a/fsck/mount.c
+++ b/fsck/mount.c
@@ -245,10 +245,11 @@ void print_inode_info(struct f2fs_sb_info *sbi,
 	DISP_u32(inode, i_addr[ofs + 3]);	/* Pointers to data blocks */
 
 	for (i = ofs + 3; i < ADDRS_PER_INODE(inode); i++) {
-		if (inode->i_addr[i] == 0x0)
-			break;
-		printf("i_addr[0x%x] points data block\t\t[0x%4x]\n",
-				i, le32_to_cpu(inode->i_addr[i]));
+// 		if (inode->i_addr[i] == 0x0)
+// 			break;
+// 		printf("i_addr[0x%x] points data block\t\t[0x%4x]\n",
+// 				i, le32_to_cpu(inode->i_addr[i]));
+	DISP_u32(inode, i_addr[i]);	/* Pointers to data blocks */
 	}
 
 	DISP_u32(inode, i_nid[0]);	/* direct */