e2fsck/pass1b.c

   1 /*
   2  * pass1b.c --- Pass #1b of e2fsck
   3  *
   4  * This file contains pass1B, pass1C, and pass1D of e2fsck.  They are
   5  * only invoked if pass 1 discovered blocks which are in use by more
   6  * than one inode.
   7  *
   8  * Pass1B scans the data blocks of all the inodes again, generating a
   9  * complete list of duplicate blocks and which inodes have claimed
  10  * them.
  11  *
  12  * Pass1C does a tree-traversal of the filesystem, to determine the
  13  * parent directories of these inodes.  This step is necessary so that
  14  * e2fsck can print out the pathnames of affected inodes.
  15  *
  16  * Pass1D is a reconciliation pass.  For each inode with duplicate
  17  * blocks, the user is prompted if s/he would like to clone the file
  18  * (so that the file gets a fresh copy of the duplicated blocks) or
  19  * simply to delete the file.
  20  *
  21  * Copyright (C) 1993, 1994, 1995, 1996, 1997 Theodore Ts'o.
  22  *
  23  * %Begin-Header%
  24  * This file may be redistributed under the terms of the GNU Public
  25  * License.
  26  * %End-Header%
  27  *
  28  */
  29
  30 #include "config.h"
  31 #include <time.h>
  32 #ifdef HAVE_ERRNO_H
  33 #include <errno.h>
  34 #endif
  35
  36 #ifdef HAVE_INTTYPES_H
  37 #include <inttypes.h>
  38 #endif
  39
  40 #ifndef HAVE_INTPTR_T
  41 typedef long intptr_t;
  42 #endif
  43
  44 /* Needed for architectures where sizeof(int) != sizeof(void *) */
  45 #define INT_TO_VOIDPTR(val)  ((void *)(intptr_t)(val))
  46 #define VOIDPTR_TO_INT(ptr)  ((int)(intptr_t)(ptr))
  47
  48 #include <et/com_err.h>
  49 #include "e2fsck.h"
  50
  51 #include "problem.h"
  52 #include "support/dict.h"
  53
  54 /* Define an extension to the ext2 library's block count information */
  55 #define BLOCK_COUNT_EXTATTR     (-5)
  56
  57 struct cluster_el {
  58         blk64_t cluster;
  59         struct cluster_el *next;
  60 };
  61
  62 struct inode_el {
  63         ext2_ino_t      inode;
  64         struct inode_el *next;
  65 };
  66
  67 struct dup_cluster {
  68         int             num_bad;
  69         struct inode_el *inode_list;
  70 };
  71
  72 /*
  73  * This structure stores information about a particular inode which
  74  * is sharing blocks with other inodes.  This information is collected
  75  * to display to the user, so that the user knows what files he or she
  76  * is dealing with, when trying to decide how to resolve the conflict
  77  * of multiply-claimed blocks.
  78  */
  79 struct dup_inode {
  80         ext2_ino_t              dir;
  81         int                     num_dupblocks;
  82         struct ext2_inode_large inode;
  83         struct cluster_el       *cluster_list;
  84 };
  85
  86 static int process_pass1b_block(ext2_filsys fs, blk64_t *blocknr,
  87                                 e2_blkcnt_t blockcnt, blk64_t ref_blk,
  88                                 int ref_offset, void *priv_data);
  89 static void delete_file(e2fsck_t ctx, ext2_ino_t ino,
  90                         struct dup_inode *dp, char *block_buf);
  91 static errcode_t clone_file(e2fsck_t ctx, ext2_ino_t ino,
  92                             struct dup_inode *dp, char* block_buf);
  93 static int check_if_fs_block(e2fsck_t ctx, blk64_t test_block);
  94 static int check_if_fs_cluster(e2fsck_t ctx, blk64_t cluster);
  95
  96 static void pass1b(e2fsck_t ctx, char *block_buf);
  97 static void pass1c(e2fsck_t ctx, char *block_buf);
  98 static void pass1d(e2fsck_t ctx, char *block_buf);
  99
 100 static int dup_inode_count = 0;
 101 static int dup_inode_founddir = 0;
 102
 103 static dict_t clstr_dict, ino_dict;
 104
 105 static ext2fs_inode_bitmap inode_dup_map;
 106
 107 static int dict_int_cmp(const void *cmp_ctx EXT2FS_ATTR((unused)),
 108                         const void *a, const void *b)
 109 {
 110         intptr_t        ia, ib;
 111
 112         ia = (intptr_t)a;
 113         ib = (intptr_t)b;
 114
 115         return (ia-ib);
 116 }
 117
 118 /*
 119  * Add a duplicate block record
 120  */
 121 static void add_dupe(e2fsck_t ctx, ext2_ino_t ino, blk64_t cluster,
 122                      struct ext2_inode_large *inode)
 123 {
 124         dnode_t *n;
 125         struct dup_cluster      *db;
 126         struct dup_inode        *di;
 127         struct cluster_el       *cluster_el;
 128         struct inode_el         *ino_el;
 129
 130         n = dict_lookup(&clstr_dict, INT_TO_VOIDPTR(cluster));
 131         if (n)
 132                 db = (struct dup_cluster *) dnode_get(n);
 133         else {
 134                 db = (struct dup_cluster *) e2fsck_allocate_memory(ctx,
 135                         sizeof(struct dup_cluster), "duplicate cluster header");
 136                 db->num_bad = 0;
 137                 db->inode_list = 0;
 138                 dict_alloc_insert(&clstr_dict, INT_TO_VOIDPTR(cluster), db);
 139         }
 140         ino_el = (struct inode_el *) e2fsck_allocate_memory(ctx,
 141                          sizeof(struct inode_el), "inode element");
 142         ino_el->inode = ino;
 143         ino_el->next = db->inode_list;
 144         db->inode_list = ino_el;
 145         db->num_bad++;
 146
 147         n = dict_lookup(&ino_dict, INT_TO_VOIDPTR(ino));
 148         if (n)
 149                 di = (struct dup_inode *) dnode_get(n);
 150         else {
 151                 di = (struct dup_inode *) e2fsck_allocate_memory(ctx,
 152                          sizeof(struct dup_inode), "duplicate inode header");
 153                 if (ino == EXT2_ROOT_INO) {
 154                         di->dir = EXT2_ROOT_INO;
 155                         dup_inode_founddir++;
 156                 } else
 157                         di->dir = 0;
 158
 159                 di->num_dupblocks = 0;
 160                 di->cluster_list = 0;
 161                 di->inode = *inode;
 162                 dict_alloc_insert(&ino_dict, INT_TO_VOIDPTR(ino), di);
 163         }
 164         cluster_el = (struct cluster_el *) e2fsck_allocate_memory(ctx,
 165                          sizeof(struct cluster_el), "cluster element");
 166         cluster_el->cluster = cluster;
 167         cluster_el->next = di->cluster_list;
 168         di->cluster_list = cluster_el;
 169         di->num_dupblocks++;
 170 }
 171
 172 /*
 173  * Free a duplicate inode record
 174  */
 175 static void inode_dnode_free(dnode_t *node,
 176                              void *context EXT2FS_ATTR((unused)))
 177 {
 178         struct dup_inode        *di;
 179         struct cluster_el               *p, *next;
 180
 181         di = (struct dup_inode *) dnode_get(node);
 182         for (p = di->cluster_list; p; p = next) {
 183                 next = p->next;
 184                 ext2fs_free_mem(&p);
 185         }
 186         ext2fs_free_mem(&di);
 187         ext2fs_free_mem(&node);
 188 }
 189
 190 /*
 191  * Free a duplicate cluster record
 192  */
 193 static void cluster_dnode_free(dnode_t *node,
 194                                void *context EXT2FS_ATTR((unused)))
 195 {
 196         struct dup_cluster      *dc;
 197         struct inode_el         *p, *next;
 198
 199         dc = (struct dup_cluster *) dnode_get(node);
 200         for (p = dc->inode_list; p; p = next) {
 201                 next = p->next;
 202                 ext2fs_free_mem(&p);
 203         }
 204         ext2fs_free_mem(&dc);
 205         ext2fs_free_mem(&node);
 206 }
 207
 208
 209 /*
 210  * Main procedure for handling duplicate blocks
 211  */
 212 void e2fsck_pass1_dupblocks(e2fsck_t ctx, char *block_buf)
 213 {
 214         ext2_filsys             fs = ctx->fs;
 215         struct problem_context  pctx;
 216 #ifdef RESOURCE_TRACK
 217         struct resource_track   rtrack;
 218 #endif
 219
 220         clear_problem_context(&pctx);
 221
 222         pctx.errcode = e2fsck_allocate_inode_bitmap(fs,
 223                         _("multiply claimed inode map"),
 224                         EXT2FS_BMAP64_RBTREE, "inode_dup_map",
 225                         &inode_dup_map);
 226         if (pctx.errcode) {
 227                 fix_problem(ctx, PR_1B_ALLOCATE_IBITMAP_ERROR, &pctx);
 228                 ctx->flags |= E2F_FLAG_ABORT;
 229                 return;
 230         }
 231
 232         dict_init(&ino_dict, DICTCOUNT_T_MAX, dict_int_cmp);
 233         dict_init(&clstr_dict, DICTCOUNT_T_MAX, dict_int_cmp);
 234         dict_set_allocator(&ino_dict, NULL, inode_dnode_free, NULL);
 235         dict_set_allocator(&clstr_dict, NULL, cluster_dnode_free, NULL);
 236
 237         init_resource_track(&rtrack, ctx->fs->io);
 238         pass1b(ctx, block_buf);
 239         print_resource_track(ctx, "Pass 1b", &rtrack, ctx->fs->io);
 240
 241         init_resource_track(&rtrack, ctx->fs->io);
 242         pass1c(ctx, block_buf);
 243         print_resource_track(ctx, "Pass 1c", &rtrack, ctx->fs->io);
 244
 245         init_resource_track(&rtrack, ctx->fs->io);
 246         pass1d(ctx, block_buf);
 247         print_resource_track(ctx, "Pass 1d", &rtrack, ctx->fs->io);
 248
 249         if (ext2fs_has_feature_shared_blocks(ctx->fs->super) &&
 250             (ctx->options & E2F_OPT_UNSHARE_BLOCKS)) {
 251                 /*
 252                  * If we successfully managed to unshare all blocks, unset the
 253                  * shared block feature.
 254                  */
 255                 blk64_t next;
 256                 int result = ext2fs_find_first_set_block_bitmap2(
 257                         ctx->block_dup_map,
 258                         ctx->fs->super->s_first_data_block,
 259                         ext2fs_blocks_count(ctx->fs->super) - 1,
 260                         &next);
 261                 if (result == ENOENT && !(ctx->options & E2F_OPT_NO)) {
 262                         ext2fs_clear_feature_shared_blocks(ctx->fs->super);
 263                         ext2fs_mark_super_dirty(ctx->fs);
 264                 }
 265         }
 266
 267         /*
 268          * Time to free all of the accumulated data structures that we
 269          * don't need anymore.
 270          */
 271         dict_free_nodes(&ino_dict);
 272         dict_free_nodes(&clstr_dict);
 273         ext2fs_free_inode_bitmap(inode_dup_map);
 274 }
 275
 276 /*
 277  * Scan the inodes looking for inodes that contain duplicate blocks.
 278  */
 279 struct process_block_struct {
 280         e2fsck_t        ctx;
 281         ext2_ino_t      ino;
 282         int             dup_blocks;
 283         blk64_t         cur_cluster, phys_cluster;
 284         blk64_t         last_blk;
 285         struct ext2_inode_large *inode;
 286         struct problem_context *pctx;
 287 };
 288
 289 static void pass1b(e2fsck_t ctx, char *block_buf)
 290 {
 291         ext2_filsys fs = ctx->fs;
 292         ext2_ino_t ino = 0;
 293         struct ext2_inode_large inode;
 294         ext2_inode_scan scan;
 295         struct process_block_struct pb;
 296         struct problem_context pctx;
 297         problem_t op;
 298
 299         clear_problem_context(&pctx);
 300
 301         if (!(ctx->options & E2F_OPT_PREEN))
 302                 fix_problem(ctx, PR_1B_PASS_HEADER, &pctx);
 303         pctx.errcode = ext2fs_open_inode_scan(fs, ctx->inode_buffer_blocks,
 304                                               &scan);
 305         if (pctx.errcode) {
 306                 fix_problem(ctx, PR_1B_ISCAN_ERROR, &pctx);
 307                 ctx->flags |= E2F_FLAG_ABORT;
 308                 return;
 309         }
 310         ctx->stashed_inode = EXT2_INODE(&inode);
 311         pb.ctx = ctx;
 312         pb.pctx = &pctx;
 313         pctx.str = "pass1b";
 314         while (1) {
 315                 if (ino % (fs->super->s_inodes_per_group * 4) == 1) {
 316                         if (e2fsck_mmp_update(fs))
 317                                 fatal_error(ctx, 0);
 318                 }
 319                 pctx.errcode = ext2fs_get_next_inode_full(scan, &ino,
 320                                 EXT2_INODE(&inode), sizeof(inode));
 321                 if (pctx.errcode == EXT2_ET_BAD_BLOCK_IN_INODE_TABLE)
 322                         continue;
 323                 if (pctx.errcode) {
 324                         pctx.ino = ino;
 325                         fix_problem(ctx, PR_1B_ISCAN_ERROR, &pctx);
 326                         ctx->flags |= E2F_FLAG_ABORT;
 327                         return;
 328                 }
 329                 if (!ino)
 330                         break;
 331                 pctx.ino = ctx->stashed_ino = ino;
 332                 if ((ino != EXT2_BAD_INO) &&
 333                     !ext2fs_test_inode_bitmap2(ctx->inode_used_map, ino))
 334                         continue;
 335
 336                 pb.ino = ino;
 337                 pb.dup_blocks = 0;
 338                 pb.inode = &inode;
 339                 pb.cur_cluster = ~0;
 340                 pb.phys_cluster = ~0;
 341                 pb.last_blk = 0;
 342                 pb.pctx->blk = pb.pctx->blk2 = 0;
 343
 344                 if (ext2fs_inode_has_valid_blocks2(fs, EXT2_INODE(&inode)) ||
 345                     (ino == EXT2_BAD_INO))
 346                         pctx.errcode = ext2fs_block_iterate3(fs, ino,
 347                                              BLOCK_FLAG_READ_ONLY, block_buf,
 348                                              process_pass1b_block, &pb);
 349                 /* If the feature is not set, attrs will be cleared later anyway */
 350                 if (ext2fs_has_feature_xattr(fs->super) &&
 351                     ext2fs_file_acl_block(fs, EXT2_INODE(&inode))) {
 352                         blk64_t blk = ext2fs_file_acl_block(fs, EXT2_INODE(&inode));
 353                         process_pass1b_block(fs, &blk,
 354                                              BLOCK_COUNT_EXTATTR, 0, 0, &pb);
 355                         ext2fs_file_acl_block_set(fs, EXT2_INODE(&inode), blk);
 356                 }
 357                 if (pb.dup_blocks) {
 358                         if (ino != EXT2_BAD_INO) {
 359                                 op = pctx.blk == pctx.blk2 ?
 360                                         PR_1B_DUP_BLOCK : PR_1B_DUP_RANGE;
 361                                 fix_problem(ctx, op, pb.pctx);
 362                         }
 363                         end_problem_latch(ctx, PR_LATCH_DBLOCK);
 364                         if (ino >= EXT2_FIRST_INODE(fs->super) ||
 365                             ino == EXT2_ROOT_INO)
 366                                 dup_inode_count++;
 367                 }
 368                 if (pctx.errcode)
 369                         fix_problem(ctx, PR_1B_BLOCK_ITERATE, &pctx);
 370         }
 371         ext2fs_close_inode_scan(scan);
 372         e2fsck_use_inode_shortcuts(ctx, 0);
 373 }
 374
 375 static int process_pass1b_block(ext2_filsys fs EXT2FS_ATTR((unused)),
 376                                 blk64_t *block_nr,
 377                                 e2_blkcnt_t blockcnt,
 378                                 blk64_t ref_blk EXT2FS_ATTR((unused)),
 379                                 int ref_offset EXT2FS_ATTR((unused)),
 380                                 void *priv_data)
 381 {
 382         struct process_block_struct *p;
 383         e2fsck_t ctx;
 384         blk64_t lc, pc;
 385         problem_t op;
 386
 387         if (*block_nr == 0)
 388                 return 0;
 389         p = (struct process_block_struct *) priv_data;
 390         ctx = p->ctx;
 391         lc = EXT2FS_B2C(fs, blockcnt);
 392         pc = EXT2FS_B2C(fs, *block_nr);
 393
 394         if (!ext2fs_test_block_bitmap2(ctx->block_dup_map, *block_nr))
 395                 goto finish;
 396
 397         /* OK, this is a duplicate block */
 398         if (p->ino != EXT2_BAD_INO) {
 399                 if (p->last_blk + 1 != *block_nr) {
 400                         if (p->last_blk) {
 401                                 op = p->pctx->blk == p->pctx->blk2 ?
 402                                                 PR_1B_DUP_BLOCK :
 403                                                 PR_1B_DUP_RANGE;
 404                                 fix_problem(ctx, op, p->pctx);
 405                         }
 406                         p->pctx->blk = *block_nr;
 407                 }
 408                 p->pctx->blk2 = *block_nr;
 409                 p->last_blk = *block_nr;
 410         }
 411         p->dup_blocks++;
 412         ext2fs_mark_inode_bitmap2(inode_dup_map, p->ino);
 413
 414         /*
 415          * Qualifications for submitting a block for duplicate processing:
 416          * It's an extent/indirect block (and has a negative logical offset);
 417          * we've crossed a logical cluster boundary; or the physical cluster
 418          * suddenly changed, which indicates that blocks in a logical cluster
 419          * are mapped to multiple physical clusters.
 420          */
 421         if (blockcnt < 0 || lc != p->cur_cluster || pc != p->phys_cluster)
 422                 add_dupe(ctx, p->ino, EXT2FS_B2C(fs, *block_nr), p->inode);
 423
 424 finish:
 425         p->cur_cluster = lc;
 426         p->phys_cluster = pc;
 427         return 0;
 428 }
 429
 430 /*
 431  * Pass 1c: Scan directories for inodes with duplicate blocks.  This
 432  * is used so that we can print pathnames when prompting the user for
 433  * what to do.
 434  */
 435 struct search_dir_struct {
 436         int             count;
 437         ext2_ino_t      first_inode;
 438         ext2_ino_t      max_inode;
 439 };
 440
 441 static int search_dirent_proc(ext2_ino_t dir, int entry,
 442                               struct ext2_dir_entry *dirent,
 443                               int offset EXT2FS_ATTR((unused)),
 444                               int blocksize EXT2FS_ATTR((unused)),
 445                               char *buf EXT2FS_ATTR((unused)),
 446                               void *priv_data)
 447 {
 448         struct search_dir_struct *sd;
 449         struct dup_inode        *p;
 450         dnode_t                 *n;
 451
 452         sd = (struct search_dir_struct *) priv_data;
 453
 454         if (dirent->inode > sd->max_inode)
 455                 /* Should abort this inode, but not everything */
 456                 return 0;
 457
 458         if ((dirent->inode < sd->first_inode) || (entry < DIRENT_OTHER_FILE) ||
 459             !ext2fs_test_inode_bitmap2(inode_dup_map, dirent->inode))
 460                 return 0;
 461
 462         n = dict_lookup(&ino_dict, INT_TO_VOIDPTR(dirent->inode));
 463         if (!n)
 464                 return 0;
 465         p = (struct dup_inode *) dnode_get(n);
 466         if (!p->dir) {
 467                 p->dir = dir;
 468                 sd->count--;
 469         }
 470
 471         return(sd->count ? 0 : DIRENT_ABORT);
 472 }
 473
 474
 475 static void pass1c(e2fsck_t ctx, char *block_buf)
 476 {
 477         ext2_filsys fs = ctx->fs;
 478         struct search_dir_struct sd;
 479         struct problem_context pctx;
 480
 481         clear_problem_context(&pctx);
 482
 483         if (!(ctx->options & E2F_OPT_PREEN))
 484                 fix_problem(ctx, PR_1C_PASS_HEADER, &pctx);
 485
 486         /*
 487          * Search through all directories to translate inodes to names
 488          * (by searching for the containing directory for that inode.)
 489          */
 490         sd.count = dup_inode_count - dup_inode_founddir;
 491         sd.first_inode = EXT2_FIRST_INODE(fs->super);
 492         sd.max_inode = fs->super->s_inodes_count;
 493         ext2fs_dblist_dir_iterate(fs->dblist, 0, block_buf,
 494                                   search_dirent_proc, &sd);
 495 }
 496
 497 static void pass1d(e2fsck_t ctx, char *block_buf)
 498 {
 499         ext2_filsys fs = ctx->fs;
 500         struct dup_inode        *p, *t;
 501         struct dup_cluster      *q;
 502         ext2_ino_t              *shared, ino;
 503         int     shared_len;
 504         int     i;
 505         int     file_ok;
 506         int     meta_data = 0;
 507         struct problem_context pctx;
 508         dnode_t *n, *m;
 509         struct cluster_el       *s;
 510         struct inode_el *r;
 511
 512         clear_problem_context(&pctx);
 513
 514         if (!(ctx->options & E2F_OPT_PREEN))
 515                 fix_problem(ctx, PR_1D_PASS_HEADER, &pctx);
 516         e2fsck_read_bitmaps(ctx);
 517
 518         pctx.num = dup_inode_count; /* dict_count(&ino_dict); */
 519         fix_problem(ctx, PR_1D_NUM_DUP_INODES, &pctx);
 520         shared = (ext2_ino_t *) e2fsck_allocate_memory(ctx,
 521                                 sizeof(ext2_ino_t) * dict_count(&ino_dict),
 522                                 "Shared inode list");
 523         for (n = dict_first(&ino_dict); n; n = dict_next(&ino_dict, n)) {
 524                 p = (struct dup_inode *) dnode_get(n);
 525                 shared_len = 0;
 526                 file_ok = 1;
 527                 ino = (ext2_ino_t)VOIDPTR_TO_INT(dnode_getkey(n));
 528                 if (ino == EXT2_BAD_INO || ino == EXT2_RESIZE_INO)
 529                         continue;
 530
 531                 /*
 532                  * Find all of the inodes which share blocks with this
 533                  * one.  First we find all of the duplicate blocks
 534                  * belonging to this inode, and then search each block
 535                  * get the list of inodes, and merge them together.
 536                  */
 537                 for (s = p->cluster_list; s; s = s->next) {
 538                         m = dict_lookup(&clstr_dict,
 539                                         INT_TO_VOIDPTR(s->cluster));
 540                         if (!m)
 541                                 continue; /* Should never happen... */
 542                         q = (struct dup_cluster *) dnode_get(m);
 543                         if (q->num_bad > 1)
 544                                 file_ok = 0;
 545                         if (q->num_bad == 1 && (ctx->clone == E2F_CLONE_ZERO ||
 546                             ctx->shared != E2F_SHARED_PRESERVE))
 547                                 file_ok = 0;
 548                         if (check_if_fs_cluster(ctx, s->cluster)) {
 549                                 file_ok = 0;
 550                                 meta_data = 1;
 551                         }
 552
 553                         /*
 554                          * Add all inodes used by this block to the
 555                          * shared[] --- which is a unique list, so
 556                          * if an inode is already in shared[], don't
 557                          * add it again.
 558                          */
 559                         for (r = q->inode_list; r; r = r->next) {
 560                                 if (r->inode == ino)
 561                                         continue;
 562                                 for (i = 0; i < shared_len; i++)
 563                                         if (shared[i] == r->inode)
 564                                                 break;
 565                                 if (i == shared_len) {
 566                                         shared[shared_len++] = r->inode;
 567                                 }
 568                         }
 569                 }
 570
 571                 /*
 572                  * Report the inode that we are working on
 573                  */
 574                 pctx.inode = EXT2_INODE(&p->inode);
 575                 pctx.ino = ino;
 576                 pctx.dir = p->dir;
 577                 pctx.blkcount = p->num_dupblocks;
 578                 pctx.num = meta_data ? shared_len+1 : shared_len;
 579                 fix_problem(ctx, PR_1D_DUP_FILE, &pctx);
 580                 pctx.blkcount = 0;
 581                 pctx.num = 0;
 582
 583                 if (meta_data)
 584                         fix_problem(ctx, PR_1D_SHARE_METADATA, &pctx);
 585
 586                 for (i = 0; i < shared_len; i++) {
 587                         m = dict_lookup(&ino_dict, INT_TO_VOIDPTR(shared[i]));
 588                         if (!m)
 589                                 continue; /* should never happen */
 590                         t = (struct dup_inode *) dnode_get(m);
 591                         /*
 592                          * Report the inode that we are sharing with
 593                          */
 594                         pctx.inode = EXT2_INODE(&t->inode);
 595                         pctx.ino = shared[i];
 596                         pctx.dir = t->dir;
 597                         fix_problem(ctx, PR_1D_DUP_FILE_LIST, &pctx);
 598                 }
 599                 /*
 600                  * Even if the file shares blocks with itself, we still need to
 601                  * clone the blocks.
 602                  */
 603                 if (file_ok && (meta_data ? shared_len+1 : shared_len) != 0) {
 604                         fix_problem(ctx, PR_1D_DUP_BLOCKS_DEALT, &pctx);
 605                         continue;
 606                 }
 607                 if (ctx->shared != E2F_SHARED_DELETE &&
 608                     ((ctx->options & E2F_OPT_UNSHARE_BLOCKS) ||
 609                     fix_problem(ctx, PR_1D_CLONE_QUESTION, &pctx))) {
 610                         pctx.errcode = clone_file(ctx, ino, p, block_buf);
 611                         if (pctx.errcode) {
 612                                 fix_problem(ctx, PR_1D_CLONE_ERROR, &pctx);
 613                                 goto delete;
 614                         }
 615                         if (ctx->shared == E2F_SHARED_LPF &&
 616                             fix_problem(ctx, PR_1D_DISCONNECT_QUESTION, &pctx)){
 617                                 pctx.errcode = ext2fs_unlink(fs, p->dir,
 618                                                              NULL, ino, 0);
 619                                 if (pctx.errcode) {
 620                                         fix_problem(ctx, PR_1D_DISCONNECT_ERROR,
 621                                                     &pctx);
 622                                         goto delete;
 623                                 }
 624                         }
 625                         continue;
 626                 }
 627 delete:
 628                 /*
 629                  * Note: When unsharing blocks, we don't prompt to delete
 630                  * files. If the clone operation fails than the unshare
 631                  * operation should fail too.
 632                  */
 633                 if (!(ctx->options & E2F_OPT_UNSHARE_BLOCKS) &&
 634                     fix_problem(ctx, PR_1D_DELETE_QUESTION, &pctx))
 635                         delete_file(ctx, ino, p, block_buf);
 636                 else
 637                         ext2fs_unmark_valid(fs);
 638         }
 639         ext2fs_free_mem(&shared);
 640 }
 641
 642 /*
 643  * Drop the refcount on the dup_block structure, and clear the entry
 644  * in the block_dup_map if appropriate.
 645  */
 646 static void decrement_badcount(e2fsck_t ctx, blk64_t block,
 647                                struct dup_cluster *p)
 648 {
 649         p->num_bad--;
 650         if (p->num_bad <= 0 ||
 651             (p->num_bad == 1 && !check_if_fs_block(ctx, block) &&
 652             ctx->clone == E2F_CLONE_DUP)) {
 653                 if (check_if_fs_cluster(ctx, EXT2FS_B2C(ctx->fs, block)))
 654                         return;
 655                 ext2fs_unmark_block_bitmap2(ctx->block_dup_map, block);
 656         }
 657 }
 658
 659 static int delete_file_block(ext2_filsys fs,
 660                              blk64_t    *block_nr,
 661                              e2_blkcnt_t blockcnt,
 662                              blk64_t ref_block EXT2FS_ATTR((unused)),
 663                              int ref_offset EXT2FS_ATTR((unused)),
 664                              void *priv_data)
 665 {
 666         struct process_block_struct *pb;
 667         struct dup_cluster *p;
 668         dnode_t *n;
 669         e2fsck_t ctx;
 670         blk64_t c, lc;
 671
 672         pb = (struct process_block_struct *) priv_data;
 673         ctx = pb->ctx;
 674
 675         if (*block_nr == 0)
 676                 return 0;
 677
 678         c = EXT2FS_B2C(fs, *block_nr);
 679         lc = EXT2FS_B2C(fs, blockcnt);
 680         if (ext2fs_test_block_bitmap2(ctx->block_dup_map, *block_nr)) {
 681                 n = dict_lookup(&clstr_dict, INT_TO_VOIDPTR(c));
 682                 if (n) {
 683                         if (lc != pb->cur_cluster) {
 684                                 p = (struct dup_cluster *) dnode_get(n);
 685                                 decrement_badcount(ctx, *block_nr, p);
 686                                 pb->dup_blocks++;
 687                         }
 688                 } else
 689                         com_err("delete_file_block", 0,
 690                             _("internal error: can't find dup_blk for %llu\n"),
 691                                 (unsigned long long) *block_nr);
 692         } else {
 693                 if ((*block_nr % EXT2FS_CLUSTER_RATIO(ctx->fs)) == 0)
 694                         ext2fs_block_alloc_stats2(fs, *block_nr, -1);
 695                 pb->dup_blocks++;
 696         }
 697         pb->cur_cluster = lc;
 698
 699         return 0;
 700 }
 701
 702 static void delete_file(e2fsck_t ctx, ext2_ino_t ino,
 703                         struct dup_inode *dp, char* block_buf)
 704 {
 705         ext2_filsys fs = ctx->fs;
 706         struct process_block_struct pb;
 707         struct problem_context  pctx;
 708         unsigned int            count;
 709
 710         clear_problem_context(&pctx);
 711         pctx.ino = pb.ino = ino;
 712         pb.dup_blocks = 0;
 713         pb.ctx = ctx;
 714         pctx.str = "delete_file";
 715         pb.cur_cluster = ~0;
 716
 717         if (ext2fs_inode_has_valid_blocks2(fs, EXT2_INODE(&dp->inode)))
 718                 pctx.errcode = ext2fs_block_iterate3(fs, ino,
 719                                                      BLOCK_FLAG_READ_ONLY,
 720                                                      block_buf,
 721                                                      delete_file_block, &pb);
 722         if (pctx.errcode)
 723                 fix_problem(ctx, PR_1B_BLOCK_ITERATE, &pctx);
 724         if (ctx->inode_bad_map)
 725                 ext2fs_unmark_inode_bitmap2(ctx->inode_bad_map, ino);
 726         if (ctx->inode_reg_map)
 727                 ext2fs_unmark_inode_bitmap2(ctx->inode_reg_map, ino);
 728         ext2fs_unmark_inode_bitmap2(ctx->inode_dir_map, ino);
 729         ext2fs_unmark_inode_bitmap2(ctx->inode_used_map, ino);
 730         ext2fs_inode_alloc_stats2(fs, ino, -1, LINUX_S_ISDIR(dp->inode.i_mode));
 731         quota_data_sub(ctx->qctx, &dp->inode, ino,
 732                        pb.dup_blocks * fs->blocksize);
 733         quota_data_inodes(ctx->qctx, &dp->inode, ino, -1);
 734
 735         /* Inode may have changed by block_iterate, so reread it */
 736         e2fsck_read_inode_full(ctx, ino, EXT2_INODE(&dp->inode),
 737                                sizeof(dp->inode), "delete_file");
 738         e2fsck_clear_inode(ctx, ino, EXT2_INODE(&dp->inode), 0, "delete_file");
 739         if (ext2fs_file_acl_block(fs, EXT2_INODE(&dp->inode)) &&
 740             ext2fs_has_feature_xattr(fs->super)) {
 741                 blk64_t file_acl_block = ext2fs_file_acl_block(fs,
 742                                                 EXT2_INODE(&dp->inode));
 743
 744                 count = 1;
 745                 pctx.errcode = ext2fs_adjust_ea_refcount3(fs, file_acl_block,
 746                                         block_buf, -1, &count, ino);
 747                 if (pctx.errcode == EXT2_ET_BAD_EA_BLOCK_NUM) {
 748                         pctx.errcode = 0;
 749                         count = 1;
 750                 }
 751                 if (pctx.errcode) {
 752                         pctx.blk = file_acl_block;
 753                         fix_problem(ctx, PR_1B_ADJ_EA_REFCOUNT, &pctx);
 754                 }
 755                 /*
 756                  * If the count is zero, then arrange to have the
 757                  * block deleted.  If the block is in the block_dup_map,
 758                  * also call delete_file_block since it will take care
 759                  * of keeping the accounting straight.
 760                  */
 761                 if ((count == 0) ||
 762                     ext2fs_test_block_bitmap2(ctx->block_dup_map,
 763                                               file_acl_block)) {
 764                         delete_file_block(fs, &file_acl_block,
 765                                           BLOCK_COUNT_EXTATTR, 0, 0, &pb);
 766                         ext2fs_file_acl_block_set(fs, EXT2_INODE(&dp->inode),
 767                                                   file_acl_block);
 768                         quota_data_sub(ctx->qctx, &dp->inode, ino,
 769                                        fs->blocksize);
 770                 }
 771         }
 772 }
 773
 774 struct clone_struct {
 775         errcode_t       errcode;
 776         blk64_t         dup_cluster;
 777         blk64_t         alloc_block;
 778         ext2_ino_t      dir, ino;
 779         char    *buf;
 780         e2fsck_t ctx;
 781         struct ext2_inode_large *inode;
 782
 783         struct dup_cluster *save_dup_cluster;
 784         blk64_t save_blocknr;
 785 };
 786
 787 /*
 788  * Decrement the bad count *after* we've shown that (a) we can allocate a
 789  * replacement block and (b) remap the file blocks.  Unfortunately, there's no
 790  * way to find out if the remap succeeded until either the next
 791  * clone_file_block() call (an error when remapping the block after returning
 792  * BLOCK_CHANGED will halt the iteration) or after block_iterate() returns.
 793  * Otherwise, it's possible that we decrease the badcount once in preparation
 794  * to remap, then the remap fails (either we can't find a replacement block or
 795  * we have to split the extent tree and can't find a new extent block), so we
 796  * delete the file, which decreases the badcount again.
 797  */
 798 static void deferred_dec_badcount(struct clone_struct *cs)
 799 {
 800         if (!cs->save_dup_cluster)
 801                 return;
 802         decrement_badcount(cs->ctx, cs->save_blocknr, cs->save_dup_cluster);
 803         if (cs->ctx->clone == E2F_CLONE_ZERO &&
 804             cs->save_dup_cluster->num_bad == 0) {
 805                 ext2fs_unmark_block_bitmap2(cs->ctx->block_found_map,
 806                                             cs->save_blocknr);
 807                 ext2fs_block_alloc_stats(cs->ctx->fs, cs->save_blocknr, -1);
 808         }
 809         cs->save_dup_cluster = NULL;
 810 }
 811
 812 static int clone_file_block(ext2_filsys fs,
 813                             blk64_t     *block_nr,
 814                             e2_blkcnt_t blockcnt,
 815                             blk64_t ref_block EXT2FS_ATTR((unused)),
 816                             int ref_offset EXT2FS_ATTR((unused)),
 817                             void *priv_data)
 818 {
 819         struct dup_cluster *p = NULL;
 820         blk64_t new_block;
 821         errcode_t       retval;
 822         struct clone_struct *cs = (struct clone_struct *) priv_data;
 823         dnode_t *n;
 824         e2fsck_t ctx;
 825         blk64_t c;
 826         int is_meta = 0;
 827         int should_write = 1;
 828
 829         ctx = cs->ctx;
 830         deferred_dec_badcount(cs);
 831
 832         if (*block_nr == 0)
 833                 return 0;
 834
 835         if (ext2fs_has_feature_shared_blocks(ctx->fs->super) &&
 836             (ctx->options & E2F_OPT_UNSHARE_BLOCKS) &&
 837             (ctx->options & E2F_OPT_NO))
 838                 should_write = 0;
 839
 840         c = EXT2FS_B2C(fs, blockcnt);
 841         if (check_if_fs_cluster(ctx, EXT2FS_B2C(fs, *block_nr)))
 842                 is_meta = 1;
 843
 844         if (c == cs->dup_cluster && cs->alloc_block) {
 845                 new_block = cs->alloc_block;
 846                 goto got_block;
 847         }
 848
 849         if (ext2fs_test_block_bitmap2(ctx->block_dup_map, *block_nr)) {
 850                 n = dict_lookup(&clstr_dict,
 851                                 INT_TO_VOIDPTR(EXT2FS_B2C(fs, *block_nr)));
 852                 if (!n) {
 853                         com_err("clone_file_block", 0,
 854                             _("internal error: can't find dup_blk for %llu\n"),
 855                                 (unsigned long long) *block_nr);
 856                         return 0;
 857                 }
 858
 859                 p = (struct dup_cluster *) dnode_get(n);
 860
 861                 cs->dup_cluster = c;
 862                 /*
 863                  * Let's try an implied cluster allocation.  If we get the same
 864                  * cluster back, then we need to find a new block; otherwise,
 865                  * we're merely fixing the problem of one logical cluster being
 866                  * mapped to multiple physical clusters.
 867                  */
 868                 new_block = 0;
 869                 retval = ext2fs_map_cluster_block(fs, cs->ino,
 870                                                   EXT2_INODE(cs->inode),
 871                                                   blockcnt, &new_block);
 872                 if (retval == 0 && new_block != 0 &&
 873                     EXT2FS_B2C(ctx->fs, new_block) !=
 874                     EXT2FS_B2C(ctx->fs, *block_nr))
 875                         goto cluster_alloc_ok;
 876                 retval = ext2fs_new_block2(fs, 0, ctx->block_found_map,
 877                                            &new_block);
 878                 if (retval) {
 879                         cs->errcode = retval;
 880                         return BLOCK_ABORT;
 881                 }
 882                 if (ext2fs_has_feature_shared_blocks(fs->super)) {
 883                         /*
 884                          * Update the block stats so we don't get a prompt to fix block
 885                          * counts in the final pass.
 886                          */
 887                         ext2fs_block_alloc_stats2(fs, new_block, +1);
 888                 }
 889 cluster_alloc_ok:
 890                 cs->alloc_block = new_block;
 891
 892         got_block:
 893                 new_block &= ~EXT2FS_CLUSTER_MASK(fs);
 894                 new_block += EXT2FS_CLUSTER_MASK(fs) & blockcnt;
 895                 if (cs->dir && (blockcnt >= 0)) {
 896                         retval = ext2fs_set_dir_block2(fs->dblist,
 897                                         cs->dir, new_block, blockcnt);
 898                         if (retval) {
 899                                 cs->errcode = retval;
 900                                 return BLOCK_ABORT;
 901                         }
 902                 }
 903 #if 0
 904                 printf("Cloning block #%lld from %llu to %llu\n",
 905                        blockcnt, (unsigned long long) *block_nr,
 906                        (unsigned long long) new_block);
 907 #endif
 908                 if (ctx->clone == E2F_CLONE_ZERO) {
 909                         memset(cs->buf, 0, fs->blocksize);
 910                 } else {
 911                         retval = io_channel_read_blk64(fs->io, *block_nr, 1,
 912                                                        cs->buf);
 913                         if (retval) {
 914                                 cs->errcode = retval;
 915                                 return BLOCK_ABORT;
 916                         }
 917                 }
 918                 if (should_write) {
 919                         retval = io_channel_write_blk64(fs->io, new_block, 1, cs->buf);
 920                         if (retval) {
 921                                 cs->errcode = retval;
 922                                 return BLOCK_ABORT;
 923                         }
 924                 }
 925                 cs->save_dup_cluster = (is_meta ? NULL : p);
 926                 cs->save_blocknr = *block_nr;
 927                 *block_nr = new_block;
 928                 ext2fs_mark_block_bitmap2(ctx->block_found_map, new_block);
 929                 ext2fs_mark_block_bitmap2(fs->block_map, new_block);
 930
 931                 if (!should_write) {
 932                         /* Don't try to change extent information; we want e2fsck to
 933                          * return success.
 934                          */
 935                         return 0;
 936                 }
 937                 return BLOCK_CHANGED;
 938         }
 939         return 0;
 940 }
 941
 942 static errcode_t clone_file(e2fsck_t ctx, ext2_ino_t ino,
 943                             struct dup_inode *dp, char* block_buf)
 944 {
 945         ext2_filsys fs = ctx->fs;
 946         errcode_t       retval;
 947         struct clone_struct cs;
 948         struct problem_context  pctx;
 949         blk64_t         blk, new_blk;
 950         dnode_t         *n;
 951         struct inode_el *ino_el;
 952         struct dup_cluster      *dc;
 953         struct dup_inode        *di;
 954
 955         clear_problem_context(&pctx);
 956         cs.errcode = 0;
 957         cs.dir = 0;
 958         cs.dup_cluster = ~0;
 959         cs.alloc_block = 0;
 960         cs.ctx = ctx;
 961         cs.ino = ino;
 962         cs.inode = &dp->inode;
 963         cs.save_dup_cluster = NULL;
 964         cs.save_blocknr = 0;
 965         retval = ext2fs_get_mem(fs->blocksize, &cs.buf);
 966         if (retval)
 967                 return retval;
 968
 969         if (ext2fs_test_inode_bitmap2(ctx->inode_dir_map, ino))
 970                 cs.dir = ino;
 971
 972         pctx.ino = ino;
 973         pctx.str = "clone_file";
 974         if (ext2fs_inode_has_valid_blocks2(fs, EXT2_INODE(&dp->inode)))
 975                 pctx.errcode = ext2fs_block_iterate3(fs, ino, 0, block_buf,
 976                                                      clone_file_block, &cs);
 977         deferred_dec_badcount(&cs);
 978         ext2fs_mark_bb_dirty(fs);
 979         if (pctx.errcode) {
 980                 fix_problem(ctx, PR_1B_BLOCK_ITERATE, &pctx);
 981                 retval = pctx.errcode;
 982                 goto errout;
 983         }
 984         if (cs.errcode) {
 985                 com_err("clone_file", cs.errcode, "%s",
 986                         _("returned from clone_file_block"));
 987                 retval = cs.errcode;
 988                 goto errout;
 989         }
 990         /* The inode may have changed on disk, so we have to re-read it */
 991         e2fsck_read_inode_full(ctx, ino, EXT2_INODE(&dp->inode),
 992                                sizeof(dp->inode), "clone file EA");
 993         blk = ext2fs_file_acl_block(fs, EXT2_INODE(&dp->inode));
 994         new_blk = blk;
 995         if (blk && (clone_file_block(fs, &new_blk,
 996                                      BLOCK_COUNT_EXTATTR, 0, 0, &cs) ==
 997                     BLOCK_CHANGED)) {
 998                 ext2fs_file_acl_block_set(fs, EXT2_INODE(&dp->inode), new_blk);
 999                 e2fsck_write_inode_full(ctx, ino, EXT2_INODE(&dp->inode),
1000                                         sizeof(dp->inode), "clone file EA");
1001                 /*
1002                  * If we cloned the EA block, find all other inodes
1003                  * which referred to that EA block, and modify
1004                  * them to point to the new EA block.
1005                  */
1006                 n = dict_lookup(&clstr_dict,
1007                                 INT_TO_VOIDPTR(EXT2FS_B2C(fs, blk)));
1008                 if (!n) {
1009                         com_err("clone_file", 0,
1010                                 _("internal error: couldn't lookup EA "
1011                                   "block record for %llu"),
1012                                 (unsigned long long) blk);
1013                         retval = 0; /* OK to stumble on... */
1014                         goto errout;
1015                 }
1016                 dc = (struct dup_cluster *) dnode_get(n);
1017                 for (ino_el = dc->inode_list; ino_el; ino_el = ino_el->next) {
1018                         if (ino_el->inode == ino)
1019                                 continue;
1020                         n = dict_lookup(&ino_dict, INT_TO_VOIDPTR(ino_el->inode));
1021                         if (!n) {
1022                                 com_err("clone_file", 0,
1023                                         _("internal error: couldn't lookup EA "
1024                                           "inode record for %u"),
1025                                         ino_el->inode);
1026                                 retval = 0; /* OK to stumble on... */
1027                                 goto errout;
1028                         }
1029                         di = (struct dup_inode *) dnode_get(n);
1030                         if (ext2fs_file_acl_block(fs,
1031                                         EXT2_INODE(&di->inode)) == blk) {
1032                                 ext2fs_file_acl_block_set(fs,
1033                                         EXT2_INODE(&di->inode),
1034                                         ext2fs_file_acl_block(fs, EXT2_INODE(&dp->inode)));
1035                                 e2fsck_write_inode_full(ctx, ino_el->inode,
1036                                         EXT2_INODE(&di->inode),
1037                                         sizeof(di->inode), "clone file EA");
1038                                 decrement_badcount(ctx, blk, dc);
1039                         }
1040                 }
1041         }
1042         retval = 0;
1043 errout:
1044         ext2fs_free_mem(&cs.buf);
1045         return retval;
1046 }
1047
1048 /*
1049  * This routine returns 1 if a block overlaps with one of the superblocks,
1050  * group descriptors, inode bitmaps, or block bitmaps.
1051  */
1052 static int check_if_fs_block(e2fsck_t ctx, blk64_t test_block)
1053 {
1054         ext2_filsys fs = ctx->fs;
1055         blk64_t first_block;
1056         dgrp_t  i;
1057
1058         first_block = fs->super->s_first_data_block;
1059         for (i = 0; i < fs->group_desc_count; i++) {
1060
1061                 /* Check superblocks/block group descriptors */
1062                 if (ext2fs_bg_has_super(fs, i)) {
1063                         if (test_block >= first_block &&
1064                             (test_block <= first_block + fs->desc_blocks))
1065                                 return 1;
1066                 }
1067
1068                 /* Check the inode table */
1069                 if ((ext2fs_inode_table_loc(fs, i)) &&
1070                     (test_block >= ext2fs_inode_table_loc(fs, i)) &&
1071                     (test_block < (ext2fs_inode_table_loc(fs, i) +
1072                                    fs->inode_blocks_per_group)))
1073                         return 1;
1074
1075                 /* Check the bitmap blocks */
1076                 if ((test_block == ext2fs_block_bitmap_loc(fs, i)) ||
1077                     (test_block == ext2fs_inode_bitmap_loc(fs, i)))
1078                         return 1;
1079
1080                 first_block += fs->super->s_blocks_per_group;
1081         }
1082         return 0;
1083 }
1084
1085 /*
1086  * This routine returns 1 if a cluster overlaps with one of the superblocks,
1087  * group descriptors, inode bitmaps, or block bitmaps.
1088  */
1089 static int check_if_fs_cluster(e2fsck_t ctx, blk64_t cluster)
1090 {
1091         ext2_filsys fs = ctx->fs;
1092         blk64_t first_block;
1093         dgrp_t  i;
1094
1095         first_block = fs->super->s_first_data_block;
1096         for (i = 0; i < fs->group_desc_count; i++) {
1097
1098                 /* Check superblocks/block group descriptors */
1099                 if (ext2fs_bg_has_super(fs, i)) {
1100                         if (cluster >= EXT2FS_B2C(fs, first_block) &&
1101                             (cluster <= EXT2FS_B2C(fs, first_block +
1102                                                    fs->desc_blocks)))
1103                                 return 1;
1104                 }
1105
1106                 /* Check the inode table */
1107                 if ((ext2fs_inode_table_loc(fs, i)) &&
1108                     (cluster >= EXT2FS_B2C(fs,
1109                                            ext2fs_inode_table_loc(fs, i))) &&
1110                     (cluster <= EXT2FS_B2C(fs,
1111                                            ext2fs_inode_table_loc(fs, i) +
1112                                            fs->inode_blocks_per_group - 1)))
1113                         return 1;
1114
1115                 /* Check the bitmap blocks */
1116                 if ((cluster == EXT2FS_B2C(fs,
1117                                            ext2fs_block_bitmap_loc(fs, i))) ||
1118                     (cluster == EXT2FS_B2C(fs,
1119                                            ext2fs_inode_bitmap_loc(fs, i))))
1120                         return 1;
1121
1122                 first_block += fs->super->s_blocks_per_group;
1123         }
1124         return 0;
1125 }