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 "config.h"
  42 #include <string.h>
  43 #include <time.h>
  44 #ifdef HAVE_ERRNO_H
  45 #include <errno.h>
  46 #endif
  47
  48 #include "e2fsck.h"
  49 #include <ext2fs/ext2_ext_attr.h>
  50
  51 #include "problem.h"
  52
  53 #ifdef NO_INLINE_FUNCS
  54 #define _INLINE_
  55 #else
  56 #define _INLINE_ inline
  57 #endif
  58
  59 static int process_block(ext2_filsys fs, blk64_t        *blocknr,
  60                          e2_blkcnt_t blockcnt, blk64_t ref_blk,
  61                          int ref_offset, void *priv_data);
  62 static int process_bad_block(ext2_filsys fs, blk64_t *block_nr,
  63                              e2_blkcnt_t blockcnt, blk64_t ref_blk,
  64                              int ref_offset, void *priv_data);
  65 static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
  66                          char *block_buf);
  67 static void mark_table_blocks(e2fsck_t ctx);
  68 static void alloc_bb_map(e2fsck_t ctx);
  69 static void alloc_imagic_map(e2fsck_t ctx);
  70 static void mark_inode_bad(e2fsck_t ctx, ino_t ino);
  71 static void handle_fs_bad_blocks(e2fsck_t ctx);
  72 static void process_inodes(e2fsck_t ctx, char *block_buf);
  73 static EXT2_QSORT_TYPE process_inode_cmp(const void *a, const void *b);
  74 static errcode_t scan_callback(ext2_filsys fs, ext2_inode_scan scan,
  75                                   dgrp_t group, void * priv_data);
  76 static void adjust_extattr_refcount(e2fsck_t ctx, ext2_refcount_t refcount,
  77                                     char *block_buf, int adjust_sign);
  78 /* static char *describe_illegal_block(ext2_filsys fs, blk64_t block); */
  79
  80 struct process_block_struct {
  81         ext2_ino_t      ino;
  82         unsigned        is_dir:1, is_reg:1, clear:1, suppress:1,
  83                                 fragmented:1, compressed:1, bbcheck:1,
  84                                 inode_modified:1;
  85         blk64_t         num_blocks;
  86         blk64_t         max_blocks;
  87         e2_blkcnt_t     last_block;
  88         e2_blkcnt_t     last_init_lblock;
  89         e2_blkcnt_t     last_db_block;
  90         int             num_illegal_blocks;
  91         blk64_t         previous_block;
  92         struct ext2_inode *inode;
  93         struct problem_context *pctx;
  94         ext2fs_block_bitmap fs_meta_blocks;
  95         e2fsck_t        ctx;
  96 };
  97
  98 struct process_inode_block {
  99         ext2_ino_t ino;
 100         struct ext2_inode inode;
 101 };
 102
 103 struct scan_callback_struct {
 104         e2fsck_t        ctx;
 105         char            *block_buf;
 106 };
 107
 108 /*
 109  * For the inodes to process list.
 110  */
 111 static struct process_inode_block *inodes_to_process;
 112 static int process_inode_count;
 113
 114 static __u64 ext2_max_sizes[EXT2_MAX_BLOCK_LOG_SIZE -
 115                             EXT2_MIN_BLOCK_LOG_SIZE + 1];
 116
 117 /*
 118  * Free all memory allocated by pass1 in preparation for restarting
 119  * things.
 120  */
 121 static void unwind_pass1(ext2_filsys fs EXT2FS_ATTR((unused)))
 122 {
 123         ext2fs_free_mem(&inodes_to_process);
 124         inodes_to_process = 0;
 125 }
 126
 127 /*
 128  * Check to make sure a device inode is real.  Returns 1 if the device
 129  * checks out, 0 if not.
 130  *
 131  * Note: this routine is now also used to check FIFO's and Sockets,
 132  * since they have the same requirement; the i_block fields should be
 133  * zero.
 134  */
 135 int e2fsck_pass1_check_device_inode(ext2_filsys fs EXT2FS_ATTR((unused)),
 136                                     struct ext2_inode *inode)
 137 {
 138         int     i;
 139
 140         /*
 141          * If the index flag is set, then this is a bogus
 142          * device/fifo/socket
 143          */
 144         if (inode->i_flags & EXT2_INDEX_FL)
 145                 return 0;
 146
 147         /*
 148          * We should be able to do the test below all the time, but
 149          * because the kernel doesn't forcibly clear the device
 150          * inode's additional i_block fields, there are some rare
 151          * occasions when a legitimate device inode will have non-zero
 152          * additional i_block fields.  So for now, we only complain
 153          * when the immutable flag is set, which should never happen
 154          * for devices.  (And that's when the problem is caused, since
 155          * you can't set or clear immutable flags for devices.)  Once
 156          * the kernel has been fixed we can change this...
 157          */
 158         if (inode->i_flags & (EXT2_IMMUTABLE_FL | EXT2_APPEND_FL)) {
 159                 for (i=4; i < EXT2_N_BLOCKS; i++)
 160                         if (inode->i_block[i])
 161                                 return 0;
 162         }
 163         return 1;
 164 }
 165
 166 /*
 167  * Check to make sure a symlink inode is real.  Returns 1 if the symlink
 168  * checks out, 0 if not.
 169  */
 170 int e2fsck_pass1_check_symlink(ext2_filsys fs, ext2_ino_t ino,
 171                                struct ext2_inode *inode, char *buf)
 172 {
 173         unsigned int len;
 174         int i;
 175         blk64_t blocks;
 176         ext2_extent_handle_t    handle;
 177         struct ext2_extent_info info;
 178         struct ext2fs_extent    extent;
 179
 180         if ((inode->i_size_high || inode->i_size == 0) ||
 181             (inode->i_flags & EXT2_INDEX_FL))
 182                 return 0;
 183
 184         if (inode->i_flags & EXT4_EXTENTS_FL) {
 185                 if (inode->i_size > fs->blocksize)
 186                         return 0;
 187                 if (ext2fs_extent_open2(fs, ino, inode, &handle))
 188                         return 0;
 189                 i = 0;
 190                 if (ext2fs_extent_get_info(handle, &info) ||
 191                     (info.num_entries != 1) ||
 192                     (info.max_depth != 0))
 193                         goto exit_extent;
 194                 if (ext2fs_extent_get(handle, EXT2_EXTENT_ROOT, &extent) ||
 195                     (extent.e_lblk != 0) ||
 196                     (extent.e_len != 1) ||
 197                     (extent.e_pblk < fs->super->s_first_data_block) ||
 198                     (extent.e_pblk >= ext2fs_blocks_count(fs->super)))
 199                         goto exit_extent;
 200                 i = 1;
 201         exit_extent:
 202                 ext2fs_extent_free(handle);
 203                 return i;
 204         }
 205
 206         blocks = ext2fs_inode_data_blocks2(fs, inode);
 207         if (blocks) {
 208                 if ((inode->i_size >= fs->blocksize) ||
 209                     (blocks != fs->blocksize >> 9) ||
 210                     (inode->i_block[0] < fs->super->s_first_data_block) ||
 211                     (inode->i_block[0] >= ext2fs_blocks_count(fs->super)))
 212                         return 0;
 213
 214                 for (i = 1; i < EXT2_N_BLOCKS; i++)
 215                         if (inode->i_block[i])
 216                                 return 0;
 217
 218                 if (io_channel_read_blk64(fs->io, inode->i_block[0], 1, buf))
 219                         return 0;
 220
 221                 len = strnlen(buf, fs->blocksize);
 222                 if (len == fs->blocksize)
 223                         return 0;
 224         } else {
 225                 if (inode->i_size >= sizeof(inode->i_block))
 226                         return 0;
 227
 228                 len = strnlen((char *)inode->i_block, sizeof(inode->i_block));
 229                 if (len == sizeof(inode->i_block))
 230                         return 0;
 231         }
 232         if (len != inode->i_size)
 233                 return 0;
 234         return 1;
 235 }
 236
 237 /*
 238  * If the immutable (or append-only) flag is set on the inode, offer
 239  * to clear it.
 240  */
 241 #define BAD_SPECIAL_FLAGS (EXT2_IMMUTABLE_FL | EXT2_APPEND_FL)
 242 static void check_immutable(e2fsck_t ctx, struct problem_context *pctx)
 243 {
 244         if (!(pctx->inode->i_flags & BAD_SPECIAL_FLAGS))
 245                 return;
 246
 247         if (!fix_problem(ctx, PR_1_SET_IMMUTABLE, pctx))
 248                 return;
 249
 250         pctx->inode->i_flags &= ~BAD_SPECIAL_FLAGS;
 251         e2fsck_write_inode(ctx, pctx->ino, pctx->inode, "pass1");
 252 }
 253
 254 /*
 255  * If device, fifo or socket, check size is zero -- if not offer to
 256  * clear it
 257  */
 258 static void check_size(e2fsck_t ctx, struct problem_context *pctx)
 259 {
 260         struct ext2_inode *inode = pctx->inode;
 261
 262         if (EXT2_I_SIZE(inode) == 0)
 263                 return;
 264
 265         if (!fix_problem(ctx, PR_1_SET_NONZSIZE, pctx))
 266                 return;
 267
 268         inode->i_size = 0;
 269         inode->i_size_high = 0;
 270         e2fsck_write_inode(ctx, pctx->ino, pctx->inode, "pass1");
 271 }
 272
 273 static void check_ea_in_inode(e2fsck_t ctx, struct problem_context *pctx)
 274 {
 275         struct ext2_super_block *sb = ctx->fs->super;
 276         struct ext2_inode_large *inode;
 277         struct ext2_ext_attr_entry *entry;
 278         char *start;
 279         unsigned int storage_size, remain;
 280         problem_t problem = 0;
 281
 282         inode = (struct ext2_inode_large *) pctx->inode;
 283         storage_size = EXT2_INODE_SIZE(ctx->fs->super) - EXT2_GOOD_OLD_INODE_SIZE -
 284                 inode->i_extra_isize;
 285         start = ((char *) inode) + EXT2_GOOD_OLD_INODE_SIZE +
 286                 inode->i_extra_isize + sizeof(__u32);
 287         entry = (struct ext2_ext_attr_entry *) start;
 288
 289         /* scan all entry's headers first */
 290
 291         /* take finish entry 0UL into account */
 292         remain = storage_size - sizeof(__u32);
 293
 294         while (!EXT2_EXT_IS_LAST_ENTRY(entry)) {
 295                 __u32 hash;
 296
 297                 /* header eats this space */
 298                 remain -= sizeof(struct ext2_ext_attr_entry);
 299
 300                 /* is attribute name valid? */
 301                 if (EXT2_EXT_ATTR_SIZE(entry->e_name_len) > remain) {
 302                         pctx->num = entry->e_name_len;
 303                         problem = PR_1_ATTR_NAME_LEN;
 304                         goto fix;
 305                 }
 306
 307                 /* attribute len eats this space */
 308                 remain -= EXT2_EXT_ATTR_SIZE(entry->e_name_len);
 309
 310                 /* check value size */
 311                 if (entry->e_value_size > remain) {
 312                         pctx->num = entry->e_value_size;
 313                         problem = PR_1_ATTR_VALUE_SIZE;
 314                         goto fix;
 315                 }
 316
 317                 /* e_value_block must be 0 in inode's ea */
 318                 if (entry->e_value_block != 0) {
 319                         pctx->num = entry->e_value_block;
 320                         problem = PR_1_ATTR_VALUE_BLOCK;
 321                         goto fix;
 322                 }
 323
 324                 hash = ext2fs_ext_attr_hash_entry(entry,
 325                                                   start + entry->e_value_offs);
 326
 327                 /* e_hash may be 0 in older inode's ea */
 328                 if (entry->e_hash != 0 && entry->e_hash != hash) {
 329                         pctx->num = entry->e_hash;
 330                         problem = PR_1_ATTR_HASH;
 331                         goto fix;
 332                 }
 333
 334                 remain -= entry->e_value_size;
 335
 336                 entry = EXT2_EXT_ATTR_NEXT(entry);
 337         }
 338 fix:
 339         /*
 340          * it seems like a corruption. it's very unlikely we could repair
 341          * EA(s) in automatic fashion -bzzz
 342          */
 343         if (problem == 0 || !fix_problem(ctx, problem, pctx))
 344                 return;
 345
 346         /* simply remove all possible EA(s) */
 347         *((__u32 *)start) = 0UL;
 348         e2fsck_write_inode_full(ctx, pctx->ino, pctx->inode,
 349                                 EXT2_INODE_SIZE(sb), "pass1");
 350 }
 351
 352 static void check_inode_extra_space(e2fsck_t ctx, struct problem_context *pctx)
 353 {
 354         struct ext2_super_block *sb = ctx->fs->super;
 355         struct ext2_inode_large *inode;
 356         __u32 *eamagic;
 357         int min, max;
 358
 359         inode = (struct ext2_inode_large *) pctx->inode;
 360         if (EXT2_INODE_SIZE(sb) == EXT2_GOOD_OLD_INODE_SIZE) {
 361                 /* this isn't large inode. so, nothing to check */
 362                 return;
 363         }
 364
 365 #if 0
 366         printf("inode #%u, i_extra_size %d\n", pctx->ino,
 367                         inode->i_extra_isize);
 368 #endif
 369         /* i_extra_isize must cover i_extra_isize + i_checksum_hi at least */
 370         min = sizeof(inode->i_extra_isize) + sizeof(inode->i_checksum_hi);
 371         max = EXT2_INODE_SIZE(sb) - EXT2_GOOD_OLD_INODE_SIZE;
 372         /*
 373          * For now we will allow i_extra_isize to be 0, but really
 374          * implementations should never allow i_extra_isize to be 0
 375          */
 376         if (inode->i_extra_isize &&
 377             (inode->i_extra_isize < min || inode->i_extra_isize > max)) {
 378                 if (!fix_problem(ctx, PR_1_EXTRA_ISIZE, pctx))
 379                         return;
 380                 inode->i_extra_isize = min;
 381                 e2fsck_write_inode_full(ctx, pctx->ino, pctx->inode,
 382                                         EXT2_INODE_SIZE(sb), "pass1");
 383                 return;
 384         }
 385
 386         eamagic = (__u32 *) (((char *) inode) + EXT2_GOOD_OLD_INODE_SIZE +
 387                         inode->i_extra_isize);
 388         if (*eamagic == EXT2_EXT_ATTR_MAGIC) {
 389                 /* it seems inode has an extended attribute(s) in body */
 390                 check_ea_in_inode(ctx, pctx);
 391         }
 392 }
 393
 394 /*
 395  * Check to see if the inode might really be a directory, despite i_mode
 396  *
 397  * This is a lot of complexity for something for which I'm not really
 398  * convinced happens frequently in the wild.  If for any reason this
 399  * causes any problems, take this code out.
 400  * [tytso:20070331.0827EDT]
 401  */
 402 static void check_is_really_dir(e2fsck_t ctx, struct problem_context *pctx,
 403                                 char *buf)
 404 {
 405         struct ext2_inode *inode = pctx->inode;
 406         struct ext2_dir_entry   *dirent;
 407         errcode_t               retval;
 408         blk64_t                 blk;
 409         unsigned int            i, rec_len, not_device = 0;
 410         int                     extent_fs;
 411
 412         /*
 413          * If the mode looks OK, we believe it.  If the first block in
 414          * the i_block array is 0, this cannot be a directory. If the
 415          * inode is extent-mapped, it is still the case that the latter
 416          * cannot be 0 - the magic number in the extent header would make
 417          * it nonzero.
 418          */
 419         if (LINUX_S_ISDIR(inode->i_mode) || LINUX_S_ISREG(inode->i_mode) ||
 420             LINUX_S_ISLNK(inode->i_mode) || inode->i_block[0] == 0)
 421                 return;
 422
 423         /*
 424          * Check the block numbers in the i_block array for validity:
 425          * zero blocks are skipped (but the first one cannot be zero -
 426          * see above), other blocks are checked against the first and
 427          * max data blocks (from the the superblock) and against the
 428          * block bitmap. Any invalid block found means this cannot be
 429          * a directory.
 430          *
 431          * If there are non-zero blocks past the fourth entry, then
 432          * this cannot be a device file: we remember that for the next
 433          * check.
 434          *
 435          * For extent mapped files, we don't do any sanity checking:
 436          * just try to get the phys block of logical block 0 and run
 437          * with it.
 438          */
 439
 440         extent_fs = (ctx->fs->super->s_feature_incompat &
 441                      EXT3_FEATURE_INCOMPAT_EXTENTS);
 442         if (extent_fs && (inode->i_flags & EXT4_EXTENTS_FL)) {
 443                 /* extent mapped */
 444                 if  (ext2fs_bmap2(ctx->fs, pctx->ino, inode, 0, 0, 0, 0,
 445                                  &blk))
 446                         return;
 447                 /* device files are never extent mapped */
 448                 not_device++;
 449         } else {
 450                 for (i=0; i < EXT2_N_BLOCKS; i++) {
 451                         blk = inode->i_block[i];
 452                         if (!blk)
 453                                 continue;
 454                         if (i >= 4)
 455                                 not_device++;
 456
 457                         if (blk < ctx->fs->super->s_first_data_block ||
 458                             blk >= ext2fs_blocks_count(ctx->fs->super) ||
 459                             ext2fs_fast_test_block_bitmap2(ctx->block_found_map,
 460                                                            blk))
 461                                 return; /* Invalid block, can't be dir */
 462                 }
 463                 blk = inode->i_block[0];
 464         }
 465
 466         /*
 467          * If the mode says this is a device file and the i_links_count field
 468          * is sane and we have not ruled it out as a device file previously,
 469          * we declare it a device file, not a directory.
 470          */
 471         if ((LINUX_S_ISCHR(inode->i_mode) || LINUX_S_ISBLK(inode->i_mode)) &&
 472             (inode->i_links_count == 1) && !not_device)
 473                 return;
 474
 475         /* read the first block */
 476         ehandler_operation(_("reading directory block"));
 477         retval = ext2fs_read_dir_block3(ctx->fs, blk, buf, 0);
 478         ehandler_operation(0);
 479         if (retval)
 480                 return;
 481
 482         dirent = (struct ext2_dir_entry *) buf;
 483         retval = ext2fs_get_rec_len(ctx->fs, dirent, &rec_len);
 484         if (retval)
 485                 return;
 486         if (((dirent->name_len & 0xFF) != 1) ||
 487             (dirent->name[0] != '.') ||
 488             (dirent->inode != pctx->ino) ||
 489             (rec_len < 12) ||
 490             (rec_len % 4) ||
 491             (rec_len >= ctx->fs->blocksize - 12))
 492                 return;
 493
 494         dirent = (struct ext2_dir_entry *) (buf + rec_len);
 495         retval = ext2fs_get_rec_len(ctx->fs, dirent, &rec_len);
 496         if (retval)
 497                 return;
 498         if (((dirent->name_len & 0xFF) != 2) ||
 499             (dirent->name[0] != '.') ||
 500             (dirent->name[1] != '.') ||
 501             (rec_len < 12) ||
 502             (rec_len % 4))
 503                 return;
 504
 505         if (fix_problem(ctx, PR_1_TREAT_AS_DIRECTORY, pctx)) {
 506                 inode->i_mode = (inode->i_mode & 07777) | LINUX_S_IFDIR;
 507                 e2fsck_write_inode_full(ctx, pctx->ino, inode,
 508                                         EXT2_INODE_SIZE(ctx->fs->super),
 509                                         "check_is_really_dir");
 510         }
 511 }
 512
 513 void e2fsck_setup_tdb_icount(e2fsck_t ctx, int flags,
 514                              ext2_icount_t *ret)
 515 {
 516         unsigned int            threshold;
 517         ext2_ino_t              num_dirs;
 518         errcode_t               retval;
 519         char                    *tdb_dir;
 520         int                     enable;
 521
 522         *ret = 0;
 523
 524         profile_get_string(ctx->profile, "scratch_files", "directory", 0, 0,
 525                            &tdb_dir);
 526         profile_get_uint(ctx->profile, "scratch_files",
 527                          "numdirs_threshold", 0, 0, &threshold);
 528         profile_get_boolean(ctx->profile, "scratch_files",
 529                             "icount", 0, 1, &enable);
 530
 531         retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs);
 532         if (retval)
 533                 num_dirs = 1024;        /* Guess */
 534
 535         if (!enable || !tdb_dir || access(tdb_dir, W_OK) ||
 536             (threshold && num_dirs <= threshold))
 537                 return;
 538
 539         retval = ext2fs_create_icount_tdb(ctx->fs, tdb_dir, flags, ret);
 540         if (retval)
 541                 *ret = 0;
 542 }
 543
 544 void e2fsck_pass1(e2fsck_t ctx)
 545 {
 546         int     i;
 547         __u64   max_sizes;
 548         ext2_filsys fs = ctx->fs;
 549         ext2_ino_t      ino = 0;
 550         struct ext2_inode *inode = NULL;
 551         ext2_inode_scan scan = NULL;
 552         char            *block_buf = NULL;
 553 #ifdef RESOURCE_TRACK
 554         struct resource_track   rtrack;
 555 #endif
 556         unsigned char   frag, fsize;
 557         struct          problem_context pctx;
 558         struct          scan_callback_struct scan_struct;
 559         struct ext2_super_block *sb = ctx->fs->super;
 560         const char      *old_op;
 561         unsigned int    save_type;
 562         int             imagic_fs, extent_fs;
 563         int             low_dtime_check = 1;
 564         int             inode_size;
 565
 566         init_resource_track(&rtrack, ctx->fs->io);
 567         clear_problem_context(&pctx);
 568
 569         if (!(ctx->options & E2F_OPT_PREEN))
 570                 fix_problem(ctx, PR_1_PASS_HEADER, &pctx);
 571
 572         if ((fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) &&
 573             !(ctx->options & E2F_OPT_NO)) {
 574                 if (ext2fs_u32_list_create(&ctx->dirs_to_hash, 50))
 575                         ctx->dirs_to_hash = 0;
 576         }
 577
 578 #ifdef MTRACE
 579         mtrace_print("Pass 1");
 580 #endif
 581
 582 #define EXT2_BPP(bits) (1ULL << ((bits) - 2))
 583
 584         for (i = EXT2_MIN_BLOCK_LOG_SIZE; i <= EXT2_MAX_BLOCK_LOG_SIZE; i++) {
 585                 max_sizes = EXT2_NDIR_BLOCKS + EXT2_BPP(i);
 586                 max_sizes = max_sizes + EXT2_BPP(i) * EXT2_BPP(i);
 587                 max_sizes = max_sizes + EXT2_BPP(i) * EXT2_BPP(i) * EXT2_BPP(i);
 588                 max_sizes = (max_sizes * (1UL << i));
 589                 ext2_max_sizes[i - EXT2_MIN_BLOCK_LOG_SIZE] = max_sizes;
 590         }
 591 #undef EXT2_BPP
 592
 593         imagic_fs = (sb->s_feature_compat & EXT2_FEATURE_COMPAT_IMAGIC_INODES);
 594         extent_fs = (sb->s_feature_incompat & EXT3_FEATURE_INCOMPAT_EXTENTS);
 595
 596         /*
 597          * Allocate bitmaps structures
 598          */
 599         pctx.errcode = e2fsck_allocate_inode_bitmap(fs, _("in-use inode map"),
 600                                                     EXT2FS_BMAP64_RBTREE,
 601                                                     "inode_used_map",
 602                                                     &ctx->inode_used_map);
 603         if (pctx.errcode) {
 604                 pctx.num = 1;
 605                 fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
 606                 ctx->flags |= E2F_FLAG_ABORT;
 607                 return;
 608         }
 609         pctx.errcode = e2fsck_allocate_inode_bitmap(fs,
 610                         _("directory inode map"),
 611                         EXT2FS_BMAP64_AUTODIR,
 612                         "inode_dir_map", &ctx->inode_dir_map);
 613         if (pctx.errcode) {
 614                 pctx.num = 2;
 615                 fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
 616                 ctx->flags |= E2F_FLAG_ABORT;
 617                 return;
 618         }
 619         pctx.errcode = e2fsck_allocate_inode_bitmap(fs,
 620                         _("regular file inode map"), EXT2FS_BMAP64_RBTREE,
 621                         "inode_reg_map", &ctx->inode_reg_map);
 622         if (pctx.errcode) {
 623                 pctx.num = 6;
 624                 fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
 625                 ctx->flags |= E2F_FLAG_ABORT;
 626                 return;
 627         }
 628         pctx.errcode = e2fsck_allocate_subcluster_bitmap(fs,
 629                         _("in-use block map"), EXT2FS_BMAP64_RBTREE,
 630                         "block_found_map", &ctx->block_found_map);
 631         if (pctx.errcode) {
 632                 pctx.num = 1;
 633                 fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR, &pctx);
 634                 ctx->flags |= E2F_FLAG_ABORT;
 635                 return;
 636         }
 637         e2fsck_setup_tdb_icount(ctx, 0, &ctx->inode_link_info);
 638         if (!ctx->inode_link_info) {
 639                 e2fsck_set_bitmap_type(fs, EXT2FS_BMAP64_RBTREE,
 640                                        "inode_link_info", &save_type);
 641                 pctx.errcode = ext2fs_create_icount2(fs, 0, 0, 0,
 642                                                      &ctx->inode_link_info);
 643                 fs->default_bitmap_type = save_type;
 644         }
 645
 646         if (pctx.errcode) {
 647                 fix_problem(ctx, PR_1_ALLOCATE_ICOUNT, &pctx);
 648                 ctx->flags |= E2F_FLAG_ABORT;
 649                 return;
 650         }
 651         inode_size = EXT2_INODE_SIZE(fs->super);
 652         inode = (struct ext2_inode *)
 653                 e2fsck_allocate_memory(ctx, inode_size, "scratch inode");
 654
 655         inodes_to_process = (struct process_inode_block *)
 656                 e2fsck_allocate_memory(ctx,
 657                                        (ctx->process_inode_size *
 658                                         sizeof(struct process_inode_block)),
 659                                        "array of inodes to process");
 660         process_inode_count = 0;
 661
 662         pctx.errcode = ext2fs_init_dblist(fs, 0);
 663         if (pctx.errcode) {
 664                 fix_problem(ctx, PR_1_ALLOCATE_DBCOUNT, &pctx);
 665                 ctx->flags |= E2F_FLAG_ABORT;
 666                 goto endit;
 667         }
 668
 669         /*
 670          * If the last orphan field is set, clear it, since the pass1
 671          * processing will automatically find and clear the orphans.
 672          * In the future, we may want to try using the last_orphan
 673          * linked list ourselves, but for now, we clear it so that the
 674          * ext3 mount code won't get confused.
 675          */
 676         if (!(ctx->options & E2F_OPT_READONLY)) {
 677                 if (fs->super->s_last_orphan) {
 678                         fs->super->s_last_orphan = 0;
 679                         ext2fs_mark_super_dirty(fs);
 680                 }
 681         }
 682
 683         mark_table_blocks(ctx);
 684         pctx.errcode = ext2fs_convert_subcluster_bitmap(fs,
 685                                                 &ctx->block_found_map);
 686         if (pctx.errcode) {
 687                 fix_problem(ctx, PR_1_CONVERT_SUBCLUSTER, &pctx);
 688                 ctx->flags |= E2F_FLAG_ABORT;
 689                 goto endit;
 690         }
 691         block_buf = (char *) e2fsck_allocate_memory(ctx, fs->blocksize * 3,
 692                                                     "block interate buffer");
 693         e2fsck_use_inode_shortcuts(ctx, 1);
 694         e2fsck_intercept_block_allocations(ctx);
 695         old_op = ehandler_operation(_("opening inode scan"));
 696         pctx.errcode = ext2fs_open_inode_scan(fs, ctx->inode_buffer_blocks,
 697                                               &scan);
 698         ehandler_operation(old_op);
 699         if (pctx.errcode) {
 700                 fix_problem(ctx, PR_1_ISCAN_ERROR, &pctx);
 701                 ctx->flags |= E2F_FLAG_ABORT;
 702                 goto endit;
 703         }
 704         ext2fs_inode_scan_flags(scan, EXT2_SF_SKIP_MISSING_ITABLE, 0);
 705         ctx->stashed_inode = inode;
 706         scan_struct.ctx = ctx;
 707         scan_struct.block_buf = block_buf;
 708         ext2fs_set_inode_callback(scan, scan_callback, &scan_struct);
 709         if (ctx->progress && ((ctx->progress)(ctx, 1, 0,
 710                                               ctx->fs->group_desc_count)))
 711                 goto endit;
 712         if ((fs->super->s_wtime < fs->super->s_inodes_count) ||
 713             (fs->super->s_mtime < fs->super->s_inodes_count) ||
 714             (fs->super->s_mkfs_time &&
 715              fs->super->s_mkfs_time < fs->super->s_inodes_count))
 716                 low_dtime_check = 0;
 717
 718         if ((fs->super->s_feature_incompat & EXT4_FEATURE_INCOMPAT_MMP) &&
 719             fs->super->s_mmp_block > fs->super->s_first_data_block &&
 720             fs->super->s_mmp_block < ext2fs_blocks_count(fs->super))
 721                 ext2fs_mark_block_bitmap2(ctx->block_found_map,
 722                                           fs->super->s_mmp_block);
 723
 724         while (1) {
 725                 if (ino % (fs->super->s_inodes_per_group * 4) == 1) {
 726                         if (e2fsck_mmp_update(fs))
 727                                 fatal_error(ctx, 0);
 728                 }
 729                 old_op = ehandler_operation(_("getting next inode from scan"));
 730                 pctx.errcode = ext2fs_get_next_inode_full(scan, &ino,
 731                                                           inode, inode_size);
 732                 ehandler_operation(old_op);
 733                 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
 734                         return;
 735                 if (pctx.errcode == EXT2_ET_BAD_BLOCK_IN_INODE_TABLE) {
 736                         if (!ctx->inode_bb_map)
 737                                 alloc_bb_map(ctx);
 738                         ext2fs_mark_inode_bitmap2(ctx->inode_bb_map, ino);
 739                         ext2fs_mark_inode_bitmap2(ctx->inode_used_map, ino);
 740                         continue;
 741                 }
 742                 if (pctx.errcode) {
 743                         fix_problem(ctx, PR_1_ISCAN_ERROR, &pctx);
 744                         ctx->flags |= E2F_FLAG_ABORT;
 745                         goto endit;
 746                 }
 747                 if (!ino)
 748                         break;
 749                 pctx.ino = ino;
 750                 pctx.inode = inode;
 751                 ctx->stashed_ino = ino;
 752                 if (inode->i_links_count) {
 753                         pctx.errcode = ext2fs_icount_store(ctx->inode_link_info,
 754                                            ino, inode->i_links_count);
 755                         if (pctx.errcode) {
 756                                 pctx.num = inode->i_links_count;
 757                                 fix_problem(ctx, PR_1_ICOUNT_STORE, &pctx);
 758                                 ctx->flags |= E2F_FLAG_ABORT;
 759                                 goto endit;
 760                         }
 761                 }
 762
 763                 /*
 764                  * Test for incorrect extent flag settings.
 765                  *
 766                  * On big-endian machines we must be careful:
 767                  * When the inode is read, the i_block array is not swapped
 768                  * if the extent flag is set.  Therefore if we are testing
 769                  * for or fixing a wrongly-set flag, we must potentially
 770                  * (un)swap before testing, or after fixing.
 771                  */
 772
 773                 /*
 774                  * In this case the extents flag was set when read, so
 775                  * extent_header_verify is ok.  If the inode is cleared,
 776                  * no need to swap... so no extra swapping here.
 777                  */
 778                 if ((inode->i_flags & EXT4_EXTENTS_FL) && !extent_fs &&
 779                     (inode->i_links_count || (ino == EXT2_BAD_INO) ||
 780                      (ino == EXT2_ROOT_INO) || (ino == EXT2_JOURNAL_INO))) {
 781                         if ((ext2fs_extent_header_verify(inode->i_block,
 782                                                  sizeof(inode->i_block)) == 0) &&
 783                             fix_problem(ctx, PR_1_EXTENT_FEATURE, &pctx)) {
 784                                 sb->s_feature_incompat |= EXT3_FEATURE_INCOMPAT_EXTENTS;
 785                                 ext2fs_mark_super_dirty(fs);
 786                                 extent_fs = 1;
 787                         } else if (fix_problem(ctx, PR_1_EXTENTS_SET, &pctx)) {
 788                         clear_inode:
 789                                 e2fsck_clear_inode(ctx, ino, inode, 0, "pass1");
 790                                 if (ino == EXT2_BAD_INO)
 791                                         ext2fs_mark_inode_bitmap2(ctx->inode_used_map,
 792                                                                  ino);
 793                                 continue;
 794                         }
 795                 }
 796
 797                 /*
 798                  * For big-endian machines:
 799                  * If the inode didn't have the extents flag set when it
 800                  * was read, then the i_blocks array was swapped.  To test
 801                  * as an extents header, we must swap it back first.
 802                  * IF we then set the extents flag, the entire i_block
 803                  * array must be un/re-swapped to make it proper extents data.
 804                  */
 805                 if (extent_fs && !(inode->i_flags & EXT4_EXTENTS_FL) &&
 806                     (inode->i_links_count || (ino == EXT2_BAD_INO) ||
 807                      (ino == EXT2_ROOT_INO) || (ino == EXT2_JOURNAL_INO)) &&
 808                     (LINUX_S_ISREG(inode->i_mode) ||
 809                      LINUX_S_ISDIR(inode->i_mode))) {
 810                         void *ehp;
 811 #ifdef WORDS_BIGENDIAN
 812                         __u32 tmp_block[EXT2_N_BLOCKS];
 813
 814                         for (i = 0; i < EXT2_N_BLOCKS; i++)
 815                                 tmp_block[i] = ext2fs_swab32(inode->i_block[i]);
 816                         ehp = tmp_block;
 817 #else
 818                         ehp = inode->i_block;
 819 #endif
 820                         if ((ext2fs_extent_header_verify(ehp,
 821                                          sizeof(inode->i_block)) == 0) &&
 822                             (fix_problem(ctx, PR_1_UNSET_EXTENT_FL, &pctx))) {
 823                                 inode->i_flags |= EXT4_EXTENTS_FL;
 824 #ifdef WORDS_BIGENDIAN
 825                                 memcpy(inode->i_block, tmp_block,
 826                                        sizeof(inode->i_block));
 827 #endif
 828                                 e2fsck_write_inode(ctx, ino, inode, "pass1");
 829                         }
 830                 }
 831
 832                 if (ino == EXT2_BAD_INO) {
 833                         struct process_block_struct pb;
 834
 835                         if ((inode->i_mode || inode->i_uid || inode->i_gid ||
 836                              inode->i_links_count || inode->i_file_acl) &&
 837                             fix_problem(ctx, PR_1_INVALID_BAD_INODE, &pctx)) {
 838                                 memset(inode, 0, sizeof(struct ext2_inode));
 839                                 e2fsck_write_inode(ctx, ino, inode,
 840                                                    "clear bad inode");
 841                         }
 842
 843                         pctx.errcode = ext2fs_copy_bitmap(ctx->block_found_map,
 844                                                           &pb.fs_meta_blocks);
 845                         if (pctx.errcode) {
 846                                 pctx.num = 4;
 847                                 fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR, &pctx);
 848                                 ctx->flags |= E2F_FLAG_ABORT;
 849                                 goto endit;
 850                         }
 851                         pb.ino = EXT2_BAD_INO;
 852                         pb.num_blocks = pb.last_block = 0;
 853                         pb.last_db_block = -1;
 854                         pb.num_illegal_blocks = 0;
 855                         pb.suppress = 0; pb.clear = 0; pb.is_dir = 0;
 856                         pb.is_reg = 0; pb.fragmented = 0; pb.bbcheck = 0;
 857                         pb.inode = inode;
 858                         pb.pctx = &pctx;
 859                         pb.ctx = ctx;
 860                         pctx.errcode = ext2fs_block_iterate3(fs, ino, 0,
 861                                      block_buf, process_bad_block, &pb);
 862                         ext2fs_free_block_bitmap(pb.fs_meta_blocks);
 863                         if (pctx.errcode) {
 864                                 fix_problem(ctx, PR_1_BLOCK_ITERATE, &pctx);
 865                                 ctx->flags |= E2F_FLAG_ABORT;
 866                                 goto endit;
 867                         }
 868                         if (pb.bbcheck)
 869                                 if (!fix_problem(ctx, PR_1_BBINODE_BAD_METABLOCK_PROMPT, &pctx)) {
 870                                 ctx->flags |= E2F_FLAG_ABORT;
 871                                 goto endit;
 872                         }
 873                         ext2fs_mark_inode_bitmap2(ctx->inode_used_map, ino);
 874                         clear_problem_context(&pctx);
 875                         continue;
 876                 } else if (ino == EXT2_ROOT_INO) {
 877                         /*
 878                          * Make sure the root inode is a directory; if
 879                          * not, offer to clear it.  It will be
 880                          * regnerated in pass #3.
 881                          */
 882                         if (!LINUX_S_ISDIR(inode->i_mode)) {
 883                                 if (fix_problem(ctx, PR_1_ROOT_NO_DIR, &pctx))
 884                                         goto clear_inode;
 885                         }
 886                         /*
 887                          * If dtime is set, offer to clear it.  mke2fs
 888                          * version 0.2b created filesystems with the
 889                          * dtime field set for the root and lost+found
 890                          * directories.  We won't worry about
 891                          * /lost+found, since that can be regenerated
 892                          * easily.  But we will fix the root directory
 893                          * as a special case.
 894                          */
 895                         if (inode->i_dtime && inode->i_links_count) {
 896                                 if (fix_problem(ctx, PR_1_ROOT_DTIME, &pctx)) {
 897                                         inode->i_dtime = 0;
 898                                         e2fsck_write_inode(ctx, ino, inode,
 899                                                            "pass1");
 900                                 }
 901                         }
 902                 } else if (ino == EXT2_JOURNAL_INO) {
 903                         ext2fs_mark_inode_bitmap2(ctx->inode_used_map, ino);
 904                         if (fs->super->s_journal_inum == EXT2_JOURNAL_INO) {
 905                                 if (!LINUX_S_ISREG(inode->i_mode) &&
 906                                     fix_problem(ctx, PR_1_JOURNAL_BAD_MODE,
 907                                                 &pctx)) {
 908                                         inode->i_mode = LINUX_S_IFREG;
 909                                         e2fsck_write_inode(ctx, ino, inode,
 910                                                            "pass1");
 911                                 }
 912                                 check_blocks(ctx, &pctx, block_buf);
 913                                 continue;
 914                         }
 915                         if ((inode->i_links_count ||
 916                              inode->i_blocks || inode->i_block[0]) &&
 917                             fix_problem(ctx, PR_1_JOURNAL_INODE_NOT_CLEAR,
 918                                         &pctx)) {
 919                                 memset(inode, 0, inode_size);
 920                                 ext2fs_icount_store(ctx->inode_link_info,
 921                                                     ino, 0);
 922                                 e2fsck_write_inode_full(ctx, ino, inode,
 923                                                         inode_size, "pass1");
 924                         }
 925                 } else if ((ino == EXT4_USR_QUOTA_INO) ||
 926                            (ino == EXT4_GRP_QUOTA_INO)) {
 927                         ext2fs_mark_inode_bitmap2(ctx->inode_used_map, ino);
 928                         if ((fs->super->s_feature_ro_compat &
 929                                         EXT4_FEATURE_RO_COMPAT_QUOTA) &&
 930                             ((fs->super->s_usr_quota_inum == ino) ||
 931                              (fs->super->s_grp_quota_inum == ino))) {
 932                                 if (!LINUX_S_ISREG(inode->i_mode) &&
 933                                     fix_problem(ctx, PR_1_QUOTA_BAD_MODE,
 934                                                         &pctx)) {
 935                                         inode->i_mode = LINUX_S_IFREG;
 936                                         e2fsck_write_inode(ctx, ino, inode,
 937                                                         "pass1");
 938                                 }
 939                                 check_blocks(ctx, &pctx, block_buf);
 940                                 continue;
 941                         }
 942                         if ((inode->i_links_count ||
 943                              inode->i_blocks || inode->i_block[0]) &&
 944                             fix_problem(ctx, PR_1_QUOTA_INODE_NOT_CLEAR,
 945                                         &pctx)) {
 946                                 memset(inode, 0, inode_size);
 947                                 ext2fs_icount_store(ctx->inode_link_info,
 948                                                     ino, 0);
 949                                 e2fsck_write_inode_full(ctx, ino, inode,
 950                                                         inode_size, "pass1");
 951                         }
 952                 } else if (ino < EXT2_FIRST_INODE(fs->super)) {
 953                         problem_t problem = 0;
 954
 955                         ext2fs_mark_inode_bitmap2(ctx->inode_used_map, ino);
 956                         if (ino == EXT2_BOOT_LOADER_INO) {
 957                                 if (LINUX_S_ISDIR(inode->i_mode))
 958                                         problem = PR_1_RESERVED_BAD_MODE;
 959                         } else if (ino == EXT2_RESIZE_INO) {
 960                                 if (inode->i_mode &&
 961                                     !LINUX_S_ISREG(inode->i_mode))
 962                                         problem = PR_1_RESERVED_BAD_MODE;
 963                         } else {
 964                                 if (inode->i_mode != 0)
 965                                         problem = PR_1_RESERVED_BAD_MODE;
 966                         }
 967                         if (problem) {
 968                                 if (fix_problem(ctx, problem, &pctx)) {
 969                                         inode->i_mode = 0;
 970                                         e2fsck_write_inode(ctx, ino, inode,
 971                                                            "pass1");
 972                                 }
 973                         }
 974                         check_blocks(ctx, &pctx, block_buf);
 975                         continue;
 976                 }
 977
 978                 /*
 979                  * Check for inodes who might have been part of the
 980                  * orphaned list linked list.  They should have gotten
 981                  * dealt with by now, unless the list had somehow been
 982                  * corrupted.
 983                  *
 984                  * FIXME: In the future, inodes which are still in use
 985                  * (and which are therefore) pending truncation should
 986                  * be handled specially.  Right now we just clear the
 987                  * dtime field, and the normal e2fsck handling of
 988                  * inodes where i_size and the inode blocks are
 989                  * inconsistent is to fix i_size, instead of releasing
 990                  * the extra blocks.  This won't catch the inodes that
 991                  * was at the end of the orphan list, but it's better
 992                  * than nothing.  The right answer is that there
 993                  * shouldn't be any bugs in the orphan list handling.  :-)
 994                  */
 995                 if (inode->i_dtime && low_dtime_check &&
 996                     inode->i_dtime < ctx->fs->super->s_inodes_count) {
 997                         if (fix_problem(ctx, PR_1_LOW_DTIME, &pctx)) {
 998                                 inode->i_dtime = inode->i_links_count ?
 999                                         0 : ctx->now;
1000                                 e2fsck_write_inode(ctx, ino, inode,
1001                                                    "pass1");
1002                         }
1003                 }
1004
1005                 /*
1006                  * This code assumes that deleted inodes have
1007                  * i_links_count set to 0.
1008                  */
1009                 if (!inode->i_links_count) {
1010                         if (!inode->i_dtime && inode->i_mode) {
1011                                 if (fix_problem(ctx,
1012                                             PR_1_ZERO_DTIME, &pctx)) {
1013                                         inode->i_dtime = ctx->now;
1014                                         e2fsck_write_inode(ctx, ino, inode,
1015                                                            "pass1");
1016                                 }
1017                         }
1018                         continue;
1019                 }
1020                 /*
1021                  * n.b.  0.3c ext2fs code didn't clear i_links_count for
1022                  * deleted files.  Oops.
1023                  *
1024                  * Since all new ext2 implementations get this right,
1025                  * we now assume that the case of non-zero
1026                  * i_links_count and non-zero dtime means that we
1027                  * should keep the file, not delete it.
1028                  *
1029                  */
1030                 if (inode->i_dtime) {
1031                         if (fix_problem(ctx, PR_1_SET_DTIME, &pctx)) {
1032                                 inode->i_dtime = 0;
1033                                 e2fsck_write_inode(ctx, ino, inode, "pass1");
1034                         }
1035                 }
1036
1037                 ext2fs_mark_inode_bitmap2(ctx->inode_used_map, ino);
1038                 switch (fs->super->s_creator_os) {
1039                     case EXT2_OS_HURD:
1040                         frag = inode->osd2.hurd2.h_i_frag;
1041                         fsize = inode->osd2.hurd2.h_i_fsize;
1042                         break;
1043                     default:
1044                         frag = fsize = 0;
1045                 }
1046
1047                 if (inode->i_faddr || frag || fsize ||
1048                     (LINUX_S_ISDIR(inode->i_mode) && inode->i_dir_acl))
1049                         mark_inode_bad(ctx, ino);
1050                 if (!(fs->super->s_feature_incompat &
1051                       EXT4_FEATURE_INCOMPAT_64BIT) &&
1052                     inode->osd2.linux2.l_i_file_acl_high != 0)
1053                         mark_inode_bad(ctx, ino);
1054                 if ((fs->super->s_creator_os == EXT2_OS_LINUX) &&
1055                     !(fs->super->s_feature_ro_compat &
1056                       EXT4_FEATURE_RO_COMPAT_HUGE_FILE) &&
1057                     (inode->osd2.linux2.l_i_blocks_hi != 0))
1058                         mark_inode_bad(ctx, ino);
1059                 if (inode->i_flags & EXT2_IMAGIC_FL) {
1060                         if (imagic_fs) {
1061                                 if (!ctx->inode_imagic_map)
1062                                         alloc_imagic_map(ctx);
1063                                 ext2fs_mark_inode_bitmap2(ctx->inode_imagic_map,
1064                                                          ino);
1065                         } else {
1066                                 if (fix_problem(ctx, PR_1_SET_IMAGIC, &pctx)) {
1067                                         inode->i_flags &= ~EXT2_IMAGIC_FL;
1068                                         e2fsck_write_inode(ctx, ino,
1069                                                            inode, "pass1");
1070                                 }
1071                         }
1072                 }
1073
1074                 check_inode_extra_space(ctx, &pctx);
1075                 check_is_really_dir(ctx, &pctx, block_buf);
1076
1077                 /*
1078                  * ext2fs_inode_has_valid_blocks2 does not actually look
1079                  * at i_block[] values, so not endian-sensitive here.
1080                  */
1081                 if (extent_fs && (inode->i_flags & EXT4_EXTENTS_FL) &&
1082                     LINUX_S_ISLNK(inode->i_mode) &&
1083                     !ext2fs_inode_has_valid_blocks2(fs, inode) &&
1084                     fix_problem(ctx, PR_1_FAST_SYMLINK_EXTENT_FL, &pctx)) {
1085                         inode->i_flags &= ~EXT4_EXTENTS_FL;
1086                         e2fsck_write_inode(ctx, ino, inode, "pass1");
1087                 }
1088
1089                 if (LINUX_S_ISDIR(inode->i_mode)) {
1090                         ext2fs_mark_inode_bitmap2(ctx->inode_dir_map, ino);
1091                         e2fsck_add_dir_info(ctx, ino, 0);
1092                         ctx->fs_directory_count++;
1093                 } else if (LINUX_S_ISREG (inode->i_mode)) {
1094                         ext2fs_mark_inode_bitmap2(ctx->inode_reg_map, ino);
1095                         ctx->fs_regular_count++;
1096                 } else if (LINUX_S_ISCHR (inode->i_mode) &&
1097                            e2fsck_pass1_check_device_inode(fs, inode)) {
1098                         check_immutable(ctx, &pctx);
1099                         check_size(ctx, &pctx);
1100                         ctx->fs_chardev_count++;
1101                 } else if (LINUX_S_ISBLK (inode->i_mode) &&
1102                            e2fsck_pass1_check_device_inode(fs, inode)) {
1103                         check_immutable(ctx, &pctx);
1104                         check_size(ctx, &pctx);
1105                         ctx->fs_blockdev_count++;
1106                 } else if (LINUX_S_ISLNK (inode->i_mode) &&
1107                            e2fsck_pass1_check_symlink(fs, ino, inode,
1108                                                       block_buf)) {
1109                         check_immutable(ctx, &pctx);
1110                         ctx->fs_symlinks_count++;
1111                         if (ext2fs_inode_data_blocks(fs, inode) == 0) {
1112                                 ctx->fs_fast_symlinks_count++;
1113                                 check_blocks(ctx, &pctx, block_buf);
1114                                 continue;
1115                         }
1116                 }
1117                 else if (LINUX_S_ISFIFO (inode->i_mode) &&
1118                          e2fsck_pass1_check_device_inode(fs, inode)) {
1119                         check_immutable(ctx, &pctx);
1120                         check_size(ctx, &pctx);
1121                         ctx->fs_fifo_count++;
1122                 } else if ((LINUX_S_ISSOCK (inode->i_mode)) &&
1123                            e2fsck_pass1_check_device_inode(fs, inode)) {
1124                         check_immutable(ctx, &pctx);
1125                         check_size(ctx, &pctx);
1126                         ctx->fs_sockets_count++;
1127                 } else
1128                         mark_inode_bad(ctx, ino);
1129                 if (!(inode->i_flags & EXT4_EXTENTS_FL)) {
1130                         if (inode->i_block[EXT2_IND_BLOCK])
1131                                 ctx->fs_ind_count++;
1132                         if (inode->i_block[EXT2_DIND_BLOCK])
1133                                 ctx->fs_dind_count++;
1134                         if (inode->i_block[EXT2_TIND_BLOCK])
1135                                 ctx->fs_tind_count++;
1136                 }
1137                 if (!(inode->i_flags & EXT4_EXTENTS_FL) &&
1138                     (inode->i_block[EXT2_IND_BLOCK] ||
1139                      inode->i_block[EXT2_DIND_BLOCK] ||
1140                      inode->i_block[EXT2_TIND_BLOCK] ||
1141                      ext2fs_file_acl_block(fs, inode))) {
1142                         inodes_to_process[process_inode_count].ino = ino;
1143                         inodes_to_process[process_inode_count].inode = *inode;
1144                         process_inode_count++;
1145                 } else
1146                         check_blocks(ctx, &pctx, block_buf);
1147
1148                 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
1149                         goto endit;
1150
1151                 if (process_inode_count >= ctx->process_inode_size) {
1152                         process_inodes(ctx, block_buf);
1153
1154                         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
1155                                 goto endit;
1156                 }
1157         }
1158         process_inodes(ctx, block_buf);
1159         ext2fs_close_inode_scan(scan);
1160         scan = NULL;
1161
1162         /*
1163          * If any extended attribute blocks' reference counts need to
1164          * be adjusted, either up (ctx->refcount_extra), or down
1165          * (ctx->refcount), then fix them.
1166          */
1167         if (ctx->refcount) {
1168                 adjust_extattr_refcount(ctx, ctx->refcount, block_buf, -1);
1169                 ea_refcount_free(ctx->refcount);
1170                 ctx->refcount = 0;
1171         }
1172         if (ctx->refcount_extra) {
1173                 adjust_extattr_refcount(ctx, ctx->refcount_extra,
1174                                         block_buf, +1);
1175                 ea_refcount_free(ctx->refcount_extra);
1176                 ctx->refcount_extra = 0;
1177         }
1178
1179         if (ctx->invalid_bitmaps)
1180                 handle_fs_bad_blocks(ctx);
1181
1182         /* We don't need the block_ea_map any more */
1183         if (ctx->block_ea_map) {
1184                 ext2fs_free_block_bitmap(ctx->block_ea_map);
1185                 ctx->block_ea_map = 0;
1186         }
1187
1188         if (ctx->flags & E2F_FLAG_RESIZE_INODE) {
1189                 clear_problem_context(&pctx);
1190                 pctx.errcode = ext2fs_create_resize_inode(fs);
1191                 if (pctx.errcode) {
1192                         if (!fix_problem(ctx, PR_1_RESIZE_INODE_CREATE,
1193                                          &pctx)) {
1194                                 ctx->flags |= E2F_FLAG_ABORT;
1195                                 goto endit;
1196                         }
1197                         pctx.errcode = 0;
1198                 }
1199                 if (!pctx.errcode) {
1200                         e2fsck_read_inode(ctx, EXT2_RESIZE_INO, inode,
1201                                           "recreate inode");
1202                         inode->i_mtime = ctx->now;
1203                         e2fsck_write_inode(ctx, EXT2_RESIZE_INO, inode,
1204                                            "recreate inode");
1205                 }
1206                 ctx->flags &= ~E2F_FLAG_RESIZE_INODE;
1207         }
1208
1209         if (ctx->flags & E2F_FLAG_RESTART) {
1210                 /*
1211                  * Only the master copy of the superblock and block
1212                  * group descriptors are going to be written during a
1213                  * restart, so set the superblock to be used to be the
1214                  * master superblock.
1215                  */
1216                 ctx->use_superblock = 0;
1217                 unwind_pass1(fs);
1218                 goto endit;
1219         }
1220
1221         if (ctx->block_dup_map) {
1222                 if (ctx->options & E2F_OPT_PREEN) {
1223                         clear_problem_context(&pctx);
1224                         fix_problem(ctx, PR_1_DUP_BLOCKS_PREENSTOP, &pctx);
1225                 }
1226                 e2fsck_pass1_dupblocks(ctx, block_buf);
1227         }
1228         ext2fs_free_mem(&inodes_to_process);
1229 endit:
1230         e2fsck_use_inode_shortcuts(ctx, 0);
1231
1232         if (scan)
1233                 ext2fs_close_inode_scan(scan);
1234         if (block_buf)
1235                 ext2fs_free_mem(&block_buf);
1236         if (inode)
1237                 ext2fs_free_mem(&inode);
1238
1239         if ((ctx->flags & E2F_FLAG_SIGNAL_MASK) == 0)
1240                 print_resource_track(ctx, _("Pass 1"), &rtrack, ctx->fs->io);
1241 }
1242
1243 /*
1244  * When the inode_scan routines call this callback at the end of the
1245  * glock group, call process_inodes.
1246  */
1247 static errcode_t scan_callback(ext2_filsys fs,
1248                                ext2_inode_scan scan EXT2FS_ATTR((unused)),
1249                                dgrp_t group, void * priv_data)
1250 {
1251         struct scan_callback_struct *scan_struct;
1252         e2fsck_t ctx;
1253
1254         scan_struct = (struct scan_callback_struct *) priv_data;
1255         ctx = scan_struct->ctx;
1256
1257         process_inodes((e2fsck_t) fs->priv_data, scan_struct->block_buf);
1258
1259         if (ctx->progress)
1260                 if ((ctx->progress)(ctx, 1, group+1,
1261                                     ctx->fs->group_desc_count))
1262                         return EXT2_ET_CANCEL_REQUESTED;
1263
1264         return 0;
1265 }
1266
1267 /*
1268  * Process the inodes in the "inodes to process" list.
1269  */
1270 static void process_inodes(e2fsck_t ctx, char *block_buf)
1271 {
1272         int                     i;
1273         struct ext2_inode       *old_stashed_inode;
1274         ext2_ino_t              old_stashed_ino;
1275         const char              *old_operation;
1276         char                    buf[80];
1277         struct problem_context  pctx;
1278
1279 #if 0
1280         printf("begin process_inodes: ");
1281 #endif
1282         if (process_inode_count == 0)
1283                 return;
1284         old_operation = ehandler_operation(0);
1285         old_stashed_inode = ctx->stashed_inode;
1286         old_stashed_ino = ctx->stashed_ino;
1287         qsort(inodes_to_process, process_inode_count,
1288                       sizeof(struct process_inode_block), process_inode_cmp);
1289         clear_problem_context(&pctx);
1290         for (i=0; i < process_inode_count; i++) {
1291                 pctx.inode = ctx->stashed_inode = &inodes_to_process[i].inode;
1292                 pctx.ino = ctx->stashed_ino = inodes_to_process[i].ino;
1293
1294 #if 0
1295                 printf("%u ", pctx.ino);
1296 #endif
1297                 sprintf(buf, _("reading indirect blocks of inode %u"),
1298                         pctx.ino);
1299                 ehandler_operation(buf);
1300                 check_blocks(ctx, &pctx, block_buf);
1301                 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
1302                         break;
1303         }
1304         ctx->stashed_inode = old_stashed_inode;
1305         ctx->stashed_ino = old_stashed_ino;
1306         process_inode_count = 0;
1307 #if 0
1308         printf("end process inodes\n");
1309 #endif
1310         ehandler_operation(old_operation);
1311 }
1312
1313 static EXT2_QSORT_TYPE process_inode_cmp(const void *a, const void *b)
1314 {
1315         const struct process_inode_block *ib_a =
1316                 (const struct process_inode_block *) a;
1317         const struct process_inode_block *ib_b =
1318                 (const struct process_inode_block *) b;
1319         int     ret;
1320
1321         ret = (ib_a->inode.i_block[EXT2_IND_BLOCK] -
1322                ib_b->inode.i_block[EXT2_IND_BLOCK]);
1323         if (ret == 0)
1324                 /*
1325                  * We only call process_inodes() for non-extent
1326                  * inodes, so it's OK to pass NULL to
1327                  * ext2fs_file_acl_block() here.
1328                  */
1329                 ret = ext2fs_file_acl_block(0, &(ib_a->inode)) -
1330                         ext2fs_file_acl_block(0, &(ib_b->inode));
1331         if (ret == 0)
1332                 ret = ib_a->ino - ib_b->ino;
1333         return ret;
1334 }
1335
1336 /*
1337  * Mark an inode as being bad in some what
1338  */
1339 static void mark_inode_bad(e2fsck_t ctx, ino_t ino)
1340 {
1341         struct          problem_context pctx;
1342
1343         if (!ctx->inode_bad_map) {
1344                 clear_problem_context(&pctx);
1345
1346                 pctx.errcode = e2fsck_allocate_inode_bitmap(ctx->fs,
1347                                 _("bad inode map"), EXT2FS_BMAP64_RBTREE,
1348                                 "inode_bad_map", &ctx->inode_bad_map);
1349                 if (pctx.errcode) {
1350                         pctx.num = 3;
1351                         fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
1352                         /* Should never get here */
1353                         ctx->flags |= E2F_FLAG_ABORT;
1354                         return;
1355                 }
1356         }
1357         ext2fs_mark_inode_bitmap2(ctx->inode_bad_map, ino);
1358 }
1359
1360
1361 /*
1362  * This procedure will allocate the inode "bb" (badblock) map table
1363  */
1364 static void alloc_bb_map(e2fsck_t ctx)
1365 {
1366         struct          problem_context pctx;
1367
1368         clear_problem_context(&pctx);
1369         pctx.errcode = e2fsck_allocate_inode_bitmap(ctx->fs,
1370                         _("inode in bad block map"), EXT2FS_BMAP64_RBTREE,
1371                         "inode_bb_map", &ctx->inode_bb_map);
1372         if (pctx.errcode) {
1373                 pctx.num = 4;
1374                 fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
1375                 /* Should never get here */
1376                 ctx->flags |= E2F_FLAG_ABORT;
1377                 return;
1378         }
1379 }
1380
1381 /*
1382  * This procedure will allocate the inode imagic table
1383  */
1384 static void alloc_imagic_map(e2fsck_t ctx)
1385 {
1386         struct          problem_context pctx;
1387
1388         clear_problem_context(&pctx);
1389         pctx.errcode = e2fsck_allocate_inode_bitmap(ctx->fs,
1390                         _("imagic inode map"), EXT2FS_BMAP64_RBTREE,
1391                         "inode_imagic_map", &ctx->inode_imagic_map);
1392         if (pctx.errcode) {
1393                 pctx.num = 5;
1394                 fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
1395                 /* Should never get here */
1396                 ctx->flags |= E2F_FLAG_ABORT;
1397                 return;
1398         }
1399 }
1400
1401 /*
1402  * Marks a block as in use, setting the dup_map if it's been set
1403  * already.  Called by process_block and process_bad_block.
1404  *
1405  * WARNING: Assumes checks have already been done to make sure block
1406  * is valid.  This is true in both process_block and process_bad_block.
1407  */
1408 static _INLINE_ void mark_block_used(e2fsck_t ctx, blk64_t block)
1409 {
1410         struct          problem_context pctx;
1411
1412         clear_problem_context(&pctx);
1413
1414         if (ext2fs_fast_test_block_bitmap2(ctx->block_found_map, block)) {
1415                 if (!ctx->block_dup_map) {
1416                         pctx.errcode = e2fsck_allocate_block_bitmap(ctx->fs,
1417                                         _("multiply claimed block map"),
1418                                         EXT2FS_BMAP64_RBTREE, "block_dup_map",
1419                                         &ctx->block_dup_map);
1420                         if (pctx.errcode) {
1421                                 pctx.num = 3;
1422                                 fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR,
1423                                             &pctx);
1424                                 /* Should never get here */
1425                                 ctx->flags |= E2F_FLAG_ABORT;
1426                                 return;
1427                         }
1428                 }
1429                 ext2fs_fast_mark_block_bitmap2(ctx->block_dup_map, block);
1430         } else {
1431                 ext2fs_fast_mark_block_bitmap2(ctx->block_found_map, block);
1432         }
1433 }
1434
1435 static _INLINE_ void mark_blocks_used(e2fsck_t ctx, blk64_t block,
1436                                       unsigned int num)
1437 {
1438         if (ext2fs_test_block_bitmap_range2(ctx->block_found_map, block, num))
1439                 ext2fs_mark_block_bitmap_range2(ctx->block_found_map, block, num);
1440         else
1441                 while (num--)
1442                         mark_block_used(ctx, block++);
1443 }
1444
1445 /*
1446  * Adjust the extended attribute block's reference counts at the end
1447  * of pass 1, either by subtracting out references for EA blocks that
1448  * are still referenced in ctx->refcount, or by adding references for
1449  * EA blocks that had extra references as accounted for in
1450  * ctx->refcount_extra.
1451  */
1452 static void adjust_extattr_refcount(e2fsck_t ctx, ext2_refcount_t refcount,
1453                                     char *block_buf, int adjust_sign)
1454 {
1455         struct ext2_ext_attr_header     *header;
1456         struct problem_context          pctx;
1457         ext2_filsys                     fs = ctx->fs;
1458         blk64_t                         blk;
1459         __u32                           should_be;
1460         int                             count;
1461
1462         clear_problem_context(&pctx);
1463
1464         ea_refcount_intr_begin(refcount);
1465         while (1) {
1466                 if ((blk = ea_refcount_intr_next(refcount, &count)) == 0)
1467                         break;
1468                 pctx.blk = blk;
1469                 pctx.errcode = ext2fs_read_ext_attr2(fs, blk, block_buf);
1470                 if (pctx.errcode) {
1471                         fix_problem(ctx, PR_1_EXTATTR_READ_ABORT, &pctx);
1472                         return;
1473                 }
1474                 header = (struct ext2_ext_attr_header *) block_buf;
1475                 pctx.blkcount = header->h_refcount;
1476                 should_be = header->h_refcount + adjust_sign * count;
1477                 pctx.num = should_be;
1478                 if (fix_problem(ctx, PR_1_EXTATTR_REFCOUNT, &pctx)) {
1479                         header->h_refcount = should_be;
1480                         pctx.errcode = ext2fs_write_ext_attr2(fs, blk,
1481                                                              block_buf);
1482                         if (pctx.errcode) {
1483                                 fix_problem(ctx, PR_1_EXTATTR_WRITE_ABORT,
1484                                             &pctx);
1485                                 continue;
1486                         }
1487                 }
1488         }
1489 }
1490
1491 /*
1492  * Handle processing the extended attribute blocks
1493  */
1494 static int check_ext_attr(e2fsck_t ctx, struct problem_context *pctx,
1495                            char *block_buf)
1496 {
1497         ext2_filsys fs = ctx->fs;
1498         ext2_ino_t      ino = pctx->ino;
1499         struct ext2_inode *inode = pctx->inode;
1500         blk64_t         blk;
1501         char *          end;
1502         struct ext2_ext_attr_header *header;
1503         struct ext2_ext_attr_entry *entry;
1504         int             count;
1505         region_t        region = 0;
1506
1507         blk = ext2fs_file_acl_block(fs, inode);
1508         if (blk == 0)
1509                 return 0;
1510
1511         /*
1512          * If the Extended attribute flag isn't set, then a non-zero
1513          * file acl means that the inode is corrupted.
1514          *
1515          * Or if the extended attribute block is an invalid block,
1516          * then the inode is also corrupted.
1517          */
1518         if (!(fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_EXT_ATTR) ||
1519             (blk < fs->super->s_first_data_block) ||
1520             (blk >= ext2fs_blocks_count(fs->super))) {
1521                 mark_inode_bad(ctx, ino);
1522                 return 0;
1523         }
1524
1525         /* If ea bitmap hasn't been allocated, create it */
1526         if (!ctx->block_ea_map) {
1527                 pctx->errcode = e2fsck_allocate_block_bitmap(fs,
1528                                         _("ext attr block map"),
1529                                         EXT2FS_BMAP64_RBTREE, "block_ea_map",
1530                                         &ctx->block_ea_map);
1531                 if (pctx->errcode) {
1532                         pctx->num = 2;
1533                         fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR, pctx);
1534                         ctx->flags |= E2F_FLAG_ABORT;
1535                         return 0;
1536                 }
1537         }
1538
1539         /* Create the EA refcount structure if necessary */
1540         if (!ctx->refcount) {
1541                 pctx->errcode = ea_refcount_create(0, &ctx->refcount);
1542                 if (pctx->errcode) {
1543                         pctx->num = 1;
1544                         fix_problem(ctx, PR_1_ALLOCATE_REFCOUNT, pctx);
1545                         ctx->flags |= E2F_FLAG_ABORT;
1546                         return 0;
1547                 }
1548         }
1549
1550 #if 0
1551         /* Debugging text */
1552         printf("Inode %u has EA block %u\n", ino, blk);
1553 #endif
1554
1555         /* Have we seen this EA block before? */
1556         if (ext2fs_fast_test_block_bitmap2(ctx->block_ea_map, blk)) {
1557                 if (ea_refcount_decrement(ctx->refcount, blk, 0) == 0)
1558                         return 1;
1559                 /* Ooops, this EA was referenced more than it stated */
1560                 if (!ctx->refcount_extra) {
1561                         pctx->errcode = ea_refcount_create(0,
1562                                            &ctx->refcount_extra);
1563                         if (pctx->errcode) {
1564                                 pctx->num = 2;
1565                                 fix_problem(ctx, PR_1_ALLOCATE_REFCOUNT, pctx);
1566                                 ctx->flags |= E2F_FLAG_ABORT;
1567                                 return 0;
1568                         }
1569                 }
1570                 ea_refcount_increment(ctx->refcount_extra, blk, 0);
1571                 return 1;
1572         }
1573
1574         /*
1575          * OK, we haven't seen this EA block yet.  So we need to
1576          * validate it
1577          */
1578         pctx->blk = blk;
1579         pctx->errcode = ext2fs_read_ext_attr2(fs, blk, block_buf);
1580         if (pctx->errcode && fix_problem(ctx, PR_1_READ_EA_BLOCK, pctx))
1581                 goto clear_extattr;
1582         header = (struct ext2_ext_attr_header *) block_buf;
1583         pctx->blk = ext2fs_file_acl_block(fs, inode);
1584         if (((ctx->ext_attr_ver == 1) &&
1585              (header->h_magic != EXT2_EXT_ATTR_MAGIC_v1)) ||
1586             ((ctx->ext_attr_ver == 2) &&
1587              (header->h_magic != EXT2_EXT_ATTR_MAGIC))) {
1588                 if (fix_problem(ctx, PR_1_BAD_EA_BLOCK, pctx))
1589                         goto clear_extattr;
1590         }
1591
1592         if (header->h_blocks != 1) {
1593                 if (fix_problem(ctx, PR_1_EA_MULTI_BLOCK, pctx))
1594                         goto clear_extattr;
1595         }
1596
1597         region = region_create(0, fs->blocksize);
1598         if (!region) {
1599                 fix_problem(ctx, PR_1_EA_ALLOC_REGION_ABORT, pctx);
1600                 ctx->flags |= E2F_FLAG_ABORT;
1601                 return 0;
1602         }
1603         if (region_allocate(region, 0, sizeof(struct ext2_ext_attr_header))) {
1604                 if (fix_problem(ctx, PR_1_EA_ALLOC_COLLISION, pctx))
1605                         goto clear_extattr;
1606         }
1607
1608         entry = (struct ext2_ext_attr_entry *)(header+1);
1609         end = block_buf + fs->blocksize;
1610         while ((char *)entry < end && *(__u32 *)entry) {
1611                 __u32 hash;
1612
1613                 if (region_allocate(region, (char *)entry - (char *)header,
1614                                    EXT2_EXT_ATTR_LEN(entry->e_name_len))) {
1615                         if (fix_problem(ctx, PR_1_EA_ALLOC_COLLISION, pctx))
1616                                 goto clear_extattr;
1617                         break;
1618                 }
1619                 if ((ctx->ext_attr_ver == 1 &&
1620                      (entry->e_name_len == 0 || entry->e_name_index != 0)) ||
1621                     (ctx->ext_attr_ver == 2 &&
1622                      entry->e_name_index == 0)) {
1623                         if (fix_problem(ctx, PR_1_EA_BAD_NAME, pctx))
1624                                 goto clear_extattr;
1625                         break;
1626                 }
1627                 if (entry->e_value_block != 0) {
1628                         if (fix_problem(ctx, PR_1_EA_BAD_VALUE, pctx))
1629                                 goto clear_extattr;
1630                 }
1631                 if (entry->e_value_offs + entry->e_value_size > fs->blocksize) {
1632                         if (fix_problem(ctx, PR_1_EA_BAD_VALUE, pctx))
1633                                 goto clear_extattr;
1634                         break;
1635                 }
1636                 if (entry->e_value_size &&
1637                     region_allocate(region, entry->e_value_offs,
1638                                     EXT2_EXT_ATTR_SIZE(entry->e_value_size))) {
1639                         if (fix_problem(ctx, PR_1_EA_ALLOC_COLLISION, pctx))
1640                                 goto clear_extattr;
1641                 }
1642
1643                 hash = ext2fs_ext_attr_hash_entry(entry, block_buf +
1644                                                          entry->e_value_offs);
1645
1646                 if (entry->e_hash != hash) {
1647                         pctx->num = entry->e_hash;
1648                         if (fix_problem(ctx, PR_1_ATTR_HASH, pctx))
1649                                 goto clear_extattr;
1650                         entry->e_hash = hash;
1651                 }
1652
1653                 entry = EXT2_EXT_ATTR_NEXT(entry);
1654         }
1655         if (region_allocate(region, (char *)entry - (char *)header, 4)) {
1656                 if (fix_problem(ctx, PR_1_EA_ALLOC_COLLISION, pctx))
1657                         goto clear_extattr;
1658         }
1659         region_free(region);
1660
1661         count = header->h_refcount - 1;
1662         if (count)
1663                 ea_refcount_store(ctx->refcount, blk, count);
1664         mark_block_used(ctx, blk);
1665         ext2fs_fast_mark_block_bitmap2(ctx->block_ea_map, blk);
1666         return 1;
1667
1668 clear_extattr:
1669         if (region)
1670                 region_free(region);
1671         ext2fs_file_acl_block_set(fs, inode, 0);
1672         e2fsck_write_inode(ctx, ino, inode, "check_ext_attr");
1673         return 0;
1674 }
1675
1676 /* Returns 1 if bad htree, 0 if OK */
1677 static int handle_htree(e2fsck_t ctx, struct problem_context *pctx,
1678                         ext2_ino_t ino, struct ext2_inode *inode,
1679                         char *block_buf)
1680 {
1681         struct ext2_dx_root_info        *root;
1682         ext2_filsys                     fs = ctx->fs;
1683         errcode_t                       retval;
1684         blk64_t                         blk;
1685
1686         if ((!LINUX_S_ISDIR(inode->i_mode) &&
1687              fix_problem(ctx, PR_1_HTREE_NODIR, pctx)) ||
1688             (!(fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) &&
1689              fix_problem(ctx, PR_1_HTREE_SET, pctx)))
1690                 return 1;
1691
1692         pctx->errcode = ext2fs_bmap2(fs, ino, inode, 0, 0, 0, 0, &blk);
1693
1694         if ((pctx->errcode) ||
1695             (blk == 0) ||
1696             (blk < fs->super->s_first_data_block) ||
1697             (blk >= ext2fs_blocks_count(fs->super))) {
1698                 if (fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
1699                         return 1;
1700                 else
1701                         return 0;
1702         }
1703
1704         retval = io_channel_read_blk64(fs->io, blk, 1, block_buf);
1705         if (retval && fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
1706                 return 1;
1707
1708         /* XXX should check that beginning matches a directory */
1709         root = (struct ext2_dx_root_info *) (block_buf + 24);
1710
1711         if ((root->reserved_zero || root->info_length < 8) &&
1712             fix_problem(ctx, PR_1_HTREE_BADROOT, pctx))
1713                 return 1;
1714
1715         pctx->num = root->hash_version;
1716         if ((root->hash_version != EXT2_HASH_LEGACY) &&
1717             (root->hash_version != EXT2_HASH_HALF_MD4) &&
1718             (root->hash_version != EXT2_HASH_TEA) &&
1719             fix_problem(ctx, PR_1_HTREE_HASHV, pctx))
1720                 return 1;
1721
1722         if ((root->unused_flags & EXT2_HASH_FLAG_INCOMPAT) &&
1723             fix_problem(ctx, PR_1_HTREE_INCOMPAT, pctx))
1724                 return 1;
1725
1726         pctx->num = root->indirect_levels;
1727         if ((root->indirect_levels > 1) &&
1728             fix_problem(ctx, PR_1_HTREE_DEPTH, pctx))
1729                 return 1;
1730
1731         return 0;
1732 }
1733
1734 void e2fsck_clear_inode(e2fsck_t ctx, ext2_ino_t ino,
1735                         struct ext2_inode *inode, int restart_flag,
1736                         const char *source)
1737 {
1738         inode->i_flags = 0;
1739         inode->i_links_count = 0;
1740         ext2fs_icount_store(ctx->inode_link_info, ino, 0);
1741         inode->i_dtime = ctx->now;
1742
1743         ext2fs_unmark_inode_bitmap2(ctx->inode_dir_map, ino);
1744         ext2fs_unmark_inode_bitmap2(ctx->inode_used_map, ino);
1745         if (ctx->inode_reg_map)
1746                 ext2fs_unmark_inode_bitmap2(ctx->inode_reg_map, ino);
1747         if (ctx->inode_bad_map)
1748                 ext2fs_unmark_inode_bitmap2(ctx->inode_bad_map, ino);
1749
1750         /*
1751          * If the inode was partially accounted for before processing
1752          * was aborted, we need to restart the pass 1 scan.
1753          */
1754         ctx->flags |= restart_flag;
1755
1756         if (ino == EXT2_BAD_INO)
1757                 memset(inode, 0, sizeof(struct ext2_inode));
1758
1759         e2fsck_write_inode(ctx, ino, inode, source);
1760 }
1761
1762 static void scan_extent_node(e2fsck_t ctx, struct problem_context *pctx,
1763                              struct process_block_struct *pb,
1764                              blk64_t start_block, blk64_t end_block,
1765                              blk64_t eof_block,
1766                              ext2_extent_handle_t ehandle)
1767 {
1768         struct ext2fs_extent    extent;
1769         blk64_t                 blk, last_lblk;
1770         e2_blkcnt_t             blockcnt;
1771         unsigned int            i;
1772         int                     is_dir, is_leaf;
1773         problem_t               problem;
1774         struct ext2_extent_info info;
1775
1776         pctx->errcode = ext2fs_extent_get_info(ehandle, &info);
1777         if (pctx->errcode)
1778                 return;
1779
1780         pctx->errcode = ext2fs_extent_get(ehandle, EXT2_EXTENT_FIRST_SIB,
1781                                           &extent);
1782         while (!pctx->errcode && info.num_entries-- > 0) {
1783                 is_leaf = extent.e_flags & EXT2_EXTENT_FLAGS_LEAF;
1784                 is_dir = LINUX_S_ISDIR(pctx->inode->i_mode);
1785                 last_lblk = extent.e_lblk + extent.e_len - 1;
1786
1787                 problem = 0;
1788                 if (extent.e_pblk == 0 ||
1789                     extent.e_pblk < ctx->fs->super->s_first_data_block ||
1790                     extent.e_pblk >= ext2fs_blocks_count(ctx->fs->super))
1791                         problem = PR_1_EXTENT_BAD_START_BLK;
1792                 else if (extent.e_lblk < start_block)
1793                         problem = PR_1_OUT_OF_ORDER_EXTENTS;
1794                 else if ((end_block && last_lblk > end_block) &&
1795                          (!(extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT &&
1796                                 last_lblk > eof_block)))
1797                         problem = PR_1_EXTENT_END_OUT_OF_BOUNDS;
1798                 else if (is_leaf && extent.e_len == 0)
1799                         problem = PR_1_EXTENT_LENGTH_ZERO;
1800                 else if (is_leaf &&
1801                          (extent.e_pblk + extent.e_len) >
1802                          ext2fs_blocks_count(ctx->fs->super))
1803                         problem = PR_1_EXTENT_ENDS_BEYOND;
1804                 else if (is_leaf && is_dir &&
1805                          ((extent.e_lblk + extent.e_len) >
1806                           (1 << (21 - ctx->fs->super->s_log_block_size))))
1807                         problem = PR_1_TOOBIG_DIR;
1808
1809                 if (problem) {
1810 report_problem:
1811                         pctx->blk = extent.e_pblk;
1812                         pctx->blk2 = extent.e_lblk;
1813                         pctx->num = extent.e_len;
1814                         pctx->blkcount = extent.e_lblk + extent.e_len;
1815                         if (fix_problem(ctx, problem, pctx)) {
1816                                 if (ctx->invalid_bitmaps) {
1817                                         /*
1818                                          * If fsck knows the bitmaps are bad,
1819                                          * skip to the next extent and
1820                                          * try to clear this extent again
1821                                          * after fixing the bitmaps, by
1822                                          * restarting fsck.
1823                                          */
1824                                         pctx->errcode = ext2fs_extent_get(
1825                                                           ehandle,
1826                                                           EXT2_EXTENT_NEXT_SIB,
1827                                                           &extent);
1828                                         ctx->flags |= E2F_FLAG_RESTART_LATER;
1829                                         if (pctx->errcode ==
1830                                                     EXT2_ET_NO_CURRENT_NODE) {
1831                                                 pctx->errcode = 0;
1832                                                 break;
1833                                         }
1834                                         continue;
1835                                 }
1836                                 e2fsck_read_bitmaps(ctx);
1837                                 pb->inode_modified = 1;
1838                                 pctx->errcode =
1839                                         ext2fs_extent_delete(ehandle, 0);
1840                                 if (pctx->errcode) {
1841                                         pctx->str = "ext2fs_extent_delete";
1842                                         return;
1843                                 }
1844                                 pctx->errcode = ext2fs_extent_fix_parents(ehandle);
1845                                 if (pctx->errcode &&
1846                                     pctx->errcode != EXT2_ET_NO_CURRENT_NODE) {
1847                                         pctx->str = "ext2fs_extent_fix_parents";
1848                                         return;
1849                                 }
1850                                 pctx->errcode = ext2fs_extent_get(ehandle,
1851                                                                   EXT2_EXTENT_CURRENT,
1852                                                                   &extent);
1853                                 if (pctx->errcode == EXT2_ET_NO_CURRENT_NODE) {
1854                                         pctx->errcode = 0;
1855                                         break;
1856                                 }
1857                                 continue;
1858                         }
1859                         goto next;
1860                 }
1861
1862                 if (!is_leaf) {
1863                         blk64_t lblk = extent.e_lblk;
1864
1865                         blk = extent.e_pblk;
1866                         pctx->errcode = ext2fs_extent_get(ehandle,
1867                                                   EXT2_EXTENT_DOWN, &extent);
1868                         if (pctx->errcode) {
1869                                 pctx->str = "EXT2_EXTENT_DOWN";
1870                                 problem = PR_1_EXTENT_HEADER_INVALID;
1871                                 if (pctx->errcode == EXT2_ET_EXTENT_HEADER_BAD)
1872                                         goto report_problem;
1873                                 return;
1874                         }
1875                         /* The next extent should match this index's logical start */
1876                         if (extent.e_lblk != lblk) {
1877                                 struct ext2_extent_info e_info;
1878
1879                                 ext2fs_extent_get_info(ehandle, &e_info);
1880                                 pctx->blk = lblk;
1881                                 pctx->blk2 = extent.e_lblk;
1882                                 pctx->num = e_info.curr_level - 1;
1883                                 problem = PR_1_EXTENT_INDEX_START_INVALID;
1884                                 if (fix_problem(ctx, problem, pctx)) {
1885                                         pb->inode_modified = 1;
1886                                         pctx->errcode =
1887                                                 ext2fs_extent_fix_parents(ehandle);
1888                                         if (pctx->errcode) {
1889                                                 pctx->str = "ext2fs_extent_fix_parents";
1890                                                 return;
1891                                         }
1892                                 }
1893                         }
1894                         scan_extent_node(ctx, pctx, pb, extent.e_lblk,
1895                                          last_lblk, eof_block, ehandle);
1896                         if (pctx->errcode)
1897                                 return;
1898                         pctx->errcode = ext2fs_extent_get(ehandle,
1899                                                   EXT2_EXTENT_UP, &extent);
1900                         if (pctx->errcode) {
1901                                 pctx->str = "EXT2_EXTENT_UP";
1902                                 return;
1903                         }
1904                         mark_block_used(ctx, blk);
1905                         pb->num_blocks++;
1906                         goto next;
1907                 }
1908
1909                 if ((pb->previous_block != 0) &&
1910                     (pb->previous_block+1 != extent.e_pblk)) {
1911                         if (ctx->options & E2F_OPT_FRAGCHECK) {
1912                                 char type = '?';
1913
1914                                 if (pb->is_dir)
1915                                         type = 'd';
1916                                 else if (pb->is_reg)
1917                                         type = 'f';
1918
1919                                 printf(("%6lu(%c): expecting %6lu "
1920                                         "actual extent "
1921                                         "phys %6lu log %lu len %lu\n"),
1922                                        (unsigned long) pctx->ino, type,
1923                                        (unsigned long) pb->previous_block+1,
1924                                        (unsigned long) extent.e_pblk,
1925                                        (unsigned long) extent.e_lblk,
1926                                        (unsigned long) extent.e_len);
1927                         }
1928                         pb->fragmented = 1;
1929                 }
1930                 /*
1931                  * If we notice a gap in the logical block mappings of an
1932                  * extent-mapped directory, offer to close the hole by
1933                  * moving the logical block down, otherwise we'll go mad in
1934                  * pass 3 allocating empty directory blocks to fill the hole.
1935                  */
1936                 if (is_dir &&
1937                     pb->last_block + 1 < (e2_blkcnt_t)extent.e_lblk) {
1938                         blk64_t new_lblk;
1939
1940                         new_lblk = pb->last_block + 1;
1941                         if (EXT2FS_CLUSTER_RATIO(ctx->fs) > 1)
1942                                 new_lblk = ((new_lblk +
1943                                              EXT2FS_CLUSTER_RATIO(ctx->fs)) &
1944                                             EXT2FS_CLUSTER_MASK(ctx->fs)) |
1945                                            (extent.e_lblk &
1946                                             EXT2FS_CLUSTER_MASK(ctx->fs));
1947                         pctx->blk = extent.e_lblk;
1948                         pctx->blk2 = new_lblk;
1949                         if (fix_problem(ctx, PR_1_COLLAPSE_DBLOCK, pctx)) {
1950                                 extent.e_lblk = new_lblk;
1951                                 pb->inode_modified = 1;
1952                                 pctx->errcode = ext2fs_extent_replace(ehandle,
1953                                                                 0, &extent);
1954                                 if (pctx->errcode) {
1955                                         pctx->errcode = 0;
1956                                         goto alloc_later;
1957                                 }
1958                                 pctx->errcode = ext2fs_extent_fix_parents(ehandle);
1959                                 if (pctx->errcode)
1960                                         goto failed_add_dir_block;
1961                                 pctx->errcode = ext2fs_extent_goto(ehandle,
1962                                                                 extent.e_lblk);
1963                                 if (pctx->errcode)
1964                                         goto failed_add_dir_block;
1965                                 last_lblk = extent.e_lblk + extent.e_len - 1;
1966                         }
1967                 }
1968 alloc_later:
1969                 while (is_dir && (++pb->last_db_block <
1970                                   (e2_blkcnt_t) extent.e_lblk)) {
1971                         pctx->errcode = ext2fs_add_dir_block2(ctx->fs->dblist,
1972                                                               pb->ino, 0,
1973                                                               pb->last_db_block);
1974                         if (pctx->errcode) {
1975                                 pctx->blk = 0;
1976                                 pctx->num = pb->last_db_block;
1977                                 goto failed_add_dir_block;
1978                         }
1979                 }
1980                 if (!ctx->fs->cluster_ratio_bits) {
1981                         mark_blocks_used(ctx, extent.e_pblk, extent.e_len);
1982                         pb->num_blocks += extent.e_len;
1983                 }
1984                 for (blk = extent.e_pblk, blockcnt = extent.e_lblk, i = 0;
1985                      i < extent.e_len;
1986                      blk++, blockcnt++, i++) {
1987                         if (ctx->fs->cluster_ratio_bits &&
1988                             !(pb->previous_block &&
1989                               (EXT2FS_B2C(ctx->fs, blk) ==
1990                                EXT2FS_B2C(ctx->fs, pb->previous_block)) &&
1991                               (blk & EXT2FS_CLUSTER_MASK(ctx->fs)) ==
1992                               ((unsigned) blockcnt & EXT2FS_CLUSTER_MASK(ctx->fs)))) {
1993                                 mark_block_used(ctx, blk);
1994                                 pb->num_blocks++;
1995                         }
1996
1997                         pb->previous_block = blk;
1998
1999                         if (is_dir) {
2000                                 pctx->errcode = ext2fs_add_dir_block2(ctx->fs->dblist, pctx->ino, blk, blockcnt);
2001                                 if (pctx->errcode) {
2002                                         pctx->blk = blk;
2003                                         pctx->num = blockcnt;
2004                                 failed_add_dir_block:
2005                                         fix_problem(ctx, PR_1_ADD_DBLOCK, pctx);
2006                                         /* Should never get here */
2007                                         ctx->flags |= E2F_FLAG_ABORT;
2008                                         return;
2009                                 }
2010                         }
2011                 }
2012                 if (is_dir && extent.e_len > 0)
2013                         pb->last_db_block = blockcnt - 1;
2014                 pb->previous_block = extent.e_pblk + extent.e_len - 1;
2015                 start_block = pb->last_block = last_lblk;
2016                 if (is_leaf && !is_dir &&
2017                     !(extent.e_flags & EXT2_EXTENT_FLAGS_UNINIT))
2018                         pb->last_init_lblock = last_lblk;
2019         next:
2020                 pctx->errcode = ext2fs_extent_get(ehandle,
2021                                                   EXT2_EXTENT_NEXT_SIB,
2022                                                   &extent);
2023         }
2024         if (pctx->errcode == EXT2_ET_EXTENT_NO_NEXT)
2025                 pctx->errcode = 0;
2026 }
2027
2028 static void check_blocks_extents(e2fsck_t ctx, struct problem_context *pctx,
2029                                  struct process_block_struct *pb)
2030 {
2031         struct ext2_extent_info info;
2032         struct ext2_inode       *inode = pctx->inode;
2033         ext2_extent_handle_t    ehandle;
2034         ext2_filsys             fs = ctx->fs;
2035         ext2_ino_t              ino = pctx->ino;
2036         errcode_t               retval;
2037         blk64_t                 eof_lblk;
2038
2039         pctx->errcode = ext2fs_extent_open2(fs, ino, inode, &ehandle);
2040         if (pctx->errcode) {
2041                 if (fix_problem(ctx, PR_1_READ_EXTENT, pctx))
2042                         e2fsck_clear_inode(ctx, ino, inode, 0,
2043                                            "check_blocks_extents");
2044                 pctx->errcode = 0;
2045                 return;
2046         }
2047
2048         retval = ext2fs_extent_get_info(ehandle, &info);
2049         if (retval == 0) {
2050                 if (info.max_depth >= MAX_EXTENT_DEPTH_COUNT)
2051                         info.max_depth = MAX_EXTENT_DEPTH_COUNT-1;
2052                 ctx->extent_depth_count[info.max_depth]++;
2053         }
2054
2055         eof_lblk = ((EXT2_I_SIZE(inode) + fs->blocksize - 1) >>
2056                 EXT2_BLOCK_SIZE_BITS(fs->super)) - 1;
2057         scan_extent_node(ctx, pctx, pb, 0, 0, eof_lblk, ehandle);
2058         if (pctx->errcode &&
2059             fix_problem(ctx, PR_1_EXTENT_ITERATE_FAILURE, pctx)) {
2060                 pb->num_blocks = 0;
2061                 inode->i_blocks = 0;
2062                 e2fsck_clear_inode(ctx, ino, inode, E2F_FLAG_RESTART,
2063                                    "check_blocks_extents");
2064                 pctx->errcode = 0;
2065         }
2066         ext2fs_extent_free(ehandle);
2067 }
2068
2069 /*
2070  * This subroutine is called on each inode to account for all of the
2071  * blocks used by that inode.
2072  */
2073 static void check_blocks(e2fsck_t ctx, struct problem_context *pctx,
2074                          char *block_buf)
2075 {
2076         ext2_filsys fs = ctx->fs;
2077         struct process_block_struct pb;
2078         ext2_ino_t      ino = pctx->ino;
2079         struct ext2_inode *inode = pctx->inode;
2080         unsigned        bad_size = 0;
2081         int             dirty_inode = 0;
2082         int             extent_fs;
2083         __u64           size;
2084
2085         pb.ino = ino;
2086         pb.num_blocks = 0;
2087         pb.last_block = -1;
2088         pb.last_init_lblock = -1;
2089         pb.last_db_block = -1;
2090         pb.num_illegal_blocks = 0;
2091         pb.suppress = 0; pb.clear = 0;
2092         pb.fragmented = 0;
2093         pb.compressed = 0;
2094         pb.previous_block = 0;
2095         pb.is_dir = LINUX_S_ISDIR(inode->i_mode);
2096         pb.is_reg = LINUX_S_ISREG(inode->i_mode);
2097         pb.max_blocks = 1 << (31 - fs->super->s_log_block_size);
2098         pb.inode = inode;
2099         pb.pctx = pctx;
2100         pb.ctx = ctx;
2101         pb.inode_modified = 0;
2102         pctx->ino = ino;
2103         pctx->errcode = 0;
2104
2105         extent_fs = (ctx->fs->super->s_feature_incompat &
2106                      EXT3_FEATURE_INCOMPAT_EXTENTS);
2107
2108         if (inode->i_flags & EXT2_COMPRBLK_FL) {
2109                 if (fs->super->s_feature_incompat &
2110                     EXT2_FEATURE_INCOMPAT_COMPRESSION)
2111                         pb.compressed = 1;
2112                 else {
2113                         if (fix_problem(ctx, PR_1_COMPR_SET, pctx)) {
2114                                 inode->i_flags &= ~EXT2_COMPRBLK_FL;
2115                                 dirty_inode++;
2116                         }
2117                 }
2118         }
2119
2120         if (ext2fs_file_acl_block(fs, inode) &&
2121             check_ext_attr(ctx, pctx, block_buf)) {
2122                 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
2123                         goto out;
2124                 pb.num_blocks++;
2125         }
2126
2127         if (ext2fs_inode_has_valid_blocks2(fs, inode)) {
2128                 if (extent_fs && (inode->i_flags & EXT4_EXTENTS_FL))
2129                         check_blocks_extents(ctx, pctx, &pb);
2130                 else {
2131                         /*
2132                          * If we've modified the inode, write it out before
2133                          * iterate() tries to use it.
2134                          */
2135                         if (dirty_inode) {
2136                                 e2fsck_write_inode(ctx, ino, inode,
2137                                                    "check_blocks");
2138                                 dirty_inode = 0;
2139                         }
2140                         pctx->errcode = ext2fs_block_iterate3(fs, ino,
2141                                                 pb.is_dir ? BLOCK_FLAG_HOLE : 0,
2142                                                 block_buf, process_block, &pb);
2143                         /*
2144                          * We do not have uninitialized extents in non extent
2145                          * files.
2146                          */
2147                         pb.last_init_lblock = pb.last_block;
2148                         /*
2149                          * If iterate() changed a block mapping, we have to
2150                          * re-read the inode.  If we decide to clear the
2151                          * inode after clearing some stuff, we'll re-write the
2152                          * bad mappings into the inode!
2153                          */
2154                         if (pb.inode_modified)
2155                                 e2fsck_read_inode(ctx, ino, inode,
2156                                                   "check_blocks");
2157                 }
2158         }
2159         end_problem_latch(ctx, PR_LATCH_BLOCK);
2160         end_problem_latch(ctx, PR_LATCH_TOOBIG);
2161         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
2162                 goto out;
2163         if (pctx->errcode)
2164                 fix_problem(ctx, PR_1_BLOCK_ITERATE, pctx);
2165
2166         if (pb.fragmented && pb.num_blocks < fs->super->s_blocks_per_group) {
2167                 if (LINUX_S_ISDIR(inode->i_mode))
2168                         ctx->fs_fragmented_dir++;
2169                 else
2170                         ctx->fs_fragmented++;
2171         }
2172
2173         if (pb.clear) {
2174                 e2fsck_clear_inode(ctx, ino, inode, E2F_FLAG_RESTART,
2175                                    "check_blocks");
2176                 return;
2177         }
2178
2179         if (inode->i_flags & EXT2_INDEX_FL) {
2180                 if (handle_htree(ctx, pctx, ino, inode, block_buf)) {
2181                         inode->i_flags &= ~EXT2_INDEX_FL;
2182                         dirty_inode++;
2183                 } else {
2184 #ifdef ENABLE_HTREE
2185                         e2fsck_add_dx_dir(ctx, ino, pb.last_block+1);
2186 #endif
2187                 }
2188         }
2189
2190         if (!pb.num_blocks && pb.is_dir) {
2191                 if (fix_problem(ctx, PR_1_ZERO_LENGTH_DIR, pctx)) {
2192                         e2fsck_clear_inode(ctx, ino, inode, 0, "check_blocks");
2193                         ctx->fs_directory_count--;
2194                         return;
2195                 }
2196         }
2197
2198         if (ino == EXT2_ROOT_INO || ino >= EXT2_FIRST_INODE(ctx->fs->super)) {
2199                 quota_data_add(ctx->qctx, inode, ino,
2200                                pb.num_blocks * fs->blocksize);
2201                 quota_data_inodes(ctx->qctx, inode, ino, +1);
2202         }
2203
2204         if (!(fs->super->s_feature_ro_compat &
2205               EXT4_FEATURE_RO_COMPAT_HUGE_FILE) ||
2206             !(inode->i_flags & EXT4_HUGE_FILE_FL))
2207                 pb.num_blocks *= (fs->blocksize / 512);
2208         pb.num_blocks *= EXT2FS_CLUSTER_RATIO(fs);
2209 #if 0
2210         printf("inode %u, i_size = %u, last_block = %lld, i_blocks=%llu, num_blocks = %llu\n",
2211                ino, inode->i_size, pb.last_block, ext2fs_inode_i_blocks(fs, inode),
2212                pb.num_blocks);
2213 #endif
2214         if (pb.is_dir) {
2215                 int nblock = inode->i_size >> EXT2_BLOCK_SIZE_BITS(fs->super);
2216                 if (inode->i_size & (fs->blocksize - 1))
2217                         bad_size = 5;
2218                 else if (nblock > (pb.last_block + 1))
2219                         bad_size = 1;
2220                 else if (nblock < (pb.last_block + 1)) {
2221                         if (((pb.last_block + 1) - nblock) >
2222                             fs->super->s_prealloc_dir_blocks)
2223                                 bad_size = 2;
2224                 }
2225         } else {
2226                 e2_blkcnt_t blkpg = ctx->blocks_per_page;
2227
2228                 size = EXT2_I_SIZE(inode);
2229                 if ((pb.last_init_lblock >= 0) &&
2230                     /* allow allocated blocks to end of PAGE_SIZE */
2231                     (size < (__u64)pb.last_init_lblock * fs->blocksize) &&
2232                     (pb.last_init_lblock / blkpg * blkpg != pb.last_init_lblock ||
2233                      size < (__u64)(pb.last_init_lblock & ~(blkpg-1)) *
2234                      fs->blocksize))
2235                         bad_size = 3;
2236                 else if (!(extent_fs && (inode->i_flags & EXT4_EXTENTS_FL)) &&
2237                          size > ext2_max_sizes[fs->super->s_log_block_size])
2238                         /* too big for a direct/indirect-mapped file */
2239                         bad_size = 4;
2240                 else if ((extent_fs && (inode->i_flags & EXT4_EXTENTS_FL)) &&
2241                          size >
2242                          ((1ULL << (32 + EXT2_BLOCK_SIZE_BITS(fs->super))) - 1))
2243                         /* too big for an extent-based file - 32bit ee_block */
2244                         bad_size = 6;
2245         }
2246         /* i_size for symlinks is checked elsewhere */
2247         if (bad_size && !LINUX_S_ISLNK(inode->i_mode)) {
2248                 pctx->num = (pb.last_block+1) * fs->blocksize;
2249                 pctx->group = bad_size;
2250                 if (fix_problem(ctx, PR_1_BAD_I_SIZE, pctx)) {
2251                         inode->i_size = pctx->num;
2252                         if (!LINUX_S_ISDIR(inode->i_mode))
2253                                 inode->i_size_high = pctx->num >> 32;
2254                         dirty_inode++;
2255                 }
2256                 pctx->num = 0;
2257         }
2258         if (LINUX_S_ISREG(inode->i_mode) &&
2259             ext2fs_needs_large_file_feature(EXT2_I_SIZE(inode)))
2260                 ctx->large_files++;
2261         if ((pb.num_blocks != ext2fs_inode_i_blocks(fs, inode)) ||
2262             ((fs->super->s_feature_ro_compat &
2263               EXT4_FEATURE_RO_COMPAT_HUGE_FILE) &&
2264              (inode->i_flags & EXT4_HUGE_FILE_FL) &&
2265              (inode->osd2.linux2.l_i_blocks_hi != 0))) {
2266                 pctx->num = pb.num_blocks;
2267                 if (fix_problem(ctx, PR_1_BAD_I_BLOCKS, pctx)) {
2268                         inode->i_blocks = pb.num_blocks;
2269                         inode->osd2.linux2.l_i_blocks_hi = pb.num_blocks >> 32;
2270                         dirty_inode++;
2271                 }
2272                 pctx->num = 0;
2273         }
2274
2275         if (ctx->dirs_to_hash && pb.is_dir &&
2276             !(inode->i_flags & EXT2_INDEX_FL) &&
2277             ((inode->i_size / fs->blocksize) >= 3))
2278                 ext2fs_u32_list_add(ctx->dirs_to_hash, ino);
2279
2280 out:
2281         if (dirty_inode)
2282                 e2fsck_write_inode(ctx, ino, inode, "check_blocks");
2283 }
2284
2285 #if 0
2286 /*
2287  * Helper function called by process block when an illegal block is
2288  * found.  It returns a description about why the block is illegal
2289  */
2290 static char *describe_illegal_block(ext2_filsys fs, blk64_t block)
2291 {
2292         blk64_t super;
2293         int     i;
2294         static char     problem[80];
2295
2296         super = fs->super->s_first_data_block;
2297         strcpy(problem, "PROGRAMMING ERROR: Unknown reason for illegal block");
2298         if (block < super) {
2299                 sprintf(problem, "< FIRSTBLOCK (%u)", super);
2300                 return(problem);
2301         } else if (block >= ext2fs_blocks_count(fs->super)) {
2302                 sprintf(problem, "> BLOCKS (%u)", ext2fs_blocks_count(fs->super));
2303                 return(problem);
2304         }
2305         for (i = 0; i < fs->group_desc_count; i++) {
2306                 if (block == super) {
2307                         sprintf(problem, "is the superblock in group %d", i);
2308                         break;
2309                 }
2310                 if (block > super &&
2311                     block <= (super + fs->desc_blocks)) {
2312                         sprintf(problem, "is in the group descriptors "
2313                                 "of group %d", i);
2314                         break;
2315                 }
2316                 if (block == ext2fs_block_bitmap_loc(fs, i)) {
2317                         sprintf(problem, "is the block bitmap of group %d", i);
2318                         break;
2319                 }
2320                 if (block == ext2fs_inode_bitmap_loc(fs, i)) {
2321                         sprintf(problem, "is the inode bitmap of group %d", i);
2322                         break;
2323                 }
2324                 if (block >= ext2fs_inode_table_loc(fs, i) &&
2325                     (block < ext2fs_inode_table_loc(fs, i)
2326                      + fs->inode_blocks_per_group)) {
2327                         sprintf(problem, "is in the inode table of group %d",
2328                                 i);
2329                         break;
2330                 }
2331                 super += fs->super->s_blocks_per_group;
2332         }
2333         return(problem);
2334 }
2335 #endif
2336
2337 /*
2338  * This is a helper function for check_blocks().
2339  */
2340 static int process_block(ext2_filsys fs,
2341                   blk64_t       *block_nr,
2342                   e2_blkcnt_t blockcnt,
2343                   blk64_t ref_block EXT2FS_ATTR((unused)),
2344                   int ref_offset EXT2FS_ATTR((unused)),
2345                   void *priv_data)
2346 {
2347         struct process_block_struct *p;
2348         struct problem_context *pctx;
2349         blk64_t blk = *block_nr;
2350         int     ret_code = 0;
2351         problem_t       problem = 0;
2352         e2fsck_t        ctx;
2353
2354         p = (struct process_block_struct *) priv_data;
2355         pctx = p->pctx;
2356         ctx = p->ctx;
2357
2358         if (p->compressed && (blk == EXT2FS_COMPRESSED_BLKADDR)) {
2359                 /* todo: Check that the comprblk_fl is high, that the
2360                    blkaddr pattern looks right (all non-holes up to
2361                    first EXT2FS_COMPRESSED_BLKADDR, then all
2362                    EXT2FS_COMPRESSED_BLKADDR up to end of cluster),
2363                    that the feature_incompat bit is high, and that the
2364                    inode is a regular file.  If we're doing a "full
2365                    check" (a concept introduced to e2fsck by e2compr,
2366                    meaning that we look at data blocks as well as
2367                    metadata) then call some library routine that
2368                    checks the compressed data.  I'll have to think
2369                    about this, because one particularly important
2370                    problem to be able to fix is to recalculate the
2371                    cluster size if necessary.  I think that perhaps
2372                    we'd better do most/all e2compr-specific checks
2373                    separately, after the non-e2compr checks.  If not
2374                    doing a full check, it may be useful to test that
2375                    the personality is linux; e.g. if it isn't then
2376                    perhaps this really is just an illegal block. */
2377                 return 0;
2378         }
2379
2380         if (blk == 0)
2381                 return 0;
2382
2383 #if 0
2384         printf("Process_block, inode %lu, block %u, #%d\n", p->ino, blk,
2385                blockcnt);
2386 #endif
2387
2388         /*
2389          * Simplistic fragmentation check.  We merely require that the
2390          * file be contiguous.  (Which can never be true for really
2391          * big files that are greater than a block group.)
2392          */
2393         if (!HOLE_BLKADDR(p->previous_block) && p->ino != EXT2_RESIZE_INO) {
2394                 if (p->previous_block+1 != blk) {
2395                         if (ctx->options & E2F_OPT_FRAGCHECK) {
2396                                 char type = '?';
2397
2398                                 if (p->is_dir)
2399                                         type = 'd';
2400                                 else if (p->is_reg)
2401                                         type = 'f';
2402
2403                                 printf(_("%6lu(%c): expecting %6lu "
2404                                          "got phys %6lu (blkcnt %lld)\n"),
2405                                        (unsigned long) pctx->ino, type,
2406                                        (unsigned long) p->previous_block+1,
2407                                        (unsigned long) blk,
2408                                        blockcnt);
2409                         }
2410                         p->fragmented = 1;
2411                 }
2412         }
2413
2414         if (p->is_dir && blockcnt > (1 << (21 - fs->super->s_log_block_size)))
2415                 problem = PR_1_TOOBIG_DIR;
2416         if (p->is_reg && p->num_blocks+1 >= p->max_blocks)
2417                 problem = PR_1_TOOBIG_REG;
2418         if (!p->is_dir && !p->is_reg && blockcnt > 0)
2419                 problem = PR_1_TOOBIG_SYMLINK;
2420
2421         if (blk < fs->super->s_first_data_block ||
2422             blk >= ext2fs_blocks_count(fs->super))
2423                 problem = PR_1_ILLEGAL_BLOCK_NUM;
2424
2425         if (problem) {
2426                 p->num_illegal_blocks++;
2427                 if (!p->suppress && (p->num_illegal_blocks % 12) == 0) {
2428                         if (fix_problem(ctx, PR_1_TOO_MANY_BAD_BLOCKS, pctx)) {
2429                                 p->clear = 1;
2430                                 return BLOCK_ABORT;
2431                         }
2432                         if (fix_problem(ctx, PR_1_SUPPRESS_MESSAGES, pctx)) {
2433                                 p->suppress = 1;
2434                                 set_latch_flags(PR_LATCH_BLOCK,
2435                                                 PRL_SUPPRESS, 0);
2436                         }
2437                 }
2438                 pctx->blk = blk;
2439                 pctx->blkcount = blockcnt;
2440                 if (fix_problem(ctx, problem, pctx)) {
2441                         blk = *block_nr = 0;
2442                         ret_code = BLOCK_CHANGED;
2443                         p->inode_modified = 1;
2444                         goto mark_dir;
2445                 } else
2446                         return 0;
2447         }
2448
2449         if (p->ino == EXT2_RESIZE_INO) {
2450                 /*
2451                  * The resize inode has already be sanity checked
2452                  * during pass #0 (the superblock checks).  All we
2453                  * have to do is mark the double indirect block as
2454                  * being in use; all of the other blocks are handled
2455                  * by mark_table_blocks()).
2456                  */
2457                 if (blockcnt == BLOCK_COUNT_DIND)
2458                         mark_block_used(ctx, blk);
2459                 p->num_blocks++;
2460         } else if (!(ctx->fs->cluster_ratio_bits &&
2461                      p->previous_block &&
2462                      (EXT2FS_B2C(ctx->fs, blk) ==
2463                       EXT2FS_B2C(ctx->fs, p->previous_block)) &&
2464                      (blk & EXT2FS_CLUSTER_MASK(ctx->fs)) ==
2465                      ((unsigned) blockcnt & EXT2FS_CLUSTER_MASK(ctx->fs)))) {
2466                 mark_block_used(ctx, blk);
2467                 p->num_blocks++;
2468         }
2469         if (blockcnt >= 0)
2470                 p->last_block = blockcnt;
2471         p->previous_block = blk;
2472 mark_dir:
2473         if (p->is_dir && (blockcnt >= 0)) {
2474                 while (++p->last_db_block < blockcnt) {
2475                         pctx->errcode = ext2fs_add_dir_block2(fs->dblist,
2476                                                               p->ino, 0,
2477                                                               p->last_db_block);
2478                         if (pctx->errcode) {
2479                                 pctx->blk = 0;
2480                                 pctx->num = p->last_db_block;
2481                                 goto failed_add_dir_block;
2482                         }
2483                 }
2484                 pctx->errcode = ext2fs_add_dir_block2(fs->dblist, p->ino,
2485                                                       blk, blockcnt);
2486                 if (pctx->errcode) {
2487                         pctx->blk = blk;
2488                         pctx->num = blockcnt;
2489                 failed_add_dir_block:
2490                         fix_problem(ctx, PR_1_ADD_DBLOCK, pctx);
2491                         /* Should never get here */
2492                         ctx->flags |= E2F_FLAG_ABORT;
2493                         return BLOCK_ABORT;
2494                 }
2495         }
2496         return ret_code;
2497 }
2498
2499 static int process_bad_block(ext2_filsys fs,
2500                       blk64_t *block_nr,
2501                       e2_blkcnt_t blockcnt,
2502                       blk64_t ref_block EXT2FS_ATTR((unused)),
2503                       int ref_offset EXT2FS_ATTR((unused)),
2504                       void *priv_data)
2505 {
2506         struct process_block_struct *p;
2507         blk64_t         blk = *block_nr;
2508         blk64_t         first_block;
2509         dgrp_t          i;
2510         struct problem_context *pctx;
2511         e2fsck_t        ctx;
2512
2513         /*
2514          * Note: This function processes blocks for the bad blocks
2515          * inode, which is never compressed.  So we don't use HOLE_BLKADDR().
2516          */
2517
2518         if (!blk)
2519                 return 0;
2520
2521         p = (struct process_block_struct *) priv_data;
2522         ctx = p->ctx;
2523         pctx = p->pctx;
2524
2525         pctx->ino = EXT2_BAD_INO;
2526         pctx->blk = blk;
2527         pctx->blkcount = blockcnt;
2528
2529         if ((blk < fs->super->s_first_data_block) ||
2530             (blk >= ext2fs_blocks_count(fs->super))) {
2531                 if (fix_problem(ctx, PR_1_BB_ILLEGAL_BLOCK_NUM, pctx)) {
2532                         *block_nr = 0;
2533                         return BLOCK_CHANGED;
2534                 } else
2535                         return 0;
2536         }
2537
2538         if (blockcnt < 0) {
2539                 if (ext2fs_test_block_bitmap2(p->fs_meta_blocks, blk)) {
2540                         p->bbcheck = 1;
2541                         if (fix_problem(ctx, PR_1_BB_FS_BLOCK, pctx)) {
2542                                 *block_nr = 0;
2543                                 return BLOCK_CHANGED;
2544                         }
2545                 } else if (ext2fs_test_block_bitmap2(ctx->block_found_map,
2546                                                     blk)) {
2547                         p->bbcheck = 1;
2548                         if (fix_problem(ctx, PR_1_BBINODE_BAD_METABLOCK,
2549                                         pctx)) {
2550                                 *block_nr = 0;
2551                                 return BLOCK_CHANGED;
2552                         }
2553                         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
2554                                 return BLOCK_ABORT;
2555                 } else
2556                         mark_block_used(ctx, blk);
2557                 return 0;
2558         }
2559 #if 0
2560         printf ("DEBUG: Marking %u as bad.\n", blk);
2561 #endif
2562         ctx->fs_badblocks_count++;
2563         /*
2564          * If the block is not used, then mark it as used and return.
2565          * If it is already marked as found, this must mean that
2566          * there's an overlap between the filesystem table blocks
2567          * (bitmaps and inode table) and the bad block list.
2568          */
2569         if (!ext2fs_test_block_bitmap2(ctx->block_found_map, blk)) {
2570                 ext2fs_mark_block_bitmap2(ctx->block_found_map, blk);
2571                 return 0;
2572         }
2573         /*
2574          * Try to find the where the filesystem block was used...
2575          */
2576         first_block = fs->super->s_first_data_block;
2577
2578         for (i = 0; i < fs->group_desc_count; i++ ) {
2579                 pctx->group = i;
2580                 pctx->blk = blk;
2581                 if (!ext2fs_bg_has_super(fs, i))
2582                         goto skip_super;
2583                 if (blk == first_block) {
2584                         if (i == 0) {
2585                                 if (fix_problem(ctx,
2586                                                 PR_1_BAD_PRIMARY_SUPERBLOCK,
2587                                                 pctx)) {
2588                                         *block_nr = 0;
2589                                         return BLOCK_CHANGED;
2590                                 }
2591                                 return 0;
2592                         }
2593                         fix_problem(ctx, PR_1_BAD_SUPERBLOCK, pctx);
2594                         return 0;
2595                 }
2596                 if ((blk > first_block) &&
2597                     (blk <= first_block + fs->desc_blocks)) {
2598                         if (i == 0) {
2599                                 pctx->blk = *block_nr;
2600                                 if (fix_problem(ctx,
2601                         PR_1_BAD_PRIMARY_GROUP_DESCRIPTOR, pctx)) {
2602                                         *block_nr = 0;
2603                                         return BLOCK_CHANGED;
2604                                 }
2605                                 return 0;
2606                         }
2607                         fix_problem(ctx, PR_1_BAD_GROUP_DESCRIPTORS, pctx);
2608                         return 0;
2609                 }
2610         skip_super:
2611                 if (blk == ext2fs_block_bitmap_loc(fs, i)) {
2612                         if (fix_problem(ctx, PR_1_BB_BAD_BLOCK, pctx)) {
2613                                 ctx->invalid_block_bitmap_flag[i]++;
2614                                 ctx->invalid_bitmaps++;
2615                         }
2616                         return 0;
2617                 }
2618                 if (blk == ext2fs_inode_bitmap_loc(fs, i)) {
2619                         if (fix_problem(ctx, PR_1_IB_BAD_BLOCK, pctx)) {
2620                                 ctx->invalid_inode_bitmap_flag[i]++;
2621                                 ctx->invalid_bitmaps++;
2622                         }
2623                         return 0;
2624                 }
2625                 if ((blk >= ext2fs_inode_table_loc(fs, i)) &&
2626                     (blk < (ext2fs_inode_table_loc(fs, i) +
2627                             fs->inode_blocks_per_group))) {
2628                         /*
2629                          * If there are bad blocks in the inode table,
2630                          * the inode scan code will try to do
2631                          * something reasonable automatically.
2632                          */
2633                         return 0;
2634                 }
2635                 first_block += fs->super->s_blocks_per_group;
2636         }
2637         /*
2638          * If we've gotten to this point, then the only
2639          * possibility is that the bad block inode meta data
2640          * is using a bad block.
2641          */
2642         if ((blk == p->inode->i_block[EXT2_IND_BLOCK]) ||
2643             (blk == p->inode->i_block[EXT2_DIND_BLOCK]) ||
2644             (blk == p->inode->i_block[EXT2_TIND_BLOCK])) {
2645                 p->bbcheck = 1;
2646                 if (fix_problem(ctx, PR_1_BBINODE_BAD_METABLOCK, pctx)) {
2647                         *block_nr = 0;
2648                         return BLOCK_CHANGED;
2649                 }
2650                 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
2651                         return BLOCK_ABORT;
2652                 return 0;
2653         }
2654
2655         pctx->group = -1;
2656
2657         /* Warn user that the block wasn't claimed */
2658         fix_problem(ctx, PR_1_PROGERR_CLAIMED_BLOCK, pctx);
2659
2660         return 0;
2661 }
2662
2663 static void new_table_block(e2fsck_t ctx, blk64_t first_block, dgrp_t group,
2664                             const char *name, int num, blk64_t *new_block)
2665 {
2666         ext2_filsys fs = ctx->fs;
2667         dgrp_t          last_grp;
2668         blk64_t         old_block = *new_block;
2669         blk64_t         last_block;
2670         dgrp_t          flexbg;
2671         unsigned        flexbg_size;
2672         int             i, is_flexbg;
2673         char            *buf;
2674         struct problem_context  pctx;
2675
2676         clear_problem_context(&pctx);
2677
2678         pctx.group = group;
2679         pctx.blk = old_block;
2680         pctx.str = name;
2681
2682         /*
2683          * For flex_bg filesystems, first try to allocate the metadata
2684          * within the flex_bg, and if that fails then try finding the
2685          * space anywhere in the filesystem.
2686          */
2687         is_flexbg = EXT2_HAS_INCOMPAT_FEATURE(fs->super,
2688                                               EXT4_FEATURE_INCOMPAT_FLEX_BG);
2689         if (is_flexbg) {
2690                 flexbg_size = 1 << fs->super->s_log_groups_per_flex;
2691                 flexbg = group / flexbg_size;
2692                 first_block = ext2fs_group_first_block2(fs,
2693                                                         flexbg_size * flexbg);
2694                 last_grp = group | (flexbg_size - 1);
2695                 if (last_grp >= fs->group_desc_count)
2696                         last_grp = fs->group_desc_count - 1;
2697                 last_block = ext2fs_group_last_block2(fs, last_grp);
2698         } else
2699                 last_block = ext2fs_group_last_block2(fs, group);
2700         pctx.errcode = ext2fs_get_free_blocks2(fs, first_block, last_block,
2701                                                num, ctx->block_found_map,
2702                                                new_block);
2703         if (is_flexbg && (pctx.errcode == EXT2_ET_BLOCK_ALLOC_FAIL))
2704                 pctx.errcode = ext2fs_get_free_blocks2(fs,
2705                                 fs->super->s_first_data_block,
2706                                 ext2fs_blocks_count(fs->super),
2707                                 num, ctx->block_found_map, new_block);
2708         if (pctx.errcode) {
2709                 pctx.num = num;
2710                 fix_problem(ctx, PR_1_RELOC_BLOCK_ALLOCATE, &pctx);
2711                 ext2fs_unmark_valid(fs);
2712                 ctx->flags |= E2F_FLAG_ABORT;
2713                 return;
2714         }
2715         pctx.errcode = ext2fs_get_mem(fs->blocksize, &buf);
2716         if (pctx.errcode) {
2717                 fix_problem(ctx, PR_1_RELOC_MEMORY_ALLOCATE, &pctx);
2718                 ext2fs_unmark_valid(fs);
2719                 ctx->flags |= E2F_FLAG_ABORT;
2720                 return;
2721         }
2722         ext2fs_mark_super_dirty(fs);
2723         fs->flags &= ~EXT2_FLAG_MASTER_SB_ONLY;
2724         pctx.blk2 = *new_block;
2725         fix_problem(ctx, (old_block ? PR_1_RELOC_FROM_TO :
2726                           PR_1_RELOC_TO), &pctx);
2727         pctx.blk2 = 0;
2728         for (i = 0; i < num; i++) {
2729                 pctx.blk = i;
2730                 ext2fs_mark_block_bitmap2(ctx->block_found_map, (*new_block)+i);
2731                 if (old_block) {
2732                         pctx.errcode = io_channel_read_blk64(fs->io,
2733                                    old_block + i, 1, buf);
2734                         if (pctx.errcode)
2735                                 fix_problem(ctx, PR_1_RELOC_READ_ERR, &pctx);
2736                 } else
2737                         memset(buf, 0, fs->blocksize);
2738
2739                 pctx.blk = (*new_block) + i;
2740                 pctx.errcode = io_channel_write_blk64(fs->io, pctx.blk,
2741                                               1, buf);
2742                 if (pctx.errcode)
2743                         fix_problem(ctx, PR_1_RELOC_WRITE_ERR, &pctx);
2744         }
2745         ext2fs_free_mem(&buf);
2746 }
2747
2748 /*
2749  * This routine gets called at the end of pass 1 if bad blocks are
2750  * detected in the superblock, group descriptors, inode_bitmaps, or
2751  * block bitmaps.  At this point, all of the blocks have been mapped
2752  * out, so we can try to allocate new block(s) to replace the bad
2753  * blocks.
2754  */
2755 static void handle_fs_bad_blocks(e2fsck_t ctx)
2756 {
2757         ext2_filsys fs = ctx->fs;
2758         dgrp_t          i;
2759         blk64_t         first_block;
2760         blk64_t         new_blk;
2761
2762         for (i = 0; i < fs->group_desc_count; i++) {
2763                 first_block = ext2fs_group_first_block2(fs, i);
2764
2765                 if (ctx->invalid_block_bitmap_flag[i]) {
2766                         new_blk = ext2fs_block_bitmap_loc(fs, i);
2767                         new_table_block(ctx, first_block, i, _("block bitmap"),
2768                                         1, &new_blk);
2769                         ext2fs_block_bitmap_loc_set(fs, i, new_blk);
2770                 }
2771                 if (ctx->invalid_inode_bitmap_flag[i]) {
2772                         new_blk = ext2fs_inode_bitmap_loc(fs, i);
2773                         new_table_block(ctx, first_block, i, _("inode bitmap"),
2774                                         1, &new_blk);
2775                         ext2fs_inode_bitmap_loc_set(fs, i, new_blk);
2776                 }
2777                 if (ctx->invalid_inode_table_flag[i]) {
2778                         new_blk = ext2fs_inode_table_loc(fs, i);
2779                         new_table_block(ctx, first_block, i, _("inode table"),
2780                                         fs->inode_blocks_per_group,
2781                                         &new_blk);
2782                         ext2fs_inode_table_loc_set(fs, i, new_blk);
2783                         ctx->flags |= E2F_FLAG_RESTART;
2784                 }
2785         }
2786         ctx->invalid_bitmaps = 0;
2787 }
2788
2789 /*
2790  * This routine marks all blocks which are used by the superblock,
2791  * group descriptors, inode bitmaps, and block bitmaps.
2792  */
2793 static void mark_table_blocks(e2fsck_t ctx)
2794 {
2795         ext2_filsys fs = ctx->fs;
2796         blk64_t b;
2797         dgrp_t  i;
2798         unsigned int    j;
2799         struct problem_context pctx;
2800
2801         clear_problem_context(&pctx);
2802
2803         for (i = 0; i < fs->group_desc_count; i++) {
2804                 pctx.group = i;
2805
2806                 ext2fs_reserve_super_and_bgd(fs, i, ctx->block_found_map);
2807
2808                 /*
2809                  * Mark the blocks used for the inode table
2810                  */
2811                 if (ext2fs_inode_table_loc(fs, i)) {
2812                         for (j = 0, b = ext2fs_inode_table_loc(fs, i);
2813                              j < fs->inode_blocks_per_group;
2814                              j++, b++) {
2815                                 if (ext2fs_test_block_bitmap2(ctx->block_found_map,
2816                                                              b)) {
2817                                         pctx.blk = b;
2818                                         if (!ctx->invalid_inode_table_flag[i] &&
2819                                             fix_problem(ctx,
2820                                                 PR_1_ITABLE_CONFLICT, &pctx)) {
2821                                                 ctx->invalid_inode_table_flag[i]++;
2822                                                 ctx->invalid_bitmaps++;
2823                                         }
2824                                 } else {
2825                                     ext2fs_mark_block_bitmap2(ctx->block_found_map,
2826                                                              b);
2827                                 }
2828                         }
2829                 }
2830
2831                 /*
2832                  * Mark block used for the block bitmap
2833                  */
2834                 if (ext2fs_block_bitmap_loc(fs, i)) {
2835                         if (ext2fs_test_block_bitmap2(ctx->block_found_map,
2836                                      ext2fs_block_bitmap_loc(fs, i))) {
2837                                 pctx.blk = ext2fs_block_bitmap_loc(fs, i);
2838                                 if (fix_problem(ctx, PR_1_BB_CONFLICT, &pctx)) {
2839                                         ctx->invalid_block_bitmap_flag[i]++;
2840                                         ctx->invalid_bitmaps++;
2841                                 }
2842                         } else {
2843                             ext2fs_mark_block_bitmap2(ctx->block_found_map,
2844                                      ext2fs_block_bitmap_loc(fs, i));
2845                     }
2846
2847                 }
2848                 /*
2849                  * Mark block used for the inode bitmap
2850                  */
2851                 if (ext2fs_inode_bitmap_loc(fs, i)) {
2852                         if (ext2fs_test_block_bitmap2(ctx->block_found_map,
2853                                      ext2fs_inode_bitmap_loc(fs, i))) {
2854                                 pctx.blk = ext2fs_inode_bitmap_loc(fs, i);
2855                                 if (fix_problem(ctx, PR_1_IB_CONFLICT, &pctx)) {
2856                                         ctx->invalid_inode_bitmap_flag[i]++;
2857                                         ctx->invalid_bitmaps++;
2858                                 }
2859                         } else {
2860                             ext2fs_mark_block_bitmap2(ctx->block_found_map,
2861                                      ext2fs_inode_bitmap_loc(fs, i));
2862                         }
2863                 }
2864         }
2865 }
2866
2867 /*
2868  * Thes subroutines short circuits ext2fs_get_blocks and
2869  * ext2fs_check_directory; we use them since we already have the inode
2870  * structure, so there's no point in letting the ext2fs library read
2871  * the inode again.
2872  */
2873 static errcode_t pass1_get_blocks(ext2_filsys fs, ext2_ino_t ino,
2874                                   blk_t *blocks)
2875 {
2876         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2877         int     i;
2878
2879         if ((ino != ctx->stashed_ino) || !ctx->stashed_inode)
2880                 return EXT2_ET_CALLBACK_NOTHANDLED;
2881
2882         for (i=0; i < EXT2_N_BLOCKS; i++)
2883                 blocks[i] = ctx->stashed_inode->i_block[i];
2884         return 0;
2885 }
2886
2887 static errcode_t pass1_read_inode(ext2_filsys fs, ext2_ino_t ino,
2888                                   struct ext2_inode *inode)
2889 {
2890         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2891
2892         if ((ino != ctx->stashed_ino) || !ctx->stashed_inode)
2893                 return EXT2_ET_CALLBACK_NOTHANDLED;
2894         *inode = *ctx->stashed_inode;
2895         return 0;
2896 }
2897
2898 static errcode_t pass1_write_inode(ext2_filsys fs, ext2_ino_t ino,
2899                             struct ext2_inode *inode)
2900 {
2901         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2902
2903         if ((ino == ctx->stashed_ino) && ctx->stashed_inode &&
2904                 (inode != ctx->stashed_inode))
2905                 *ctx->stashed_inode = *inode;
2906         return EXT2_ET_CALLBACK_NOTHANDLED;
2907 }
2908
2909 static errcode_t pass1_check_directory(ext2_filsys fs, ext2_ino_t ino)
2910 {
2911         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2912
2913         if ((ino != ctx->stashed_ino) || !ctx->stashed_inode)
2914                 return EXT2_ET_CALLBACK_NOTHANDLED;
2915
2916         if (!LINUX_S_ISDIR(ctx->stashed_inode->i_mode))
2917                 return EXT2_ET_NO_DIRECTORY;
2918         return 0;
2919 }
2920
2921 static errcode_t e2fsck_get_alloc_block(ext2_filsys fs, blk64_t goal,
2922                                         blk64_t *ret)
2923 {
2924         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2925         errcode_t       retval;
2926         blk64_t         new_block;
2927
2928         if (ctx->block_found_map) {
2929                 retval = ext2fs_new_block2(fs, goal, ctx->block_found_map,
2930                                            &new_block);
2931                 if (retval)
2932                         return retval;
2933                 if (fs->block_map) {
2934                         ext2fs_mark_block_bitmap2(fs->block_map, new_block);
2935                         ext2fs_mark_bb_dirty(fs);
2936                 }
2937         } else {
2938                 if (!fs->block_map) {
2939                         retval = ext2fs_read_block_bitmap(fs);
2940                         if (retval)
2941                                 return retval;
2942                 }
2943
2944                 retval = ext2fs_new_block2(fs, goal, 0, &new_block);
2945                 if (retval)
2946                         return retval;
2947         }
2948
2949         *ret = new_block;
2950         return (0);
2951 }
2952
2953 static void e2fsck_block_alloc_stats(ext2_filsys fs, blk64_t blk, int inuse)
2954 {
2955         e2fsck_t ctx = (e2fsck_t) fs->priv_data;
2956
2957         if (ctx->block_found_map) {
2958                 if (inuse > 0)
2959                         ext2fs_mark_block_bitmap2(ctx->block_found_map, blk);
2960                 else
2961                         ext2fs_unmark_block_bitmap2(ctx->block_found_map, blk);
2962         }
2963 }
2964
2965 void e2fsck_use_inode_shortcuts(e2fsck_t ctx, int use_shortcuts)
2966 {
2967         ext2_filsys fs = ctx->fs;
2968
2969         if (use_shortcuts) {
2970                 fs->get_blocks = pass1_get_blocks;
2971                 fs->check_directory = pass1_check_directory;
2972                 fs->read_inode = pass1_read_inode;
2973                 fs->write_inode = pass1_write_inode;
2974                 ctx->stashed_ino = 0;
2975         } else {
2976                 fs->get_blocks = 0;
2977                 fs->check_directory = 0;
2978                 fs->read_inode = 0;
2979                 fs->write_inode = 0;
2980         }
2981 }
2982
2983 void e2fsck_intercept_block_allocations(e2fsck_t ctx)
2984 {
2985         ext2fs_set_alloc_block_callback(ctx->fs, e2fsck_get_alloc_block, 0);
2986         ext2fs_set_block_alloc_stats_callback(ctx->fs,
2987                                                 e2fsck_block_alloc_stats, 0);
2988 }