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