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