LinuxLists.cc - [PATCH] e2freefrag utility

[permalink] [raw]

Subject: Re: [PATCH] e2freefrag utility

On Mon, Jul 20, 2009 at 06:17:50PM -0600, Andreas Dilger wrote:
> Attached is the e2freefrag tool. It grabs the block bitmaps, creates
> buddy bitmaps from them and displays the total/free chunks (default
> 1MB chunk size), and a histogram of free space.
>
> It could probably be enhanced to print the chunk sizes based on the
> RAID chunk size stored in the superblock, but I just thought of that
> this minute...

Thanks, checked in with some minor changes to fix some printf
warnings.

Here's the output on my root filesystem (which has been in use since
February):

Device: /dev/ssd/root
Blocksize: 4096 bytes
Total blocks: 18350080
Free blocks: 10774142 (58.7%)

Chunksize: 1048576 bytes (256 blocks)
Total chunks: 71681
Free chunks: 21792 (30.4%)

Min free chunk: 4 KB
Max free chunk: 568232 KB
Avg free chunk: 184 KB

HISTOGRAM OF FREE CHUNK SIZES:
Chunk Size Range : Free chunks
4K... 8K- : 35005
8K... 16K- : 33639
16K... 32K- : 31419
32K... 64K- : 33953
64K... 128K- : 26397
128K... 256K- : 7314
256K... 512K- : 1855
512K... 1024K- : 1612
1M... 2M- : 1160
2M... 4M- : 567
4M... 8M- : 303
8M... 16M- : 106
16M... 32M- : 40
32M... 64M- : 51
64M... 128M- : 123
128M... 256M- : 8
512M... 1024M- : 1

Yeah.... pretty fragmented. :-(

- Ted

2009-07-23 04:59:48

[permalink] [raw]

Subject: Re: [PATCH] e2freefrag utility

Theodore Tso wrote:
...

> Here's the output on my root filesystem (which has been in use since
> February):
>
> Device: /dev/ssd/root
> Blocksize: 4096 bytes
> Total blocks: 18350080
> Free blocks: 10774142 (58.7%)
>
> Chunksize: 1048576 bytes (256 blocks)
> Total chunks: 71681
> Free chunks: 21792 (30.4%)
>
> Min free chunk: 4 KB
> Max free chunk: 568232 KB
> Avg free chunk: 184 KB
>
> HISTOGRAM OF FREE CHUNK SIZES:
> Chunk Size Range : Free chunks
> 4K... 8K- : 35005
> 8K... 16K- : 33639
> 16K... 32K- : 31419
> 32K... 64K- : 33953
> 64K... 128K- : 26397
> 128K... 256K- : 7314
> 256K... 512K- : 1855
> 512K... 1024K- : 1612
> 1M... 2M- : 1160
> 2M... 4M- : 567
> 4M... 8M- : 303
> 8M... 16M- : 106
> 16M... 32M- : 40
> 32M... 64M- : 51
> 64M... 128M- : 123
> 128M... 256M- : 8
> 512M... 1024M- : 1
>
> Yeah.... pretty fragmented. :-(
>

Just for comparison, here's a 30G xfs root that has run for a year or
two, currently about 70% full:

xfs_db> freesp -s
from to extents blocks pct
1 1 1849 1849 0.08
2 3 1383 3293 0.14
4 7 1034 5429 0.23
8 15 1061 12260 0.53
16 31 641 13261 0.57
32 63 355 15601 0.67
64 127 221 19940 0.86
128 255 195 35841 1.54
256 511 173 63066 2.71
512 1023 122 89824 3.86
1024 2047 51 70032 3.01
2048 4095 22 60982 2.62
4096 8191 20 116580 5.01
8192 16383 10 109896 4.72
16384 32767 7 152026 6.53
32768 65535 4 206283 8.87
65536 131071 3 285744 12.28
262144 524287 1 509811 21.91
524288 1048575 1 554838 23.85
total free extents 7153
total free blocks 2326556
average free extent size 325.256

from...to units are in 4k blocks.

Maybe the fancy ext4 defragger will have a good second use case in
cleaning up some of that freespace fragmentation.

-Eric

2009-07-23 13:46:08

[permalink] [raw]

Subject: How to fix up mballoc

So I started looking to see how we might be able to improve mballoc to
avoid freespace fragmentation, and I came up with the following high
level design. Does this look sane? Have I overlooked anything?

1) In ext4_mb_normalize_request(), if the inode that we are allocating
does not have any open file descriptors for write (i.e., it's already
closed and we're allocating via delalloc) _and_ the inode was
previously opened with O_CREAT and without O_APPEND (checked via a
flag in EXT4_I(inode)), then do not normalize the size to a power of
two, but rather to the filesystem blocksize.

The idea here is that we should be trying to find an exact fit, since
most of the time (except for log files, which get appended; hence the
O_CREAT && !O_APPEND test) once a file is written, that is probably
the final size for the file. So normalizing the size for the
preallocation area to a power of two will be counterproductive for
most files.

2) If the there has been less than X files opened in Y jiffies the
parent directory (using the dentry path used to open the file), then
do not set EXT4_MB_HINT_GROUP_ALLOC in ext4_mb_group_or_file(). We
can simulate this for without creating this patch to test #1 by
setting mb_stream_request to 0 (which should completely disable group
preallocation).

