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