1/* $OpenBSD: pass1.c,v 1.49 2024/02/03 18:51:57 beck 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 49static daddr_t badblk; 50static daddr_t dupblk; 51static void checkinode(ino_t, struct inodesc *); 52 53static ino_t info_inumber; 54 55static int 56pass1_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 63void 64pass1(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 * Allocate inoinfo structures for the allocated inodes. 115 */ 116 inostathead[c].il_numalloced = inosused; 117 if (inosused == 0) { 118 inostathead[c].il_stat = 0; 119 continue; 120 } 121 info = Calloc((unsigned)inosused, sizeof(struct inostat)); 122 inospace = (unsigned)inosused * sizeof(struct inostat); 123 if (info == NULL) 124 errexit("cannot alloc %zu bytes for inoinfo\n", inospace); 125 inostathead[c].il_stat = info; 126 /* 127 * Scan the allocated inodes. 128 */ 129 for (i = 0; i < inosused; i++, inumber++) { 130 info_inumber = inumber; 131 if (inumber < ROOTINO) { 132 (void)getnextinode(inumber); 133 continue; 134 } 135 checkinode(inumber, &idesc); 136 } 137 lastino += 1; 138 if (inosused < sblock.fs_ipg || inumber == lastino) 139 continue; 140 /* 141 * If we were not able to determine in advance which inodes 142 * were in use, then reduce the size of the inoinfo structure 143 * to the size necessary to describe the inodes that we 144 * really found. 145 */ 146 if (lastino < (c * sblock.fs_ipg)) 147 ninosused = 0; 148 else 149 ninosused = lastino - (c * sblock.fs_ipg); 150 inostathead[c].il_numalloced = ninosused; 151 if (ninosused == 0) { 152 free(inostathead[c].il_stat); 153 inostathead[c].il_stat = 0; 154 continue; 155 } 156 if (ninosused != inosused) { 157 struct inostat *ninfo; 158 size_t ninospace; 159 160 ninfo = Reallocarray(info, ninosused, sizeof(*ninfo)); 161 if (ninfo == NULL) { 162 pfatal("too many inodes %llu, or out of memory\n", 163 (unsigned long long)ninosused); 164 exit(8); 165 } 166 ninospace = ninosused * sizeof(*ninfo); 167 if (ninosused > inosused) 168 memset(&ninfo[inosused], 0, ninospace - inospace); 169 inostathead[c].il_stat = ninfo; 170 } 171 } 172 info_fn = NULL; 173 freeinodebuf(); 174} 175 176static void 177checkinode(ino_t inumber, struct inodesc *idesc) 178{ 179 union dinode *dp; 180 off_t kernmaxfilesize; 181 struct zlncnt *zlnp; 182 int ndb, j; 183 mode_t mode; 184 u_int64_t lndb; 185 186 dp = getnextinode(inumber); 187 mode = DIP(dp, di_mode) & IFMT; 188 if (mode == 0) { 189 if ((sblock.fs_magic == FS_UFS1_MAGIC && 190 (memcmp(dp->dp1.di_db, ufs1_zino.di_db, 191 NDADDR * sizeof(int32_t)) || 192 memcmp(dp->dp1.di_ib, ufs1_zino.di_ib, 193 NIADDR * sizeof(int32_t)) || 194 dp->dp1.di_mode || dp->dp1.di_size)) || 195 (sblock.fs_magic == FS_UFS2_MAGIC && 196 (memcmp(dp->dp2.di_db, ufs2_zino.di_db, 197 NDADDR * sizeof(daddr_t)) || 198 memcmp(dp->dp2.di_ib, ufs2_zino.di_ib, 199 NIADDR * sizeof(daddr_t)) || 200 dp->dp2.di_mode || dp->dp2.di_size))) { 201 pfatal("PARTIALLY ALLOCATED INODE I=%llu", 202 (unsigned long long)inumber); 203 if (reply("CLEAR") == 1) { 204 dp = ginode(inumber); 205 clearinode(dp); 206 inodirty(); 207 } 208 } 209 SET_ISTATE(inumber, USTATE); 210 return; 211 } 212 lastino = inumber; 213 /* This should match the file size limit in ffs_mountfs(). */ 214 kernmaxfilesize = FS_KERNMAXFILESIZE(getpagesize(), &sblock); 215 if (DIP(dp, di_size) > kernmaxfilesize || 216 DIP(dp, di_size) > sblock.fs_maxfilesize || 217 (mode == IFDIR && DIP(dp, di_size) > MAXDIRSIZE)) { 218 if (debug) 219 printf("bad size %llu:", 220 (unsigned long long)DIP(dp, di_size)); 221 goto unknown; 222 } 223 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 224 dp = ginode(inumber); 225 DIP_SET(dp, di_size, sblock.fs_fsize); 226 DIP_SET(dp, di_mode, IFREG|0600); 227 inodirty(); 228 } 229 lndb = howmany(DIP(dp, di_size), sblock.fs_bsize); 230 ndb = lndb > (u_int64_t)INT_MAX ? -1 : (int)lndb; 231 if (ndb < 0) { 232 if (debug) 233 printf("bad size %llu ndb %d:", 234 (unsigned long long)DIP(dp, di_size), ndb); 235 goto unknown; 236 } 237 if (mode == IFBLK || mode == IFCHR) 238 ndb++; 239 if (mode == IFLNK) { 240 /* 241 * Fake ndb value so direct/indirect block checks below 242 * will detect any garbage after symlink string. 243 */ 244 if (DIP(dp, di_size) < sblock.fs_maxsymlinklen) { 245 if (sblock.fs_magic == FS_UFS1_MAGIC) 246 ndb = howmany(DIP(dp, di_size), 247 sizeof(int32_t)); 248 else 249 ndb = howmany(DIP(dp, di_size), 250 sizeof(int64_t)); 251 if (ndb > NDADDR) { 252 j = ndb - NDADDR; 253 for (ndb = 1; j > 1; j--) 254 ndb *= NINDIR(&sblock); 255 ndb += NDADDR; 256 } 257 } 258 } 259 for (j = ndb; j < NDADDR; j++) 260 if (DIP(dp, di_db[j]) != 0) { 261 if (debug) 262 printf("bad direct addr: %lld\n", 263 (long long)DIP(dp, di_db[j])); 264 goto unknown; 265 } 266 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 267 ndb /= NINDIR(&sblock); 268 for (; j < NIADDR; j++) 269 if (DIP(dp, di_ib[j]) != 0) { 270 if (debug) 271 printf("bad indirect addr: %lld\n", 272 (long long)DIP(dp, di_ib[j])); 273 goto unknown; 274 } 275 if (ftypeok(dp) == 0) 276 goto unknown; 277 n_files++; 278 ILNCOUNT(inumber) = DIP(dp, di_nlink); 279 if (DIP(dp, di_nlink) <= 0) { 280 zlnp = Malloc(sizeof *zlnp); 281 if (zlnp == NULL) { 282 pfatal("LINK COUNT TABLE OVERFLOW"); 283 if (reply("CONTINUE") == 0) { 284 ckfini(0); 285 errexit("%s", ""); 286 } 287 } else { 288 zlnp->zlncnt = inumber; 289 zlnp->next = zlnhead; 290 zlnhead = zlnp; 291 } 292 } 293 if (mode == IFDIR) { 294 if (DIP(dp, di_size) == 0) 295 SET_ISTATE(inumber, DCLEAR); 296 else 297 SET_ISTATE(inumber, DSTATE); 298 cacheino(dp, inumber); 299 } else 300 SET_ISTATE(inumber, FSTATE); 301 SET_ITYPE(inumber, IFTODT(mode)); 302 badblk = dupblk = 0; 303 idesc->id_number = inumber; 304 (void)ckinode(dp, idesc); 305 idesc->id_entryno *= btodb(sblock.fs_fsize); 306 if (DIP(dp, di_blocks) != idesc->id_entryno) { 307 pwarn("INCORRECT BLOCK COUNT I=%llu (%lld should be %lld)", 308 (unsigned long long)inumber, (long long)DIP(dp, di_blocks), 309 (long long)idesc->id_entryno); 310 if (preen) 311 printf(" (CORRECTED)\n"); 312 else if (reply("CORRECT") == 0) 313 return; 314 dp = ginode(inumber); 315 DIP_SET(dp, di_blocks, idesc->id_entryno); 316 inodirty(); 317 } 318 return; 319unknown: 320 pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber); 321 SET_ISTATE(inumber, FCLEAR); 322 if (reply("CLEAR") == 1) { 323 SET_ISTATE(inumber, USTATE); 324 dp = ginode(inumber); 325 clearinode(dp); 326 inodirty(); 327 } 328} 329 330int 331pass1check(struct inodesc *idesc) 332{ 333 int res = KEEPON; 334 int anyout, nfrags; 335 daddr_t blkno = idesc->id_blkno; 336 struct dups *dlp; 337 struct dups *new; 338 339 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 340 blkerror(idesc->id_number, "BAD", blkno); 341 if (badblk++ >= MAXBAD) { 342 pwarn("EXCESSIVE BAD BLKS I=%llu", 343 (unsigned long long)idesc->id_number); 344 if (preen) 345 printf(" (SKIPPING)\n"); 346 else if (reply("CONTINUE") == 0) { 347 ckfini(0); 348 errexit("%s", ""); 349 } 350 return (STOP); 351 } 352 } 353 for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { 354 if (anyout && chkrange(blkno, 1)) { 355 res = SKIP; 356 } else if (!testbmap(blkno)) { 357 n_blks++; 358 setbmap(blkno); 359 } else { 360 blkerror(idesc->id_number, "DUP", blkno); 361 if (dupblk++ >= MAXDUP) { 362 pwarn("EXCESSIVE DUP 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 new = Malloc(sizeof(struct dups)); 373 if (new == NULL) { 374 pfatal("DUP TABLE OVERFLOW."); 375 if (reply("CONTINUE") == 0) { 376 ckfini(0); 377 errexit("%s", ""); 378 } 379 return (STOP); 380 } 381 new->dup = blkno; 382 if (muldup == 0) { 383 duplist = muldup = new; 384 new->next = 0; 385 } else { 386 new->next = muldup->next; 387 muldup->next = new; 388 } 389 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 390 if (dlp->dup == blkno) 391 break; 392 if (dlp == muldup && dlp->dup != blkno) 393 muldup = new; 394 } 395 /* 396 * count the number of blocks found in id_entryno 397 */ 398 idesc->id_entryno++; 399 } 400 return (res); 401} 402