New: non-contiguous files (64.9%) on a ext4 fs

http://bugzilla.kernel.org/show_bug.cgi?id=13930

Summary: non-contiguous files (64.9%) on a ext4 fs
Product: File System
Version: 2.5
Kernel Version: Linux version 2.6.31-rc5 (logik@LogikPC) (gcc version
4.3.3 (Debian 4.3.3-15) ) #1 SMP PREEMPT Sat Aug 1 19:52:55 CEST 2009
Platform: All
OS/Version: Linux
Tree: Mainline
Status: NEW
Severity: normal
Priority: P1
Component: ext4
AssignedTo: [email protected]
ReportedBy: [email protected]
Regression: No

Normally ext4 is a perfect non-contifuous FS ... so why when I make an:

sudo e2fsck -v -f -p /dev/sdc1

15953 inodes used (0.03%)
10361 non-contiguous files (64.9%)
7 non-contiguous directories (0.0%)
nombre d'i-noeuds avec des blocs ind/dind/tind : 0/0/0 Histogramme des profondeurs d'extents : 14555/1388
234324740 blocks used (95.96%)
0 bad blocks
1 large file

14728 regular files
1216 directories
0 character device files
0 block device files
0 fifos
0 links
0 symbolic links (0 fast symbolic links)
0 sockets
--------
15944 files

We have 64.9% of non-contiguous files on a ext4 fs,

Files have been transfered from a cifs mount (useful ?) and files size are [2-10]|[600-800]MB

Some references:
Lacie 1To on usb with usb-Hitachi_HDS721010KLA330

Want more info ... just ask because I don't know what send now for help you :)

Configure bugmail: http://bugzilla.kernel.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching the assignee of the bug.--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

http://bugzilla.kernel.org/show_bug.cgi?id=13930

Eric Sandeen <[email protected]> changed:

What |Removed |Added
----------------------------------------------------------------------------
CC| |[email protected]

--- Comment #1 from Eric Sandeen <[email protected]> 2009-08-07 14:40:11 --- It might be interesting to poke around with filefrag and see which files are fragmented, and compare that to how big they are. Summary stats like this can sometimes be misleading.

Or to put it another way, if half your files are < 100M and contiguous, and the other half are > 100M and all of those have 2 50M extents each, I think e2fsck would say "50.0% non-contiguous" - but this isn't really indicative of a problem.

If you can demonstrate that simply copying a large file (or files) from cifs leads to bad fragmentation of that file (or files), then we probably have something to work on.

Configure bugmail: http://bugzilla.kernel.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching the assignee of the bug.

Note that the largest single extent in ext4 is 128MB, so it is perfectly normal to have fragmented files if they are 600MB in size. Maybe we should change the e2fsck stats to not consider a file fragmented if it fills the whole block group (less any metadata therein)?

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

