e2fsck/pass3.c

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