Skip to contentSkip to conversation

udf: Incorrect final NOT_ALLOCATED (hole) extent length

PATCH Superseded Steve Magnani 2 participants 8 messages Jun 4, 2019 – Jun 27, 2019 UDF filesystem

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

cover udf: Incorrect final NOT_ALLOCATED (hole) extent length

The following script reveals some errors in the final NOT_RECORDED_NOT_ALLOCATED extent of a file following use of truncate(1) to extend the file by adding or manipulating a hole at the end.

The script produces the following output:

Now testing NOT ALLOCATED extent.

 Testing    0 -->  300 : FAILED - bad extent type/length: expected 8000012C, actual 80000200
 Testing  300 -->  301 : PASSED
 Testing  301 -->  302 : FAILED - bad extent type/length: expected 8000012E, actual 8000012D
 Testing  302 -->  511 : FAILED - bad extent type/length: expected 800001FF, actual 8000012D
 Testing  511 -->  512 : FAILED - bad extent type/length: expected 80000200, actual 8000012D
 Testing  512 -->  513 : FAILED - bad extent type/length: expected 80000201, actual 80000400
 Testing  513 -->  514 : PASSED

Testing 514 --> 1023 : FAILED - bad extent type/length: expected 800003FF, actual 80000202 Testing 1023 --> 1024 : FAILED - bad extent type/length: expected 80000400, actual 80000202 Testing 1024 --> 1026 : FAILED - bad extent type/length: expected 80000402, actual 80000600 Testing 1026 --> 1538 : FAILED - bad extent type/length: expected 80000602, actual 80000800 Testing 1538 --> 4096 : PASSED
Testing 4096 --> 0 : PASSED
Testing 0 --> 4096 : PASSED
Testing 4096 --> 0 : PASSED
Testing 0 --> 4097 : FAILED - bad extent type/length: expected 80001001, actual 80001200
Testing 4097 --> 0 : PASSED

Now testing RECORDED extent.

 Testing  512 -->  512 : PASSED
 Testing  512 -->  511 : PASSED
 Testing  511 -->  300 : PASSED
 Testing  300 -->  512 : FAILED - bad extent type/length: expected 00000200, actual 0000012C

Now testing NOT ALLOCATED beyond RECORDED.

 Testing  512 -->  513 : FAILED - bad extent type/length: expected 00000200 80000001, actual 00000200 80000200
 Testing  513 -->  512 : PASSED
 Testing  512 -->  300 : PASSED
 Testing  300 -->  513 : FAILED - bad extent type/length: expected 00000200 80000001, actual 00000200 80000200
 Testing  513 -->  300 : PASSED
 Testing  300 --> 1538 : FAILED - bad extent type/length: expected 00000200 80000402, actual 00000200 80000600

Testing 1538 --> 0 : PASSED

Now testing multiple NOT ALLOCATED.
Testing 0 --> 1073741312 : PASSED
Testing 1073741312 --> 0 : PASSED
Testing 0 --> 1073741313 : FAILED - bad extent type/length: expected BFFFFE00 80000001, actual BFFFFE00 80000200
Testing 1073741313 --> 0 : PASSED
Testing 0 --> 1073741824 : PASSED

#!/bin/bash

FS_SIZE=256K
FS_FILE=/tmp/test.udf
MNT=/mnt
ICB_LSN=261
XXD=/usr/bin/xxd

truncate_test()

{
    local prev_size=`ls -l ${MNT}/truncate.test | cut -d' ' -f5`
    printf "Testing %4u --> %4u : " $prev_size $1 
    truncate --size=$1 ${MNT}/truncate.test
    sync
    local new_size=`ls -l ${MNT}/truncate.test | cut -d' ' -f5`

    if [ $new_size -ne $1 ] ; then
        echo FAILED - bad information length
    else
        local ext_type_and_len=`dd if=${FS_FILE} skip=${ICB_LSN} count=1 2> /dev/null | dd bs=1 skip=216 count=4 2> /dev/null | ${XXD} -g4 -e -u | cut -c11-18`
        if [ "$ext_type_and_len" = "$2" ] ; then
            if [ -z "$3" ] ; then
                echo PASSED
            else
                ext_type_and_len=`dd if=${FS_FILE} skip=${ICB_LSN} count=1 2> /dev/null | dd bs=1 skip=232 count=4 2> /dev/null | ${XXD} -g4 -e -u | cut -c11-18`
                if [ "$ext_type_and_len" = "$3" ] ; then
                    echo PASSED
                else
                    echo FAILED - bad extent type/length: expected $2 $3, actual $2 $ext_type_and_len
                fi
            fi
        else
            echo FAILED - bad extent type/length: expected $2, actual $ext_type_and_len
        fi
    fi
}

