Why ext3 uses different policies to allocate inodes for dirs and files?

Why ext3 uses different policies to allocate inodes for dirs and files?

[Xin Zhao]

The policy seems to distribute dir inodes uniformly on all block
groups. Why do we want to do this?  Isn't it better to create a dir
inode close to its parent dir inode?

Thanks in advance for your help!

Xin

RE: Why ext3 uses different policies to allocate inodes for dirs and files?

[Joseph D. Wagner]

> The policy seems to distribute dir inodes uniformly on all block
> groups. Why do we want to do this?  Isn't it better to create a dir
> inode close to its parent dir inode?

Directories can, and frequently are, moved.  If you kept the dir inode close to its parent dir inode, you'd have to move dir inodes around every time you move directories.  Less is more.

Keeping the dir inodes uniform means the time to perform a name->inode lookup is relatively the same regardless of directory.  While admittedly this does not always yield the fastest performance, in this case we prefer consistency over speed.

I'm sure there are other good reasons too, but these two are enough to justify it.

Joseph D. Wagner

Re: Why ext3 uses different policies to allocate inodes for dirs and files?

[Andreas Dilger]

On Mar 06, 2006  23:24 -0600, Joseph D. Wagner wrote:
> > The policy seems to distribute dir inodes uniformly on all block
> > groups. Why do we want to do this?  Isn't it better to create a dir
> > inode close to its parent dir inode?
> 
> Directories can, and frequently are, moved.  If you kept the dir inode
> close to its parent dir inode, you'd have to move dir inodes around
> every time you move directories.  Less is more.

I'm not sure what it is you are saying.  Directories may be renamed, but
the inodes are never moved.

The reason that directory inodes are spread across the disk is that this
allows later balancing of the file inodes that are created within each
directory.  If all of the parent directories are kept in the same group,
you would just end up having all inodes at the start of the filesystem
in use, with high fragmentation and no locality between directories and
the files created therein, and similar problems with inode blocks.

Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.

RE: Why ext3 uses different policies to allocate inodes for dirs and files?

[Joseph D. Wagner]

> I'm not sure what it is you are saying.  Directories may be renamed, but
> the inodes are never moved.

That is what I meant to say.  I should have been clearer between when I said "directories" and "dir inodes".  When I said "directories" I was referring to the names.  By "directories are moved" I was referring to how you can rename a directory in such a way as to change its name within the hierarchy.  For example:

mv -R /usr/local/lib/i386-redhat-linux/ /usr/lib/

Assuming that the source and destination are the same partition, this "move" operation is actually a simple "rename".  The "dir inode" listing of "i386-redhat-linux" is removed from the "/usr/local/lib/" directory list and added to the "/usr/lib/" directory list.

If the "dir inode" were to be moved closer to the "parent dir inode", this would become quite an expensive "move" operation, as it would have to move all of the "dir inodes" of the "i386-redhat-linux" directory and all subdirectories away from the "parent dir inode" of "/usr/local/lib/" and closer to the "parent dir inode" of "/usr/lib/".

Like I said, this is just one of several reasons why "dir inodes" are spread out more uniformly throughout the partition, rather than kept close to their "parent dir inode".

Sorry I wasn't clearer.

Joseph D. Wagner

Re: Why ext3 uses different policies to allocate inodes for dirs and files?

[Matthew Wilcox]

On Tue, Mar 07, 2006 at 09:34:53AM -0600, Joseph D. Wagner wrote:
> > I'm not sure what it is you are saying.  Directories may be renamed, but
> > the inodes are never moved.
> 
> If the "dir inode" were to be moved closer to the "parent dir inode", this would become quite an expensive "move" operation, as it would have to move all of the "dir inodes" of the "i386-redhat-linux" directory and all subdirectories away from the "parent dir inode" of "/usr/local/lib/" and closer to the "parent dir inode" of "/usr/lib/".

inodes are allocated once and never moved.  We're talking about initial
allocation.  So even though files have their inodes allocated near
their parent directory's inode, their inode is not moved when moved to
another directory.

The reason, as Andreas said, is that if we did allocate directory inodes
near their parent inode, we would end up just filling up from the start
of the drive and never spreading out.