Skip to contentSkip to conversation

UBIFS: a pair of orphan bugs

PATCH Superseded Adam Thomas 3 participants 9 messages Jan 28, 2013 – Feb 4, 2013

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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

#1 lore raw

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

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(-)
fs/ubifs/orphan.c +5 -1
index 769701c..8433f53 100644
@@ -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;
fs/ubifs/ubifs.h +3 -1
index d133c27..c16fff7 100644
@@ -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;
 };
 
 /**
Signature · 1 line
1.7.9.5
#2 lore raw

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

Quoted 4 lines · 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.

Very true!

Quoted 11 lines

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.

Quoted 49 lines
---
 fs/ubifs/orphan.c |    6 +++++-
 fs/ubifs/ubifs.h  |    4 +++-
 2 files changed, 8 insertions(+), 2 deletions(-)
fs/ubifs/orphan.c +5 -1
index 769701c..8433f53 100644
@@ -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;
fs/ubifs/ubifs.h +0 -0
index d133c27..c16fff7 100644

fs/ubifs/ubifs.h struct ubifs_budget_req { · line 907

Quoted 4 lines
fs/ubifs/ubifs.h +1 -0
@@ -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().

Quoted 14 lines
fs/ubifs/ubifs.h +2 -1
  */
 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;
 };
 
 /**
#3 lore raw

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

Quoted 3 lines · Adrian Hunter

OK

Needs an signed-off line.

Thanks for the review. Added.

Quoted 1 line

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

Fixed.

Thanks,
-Adam

#4 lore raw

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

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 |    7 ++++++-
 fs/ubifs/ubifs.h  |    4 +++-
 2 files changed, 9 insertions(+), 2 deletions(-)
fs/ubifs/orphan.c +6 -1
index 769701c..8534d9c 100644
@@ -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;
fs/ubifs/ubifs.h +3 -1
index d133c27..c16fff7 100644
@@ -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;
 };
 
 /**
Signature · 1 line
1.7.9.5
#5 lore raw

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

Quoted 10 lines · 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

Quoted 7 lines

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.

Pushed both to linux-ubifs.git, added 'Cc: [email protected]'.

Signature · 2 lines
Best Regards,
Artem Bityutskiy
#6 lore raw

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

In reply to 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(-)
fs/ubifs/orphan.c +4 -1
index 8433f53..071d607 100644
@@ -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,
fs/ubifs/ubifs.h +2 -0
index c16fff7..b2babce 100644
@@ -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;
 };
 
 /**
Signature · 1 line
1.7.9.5
Reviewed-by on v1 2/2
#7 lore raw

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

Quoted 4 lines · 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.

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

Quoted 3 lines

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

Needs an signed-off line.

Quoted 62 lines
---
 fs/ubifs/orphan.c |    5 ++++-
 fs/ubifs/ubifs.h  |    2 ++
 2 files changed, 6 insertions(+), 1 deletion(-)
fs/ubifs/orphan.c +4 -1
index 8433f53..071d607 100644
@@ -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,
fs/ubifs/ubifs.h +2 -0
index c16fff7..b2babce 100644
@@ -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;
 };
 
 /**
#8 lore raw

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

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(-)
fs/ubifs/orphan.c +4 -1
index 8534d9c..ba32da3 100644
@@ -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,
fs/ubifs/ubifs.h +2 -0
index c16fff7..b2babce 100644
@@ -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;
 };
 
 /**
Signature · 1 line
1.7.9.5