1/*	$OpenBSD: pass1.c,v 1.49 2024/02/03 18:51:57 beck Exp $	*/
2/*	$NetBSD: pass1.c,v 1.16 1996/09/27 22:45:15 christos Exp $	*/
3
4/*
5 * Copyright (c) 1980, 1986, 1993
6 *	The Regents of the University of California.  All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 *    may be used to endorse or promote products derived from this software
18 *    without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33#include <sys/param.h>	/* MIN setbit btodb isset */
34#include <sys/time.h>
35#include <ufs/ufs/dinode.h>
36#include <ufs/ufs/dir.h>
37#include <ufs/ffs/fs.h>
38
39#include <stdio.h>
40#include <stdlib.h>
41#include <string.h>
42#include <unistd.h>
43#include <limits.h>
44
45#include "fsck.h"
46#include "extern.h"
47#include "fsutil.h"
48
49static daddr_t badblk;
50static daddr_t dupblk;
51static void checkinode(ino_t, struct inodesc *);
52
53static ino_t info_inumber;
54
55static int
56pass1_info(char *buf, size_t buflen)
57{
58	return (snprintf(buf, buflen, "phase 1, inode %llu/%llu",
59	    (unsigned long long)info_inumber,
60	    (unsigned long long)sblock.fs_ipg * sblock.fs_ncg) > 0);
61}
62
63void
64pass1(void)
65{
66	ino_t inumber, inosused, ninosused;
67	size_t inospace;
68	struct inostat *info;
69	struct bufarea *cgbp;
70	struct cg *cgp;
71	u_int c;
72	struct inodesc idesc;
73	daddr_t i, cgd;
74	u_int8_t *cp;
75
76	/*
77	 * Set file system reserved blocks in used block map.
78	 */
79	for (c = 0; c < sblock.fs_ncg; c++) {
80		cgd = cgdmin(&sblock, c);
81		if (c == 0)
82			i = cgbase(&sblock, c);
83		else
84			i = cgsblock(&sblock, c);
85		for (; i < cgd; i++)
86			setbmap(i);
87	}
88	i = sblock.fs_csaddr;
89	cgd = i + howmany(sblock.fs_cssize, sblock.fs_fsize);
90	for (; i < cgd; i++)
91		setbmap(i);
92	/*
93	 * Find all allocated blocks.
94	 */
95	memset(&idesc, 0, sizeof(struct inodesc));
96	idesc.id_type = ADDR;
97	idesc.id_func = pass1check;
98	n_files = n_blks = 0;
99	info_inumber = 0;
100	info_fn = pass1_info;
101	for (c = 0; c < sblock.fs_ncg; c++) {
102		inumber = c * sblock.fs_ipg;
103		setinodebuf(inumber);
104		cgbp = cglookup(c);
105		cgp = cgbp->b_un.b_cg;
106		if (sblock.fs_magic == FS_UFS2_MAGIC) {
107			inosused = cgp->cg_initediblk;
108			if (inosused > sblock.fs_ipg)
109				inosused = sblock.fs_ipg;
110		} else
111			inosused = sblock.fs_ipg;
112
113		/*
114		 * Allocate inoinfo structures for the allocated inodes.
115		 */
116		inostathead[c].il_numalloced = inosused;
117		if (inosused == 0) {
118			inostathead[c].il_stat = 0;
119			continue;
120		}
121		info = Calloc((unsigned)inosused, sizeof(struct inostat));
122		inospace = (unsigned)inosused * sizeof(struct inostat);
123		if (info == NULL)
124			errexit("cannot alloc %zu bytes for inoinfo\n", inospace);
125		inostathead[c].il_stat = info;
126		/*
127		 * Scan the allocated inodes.
128		 */
129		for (i = 0; i < inosused; i++, inumber++) {
130			info_inumber = inumber;
131			if (inumber < ROOTINO) {
132				(void)getnextinode(inumber);
133				continue;
134			}
135			checkinode(inumber, &idesc);
136		}
137		lastino += 1;
138		if (inosused < sblock.fs_ipg || inumber == lastino)
139			continue;
140		/*
141		 * If we were not able to determine in advance which inodes
142		 * were in use, then reduce the size of the inoinfo structure
143		 * to the size necessary to describe the inodes that we
144		 * really found.
145		 */
146		if (lastino < (c * sblock.fs_ipg))
147			ninosused = 0;
148		else
149			ninosused = lastino - (c * sblock.fs_ipg);
150		inostathead[c].il_numalloced = ninosused;
151		if (ninosused == 0) {
152			free(inostathead[c].il_stat);
153			inostathead[c].il_stat = 0;
154			continue;
155		}
156		if (ninosused != inosused) {
157			struct inostat *ninfo;
158			size_t ninospace;
159
160			ninfo = Reallocarray(info, ninosused, sizeof(*ninfo));
161			if (ninfo == NULL) {
162				pfatal("too many inodes %llu, or out of memory\n",
163				    (unsigned long long)ninosused);
164				exit(8);
165			}
166			ninospace = ninosused * sizeof(*ninfo);
167			if (ninosused > inosused)
168				memset(&ninfo[inosused], 0, ninospace - inospace);
169			inostathead[c].il_stat = ninfo;
170		}
171	}
172	info_fn = NULL;
173	freeinodebuf();
174}
175
176static void
177checkinode(ino_t inumber, struct inodesc *idesc)
178{
179	union dinode *dp;
180	off_t kernmaxfilesize;
181	struct zlncnt *zlnp;
182	int ndb, j;
183	mode_t mode;
184	u_int64_t lndb;
185
186	dp = getnextinode(inumber);
187	mode = DIP(dp, di_mode) & IFMT;
188	if (mode == 0) {
189		if ((sblock.fs_magic == FS_UFS1_MAGIC &&
190		     (memcmp(dp->dp1.di_db, ufs1_zino.di_db,
191			NDADDR * sizeof(int32_t)) ||
192		      memcmp(dp->dp1.di_ib, ufs1_zino.di_ib,
193			NIADDR * sizeof(int32_t)) ||
194		      dp->dp1.di_mode || dp->dp1.di_size)) ||
195		    (sblock.fs_magic == FS_UFS2_MAGIC &&
196		     (memcmp(dp->dp2.di_db, ufs2_zino.di_db,
197			NDADDR * sizeof(daddr_t)) ||
198		      memcmp(dp->dp2.di_ib, ufs2_zino.di_ib,
199			NIADDR * sizeof(daddr_t)) ||
200		      dp->dp2.di_mode || dp->dp2.di_size))) {
201			pfatal("PARTIALLY ALLOCATED INODE I=%llu",
202			    (unsigned long long)inumber);
203			if (reply("CLEAR") == 1) {
204				dp = ginode(inumber);
205				clearinode(dp);
206				inodirty();
207			}
208		}
209		SET_ISTATE(inumber, USTATE);
210		return;
211	}
212	lastino = inumber;
213	/* This should match the file size limit in ffs_mountfs(). */
214	kernmaxfilesize = FS_KERNMAXFILESIZE(getpagesize(), &sblock);
215	if (DIP(dp, di_size) > kernmaxfilesize ||
216	    DIP(dp, di_size) > sblock.fs_maxfilesize ||
217	    (mode == IFDIR && DIP(dp, di_size) > MAXDIRSIZE)) {
218		if (debug)
219			printf("bad size %llu:",
220			    (unsigned long long)DIP(dp, di_size));
221		goto unknown;
222	}
223	if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) {
224		dp = ginode(inumber);
225		DIP_SET(dp, di_size, sblock.fs_fsize);
226		DIP_SET(dp, di_mode, IFREG|0600);
227		inodirty();
228	}
229	lndb = howmany(DIP(dp, di_size), sblock.fs_bsize);
230	ndb = lndb > (u_int64_t)INT_MAX ? -1 : (int)lndb;
231	if (ndb < 0) {
232		if (debug)
233			printf("bad size %llu ndb %d:",
234			    (unsigned long long)DIP(dp, di_size), ndb);
235		goto unknown;
236	}
237	if (mode == IFBLK || mode == IFCHR)
238		ndb++;
239	if (mode == IFLNK) {
240		/*
241		 * Fake ndb value so direct/indirect block checks below
242		 * will detect any garbage after symlink string.
243		 */
244		if (DIP(dp, di_size) < sblock.fs_maxsymlinklen) {
245			if (sblock.fs_magic == FS_UFS1_MAGIC)
246				ndb = howmany(DIP(dp, di_size),
247				    sizeof(int32_t));
248			else
249				ndb = howmany(DIP(dp, di_size),
250				    sizeof(int64_t));
251			if (ndb > NDADDR) {
252				j = ndb - NDADDR;
253				for (ndb = 1; j > 1; j--)
254					ndb *= NINDIR(&sblock);
255				ndb += NDADDR;
256			}
257		}
258	}
259	for (j = ndb; j < NDADDR; j++)
260		if (DIP(dp, di_db[j]) != 0) {
261			if (debug)
262				printf("bad direct addr: %lld\n",
263				    (long long)DIP(dp, di_db[j]));
264			goto unknown;
265		}
266	for (j = 0, ndb -= NDADDR; ndb > 0; j++)
267		ndb /= NINDIR(&sblock);
268	for (; j < NIADDR; j++)
269		if (DIP(dp, di_ib[j]) != 0) {
270			if (debug)
271				printf("bad indirect addr: %lld\n",
272				    (long long)DIP(dp, di_ib[j]));
273			goto unknown;
274		}
275	if (ftypeok(dp) == 0)
276		goto unknown;
277	n_files++;
278	ILNCOUNT(inumber) = DIP(dp, di_nlink);
279	if (DIP(dp, di_nlink) <= 0) {
280		zlnp = Malloc(sizeof *zlnp);
281		if (zlnp == NULL) {
282			pfatal("LINK COUNT TABLE OVERFLOW");
283			if (reply("CONTINUE") == 0) {
284				ckfini(0);
285				errexit("%s", "");
286			}
287		} else {
288			zlnp->zlncnt = inumber;
289			zlnp->next = zlnhead;
290			zlnhead = zlnp;
291		}
292	}
293	if (mode == IFDIR) {
294		if (DIP(dp, di_size) == 0)
295			SET_ISTATE(inumber, DCLEAR);
296		else
297			SET_ISTATE(inumber, DSTATE);
298		cacheino(dp, inumber);
299	} else
300		SET_ISTATE(inumber, FSTATE);
301	SET_ITYPE(inumber, IFTODT(mode));
302	badblk = dupblk = 0;
303	idesc->id_number = inumber;
304	(void)ckinode(dp, idesc);
305	idesc->id_entryno *= btodb(sblock.fs_fsize);
306	if (DIP(dp, di_blocks) != idesc->id_entryno) {
307		pwarn("INCORRECT BLOCK COUNT I=%llu (%lld should be %lld)",
308		    (unsigned long long)inumber, (long long)DIP(dp, di_blocks),
309		    (long long)idesc->id_entryno);
310		if (preen)
311			printf(" (CORRECTED)\n");
312		else if (reply("CORRECT") == 0)
313			return;
314		dp = ginode(inumber);
315		DIP_SET(dp, di_blocks, idesc->id_entryno);
316		inodirty();
317	}
318	return;
319unknown:
320	pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber);
321	SET_ISTATE(inumber, FCLEAR);
322	if (reply("CLEAR") == 1) {
323		SET_ISTATE(inumber, USTATE);
324		dp = ginode(inumber);
325		clearinode(dp);
326		inodirty();
327	}
328}
329
330int
331pass1check(struct inodesc *idesc)
332{
333	int res = KEEPON;
334	int anyout, nfrags;
335	daddr_t blkno = idesc->id_blkno;
336	struct dups *dlp;
337	struct dups *new;
338
339	if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) {
340		blkerror(idesc->id_number, "BAD", blkno);
341		if (badblk++ >= MAXBAD) {
342			pwarn("EXCESSIVE BAD BLKS I=%llu",
343			    (unsigned long long)idesc->id_number);
344			if (preen)
345				printf(" (SKIPPING)\n");
346			else if (reply("CONTINUE") == 0) {
347				ckfini(0);
348				errexit("%s", "");
349			}
350			return (STOP);
351		}
352	}
353	for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) {
354		if (anyout && chkrange(blkno, 1)) {
355			res = SKIP;
356		} else if (!testbmap(blkno)) {
357			n_blks++;
358			setbmap(blkno);
359		} else {
360			blkerror(idesc->id_number, "DUP", blkno);
361			if (dupblk++ >= MAXDUP) {
362				pwarn("EXCESSIVE DUP BLKS I=%llu",
363				    (unsigned long long)idesc->id_number);
364				if (preen)
365					printf(" (SKIPPING)\n");
366				else if (reply("CONTINUE") == 0) {
367					ckfini(0);
368					errexit("%s", "");
369				}
370				return (STOP);
371			}
372			new = Malloc(sizeof(struct dups));
373			if (new == NULL) {
374				pfatal("DUP TABLE OVERFLOW.");
375				if (reply("CONTINUE") == 0) {
376					ckfini(0);
377					errexit("%s", "");
378				}
379				return (STOP);
380			}
381			new->dup = blkno;
382			if (muldup == 0) {
383				duplist = muldup = new;
384				new->next = 0;
385			} else {
386				new->next = muldup->next;
387				muldup->next = new;
388			}
389			for (dlp = duplist; dlp != muldup; dlp = dlp->next)
390				if (dlp->dup == blkno)
391					break;
392			if (dlp == muldup && dlp->dup != blkno)
393				muldup = new;
394		}
395		/*
396		 * count the number of blocks found in id_entryno
397		 */
398		idesc->id_entryno++;
399	}
400	return (res);
401}
402