sbin/fsck_ext2fs/pass2.c

   1 /*      $NetBSD: pass2.c,v 1.15 2009/10/19 18:41:08 bouyer Exp $        */
   2
   3 /*
   4  * Copyright (c) 1980, 1986, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of the University nor the names of its contributors
  16  *    may be used to endorse or promote products derived from this software
  17  *    without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29  * SUCH DAMAGE.
  30  */
  31
  32 /*
  33  * Copyright (c) 1997 Manuel Bouyer.
  34  *
  35  * Redistribution and use in source and binary forms, with or without
  36  * modification, are permitted provided that the following conditions
  37  * are met:
  38  * 1. Redistributions of source code must retain the above copyright
  39  *    notice, this list of conditions and the following disclaimer.
  40  * 2. Redistributions in binary form must reproduce the above copyright
  41  *    notice, this list of conditions and the following disclaimer in the
  42  *    documentation and/or other materials provided with the distribution.
  43  *
  44  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  45  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  46  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  47  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  48  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  49  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  50  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  51  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  52  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  53  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  54  */
  55
  56 #include <sys/cdefs.h>
  57 #ifndef lint
  58 #if 0
  59 static char sccsid[] = "@(#)pass2.c     8.6 (Berkeley) 10/27/94";
  60 #else
  61 __RCSID("$NetBSD: pass2.c,v 1.15 2009/10/19 18:41:08 bouyer Exp $");
  62 #endif
  63 #endif /* not lint */
  64
  65 #include <sys/param.h>
  66 #include <sys/time.h>
  67 #include <ufs/ext2fs/ext2fs_dinode.h>
  68 #include <ufs/ext2fs/ext2fs_dir.h>
  69 #include <ufs/ext2fs/ext2fs.h>
  70
  71 #include <ufs/ufs/dinode.h> /* for IFMT & friends */
  72
  73 #include <stdio.h>
  74 #include <stdlib.h>
  75 #include <string.h>
  76
  77 #include "fsck.h"
  78 #include "fsutil.h"
  79 #include "extern.h"
  80 #include "exitvalues.h"
  81
  82 #define MINDIRSIZE      (sizeof (struct ext2fs_dirtemplate))
  83
  84 static int pass2check(struct inodesc *);
  85 static int blksort(const void *, const void *);
  86
  87 void
  88 pass2(void)
  89 {
  90         struct ext2fs_dinode *dp;
  91         struct inoinfo **inpp, *inp;
  92         struct inoinfo **inpend;
  93         struct inodesc curino;
  94         struct ext2fs_dinode dino;
  95         char pathbuf[MAXPATHLEN + 1];
  96
  97         switch (statemap[EXT2_ROOTINO]) {
  98
  99         case USTATE:
 100                 pfatal("ROOT INODE UNALLOCATED");
 101                 if (reply("ALLOCATE") == 0)
 102                         exit(FSCK_EXIT_CHECK_FAILED);
 103                 if (allocdir(EXT2_ROOTINO, EXT2_ROOTINO, 0755) != EXT2_ROOTINO)
 104                         errexit("CANNOT ALLOCATE ROOT INODE");
 105                 break;
 106
 107         case DCLEAR:
 108                 pfatal("DUPS/BAD IN ROOT INODE");
 109                 if (reply("REALLOCATE")) {
 110                         freeino(EXT2_ROOTINO);
 111                         if (allocdir(EXT2_ROOTINO, EXT2_ROOTINO, 0755) != EXT2_ROOTINO)
 112                                 errexit("CANNOT ALLOCATE ROOT INODE");
 113                         break;
 114                 }
 115                 if (reply("CONTINUE") == 0)
 116                         exit(FSCK_EXIT_CHECK_FAILED);
 117                 break;
 118
 119         case FSTATE:
 120         case FCLEAR:
 121                 pfatal("ROOT INODE NOT DIRECTORY");
 122                 if (reply("REALLOCATE")) {
 123                         freeino(EXT2_ROOTINO);
 124                         if (allocdir(EXT2_ROOTINO, EXT2_ROOTINO, 0755) != EXT2_ROOTINO)
 125                                 errexit("CANNOT ALLOCATE ROOT INODE");
 126                         break;
 127                 }
 128                 if (reply("FIX") == 0)
 129                         exit(FSCK_EXIT_CHECK_FAILED);
 130                 dp = ginode(EXT2_ROOTINO);
 131                 dp->e2di_mode = h2fs16((fs2h16(dp->e2di_mode) & ~IFMT) | IFDIR);
 132                 inodirty();
 133                 break;
 134
 135         case DSTATE:
 136                 break;
 137
 138         default:
 139                 errexit("BAD STATE %d FOR ROOT INODE", statemap[EXT2_ROOTINO]);
 140         }
 141
 142         /*
 143          * Sort the directory list into disk block order.
 144          */
 145         qsort((char *)inpsort, (size_t)inplast, sizeof *inpsort, blksort);
 146         /*
 147          * Check the integrity of each directory.
 148          */
 149         memset(&curino, 0, sizeof(struct inodesc));
 150         curino.id_type = DATA;
 151         curino.id_func = pass2check;
 152         inpend = &inpsort[inplast];
 153         for (inpp = inpsort; inpp < inpend; inpp++) {
 154                 inp = *inpp;
 155                 if (inp->i_isize == 0)
 156                         continue;
 157                 if (inp->i_isize < MINDIRSIZE) {
 158                         direrror(inp->i_number, "DIRECTORY TOO SHORT");
 159                         inp->i_isize = roundup(MINDIRSIZE, sblock.e2fs_bsize);
 160                         if (reply("FIX") == 1) {
 161                                 dp = ginode(inp->i_number);
 162                                 inossize(dp, inp->i_isize);
 163                                 inodirty();
 164                         }
 165                 } else if ((inp->i_isize & (sblock.e2fs_bsize - 1)) != 0) {
 166                         getpathname(pathbuf, sizeof(pathbuf), inp->i_number,
 167                             inp->i_number);
 168                         pwarn("DIRECTORY %s: LENGTH %lu NOT MULTIPLE OF %d",
 169                             pathbuf, (u_long)inp->i_isize, sblock.e2fs_bsize);
 170                         if (preen)
 171                                 printf(" (ADJUSTED)\n");
 172                         inp->i_isize = roundup(inp->i_isize, sblock.e2fs_bsize);
 173                         if (preen || reply("ADJUST") == 1) {
 174                                 dp = ginode(inp->i_number);
 175                                 inossize(dp, inp->i_isize);
 176                                 inodirty();
 177                         }
 178                 }
 179                 memset(&dino, 0, sizeof(struct ext2fs_dinode));
 180                 dino.e2di_mode = h2fs16(IFDIR);
 181                 inossize(&dino, inp->i_isize);
 182                 memcpy(&dino.e2di_blocks[0], &inp->i_blks[0], (size_t)inp->i_numblks);
 183                 curino.id_number = inp->i_number;
 184                 curino.id_parent = inp->i_parent;
 185                 (void)ckinode(&dino, &curino);
 186         }
 187         /*
 188          * Now that the parents of all directories have been found,
 189          * make another pass to verify the value of `..'
 190          */
 191         for (inpp = inpsort; inpp < inpend; inpp++) {
 192                 inp = *inpp;
 193                 if (inp->i_parent == 0 || inp->i_isize == 0)
 194                         continue;
 195                 if (inp->i_dotdot == inp->i_parent ||
 196                     inp->i_dotdot == (ino_t)-1)
 197                         continue;
 198                 if (inp->i_dotdot == 0) {
 199                         inp->i_dotdot = inp->i_parent;
 200                         fileerror(inp->i_parent, inp->i_number, "MISSING '..'");
 201                         if (reply("FIX") == 0)
 202                                 continue;
 203                         (void)makeentry(inp->i_number, inp->i_parent, "..");
 204                         lncntp[inp->i_parent]--;
 205                         continue;
 206                 }
 207                 fileerror(inp->i_parent, inp->i_number,
 208                     "BAD INODE NUMBER FOR '..'");
 209                 if (reply("FIX") == 0)
 210                         continue;
 211                 lncntp[inp->i_dotdot]++;
 212                 lncntp[inp->i_parent]--;
 213                 inp->i_dotdot = inp->i_parent;
 214                 (void)changeino(inp->i_number, "..", inp->i_parent);
 215         }
 216         /*
 217          * Mark all the directories that can be found from the root.
 218          */
 219         propagate();
 220 }
 221
 222 static int
 223 pass2check(struct inodesc *idesc)
 224 {
 225         struct ext2fs_direct *dirp = idesc->id_dirp;
 226         struct inoinfo *inp;
 227         int n, entrysize, ret = 0;
 228         struct ext2fs_dinode *dp;
 229         const char *errmsg;
 230         struct ext2fs_direct proto;
 231         char namebuf[MAXPATHLEN + 1];
 232         char pathbuf[MAXPATHLEN + 1];
 233
 234         /*
 235          * check for "."
 236          */
 237         if (idesc->id_entryno != 0)
 238                 goto chk1;
 239         if (fs2h32(dirp->e2d_ino) != 0 && dirp->e2d_namlen == 1 &&
 240                 dirp->e2d_name[0] == '.') {
 241                 if (fs2h32(dirp->e2d_ino) != idesc->id_number) {
 242                         direrror(idesc->id_number, "BAD INODE NUMBER FOR '.'");
 243                         dirp->e2d_ino = h2fs32(idesc->id_number);
 244                         if (reply("FIX") == 1)
 245                                 ret |= ALTERED;
 246                 }
 247                 if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 248                     (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE)
 249                     && (dirp->e2d_type != EXT2_FT_DIR)) {
 250                         direrror(idesc->id_number, "BAD TYPE VALUE FOR '.'");
 251                         dirp->e2d_type = EXT2_FT_DIR;
 252                         if (reply("FIX") == 1)
 253                                 ret |= ALTERED;
 254                 }
 255                 goto chk1;
 256         }
 257         direrror(idesc->id_number, "MISSING '.'");
 258         proto.e2d_ino = h2fs32(idesc->id_number);
 259         proto.e2d_namlen = 1;
 260         if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 261             (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE))
 262                 proto.e2d_type = EXT2_FT_DIR;
 263         else
 264                 proto.e2d_type = 0;
 265         (void)strlcpy(proto.e2d_name, ".", sizeof(proto.e2d_name));
 266         entrysize = EXT2FS_DIRSIZ(proto.e2d_namlen);
 267         if (fs2h32(dirp->e2d_ino) != 0 && strcmp(dirp->e2d_name, "..") != 0) {
 268                 pfatal("CANNOT FIX, FIRST ENTRY IN DIRECTORY CONTAINS %s\n",
 269                         dirp->e2d_name);
 270         } else if (fs2h16(dirp->e2d_reclen) < entrysize) {
 271                 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '.'\n");
 272         } else if (fs2h16(dirp->e2d_reclen) < 2 * entrysize) {
 273                 proto.e2d_reclen = dirp->e2d_reclen;
 274                 memcpy(dirp, &proto, (size_t)entrysize);
 275                 if (reply("FIX") == 1)
 276                         ret |= ALTERED;
 277         } else {
 278                 n = fs2h16(dirp->e2d_reclen) - entrysize;
 279                 proto.e2d_reclen = h2fs16(entrysize);
 280                 memcpy(dirp, &proto, (size_t)entrysize);
 281                 idesc->id_entryno++;
 282                 lncntp[fs2h32(dirp->e2d_ino)]--;
 283                 dirp = (struct ext2fs_direct *)((char *)(dirp) + entrysize);
 284                 memset(dirp, 0, (size_t)n);
 285                 dirp->e2d_reclen = h2fs16(n);
 286                 if (reply("FIX") == 1)
 287                         ret |= ALTERED;
 288         }
 289 chk1:
 290         if (idesc->id_entryno > 1)
 291                 goto chk2;
 292         inp = getinoinfo(idesc->id_number);
 293         proto.e2d_ino = h2fs32(inp->i_parent);
 294         proto.e2d_namlen = 2;
 295         if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 296             (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE))
 297                 proto.e2d_type = EXT2_FT_DIR;
 298         else
 299                 proto.e2d_type = 0;
 300         (void)strlcpy(proto.e2d_name, "..", sizeof(proto.e2d_name));
 301         entrysize = EXT2FS_DIRSIZ(2);
 302         if (idesc->id_entryno == 0) {
 303                 n = EXT2FS_DIRSIZ(dirp->e2d_namlen);
 304                 if (fs2h16(dirp->e2d_reclen) < n + entrysize)
 305                         goto chk2;
 306                 proto.e2d_reclen = h2fs16(fs2h16(dirp->e2d_reclen) - n);
 307                 dirp->e2d_reclen = h2fs16(n);
 308                 idesc->id_entryno++;
 309                 lncntp[fs2h32(dirp->e2d_ino)]--;
 310                 dirp = (struct ext2fs_direct *)((char *)(dirp) + n);
 311                 memset(dirp, 0, (size_t)fs2h16(proto.e2d_reclen));
 312                 dirp->e2d_reclen = proto.e2d_reclen;
 313         }
 314         if (fs2h32(dirp->e2d_ino) != 0 &&
 315             dirp->e2d_namlen == 2 &&
 316             strncmp(dirp->e2d_name, "..", 2) == 0) {
 317                 inp->i_dotdot = fs2h32(dirp->e2d_ino);
 318                 if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 319                     (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE)
 320                     && dirp->e2d_type != EXT2_FT_DIR) {
 321                         direrror(idesc->id_number, "BAD TYPE VALUE FOR '..'");
 322                         dirp->e2d_type = EXT2_FT_DIR;
 323                         if (reply("FIX") == 1)
 324                                 ret |= ALTERED;
 325                 }
 326                 goto chk2;
 327         }
 328         if (fs2h32(dirp->e2d_ino) != 0 &&
 329                 dirp->e2d_namlen == 1 &&
 330                 strncmp(dirp->e2d_name, ".", 1) != 0) {
 331                 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
 332                 pfatal("CANNOT FIX, SECOND ENTRY IN DIRECTORY CONTAINS %s\n",
 333                         dirp->e2d_name);
 334                 inp->i_dotdot = (ino_t)-1;
 335         } else if (fs2h16(dirp->e2d_reclen) < entrysize) {
 336                 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
 337                 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '..'\n");
 338                 inp->i_dotdot = (ino_t)-1;
 339         } else if (inp->i_parent != 0) {
 340                 /*
 341                  * We know the parent, so fix now.
 342                  */
 343                 inp->i_dotdot = inp->i_parent;
 344                 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
 345                 proto.e2d_reclen = dirp->e2d_reclen;
 346                 memcpy(dirp, &proto, (size_t)entrysize);
 347                 if (reply("FIX") == 1)
 348                         ret |= ALTERED;
 349         }
 350         idesc->id_entryno++;
 351         if (fs2h32(dirp->e2d_ino) != 0)
 352                 lncntp[fs2h32(dirp->e2d_ino)]--;
 353         return (ret|KEEPON);
 354 chk2:
 355         if (fs2h32(dirp->e2d_ino) == 0)
 356                 return (ret|KEEPON);
 357         if (dirp->e2d_namlen <= 2 &&
 358             dirp->e2d_name[0] == '.' &&
 359             idesc->id_entryno >= 2) {
 360                 if (dirp->e2d_namlen == 1) {
 361                         direrror(idesc->id_number, "EXTRA '.' ENTRY");
 362                         dirp->e2d_ino = 0;
 363                         if (reply("FIX") == 1)
 364                                 ret |= ALTERED;
 365                         return (KEEPON | ret);
 366                 }
 367                 if (dirp->e2d_name[1] == '.') {
 368                         direrror(idesc->id_number, "EXTRA '..' ENTRY");
 369                         dirp->e2d_ino = 0;
 370                         if (reply("FIX") == 1)
 371                                 ret |= ALTERED;
 372                         return (KEEPON | ret);
 373                 }
 374         }
 375         idesc->id_entryno++;
 376         n = 0;
 377         if (fs2h32(dirp->e2d_ino) > maxino ||
 378                 (fs2h32(dirp->e2d_ino) < EXT2_FIRSTINO &&
 379                  fs2h32(dirp->e2d_ino) != EXT2_ROOTINO)) {
 380                 fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), "I OUT OF RANGE");
 381                 n = reply("REMOVE");
 382         } else {
 383 again:
 384                 switch (statemap[fs2h32(dirp->e2d_ino)]) {
 385                 case USTATE:
 386                         if (idesc->id_entryno <= 2)
 387                                 break;
 388                         fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), "UNALLOCATED");
 389                         n = reply("REMOVE");
 390                         break;
 391
 392                 case DCLEAR:
 393                 case FCLEAR:
 394                         if (idesc->id_entryno <= 2)
 395                                 break;
 396                         if (statemap[fs2h32(dirp->e2d_ino)] == FCLEAR)
 397                                 errmsg = "DUP/BAD";
 398                         else if (!preen)
 399                                 errmsg = "ZERO LENGTH DIRECTORY";
 400                         else {
 401                                 n = 1;
 402                                 break;
 403                         }
 404                         fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), errmsg);
 405                         if ((n = reply("REMOVE")) == 1)
 406                                 break;
 407                         dp = ginode(fs2h32(dirp->e2d_ino));
 408                         statemap[fs2h32(dirp->e2d_ino)] =
 409                             (fs2h16(dp->e2di_mode) & IFMT) == IFDIR ? DSTATE : FSTATE;
 410                         lncntp[fs2h32(dirp->e2d_ino)] = fs2h16(dp->e2di_nlink);
 411                         goto again;
 412
 413                 case DSTATE:
 414                 case DFOUND:
 415                         inp = getinoinfo(fs2h32(dirp->e2d_ino));
 416                         if (inp->i_parent != 0 && idesc->id_entryno > 2) {
 417                                 getpathname(pathbuf, sizeof(pathbuf),
 418                                     idesc->id_number, idesc->id_number);
 419                                 getpathname(namebuf, sizeof(namebuf),
 420                                     fs2h32(dirp->e2d_ino),
 421                                     fs2h32(dirp->e2d_ino));
 422                                 pwarn("%s %s %s\n", pathbuf,
 423                                     "IS AN EXTRANEOUS HARD LINK TO DIRECTORY",
 424                                     namebuf);
 425                                 if (preen)
 426                                         printf(" (IGNORED)\n");
 427                                 else if ((n = reply("REMOVE")) == 1)
 428                                         break;
 429                         }
 430                         if (idesc->id_entryno > 2)
 431                                 inp->i_parent = idesc->id_number;
 432                         /* fall through */
 433
 434                 case FSTATE:
 435                         if (sblock.e2fs.e2fs_rev > E2FS_REV0 &&
 436                             (sblock.e2fs.e2fs_features_incompat &
 437                                 EXT2F_INCOMPAT_FTYPE) &&
 438                             dirp->e2d_type !=
 439                                 inot2ext2dt(typemap[fs2h32(dirp->e2d_ino)])) {
 440                                 dirp->e2d_type =
 441                                     inot2ext2dt(typemap[fs2h32(dirp->e2d_ino)]);
 442                                 fileerror(idesc->id_number,
 443                                     fs2h32(dirp->e2d_ino),
 444                                     "BAD TYPE VALUE");
 445                                 if (reply("FIX") == 1)
 446                                         ret |= ALTERED;
 447                         }
 448                         lncntp[fs2h32(dirp->e2d_ino)]--;
 449                         break;
 450
 451                 default:
 452                         errexit("BAD STATE %d FOR INODE I=%d",
 453                             statemap[fs2h32(dirp->e2d_ino)], fs2h32(dirp->e2d_ino));
 454                 }
 455         }
 456         if (n == 0)
 457                 return (ret|KEEPON);
 458         dirp->e2d_ino = 0;
 459         return (ret|KEEPON|ALTERED);
 460 }
 461
 462 /*
 463  * Routine to sort disk blocks.
 464  */
 465 static int
 466 blksort(const void *inpp1, const void *inpp2)
 467 {
 468         return ((* (const struct inoinfo * const*) inpp1)->i_blks[0] -
 469                 (* (const struct inoinfo * const*) inpp2)->i_blks[0]);
 470 }