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