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 <time.h>
  31 #ifdef HAVE_ERRNO_H
  32 #include <errno.h>
  33 #endif
  34
  35 #include <et/com_err.h>
  36 #include "e2fsck.h"
  37
  38 #include "problem.h"
  39
  40 /*
  41  * This is structure is allocated for each time that a block is
  42  * claimed by more than one file.  So if a particular block is claimed
  43  * by 3 files, then three copies of this structure will be allocated,
  44  * one for each conflict.
  45  *
  46  * The linked list structure is as follows:
  47  *
  48  * dup_blk -->  block #34  --> block #35  --> block #47
  49  *              inode #12      inode #14      inode #17
  50  *              num_bad = 3    num_bad = 2    num_bad = 2
  51  *                |              |               |
  52  *                V              V               V
  53  *              block #34      block #35      block #47
  54  *              inode #14      inode #15      inode #23
  55  *                |
  56  *                V
  57  *              block #34
  58  *              inode #15
  59  *
  60  * The num_bad field indicates how many inodes are sharing a
  61  * particular block, and is only stored in the first element of the
  62  * linked list for a particular block.  As the block conflicts are
  63  * resolved, num_bad is decremented; when it reaches 1, then we no
  64  * longer need to worry about that block.
  65  */
  66 struct dup_block {
  67         blk_t           block;          /* Block number */
  68         ino_t           ino;            /* Inode number */
  69         int             num_bad;
  70         /* Pointer to next dup record with different block */
  71         struct dup_block *next_block;
  72         /* Pointer to next dup record with different inode */
  73         struct dup_block *next_inode;
  74 };
  75
  76 /*
  77  * This structure stores information about a particular inode which
  78  * is sharing blocks with other inodes.  This information is collected
  79  * to display to the user, so that the user knows what files he or she
  80  * is dealing with, when trying to decide how to resolve the conflict
  81  * of multiply-claimed blocks.
  82  */
  83 struct dup_inode {
  84         ino_t                   ino, dir;
  85         int                     num_dupblocks;
  86         struct ext2_inode       inode;
  87         struct dup_inode        *next;
  88 };
  89
  90 static int process_pass1b_block(ext2_filsys fs, blk_t   *blocknr,
  91                                 int     blockcnt, void  *private);
  92 static void delete_file(e2fsck_t ctx, struct dup_inode *dp,
  93                         char *block_buf);
  94 static int clone_file(e2fsck_t ctx, struct dup_inode *dp, char* block_buf);
  95 static void pass1b(e2fsck_t ctx, char *block_buf);
  96 static void pass1c(e2fsck_t ctx, char *block_buf);
  97 static void pass1d(e2fsck_t ctx, char *block_buf);
  98
  99 static struct dup_block *dup_blk = 0;
 100 static struct dup_inode *dup_ino = 0;
 101 static int dup_inode_count = 0;
 102
 103 static ext2fs_inode_bitmap inode_dup_map;
 104
 105 /*
 106  * Main procedure for handling duplicate blocks
 107  */
 108 void e2fsck_pass1_dupblocks(e2fsck_t ctx, char *block_buf)
 109 {
 110         ext2_filsys             fs = ctx->fs;
 111         struct dup_block        *p, *q, *next_p, *next_q;
 112         struct dup_inode        *r, *next_r;
 113         struct problem_context  pctx;
 114
 115         clear_problem_context(&pctx);
 116
 117         pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
 118                       "multiply claimed inode map", &inode_dup_map);
 119         if (pctx.errcode) {
 120                 fix_problem(ctx, PR_1B_ALLOCATE_IBITMAP_ERROR, &pctx);
 121                 ctx->flags |= E2F_FLAG_ABORT;
 122                 return;
 123         }
 124
 125         pass1b(ctx, block_buf);
 126         pass1c(ctx, block_buf);
 127         pass1d(ctx, block_buf);
 128
 129         /*
 130          * Time to free all of the accumulated data structures that we
 131          * don't need anymore.
 132          */
 133         ext2fs_free_inode_bitmap(inode_dup_map); inode_dup_map = 0;
 134         ext2fs_free_block_bitmap(ctx->block_dup_map); ctx->block_dup_map = 0;
 135         for (p = dup_blk; p; p = next_p) {
 136                 next_p = p->next_block;
 137                 for (q = p; q; q = next_q) {
 138                         next_q = q->next_inode;
 139                         ext2fs_free_mem((void **) &q);
 140                 }
 141         }
 142         for (r = dup_ino; r; r = next_r) {
 143                 next_r = r->next;
 144                 ext2fs_free_mem((void **) &r);
 145         }
 146 }
 147
 148 /*
 149  * Scan the inodes looking for inodes that contain duplicate blocks.
 150  */
 151 struct process_block_struct {
 152         ino_t   ino;
 153         int     dup_blocks;
 154         e2fsck_t ctx;
 155         struct problem_context *pctx;
 156 };
 157
 158 static void pass1b(e2fsck_t ctx, char *block_buf)
 159 {
 160         ext2_filsys fs = ctx->fs;
 161         ino_t   ino;
 162         struct ext2_inode inode;
 163         ext2_inode_scan scan;
 164         errcode_t       retval;
 165         struct process_block_struct pb;
 166         struct dup_inode *dp;
 167         struct problem_context pctx;
 168
 169         clear_problem_context(&pctx);
 170
 171         fix_problem(ctx, PR_1B_PASS_HEADER, &pctx);
 172         pctx.errcode = ext2fs_open_inode_scan(fs, ctx->inode_buffer_blocks,
 173                                               &scan);
 174         if (pctx.errcode) {
 175                 fix_problem(ctx, PR_1B_ISCAN_ERROR, &pctx);
 176                 ctx->flags |= E2F_FLAG_ABORT;
 177                 return;
 178         }
 179         pctx.errcode = ext2fs_get_next_inode(scan, &ino, &inode);
 180         if (pctx.errcode) {
 181                 fix_problem(ctx, PR_1B_ISCAN_ERROR, &pctx);
 182                 ctx->flags |= E2F_FLAG_ABORT;
 183                 return;
 184         }
 185         ctx->stashed_inode = &inode;
 186         pb.ctx = ctx;
 187         pb.pctx = &pctx;
 188         while (ino) {
 189                 pctx.ino = ctx->stashed_ino = ino;
 190                 if ((ino != EXT2_BAD_INO) &&
 191                     (!ext2fs_test_inode_bitmap(ctx->inode_used_map, ino) ||
 192                      !ext2fs_inode_has_valid_blocks(&inode)))
 193                         goto next;
 194
 195                 pb.ino = ino;
 196                 pb.dup_blocks = 0;
 197                 retval = ext2fs_block_iterate(fs, ino, 0, block_buf,
 198                                               process_pass1b_block, &pb);
 199                 if (pb.dup_blocks) {
 200                         end_problem_latch(ctx, PR_LATCH_DBLOCK);
 201                         dp = e2fsck_allocate_memory(ctx,
 202                                     sizeof(struct dup_inode),
 203                                     "duplicate inode record");
 204                         dp->ino = ino;
 205                         dp->dir = 0;
 206                         dp->inode = inode;
 207                         dp->num_dupblocks = pb.dup_blocks;
 208                         dp->next = dup_ino;
 209                         dup_ino = dp;
 210                         if (ino != EXT2_BAD_INO)
 211                                 dup_inode_count++;
 212                 }
 213                 if (retval)
 214                         com_err(ctx->program_name, retval,
 215                                 "while calling ext2fs_block_iterate in pass1b");
 216
 217         next:
 218                 pctx.errcode = ext2fs_get_next_inode(scan, &ino, &inode);
 219                 if (pctx.errcode == EXT2_ET_BAD_BLOCK_IN_INODE_TABLE)
 220                         goto next;
 221                 if (pctx.errcode) {
 222                         fix_problem(ctx, PR_1B_ISCAN_ERROR, &pctx);
 223                         ctx->flags |= E2F_FLAG_ABORT;
 224                         return;
 225                 }
 226         }
 227         ext2fs_close_inode_scan(scan);
 228         fs->get_blocks = 0;
 229         fs->check_directory = 0;
 230 }
 231
 232 int process_pass1b_block(ext2_filsys fs,
 233                          blk_t  *block_nr,
 234                          int blockcnt,
 235                          void *private)
 236 {
 237         struct process_block_struct *p;
 238         struct dup_block *dp, *q, *r;
 239         int i;
 240         e2fsck_t ctx;
 241
 242         if (!*block_nr)
 243                 return 0;
 244         p = (struct process_block_struct *) private;
 245         ctx = p->ctx;
 246
 247         if (ext2fs_test_block_bitmap(ctx->block_dup_map, *block_nr)) {
 248                 /* OK, this is a duplicate block */
 249                 if (p->ino != EXT2_BAD_INO) {
 250                         p->pctx->blk = *block_nr;
 251                         fix_problem(ctx, PR_1B_DUP_BLOCK, p->pctx);
 252                 }
 253                 p->dup_blocks++;
 254                 ext2fs_mark_block_bitmap(ctx->block_dup_map, *block_nr);
 255                 ext2fs_mark_inode_bitmap(inode_dup_map, p->ino);
 256                 dp = e2fsck_allocate_memory(ctx, sizeof(struct dup_block),
 257                                             "duplicate block record");
 258                 dp->block = *block_nr;
 259                 dp->ino = p->ino;
 260                 dp->num_bad = 0;
 261                 q = dup_blk;
 262                 while (q) {
 263                         if (q->block == *block_nr)
 264                                 break;
 265                         q = q->next_block;
 266                 }
 267                 if (q) {
 268                         dp->next_inode = q->next_inode;
 269                         q->next_inode = dp;
 270                 } else {
 271                         dp->next_block = dup_blk;
 272                         dup_blk = dp;
 273                 }
 274         }
 275         /*
 276          * Set the num_bad field
 277          */
 278         for (q = dup_blk; q; q = q->next_block) {
 279                 i = 0;
 280                 for (r = q; r; r = r->next_inode)
 281                         i++;
 282                 q->num_bad = i;
 283         }
 284         return 0;
 285 }
 286
 287 /*
 288  * Pass 1c: Scan directories for inodes with duplicate blocks.  This
 289  * is used so that we can print pathnames when prompting the user for
 290  * what to do.
 291  */
 292 struct search_dir_struct {
 293         int             count;
 294         ino_t           first_inode;
 295         ino_t           max_inode;
 296 };
 297
 298 static int search_dirent_proc(ino_t dir, int entry,
 299                               struct ext2_dir_entry *dirent,
 300                               int offset, int blocksize,
 301                               char *buf, void *private)
 302 {
 303         struct search_dir_struct *sd = private;
 304         struct dup_inode        *p;
 305
 306         if (dirent->inode > sd->max_inode)
 307                 /* Should abort this inode, but not everything */
 308                 return 0;
 309
 310         if (!dirent->inode || (entry < DIRENT_OTHER_FILE) ||
 311             !ext2fs_test_inode_bitmap(inode_dup_map, dirent->inode))
 312                 return 0;
 313
 314         for (p = dup_ino; p; p = p->next) {
 315                 if ((p->ino >= sd->first_inode) &&
 316                     (p->ino == dirent->inode))
 317                         break;
 318         }
 319
 320         if (!p || p->dir)
 321                 return 0;
 322
 323         p->dir = dir;
 324         sd->count--;
 325
 326         return(sd->count ? 0 : DIRENT_ABORT);
 327 }
 328
 329
 330 static void pass1c(e2fsck_t ctx, char *block_buf)
 331 {
 332         ext2_filsys fs = ctx->fs;
 333         struct dup_inode        *p;
 334         int     inodes_left = dup_inode_count;
 335         struct search_dir_struct sd;
 336         struct problem_context pctx;
 337
 338         clear_problem_context(&pctx);
 339
 340         fix_problem(ctx, PR_1C_PASS_HEADER, &pctx);
 341
 342         /*
 343          * First check to see if any of the inodes with dup blocks is
 344          * a special inode.  (Note that the bad block inode isn't
 345          * counted.)
 346          */
 347         for (p = dup_ino; p; p = p->next) {
 348                 if ((p->ino < EXT2_FIRST_INODE(fs->super)) &&
 349                     (p->ino != EXT2_BAD_INO))
 350                         inodes_left--;
 351         }
 352
 353         /*
 354          * Search through all directories to translate inodes to names
 355          * (by searching for the containing directory for that inode.)
 356          */
 357         sd.count = inodes_left;
 358         sd.first_inode = EXT2_FIRST_INODE(fs->super);
 359         sd.max_inode = fs->super->s_inodes_count;
 360         ext2fs_dblist_dir_iterate(fs->dblist, 0, block_buf,
 361                                   search_dirent_proc, &sd);
 362 }
 363
 364 static void pass1d(e2fsck_t ctx, char *block_buf)
 365 {
 366         ext2_filsys fs = ctx->fs;
 367         struct dup_inode        *p, *s;
 368         struct dup_block        *q, *r;
 369         ino_t   *shared;
 370         int     shared_len;
 371         int     i;
 372         int     file_ok;
 373         int     meta_data = 0;
 374         struct problem_context pctx;
 375
 376         clear_problem_context(&pctx);
 377
 378         fix_problem(ctx, PR_1D_PASS_HEADER, &pctx);
 379         e2fsck_read_bitmaps(ctx);
 380
 381         pctx.num = dup_inode_count;
 382         fix_problem(ctx, PR_1D_NUM_DUP_INODES, &pctx);
 383         shared = e2fsck_allocate_memory(ctx, sizeof(ino_t) * dup_inode_count,
 384                                         "Shared inode list");
 385         for (p = dup_ino; p; p = p->next) {
 386                 shared_len = 0;
 387                 file_ok = 1;
 388                 if (p->ino == EXT2_BAD_INO)
 389                         continue;
 390
 391                 /*
 392                  * Search through the duplicate records to see which
 393                  * inodes share blocks with this one
 394                  */
 395                 for (q = dup_blk; q; q = q->next_block) {
 396                         /*
 397                          * See if this block is used by this inode.
 398                          * If it isn't, continue.
 399                          */
 400                         for (r = q; r; r = r->next_inode)
 401                                 if (r->ino == p->ino)
 402                                         break;
 403                         if (!r)
 404                                 continue;
 405                         if (q->num_bad > 1)
 406                                 file_ok = 0;
 407                         if (ext2fs_test_block_bitmap(ctx->block_illegal_map,
 408                                                      q->block)) {
 409                                 file_ok = 0;
 410                                 meta_data = 1;
 411                         }
 412
 413                         /*
 414                          * Add all inodes used by this block to the
 415                          * shared[] --- which is a unique list, so
 416                          * if an inode is already in shared[], don't
 417                          * add it again.
 418                          */
 419                         for (r = q; r; r = r->next_inode) {
 420                                 if (r->ino == p->ino)
 421                                         continue;
 422                                 for (i = 0; i < shared_len; i++)
 423                                         if (shared[i] == r->ino)
 424                                                 break;
 425                                 if (i == shared_len) {
 426                                         shared[shared_len++] = r->ino;
 427                                 }
 428                         }
 429                 }
 430
 431                 /*
 432                  * Report the inode that we are working on
 433                  */
 434                 pctx.inode = &p->inode;
 435                 pctx.ino = p->ino;
 436                 pctx.dir = p->dir;
 437                 pctx.blkcount = p->num_dupblocks;
 438                 pctx.num = meta_data ? shared_len+1 : shared_len;
 439                 fix_problem(ctx, PR_1D_DUP_FILE, &pctx);
 440                 pctx.blkcount = 0;
 441                 pctx.num = 0;
 442
 443                 if (meta_data)
 444                         fix_problem(ctx, PR_1D_SHARE_METADATA, &pctx);
 445
 446                 for (i = 0; i < shared_len; i++) {
 447                         for (s = dup_ino; s; s = s->next)
 448                                 if (s->ino == shared[i])
 449                                         break;
 450                         if (!s)
 451                                 continue;
 452                         /*
 453                          * Report the inode that we are sharing with
 454                          */
 455                         pctx.inode = &s->inode;
 456                         pctx.ino = s->ino;
 457                         pctx.dir = s->dir;
 458                         fix_problem(ctx, PR_1D_DUP_FILE_LIST, &pctx);
 459                 }
 460                 if (file_ok) {
 461                         fix_problem(ctx, PR_1D_DUP_BLOCKS_DEALT, &pctx);
 462                         continue;
 463                 }
 464                 if (fix_problem(ctx, PR_1D_CLONE_QUESTION, &pctx)) {
 465                         pctx.errcode = clone_file(ctx, p, block_buf);
 466                         if (pctx.errcode)
 467                                 fix_problem(ctx, PR_1D_CLONE_ERROR, &pctx);
 468                         else
 469                                 continue;
 470                 }
 471                 if (fix_problem(ctx, PR_1D_DELETE_QUESTION, &pctx))
 472                         delete_file(ctx, p, block_buf);
 473                 else
 474                         ext2fs_unmark_valid(fs);
 475         }
 476         ext2fs_free_mem((void **) &shared);
 477 }
 478
 479 static int delete_file_block(ext2_filsys fs,
 480                              blk_t      *block_nr,
 481                              int blockcnt,
 482                              void *private)
 483 {
 484         struct process_block_struct *pb = private;
 485         struct dup_block *p;
 486         e2fsck_t ctx;
 487
 488         ctx = pb->ctx;
 489
 490         if (!*block_nr)
 491                 return 0;
 492
 493         if (ext2fs_test_block_bitmap(ctx->block_dup_map, *block_nr)) {
 494                 for (p = dup_blk; p; p = p->next_block)
 495                         if (p->block == *block_nr)
 496                                 break;
 497                 if (p) {
 498                         p->num_bad--;
 499                         if (p->num_bad == 1)
 500                                 ext2fs_unmark_block_bitmap(ctx->block_dup_map,
 501                                                            *block_nr);
 502                 } else
 503                         com_err("delete_file_block", 0,
 504                                 "internal error; can't find dup_blk for %d\n",
 505                                 *block_nr);
 506         } else {
 507                 ext2fs_unmark_block_bitmap(ctx->block_found_map, *block_nr);
 508                 ext2fs_unmark_block_bitmap(fs->block_map, *block_nr);
 509         }
 510
 511         return 0;
 512 }
 513
 514 static void delete_file(e2fsck_t ctx, struct dup_inode *dp, char* block_buf)
 515 {
 516         ext2_filsys fs = ctx->fs;
 517         errcode_t       retval;
 518         struct process_block_struct pb;
 519         struct ext2_inode       inode;
 520
 521         pb.ino = dp->ino;
 522         pb.dup_blocks = dp->num_dupblocks;
 523         pb.ctx = ctx;
 524
 525         retval = ext2fs_block_iterate(fs, dp->ino, 0, block_buf,
 526                                       delete_file_block, &pb);
 527         if (retval)
 528                 com_err("delete_file", retval,
 529                         "while calling ext2fs_block_iterate for inode %d",
 530                         dp->ino);
 531         ext2fs_unmark_inode_bitmap(ctx->inode_used_map, dp->ino);
 532         ext2fs_unmark_inode_bitmap(ctx->inode_dir_map, dp->ino);
 533         if (ctx->inode_bad_map)
 534                 ext2fs_unmark_inode_bitmap(ctx->inode_bad_map, dp->ino);
 535         ext2fs_unmark_inode_bitmap(fs->inode_map, dp->ino);
 536         ext2fs_mark_ib_dirty(fs);
 537         ext2fs_mark_bb_dirty(fs);
 538         e2fsck_read_inode(ctx, dp->ino, &inode, "delete_file");
 539         inode.i_links_count = 0;
 540         inode.i_dtime = time(0);
 541         e2fsck_write_inode(ctx, dp->ino, &inode, "delete_file");
 542 }
 543
 544 struct clone_struct {
 545         errcode_t       errcode;
 546         ino_t           dir;
 547         char    *buf;
 548         e2fsck_t ctx;
 549 };
 550
 551 static int clone_file_block(ext2_filsys fs,
 552                             blk_t       *block_nr,
 553                             int blockcnt,
 554                             void *private)
 555 {
 556         struct dup_block *p;
 557         blk_t   new_block;
 558         errcode_t       retval;
 559         struct clone_struct *cs = (struct clone_struct *) private;
 560         e2fsck_t ctx;
 561
 562         ctx = cs->ctx;
 563
 564         if (!*block_nr)
 565                 return 0;
 566
 567         if (ext2fs_test_block_bitmap(ctx->block_dup_map, *block_nr)) {
 568                 for (p = dup_blk; p; p = p->next_block)
 569                         if (p->block == *block_nr)
 570                                 break;
 571                 if (p) {
 572                         retval = ext2fs_new_block(fs, 0, ctx->block_found_map,
 573                                                   &new_block);
 574                         if (retval) {
 575                                 cs->errcode = retval;
 576                                 return BLOCK_ABORT;
 577                         }
 578                         if (cs->dir) {
 579                                 retval = ext2fs_set_dir_block(fs->dblist,
 580                                       cs->dir, new_block, blockcnt);
 581                                 if (retval) {
 582                                         cs->errcode = retval;
 583                                         return BLOCK_ABORT;
 584                                 }
 585                         }
 586                         retval = io_channel_read_blk(fs->io, *block_nr, 1,
 587                                                      cs->buf);
 588                         if (retval) {
 589                                 cs->errcode = retval;
 590                                 return BLOCK_ABORT;
 591                         }
 592                         retval = io_channel_write_blk(fs->io, new_block, 1,
 593                                                       cs->buf);
 594                         if (retval) {
 595                                 cs->errcode = retval;
 596                                 return BLOCK_ABORT;
 597                         }
 598                         p->num_bad--;
 599                         if (p->num_bad == 1)
 600                                 ext2fs_unmark_block_bitmap(ctx->block_dup_map,
 601                                                            *block_nr);
 602                         *block_nr = new_block;
 603                         ext2fs_mark_block_bitmap(ctx->block_found_map,
 604                                                  new_block);
 605                         ext2fs_mark_block_bitmap(fs->block_map, new_block);
 606                         return BLOCK_CHANGED;
 607                 } else
 608                         com_err("clone_file_block", 0,
 609                                 "internal error; can't find dup_blk for %d\n",
 610                                 *block_nr);
 611         }
 612         return 0;
 613 }
 614
 615 static int clone_file(e2fsck_t ctx, struct dup_inode *dp, char* block_buf)
 616 {
 617         ext2_filsys fs = ctx->fs;
 618         errcode_t       retval;
 619         struct clone_struct cs;
 620
 621         cs.errcode = 0;
 622         cs.dir = 0;
 623         cs.ctx = ctx;
 624         retval = ext2fs_get_mem(fs->blocksize, (void **) &cs.buf);
 625         if (retval)
 626                 return retval;
 627
 628         if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, dp->ino))
 629                 cs.dir = dp->ino;
 630
 631         retval = ext2fs_block_iterate(fs, dp->ino, 0, block_buf,
 632                                       clone_file_block, &cs);
 633         ext2fs_mark_bb_dirty(fs);
 634         ext2fs_free_mem((void **) &cs.buf);
 635         if (retval) {
 636                 com_err("clone_file", retval,
 637                         "while calling ext2fs_block_iterate for inode %d",
 638                         dp->ino);
 639                 return retval;
 640         }
 641         if (cs.errcode) {
 642                 com_err("clone_file", cs.errcode,
 643                         "returned from clone_file_block");
 644                 return retval;
 645         }
 646         return 0;
 647 }