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

From: David Masover
Date: Tue Aug 22 2006 - 16:23:11 EST

Jeff Mahoney wrote:
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
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.

Maybe, but it's still not a counterpoint. No matter how fragmented a filesystem is, freeing space can open up contiguous space, whereas if space is not freed, you won't open up contiguous space.

Thus, if your FS is 50% full and 100% fragmented, then you wait till space is freed, because if nothing happens, or if more space is filled in, you'll have the same problem at 60% than you did at 50%. If, however, you're at 60% full, and 10% of the space is freed, then it's fairly unlikely that you still don't have contiguous space, and it's worth it to scan once more at 50%, and again if it then drops to 40%.

So, if your FS is 90% full and space is being freed, I'd think it would be worth it to scan again at 80%, 70%, and so on. I'd also imagine it would do little or nothing to constantly monitor an FS that stays mostly full -- maybe give it a certain amount of time, but if we're repacking anyway, just wait for a repacker run. It seems very unlikely that between repacker runs, activity between 86% and 94% would open up contiguous space.

It's still not a direct function of freed space (as opposed to free space), but it starts to look better.

I'm not endorsing one way or the other without benchmarks, though.

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.

For what behavior -- appending?

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.

This sounds like the NTFS strategy, which was basically to allow all hell to break loose -- above a certain chunk size. Keep chunks of a certain size contiguous, and you limit the number of seeks by quite a lot.
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at