pass1.c revision 71884
18871Srgrimes/* 21558Srgrimes * Copyright (c) 1980, 1986, 1993 31558Srgrimes * The Regents of the University of California. All rights reserved. 41558Srgrimes * 51558Srgrimes * Redistribution and use in source and binary forms, with or without 61558Srgrimes * modification, are permitted provided that the following conditions 71558Srgrimes * are met: 81558Srgrimes * 1. Redistributions of source code must retain the above copyright 91558Srgrimes * notice, this list of conditions and the following disclaimer. 101558Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111558Srgrimes * notice, this list of conditions and the following disclaimer in the 121558Srgrimes * documentation and/or other materials provided with the distribution. 131558Srgrimes * 3. All advertising materials mentioning features or use of this software 141558Srgrimes * must display the following acknowledgement: 151558Srgrimes * This product includes software developed by the University of 161558Srgrimes * California, Berkeley and its contributors. 171558Srgrimes * 4. Neither the name of the University nor the names of its contributors 181558Srgrimes * may be used to endorse or promote products derived from this software 191558Srgrimes * without specific prior written permission. 201558Srgrimes * 211558Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221558Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231558Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241558Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251558Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261558Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271558Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281558Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291558Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301558Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 311558Srgrimes * SUCH DAMAGE. 321558Srgrimes */ 331558Srgrimes 341558Srgrimes#ifndef lint 3541477Sjulian#if 0 3623675Speterstatic const char sccsid[] = "@(#)pass1.c 8.6 (Berkeley) 4/28/95"; 3741477Sjulian#endif 3841477Sjulianstatic const char rcsid[] = 3950476Speter "$FreeBSD: head/sbin/fsck_ffs/pass1.c 71884 2001-01-31 15:16:56Z iedowse $"; 401558Srgrimes#endif /* not lint */ 411558Srgrimes 421558Srgrimes#include <sys/param.h> 4362668Smckusick#include <sys/stat.h> 4423675Speter 451558Srgrimes#include <ufs/ufs/dinode.h> 461558Srgrimes#include <ufs/ufs/dir.h> 471558Srgrimes#include <ufs/ffs/fs.h> 4823675Speter 4923675Speter#include <err.h> 501558Srgrimes#include <string.h> 5123675Speter 521558Srgrimes#include "fsck.h" 531558Srgrimes 5423675Speterstatic ufs_daddr_t badblk; 5523675Speterstatic ufs_daddr_t dupblk; 5641474Sjulianstatic ino_t lastino; /* last inode in use */ 571558Srgrimes 5823675Speterstatic void checkinode __P((ino_t inumber, struct inodesc *)); 597585Sbde 607585Sbdevoid 611558Srgrimespass1() 621558Srgrimes{ 6341474Sjulian u_int8_t *cp; 641558Srgrimes ino_t inumber; 6541474Sjulian int c, i, cgd, inosused; 6641474Sjulian struct inostat *info; 671558Srgrimes struct inodesc idesc; 681558Srgrimes 691558Srgrimes /* 701558Srgrimes * Set file system reserved blocks in used block map. 711558Srgrimes */ 721558Srgrimes for (c = 0; c < sblock.fs_ncg; c++) { 731558Srgrimes cgd = cgdmin(&sblock, c); 741558Srgrimes if (c == 0) { 751558Srgrimes i = cgbase(&sblock, c); 761558Srgrimes } else 771558Srgrimes i = cgsblock(&sblock, c); 781558Srgrimes for (; i < cgd; i++) 791558Srgrimes setbmap(i); 801558Srgrimes } 8169800Stomsoft i = sblock.fs_csaddr; 8269800Stomsoft cgd = i + howmany(sblock.fs_cssize, sblock.fs_fsize); 8369800Stomsoft for (; i < cgd; i++) 8469800Stomsoft setbmap(i); 8569800Stomsoft 861558Srgrimes /* 871558Srgrimes * Find all allocated blocks. 881558Srgrimes */ 8923675Speter memset(&idesc, 0, sizeof(struct inodesc)); 901558Srgrimes idesc.id_func = pass1check; 911558Srgrimes n_files = n_blks = 0; 921558Srgrimes for (c = 0; c < sblock.fs_ncg; c++) { 9341474Sjulian inumber = c * sblock.fs_ipg; 9441474Sjulian setinodebuf(inumber); 9541474Sjulian inosused = sblock.fs_ipg; 9670050Siedowse if (got_siginfo) { 9770050Siedowse printf("%s: phase 1: cyl group %d of %d (%d%%)\n", 9870050Siedowse cdevname, c, sblock.fs_ncg, 9970050Siedowse c * 100 / sblock.fs_ncg); 10070050Siedowse got_siginfo = 0; 10170050Siedowse } 10241474Sjulian /* 10341474Sjulian * If we are using soft updates, then we can trust the 10441474Sjulian * cylinder group inode allocation maps to tell us which 10541474Sjulian * inodes are allocated. We will scan the used inode map 10641474Sjulian * to find the inodes that are really in use, and then 10741474Sjulian * read only those inodes in from disk. 10841474Sjulian */ 10941474Sjulian if (preen && usedsoftdep) { 11041474Sjulian getblk(&cgblk, cgtod(&sblock, c), sblock.fs_cgsize); 11141474Sjulian if (!cg_chkmagic(&cgrp)) 11241474Sjulian pfatal("CG %d: BAD MAGIC NUMBER\n", c); 11341474Sjulian cp = &cg_inosused(&cgrp)[(sblock.fs_ipg - 1) / NBBY]; 11441474Sjulian for ( ; inosused > 0; inosused -= NBBY, cp--) { 11541474Sjulian if (*cp == 0) 11641474Sjulian continue; 11741474Sjulian for (i = 1 << (NBBY - 1); i > 0; i >>= 1) { 11841474Sjulian if (*cp & i) 11941474Sjulian break; 12041474Sjulian inosused--; 12141474Sjulian } 12241474Sjulian break; 12341474Sjulian } 12441474Sjulian if (inosused < 0) 12541474Sjulian inosused = 0; 12641474Sjulian } 12741474Sjulian /* 12841474Sjulian * Allocate inoinfo structures for the allocated inodes. 12941474Sjulian */ 13041474Sjulian inostathead[c].il_numalloced = inosused; 13141474Sjulian if (inosused == 0) { 13241474Sjulian inostathead[c].il_stat = 0; 13341474Sjulian continue; 13441474Sjulian } 13541474Sjulian info = calloc((unsigned)inosused, sizeof(struct inostat)); 13641474Sjulian if (info == NULL) 13741474Sjulian pfatal("cannot alloc %u bytes for inoinfo\n", 13841474Sjulian (unsigned)(sizeof(struct inostat) * inosused)); 13941474Sjulian inostathead[c].il_stat = info; 14041474Sjulian /* 14141474Sjulian * Scan the allocated inodes. 14241474Sjulian */ 14341474Sjulian for (i = 0; i < inosused; i++, inumber++) { 14441474Sjulian if (inumber < ROOTINO) { 14541474Sjulian (void)getnextinode(inumber); 1461558Srgrimes continue; 14741474Sjulian } 1481558Srgrimes checkinode(inumber, &idesc); 1491558Srgrimes } 15041474Sjulian lastino += 1; 15141474Sjulian if (inosused < sblock.fs_ipg || inumber == lastino) 15241474Sjulian continue; 15341474Sjulian /* 15441474Sjulian * If we were not able to determine in advance which inodes 15541474Sjulian * were in use, then reduce the size of the inoinfo structure 15641474Sjulian * to the size necessary to describe the inodes that we 15741474Sjulian * really found. 15841474Sjulian */ 15941474Sjulian inosused = lastino - (c * sblock.fs_ipg); 16041474Sjulian if (inosused < 0) 16141474Sjulian inosused = 0; 16241474Sjulian inostathead[c].il_numalloced = inosused; 16341474Sjulian if (inosused == 0) { 16441474Sjulian free(inostathead[c].il_stat); 16541474Sjulian inostathead[c].il_stat = 0; 16641474Sjulian continue; 16741474Sjulian } 16841474Sjulian info = calloc((unsigned)inosused, sizeof(struct inostat)); 16941474Sjulian if (info == NULL) 17041474Sjulian pfatal("cannot alloc %u bytes for inoinfo\n", 17141474Sjulian (unsigned)(sizeof(struct inostat) * inosused)); 17241474Sjulian memmove(info, inostathead[c].il_stat, inosused * sizeof(*info)); 17341474Sjulian free(inostathead[c].il_stat); 17441474Sjulian inostathead[c].il_stat = info; 1751558Srgrimes } 1761558Srgrimes freeinodebuf(); 1771558Srgrimes} 1781558Srgrimes 17923675Speterstatic void 1801558Srgrimescheckinode(inumber, idesc) 1811558Srgrimes ino_t inumber; 1821558Srgrimes register struct inodesc *idesc; 1831558Srgrimes{ 1841558Srgrimes register struct dinode *dp; 1851558Srgrimes struct zlncnt *zlnp; 18671884Siedowse u_int64_t kernmaxfilesize; 18771884Siedowse ufs_daddr_t ndb, j; 1881558Srgrimes mode_t mode; 1892603Sdg char *symbuf; 1901558Srgrimes 1911558Srgrimes dp = getnextinode(inumber); 1921558Srgrimes mode = dp->di_mode & IFMT; 1931558Srgrimes if (mode == 0) { 19423675Speter if (memcmp(dp->di_db, zino.di_db, 19523675Speter NDADDR * sizeof(ufs_daddr_t)) || 19623675Speter memcmp(dp->di_ib, zino.di_ib, 19723675Speter NIADDR * sizeof(ufs_daddr_t)) || 1981558Srgrimes dp->di_mode || dp->di_size) { 1991558Srgrimes pfatal("PARTIALLY ALLOCATED INODE I=%lu", inumber); 2001558Srgrimes if (reply("CLEAR") == 1) { 2011558Srgrimes dp = ginode(inumber); 2021558Srgrimes clearinode(dp); 2031558Srgrimes inodirty(); 2041558Srgrimes } 2051558Srgrimes } 20641474Sjulian inoinfo(inumber)->ino_state = USTATE; 2071558Srgrimes return; 2081558Srgrimes } 2091558Srgrimes lastino = inumber; 21071884Siedowse /* This should match the file size limit in ffs_mountfs(). */ 21171884Siedowse kernmaxfilesize = (u_int64_t)0x40000000 * sblock.fs_bsize - 1; 21271884Siedowse if (dp->di_size > kernmaxfilesize || 21371884Siedowse dp->di_size > sblock.fs_maxfilesize || 21423999Speter (mode == IFDIR && dp->di_size > MAXDIRSIZE)) { 2151558Srgrimes if (debug) 2161558Srgrimes printf("bad size %qu:", dp->di_size); 2171558Srgrimes goto unknown; 2181558Srgrimes } 2191558Srgrimes if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 2201558Srgrimes dp = ginode(inumber); 2211558Srgrimes dp->di_size = sblock.fs_fsize; 2221558Srgrimes dp->di_mode = IFREG|0600; 2231558Srgrimes inodirty(); 2241558Srgrimes } 22563003Smckusick if ((mode == IFBLK || mode == IFCHR || mode == IFIFO || 22663003Smckusick mode == IFSOCK) && dp->di_size != 0) { 22763003Smckusick if (debug) 22863003Smckusick printf("bad special-file size %qu:", dp->di_size); 22963003Smckusick goto unknown; 23063003Smckusick } 2311558Srgrimes ndb = howmany(dp->di_size, sblock.fs_bsize); 2321558Srgrimes if (ndb < 0) { 2331558Srgrimes if (debug) 2341558Srgrimes printf("bad size %qu ndb %d:", 2351558Srgrimes dp->di_size, ndb); 2361558Srgrimes goto unknown; 2371558Srgrimes } 2381558Srgrimes if (mode == IFBLK || mode == IFCHR) 2391558Srgrimes ndb++; 2401558Srgrimes if (mode == IFLNK) { 2411558Srgrimes if (doinglevel2 && 2421558Srgrimes dp->di_size > 0 && dp->di_size < MAXSYMLINKLEN && 2431558Srgrimes dp->di_blocks != 0) { 2442603Sdg symbuf = alloca(secsize); 2451558Srgrimes if (bread(fsreadfd, symbuf, 2461558Srgrimes fsbtodb(&sblock, dp->di_db[0]), 2472603Sdg (long)secsize) != 0) 24823675Speter errx(EEXIT, "cannot read symlink"); 2491558Srgrimes if (debug) { 2501558Srgrimes symbuf[dp->di_size] = 0; 25137236Sbde printf("convert symlink %lu(%s) of size %ld\n", 25241474Sjulian (u_long)inumber, symbuf, (long)dp->di_size); 2531558Srgrimes } 2541558Srgrimes dp = ginode(inumber); 25523675Speter memmove(dp->di_shortlink, symbuf, (long)dp->di_size); 2561558Srgrimes dp->di_blocks = 0; 2571558Srgrimes inodirty(); 2581558Srgrimes } 2591558Srgrimes /* 2601558Srgrimes * Fake ndb value so direct/indirect block checks below 2611558Srgrimes * will detect any garbage after symlink string. 2621558Srgrimes */ 26341474Sjulian if (dp->di_size < sblock.fs_maxsymlinklen) { 26423675Speter ndb = howmany(dp->di_size, sizeof(ufs_daddr_t)); 2651558Srgrimes if (ndb > NDADDR) { 2661558Srgrimes j = ndb - NDADDR; 2671558Srgrimes for (ndb = 1; j > 1; j--) 2681558Srgrimes ndb *= NINDIR(&sblock); 2691558Srgrimes ndb += NDADDR; 2701558Srgrimes } 2711558Srgrimes } 2721558Srgrimes } 2731558Srgrimes for (j = ndb; j < NDADDR; j++) 2741558Srgrimes if (dp->di_db[j] != 0) { 2751558Srgrimes if (debug) 27637236Sbde printf("bad direct addr: %ld\n", 27737236Sbde (long)dp->di_db[j]); 2781558Srgrimes goto unknown; 2791558Srgrimes } 2801558Srgrimes for (j = 0, ndb -= NDADDR; ndb > 0; j++) 2811558Srgrimes ndb /= NINDIR(&sblock); 2821558Srgrimes for (; j < NIADDR; j++) 2831558Srgrimes if (dp->di_ib[j] != 0) { 2841558Srgrimes if (debug) 2851558Srgrimes printf("bad indirect addr: %ld\n", 28637236Sbde (long)dp->di_ib[j]); 2871558Srgrimes goto unknown; 2881558Srgrimes } 2891558Srgrimes if (ftypeok(dp) == 0) 2901558Srgrimes goto unknown; 2911558Srgrimes n_files++; 29241474Sjulian inoinfo(inumber)->ino_linkcnt = dp->di_nlink; 2931558Srgrimes if (dp->di_nlink <= 0) { 2941558Srgrimes zlnp = (struct zlncnt *)malloc(sizeof *zlnp); 2951558Srgrimes if (zlnp == NULL) { 2961558Srgrimes pfatal("LINK COUNT TABLE OVERFLOW"); 29734266Sjulian if (reply("CONTINUE") == 0) { 29834266Sjulian ckfini(0); 29923675Speter exit(EEXIT); 30034266Sjulian } 3011558Srgrimes } else { 3021558Srgrimes zlnp->zlncnt = inumber; 3031558Srgrimes zlnp->next = zlnhead; 3041558Srgrimes zlnhead = zlnp; 3051558Srgrimes } 3061558Srgrimes } 3071558Srgrimes if (mode == IFDIR) { 3081558Srgrimes if (dp->di_size == 0) 30941474Sjulian inoinfo(inumber)->ino_state = DCLEAR; 3101558Srgrimes else 31141474Sjulian inoinfo(inumber)->ino_state = DSTATE; 3121558Srgrimes cacheino(dp, inumber); 31341474Sjulian countdirs++; 3141558Srgrimes } else 31541474Sjulian inoinfo(inumber)->ino_state = FSTATE; 31641474Sjulian inoinfo(inumber)->ino_type = IFTODT(mode); 3171558Srgrimes if (doinglevel2 && 3181558Srgrimes (dp->di_ouid != (u_short)-1 || dp->di_ogid != (u_short)-1)) { 3191558Srgrimes dp = ginode(inumber); 3201558Srgrimes dp->di_uid = dp->di_ouid; 3211558Srgrimes dp->di_ouid = -1; 3221558Srgrimes dp->di_gid = dp->di_ogid; 3231558Srgrimes dp->di_ogid = -1; 3241558Srgrimes inodirty(); 3251558Srgrimes } 3261558Srgrimes badblk = dupblk = 0; 3271558Srgrimes idesc->id_number = inumber; 32862668Smckusick if (dp->di_flags & SF_SNAPSHOT) 32962668Smckusick idesc->id_type = SNAP; 33062668Smckusick else 33162668Smckusick idesc->id_type = ADDR; 3321558Srgrimes (void)ckinode(dp, idesc); 3331558Srgrimes idesc->id_entryno *= btodb(sblock.fs_fsize); 3341558Srgrimes if (dp->di_blocks != idesc->id_entryno) { 3351558Srgrimes pwarn("INCORRECT BLOCK COUNT I=%lu (%ld should be %ld)", 3361558Srgrimes inumber, dp->di_blocks, idesc->id_entryno); 3371558Srgrimes if (preen) 3381558Srgrimes printf(" (CORRECTED)\n"); 3391558Srgrimes else if (reply("CORRECT") == 0) 3401558Srgrimes return; 3411558Srgrimes dp = ginode(inumber); 3421558Srgrimes dp->di_blocks = idesc->id_entryno; 3431558Srgrimes inodirty(); 3441558Srgrimes } 3451558Srgrimes return; 3461558Srgrimesunknown: 3471558Srgrimes pfatal("UNKNOWN FILE TYPE I=%lu", inumber); 34841474Sjulian inoinfo(inumber)->ino_state = FCLEAR; 3491558Srgrimes if (reply("CLEAR") == 1) { 35041474Sjulian inoinfo(inumber)->ino_state = USTATE; 3511558Srgrimes dp = ginode(inumber); 3521558Srgrimes clearinode(dp); 3531558Srgrimes inodirty(); 3541558Srgrimes } 3551558Srgrimes} 3561558Srgrimes 3577585Sbdeint 3581558Srgrimespass1check(idesc) 3591558Srgrimes register struct inodesc *idesc; 3601558Srgrimes{ 3611558Srgrimes int res = KEEPON; 3621558Srgrimes int anyout, nfrags; 36323675Speter ufs_daddr_t blkno = idesc->id_blkno; 3641558Srgrimes register struct dups *dlp; 3651558Srgrimes struct dups *new; 3661558Srgrimes 36762668Smckusick if (idesc->id_type == SNAP) { 36862668Smckusick if (blkno == BLK_NOCOPY) 36962668Smckusick return (KEEPON); 37062668Smckusick if (idesc->id_number == cursnapshot) { 37162668Smckusick if (blkno == blkstofrags(&sblock, idesc->id_lbn)) 37262668Smckusick return (KEEPON); 37362668Smckusick if (blkno == BLK_SNAP) { 37462668Smckusick blkno = blkstofrags(&sblock, idesc->id_lbn); 37562668Smckusick idesc->id_entryno -= idesc->id_numfrags; 37662668Smckusick } 37762668Smckusick } else { 37862668Smckusick if (blkno == BLK_SNAP) 37962668Smckusick return (KEEPON); 38062668Smckusick } 38162668Smckusick } 3821558Srgrimes if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 3831558Srgrimes blkerror(idesc->id_number, "BAD", blkno); 3841558Srgrimes if (badblk++ >= MAXBAD) { 3851558Srgrimes pwarn("EXCESSIVE BAD BLKS I=%lu", 3861558Srgrimes idesc->id_number); 3871558Srgrimes if (preen) 3881558Srgrimes printf(" (SKIPPING)\n"); 38934266Sjulian else if (reply("CONTINUE") == 0) { 39034266Sjulian ckfini(0); 39123675Speter exit(EEXIT); 39234266Sjulian } 3931558Srgrimes return (STOP); 3941558Srgrimes } 3951558Srgrimes } 3961558Srgrimes for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { 3971558Srgrimes if (anyout && chkrange(blkno, 1)) { 3981558Srgrimes res = SKIP; 3991558Srgrimes } else if (!testbmap(blkno)) { 4001558Srgrimes n_blks++; 4011558Srgrimes setbmap(blkno); 4021558Srgrimes } else { 4031558Srgrimes blkerror(idesc->id_number, "DUP", blkno); 4041558Srgrimes if (dupblk++ >= MAXDUP) { 4051558Srgrimes pwarn("EXCESSIVE DUP BLKS I=%lu", 4061558Srgrimes idesc->id_number); 4071558Srgrimes if (preen) 4081558Srgrimes printf(" (SKIPPING)\n"); 40934266Sjulian else if (reply("CONTINUE") == 0) { 41034266Sjulian ckfini(0); 41123675Speter exit(EEXIT); 41234266Sjulian } 4131558Srgrimes return (STOP); 4141558Srgrimes } 4151558Srgrimes new = (struct dups *)malloc(sizeof(struct dups)); 4161558Srgrimes if (new == NULL) { 4171558Srgrimes pfatal("DUP TABLE OVERFLOW."); 41834266Sjulian if (reply("CONTINUE") == 0) { 41934266Sjulian ckfini(0); 42023675Speter exit(EEXIT); 42134266Sjulian } 4221558Srgrimes return (STOP); 4231558Srgrimes } 4241558Srgrimes new->dup = blkno; 4251558Srgrimes if (muldup == 0) { 4261558Srgrimes duplist = muldup = new; 4271558Srgrimes new->next = 0; 4281558Srgrimes } else { 4291558Srgrimes new->next = muldup->next; 4301558Srgrimes muldup->next = new; 4311558Srgrimes } 4321558Srgrimes for (dlp = duplist; dlp != muldup; dlp = dlp->next) 4331558Srgrimes if (dlp->dup == blkno) 4341558Srgrimes break; 4351558Srgrimes if (dlp == muldup && dlp->dup != blkno) 4361558Srgrimes muldup = new; 4371558Srgrimes } 4381558Srgrimes /* 4391558Srgrimes * count the number of blocks found in id_entryno 4401558Srgrimes */ 4411558Srgrimes idesc->id_entryno++; 4421558Srgrimes } 4431558Srgrimes return (res); 4441558Srgrimes} 445