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_balloc.c,v 1.11.2.3 2001/08/14 18:03:19 gallatin Exp $
8 * $DragonFly: src/sys/vfs/gnu/ext2fs/ext2_linux_balloc.c,v 1.11 2007/09/23 04:09:55 yanyh Exp $
11 * linux/fs/ext2/balloc.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 * Enhanced block allocation by Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
22 * The free blocks 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.
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).
32 #include <sys/param.h>
33 #include <sys/systm.h>
36 #include <sys/mount.h>
37 #include <sys/vnode.h>
39 #include <sys/thread2.h>
44 #include "ext2mount.h"
45 #include "ext2_extern.h"
47 #include "ext2_fs_sb.h"
51 #include "i386-bitops.h"
53 #include "ext2_bitops.h"
56 #define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
58 /* got rid of get_group_desc since it can already be found in
63 read_block_bitmap(struct mount
*mp
, unsigned int block_group
,
64 unsigned long bitmap_nr
)
66 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
67 struct ext2_group_desc
* gdp
;
68 struct buffer_head
* bh
;
71 gdp
= get_group_desc (mp
, block_group
, NULL
);
72 error
= bread(VFSTOEXT2(mp
)->um_devvp
,
73 fsbtodoff(sb
, gdp
->bg_block_bitmap
),
74 sb
->s_blocksize
, &bh
);
76 panic ( "read_block_bitmap: "
77 "Cannot read block bitmap - "
78 "block_group = %d, block_bitmap = %lu",
79 block_group
, (unsigned long) gdp
->bg_block_bitmap
);
81 sb
->s_block_bitmap_number
[bitmap_nr
] = block_group
;
82 sb
->s_block_bitmap
[bitmap_nr
] = bh
;
87 * load_block_bitmap loads the block bitmap for a blocks group
89 * It maintains a cache for the last bitmaps loaded. This cache is managed
90 * with a LRU algorithm.
93 * 1/ There is one cache per mounted file system.
94 * 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
95 * this function reads the bitmap without maintaining a LRU cache.
98 load__block_bitmap(struct mount
*mp
, unsigned int block_group
)
101 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
102 unsigned long block_bitmap_number
;
103 struct buffer_head
* block_bitmap
;
105 if (block_group
>= sb
->s_groups_count
)
106 panic ( "load_block_bitmap: "
107 "block_group >= groups_count - "
108 "block_group = %d, groups_count = %lu",
109 block_group
, sb
->s_groups_count
);
111 if (sb
->s_groups_count
<= EXT2_MAX_GROUP_LOADED
) {
112 if (sb
->s_block_bitmap
[block_group
]) {
113 if (sb
->s_block_bitmap_number
[block_group
] !=
115 panic ( "load_block_bitmap: "
116 "block_group != block_bitmap_number");
120 read_block_bitmap (mp
, block_group
, block_group
);
125 for (i
= 0; i
< sb
->s_loaded_block_bitmaps
&&
126 sb
->s_block_bitmap_number
[i
] != block_group
; i
++)
128 if (i
< sb
->s_loaded_block_bitmaps
&&
129 sb
->s_block_bitmap_number
[i
] == block_group
) {
130 block_bitmap_number
= sb
->s_block_bitmap_number
[i
];
131 block_bitmap
= sb
->s_block_bitmap
[i
];
132 for (j
= i
; j
> 0; j
--) {
133 sb
->s_block_bitmap_number
[j
] =
134 sb
->s_block_bitmap_number
[j
- 1];
135 sb
->s_block_bitmap
[j
] =
136 sb
->s_block_bitmap
[j
- 1];
138 sb
->s_block_bitmap_number
[0] = block_bitmap_number
;
139 sb
->s_block_bitmap
[0] = block_bitmap
;
141 if (sb
->s_loaded_block_bitmaps
< EXT2_MAX_GROUP_LOADED
)
142 sb
->s_loaded_block_bitmaps
++;
144 ULCK_BUF(sb
->s_block_bitmap
[EXT2_MAX_GROUP_LOADED
- 1])
146 for (j
= sb
->s_loaded_block_bitmaps
- 1; j
> 0; j
--) {
147 sb
->s_block_bitmap_number
[j
] =
148 sb
->s_block_bitmap_number
[j
- 1];
149 sb
->s_block_bitmap
[j
] =
150 sb
->s_block_bitmap
[j
- 1];
152 read_block_bitmap (mp
, block_group
, 0);
158 load_block_bitmap(struct mount
* mp
, unsigned int block_group
)
160 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
161 if (sb
->s_loaded_block_bitmaps
> 0 &&
162 sb
->s_block_bitmap_number
[0] == block_group
)
165 if (sb
->s_groups_count
<= EXT2_MAX_GROUP_LOADED
&&
166 sb
->s_block_bitmap_number
[block_group
] == block_group
&&
167 sb
->s_block_bitmap
[block_group
])
170 return load__block_bitmap (mp
, block_group
);
174 ext2_free_blocks(struct mount
* mp
, unsigned long block
,
177 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
178 struct buffer_head
* bh
;
179 struct buffer_head
* bh2
;
180 unsigned long block_group
;
184 struct ext2_group_desc
* gdp
;
185 struct ext2_super_block
* es
= sb
->s_es
;
188 kprintf ("ext2_free_blocks: nonexistent device");
191 lock_super (VFSTOEXT2(mp
)->um_devvp
);
192 if (block
< es
->s_first_data_block
||
193 (block
+ count
) > es
->s_blocks_count
) {
194 kprintf ( "ext2_free_blocks: "
195 "Freeing blocks not in datazone - "
196 "block = %lu, count = %lu", block
, count
);
197 unlock_super (VFSTOEXT2(mp
)->um_devvp
);
201 ext2_debug ("freeing blocks %lu to %lu\n", block
, block
+count
-1);
203 block_group
= (block
- es
->s_first_data_block
) /
204 EXT2_BLOCKS_PER_GROUP(sb
);
205 bit
= (block
- es
->s_first_data_block
) % EXT2_BLOCKS_PER_GROUP(sb
);
206 if (bit
+ count
> EXT2_BLOCKS_PER_GROUP(sb
))
207 panic ( "ext2_free_blocks: "
208 "Freeing blocks across group boundary - "
209 "Block = %lu, count = %lu",
211 bitmap_nr
= load_block_bitmap (mp
, block_group
);
212 bh
= sb
->s_block_bitmap
[bitmap_nr
];
213 gdp
= get_group_desc (mp
, block_group
, &bh2
);
215 if (/* test_opt (sb, CHECK_STRICT) && assume always strict ! */
216 (in_range (gdp
->bg_block_bitmap
, block
, count
) ||
217 in_range (gdp
->bg_inode_bitmap
, block
, count
) ||
218 in_range (block
, gdp
->bg_inode_table
,
219 sb
->s_itb_per_group
) ||
220 in_range (block
+ count
- 1, gdp
->bg_inode_table
,
221 sb
->s_itb_per_group
)))
222 panic ( "ext2_free_blocks: "
223 "Freeing blocks in system zones - "
224 "Block = %lu, count = %lu",
227 for (i
= 0; i
< count
; i
++) {
228 if (!clear_bit (bit
+ i
, bh
->b_data
))
229 kprintf ("ext2_free_blocks: "
230 "bit already cleared for block %lu",
233 gdp
->bg_free_blocks_count
++;
234 es
->s_free_blocks_count
++;
238 mark_buffer_dirty(bh2
);
239 mark_buffer_dirty(bh
);
241 if (sb->s_flags & MS_SYNCHRONOUS) {
242 ll_rw_block (WRITE, 1, &bh);
247 unlock_super (VFSTOEXT2(mp
)->um_devvp
);
252 * ext2_new_block uses a goal block to assist allocation. If the goal is
253 * free, or there is a free block within 32 blocks of the goal, that block
254 * is allocated. Otherwise a forward search is made for a free block; within
255 * each block group the search first looks for an entire free byte in the block
256 * bitmap, and then for any free bit if that fails.
259 ext2_new_block(struct mount
* mp
, unsigned long goal
,
260 u_int32_t
* prealloc_count
,
261 u_int32_t
* prealloc_block
)
263 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
264 struct buffer_head
* bh
;
265 struct buffer_head
* bh2
;
269 struct ext2_group_desc
* gdp
;
270 struct ext2_super_block
* es
= sb
->s_es
;
273 static int goal_hits
= 0, goal_attempts
= 0;
276 kprintf ("ext2_new_block: nonexistent device");
279 lock_super (VFSTOEXT2(mp
)->um_devvp
);
281 ext2_debug ("goal=%lu.\n", goal
);
285 * First, test whether the goal block is free.
287 if (goal
< es
->s_first_data_block
|| goal
>= es
->s_blocks_count
)
288 goal
= es
->s_first_data_block
;
289 i
= (goal
- es
->s_first_data_block
) / EXT2_BLOCKS_PER_GROUP(sb
);
290 gdp
= get_group_desc (mp
, i
, &bh2
);
291 if (gdp
->bg_free_blocks_count
> 0) {
292 j
= ((goal
- es
->s_first_data_block
) % EXT2_BLOCKS_PER_GROUP(sb
));
297 bitmap_nr
= load_block_bitmap (mp
, i
);
298 bh
= sb
->s_block_bitmap
[bitmap_nr
];
300 ext2_debug ("goal is at %d:%d.\n", i
, j
);
302 if (!test_bit(j
, bh
->b_data
)) {
305 ext2_debug ("goal bit allocated.\n");
311 * The goal was occupied; search forward for a free
312 * block within the next XX blocks.
314 * end_goal is more or less random, but it has to be
315 * less than EXT2_BLOCKS_PER_GROUP. Aligning up to the
316 * next 64-bit boundary is simple..
318 int end_goal
= (j
+ 63) & ~63;
319 j
= find_next_zero_bit(bh
->b_data
, end_goal
, j
);
324 ext2_debug ("Bit not found near goal\n");
327 * There has been no free block found in the near vicinity
328 * of the goal: do a search forward through the block groups,
329 * searching in each group first for an entire free byte in
330 * the bitmap and then for any free bit.
332 * Search first in the remainder of the current group; then,
333 * cyclicly search through the rest of the groups.
335 p
= ((char *) bh
->b_data
) + (j
>> 3);
336 r
= memscan(p
, 0, (EXT2_BLOCKS_PER_GROUP(sb
) - j
+ 7) >> 3);
337 k
= (r
- ((char *) bh
->b_data
)) << 3;
338 if (k
< EXT2_BLOCKS_PER_GROUP(sb
)) {
342 k
= find_next_zero_bit ((unsigned long *) bh
->b_data
,
343 EXT2_BLOCKS_PER_GROUP(sb
),
345 if (k
< EXT2_BLOCKS_PER_GROUP(sb
)) {
351 ext2_debug ("Bit not found in block group %d.\n", i
);
354 * Now search the rest of the groups. We assume that
355 * i and gdp correctly point to the last group visited.
357 for (k
= 0; k
< sb
->s_groups_count
; k
++) {
359 if (i
>= sb
->s_groups_count
)
361 gdp
= get_group_desc (mp
, i
, &bh2
);
362 if (gdp
->bg_free_blocks_count
> 0)
365 if (k
>= sb
->s_groups_count
) {
366 unlock_super (VFSTOEXT2(mp
)->um_devvp
);
369 bitmap_nr
= load_block_bitmap (mp
, i
);
370 bh
= sb
->s_block_bitmap
[bitmap_nr
];
371 r
= memscan(bh
->b_data
, 0, EXT2_BLOCKS_PER_GROUP(sb
) >> 3);
372 j
= (r
- bh
->b_data
) << 3;
374 if (j
< EXT2_BLOCKS_PER_GROUP(sb
))
377 j
= find_first_zero_bit ((unsigned long *) bh
->b_data
,
378 EXT2_BLOCKS_PER_GROUP(sb
));
379 if (j
>= EXT2_BLOCKS_PER_GROUP(sb
)) {
380 kprintf ( "ext2_new_block: "
381 "Free blocks count corrupted for block group %d", i
);
382 unlock_super (VFSTOEXT2(mp
)->um_devvp
);
388 * We have succeeded in finding a free byte in the block
389 * bitmap. Now search backwards up to 7 bits to find the
390 * start of this group of free blocks.
392 for (k
= 0; k
< 7 && j
> 0 && !test_bit (j
- 1, bh
->b_data
); k
++, j
--);
396 ext2_debug ("using block group %d(%d)\n", i
, gdp
->bg_free_blocks_count
);
398 tmp
= j
+ i
* EXT2_BLOCKS_PER_GROUP(sb
) + es
->s_first_data_block
;
400 if (/* test_opt (sb, CHECK_STRICT) && we are always strict. */
401 (tmp
== gdp
->bg_block_bitmap
||
402 tmp
== gdp
->bg_inode_bitmap
||
403 in_range (tmp
, gdp
->bg_inode_table
, sb
->s_itb_per_group
)))
404 panic ( "ext2_new_block: "
405 "Allocating block in system zone - "
406 "%dth block = %u in group %u", j
, tmp
, i
);
408 if (set_bit (j
, bh
->b_data
)) {
409 kprintf ( "ext2_new_block: "
410 "bit already set for block %d", j
);
414 ext2_debug ("found bit %d\n", j
);
417 * Do block preallocation now if required.
419 #ifdef EXT2_PREALLOCATE
420 if (prealloc_block
) {
422 *prealloc_block
= tmp
+ 1;
424 k
< 8 && (j
+ k
) < EXT2_BLOCKS_PER_GROUP(sb
); k
++) {
425 if (set_bit (j
+ k
, bh
->b_data
))
429 gdp
->bg_free_blocks_count
-= *prealloc_count
;
430 es
->s_free_blocks_count
-= *prealloc_count
;
431 ext2_debug ("Preallocated a further %lu bits.\n",
438 mark_buffer_dirty(bh
);
440 if (sb->s_flags & MS_SYNCHRONOUS) {
441 ll_rw_block (WRITE, 1, &bh);
445 if (j
>= es
->s_blocks_count
) {
446 kprintf ( "ext2_new_block: "
447 "block >= blocks count - "
448 "block_group = %d, block=%d", i
, j
);
449 unlock_super (VFSTOEXT2(mp
)->um_devvp
);
453 ext2_debug ("allocating block %d. "
454 "Goal hits %d of %d.\n", j
, goal_hits
, goal_attempts
);
456 gdp
->bg_free_blocks_count
--;
457 mark_buffer_dirty(bh2
);
458 es
->s_free_blocks_count
--;
460 unlock_super (VFSTOEXT2(mp
)->um_devvp
);
466 ext2_count_free_blocks(struct mount
* mp
)
468 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
470 struct ext2_super_block
* es
;
471 unsigned long desc_count
, bitmap_count
, x
;
473 struct ext2_group_desc
* gdp
;
476 lock_super (VFSTOEXT2(mp
)->um_devvp
);
481 for (i
= 0; i
< sb
->s_groups_count
; i
++) {
482 gdp
= get_group_desc (mp
, i
, NULL
);
483 desc_count
+= gdp
->bg_free_blocks_count
;
484 bitmap_nr
= load_block_bitmap (mp
, i
);
485 x
= ext2_count_free (sb
->s_block_bitmap
[bitmap_nr
],
487 ext2_debug ("group %d: stored = %d, counted = %lu\n",
488 i
, gdp
->bg_free_blocks_count
, x
);
491 ext2_debug( "stored = %lu, computed = %lu, %lu\n",
492 es
->s_free_blocks_count
, desc_count
, bitmap_count
);
493 unlock_super (VFSTOEXT2(mp
)->um_devvp
);
496 return sb
->s_es
->s_free_blocks_count
;
502 block_in_use (unsigned long block
, struct ext2_sb_info
*sb
,
505 return test_bit ((block
- sb
->s_es
->s_first_data_block
) %
506 EXT2_BLOCKS_PER_GROUP(sb
), map
);
510 test_root(int a
, int b
)
524 ext2_group_sparse(int group
)
526 return (test_root(group
, 3) || test_root(group
, 5) ||
527 test_root(group
, 7));
532 ext2_check_blocks_bitmap(struct mount
* mp
)
534 struct ext2_sb_info
*sb
= VFSTOEXT2(mp
)->um_e2fs
;
535 struct buffer_head
* bh
;
536 struct ext2_super_block
* es
;
537 unsigned long desc_count
, bitmap_count
, x
;
538 unsigned long desc_blocks
;
540 struct ext2_group_desc
* gdp
;
543 lock_super (VFSTOEXT2(mp
)->um_devvp
);
548 desc_blocks
= (sb
->s_groups_count
+ EXT2_DESC_PER_BLOCK(sb
) - 1) /
549 EXT2_DESC_PER_BLOCK(sb
);
550 for (i
= 0; i
< sb
->s_groups_count
; i
++) {
551 gdp
= get_group_desc (mp
, i
, NULL
);
552 desc_count
+= gdp
->bg_free_blocks_count
;
553 bitmap_nr
= load_block_bitmap (mp
, i
);
554 bh
= sb
->s_block_bitmap
[bitmap_nr
];
556 if (!(es
->s_feature_ro_compat
&
557 EXT2_FEATURE_RO_COMPAT_SPARSE_SUPER
) ||
558 ext2_group_sparse(i
)) {
559 if (!test_bit (0, bh
->b_data
))
560 kprintf ("ext2_check_blocks_bitmap: "
561 "Superblock in group %d "
562 "is marked free", i
);
564 for (j
= 0; j
< desc_blocks
; j
++)
565 if (!test_bit (j
+ 1, bh
->b_data
))
566 kprintf ("ext2_check_blocks_bitmap: "
567 "Descriptor block #%d in group "
568 "%d is marked free", j
, i
);
571 if (!block_in_use (gdp
->bg_block_bitmap
, sb
, bh
->b_data
))
572 kprintf ("ext2_check_blocks_bitmap: "
573 "Block bitmap for group %d is marked free",
576 if (!block_in_use (gdp
->bg_inode_bitmap
, sb
, bh
->b_data
))
577 kprintf ("ext2_check_blocks_bitmap: "
578 "Inode bitmap for group %d is marked free",
581 for (j
= 0; j
< sb
->s_itb_per_group
; j
++)
582 if (!block_in_use (gdp
->bg_inode_table
+ j
, sb
, bh
->b_data
))
583 kprintf ("ext2_check_blocks_bitmap: "
584 "Block #%d of the inode table in "
585 "group %d is marked free", j
, i
);
587 x
= ext2_count_free (bh
, sb
->s_blocksize
);
588 if (gdp
->bg_free_blocks_count
!= x
)
589 kprintf ("ext2_check_blocks_bitmap: "
590 "Wrong free blocks count for group %d, "
591 "stored = %d, counted = %lu", i
,
592 gdp
->bg_free_blocks_count
, x
);
595 if (es
->s_free_blocks_count
!= bitmap_count
)
596 kprintf ("ext2_check_blocks_bitmap: "
597 "Wrong free blocks count in super block, "
598 "stored = %lu, counted = %lu",
599 (unsigned long) es
->s_free_blocks_count
, bitmap_count
);
600 unlock_super (VFSTOEXT2(mp
)->um_devvp
);
605 * this function is taken from
606 * linux/fs/ext2/bitmap.c
609 static int nibblemap
[] = {4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
611 unsigned long ext2_count_free (struct buffer_head
* map
, unsigned int numchars
)
614 unsigned long sum
= 0;
618 for (i
= 0; i
< numchars
; i
++)
619 sum
+= nibblemap
[map
->b_data
[i
] & 0xf] +
620 nibblemap
[(map
->b_data
[i
] >> 4) & 0xf];