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