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