Allocating inodes from a single block

Allocating inodes from a single block

[Michael Nishimoto]

Hi everyone,

Filesystem free space becomes fragmented over time.  It's possible
for total free space to be a decent size and still not have a chunk
large enough to allocate new inodes.

During testing, we managed to create a 111G filesystem which
could no longer create new inodes, but it had 6% free space.

Has anyone thought about how to solve this issue?

Ideally, a solution would still allocate multiple contiguous blocks
of inodes when space is available but would eventually work when
only single free blocks are available.  And it would be good if
any change remains backwards compatible with existing ondisk
formats.

thanks,

  Michael

Re: Allocating inodes from a single block

[Chris Wedgwood]

On Tue, Jul 17, 2007 at 11:11:50AM -0700, Michael Nishimoto wrote:

> Filesystem free space becomes fragmented over time.  It's possible
> for total free space to be a decent size and still not have a chunk
> large enough to allocate new inodes.

by default there is a restriction that indoes shouldn't consume more
that 25% of the total space

see the mkfs.xfs man-page for details, search for 'maxpct'

for existing filesystems you can use xfs_db to rewrite this value

Re: Allocating inodes from a single block

[Michael Nishimoto]

Chris Wedgwood wrote:
> On Tue, Jul 17, 2007 at 11:11:50AM -0700, Michael Nishimoto wrote:
> 
>  > Filesystem free space becomes fragmented over time.  It's possible
>  > for total free space to be a decent size and still not have a chunk
>  > large enough to allocate new inodes.
> 
> by default there is a restriction that indoes shouldn't consume more
> that 25% of the total space
> 
> see the mkfs.xfs man-page for details, search for 'maxpct'
> 
> for existing filesystems you can use xfs_db to rewrite this value

I do know about the 25% restriction, but that isn't what I'm talking
about.  I'm not suggesting to fillup a filesystem 100% with
inodes.

Imagine a case where only 2-3% of the space is inodes but that 94%
of the total space was filled.  If the remaining 6% of space is
highly fragmented, then no new inodes can be allocated.  The dialloc
code couldn't find 8 contiguous blocks.

    Mike

Re: Allocating inodes from a single block

[Eric Sandeen]

Chris Wedgwood wrote:
> On Tue, Jul 17, 2007 at 11:11:50AM -0700, Michael Nishimoto wrote:
> 
>> Filesystem free space becomes fragmented over time.  It's possible
>> for total free space to be a decent size and still not have a chunk
>> large enough to allocate new inodes.
> 
> by default there is a restriction that indoes shouldn't consume more
> that 25% of the total space
> 
> see the mkfs.xfs man-page for details, search for 'maxpct'
> 
> for existing filesystems you can use xfs_db to rewrite this value

The problem is that inodes are allocated in "clusters" of blocks.

If your free blocks aren't such that they can form a cluster, I think
you're out of luck when trying to allocate new inodes if your existing
clusters are full.

-Eric

Re: Allocating inodes from a single block

[Nathan Scott]

On Tue, 2007-07-17 at 20:43 -0500, Eric Sandeen wrote:
> Chris Wedgwood wrote:
> > On Tue, Jul 17, 2007 at 11:11:50AM -0700, Michael Nishimoto wrote:
> > 
> >> Filesystem free space becomes fragmented over time.  It's possible
> >> for total free space to be a decent size and still not have a chunk
> >> large enough to allocate new inodes.
> > 
> > by default there is a restriction that indoes shouldn't consume more
> > that 25% of the total space
> > 
> > see the mkfs.xfs man-page for details, search for 'maxpct'
> > 
> > for existing filesystems you can use xfs_db to rewrite this value

FWIW, xfs_growfs can be used to change this online.

> The problem is that inodes are allocated in "clusters" of blocks.
> 
> If your free blocks aren't such that they can form a cluster, I think
> you're out of luck when trying to allocate new inodes if your existing
> clusters are full.

Have you looked into this much Mike?  I've not recently, but from a
quick peek it looks like the cluster size is set in xfs_mount.c as
mp->m_inode_cluster_size and a different value is used depending on
the machines memory size ... so, perhaps this can be made a mount
option?  (XFS_INODE_SMALL_CLUSTER_SIZE is 1FSB AFAICT).  But, maybe
I'm missing something or not remembering some details here that'd
make that infeasible.

