1 /* $OpenBSD: pass1.c,v 1.47 2020/07/13 06:52:53 otto Exp $ */ 2 /* $NetBSD: pass1.c,v 1.16 1996/09/27 22:45:15 christos Exp $ */ 3 4 /* 5 * Copyright (c) 1980, 1986, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. Neither the name of the University nor the names of its contributors 17 * may be used to endorse or promote products derived from this software 18 * without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 30 * SUCH DAMAGE. 31 */ 32 33 #include <sys/param.h> /* MIN setbit btodb isset */ 34 #include <sys/time.h> 35 #include <ufs/ufs/dinode.h> 36 #include <ufs/ufs/dir.h> 37 #include <ufs/ffs/fs.h> 38 39 #include <stdio.h> 40 #include <stdlib.h> 41 #include <string.h> 42 #include <unistd.h> 43 #include <limits.h> 44 45 #include "fsck.h" 46 #include "extern.h" 47 #include "fsutil.h" 48 49 static daddr_t badblk; 50 static daddr_t dupblk; 51 static void checkinode(ino_t, struct inodesc *); 52 53 static ino_t info_inumber; 54 55 static int 56 pass1_info(char *buf, size_t buflen) 57 { 58 return (snprintf(buf, buflen, "phase 1, inode %llu/%llu", 59 (unsigned long long)info_inumber, 60 (unsigned long long)sblock.fs_ipg * sblock.fs_ncg) > 0); 61 } 62 63 void 64 pass1(void) 65 { 66 ino_t inumber, inosused, ninosused; 67 size_t inospace; 68 struct inostat *info; 69 struct bufarea *cgbp; 70 struct cg *cgp; 71 u_int c; 72 struct inodesc idesc; 73 daddr_t i, cgd; 74 u_int8_t *cp; 75 76 /* 77 * Set file system reserved blocks in used block map. 78 */ 79 for (c = 0; c < sblock.fs_ncg; c++) { 80 cgd = cgdmin(&sblock, c); 81 if (c == 0) 82 i = cgbase(&sblock, c); 83 else 84 i = cgsblock(&sblock, c); 85 for (; i < cgd; i++) 86 setbmap(i); 87 } 88 i = sblock.fs_csaddr; 89 cgd = i + howmany(sblock.fs_cssize, sblock.fs_fsize); 90 for (; i < cgd; i++) 91 setbmap(i); 92 /* 93 * Find all allocated blocks. 94 */ 95 memset(&idesc, 0, sizeof(struct inodesc)); 96 idesc.id_type = ADDR; 97 idesc.id_func = pass1check; 98 n_files = n_blks = 0; 99 info_inumber = 0; 100 info_fn = pass1_info; 101 for (c = 0; c < sblock.fs_ncg; c++) { 102 inumber = c * sblock.fs_ipg; 103 setinodebuf(inumber); 104 cgbp = cglookup(c); 105 cgp = cgbp->b_un.b_cg; 106 if (sblock.fs_magic == FS_UFS2_MAGIC) { 107 inosused = cgp->cg_initediblk; 108 if (inosused > sblock.fs_ipg) 109 inosused = sblock.fs_ipg; 110 } else 111 inosused = sblock.fs_ipg; 112 113 /* 114 * If we are using soft updates, then we can trust the 115 * cylinder group inode allocation maps to tell us which 116 * inodes are allocated. We will scan the used inode map 117 * to find the inodes that are really in use, and then 118 * read only those inodes in from disk. 119 */ 120 if (preen && usedsoftdep) { 121 cp = &cg_inosused(cgp)[(inosused - 1) / CHAR_BIT]; 122 for ( ; inosused != 0; cp--) { 123 if (*cp == 0) { 124 if (inosused > CHAR_BIT) 125 inosused -= CHAR_BIT; 126 else 127 inosused = 0; 128 continue; 129 } 130 for (i = 1 << (CHAR_BIT - 1); i > 0; i >>= 1) { 131 if (*cp & i) 132 break; 133 inosused--; 134 } 135 break; 136 } 137 } 138 /* 139 * Allocate inoinfo structures for the allocated inodes. 140 */ 141 inostathead[c].il_numalloced = inosused; 142 if (inosused == 0) { 143 inostathead[c].il_stat = 0; 144 continue; 145 } 146 info = Calloc((unsigned)inosused, sizeof(struct inostat)); 147 inospace = (unsigned)inosused * sizeof(struct inostat); 148 if (info == NULL) 149 errexit("cannot alloc %zu bytes for inoinfo\n", inospace); 150 inostathead[c].il_stat = info; 151 /* 152 * Scan the allocated inodes. 153 */ 154 for (i = 0; i < inosused; i++, inumber++) { 155 info_inumber = inumber; 156 if (inumber < ROOTINO) { 157 (void)getnextinode(inumber); 158 continue; 159 } 160 checkinode(inumber, &idesc); 161 } 162 lastino += 1; 163 if (inosused < sblock.fs_ipg || inumber == lastino) 164 continue; 165 /* 166 * If we were not able to determine in advance which inodes 167 * were in use, then reduce the size of the inoinfo structure 168 * to the size necessary to describe the inodes that we 169 * really found. 170 */ 171 if (lastino < (c * sblock.fs_ipg)) 172 ninosused = 0; 173 else 174 ninosused = lastino - (c * sblock.fs_ipg); 175 inostathead[c].il_numalloced = ninosused; 176 if (ninosused == 0) { 177 free(inostathead[c].il_stat); 178 inostathead[c].il_stat = 0; 179 continue; 180 } 181 if (ninosused != inosused) { 182 struct inostat *ninfo; 183 size_t ninospace; 184 185 ninfo = Reallocarray(info, ninosused, sizeof(*ninfo)); 186 if (ninfo == NULL) { 187 pfatal("too many inodes %llu, or out of memory\n", 188 (unsigned long long)ninosused); 189 exit(8); 190 } 191 ninospace = ninosused * sizeof(*ninfo); 192 if (ninosused > inosused) 193 memset(&ninfo[inosused], 0, ninospace - inospace); 194 inostathead[c].il_stat = ninfo; 195 } 196 } 197 info_fn = NULL; 198 freeinodebuf(); 199 } 200 201 static void 202 checkinode(ino_t inumber, struct inodesc *idesc) 203 { 204 union dinode *dp; 205 off_t kernmaxfilesize; 206 struct zlncnt *zlnp; 207 int ndb, j; 208 mode_t mode; 209 u_int64_t lndb; 210 211 dp = getnextinode(inumber); 212 mode = DIP(dp, di_mode) & IFMT; 213 if (mode == 0) { 214 if ((sblock.fs_magic == FS_UFS1_MAGIC && 215 (memcmp(dp->dp1.di_db, ufs1_zino.di_db, 216 NDADDR * sizeof(int32_t)) || 217 memcmp(dp->dp1.di_ib, ufs1_zino.di_ib, 218 NIADDR * sizeof(int32_t)) || 219 dp->dp1.di_mode || dp->dp1.di_size)) || 220 (sblock.fs_magic == FS_UFS2_MAGIC && 221 (memcmp(dp->dp2.di_db, ufs2_zino.di_db, 222 NDADDR * sizeof(daddr_t)) || 223 memcmp(dp->dp2.di_ib, ufs2_zino.di_ib, 224 NIADDR * sizeof(daddr_t)) || 225 dp->dp2.di_mode || dp->dp2.di_size))) { 226 pfatal("PARTIALLY ALLOCATED INODE I=%llu", 227 (unsigned long long)inumber); 228 if (reply("CLEAR") == 1) { 229 dp = ginode(inumber); 230 clearinode(dp); 231 inodirty(); 232 } 233 } 234 SET_ISTATE(inumber, USTATE); 235 return; 236 } 237 lastino = inumber; 238 /* This should match the file size limit in ffs_mountfs(). */ 239 kernmaxfilesize = FS_KERNMAXFILESIZE(getpagesize(), &sblock); 240 if (DIP(dp, di_size) > kernmaxfilesize || 241 DIP(dp, di_size) > sblock.fs_maxfilesize || 242 (mode == IFDIR && DIP(dp, di_size) > MAXDIRSIZE)) { 243 if (debug) 244 printf("bad size %llu:", 245 (unsigned long long)DIP(dp, di_size)); 246 goto unknown; 247 } 248 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 249 dp = ginode(inumber); 250 DIP_SET(dp, di_size, sblock.fs_fsize); 251 DIP_SET(dp, di_mode, IFREG|0600); 252 inodirty(); 253 } 254 lndb = howmany(DIP(dp, di_size), sblock.fs_bsize); 255 ndb = lndb > (u_int64_t)INT_MAX ? -1 : (int)lndb; 256 if (ndb < 0) { 257 if (debug) 258 printf("bad size %llu ndb %d:", 259 (unsigned long long)DIP(dp, di_size), ndb); 260 goto unknown; 261 } 262 if (mode == IFBLK || mode == IFCHR) 263 ndb++; 264 if (mode == IFLNK) { 265 /* 266 * Fake ndb value so direct/indirect block checks below 267 * will detect any garbage after symlink string. 268 */ 269 if (DIP(dp, di_size) < sblock.fs_maxsymlinklen || 270 (sblock.fs_maxsymlinklen == 0 && DIP(dp, di_blocks) == 0)) { 271 if (sblock.fs_magic == FS_UFS1_MAGIC) 272 ndb = howmany(DIP(dp, di_size), 273 sizeof(int32_t)); 274 else 275 ndb = howmany(DIP(dp, di_size), 276 sizeof(int64_t)); 277 if (ndb > NDADDR) { 278 j = ndb - NDADDR; 279 for (ndb = 1; j > 1; j--) 280 ndb *= NINDIR(&sblock); 281 ndb += NDADDR; 282 } 283 } 284 } 285 for (j = ndb; j < NDADDR; j++) 286 if (DIP(dp, di_db[j]) != 0) { 287 if (debug) 288 printf("bad direct addr: %lld\n", 289 (long long)DIP(dp, di_db[j])); 290 goto unknown; 291 } 292 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 293 ndb /= NINDIR(&sblock); 294 for (; j < NIADDR; j++) 295 if (DIP(dp, di_ib[j]) != 0) { 296 if (debug) 297 printf("bad indirect addr: %lld\n", 298 (long long)DIP(dp, di_ib[j])); 299 goto unknown; 300 } 301 if (ftypeok(dp) == 0) 302 goto unknown; 303 n_files++; 304 ILNCOUNT(inumber) = DIP(dp, di_nlink); 305 if (DIP(dp, di_nlink) <= 0) { 306 zlnp = Malloc(sizeof *zlnp); 307 if (zlnp == NULL) { 308 pfatal("LINK COUNT TABLE OVERFLOW"); 309 if (reply("CONTINUE") == 0) { 310 ckfini(0); 311 errexit("%s", ""); 312 } 313 } else { 314 zlnp->zlncnt = inumber; 315 zlnp->next = zlnhead; 316 zlnhead = zlnp; 317 } 318 } 319 if (mode == IFDIR) { 320 if (DIP(dp, di_size) == 0) 321 SET_ISTATE(inumber, DCLEAR); 322 else 323 SET_ISTATE(inumber, DSTATE); 324 cacheino(dp, inumber); 325 } else 326 SET_ISTATE(inumber, FSTATE); 327 SET_ITYPE(inumber, IFTODT(mode)); 328 badblk = dupblk = 0; 329 idesc->id_number = inumber; 330 (void)ckinode(dp, idesc); 331 idesc->id_entryno *= btodb(sblock.fs_fsize); 332 if (DIP(dp, di_blocks) != idesc->id_entryno) { 333 pwarn("INCORRECT BLOCK COUNT I=%llu (%lld should be %lld)", 334 (unsigned long long)inumber, (long long)DIP(dp, di_blocks), 335 (long long)idesc->id_entryno); 336 if (preen) 337 printf(" (CORRECTED)\n"); 338 else if (reply("CORRECT") == 0) 339 return; 340 dp = ginode(inumber); 341 DIP_SET(dp, di_blocks, idesc->id_entryno); 342 inodirty(); 343 } 344 return; 345 unknown: 346 pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber); 347 SET_ISTATE(inumber, FCLEAR); 348 if (reply("CLEAR") == 1) { 349 SET_ISTATE(inumber, USTATE); 350 dp = ginode(inumber); 351 clearinode(dp); 352 inodirty(); 353 } 354 } 355 356 int 357 pass1check(struct inodesc *idesc) 358 { 359 int res = KEEPON; 360 int anyout, nfrags; 361 daddr_t blkno = idesc->id_blkno; 362 struct dups *dlp; 363 struct dups *new; 364 365 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 366 blkerror(idesc->id_number, "BAD", blkno); 367 if (badblk++ >= MAXBAD) { 368 pwarn("EXCESSIVE BAD BLKS I=%llu", 369 (unsigned long long)idesc->id_number); 370 if (preen) 371 printf(" (SKIPPING)\n"); 372 else if (reply("CONTINUE") == 0) { 373 ckfini(0); 374 errexit("%s", ""); 375 } 376 return (STOP); 377 } 378 } 379 for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { 380 if (anyout && chkrange(blkno, 1)) { 381 res = SKIP; 382 } else if (!testbmap(blkno)) { 383 n_blks++; 384 setbmap(blkno); 385 } else { 386 blkerror(idesc->id_number, "DUP", blkno); 387 if (dupblk++ >= MAXDUP) { 388 pwarn("EXCESSIVE DUP BLKS I=%llu", 389 (unsigned long long)idesc->id_number); 390 if (preen) 391 printf(" (SKIPPING)\n"); 392 else if (reply("CONTINUE") == 0) { 393 ckfini(0); 394 errexit("%s", ""); 395 } 396 return (STOP); 397 } 398 new = Malloc(sizeof(struct dups)); 399 if (new == NULL) { 400 pfatal("DUP TABLE OVERFLOW."); 401 if (reply("CONTINUE") == 0) { 402 ckfini(0); 403 errexit("%s", ""); 404 } 405 return (STOP); 406 } 407 new->dup = blkno; 408 if (muldup == 0) { 409 duplist = muldup = new; 410 new->next = 0; 411 } else { 412 new->next = muldup->next; 413 muldup->next = new; 414 } 415 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 416 if (dlp->dup == blkno) 417 break; 418 if (dlp == muldup && dlp->dup != blkno) 419 muldup = new; 420 } 421 /* 422 * count the number of blocks found in id_entryno 423 */ 424 idesc->id_entryno++; 425 } 426 return (res); 427 } 428