From nobody Thu Feb 12 21:56:37 2026 Received: from szxga08-in.huawei.com (szxga08-in.huawei.com [45.249.212.255]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id AE50615AAD1 for ; Fri, 7 Jun 2024 04:27:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=45.249.212.255 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717734452; cv=none; b=WNmancebpiGGXjgIPqGMJg+rbrEbsgmXXrEwa6cSUKH6rySbkNwPCUfqSKQCa4dKqC+d0bsQGGARPO0MWPVHKTrud1G3UoTxHc69mCOZNFkLGxV/QOTYer9NVMaTmLpt7t0eEK8rPyKTPkIIvaYb/iQWpXqvxx6bFNw0KFbmjxc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1717734452; c=relaxed/simple; bh=v3ETs9sJ1Z2KlftB6ZBvQyYnscciU+t3CjrgEmHW8Co=; h=From:To:CC:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=cilmtN2eD0gRIpeQ/pCizCdiE3ZeqT3WkjHWBJUrHVU27BiTU1byIf+bmIsmP7f/YuT0OX8B4SmwJ9TrQLycXHoL5fTyhAhspMdLkay8Y/KbER+ix8nABf4jnCibKJNUft22aiuUN+F9sK0eRWQofEdsk1vXHCu+m4KyLWZTU1g= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com; spf=pass smtp.mailfrom=huawei.com; arc=none smtp.client-ip=45.249.212.255 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=huawei.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=huawei.com Received: from mail.maildlp.com (unknown [172.19.163.252]) by szxga08-in.huawei.com (SkyGuard) with ESMTP id 4VwSk72qVCz1SB2c; Fri, 7 Jun 2024 12:23:27 +0800 (CST) Received: from kwepemm600013.china.huawei.com (unknown [7.193.23.68]) by mail.maildlp.com (Postfix) with ESMTPS id 2301B180085; Fri, 7 Jun 2024 12:27:26 +0800 (CST) Received: from huawei.com (10.175.104.67) by kwepemm600013.china.huawei.com (7.193.23.68) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.1.2507.39; Fri, 7 Jun 2024 12:27:14 +0800 From: Zhihao Cheng To: , , , , , CC: , Subject: [RFC PATCH mtd-utils 064/110] fsck.ubifs: rebuild_fs: Remove deleted nodes from valid node tree Date: Fri, 7 Jun 2024 12:25:29 +0800 Message-ID: <20240607042615.2069840-65-chengzhihao1@huawei.com> X-Mailer: git-send-email 2.39.2 In-Reply-To: <20240607042615.2069840-1-chengzhihao1@huawei.com> References: <20240607042615.2069840-1-chengzhihao1@huawei.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To kwepemm600013.china.huawei.com (7.193.23.68) Content-Type: text/plain; charset="utf-8" This is the 2/12 step of rebuilding. Traverse nodes from del_inos and del_dents trees, remove inode nodes and dentry nodes with smaller sqnum from valid trees. This step handles 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. UBIFS rebuild_fs cannot solve it, because the real existence information of nodes depends on TNC, but TNC should not be depended for UBIFS rebuild_fs. Signed-off-by: Zhihao Cheng --- ubifs-utils/fsck.ubifs/rebuild_fs.c | 120 ++++++++++++++++++++++++++++++++= +++- 1 file changed, 119 insertions(+), 1 deletion(-) diff --git a/ubifs-utils/fsck.ubifs/rebuild_fs.c b/ubifs-utils/fsck.ubifs/r= ebuild_fs.c index 3ca94869..dbb0f3bc 100644 --- a/ubifs-utils/fsck.ubifs/rebuild_fs.c +++ b/ubifs-utils/fsck.ubifs/rebuild_fs.c @@ -364,6 +364,117 @@ out: return err; } =20 +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 =3D si->valid_inos.rb_node; + while (p) { + ino_node =3D rb_entry(p, struct scanned_ino_node, rb); + cmp =3D keys_cmp(c, &target->key, &ino_node->key); + if (cmp < 0) { + p =3D p->rb_left; + } else if (cmp > 0) { + p =3D 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, nlen; + struct scanned_dent_node *dent_node; + struct rb_node *p; + + p =3D si->valid_dents.rb_node; + while (p) { + dent_node =3D rb_entry(p, struct scanned_dent_node, rb); + cmp =3D keys_cmp(c, &target->key, &dent_node->key); + if (cmp < 0) { + p =3D p->rb_left; + } else if (cmp > 0) { + p =3D p->rb_right; + } else { + nlen =3D min(target->nlen, dent_node->nlen); + cmp =3D strncmp(target->name, dent_node->name, nlen) ? : + target->nlen - dent_node->nlen; + if (cmp < 0) { + p =3D p->rb_left; + } else if (cmp > 0) { + p =3D p->rb_right; + } else { + if (target->header.sqnum > + dent_node->header.sqnum) + return dent_node; + else + return NULL; + } + } + } + + return NULL; +} + +/** + * 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 val= id + * node, removes valid node from tree if the sqnum of deleted node is bigg= er. + * 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 =3D rb_first(&si->del_inos); + while (this) { + del_ino_node =3D rb_entry(this, struct scanned_ino_node, rb); + this =3D rb_next(this); + + valid_ino_node =3D lookup_valid_ino_node(c, si, del_ino_node); + if (valid_ino_node) { + 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 =3D rb_first(&si->del_dents); + while (this) { + del_dent_node =3D rb_entry(this, struct scanned_dent_node, rb); + this =3D rb_next(this); + + valid_dent_node =3D lookup_valid_dent_node(c, si, del_dent_node); + if (valid_dent_node) { + 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); + } +} + /** * ubifs_rebuild_filesystem - Rebuild filesystem. * @c: UBIFS file-system description object @@ -389,9 +500,16 @@ int ubifs_rebuild_filesystem(struct ubifs_info *c) /* Step 1: Scan valid/deleted nodes from volume. */ log_out(c, "Scan nodes"); err =3D scan_nodes(c, &si); - if (err) + if (err) { exit_code |=3D FSCK_ERROR; + goto out; + } + + /* Step 2: Remove deleted nodes from valid node tree. */ + log_out(c, "Remove deleted nodes"); + remove_del_nodes(c, &si); =20 +out: destroy_scanned_info(c, &si); destroy_rebuild_info(c); =20 --=20 2.13.6