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;
253 if ((dp = getnextinode(inumber, rebuildcg)) == NULL)
255 mode = DIP(dp, di_mode) & IFMT;
257 if ((sblock.fs_magic == FS_UFS1_MAGIC &&
258 (memcmp(dp->dp1.di_db, ufs1_zino.di_db,
259 UFS_NDADDR * sizeof(ufs1_daddr_t)) ||
260 memcmp(dp->dp1.di_ib, ufs1_zino.di_ib,
261 UFS_NIADDR * sizeof(ufs1_daddr_t)) ||
262 dp->dp1.di_mode || dp->dp1.di_size)) ||
263 (sblock.fs_magic == FS_UFS2_MAGIC &&
264 (memcmp(dp->dp2.di_db, ufs2_zino.di_db,
265 UFS_NDADDR * sizeof(ufs2_daddr_t)) ||
266 memcmp(dp->dp2.di_ib, ufs2_zino.di_ib,
267 UFS_NIADDR * sizeof(ufs2_daddr_t)) ||
268 dp->dp2.di_mode || dp->dp2.di_size))) {
269 pfatal("PARTIALLY ALLOCATED INODE I=%lu",
271 if (reply("CLEAR") == 1) {
272 dp = ginode(inumber);
277 inoinfo(inumber)->ino_state = USTATE;
281 /* This should match the file size limit in ffs_mountfs(). */
282 if (sblock.fs_magic == FS_UFS1_MAGIC)
283 kernmaxfilesize = (off_t)0x40000000 * sblock.fs_bsize - 1;
285 kernmaxfilesize = sblock.fs_maxfilesize;
286 if (DIP(dp, di_size) > kernmaxfilesize ||
287 DIP(dp, di_size) > sblock.fs_maxfilesize ||
288 (mode == IFDIR && DIP(dp, di_size) > MAXDIRSIZE)) {
290 printf("bad size %ju:", (uintmax_t)DIP(dp, di_size));
293 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) {
294 dp = ginode(inumber);
295 DIP_SET(dp, di_size, sblock.fs_fsize);
296 DIP_SET(dp, di_mode, IFREG|0600);
299 if ((mode == IFBLK || mode == IFCHR || mode == IFIFO ||
300 mode == IFSOCK) && DIP(dp, di_size) != 0) {
302 printf("bad special-file size %ju:",
303 (uintmax_t)DIP(dp, di_size));
306 if ((mode == IFBLK || mode == IFCHR) &&
307 (dev_t)DIP(dp, di_rdev) == NODEV) {
309 printf("bad special-file rdev NODEV:");
312 ndb = howmany(DIP(dp, di_size), sblock.fs_bsize);
315 printf("bad size %ju ndb %ju:",
316 (uintmax_t)DIP(dp, di_size), (uintmax_t)ndb);
319 if (mode == IFBLK || mode == IFCHR)
323 * Fake ndb value so direct/indirect block checks below
324 * will detect any garbage after symlink string.
326 if (DIP(dp, di_size) < (off_t)sblock.fs_maxsymlinklen) {
327 if (sblock.fs_magic == FS_UFS1_MAGIC)
328 ndb = howmany(DIP(dp, di_size),
329 sizeof(ufs1_daddr_t));
331 ndb = howmany(DIP(dp, di_size),
332 sizeof(ufs2_daddr_t));
333 if (ndb > UFS_NDADDR) {
334 j = ndb - UFS_NDADDR;
335 for (ndb = 1; j > 1; j--)
336 ndb *= NINDIR(&sblock);
341 for (j = ndb; ndb < UFS_NDADDR && j < UFS_NDADDR; j++)
342 if (DIP(dp, di_db[j]) != 0) {
344 printf("bad direct addr[%d]: %ju\n", j,
345 (uintmax_t)DIP(dp, di_db[j]));
348 for (j = 0, ndb -= UFS_NDADDR; ndb > 0; j++)
349 ndb /= NINDIR(&sblock);
350 for (; j < UFS_NIADDR; j++)
351 if (DIP(dp, di_ib[j]) != 0) {
353 printf("bad indirect addr: %ju\n",
354 (uintmax_t)DIP(dp, di_ib[j]));
357 if (ftypeok(dp) == 0)
360 inoinfo(inumber)->ino_linkcnt = DIP(dp, di_nlink);
362 if (DIP(dp, di_size) == 0)
363 inoinfo(inumber)->ino_state = DCLEAR;
364 else if (DIP(dp, di_nlink) <= 0)
365 inoinfo(inumber)->ino_state = DZLINK;
367 inoinfo(inumber)->ino_state = DSTATE;
368 cacheino(dp, inumber);
370 } else if (DIP(dp, di_nlink) <= 0)
371 inoinfo(inumber)->ino_state = FZLINK;
373 inoinfo(inumber)->ino_state = FSTATE;
374 inoinfo(inumber)->ino_type = IFTODT(mode);
376 idesc->id_number = inumber;
377 if (DIP(dp, di_flags) & SF_SNAPSHOT)
378 idesc->id_type = SNAP;
380 idesc->id_type = ADDR;
381 (void)ckinode(dp, idesc);
382 if (sblock.fs_magic == FS_UFS2_MAGIC && dp->dp2.di_extsize > 0) {
383 idesc->id_type = ADDR;
384 ndb = howmany(dp->dp2.di_extsize, sblock.fs_bsize);
385 for (j = 0; j < UFS_NXADDR; j++) {
387 (offset = blkoff(&sblock, dp->dp2.di_extsize)) != 0)
388 idesc->id_numfrags = numfrags(&sblock,
389 fragroundup(&sblock, offset));
391 idesc->id_numfrags = sblock.fs_frag;
392 if (dp->dp2.di_extb[j] == 0)
394 idesc->id_blkno = dp->dp2.di_extb[j];
395 ret = (*idesc->id_func)(idesc);
400 if (sblock.fs_magic == FS_UFS2_MAGIC)
401 eascan(idesc, &dp->dp2);
402 idesc->id_entryno *= btodb(sblock.fs_fsize);
403 if (DIP(dp, di_blocks) != idesc->id_entryno) {
404 pwarn("INCORRECT BLOCK COUNT I=%lu (%ju should be %ju)",
405 (u_long)inumber, (uintmax_t)DIP(dp, di_blocks),
406 (uintmax_t)idesc->id_entryno);
408 printf(" (CORRECTED)\n");
409 else if (reply("CORRECT") == 0)
411 if (bkgrdflag == 0) {
412 dp = ginode(inumber);
413 DIP_SET(dp, di_blocks, idesc->id_entryno);
416 cmd.value = idesc->id_number;
417 cmd.size = idesc->id_entryno - DIP(dp, di_blocks);
419 printf("adjblkcnt ino %ju amount %lld\n",
420 (uintmax_t)cmd.value, (long long)cmd.size);
421 if (sysctl(adjblkcnt, MIBSIZE, 0, 0,
422 &cmd, sizeof cmd) == -1)
423 rwerror("ADJUST INODE BLOCK COUNT", cmd.value);
427 * Soft updates will always ensure that the file size is correct
428 * for files that contain only direct block pointers. However
429 * soft updates does not roll back sizes for files with indirect
430 * blocks that it has set to unallocated because their contents
431 * have not yet been written to disk. Hence, the file can appear
432 * to have a hole at its end because the block pointer has been
433 * rolled back to zero. Thus, id_lballoc tracks the last allocated
434 * block in the file. Here, for files that extend into indirect
435 * blocks, we check for a size past the last allocated block of
436 * the file and if that is found, shorten the file to reference
437 * the last allocated block to avoid having it reference a hole
440 if (DIP(dp, di_size) > UFS_NDADDR * sblock.fs_bsize &&
441 idesc->id_lballoc < lblkno(&sblock, DIP(dp, di_size) - 1)) {
442 fixsize = lblktosize(&sblock, idesc->id_lballoc + 1);
443 pwarn("INODE %lu: FILE SIZE %ju BEYOND END OF ALLOCATED FILE, "
444 "SIZE SHOULD BE %ju", (u_long)inumber,
445 (uintmax_t)DIP(dp, di_size), fixsize);
447 printf(" (ADJUSTED)\n");
448 else if (reply("ADJUST") == 0)
450 if (bkgrdflag == 0) {
451 dp = ginode(inumber);
452 DIP_SET(dp, di_size, fixsize);
455 cmd.value = idesc->id_number;
458 printf("setsize ino %ju size set to %ju\n",
459 (uintmax_t)cmd.value, (uintmax_t)cmd.size);
460 if (sysctl(setsize, MIBSIZE, 0, 0,
461 &cmd, sizeof cmd) == -1)
462 rwerror("SET INODE SIZE", cmd.value);
468 pfatal("UNKNOWN FILE TYPE I=%lu", (u_long)inumber);
469 inoinfo(inumber)->ino_state = FCLEAR;
470 if (reply("CLEAR") == 1) {
471 inoinfo(inumber)->ino_state = USTATE;
472 dp = ginode(inumber);
480 pass1check(struct inodesc *idesc)
484 ufs2_daddr_t blkno = idesc->id_blkno;
488 if (idesc->id_type == SNAP) {
489 if (blkno == BLK_NOCOPY)
491 if (idesc->id_number == cursnapshot) {
492 if (blkno == blkstofrags(&sblock, idesc->id_lbn))
494 if (blkno == BLK_SNAP) {
495 blkno = blkstofrags(&sblock, idesc->id_lbn);
496 idesc->id_entryno -= idesc->id_numfrags;
499 if (blkno == BLK_SNAP)
503 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) {
504 blkerror(idesc->id_number, "BAD", blkno);
505 if (badblk++ >= MAXBAD) {
506 pwarn("EXCESSIVE BAD BLKS I=%lu",
507 (u_long)idesc->id_number);
509 printf(" (SKIPPING)\n");
510 else if (reply("CONTINUE") == 0) {
518 for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) {
519 if (anyout && chkrange(blkno, 1)) {
521 } else if (!testbmap(blkno)) {
525 blkerror(idesc->id_number, "DUP", blkno);
526 if (dupblk++ >= MAXDUP) {
527 pwarn("EXCESSIVE DUP BLKS I=%lu",
528 (u_long)idesc->id_number);
530 printf(" (SKIPPING)\n");
531 else if (reply("CONTINUE") == 0) {
538 new = (struct dups *)Malloc(sizeof(struct dups));
540 pfatal("DUP TABLE OVERFLOW.");
541 if (reply("CONTINUE") == 0) {
549 if (muldup == NULL) {
550 duplist = muldup = new;
553 new->next = muldup->next;
556 for (dlp = duplist; dlp != muldup; dlp = dlp->next)
557 if (dlp->dup == blkno)
559 if (dlp == muldup && dlp->dup != blkno)
563 * count the number of blocks found in id_entryno
567 if (idesc->id_level == 0 && idesc->id_lballoc < idesc->id_lbn)
568 idesc->id_lballoc = idesc->id_lbn;