Re: File System Performance

[Andreas Dilger]

On Nov 12, 2001  23:34 -0700, Richard Gooch wrote:
> > Currently, without any patching, any new directory will be put in a
> > different block group from its parent.
> 
> Your statement seems inconsistent with the comment above
> fs/ext2/ialloc.c:ext2_new_inode():
> /*
>  * There are two policies for allocating an inode.  If the new inode is
>  * a directory, then a forward search is made for a block group with both
>  * free space and a low directory-to-inode ratio; if that fails, then of
>  * the groups with above-average free space, that group with the fewest
>  * directories already is chosen.
>  *
>  * For other inodes, search forward from the parent directory\'s block
>  * group to find a free inode.
>  */

This is only a comment, and not actual code.  The code looks like:

	if (S_ISDIR(mode)) {
		int avefreei = le32_to_cpu(es->s_free_inodes_count) /
			sb->u.ext2_sb.s_groups_count;

		/* Place directory in a group with free inodes and blocks. */
		for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
			tmp = ext2_get_group_desc (sb, j, &bh2);
			if (tmp && le16_to_cpu(tmp->bg_free_inodes_count) &&
			    le16_to_cpu(tmp->bg_free_inodes_count) >= avefreei){
				if (!gdp ||
				    (le16_to_cpu(tmp->bg_free_blocks_count) >
				     le16_to_cpu(gdp->bg_free_blocks_count))) {
					group = j;
					gdp = tmp;
				}
			}
		}
	} else {

So, as you can see, it searches all of the directories for a group which:
a) has any free inodes (redundant with (b), actually)
b) has more than the average number of free inodes
c) has the most free blocks

> So N successive calls to mkdir(2), with the same parent, should result
> in those directories being stored in the same block group as each
> other. And, furthermore, if the parent directory block group is mostly
> empty, then the child directories are placed adjacent to the parent's
> block group.

So, as we see above, the starting directory is irrelevant.  We pick the
best directory with an exhaustive search of all block groups.  Note that
you are correct in that IF the parent block group is mostly empty, then
subdirectories would also be placed there, but the nature of the algorithm
is that EVERYTHING would go there until it is not "better" than any other
group, at which case we have approximately round-robin group allocation.

Maybe a better heuristic is to add a "bonus" to the parent directory's
group, so other things being equal we stay in the same group.  This gives
us some advantage of clustering, but also allows a global optimal choice
to be made in case we are looking for a new group.

> > Now does this make sence?
> 
> It would, if you were correct about the current implementation. Which
> I think isn't the case.
> 
> > Not currently, but the patch that is out will do this.
> 
> I think it currently *does*. Check the comment. Straight from the
> 2.4.14 sources.

You shouldn't base arguments on a comment, because they tend to not be
updated along with changes to the code.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/