pass5.c revision 163845
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 32static 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: head/sbin/fsck_ffs/pass5.c 163845 2006-10-31 22:06:56Z pjd $"); 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 51static void check_maps(u_char *, u_char *, int, int, const char *, int *, int, int); 52 53void 54pass5(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 cstotal.cs_nffree += newcg->cg_cs.cs_nffree; 295 cstotal.cs_nbfree += newcg->cg_cs.cs_nbfree; 296 cstotal.cs_nifree += newcg->cg_cs.cs_nifree; 297 cstotal.cs_ndir += newcg->cg_cs.cs_ndir; 298 cs = &fs->fs_cs(fs, c); 299 if (cursnapshot == 0 && 300 memcmp(&newcg->cg_cs, cs, sizeof *cs) != 0 && 301 dofix(&idesc[0], "FREE BLK COUNT(S) WRONG IN SUPERBLK")) { 302 memmove(cs, &newcg->cg_cs, sizeof *cs); 303 sbdirty(); 304 } 305 if (rewritecg) { 306 memmove(cg, newcg, (size_t)fs->fs_cgsize); 307 cgdirty(); 308 continue; 309 } 310 if (cursnapshot == 0 && 311 memcmp(newcg, cg, basesize) != 0 && 312 dofix(&idesc[2], "SUMMARY INFORMATION BAD")) { 313 memmove(cg, newcg, (size_t)basesize); 314 cgdirty(); 315 } 316 if (bkgrdflag != 0 || usedsoftdep || debug) { 317 excessdirs = cg->cg_cs.cs_ndir - newcg->cg_cs.cs_ndir; 318 if (excessdirs < 0) { 319 pfatal("LOST %d DIRECTORIES\n", -excessdirs); 320 excessdirs = 0; 321 } 322 if (excessdirs > 0) 323 check_maps(cg_inosused(newcg), cg_inosused(cg), 324 inomapsize, cg->cg_cgx * fs->fs_ipg, "DIR", 325 freedirs, 0, excessdirs); 326 check_maps(cg_inosused(newcg), cg_inosused(cg), 327 inomapsize, cg->cg_cgx * fs->fs_ipg, "FILE", 328 freefiles, excessdirs, fs->fs_ipg); 329 check_maps(cg_blksfree(cg), cg_blksfree(newcg), 330 blkmapsize, cg->cg_cgx * fs->fs_fpg, "FRAG", 331 freeblks, 0, fs->fs_fpg); 332 } 333 if (cursnapshot == 0 && 334 memcmp(cg_inosused(newcg), cg_inosused(cg), mapsize) != 0 && 335 dofix(&idesc[1], "BLK(S) MISSING IN BIT MAPS")) { 336 memmove(cg_inosused(cg), cg_inosused(newcg), 337 (size_t)mapsize); 338 cgdirty(); 339 } 340 } 341 if (cursnapshot == 0 && 342 memcmp(&cstotal, &fs->fs_cstotal, sizeof cstotal) != 0 343 && dofix(&idesc[0], "SUMMARY BLK COUNT(S) WRONG IN SUPERBLK")) { 344 memmove(&fs->fs_cstotal, &cstotal, sizeof cstotal); 345 fs->fs_ronly = 0; 346 fs->fs_fmod = 0; 347 sbdirty(); 348 } 349 350 /* 351 * When doing background fsck on a snapshot, figure out whether 352 * the superblock summary is inaccurate and correct it when 353 * necessary. 354 */ 355 if (cursnapshot != 0) { 356 cmd.size = 1; 357 358 cmd.value = cstotal.cs_ndir - fs->fs_cstotal.cs_ndir; 359 if (cmd.value != 0) { 360 if (debug) 361 printf("adjndir by %+" PRIi64 "\n", cmd.value); 362 if (bkgrdsumadj == 0 || sysctl(adjndir, MIBSIZE, 0, 0, 363 &cmd, sizeof cmd) == -1) 364 rwerror("ADJUST NUMBER OF DIRECTORIES", cmd.value); 365 } 366 367 cmd.value = cstotal.cs_nbfree - fs->fs_cstotal.cs_nbfree; 368 if (cmd.value != 0) { 369 if (debug) 370 printf("adjnbfree by %+" PRIi64 "\n", cmd.value); 371 if (bkgrdsumadj == 0 || sysctl(adjnbfree, MIBSIZE, 0, 0, 372 &cmd, sizeof cmd) == -1) 373 rwerror("ADJUST NUMBER OF FREE BLOCKS", cmd.value); 374 } 375 376 cmd.value = cstotal.cs_nifree - fs->fs_cstotal.cs_nifree; 377 if (cmd.value != 0) { 378 if (debug) 379 printf("adjnifree by %+" PRIi64 "\n", cmd.value); 380 if (bkgrdsumadj == 0 || sysctl(adjnifree, MIBSIZE, 0, 0, 381 &cmd, sizeof cmd) == -1) 382 rwerror("ADJUST NUMBER OF FREE INODES", cmd.value); 383 } 384 385 cmd.value = cstotal.cs_nffree - fs->fs_cstotal.cs_nffree; 386 if (cmd.value != 0) { 387 if (debug) 388 printf("adjnffree by %+" PRIi64 "\n", cmd.value); 389 if (bkgrdsumadj == 0 || sysctl(adjnffree, MIBSIZE, 0, 0, 390 &cmd, sizeof cmd) == -1) 391 rwerror("ADJUST NUMBER OF FREE FRAGS", cmd.value); 392 } 393 394 cmd.value = cstotal.cs_numclusters - fs->fs_cstotal.cs_numclusters; 395 if (cmd.value != 0) { 396 if (debug) 397 printf("adjnumclusters by %+" PRIi64 "\n", cmd.value); 398 if (bkgrdsumadj == 0 || sysctl(adjnumclusters, MIBSIZE, 0, 0, 399 &cmd, sizeof cmd) == -1) 400 rwerror("ADJUST NUMBER OF FREE CLUSTERS", cmd.value); 401 } 402 } 403} 404 405static void 406check_maps( 407 u_char *map1, /* map of claimed allocations */ 408 u_char *map2, /* map of determined allocations */ 409 int mapsize, /* size of above two maps */ 410 int startvalue, /* resource value for first element in map */ 411 const char *name, /* name of resource found in maps */ 412 int *opcode, /* sysctl opcode to free resource */ 413 int skip, /* number of entries to skip before starting to free */ 414 int limit) /* limit on number of entries to free */ 415{ 416# define BUFSIZE 16 417 char buf[BUFSIZE]; 418 long i, j, k, l, m, n, size; 419 int astart, aend, ustart, uend; 420 void (*msg)(const char *fmt, ...); 421 422 if (bkgrdflag) 423 msg = pfatal; 424 else 425 msg = pwarn; 426 astart = ustart = aend = uend = -1; 427 for (i = 0; i < mapsize; i++) { 428 j = *map1++; 429 k = *map2++; 430 if (j == k) 431 continue; 432 for (m = 0, l = 1; m < CHAR_BIT; m++, l <<= 1) { 433 if ((j & l) == (k & l)) 434 continue; 435 n = startvalue + i * CHAR_BIT + m; 436 if ((j & l) != 0) { 437 if (astart == -1) { 438 astart = aend = n; 439 continue; 440 } 441 if (aend + 1 == n) { 442 aend = n; 443 continue; 444 } 445 if (astart == aend) 446 (*msg)("ALLOCATED %s %d MARKED FREE\n", 447 name, astart); 448 else 449 (*msg)("%s %sS %d-%d MARKED FREE\n", 450 "ALLOCATED", name, astart, aend); 451 astart = aend = n; 452 } else { 453 if (ustart == -1) { 454 ustart = uend = n; 455 continue; 456 } 457 if (uend + 1 == n) { 458 uend = n; 459 continue; 460 } 461 size = uend - ustart + 1; 462 if (size <= skip) { 463 skip -= size; 464 ustart = uend = n; 465 continue; 466 } 467 if (skip > 0) { 468 ustart += skip; 469 size -= skip; 470 skip = 0; 471 } 472 if (size > limit) 473 size = limit; 474 if (debug && size == 1) 475 pwarn("%s %s %d MARKED USED\n", 476 "UNALLOCATED", name, ustart); 477 else if (debug) 478 pwarn("%s %sS %d-%ld MARKED USED\n", 479 "UNALLOCATED", name, ustart, 480 ustart + size - 1); 481 if (bkgrdflag != 0) { 482 cmd.value = ustart; 483 cmd.size = size; 484 if (sysctl(opcode, MIBSIZE, 0, 0, 485 &cmd, sizeof cmd) == -1) { 486 snprintf(buf, BUFSIZE, 487 "FREE %s", name); 488 rwerror(buf, cmd.value); 489 } 490 } 491 limit -= size; 492 if (limit <= 0) 493 return; 494 ustart = uend = n; 495 } 496 } 497 } 498 if (astart != -1) { 499 if (astart == aend) 500 (*msg)("ALLOCATED %s %d MARKED FREE\n", name, astart); 501 else 502 (*msg)("ALLOCATED %sS %d-%d MARKED FREE\n", 503 name, astart, aend); 504 } 505 if (ustart != -1) { 506 size = uend - ustart + 1; 507 if (size <= skip) 508 return; 509 if (skip > 0) { 510 ustart += skip; 511 size -= skip; 512 } 513 if (size > limit) 514 size = limit; 515 if (debug) { 516 if (size == 1) 517 pwarn("UNALLOCATED %s %d MARKED USED\n", 518 name, ustart); 519 else 520 pwarn("UNALLOCATED %sS %d-%ld MARKED USED\n", 521 name, ustart, ustart + size - 1); 522 } 523 if (bkgrdflag != 0) { 524 cmd.value = ustart; 525 cmd.size = size; 526 if (sysctl(opcode, MIBSIZE, 0, 0, &cmd, 527 sizeof cmd) == -1) { 528 snprintf(buf, BUFSIZE, "FREE %s", name); 529 rwerror(buf, cmd.value); 530 } 531 } 532 } 533} 534