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