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: <20110315171843.GI8120@thunk.org>
Date:	Tue, 15 Mar 2011 13:18:43 -0400
From:	Ted Ts'o <tytso@....edu>
To:	Rogier Wolff <R.E.Wolff@...Wizard.nl>
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 02:33:27PM +0100, Rogier Wolff wrote:
> 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.

It depends on your workload.  In the case of dpkg, everything fits in
cache (usually) so after the first operation this is no longer a
concern.  But all of the data blocks of /var/lib/dpkg/info/* is huge,
since not using a real database means that a 4k block is consumed for
300 bytes of data, so fitting all of the data blocks in memory
generally doesn't work, which is why the dpkg folks are sorting by
block number.

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

We do something else, which is we group all directory blocks together
at the beginning of each flex_bg.  This tends to reduce free space
fragmentation, and it helps to optimize for large files that are
bigger than a block group, and where you want to have contiguous
regions larger than a bg --- so breaking up the space every bg is not
a great idea.  Again, with general purpose file systems you can't just
optimize for one thing, and life is full of tradeoffs.

      	   	    	    	       	    - 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