sbin/fsck_ffs/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
  30 #if 0
  31 #ifndef lint
  32 static const char sccsid[] = "@(#)pass2.c       8.9 (Berkeley) 4/28/95";
  33 #endif /* not lint */
  34 #endif
  35 #include <sys/cdefs.h>
  36 __FBSDID("$FreeBSD$");
  37
  38 #include <sys/param.h>
  39 #include <sys/sysctl.h>
  40
  41 #include <ufs/ufs/dinode.h>
  42 #include <ufs/ufs/dir.h>
  43 #include <ufs/ffs/fs.h>
  44
  45 #include <err.h>
  46 #include <errno.h>
  47 #include <stdint.h>
  48 #include <string.h>
  49
  50 #include "fsck.h"
  51
  52 #define MINDIRSIZE      (sizeof (struct dirtemplate))
  53
  54 static int fix_extraneous(struct inoinfo *, struct inodesc *);
  55 static int deleteentry(struct inodesc *);
  56 static int blksort(const void *, const void *);
  57 static int pass2check(struct inodesc *);
  58
  59 void
  60 pass2(void)
  61 {
  62         union dinode *dp;
  63         struct inoinfo **inpp, *inp;
  64         struct inoinfo **inpend;
  65         struct inodesc curino;
  66         union dinode dino;
  67         int i;
  68         char pathbuf[MAXPATHLEN + 1];
  69
  70         switch (inoinfo(UFS_ROOTINO)->ino_state) {
  71
  72         case USTATE:
  73                 pfatal("ROOT INODE UNALLOCATED");
  74                 if (reply("ALLOCATE") == 0) {
  75                         ckfini(0);
  76                         exit(EEXIT);
  77                 }
  78                 if (allocdir(UFS_ROOTINO, UFS_ROOTINO, 0755) != UFS_ROOTINO)
  79                         errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
  80                 break;
  81
  82         case DCLEAR:
  83                 pfatal("DUPS/BAD IN ROOT INODE");
  84                 if (reply("REALLOCATE")) {
  85                         freeino(UFS_ROOTINO);
  86                         if (allocdir(UFS_ROOTINO, UFS_ROOTINO, 0755) !=
  87                             UFS_ROOTINO)
  88                                 errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
  89                         break;
  90                 }
  91                 if (reply("CONTINUE") == 0) {
  92                         ckfini(0);
  93                         exit(EEXIT);
  94                 }
  95                 break;
  96
  97         case FSTATE:
  98         case FCLEAR:
  99         case FZLINK:
 100                 pfatal("ROOT INODE NOT DIRECTORY");
 101                 if (reply("REALLOCATE")) {
 102                         freeino(UFS_ROOTINO);
 103                         if (allocdir(UFS_ROOTINO, UFS_ROOTINO, 0755) !=
 104                             UFS_ROOTINO)
 105                                 errx(EEXIT, "CANNOT ALLOCATE ROOT INODE");
 106                         break;
 107                 }
 108                 if (reply("FIX") == 0) {
 109                         ckfini(0);
 110                         exit(EEXIT);
 111                 }
 112                 dp = ginode(UFS_ROOTINO);
 113                 DIP_SET(dp, di_mode, DIP(dp, di_mode) & ~IFMT);
 114                 DIP_SET(dp, di_mode, DIP(dp, di_mode) | IFDIR);
 115                 inodirty();
 116                 break;
 117
 118         case DSTATE:
 119         case DZLINK:
 120                 break;
 121
 122         default:
 123                 errx(EEXIT, "BAD STATE %d FOR ROOT INODE",
 124                     inoinfo(UFS_ROOTINO)->ino_state);
 125         }
 126         inoinfo(UFS_ROOTINO)->ino_state = DFOUND;
 127         inoinfo(UFS_WINO)->ino_state = FSTATE;
 128         inoinfo(UFS_WINO)->ino_type = DT_WHT;
 129         /*
 130          * Sort the directory list into disk block order.
 131          */
 132         qsort((char *)inpsort, (size_t)inplast, sizeof *inpsort, blksort);
 133         /*
 134          * Check the integrity of each directory.
 135          */
 136         memset(&curino, 0, sizeof(struct inodesc));
 137         curino.id_type = DATA;
 138         curino.id_func = pass2check;
 139         inpend = &inpsort[inplast];
 140         for (inpp = inpsort; inpp < inpend; inpp++) {
 141                 if (got_siginfo) {
 142                         printf("%s: phase 2: dir %td of %d (%d%%)\n", cdevname,
 143                             inpp - inpsort, (int)inplast,
 144                             (int)((inpp - inpsort) * 100 / inplast));
 145                         got_siginfo = 0;
 146                 }
 147                 if (got_sigalarm) {
 148                         setproctitle("%s p2 %d%%", cdevname,
 149                             (int)((inpp - inpsort) * 100 / inplast));
 150                         got_sigalarm = 0;
 151                 }
 152                 inp = *inpp;
 153                 if (inp->i_isize == 0)
 154                         continue;
 155                 if (inp->i_isize < MINDIRSIZE) {
 156                         direrror(inp->i_number, "DIRECTORY TOO SHORT");
 157                         inp->i_isize = roundup(MINDIRSIZE, DIRBLKSIZ);
 158                         if (reply("FIX") == 1) {
 159                                 dp = ginode(inp->i_number);
 160                                 DIP_SET(dp, di_size, inp->i_isize);
 161                                 inodirty();
 162                         }
 163                 } else if ((inp->i_isize & (DIRBLKSIZ - 1)) != 0) {
 164                         getpathname(pathbuf, inp->i_number, inp->i_number);
 165                         if (usedsoftdep)
 166                                 pfatal("%s %s: LENGTH %jd NOT MULTIPLE OF %d",
 167                                         "DIRECTORY", pathbuf,
 168                                         (intmax_t)inp->i_isize, DIRBLKSIZ);
 169                         else
 170                                 pwarn("%s %s: LENGTH %jd NOT MULTIPLE OF %d",
 171                                         "DIRECTORY", pathbuf,
 172                                         (intmax_t)inp->i_isize, DIRBLKSIZ);
 173                         if (preen)
 174                                 printf(" (ADJUSTED)\n");
 175                         inp->i_isize = roundup(inp->i_isize, DIRBLKSIZ);
 176                         if (preen || reply("ADJUST") == 1) {
 177                                 dp = ginode(inp->i_number);
 178                                 DIP_SET(dp, di_size,
 179                                     roundup(inp->i_isize, DIRBLKSIZ));
 180                                 inodirty();
 181                         }
 182                 }
 183                 dp = &dino;
 184                 memset(dp, 0, sizeof(struct ufs2_dinode));
 185                 DIP_SET(dp, di_mode, IFDIR);
 186                 DIP_SET(dp, di_size, inp->i_isize);
 187                 for (i = 0; i < MIN(inp->i_numblks, UFS_NDADDR); i++)
 188                         DIP_SET(dp, di_db[i], inp->i_blks[i]);
 189                 if (inp->i_numblks > UFS_NDADDR)
 190                         for (i = 0; i < UFS_NIADDR; i++)
 191                                 DIP_SET(dp, di_ib[i],
 192                                     inp->i_blks[UFS_NDADDR + i]);
 193                 curino.id_number = inp->i_number;
 194                 curino.id_parent = inp->i_parent;
 195                 (void)ckinode(dp, &curino);
 196         }
 197         /*
 198          * Now that the parents of all directories have been found,
 199          * make another pass to verify the value of `..'
 200          */
 201         for (inpp = inpsort; inpp < inpend; inpp++) {
 202                 inp = *inpp;
 203                 if (inp->i_parent == 0 || inp->i_isize == 0)
 204                         continue;
 205                 if (inoinfo(inp->i_parent)->ino_state == DFOUND &&
 206                     INO_IS_DUNFOUND(inp->i_number))
 207                         inoinfo(inp->i_number)->ino_state = DFOUND;
 208                 if (inp->i_dotdot == inp->i_parent ||
 209                     inp->i_dotdot == (ino_t)-1)
 210                         continue;
 211                 if (inp->i_dotdot == 0) {
 212                         inp->i_dotdot = inp->i_parent;
 213                         fileerror(inp->i_parent, inp->i_number, "MISSING '..'");
 214                         if (reply("FIX") == 0)
 215                                 continue;
 216                         (void)makeentry(inp->i_number, inp->i_parent, "..");
 217                         inoinfo(inp->i_parent)->ino_linkcnt--;
 218                         continue;
 219                 }
 220                 /*
 221                  * Here we have:
 222                  *    inp->i_number is directory with bad ".." in it.
 223                  *    inp->i_dotdot is current value of "..".
 224                  *    inp->i_parent is directory to which ".." should point.
 225                  */
 226                 getpathname(pathbuf, inp->i_parent, inp->i_number);
 227                 printf("BAD INODE NUMBER FOR '..' in DIR I=%ju (%s)\n",
 228                     (uintmax_t)inp->i_number, pathbuf);
 229                 getpathname(pathbuf, inp->i_dotdot, inp->i_dotdot);
 230                 printf("CURRENTLY POINTS TO I=%ju (%s), ",
 231                     (uintmax_t)inp->i_dotdot, pathbuf);
 232                 getpathname(pathbuf, inp->i_parent, inp->i_parent);
 233                 printf("SHOULD POINT TO I=%ju (%s)",
 234                     (uintmax_t)inp->i_parent, pathbuf);
 235                 if (cursnapshot != 0) {
 236                         /*
 237                          * We need to:
 238                          *    setcwd(inp->i_number);
 239                          *    setdotdot(inp->i_dotdot, inp->i_parent);
 240                          */
 241                         cmd.value = inp->i_number;
 242                         if (sysctlbyname("vfs.ffs.setcwd", 0, 0,
 243                             &cmd, sizeof cmd) == -1) {
 244                                 /* kernel lacks support for these functions */
 245                                 printf(" (IGNORED)\n");
 246                                 continue;
 247                         }
 248                         cmd.value = inp->i_dotdot; /* verify same value */
 249                         cmd.size = inp->i_parent;  /* new parent */
 250                         if (sysctlbyname("vfs.ffs.setdotdot", 0, 0,
 251                             &cmd, sizeof cmd) == -1) {
 252                                 printf(" (FIX FAILED: %s)\n", strerror(errno));
 253                                 continue;
 254                         }
 255                         printf(" (FIXED)\n");
 256                         inoinfo(inp->i_parent)->ino_linkcnt--;
 257                         inp->i_dotdot = inp->i_parent;
 258                         continue;
 259                 }
 260                 if (preen)
 261                         printf(" (FIXED)\n");
 262                 else if (reply("FIX") == 0)
 263                         continue;
 264                 inoinfo(inp->i_dotdot)->ino_linkcnt++;
 265                 inoinfo(inp->i_parent)->ino_linkcnt--;
 266                 inp->i_dotdot = inp->i_parent;
 267                 (void)changeino(inp->i_number, "..", inp->i_parent);
 268         }
 269         /*
 270          * Mark all the directories that can be found from the root.
 271          */
 272         propagate();
 273 }
 274
 275 static int
 276 pass2check(struct inodesc *idesc)
 277 {
 278         struct direct *dirp = idesc->id_dirp;
 279         char dirname[MAXPATHLEN + 1];
 280         struct inoinfo *inp;
 281         int n, entrysize, ret = 0;
 282         union dinode *dp;
 283         const char *errmsg;
 284         struct direct proto;
 285
 286         /*
 287          * check for "."
 288          */
 289         if (dirp->d_ino > maxino)
 290                 goto chk2;
 291         if (idesc->id_entryno != 0)
 292                 goto chk1;
 293         if (dirp->d_ino != 0 && strcmp(dirp->d_name, ".") == 0) {
 294                 if (dirp->d_ino != idesc->id_number) {
 295                         direrror(idesc->id_number, "BAD INODE NUMBER FOR '.'");
 296                         dirp->d_ino = idesc->id_number;
 297                         if (reply("FIX") == 1)
 298                                 ret |= ALTERED;
 299                 }
 300                 if (dirp->d_type != DT_DIR) {
 301                         direrror(idesc->id_number, "BAD TYPE VALUE FOR '.'");
 302                         dirp->d_type = DT_DIR;
 303                         if (reply("FIX") == 1)
 304                                 ret |= ALTERED;
 305                 }
 306                 goto chk1;
 307         }
 308         direrror(idesc->id_number, "MISSING '.'");
 309         proto.d_ino = idesc->id_number;
 310         proto.d_type = DT_DIR;
 311         proto.d_namlen = 1;
 312         (void)strcpy(proto.d_name, ".");
 313         entrysize = DIRSIZ(0, &proto);
 314         if (dirp->d_ino != 0 && strcmp(dirp->d_name, "..") != 0) {
 315                 pfatal("CANNOT FIX, FIRST ENTRY IN DIRECTORY CONTAINS %s\n",
 316                         dirp->d_name);
 317         } else if (dirp->d_reclen < entrysize) {
 318                 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '.'\n");
 319         } else if (dirp->d_reclen < 2 * entrysize) {
 320                 proto.d_reclen = dirp->d_reclen;
 321                 memmove(dirp, &proto, (size_t)entrysize);
 322                 if (reply("FIX") == 1)
 323                         ret |= ALTERED;
 324         } else {
 325                 n = dirp->d_reclen - entrysize;
 326                 proto.d_reclen = entrysize;
 327                 memmove(dirp, &proto, (size_t)entrysize);
 328                 idesc->id_entryno++;
 329                 inoinfo(dirp->d_ino)->ino_linkcnt--;
 330                 dirp = (struct direct *)((char *)(dirp) + entrysize);
 331                 memset(dirp, 0, (size_t)n);
 332                 dirp->d_reclen = n;
 333                 if (reply("FIX") == 1)
 334                         ret |= ALTERED;
 335         }
 336 chk1:
 337         if (idesc->id_entryno > 1)
 338                 goto chk2;
 339         inp = getinoinfo(idesc->id_number);
 340         proto.d_ino = inp->i_parent;
 341         proto.d_type = DT_DIR;
 342         proto.d_namlen = 2;
 343         (void)strcpy(proto.d_name, "..");
 344         entrysize = DIRSIZ(0, &proto);
 345         if (idesc->id_entryno == 0) {
 346                 n = DIRSIZ(0, dirp);
 347                 if (dirp->d_reclen < n + entrysize)
 348                         goto chk2;
 349                 proto.d_reclen = dirp->d_reclen - n;
 350                 dirp->d_reclen = n;
 351                 idesc->id_entryno++;
 352                 inoinfo(dirp->d_ino)->ino_linkcnt--;
 353                 dirp = (struct direct *)((char *)(dirp) + n);
 354                 memset(dirp, 0, (size_t)proto.d_reclen);
 355                 dirp->d_reclen = proto.d_reclen;
 356         }
 357         if (dirp->d_ino != 0 && strcmp(dirp->d_name, "..") == 0) {
 358                 inp->i_dotdot = dirp->d_ino;
 359                 if (dirp->d_type != DT_DIR) {
 360                         direrror(idesc->id_number, "BAD TYPE VALUE FOR '..'");
 361                         dirp->d_type = DT_DIR;
 362                         if (reply("FIX") == 1)
 363                                 ret |= ALTERED;
 364                 }
 365                 goto chk2;
 366         }
 367         if (dirp->d_ino != 0 && strcmp(dirp->d_name, ".") != 0) {
 368                 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
 369                 pfatal("CANNOT FIX, SECOND ENTRY IN DIRECTORY CONTAINS %s\n",
 370                         dirp->d_name);
 371                 inp->i_dotdot = (ino_t)-1;
 372         } else if (dirp->d_reclen < entrysize) {
 373                 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
 374                 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '..'\n");
 375                 inp->i_dotdot = (ino_t)-1;
 376         } else if (inp->i_parent != 0) {
 377                 /*
 378                  * We know the parent, so fix now.
 379                  */
 380                 inp->i_dotdot = inp->i_parent;
 381                 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'");
 382                 proto.d_reclen = dirp->d_reclen;
 383                 memmove(dirp, &proto, (size_t)entrysize);
 384                 if (reply("FIX") == 1)
 385                         ret |= ALTERED;
 386         }
 387         idesc->id_entryno++;
 388         if (dirp->d_ino != 0)
 389                 inoinfo(dirp->d_ino)->ino_linkcnt--;
 390         return (ret|KEEPON);
 391 chk2:
 392         if (dirp->d_ino == 0)
 393                 return (ret|KEEPON);
 394         if (dirp->d_namlen <= 2 &&
 395             dirp->d_name[0] == '.' &&
 396             idesc->id_entryno >= 2) {
 397                 if (dirp->d_namlen == 1) {
 398                         direrror(idesc->id_number, "EXTRA '.' ENTRY");
 399                         dirp->d_ino = 0;
 400                         if (reply("FIX") == 1)
 401                                 ret |= ALTERED;
 402                         return (KEEPON | ret);
 403                 }
 404                 if (dirp->d_name[1] == '.') {
 405                         direrror(idesc->id_number, "EXTRA '..' ENTRY");
 406                         dirp->d_ino = 0;
 407                         if (reply("FIX") == 1)
 408                                 ret |= ALTERED;
 409                         return (KEEPON | ret);
 410                 }
 411         }
 412         idesc->id_entryno++;
 413         n = 0;
 414         if (dirp->d_ino > maxino) {
 415                 fileerror(idesc->id_number, dirp->d_ino, "I OUT OF RANGE");
 416                 n = reply("REMOVE");
 417         } else if (((dirp->d_ino == UFS_WINO && dirp->d_type != DT_WHT) ||
 418                     (dirp->d_ino != UFS_WINO && dirp->d_type == DT_WHT))) {
 419                 fileerror(idesc->id_number, dirp->d_ino, "BAD WHITEOUT ENTRY");
 420                 dirp->d_ino = UFS_WINO;
 421                 dirp->d_type = DT_WHT;
 422                 if (reply("FIX") == 1)
 423                         ret |= ALTERED;
 424         } else {
 425 again:
 426                 switch (inoinfo(dirp->d_ino)->ino_state) {
 427                 case USTATE:
 428                         if (idesc->id_entryno <= 2)
 429                                 break;
 430                         fileerror(idesc->id_number, dirp->d_ino, "UNALLOCATED");
 431                         n = reply("REMOVE");
 432                         break;
 433
 434                 case DCLEAR:
 435                 case FCLEAR:
 436                         if (idesc->id_entryno <= 2)
 437                                 break;
 438                         if (inoinfo(dirp->d_ino)->ino_state == FCLEAR)
 439                                 errmsg = "DUP/BAD";
 440                         else if (!preen && !usedsoftdep)
 441                                 errmsg = "ZERO LENGTH DIRECTORY";
 442                         else if (cursnapshot == 0) {
 443                                 n = 1;
 444                                 break;
 445                         } else {
 446                                 getpathname(dirname, idesc->id_number,
 447                                     dirp->d_ino);
 448                                 pwarn("ZERO LENGTH DIRECTORY %s I=%ju",
 449                                     dirname, (uintmax_t)dirp->d_ino);
 450                                 /*
 451                                  * We need to:
 452                                  *    setcwd(idesc->id_parent);
 453                                  *    rmdir(dirp->d_name);
 454                                  */
 455                                 cmd.value = idesc->id_number;
 456                                 if (sysctlbyname("vfs.ffs.setcwd", 0, 0,
 457                                     &cmd, sizeof cmd) == -1) {
 458                                         /* kernel lacks support */
 459                                         printf(" (IGNORED)\n");
 460                                         n = 1;
 461                                         break;
 462                                 }
 463                                 if (rmdir(dirp->d_name) == -1) {
 464                                         printf(" (REMOVAL FAILED: %s)\n",
 465                                             strerror(errno));
 466                                         n = 1;
 467                                         break;
 468                                 }
 469                                 /* ".." reference to parent is removed */
 470                                 inoinfo(idesc->id_number)->ino_linkcnt--;
 471                                 printf(" (REMOVED)\n");
 472                                 break;
 473                         }
 474                         fileerror(idesc->id_number, dirp->d_ino, errmsg);
 475                         if ((n = reply("REMOVE")) == 1)
 476                                 break;
 477                         dp = ginode(dirp->d_ino);
 478                         inoinfo(dirp->d_ino)->ino_state =
 479                            (DIP(dp, di_mode) & IFMT) == IFDIR ? DSTATE : FSTATE;
 480                         inoinfo(dirp->d_ino)->ino_linkcnt = DIP(dp, di_nlink);
 481                         goto again;
 482
 483                 case DSTATE:
 484                 case DZLINK:
 485                         if (inoinfo(idesc->id_number)->ino_state == DFOUND)
 486                                 inoinfo(dirp->d_ino)->ino_state = DFOUND;
 487                         /* FALLTHROUGH */
 488
 489                 case DFOUND:
 490                         inp = getinoinfo(dirp->d_ino);
 491                         if (idesc->id_entryno > 2) {
 492                                 if (inp->i_parent == 0)
 493                                         inp->i_parent = idesc->id_number;
 494                                 else if ((n = fix_extraneous(inp, idesc)) == 1)
 495                                         break;
 496                         }
 497                         /* FALLTHROUGH */
 498
 499                 case FSTATE:
 500                 case FZLINK:
 501                         if (dirp->d_type != inoinfo(dirp->d_ino)->ino_type) {
 502                                 fileerror(idesc->id_number, dirp->d_ino,
 503                                     "BAD TYPE VALUE");
 504                                 dirp->d_type = inoinfo(dirp->d_ino)->ino_type;
 505                                 if (reply("FIX") == 1)
 506                                         ret |= ALTERED;
 507                         }
 508                         inoinfo(dirp->d_ino)->ino_linkcnt--;
 509                         break;
 510
 511                 default:
 512                         errx(EEXIT, "BAD STATE %d FOR INODE I=%ju",
 513                             inoinfo(dirp->d_ino)->ino_state,
 514                             (uintmax_t)dirp->d_ino);
 515                 }
 516         }
 517         if (n == 0)
 518                 return (ret|KEEPON);
 519         dirp->d_ino = 0;
 520         return (ret|KEEPON|ALTERED);
 521 }
 522
 523 static int
 524 fix_extraneous(struct inoinfo *inp, struct inodesc *idesc)
 525 {
 526         char *cp;
 527         struct inodesc dotdesc;
 528         char oldname[MAXPATHLEN + 1];
 529         char newname[MAXPATHLEN + 1];
 530
 531         /*
 532          * If we have not yet found "..", look it up now so we know
 533          * which inode the directory itself believes is its parent.
 534          */
 535         if (inp->i_dotdot == 0) {
 536                 memset(&dotdesc, 0, sizeof(struct inodesc));
 537                 dotdesc.id_type = DATA;
 538                 dotdesc.id_number = idesc->id_dirp->d_ino;
 539                 dotdesc.id_func = findino;
 540                 dotdesc.id_name = strdup("..");
 541                 if ((ckinode(ginode(dotdesc.id_number), &dotdesc) & FOUND))
 542                         inp->i_dotdot = dotdesc.id_parent;
 543         }
 544         /*
 545          * We have the previously found old name (inp->i_parent) and the
 546          * just found new name (idesc->id_number). We have five cases:
 547          * 1)  ".." is missing - can remove either name, choose to delete
 548          *     new one and let fsck create ".." pointing to old name.
 549          * 2) Both new and old are in same directory, choose to delete
 550          *    the new name and let fsck fix ".." if it is wrong.
 551          * 3) ".." does not point to the new name, so delete it and let
 552          *    fsck fix ".." to point to the old one if it is wrong.
 553          * 4) ".." points to the old name only, so delete the new one.
 554          * 5) ".." points to the new name only, so delete the old one.
 555          *
 556          * For cases 1-4 we eliminate the new name;
 557          * for case 5 we eliminate the old name.
 558          */
 559         if (inp->i_dotdot == 0 ||                   /* Case 1 */
 560             idesc->id_number == inp->i_parent ||    /* Case 2 */
 561             inp->i_dotdot != idesc->id_number ||    /* Case 3 */
 562             inp->i_dotdot == inp->i_parent) {       /* Case 4 */
 563                 getpathname(newname, idesc->id_number, idesc->id_number);
 564                 if (strcmp(newname, "/") != 0)
 565                         strcat (newname, "/");
 566                 strcat(newname, idesc->id_dirp->d_name);
 567                 getpathname(oldname, inp->i_number, inp->i_number);
 568                 pwarn("%s IS AN EXTRANEOUS HARD LINK TO DIRECTORY %s",
 569                     newname, oldname);
 570                 if (cursnapshot != 0) {
 571                         /*
 572                          * We need to
 573                          *    setcwd(idesc->id_number);
 574                          *    unlink(idesc->id_dirp->d_name);
 575                          */
 576                         cmd.value = idesc->id_number;
 577                         if (sysctlbyname("vfs.ffs.setcwd", 0, 0,
 578                             &cmd, sizeof cmd) == -1) {
 579                                 printf(" (IGNORED)\n");
 580                                 return (0);
 581                         }
 582                         cmd.value = (intptr_t)idesc->id_dirp->d_name;
 583                         cmd.size = inp->i_number; /* verify same name */
 584                         if (sysctlbyname("vfs.ffs.unlink", 0, 0,
 585                             &cmd, sizeof cmd) == -1) {
 586                                 printf(" (UNLINK FAILED: %s)\n",
 587                                     strerror(errno));
 588                                 return (0);
 589                         }
 590                         printf(" (REMOVED)\n");
 591                         return (0);
 592                 }
 593                 if (preen) {
 594                         printf(" (REMOVED)\n");
 595                         return (1);
 596                 }
 597                 return (reply("REMOVE"));
 598         }
 599         /*
 600          * None of the first four cases above, so must be case (5).
 601          * Eliminate the old name and make the new the name the parent.
 602          */
 603         getpathname(oldname, inp->i_parent, inp->i_number);
 604         getpathname(newname, inp->i_number, inp->i_number);
 605         pwarn("%s IS AN EXTRANEOUS HARD LINK TO DIRECTORY %s", oldname,
 606             newname);
 607         if (cursnapshot != 0) {
 608                 /*
 609                  * We need to
 610                  *    setcwd(inp->i_parent);
 611                  *    unlink(last component of oldname pathname);
 612                  */
 613                 cmd.value = inp->i_parent;
 614                 if (sysctlbyname("vfs.ffs.setcwd", 0, 0,
 615                     &cmd, sizeof cmd) == -1) {
 616                         printf(" (IGNORED)\n");
 617                         return (0);
 618                 }
 619                 if ((cp = strchr(oldname, '/')) == NULL) {
 620                         printf(" (IGNORED)\n");
 621                         return (0);
 622                 }
 623                 cmd.value = (intptr_t)(cp + 1);
 624                 cmd.size = inp->i_number; /* verify same name */
 625                 if (sysctlbyname("vfs.ffs.unlink", 0, 0,
 626                     &cmd, sizeof cmd) == -1) {
 627                         printf(" (UNLINK FAILED: %s)\n",
 628                             strerror(errno));
 629                         return (0);
 630                 }
 631                 printf(" (REMOVED)\n");
 632                 inp->i_parent = idesc->id_number;  /* reparent to correct dir */
 633                 return (0);
 634         }
 635         if (!preen && !reply("REMOVE"))
 636                 return (0);
 637         memset(&dotdesc, 0, sizeof(struct inodesc));
 638         dotdesc.id_type = DATA;
 639         dotdesc.id_number = inp->i_parent; /* directory in which name appears */
 640         dotdesc.id_parent = inp->i_number; /* inode number in entry to delete */
 641         dotdesc.id_func = deleteentry;
 642         if ((ckinode(ginode(dotdesc.id_number), &dotdesc) & FOUND) && preen)
 643                 printf(" (REMOVED)\n");
 644         inp->i_parent = idesc->id_number;  /* reparent to correct directory */
 645         inoinfo(inp->i_number)->ino_linkcnt++; /* name gone, return reference */
 646         return (0);
 647 }
 648
 649 static int
 650 deleteentry(struct inodesc *idesc)
 651 {
 652         struct direct *dirp = idesc->id_dirp;
 653
 654         if (idesc->id_entryno++ < 2 || dirp->d_ino != idesc->id_parent)
 655                 return (KEEPON);
 656         dirp->d_ino = 0;
 657         return (ALTERED|STOP|FOUND);
 658 }
 659
 660 /*
 661  * Routine to sort disk blocks.
 662  */
 663 static int
 664 blksort(const void *arg1, const void *arg2)
 665 {
 666
 667         return ((*(struct inoinfo * const *)arg1)->i_blks[0] -
 668                 (*(struct inoinfo * const *)arg2)->i_blks[0]);
 669 }