xfs_fsr allocation group optimization

xfs_fsr allocation group optimization

[Johan Andersson]

[-- Attachment #1: Type: text/plain, Size: 1624 bytes --]

Hi!

Last week I discovered that one of our volumes had 87%(!) file
fragmentation. Number of extents per file was in the range of thousands!
Nothing you are used to when it comes to XFS...
The filesystem is 68% full, but was up to 99% full for a short period a
couple of weeks earlier.

The xfs_fsr utility is made for this kind of problem, but after reading
more about xfs_fsr, in particular this:
http://oss.sgi.com/archives/xfs/2003-02/msg00141.html
I was more sceptical.

So I run some tests. And as Chris pointed out, when running xfs_fsr on a
badly fragmented filesystem, it completely destroys the locality of
files.

Then I decided to try to fix this, so I wrote a dirty little proof of
concept hack to xfs_fsr.c (diff against cvs attached) that finds one
name for the inode it defrags, and places the temporary file it's parent
directory. This way, it will restore the broken locality.

This works fine, after running it on the badly fragmented filesystem,
both fragmentation and locality was better than ever!

However, this fix is as I said "dirty". It uses find -inum to find a
filename for an inode. This makes it quite slow. Not much of a problem
for a one-time problem like this, but it's not very nice to put this
into a cron-job. There must be a better way to find the filename. But
I'm not familiar with the internals of XFS, so I thought I ask on this
list:
Does anyone know of a good way to find one filename that points o a
certain inode? I can't use xfs_db ncheck, as the filesystem is mounted.
Or is there a way to tell XFS to place extents in a newly created file
in a certain AG?

/Johan Andersson


[-- Attachment #2: xfs_fsr-agfix.diff --]
[-- Type: text/x-patch, Size: 1522 bytes --]

Index: xfs_fsr.c
===================================================================
RCS file: /cvs/xfs-cmds/xfsdump/fsr/xfs_fsr.c,v
retrieving revision 1.28
diff -u -r1.28 xfs_fsr.c
--- xfs_fsr.c	24 May 2007 03:59:42 -0000	1.28
+++ xfs_fsr.c	11 Jun 2007 06:42:29 -0000
@@ -655,10 +655,12 @@
 	int	ret;
 	__s32	buflenout;
 	xfs_bstat_t buf[GRABSZ];
-	char	fname[64];
+	char	fname[PATH_MAX+1];
 	char	*tname;
+	char    cmd[64];
 	jdm_fshandle_t	*fshandlep;
 	xfs_ino_t	lastino = startino;
+	FILE    *pfname;
 
 	fsrprintf(_("%s start inode=%llu\n"), mntdir,
 		(unsigned long long)startino);
@@ -714,11 +716,20 @@
 				continue;
 			}
 
-			/* Don't know the pathname, so make up something */
-			sprintf(fname, "ino=%lld", (long long)p->bs_ino);
-
-			/* Get a tmp file name */
-			tname = tmp_next(mntdir);
+			/* Find (one) filename that this inode belongs to. */
+			snprintf(cmd, sizeof(cmd), "find %s -xdev -inum %lld -print0", mntdir, (long long)p->bs_ino);
+			pfname = popen(cmd, "r");
+			fgets(fname, sizeof(fname), pfname);
+			pclose(pfname);
+			
+			if (strlen(fname)) {
+			  tname = gettmpname(fname);
+			} else {
+			  /* Don't know the pathname, so make up something */
+			  snprintf(fname, sizeof(fname), "ino=%lld", (long long)p->bs_ino);
+			  /* Get a tmp file name */
+			  tname = tmp_next(mntdir);
+			} 
 
 			ret = fsrfile_common(fname, tname, mntdir, fd, p);
 
@@ -1297,6 +1308,8 @@
 
 	strcat(buf, sbuf);
 
+	fsrprintf(_("gettmpname: fname=%s, buf=%s\n"), fname, buf);
+
 	return(buf);
 }
 

Re: xfs_fsr allocation group optimization

[Chris Wedgwood]

On Mon, Jun 11, 2007 at 08:51:32AM +0200, Johan Andersson wrote:

> So I run some tests. And as Chris pointed out, when running xfs_fsr
> on a badly fragmented filesystem, it completely destroys the
> locality of files.

You can always do something like:

   find path/to/defrag/ -type f -print0 | xargs -r0 xfs_fsr -v

and check /var/log/daemon.log (or whatever) for a progress report.

This will of course only make one pass, so you might want to wrap it.
But unless you're really low on space it's probably not useful to make
many passes anyhow.

You might always want the -d argument (not sure if the man page has
this).

Re: xfs_fsr allocation group optimization

[Johan Andersson]

