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