1 /* $NetBSD: pass5.c,v 1.23 1999/11/28 20:03:17 bouyer 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.23 1999/11/28 20:03:17 bouyer 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 int inomapsize, blkmapsize; 68 struct fs *fs = sblock; 69 ufs_daddr_t dbase, dmax; 70 ufs_daddr_t d; 71 long i, j, k; 72 struct csum *cs; 73 struct csum cstotal; 74 struct inodesc idesc[3]; 75 char buf[MAXBSIZE]; 76 struct cg *newcg = (struct cg *)buf; 77 struct ocg *ocg = (struct ocg *)buf; 78 struct cg *cg = cgrp; 79 80 statemap[WINO] = USTATE; 81 memset(newcg, 0, (size_t)fs->fs_cgsize); 82 newcg->cg_niblk = fs->fs_ipg; 83 if (cvtlevel >= 3) { 84 if (fs->fs_maxcontig < 2 && fs->fs_contigsumsize > 0) { 85 if (preen) 86 pwarn("DELETING CLUSTERING MAPS\n"); 87 if (preen || reply("DELETE CLUSTERING MAPS")) { 88 fs->fs_contigsumsize = 0; 89 doinglevel1 = 1; 90 sbdirty(); 91 } 92 } 93 if (fs->fs_maxcontig > 1) { 94 char *doit = 0; 95 96 if (fs->fs_contigsumsize < 1) { 97 doit = "CREAT"; 98 } else if (fs->fs_contigsumsize < fs->fs_maxcontig && 99 fs->fs_contigsumsize < FS_MAXCONTIG) { 100 doit = "EXPAND"; 101 } 102 if (doit) { 103 i = fs->fs_contigsumsize; 104 fs->fs_contigsumsize = 105 MIN(fs->fs_maxcontig, FS_MAXCONTIG); 106 if (CGSIZE(fs) > fs->fs_bsize) { 107 pwarn("CANNOT %s CLUSTER MAPS\n", doit); 108 fs->fs_contigsumsize = i; 109 } else if (preen || 110 reply("CREATE CLUSTER MAPS")) { 111 if (preen) 112 pwarn("%sING CLUSTER MAPS\n", 113 doit); 114 fs->fs_cgsize = 115 fragroundup(fs, CGSIZE(fs)); 116 cg = cgrp = 117 realloc(cgrp, fs->fs_cgsize); 118 if (cg == NULL) 119 errx(EEXIT, 120 "cannot reallocate cg space"); 121 doinglevel1 = 1; 122 sbdirty(); 123 } 124 } 125 } 126 } 127 switch ((int)fs->fs_postblformat) { 128 129 case FS_42POSTBLFMT: 130 basesize = (char *)(&ocg->cg_btot[0]) - 131 (char *)(&ocg->cg_firstfield); 132 sumsize = &ocg->cg_iused[0] - (u_int8_t *)(&ocg->cg_btot[0]); 133 mapsize = &ocg->cg_free[howmany(fs->fs_fpg, NBBY)] - 134 (u_char *)&ocg->cg_iused[0]; 135 blkmapsize = howmany(fs->fs_fpg, NBBY); 136 inomapsize = &ocg->cg_free[0] - (u_char *)&ocg->cg_iused[0]; 137 ocg->cg_magic = CG_MAGIC; 138 savednrpos = fs->fs_nrpos; 139 fs->fs_nrpos = 8; 140 break; 141 142 case FS_DYNAMICPOSTBLFMT: 143 newcg->cg_btotoff = 144 &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield); 145 newcg->cg_boff = 146 newcg->cg_btotoff + fs->fs_cpg * sizeof(int32_t); 147 newcg->cg_iusedoff = newcg->cg_boff + 148 fs->fs_cpg * fs->fs_nrpos * sizeof(int16_t); 149 newcg->cg_freeoff = 150 newcg->cg_iusedoff + howmany(fs->fs_ipg, NBBY); 151 inomapsize = newcg->cg_freeoff - newcg->cg_iusedoff; 152 newcg->cg_nextfreeoff = newcg->cg_freeoff + 153 howmany(fs->fs_cpg * fs->fs_spc / NSPF(fs), NBBY); 154 blkmapsize = newcg->cg_nextfreeoff - newcg->cg_freeoff; 155 if (fs->fs_contigsumsize > 0) { 156 newcg->cg_clustersumoff = newcg->cg_nextfreeoff - 157 sizeof(int32_t); 158 newcg->cg_clustersumoff = 159 roundup(newcg->cg_clustersumoff, sizeof(int32_t)); 160 newcg->cg_clusteroff = newcg->cg_clustersumoff + 161 (fs->fs_contigsumsize + 1) * sizeof(int32_t); 162 newcg->cg_nextfreeoff = newcg->cg_clusteroff + 163 howmany(fs->fs_cpg * fs->fs_spc / NSPB(fs), NBBY); 164 } 165 newcg->cg_magic = CG_MAGIC; 166 basesize = &newcg->cg_space[0] - 167 (u_char *)(&newcg->cg_firstfield); 168 sumsize = newcg->cg_iusedoff - newcg->cg_btotoff; 169 mapsize = newcg->cg_nextfreeoff - newcg->cg_iusedoff; 170 break; 171 172 default: 173 inomapsize = blkmapsize = sumsize = 0; /* keep lint happy */ 174 errx(EEXIT, "UNKNOWN ROTATIONAL TABLE FORMAT %d", 175 fs->fs_postblformat); 176 } 177 memset(&idesc[0], 0, sizeof idesc); 178 for (i = 0; i < 3; i++) { 179 idesc[i].id_type = ADDR; 180 if (doinglevel2) 181 idesc[i].id_fix = FIX; 182 } 183 memset(&cstotal, 0, sizeof(struct csum)); 184 j = blknum(fs, fs->fs_size + fs->fs_frag - 1); 185 for (i = fs->fs_size; i < j; i++) 186 setbmap(i); 187 for (c = 0; c < fs->fs_ncg; c++) { 188 getblk(&cgblk, cgtod(fs, c), fs->fs_cgsize); 189 memcpy(cg, cgblk.b_un.b_cg, fs->fs_cgsize); 190 if((doswap && !needswap) || (!doswap && needswap)) 191 swap_cg(cgblk.b_un.b_cg, cg); 192 if (!cg_chkmagic(cg, 0)) 193 pfatal("CG %d: PASS5: BAD MAGIC NUMBER\n", c); 194 if(doswap) 195 cgdirty(); 196 dbase = cgbase(fs, c); 197 dmax = dbase + fs->fs_fpg; 198 if (dmax > fs->fs_size) 199 dmax = fs->fs_size; 200 newcg->cg_time = cg->cg_time; 201 newcg->cg_cgx = c; 202 if (c == fs->fs_ncg - 1) 203 newcg->cg_ncyl = fs->fs_ncyl % fs->fs_cpg; 204 else 205 newcg->cg_ncyl = fs->fs_cpg; 206 newcg->cg_ndblk = dmax - dbase; 207 if (fs->fs_contigsumsize > 0) 208 newcg->cg_nclusterblks = newcg->cg_ndblk / fs->fs_frag; 209 newcg->cg_cs.cs_ndir = 0; 210 newcg->cg_cs.cs_nffree = 0; 211 newcg->cg_cs.cs_nbfree = 0; 212 newcg->cg_cs.cs_nifree = fs->fs_ipg; 213 if (cg->cg_rotor < newcg->cg_ndblk) 214 newcg->cg_rotor = cg->cg_rotor; 215 else 216 newcg->cg_rotor = 0; 217 if (cg->cg_frotor < newcg->cg_ndblk) 218 newcg->cg_frotor = cg->cg_frotor; 219 else 220 newcg->cg_frotor = 0; 221 if (cg->cg_irotor < newcg->cg_niblk) 222 newcg->cg_irotor = cg->cg_irotor; 223 else 224 newcg->cg_irotor = 0; 225 memset(&newcg->cg_frsum[0], 0, sizeof newcg->cg_frsum); 226 memset(&cg_blktot(newcg, 0)[0], 0, 227 (size_t)(sumsize + mapsize)); 228 if (fs->fs_postblformat == FS_42POSTBLFMT) 229 ocg->cg_magic = CG_MAGIC; 230 j = fs->fs_ipg * c; 231 for (i = 0; i < fs->fs_ipg; j++, i++) { 232 switch (statemap[j]) { 233 234 case USTATE: 235 break; 236 237 case DSTATE: 238 case DCLEAR: 239 case DFOUND: 240 newcg->cg_cs.cs_ndir++; 241 /* fall through */ 242 243 case FSTATE: 244 case FCLEAR: 245 newcg->cg_cs.cs_nifree--; 246 setbit(cg_inosused(newcg, 0), i); 247 break; 248 249 default: 250 if (j < ROOTINO) 251 break; 252 errx(EEXIT, "BAD STATE %d FOR INODE I=%ld", 253 statemap[j], (long)j); 254 } 255 } 256 if (c == 0) 257 for (i = 0; i < ROOTINO; i++) { 258 setbit(cg_inosused(newcg, 0), i); 259 newcg->cg_cs.cs_nifree--; 260 } 261 for (i = 0, d = dbase; 262 d < dmax; 263 d += fs->fs_frag, i += fs->fs_frag) { 264 frags = 0; 265 for (j = 0; j < fs->fs_frag; j++) { 266 if (testbmap(d + j)) 267 continue; 268 setbit(cg_blksfree(newcg, 0), i + j); 269 frags++; 270 } 271 if (frags == fs->fs_frag) { 272 newcg->cg_cs.cs_nbfree++; 273 j = cbtocylno(fs, i); 274 cg_blktot(newcg, 0)[j]++; 275 cg_blks(fs, newcg, j, 0)[cbtorpos(fs, i)]++; 276 if (fs->fs_contigsumsize > 0) 277 setbit(cg_clustersfree(newcg, 0), 278 i / fs->fs_frag); 279 } else if (frags > 0) { 280 newcg->cg_cs.cs_nffree += frags; 281 blk = blkmap(fs, cg_blksfree(newcg, 0), i); 282 ffs_fragacct(fs, blk, newcg->cg_frsum, 1, 0); 283 } 284 } 285 if (fs->fs_contigsumsize > 0) { 286 int32_t *sump = cg_clustersum(newcg, 0); 287 u_char *mapp = cg_clustersfree(newcg, 0); 288 int map = *mapp++; 289 int bit = 1; 290 int run = 0; 291 292 for (i = 0; i < newcg->cg_nclusterblks; i++) { 293 if ((map & bit) != 0) { 294 run++; 295 } else if (run != 0) { 296 if (run > fs->fs_contigsumsize) 297 run = fs->fs_contigsumsize; 298 sump[run]++; 299 run = 0; 300 } 301 if ((i & (NBBY - 1)) != (NBBY - 1)) { 302 bit <<= 1; 303 } else { 304 map = *mapp++; 305 bit = 1; 306 } 307 } 308 if (run != 0) { 309 if (run > fs->fs_contigsumsize) 310 run = fs->fs_contigsumsize; 311 sump[run]++; 312 } 313 } 314 cstotal.cs_nffree += newcg->cg_cs.cs_nffree; 315 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree; 316 cstotal.cs_nifree += newcg->cg_cs.cs_nifree; 317 cstotal.cs_ndir += newcg->cg_cs.cs_ndir; 318 cs = &fs->fs_cs(fs, c); 319 if (memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0) { 320 if (dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 321 memmove(cs, &newcg->cg_cs, sizeof *cs); 322 sbdirty(); 323 } else 324 markclean = 0; 325 } 326 if (doinglevel1) { 327 memmove(cg, newcg, (size_t)fs->fs_cgsize); 328 cgdirty(); 329 continue; 330 } 331 if (memcmp(newcg, cg, basesize) != 0 || 332 memcmp(&cg_blktot(newcg, 0)[0], 333 &cg_blktot(cg, 0)[0], sumsize) != 0) { 334 if (dofix(&idesc[2], "SUMMARY INFORMATION BAD")) { 335 memmove(cg, newcg, (size_t)basesize); 336 memmove(&cg_blktot(cg, 0)[0], 337 &cg_blktot(newcg, 0)[0], (size_t)sumsize); 338 cgdirty(); 339 } else 340 markclean = 0; 341 } 342 if (usedsoftdep) { 343 for (i = 0; i < inomapsize; i++) { 344 j = cg_inosused(newcg, 0)[i]; 345 if ((cg_inosused(cg, 0)[i] & j) == j) 346 continue; 347 for (k = 0; k < NBBY; k++) { 348 if ((j & (1 << k)) == 0) 349 continue; 350 if (cg_inosused(cg, 0)[i] & (1 << k)) 351 continue; 352 pwarn("ALLOCATED INODE %ld " 353 "MARKED FREE\n", 354 c * fs->fs_ipg + i * 8 + k); 355 } 356 } 357 for (i = 0; i < blkmapsize; i++) { 358 j = cg_blksfree(cg, 0)[i]; 359 if ((cg_blksfree(newcg, 0)[i] & j) == j) 360 continue; 361 for (k = 0; k < NBBY; k++) { 362 if ((j & (1 << k)) == 0) 363 continue; 364 if (cg_inosused(cg, 0)[i] & (1 << k)) 365 continue; 366 pwarn("ALLOCATED FRAG %ld MARKED FREE", 367 c * fs->fs_fpg + i * 8 + k); 368 } 369 } 370 } 371 if (memcmp(cg_inosused(newcg, 0), cg_inosused(cg, 0), mapsize) 372 != 0 && dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) { 373 memmove(cg_inosused(cg, 0), cg_inosused(newcg, 0), 374 (size_t)mapsize); 375 cgdirty(); 376 } 377 } 378 if (fs->fs_postblformat == FS_42POSTBLFMT) 379 fs->fs_nrpos = savednrpos; 380 if (memcmp(&cstotal, &fs->fs_cstotal, sizeof *cs) != 0) { 381 if(dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 382 memmove(&fs->fs_cstotal, &cstotal, sizeof *cs); 383 fs->fs_ronly = 0; 384 fs->fs_fmod = 0; 385 sbdirty(); 386 } else 387 markclean = 0; 388 } 389 } 390 391 void 392 print_bmap(map, size) 393 u_char *map; 394 u_int32_t size; 395 { 396 int i, j; 397 398 i = 0; 399 while (i < size) { 400 printf("%u: ",i); 401 for (j = 0; j < 16; j++, i++) 402 printf("%2x ", (u_int)map[i] & 0xff); 403 printf("\n"); 404 } 405 } 406