pass1.c revision 41474
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 3523675Speterstatic const char sccsid[] = "@(#)pass1.c 8.6 (Berkeley) 4/28/95"; 361558Srgrimes#endif /* not lint */ 371558Srgrimes 381558Srgrimes#include <sys/param.h> 3941474Sjulian#include <sys/time.h> 4023675Speter 411558Srgrimes#include <ufs/ufs/dinode.h> 421558Srgrimes#include <ufs/ufs/dir.h> 431558Srgrimes#include <ufs/ffs/fs.h> 4423675Speter 4523675Speter#include <err.h> 461558Srgrimes#include <string.h> 4723675Speter 481558Srgrimes#include "fsck.h" 491558Srgrimes 5023675Speterstatic ufs_daddr_t badblk; 5123675Speterstatic ufs_daddr_t dupblk; 5241474Sjulianstatic ino_t lastino; /* last inode in use */ 531558Srgrimes 5423675Speterstatic void checkinode __P((ino_t inumber, struct inodesc *)); 557585Sbde 567585Sbdevoid 571558Srgrimespass1() 581558Srgrimes{ 5941474Sjulian u_int8_t *cp; 601558Srgrimes ino_t inumber; 6141474Sjulian int c, i, cgd, inosused; 6241474Sjulian struct inostat *info; 631558Srgrimes struct inodesc idesc; 641558Srgrimes 651558Srgrimes /* 661558Srgrimes * Set file system reserved blocks in used block map. 671558Srgrimes */ 681558Srgrimes for (c = 0; c < sblock.fs_ncg; c++) { 691558Srgrimes cgd = cgdmin(&sblock, c); 701558Srgrimes if (c == 0) { 711558Srgrimes i = cgbase(&sblock, c); 721558Srgrimes cgd += howmany(sblock.fs_cssize, sblock.fs_fsize); 731558Srgrimes } else 741558Srgrimes i = cgsblock(&sblock, c); 751558Srgrimes for (; i < cgd; i++) 761558Srgrimes setbmap(i); 771558Srgrimes } 781558Srgrimes /* 791558Srgrimes * Find all allocated blocks. 801558Srgrimes */ 8123675Speter memset(&idesc, 0, sizeof(struct inodesc)); 821558Srgrimes idesc.id_type = ADDR; 831558Srgrimes idesc.id_func = pass1check; 841558Srgrimes n_files = n_blks = 0; 851558Srgrimes for (c = 0; c < sblock.fs_ncg; c++) { 8641474Sjulian inumber = c * sblock.fs_ipg; 8741474Sjulian setinodebuf(inumber); 8841474Sjulian inosused = sblock.fs_ipg; 8941474Sjulian /* 9041474Sjulian * If we are using soft updates, then we can trust the 9141474Sjulian * cylinder group inode allocation maps to tell us which 9241474Sjulian * inodes are allocated. We will scan the used inode map 9341474Sjulian * to find the inodes that are really in use, and then 9441474Sjulian * read only those inodes in from disk. 9541474Sjulian */ 9641474Sjulian if (preen && usedsoftdep) { 9741474Sjulian getblk(&cgblk, cgtod(&sblock, c), sblock.fs_cgsize); 9841474Sjulian if (!cg_chkmagic(&cgrp)) 9941474Sjulian pfatal("CG %d: BAD MAGIC NUMBER\n", c); 10041474Sjulian cp = &cg_inosused(&cgrp)[(sblock.fs_ipg - 1) / NBBY]; 10141474Sjulian for ( ; inosused > 0; inosused -= NBBY, cp--) { 10241474Sjulian if (*cp == 0) 10341474Sjulian continue; 10441474Sjulian for (i = 1 << (NBBY - 1); i > 0; i >>= 1) { 10541474Sjulian if (*cp & i) 10641474Sjulian break; 10741474Sjulian inosused--; 10841474Sjulian } 10941474Sjulian break; 11041474Sjulian } 11141474Sjulian if (inosused < 0) 11241474Sjulian inosused = 0; 11341474Sjulian } 11441474Sjulian /* 11541474Sjulian * Allocate inoinfo structures for the allocated inodes. 11641474Sjulian */ 11741474Sjulian inostathead[c].il_numalloced = inosused; 11841474Sjulian if (inosused == 0) { 11941474Sjulian inostathead[c].il_stat = 0; 12041474Sjulian continue; 12141474Sjulian } 12241474Sjulian info = calloc((unsigned)inosused, sizeof(struct inostat)); 12341474Sjulian if (info == NULL) 12441474Sjulian pfatal("cannot alloc %u bytes for inoinfo\n", 12541474Sjulian (unsigned)(sizeof(struct inostat) * inosused)); 12641474Sjulian inostathead[c].il_stat = info; 12741474Sjulian /* 12841474Sjulian * Scan the allocated inodes. 12941474Sjulian */ 13041474Sjulian for (i = 0; i < inosused; i++, inumber++) { 13141474Sjulian if (inumber < ROOTINO) { 13241474Sjulian (void)getnextinode(inumber); 1331558Srgrimes continue; 13441474Sjulian } 1351558Srgrimes checkinode(inumber, &idesc); 1361558Srgrimes } 13741474Sjulian lastino += 1; 13841474Sjulian if (inosused < sblock.fs_ipg || inumber == lastino) 13941474Sjulian continue; 14041474Sjulian /* 14141474Sjulian * If we were not able to determine in advance which inodes 14241474Sjulian * were in use, then reduce the size of the inoinfo structure 14341474Sjulian * to the size necessary to describe the inodes that we 14441474Sjulian * really found. 14541474Sjulian */ 14641474Sjulian inosused = lastino - (c * sblock.fs_ipg); 14741474Sjulian if (inosused < 0) 14841474Sjulian inosused = 0; 14941474Sjulian inostathead[c].il_numalloced = inosused; 15041474Sjulian if (inosused == 0) { 15141474Sjulian free(inostathead[c].il_stat); 15241474Sjulian inostathead[c].il_stat = 0; 15341474Sjulian continue; 15441474Sjulian } 15541474Sjulian info = calloc((unsigned)inosused, sizeof(struct inostat)); 15641474Sjulian if (info == NULL) 15741474Sjulian pfatal("cannot alloc %u bytes for inoinfo\n", 15841474Sjulian (unsigned)(sizeof(struct inostat) * inosused)); 15941474Sjulian memmove(info, inostathead[c].il_stat, inosused * sizeof(*info)); 16041474Sjulian free(inostathead[c].il_stat); 16141474Sjulian inostathead[c].il_stat = info; 1621558Srgrimes } 1631558Srgrimes freeinodebuf(); 1641558Srgrimes} 1651558Srgrimes 16623675Speterstatic void 1671558Srgrimescheckinode(inumber, idesc) 1681558Srgrimes ino_t inumber; 1691558Srgrimes register struct inodesc *idesc; 1701558Srgrimes{ 1711558Srgrimes register struct dinode *dp; 1721558Srgrimes struct zlncnt *zlnp; 1731558Srgrimes int ndb, j; 1741558Srgrimes mode_t mode; 1752603Sdg char *symbuf; 1761558Srgrimes 1771558Srgrimes dp = getnextinode(inumber); 1781558Srgrimes mode = dp->di_mode & IFMT; 1791558Srgrimes if (mode == 0) { 18023675Speter if (memcmp(dp->di_db, zino.di_db, 18123675Speter NDADDR * sizeof(ufs_daddr_t)) || 18223675Speter memcmp(dp->di_ib, zino.di_ib, 18323675Speter NIADDR * sizeof(ufs_daddr_t)) || 1841558Srgrimes dp->di_mode || dp->di_size) { 1851558Srgrimes pfatal("PARTIALLY ALLOCATED INODE I=%lu", inumber); 1861558Srgrimes if (reply("CLEAR") == 1) { 1871558Srgrimes dp = ginode(inumber); 1881558Srgrimes clearinode(dp); 1891558Srgrimes inodirty(); 1901558Srgrimes } 1911558Srgrimes } 19241474Sjulian inoinfo(inumber)->ino_state = USTATE; 1931558Srgrimes return; 1941558Srgrimes } 1951558Srgrimes lastino = inumber; 1961558Srgrimes if (/* dp->di_size < 0 || */ 19723999Speter dp->di_size + sblock.fs_bsize - 1 < dp->di_size || 19823999Speter (mode == IFDIR && dp->di_size > MAXDIRSIZE)) { 1991558Srgrimes if (debug) 2001558Srgrimes printf("bad size %qu:", dp->di_size); 2011558Srgrimes goto unknown; 2021558Srgrimes } 2031558Srgrimes if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 2041558Srgrimes dp = ginode(inumber); 2051558Srgrimes dp->di_size = sblock.fs_fsize; 2061558Srgrimes dp->di_mode = IFREG|0600; 2071558Srgrimes inodirty(); 2081558Srgrimes } 2091558Srgrimes ndb = howmany(dp->di_size, sblock.fs_bsize); 2101558Srgrimes if (ndb < 0) { 2111558Srgrimes if (debug) 2121558Srgrimes printf("bad size %qu ndb %d:", 2131558Srgrimes dp->di_size, ndb); 2141558Srgrimes goto unknown; 2151558Srgrimes } 2161558Srgrimes if (mode == IFBLK || mode == IFCHR) 2171558Srgrimes ndb++; 2181558Srgrimes if (mode == IFLNK) { 2191558Srgrimes if (doinglevel2 && 2201558Srgrimes dp->di_size > 0 && dp->di_size < MAXSYMLINKLEN && 2211558Srgrimes dp->di_blocks != 0) { 2222603Sdg symbuf = alloca(secsize); 2231558Srgrimes if (bread(fsreadfd, symbuf, 2241558Srgrimes fsbtodb(&sblock, dp->di_db[0]), 2252603Sdg (long)secsize) != 0) 22623675Speter errx(EEXIT, "cannot read symlink"); 2271558Srgrimes if (debug) { 2281558Srgrimes symbuf[dp->di_size] = 0; 22937236Sbde printf("convert symlink %lu(%s) of size %ld\n", 23041474Sjulian (u_long)inumber, symbuf, (long)dp->di_size); 2311558Srgrimes } 2321558Srgrimes dp = ginode(inumber); 23323675Speter memmove(dp->di_shortlink, symbuf, (long)dp->di_size); 2341558Srgrimes dp->di_blocks = 0; 2351558Srgrimes inodirty(); 2361558Srgrimes } 2371558Srgrimes /* 2381558Srgrimes * Fake ndb value so direct/indirect block checks below 2391558Srgrimes * will detect any garbage after symlink string. 2401558Srgrimes */ 24141474Sjulian if (dp->di_size < sblock.fs_maxsymlinklen) { 24223675Speter ndb = howmany(dp->di_size, sizeof(ufs_daddr_t)); 2431558Srgrimes if (ndb > NDADDR) { 2441558Srgrimes j = ndb - NDADDR; 2451558Srgrimes for (ndb = 1; j > 1; j--) 2461558Srgrimes ndb *= NINDIR(&sblock); 2471558Srgrimes ndb += NDADDR; 2481558Srgrimes } 2491558Srgrimes } 2501558Srgrimes } 2511558Srgrimes for (j = ndb; j < NDADDR; j++) 2521558Srgrimes if (dp->di_db[j] != 0) { 2531558Srgrimes if (debug) 25437236Sbde printf("bad direct addr: %ld\n", 25537236Sbde (long)dp->di_db[j]); 2561558Srgrimes goto unknown; 2571558Srgrimes } 2581558Srgrimes for (j = 0, ndb -= NDADDR; ndb > 0; j++) 2591558Srgrimes ndb /= NINDIR(&sblock); 2601558Srgrimes for (; j < NIADDR; j++) 2611558Srgrimes if (dp->di_ib[j] != 0) { 2621558Srgrimes if (debug) 2631558Srgrimes printf("bad indirect addr: %ld\n", 26437236Sbde (long)dp->di_ib[j]); 2651558Srgrimes goto unknown; 2661558Srgrimes } 2671558Srgrimes if (ftypeok(dp) == 0) 2681558Srgrimes goto unknown; 2691558Srgrimes n_files++; 27041474Sjulian inoinfo(inumber)->ino_linkcnt = dp->di_nlink; 2711558Srgrimes if (dp->di_nlink <= 0) { 2721558Srgrimes zlnp = (struct zlncnt *)malloc(sizeof *zlnp); 2731558Srgrimes if (zlnp == NULL) { 2741558Srgrimes pfatal("LINK COUNT TABLE OVERFLOW"); 27534266Sjulian if (reply("CONTINUE") == 0) { 27634266Sjulian ckfini(0); 27723675Speter exit(EEXIT); 27834266Sjulian } 2791558Srgrimes } else { 2801558Srgrimes zlnp->zlncnt = inumber; 2811558Srgrimes zlnp->next = zlnhead; 2821558Srgrimes zlnhead = zlnp; 2831558Srgrimes } 2841558Srgrimes } 2851558Srgrimes if (mode == IFDIR) { 2861558Srgrimes if (dp->di_size == 0) 28741474Sjulian inoinfo(inumber)->ino_state = DCLEAR; 2881558Srgrimes else 28941474Sjulian inoinfo(inumber)->ino_state = DSTATE; 2901558Srgrimes cacheino(dp, inumber); 29141474Sjulian countdirs++; 2921558Srgrimes } else 29341474Sjulian inoinfo(inumber)->ino_state = FSTATE; 29441474Sjulian inoinfo(inumber)->ino_type = IFTODT(mode); 2951558Srgrimes if (doinglevel2 && 2961558Srgrimes (dp->di_ouid != (u_short)-1 || dp->di_ogid != (u_short)-1)) { 2971558Srgrimes dp = ginode(inumber); 2981558Srgrimes dp->di_uid = dp->di_ouid; 2991558Srgrimes dp->di_ouid = -1; 3001558Srgrimes dp->di_gid = dp->di_ogid; 3011558Srgrimes dp->di_ogid = -1; 3021558Srgrimes inodirty(); 3031558Srgrimes } 3041558Srgrimes badblk = dupblk = 0; 3051558Srgrimes idesc->id_number = inumber; 3061558Srgrimes (void)ckinode(dp, idesc); 3071558Srgrimes idesc->id_entryno *= btodb(sblock.fs_fsize); 3081558Srgrimes if (dp->di_blocks != idesc->id_entryno) { 3091558Srgrimes pwarn("INCORRECT BLOCK COUNT I=%lu (%ld should be %ld)", 3101558Srgrimes inumber, dp->di_blocks, idesc->id_entryno); 3111558Srgrimes if (preen) 3121558Srgrimes printf(" (CORRECTED)\n"); 3131558Srgrimes else if (reply("CORRECT") == 0) 3141558Srgrimes return; 3151558Srgrimes dp = ginode(inumber); 3161558Srgrimes dp->di_blocks = idesc->id_entryno; 3171558Srgrimes inodirty(); 3181558Srgrimes } 3191558Srgrimes return; 3201558Srgrimesunknown: 3211558Srgrimes pfatal("UNKNOWN FILE TYPE I=%lu", inumber); 32241474Sjulian inoinfo(inumber)->ino_state = FCLEAR; 3231558Srgrimes if (reply("CLEAR") == 1) { 32441474Sjulian inoinfo(inumber)->ino_state = USTATE; 3251558Srgrimes dp = ginode(inumber); 3261558Srgrimes clearinode(dp); 3271558Srgrimes inodirty(); 3281558Srgrimes } 3291558Srgrimes} 3301558Srgrimes 3317585Sbdeint 3321558Srgrimespass1check(idesc) 3331558Srgrimes register struct inodesc *idesc; 3341558Srgrimes{ 3351558Srgrimes int res = KEEPON; 3361558Srgrimes int anyout, nfrags; 33723675Speter ufs_daddr_t blkno = idesc->id_blkno; 3381558Srgrimes register struct dups *dlp; 3391558Srgrimes struct dups *new; 3401558Srgrimes 3411558Srgrimes if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 3421558Srgrimes blkerror(idesc->id_number, "BAD", blkno); 3431558Srgrimes if (badblk++ >= MAXBAD) { 3441558Srgrimes pwarn("EXCESSIVE BAD BLKS I=%lu", 3451558Srgrimes idesc->id_number); 3461558Srgrimes if (preen) 3471558Srgrimes printf(" (SKIPPING)\n"); 34834266Sjulian else if (reply("CONTINUE") == 0) { 34934266Sjulian ckfini(0); 35023675Speter exit(EEXIT); 35134266Sjulian } 3521558Srgrimes return (STOP); 3531558Srgrimes } 3541558Srgrimes } 3551558Srgrimes for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { 3561558Srgrimes if (anyout && chkrange(blkno, 1)) { 3571558Srgrimes res = SKIP; 3581558Srgrimes } else if (!testbmap(blkno)) { 3591558Srgrimes n_blks++; 3601558Srgrimes setbmap(blkno); 3611558Srgrimes } else { 3621558Srgrimes blkerror(idesc->id_number, "DUP", blkno); 3631558Srgrimes if (dupblk++ >= MAXDUP) { 3641558Srgrimes pwarn("EXCESSIVE DUP BLKS I=%lu", 3651558Srgrimes idesc->id_number); 3661558Srgrimes if (preen) 3671558Srgrimes printf(" (SKIPPING)\n"); 36834266Sjulian else if (reply("CONTINUE") == 0) { 36934266Sjulian ckfini(0); 37023675Speter exit(EEXIT); 37134266Sjulian } 3721558Srgrimes return (STOP); 3731558Srgrimes } 3741558Srgrimes new = (struct dups *)malloc(sizeof(struct dups)); 3751558Srgrimes if (new == NULL) { 3761558Srgrimes pfatal("DUP TABLE OVERFLOW."); 37734266Sjulian if (reply("CONTINUE") == 0) { 37834266Sjulian ckfini(0); 37923675Speter exit(EEXIT); 38034266Sjulian } 3811558Srgrimes return (STOP); 3821558Srgrimes } 3831558Srgrimes new->dup = blkno; 3841558Srgrimes if (muldup == 0) { 3851558Srgrimes duplist = muldup = new; 3861558Srgrimes new->next = 0; 3871558Srgrimes } else { 3881558Srgrimes new->next = muldup->next; 3891558Srgrimes muldup->next = new; 3901558Srgrimes } 3911558Srgrimes for (dlp = duplist; dlp != muldup; dlp = dlp->next) 3921558Srgrimes if (dlp->dup == blkno) 3931558Srgrimes break; 3941558Srgrimes if (dlp == muldup && dlp->dup != blkno) 3951558Srgrimes muldup = new; 3961558Srgrimes } 3971558Srgrimes /* 3981558Srgrimes * count the number of blocks found in id_entryno 3991558Srgrimes */ 4001558Srgrimes idesc->id_entryno++; 4011558Srgrimes } 4021558Srgrimes return (res); 4031558Srgrimes} 404