pass5.c revision 95897
1/* 2 * Copyright (c) 1980, 1986, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 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. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34#ifndef lint 35#if 0 36static const char sccsid[] = "@(#)pass5.c 8.9 (Berkeley) 4/28/95"; 37#endif 38static const char rcsid[] = 39 "$FreeBSD: head/sbin/fsck_ffs/pass5.c 95897 2002-05-02 01:03:06Z mckusick $"; 40#endif /* not lint */ 41 42#include <sys/param.h> 43#include <sys/sysctl.h> 44 45#include <ufs/ufs/dinode.h> 46#include <ufs/ffs/fs.h> 47 48#include <err.h> 49#include <string.h> 50 51#include "fsck.h" 52 53static void check_maps(u_char *, u_char *, int, int, char *, int *, int, int); 54 55void 56pass5(void) 57{ 58 int c, blk, frags, basesize, sumsize, mapsize, savednrpos = 0; 59 int inomapsize, blkmapsize; 60 struct fs *fs = &sblock; 61 struct cg *cg = &cgrp; 62 ufs_daddr_t dbase, dmax, d; 63 int i, j, excessdirs; 64 struct csum *cs; 65 struct csum cstotal; 66 struct inodesc idesc[3]; 67 char buf[MAXBSIZE]; 68 struct cg *newcg = (struct cg *)buf; 69 struct ocg *ocg = (struct ocg *)buf; 70 71 inoinfo(WINO)->ino_state = USTATE; 72 memset(newcg, 0, (size_t)fs->fs_cgsize); 73 newcg->cg_niblk = fs->fs_ipg; 74 if (cvtlevel >= 3) { 75 if (fs->fs_maxcontig < 2 && fs->fs_contigsumsize > 0) { 76 if (preen) 77 pwarn("DELETING CLUSTERING MAPS\n"); 78 if (preen || reply("DELETE CLUSTERING MAPS")) { 79 fs->fs_contigsumsize = 0; 80 doinglevel1 = 1; 81 sbdirty(); 82 } 83 } 84 if (fs->fs_maxcontig > 1) { 85 char *doit = 0; 86 87 if (fs->fs_contigsumsize < 1) { 88 doit = "CREAT"; 89 } else if (fs->fs_contigsumsize < fs->fs_maxcontig && 90 fs->fs_contigsumsize < FS_MAXCONTIG) { 91 doit = "EXPAND"; 92 } 93 if (doit) { 94 i = fs->fs_contigsumsize; 95 fs->fs_contigsumsize = 96 MIN(fs->fs_maxcontig, FS_MAXCONTIG); 97 if (CGSIZE(fs) > (u_int)fs->fs_bsize) { 98 pwarn("CANNOT %s CLUSTER MAPS\n", doit); 99 fs->fs_contigsumsize = i; 100 } else if (preen || 101 reply("CREATE CLUSTER MAPS")) { 102 if (preen) 103 pwarn("%sING CLUSTER MAPS\n", 104 doit); 105 fs->fs_cgsize = 106 fragroundup(fs, CGSIZE(fs)); 107 doinglevel1 = 1; 108 sbdirty(); 109 } 110 } 111 } 112 } 113 switch ((int)fs->fs_postblformat) { 114 115 case FS_42POSTBLFMT: 116 basesize = (char *)(&ocg->cg_btot[0]) - 117 (char *)(&ocg->cg_firstfield); 118 sumsize = &ocg->cg_iused[0] - (u_int8_t *)(&ocg->cg_btot[0]); 119 mapsize = &ocg->cg_free[howmany(fs->fs_fpg, NBBY)] - 120 (u_char *)&ocg->cg_iused[0]; 121 blkmapsize = howmany(fs->fs_fpg, NBBY); 122 inomapsize = &ocg->cg_free[0] - (u_char *)&ocg->cg_iused[0]; 123 ocg->cg_magic = CG_MAGIC; 124 savednrpos = fs->fs_nrpos; 125 fs->fs_nrpos = 8; 126 break; 127 128 case FS_DYNAMICPOSTBLFMT: 129 newcg->cg_btotoff = 130 &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield); 131 newcg->cg_boff = 132 newcg->cg_btotoff + fs->fs_cpg * sizeof(int32_t); 133 newcg->cg_iusedoff = newcg->cg_boff + 134 fs->fs_cpg * fs->fs_nrpos * sizeof(u_int16_t); 135 newcg->cg_freeoff = 136 newcg->cg_iusedoff + howmany(fs->fs_ipg, NBBY); 137 inomapsize = newcg->cg_freeoff - newcg->cg_iusedoff; 138 newcg->cg_nextfreeoff = newcg->cg_freeoff + 139 howmany(fs->fs_cpg * fs->fs_spc / NSPF(fs), NBBY); 140 blkmapsize = newcg->cg_nextfreeoff - newcg->cg_freeoff; 141 if (fs->fs_contigsumsize > 0) { 142 newcg->cg_clustersumoff = newcg->cg_nextfreeoff - 143 sizeof(u_int32_t); 144 newcg->cg_clustersumoff = 145 roundup(newcg->cg_clustersumoff, sizeof(u_int32_t)); 146 newcg->cg_clusteroff = newcg->cg_clustersumoff + 147 (fs->fs_contigsumsize + 1) * sizeof(u_int32_t); 148 newcg->cg_nextfreeoff = newcg->cg_clusteroff + 149 howmany(fs->fs_cpg * fs->fs_spc / NSPB(fs), NBBY); 150 } 151 newcg->cg_magic = CG_MAGIC; 152 basesize = &newcg->cg_space[0] - 153 (u_char *)(&newcg->cg_firstfield); 154 sumsize = newcg->cg_iusedoff - newcg->cg_btotoff; 155 mapsize = newcg->cg_nextfreeoff - newcg->cg_iusedoff; 156 break; 157 158 default: 159 inomapsize = blkmapsize = sumsize = 0; /* keep lint happy */ 160 errx(EEXIT, "UNKNOWN ROTATIONAL TABLE FORMAT %d", 161 fs->fs_postblformat); 162 } 163 memset(&idesc[0], 0, sizeof idesc); 164 for (i = 0; i < 3; i++) { 165 idesc[i].id_type = ADDR; 166 if (doinglevel2) 167 idesc[i].id_fix = FIX; 168 } 169 memset(&cstotal, 0, sizeof(struct csum)); 170 j = blknum(fs, fs->fs_size + fs->fs_frag - 1); 171 for (i = fs->fs_size; i < j; i++) 172 setbmap(i); 173 for (c = 0; c < fs->fs_ncg; c++) { 174 if (got_siginfo) { 175 printf("%s: phase 5: cyl group %d of %d (%d%%)\n", 176 cdevname, c, sblock.fs_ncg, 177 c * 100 / sblock.fs_ncg); 178 got_siginfo = 0; 179 } 180 getblk(&cgblk, cgtod(fs, c), fs->fs_cgsize); 181 if (!cg_chkmagic(cg)) 182 pfatal("CG %d: BAD MAGIC NUMBER\n", c); 183 dbase = cgbase(fs, c); 184 dmax = dbase + fs->fs_fpg; 185 if (dmax > fs->fs_size) 186 dmax = fs->fs_size; 187 newcg->cg_time = cg->cg_time; 188 newcg->cg_cgx = c; 189 if (c == fs->fs_ncg - 1 && fs->fs_ncyl % fs->fs_cpg > 0) 190 newcg->cg_ncyl = fs->fs_ncyl % fs->fs_cpg; 191 else 192 newcg->cg_ncyl = fs->fs_cpg; 193 newcg->cg_ndblk = dmax - dbase; 194 if (fs->fs_contigsumsize > 0) 195 newcg->cg_nclusterblks = newcg->cg_ndblk / fs->fs_frag; 196 newcg->cg_cs.cs_ndir = 0; 197 newcg->cg_cs.cs_nffree = 0; 198 newcg->cg_cs.cs_nbfree = 0; 199 newcg->cg_cs.cs_nifree = fs->fs_ipg; 200 if (cg->cg_rotor < newcg->cg_ndblk) 201 newcg->cg_rotor = cg->cg_rotor; 202 else 203 newcg->cg_rotor = 0; 204 if (cg->cg_frotor < newcg->cg_ndblk) 205 newcg->cg_frotor = cg->cg_frotor; 206 else 207 newcg->cg_frotor = 0; 208 if (cg->cg_irotor < fs->fs_ipg) 209 newcg->cg_irotor = cg->cg_irotor; 210 else 211 newcg->cg_irotor = 0; 212 memset(&newcg->cg_frsum[0], 0, sizeof newcg->cg_frsum); 213 memset(&cg_blktot(newcg)[0], 0, 214 (size_t)(sumsize + mapsize)); 215 if (fs->fs_postblformat == FS_42POSTBLFMT) 216 ocg->cg_magic = CG_MAGIC; 217 j = fs->fs_ipg * c; 218 for (i = 0; i < inostathead[c].il_numalloced; j++, i++) { 219 switch (inoinfo(j)->ino_state) { 220 221 case USTATE: 222 break; 223 224 case DSTATE: 225 case DCLEAR: 226 case DFOUND: 227 newcg->cg_cs.cs_ndir++; 228 /* fall through */ 229 230 case FSTATE: 231 case FCLEAR: 232 newcg->cg_cs.cs_nifree--; 233 setbit(cg_inosused(newcg), i); 234 break; 235 236 default: 237 if (j < (int)ROOTINO) 238 break; 239 errx(EEXIT, "BAD STATE %d FOR INODE I=%d", 240 inoinfo(j)->ino_state, j); 241 } 242 } 243 if (c == 0) 244 for (i = 0; i < (int)ROOTINO; i++) { 245 setbit(cg_inosused(newcg), i); 246 newcg->cg_cs.cs_nifree--; 247 } 248 for (i = 0, d = dbase; 249 d < dmax; 250 d += fs->fs_frag, i += fs->fs_frag) { 251 frags = 0; 252 for (j = 0; j < fs->fs_frag; j++) { 253 if (testbmap(d + j)) 254 continue; 255 setbit(cg_blksfree(newcg), i + j); 256 frags++; 257 } 258 if (frags == fs->fs_frag) { 259 newcg->cg_cs.cs_nbfree++; 260 j = cbtocylno(fs, i); 261 cg_blktot(newcg)[j]++; 262 cg_blks(fs, newcg, j)[cbtorpos(fs, i)]++; 263 if (fs->fs_contigsumsize > 0) 264 setbit(cg_clustersfree(newcg), 265 i / fs->fs_frag); 266 } else if (frags > 0) { 267 newcg->cg_cs.cs_nffree += frags; 268 blk = blkmap(fs, cg_blksfree(newcg), i); 269 ffs_fragacct(fs, blk, newcg->cg_frsum, 1); 270 } 271 } 272 if (fs->fs_contigsumsize > 0) { 273 int32_t *sump = cg_clustersum(newcg); 274 u_char *mapp = cg_clustersfree(newcg); 275 int map = *mapp++; 276 int bit = 1; 277 int run = 0; 278 279 for (i = 0; i < newcg->cg_nclusterblks; i++) { 280 if ((map & bit) != 0) { 281 run++; 282 } else if (run != 0) { 283 if (run > fs->fs_contigsumsize) 284 run = fs->fs_contigsumsize; 285 sump[run]++; 286 run = 0; 287 } 288 if ((i & (NBBY - 1)) != (NBBY - 1)) { 289 bit <<= 1; 290 } else { 291 map = *mapp++; 292 bit = 1; 293 } 294 } 295 if (run != 0) { 296 if (run > fs->fs_contigsumsize) 297 run = fs->fs_contigsumsize; 298 sump[run]++; 299 } 300 } 301 cstotal.cs_nffree += newcg->cg_cs.cs_nffree; 302 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree; 303 cstotal.cs_nifree += newcg->cg_cs.cs_nifree; 304 cstotal.cs_ndir += newcg->cg_cs.cs_ndir; 305 cs = &fs->fs_cs(fs, c); 306 if (cursnapshot == 0 && 307 memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0 && 308 dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 309 memmove(cs, &newcg->cg_cs, sizeof *cs); 310 sbdirty(); 311 } 312 if (doinglevel1) { 313 memmove(cg, newcg, (size_t)fs->fs_cgsize); 314 cgdirty(); 315 continue; 316 } 317 if (cursnapshot == 0 && 318 (memcmp(newcg, cg, basesize) != 0 || 319 memcmp(&cg_blktot(newcg)[0], 320 &cg_blktot(cg)[0], sumsize) != 0) && 321 dofix(&idesc[2], "SUMMARY INFORMATION BAD")) { 322 memmove(cg, newcg, (size_t)basesize); 323 memmove(&cg_blktot(cg)[0], 324 &cg_blktot(newcg)[0], (size_t)sumsize); 325 cgdirty(); 326 } 327 if (bkgrdflag != 0 || usedsoftdep || debug) { 328 excessdirs = cg->cg_cs.cs_ndir - newcg->cg_cs.cs_ndir; 329 if (excessdirs < 0) { 330 pfatal("LOST %d DIRECTORIES\n", -excessdirs); 331 excessdirs = 0; 332 } 333 if (excessdirs > 0) 334 check_maps(cg_inosused(newcg), cg_inosused(cg), 335 inomapsize, cg->cg_cgx * fs->fs_ipg, "DIR", 336 freedirs, 0, excessdirs); 337 check_maps(cg_inosused(newcg), cg_inosused(cg), 338 inomapsize, cg->cg_cgx * fs->fs_ipg, "FILE", 339 freefiles, excessdirs, fs->fs_ipg); 340 check_maps(cg_blksfree(cg), cg_blksfree(newcg), 341 blkmapsize, cg->cg_cgx * fs->fs_fpg, "FRAG", 342 freeblks, 0, fs->fs_fpg); 343 } 344 if (cursnapshot == 0 && 345 memcmp(cg_inosused(newcg), cg_inosused(cg), mapsize) != 0 && 346 dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) { 347 memmove(cg_inosused(cg), cg_inosused(newcg), 348 (size_t)mapsize); 349 cgdirty(); 350 } 351 } 352 if (fs->fs_postblformat == FS_42POSTBLFMT) 353 fs->fs_nrpos = savednrpos; 354 if (cursnapshot == 0 && 355 memcmp(&cstotal, &fs->fs_cstotal, sizeof *cs) != 0 356 && dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 357 memmove(&fs->fs_cstotal, &cstotal, sizeof *cs); 358 fs->fs_ronly = 0; 359 fs->fs_fmod = 0; 360 sbdirty(); 361 } 362} 363 364static void 365check_maps( 366 u_char *map1, /* map of claimed allocations */ 367 u_char *map2, /* map of determined allocations */ 368 int mapsize, /* size of above two maps */ 369 int startvalue, /* resource value for first element in map */ 370 char *name, /* name of resource found in maps */ 371 int *opcode, /* sysctl opcode to free resource */ 372 int skip, /* number of entries to skip before starting to free */ 373 int limit) /* limit on number of entries to free */ 374{ 375# define BUFSIZE 16 376 char buf[BUFSIZE]; 377 long i, j, k, l, m, n, size; 378 int astart, aend, ustart, uend; 379 void (*msg)(const char *fmt, ...); 380 381 if (bkgrdflag) 382 msg = pfatal; 383 else 384 msg = pwarn; 385 astart = ustart = aend = uend = -1; 386 for (i = 0; i < mapsize; i++) { 387 j = *map1++; 388 k = *map2++; 389 if (j == k) 390 continue; 391 for (m = 0, l = 1; m < NBBY; m++, l <<= 1) { 392 if ((j & l) == (k & l)) 393 continue; 394 n = startvalue + i * NBBY + m; 395 if ((j & l) != 0) { 396 if (astart == -1) { 397 astart = aend = n; 398 continue; 399 } 400 if (aend + 1 == n) { 401 aend = n; 402 continue; 403 } 404 if (astart == aend) 405 (*msg)("ALLOCATED %s %d MARKED FREE\n", 406 name, astart); 407 else 408 (*msg)("%s %sS %d-%d MARKED FREE\n", 409 "ALLOCATED", name, astart, aend); 410 astart = aend = n; 411 } else { 412 if (ustart == -1) { 413 ustart = uend = n; 414 continue; 415 } 416 if (uend + 1 == n) { 417 uend = n; 418 continue; 419 } 420 size = uend - ustart + 1; 421 if (size <= skip) { 422 skip -= size; 423 ustart = uend = n; 424 continue; 425 } 426 if (skip > 0) { 427 ustart += skip; 428 size -= skip; 429 skip = 0; 430 } 431 if (size > limit) 432 size = limit; 433 if (debug && size == 1) 434 pwarn("%s %s %d MARKED USED\n", 435 "UNALLOCATED", name, ustart); 436 else if (debug) 437 pwarn("%s %sS %d-%ld MARKED USED\n", 438 "UNALLOCATED", name, ustart, 439 ustart + size - 1); 440 if (bkgrdflag != 0) { 441 cmd.value = ustart; 442 cmd.size = size; 443 if (sysctl(opcode, MIBSIZE, 0, 0, 444 &cmd, sizeof cmd) == -1) { 445 snprintf(buf, BUFSIZE, 446 "FREE %s", name); 447 rwerror(buf, cmd.value); 448 } 449 } 450 limit -= size; 451 if (limit <= 0) 452 return; 453 ustart = uend = n; 454 } 455 } 456 } 457 if (astart != -1) { 458 if (astart == aend) 459 (*msg)("ALLOCATED %s %d MARKED FREE\n", name, astart); 460 else 461 (*msg)("ALLOCATED %sS %d-%d MARKED FREE\n", 462 name, astart, aend); 463 } 464 if (ustart != -1) { 465 size = uend - ustart + 1; 466 if (size <= skip) 467 return; 468 if (skip > 0) { 469 ustart += skip; 470 size -= skip; 471 } 472 if (size > limit) 473 size = limit; 474 if (debug) { 475 if (size == 1) 476 pwarn("UNALLOCATED %s %d MARKED USED\n", 477 name, ustart); 478 else 479 pwarn("UNALLOCATED %sS %d-%ld MARKED USED\n", 480 name, ustart, ustart + size - 1); 481 } 482 if (bkgrdflag != 0) { 483 cmd.value = ustart; 484 cmd.size = size; 485 if (sysctl(opcode, MIBSIZE, 0, 0, &cmd, 486 sizeof cmd) == -1) { 487 snprintf(buf, BUFSIZE, "FREE %s", name); 488 rwerror(buf, cmd.value); 489 } 490 } 491 } 492} 493