sbin/fsck/pass2.c

   1 /*
   2  * Copyright (c) 1980, 1986, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by the University of
  16  *      California, Berkeley and its contributors.
  17  * 4. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  * @(#)pass2.c  8.9 (Berkeley) 4/28/95
  34  * $FreeBSD: src/sbin/fsck/pass2.c,v 1.10.2.2 2001/11/24 15:14:59 iedowse Exp $
  35  * $DragonFly: src/sbin/fsck/pass2.c,v 1.11 2006/10/12 06:04:03 dillon Exp $
  36  */
  37
  38 #include <sys/param.h>
  39
  40 #include <vfs/ufs/dinode.h>
  41 #include <vfs/ufs/dir.h>
  42
  43 #include <err.h>
  44 #include <string.h>
  45
  46 #include "fsck.h"
  47
  48 #define MINDIRSIZE      (sizeof (struct dirtemplate))
  49
  50 static int blksort(const void *, const void *);
  51 static int pass2check(struct inodesc *);
  52
  53 void
  54 pass2(void)
  55 {
  56         struct ufs1_dinode *dp;
  57         struct inoinfo **inpp, *inp;
  58         struct inoinfo **inpend;
  59         struct inodesc curino;
  60         struct ufs1_dinode dino;
  61         char pathbuf[MAXPATHLEN + 1];
  62         long i, n;
  63
  64         switch (inoinfo(ROOTINO)->ino_state) {
  65
  66         case USTATE:
  67                 pfatal("ROOT INODE UNALLOCATED");
  68                 if (reply("ALLOCATE") == 0) {
  69                         ckfini(0);
  70                         exit(EEXIT);
  71                 }
  72                 if (allocdir(ROOTINO, ROOTINO, 0755) != ROOTINO)
  73                         errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
  74                 break;
  75
  76         case DCLEAR:
  77                 pfatal("DUPS/BAD IN ROOT INODE");
  78                 if (reply("REALLOCATE")) {
  79                         freeino(ROOTINO);
  80                         if (allocdir(ROOTINO, ROOTINO, 0755) != ROOTINO)
  81                                 errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
  82                         break;
  83                 }
  84                 if (reply("CONTINUE") == 0) {
  85                         ckfini(0);
  86                         exit(EEXIT);
  87                 }
  88                 break;
  89
  90         case FSTATE:
  91         case FCLEAR:
  92                 pfatal("ROOT INODE NOT DIRECTORY");
  93                 if (reply("REALLOCATE")) {
  94                         freeino(ROOTINO);
  95                         if (allocdir(ROOTINO, ROOTINO, 0755) != ROOTINO)
  96                                 errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
  97                         break;
  98                 }
  99                 if (reply("FIX") == 0) {
 100                         ckfini(0);
 101                         exit(EEXIT);
 102                 }
 103                 dp = ginode(ROOTINO);
 104                 dp->di_mode &= ~IFMT;
 105                 dp->di_mode |= IFDIR;
 106                 inodirty();
 107                 break;
 108
 109         case DSTATE:
 110                 break;
 111
 112         default:
 113                 errx(EEXIT, "BAD STATE %d FOR ROOT INODE",
 114                     inoinfo(ROOTINO)->ino_state);
 115         }
 116         inoinfo(ROOTINO)->ino_state = DFOUND;
 117         if (newinofmt) {
 118                 inoinfo(WINO)->ino_state = FSTATE;
 119                 inoinfo(WINO)->ino_type = DT_WHT;
 120         }
 121         /*
 122          * Sort the directory list into disk block order.  Do this in blocks
 123          * of 1000 directories in order to maintain locality of reference
 124          * in memory in case fsck is using swap space.
 125          */
 126         for (i = 0; i < inplast; i += 1000) {
 127                 if ((n = inplast - i) > 1000)
 128                         n = 1000;
 129                 qsort(inpsort + i, (size_t)n, sizeof *inpsort, blksort);
 130         }
 131
 132         /*
 133          * Check the integrity of each directory.
 134          */
 135         memset(&curino, 0, sizeof(struct inodesc));
 136         curino.id_type = DATA;
 137         curino.id_func = pass2check;
 138         dp = &dino;
 139         inpend = &inpsort[inplast];
 140         for (inpp = inpsort; inpp < inpend; inpp++) {
 141                 if (got_siginfo) {
 142                         printf("%s: phase 2: dir %d of %ld (%d%%)\n", cdevname,
 143                             inpp - inpsort, inplast, (int)((inpp - inpsort) * 100 /
 144                             inplast));
 145                         got_siginfo = 0;
 146                 }
 147                 inp = *inpp;
 148                 if (inp->i_isize == 0)
 149                         continue;
 150                 if (inp->i_isize < MINDIRSIZE) {
 151                         direrror(inp->i_number, "DIRECTORY TOO SHORT");
 152                         inp->i_isize = roundup(MINDIRSIZE, DIRBLKSIZ);
 153                         if (reply("FIX") == 1) {
 154                                 dp = ginode(inp->i_number);
 155                                 dp->di_size = inp->i_isize;
 156                                 inodirty();
 157                                 dp = &dino;
 158                         }
 159                 } else if ((inp->i_isize & (DIRBLKSIZ - 1)) != 0) {
 160                         getpathname(pathbuf, inp->i_number, inp->i_number);
 161                         if (usedsoftdep)
 162                                 pfatal("%s %s: LENGTH %d NOT MULTIPLE OF %d",
 163                                         "DIRECTORY", pathbuf, inp->i_isize,
 164                                         DIRBLKSIZ);
 165                         else
 166                                 pwarn("%s %s: LENGTH %d NOT MULTIPLE OF %d",
 167                                         "DIRECTORY", pathbuf, inp->i_isize,
 168                                         DIRBLKSIZ);
 169                         if (preen)
 170                                 printf(" (ADJUSTED)\n");
 171                         inp->i_isize = roundup(inp->i_isize, DIRBLKSIZ);
 172                         if (preen || reply("ADJUST") == 1) {
 173                                 dp = ginode(inp->i_number);
 174                                 dp->di_size = roundup(inp->i_isize, DIRBLKSIZ);
 175                                 inodirty();
 176                                 dp = &dino;
 177                         }
 178                 }
 179                 memset(&dino, 0, sizeof(struct ufs1_dinode));
 180                 dino.di_mode = IFDIR;
 181                 dp->di_size = inp->i_isize;
 182                 memmove(&dp->di_db[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                 ckinode(dp, &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 (inoinfo(inp->i_parent)->ino_state == DFOUND &&
 196                     inoinfo(inp->i_number)->ino_state == DSTATE)
 197                         inoinfo(inp->i_number)->ino_state = DFOUND;
 198                 if (inp->i_dotdot == inp->i_parent ||
 199                     inp->i_dotdot == (ufs1_ino_t)-1)
 200                         continue;
 201                 if (inp->i_dotdot == 0) {
 202                         inp->i_dotdot = inp->i_parent;
 203                         fileerror(inp->i_parent, inp->i_number, "MISSING '..'");
 204                         if (reply("FIX") == 0)
 205                                 continue;
 206                         makeentry(inp->i_number, inp->i_parent, "..");
 207                         inoinfo(inp->i_parent)->ino_linkcnt--;
 208                         continue;
 209                 }
 210                 fileerror(inp->i_parent, inp->i_number,
 211                     "BAD INODE NUMBER FOR '..'");
 212                 if (reply("FIX") == 0)
 213                         continue;
 214                 inoinfo(inp->i_dotdot)->ino_linkcnt++;
 215                 inoinfo(inp->i_parent)->ino_linkcnt--;
 216                 inp->i_dotdot = inp->i_parent;
 217                 changeino(inp->i_number, "..", inp->i_parent);
 218         }
 219         /*
 220          * Mark all the directories that can be found from the root.
 221          */
 222         propagate();
 223 }
 224
 225 static int
 226 pass2check(struct inodesc *idesc)
 227 {
 228         struct direct *dirp = idesc->id_dirp;
 229         struct inoinfo *inp;
 230         int n, entrysize, ret = 0;
 231         struct ufs1_dinode *dp;
 232         char *errmsg;
 233         struct direct proto;
 234         char namebuf[MAXPATHLEN + 1];
 235         char pathbuf[MAXPATHLEN + 1];
 236
 237         /*
 238          * If converting, set directory entry type.
 239          */
 240         if (doinglevel2 && dirp->d_ino > 0 && dirp->d_ino < maxino) {
 241                 dirp->d_type = inoinfo(dirp->d_ino)->ino_type;
 242                 ret |= ALTERED;
 243         }
 244         /*
 245          * check for "."
 246          */
 247         if (idesc->id_entryno != 0)
 248                 goto chk1;
 249         if (dirp->d_ino != 0 && strcmp(dirp->d_name, ".") == 0) {
 250                 if (dirp->d_ino != idesc->id_number) {
 251                         direrror(idesc->id_number, "BAD INODE NUMBER FOR '.'");
 252                         dirp->d_ino = idesc->id_number;
 253                         if (reply("FIX") == 1)
 254                                 ret |= ALTERED;
 255                 }
 256                 if (newinofmt && dirp->d_type != DT_DIR) {
 257                         direrror(idesc->id_number, "BAD TYPE VALUE FOR '.'");
 258                         dirp->d_type = DT_DIR;
 259                         if (reply("FIX") == 1)
 260                                 ret |= ALTERED;
 261                 }
 262                 goto chk1;
 263         }
 264         direrror(idesc->id_number, "MISSING '.'");
 265         proto.d_ino = idesc->id_number;
 266         if (newinofmt)
 267                 proto.d_type = DT_DIR;
 268         else
 269                 proto.d_type = 0;
 270         proto.d_namlen = 1;
 271         strcpy(proto.d_name, ".");
 272 #       if BYTE_ORDER == LITTLE_ENDIAN
 273                 if (!newinofmt) {
 274                         u_char tmp;
 275
 276                         tmp = proto.d_type;
 277                         proto.d_type = proto.d_namlen;
 278                         proto.d_namlen = tmp;
 279                 }
 280 #       endif
 281         entrysize = DIRSIZ(0, &proto);
 282         if (dirp->d_ino != 0 && strcmp(dirp->d_name, "..") != 0) {
 283                 pfatal("CANNOT FIX, FIRST ENTRY IN DIRECTORY CONTAINS %s\n",
 284                         dirp->d_name);
 285         } else if (dirp->d_reclen < entrysize) {
 286                 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '.'\n");
 287         } else if (dirp->d_reclen < 2 * entrysize) {
 288                 proto.d_reclen = dirp->d_reclen;
 289                 memmove(dirp, &proto, (size_t)entrysize);
 290                 if (reply("FIX") == 1)
 291                         ret |= ALTERED;
 292         } else {
 293                 n = dirp->d_reclen - entrysize;
 294                 proto.d_reclen = entrysize;
 295                 memmove(dirp, &proto, (size_t)entrysize);
 296                 idesc->id_entryno++;
 297                 inoinfo(dirp->d_ino)->ino_linkcnt--;
 298                 dirp = (struct direct *)((char *)(dirp) + entrysize);
 299                 memset(dirp, 0, (size_t)n);
 300                 dirp->d_reclen = n;
 301                 if (reply("FIX") == 1)
 302                         ret |= ALTERED;
 303         }
 304 chk1:
 305         if (idesc->id_entryno > 1)
 306                 goto chk2;
 307         inp = getinoinfo(idesc->id_number);
 308         proto.d_ino = inp->i_parent;
 309         if (newinofmt)
 310                 proto.d_type = DT_DIR;
 311         else
 312                 proto.d_type = 0;
 313         proto.d_namlen = 2;
 314         strcpy(proto.d_name, "..");
 315 #       if BYTE_ORDER == LITTLE_ENDIAN
 316                 if (!newinofmt) {
 317                         u_char tmp;
 318
 319                         tmp = proto.d_type;
 320                         proto.d_type = proto.d_namlen;
 321                         proto.d_namlen = tmp;
 322                 }
 323 #       endif
 324         entrysize = DIRSIZ(0, &proto);
 325         if (idesc->id_entryno == 0) {
 326                 n = DIRSIZ(0, dirp);
 327                 if (dirp->d_reclen < n + entrysize)
 328                         goto chk2;
 329                 proto.d_reclen = dirp->d_reclen - n;
 330                 dirp->d_reclen = n;
 331                 idesc->id_entryno++;
 332                 inoinfo(dirp->d_ino)->ino_linkcnt--;
 333                 dirp = (struct direct *)((char *)(dirp) + n);
 334                 memset(dirp, 0, (size_t)proto.d_reclen);
 335                 dirp->d_reclen = proto.d_reclen;
 336         }
 337         if (dirp->d_ino != 0 && strcmp(dirp->d_name, "..") == 0) {
 338                 inp->i_dotdot = dirp->d_ino;
 339                 if (newinofmt && dirp->d_type != DT_DIR) {
 340                         direrror(idesc->id_number, "BAD TYPE VALUE FOR '..'");
 341                         dirp->d_type = DT_DIR;
 342                         if (reply("FIX") == 1)
 343                                 ret |= ALTERED;
 344                 }
 345                 goto chk2;
 346         }
 347         if (dirp->d_ino != 0 && strcmp(dirp->d_name, ".") != 0) {
 348                 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
 349                 pfatal("CANNOT FIX, SECOND ENTRY IN DIRECTORY CONTAINS %s\n",
 350                         dirp->d_name);
 351                 inp->i_dotdot = (ufs1_ino_t)-1;
 352         } else if (dirp->d_reclen < entrysize) {
 353                 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
 354                 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '..'\n");
 355                 inp->i_dotdot = (ufs1_ino_t)-1;
 356         } else if (inp->i_parent != 0) {
 357                 /*
 358                  * We know the parent, so fix now.
 359                  */
 360                 inp->i_dotdot = inp->i_parent;
 361                 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
 362                 proto.d_reclen = dirp->d_reclen;
 363                 memmove(dirp, &proto, (size_t)entrysize);
 364                 if (reply("FIX") == 1)
 365                         ret |= ALTERED;
 366         }
 367         idesc->id_entryno++;
 368         if (dirp->d_ino != 0)
 369                 inoinfo(dirp->d_ino)->ino_linkcnt--;
 370         return (ret|KEEPON);
 371 chk2:
 372         if (dirp->d_ino == 0)
 373                 return (ret|KEEPON);
 374         if (dirp->d_namlen <= 2 &&
 375             dirp->d_name[0] == '.' &&
 376             idesc->id_entryno >= 2) {
 377                 if (dirp->d_namlen == 1) {
 378                         direrror(idesc->id_number, "EXTRA '.' ENTRY");
 379                         dirp->d_ino = 0;
 380                         if (reply("FIX") == 1)
 381                                 ret |= ALTERED;
 382                         return (KEEPON | ret);
 383                 }
 384                 if (dirp->d_name[1] == '.') {
 385                         direrror(idesc->id_number, "EXTRA '..' ENTRY");
 386                         dirp->d_ino = 0;
 387                         if (reply("FIX") == 1)
 388                                 ret |= ALTERED;
 389                         return (KEEPON | ret);
 390                 }
 391         }
 392         idesc->id_entryno++;
 393         n = 0;
 394         if (dirp->d_ino > maxino) {
 395                 fileerror(idesc->id_number, dirp->d_ino, "I OUT OF RANGE");
 396                 n = reply("REMOVE");
 397         } else if (newinofmt &&
 398                    ((dirp->d_ino == WINO && dirp->d_type != DT_WHT) ||
 399                     (dirp->d_ino != WINO && dirp->d_type == DT_WHT))) {
 400                 fileerror(idesc->id_number, dirp->d_ino, "BAD WHITEOUT ENTRY");
 401                 dirp->d_ino = WINO;
 402                 dirp->d_type = DT_WHT;
 403                 if (reply("FIX") == 1)
 404                         ret |= ALTERED;
 405         } else {
 406 again:
 407                 switch (inoinfo(dirp->d_ino)->ino_state) {
 408                 case USTATE:
 409                         if (idesc->id_entryno <= 2)
 410                                 break;
 411                         fileerror(idesc->id_number, dirp->d_ino, "UNALLOCATED");
 412                         n = reply("REMOVE");
 413                         break;
 414
 415                 case DCLEAR:
 416                 case FCLEAR:
 417                         if (idesc->id_entryno <= 2)
 418                                 break;
 419                         if (inoinfo(dirp->d_ino)->ino_state == FCLEAR)
 420                                 errmsg = "DUP/BAD";
 421                         else if (!preen && !usedsoftdep)
 422                                 errmsg = "ZERO LENGTH DIRECTORY";
 423                         else {
 424                                 n = 1;
 425                                 break;
 426                         }
 427                         fileerror(idesc->id_number, dirp->d_ino, errmsg);
 428                         if ((n = reply("REMOVE")) == 1)
 429                                 break;
 430                         dp = ginode(dirp->d_ino);
 431                         inoinfo(dirp->d_ino)->ino_state =
 432                             (dp->di_mode & IFMT) == IFDIR ? DSTATE : FSTATE;
 433                         inoinfo(dirp->d_ino)->ino_linkcnt = dp->di_nlink;
 434                         goto again;
 435
 436                 case DSTATE:
 437                         if (inoinfo(idesc->id_number)->ino_state == DFOUND)
 438                                 inoinfo(dirp->d_ino)->ino_state = DFOUND;
 439                         /* fall through */
 440
 441                 case DFOUND:
 442                         inp = getinoinfo(dirp->d_ino);
 443                         if (inp->i_parent != 0 && idesc->id_entryno > 2) {
 444                                 getpathname(pathbuf, idesc->id_number,
 445                                     idesc->id_number);
 446                                 getpathname(namebuf, dirp->d_ino, dirp->d_ino);
 447                                 pwarn("%s%s%s %s %s\n", pathbuf,
 448                                     (strcmp(pathbuf, "/") == 0 ? "" : "/"),
 449                                     dirp->d_name,
 450                                     "IS AN EXTRANEOUS HARD LINK TO DIRECTORY",
 451                                     namebuf);
 452                                 if (preen) {
 453                                         printf(" (REMOVED)\n");
 454                                         n = 1;
 455                                         break;
 456                                 }
 457                                 if ((n = reply("REMOVE")) == 1)
 458                                         break;
 459                         }
 460                         if (idesc->id_entryno > 2)
 461                                 inp->i_parent = idesc->id_number;
 462                         /* fall through */
 463
 464                 case FSTATE:
 465                         if (newinofmt &&
 466                             dirp->d_type != inoinfo(dirp->d_ino)->ino_type) {
 467                                 fileerror(idesc->id_number, dirp->d_ino,
 468                                     "BAD TYPE VALUE");
 469                                 dirp->d_type = inoinfo(dirp->d_ino)->ino_type;
 470                                 if (reply("FIX") == 1)
 471                                         ret |= ALTERED;
 472                         }
 473                         inoinfo(dirp->d_ino)->ino_linkcnt--;
 474                         break;
 475
 476                 default:
 477                         errx(EEXIT, "BAD STATE %d FOR INODE I=%d",
 478                             inoinfo(dirp->d_ino)->ino_state, dirp->d_ino);
 479                 }
 480         }
 481         if (n == 0)
 482                 return (ret|KEEPON);
 483         dirp->d_ino = 0;
 484         return (ret|KEEPON|ALTERED);
 485 }
 486
 487 /*
 488  * Routine to sort disk blocks.
 489  */
 490 static int
 491 blksort(const void *arg1, const void *arg2)
 492 {
 493
 494         return ((*(struct inoinfo **)arg1)->i_blks[0] -
 495                 (*(struct inoinfo **)arg2)->i_blks[0]);
 496 }