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 * 4. 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. 16 * 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 27 * SUCH DAMAGE. 28 */ 29 30 #if 0 31 #ifndef lint 32 static const char sccsid[] = "@(#)pass5.c 8.9 (Berkeley) 4/28/95"; 33 #endif /* not lint */ 34 #endif 35 #include <sys/cdefs.h> 36 __FBSDID("$FreeBSD$"); 37 38 #include <sys/param.h> 39 #include <sys/sysctl.h> 40 41 #include <ufs/ufs/dinode.h> 42 #include <ufs/ffs/fs.h> 43 44 #include <err.h> 45 #include <inttypes.h> 46 #include <limits.h> 47 #include <string.h> 48 #include <libufs.h> 49 50 #include "fsck.h" 51 52 static void check_maps(u_char *, u_char *, int, ufs2_daddr_t, const char *, int *, int, int); 53 54 static void clear_blocks(ufs2_daddr_t start, ufs2_daddr_t end); 55 56 void 57 pass5(void) 58 { 59 int c, i, j, blk, frags, basesize, mapsize; 60 int inomapsize, blkmapsize; 61 struct fs *fs = &sblock; 62 struct cg *cg = &cgrp; 63 ufs2_daddr_t d, dbase, dmax, start; 64 int excessdirs, rewritecg = 0; 65 struct csum *cs; 66 struct csum_total cstotal; 67 struct inodesc idesc[3]; 68 char buf[MAXBSIZE]; 69 struct cg *newcg = (struct cg *)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 rewritecg = 1; 81 sbdirty(); 82 } 83 } 84 if (fs->fs_maxcontig > 1) { 85 const 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 rewritecg = 1; 108 sbdirty(); 109 } 110 } 111 } 112 } 113 basesize = &newcg->cg_space[0] - (u_char *)(&newcg->cg_firstfield); 114 if (sblock.fs_magic == FS_UFS2_MAGIC) { 115 newcg->cg_iusedoff = basesize; 116 } else { 117 /* 118 * We reserve the space for the old rotation summary 119 * tables for the benefit of old kernels, but do not 120 * maintain them in modern kernels. In time, they can 121 * go away. 122 */ 123 newcg->cg_old_btotoff = basesize; 124 newcg->cg_old_boff = newcg->cg_old_btotoff + 125 fs->fs_old_cpg * sizeof(int32_t); 126 newcg->cg_iusedoff = newcg->cg_old_boff + 127 fs->fs_old_cpg * fs->fs_old_nrpos * sizeof(u_int16_t); 128 memset(&newcg->cg_space[0], 0, newcg->cg_iusedoff - basesize); 129 } 130 inomapsize = howmany(fs->fs_ipg, CHAR_BIT); 131 newcg->cg_freeoff = newcg->cg_iusedoff + inomapsize; 132 blkmapsize = howmany(fs->fs_fpg, CHAR_BIT); 133 newcg->cg_nextfreeoff = newcg->cg_freeoff + blkmapsize; 134 if (fs->fs_contigsumsize > 0) { 135 newcg->cg_clustersumoff = newcg->cg_nextfreeoff - 136 sizeof(u_int32_t); 137 newcg->cg_clustersumoff = 138 roundup(newcg->cg_clustersumoff, sizeof(u_int32_t)); 139 newcg->cg_clusteroff = newcg->cg_clustersumoff + 140 (fs->fs_contigsumsize + 1) * sizeof(u_int32_t); 141 newcg->cg_nextfreeoff = newcg->cg_clusteroff + 142 howmany(fragstoblks(fs, fs->fs_fpg), CHAR_BIT); 143 } 144 newcg->cg_magic = CG_MAGIC; 145 mapsize = newcg->cg_nextfreeoff - newcg->cg_iusedoff; 146 memset(&idesc[0], 0, sizeof idesc); 147 for (i = 0; i < 3; i++) 148 idesc[i].id_type = ADDR; 149 memset(&cstotal, 0, sizeof(struct csum_total)); 150 dmax = blknum(fs, fs->fs_size + fs->fs_frag - 1); 151 for (d = fs->fs_size; d < dmax; d++) 152 setbmap(d); 153 for (c = 0; c < fs->fs_ncg; c++) { 154 if (got_siginfo) { 155 printf("%s: phase 5: cyl group %d of %d (%d%%)\n", 156 cdevname, c, sblock.fs_ncg, 157 c * 100 / sblock.fs_ncg); 158 got_siginfo = 0; 159 } 160 if (got_sigalarm) { 161 setproctitle("%s p5 %d%%", cdevname, 162 c * 100 / sblock.fs_ncg); 163 got_sigalarm = 0; 164 } 165 getblk(&cgblk, cgtod(fs, c), fs->fs_cgsize); 166 if (!cg_chkmagic(cg)) 167 pfatal("CG %d: BAD MAGIC NUMBER\n", c); 168 newcg->cg_time = cg->cg_time; 169 newcg->cg_old_time = cg->cg_old_time; 170 newcg->cg_unrefs = cg->cg_unrefs; 171 newcg->cg_cgx = c; 172 dbase = cgbase(fs, c); 173 dmax = dbase + fs->fs_fpg; 174 if (dmax > fs->fs_size) 175 dmax = fs->fs_size; 176 newcg->cg_ndblk = dmax - dbase; 177 if (fs->fs_magic == FS_UFS1_MAGIC) { 178 if (c == fs->fs_ncg - 1) 179 newcg->cg_old_ncyl = howmany(newcg->cg_ndblk, 180 fs->fs_fpg / fs->fs_old_cpg); 181 else 182 newcg->cg_old_ncyl = fs->fs_old_cpg; 183 newcg->cg_old_niblk = fs->fs_ipg; 184 newcg->cg_niblk = 0; 185 } 186 if (fs->fs_contigsumsize > 0) 187 newcg->cg_nclusterblks = newcg->cg_ndblk / fs->fs_frag; 188 newcg->cg_cs.cs_ndir = 0; 189 newcg->cg_cs.cs_nffree = 0; 190 newcg->cg_cs.cs_nbfree = 0; 191 newcg->cg_cs.cs_nifree = fs->fs_ipg; 192 if (cg->cg_rotor >= 0 && cg->cg_rotor < newcg->cg_ndblk) 193 newcg->cg_rotor = cg->cg_rotor; 194 else 195 newcg->cg_rotor = 0; 196 if (cg->cg_frotor >= 0 && cg->cg_frotor < newcg->cg_ndblk) 197 newcg->cg_frotor = cg->cg_frotor; 198 else 199 newcg->cg_frotor = 0; 200 if (cg->cg_irotor >= 0 && cg->cg_irotor < fs->fs_ipg) 201 newcg->cg_irotor = cg->cg_irotor; 202 else 203 newcg->cg_irotor = 0; 204 if (fs->fs_magic == FS_UFS1_MAGIC) { 205 newcg->cg_initediblk = 0; 206 } else { 207 if ((unsigned)cg->cg_initediblk > fs->fs_ipg) 208 newcg->cg_initediblk = fs->fs_ipg; 209 else 210 newcg->cg_initediblk = cg->cg_initediblk; 211 } 212 memset(&newcg->cg_frsum[0], 0, sizeof newcg->cg_frsum); 213 memset(cg_inosused(newcg), 0, (size_t)(mapsize)); 214 j = fs->fs_ipg * c; 215 for (i = 0; i < inostathead[c].il_numalloced; j++, i++) { 216 switch (inoinfo(j)->ino_state) { 217 218 case USTATE: 219 break; 220 221 case DSTATE: 222 case DCLEAR: 223 case DFOUND: 224 case DZLINK: 225 newcg->cg_cs.cs_ndir++; 226 /* FALLTHROUGH */ 227 228 case FSTATE: 229 case FCLEAR: 230 case FZLINK: 231 newcg->cg_cs.cs_nifree--; 232 setbit(cg_inosused(newcg), i); 233 break; 234 235 default: 236 if (j < (int)ROOTINO) 237 break; 238 errx(EEXIT, "BAD STATE %d FOR INODE I=%d", 239 inoinfo(j)->ino_state, j); 240 } 241 } 242 if (c == 0) 243 for (i = 0; i < (int)ROOTINO; i++) { 244 setbit(cg_inosused(newcg), i); 245 newcg->cg_cs.cs_nifree--; 246 } 247 start = -1; 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 if (Eflag && start != -1) { 255 clear_blocks(start, d + j - 1); 256 start = -1; 257 } 258 continue; 259 } 260 if (start == -1) 261 start = d + j; 262 setbit(cg_blksfree(newcg), i + j); 263 frags++; 264 } 265 if (frags == fs->fs_frag) { 266 newcg->cg_cs.cs_nbfree++; 267 if (fs->fs_contigsumsize > 0) 268 setbit(cg_clustersfree(newcg), 269 i / fs->fs_frag); 270 } else if (frags > 0) { 271 newcg->cg_cs.cs_nffree += frags; 272 blk = blkmap(fs, cg_blksfree(newcg), i); 273 ffs_fragacct(fs, blk, newcg->cg_frsum, 1); 274 } 275 } 276 if (Eflag && start != -1) 277 clear_blocks(start, d - 1); 278 if (fs->fs_contigsumsize > 0) { 279 int32_t *sump = cg_clustersum(newcg); 280 u_char *mapp = cg_clustersfree(newcg); 281 int map = *mapp++; 282 int bit = 1; 283 int run = 0; 284 285 for (i = 0; i < newcg->cg_nclusterblks; i++) { 286 if ((map & bit) != 0) { 287 run++; 288 } else if (run != 0) { 289 if (run > fs->fs_contigsumsize) 290 run = fs->fs_contigsumsize; 291 sump[run]++; 292 run = 0; 293 } 294 if ((i & (CHAR_BIT - 1)) != (CHAR_BIT - 1)) { 295 bit <<= 1; 296 } else { 297 map = *mapp++; 298 bit = 1; 299 } 300 } 301 if (run != 0) { 302 if (run > fs->fs_contigsumsize) 303 run = fs->fs_contigsumsize; 304 sump[run]++; 305 } 306 } 307 if (bkgrdflag != 0) { 308 cstotal.cs_nffree += cg->cg_cs.cs_nffree; 309 cstotal.cs_nbfree += cg->cg_cs.cs_nbfree; 310 cstotal.cs_nifree += cg->cg_cs.cs_nifree; 311 cstotal.cs_ndir += cg->cg_cs.cs_ndir; 312 } else { 313 cstotal.cs_nffree += newcg->cg_cs.cs_nffree; 314 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree; 315 cstotal.cs_nifree += newcg->cg_cs.cs_nifree; 316 cstotal.cs_ndir += newcg->cg_cs.cs_ndir; 317 } 318 cs = &fs->fs_cs(fs, c); 319 if (cursnapshot == 0 && 320 memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0 && 321 dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 322 memmove(cs, &newcg->cg_cs, sizeof *cs); 323 sbdirty(); 324 } 325 if (rewritecg) { 326 memmove(cg, newcg, (size_t)fs->fs_cgsize); 327 cgdirty(); 328 continue; 329 } 330 if (cursnapshot == 0 && 331 memcmp(newcg, cg, basesize) != 0 && 332 dofix(&idesc[2], "SUMMARY INFORMATION BAD")) { 333 memmove(cg, newcg, (size_t)basesize); 334 cgdirty(); 335 } 336 if (bkgrdflag != 0 || usedsoftdep || debug) { 337 excessdirs = cg->cg_cs.cs_ndir - newcg->cg_cs.cs_ndir; 338 if (excessdirs < 0) { 339 pfatal("LOST %d DIRECTORIES\n", -excessdirs); 340 excessdirs = 0; 341 } 342 if (excessdirs > 0) 343 check_maps(cg_inosused(newcg), cg_inosused(cg), 344 inomapsize, 345 cg->cg_cgx * (ufs2_daddr_t) fs->fs_ipg, 346 "DIR", 347 freedirs, 0, excessdirs); 348 check_maps(cg_inosused(newcg), cg_inosused(cg), 349 inomapsize, 350 cg->cg_cgx * (ufs2_daddr_t) fs->fs_ipg, "FILE", 351 freefiles, excessdirs, fs->fs_ipg); 352 check_maps(cg_blksfree(cg), cg_blksfree(newcg), 353 blkmapsize, 354 cg->cg_cgx * (ufs2_daddr_t) fs->fs_fpg, "FRAG", 355 freeblks, 0, fs->fs_fpg); 356 } 357 if (cursnapshot == 0 && 358 memcmp(cg_inosused(newcg), cg_inosused(cg), mapsize) != 0 && 359 dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) { 360 memmove(cg_inosused(cg), cg_inosused(newcg), 361 (size_t)mapsize); 362 cgdirty(); 363 } 364 } 365 if (cursnapshot == 0 && 366 memcmp(&cstotal, &fs->fs_cstotal, sizeof cstotal) != 0 367 && dofix(&idesc[0], "SUMMARY BLK COUNT(S) WRONG IN SUPERBLK")) { 368 memmove(&fs->fs_cstotal, &cstotal, sizeof cstotal); 369 fs->fs_ronly = 0; 370 fs->fs_fmod = 0; 371 sbdirty(); 372 } 373 374 /* 375 * When doing background fsck on a snapshot, figure out whether 376 * the superblock summary is inaccurate and correct it when 377 * necessary. 378 */ 379 if (cursnapshot != 0) { 380 cmd.size = 1; 381 382 cmd.value = cstotal.cs_ndir - fs->fs_cstotal.cs_ndir; 383 if (cmd.value != 0) { 384 if (debug) 385 printf("adjndir by %+" PRIi64 "\n", cmd.value); 386 if (bkgrdsumadj == 0 || sysctl(adjndir, MIBSIZE, 0, 0, 387 &cmd, sizeof cmd) == -1) 388 rwerror("ADJUST NUMBER OF DIRECTORIES", cmd.value); 389 } 390 391 cmd.value = cstotal.cs_nbfree - fs->fs_cstotal.cs_nbfree; 392 if (cmd.value != 0) { 393 if (debug) 394 printf("adjnbfree by %+" PRIi64 "\n", cmd.value); 395 if (bkgrdsumadj == 0 || sysctl(adjnbfree, MIBSIZE, 0, 0, 396 &cmd, sizeof cmd) == -1) 397 rwerror("ADJUST NUMBER OF FREE BLOCKS", cmd.value); 398 } 399 400 cmd.value = cstotal.cs_nifree - fs->fs_cstotal.cs_nifree; 401 if (cmd.value != 0) { 402 if (debug) 403 printf("adjnifree by %+" PRIi64 "\n", cmd.value); 404 if (bkgrdsumadj == 0 || sysctl(adjnifree, MIBSIZE, 0, 0, 405 &cmd, sizeof cmd) == -1) 406 rwerror("ADJUST NUMBER OF FREE INODES", cmd.value); 407 } 408 409 cmd.value = cstotal.cs_nffree - fs->fs_cstotal.cs_nffree; 410 if (cmd.value != 0) { 411 if (debug) 412 printf("adjnffree by %+" PRIi64 "\n", cmd.value); 413 if (bkgrdsumadj == 0 || sysctl(adjnffree, MIBSIZE, 0, 0, 414 &cmd, sizeof cmd) == -1) 415 rwerror("ADJUST NUMBER OF FREE FRAGS", cmd.value); 416 } 417 418 cmd.value = cstotal.cs_numclusters - fs->fs_cstotal.cs_numclusters; 419 if (cmd.value != 0) { 420 if (debug) 421 printf("adjnumclusters by %+" PRIi64 "\n", cmd.value); 422 if (bkgrdsumadj == 0 || sysctl(adjnumclusters, MIBSIZE, 0, 0, 423 &cmd, sizeof cmd) == -1) 424 rwerror("ADJUST NUMBER OF FREE CLUSTERS", cmd.value); 425 } 426 } 427 } 428 429 static void 430 check_maps( 431 u_char *map1, /* map of claimed allocations */ 432 u_char *map2, /* map of determined allocations */ 433 int mapsize, /* size of above two maps */ 434 ufs2_daddr_t startvalue, /* resource value for first element in map */ 435 const char *name, /* name of resource found in maps */ 436 int *opcode, /* sysctl opcode to free resource */ 437 int skip, /* number of entries to skip before starting to free */ 438 int limit) /* limit on number of entries to free */ 439 { 440 # define BUFSIZE 16 441 char buf[BUFSIZE]; 442 long i, j, k, l, m, size; 443 ufs2_daddr_t n, astart, aend, ustart, uend; 444 void (*msg)(const char *fmt, ...); 445 446 if (bkgrdflag) 447 msg = pfatal; 448 else 449 msg = pwarn; 450 astart = ustart = aend = uend = -1; 451 for (i = 0; i < mapsize; i++) { 452 j = *map1++; 453 k = *map2++; 454 if (j == k) 455 continue; 456 for (m = 0, l = 1; m < CHAR_BIT; m++, l <<= 1) { 457 if ((j & l) == (k & l)) 458 continue; 459 n = startvalue + i * CHAR_BIT + m; 460 if ((j & l) != 0) { 461 if (astart == -1) { 462 astart = aend = n; 463 continue; 464 } 465 if (aend + 1 == n) { 466 aend = n; 467 continue; 468 } 469 if (astart == aend) 470 (*msg)("ALLOCATED %s %" PRId64 471 " MARKED FREE\n", 472 name, astart); 473 else 474 (*msg)("%s %sS %" PRId64 "-%" PRId64 475 " MARKED FREE\n", 476 "ALLOCATED", name, astart, aend); 477 astart = aend = n; 478 } else { 479 if (ustart == -1) { 480 ustart = uend = n; 481 continue; 482 } 483 if (uend + 1 == n) { 484 uend = n; 485 continue; 486 } 487 size = uend - ustart + 1; 488 if (size <= skip) { 489 skip -= size; 490 ustart = uend = n; 491 continue; 492 } 493 if (skip > 0) { 494 ustart += skip; 495 size -= skip; 496 skip = 0; 497 } 498 if (size > limit) 499 size = limit; 500 if (debug && size == 1) 501 pwarn("%s %s %" PRId64 502 " MARKED USED\n", 503 "UNALLOCATED", name, ustart); 504 else if (debug) 505 pwarn("%s %sS %" PRId64 "-%" PRId64 506 " MARKED USED\n", 507 "UNALLOCATED", name, ustart, 508 ustart + size - 1); 509 if (bkgrdflag != 0) { 510 cmd.value = ustart; 511 cmd.size = size; 512 if (sysctl(opcode, MIBSIZE, 0, 0, 513 &cmd, sizeof cmd) == -1) { 514 snprintf(buf, BUFSIZE, 515 "FREE %s", name); 516 rwerror(buf, cmd.value); 517 } 518 } 519 limit -= size; 520 if (limit <= 0) 521 return; 522 ustart = uend = n; 523 } 524 } 525 } 526 if (astart != -1) { 527 if (astart == aend) 528 (*msg)("ALLOCATED %s %" PRId64 529 " MARKED FREE\n", name, astart); 530 else 531 (*msg)("ALLOCATED %sS %" PRId64 "-%" PRId64 532 " MARKED FREE\n", 533 name, astart, aend); 534 } 535 if (ustart != -1) { 536 size = uend - ustart + 1; 537 if (size <= skip) 538 return; 539 if (skip > 0) { 540 ustart += skip; 541 size -= skip; 542 } 543 if (size > limit) 544 size = limit; 545 if (debug) { 546 if (size == 1) 547 pwarn("UNALLOCATED %s %" PRId64 548 " MARKED USED\n", 549 name, ustart); 550 else 551 pwarn("UNALLOCATED %sS %" PRId64 "-%" PRId64 552 " MARKED USED\n", 553 name, ustart, ustart + size - 1); 554 } 555 if (bkgrdflag != 0) { 556 cmd.value = ustart; 557 cmd.size = size; 558 if (sysctl(opcode, MIBSIZE, 0, 0, &cmd, 559 sizeof cmd) == -1) { 560 snprintf(buf, BUFSIZE, "FREE %s", name); 561 rwerror(buf, cmd.value); 562 } 563 } 564 } 565 } 566 567 static void clear_blocks(ufs2_daddr_t start, ufs2_daddr_t end) 568 { 569 570 if (debug) 571 printf("Zero frags %jd to %jd\n", start, end); 572 blerase(fswritefd, fsbtodb(&sblock, start), 573 lfragtosize(&sblock, end - start + 1)); 574 } 575