Re: [PATCH] Clustering indirect blocks in Ext3

Daniel Phillips
2008-01-12T06:05:35Z

On Friday 11 January 2008 16:04, Andrew Morton wrote:
> It needs to be reviewed. In exhaustive detail. Few people can do
> that and fewer are inclined to do so.

Agreed, there just have to be a few bugs in this many lines of code.
I spent a couple of hours going through it, not really looking at the
algorithms but just the superficial details. I only found minor nits,
and not many of those.

For example, I do not like to see "if (free_blocks == 0)" written as"if
(free_blocks <= 0)" in an attempt to increase robustness. What it
actually does is make the effect of an error more subtle, or
even "corrects" it. Firmly in the niggle category.

I checked the locking of sbi->bginfo and didn't see a flaw, good.

I see a missing KERN_INFO added to a printk, it technically counts as an
unrelated change but oh well.

Stylistically this new code is hard to tell apart from the incumbent
code, except for being more heavily commented. I wish all kernel code
was written this clearly.

At this point I will run away in favor of for-real Ext3 hackers (you
know who you are:-)

> I went to merge it so it could get some testing while we await review
> but the patch has all its tabs replaced with spaces, is seriously
> wordwrapped and has random newlines added to it. Please fix email
> client and resend (offlist is OK if it is unaltered).

Odd, the original post has tabs and the updated one does not, though the
client seems to be kmail in both cases.

> We should have a think about which workloads are most likely to be
> adversely affected by this change.

I was just rolling up my sleeves to construct the nasty sequential case
where the head keeps seeking back to the center of the group after
picking up each 4 MB of doubly indexed data when I realized that even
the most simple minded disk cache makes this case a non-issue. The
drive will most likely suck a full track (roughly .5 MB) or big chunk
thereof into cache the first time it seeks to the index cluster, thus
having a whole group of double index blocks in cache and then will
proceed to chew happily and linearly through the data blocks.
It seems like placing those second level index blocks all together
really helps this case. Hmm, how to break it.

How about having a disk full of 100 MB files and skipping all over the
disk randomly reading one block each time. That will fill the disk
cache, and each random read then requires seeking to two places that
were hopefully close together without index node clustering, and now
will be an average of 32 MB apart. Each of these "extra" seeks costs a
couple of ms worth of head travel plus average rotational latency of 4
ms or so, for a total 6 ms. However, even with a perfect non-clustered
layout, the index mode will still be an average of 2 MB away from the
data block, so the rotational latency is still incurred and only the
head travel is a little less, say 1 ms less. So the "extra" seek time
for clustered is 6 ms vs 5 ms for non-clustered. Add in 8 ms for the
long random seek and we have 14 ms vs 13 ms, or about 8% difference.
Only a small regression there, and I tried hard. Barring mistakes in
my estimates the sequential improvement above is large while the
regression for the nasty random construction is small.

Maybe somebody else will have better luck breaking it.

Regards,

Daniel