1 /* $NetBSD: pass2.c,v 1.13 2005/06/26 23:01:39 christos 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.13 2005/06/26 23:01:39 christos 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 86 #define MINDIRSIZE (sizeof (struct ext2fs_dirtemplate)) 87 88 static int pass2check(struct inodesc *); 89 static int blksort(const void *, const void *); 90 91 void 92 pass2(void) 93 { 94 struct ext2fs_dinode *dp; 95 struct inoinfo **inpp, *inp; 96 struct inoinfo **inpend; 97 struct inodesc curino; 98 struct ext2fs_dinode dino; 99 char pathbuf[MAXPATHLEN + 1]; 100 101 switch (statemap[EXT2_ROOTINO]) { 102 103 case USTATE: 104 pfatal("ROOT INODE UNALLOCATED"); 105 if (reply("ALLOCATE") == 0) 106 errexit("%s\n", ""); 107 if (allocdir(EXT2_ROOTINO, EXT2_ROOTINO, 0755) != EXT2_ROOTINO) 108 errexit("CANNOT ALLOCATE ROOT INODE\n"); 109 break; 110 111 case DCLEAR: 112 pfatal("DUPS/BAD IN ROOT INODE"); 113 if (reply("REALLOCATE")) { 114 freeino(EXT2_ROOTINO); 115 if (allocdir(EXT2_ROOTINO, EXT2_ROOTINO, 0755) != EXT2_ROOTINO) 116 errexit("CANNOT ALLOCATE ROOT INODE\n"); 117 break; 118 } 119 if (reply("CONTINUE") == 0) 120 errexit("%s\n", ""); 121 break; 122 123 case FSTATE: 124 case FCLEAR: 125 pfatal("ROOT INODE NOT DIRECTORY"); 126 if (reply("REALLOCATE")) { 127 freeino(EXT2_ROOTINO); 128 if (allocdir(EXT2_ROOTINO, EXT2_ROOTINO, 0755) != EXT2_ROOTINO) 129 errexit("CANNOT ALLOCATE ROOT INODE\n"); 130 break; 131 } 132 if (reply("FIX") == 0) 133 errexit("%s\n", ""); 134 dp = ginode(EXT2_ROOTINO); 135 dp->e2di_mode = h2fs16((fs2h16(dp->e2di_mode) & ~IFMT) | IFDIR); 136 inodirty(); 137 break; 138 139 case DSTATE: 140 break; 141 142 default: 143 errexit("BAD STATE %d FOR ROOT INODE\n", statemap[EXT2_ROOTINO]); 144 } 145 146 /* 147 * Sort the directory list into disk block order. 148 */ 149 qsort((char *)inpsort, (size_t)inplast, sizeof *inpsort, blksort); 150 /* 151 * Check the integrity of each directory. 152 */ 153 memset(&curino, 0, sizeof(struct inodesc)); 154 curino.id_type = DATA; 155 curino.id_func = pass2check; 156 inpend = &inpsort[inplast]; 157 for (inpp = inpsort; inpp < inpend; inpp++) { 158 inp = *inpp; 159 if (inp->i_isize == 0) 160 continue; 161 if (inp->i_isize < MINDIRSIZE) { 162 direrror(inp->i_number, "DIRECTORY TOO SHORT"); 163 inp->i_isize = roundup(MINDIRSIZE, sblock.e2fs_bsize); 164 if (reply("FIX") == 1) { 165 dp = ginode(inp->i_number); 166 inossize(dp, inp->i_isize); 167 inodirty(); 168 } 169 } else if ((inp->i_isize & (sblock.e2fs_bsize - 1)) != 0) { 170 getpathname(pathbuf, sizeof(pathbuf), inp->i_number, 171 inp->i_number); 172 pwarn("DIRECTORY %s: LENGTH %lu NOT MULTIPLE OF %d", 173 pathbuf, (u_long)inp->i_isize, sblock.e2fs_bsize); 174 if (preen) 175 printf(" (ADJUSTED)\n"); 176 inp->i_isize = roundup(inp->i_isize, sblock.e2fs_bsize); 177 if (preen || reply("ADJUST") == 1) { 178 dp = ginode(inp->i_number); 179 inossize(dp, inp->i_isize); 180 inodirty(); 181 } 182 } 183 memset(&dino, 0, sizeof(struct ext2fs_dinode)); 184 dino.e2di_mode = h2fs16(IFDIR); 185 inossize(&dino, inp->i_isize); 186 memcpy(&dino.e2di_blocks[0], &inp->i_blks[0], (size_t)inp->i_numblks); 187 curino.id_number = inp->i_number; 188 curino.id_parent = inp->i_parent; 189 (void)ckinode(&dino, &curino); 190 } 191 /* 192 * Now that the parents of all directories have been found, 193 * make another pass to verify the value of `..' 194 */ 195 for (inpp = inpsort; inpp < inpend; inpp++) { 196 inp = *inpp; 197 if (inp->i_parent == 0 || inp->i_isize == 0) 198 continue; 199 if (inp->i_dotdot == inp->i_parent || 200 inp->i_dotdot == (ino_t)-1) 201 continue; 202 if (inp->i_dotdot == 0) { 203 inp->i_dotdot = inp->i_parent; 204 fileerror(inp->i_parent, inp->i_number, "MISSING '..'"); 205 if (reply("FIX") == 0) 206 continue; 207 (void)makeentry(inp->i_number, inp->i_parent, ".."); 208 lncntp[inp->i_parent]--; 209 continue; 210 } 211 fileerror(inp->i_parent, inp->i_number, 212 "BAD INODE NUMBER FOR '..'"); 213 if (reply("FIX") == 0) 214 continue; 215 lncntp[inp->i_dotdot]++; 216 lncntp[inp->i_parent]--; 217 inp->i_dotdot = inp->i_parent; 218 (void)changeino(inp->i_number, "..", inp->i_parent); 219 } 220 /* 221 * Mark all the directories that can be found from the root. 222 */ 223 propagate(); 224 } 225 226 static int 227 pass2check(struct inodesc *idesc) 228 { 229 struct ext2fs_direct *dirp = idesc->id_dirp; 230 struct inoinfo *inp; 231 int n, entrysize, ret = 0; 232 struct ext2fs_dinode *dp; 233 const char *errmsg; 234 struct ext2fs_direct proto; 235 char namebuf[MAXPATHLEN + 1]; 236 char pathbuf[MAXPATHLEN + 1]; 237 238 /* 239 * check for "." 240 */ 241 if (idesc->id_entryno != 0) 242 goto chk1; 243 if (fs2h32(dirp->e2d_ino) != 0 && dirp->e2d_namlen == 1 && 244 dirp->e2d_name[0] == '.') { 245 if (fs2h32(dirp->e2d_ino) != idesc->id_number) { 246 direrror(idesc->id_number, "BAD INODE NUMBER FOR '.'"); 247 dirp->e2d_ino = h2fs32(idesc->id_number); 248 if (reply("FIX") == 1) 249 ret |= ALTERED; 250 } 251 if (sblock.e2fs.e2fs_rev > E2FS_REV0 && 252 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE) 253 && (dirp->e2d_type != EXT2_FT_DIR)) { 254 direrror(idesc->id_number, "BAD TYPE VALUE FOR '.'"); 255 dirp->e2d_type = EXT2_FT_DIR; 256 if (reply("FIX") == 1) 257 ret |= ALTERED; 258 } 259 goto chk1; 260 } 261 direrror(idesc->id_number, "MISSING '.'"); 262 proto.e2d_ino = h2fs32(idesc->id_number); 263 proto.e2d_namlen = 1; 264 if (sblock.e2fs.e2fs_rev > E2FS_REV0 && 265 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE)) 266 proto.e2d_type = EXT2_FT_DIR; 267 else 268 proto.e2d_type = 0; 269 (void)strlcpy(proto.e2d_name, ".", sizeof(proto.e2d_name)); 270 entrysize = EXT2FS_DIRSIZ(proto.e2d_namlen); 271 if (fs2h32(dirp->e2d_ino) != 0 && strcmp(dirp->e2d_name, "..") != 0) { 272 pfatal("CANNOT FIX, FIRST ENTRY IN DIRECTORY CONTAINS %s\n", 273 dirp->e2d_name); 274 } else if (fs2h16(dirp->e2d_reclen) < entrysize) { 275 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '.'\n"); 276 } else if (fs2h16(dirp->e2d_reclen) < 2 * entrysize) { 277 proto.e2d_reclen = dirp->e2d_reclen; 278 memcpy(dirp, &proto, (size_t)entrysize); 279 if (reply("FIX") == 1) 280 ret |= ALTERED; 281 } else { 282 n = fs2h16(dirp->e2d_reclen) - entrysize; 283 proto.e2d_reclen = h2fs16(entrysize); 284 memcpy(dirp, &proto, (size_t)entrysize); 285 idesc->id_entryno++; 286 lncntp[fs2h32(dirp->e2d_ino)]--; 287 dirp = (struct ext2fs_direct *)((char *)(dirp) + entrysize); 288 memset(dirp, 0, (size_t)n); 289 dirp->e2d_reclen = h2fs16(n); 290 if (reply("FIX") == 1) 291 ret |= ALTERED; 292 } 293 chk1: 294 if (idesc->id_entryno > 1) 295 goto chk2; 296 inp = getinoinfo(idesc->id_number); 297 proto.e2d_ino = h2fs32(inp->i_parent); 298 proto.e2d_namlen = 2; 299 if (sblock.e2fs.e2fs_rev > E2FS_REV0 && 300 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE)) 301 proto.e2d_type = EXT2_FT_DIR; 302 else 303 proto.e2d_type = 0; 304 (void)strlcpy(proto.e2d_name, "..", sizeof(proto.e2d_name)); 305 entrysize = EXT2FS_DIRSIZ(2); 306 if (idesc->id_entryno == 0) { 307 n = EXT2FS_DIRSIZ(dirp->e2d_namlen); 308 if (fs2h16(dirp->e2d_reclen) < n + entrysize) 309 goto chk2; 310 proto.e2d_reclen = h2fs16(fs2h16(dirp->e2d_reclen) - n); 311 dirp->e2d_reclen = h2fs16(n); 312 idesc->id_entryno++; 313 lncntp[fs2h32(dirp->e2d_ino)]--; 314 dirp = (struct ext2fs_direct *)((char *)(dirp) + n); 315 memset(dirp, 0, (size_t)fs2h16(proto.e2d_reclen)); 316 dirp->e2d_reclen = proto.e2d_reclen; 317 } 318 if (fs2h32(dirp->e2d_ino) != 0 && 319 dirp->e2d_namlen == 2 && 320 strncmp(dirp->e2d_name, "..", 2) == 0) { 321 inp->i_dotdot = fs2h32(dirp->e2d_ino); 322 if (sblock.e2fs.e2fs_rev > E2FS_REV0 && 323 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE) 324 && dirp->e2d_type != EXT2_FT_DIR) { 325 direrror(idesc->id_number, "BAD TYPE VALUE FOR '..'"); 326 dirp->e2d_type = EXT2_FT_DIR; 327 if (reply("FIX") == 1) 328 ret |= ALTERED; 329 } 330 goto chk2; 331 } 332 if (fs2h32(dirp->e2d_ino) != 0 && 333 dirp->e2d_namlen == 1 && 334 strncmp(dirp->e2d_name, ".", 1) != 0) { 335 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'"); 336 pfatal("CANNOT FIX, SECOND ENTRY IN DIRECTORY CONTAINS %s\n", 337 dirp->e2d_name); 338 inp->i_dotdot = (ino_t)-1; 339 } else if (fs2h16(dirp->e2d_reclen) < entrysize) { 340 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'"); 341 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '..'\n"); 342 inp->i_dotdot = (ino_t)-1; 343 } else if (inp->i_parent != 0) { 344 /* 345 * We know the parent, so fix now. 346 */ 347 inp->i_dotdot = inp->i_parent; 348 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'"); 349 proto.e2d_reclen = dirp->e2d_reclen; 350 memcpy(dirp, &proto, (size_t)entrysize); 351 if (reply("FIX") == 1) 352 ret |= ALTERED; 353 } 354 idesc->id_entryno++; 355 if (fs2h32(dirp->e2d_ino) != 0) 356 lncntp[fs2h32(dirp->e2d_ino)]--; 357 return (ret|KEEPON); 358 chk2: 359 if (fs2h32(dirp->e2d_ino) == 0) 360 return (ret|KEEPON); 361 if (dirp->e2d_namlen <= 2 && 362 dirp->e2d_name[0] == '.' && 363 idesc->id_entryno >= 2) { 364 if (dirp->e2d_namlen == 1) { 365 direrror(idesc->id_number, "EXTRA '.' ENTRY"); 366 dirp->e2d_ino = 0; 367 if (reply("FIX") == 1) 368 ret |= ALTERED; 369 return (KEEPON | ret); 370 } 371 if (dirp->e2d_name[1] == '.') { 372 direrror(idesc->id_number, "EXTRA '..' ENTRY"); 373 dirp->e2d_ino = 0; 374 if (reply("FIX") == 1) 375 ret |= ALTERED; 376 return (KEEPON | ret); 377 } 378 } 379 idesc->id_entryno++; 380 n = 0; 381 if (fs2h32(dirp->e2d_ino) > maxino || 382 (fs2h32(dirp->e2d_ino) < EXT2_FIRSTINO && 383 fs2h32(dirp->e2d_ino) != EXT2_ROOTINO)) { 384 fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), "I OUT OF RANGE"); 385 n = reply("REMOVE"); 386 } else { 387 again: 388 switch (statemap[fs2h32(dirp->e2d_ino)]) { 389 case USTATE: 390 if (idesc->id_entryno <= 2) 391 break; 392 fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), "UNALLOCATED"); 393 n = reply("REMOVE"); 394 break; 395 396 case DCLEAR: 397 case FCLEAR: 398 if (idesc->id_entryno <= 2) 399 break; 400 if (statemap[fs2h32(dirp->e2d_ino)] == FCLEAR) 401 errmsg = "DUP/BAD"; 402 else if (!preen) 403 errmsg = "ZERO LENGTH DIRECTORY"; 404 else { 405 n = 1; 406 break; 407 } 408 fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), errmsg); 409 if ((n = reply("REMOVE")) == 1) 410 break; 411 dp = ginode(fs2h32(dirp->e2d_ino)); 412 statemap[fs2h32(dirp->e2d_ino)] = 413 (fs2h16(dp->e2di_mode) & IFMT) == IFDIR ? DSTATE : FSTATE; 414 lncntp[fs2h32(dirp->e2d_ino)] = fs2h16(dp->e2di_nlink); 415 goto again; 416 417 case DSTATE: 418 case DFOUND: 419 inp = getinoinfo(fs2h32(dirp->e2d_ino)); 420 if (inp->i_parent != 0 && idesc->id_entryno > 2) { 421 getpathname(pathbuf, sizeof(pathbuf), 422 idesc->id_number, idesc->id_number); 423 getpathname(namebuf, sizeof(namebuf), 424 fs2h32(dirp->e2d_ino), 425 fs2h32(dirp->e2d_ino)); 426 pwarn("%s %s %s\n", pathbuf, 427 "IS AN EXTRANEOUS HARD LINK TO DIRECTORY", 428 namebuf); 429 if (preen) 430 printf(" (IGNORED)\n"); 431 else if ((n = reply("REMOVE")) == 1) 432 break; 433 } 434 if (idesc->id_entryno > 2) 435 inp->i_parent = idesc->id_number; 436 /* fall through */ 437 438 case FSTATE: 439 if (sblock.e2fs.e2fs_rev > E2FS_REV0 && 440 (sblock.e2fs.e2fs_features_incompat & 441 EXT2F_INCOMPAT_FTYPE) && 442 dirp->e2d_type != 443 inot2ext2dt(typemap[fs2h32(dirp->e2d_ino)])) { 444 dirp->e2d_type = 445 inot2ext2dt(typemap[fs2h32(dirp->e2d_ino)]); 446 fileerror(idesc->id_number, 447 fs2h32(dirp->e2d_ino), 448 "BAD TYPE VALUE"); 449 if (reply("FIX") == 1) 450 ret |= ALTERED; 451 } 452 lncntp[fs2h32(dirp->e2d_ino)]--; 453 break; 454 455 default: 456 errexit("BAD STATE %d FOR INODE I=%d\n", 457 statemap[fs2h32(dirp->e2d_ino)], fs2h32(dirp->e2d_ino)); 458 } 459 } 460 if (n == 0) 461 return (ret|KEEPON); 462 dirp->e2d_ino = 0; 463 return (ret|KEEPON|ALTERED); 464 } 465 466 /* 467 * Routine to sort disk blocks. 468 */ 469 static int 470 blksort(const void *inpp1, const void *inpp2) 471 { 472 return ((* (const struct inoinfo * const*) inpp1)->i_blks[0] - 473 (* (const struct inoinfo * const*) inpp2)->i_blks[0]); 474 } 475