[PATCH 0/7] UBIFS: recent patches

[PATCH 0/7] UBIFS: recent patches

[Artem Bityutskiy]

Hi,

while looking at the UBIFS gc_lnum  == -1 issue, and testing UBIFS in 2.6.35, I
found few issues and made several patches. Here they go. I've also pushed them
to ubifs-2.6 / master.

Note, the GC sorting fixes are presumably important to have, so please, test
them them before I've merged buggy versions upstream (2.6.37) and to back-port
trees :-)

Matthieu, I failed to figure out how gc_lnum can become -1 in the master node.
Most probably I'll have to create a debugging patch and ask you to reproduce
the error again, but do not thing I'll have time for this in August. So, you
could try to look at the code and put more printk's in interesting places
yourself, and find when exactly it becomes -1, and then how it ends up in the
master node. That would be helpful.

Artem.

[PATCH 1/7] UBIFS: switch to RO mode after synchronizing

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

In 'ubifs_garbage_collect()' on error path, we first switch to R/O mode, and
then synchronize write-buffers (to make sure no data are lost). But the GC
write-buffer synchronization will fail, because we are already in R/O mode.
This patch re-orders this and makes sure we first synchronize the write-buffer,
and then switch to R/O mode.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 fs/ubifs/gc.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 918d158..f89a422 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -774,8 +774,8 @@ out_unlock:
 out:
 	ubifs_assert(ret < 0);
 	ubifs_assert(ret != -ENOSPC && ret != -EAGAIN);
-	ubifs_ro_mode(c, ret);
 	ubifs_wbuf_sync_nolock(wbuf);
+	ubifs_ro_mode(c, ret);
 	mutex_unlock(&wbuf->io_mutex);
 	ubifs_return_leb(c, lp.lnum);
 	return ret;
-- 
1.7.1.1

[PATCH 2/7] UBIFS: do not treat ENOSPC specially

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

