2 * modified for Lites 1.1
4 * Aug 1995, Godmar Back (gback@cs.utah.edu)
5 * University of Utah, Department of Computer Science
7 * $FreeBSD: src/sys/gnu/ext2fs/ext2_linux_ialloc.c,v 1.13.2.2 2001/08/14 18:03:19 gallatin Exp $
8 * $DragonFly: src/sys/vfs/gnu/ext2fs/ext2_linux_ialloc.c,v 1.6 2005/06/06 15:35:06 dillon Exp $
11 * linux/fs/ext2/ialloc.c
13 * Copyright (C) 1992, 1993, 1994, 1995
14 * Remy Card (card@masi.ibp.fr)
15 * Laboratoire MASI - Institut Blaise Pascal
16 * Universite Pierre et Marie Curie (Paris VI)
18 * BSD ufs-inspired inode and directory allocation by
19 * Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
23 * The free inodes are managed by bitmaps. A file system contains several
24 * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
25 * block for inodes, N blocks for the inode table and data blocks.
27 * The file system contains group descriptors which are located after the
28 * super block. Each descriptor contains the number of the bitmap block and
29 * the free blocks count in the block. The descriptors are loaded in memory
30 * when a file system is mounted (see ext2_read_super).
33 #include <sys/param.h>
34 #include <sys/systm.h>
37 #include <sys/mount.h>
38 #include <sys/vnode.h>
40 #include <vfs/ufs/quota.h>
41 #include <vfs/ufs/inode.h>
42 #include <vfs/ufs/ufsmount.h>
43 #include "ext2_extern.h"
45 #include "ext2_fs_sb.h"
49 #include <sys/thread2.h>
52 #include "i386-bitops.h"
53 #elif defined(__alpha__)
54 #include "alpha-bitops.h"
56 #error please provide bit operation functions
59 /* this is supposed to mark a buffer dirty on ready for delayed writing
61 void mark_buffer_dirty(struct buf *bh)
64 bh->b_flags |= B_DIRTY;
68 struct ext2_group_desc * get_group_desc (struct mount * mp,
69 unsigned int block_group,
70 struct buffer_head ** bh)
72 struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
73 unsigned long group_desc;
75 struct ext2_group_desc * gdp;
77 if (block_group >= sb->s_groups_count)
78 panic ("get_group_desc: "
79 "block_group >= groups_count - "
80 "block_group = %d, groups_count = %lu",
81 block_group, sb->s_groups_count);
83 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
84 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
85 if (!sb->s_group_desc[group_desc])
86 panic ( "get_group_desc:"
87 "Group descriptor not loaded - "
88 "block_group = %d, group_desc = %lu, desc = %lu",
89 block_group, group_desc, desc);
90 gdp = (struct ext2_group_desc *)
91 sb->s_group_desc[group_desc]->b_data;
93 *bh = sb->s_group_desc[group_desc];
97 static void read_inode_bitmap (struct mount * mp,
98 unsigned long block_group,
99 unsigned int bitmap_nr)
101 struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
102 struct ext2_group_desc * gdp;
103 struct buffer_head * bh;
106 gdp = get_group_desc (mp, block_group, NULL);
107 if ((error = bread (VFSTOUFS(mp)->um_devvp,
108 fsbtodb(sb, gdp->bg_inode_bitmap),
109 sb->s_blocksize, &bh)) != 0)
110 panic ( "read_inode_bitmap:"
111 "Cannot read inode bitmap - "
112 "block_group = %lu, inode_bitmap = %lu",
113 block_group, (unsigned long) gdp->bg_inode_bitmap);
114 sb->s_inode_bitmap_number[bitmap_nr] = block_group;
115 sb->s_inode_bitmap[bitmap_nr] = bh;
120 * load_inode_bitmap loads the inode bitmap for a blocks group
122 * It maintains a cache for the last bitmaps loaded. This cache is managed
123 * with a LRU algorithm.
126 * 1/ There is one cache per mounted file system.
127 * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
128 * this function reads the bitmap without maintaining a LRU cache.
130 static int load_inode_bitmap (struct mount * mp,
131 unsigned int block_group)
133 struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
135 unsigned long inode_bitmap_number;
136 struct buffer_head * inode_bitmap;
138 if (block_group >= sb->s_groups_count)
139 panic ("load_inode_bitmap:"
140 "block_group >= groups_count - "
141 "block_group = %d, groups_count = %lu",
142 block_group, sb->s_groups_count);
143 if (sb->s_loaded_inode_bitmaps > 0 &&
144 sb->s_inode_bitmap_number[0] == block_group)
146 if (sb->s_groups_count <= EXT2_MAX_GROUP_LOADED) {
147 if (sb->s_inode_bitmap[block_group]) {
148 if (sb->s_inode_bitmap_number[block_group] !=
150 panic ( "load_inode_bitmap:"
151 "block_group != inode_bitmap_number");
155 read_inode_bitmap (mp, block_group, block_group);
160 for (i = 0; i < sb->s_loaded_inode_bitmaps &&
161 sb->s_inode_bitmap_number[i] != block_group;
164 if (i < sb->s_loaded_inode_bitmaps &&
165 sb->s_inode_bitmap_number[i] == block_group) {
166 inode_bitmap_number = sb->s_inode_bitmap_number[i];
167 inode_bitmap = sb->s_inode_bitmap[i];
168 for (j = i; j > 0; j--) {
169 sb->s_inode_bitmap_number[j] =
170 sb->s_inode_bitmap_number[j - 1];
171 sb->s_inode_bitmap[j] =
172 sb->s_inode_bitmap[j - 1];
174 sb->s_inode_bitmap_number[0] = inode_bitmap_number;
175 sb->s_inode_bitmap[0] = inode_bitmap;
177 if (sb->s_loaded_inode_bitmaps < EXT2_MAX_GROUP_LOADED)
178 sb->s_loaded_inode_bitmaps++;
180 ULCK_BUF(sb->s_inode_bitmap[EXT2_MAX_GROUP_LOADED - 1])
181 for (j = sb->s_loaded_inode_bitmaps - 1; j > 0; j--) {
182 sb->s_inode_bitmap_number[j] =
183 sb->s_inode_bitmap_number[j - 1];
184 sb->s_inode_bitmap[j] =
185 sb->s_inode_bitmap[j - 1];
187 read_inode_bitmap (mp, block_group, 0);
193 void ext2_free_inode (struct inode * inode)
195 struct ext2_sb_info * sb;
196 struct buffer_head * bh;
197 struct buffer_head * bh2;
198 unsigned long block_group;
201 struct ext2_group_desc * gdp;
202 struct ext2_super_block * es;
207 if (inode->i_nlink) {
208 printf ("ext2_free_inode: inode has nlink=%d\n",
213 ext2_debug ("freeing inode %lu\n", inode->i_number);
216 lock_super (DEVVP(inode));
217 if (inode->i_number < EXT2_FIRST_INO ||
218 inode->i_number > sb->s_es->s_inodes_count) {
219 printf ("free_inode reserved inode or nonexistent inode");
220 unlock_super (DEVVP(inode));
224 block_group = (inode->i_number - 1) / EXT2_INODES_PER_GROUP(sb);
225 bit = (inode->i_number - 1) % EXT2_INODES_PER_GROUP(sb);
226 bitmap_nr = load_inode_bitmap (ITOV(inode)->v_mount, block_group);
227 bh = sb->s_inode_bitmap[bitmap_nr];
228 if (!clear_bit (bit, bh->b_data))
229 printf ( "ext2_free_inode:"
230 "bit already cleared for inode %lu",
231 (unsigned long)inode->i_number);
233 gdp = get_group_desc (ITOV(inode)->v_mount, block_group, &bh2);
234 gdp->bg_free_inodes_count++;
235 if (S_ISDIR(inode->i_mode))
236 gdp->bg_used_dirs_count--;
237 mark_buffer_dirty(bh2);
238 es->s_free_inodes_count++;
240 mark_buffer_dirty(bh);
242 if (sb->s_flags & MS_SYNCHRONOUS) {
243 ll_rw_block (WRITE, 1, &bh);
248 unlock_super (DEVVP(inode));
253 * This function increments the inode version number
255 * This may be used one day by the NFS server
257 static void inc_inode_version (struct inode * inode,
258 struct ext2_group_desc *gdp,
261 unsigned long inode_block;
262 struct buffer_head * bh;
263 struct ext2_inode * raw_inode;
265 inode_block = gdp->bg_inode_table + (((inode->i_number - 1) %
266 EXT2_INODES_PER_GROUP(inode->i_sb)) /
267 EXT2_INODES_PER_BLOCK(inode->i_sb));
268 bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
270 printf ("inc_inode_version Cannot load inode table block - "
271 "inode=%lu, inode_block=%lu\n",
272 inode->i_number, inode_block);
273 inode->u.ext2_i.i_version = 1;
276 raw_inode = ((struct ext2_inode *) bh->b_data) +
277 (((inode->i_number - 1) %
278 EXT2_INODES_PER_GROUP(inode->i_sb)) %
279 EXT2_INODES_PER_BLOCK(inode->i_sb));
280 raw_inode->i_version++;
281 inode->u.ext2_i.i_version = raw_inode->i_version;
288 * There are two policies for allocating an inode. If the new inode is
289 * a directory, then a forward search is made for a block group with both
290 * free space and a low directory-to-inode ratio; if that fails, then of
291 * the groups with above-average free space, that group with the fewest
292 * directories already is chosen.
294 * For other inodes, search forward from the parent directory\'s block
295 * group to find a free inode.
298 * this functino has been reduced to the actual 'find the inode number' part
300 ino_t ext2_new_inode (const struct inode * dir, int mode)
302 struct ext2_sb_info * sb;
303 struct buffer_head * bh;
304 struct buffer_head * bh2;
307 struct ext2_group_desc * gdp;
308 struct ext2_group_desc * tmp;
309 struct ext2_super_block * es;
315 lock_super (DEVVP(dir));
321 avefreei = es->s_free_inodes_count /
323 /* I am not yet convinced that this next bit is necessary.
324 i = dir->u.ext2_i.i_block_group;
325 for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
326 tmp = get_group_desc (sb, i, &bh2);
327 if ((tmp->bg_used_dirs_count << 8) <
328 tmp->bg_free_inodes_count) {
333 i = ++i % sb->u.ext2_sb.s_groups_count;
337 for (j = 0; j < sb->s_groups_count; j++) {
338 tmp = get_group_desc(ITOV(dir)->v_mount,j,&bh2);
339 if (tmp->bg_free_inodes_count &&
340 tmp->bg_free_inodes_count >= avefreei) {
342 (tmp->bg_free_blocks_count >
343 gdp->bg_free_blocks_count)) {
354 * Try to place the inode in its parent directory
356 i = dir->i_block_group;
357 tmp = get_group_desc (ITOV(dir)->v_mount, i, &bh2);
358 if (tmp->bg_free_inodes_count)
363 * Use a quadratic hash to find a group with a
366 for (j = 1; j < sb->s_groups_count; j <<= 1) {
368 if (i >= sb->s_groups_count)
369 i -= sb->s_groups_count;
370 tmp = get_group_desc(ITOV(dir)->v_mount,i,&bh2);
371 if (tmp->bg_free_inodes_count) {
379 * That failed: try linear search for a free inode
381 i = dir->i_block_group + 1;
382 for (j = 2; j < sb->s_groups_count; j++) {
383 if (++i >= sb->s_groups_count)
385 tmp = get_group_desc(ITOV(dir)->v_mount,i,&bh2);
386 if (tmp->bg_free_inodes_count) {
395 unlock_super (DEVVP(dir));
398 bitmap_nr = load_inode_bitmap (ITOV(dir)->v_mount, i);
399 bh = sb->s_inode_bitmap[bitmap_nr];
400 if ((j = find_first_zero_bit ((unsigned long *) bh->b_data,
401 EXT2_INODES_PER_GROUP(sb))) <
402 EXT2_INODES_PER_GROUP(sb)) {
403 if (set_bit (j, bh->b_data)) {
404 printf ( "ext2_new_inode:"
405 "bit already set for inode %d", j);
408 /* Linux now does the following:
409 mark_buffer_dirty(bh);
410 if (sb->s_flags & MS_SYNCHRONOUS) {
411 ll_rw_block (WRITE, 1, &bh);
415 mark_buffer_dirty(bh);
417 if (gdp->bg_free_inodes_count != 0) {
418 printf ( "ext2_new_inode:"
419 "Free inodes count corrupted in group %d",
421 unlock_super (DEVVP(dir));
426 j += i * EXT2_INODES_PER_GROUP(sb) + 1;
427 if (j < EXT2_FIRST_INO || j > es->s_inodes_count) {
428 printf ( "ext2_new_inode:"
429 "reserved inode or inode > inodes count - "
430 "block_group = %d,inode=%d", i, j);
431 unlock_super (DEVVP(dir));
434 gdp->bg_free_inodes_count--;
436 gdp->bg_used_dirs_count++;
437 mark_buffer_dirty(bh2);
438 es->s_free_inodes_count--;
439 /* mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1); */
441 unlock_super (DEVVP(dir));
446 static unsigned long ext2_count_free_inodes (struct mount * mp)
449 struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
450 struct ext2_super_block * es;
451 unsigned long desc_count, bitmap_count, x;
453 struct ext2_group_desc * gdp;
456 lock_super (VFSTOUFS(mp)->um_devvp);
461 for (i = 0; i < sb->s_groups_count; i++) {
462 gdp = get_group_desc (mp, i, NULL);
463 desc_count += gdp->bg_free_inodes_count;
464 bitmap_nr = load_inode_bitmap (mp, i);
465 x = ext2_count_free (sb->s_inode_bitmap[bitmap_nr],
466 EXT2_INODES_PER_GROUP(sb) / 8);
467 ext2_debug ("group %d: stored = %d, counted = %lu\n",
468 i, gdp->bg_free_inodes_count, x);
471 ext2_debug("stored = %lu, computed = %lu, %lu\n",
472 es->s_free_inodes_count, desc_count, bitmap_count);
473 unlock_super (VFSTOUFS(mp)->um_devvp);
476 return VFSTOUFS(mp)->um_e2fsb->s_free_inodes_count;
482 void ext2_check_inodes_bitmap (struct mount * mp)
484 struct ext2_super_block * es;
485 unsigned long desc_count, bitmap_count, x;
487 struct ext2_group_desc * gdp;
491 es = sb->u.ext2_sb.s_es;
495 for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
496 gdp = get_group_desc (sb, i, NULL);
497 desc_count += gdp->bg_free_inodes_count;
498 bitmap_nr = load_inode_bitmap (sb, i);
499 x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
500 EXT2_INODES_PER_GROUP(sb) / 8);
501 if (gdp->bg_free_inodes_count != x)
502 printf ( "ext2_check_inodes_bitmap:"
503 "Wrong free inodes count in group %d, "
504 "stored = %d, counted = %lu", i,
505 gdp->bg_free_inodes_count, x);
508 if (es->s_free_inodes_count != bitmap_count)
509 printf ( "ext2_check_inodes_bitmap:"
510 "Wrong free inodes count in super block, "
511 "stored = %lu, counted = %lu",
512 (unsigned long) es->s_free_inodes_count, bitmap_count);