e2fsck/pass1.c

   1 /*
   2  * pass1.c -- pass #1 of e2fsck: sequential scan of the inode table
   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  * Pass 1 of e2fsck iterates over all the inodes in the filesystems,
  12  * and applies the following tests to each inode:
  13  *
  14  *      - The mode field of the inode must be legal.
  15  *      - The size and block count fields of the inode are correct.
  16  *      - A data block must not be used by another inode
  17  *
  18  * Pass 1 also gathers the collects the following information:
  19  *
  20  *      - A bitmap of which inodes are in use.          (inode_used_map)
  21  *      - A bitmap of which inodes are directories.     (inode_dir_map)
  22  *      - A bitmap of which inodes are regular files.   (inode_reg_map)
  23  *      - A bitmap of which inodes have bad fields.     (inode_bad_map)
  24  *      - A bitmap of which inodes are in bad blocks.   (inode_bb_map)
  25  *      - A bitmap of which inodes are imagic inodes.   (inode_imagic_map)
  26  *      - A bitmap of which blocks are in use.          (block_found_map)
  27  *      - A bitmap of which blocks are in use by two inodes     (block_dup_map)
  28  *      - The data blocks of the directory inodes.      (dir_map)
  29  *
  30  * Pass 1 is designed to stash away enough information so that the
  31  * other passes should not need to read in the inode information
  32  * during the normal course of a filesystem check.  (Althogh if an
  33  * inconsistency is detected, other passes may need to read in an
  34  * inode to fix it.)
  35  *
  36  * Note that pass 1B will be invoked if there are any duplicate blocks
  37  * found.
  38  */
  39
  40 #define _GNU_SOURCE 1 /* get strnlen() */
  41 #include <string.h>
  42 #include <time.h>
  43 #ifdef HAVE_ERRNO_H
  44 #include <errno.h>
  45 #endif
  46
  47 #include "e2fsck.h"
  48 #include <ext2fs/ext2_ext_attr.h>
  49
  50 #include "problem.h"
  51
  52 #ifdef NO_INLINE_FUNCS
  53 #define _INLINE_
  54 #else
  55 #define _INLINE_ inline
  56 #endif
  57
  58 static int process_block(ext2_filsys fs, blk_t  *blocknr,
  59                          e2_blkcnt_t blockcnt, blk_t ref_blk,
  60                          int ref_offset, void *priv_data);
  61 static int process_bad_block(ext2_filsys fs, blk_t *block_nr,
  62                              e2_blkcnt_t blockcnt, blk_t ref_blk,
  63                              int ref_offset, void *priv_data);
  64 static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
  65                          char *block_buf);
  66 static void mark_table_blocks(e2fsck_t ctx);
  67 static void alloc_bb_map(e2fsck_t ctx);
  68 static void alloc_imagic_map(e2fsck_t ctx);
  69 static void mark_inode_bad(e2fsck_t ctx, ino_t ino);
  70 static void handle_fs_bad_blocks(e2fsck_t ctx);
  71 static void process_inodes(e2fsck_t ctx, char *block_buf);
  72 static EXT2_QSORT_TYPE process_inode_cmp(const void *a, const void *b);
  73 static errcode_t scan_callback(ext2_filsys fs, ext2_inode_scan scan,
  74                                   dgrp_t group, void * priv_data);
  75 static void adjust_extattr_refcount(e2fsck_t ctx, ext2_refcount_t refcount,
  76                                     char *block_buf, int adjust_sign);
  77 /* static char *describe_illegal_block(ext2_filsys fs, blk_t block); */
  78
  79 struct process_block_struct {
  80         ext2_ino_t      ino;
  81         unsigned        is_dir:1, is_reg:1, clear:1, suppress:1,
  82                                 fragmented:1, compressed:1, bbcheck:1;
  83         blk_t           num_blocks;
  84         blk_t           max_blocks;
  85         e2_blkcnt_t     last_block;
  86         int             num_illegal_blocks;
  87         blk_t           previous_block;
  88         struct ext2_inode *inode;
  89         struct problem_context *pctx;
  90         ext2fs_block_bitmap fs_meta_blocks;
  91         e2fsck_t        ctx;
  92 };
  93
  94 struct process_inode_block {
  95         ext2_ino_t ino;
  96         struct ext2_inode inode;
  97 };
  98
  99 struct scan_callback_struct {
 100         e2fsck_t        ctx;
 101         char            *block_buf;
 102 };
 103
 104 /*
 105  * For the inodes to process list.
 106  */
 107 static struct process_inode_block *inodes_to_process;
 108 static int process_inode_count;
 109
 110 static __u64 ext2_max_sizes[EXT2_MAX_BLOCK_LOG_SIZE -
 111                             EXT2_MIN_BLOCK_LOG_SIZE + 1];
 112
 113 /*
 114  * Free all memory allocated by pass1 in preparation for restarting
 115  * things.
 116  */
 117 static void unwind_pass1(ext2_filsys fs EXT2FS_ATTR((unused)))
 118 {
 119         ext2fs_free_mem(&inodes_to_process);
 120         inodes_to_process = 0;
 121 }
 122
 123 /*
 124  * Check to make sure a device inode is real.  Returns 1 if the device
 125  * checks out, 0 if not.
 126  *
 127  * Note: this routine is now also used to check FIFO's and Sockets,
 128  * since they have the same requirement; the i_block fields should be
 129  * zero.
 130  */
 131 int e2fsck_pass1_check_device_inode(ext2_filsys fs EXT2FS_ATTR((unused)),
 132                                     struct ext2_inode *inode)
 133 {
 134         int     i;
 135
 136         /*
 137          * If the index flag is set, then this is a bogus
 138          * device/fifo/socket
 139          */
 140         if (inode->i_flags & EXT2_INDEX_FL)
 141                 return 0;
 142
 143         /*
 144          * We should be able to do the test below all the time, but
 145          * because the kernel doesn't forcibly clear the device
 146          * inode's additional i_block fields, there are some rare
 147          * occasions when a legitimate device inode will have non-zero
 148          * additional i_block fields.  So for now, we only complain
 149          * when the immutable flag is set, which should never happen
 150          * for devices.  (And that's when the problem is caused, since
 151          * you can't set or clear immutable flags for devices.)  Once
 152          * the kernel has been fixed we can change this...
 153          */
 154         if (inode->i_flags & (EXT2_IMMUTABLE_FL | EXT2_APPEND_FL)) {
 155                 for (i=4; i < EXT2_N_BLOCKS; i++)
 156                         if (inode->i_block[i])
 157                                 return 0;
 158         }
 159         return 1;
 160 }
 161
 162 /*
 163  * Check to make sure a symlink inode is real.  Returns 1 if the symlink
 164  * checks out, 0 if not.
 165  */
 166 int e2fsck_pass1_check_symlink(ext2_filsys fs, struct ext2_inode *inode,
 167                                char *buf)
 168 {
 169         unsigned int len;
 170         int i;
 171         blk_t   blocks;
 172
 173         if ((inode->i_size_high || inode->i_size == 0) ||
 174             (inode->i_flags & EXT2_INDEX_FL))
 175                 return 0;
 176
 177         blocks = ext2fs_inode_data_blocks(fs, inode);
 178         if (blocks) {
 179                 if ((inode->i_size >= fs->blocksize) ||
 180                     (blocks != fs->blocksize >> 9) ||
 181                     (inode->i_block[0] < fs->super->s_first_data_block) ||
 182                     (inode->i_block[0] >= fs->super->s_blocks_count))
 183                         return 0;
 184
 185                 for (i = 1; i < EXT2_N_BLOCKS; i++)
 186                         if (inode->i_block[i])
 187                                 return 0;
 188
 189                 if (io_channel_read_blk(fs->io, inode->i_block[0], 1, buf))
 190                         return 0;
 191
 192                 len = strnlen(buf, fs->blocksize);
 193                 if (len == fs->blocksize)
 194                         return 0;
 195         } else {
 196                 if (inode->i_size >= sizeof(inode->i_block))
 197                         return 0;
 198
 199                 len = strnlen((char *)inode->i_block, sizeof(inode->i_block));
 200                 if (len == sizeof(inode->i_block))
 201                         return 0;
 202         }
 203         if (len != inode->i_size)
 204                 return 0;
 205         return 1;
 206 }
 207
 208 /*
 209  * If the immutable (or append-only) flag is set on the inode, offer
 210  * to clear it.
 211  */
 212 #define BAD_SPECIAL_FLAGS (EXT2_IMMUTABLE_FL | EXT2_APPEND_FL)
 213 static void check_immutable(e2fsck_t ctx, struct problem_context *pctx)
 214 {
 215         if (!(pctx->inode->i_flags & BAD_SPECIAL_FLAGS))
 216                 return;
 217
 218         if (!fix_problem(ctx, PR_1_SET_IMMUTABLE, pctx))
 219                 return;
 220
 221         pctx->inode->i_flags &= ~BAD_SPECIAL_FLAGS;
 222         e2fsck_write_inode(ctx, pctx->ino, pctx->inode, "pass1");
 223 }
 224
 225 /*
 226  * If device, fifo or socket, check size is zero -- if not offer to
 227  * clear it
 228  */
 229 static void check_size(e2fsck_t ctx, struct problem_context *pctx)
 230 {
 231         struct ext2_inode *inode = pctx->inode;
 232
 233         if ((inode->i_size == 0) && (inode->i_size_high == 0))
 234                 return;
 235
 236         if (!fix_problem(ctx, PR_1_SET_NONZSIZE, pctx))
 237                 return;
 238
 239         inode->i_size = 0;
 240         inode->i_size_high = 0;
 241         e2fsck_write_inode(ctx, pctx->ino, pctx->inode, "pass1");
 242 }
 243
 244 static void check_ea_in_inode(e2fsck_t ctx, struct problem_context *pctx)
 245 {
 246         struct ext2_super_block *sb = ctx->fs->super;
 247         struct ext2_inode_large *inode;
 248         struct ext2_ext_attr_entry *entry;
 249         char *start, *end;
 250         unsigned int storage_size, remain;
 251         int problem = 0;
 252
 253         inode = (struct ext2_inode_large *) pctx->inode;
 254         storage_size = EXT2_INODE_SIZE(ctx->fs->super) - EXT2_GOOD_OLD_INODE_SIZE -
 255                 inode->i_extra_isize;
 256         start = ((char *) inode) + EXT2_GOOD_OLD_INODE_SIZE +
 257                 inode->i_extra_isize + sizeof(__u32);
 258         end = (char *) inode + EXT2_INODE_SIZE(ctx->fs->super);
 259         entry = (struct ext2_ext_attr_entry *) start;
 260
 261         /* scan all entry's headers first */
 262
 263         /* take finish entry 0UL into account */
 264         remain = storage_size - sizeof(__u32);
 265
 266         while (!EXT2_EXT_IS_LAST_ENTRY(entry)) {
 267
 268                 /* header eats this space */
 269                 remain -= sizeof(struct ext2_ext_attr_entry);
 270
 271                 /* is attribute name valid? */
 272                 if (EXT2_EXT_ATTR_SIZE(entry->e_name_len) > remain) {
 273                         pctx->num = entry->e_name_len;
 274                         problem = PR_1_ATTR_NAME_LEN;
 275                         goto fix;
 276                 }
 277
 278                 /* attribute len eats this space */
 279                 remain -= EXT2_EXT_ATTR_SIZE(entry->e_name_len);
 280
 281                 /* check value size */
 282                 if (entry->e_value_size == 0 || entry->e_value_size > remain) {
 283                         pctx->num = entry->e_value_size;
 284                         problem = PR_1_ATTR_VALUE_SIZE;
 285                         goto fix;
 286                 }
 287
 288                 /* e_value_block must be 0 in inode's ea */
 289                 if (entry->e_value_block != 0) {
 290                         pctx->num = entry->e_value_block;
 291                         problem = PR_1_ATTR_VALUE_BLOCK;
 292                         goto fix;
 293                 }
 294
 295                 /* e_hash must be 0 in inode's ea */
 296                 if (entry->e_hash != 0) {
 297                         pctx->num = entry->e_hash;
 298                         problem = PR_1_ATTR_HASH;
 299                         goto fix;
 300                 }
 301
 302                 remain -= entry->e_value_size;
 303
 304                 entry = EXT2_EXT_ATTR_NEXT(entry);
 305         }
 306 fix:
 307         /*
 308          * it seems like a corruption. it's very unlikely we could repair
 309          * EA(s) in automatic fashion -bzzz
 310          */
 311 #if 0
 312         problem = PR_1_ATTR_HASH;
 313 #endif
 314         if (problem == 0 || !fix_problem(ctx, problem, pctx))
 315                 return;
 316
 317         /* simple remove all possible EA(s) */
 318         *((__u32 *)start) = 0UL;
 319         e2fsck_write_inode_full(ctx, pctx->ino, (struct ext2_inode *) inode,
 320                                 EXT2_INODE_SIZE(sb), "pass1");
 321 }
 322
 323 static void check_inode_extra_space(e2fsck_t ctx, struct problem_context *pctx)
 324 {
 325         struct ext2_super_block *sb = ctx->fs->super;
 326         struct ext2_inode_large *inode;
 327         __u32 *eamagic;
 328         int min, max;
 329
 330         inode = (struct ext2_inode_large *) pctx->inode;
 331         if (EXT2_INODE_SIZE(sb) == EXT2_GOOD_OLD_INODE_SIZE) {
 332                 /* this isn't large inode. so, nothing to check */
 333                 return;
 334         }
 335
 336 #if 0
 337         printf("inode #%u, i_extra_size %d\n", pctx->ino,
 338                         inode->i_extra_isize);
 339 #endif
 340         /* i_extra_isize must cover i_extra_isize + i_pad1 at least */
 341         min = sizeof(inode->i_extra_isize) + sizeof(inode->i_pad1);
 342         max = EXT2_INODE_SIZE(sb) - EXT2_GOOD_OLD_INODE_SIZE;
 343         /*
 344          * For now we will allow i_extra_isize to be 0, but really
 345          * implementations should never allow i_extra_isize to be 0
 346          */
 347         if (inode->i_extra_isize &&
 348             (inode->i_extra_isize < min || inode->i_extra_isize > max)) {
 349                 if (!fix_problem(ctx, PR_1_EXTRA_ISIZE, pctx))
 350                         return;
 351                 inode->i_extra_isize = min;
 352                 e2fsck_write_inode_full(ctx, pctx->ino, pctx->inode,
 353                                         EXT2_INODE_SIZE(sb), "pass1");
 354                 return;
 355         }
 356
 357         eamagic = (__u32 *) (((char *) inode) + EXT2_GOOD_OLD_INODE_SIZE +
 358                         inode->i_extra_isize);
 359         if (*eamagic == EXT2_EXT_ATTR_MAGIC) {
 360                 /* it seems inode has an extended attribute(s) in body */
 361                 check_ea_in_inode(ctx, pctx);
 362         }
 363 }
 364
 365 /*
 366  * Check to see if the inode might really be a directory, despite i_mode
 367  *
 368  * This is a lot of complexity for something for which I'm not really
 369  * convinced happens frequently in the wild.  If for any reason this
 370  * causes any problems, take this code out.
 371  * [tytso:20070331.0827EDT]
 372  */
 373 static void check_is_really_dir(e2fsck_t ctx, struct problem_context *pctx,
 374                                 char *buf)
 375 {
 376         struct ext2_inode *inode = pctx->inode;
 377         struct ext2_dir_entry   *dirent;
 378         const char              *old_op;
 379         errcode_t               retval;
 380         blk_t                   blk;
 381         int                     i, not_device = 0;
 382
 383         if (LINUX_S_ISDIR(inode->i_mode) || LINUX_S_ISREG(inode->i_mode) ||
 384             LINUX_S_ISLNK(inode->i_mode) || inode->i_block[0] == 0)
 385                 return;
 386
 387         for (i=0; i < EXT2_N_BLOCKS; i++) {
 388                 blk = inode->i_block[i];
 389                 if (!blk)
 390                         continue;
 391                 if (i >= 4)
 392                         not_device++;
 393
 394                 if (blk < ctx->fs->super->s_first_data_block ||
 395                     blk >= ctx->fs->super->s_blocks_count ||
 396                     ext2fs_fast_test_block_bitmap(ctx->block_found_map, blk))
 397                         return; /* Invalid block, can't be dir */
 398         }
 399
 400         if ((LINUX_S_ISCHR(inode->i_mode) || LINUX_S_ISBLK(inode->i_mode)) &&
 401             (inode->i_links_count == 1) && !not_device)
 402                 return;
 403
 404         old_op = ehandler_operation(_("reading directory block"));
 405         retval = ext2fs_read_dir_block(ctx->fs, inode->i_block[0], buf);
 406         ehandler_operation(0);
 407         if (retval)
 408                 return;
 409
 410         dirent = (struct ext2_dir_entry *) buf;
 411         if (((dirent->name_len & 0xFF) != 1) ||
 412             (dirent->name[0] != '.') ||
 413             (dirent->inode != pctx->ino) ||
 414             (dirent->rec_len < 12) ||
 415             (dirent->rec_len % 4) ||
 416             (dirent->rec_len >= ctx->fs->blocksize - 12))
 417                 return;
 418
 419         dirent = (struct ext2_dir_entry *) (buf + dirent->rec_len);
 420         if (((dirent->name_len & 0xFF) != 2) ||
 421             (dirent->name[0] != '.') ||
 422             (dirent->name[1] != '.') ||
 423             (dirent->rec_len < 12) ||
 424             (dirent->rec_len % 4))
 425                 return;
 426
 427         if (fix_problem(ctx, PR_1_TREAT_AS_DIRECTORY, pctx)) {
 428                 inode->i_mode = (inode->i_mode & 07777) | LINUX_S_IFDIR;
 429                 e2fsck_write_inode_full(ctx, pctx->ino, inode,
 430                                         EXT2_INODE_SIZE(ctx->fs->super),
 431                                         "check_is_really_dir");
 432         }
 433 }
 434
 435 extern void e2fsck_setup_tdb_icount(e2fsck_t ctx, int flags,
 436                                     ext2_icount_t *ret)
 437 {
 438         unsigned int            threshold;
 439         ext2_ino_t              num_dirs;
 440         errcode_t               retval;
 441         char                    *tdb_dir;
 442         int                     enable;
 443
 444         *ret = 0;
 445
 446         profile_get_string(ctx->profile, "scratch_files", "directory", 0, 0,
 447                            &tdb_dir);
 448         profile_get_uint(ctx->profile, "scratch_files",
 449                          "numdirs_threshold", 0, 0, &threshold);
 450         profile_get_boolean(ctx->profile, "scratch_files",
 451                             "icount", 0, 1, &enable);
 452
 453         retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs);
 454         if (retval)
 455                 num_dirs = 1024;        /* Guess */
 456
 457         if (!enable || !tdb_dir || access(tdb_dir, W_OK) ||
 458             (threshold && num_dirs <= threshold))
 459                 return;
 460
 461         retval = ext2fs_create_icount_tdb(ctx->fs, tdb_dir, flags, ret);
 462         if (retval)
 463                 *ret = 0;
 464 }
 465
 466 void e2fsck_pass1(e2fsck_t ctx)
 467 {
 468         int     i;
 469         __u64   max_sizes;
 470         ext2_filsys fs = ctx->fs;
 471         ext2_ino_t      ino;
 472         struct ext2_inode *inode;
 473         ext2_inode_scan scan;
 474         char            *block_buf;
 475 #ifdef RESOURCE_TRACK
 476         struct resource_track   rtrack;
 477 #endif
 478         unsigned char   frag, fsize;
 479         struct          problem_context pctx;
 480         struct          scan_callback_struct scan_struct;
 481         struct ext2_super_block *sb = ctx->fs->super;
 482         const char      *old_op;
 483         int             imagic_fs;
 484         int             busted_fs_time = 0;
 485         int             inode_size;
 486
 487 #ifdef RESOURCE_TRACK
 488         init_resource_track(&rtrack);
 489 #endif
 490         clear_problem_context(&pctx);
 491
 492         if (!(ctx->options & E2F_OPT_PREEN))
 493                 fix_problem(ctx, PR_1_PASS_HEADER, &pctx);
 494
 495         if ((fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) &&
 496             !(ctx->options & E2F_OPT_NO)) {
 497                 if (ext2fs_u32_list_create(&ctx->dirs_to_hash, 50))
 498                         ctx->dirs_to_hash = 0;
 499         }
 500
 501 #ifdef MTRACE
 502         mtrace_print("Pass 1");
 503 #endif
 504
 505 #define EXT2_BPP(bits) (1ULL << ((bits) - 2))
 506
 507         for (i = EXT2_MIN_BLOCK_LOG_SIZE; i <= EXT2_MAX_BLOCK_LOG_SIZE; i++) {
 508                 max_sizes = EXT2_NDIR_BLOCKS + EXT2_BPP(i);
 509                 max_sizes = max_sizes + EXT2_BPP(i) * EXT2_BPP(i);
 510                 max_sizes = max_sizes + EXT2_BPP(i) * EXT2_BPP(i) * EXT2_BPP(i);
 511                 max_sizes = (max_sizes * (1UL << i)) - 1;
 512                 ext2_max_sizes[i - EXT2_MIN_BLOCK_LOG_SIZE] = max_sizes;
 513         }
 514 #undef EXT2_BPP
 515
 516         imagic_fs = (sb->s_feature_compat & EXT2_FEATURE_COMPAT_IMAGIC_INODES);
 517
 518         /*
 519          * Allocate bitmaps structures
 520          */
 521         pctx.errcode = ext2fs_allocate_inode_bitmap(fs, _("in-use inode map"),
 522                                               &ctx->inode_used_map);
 523         if (pctx.errcode) {
 524                 pctx.num = 1;
 525                 fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
 526                 ctx->flags |= E2F_FLAG_ABORT;
 527                 return;
 528         }
 529         pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
 530                                 _("directory inode map"), &ctx->inode_dir_map);
 531         if (pctx.errcode) {
 532                 pctx.num = 2;
 533                 fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
 534                 ctx->flags |= E2F_FLAG_ABORT;
 535                 return;
 536         }
 537         pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
 538                         _("regular file inode map"), &ctx->inode_reg_map);
 539         if (pctx.errcode) {
 540                 pctx.num = 6;
 541                 fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
 542                 ctx->flags |= E2F_FLAG_ABORT;
 543                 return;
 544         }
 545         pctx.errcode = ext2fs_allocate_block_bitmap(fs, _("in-use block map"),
 546                                               &ctx->block_found_map);
 547         if (pctx.errcode) {
 548                 pctx.num = 1;
 549                 fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR, &pctx);
 550                 ctx->flags |= E2F_FLAG_ABORT;
 551                 return;
 552         }
 553         e2fsck_setup_tdb_icount(ctx, 0, &ctx->inode_link_info);
 554         if (!ctx->inode_link_info)
 555                 pctx.errcode = ext2fs_create_icount2(fs, 0, 0, 0,
 556                                                      &ctx->inode_link_info);
 557         if (pctx.errcode) {
 558                 fix_problem(ctx, PR_1_ALLOCATE_ICOUNT, &pctx);
 559                 ctx->flags |= E2F_FLAG_ABORT;
 560                 return;
 561         }
 562         inode_size = EXT2_INODE_SIZE(fs->super);
 563         inode = (struct ext2_inode *)
 564                 e2fsck_allocate_memory(ctx, inode_size, "scratch inode");
 565
 566         inodes_to_process = (struct process_inode_block *)
 567                 e2fsck_allocate_memory(ctx,
 568                                        (ctx->process_inode_size *
 569                                         sizeof(struct process_inode_block)),
 570                                        "array of inodes to process");
 571         process_inode_count = 0;
 572
 573         pctx.errcode = ext2fs_init_dblist(fs, 0);
 574         if (pctx.errcode) {
 575                 fix_problem(ctx, PR_1_ALLOCATE_DBCOUNT, &pctx);
 576                 ctx->flags |= E2F_FLAG_ABORT;
 577                 ext2fs_free_mem(&inode);
 578                 return;
 579         }
 580
 581         /*
 582          * If the last orphan field is set, clear it, since the pass1
 583          * processing will automatically find and clear the orphans.
 584          * In the future, we may want to try using the last_orphan
 585          * linked list ourselves, but for now, we clear it so that the
 586          * ext3 mount code won't get confused.
 587          */
 588         if (!(ctx->options & E2F_OPT_READONLY)) {
 589                 if (fs->super->s_last_orphan) {
 590                         fs->super->s_last_orphan = 0;
 591                         ext2fs_mark_super_dirty(fs);
 592                 }
 593         }
 594
 595         mark_table_blocks(ctx);
 596         block_buf = (char *) e2fsck_allocate_memory(ctx, fs->blocksize * 3,
 597                                                     "block interate buffer");
 598         e2fsck_use_inode_shortcuts(ctx, 1);
 599         old_op = ehandler_operation(_("opening inode scan"));
 600         pctx.errcode = ext2fs_open_inode_scan(fs, ctx->inode_buffer_blocks,
 601                                               &scan);
 602         ehandler_operation(old_op);
 603         if (pctx.errcode) {
 604                 fix_problem(ctx, PR_1_ISCAN_ERROR, &pctx);
 605                 ctx->flags |= E2F_FLAG_ABORT;
 606                 ext2fs_free_mem(&block_buf);
 607                 ext2fs_free_mem(&inode);
 608                 return;
 609         }
 610         ext2fs_inode_scan_flags(scan, EXT2_SF_SKIP_MISSING_ITABLE, 0);
 611         ctx->stashed_inode = inode;
 612         scan_struct.ctx = ctx;
 613         scan_struct.block_buf = block_buf;
 614         ext2fs_set_inode_callback(scan, scan_callback, &scan_struct);
 615         if (ctx->progress)
 616                 if ((ctx->progress)(ctx, 1, 0, ctx->fs->group_desc_count))
 617                         return;
 618         if ((fs->super->s_wtime < fs->super->s_inodes_count) ||
 619             (fs->super->s_mtime < fs->super->s_inodes_count))
 620                 busted_fs_time = 1;
 621
 622         while (1) {
 623                 old_op = ehandler_operation(_("getting next inode from scan"));
 624                 pctx.errcode = ext2fs_get_next_inode_full(scan, &ino,
 625                                                           inode, inode_size);
 626                 ehandler_operation(old_op);
 627                 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
 628                         return;
 629                 if (pctx.errcode == EXT2_ET_BAD_BLOCK_IN_INODE_TABLE) {
 630                         if (!ctx->inode_bb_map)
 631                                 alloc_bb_map(ctx);
 632                         ext2fs_mark_inode_bitmap(ctx->inode_bb_map, ino);
 633                         ext2fs_mark_inode_bitmap(ctx->inode_used_map, ino);
 634                         continue;
 635                 }
 636                 if (pctx.errcode) {
 637                         fix_problem(ctx, PR_1_ISCAN_ERROR, &pctx);
 638                         ctx->flags |= E2F_FLAG_ABORT;
 639                         return;
 640                 }
 641                 if (!ino)
 642                         break;
 643                 pctx.ino = ino;
 644                 pctx.inode = inode;
 645                 ctx->stashed_ino = ino;
 646                 if (inode->i_links_count) {
 647                         pctx.errcode = ext2fs_icount_store(ctx->inode_link_info,
 648                                            ino, inode->i_links_count);
 649                         if (pctx.errcode) {
 650                                 pctx.num = inode->i_links_count;
 651                                 fix_problem(ctx, PR_1_ICOUNT_STORE, &pctx);
 652                                 ctx->flags |= E2F_FLAG_ABORT;
 653                                 return;
 654                         }
 655                 }
 656                 if (ino == EXT2_BAD_INO) {
 657                         struct process_block_struct pb;
 658
 659                         pctx.errcode = ext2fs_copy_bitmap(ctx->block_found_map,
 660                                                           &pb.fs_meta_blocks);
 661                         if (pctx.errcode) {
 662                                 pctx.num = 4;
 663                                 fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR, &pctx);
 664                                 ctx->flags |= E2F_FLAG_ABORT;
 665                                 return;
 666                         }
 667                         pb.ino = EXT2_BAD_INO;
 668                         pb.num_blocks = pb.last_block = 0;
 669                         pb.num_illegal_blocks = 0;
 670                         pb.suppress = 0; pb.clear = 0; pb.is_dir = 0;
 671                         pb.is_reg = 0; pb.fragmented = 0; pb.bbcheck = 0;
 672                         pb.inode = inode;
 673                         pb.pctx = &pctx;
 674                         pb.ctx = ctx;
 675                         pctx.errcode = ext2fs_block_iterate2(fs, ino, 0,
 676                                      block_buf, process_bad_block, &pb);
 677                         ext2fs_free_block_bitmap(pb.fs_meta_blocks);
 678                         if (pctx.errcode) {
 679                                 fix_problem(ctx, PR_1_BLOCK_ITERATE, &pctx);
 680                                 ctx->flags |= E2F_FLAG_ABORT;
 681                                 return;
 682                         }
 683                         if (pb.bbcheck)
 684                                 if (!fix_problem(ctx, PR_1_BBINODE_BAD_METABLOCK_PROMPT, &pctx)) {
 685                                 ctx->flags |= E2F_FLAG_ABORT;
 686                                 return;
 687                         }
 688                         ext2fs_mark_inode_bitmap(ctx->inode_used_map, ino);
 689                         clear_problem_context(&pctx);
 690                         continue;
 691                 } else if (ino == EXT2_ROOT_INO) {
 692                         /*
 693                          * Make sure the root inode is a directory; if
 694                          * not, offer to clear it.  It will be
 695                          * regnerated in pass #3.
 696                          */
 697                         if (!LINUX_S_ISDIR(inode->i_mode)) {
 698                                 if (fix_problem(ctx, PR_1_ROOT_NO_DIR, &pctx)) {
 699                                         inode->i_dtime = ctx->now;
 700                                         inode->i_links_count = 0;
 701                                         ext2fs_icount_store(ctx->inode_link_info,
 702                                                             ino, 0);
 703                                         e2fsck_write_inode(ctx, ino, inode,
 704                                                            "pass1");
 705                                 }
 706
 707                         }
 708                         /*
 709                          * If dtime is set, offer to clear it.  mke2fs
 710                          * version 0.2b created filesystems with the
 711                          * dtime field set for the root and lost+found
 712                          * directories.  We won't worry about
 713                          * /lost+found, since that can be regenerated
 714                          * easily.  But we will fix the root directory
 715                          * as a special case.
 716                          */
 717                         if (inode->i_dtime && inode->i_links_count) {
 718                                 if (fix_problem(ctx, PR_1_ROOT_DTIME, &pctx)) {
 719                                         inode->i_dtime = 0;
 720                                         e2fsck_write_inode(ctx, ino, inode,
 721                                                            "pass1");
 722                                 }
 723                         }
 724                 } else if (ino == EXT2_JOURNAL_INO) {
 725                         ext2fs_mark_inode_bitmap(ctx->inode_used_map, ino);
 726                         if (fs->super->s_journal_inum == EXT2_JOURNAL_INO) {
 727                                 if (!LINUX_S_ISREG(inode->i_mode) &&
 728                                     fix_problem(ctx, PR_1_JOURNAL_BAD_MODE,
 729                                                 &pctx)) {
 730                                         inode->i_mode = LINUX_S_IFREG;
 731                                         e2fsck_write_inode(ctx, ino, inode,
 732                                                            "pass1");
 733                                 }
 734                                 check_blocks(ctx, &pctx, block_buf);
 735                                 continue;
 736                         }
 737                         if ((inode->i_links_count || inode->i_blocks ||
 738                              inode->i_blocks || inode->i_block[0]) &&
 739                             fix_problem(ctx, PR_1_JOURNAL_INODE_NOT_CLEAR,
 740                                         &pctx)) {
 741                                 memset(inode, 0, inode_size);
 742                                 ext2fs_icount_store(ctx->inode_link_info,
 743                                                     ino, 0);
 744                                 e2fsck_write_inode_full(ctx, ino, inode,
 745                                                         inode_size, "pass1");
 746                         }
 747                 } else if (ino < EXT2_FIRST_INODE(fs->super)) {
 748                         int     problem = 0;
 749
 750                         ext2fs_mark_inode_bitmap(ctx->inode_used_map, ino);
 751                         if (ino == EXT2_BOOT_LOADER_INO) {
 752                                 if (LINUX_S_ISDIR(inode->i_mode))
 753                                         problem = PR_1_RESERVED_BAD_MODE;
 754                         } else if (ino == EXT2_RESIZE_INO) {
 755                                 if (inode->i_mode &&
 756                                     !LINUX_S_ISREG(inode->i_mode))
 757                                         problem = PR_1_RESERVED_BAD_MODE;
 758                         } else {
 759                                 if (inode->i_mode != 0)
 760                                         problem = PR_1_RESERVED_BAD_MODE;
 761                         }
 762                         if (problem) {
 763                                 if (fix_problem(ctx, problem, &pctx)) {
 764                                         inode->i_mode = 0;
 765                                         e2fsck_write_inode(ctx, ino, inode,
 766                                                            "pass1");
 767                                 }
 768                         }
 769                         check_blocks(ctx, &pctx, block_buf);
 770                         continue;
 771                 }
 772                 /*
 773                  * Check for inodes who might have been part of the
 774                  * orphaned list linked list.  They should have gotten
 775                  * dealt with by now, unless the list had somehow been
 776                  * corrupted.
 777                  *
 778                  * FIXME: In the future, inodes which are still in use
 779                  * (and which are therefore) pending truncation should
 780                  * be handled specially.  Right now we just clear the
 781                  * dtime field, and the normal e2fsck handling of
 782                  * inodes where i_size and the inode blocks are
 783                  * inconsistent is to fix i_size, instead of releasing
 784                  * the extra blocks.  This won't catch the inodes that
 785                  * was at the end of the orphan list, but it's better
 786                  * than nothing.  The right answer is that there
 787                  * shouldn't be any bugs in the orphan list handling.  :-)
 788                  */
 789                 if (inode->i_dtime && !busted_fs_time &&
 790                     inode->i_dtime < ctx->fs->super->s_inodes_count) {
 791                         if (fix_problem(ctx, PR_1_LOW_DTIME, &pctx)) {
 792                                 inode->i_dtime = inode->i_links_count ?
 793                                         0 : ctx->now;
 794                                 e2fsck_write_inode(ctx, ino, inode,
 795                                                    "pass1");
 796                         }
 797                 }
 798
 799                 /*
 800                  * This code assumes that deleted inodes have
 801                  * i_links_count set to 0.
 802                  */
 803                 if (!inode->i_links_count) {
 804                         if (!inode->i_dtime && inode->i_mode) {
 805                                 if (fix_problem(ctx,
 806                                             PR_1_ZERO_DTIME, &pctx)) {
 807                                         inode->i_dtime = ctx->now;
 808                                         e2fsck_write_inode(ctx, ino, inode,
 809                                                            "pass1");
 810                                 }
 811                         }
 812                         continue;
 813                 }
 814                 /*
 815                  * n.b.  0.3c ext2fs code didn't clear i_links_count for
 816                  * deleted files.  Oops.
 817                  *
 818                  * Since all new ext2 implementations get this right,
 819                  * we now assume that the case of non-zero
 820                  * i_links_count and non-zero dtime means that we
 821                  * should keep the file, not delete it.
 822                  *
 823                  */
 824                 if (inode->i_dtime) {
 825                         if (fix_problem(ctx, PR_1_SET_DTIME, &pctx)) {
 826                                 inode->i_dtime = 0;
 827                                 e2fsck_write_inode(ctx, ino, inode, "pass1");
 828                         }
 829                 }
 830
 831                 ext2fs_mark_inode_bitmap(ctx->inode_used_map, ino);
 832                 switch (fs->super->s_creator_os) {
 833                     case EXT2_OS_HURD:
 834                         frag = inode->osd2.hurd2.h_i_frag;
 835                         fsize = inode->osd2.hurd2.h_i_fsize;
 836                         break;
 837                     case EXT2_OS_MASIX:
 838                         frag = inode->osd2.masix2.m_i_frag;
 839                         fsize = inode->osd2.masix2.m_i_fsize;
 840                         break;
 841                     default:
 842                         frag = fsize = 0;
 843                 }
 844
 845                 if (inode->i_faddr || frag || fsize ||
 846                     (LINUX_S_ISDIR(inode->i_mode) && inode->i_dir_acl))
 847                         mark_inode_bad(ctx, ino);
 848                 if ((fs->super->s_creator_os == EXT2_OS_LINUX) &&
 849                     !(fs->super->s_feature_ro_compat &
 850                       EXT4_FEATURE_RO_COMPAT_HUGE_FILE) &&
 851                     (inode->osd2.linux2.l_i_blocks_hi != 0))
 852                         mark_inode_bad(ctx, ino);
 853                 if (inode->i_flags & EXT2_IMAGIC_FL) {
 854                         if (imagic_fs) {
 855                                 if (!ctx->inode_imagic_map)
 856                                         alloc_imagic_map(ctx);
 857                                 ext2fs_mark_inode_bitmap(ctx->inode_imagic_map,
 858                                                          ino);
 859                         } else {
 860                                 if (fix_problem(ctx, PR_1_SET_IMAGIC, &pctx)) {
 861                                         inode->i_flags &= ~EXT2_IMAGIC_FL;
 862                                         e2fsck_write_inode(ctx, ino,
 863                                                            inode, "pass1");
 864                                 }
 865                         }
 866                 }
 867
 868                 check_inode_extra_space(ctx, &pctx);
 869                 check_is_really_dir(ctx, &pctx, block_buf);
 870
 871                 if (LINUX_S_ISDIR(inode->i_mode)) {
 872                         ext2fs_mark_inode_bitmap(ctx->inode_dir_map, ino);
 873                         e2fsck_add_dir_info(ctx, ino, 0);
 874                         ctx->fs_directory_count++;
 875                 } else if (LINUX_S_ISREG (inode->i_mode)) {
 876                         ext2fs_mark_inode_bitmap(ctx->inode_reg_map, ino);
 877                         ctx->fs_regular_count++;
 878                 } else if (LINUX_S_ISCHR (inode->i_mode) &&
 879                            e2fsck_pass1_check_device_inode(fs, inode)) {
 880                         check_immutable(ctx, &pctx);
 881                         check_size(ctx, &pctx);
 882                         ctx->fs_chardev_count++;
 883                 } else if (LINUX_S_ISBLK (inode->i_mode) &&
 884                            e2fsck_pass1_check_device_inode(fs, inode)) {
 885                         check_immutable(ctx, &pctx);
 886                         check_size(ctx, &pctx);
 887                         ctx->fs_blockdev_count++;
 888                 } else if (LINUX_S_ISLNK (inode->i_mode) &&
 889                            e2fsck_pass1_check_symlink(fs, inode, block_buf)) {
 890                         check_immutable(ctx, &pctx);
 891                         ctx->fs_symlinks_count++;
 892                         if (ext2fs_inode_data_blocks(fs, inode) == 0) {
 893                                 ctx->fs_fast_symlinks_count++;
 894                                 check_blocks(ctx, &pctx, block_buf);
 895                                 continue;
 896                         }
 897                 }
 898                 else if (LINUX_S_ISFIFO (inode->i_mode) &&
 899                          e2fsck_pass1_check_device_inode(fs, inode)) {
 900                         check_immutable(ctx, &pctx);
 901                         check_size(ctx, &pctx);
 902                         ctx->fs_fifo_count++;
 903                 } else if ((LINUX_S_ISSOCK (inode->i_mode)) &&
 904                            e2fsck_pass1_check_device_inode(fs, inode)) {
 905                         check_immutable(ctx, &pctx);
 906                         check_size(ctx, &pctx);
 907                         ctx->fs_sockets_count++;
 908                 } else
 909                         mark_inode_bad(ctx, ino);
 910                 if (inode->i_block[EXT2_IND_BLOCK])
 911                         ctx->fs_ind_count++;
 912                 if (inode->i_block[EXT2_DIND_BLOCK])
 913                         ctx->fs_dind_count++;
 914                 if (inode->i_block[EXT2_TIND_BLOCK])
 915                         ctx->fs_tind_count++;
 916                 if (inode->i_block[EXT2_IND_BLOCK] ||
 917                     inode->i_block[EXT2_DIND_BLOCK] ||
 918                     inode->i_block[EXT2_TIND_BLOCK] ||
 919                     inode->i_file_acl) {
 920                         inodes_to_process[process_inode_count].ino = ino;
 921                         inodes_to_process[process_inode_count].inode = *inode;
 922                         process_inode_count++;
 923                 } else
 924                         check_blocks(ctx, &pctx, block_buf);
 925
 926                 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
 927                         return;
 928
 929                 if (process_inode_count >= ctx->process_inode_size) {
 930                         process_inodes(ctx, block_buf);
 931
 932                         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
 933                                 return;
 934                 }
 935         }
 936         process_inodes(ctx, block_buf);
 937         ext2fs_close_inode_scan(scan);
 938
 939         /*
 940          * If any extended attribute blocks' reference counts need to
 941          * be adjusted, either up (ctx->refcount_extra), or down
 942          * (ctx->refcount), then fix them.
 943          */
 944         if (ctx->refcount) {
 945                 adjust_extattr_refcount(ctx, ctx->refcount, block_buf, -1);
 946                 ea_refcount_free(ctx->refcount);
 947                 ctx->refcount = 0;
 948         }
 949         if (ctx->refcount_extra) {
 950                 adjust_extattr_refcount(ctx, ctx->refcount_extra,
 951                                         block_buf, +1);
 952                 ea_refcount_free(ctx->refcount_extra);
 953                 ctx->refcount_extra = 0;
 954         }
 955
 956         if (ctx->invalid_bitmaps)
 957                 handle_fs_bad_blocks(ctx);
 958
 959         /* We don't need the block_ea_map any more */
 960         if (ctx->block_ea_map) {
 961                 ext2fs_free_block_bitmap(ctx->block_ea_map);
 962                 ctx->block_ea_map = 0;
 963         }
 964
 965         if (ctx->flags & E2F_FLAG_RESIZE_INODE) {
 966                 ext2fs_block_bitmap save_bmap;
 967
 968                 save_bmap = fs->block_map;
 969                 fs->block_map = ctx->block_found_map;
 970                 clear_problem_context(&pctx);
 971                 pctx.errcode = ext2fs_create_resize_inode(fs);
 972                 if (pctx.errcode) {
 973                         fix_problem(ctx, PR_1_RESIZE_INODE_CREATE, &pctx);
 974                         /* Should never get here */
 975                         ctx->flags |= E2F_FLAG_ABORT;
 976                         return;
 977                 }
 978                 e2fsck_read_inode(ctx, EXT2_RESIZE_INO, inode,
 979                                   "recreate inode");
 980                 inode->i_mtime = ctx->now;
 981                 e2fsck_write_inode(ctx, EXT2_RESIZE_INO, inode,
 982                                    "recreate inode");
 983                 fs->block_map = save_bmap;
 984                 ctx->flags &= ~E2F_FLAG_RESIZE_INODE;
 985         }
 986
 987         if (ctx->flags & E2F_FLAG_RESTART) {
 988                 /*
 989                  * Only the master copy of the superblock and block
 990                  * group descriptors are going to be written during a
 991                  * restart, so set the superblock to be used to be the
 992                  * master superblock.
 993                  */
 994                 ctx->use_superblock = 0;
 995                 unwind_pass1(fs);
 996                 goto endit;
 997         }
 998
 999         if (ctx->block_dup_map) {
1000                 if (ctx->options & E2F_OPT_PREEN) {
1001                         clear_problem_context(&pctx);
1002                         fix_problem(ctx, PR_1_DUP_BLOCKS_PREENSTOP, &pctx);
1003                 }
1004                 e2fsck_pass1_dupblocks(ctx, block_buf);
1005         }
1006         ext2fs_free_mem(&inodes_to_process);
1007 endit:
1008         e2fsck_use_inode_shortcuts(ctx, 0);
1009
1010         ext2fs_free_mem(&block_buf);
1011         ext2fs_free_mem(&inode);
1012
1013 #ifdef RESOURCE_TRACK
1014         if (ctx->options & E2F_OPT_TIME2) {
1015                 e2fsck_clear_progbar(ctx);
1016                 print_resource_track(_("Pass 1"), &rtrack);
1017         }
1018 #endif
1019 }
1020
1021 /*
1022  * When the inode_scan routines call this callback at the end of the
1023  * glock group, call process_inodes.
1024  */
1025 static errcode_t scan_callback(ext2_filsys fs,
1026                                ext2_inode_scan scan EXT2FS_ATTR((unused)),
1027                                dgrp_t group, void * priv_data)
1028 {
1029         struct scan_callback_struct *scan_struct;
1030         e2fsck_t ctx;
1031
1032         scan_struct = (struct scan_callback_struct *) priv_data;
1033         ctx = scan_struct->ctx;
1034
1035         process_inodes((e2fsck_t) fs->priv_data, scan_struct->block_buf);
1036
1037         if (ctx->progress)
1038                 if ((ctx->progress)(ctx, 1, group+1,
1039                                     ctx->fs->group_desc_count))
1040                         return EXT2_ET_CANCEL_REQUESTED;
1041
1042         return 0;
1043 }
1044
1045 /*
1046  * Process the inodes in the "inodes to process" list.
1047  */
1048 static void process_inodes(e2fsck_t ctx, char *block_buf)
1049 {
1050         int                     i;
1051         struct ext2_inode       *old_stashed_inode;
1052         ext2_ino_t              old_stashed_ino;
1053         const char              *old_operation;
1054         char                    buf[80];
1055         struct problem_context  pctx;
1056
1057 #if 0
1058         printf("begin process_inodes: ");
1059 #endif
1060         if (process_inode_count == 0)
1061                 return;
1062         old_operation = ehandler_operation(0);
1063         old_stashed_inode = ctx->stashed_inode;
1064         old_stashed_ino = ctx->stashed_ino;
1065         qsort(inodes_to_process, process_inode_count,
1066                       sizeof(struct process_inode_block), process_inode_cmp);
1067         clear_problem_context(&pctx);
1068         for (i=0; i < process_inode_count; i++) {
1069                 pctx.inode = ctx->stashed_inode = &inodes_to_process[i].inode;
1070                 pctx.ino = ctx->stashed_ino = inodes_to_process[i].ino;
1071
1072 #if 0
1073                 printf("%u ", pctx.ino);
1074 #endif
1075                 sprintf(buf, _("reading indirect blocks of inode %u"),
1076                         pctx.ino);
1077                 ehandler_operation(buf);
1078                 check_blocks(ctx, &pctx, block_buf);
1079                 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
1080                         break;
1081         }
1082         ctx->stashed_inode = old_stashed_inode;
1083         ctx->stashed_ino = old_stashed_ino;
1084         process_inode_count = 0;
1085 #if 0
1086         printf("end process inodes\n");
1087 #endif
1088         ehandler_operation(old_operation);
1089 }
1090
1091 static EXT2_QSORT_TYPE process_inode_cmp(const void *a, const void *b)
1092 {
1093         const struct process_inode_block *ib_a =
1094                 (const struct process_inode_block *) a;
1095         const struct process_inode_block *ib_b =
1096                 (const struct process_inode_block *) b;
1097         int     ret;
1098
1099         ret = (ib_a->inode.i_block[EXT2_IND_BLOCK] -
1100                ib_b->inode.i_block[EXT2_IND_BLOCK]);
1101         if (ret == 0)
1102                 ret = ib_a->inode.i_file_acl - ib_b->inode.i_file_acl;
1103         return ret;
1104 }
1105
1106 /*
1107  * Mark an inode as being bad in some what
1108  */
1109 static void mark_inode_bad(e2fsck_t ctx, ino_t ino)
1110 {
1111         struct          problem_context pctx;
1112
1113         if (!ctx->inode_bad_map) {
1114                 clear_problem_context(&pctx);
1115
1116                 pctx.errcode = ext2fs_allocate_inode_bitmap(ctx->fs,
1117                             _("bad inode map"), &ctx->inode_bad_map);
1118                 if (pctx.errcode) {
1119                         pctx.num = 3;
1120                         fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
1121                         /* Should never get here */
1122                         ctx->flags |= E2F_FLAG_ABORT;
1123                         return;
1124                 }
1125         }
1126         ext2fs_mark_inode_bitmap(ctx->inode_bad_map, ino);
1127 }
1128
1129
1130 /*
1131  * This procedure will allocate the inode "bb" (badblock) map table
1132  */
1133 static void alloc_bb_map(e2fsck_t ctx)
1134 {
1135         struct          problem_context pctx;
1136
1137         clear_problem_context(&pctx);
1138         pctx.errcode = ext2fs_allocate_inode_bitmap(ctx->fs,
1139                                               _("inode in bad block map"),
1140                                               &ctx->inode_bb_map);
1141         if (pctx.errcode) {
1142                 pctx.num = 4;
1143                 fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
1144                 /* Should never get here */
1145                 ctx->flags |= E2F_FLAG_ABORT;
1146                 return;
1147         }
1148 }
1149
1150 /*
1151  * This procedure will allocate the inode imagic table
1152  */
1153 static void alloc_imagic_map(e2fsck_t ctx)
1154 {
1155         struct          problem_context pctx;
1156
1157         clear_problem_context(&pctx);
1158         pctx.errcode = ext2fs_allocate_inode_bitmap(ctx->fs,
1159                                               _("imagic inode map"),
1160                                               &ctx->inode_imagic_map);
1161         if (pctx.errcode) {
1162                 pctx.num = 5;
1163                 fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
1164                 /* Should never get here */
1165                 ctx->flags |= E2F_FLAG_ABORT;
1166                 return;
1167         }
1168 }
1169
1170 /*
1171  * Marks a block as in use, setting the dup_map if it's been set
1172  * already.  Called by process_block and process_bad_block.
1173  *
1174  * WARNING: Assumes checks have already been done to make sure block
1175  * is valid.  This is true in both process_block and process_bad_block.
1176  */
1177 static _INLINE_ void mark_block_used(e2fsck_t ctx, blk_t block)
1178 {
1179         struct          problem_context pctx;
1180
1181         clear_problem_context(&pctx);
1182
1183         if (ext2fs_fast_test_block_bitmap(ctx->block_found_map, block)) {
1184                 if (!ctx->block_dup_map) {
1185                         pctx.errcode = ext2fs_allocate_block_bitmap(ctx->fs,
1186                               _("multiply claimed block map"),
1187                               &ctx->block_dup_map);
1188                         if (pctx.errcode) {
1189                                 pctx.num = 3;
1190                                 fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR,
1191                                             &pctx);
1192                                 /* Should never get here */
1193                                 ctx->flags |= E2F_FLAG_ABORT;
1194                                 return;
1195                         }
1196                 }
1197                 ext2fs_fast_mark_block_bitmap(ctx->block_dup_map, block);
1198         } else {
1199                 ext2fs_fast_mark_block_bitmap(ctx->block_found_map, block);
1200         }
1201 }
1202
1203 /*
1204  * Adjust the extended attribute block's reference counts at the end
1205  * of pass 1, either by subtracting out references for EA blocks that
1206  * are still referenced in ctx->refcount, or by adding references for
1207  * EA blocks that had extra references as accounted for in
1208  * ctx->refcount_extra.
1209  */
1210 static void adjust_extattr_refcount(e2fsck_t ctx, ext2_refcount_t refcount,
1211                                     char *block_buf, int adjust_sign)
1212 {
1213         struct ext2_ext_attr_header     *header;
1214         struct problem_context          pctx;
1215         ext2_filsys                     fs = ctx->fs;
1216         blk_t                           blk;
1217         __u32                           should_be;
1218         int                             count;
1219
1220         clear_problem_context(&pctx);
1221
1222         ea_refcount_intr_begin(refcount);
1223         while (1) {
1224                 if ((blk = ea_refcount_intr_next(refcount, &count)) == 0)
1225                         break;
1226                 pctx.blk = blk;
1227                 pctx.errcode = ext2fs_read_ext_attr(fs, blk, block_buf);
1228                 if (pctx.errcode) {
1229                         fix_problem(ctx, PR_1_EXTATTR_READ_ABORT, &pctx);
1230                         return;
1231                 }
1232                 header = (struct ext2_ext_attr_header *) block_buf;
1233                 pctx.blkcount = header->h_refcount;
1234                 should_be = header->h_refcount + adjust_sign * count;
1235                 pctx.num = should_be;
1236                 if (fix_problem(ctx, PR_1_EXTATTR_REFCOUNT, &pctx)) {
1237                         header->h_refcount = should_be;
1238                         pctx.errcode = ext2fs_write_ext_attr(fs, blk,
1239                                                              block_buf);
1240                         if (pctx.errcode) {
1241                                 fix_problem(ctx, PR_1_EXTATTR_WRITE, &pctx);
1242                                 continue;
1243                         }
1244                 }
1245         }
1246 }
1247
1248 /*
1249  * Handle processing the extended attribute blocks
1250  */
1251 static int check_ext_attr(e2fsck_t ctx, struct problem_context *pctx,
1252                            char *block_buf)
1253 {
1254         ext2_filsys fs = ctx->fs;
1255         ext2_ino_t      ino = pctx->ino;
1256         struct ext2_inode *inode = pctx->inode;
1257         blk_t           blk;
1258         char *          end;
1259         struct ext2_ext_attr_header *header;
1260         struct ext2_ext_attr_entry *entry;
1261         int             count;
1262         region_t        region = 0;
1263
1264         blk = inode->i_file_acl;
1265         if (blk == 0)
1266                 return 0;
1267
1268         /*
1269          * If the Extended attribute flag isn't set, then a non-zero
1270          * file acl means that the inode is corrupted.
1271          *
1272          * Or if the extended attribute block is an invalid block,
1273          * then the inode is also corrupted.
1274          */
1275         if (!(fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_EXT_ATTR) ||
1276             (blk < fs->super->s_first_data_block) ||
1277             (blk >= fs->super->s_blocks_count)) {
1278                 mark_inode_bad(ctx, ino);
1279                 return 0;
1280         }
1281
1282         /* If ea bitmap hasn't been allocated, create it */
1283         if (!ctx->block_ea_map) {
1284                 pctx->errcode = ext2fs_allocate_block_bitmap(fs,
1285                                                       _("ext attr block map"),
1286                                                       &ctx->block_ea_map);
1287                 if (pctx->errcode) {
1288                         pctx->num = 2;
1289                         fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR, pctx);
1290                         ctx->flags |= E2F_FLAG_ABORT;
1291                         return 0;
1292                 }
1293         }
1294
1295         /* Create the EA refcount structure if necessary */
1296         if (!ctx->refcount) {
1297                 pctx->errcode = ea_refcount_create(0, &ctx->refcount);
1298                 if (pctx->errcode) {
1299                         pctx->num = 1;
1300                         fix_problem(ctx, PR_1_ALLOCATE_REFCOUNT, pctx);
1301                         ctx->flags |= E2F_FLAG_ABORT;
1302                         return 0;
1303                 }
1304         }
1305
1306 #if 0
1307         /* Debugging text */
1308         printf("Inode %u has EA block %u\n", ino, blk);
1309 #endif
1310
1311         /* Have we seen this EA block before? */
1312         if (ext2fs_fast_test_block_bitmap(ctx->block_ea_map, blk)) {
1313                 if (ea_refcount_decrement(ctx->refcount, blk, 0) == 0)
1314                         return 1;
1315                 /* Ooops, this EA was referenced more than it stated */
1316                 if (!ctx->refcount_extra) {
1317                         pctx->errcode = ea_refcount_create(0,
1318                                            &ctx->refcount_extra);
1319                         if (pctx->errcode) {
1320                                 pctx->num = 2;
1321                                 fix_problem(ctx, PR_1_ALLOCATE_REFCOUNT, pctx);
1322                                 ctx->flags |= E2F_FLAG_ABORT;
1323                                 return 0;
1324                         }
1325                 }
1326                 ea_refcount_increment(ctx->refcount_extra, blk, 0);
1327                 return 1;
1328         }
1329
1330         /*
1331          * OK, we haven't seen this EA block yet.  So we need to
1332          * validate it
1333          */
1334         pctx->blk = blk;
1335         pctx->errcode = ext2fs_read_ext_attr(fs, blk, block_buf);
1336         if (pctx->errcode && fix_problem(ctx, PR_1_READ_EA_BLOCK, pctx))
1337                 goto clear_extattr;
1338         header = (struct ext2_ext_attr_header *) block_buf;
1339         pctx->blk = inode->i_file_acl;
1340         if (((ctx->ext_attr_ver == 1) &&
1341              (header->h_magic != EXT2_EXT_ATTR_MAGIC_v1)) ||
1342             ((ctx->ext_attr_ver == 2) &&
1343              (header->h_magic != EXT2_EXT_ATTR_MAGIC))) {
1344                 if (fix_problem(ctx, PR_1_BAD_EA_BLOCK, pctx))
1345                         goto clear_extattr;
1346         }
1347
1348         if (header->h_blocks != 1) {
1349                 if (fix_problem(ctx, PR_1_EA_MULTI_BLOCK, pctx))
1350                         goto clear_extattr;
1351         }
1352
1353         region = region_create(0, fs->blocksize);
1354         if (!region) {
1355                 fix_problem(ctx, PR_1_EA_ALLOC_REGION, pctx);
1356                 ctx->flags |= E2F_FLAG_ABORT;
1357                 return 0;
1358         }
1359         if (region_allocate(region, 0, sizeof(struct ext2_ext_attr_header))) {
1360                 if (fix_problem(ctx, PR_1_EA_ALLOC_COLLISION, pctx))
1361                         goto clear_extattr;
1362         }
1363
1364         entry = (struct ext2_ext_attr_entry *)(header+1);
1365         end = block_buf + fs->blocksize;
1366         while ((char *)entry < end && *(__u32 *)entry) {
1367                 if (region_allocate(region, (char *)entry - (char *)header,
1368                                    EXT2_EXT_ATTR_LEN(entry->e_name_len))) {
1369                         if (fix_problem(ctx, PR_1_EA_ALLOC_COLLISION, pctx))
1370                                 goto clear_extattr;
1371                 }
1372                 if ((ctx->ext_attr_ver == 1 &&
1373                      (entry->e_name_len == 0 || entry->e_name_index != 0)) ||
1374                     (ctx->ext_attr_ver == 2 &&
1375                      entry->e_name_index == 0)) {
1376                         if (fix_problem(ctx, PR_1_EA_BAD_NAME, pctx))
1377                                 goto clear_extattr;
1378                 }
1379                 if (entry->e_value_block != 0) {
1380                         if (fix_problem(ctx, PR_1_EA_BAD_VALUE, pctx))
1381                                 goto clear_extattr;
1382                 }
1383                 if (entry->e_value_offs + entry->e_value_size > fs->blocksize) {
1384                         if (fix_problem(ctx, PR_1_EA_BAD_VALUE, pctx))
1385                                 goto clear_extattr;
1386                         break;
1387                 }
1388                 if (entry->e_value_size &&
1389                     region_allocate(region, entry->e_value_offs,
1390                                     EXT2_EXT_ATTR_SIZE(entry->e_value_size))) {
1391                         if (fix_problem(ctx, PR_1_EA_ALLOC_COLLISION, pctx))
1392                                 goto clear_extattr;
1393                 }
1394                 entry = EXT2_EXT_ATTR_NEXT(entry);
1395         }
1396         if (region_allocate(region, (char *)entry - (char *)header, 4)) {
1397                 if (fix_problem(ctx, PR_1_EA_ALLOC_COLLISION, pctx))
1398                         goto clear_extattr;
1399         }
1400         region_free(region);
1401
1402         count = header->h_refcount - 1;
1403         if (count)
1404                 ea_refcount_store(ctx->refcount, blk, count);
1405         mark_block_used(ctx, blk);
1406         ext2fs_fast_mark_block_bitmap(ctx->block_ea_map, blk);
1407         return 1;
1408
1409 clear_extattr:
1410         if (region)
1411                 region_free(region);
1412         inode->i_file_acl = 0;
1413         e2fsck_write_inode(ctx, ino, inode, "check_ext_attr");
1414         return 0;
1415 }
1416
1417 /* Returns 1 if bad htree, 0 if OK */
1418 static int handle_htree(e2fsck_t ctx, struct problem_context *pctx,
1419                         ext2_ino_t ino EXT2FS_ATTR((unused)),
1420                         struct ext2_inode *inode,
1421                         char *block_buf)
1422 {
1423         struct ext2_dx_root_info        *root;
1424         ext2_filsys                     fs = ctx->fs;
1425         errcode_t                       retval;
1426         blk_t                           blk;
1427
1428         if ((!LINUX_S_ISDIR(inode->i_mode) &&
1429              fix_problem(ctx, PR_1_HTREE_NODIR, pctx)) ||
1430             (!(fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) &&
1431              fix_problem(ctx, PR_1_HTREE_SET, pctx)))
1432                 return 1;
1433
1434         blk = inode->i_block[0];
1435         if (((blk == 0) ||
1436              (blk < fs->super->s_first_data_block) ||
1437              (blk >= fs->super->s_blocks_count)) &&
1438             fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
1439                 return 1;
1440
1441         retval = io_channel_read_blk(fs->io, blk, 1, block_buf);
1442         if (retval && fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
1443                 return 1;
1444
1445         /* XXX should check that beginning matches a directory */
1446         root = (struct ext2_dx_root_info *) (block_buf + 24);
1447
1448         if ((root->reserved_zero || root->info_length < 8) &&
1449             fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
1450                 return 1;
1451
1452         pctx->num = root->hash_version;
1453         if ((root->hash_version != EXT2_HASH_LEGACY) &&
1454             (root->hash_version != EXT2_HASH_HALF_MD4) &&
1455             (root->hash_version != EXT2_HASH_TEA) &&
1456             fix_problem(ctx, PR_1_HTREE_HASHV, pctx))
1457                 return 1;
1458
1459         if ((root->unused_flags & EXT2_HASH_FLAG_INCOMPAT) &&
1460             fix_problem(ctx, PR_1_HTREE_INCOMPAT, pctx))
1461                 return 1;
1462
1463         pctx->num = root->indirect_levels;
1464         if ((root->indirect_levels > 1) &&
1465             fix_problem(ctx, PR_1_HTREE_DEPTH, pctx))
1466                 return 1;
1467
1468         return 0;
1469 }
1470
1471 /*
1472  * This subroutine is called on each inode to account for all of the
1473  * blocks used by that inode.
1474  */
1475 static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
1476                          char *block_buf)
1477 {
1478         ext2_filsys fs = ctx->fs;
1479         struct process_block_struct pb;
1480         ext2_ino_t      ino = pctx->ino;
1481         struct ext2_inode *inode = pctx->inode;
1482         int             bad_size = 0;
1483         int             dirty_inode = 0;
1484         __u64           size;
1485
1486         pb.ino = ino;
1487         pb.num_blocks = 0;
1488         pb.last_block = -1;
1489         pb.num_illegal_blocks = 0;
1490         pb.suppress = 0; pb.clear = 0;
1491         pb.fragmented = 0;
1492         pb.compressed = 0;
1493         pb.previous_block = 0;
1494         pb.is_dir = LINUX_S_ISDIR(inode->i_mode);
1495         pb.is_reg = LINUX_S_ISREG(inode->i_mode);
1496         pb.max_blocks = 1 << (31 - fs->super->s_log_block_size);
1497         pb.inode = inode;
1498         pb.pctx = pctx;
1499         pb.ctx = ctx;
1500         pctx->ino = ino;
1501         pctx->errcode = 0;
1502
1503         if (inode->i_flags & EXT2_COMPRBLK_FL) {
1504                 if (fs->super->s_feature_incompat &
1505                     EXT2_FEATURE_INCOMPAT_COMPRESSION)
1506                         pb.compressed = 1;
1507                 else {
1508                         if (fix_problem(ctx, PR_1_COMPR_SET, pctx)) {
1509                                 inode->i_flags &= ~EXT2_COMPRBLK_FL;
1510                                 dirty_inode++;
1511                         }
1512                 }
1513         }
1514
1515         if (inode->i_file_acl && check_ext_attr(ctx, pctx, block_buf))
1516                 pb.num_blocks++;
1517
1518         if (ext2fs_inode_has_valid_blocks(inode))
1519                 pctx->errcode = ext2fs_block_iterate2(fs, ino,
1520                                        pb.is_dir ? BLOCK_FLAG_HOLE : 0,
1521                                        block_buf, process_block, &pb);
1522         end_problem_latch(ctx, PR_LATCH_BLOCK);
1523         end_problem_latch(ctx, PR_LATCH_TOOBIG);
1524         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
1525                 goto out;
1526         if (pctx->errcode)
1527                 fix_problem(ctx, PR_1_BLOCK_ITERATE, pctx);
1528
1529         if (pb.fragmented && pb.num_blocks < fs->super->s_blocks_per_group)
1530                 ctx->fs_fragmented++;
1531
1532         if (pb.clear) {
1533                 inode->i_links_count = 0;
1534                 ext2fs_icount_store(ctx->inode_link_info, ino, 0);
1535                 inode->i_dtime = ctx->now;
1536                 dirty_inode++;
1537                 ext2fs_unmark_inode_bitmap(ctx->inode_dir_map, ino);
1538                 ext2fs_unmark_inode_bitmap(ctx->inode_reg_map, ino);
1539                 ext2fs_unmark_inode_bitmap(ctx->inode_used_map, ino);
1540                 /*
1541                  * The inode was probably partially accounted for
1542                  * before processing was aborted, so we need to
1543                  * restart the pass 1 scan.
1544                  */
1545                 ctx->flags |= E2F_FLAG_RESTART;
1546                 goto out;
1547         }
1548
1549         if (pb.is_dir) {
1550                 while (1) {
1551                         struct ext2_db_entry *entry;
1552
1553                         if (ext2fs_dblist_get_last(fs->dblist, &entry) ||
1554                             (entry->ino != ino) ||
1555                             (entry->blk != 0) ||
1556                             (entry->blockcnt == 0))
1557                                 break;
1558                         /* printf("Dropping ino %lu blk %lu blockcnt %d\n",
1559                                   entry->ino, entry->blk, entry->blockcnt); */
1560                         ext2fs_dblist_drop_last(fs->dblist);
1561                         if (ext2fs_dblist_get_last(fs->dblist, &entry) ||
1562                             (entry->ino != ino))
1563                                 pb.last_block--;
1564                         else
1565                                 pb.last_block = entry->blockcnt;
1566                 }
1567         }
1568
1569         if (inode->i_flags & EXT2_INDEX_FL) {
1570                 if (handle_htree(ctx, pctx, ino, inode, block_buf)) {
1571                         inode->i_flags &= ~EXT2_INDEX_FL;
1572                         dirty_inode++;
1573                 } else {
1574 #ifdef ENABLE_HTREE
1575                         e2fsck_add_dx_dir(ctx, ino, pb.last_block+1);
1576 #endif
1577                 }
1578         }
1579         if (ctx->dirs_to_hash && pb.is_dir &&
1580             !(inode->i_flags & EXT2_INDEX_FL) &&
1581             ((inode->i_size / fs->blocksize) >= 3))
1582                 ext2fs_u32_list_add(ctx->dirs_to_hash, ino);
1583
1584         if (!pb.num_blocks && pb.is_dir) {
1585                 if (fix_problem(ctx, PR_1_ZERO_LENGTH_DIR, pctx)) {
1586                         inode->i_links_count = 0;
1587                         ext2fs_icount_store(ctx->inode_link_info, ino, 0);
1588                         inode->i_dtime = ctx->now;
1589                         dirty_inode++;
1590                         ext2fs_unmark_inode_bitmap(ctx->inode_dir_map, ino);
1591                         ext2fs_unmark_inode_bitmap(ctx->inode_reg_map, ino);
1592                         ext2fs_unmark_inode_bitmap(ctx->inode_used_map, ino);
1593                         ctx->fs_directory_count--;
1594                         goto out;
1595                 }
1596         }
1597
1598         pb.num_blocks *= (fs->blocksize / 512);
1599 #if 0
1600         printf("inode %u, i_size = %lu, last_block = %lld, i_blocks=%lu, num_blocks = %lu\n",
1601                ino, inode->i_size, pb.last_block, inode->i_blocks,
1602                pb.num_blocks);
1603 #endif
1604         if (pb.is_dir) {
1605                 int nblock = inode->i_size >> EXT2_BLOCK_SIZE_BITS(fs->super);
1606                 if (inode->i_size & (fs->blocksize - 1))
1607                         bad_size = 5;
1608                 else if (nblock > (pb.last_block + 1))
1609                         bad_size = 1;
1610                 else if (nblock < (pb.last_block + 1)) {
1611                         if (((pb.last_block + 1) - nblock) >
1612                             fs->super->s_prealloc_dir_blocks)
1613                                 bad_size = 2;
1614                 }
1615         } else {
1616                 e2_blkcnt_t blkpg = ctx->blocks_per_page;
1617
1618                 size = EXT2_I_SIZE(inode);
1619                 if ((pb.last_block >= 0) &&
1620                     /* allow allocated blocks to end of PAGE_SIZE */
1621                     (size < (__u64)pb.last_block * fs->blocksize) &&
1622                     (pb.last_block / blkpg * blkpg != pb.last_block ||
1623                      size < (__u64)(pb.last_block & ~(blkpg-1)) *fs->blocksize))
1624                         bad_size = 3;
1625                 else if (size > ext2_max_sizes[fs->super->s_log_block_size])
1626                         bad_size = 4;
1627         }
1628         /* i_size for symlinks is checked elsewhere */
1629         if (bad_size && !LINUX_S_ISLNK(inode->i_mode)) {
1630                 pctx->num = (pb.last_block+1) * fs->blocksize;
1631                 if (fix_problem(ctx, PR_1_BAD_I_SIZE, pctx)) {
1632                         inode->i_size = pctx->num;
1633                         if (!LINUX_S_ISDIR(inode->i_mode))
1634                                 inode->i_size_high = pctx->num >> 32;
1635                         dirty_inode++;
1636                 }
1637                 pctx->num = 0;
1638         }
1639         if (LINUX_S_ISREG(inode->i_mode) &&
1640             (inode->i_size_high || inode->i_size & 0x80000000UL))
1641                 ctx->large_files++;
1642         if (pb.num_blocks != inode->i_blocks) {
1643                 pctx->num = pb.num_blocks;
1644                 if (fix_problem(ctx, PR_1_BAD_I_BLOCKS, pctx)) {
1645                         inode->i_blocks = pb.num_blocks;
1646                         dirty_inode++;
1647                 }
1648                 pctx->num = 0;
1649         }
1650 out:
1651         if (dirty_inode)
1652                 e2fsck_write_inode(ctx, ino, inode, "check_blocks");
1653 }
1654
1655 #if 0
1656 /*
1657  * Helper function called by process block when an illegal block is
1658  * found.  It returns a description about why the block is illegal
1659  */
1660 static char *describe_illegal_block(ext2_filsys fs, blk_t block)
1661 {
1662         blk_t   super;
1663         int     i;
1664         static char     problem[80];
1665
1666         super = fs->super->s_first_data_block;
1667         strcpy(problem, "PROGRAMMING ERROR: Unknown reason for illegal block");
1668         if (block < super) {
1669                 sprintf(problem, "< FIRSTBLOCK (%u)", super);
1670                 return(problem);
1671         } else if (block >= fs->super->s_blocks_count) {
1672                 sprintf(problem, "> BLOCKS (%u)", fs->super->s_blocks_count);
1673                 return(problem);
1674         }
1675         for (i = 0; i < fs->group_desc_count; i++) {
1676                 if (block == super) {
1677                         sprintf(problem, "is the superblock in group %d", i);
1678                         break;
1679                 }
1680                 if (block > super &&
1681                     block <= (super + fs->desc_blocks)) {
1682                         sprintf(problem, "is in the group descriptors "
1683                                 "of group %d", i);
1684                         break;
1685                 }
1686                 if (block == fs->group_desc[i].bg_block_bitmap) {
1687                         sprintf(problem, "is the block bitmap of group %d", i);
1688                         break;
1689                 }
1690                 if (block == fs->group_desc[i].bg_inode_bitmap) {
1691                         sprintf(problem, "is the inode bitmap of group %d", i);
1692                         break;
1693                 }
1694                 if (block >= fs->group_desc[i].bg_inode_table &&
1695                     (block < fs->group_desc[i].bg_inode_table
1696                      + fs->inode_blocks_per_group)) {
1697                         sprintf(problem, "is in the inode table of group %d",
1698                                 i);
1699                         break;
1700                 }
1701                 super += fs->super->s_blocks_per_group;
1702         }
1703         return(problem);
1704 }
1705 #endif
1706
1707 /*
1708  * This is a helper function for check_blocks().
1709  */
1710 static int process_block(ext2_filsys fs,
1711                   blk_t *block_nr,
1712                   e2_blkcnt_t blockcnt,
1713                   blk_t ref_block EXT2FS_ATTR((unused)),
1714                   int ref_offset EXT2FS_ATTR((unused)),
1715                   void *priv_data)
1716 {
1717         struct process_block_struct *p;
1718         struct problem_context *pctx;
1719         blk_t   blk = *block_nr;
1720         int     ret_code = 0;
1721         int     problem = 0;
1722         e2fsck_t        ctx;
1723
1724         p = (struct process_block_struct *) priv_data;
1725         pctx = p->pctx;
1726         ctx = p->ctx;
1727
1728         if (p->compressed && (blk == EXT2FS_COMPRESSED_BLKADDR)) {
1729                 /* todo: Check that the comprblk_fl is high, that the
1730                    blkaddr pattern looks right (all non-holes up to
1731                    first EXT2FS_COMPRESSED_BLKADDR, then all
1732                    EXT2FS_COMPRESSED_BLKADDR up to end of cluster),
1733                    that the feature_incompat bit is high, and that the
1734                    inode is a regular file.  If we're doing a "full
1735                    check" (a concept introduced to e2fsck by e2compr,
1736                    meaning that we look at data blocks as well as
1737                    metadata) then call some library routine that
1738                    checks the compressed data.  I'll have to think
1739                    about this, because one particularly important
1740                    problem to be able to fix is to recalculate the
1741                    cluster size if necessary.  I think that perhaps
1742                    we'd better do most/all e2compr-specific checks
1743                    separately, after the non-e2compr checks.  If not
1744                    doing a full check, it may be useful to test that
1745                    the personality is linux; e.g. if it isn't then
1746                    perhaps this really is just an illegal block. */
1747                 return 0;
1748         }
1749
1750         if (blk == 0) {
1751                 if (p->is_dir == 0) {
1752                         /*
1753                          * Should never happen, since only directories
1754                          * get called with BLOCK_FLAG_HOLE
1755                          */
1756 #if DEBUG_E2FSCK
1757                         printf("process_block() called with blk == 0, "
1758                                "blockcnt=%d, inode %lu???\n",
1759                                blockcnt, p->ino);
1760 #endif
1761                         return 0;
1762                 }
1763                 if (blockcnt < 0)
1764                         return 0;
1765                 if (blockcnt * fs->blocksize < p->inode->i_size) {
1766 #if 0
1767                         printf("Missing block (#%d) in directory inode %lu!\n",
1768                                blockcnt, p->ino);
1769 #endif
1770                         p->last_block = blockcnt;
1771                         goto mark_dir;
1772                 }
1773                 return 0;
1774         }
1775
1776 #if 0
1777         printf("Process_block, inode %lu, block %u, #%d\n", p->ino, blk,
1778                blockcnt);
1779 #endif
1780
1781         /*
1782          * Simplistic fragmentation check.  We merely require that the
1783          * file be contiguous.  (Which can never be true for really
1784          * big files that are greater than a block group.)
1785          */
1786         if (!HOLE_BLKADDR(p->previous_block)) {
1787                 if (p->previous_block+1 != blk)
1788                         p->fragmented = 1;
1789         }
1790         p->previous_block = blk;
1791
1792         if (p->is_dir && blockcnt > (1 << (21 - fs->super->s_log_block_size)))
1793                 problem = PR_1_TOOBIG_DIR;
1794         if (p->is_reg && p->num_blocks+1 >= p->max_blocks)
1795                 problem = PR_1_TOOBIG_REG;
1796         if (!p->is_dir && !p->is_reg && blockcnt > 0)
1797                 problem = PR_1_TOOBIG_SYMLINK;
1798
1799         if (blk < fs->super->s_first_data_block ||
1800             blk >= fs->super->s_blocks_count)
1801                 problem = PR_1_ILLEGAL_BLOCK_NUM;
1802
1803         if (problem) {
1804                 p->num_illegal_blocks++;
1805                 if (!p->suppress && (p->num_illegal_blocks % 12) == 0) {
1806                         if (fix_problem(ctx, PR_1_TOO_MANY_BAD_BLOCKS, pctx)) {
1807                                 p->clear = 1;
1808                                 return BLOCK_ABORT;
1809                         }
1810                         if (fix_problem(ctx, PR_1_SUPPRESS_MESSAGES, pctx)) {
1811                                 p->suppress = 1;
1812                                 set_latch_flags(PR_LATCH_BLOCK,
1813                                                 PRL_SUPPRESS, 0);
1814                         }
1815                 }
1816                 pctx->blk = blk;
1817                 pctx->blkcount = blockcnt;
1818                 if (fix_problem(ctx, problem, pctx)) {
1819                         blk = *block_nr = 0;
1820                         ret_code = BLOCK_CHANGED;
1821                         goto mark_dir;
1822                 } else
1823                         return 0;
1824         }
1825
1826         if (p->ino == EXT2_RESIZE_INO) {
1827                 /*
1828                  * The resize inode has already be sanity checked
1829                  * during pass #0 (the superblock checks).  All we
1830                  * have to do is mark the double indirect block as
1831                  * being in use; all of the other blocks are handled
1832                  * by mark_table_blocks()).
1833                  */
1834                 if (blockcnt == BLOCK_COUNT_DIND)
1835                         mark_block_used(ctx, blk);
1836         } else
1837                 mark_block_used(ctx, blk);
1838         p->num_blocks++;
1839         if (blockcnt >= 0)
1840                 p->last_block = blockcnt;
1841 mark_dir:
1842         if (p->is_dir && (blockcnt >= 0)) {
1843                 pctx->errcode = ext2fs_add_dir_block(fs->dblist, p->ino,
1844                                                     blk, blockcnt);
1845                 if (pctx->errcode) {
1846                         pctx->blk = blk;
1847                         pctx->num = blockcnt;
1848                         fix_problem(ctx, PR_1_ADD_DBLOCK, pctx);
1849                         /* Should never get here */
1850                         ctx->flags |= E2F_FLAG_ABORT;
1851                         return BLOCK_ABORT;
1852                 }
1853         }
1854         return ret_code;
1855 }
1856
1857 static int process_bad_block(ext2_filsys fs,
1858                       blk_t *block_nr,
1859                       e2_blkcnt_t blockcnt,
1860                       blk_t ref_block EXT2FS_ATTR((unused)),
1861                       int ref_offset EXT2FS_ATTR((unused)),
1862                       void *priv_data)
1863 {
1864         struct process_block_struct *p;
1865         blk_t           blk = *block_nr;
1866         blk_t           first_block;
1867         dgrp_t          i;
1868         struct problem_context *pctx;
1869         e2fsck_t        ctx;
1870
1871         /*
1872          * Note: This function processes blocks for the bad blocks
1873          * inode, which is never compressed.  So we don't use HOLE_BLKADDR().
1874          */
1875
1876         if (!blk)
1877                 return 0;
1878
1879         p = (struct process_block_struct *) priv_data;
1880         ctx = p->ctx;
1881         pctx = p->pctx;
1882
1883         pctx->ino = EXT2_BAD_INO;
1884         pctx->blk = blk;
1885         pctx->blkcount = blockcnt;
1886
1887         if ((blk < fs->super->s_first_data_block) ||
1888             (blk >= fs->super->s_blocks_count)) {
1889                 if (fix_problem(ctx, PR_1_BB_ILLEGAL_BLOCK_NUM, pctx)) {
1890                         *block_nr = 0;
1891                         return BLOCK_CHANGED;
1892                 } else
1893                         return 0;
1894         }
1895
1896         if (blockcnt < 0) {
1897                 if (ext2fs_test_block_bitmap(p->fs_meta_blocks, blk)) {
1898                         p->bbcheck = 1;
1899                         if (fix_problem(ctx, PR_1_BB_FS_BLOCK, pctx)) {
1900                                 *block_nr = 0;
1901                                 return BLOCK_CHANGED;
1902                         }
1903                 } else if (ext2fs_test_block_bitmap(ctx->block_found_map,
1904                                                     blk)) {
1905                         p->bbcheck = 1;
1906                         if (fix_problem(ctx, PR_1_BBINODE_BAD_METABLOCK,
1907                                         pctx)) {
1908                                 *block_nr = 0;
1909                                 return BLOCK_CHANGED;
1910                         }
1911                         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
1912                                 return BLOCK_ABORT;
1913                 } else
1914                         mark_block_used(ctx, blk);
1915                 return 0;
1916         }
1917 #if 0
1918         printf ("DEBUG: Marking %u as bad.\n", blk);
1919 #endif
1920         ctx->fs_badblocks_count++;
1921         /*
1922          * If the block is not used, then mark it as used and return.
1923          * If it is already marked as found, this must mean that
1924          * there's an overlap between the filesystem table blocks
1925          * (bitmaps and inode table) and the bad block list.
1926          */
1927         if (!ext2fs_test_block_bitmap(ctx->block_found_map, blk)) {
1928                 ext2fs_mark_block_bitmap(ctx->block_found_map, blk);
1929                 return 0;
1930         }
1931         /*
1932          * Try to find the where the filesystem block was used...
1933          */
1934         first_block = fs->super->s_first_data_block;
1935
1936         for (i = 0; i < fs->group_desc_count; i++ ) {
1937                 pctx->group = i;
1938                 pctx->blk = blk;
1939                 if (!ext2fs_bg_has_super(fs, i))
1940                         goto skip_super;
1941                 if (blk == first_block) {
1942                         if (i == 0) {
1943                                 if (fix_problem(ctx,
1944                                                 PR_1_BAD_PRIMARY_SUPERBLOCK,
1945                                                 pctx)) {
1946                                         *block_nr = 0;
1947                                         return BLOCK_CHANGED;
1948                                 }
1949                                 return 0;
1950                         }
1951                         fix_problem(ctx, PR_1_BAD_SUPERBLOCK, pctx);
1952                         return 0;
1953                 }
1954                 if ((blk > first_block) &&
1955                     (blk <= first_block + fs->desc_blocks)) {
1956                         if (i == 0) {
1957                                 pctx->blk = *block_nr;
1958                                 if (fix_problem(ctx,
1959                         PR_1_BAD_PRIMARY_GROUP_DESCRIPTOR, pctx)) {
1960                                         *block_nr = 0;
1961                                         return BLOCK_CHANGED;
1962                                 }
1963                                 return 0;
1964                         }
1965                         fix_problem(ctx, PR_1_BAD_GROUP_DESCRIPTORS, pctx);
1966                         return 0;
1967                 }
1968         skip_super:
1969                 if (blk == fs->group_desc[i].bg_block_bitmap) {
1970                         if (fix_problem(ctx, PR_1_BB_BAD_BLOCK, pctx)) {
1971                                 ctx->invalid_block_bitmap_flag[i]++;
1972                                 ctx->invalid_bitmaps++;
1973                         }
1974                         return 0;
1975                 }
1976                 if (blk == fs->group_desc[i].bg_inode_bitmap) {
1977                         if (fix_problem(ctx, PR_1_IB_BAD_BLOCK, pctx)) {
1978                                 ctx->invalid_inode_bitmap_flag[i]++;
1979                                 ctx->invalid_bitmaps++;
1980                         }
1981                         return 0;
1982                 }
1983                 if ((blk >= fs->group_desc[i].bg_inode_table) &&
1984                     (blk < (fs->group_desc[i].bg_inode_table +
1985                             fs->inode_blocks_per_group))) {
1986                         /*
1987                          * If there are bad blocks in the inode table,
1988                          * the inode scan code will try to do
1989                          * something reasonable automatically.
1990                          */
1991                         return 0;
1992                 }
1993                 first_block += fs->super->s_blocks_per_group;
1994         }
1995         /*
1996          * If we've gotten to this point, then the only
1997          * possibility is that the bad block inode meta data
1998          * is using a bad block.
1999          */
2000         if ((blk == p->inode->i_block[EXT2_IND_BLOCK]) ||
2001             (blk == p->inode->i_block[EXT2_DIND_BLOCK]) ||
2002             (blk == p->inode->i_block[EXT2_TIND_BLOCK])) {
2003                 p->bbcheck = 1;
2004                 if (fix_problem(ctx, PR_1_BBINODE_BAD_METABLOCK, pctx)) {
2005                         *block_nr = 0;
2006                         return BLOCK_CHANGED;
2007                 }
2008                 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
2009                         return BLOCK_ABORT;
2010                 return 0;
2011         }
2012
2013         pctx->group = -1;
2014
2015         /* Warn user that the block wasn't claimed */
2016         fix_problem(ctx, PR_1_PROGERR_CLAIMED_BLOCK, pctx);
2017
2018         return 0;
2019 }
2020
2021 static void new_table_block(e2fsck_t ctx, blk_t first_block, int group,
2022                             const char *name, int num, blk_t *new_block)
2023 {
2024         ext2_filsys fs = ctx->fs;
2025         blk_t           old_block = *new_block;
2026         blk_t           last_block;
2027         int             i;
2028         char            *buf;
2029         struct problem_context  pctx;
2030
2031         clear_problem_context(&pctx);
2032
2033         pctx.group = group;
2034         pctx.blk = old_block;
2035         pctx.str = name;
2036
2037         last_block = ext2fs_group_last_block(fs, group);
2038         pctx.errcode = ext2fs_get_free_blocks(fs, first_block, last_block,
2039                                         num, ctx->block_found_map, new_block);
2040         if (pctx.errcode) {
2041                 pctx.num = num;
2042                 fix_problem(ctx, PR_1_RELOC_BLOCK_ALLOCATE, &pctx);
2043                 ext2fs_unmark_valid(fs);
2044                 return;
2045         }
2046         pctx.errcode = ext2fs_get_mem(fs->blocksize, &buf);
2047         if (pctx.errcode) {
2048                 fix_problem(ctx, PR_1_RELOC_MEMORY_ALLOCATE, &pctx);
2049                 ext2fs_unmark_valid(fs);
2050                 return;
2051         }
2052         ext2fs_mark_super_dirty(fs);
2053         fs->flags &= ~EXT2_FLAG_MASTER_SB_ONLY;
2054         pctx.blk2 = *new_block;
2055         fix_problem(ctx, (old_block ? PR_1_RELOC_FROM_TO :
2056                           PR_1_RELOC_TO), &pctx);
2057         pctx.blk2 = 0;
2058         for (i = 0; i < num; i++) {
2059                 pctx.blk = i;
2060                 ext2fs_mark_block_bitmap(ctx->block_found_map, (*new_block)+i);
2061                 if (old_block) {
2062                         pctx.errcode = io_channel_read_blk(fs->io,
2063                                    old_block + i, 1, buf);
2064                         if (pctx.errcode)
2065                                 fix_problem(ctx, PR_1_RELOC_READ_ERR, &pctx);
2066                 } else
2067                         memset(buf, 0, fs->blocksize);
2068
2069                 pctx.blk = (*new_block) + i;
2070                 pctx.errcode = io_channel_write_blk(fs->io, pctx.blk,
2071                                               1, buf);
2072                 if (pctx.errcode)
2073                         fix_problem(ctx, PR_1_RELOC_WRITE_ERR, &pctx);
2074         }
2075         ext2fs_free_mem(&buf);
2076 }
2077
2078 /*
2079  * This routine gets called at the end of pass 1 if bad blocks are
2080  * detected in the superblock, group descriptors, inode_bitmaps, or
2081  * block bitmaps.  At this point, all of the blocks have been mapped
2082  * out, so we can try to allocate new block(s) to replace the bad
2083  * blocks.
2084  */
2085 static void handle_fs_bad_blocks(e2fsck_t ctx)
2086 {
2087         ext2_filsys fs = ctx->fs;
2088         dgrp_t          i;
2089         blk_t           first_block;
2090
2091         for (i = 0; i < fs->group_desc_count; i++) {
2092                 first_block = ext2fs_group_first_block(fs, i);
2093
2094                 if (ctx->invalid_block_bitmap_flag[i]) {
2095                         new_table_block(ctx, first_block, i, _("block bitmap"),
2096                                         1, &fs->group_desc[i].bg_block_bitmap);
2097                 }
2098                 if (ctx->invalid_inode_bitmap_flag[i]) {
2099                         new_table_block(ctx, first_block, i, _("inode bitmap"),
2100                                         1, &fs->group_desc[i].bg_inode_bitmap);
2101                 }
2102                 if (ctx->invalid_inode_table_flag[i]) {
2103                         new_table_block(ctx, first_block, i, _("inode table"),
2104                                         fs->inode_blocks_per_group,
2105                                         &fs->group_desc[i].bg_inode_table);
2106                         ctx->flags |= E2F_FLAG_RESTART;
2107                 }
2108         }
2109         ctx->invalid_bitmaps = 0;
2110 }
2111
2112 /*
2113  * This routine marks all blocks which are used by the superblock,
2114  * group descriptors, inode bitmaps, and block bitmaps.
2115  */
2116 static void mark_table_blocks(e2fsck_t ctx)
2117 {
2118         ext2_filsys fs = ctx->fs;
2119         blk_t   b;
2120         dgrp_t  i;
2121         int     j;
2122         struct problem_context pctx;
2123
2124         clear_problem_context(&pctx);
2125
2126         for (i = 0; i < fs->group_desc_count; i++) {
2127                 pctx.group = i;
2128
2129                 ext2fs_reserve_super_and_bgd(fs, i, ctx->block_found_map);
2130
2131                 /*
2132                  * Mark the blocks used for the inode table
2133                  */
2134                 if (fs->group_desc[i].bg_inode_table) {
2135                         for (j = 0, b = fs->group_desc[i].bg_inode_table;
2136                              j < fs->inode_blocks_per_group;
2137                              j++, b++) {
2138                                 if (ext2fs_test_block_bitmap(ctx->block_found_map,
2139                                                              b)) {
2140                                         pctx.blk = b;
2141                                         if (fix_problem(ctx,
2142                                                 PR_1_ITABLE_CONFLICT, &pctx)) {
2143                                                 ctx->invalid_inode_table_flag[i]++;
2144                                                 ctx->invalid_bitmaps++;
2145                                         }
2146                                 } else {
2147                                     ext2fs_mark_block_bitmap(ctx->block_found_map,
2148                                                              b);
2149                                 }
2150                         }
2151                 }
2152
2153                 /*
2154                  * Mark block used for the block bitmap
2155                  */
2156                 if (fs->group_desc[i].bg_block_bitmap) {
2157                         if (ext2fs_test_block_bitmap(ctx->block_found_map,
2158                                      fs->group_desc[i].bg_block_bitmap)) {
2159                                 pctx.blk = fs->group_desc[i].bg_block_bitmap;
2160                                 if (fix_problem(ctx, PR_1_BB_CONFLICT, &pctx)) {
2161                                         ctx->invalid_block_bitmap_flag[i]++;
2162                                         ctx->invalid_bitmaps++;
2163                                 }
2164                         } else {
2165                             ext2fs_mark_block_bitmap(ctx->block_found_map,
2166                                      fs->group_desc[i].bg_block_bitmap);
2167                     }
2168
2169                 }
2170                 /*
2171                  * Mark block used for the inode bitmap
2172                  */
2173                 if (fs->group_desc[i].bg_inode_bitmap) {
2174                         if (ext2fs_test_block_bitmap(ctx->block_found_map,
2175                                      fs->group_desc[i].bg_inode_bitmap)) {
2176                                 pctx.blk = fs->group_desc[i].bg_inode_bitmap;
2177                                 if (fix_problem(ctx, PR_1_IB_CONFLICT, &pctx)) {
2178                                         ctx->invalid_inode_bitmap_flag[i]++;
2179                                         ctx->invalid_bitmaps++;
2180                                 }
2181                         } else {
2182                             ext2fs_mark_block_bitmap(ctx->block_found_map,
2183                                      fs->group_desc[i].bg_inode_bitmap);
2184                         }
2185                 }
2186         }
2187 }
2188
2189 /*
2190  * Thes subroutines short circuits ext2fs_get_blocks and
2191  * ext2fs_check_directory; we use them since we already have the inode
2192  * structure, so there's no point in letting the ext2fs library read
2193  * the inode again.
2194  */
2195 static errcode_t pass1_get_blocks(ext2_filsys fs, ext2_ino_t ino,
2196                                   blk_t *blocks)
2197 {
2198         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2199         int     i;
2200
2201         if ((ino != ctx->stashed_ino) || !ctx->stashed_inode)
2202                 return EXT2_ET_CALLBACK_NOTHANDLED;
2203
2204         for (i=0; i < EXT2_N_BLOCKS; i++)
2205                 blocks[i] = ctx->stashed_inode->i_block[i];
2206         return 0;
2207 }
2208
2209 static errcode_t pass1_read_inode(ext2_filsys fs, ext2_ino_t ino,
2210                                   struct ext2_inode *inode)
2211 {
2212         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2213
2214         if ((ino != ctx->stashed_ino) || !ctx->stashed_inode)
2215                 return EXT2_ET_CALLBACK_NOTHANDLED;
2216         *inode = *ctx->stashed_inode;
2217         return 0;
2218 }
2219
2220 static errcode_t pass1_write_inode(ext2_filsys fs, ext2_ino_t ino,
2221                             struct ext2_inode *inode)
2222 {
2223         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2224
2225         if ((ino == ctx->stashed_ino) && ctx->stashed_inode &&
2226                 (inode != ctx->stashed_inode))
2227                 *ctx->stashed_inode = *inode;
2228         return EXT2_ET_CALLBACK_NOTHANDLED;
2229 }
2230
2231 static errcode_t pass1_check_directory(ext2_filsys fs, ext2_ino_t ino)
2232 {
2233         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2234
2235         if ((ino != ctx->stashed_ino) || !ctx->stashed_inode)
2236                 return EXT2_ET_CALLBACK_NOTHANDLED;
2237
2238         if (!LINUX_S_ISDIR(ctx->stashed_inode->i_mode))
2239                 return EXT2_ET_NO_DIRECTORY;
2240         return 0;
2241 }
2242
2243 void e2fsck_use_inode_shortcuts(e2fsck_t ctx, int bool)
2244 {
2245         ext2_filsys fs = ctx->fs;
2246
2247         if (bool) {
2248                 fs->get_blocks = pass1_get_blocks;
2249                 fs->check_directory = pass1_check_directory;
2250                 fs->read_inode = pass1_read_inode;
2251                 fs->write_inode = pass1_write_inode;
2252                 ctx->stashed_ino = 0;
2253         } else {
2254                 fs->get_blocks = 0;
2255                 fs->check_directory = 0;
2256                 fs->read_inode = 0;
2257                 fs->write_inode = 0;
2258         }
2259 }