2 * SPDX-License-Identifier: BSD-3-Clause
4 * Copyright (c) 1980, 1986, 1993
5 * The Regents of the University of California. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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.
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
34 static const char sccsid[] = "@(#)pass1.c 8.6 (Berkeley) 4/28/95";
37 #include <sys/cdefs.h>
38 __FBSDID("$FreeBSD$");
40 #include <sys/param.h>
42 #include <sys/sysctl.h>
44 #include <ufs/ufs/dinode.h>
45 #include <ufs/ufs/dir.h>
46 #include <ufs/ffs/fs.h>
55 static ufs2_daddr_t badblk;
56 static ufs2_daddr_t dupblk;
57 static ino_t lastino; /* last inode in use */
59 static int checkinode(ino_t inumber, struct inodesc *, int rebuildcg);
68 ino_t inumber, inosused, mininos;
73 badblk = dupblk = lastino = 0;
76 * Set file system reserved blocks in used block map.
78 for (c = 0; c < sblock.fs_ncg; c++) {
79 cgd = cgdmin(&sblock, c);
81 i = cgbase(&sblock, c);
83 i = cgsblock(&sblock, c);
88 cgd = i + howmany(sblock.fs_cssize, sblock.fs_fsize);
93 * Find all allocated blocks.
95 memset(&idesc, 0, sizeof(struct inodesc));
96 idesc.id_func = pass1check;
98 for (c = 0; c < sblock.fs_ncg; c++) {
99 inumber = c * sblock.fs_ipg;
100 setinodebuf(inumber);
102 cgp = cgbp->b_un.b_cg;
104 if (!check_cgmagic(c, cgbp))
106 if (!rebuildcg && sblock.fs_magic == FS_UFS2_MAGIC) {
107 inosused = cgp->cg_initediblk;
108 if (inosused > sblock.fs_ipg) {
110 "Too many initialized inodes (%ju > %d) in cylinder group %d\nReset to %d\n",
112 sblock.fs_ipg, c, sblock.fs_ipg);
113 inosused = sblock.fs_ipg;
116 inosused = sblock.fs_ipg;
119 printf("%s: phase 1: cyl group %d of %d (%d%%)\n",
120 cdevname, c, sblock.fs_ncg,
121 c * 100 / sblock.fs_ncg);
125 setproctitle("%s p1 %d%%", cdevname,
126 c * 100 / sblock.fs_ncg);
130 * If we are using soft updates, then we can trust the
131 * cylinder group inode allocation maps to tell us which
132 * inodes are allocated. We will scan the used inode map
133 * to find the inodes that are really in use, and then
134 * read only those inodes in from disk.
136 if ((preen || inoopt) && usedsoftdep && !rebuildcg) {
137 cp = &cg_inosused(cgp)[(inosused - 1) / CHAR_BIT];
138 for ( ; inosused != 0; cp--) {
140 if (inosused > CHAR_BIT)
141 inosused -= CHAR_BIT;
146 for (i = 1 << (CHAR_BIT - 1); i > 0; i >>= 1) {
155 * Allocate inoinfo structures for the allocated inodes.
157 inostathead[c].il_numalloced = inosused;
159 inostathead[c].il_stat = NULL;
162 info = Calloc((unsigned)inosused, sizeof(struct inostat));
164 errx(EEXIT, "cannot alloc %u bytes for inoinfo",
165 (unsigned)(sizeof(struct inostat) * inosused));
166 inostathead[c].il_stat = info;
168 * Scan the allocated inodes.
170 for (i = 0; i < inosused; i++, inumber++) {
171 if (inumber < UFS_ROOTINO) {
172 (void)getnextinode(inumber, rebuildcg);
176 * NULL return indicates probable end of allocated
177 * inodes during cylinder group rebuild attempt.
178 * We always keep trying until we get to the minimum
179 * valid number for this cylinder group.
181 if (checkinode(inumber, &idesc, rebuildcg) == 0 &&
182 i > cgp->cg_initediblk)
186 * This optimization speeds up future runs of fsck
187 * by trimming down the number of inodes in cylinder
188 * groups that formerly had many inodes but now have
191 mininos = roundup(inosused + INOPB(&sblock), INOPB(&sblock));
192 if (inoopt && !preen && !rebuildcg &&
193 sblock.fs_magic == FS_UFS2_MAGIC &&
194 cgp->cg_initediblk > 2 * INOPB(&sblock) &&
195 mininos < cgp->cg_initediblk) {
196 i = cgp->cg_initediblk;
197 if (mininos < 2 * INOPB(&sblock))
198 cgp->cg_initediblk = 2 * INOPB(&sblock);
200 cgp->cg_initediblk = mininos;
201 pwarn("CYLINDER GROUP %d: RESET FROM %ju TO %d %s\n",
202 c, i, cgp->cg_initediblk, "VALID INODES");
205 if (inosused < sblock.fs_ipg)
208 if (lastino < (c * sblock.fs_ipg))
211 inosused = lastino - (c * sblock.fs_ipg);
212 if (rebuildcg && inosused > cgp->cg_initediblk &&
213 sblock.fs_magic == FS_UFS2_MAGIC) {
214 cgp->cg_initediblk = roundup(inosused, INOPB(&sblock));
215 pwarn("CYLINDER GROUP %d: FOUND %d VALID INODES\n", c,
219 * If we were not able to determine in advance which inodes
220 * were in use, then reduce the size of the inoinfo structure
221 * to the size necessary to describe the inodes that we
224 if (inumber == lastino)
226 inostathead[c].il_numalloced = inosused;
228 free(inostathead[c].il_stat);
229 inostathead[c].il_stat = NULL;
232 info = Calloc((unsigned)inosused, sizeof(struct inostat));
234 errx(EEXIT, "cannot alloc %u bytes for inoinfo",
235 (unsigned)(sizeof(struct inostat) * inosused));
236 memmove(info, inostathead[c].il_stat, inosused * sizeof(*info));
237 free(inostathead[c].il_stat);
238 inostathead[c].il_stat = info;
244 checkinode(ino_t inumber, struct inodesc *idesc, int rebuildcg)
247 off_t kernmaxfilesize;
252 if ((dp = getnextinode(inumber, rebuildcg)) == NULL)
254 mode = DIP(dp, di_mode) & IFMT;
256 if ((sblock.fs_magic == FS_UFS1_MAGIC &&
257 (memcmp(dp->dp1.di_db, ufs1_zino.di_db,
258 UFS_NDADDR * sizeof(ufs1_daddr_t)) ||
259 memcmp(dp->dp1.di_ib, ufs1_zino.di_ib,
260 UFS_NIADDR * sizeof(ufs1_daddr_t)) ||
261 dp->dp1.di_mode || dp->dp1.di_size)) ||
262 (sblock.fs_magic == FS_UFS2_MAGIC &&
263 (memcmp(dp->dp2.di_db, ufs2_zino.di_db,
264 UFS_NDADDR * sizeof(ufs2_daddr_t)) ||
265 memcmp(dp->dp2.di_ib, ufs2_zino.di_ib,
266 UFS_NIADDR * sizeof(ufs2_daddr_t)) ||
267 dp->dp2.di_mode || dp->dp2.di_size))) {
268 pfatal("PARTIALLY ALLOCATED INODE I=%lu",
270 if (reply("CLEAR") == 1) {
271 dp = ginode(inumber);
276 inoinfo(inumber)->ino_state = USTATE;
280 /* This should match the file size limit in ffs_mountfs(). */
281 if (sblock.fs_magic == FS_UFS1_MAGIC)
282 kernmaxfilesize = (off_t)0x40000000 * sblock.fs_bsize - 1;
284 kernmaxfilesize = sblock.fs_maxfilesize;
285 if (DIP(dp, di_size) > kernmaxfilesize ||
286 DIP(dp, di_size) > sblock.fs_maxfilesize ||
287 (mode == IFDIR && DIP(dp, di_size) > MAXDIRSIZE)) {
289 printf("bad size %ju:", (uintmax_t)DIP(dp, di_size));
292 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) {
293 dp = ginode(inumber);
294 DIP_SET(dp, di_size, sblock.fs_fsize);
295 DIP_SET(dp, di_mode, IFREG|0600);
298 if ((mode == IFBLK || mode == IFCHR || mode == IFIFO ||
299 mode == IFSOCK) && DIP(dp, di_size) != 0) {
301 printf("bad special-file size %ju:",
302 (uintmax_t)DIP(dp, di_size));
305 if ((mode == IFBLK || mode == IFCHR) &&
306 (dev_t)DIP(dp, di_rdev) == NODEV) {
308 printf("bad special-file rdev NODEV:");
311 ndb = howmany(DIP(dp, di_size), sblock.fs_bsize);
314 printf("bad size %ju ndb %ju:",
315 (uintmax_t)DIP(dp, di_size), (uintmax_t)ndb);
318 if (mode == IFBLK || mode == IFCHR)
322 * Fake ndb value so direct/indirect block checks below
323 * will detect any garbage after symlink string.
325 if (DIP(dp, di_size) < (off_t)sblock.fs_maxsymlinklen) {
326 if (sblock.fs_magic == FS_UFS1_MAGIC)
327 ndb = howmany(DIP(dp, di_size),
328 sizeof(ufs1_daddr_t));
330 ndb = howmany(DIP(dp, di_size),
331 sizeof(ufs2_daddr_t));
332 if (ndb > UFS_NDADDR) {
333 j = ndb - UFS_NDADDR;
334 for (ndb = 1; j > 1; j--)
335 ndb *= NINDIR(&sblock);
340 for (j = ndb; ndb < UFS_NDADDR && j < UFS_NDADDR; j++)
341 if (DIP(dp, di_db[j]) != 0) {
343 printf("bad direct addr[%d]: %ju\n", j,
344 (uintmax_t)DIP(dp, di_db[j]));
347 for (j = 0, ndb -= UFS_NDADDR; ndb > 0; j++)
348 ndb /= NINDIR(&sblock);
349 for (; j < UFS_NIADDR; j++)
350 if (DIP(dp, di_ib[j]) != 0) {
352 printf("bad indirect addr: %ju\n",
353 (uintmax_t)DIP(dp, di_ib[j]));
356 if (ftypeok(dp) == 0)
359 inoinfo(inumber)->ino_linkcnt = DIP(dp, di_nlink);
361 if (DIP(dp, di_size) == 0)
362 inoinfo(inumber)->ino_state = DCLEAR;
363 else if (DIP(dp, di_nlink) <= 0)
364 inoinfo(inumber)->ino_state = DZLINK;
366 inoinfo(inumber)->ino_state = DSTATE;
367 cacheino(dp, inumber);
369 } else if (DIP(dp, di_nlink) <= 0)
370 inoinfo(inumber)->ino_state = FZLINK;
372 inoinfo(inumber)->ino_state = FSTATE;
373 inoinfo(inumber)->ino_type = IFTODT(mode);
375 idesc->id_number = inumber;
376 if (DIP(dp, di_flags) & SF_SNAPSHOT)
377 idesc->id_type = SNAP;
379 idesc->id_type = ADDR;
380 (void)ckinode(dp, idesc);
381 if (sblock.fs_magic == FS_UFS2_MAGIC && dp->dp2.di_extsize > 0) {
382 idesc->id_type = ADDR;
383 ndb = howmany(dp->dp2.di_extsize, sblock.fs_bsize);
384 for (j = 0; j < UFS_NXADDR; j++) {
386 (offset = blkoff(&sblock, dp->dp2.di_extsize)) != 0)
387 idesc->id_numfrags = numfrags(&sblock,
388 fragroundup(&sblock, offset));
390 idesc->id_numfrags = sblock.fs_frag;
391 if (dp->dp2.di_extb[j] == 0)
393 idesc->id_blkno = dp->dp2.di_extb[j];
394 ret = (*idesc->id_func)(idesc);
399 if (sblock.fs_magic == FS_UFS2_MAGIC)
400 eascan(idesc, &dp->dp2);
401 idesc->id_entryno *= btodb(sblock.fs_fsize);
402 if (DIP(dp, di_blocks) != idesc->id_entryno) {
403 pwarn("INCORRECT BLOCK COUNT I=%lu (%ju should be %ju)",
404 (u_long)inumber, (uintmax_t)DIP(dp, di_blocks),
405 (uintmax_t)idesc->id_entryno);
407 printf(" (CORRECTED)\n");
408 else if (reply("CORRECT") == 0)
410 if (bkgrdflag == 0) {
411 dp = ginode(inumber);
412 DIP_SET(dp, di_blocks, idesc->id_entryno);
415 cmd.value = idesc->id_number;
416 cmd.size = idesc->id_entryno - DIP(dp, di_blocks);
418 printf("adjblkcnt ino %ju amount %lld\n",
419 (uintmax_t)cmd.value, (long long)cmd.size);
420 if (sysctl(adjblkcnt, MIBSIZE, 0, 0,
421 &cmd, sizeof cmd) == -1)
422 rwerror("ADJUST INODE BLOCK COUNT", cmd.value);
427 pfatal("UNKNOWN FILE TYPE I=%lu", (u_long)inumber);
428 inoinfo(inumber)->ino_state = FCLEAR;
429 if (reply("CLEAR") == 1) {
430 inoinfo(inumber)->ino_state = USTATE;
431 dp = ginode(inumber);
439 pass1check(struct inodesc *idesc)
443 ufs2_daddr_t blkno = idesc->id_blkno;
447 if (idesc->id_type == SNAP) {
448 if (blkno == BLK_NOCOPY)
450 if (idesc->id_number == cursnapshot) {
451 if (blkno == blkstofrags(&sblock, idesc->id_lbn))
453 if (blkno == BLK_SNAP) {
454 blkno = blkstofrags(&sblock, idesc->id_lbn);
455 idesc->id_entryno -= idesc->id_numfrags;
458 if (blkno == BLK_SNAP)
462 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) {
463 blkerror(idesc->id_number, "BAD", blkno);
464 if (badblk++ >= MAXBAD) {
465 pwarn("EXCESSIVE BAD BLKS I=%lu",
466 (u_long)idesc->id_number);
468 printf(" (SKIPPING)\n");
469 else if (reply("CONTINUE") == 0) {
477 for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) {
478 if (anyout && chkrange(blkno, 1)) {
480 } else if (!testbmap(blkno)) {
484 blkerror(idesc->id_number, "DUP", blkno);
485 if (dupblk++ >= MAXDUP) {
486 pwarn("EXCESSIVE DUP BLKS I=%lu",
487 (u_long)idesc->id_number);
489 printf(" (SKIPPING)\n");
490 else if (reply("CONTINUE") == 0) {
497 new = (struct dups *)Malloc(sizeof(struct dups));
499 pfatal("DUP TABLE OVERFLOW.");
500 if (reply("CONTINUE") == 0) {
508 if (muldup == NULL) {
509 duplist = muldup = new;
512 new->next = muldup->next;
515 for (dlp = duplist; dlp != muldup; dlp = dlp->next)
516 if (dlp->dup == blkno)
518 if (dlp == muldup && dlp->dup != blkno)
522 * count the number of blocks found in id_entryno