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