[PATCH RESEND 0/3] udf: fix double allocation from the unallocated space table

[PATCH RESEND 0/3] udf: fix double allocation from the unallocated space table

[Matthias Goergens]

Hi Honza,

Resent because the first posting went out without threading; nothing
else has changed.

A filesystem made with "mkudffs --space=unalloctable" hands out blocks
that are still in use, for two separate reasons.

Patch 1: udf_table_new_block() keeps the extent type in the length
word, so an exhausted type-1 table extent (the type mkudffs writes)
survives as a zero-length extent pointing at an in-use block, and the
next allocation from it underflows into about a gigabyte of "free"
space.  Filling a fresh 1 MiB image with empty files is enough to
overwrite the reserve VDS and the backup anchor.  This is the double
allocation behind the two syzbot reports linked in the patch.

Patch 2 checks the table once at mount and refuses read-write access
if it is damaged, for example by the bug in patch 1.

Patch 3: when a file's extent list ends in an empty allocation extent,
udf_next_aext() returns 0 with its outputs describing the continuation
descriptor, and udf_discard_prealloc() frees that block a second time
instead of the preallocated blocks.  On a table the block is then
handed out twice, and the fsx runs of generic/091 and generic/263 read
back bad data, with or without patches 1 and 2.  On a bitmap the
preallocated blocks leak.

With the series, fstests -g quick (2 GiB images; KASAN, UBSAN and
lockdep enabled) passes generic/091 and generic/263 on a table.  The
remaining failures (generic/131, 360, 563, 634 and 777, and a hang in
generic/346) are the same without the series and on a bitmap, where
the series changes no result.  The reproducers are below the --- of
patches 1 and 3.

The series is based on your for_next and applies to v7.3-rc5 as well.

Thanks,
Matthias

---
For stable: patch 3 builds on the int return of udf_next_aext()
(b405c1e58b73, v6.12, also backported to 6.6.y) and applies as is to
6.6.y and later; older stable trees need a trivial adaptation.

Matthias Goergens (3):
  udf: don't let the extent type hide an exhausted free-space table
    extent
  udf: check the unallocated space table when it is loaded
  udf: leave udf_next_aext() outputs alone at the end of the extent list

 fs/udf/balloc.c |  9 ++++--
 fs/udf/inode.c  | 21 ++++++++++---
 fs/udf/super.c  | 80 ++++++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 102 insertions(+), 8 deletions(-)


base-commit: ba5855e74bcd761123e39f4708834a0015a74a8b
-- 
2.55.0

[PATCH RESEND 1/3] udf: don't let the extent type hide an exhausted free-space table extent

[Matthias Goergens]

udf_table_new_block() takes the first block of the free-space table
extent closest to the goal.  It keeps that extent's type and length
together in goal_elen, subtracts one block, and deletes the extent only
if goal_elen then reaches zero.  UDF 2.60 section 2.3.7.1 requires the
free-space extents of an Unallocated Space Entry to be of type 1
(allocated but not recorded), and mkudffs writes them that way.  For
such an extent the type bits keep goal_elen non-zero, so taking its last
block leaves a type-1 extent of length zero behind, starting at the
block after the extent, which is in use.

The next allocation that picks this empty extent returns that in-use
block.  Subtracting a block from 0x40000000 then borrows from the type
bits, and the extent becomes type 0 with a length of 2^30 - blocksize:
about a gigabyte of "free" space overlapping live metadata, the other
table extents and whatever lies behind the partition.  From then on
blocks are handed out twice, or past the end of the partition.

Extents that udf_table_free_blocks() adds are type 0, where the check
works, so only tables written by mkudffs or by another implementation
are affected.  Nothing more than filling such a filesystem is needed:
on a fresh 1 MiB "mkudffs --space=unalloctable" image, creating empty
files until the partition is full writes file entries over the reserve
volume descriptor sequence and the backup anchor, and df then reports a
negative amount of used space.

