1 /* $NetBSD: pass5.c,v 1.31 2002/09/28 20:11:06 dbj 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. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by the University of 18 * California, Berkeley and its contributors. 19 * 4. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #include <sys/cdefs.h> 37 #ifndef lint 38 #if 0 39 static char sccsid[] = "@(#)pass5.c 8.9 (Berkeley) 4/28/95"; 40 #else 41 __RCSID("$NetBSD: pass5.c,v 1.31 2002/09/28 20:11:06 dbj Exp $"); 42 #endif 43 #endif /* not lint */ 44 45 #include <sys/param.h> 46 #include <sys/time.h> 47 48 #include <ufs/ufs/dinode.h> 49 #include <ufs/ffs/fs.h> 50 #include <ufs/ffs/ffs_extern.h> 51 #include <ufs/ufs/ufs_bswap.h> 52 53 #include <err.h> 54 #include <string.h> 55 #include <malloc.h> 56 57 #include "fsutil.h" 58 #include "fsck.h" 59 #include "extern.h" 60 61 void print_bmap __P((u_char *,u_int32_t)); 62 63 void 64 pass5() 65 { 66 int c, blk, frags, basesize, sumsize, mapsize, savednrpos = 0; 67 int32_t savednpsect, savedinterleave; 68 int inomapsize, blkmapsize; 69 struct fs *fs = sblock; 70 ufs_daddr_t dbase, dmax; 71 ufs_daddr_t d; 72 long i, j, k; 73 struct csum *cs; 74 struct csum cstotal; 75 struct inodesc idesc[4]; 76 char buf[MAXBSIZE]; 77 struct cg *newcg = (struct cg *)buf; 78 struct ocg *ocg = (struct ocg *)buf; 79 struct cg *cg = cgrp; 80 81 statemap[WINO] = USTATE; 82 memset(newcg, 0, (size_t)fs->fs_cgsize); 83 newcg->cg_niblk = fs->fs_ipg; 84 if (cvtlevel >= 3) { 85 if (fs->fs_maxcontig < 2 && fs->fs_contigsumsize > 0) { 86 if (preen) 87 pwarn("DELETING CLUSTERING MAPS\n"); 88 if (preen || reply("DELETE CLUSTERING MAPS")) { 89 fs->fs_contigsumsize = 0; 90 doinglevel1 = 1; 91 sbdirty(); 92 } 93 } 94 if (fs->fs_maxcontig > 1) { 95 char *doit = 0; 96 97 if (fs->fs_contigsumsize < 1) { 98 doit = "CREAT"; 99 } else if (fs->fs_contigsumsize < fs->fs_maxcontig && 100 fs->fs_contigsumsize < FS_MAXCONTIG) { 101 doit = "EXPAND"; 102 } 103 if (doit) { 104 i = fs->fs_contigsumsize; 105 fs->fs_contigsumsize = 106 MIN(fs->fs_maxcontig, FS_MAXCONTIG); 107 if (CGSIZE(fs) > fs->fs_bsize) { 108 pwarn("CANNOT %s CLUSTER MAPS\n", doit); 109 fs->fs_contigsumsize = i; 110 } else if (preen || 111 reply("CREATE CLUSTER MAPS")) { 112 if (preen) 113 pwarn("%sING CLUSTER MAPS\n", 114 doit); 115 fs->fs_cgsize = 116 fragroundup(fs, CGSIZE(fs)); 117 cg = cgrp = 118 realloc(cgrp, fs->fs_cgsize); 119 if (cg == NULL) 120 errx(EEXIT, 121 "cannot reallocate cg space"); 122 doinglevel1 = 1; 123 sbdirty(); 124 } 125 } 126 } 127 } 128 switch ((int)fs->fs_postblformat) { 129 130 case FS_42POSTBLFMT: 131 basesize = (char *)(&ocg->cg_btot[0]) - 132 (char *)(&ocg->cg_firstfield); 133 sumsize = &ocg->cg_iused[0] - (u_int8_t *)(&ocg->cg_btot[0]); 134 mapsize = &ocg->cg_free[howmany(fs->fs_fpg, NBBY)] - 135 (u_char *)&ocg->cg_iused[0]; 136 blkmapsize = howmany(fs->fs_fpg, NBBY); 137 inomapsize = &ocg->cg_free[0] - (u_char *)&ocg->cg_iused[0]; 138 ocg->cg_magic = CG_MAGIC; 139 savednrpos = fs->fs_nrpos; 140 savednpsect = fs->fs_npsect; 141 savedinterleave = fs->fs_interleave; 142 fs->fs_nrpos = 8; 143 fs->fs_npsect = fs->fs_nsect; 144 fs->fs_interleave = 1; 145 break; 146 147 case FS_DYNAMICPOSTBLFMT: 148 newcg->cg_btotoff = 149 &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield); 150 newcg->cg_boff = 151 newcg->cg_btotoff + fs->fs_cpg * sizeof(int32_t); 152 newcg->cg_iusedoff = newcg->cg_boff + 153 fs->fs_cpg * fs->fs_nrpos * sizeof(int16_t); 154 newcg->cg_freeoff = 155 newcg->cg_iusedoff + howmany(fs->fs_ipg, NBBY); 156 inomapsize = newcg->cg_freeoff - newcg->cg_iusedoff; 157 newcg->cg_nextfreeoff = newcg->cg_freeoff + 158 howmany(fs->fs_cpg * fs->fs_spc / NSPF(fs), NBBY); 159 blkmapsize = newcg->cg_nextfreeoff - newcg->cg_freeoff; 160 if (fs->fs_contigsumsize > 0) { 161 newcg->cg_clustersumoff = newcg->cg_nextfreeoff - 162 sizeof(int32_t); 163 if (isappleufs) { 164 /* Apple PR2216969 gives rationale for this change. 165 * I believe they were mistaken, but we need to 166 * duplicate it for compatibility. -- dbj@netbsd.org 167 */ 168 newcg->cg_clustersumoff += sizeof(int32_t); 169 } 170 newcg->cg_clustersumoff = 171 roundup(newcg->cg_clustersumoff, sizeof(int32_t)); 172 newcg->cg_clusteroff = newcg->cg_clustersumoff + 173 (fs->fs_contigsumsize + 1) * sizeof(int32_t); 174 newcg->cg_nextfreeoff = newcg->cg_clusteroff + 175 howmany(fs->fs_cpg * fs->fs_spc / NSPB(fs), NBBY); 176 } 177 newcg->cg_magic = CG_MAGIC; 178 basesize = &newcg->cg_space[0] - 179 (u_char *)(&newcg->cg_firstfield); 180 sumsize = newcg->cg_iusedoff - newcg->cg_btotoff; 181 mapsize = newcg->cg_nextfreeoff - newcg->cg_iusedoff; 182 break; 183 184 default: 185 inomapsize = blkmapsize = sumsize = 0; /* keep lint happy */ 186 errx(EEXIT, "UNKNOWN ROTATIONAL TABLE FORMAT %d", 187 fs->fs_postblformat); 188 } 189 memset(&idesc[0], 0, sizeof idesc); 190 for (i = 0; i < 4; i++) { 191 idesc[i].id_type = ADDR; 192 if (doinglevel2) 193 idesc[i].id_fix = FIX; 194 } 195 memset(&cstotal, 0, sizeof(struct csum)); 196 j = blknum(fs, fs->fs_size + fs->fs_frag - 1); 197 for (i = fs->fs_size; i < j; i++) 198 setbmap(i); 199 for (c = 0; c < fs->fs_ncg; c++) { 200 if (got_siginfo) { 201 fprintf(stderr, 202 "%s: phase 5: cyl group %d of %d (%d%%)\n", 203 cdevname(), c, fs->fs_ncg, 204 c * 100 / fs->fs_ncg); 205 got_siginfo = 0; 206 } 207 getblk(&cgblk, cgtod(fs, c), fs->fs_cgsize); 208 memcpy(cg, cgblk.b_un.b_cg, fs->fs_cgsize); 209 if((doswap && !needswap) || (!doswap && needswap)) 210 swap_cg(cgblk.b_un.b_cg, cg); 211 if (!cg_chkmagic(cg, 0)) 212 pfatal("CG %d: PASS5: BAD MAGIC NUMBER\n", c); 213 if(doswap) 214 cgdirty(); 215 /* 216 * While we have the disk head where we want it, 217 * write back the superblock to the spare at this 218 * cylinder group. 219 */ 220 if ((cvtlevel && sblk.b_dirty) || doswap) { 221 bwrite(fswritefd, sblk.b_un.b_buf, 222 fsbtodb(sblock, cgsblock(sblock, c)), 223 sblock->fs_sbsize); 224 } else { 225 /* 226 * Read in the current alternate superblock, 227 * and compare it to the master. If it's 228 * wrong, fix it up. 229 */ 230 getblk(&asblk, cgsblock(sblock, c), sblock->fs_sbsize); 231 if (asblk.b_errs) 232 pfatal("CG %d: UNABLE TO READ ALTERNATE " 233 "SUPERBLK\n", c); 234 else { 235 memmove(altsblock, asblk.b_un.b_fs, 236 sblock->fs_sbsize); 237 if (needswap) 238 ffs_sb_swap(asblk.b_un.b_fs, altsblock); 239 } 240 if ((asblk.b_errs || cmpsblks(sblock, altsblock)) && 241 dofix(&idesc[3], 242 "ALTERNATE SUPERBLK(S) ARE INCORRECT")) { 243 bwrite(fswritefd, sblk.b_un.b_buf, 244 fsbtodb(sblock, cgsblock(sblock, c)), 245 sblock->fs_sbsize); 246 } 247 } 248 dbase = cgbase(fs, c); 249 dmax = dbase + fs->fs_fpg; 250 if (dmax > fs->fs_size) 251 dmax = fs->fs_size; 252 newcg->cg_time = cg->cg_time; 253 newcg->cg_cgx = c; 254 if (c == fs->fs_ncg - 1) 255 newcg->cg_ncyl = fs->fs_ncyl % fs->fs_cpg; 256 else 257 newcg->cg_ncyl = fs->fs_cpg; 258 newcg->cg_ndblk = dmax - dbase; 259 if (fs->fs_contigsumsize > 0) 260 newcg->cg_nclusterblks = newcg->cg_ndblk / fs->fs_frag; 261 newcg->cg_cs.cs_ndir = 0; 262 newcg->cg_cs.cs_nffree = 0; 263 newcg->cg_cs.cs_nbfree = 0; 264 newcg->cg_cs.cs_nifree = fs->fs_ipg; 265 if (cg->cg_rotor >= 0 && cg->cg_rotor < newcg->cg_ndblk) 266 newcg->cg_rotor = cg->cg_rotor; 267 else 268 newcg->cg_rotor = 0; 269 if (cg->cg_frotor >= 0 && cg->cg_frotor < newcg->cg_ndblk) 270 newcg->cg_frotor = cg->cg_frotor; 271 else 272 newcg->cg_frotor = 0; 273 if (cg->cg_irotor >= 0 && cg->cg_irotor < newcg->cg_niblk) 274 newcg->cg_irotor = cg->cg_irotor; 275 else 276 newcg->cg_irotor = 0; 277 memset(&newcg->cg_frsum[0], 0, sizeof newcg->cg_frsum); 278 memset(&cg_blktot(newcg, 0)[0], 0, 279 (size_t)(sumsize + mapsize)); 280 if (fs->fs_postblformat == FS_42POSTBLFMT) 281 ocg->cg_magic = CG_MAGIC; 282 j = fs->fs_ipg * c; 283 for (i = 0; i < fs->fs_ipg; j++, i++) { 284 switch (statemap[j]) { 285 286 case USTATE: 287 break; 288 289 case DSTATE: 290 case DCLEAR: 291 case DFOUND: 292 newcg->cg_cs.cs_ndir++; 293 /* fall through */ 294 295 case FSTATE: 296 case FCLEAR: 297 newcg->cg_cs.cs_nifree--; 298 setbit(cg_inosused(newcg, 0), i); 299 break; 300 301 default: 302 if (j < ROOTINO) 303 break; 304 errx(EEXIT, "BAD STATE %d FOR INODE I=%ld", 305 statemap[j], (long)j); 306 } 307 } 308 if (c == 0) 309 for (i = 0; i < ROOTINO; i++) { 310 setbit(cg_inosused(newcg, 0), i); 311 newcg->cg_cs.cs_nifree--; 312 } 313 for (i = 0, d = dbase; 314 d < dmax; 315 d += fs->fs_frag, i += fs->fs_frag) { 316 frags = 0; 317 for (j = 0; j < fs->fs_frag; j++) { 318 if (testbmap(d + j)) 319 continue; 320 setbit(cg_blksfree(newcg, 0), i + j); 321 frags++; 322 } 323 if (frags == fs->fs_frag) { 324 newcg->cg_cs.cs_nbfree++; 325 j = cbtocylno(fs, i); 326 cg_blktot(newcg, 0)[j]++; 327 cg_blks(fs, newcg, j, 0)[cbtorpos(fs, i)]++; 328 if (fs->fs_contigsumsize > 0) 329 setbit(cg_clustersfree(newcg, 0), 330 fragstoblks(fs, i)); 331 } else if (frags > 0) { 332 newcg->cg_cs.cs_nffree += frags; 333 blk = blkmap(fs, cg_blksfree(newcg, 0), i); 334 ffs_fragacct(fs, blk, newcg->cg_frsum, 1, 0); 335 } 336 } 337 if (fs->fs_contigsumsize > 0) { 338 int32_t *sump = cg_clustersum(newcg, 0); 339 u_char *mapp = cg_clustersfree(newcg, 0); 340 int map = *mapp++; 341 int bit = 1; 342 int run = 0; 343 344 for (i = 0; i < newcg->cg_nclusterblks; i++) { 345 if ((map & bit) != 0) { 346 run++; 347 } else if (run != 0) { 348 if (run > fs->fs_contigsumsize) 349 run = fs->fs_contigsumsize; 350 sump[run]++; 351 run = 0; 352 } 353 if ((i & (NBBY - 1)) != (NBBY - 1)) { 354 bit <<= 1; 355 } else { 356 map = *mapp++; 357 bit = 1; 358 } 359 } 360 if (run != 0) { 361 if (run > fs->fs_contigsumsize) 362 run = fs->fs_contigsumsize; 363 sump[run]++; 364 } 365 } 366 cstotal.cs_nffree += newcg->cg_cs.cs_nffree; 367 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree; 368 cstotal.cs_nifree += newcg->cg_cs.cs_nifree; 369 cstotal.cs_ndir += newcg->cg_cs.cs_ndir; 370 cs = &fs->fs_cs(fs, c); 371 if (memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0) { 372 if (dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 373 memmove(cs, &newcg->cg_cs, sizeof *cs); 374 sbdirty(); 375 } else 376 markclean = 0; 377 } 378 if (doinglevel1) { 379 memmove(cg, newcg, (size_t)fs->fs_cgsize); 380 cgdirty(); 381 continue; 382 } 383 if (memcmp(newcg, cg, basesize) != 0 || 384 memcmp(&cg_blktot(newcg, 0)[0], 385 &cg_blktot(cg, 0)[0], sumsize) != 0) { 386 if (dofix(&idesc[2], "SUMMARY INFORMATION BAD")) { 387 memmove(cg, newcg, (size_t)basesize); 388 memmove(&cg_blktot(cg, 0)[0], 389 &cg_blktot(newcg, 0)[0], (size_t)sumsize); 390 cgdirty(); 391 } else 392 markclean = 0; 393 } 394 if (usedsoftdep) { 395 for (i = 0; i < inomapsize; i++) { 396 j = cg_inosused(newcg, 0)[i]; 397 if ((cg_inosused(cg, 0)[i] & j) == j) 398 continue; 399 for (k = 0; k < NBBY; k++) { 400 if ((j & (1 << k)) == 0) 401 continue; 402 if (cg_inosused(cg, 0)[i] & (1 << k)) 403 continue; 404 pwarn("ALLOCATED INODE %ld " 405 "MARKED FREE\n", 406 c * fs->fs_ipg + i * 8 + k); 407 } 408 } 409 for (i = 0; i < blkmapsize; i++) { 410 j = cg_blksfree(cg, 0)[i]; 411 if ((cg_blksfree(newcg, 0)[i] & j) == j) 412 continue; 413 for (k = 0; k < NBBY; k++) { 414 if ((j & (1 << k)) == 0) 415 continue; 416 if (cg_inosused(cg, 0)[i] & (1 << k)) 417 continue; 418 pwarn("ALLOCATED FRAG %ld " 419 "MARKED FREE\n", 420 c * fs->fs_fpg + i * 8 + k); 421 } 422 } 423 } 424 if (memcmp(cg_inosused(newcg, 0), cg_inosused(cg, 0), mapsize) 425 != 0 && dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) { 426 memmove(cg_inosused(cg, 0), cg_inosused(newcg, 0), 427 (size_t)mapsize); 428 cgdirty(); 429 } 430 } 431 if (fs->fs_postblformat == FS_42POSTBLFMT) { 432 fs->fs_nrpos = savednrpos; 433 fs->fs_npsect = savednpsect; 434 fs->fs_interleave = savedinterleave; 435 } 436 if (memcmp(&cstotal, &fs->fs_cstotal, sizeof *cs) != 0) { 437 if (dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 438 memmove(&fs->fs_cstotal, &cstotal, sizeof *cs); 439 fs->fs_ronly = 0; 440 fs->fs_fmod = 0; 441 sbdirty(); 442 } else 443 markclean = 0; 444 } 445 } 446 447 void 448 print_bmap(map, size) 449 u_char *map; 450 u_int32_t size; 451 { 452 int i, j; 453 454 i = 0; 455 while (i < size) { 456 printf("%u: ",i); 457 for (j = 0; j < 16; j++, i++) 458 printf("%2x ", (u_int)map[i] & 0xff); 459 printf("\n"); 460 } 461 } 462