### MAIN

rm -f $FS_FILE

truncate --size=${FS_SIZE} $FS_FILE
mkudffs --label=TRUNCATE --media-type=hd --uid=1000 --gid=1000 $FS_FILE > /dev/null echo -n Mounting test filesystem...
sudo mount $FS_FILE $MNT -o loop
echo
touch ${MNT}/truncate.test

echo
echo Now testing NOT ALLOCATED extent.

truncate_test 300  8000012C
truncate_test 301  8000012D
truncate_test 302  8000012E
truncate_test 511  800001FF
truncate_test 512  80000200
truncate_test 513  80000201
truncate_test 514  80000202

truncate_test 1023 800003FF
truncate_test 1024 80000400
truncate_test 1026 80000402
truncate_test 1538 80000602
truncate_test 4096 80001000
truncate_test 0 00000000
truncate_test 4096 80001000
truncate_test 0 00000000
truncate_test 4097 80001001
truncate_test 0 00000000

dd if=/dev/zero of=${MNT}/truncate.test bs=512 count=1 2> /dev/null echo
echo Now testing RECORDED extent.

truncate_test 512  00000200
truncate_test 511  000001FF
truncate_test 300  0000012C
truncate_test 512  00000200
echo
echo Now testing NOT ALLOCATED beyond RECORDED.
truncate_test 513  00000200 80000001
truncate_test 512  00000200 00000000
truncate_test 300  0000012C
truncate_test 513  00000200 80000001
truncate_test 300  0000012C 00000000

truncate_test 1538 00000200 80000402
truncate_test 0 00000000

echo
echo Now testing multiple NOT ALLOCATED.
truncate_test 1073741312 BFFFFE00
truncate_test 0 00000000
truncate_test 1073741313 BFFFFE00 80000001
truncate_test 0 00000000
truncate_test 1073741824 BFFFFE00 80000200

sudo umount $FS_FILE

------------------------------------------------------------------------
Steven J. Magnani "I claim this network for MARS!
www.digidescorp.com Earthling, return my space modulator!"

#include <standard.disclaimer>

#1 lore raw

PATCH 1/1 udf: Fix incorrect final NOT_ALLOCATED (hole) extent length

In some cases, using the 'truncate' command to extend a UDF file results in a mismatch between the length of the file's extents (specifically, due to incorrect length of the final NOT_ALLOCATED extent) and the information (file) length. The discrepancy can prevent other operating systems (i.e., Windows 10) from opening the file.

Two particular errors have been observed when extending a file:

1. The final extent is larger than it should be, having been rounded up to a multiple of the block size.

B. The final extent is not shorter than it should be, due to not having
been updated when the file's information length was increased.

The first case could represent a design error, if coded intentionally due to a misinterpretation of scantily-documented ECMA-167 "file tail" rules. The standard specifies that the tail, if present, consists of a sequence of "unrecorded and allocated" extents (only).

