linux-ext4 - Re: Question about ext4 extents and file fragmentation

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <a1dba5a8-ecdd-4618-0dc2-7cf4a67b0d40@gmail.com>
Date:   Thu, 21 Mar 2019 10:29:23 +0100
From:   Mikhail Morfikov <mmorfikov@...il.com>
To:     Theodore Ts'o <tytso@....edu>
Cc:     linux-ext4@...r.kernel.org
Subject: Re: Question about ext4 extents and file fragmentation

On 21/03/2019 04:18, Theodore Ts'o wrote:
> On Wed, Mar 20, 2019 at 11:44:19PM +0100, Mikhail Morfikov wrote:
>> When we have a big file on an ext4 partition, and filefrag shows
>> the following:
>>
>> filefrag -ve /bigfile
>> Filesystem type is: ef53
>> File size of /bigfile is 1439201280 (351368 blocks of 4096 bytes)
>>  ext:     logical_offset:        physical_offset: length:   expected: flags:
>>    0:        0..   32767:      34816..     67583:  32768:            
>>    1:    32768..   63487:      67584..     98303:  30720:            
>>    2:    63488..   96255:     100352..    133119:  32768:      98304:
>>    3:    96256..  126975:     133120..    163839:  30720:            
>>    4:   126976..  159743:     165888..    198655:  32768:     163840:
>>    5:   159744..  190463:     198656..    229375:  30720:            
>>    6:   190464..  223231:     231424..    264191:  32768:     229376:
>>    7:   223232..  253951:     264192..    294911:  30720:            
>>    8:   253952..  286719:     296960..    329727:  32768:     294912:
>>    9:   286720..  319487:     329728..    362495:  32768:            
>>   10:   319488..  351367:     362496..    394375:  31880:             last,eof
>> /bigfile: 5 extents found
>>
>> 1. How many fragments does this file really have? 11 or 5? 
>> 2. Should the extents 0 and 1 be treated as one fragment or two 
>>    separate ones? I know they could be one from the human 
>>    perspective, but is it really one for ext4 filesystem?
> 
> They are encoded as two separate physical extents on disk.  Logically,
> extents 0, 1, and 2 are contiguous regions on idks.So 5 fragments then?

>> 3. What does actually happen during the read in the case of 
>>    some HDD and its magnetic heads? If the head finishes reading 
>>    the whole extent (ext 0), will it be able to read the data of 
>>    the next extent (ext 1) without any delays like in the case of
>>    raw read (for instance dd if=/dev/sda ...), or will it be 
>>    delayed because of the filesystem layer, and the head will 
>>    have to spend some time to be positioned again in order to 
>>    read the next extent?
> 
> The delay won't be because of the file system layer, as the
> information about these first three extents will all be stored on the
> same block on disk.  In addition, ext4 has an in-memory "extent cache"
> which stores the logical->physical block mapping, and in memory, it
> will be stored as a single entry in the extent cache.
> 
> It takes *time* to read 128 megabytes (32768 4k blocks), and from a
> hard drive perspective, you are doing a streaming sequential read, how
> the file system metadata is stored is not going to be the limiting
> factor.  In fact, it's likely that they won't be issued to the hard
> drive as a single I/O request anyway.  But that doesn't matter; the
> hard drive has an I/O request queue, and so the right thing will
> happen.
> 

Yes, I know that many things can happen during the 128M read. But wecan assume that we have some simplified environment, where we have 
only one disk, one file we want to read at the moment, and we have 
time to do it without any external interferences.

If I understood correctly, as long as the extents reside on a contiguous 
region, they will be read sequentially without any delays, right? So if 
the file in question was one big contiguous region, would it be read 
sequentially from the beginning of the file to its end? 

Also I have a question concerning the following sentence[1]: 
  "When there are more than four extents to a file, the rest of the 
  extents are indexed in a tree." 
Does this mean that only four extents can be read sequentially in a 
file that have only contiguous blocks of data, or because of the 
extent cache, the whole file can be read sequentially anyway?

[1] https://en.wikipedia.org/wiki/Ext4#Features




Download attachment "signature.asc" of type "application/pgp-signature" (834 bytes)