From patchwork Sun Aug 8 09:57:32 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Artem Bityutskiy X-Patchwork-Id: 61204 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from bombadil.infradead.org (bombadil.infradead.org [18.85.46.34]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id EA4BAB6EE8 for ; Sun, 8 Aug 2010 19:59:25 +1000 (EST) Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.72 #1 (Red Hat Linux)) id 1Oi2dp-0003uT-HZ; Sun, 08 Aug 2010 09:58:05 +0000 Received: from smtp.nokia.com ([192.100.105.134] helo=mgw-mx09.nokia.com) by bombadil.infradead.org with esmtps (Exim 4.72 #1 (Red Hat Linux)) id 1Oi2dn-0003sQ-1j for linux-mtd@lists.infradead.org; Sun, 08 Aug 2010 09:58:04 +0000 Received: from esebh106.NOE.Nokia.com (esebh106.ntc.nokia.com [172.21.138.213]) by mgw-mx09.nokia.com (Switch-3.3.3/Switch-3.3.3) with ESMTP id o789vwvL021304; Sun, 8 Aug 2010 04:58:00 -0500 Received: from esebh102.NOE.Nokia.com ([172.21.138.183]) by esebh106.NOE.Nokia.com with Microsoft SMTPSVC(6.0.3790.4675); Sun, 8 Aug 2010 12:57:57 +0300 Received: from mgw-da02.ext.nokia.com ([147.243.128.26]) by esebh102.NOE.Nokia.com over TLS secured channel with Microsoft SMTPSVC(6.0.3790.4675); Sun, 8 Aug 2010 12:57:56 +0300 Received: from eru.research.nokia.com (esdhcp04136.research.nokia.com [172.21.41.36]) by mgw-da02.ext.nokia.com (Switch-3.3.3/Switch-3.3.3) with ESMTP id o789vbYk004906; Sun, 8 Aug 2010 12:57:52 +0300 From: Artem Bityutskiy To: linux-mtd@lists.infradead.org Subject: [PATCHv2 9/9] UBIFS: introduce list sorting debugging checks Date: Sun, 8 Aug 2010 12:57:32 +0300 Message-Id: <1281261452-9868-10-git-send-email-dedekind1@gmail.com> X-Mailer: git-send-email 1.7.1.1 In-Reply-To: <1281261452-9868-1-git-send-email-dedekind1@gmail.com> References: <1281261452-9868-1-git-send-email-dedekind1@gmail.com> X-OriginalArrivalTime: 08 Aug 2010 09:57:57.0340 (UTC) FILETIME=[2D74E1C0:01CB36E0] X-Nokia-AV: Clean X-CRM114-Version: 20090807-BlameThorstenAndJenny ( TRE 0.7.6 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20100808_055803_427145_E1CA7761 X-CRM114-Status: GOOD ( 25.31 ) X-Spam-Score: 1.1 (+) X-Spam-Report: SpamAssassin version 3.3.1 on bombadil.infradead.org summary: Content analysis details: (1.1 points) pts rule name description ---- ---------------------- -------------------------------------------------- 0.0 FREEMAIL_FROM Sender email is freemail (dedekind1[at]gmail.com) 0.0 DKIM_ADSP_CUSTOM_MED No valid author signature, adsp_override is CUSTOM_MED 2.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in digit (dedekind1[at]gmail.com) -2.3 RCVD_IN_DNSWL_MED RBL: Sender listed at http://www.dnswl.org/, medium trust [192.100.105.134 listed in list.dnswl.org] 1.2 NML_ADSP_CUSTOM_MED ADSP custom_med hit, and not from a mailing list 0.0 T_TO_NO_BRKTS_FREEMAIL T_TO_NO_BRKTS_FREEMAIL Cc: Matthieu CASTET , Adrian Hunter X-BeenThere: linux-mtd@lists.infradead.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Linux MTD discussion mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: linux-mtd-bounces@lists.infradead.org Errors-To: linux-mtd-bounces+incoming=patchwork.ozlabs.org@lists.infradead.org From: Artem Bityutskiy The UBIFS bug in the GC list sorting comparison functions inspired me to write internal debugging check functions which verify that the list of nodes is sorted properly. So, this patch implements 2 new debugging functions: o 'dbg_check_data_nodes_order()' - check order of data nodes list o 'dbg_check_nondata_nodes_order()' - check order of non-data nodes list The debugging functions are executed only if general UBIFS debugging checks are enabled. And they are compiled out if UBIFS debugging is disabled. Signed-off-by: Artem Bityutskiy --- fs/ubifs/debug.c | 156 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/ubifs/debug.h | 4 ++ fs/ubifs/gc.c | 10 +++- 3 files changed, 168 insertions(+), 2 deletions(-) diff --git a/fs/ubifs/debug.c b/fs/ubifs/debug.c index c2a68ba..1f00d77 100644 --- a/fs/ubifs/debug.c +++ b/fs/ubifs/debug.c @@ -2239,6 +2239,162 @@ out_free: return err; } +/** + * dbg_check_data_nodes_order - check that list of data nodes is sorted. + * @c: UBIFS file-system description object + * @head: the list of nodes ('struct ubifs_scan_node' objects) + * + * This function returns zero if the list of data nodes is sorted correctly, + * and %-EINVAL if not. + */ +int dbg_check_data_nodes_order(struct ubifs_info *c, struct list_head *head) +{ + struct list_head *cur; + struct ubifs_scan_node *sa, *sb; + + if (!(ubifs_chk_flags & UBIFS_CHK_GEN)) + return 0; + + for (cur = head->next; cur->next != head; cur = cur->next) { + ino_t inuma, inumb; + uint32_t blka, blkb; + + cond_reshed(); + sa = container_of(cur, struct ubifs_scan_node, list); + sb = container_of(cur->next, struct ubifs_scan_node, list); + + if (sa->type != UBIFS_DATA_NODE) { + ubifs_err("bad node type %d", sa->type); + dbg_dump_node(c, sa->node); + return -EINVAL; + } + if (sb->type != UBIFS_DATA_NODE) { + ubifs_err("bad node type %d", sb->type); + dbg_dump_node(c, sb->node); + return -EINVAL; + } + + inuma = key_inum(c, &sa->key); + inumb = key_inum(c, &sb->key); + + if (inuma < inumb) + continue; + if (inuma > inumb) { + ubifs_err("larger inum %lu goes before inum %lu", + (unsigned long)inuma, (unsigned long)inumb); + goto error_dump; + } + + blka = key_block(c, &sa->key); + blkb = key_block(c, &sb->key); + + if (blka > blkb) { + ubifs_err("larger block %u goes before %u", blka, blkb); + goto error_dump; + } + if (blka == blkb) { + ubifs_err("two data nodes for the same block"); + goto error_dump; + } + } + + return 0; + +error_dump: + dbg_dump_node(c, sa->node); + dbg_dump_node(c, sb->node); + return -EINVAL; +} + +/** + * dbg_check_nondata_nodes_order - check that list of data nodes is sorted. + * @c: UBIFS file-system description object + * @head: the list of nodes ('struct ubifs_scan_node' objects) + * + * This function returns zero if the list of non-data nodes is sorted correctly, + * and %-EINVAL if not. + */ +int dbg_check_nondata_nodes_order(struct ubifs_info *c, struct list_head *head) +{ + struct list_head *cur; + struct ubifs_scan_node *sa, *sb; + + if (!(ubifs_chk_flags & UBIFS_CHK_GEN)) + return 0; + + for (cur = head->next; cur->next != head; cur = cur->next) { + ino_t inuma, inumb; + uint32_t hasha, hashb; + + cond_reshed(); + sa = container_of(cur, struct ubifs_scan_node, list); + sb = container_of(cur->next, struct ubifs_scan_node, list); + + if (sa->type != UBIFS_INO_NODE && sa->type != UBIFS_DENT_NODE && + sa->type != UBIFS_XENT_NODE) { + ubifs_err("bad node type %d", sa->type); + dbg_dump_node(c, sa->node); + return -EINVAL; + } + if (sa->type != UBIFS_INO_NODE && sa->type != UBIFS_DENT_NODE && + sa->type != UBIFS_XENT_NODE) { + ubifs_err("bad node type %d", sb->type); + dbg_dump_node(c, sb->node); + return -EINVAL; + } + + if (sa->type != UBIFS_INO_NODE && sb->type == UBIFS_INO_NODE) { + ubifs_err("non-inode node goes before inode node"); + goto error_dump; + } + + if (sa->type == UBIFS_INO_NODE && sb->type != UBIFS_INO_NODE) + continue; + + if (sa->type == UBIFS_INO_NODE && sb->type == UBIFS_INO_NODE) { + /* Inode nodes are sorted in descending size order */ + if (sa->len < sb->len) { + ubifs_err("smaller inode node goes first"); + goto error_dump; + } + continue; + } + + /* + * This is either a dentry or xentry, which should be sorted in + * ascending (parent ino, hash) order. + */ + inuma = key_inum(c, &sa->key); + inumb = key_inum(c, &sb->key); + + if (inuma < inumb) + continue; + if (inuma > inumb) { + ubifs_err("larger inum %lu goes before inum %lu", + (unsigned long)inuma, (unsigned long)inumb); + goto error_dump; + } + + hasha = key_block(c, &sa->key); + hashb = key_block(c, &sb->key); + + if (hasha > hashb) { + ubifs_err("larger hash %u goes before %u", hasha, hashb); + goto error_dump; + } + } + + return 0; + +error_dump: + ubifs_msg("dumping first node"); + dbg_dump_node(c, sa->node); + ubifs_msg("dumping second node"); + dbg_dump_node(c, sb->node); + return -EINVAL; + return 0; +} + static int invocation_cnt; int dbg_force_in_the_gaps(void) diff --git a/fs/ubifs/debug.h b/fs/ubifs/debug.h index 29d9601..69ebe47 100644 --- a/fs/ubifs/debug.h +++ b/fs/ubifs/debug.h @@ -324,6 +324,8 @@ int dbg_check_lpt_nodes(struct ubifs_info *c, struct ubifs_cnode *cnode, int row, int col); int dbg_check_inode_size(struct ubifs_info *c, const struct inode *inode, loff_t size); +int dbg_check_data_nodes_order(struct ubifs_info *c, struct list_head *head); +int dbg_check_nondata_nodes_order(struct ubifs_info *c, struct list_head *head); /* Force the use of in-the-gaps method for testing */ @@ -465,6 +467,8 @@ void dbg_debugfs_exit_fs(struct ubifs_info *c); #define dbg_check_lprops(c) 0 #define dbg_check_lpt_nodes(c, cnode, row, col) 0 #define dbg_check_inode_size(c, inode, size) 0 +#define dbg_check_data_nodes_order(c, head) 0 +#define dbg_check_nondata_nodes_order(c, head) 0 #define dbg_force_in_the_gaps_enabled 0 #define dbg_force_in_the_gaps() 0 #define dbg_failure_mode 0 diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c index 84ab9aa..95317a9 100644 --- a/fs/ubifs/gc.c +++ b/fs/ubifs/gc.c @@ -242,14 +242,13 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b) static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb, struct list_head *nondata, int *min) { + int err; struct ubifs_scan_node *snod, *tmp; *min = INT_MAX; /* Separate data nodes and non-data nodes */ list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) { - int err; - ubifs_assert(snod->type == UBIFS_INO_NODE || snod->type == UBIFS_DATA_NODE || snod->type == UBIFS_DENT_NODE || @@ -293,6 +292,13 @@ static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb, /* Sort data and non-data nodes */ list_sort(c, &sleb->nodes, &data_nodes_cmp); list_sort(c, nondata, &nondata_nodes_cmp); + + err = dbg_check_data_nodes_order(c, &sleb->nodes); + if (err) + return err; + err = dbg_check_nondata_nodes_order(c, nondata); + if (err) + return err; return 0; }