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: <20110315133327.GG22577@bitwizard.nl>
Date:	Tue, 15 Mar 2011 14:33:27 +0100
From:	Rogier Wolff <R.E.Wolff@...Wizard.nl>
To:	Theodore Tso <tytso@....EDU>
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 Tue, Mar 15, 2011 at 07:06:34AM -0400, Theodore Tso wrote:
> So in an absolute cold cache situations, what I'd recommend is
> readdir, sort by inode, FIEMAP, sort by block, and then read in the
> dpkg files.  Of course an RPM partisan might say, "it would help if
> you guys had used a real database instead of ab(using) the file
> system.  And then the dpkg guys could complain about what happens
> when RPM has to deal with corrupted rpm database, and how this
> allows dpkg to use shell scripts to access their package
> information.  Life is full of tradeoffs.

IMHO, the most important part is "up to and including the stat". It
should be possible to get the directory, and inode info all inside the
same "16Mb" part of the disk. This would result in (after a few seeks)
the rest of the accesses coming from the disk's cache. 

This would mean that you should allocate directory blocks from the end
PREVIOUS block group.... 

	Roger. 

-- 
** R.E.Wolff@...Wizard.nl ** http://www.BitWizard.nl/ ** +31-15-2600998 **
**    Delftechpark 26 2628 XH  Delft, The Netherlands. KVK: 27239233    **
*-- BitWizard writes Linux device drivers for any device you may have! --*
Q: It doesn't work. A: Look buddy, doesn't work is an ambiguous statement. 
Does it sit on the couch all day? Is it unemployed? Please be specific! 
Define 'it' and what it isn't doing. --------- Adapted from lxrbot FAQ
--
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