Index: linux-2.4.21-suse2/fs/ext3/ialloc.c =================================================================== --- linux-2.4.21-suse2.orig/fs/ext3/ialloc.c 2005-08-04 09:14:23.000000000 -0600 +++ linux-2.4.21-suse2/fs/ext3/ialloc.c 2005-08-04 09:17:49.000000000 -0600 @@ -328,19 +328,140 @@ * directories already is chosen. * * For other inodes, search forward from the parent directory's block - * group to find a free inode. + * group to find a free inode in a group with some free blocks. */ +static int find_group_dir(struct super_block *sb, const struct inode *parent, + struct ext3_group_desc **best_desc, + struct buffer_head **best_bh) +{ + struct ext3_sb_info *sbi = EXT3_SB(sb); + int ngroups = sbi->s_groups_count; + int avefreei; + struct ext3_group_desc *desc; + struct buffer_head *bh; + int group, best_group = -1, ndir_best = 999999999; + + *best_desc = NULL; + *best_bh = NULL; + + avefreei = le32_to_cpu(sbi->s_es->s_free_inodes_count) / ngroups; + + for (group = 0; group < ngroups; group++) { + desc = ext3_get_group_desc(sb, group, &bh); + if (!desc || !desc->bg_free_inodes_count) + continue; + if (le16_to_cpu(desc->bg_free_inodes_count) < avefreei) + continue; + if (le16_to_cpu(desc->bg_used_dirs_count) > ndir_best) + continue; + if (!*best_desc || + (le16_to_cpu(desc->bg_free_blocks_count) > + le16_to_cpu((*best_desc)->bg_free_blocks_count))) { + *best_bh = bh; + *best_desc = desc; + best_group = group; + ndir_best = le16_to_cpu(desc->bg_used_dirs_count); + } + } + + return best_group; +} + +static int find_group_other(struct super_block *sb, const struct inode *parent, + struct ext3_group_desc **best_desc, + struct buffer_head **best_bh) +{ + struct ext3_sb_info *sbi = EXT3_SB(sb); + int parent_group = EXT3_I(parent)->i_block_group; + int ngroups = sbi->s_groups_count; + int avefreeb; + struct ext3_group_desc *desc; + struct buffer_head *bh; + int group, i, best_group = -1; + + *best_desc = NULL; + *best_bh = NULL; + + /* + * Try to place the inode in its parent directory + */ + group = parent_group; + desc = ext3_get_group_desc (sb, group, &bh); + if (desc && le16_to_cpu(desc->bg_free_inodes_count) && + le16_to_cpu(desc->bg_free_blocks_count)) { + *best_desc = desc; + *best_bh = bh; + return group; + } + + /* + * We're going to place this inode in a different blockgroup from its + * parent. We want to cause files in a common directory to all land in + * the same blockgroup if it has space. But we want files which are + * in a different directory which shares a blockgroup with our parent + * to land in a different blockgroup. + * + * So add our directory's i_ino into the starting point for the hash. + */ + group = (group + parent->i_ino) % ngroups; + + avefreeb = le32_to_cpu(sbi->s_es->s_free_blocks_count) / + sbi->s_groups_count / ngroups; + + /* + * Use a quadratic hash to find a group with a free inode and some free + * blocks. + */ + for (i = 1; i < ngroups; i <<= 1) { + group += i; + if (group >= ngroups) + group -= ngroups; + desc = ext3_get_group_desc(sb, group, &bh); + if (!desc || !desc->bg_free_inodes_count) + continue; + if (le16_to_cpu(desc->bg_free_blocks_count) > avefreeb) { + *best_bh = bh; + *best_desc = desc; + return group; + } + } + + /* + * That failed: try linear search for a group with free inodes and + * preferrably free blocks, returning as soon as we find a good one. + */ + group = sbi->s_last_group; + for (i = 0; i < ngroups; i++) { + if (++group >= ngroups) + group = 0; + desc = ext3_get_group_desc(sb, group, &bh); + if (!desc || !desc->bg_free_inodes_count) + continue; + if (!*best_desc || + (le16_to_cpu(desc->bg_free_blocks_count) > + le16_to_cpu((*best_desc)->bg_free_blocks_count))) { + *best_bh = bh; + *best_desc = desc; + best_group = group; + if (le16_to_cpu(desc->bg_free_blocks_count) >= avefreeb) + break; + } + } + sbi->s_last_group = best_group; + + return best_group; +} + struct inode * ext3_new_inode(handle_t *handle, const struct inode * dir, int mode, unsigned long goal) { struct super_block * sb; struct buffer_head * bh; struct buffer_head * bh2; - int i, j, avefreei; + int i, j; struct inode * inode; int bitmap_nr; struct ext3_group_desc * gdp; - struct ext3_group_desc * tmp; struct ext3_super_block * es; struct ext3_iloc iloc; int err = 0; @@ -392,72 +513,10 @@ } repeat: - gdp = NULL; - i = 0; - - if (S_ISDIR(mode)) { - avefreei = le32_to_cpu(es->s_free_inodes_count) / - sb->u.ext3_sb.s_groups_count; - if (!gdp) { - for (j = 0; j < sb->u.ext3_sb.s_groups_count; j++) { - struct buffer_head *temp_buffer; - tmp = ext3_get_group_desc (sb, j, &temp_buffer); - 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))) { - i = j; - gdp = tmp; - bh2 = temp_buffer; - } - } - } - } - } else { - /* - * Try to place the inode in its parent directory - */ - i = dir->u.ext3_i.i_block_group; - tmp = ext3_get_group_desc (sb, i, &bh2); - if (tmp && le16_to_cpu(tmp->bg_free_inodes_count)) - gdp = tmp; - else - { - /* - * Use a quadratic hash to find a group with a - * free inode - */ - for (j = 1; j < sb->u.ext3_sb.s_groups_count; j <<= 1) { - i += j; - if (i >= sb->u.ext3_sb.s_groups_count) - i -= sb->u.ext3_sb.s_groups_count; - tmp = ext3_get_group_desc (sb, i, &bh2); - if (tmp && - le16_to_cpu(tmp->bg_free_inodes_count)) { - gdp = tmp; - break; - } - } - } - if (!gdp) { - /* - * That failed: try linear search for a free inode - */ - i = dir->u.ext3_i.i_block_group + 1; - for (j = 2; j < sb->u.ext3_sb.s_groups_count; j++) { - if (++i >= sb->u.ext3_sb.s_groups_count) - i = 0; - tmp = ext3_get_group_desc (sb, i, &bh2); - if (tmp && - le16_to_cpu(tmp->bg_free_inodes_count)) { - gdp = tmp; - break; - } - } - } - } + if (S_ISDIR(mode)) + i = find_group_dir(sb, dir, &gdp, &bh2); + else + i = find_group_other(sb, dir, &gdp, &bh2); err = -ENOSPC; if (!gdp) Index: linux-2.4.21-suse2/include/linux/ext3_fs_sb.h =================================================================== --- linux-2.4.21-suse2.orig/include/linux/ext3_fs_sb.h 2005-08-04 09:14:21.000000000 -0600 +++ linux-2.4.21-suse2/include/linux/ext3_fs_sb.h 2005-08-04 09:19:32.000000000 -0600 @@ -45,6 +45,7 @@ unsigned long s_gdb_count; /* Number of group descriptor blocks */ unsigned long s_desc_per_block; /* Number of group descriptors per block */ unsigned long s_groups_count; /* Number of groups in the fs */ + unsigned long s_last_group; /* Last group used for inode allocation */ struct buffer_head * s_sbh; /* Buffer containing the super block */ struct ext3_super_block * s_es; /* Pointer to the super block in the buffer */ struct buffer_head ** s_group_desc;