But xfs_fsr sorts inodes by number of extents in order to optimise free
space. If you run the "find ..." on a badly fragmented file system, it
won't optimise much at all, since there won't be free chunks large
enough for big files. I tried to just copy one file and remove the
original in the file system mentioned, but it only got worse. Running
running xfs_fsr on the whole file system got it down to 0% file frag, 1
extent/file. So xfs_fsr on a whole file system is much more effective
than xfs_fsr on each file in the file system. Especially if the file
system is near full.

/Johan Andersson

On Mon, 2007-06-11 at 00:35 -0700, Chris Wedgwood wrote:
> On Mon, Jun 11, 2007 at 08:51:32AM +0200, Johan Andersson wrote:
> 
> > So I run some tests. And as Chris pointed out, when running xfs_fsr
> > on a badly fragmented filesystem, it completely destroys the
> > locality of files.
> 
> You can always do something like:
> 
>    find path/to/defrag/ -type f -print0 | xargs -r0 xfs_fsr -v
> 
> and check /var/log/daemon.log (or whatever) for a progress report.
> 
> This will of course only make one pass, so you might want to wrap it.
> But unless you're really low on space it's probably not useful to make
> many passes anyhow.
> 
> You might always want the -d argument (not sure if the man page has
> this).
> 
> 

Re: xfs_fsr allocation group optimization

[Chris Wedgwood]

On Mon, Jun 11, 2007 at 10:43:29AM +0200, Johan Andersson wrote:

> But xfs_fsr sorts inodes by number of extents in order to optimise
> free space.

yeah, and the 'window' it uses is fairly small, iirc it does a
bulkstat of 64-inodes at a time and then sorts from the worst to the
best

i have a tree somewhere[1] that has this as a command line option as
well as a few other things

> If you run the "find ..." on a badly fragmented file system, it
> won't optimise much at all, since there won't be free chunks large
> enough for big files.

yes, that's always going to be the case though with the current simple
but somewhat arguably myopic algorithm

> I tried to just copy one file and remove the original in the file
> system mentioned, but it only got worse.

long-term we need to teach things like cp and rsync about
preallocation, but the generic APIs for this haven't bene fully
fleshed out

without that you're almost certainly going to get some level of
fragmentation for files over a certain size (smaller files end up
being contiguous usually becaue of delayed allocation)

> Running running xfs_fsr on the whole file system got it down to 0%
> file frag, 1 extent/file.

using "find .... xfs_fsr" you get temporary files in the same AG as
the file your are defragmenting, avoiding the spreading out effect,
but this might not be the least-defragmented file you can get

what's really needed is an attempt to find space near the original
file if possible and if not then an option to try harder looking in
other AGs

> So xfs_fsr on a whole file system is much more effective than
> xfs_fsr on each file in the file system. Especially if the file
> system is near full.

well, xfs_fsr doesn't work very well if the filesystem is near full
for the most part

it works very well if you have a reasonable amount of free-space (say
5%) but what's really needed is a smarter way to defragment, perhaps
by tweaking the allocator to avoid some AGs or parts of the device so
we cab bubble things about.  if people are serious about shrink work
maybe those APIs could assist here.





[1] sorry, i'm not sure where, there are also options not to touch
    recently created files as that's often they are in use and to also
    not bother doing the defragment unless the improvement is fairly
    significant, so it tends to spend it's time doing work that makes
    the biggest most useful impact

    i think the tree that has all these changes ended up being ugly
    and the changes weren't cleanly separated and thus were never
    posted

    if i find the tree i'll just publish it as-is

Re: xfs_fsr allocation group optimization

[Johan Andersson]

On Mon, 2007-06-11 at 02:01 -0700, Chris Wedgwood wrote:
> using "find .... xfs_fsr" you get temporary files in the same AG as
> the file your are defragmenting, avoiding the spreading out effect,
> but this might not be the least-defragmented file you can get
> 
> what's really needed is an attempt to find space near the original
> file if possible and if not then an option to try harder looking in
> other AGs
This is exactly what the simple but ugly patch I attached achieves by
looking up the filename of the inode it defrags when doing a full file
system defrag. And it works well, except that it spends a lot of time
finding that file name. As I said, a better option would be if you could
tell XFS in what AG you want extents for a newly created file to place
it's extents in. 

/Johan Andersson

Re: xfs_fsr allocation group optimization

[Chris Wedgwood]

On Mon, Jun 11, 2007 at 11:15:56AM +0200, Johan Andersson wrote:

> This is exactly what the simple but ugly patch I attached achieves
> by looking up the filename of the inode it defrags when doing a full
> file system defrag. And it works well, except that it spends a lot
> of time finding that file name. As I said, a better option would be
> if you could tell XFS in what AG you want extents for a newly
> created file to place it's extents in.

