1 Index: lum/fs/ext3/ialloc.c
2 ===================================================================
3 --- lum.orig/fs/ext3/ialloc.c 2004-08-26 13:14:35.000000000 -0600
4 +++ lum/fs/ext3/ialloc.c 2004-08-31 15:00:35.000000000 -0600
5 @@ -327,8 +327,130 @@ int ext3_itable_block_used(struct super_
6 * directories already is chosen.
8 * For other inodes, search forward from the parent directory's block
9 - * group to find a free inode.
10 + * group to find a free inode in a group with some free blocks.
12 +static int find_group_dir(struct super_block *sb, const struct inode *parent,
13 + struct ext3_group_desc **best_desc,
14 + struct buffer_head **best_bh)
16 + struct ext3_sb_info *sbi = EXT3_SB(sb);
17 + int ngroups = sbi->s_groups_count;
19 + struct ext3_group_desc *desc;
20 + struct buffer_head *bh;
21 + int group, best_group = -1, ndir_best = 999999999;
26 + avefreei = le32_to_cpu(sbi->s_es->s_free_inodes_count) / ngroups;
28 + for (group = 0; group < ngroups; group++) {
29 + desc = ext3_get_group_desc(sb, group, &bh);
30 + if (!desc || !desc->bg_free_inodes_count)
32 + if (le16_to_cpu(desc->bg_free_inodes_count) < avefreei)
34 + if (le16_to_cpu(desc->bg_used_dirs_count) > ndir_best)
37 + (le16_to_cpu(desc->bg_free_blocks_count) >
38 + le16_to_cpu((*best_desc)->bg_free_blocks_count))) {
42 + ndir_best = le16_to_cpu(desc->bg_used_dirs_count);
49 +static int find_group_other(struct super_block *sb, const struct inode *parent,
50 + struct ext3_group_desc **best_desc,
51 + struct buffer_head **best_bh)
53 + struct ext3_sb_info *sbi = EXT3_SB(sb);
54 + int parent_group = EXT3_I(parent)->i_block_group;
55 + int ngroups = sbi->s_groups_count;
57 + struct ext3_group_desc *desc;
58 + struct buffer_head *bh;
59 + int group, i, best_group = -1;
65 + * Try to place the inode in its parent directory
67 + group = parent_group;
68 + desc = ext3_get_group_desc (sb, group, &bh);
69 + if (desc && le16_to_cpu(desc->bg_free_inodes_count) &&
70 + le16_to_cpu(desc->bg_free_blocks_count)) {
77 + * We're going to place this inode in a different blockgroup from its
78 + * parent. We want to cause files in a common directory to all land in
79 + * the same blockgroup if it has space. But we want files which are
80 + * in a different directory which shares a blockgroup with our parent
81 + * to land in a different blockgroup.
83 + * So add our directory's i_ino into the starting point for the hash.
85 + group = (group + parent->i_ino) % ngroups;
87 + avefreeb = le32_to_cpu(sbi->s_es->s_free_blocks_count) /
88 + sbi->s_groups_count / ngroups;
91 + * Use a quadratic hash to find a group with a free inode and some free
94 + for (i = 1; i < ngroups; i <<= 1) {
96 + if (group >= ngroups)
98 + desc = ext3_get_group_desc(sb, group, &bh);
99 + if (!desc || !desc->bg_free_inodes_count)
101 + if (le16_to_cpu(desc->bg_free_blocks_count) > avefreeb) {
109 + * That failed: try linear search for a group with free inodes and
110 + * preferrably free blocks, returning as soon as we find a good one.
112 + group = sbi->s_last_group;
113 + for (i = 0; i < ngroups; i++) {
114 + if (++group >= ngroups)
116 + desc = ext3_get_group_desc(sb, group, &bh);
117 + if (!desc || !desc->bg_free_inodes_count)
120 + (le16_to_cpu(desc->bg_free_blocks_count) >
121 + le16_to_cpu((*best_desc)->bg_free_blocks_count))) {
124 + best_group = group;
125 + if (le16_to_cpu(desc->bg_free_blocks_count) >= avefreeb)
129 + sbi->s_last_group = best_group;
134 struct inode * ext3_new_inode (handle_t *handle,
135 const struct inode * dir, int mode,
137 @@ -336,11 +459,10 @@ struct inode * ext3_new_inode (handle_t
138 struct super_block * sb;
139 struct buffer_head * bh;
140 struct buffer_head * bh2;
141 - int i, j, avefreei;
143 struct inode * inode;
145 struct ext3_group_desc * gdp;
146 - struct ext3_group_desc * tmp;
147 struct ext3_super_block * es;
148 struct ext3_iloc iloc;
150 @@ -392,72 +514,10 @@ struct inode * ext3_new_inode (handle_t
157 - if (S_ISDIR(mode)) {
158 - avefreei = le32_to_cpu(es->s_free_inodes_count) /
159 - sb->u.ext3_sb.s_groups_count;
161 - for (j = 0; j < sb->u.ext3_sb.s_groups_count; j++) {
162 - struct buffer_head *temp_buffer;
163 - tmp = ext3_get_group_desc (sb, j, &temp_buffer);
165 - le16_to_cpu(tmp->bg_free_inodes_count) &&
166 - le16_to_cpu(tmp->bg_free_inodes_count) >=
168 - if (!gdp || (le16_to_cpu(tmp->bg_free_blocks_count) >
169 - le16_to_cpu(gdp->bg_free_blocks_count))) {
179 - * Try to place the inode in its parent directory
181 - i = dir->u.ext3_i.i_block_group;
182 - tmp = ext3_get_group_desc (sb, i, &bh2);
183 - if (tmp && le16_to_cpu(tmp->bg_free_inodes_count))
188 - * Use a quadratic hash to find a group with a
191 - for (j = 1; j < sb->u.ext3_sb.s_groups_count; j <<= 1) {
193 - if (i >= sb->u.ext3_sb.s_groups_count)
194 - i -= sb->u.ext3_sb.s_groups_count;
195 - tmp = ext3_get_group_desc (sb, i, &bh2);
197 - le16_to_cpu(tmp->bg_free_inodes_count)) {
205 - * That failed: try linear search for a free inode
207 - i = dir->u.ext3_i.i_block_group + 1;
208 - for (j = 2; j < sb->u.ext3_sb.s_groups_count; j++) {
209 - if (++i >= sb->u.ext3_sb.s_groups_count)
211 - tmp = ext3_get_group_desc (sb, i, &bh2);
213 - le16_to_cpu(tmp->bg_free_inodes_count)) {
221 + i = find_group_dir(sb, dir, &gdp, &bh2);
223 + i = find_group_other(sb, dir, &gdp, &bh2);
227 Index: lum/include/linux/ext3_fs_sb.h
228 ===================================================================
229 --- lum.orig/include/linux/ext3_fs_sb.h 2004-08-26 13:28:53.000000000 -0600
230 +++ lum/include/linux/ext3_fs_sb.h 2004-08-31 11:04:27.000000000 -0600
231 @@ -45,6 +45,7 @@ struct ext3_sb_info {
232 unsigned long s_gdb_count; /* Number of group descriptor blocks */
233 unsigned long s_desc_per_block; /* Number of group descriptors per block */
234 unsigned long s_groups_count; /* Number of groups in the fs */
235 + unsigned long s_last_group; /* Last group used for inode allocation */
236 struct buffer_head * s_sbh; /* Buffer containing the super block */
237 struct ext3_super_block * s_es; /* Pointer to the super block in the buffer */
238 struct buffer_head ** s_group_desc;