Even better than a mount option would be to degrade to smaller size
dynamically... not sure how hard that'd be either ... probably lots
of corner cases lurking there.

cheers.

--
Nathan

Re: Allocating inodes from a single block

[David Chinner]

On Wed, Jul 18, 2007 at 12:01:30PM +1000, Nathan Scott wrote:
> On Tue, 2007-07-17 at 20:43 -0500, Eric Sandeen wrote:
> > Chris Wedgwood wrote:
> > > On Tue, Jul 17, 2007 at 11:11:50AM -0700, Michael Nishimoto wrote:
> > > 
> > >> Filesystem free space becomes fragmented over time.  It's possible
> > >> for total free space to be a decent size and still not have a chunk
> > >> large enough to allocate new inodes.
> > > 
> > > by default there is a restriction that indoes shouldn't consume more
> > > that 25% of the total space
> > > 
> > > see the mkfs.xfs man-page for details, search for 'maxpct'
> > > 
> > > for existing filesystems you can use xfs_db to rewrite this value
> 
> FWIW, xfs_growfs can be used to change this online.
> 
> > The problem is that inodes are allocated in "clusters" of blocks.
> > 
> > If your free blocks aren't such that they can form a cluster, I think
> > you're out of luck when trying to allocate new inodes if your existing
> > clusters are full.
> 
> Have you looked into this much Mike?  I've not recently, but from a
> quick peek it looks like the cluster size is set in xfs_mount.c as
> mp->m_inode_cluster_size and a different value is used depending on
> the machines memory size ... so, perhaps this can be made a mount
> option?  (XFS_INODE_SMALL_CLUSTER_SIZE is 1FSB AFAICT).  But, maybe
> I'm missing something or not remembering some details here that'd
> make that infeasible.

The issue here is not the cluster size - that is purely an in-memory
arrangement for reading/writing muliple inodes at once. The issue
here is inode *chunks* (as Eric pointed out).

Basically, each record in the AGI btree has a 64 bit but-field for
indicating whether the inodes in the chunk are used or free and a
64bit address of the first block of the inode chunk.

It is assumed that all the inodes in the chunk are contiguous as
they are addressed in a compressed form - AG #, block # of first inode,
inode number in chunk.

That means that:

	a) the inode size across the entire AG must be fixed
	b) the inodes must be allocated in contiguous chunks of
	   64 inodes regardless of their size

To change this, you need to completely change the AGI format, the
inode allocation code and the inode freeing code and all the code that
assumes that inodes appear in 64 inode chunks e.g. bulkstat. Then
repair, xfs_db, mkfs, check, etc....

The best you can do to try to avoid these sorts of problems is
use the "ikeep" option to keep empty inode chunks around. That way
if you remove a bunch of files then fragement free space you'll
still be able to create new files until you run out of pre-allocated
inodes....

> Even better than a mount option would be to degrade to smaller size
> dynamically... not sure how hard that'd be either ... probably lots
> of corner cases lurking there.

And a major on-disk format change.

Cheers,

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

Re: Allocating inodes from a single block

[Michael Nishimoto]

David Chinner wrote:

>On Wed, Jul 18, 2007 at 12:01:30PM +1000, Nathan Scott wrote:
>  
>
>>On Tue, 2007-07-17 at 20:43 -0500, Eric Sandeen wrote:
>>    
>>
>>>Chris Wedgwood wrote:
>>>      
>>>
>>>>On Tue, Jul 17, 2007 at 11:11:50AM -0700, Michael Nishimoto wrote:
>>>>
>>>>        
>>>>
>>>>>Filesystem free space becomes fragmented over time.  It's possible
>>>>>for total free space to be a decent size and still not have a chunk
>>>>>large enough to allocate new inodes.
>>>>>          
>>>>>
>>>>by default there is a restriction that indoes shouldn't consume more
>>>>that 25% of the total space
>>>>
>>>>see the mkfs.xfs man-page for details, search for 'maxpct'
>>>>
>>>>for existing filesystems you can use xfs_db to rewrite this value
>>>>        
>>>>
>>FWIW, xfs_growfs can be used to change this online.
>>
>>    
>>
>>>The problem is that inodes are allocated in "clusters" of blocks.
>>>
>>>If your free blocks aren't such that they can form a cluster, I think
>>>you're out of luck when trying to allocate new inodes if your existing
>>>clusters are full.
>>>      
>>>
>>Have you looked into this much Mike?  I've not recently, but from a
>>quick peek it looks like the cluster size is set in xfs_mount.c as
>>mp->m_inode_cluster_size and a different value is used depending on
>>the machines memory size ... so, perhaps this can be made a mount
>>option?  (XFS_INODE_SMALL_CLUSTER_SIZE is 1FSB AFAICT).  But, maybe
>>I'm missing something or not remembering some details here that'd
>>make that infeasible.
>>    
>>
>
>The issue here is not the cluster size - that is purely an in-memory
>arrangement for reading/writing muliple inodes at once. The issue
>here is inode *chunks* (as Eric pointed out).
>
>Basically, each record in the AGI btree has a 64 bit but-field for
>indicating whether the inodes in the chunk are used or free and a
>64bit address of the first block of the inode chunk.
>
>It is assumed that all the inodes in the chunk are contiguous as
>they are addressed in a compressed form - AG #, block # of first inode,
>inode number in chunk.
>
>That means that:
>
>	a) the inode size across the entire AG must be fixed
>	b) the inodes must be allocated in contiguous chunks of
>	   64 inodes regardless of their size
>
>To change this, you need to completely change the AGI format, the
>inode allocation code and the inode freeing code and all the code that
>assumes that inodes appear in 64 inode chunks e.g. bulkstat. Then
>repair, xfs_db, mkfs, check, etc....
>
>The best you can do to try to avoid these sorts of problems is
>use the "ikeep" option to keep empty inode chunks around. That way
>if you remove a bunch of files then fragement free space you'll
>still be able to create new files until you run out of pre-allocated
>inodes....
>
>  
>
>>Even better than a mount option would be to degrade to smaller size
>>dynamically... not sure how hard that'd be either ... probably lots
>>of corner cases lurking there.
>>    
>>
>
>And a major on-disk format change.
>
>Cheers,
>
>Dave.
>  
>
Dave,

There certainly are alot of places where code will need to change, but
the changes might not be as dramatic if we assume that the ondisk
format stays mostly the same.

One of the ideas that we've been tossing around is to steal a single byte
from xfs_inobt_rec and use it as a bitmap to indicate which of the blocks
within an 8 block chunk have inodes allocated in them.  We certainly haven't
gone through all the places in the code that need to change; and hence, 
don't
understand the entire magnitude of this change, but it looks
like this might allow ondisk formats to remain backwards compatible.

We were thinking that it's possible to steal a byte from ir_freecount
because that field doesn't need 32 bits.

thanks for the input,

   Michael

Re: Allocating inodes from a single block

[Mike Montour]

David Chinner wrote:
> The issue here is not the cluster size - that is purely an in-memory
> arrangement for reading/writing muliple inodes at once. The issue
> here is inode *chunks* (as Eric pointed out).
>
> [...]
> The best you can do to try to avoid these sorts of problems is
> use the "ikeep" option to keep empty inode chunks around. That way
> if you remove a bunch of files then fragement free space you'll
> still be able to create new files until you run out of pre-allocated
> inodes....
>   

What would it take to add an option to mkfs.xfs (or to create a
dedicated tool) that would efficiently[1] pre-allocate a specified
number of inode chunks when a filesystem is created? I know that XFS's
dynamic inode allocation is usually considered a "feature" relative to
filesystems like ext3, but there are cases where it's important to know
that you will not run out of inodes due to free-space fragmentation.
Note that "df -i" will still report a large number of "free inodes" when
this happens, so it's hard for a userspace application to know why it
got an error:

linux:~# df -i
Filesystem Inodes IUsed IFree IUse% Mounted on
/dev/cciss/c0d1p1 28353238 1873216 26480022 7% /mnt

