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: <7A57B033-E270-4DE1-86B9-F06B4BF9DA20@mit.edu>
Date:	Tue, 15 Mar 2011 07:38:29 -0400
From:	Theodore Tso <tytso@....EDU>
To:	Ric Wheeler <ricwheeler@...il.com>
Cc:	Florian Weimer <fweimer@....de>, Eric Sandeen <sandeen@...hat.com>,
	Phillip Susi <psusi@....rr.com>,
	"linux-ext4@...r.kernel.org" <linux-ext4@...r.kernel.org>
Subject: Re: Large directories and poor order correlation

On Mar 15, 2011, at 7:23 AM, Ric Wheeler wrote:
> 
> I have tested both sorting techniques with very large directories.
> 
> Most of the gain came with the simple sorting by inode number, but of course this relies on the file system allocation policy having a correlation between the inode numbers and layout (i.e., higher inode number correspond to higher block numbers).

That's not just a matter of file system allocation policy, but how fragmented the free space is as far 
as inode numbers and block numbers might be.  (Especially in the block group where /var/lib/dpkg/info
lives, on Debian systems.  That's because that directory is (ab)used as a database, with lots of files
added and deleted, so over time it's pretty much inevitable that any link between directory order,
inode numbers, and block numbers, would become weaker and weaker over time.  Fortunately the
overall database tends to fit into the dentry, inode, and page caches after the first dpkg operation...)

> Note that you can get the inode number used in this sorting without doing any stat calls.

Sure.  And in the worst case, you would sort based on the inode number so that when you call
open/FI[BE]MAP, the disk isn't seeking all over the place when you read in the inode structure...
Then you need to sort by block numbers, and assuming that you have enough memory that
all of /var/lib/dpkg/info/* fits in the inode cache, you will minimize seeking while you read the
blocks into memory.

-- Ted

--
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