linux-ext4 - Question on block group allocation

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-next>] [day] [month] [year] [list]

Date:	Thu, 23 Apr 2009 09:41:50 -0700
From:	Curt Wohlgemuth <curtw@...gle.com>
To:	ext4 development <linux-ext4@...r.kernel.org>
Subject: Question on block group allocation

Hi:

I'm seeing a performance problem on ext4 vs ext2, and in trying to
narrow it down, I've got a question about block allocation in ext4
that I'm having trouble figuring out.

The test in question just does random reads of several rather large
files (4.5GB and 10GB) in a single thread.  All files are created in
the top-level directory.  Looking into the block layout for the
various files, I'm struck by the wide separation of the extents in
some of the files.

As a simple example, I formatted/mounted a new ext4 partition with
default parameters (with the exception of "-O ^has_journal", but this
shouldn't make a difference); the FS has 5585 block groups of 4K
blocks.

Using dd, I created (in this order) two 4GB files and a 10GB file in
the mount directory.

The extent blocks are reasonably close together for the two 4GB files,
but the extents for the 10GB file show a huge gap, which seems to hurt
the random read performance pretty substantially.  Here's the output
from debugfs:

BLOCKS:
(IND):8396832, (0-106495):8282112-8388607,
(106496-399359):11241472-11534335, (399360-888831):20482048-20971519,
(888832-1116159):23889920-24117247, (1116160-1277951):71665664-
71827455, (1277952-1767423):78678016-79167487,
(1767424-2125823):102402048-102760447,
(2125824-2148351):102768672-102791199,
(2148352-2621439):102793216-103266303
TOTAL: 2621441

Note the gap between blocks 79167487 and 102402048.  I was lucky
enough to capture the mb_history from this 10GB create:

29109 14       735/30720/32758@...4112 735/30720/2048@...4112
735/30720/2048@...4112  1     0     0  1568  M     0     0
29109 14       736/0/32758@...6160     736/0/2048@...6160
2187/2048/2048@...6160  1     1     0  1568        0     0
29109 14       2187/4096/32758@...8208 2187/4096/2048@...8208
2187/4096/2048@...8208  1     0     0  1568  M     2048  4096

I've been staring at ext4_mb_regular_allocator() trying to understand
why an allocation with a goal block of 736 ends up with a best found
extent group of 2187, and I'm stuck -- at least without a lot of
printk messages.  It seems to me that we just cycle through the block
groups starting with the goal group until we find a group that fits.
Again, according to dumpe2fs, block groups 737, 738, 739, ... all have
32768 free blocks.  So why we end up with a best fit group of 2187 is
a mystery to me.

Can anybody give me an insight to what's happening here?

Thanks,
Curt
--
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