- Ted

2009-07-23 17:08:37

[permalink] [raw]

Subject: Re: [PATCH] e2freefrag utility

On Jul 22, 2009 23:59 -0500, Eric Sandeen wrote:
> Theodore Tso wrote:
> > Here's the output on my root filesystem (which has been in use since
> > February):
> >
> > Total chunks: 71681
> > Free chunks: 21792 (30.4%)
> >
> > Min free chunk: 4 KB
> > Max free chunk: 568232 KB
> > Avg free chunk: 184 KB
> >
> > HISTOGRAM OF FREE CHUNK SIZES:
> > Chunk Size Range : Free chunks
> > 4K... 8K- : 35005
> > 8K... 16K- : 33639
:
:
> > 128M... 256M- : 8
> > 512M... 1024M- : 1
> >
> > Yeah.... pretty fragmented. :-(
> >
>
>
> Just for comparison, here's a 30G xfs root that has run for a year or
> two, currently about 70% full:
>
> xfs_db> freesp -s
> from to extents blocks pct
> 1 1 1849 1849 0.08
> 2 3 1383 3293 0.14
:
:
> 262144 524287 1 509811 21.91
> 524288 1048575 1 554838 23.85
> total free extents 7153
> total free blocks 2326556
> average free extent size 325.256

I like the printing of the total blocks in each section and the
percent of blocks... Attached is an incremental patch that adds
the same to e2freefrag.

Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.

Attachments:

(No filename) (1.23 kB)
e2freefrag-pct.diff (4.67 kB)
Download all attachments

2009-07-23 17:19:28

[permalink] [raw]

Subject: Re: [PATCH] e2freefrag utility

Andreas Dilger wrote:

> I like the printing of the total blocks in each section and the
> percent of blocks... Attached is an incremental patch that adds
> the same to e2freefrag.

Thanks, I was going to suggest that :)

-Eric

2009-07-23 17:43:53

[permalink] [raw]

Subject: Re: How to fix up mballoc

Theodore Tso wrote:
> So I started looking to see how we might be able to improve mballoc to
> avoid freespace fragmentation, and I came up with the following high
> level design. Does this look sane? Have I overlooked anything?
>
> 1) In ext4_mb_normalize_request(), if the inode that we are allocating
> does not have any open file descriptors for write (i.e., it's already
> closed and we're allocating via delalloc) _and_ the inode was
> previously opened with O_CREAT and without O_APPEND (checked via a
> flag in EXT4_I(inode)), then do not normalize the size to a power of
> two, but rather to the filesystem blocksize.
>
> The idea here is that we should be trying to find an exact fit, since
> most of the time (except for log files, which get appended; hence the
> O_CREAT && !O_APPEND test) once a file is written, that is probably
> the final size for the file. So normalizing the size for the
> preallocation area to a power of two will be counterproductive for
> most files.

I'm sort of woefully ignorant of a lot of the mballoc stuff.

When you say once a file is written that's probably the final size... do
you mean when writes are done and it's closed, or when the first write
to the file is complete?

I think an awful lot of normal cases write to a file in sub-file-sized
chunks (think mp3 or flac encoding, file downloading, etc).

Also, I get the !O_APPEND test, but is O_CREAT necessary? I wonder how
much of a hint that really gives us.

> 2) If the there has been less than X files opened in Y jiffies the
> parent directory (using the dentry path used to open the file), then
> do not set EXT4_MB_HINT_GROUP_ALLOC in ext4_mb_group_or_file(). We
> can simulate this for without creating this patch to test #1 by
> setting mb_stream_request to 0 (which should completely disable group
> preallocation).

Hm have to try hard to parse that ;) But that sounds reasonable I think.

I'm talking to the Fedora infrastructure folks to see if there's a way
to recreate snapshots of, say, the F10 repos from initial release to
today, to be able to sort of fast-forward root filesystem updates. It'd
be a nice way to do accelerated aging tests for any changes we make, at
least for one usecase ...

-Eric

> - Ted

2009-07-23 17:52:00

by Mingming Cao

[permalink] [raw]

Subject: Re: How to fix up mballoc

Theodore Tso wrote:
> So I started looking to see how we might be able to improve mballoc to
> avoid freespace fragmentation, and I came up with the following high
> level design. Does this look sane? Have I overlooked anything?
>
> 1) In ext4_mb_normalize_request(), if the inode that we are allocating
> does not have any open file descriptors for write (i.e., it's already
> closed and we're allocating via delalloc) _and_ the inode was
> previously opened with O_CREAT and without O_APPEND (checked via a
> flag in EXT4_I(inode)), then do not normalize the size to a power of
> two, but rather to the filesystem blocksize.
>
> The idea here is that we should be trying to find an exact fit, since
> most of the time (except for log files, which get appended; hence the
> O_CREAT && !O_APPEND test) once a file is written, that is probably
> the final size for the file. So normalizing the size for the
> preallocation area to a power of two will be counterproductive for
> most files.
>
>
I am trying to understand what user cases prefer normalize allocation
request size? If they are uncommon cases, perhaps
we should disable the normalize the allocation size disabled by default,
unless the apps opens the files with O_APPEND?
> 2) If the there has been less than X files opened in Y jiffies the
> parent directory (using the dentry path used to open the file), then
> do not set EXT4_MB_HINT_GROUP_ALLOC in ext4_mb_group_or_file(). We
> can simulate this for without creating this patch to test #1 by
> setting mb_stream_request to 0 (which should completely disable group
> preallocation).
>
> - Ted
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
>

