linux-ext4 - Re: Large directories and poor order correlation

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: <4D7E8005.4030201@cfl.rr.com>
Date:	Mon, 14 Mar 2011 16:52:21 -0400
From:	Phillip Susi <psusi@....rr.com>
To:	Eric Sandeen <sandeen@...hat.com>
CC:	"linux-ext4@...r.kernel.org" <linux-ext4@...r.kernel.org>
Subject: Re: Large directories and poor order correlation

On 3/14/2011 4:37 PM, Eric Sandeen wrote:
> On 3/14/11 3:24 PM, Phillip Susi wrote:
>> Shouldn't copying or extracting or otherwise populating a large
>> directory of many small files at the same time result in a strong
>> correlation between the order the names appear in the directory, and the
>> order their data blocks are stored on disk, and thus, read performance
>> should not be negatively impacted by fragmentation?
> 
> No, because htree (dir_index) dirs returns names in hash-value
> order, not inode number order.  i.e. "at random."

I thought that the htree was used to look up names, but the normal
directory was used to enumerate them?  In other words, the htree speeds
up opening a single file, but slows down traversing the entire
directory, so should not be used there.

Also isn't htree only enabled for large directories?  I still see crummy
correlation for small ( < 100 files, even one with only 8 entries )
directories.

It seems unreasonable to ask applications to read all directory entries,
then sort them by inode number to achieve reasonable performance.  This
seems like something the fs should be doing.

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