OSDN Git Service

Code drop from //branches/cupcake/...@124589
[android-x86/external-e2fsprogs.git] / e2fsck / pass5.c
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
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
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
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
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
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
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