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