Home | History | Annotate | Line # | Download | only in fsck_lfs
pass1.c revision 1.15 
      1 /* $NetBSD: pass1.c,v 1.15 2003/04/02 10:39:28 fvdl Exp $	 */
      2 
      3 /*
      4  * Copyright (c) 1980, 1986, 1993
      5  *	The Regents of the University of California.  All rights reserved.
      6  *
      7  * Redistribution and use in source and binary forms, with or without
      8  * modification, are permitted provided that the following conditions
      9  * are met:
     10  * 1. Redistributions of source code must retain the above copyright
     11  *    notice, this list of conditions and the following disclaimer.
     12  * 2. Redistributions in binary form must reproduce the above copyright
     13  *    notice, this list of conditions and the following disclaimer in the
     14  *    documentation and/or other materials provided with the distribution.
     15  * 3. All advertising materials mentioning features or use of this software
     16  *    must display the following acknowledgement:
     17  *	This product includes software developed by the University of
     18  *	California, Berkeley and its contributors.
     19  * 4. Neither the name of the University nor the names of its contributors
     20  *    may be used to endorse or promote products derived from this software
     21  *    without specific prior written permission.
     22  *
     23  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     24  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     25  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     26  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     27  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     28  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     29  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     30  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     32  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     33  * SUCH DAMAGE.
     34  */
     35 
     36 #include <sys/param.h>
     37 #include <sys/time.h>
     38 #include <sys/mount.h>
     39 #include <sys/buf.h>
     40 
     41 #include <ufs/ufs/inode.h>
     42 #include <ufs/ufs/dir.h>
     43 #define vnode uvnode
     44 #include <ufs/lfs/lfs.h>
     45 #undef vnode
     46 
     47 #include <err.h>
     48 #include <stdio.h>
     49 #include <stdlib.h>
     50 #include <string.h>
     51 
     52 #include <signal.h>
     53 
     54 #include "bufcache.h"
     55 #include "vnode.h"
     56 #include "lfs.h"
     57 
     58 #include "fsck.h"
     59 #include "extern.h"
     60 #include "fsutil.h"
     61 
     62 SEGUSE *seg_table;
     63 extern ufs_daddr_t *din_table;
     64 
     65 ufs_daddr_t badblk;
     66 static ufs_daddr_t dupblk;
     67 static int i_d_cmp(const void *, const void *);
     68 
     69 struct ino_daddr {
     70 	ino_t ino;
     71 	ufs_daddr_t daddr;
     72 };
     73 
     74 static int
     75 i_d_cmp(const void *va, const void *vb)
     76 {
     77 	struct ino_daddr *a, *b;
     78 
     79 	a = *((struct ino_daddr **) va);
     80 	b = *((struct ino_daddr **) vb);
     81 
     82 	if (a->daddr == b->daddr) {
     83 		return (a->ino - b->ino);
     84 	}
     85 	if (a->daddr > b->daddr) {
     86 		return 1;
     87 	}
     88 	return -1;
     89 }
     90 
     91 void
     92 pass1()
     93 {
     94 	ino_t inumber;
     95 	int i;
     96 	struct inodesc idesc;
     97 	struct ufs1_dinode *tinode;
     98 	struct ifile *ifp;
     99 	struct ubuf *bp;
    100 	struct ino_daddr **dins;
    101 
    102 	/*
    103 	 * Find all allocated blocks, initialize numdirs.
    104 	 */
    105 	memset(&idesc, 0, sizeof(struct inodesc));
    106 	idesc.id_type = ADDR;
    107 	idesc.id_func = pass1check;
    108 	idesc.id_lblkno = 0;
    109 	inumber = 0;
    110 	n_files = n_blks = 0;
    111 
    112 	if (debug)
    113 		printf("creating sorted inode address table...\n");
    114 	/* Sort by daddr */
    115 	dins = (struct ino_daddr **) malloc(maxino * sizeof(*dins));
    116 	for (i = 0; i < maxino; i++) {
    117 		dins[i] = malloc(sizeof(**dins));
    118 		dins[i]->ino = i;
    119 		if (i == fs->lfs_ifile)
    120 			dins[i]->daddr = fs->lfs_idaddr;
    121 		else {
    122 			LFS_IENTRY(ifp, fs, i, bp);
    123 			dins[i]->daddr = ifp->if_daddr;
    124 			brelse(bp);
    125 		}
    126 	}
    127 	qsort(dins, maxino, sizeof(*dins), i_d_cmp);
    128 
    129 	/* find a value for numdirs, fill in din_table */
    130 	if (debug)
    131 		printf("counting dirs...\n");
    132 	numdirs = 0;
    133 	for (i = 0; i < maxino; i++) {
    134 		inumber = dins[i]->ino;
    135 		if (inumber == 0 || dins[i]->daddr == 0)
    136 			continue;
    137 		tinode = ginode(inumber);
    138 		if (tinode && (tinode->di_mode & IFMT) == IFDIR)
    139 			numdirs++;
    140 	}
    141 
    142 	/* from setup.c */
    143 	inplast = 0;
    144 	listmax = numdirs + 10;
    145 	inpsort = (struct inoinfo **) calloc((unsigned) listmax,
    146 	    sizeof(struct inoinfo *));
    147 	inphead = (struct inoinfo **) calloc((unsigned) numdirs,
    148 	    sizeof(struct inoinfo *));
    149 	if (inpsort == NULL || inphead == NULL) {
    150 		printf("cannot alloc %lu bytes for inphead\n",
    151 		    (unsigned long) numdirs * sizeof(struct inoinfo *));
    152 		exit(1);
    153 	}
    154 	if (debug)
    155 		printf("counting blocks...\n");
    156 
    157 	for (i = 0; i < maxino; i++) {
    158 		inumber = dins[i]->ino;
    159 		if (inumber == 0 || dins[i]->daddr == 0) {
    160 			statemap[inumber] = USTATE;
    161 			continue;
    162 		}
    163 		if (dins[i]->daddr != LFS_UNUSED_DADDR) {
    164 			checkinode(inumber, &idesc);
    165 		} else {
    166 			statemap[inumber] = USTATE;
    167 		}
    168 		free(dins[i]);
    169 	}
    170 	free(dins);
    171 }
    172 
    173 void
    174 checkinode(ino_t inumber, struct inodesc * idesc)
    175 {
    176 	struct ufs1_dinode *dp;
    177 	struct uvnode  *vp;
    178 	struct zlncnt *zlnp;
    179 	int ndb, j;
    180 	mode_t mode;
    181 
    182 	vp = vget(fs, inumber);
    183 	dp = VTOD(vp);
    184 
    185 	if (dp == NULL) {
    186 		/* pwarn("Could not find inode %ld\n",(long)inumber); */
    187 		statemap[inumber] = USTATE;
    188 		return;
    189 	}
    190 	mode = dp->di_mode & IFMT;
    191 
    192 	/* XXX - LFS doesn't have this particular problem (?) */
    193 	if (mode == 0) {
    194 		if (memcmp(dp->di_db, zino.di_db, NDADDR * sizeof(ufs_daddr_t)) ||
    195 		    memcmp(dp->di_ib, zino.di_ib, NIADDR * sizeof(ufs_daddr_t)) ||
    196 		    dp->di_mode || dp->di_size) {
    197 			pwarn("mode=o%o, ifmt=o%o\n", dp->di_mode, mode);
    198 			pfatal("PARTIALLY ALLOCATED INODE I=%u", inumber);
    199 			if (reply("CLEAR") == 1) {
    200 				vp = vget(fs, inumber);
    201 				dp = VTOD(vp);
    202 				clearinode(dp);
    203 				inodirty(VTOI(vp));
    204 			}
    205 		}
    206 		statemap[inumber] = USTATE;
    207 		return;
    208 	}
    209 	lastino = inumber;
    210 	if (dp->di_size < 0 || dp->di_size + fs->lfs_bsize - 1 < dp->di_size) {
    211 		if (debug)
    212 			printf("bad size %llu:",
    213 			    (unsigned long long) dp->di_size);
    214 		goto unknown;
    215 	}
    216 	if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) {
    217 		vp = vget(fs, inumber);
    218 		dp = VTOD(vp);
    219 		dp->di_size = fs->lfs_fsize;
    220 		dp->di_mode = IFREG | 0600;
    221 		inodirty(VTOI(vp));
    222 	}
    223 	ndb = howmany(dp->di_size, fs->lfs_bsize);
    224 	if (ndb < 0) {
    225 		if (debug)
    226 			printf("bad size %llu ndb %d:",
    227 			    (unsigned long long) dp->di_size, ndb);
    228 		goto unknown;
    229 	}
    230 	if (mode == IFBLK || mode == IFCHR)
    231 		ndb++;
    232 	if (mode == IFLNK) {
    233 		/*
    234 		 * Fake ndb value so direct/indirect block checks below
    235 		 * will detect any garbage after symlink string.
    236 		 */
    237 		if (dp->di_size < fs->lfs_maxsymlinklen ||
    238 		    (fs->lfs_maxsymlinklen == 0 && dp->di_blocks == 0)) {
    239 			ndb = howmany(dp->di_size, sizeof(ufs_daddr_t));
    240 			if (ndb > NDADDR) {
    241 				j = ndb - NDADDR;
    242 				for (ndb = 1; j > 1; j--)
    243 					ndb *= NINDIR(fs);
    244 				ndb += NDADDR;
    245 			}
    246 		}
    247 	}
    248 	for (j = ndb; j < NDADDR; j++)
    249 		if (dp->di_db[j] != 0) {
    250 			if (debug)
    251 				printf("bad direct addr: %d\n", dp->di_db[j]);
    252 			goto unknown;
    253 		}
    254 	for (j = 0, ndb -= NDADDR; ndb > 0; j++)
    255 		ndb /= NINDIR(fs);
    256 	for (; j < NIADDR; j++)
    257 		if (dp->di_ib[j] != 0) {
    258 			if (debug)
    259 				printf("bad indirect addr: %d\n",
    260 				    dp->di_ib[j]);
    261 			/* goto unknown; */
    262 		}
    263 	if (ftypeok(dp) == 0)
    264 		goto unknown;
    265 	n_files++;
    266 	lncntp[inumber] = dp->di_nlink;
    267 	if (dp->di_nlink <= 0) {
    268 		zlnp = (struct zlncnt *) malloc(sizeof *zlnp);
    269 		if (zlnp == NULL) {
    270 			pfatal("LINK COUNT TABLE OVERFLOW");
    271 			if (reply("CONTINUE") == 0)
    272 				err(8, "%s", "");
    273 		} else {
    274 			zlnp->zlncnt = inumber;
    275 			zlnp->next = zlnhead;
    276 			zlnhead = zlnp;
    277 		}
    278 	}
    279 	if (mode == IFDIR) {
    280 		if (dp->di_size == 0)
    281 			statemap[inumber] = DCLEAR;
    282 		else
    283 			statemap[inumber] = DSTATE;
    284 		cacheino(dp, inumber);
    285 	} else
    286 		statemap[inumber] = FSTATE;
    287 	typemap[inumber] = IFTODT(mode);
    288 	badblk = dupblk = 0;
    289 	idesc->id_number = inumber;
    290 	(void) ckinode(VTOD(vp), idesc);
    291 	if (dp->di_blocks != idesc->id_entryno) {
    292 		pwarn("INCORRECT BLOCK COUNT I=%u (%d should be %d)",
    293 		    inumber, dp->di_blocks, idesc->id_entryno);
    294 		if (preen)
    295 			printf(" (CORRECTED)\n");
    296 		else if (reply("CORRECT") == 0)
    297 			return;
    298 		VTOI(vp)->i_ffs1_blocks = idesc->id_entryno;
    299 		inodirty(VTOI(vp));
    300 	}
    301 	return;
    302 unknown:
    303 	pfatal("UNKNOWN FILE TYPE I=%u", inumber);
    304 	statemap[inumber] = FCLEAR;
    305 	if (reply("CLEAR") == 1) {
    306 		statemap[inumber] = USTATE;
    307 		vp = vget(fs, inumber);
    308 		dp = VTOD(vp);
    309 		clearinode(dp);
    310 		inodirty(VTOI(vp));
    311 	}
    312 }
    313 
    314 int
    315 pass1check(struct inodesc *idesc)
    316 {
    317 	int res = KEEPON;
    318 	int anyout, ndblks;
    319 	daddr_t blkno = idesc->id_blkno;
    320 	register struct dups *dlp;
    321 	struct dups *new;
    322 
    323 	if ((anyout = chkrange(blkno, fragstofsb(fs, idesc->id_numfrags))) != 0) {
    324 		blkerror(idesc->id_number, "BAD", blkno);
    325 		if (badblk++ >= MAXBAD) {
    326 			pwarn("EXCESSIVE BAD BLKS I=%u",
    327 			    idesc->id_number);
    328 			if (preen)
    329 				printf(" (SKIPPING)\n");
    330 			else if (reply("CONTINUE") == 0)
    331 				err(8, "%s", "");
    332 			return (STOP);
    333 		}
    334 	} else if (!testbmap(blkno)) {
    335 		seg_table[dtosn(fs, blkno)].su_nbytes += idesc->id_numfrags * fs->lfs_fsize;
    336 	}
    337 	for (ndblks = fragstofsb(fs, idesc->id_numfrags); ndblks > 0; blkno++, ndblks--) {
    338 		if (anyout && chkrange(blkno, 1)) {
    339 			res = SKIP;
    340 		} else if (!testbmap(blkno)) {
    341 			n_blks++;
    342 #ifndef VERBOSE_BLOCKMAP
    343 			setbmap(blkno);
    344 #else
    345 			setbmap(blkno, idesc->id_number);
    346 #endif
    347 		} else {
    348 			blkerror(idesc->id_number, "DUP", blkno);
    349 #ifdef VERBOSE_BLOCKMAP
    350 			pwarn("(lbn %d: Holder is %d)\n", idesc->id_lblkno,
    351 			    testbmap(blkno));
    352 #endif
    353 			if (dupblk++ >= MAXDUP) {
    354 				pwarn("EXCESSIVE DUP BLKS I=%u",
    355 				    idesc->id_number);
    356 				if (preen)
    357 					printf(" (SKIPPING)\n");
    358 				else if (reply("CONTINUE") == 0)
    359 					err(8, "%s", "");
    360 				return (STOP);
    361 			}
    362 			new = (struct dups *) malloc(sizeof(struct dups));
    363 			if (new == NULL) {
    364 				pfatal("DUP TABLE OVERFLOW.");
    365 				if (reply("CONTINUE") == 0)
    366 					err(8, "%s", "");
    367 				return (STOP);
    368 			}
    369 			new->dup = blkno;
    370 			if (muldup == 0) {
    371 				duplist = muldup = new;
    372 				new->next = 0;
    373 			} else {
    374 				new->next = muldup->next;
    375 				muldup->next = new;
    376 			}
    377 			for (dlp = duplist; dlp != muldup; dlp = dlp->next)
    378 				if (dlp->dup == blkno)
    379 					break;
    380 			if (dlp == muldup && dlp->dup != blkno)
    381 				muldup = new;
    382 		}
    383 		/*
    384 		 * count the number of blocks found in id_entryno
    385 		 */
    386 		idesc->id_entryno++;
    387 	}
    388 	return (res);
    389 }
    390