linux-ext4 - Re: ext4: first write to large ext3 filesystem takes 96 seconds

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]

Date:	Mon, 7 Jul 2014 23:54:05 -0400
From:	Theodore Ts'o <tytso@....edu>
To:	Benjamin LaHaise <bcrl@...ck.org>
Cc:	linux-ext4@...r.kernel.org
Subject: Re: ext4: first write to large ext3 filesystem takes 96 seconds

On Mon, Jul 07, 2014 at 09:35:11PM -0400, Benjamin LaHaise wrote:
> 
> Sure -- I put a copy at http://www.kvack.org/~bcrl/mb_groups as it's a bit 
> too big for the mailing list.  The filesystem in question has a couple of 
> 11GB files on it, with the remainder of the space being taken up by files 
> 7200016 bytes in size.  

Right, so looking at mb_groups we see a bunch of the problems.  There
are a large number block groups which look like this:

#group: free  frags first [ 2^0   2^1   2^2   2^3   2^4   2^5   2^6   2^7   2^8   2^9   2^10  2^11  2^12  2^13  ]
#288  : 1540  7     13056 [ 0     0     1     0     0     0     0     0     6     0     0     0     0     0     ]

It would be very interesting to see what allocation pattern resulted
in so many block groups with this layout.  Before we read in
allocation bitmap, all we know from the block group descriptors is
that there are 1540 free blocks.  What we don't know is that they are
broken up into 6 256 block free regions, plus a 4 block region.

If we try to allocate a 1024 block region, we'll end up searching a
large number of these block groups before find one which is suitable.

Or there is a large collection of block groups that look like this:

#834  : 4900  39    514   [ 0     20    5     5     16    6     4     8     6     1     1     0     0     0     ]

Similarly, we could try to look for a contiguous 2048 range, but even
though there is 4900 blocks available, we can't tell the difference
between something a free block layout which looks like like the above,
versus one that looks like this:

#834  : 4900  39    514   [ 0      6    0     1     3    5     1     4     0     0     0     2     0     0     ]

We could try going straight for the largely empty block groups, but
that's more likely to fragment the file system more quickly, and then
once those largely empty block groups are partially used, then we'll
end up taking a long time while we scan all of the block groups.

       	      	     	  	   	- 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