Ah that crossed my mind, but since so many other e2fsprogs tools coalesce adjacent extents and report "1" I figured e2fsck was too (though I didn't look...)

-Eric

http://bugzilla.kernel.org/show_bug.cgi?id=13930

Theodore Tso <[email protected]> changed:

What |Removed |Added
----------------------------------------------------------------------------
CC| |[email protected]

--- Comment #2 from Theodore Tso <[email protected]> 2009-08-07 22:20:51 --- I'm pretty sure what's going on here is the problem I've reported before where if you have a large number of large files being written at the same time, the Linux page cleaner round-robins between the different dirty inodes to avoid starving some inode from ever getting its dirty pages written out. This then combines with ext4's multi-block allocator limiting its search for 8MB of free extent chunks, so we only expand a dirty page writeback request into 2048
blocks. See the discussion here:

    http://thread.gmane.org/gmane.comp.file-systems.ext4/13107

The reason why you're seeing this so much is that this filesystem has relatively few inodes (just under 16,000) and a very large average inode size (about 54 megabytes), and so a very large number of the files are
"non-contiguous". But, if you look at this statistic from e2fsck:

Histogramme des profondeurs d'extents : 14555/1388

14,555, or 91% of the files, have fewer than 4 extents, so that all of the extents fit in the inode. (Note that an extent addresses at most 128 meg, so
by definition a 512meg file will have at least 4 extents.) That means it's
highly likely that if you look at a particularly large file using "filefrag -v", you will see something like this:

ext logical physical expected length flags

   0       0  2165248             512 
   1     512  2214400  2165759   1536 
   2    2048  2244608  2215935   2048 
   3    4096  2250752  2246655   2048 
   4    6144  2254848  2252799  32768 
   5   38912  2287616            8192 
   6   47104  2299904  2295807   2048 
   7   49152  2306048  2301951   2048 eof

Note that extent #5 is really located contiguously after extent #4; the reason why a new extent was created is because the maximum length that can be encoded in the on-disk extent data structure is 32,768 blocks. (Which if you are using 4k blocks, means a maximum extent size of 128 megs.)

So this kind of "non-contiguous" file is non-optimal, and we really should fix the block allocator to better. On the other hand, it's not as disastrously fragmented as say, the following file from an ext3 filesystem:

ext logical physical length

   0       0  5228587    12 
   1      12  5228600   110 
   2     122  5228768   145
   3     267  5228915     1
   4     268  5228918     9
   5     277  5228936    69
   6     346  5229392   165
   7     511  5230282   124
   8     635  5230496    42
   9     677  5231614    10
  10     687  5231856    20
  11     707  5231877    46
  12     753  5231975     1
  13     754  5232033    14
  14     768  5232205     2
  15     770  5233913     4
  16     774  5233992   262
  17    1036  5234256   191

Part of the problem is that "non-contiguous" or "fragmented" doesn't really describe whether the file is like the first ext4 file (which is indeed non-contiguous, and while it could be better allocated on disk, the time to read the file sequentially won't be _that_ much worse than a file that 100% contiguous), than say, a file like this second ext3 file, where the performance degradation are much worse.

I suppose we could do something where we define "fragmented" as a file where has no extents which are smaller than N blocks, or where the average extent
size is greater than M blocks. My original way of dealing with this number
was to simply use the phrase "non-contiguous" instead of "fragmented", which is technically accurate, but it causes people to get overly concerned when they
see something like "64.9% non-contiguous files". Unfortunately, at moment
what this means is something like "approximately 65% of your files are greater than 8 megabytes".

Configure bugmail: http://bugzilla.kernel.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching the assignee of the bug.

http://bugzilla.kernel.org/show_bug.cgi?id=13930

--- Comment #3 from Cédric M <[email protected]> 2009-08-07 22:37:59 --- I have make some try on a 242MB file:

du -h file
242M

And after an:
Filesystem type is: ef53
File size of ****** is 253480960 (61885 blocks, blocksize 4096)
ext logical physical expected length flags
0 0 215814144 2048

   1    2048 215820288 215816191   2048 
   2    4096 215824384 215822335   2048 
   3    6144 215828480 215826431   2048 
   4    8192 215832576 215830527   2048 
   5   10240 215836672 215834623   2048 
   6   12288 215840768 215838719   2048 
   7   14336 215844864 215842815   2048 
   8   16384 215848960 215846911   2048 
   9   18432 215853056 215851007  26624 
  10   45056 215881728 215879679   2048 
  11   47104 215885824 215883775   2048 
  12   49152 215891968 215887871   2048 
  13   51200 215896064 215894015   2048 
  14   53248 215900160 215898111   2048 
  15   55296 215904256 215902207   2048 
  16   57344 215908352 215906303   2048 
  17   59392 215912448 215910399   2048 
  18   61440 215918592 215914495    445 eof

So why so much extend ?