2009-07-24 00:23:28

[permalink] [raw]

Subject: Re: How to fix up mballoc

On Thu, Jul 23, 2009 at 12:43:47PM -0500, Eric Sandeen wrote:
> > 1) In ext4_mb_normalize_request(), if the inode that we are allocating
> > does not have any open file descriptors for write (i.e., it's already
> > closed and we're allocating via delalloc) _and_ the inode was
> > previously opened with O_CREAT and without O_APPEND (checked via a
> > flag in EXT4_I(inode)), then do not normalize the size to a power of
> > two, but rather to the filesystem blocksize.
>
> I'm sort of woefully ignorant of a lot of the mballoc stuff.
>
> When you say once a file is written that's probably the final size... do
> you mean when writes are done and it's closed, or when the first write
> to the file is complete?
>
> I think an awful lot of normal cases write to a file in sub-file-sized
> chunks (think mp3 or flac encoding, file downloading, etc).

I meant when the writes are done and the files are closed; hence my
proposal that we do this do #1 above only if there are no open file
descriptors for write. That is, if the file can be written and closed
by the userspace process before any delayed allocation blocks are
attempted to be written by the filesystem, we can probably safely
assume that the file won't grown in size later on.

> Also, I get the !O_APPEND test, but is O_CREAT necessary? I wonder how
> much of a hint that really gives us.

Well, it probably should be O_CREAT || O_TRUNC. The basic idea here is
to distinguish between a file which gets appended to via syslog, or
via a mail delivery program that writes 4k of data to the end of a
mail spool file. In some cases, such as the mail delivery program, it
might not use O_APPEND, but instead it might lock the file, seek to
end of the file, and then right the 4k worth of e-mail. So if the
file wasn't freshly created (or truncated) at the last open, maybe we
should use a more aggressive preallocation --- and in the case of
/var/mail spool delivery, perhaps the preallocation should persist
beyond the file getting closed. (In the future we might want to have
some hueristics where if we notice that the pattern of file writes is
a repeated open, write-causing-block-allocation, close, maybe we
should do some kind of block reservation style scheme while the
filesystem is mounted and the inode stays in the inode cache.)

- Ted

2009-07-24 00:43:39

[permalink] [raw]

Subject: Re: How to fix up mballoc

On Thu, Jul 23, 2009 at 10:51:58AM -0700, Mingming Cao wrote:
> I am trying to understand what user cases prefer normalize allocation
> request size? If they are uncommon cases, perhaps
> we should disable the normalize the allocation size disabled by default,
> unless the apps opens the files with O_APPEND?

The case where we would want to round the allocation size up would be
if we are writing a large file (say, like a large mp3 or mpeg4 file),
which takes a while for the audio/video encoder to write out the
blocks. In that case, doing file-based preallocation is a good thing.

Normally, if we are doing block allocations for files greater than 16
blocks (i.e, 64k), we use file-based preallocation. Otherwise we use
block group allocations. The problem with using block group
allocations is that way it works is that first time we try to allocate
out of a block group, we try to find a free extent which is 512 blocks
long. If we can't find a free extent which is 512 blocks long, we'll
try another block group. Hence, for small files, once a block group
gets fragmented to the point where there isn't a free chunk which is
512 blocks long, we'll try to find another block group --- even if
that means finding another block group far, FAR away from the block
group where the directory is contained.

Worse yet, if we unmount and remount the filesystem, we forget the
fact that we were using a particular (now-partially filled)
preallocation group, so the next time we try to allocate space for a
small file, we will find *another* free 512 block chunk to allocate
small files. Given that there is 32,768 blocks in block group, after
64 interations of "mount, write one 4k file in a directory, unmount",
that block group will have 64 files, each separated by 511 blocks, and
that block group will no longer have any free 512 chunks for block
allocations. (And given that the block preallocation is per-CPU, it
becomes even worse on an SMP system.)

Put this baldly, it may be that we need to do a fundamental rethink on
how we do per-cpu, per-blockgroup preallocations for small files.
Maybe instead of trying to find a 512 extent which is completely full,
we should instead be looking for a 512 extent which has at least
mb_stream_req free blocks (i.e. by default 16 free blocks).

- Ted

2009-07-24 02:18:51

[permalink] [raw]

Subject: Re: How to fix up mballoc

Theodore Tso wrote:
> On Thu, Jul 23, 2009 at 12:43:47PM -0500, Eric Sandeen wrote:
>>> 1) In ext4_mb_normalize_request(), if the inode that we are allocating
>>> does not have any open file descriptors for write (i.e., it's already
>>> closed and we're allocating via delalloc) _and_ the inode was
>>> previously opened with O_CREAT and without O_APPEND (checked via a
>>> flag in EXT4_I(inode)), then do not normalize the size to a power of
>>> two, but rather to the filesystem blocksize.
>> I'm sort of woefully ignorant of a lot of the mballoc stuff.
>>
>> When you say once a file is written that's probably the final size... do
>> you mean when writes are done and it's closed, or when the first write
>> to the file is complete?
>>
>> I think an awful lot of normal cases write to a file in sub-file-sized
>> chunks (think mp3 or flac encoding, file downloading, etc).
>
> I meant when the writes are done and the files are closed; hence my
> proposal that we do this do #1 above only if there are no open file
> descriptors for write. That is, if the file can be written and closed
> by the userspace process before any delayed allocation blocks are
> attempted to be written by the filesystem, we can probably safely
> assume that the file won't grown in size later on.

Ah, ok. Sorry, I misunderstood. Yep, that seems reasonable.

It should probably get tested with workloads like video transcoding,
where there will be incremental writes that span many minutes or hours.

>> Also, I get the !O_APPEND test, but is O_CREAT necessary? I wonder how
>> much of a hint that really gives us.
>
> Well, it probably should be O_CREAT || O_TRUNC. The basic idea here is
> to distinguish between a file which gets appended to via syslog, or
> via a mail delivery program that writes 4k of data to the end of a
> mail spool file. In some cases, such as the mail delivery program, it
> might not use O_APPEND, but instead it might lock the file, seek to
> end of the file, and then right the 4k worth of e-mail. So if the
> file wasn't freshly created (or truncated) at the last open, maybe we
> should use a more aggressive preallocation --- and in the case of
> /var/mail spool delivery, perhaps the preallocation should persist
> beyond the file getting closed. (In the future we might want to have
> some hueristics where if we notice that the pattern of file writes is
> a repeated open, write-causing-block-allocation, close, maybe we
> should do some kind of block reservation style scheme while the
> filesystem is mounted and the inode stays in the inode cache.)

sounds fancy ;)