'ubifs_garbage_collect_leb()' should never return '-ENOSPC', and if it
does, this is an error. Thus, do not treat this error code specially.
'-EAGAIN' is a special error code, but not '-ENOSPC'.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 fs/ubifs/gc.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index f89a422..29ce1b3 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -677,7 +677,7 @@ int ubifs_garbage_collect(struct ubifs_info *c, int anyway)
 
 		ret = ubifs_garbage_collect_leb(c, &lp);
 		if (ret < 0) {
-			if (ret == -EAGAIN || ret == -ENOSPC) {
+			if (ret == -EAGAIN) {
 				/*
 				 * These codes are not errors, so we have to
 				 * return the LEB to lprops. But if the
-- 
1.7.1.1

Re: [PATCH 2/7] UBIFS: do not treat ENOSPC specially

[Vitaly Wool]

Hi Artem,

On Sat, Aug 7, 2010 at 4:26 AM, Artem Bityutskiy <dedekind1@gmail.com> wrote:
> From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
>
> 'ubifs_garbage_collect_leb()' should never return '-ENOSPC', and if it
> does, this is an error. Thus, do not treat this error code specially.
> '-EAGAIN' is a special error code, but not '-ENOSPC'.
>
> Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> ---
>  fs/ubifs/gc.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
>
> diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
> index f89a422..29ce1b3 100644
> --- a/fs/ubifs/gc.c
> +++ b/fs/ubifs/gc.c
> @@ -677,7 +677,7 @@ int ubifs_garbage_collect(struct ubifs_info *c, int anyway)
>
>                ret = ubifs_garbage_collect_leb(c, &lp);
>                if (ret < 0) {
> -                       if (ret == -EAGAIN || ret == -ENOSPC) {
> +                       if (ret == -EAGAIN) {
>                                /*
>                                 * These codes are not errors, so we have to
>                                 * return the LEB to lprops. But if the

(just passing by...) probably the comment should be updated as well?

Thanks,
   Vitaly

Re: [PATCH 2/7] UBIFS: do not treat ENOSPC specially

[Artem Bityutskiy]

On Sun, 2010-08-08 at 13:51 -0400, Vitaly Wool wrote:
> >                ret = ubifs_garbage_collect_leb(c, &lp);
> >                if (ret < 0) {
> > -                       if (ret == -EAGAIN || ret == -ENOSPC) {
> > +                       if (ret == -EAGAIN) {
> >                                /*
> >                                 * These codes are not errors, so we have to
> >                                 * return the LEB to lprops. But if the
> 
> (just passing by...) probably the comment should be updated as well?

Hi, indeed :-)

Artem.

[PATCH 3/7] UBIFS: fix assertion warning

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

This patch fixes the following false assertion warning:

UBIFS assert failed in data_nodes_cmp at 130 (pid 15107)

The assertion was wrong because it did not take into account that the
node can be an xentry.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 fs/ubifs/gc.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index 29ce1b3..d060c62 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -178,7 +178,8 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 	if (typeb == UBIFS_INO_KEY)
 		return 1;
 
-	ubifs_assert(typea == UBIFS_DENT_KEY && typeb == UBIFS_DENT_KEY);
+	ubifs_assert(typea == UBIFS_DENT_KEY || typea == UBIFS_XENT_KEY);
+	ubifs_assert(typeb == UBIFS_DENT_KEY || typeb == UBIFS_XENT_KEY);
 	inuma = key_inum(c, &sa->key);
 	inumb = key_inum(c, &sb->key);
 
-- 
1.7.1.1

[PATCH 4/7] UBIFS: fix GC sroting

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

Unfortunately, the comparison functions for both data and non-data nodes
('data_nodes_cmp()' and 'nondata_nodes_cmp()') was screwed. It did not
work for the case when 'inuma == inumb' and 'blka > blkb' or 'hasha > hashb'.

Basically, this means that it did not actually sort the list. This is not
fatal, but this means that GC did not optimize the on-flash layout as we
thought it would.

This issue was revealed by commit '835cc0c8477fdbc59e0217891d6f11061b1ac4e2' of
Don Mullis: assertions in the comparison functions started triggering.

This patch fixes the issue. Additionally, it makes the comparison functions
return immediately the elements to compare are actually the same element.
This is just a tiny optimization.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 fs/ubifs/gc.c |   34 ++++++++++++++--------------------
 1 files changed, 14 insertions(+), 20 deletions(-)

diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index d060c62..fbb9272 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -125,6 +125,9 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 	struct ubifs_scan_node *sa, *sb;
 
 	cond_resched();
+	if (a == b)
+		return 0;
+
 	sa = list_entry(a, struct ubifs_scan_node, list);
 	sb = list_entry(b, struct ubifs_scan_node, list);
 	ubifs_assert(key_type(c, &sa->key) == UBIFS_DATA_KEY);
@@ -133,16 +136,10 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 	inuma = key_inum(c, &sa->key);
 	inumb = key_inum(c, &sb->key);
 
-	if (inuma == inumb) {
-		unsigned int blka = key_block(c, &sa->key);
-		unsigned int blkb = key_block(c, &sb->key);
-
-		if (blka <= blkb)
-			return -1;
-	} else if (inuma <= inumb)
-		return -1;
-
-	return 1;
+	if (inuma == inumb)
+		return key_block(c, &sa->key) - key_block(c, &sb->key);
+	else
+		return inuma - inumb;
 }
 
 /*
@@ -163,6 +160,9 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 	struct ubifs_scan_node *sa, *sb;
 
 	cond_resched();
+	if (a == b)
+		return 0;
+
 	sa = list_entry(a, struct ubifs_scan_node, list);
 	sb = list_entry(b, struct ubifs_scan_node, list);
 	typea = key_type(c, &sa->key);
@@ -183,16 +183,10 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 	inuma = key_inum(c, &sa->key);
 	inumb = key_inum(c, &sb->key);
 
-	if (inuma == inumb) {
-		uint32_t hasha = key_hash(c, &sa->key);
-		uint32_t hashb = key_hash(c, &sb->key);
-
-		if (hasha <= hashb)
-			return -1;
-	} else if (inuma <= inumb)
-		return -1;
-
-	return 1;
+	if (inuma == inumb)
+		return key_hash(c, &sa->key) - key_hash(c, &sb->key);
+	else
+		return inuma - inumb;
 }
 
 /**
-- 
1.7.1.1

Re: [PATCH 4/7] UBIFS: fix GC sroting

[Adrian Hunter]

Artem Bityutskiy wrote:
> From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> 
> Unfortunately, the comparison functions for both data and non-data nodes
> ('data_nodes_cmp()' and 'nondata_nodes_cmp()') was screwed. It did not
> work for the case when 'inuma == inumb' and 'blka > blkb' or 'hasha > hashb'.

Can you explain a bit more.  The old logic looks OK to me whereas the
new logic would seem to make block 0x80000001 < 0x00000001 ?

> 
> Basically, this means that it did not actually sort the list. This is not
> fatal, but this means that GC did not optimize the on-flash layout as we
> thought it would.
> 
> This issue was revealed by commit '835cc0c8477fdbc59e0217891d6f11061b1ac4e2' of
> Don Mullis: assertions in the comparison functions started triggering.
> 
> This patch fixes the issue. Additionally, it makes the comparison functions
> return immediately the elements to compare are actually the same element.
> This is just a tiny optimization.
> 
> Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> ---
>  fs/ubifs/gc.c |   34 ++++++++++++++--------------------
>  1 files changed, 14 insertions(+), 20 deletions(-)
> 
> diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
> index d060c62..fbb9272 100644
> --- a/fs/ubifs/gc.c
> +++ b/fs/ubifs/gc.c
> @@ -125,6 +125,9 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
>  	struct ubifs_scan_node *sa, *sb;
>  
>  	cond_resched();
> +	if (a == b)
> +		return 0;
> +
>  	sa = list_entry(a, struct ubifs_scan_node, list);
>  	sb = list_entry(b, struct ubifs_scan_node, list);
>  	ubifs_assert(key_type(c, &sa->key) == UBIFS_DATA_KEY);
> @@ -133,16 +136,10 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
>  	inuma = key_inum(c, &sa->key);
>  	inumb = key_inum(c, &sb->key);
>  
> -	if (inuma == inumb) {
> -		unsigned int blka = key_block(c, &sa->key);
> -		unsigned int blkb = key_block(c, &sb->key);
> -
> -		if (blka <= blkb)
> -			return -1;
> -	} else if (inuma <= inumb)
> -		return -1;
> -
> -	return 1;
> +	if (inuma == inumb)
> +		return key_block(c, &sa->key) - key_block(c, &sb->key);
> +	else
> +		return inuma - inumb;
>  }
>  
>  /*
> @@ -163,6 +160,9 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
>  	struct ubifs_scan_node *sa, *sb;
>  
>  	cond_resched();
> +	if (a == b)
> +		return 0;
> +
>  	sa = list_entry(a, struct ubifs_scan_node, list);
>  	sb = list_entry(b, struct ubifs_scan_node, list);
>  	typea = key_type(c, &sa->key);
> @@ -183,16 +183,10 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
>  	inuma = key_inum(c, &sa->key);
>  	inumb = key_inum(c, &sb->key);
>  
> -	if (inuma == inumb) {
> -		uint32_t hasha = key_hash(c, &sa->key);
> -		uint32_t hashb = key_hash(c, &sb->key);
> -
> -		if (hasha <= hashb)
> -			return -1;
> -	} else if (inuma <= inumb)
> -		return -1;
> -
> -	return 1;
> +	if (inuma == inumb)
> +		return key_hash(c, &sa->key) - key_hash(c, &sb->key);
> +	else
> +		return inuma - inumb;
>  }
>  
>  /**

Re: [PATCH 4/7] UBIFS: fix GC sroting

[Artem Bityutskiy]

On Sat, 2010-08-07 at 15:11 +0300, Adrian Hunter wrote:
> Artem Bityutskiy wrote:
> > From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> > 
> > Unfortunately, the comparison functions for both data and non-data nodes
> > ('data_nodes_cmp()' and 'nondata_nodes_cmp()') was screwed. It did not
> > work for the case when 'inuma == inumb' and 'blka > blkb' or 'hasha > hashb'.
> 
> Can you explain a bit more.  The old logic looks OK to me whereas the
> new logic would seem to make block 0x80000001 < 0x00000001 ?

Yes, I need to look once again at this...

-- 
Best Regards,
Artem Bityutskiy (Артём Битюцкий)

[PATCH 5/7] UBIFS: do not look up junk nodes

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

When moving nodes, do not try to look up truncation and padding nodes in TNC,
because they do not exist there. This bug was most probably harmless, because
the TNC look-up probably failed for all padding and truncation nodes, but it
could also succeed and lead to various "interesting" errors.

This patch fixes the issue.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 fs/ubifs/gc.c |   23 ++++++++++++++++++++---
 1 files changed, 20 insertions(+), 3 deletions(-)

diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index fbb9272..f68e58d 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -227,9 +227,26 @@ static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
 	list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
 		int err;
 
-		ubifs_assert(snod->type != UBIFS_IDX_NODE);
-		ubifs_assert(snod->type != UBIFS_REF_NODE);
-		ubifs_assert(snod->type != UBIFS_CS_NODE);
+		ubifs_assert(snod->type == UBIFS_INO_NODE  ||
+			     snod->type == UBIFS_DATA_NODE ||
+			     snod->type == UBIFS_DENT_NODE ||
+			     snod->type == UBIFS_XENT_NODE ||
+			     snod->type == UBIFS_TRUN_NODE ||
+			     snod->type == UBIFS_PAD_NODE);
+		ubifs_assert(key_type(c, &snod->key) == UBIFS_DATA_KEY ||
+			     key_type(c, &snod->key) == UBIFS_INO_KEY  ||
+			     key_type(c, &snod->key) == UBIFS_DENT_KEY ||
+			     key_type(c, &snod->key) == UBIFS_XENT_KEY);
+
+		if (snod->type != UBIFS_INO_NODE  &&
+		    snod->type != UBIFS_DATA_NODE &&
+		    snod->type != UBIFS_DENT_NODE &&
+		    snod->type != UBIFS_XENT_NODE) {
+			/* Truncation or padding node, zap it */
+			list_del(&snod->list);
+			kfree(snod);
+			continue;
+		}
 
 		err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum,
 					 snod->offs, 0);
-- 
1.7.1.1

Re: [PATCH 5/7] UBIFS: do not look up junk nodes

[Adrian Hunter]

Artem Bityutskiy wrote:
> From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> 
> When moving nodes, do not try to look up truncation and padding nodes in TNC,
> because they do not exist there. This bug was most probably harmless, because
> the TNC look-up probably failed for all padding and truncation nodes, but it

The scan does not return padding nodes.

> could also succeed and lead to various "interesting" errors.

Why would it succeed?

> 
> This patch fixes the issue.
> 
> Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> ---
>  fs/ubifs/gc.c |   23 ++++++++++++++++++++---
>  1 files changed, 20 insertions(+), 3 deletions(-)
> 
> diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
> index fbb9272..f68e58d 100644
> --- a/fs/ubifs/gc.c
> +++ b/fs/ubifs/gc.c
> @@ -227,9 +227,26 @@ static int sort_nodes(struct ubifs_info *c, struct ubifs_scan_leb *sleb,
>  	list_for_each_entry_safe(snod, tmp, &sleb->nodes, list) {
>  		int err;
>  
> -		ubifs_assert(snod->type != UBIFS_IDX_NODE);
> -		ubifs_assert(snod->type != UBIFS_REF_NODE);
> -		ubifs_assert(snod->type != UBIFS_CS_NODE);
> +		ubifs_assert(snod->type == UBIFS_INO_NODE  ||
> +			     snod->type == UBIFS_DATA_NODE ||
> +			     snod->type == UBIFS_DENT_NODE ||
> +			     snod->type == UBIFS_XENT_NODE ||
> +			     snod->type == UBIFS_TRUN_NODE ||
> +			     snod->type == UBIFS_PAD_NODE);
> +		ubifs_assert(key_type(c, &snod->key) == UBIFS_DATA_KEY ||
> +			     key_type(c, &snod->key) == UBIFS_INO_KEY  ||
> +			     key_type(c, &snod->key) == UBIFS_DENT_KEY ||
> +			     key_type(c, &snod->key) == UBIFS_XENT_KEY);
> +
> +		if (snod->type != UBIFS_INO_NODE  &&
> +		    snod->type != UBIFS_DATA_NODE &&
> +		    snod->type != UBIFS_DENT_NODE &&
> +		    snod->type != UBIFS_XENT_NODE) {
> +			/* Truncation or padding node, zap it */
> +			list_del(&snod->list);
> +			kfree(snod);
> +			continue;
> +		}
>  
>  		err = ubifs_tnc_has_node(c, &snod->key, 0, sleb->lnum,
>  					 snod->offs, 0);

Re: [PATCH 5/7] UBIFS: do not look up junk nodes

[Artem Bityutskiy]

Adrian, thanks for review!

On Sat, 2010-08-07 at 15:06 +0300, Adrian Hunter wrote:
> Artem Bityutskiy wrote:
> > From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
> > 
> > When moving nodes, do not try to look up truncation and padding nodes in TNC,
> > because they do not exist there. This bug was most probably harmless, because
> > the TNC look-up probably failed for all padding and truncation nodes, but it
> 
> The scan does not return padding nodes.

Oh yes.

> > could also succeed and lead to various "interesting" errors.
> 
> Why would it succeed?

In 'ubifs_add_snod()' we call call 'key_read(c, &ino->key, &snod->key)'
for truncation nodes. However, 'struct ubifs_trun_node' does not have
key, so we read something else, and may happen to succeed in TNC lookup
then.

I guess the 'ubifs_add_snod()' should be fixed. Then key for truncation
nodes will be zero, and TNC lookup wont's succeed for sure, but it is
safer still to avoid look up for anything but data/ino/dent/xent nodes,
I think, no?

-- 
Best Regards,
Artem Bityutskiy (Артём Битюцкий)

[PATCH 6/7] UBIFS: do not use key type in list_sort compariosn fuction

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

Simplify the 'nondata_nodes_cmp()' a bit by using the
'struct ubifs_scan_node->type' field, instead of the key type.

And while on it, add more 'ubifs_assert()' statements to the 'list_sort()'
comparison function in gc.c.

Signed-off-by: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>
---
 fs/ubifs/gc.c |   29 ++++++++++++++++++++---------
 1 files changed, 20 insertions(+), 9 deletions(-)

diff --git a/fs/ubifs/gc.c b/fs/ubifs/gc.c
index f68e58d..0bc6565 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -130,8 +130,11 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 
 	sa = list_entry(a, struct ubifs_scan_node, list);
 	sb = list_entry(b, struct ubifs_scan_node, list);
+
 	ubifs_assert(key_type(c, &sa->key) == UBIFS_DATA_KEY);
 	ubifs_assert(key_type(c, &sb->key) == UBIFS_DATA_KEY);
+	ubifs_assert(sa->type == UBIFS_DATA_NODE);
+	ubifs_assert(sb->type == UBIFS_DATA_NODE);
 
 	inuma = key_inum(c, &sa->key);
 	inumb = key_inum(c, &sb->key);
@@ -154,7 +157,6 @@ int data_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
  */
 int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 {
-	int typea, typeb;
 	ino_t inuma, inumb;
 	struct ubifs_info *c = priv;
 	struct ubifs_scan_node *sa, *sb;
@@ -165,21 +167,30 @@ int nondata_nodes_cmp(void *priv, struct list_head *a, struct list_head *b)
 
 	sa = list_entry(a, struct ubifs_scan_node, list);
 	sb = list_entry(b, struct ubifs_scan_node, list);
-	typea = key_type(c, &sa->key);
-	typeb = key_type(c, &sb->key);
-	ubifs_assert(typea != UBIFS_DATA_KEY && typeb != UBIFS_DATA_KEY);
+
+	ubifs_assert(key_type(c, &sa->key) != UBIFS_DATA_KEY &&
+		     key_type(c, &sb->key) != UBIFS_DATA_KEY);
+	ubifs_assert(sa->type != UBIFS_DATA_NODE &&
+		     sb->type != UBIFS_DATA_NODE);
 
 	/* Inodes go before directory entries */
-	if (typea == UBIFS_INO_KEY) {
-		if (typeb == UBIFS_INO_KEY)
+	if (sa->type == UBIFS_INO_NODE) {
+		if (sb->type == UBIFS_INO_NODE)
 			return sb->len - sa->len;
 		return -1;
 	}
-	if (typeb == UBIFS_INO_KEY)
+	if (sb->type == UBIFS_INO_NODE)
 		return 1;
 
-	ubifs_assert(typea == UBIFS_DENT_KEY || typea == UBIFS_XENT_KEY);
-	ubifs_assert(typeb == UBIFS_DENT_KEY || typeb == UBIFS_XENT_KEY);
+	ubifs_assert(key_type(c, &sa->key) == UBIFS_DENT_KEY ||
+		     key_type(c, &sa->key) == UBIFS_XENT_KEY);
+	ubifs_assert(key_type(c, &sb->key) == UBIFS_DENT_KEY ||
+		     key_type(c, &sb->key) == UBIFS_XENT_KEY);
+	ubifs_assert(sa->type == UBIFS_DENT_NODE ||
+		     sa->type == UBIFS_XENT_NODE);
+	ubifs_assert(sb->type == UBIFS_DENT_NODE ||
+		     sb->type == UBIFS_XENT_NODE);
+
 	inuma = key_inum(c, &sa->key);
 	inumb = key_inum(c, &sb->key);
 
-- 
1.7.1.1

[PATCH 7/7] UBIFS: introduce list sorting debugging checks

[Artem Bityutskiy]

From: Artem Bityutskiy <Artem.Bityutskiy@nokia.com>

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 <Artem.Bityutskiy@nokia.com>
---
 fs/ubifs/debug.c |  154 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/ubifs/debug.h |    4 ++
 fs/ubifs/gc.c    |   10 +++-
 3 files changed, 166 insertions(+), 2 deletions(-)

diff --git a/fs/ubifs/debug.c b/fs/ubifs/debug.c
index c2a68ba..98094a8 100644
--- a/fs/ubifs/debug.c
+++ b/fs/ubifs/debug.c
@@ -2239,6 +2239,160 @@ 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;
+
+		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;
+
+		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 0bc6565..130f983 100644
--- a/fs/ubifs/gc.c
+++ b/fs/ubifs/gc.c
@@ -230,14 +230,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 ||
@@ -281,6 +280,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;
 }
 
-- 
1.7.1.1

Re: [PATCH 0/7] UBIFS: recent patches

[Matthieu CASTET]

Artem Bityutskiy a écrit :
> Hi,
> 
> Matthieu, I failed to figure out how gc_lnum can become -1 in the master node.
> Most probably I'll have to create a debugging patch and ask you to reproduce
> the error again, but do not thing I'll have time for this in August. So, you
> could try to look at the code and put more printk's in interesting places
> yourself, and find when exactly it becomes -1, and then how it ends up in the
> master node. That would be helpful.
Ok,

I will try to see what can I do.


Matthieu