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 (check_if_fs_cluster(ctx, s->cluster)) {
 546                                 file_ok = 0;
 547                                 meta_data = 1;
 548                         }
 549
 550                         /*
 551                          * Add all inodes used by this block to the
 552                          * shared[] --- which is a unique list, so
 553                          * if an inode is already in shared[], don't
 554                          * add it again.
 555                          */
 556                         for (r = q->inode_list; r; r = r->next) {
 557                                 if (r->inode == ino)
 558                                         continue;
 559                                 for (i = 0; i < shared_len; i++)
 560                                         if (shared[i] == r->inode)
 561                                                 break;
 562                                 if (i == shared_len) {
 563                                         shared[shared_len++] = r->inode;
 564                                 }
 565                         }
 566                 }
 567
 568                 /*
 569                  * Report the inode that we are working on
 570                  */
 571                 pctx.inode = EXT2_INODE(&p->inode);
 572                 pctx.ino = ino;
 573                 pctx.dir = p->dir;
 574                 pctx.blkcount = p->num_dupblocks;
 575                 pctx.num = meta_data ? shared_len+1 : shared_len;
 576                 fix_problem(ctx, PR_1D_DUP_FILE, &pctx);
 577                 pctx.blkcount = 0;
 578                 pctx.num = 0;
 579
 580                 if (meta_data)
 581                         fix_problem(ctx, PR_1D_SHARE_METADATA, &pctx);
 582
 583                 for (i = 0; i < shared_len; i++) {
 584                         m = dict_lookup(&ino_dict, INT_TO_VOIDPTR(shared[i]));
 585                         if (!m)
 586                                 continue; /* should never happen */
 587                         t = (struct dup_inode *) dnode_get(m);
 588                         /*
 589                          * Report the inode that we are sharing with
 590                          */
 591                         pctx.inode = EXT2_INODE(&t->inode);
 592                         pctx.ino = shared[i];
 593                         pctx.dir = t->dir;
 594                         fix_problem(ctx, PR_1D_DUP_FILE_LIST, &pctx);
 595                 }
 596                 /*
 597                  * Even if the file shares blocks with itself, we still need to
 598                  * clone the blocks.
 599                  */
 600                 if (file_ok && (meta_data ? shared_len+1 : shared_len) != 0) {
 601                         fix_problem(ctx, PR_1D_DUP_BLOCKS_DEALT, &pctx);
 602                         continue;
 603                 }
 604                 if ((ctx->options & E2F_OPT_UNSHARE_BLOCKS) ||
 605                     fix_problem(ctx, PR_1D_CLONE_QUESTION, &pctx)) {
 606                         pctx.errcode = clone_file(ctx, ino, p, block_buf);
 607                         if (pctx.errcode)
 608                                 fix_problem(ctx, PR_1D_CLONE_ERROR, &pctx);
 609                         else
 610                                 continue;
 611                 }
 612                 /*
 613                  * Note: When unsharing blocks, we don't prompt to delete
 614                  * files. If the clone operation fails than the unshare
 615                  * operation should fail too.
 616                  */
 617                 if (!(ctx->options & E2F_OPT_UNSHARE_BLOCKS) &&
 618                     fix_problem(ctx, PR_1D_DELETE_QUESTION, &pctx))
 619                         delete_file(ctx, ino, p, block_buf);
 620                 else
 621                         ext2fs_unmark_valid(fs);
 622         }
 623         ext2fs_free_mem(&shared);
 624 }
 625
 626 /*
 627  * Drop the refcount on the dup_block structure, and clear the entry
 628  * in the block_dup_map if appropriate.
 629  */
 630 static void decrement_badcount(e2fsck_t ctx, blk64_t block,
 631                                struct dup_cluster *p)
 632 {
 633         p->num_bad--;
 634         if (p->num_bad <= 0 ||
 635             (p->num_bad == 1 && !check_if_fs_block(ctx, block))) {
 636                 if (check_if_fs_cluster(ctx, EXT2FS_B2C(ctx->fs, block)))
 637                         return;
 638                 ext2fs_unmark_block_bitmap2(ctx->block_dup_map, block);
 639         }
 640 }
 641
 642 static int delete_file_block(ext2_filsys fs,
 643                              blk64_t    *block_nr,
 644                              e2_blkcnt_t blockcnt,
 645                              blk64_t ref_block EXT2FS_ATTR((unused)),
 646                              int ref_offset EXT2FS_ATTR((unused)),
 647                              void *priv_data)
 648 {
 649         struct process_block_struct *pb;
 650         struct dup_cluster *p;
 651         dnode_t *n;
 652         e2fsck_t ctx;
 653         blk64_t c, lc;
 654
 655         pb = (struct process_block_struct *) priv_data;
 656         ctx = pb->ctx;
 657
 658         if (*block_nr == 0)
 659                 return 0;
 660
 661         c = EXT2FS_B2C(fs, *block_nr);
 662         lc = EXT2FS_B2C(fs, blockcnt);
 663         if (ext2fs_test_block_bitmap2(ctx->block_dup_map, *block_nr)) {
 664                 n = dict_lookup(&clstr_dict, INT_TO_VOIDPTR(c));
 665                 if (n) {
 666                         if (lc != pb->cur_cluster) {
 667                                 p = (struct dup_cluster *) dnode_get(n);
 668                                 decrement_badcount(ctx, *block_nr, p);
 669                                 pb->dup_blocks++;
 670                         }
 671                 } else
 672                         com_err("delete_file_block", 0,
 673                             _("internal error: can't find dup_blk for %llu\n"),
 674                                 (unsigned long long) *block_nr);
 675         } else {
 676                 if ((*block_nr % EXT2FS_CLUSTER_RATIO(ctx->fs)) == 0)
 677                         ext2fs_block_alloc_stats2(fs, *block_nr, -1);
 678                 pb->dup_blocks++;
 679         }
 680         pb->cur_cluster = lc;
 681
 682         return 0;
 683 }
 684
 685 static void delete_file(e2fsck_t ctx, ext2_ino_t ino,
 686                         struct dup_inode *dp, char* block_buf)
 687 {
 688         ext2_filsys fs = ctx->fs;
 689         struct process_block_struct pb;
 690         struct problem_context  pctx;
 691         unsigned int            count;
 692
 693         clear_problem_context(&pctx);
 694         pctx.ino = pb.ino = ino;
 695         pb.dup_blocks = 0;
 696         pb.ctx = ctx;
 697         pctx.str = "delete_file";
 698         pb.cur_cluster = ~0;
 699
 700         if (ext2fs_inode_has_valid_blocks2(fs, EXT2_INODE(&dp->inode)))
 701                 pctx.errcode = ext2fs_block_iterate3(fs, ino,
 702                                                      BLOCK_FLAG_READ_ONLY,
 703                                                      block_buf,
 704                                                      delete_file_block, &pb);
 705         if (pctx.errcode)
 706                 fix_problem(ctx, PR_1B_BLOCK_ITERATE, &pctx);
 707         if (ctx->inode_bad_map)
 708                 ext2fs_unmark_inode_bitmap2(ctx->inode_bad_map, ino);
 709         if (ctx->inode_reg_map)
 710                 ext2fs_unmark_inode_bitmap2(ctx->inode_reg_map, ino);
 711         ext2fs_unmark_inode_bitmap2(ctx->inode_dir_map, ino);
 712         ext2fs_unmark_inode_bitmap2(ctx->inode_used_map, ino);
 713         ext2fs_inode_alloc_stats2(fs, ino, -1, LINUX_S_ISDIR(dp->inode.i_mode));
 714         quota_data_sub(ctx->qctx, &dp->inode, ino,
 715                        pb.dup_blocks * fs->blocksize);
 716         quota_data_inodes(ctx->qctx, &dp->inode, ino, -1);
 717
 718         /* Inode may have changed by block_iterate, so reread it */
 719         e2fsck_read_inode_full(ctx, ino, EXT2_INODE(&dp->inode),
 720                                sizeof(dp->inode), "delete_file");
 721         e2fsck_clear_inode(ctx, ino, EXT2_INODE(&dp->inode), 0, "delete_file");
 722         if (ext2fs_file_acl_block(fs, EXT2_INODE(&dp->inode)) &&
 723             ext2fs_has_feature_xattr(fs->super)) {
 724                 blk64_t file_acl_block = ext2fs_file_acl_block(fs,
 725                                                 EXT2_INODE(&dp->inode));
 726
 727                 count = 1;
 728                 pctx.errcode = ext2fs_adjust_ea_refcount3(fs, file_acl_block,
 729                                         block_buf, -1, &count, ino);
 730                 if (pctx.errcode == EXT2_ET_BAD_EA_BLOCK_NUM) {
 731                         pctx.errcode = 0;
 732                         count = 1;
 733                 }
 734                 if (pctx.errcode) {
 735                         pctx.blk = file_acl_block;
 736                         fix_problem(ctx, PR_1B_ADJ_EA_REFCOUNT, &pctx);
 737                 }
 738                 /*
 739                  * If the count is zero, then arrange to have the
 740                  * block deleted.  If the block is in the block_dup_map,
 741                  * also call delete_file_block since it will take care
 742                  * of keeping the accounting straight.
 743                  */
 744                 if ((count == 0) ||
 745                     ext2fs_test_block_bitmap2(ctx->block_dup_map,
 746                                               file_acl_block)) {
 747                         delete_file_block(fs, &file_acl_block,
 748                                           BLOCK_COUNT_EXTATTR, 0, 0, &pb);
 749                         ext2fs_file_acl_block_set(fs, EXT2_INODE(&dp->inode),
 750                                                   file_acl_block);
 751                         quota_data_sub(ctx->qctx, &dp->inode, ino,
 752                                        fs->blocksize);
 753                 }
 754         }
 755 }
 756
 757 struct clone_struct {
 758         errcode_t       errcode;
 759         blk64_t         dup_cluster;
 760         blk64_t         alloc_block;
 761         ext2_ino_t      dir, ino;
 762         char    *buf;
 763         e2fsck_t ctx;
 764         struct ext2_inode_large *inode;
 765
 766         struct dup_cluster *save_dup_cluster;
 767         blk64_t save_blocknr;
 768 };
 769
 770 /*
 771  * Decrement the bad count *after* we've shown that (a) we can allocate a
 772  * replacement block and (b) remap the file blocks.  Unfortunately, there's no
 773  * way to find out if the remap succeeded until either the next
 774  * clone_file_block() call (an error when remapping the block after returning
 775  * BLOCK_CHANGED will halt the iteration) or after block_iterate() returns.
 776  * Otherwise, it's possible that we decrease the badcount once in preparation
 777  * to remap, then the remap fails (either we can't find a replacement block or
 778  * we have to split the extent tree and can't find a new extent block), so we
 779  * delete the file, which decreases the badcount again.
 780  */
 781 static void deferred_dec_badcount(struct clone_struct *cs)
 782 {
 783         if (!cs->save_dup_cluster)
 784                 return;
 785         decrement_badcount(cs->ctx, cs->save_blocknr, cs->save_dup_cluster);
 786         cs->save_dup_cluster = NULL;
 787 }
 788
 789 static int clone_file_block(ext2_filsys fs,
 790                             blk64_t     *block_nr,
 791                             e2_blkcnt_t blockcnt,
 792                             blk64_t ref_block EXT2FS_ATTR((unused)),
 793                             int ref_offset EXT2FS_ATTR((unused)),
 794                             void *priv_data)
 795 {
 796         struct dup_cluster *p = NULL;
 797         blk64_t new_block;
 798         errcode_t       retval;
 799         struct clone_struct *cs = (struct clone_struct *) priv_data;
 800         dnode_t *n;
 801         e2fsck_t ctx;
 802         blk64_t c;
 803         int is_meta = 0;
 804         int should_write = 1;
 805
 806         ctx = cs->ctx;
 807         deferred_dec_badcount(cs);
 808
 809         if (*block_nr == 0)
 810                 return 0;
 811
 812         if (ext2fs_has_feature_shared_blocks(ctx->fs->super) &&
 813             (ctx->options & E2F_OPT_UNSHARE_BLOCKS) &&
 814             (ctx->options & E2F_OPT_NO))
 815                 should_write = 0;
 816
 817         c = EXT2FS_B2C(fs, blockcnt);
 818         if (check_if_fs_cluster(ctx, EXT2FS_B2C(fs, *block_nr)))
 819                 is_meta = 1;
 820
 821         if (c == cs->dup_cluster && cs->alloc_block) {
 822                 new_block = cs->alloc_block;
 823                 goto got_block;
 824         }
 825
 826         if (ext2fs_test_block_bitmap2(ctx->block_dup_map, *block_nr)) {
 827                 n = dict_lookup(&clstr_dict,
 828                                 INT_TO_VOIDPTR(EXT2FS_B2C(fs, *block_nr)));
 829                 if (!n) {
 830                         com_err("clone_file_block", 0,
 831                             _("internal error: can't find dup_blk for %llu\n"),
 832                                 (unsigned long long) *block_nr);
 833                         return 0;
 834                 }
 835
 836                 p = (struct dup_cluster *) dnode_get(n);
 837
 838                 cs->dup_cluster = c;
 839                 /*
 840                  * Let's try an implied cluster allocation.  If we get the same
 841                  * cluster back, then we need to find a new block; otherwise,
 842                  * we're merely fixing the problem of one logical cluster being
 843                  * mapped to multiple physical clusters.
 844                  */
 845                 new_block = 0;
 846                 retval = ext2fs_map_cluster_block(fs, cs->ino,
 847                                                   EXT2_INODE(cs->inode),
 848                                                   blockcnt, &new_block);
 849                 if (retval == 0 && new_block != 0 &&
 850                     EXT2FS_B2C(ctx->fs, new_block) !=
 851                     EXT2FS_B2C(ctx->fs, *block_nr))
 852                         goto cluster_alloc_ok;
 853                 retval = ext2fs_new_block2(fs, 0, ctx->block_found_map,
 854                                            &new_block);
 855                 if (retval) {
 856                         cs->errcode = retval;
 857                         return BLOCK_ABORT;
 858                 }
 859                 if (ext2fs_has_feature_shared_blocks(fs->super)) {
 860                         /*
 861                          * Update the block stats so we don't get a prompt to fix block
 862                          * counts in the final pass.
 863                          */
 864                         ext2fs_block_alloc_stats2(fs, new_block, +1);
 865                 }
 866 cluster_alloc_ok:
 867                 cs->alloc_block = new_block;
 868
 869         got_block:
 870                 new_block &= ~EXT2FS_CLUSTER_MASK(fs);
 871                 new_block += EXT2FS_CLUSTER_MASK(fs) & blockcnt;
 872                 if (cs->dir && (blockcnt >= 0)) {
 873                         retval = ext2fs_set_dir_block2(fs->dblist,
 874                                         cs->dir, new_block, blockcnt);
 875                         if (retval) {
 876                                 cs->errcode = retval;
 877                                 return BLOCK_ABORT;
 878                         }
 879                 }
 880 #if 0
 881                 printf("Cloning block #%lld from %llu to %llu\n",
 882                        blockcnt, (unsigned long long) *block_nr,
 883                        (unsigned long long) new_block);
 884 #endif
 885                 retval = io_channel_read_blk64(fs->io, *block_nr, 1, cs->buf);
 886                 if (retval) {
 887                         cs->errcode = retval;
 888                         return BLOCK_ABORT;
 889                 }
 890                 if (should_write) {
 891                         retval = io_channel_write_blk64(fs->io, new_block, 1, cs->buf);
 892                         if (retval) {
 893                                 cs->errcode = retval;
 894                                 return BLOCK_ABORT;
 895                         }
 896                 }
 897                 cs->save_dup_cluster = (is_meta ? NULL : p);
 898                 cs->save_blocknr = *block_nr;
 899                 *block_nr = new_block;
 900                 ext2fs_mark_block_bitmap2(ctx->block_found_map, new_block);
 901                 ext2fs_mark_block_bitmap2(fs->block_map, new_block);
 902
 903                 if (!should_write) {
 904                         /* Don't try to change extent information; we want e2fsck to
 905                          * return success.
 906                          */
 907                         return 0;
 908                 }
 909                 return BLOCK_CHANGED;
 910         }
 911         return 0;
 912 }
 913
 914 static errcode_t clone_file(e2fsck_t ctx, ext2_ino_t ino,
 915                             struct dup_inode *dp, char* block_buf)
 916 {
 917         ext2_filsys fs = ctx->fs;
 918         errcode_t       retval;
 919         struct clone_struct cs;
 920         struct problem_context  pctx;
 921         blk64_t         blk, new_blk;
 922         dnode_t         *n;
 923         struct inode_el *ino_el;
 924         struct dup_cluster      *dc;
 925         struct dup_inode        *di;
 926
 927         clear_problem_context(&pctx);
 928         cs.errcode = 0;
 929         cs.dir = 0;
 930         cs.dup_cluster = ~0;
 931         cs.alloc_block = 0;
 932         cs.ctx = ctx;
 933         cs.ino = ino;
 934         cs.inode = &dp->inode;
 935         cs.save_dup_cluster = NULL;
 936         cs.save_blocknr = 0;
 937         retval = ext2fs_get_mem(fs->blocksize, &cs.buf);
 938         if (retval)
 939                 return retval;
 940
 941         if (ext2fs_test_inode_bitmap2(ctx->inode_dir_map, ino))
 942                 cs.dir = ino;
 943
 944         pctx.ino = ino;
 945         pctx.str = "clone_file";
 946         if (ext2fs_inode_has_valid_blocks2(fs, EXT2_INODE(&dp->inode)))
 947                 pctx.errcode = ext2fs_block_iterate3(fs, ino, 0, block_buf,
 948                                                      clone_file_block, &cs);
 949         deferred_dec_badcount(&cs);
 950         ext2fs_mark_bb_dirty(fs);
 951         if (pctx.errcode) {
 952                 fix_problem(ctx, PR_1B_BLOCK_ITERATE, &pctx);
 953                 retval = pctx.errcode;
 954                 goto errout;
 955         }
 956         if (cs.errcode) {
 957                 com_err("clone_file", cs.errcode, "%s",
 958                         _("returned from clone_file_block"));
 959                 retval = cs.errcode;
 960                 goto errout;
 961         }
 962         /* The inode may have changed on disk, so we have to re-read it */
 963         e2fsck_read_inode_full(ctx, ino, EXT2_INODE(&dp->inode),
 964                                sizeof(dp->inode), "clone file EA");
 965         blk = ext2fs_file_acl_block(fs, EXT2_INODE(&dp->inode));
 966         new_blk = blk;
 967         if (blk && (clone_file_block(fs, &new_blk,
 968                                      BLOCK_COUNT_EXTATTR, 0, 0, &cs) ==
 969                     BLOCK_CHANGED)) {
 970                 ext2fs_file_acl_block_set(fs, EXT2_INODE(&dp->inode), new_blk);
 971                 e2fsck_write_inode_full(ctx, ino, EXT2_INODE(&dp->inode),
 972                                         sizeof(dp->inode), "clone file EA");
 973                 /*
 974                  * If we cloned the EA block, find all other inodes
 975                  * which referred to that EA block, and modify
 976                  * them to point to the new EA block.
 977                  */
 978                 n = dict_lookup(&clstr_dict,
 979                                 INT_TO_VOIDPTR(EXT2FS_B2C(fs, blk)));
 980                 if (!n) {
 981                         com_err("clone_file", 0,
 982                                 _("internal error: couldn't lookup EA "
 983                                   "block record for %llu"),
 984                                 (unsigned long long) blk);
 985                         retval = 0; /* OK to stumble on... */
 986                         goto errout;
 987                 }
 988                 dc = (struct dup_cluster *) dnode_get(n);
 989                 for (ino_el = dc->inode_list; ino_el; ino_el = ino_el->next) {
 990                         if (ino_el->inode == ino)
 991                                 continue;
 992                         n = dict_lookup(&ino_dict, INT_TO_VOIDPTR(ino_el->inode));
 993                         if (!n) {
 994                                 com_err("clone_file", 0,
 995                                         _("internal error: couldn't lookup EA "
 996                                           "inode record for %u"),
 997                                         ino_el->inode);
 998                                 retval = 0; /* OK to stumble on... */
 999                                 goto errout;
1000                         }
1001                         di = (struct dup_inode *) dnode_get(n);
1002                         if (ext2fs_file_acl_block(fs,
1003                                         EXT2_INODE(&di->inode)) == blk) {
1004                                 ext2fs_file_acl_block_set(fs,
1005                                         EXT2_INODE(&di->inode),
1006                                         ext2fs_file_acl_block(fs, EXT2_INODE(&dp->inode)));
1007                                 e2fsck_write_inode_full(ctx, ino_el->inode,
1008                                         EXT2_INODE(&di->inode),
1009                                         sizeof(di->inode), "clone file EA");
1010                                 decrement_badcount(ctx, blk, dc);
1011                         }
1012                 }
1013         }
1014         retval = 0;
1015 errout:
1016         ext2fs_free_mem(&cs.buf);
1017         return retval;
1018 }
1019
1020 /*
1021  * This routine returns 1 if a block overlaps with one of the superblocks,
1022  * group descriptors, inode bitmaps, or block bitmaps.
1023  */
1024 static int check_if_fs_block(e2fsck_t ctx, blk64_t test_block)
1025 {
1026         ext2_filsys fs = ctx->fs;
1027         blk64_t first_block;
1028         dgrp_t  i;
1029
1030         first_block = fs->super->s_first_data_block;
1031         for (i = 0; i < fs->group_desc_count; i++) {
1032
1033                 /* Check superblocks/block group descriptors */
1034                 if (ext2fs_bg_has_super(fs, i)) {
1035                         if (test_block >= first_block &&
1036                             (test_block <= first_block + fs->desc_blocks))
1037                                 return 1;
1038                 }
1039
1040                 /* Check the inode table */
1041                 if ((ext2fs_inode_table_loc(fs, i)) &&
1042                     (test_block >= ext2fs_inode_table_loc(fs, i)) &&
1043                     (test_block < (ext2fs_inode_table_loc(fs, i) +
1044                                    fs->inode_blocks_per_group)))
1045                         return 1;
1046
1047                 /* Check the bitmap blocks */
1048                 if ((test_block == ext2fs_block_bitmap_loc(fs, i)) ||
1049                     (test_block == ext2fs_inode_bitmap_loc(fs, i)))
1050                         return 1;
1051
1052                 first_block += fs->super->s_blocks_per_group;
1053         }
1054         return 0;
1055 }
1056
1057 /*
1058  * This routine returns 1 if a cluster overlaps with one of the superblocks,
1059  * group descriptors, inode bitmaps, or block bitmaps.
1060  */
1061 static int check_if_fs_cluster(e2fsck_t ctx, blk64_t cluster)
1062 {
1063         ext2_filsys fs = ctx->fs;
1064         blk64_t first_block;
1065         dgrp_t  i;
1066
1067         first_block = fs->super->s_first_data_block;
1068         for (i = 0; i < fs->group_desc_count; i++) {
1069
1070                 /* Check superblocks/block group descriptors */
1071                 if (ext2fs_bg_has_super(fs, i)) {
1072                         if (cluster >= EXT2FS_B2C(fs, first_block) &&
1073                             (cluster <= EXT2FS_B2C(fs, first_block +
1074                                                    fs->desc_blocks)))
1075                                 return 1;
1076                 }
1077
1078                 /* Check the inode table */
1079                 if ((ext2fs_inode_table_loc(fs, i)) &&
1080                     (cluster >= EXT2FS_B2C(fs,
1081                                            ext2fs_inode_table_loc(fs, i))) &&
1082                     (cluster <= EXT2FS_B2C(fs,
1083                                            ext2fs_inode_table_loc(fs, i) +
1084                                            fs->inode_blocks_per_group - 1)))
1085                         return 1;
1086
1087                 /* Check the bitmap blocks */
1088                 if ((cluster == EXT2FS_B2C(fs,
1089                                            ext2fs_block_bitmap_loc(fs, i))) ||
1090                     (cluster == EXT2FS_B2C(fs,
1091                                            ext2fs_inode_bitmap_loc(fs, i))))
1092                         return 1;
1093
1094                 first_block += fs->super->s_blocks_per_group;
1095         }
1096         return 0;
1097 }