Question on block group allocation

Question on block group allocation

[Curt Wohlgemuth]

Hi:

I'm seeing a performance problem on ext4 vs ext2, and in trying to
narrow it down, I've got a question about block allocation in ext4
that I'm having trouble figuring out.

The test in question just does random reads of several rather large
files (4.5GB and 10GB) in a single thread.  All files are created in
the top-level directory.  Looking into the block layout for the
various files, I'm struck by the wide separation of the extents in
some of the files.

As a simple example, I formatted/mounted a new ext4 partition with
default parameters (with the exception of "-O ^has_journal", but this
shouldn't make a difference); the FS has 5585 block groups of 4K
blocks.

Using dd, I created (in this order) two 4GB files and a 10GB file in
the mount directory.

The extent blocks are reasonably close together for the two 4GB files,
but the extents for the 10GB file show a huge gap, which seems to hurt
the random read performance pretty substantially.  Here's the output
from debugfs:

BLOCKS:
(IND):8396832, (0-106495):8282112-8388607,
(106496-399359):11241472-11534335, (399360-888831):20482048-20971519,
(888832-1116159):23889920-24117247, (1116160-1277951):71665664-
71827455, (1277952-1767423):78678016-79167487,
(1767424-2125823):102402048-102760447,
(2125824-2148351):102768672-102791199,
(2148352-2621439):102793216-103266303
TOTAL: 2621441

Note the gap between blocks 79167487 and 102402048.  I was lucky
enough to capture the mb_history from this 10GB create:

29109 14       735/30720/32758@1114112 735/30720/2048@1114112
735/30720/2048@1114112  1     0     0  1568  M     0     0
29109 14       736/0/32758@1116160     736/0/2048@1116160
2187/2048/2048@1116160  1     1     0  1568        0     0
29109 14       2187/4096/32758@1118208 2187/4096/2048@1118208
2187/4096/2048@1118208  1     0     0  1568  M     2048  4096

I've been staring at ext4_mb_regular_allocator() trying to understand
why an allocation with a goal block of 736 ends up with a best found
extent group of 2187, and I'm stuck -- at least without a lot of
printk messages.  It seems to me that we just cycle through the block
groups starting with the goal group until we find a group that fits.
Again, according to dumpe2fs, block groups 737, 738, 739, ... all have
32768 free blocks.  So why we end up with a best fit group of 2187 is
a mystery to me.

Can anybody give me an insight to what's happening here?

Thanks,
Curt

Re: Question on block group allocation

[Andreas Dilger]

On Apr 23, 2009  09:41 -0700, Curt Wohlgemuth wrote:
> I'm seeing a performance problem on ext4 vs ext2, and in trying to
> narrow it down, I've got a question about block allocation in ext4
> that I'm having trouble figuring out.
> 
> Using dd, I created (in this order) two 4GB files and a 10GB file in
> the mount directory.
> 
> The extent blocks are reasonably close together for the two 4GB files,
> but the extents for the 10GB file show a huge gap, which seems to hurt
> the random read performance pretty substantially.  Here's the output
> from debugfs:
> 
> BLOCKS:
> (IND):8396832, (0-106495):8282112-8388607,
> (106496-399359):11241472-11534335, (399360-888831):20482048-20971519,
> (888832-1116159):23889920-24117247, (1116160-1277951):71665664-
> 71827455, (1277952-1767423):78678016-79167487,
> (1767424-2125823):102402048-102760447,
> (2125824-2148351):102768672-102791199,
> (2148352-2621439):102793216-103266303
> TOTAL: 2621441
> 
> Note the gap between blocks 79167487 and 102402048.

Well, there are other even larger gaps for other chunks of the file.

> I was lucky enough to capture the mb_history from this 10GB create:
> 
> 29109 14       735/30720/32758@1114112 735/30720/2048@1114112
> 735/30720/2048@1114112  1     0     0  1568  M     0     0
> 29109 14       736/0/32758@1116160     736/0/2048@1116160
> 2187/2048/2048@1116160  1     1     0  1568        0     0
> 29109 14       2187/4096/32758@1118208 2187/4096/2048@1118208
> 2187/4096/2048@1118208  1     0     0  1568  M     2048  4096
> 
> I've been staring at ext4_mb_regular_allocator() trying to understand
> why an allocation with a goal block of 736 ends up with a best found
> extent group of 2187, and I'm stuck -- at least without a lot of
> printk messages.  It seems to me that we just cycle through the block
> groups starting with the goal group until we find a group that fits.
> Again, according to dumpe2fs, block groups 737, 738, 739, ... all have
> 32768 free blocks.  So why we end up with a best fit group of 2187 is
> a mystery to me.

This is likely the "uninit_bg" feature that is causing the allocations
to skip groups which are marked BLOCK_UNINIT.  In some sense the benefit
of skipping the block bitmap read during e2fsck is probably not at all
beneficial compared to the cost of the extra seeking during IO.  As the
filesystem gets more full, the BLOCK_UNIIT flags would be cleared anyways,
so we might as well just keep the early allocations contiguous.

A simple change to verify this would be something like the following,
but it hasn't actually been tested.

--- ./fs/ext4/mballoc.c.uninit    2009-04-08 19:13:13.000000000 -0600
+++ ./fs/ext4/mballoc.c 2009-04-23 13:02:22.000000000 -0600
@@ -1742,10 +1723,6 @@ static int ext4_mb_good_group(struct ext
 	switch (cr) {
 	case 0:
 		BUG_ON(ac->ac_2order == 0);
-		/* If this group is uninitialized, skip it initially */
-		desc = ext4_get_group_desc(ac->ac_sb, group, NULL);
-		if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))
-			return 0;
 
 		bits = ac->ac_sb->s_blocksize_bits + 1;
 		for (i = ac->ac_2order; i <= bits; i++)
@@ -2039,9 +2035,7 @@ repeat:
 			ac->ac_groups_scanned++;
 			desc = ext4_get_group_desc(sb, group, NULL);
-			if (cr == 0 || (desc->bg_flags &
-				cpu_to_le16(EXT4_BG_BLOCK_UNINIT) &&
-				ac->ac_2order != 0))
+			if (cr == 0)
 				ext4_mb_simple_scan_group(ac, &e4b);
 			else if (cr == 1 &&
 					ac->ac_g_ex.fe_len == sbi->s_stripe)


Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.

Re: Question on block group allocation

[Curt Wohlgemuth]

Hi Andreas:

On Thu, Apr 23, 2009 at 12:08 PM, Andreas Dilger <adilger@sun.com> wrote:
> On Apr 23, 2009  09:41 -0700, Curt Wohlgemuth wrote:
>> I'm seeing a performance problem on ext4 vs ext2, and in trying to
>> narrow it down, I've got a question about block allocation in ext4
>> that I'm having trouble figuring out.
>>
>> Using dd, I created (in this order) two 4GB files and a 10GB file in
>> the mount directory.
>>
>> The extent blocks are reasonably close together for the two 4GB files,
>> but the extents for the 10GB file show a huge gap, which seems to hurt
>> the random read performance pretty substantially.  Here's the output
>> from debugfs:
>>
>> BLOCKS:
>> (IND):8396832, (0-106495):8282112-8388607,
>> (106496-399359):11241472-11534335, (399360-888831):20482048-20971519,
>> (888832-1116159):23889920-24117247, (1116160-1277951):71665664-
>> 71827455, (1277952-1767423):78678016-79167487,
>> (1767424-2125823):102402048-102760447,
>> (2125824-2148351):102768672-102791199,
>> (2148352-2621439):102793216-103266303
>> TOTAL: 2621441
>>
>> Note the gap between blocks 79167487 and 102402048.
>
> Well, there are other even larger gaps for other chunks of the file.

Really?  Not that it's important, but I'm not seeing them...

>> I was lucky enough to capture the mb_history from this 10GB create:
>>
>> 29109 14       735/30720/32758@1114112 735/30720/2048@1114112
>> 735/30720/2048@1114112  1     0     0  1568  M     0     0
>> 29109 14       736/0/32758@1116160     736/0/2048@1116160
>> 2187/2048/2048@1116160  1     1     0  1568        0     0
>> 29109 14       2187/4096/32758@1118208 2187/4096/2048@1118208
>> 2187/4096/2048@1118208  1     0     0  1568  M     2048  4096
>>
>> I've been staring at ext4_mb_regular_allocator() trying to understand
>> why an allocation with a goal block of 736 ends up with a best found
>> extent group of 2187, and I'm stuck -- at least without a lot of
>> printk messages.  It seems to me that we just cycle through the block
>> groups starting with the goal group until we find a group that fits.
>> Again, according to dumpe2fs, block groups 737, 738, 739, ... all have
>> 32768 free blocks.  So why we end up with a best fit group of 2187 is
>> a mystery to me.
>
> This is likely the "uninit_bg" feature that is causing the allocations
> to skip groups which are marked BLOCK_UNINIT.  In some sense the benefit
> of skipping the block bitmap read during e2fsck is probably not at all
> beneficial compared to the cost of the extra seeking during IO.  As the
> filesystem gets more full, the BLOCK_UNIIT flags would be cleared anyways,
> so we might as well just keep the early allocations contiguous.

Ah, thanks!  That's what I was missing.  Yes, I sort of skipped over
the "is this a good group?" question.

> A simple change to verify this would be something like the following,
> but it hasn't actually been tested.

Tell you what:  I'll try this out and see if it helps out my test case.

Thanks,
Curt

>
> --- ./fs/ext4/mballoc.c.uninit    2009-04-08 19:13:13.000000000 -0600
> +++ ./fs/ext4/mballoc.c 2009-04-23 13:02:22.000000000 -0600
> @@ -1742,10 +1723,6 @@ static int ext4_mb_good_group(struct ext
>        switch (cr) {
>        case 0:
>                BUG_ON(ac->ac_2order == 0);
> -               /* If this group is uninitialized, skip it initially */
> -               desc = ext4_get_group_desc(ac->ac_sb, group, NULL);
> -               if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))
> -                       return 0;
>
>                bits = ac->ac_sb->s_blocksize_bits + 1;
>                for (i = ac->ac_2order; i <= bits; i++)
> @@ -2039,9 +2035,7 @@ repeat:
>                        ac->ac_groups_scanned++;
>                        desc = ext4_get_group_desc(sb, group, NULL);
> -                       if (cr == 0 || (desc->bg_flags &
> -                               cpu_to_le16(EXT4_BG_BLOCK_UNINIT) &&
> -                               ac->ac_2order != 0))
> +                       if (cr == 0)
>                                ext4_mb_simple_scan_group(ac, &e4b);
>                        else if (cr == 1 &&
>                                        ac->ac_g_ex.fe_len == sbi->s_stripe)
>
>
> Cheers, Andreas
> --
> Andreas Dilger
> Sr. Staff Engineer, Lustre Group
> Sun Microsystems of Canada, Inc.
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Question on block group allocation

[Theodore Tso]

On Thu, Apr 23, 2009 at 03:02:05PM -0700, Curt Wohlgemuth wrote:
> > This is likely the "uninit_bg" feature that is causing the allocations
> > to skip groups which are marked BLOCK_UNINIT.  In some sense the benefit
> > of skipping the block bitmap read during e2fsck is probably not at all
> > beneficial compared to the cost of the extra seeking during IO.  As the
> > filesystem gets more full, the BLOCK_UNIIT flags would be cleared anyways,
> > so we might as well just keep the early allocations contiguous.

Well, I tried out Andreas' patch, by doing an rsync copy from my SSD
root partition to a 5400 rpm laptop drive, and then ran e2fsck and
dumpe2fs.  The results were interesting:

               Before Patch			  After Patch
	      Time in seconds			Time in seconds
	    Real /  User/  Sys   MB/s	   Real /  User/  Sys    MB/s	   
Pass 1      8.52 / 2.21 / 0.46  20.43	   8.84 / 4.97 / 1.11   19.68
Pass 2	   21.16 / 1.02 / 1.86  11.30	   6.54 / 1.77 / 1.78   36.39
Pass 3 	    0.01 / 0.00 / 0.00 139.00	   0.01 / 0.01 / 0.00  128.90
Pass 4	    0.16 / 0.15 / 0.00   0.00	   0.17 / 0.17 / 0.00    0.00
Pass 5	    2.52 / 1.99 / 0.09   0.79	   2.31 / 1.78 / 0.06	 0.86
Total	   32.40 / 5.11 / 2.49  12.81	  17.99 / 8.75 / 2.98	23.01

The surprise is in the gross inspection of the dumpe2fs results:

    	     	       	     Before Patch    After Patch
# of non-contig files  	     	762	        779
# of non-contig directories	571		570
# of BLOCK_UNINIT bg's		307		293
# of INODE_UNINIT bg's		503		503

So the interesting thing is that the patch only "broke open" an
additional 14 block groups (out of a 333 block groups in use when the
filesystem was created with the unpatched kernel).  However, this
allowed the pass 2 directory time to go *down* by over a factor of
three (from 21.2 seconds with the unpatched ext4 code to 6.5 seconds
with the the patch.

I think what the patch did was to diminish allocation pressure on the
first block group in the flex_bg, so we weren't mixing directory and
regular file contents.  This eliminated seeks during pass 2 of e2fsck,
which was actually a Very Good Thing.

> > A simple change to verify this would be something like the following,
> > but it hasn't actually been tested.
> 
> Tell you what:  I'll try this out and see if it helps out my test case.

Let me know what this does for your test case.  Hopefully the patch
also makes things better, since this patch is looking very interesting
right now.

Andreas, can I get a Signed-off-by from you for this patch? 

Thanks,

						- Ted
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Question on block group allocation

[Curt Wohlgemuth]

Hi Ted:

I don't have access to the actual data right now, because I created
the files and ran the benchmark just before leaving for a few days,
but...

On Sun, Apr 26, 2009 at 8:14 PM, Theodore Tso <tytso@mit.edu> wrote:
> On Thu, Apr 23, 2009 at 03:02:05PM -0700, Curt Wohlgemuth wrote:
>> > This is likely the "uninit_bg" feature that is causing the allocations
>> > to skip groups which are marked BLOCK_UNINIT.  In some sense the benefit
>> > of skipping the block bitmap read during e2fsck is probably not at all
>> > beneficial compared to the cost of the extra seeking during IO.  As the
>> > filesystem gets more full, the BLOCK_UNIIT flags would be cleared anyways,
>> > so we might as well just keep the early allocations contiguous.
>
> Well, I tried out Andreas' patch, by doing an rsync copy from my SSD
> root partition to a 5400 rpm laptop drive, and then ran e2fsck and
> dumpe2fs.  The results were interesting:
>
>               Before Patch                       After Patch
>              Time in seconds                   Time in seconds
>            Real /  User/  Sys   MB/s      Real /  User/  Sys    MB/s
> Pass 1      8.52 / 2.21 / 0.46  20.43      8.84 / 4.97 / 1.11   19.68
> Pass 2     21.16 / 1.02 / 1.86  11.30      6.54 / 1.77 / 1.78   36.39
> Pass 3      0.01 / 0.00 / 0.00 139.00      0.01 / 0.01 / 0.00  128.90
> Pass 4      0.16 / 0.15 / 0.00   0.00      0.17 / 0.17 / 0.00    0.00
> Pass 5      2.52 / 1.99 / 0.09   0.79      2.31 / 1.78 / 0.06    0.86
> Total      32.40 / 5.11 / 2.49  12.81     17.99 / 8.75 / 2.98   23.01
>
> The surprise is in the gross inspection of the dumpe2fs results:
>
>                             Before Patch    After Patch
> # of non-contig files           762             779
> # of non-contig directories     571             570
> # of BLOCK_UNINIT bg's          307             293
> # of INODE_UNINIT bg's          503             503
>
> So the interesting thing is that the patch only "broke open" an
> additional 14 block groups (out of a 333 block groups in use when the
> filesystem was created with the unpatched kernel).  However, this
> allowed the pass 2 directory time to go *down* by over a factor of
> three (from 21.2 seconds with the unpatched ext4 code to 6.5 seconds
> with the the patch.
>
> I think what the patch did was to diminish allocation pressure on the
> first block group in the flex_bg, so we weren't mixing directory and
> regular file contents.  This eliminated seeks during pass 2 of e2fsck,
> which was actually a Very Good Thing.
>
>> > A simple change to verify this would be something like the following,
>> > but it hasn't actually been tested.
>>
>> Tell you what:  I'll try this out and see if it helps out my test case.
>
> Let me know what this does for your test case.  Hopefully the patch
> also makes things better, since this patch is looking very interesting
> right now.

The random read throughput on the 10GB file went from ~16 MB/s to ~22
MB/s after Andreas' patch; the total fragmentation of the file was
much lower than before his patch.

However, the number of extents went up by quite a bit (I don't have
the debugfs output in front of me at the moment, sorry).  It seemed
that no extent crossed a block group; I didn't have time to see if
Andreas' patch disabled flex BGs or not, as to what was going on.

I'll be able to send details out on Tuesday.

Curt

>
> Andreas, can I get a Signed-off-by from you for this patch?
>
> Thanks,
>
>                                                - Ted
>
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Question on block group allocation

[Theodore Tso]

On Sun, Apr 26, 2009 at 11:29:39PM -0600, Curt Wohlgemuth wrote:
> 
> The random read throughput on the 10GB file went from ~16 MB/s to ~22
> MB/s after Andreas' patch; the total fragmentation of the file was
> much lower than before his patch.
> 
> However, the number of extents went up by quite a bit (I don't have
> the debugfs output in front of me at the moment, sorry).  It seemed
> that no extent crossed a block group; I didn't have time to see if
> Andreas' patch disabled flex BGs or not, as to what was going on.

Try running e2fsck with the "-E fragcheck" option, and then capture
e2fsck's stdout.  It will help with the grunt work of doing the
analysis, in terms of displaying the details of all of the files which
are discontiguous.

						- Ted

Re: Question on block group allocation

[Theodore Tso]

On Sun, Apr 26, 2009 at 11:29:39PM -0600, Curt Wohlgemuth wrote:
> The random read throughput on the 10GB file went from ~16 MB/s to ~22
> MB/s after Andreas' patch; the total fragmentation of the file was
> much lower than before his patch.
> 
> However, the number of extents went up by quite a bit (I don't have
> the debugfs output in front of me at the moment, sorry).  

I'm curious what you meant by the combination of these two statements,
"the total fragmentation of the file was much lower than before his
patch", and "the number of extents went up by quite a bit".  Can you
send me the debugfs output when you have a chance?

Thanks,

						- Ted

Re: Question on block group allocation

[Curt Wohlgemuth]

[-- Attachment #1: Type: text/plain, Size: 1750 bytes --]

Hi Ted:

On Mon, Apr 27, 2009 at 3:40 PM, Theodore Tso <tytso@mit.edu> wrote:
> On Sun, Apr 26, 2009 at 11:29:39PM -0600, Curt Wohlgemuth wrote:
>> The random read throughput on the 10GB file went from ~16 MB/s to ~22
>> MB/s after Andreas' patch; the total fragmentation of the file was
>> much lower than before his patch.
>>
>> However, the number of extents went up by quite a bit (I don't have
>> the debugfs output in front of me at the moment, sorry).
>
> I'm curious what you meant by the combination of these two statements,
> "the total fragmentation of the file was much lower than before his
> patch", and "the number of extents went up by quite a bit".  Can you
> send me the debugfs output when you have a chance?

Sorry it's been so long for me to reply.

Okay, my phrasing was not as precise as it could have been.  What I
meant by "total fragmentation" was simply that the range of physical
blocks for the 10GB file was much lower with Andreas' patch:

Before patch:  8282112 - 103266303
After patch: 271360 - 5074943

The number of extents is much larger.  See the attached debugfs output.

Here's the output of "e2fsck -E fragcheck" on the block devices;
remember, though, that each one has only 3 files:

-rw-rw-r--    1 root     root     10737418240 Apr 23 15:33 10g
-rw-rw-r--    1 root     root     4294967296 Apr 23 15:30 4g
-rw-rw-r--    1 root     root     4294967296 Apr 23 15:30 4g-2
drwx------    2 root     root        16384 Apr 23 15:27 lost+found/

Before patch:
e2fsck 1.41.3 (12-Oct-2008)
/dev/hdm3: clean, 14/45760512 files, 7608255/183010471 blocks

After patch:
e2fsck 1.41.3 (12-Oct-2008)
/dev/hdo3: clean, 14/45760512 files, 7608258/183010471 blocks


Thanks,
Curt

[-- Attachment #2: debugfs.before-patch --]
[-- Type: application/octet-stream, Size: 888 bytes --]

Inode: 14   Type: regular    Mode:  0664   Flags: 0x80000
Generation: 3039487964    Version: 0x00000000:00000001
User:     0   Group:     0   Size: 10737418240
File ACL: 0    Directory ACL: 0
Links: 1   Blockcount: 20971528
Fragment:  Address: 0    Number: 0    Size: 0
 ctime: 0x49efa0f4:b4e10eb4 -- Wed Apr 22 15:57:56 2009
 atime: 0x49f89bb5:2f6e87cc -- Wed Apr 29 11:25:57 2009
 mtime: 0x49efa0f4:b4e10eb4 -- Wed Apr 22 15:57:56 2009
crtime: 0x49efa0d1:449576d0 -- Wed Apr 22 15:57:21 2009
Size of extra inode fields: 28
BLOCKS:
(IND):8396832, (0-106495):8282112-8388607, (106496-399359):11241472-11534335, (399360-888831):20482048-20971519, (888832-1116159):23889920-24117247, (1116160-1277951):71665664-71827455, (1277952-1767423):78678016-79167487, (1767424-2125823):102402048-102760447, (2125824-2148351):102768672-102791199, (2148352-2621439):102793216-103266303
TOTAL: 2621441


[-- Attachment #3: debugfs.after-patch --]
[-- Type: application/octet-stream, Size: 12951 bytes --]

Inode: 14   Type: regular    Mode:  0664   Flags: 0x80000
Generation: 310363953    Version: 0x00000000:00000001
User:     0   Group:     0   Size: 10737418240
File ACL: 0    Directory ACL: 0
Links: 1   Blockcount: 20971536
Fragment:  Address: 0    Number: 0    Size: 0
 ctime: 0x49f0ec9f:2956e76c -- Thu Apr 23 15:33:03 2009
 atime: 0x49f0ec2b:588bc38c -- Thu Apr 23 15:31:07 2009
 mtime: 0x49f0ec9f:2956e76c -- Thu Apr 23 15:33:03 2009
crtime: 0x49f0ec2b:588bc38c -- Thu Apr 23 15:31:07 2009
Size of extra inode fields: 28
BLOCKS:
(IND):820225, (0-1023):271360-272383, (1024-2047):821248-822271, (2048-4095):825344-827391, (4096-6143):829440-831487, (6144-8191):835584-837631, (8192-10239):841728-843775, (10240-12287):847872-849919, (12288-14335):851968-854015, (14336-16383):858112-860159, (16384-18431):868352-870399, (18432-20479):872448-874495, (20480-22527):876544-878591, (22528-24575):886784-888831, (24576-26623):894976-897023, (26624-28671):903168-905215, (28672-30719):907264-909311, (30720-32767):913408-915455, (32768-34815):919552-921599, (34816-36863):925696-927743, (36864-38911):931840-933887, (38912-40959):937984-940031, (40960-43007):944128-946175, (43008-45055):950272-952319, (45056-47103):956416-958463, (47104-49151):962560-964607, (49152-51199):970752-972799, (51200-53247):976896-978943, (53248-55295):983040-985087, (55296-57343):989184-991231, (57344-59391):993280-995327, (59392-61439):999424-1001471, (61440-63487):1007616-1009663, (63488-65535):1011712-1013759, (65536-67583):1017856-1019903, (67584-69631):1026048-1028095, (69632-71679):1030144-1032191, (71680-73727):1036288-1038335, (73728-75775):1044480-1046527, (75776-77823):1083392-1085439, (77824-79871):1091584-1093631, (79872-81919):1095680-1097727, (81920-83967):1101824-1103871, (83968-86015):1105920-1107967, (86016-88063):1114112-1116159, (88064-90111):1120256-1122303, (90112-92159):1124352-1126399, (92160-94207):1132544-1134591, (94208-96255):1138688-1140735, (96256-98303):1142784-1144831, (98304-100351):1150976-1153023, (100352-102399):1157120-1159167, (102400-104447):1161216-1163263, (104448-106495):1169408-1171455, (106496-108543):1175552-1177599, (108544-110591):1179648-1181695, (110592-112639):1187840-1189887, (112640-114687):1193984-1196031, (114688-116735):1198080-1200127, (116736-118783):1206272-1208319, (118784-120831):1212416-1214463, (120832-122879):1218560-1220607, (122880-124927):1226752-1228799, (124928-126975):1230848-1232895, (126976-129023):1236992-1239039, (129024-131071):1245184-1247231, (131072-133119):1249280-1251327, (133120-135167):1255424-1257471, (135168-137215):1263616-1265663, (137216-139263):1267712-1269759, (139264-141311):1273856-1275903, (141312-143359):1277952-1279999, (143360-145407):1284096-1286143, (145408-147455):1294336-1296383, (147456-149503):1298432-1300479, (149504-151551):1302528-1304575, (151552-153599):1312768-1314815, (153600-155647):1316864-1318911, (155648-157695):1320960-1323007, (157696-159743):1331200-1333247, (159744-161791):1335296-1337343, (161792-163839):1339392-1341439, (163840-165887):1349632-1351679, (165888-167935):1353728-1355775, (167936-169983):1357824-1359871, (169984-172031):1368064-1370111, (172032-174079):1372160-1374207, (174080-176127):1376256-1378303, (176128-178175):1386496-1388543, (178176-180223):1390592-1392639, (180224-182271):1394688-1396735, (182272-184319):1404928-1406975, (184320-186367):1409024-1411071, (186368-188415):1413120-1415167, (188416-190463):1423360-1425407, (190464-192511):1427456-1429503, (192512-194559):1431552-1433599, (194560-196607):1441792-1443839, (196608-198655):1445888-1447935, (198656-200703):1449984-1452031, (200704-202751):1460224-1462271, (202752-204799):1464320-1466367, (204800-206847):1468416-1470463, (206848-208895):1478656-1480703, (208896-210943):1482752-1484799, (210944-212991):1486848-1488895, (212992-215039):1497088-1499135, (215040-217087):1501184-1503231, (217088-219135):1505280-1507327, (219136-221183):1515520-1517567, (221184-223231):1519616-1521663, (223232-225279):1523712-1525759, (225280-227327):1531904-1533951, (227328-229375):1538048-1540095, (229376-231423):1544192-1546239, (231424-233471):1550336-1552383, (233472-235519):1558528-1560575, (235520-237567):1562624-1564671, (237568-239615):1566720-1568767, (239616-241663):1607680-1609727, (241664-243711):1613824-1615871, (243712-245759):1619968-1622015, (245760-247807):1628160-1630207, (247808-249855):1634304-1636351, (249856-251903):1638400-1640447, (251904-253951):1644544-1646591, (253952-255999):1652736-1654783, (256000-258047):1656832-1658879, (258048-260095):1662976-1665023, (260096-262143):1671168-1673215, (262144-264191):1675264-1677311, (264192-266239):1681408-1683455, (266240-268287):1689600-1691647, (268288-270335):1693696-1695743, (270336-272383):1699840-1701887, (272384-274431):1708032-1710079, (274432-276479):1712128-1714175, (276480-278527):1718272-1720319, (278528-280575):1726464-1728511, (280576-282623):1730560-1732607, (282624-284671):1736704-1738751, (284672-286719):1744896-1746943, (286720-288767):1748992-1751039, (288768-290815):1755136-1757183, (290816-292863):1763328-1765375, (292864-294911):1767424-1769471, (294912-296959):1773568-1775615, (296960-299007):1781760-1783807, (299008-301055):1785856-1787903, (301056-303103):1792000-1794047, (303104-305151):1800192-1802239, (305152-307199):1804288-1806335, (307200-309247):1810432-1812479, (309248-311295):1818624-1820671, (311296-313343):1822720-1824767, (313344-315391):1828864-1830911, (315392-317439):1835008-1837055, (317440-319487):1841152-1843199, (319488-321535):1847296-1849343, (321536-323583):1853440-1855487, (323584-325631):1859584-1861631, (325632-327679):1865728-1867775, (327680-329727):1871872-1873919, (329728-331775):1878016-1880063, (331776-333823):1884160-1886207, (333824-335871):1890304-1892351, (335872-337919):1896448-1898495, (337920-339967):1902592-1904639, (339968-342015):1908736-1910783, (342016-344063):1914880-1916927, (344064-346111):1921024-1923071, (346112-348159):1927168-1929215, (348160-350207):1933312-1935359, (350208-352255):1939456-1941503, (352256-354303):1945600-1947647, (354304-356351):1951744-1953791, (356352-358399):1957888-1959935, (358400-360447):1964032-1966079, (360448-362495):1970176-1972223, (362496-364543):1976320-1978367, (364544-366591):1982464-1984511, (366592-368639):1988608-1990655, (368640-370687):1994752-1996799, (370688-372735):2000896-2002943, (372736-374783):2007040-2009087, (374784-376831):2013184-2015231, (376832-378879):2019328-2021375, (378880-380927):2025472-2027519, (380928-382975):2031616-2033663, (382976-385023):2035712-2037759, (385024-387071):2041856-2043903, (387072-389119):2050048-2052095, (389120-391167):2056192-2058239, (391168-393215):2062336-2064383, (393216-395263):2068480-2070527, (395264-397311):2074624-2076671, (397312-399359):2080768-2082815, (399360-401407):2086912-2088959, (401408-403455):2093056-2095103, (403456-405503):2129920-2131967, (405504-407551):2138112-2140159, (407552-409599):2144256-2146303, (409600-411647):2148352-2150399, (411648-413695):2154496-2156543, (413696-415743):2162688-2164735, (415744-417791):2166784-2168831, (417792-419839):2172928-2174975, (419840-421887):2181120-2183167, (421888-423935):2185216-2187263, (423936-425983):2191360-2193407, (425984-428031):2199552-2201599, (428032-430079):2203648-2205695, (430080-432127):2209792-2211839, (432128-434175):2217984-2220031, (434176-436223):2222080-2224127, (436224-438271):2228224-2230271, (438272-440319):2236416-2238463, (440320-442367):2240512-2242559, (442368-444415):2246656-2248703, (444416-446463):2254848-2256895, (446464-448511):2258944-2260991, (448512-450559):2267136-2269183, (450560-452607):2275328-2277375, (452608-454655):2281472-2283519, (454656-456703):2287616-2289663, (456704-458751):2295808-2297855, (458752-460799):2299904-2301951, (460800-462847):2306048-2308095, (462848-464895):2310144-2312191, (464896-466943):2320384-2322431, (466944-468991):2324480-2326527, (468992-471039):2328576-2330623, (471040-473087):2338816-2340863, (473088-475135):2342912-2344959, (475136-477183):2347008-2349055, (477184-479231):2357248-2359295, (479232-481279):2363392-2365439, (481280-483327):2367488-2369535, (483328-485375):2377728-2379775, (485376-487423):2381824-2383871, (487424-489471):2385920-2387967, (489472-491519):2396160-2398207, (491520-493567):2400256-2402303, (493568-495615):2404352-2406399, (495616-497663):2414592-2416639, (497664-499711):2418688-2420735, (499712-501759):2424832-2426879, (501760-503807):2433024-2435071, (503808-505855):2437120-2439167, (505856-507903):2443264-2445311, (507904-509951):2451456-2453503, (509952-511999):2455552-2457599, (512000-514047):2461696-2463743, (514048-516095):2469888-2471935, (516096-518143):2473984-2476031, (518144-520191):2480128-2482175, (520192-522239):2488320-2490367, (522240-524287):2492416-2494463, (524288-526335):2496512-2498559, (526336-528383):2502656-2504703, (528384-530431):2510848-2512895, (530432-532479):2516992-2519039, (532480-534527):2523136-2525183, (534528-536575):2527232-2529279, (536576-538623):2535424-2537471, (538624-540671):2541568-2543615, (540672-542719):2545664-2547711, (542720-544767):2553856-2555903, (544768-546815):2560000-2562047, (546816-548863):2564096-2566143, (548864-550911):2572288-2574335, (550912-552959):2578432-2580479, (552960-555007):2582528-2584575, (555008-557055):2590720-2592767, (557056-559103):2596864-2598911, (559104-561151):2600960-2603007, (561152-563199):2609152-2611199, (563200-565247):2615296-2617343, (565248-567295):2619392-2621439, (567296-569343):2660352-2662399, (569344-571391):2666496-2668543, (571392-573439):2672640-2674687, (573440-575487):2678784-2680831, (575488-579583):2684928-2689023, (579584-583679):2693120-2697215, (583680-585727):2699264-2701311, (585728-589823):2705408-2709503, (589824-591871):2711552-2713599, (591872-595967):2717696-2721791, (595968-598015):2723840-2725887, (598016-602111):2729984-2734079, (602112-604159):2736128-2738175, (604160-608255):2742272-2746367, (608256-610303):2748416-2750463, (610304-612351):2752512-2754559, (612352-614399):2756608-2758655, (614400-616447):2762752-2764799, (616448-618495):2766848-2768895, (618496-622591):2770944-2775039, (622592-624639):2779136-2781183, (624640-628735):2783232-2787327, (628736-630783):2791424-2793471, (630784-632831):2795520-2797567, (632832-634879):2799616-2801663, (634880-636927):2803712-2805759, (636928-638975):2807808-2809855, (638976-641023):2811904-2813951, (641024-643071):2816000-2818047, (643072-645119):2820096-2822143, (645120-647167):2824192-2826239, (647168-649215):2828288-2830335, (649216-651263):2832384-2834431, (651264-653311):2836480-2838527, (653312-655359):2840576-2842623, (655360-657407):2844672-2846719, (657408-659455):2848768-2850815, (659456-661503):2852864-2854911, (661504-663551):2856960-2859007, (663552-665599):2861056-2863103, (665600-667647):2865152-2867199, (667648-669695):2869248-2871295, (669696-671743):2873344-2875391, (671744-673791):2877440-2879487, (673792-675839):2881536-2883583, (675840-677887):2885632-2887679, (677888-679935):2889728-2891775, (679936-681983):2893824-2895871, (681984-684031):2897920-2899967, (684032-686079):2902016-2904063, (686080-688127):2906112-2908159, (688128-690175):2910208-2912255, (690176-692223):2914304-2916351, (692224-694271):2918400-2920447, (694272-696319):2922496-2924543, (696320-698367):2926592-2928639, (698368-700415):2930688-2932735, (700416-702463):2934784-2936831, (702464-704511):2938880-2940927, (704512-706559):2942976-2945023, (706560-708607):2947072-2949119, (708608-710655):2951168-2953215, (IND):2957312, (710656-712703):2955264-2957311, (712704-714751):2961408-2963455, (714752-716799):2965504-2967551, (716800-718847):2969600-2971647, (718848-720895):2973696-2975743, (720896-722943):2977792-2979839, (722944-724991):2981888-2983935, (724992-727039):2985984-2988031, (727040-729087):2990080-2992127, (729088-733183):2994176-2998271, (733184-735231):3002368-3004415, (735232-739327):3006464-3010559, (739328-741375):3014656-3016703, (741376-743423):3018752-3020799, (743424-745471):3022848-3024895, (745472-747519):3026944-3028991, (747520-749567):3031040-3033087, (749568-751615):3035136-3037183, (751616-753663):3039232-3041279, (753664-755711):3043328-3045375, (755712-757759):3047424-3049471, (757760-759807):3051520-3053567, (759808-761855):3055616-3057663, (761856-763903):3059712-3061759, (763904-765951):3063808-3065855, (765952-767999):3067904-3069951, (768000-770047):3072000-3074047, (770048-772095):3076096-3078143, (772096-774143):3080192-3082239, (774144-776191):3084288-3086335, (776192-778239):3088384-3090431, (778240-780287):3092480-3094527, (780288-782335):3096576-3098623, (782336-784383):3100672-3102719, (784384-825343):3104768-3145727, (825344-1316863):3178496-3670015, (1316864-1710079):3702784-4095999, (1710080-1806335):4098048-4194303, (1806336-2297855):4227072-4718591, (2297856-2621439):4751360-5074943
TOTAL: 2621442

Re: Question on block group allocation

[Theodore Tso]

On Wed, Apr 29, 2009 at 03:16:47PM -0400, Theodore Tso wrote:
> 
> When you have a chance, can you send out the details from your test run?
> 

Oops, sorry, our two e-mails overlapped.  Sorry, I didn't see your new
e-mail when I sent my ping-o-gram.

On Wed, Apr 29, 2009 at 11:38:49AM -0700, Curt Wohlgemuth wrote:
> 
> Okay, my phrasing was not as precise as it could have been.  What I
> meant by "total fragmentation" was simply that the range of physical
> blocks for the 10GB file was much lower with Andreas' patch:
> 
> Before patch:  8282112 - 103266303
> After patch: 271360 - 5074943
> 
> The number of extents is much larger.  See the attached debugfs output.

Ah, OK.  You didn't attach the "e2fsck -E fragcheck" output, but I'm
going to guess that the blocks for 10g, 4g, and 4g-2 ended up getting
interleaved, possibly because they were written in parallel, and not
one after each other?  Each of the extents in the "after" debugfs were
proximately 2k blocks (8 megabytes) in length, and are separated by a
largish cnumber of blocks.  

Now, if my theory that the files were written in an interleaved
fashion is correct, if it is also true that they will be read in an
interleaved pattern, the layout on disk might actually be the best
one.  If however they are going to be read sequentially, and you
really want them to be allocated contiguously, then if you know what
the final size of these files will be, then the probably the best
thing to do is to use the fallocate system call.

Does that make sense?

					- Ted

Re: Question on block group allocation

[Curt Wohlgemuth]

Hi Ted:

On Wed, Apr 29, 2009 at 12:37 PM, Theodore Tso <tytso@mit.edu> wrote:
> On Wed, Apr 29, 2009 at 03:16:47PM -0400, Theodore Tso wrote:
>>
>> When you have a chance, can you send out the details from your test run?
>>
>
> Oops, sorry, our two e-mails overlapped.  Sorry, I didn't see your new
> e-mail when I sent my ping-o-gram.
>
> On Wed, Apr 29, 2009 at 11:38:49AM -0700, Curt Wohlgemuth wrote:
>>
>> Okay, my phrasing was not as precise as it could have been.  What I
>> meant by "total fragmentation" was simply that the range of physical
>> blocks for the 10GB file was much lower with Andreas' patch:
>>
>> Before patch:  8282112 - 103266303
>> After patch: 271360 - 5074943
>>
>> The number of extents is much larger.  See the attached debugfs output.
>
> Ah, OK.  You didn't attach the "e2fsck -E fragcheck" output, but I'm
> going to guess that the blocks for 10g, 4g, and 4g-2 ended up getting
> interleaved, possibly because they were written in parallel, and not
> one after each other?  Each of the extents in the "after" debugfs were
> proximately 2k blocks (8 megabytes) in length, and are separated by a
> largish cnumber of blocks.

Hmm, I thought I attached the output from "e2fsck -E fragcheck"; yes,
I did: one simple line:

        /dev/hdm3: clean, 14/45760512 files, 7608255/183010471 blocks

And actually, I created the files sequentially:

dd if=/dev/zero of=$MNT_PT/4g bs=1G count=4
dd if=/dev/zero of=$MNT_PT/4g-2 bs=1G count=4
dd if=/dev/zero of=$MNT_PT/10g bs=1G count=10

> Now, if my theory that the files were written in an interleaved
> fashion is correct, if it is also true that they will be read in an
> interleaved pattern, the layout on disk might actually be the best
> one.  If however they are going to be read sequentially, and you
> really want them to be allocated contiguously, then if you know what
> the final size of these files will be, then the probably the best
> thing to do is to use the fallocate system call.
>
> Does that make sense?

Sure, in this sense.

The test in question does something like this:

1. Create 20 or so large files, sequentially.
2. Randomly choose a file.
3. Randomly choose an offset in this file.
4. Read from that file/offset a fixed buffer size (say 256k); the file
was opened with O_DIRECT
5. Go back to #2
6. Stop after some time period

This might not be the most realistic workload we want (the test
actually can be run by doing #1 above with multiple threads), but it's
certainly interesting.

The point that I'm interested in is why the physical block spread is
so different for the 10GB file between (a) the above 'dd' command
sequence; and (b) simply creating the "10g" file alone, without
creating the 4GB files first.

I just did (b) above on a kernel without Andreas' patch, on a freshly
formatted ext4 FS, and here's (most of) the debugfs output for it:

BLOCKS:
(IND):164865, (0-63487):34816-98303, (63488-126975):100352-163839, (126976-19046
3):165888-229375, (190464-253951):231424-294911, (253952-481279):296960-524287,
(481280-544767):821248-884735, (544768-706559):886784-1048575, (706560-1196031):
1607680-2097151, (1196032-1453067):2656256-2913291
TOTAL: 1453069

The total spread of the blocks is tiny compared to the total spread
from the 3 "dd" commands above.

I haven't yet really looked at the block allocation results using
Andreas' patch, except for the "10g" file after the three "dd"
commands above.  So I'm not sure what the effects are with, say,
larger numbers of files.  I'll be doing some more experimentation
soon.

Thanks,
Curt
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Question on block group allocation

[Theodore Tso]

On Wed, Apr 29, 2009 at 01:21:09PM -0700, Curt Wohlgemuth wrote:
> 
> Hmm, I thought I attached the output from "e2fsck -E fragcheck"; yes,
> I did: one simple line:
> 
>         /dev/hdm3: clean, 14/45760512 files, 7608255/183010471 blocks

Sorry, I should have been more explicit.   You need to do

"e2fsck -f -E fragcheck", and you will get a *heck* of a lot more than
a single line.  :-)

> And actually, I created the files sequentially:
> 
> dd if=/dev/zero of=$MNT_PT/4g bs=1G count=4
> dd if=/dev/zero of=$MNT_PT/4g-2 bs=1G count=4
> dd if=/dev/zero of=$MNT_PT/10g bs=1G count=10

Really?  Hmm, I wouldn't have expected that.  So now I'd really love
to see the fragcheck results (both with and without the patch), and/or
the results of debugfs stat'ing all three files, both with and without
the patch.

Thanks,

						- Ted

Re: Question on block group allocation

[Theodore Tso]

Oh --- one more question.  You did these tests on your 2.6.26-based
kernel with ext4 backports, right?  Not 2.6.30 mainline kernel?  Did
you backport the changes to the block and inode allocators?  i.e.,
this patch (plus a 1 or 2 subsequent bug fixes)?


commit a4912123b688e057084e6557cef8924f7ae5bbde
Author: Theodore Ts'o <tytso@mit.edu>
Date:   Thu Mar 12 12:18:34 2009 -0400

    ext4: New inode/block allocation algorithms for flex_bg filesystems
    
    The find_group_flex() inode allocator is now only used if the
    filesystem is mounted using the "oldalloc" mount option.  It is
    replaced with the original Orlov allocator that has been updated for
    flex_bg filesystems (it should behave the same way if flex_bg is
    disabled).  The inode allocator now functions by taking into account
    each flex_bg group, instead of each block group, when deciding whether
    or not it's time to allocate a new directory into a fresh flex_bg.
    
    The block allocator has also been changed so that the first block
    group in each flex_bg is preferred for use for storing directory
    blocks.  This keeps directory blocks close together, which is good for
    speeding up e2fsck since large directories are more likely to look
    like this:
    
    debugfs:  stat /home/tytso/Maildir/cur
    Inode: 1844562   Type: directory    Mode:  0700   Flags: 0x81000
    Generation: 1132745781    Version: 0x00000000:0000ad71
    User: 15806   Group: 15806   Size: 1060864
    File ACL: 0    Directory ACL: 0
    Links: 2   Blockcount: 2072
    Fragment:  Address: 0    Number: 0    Size: 0
     ctime: 0x499c0ff4:164961f4 -- Wed Feb 18 08:41:08 2009
     atime: 0x499c0ff4:00000000 -- Wed Feb 18 08:41:08 2009
     mtime: 0x49957f51:00000000 -- Fri Feb 13 09:10:25 2009
    crtime: 0x499c0f57:00d51440 -- Wed Feb 18 08:38:31 2009
    Size of extra inode fields: 28
    BLOCKS:
    (0):7348651, (1-258):7348654-7348911
    TOTAL: 259
    
    Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>

						- Ted

Re: Question on block group allocation

[Curt Wohlgemuth]

Hi Ted:

On Wed, Apr 29, 2009 at 2:50 PM, Theodore Tso <tytso@mit.edu> wrote:
> Oh --- one more question.  You did these tests on your 2.6.26-based
> kernel with ext4 backports, right?  Not 2.6.30 mainline kernel?  Did
> you backport the changes to the block and inode allocators?  i.e.,
> this patch (plus a 1 or 2 subsequent bug fixes)?
>
>
> commit a4912123b688e057084e6557cef8924f7ae5bbde
> Author: Theodore Ts'o <tytso@mit.edu>
> Date:   Thu Mar 12 12:18:34 2009 -0400
>
>    ext4: New inode/block allocation algorithms for flex_bg filesystems

Yes, we have this patch.  I'm not sure if we have the "1 or 2" bug
fixes you refer to above; do you have commits for these?

I'm regen'ing the e2fsck and debugfs output for the 3 "dd" sequence
above, for our stock kernel and for this + Andreas' patch.

Thanks,
Curt

>
>    The find_group_flex() inode allocator is now only used if the
>    filesystem is mounted using the "oldalloc" mount option.  It is
>    replaced with the original Orlov allocator that has been updated for
>    flex_bg filesystems (it should behave the same way if flex_bg is
>    disabled).  The inode allocator now functions by taking into account
>    each flex_bg group, instead of each block group, when deciding whether
>    or not it's time to allocate a new directory into a fresh flex_bg.
>
>    The block allocator has also been changed so that the first block
>    group in each flex_bg is preferred for use for storing directory
>    blocks.  This keeps directory blocks close together, which is good for
>    speeding up e2fsck since large directories are more likely to look
>    like this:
>
>    debugfs:  stat /home/tytso/Maildir/cur
>    Inode: 1844562   Type: directory    Mode:  0700   Flags: 0x81000
>    Generation: 1132745781    Version: 0x00000000:0000ad71
>    User: 15806   Group: 15806   Size: 1060864
>    File ACL: 0    Directory ACL: 0
>    Links: 2   Blockcount: 2072
>    Fragment:  Address: 0    Number: 0    Size: 0
>     ctime: 0x499c0ff4:164961f4 -- Wed Feb 18 08:41:08 2009
>     atime: 0x499c0ff4:00000000 -- Wed Feb 18 08:41:08 2009
>     mtime: 0x49957f51:00000000 -- Fri Feb 13 09:10:25 2009
>    crtime: 0x499c0f57:00d51440 -- Wed Feb 18 08:38:31 2009
>    Size of extra inode fields: 28
>    BLOCKS:
>    (0):7348651, (1-258):7348654-7348911
>    TOTAL: 259
>
>    Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
>
>                                                - Ted
>
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Question on block group allocation

[Theodore Tso]

On Wed, Apr 29, 2009 at 03:29:55PM -0700, Curt Wohlgemuth wrote:
> Yes, we have this patch.  I'm not sure if we have the "1 or 2" bug
> fixes you refer to above; do you have commits for these?

b5451f7b  ext4: Fix potential inode allocation soft lockup in Orlov allocator
6b82f3cb  ext4: really print the find_group_flex fallback warning only once
7d39db14  ext4: Use struct flex_groups to calculate get_orlov_stats()
9f24e420  ext4: Use atomic_t's in struct flex_groups

						- Ted

Re: Question on block group allocation

[Curt Wohlgemuth]

Hi Ted:

On Wed, Apr 29, 2009 at 2:20 PM, Theodore Tso <tytso@mit.edu> wrote:
> On Wed, Apr 29, 2009 at 01:21:09PM -0700, Curt Wohlgemuth wrote:
>>
>> Hmm, I thought I attached the output from "e2fsck -E fragcheck"; yes,
>> I did: one simple line:
>>
>>         /dev/hdm3: clean, 14/45760512 files, 7608255/183010471 blocks
>
> Sorry, I should have been more explicit.   You need to do
>
> "e2fsck -f -E fragcheck", and you will get a *heck* of a lot more than
> a single line.  :-)
>
>> And actually, I created the files sequentially:
>>
>> dd if=/dev/zero of=$MNT_PT/4g bs=1G count=4
>> dd if=/dev/zero of=$MNT_PT/4g-2 bs=1G count=4
>> dd if=/dev/zero of=$MNT_PT/10g bs=1G count=10
>
> Really?  Hmm, I wouldn't have expected that.  So now I'd really love
> to see the fragcheck results (both with and without the patch), and/or
> the results of debugfs stat'ing all three files, both with and without
> the patch.

Although it might seem like I've been ignoring this request, in fact
I'm having trouble recreating the problem now.  Both the "three dd"
commands above, and the performance problem I was seeing in the
original posting seem to have mysteriously disappeared.  I'll keep
trying and let the list know what I find.

Thanks,
Curt

>
> Thanks,
>
>                                                - Ted
>
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Question on block group allocation

[Theodore Tso]

On Sun, Apr 26, 2009 at 11:29:39PM -0600, Curt Wohlgemuth wrote:
> The random read throughput on the 10GB file went from ~16 MB/s to ~22
> MB/s after Andreas' patch; the total fragmentation of the file was
> much lower than before his patch.
> 
> However, the number of extents went up by quite a bit (I don't have
> the debugfs output in front of me at the moment, sorry).  It seemed
> that no extent crossed a block group; I didn't have time to see if
> Andreas' patch disabled flex BGs or not, as to what was going on.
> 
> I'll be able to send details out on Tuesday.

Hi Curt,

When you have a chance, can you send out the details from your test run?

Many thanks,

						- Ted

Re: Question on block group allocation

[Andreas Dilger]

On Apr 23, 2009  13:08 -0600, Andreas Dilger wrote:
> This is likely the "uninit_bg" feature that is causing the allocations
> to skip groups which are marked BLOCK_UNINIT.  In some sense the benefit
> of skipping the block bitmap read during e2fsck is probably not at all
> beneficial compared to the cost of the extra seeking during IO.  As the
> filesystem gets more full, the BLOCK_UNIIT flags would be cleared anyways,
> so we might as well just keep the early allocations contiguous.
> 
> A simple change to verify this would be something like the following,
> but it hasn't actually been tested.
> 
> --- ./fs/ext4/mballoc.c.uninit    2009-04-08 19:13:13.000000000 -0600
> +++ ./fs/ext4/mballoc.c 2009-04-23 13:02:22.000000000 -0600
> @@ -1742,10 +1723,6 @@ static int ext4_mb_good_group(struct ext
>  	switch (cr) {
>  	case 0:
>  		BUG_ON(ac->ac_2order == 0);
> -		/* If this group is uninitialized, skip it initially */
> -		desc = ext4_get_group_desc(ac->ac_sb, group, NULL);
> -		if (desc->bg_flags & cpu_to_le16(EXT4_BG_BLOCK_UNINIT))
> -			return 0;
>  
>  		bits = ac->ac_sb->s_blocksize_bits + 1;
>  		for (i = ac->ac_2order; i <= bits; i++)
> @@ -2039,9 +2035,7 @@ repeat:
>  			ac->ac_groups_scanned++;
>  			desc = ext4_get_group_desc(sb, group, NULL);
> -			if (cr == 0 || (desc->bg_flags &
> -				cpu_to_le16(EXT4_BG_BLOCK_UNINIT) &&
> -				ac->ac_2order != 0))
> +			if (cr == 0)
>  				ext4_mb_simple_scan_group(ac, &e4b);
>  			else if (cr == 1 &&
>  					ac->ac_g_ex.fe_len == sbi->s_stripe)

Because this is actually proving to be useful:

Signed-off-by: Andreas Dilger <adilger@sun.com>

As we discussed in the call, I suspect BLOCK_UNINIT was more useful in the
past when directories were spread over all groups evenly (pre-Orlov), and
before flex_bg where seeking to read all of the bitmaps was a slow and
painful process.  For flex_bg it could be WORSE to skip bitmap reads because
instead of doing contiguous 64kB reads it may now doing read 4kB, seek,
read 4kB, seek, etc.

Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.