On syzbot's images the same double allocation is what the two reports
below trip over.  In the first, ftruncate() extends a new file with
enough hole extents to need a chain of allocation extent descriptors;
one AED is placed on another inode's file entry, and a later one is
placed on the block of the AED currently being filled, which
udf_setup_indirect_aext() zeroes, so __udf_add_aext() finds
lengthAllocDescs out of step with its cursor.  In the second, an AED
is placed past the end of the device, sb_getblk() fails, and the error
path of udf_do_extend_file() calls udf_truncate_extents() on an extent
list that no longer covers i_size.

Keep the type separately from the length, as udf_table_prealloc_blocks()
already does.

Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
Cc: stable@vger.kernel.org
Reported-by: syzbot+799a0e744ac47f928024@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=799a0e744ac47f928024
Reported-by: syzbot+43fc5ba6dcb33e3261ca@syzkaller.appspotmail.com
Closes: https://syzkaller.appspot.com/bug?extid=43fc5ba6dcb33e3261ca
Signed-off-by: Matthias Goergens <matthias.goergens@gmail.com>
---
Reproducer, with mkudffs from udftools:

  truncate --size=1M udf.img
  mkudffs --blocksize=512 --space=unalloctable udf.img
  mount -t udf -o loop udf.img /mnt
  mkdir /mnt/d
  i=0; while touch /mnt/d/f$i 2> /dev/null; do i=$((i + 1)); done
  df /mnt
  umount /mnt
  dd if=udf.img bs=512 skip=2047 count=1 | od -A n -t u2 -N 2

Without this patch df shows a negative used count, and the last block,
the backup anchor (tag identifier 2), now holds an extended file entry
(266).  With it, file creation stops when the partition is full, df
shows it 100% used, and the anchor is intact.

 fs/udf/balloc.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/fs/udf/balloc.c b/fs/udf/balloc.c
index 30cec5600149..2ec577b4321c 100644
--- a/fs/udf/balloc.c
+++ b/fs/udf/balloc.c
@@ -572,7 +572,7 @@ static udf_pblk_t udf_table_new_block(struct super_block *sb,
 	uint32_t elen, goal_elen = 0;
 	struct kernel_lb_addr eloc, goal_eloc;
 	struct extent_position epos, goal_epos;
-	int8_t etype;
+	int8_t etype, goal_etype = 0;
 	struct udf_inode_info *iinfo = UDF_I(table);
 	int ret = 0;
 
@@ -623,7 +623,8 @@ static udf_pblk_t udf_table_new_block(struct super_block *sb,
 			goal_epos.block = epos.block;
 			goal_epos.offset = epos.offset - adsize;
 			goal_eloc = eloc;
-			goal_elen = (etype << 30) | elen;
+			goal_elen = elen;
+			goal_etype = etype;
 		}
 	}
 
