UBIFS: a pair of orphan bugs

UBIFS: a pair of orphan bugs

[Adam Thomas]

Hello linux-mtd,

I recently encountered some UBIFS inconsistencies and tracked it back
to a pair of bugs in orphan delete. There is an assumption in
ubifs_delete_orphan that if the orphan cnext is NULL then it is not on
the cnext list, but that is incorrect for the last orphan on the cnext
list, which results in modifying freed memory. The same assumption is
made for the dnext list, which results in a double free. I am
including two patches that fix these issues by adding flags to
ubifs_orphan for pending commit and pending delete that are used
instead of checking cnext and dnext.

The cnext bug specifically was the cause of the inconsistencies I
encountered and is easy to reproduce. For example, repeatedly
untarring a root filesystem tarball and then removing those files
almost always results in inconsistencies in around 10 iterations. I do
not have a repro case for the dnext bug, I discovered that one due to
its similarity to the cnext list.

Thanks,
-Adam

[PATCH 1/2] UBIFS: fix use of freed ubifs_orphan objects

[Adam Thomas]

The last orphan in the cnext list has its cnext set to NULL. Because
of that, ubifs_delete_orphan assumes that it is not on the cnext list
and frees it immediately instead of adding it to the dnext list. The
freed orphan is later modified by write_orph_node.

This can cause various inconsistencies including directory entries
that cannot be removed and this error:

UBIFS error (pid 20685): layout_cnodes: LPT out of space at LEB 14:129009 needing 17, done_ltab 1, done_lsave 1

This is a regression introduced by
"7074e5eb UBIFS: remove invalid reference to list iterator variable".

This change adds an explicit flag to ubifs_orphan indicating whether
it is pending commit.
---
 fs/ubifs/orphan.c |    6 +++++-
 fs/ubifs/ubifs.h  |    4 +++-
 2 files changed, 8 insertions(+), 2 deletions(-)

diff --git a/fs/ubifs/orphan.c b/fs/ubifs/orphan.c
index 769701c..8433f53 100644
--- a/fs/ubifs/orphan.c
+++ b/fs/ubifs/orphan.c
@@ -132,7 +132,7 @@ void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum)
 					(unsigned long)inum);
 				return;
 			}
