1 /* $NetBSD: pass2.c,v 1.10 2004/03/22 19:46:53 bouyer 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.10 2004/03/22 19:46:53 bouyer 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 __P((struct inodesc *)); 89 static int blksort __P((const void *, const void *)); 90 91 void 92 pass2() 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 dp->e2di_size = h2fs32(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 dp->e2di_size = h2fs32(inp->i_isize); 180 inodirty(); 181 } 182 } 183 memset(&dino, 0, sizeof(struct ext2fs_dinode)); 184 dino.e2di_mode = h2fs16(IFDIR); 185 dino.e2di_size = h2fs32(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(idesc) 228 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 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\n", 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(inpp1, inpp2) 472 const void *inpp1, *inpp2; 473 { 474 return ((* (struct inoinfo **) inpp1)->i_blks[0] - 475 (* (struct inoinfo **) inpp2)->i_blks[0]); 476 } 477