1 /* $NetBSD: pass2.c,v 1.9 2003/10/05 17:48:49 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 REGENTS AND CONTRIBUTORS ``AS IS'' AND 50 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 51 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 52 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 53 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 54 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 55 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 56 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 57 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 58 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 59 * SUCH DAMAGE. 60 */ 61 62 #include <sys/cdefs.h> 63 #ifndef lint 64 #if 0 65 static char sccsid[] = "@(#)pass2.c 8.6 (Berkeley) 10/27/94"; 66 #else 67 __RCSID("$NetBSD: pass2.c,v 1.9 2003/10/05 17:48:49 bouyer Exp $"); 68 #endif 69 #endif /* not lint */ 70 71 #include <sys/param.h> 72 #include <sys/time.h> 73 #include <ufs/ext2fs/ext2fs_dinode.h> 74 #include <ufs/ext2fs/ext2fs_dir.h> 75 #include <ufs/ext2fs/ext2fs.h> 76 77 #include <ufs/ufs/dinode.h> /* for IFMT & friends */ 78 79 #include <stdio.h> 80 #include <stdlib.h> 81 #include <string.h> 82 83 #include "fsck.h" 84 #include "fsutil.h" 85 #include "extern.h" 86 87 #define MINDIRSIZE (sizeof (struct ext2fs_dirtemplate)) 88 89 static int pass2check __P((struct inodesc *)); 90 static int blksort __P((const void *, const void *)); 91 92 void 93 pass2() 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 errexit("%s\n", ""); 108 if (allocdir(EXT2_ROOTINO, EXT2_ROOTINO, 0755) != EXT2_ROOTINO) 109 errexit("CANNOT ALLOCATE ROOT INODE\n"); 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\n"); 118 break; 119 } 120 if (reply("CONTINUE") == 0) 121 errexit("%s\n", ""); 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\n"); 131 break; 132 } 133 if (reply("FIX") == 0) 134 errexit("%s\n", ""); 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\n", 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 dp->e2di_size = h2fs32(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 dp->e2di_size = h2fs32(inp->i_isize); 181 inodirty(); 182 } 183 } 184 memset(&dino, 0, sizeof(struct ext2fs_dinode)); 185 dino.e2di_mode = h2fs16(IFDIR); 186 dino.e2di_size = h2fs32(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(idesc) 229 struct inodesc *idesc; 230 { 231 struct ext2fs_direct *dirp = idesc->id_dirp; 232 struct inoinfo *inp; 233 int n, entrysize, ret = 0; 234 struct ext2fs_dinode *dp; 235 char *errmsg; 236 struct ext2fs_direct proto; 237 char namebuf[MAXPATHLEN + 1]; 238 char pathbuf[MAXPATHLEN + 1]; 239 240 /* 241 * check for "." 242 */ 243 if (idesc->id_entryno != 0) 244 goto chk1; 245 if (fs2h32(dirp->e2d_ino) != 0 && dirp->e2d_namlen == 1 && 246 dirp->e2d_name[0] == '.') { 247 if (fs2h32(dirp->e2d_ino) != idesc->id_number) { 248 direrror(idesc->id_number, "BAD INODE NUMBER FOR '.'"); 249 dirp->e2d_ino = h2fs32(idesc->id_number); 250 if (reply("FIX") == 1) 251 ret |= ALTERED; 252 } 253 if (sblock.e2fs.e2fs_rev > E2FS_REV0 && 254 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE) 255 && (dirp->e2d_type != EXT2_FT_DIR)) { 256 direrror(idesc->id_number, "BAD TYPE VALUE FOR '.'"); 257 dirp->e2d_type = EXT2_FT_DIR; 258 if (reply("FIX") == 1) 259 ret |= ALTERED; 260 } 261 goto chk1; 262 } 263 direrror(idesc->id_number, "MISSING '.'"); 264 proto.e2d_ino = h2fs32(idesc->id_number); 265 proto.e2d_namlen = 1; 266 if (sblock.e2fs.e2fs_rev > E2FS_REV0 && 267 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE)) 268 proto.e2d_type = EXT2_FT_DIR; 269 else 270 proto.e2d_type = 0; 271 (void)strlcpy(proto.e2d_name, ".", sizeof(proto.e2d_name)); 272 entrysize = EXT2FS_DIRSIZ(proto.e2d_namlen); 273 if (fs2h32(dirp->e2d_ino) != 0 && strcmp(dirp->e2d_name, "..") != 0) { 274 pfatal("CANNOT FIX, FIRST ENTRY IN DIRECTORY CONTAINS %s\n", 275 dirp->e2d_name); 276 } else if (fs2h16(dirp->e2d_reclen) < entrysize) { 277 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '.'\n"); 278 } else if (fs2h16(dirp->e2d_reclen) < 2 * entrysize) { 279 proto.e2d_reclen = dirp->e2d_reclen; 280 memcpy(dirp, &proto, (size_t)entrysize); 281 if (reply("FIX") == 1) 282 ret |= ALTERED; 283 } else { 284 n = fs2h16(dirp->e2d_reclen) - entrysize; 285 proto.e2d_reclen = h2fs16(entrysize); 286 memcpy(dirp, &proto, (size_t)entrysize); 287 idesc->id_entryno++; 288 lncntp[fs2h32(dirp->e2d_ino)]--; 289 dirp = (struct ext2fs_direct *)((char *)(dirp) + entrysize); 290 memset(dirp, 0, (size_t)n); 291 dirp->e2d_reclen = h2fs16(n); 292 if (reply("FIX") == 1) 293 ret |= ALTERED; 294 } 295 chk1: 296 if (idesc->id_entryno > 1) 297 goto chk2; 298 inp = getinoinfo(idesc->id_number); 299 proto.e2d_ino = h2fs32(inp->i_parent); 300 proto.e2d_namlen = 2; 301 if (sblock.e2fs.e2fs_rev > E2FS_REV0 && 302 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE)) 303 proto.e2d_type = EXT2_FT_DIR; 304 else 305 proto.e2d_type = 0; 306 (void)strlcpy(proto.e2d_name, "..", sizeof(proto.e2d_name)); 307 entrysize = EXT2FS_DIRSIZ(2); 308 if (idesc->id_entryno == 0) { 309 n = EXT2FS_DIRSIZ(dirp->e2d_namlen); 310 if (fs2h16(dirp->e2d_reclen) < n + entrysize) 311 goto chk2; 312 proto.e2d_reclen = h2fs16(fs2h16(dirp->e2d_reclen) - n); 313 dirp->e2d_reclen = h2fs16(n); 314 idesc->id_entryno++; 315 lncntp[fs2h32(dirp->e2d_ino)]--; 316 dirp = (struct ext2fs_direct *)((char *)(dirp) + n); 317 memset(dirp, 0, (size_t)fs2h16(proto.e2d_reclen)); 318 dirp->e2d_reclen = proto.e2d_reclen; 319 } 320 if (fs2h32(dirp->e2d_ino) != 0 && 321 dirp->e2d_namlen == 2 && 322 strncmp(dirp->e2d_name, "..", 2) == 0) { 323 inp->i_dotdot = fs2h32(dirp->e2d_ino); 324 if (sblock.e2fs.e2fs_rev > E2FS_REV0 && 325 (sblock.e2fs.e2fs_features_incompat & EXT2F_INCOMPAT_FTYPE) 326 && dirp->e2d_type != EXT2_FT_DIR) { 327 direrror(idesc->id_number, "BAD TYPE VALUE FOR '..'"); 328 dirp->e2d_type = EXT2_FT_DIR; 329 if (reply("FIX") == 1) 330 ret |= ALTERED; 331 } 332 goto chk2; 333 } 334 if (fs2h32(dirp->e2d_ino) != 0 && 335 dirp->e2d_namlen == 1 && 336 strncmp(dirp->e2d_name, ".", 1) != 0) { 337 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'"); 338 pfatal("CANNOT FIX, SECOND ENTRY IN DIRECTORY CONTAINS %s\n", 339 dirp->e2d_name); 340 inp->i_dotdot = (ino_t)-1; 341 } else if (fs2h16(dirp->e2d_reclen) < entrysize) { 342 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'"); 343 pfatal("CANNOT FIX, INSUFFICIENT SPACE TO ADD '..'\n"); 344 inp->i_dotdot = (ino_t)-1; 345 } else if (inp->i_parent != 0) { 346 /* 347 * We know the parent, so fix now. 348 */ 349 inp->i_dotdot = inp->i_parent; 350 fileerror(inp->i_parent, idesc->id_number, "MISSING '..'"); 351 proto.e2d_reclen = dirp->e2d_reclen; 352 memcpy(dirp, &proto, (size_t)entrysize); 353 if (reply("FIX") == 1) 354 ret |= ALTERED; 355 } 356 idesc->id_entryno++; 357 if (fs2h32(dirp->e2d_ino) != 0) 358 lncntp[fs2h32(dirp->e2d_ino)]--; 359 return (ret|KEEPON); 360 chk2: 361 if (fs2h32(dirp->e2d_ino) == 0) 362 return (ret|KEEPON); 363 if (dirp->e2d_namlen <= 2 && 364 dirp->e2d_name[0] == '.' && 365 idesc->id_entryno >= 2) { 366 if (dirp->e2d_namlen == 1) { 367 direrror(idesc->id_number, "EXTRA '.' ENTRY"); 368 dirp->e2d_ino = 0; 369 if (reply("FIX") == 1) 370 ret |= ALTERED; 371 return (KEEPON | ret); 372 } 373 if (dirp->e2d_name[1] == '.') { 374 direrror(idesc->id_number, "EXTRA '..' ENTRY"); 375 dirp->e2d_ino = 0; 376 if (reply("FIX") == 1) 377 ret |= ALTERED; 378 return (KEEPON | ret); 379 } 380 } 381 idesc->id_entryno++; 382 n = 0; 383 if (fs2h32(dirp->e2d_ino) > maxino || 384 (fs2h32(dirp->e2d_ino) < EXT2_FIRSTINO && 385 fs2h32(dirp->e2d_ino) != EXT2_ROOTINO)) { 386 fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), "I OUT OF RANGE"); 387 n = reply("REMOVE"); 388 } else { 389 again: 390 switch (statemap[fs2h32(dirp->e2d_ino)]) { 391 case USTATE: 392 if (idesc->id_entryno <= 2) 393 break; 394 fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), "UNALLOCATED"); 395 n = reply("REMOVE"); 396 break; 397 398 case DCLEAR: 399 case FCLEAR: 400 if (idesc->id_entryno <= 2) 401 break; 402 if (statemap[fs2h32(dirp->e2d_ino)] == FCLEAR) 403 errmsg = "DUP/BAD"; 404 else if (!preen) 405 errmsg = "ZERO LENGTH DIRECTORY"; 406 else { 407 n = 1; 408 break; 409 } 410 fileerror(idesc->id_number, fs2h32(dirp->e2d_ino), errmsg); 411 if ((n = reply("REMOVE")) == 1) 412 break; 413 dp = ginode(fs2h32(dirp->e2d_ino)); 414 statemap[fs2h32(dirp->e2d_ino)] = 415 (fs2h16(dp->e2di_mode) & IFMT) == IFDIR ? DSTATE : FSTATE; 416 lncntp[fs2h32(dirp->e2d_ino)] = fs2h16(dp->e2di_nlink); 417 goto again; 418 419 case DSTATE: 420 case DFOUND: 421 inp = getinoinfo(fs2h32(dirp->e2d_ino)); 422 if (inp->i_parent != 0 && idesc->id_entryno > 2) { 423 getpathname(pathbuf, sizeof(pathbuf), 424 idesc->id_number, idesc->id_number); 425 getpathname(namebuf, sizeof(namebuf), 426 fs2h32(dirp->e2d_ino), 427 fs2h32(dirp->e2d_ino)); 428 pwarn("%s %s %s\n", pathbuf, 429 "IS AN EXTRANEOUS HARD LINK TO DIRECTORY", 430 namebuf); 431 if (preen) 432 printf(" (IGNORED)\n"); 433 else if ((n = reply("REMOVE")) == 1) 434 break; 435 } 436 if (idesc->id_entryno > 2) 437 inp->i_parent = idesc->id_number; 438 /* fall through */ 439 440 case FSTATE: 441 if (sblock.e2fs.e2fs_rev > E2FS_REV0 && 442 (sblock.e2fs.e2fs_features_incompat & 443 EXT2F_INCOMPAT_FTYPE) && 444 dirp->e2d_type != 445 inot2ext2dt(typemap[fs2h32(dirp->e2d_ino)])) { 446 dirp->e2d_type = 447 inot2ext2dt(typemap[fs2h32(dirp->e2d_ino)]); 448 fileerror(idesc->id_number, 449 fs2h32(dirp->e2d_ino), 450 "BAD TYPE VALUE"); 451 if (reply("FIX") == 1) 452 ret |= ALTERED; 453 } 454 lncntp[fs2h32(dirp->e2d_ino)]--; 455 break; 456 457 default: 458 errexit("BAD STATE %d FOR INODE I=%d\n", 459 statemap[fs2h32(dirp->e2d_ino)], fs2h32(dirp->e2d_ino)); 460 } 461 } 462 if (n == 0) 463 return (ret|KEEPON); 464 dirp->e2d_ino = 0; 465 return (ret|KEEPON|ALTERED); 466 } 467 468 /* 469 * Routine to sort disk blocks. 470 */ 471 static int 472 blksort(inpp1, inpp2) 473 const void *inpp1, *inpp2; 474 { 475 return ((* (struct inoinfo **) inpp1)->i_blks[0] - 476 (* (struct inoinfo **) inpp2)->i_blks[0]); 477 } 478