-Eric

> - Ted

2009-07-24 02:26:23

[permalink] [raw]

Subject: Re: How to fix up mballoc

Eric Sandeen wrote:
> Theodore Tso wrote:
>> On Thu, Jul 23, 2009 at 12:43:47PM -0500, Eric Sandeen wrote:
>>>> 1) In ext4_mb_normalize_request(), if the inode that we are allocating
>>>> does not have any open file descriptors for write (i.e., it's already
>>>> closed and we're allocating via delalloc) _and_ the inode was
>>>> previously opened with O_CREAT and without O_APPEND (checked via a
>>>> flag in EXT4_I(inode)), then do not normalize the size to a power of
>>>> two, but rather to the filesystem blocksize.
>>> I'm sort of woefully ignorant of a lot of the mballoc stuff.
>>>
>>> When you say once a file is written that's probably the final size... do
>>> you mean when writes are done and it's closed, or when the first write
>>> to the file is complete?
>>>
>>> I think an awful lot of normal cases write to a file in sub-file-sized
>>> chunks (think mp3 or flac encoding, file downloading, etc).
>> I meant when the writes are done and the files are closed; hence my
>> proposal that we do this do #1 above only if there are no open file
>> descriptors for write. That is, if the file can be written and closed
>> by the userspace process before any delayed allocation blocks are
>> attempted to be written by the filesystem, we can probably safely
>> assume that the file won't grown in size later on.
>
> Ah, ok. Sorry, I misunderstood. Yep, that seems reasonable.
>
> It should probably get tested with workloads like video transcoding,
> where there will be incremental writes that span many minutes or hours.

Ugh right after I sent this I think I'm finally making sense of it. :)
In that case, come allocation time there =would= be file descriptors
open, and we'd go back to the old method of normalizing the allocation.
You're just talking about changing things where an entire series of
file writes have come & gone, everything is closed & done, and -now-
we're allocating.

Sorry for being slow. :)

-Eric

2009-07-24 02:31:24

[permalink] [raw]

Subject: Re: How to fix up mballoc

