From patchwork Thu Dec 28 01:40:56 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhihao Cheng X-Patchwork-Id: 183606 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:6f82:b0:100:9c79:88ff with SMTP id tb2csp1757160dyb; Wed, 27 Dec 2023 17:38:44 -0800 (PST) X-Google-Smtp-Source: AGHT+IEnwjI6fuVBZssG9O72dgLStjmcVHsyMyk6NkFuSYPioeDcrQR3GQGf2NSOEdCZTrDJIXbG X-Received: by 2002:a05:6870:9720:b0:1fb:75a:77ba with SMTP id n32-20020a056870972000b001fb075a77bamr7976344oaq.107.1703727523915; Wed, 27 Dec 2023 17:38:43 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1703727523; cv=none; d=google.com; s=arc-20160816; b=y436PcxFlZk/8vOSk9/EhXp2ahjsDdpcn8e19f6QvMgM6TW+gI+OXn5WjBD5GQvW8B WTIMCgsAaomfId4Q08oFveWBJH7E0aj+Dg9UBHU8ctBVin1SrJb3NQtf/U6ecdaODzYD 3URSQv/od2d3BjSzcwfVDut33I0o8YzZzBM3OQNm2OBas+F6NvRjjrnQSdEctSAzkegj q9hD1f37BGjnJn1hAcZV9E//8GxxUGx3sftUYAzonMkuPir0iCIAO3TZ9LjlfP9fVDJj jrpELS96kUZP9/dc8jZB8F+zD3c/dj23goB14rfWD4eVRyaLPBFH6MtfefAcWlhK86rs M+5A== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:references:in-reply-to:message-id :date:subject:cc:to:from; bh=caezeq2TCqrMo2JNj6RQZ7l0eUyRMX8GvrtAqJ8/0lA=; fh=3kaVOPShTC55oj708yh1yJALapWuogKx6Yvc3sQq9zY=; b=JV3WnajR5t7dy6hmo5PRzMAHOypNs3TNIp1jSbUR+aaU6MiV+mXwgKrJoWVA19+Btd Ec8HMHYEgNXfC/+/7rgkwKuhypMpMbNCTN0bkig06ZX3Hm4XS0zOyWIoWRqx0+r0CX2t 2iq/ffFm5fxuMILGBPZCskZMmyEy6RXdK67bbxKOAXZE3i0xkLDlVjial7HrhsqMAj90 bEmLwaMEbRTJi0d++FFGWRzxMtXaNLUMLpoXfBdCPZBGq6Db6ulITol5nWYNLXGY6cLO kcDITm3TCGeO51d1HKnlL/PH0xhKFYQC74CTPklOiMuZ3MiTSXOmJdrRQfD2ip1OnSAI WJIQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel+bounces-12349-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-12349-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from sv.mirrors.kernel.org (sv.mirrors.kernel.org. [2604:1380:45e3:2400::1]) by mx.google.com with ESMTPS id v33-20020a631521000000b005cdfdd2625dsi8758573pgl.273.2023.12.27.17.38.43 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 27 Dec 2023 17:38:43 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-12349-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) client-ip=2604:1380:45e3:2400::1; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel+bounces-12349-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-12349-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sv.mirrors.kernel.org (Postfix) with ESMTPS id 849A5282B4D for ; Thu, 28 Dec 2023 01:38:43 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id D78053C00; Thu, 28 Dec 2023 01:38:13 +0000 (UTC) X-Original-To: linux-kernel@vger.kernel.org Received: from szxga05-in.huawei.com (szxga05-in.huawei.com [45.249.212.191]) (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 C62A510E5 for ; Thu, 28 Dec 2023 01:38:09 +0000 (UTC) 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.44]) by szxga05-in.huawei.com (SkyGuard) with ESMTP id 4T0rdg1m7jz1FGL4; Thu, 28 Dec 2023 09:34:15 +0800 (CST) Received: from kwepemm000013.china.huawei.com (unknown [7.193.23.81]) by mail.maildlp.com (Postfix) with ESMTPS id 2A137140120; Thu, 28 Dec 2023 09:38:07 +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:06 +0800 From: Zhihao Cheng To: , , , , CC: , Subject: [PATCH RFC 01/17] ubifs: repair: Load filesystem info from volume Date: Thu, 28 Dec 2023 09:40:56 +0800 Message-ID: <20231228014112.2836317-2-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> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To kwepemm000013.china.huawei.com (7.193.23.81) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1786487792168647612 X-GMAIL-MSGID: 1786487792168647612 This is the 1/13 step of repairing. Open UBI volume and read UBIFS super block, which is similar to UBIFS mounting process. If read superblock failed, repair is failure. Signed-off-by: Zhihao Cheng --- fs/ubifs/Makefile | 2 +- fs/ubifs/repair.c | 109 ++++++++++++++++++++++++++++++++++++++++++++++ fs/ubifs/super.c | 10 ++--- fs/ubifs/ubifs.h | 5 +++ 4 files changed, 120 insertions(+), 6 deletions(-) create mode 100644 fs/ubifs/repair.c diff --git a/fs/ubifs/Makefile b/fs/ubifs/Makefile index 314c80b24a76..88a11f85e150 100644 --- a/fs/ubifs/Makefile +++ b/fs/ubifs/Makefile @@ -5,7 +5,7 @@ ubifs-y += shrinker.o journal.o file.o dir.o super.o sb.o io.o ubifs-y += tnc.o master.o scan.o replay.o log.o commit.o gc.o orphan.o ubifs-y += budget.o find.o tnc_commit.o compress.o lpt.o lprops.o ubifs-y += recovery.o ioctl.o lpt_commit.o tnc_misc.o debug.o -ubifs-y += misc.o sysfs.o +ubifs-y += misc.o sysfs.o repair.o ubifs-$(CONFIG_FS_ENCRYPTION) += crypto.o ubifs-$(CONFIG_UBIFS_FS_XATTR) += xattr.o ubifs-$(CONFIG_UBIFS_FS_AUTHENTICATION) += auth.o diff --git a/fs/ubifs/repair.c b/fs/ubifs/repair.c new file mode 100644 index 000000000000..b722187de74f --- /dev/null +++ b/fs/ubifs/repair.c @@ -0,0 +1,109 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * This file is part of UBIFS. + * + * Copyright (C) 2023-2024, Huawei Technologies Co, Ltd. + * + * Authors: Zhihao Cheng + */ + +/* + * This file implements ubifs repair. + */ + +#include +#include "ubifs.h" + +int ubifs_repair(const char *dev_name) +{ + int err = 0; + struct ubifs_info *c; + struct ubi_volume_desc *ubi; + struct super_block *fake_sb; + + ubi = open_ubi(dev_name, UBI_READWRITE); + if (IS_ERR(ubi)) { + err = PTR_ERR(ubi); + pr_err("cannot open dev %s, err %d\n", dev_name, err); + return err; + } + + fake_sb = kzalloc(sizeof(struct super_block), GFP_KERNEL); + if (!fake_sb) { + err = -ENOMEM; + goto close_volume; + } + + c = alloc_ubifs_info(ubi); + if (!c) { + err = -ENOMEM; + goto free_sb; + } + + c->ubi = ubi; + c->vfs_sb = fake_sb; + c->max_inode_sz = key_max_inode_size(c); + if (c->max_inode_sz > MAX_LFS_FILESIZE) + c->max_inode_sz = MAX_LFS_FILESIZE; + + err = init_constants_early(c); + if (err) + goto free_ubifs; + + err = ubifs_debugging_init(c); + if (err) + goto free_ubifs; + + if (c->ro_media) { + err = -EROFS; + goto free_debug; + } + + err = check_volume_empty(c); + if (err) + goto free_debug; + + if (c->empty) { + ubifs_err(c, "empty filesystem"); + err = -ENODEV; + goto free_debug; + } + + c->sbuf = vmalloc(c->leb_size); + if (!c->sbuf) { + err = -ENOMEM; + goto free_debug; + } + + /* Step 1: Load filesystem info from volume. */ + ubifs_msg(c, "Step 1: Load filesystem"); + err = ubifs_read_superblock(c); + if (err) + goto free_sup; + + /* TODO: Support repairing authenticated image. */ + if (le32_to_cpu(c->sup_node->flags) & UBIFS_FLG_AUTHENTICATION) { + ubifs_err(c, "not support authentication"); + err = -EOPNOTSUPP; + goto free_sup; + } + + err = init_constants_sb(c); + if (err) + goto free_sup; + + ubifs_msg(c, "Repair success!"); + +free_sup: + kfree(c->sup_node); + vfree(c->sbuf); +free_debug: + ubifs_debugging_exit(c); +free_ubifs: + kfree(c); +free_sb: + kfree(fake_sb); +close_volume: + ubi_close_volume(ubi); + return err; +} diff --git a/fs/ubifs/super.c b/fs/ubifs/super.c index eabb0f44ea3e..ad726523d491 100644 --- a/fs/ubifs/super.c +++ b/fs/ubifs/super.c @@ -506,7 +506,7 @@ static int ubifs_sync_fs(struct super_block *sb, int wait) * requirements. Returns zero in case of success and a negative error code in * case of failure. */ -static int init_constants_early(struct ubifs_info *c) +int init_constants_early(struct ubifs_info *c) { if (c->vi.corrupted) { ubifs_warn(c, "UBI volume is corrupted - read-only mode"); @@ -670,7 +670,7 @@ static int bud_wbuf_callback(struct ubifs_info *c, int lnum, int free, int pad) * makes sure they are all right. Returns zero in case of success and a * negative error code in case of failure. */ -static int init_constants_sb(struct ubifs_info *c) +int init_constants_sb(struct ubifs_info *c) { int tmp, err; long long tmp64; @@ -934,7 +934,7 @@ static void free_buds(struct ubifs_info *c) * Returns zero in case of success and a negative error code in case of * failure. */ -static int check_volume_empty(struct ubifs_info *c) +int check_volume_empty(struct ubifs_info *c) { int lnum, err; @@ -2086,7 +2086,7 @@ const struct super_operations ubifs_super_operations = { * returns UBI volume description object in case of success and a negative * error code in case of failure. */ -static struct ubi_volume_desc *open_ubi(const char *name, int mode) +struct ubi_volume_desc *open_ubi(const char *name, int mode) { struct ubi_volume_desc *ubi; int dev, vol; @@ -2132,7 +2132,7 @@ static struct ubi_volume_desc *open_ubi(const char *name, int mode) return ERR_PTR(-EINVAL); } -static struct ubifs_info *alloc_ubifs_info(struct ubi_volume_desc *ubi) +struct ubifs_info *alloc_ubifs_info(struct ubi_volume_desc *ubi) { struct ubifs_info *c; diff --git a/fs/ubifs/ubifs.h b/fs/ubifs/ubifs.h index 3916dc4f30ca..a7ee8010ad66 100644 --- a/fs/ubifs/ubifs.h +++ b/fs/ubifs/ubifs.h @@ -2072,6 +2072,11 @@ static inline int ubifs_init_security(struct inode *dentry, /* super.c */ struct inode *ubifs_iget(struct super_block *sb, unsigned long inum); +int init_constants_early(struct ubifs_info *c); +int init_constants_sb(struct ubifs_info *c); +int check_volume_empty(struct ubifs_info *c); +struct ubi_volume_desc *open_ubi(const char *name, int mode); +struct ubifs_info *alloc_ubifs_info(struct ubi_volume_desc *ubi); /* recovery.c */ int ubifs_recover_master_node(struct ubifs_info *c); 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: 183607 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:6f82:b0:100:9c79:88ff with SMTP id tb2csp1757230dyb; Wed, 27 Dec 2023 17:39:03 -0800 (PST) X-Google-Smtp-Source: AGHT+IHCPxx3OObjAvA0Ps1nUnSguhJxaSDRqQD1XrOJUBncbP0GbXaqj77RixfISErWJx90oCgN X-Received: by 2002:a17:90a:2a8b:b0:28c:18a:c30f with SMTP id j11-20020a17090a2a8b00b0028c018ac30fmr2869750pjd.70.1703727543108; Wed, 27 Dec 2023 17:39:03 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1703727543; cv=none; d=google.com; s=arc-20160816; b=lIJFhC+kotdfWWPOs36x5k0yyXaMbvKIrYIHwUZRUyu711dfuOi420KQVp9UrsDBPE +HukDnS+tEIaMsBPJaJQJvmm5Wip4Ekpj7Su2Hd92wFId+b4ZuqHrFE22ZEJt/hGLDBa a8EiNW+FRENxWIJe1I3ZitnlUHm0pIsg1iYfhdeuAYA8wAtRkeH8iXsQ8gaRJgUDfPas ku3R4U34ExI7Jj+W65QAkXsQdcst0A3ywiqk028PCmPuMJNJrV151Uk1d4y+HRRverX6 WOLMuqpZ1pr5+9OZ/16AX5GNsii2V9jiCKX1yhUc9NBs5HFH38MqGcS79QFK4Nvtvt2/ N8xg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:references:in-reply-to:message-id :date:subject:cc:to:from; bh=M1XLRQvJFHcwG2GxgT6wY9SBnTTK9xuG765M9TP0ZYI=; fh=3kaVOPShTC55oj708yh1yJALapWuogKx6Yvc3sQq9zY=; b=IwNBJIsMMsE4hKxdGyz4m6MR2kXZc+Jg6Z/M+j3dv9cUz1xCBwZrY1adlvEyaKWkIM s/tqhfSEtV74nJJpfmc3DrliSdx+cYuRHvHIjrtmJDcmwa8aROx1EHmuqfV3bZHvwnmB qm7d9PfhoNCEW8m2cXNoHYE706HpAjS8+hqfYCSpTPbmxwGFLnhR61h60pzU+U9hTAAh mBt6t+SZCVswt3ZIrel2f/4ufqM0dSPJ6iq194GrVx/AprRoJRvAbT82JSJhDUOucm5q P31fSe87XZmF84STo2Qun1FGfN95daAXlSvgnHz3PqwvlQR3I7EGnZR5q8CZ5+bBmKLG QIVQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel+bounces-12350-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) smtp.mailfrom="linux-kernel+bounces-12350-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from sv.mirrors.kernel.org (sv.mirrors.kernel.org. [139.178.88.99]) by mx.google.com with ESMTPS id pg3-20020a17090b1e0300b0028bd40445bbsi13986258pjb.139.2023.12.27.17.39.02 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 27 Dec 2023 17:39:03 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-12350-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel+bounces-12350-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) smtp.mailfrom="linux-kernel+bounces-12350-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sv.mirrors.kernel.org (Postfix) with ESMTPS id CDE012827F6 for ; Thu, 28 Dec 2023 01:39:02 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id BBAD55253; Thu, 28 Dec 2023 01:38:14 +0000 (UTC) X-Original-To: linux-kernel@vger.kernel.org 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 8766810F2 for ; Thu, 28 Dec 2023 01:38:10 +0000 (UTC) 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 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> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To kwepemm000013.china.huawei.com (7.193.23.81) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1786487812335791007 X-GMAIL-MSGID: 1786487812335791007 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; } From patchwork Thu Dec 28 01:41:12 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Zhihao Cheng X-Patchwork-Id: 183608 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:6f82:b0:100:9c79:88ff with SMTP id tb2csp1758152dyb; Wed, 27 Dec 2023 17:42:32 -0800 (PST) X-Google-Smtp-Source: AGHT+IE4OnHShstcRH+J/hs7JUDKaFUOfihGXZAMOCpaBWYvv3GkxZinu8Q355W/naEqycwMmjxw X-Received: by 2002:a17:906:230f:b0:a23:532e:83d9 with SMTP id l15-20020a170906230f00b00a23532e83d9mr4234227eja.93.1703727752441; Wed, 27 Dec 2023 17:42:32 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1703727752; cv=none; d=google.com; s=arc-20160816; b=hPwAKtAS03YrUQ5ut2CdLjjVDNGrE7fSmo9bwoRFtfaNT7ldziDUW+YMF/JJHWzSrf WfOlpHVdbVvGfN99m62RFyMHdu9cUlh70SuB31c6n0geNJlyV0YLSZgKBrJRmDROPAKM 8ljYEbdyL1Q9h33fd7JvOuQxd77N3z5+JuK7z1IeTPoe/az1aaRW/pA8b/S3WhXKE2er vX5rJuzvqGEl5wDulkoRaUGBlrMKmdDMpxvY7fougx+awi+bZPnqS026NWVmFlnLmzJq pha2fGC0O6p58R1EdMdZ1k96QWqzBZ0jcxsebatdxvyyOhXbUl1kpZL25xI9sjA+6iJW PDhg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:references:in-reply-to:message-id :date:subject:cc:to:from; bh=LH/kVP0E4Dlvw1T0afja0T05/0iCQ3bCqqG5pEvXkHo=; fh=3kaVOPShTC55oj708yh1yJALapWuogKx6Yvc3sQq9zY=; b=QejK3cn7Q+Wgjj1D5qhBWRroMYq8075dTedWkQ7wGuK3qsXXKHc495t/6M+e69ZzWl tNv0qaezfENP5HiPMEZ6FG9ZcdLw4IzLXG6yrj7USvzsX4f2bhvHjZDZt6xqIW2qVW9t GMaJOU6XcubF8FYbv3EyzYeiMLAp7QoqpX7fflEESgQJza+j9RP8+rQ3HdvzOHplLWSV OQmxdzabmF1IgMu0HBVtsHQwaTzTJ4DteQ9yaTZYQMhTTsUX4FrpSr8ndCCpeUSUYbhf EnPGE7hZ+OmCEG4/jfkUPA4VAXShG7e/I/vKKtlb8tDY9IQY1DXeqTptvqbGHV1t8Bm1 rpDg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel+bounces-12366-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) smtp.mailfrom="linux-kernel+bounces-12366-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [2604:1380:4601:e00::3]) by mx.google.com with ESMTPS id su16-20020a17090703d000b00a26e3522badsi3679595ejb.955.2023.12.27.17.42.32 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 27 Dec 2023 17:42:32 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-12366-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) client-ip=2604:1380:4601:e00::3; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel+bounces-12366-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) smtp.mailfrom="linux-kernel+bounces-12366-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=fail (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=huawei.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by am.mirrors.kernel.org (Postfix) with ESMTPS id E23F01F2139C for ; Thu, 28 Dec 2023 01:42:31 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 704266131; Thu, 28 Dec 2023 01:40:04 +0000 (UTC) X-Original-To: linux-kernel@vger.kernel.org Received: from szxga04-in.huawei.com (szxga04-in.huawei.com [45.249.212.190]) (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 DAC2646BF for ; Thu, 28 Dec 2023 01:40:00 +0000 (UTC) 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.88.214]) by szxga04-in.huawei.com (SkyGuard) with ESMTP id 4T0rkk3gcSz29gby; Thu, 28 Dec 2023 09:38:38 +0800 (CST) Received: from kwepemm000013.china.huawei.com (unknown [7.193.23.81]) by mail.maildlp.com (Postfix) with ESMTPS id BACD01A0192; Thu, 28 Dec 2023 09:39:43 +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:16 +0800 From: Zhihao Cheng To: , , , , CC: , Subject: [PATCH RFC 17/17] Documentation: ubifs: Add ubifs repair whitepaper Date: Thu, 28 Dec 2023 09:41:12 +0800 Message-ID: <20231228014112.2836317-18-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> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-ClientProxiedBy: dggems706-chm.china.huawei.com (10.3.19.183) To kwepemm000013.china.huawei.com (7.193.23.81) X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1786488031528840466 X-GMAIL-MSGID: 1786488031528840466 Add documentation for UBIFS repair. Add 'ubifs' dir under 'Documentation/filesystems/', and move all docs related to UBIFS into 'Documentation/filesystems/ubifs'. Signed-off-by: Zhihao Cheng --- Documentation/filesystems/index.rst | 3 +- .../authentication.rst} | 0 Documentation/filesystems/ubifs/index.rst | 11 + .../filesystems/{ubifs.rst => ubifs/main.rst} | 0 Documentation/filesystems/ubifs/repair.rst | 235 ++++++++++++++++++ MAINTAINERS | 5 +- 6 files changed, 250 insertions(+), 4 deletions(-) rename Documentation/filesystems/{ubifs-authentication.rst => ubifs/authentication.rst} (100%) create mode 100644 Documentation/filesystems/ubifs/index.rst rename Documentation/filesystems/{ubifs.rst => ubifs/main.rst} (100%) create mode 100644 Documentation/filesystems/ubifs/repair.rst diff --git a/Documentation/filesystems/index.rst b/Documentation/filesystems/index.rst index 09cade7eaefc..7a7e3c0a5289 100644 --- a/Documentation/filesystems/index.rst +++ b/Documentation/filesystems/index.rst @@ -116,8 +116,7 @@ Documentation for filesystem implementations. sysfs sysv-fs tmpfs - ubifs - ubifs-authentication + ubifs/index udf virtiofs vfat diff --git a/Documentation/filesystems/ubifs-authentication.rst b/Documentation/filesystems/ubifs/authentication.rst similarity index 100% rename from Documentation/filesystems/ubifs-authentication.rst rename to Documentation/filesystems/ubifs/authentication.rst diff --git a/Documentation/filesystems/ubifs/index.rst b/Documentation/filesystems/ubifs/index.rst new file mode 100644 index 000000000000..fba59a916e89 --- /dev/null +++ b/Documentation/filesystems/ubifs/index.rst @@ -0,0 +1,11 @@ +=============== +UBI File System +=============== + + +.. toctree:: + :maxdepth: 1 + + main + repair + authentication diff --git a/Documentation/filesystems/ubifs.rst b/Documentation/filesystems/ubifs/main.rst similarity index 100% rename from Documentation/filesystems/ubifs.rst rename to Documentation/filesystems/ubifs/main.rst diff --git a/Documentation/filesystems/ubifs/repair.rst b/Documentation/filesystems/ubifs/repair.rst new file mode 100644 index 000000000000..212fa886b1a1 --- /dev/null +++ b/Documentation/filesystems/ubifs/repair.rst @@ -0,0 +1,235 @@ +.. SPDX-License-Identifier: GPL-2.0 + +.. UBIFS Repairing +.. sigma star gmbh +.. 2023 + +==================== +UBIFS Repair Support +==================== + +Introduction +============ + +UBIFS repair provides a way to fix inconsistent UBIFS image(which is corrupted +by hardware exceptions or UBIFS realization bugs) and makes filesystem become +consistent, just like fsck tools(eg. fsck.ext4, fsck.f2fs, fsck.fat, etc.) do. + +Why do we need UBIFS repair? +============================ + +The inconsistent UBIFS image is produced by mainly two aspects: + +- *Hardware exceptions*: Some of them are ecc uncorrectable errors(eg. [1]_ + [2]_), some of them are caused by intermittent writing protection(unstable + voltage). +- *UBIFS realization bugs*: Some of them are known bugs which are fixable (eg. + [3]_ [4]_ [5]_ [6]_ [7]_ [8]_ [9]_ [10]_ [11]_ [12]_, etc.), some of them are + unknown bugs(eg. [13]_), some of them are hard to fix(eg. [14]_). + +Once the UBIFS image becomes inconsistent, userspace applications won't work +properly, as we all know, UBIFS is mainly applied in embedded system, which +could affect many domains(eg. communications, IoT, family network, etc.). The +only way to rescue device is formating UBI device and mkfs, which will lost all +userdata, and it could be intolerable for some important situations. + +So, a filesystem repair tool is urgent for UBIFS, even it has been born for 15 +years, and it's not too late to do it for there will be more embedded devices in +the future IOT world. + +Implementation +============== + +Design +------ + +The direct idea of fixing an UBIFS image may be similar to mounting process: + +- Step 1: Read superblock. +- Step 2: Read master node. +- Step 3: Replay journal. +- Step 4: Traverse TNC, check and drop bad znodes, scan files according to TNC. +- Step 5: ... + +.. [LINK_1] This method has 3 disadvantages, and point 2 and 3 are unsolvable: + +- 1. It depends on too many areas, for example master, log. Repair will be + failed if each one of these areas becomes corrupted. +- 2. The amount of files can be recovered is decided by the degree of corruption + in TNC. All files will be lost if the max level znode is corrupted. +- 3. If we do step 3 before step 4 and TNC is corrupted, step 3 could be failed + while updating TNC, which makes repair failed. If we do step 4 before step 3 + and gc occurred in last mounting, empty('0xFF') area could be scanned based on + TNC, the node corresponding to bad TNC branch could be a good one because the + empty area has been gced and journal replaying is not performed (TNC could be + updated after replaying jouranl); Or the node corresponding to bad TNC branch + could be a bad one, because hardware exceptions happened. So it is hard to + decide the order between journal replaying and TNC traversing. Similar order + problem exists between journal replaying and LPT traversing too. + +To sum up, UBIFS repair should depend on less meta areas and recover as much +repairable data as possible. + +Since UBIFS assign sqnum for each node, it makes possible to distinguish new and +old verions for same file, so the main idea is scanning all nodes and then +rebuild TNC and recalculate space statistics informaion. + +Repair process +-------------- + +There are 13 steps for reparing an UBIFS image: + +- Step 1: Read superblock. +- Step 2: Scan nodes(inode node/dentry node/data node/truncation node) from + all LEBs, corrupted nodes(eg. incorrect crc, bad inode size, bad dentry name + length, etc.) are dropped during scanning. Valid inode nodes(nlink > 0) and + dentry nodes(inum != 0) are put into two valid trees separately, also, deleted + inode nodes (nlink is 0) and deleted dentry nodes(inum is 0) are put into two + deleted trees separately. Other nodes are put into corresponding file. The + final recovered file(xattr is treated as a file) is organized as: + +:: + + (rbtree, inum indexed) + / \ + file1 file2 + / \ + file3 file4 + + file { + inode node // each file has 1 inode node + dentry (sub rb_tree, sqnum indexed) // '/' has no dentries, otherwise + // at least 1 dentry is required. + trun node // the newest one truncation node + data (sub rb_tree, block number indexed) // Each file may have 0 + // many data nodes + } + +- Step 3: Traverse nodes from deleted trees, remove inode nodes and dentry nodes + with smaller sqnum from valid trees. valid_inos - del_inos = *left_inos*, + valid_dents - del_dents = *left_dents*. + +.. [LINK_2] 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. + +- Step 4: Traverse *left_inos* and *left_dents*, insert inode node and dentry + nodes into corresponding files. + Each file corresponds to a real file or xattr, it contains 1 inode node, multi + dentry nodes, multi data nodes, 1 newest truncation node(if exists). +- Step 5: Drop invalid files. For example, nonconsistent file type between inode + node and dentry nodes, file has no dentry nodes(excepts '/'), encrypted file + has no xattr information, etc. +- Step 6: Extract reachable directory entries tree. Make sure that all files can + be searched from '/', unreachable file is deleted. +- Step 7: Correct the file information. Traverse all files and calculate + information (nlink, size, xattr_cnt, etc.) for each file just like + check_leaf() does, correct inode node based on calculated information. +- Step 8: Record used LEBs. Traverse all files'(including effective nodes on + deleted trees in step 2) position, after this step UBIFS repair knows which + LEB is empty. +- Step 9: Re-write data. Read data from LEB and write back data, make sure that + all LEB is ended with empty data(0xFF). It will prevent failed gc scanning in + next mounting. +- Step 10: Build TNC. Construct TNC according to all files' nodes, just like + mkfs does, then write TNC on flash. +- Step 11: Build LPT. Construct LPT according to all nodes' position, just like + mkfs does, then write TNC on flash. +- Step 12: Clean up log area and orphan area. Recovery process is finished, log + area and orphan area can be erased. +- Step 13: Write master node. Since all meta areas are ready, master node can + be updated. + +Evaluation +========== + +Based on the implementation of ubifs repair, there are following advantages and +limitations. + +Advantages +---------- + +- 1. Power-cut during repairing is tolerant, UBIFS repair always do full + scanning and final valid nodes won't be erased from flash, so UBIFS repair + can always rebuild filesystem based on scanning nodes even it is breaked by + power-cut. +- 2. The UBIFS image can be fixed as long as the super block is not corrupted. + If there exists no valid nodes on flash, UBIFS repair will create a new '/' + just like create_default_filesystem() does. +- 3. Encrypted UBIFS image is supported, because dentry name and data content of + file are not necessary for UBIFS repair process. + +Limitations +----------- + +- 1. Deleted files could be recovered [LINK_2]_. Similar problem exists on data + nodes, for example, 8K-size file A(dn0, dn1) is truncated as 0, 4K data(dn2) + is then written from offset 4K in file A. The dn0 and dn2 is recovered after + repairing, but only dn2 is expected to be 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, see [LINK_1]_. +- 2. All valid nodes are loaded in memory, if there are too many files, it could + trigger OOM while repairing. Similar problem exists in dbg_check_filesystem(). +- 3. Authenticated UBIFS image is not supported for now, it can be supported by + extending new fields in repair interface(used to passing authentication + information) and implementing parsing authenticated nodes. + +How to use? +=========== + +UBIFS repair is suggested to be invoked when UBIFS image becomes inconsistent, +for example: + +- UBIFS image cannot be mounted caused by corrupted data(eg. bad crc, bad lpt, + bad tnc, bad master node, bad log area, etc.) or inconsistent meta data(eg. + inode size is smaller than data length, lost dentry node, lost inode node, + wrong nlink, etc.). +- Errors occurr in file accessing/reading, and error messages are related to + inconsistent meta data. +- UBIFS becomes readonly caused by inconsistent meta data(eg. assertion failure + on metadata checking). +- Other problems related to inconsistent UBIFS image. + +Invoke UBIFS repair by: echo ``UBIFS_DEV`` > /sys/kernel/debug/ubifs/repair_fs, +``UBIFS_DEV`` could be: + +- ubiX_Y: X means UBI device number and Y means UBI volume number. + For example: echo "ubi0_0" > /sys/kernel/debug/ubifs/repair_fs +- /dev/ubiX_Y: X means UBI device number and Y means UBI volume number. + For example: echo "/dev/ubi0_0" > /sys/kernel/debug/ubifs/repair_fs +- ubiX:NAME: X means UBI device number and NAME means UBI volume name. + For example: echo "ubi0:userdata" > /sys/kernel/debug/ubifs/repair_fs + +References +========== + +.. [1] https://lore.kernel.org/linux-mtd/1582293853-136727-1-git-send-email-chengzhihao1@huawei.com/ + +.. [2] https://lore.kernel.org/linux-mtd/CAMxq0fNSWrUFMmmTs8Ri9gFOvS+KQJvZN3-_KuiqXi9bbmCB0Q@mail.gmail.com/ + +.. [3] https://lore.kernel.org/linux-mtd/20211227032246.2886878-6-chengzhihao1@huawei.com/ + +.. [4] https://lore.kernel.org/linux-mtd/1638777819.2925845.1695222544742.JavaMail.zimbra@robart.cc/T/#u + +.. [5] https://lore.kernel.org/linux-mtd/20190515203113.19398-1-richard@nod.at/ + +.. [6] https://lore.kernel.org/linux-mtd/20190404223438.29408-1-richard@nod.at/ + +.. [7] https://lore.kernel.org/linux-mtd/20210316085214.25024-1-guochun.mao@mediatek.com/ + +.. [8] https://lore.kernel.org/linux-mtd/20180611225228.28931-1-richard@nod.at/ + +.. [9] https://lore.kernel.org/linux-mtd/20180611214109.14424-1-richard@nod.at/ + +.. [10] https://lore.kernel.org/linux-mtd/1476823591-6137-1-git-send-email-richard@nod.at/ + +.. [11] https://lore.kernel.org/linux-mtd/1474495050-13529-1-git-send-email-pascal.eberhard@gmail.com/ + +.. [12] https://lore.kernel.org/linux-mtd/1342340237-29656-1-git-send-email-dedekind1@gmail.com/ + +.. [13] https://linux-mtd.infradead.narkive.com/bfcHzD0j/ubi-ubifs-corruptions-during-random-power-cuts + +.. [14] https://bugzilla.kernel.org/show_bug.cgi?id=218309 diff --git a/MAINTAINERS b/MAINTAINERS index 7cef2d2ef8d7..6703dfb10369 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -22161,8 +22161,9 @@ W: http://www.linux-mtd.infradead.org/doc/ubifs.html T: git git://git.kernel.org/pub/scm/linux/kernel/git/rw/ubifs.git next T: git git://git.kernel.org/pub/scm/linux/kernel/git/rw/ubifs.git fixes F: Documentation/ABI/testing/sysfs-fs-ubifs -F: Documentation/filesystems/ubifs-authentication.rst -F: Documentation/filesystems/ubifs.rst +F: Documentation/filesystems/ubifs/authentication.rst +F: Documentation/filesystems/ubifs/main.rst +F: Documentation/filesystems/ubifs/repair.rst F: fs/ubifs/ UBLK USERSPACE BLOCK DRIVER