2 * Copyright (c) 1980, 1986, 1993
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * @(#)pass5.c 8.9 (Berkeley) 4/28/95
30 * $FreeBSD: src/sbin/fsck/pass5.c,v 1.17.2.2 2002/11/26 04:46:59 julian Exp $
33 #include <sys/param.h>
35 #include <vfs/ufs/dinode.h>
36 #include <vfs/ufs/fs.h>
46 int c, blk, frags, basesize, sumsize, mapsize, savednrpos = 0;
47 int inomapsize, blkmapsize;
48 struct fs *fs = &sblock;
49 struct cg *cg = &cgrp;
50 ufs_daddr_t dbase, dmax;
55 struct inodesc idesc[3];
57 struct cg *newcg = (struct cg *)buf;
58 struct ocg *ocg = (struct ocg *)buf;
60 inoinfo(WINO)->ino_state = USTATE;
61 memset(newcg, 0, (size_t)fs->fs_cgsize);
62 newcg->cg_niblk = fs->fs_ipg;
64 if (fs->fs_maxcontig < 2 && fs->fs_contigsumsize > 0) {
66 pwarn("DELETING CLUSTERING MAPS\n");
67 if (preen || reply("DELETE CLUSTERING MAPS")) {
68 fs->fs_contigsumsize = 0;
73 if (fs->fs_maxcontig > 1) {
76 if (fs->fs_contigsumsize < 1) {
78 } else if (fs->fs_contigsumsize < fs->fs_maxcontig &&
79 fs->fs_contigsumsize < FS_MAXCONTIG) {
83 i = fs->fs_contigsumsize;
84 fs->fs_contigsumsize =
85 MIN(fs->fs_maxcontig, FS_MAXCONTIG);
86 if (CGSIZE(fs) > fs->fs_bsize) {
87 pwarn("CANNOT %s CLUSTER MAPS\n", doit);
88 fs->fs_contigsumsize = i;
90 reply("CREATE CLUSTER MAPS")) {
92 pwarn("%sING CLUSTER MAPS\n",
95 fragroundup(fs, CGSIZE(fs));
102 switch ((int)fs->fs_postblformat) {
105 basesize = (char *)(&ocg->cg_btot[0]) -
106 (char *)(&ocg->cg_firstfield);
107 sumsize = &ocg->cg_iused[0] - (u_int8_t *)(&ocg->cg_btot[0]);
108 mapsize = &ocg->cg_free[howmany(fs->fs_fpg, NBBY)] -
109 (u_char *)&ocg->cg_iused[0];
110 blkmapsize = howmany(fs->fs_fpg, NBBY);
111 inomapsize = &ocg->cg_free[0] - (u_char *)&ocg->cg_iused[0];
112 ocg->cg_magic = CG_MAGIC;
113 savednrpos = fs->fs_nrpos;
117 case FS_DYNAMICPOSTBLFMT:
119 &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield);
121 newcg->cg_btotoff + fs->fs_cpg * sizeof(int32_t);
122 newcg->cg_iusedoff = newcg->cg_boff +
123 fs->fs_cpg * fs->fs_nrpos * sizeof(u_int16_t);
125 newcg->cg_iusedoff + howmany(fs->fs_ipg, NBBY);
126 inomapsize = newcg->cg_freeoff - newcg->cg_iusedoff;
127 newcg->cg_nextfreeoff = newcg->cg_freeoff +
128 howmany(fs->fs_cpg * fs->fs_spc / NSPF(fs), NBBY);
129 blkmapsize = newcg->cg_nextfreeoff - newcg->cg_freeoff;
130 if (fs->fs_contigsumsize > 0) {
131 newcg->cg_clustersumoff = newcg->cg_nextfreeoff -
133 newcg->cg_clustersumoff =
134 roundup(newcg->cg_clustersumoff, sizeof(u_int32_t));
135 newcg->cg_clusteroff = newcg->cg_clustersumoff +
136 (fs->fs_contigsumsize + 1) * sizeof(u_int32_t);
137 newcg->cg_nextfreeoff = newcg->cg_clusteroff +
138 howmany(fs->fs_cpg * fs->fs_spc / NSPB(fs), NBBY);
140 newcg->cg_magic = CG_MAGIC;
141 basesize = &newcg->cg_space[0] -
142 (u_char *)(&newcg->cg_firstfield);
143 sumsize = newcg->cg_iusedoff - newcg->cg_btotoff;
144 mapsize = newcg->cg_nextfreeoff - newcg->cg_iusedoff;
148 inomapsize = blkmapsize = sumsize = 0; /* keep lint happy */
149 errx(EEXIT, "UNKNOWN ROTATIONAL TABLE FORMAT %d",
150 fs->fs_postblformat);
152 memset(&idesc[0], 0, sizeof idesc);
153 for (i = 0; i < 3; i++) {
154 idesc[i].id_type = ADDR;
156 idesc[i].id_fix = FIX;
158 memset(&cstotal, 0, sizeof(struct csum));
159 j = blknum(fs, fs->fs_size + fs->fs_frag - 1);
160 for (i = fs->fs_size; i < j; i++)
162 for (c = 0; c < fs->fs_ncg; c++) {
164 printf("%s: phase 5: cyl group %d of %d (%d%%)\n",
165 cdevname, c, sblock.fs_ncg,
166 c * 100 / sblock.fs_ncg);
169 getblk(&cgblk, cgtod(fs, c), fs->fs_cgsize);
170 if (!cg_chkmagic(cg))
171 pfatal("CG %d: BAD MAGIC NUMBER\n", c);
172 dbase = cgbase(fs, c);
173 dmax = dbase + fs->fs_fpg;
174 if (dmax > fs->fs_size)
176 newcg->cg_time = cg->cg_time;
178 if (c == fs->fs_ncg - 1)
179 newcg->cg_ncyl = fs->fs_ncyl % fs->fs_cpg;
181 newcg->cg_ncyl = fs->fs_cpg;
182 newcg->cg_ndblk = dmax - dbase;
183 if (fs->fs_contigsumsize > 0)
184 newcg->cg_nclusterblks = newcg->cg_ndblk / fs->fs_frag;
185 newcg->cg_cs.cs_ndir = 0;
186 newcg->cg_cs.cs_nffree = 0;
187 newcg->cg_cs.cs_nbfree = 0;
188 newcg->cg_cs.cs_nifree = fs->fs_ipg;
189 if ((cg->cg_rotor >= 0) && (cg->cg_rotor < newcg->cg_ndblk))
190 newcg->cg_rotor = cg->cg_rotor;
193 if ((cg->cg_frotor >= 0) && (cg->cg_frotor < newcg->cg_ndblk))
194 newcg->cg_frotor = cg->cg_frotor;
196 newcg->cg_frotor = 0;
197 if ((cg->cg_irotor >= 0) && (cg->cg_irotor < newcg->cg_niblk))
198 newcg->cg_irotor = cg->cg_irotor;
200 newcg->cg_irotor = 0;
201 memset(&newcg->cg_frsum[0], 0, sizeof newcg->cg_frsum);
202 memset(&cg_blktot(newcg)[0], 0,
203 (size_t)(sumsize + mapsize));
204 if (fs->fs_postblformat == FS_42POSTBLFMT)
205 ocg->cg_magic = CG_MAGIC;
207 for (i = 0; i < inostathead[c].il_numalloced; j++, i++) {
208 switch (inoinfo(j)->ino_state) {
216 newcg->cg_cs.cs_ndir++;
221 newcg->cg_cs.cs_nifree--;
222 setbit(cg_inosused(newcg), i);
228 errx(EEXIT, "BAD STATE %d FOR INODE I=%ld",
229 inoinfo(j)->ino_state, j);
233 for (i = 0; i < ROOTINO; i++) {
234 setbit(cg_inosused(newcg), i);
235 newcg->cg_cs.cs_nifree--;
237 for (i = 0, d = dbase;
239 d += fs->fs_frag, i += fs->fs_frag) {
241 for (j = 0; j < fs->fs_frag; j++) {
244 setbit(cg_blksfree(newcg), i + j);
247 if (frags == fs->fs_frag) {
248 newcg->cg_cs.cs_nbfree++;
249 j = cbtocylno(fs, i);
250 cg_blktot(newcg)[j]++;
251 cg_blks(fs, newcg, j)[cbtorpos(fs, i)]++;
252 if (fs->fs_contigsumsize > 0)
253 setbit(cg_clustersfree(newcg),
255 } else if (frags > 0) {
256 newcg->cg_cs.cs_nffree += frags;
257 blk = blkmap(fs, cg_blksfree(newcg), i);
258 ffs_fragacct(fs, blk, newcg->cg_frsum, 1);
261 if (fs->fs_contigsumsize > 0) {
262 int32_t *sump = cg_clustersum(newcg);
263 u_char *mapp = cg_clustersfree(newcg);
268 for (i = 0; i < newcg->cg_nclusterblks; i++) {
269 if ((map & bit) != 0) {
271 } else if (run != 0) {
272 if (run > fs->fs_contigsumsize)
273 run = fs->fs_contigsumsize;
277 if ((i & (NBBY - 1)) != (NBBY - 1)) {
285 if (run > fs->fs_contigsumsize)
286 run = fs->fs_contigsumsize;
290 cstotal.cs_nffree += newcg->cg_cs.cs_nffree;
291 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree;
292 cstotal.cs_nifree += newcg->cg_cs.cs_nifree;
293 cstotal.cs_ndir += newcg->cg_cs.cs_ndir;
294 cs = &fs->fs_cs(fs, c);
295 if (memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0 &&
296 dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) {
297 memmove(cs, &newcg->cg_cs, sizeof *cs);
301 memmove(cg, newcg, (size_t)fs->fs_cgsize);
305 if ((memcmp(newcg, cg, basesize) != 0 ||
306 memcmp(&cg_blktot(newcg)[0],
307 &cg_blktot(cg)[0], sumsize) != 0) &&
308 dofix(&idesc[2], "SUMMARY INFORMATION BAD")) {
309 memmove(cg, newcg, (size_t)basesize);
310 memmove(&cg_blktot(cg)[0],
311 &cg_blktot(newcg)[0], (size_t)sumsize);
315 for (i = 0; i < inomapsize; i++) {
316 j = cg_inosused(newcg)[i];
317 if ((cg_inosused(cg)[i] & j) == j)
319 for (k = 0; k < NBBY; k++) {
320 if ((j & (1 << k)) == 0)
322 if (cg_inosused(cg)[i] & (1 << k))
324 pwarn("ALLOCATED INODE %ld MARKED FREE\n",
325 c * fs->fs_ipg + i * NBBY + k);
328 for (i = 0; i < blkmapsize; i++) {
329 j = cg_blksfree(cg)[i];
330 if ((cg_blksfree(newcg)[i] & j) == j)
332 for (k = 0; k < NBBY; k++) {
333 if ((j & (1 << k)) == 0)
335 if (cg_blksfree(newcg)[i] & (1 << k))
337 pwarn("ALLOCATED FRAG %ld MARKED FREE\n",
338 c * fs->fs_fpg + i * NBBY + k);
342 if (memcmp(cg_inosused(newcg), cg_inosused(cg), mapsize) != 0 &&
343 dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) {
344 memmove(cg_inosused(cg), cg_inosused(newcg),
349 if (fs->fs_postblformat == FS_42POSTBLFMT)
350 fs->fs_nrpos = savednrpos;
351 if (memcmp(&cstotal, &fs->fs_cstotal, sizeof *cs) != 0
352 && dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) {
353 memmove(&fs->fs_cstotal, &cstotal, sizeof *cs);