linux:~# df
Filesystem 1k-blocks Used Available Use% Mounted on
/dev/cciss/c0d1p1 429977152 377017108 52960044 88% /mnt

gn1-a-1:~# xfs_db -r /dev/cciss/c0d1p1 -c "freesp -s"
   from to extents blocks pct
      1 1 128231 128231 0.97
      2 3 223964 555531 4.20
      4 7 400255 2113089 15.97
      8 15 838820 10436529 78.86
     16 31 8 128 0.00
total free extents 1591278
total free blocks 13233508
average free extent size 8.31628

This filesystem was created with "-i maxpct=0,size=2048", so a new chunk
of 64 inodes would require an extent of 128 KiB (32 * 4KiB blocks).

1. "efficiently" = significantly faster than a userspace script to
'touch' a few million files and then 'rm' them.

Re: Allocating inodes from a single block

[David Chinner]

On Wed, Jul 18, 2007 at 12:10:39PM -0700, Mike Montour wrote:
> David Chinner wrote:
> > The issue here is not the cluster size - that is purely an in-memory
> > arrangement for reading/writing muliple inodes at once. The issue
> > here is inode *chunks* (as Eric pointed out).
> >
> > [...]
> > The best you can do to try to avoid these sorts of problems is
> > use the "ikeep" option to keep empty inode chunks around. That way
> > if you remove a bunch of files then fragement free space you'll
> > still be able to create new files until you run out of pre-allocated
> > inodes....
> >   
> 
> What would it take to add an option to mkfs.xfs (or to create a
> dedicated tool) that would efficiently[1] pre-allocate a specified
> number of inode chunks when a filesystem is created?

Like an extension to mkfs.xfs's prototype file?

> This filesystem was created with "-i maxpct=0,size=2048", so a new chunk
> of 64 inodes would require an extent of 128 KiB (32 * 4KiB blocks).

i.e. worst case.

> 1. "efficiently" = significantly faster than a userspace script to
> 'touch' a few million files and then 'rm' them.

A "bulk create" option has long been considered to optimise filesystem
restore - precreating lots of inodes in an efficient manner is pretty
much a prereq for this.

The other option (and one that I prefer) is extending xfs_fsr to b
able to defragment free space. i.e. to compact space in each AG. To
do this efficiently, however, we really need a reverse map to determine
the owners of the blocks we want to move...

Cheers,

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

Re: Allocating inodes from a single block

[Mike Montour]

David Chinner wrote:
>> What would it take to add an option to mkfs.xfs (or to create a
>> dedicated tool) that would efficiently[1] pre-allocate a specified
>> number of inode chunks when a filesystem is created?
>>     
>
> Like an extension to mkfs.xfs's prototype file?
>   
I guess it could go there, e.g. the "number of inodes" parameter on line
2 of the prototype file (which is currently "merely for backward
compatibility"). Another possibility would be a "-i minpct=N" parameter
to mkfs.xfs, i.e. reserve N percent of the space on the disk for inodes,
and after that's full then allocate more chunks dynamically until the
"maxpct" limit is reached.

Ideally this pre-allocation would be able to reserve space for the inode
chunks without actually having to write to all of those disk blocks
(e.g. to be able to dedicate 25% of a 2 TB device to 1024-byte inodes
without having to write 500 GB of data to the device). I am not familiar
enough with the XFS data structures to know whether this would be an
easy or a hard thing to do.

>> This filesystem was created with "-i maxpct=0,size=2048", so a new chunk
>> of 64 inodes would require an extent of 128 KiB (32 * 4KiB blocks).
>>     
>
> i.e. worst case.
>   
Yes, although in this case the "maxpct" didn't matter because less than
25% of the disk was being used for inodes when the problem was
encountered. It is likely to occur with smaller inodes, but it can still
happen.

Re: Allocating inodes from a single block

[David Chinner]

Hi Michael,

Sorry for taking so long to get back to you on this; this mail
never got through to my @sgi.com account and I only just noticed
it earlier today when trolling my personal email account....

Michael Nishimoto <miken@agami.com> wrote:
> David Chinner wrote:
> >The issue here is not the cluster size - that is purely an in-memory
> >arrangement for reading/writing muliple inodes at once. The issue
> >here is inode *chunks* (as Eric pointed out).
> >
> >Basically, each record in the AGI btree has a 64 bit but-field for
> >indicating whether the inodes in the chunk are used or free and a
> >64bit address of the first block of the inode chunk.
> >
> >It is assumed that all the inodes in the chunk are contiguous as
> >they are addressed in a compressed form - AG #, block # of first inode,
> >inode number in chunk.
> >
> >That means that:
> >
> >	a) the inode size across the entire AG must be fixed
> >	b) the inodes must be allocated in contiguous chunks of
> >	   64 inodes regardless of their size
> >
> >To change this, you need to completely change the AGI format, the
> >inode allocation code and the inode freeing code and all the code that
> >assumes that inodes appear in 64 inode chunks e.g. bulkstat. Then
> >repair, xfs_db, mkfs, check, etc....
> >
> >The best you can do to try to avoid these sorts of problems is
> >use the "ikeep" option to keep empty inode chunks around. That way
> >if you remove a bunch of files then fragement free space you'll
> >still be able to create new files until you run out of pre-allocated
> >inodes....
> 
> There certainly are alot of places where code will need to change, but
> the changes might not be as dramatic if we assume that the ondisk
> format stays mostly the same.

