UBIFS: a pair of orphan bugs
Subsystems (2)
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
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
@@ -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
@@ -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
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_orphanassumes 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 bywrite_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_ltab1,done_lsave1This is a regression introduced by
"7074e5ebUBIFS: remove invalid reference to list iterator variable".This change adds an explicit flag to
ubifs_orphanindicating 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@@ -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
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; };/**
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
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
@@ -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
@@ -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
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_orphanassumes 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 bywrite_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_ltab1,done_lsave1
Quoted 7 lines
This is a regression introduced by
"7074e5ebUBIFS: remove invalid reference to list iterator variable".This change adds an explicit flag to
ubifs_orphanindicating whether it is pending commit.Signed-off-by Adam Thomas <[email protected]>
Pushed both to linux-ubifs.git, added 'Cc: [email protected]'.
Signature · 2 lines
Best Regards, Artem Bityutskiy
PATCH 2/2 UBIFS: fix double free of ubifs_orphan objects
In reply to Adam ThomasThe 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
@@ -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
@@ -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
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_orphanassumes 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 byerase_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_orphanindicating 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@@ -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@@ -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
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
@@ -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
@@ -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