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.12 2007/09/23 04:09:55 yanyh 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>
42 #include "ext2mount.h"
43 #include "ext2_extern.h"
45 #include "ext2_fs_sb.h"
49 #include <sys/thread2.h>
52 #include "i386-bitops.h"
54 #include "ext2_bitops.h"
57 /* this is supposed to mark a buffer dirty on ready for delayed writing
60 mark_buffer_dirty(struct buf
*bh
)
63 bh
->b_flags
|= B_DIRTY
;
67 struct ext2_group_desc
*
68 get_group_desc(struct mount
* mp
, unsigned int block_group
,
69 struct buffer_head
**bh
)
71 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
72 unsigned long group_desc
;
74 struct ext2_group_desc
* gdp
;
76 if (block_group
>= sb
->s_groups_count
)
77 panic ("get_group_desc: "
78 "block_group >= groups_count - "
79 "block_group = %d, groups_count = %lu",
80 block_group
, sb
->s_groups_count
);
82 group_desc
= block_group
/ EXT2_DESC_PER_BLOCK(sb
);
83 desc
= block_group
% EXT2_DESC_PER_BLOCK(sb
);
84 if (!sb
->s_group_desc
[group_desc
])
85 panic ( "get_group_desc:"
86 "Group descriptor not loaded - "
87 "block_group = %d, group_desc = %lu, desc = %lu",
88 block_group
, group_desc
, desc
);
89 gdp
= (struct ext2_group_desc
*)
90 sb
->s_group_desc
[group_desc
]->b_data
;
92 *bh
= sb
->s_group_desc
[group_desc
];
97 read_inode_bitmap(struct mount
*mp
, unsigned long block_group
,
98 unsigned int bitmap_nr
)
100 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
101 struct ext2_group_desc
* gdp
;
102 struct buffer_head
* bh
;
105 gdp
= get_group_desc (mp
, block_group
, NULL
);
106 if ((error
= bread (VFSTOEXT2(mp
)->um_devvp
,
107 fsbtodoff(sb
, gdp
->bg_inode_bitmap
),
108 sb
->s_blocksize
, &bh
)) != 0)
109 panic ( "read_inode_bitmap:"
110 "Cannot read inode bitmap - "
111 "block_group = %lu, inode_bitmap = %lu",
112 block_group
, (unsigned long) gdp
->bg_inode_bitmap
);
113 sb
->s_inode_bitmap_number
[bitmap_nr
] = block_group
;
114 sb
->s_inode_bitmap
[bitmap_nr
] = bh
;
119 * load_inode_bitmap loads the inode bitmap for a blocks group
121 * It maintains a cache for the last bitmaps loaded. This cache is managed
122 * with a LRU algorithm.
125 * 1/ There is one cache per mounted file system.
126 * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
127 * this function reads the bitmap without maintaining a LRU cache.
130 load_inode_bitmap(struct mount
*mp
, unsigned int block_group
)
132 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
134 unsigned long inode_bitmap_number
;
135 struct buffer_head
* inode_bitmap
;
137 if (block_group
>= sb
->s_groups_count
)
138 panic ("load_inode_bitmap:"
139 "block_group >= groups_count - "
140 "block_group = %d, groups_count = %lu",
141 block_group
, sb
->s_groups_count
);
142 if (sb
->s_loaded_inode_bitmaps
> 0 &&
143 sb
->s_inode_bitmap_number
[0] == block_group
)
145 if (sb
->s_groups_count
<= EXT2_MAX_GROUP_LOADED
) {
146 if (sb
->s_inode_bitmap
[block_group
]) {
147 if (sb
->s_inode_bitmap_number
[block_group
] !=
149 panic ( "load_inode_bitmap:"
150 "block_group != inode_bitmap_number");
154 read_inode_bitmap (mp
, block_group
, block_group
);
159 for (i
= 0; i
< sb
->s_loaded_inode_bitmaps
&&
160 sb
->s_inode_bitmap_number
[i
] != block_group
;
163 if (i
< sb
->s_loaded_inode_bitmaps
&&
164 sb
->s_inode_bitmap_number
[i
] == block_group
) {
165 inode_bitmap_number
= sb
->s_inode_bitmap_number
[i
];
166 inode_bitmap
= sb
->s_inode_bitmap
[i
];
167 for (j
= i
; j
> 0; j
--) {
168 sb
->s_inode_bitmap_number
[j
] =
169 sb
->s_inode_bitmap_number
[j
- 1];
170 sb
->s_inode_bitmap
[j
] =
171 sb
->s_inode_bitmap
[j
- 1];
173 sb
->s_inode_bitmap_number
[0] = inode_bitmap_number
;
174 sb
->s_inode_bitmap
[0] = inode_bitmap
;
176 if (sb
->s_loaded_inode_bitmaps
< EXT2_MAX_GROUP_LOADED
)
177 sb
->s_loaded_inode_bitmaps
++;
179 ULCK_BUF(sb
->s_inode_bitmap
[EXT2_MAX_GROUP_LOADED
- 1])
180 for (j
= sb
->s_loaded_inode_bitmaps
- 1; j
> 0; j
--) {
181 sb
->s_inode_bitmap_number
[j
] =
182 sb
->s_inode_bitmap_number
[j
- 1];
183 sb
->s_inode_bitmap
[j
] =
184 sb
->s_inode_bitmap
[j
- 1];
186 read_inode_bitmap (mp
, block_group
, 0);
193 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 kprintf ("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(sb
) ||
218 inode
->i_number
> sb
->s_es
->s_inodes_count
) {
219 kprintf ("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 kprintf ( "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
258 inc_inode_version(struct inode
*inode
, struct ext2_group_desc
*gdp
, int mode
)
260 unsigned long inode_block
;
261 struct buffer_head
* bh
;
262 struct ext2_inode
* raw_inode
;
264 inode_block
= gdp
->bg_inode_table
+ (((inode
->i_number
- 1) %
265 EXT2_INODES_PER_GROUP(inode
->i_sb
)) /
266 EXT2_INODES_PER_BLOCK(inode
->i_sb
));
267 bh
= bread (inode
->i_sb
->s_dev
, dbtob(inode_block
), inode
->i_sb
->s_blocksize
);
269 kprintf ("inc_inode_version Cannot load inode table block - "
270 "inode=%lu, inode_block=%lu\n",
271 inode
->i_number
, inode_block
);
272 inode
->u
.ext2_i
.i_version
= 1;
275 raw_inode
= ((struct ext2_inode
*) bh
->b_data
) +
276 (((inode
->i_number
- 1) %
277 EXT2_INODES_PER_GROUP(inode
->i_sb
)) %
278 EXT2_INODES_PER_BLOCK(inode
->i_sb
));
279 raw_inode
->i_version
++;
280 inode
->u
.ext2_i
.i_version
= raw_inode
->i_version
;
287 * There are two policies for allocating an inode. If the new inode is
288 * a directory, then a forward search is made for a block group with both
289 * free space and a low directory-to-inode ratio; if that fails, then of
290 * the groups with above-average free space, that group with the fewest
291 * directories already is chosen.
293 * For other inodes, search forward from the parent directory\'s block
294 * group to find a free inode.
297 * this functino has been reduced to the actual 'find the inode number' part
300 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 kprintf ( "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 kprintf ( "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(sb
) || j
> es
->s_inodes_count
) {
428 kprintf ( "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
));
447 ext2_count_free_inodes(struct mount
*mp
)
450 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
451 struct ext2_super_block
* es
;
452 unsigned long desc_count
, bitmap_count
, x
;
454 struct ext2_group_desc
* gdp
;
457 lock_super (VFSTOEXT2(mp
)->um_devvp
);
462 for (i
= 0; i
< sb
->s_groups_count
; i
++) {
463 gdp
= get_group_desc (mp
, i
, NULL
);
464 desc_count
+= gdp
->bg_free_inodes_count
;
465 bitmap_nr
= load_inode_bitmap (mp
, i
);
466 x
= ext2_count_free (sb
->s_inode_bitmap
[bitmap_nr
],
467 EXT2_INODES_PER_GROUP(sb
) / 8);
468 ext2_debug ("group %d: stored = %d, counted = %lu\n",
469 i
, gdp
->bg_free_inodes_count
, x
);
472 ext2_debug("stored = %lu, computed = %lu, %lu\n",
473 es
->s_free_inodes_count
, desc_count
, bitmap_count
);
474 unlock_super (VFSTOEXT2(mp
)->um_devvp
);
477 return VFSTOEXT2(mp
)->um_e2fsb
->s_free_inodes_count
;
484 ext2_check_inodes_bitmap(struct mount
*mp
)
486 struct ext2_super_block
* es
;
487 unsigned long desc_count
, bitmap_count
, x
;
489 struct ext2_group_desc
* gdp
;
493 es
= sb
->u
.ext2_sb
.s_es
;
497 for (i
= 0; i
< sb
->u
.ext2_sb
.s_groups_count
; i
++) {
498 gdp
= get_group_desc (sb
, i
, NULL
);
499 desc_count
+= gdp
->bg_free_inodes_count
;
500 bitmap_nr
= load_inode_bitmap (sb
, i
);
501 x
= ext2_count_free (sb
->u
.ext2_sb
.s_inode_bitmap
[bitmap_nr
],
502 EXT2_INODES_PER_GROUP(sb
) / 8);
503 if (gdp
->bg_free_inodes_count
!= x
)
504 kprintf ( "ext2_check_inodes_bitmap:"
505 "Wrong free inodes count in group %d, "
506 "stored = %d, counted = %lu", i
,
507 gdp
->bg_free_inodes_count
, x
);
510 if (es
->s_free_inodes_count
!= bitmap_count
)
511 kprintf ( "ext2_check_inodes_bitmap:"
512 "Wrong free inodes count in super block, "
513 "stored = %lu, counted = %lu",
514 (unsigned long) es
->s_free_inodes_count
, bitmap_count
);