Ok....

> One of the ideas that we've been tossing around is to steal a single byte
> from xfs_inobt_rec and use it as a bitmap to indicate which of the blocks
> within an 8 block chunk have inodes allocated in them.  We certainly haven't
> gone through all the places in the code that need to change; and hence, 
> don't
> understand the entire magnitude of this change, but it looks
> like this might allow ondisk formats to remain backwards compatible.

It's not backward compatible - the moment you allocate a
short chunk you need to set a new version bit in either the SB or
the AGI because older kernels will interpret the freecount in the
xfs_inobt_rec incorrectly.

> We were thinking that it's possible to steal a byte from ir_freecount
> because that field doesn't need 32 bits.

True, but I don't think the code complexity is really an issue here.
The issue is what it would do to the way stuff gets stored on disk
and the impact that has on everything else:

	a) reduces the inodes per AGI btree record.
		- tree gets deeper
		- tree requires more blocks
		- tree requires more frequent splits
		- tree gets more fragmented as the number of blocks
		  it requires increases near ENOSPC when space is
		  typically fragmented.
		- i.e. tree takes longer to write back and has a higher
		  log overhead
		- transaction reservations need increasing as tree
		  depth is no longer a function of AG size (*nasty*).
		  i.e. less allocation transaction on the fly at once
		  and greater potential for reservation overruns.
		- free inode searches take longer (already a limiting factor)
		- searching left+right is no longer symmetric so
		  we'd lose some determinism

	b) places small blocks into the filesystem on a much longer
	   term than single block file data
		- increases long term free space fragmenation
		- less likely to coalesce free space into large extents
		  as old data is freed up.
	
	c) inode clusters are placed further apart.
		- more seeks for directory traversal + stat workloads
		- slower writeback due to more seeks
	
	d) inode clusters limited to smallest allocation size
		- more I/O to read and write inodes
		- more seeks for directory traversal + stat workloads
		- slower writeback due to more seeks

The inode cluster issues could be solved, but it's still a nasty
thing because the inode caching code does not know about different
cluster sizes and there's no easy way to propagate that info from
the btree.

However, I still don't think that going to single block inode clusters
make a lot of sense given the amount of effort we go to everywhere
else to ensure large contiguous allocations. To me it seems like a
step backwards - it's not a solution to the general free space
fragmentation situation that XFS can get itself into, and that's
the problem we really need to fix.

FWIW, when we fragment data files, we use xfs_fsr to fix it up and
we have mechanisms in the kernel for optimising and ensuring
correctness of that operation.  We should treat free-space
fragmentation the same way because, like data file fragmentation,
it's not something that is a common problem and it can be fixed
up from userspace.....

FWIW-2, free space defragmentation for xfs_fsr is something
that has long been on the to-do list, but this problem is rare
enough that it's never been a high priority to implement....

Cheers,

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