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