fs/udf/inode.c +24 -11
@@ -474,7 +474,8 @@ static struct buffer_head *udf_getblk(st
 static int udf_do_extend_file(struct inode *inode,
 			      struct extent_position *last_pos,
 			      struct kernel_long_ad *last_ext,
-			      sector_t blocks)
+			      sector_t blocks,
+			      unsigned long partial_final_block)
 {
 	sector_t add;
 	int count = 0, fake = !(last_ext->extLength & UDF_EXTENT_LENGTH_MASK);
@@ -486,7 +487,7 @@ static int udf_do_extend_file(struct ino
 
 	/* The previous extent is fake and we should not extend by anything
 	 * - there's nothing to do... */
-	if (!blocks && fake)
+	if (!blocks && !partial_final_block && fake)
 		return 0;
 
 	iinfo = UDF_I(inode);
@@ -524,6 +525,10 @@ static int udf_do_extend_file(struct ino
 			add = blocks;
 		blocks -= add;
 		last_ext->extLength += add << sb->s_blocksize_bits;
+		if (blocks == 0 && partial_final_block) {
+			last_ext->extLength -= sb->s_blocksize
+				- partial_final_block;
+		}
 	}
 
 	if (fake) {
@@ -566,6 +571,10 @@ static int udf_do_extend_file(struct ino
 	if (blocks) {
 		last_ext->extLength = EXT_NOT_RECORDED_NOT_ALLOCATED |
 			(blocks << sb->s_blocksize_bits);
+		if (partial_final_block) {
+			last_ext->extLength -= sb->s_blocksize
+					- partial_final_block;
+		}
 		err = udf_add_aext(inode, last_pos, &last_ext->extLocation,
 				   last_ext->extLength, 1);
 		if (err)
@@ -605,6 +614,7 @@ static int udf_extend_file(struct inode
 	int8_t etype;
 	struct super_block *sb = inode->i_sb;
 	sector_t first_block = newsize >> sb->s_blocksize_bits, offset;
+	unsigned long partial_final_block;
 	int adsize;
 	struct udf_inode_info *iinfo = UDF_I(inode);
 	struct kernel_long_ad extent;
@@ -619,15 +629,17 @@ static int udf_extend_file(struct inode
 
 	etype = inode_bmap(inode, first_block, &epos, &eloc, &elen, &offset);
 
+	partial_final_block = newsize & (sb->s_blocksize - 1);
+
 	/* File has extent covering the new size (could happen when extending
 	 * inside a block)? */
-	if (etype != -1)
-		return 0;
-	if (newsize & (sb->s_blocksize - 1))
-		offset++;
-	/* Extended file just to the boundary of the last file block? */
-	if (offset == 0)
-		return 0;
+	if (etype == -1) {
+		if (partial_final_block)
+			offset++;
+	} else {
+		/* Extending file within the last file block */
+		offset = 0;  /* Don't add any new blocks */
+	}
 
 	/* Truncate is extending the file by 'offset' blocks */
 	if ((!epos.bh && epos.offset == udf_file_entry_alloc_offset(inode)) ||
@@ -643,7 +655,8 @@ static int udf_extend_file(struct inode
 				      &extent.extLength, 0);
 		extent.extLength |= etype << 30;
 	}
-	err = udf_do_extend_file(inode, &epos, &extent, offset);
+	err = udf_do_extend_file(inode, &epos, &extent, offset,
+				 partial_final_block);
 	if (err < 0)
 		goto out;
 	err = 0;
@@ -760,7 +773,7 @@ static sector_t inode_getblk(struct inod
 			startnum = (offset > 0);
 		}
 		/* Create extents for the hole between EOF and offset */
-		ret = udf_do_extend_file(inode, &prev_epos, laarr, offset);
+		ret = udf_do_extend_file(inode, &prev_epos, laarr, offset, 0);
 		if (ret < 0) {
 			*err = ret;
 			newblock = 0;
#2 lore raw

Re: [PATCH 1/1] udf: Fix incorrect final NOT_ALLOCATED (hole) extent length

Quoted 1 line · Steve Magnani

B. The final extent is not shorter than it should be, due to not having

Oops: should have been

B. The final extent is shorter than it should be, due to not having

#3 lore raw

Re: [PATCH 1/1] udf: Fix incorrect final NOT_ALLOCATED (hole) extent length

In reply to Steve Magnani

Hi Jan,

Quoted 6 lines · Steve Magnani

In some cases, using the 'truncate' command to extend a UDF file results in a mismatch between the length of the file's extents (specifically, due to incorrect length of the final NOT_ALLOCATED extent) and the information (file) length. The discrepancy can prevent other operating systems (i.e., Windows 10) from opening the file.

Quoted 7 lines

Two particular errors have been observed when extending a file:

1. The final extent is larger than it should be, having been rounded up to a multiple of the block size.

B. The final extent is shorter than it should be, due to not having
been updated when the file's information length was increased.

Wondering if you've seen this, or if something got lost in a spam folder.

Regards,

------------------------------------------------------------------------
Steven J. Magnani "I claim this network for MARS!
www.digidescorp.com Earthling, return my space modulator!"

#include <standard.disclaimer>

#4 lore raw

Re: [PATCH 1/1] udf: Fix incorrect final NOT_ALLOCATED (hole) extent length

Hi Steve!

Quoted 10 lines · Steve Magnani
Quoted 8 lines · Steve Magnani

In some cases, using the 'truncate' command to extend a UDF file results in a mismatch between the length of the file's extents (specifically, due to incorrect length of the final NOT_ALLOCATED extent) and the information (file) length. The discrepancy can prevent other operating systems (i.e., Windows 10) from opening the file.

Two particular errors have been observed when extending a file:

Quoted 7 lines
Quoted 5 lines

1. The final extent is larger than it should be, having been rounded up to a multiple of the block size.

B. The final extent is shorter than it should be, due to not having
been updated when the file's information length was increased.

Wondering if you've seen this, or if something got lost in a spam folder.

Sorry for not getting to you earlier. I've seen the patches and they look reasonable to me. I just wanted to have a one more closer look but last weeks were rather busy so I didn't get to it. I'll look into it this week. Thanks a lot for debugging the problem and sending the fixes!

Honza

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR
#5 lore raw

Re: [PATCH 1/1] udf: Fix incorrect final NOT_ALLOCATED (hole) extent length

Quoted 18 lines · Jan Kara

Hi Steve!

Quoted 15 lines · Steve Magnani
Quoted 13 lines · Steve Magnani

In some cases, using the 'truncate' command to extend a UDF file results in a mismatch between the length of the file's extents (specifically, due to incorrect length of the final NOT_ALLOCATED extent) and the information (file) length. The discrepancy can prevent other operating systems (i.e., Windows 10) from opening the file.

Two particular errors have been observed when extending a file:

1. The final extent is larger than it should be, having been rounded up to a multiple of the block size.

B. The final extent is shorter than it should be, due to not having
been updated when the file's information length was increased.

Quoted 7 lines
Quoted 1 line

Wondering if you've seen this, or if something got lost in a spam folder.

Sorry for not getting to you earlier. I've seen the patches and they look reasonable to me. I just wanted to have a one more closer look but last weeks were rather busy so I didn't get to it. I'll look into it this week. Thanks a lot for debugging the problem and sending the fixes!

Honza

No worries. If you're short on time I'd suggest looking first at the ways udf_do_extend_file() can be called via inode_getblk(). Those were harder for me to follow so if there is a bug it's most likely in one of those paths.

Regards,
------------------------------------------------------------------------
Steven J. Magnani "I claim this network for MARS!
www.digidescorp.com Earthling, return my space modulator!"

#include <standard.disclaimer>

#6 lore raw

Re: [PATCH 1/1] udf: Fix incorrect final NOT_ALLOCATED (hole) extent length

In reply to Steve Magnani
Quoted 14 lines · Steve Magnani

In some cases, using the 'truncate' command to extend a UDF file results in a mismatch between the length of the file's extents (specifically, due to incorrect length of the final NOT_ALLOCATED extent) and the information (file) length. The discrepancy can prevent other operating systems (i.e., Windows 10) from opening the file.

Two particular errors have been observed when extending a file:

1. The final extent is larger than it should be, having been rounded up to a multiple of the block size.

B. The final extent is not shorter than it should be, due to not having
been updated when the file's information length was increased.

Quoted 6 lines

The first case could represent a design error, if coded intentionally due to a misinterpretation of scantily-documented ECMA-167 "file tail" rules. The standard specifies that the tail, if present, consists of a sequence of "unrecorded and allocated" extents (only).

Thanks for the testcase and the patch! I finally got to reading through this in detail. In udf driver in Linux we are generally fine with the last extent being rounded up to the block size. udf_truncate_tail_extent() is generally responsible for truncating the last extent to appropriate size once we are done with the inode. However there are two problems with this:

1) We used to do this inside udf_clear_inode() back in the old days but then switched to a different scheme in commit 2c948b3f86e5f "udf: Avoid IO in udf_clear_inode". So this actually breaks workloads where user calls truncate(2) directly and there's no place where udf_truncate_tail_extent() gets called.

2) udf_extend_file() sets i_lenExtents == i_size although the last extent isn't properly rounded so even if udf_truncate_tail_extent() gets called (which is actually the case for truncate(1) which does open, ftruncate, close), it will think it has nothing to do and exit.

Now 2) is easily fixed by setting i_lenExtents to real length of extents we have created. However that still leaves problem 1) which isn't easy to deal with. After some though I think that your solution of making udf_do_extend_file() always create appropriately sized extents makes sense. However I dislike the calling convention you've chosen. When udf_do_extend_file() needs to now byte length, then why not pass it to it directly, instead of somewhat cumbersome "sector length + byte offset" pair?

Will you update the patch please? Thanks!

Honza

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR
#7 lore raw

Re: [PATCH 1/1] udf: Fix incorrect final NOT_ALLOCATED (hole) extent length

Hi Jan,

Quoted 47 lines · Jan Kara
Quoted 14 lines · Steve Magnani

In some cases, using the 'truncate' command to extend a UDF file results in a mismatch between the length of the file's extents (specifically, due to incorrect length of the final NOT_ALLOCATED extent) and the information (file) length. The discrepancy can prevent other operating systems (i.e., Windows 10) from opening the file.

Two particular errors have been observed when extending a file:

1. The final extent is larger than it should be, having been rounded up to a multiple of the block size.

B. The final extent is not shorter than it should be, due to not having
been updated when the file's information length was increased.

Quoted 6 lines

The first case could represent a design error, if coded intentionally due to a misinterpretation of scantily-documented ECMA-167 "file tail" rules. The standard specifies that the tail, if present, consists of a sequence of "unrecorded and allocated" extents (only).

Thanks for the testcase and the patch! I finally got to reading through this in detail. In udf driver in Linux we are generally fine with the last extent being rounded up to the block size. udf_truncate_tail_extent() is generally responsible for truncating the last extent to appropriate size once we are done with the inode. However there are two problems with this:

1) We used to do this inside udf_clear_inode() back in the old days but then switched to a different scheme in commit 2c948b3f86e5f "udf: Avoid IO in udf_clear_inode". So this actually breaks workloads where user calls truncate(2) directly and there's no place where udf_truncate_tail_extent() gets called.

2) udf_extend_file() sets i_lenExtents == i_size although the last extent isn't properly rounded so even if udf_truncate_tail_extent() gets called (which is actually the case for truncate(1) which does open, ftruncate, close), it will think it has nothing to do and exit.

Now 2) is easily fixed by setting i_lenExtents to real length of extents we have created. However that still leaves problem 1) which isn't easy to deal with. After some though I think that your solution of making udf_do_extend_file() always create appropriately sized extents makes sense. However I dislike the calling convention you've chosen. When udf_do_extend_file() needs to now byte length, then why not pass it to it directly, instead of somewhat cumbersome "sector length + byte offset" pair?

Quoted 1 line

Will you update the patch please? Thanks!

That sounds reasonable, but at first glance I think it might be more confusing. The API as I reworked it now communicates two different (although related) things - the number of blocks that need to be added, and the number of bytes within the last block that are part of the file. This is able to cover both the corner case of extending within the last file block and extending beyond that:

   	partial_final_block = newsize & (sb->s_blocksize - 1);

/* File has extent covering the new size (could happen when extending
* inside a block)? */
if (etype == -1) {
if (partial_final_block)
offset++;
} else {
/* Extending file within the last file block */ offset = 0; /* Don't add any new blocks */
}

If it were as simple as passing to udf_do_extend_file() a loff_t specifying the number of bytes to add, including both full blocks and a final partial block, I would agree with you. But this isn't enough information for udf_do_extend_file() to know whether the final partial block requires a new block or not.

I will think about it some more. Maybe moving the 'extending within the last file block' case out to udf_extend_file() would help.

Steve