1 /* $OpenBSD: pass1.c,v 1.43 2015/08/22 06:00:27 deraadt 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 int c; 70 struct inodesc idesc; 71 daddr_t i, cgd; 72 u_int8_t *cp; 73 74 /* 75 * Set file system reserved blocks in used block map. 76 */ 77 for (c = 0; c < sblock.fs_ncg; c++) { 78 cgd = cgdmin(&sblock, c); 79 if (c == 0) 80 i = cgbase(&sblock, c); 81 else 82 i = cgsblock(&sblock, c); 83 for (; i < cgd; i++) 84 setbmap(i); 85 } 86 i = sblock.fs_csaddr; 87 cgd = i + howmany(sblock.fs_cssize, sblock.fs_fsize); 88 for (; i < cgd; i++) 89 setbmap(i); 90 /* 91 * Find all allocated blocks. 92 */ 93 memset(&idesc, 0, sizeof(struct inodesc)); 94 idesc.id_type = ADDR; 95 idesc.id_func = pass1check; 96 n_files = n_blks = 0; 97 info_inumber = 0; 98 info_fn = pass1_info; 99 for (c = 0; c < sblock.fs_ncg; c++) { 100 inumber = c * sblock.fs_ipg; 101 setinodebuf(inumber); 102 getblk(&cgblk, cgtod(&sblock, c), sblock.fs_cgsize); 103 if (sblock.fs_magic == FS_UFS2_MAGIC) { 104 inosused = cgrp.cg_initediblk; 105 if (inosused > sblock.fs_ipg) 106 inosused = sblock.fs_ipg; 107 } else 108 inosused = sblock.fs_ipg; 109 110 /* 111 * If we are using soft updates, then we can trust the 112 * cylinder group inode allocation maps to tell us which 113 * inodes are allocated. We will scan the used inode map 114 * to find the inodes that are really in use, and then 115 * read only those inodes in from disk. 116 */ 117 if (preen && usedsoftdep) { 118 cp = &cg_inosused(&cgrp)[(inosused - 1) / CHAR_BIT]; 119 for ( ; inosused > 0; inosused -= CHAR_BIT, cp--) { 120 if (*cp == 0) 121 continue; 122 for (i = 1 << (CHAR_BIT - 1); i > 0; i >>= 1) { 123 if (*cp & i) 124 break; 125 inosused--; 126 } 127 break; 128 } 129 if (inosused < 0) 130 inosused = 0; 131 } 132 /* 133 * Allocate inoinfo structures for the allocated inodes. 134 */ 135 inostathead[c].il_numalloced = inosused; 136 if (inosused == 0) { 137 inostathead[c].il_stat = 0; 138 continue; 139 } 140 info = calloc((unsigned)inosused, sizeof(struct inostat)); 141 inospace = (unsigned)inosused * sizeof(struct inostat); 142 if (info == NULL) 143 errexit("cannot alloc %zu bytes for inoinfo", inospace); 144 inostathead[c].il_stat = info; 145 /* 146 * Scan the allocated inodes. 147 */ 148 for (i = 0; i < inosused; i++, inumber++) { 149 info_inumber = inumber; 150 if (inumber < ROOTINO) { 151 (void)getnextinode(inumber); 152 continue; 153 } 154 checkinode(inumber, &idesc); 155 } 156 lastino += 1; 157 if (inosused < sblock.fs_ipg || inumber == lastino) 158 continue; 159 /* 160 * If we were not able to determine in advance which inodes 161 * were in use, then reduce the size of the inoinfo structure 162 * to the size necessary to describe the inodes that we 163 * really found. 164 */ 165 if (lastino < (c * sblock.fs_ipg)) 166 ninosused = 0; 167 else 168 ninosused = lastino - (c * sblock.fs_ipg); 169 inostathead[c].il_numalloced = ninosused; 170 if (ninosused == 0) { 171 free(inostathead[c].il_stat); 172 inostathead[c].il_stat = 0; 173 continue; 174 } 175 if (ninosused != inosused) { 176 struct inostat *ninfo; 177 size_t ninospace; 178 179 ninfo = reallocarray(info, ninosused, sizeof(*ninfo)); 180 if (ninfo == NULL) { 181 pfatal("too many inodes %llu, or out of memory\n", 182 (unsigned long long)ninosused); 183 exit(8); 184 } 185 ninospace = ninosused * sizeof(*ninfo); 186 if (ninosused > inosused) 187 memset(&ninfo[inosused], 0, ninospace - inospace); 188 inostathead[c].il_stat = ninfo; 189 } 190 } 191 info_fn = NULL; 192 freeinodebuf(); 193 } 194 195 static void 196 checkinode(ino_t inumber, struct inodesc *idesc) 197 { 198 union dinode *dp; 199 off_t kernmaxfilesize; 200 struct zlncnt *zlnp; 201 int ndb, j; 202 mode_t mode; 203 u_int64_t lndb; 204 205 dp = getnextinode(inumber); 206 mode = DIP(dp, di_mode) & IFMT; 207 if (mode == 0) { 208 if ((sblock.fs_magic == FS_UFS1_MAGIC && 209 (memcmp(dp->dp1.di_db, ufs1_zino.di_db, 210 NDADDR * sizeof(int32_t)) || 211 memcmp(dp->dp1.di_ib, ufs1_zino.di_ib, 212 NIADDR * sizeof(int32_t)) || 213 dp->dp1.di_mode || dp->dp1.di_size)) || 214 (sblock.fs_magic == FS_UFS2_MAGIC && 215 (memcmp(dp->dp2.di_db, ufs2_zino.di_db, 216 NDADDR * sizeof(daddr_t)) || 217 memcmp(dp->dp2.di_ib, ufs2_zino.di_ib, 218 NIADDR * sizeof(daddr_t)) || 219 dp->dp2.di_mode || dp->dp2.di_size))) { 220 pfatal("PARTIALLY ALLOCATED INODE I=%llu", 221 (unsigned long long)inumber); 222 if (reply("CLEAR") == 1) { 223 dp = ginode(inumber); 224 clearinode(dp); 225 inodirty(); 226 } 227 } 228 SET_ISTATE(inumber, USTATE); 229 return; 230 } 231 lastino = inumber; 232 /* This should match the file size limit in ffs_mountfs(). */ 233 kernmaxfilesize = FS_KERNMAXFILESIZE(getpagesize(), &sblock); 234 if (DIP(dp, di_size) > kernmaxfilesize || 235 DIP(dp, di_size) > sblock.fs_maxfilesize || 236 (mode == IFDIR && DIP(dp, di_size) > MAXDIRSIZE)) { 237 if (debug) 238 printf("bad size %llu:", 239 (unsigned long long)DIP(dp, di_size)); 240 goto unknown; 241 } 242 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 243 dp = ginode(inumber); 244 DIP_SET(dp, di_size, sblock.fs_fsize); 245 DIP_SET(dp, di_mode, IFREG|0600); 246 inodirty(); 247 } 248 lndb = howmany(DIP(dp, di_size), sblock.fs_bsize); 249 ndb = lndb > (u_int64_t)INT_MAX ? -1 : (int)lndb; 250 if (ndb < 0) { 251 if (debug) 252 printf("bad size %llu ndb %d:", 253 (unsigned long long)DIP(dp, di_size), ndb); 254 goto unknown; 255 } 256 if (mode == IFBLK || mode == IFCHR) 257 ndb++; 258 if (mode == IFLNK) { 259 /* 260 * Fake ndb value so direct/indirect block checks below 261 * will detect any garbage after symlink string. 262 */ 263 if (DIP(dp, di_size) < sblock.fs_maxsymlinklen || 264 (sblock.fs_maxsymlinklen == 0 && DIP(dp, di_blocks) == 0)) { 265 if (sblock.fs_magic == FS_UFS1_MAGIC) 266 ndb = howmany(DIP(dp, di_size), 267 sizeof(int32_t)); 268 else 269 ndb = howmany(DIP(dp, di_size), 270 sizeof(int64_t)); 271 if (ndb > NDADDR) { 272 j = ndb - NDADDR; 273 for (ndb = 1; j > 1; j--) 274 ndb *= NINDIR(&sblock); 275 ndb += NDADDR; 276 } 277 } 278 } 279 for (j = ndb; j < NDADDR; j++) 280 if (DIP(dp, di_db[j]) != 0) { 281 if (debug) 282 printf("bad direct addr: %lld\n", 283 (long long)DIP(dp, di_db[j])); 284 goto unknown; 285 } 286 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 287 ndb /= NINDIR(&sblock); 288 for (; j < NIADDR; j++) 289 if (DIP(dp, di_ib[j]) != 0) { 290 if (debug) 291 printf("bad indirect addr: %lld\n", 292 (long long)DIP(dp, di_ib[j])); 293 goto unknown; 294 } 295 if (ftypeok(dp) == 0) 296 goto unknown; 297 n_files++; 298 ILNCOUNT(inumber) = DIP(dp, di_nlink); 299 if (DIP(dp, di_nlink) <= 0) { 300 zlnp = malloc(sizeof *zlnp); 301 if (zlnp == NULL) { 302 pfatal("LINK COUNT TABLE OVERFLOW"); 303 if (reply("CONTINUE") == 0) { 304 ckfini(0); 305 errexit("%s", ""); 306 } 307 } else { 308 zlnp->zlncnt = inumber; 309 zlnp->next = zlnhead; 310 zlnhead = zlnp; 311 } 312 } 313 if (mode == IFDIR) { 314 if (DIP(dp, di_size) == 0) 315 SET_ISTATE(inumber, DCLEAR); 316 else 317 SET_ISTATE(inumber, DSTATE); 318 cacheino(dp, inumber); 319 } else 320 SET_ISTATE(inumber, FSTATE); 321 SET_ITYPE(inumber, IFTODT(mode)); 322 badblk = dupblk = 0; 323 idesc->id_number = inumber; 324 (void)ckinode(dp, idesc); 325 idesc->id_entryno *= btodb(sblock.fs_fsize); 326 if (DIP(dp, di_blocks) != idesc->id_entryno) { 327 pwarn("INCORRECT BLOCK COUNT I=%llu (%lld should be %lld)", 328 (unsigned long long)inumber, (long long)DIP(dp, di_blocks), 329 (long long)idesc->id_entryno); 330 if (preen) 331 printf(" (CORRECTED)\n"); 332 else if (reply("CORRECT") == 0) 333 return; 334 dp = ginode(inumber); 335 DIP_SET(dp, di_blocks, idesc->id_entryno); 336 inodirty(); 337 } 338 return; 339 unknown: 340 pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber); 341 SET_ISTATE(inumber, FCLEAR); 342 if (reply("CLEAR") == 1) { 343 SET_ISTATE(inumber, USTATE); 344 dp = ginode(inumber); 345 clearinode(dp); 346 inodirty(); 347 } 348 } 349 350 int 351 pass1check(struct inodesc *idesc) 352 { 353 int res = KEEPON; 354 int anyout, nfrags; 355 daddr_t blkno = idesc->id_blkno; 356 struct dups *dlp; 357 struct dups *new; 358 359 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 360 blkerror(idesc->id_number, "BAD", blkno); 361 if (badblk++ >= MAXBAD) { 362 pwarn("EXCESSIVE BAD BLKS I=%llu", 363 (unsigned long long)idesc->id_number); 364 if (preen) 365 printf(" (SKIPPING)\n"); 366 else if (reply("CONTINUE") == 0) { 367 ckfini(0); 368 errexit("%s", ""); 369 } 370 return (STOP); 371 } 372 } 373 for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { 374 if (anyout && chkrange(blkno, 1)) { 375 res = SKIP; 376 } else if (!testbmap(blkno)) { 377 n_blks++; 378 setbmap(blkno); 379 } else { 380 blkerror(idesc->id_number, "DUP", blkno); 381 if (dupblk++ >= MAXDUP) { 382 pwarn("EXCESSIVE DUP BLKS I=%llu", 383 (unsigned long long)idesc->id_number); 384 if (preen) 385 printf(" (SKIPPING)\n"); 386 else if (reply("CONTINUE") == 0) { 387 ckfini(0); 388 errexit("%s", ""); 389 } 390 return (STOP); 391 } 392 new = malloc(sizeof(struct dups)); 393 if (new == NULL) { 394 pfatal("DUP TABLE OVERFLOW."); 395 if (reply("CONTINUE") == 0) { 396 ckfini(0); 397 errexit("%s", ""); 398 } 399 return (STOP); 400 } 401 new->dup = blkno; 402 if (muldup == 0) { 403 duplist = muldup = new; 404 new->next = 0; 405 } else { 406 new->next = muldup->next; 407 muldup->next = new; 408 } 409 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 410 if (dlp->dup == blkno) 411 break; 412 if (dlp == muldup && dlp->dup != blkno) 413 muldup = new; 414 } 415 /* 416 * count the number of blocks found in id_entryno 417 */ 418 idesc->id_entryno++; 419 } 420 return (res); 421 } 422