From patchwork Thu Dec 28 01:40:58 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhihao Cheng X-Patchwork-Id: 1880649 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; dkim=pass (2048-bit key; secure) header.d=lists.infradead.org header.i=@lists.infradead.org header.a=rsa-sha256 header.s=bombadil.20210309 header.b=2iIrEAwV; dkim-atps=neutral Authentication-Results: legolas.ozlabs.org; spf=none (no SPF record) smtp.mailfrom=lists.infradead.org (client-ip=2607:7c80:54:3::133; helo=bombadil.infradead.org; envelope-from=linux-mtd-bounces+incoming=patchwork.ozlabs.org@lists.infradead.org; receiver=patchwork.ozlabs.org) Received: from bombadil.infradead.org (bombadil.infradead.org [IPv6:2607:7c80:54:3::133]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (secp384r1) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4T0rkp4S1Wz23d7 for ; Thu, 28 Dec 2023 12:38:42 +1100 (AEDT) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:List-Subscribe:List-Help:List-Post: List-Archive:List-Unsubscribe:List-Id:MIME-Version:References:In-Reply-To: Message-ID:Date:Subject:CC:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=HFERXz13VVHrYtMuVWkWz2yLbiIxKIwAEv2rSKJ9DEk=; b=2iIrEAwVEpYUET HX9/cJL/jhZAMTx0hBz8mejApd7tDAB+IgKKPBSQWfEta6qpxTafrxG+0XJz+NnyPtZSGoMjOe9NO 5nqPUFZ/Lfi1WQL7sQ2I4g2jODIsJNVlM2DrkKGf1NJU91Ro02yOaTrICML7LS0L2lIvUhAIcV7Cv blB0/I6STA+EmYFmmtTQHl4Qo+tAj2nM1VPj3Qt3/Vh0ipdWFoOdunZMV2YQULRb/sDDs1zGyG6xp gzFBjekBnLtxGN+Q/qQv51dteTCTRHV6c/rXPBYNfzeiWX8qSj1Z4UgZhQek53QOUfebXkAX2OYoc 2KZl+flT/fJCkgD0oiyQ==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.96 #2 (Red Hat Linux)) id 1rIfLl-00FpWM-09; Thu, 28 Dec 2023 01:38:17 +0000 Received: from szxga08-in.huawei.com ([45.249.212.255]) by bombadil.infradead.org with esmtps (Exim 4.96 #2 (Red Hat Linux)) id 1rIfLh-00FpVO-1D for linux-mtd@lists.infradead.org; Thu, 28 Dec 2023 01:38:15 +0000 Received: from mail.maildlp.com (unknown [172.19.163.252]) by szxga08-in.huawei.com (SkyGuard) with ESMTP id 4T0rjd4x1Yz1Q6xV; Thu, 28 Dec 2023 09:37:41 +0800 (CST) Received: from kwepemm000013.china.huawei.com (unknown [7.193.23.81]) by mail.maildlp.com (Postfix) with ESMTPS id 795BB180075; Thu, 28 Dec 2023 09:38:08 +0800 (CST) Received: from huawei.com (10.175.127.227) by kwepemm000013.china.huawei.com (7.193.23.81) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2507.35; Thu, 28 Dec 2023 09:38:07 +0800 From: Zhihao Cheng To: , , , , CC: , Subject: [PATCH RFC 03/17] ubifs: repair: Remove deleted nodes from valid node tree Date: Thu, 28 Dec 2023 09:40:58 +0800 Message-ID: <20231228014112.2836317-4-chengzhihao1@huawei.com> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20231228014112.2836317-1-chengzhihao1@huawei.com> References: <20231228014112.2836317-1-chengzhihao1@huawei.com> MIME-Version: 1.0 X-Originating-IP: [10.175.127.227] X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To kwepemm000013.china.huawei.com (7.193.23.81) X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20231227_173813_769218_D9427A64 X-CRM114-Status: GOOD ( 13.89 ) X-Spam-Score: -2.3 (--) X-Spam-Report: Spam detection software, running on the system "bombadil.infradead.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: This is the 3/13 step of repairing. 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 repairing because [...] Content analysis details: (-2.3 points, 5.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -2.3 RCVD_IN_DNSWL_MED RBL: Sender listed at https://www.dnswl.org/, medium trust [45.249.212.255 listed in list.dnswl.org] -0.0 SPF_PASS SPF: sender matches SPF record 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 0.0 RCVD_IN_MSPIKE_H5 RBL: Excellent reputation (+5) [45.249.212.255 listed in wl.mailspike.net] 0.0 RCVD_IN_MSPIKE_WL Mailspike good senders X-BeenThere: linux-mtd@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Linux MTD discussion mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: "linux-mtd" Errors-To: linux-mtd-bounces+incoming=patchwork.ozlabs.org@lists.infradead.org This is the 3/13 step of repairing. 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 repairing 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 repair cannot solve it, because the real existence information of nodes depends on TNC, but TNC should not be depended for UBIFS repair. Signed-off-by: Zhihao Cheng --- fs/ubifs/repair.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 120 insertions(+) diff --git a/fs/ubifs/repair.c b/fs/ubifs/repair.c index 18920e9896bc..d932c16ec893 100644 --- a/fs/ubifs/repair.c +++ b/fs/ubifs/repair.c @@ -930,6 +930,119 @@ static int scan_nodes(struct ubifs_info *c, struct scanned_info *si) return err; } +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 = si->valid_inos.rb_node; + while (p) { + ino_node = rb_entry(p, struct scanned_ino_node, rb); + cmp = keys_cmp(c, &target->key, &ino_node->key); + if (cmp < 0) { + p = p->rb_left; + } else if (cmp > 0) { + p = 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 = si->valid_dents.rb_node; + while (p) { + dent_node = rb_entry(p, struct scanned_dent_node, rb); + cmp = keys_cmp(c, &target->key, &dent_node->key); + if (cmp < 0) { + p = p->rb_left; + } else if (cmp > 0) { + p = p->rb_right; + } else { + nlen = min(target->nlen, dent_node->nlen); + cmp = strncmp(target->name, dent_node->name, nlen) ? : + target->nlen - dent_node->nlen; + if (cmp < 0) { + p = p->rb_left; + } else if (cmp > 0) { + p = 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 valid + * node, removes valid node from tree if the sqnum of deleted node is bigger. + * 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 = rb_first(&si->del_inos); + while (this) { + cond_resched(); + del_ino_node = rb_entry(this, struct scanned_ino_node, rb); + this = rb_next(this); + + valid_ino_node = 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 = rb_first(&si->del_dents); + while (this) { + cond_resched(); + del_dent_node = rb_entry(this, struct scanned_dent_node, rb); + this = rb_next(this); + + valid_dent_node = 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); + } +} + static int do_repair(struct ubifs_info *c) { int err = 0; @@ -940,7 +1053,14 @@ static int do_repair(struct ubifs_info *c) /* Step 2: Scan valid/deleted nodes from volume. */ ubifs_msg(c, "Step 2: Scan nodes"); err = scan_nodes(c, &si); + if (err) + goto out; + + /* Step 3: Remove deleted nodes from valid node tree. */ + ubifs_msg(c, "Step 3: Remove deleted nodes"); + remove_del_nodes(c, &si); +out: destroy_scanned_info(c, &si); return err; }