LINT build test. Aggregated source code adjustments to bring most of the
[dragonfly.git] / sys / vfs / gnu / ext2fs / ext2_linux_ialloc.c
CommitLineData
984263bc
MD
1/*
2 * modified for Lites 1.1
3 *
4 * Aug 1995, Godmar Back (gback@cs.utah.edu)
5 * University of Utah, Department of Computer Science
6 *
7 * $FreeBSD: src/sys/gnu/ext2fs/ext2_linux_ialloc.c,v 1.13.2.2 2001/08/14 18:03:19 gallatin Exp $
7b95be2a 8 * $DragonFly: src/sys/vfs/gnu/ext2fs/ext2_linux_ialloc.c,v 1.3 2003/07/21 07:57:43 dillon Exp $
984263bc
MD
9 */
10/*
11 * linux/fs/ext2/ialloc.c
12 *
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)
17 *
18 * BSD ufs-inspired inode and directory allocation by
19 * Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
20 */
21
22/*
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.
26 *
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).
31 */
32
33#include <sys/param.h>
34#include <sys/systm.h>
35#include <sys/buf.h>
36#include <sys/proc.h>
37#include <sys/mount.h>
38#include <sys/vnode.h>
39
40#include <ufs/ufs/quota.h>
41#include <ufs/ufs/inode.h>
42#include <ufs/ufs/ufsmount.h>
43#include <gnu/ext2fs/ext2_extern.h>
44#include <gnu/ext2fs/ext2_fs.h>
45#include <gnu/ext2fs/ext2_fs_sb.h>
46#include <gnu/ext2fs/fs.h>
47#include <sys/stat.h>
7b95be2a 48#include <sys/buf2.h>
984263bc
MD
49
50#ifdef __i386__
51#include <gnu/ext2fs/i386-bitops.h>
52#elif defined(__alpha__)
53#include <gnu/ext2fs/alpha-bitops.h>
54#else
55#error please provide bit operation functions
56#endif
57
58/* this is supposed to mark a buffer dirty on ready for delayed writing
59 */
60void mark_buffer_dirty(struct buf *bh)
61{
62 int s;
63
64 s = splbio();
65 bh->b_flags |= B_DIRTY;
66 splx(s);
67}
68
69struct ext2_group_desc * get_group_desc (struct mount * mp,
70 unsigned int block_group,
71 struct buffer_head ** bh)
72{
73 struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
74 unsigned long group_desc;
75 unsigned long desc;
76 struct ext2_group_desc * gdp;
77
78 if (block_group >= sb->s_groups_count)
79 panic ("get_group_desc: "
80 "block_group >= groups_count - "
81 "block_group = %d, groups_count = %lu",
82 block_group, sb->s_groups_count);
83
84 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
85 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
86 if (!sb->s_group_desc[group_desc])
87 panic ( "get_group_desc:"
88 "Group descriptor not loaded - "
89 "block_group = %d, group_desc = %lu, desc = %lu",
90 block_group, group_desc, desc);
91 gdp = (struct ext2_group_desc *)
92 sb->s_group_desc[group_desc]->b_data;
93 if (bh)
94 *bh = sb->s_group_desc[group_desc];
95 return gdp + desc;
96}
97
98static void read_inode_bitmap (struct mount * mp,
99 unsigned long block_group,
100 unsigned int bitmap_nr)
101{
102 struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
103 struct ext2_group_desc * gdp;
104 struct buffer_head * bh;
105 int error;
106
107 gdp = get_group_desc (mp, block_group, NULL);
108 if ((error = bread (VFSTOUFS(mp)->um_devvp,
109 fsbtodb(sb, gdp->bg_inode_bitmap),
7b95be2a 110 sb->s_blocksize, &bh)) != 0)
984263bc
MD
111 panic ( "read_inode_bitmap:"
112 "Cannot read inode bitmap - "
113 "block_group = %lu, inode_bitmap = %lu",
114 block_group, (unsigned long) gdp->bg_inode_bitmap);
115 sb->s_inode_bitmap_number[bitmap_nr] = block_group;
116 sb->s_inode_bitmap[bitmap_nr] = bh;
117 LCK_BUF(bh)
118}
119
120/*
121 * load_inode_bitmap loads the inode bitmap for a blocks group
122 *
123 * It maintains a cache for the last bitmaps loaded. This cache is managed
124 * with a LRU algorithm.
125 *
126 * Notes:
127 * 1/ There is one cache per mounted file system.
128 * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
129 * this function reads the bitmap without maintaining a LRU cache.
130 */
131static int load_inode_bitmap (struct mount * mp,
132 unsigned int block_group)
133{
134 struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
135 int i, j;
136 unsigned long inode_bitmap_number;
137 struct buffer_head * inode_bitmap;
138
139 if (block_group >= sb->s_groups_count)
140 panic ("load_inode_bitmap:"
141 "block_group >= groups_count - "
142 "block_group = %d, groups_count = %lu",
143 block_group, sb->s_groups_count);
144 if (sb->s_loaded_inode_bitmaps > 0 &&
145 sb->s_inode_bitmap_number[0] == block_group)
146 return 0;
147 if (sb->s_groups_count <= EXT2_MAX_GROUP_LOADED) {
148 if (sb->s_inode_bitmap[block_group]) {
149 if (sb->s_inode_bitmap_number[block_group] !=
150 block_group)
151 panic ( "load_inode_bitmap:"
152 "block_group != inode_bitmap_number");
153 else
154 return block_group;
155 } else {
156 read_inode_bitmap (mp, block_group, block_group);
157 return block_group;
158 }
159 }
160
161 for (i = 0; i < sb->s_loaded_inode_bitmaps &&
162 sb->s_inode_bitmap_number[i] != block_group;
163 i++)
164 ;
165 if (i < sb->s_loaded_inode_bitmaps &&
166 sb->s_inode_bitmap_number[i] == block_group) {
167 inode_bitmap_number = sb->s_inode_bitmap_number[i];
168 inode_bitmap = sb->s_inode_bitmap[i];
169 for (j = i; j > 0; j--) {
170 sb->s_inode_bitmap_number[j] =
171 sb->s_inode_bitmap_number[j - 1];
172 sb->s_inode_bitmap[j] =
173 sb->s_inode_bitmap[j - 1];
174 }
175 sb->s_inode_bitmap_number[0] = inode_bitmap_number;
176 sb->s_inode_bitmap[0] = inode_bitmap;
177 } else {
178 if (sb->s_loaded_inode_bitmaps < EXT2_MAX_GROUP_LOADED)
179 sb->s_loaded_inode_bitmaps++;
180 else
181 ULCK_BUF(sb->s_inode_bitmap[EXT2_MAX_GROUP_LOADED - 1])
182 for (j = sb->s_loaded_inode_bitmaps - 1; j > 0; j--) {
183 sb->s_inode_bitmap_number[j] =
184 sb->s_inode_bitmap_number[j - 1];
185 sb->s_inode_bitmap[j] =
186 sb->s_inode_bitmap[j - 1];
187 }
188 read_inode_bitmap (mp, block_group, 0);
189 }
190 return 0;
191}
192
193
194void ext2_free_inode (struct inode * inode)
195{
196 struct ext2_sb_info * sb;
197 struct buffer_head * bh;
198 struct buffer_head * bh2;
199 unsigned long block_group;
200 unsigned long bit;
201 int bitmap_nr;
202 struct ext2_group_desc * gdp;
203 struct ext2_super_block * es;
204
205 if (!inode)
206 return;
207
208 if (inode->i_nlink) {
209 printf ("ext2_free_inode: inode has nlink=%d\n",
210 inode->i_nlink);
211 return;
212 }
213
214 ext2_debug ("freeing inode %lu\n", inode->i_number);
215
216 sb = inode->i_e2fs;
217 lock_super (DEVVP(inode));
218 if (inode->i_number < EXT2_FIRST_INO ||
219 inode->i_number > sb->s_es->s_inodes_count) {
220 printf ("free_inode reserved inode or nonexistent inode");
221 unlock_super (DEVVP(inode));
222 return;
223 }
224 es = sb->s_es;
225 block_group = (inode->i_number - 1) / EXT2_INODES_PER_GROUP(sb);
226 bit = (inode->i_number - 1) % EXT2_INODES_PER_GROUP(sb);
227 bitmap_nr = load_inode_bitmap (ITOV(inode)->v_mount, block_group);
228 bh = sb->s_inode_bitmap[bitmap_nr];
229 if (!clear_bit (bit, bh->b_data))
230 printf ( "ext2_free_inode:"
231 "bit already cleared for inode %lu",
232 (unsigned long)inode->i_number);
233 else {
234 gdp = get_group_desc (ITOV(inode)->v_mount, block_group, &bh2);
235 gdp->bg_free_inodes_count++;
236 if (S_ISDIR(inode->i_mode))
237 gdp->bg_used_dirs_count--;
238 mark_buffer_dirty(bh2);
239 es->s_free_inodes_count++;
240 }
241 mark_buffer_dirty(bh);
242/*** XXX
243 if (sb->s_flags & MS_SYNCHRONOUS) {
244 ll_rw_block (WRITE, 1, &bh);
245 wait_on_buffer (bh);
246 }
247***/
248 sb->s_dirt = 1;
249 unlock_super (DEVVP(inode));
250}
251
252#if linux
253/*
254 * This function increments the inode version number
255 *
256 * This may be used one day by the NFS server
257 */
258static void inc_inode_version (struct inode * inode,
259 struct ext2_group_desc *gdp,
260 int mode)
261{
262 unsigned long inode_block;
263 struct buffer_head * bh;
264 struct ext2_inode * raw_inode;
265
266 inode_block = gdp->bg_inode_table + (((inode->i_number - 1) %
267 EXT2_INODES_PER_GROUP(inode->i_sb)) /
268 EXT2_INODES_PER_BLOCK(inode->i_sb));
269 bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
270 if (!bh) {
271 printf ("inc_inode_version Cannot load inode table block - "
272 "inode=%lu, inode_block=%lu\n",
273 inode->i_number, inode_block);
274 inode->u.ext2_i.i_version = 1;
275 return;
276 }
277 raw_inode = ((struct ext2_inode *) bh->b_data) +
278 (((inode->i_number - 1) %
279 EXT2_INODES_PER_GROUP(inode->i_sb)) %
280 EXT2_INODES_PER_BLOCK(inode->i_sb));
281 raw_inode->i_version++;
282 inode->u.ext2_i.i_version = raw_inode->i_version;
283 bdwrite (bh);
284}
285
286#endif /* linux */
287
288/*
289 * There are two policies for allocating an inode. If the new inode is
290 * a directory, then a forward search is made for a block group with both
291 * free space and a low directory-to-inode ratio; if that fails, then of
292 * the groups with above-average free space, that group with the fewest
293 * directories already is chosen.
294 *
295 * For other inodes, search forward from the parent directory\'s block
296 * group to find a free inode.
297 */
298/*
299 * this functino has been reduced to the actual 'find the inode number' part
300 */
301ino_t ext2_new_inode (const struct inode * dir, int mode)
302{
303 struct ext2_sb_info * sb;
304 struct buffer_head * bh;
305 struct buffer_head * bh2;
306 int i, j, avefreei;
307 int bitmap_nr;
308 struct ext2_group_desc * gdp;
309 struct ext2_group_desc * tmp;
310 struct ext2_super_block * es;
311
312 if (!dir)
313 return 0;
314 sb = dir->i_e2fs;
315
316 lock_super (DEVVP(dir));
317 es = sb->s_es;
318repeat:
319 gdp = NULL; i=0;
320
321 if (S_ISDIR(mode)) {
322 avefreei = es->s_free_inodes_count /
323 sb->s_groups_count;
324/* I am not yet convinced that this next bit is necessary.
325 i = dir->u.ext2_i.i_block_group;
326 for (j = 0; j < sb->u.ext2_sb.s_groups_count; j++) {
327 tmp = get_group_desc (sb, i, &bh2);
328 if ((tmp->bg_used_dirs_count << 8) <
329 tmp->bg_free_inodes_count) {
330 gdp = tmp;
331 break;
332 }
333 else
334 i = ++i % sb->u.ext2_sb.s_groups_count;
335 }
336*/
337 if (!gdp) {
338 for (j = 0; j < sb->s_groups_count; j++) {
339 tmp = get_group_desc(ITOV(dir)->v_mount,j,&bh2);
340 if (tmp->bg_free_inodes_count &&
341 tmp->bg_free_inodes_count >= avefreei) {
342 if (!gdp ||
343 (tmp->bg_free_blocks_count >
344 gdp->bg_free_blocks_count)) {
345 i = j;
346 gdp = tmp;
347 }
348 }
349 }
350 }
351 }
352 else
353 {
354 /*
355 * Try to place the inode in its parent directory
356 */
357 i = dir->i_block_group;
358 tmp = get_group_desc (ITOV(dir)->v_mount, i, &bh2);
359 if (tmp->bg_free_inodes_count)
360 gdp = tmp;
361 else
362 {
363 /*
364 * Use a quadratic hash to find a group with a
365 * free inode
366 */
367 for (j = 1; j < sb->s_groups_count; j <<= 1) {
368 i += j;
369 if (i >= sb->s_groups_count)
370 i -= sb->s_groups_count;
371 tmp = get_group_desc(ITOV(dir)->v_mount,i,&bh2);
372 if (tmp->bg_free_inodes_count) {
373 gdp = tmp;
374 break;
375 }
376 }
377 }
378 if (!gdp) {
379 /*
380 * That failed: try linear search for a free inode
381 */
382 i = dir->i_block_group + 1;
383 for (j = 2; j < sb->s_groups_count; j++) {
384 if (++i >= sb->s_groups_count)
385 i = 0;
386 tmp = get_group_desc(ITOV(dir)->v_mount,i,&bh2);
387 if (tmp->bg_free_inodes_count) {
388 gdp = tmp;
389 break;
390 }
391 }
392 }
393 }
394
395 if (!gdp) {
396 unlock_super (DEVVP(dir));
397 return 0;
398 }
399 bitmap_nr = load_inode_bitmap (ITOV(dir)->v_mount, i);
400 bh = sb->s_inode_bitmap[bitmap_nr];
401 if ((j = find_first_zero_bit ((unsigned long *) bh->b_data,
402 EXT2_INODES_PER_GROUP(sb))) <
403 EXT2_INODES_PER_GROUP(sb)) {
404 if (set_bit (j, bh->b_data)) {
405 printf ( "ext2_new_inode:"
406 "bit already set for inode %d", j);
407 goto repeat;
408 }
409/* Linux now does the following:
410 mark_buffer_dirty(bh);
411 if (sb->s_flags & MS_SYNCHRONOUS) {
412 ll_rw_block (WRITE, 1, &bh);
413 wait_on_buffer (bh);
414 }
415*/
416 mark_buffer_dirty(bh);
417 } else {
418 if (gdp->bg_free_inodes_count != 0) {
419 printf ( "ext2_new_inode:"
420 "Free inodes count corrupted in group %d",
421 i);
422 unlock_super (DEVVP(dir));
423 return 0;
424 }
425 goto repeat;
426 }
427 j += i * EXT2_INODES_PER_GROUP(sb) + 1;
428 if (j < EXT2_FIRST_INO || j > es->s_inodes_count) {
429 printf ( "ext2_new_inode:"
430 "reserved inode or inode > inodes count - "
431 "block_group = %d,inode=%d", i, j);
432 unlock_super (DEVVP(dir));
433 return 0;
434 }
435 gdp->bg_free_inodes_count--;
436 if (S_ISDIR(mode))
437 gdp->bg_used_dirs_count++;
438 mark_buffer_dirty(bh2);
439 es->s_free_inodes_count--;
440 /* mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1); */
441 sb->s_dirt = 1;
442 unlock_super (DEVVP(dir));
443 return j;
444}
445
446#ifdef unused
447static unsigned long ext2_count_free_inodes (struct mount * mp)
448{
449#ifdef EXT2FS_DEBUG
450 struct ext2_sb_info *sb = VFSTOUFS(mp)->um_e2fs;
451 struct ext2_super_block * es;
452 unsigned long desc_count, bitmap_count, x;
453 int bitmap_nr;
454 struct ext2_group_desc * gdp;
455 int i;
456
457 lock_super (VFSTOUFS(mp)->um_devvp);
458 es = sb->s_es;
459 desc_count = 0;
460 bitmap_count = 0;
461 gdp = NULL;
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);
470 bitmap_count += x;
471 }
472 ext2_debug("stored = %lu, computed = %lu, %lu\n",
473 es->s_free_inodes_count, desc_count, bitmap_count);
474 unlock_super (VFSTOUFS(mp)->um_devvp);
475 return desc_count;
476#else
477 return VFSTOUFS(mp)->um_e2fsb->s_free_inodes_count;
478#endif
479}
480#endif /* unused */
481
482#ifdef LATER
483void ext2_check_inodes_bitmap (struct mount * mp)
484{
485 struct ext2_super_block * es;
486 unsigned long desc_count, bitmap_count, x;
487 int bitmap_nr;
488 struct ext2_group_desc * gdp;
489 int i;
490
491 lock_super (sb);
492 es = sb->u.ext2_sb.s_es;
493 desc_count = 0;
494 bitmap_count = 0;
495 gdp = NULL;
496 for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
497 gdp = get_group_desc (sb, i, NULL);
498 desc_count += gdp->bg_free_inodes_count;
499 bitmap_nr = load_inode_bitmap (sb, i);
500 x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
501 EXT2_INODES_PER_GROUP(sb) / 8);
502 if (gdp->bg_free_inodes_count != x)
503 printf ( "ext2_check_inodes_bitmap:"
504 "Wrong free inodes count in group %d, "
505 "stored = %d, counted = %lu", i,
506 gdp->bg_free_inodes_count, x);
507 bitmap_count += x;
508 }
509 if (es->s_free_inodes_count != bitmap_count)
510 printf ( "ext2_check_inodes_bitmap:"
511 "Wrong free inodes count in super block, "
512 "stored = %lu, counted = %lu",
513 (unsigned long) es->s_free_inodes_count, bitmap_count);
514 unlock_super (sb);
515}
516#endif