1 /*
2 * pass5.c --- check block and inode bitmaps against on-disk bitmaps
3 *
4 * Copyright (C) 1993, 1994, 1995, 1996, 1997 Theodore Ts'o.
5 *
6 * %Begin-Header%
7 * This file may be redistributed under the terms of the GNU Public
8 * License.
9 * %End-Header%
10 *
11 */
12
13 #include "e2fsck.h"
14 #include "problem.h"
15
16 static void check_block_bitmaps(e2fsck_t ctx);
17 static void check_inode_bitmaps(e2fsck_t ctx);
18 static void check_inode_end(e2fsck_t ctx);
19 static void check_block_end(e2fsck_t ctx);
20
e2fsck_pass5(e2fsck_t ctx)21 void e2fsck_pass5(e2fsck_t ctx)
22 {
23 #ifdef RESOURCE_TRACK
24 struct resource_track rtrack;
25 #endif
26 struct problem_context pctx;
27
28 #ifdef MTRACE
29 mtrace_print("Pass 5");
30 #endif
31
32 #ifdef RESOURCE_TRACK
33 init_resource_track(&rtrack);
34 #endif
35
36 clear_problem_context(&pctx);
37
38 if (!(ctx->options & E2F_OPT_PREEN))
39 fix_problem(ctx, PR_5_PASS_HEADER, &pctx);
40
41 if (ctx->progress)
42 if ((ctx->progress)(ctx, 5, 0, ctx->fs->group_desc_count*2))
43 return;
44
45 e2fsck_read_bitmaps(ctx);
46
47 check_block_bitmaps(ctx);
48 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
49 return;
50 check_inode_bitmaps(ctx);
51 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
52 return;
53 check_inode_end(ctx);
54 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
55 return;
56 check_block_end(ctx);
57 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
58 return;
59
60 ext2fs_free_inode_bitmap(ctx->inode_used_map);
61 ctx->inode_used_map = 0;
62 ext2fs_free_inode_bitmap(ctx->inode_dir_map);
63 ctx->inode_dir_map = 0;
64 ext2fs_free_block_bitmap(ctx->block_found_map);
65 ctx->block_found_map = 0;
66
67 #ifdef RESOURCE_TRACK
68 if (ctx->options & E2F_OPT_TIME2) {
69 e2fsck_clear_progbar(ctx);
70 print_resource_track(_("Pass 5"), &rtrack);
71 }
72 #endif
73 }
74
75 #define NO_BLK ((blk_t) -1)
76
print_bitmap_problem(e2fsck_t ctx,int problem,struct problem_context * pctx)77 static void print_bitmap_problem(e2fsck_t ctx, int problem,
78 struct problem_context *pctx)
79 {
80 switch (problem) {
81 case PR_5_BLOCK_UNUSED:
82 if (pctx->blk == pctx->blk2)
83 pctx->blk2 = 0;
84 else
85 problem = PR_5_BLOCK_RANGE_UNUSED;
86 break;
87 case PR_5_BLOCK_USED:
88 if (pctx->blk == pctx->blk2)
89 pctx->blk2 = 0;
90 else
91 problem = PR_5_BLOCK_RANGE_USED;
92 break;
93 case PR_5_INODE_UNUSED:
94 if (pctx->ino == pctx->ino2)
95 pctx->ino2 = 0;
96 else
97 problem = PR_5_INODE_RANGE_UNUSED;
98 break;
99 case PR_5_INODE_USED:
100 if (pctx->ino == pctx->ino2)
101 pctx->ino2 = 0;
102 else
103 problem = PR_5_INODE_RANGE_USED;
104 break;
105 }
106 fix_problem(ctx, problem, pctx);
107 pctx->blk = pctx->blk2 = NO_BLK;
108 pctx->ino = pctx->ino2 = 0;
109 }
110
check_block_bitmaps(e2fsck_t ctx)111 static void check_block_bitmaps(e2fsck_t ctx)
112 {
113 ext2_filsys fs = ctx->fs;
114 blk_t i, super;
115 int *free_array;
116 int group = 0;
117 unsigned int blocks = 0;
118 unsigned int free_blocks = 0;
119 int group_free = 0;
120 int actual, bitmap;
121 struct problem_context pctx;
122 int problem, save_problem, fixit, had_problem;
123 errcode_t retval;
124 int lazy_bg = 0;
125 int skip_group = 0;
126
127 clear_problem_context(&pctx);
128 free_array = (int *) e2fsck_allocate_memory(ctx,
129 fs->group_desc_count * sizeof(int), "free block count array");
130
131 if ((fs->super->s_first_data_block <
132 ext2fs_get_block_bitmap_start(ctx->block_found_map)) ||
133 (fs->super->s_blocks_count-1 >
134 ext2fs_get_block_bitmap_end(ctx->block_found_map))) {
135 pctx.num = 1;
136 pctx.blk = fs->super->s_first_data_block;
137 pctx.blk2 = fs->super->s_blocks_count -1;
138 pctx.ino = ext2fs_get_block_bitmap_start(ctx->block_found_map);
139 pctx.ino2 = ext2fs_get_block_bitmap_end(ctx->block_found_map);
140 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
141
142 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
143 goto errout;
144 }
145
146 if ((fs->super->s_first_data_block <
147 ext2fs_get_block_bitmap_start(fs->block_map)) ||
148 (fs->super->s_blocks_count-1 >
149 ext2fs_get_block_bitmap_end(fs->block_map))) {
150 pctx.num = 2;
151 pctx.blk = fs->super->s_first_data_block;
152 pctx.blk2 = fs->super->s_blocks_count -1;
153 pctx.ino = ext2fs_get_block_bitmap_start(fs->block_map);
154 pctx.ino2 = ext2fs_get_block_bitmap_end(fs->block_map);
155 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
156
157 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
158 goto errout;
159 }
160
161 if (EXT2_HAS_COMPAT_FEATURE(fs->super, EXT2_FEATURE_COMPAT_LAZY_BG))
162 lazy_bg++;
163
164 redo_counts:
165 had_problem = 0;
166 save_problem = 0;
167 pctx.blk = pctx.blk2 = NO_BLK;
168 if (lazy_bg && (fs->group_desc[group].bg_flags &
169 EXT2_BG_BLOCK_UNINIT))
170 skip_group++;
171 super = fs->super->s_first_data_block;
172 for (i = fs->super->s_first_data_block;
173 i < fs->super->s_blocks_count;
174 i++) {
175 actual = ext2fs_fast_test_block_bitmap(ctx->block_found_map, i);
176
177 if (skip_group) {
178 if ((i >= super) &&
179 (i <= super + fs->desc_blocks) &&
180 ext2fs_bg_has_super(fs, group))
181 bitmap = 1;
182 else if (i == fs->group_desc[group].bg_block_bitmap)
183 bitmap = 1;
184 else if (i == fs->group_desc[group].bg_inode_bitmap)
185 bitmap = 1;
186 else if (i >= fs->group_desc[group].bg_inode_table &&
187 (i < fs->group_desc[group].bg_inode_table
188 + fs->inode_blocks_per_group))
189 bitmap = 1;
190 else
191 bitmap = 0;
192 actual = (actual != 0);
193 } else
194 bitmap = ext2fs_fast_test_block_bitmap(fs->block_map, i);
195
196 if (actual == bitmap)
197 goto do_counts;
198
199 if (!actual && bitmap) {
200 /*
201 * Block not used, but marked in use in the bitmap.
202 */
203 problem = PR_5_BLOCK_UNUSED;
204 } else {
205 /*
206 * Block used, but not marked in use in the bitmap.
207 */
208 problem = PR_5_BLOCK_USED;
209 }
210 if (pctx.blk == NO_BLK) {
211 pctx.blk = pctx.blk2 = i;
212 save_problem = problem;
213 } else {
214 if ((problem == save_problem) &&
215 (pctx.blk2 == i-1))
216 pctx.blk2++;
217 else {
218 print_bitmap_problem(ctx, save_problem, &pctx);
219 pctx.blk = pctx.blk2 = i;
220 save_problem = problem;
221 }
222 }
223 ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
224 had_problem++;
225
226 do_counts:
227 if (!bitmap && !skip_group) {
228 group_free++;
229 free_blocks++;
230 }
231 blocks ++;
232 if ((blocks == fs->super->s_blocks_per_group) ||
233 (i == fs->super->s_blocks_count-1)) {
234 free_array[group] = group_free;
235 group ++;
236 blocks = 0;
237 group_free = 0;
238 skip_group = 0;
239 super += fs->super->s_blocks_per_group;
240 if (ctx->progress)
241 if ((ctx->progress)(ctx, 5, group,
242 fs->group_desc_count*2))
243 goto errout;
244 if (lazy_bg &&
245 (i != fs->super->s_blocks_count-1) &&
246 (fs->group_desc[group].bg_flags &
247 EXT2_BG_BLOCK_UNINIT))
248 skip_group++;
249 }
250 }
251 if (pctx.blk != NO_BLK)
252 print_bitmap_problem(ctx, save_problem, &pctx);
253 if (had_problem)
254 fixit = end_problem_latch(ctx, PR_LATCH_BBITMAP);
255 else
256 fixit = -1;
257 ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
258
259 if (fixit == 1) {
260 ext2fs_free_block_bitmap(fs->block_map);
261 retval = ext2fs_copy_bitmap(ctx->block_found_map,
262 &fs->block_map);
263 if (retval) {
264 clear_problem_context(&pctx);
265 fix_problem(ctx, PR_5_COPY_BBITMAP_ERROR, &pctx);
266 ctx->flags |= E2F_FLAG_ABORT;
267 goto errout;
268 }
269 ext2fs_set_bitmap_padding(fs->block_map);
270 ext2fs_mark_bb_dirty(fs);
271
272 /* Redo the counts */
273 blocks = 0; free_blocks = 0; group_free = 0; group = 0;
274 memset(free_array, 0, fs->group_desc_count * sizeof(int));
275 goto redo_counts;
276 } else if (fixit == 0)
277 ext2fs_unmark_valid(fs);
278
279 for (i = 0; i < fs->group_desc_count; i++) {
280 if (free_array[i] != fs->group_desc[i].bg_free_blocks_count) {
281 pctx.group = i;
282 pctx.blk = fs->group_desc[i].bg_free_blocks_count;
283 pctx.blk2 = free_array[i];
284
285 if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT_GROUP,
286 &pctx)) {
287 fs->group_desc[i].bg_free_blocks_count =
288 free_array[i];
289 ext2fs_mark_super_dirty(fs);
290 } else
291 ext2fs_unmark_valid(fs);
292 }
293 }
294 if (free_blocks != fs->super->s_free_blocks_count) {
295 pctx.group = 0;
296 pctx.blk = fs->super->s_free_blocks_count;
297 pctx.blk2 = free_blocks;
298
299 if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT, &pctx)) {
300 fs->super->s_free_blocks_count = free_blocks;
301 ext2fs_mark_super_dirty(fs);
302 } else
303 ext2fs_unmark_valid(fs);
304 }
305 errout:
306 ext2fs_free_mem(&free_array);
307 }
308
check_inode_bitmaps(e2fsck_t ctx)309 static void check_inode_bitmaps(e2fsck_t ctx)
310 {
311 ext2_filsys fs = ctx->fs;
312 ext2_ino_t i;
313 unsigned int free_inodes = 0;
314 int group_free = 0;
315 int dirs_count = 0;
316 int group = 0;
317 unsigned int inodes = 0;
318 int *free_array;
319 int *dir_array;
320 int actual, bitmap;
321 errcode_t retval;
322 struct problem_context pctx;
323 int problem, save_problem, fixit, had_problem;
324 int lazy_bg = 0;
325 int skip_group = 0;
326
327 clear_problem_context(&pctx);
328 free_array = (int *) e2fsck_allocate_memory(ctx,
329 fs->group_desc_count * sizeof(int), "free inode count array");
330
331 dir_array = (int *) e2fsck_allocate_memory(ctx,
332 fs->group_desc_count * sizeof(int), "directory count array");
333
334 if ((1 < ext2fs_get_inode_bitmap_start(ctx->inode_used_map)) ||
335 (fs->super->s_inodes_count >
336 ext2fs_get_inode_bitmap_end(ctx->inode_used_map))) {
337 pctx.num = 3;
338 pctx.blk = 1;
339 pctx.blk2 = fs->super->s_inodes_count;
340 pctx.ino = ext2fs_get_inode_bitmap_start(ctx->inode_used_map);
341 pctx.ino2 = ext2fs_get_inode_bitmap_end(ctx->inode_used_map);
342 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
343
344 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
345 goto errout;
346 }
347 if ((1 < ext2fs_get_inode_bitmap_start(fs->inode_map)) ||
348 (fs->super->s_inodes_count >
349 ext2fs_get_inode_bitmap_end(fs->inode_map))) {
350 pctx.num = 4;
351 pctx.blk = 1;
352 pctx.blk2 = fs->super->s_inodes_count;
353 pctx.ino = ext2fs_get_inode_bitmap_start(fs->inode_map);
354 pctx.ino2 = ext2fs_get_inode_bitmap_end(fs->inode_map);
355 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
356
357 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
358 goto errout;
359 }
360
361 if (EXT2_HAS_COMPAT_FEATURE(fs->super,
362 EXT2_FEATURE_COMPAT_LAZY_BG))
363 lazy_bg++;
364
365 redo_counts:
366 had_problem = 0;
367 save_problem = 0;
368 pctx.ino = pctx.ino2 = 0;
369 if (lazy_bg && (fs->group_desc[group].bg_flags &
370 EXT2_BG_INODE_UNINIT))
371 skip_group++;
372
373 /* Protect loop from wrap-around if inodes_count is maxed */
374 for (i = 1; i <= fs->super->s_inodes_count && i > 0; i++) {
375 actual = ext2fs_fast_test_inode_bitmap(ctx->inode_used_map, i);
376 if (skip_group)
377 bitmap = 0;
378 else
379 bitmap = ext2fs_fast_test_inode_bitmap(fs->inode_map, i);
380 if (actual == bitmap)
381 goto do_counts;
382
383 if (!actual && bitmap) {
384 /*
385 * Inode wasn't used, but marked in bitmap
386 */
387 problem = PR_5_INODE_UNUSED;
388 } else /* if (actual && !bitmap) */ {
389 /*
390 * Inode used, but not in bitmap
391 */
392 problem = PR_5_INODE_USED;
393 }
394 if (pctx.ino == 0) {
395 pctx.ino = pctx.ino2 = i;
396 save_problem = problem;
397 } else {
398 if ((problem == save_problem) &&
399 (pctx.ino2 == i-1))
400 pctx.ino2++;
401 else {
402 print_bitmap_problem(ctx, save_problem, &pctx);
403 pctx.ino = pctx.ino2 = i;
404 save_problem = problem;
405 }
406 }
407 ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
408 had_problem++;
409
410 do_counts:
411 if (bitmap) {
412 if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, i))
413 dirs_count++;
414 } else if (!skip_group) {
415 group_free++;
416 free_inodes++;
417 }
418 inodes++;
419 if ((inodes == fs->super->s_inodes_per_group) ||
420 (i == fs->super->s_inodes_count)) {
421 free_array[group] = group_free;
422 dir_array[group] = dirs_count;
423 group ++;
424 inodes = 0;
425 skip_group = 0;
426 group_free = 0;
427 dirs_count = 0;
428 if (ctx->progress)
429 if ((ctx->progress)(ctx, 5,
430 group + fs->group_desc_count,
431 fs->group_desc_count*2))
432 goto errout;
433 if (lazy_bg &&
434 (i != fs->super->s_inodes_count) &&
435 (fs->group_desc[group].bg_flags &
436 EXT2_BG_INODE_UNINIT))
437 skip_group++;
438 }
439 }
440 if (pctx.ino)
441 print_bitmap_problem(ctx, save_problem, &pctx);
442
443 if (had_problem)
444 fixit = end_problem_latch(ctx, PR_LATCH_IBITMAP);
445 else
446 fixit = -1;
447 ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
448
449 if (fixit == 1) {
450 ext2fs_free_inode_bitmap(fs->inode_map);
451 retval = ext2fs_copy_bitmap(ctx->inode_used_map,
452 &fs->inode_map);
453 if (retval) {
454 clear_problem_context(&pctx);
455 fix_problem(ctx, PR_5_COPY_IBITMAP_ERROR, &pctx);
456 ctx->flags |= E2F_FLAG_ABORT;
457 goto errout;
458 }
459 ext2fs_set_bitmap_padding(fs->inode_map);
460 ext2fs_mark_ib_dirty(fs);
461
462 /* redo counts */
463 inodes = 0; free_inodes = 0; group_free = 0;
464 dirs_count = 0; group = 0;
465 memset(free_array, 0, fs->group_desc_count * sizeof(int));
466 memset(dir_array, 0, fs->group_desc_count * sizeof(int));
467 goto redo_counts;
468 } else if (fixit == 0)
469 ext2fs_unmark_valid(fs);
470
471 for (i = 0; i < fs->group_desc_count; i++) {
472 if (free_array[i] != fs->group_desc[i].bg_free_inodes_count) {
473 pctx.group = i;
474 pctx.ino = fs->group_desc[i].bg_free_inodes_count;
475 pctx.ino2 = free_array[i];
476 if (fix_problem(ctx, PR_5_FREE_INODE_COUNT_GROUP,
477 &pctx)) {
478 fs->group_desc[i].bg_free_inodes_count =
479 free_array[i];
480 ext2fs_mark_super_dirty(fs);
481 } else
482 ext2fs_unmark_valid(fs);
483 }
484 if (dir_array[i] != fs->group_desc[i].bg_used_dirs_count) {
485 pctx.group = i;
486 pctx.ino = fs->group_desc[i].bg_used_dirs_count;
487 pctx.ino2 = dir_array[i];
488
489 if (fix_problem(ctx, PR_5_FREE_DIR_COUNT_GROUP,
490 &pctx)) {
491 fs->group_desc[i].bg_used_dirs_count =
492 dir_array[i];
493 ext2fs_mark_super_dirty(fs);
494 } else
495 ext2fs_unmark_valid(fs);
496 }
497 }
498 if (free_inodes != fs->super->s_free_inodes_count) {
499 pctx.group = -1;
500 pctx.ino = fs->super->s_free_inodes_count;
501 pctx.ino2 = free_inodes;
502
503 if (fix_problem(ctx, PR_5_FREE_INODE_COUNT, &pctx)) {
504 fs->super->s_free_inodes_count = free_inodes;
505 ext2fs_mark_super_dirty(fs);
506 } else
507 ext2fs_unmark_valid(fs);
508 }
509 errout:
510 ext2fs_free_mem(&free_array);
511 ext2fs_free_mem(&dir_array);
512 }
513
check_inode_end(e2fsck_t ctx)514 static void check_inode_end(e2fsck_t ctx)
515 {
516 ext2_filsys fs = ctx->fs;
517 ext2_ino_t end, save_inodes_count, i;
518 struct problem_context pctx;
519
520 clear_problem_context(&pctx);
521
522 end = EXT2_INODES_PER_GROUP(fs->super) * fs->group_desc_count;
523 pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map, end,
524 &save_inodes_count);
525 if (pctx.errcode) {
526 pctx.num = 1;
527 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
528 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
529 return;
530 }
531 if (save_inodes_count == end)
532 return;
533
534 /* protect loop from wrap-around if end is maxed */
535 for (i = save_inodes_count + 1; i <= end && i > save_inodes_count; i++) {
536 if (!ext2fs_test_inode_bitmap(fs->inode_map, i)) {
537 if (fix_problem(ctx, PR_5_INODE_BMAP_PADDING, &pctx)) {
538 for (i = save_inodes_count + 1; i <= end; i++)
539 ext2fs_mark_inode_bitmap(fs->inode_map,
540 i);
541 ext2fs_mark_ib_dirty(fs);
542 } else
543 ext2fs_unmark_valid(fs);
544 break;
545 }
546 }
547
548 pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map,
549 save_inodes_count, 0);
550 if (pctx.errcode) {
551 pctx.num = 2;
552 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
553 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
554 return;
555 }
556 }
557
check_block_end(e2fsck_t ctx)558 static void check_block_end(e2fsck_t ctx)
559 {
560 ext2_filsys fs = ctx->fs;
561 blk_t end, save_blocks_count, i;
562 struct problem_context pctx;
563
564 clear_problem_context(&pctx);
565
566 end = fs->block_map->start +
567 (EXT2_BLOCKS_PER_GROUP(fs->super) * fs->group_desc_count) - 1;
568 pctx.errcode = ext2fs_fudge_block_bitmap_end(fs->block_map, end,
569 &save_blocks_count);
570 if (pctx.errcode) {
571 pctx.num = 3;
572 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
573 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
574 return;
575 }
576 if (save_blocks_count == end)
577 return;
578
579 /* Protect loop from wrap-around if end is maxed */
580 for (i = save_blocks_count + 1; i <= end && i > save_blocks_count; i++) {
581 if (!ext2fs_test_block_bitmap(fs->block_map, i)) {
582 if (fix_problem(ctx, PR_5_BLOCK_BMAP_PADDING, &pctx)) {
583 for (i = save_blocks_count + 1; i <= end; i++)
584 ext2fs_mark_block_bitmap(fs->block_map,
585 i);
586 ext2fs_mark_bb_dirty(fs);
587 } else
588 ext2fs_unmark_valid(fs);
589 break;
590 }
591 }
592
593 pctx.errcode = ext2fs_fudge_block_bitmap_end(fs->block_map,
594 save_blocks_count, 0);
595 if (pctx.errcode) {
596 pctx.num = 4;
597 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
598 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
599 return;
600 }
601 }
602
603
604
605