(ie: ALL files have been write one to one on the whole disk (like a "cp -R /cifs /ext4) (not torrent/crappy_speed_download_tools/etc ... things))

With a full dir: (for / du -h / filefrag / sed )
180M
: 12 extents found
181M
: 20 extents found
281M
: 22 extents found
275M
: 22 extents found
275M
: 22 extents found
181M
: 20 extents found
281M
: 22 extents found
281M
: 21 extents found
277M
: 21 extents found
280M
: 21 extents found
180M
: 21 extents found
285M
: 13 extents found
180M
: 6 extents found

Configure bugmail: http://bugzilla.kernel.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching the assignee of the bug.--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html

No, actually e2fsck counts non-contiguous only when the extent is non-adjacent to the previous extent.

What we may want to do though is to create some other statistic which is something like "file has more than one contiguous run of blocks and one or more contiguous runs of blocks is smaller than 512 blocks". This will take into account that for very large files small amounts of non-contiguousness is acceptable, although certainly not ideal. But if we report both number of non-contiguous files, and number of fragmented files, it might be a good way of reflecting this.

We really do need to improve the ext4's block allocator, though. What we have here is definitely that needs improving. Personally, I think free space fragmentation problem caused by small files should be higher priority, since although it isn't as blindly obvious by people running e2fsprogs, in the long run the free space fragmentation will cause files to get fragmented very badly when the filesystem ages and as it gets full.

- Ted

http://bugzilla.kernel.org/show_bug.cgi?id=13930

--- Comment #4 from Theodore Tso <[email protected]> 2009-08-08 01:30:24 --- There are so many extents because as discussed in the linux-ext4 mailing list thread I referenced above, when you write multiple large files close together in time, the large files get interleaved with each other.

"cp -R /cifs /ext4" doesn't call fsync() between writing each file, so the dirty pages for multiple files are left dirty in the page cache during the
copy. The VM page flush daemon doesn't write one file out completely, and
then another, but instead round-robins between different inodes. The ext4
delayed allocation code tries to work around this by trying to find adjacent dirty pages and then trying to do a large block allocation; but currently the ext4 multiblock allocator only tries to grab up to 8 megabytes at a time, to avoid spending too much CPU time in what might be a fruitless attempt to find that many contiguous free blocks.

It's a known bug, but fixing is a bit complicated. It's on our TODO list.

Configure bugmail: http://bugzilla.kernel.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching the assignee of the bug.

http://bugzilla.kernel.org/show_bug.cgi?id=13930

--- Comment #5 from Theodore Tso <[email protected]> 2009-08-10 12:04:13 ---
I did some more looking at this issue. The root cause is pdflush, which is
the daemon that starts forcing background writes when 10% of the available page
cache is dirty. It will write out a maximum of 1024 blocks per page, because
of a hard-coded limit in mm/page-writeback.c:

/*
* The maximum number of pages to writeout in a single bdflush/kupdate
* operation. We do this so we don't hold I_SYNC against an inode for
* enormous amounts of time, which would block a userspace task which has
* been forced to throttle against that inode. Also, the code reevaluates
* the dirty each time it has written this many pages.
*/
#define MAX_WRITEBACK_PAGES 1024

The means that background_writeout() in mm/page-writeback.c only calls ext4_da_writepages requesting a writeout of 1024 pages, which we can see if we put a trace on ext4_da_writepages after writing a very large file:

         pdflush-398   [000]  5743.853396: ext4_da_writepages: dev sdc1 ino 12
nr_t_write 1024 pages_skipped 0 range_start 0 range_end 0 nonblock
ing 1 for_kupdate 0 for_reclaim 0 for_writepages 1 range_cyclic 1
         pdflush-398   [000]  5743.858988: ext4_da_writepages_result: dev sdc1
ino 12 ret 0 pages_written 1024 pages_skipped 0 congestion 0 more_
io 0 no_nrwrite_index_update 0
         pdflush-398   [000]  5743.923578: ext4_da_writepages: dev sdc1 ino 12
nr_t_write 1024 pages_skipped 0 range_start 0 range_end 0 nonblock
ing 1 for_kupdate 0 for_reclaim 0 for_writepages 1 range_cyclic 1
         pdflush-398   [000]  5743.927562: ext4_da_writepages_result: dev sdc1

ino 12 ret 0 pages_written 1024 pages_skipped 0 congestion 0 more_ io 0 no_nrwrite_index_update 0

The ext4_da_writepages() function is therefore allocating 1024 blocks at a time, which the ext4 multiblock allocator is increasing to 2048 blocks (and sometimes 1024 blocks is allocated, and sometimes 2048 blocks is allocated), as we can see from /proc/fs/ext4/<dev>/mb_history:

1982 12 1/14336/1024@12288 1/14336/2048@12288
1/14336/2048@12288 1 0 0 0x0e20 M 0 0
1982 12 1/15360/1024@13312
1/15360/1024@13312
1982 12 1/16384/1024@14336 1/16384/2048@14336
1/16384/2048@14336 1 0 0 0x0e20 M 2048 8192
1982 12 1/17408/1024@15360
1/17408/1024@15360

If there are multiple large dirty files in the page cache, then pdflush will round-robin trying to write out the inodes, with the result that large files get interleaved in chunks of 4M (1024 pages) to 8M (2048), and larger chunks happen only when there is only pages from one inode left in memory.

Potential solutions in the next comment...

Configure bugmail: http://bugzilla.kernel.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching the assignee of the bug.

http://bugzilla.kernel.org/show_bug.cgi?id=13930

--- Comment #6 from Theodore Tso <[email protected]> 2009-08-10 13:11:32 --- There are a number of ways that we can increase the size of block allocation request made by ext4_da_writepages:

1) Increase MAX_WRITEBACK_PAGES, possibly on a per-filesystem basis.

The comment around MAX_WRITEBACK_PAGES indicates the problem is around blocking tasks that wait on I_SYNC, but it's not clear this is really a problem. Before I_SYNC was separated out from I_LOCK, this was clearly much more of an issue, but now the only time when a process waits for I_SYNC, as near as I can
tell, is when they are calling fsync() or otherwise forcing out the inode. So
I don't think it's going to be that big of a deal.

2) We can change ext4_da_writepages() to attempt to see if there are more dirty pages in the page cache beyond what had been requested to be written, and if so, we pass a hint to mballoc via an extension to the allocation_request structure so that additional blocks are allocated and reserved in the inode's preallocation structure.

