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