AGs can be large, you really want to say 'allocate near ...'

Re: xfs_fsr allocation group optimization

[Johan Andersson]

On Mon, 2007-06-11 at 02:41 -0700, Chris Wedgwood wrote:
> On Mon, Jun 11, 2007 at 11:15:56AM +0200, Johan Andersson wrote:
> 
> > This is exactly what the simple but ugly patch I attached achieves
> > by looking up the filename of the inode it defrags when doing a full
> > file system defrag. And it works well, except that it spends a lot
> > of time finding that file name. As I said, a better option would be
> > if you could tell XFS in what AG you want extents for a newly
> > created file to place it's extents in.
> 
> AGs can be large, you really want to say 'allocate near ...'

Yes, absolutely, if that was possible. But with the current XFS, at
least we can place it in the same AG. In the way xfs_fsr operates now,
in almost all user space, I don't see any good way to tell XFS where to
place the extents, other than creating the temporary file in the same
directory as the original file.

My question is really, is there a better way than "find -xdev -inum" to
find what file points to a given inode? It would solve our immediate
problem with xfs_fsr destroying locality of files, while still
optimising the file system properly.

/Johan Andersson

Re: xfs_fsr allocation group optimization

[Chris Wedgwood]

On Mon, Jun 11, 2007 at 12:39:13PM +0200, Johan Andersson wrote:

> In the way xfs_fsr operates now, in almost all user space, I don't
> see any good way to tell XFS where to place the extents, other than
> creating the temporary file in the same directory as the original
> file.

Exactly.

> My question is really, is there a better way than "find -xdev -inum"
> to find what file points to a given inode?

You can build then entire tree in-core using bulkstat and readdir,
doing the bulkstat first means you can try to optimize the order you
do the readdirs in somewhat.

Re: xfs_fsr allocation group optimization

[Nathan Scott]

On Mon, 2007-06-11 at 08:58 -0700, Chris Wedgwood wrote:
> 
> 
> > In the way xfs_fsr operates now, in almost all user space, I don't
> > see any good way to tell XFS where to place the extents, other than
> > creating the temporary file in the same directory as the original
> > file.
> 
> Exactly.
> 
> > My question is really, is there a better way than "find -xdev -inum"
> > to find what file points to a given inode?
> 
> You can build then entire tree in-core using bulkstat and readdir,
> doing the bulkstat first means you can try to optimize the order you
> do the readdirs in somewhat.
> 

Probably better to change the kernel extent-swap code to not do
alloc-near-tempinode allocations, and instead find a way to pass
XFS_ALLOCTYPE_THIS_AG/XFS_ALLOCTYPE_NEAR_BNO/or some saner alloc
flag down to the allocator for all extent swapping allocations.

cheers.

Re: xfs_fsr allocation group optimization

[David Chinner]

On Tue, Jun 12, 2007 at 09:07:36AM +1000, Nathan Scott wrote:
> On Mon, 2007-06-11 at 08:58 -0700, Chris Wedgwood wrote:
> > > In the way xfs_fsr operates now, in almost all user space, I don't
> > > see any good way to tell XFS where to place the extents, other than
> > > creating the temporary file in the same directory as the original
> > > file.
> > 
> > Exactly.
> > 
> > > My question is really, is there a better way than "find -xdev -inum"
> > > to find what file points to a given inode?
> > 
> > You can build then entire tree in-core using bulkstat and readdir,
> > doing the bulkstat first means you can try to optimize the order you
> > do the readdirs in somewhat.
> 
> Probably better to change the kernel extent-swap code to not do
> alloc-near-tempinode allocations, and instead find a way to pass
> XFS_ALLOCTYPE_THIS_AG/XFS_ALLOCTYPE_NEAR_BNO/or some saner alloc
> flag down to the allocator for all extent swapping allocations.

/me sighs and points to the generic allocation interface I wanted
for exactly these reasons:

http://marc.info/?l=linux-fsdevel&m=116278169519095&w=2

Instead, we're getting a mostly useless XFS_IOC_RESVSP replacement
called sys_fallocate() that provides us with pretty much nothing.
Given that sys_fallocate() can't be extended to do this sort of
thing, we're going to be stuck with doing our own thing again....

Cheers,

Dave.
-- 
Dave Chinner
Principal Engineer
SGI Australian Software Group

Re: xfs_fsr allocation group optimization

[David Chinner]

