pass3.c revision 1b6bf1759af884957234b7dce768b785f792abd0
1/* 2 * pass3.c -- pass #3 of e2fsck: Check for directory connectivity 3 * 4 * Copyright (C) 1993, 1994, 1995, 1996, 1997 Theodore Ts'o. 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Public 8 * License. 9 * %End-Header% 10 * 11 * Pass #3 assures that all directories are connected to the 12 * filesystem tree, using the following algorithm: 13 * 14 * First, the root directory is checked to make sure it exists; if 15 * not, e2fsck will offer to create a new one. It is then marked as 16 * "done". 17 * 18 * Then, pass3 interates over all directory inodes; for each directory 19 * it attempts to trace up the filesystem tree, using dirinfo.parent 20 * until it reaches a directory which has been marked "done". If it 21 * can not do so, then the directory must be disconnected, and e2fsck 22 * will offer to reconnect it to /lost+found. While it is chasing 23 * parent pointers up the filesystem tree, if pass3 sees a directory 24 * twice, then it has detected a filesystem loop, and it will again 25 * offer to reconnect the directory to /lost+found in to break the 26 * filesystem loop. 27 * 28 * Pass 3 also contains the subroutine, reconnect_file() to reconnect 29 * inodes to /lost+found; this subroutine is also used by pass 4. 30 * reconnect_file() calls get_lost_and_found(), which is responsible 31 * for creating /lost+found if it does not exist. 32 * 33 * Pass 3 frees the following data structures: 34 * - The dirinfo directory information cache. 35 */ 36 37#ifdef HAVE_ERRNO_H 38#include <errno.h> 39#endif 40 41#include "e2fsck.h" 42#include "problem.h" 43 44static void check_root(e2fsck_t ctx); 45static void check_directory(e2fsck_t ctx, struct dir_info *dir, 46 struct problem_context *pctx); 47static ino_t get_lost_and_found(e2fsck_t ctx); 48static void fix_dotdot(e2fsck_t ctx, struct dir_info *dir, ino_t parent); 49static errcode_t adjust_inode_count(e2fsck_t ctx, ino_t ino, int adj); 50static errcode_t expand_directory(e2fsck_t ctx, ino_t dir); 51 52static ino_t lost_and_found = 0; 53static int bad_lost_and_found = 0; 54 55static ext2fs_inode_bitmap inode_loop_detect; 56static ext2fs_inode_bitmap inode_done_map; 57 58void pass3(e2fsck_t ctx) 59{ 60 ext2_filsys fs = ctx->fs; 61 int i; 62 struct resource_track rtrack; 63 struct problem_context pctx; 64 struct dir_info *dir; 65 66 init_resource_track(&rtrack); 67 68 clear_problem_context(&pctx); 69 70#ifdef MTRACE 71 mtrace_print("Pass 3"); 72#endif 73 74 if (!(ctx->options & E2F_OPT_PREEN)) 75 fix_problem(ctx, PR_3_PASS_HEADER, &pctx); 76 77 /* 78 * Allocate some bitmaps to do loop detection. 79 */ 80 pctx.errcode = ext2fs_allocate_inode_bitmap(fs, 81 "inode loop detection bitmap", &inode_loop_detect); 82 if (pctx.errcode) { 83 pctx.num = 1; 84 fix_problem(ctx, PR_3_ALLOCATE_IBITMAP_ERROR, &pctx); 85 fatal_error(0); 86 } 87 pctx.errcode = ext2fs_allocate_inode_bitmap(fs, "inode done bitmap", 88 &inode_done_map); 89 if (pctx.errcode) { 90 pctx.num = 2; 91 fix_problem(ctx, PR_3_ALLOCATE_IBITMAP_ERROR, &pctx); 92 fatal_error(0); 93 } 94 if (ctx->options & E2F_OPT_TIME) 95 print_resource_track("Peak memory", &ctx->global_rtrack); 96 97 check_root(ctx); 98 ext2fs_mark_inode_bitmap(inode_done_map, EXT2_ROOT_INO); 99 100 for (i=0; (dir = dir_info_iter(&i)) != 0;) { 101 if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, dir->ino)) 102 check_directory(ctx, dir, &pctx); 103 } 104 105 106 free_dir_info(fs); 107 ext2fs_free_inode_bitmap(inode_loop_detect); 108 ext2fs_free_inode_bitmap(inode_done_map); 109 if (ctx->options & E2F_OPT_TIME2) 110 print_resource_track("Pass 3", &rtrack); 111} 112 113/* 114 * This makes sure the root inode is present; if not, we ask if the 115 * user wants us to create it. Not creating it is a fatal error. 116 */ 117static void check_root(e2fsck_t ctx) 118{ 119 ext2_filsys fs = ctx->fs; 120 blk_t blk; 121 struct ext2_inode inode; 122 char * block; 123 struct problem_context pctx; 124 125 clear_problem_context(&pctx); 126 127 if (ext2fs_test_inode_bitmap(ctx->inode_used_map, EXT2_ROOT_INO)) { 128 /* 129 * If the root inode is a directory, die here. The 130 * user must have answered 'no' in pass1 when we 131 * offered to clear it. 132 */ 133 if (!(ext2fs_test_inode_bitmap(ctx->inode_dir_map, 134 EXT2_ROOT_INO))) 135 fatal_error("Root inode not directory"); 136 return; 137 } 138 139 if (!fix_problem(ctx, PR_3_NO_ROOT_INODE, &pctx)) 140 fatal_error("Cannot proceed without a root inode."); 141 142 read_bitmaps(ctx); 143 144 /* 145 * First, find a free block 146 */ 147 pctx.errcode = ext2fs_new_block(fs, 0, ctx->block_found_map, &blk); 148 if (pctx.errcode) { 149 pctx.str = "ext2fs_new_block"; 150 fix_problem(ctx, PR_3_CREATE_ROOT_ERROR, &pctx); 151 fatal_error(0); 152 } 153 ext2fs_mark_block_bitmap(ctx->block_found_map, blk); 154 ext2fs_mark_block_bitmap(fs->block_map, blk); 155 ext2fs_mark_bb_dirty(fs); 156 157 /* 158 * Now let's create the actual data block for the inode 159 */ 160 pctx.errcode = ext2fs_new_dir_block(fs, EXT2_ROOT_INO, EXT2_ROOT_INO, 161 &block); 162 if (pctx.errcode) { 163 pctx.str = "ext2fs_new_dir_block"; 164 fix_problem(ctx, PR_3_CREATE_ROOT_ERROR, &pctx); 165 fatal_error(0); 166 } 167 168 pctx.errcode = ext2fs_write_dir_block(fs, blk, block); 169 if (pctx.errcode) { 170 pctx.str = "ext2fs_write_dir_block"; 171 fix_problem(ctx, PR_3_CREATE_ROOT_ERROR, &pctx); 172 fatal_error(0); 173 } 174 free(block); 175 176 /* 177 * Set up the inode structure 178 */ 179 memset(&inode, 0, sizeof(inode)); 180 inode.i_mode = 040755; 181 inode.i_size = fs->blocksize; 182 inode.i_atime = inode.i_ctime = inode.i_mtime = time(0); 183 inode.i_links_count = 2; 184 inode.i_blocks = fs->blocksize / 512; 185 inode.i_block[0] = blk; 186 187 /* 188 * Write out the inode. 189 */ 190 pctx.errcode = ext2fs_write_inode(fs, EXT2_ROOT_INO, &inode); 191 if (pctx.errcode) { 192 pctx.str = "ext2fs_write_inode"; 193 fix_problem(ctx, PR_3_CREATE_ROOT_ERROR, &pctx); 194 fatal_error(0); 195 } 196 197 /* 198 * Miscellaneous bookkeeping... 199 */ 200 add_dir_info(fs, EXT2_ROOT_INO, EXT2_ROOT_INO); 201 ext2fs_icount_store(ctx->inode_count, EXT2_ROOT_INO, 2); 202 ext2fs_icount_store(ctx->inode_link_info, EXT2_ROOT_INO, 2); 203 204 ext2fs_mark_inode_bitmap(ctx->inode_used_map, EXT2_ROOT_INO); 205 ext2fs_mark_inode_bitmap(ctx->inode_dir_map, EXT2_ROOT_INO); 206 ext2fs_mark_inode_bitmap(fs->inode_map, EXT2_ROOT_INO); 207 ext2fs_mark_ib_dirty(fs); 208} 209 210/* 211 * This subroutine is responsible for making sure that a particular 212 * directory is connected to the root; if it isn't we trace it up as 213 * far as we can go, and then offer to connect the resulting parent to 214 * the lost+found. We have to do loop detection; if we ever discover 215 * a loop, we treat that as a disconnected directory and offer to 216 * reparent it to lost+found. 217 */ 218static void check_directory(e2fsck_t ctx, struct dir_info *dir, 219 struct problem_context *pctx) 220{ 221 ext2_filsys fs = ctx->fs; 222 struct dir_info *p = dir; 223 224 ext2fs_clear_inode_bitmap(inode_loop_detect); 225 while (p) { 226 /* 227 * If we find a parent which we've already checked, 228 * then stop; we know it's either already connected to 229 * the directory tree, or it isn't but the user has 230 * already told us he doesn't want us to reconnect the 231 * disconnected subtree. 232 */ 233 if (ext2fs_test_inode_bitmap(inode_done_map, p->ino)) 234 goto check_dot_dot; 235 /* 236 * Mark this inode as being "done"; by the time we 237 * return from this function, the inode we either be 238 * verified as being connected to the directory tree, 239 * or we will have offered to reconnect this to 240 * lost+found. 241 */ 242 ext2fs_mark_inode_bitmap(inode_done_map, p->ino); 243 /* 244 * If this directory doesn't have a parent, or we've 245 * seen the parent once already, then offer to 246 * reparent it to lost+found 247 */ 248 if (!p->parent || 249 (ext2fs_test_inode_bitmap(inode_loop_detect, 250 p->parent))) 251 break; 252 ext2fs_mark_inode_bitmap(inode_loop_detect, 253 p->parent); 254 p = get_dir_info(p->parent); 255 } 256 /* 257 * If we've reached here, we've hit a detached directory 258 * inode; offer to reconnect it to lost+found. 259 */ 260 pctx->ino = p->ino; 261 if (fix_problem(ctx, PR_3_UNCONNECTED_DIR, pctx)) { 262 if (reconnect_file(ctx, p->ino)) 263 ext2fs_unmark_valid(fs); 264 else { 265 p->parent = lost_and_found; 266 fix_dotdot(ctx, p, lost_and_found); 267 } 268 } 269 270 /* 271 * Make sure that .. and the parent directory are the same; 272 * offer to fix it if not. 273 */ 274check_dot_dot: 275 if (dir->parent != dir->dotdot) { 276 pctx->ino = dir->ino; 277 pctx->ino2 = dir->dotdot; 278 pctx->dir = dir->parent; 279 if (fix_problem(ctx, PR_3_BAD_DOT_DOT, pctx)) 280 fix_dotdot(ctx, dir, dir->parent); 281 } 282} 283 284/* 285 * This routine gets the lost_and_found inode, making it a directory 286 * if necessary 287 */ 288ino_t get_lost_and_found(e2fsck_t ctx) 289{ 290 ext2_filsys fs = ctx->fs; 291 ino_t ino; 292 blk_t blk; 293 errcode_t retval; 294 struct ext2_inode inode; 295 char * block; 296 const char name[] = "lost+found"; 297 struct problem_context pctx; 298 299 clear_problem_context(&pctx); 300 301 retval = ext2fs_lookup(fs, EXT2_ROOT_INO, name, 302 sizeof(name)-1, 0, &ino); 303 if (!retval) 304 return ino; 305 if (retval != ENOENT) { 306 pctx.errcode = retval; 307 fix_problem(ctx, PR_3_ERR_FIND_LPF, &pctx); 308 } 309 if (!fix_problem(ctx, PR_3_NO_LF_DIR, 0)) 310 return 0; 311 312 /* 313 * Read the inode and block bitmaps in; we'll be messing with 314 * them. 315 */ 316 read_bitmaps(ctx); 317 318 /* 319 * First, find a free block 320 */ 321 retval = ext2fs_new_block(fs, 0, ctx->block_found_map, &blk); 322 if (retval) { 323 pctx.errcode = retval; 324 fix_problem(ctx, PR_3_ERR_LPF_NEW_BLOCK, &pctx); 325 return 0; 326 } 327 ext2fs_mark_block_bitmap(ctx->block_found_map, blk); 328 ext2fs_mark_block_bitmap(fs->block_map, blk); 329 ext2fs_mark_bb_dirty(fs); 330 331 /* 332 * Next find a free inode. 333 */ 334 retval = ext2fs_new_inode(fs, EXT2_ROOT_INO, 040755, 335 ctx->inode_used_map, &ino); 336 if (retval) { 337 pctx.errcode = retval; 338 fix_problem(ctx, PR_3_ERR_LPF_NEW_INODE, &pctx); 339 return 0; 340 } 341 ext2fs_mark_inode_bitmap(ctx->inode_used_map, ino); 342 ext2fs_mark_inode_bitmap(ctx->inode_dir_map, ino); 343 ext2fs_mark_inode_bitmap(fs->inode_map, ino); 344 ext2fs_mark_ib_dirty(fs); 345 346 /* 347 * Now let's create the actual data block for the inode 348 */ 349 retval = ext2fs_new_dir_block(fs, ino, EXT2_ROOT_INO, &block); 350 if (retval) { 351 pctx.errcode = retval; 352 fix_problem(ctx, PR_3_ERR_LPF_NEW_DIR_BLOCK, &pctx); 353 return 0; 354 } 355 356 retval = ext2fs_write_dir_block(fs, blk, block); 357 free(block); 358 if (retval) { 359 pctx.errcode = retval; 360 fix_problem(ctx, PR_3_ERR_LPF_WRITE_BLOCK, &pctx); 361 return 0; 362 } 363 364 /* 365 * Set up the inode structure 366 */ 367 memset(&inode, 0, sizeof(inode)); 368 inode.i_mode = 040755; 369 inode.i_size = fs->blocksize; 370 inode.i_atime = inode.i_ctime = inode.i_mtime = time(0); 371 inode.i_links_count = 2; 372 inode.i_blocks = fs->blocksize / 512; 373 inode.i_block[0] = blk; 374 375 /* 376 * Next, write out the inode. 377 */ 378 pctx.errcode = ext2fs_write_inode(fs, ino, &inode); 379 if (pctx.errcode) { 380 pctx.str = "ext2fs_write_inode"; 381 fix_problem(ctx, PR_3_CREATE_LPF_ERROR, &pctx); 382 return 0; 383 } 384 /* 385 * Finally, create the directory link 386 */ 387 pctx.errcode = ext2fs_link(fs, EXT2_ROOT_INO, name, ino, 0); 388 if (pctx.errcode) { 389 pctx.str = "ext2fs_link"; 390 fix_problem(ctx, PR_3_CREATE_LPF_ERROR, &pctx); 391 return 0; 392 } 393 394 /* 395 * Miscellaneous bookkeeping that needs to be kept straight. 396 */ 397 add_dir_info(fs, ino, EXT2_ROOT_INO); 398 adjust_inode_count(ctx, EXT2_ROOT_INO, +1); 399 ext2fs_icount_store(ctx->inode_count, ino, 2); 400 ext2fs_icount_store(ctx->inode_link_info, ino, 2); 401#if 0 402 printf("/lost+found created; inode #%lu\n", ino); 403#endif 404 return ino; 405} 406 407/* 408 * This routine will connect a file to lost+found 409 */ 410int reconnect_file(e2fsck_t ctx, ino_t inode) 411{ 412 ext2_filsys fs = ctx->fs; 413 errcode_t retval; 414 char name[80]; 415 struct problem_context pctx; 416 417 clear_problem_context(&pctx); 418 pctx.ino = inode; 419 420 if (!bad_lost_and_found && !lost_and_found) { 421 lost_and_found = get_lost_and_found(ctx); 422 if (!lost_and_found) 423 bad_lost_and_found++; 424 } 425 if (bad_lost_and_found) { 426 fix_problem(ctx, PR_3_NO_LPF, &pctx); 427 return 1; 428 } 429 430 sprintf(name, "#%lu", inode); 431 retval = ext2fs_link(fs, lost_and_found, name, inode, 0); 432 if (retval == EXT2_ET_DIR_NO_SPACE) { 433 if (!fix_problem(ctx, PR_3_EXPAND_LF_DIR, &pctx)) 434 return 1; 435 retval = expand_directory(ctx, lost_and_found); 436 if (retval) { 437 pctx.errcode = retval; 438 fix_problem(ctx, PR_3_CANT_EXPAND_LPF, &pctx); 439 return 1; 440 } 441 retval = ext2fs_link(fs, lost_and_found, name, inode, 0); 442 } 443 if (retval) { 444 pctx.errcode = retval; 445 fix_problem(ctx, PR_3_CANT_RECONNECT, &pctx); 446 return 1; 447 } 448 adjust_inode_count(ctx, inode, +1); 449 450 return 0; 451} 452 453/* 454 * Utility routine to adjust the inode counts on an inode. 455 */ 456static errcode_t adjust_inode_count(e2fsck_t ctx, ino_t ino, int adj) 457{ 458 ext2_filsys fs = ctx->fs; 459 errcode_t retval; 460 struct ext2_inode inode; 461 462 if (!ino) 463 return 0; 464 465 retval = ext2fs_read_inode(fs, ino, &inode); 466 if (retval) 467 return retval; 468 469#if 0 470 printf("Adjusting link count for inode %lu by %d (from %d)\n", ino, adj, 471 inode.i_links_count); 472#endif 473 474 inode.i_links_count += adj; 475 if (adj == 1) { 476 ext2fs_icount_increment(ctx->inode_count, ino, 0); 477 ext2fs_icount_increment(ctx->inode_link_info, ino, 0); 478 } else { 479 ext2fs_icount_decrement(ctx->inode_count, ino, 0); 480 ext2fs_icount_decrement(ctx->inode_link_info, ino, 0); 481 } 482 483 484 retval = ext2fs_write_inode(fs, ino, &inode); 485 if (retval) 486 return retval; 487 488 return 0; 489} 490 491/* 492 * Fix parent --- this routine fixes up the parent of a directory. 493 */ 494struct fix_dotdot_struct { 495 ext2_filsys fs; 496 ino_t parent; 497 int done; 498 e2fsck_t ctx; 499}; 500 501static int fix_dotdot_proc(struct ext2_dir_entry *dirent, 502 int offset, 503 int blocksize, 504 char *buf, 505 void *private) 506{ 507 struct fix_dotdot_struct *fp = (struct fix_dotdot_struct *) private; 508 errcode_t retval; 509 struct problem_context pctx; 510 511 if (dirent->name_len != 2) 512 return 0; 513 if (strncmp(dirent->name, "..", 2)) 514 return 0; 515 516 clear_problem_context(&pctx); 517 518 retval = adjust_inode_count(fp->ctx, dirent->inode, -1); 519 if (retval) { 520 pctx.errcode = retval; 521 fix_problem(fp->ctx, PR_3_ADJUST_INODE, &pctx); 522 } 523 retval = adjust_inode_count(fp->ctx, fp->parent, 1); 524 if (retval) { 525 pctx.errcode = retval; 526 fix_problem(fp->ctx, PR_3_ADJUST_INODE, &pctx); 527 } 528 dirent->inode = fp->parent; 529 530 fp->done++; 531 return DIRENT_ABORT | DIRENT_CHANGED; 532} 533 534static void fix_dotdot(e2fsck_t ctx, struct dir_info *dir, ino_t parent) 535{ 536 ext2_filsys fs = ctx->fs; 537 errcode_t retval; 538 struct fix_dotdot_struct fp; 539 struct problem_context pctx; 540 541 fp.fs = fs; 542 fp.parent = parent; 543 fp.done = 0; 544 fp.ctx = ctx; 545 546#if 0 547 printf("Fixing '..' of inode %lu to be %lu...\n", dir->ino, parent); 548#endif 549 550 retval = ext2fs_dir_iterate(fs, dir->ino, DIRENT_FLAG_INCLUDE_EMPTY, 551 0, fix_dotdot_proc, &fp); 552 if (retval || !fp.done) { 553 clear_problem_context(&pctx); 554 pctx.ino = dir->ino; 555 pctx.errcode = retval; 556 fix_problem(ctx, retval ? PR_3_FIX_PARENT_ERR : 557 PR_3_FIX_PARENT_NOFIND, &pctx); 558 ext2fs_unmark_valid(fs); 559 } 560 dir->dotdot = parent; 561 562 return; 563} 564 565/* 566 * These routines are responsible for expanding a /lost+found if it is 567 * too small. 568 */ 569 570struct expand_dir_struct { 571 int done; 572 errcode_t err; 573 e2fsck_t ctx; 574}; 575 576static int expand_dir_proc(ext2_filsys fs, 577 blk_t *blocknr, 578 int blockcnt, 579 void *private) 580{ 581 struct expand_dir_struct *es = (struct expand_dir_struct *) private; 582 blk_t new_blk; 583 static blk_t last_blk = 0; 584 char *block; 585 errcode_t retval; 586 e2fsck_t ctx; 587 588 ctx = es->ctx; 589 590 if (*blocknr) { 591 last_blk = *blocknr; 592 return 0; 593 } 594 retval = ext2fs_new_block(fs, last_blk, ctx->block_found_map, 595 &new_blk); 596 if (retval) { 597 es->err = retval; 598 return BLOCK_ABORT; 599 } 600 if (blockcnt > 0) { 601 retval = ext2fs_new_dir_block(fs, 0, 0, &block); 602 if (retval) { 603 es->err = retval; 604 return BLOCK_ABORT; 605 } 606 es->done = 1; 607 } else { 608 block = malloc(fs->blocksize); 609 if (!block) { 610 es->err = ENOMEM; 611 return BLOCK_ABORT; 612 } 613 memset(block, 0, fs->blocksize); 614 } 615 retval = ext2fs_write_dir_block(fs, new_blk, block); 616 if (retval) { 617 es->err = retval; 618 return BLOCK_ABORT; 619 } 620 free(block); 621 *blocknr = new_blk; 622 ext2fs_mark_block_bitmap(ctx->block_found_map, new_blk); 623 ext2fs_mark_block_bitmap(fs->block_map, new_blk); 624 ext2fs_mark_bb_dirty(fs); 625 if (es->done) 626 return (BLOCK_CHANGED | BLOCK_ABORT); 627 else 628 return BLOCK_CHANGED; 629} 630 631static errcode_t expand_directory(e2fsck_t ctx, ino_t dir) 632{ 633 ext2_filsys fs = ctx->fs; 634 errcode_t retval; 635 struct expand_dir_struct es; 636 struct ext2_inode inode; 637 638 if (!(fs->flags & EXT2_FLAG_RW)) 639 return EXT2_ET_RO_FILSYS; 640 641 retval = ext2fs_check_directory(fs, dir); 642 if (retval) 643 return retval; 644 645 es.done = 0; 646 es.err = 0; 647 es.ctx = ctx; 648 649 retval = ext2fs_block_iterate(fs, dir, BLOCK_FLAG_APPEND, 650 0, expand_dir_proc, &es); 651 652 if (es.err) 653 return es.err; 654 if (!es.done) 655 return EXT2_ET_EXPAND_DIR_ERR; 656 657 /* 658 * Update the size and block count fields in the inode. 659 */ 660 retval = ext2fs_read_inode(fs, dir, &inode); 661 if (retval) 662 return retval; 663 664 inode.i_size += fs->blocksize; 665 inode.i_blocks += fs->blocksize / 512; 666 667 e2fsck_write_inode(fs, dir, &inode, "expand_directory"); 668 669 return 0; 670} 671