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