e2fsck/pass1.c

   1 /*
   2  * pass1.c -- pass #1 of e2fsck: sequential scan of the inode table
   3  *
   4  * Copyright (C) 1993, 1994 Theodore Ts'o.  This file may be
   5  * redistributed under the terms of the GNU Public License.
   6  *
   7  * Pass 1 of e2fsck iterates over all the inodes in the filesystems,
   8  * and applies the following tests to each inode:
   9  *
  10  *      - The mode field of the inode must be legal.
  11  *      - The size and block count fields of the inode are correct.
  12  *      - A data block must not be used by another inode
  13  *
  14  * Pass 1 also gathers the collects the following information:
  15  *
  16  *      - A bitmap of which inodes are in use.          (inode_used_map)
  17  *      - A bitmap of which inodes are directories.     (inode_dir_map)
  18  *      - A bitmap of which inodes have bad fields.     (inode_bad_map)
  19  *      - A bitmap of which blocks are in use.          (block_found_map)
  20  *      - A bitmap of which blocks are in use by two inodes     (block_dup_map)
  21  *      - The data blocks of the directory inodes.      (dir_map)
  22  *
  23  * Pass 1 is designed to stash away enough information so that the
  24  * other passes should not need to read in the inode information
  25  * during the normal course of a filesystem check.  (Althogh if an
  26  * inconsistency is detected, other passes may need to read in an
  27  * inode to fix it.)
  28  *
  29  * Note that pass 1B will be invoked if there are any duplicate blocks
  30  * found.
  31  */
  32
  33 #include <time.h>
  34 #ifdef HAVE_ERRNO_H
  35 #include <errno.h>
  36 #endif
  37
  38 #include <et/com_err.h>
  39 #include "e2fsck.h"
  40
  41 #ifdef NO_INLINE_FUNCS
  42 #define _INLINE_
  43 #else
  44 #define _INLINE_ inline
  45 #endif
  46
  47 /* Files counts */
  48 int fs_directory_count = 0;
  49 int fs_regular_count = 0;
  50 int fs_blockdev_count = 0;
  51 int fs_chardev_count = 0;
  52 int fs_links_count = 0;
  53 int fs_symlinks_count = 0;
  54 int fs_fast_symlinks_count = 0;
  55 int fs_fifo_count = 0;
  56 int fs_total_count = 0;
  57 int fs_badblocks_count = 0;
  58 int fs_sockets_count = 0;
  59 int fs_ind_count = 0;
  60 int fs_dind_count = 0;
  61 int fs_tind_count = 0;
  62 int fs_fragmented = 0;
  63
  64 ext2fs_inode_bitmap inode_used_map = 0; /* Inodes which are in use */
  65 ext2fs_inode_bitmap inode_bad_map = 0;  /* Inodes which are bad in some way */
  66 ext2fs_inode_bitmap inode_dir_map = 0;  /* Inodes which are directories */
  67
  68 ext2fs_block_bitmap block_found_map = 0;
  69 ext2fs_block_bitmap block_dup_map = 0;
  70 ext2fs_block_bitmap block_illegal_map = 0;
  71
  72 static int fix_link_count = -1;
  73
  74 unsigned short * inode_link_info = NULL;
  75
  76 static int process_block(ext2_filsys fs, blk_t  *blocknr,
  77                          int    blockcnt, void  *private);
  78 static int process_bad_block(ext2_filsys fs, blk_t *block_nr,
  79                              int blockcnt, void *private);
  80 static void check_blocks(ext2_filsys fs, ino_t ino, struct ext2_inode *inode,
  81                          char *block_buf);
  82 static void mark_table_blocks(ext2_filsys fs);
  83 static errcode_t pass1_check_directory(ext2_filsys fs, ino_t ino);
  84 static errcode_t pass1_get_blocks(ext2_filsys fs, ino_t ino, blk_t *blocks);
  85 static void alloc_bad_map(ext2_filsys fs);
  86 static void handle_fs_bad_blocks(ext2_filsys fs);
  87 static void process_inodes(ext2_filsys fs, char *block_buf);
  88 static int process_inode_cmp(const void *a, const void *b);
  89 static int dir_block_cmp(const void *a, const void *b);
  90 static errcode_t scan_callback(ext2_filsys fs, ext2_inode_scan scan,
  91                                   dgrp_t group, void * private);
  92 static char *describe_illegal_block(ext2_filsys fs, blk_t block);
  93
  94 struct process_block_struct {
  95         ino_t   ino;
  96         int     is_dir:1, clear:1, suppress:1, fragmented:1;
  97         int     num_blocks;
  98         int     last_block;
  99         int     num_illegal_blocks;
 100         int     fix;
 101         blk_t   previous_block;
 102         struct ext2_inode *inode;
 103 };
 104
 105 struct process_inode_block {
 106         ino_t   ino;
 107         struct ext2_inode inode;
 108 };
 109
 110 /*
 111  * For pass1_check_directory and pass1_get_blocks
 112  */
 113 ino_t stashed_ino;
 114 struct ext2_inode *stashed_inode;
 115
 116 /*
 117  * For the inodes to process list.
 118  */
 119 static struct process_inode_block *inodes_to_process;
 120 static int process_inode_count;
 121 int process_inode_size = 256;
 122
 123 /*
 124  * For the directory blocks list.
 125  */
 126 struct dir_block_struct *dir_blocks = 0;
 127 int     dir_block_count = 0;
 128 int     dir_block_size = 0;
 129
 130 /*
 131  * Free all memory allocated by pass1 in preparation for restarting
 132  * things.
 133  */
 134 static void unwind_pass1(ext2_filsys fs)
 135 {
 136         ext2fs_free_inode_bitmap(inode_used_map);       inode_used_map = 0;
 137         ext2fs_free_inode_bitmap(inode_dir_map);        inode_dir_map = 0;
 138         ext2fs_free_block_bitmap(block_found_map);      block_found_map = 0;
 139         free(inode_link_info);  inode_link_info = 0;
 140         free(inodes_to_process);inodes_to_process = 0;
 141         free(dir_blocks);       dir_blocks = 0;
 142         dir_block_size = 0;
 143         if (block_dup_map) {
 144                 ext2fs_free_block_bitmap(block_dup_map); block_dup_map = 0;
 145         }
 146
 147         /* Clear statistic counters */
 148         fs_directory_count = 0;
 149         fs_regular_count = 0;
 150         fs_blockdev_count = 0;
 151         fs_chardev_count = 0;
 152         fs_links_count = 0;
 153         fs_symlinks_count = 0;
 154         fs_fast_symlinks_count = 0;
 155         fs_fifo_count = 0;
 156         fs_total_count = 0;
 157         fs_badblocks_count = 0;
 158         fs_sockets_count = 0;
 159         fs_ind_count = 0;
 160         fs_dind_count = 0;
 161         fs_tind_count = 0;
 162         fs_fragmented = 0;
 163 }
 164
 165 void pass1(ext2_filsys fs)
 166 {
 167         ino_t   ino;
 168         struct ext2_inode inode;
 169         ext2_inode_scan scan;
 170         char            *block_buf;
 171         errcode_t       retval;
 172         struct resource_track   rtrack;
 173
 174         init_resource_track(&rtrack);
 175
 176         if (!preen)
 177                 printf("Pass 1: Checking inodes, blocks, and sizes\n");
 178
 179 #ifdef MTRACE
 180         mtrace_print("Pass 1");
 181 #endif
 182
 183         /*
 184          * Allocate bitmaps structures
 185          */
 186         retval = ext2fs_allocate_inode_bitmap(fs, "in-use inode map",
 187                                               &inode_used_map);
 188         if (retval) {
 189                 com_err("ext2fs_allocate_inode_bitmap", retval,
 190                         "while allocating inode_used_map");
 191                 fatal_error(0);
 192         }
 193         retval = ext2fs_allocate_inode_bitmap(fs, "directory inode map",
 194                                               &inode_dir_map);
 195         if (retval) {
 196                 com_err("ext2fs_allocate_inode_bitmap", retval,
 197                         "while allocating inode_dir_map");
 198                 fatal_error(0);
 199         }
 200         retval = ext2fs_allocate_block_bitmap(fs, "in-use block map",
 201                                               &block_found_map);
 202         if (retval) {
 203                 com_err("ext2fs_allocate_block_bitmap", retval,
 204                         "while allocating block_found_map");
 205                 fatal_error(0);
 206         }
 207         retval = ext2fs_allocate_block_bitmap(fs, "illegal block map",
 208                                               &block_illegal_map);
 209         if (retval) {
 210                 com_err("ext2fs_allocate_block_bitmap", retval,
 211                         "while allocating block_illegal_map");
 212                 fatal_error(0);
 213         }
 214         inode_link_info = allocate_memory((fs->super->s_inodes_count + 1) *
 215                                           sizeof(unsigned short),
 216                                           "inode link count array");
 217         inodes_to_process = allocate_memory(process_inode_size *
 218                                             sizeof(struct process_inode_block),
 219                                             "array of inodes to process");
 220         process_inode_count = 0;
 221
 222         dir_block_size = get_num_dirs(fs) * 4;
 223         dir_block_count = 0;
 224         dir_blocks = allocate_memory(sizeof(struct dir_block_struct) *
 225                                      dir_block_size,
 226                                      "directory block information");
 227
 228         mark_table_blocks(fs);
 229         block_buf = allocate_memory(fs->blocksize * 3, "block interate buffer");
 230         fs->get_blocks = pass1_get_blocks;
 231         fs->check_directory = pass1_check_directory;
 232         ehandler_operation("doing inode scan");
 233         retval = ext2fs_open_inode_scan(fs, inode_buffer_blocks, &scan);
 234         if (retval) {
 235                 com_err(program_name, retval, "while opening inode scan");
 236                 fatal_error(0);
 237         }
 238         retval = ext2fs_get_next_inode(scan, &ino, &inode);
 239         if (retval) {
 240                 com_err(program_name, retval, "while starting inode scan");
 241                 fatal_error(0);
 242         }
 243         stashed_inode = &inode;
 244         ext2fs_set_inode_callback(scan, scan_callback, block_buf);
 245         while (ino) {
 246                 stashed_ino = ino;
 247                 inode_link_info[ino] = inode.i_links_count;
 248                 if (ino == EXT2_BAD_INO) {
 249                         struct process_block_struct pb;
 250
 251                         pb.ino = EXT2_BAD_INO;
 252                         pb.num_blocks = pb.last_block = 0;
 253                         pb.num_illegal_blocks = 0;
 254                         pb.suppress = pb.clear = pb.is_dir = 0;
 255                         pb.fragmented = 0;
 256                         pb.fix = -1;
 257                         pb.inode = &inode;
 258                         retval = ext2fs_block_iterate(fs, ino, 0, block_buf,
 259                                                       process_bad_block, &pb);
 260                         if (retval)
 261                                 com_err(program_name, retval, "while calling e2fsc_block_interate in pass 1");
 262
 263                         ext2fs_mark_inode_bitmap(inode_used_map, ino);
 264                         goto next;
 265                 }
 266                 if (ino == EXT2_ROOT_INO) {
 267                         /*
 268                          * Make sure the root inode is a directory; if
 269                          * not, offer to clear it.  It will be
 270                          * regnerated in pass #3.
 271                          */
 272                         if (!LINUX_S_ISDIR(inode.i_mode)) {
 273                                 printf("Root inode is not a directory.  ");
 274                                 preenhalt(fs);
 275                                 if (ask("Clear", 1)) {
 276                                         inode.i_dtime = time(0);
 277                                         inode.i_links_count = 0;
 278                                         inode_link_info[ino] = 0;
 279                                         e2fsck_write_inode(fs, ino, &inode,
 280                                                            "pass1");
 281                                 } else
 282                                         ext2fs_unmark_valid(fs);
 283                         }
 284                         /*
 285                          * If dtime is set, offer to clear it.  mke2fs
 286                          * version 0.2b created filesystems with the
 287                          * dtime field set for the root and lost+found
 288                          * directories.  We won't worry about
 289                          * /lost+found, since that can be regenerated
 290                          * easily.  But we will fix the root directory
 291                          * as a special case.
 292                          */
 293                         if (inode.i_dtime && inode.i_links_count) {
 294                                 if (ask("Root inode has dtime set "
 295                                         "(probably due to old mke2fs).  Fix",
 296                                         1)) {
 297                                         inode.i_dtime = 0;
 298                                         e2fsck_write_inode(fs, ino, &inode,
 299                                                            "pass1");
 300                                         printf("Note: /lost+found will "
 301                                                "probably be deleted as well, "
 302                                                "due to the mke2fs bug.\n"
 303                                                "Be sure to run mklost+found "
 304                                                "to recreate it after e2fsck "
 305                                                "finishes.\n\n");
 306                                 } else
 307                                         ext2fs_unmark_valid(fs);
 308                         }
 309                 }
 310                 if ((ino != EXT2_ROOT_INO) &&
 311                     (ino < EXT2_FIRST_INODE(fs->super))) {
 312                         ext2fs_mark_inode_bitmap(inode_used_map, ino);
 313                         if (inode.i_mode != 0) {
 314                                 printf("Reserved inode %lu has bad mode.  ", ino);
 315                                 if (ask("Clear", 1)) {
 316                                         inode.i_mode = 0;
 317                                         e2fsck_write_inode(fs, ino, &inode,
 318                                                            "pass1");
 319                                 } else
 320                                         ext2fs_unmark_valid(fs);
 321                         }
 322                         check_blocks(fs, ino, &inode, block_buf);
 323                         goto next;
 324                 }
 325                 /*
 326                  * This code assumes that deleted inodes have
 327                  * i_links_count set to 0.
 328                  */
 329                 if (!inode.i_links_count) {
 330                         if (!inode.i_dtime && inode.i_mode) {
 331                                 printf("Deleted inode %lu has zero dtime.\n",
 332                                        ino);
 333                                 if (ask("Set dtime", 1)) {
 334                                         inode.i_dtime = time(0);
 335                                         e2fsck_write_inode(fs, ino, &inode,
 336                                                            "pass1");
 337                                 } else
 338                                         ext2fs_unmark_valid(fs);
 339                         }
 340                         goto next;
 341                 }
 342                 /*
 343                  * 0.3c ext2fs code didn't clear i_links_count for
 344                  * deleted files.  Oops.
 345                  *
 346                  * In the future, when the new ext2fs behavior is the
 347                  * norm, we may want to handle the case of a non-zero
 348                  * i_links_count and non-zero dtime by clearing dtime
 349                  * and assuming the inode is in use, instead of
 350                  * assuming the inode is not in use.
 351                  */
 352                 if (inode.i_dtime) {
 353                         if (fix_link_count == -1) {
 354                                 printf("\nDeleted inode detected with non-zero link count.\n");
 355                                 printf("This is probably due to old ext2fs kernel code.  \n");
 356                                 fix_link_count = ask("Fix inode(s)", 1);
 357                         }
 358                         printf("Inode %lu is deleted w/ non-zero link_count.  %s\n",
 359                                ino, clear_msg[fix_link_count]);
 360                         if (fix_link_count) {
 361                                 inode.i_links_count = 0;
 362                                 inode_link_info[ino] = 0;
 363                                 e2fsck_write_inode(fs, ino, &inode, "pass1");
 364                         } else
 365                                 ext2fs_unmark_valid(fs);
 366                         goto next;
 367                 }
 368
 369                 ext2fs_mark_inode_bitmap(inode_used_map, ino);
 370                 if (inode.i_faddr
 371 #if HAVE_EXT2_FRAGS
 372                     || inode.i_frag || inode.i_fsize
 373 #endif
 374                     || inode.i_file_acl || inode.i_dir_acl) {
 375                         if (!inode_bad_map)
 376                                 alloc_bad_map(fs);
 377                         ext2fs_mark_inode_bitmap(inode_bad_map, ino);
 378                 }
 379
 380                 if (LINUX_S_ISDIR(inode.i_mode)) {
 381                         ext2fs_mark_inode_bitmap(inode_dir_map, ino);
 382                         add_dir_info(fs, ino, 0, &inode);
 383                         fs_directory_count++;
 384                 } else if (LINUX_S_ISREG (inode.i_mode))
 385                         fs_regular_count++;
 386                 else if (LINUX_S_ISCHR (inode.i_mode))
 387                         fs_chardev_count++;
 388                 else if (LINUX_S_ISBLK (inode.i_mode))
 389                         fs_blockdev_count++;
 390                 else if (LINUX_S_ISLNK (inode.i_mode)) {
 391                         fs_symlinks_count++;
 392                         if (!inode.i_blocks)
 393                                 fs_fast_symlinks_count++;
 394                 }
 395                 else if (LINUX_S_ISFIFO (inode.i_mode))
 396                         fs_fifo_count++;
 397                 else if (LINUX_S_ISSOCK (inode.i_mode))
 398                         fs_sockets_count++;
 399                 else {
 400                         if (!inode_bad_map)
 401                                 alloc_bad_map(fs);
 402                         ext2fs_mark_inode_bitmap(inode_bad_map, ino);
 403                 }
 404                 if (inode.i_block[EXT2_IND_BLOCK])
 405                         fs_ind_count++;
 406                 if (inode.i_block[EXT2_DIND_BLOCK])
 407                         fs_dind_count++;
 408                 if (inode.i_block[EXT2_TIND_BLOCK])
 409                         fs_tind_count++;
 410                 if (inode.i_block[EXT2_IND_BLOCK] ||
 411                     inode.i_block[EXT2_DIND_BLOCK] ||
 412                     inode.i_block[EXT2_TIND_BLOCK]) {
 413                         inodes_to_process[process_inode_count].ino = ino;
 414                         inodes_to_process[process_inode_count].inode = inode;
 415                         process_inode_count++;
 416                 } else
 417                         check_blocks(fs, ino, &inode, block_buf);
 418
 419                 if (process_inode_count >= process_inode_size)
 420                         process_inodes(fs, block_buf);
 421         next:
 422                 retval = ext2fs_get_next_inode(scan, &ino, &inode);
 423                 if (retval) {
 424                         com_err(program_name, retval,
 425                                 "while doing inode scan");
 426                         fatal_error(0);
 427                 }
 428         }
 429         process_inodes(fs, block_buf);
 430         ext2fs_close_inode_scan(scan);
 431         ehandler_operation(0);
 432
 433         qsort(dir_blocks, dir_block_count, sizeof(struct dir_block_struct),
 434               dir_block_cmp);
 435
 436         if (invalid_bitmaps)
 437                 handle_fs_bad_blocks(fs);
 438
 439         if (restart_e2fsck) {
 440                 unwind_pass1(fs);
 441                 goto endit;
 442         }
 443
 444         if (block_dup_map) {
 445                 if (preen) {
 446                         printf("Duplicate or bad blocks in use!\n");
 447                         preenhalt(fs);
 448                 }
 449                 pass1_dupblocks(fs, block_buf);
 450         }
 451         fs->get_blocks = 0;
 452         fs->check_directory = 0;
 453         free(inodes_to_process);
 454 endit:
 455         free(block_buf);
 456         ext2fs_free_block_bitmap(block_illegal_map);
 457         block_illegal_map = 0;
 458
 459         if (tflag > 1) {
 460                 printf("Pass 1: ");
 461                 print_resource_track(&rtrack);
 462         }
 463 }
 464
 465 /*
 466  * When the inode_scan routines call this callback at the end of the
 467  * glock group, call process_inodes.
 468  */
 469 static errcode_t scan_callback(ext2_filsys fs, ext2_inode_scan scan,
 470                                dgrp_t group, void * private)
 471 {
 472         process_inodes(fs, (char *) private);
 473         return 0;
 474 }
 475
 476 /*
 477  * Process the inodes in the "inodes to process" list.
 478  */
 479 static void process_inodes(ext2_filsys fs, char *block_buf)
 480 {
 481         int                     i;
 482         struct ext2_inode       *old_stashed_inode;
 483         ino_t                   ino;
 484         const char              *old_operation;
 485         char                    buf[80];
 486
 487 #if 0
 488         printf("begin process_inodes: ");
 489 #endif
 490         old_operation = ehandler_operation(0);
 491         old_stashed_inode = stashed_inode;
 492         qsort(inodes_to_process, process_inode_count,
 493                       sizeof(struct process_inode_block), process_inode_cmp);
 494         for (i=0; i < process_inode_count; i++) {
 495                 stashed_inode = &inodes_to_process[i].inode;
 496                 ino = inodes_to_process[i].ino;
 497                 stashed_ino = ino;
 498 #if 0
 499                 printf("%u ", ino);
 500 #endif
 501                 sprintf(buf, "reading indirect blocks of inode %lu", ino);
 502                 ehandler_operation(buf);
 503                 check_blocks(fs, ino, stashed_inode, block_buf);
 504
 505         }
 506         stashed_inode = old_stashed_inode;
 507         process_inode_count = 0;
 508 #if 0
 509         printf("end process inodes\n");
 510 #endif
 511         ehandler_operation(old_operation);
 512 }
 513
 514 static int process_inode_cmp(const void *a, const void *b)
 515 {
 516         const struct process_inode_block *ib_a =
 517                 (const struct process_inode_block *) a;
 518         const struct process_inode_block *ib_b =
 519                 (const struct process_inode_block *) b;
 520
 521         return (ib_a->inode.i_block[EXT2_IND_BLOCK] -
 522                 ib_b->inode.i_block[EXT2_IND_BLOCK]);
 523 }
 524
 525 static int dir_block_cmp(const void *a, const void *b)
 526 {
 527         const struct dir_block_struct *db_a =
 528                 (const struct dir_block_struct *) a;
 529         const struct dir_block_struct *db_b =
 530                 (const struct dir_block_struct *) b;
 531
 532         if (db_a->blk != db_b->blk)
 533                 return (db_a->blk - db_b->blk);
 534
 535         if (db_a->ino != db_b->ino)
 536                 return (db_a->ino - db_b->ino);
 537
 538         return (db_a->blockcnt - db_b->blockcnt);
 539 }
 540
 541 /*
 542  * This procedure will allocate the inode bad map table
 543  */
 544 static void alloc_bad_map(ext2_filsys fs)
 545 {
 546         errcode_t       retval;
 547
 548         retval = ext2fs_allocate_inode_bitmap(fs, "bad inode map",
 549                                               &inode_bad_map);
 550         if (retval) {
 551                 com_err("ext2fs_allocate_inode_bitmap", retval,
 552                         "while allocating inode_bad_map");
 553                 fatal_error(0);
 554         }
 555 }
 556
 557 /*
 558  * Marks a block as in use, setting the dup_map if it's been set
 559  * already.  Called by process_block and process_bad_block.
 560  *
 561  * WARNING: Assumes checks have already been done to make sure block
 562  * is valid.  This is true in both process_block and process_bad_block.
 563  */
 564 static _INLINE_ void mark_block_used(ext2_filsys fs, blk_t block)
 565 {
 566         errcode_t       retval;
 567
 568         if (ext2fs_fast_test_block_bitmap(block_found_map, block)) {
 569                 if (!block_dup_map) {
 570                         retval = ext2fs_allocate_block_bitmap(fs,
 571                               "multiply claimed block map", &block_dup_map);
 572                         if (retval) {
 573                                 com_err("ext2fs_allocate_block_bitmap", retval,
 574                                         "while allocating block_dup_map");
 575                                 fatal_error(0);
 576                         }
 577                 }
 578                 ext2fs_fast_mark_block_bitmap(block_dup_map, block);
 579         } else {
 580                 ext2fs_fast_mark_block_bitmap(block_found_map, block);
 581         }
 582 }
 583
 584 /*
 585  * This subroutine is called on each inode to account for all of the
 586  * blocks used by that inode.
 587  */
 588 static void check_blocks(ext2_filsys fs, ino_t ino, struct ext2_inode *inode,
 589                          char *block_buf)
 590 {
 591         struct process_block_struct pb;
 592         errcode_t       retval;
 593
 594         if (!inode_has_valid_blocks(inode))
 595                 return;
 596
 597         pb.ino = ino;
 598         pb.num_blocks = pb.last_block = 0;
 599         pb.num_illegal_blocks = 0;
 600         pb.suppress = pb.clear = 0;
 601         pb.fragmented = 0;
 602         pb.previous_block = 0;
 603         pb.is_dir = LINUX_S_ISDIR(inode->i_mode);
 604         pb.fix = -1;
 605         pb.inode = inode;
 606         retval = ext2fs_block_iterate(fs, ino,
 607                                       pb.is_dir ? BLOCK_FLAG_HOLE : 0,
 608                                       block_buf, process_block, &pb);
 609         if (retval)
 610                 com_err(program_name, retval,
 611                         "while calling ext2fs_block_iterate in check_blocks");
 612
 613         if (pb.fragmented && pb.num_blocks < fs->super->s_blocks_per_group)
 614                 fs_fragmented++;
 615
 616         if (pb.clear) {
 617                 e2fsck_read_inode(fs, ino, inode, "check_blocks");
 618                 if (retval) {
 619                         com_err("check_blocks", retval,
 620                                 "while reading to be cleared inode %d", ino);
 621                         fatal_error(0);
 622                 }
 623                 inode->i_links_count = 0;
 624                 inode_link_info[ino] = 0;
 625                 inode->i_dtime = time(0);
 626                 e2fsck_write_inode(fs, ino, inode, "check_blocks");
 627                 ext2fs_unmark_inode_bitmap(inode_dir_map, ino);
 628                 ext2fs_unmark_inode_bitmap(inode_used_map, ino);
 629                 /*
 630                  * The inode was probably partially accounted for
 631                  * before processing was aborted, so we need to
 632                  * restart the pass 1 scan.
 633                  */
 634                 restart_e2fsck++;
 635                 return;
 636         }
 637
 638         if (pb.fix > 0)
 639                 e2fsck_read_inode(fs, ino, inode, "check_blocks");
 640
 641         pb.num_blocks *= (fs->blocksize / 512);
 642 #if 0
 643         printf("inode %u, i_size = %lu, last_block = %lu, i_blocks=%lu, num_blocks = %lu\n",
 644                ino, inode->i_size, pb.last_block, inode->i_blocks,
 645                pb.num_blocks);
 646 #endif
 647         if (!pb.num_blocks && pb.is_dir) {
 648                 printf("Inode %lu is a zero length directory.  ", ino);
 649                 if (ask("Clear", 1)) {
 650                         inode->i_links_count = 0;
 651                         inode_link_info[ino] = 0;
 652                         inode->i_dtime = time(0);
 653                         e2fsck_write_inode(fs, ino, inode, "check_blocks");
 654                         ext2fs_unmark_inode_bitmap(inode_dir_map, ino);
 655                         ext2fs_unmark_inode_bitmap(inode_used_map, ino);
 656                         fs_directory_count--;
 657                         pb.is_dir = 0;
 658                 } else
 659                         ext2fs_unmark_valid(fs);
 660         }
 661         if ((pb.is_dir && (inode->i_size != (pb.last_block + 1) * fs->blocksize)) ||
 662             (inode->i_size < pb.last_block * fs->blocksize)) {
 663                 printf ("%s %lu, incorrect size, %u (counted = %u). ",
 664                         pb.is_dir ? "Directory" : "Inode", ino, inode->i_size,
 665                         (pb.last_block+1) * fs->blocksize);
 666                 if (ask ("Set size to counted", 1)) {
 667                         inode->i_size = (pb.last_block+1) * fs->blocksize;
 668                         e2fsck_write_inode(fs, ino, inode, "check_blocks");
 669                 } else
 670                         ext2fs_unmark_valid(fs);
 671         }
 672         if (pb.num_blocks != inode->i_blocks) {
 673                 printf ("Inode %lu, i_blocks wrong %u (counted=%u).  ",
 674                         ino, inode->i_blocks, pb.num_blocks);
 675                 if (ask ("Set i_blocks to counted", 1)) {
 676                         inode->i_blocks = pb.num_blocks;
 677                         e2fsck_write_inode(fs, ino, inode, "check_blocks");
 678                 } else
 679                                 ext2fs_unmark_valid(fs);
 680         }
 681 }
 682
 683 /*
 684  * Helper function called by process block when an illegal block is
 685  * found.  It returns a description about why the block is illegal
 686  */
 687 static char *describe_illegal_block(ext2_filsys fs, blk_t block)
 688 {
 689         blk_t   super;
 690         int     i;
 691         static char     problem[80];
 692
 693         super = fs->super->s_first_data_block;
 694         strcpy(problem, "PROGRAMMING ERROR: Unknown reason for illegal block");
 695         if (block < super) {
 696                 sprintf(problem, "< FIRSTBLOCK (%u)", super);
 697                 return(problem);
 698         } else if (block >= fs->super->s_blocks_count) {
 699                 sprintf(problem, "> BLOCKS (%u)", fs->super->s_blocks_count);
 700                 return(problem);
 701         }
 702         for (i = 0; i < fs->group_desc_count; i++) {
 703                 if (block == super) {
 704                         sprintf(problem, "is the superblock in group %d", i);
 705                         break;
 706                 }
 707                 if (block > super &&
 708                     block <= (super + fs->desc_blocks)) {
 709                         sprintf(problem, "is in the group descriptors "
 710                                 "of group %d", i);
 711                         break;
 712                 }
 713                 if (block == fs->group_desc[i].bg_block_bitmap) {
 714                         sprintf(problem, "is the block bitmap of group %d", i);
 715                         break;
 716                 }
 717                 if (block == fs->group_desc[i].bg_inode_bitmap) {
 718                         sprintf(problem, "is the inode bitmap of group %d", i);
 719                         break;
 720                 }
 721                 if (block >= fs->group_desc[i].bg_inode_table &&
 722                     (block < fs->group_desc[i].bg_inode_table
 723                      + fs->inode_blocks_per_group)) {
 724                         sprintf(problem, "is in the inode table of group %d",
 725                                 i);
 726                         break;
 727                 }
 728                 super += fs->super->s_blocks_per_group;
 729         }
 730         return(problem);
 731 }
 732
 733 /*
 734  * This is a helper function for check_blocks().
 735  */
 736 int process_block(ext2_filsys fs,
 737                   blk_t *block_nr,
 738                   int blockcnt,
 739                   void *private)
 740 {
 741         struct process_block_struct *p;
 742         char    *problem;
 743         blk_t   blk = *block_nr;
 744         int     ret_code = 0;
 745
 746         p = (struct process_block_struct *) private;
 747
 748         if (blk == 0) {
 749                 if (p->is_dir == 0) {
 750                         printf("process_block() called with blk == 0, "
 751                                "inode %lu???", p->ino);
 752                         return 0;
 753                 }
 754                 if (blockcnt < 0)
 755                         return 0;
 756                 if (blockcnt * fs->blocksize < p->inode->i_size) {
 757                         printf("Hole found in directory inode %lu!  "
 758                                "(blkcnt=%d)\n", p->ino, blockcnt);
 759                         goto mark_dir;
 760                 }
 761                 return 0;
 762         }
 763
 764 #if 0
 765         printf("Process_block, inode %lu, block %u, #%d\n", p->ino, blk,
 766                blockcnt);
 767 #endif
 768
 769         /*
 770          * Simplistic fragmentation check.  We merely require that the
 771          * file be contiguous.  (Which can never be true for really
 772          * big files that are greater than a block group.)
 773          */
 774         if (p->previous_block) {
 775                 if (p->previous_block+1 != blk)
 776                         p->fragmented = 1;
 777         }
 778         p->previous_block = blk;
 779
 780
 781         if (blk < fs->super->s_first_data_block ||
 782             blk >= fs->super->s_blocks_count ||
 783             ext2fs_test_block_bitmap(block_illegal_map, blk)) {
 784                 problem = describe_illegal_block(fs, blk);
 785                 if (preen) {
 786                         printf("Block %u of inode %lu %s\n", blk, p->ino,
 787                                problem);
 788                         preenhalt(fs);
 789                 }
 790                 if (p->fix == -1) {
 791                         printf("Remove illegal block(s) in inode %lu", p->ino);
 792                         p->fix = ask("", 1);
 793                 }
 794                 p->num_illegal_blocks++;
 795                 if (!p->suppress && (p->num_illegal_blocks % 20) == 0) {
 796                         printf("Too many illegal blocks in inode %lu.\n",
 797                                p->ino);
 798                         if (ask("Clear inode", 1)) {
 799                                 p->clear = 1;
 800                                 return BLOCK_ABORT;
 801                         }
 802                         if (ask("Supress messages", 0)) {
 803                                 p->suppress = 1;
 804                         }
 805                 }
 806                 if (!p->suppress)
 807                         printf("Block #%d (%u) %s.  %s\n", blockcnt, blk,
 808                                problem, clear_msg[p->fix]);
 809                 if (p->fix) {
 810                         blk = *block_nr = 0;
 811                         ret_code = BLOCK_CHANGED;
 812                         goto mark_dir;
 813                 } else {
 814                         ext2fs_unmark_valid(fs);
 815                         return 0;
 816                 }
 817         }
 818
 819         mark_block_used(fs, blk);
 820         p->num_blocks++;
 821         if (blockcnt < 0)
 822                 return 0;
 823
 824         p->last_block = blockcnt;
 825 mark_dir:
 826         if (p->is_dir) {
 827                 if (dir_block_count >= dir_block_size) {
 828                         dir_block_size += 100;
 829                         dir_blocks = realloc(dir_blocks,
 830                                              dir_block_size *
 831                                              sizeof(struct dir_block_struct));
 832                         if (dir_blocks == 0)
 833                                 fatal_error("Not enough memory to "
 834                                             "realloc dir_blocks");
 835                 }
 836
 837                 dir_blocks[dir_block_count].blk = blk;
 838                 dir_blocks[dir_block_count].ino = p->ino;
 839                 dir_blocks[dir_block_count].blockcnt = blockcnt;
 840                 dir_block_count++;
 841         }
 842         return ret_code;
 843 }
 844
 845 static void bad_block_indirect(ext2_filsys fs, blk_t blk)
 846 {
 847         printf("Bad block %u used as bad block indirect block?!?\n", blk);
 848         preenhalt(fs);
 849         printf("\nThis inconsistency can not be fixed with "
 850                "e2fsck; to fix it, use\n"
 851                """dumpe2fs -b"" to dump out the bad block "
 852                "list and ""e2fsck -L filename""\n"
 853                "to read it back in again.\n");
 854         if (ask("Continue", 0))
 855                 return;
 856         fatal_error(0);
 857 }
 858
 859 static int bad_primary_block(ext2_filsys fs, blk_t *block_nr)
 860 {
 861         printf("\nIf the block is really bad, the filesystem can not be "
 862                "fixed.\n");
 863         preenhalt(fs);
 864         printf("You can clear the this block from the bad block list\n");
 865         printf("and hope that block is really OK, but there are no "
 866                "guarantees.\n\n");
 867         if (ask("Clear (and hope for the best)", 1)) {
 868                 *block_nr = 0;
 869                 return 1;
 870         }
 871         ext2fs_unmark_valid(fs);
 872         return 0;
 873 }
 874
 875 int process_bad_block(ext2_filsys fs,
 876                       blk_t *block_nr,
 877                       int blockcnt,
 878                       void *private)
 879 {
 880         struct process_block_struct *p;
 881         blk_t           blk = *block_nr;
 882         int             first_block;
 883         int             i;
 884
 885         if (!blk)
 886                 return 0;
 887         p = (struct process_block_struct *) private;
 888
 889         if ((blk < fs->super->s_first_data_block) ||
 890             (blk >= fs->super->s_blocks_count)) {
 891                 if (preen) {
 892                         printf("Illegal block %u in bad block inode\n", blk);
 893                         preenhalt(fs);
 894                 }
 895                 if (p->fix == -1)
 896                         p->fix = ask("Remove illegal block(s) in bad block inode", 1);
 897                 printf("Illegal block %u in bad block inode.  %s\n", blk,
 898                        clear_msg[p->fix]);
 899                 if (p->fix) {
 900                         *block_nr = 0;
 901                         return BLOCK_CHANGED;
 902                 } else {
 903                         ext2fs_unmark_valid(fs);
 904                         return 0;
 905                 }
 906         }
 907
 908         if (blockcnt < 0) {
 909                 if (ext2fs_test_block_bitmap(block_found_map, blk))
 910                         bad_block_indirect(fs, blk);
 911                 else
 912                         mark_block_used(fs, blk);
 913                 return 0;
 914         }
 915 #if 0
 916         printf ("DEBUG: Marking %u as bad.\n", blk);
 917 #endif
 918         fs_badblocks_count++;
 919         /*
 920          * If the block is not used, then mark it as used and return.
 921          * If it is already marked as found, this must mean that
 922          * there's an overlap between the filesystem table blocks
 923          * (bitmaps and inode table) and the bad block list.
 924          */
 925         if (!ext2fs_test_block_bitmap(block_found_map, blk)) {
 926                 ext2fs_mark_block_bitmap(block_found_map, blk);
 927                 return 0;
 928         }
 929         /*
 930          * Try to find the where the filesystem block was used...
 931          */
 932         first_block = fs->super->s_first_data_block;
 933
 934         for (i = 0; i < fs->group_desc_count; i++ ) {
 935                 if (blk == first_block) {
 936                         if (i == 0) {
 937                                 printf("The primary superblock (%u) is "
 938                                        "on the bad block list.\n", blk);
 939                                 if (bad_primary_block(fs, block_nr))
 940                                         return BLOCK_CHANGED;
 941                                 return 0;
 942                         }
 943                         if (!preen)
 944                                 printf("Warning: Group %d's superblock "
 945                                        "(%u) is bad.\n", i, blk);
 946                         return 0;
 947                 }
 948                 if ((blk > first_block) &&
 949                     (blk <= first_block + fs->desc_blocks)) {
 950                         if (i == 0) {
 951                                 printf("Block %u in the primary group "
 952                                        "descriptors is on the bad block "
 953                                        "list\n", blk);
 954                                 if (bad_primary_block(fs, block_nr))
 955                                         return BLOCK_CHANGED;
 956                                 return 0;
 957                         }
 958                         if (!preen)
 959                                 printf("Warning: Group %d's copy of the "
 960                                        "group descriptors has a bad "
 961                                        "block (%u).\n", i, blk);
 962                         return 0;
 963                 }
 964                 if (blk == fs->group_desc[i].bg_block_bitmap) {
 965                         printf("Group %d's block bitmap (%u) is bad.  ",
 966                                i, blk);
 967                         if (ask("Relocate", 1)) {
 968                                 invalid_block_bitmap[i]++;
 969                                 invalid_bitmaps++;
 970                         } else
 971                                 ext2fs_unmark_valid(fs);
 972                         return 0;
 973                 }
 974                 if (blk == fs->group_desc[i].bg_inode_bitmap) {
 975                         printf("Group %d's inode bitmap (%u) is bad.  ",
 976                                i, blk);
 977                         if (ask("Relocate", 1)) {
 978                                 invalid_inode_bitmap[i]++;
 979                                 invalid_bitmaps++;
 980                         } else
 981                                 ext2fs_unmark_valid(fs);
 982                         return 0;
 983                 }
 984                 if ((blk >= fs->group_desc[i].bg_inode_table) &&
 985                     (blk < (fs->group_desc[i].bg_inode_table +
 986                             fs->inode_blocks_per_group))) {
 987                         printf("WARNING: Severe data loss possible!!!!\n");
 988                         printf("Bad block %u in group %d's inode table.  ",
 989                                blk, i);
 990                         if (ask("Relocate", 1)) {
 991                                 invalid_inode_table[i]++;
 992                                 invalid_bitmaps++;
 993                         } else
 994                                 ext2fs_unmark_valid(fs);
 995                         return 0;
 996                 }
 997                 first_block += fs->super->s_blocks_per_group;
 998         }
 999         /*
1000          * If we've gotten to this point, then the only
1001          * possibility is that the bad block inode meta data
1002          * is using a bad block.
1003          */
1004         if ((blk == p->inode->i_block[EXT2_IND_BLOCK]) ||
1005             p->inode->i_block[EXT2_DIND_BLOCK]) {
1006                 bad_block_indirect(fs, blk);
1007                 return 0;
1008         }
1009
1010         printf("Programming error?  block #%u claimed for no reason "
1011                "in process_bad_block.\n", blk);
1012         return 0;
1013 }
1014
1015 static void new_table_block(ext2_filsys fs, blk_t first_block, int group,
1016                             const char *name, int num, blk_t *new_block)
1017 {
1018         errcode_t       retval;
1019         blk_t           old_block = *new_block;
1020         int             i;
1021         char            *buf;
1022
1023         retval = ext2fs_get_free_blocks(fs, first_block,
1024                         first_block + fs->super->s_blocks_per_group,
1025                                         num, block_found_map, new_block);
1026         if (retval) {
1027                 printf("Could not allocate %d block(s) for %s: %s\n",
1028                        num, name, error_message(retval));
1029                 ext2fs_unmark_valid(fs);
1030                 return;
1031         }
1032         buf = malloc(fs->blocksize);
1033         if (!buf) {
1034                 printf("Could not allocate block buffer for relocating %s\n",
1035                        name);
1036                 ext2fs_unmark_valid(fs);
1037                 return;
1038         }
1039         ext2fs_mark_super_dirty(fs);
1040         printf("Relocating group %d's %s ", group, name);
1041         if (old_block)
1042                 printf("from %u ", old_block);
1043         printf("to %u...\n", *new_block);
1044         for (i = 0; i < num; i++) {
1045                 ext2fs_mark_block_bitmap(block_found_map, (*new_block)+i);
1046                 if (old_block) {
1047                         retval = io_channel_read_blk(fs->io, old_block + i,
1048                                                      1, buf);
1049                         if (retval)
1050                                 printf("Warning: could not read block %u "
1051                                        "of %s: %s\n",
1052                                        old_block + i, name,
1053                                        error_message(retval));
1054                 } else
1055                         memset(buf, 0, fs->blocksize);
1056
1057                 retval = io_channel_write_blk(fs->io, (*new_block) + i,
1058                                               1, buf);
1059                 if (retval)
1060                         printf("Warning: could not write block %u for %s: %s\n",
1061                                (*new_block) + i, name, error_message(retval));
1062         }
1063         free(buf);
1064 }
1065
1066 /*
1067  * This routine gets called at the end of pass 1 if bad blocks are
1068  * detected in the superblock, group descriptors, inode_bitmaps, or
1069  * block bitmaps.  At this point, all of the blocks have been mapped
1070  * out, so we can try to allocate new block(s) to replace the bad
1071  * blocks.
1072  */
1073 static void handle_fs_bad_blocks(ext2_filsys fs)
1074 {
1075         int             i;
1076         int             first_block = fs->super->s_first_data_block;
1077
1078         for (i = 0; i < fs->group_desc_count; i++) {
1079                 if (invalid_block_bitmap[i]) {
1080                         new_table_block(fs, first_block, i, "block bitmap", 1,
1081                                         &fs->group_desc[i].bg_block_bitmap);
1082                 }
1083                 if (invalid_inode_bitmap[i]) {
1084                         new_table_block(fs, first_block, i, "inode bitmap", 1,
1085                                         &fs->group_desc[i].bg_inode_bitmap);
1086                 }
1087                 if (invalid_inode_table[i]) {
1088                         new_table_block(fs, first_block, i, "inode table",
1089                                         fs->inode_blocks_per_group,
1090                                         &fs->group_desc[i].bg_inode_table);
1091                         restart_e2fsck++;
1092                 }
1093                 first_block += fs->super->s_blocks_per_group;
1094         }
1095         invalid_bitmaps = 0;
1096 }
1097
1098 /*
1099  * This routine marks all blocks which are used by the superblock,
1100  * group descriptors, inode bitmaps, and block bitmaps.
1101  */
1102 static void mark_table_blocks(ext2_filsys fs)
1103 {
1104         blk_t   block, b;
1105         int     i,j;
1106
1107         block = fs->super->s_first_data_block;
1108         for (i = 0; i < fs->group_desc_count; i++) {
1109                 /*
1110                  * Mark block used for the block bitmap
1111                  */
1112                 if (fs->group_desc[i].bg_block_bitmap) {
1113                         if (ext2fs_test_block_bitmap(block_found_map,
1114                                      fs->group_desc[i].bg_block_bitmap)) {
1115                                 printf("Group %i's block bitmap at %u "
1116                                        "conflicts with some other fs block.\n",
1117                                        i, fs->group_desc[i].bg_block_bitmap);
1118                                 preenhalt(fs);
1119                                 if (ask("Relocate", 1)) {
1120                                         invalid_block_bitmap[i]++;
1121                                         invalid_bitmaps++;
1122                                 } else {
1123                                         ext2fs_unmark_valid(fs);
1124                                 }
1125                         } else {
1126                             ext2fs_mark_block_bitmap(block_found_map,
1127                                      fs->group_desc[i].bg_block_bitmap);
1128                             ext2fs_mark_block_bitmap(block_illegal_map,
1129                                      fs->group_desc[i].bg_block_bitmap);
1130                     }
1131
1132                 }
1133                 /*
1134                  * Mark block used for the inode bitmap
1135                  */
1136                 if (fs->group_desc[i].bg_inode_bitmap) {
1137                         if (ext2fs_test_block_bitmap(block_found_map,
1138                                      fs->group_desc[i].bg_inode_bitmap)) {
1139                                 printf("Group %i's inode bitmap at %u "
1140                                        "conflicts with some other fs block.\n",
1141                                        i, fs->group_desc[i].bg_inode_bitmap);
1142                                 preenhalt(fs);
1143                                 if (ask("Relocate", 1)) {
1144                                         invalid_inode_bitmap[i]++;
1145                                         invalid_bitmaps++;
1146                                 } else {
1147                                         ext2fs_unmark_valid(fs);
1148                                 }
1149                         } else {
1150                             ext2fs_mark_block_bitmap(block_found_map,
1151                                      fs->group_desc[i].bg_inode_bitmap);
1152                             ext2fs_mark_block_bitmap(block_illegal_map,
1153                                      fs->group_desc[i].bg_inode_bitmap);
1154                         }
1155                 }
1156
1157                 /*
1158                  * Mark the blocks used for the inode table
1159                  */
1160                 if (fs->group_desc[i].bg_inode_table) {
1161                         for (j = 0, b = fs->group_desc[i].bg_inode_table;
1162                              j < fs->inode_blocks_per_group;
1163                              j++, b++) {
1164                                 if (ext2fs_test_block_bitmap(block_found_map,
1165                                                              b)) {
1166                                         printf("Group %i's inode table at %u "
1167                                                "conflicts with some other "
1168                                                "fs block.\n",
1169                                                i, b);
1170                                         preenhalt(fs);
1171                                         if (ask("Relocate", 1)) {
1172                                                 invalid_inode_table[i]++;
1173                                                 invalid_bitmaps++;
1174                                         } else {
1175                                                 ext2fs_unmark_valid(fs);
1176                                         }
1177                                 } else {
1178                                     ext2fs_mark_block_bitmap(block_found_map,
1179                                                              b);
1180                                     ext2fs_mark_block_bitmap(block_illegal_map,
1181                                                              b);
1182                                     }
1183                         }
1184                 }
1185
1186                 /*
1187                  * Mark this group's copy of the superblock
1188                  */
1189                 ext2fs_mark_block_bitmap(block_found_map, block);
1190                 ext2fs_mark_block_bitmap(block_illegal_map, block);
1191
1192                 /*
1193                  * Mark this group's copy of the descriptors
1194                  */
1195                 for (j = 0; j < fs->desc_blocks; j++) {
1196                         ext2fs_mark_block_bitmap(block_found_map,
1197                                                  block + j + 1);
1198                         ext2fs_mark_block_bitmap(block_illegal_map,
1199                                                  block + j + 1);
1200                 }
1201                 block += fs->super->s_blocks_per_group;
1202         }
1203 }
1204
1205 /*
1206  * This subroutines short circuits ext2fs_get_blocks and
1207  * ext2fs_check_directory; we use them since we already have the inode
1208  * structure, so there's no point in letting the ext2fs library read
1209  * the inode again.
1210  */
1211 static errcode_t pass1_get_blocks(ext2_filsys fs, ino_t ino, blk_t *blocks)
1212 {
1213         int     i;
1214
1215         if (ino == stashed_ino) {
1216                 for (i=0; i < EXT2_N_BLOCKS; i++)
1217                         blocks[i] = stashed_inode->i_block[i];
1218                 return 0;
1219         }
1220         printf("INTERNAL ERROR: pass1_get_blocks: unexpected inode #%lu\n",
1221                ino);
1222         printf("\t(was expecting %lu)\n", stashed_ino);
1223         exit(FSCK_ERROR);
1224 }
1225
1226 static errcode_t pass1_check_directory(ext2_filsys fs, ino_t ino)
1227 {
1228         if (ino == stashed_ino) {
1229                 if (!LINUX_S_ISDIR(stashed_inode->i_mode))
1230                         return ENOTDIR;
1231                 return 0;
1232         }
1233         printf("INTERNAL ERROR: pass1_check_directory: unexpected inode #%lu\n",
1234                ino);
1235         printf("\t(was expecting %lu)\n", stashed_ino);
1236         exit(FSCK_ERROR);
1237 }