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_size &&
1384                     region_allocate(region, entry->e_value_offs,
1385                                     EXT2_EXT_ATTR_SIZE(entry->e_value_size))) {
1386                         if (fix_problem(ctx, PR_1_EA_ALLOC_COLLISION, pctx))
1387                                 goto clear_extattr;
1388                 }
1389                 entry = EXT2_EXT_ATTR_NEXT(entry);
1390         }
1391         if (region_allocate(region, (char *)entry - (char *)header, 4)) {
1392                 if (fix_problem(ctx, PR_1_EA_ALLOC_COLLISION, pctx))
1393                         goto clear_extattr;
1394         }
1395         region_free(region);
1396
1397         count = header->h_refcount - 1;
1398         if (count)
1399                 ea_refcount_store(ctx->refcount, blk, count);
1400         mark_block_used(ctx, blk);
1401         ext2fs_fast_mark_block_bitmap(ctx->block_ea_map, blk);
1402         return 1;
1403
1404 clear_extattr:
1405         if (region)
1406                 region_free(region);
1407         inode->i_file_acl = 0;
1408         e2fsck_write_inode(ctx, ino, inode, "check_ext_attr");
1409         return 0;
1410 }
1411
1412 /* Returns 1 if bad htree, 0 if OK */
1413 static int handle_htree(e2fsck_t ctx, struct problem_context *pctx,
1414                         ext2_ino_t ino EXT2FS_ATTR((unused)),
1415                         struct ext2_inode *inode,
1416                         char *block_buf)
1417 {
1418         struct ext2_dx_root_info        *root;
1419         ext2_filsys                     fs = ctx->fs;
1420         errcode_t                       retval;
1421         blk_t                           blk;
1422
1423         if ((!LINUX_S_ISDIR(inode->i_mode) &&
1424              fix_problem(ctx, PR_1_HTREE_NODIR, pctx)) ||
1425             (!(fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) &&
1426              fix_problem(ctx, PR_1_HTREE_SET, pctx)))
1427                 return 1;
1428
1429         blk = inode->i_block[0];
1430         if (((blk == 0) ||
1431              (blk < fs->super->s_first_data_block) ||
1432              (blk >= fs->super->s_blocks_count)) &&
1433             fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
1434                 return 1;
1435
1436         retval = io_channel_read_blk(fs->io, blk, 1, block_buf);
1437         if (retval && fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
1438                 return 1;
1439
1440         /* XXX should check that beginning matches a directory */
1441         root = (struct ext2_dx_root_info *) (block_buf + 24);
1442
1443         if ((root->reserved_zero || root->info_length < 8) &&
1444             fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
1445                 return 1;
1446
1447         pctx->num = root->hash_version;
1448         if ((root->hash_version != EXT2_HASH_LEGACY) &&
1449             (root->hash_version != EXT2_HASH_HALF_MD4) &&
1450             (root->hash_version != EXT2_HASH_TEA) &&
1451             fix_problem(ctx, PR_1_HTREE_HASHV, pctx))
1452                 return 1;
1453
1454         if ((root->unused_flags & EXT2_HASH_FLAG_INCOMPAT) &&
1455             fix_problem(ctx, PR_1_HTREE_INCOMPAT, pctx))
1456                 return 1;
1457
1458         pctx->num = root->indirect_levels;
1459         if ((root->indirect_levels > 1) &&
1460             fix_problem(ctx, PR_1_HTREE_DEPTH, pctx))
1461                 return 1;
1462
1463         return 0;
1464 }
1465
1466 /*
1467  * This subroutine is called on each inode to account for all of the
1468  * blocks used by that inode.
1469  */
1470 static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
1471                          char *block_buf)
1472 {
1473         ext2_filsys fs = ctx->fs;
1474         struct process_block_struct pb;
1475         ext2_ino_t      ino = pctx->ino;
1476         struct ext2_inode *inode = pctx->inode;
1477         int             bad_size = 0;
1478         int             dirty_inode = 0;
1479         __u64           size;
1480
1481         pb.ino = ino;
1482         pb.num_blocks = 0;
1483         pb.last_block = -1;
1484         pb.num_illegal_blocks = 0;
1485         pb.suppress = 0; pb.clear = 0;
1486         pb.fragmented = 0;
1487         pb.compressed = 0;
1488         pb.previous_block = 0;
1489         pb.is_dir = LINUX_S_ISDIR(inode->i_mode);
1490         pb.is_reg = LINUX_S_ISREG(inode->i_mode);
1491         pb.max_blocks = 1 << (31 - fs->super->s_log_block_size);
1492         pb.inode = inode;
1493         pb.pctx = pctx;
1494         pb.ctx = ctx;
1495         pctx->ino = ino;
1496         pctx->errcode = 0;
1497
1498         if (inode->i_flags & EXT2_COMPRBLK_FL) {
1499                 if (fs->super->s_feature_incompat &
1500                     EXT2_FEATURE_INCOMPAT_COMPRESSION)
1501                         pb.compressed = 1;
1502                 else {
1503                         if (fix_problem(ctx, PR_1_COMPR_SET, pctx)) {
1504                                 inode->i_flags &= ~EXT2_COMPRBLK_FL;
1505                                 dirty_inode++;
1506                         }
1507                 }
1508         }
1509
1510         if (inode->i_file_acl && check_ext_attr(ctx, pctx, block_buf))
1511                 pb.num_blocks++;
1512
1513         if (ext2fs_inode_has_valid_blocks(inode))
1514                 pctx->errcode = ext2fs_block_iterate2(fs, ino,
1515                                        pb.is_dir ? BLOCK_FLAG_HOLE : 0,
1516                                        block_buf, process_block, &pb);
1517         end_problem_latch(ctx, PR_LATCH_BLOCK);
1518         end_problem_latch(ctx, PR_LATCH_TOOBIG);
1519         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
1520                 goto out;
1521         if (pctx->errcode)
1522                 fix_problem(ctx, PR_1_BLOCK_ITERATE, pctx);
1523
1524         if (pb.fragmented && pb.num_blocks < fs->super->s_blocks_per_group)
1525                 ctx->fs_fragmented++;
1526
1527         if (pb.clear) {
1528                 inode->i_links_count = 0;
1529                 ext2fs_icount_store(ctx->inode_link_info, ino, 0);
1530                 inode->i_dtime = ctx->now;
1531                 dirty_inode++;
1532                 ext2fs_unmark_inode_bitmap(ctx->inode_dir_map, ino);
1533                 ext2fs_unmark_inode_bitmap(ctx->inode_reg_map, ino);
1534                 ext2fs_unmark_inode_bitmap(ctx->inode_used_map, ino);
1535                 /*
1536                  * The inode was probably partially accounted for
1537                  * before processing was aborted, so we need to
1538                  * restart the pass 1 scan.
1539                  */
1540                 ctx->flags |= E2F_FLAG_RESTART;
1541                 goto out;
1542         }
1543
1544         if (inode->i_flags & EXT2_INDEX_FL) {
1545                 if (handle_htree(ctx, pctx, ino, inode, block_buf)) {
1546                         inode->i_flags &= ~EXT2_INDEX_FL;
1547                         dirty_inode++;
1548                 } else {
1549 #ifdef ENABLE_HTREE
1550                         e2fsck_add_dx_dir(ctx, ino, pb.last_block+1);
1551 #endif
1552                 }
1553         }
1554         if (ctx->dirs_to_hash && pb.is_dir &&
1555             !(inode->i_flags & EXT2_INDEX_FL) &&
1556             ((inode->i_size / fs->blocksize) >= 3))
1557                 ext2fs_u32_list_add(ctx->dirs_to_hash, ino);
1558
1559         if (!pb.num_blocks && pb.is_dir) {
1560                 if (fix_problem(ctx, PR_1_ZERO_LENGTH_DIR, pctx)) {
1561                         inode->i_links_count = 0;
1562                         ext2fs_icount_store(ctx->inode_link_info, ino, 0);
1563                         inode->i_dtime = ctx->now;
1564                         dirty_inode++;
1565                         ext2fs_unmark_inode_bitmap(ctx->inode_dir_map, ino);
1566                         ext2fs_unmark_inode_bitmap(ctx->inode_reg_map, ino);
1567                         ext2fs_unmark_inode_bitmap(ctx->inode_used_map, ino);
1568                         ctx->fs_directory_count--;
1569                         goto out;
1570                 }
1571         }
1572
1573         pb.num_blocks *= (fs->blocksize / 512);
1574 #if 0
1575         printf("inode %u, i_size = %lu, last_block = %lld, i_blocks=%lu, num_blocks = %lu\n",
1576                ino, inode->i_size, pb.last_block, inode->i_blocks,
1577                pb.num_blocks);
1578 #endif
1579         if (pb.is_dir) {
1580                 int nblock = inode->i_size >> EXT2_BLOCK_SIZE_BITS(fs->super);
1581                 if (nblock > (pb.last_block + 1))
1582                         bad_size = 1;
1583                 else if (nblock < (pb.last_block + 1)) {
1584                         if (((pb.last_block + 1) - nblock) >
1585                             fs->super->s_prealloc_dir_blocks)
1586                                 bad_size = 2;
1587                 }
1588         } else {
1589                 size = EXT2_I_SIZE(inode);
1590                 if ((pb.last_block >= 0) &&
1591                     (size < (__u64) pb.last_block * fs->blocksize))
1592                         bad_size = 3;
1593                 else if (size > ext2_max_sizes[fs->super->s_log_block_size])
1594                         bad_size = 4;
1595         }
1596         /* i_size for symlinks is checked elsewhere */
1597         if (bad_size && !LINUX_S_ISLNK(inode->i_mode)) {
1598                 pctx->num = (pb.last_block+1) * fs->blocksize;
1599                 if (fix_problem(ctx, PR_1_BAD_I_SIZE, pctx)) {
1600                         inode->i_size = pctx->num;
1601                         if (!LINUX_S_ISDIR(inode->i_mode))
1602                                 inode->i_size_high = pctx->num >> 32;
1603                         dirty_inode++;
1604                 }
1605                 pctx->num = 0;
1606         }
1607         if (LINUX_S_ISREG(inode->i_mode) &&
1608             (inode->i_size_high || inode->i_size & 0x80000000UL))
1609                 ctx->large_files++;
1610         if (pb.num_blocks != inode->i_blocks) {
1611                 pctx->num = pb.num_blocks;
1612                 if (fix_problem(ctx, PR_1_BAD_I_BLOCKS, pctx)) {
1613                         inode->i_blocks = pb.num_blocks;
1614                         dirty_inode++;
1615                 }
1616                 pctx->num = 0;
1617         }
1618 out:
1619         if (dirty_inode)
1620                 e2fsck_write_inode(ctx, ino, inode, "check_blocks");
1621 }
1622
1623 #if 0
1624 /*
1625  * Helper function called by process block when an illegal block is
1626  * found.  It returns a description about why the block is illegal
1627  */
1628 static char *describe_illegal_block(ext2_filsys fs, blk_t block)
1629 {
1630         blk_t   super;
1631         int     i;
1632         static char     problem[80];
1633
1634         super = fs->super->s_first_data_block;
1635         strcpy(problem, "PROGRAMMING ERROR: Unknown reason for illegal block");
1636         if (block < super) {
1637                 sprintf(problem, "< FIRSTBLOCK (%u)", super);
1638                 return(problem);
1639         } else if (block >= fs->super->s_blocks_count) {
1640                 sprintf(problem, "> BLOCKS (%u)", fs->super->s_blocks_count);
1641                 return(problem);
1642         }
1643         for (i = 0; i < fs->group_desc_count; i++) {
1644                 if (block == super) {
1645                         sprintf(problem, "is the superblock in group %d", i);
1646                         break;
1647                 }
1648                 if (block > super &&
1649                     block <= (super + fs->desc_blocks)) {
1650                         sprintf(problem, "is in the group descriptors "
1651                                 "of group %d", i);
1652                         break;
1653                 }
1654                 if (block == fs->group_desc[i].bg_block_bitmap) {
1655                         sprintf(problem, "is the block bitmap of group %d", i);
1656                         break;
1657                 }
1658                 if (block == fs->group_desc[i].bg_inode_bitmap) {
1659                         sprintf(problem, "is the inode bitmap of group %d", i);
1660                         break;
1661                 }
1662                 if (block >= fs->group_desc[i].bg_inode_table &&
1663                     (block < fs->group_desc[i].bg_inode_table
1664                      + fs->inode_blocks_per_group)) {
1665                         sprintf(problem, "is in the inode table of group %d",
1666                                 i);
1667                         break;
1668                 }
1669                 super += fs->super->s_blocks_per_group;
1670         }
1671         return(problem);
1672 }
1673 #endif
1674
1675 /*
1676  * This is a helper function for check_blocks().
1677  */
1678 static int process_block(ext2_filsys fs,
1679                   blk_t *block_nr,
1680                   e2_blkcnt_t blockcnt,
1681                   blk_t ref_block EXT2FS_ATTR((unused)),
1682                   int ref_offset EXT2FS_ATTR((unused)),
1683                   void *priv_data)
1684 {
1685         struct process_block_struct *p;
1686         struct problem_context *pctx;
1687         blk_t   blk = *block_nr;
1688         int     ret_code = 0;
1689         int     problem = 0;
1690         e2fsck_t        ctx;
1691
1692         p = (struct process_block_struct *) priv_data;
1693         pctx = p->pctx;
1694         ctx = p->ctx;
1695
1696         if (p->compressed && (blk == EXT2FS_COMPRESSED_BLKADDR)) {
1697                 /* todo: Check that the comprblk_fl is high, that the
1698                    blkaddr pattern looks right (all non-holes up to
1699                    first EXT2FS_COMPRESSED_BLKADDR, then all
1700                    EXT2FS_COMPRESSED_BLKADDR up to end of cluster),
1701                    that the feature_incompat bit is high, and that the
1702                    inode is a regular file.  If we're doing a "full
1703                    check" (a concept introduced to e2fsck by e2compr,
1704                    meaning that we look at data blocks as well as
1705                    metadata) then call some library routine that
1706                    checks the compressed data.  I'll have to think
1707                    about this, because one particularly important
1708                    problem to be able to fix is to recalculate the
1709                    cluster size if necessary.  I think that perhaps
1710                    we'd better do most/all e2compr-specific checks
1711                    separately, after the non-e2compr checks.  If not
1712                    doing a full check, it may be useful to test that
1713                    the personality is linux; e.g. if it isn't then
1714                    perhaps this really is just an illegal block. */
1715                 return 0;
1716         }
1717
1718         if (blk == 0) {
1719                 if (p->is_dir == 0) {
1720                         /*
1721                          * Should never happen, since only directories
1722                          * get called with BLOCK_FLAG_HOLE
1723                          */
1724 #if DEBUG_E2FSCK
1725                         printf("process_block() called with blk == 0, "
1726                                "blockcnt=%d, inode %lu???\n",
1727                                blockcnt, p->ino);
1728 #endif
1729                         return 0;
1730                 }
1731                 if (blockcnt < 0)
1732                         return 0;
1733                 if (blockcnt * fs->blocksize < p->inode->i_size) {
1734 #if 0
1735                         printf("Missing block (#%d) in directory inode %lu!\n",
1736                                blockcnt, p->ino);
1737 #endif
1738                         goto mark_dir;
1739                 }
1740                 return 0;
1741         }
1742
1743 #if 0
1744         printf("Process_block, inode %lu, block %u, #%d\n", p->ino, blk,
1745                blockcnt);
1746 #endif
1747
1748         /*
1749          * Simplistic fragmentation check.  We merely require that the
1750          * file be contiguous.  (Which can never be true for really
1751          * big files that are greater than a block group.)
1752          */
1753         if (!HOLE_BLKADDR(p->previous_block)) {
1754                 if (p->previous_block+1 != blk)
1755                         p->fragmented = 1;
1756         }
1757         p->previous_block = blk;
1758
1759         if (p->is_dir && blockcnt > (1 << (21 - fs->super->s_log_block_size)))
1760                 problem = PR_1_TOOBIG_DIR;
1761         if (p->is_reg && p->num_blocks+1 >= p->max_blocks)
1762                 problem = PR_1_TOOBIG_REG;
1763         if (!p->is_dir && !p->is_reg && blockcnt > 0)
1764                 problem = PR_1_TOOBIG_SYMLINK;
1765
1766         if (blk < fs->super->s_first_data_block ||
1767             blk >= fs->super->s_blocks_count)
1768                 problem = PR_1_ILLEGAL_BLOCK_NUM;
1769
1770         if (problem) {
1771                 p->num_illegal_blocks++;
1772                 if (!p->suppress && (p->num_illegal_blocks % 12) == 0) {
1773                         if (fix_problem(ctx, PR_1_TOO_MANY_BAD_BLOCKS, pctx)) {
1774                                 p->clear = 1;
1775                                 return BLOCK_ABORT;
1776                         }
1777                         if (fix_problem(ctx, PR_1_SUPPRESS_MESSAGES, pctx)) {
1778                                 p->suppress = 1;
1779                                 set_latch_flags(PR_LATCH_BLOCK,
1780                                                 PRL_SUPPRESS, 0);
1781                         }
1782                 }
1783                 pctx->blk = blk;
1784                 pctx->blkcount = blockcnt;
1785                 if (fix_problem(ctx, problem, pctx)) {
1786                         blk = *block_nr = 0;
1787                         ret_code = BLOCK_CHANGED;
1788                         goto mark_dir;
1789                 } else
1790                         return 0;
1791         }
1792
1793         if (p->ino == EXT2_RESIZE_INO) {
1794                 /*
1795                  * The resize inode has already be sanity checked
1796                  * during pass #0 (the superblock checks).  All we
1797                  * have to do is mark the double indirect block as
1798                  * being in use; all of the other blocks are handled
1799                  * by mark_table_blocks()).
1800                  */
1801                 if (blockcnt == BLOCK_COUNT_DIND)
1802                         mark_block_used(ctx, blk);
1803         } else
1804                 mark_block_used(ctx, blk);
1805         p->num_blocks++;
1806         if (blockcnt >= 0)
1807                 p->last_block = blockcnt;
1808 mark_dir:
1809         if (p->is_dir && (blockcnt >= 0)) {
1810                 pctx->errcode = ext2fs_add_dir_block(fs->dblist, p->ino,
1811                                                     blk, blockcnt);
1812                 if (pctx->errcode) {
1813                         pctx->blk = blk;
1814                         pctx->num = blockcnt;
1815                         fix_problem(ctx, PR_1_ADD_DBLOCK, pctx);
1816                         /* Should never get here */
1817                         ctx->flags |= E2F_FLAG_ABORT;
1818                         return BLOCK_ABORT;
1819                 }
1820         }
1821         return ret_code;
1822 }
1823
1824 static int process_bad_block(ext2_filsys fs,
1825                       blk_t *block_nr,
1826                       e2_blkcnt_t blockcnt,
1827                       blk_t ref_block EXT2FS_ATTR((unused)),
1828                       int ref_offset EXT2FS_ATTR((unused)),
1829                       void *priv_data)
1830 {
1831         struct process_block_struct *p;
1832         blk_t           blk = *block_nr;
1833         blk_t           first_block;
1834         dgrp_t          i;
1835         struct problem_context *pctx;
1836         e2fsck_t        ctx;
1837
1838         /*
1839          * Note: This function processes blocks for the bad blocks
1840          * inode, which is never compressed.  So we don't use HOLE_BLKADDR().
1841          */
1842
1843         if (!blk)
1844                 return 0;
1845
1846         p = (struct process_block_struct *) priv_data;
1847         ctx = p->ctx;
1848         pctx = p->pctx;
1849
1850         pctx->ino = EXT2_BAD_INO;
1851         pctx->blk = blk;
1852         pctx->blkcount = blockcnt;
1853
1854         if ((blk < fs->super->s_first_data_block) ||
1855             (blk >= fs->super->s_blocks_count)) {
1856                 if (fix_problem(ctx, PR_1_BB_ILLEGAL_BLOCK_NUM, pctx)) {
1857                         *block_nr = 0;
1858                         return BLOCK_CHANGED;
1859                 } else
1860                         return 0;
1861         }
1862
1863         if (blockcnt < 0) {
1864                 if (ext2fs_test_block_bitmap(p->fs_meta_blocks, blk)) {
1865                         p->bbcheck = 1;
1866                         if (fix_problem(ctx, PR_1_BB_FS_BLOCK, pctx)) {
1867                                 *block_nr = 0;
1868                                 return BLOCK_CHANGED;
1869                         }
1870                 } else if (ext2fs_test_block_bitmap(ctx->block_found_map,
1871                                                     blk)) {
1872                         p->bbcheck = 1;
1873                         if (fix_problem(ctx, PR_1_BBINODE_BAD_METABLOCK,
1874                                         pctx)) {
1875                                 *block_nr = 0;
1876                                 return BLOCK_CHANGED;
1877                         }
1878                         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
1879                                 return BLOCK_ABORT;
1880                 } else
1881                         mark_block_used(ctx, blk);
1882                 return 0;
1883         }
1884 #if 0
1885         printf ("DEBUG: Marking %u as bad.\n", blk);
1886 #endif
1887         ctx->fs_badblocks_count++;
1888         /*
1889          * If the block is not used, then mark it as used and return.
1890          * If it is already marked as found, this must mean that
1891          * there's an overlap between the filesystem table blocks
1892          * (bitmaps and inode table) and the bad block list.
1893          */
1894         if (!ext2fs_test_block_bitmap(ctx->block_found_map, blk)) {
1895                 ext2fs_mark_block_bitmap(ctx->block_found_map, blk);
1896                 return 0;
1897         }
1898         /*
1899          * Try to find the where the filesystem block was used...
1900          */
1901         first_block = fs->super->s_first_data_block;
1902
1903         for (i = 0; i < fs->group_desc_count; i++ ) {
1904                 pctx->group = i;
1905                 pctx->blk = blk;
1906                 if (!ext2fs_bg_has_super(fs, i))
1907                         goto skip_super;
1908                 if (blk == first_block) {
1909                         if (i == 0) {
1910                                 if (fix_problem(ctx,
1911                                                 PR_1_BAD_PRIMARY_SUPERBLOCK,
1912                                                 pctx)) {
1913                                         *block_nr = 0;
1914                                         return BLOCK_CHANGED;
1915                                 }
1916                                 return 0;
1917                         }
1918                         fix_problem(ctx, PR_1_BAD_SUPERBLOCK, pctx);
1919                         return 0;
1920                 }
1921                 if ((blk > first_block) &&
1922                     (blk <= first_block + fs->desc_blocks)) {
1923                         if (i == 0) {
1924                                 pctx->blk = *block_nr;
1925                                 if (fix_problem(ctx,
1926                         PR_1_BAD_PRIMARY_GROUP_DESCRIPTOR, pctx)) {
1927                                         *block_nr = 0;
1928                                         return BLOCK_CHANGED;
1929                                 }
1930                                 return 0;
1931                         }
1932                         fix_problem(ctx, PR_1_BAD_GROUP_DESCRIPTORS, pctx);
1933                         return 0;
1934                 }
1935         skip_super:
1936                 if (blk == fs->group_desc[i].bg_block_bitmap) {
1937                         if (fix_problem(ctx, PR_1_BB_BAD_BLOCK, pctx)) {
1938                                 ctx->invalid_block_bitmap_flag[i]++;
1939                                 ctx->invalid_bitmaps++;
1940                         }
1941                         return 0;
1942                 }
1943                 if (blk == fs->group_desc[i].bg_inode_bitmap) {
1944                         if (fix_problem(ctx, PR_1_IB_BAD_BLOCK, pctx)) {
1945                                 ctx->invalid_inode_bitmap_flag[i]++;
1946                                 ctx->invalid_bitmaps++;
1947                         }
1948                         return 0;
1949                 }
1950                 if ((blk >= fs->group_desc[i].bg_inode_table) &&
1951                     (blk < (fs->group_desc[i].bg_inode_table +
1952                             fs->inode_blocks_per_group))) {
1953                         /*
1954                          * If there are bad blocks in the inode table,
1955                          * the inode scan code will try to do
1956                          * something reasonable automatically.
1957                          */
1958                         return 0;
1959                 }
1960                 first_block += fs->super->s_blocks_per_group;
1961         }
1962         /*
1963          * If we've gotten to this point, then the only
1964          * possibility is that the bad block inode meta data
1965          * is using a bad block.
1966          */
1967         if ((blk == p->inode->i_block[EXT2_IND_BLOCK]) ||
1968             (blk == p->inode->i_block[EXT2_DIND_BLOCK]) ||
1969             (blk == p->inode->i_block[EXT2_TIND_BLOCK])) {
1970                 p->bbcheck = 1;
1971                 if (fix_problem(ctx, PR_1_BBINODE_BAD_METABLOCK, pctx)) {
1972                         *block_nr = 0;
1973                         return BLOCK_CHANGED;
1974                 }
1975                 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
1976                         return BLOCK_ABORT;
1977                 return 0;
1978         }
1979
1980         pctx->group = -1;
1981
1982         /* Warn user that the block wasn't claimed */
1983         fix_problem(ctx, PR_1_PROGERR_CLAIMED_BLOCK, pctx);
1984
1985         return 0;
1986 }
1987
1988 static void new_table_block(e2fsck_t ctx, blk_t first_block, int group,
1989                             const char *name, int num, blk_t *new_block)
1990 {
1991         ext2_filsys fs = ctx->fs;
1992         blk_t           old_block = *new_block;
1993         blk_t           last_block;
1994         int             i;
1995         char            *buf;
1996         struct problem_context  pctx;
1997
1998         clear_problem_context(&pctx);
1999
2000         pctx.group = group;
2001         pctx.blk = old_block;
2002         pctx.str = name;
2003
2004         last_block = ext2fs_group_last_block(fs, group);
2005         pctx.errcode = ext2fs_get_free_blocks(fs, first_block, last_block,
2006                                         num, ctx->block_found_map, new_block);
2007         if (pctx.errcode) {
2008                 pctx.num = num;
2009                 fix_problem(ctx, PR_1_RELOC_BLOCK_ALLOCATE, &pctx);
2010                 ext2fs_unmark_valid(fs);
2011                 return;
2012         }
2013         pctx.errcode = ext2fs_get_mem(fs->blocksize, &buf);
2014         if (pctx.errcode) {
2015                 fix_problem(ctx, PR_1_RELOC_MEMORY_ALLOCATE, &pctx);
2016                 ext2fs_unmark_valid(fs);
2017                 return;
2018         }
2019         ext2fs_mark_super_dirty(fs);
2020         fs->flags &= ~EXT2_FLAG_MASTER_SB_ONLY;
2021         pctx.blk2 = *new_block;
2022         fix_problem(ctx, (old_block ? PR_1_RELOC_FROM_TO :
2023                           PR_1_RELOC_TO), &pctx);
2024         pctx.blk2 = 0;
2025         for (i = 0; i < num; i++) {
2026                 pctx.blk = i;
2027                 ext2fs_mark_block_bitmap(ctx->block_found_map, (*new_block)+i);
2028                 if (old_block) {
2029                         pctx.errcode = io_channel_read_blk(fs->io,
2030                                    old_block + i, 1, buf);
2031                         if (pctx.errcode)
2032                                 fix_problem(ctx, PR_1_RELOC_READ_ERR, &pctx);
2033                 } else
2034                         memset(buf, 0, fs->blocksize);
2035
2036                 pctx.blk = (*new_block) + i;
2037                 pctx.errcode = io_channel_write_blk(fs->io, pctx.blk,
2038                                               1, buf);
2039                 if (pctx.errcode)
2040                         fix_problem(ctx, PR_1_RELOC_WRITE_ERR, &pctx);
2041         }
2042         ext2fs_free_mem(&buf);
2043 }
2044
2045 /*
2046  * This routine gets called at the end of pass 1 if bad blocks are
2047  * detected in the superblock, group descriptors, inode_bitmaps, or
2048  * block bitmaps.  At this point, all of the blocks have been mapped
2049  * out, so we can try to allocate new block(s) to replace the bad
2050  * blocks.
2051  */
2052 static void handle_fs_bad_blocks(e2fsck_t ctx)
2053 {
2054         ext2_filsys fs = ctx->fs;
2055         dgrp_t          i;
2056         blk_t           first_block;
2057
2058         for (i = 0; i < fs->group_desc_count; i++) {
2059                 first_block = ext2fs_group_first_block(fs, i);
2060
2061                 if (ctx->invalid_block_bitmap_flag[i]) {
2062                         new_table_block(ctx, first_block, i, _("block bitmap"),
2063                                         1, &fs->group_desc[i].bg_block_bitmap);
2064                 }
2065                 if (ctx->invalid_inode_bitmap_flag[i]) {
2066                         new_table_block(ctx, first_block, i, _("inode bitmap"),
2067                                         1, &fs->group_desc[i].bg_inode_bitmap);
2068                 }
2069                 if (ctx->invalid_inode_table_flag[i]) {
2070                         new_table_block(ctx, first_block, i, _("inode table"),
2071                                         fs->inode_blocks_per_group,
2072                                         &fs->group_desc[i].bg_inode_table);
2073                         ctx->flags |= E2F_FLAG_RESTART;
2074                 }
2075         }
2076         ctx->invalid_bitmaps = 0;
2077 }
2078
2079 /*
2080  * This routine marks all blocks which are used by the superblock,
2081  * group descriptors, inode bitmaps, and block bitmaps.
2082  */
2083 static void mark_table_blocks(e2fsck_t ctx)
2084 {
2085         ext2_filsys fs = ctx->fs;
2086         blk_t   b;
2087         dgrp_t  i;
2088         int     j;
2089         struct problem_context pctx;
2090
2091         clear_problem_context(&pctx);
2092
2093         for (i = 0; i < fs->group_desc_count; i++) {
2094                 pctx.group = i;
2095
2096                 ext2fs_reserve_super_and_bgd(fs, i, ctx->block_found_map);
2097
2098                 /*
2099                  * Mark the blocks used for the inode table
2100                  */
2101                 if (fs->group_desc[i].bg_inode_table) {
2102                         for (j = 0, b = fs->group_desc[i].bg_inode_table;
2103                              j < fs->inode_blocks_per_group;
2104                              j++, b++) {
2105                                 if (ext2fs_test_block_bitmap(ctx->block_found_map,
2106                                                              b)) {
2107                                         pctx.blk = b;
2108                                         if (fix_problem(ctx,
2109                                                 PR_1_ITABLE_CONFLICT, &pctx)) {
2110                                                 ctx->invalid_inode_table_flag[i]++;
2111                                                 ctx->invalid_bitmaps++;
2112                                         }
2113                                 } else {
2114                                     ext2fs_mark_block_bitmap(ctx->block_found_map,
2115                                                              b);
2116                                 }
2117                         }
2118                 }
2119
2120                 /*
2121                  * Mark block used for the block bitmap
2122                  */
2123                 if (fs->group_desc[i].bg_block_bitmap) {
2124                         if (ext2fs_test_block_bitmap(ctx->block_found_map,
2125                                      fs->group_desc[i].bg_block_bitmap)) {
2126                                 pctx.blk = fs->group_desc[i].bg_block_bitmap;
2127                                 if (fix_problem(ctx, PR_1_BB_CONFLICT, &pctx)) {
2128                                         ctx->invalid_block_bitmap_flag[i]++;
2129                                         ctx->invalid_bitmaps++;
2130                                 }
2131                         } else {
2132                             ext2fs_mark_block_bitmap(ctx->block_found_map,
2133                                      fs->group_desc[i].bg_block_bitmap);
2134                     }
2135
2136                 }
2137                 /*
2138                  * Mark block used for the inode bitmap
2139                  */
2140                 if (fs->group_desc[i].bg_inode_bitmap) {
2141                         if (ext2fs_test_block_bitmap(ctx->block_found_map,
2142                                      fs->group_desc[i].bg_inode_bitmap)) {
2143                                 pctx.blk = fs->group_desc[i].bg_inode_bitmap;
2144                                 if (fix_problem(ctx, PR_1_IB_CONFLICT, &pctx)) {
2145                                         ctx->invalid_inode_bitmap_flag[i]++;
2146                                         ctx->invalid_bitmaps++;
2147                                 }
2148                         } else {
2149                             ext2fs_mark_block_bitmap(ctx->block_found_map,
2150                                      fs->group_desc[i].bg_inode_bitmap);
2151                         }
2152                 }
2153         }
2154 }
2155
2156 /*
2157  * Thes subroutines short circuits ext2fs_get_blocks and
2158  * ext2fs_check_directory; we use them since we already have the inode
2159  * structure, so there's no point in letting the ext2fs library read
2160  * the inode again.
2161  */
2162 static errcode_t pass1_get_blocks(ext2_filsys fs, ext2_ino_t ino,
2163                                   blk_t *blocks)
2164 {
2165         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2166         int     i;
2167
2168         if ((ino != ctx->stashed_ino) || !ctx->stashed_inode)
2169                 return EXT2_ET_CALLBACK_NOTHANDLED;
2170
2171         for (i=0; i < EXT2_N_BLOCKS; i++)
2172                 blocks[i] = ctx->stashed_inode->i_block[i];
2173         return 0;
2174 }
2175
2176 static errcode_t pass1_read_inode(ext2_filsys fs, ext2_ino_t ino,
2177                                   struct ext2_inode *inode)
2178 {
2179         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2180
2181         if ((ino != ctx->stashed_ino) || !ctx->stashed_inode)
2182                 return EXT2_ET_CALLBACK_NOTHANDLED;
2183         *inode = *ctx->stashed_inode;
2184         return 0;
2185 }
2186
2187 static errcode_t pass1_write_inode(ext2_filsys fs, ext2_ino_t ino,
2188                             struct ext2_inode *inode)
2189 {
2190         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2191
2192         if ((ino == ctx->stashed_ino) && ctx->stashed_inode &&
2193                 (inode != ctx->stashed_inode))
2194                 *ctx->stashed_inode = *inode;
2195         return EXT2_ET_CALLBACK_NOTHANDLED;
2196 }
2197
2198 static errcode_t pass1_check_directory(ext2_filsys fs, ext2_ino_t ino)
2199 {
2200         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2201
2202         if ((ino != ctx->stashed_ino) || !ctx->stashed_inode)
2203                 return EXT2_ET_CALLBACK_NOTHANDLED;
2204
2205         if (!LINUX_S_ISDIR(ctx->stashed_inode->i_mode))
2206                 return EXT2_ET_NO_DIRECTORY;
2207         return 0;
2208 }
2209
2210 void e2fsck_use_inode_shortcuts(e2fsck_t ctx, int bool)
2211 {
2212         ext2_filsys fs = ctx->fs;
2213
2214         if (bool) {
2215                 fs->get_blocks = pass1_get_blocks;
2216                 fs->check_directory = pass1_check_directory;
2217                 fs->read_inode = pass1_read_inode;
2218                 fs->write_inode = pass1_write_inode;
2219                 ctx->stashed_ino = 0;
2220         } else {
2221                 fs->get_blocks = 0;
2222                 fs->check_directory = 0;
2223                 fs->read_inode = 0;
2224                 fs->write_inode = 0;
2225         }
2226 }