3) Jens Axboe is working on a set of patches which create a separate pdflush thread for each block device (the per-bdi patches). I don't think there is a risk in increasing MAX_WRITEBACK_PAGES, but if there is still a concern, with the per-bdi patches, perhaps the per-bdi patches could be changed to prefer dirty inodes which are closed, and writing out complete inodes which have been closed, one at a time, instead of stopping after MAX_WRITEBACK_PAGES.

These changes should allow us to improve ext4's large file writeback to the point where it is allocating up to 32768 blocks at a time, instead of 1024 blocks at a time. At the moment the mballoc code isn't capable of allocating more than a block group's worth of blocks at a time, since it was written assuming that there was per block group metadata at the beginning of each block
group which prevented allocations from spanning block groups. So long term,
we may need to make further improvements to help assure sane allocations for really files > 128 megs --- although solution #3 might help this situation even without mballoc changes, since there would only be a single pdflush thread per bdi writing out large files.

Configure bugmail: http://bugzilla.kernel.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching the assignee of the bug.

http://bugzilla.kernel.org/show_bug.cgi?id=13930

Alan <[email protected]> changed:

What |Removed |Added
----------------------------------------------------------------------------

                 CC|                            |[email protected]
     Kernel Version|Linux version 2.6.31-rc5    |2.6.31-5(deb)
                   |(logik@LogikPC) (gcc        |
                   |version 4.3.3 (Debian       |
                   |4.3.3-15) ) #1 SMP PREEMPT  |
                   |Sat Aug 1 19:52:55 CEST     |
                   |2009                        |

Configure bugmail: http://bugzilla.kernel.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching the assignee of the bug.