2 * modified for Lites 1.1
4 * Aug 1995, Godmar Back (gback@cs.utah.edu)
5 * University of Utah, Department of Computer Science
10 * linux/fs/ext2/ialloc.c
12 * Copyright (C) 1992, 1993, 1994, 1995
13 * Remy Card (card@masi.ibp.fr)
14 * Laboratoire MASI - Institut Blaise Pascal
15 * Universite Pierre et Marie Curie (Paris VI)
17 * BSD ufs-inspired inode and directory allocation by
18 * Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
20 * This program is free software; you can redistribute it and/or modify
21 * it under the terms of the GNU General Public License as published by
22 * the Free Software Foundation; either version 2 of the License.
24 * This program is distributed in the hope that it will be useful,
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27 * GNU General Public License for more details.
29 * You should have received a copy of the GNU General Public License
30 * along with this program; if not, write to the Free Software
31 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
36 * The free inodes are managed by bitmaps. A file system contains several
37 * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
38 * block for inodes, N blocks for the inode table and data blocks.
40 * The file system contains group descriptors which are located after the
41 * super block. Each descriptor contains the number of the bitmap block and
42 * the free blocks count in the block. The descriptors are loaded in memory
43 * when a file system is mounted (see ext2_read_super).
46 #include <sys/param.h>
47 #include <sys/systm.h>
50 #include <sys/mount.h>
51 #include <sys/vnode.h>
53 #include <gnu/fs/ext2fs/inode.h>
54 #include <gnu/fs/ext2fs/ext2_mount.h>
55 #include <gnu/fs/ext2fs/ext2_extern.h>
56 #include <gnu/fs/ext2fs/ext2_fs.h>
57 #include <gnu/fs/ext2fs/ext2_fs_sb.h>
58 #include <gnu/fs/ext2fs/fs.h>
62 #include <gnu/fs/ext2fs/i386-bitops.h>
64 #include <gnu/fs/ext2fs/ext2_bitops.h>
67 /* this is supposed to mark a buffer dirty on ready for delayed writing
69 void mark_buffer_dirty(struct buf *bh)
74 bh->b_flags |= B_DIRTY;
78 struct ext2_group_desc * get_group_desc (struct mount * mp,
79 unsigned int block_group,
80 struct buffer_head ** bh)
82 struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
83 unsigned long group_desc;
85 struct ext2_group_desc * gdp;
87 if (block_group >= sb->s_groups_count)
88 panic ("get_group_desc: "
89 "block_group >= groups_count - "
90 "block_group = %d, groups_count = %lu",
91 block_group, sb->s_groups_count);
93 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
94 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
95 if (!sb->s_group_desc[group_desc])
96 panic ( "get_group_desc:"
97 "Group descriptor not loaded - "
98 "block_group = %d, group_desc = %lu, desc = %lu",
99 block_group, group_desc, desc);
100 gdp = (struct ext2_group_desc *)
101 sb->s_group_desc[group_desc]->b_data;
103 *bh = sb->s_group_desc[group_desc];
107 static void read_inode_bitmap (struct mount * mp,
108 unsigned long block_group,
109 unsigned int bitmap_nr)
111 struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
112 struct ext2_group_desc * gdp;
113 struct buffer_head * bh;
116 gdp = get_group_desc (mp, block_group, NULL);
117 if ((error = bread (VFSTOEXT2(mp)->um_devvp,
118 fsbtodb(sb, gdp->bg_inode_bitmap),
121 panic ( "read_inode_bitmap:"
122 "Cannot read inode bitmap - "
123 "block_group = %lu, inode_bitmap = %lu",
124 block_group, (unsigned long) gdp->bg_inode_bitmap);
125 sb->s_inode_bitmap_number[bitmap_nr] = block_group;
126 sb->s_inode_bitmap[bitmap_nr] = bh;
131 * load_inode_bitmap loads the inode bitmap for a blocks group
133 * It maintains a cache for the last bitmaps loaded. This cache is managed
134 * with a LRU algorithm.
137 * 1/ There is one cache per mounted file system.
138 * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
139 * this function reads the bitmap without maintaining a LRU cache.
141 static int load_inode_bitmap (struct mount * mp,
142 unsigned int block_group)
144 struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
146 unsigned long inode_bitmap_number;
147 struct buffer_head * inode_bitmap;
149 if (block_group >= sb->s_groups_count)
150 panic ("load_inode_bitmap:"
151 "block_group >= groups_count - "
152 "block_group = %d, groups_count = %lu",
153 block_group, sb->s_groups_count);
154 if (sb->s_loaded_inode_bitmaps > 0 &&
155 sb->s_inode_bitmap_number[0] == block_group)
157 if (sb->s_groups_count <= EXT2_MAX_GROUP_LOADED) {
158 if (sb->s_inode_bitmap[block_group]) {
159 if (sb->s_inode_bitmap_number[block_group] !=
161 panic ( "load_inode_bitmap:"
162 "block_group != inode_bitmap_number");
166 read_inode_bitmap (mp, block_group, block_group);
171 for (i = 0; i < sb->s_loaded_inode_bitmaps &&
172 sb->s_inode_bitmap_number[i] != block_group;
175 if (i < sb->s_loaded_inode_bitmaps &&
176 sb->s_inode_bitmap_number[i] == block_group) {
177 inode_bitmap_number = sb->s_inode_bitmap_number[i];
178 inode_bitmap = sb->s_inode_bitmap[i];
179 for (j = i; j > 0; j--) {
180 sb->s_inode_bitmap_number[j] =
181 sb->s_inode_bitmap_number[j - 1];
182 sb->s_inode_bitmap[j] =
183 sb->s_inode_bitmap[j - 1];
185 sb->s_inode_bitmap_number[0] = inode_bitmap_number;
186 sb->s_inode_bitmap[0] = inode_bitmap;
188 if (sb->s_loaded_inode_bitmaps < EXT2_MAX_GROUP_LOADED)
189 sb->s_loaded_inode_bitmaps++;
191 ULCK_BUF(sb->s_inode_bitmap[EXT2_MAX_GROUP_LOADED - 1])
192 for (j = sb->s_loaded_inode_bitmaps - 1; j > 0; j--) {
193 sb->s_inode_bitmap_number[j] =
194 sb->s_inode_bitmap_number[j - 1];
195 sb->s_inode_bitmap[j] =
196 sb->s_inode_bitmap[j - 1];
198 read_inode_bitmap (mp, block_group, 0);
204 void ext2_free_inode (struct inode * inode)
206 struct ext2_sb_info * sb;
207 struct buffer_head * bh;
208 struct buffer_head * bh2;
209 unsigned long block_group;
212 struct ext2_group_desc * gdp;
213 struct ext2_super_block * es;
218 if (inode->i_nlink) {
219 printf ("ext2_free_inode: inode has nlink=%d\n",
224 ext2_debug ("freeing inode %lu\n", inode->i_number);
227 lock_super (DEVVP(inode));
228 if (inode->i_number < EXT2_FIRST_INO ||
229 inode->i_number > sb->s_es->s_inodes_count) {
230 printf ("free_inode reserved inode or nonexistent inode");
231 unlock_super (DEVVP(inode));
235 block_group = (inode->i_number - 1) / EXT2_INODES_PER_GROUP(sb);
236 bit = (inode->i_number - 1) % EXT2_INODES_PER_GROUP(sb);
237 bitmap_nr = load_inode_bitmap (ITOV(inode)->v_mount, block_group);
238 bh = sb->s_inode_bitmap[bitmap_nr];
239 if (!clear_bit (bit, bh->b_data))
240 printf ( "ext2_free_inode:"
241 "bit already cleared for inode %lu",
242 (unsigned long)inode->i_number);
244 gdp = get_group_desc (ITOV(inode)->v_mount, block_group, &bh2);
245 gdp->bg_free_inodes_count++;
246 if (S_ISDIR(inode->i_mode))
247 gdp->bg_used_dirs_count--;
248 mark_buffer_dirty(bh2);
249 es->s_free_inodes_count++;
251 mark_buffer_dirty(bh);
253 if (sb->s_flags & MS_SYNCHRONOUS) {
254 ll_rw_block (WRITE, 1, &bh);
259 unlock_super (DEVVP(inode));
264 * This function increments the inode version number
266 * This may be used one day by the NFS server
268 static void inc_inode_version (struct inode * inode,
269 struct ext2_group_desc *gdp,
272 unsigned long inode_block;
273 struct buffer_head * bh;
274 struct ext2_inode * raw_inode;
276 inode_block = gdp->bg_inode_table + (((inode->i_number - 1) %
277 EXT2_INODES_PER_GROUP(inode->i_sb)) /
278 EXT2_INODES_PER_BLOCK(inode->i_sb));
279 bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
281 printf ("inc_inode_version Cannot load inode table block - "
282 "inode=%lu, inode_block=%lu\n",
283 inode->i_number, inode_block);
284 inode->u.ext2_i.i_version = 1;
287 raw_inode = ((struct ext2_inode *) bh->b_data) +
288 (((inode->i_number - 1) %
289 EXT2_INODES_PER_GROUP(inode->i_sb)) %
290 EXT2_INODES_PER_BLOCK(inode->i_sb));
291 raw_inode->i_version++;
292 inode->u.ext2_i.i_version = raw_inode->i_version;
299 * There are two policies for allocating an inode. If the new inode is
300 * a directory, then a forward search is made for a block group with both
301 * free space and a low directory-to-inode ratio; if that fails, then of
302 * the groups with above-average free space, that group with the fewest
303 * directories already is chosen.
305 * For other inodes, search forward from the parent directory\'s block
306 * group to find a free inode.
309 * this functino has been reduced to the actual 'find the inode number' part
311 ino_t ext2_new_inode (const struct inode * dir, int mode)
313 struct ext2_sb_info * sb;
314 struct buffer_head * bh;
315 struct buffer_head * bh2;
318 struct ext2_group_desc * gdp;
319 struct ext2_group_desc * tmp;
320 struct ext2_super_block * es;
326 lock_super (DEVVP(dir));
332 avefreei = es->s_free_inodes_count /
334 /* I am not yet convinced that this next bit is necessary.
335 i = dir->u.ext2_i.i_block_group;
336 for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
337 tmp = get_group_desc (sb, i, &bh2);
338 if ((tmp->bg_used_dirs_count << 8) <
339 tmp->bg_free_inodes_count) {
344 i = ++i % sb->u.ext2_sb.s_groups_count;
348 for (j = 0; j < sb->s_groups_count; j++) {
349 tmp = get_group_desc(ITOV(dir)->v_mount,j,&bh2);
350 if (tmp->bg_free_inodes_count &&
351 tmp->bg_free_inodes_count >= avefreei) {
353 (tmp->bg_free_blocks_count >
354 gdp->bg_free_blocks_count)) {
365 * Try to place the inode in its parent directory
367 i = dir->i_block_group;
368 tmp = get_group_desc (ITOV(dir)->v_mount, i, &bh2);
369 if (tmp->bg_free_inodes_count)
374 * Use a quadratic hash to find a group with a
377 for (j = 1; j < sb->s_groups_count; j <<= 1) {
379 if (i >= sb->s_groups_count)
380 i -= sb->s_groups_count;
381 tmp = get_group_desc(ITOV(dir)->v_mount,i,&bh2);
382 if (tmp->bg_free_inodes_count) {
390 * That failed: try linear search for a free inode
392 i = dir->i_block_group + 1;
393 for (j = 2; j < sb->s_groups_count; j++) {
394 if (++i >= sb->s_groups_count)
396 tmp = get_group_desc(ITOV(dir)->v_mount,i,&bh2);
397 if (tmp->bg_free_inodes_count) {
406 unlock_super (DEVVP(dir));
409 bitmap_nr = load_inode_bitmap (ITOV(dir)->v_mount, i);
410 bh = sb->s_inode_bitmap[bitmap_nr];
411 if ((j = find_first_zero_bit ((unsigned long *) bh->b_data,
412 EXT2_INODES_PER_GROUP(sb))) <
413 EXT2_INODES_PER_GROUP(sb)) {
414 if (set_bit (j, bh->b_data)) {
415 printf ( "ext2_new_inode:"
416 "bit already set for inode %d", j);
419 /* Linux now does the following:
420 mark_buffer_dirty(bh);
421 if (sb->s_flags & MS_SYNCHRONOUS) {
422 ll_rw_block (WRITE, 1, &bh);
426 mark_buffer_dirty(bh);
428 if (gdp->bg_free_inodes_count != 0) {
429 printf ( "ext2_new_inode:"
430 "Free inodes count corrupted in group %d",
432 unlock_super (DEVVP(dir));
437 j += i * EXT2_INODES_PER_GROUP(sb) + 1;
438 if (j < EXT2_FIRST_INO || j > es->s_inodes_count) {
439 printf ( "ext2_new_inode:"
440 "reserved inode or inode > inodes count - "
441 "block_group = %d,inode=%d", i, j);
442 unlock_super (DEVVP(dir));
445 gdp->bg_free_inodes_count--;
447 gdp->bg_used_dirs_count++;
448 mark_buffer_dirty(bh2);
449 es->s_free_inodes_count--;
450 /* mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1); */
452 unlock_super (DEVVP(dir));
457 static unsigned long ext2_count_free_inodes (struct mount * mp)
460 struct ext2_sb_info *sb = VFSTOEXT2(mp)->um_e2fs;
461 struct ext2_super_block * es;
462 unsigned long desc_count, bitmap_count, x;
464 struct ext2_group_desc * gdp;
467 lock_super (VFSTOEXT2(mp)->um_devvp);
472 for (i = 0; i < sb->s_groups_count; i++) {
473 gdp = get_group_desc (mp, i, NULL);
474 desc_count += gdp->bg_free_inodes_count;
475 bitmap_nr = load_inode_bitmap (mp, i);
476 x = ext2_count_free (sb->s_inode_bitmap[bitmap_nr],
477 EXT2_INODES_PER_GROUP(sb) / 8);
478 ext2_debug ("group %d: stored = %d, counted = %lu\n",
479 i, gdp->bg_free_inodes_count, x);
482 ext2_debug("stored = %lu, computed = %lu, %lu\n",
483 es->s_free_inodes_count, desc_count, bitmap_count);
484 unlock_super (VFSTOEXT2(mp)->um_devvp);
487 return VFSTOEXT2(mp)->um_e2fsb->s_free_inodes_count;
493 void ext2_check_inodes_bitmap (struct mount * mp)
495 struct ext2_super_block * es;
496 unsigned long desc_count, bitmap_count, x;
498 struct ext2_group_desc * gdp;
502 es = sb->u.ext2_sb.s_es;
506 for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
507 gdp = get_group_desc (sb, i, NULL);
508 desc_count += gdp->bg_free_inodes_count;
509 bitmap_nr = load_inode_bitmap (sb, i);
510 x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
511 EXT2_INODES_PER_GROUP(sb) / 8);
512 if (gdp->bg_free_inodes_count != x)
513 printf ( "ext2_check_inodes_bitmap:"
514 "Wrong free inodes count in group %d, "
515 "stored = %d, counted = %lu", i,
516 gdp->bg_free_inodes_count, x);
519 if (es->s_free_inodes_count != bitmap_count)
520 printf ( "ext2_check_inodes_bitmap:"
521 "Wrong free inodes count in super block, "
522 "stored = %lu, counted = %lu",
523 (unsigned long) es->s_free_inodes_count, bitmap_count);