2 * linux/fs/ext2/ialloc.c
4 * Copyright (C) 1992, 1993, 1994, 1995
5 * Remy Card (card@masi.ibp.fr)
6 * Laboratoire MASI - Institut Blaise Pascal
7 * Universite Pierre et Marie Curie (Paris VI)
9 * BSD ufs-inspired inode and directory allocation by
10 * Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
11 * Big-endian to little-endian byte-swapping/bitmaps by
12 * David S. Miller (davem@caip.rutgers.edu), 1995
15 #include <linux/config.h>
17 #include <linux/ext2_fs.h>
18 #include <linux/locks.h>
19 #include <linux/quotaops.h>
23 * ialloc.c contains the inodes allocation and deallocation routines
27 * The free inodes are managed by bitmaps. A file system contains several
28 * blocks groups. Each group contains 1 bitmap block for blocks, 1 bitmap
29 * block for inodes, N blocks for the inode table and data blocks.
31 * The file system contains group descriptors which are located after the
32 * super block. Each descriptor contains the number of the bitmap block and
33 * the free blocks count in the block. The descriptors are loaded in memory
34 * when a file system is mounted (see ext2_read_super).
39 * Read the inode allocation bitmap for a given block_group, reading
40 * into the specified slot in the superblock's bitmap cache.
42 * Return buffer_head of bitmap on success or NULL.
44 static struct buffer_head *read_inode_bitmap (struct super_block * sb,
45 unsigned long block_group)
47 struct ext2_group_desc *desc;
48 struct buffer_head *bh = NULL;
50 desc = ext2_get_group_desc(sb, block_group, NULL);
54 bh = sb_bread(sb, le32_to_cpu(desc->bg_inode_bitmap));
56 ext2_error (sb, "read_inode_bitmap",
57 "Cannot read inode bitmap - "
58 "block_group = %lu, inode_bitmap = %lu",
59 block_group, (unsigned long) desc->bg_inode_bitmap);
65 * load_inode_bitmap loads the inode bitmap for a blocks group
67 * It maintains a cache for the last bitmaps loaded. This cache is managed
68 * with a LRU algorithm.
71 * 1/ There is one cache per mounted file system.
72 * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
73 * this function reads the bitmap without maintaining a LRU cache.
75 * Return the buffer_head of the bitmap or the ERR_PTR(error)
77 static struct buffer_head *load_inode_bitmap (struct super_block * sb,
78 unsigned int block_group)
81 struct ext2_sb_info *sbi = &sb->u.ext2_sb;
82 struct buffer_head *bh = sbi->s_inode_bitmap[0];
84 if (block_group >= sbi->s_groups_count)
85 ext2_panic (sb, "load_inode_bitmap",
86 "block_group >= groups_count - "
87 "block_group = %d, groups_count = %lu",
88 block_group, sbi->s_groups_count);
90 if (sbi->s_loaded_inode_bitmaps > 0 &&
91 sbi->s_inode_bitmap_number[0] == block_group && bh)
94 if (sbi->s_groups_count <= EXT2_MAX_GROUP_LOADED) {
96 bh = sbi->s_inode_bitmap[slot];
99 if (sbi->s_inode_bitmap_number[slot] == slot)
101 ext2_panic (sb, "load_inode_bitmap",
102 "block_group != inode_bitmap_number");
106 for (i = 0; i < sbi->s_loaded_inode_bitmaps &&
107 sbi->s_inode_bitmap_number[i] != block_group;
110 if (i < sbi->s_loaded_inode_bitmaps)
111 bh = sbi->s_inode_bitmap[i];
112 else if (sbi->s_loaded_inode_bitmaps < EXT2_MAX_GROUP_LOADED)
113 sbi->s_loaded_inode_bitmaps++;
115 brelse (sbi->s_inode_bitmap[--i]);
118 sbi->s_inode_bitmap_number[i+1] = sbi->s_inode_bitmap_number[i];
119 sbi->s_inode_bitmap[i+1] = sbi->s_inode_bitmap[i];
124 bh = read_inode_bitmap (sb, block_group);
125 sbi->s_inode_bitmap_number[slot] = block_group;
126 sbi->s_inode_bitmap[slot] = bh;
128 return ERR_PTR(-EIO);
134 * NOTE! When we get the inode, we're the only people
135 * that have access to it, and as such there are no
136 * race conditions we have to worry about. The inode
137 * is not on the hash-lists, and it cannot be reached
138 * through the filesystem because the directory entry
139 * has been deleted earlier.
141 * HOWEVER: we must make sure that we get no aliases,
142 * which means that we have to call "clear_inode()"
143 * _before_ we mark the inode not in use in the inode
144 * bitmaps. Otherwise a newly created file might use
145 * the same inode number (not actually the same pointer
146 * though), and then we'd have two inodes sharing the
147 * same inode number and space on the harddisk.
149 void ext2_free_inode (struct inode * inode)
151 struct super_block * sb = inode->i_sb;
154 struct buffer_head * bh;
155 struct buffer_head * bh2;
156 unsigned long block_group;
158 struct ext2_group_desc * desc;
159 struct ext2_super_block * es;
162 ext2_debug ("freeing inode %lu\n", ino);
165 * Note: we must free any quota before locking the superblock,
166 * as writing the quota to disk may need the lock as well.
168 if (!is_bad_inode(inode)) {
169 /* Quota is already initialized in iput() */
170 DQUOT_FREE_INODE(inode);
175 es = sb->u.ext2_sb.s_es;
176 is_directory = S_ISDIR(inode->i_mode);
178 /* Do this BEFORE marking the inode not in use or returning an error */
181 if (ino < EXT2_FIRST_INO(sb) ||
182 ino > le32_to_cpu(es->s_inodes_count)) {
183 ext2_error (sb, "ext2_free_inode",
184 "reserved or nonexistent inode %lu", ino);
187 block_group = (ino - 1) / EXT2_INODES_PER_GROUP(sb);
188 bit = (ino - 1) % EXT2_INODES_PER_GROUP(sb);
189 bh = load_inode_bitmap (sb, block_group);
193 /* Ok, now we can actually update the inode bitmaps.. */
194 if (!ext2_clear_bit (bit, bh->b_data))
195 ext2_error (sb, "ext2_free_inode",
196 "bit already cleared for inode %lu", ino);
198 desc = ext2_get_group_desc (sb, block_group, &bh2);
200 desc->bg_free_inodes_count =
201 cpu_to_le16(le16_to_cpu(desc->bg_free_inodes_count) + 1);
203 desc->bg_used_dirs_count =
204 cpu_to_le16(le16_to_cpu(desc->bg_used_dirs_count) - 1);
206 mark_buffer_dirty(bh2);
207 es->s_free_inodes_count =
208 cpu_to_le32(le32_to_cpu(es->s_free_inodes_count) + 1);
209 mark_buffer_dirty(sb->u.ext2_sb.s_sbh);
211 mark_buffer_dirty(bh);
212 if (sb->s_flags & MS_SYNCHRONOUS) {
213 ll_rw_block (WRITE, 1, &bh);
222 * There are two policies for allocating an inode. If the new inode is
223 * a directory, then a forward search is made for a block group with both
224 * free space and a low directory-to-inode ratio; if that fails, then of
225 * the groups with above-average free space, that group with the fewest
226 * directories already is chosen.
228 * For other inodes, search forward from the parent directory\'s block
229 * group to find a free inode.
232 static int find_group_dir(struct super_block *sb, int parent_group)
234 struct ext2_super_block * es = sb->u.ext2_sb.s_es;
235 int ngroups = sb->u.ext2_sb.s_groups_count;
236 int avefreei = le32_to_cpu(es->s_free_inodes_count) / ngroups;
237 struct ext2_group_desc *desc, *best_desc = NULL;
238 struct buffer_head *bh, *best_bh = NULL;
239 int group, best_group = -1;
241 for (group = 0; group < ngroups; group++) {
242 desc = ext2_get_group_desc (sb, group, &bh);
243 if (!desc || !desc->bg_free_inodes_count)
245 if (le16_to_cpu(desc->bg_free_inodes_count) < avefreei)
248 (le16_to_cpu(desc->bg_free_blocks_count) >
249 le16_to_cpu(best_desc->bg_free_blocks_count))) {
257 best_desc->bg_free_inodes_count =
258 cpu_to_le16(le16_to_cpu(best_desc->bg_free_inodes_count) - 1);
259 best_desc->bg_used_dirs_count =
260 cpu_to_le16(le16_to_cpu(best_desc->bg_used_dirs_count) + 1);
261 mark_buffer_dirty(best_bh);
265 static int find_group_other(struct super_block *sb, int parent_group)
267 int ngroups = sb->u.ext2_sb.s_groups_count;
268 struct ext2_group_desc *desc;
269 struct buffer_head *bh;
273 * Try to place the inode in its parent directory
275 group = parent_group;
276 desc = ext2_get_group_desc (sb, group, &bh);
277 if (desc && le16_to_cpu(desc->bg_free_inodes_count))
281 * Use a quadratic hash to find a group with a
284 for (i = 1; i < ngroups; i <<= 1) {
286 if (group >= ngroups)
288 desc = ext2_get_group_desc (sb, group, &bh);
289 if (desc && le16_to_cpu(desc->bg_free_inodes_count))
294 * That failed: try linear search for a free inode
296 group = parent_group + 1;
297 for (i = 2; i < ngroups; i++) {
298 if (++group >= ngroups)
300 desc = ext2_get_group_desc (sb, group, &bh);
301 if (desc && le16_to_cpu(desc->bg_free_inodes_count))
308 desc->bg_free_inodes_count =
309 cpu_to_le16(le16_to_cpu(desc->bg_free_inodes_count) - 1);
310 mark_buffer_dirty(bh);
314 struct inode * ext2_new_inode (const struct inode * dir, int mode)
316 struct super_block * sb;
317 struct buffer_head * bh;
318 struct buffer_head * bh2;
321 struct inode * inode;
322 struct ext2_group_desc * desc;
323 struct ext2_super_block * es;
327 inode = new_inode(sb);
329 return ERR_PTR(-ENOMEM);
332 es = sb->u.ext2_sb.s_es;
335 group = find_group_dir(sb, dir->u.ext2_i.i_block_group);
337 group = find_group_other(sb, dir->u.ext2_i.i_block_group);
344 bh = load_inode_bitmap (sb, group);
348 i = ext2_find_first_zero_bit ((unsigned long *) bh->b_data,
349 EXT2_INODES_PER_GROUP(sb));
350 if (i >= EXT2_INODES_PER_GROUP(sb))
352 ext2_set_bit (i, bh->b_data);
354 mark_buffer_dirty(bh);
355 if (sb->s_flags & MS_SYNCHRONOUS) {
356 ll_rw_block (WRITE, 1, &bh);
360 ino = group * EXT2_INODES_PER_GROUP(sb) + i + 1;
361 if (ino < EXT2_FIRST_INO(sb) || ino > le32_to_cpu(es->s_inodes_count)) {
362 ext2_error (sb, "ext2_new_inode",
363 "reserved inode or inode > inodes count - "
364 "block_group = %d,inode=%ld", group, ino);
369 es->s_free_inodes_count =
370 cpu_to_le32(le32_to_cpu(es->s_free_inodes_count) - 1);
371 mark_buffer_dirty(sb->u.ext2_sb.s_sbh);
373 inode->i_uid = current->fsuid;
374 if (test_opt (sb, GRPID))
375 inode->i_gid = dir->i_gid;
376 else if (dir->i_mode & S_ISGID) {
377 inode->i_gid = dir->i_gid;
381 inode->i_gid = current->fsgid;
382 inode->i_mode = mode;
385 inode->i_blksize = PAGE_SIZE; /* This is the optimal IO size (for stat), not the fs block size */
387 inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
388 inode->u.ext2_i.i_state = EXT2_STATE_NEW;
389 inode->u.ext2_i.i_flags = dir->u.ext2_i.i_flags & ~EXT2_BTREE_FL;
391 inode->u.ext2_i.i_flags &= ~(EXT2_IMMUTABLE_FL|EXT2_APPEND_FL);
392 inode->u.ext2_i.i_block_group = group;
393 ext2_set_inode_flags(inode);
394 insert_inode_hash(inode);
395 inode->i_generation = event++;
396 mark_inode_dirty(inode);
399 if(DQUOT_ALLOC_INODE(inode)) {
401 inode->i_flags |= S_NOQUOTA;
404 return ERR_PTR(-EDQUOT);
406 ext2_debug ("allocating inode %lu\n", inode->i_ino);
410 desc = ext2_get_group_desc (sb, group, &bh2);
411 desc->bg_free_inodes_count =
412 cpu_to_le16(le16_to_cpu(desc->bg_free_inodes_count) + 1);
414 desc->bg_used_dirs_count =
415 cpu_to_le16(le16_to_cpu(desc->bg_used_dirs_count) - 1);
416 mark_buffer_dirty(bh2);
419 make_bad_inode(inode);
424 ext2_error (sb, "ext2_new_inode",
425 "Free inodes count corrupted in group %d",
427 /* Is it really ENOSPC? */
429 if (sb->s_flags & MS_RDONLY)
432 desc = ext2_get_group_desc (sb, group, &bh2);
433 desc->bg_free_inodes_count = 0;
434 mark_buffer_dirty(bh2);
438 unsigned long ext2_count_free_inodes (struct super_block * sb)
441 struct ext2_super_block * es;
442 unsigned long desc_count = 0, bitmap_count = 0;
446 es = sb->u.ext2_sb.s_es;
447 for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
448 struct ext2_group_desc *desc = ext2_get_group_desc (sb, i, NULL);
449 struct buffer_head *bh;
454 desc_count += le16_to_cpu(desc->bg_free_inodes_count);
455 bh = load_inode_bitmap (sb, i);
459 x = ext2_count_free (bh, EXT2_INODES_PER_GROUP(sb) / 8);
460 printk ("group %d: stored = %d, counted = %lu\n",
461 i, le16_to_cpu(desc->bg_free_inodes_count), x);
464 printk("ext2_count_free_inodes: stored = %lu, computed = %lu, %lu\n",
465 le32_to_cpu(es->s_free_inodes_count), desc_count, bitmap_count);
469 return le32_to_cpu(sb->u.ext2_sb.s_es->s_free_inodes_count);
473 #ifdef CONFIG_EXT2_CHECK
474 /* Called at mount-time, super-block is locked */
475 void ext2_check_inodes_bitmap (struct super_block * sb)
477 struct ext2_super_block * es = sb->u.ext2_sb.s_es;
478 unsigned long desc_count = 0, bitmap_count = 0;
481 for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
482 struct ext2_group_desc *desc = ext2_get_group_desc(sb, i, NULL);
483 struct buffer_head *bh;
488 desc_count += le16_to_cpu(desc->bg_free_inodes_count);
489 bh = load_inode_bitmap (sb, i);
493 x = ext2_count_free (bh, EXT2_INODES_PER_GROUP(sb) / 8);
494 if (le16_to_cpu(desc->bg_free_inodes_count) != x)
495 ext2_error (sb, "ext2_check_inodes_bitmap",
496 "Wrong free inodes count in group %d, "
497 "stored = %d, counted = %lu", i,
498 le16_to_cpu(desc->bg_free_inodes_count), x);
501 if (le32_to_cpu(es->s_free_inodes_count) != bitmap_count)
502 ext2_error (sb, "ext2_check_inodes_bitmap",
503 "Wrong free inodes count in super block, "
504 "stored = %lu, counted = %lu",
505 (unsigned long)le32_to_cpu(es->s_free_inodes_count),