pass1.c revision 102231
1124271Sgreen/* 2124271Sgreen * Copyright (c) 1980, 1986, 1993 3124271Sgreen * The Regents of the University of California. All rights reserved. 4124271Sgreen * 5124271Sgreen * Redistribution and use in source and binary forms, with or without 6124271Sgreen * modification, are permitted provided that the following conditions 7124271Sgreen * are met: 8124271Sgreen * 1. Redistributions of source code must retain the above copyright 9124271Sgreen * notice, this list of conditions and the following disclaimer. 10124271Sgreen * 2. Redistributions in binary form must reproduce the above copyright 11124271Sgreen * notice, this list of conditions and the following disclaimer in the 12124271Sgreen * documentation and/or other materials provided with the distribution. 13124271Sgreen * 3. All advertising materials mentioning features or use of this software 14124271Sgreen * must display the following acknowledgement: 15124271Sgreen * This product includes software developed by the University of 16124271Sgreen * California, Berkeley and its contributors. 17124271Sgreen * 4. Neither the name of the University nor the names of its contributors 18124271Sgreen * may be used to endorse or promote products derived from this software 19124271Sgreen * without specific prior written permission. 20124271Sgreen * 21124271Sgreen * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22124271Sgreen * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23124271Sgreen * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24124271Sgreen * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25124271Sgreen * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26124271Sgreen * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27124271Sgreen * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28124271Sgreen * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29124271Sgreen * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30124271Sgreen * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31124271Sgreen * SUCH DAMAGE. 32124271Sgreen */ 33124271Sgreen 34124271Sgreen#ifndef lint 35124271Sgreen#if 0 36124271Sgreenstatic const char sccsid[] = "@(#)pass1.c 8.6 (Berkeley) 4/28/95"; 37124271Sgreen#endif 38124271Sgreenstatic const char rcsid[] = 39124271Sgreen "$FreeBSD: head/sbin/fsck_ffs/pass1.c 102231 2002-08-21 18:11:48Z trhodes $"; 40124271Sgreen#endif /* not lint */ 41158882Sglebius 42124271Sgreen#include <sys/param.h> 43158882Sglebius#include <sys/stat.h> 44158882Sglebius#include <sys/sysctl.h> 45158882Sglebius 46158882Sglebius#include <ufs/ufs/dinode.h> 47124271Sgreen#include <ufs/ufs/dir.h> 48124271Sgreen#include <ufs/ffs/fs.h> 49124271Sgreen 50124271Sgreen#include <err.h> 51124271Sgreen#include <stdint.h> 52124271Sgreen#include <string.h> 53124271Sgreen 54124271Sgreen#include "fsck.h" 55124271Sgreen 56124271Sgreenstatic ufs2_daddr_t badblk; 57124271Sgreenstatic ufs2_daddr_t dupblk; 58124271Sgreenstatic ino_t lastino; /* last inode in use */ 59124271Sgreen 60124271Sgreenstatic void checkinode(ino_t inumber, struct inodesc *); 61124271Sgreen 62124271Sgreenvoid 63124271Sgreenpass1(void) 64124271Sgreen{ 65125115Sru struct inostat *info; 66125115Sru struct inodesc idesc; 67124271Sgreen ino_t inumber, inosused; 68125011Sru ufs2_daddr_t i, cgd; 69125011Sru u_int8_t *cp; 70124271Sgreen int c; 71124271Sgreen 72124271Sgreen /* 73166529Skevlo * Set file system reserved blocks in used block map. 74124271Sgreen */ 75124271Sgreen for (c = 0; c < sblock.fs_ncg; c++) { 76124271Sgreen cgd = cgdmin(&sblock, c); 77124271Sgreen if (c == 0) { 78124271Sgreen i = cgbase(&sblock, c); 79124271Sgreen } else 80124271Sgreen i = cgsblock(&sblock, c); 81124271Sgreen for (; i < cgd; i++) 82124271Sgreen setbmap(i); 83124271Sgreen } 84124271Sgreen i = sblock.fs_csaddr; 85124271Sgreen cgd = i + howmany(sblock.fs_cssize, sblock.fs_fsize); 86124271Sgreen for (; i < cgd; i++) 87124271Sgreen setbmap(i); 88124271Sgreen 89124271Sgreen /* 90124271Sgreen * Find all allocated blocks. 91124271Sgreen */ 92124271Sgreen memset(&idesc, 0, sizeof(struct inodesc)); 93124271Sgreen idesc.id_func = pass1check; 94124271Sgreen n_files = n_blks = 0; 95124271Sgreen for (c = 0; c < sblock.fs_ncg; c++) { 96124271Sgreen inumber = c * sblock.fs_ipg; 97124271Sgreen setinodebuf(inumber); 98124271Sgreen getblk(&cgblk, cgtod(&sblock, c), sblock.fs_cgsize); 99124271Sgreen if (sblock.fs_magic == FS_UFS2_MAGIC) 100124271Sgreen inosused = cgrp.cg_initediblk; 101124271Sgreen else 102124271Sgreen inosused = sblock.fs_ipg; 103124271Sgreen if (got_siginfo) { 104124271Sgreen printf("%s: phase 1: cyl group %d of %d (%d%%)\n", 105124271Sgreen cdevname, c, sblock.fs_ncg, 106125115Sru c * 100 / sblock.fs_ncg); 107124271Sgreen got_siginfo = 0; 108124271Sgreen } 109124271Sgreen /* 110124271Sgreen * If we are using soft updates, then we can trust the 111125115Sru * cylinder group inode allocation maps to tell us which 112124271Sgreen * inodes are allocated. We will scan the used inode map 113124271Sgreen * to find the inodes that are really in use, and then 114124271Sgreen * read only those inodes in from disk. 115124271Sgreen */ 116124271Sgreen if (preen && usedsoftdep) { 117124271Sgreen if (!cg_chkmagic(&cgrp)) 118124271Sgreen pfatal("CG %d: BAD MAGIC NUMBER\n", c); 119124271Sgreen cp = &cg_inosused(&cgrp)[(inosused - 1) / NBBY]; 120124271Sgreen for ( ; inosused > 0; inosused -= NBBY, cp--) { 121124271Sgreen if (*cp == 0) 122124271Sgreen continue; 123124271Sgreen for (i = 1 << (NBBY - 1); i > 0; i >>= 1) { 124124271Sgreen if (*cp & i) 125124271Sgreen break; 126124271Sgreen inosused--; 127124271Sgreen } 128124271Sgreen break; 129124271Sgreen } 130124271Sgreen if (inosused < 0) 131124271Sgreen inosused = 0; 132124271Sgreen } 133125115Sru /* 134125115Sru * Allocate inoinfo structures for the allocated inodes. 135125115Sru */ 136124271Sgreen inostathead[c].il_numalloced = inosused; 137125011Sru if (inosused == 0) { 138124271Sgreen inostathead[c].il_stat = 0; 139124271Sgreen continue; 140124271Sgreen } 141124271Sgreen info = calloc((unsigned)inosused, sizeof(struct inostat)); 142124271Sgreen if (info == NULL) 143124271Sgreen pfatal("cannot alloc %u bytes for inoinfo\n", 144124271Sgreen (unsigned)(sizeof(struct inostat) * inosused)); 145125115Sru inostathead[c].il_stat = info; 146124271Sgreen /* 147124271Sgreen * Scan the allocated inodes. 148124271Sgreen */ 149125115Sru for (i = 0; i < inosused; i++, inumber++) { 150125115Sru if (inumber < ROOTINO) { 151124271Sgreen (void)getnextinode(inumber); 152124271Sgreen continue; 153124271Sgreen } 154124271Sgreen checkinode(inumber, &idesc); 155125115Sru } 156125115Sru lastino += 1; 157125115Sru if (inosused < sblock.fs_ipg || inumber == lastino) 158125115Sru continue; 159124271Sgreen /* 160125115Sru * If we were not able to determine in advance which inodes 161124271Sgreen * were in use, then reduce the size of the inoinfo structure 162124271Sgreen * to the size necessary to describe the inodes that we 163124271Sgreen * really found. 164124271Sgreen */ 165124271Sgreen if (lastino < (c * sblock.fs_ipg)) 166124271Sgreen inosused = 0; 167124271Sgreen else 168124271Sgreen inosused = lastino - (c * sblock.fs_ipg); 169124271Sgreen inostathead[c].il_numalloced = inosused; 170124271Sgreen if (inosused == 0) { 171124271Sgreen free(inostathead[c].il_stat); 172124271Sgreen inostathead[c].il_stat = 0; 173124271Sgreen continue; 174124271Sgreen } 175124271Sgreen info = calloc((unsigned)inosused, sizeof(struct inostat)); 176124271Sgreen if (info == NULL) 177124271Sgreen pfatal("cannot alloc %u bytes for inoinfo\n", 178124271Sgreen (unsigned)(sizeof(struct inostat) * inosused)); 179124271Sgreen memmove(info, inostathead[c].il_stat, inosused * sizeof(*info)); 180124271Sgreen free(inostathead[c].il_stat); 181124271Sgreen inostathead[c].il_stat = info; 182124271Sgreen } 183124271Sgreen freeinodebuf(); 184124271Sgreen} 185124271Sgreen 186124271Sgreenstatic void 187125115Srucheckinode(ino_t inumber, struct inodesc *idesc) 188124271Sgreen{ 189124271Sgreen union dinode *dp; 190124271Sgreen struct zlncnt *zlnp; 191124271Sgreen off_t kernmaxfilesize; 192125115Sru ufs2_daddr_t ndb; 193124271Sgreen mode_t mode; 194124271Sgreen int j; 195124271Sgreen 196124271Sgreen dp = getnextinode(inumber); 197124271Sgreen mode = DIP(dp, di_mode) & IFMT; 198124271Sgreen if (mode == 0) { 199124271Sgreen if ((sblock.fs_magic == FS_UFS1_MAGIC && 200124271Sgreen (memcmp(dp->dp1.di_db, ufs1_zino.di_db, 201 NDADDR * sizeof(ufs1_daddr_t)) || 202 memcmp(dp->dp1.di_ib, ufs1_zino.di_ib, 203 NIADDR * sizeof(ufs1_daddr_t)) || 204 dp->dp1.di_mode || dp->dp1.di_size)) || 205 (sblock.fs_magic == FS_UFS2_MAGIC && 206 (memcmp(dp->dp2.di_db, ufs2_zino.di_db, 207 NDADDR * sizeof(ufs2_daddr_t)) || 208 memcmp(dp->dp2.di_ib, ufs2_zino.di_ib, 209 NIADDR * sizeof(ufs2_daddr_t)) || 210 dp->dp2.di_mode || dp->dp2.di_size))) { 211 pfatal("PARTIALLY ALLOCATED INODE I=%lu", 212 (u_long)inumber); 213 if (reply("CLEAR") == 1) { 214 dp = ginode(inumber); 215 clearinode(dp); 216 inodirty(); 217 } 218 } 219 inoinfo(inumber)->ino_state = USTATE; 220 return; 221 } 222 lastino = inumber; 223 /* This should match the file size limit in ffs_mountfs(). */ 224 if (sblock.fs_magic == FS_UFS1_MAGIC) 225 kernmaxfilesize = (off_t)0x40000000 * sblock.fs_bsize - 1; 226 else 227 kernmaxfilesize = sblock.fs_maxfilesize; 228 if (DIP(dp, di_size) > kernmaxfilesize || 229 DIP(dp, di_size) > sblock.fs_maxfilesize || 230 (mode == IFDIR && DIP(dp, di_size) > MAXDIRSIZE)) { 231 if (debug) 232 printf("bad size %ju:", (uintmax_t)DIP(dp, di_size)); 233 goto unknown; 234 } 235 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 236 dp = ginode(inumber); 237 DIP(dp, di_size) = sblock.fs_fsize; 238 DIP(dp, di_mode) = IFREG|0600; 239 inodirty(); 240 } 241 if ((mode == IFBLK || mode == IFCHR || mode == IFIFO || 242 mode == IFSOCK) && DIP(dp, di_size) != 0) { 243 if (debug) 244 printf("bad special-file size %ju:", 245 (uintmax_t)DIP(dp, di_size)); 246 goto unknown; 247 } 248 if ((mode == IFBLK || mode == IFCHR) && 249 (dev_t)DIP(dp, di_rdev) == NODEV) { 250 if (debug) 251 printf("bad special-file rdev NODEV:"); 252 goto unknown; 253 } 254 ndb = howmany(DIP(dp, di_size), sblock.fs_bsize); 255 if (ndb < 0) { 256 if (debug) 257 printf("bad size %ju ndb %ju:", 258 (uintmax_t)DIP(dp, di_size), (uintmax_t)ndb); 259 goto unknown; 260 } 261 if (mode == IFBLK || mode == IFCHR) 262 ndb++; 263 if (mode == IFLNK) { 264 /* 265 * Fake ndb value so direct/indirect block checks below 266 * will detect any garbage after symlink string. 267 */ 268 if (DIP(dp, di_size) < (off_t)sblock.fs_maxsymlinklen) { 269 if (sblock.fs_magic == FS_UFS1_MAGIC) 270 ndb = howmany(DIP(dp, di_size), 271 sizeof(ufs1_daddr_t)); 272 else 273 ndb = howmany(DIP(dp, di_size), 274 sizeof(ufs2_daddr_t)); 275 if (ndb > NDADDR) { 276 j = ndb - NDADDR; 277 for (ndb = 1; j > 1; j--) 278 ndb *= NINDIR(&sblock); 279 ndb += NDADDR; 280 } 281 } 282 } 283 for (j = ndb; ndb < NDADDR && j < NDADDR; j++) 284 if (DIP(dp, di_db[j]) != 0) { 285 if (debug) 286 printf("bad direct addr[%d]: %ju\n", j, 287 (uintmax_t)DIP(dp, di_db[j])); 288 goto unknown; 289 } 290 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 291 ndb /= NINDIR(&sblock); 292 for (; j < NIADDR; j++) 293 if (DIP(dp, di_ib[j]) != 0) { 294 if (debug) 295 printf("bad indirect addr: %ju\n", 296 (uintmax_t)DIP(dp, di_ib[j])); 297 goto unknown; 298 } 299 if (ftypeok(dp) == 0) 300 goto unknown; 301 n_files++; 302 inoinfo(inumber)->ino_linkcnt = DIP(dp, di_nlink); 303 if (DIP(dp, di_nlink) <= 0) { 304 zlnp = (struct zlncnt *)malloc(sizeof *zlnp); 305 if (zlnp == NULL) { 306 pfatal("LINK COUNT TABLE OVERFLOW"); 307 if (reply("CONTINUE") == 0) { 308 ckfini(0); 309 exit(EEXIT); 310 } 311 } else { 312 zlnp->zlncnt = inumber; 313 zlnp->next = zlnhead; 314 zlnhead = zlnp; 315 } 316 } 317 if (mode == IFDIR) { 318 if (DIP(dp, di_size) == 0) 319 inoinfo(inumber)->ino_state = DCLEAR; 320 else 321 inoinfo(inumber)->ino_state = DSTATE; 322 cacheino(dp, inumber); 323 countdirs++; 324 } else 325 inoinfo(inumber)->ino_state = FSTATE; 326 inoinfo(inumber)->ino_type = IFTODT(mode); 327 badblk = dupblk = 0; 328 idesc->id_number = inumber; 329 if (DIP(dp, di_flags) & SF_SNAPSHOT) 330 idesc->id_type = SNAP; 331 else 332 idesc->id_type = ADDR; 333 (void)ckinode(dp, idesc); 334 idesc->id_entryno *= btodb(sblock.fs_fsize); 335 if (DIP(dp, di_blocks) != idesc->id_entryno) { 336 pwarn("INCORRECT BLOCK COUNT I=%lu (%ju should be %ju)", 337 (u_long)inumber, (uintmax_t)DIP(dp, di_blocks), 338 (uintmax_t)idesc->id_entryno); 339 if (preen) 340 printf(" (CORRECTED)\n"); 341 else if (reply("CORRECT") == 0) 342 return; 343 if (bkgrdflag == 0) { 344 dp = ginode(inumber); 345 DIP(dp, di_blocks) = idesc->id_entryno; 346 inodirty(); 347 } else { 348 cmd.value = idesc->id_number; 349 cmd.size = idesc->id_entryno - DIP(dp, di_blocks); 350 if (debug) 351 printf("adjblkcnt ino %ju amount %lld\n", 352 (uintmax_t)cmd.value, (long long)cmd.size); 353 if (sysctl(adjblkcnt, MIBSIZE, 0, 0, 354 &cmd, sizeof cmd) == -1) 355 rwerror("ADJUST INODE BLOCK COUNT", cmd.value); 356 } 357 } 358 return; 359unknown: 360 pfatal("UNKNOWN FILE TYPE I=%lu", (u_long)inumber); 361 inoinfo(inumber)->ino_state = FCLEAR; 362 if (reply("CLEAR") == 1) { 363 inoinfo(inumber)->ino_state = USTATE; 364 dp = ginode(inumber); 365 clearinode(dp); 366 inodirty(); 367 } 368} 369 370int 371pass1check(struct inodesc *idesc) 372{ 373 int res = KEEPON; 374 int anyout, nfrags; 375 ufs2_daddr_t blkno = idesc->id_blkno; 376 struct dups *dlp; 377 struct dups *new; 378 379 if (idesc->id_type == SNAP) { 380 if (blkno == BLK_NOCOPY) 381 return (KEEPON); 382 if (idesc->id_number == cursnapshot) { 383 if (blkno == blkstofrags(&sblock, idesc->id_lbn)) 384 return (KEEPON); 385 if (blkno == BLK_SNAP) { 386 blkno = blkstofrags(&sblock, idesc->id_lbn); 387 idesc->id_entryno -= idesc->id_numfrags; 388 } 389 } else { 390 if (blkno == BLK_SNAP) 391 return (KEEPON); 392 } 393 } 394 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 395 blkerror(idesc->id_number, "BAD", blkno); 396 if (badblk++ >= MAXBAD) { 397 pwarn("EXCESSIVE BAD BLKS I=%lu", 398 (u_long)idesc->id_number); 399 if (preen) 400 printf(" (SKIPPING)\n"); 401 else if (reply("CONTINUE") == 0) { 402 ckfini(0); 403 exit(EEXIT); 404 } 405 return (STOP); 406 } 407 } 408 for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { 409 if (anyout && chkrange(blkno, 1)) { 410 res = SKIP; 411 } else if (!testbmap(blkno)) { 412 n_blks++; 413 setbmap(blkno); 414 } else { 415 blkerror(idesc->id_number, "DUP", blkno); 416 if (dupblk++ >= MAXDUP) { 417 pwarn("EXCESSIVE DUP BLKS I=%lu", 418 (u_long)idesc->id_number); 419 if (preen) 420 printf(" (SKIPPING)\n"); 421 else if (reply("CONTINUE") == 0) { 422 ckfini(0); 423 exit(EEXIT); 424 } 425 return (STOP); 426 } 427 new = (struct dups *)malloc(sizeof(struct dups)); 428 if (new == NULL) { 429 pfatal("DUP TABLE OVERFLOW."); 430 if (reply("CONTINUE") == 0) { 431 ckfini(0); 432 exit(EEXIT); 433 } 434 return (STOP); 435 } 436 new->dup = blkno; 437 if (muldup == 0) { 438 duplist = muldup = new; 439 new->next = 0; 440 } else { 441 new->next = muldup->next; 442 muldup->next = new; 443 } 444 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 445 if (dlp->dup == blkno) 446 break; 447 if (dlp == muldup && dlp->dup != blkno) 448 muldup = new; 449 } 450 /* 451 * count the number of blocks found in id_entryno 452 */ 453 idesc->id_entryno++; 454 } 455 return (res); 456} 457