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