On Mon, Jun 11, 2007 at 11:15:56AM +0200, Johan Andersson wrote:
> On Mon, 2007-06-11 at 02:01 -0700, Chris Wedgwood wrote:
> > using "find .... xfs_fsr" you get temporary files in the same AG as
> > the file your are defragmenting, avoiding the spreading out effect,
> > but this might not be the least-defragmented file you can get
> > 
> > what's really needed is an attempt to find space near the original
> > file if possible and if not then an option to try harder looking in
> > other AGs
> This is exactly what the simple but ugly patch I attached achieves by
> looking up the filename of the inode it defrags when doing a full file
> system defrag. And it works well, except that it spends a lot of time
> finding that file name. As I said, a better option would be if you could
> tell XFS in what AG you want extents for a newly created file to place
> it's extents in. 

Yup. That would be nice. We've got the basis of doing allocation policies
with the filestreams code - an arbitrary blob of data associated with
an inode that influences the allocation decision. Userspace driven
allocation hints are more complex and require subtler hooks in the
allocation path, though....

Cheers,

Dave.
-- 
Dave Chinner
Principal Engineer
SGI Australian Software Group

Re: xfs_fsr allocation group optimization

[David Chinner]

On Mon, Jun 11, 2007 at 08:51:32AM +0200, Johan Andersson wrote:
> Does anyone know of a good way to find one filename that points o a
> certain inode?

We need an rmap....

We have some prototype linux code that does parent pointers (i.e.
each inode has a back pointer to it's parent inode), but that, IIUC,
is a long way from prime-time. Tim?

Cheers,

Dave.
-- 
Dave Chinner
Principal Engineer
SGI Australian Software Group

Re: xfs_fsr allocation group optimization

[Timothy Shimmin]

David Chinner wrote:
> On Mon, Jun 11, 2007 at 08:51:32AM +0200, Johan Andersson wrote:
>> Does anyone know of a good way to find one filename that points o a
>> certain inode?
> 
> We need an rmap....
> 
> We have some prototype linux code that does parent pointers (i.e.
> each inode has a back pointer to it's parent inode), but that, IIUC,
> is a long way from prime-time. Tim?
> 
> Cheers,
> 
> Dave.

I don't know about a "long way" (longer to fully supported, yes)
Firstly, I need to move its hooks out of linux-2.6/xfs_iops.c which were 
referring to xfs inodes (instead of vnodes) probably back where they were in
xfs_vnodeops.c.

Nathan, did you have some other suggestion than this - unfortunately,
I haven't looked at this code (until recently) for a while.

Cheers,
Tim.

Re: xfs_fsr allocation group optimization

[Nathan Scott]

On Fri, 2007-06-15 at 17:20 +1000, Timothy Shimmin wrote:
> 
> I don't know about a "long way" (longer to fully supported, yes)
> Firstly, I need to move its hooks out of linux-2.6/xfs_iops.c which
> were 
> referring to xfs inodes (instead of vnodes) probably back where they
> were in
> xfs_vnodeops.c.
> 
> Nathan, did you have some other suggestion than this - unfortunately,
> I haven't looked at this code (until recently) for a while. 

Geez, that takes me back - hummm, I seem to remember a possibly-iget-
related performance issue?  Not much else, sorry (it _is_ beer o'clock
on a Friday arvo after all...).

cheers.

--
Nathan

Re: xfs_fsr allocation group optimization

[Johan Andersson]

On Fri, 2007-06-15 at 17:20 +1000, Timothy Shimmin wrote:
> David Chinner wrote:
> > On Mon, Jun 11, 2007 at 08:51:32AM +0200, Johan Andersson wrote:
> >> Does anyone know of a good way to find one filename that points o a
> >> certain inode?
> > 
> > We need an rmap....
> > 
> > We have some prototype linux code that does parent pointers (i.e.
> > each inode has a back pointer to it's parent inode), but that, IIUC,
> > is a long way from prime-time. Tim?
> > 
> > Cheers,
> > 
> > Dave.
> 
> I don't know about a "long way" (longer to fully supported, yes)
> Firstly, I need to move its hooks out of linux-2.6/xfs_iops.c which were 
> referring to xfs inodes (instead of vnodes) probably back where they were in
> xfs_vnodeops.c.
> 
> Nathan, did you have some other suggestion than this - unfortunately,
> I haven't looked at this code (until recently) for a while.
> 
> Cheers,
> Tim.
> 

I have another idea that i plan to try. The idea was to add an ioctl to
"clone" an inode. By using the original inode (the one to be
defragmented) as parent "directory" in the call to xfs_dir_ialloc(), the
new inode should be allocated near the original inode. The fsr can then
open the new inode with jdm_open and proceed as normal.
This would also solve another problem that I see with fsr, the mtime of
every directory in the fs is updated when fsr is run. 

I do see one problem with this: If the defrag is aborted for some
reason, we can get orphaned inodes. Will fsck handle this?

/Johan Andersson