@@ -647,7 +648,8 @@ static udf_pblk_t udf_table_new_block(struct super_block *sb,
 	goal_elen -= sb->s_blocksize;
 
 	if (goal_elen)
-		udf_write_aext(table, &goal_epos, &goal_eloc, goal_elen, 1);
+		udf_write_aext(table, &goal_epos, &goal_eloc,
+			       (goal_etype << 30) | goal_elen, 1);
 	else
 		udf_delete_aext(table, goal_epos, &freed);
 	brelse(goal_epos.bh);
-- 
2.55.0

[PATCH RESEND 2/3] udf: check the unallocated space table when it is loaded

[Matthias Goergens]

udf_table_new_block() hands out the first block of the extent closest
to its goal and trusts that the extent covers at least one whole block
inside the partition.  Nothing checks that.  A zero-length extent makes
it return the block the extent points at, which need not be free, and
the subtraction of one block then underflows the length into the type
bits, turning the entry into a bogus continuation.  An extent running
past the end of the partition makes it return blocks behind the
partition.

Such tables are not only found on crafted images: until the previous
commit, udf_table_new_block() itself left zero-length extents behind
in tables written by mkudffs, and then converted them into extents
running past the partition.

Check every extent once when the table is loaded, and refuse
read-write access if one is empty, is not a whole number of blocks, or
does not lie inside the partition, in the same way as for other
allocation information the kernel cannot use.  Check first that the
table is an Unallocated Space Entry at all: the walk starts at the
offset of the allocation descriptors in one, and for a file entry that
offset lies before the inode's in-memory copy of the descriptors.
Treat a chain of allocation extent descriptors that leads back to
itself the same way: the walk would otherwise return the same extents
forever, and the mount would never finish.  Let a fatal signal
interrupt the walk and fail the mount.

Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
Cc: stable@vger.kernel.org
Signed-off-by: Matthias Goergens <matthias.goergens@gmail.com>
---
 fs/udf/super.c | 80 +++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 79 insertions(+), 1 deletion(-)

diff --git a/fs/udf/super.c b/fs/udf/super.c
index 5351755aca3e..995969e6c7c5 100644
--- a/fs/udf/super.c
+++ b/fs/udf/super.c
@@ -1106,6 +1106,73 @@ static int check_partition_desc(struct super_block *sb,
 	return 0;
 }
 
+/*
+ * Check the Unallocated Space Table once when it is loaded: the allocator
+ * hands out blocks from the start of each extent and trusts that every
+ * extent covers at least one whole block inside the partition.
+ */
+static int udf_check_unalloc_table(struct super_block *sb,
+				   struct inode *table, u32 partition_len)
+{
+	struct extent_position epos = {
+		.block = UDF_I(table)->i_location,
+		.offset = sizeof(struct unallocSpaceEntry),
+	};
+	struct kernel_lb_addr eloc;
+	uint32_t elen, blocks;
+	struct kernel_lb_addr seen_block = {};
+	uint32_t seen_offset = 0;
+	u64 steps = 0, period = 1;
+	int8_t etype;
+	int ret;
+
+	/* The walk below assumes the layout of an Unallocated Space Entry */
+	if (!UDF_I(table)->i_use) {
+		udf_err(sb, "unallocated space table is not an unallocated space entry\n");
+		return -EFSCORRUPTED;
+	}
+
+	while ((ret = udf_next_aext(table, &epos, &eloc, &elen, &etype, 1)) > 0) {
+		blocks = elen >> sb->s_blocksize_bits;
+		if (!blocks || (elen & (sb->s_blocksize - 1)) ||
+		    eloc.logicalBlockNum >= partition_len ||
+		    blocks > partition_len - eloc.logicalBlockNum) {
+			udf_err(sb, "invalid unallocated space table extent (block %u, length %u)\n",
+				eloc.logicalBlockNum, elen);
+			ret = -EFSCORRUPTED;
+			break;
+		}
+		/*
+		 * A chain of allocation extents can lead back to itself, and
+		 * then the walk returns the same extents forever.  Remember a
+		 * position at doubling intervals (Brent's cycle detection);
+		 * a walk that comes back to it is in a loop.
+		 */
+		if (epos.block.logicalBlockNum == seen_block.logicalBlockNum &&
+		    epos.block.partitionReferenceNum ==
+				seen_block.partitionReferenceNum &&
+		    epos.offset == seen_offset) {
+			udf_err(sb, "unallocated space table loops back on itself\n");
+			ret = -EFSCORRUPTED;
+			break;
+		}
+		if (++steps == period) {
+			seen_block = epos.block;
+			seen_offset = epos.offset;
+			steps = 0;
+			period <<= 1;
+		}
+		if (fatal_signal_pending(current)) {
+			udf_err(sb, "interrupted while checking the unallocated space table\n");
+			ret = -EINTR;
+			break;
+		}
+		cond_resched();
+	}
+	brelse(epos.bh);
+	return ret;
+}
+
 static int udf_fill_partdesc_info(struct super_block *sb,
 		struct partitionDesc *p, int p_index)
 {
@@ -1166,6 +1233,16 @@ static int udf_fill_partdesc_info(struct super_block *sb,
 				  p_index);
 			return PTR_ERR(inode);
 		}
+		err = udf_check_unalloc_table(sb, inode, map->s_partition_len);
+		if (err) {
+			iput(inode);
+			if (err == -EINTR)
+				return err;
+			if (!sb_rdonly(sb))
+				return -EACCES;
+			UDF_SET_FLAG(sb, UDF_FLAG_RW_INCOMPAT);
+			return 0;
+		}
 		map->s_uspace.s_table = inode;
 		map->s_partition_flags |= UDF_PART_FLAG_UNALLOC_TABLE;
 		udf_debug("unallocSpaceTable (part %d) @ %llu\n",
@@ -2233,8 +2310,9 @@ static int udf_fill_super(struct super_block *sb, struct fs_context *fc)
 				/*
 				 * EACCES is special - we want to propagate to
 				 * upper layers that we cannot handle RW mount.
+				 * EINTR means that a fatal signal is pending.
 				 */
-				if (ret == -EACCES)
+				if (ret == -EACCES || ret == -EINTR)
 					break;
 			} else
 				break;
-- 
2.55.0

[PATCH RESEND 3/3] udf: leave udf_next_aext() outputs alone at the end of the extent list

[Matthias Goergens]

udf_next_aext() decodes each allocation descriptor straight into the
caller's eloc, elen and etype, and follows a continuation descriptor
into the next allocation extent.  If that allocation extent holds no
descriptors, it returns 0 for the end of the list, but by then eloc,
elen and etype describe the continuation descriptor itself: the block
of the empty allocation extent, one block long, type 3.

The kernel creates such lists itself: udf_delete_aext() leaves the last
allocation extent of a list empty when it removes its only descriptor,
and udf_do_extend_file() and udf_extend_file() already handle a list
that ends in an empty one.

Two callers use the outputs after a return of 0.  udf_discard_prealloc()
walks to the last extent and, if it is a preallocation, deletes it with
udf_delete_aext() and frees eloc/elen.  When an empty allocation extent
follows, udf_delete_aext() removes the continuation and frees the empty
block, and udf_discard_prealloc() then frees that block a second time
instead of the preallocated blocks.  On a space bitmap the preallocated
blocks are leaked and the free block count drifts.  On an unallocated
space table the second free adds a second free extent for the same
block, which is later handed out twice: fsx as run by generic/091 and
generic/263 ends up with two parts of its test file in one block and
reads back bad data.

udf_table_prealloc_blocks() can likewise take an empty allocation extent
at the end of the table's own list for a free extent starting at the
goal block.

Only update the outputs once a descriptor other than a continuation has
been found.  The other callers use the outputs only on a positive
return, or not at all, with one exception: when udf_table_free_blocks()
appends a new extent, it keeps the partition reference of whatever eloc
last held, which for a table whose list is a single continuation to an
empty allocation extent would now be uninitialised.  Take it from the
freed blocks instead.

Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
Cc: stable@vger.kernel.org
Signed-off-by: Matthias Goergens <matthias.goergens@gmail.com>
---
Reproducer, with fsx from fstests and mkudffs from udftools:

  truncate --size=2G udf.img
  mkudffs --blocksize=512 --space=unalloctable udf.img
  mount -t udf -o loop udf.img /mnt
  fsx -N 10000 -l 500000 -r 4096 -t 512 -w 512 -Z -R -W /mnt/junk

Without this patch fsx stops with READ BAD DATA after about 9850
operations, in every run; with it, all 10000 operations complete.
With --space=unallocbitmap fsx completes either way.

 fs/udf/balloc.c |  1 +
 fs/udf/inode.c  | 21 +++++++++++++++++----
 2 files changed, 18 insertions(+), 4 deletions(-)

diff --git a/fs/udf/balloc.c b/fs/udf/balloc.c
index 2ec577b4321c..d863ee201cbf 100644
--- a/fs/udf/balloc.c
+++ b/fs/udf/balloc.c
@@ -457,6 +457,7 @@ static void udf_table_free_blocks(struct super_block *sb,
 
 		int adsize;
 
+		eloc.partitionReferenceNum = bloc->partitionReferenceNum;
 		eloc.logicalBlockNum = start;
 		elen = EXT_RECORDED_ALLOCATED |
 			(count << sb->s_blocksize_bits);
diff --git a/fs/udf/inode.c b/fs/udf/inode.c
index 71386e7ac796..0e55f749bc48 100644
--- a/fs/udf/inode.c
+++ b/fs/udf/inode.c
@@ -2266,22 +2266,35 @@ void udf_write_aext(struct inode *inode, struct extent_position *epos,
 
 /*
  * Returns 1 on success, -errno on error, 0 on hit EOF.
+ *
+ * eloc, elen and etype are only updated when the next allocation descriptor
+ * was found.  In particular, when a chain of indirect extents ends in an
+ * empty one, following the trailing CONTINUE descriptor and hitting EOF must
+ * not clobber them with the location and length of that CONTINUE: callers
+ * keep using the last real extent's values after a 0 return, e.g. to discard
+ * its preallocation.
  */
 int udf_next_aext(struct inode *inode, struct extent_position *epos,
 		  struct kernel_lb_addr *eloc, uint32_t *elen, int8_t *etype,
 		  int inc)
 {
+	struct kernel_lb_addr tloc;
+	uint32_t tlen;
+	int8_t ttype;
 	unsigned int indirections = 0;
 	int ret = 0;
 	udf_pblk_t block;
 
 	while (1) {
-		ret = udf_current_aext(inode, epos, eloc, elen,
-				       etype, inc);
+		ret = udf_current_aext(inode, epos, &tloc, &tlen, &ttype, inc);
 		if (ret <= 0)
 			return ret;
-		if (*etype != (EXT_NEXT_EXTENT_ALLOCDESCS >> 30))
+		if (ttype != (EXT_NEXT_EXTENT_ALLOCDESCS >> 30)) {
+			*eloc = tloc;
+			*elen = tlen;
+			*etype = ttype;
 			return ret;
+		}
 
 		if (++indirections > UDF_MAX_INDIR_EXTS) {
 			udf_err(inode->i_sb,
@@ -2290,7 +2303,7 @@ int udf_next_aext(struct inode *inode, struct extent_position *epos,
 			return -EFSCORRUPTED;
 		}
 
-		epos->block = *eloc;
+		epos->block = tloc;
 		epos->offset = sizeof(struct allocExtDesc);
 		brelse(epos->bh);
 		block = udf_get_lb_pblock(inode->i_sb, &epos->block, 0);
-- 
2.55.0

Re: [PATCH RESEND 3/3] udf: leave udf_next_aext() outputs alone at the end of the extent list

[Jan Kara]

On Fri 02-10-26 12:26:27, Matthias Goergens wrote:
> udf_next_aext() decodes each allocation descriptor straight into the
> caller's eloc, elen and etype, and follows a continuation descriptor
> into the next allocation extent.  If that allocation extent holds no
> descriptors, it returns 0 for the end of the list, but by then eloc,
> elen and etype describe the continuation descriptor itself: the block
> of the empty allocation extent, one block long, type 3.
> 
> The kernel creates such lists itself: udf_delete_aext() leaves the last
> allocation extent of a list empty when it removes its only descriptor,
> and udf_do_extend_file() and udf_extend_file() already handle a list
> that ends in an empty one.
> 
> Two callers use the outputs after a return of 0.  udf_discard_prealloc()
> walks to the last extent and, if it is a preallocation, deletes it with
> udf_delete_aext() and frees eloc/elen.  When an empty allocation extent
> follows, udf_delete_aext() removes the continuation and frees the empty
> block, and udf_discard_prealloc() then frees that block a second time
> instead of the preallocated blocks.  On a space bitmap the preallocated
> blocks are leaked and the free block count drifts.  On an unallocated
> space table the second free adds a second free extent for the same
> block, which is later handed out twice: fsx as run by generic/091 and
> generic/263 ends up with two parts of its test file in one block and
> reads back bad data.
> 
> udf_table_prealloc_blocks() can likewise take an empty allocation extent
> at the end of the table's own list for a free extent starting at the
> goal block.
> 
> Only update the outputs once a descriptor other than a continuation has
> been found.  The other callers use the outputs only on a positive
> return, or not at all, with one exception: when udf_table_free_blocks()
> appends a new extent, it keeps the partition reference of whatever eloc
> last held, which for a table whose list is a single continuation to an
> empty allocation extent would now be uninitialised.  Take it from the
> freed blocks instead.
> 
> Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
> Cc: stable@vger.kernel.org
> Signed-off-by: Matthias Goergens <matthias.goergens@gmail.com>

Good catch! But I'd consider this mostly a bug in udf_discard_prealloc().
If udf_next_aext() returns value <= 0, you cannot assume anything about the
content of eloc & elen, including whether their value was or wasn't
clobbered. So IMO a nicer fix is to fix udf_discard_prealloc() to use
tmpeloc & tmpelen which should fix the problem as well.

								Honza

> ---
> Reproducer, with fsx from fstests and mkudffs from udftools:
> 
>   truncate --size=2G udf.img
>   mkudffs --blocksize=512 --space=unalloctable udf.img
>   mount -t udf -o loop udf.img /mnt
>   fsx -N 10000 -l 500000 -r 4096 -t 512 -w 512 -Z -R -W /mnt/junk
> 
> Without this patch fsx stops with READ BAD DATA after about 9850
> operations, in every run; with it, all 10000 operations complete.
> With --space=unallocbitmap fsx completes either way.
> 
>  fs/udf/balloc.c |  1 +
>  fs/udf/inode.c  | 21 +++++++++++++++++----
>  2 files changed, 18 insertions(+), 4 deletions(-)
> 
> diff --git a/fs/udf/balloc.c b/fs/udf/balloc.c
> index 2ec577b4321c..d863ee201cbf 100644
> --- a/fs/udf/balloc.c
> +++ b/fs/udf/balloc.c
> @@ -457,6 +457,7 @@ static void udf_table_free_blocks(struct super_block *sb,
>  
>  		int adsize;
>  
> +		eloc.partitionReferenceNum = bloc->partitionReferenceNum;
>  		eloc.logicalBlockNum = start;
>  		elen = EXT_RECORDED_ALLOCATED |
>  			(count << sb->s_blocksize_bits);
> diff --git a/fs/udf/inode.c b/fs/udf/inode.c
> index 71386e7ac796..0e55f749bc48 100644
> --- a/fs/udf/inode.c
> +++ b/fs/udf/inode.c
> @@ -2266,22 +2266,35 @@ void udf_write_aext(struct inode *inode, struct extent_position *epos,
>  
>  /*
>   * Returns 1 on success, -errno on error, 0 on hit EOF.
> + *
> + * eloc, elen and etype are only updated when the next allocation descriptor
> + * was found.  In particular, when a chain of indirect extents ends in an
> + * empty one, following the trailing CONTINUE descriptor and hitting EOF must
> + * not clobber them with the location and length of that CONTINUE: callers
> + * keep using the last real extent's values after a 0 return, e.g. to discard
> + * its preallocation.
>   */
>  int udf_next_aext(struct inode *inode, struct extent_position *epos,
>  		  struct kernel_lb_addr *eloc, uint32_t *elen, int8_t *etype,
>  		  int inc)
>  {
> +	struct kernel_lb_addr tloc;
> +	uint32_t tlen;
> +	int8_t ttype;
>  	unsigned int indirections = 0;
>  	int ret = 0;
>  	udf_pblk_t block;
>  
>  	while (1) {
> -		ret = udf_current_aext(inode, epos, eloc, elen,
> -				       etype, inc);
> +		ret = udf_current_aext(inode, epos, &tloc, &tlen, &ttype, inc);
>  		if (ret <= 0)
>  			return ret;
> -		if (*etype != (EXT_NEXT_EXTENT_ALLOCDESCS >> 30))
> +		if (ttype != (EXT_NEXT_EXTENT_ALLOCDESCS >> 30)) {
> +			*eloc = tloc;
> +			*elen = tlen;
> +			*etype = ttype;
>  			return ret;
> +		}
>  
>  		if (++indirections > UDF_MAX_INDIR_EXTS) {
>  			udf_err(inode->i_sb,
> @@ -2290,7 +2303,7 @@ int udf_next_aext(struct inode *inode, struct extent_position *epos,
>  			return -EFSCORRUPTED;
>  		}
>  
> -		epos->block = *eloc;
> +		epos->block = tloc;
>  		epos->offset = sizeof(struct allocExtDesc);
>  		brelse(epos->bh);
>  		block = udf_get_lb_pblock(inode->i_sb, &epos->block, 0);
> -- 
> 2.55.0
> 
-- 
Jan Kara <jack@suse.com>
SUSE Labs, CR