Home | History | Annotate | Line # | Download | only in fsck_lfs
pass1.c revision 1.30.6.2
      1  1.30.6.2      yamt /* $NetBSD: pass1.c,v 1.30.6.2 2014/05/22 11:37:28 yamt 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 #define vnode uvnode
     38       1.1  perseant #include <ufs/lfs/lfs.h>
     39  1.30.6.2      yamt #include <ufs/lfs/lfs_inode.h>
     40      1.14  perseant #undef vnode
     41       1.1  perseant 
     42      1.14  perseant #include <err.h>
     43       1.1  perseant #include <stdio.h>
     44       1.1  perseant #include <stdlib.h>
     45       1.1  perseant #include <string.h>
     46       1.1  perseant #include <signal.h>
     47      1.28  christos #include <util.h>
     48       1.1  perseant 
     49      1.14  perseant #include "bufcache.h"
     50      1.14  perseant #include "vnode.h"
     51      1.23  christos #include "lfs_user.h"
     52      1.14  perseant 
     53       1.1  perseant #include "fsck.h"
     54       1.1  perseant #include "extern.h"
     55       1.1  perseant #include "fsutil.h"
     56       1.1  perseant 
     57      1.14  perseant SEGUSE *seg_table;
     58  1.30.6.2      yamt extern ulfs_daddr_t *din_table;
     59       1.1  perseant 
     60  1.30.6.2      yamt ulfs_daddr_t badblk;
     61  1.30.6.2      yamt static ulfs_daddr_t dupblk;
     62      1.14  perseant static int i_d_cmp(const void *, const void *);
     63       1.1  perseant 
     64       1.5  perseant struct ino_daddr {
     65      1.14  perseant 	ino_t ino;
     66  1.30.6.2      yamt 	ulfs_daddr_t daddr;
     67       1.5  perseant };
     68       1.5  perseant 
     69       1.5  perseant static int
     70       1.5  perseant i_d_cmp(const void *va, const void *vb)
     71       1.5  perseant {
     72      1.21  christos 	const struct ino_daddr *a, *b;
     73       1.5  perseant 
     74      1.21  christos 	a = *((const struct ino_daddr *const *) va);
     75      1.21  christos 	b = *((const struct ino_daddr *const *) vb);
     76       1.5  perseant 
     77       1.5  perseant 	if (a->daddr == b->daddr) {
     78       1.5  perseant 		return (a->ino - b->ino);
     79       1.5  perseant 	}
     80       1.5  perseant 	if (a->daddr > b->daddr) {
     81       1.5  perseant 		return 1;
     82       1.5  perseant 	}
     83       1.5  perseant 	return -1;
     84       1.5  perseant }
     85       1.5  perseant 
     86       1.1  perseant void
     87      1.19   xtraeme pass1(void)
     88       1.1  perseant {
     89      1.14  perseant 	ino_t inumber;
     90      1.14  perseant 	int i;
     91      1.14  perseant 	struct inodesc idesc;
     92  1.30.6.2      yamt 	struct ulfs1_dinode *tinode;
     93      1.14  perseant 	struct ifile *ifp;
     94      1.14  perseant 	struct ubuf *bp;
     95       1.5  perseant 	struct ino_daddr **dins;
     96       1.1  perseant 
     97       1.1  perseant 	/*
     98       1.1  perseant 	 * Find all allocated blocks, initialize numdirs.
     99       1.1  perseant 	 */
    100       1.1  perseant 	memset(&idesc, 0, sizeof(struct inodesc));
    101       1.1  perseant 	idesc.id_type = ADDR;
    102       1.1  perseant 	idesc.id_func = pass1check;
    103       1.1  perseant 	idesc.id_lblkno = 0;
    104       1.1  perseant 	inumber = 0;
    105       1.1  perseant 	n_files = n_blks = 0;
    106       1.1  perseant 
    107       1.5  perseant 	if (debug)
    108      1.14  perseant 		printf("creating sorted inode address table...\n");
    109       1.5  perseant 	/* Sort by daddr */
    110      1.28  christos 	dins = ecalloc(maxino, sizeof(*dins));
    111       1.8  perseant 	for (i = 0; i < maxino; i++) {
    112      1.28  christos 		dins[i] = emalloc(sizeof(**dins));
    113       1.5  perseant 		dins[i]->ino = i;
    114      1.14  perseant 		if (i == fs->lfs_ifile)
    115      1.14  perseant 			dins[i]->daddr = fs->lfs_idaddr;
    116      1.14  perseant 		else {
    117      1.14  perseant 			LFS_IENTRY(ifp, fs, i, bp);
    118      1.14  perseant 			dins[i]->daddr = ifp->if_daddr;
    119      1.29        ad 			brelse(bp, 0);
    120      1.14  perseant 		}
    121       1.5  perseant 	}
    122       1.8  perseant 	qsort(dins, maxino, sizeof(*dins), i_d_cmp);
    123       1.5  perseant 
    124       1.5  perseant 	/* find a value for numdirs, fill in din_table */
    125       1.5  perseant 	if (debug)
    126       1.5  perseant 		printf("counting dirs...\n");
    127       1.6  perseant 	numdirs = 0;
    128       1.8  perseant 	for (i = 0; i < maxino; i++) {
    129       1.5  perseant 		inumber = dins[i]->ino;
    130       1.6  perseant 		if (inumber == 0 || dins[i]->daddr == 0)
    131       1.5  perseant 			continue;
    132      1.14  perseant 		tinode = ginode(inumber);
    133  1.30.6.2      yamt 		if (tinode && (tinode->di_mode & LFS_IFMT) == LFS_IFDIR)
    134       1.5  perseant 			numdirs++;
    135       1.1  perseant 	}
    136       1.1  perseant 
    137       1.1  perseant 	/* from setup.c */
    138       1.6  perseant 	inplast = 0;
    139       1.6  perseant 	listmax = numdirs + 10;
    140      1.28  christos 	inpsort = ecalloc(listmax, sizeof(struct inoinfo *));
    141      1.28  christos 	inphead = ecalloc(numdirs, sizeof(struct inoinfo *));
    142       1.5  perseant 	if (debug)
    143       1.5  perseant 		printf("counting blocks...\n");
    144      1.14  perseant 
    145       1.8  perseant 	for (i = 0; i < maxino; i++) {
    146       1.5  perseant 		inumber = dins[i]->ino;
    147       1.7  perseant 		if (inumber == 0 || dins[i]->daddr == 0) {
    148       1.7  perseant 			statemap[inumber] = USTATE;
    149       1.5  perseant 			continue;
    150       1.7  perseant 		}
    151      1.14  perseant 		if (dins[i]->daddr != LFS_UNUSED_DADDR) {
    152       1.5  perseant 			checkinode(inumber, &idesc);
    153       1.5  perseant 		} else {
    154       1.5  perseant 			statemap[inumber] = USTATE;
    155       1.5  perseant 		}
    156       1.5  perseant 		free(dins[i]);
    157       1.6  perseant 	}
    158       1.5  perseant 	free(dins);
    159       1.1  perseant }
    160       1.1  perseant 
    161      1.14  perseant void
    162       1.6  perseant checkinode(ino_t inumber, struct inodesc * idesc)
    163       1.1  perseant {
    164  1.30.6.2      yamt 	struct ulfs1_dinode *dp;
    165      1.14  perseant 	struct uvnode  *vp;
    166      1.14  perseant 	struct zlncnt *zlnp;
    167      1.26  perseant 	struct ubuf *bp;
    168      1.26  perseant 	IFILE *ifp;
    169      1.14  perseant 	int ndb, j;
    170      1.14  perseant 	mode_t mode;
    171       1.1  perseant 
    172      1.14  perseant 	vp = vget(fs, inumber);
    173      1.16      yamt 	if (vp)
    174      1.16      yamt 		dp = VTOD(vp);
    175      1.16      yamt 	else
    176      1.16      yamt 		dp = NULL;
    177       1.1  perseant 
    178       1.6  perseant 	if (dp == NULL) {
    179       1.6  perseant 		statemap[inumber] = USTATE;
    180       1.6  perseant 		return;
    181       1.6  perseant 	}
    182  1.30.6.2      yamt 	mode = dp->di_mode & LFS_IFMT;
    183       1.1  perseant 
    184       1.6  perseant 	/* XXX - LFS doesn't have this particular problem (?) */
    185       1.1  perseant 	if (mode == 0) {
    186  1.30.6.2      yamt 		if (memcmp(dp->di_db, zino.di_db, ULFS_NDADDR * sizeof(ulfs_daddr_t)) ||
    187  1.30.6.2      yamt 		    memcmp(dp->di_ib, zino.di_ib, ULFS_NIADDR * sizeof(ulfs_daddr_t)) ||
    188       1.1  perseant 		    dp->di_mode || dp->di_size) {
    189       1.1  perseant 			pwarn("mode=o%o, ifmt=o%o\n", dp->di_mode, mode);
    190      1.22  christos 			pfatal("PARTIALLY ALLOCATED INODE I=%llu",
    191      1.22  christos 			    (unsigned long long)inumber);
    192       1.1  perseant 			if (reply("CLEAR") == 1) {
    193      1.14  perseant 				vp = vget(fs, inumber);
    194      1.18      yamt 				clearinode(inumber);
    195      1.18      yamt 				vnode_destroy(vp);
    196       1.1  perseant 			}
    197       1.1  perseant 		}
    198       1.1  perseant 		statemap[inumber] = USTATE;
    199       1.1  perseant 		return;
    200       1.1  perseant 	}
    201       1.1  perseant 	lastino = inumber;
    202      1.27  christos 	if (/* dp->di_size < 0 || */
    203      1.27  christos 	    dp->di_size + fs->lfs_bsize - 1 < dp->di_size) {
    204       1.1  perseant 		if (debug)
    205       1.9     lukem 			printf("bad size %llu:",
    206      1.14  perseant 			    (unsigned long long) dp->di_size);
    207       1.1  perseant 		goto unknown;
    208       1.1  perseant 	}
    209  1.30.6.2      yamt 	if (!preen && mode == LFS_IFMT && reply("HOLD BAD BLOCK") == 1) {
    210      1.14  perseant 		vp = vget(fs, inumber);
    211      1.14  perseant 		dp = VTOD(vp);
    212      1.14  perseant 		dp->di_size = fs->lfs_fsize;
    213  1.30.6.2      yamt 		dp->di_mode = LFS_IFREG | 0600;
    214      1.14  perseant 		inodirty(VTOI(vp));
    215       1.1  perseant 	}
    216      1.14  perseant 	ndb = howmany(dp->di_size, fs->lfs_bsize);
    217       1.1  perseant 	if (ndb < 0) {
    218       1.1  perseant 		if (debug)
    219       1.9     lukem 			printf("bad size %llu ndb %d:",
    220      1.14  perseant 			    (unsigned long long) dp->di_size, ndb);
    221       1.1  perseant 		goto unknown;
    222       1.1  perseant 	}
    223  1.30.6.2      yamt 	if (mode == LFS_IFBLK || mode == LFS_IFCHR)
    224       1.1  perseant 		ndb++;
    225  1.30.6.2      yamt 	if (mode == LFS_IFLNK) {
    226       1.1  perseant 		/*
    227       1.1  perseant 		 * Fake ndb value so direct/indirect block checks below
    228       1.1  perseant 		 * will detect any garbage after symlink string.
    229       1.1  perseant 		 */
    230      1.14  perseant 		if (dp->di_size < fs->lfs_maxsymlinklen ||
    231      1.14  perseant 		    (fs->lfs_maxsymlinklen == 0 && dp->di_blocks == 0)) {
    232  1.30.6.2      yamt 			ndb = howmany(dp->di_size, sizeof(ulfs_daddr_t));
    233  1.30.6.2      yamt 			if (ndb > ULFS_NDADDR) {
    234  1.30.6.2      yamt 				j = ndb - ULFS_NDADDR;
    235       1.1  perseant 				for (ndb = 1; j > 1; j--)
    236  1.30.6.2      yamt 					ndb *= LFS_NINDIR(fs);
    237  1.30.6.2      yamt 				ndb += ULFS_NDADDR;
    238       1.1  perseant 			}
    239       1.1  perseant 		}
    240       1.1  perseant 	}
    241  1.30.6.2      yamt 	for (j = ndb; j < ULFS_NDADDR; j++)
    242       1.1  perseant 		if (dp->di_db[j] != 0) {
    243       1.1  perseant 			if (debug)
    244      1.25  perseant 				printf("bad direct addr for size %lld lbn %d: 0x%x\n",
    245      1.25  perseant 					(long long)dp->di_size, j, (unsigned)dp->di_db[j]);
    246       1.1  perseant 			goto unknown;
    247       1.1  perseant 		}
    248  1.30.6.2      yamt 	for (j = 0, ndb -= ULFS_NDADDR; ndb > 0; j++)
    249  1.30.6.2      yamt 		ndb /= LFS_NINDIR(fs);
    250  1.30.6.2      yamt 	for (; j < ULFS_NIADDR; j++)
    251       1.1  perseant 		if (dp->di_ib[j] != 0) {
    252       1.1  perseant 			if (debug)
    253      1.25  perseant 				printf("bad indirect addr for size %lld # %d: 0x%x\n",
    254      1.25  perseant 					(long long)dp->di_size, j, (unsigned)dp->di_ib[j]);
    255      1.25  perseant 			goto unknown;
    256       1.1  perseant 		}
    257       1.1  perseant 	if (ftypeok(dp) == 0)
    258       1.1  perseant 		goto unknown;
    259       1.1  perseant 	n_files++;
    260       1.1  perseant 	lncntp[inumber] = dp->di_nlink;
    261       1.1  perseant 	if (dp->di_nlink <= 0) {
    262      1.28  christos 		zlnp = emalloc(sizeof *zlnp);
    263      1.28  christos 		zlnp->zlncnt = inumber;
    264      1.28  christos 		zlnp->next = zlnhead;
    265      1.28  christos 		zlnhead = zlnp;
    266       1.1  perseant 	}
    267  1.30.6.2      yamt 	if (mode == LFS_IFDIR) {
    268       1.1  perseant 		if (dp->di_size == 0)
    269       1.1  perseant 			statemap[inumber] = DCLEAR;
    270       1.1  perseant 		else
    271       1.1  perseant 			statemap[inumber] = DSTATE;
    272       1.1  perseant 		cacheino(dp, inumber);
    273       1.1  perseant 	} else
    274       1.1  perseant 		statemap[inumber] = FSTATE;
    275      1.26  perseant 
    276      1.26  perseant 	/*
    277      1.26  perseant 	 * Check for an orphaned file.  These happen when the cleaner has
    278      1.26  perseant 	 * to rewrite blocks from a file whose directory operation (removal)
    279      1.26  perseant 	 * is in progress.
    280      1.26  perseant 	 */
    281      1.26  perseant 	if (dp->di_nlink <= 0) {
    282      1.26  perseant 		LFS_IENTRY(ifp, fs, inumber, bp);
    283      1.26  perseant 		if (ifp->if_nextfree == LFS_ORPHAN_NEXTFREE) {
    284  1.30.6.2      yamt 			statemap[inumber] = (mode == LFS_IFDIR ? DCLEAR : FCLEAR);
    285      1.26  perseant 			/* Add this to our list of orphans */
    286      1.28  christos 			zlnp = emalloc(sizeof *zlnp);
    287      1.28  christos 			zlnp->zlncnt = inumber;
    288      1.28  christos 			zlnp->next = orphead;
    289      1.28  christos 			orphead = zlnp;
    290      1.26  perseant 		}
    291      1.29        ad 		brelse(bp, 0);
    292      1.26  perseant 	}
    293      1.26  perseant 
    294  1.30.6.2      yamt 	typemap[inumber] = LFS_IFTODT(mode);
    295       1.1  perseant 	badblk = dupblk = 0;
    296       1.1  perseant 	idesc->id_number = inumber;
    297      1.14  perseant 	(void) ckinode(VTOD(vp), idesc);
    298       1.1  perseant 	if (dp->di_blocks != idesc->id_entryno) {
    299      1.25  perseant 		pwarn("INCORRECT BLOCK COUNT I=%llu (%d SHOULD BE %d)",
    300      1.22  christos 		    (unsigned long long)inumber, dp->di_blocks,
    301      1.22  christos 		    idesc->id_entryno);
    302       1.1  perseant 		if (preen)
    303       1.1  perseant 			printf(" (CORRECTED)\n");
    304       1.1  perseant 		else if (reply("CORRECT") == 0)
    305       1.1  perseant 			return;
    306      1.15      fvdl 		VTOI(vp)->i_ffs1_blocks = idesc->id_entryno;
    307      1.14  perseant 		inodirty(VTOI(vp));
    308       1.1  perseant 	}
    309       1.1  perseant 	return;
    310       1.1  perseant unknown:
    311      1.22  christos 	pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber);
    312       1.1  perseant 	statemap[inumber] = FCLEAR;
    313       1.1  perseant 	if (reply("CLEAR") == 1) {
    314       1.1  perseant 		statemap[inumber] = USTATE;
    315      1.14  perseant 		vp = vget(fs, inumber);
    316      1.18      yamt 		clearinode(inumber);
    317      1.18      yamt 		vnode_destroy(vp);
    318       1.1  perseant 	}
    319       1.1  perseant }
    320       1.1  perseant 
    321       1.1  perseant int
    322      1.14  perseant pass1check(struct inodesc *idesc)
    323       1.1  perseant {
    324      1.14  perseant 	int res = KEEPON;
    325      1.14  perseant 	int anyout, ndblks;
    326      1.14  perseant 	daddr_t blkno = idesc->id_blkno;
    327      1.20     perry 	struct dups *dlp;
    328      1.14  perseant 	struct dups *new;
    329       1.1  perseant 
    330      1.30   mlelstv 	if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) {
    331       1.1  perseant 		blkerror(idesc->id_number, "BAD", blkno);
    332       1.1  perseant 		if (badblk++ >= MAXBAD) {
    333      1.22  christos 			pwarn("EXCESSIVE BAD BLKS I=%llu",
    334      1.22  christos 			    (unsigned long long)idesc->id_number);
    335       1.1  perseant 			if (preen)
    336       1.1  perseant 				printf(" (SKIPPING)\n");
    337       1.1  perseant 			else if (reply("CONTINUE") == 0)
    338      1.28  christos 				err(EEXIT, "%s", "");
    339       1.1  perseant 			return (STOP);
    340       1.1  perseant 		}
    341       1.8  perseant 	} else if (!testbmap(blkno)) {
    342  1.30.6.2      yamt 		seg_table[lfs_dtosn(fs, blkno)].su_nbytes += idesc->id_numfrags * fs->lfs_fsize;
    343       1.1  perseant 	}
    344      1.30   mlelstv 	for (ndblks = idesc->id_numfrags; ndblks > 0; blkno++, ndblks--) {
    345       1.1  perseant 		if (anyout && chkrange(blkno, 1)) {
    346       1.1  perseant 			res = SKIP;
    347       1.1  perseant 		} else if (!testbmap(blkno)) {
    348       1.1  perseant 			n_blks++;
    349       1.1  perseant #ifndef VERBOSE_BLOCKMAP
    350       1.1  perseant 			setbmap(blkno);
    351       1.1  perseant #else
    352       1.6  perseant 			setbmap(blkno, idesc->id_number);
    353       1.1  perseant #endif
    354       1.1  perseant 		} else {
    355       1.1  perseant 			blkerror(idesc->id_number, "DUP", blkno);
    356       1.1  perseant #ifdef VERBOSE_BLOCKMAP
    357      1.26  perseant 			pwarn("(lbn %lld: Holder is %lld)\n",
    358      1.26  perseant 				(long long)idesc->id_lblkno,
    359      1.26  perseant 				(long long)testbmap(blkno));
    360       1.1  perseant #endif
    361       1.1  perseant 			if (dupblk++ >= MAXDUP) {
    362      1.22  christos 				pwarn("EXCESSIVE DUP BLKS I=%llu",
    363      1.22  christos 				    (unsigned long long)idesc->id_number);
    364       1.1  perseant 				if (preen)
    365       1.1  perseant 					printf(" (SKIPPING)\n");
    366       1.1  perseant 				else if (reply("CONTINUE") == 0)
    367      1.28  christos 					err(EEXIT, "%s", "");
    368       1.1  perseant 				return (STOP);
    369       1.1  perseant 			}
    370      1.28  christos 			new = emalloc(sizeof(struct dups));
    371       1.1  perseant 			new->dup = blkno;
    372       1.1  perseant 			if (muldup == 0) {
    373       1.1  perseant 				duplist = muldup = new;
    374       1.1  perseant 				new->next = 0;
    375       1.1  perseant 			} else {
    376       1.1  perseant 				new->next = muldup->next;
    377       1.1  perseant 				muldup->next = new;
    378       1.1  perseant 			}
    379       1.1  perseant 			for (dlp = duplist; dlp != muldup; dlp = dlp->next)
    380       1.1  perseant 				if (dlp->dup == blkno)
    381       1.1  perseant 					break;
    382       1.1  perseant 			if (dlp == muldup && dlp->dup != blkno)
    383       1.1  perseant 				muldup = new;
    384       1.1  perseant 		}
    385       1.1  perseant 		/*
    386       1.1  perseant 		 * count the number of blocks found in id_entryno
    387       1.1  perseant 		 */
    388       1.6  perseant 		idesc->id_entryno++;
    389       1.1  perseant 	}
    390       1.1  perseant 	return (res);
    391       1.1  perseant }
    392