1 /* $OpenBSD: pass5.c,v 1.14 2001/12/01 19:04:41 deraadt Exp $ */ 2 /* $NetBSD: pass5.c,v 1.16 1996/09/27 22:45:18 christos Exp $ */ 3 4 /* 5 * Copyright (c) 1980, 1986, 1993 6 * The Regents of the University of California. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the University of 19 * California, Berkeley and its contributors. 20 * 4. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 */ 36 37 #ifndef lint 38 #if 0 39 static char sccsid[] = "@(#)pass5.c 8.6 (Berkeley) 11/30/94"; 40 #else 41 static char rcsid[] = "$OpenBSD: pass5.c,v 1.14 2001/12/01 19:04:41 deraadt Exp $"; 42 #endif 43 #endif /* not lint */ 44 45 #include <sys/param.h> 46 #include <sys/time.h> 47 #include <sys/lock.h> 48 #include <sys/ucred.h> 49 #include <ufs/ufs/dinode.h> 50 #include <ufs/ffs/fs.h> 51 #include <ufs/ufs/quota.h> 52 #include <ufs/ufs/inode.h> 53 #include <ufs/ffs/ffs_extern.h> 54 #include <stdio.h> 55 #include <string.h> 56 57 #include "fsutil.h" 58 #include "fsck.h" 59 #include "extern.h" 60 61 static int info_cg; 62 static int info_maxcg; 63 64 static int 65 pass5_info(buf, buflen) 66 char *buf; 67 int buflen; 68 { 69 return snprintf(buf, buflen, "phase 5, cg %d/%d", info_cg, info_maxcg); 70 } 71 72 void 73 pass5() 74 { 75 int c, blk, frags, basesize, sumsize, mapsize, savednrpos=0; 76 int inomapsize, blkmapsize; 77 struct fs *fs = &sblock; 78 struct cg *cg = &cgrp; 79 daddr_t dbase, dmax; 80 daddr_t d; 81 long i, j, k; 82 struct csum *cs; 83 struct csum cstotal; 84 struct inodesc idesc[3]; 85 char buf[MAXBSIZE]; 86 struct cg *newcg = (struct cg *)buf; 87 struct ocg *ocg = (struct ocg *)buf; 88 89 statemap[WINO] = USTATE; 90 memset(newcg, 0, (size_t)fs->fs_cgsize); 91 newcg->cg_niblk = fs->fs_ipg; 92 if (cvtlevel >= 3) { 93 if (fs->fs_maxcontig < 2 && fs->fs_contigsumsize > 0) { 94 if (preen) 95 pwarn("DELETING CLUSTERING MAPS\n"); 96 if (preen || reply("DELETE CLUSTERING MAPS")) { 97 fs->fs_contigsumsize = 0; 98 doinglevel1 = 1; 99 sbdirty(); 100 } 101 } 102 if (fs->fs_maxcontig > 1) { 103 char *doit = 0; 104 105 if (fs->fs_contigsumsize < 1) { 106 doit = "CREAT"; 107 } else if (fs->fs_contigsumsize < fs->fs_maxcontig && 108 fs->fs_contigsumsize < FS_MAXCONTIG) { 109 doit = "EXPAND"; 110 } 111 if (doit) { 112 i = fs->fs_contigsumsize; 113 fs->fs_contigsumsize = 114 MIN(fs->fs_maxcontig, FS_MAXCONTIG); 115 if (CGSIZE(fs) > fs->fs_bsize) { 116 pwarn("CANNOT %s CLUSTER MAPS\n", doit); 117 fs->fs_contigsumsize = i; 118 } else if (preen || 119 reply("CREATE CLUSTER MAPS")) { 120 if (preen) 121 pwarn("%sING CLUSTER MAPS\n", 122 doit); 123 fs->fs_cgsize = 124 fragroundup(fs, CGSIZE(fs)); 125 doinglevel1 = 1; 126 sbdirty(); 127 } 128 } 129 } 130 } 131 switch ((int)fs->fs_postblformat) { 132 133 case FS_42POSTBLFMT: 134 basesize = (char *)(&ocg->cg_btot[0]) - 135 (char *)(&ocg->cg_firstfield); 136 sumsize = &ocg->cg_iused[0] - (u_int8_t *)(&ocg->cg_btot[0]); 137 mapsize = &ocg->cg_free[howmany(fs->fs_fpg, NBBY)] - 138 (u_char *)&ocg->cg_iused[0]; 139 blkmapsize = howmany(fs->fs_fpg, NBBY); 140 inomapsize = sizeof(ocg->cg_iused); 141 ocg->cg_magic = CG_MAGIC; 142 savednrpos = fs->fs_nrpos; 143 fs->fs_nrpos = 8; 144 break; 145 146 case FS_DYNAMICPOSTBLFMT: 147 newcg->cg_btotoff = 148 &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield); 149 newcg->cg_boff = 150 newcg->cg_btotoff + fs->fs_cpg * sizeof(int32_t); 151 newcg->cg_iusedoff = newcg->cg_boff + 152 fs->fs_cpg * fs->fs_nrpos * sizeof(int16_t); 153 newcg->cg_freeoff = 154 newcg->cg_iusedoff + howmany(fs->fs_ipg, NBBY); 155 inomapsize = newcg->cg_freeoff - newcg->cg_iusedoff; 156 newcg->cg_nextfreeoff = newcg->cg_freeoff + 157 howmany(fs->fs_cpg * fs->fs_spc / NSPF(fs), NBBY); 158 blkmapsize = newcg->cg_nextfreeoff - newcg->cg_freeoff; 159 if (fs->fs_contigsumsize > 0) { 160 newcg->cg_clustersumoff = newcg->cg_nextfreeoff - 161 sizeof(int32_t); 162 newcg->cg_clustersumoff = 163 roundup(newcg->cg_clustersumoff, sizeof(int32_t)); 164 newcg->cg_clusteroff = newcg->cg_clustersumoff + 165 (fs->fs_contigsumsize + 1) * sizeof(int32_t); 166 newcg->cg_nextfreeoff = newcg->cg_clusteroff + 167 howmany(fs->fs_cpg * fs->fs_spc / NSPB(fs), NBBY); 168 } 169 newcg->cg_magic = CG_MAGIC; 170 basesize = &newcg->cg_space[0] - 171 (u_char *)(&newcg->cg_firstfield); 172 sumsize = newcg->cg_iusedoff - newcg->cg_btotoff; 173 mapsize = newcg->cg_nextfreeoff - newcg->cg_iusedoff; 174 break; 175 176 default: 177 inomapsize = blkmapsize = sumsize = 0; 178 errexit("UNKNOWN ROTATIONAL TABLE FORMAT %d\n", 179 fs->fs_postblformat); 180 } 181 memset(&idesc[0], 0, sizeof idesc); 182 for (i = 0; i < 3; i++) { 183 idesc[i].id_type = ADDR; 184 if (doinglevel2) 185 idesc[i].id_fix = FIX; 186 } 187 memset(&cstotal, 0, sizeof(struct csum)); 188 j = blknum(fs, fs->fs_size + fs->fs_frag - 1); 189 for (i = fs->fs_size; i < j; i++) 190 setbmap(i); 191 info_cg = 0; 192 info_maxcg = fs->fs_ncg; 193 info_fn = pass5_info; 194 for (c = 0; c < fs->fs_ncg; c++) { 195 info_cg = c; 196 getblk(&cgblk, cgtod(fs, c), fs->fs_cgsize); 197 if (!cg_chkmagic(cg)) 198 pfatal("CG %d: BAD MAGIC NUMBER\n", c); 199 dbase = cgbase(fs, c); 200 dmax = dbase + fs->fs_fpg; 201 if (dmax > fs->fs_size) 202 dmax = fs->fs_size; 203 newcg->cg_time = cg->cg_time; 204 newcg->cg_cgx = c; 205 if (c == fs->fs_ncg - 1) 206 newcg->cg_ncyl = fs->fs_ncyl % fs->fs_cpg; 207 else 208 newcg->cg_ncyl = fs->fs_cpg; 209 newcg->cg_ndblk = dmax - dbase; 210 if (fs->fs_contigsumsize > 0) 211 newcg->cg_nclusterblks = newcg->cg_ndblk / fs->fs_frag; 212 newcg->cg_cs.cs_ndir = 0; 213 newcg->cg_cs.cs_nffree = 0; 214 newcg->cg_cs.cs_nbfree = 0; 215 newcg->cg_cs.cs_nifree = fs->fs_ipg; 216 if (cg->cg_rotor < newcg->cg_ndblk) 217 newcg->cg_rotor = cg->cg_rotor; 218 else 219 newcg->cg_rotor = 0; 220 if (cg->cg_frotor < newcg->cg_ndblk) 221 newcg->cg_frotor = cg->cg_frotor; 222 else 223 newcg->cg_frotor = 0; 224 if (cg->cg_irotor < newcg->cg_niblk) 225 newcg->cg_irotor = cg->cg_irotor; 226 else 227 newcg->cg_irotor = 0; 228 memset(&newcg->cg_frsum[0], 0, sizeof newcg->cg_frsum); 229 memset(&cg_blktot(newcg)[0], 0, 230 (size_t)(sumsize + mapsize)); 231 if (fs->fs_postblformat == FS_42POSTBLFMT) 232 ocg->cg_magic = CG_MAGIC; 233 j = fs->fs_ipg * c; 234 for (i = 0; i < fs->fs_ipg; j++, i++) { 235 switch (statemap[j]) { 236 237 case USTATE: 238 break; 239 240 case DSTATE: 241 case DCLEAR: 242 case DFOUND: 243 newcg->cg_cs.cs_ndir++; 244 /* fall through */ 245 246 case FSTATE: 247 case FCLEAR: 248 newcg->cg_cs.cs_nifree--; 249 setbit(cg_inosused(newcg), i); 250 break; 251 252 default: 253 if (j < ROOTINO) 254 break; 255 errexit("BAD STATE %d FOR INODE I=%ld", 256 statemap[j], j); 257 } 258 } 259 if (c == 0) 260 for (i = 0; i < ROOTINO; i++) { 261 setbit(cg_inosused(newcg), i); 262 newcg->cg_cs.cs_nifree--; 263 } 264 for (i = 0, d = dbase; 265 d < dmax; 266 d += fs->fs_frag, i += fs->fs_frag) { 267 frags = 0; 268 for (j = 0; j < fs->fs_frag; j++) { 269 if (testbmap(d + j)) 270 continue; 271 setbit(cg_blksfree(newcg), i + j); 272 frags++; 273 } 274 if (frags == fs->fs_frag) { 275 newcg->cg_cs.cs_nbfree++; 276 j = cbtocylno(fs, i); 277 cg_blktot(newcg)[j]++; 278 cg_blks(fs, newcg, j)[cbtorpos(fs, i)]++; 279 if (fs->fs_contigsumsize > 0) 280 setbit(cg_clustersfree(newcg), 281 i / fs->fs_frag); 282 } else if (frags > 0) { 283 newcg->cg_cs.cs_nffree += frags; 284 blk = blkmap(fs, cg_blksfree(newcg), i); 285 ffs_fragacct(fs, blk, newcg->cg_frsum, 1); 286 } 287 } 288 if (fs->fs_contigsumsize > 0) { 289 int32_t *sump = cg_clustersum(newcg); 290 u_char *mapp = cg_clustersfree(newcg); 291 int map = *mapp++; 292 int bit = 1; 293 int run = 0; 294 295 for (i = 0; i < newcg->cg_nclusterblks; i++) { 296 if ((map & bit) != 0) { 297 run++; 298 } else if (run != 0) { 299 if (run > fs->fs_contigsumsize) 300 run = fs->fs_contigsumsize; 301 sump[run]++; 302 run = 0; 303 } 304 if ((i & (NBBY - 1)) != (NBBY - 1)) { 305 bit <<= 1; 306 } else { 307 map = *mapp++; 308 bit = 1; 309 } 310 } 311 if (run != 0) { 312 if (run > fs->fs_contigsumsize) 313 run = fs->fs_contigsumsize; 314 sump[run]++; 315 } 316 } 317 cstotal.cs_nffree += newcg->cg_cs.cs_nffree; 318 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree; 319 cstotal.cs_nifree += newcg->cg_cs.cs_nifree; 320 cstotal.cs_ndir += newcg->cg_cs.cs_ndir; 321 cs = &fs->fs_cs(fs, c); 322 if (memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0 && 323 dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 324 memcpy(cs, &newcg->cg_cs, sizeof *cs); 325 sbdirty(); 326 } 327 if (doinglevel1) { 328 memcpy(cg, newcg, (size_t)fs->fs_cgsize); 329 cgdirty(); 330 continue; 331 } 332 if ((memcmp(newcg, cg, basesize) != 0 || 333 memcmp(&cg_blktot(newcg)[0], 334 &cg_blktot(cg)[0], sumsize) != 0) && 335 dofix(&idesc[2], "SUMMARY INFORMATION BAD")) { 336 memcpy(cg, newcg, (size_t)basesize); 337 memcpy(&cg_blktot(cg)[0], 338 &cg_blktot(newcg)[0], (size_t)sumsize); 339 cgdirty(); 340 } 341 if (usedsoftdep) { 342 for (i = 0; i < inomapsize; i++) { 343 j = cg_inosused(newcg)[i]; 344 if ((cg_inosused(cg)[i] & j) == j) 345 continue; 346 for (k = 0; k < NBBY; k++) { 347 if ((j & (1 << k)) == 0) 348 continue; 349 if (cg_inosused(cg)[i] & (1 << k)) 350 continue; 351 pwarn("ALLOCATED INODE %ld MARKED FREE\n", 352 c * fs->fs_ipg + i * 8 + k); 353 } 354 } 355 for (i = 0; i < blkmapsize; i++) { 356 j = cg_blksfree(cg)[i]; 357 if ((cg_blksfree(newcg)[i] & j) == j) 358 continue; 359 for (k = 0; k < NBBY; k++) { 360 if ((j & (1 << k)) == 0) 361 continue; 362 if (cg_inosused(cg)[i] & (1 << k)) 363 continue; 364 pwarn("ALLOCATED FRAG %ld MARKED FREE\n", 365 c * fs->fs_fpg + i * 8 + k); 366 } 367 } 368 } 369 if (memcmp(cg_inosused(newcg), cg_inosused(cg), 370 mapsize) != 0 && 371 dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) { 372 memmove(cg_inosused(cg), cg_inosused(newcg), 373 (size_t)mapsize); 374 cgdirty(); 375 } 376 } 377 info_fn = NULL; 378 if (fs->fs_postblformat == FS_42POSTBLFMT) 379 fs->fs_nrpos = savednrpos; 380 if (memcmp(&cstotal, &fs->fs_cstotal, sizeof *cs) != 0 381 && dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 382 memcpy(&fs->fs_cstotal, &cstotal, sizeof *cs); 383 fs->fs_ronly = 0; 384 fs->fs_fmod = 0; 385 sbdirty(); 386 } 387 } 388