pass1b.c revision 1b6bf1759af884957234b7dce768b785f792abd0
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 int blockcnt, void *private); 92static void delete_file(e2fsck_t ctx, struct dup_inode *dp, 93 char *block_buf); 94static int clone_file(e2fsck_t ctx, struct dup_inode *dp, char* block_buf); 95static void pass1b(e2fsck_t ctx, char *block_buf); 96static void pass1c(e2fsck_t ctx, char *block_buf); 97static void pass1d(e2fsck_t ctx, char *block_buf); 98 99static struct dup_block *dup_blk = 0; 100static struct dup_inode *dup_ino = 0; 101static int dup_inode_count = 0; 102 103static ext2fs_inode_bitmap inode_dup_map; 104 105/* 106 * Main procedure for handling duplicate blocks 107 */ 108void 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 */ 150struct process_block_struct { 151 ino_t ino; 152 int dup_blocks; 153 e2fsck_t ctx; 154 struct problem_context *pctx; 155}; 156 157void 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 227int 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 */ 287struct search_dir_struct { 288 int count; 289 ino_t first_inode; 290 ino_t max_inode; 291}; 292 293static 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 325void 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 359static 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 474static 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 509static 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 539struct clone_struct { 540 errcode_t errcode; 541 ino_t dir; 542 char *buf; 543 e2fsck_t ctx; 544}; 545 546static 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 610static 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} 643