linux-kernel - Re: [PATCH] reiserfs: eliminate minimum window size for bitmap searching

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: <44EB28EC.50802@suse.com>
Date:	Tue, 22 Aug 2006 11:55:24 -0400
From:	Jeff Mahoney <jeffm@...e.com>
To:	David Masover <ninja@...phack.com>
Cc:	Andrew Morton <akpm@...l.org>, Linus Torvalds <torvalds@...l.org>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
	ReiserFS List <reiserfs-list@...esys.com>,
	Mike Benoit <ipso@...ppymail.ca>
Subject: Re: [PATCH] reiserfs: eliminate minimum window size for bitmap searching

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

David Masover wrote:
> Jeff Mahoney wrote:
>>  When a file system becomes fragmented (using MythTV, for example), the
>>  bigalloc window searching ends up causing huge performance problems. In
>>  a file system presented by a user experiencing this bug, the file system
>>  was 90% free, but no 32-block free windows existed on the entire file
>> system.
>>  This causes the allocator to scan the entire file system for each
>> 128k write
>>  before backing down to searching for individual blocks.
> 
> Question:  Would it be better to take that performance hit once, then
> cache the result for awhile?  If we can't find enough consecutive space,
> such space isn't likely to appear until a lot of space is freed or a
> repacker is run.

The problem is that finding the window isn't really a direct function of
free space, it's a function of fragmentation. You could have a 50% full
file system that still can't find a 32 block window by having every
other block used. I know it's an extremely unlikely case, but it
demonstrates the point perfectly.

>>  In the end, finding a contiguous window for all the blocks in a write is
>>  an advantageous special case, but one that can be found naturally when
>>  such a window exists anyway.
> 
> Hmm.  Ok, I don't understand how this works, so I'll shut up.

If the space after the end of the file has 32 or more blocks free, even
without the bigalloc behavior, those blocks will be used.

Also, I think the bigalloc behavior just ultimately ends up introducing
even more fragmentation on an already fragmented file system. It'll keep
contiguous chunks together, but those chunks can end up being spread all
over the disk.

- -Jeff

- --
Jeff Mahoney
SUSE Labs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

iD8DBQFE6yjsLPWxlyuTD7IRAuT0AJ9ssQafYPW+Gy/E/xN+LKCxamjycwCgqL6P
aUbgXdn+0+K3sJhWGBWtrno=
=NDyT
-----END PGP SIGNATURE-----
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/