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