This source file includes following definitions.
- get_group_desc
- read_block_bitmap
- load__block_bitmap
- load_block_bitmap
- ext2_free_blocks
- ext2_new_block
- ext2_count_free_blocks
- block_in_use
- ext2_check_blocks_bitmap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 #include <linux/fs.h>
27 #include <linux/ext2_fs.h>
28 #include <linux/stat.h>
29 #include <linux/sched.h>
30 #include <linux/string.h>
31 #include <linux/locks.h>
32
33 #include <asm/bitops.h>
34
35 #define in_range(b, first, len) ((b) >= (first) && (b) <= (first) + (len) - 1)
36
37 static struct ext2_group_desc * get_group_desc (struct super_block * sb,
38 unsigned int block_group,
39 struct buffer_head ** bh)
40 {
41 unsigned long group_desc;
42 unsigned long desc;
43 struct ext2_group_desc * gdp;
44
45 if (block_group >= sb->u.ext2_sb.s_groups_count)
46 ext2_panic (sb, "get_group_desc",
47 "block_group >= groups_count - "
48 "block_group = %d, groups_count = %lu",
49 block_group, sb->u.ext2_sb.s_groups_count);
50
51 group_desc = block_group / EXT2_DESC_PER_BLOCK(sb);
52 desc = block_group % EXT2_DESC_PER_BLOCK(sb);
53 if (!sb->u.ext2_sb.s_group_desc[group_desc])
54 ext2_panic (sb, "get_group_desc",
55 "Group descriptor not loaded - "
56 "block_group = %d, group_desc = %lu, desc = %lu",
57 block_group, group_desc, desc);
58 gdp = (struct ext2_group_desc *)
59 sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
60 if (bh)
61 *bh = sb->u.ext2_sb.s_group_desc[group_desc];
62 return gdp + desc;
63 }
64
65 static void read_block_bitmap (struct super_block * sb,
66 unsigned int block_group,
67 unsigned long bitmap_nr)
68 {
69 struct ext2_group_desc * gdp;
70 struct buffer_head * bh;
71
72 gdp = get_group_desc (sb, block_group, NULL);
73 bh = bread (sb->s_dev, gdp->bg_block_bitmap, sb->s_blocksize);
74 if (!bh)
75 ext2_panic (sb, "read_block_bitmap",
76 "Cannot read block bitmap - "
77 "block_group = %d, block_bitmap = %lu",
78 block_group, gdp->bg_block_bitmap);
79 sb->u.ext2_sb.s_block_bitmap_number[bitmap_nr] = block_group;
80 sb->u.ext2_sb.s_block_bitmap[bitmap_nr] = bh;
81 }
82
83
84
85
86
87
88
89
90
91
92
93
94 static int load__block_bitmap (struct super_block * sb,
95 unsigned int block_group)
96 {
97 int i, j;
98 unsigned long block_bitmap_number;
99 struct buffer_head * block_bitmap;
100
101 if (block_group >= sb->u.ext2_sb.s_groups_count)
102 ext2_panic (sb, "load_block_bitmap",
103 "block_group >= groups_count - "
104 "block_group = %d, groups_count = %lu",
105 block_group, sb->u.ext2_sb.s_groups_count);
106
107 if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED) {
108 if (sb->u.ext2_sb.s_block_bitmap[block_group]) {
109 if (sb->u.ext2_sb.s_block_bitmap_number[block_group] !=
110 block_group)
111 ext2_panic (sb, "load_block_bitmap",
112 "block_group != block_bitmap_number");
113 else
114 return block_group;
115 } else {
116 read_block_bitmap (sb, block_group, block_group);
117 return block_group;
118 }
119 }
120
121 for (i = 0; i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
122 sb->u.ext2_sb.s_block_bitmap_number[i] != block_group; i++)
123 ;
124 if (i < sb->u.ext2_sb.s_loaded_block_bitmaps &&
125 sb->u.ext2_sb.s_block_bitmap_number[i] == block_group) {
126 block_bitmap_number = sb->u.ext2_sb.s_block_bitmap_number[i];
127 block_bitmap = sb->u.ext2_sb.s_block_bitmap[i];
128 for (j = i; j > 0; j--) {
129 sb->u.ext2_sb.s_block_bitmap_number[j] =
130 sb->u.ext2_sb.s_block_bitmap_number[j - 1];
131 sb->u.ext2_sb.s_block_bitmap[j] =
132 sb->u.ext2_sb.s_block_bitmap[j - 1];
133 }
134 sb->u.ext2_sb.s_block_bitmap_number[0] = block_bitmap_number;
135 sb->u.ext2_sb.s_block_bitmap[0] = block_bitmap;
136 } else {
137 if (sb->u.ext2_sb.s_loaded_block_bitmaps < EXT2_MAX_GROUP_LOADED)
138 sb->u.ext2_sb.s_loaded_block_bitmaps++;
139 else
140 brelse (sb->u.ext2_sb.s_block_bitmap[EXT2_MAX_GROUP_LOADED - 1]);
141 for (j = sb->u.ext2_sb.s_loaded_block_bitmaps - 1; j > 0; j--) {
142 sb->u.ext2_sb.s_block_bitmap_number[j] =
143 sb->u.ext2_sb.s_block_bitmap_number[j - 1];
144 sb->u.ext2_sb.s_block_bitmap[j] =
145 sb->u.ext2_sb.s_block_bitmap[j - 1];
146 }
147 read_block_bitmap (sb, block_group, 0);
148 }
149 return 0;
150 }
151
152 static inline int load_block_bitmap (struct super_block * sb,
153 unsigned int block_group)
154 {
155 if (sb->u.ext2_sb.s_loaded_block_bitmaps > 0 &&
156 sb->u.ext2_sb.s_block_bitmap_number[0] == block_group)
157 return 0;
158
159 if (sb->u.ext2_sb.s_groups_count <= EXT2_MAX_GROUP_LOADED &&
160 sb->u.ext2_sb.s_block_bitmap_number[block_group] == block_group &&
161 sb->u.ext2_sb.s_block_bitmap[block_group])
162 return block_group;
163
164 return load__block_bitmap (sb, block_group);
165 }
166
167 void ext2_free_blocks (struct super_block * sb, unsigned long block,
168 unsigned long count)
169 {
170 struct buffer_head * bh;
171 struct buffer_head * bh2;
172 unsigned long block_group;
173 unsigned long bit;
174 unsigned long i;
175 int bitmap_nr;
176 struct ext2_group_desc * gdp;
177 struct ext2_super_block * es;
178
179 if (!sb) {
180 printk ("ext2_free_blocks: nonexistent device");
181 return;
182 }
183 lock_super (sb);
184 es = sb->u.ext2_sb.s_es;
185 if (block < es->s_first_data_block ||
186 (block + count) > es->s_blocks_count) {
187 ext2_error (sb, "ext2_free_blocks",
188 "Freeing blocks not in datazone - "
189 "block = %lu, count = %lu", block, count);
190 unlock_super (sb);
191 return;
192 }
193
194 ext2_debug ("freeing block %lu\n", block);
195
196 block_group = (block - es->s_first_data_block) /
197 EXT2_BLOCKS_PER_GROUP(sb);
198 bit = (block - es->s_first_data_block) % EXT2_BLOCKS_PER_GROUP(sb);
199 if (bit + count > EXT2_BLOCKS_PER_GROUP(sb))
200 ext2_panic (sb, "ext2_free_blocks",
201 "Freeing blocks across group boundary - "
202 "Block = %lu, count = %lu",
203 block, count);
204 bitmap_nr = load_block_bitmap (sb, block_group);
205 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
206 gdp = get_group_desc (sb, block_group, &bh2);
207
208 if (test_opt (sb, CHECK_STRICT) &&
209 (in_range (gdp->bg_block_bitmap, block, count) ||
210 in_range (gdp->bg_inode_bitmap, block, count) ||
211 in_range (block, gdp->bg_inode_table,
212 sb->u.ext2_sb.s_itb_per_group) ||
213 in_range (block + count - 1, gdp->bg_inode_table,
214 sb->u.ext2_sb.s_itb_per_group)))
215 ext2_panic (sb, "ext2_free_blocks",
216 "Freeing blocks in system zones - "
217 "Block = %lu, count = %lu",
218 block, count);
219
220 for (i = 0; i < count; i++) {
221 if (!clear_bit (bit + i, bh->b_data))
222 ext2_warning (sb, "ext2_free_blocks",
223 "bit already cleared for block %lu",
224 block);
225 else {
226 gdp->bg_free_blocks_count++;
227 es->s_free_blocks_count++;
228 }
229 }
230
231 mark_buffer_dirty(bh2, 1);
232 mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1);
233
234 mark_buffer_dirty(bh, 1);
235 if (sb->s_flags & MS_SYNCHRONOUS) {
236 ll_rw_block (WRITE, 1, &bh);
237 wait_on_buffer (bh);
238 }
239 sb->s_dirt = 1;
240 unlock_super (sb);
241 return;
242 }
243
244
245
246
247
248
249
250
251 int ext2_new_block (struct super_block * sb, unsigned long goal,
252 unsigned long * prealloc_count,
253 unsigned long * prealloc_block)
254 {
255 struct buffer_head * bh;
256 struct buffer_head * bh2;
257 char * p, * r;
258 int i, j, k, tmp;
259 unsigned long lmap;
260 int bitmap_nr;
261 struct ext2_group_desc * gdp;
262 struct ext2_super_block * es;
263
264 #ifdef EXT2FS_DEBUG
265 static int goal_hits = 0, goal_attempts = 0;
266 #endif
267 if (!sb) {
268 printk ("ext2_new_block: nonexistent device");
269 return 0;
270 }
271 lock_super (sb);
272 es = sb->u.ext2_sb.s_es;
273 if (es->s_free_blocks_count <= es->s_r_blocks_count &&
274 (!fsuser() && (sb->u.ext2_sb.s_resuid != current->fsuid) &&
275 (sb->u.ext2_sb.s_resgid == 0 ||
276 !in_group_p (sb->u.ext2_sb.s_resgid)))) {
277 unlock_super (sb);
278 return 0;
279 }
280
281 ext2_debug ("goal=%lu.\n", goal);
282
283 repeat:
284
285
286
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 (sb, i, &bh2);
291 if (gdp->bg_free_blocks_count > 0) {
292 j = ((goal - es->s_first_data_block) % EXT2_BLOCKS_PER_GROUP(sb));
293 #ifdef EXT2FS_DEBUG
294 if (j)
295 goal_attempts++;
296 #endif
297 bitmap_nr = load_block_bitmap (sb, i);
298 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
299
300 ext2_debug ("goal is at %d:%d.\n", i, j);
301
302 if (!test_bit(j, bh->b_data)) {
303 #ifdef EXT2FS_DEBUG
304 goal_hits++;
305 ext2_debug ("goal bit allocated.\n");
306 #endif
307 goto got_block;
308 }
309 if (j) {
310
311
312
313
314 lmap = ((((unsigned long *) bh->b_data)[j >> 5]) >>
315 ((j & 31) + 1));
316 if (j < EXT2_BLOCKS_PER_GROUP(sb) - 32)
317 lmap |= (((unsigned long *) bh->b_data)[(j >> 5) + 1]) <<
318 (31 - (j & 31));
319 else
320 lmap |= 0xffffffff << (31 - (j & 31));
321 if (lmap != 0xffffffffl) {
322 k = ffz(lmap) + 1;
323 if ((j + k) < EXT2_BLOCKS_PER_GROUP(sb)) {
324 j += k;
325 goto got_block;
326 }
327 }
328 }
329
330 ext2_debug ("Bit not found near goal\n");
331
332
333
334
335
336
337
338
339
340
341 p = ((char *) bh->b_data) + (j >> 3);
342 r = memscan(p, 0, (EXT2_BLOCKS_PER_GROUP(sb) - j + 7) >> 3);
343 k = (r - ((char *) bh->b_data)) << 3;
344 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
345 j = k;
346 goto search_back;
347 }
348 k = find_next_zero_bit ((unsigned long *) bh->b_data,
349 EXT2_BLOCKS_PER_GROUP(sb),
350 j);
351 if (k < EXT2_BLOCKS_PER_GROUP(sb)) {
352 j = k;
353 goto got_block;
354 }
355 }
356
357 ext2_debug ("Bit not found in block group %d.\n", i);
358
359
360
361
362
363 for (k = 0; k < sb->u.ext2_sb.s_groups_count; k++) {
364 i++;
365 if (i >= sb->u.ext2_sb.s_groups_count)
366 i = 0;
367 gdp = get_group_desc (sb, i, &bh2);
368 if (gdp->bg_free_blocks_count > 0)
369 break;
370 }
371 if (k >= sb->u.ext2_sb.s_groups_count) {
372 unlock_super (sb);
373 return 0;
374 }
375 bitmap_nr = load_block_bitmap (sb, i);
376 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
377 r = memscan(bh->b_data, 0, EXT2_BLOCKS_PER_GROUP(sb) >> 3);
378 j = (r - bh->b_data) << 3;
379 if (j < EXT2_BLOCKS_PER_GROUP(sb))
380 goto search_back;
381 else
382 j = find_first_zero_bit ((unsigned long *) bh->b_data,
383 EXT2_BLOCKS_PER_GROUP(sb));
384 if (j >= EXT2_BLOCKS_PER_GROUP(sb)) {
385 ext2_error (sb, "ext2_new_block",
386 "Free blocks count corrupted for block group %d", i);
387 unlock_super (sb);
388 return 0;
389 }
390
391 search_back:
392
393
394
395
396
397 for (k = 0; k < 7 && j > 0 && !test_bit (j - 1, bh->b_data); k++, j--);
398
399 got_block:
400
401 ext2_debug ("using block group %d(%d)\n", i, gdp->bg_free_blocks_count);
402
403 tmp = j + i * EXT2_BLOCKS_PER_GROUP(sb) + es->s_first_data_block;
404
405 if (test_opt (sb, CHECK_STRICT) &&
406 (tmp == gdp->bg_block_bitmap ||
407 tmp == gdp->bg_inode_bitmap ||
408 in_range (tmp, gdp->bg_inode_table, sb->u.ext2_sb.s_itb_per_group)))
409 ext2_panic (sb, "ext2_new_block",
410 "Allocating block in system zone - "
411 "block = %u", tmp);
412
413 if (set_bit (j, bh->b_data)) {
414 ext2_warning (sb, "ext2_new_block",
415 "bit already set for block %d", j);
416 goto repeat;
417 }
418
419 ext2_debug ("found bit %d\n", j);
420
421
422
423
424 #ifdef EXT2_PREALLOCATE
425 if (prealloc_block) {
426 *prealloc_count = 0;
427 *prealloc_block = tmp + 1;
428 for (k = 1;
429 k < 8 && (j + k) < EXT2_BLOCKS_PER_GROUP(sb); k++) {
430 if (set_bit (j + k, bh->b_data))
431 break;
432 (*prealloc_count)++;
433 }
434 gdp->bg_free_blocks_count -= *prealloc_count;
435 es->s_free_blocks_count -= *prealloc_count;
436 ext2_debug ("Preallocated a further %lu bits.\n",
437 *prealloc_count);
438 }
439 #endif
440
441 j = tmp;
442
443 mark_buffer_dirty(bh, 1);
444 if (sb->s_flags & MS_SYNCHRONOUS) {
445 ll_rw_block (WRITE, 1, &bh);
446 wait_on_buffer (bh);
447 }
448
449 if (j >= es->s_blocks_count) {
450 ext2_error (sb, "ext2_new_block",
451 "block >= blocks count - "
452 "block_group = %d, block=%d", i, j);
453 unlock_super (sb);
454 return 0;
455 }
456 if (!(bh = getblk (sb->s_dev, j, sb->s_blocksize))) {
457 ext2_error (sb, "ext2_new_block", "cannot get block %d", j);
458 unlock_super (sb);
459 return 0;
460 }
461 memset(bh->b_data, 0, sb->s_blocksize);
462 bh->b_uptodate = 1;
463 mark_buffer_dirty(bh, 1);
464 brelse (bh);
465
466 ext2_debug ("allocating block %d. "
467 "Goal hits %d of %d.\n", j, goal_hits, goal_attempts);
468
469 gdp->bg_free_blocks_count--;
470 mark_buffer_dirty(bh2, 1);
471 es->s_free_blocks_count--;
472 mark_buffer_dirty(sb->u.ext2_sb.s_sbh, 1);
473 sb->s_dirt = 1;
474 unlock_super (sb);
475 return j;
476 }
477
478 unsigned long ext2_count_free_blocks (struct super_block * sb)
479 {
480 #ifdef EXT2FS_DEBUG
481 struct ext2_super_block * es;
482 unsigned long desc_count, bitmap_count, x;
483 int bitmap_nr;
484 struct ext2_group_desc * gdp;
485 int i;
486
487 lock_super (sb);
488 es = sb->u.ext2_sb.s_es;
489 desc_count = 0;
490 bitmap_count = 0;
491 gdp = NULL;
492 for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
493 gdp = get_group_desc (sb, i, NULL);
494 desc_count += gdp->bg_free_blocks_count;
495 bitmap_nr = load_block_bitmap (sb, i);
496 x = ext2_count_free (sb->u.ext2_sb.s_block_bitmap[bitmap_nr],
497 sb->s_blocksize);
498 printk ("group %d: stored = %d, counted = %lu\n",
499 i, gdp->bg_free_blocks_count, x);
500 bitmap_count += x;
501 }
502 printk("ext2_count_free_blocks: stored = %lu, computed = %lu, %lu\n",
503 es->s_free_blocks_count, desc_count, bitmap_count);
504 unlock_super (sb);
505 return bitmap_count;
506 #else
507 return sb->u.ext2_sb.s_es->s_free_blocks_count;
508 #endif
509 }
510
511 static inline int block_in_use (unsigned long block,
512 struct super_block * sb,
513 unsigned char * map)
514 {
515 return test_bit ((block - sb->u.ext2_sb.s_es->s_first_data_block) %
516 EXT2_BLOCKS_PER_GROUP(sb), map);
517 }
518
519 void ext2_check_blocks_bitmap (struct super_block * sb)
520 {
521 struct buffer_head * bh;
522 struct ext2_super_block * es;
523 unsigned long desc_count, bitmap_count, x;
524 unsigned long desc_blocks;
525 int bitmap_nr;
526 struct ext2_group_desc * gdp;
527 int i, j;
528
529 lock_super (sb);
530 es = sb->u.ext2_sb.s_es;
531 desc_count = 0;
532 bitmap_count = 0;
533 gdp = NULL;
534 desc_blocks = (sb->u.ext2_sb.s_groups_count + EXT2_DESC_PER_BLOCK(sb) - 1) /
535 EXT2_DESC_PER_BLOCK(sb);
536 for (i = 0; i < sb->u.ext2_sb.s_groups_count; i++) {
537 gdp = get_group_desc (sb, i, NULL);
538 desc_count += gdp->bg_free_blocks_count;
539 bitmap_nr = load_block_bitmap (sb, i);
540 bh = sb->u.ext2_sb.s_block_bitmap[bitmap_nr];
541
542 if (!test_bit (0, bh->b_data))
543 ext2_error (sb, "ext2_check_blocks_bitmap",
544 "Superblock in group %d is marked free", i);
545
546 for (j = 0; j < desc_blocks; j++)
547 if (!test_bit (j + 1, bh->b_data))
548 ext2_error (sb, "ext2_check_blocks_bitmap",
549 "Descriptor block #%d in group "
550 "%d is marked free", j, i);
551
552 if (!block_in_use (gdp->bg_block_bitmap, sb, bh->b_data))
553 ext2_error (sb, "ext2_check_blocks_bitmap",
554 "Block bitmap for group %d is marked free",
555 i);
556
557 if (!block_in_use (gdp->bg_inode_bitmap, sb, bh->b_data))
558 ext2_error (sb, "ext2_check_blocks_bitmap",
559 "Inode bitmap for group %d is marked free",
560 i);
561
562 for (j = 0; j < sb->u.ext2_sb.s_itb_per_group; j++)
563 if (!block_in_use (gdp->bg_inode_table + j, sb, bh->b_data))
564 ext2_error (sb, "ext2_check_blocks_bitmap",
565 "Block #%d of the inode table in "
566 "group %d is marked free", j, i);
567
568 x = ext2_count_free (bh, sb->s_blocksize);
569 if (gdp->bg_free_blocks_count != x)
570 ext2_error (sb, "ext2_check_blocks_bitmap",
571 "Wrong free blocks count for group %d, "
572 "stored = %d, counted = %lu", i,
573 gdp->bg_free_blocks_count, x);
574 bitmap_count += x;
575 }
576 if (es->s_free_blocks_count != bitmap_count)
577 ext2_error (sb, "ext2_check_blocks_bitmap",
578 "Wrong free blocks count in super block, "
579 "stored = %lu, counted = %lu",
580 es->s_free_blocks_count, bitmap_count);
581 unlock_super (sb);
582 }