fsck.ubifs: check and correct the space statistics

This is the 12/18 step of fsck. Check and correct the space statistics.
There could be following steps and possible errors:
 Step 1. Exit for check mode, if %FR_LPT_CORRUPTED or %FR_LPT_INCORRECT
 is set in lpt status, the exit code should have %FSCK_UNCORRECTED.
 Step 2. Check lpt status, if %FR_LPT_CORRUPTED is set in lpt status,
 normal mode with 'no' answer will exit, other modes will rebuild lpt.
 Step 3. 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.
  b. Incorrect nnode/pnode, normal mode with 'no' answer will exit,
     other other modes will correct the nnode/pnode.
  c. Inconsistent comparing result, normal mode with 'no' answer
     will exit, other modes will correct the space statistics.
 Step 4. Check and correct the lprops table information.
 Step 5. Set gc lnum(ubifs_rcvry_gc_commit / take_gc_lnum).

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

1 files changed, 572 insertions, 4 deletions

diff --git a/ubifs-utils/fsck.ubifs/check_space.c b/ubifs-utils/fsck.ubifs/check_space.c
index f758bf1..afe6ba0 100644
--- a/ubifs-utils/fsck.ubifs/check_space.c
+++ b/ubifs-utils/fsck.ubifs/check_space.c
@@ -44,18 +44,20 @@ int get_free_leb(struct ubifs_info *c)
  * 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)
+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. */
+	/* Set gc lnum, equivalent to ubifs_rcvry_gc_commit/take_gc_lnum. */
 	lnum = get_free_leb(c);
 	if (lnum < 0)
 		return lnum;
@@ -63,7 +65,7 @@ int build_lpt(struct ubifs_info *c, calculate_lp_callback calculate_lp_cb)
 
 	/* Update LPT. */
 	for (i = 0; i < c->main_lebs; i++) {
-		err = calculate_lp_cb(c, i, &free, &dirty);
+		err = calculate_lp_cb(c, i, &free, &dirty, NULL);
 		if (err)
 			return err;
 
@@ -87,8 +89,574 @@ int build_lpt(struct ubifs_info *c, calculate_lp_callback calculate_lp_cb)
 				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);
+	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;
 }