On Jul 23, 2009 20:23 -0400, Theodore Ts'o wrote:
> On Thu, Jul 23, 2009 at 12:43:47PM -0500, Eric Sandeen wrote:
> > > 1) In ext4_mb_normalize_request(), if the inode that we are allocating
> > > does not have any open file descriptors for write (i.e., it's already
> > > closed and we're allocating via delalloc) _and_ the inode was
> > > previously opened with O_CREAT and without O_APPEND (checked via a
> > > flag in EXT4_I(inode)), then do not normalize the size to a power of
> > > two, but rather to the filesystem blocksize.
> >
> > I'm sort of woefully ignorant of a lot of the mballoc stuff.
> >
> > When you say once a file is written that's probably the final size... do
> > you mean when writes are done and it's closed, or when the first write
> > to the file is complete?
> >
> > I think an awful lot of normal cases write to a file in sub-file-sized
> > chunks (think mp3 or flac encoding, file downloading, etc).
>
> I meant when the writes are done and the files are closed; hence my
> proposal that we do this do #1 above only if there are no open file
> descriptors for write. That is, if the file can be written and closed
> by the userspace process before any delayed allocation blocks are
> attempted to be written by the filesystem, we can probably safely
> assume that the file won't grown in size later on.

Right, this is a reasonable default I think.

> > Also, I get the !O_APPEND test, but is O_CREAT necessary? I wonder how
> > much of a hint that really gives us.
>
> Well, it probably should be O_CREAT || O_TRUNC. The basic idea here is
> to distinguish between a file which gets appended to via syslog, or
> via a mail delivery program that writes 4k of data to the end of a
> mail spool file. In some cases, such as the mail delivery program, it
> might not use O_APPEND, but instead it might lock the file, seek to
> end of the file, and then right the 4k worth of e-mail. So if the
> file wasn't freshly created (or truncated) at the last open, maybe we
> should use a more aggressive preallocation --- and in the case of
> /var/mail spool delivery, perhaps the preallocation should persist
> beyond the file getting closed. (In the future we might want to have
> some hueristics where if we notice that the pattern of file writes is
> a repeated open, write-causing-block-allocation, close, maybe we
> should do some kind of block reservation style scheme while the
> filesystem is mounted and the inode stays in the inode cache.)

I think you are on the right track with the !O_TRUNC check. Namely,
any file which is a non-zero size and gets an extending write at a
non-zero offset should probably get some persistent preallocation
(fallocate).

Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.

2009-07-24 22:33:13

[permalink] [raw]

Subject: Re: [PATCH] e2freefrag utility

On Thu, Jul 23, 2009 at 11:07:59AM -0600, Andreas Dilger wrote:
>
> I like the printing of the total blocks in each section and the
> percent of blocks... Attached is an incremental patch that adds
> the same to e2freefrag.

Thanks, applied.

One question --- right now the chunksize (as specified by -c) only
affects these lines printed by e2freefrag, right?

Chunksize: 1048576 bytes (256 blocks)
Total chunks: 71681
Free chunks: 21657 (30.2%)

They are a little confusing since "chunk" as used here is different
from "chunk" used in the next part of the output:

Min free chunk: 4 KB
Max free chunk: 568232 KB
Avg free chunk: 188 KB

How useful is it to print the "total chunks / free chunks" in the
general case? I'm guessing this relates to Lutsre's chunking and
chunksize? Would it make sense to only print the "Chunksize / Total
chunks / Free Chunks" if a chunksize is specified explicitly via the
-c option, and to do a s/chunk/extent/ in the next part of the output,
i.e.:

Min free extent: 4 KB
Max free extent: 568232 KB
Avg free extent size: 188 KB

- Ted

2009-07-24 23:14:57

[permalink] [raw]

Subject: Re: [PATCH] e2freefrag utility

On Jul 24, 2009 18:32 -0400, Theodore Ts'o wrote:
> One question --- right now the chunksize (as specified by -c) only
> affects these lines printed by e2freefrag, right?
>
> Chunksize: 1048576 bytes (256 blocks)
> Total chunks: 71681
> Free chunks: 21657 (30.2%)

Yes, pretty much.

> They are a little confusing since "chunk" as used here is different
> from "chunk" used in the next part of the output:
>
> Min free chunk: 4 KB
> Max free chunk: 568232 KB
> Avg free chunk: 188 KB

You're right. "free extent" is better.

> How useful is it to print the "total chunks / free chunks" in the
> general case? I'm guessing this relates to Lutsre's chunking and
> chunksize?

Well, it was important for the hardware RAID setups, to see how many
stripe-aligned free chunks are available in the filesystem. Since
mballoc will also try to allocate/align on "chunk" boundaries this
is useful to know. If this chunksize depended on the superblock
s_raid_stripe_width then it would be more useful for the general public.

> Would it make sense to only print the "Chunksize / Total
> chunks / Free Chunks" if a chunksize is specified explicitly via the
> -c option, and to do a s/chunk/extent/ in the next part of the output,

I don't have a big objection. I don't think there are any tools that
depend on this output.

Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.

2009-07-25 00:19:29

[permalink] [raw]

Subject: Re: [PATCH] e2freefrag utility

On Fri, Jul 24, 2009 at 05:14:25PM -0600, Andreas Dilger wrote:
>
> Well, it was important for the hardware RAID setups, to see how many
> stripe-aligned free chunks are available in the filesystem. Since
> mballoc will also try to allocate/align on "chunk" boundaries this
> is useful to know. If this chunksize depended on the superblock
> s_raid_stripe_width then it would be more useful for the general public.

Yeah, I think what we should try to do is to display the chunk
information if s_raid_stripe_width if it is set, and otherwise only
print it if a chunk size is explicitly specified. Sounds like a plan?

- Ted

2009-07-27 18:37:08

[permalink] [raw]

Subject: Re: [PATCH] e2freefrag utility

On Jul 24, 2009 20:18 -0400, Theodore Ts'o wrote:
> On Fri, Jul 24, 2009 at 05:14:25PM -0600, Andreas Dilger wrote:
> > Well, it was important for the hardware RAID setups, to see how many
> > stripe-aligned free chunks are available in the filesystem. Since
> > mballoc will also try to allocate/align on "chunk" boundaries this
> > is useful to know. If this chunksize depended on the superblock
> > s_raid_stripe_width then it would be more useful for the general public.
>
> Yeah, I think what we should try to do is to display the chunk
> information if s_raid_stripe_width if it is set, and otherwise only
> print it if a chunk size is explicitly specified. Sounds like a plan?

Yes, sounds reasonable.

Cheers, Andreas
--
Andreas Dilger
Sr. Staff Engineer, Lustre Group
Sun Microsystems of Canada, Inc.

2009-08-10 03:32:01

[permalink] [raw]

Subject: [PATCH 2/6] e2freefrag: Do not print chunk-related information by default

Only print information related to chunk sizes if a chunksize is
printed.

Signed-off-by: "Theodore Ts'o" <[email protected]>
---
misc/e2freefrag.8.in | 13 +++++--------
misc/e2freefrag.c | 30 +++++++++++++++++++-----------
2 files changed, 24 insertions(+), 19 deletions(-)

diff --git a/misc/e2freefrag.8.in b/misc/e2freefrag.8.in
index 77fadd7..56fdbff 100644
--- a/misc/e2freefrag.8.in
+++ b/misc/e2freefrag.8.in
@@ -30,9 +30,12 @@ can be used to gauge the level of free space fragmentation in the filesystem.
.SH OPTIONS
.TP
.BI \-c " chunk_kb"
-Desired size of chunk. It is specified in units of kilobytes (KB). If no
+If a chunk size is specified, then
+.B e2freefrag
+will print how many free chunks of size
.I chunk_kb
-is specified on the command line, then the default value is 1024KB.
+are available in units of kilobytes (Kb). The chunk size must be a
+power of two and be larger than filesystem block size.
.TP
.BI \-h
Print the usage of the program.
@@ -47,12 +50,6 @@ Total blocks: 1504085
.br
Free blocks: 292995 (19.5%)
.br
-Chunk size: 1048576 bytes (256 blocks)
-.br
-Total chunks: 5876
-.br
-Free chunks: 463 (7.9%)
-.br

Min. free extent: 4 KB
.br
diff --git a/misc/e2freefrag.c b/misc/e2freefrag.c
index 9e7b617..274bf55 100644
--- a/misc/e2freefrag.c
+++ b/misc/e2freefrag.c
@@ -52,9 +52,14 @@ void init_chunk_info(ext2_filsys fs, struct chunk_info *info)
{
int i;

- info->chunkbits = ul_log2(info->chunkbytes);
info->blocksize_bits = ul_log2((unsigned long)fs->blocksize);
- info->blks_in_chunk = info->chunkbytes >> info->blocksize_bits;
+ if (info->chunkbytes) {
+ info->chunkbits = ul_log2(info->chunkbytes);
+ info->blks_in_chunk = info->chunkbytes >> info->blocksize_bits;
+ } else {
+ info->chunkbits = ul_log2(DEFAULT_CHUNKSIZE);
+ info->blks_in_chunk = DEFAULT_CHUNKSIZE >> info->blocksize_bits;
+ }

info->min = ~0UL;
info->max = info->avg = 0;
@@ -138,13 +143,16 @@ errcode_t get_chunk_info(ext2_filsys fs, struct chunk_info *info)
(double)fs->super->s_free_blocks_count * 100 /
fs->super->s_blocks_count);

- printf("\nChunksize: %lu bytes (%u blocks)\n",
- info->chunkbytes, info->blks_in_chunk);
- total_chunks = (fs->super->s_blocks_count + info->blks_in_chunk) >>
- (info->chunkbits - info->blocksize_bits);
- printf("Total chunks: %lu\nFree chunks: %lu (%0.1f%%)\n",
- total_chunks, info->free_chunks,
- (double)info->free_chunks * 100 / total_chunks);
+ if (info->chunkbytes) {
+ printf("\nChunksize: %lu bytes (%u blocks)\n",
+ info->chunkbytes, info->blks_in_chunk);
+ total_chunks = (fs->super->s_blocks_count +
+ info->blks_in_chunk) >>
+ (info->chunkbits - info->blocksize_bits);
+ printf("Total chunks: %lu\nFree chunks: %lu (%0.1f%%)\n",
+ total_chunks, info->free_chunks,
+ (double)info->free_chunks * 100 / total_chunks);
+ }

/* Display chunk information in KB */
if (info->real_free_chunks) {
@@ -228,7 +236,7 @@ void open_device(char *device_name, ext2_filsys *fs)

int main(int argc, char *argv[])
{
- struct chunk_info chunk_info = { .chunkbytes = DEFAULT_CHUNKSIZE };
+ struct chunk_info chunk_info = { };
errcode_t retval = 0;
ext2_filsys fs = NULL;
char *device_name;
@@ -273,7 +281,7 @@ int main(int argc, char *argv[])

open_device(device_name, &fs);

- if (chunk_info.chunkbytes < fs->blocksize) {
+ if (chunk_info.chunkbytes && (chunk_info.chunkbytes < fs->blocksize)) {
fprintf(stderr, "%s: chunksize must be greater than or equal "
"to filesystem blocksize.\n", progname);
exit(1);
--
1.6.3.2.1.gb9f7d.dirty

2009-08-10 03:32:00

[permalink] [raw]

Subject: [PATCH 0/6] Patches to improve/fix e2freefrag

As we had discussed earlier, here are the patches to make the output of
e2freefrag either to understand. While I was working with the program,
I found a number of bugs that caused it to behave incorrectly on file
systems with 1k block size, and to give incorrect information in some
circumstances. These patches fix all of this bugs I was able to find.

Theodore Ts'o (6):
e2freefrag: Clarify e2freefrag's messages
e2freefrag: Do not print chunk-related information by default
e2freefrag: Fix to work correctly for file systems with 1kb block
sizes
e2freefrag: Take into account the last free extent in the file system
Add V=1 support when linking e2freefrag in misc/Makefile.in
libext2fs: Treat uninitialized parts of bitmaps as unallocated

lib/ext2fs/rw_bitmaps.c | 4 +-
misc/Makefile.in | 4 +-
misc/e2freefrag.8.in | 23 +++++------
misc/e2freefrag.c | 99 +++++++++++++++++++++++++++++-----------------
tests/m_uninit/expect.1 | 48 +++++++++++-----------
5 files changed, 100 insertions(+), 78 deletions(-)

2009-08-10 03:32:02

[permalink] [raw]

Subject: [PATCH 5/6] Add V=1 support when linking e2freefrag in misc/Makefile.in

Signed-off-by: "Theodore Ts'o" <[email protected]>
---
misc/Makefile.in | 4 ++--
1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/misc/Makefile.in b/misc/Makefile.in
index 3076f67..a5ed0c0 100644
--- a/misc/Makefile.in
+++ b/misc/Makefile.in
@@ -289,8 +289,8 @@ logsave.profiled: profiled/logsave.o
$(Q) $(CC) $(ALL_LDFLAGS) -g -pg -o logsave.profiled profiled/logsave.o

e2freefrag: $(E2FREEFRAG_OBJS)
- @echo " LD $@"
- @$(CC) $(ALL_LDFLAGS) -o e2freefrag $(E2FREEFRAG_OBJS) $(LIBS)
+ $(E) " LD $@"
+ $(Q) $(CC) $(ALL_LDFLAGS) -o e2freefrag $(E2FREEFRAG_OBJS) $(LIBS)

filefrag: $(FILEFRAG_OBJS)
$(E) " LD $@"
--
1.6.3.2.1.gb9f7d.dirty

2009-08-10 03:32:01

[permalink] [raw]

Subject: [PATCH 1/6] e2freefrag: Clarify e2freefrag's messages

"Free chunks" is confusing since it has nothing to do with the
chunksize; use "free extents" instead.

Also add a missing newline in an error message.

Signed-off-by: "Theodore Ts'o" <[email protected]>
---
misc/e2freefrag.8.in | 10 +++++-----
misc/e2freefrag.c | 12 ++++++------
2 files changed, 11 insertions(+), 11 deletions(-)

diff --git a/misc/e2freefrag.8.in b/misc/e2freefrag.8.in
index 9c47e97..77fadd7 100644
--- a/misc/e2freefrag.8.in
+++ b/misc/e2freefrag.8.in
@@ -54,16 +54,16 @@ Total chunks: 5876
Free chunks: 463 (7.9%)
.br

-Min free chunk: 4 KB
+Min. free extent: 4 KB
.br
-Max free chunk: 24008 KB
+Max. free extent: 24008 KB
.br
-Avg free chunk: 252 KB
+Avg. free extent: 252 KB
.br

-HISTOGRAM OF FREE CHUNK SIZES:
+HISTOGRAM OF FREE EXTENT SIZES:
.br
-Chunk Size Range : Free chunks Free Blocks Percent
+Extent Size Range : Free extents Free Blocks Percent
.br
4K... 8K- : 704 704 0.2%
.br
diff --git a/misc/e2freefrag.c b/misc/e2freefrag.c
index df41853..9e7b617 100644
--- a/misc/e2freefrag.c
+++ b/misc/e2freefrag.c
@@ -156,16 +156,16 @@ errcode_t get_chunk_info(ext2_filsys fs, struct chunk_info *info)
info->min = 0;
}

- printf("\nMin free chunk: %lu KB \nMax free chunk: %lu KB\n"
- "Avg free chunk: %lu KB\n", info->min, info->max, info->avg);
+ printf("\nMin. free extent: %lu KB \nMax. free extent: %lu KB\n"
+ "Avg. free extent: %lu KB\n", info->min, info->max, info->avg);

- printf("\nHISTOGRAM OF FREE CHUNK SIZES:\n");
- printf("%s : %12s %12s %7s\n", "Chunk Size Range", "Free chunks",
+ printf("\nHISTOGRAM OF FREE EXTENT SIZES:\n");
+ printf("%s : %12s %12s %7s\n", "Extent Size Range", "Free extents",
"Free Blocks", "Percent");
for (i = 0; i < MAX_HIST; i++) {
end = 1 << (i + info->blocksize_bits - units);
if (info->histogram.fc_chunks[i] != 0)
- printf("%5lu%c...%5lu%c- : %12lu %12lu %6.2f%%\n",
+ printf("%5lu%c...%5lu%c- : %12lu %12lu %6.2f%%\n",
start, *unitp, end, *unitp,
info->histogram.fc_chunks[i],
info->histogram.fc_blocks[i],
@@ -250,7 +250,7 @@ int main(int argc, char *argv[])
if (chunk_info.chunkbytes &
(chunk_info.chunkbytes - 1)) {
fprintf(stderr, "%s: chunk size must be a "
- "power of 2.", argv[0]);
+ "power of 2.\n", argv[0]);
usage(progname);
}
chunk_info.chunkbytes *= 1024;
--
1.6.3.2.1.gb9f7d.dirty

2009-08-10 03:32:02

[permalink] [raw]

Subject: [PATCH 3/6] e2freefrag: Fix to work correctly for file systems with 1kb block sizes

If the file system has a non-zero s_first_data_block, as is the case
when the block size is 1kb, e2freefrag would incorrectly try to
reference invalid data blocks in the block allocation bitmap.

Signed-off-by: "Theodore Ts'o" <[email protected]>
---
misc/e2freefrag.c | 12 ++++++++----
1 files changed, 8 insertions(+), 4 deletions(-)

diff --git a/misc/e2freefrag.c b/misc/e2freefrag.c
index 274bf55..10a48ad 100644
--- a/misc/e2freefrag.c
+++ b/misc/e2freefrag.c
@@ -79,6 +79,7 @@ void scan_block_bitmap(ext2_filsys fs, struct chunk_info *info)
unsigned long long chunk_num;
unsigned long last_chunk_size = 0;
unsigned long long chunk_start_blk = 0;
+ int used;

for (chunk_num = 0; chunk_num < chunks; chunk_num++) {
unsigned long long blk, num_blks;
@@ -95,10 +96,13 @@ void scan_block_bitmap(ext2_filsys fs, struct chunk_info *info)
/* Initialize starting block for first chunk correctly else
* there is a segfault when blocksize = 1024 in which case
* block_map->start = 1 */
- for (blk = (chunk_num == 0 ? fs->super->s_first_data_block : 0);
- blk < num_blks; blk++, chunk_start_blk++) {
- int used = ext2fs_fast_test_block_bitmap(fs->block_map,
- chunk_start_blk);
+ for (blk = 0; blk < num_blks; blk++, chunk_start_blk++) {
+ if (chunk_num == 0 && blk == 0) {
+ blk = fs->super->s_first_data_block;
+ chunk_start_blk = blk;
+ }
+ used = ext2fs_fast_test_block_bitmap(fs->block_map,
+ chunk_start_blk);
if (!used) {
last_chunk_size++;
chunk_free++;
--
1.6.3.2.1.gb9f7d.dirty

2009-08-10 03:32:02

[permalink] [raw]

Subject: [PATCH 4/6] e2freefrag: Take into account the last free extent in the file system

Fix a bug in e2freefrag where if the last free extent is at the very
end of the filesystem, it would be disregarded.

Signed-off-by: "Theodore Ts'o" <[email protected]>
---
misc/e2freefrag.c | 47 ++++++++++++++++++++++++++++++-----------------
1 files changed, 30 insertions(+), 17 deletions(-)

diff --git a/misc/e2freefrag.c b/misc/e2freefrag.c
index 10a48ad..a4ab994 100644
--- a/misc/e2freefrag.c
+++ b/misc/e2freefrag.c
@@ -71,6 +71,24 @@ void init_chunk_info(ext2_filsys fs, struct chunk_info *info)
}
}

+void update_chunk_stats(struct chunk_info *info, unsigned long chunk_size)
+{
+ unsigned long index;
+
+ index = ul_log2(chunk_size) + 1;
+ if (index >= MAX_HIST)
+ index = MAX_HIST-1;
+ info->histogram.fc_chunks[index]++;
+ info->histogram.fc_blocks[index] += chunk_size;
+
+ if (chunk_size > info->max)
+ info->max = chunk_size;
+ if (chunk_size < info->min)
+ info->min = chunk_size;
+ info->avg += chunk_size;
+ info->real_free_chunks++;
+}
+
void scan_block_bitmap(ext2_filsys fs, struct chunk_info *info)
{
unsigned long long blocks_count = fs->super->s_blocks_count;
@@ -109,20 +127,7 @@ void scan_block_bitmap(ext2_filsys fs, struct chunk_info *info)
}

if (used && last_chunk_size != 0) {
- unsigned long index;
-
- index = ul_log2(last_chunk_size) + 1;
- info->histogram.fc_chunks[index]++;
- info->histogram.fc_blocks[index] +=
- last_chunk_size;
-
- if (last_chunk_size > info->max)
- info->max = last_chunk_size;
- if (last_chunk_size < info->min)
- info->min = last_chunk_size;
- info->avg += last_chunk_size;
-
- info->real_free_chunks++;
+ update_chunk_stats(info, last_chunk_size);
last_chunk_size = 0;
}
}
@@ -130,6 +135,8 @@ void scan_block_bitmap(ext2_filsys fs, struct chunk_info *info)
if (chunk_free == info->blks_in_chunk)
info->free_chunks++;
}
+ if (last_chunk_size != 0)
+ update_chunk_stats(info, last_chunk_size);
}

errcode_t get_chunk_info(ext2_filsys fs, struct chunk_info *info)
@@ -176,13 +183,19 @@ errcode_t get_chunk_info(ext2_filsys fs, struct chunk_info *info)
"Free Blocks", "Percent");
for (i = 0; i < MAX_HIST; i++) {
end = 1 << (i + info->blocksize_bits - units);
- if (info->histogram.fc_chunks[i] != 0)
- printf("%5lu%c...%5lu%c- : %12lu %12lu %6.2f%%\n",
- start, *unitp, end, *unitp,
+ if (info->histogram.fc_chunks[i] != 0) {
+ char end_str[32];
+
+ sprintf(end_str, "%5lu%c-", end, *unitp);
+ if (i == MAX_HIST-1)
+ strcpy(end_str, "max ");
+ printf("%5lu%c...%7s : %12lu %12lu %6.2f%%\n",
+ start, *unitp, end_str,
info->histogram.fc_chunks[i],
info->histogram.fc_blocks[i],
(double)info->histogram.fc_blocks[i] * 100 /
fs->super->s_free_blocks_count);
+ }
start = end;
if (start == 1<<10) {
start = 1;
--
1.6.3.2.1.gb9f7d.dirty

2009-08-10 03:32:02