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