e2fsck/pass3.c

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