-			if (o->cnext) {
+			if (o->cmt) {
 				o->dnext = c->orph_dnext;
 				c->orph_dnext = o;
 				spin_unlock(&c->orphan_lock);
@@ -172,7 +172,9 @@ int ubifs_orphan_start_commit(struct ubifs_info *c)
 	last = &c->orph_cnext;
 	list_for_each_entry(orphan, &c->orph_new, new_list) {
 		ubifs_assert(orphan->new);
+		ubifs_assert(!orphan->cmt);
 		orphan->new = 0;
+		orphan->cmt = 1;
 		*last = orphan;
 		last = &orphan->cnext;
 	}
@@ -299,6 +301,7 @@ static int write_orph_node(struct ubifs_info *c, int atomic)
 	cnext = c->orph_cnext;
 	for (i = 0; i < cnt; i++) {
 		orphan = cnext;
+		ubifs_assert(orphan->cmt);
 		orph->inos[i] = cpu_to_le64(orphan->inum);
 		cnext = orphan->cnext;
 		orphan->cnext = NULL;
@@ -378,6 +381,7 @@ static int consolidate(struct ubifs_info *c)
 		list_for_each_entry(orphan, &c->orph_list, list) {
 			if (orphan->new)
 				continue;
+			orphan->cmt = 1;
 			*last = orphan;
 			last = &orphan->cnext;
 			cnt += 1;
diff --git a/fs/ubifs/ubifs.h b/fs/ubifs/ubifs.h
index d133c27..c16fff7 100644
--- a/fs/ubifs/ubifs.h
+++ b/fs/ubifs/ubifs.h
@@ -904,6 +904,7 @@ struct ubifs_budget_req {
  * @dnext: next orphan to delete
  * @inum: inode number
  * @new: %1 => added since the last commit, otherwise %0
+ * @cmt: %1 => commit pending, otherwise %0
  */
 struct ubifs_orphan {
 	struct rb_node rb;
@@ -912,7 +913,8 @@ struct ubifs_orphan {
 	struct ubifs_orphan *cnext;
 	struct ubifs_orphan *dnext;
 	ino_t inum;
-	int new;
+	unsigned new:1;
+	unsigned cmt:1;
 };
 
 /**
-- 
1.7.9.5

Re: [PATCH 1/2] UBIFS: fix use of freed ubifs_orphan objects

[Adrian Hunter]

On 28/01/13 03:28, Adam Thomas wrote:
> The last orphan in the cnext list has its cnext set to NULL. Because
> of that, ubifs_delete_orphan assumes that it is not on the cnext list
> and frees it immediately instead of adding it to the dnext list. The
> freed orphan is later modified by write_orph_node.

Very true!

> 
> This can cause various inconsistencies including directory entries
> that cannot be removed and this error:
> 
> UBIFS error (pid 20685): layout_cnodes: LPT out of space at LEB 14:129009 needing 17, done_ltab 1, done_lsave 1
> 
> This is a regression introduced by
> "7074e5eb UBIFS: remove invalid reference to list iterator variable".
> 
> This change adds an explicit flag to ubifs_orphan indicating whether
> it is pending commit.

OK

Needs an signed-off line.

> ---
>  fs/ubifs/orphan.c |    6 +++++-
>  fs/ubifs/ubifs.h  |    4 +++-
>  2 files changed, 8 insertions(+), 2 deletions(-)
> 
> diff --git a/fs/ubifs/orphan.c b/fs/ubifs/orphan.c
> index 769701c..8433f53 100644
> --- a/fs/ubifs/orphan.c
> +++ b/fs/ubifs/orphan.c
> @@ -132,7 +132,7 @@ void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum)
>  					(unsigned long)inum);
>  				return;
>  			}
> -			if (o->cnext) {
> +			if (o->cmt) {
>  				o->dnext = c->orph_dnext;
>  				c->orph_dnext = o;
>  				spin_unlock(&c->orphan_lock);
> @@ -172,7 +172,9 @@ int ubifs_orphan_start_commit(struct ubifs_info *c)
>  	last = &c->orph_cnext;
>  	list_for_each_entry(orphan, &c->orph_new, new_list) {
>  		ubifs_assert(orphan->new);
> +		ubifs_assert(!orphan->cmt);
>  		orphan->new = 0;
> +		orphan->cmt = 1;
>  		*last = orphan;
>  		last = &orphan->cnext;
>  	}
> @@ -299,6 +301,7 @@ static int write_orph_node(struct ubifs_info *c, int atomic)
>  	cnext = c->orph_cnext;
>  	for (i = 0; i < cnt; i++) {
>  		orphan = cnext;
> +		ubifs_assert(orphan->cmt);
>  		orph->inos[i] = cpu_to_le64(orphan->inum);
>  		cnext = orphan->cnext;
>  		orphan->cnext = NULL;
> @@ -378,6 +381,7 @@ static int consolidate(struct ubifs_info *c)
>  		list_for_each_entry(orphan, &c->orph_list, list) {
>  			if (orphan->new)
>  				continue;
> +			orphan->cmt = 1;
>  			*last = orphan;
>  			last = &orphan->cnext;
>  			cnt += 1;
> diff --git a/fs/ubifs/ubifs.h b/fs/ubifs/ubifs.h
> index d133c27..c16fff7 100644
> --- a/fs/ubifs/ubifs.h
> +++ b/fs/ubifs/ubifs.h
> @@ -904,6 +904,7 @@ struct ubifs_budget_req {
>   * @dnext: next orphan to delete
>   * @inum: inode number
>   * @new: %1 => added since the last commit, otherwise %0
> + * @cmt: %1 => commit pending, otherwise %0

You need to set cmt to zero in write_orph_node().

>   */
>  struct ubifs_orphan {
>  	struct rb_node rb;
> @@ -912,7 +913,8 @@ struct ubifs_orphan {
>  	struct ubifs_orphan *cnext;
>  	struct ubifs_orphan *dnext;
>  	ino_t inum;
> -	int new;
> +	unsigned new:1;
> +	unsigned cmt:1;
>  };
>  
>  /**
> 

Re: [PATCH 1/2] UBIFS: fix use of freed ubifs_orphan objects

[Adam Thomas]

On Fri, Feb 1, 2013 at 5:23 AM, Adrian Hunter wrote:
> OK
> 
> Needs an signed-off line.

Thanks for the review.  Added.

> You need to set cmt to zero in write_orph_node().

Fixed.

Thanks,
-Adam

[PATCH v2 1/2] UBIFS: fix use of freed ubifs_orphan objects

[Adam Thomas]

The last orphan in the cnext list has its cnext set to NULL. Because
of that, ubifs_delete_orphan assumes that it is not on the cnext list
and frees it immediately instead of adding it to the dnext list. The
freed orphan is later modified by write_orph_node.

This can cause various inconsistencies including directory entries
that cannot be removed and this error:

UBIFS error (pid 20685): layout_cnodes: LPT out of space at LEB 14:129009 needing 17, done_ltab 1, done_lsave 1

This is a regression introduced by
"7074e5eb UBIFS: remove invalid reference to list iterator variable".

This change adds an explicit flag to ubifs_orphan indicating whether
it is pending commit.

Signed-off-by: Adam Thomas <adamthomas1111@gmail.com>
---
 fs/ubifs/orphan.c |    7 ++++++-
 fs/ubifs/ubifs.h  |    4 +++-
 2 files changed, 9 insertions(+), 2 deletions(-)

diff --git a/fs/ubifs/orphan.c b/fs/ubifs/orphan.c
index 769701c..8534d9c 100644
--- a/fs/ubifs/orphan.c
+++ b/fs/ubifs/orphan.c
@@ -132,7 +132,7 @@ void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum)
 					(unsigned long)inum);
 				return;
 			}
-			if (o->cnext) {
+			if (o->cmt) {
 				o->dnext = c->orph_dnext;
 				c->orph_dnext = o;
 				spin_unlock(&c->orphan_lock);
@@ -172,7 +172,9 @@ int ubifs_orphan_start_commit(struct ubifs_info *c)
 	last = &c->orph_cnext;
 	list_for_each_entry(orphan, &c->orph_new, new_list) {
 		ubifs_assert(orphan->new);
+		ubifs_assert(!orphan->cmt);
 		orphan->new = 0;
+		orphan->cmt = 1;
 		*last = orphan;
 		last = &orphan->cnext;
 	}
@@ -299,7 +301,9 @@ static int write_orph_node(struct ubifs_info *c, int atomic)
 	cnext = c->orph_cnext;
 	for (i = 0; i < cnt; i++) {
 		orphan = cnext;
+		ubifs_assert(orphan->cmt);
 		orph->inos[i] = cpu_to_le64(orphan->inum);
+		orphan->cmt = 0;
 		cnext = orphan->cnext;
 		orphan->cnext = NULL;
 	}
@@ -378,6 +382,7 @@ static int consolidate(struct ubifs_info *c)
 		list_for_each_entry(orphan, &c->orph_list, list) {
 			if (orphan->new)
 				continue;
+			orphan->cmt = 1;
 			*last = orphan;
 			last = &orphan->cnext;
 			cnt += 1;
diff --git a/fs/ubifs/ubifs.h b/fs/ubifs/ubifs.h
index d133c27..c16fff7 100644
--- a/fs/ubifs/ubifs.h
+++ b/fs/ubifs/ubifs.h
@@ -904,6 +904,7 @@ struct ubifs_budget_req {
  * @dnext: next orphan to delete
  * @inum: inode number
  * @new: %1 => added since the last commit, otherwise %0
+ * @cmt: %1 => commit pending, otherwise %0
  */
 struct ubifs_orphan {
 	struct rb_node rb;
@@ -912,7 +913,8 @@ struct ubifs_orphan {
 	struct ubifs_orphan *cnext;
 	struct ubifs_orphan *dnext;
 	ino_t inum;
-	int new;
+	unsigned new:1;
+	unsigned cmt:1;
 };
 
 /**
-- 
1.7.9.5

Re: [PATCH v2 1/2] UBIFS: fix use of freed ubifs_orphan objects

[Artem Bityutskiy]

[-- Attachment #1: Type: text/plain, Size: 949 bytes --]

On Sat, 2013-02-02 at 22:32 +0000, Adam Thomas wrote:
> The last orphan in the cnext list has its cnext set to NULL. Because
> of that, ubifs_delete_orphan assumes that it is not on the cnext list
> and frees it immediately instead of adding it to the dnext list. The
> freed orphan is later modified by write_orph_node.
> 
> This can cause various inconsistencies including directory entries
> that cannot be removed and this error:
> 
> UBIFS error (pid 20685): layout_cnodes: LPT out of space at LEB 14:129009 needing 17, done_ltab 1, done_lsave 1
> 
> This is a regression introduced by
> "7074e5eb UBIFS: remove invalid reference to list iterator variable".
> 
> This change adds an explicit flag to ubifs_orphan indicating whether
> it is pending commit.
> 
> Signed-off-by: Adam Thomas <adamthomas1111@gmail.com>

Pushed both to linux-ubifs.git, added 'Cc: stable@vger.kernel.org'.

-- 
Best Regards,
Artem Bityutskiy

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

[PATCH 2/2] UBIFS: fix double free of ubifs_orphan objects

[Adam Thomas]

The last orphan in the dnext list has its dnext set to NULL. Because
of that, ubifs_delete_orphan assumes that it is not on the dnext list
and frees it immediately instead ignoring it as a second delete. The
orphan is later freed again by erase_deleted.

This change adds an explicit flag to ubifs_orphan indicating whether
it is pending delete.
---
 fs/ubifs/orphan.c |    5 ++++-
 fs/ubifs/ubifs.h  |    2 ++
 2 files changed, 6 insertions(+), 1 deletion(-)

diff --git a/fs/ubifs/orphan.c b/fs/ubifs/orphan.c
index 8433f53..071d607 100644
--- a/fs/ubifs/orphan.c
+++ b/fs/ubifs/orphan.c
@@ -126,13 +126,14 @@ void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum)
 		else if (inum > o->inum)
 			p = p->rb_right;
 		else {
-			if (o->dnext) {
+			if (o->del) {
 				spin_unlock(&c->orphan_lock);
 				dbg_gen("deleted twice ino %lu",
 					(unsigned long)inum);
 				return;
 			}
 			if (o->cmt) {
+				o->del = 1;
 				o->dnext = c->orph_dnext;
 				c->orph_dnext = o;
 				spin_unlock(&c->orphan_lock);
@@ -446,6 +447,7 @@ static void erase_deleted(struct ubifs_info *c)
 		orphan = dnext;
 		dnext = orphan->dnext;
 		ubifs_assert(!orphan->new);
+		ubifs_assert(orphan->del);
 		rb_erase(&orphan->rb, &c->orph_tree);
 		list_del(&orphan->list);
 		c->tot_orphans -= 1;
@@ -535,6 +537,7 @@ static int insert_dead_orphan(struct ubifs_info *c, ino_t inum)
 	rb_link_node(&orphan->rb, parent, p);
 	rb_insert_color(&orphan->rb, &c->orph_tree);
 	list_add_tail(&orphan->list, &c->orph_list);
+	orphan->del = 1;
 	orphan->dnext = c->orph_dnext;
 	c->orph_dnext = orphan;
 	dbg_mnt("ino %lu, new %d, tot %d", (unsigned long)inum,
diff --git a/fs/ubifs/ubifs.h b/fs/ubifs/ubifs.h
index c16fff7..b2babce 100644
--- a/fs/ubifs/ubifs.h
+++ b/fs/ubifs/ubifs.h
@@ -905,6 +905,7 @@ struct ubifs_budget_req {
  * @inum: inode number
  * @new: %1 => added since the last commit, otherwise %0
  * @cmt: %1 => commit pending, otherwise %0
+ * @del: %1 => delete pending, otherwise %0
  */
 struct ubifs_orphan {
 	struct rb_node rb;
@@ -915,6 +916,7 @@ struct ubifs_orphan {
 	ino_t inum;
 	unsigned new:1;
 	unsigned cmt:1;
+	unsigned del:1;
 };
 
 /**
-- 
1.7.9.5

Re: [PATCH 2/2] UBIFS: fix double free of ubifs_orphan objects

[Adrian Hunter]

On 28/01/13 03:28, Adam Thomas wrote:
> The last orphan in the dnext list has its dnext set to NULL. Because
> of that, ubifs_delete_orphan assumes that it is not on the dnext list
> and frees it immediately instead ignoring it as a second delete. The
> orphan is later freed again by erase_deleted.

In fact, unless something has gone wrong, an inode is only ever deleted once.

> 
> This change adds an explicit flag to ubifs_orphan indicating whether
> it is pending delete.

Needs an signed-off line.

Reviewed-by: Adrian Hunter <adrian.hunter@intel.com>

> ---
>  fs/ubifs/orphan.c |    5 ++++-
>  fs/ubifs/ubifs.h  |    2 ++
>  2 files changed, 6 insertions(+), 1 deletion(-)
> 
> diff --git a/fs/ubifs/orphan.c b/fs/ubifs/orphan.c
> index 8433f53..071d607 100644
> --- a/fs/ubifs/orphan.c
> +++ b/fs/ubifs/orphan.c
> @@ -126,13 +126,14 @@ void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum)
>  		else if (inum > o->inum)
>  			p = p->rb_right;
>  		else {
> -			if (o->dnext) {
> +			if (o->del) {
>  				spin_unlock(&c->orphan_lock);
>  				dbg_gen("deleted twice ino %lu",
>  					(unsigned long)inum);
>  				return;
>  			}
>  			if (o->cmt) {
> +				o->del = 1;
>  				o->dnext = c->orph_dnext;
>  				c->orph_dnext = o;
>  				spin_unlock(&c->orphan_lock);
> @@ -446,6 +447,7 @@ static void erase_deleted(struct ubifs_info *c)
>  		orphan = dnext;
>  		dnext = orphan->dnext;
>  		ubifs_assert(!orphan->new);
> +		ubifs_assert(orphan->del);
>  		rb_erase(&orphan->rb, &c->orph_tree);
>  		list_del(&orphan->list);
>  		c->tot_orphans -= 1;
> @@ -535,6 +537,7 @@ static int insert_dead_orphan(struct ubifs_info *c, ino_t inum)
>  	rb_link_node(&orphan->rb, parent, p);
>  	rb_insert_color(&orphan->rb, &c->orph_tree);
>  	list_add_tail(&orphan->list, &c->orph_list);
> +	orphan->del = 1;
>  	orphan->dnext = c->orph_dnext;
>  	c->orph_dnext = orphan;
>  	dbg_mnt("ino %lu, new %d, tot %d", (unsigned long)inum,
> diff --git a/fs/ubifs/ubifs.h b/fs/ubifs/ubifs.h
> index c16fff7..b2babce 100644
> --- a/fs/ubifs/ubifs.h
> +++ b/fs/ubifs/ubifs.h
> @@ -905,6 +905,7 @@ struct ubifs_budget_req {
>   * @inum: inode number
>   * @new: %1 => added since the last commit, otherwise %0
>   * @cmt: %1 => commit pending, otherwise %0
> + * @del: %1 => delete pending, otherwise %0
>   */
>  struct ubifs_orphan {
>  	struct rb_node rb;
> @@ -915,6 +916,7 @@ struct ubifs_orphan {
>  	ino_t inum;
>  	unsigned new:1;
>  	unsigned cmt:1;
> +	unsigned del:1;
>  };
>  
>  /**
> 

[PATCH v2 2/2] UBIFS: fix double free of ubifs_orphan objects

[Adam Thomas]

The last orphan in the dnext list has its dnext set to NULL. Because
of that, ubifs_delete_orphan assumes that it is not on the dnext list
and frees it immediately instead ignoring it as a second delete. The
orphan is later freed again by erase_deleted.

This change adds an explicit flag to ubifs_orphan indicating whether
it is pending delete.

Signed-off-by: Adam Thomas <adamthomas1111@gmail.com>
---
 fs/ubifs/orphan.c |    5 ++++-
 fs/ubifs/ubifs.h  |    2 ++
 2 files changed, 6 insertions(+), 1 deletion(-)

diff --git a/fs/ubifs/orphan.c b/fs/ubifs/orphan.c
index 8534d9c..ba32da3 100644
--- a/fs/ubifs/orphan.c
+++ b/fs/ubifs/orphan.c
@@ -126,13 +126,14 @@ void ubifs_delete_orphan(struct ubifs_info *c, ino_t inum)
 		else if (inum > o->inum)
 			p = p->rb_right;
 		else {
-			if (o->dnext) {
+			if (o->del) {
 				spin_unlock(&c->orphan_lock);
 				dbg_gen("deleted twice ino %lu",
 					(unsigned long)inum);
 				return;
 			}
 			if (o->cmt) {
+				o->del = 1;
 				o->dnext = c->orph_dnext;
 				c->orph_dnext = o;
 				spin_unlock(&c->orphan_lock);
@@ -447,6 +448,7 @@ static void erase_deleted(struct ubifs_info *c)
 		orphan = dnext;
 		dnext = orphan->dnext;
 		ubifs_assert(!orphan->new);
+		ubifs_assert(orphan->del);
 		rb_erase(&orphan->rb, &c->orph_tree);
 		list_del(&orphan->list);
 		c->tot_orphans -= 1;
@@ -536,6 +538,7 @@ static int insert_dead_orphan(struct ubifs_info *c, ino_t inum)
 	rb_link_node(&orphan->rb, parent, p);
 	rb_insert_color(&orphan->rb, &c->orph_tree);
 	list_add_tail(&orphan->list, &c->orph_list);
+	orphan->del = 1;
 	orphan->dnext = c->orph_dnext;
 	c->orph_dnext = orphan;
 	dbg_mnt("ino %lu, new %d, tot %d", (unsigned long)inum,
diff --git a/fs/ubifs/ubifs.h b/fs/ubifs/ubifs.h
index c16fff7..b2babce 100644
--- a/fs/ubifs/ubifs.h
+++ b/fs/ubifs/ubifs.h
@@ -905,6 +905,7 @@ struct ubifs_budget_req {
  * @inum: inode number
  * @new: %1 => added since the last commit, otherwise %0
  * @cmt: %1 => commit pending, otherwise %0
+ * @del: %1 => delete pending, otherwise %0
  */
 struct ubifs_orphan {
 	struct rb_node rb;
@@ -915,6 +916,7 @@ struct ubifs_orphan {
 	ino_t inum;
 	unsigned new:1;
 	unsigned cmt:1;
+	unsigned del:1;
 };
 
 /**
-- 
1.7.9.5