[PATCH 1/2] ubifs: tnc_delete: Don't free zero-branch znodes if memory allocation fails

[Zhihao Cheng]

The freed zero-branch znodes won't be removed from TNC if a failure
(eg. mem alloc in insert_old_idx_znode) happens in tnc_delete, then
TNC traversing could access the freed znodes, the details shown as:

 file: consists of many data nodes, TNC is:
                       znode_A (lv 2)
		 /                       \
         znode (lv 1)                 znode_B (lv 1)
	  /        \                      |
    znode(lv 0)...znode(lv 0)         znode_C (lv 0, child_cnt = 1)
    |    |    |    |	  |               |
 ino_1 ino_f dent dn0...dn_i-1		dn_i

    P1
 truncate(file, dn_i-1)
  ubifs_setattr
   ubifs_jnl_truncate
    ubifs_tnc_remove_range
     tnc_delete // dn_i is removed, znode_C->child_cnt becomes 0
      do-while
       kfree(znode_C)
       ENOMEM = insert_old_idx_znode(c, znode_B)
       return
      znode->zbranch[i] = znode->zbranch[i + 1] // skip,
      // znode_C is still in TNC

 the TNC looks like:
                       znode_A (lv 2)
		 /                       \
         znode (lv 1)                 znode_B (lv 1)
	  /        \                      |
    znode(lv 0)...znode(lv 0)         znode_C (lv 0, child_cnt = 0, freed)
    |    |    |    |	  |
 ino_1 ino_f dent dn0...dn_i-1

     P2
 drop_caches_sysctl_handler
  shrink_slab
   ubifs_shrink_scan
    shrink_tnc_trees
     shrink_tnc
      ubifs_tnc_levelorder_next
       access znode_C // UAF

The root cause is that zero-branch znodes freeing & znode->zbranch is not
atomic, which could be interrupted by the insert_old_idx_znode() failure,
fix it by freeing znodes after all insert_old_idx_znode() callers success.
The znodes collapsing won't meet the problem if insert_old_idx() fails,
because znode is freed after updating c->zroot, the TNC traversing won't
access a freed znode.
Notice: we add new field 'fnext' in struct ubifs_znode to trace to be
freed znodes. Because tnc_delete and do_commit could race, the members
parent/cnext/cparent can not be reused. Importing a stack array to record
znodes is also not recommended, becase the UBIFS_MAX_LEVELS*sizeof(ptr)
becomes 4096, which may cause the compiler to complain.

Reproducer is https://bugzilla.kernel.org/show_bug.cgi?id=222129.

Fixes: 1e51764a3c2a ("UBIFS: add new flash file system")
Signed-off-by: Zhihao Cheng <chengzhihao1 at huawei.com>
---
 fs/ubifs/tnc.c   | 40 +++++++++++++++++++++++++++++++---------
 fs/ubifs/ubifs.h |  2 ++
 2 files changed, 33 insertions(+), 9 deletions(-)

diff --git a/fs/ubifs/tnc.c b/fs/ubifs/tnc.c
index 776e6bc6a00d..679afddadf82 100644
--- a/fs/ubifs/tnc.c
+++ b/fs/ubifs/tnc.c
@@ -2514,8 +2514,9 @@ int ubifs_tnc_add_nm(struct ubifs_info *c, const union ubifs_key *key,
 static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n)
 {
 	struct ubifs_zbranch *zbr;
-	struct ubifs_znode *zp;
+	struct ubifs_znode *zp, *zn;
 	int i, err;
+	struct ubifs_znode free_head = { .fnext = NULL };
 
 	/* Delete without merge for now */
 	ubifs_assert(c, znode->level == 0);
@@ -2543,7 +2544,7 @@ static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n)
 	 * This was the last zbranch, we have to delete this znode from the
 	 * parent.
 	 */
-
+	zn = &free_head;
 	do {
 		ubifs_assert(c, !ubifs_zn_obsolete(znode));
 		ubifs_assert(c, ubifs_zn_dirty(znode));
@@ -2554,15 +2555,20 @@ static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n)
 		atomic_long_dec(&c->dirty_zn_cnt);
 
 		err = insert_old_idx_znode(c, znode);
-		if (err)
+		if (err) {
+			zn = free_head.fnext;
+			while (zn) {
+				struct ubifs_znode *next = zn->fnext;
+
+				zn->fnext = NULL;
+				zn = next;
+			}
 			return err;
+		}
+
+		zn->fnext = znode;
+		zn = znode;
 
-		if (znode->cnext) {
-			__set_bit(OBSOLETE_ZNODE, &znode->flags);
-			atomic_long_inc(&c->clean_zn_cnt);
-			atomic_long_inc(&ubifs_clean_zn_cnt);
-		} else
-			kfree(znode);
 		znode = zp;
 	} while (znode->child_cnt == 1); /* while removing last child */
 
@@ -2575,6 +2581,22 @@ static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n)
 			znode->zbranch[i].znode->iip = i;
 	}
 
+	/* Free zero-branchs znodes. */
+	zn = free_head.fnext;
+	while (zn) {
+		struct ubifs_znode *next = zn->fnext;
+
+		zn->fnext = NULL;
+		if (zn->cnext) {
+			__set_bit(OBSOLETE_ZNODE, &zn->flags);
+			atomic_long_inc(&c->clean_zn_cnt);
+			atomic_long_inc(&ubifs_clean_zn_cnt);
+		} else {
+			kfree(zn);
+		}
+		zn = next;
+	}
+
 	/*
 	 * If this is the root and it has only 1 child then
 	 * collapse the tree.
diff --git a/fs/ubifs/ubifs.h b/fs/ubifs/ubifs.h
index 00db0d19a85e..c3ae7c2625a4 100644
--- a/fs/ubifs/ubifs.h
+++ b/fs/ubifs/ubifs.h
@@ -761,6 +761,7 @@ struct ubifs_zbranch {
  * @parent: parent znode or NULL if it is the root
  * @cnext: next znode to commit
  * @cparent: parent node for this commit
+ * @fnext: next znode to free
  * @ciip: index in cparent's zbranch array
  * @flags: znode flags (%DIRTY_ZNODE, %COW_ZNODE or %OBSOLETE_ZNODE)
  * @time: last access time (seconds)
@@ -780,6 +781,7 @@ struct ubifs_znode {
 	struct ubifs_znode *parent;
 	struct ubifs_znode *cnext;
 	struct ubifs_znode *cparent;
+	struct ubifs_znode *fnext;
 	int ciip;
 	unsigned long flags;
 	time64_t time;
-- 
2.52.0