[RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[sho]

Hi Johann, Andreas

On Jun 05, 2006  15:13 +0200, Johann Lombardi wrote:
> On Fri, May 26, 2006 at 06:00:32AM -0600, Andreas Dilger wrote:
> > On May 25, 2006  21:49 +0900, sho@tnes.nec.co.jp wrote:
> > > @@ -1463,11 +1463,17 @@ static int ext3_fill_super (struct super
> > > +	if (blocksize > PAGE_SIZE) {
> > > +		printk(KERN_ERR "EXT3-fs: cannot mount filesystem with "
> > > +		       "blocksize %u larger than PAGE_SIZE %u on %s\n",
> > > +		       blocksize, PAGE_SIZE, sb->s_id);
> > > +		goto failed_mount;
> > > +	}
> > > +
> > >  	if (blocksize < EXT3_MIN_BLOCK_SIZE ||
> > > -	    blocksize > EXT3_MAX_BLOCK_SIZE) {
> > > +	    blocksize > EXT3_EXTENDED_MAX_BLOCK_SIZE) {
> >
> > We may as well just change EXT3_MAX_BLOCK_SIZE to be 65536, because no other
> > code uses this value.  It is already 65536 in the e2fsprogs.
> 
> AFAICS, ext3_dir_entry_2->rec_len will overflow with a 64kB blocksize.
Agree.


ext2/ext3_dir_entry_2 has a 16-bit entry(rec_len) and it would overflow
with 64KB blocksize.  This patch prevent from overflow by limiting
rec_len to 65532.

This patch applies on top of Mingming's patches which were posted at:
  http://marc.theaimsgroup.com/?l=ext2-devel&m=114981607414944&w=2

I couldn't test with this patch because OS wouldn't boot with or
without it when CONFIG_IA64_PAGE_SIZE_64KB was enabled.

Patch-set consists of the following 2 patches.

  [1/2]  ext3: enlarge blocksize and fix rec_len overflow
          - Allow blocksize up to 64KB.
          - prevent rec_len from overflow with 64KB blocksize

  [2/2]  ext2: fix rec_len overflow
          - prevent rec_len from overflow with 64KB blocksize


Signed-off-by: Takashi Sato sho@tnes.nec.co.jp
---
diff -upNr -X linux-2.6.17-rc6/Documentation/dontdiff linux-2.6.17-rc6/fs/ext3/namei.c linux-2.6.17-rc6.tmp/fs/ext3/namei.c
--- linux-2.6.17-rc6/fs/ext3/namei.c	2006-06-27 09:05:11.000000000 +0900
+++ linux-2.6.17-rc6.tmp/fs/ext3/namei.c	2006-06-27 09:07:15.000000000 +0900
@@ -1154,8 +1154,13 @@ static struct ext3_dir_entry_2 *do_split
 	/* Fancy dance to stay within two buffers */
 	de2 = dx_move_dirents(data1, data2, map + split, count - split);
 	de = dx_pack_dirents(data1,blocksize);
-	de->rec_len = cpu_to_le16(data1 + blocksize - (char *) de);
-	de2->rec_len = cpu_to_le16(data2 + blocksize - (char *) de2);
+	if (blocksize < EXT3_RECLEN_MAX) {
+		de->rec_len = cpu_to_le16(data1 + blocksize - (char *) de);
+		de2->rec_len = cpu_to_le16(data2 + blocksize - (char *) de2);
+	} else {
+		de->rec_len = cpu_to_le16(data1 + EXT3_RECLEN_MAX - (char *) de);
+		de2->rec_len = cpu_to_le16(data2 + EXT3_RECLEN_MAX - (char *) de2);
+	}
 	dxtrace(dx_show_leaf (hinfo, (struct ext3_dir_entry_2 *) data1, blocksize, 1));
 	dxtrace(dx_show_leaf (hinfo, (struct ext3_dir_entry_2 *) data2, blocksize, 1));
 
@@ -1206,7 +1211,10 @@ static int add_dirent_to_buf(handle_t *h
 	reclen = EXT3_DIR_REC_LEN(namelen);
 	if (!de) {
 		de = (struct ext3_dir_entry_2 *)bh->b_data;
-		top = bh->b_data + dir->i_sb->s_blocksize - reclen;
+		if (dir->i_sb->s_blocksize < EXT3_RECLEN_MAX)
+			top = bh->b_data + dir->i_sb->s_blocksize - reclen;
+		else
+			top = bh->b_data + EXT3_RECLEN_MAX - reclen;
 		while ((char *) de <= top) {
 			if (!ext3_check_dir_entry("ext3_add_entry", dir, de,
 						  bh, offset)) {
@@ -1417,7 +1425,10 @@ static int ext3_add_entry (handle_t *han
 		return retval;
 	de = (struct ext3_dir_entry_2 *) bh->b_data;
 	de->inode = 0;
-	de->rec_len = cpu_to_le16(rlen = blocksize);
+	if (blocksize < EXT3_RECLEN_MAX)
+		de->rec_len = cpu_to_le16(rlen = blocksize);
+	else
+		de->rec_len = cpu_to_le16(rlen = EXT3_RECLEN_MAX);
 	nlen = 0;
 	return add_dirent_to_buf(handle, dentry, inode, de, bh);
 }
@@ -1482,7 +1493,10 @@ static int ext3_dx_add_entry(handle_t *h
 			goto cleanup;
 		node2 = (struct dx_node *)(bh2->b_data);
 		entries2 = node2->entries;
-		node2->fake.rec_len = cpu_to_le16(sb->s_blocksize);
+		if (sb->s_blocksize < EXT3_RECLEN_MAX)
+			node2->fake.rec_len = cpu_to_le16(sb->s_blocksize);
+		else
+			node2->fake.rec_len = cpu_to_le16(EXT3_RECLEN_MAX);
 		node2->fake.inode = 0;
 		BUFFER_TRACE(frame->bh, "get_write_access");
 		err = ext3_journal_get_write_access(handle, frame->bh);
diff -upNr -X linux-2.6.17-rc6/Documentation/dontdiff linux-2.6.17-rc6/include/linux/ext3_fs.h linux-2.6.17-rc6.tmp/include/linux/ext3_fs.h
--- linux-2.6.17-rc6/include/linux/ext3_fs.h	2006-06-27 09:05:15.000000000 +0900
+++ linux-2.6.17-rc6.tmp/include/linux/ext3_fs.h	2006-06-27 08:51:08.000000000 +0900
@@ -82,11 +82,16 @@ struct statfs;
 #define EXT3_LINK_MAX		32000
 
 /*
+ * Maximal size of directory entry record length
+ */
+#define EXT3_RECLEN_MAX                 65532
+
+/*
  * Macro-instructions used to manage several block sizes
  */
 #define EXT3_MIN_BLOCK_SIZE		1024
-#define	EXT3_MAX_BLOCK_SIZE		4096
-#define EXT3_MIN_BLOCK_LOG_SIZE		  10
+#define	EXT3_MAX_BLOCK_SIZE		65536
+#define EXT3_MIN_BLOCK_LOG_SIZE		10
 #ifdef __KERNEL__
 # define EXT3_BLOCK_SIZE(s)		((s)->s_blocksize)
 #else


Cheers, sho

Re: [RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[Johann Lombardi]

Hi Takashi,

> ext2/ext3_dir_entry_2 has a 16-bit entry(rec_len) and it would overflow
> with 64KB blocksize.  This patch prevent from overflow by limiting
> rec_len to 65532.

In empty_dir(), offset is incremented by de->rec_len until it reaches
inode->i_size. I think bad things will happen with a 64kB blocksize since
the records no longer span the entire directory block.

AFAICS, there's a similar issue with bh->b_size in ext3_delete_entry().

Cheers,

Johann

Re: [RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[Andreas Dilger]

On Jun 28, 2006  17:50 +0200, Johann Lombardi wrote:
> ext2/ext3_dir_entry_2 has a 16-bit entry(rec_len) and it would overflow
> with 64KB blocksize.  This patch prevent from overflow by limiting
> rec_len to 65532.

Having a max rec_len of 65532 is rather unfortunate, since the dir
blocks always need to filled with dir entries.  65536 - 65532 = 4, and
the minimum ext3_dir_entry size is 8 bytes.  I would instead make this
maybe 64 bytes less so that there is room for a filename in the "tail"
dir_entry.


Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.

Re: [Ext2-devel] [RFC 1/2] ext3: enlarge blocksize and fix rec_lenoverflow

[Takashi Sato]

Hi,

> On Jun 28, 2006  17:50 +0200, Johann Lombardi wrote:
>> ext2/ext3_dir_entry_2 has a 16-bit entry(rec_len) and it would overflow
>> with 64KB blocksize.  This patch prevent from overflow by limiting
>> rec_len to 65532.
> 
> Having a max rec_len of 65532 is rather unfortunate, since the dir
> blocks always need to filled with dir entries.

Oh, that's right.

> 65536 - 65532 = 4, and
> the minimum ext3_dir_entry size is 8 bytes.  I would instead make this
> maybe 64 bytes less so that there is room for a filename in the "tail"
> dir_entry.

What does "64 bytes" mean?
Do you mean that the following dummy entry should be added
at the tail of the directory block?

struct ext3_dir_entry_2 {
 __le32 inode   = 0
 __le16 rec_len = 16
 __u8 name_len  = 4
 __u8 file_type = 0
 char name      = "dir_end"
};

Cheers, sho 

Re: [Ext2-devel] [RFC 1/2] ext3: enlarge blocksize and fix rec_lenoverflow

[Andreas Dilger]

On Jun 29, 2006  19:46 +0900, Takashi Sato wrote:
> >On Jun 28, 2006  17:50 +0200, Johann Lombardi wrote:
> >>ext2/ext3_dir_entry_2 has a 16-bit entry(rec_len) and it would overflow
> >>with 64KB blocksize.  This patch prevent from overflow by limiting
> >>rec_len to 65532.
> >
> >Having a max rec_len of 65532 is rather unfortunate, since the dir
> >blocks always need to filled with dir entries.
> 
> Oh, that's right.
> 
> >65536 - 65532 = 4, and
> >the minimum ext3_dir_entry size is 8 bytes.  I would instead make this
> >maybe 64 bytes less so that there is room for a filename in the "tail"
> >dir_entry.
> 
> What does "64 bytes" mean?
> Do you mean that the following dummy entry should be added
> at the tail of the directory block?
> 
> struct ext3_dir_entry_2 {
> __le32 inode   = 0
> __le16 rec_len = 16
> __u8 name_len  = 4
> __u8 file_type = 0
> char name      = "dir_end"
> };

Sure, something like this.  The goal of this dir entry is to:
a) fill up the remaining space in the dir block
b) be large enough to be used later on when the start of the block has
   been consumed, so it shouldn't be too small.  It could even be as
   large as 4kB or 8kB or 32kB.

Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.

Re: [RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[Daniel Phillips]

Hi Andreas,

Andreas Dilger wrote:
> On Jun 28, 2006  17:50 +0200, Johann Lombardi wrote:
>>ext2/ext3_dir_entry_2 has a 16-bit entry(rec_len) and it would overflow
>>with 64KB blocksize.  This patch prevent from overflow by limiting
>>rec_len to 65532.
> 
> Having a max rec_len of 65532 is rather unfortunate, since the dir
> blocks always need to filled with dir entries.  65536 - 65532 = 4, and
> the minimum ext3_dir_entry size is 8 bytes.  I would instead make this
> maybe 64 bytes less so that there is room for a filename in the "tail"
> dir_entry.

Then why not introduce a little symmetry by making max rec_len 2**15 and
treat big directory blocks as an array of smaller ones?  I dimly recall
the page-cache oriented Ext2 dir code already does this.

Regards,

Daniel

Re: [RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[Andreas Dilger]

On Jun 29, 2006  11:10 -0700, Daniel Phillips wrote:
> Andreas Dilger wrote:
> >On Jun 28, 2006  17:50 +0200, Johann Lombardi wrote:
> >>ext2/ext3_dir_entry_2 has a 16-bit entry(rec_len) and it would overflow
> >>with 64KB blocksize.  This patch prevent from overflow by limiting
> >>rec_len to 65532.
> >
> >Having a max rec_len of 65532 is rather unfortunate, since the dir
> >blocks always need to filled with dir entries.  65536 - 65532 = 4, and
> >the minimum ext3_dir_entry size is 8 bytes.  I would instead make this
> >maybe 64 bytes less so that there is room for a filename in the "tail"
> >dir_entry.
> 
> Then why not introduce a little symmetry by making max rec_len 2**15 and
> treat big directory blocks as an array of smaller ones?  I dimly recall
> the page-cache oriented Ext2 dir code already does this.

I have no objection to this at all, but I think it will lead to a slightly
more complex implementation.  We even discussed in the distant past to
make large directories a series of 4kB "chunks", for fs blocksize >= 4kB.
This has negative implications for large filenames because the internal
free space fragmentation is high, but has the advantage that it might
eventually still be usable if we can get blocksize > PAGE_SIZE.

The difficulty is that when freeing dir entires you would have to be
concerned with a merging a dir_entry that is spanning the middle
of a 2^16 block.

Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.

Re: [RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[Daniel Phillips]

Andreas Dilger wrote:
> On Jun 29, 2006  11:10 -0700, Daniel Phillips wrote:
>>Andreas Dilger wrote:
>>>On Jun 28, 2006  17:50 +0200, Johann Lombardi wrote:
>>>
>>>>ext2/ext3_dir_entry_2 has a 16-bit entry(rec_len) and it would overflow
>>>>with 64KB blocksize.  This patch prevent from overflow by limiting
>>>>rec_len to 65532.
>>>
>>>Having a max rec_len of 65532 is rather unfortunate, since the dir
>>>blocks always need to filled with dir entries.  65536 - 65532 = 4, and
>>>the minimum ext3_dir_entry size is 8 bytes.  I would instead make this
>>>maybe 64 bytes less so that there is room for a filename in the "tail"
>>>dir_entry.
>>
>>Then why not introduce a little symmetry by making max rec_len 2**15 and
>>treat big directory blocks as an array of smaller ones?  I dimly recall
>>the page-cache oriented Ext2 dir code already does this.
> 
> I have no objection to this at all, but I think it will lead to a slightly
> more complex implementation.  We even discussed in the distant past to
> make large directories a series of 4kB "chunks", for fs blocksize >= 4kB.
> This has negative implications for large filenames because the internal
> free space fragmentation is high, but has the advantage that it might
> eventually still be usable if we can get blocksize > PAGE_SIZE.
> 
> The difficulty is that when freeing dir entires you would have to be
> concerned with a merging a dir_entry that is spanning the middle
> of a 2^16 block.

That is easy, just don't let an entry span subblocks by not letting
delete merge past the end of a subblock, just a minor tweak.  New block
initialization needs an outer loop on subblocks and that's it, I think.

Regards,

Daniel

Re: [RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[Johann Lombardi]

Hi,

> >I have no objection to this at all, but I think it will lead to a slightly
> >more complex implementation.  We even discussed in the distant past to
> >make large directories a series of 4kB "chunks", for fs blocksize >= 4kB.
> >This has negative implications for large filenames because the internal
> >free space fragmentation is high, but has the advantage that it might
> >eventually still be usable if we can get blocksize > PAGE_SIZE.
> >
> >The difficulty is that when freeing dir entires you would have to be
> >concerned with a merging a dir_entry that is spanning the middle
> >of a 2^16 block.
> 
> That is easy, just don't let an entry span subblocks by not letting
> delete merge past the end of a subblock, just a minor tweak.  New block
> initialization needs an outer loop on subblocks and that's it, I think.

I've been working on a patch implementing this feature. It currently works w/o 
htree.
With dir_index, the difficulty is that an entry can span subblocks after a leaf
block split.

Cheers,

Johann

Re: [RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[Daniel Phillips]

Johann Lombardi wrote:
>>>I have no objection to this at all, but I think it will lead to a slightly
>>>more complex implementation.  We even discussed in the distant past to
>>>make large directories a series of 4kB "chunks", for fs blocksize >= 4kB.
>>>This has negative implications for large filenames because the internal
>>>free space fragmentation is high, but has the advantage that it might
>>>eventually still be usable if we can get blocksize > PAGE_SIZE.
>>>
>>>The difficulty is that when freeing dir entires you would have to be
>>>concerned with a merging a dir_entry that is spanning the middle
>>>of a 2^16 block.
>>
>>That is easy, just don't let an entry span subblocks by not letting
>>delete merge past the end of a subblock, just a minor tweak.  New block
>>initialization needs an outer loop on subblocks and that's it, I think.
> 
> 
> I've been working on a patch implementing this feature. It currently works w/o 
> htree.
> With dir_index, the difficulty is that an entry can span subblocks after a leaf
> block split.

Argh, hoist by my own petard!  That is not the only problem - we also need
to represent 64K empty records for the index blocks.  These issues need to
be dealt with in order to go past 64K blocks, and then we have so many
entries per block we probably want to rethink the leaf format anyway.  OK,
just to handle the 64K case, what is wrong with treating 0 as 64K?

Regards,

Daniel

Re: [RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[Andreas Dilger]

On Jun 30, 2006  11:19 -0700, Daniel Phillips wrote:
> OK, just to handle the 64K case, what is wrong with treating 0 as 64K?

Hmm, good question - it's impossible to have a valid rec_len of 0 bytes.
There would need to be some special casing in the directory handling code.
Also, it breaks some of the directory sanity checking, and since "0" is
a common corruption pattern it isn't great to use.  We could instead use
0xfffc to mean 0x10000 since they are virtually the same value and the
error checking is safe.  It isn't possible to have this as a valid value.

Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.

Re: [RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[Michael Tokarev]

Andreas Dilger wrote:
> On Jun 30, 2006  11:19 -0700, Daniel Phillips wrote:
>> OK, just to handle the 64K case, what is wrong with treating 0 as 64K?
> 
> Hmm, good question - it's impossible to have a valid rec_len of 0 bytes.
> There would need to be some special casing in the directory handling code.
> Also, it breaks some of the directory sanity checking, and since "0" is
> a common corruption pattern it isn't great to use.  We could instead use
> 0xfffc to mean 0x10000 since they are virtually the same value and the
> error checking is safe.  It isn't possible to have this as a valid value.

I understand the wishes to extend the filesystem capabilities which are
now becoming limited. I understand sometimes it's relatively easy to
"extend the width" of some on-disk fields this way.

But.

Isn't this sort of kludges (in a normally numeric field of a limited width,
introduce special normally-impossible values to mean different values) are
the ways to complicate things (code) and confuse various tools and people
for too much, making the whole thing just broken by design?

A line should be drawn somewhere.  When, after breaking (and thus "fixing")
some currently present limit, we change internal semantics in an ugly way,
maybe it's really better to change original design and introduce new,
somehow incompatible filesystem instead?

Please excuse me if this my comment is entirely beyong the point, because,
well.. to be fair, I don't quite understand what's the whole talk about,
I'm just reading the above (quoted) email out of context... ;)

/mjt

Re: [RFC 1/2] ext3: enlarge blocksize and fix rec_len overflow

[Daniel Phillips]

Andreas Dilger wrote:
> On Jun 30, 2006  11:19 -0700, Daniel Phillips wrote:
>>OK, just to handle the 64K case, what is wrong with treating 0 as 64K?
> 
> Hmm, good question - it's impossible to have a valid rec_len of 0 bytes.
> There would need to be some special casing in the directory handling code.
> Also, it breaks some of the directory sanity checking, and since "0" is
> a common corruption pattern it isn't great to use.  We could instead use
> 0xfffc to mean 0x10000 since they are virtually the same value and the
> error checking is safe.  It isn't possible to have this as a valid value.

That might be unnecessarily paranoid, a zero would be legal only with 64K
block size and then only in the first record of the block.

How about this wrapper, with associated struct field name change?

unsigned ext3_entry_len(struct ext3_dir_entry_2 *de)
{
	return (le16_to_cpu(de->entry_len) ? : (1 << 16);
}

Storing will just work.  In search_dirblock we don't even get extra code
because there is already a special check for zero that goes away.

Regards,

Daniel